Assignment 8, due Apr 4

Consider this sequence of operations on a pre-existing disk file:

        fd = open( ... );
        lseek( fd, pos, SEEK_SET )
        write( fd, buf, 512 )
        close( fd );

a) Describe the values of pos and buf that lead to the best case with regard to disk input/output performance. (0.5 points)

Both pos and buf should be multiples of 512.

b) Assume that pos does not conform to the constraints outlined in your answer to part a above, how many distinct read and write operations must be performed by the disk hardware? Explain them! (0.5 points)

The write operation spans two sectors. To modify just part of the file, we need to

1. read the first sector, modify the tail end of it from the buffer, and
2. write the first sector back to disk, then
3. read the second sector, modify the head end of it from the buffer, and
4. write the second sector back to disk.

So, it takes 4 distinct disk operations. If pos had been a multiple of 512, it would have taken just one operation.

c) Assume that buf does not conform to the constraints outlined in your answer to part a above, how many distinct copys must be made from the user's buffer. Explain them. (0.5 points)

If buf does not conform to the constraints outlined, the user's buffer spans two pages that are consecutive in the user's virtual address space. Unfortunately, these pages need not be physically consecutive, so the operating system must first copy the second part of the first page before copying the first part of the second page, as two separate operations. Potentially, each of these could require a page fault.

d) Combine your answers to parts b and c, describing a likely sequence of events. You may assume the system has some kind of disk cache, if that simplifies your answer. (0.5 points)

If neither the disk address nor the memory address are aligned, there will be 4 distinct disk operations on the file, possibly two page faults, and 2 or 3 distinct memory to memory copy operations:

1. read the first sector of disk.
2. possibly force a page fault on the first section of the user buffer.
3. copy the part or all of the head end of the user's buffer, which is in the tail end of the first page, into the tail end of the first disk buffer.
4. read the second sector of disk.
5. possibly force a page fault on the second section of the user buffer.
6. if the least significant 9 bits of pos and buf differ, there will be a copy operation from the middle chunk of the user's buffer. This could be from either the very tail end of the first page or the very head end of the second page, and it will be to either the very head end of the second buffer or the very tail end of the first buffer, depending on how pos and buf differ.
7. write the first sector back to disk.
8. copy the part or all of the tail end of the user's buffer, which is in the head end of second page, into the head end of the second disk buffer.
9. write the second sector back to disk.

a) How does the data structure simplify in this case. (Hint, the simplification is considerable). (0.5 points)

First, of course, the free-list pointers are completely eliminated. Second, if the search is always from the lowest block in the heap, there is never a need for back links, so each boundary tag is just one bit to indicate used or free, plus a pointer to the next tag.

b) If your computer system has virtual memory, what would the performance implications of this new heap be, as compared with the heap described in the notes. (There are implications with regard to page fault rate that are distinct from the implications with regard to CPU cycles needed per allocate, on average.) (0.5 points)

Always searching from one end would generally keep the heap compact, with large unused blocks in the heap at high addresses and only a few successively smaller free blocks at the start of the heap. In comparison, the complex algorithm given in the notes will spread blocks of all types uniformly through memory. As a result, the simplified data structure will have better locality of reference and therefore fewer page faults in a virtual memory environment.

Of course, there is an expense: Searches for new memory blocks will tend to be longer than they would be if free blocks were uniformly distributed through memory. Here, we saved page faults at the expense of increased computational cost.