%
% The Lion's Commentary, file ch26.tex, version 1.4, 15 May 1994
%
\se{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.

\sbs{Section One}

\bd
\item[1.1] Devise changes to ``malloc'' (2528)
to implement the Best Fit algorithm.

\item[1.2] Rewrite the procedure ``mfree''
(2556) to render its function more
easily discernible by the reader.

\item[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?

\item[1.4] Prove that ``malloc'' and ``mfree''
jointly solve the memory aliocation
problem correctly.

\item[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.

\item[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.

\item[1.7] Compile the program

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

and compare the result with the contents of the array ``icode'' (1516).

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

\item[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?

\item[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?

\item[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.

\item[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.

\item[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.
\ed

\sbs{Section Two}

\bd
\item[2.1] Explain in detail how the system
reacts to a floating point trap which
occurs when the processor is in kernel
mode.

\item[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.

\item[2.3] Document ``backup'' (1012).

\item[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.

\item[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.
\ed

\sbs{Section Three}

\bd
\item[3.1] Rewrite the procedure ``sched'' to
avoid the use of ``goto'' statements.

\item[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.

\item[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?

\item[3.4] Explain why the buffer areas
declared on line 4720 are 514, and not
512, characters long.

\item[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.
\ed

\sbs{Section Four}

\bd
\item[4.1] Devise a scheme for labelling file
system volumes and checking these
labels when the volumes are mounted.

\item[4.2] Discuss the problems of supporting
ANSI standard labelled tapes under
UNIX, and propose a solution.

\item[4.3] Design a scheme for providing index
sequential access to files.

\item[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.

\item[4.5] Devise a technique to measure the
efficiency of pipes. Apply the technique and report your results.

\item[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.

\item[5.1] By monitoring the number of free
buffers or otherwise, determine whether
the number of character buffers provided at your installation is adequate.

\item[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.

\item[5.3] Redesign the line printer driver to
handle overprinting and backspacing
more efficiently in the sense of
minimising the number of print cycles.

\item[5.4] Document ``mmread'' (0916) and
``mmwrite'' (9042).
\ed
\sbs{General}

\bd
\item[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:

\bd
\item[(a)] reduce the space required by 500
words;

\item[(b)] utilise an additional 500 words.
\ed

\item[6.2] Discuss the merits of ``C'' as a systems programming language. What
features are missing? or superfluous?
\ed