Midterm II Solutions and Comments

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

Midterm 2 Grade Distribution

                             X
                             X
                             X
 Median = 6.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_X_X_X_X___
  0 . 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
              D  + -  C  + -  B  + -  A  +

This grade scale should be taken as very rough, since it would be wrong to assign a grade entirely on the basis of one exam.

Midterm 1 + Midterm 2 Grade Distribution

                                   X    
 Mean   = 15.55              X     X X X
 Median = 15.8             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_X_X_X___
  0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20
                      D + - C + - B + - A +

Again, this grade scale should be taken as very rough!

Exam Solutions

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.
```
				Location     Value
	; File A
	    EXT X		__0010__   ___00_____
	    INT Y
	Y   =   5		__0011__   _(_13_)___
	    B   0
	    B   X		__0012__   ___05_____
	    B   Y
				__0013__   ___01_____
	; File B
	    INT X		__0014__   _(_13_)___
	    EXT Y
	X:  B   1		__0015__   ___06_____
	    B   X
	    B   Y+1		________   __________
```
For a bit more credit, circle (or parenthesize?) the values that were relocated as they were loaded into memory.

8 filled in the blanks as shown, 6 more made only one small errors, and 9 more made only 2 small errors. The most common error was to completely ignore the specified relocaton base! A total of 28 students made this fairly severe error. 8 used 2-byte operand values (4 hexadecimal digits), and the relocatable locations at addresses 11 and 14 caused problems for many students.
15 correctly noted that the contents of memory locations 11 and 14 were relocated, while 7 noted these two plus another. There was a small amount of credit for those who commented about location 16 being relocated, because, in a sense, Y is a relocation base for the absolute constant 1.
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").
a) How big is the largest small file? 4K-32 = 4064 bytes

24 got this. 10 gave sizes in odd units, words (not common in the real world, but not evil) and a few gave sizes in bits (this verges on evil). 10 gave answers of 992 or 3968 that resulted from taking 1K to mean 1000 instead of 1024. Computer science students should know by now that by default, when quoting memory capacity, 1K means 1024!

b) How big is the largest "larger file"? 1016 x 4096 = about 4,000,000 bytes

21 did well here, 13 earned no credit.

c) How big is the largest "extraordinarily large file"? __________

20 did well here, 19 earned no credit.
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.
a) How many low-level files would the directory manager need to read in order to open this file?

read / to find the name space
read /space/ to find the name jones
read /space/jones to find the name .public-html
read /space/jones/.public-html to find the name syssoft
read /space/jones/.public-html/syssoft to find the name index.html
39 gave the answer 5, 4 gave the answer 4 with sufficient explanation of their slightly eccentric assumptions to earn full credit.

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

The i-node for / is already in memory, but we need to read in
the i-node for /space/
the i-node for /space/jones
the i-node for /space/jones/.public-html/
the i-node for /space/jones/.public-html/syssoft/
the i-node for /space/jones/.public-html/syssoft/index.html
36 gave the answer 5 (note that it is not the same 5 as in part a). 4 had off by one errors for a minor penalty.

c) How many disk read operations would be required in order to read the first byte of this file?
Reading each i-node requires a disk read operation, and no additional reads are needed to open the file because all directories are small enough to fit entirely within the small-model file that fits entirely in the i-node. Reading the first byte could require from 0 to 2 extra reads, depending on the size of the index.html file.
2 gave answers of 5 and 3 gave answers of 6, for full credit. 20 simply added 5+5, assuming that each file and each i-node would require a separate disk read (as if directories did not fit in the i-node, as stated in the problem statement). 10 managed to add 5+5+5, with no hint of where the extra 5 came from.
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       __2__       __3__

         3            3   4       _16__       _17__

         4            7   8       _32__       _33__

         5            0   3       _51__       _52__
```
18 gave the answer given above; on the other extremen 11 had errors that were so numerous and difficult to figure out that they earned no credit.
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? __16_____________

30 gave good answers here, 9 more had either 8 or 32, for partial credit because these were off by one iteration of the loop. 3 had either 2 or 4, at least they were powers of 2, so they got a little credit.

b) What commands in the script involve loading and running programs?
__echo____________________________________________

19 gave the correct answer. 8 gave echo plus either set or while but not both for partial credit. 2 more gave echo plus set plus another for a little credit.
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.
```
 ____ascii = table[ keycode ]___that is, a translation table in an array
```
15 gave this answer, 11 gave computationally complex but functionally equivalent schemes (cascade of if-statements, symbol table, etc) for over half credit. 13 managed to ignore the translation problem while writing something that indicated that they at least understood something about input-output.

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.
```
 __if keboarddata = SHIFTPRESS then shift = 128________________________

 __else if keyboarddata = SHIFTRELEASE then shift = 0__________________

 __else enqueue( table[ keycode + shift ] )____________________________
```
Nobody gave easy to read code, but 10 gave good answers that said essentially what the code above suggests. 4 more were on the right track but vague, for a small penalty, and 12 were even harder to follow, for a larger penalty. 18 more had vague answers with errors that earned credit, but under half credit.