Winter 2006 Midterm Solutions |
Problems | Grader |
---|---|
1 | Mendel |
2 | Ben |
3, 5 | Nazia |
4 | Josh |
Note: FIFO or FCFS schedulers can starve unless you add time slices and preemption to the scheduler.
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:
- 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.
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.
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...
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:
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;
-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.