Sample Final, Fall 2009

NAME: __________________________________

CPSC 323a  Second In-Class Examination

Do all work on the exam.  Each problem is worth the number of points noted,
which may not be proportional to its level of difficulty.

 1. a. (8 points) Describe how segmentation works.  Give sufficient detail as
    to define all of the following terms:  physical address space, virtual
    address space, segment, segment table, segment length, protection,
    segmentation fault, and memory map.  Circle each term at the point it is
    defined.

    b. (4 points) Give two advantages of segmentation over paging and two
    disadvantages.

 2. (10 points) Do the following code segments guarantee mutual exclusion?  Are
    they deadlock-free?  Justify your answers.  (Assume that Pturn, Qturn, and
    turn are shared variables which have been initialized to FALSE, FALSE, and
    P respectively.)

     P: for (;;) {                        Q: for (;;) {
	   Pturn = TRUE;                        Qturn = TRUE;
	   turn = P;                            turn = Q;
	   while (Qturn && turn == P)           while (Pturn && turn == Q)
	      ;                                    ;
	   <USE RESOURCE>                       <USE RESOURCE>
	   Pturn = FALSE;                       Qturn = FALSE;
	}                                    }

 3. In designing a new computer you have decided to break instruction execution
    into three stages:  fetch instruction, decode instruction, and execute
    instruction.

    a. (2 points) How could having a uniform instruction length help you
    pipeline this three-stage process?

    b. (2 points) How could having a regular instruction format (i.e., the same
    sets of bits specify register operands / offsets whenever an instruction
    contains these fields) help you reduce the cycle time in a pipelined
    implementation of this three-stage process?

    c. (4 points) What is a branch hazard?  Give two ways of dealing with this
    problem in a pipelined implementation of this three-stage process?

 4. (5 points) Imagine that you had to implement the UNIX system on a
    microcomputer where main memory was in short supply.  After much program
    "tuning", it still did not quite fit, so you picked a group of system calls
    at random to sacrifice for the general good -- MKDIR/RMDIR/CHDIR lost.
    Design a file-naming convention and a subroutine library that would allow
    user-level routines to pretend that they are dealing with a hierarchical
    file system.  What changes (if any) would need to be made to the shell and
    the Standard I/O Library in order to implement this scheme.

								CS-323-12/08/09