Final Exam

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

Name: ______________________________________________ ID Number: ___________________

Please answer in the space provided! Your name must be legible and in the form used on your University ID card! Illegible and verbose answers will be penalized! This exam is open-book, open-notes, closed neighbor! This exam has 20 points; spend about 5 minutes per point.

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) __________ The identity of the device on which the file is stored.
b) __________ The buffer from which successive characters are unpacked.
c) __________ The current position in the buffer mentioned in part b.
d) __________ The mapping from sector-in-file to sector-on-device.
e) __________ Information about the encoding of end-of-line for this file (eg: DOS or Unix).
f) __________ The sector number of the next buffer to read from the file.
g) __________ The open file number.
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) __________ Merger of free blocks is as lazy as possible; being deferred until no free blocks are available that would satisfy the current request.
b) __________ Very eager merger of free blocks; merger happens as the block is deallocated if it happens to be adjacent to another free block.
c) __________ 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) __________ Deallocated blocks are always placed at the head of the free-list.
e) __________ The free list is circular, and the starting point of each search is the block after wherever the previous search ended.
f) __________ The free list is maintained in sorted order, by block size, with all searches starting from the smallest free block.
g) __________ 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.
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())
	      input_status_register &= ~interrupt_enable_bit;
	   restore_registers;
	   return_from_interrupt;

	process_model_interrupt_service_routine:
	   save_registers;
	   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();

	      ________________________________________________

	      ________________________________________________

	      ________________________________________________

	      ________________________________________________
	   }
```
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).
```
      ______________________________________________________________

      ______________________________________________________________
```
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).
```
      ______________________________________________________________

      ______________________________________________________________
```
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).
```
      ______________________________________________________________

      ______________________________________________________________
```
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).
```
      ______________________________________________________________

      ______________________________________________________________
```

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)

      ______________________________________________________________

b) What is the enforcement rule? (1 point)

      ______________________________________________________________

      ______________________________________________________________

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).
```
      ______________________________________________________________
```
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).
```
      ______________________________________________________________

      ______________________________________________________________
```
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).
```
      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________
```
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)?
```
      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________
```

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).

      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________

      ______________________________________________________________