: Section One

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.