26 Suggested Exercises

Any operating system design involves many subjective and ad hoc judgements on the part of system’s designers. At many places in the UNIX source code you will find yourself wondering “Why did they do it that way?”, “What would happen if I changed this?”

The following exercises express some of these questions. Some can be answered from an examination of the source code alone after a study in more depth; others require some experimental probing and measurement, for which read-only access to the file “/dev/kmem” via terminal will prove invaluable; and still others really require the construction and testing of experimental versions of the operating system.

26.1 Section One

1.1

Devise changes to “malloc” (2528) to implement the Best Fit algorithm.

1.2

Rewrite the procedure “mfree” (2556) to render its function more easily discernible by the reader.

1.3

Investigate the adequacy of the sizes of the arrays “coremap” and “swapmap” (0203, 0204). How should “CMAPSIZ” and “SWAPSIZ” change when “NPROC” is increased?

1.4

Prove that “malloc” and “mfree” jointly solve the memory aliocation problem correctly.

1.5

By monitoring the contents of “coremap”, estimate the efficiency with which main memory is utilised. Estimate also the cost of compacting “in use areas” of main memory from time to time to reduce memory fragmentation.

Hence decide whether it would be worthwhile to extend the present memory allocation scheme to include memory compaction.

1.6

In setting the first six kernel page description registers, UNIX does not make use of all the hardware protection features that are available e.g. some pages which contain only pure text could be made read-only. Devise changes to the code to maximise the use of the available hardware protection.

1.7

Compile the program

    char *init ``/etc/init'';
    main ( ) {
    execl (init, init, 0);
    while (1);
    }

and compare the result with the contents of the array “icode” (1516).

1.8

Investigate the size required for kernel mode stack areas. Hence show that the 367 word area which is provided is adequate.

1.9

If main memory consists of several independent memory modules and one of these, not the last, is down, “main” will not include memory modules beyond the one which is down, in the list of available space in “coremap”. Devise some simple changes to “main” to handle this situation. what other parts of the system would also need revision?

1.10

Rewrite the routines “estabur” (1650) and “sureg” (1739) so that they will work as efficiently as possible on the PDP11/40. How often are these routines used in practice? Would it really be worthwhile trying to implement your improved versions?

1.11

Investigate the overheads involved in initiating a new process. Perform a series of measurements for a set of different sized programs under different conditions.

1.12

Evaluate the following scheme which is intended by Ken Thompson as the basis for a revised scheduling algorithm:

A number “p” is kept for each process, stored as “p_cpu”. “p” is incremented by one every clock tick that the process is found to be executing. “p” therefore accumulates the CPU usage. Every second, each value of “p” is replaced by four fifths of its value rounded to the nearest integer. This means that “o” has values which are bounded by zero and the solution of the equation \(k = 0.8*(k + HZ)\) i.e. 4*HZ. Hence if HZ is 50 or 60, and “p” is integerised, “p” can be stored in one byte.

1.13

The “proc” table is always searched via a direct linear search. As the table size is increased, the search overheads also increase. Survey the alternatives for improving the search mechanism, when “NPROC” is say 300.

26.2 Section Two

2.1: Explain in detail how the system reacts to a floating point trap which occurs when the processor is in kernel mode.
2.2: When a process dies, a “zombie” record is written to disk, and is subsequently read back by the parent. Devise a scheme for passing back the necessary information to the parent which will avoid the overhead of the two i/o operations.
2.3: Document “backup” (1012).
2.4: It is relatively easy using the “shell” to set up a set of asynchronous processes which will flood your terminal with useless output. Trying to stop these processes individually can be a problem, since their identifying numbers may not be known. Use of the command “kill 0” is usually an act of sheer desperation. Devise an alternative scheme, e.g. based on the use of messages such as “kill –99”, which will be effective, but more selective.
2.5: Design a form of coroutine jump whlch will cause control to pass more efficiently between a program which is being traced, and its parent.

26.3 Section Three

3.1

Rewrite the procedure “sched” to avoid the use of “goto” statements.

3.2

Modify “sched” so that the text segment and data segment for a program will possibly be allocated in separate main memory areas if a single large area is not immediately available.

3.3

If the system crashes and must be “rebooted” the contents of the buffers which were not written out at the time of the crash are lost.

However if a core dump is taken, the contents of the buffers can be obtained and hence the contents of the disk can be brought completely up to date. Outline a detalled plan for carrying out this scheme. How effective do you think it would be?

3.4

Explain why the buffer areas declared on line 4720 are 514, and not 512, characters long.

3.5

Explain how deadlock situations may arise if there are too few “large” buffers available. What measures can you suggest to alleviate the problem, assuming that increasing the number of buffers is not possible.

26.4 Section Four

4.1: Devise a scheme for labelling file system volumes and checking these labels when the volumes are mounted.
4.2: Discuss the problems of supporting ANSI standard labelled tapes under UNIX, and propose a solution.
4.3: Design a scheme for providing index sequential access to files.
4.4: The emergence of the “sticky bit” (see “CHMOD(I)” in the PM) confirms that there are some residual advantages in allocating all the space for a file contiguously. Discuss the merits of making “contiguous files” more generally available.
4.5: Devise a technique to measure the efficiency of pipes. Apply the technique and report your results.
4.6: Devise modifications to “pipe.c” which will make pipes more efficient according to the following scheme: whenever the “read” pointer is greater than 512, rotate the non-null block numbers in the “inode” ana decrease both the “read” and “write” pointers by 512.
5.1: By monitoring the number of free buffers or otherwise, determine whether the number of character buffers provided at your installation is adequate.
5.2: Perform measurements and/or experiments to determine whether the character buffer blocks would be more efficiently utilised if they consisted of four or eight characters, rather than six, per block.
5.3: Redesign the line printer driver to handle overprinting and backspacing more efficiently in the sense of minimising the number of print cycles.
5.4: Document “mmread” (0916) and “mmwrite” (9042).

26.5 General

6.1

The easiest way to vary the main memory space used by the operating system is to vary “NBUF”. If this is forbidden, propose the best way to:

(a): reduce the space required by 500 words;
(b): utilise an additional 500 words.

6.2

Discuss the merits of “C” as a systems programming language. What features are missing? or superfluous?