CSC256, CSC456 Midterm Exam 3/15/98
Results indicated good understanding of the material to date, but that the exam was quite long for a single class period. Despite that, there were perfect scores by both CSC256 and CSC456 students. After some analysis, I simply added full credit for one problem into each of your scores (this was more generous than dropping the lowest problem). I saw a few fairly serious misconceptions, so please make sure that you understand the solutions thoroughly, and obtain help from me during office hours if needed.
Of 12 problems, CSC456 students are to work any 10 and CSC256 students must work 8. Please clearly designate the problems you want credit for. This exam is closed book, closed notes. You may use a calculator -- but not a computer with significant memory. Please write clearly, label answers (2c etc.), and show all work. I'll try to be as unambiguous as possible in the questions; in the event that you need to make an assumption to proceed WRITE IT DOWN. In the interest of fairness, I will be highly resistant to answering questions during the exam. If you would not mind my disclosing your answer as the correct solution, please indicate so.
1. What resources are used when a thread is created? How do they differ from those used when a process is created? Describe the actions taken by the NachOS kernel to switch between a) threads, and b) processes.
Most people did fine on this. I wanted to see that a thread gets a register set, including pc and stack pointer, and memory for a stack. A process gets a full address space including code, initialized data, uninitialized data (heap), and a thread's stuff. In NachOS, switching differs only in the need to swap address space for processes (by changing the page table register or flushing the TLB if used). Steps include disable interrupts, save current thread state, place thread in ready queue (if not waiting for io), select next thread, determine if process switch is necessary and switch (optimization -- no process switch if next thread is from same process), restore its state, begin executing it.
2. Consider the following set of processes, with the length of the CPU burst time given in milliseconds:
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0.
|
Algorithm |
a) Process Order |
b) Wait Time |
Average |
||||
|
P1 |
P2 |
P3 |
P4 |
P5 |
|||
|
FCFS |
12345 |
0 |
10 |
11 |
13 |
14 |
9.6 |
|
SJF |
24351 |
9 |
0 |
2 |
1 |
4 |
3.2 |
|
42351 |
9 |
1 |
2 |
0 |
4 |
3.2 |
|
|
Non-preemptive priority |
25134 |
6 |
0 |
16 |
18 |
1 |
8.2 |
|
25314 |
8 |
0 |
6 |
18 |
1 |
6.6 |
|
|
RR |
12345 135 15 15 15 1 1 1 1 1 |
0+4+2+1+1 +1 =9 |
1 |
2+3=5 |
3 |
4+2+1+1+1=9 |
5.4 |
Clearly SJF -- some of you remembered that SJF is provably optimal for minimizing waiting time.
3. Consider a variant of the round-robin scheduling algorithm where the entries in the ready queue are pointers to process-control-blocks.
Doubling the time given that process.
Simple scheme which would provide some priority work with minimal modification to scheduler. But, overhead for managing pointers is a nuisance -- what if the process is io waiting or done? Have to remove BOTH pointers from ready queue, etc. Also may increase overhead if same process runs back-to-back -- it was not necessary to switch contexts. (Practically speaking, I'd always check to see if a context switch were necessary before doing one.)
Add a simple quantum indicator to PCB.
4. Demonstrate that monitors and semaphores are all equivalent, insofar as the same types of synchronization problems can be implemented with them.
This problem seemed to confuse many of you, and most of you stayed away from it. If I can implement semaphores using monitors and also implement monitors using semaphores, we have shown that they resolve the same class of synchronization problems.
// Semaphore using monitor
monitor {
int count;
condition waiting;
function init( initial_count ) {
count = initial_count;
}
function P() {
while (count < 0) waiting.wait();
count = count - 1;
}
function V() {
count = count + 1;
waiting.release();
}
}
// Monitor using semaphores
semaphore mutex :=1 , waiting := 0;
int count := 0;
For each invocation of a monitor function do { mutex.P(); function; mutex.V() }. For each use of a condition variable.wait() do { waiting.P(), count = count+1}. For each use of a condition variable.signal() do { waiting.V(), count = count-1}. For each use of a condition variable.broadcast() do { while( count0) { waiting.V(); count = count-1;}}
I expected rather better results on this one, since you did the second part in assignment one, and I did the first part in class. Don't be surprised if it recurs in some variant on the final.
5. Write a bounded-buffer monitor in which the buffers (of pointers) are embedded within the monitor itself.
Numerous good solutions to this.
Monitor {
Condition full, empty;
Queue q;
BbInsert( item ) {
while ( queue.isFull() ) full.wait();
q.insert(item);
empty.release();
}
item BbRemove() {
while ( queue.isEmpty() ) empty.wait();
result = q.remove();
full.release();
return result;
}
}
6. Consider the following snapshot of a system:
Yes it is safe, P0, P2, P3, P1, P4 is one of many sequences which work.
No, there are not enough C's to insure deadlock avoidance at this time.
7. Explain the difference between internal and external fragmentation. Explain the following allocation algorithms: first-fit, best-fit, worst-fit. Given discontiguous memory partitions of 100k, 500k, 200k, 300k, and 600k in order, how would each of the first-fit, best-fit, worst-fit algorithms place processes of 212k, 417k, 112k, and 426k (in order)? Which algorithm makes the most efficient use of memory?
There were a few common mistakes here -- most related to forgetting to divide the block that a process was assigned to.
|
Original block |
First-fit |
Best-fit |
Worst-fit |
|
100k |
|
|
|
|
500k |
212k / 112k |
417k |
417k |
|
200k |
|
112k |
|
|
300k |
|
212k |
|
|
600k |
417k |
426k |
212k / 112k |
|
Won't fit now |
426k |
|
426k |
Clearly Best-fit pays off in this example.
8. Consider a paging system with the page table stored in memory.
200ns page table ref + 200 ns memory ref = 400 ns
(0 ns TLB + 200ns memory ref) *.75 + (200ns page table ref + 200 ns memory ref) * .25 = 250 ns
Let p be probability of a page fault. Worst case:
200ns = ( 100 ns ) (1-p) + (p)(100ns + (20 * 106 ns * .7 + 8 * 106 ns * .3 ))
p = 1/164000 =~ .0000061 Hence, 1 page fault in 164,000 memory reference DOUBLES the effective access time of physical memory.
9. Consider the following segment table:
This was a freebie -- no one got it wrong. C and E are invalid references, the others are a) 649, b) 2310, d) 1727.
10. A certain computer provides its users with a virtual memory space of 232 bytes. The computer has 218 bytes of physical memory, and a TLB. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 1112345616. Explain how the system establishes the corresponding physical location. Distinguish between hardware and software operations.
The hardware separates the address into the page address 1112316 and offset 45616. The TLB attempts to translate the address -- if found, the TLB's page frame address is added to 456 and is the physical address. If the address was not found in the TLB, either hardware or software (the TLB trap handler) then maps the page 11123 through the page table. If valid, the TLB is updated and the original instruction is restarted. Many of you confused a TLB miss with a page fault; TLB's are usually much smaller than a page table, so TLB misses are common, even for loaded pages. If the page table indicated the entry was invalid then a page fault occurs. Software operations follow: At this point the page must be retrieved, loaded into a page frame, added to the page table, added to the TLB, and then the original instruction can be restarted.
11. Using the page reference sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 determine the number of page faults which will occur for FIFO, Optimal, and LRU page replacement algorithms. How well does LRU approximate Optimal? Why? Which of these algorithms will not exhibit Belady's anomaly? Why not?
|
|
P f |
1 |
2 |
3 |
4 |
1 |
2 |
5 |
1 |
2 |
3 |
4 |
5 |
Page faults |
|
FIFO |
A |
1 |
|
|
4 |
|
|
5 |
|
|
|
|
|
9 |
|
B |
|
2 |
|
|
1 |
|
|
. |
|
3 |
|
|
||
|
C |
|
|
3 |
|
|
2 |
|
|
. |
|
4 |
|
||
|
Opt |
A |
1 |
|
|
|
. |
|
|
. |
|
3 |
|
|
7 |
|
B |
|
2 |
|
|
|
. |
|
|
. |
|
4 |
|
||
|
C |
|
|
3 |
4 |
|
|
5 |
|
|
|
|
|
||
|
LRU |
A |
1 |
|
|
4 |
|
|
5 |
|
|
3 |
|
|
10 |
|
B |
|
2 |
|
|
1 |
|
|
. |
|
|
4 |
|
||
|
C |
|
|
3 |
|
|
2 |
|
|
. |
|
|
5 |
LRU does not approximate Opt very well in this example since there are so few page frames that seldom does a page get to be in memory long enough to be referenced twice (we're definitely thrashing here). Hence the limited time period past is not a good approximation to the unlimited time period (in the future) used by Belady's optimal algorithm. It would improve dramatically with a few more frames and a longer reference sequence, since the effective reference time window increases with number of frames.
Neither LRU nor opt will exhibit Belady's anomaly, since they are "stack" algorithms, which insure that larger numbers of page frames store a superset of the frames stored in the original case. Note that this has significant implications for the local vs. global allocation schemes.
|
|
P f |
1 |
2 |
3 |
4 |
1 |
2 |
5 |
1 |
2 |
3 |
4 |
5 |
Page faults |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
12. Consider a demand paging system with a paging disk that has an average access and transfer time of 20 ms. Addresses are translated through a page table in main memory, with an access time of 1 us per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page table entry is in the associative memory. Assume that 80 percent of the accesses are in the associative memory, and that, of the remaining, 10% (or 2% of the total) cause page faults. What is the effective access time?
Eatclean = 1us * .8 + (1us + 1us) * (.2*.9) + (20,000 us) * (.2*.1) = 401.16
Eatdirty = 1us * .8 + (1us + 1us) * (.2*.9) + (20,000 us *2) * (.2*.1) = 801.16