Answer set

Problem 1
(a) false. The Banker's algorithm is used to avoid deadlock and 
    not to see if a bank account is balanced or not.
(b) false.  The amount of addressable memory is determined by
    the number of bits of virtual address, not the translation scheme.
(c)  true. Address translation provides protection.

Problem 2
(a) An interrupt handler can't block because the interrupt handler
     runs in the context of the current thread, so:
    (i) the interrupted thread won't be able to continue until the 
	  interrupt returns
    (ii) other interrupts aren't allowed until the interrupt returns
    (iii) an interrupt has doesn't have a thread control block or 
       its own stack, and so it can't be pulled on/off the ready list 

(b) Shortest job first is optimal.  If round robin ever takes a time
slice, it can't be optimal, because SJF never time slices between jobs.

However, if there's only one job, or if all jobs are shorter
than the time slice, and they are all the same length, then RR = FIFO = SJF.

Problem 3
3 resource ordering
4 claiming in advance
2 eliminating waiting
1 detect and correction

An explanation:

Deadlock detection lets the program go ahead normally, as if
deadlock isn't a consideration, until you get into a deadlock.
Maximal concurrency.

Eliminating waiting also lets the program go ahead normally, as if
deadlock isn't a consideration, until the program tries to grab
a resource that's in use.  Since resources are typically unused
(contention for resources is low), then almost as good as detecting
and breaking deadlock.

Resource ordering is a greater restriction on the behavior
of the program -- the program can't grab resources out of order,
even if they are unused (as an analogy, this is like making all the cars
drive around the Bay clockwise to avoid deadlock).

Claiming all resources in advance is even stricter than resource
ordering.


Problem 4

(a)

struct segment_entry {
    PageTable *pageTable; 		// also OK was base & bounds
    int pageTableSize;
    }

struct page_entry {
    int physicalPageFrame;		// note: no size field!
					// all pages are same length!
    }

(b)
(Assuming segSize and pageSize are in bytes.  If in bits, it's
a little more complicated, but still do-able.)

segTable[quot(vaddr, segSize)].pageTable[
	quot(rem(vaddr,segSize), pageSize)].physicalpageFrame*pageSize
		+ rem(vaddr, pageSize)

Problem 5 
(a) With Mesa style monitors, a signalled thread is put on the ready queue
with no special priority.  As a result, another thread can slip in
and grab the monitor lock before the signalled thread. When the signalled 
thread eventually gets the CPU, the monitor lock could be busy, but even
if it isn't, the condition may have changed, so that the signalled
thread may have to go back to sleep (in other words, the "if" vs. "while"
issue in Mesa-style monitors ).

(b)

The approach is just to make sure no other thread can grab
the semaphore before the signalled thread.  So in V, if someone
is waiting, signal them, but *don't* increment the semaphore.
That way, the signalled thread will go, and no one else can slip in.

This assumes condition->Wait() keeps threads in FIFO order (which
is true for almost all of your implementations for Nachos assignment 
1); you can also build an explicit list of threads, each with their
own condition variable, if you don't like that assumption.

class Semaphore {
Lock lock;
Condition condition;
int value;
int numWaiters;
}

P() {
   lock->Acquire(); 

   if(count == 0) {
      numWaiters++;
      condition->Wait(lock);
      }
   else
      count--;
   lock->Release();
   }

Semaphore::V() {
   lock->Acquire();

   if (numWaiters > 0) {
	numWaiters--;
	condition->Signal(lock);
   } else
        count++;

   lock->Release();
   }