With single buffering, the operating system dedicates a buffer to a process. This allows the process to work on one block while the I/O system reads another block into the buffer.

With double buffering, the operating system dedicates two buffers to a process. The process can then empty one buffer while the I/O system fills the other. This allows the process to process data as fast as the I/O system can read it in.

With a sequential file, the records are stored in order of a particular key, but searching requires going through all of the records sequentially until a match is found. In an indexed sequential file, the index contains pointers to every K records in the file. For a file with N records, searching for a record with a particular key requires searching only the N/K entries in the index, and then the K records in that section of the file. Depending on the size of K, this can be considerably less than sequentially searching through all N entries.

Answer:

Consider the disk system described in Problem 11.9 and assume the disk rotates at 360 rpm. A processor reads one sector from the disk using interrupt-driven I/O, with one interrupt per byte. If it takes 2.5 μs to process each interrupt, what percentage of time will the processor spend handling I/O (disregard seek time)? Repeat using DMA, and assume one interrupt per sector.

Answer:

If you have the disk rotating at 360 rpm, then one byte is read off the disk in:

T = b/rN = 1/(360 rpm*512 bytes/sector * 96 sectors/track)

T = 3.4 μs

If one interrupt occurs every byte, then the operating system will process an interrupt (2.5 μs), then do some work, then process another interrupt, etc. The time between interrupts is equal to the time it takes to read one byte. In other words, the disk will read one byte, then interrupt the operating system, then read another byte. The operating system will only be able to get work done if it has enough time to finish processing an interrupt before the next one occurs. In this case, the processor will spend 2.5 μs / 3.4 μs or 74% of its time handling I/O.

With DMA, there is only one interrupt for the entire sector. It takes 3.4 μs/byte * 512 bytes/sector = 1,741 μs to read the sector. Therefore the processor only spends 2.5 μs / 1741 μs = .14% of the time handling I/O.

Note: The above answer does not take into account rotational delay. If you include rotational delay, then the time to read a byte becomes very large:

T = b/rN + 1/2r = 83 ms

This means the time the processor spends processing interrupts is very small (approximately .003% in both cases).

Answer:

Consider a disk array that does not use striping. If multiple I/O requests are issued for files on different disks, then performance is the same as a striped disk array. However, the advantage of striping is that it improves the chances that multiple I/O requests will in fact be for data on different disks. Without striping, all the files from a given directory will be on the same disk, so a single user operating in a single directory will be using one disk instead of all the disks in the array. Likewise, it is likely that all user files will be on one disk, and all binaries on another, so that multiple users accessing their files will use the same disk. Disk striping is a simple, automated way for the administrator of the array to ensure that files are spread out across all the disks.

T = Ts + 1/(2r) + b/(rN)

T = .008 + (60 s/m)(1 r)/ (2*9600 r/m) + (1 MB)(1024 KB/MB)(60 s/m)/(9600 r/m)(300 KB/r)

T = .008 s + .003125 s + .021333 s

T = 32.458 ms

T = 10*(Ts + 1/(2r) + 1/(rN))

T = 10(.008 s + .003125 s + (100 KB)(60 s/m)/(9600 rpm)(300 KB/r)

T = 10(.008 s + .003125 s + .002083 s)

T = 132.083 ms

Both the indexed file organization and the hashed file are efficient for frequent access to random parts of a file. Since the file is updated infrequently, the overhead of keeping indexes is reduced.

The indexed sequential file is efficient when access is usually to the entire file in sequential order. Keeping multiple indexes adds unnecessary overhead and the hash structure is not as useful for sequential access.

The hashed file is efficient for frequent updates, and also is efficient for random access.

Yes, it is easy to recover the lost space. Keep a bit map for every block on the disk, initially set to zero. Then traverse the file system starting at the root, and mark the bit mask with a 1 for every block that is used by every file. In the end, those blocks still marked by a zero are free.

One solution is to keep a copy of the free space pointer in several different places on the disk.

The maximum file size can be found by calculating the space all the different types of block pointers can reference. First we need to calculate the number of pointers an indirect block can hold:

N = 8*1024*8/32 = 2048

Then:

Size = 12*8 + 2048*8 + 2048*2048*8 + 2048*2048*2048*8 KB = 64 TeraBytes

The maximum file system partition is essentially equal to the size of a disk. Since we use 24 bits to address the blocks on each disk, the maximum size of a disk is 128 GB.

The address given is in the 13 MB range. The 12 direct pointers cover 96K, so the address is not located there. The singly indirect pointer covers the next 16 MB of the file, so the address is in a block referenced by the singly indirect pointer. This means we will need two disk accesses, one for the indirect block and another for the block containing the data.

UDP does not use congestion control, so all it has to do is send at whatever rate it desires. If this causes packet loss due to congestion in a router (a FIFO queue overflowing), then the TCP flows will slow down. If UDP sends at a high enough rate, it can force the TCP flows to slow down enough that they get nothing.

A UDP server needs only one socket because anyone can send to it on that socket. It does not establish connections to each client. A TCP server, on the other hand, needs a socket for each client because it establishes a separate connection for each one.