Final Exam

22C:50 Section 2, Fall 2000

Name: ________________________________________________

ID Number: ___________________

E-mail Address: __________________________________
Final grades will be E-mailed to this address

Please write your answers in the space provided! Make sure your name is in the same form as it appears on your University ID card! Illegible and excessively long answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam is worth 1/5 of the final grade (20 points; allocate 6 minutes per point).

A problem: Hand assemble the following two EAL source files. For those lines of code that cause data to be stored in memory, and only for those, show the memory address, the value stored, and for each, whether it is (A) or relocatable (R). Indicate this in the blank labeled reloc following the corresponding address or value. To the right of the vertical line, put the result of relocating, linking and loading the object files from these two source files at memory address 0. (3 points)

line     hexadecimal          source        |
     loc  reloc  val reloc    text          |
                                            |  result of
 1  ______ ___ ______ ___         B    22   |  relocation,
                                            |  linking and
 2  ______ ___ ______ ___    X:   B    #22  |  loading at
                                            |  address 0
 3  ______ ___ ______ ___         B    Z    |
                                            |   loc    val
 4  ______ ___ ______ ___         B    Y    |
                                            |  ______ ______
 5  ______ ___ ______ ___         INT  X    |
                                            |  ______ ______
 6  ______ ___ ______ ___         EXT  Y    |
                                            |  ______ ______
 7  ______ ___ ______ ___         EXT  Z    |
                                            |  ______ ______
                                            |
line     hexadecimal          source        |  ______ ______
     loc  reloc  val reloc    text          |
                                            |  ______ ______
 1  ______ ___ ______ ___         B    X    |
                                            |  ______ ______
 2  ______ ___ ______ ___    Y    =    10   |
                                            |
 3  ______ ___ ______ ___    Z:             |
                                            |
 4  ______ ___ ______ ___         EXT  X    |
                                            |
 5  ______ ___ ______ ___         INT  Y    |
                                            |
 6  ______ ___ ______ ___         INT  Z    |

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? (1.5 points)
```
_____________________________________________________________

_____________________________________________________________
```
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? (1.5 points)
```
_____________________________________________________________
```
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? (1.5 points)
```
_____________________________________________________________

_____________________________________________________________
```
Problem D: Your boss says to use LRU replacement in the page fault handler. Why would this be a mistake. (1.5 points)
```
_____________________________________________________________

_____________________________________________________________
```
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. One problem they face is storage for all the images found in web pages. Some images are only a few pixels, for example 16x16 bullets take only 256 bytes, but others are huge, such as the occasional 1024x1024 image, requiring a full megabyte. The decision has already 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. (1.5 points)
```
_____________________________________________________________

_____________________________________________________________
```
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? (1.5 points)
```
_____________________________________________________________

_____________________________________________________________
```
Background: The PDA design team has concluded that the best way to handle animated images appearing within web pages is to assign one process to each image, with that process charged with the job of plotting successive frames of the image, where, after plotting each frame, the process delays an amount determined by that image before plotting the next frame. The designers have concluded that few web pages contain more than 10 animated images, 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. Of course, there are no guarnatees governing remote responses over the network. The PDA screen has about 1/4 megapixels, and the basic image update software can update 1 million pixels per second.
Problem A: How long should the time-slice be for the preemptive scheduler on this PDA. (1.5 points)
```
_____________________________________________________________
```
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. (1.5 points)
```
_____________________________________________________________

_____________________________________________________________

_____________________________________________________________
```
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? (2 points)
```
_____________________________________________________________
```
Problem B: Each time the real-time clock interrupt occurs, what does it do? (3 points)
```
_____________________________________________________________

_____________________________________________________________

_____________________________________________________________

_____________________________________________________________

_____________________________________________________________
```