Winter 2006 Midterm Solutions

About This Midterm

Problem 1

Part (a)

Answer:
A round-robin CPU scheduler that runs each job for a time-slice and then switches will guarantee that all jobs get at least some access to the CPU so we will not get starvation.

Note: FIFO or FCFS schedulers can starve unless you add time slices and preemption to the scheduler.

Part (b)

Answer:
Shortest job to completion first (SJC) running a workload with many short jobs can starve long running software. Similarly, a strict priority scheme in which a high priority job runs continuously so lower priority jobs will starve.

Part (c)

There are several possible answers for this question depending on how you choose to attack the problem. For example, you could argue that the CPU can be safely preempted so any scheduling algorithm with this capability violates one of the four necessary and sufficient conditions of deadlock and hence can.t deadlock. You could also go the other way and argue that a sufficiently perverse algorithm such as one that doesn.t include the ability to preempt and maintains a relationship between jobs where one has to wait for another could in fact generate a deadlock condition.

Note: Describing a deadlock involving threads waiting for a lock doesn.t really involve the CPU scheduling algorithm so it doesn.t answer the question being asked.

Note: Describing a CPU algorithm that results in starvation (e.g. strict priority scheme with or without priority donation) doesn.t really answer the question either. It also hits on the subtle difference between starvation and deadlock. Starvation means there is a path to making forward process but the scheduler is not choosing it. Deadlock means there is no path forward. Answer:

Problem 2

Part (a)

Answer:
There were many different ways of answering this problem, but a typical good answer should mention the following:

- Use a hierarchical memory mapping system, where the outer level is always present in memory and the inner level of user page tables can be paged
- Treat the user page tables similar to pages themselves so they can be swapped to and from virtual memory from disk, and manage present/not present bits
- Page tables can be retrieved on a page fault when trying to resolve a virtual address. Need some way to map page faulting address to physical location of the page table. Some people mentioned mapping a process' pid to a location on disk, others used fixed disk locations. At least mentioning you need some way to track the page tables on disk was required.
- Some eviction policy is required for page tables. LRU or clock algorithm is acceptable.

Part (b)

Answer:
Yes. In the scheme above, we can see that it is possible to make the whole page table bigger than physical memory by storing parts of it on disk. It could also be necessary given very small pages (extreme case of 1 page = 1 byte) and small physical memory. The overhead space needed for address translation could be bigger than the physical memory.

Problem 3

Answer:
Replacing enable/disable interrupts with a spin-lock would not work. The reason is that if we just have spin locks to synchronize access to kernel data, an interrupt could occur at any time (since the interrupts aren't disabled) and these data structures could be modified in the interrupt handler. And so, the kernel data would not be in a consistent state, as mutual exclusion is not preserved when interrupts are not disabled.

Another acceptable answer was:

Yes, this scheme would work if the spin-lock was implemented such that it disabled interrupts. It would work because spin locks would prevent threads running on other processors from modifying the kernel data, and disabling interrupts would prevent the interrupt handler from accessing these data structures, and so access to the kernel data structures would be exclusive to the thread that acquires the spin lock.

Problem 4

Answer:
There are three keys to the problem: you need some way to keep track of how many ticks have passed relative to the alarm request amount; you need some way to communicate between the Tick() function and the WaitFor() function; you need to support alarm requests from more than one thread. Here is the simplest solution, which received extra credit for using just one condition variable...

monitor struct {
  condition alarm_cond;

  void WaitFor(int ticks) {
    int i;
    for (i = 0; i < ticks; i++)
      wait(alarm_cond);
  }

  void Tick() {
   broadcast(alarm_cond);
  }
} AlarmClock;
Solutions that used a list of condition variables, a list of wakeup times, and the wait/signal synchronization scheme received full credit. There were many variations of this solution; in general, if it worked, it received full credit. Common mistakes:
-Supporting only one sleeping thread. If there is only one condition variable, 'broadcast' must be used instead of 'signal'. Otherwise, one sleeping thread may steal all the signals and another thread could sleep too long or even starve. Storing the 'ticks' request in a global variable was another common mistake that would break multi-thread sleeping.
-Using locks or semaphores instead of condition variables. Monitors use an implicit locking scheme for synchronization; for this reason, standard synchronization primitives won't work inside a monitor function.
-Adding unnecessary locking around the monitor functions. No points were deducted for this mistake.
-Forgetting to declare additional data members.

Problem 5

Part (a)

Answer:
The error "External Reference FOO not found" would be generated in the second pass of the linker. This is because the linker patches reference using the file and the global symbol table in the second pass, and when it does not find FOO, it generates this error.

Part (b)

Answer:
The error "Duplicate symbol definition FOO" would be found in the first pass of the linker. Since the linker constructs the global symbol table with an entry for every symbol used or defined during the first pass, when it comes across another definition of FOO, it complains because FOO already exists in the global symbol table.