Fall 2002 Midterm Solutions |
Problem | Grader |
---|---|
1, 2 | Mendel |
3, 6 | John |
4, 5 | Dan |
Priority donation can be approximated in a lottery scheduling system by having the waiting process loan its tickets to the process holding the resource that it needs. The tickets are returned to the original process when the resource is released and that process can continue.
Part B
Having a short time slice for the high priority queues causes I/O-bound jobs to stay with a high priority while CPU-bound jobs quickly exceed the time slices and drop to lower priority queues. Once in low priority queues the CPU-bound jobs are given long time slices to avoid the overhead of the time slices ending frequently while the CPU-bound job is running. In this way the time slice helps both in segregation of the jobs as well as efficient implementation of CPU-bound jobs.
Part C
It is relatively ease to imagine workloads in which round-robin isn't fairest under most fairness criteria. For example, a system with a mixture of I/O-bound and CPU-bound jobs would disfavor the I/O-bounds which don't use the entire timeslice for each burst.
Unlike physical memory, the CPU is easily preempted and hence violates one of the four necessary and sufficient conditions for deadlock.
Part B
There are many ways of answering this question. Unlike physical memory, virtual memory can be easily preempted breaking one of the causes of deadlock. The swap area of virtual machine is a finite, shared resource that it possible to deadlock on.
Part C
Disabling interrupts prevents interrupts (including the timer interrupt) from invoking the operating system scheduler that preempting the job during the critical section. Without this preemption possibility on a uniprocessor, the process will execute the critical section to completion before another job will be able to get the CPU and enter the critical section.
Part D
On a multiprocessor, preventing context switches on one processor doesn't prevent a thread running on another processor from entering the critical section.
Part E
Disabling interrupt in conjunction with locks not only prevents preemption of the thread it insures that interrupt handlers of any sort will not be run. This can be important if the interrupt handlers use spin locks as well. If you don't disable interrupts and take an interrupt with a spin lock held and that interrupt tries to acquire the same spin lock, you deadlock. The main observation is you need to synchronize with the interrupt handler both on an uniprocessor as well as a multiprocessor.p>
On the first call, we have to do three main things:
(1) Map the dll into our process.s address space, by telling the VM system to place X.dll in our address space starting at memory address Y.
(2) Patch up the calls into the dll. In our code where we call
function Z in X.dll, we replace that information
(3) Page fault the code into physical memory, if it was out on disk.
Once we've done these on the first call, we do not have to do them again
for later calls.
Part B
As a general rule, the more information we have about how a program is
going to run, the more optimization we can perform of that program.s code.
The advantage of run-time code generation is that we have much more
information about the situation in which we.re going to run the program at
run-time than we would at compile-time. This makes possible a set of
techniques collectively referred to as run-time optimizations.
Numerous problems can result from allowing a user access to kernel memory: security violations, kernel crashes, incorrect kernel behavior, etc. (Any such problems were considered a correct representation of this larger problem.)
(2) Since the OS is now directly accessing arguments and kernel data structures using the machine's translation hardware (instead of doing explicit software translation of every pointer), it is possible for the kernel to page fault in a system call or other kernel routine. This adds significant complexity to kernel procedures: for example, it is now possible to page fault in the page-fault handler, which introduces significant synchronization complexities. If user-space addresses are accessed in the fault handler after it has taken any kind of lock, a page fault can easily cause deadlock. Any answer pointing out that the kernel can now page fault in places where it can't when it's doing explicit software translation was accepted.
(3) We also accepted answers that indicated that the kernel might now occupy a portion of the address space that user processes might expect to be able to access, thus reducing the effective user address space.
Some people weren't totally clear on what's happening here, so we'll try to explain in a little more detail... in this new system, the OS does not use a segment table to translate addresses (i.e. there is no segment table at all). Memory addresses are translated using the page table, and the OS just sets up the page table so that a user process that thinks it's accessing memory through a segment table can run just fine.
For example, how does a user process say that it wants to access the data that's 4 bytes away from the start of segment 2? It simply generates a read with the following address :
10 000000000000000000000000000100
...I write this in binary to make it clear how the user shows that he's accessing "segment 2"; he simply sets the top two bits to "10". And he puts the "segment offset" in the other 30 bits.
The OS now has an address that it can look up in the page table just the way we're used to thinking about page tables; there's no segmentation to think about at all. It uses the top 20 bits to index into the page table; here those bits are :
10 000000000000000000
...or hex 80000. Thus the translation for this page would be found at entry 0x80000. The remaining 12 bits would specify the page offset (0x4 in this case).
Hopefully that's a clear explanation of how this system translates addresses to emulate segmentation... now what does the page table for the given segment table look like?
Page | Valid | Protection | Physical Page |
0 → 0x800 - 1 | yes | read-only | |
0x800 → 218 - 1 | no | ||
218 → 218 + 0x800 - 1 | yes | r/w | |
218 + 0x800 → 3 * 218 | no | ||
3 * 218 → 3 * 218 + 0x1000 - 1 | yes | r/w/sup only | |
everything else | no |
Part B
This paging system requires a significant amount of memory (to store a flat page table for each process).
Generally, the answer here is that there will be more read that write requests (1). This is because in a steady state, any page which is paged out will usually be paged back in again (because the process is still running, and so will need that page to be re-loaded). Thus, every time we evict a page, we are incurring a future read when we have to bring the page in. However, only some fraction of those pages which we evict has to be written out, since we only write out dirty pages (and we know that, at the very least, the code pages will never be dirty). Therefore, we will have more reads than writes.
Note that the other answers to the question were accepted, provided the reasoning was very sound about the workload characteristics which would give you as many or more writes as reads.
Part B
Yes, we can solve the thrashing problem by adding infinite memory to the computer. With infinite memory, we will never have to evict a page from memory, so the only time a page has to be read is when it is lazy-loaded into memory. Further, with an infinite memory we can set our file cache equal to the size of the disk, and so even that page fault will just entail moving the data from the file cache into the process's VM space.