Midterm Exam, Fall 2002

Solutions and Comments

Part of 22C:116, fall 2002
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Midterm Grade Distributions

Homework Scores

Mean   = 24.35
Medain = 27.25
                                                      X       X
____________X_______________________X_X_____X_______X_X_____X_X___
 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32

This was a larger spread of homework scores than I'm accustomed to seeing in this course, perhaps because I've been assigning programming problems more like those I would assign in an undergraduate course.

Midterm Exam

Mean   = 7.45
Medain = 7.00
    X           X           X
____X_______X_X_X___X___X___X_______________
 0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20

The range of scores was not unusual for my midterm exams in this course.

Overall

Mean   = 31.80
Medain = 32.75
                                        X       X
__X_________________________X___________X_____X_X_________X_X_________X_
 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36. 38. 40. 42. 44
                        B-                   B+ A-                   A+

The grade scale suggested above is very tentative.

The Exam with Answers and Comments

Note: This is an open-book, open-notes exam. Please write your answers in the exam booklet supplied. Leave blank lines between your answers to different questions, and leave a margin down the side of each page. Please write your name in the form it appears on your university ID card; write your name in the blank provided on the front cover. This exam is worth 20 points and has 10 parts! Allocate about 5 minutes per part.

General Background: Several problems on this exam refer to ECOS, the Excessively Complex Operating System introduced in the study questions distributed for this exam. Here are some new facts about ECOS:

ECOS uses the binary buddy system to manage the heap used to store compressed images of less recently used pages in main memory. This means that the expected loss to internal fragmentation is about 25% for a random distribution of allocation requests and the maximum internal fragment size is about 50% of the allocated block.

The page size used by ECOS is 4K bytes, and the maximum physical memory is 4 gigabytes. There are 8 bits in the page table entry reserved for access rights, status, MMU control, etc. Page table entries are 32 bits.

All new versions of the ECOS disk drivers use the cyclic elevator algorithm for disk scheduling.

ECDBMS (the Excessively Complex DataBase Management System) is a general purpose database management system. ECDBMS operates as a single-threaded application.

  1. Background: The total memory requirement for ECDBMS is 100 megabytes; the working set size for ECDBMS has been measured empirically to be 10 megabytes. On the average, the pages of ECDBMS compress to 1/3 of their raw size; Half of all pages compress by a factor of 1/2 to 1/4, while one in 4 compress to a smaller size and 1 in 4 compress to a larger size.

    A Problem: If ECDBMS is the primary application you will be running, how much RAM should you purchase? Explain your answer! (Ignore the RAM requirements of other applications or the system itself.)

    The naive answer was 40 Mb. This is 10 Mb for the working set, plus 1/3 of 90 Mb for the copies of pages not in the working set that are compressed by 1/3, on the average. A slightly better naive answer takes into account the expected loss to internal fragmentation of the buddy system, about 25% for a completely random distribution of block sizes. This requires that we add 1/4 of 1/3 of 90 Mb to the sum, giving 47.5 Mb.

    The best answer takes into account what you are given about the distribution of compressed page sizes. Start with 10 Mb for the working set; add to this 1/2 of 45 Mb for the pages that compress between 1/2 and 1/4 of their original sizes, because fragmentation causes us to treat them as if they compressed to exactly 1/2 their original size; add to this all of 22.5 Mb for the pages that don't compress to even 1/2 their old size (compression wins nothing for these), and finally, add 1/4 of 22.5 Mb for the pages that compress by a factor of 4 or more. Note that this overestimates the memory required, but that this overestimate is small! This gives a total of 61 Mb.

    1 student did well here, 3 gave naive answers, and 2 more forgot to include the working set in their computation. There were several genuinely wierd answers! 3 concluded that the system required significantly over 100 Mb (why bother using virtual memory in that case!) while one somehow got it down to 13 mb.3 mb.3 mb.

    Note that this problem was almost exactly the third part of study question 1, with only the details of the compression algorithm added for this exam.

  2. Background: When a page is compressed, the page table entry for that page is marked as invalid, and the frame number field, plus any other spare bits in the page table, are used to hold the memory address of the compressed version of the page.

    Part A: What is the smallest memory block that can be allocated to hold a compressed page. Explain.

    Given a 32-bit page table entry with 8 bits reserved for access rights and other flags, we have 24 bits left over that could be used to hold a pointer to the compressed page when a page is not in the working set. Given that the physical address is 32 bits, we can use these 24 bits as a pointer to any block of 256 bytes by setting the least significant 8 bits of the pointer to zero. Therefore, the smallest block of compressed data we can handle is 256 bytes!

    Only one did well here, while one more did well but gave a very poor explanation. Two earned a little partial credit for answers that began by recognizing relevant details and then drew incorrect conclusions, while 6 earned no credit at all.

    This problem was almost exactly the second part of study question 1, with only the details of the addressing scheme added.

    Part B: If each process has its own virtual address map, does this make it difficult to implement shared pages? Why, and why does your answer change when you segment the address map and share entire segments?

    Nobody did well here. Only two earned partial credit for poorly articulated answers that were, at least, not entirely wrong. 8 earned no credit. Therefore, this problem will be re-worked as a homework assignment and no solution is given here.

  3. Background: The internal representation of an ECOS semaphore has a count field and a list of waiting processes, each with a field indicating the amount by which they want to decrement the count. The wait operation, in a critical section, checks the count against the desired decrement. If the count can be decremented without going negative, it is decremented and the process does not block. If it cannot be decremented, the process is enqueued and blocked.

    Part A: What invariant relationship holds between the count field of the semaphore and the desired decrement fields of all the processes blocked on that semaphore.

    The invariant is: The count field of the semaphore is always less than any of the desired decrement fields of processes waiting on that semaphore. 5 gave that answer for full credit.

    Two students earned partial credit for confused answers; one invented a mysterious FIFO constraint on waiting processes, while the other spoke in terms of the sum of the desired decrements instead of the minimum desired decrement. The remainder earned no credit.

    Note that the second part of study question 2 provides background here. The implementation discussed in the background here is perhaps the simplest reasonable implementation of the ECOS semaphore primitives.

    Part B: Briefly what computations are performed by the signal operation? Focus on those that differ from the equivalent conventional semaphore where the decrement is always 1.

    The signal operation, after incrementing the counter on the semaphore, must search the ready list to see if the counter is now greater than the count required to unblock one or more processes; in contrast, with conventional semaphores, at most one process will be unblocked and no search of the waiting list is required. Note that, in the worst case under ECOS, the entire waiting list will be searched and all processes in it will be unblocked.

    2 did well here, 2 mentioned the dequeue and schedule step, but did not elaborate; they got half credit. One more earned a bit of credit for almost seeing the key issues. The remainder got nothing.

    This part of this problem built cumulatively on the previous part, with a distant relationship to the first part of study question 2.

    Part C: An ECOS programmer notices that the signal() operation is sometimes very slow and at other times very fast. On further experiments, the programmer notices that replacing signal(s,n) with n repititions of signal(s,1) seems to lead to even greater variation in speed. Why is the ECOS signal() operation subject to such variations in speed?

    Given the that the search required for the ECOS signal operation takes an amount of time that depends on the number of blocked processes and the number of them being unblocked, it is clear that the programmer is studying the delays on a semaphore that is sometimes associated with a large number of blocked processes, while at other times, it is associated with few.

    Note that the second experiment exposes the fact that this version of ECOS must be searching the entire list of blocked processes on each signal. This is what it would have to do if the list is not sorted with the least request first.

    Two did well herem, one more got half credit by noticing key parts of the problem without connecting the pieces, and two more almost saw the key issues without quite grasping them. Five got no credit.

    This part of the problem was purely dependent on the previous part, and one student with a wrong answer to the previous part got decent credit here for drawing correct conclusions from that wrong answer.

  4. Background: Recall that the the ECOS I/O operations are nonblocking, and if a process wants to await completion of an operation, it must explicitly block by waiting on the ECOS semaphore that was passed to the I/O operation. This allows a process to post multiple I/O operations before waiting for any of them to complete. The ECDBMS database manager makes extensive use of this feature.

    Part A: When ECDBMS was ported from ECOS to Unix, the performance was seriously degraded. Explain why; for full credit, you must connect issues in ECDBMS with differences in the ECOS and Unix kernel interfaces and relevant things you know about the device drivers.

    ECDBMS is single threaded; under Unix, it can, therefore, only issue one disk read request at a time (assuming that requests are sector aligned), because the Unix read operation blocks until the desired sector is read. In contrast, under ECOS, ECDBMS could issue multiple reads before blocking waiting for all of them to complete. As a result, the disk scheduler of ECOS can schedule disk requests, where the disk scheduler of Unix can only have a big effect if there are multiple processes posting I/O requests.

    Two did well here, one more had an odd focus that lost a bit of credit, but really understood the issues; the remainder earned no credit.

    The final part of the final study question, plus the homework involving nonblocking I/O under Unix, was preparation for this.

    Part B: After posting two I/O operations A and B, you want to do this() as soon as A finishes, and that() as soon as B finishes. Can you do this in ECOS? Could you do this (perhaps inefficiently) if ECOS contained a new kernel primitive wouldblock(s,n) that returns true of wait(s,n) would block? What efficiency concern does your solution raise?

    If you use multiple processes or kernel threads, you can solve this in ECOS without the new mechanism. With the mechanism, you can do it with a single thread like this:

    		read( fA, bA, nA, semA );
    		read( fB, bB, nB, semB );
    		doneA = doneB = false;
    		repeat
    		   if not wouldblock( semA, nA )
    		      this(); doneA = true;
                       endif;
    		   if not wouldblock( semB, nB )
    		      that(); doneB = true;
                       endif;
    		until doneA and doneB;
    
    The problem with this is that it uses busy waiting, so it is not very efficient.

    Two did well, although their answers were far terser than is given here. One more gave too little detail in answer to the final question about the efficiency concern. 6 gave minimal answers such as no, yes, without addressing the final part of the question; these earned half credit. One had a disorganized answer that earned even less credit.

  5. Background: One part of ECDBMS allocates a huge buffer and then issues one a single read to fill the buffer from a disk file. Under a much older version of ECOS, the software that processes this buffer was able to do most of the analysis before the read finished by waiting for a few bytes at a time, processing those bytes, and then waiting for more. After an upgrade to ECOS, the software was no longer able to scan this buffer as quickly. The disk driver and the file system developers insisted that they had provided a performance upgrade, and indeed, almost all other parts of ECDBMS and other applications performed better after these upgrades.

    Part A: What major feature must have been added to the I/O drivers of ECOS to allow this performance degradation? What evidence do you have that allows you to infer the presence of this feature?

    A disk scheduler must have been added; we know from the background information at the start of the exam that one was added, and now we see the performance impact of this. Generally, the new scheduler would improve performance, as observed, but without such a scheduler, the consecutive sectors required to complete a huge read would have been read in sequential order, and as the read of each sector finishes, the semaphore count would have been incremented by the size of a sector. With a scheduler, the sectors might be read in other orders, and therefore, under the rules of ECOS, the system may no longer be able to signal the completion of the reads as they are done.

    Three did well here. 4 had plausable wrong answers, 3 earning half credit and one earning more for an even better plausability argument. 3 earned no credit.

    The first and last parts of the final study question were strong preparation for this exam question!

    Part B: Can you determine from this information whether ECOS files are required to be stored contiguously on disk? What evidence supports this conclusion?

    If files were always stored contiguously, disk schedulers would rarely force out-of-order reading of the consecutive sectors required to fill a large buffer, so nobody would be likely to notice the performance change when a disk scheduler was added. With non-consecutive allocation of sectors, the performance benefit of reading them out of order using a good disk scheduler might be significant, leading to the symptoms observed.

    Three did well, 2 worked through the evidence but failed to draw a conclusion, earning half credit, and 5 earned no credit.