Final Exam Solutions

22C:50 Section 2, Fall 2000

Grade Distribution

Median = 7.6
Mean   = 8.6
              X   X                   X
        X     X   X X             X   X
    X   X     X   X X   X         X X X           X     X
____X___X_X_X_X___X_X_X_X___X___X_X_X_X_____X_____X___X_X_____________X__
 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.
  D D + + - - C C C + + - - - B B B B + + + - - - - A A A A A A + + + +

Solutions

A problem: Hand assemble the following two EAL source files. (3 points)

line     hexadecimal          source        |
     loc  reloc  val reloc    text          |
                                            |  result of
 1  _0000_ _R_ __16__ _A_         B    22   |  relocation,
                                            |  linking and
 2  _0001_ _R_ __22__ _A_    X:   B    #22  |  loading at
                                            |  address 0
 3  _0002_ _R_ __?___ _?_         B    Z    |
                                            |   loc    val
 4  _0003_ _R_ __?___ _?_         B    Y    |
                                            |  _0000_ __16__
 5  ______ ___ ______ ___         INT  X    |
                                            |  _0001_ __22__
 6  ______ ___ ______ ___         EXT  Y    |
                                            |  _0002_ __05__
 7  ______ ___ ______ ___         EXT  Z    |
                                            |  _0003_ __0A__
                                            |
line     hexadecimal          source        |  _0004_ __01__
     loc  reloc  val reloc    text          |
                                            |  ______ ______
 1  _0000_ _R_ __??__ _?_         B    X    |
                                            |  ______ ______
 2  ______ ___ ______ ___    Y    =    10   |
                                            |
 3  ______ ___ ______ ___    Z:             |
                                            |
 4  ______ ___ ______ ___         EXT  X    |
                                            |
 5  ______ ___ ______ ___         INT  Y    |
                                            |
 6  ______ ___ ______ ___         INT  Z    |

There were 6 perfect scores, and only 2 received no credit at all. 9 forgot to indicate whether the locations were relocatable or absolute. 22 gave premature values for the external symbols, implying that the assembler had some magic knowledge of context allowing it to know what the code would be linked with at a later date. The ultimate value of location 2 caused the most trouble, with 16 having odd answers; of these, 9 gave the value 1; these forgot to relocate the value of the label Z when they linked the two object files.

Background: A large manufacturer of PDA's is moving to integrate a web browser into their next generation product. This will have a 32-bit processor, 4 megabytes of RAM, and 100 megabytes of page-erasable flash EEPROM, plus a radio modem able to connect to the net using cellular telephone technology. Page erasable EEPROM is 10 times slower than RAM for reading or writing, and the only way to change a bit of this memory from 1 to 0 is to erase a full page of memory, 1024 bytes; changing from 0 to 1 is done by a normal write operation.
Problem A: Why is virtual memory relevant on this system, given that it has no disk?
The system has a small fast memory and a large slow memory. Virtual memory allows applications to be written as if the entire memory was large and fast.
About 10 got this; another 14 had weak but relevant answers, and about as many had answers that were simply wrong.

Problem B: An important component was not mentioned in the background statement. The appropriate question to ask the hardware designers is, is this component built-into the CPU or was it accidentally left out of the plan? What is it?
The memory management unit, or MMU.
Slightly more than half got this correct. There was little partial credit.

Problem C: Your boss says there is no need for DMA I/O, no need for I/O request queues and no need for request schedulers. What is it about the change from disk to flash EEPROM that justifies this assertion?
The statement of the problem suggests that the CPU can directly read and write the EEPROM, so instead of disk I/O, the CPU would simply copy pages from EEPROM to RAM, or flash a page of EEPROM and then copy from RAM to EEPROM.
Only 5 did well here, 6 had weak but useful answers, and another 4 had very weak answers.

Problem D: Your boss says to use LRU replacement in the page fault handler. Why would this be a mistake.
Pure LRU replacement requires expensive hardware in the MMU to record the time of last use on each page.
About 15 got this right and another 8 earned partial credit.
Background: A large manufacturer of PDA's is moving to integrate a web browser into their next generation product, with about 100 megabytes of memory. The decision has been made to store images in the web browser's heap, which is stored in the virtual address space of the browser.
Problem A: What heap management algorithm would you suggest for the prototype version of this browser? The primary criteria is reasonable performance for a reasonable amount of implementation effort.
The buddy system is the obvious choice. About 16 proposed this.
Another 7 proposed using significantly more complex heap managers or alternatives that offered much worse performance.
About 5 made vague suggestions that at least indicated that they knew what problem they were solving.
Most of the outright wrong answers suggested a failure to understand the problem (answers like FIFO, heapsort, or LRU fell in this category).

Problem B: Why might the alogorithm you selected for a prototype be inappropriate in the final production version of the software. Is there a more appropriate algorithm for the production version?
The big problem with quick-and-dirty heap managers is fragmentation; about 19 said this. A good way to reduce fragmentation would be to use something like a boundary tag algorithm; about 8 said this.
About 12 suggested that the Fibonacci buddy system would solve the fragmentation problem. It reduces it, but the simple buddy system loses 25% of the heap to fragmentation, while the Fibonacci system loses 19% to fragmentation. This is only a 5% gain, so the difference is not something to crow about.
Only about 8 received no credit on this problem.
Background: The designers have concluded that few web pages contain more than 10 animated images, with one dedicated to animating each image, and in this worst case, they want to guarantee that no user will have to wait more than 0.1 seconds between touching the screen and a local software response. The screen contains 1/4 million pixels, and can be replotted at the rate of 1 million pixels per second.
Problem A: How long should the time-slice be for the preemptive scheduler on this PDA.
0.1 sec response time / 10 processes = 0.01 seconds.
About 10 got this right. Wrong answers varied from 4000 seconds to .00000025 seconds. 7 proposed 0.1 seconds, 3 each proposed .04 and .25 seconds. Many students seem to have significant problems when they are presented with more quantitative information than is required to solve the problem!

Problem B: Your boss says you don't need preemption because the processes displaying each animated relinquish at the end of each replot. Explain to him why he is wrong.
It takes 1/4 second to update the entire screen, so if any image fills the entire screen, relinquishing at the end of a replot of the image can only guarantee a 0.25 second response time.
About 6 got this, another had the idea right, but failed to express the answer in quantitative terms, and two more dealt with the right issue but gave no support for their answer. The remainder (significantly more than half the class) earned no credit.
Background: The PDA product will use a touch screen. One process on the PDA must run 20 times a second to sense the current state of the touch screen. The real-time-clock hardware requests 1000 interrupts per second. Animated images may need periodic signals from the real time clock at rates determined by their animators, and the scheduler also needs to use the clock at the end of each timeslice.
Problem A: When a process needs a signal from the real-time clock at some future time, it enters that time, plus something else, into the real-time clock's queue and then awaits the signal. What kind of object is that something else?
A semaphore.
About 8 got this, while about 16 earned no credit. Answers worthy of partial credit included suggestions of putting the process itself in the queue or adding extraneous information beyond that required to solve the problem.

Problem B: Each time the real-time clock interrupt occurs, what does it do?
First, if this clock interrupt makrs the end of a time slice, preempt the current process in favor of a ready process. Given a 0.1 second time slice and 1000 ticks per second, this will happen one tich in 100.
Second, increment the current time and see if it exceeds the time on the head entry on the real-time-clock queue. If so, signal the semaphore in that entry (or do something to wake up the waiting process).
One student had a genuinely good answer to this entire question, and 3 more had generally good answers that were only slightly in error. 16 earned 1/3 to 1/2 credit for answers containing major errors but still clearly indicating an understanding of the kind of activity expected from a real-time clock interrupt service routine. Around 8 earned no credit.