COMS W4118: Operating Systems I
			      Spring, 2000
		    Comprehensive Exam: May 2, 2000

DIRECTIONS
This exam is closed book, calculator is permitted.  You have 60
minutes to complete the exam.  Complete the following four questions.
The questions are all of equal weight.  The order of the questions is
random, so the difficulty may vary from question to question.  Don't
get stuck by insisting on doing them in exact order; as long as your
answers are clearly labeled with the problem numbers, they can appear
in any order in your exam book.  Make sure you write your name and
email address on the front cover of your exam book.

You need not write a novel in order to get full credit.  In fact,
beyond a certain point excess verbiage begins to suggest uncertainty
and will be penalized.  Use diagrams when possible or necessary.


1.  Suppose we have a producer and a consumer.  The producer produces
    items and inserts them into a queue owned by the consumer, while
    the consumer consumes items from its queue in FIFO order.  Each
    item requires 1 time quantum to produce and 1 time quantum to
    consume.  The queue is initially empty and has a maximum size of
    3.  If the queue is full when a producer wants to run, the
    producer will spin wait until the queue is not full.  If the
    queue is empty when the consumer wants to run, the consumer will
    spin wait until the queue is not empty.  Consider the case when
    we run three producers P1, P2, and P3, and one consumer C1 and all
    of the processes are runnable starting at time zero.

    a)  If round-robin scheduling is used to execute the processes,
        how many items will each process have produced and consumed
        at the end of 10 time quanta?  Assume that the initial run
        queue order is P1, P2, P3, C1.

    b)	If priority scheduling is used to execute the processes and
        the priorities P(X) are assigned as P(C1)=4, P(P3)=3, P(P2)=2,
        P(P1)=1, how many items will each process have produced and
        consumed at the end of 10 time quanta?  Assume that a larger
        number is a higher priority.

    c)	Suppose priority scheduling is used to execute the processes
        and the priorities are assigned as in part b, except that
        P(C1)=0 unless the queue is full, in which case P(C1)=4.  How
        many items will each process have produced and consumed at
        the end of 10 time quanta?   

    d)  Suppose processes were scheduled as in part a, except that
        processes waited by blocking instead of spinning.  How many
        items will each process have produced and consumed at the end
        of 10 time quanta?


2.  Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in
    order), how would each of the following algorithms place processes
    of 212K, 417K, 112K, and 426K (in order)?  

    a)  First-fit

    b)  Best-fit

    c)  Next-fit

    d)  Worst-fit

    e)  Which algorithm makes the most efficient use of memory?


3.  Consider a file currently consisting of 100 blocks.  Assume that
    the file control block (and the index block, in the case of
    indexed allocation) is already in memory.  Calculate how many disk
    I/O operations are required for contigious, linked, and indexed
    (single-level) allocation strategies, if, for one block, the
    following conditions hold.  In the contiguous-allocation case,
    assume that there is no room to grow in the beginning, but there
    is room to grow in the end.  Assume that the block information to
    be added is stored in memory.

    a)  The block is added at the beginning.

    b)	The block is added in the middle.

    c)	The block is added at the end.

    d)	The block is removed from the beginning.

    e)	The block is removed from the middle.

    f)	The block is removed from the end.


4.  You are to implement the OS2000 timer interrupt handler tint() for
    the timer interrupt mechanism used on the x99 hardware architecture.  
    x99 has two 64-bit hardware registers, a COUNT register and a
    COMPARE register.  COUNT is initially zero and COMPARE is
    initially 1000.  Every microsecond, x99 increments COUNT by one
    and compares the value of COUNT with COMPARE.  If the values are
    equal, the x99 hardware generates a timer interrupt, which calls
    tint().  To do proper OS2000 scheduling, tint() needs to increment
    a global variable TICK by one every millisecond.  To do this,
    tint() must read and write COUNT and COMPARE to ensure that a
    timer interrupt is regularly generated.  Register reads and writes
    are atomic, but there is no atomic read-then-write operation.

    a)  Consider the following tint() implementation.  Every time the
        timer interrupt goes off, tint() increments TICK by one and
        resets COUNT to zero.  COMPARE is left unchanged.  Will this
        approach generate a timer interrupt every millisecond?
        Explain why or why not.

    b)  Explain in English a more robust method than the one used
        in part a for updating the hardware registers to generate a
        timer interrupt every millisecond.  You can assume that tint()
        requires less than a millisecond to execute, so long as it
        does not use a divide operation.  For this part of the
        problem, you can also assume that all interrupts are disabled
        while tint() executes (i.e. if any other interrupts occur,
        they will not be handled until after tint() completes).

    c)	You are now told that due to a new change in x99, there are
        high priority interrupts that cannot be disabled and may go off
	and "preempt" tint() while it is executing.  These interrupts
        occur infrequently, but may require more than a millisecond to
        process.  Using pseudo-C, write a correct implementation of
        tint() that accounts for the fact that other interrupts may go
        off and delay the completion of tint().  If multiple
        milliseconds elapse before tint() completes, TICK should be
        incremented to account for each millisecond.