Unix Internals
Dayton Clark
Summer 1998
Final Exam
Due: August 3rd, (~35% of grade)


The final exam.


Getting started 

% mkdir final

% cd final



  1. Answer question 1.9, page 16, in the text.
  2. Consider question 2.11, page 53, in the text.   Using the code fragment from the question, answer the questions below.  Ignore the instruction cache, we are interested only in the data cache.  The size of the data cache is 8K bytes (4 bytes per int).  Answer the questions first assuming a 16 byte line, then for a 256 byte line.
    1. Describe the layout of the array in memory including how many bytes the array takes in total.  Note different compilers on different machines would lay this out differently.  It is not so important how you decide to lay it out, but I want you to specify a layout to use for the purposes of this question.
    2. Specify the total number of data references in the for loop.
    3. Specify the total number of data cache hits in the for loop.
    4. Specify the total number of data cache misses in the for loop.
  3. Answer question 3.4, page 79, in the text.
  4. Answer question 9.8, page 192, in the text.
  5. On page 205 of the text the author suggests that a kernel might include code to automatically release and obtain spin-locks around context switches.  I want you to write this code.  Asumptions:
    1. There are 32 spin-locks in the kernel.  They are kept in a global array, int spin-lock[32].
      1. For each process there is a structure, struct proc, which contains the process specific data.  In this structure is a field, int locks, which is a bit-map used for keeping track of locks held by the process.
    2. There is a function, struct proc* curproc(), which returns a pointer to the current process's struct proc.
    3. The processor supports a test-and-set instruction and a routeine, int testandset(int* location), is available to you.
    Code the following routines.  Note: I expect reasonably accurate C code with enough comments to make it clear what you are doing.  I will not attempt to compile the code and will not deduct for minor syntactical errors.  Also, auxilliary procedures which are awkward to code do not need to be coded in detail, for instance if you require that a list of integers be sorted you can substitute a comment like // sort the array into ascending order instead of the actual sort code.
    1. void lock(int n) which obtains spin-lock n.  This routine simply obtains the lock, it makes no assumptions or checks as to other locks that the process may hold.  This routine is responsible for updating the process's locks map.
    2. void unlock(int n) which releases spin-lock n.  This routine simply releases the lock, it makes no assumptions or checks as to other locks that the process may hold.  This routine is responsible for updating the process's locks map.
    3. void suspend_release() which releases all held spin-locks prior to suspending the current process.
    4. void suspend_restore() which re-obtains all the locks that the current process had before being suspended.
    5. For extra credit implement void safe_lock(int n) which obtains a lock in a deadlock free manor.

You are free to consult and non-living resource for this exam.  You may refer to any book or document on the web, but you may not consult with any living person, except for me.  I am practiced and good at detecting collaboration and will give all concerned a zero for the exam if I discover any.


Hand it in 

To hand it in use toteach as follows
% ~clark/bin/toteach -a final Discussion
where -a final indicates that this is the final exam (this is not necessary if you are in a directory named final).
Note that as of today, July 27th, toteach, is not set up for the final.  I will try to set it up tonight.