Final Exam Solutions and Comments

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

Grade Distributions

Overall

Mean   = 68.08           X
Median = 68.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___
      50. . . . 60. . . . 70. . . . 80. . . . 90

Total of all 3 Exams

Mean   = 20.86           X
Median = 20.2        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_______
      10. . . . 15. . . . 20. . . . 25. . . . 30. . . . 35

Final Exam

Mean   = 10.08                         X
Median =  9.7                  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

The Exam, with Solutions

A typical programming language implementation includes a heap manager for objects allocated by the application program. A typical Unix-like operating system includes a heap manager used to allocate system objects. Opening a new input file and binding it to an input stream in a language such as C or Java causes a block of memory to be allocated on each of these heaps. Each of the following data items is associated with the open stream-file and must be stored in either the system block (S) or the user block (U). For each, identify where it is most likely to be put (2 points):
a) ____S_____ The identity of the device on which the file is stored.
b) ____U_____ The buffer from which successive characters are unpacked.
c) ____U_____ The current position in the buffer mentioned in part b.
d) ____S_____ The mapping from sector-in-file to sector-on-device.
e) ____U_____ Information about the encoding of end-of-line for this file (eg: DOS or Unix).
f) ____S_____ The sector number of the next buffer to read from the file.
g) ____U_____ The open file number.

Only 2 had perfect scores above. Almost everyone got part d; the median score for the question was 1.4 points. Around 10 students missed parts a, b, c and e, while 13 students missed parts f and g.
Consider the question of structuring the free list of a boundary-tag heap manager. We could use a doubly linked list (each free block has pointers to the next and the previous free block) or a singly linked list. For each of the following variant boundary tag algorithms, indicate whether the free list must be doubly linked (D) or whether it can be singly linked (S) (2 points):
a) ____S_____ Merger of free blocks is as lazy as possible; being deferred until no free blocks are available that would satisfy the current request.
b) ____D_____ Very eager merger of free blocks; merger happens as the block is deallocated if it happens to be adjacent to another free block.
c) ____D_____ Moderately lazy merger of free blocks; merger happens whenever a scan of the free-list during the allocate operation finds a free-block adjacent to another free block.
d) ____S_____ Deallocated blocks are always placed at the head of the free-list.
e) ____S_____ The free list is circular, and the starting point of each search is the block after wherever the previous search ended.
f) ____S_____ The free list is maintained in sorted order, by block size, with all searches starting from the smallest free block.
g) ____D_____ The free list is circular, searches for a big enough free block move clockwise around the list, while the starting point of each search moves one step counterclockwise from the previous search.

Only 3 had perfect scores here, but the median for the question was 1.7 points. Part Cwas particularly hard, 22 missed this. Only 2 students missed parts b and g. Parts a, d and e were missed by around 5 students, while part f was missed by around 10.
Consider the following two models for device service: The traditional model, in which the interrupt service routine is large and does half the work of the device driver (the other half being done by interface routines called by users), and the process-model, in which the interrupt service routine is trivial: it simply calls signal on a semaphore. The work that would have been done by a traditional interrupt service routine is now done by a process that periodically waits on the semaphore. Here is the code of the two for a byte serial input port:
```
	conventional_interrupt_service_routine:
	   save_registers;
	   temp = input_data_register;
	   byte_serial_queue.enqueue(temp);
	   if (!byte_serial_queue.full())  <-- small bug here
	      input_status_register &= ~interrupt_enable_bit;
	   restore_registers;
	   return_from_interrupt;

	process_model_interrupt_service_routine:
	   save_registers; <-- corresponding bug after this line
	   byte_serial_semaphore.signal();
	   restore_registers;
	   return_from_interrupt;
```
a) Give the code, under the process_model, for the proces that does the rest of the work done by the conventional interrupt service routine (2 points).
```
	process_model_interrupt_service_process:
	   loop {
	      byte_serial_semaphore.wait();
	      _ temp = interrupt_data_register; ______________
	      _ byte_serial_queue.enqueue( temp ); ___________
	      _ if (! byte_serial_queue.full() ) _____________
	      ____ input_status_register |= interrupt_enable_bit;
	   }
```
10 did well here, while 2 left it blank and 4 earned no credit. The number who had difficulty was a bit dismaying, since the code needed could be determined by "subtracting" the code that was included in the process model interrupt service routine from the given code for the conventional model. (there is a small bug in the enable/disable interrupt code in the exam, as written; some students found this bug, but generally, there was no penalty for failing to account properly for it.)

b) Aside from a bit of added complexity and a bit of scheduling overhead, why might the process model for interrupt service fail? Hint: Consider the assumptions you have to make in order to make it work (1 point).
```
      _ You need to assume that the scheduler gives sufficient _____
      _ priority to the interrupt service process. _________________
```
Only 3 students gave essentially this answer; 8 more gave trivial answers or made strawman arguments for half credit. No credit was given for answers that listed parallel programming problems such as deadlock or critical sections that are in no serious way different between these two solutions.

c) Assuming the problem(s) identified above are solved, what is the potential major advantage of using the process model for interrupt service? Hint: Consider more complex interrupt service routines, for example, a disk interrupt service routine with disk scheduling (1 point).
```
      _ The interrupt service routine can take time, it can even ___
      _ block awaiting other processes, and it can be interrupted. _
```
9 gave one of the answers above, and 4 earned half credit for interesting but secondary observations. No credit was given for answers that were as applicable to one model for interrupt handling as for the other. Over 10 students made outright false assertions about the differences between these models (for example, that the process model is faster).

d) Here, we have assumed that an interrupt service routine can evoke the signal operation on a semaphore. If this is true, is it equally realistic for an interrupt service routine to evoke the wait operation on semaphore? Briefly explain your answer (1 point).
```
      _ No.  The actual interrupt service routine can never block __

      _ because, properly speaking, it is not a process. ___________
```
8 gave this answer, 15 earned partial credit for relevant observations with wrong or only partially correct reasoning. The rest gave answers that were not creditworthy.

e) It is likely that the signal operation on a semaphore, as evoked from within an interrupt service routine, will differ from the signal operation on the same semaphore, as evoked from a regular process. Briefly explain the difference (1 point).
```
      _ Signal has critical sections; these are typically guarded __
      _ differently within an interrupt service routine. ___________
```
4 did well here, 3 more touched on this in odd ways for partial credit. The remainder gave answers that were not creditworthy.
A semaphore can be viewed as an integer with an added constraint and an unusual enforcement rule for this constraint.
a) What is the constraint? (1 point)
```
      __ S >= 0 ____________________________________________________
```
b) What is the enforcement rule? (1 point)
```
      __ block the operation (S = S - 1) ___________________________
      __ until it can be done without violating the invariant ______
```
9 got each of these parts. 9 listed odd invariants that were worth half credit or more, but partial credit was rare on part b.
Consider the problem of picking an appropriate structure for a disk request queue to support the elevator algorithm. Modern disks have a huge number of tracks per recording surface, so we decide to use a lexicographic search tree to represent the queue, using the disk address as the search key.
a) In what order should we pack the fields of the disk address in order to get the best performance from performing disk operations using a simple in-order traversal of the search tree. The fields are (T) track in cylinder, (S) sector, and (C) cylinder. Make sure you give the most significant field first, and the least significant field last (1 point).
```
      __ CTS _______________________________________________________
```
21 gave this answer; 5 gave CST for less than half credit. no credit was given for STC, TSC and TCS (a few people gave one or another of these). Nobody guessed SCT, the only remaining possibility.

b) What abstract operations on the binary search tree does the disk interrupt driver need to perform? Typical tree operations include inserting an item with a given key, finding the item with a particular key, finding the successor or predecessor of an item, deleting an item from the tree, duplicating an item in the tree, and so on (1 point).
```
      _ The interrupt service routine does succ and pred as it _____

      _ scans the tree, and delete when it finishes each request. __
```
13 gave sudd, only 8 gave pred, and 14 gave delete. 11 said insert; this is done by the user side of the code, not by the interrupt service routine. 10 said lookup; this is never needed unless the disk queue is used to cache pending requests, and then it is certainly not done by the interrupt service code. 2 said copy, an operation that seems irrelevant, and 8 left this blank!

c) If a user writes code that guarantees that there will always be at least one disk request enqueued for some cylinder, some naive versions of the elevator algorithm will lock up, preventing the heads from moving to service requests for input or output to other cylinders. If you construct the search-tree-based disk scheduler described here, does this suffer from this defect? Explain why or why not (2 points).
```
      _ In fact, with the details given, the answer is unclear! ____
      _ It depends on whether the next item to process is found ____
      _ before or after I/O is scheduled, and it depends on how ____
      _ items with equal keys are inserted in the tree. ____________
```
2 did well here, 12 more earned half credit or more, and 8 more earned at least some partial credit.
Some machines have a special instruction called SLEEP that stops the system clock until the interrupt request line goes high. The advantage of stopping the clock is that the power consumption of the CPU goes to zero during this time. Assume that there are multiple user processes, and that each process may be in any of the process states ready, running, waiting or dead, what process should execute the SLEEP instruction, and when should it do so (2 points)?
```
      _ The idle process on each iteration of the idle loop. _______
```
3 gave this answer, 4 more gave vague answers that hinted at this, while 4 earned half credit by suggesting the not entirely irrelevant idea that this instruction might be called when a process dies or waits. 16 suggested either that this instructin should be called when a process dies or when a process waits, but not both; these earned even less credit. The few remaining gave irrelevant answers.
Explain why a multiprocessor with n CPUs must have n idle processes; it may help to consider under what circumstances all of them will be running, and under what circumstances none will be running (2 points).
```
      _ We need one idle process per CPU so that all CPU's have ____
      _ something to do when there is no work needing to be done ___
      _ at the moment. _____________________________________________
```
17 gave essentially this answer, and 7 more gave answers worth half credit or more. Only 2 gave answers that earned no credit.