11.6 Consider a file system on a disk that has both logical and physical block sizes of 512 bytes. Assume that the information about each file is already in memory. For each of the three allocation strategies (contiguous, linked, and indexed), answer these questions:

a. How is the logical-to-physical address mapping accomplished in this system? (For the indexed allocation, assume that a file is always less than 512 blocks long.)

b. If we are currently at logical block 10 (the last block accessed was block 10) and want to access logical block 4, how many physical blocks must be read from the disk?

Answer: Let Z be the starting file address (block number).
a. Contiguous. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.
    i. Add X to Z to obtain the physical block number. Y is the displacement into that block.
    ii. 1
b. Linked. Divide the logical physical address by 511 with X and Y the resulting quo-tient and remainder respectively.
    i. Chase down the linked list (getting X + 1 blocks). Y + 1 is the displacement into the last physical block.
    ii. 4
c.Indexed. Divide the logical address by 512 with X and Y the resulting quotient and remainder respectively.
    i. Get the index block into memory. Physical block address is contained in the index block at location X. Y is the displacement into the desired physical block.
    ii. 2

12.1 State three advantages of placing functionality in a device controller, rather than in the kernel. State three disadvantages.

Answer: Three advantages: Bugs are less likely to cause an operating system crash Performance can be improved by utilizing dedicated hardware and hard-coded algo-rithms
The kernel is simplified by moving algorithms out of it Three disadvantages: Bugs are harder to fix - a new firmware version or new hardware is needed
Improving algorithms likewise require a hardware update rather than just kernel or de-vice driver update
Embedded algorithms could conflict with application's use of the device, causing de-creased performance.

12.2 Consider the following I/O scenarios on a single-user PC.

    a. A mouse used with a graphical user interface
    b. A tape drive on a multitasking operating system (assume no device preallocation is available)
    c. A disk drive containing user files
    d. A graphics card with direct bus connection, accessible through memory-mapped I/O

For each of these I/O scenarios, would you design the operating system to use buffering, spooling, caching, or a combination? Would you use polled I/O, or interrupt-driven I/O? Give reasons for your choices.

Answer:
    a. A mouse used with a graphical user interface Buffering may be needed to record mouse movement during times when higher-priority operations are taking place. Spooling and caching are inappropriate. Inter-rupt driven I/O is most appropriate.
    b. A tape drive on a multitasking operating system (assume no device preallocation is available)
   Buffering may be needed to manage throughput difference between the tape drive and the source or destination of the I/O, Caching can be used to hold copies of data that resides on the tape, for faster access. Spooling could be used to stage data to the device when multiple users desire to read from or write to it. Interrupt driven I/O is likely to allow the best performance.
    c. A disk drive containing user files Buffering can be used to hold data while in transit from user space to the disk, and visa versa. Caching can be used to hold disk-resident data for improved perfor-mance. Spooling is not necessary because disks are shared-access devices. Interrupt-driven I/O is best for devices such as disks that transfer data at slow rates.
    d. A graphics card with direct bus connection, accessible through memory-mapped I/O
    Buffering may be needed to control multiple access and for performance (double-buffering can be used to hold the next screen image while displaying the current one). Caching and spooling are not necessary due to the fast and shared-access natures of the device. Polling and interrupts are only useful for input and for I/O completion detection, neither of which is needed for a memory-mapped device.

12.4 Describe three circumstances under which blocking I/O should be used. Describe three circumstances under which nonblocking I/O should be used. Why not just implement nonblocking I/O and have processes busy-wait until their device is ready?

Answer: Generally, blocking I/O is appropriate when the process will only be waiting for one spe-cific event. Examples include a disk, tape, or keyboard read by an application program. Non-blocking I/O is useful when I/O may come from more than one source and the order of the I/O arrival is not predetermined. Examples include network daemons listening to more than one network socket, window managers that accept mouse movement as well as keyboard input, and I/O-management programs, such as a copy command that copies data between I/O devices. In the last case, the program could optimize its performance by buffering the input and output and using non-blocking I/O to keep both devices fully occupied.

Non-blocking I/O is more complicated for programmers, because of the asynchonous rendezvous that is needed when an I/O occurs. Also, busy waiting is less efficient than interrupt-driven I/O so the overall system performance would decrease.