CSE120, Fall 2005, Homework 2
Due: October 18, in class

1. [10 pts] What are the benefits of kernel threads?  What are the 
benefits of user-level threads?  How might the operating system combine 
the benefits of both of these styles of threading?

2. [10 pts] When are spinlocks preferable to semaphores?  When are 
semaphores preferable to spinlocks?  Why?

3. [Silberschatz] [10 pts] Show that, if the wait and signal operations 
(of a semaphore) are not executed atomically, then mutual exclusion may 
be violated.

4. [10 pts] Suppose we devise a new scheduling algorithm, Longest 
Elapsed Time (LET).  With LET, at each scheduling interval, we select 
the job that has run for the longest amount of time already.  If two 
jobs have run for the same amount of time, we choose between them at 
random.  Assume no two jobs begin simultaneously.  How does LET compare 
to other scheduling algorithms?  How is it the same as or different than 
other scheduling algorithms?

5. [10 pts] Suppose the architecture provides a single atomic operation: 
test-and-increment.  This operation atomically takes the contents of a 
register, increments it, and returns its old value prior to increment.  
Assume that the registers are 32-bit integers that wrap around upon 
increment at 2^32 - 1, returning to 0.  Can a spinlock be built using 
this operation on a single register?  If so, write pseudocode for its 
acquire() and release() methods.  (You may not disable interrupts.)

6. [15 pts] The dining philosophers problem is a classic problem in 
which N philosophers sitting at a circular table are trying to eat; each 
philosopher has one fork to the left and one fork to the right (thus 
there are N forks).  In order to eat, a philosopher needs two forks at 
the same time, but can atomically pick up only one at a time.  Clearly 
it's not possible for all the philosophers to eat at the same time, but 
we want them all to eat eventually.

Suppose all the philosophers use the following strategy to eat: first 
they wait for their right fork to become available and once it does, 
they pick it up.  Then they wait for and pick up their left fork 
similarly.  Once they have both forks, they eat, and after eating, put 
down both forks.  Will this approach work, and will all the philosophers 
be able to eat?  Is there any way for the philosophers to eat assuming 
that they all use the exact same strategy?  Why or why not?

7. [15 pts] Suppose the hardware does not support virtual memory yet we 
want to enable concurrency.  Suppose we have two pieces of software that 
are designed to run by themselves, but we want to run them concurrently 
in the same address space.  Assume that these programs only make valid 
memory references and never allocate more than a predetermined amount of 
memory.  How might we design a "thread" scheduler that controls these 
two processes?  How would the programs' binaries have to be modified to 
support this?

8. [20 pts] Suppose the kernel and user space processes share a special 
memory page which contains the contents of some kernel data structure 
that user-space processes want to read (system time, for example).  The 
kernel periodically updates the contents of this page, and user 
processes read from it; the kernel has read-write access to the page, 
but user processes have read-only access to it.  We want to provide 
consistency guarantees - if a user process were to read the page while 
the kernel is updating it, the process may get inconsistent results, and 
since the page is read-only to the user process, we can't use a 
traditional mutex to protect the data structure.

Devise a method write() which executes in the kernel that performs the 
data structure update.  Devise a method read() which executes in the 
user process that has two possible return values - either it 
successfully reads the data structure and returns "success" or it 
detects that there was an inconsistency and returns "failure" (meaning 
that the kernel may have been writing concurrently).  read() may fail 
due to a perceived inconsistency arbitrarily many times, but it should 
eventually succeed on re-execution.  (In other words, read() should not 
simply always "detect an inconsistency".)

To aid in this, assume you have an arbitrary number of counters that 
reside in that page which can be atomically incremented or decremented 
(only by the kernel, obviously).  Write write() and read() in pseudocode 
as needed, and assume you have subroutines writestructure() and 
readstructure() that do the actual data structure writing and reading.