Homework 4

22C:116, Spring 1995

Due Friday Feb. 17, 1995, in class

1. Background: Typically, the optimal disk sector size is determined by two variables, the time taken to read a sector (the average head positioning and rotational latency, plus the transfer time and any other delays) and the time taken to process one sector's worth of data Ideally, these two times should balance. If the CPU is too fast, it will be poorly utilized by spending too much time waiting for data from disk. If the disk is too fast, it will be underutilized.

   Note that the time taken to process a sector's worth of data depends on the sector size, the CPU speed, and the amount of computation needed to produce or consume one byte of data. The latter obviously varies from applicaton to application, but an average value can be measured empirically, and all the other variables on which the optimal sector size depends are static functions of the hardware.

   The problem: Develop a formula for the optimal sector size. In doing this, ignore such practical considerations as the desire to have the sector size a power of two.

2. Typically, once the disk sector size has been determined, the page size used for virtual memory must be a multiple of the sector size. In the absence of such considerations, what variables must be considered in determining the optimal page size and how do these affect the page size.

3. Background: Consider a sequential terminal which presents a memory-mapped interface to the operating system, as follows:
   • DATAIN -- the most recent character received from the terminal keyboard. This is changed by hardware every time a new key is pressed.

   • DATAOUT -- The character most recently transmitted to the display. Assigning a value to this location causes the transmission of one character to begin.

   • INREADY -- Set to one by the arrival of a character from the keyboard; the software may set this to zero, as needed.

   • OUTREADY -- Set to one by the completion of the transmission of one character to the display; the software may set this to zero, as needed.

   In addition, this terminal requests an interrupt whenever INREADY or OUTREADY are equal to one. A single interrupt service routine is used for both input and output, and interrupts are globally disabled whenever this routine is running.

   Furthermore, the operating system already includes support for a datatype called CHQUEUE, and there are two routines, ENCHQ and DECHQ available for enqueueing and dequeuing characters from a CHQUEUE object. The function TSTCHQ returns FULL, EMPTY, or OK to inform the caller of the state fo a CHQUEUE object.

   The problem: Write detailed pseudocode for an interrupt handler for this device that puts input data on a CHQUEUE called INQUEUE and takes output for this device from a CHQUEUE called OUTQUEUE. Input should be discarded when INQUEUE is full. Null characters should be output if OUTQUEUE ever becomes empty.

4. The above problem specification left little alternative but to output Null characters when there was no data available to output. How could your solution be changed to allow output to simply cease when no output was available. More importantly, what aspects of the above background statement make such a change to your solution infeasable?