Winter 2002 Midterm Solutions |
Problem | Grader |
---|---|
1a, 1b | Sean Anderson |
1c, 2a | Huat Chye Lim |
2b | Mendel Rosenblum |
3 | Jeffrey Wang |
4 | Woojin Kim |
All midterm grade dispute e-mails must be sent by Friday, 3/8, at 11:59 p.m. to be considered.
Partial credit:
Generally, 3 points were given for poor explanations of the timer
interrupt, such as just writing, "preemption." One point was given for
not discussing timer interrupts but discussing other methods that the OS
can gain control, such as through a syscall (which requires the
misbehaving program's cooperation). No points were given if answers
totally missed point of the question, such as ones just describing
scheduling algorithms.
Partial credit:
A couple points were given for explaining the difference between global
and local replacement algorithms.
4 | If stated that PIC shared libraries can be placed anywhere in a virtual address space, thus offering an advantage over static shared libraries |
3 | If stated that PIC shared libraries can be placed anywhere in a virtual address space |
2 | If gave an explanation of PIC that explained that PIC works using PC-relative (or base-plus-offset) addressing |
1 | If gave any other explanation of PIC that was generally correct |
A number of people stated, implicitly or explicitly, that libraries that are not PIC are not shared. This is not true: statically-linked shared libraries do not use PIC, but are still shared. No points were taken off for making this statement.
Because each A thread waits on X once while each B thread signals X twice, there can be up to twice as many A as B threads passing through DoIt() at the same time. However, there cannot be more A threads than this quantity, because the number of A threads is limited by the number of signals to X (two) that each B thread makes.
Likewise, because each B thread waits on Y once while each A thread signals Y once, there can be up to as many B as A threads passing through DoIt() at the same time. There cannot be more B threads than this quantity because the number of B threads is limited by the number of signals to Y (one) that each A thread makes.
The range of valid ratios of A threads to B threads passing through DoIt() at the same time can therefore be expressed as:
Where a is the number of A threads and b is the number of B threads.
+4 | If stated that the upper bound of the A:B thread ratio is 2:1 |
+3 | If did not do the above, but did state that the upper bound of the A:B thread ratio is greater than 1 |
+1 | If correctly explained this upper bound |
+2 | If stated that the lower bound of the A:B thread ratio is 1:1 |
+1 | If correctly explained this lower bound |
If the answer did not discuss the A:B thread ratio, 0-4 points were given depending on the correctness and relevance of the statements made.
Because condition variables have no history, you need to explicitly track the number threads or semaphore value. Here's an example of a routine that tracks the semaphore values:
monitor { unsigned int semaX = 0; unsigned int semaY = 0; ConditionVariable Xwait, Ywait; void routine(threadType) { switch (threadType) { case typeA: while (semaX == 0) { Xwait->wait(); // For a signal } semaX--; // P(semaY); semaY++; Ywait->signal(); // V(semaY); break; case typeB: semaX += 2; // V(semaX); V(semaX); Xwait->signal(); Xwait->signal(); while (semaY == 0) { Ywait->wait(); } semaY--; // P(semaY); break; } DoIt(); } }
Grading gave most of the points for having some code that had integers counting and condition variables waiting and signaling in some kind of sensible way. Treating condition variables like semaphores got very few points (0 or 1).
(credit was also given for A,B: since swapping segment tables is fast)
-1 | claims that process with most tickets is *always* chosen. This is wrong, as our algorithm is a lottery and thus is somewhat randomized. |
-1 | doesn't mention that the scheduler takes away all the tickets of the currently running thread. |
-2 | incorrect algorithm, but somewhat right intuitions |
-4 | completely wrong |
-1 | does discuss time quanta/priority level pertaining to MLFQ scheduler |
-2 | wrong reasoning |
-3 | "Job A gets higher priority" and reasoning is wrong |
-1 | does not mention that Job A runs whenever Job B is blocked on I/O |
-2 | wrong reasoning |
-3 | "Job B gets more CPU time" and reasoning is wrong |
CS 140 Homepage |
cs140-staff@cs.stanford.edu
Last modified: Tue Mar 5 00:34:45 PST 2002
|