Midterm II

Part of materials for 22C:50, Spring 2003
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Name: ________________________________________________

ID Number: ___________________

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/10 of the final grade (10 points; allocate 4-5 minutes per point).

A problem: Hand assemble, link, relocate and load the following bits of EAL code, showing only the values that are eventually loaded into memory. Assume that the initial relocation base for linking and loading is 10₁₆. Give all addresses and values in hexadecimal. (2 points)
```
				Location     Value
	; File A
	    EXT X		________   __________
	    INT Y
	Y   =   5		________   __________
	    B   0
	    B   X		________   __________
	    B   Y
				________   __________
	; File B
	    INT X		________   __________
	    EXT Y
	X:  B   1		________   __________
	    B   X
	    B   Y+1		________   __________
```
For a bit more credit, circle the values that were relocated as they were loaded into memory. (0.5 points)
Background: The fictional On-a-Shoestring Software Corp offers a new operating system called OASOS, featuring a marginally novel file system structure. This file system is just like Unix, except:
- I-nodes are one sector in size (4K bytes, or 1K 32-bit words).
- linearized sector numbers are 32-bit quantities.
- The first 8 words (32 bytes) of an i-node hold administrative data including the file size.
- For small files, the remaining bytes of the i-node hold the file itself.
- For larger files, the remaining words of the i-node hold the 32-bit disk addresses of the sectors of the file.
- For extraordinarily large files, the i-node holds the disk addresses of index sectors holding addresses of data sectors.
For parts b and c you may use round numbers (say "about 1000" instead of "exactly 1024"). (1.5 points)
a) How big is the largest small file? __________
b) How big is the largest "larger file"? __________
c) How big is the largest "extraordinarily large file"? __________
Background: Consider the OASOS file system is being used on a web server, and a client requests the following file:
```
/space/jones/.public-html/syssoft/index.html
```
Assume that opening a file reads just that file's OASOS-style i-node into main memory; also assume that the i-node for the root directory of the file system is always in RAM once the system is started and that none of the directories are larger than a few kilobytes. (1.8 points)
a) How many low-level files would the directory manager need to read in order to open this file?

____________
b) How many i-nodes would be read by the directory manager as it opens this file?

____________
c) How many disk read operations would be required in order to read the first byte of this file?

____________
Background: Consider a disk with 12 sectors per track, 8 cylinders, and 1 surface. Sectors are numbered from 1 to 12 (like on a clock) and the disk spins counterclockwise so the sectors pass the head in ascending order. In the time it takes to move the disk heads from cylinder a to cylinder b, |a-b| sectors spin past the head.
A problem: How long will it take to read the following sequence of disk addresses, from the start of data transfer for the first read to the end of data transfer for the last. Measure all times in units of 1/12 revolution, assuming that the read of sector 0 cylinder 0 begins at time 0 and ends at time 1. (1 point)
```
  transfer number    cyl sect   begin time   end time

         1            0   0         0           1  

         2            1   2       _____       _____

         3            3   4       _____       _____

         4            7   8       _____       _____

         5            0   3       _____       _____
```
Background: Consider the following little Unix shell script:
```
	#
	set count = $1
	set answer = 1
	while ( $count > 0 )
		@ count --
		@ answer = $answer + $answer
	end
	echo $answer
```
Most of the lines of the above script are directly executed by code in the shell, while others may be executed by loading and running programs. (1 point)
a) What is the output for an input of 4? _________________
b) What commands in the script involve loading and running programs?
__________________________________________________
Background: A serial keyboard for a typical modern computer has about 101 keys, each with a distinct keycode from 0 to 101. There is a tiny little microprocessor in the keyboard itself that sends a data packet to the host computer whenever a key is pressed and another data packet whenever a key is released -- so the computer gets two packets per keypress! These packets could be formatted as follows:
```
	 _______________
	|_|_____________| Data from keyboard
	|p|   keycode   |
```
- p -- 0 indicates key released, 1 indicates key pressed
- keycode -- 7 bits indicating what key was pressed or released
Note that shift is just a normal key from this perspective, and pressing and releasing a letter key sends the identical same two packets of data whether or not the shift key is being held down at the time. Furthermore, the keycodes are not related to the standard ISO/ASCII code, they just indicate the row (3 bits) and column (4 bits) of the key that was pressed.
If we want the keyboard input queue to contain ISO/ASCII codes, the input interrupt driver could translate row/column codes to ISO/ASCII before it enqueues anything. (2.2 points)
a) First, suggest a mechanism appropriate for handling the basic translation, ignoring problems raised by the shift, control, alt and similar keys.
```
 ______________________________________________________________________

 ______________________________________________________________________

 ______________________________________________________________________

 ______________________________________________________________________
```
b) Second, suggest how you would extend this to handle the shift key; it should be possible to generalize on this to handle control, alt and the others, but you don't need to give detail for these.
```
 ______________________________________________________________________

 ______________________________________________________________________

 ______________________________________________________________________

 ______________________________________________________________________
```