CSCI-UA.0202 Spring 2015 Homework 8

Handed out Sunday, Apr 12, 2015
Due 10:00 AM, Friday, Apr 17, 2015

Homework 8

These problems should be done on your own. We're not going to be grading them strictly (we'll mainly look at whether you attempted them). But they will be reinforcing knowledge and skills, so you should totally work through them carefully.

File systems

Is it fundamentally necessary to store on disk information about the unallocated disk sectors (the bitmap, etc.)? Explain why or why not.

File systems

Consider a file system that uses a UNIX-like file system with multi-level indexing. For more reliability, the inode array is actually replicated on the disk in two different places. The intent is that if one or a group of sectors that are storing either replica of the array becomes corrupted, the system can always recover from the other replica. Discuss the effect of having this replicated data structure on performance.

File systems

Suppose you have a file system with multi-level indexing (with 14 direct pointers, 1 indirect inode, 1 doubly indirect pointer, and 1 triple indirect pointer in the inode), directories, inodes statically allocated in an array 0..MAX_INUM in a known location on disk. Also assume there is an on-disk bitmap of free inodes and free sectors. Assume that the file containing the root directory is stored in a well-known inode with inumber ROOT_INUM.

Assume each file fits in one sector. Assume each inode consumes exactly one sector.

Consider creating a new file "/foo/bar" in the existing directory "foo" and writing one sector of data to that file.

Assume no in-memory cache.

  1. List the reads and writes that must be executed to accomplish this task (and explain how each disk address is determined.)

    2. Suppose we want to ensure that these actions occur reliably (e.g., if a crash occurs, the file ends up either created and full with the bitmaps and directories updated accordingly, or not created with none of these updates having occurred). Using ordered synchronous metadata writes and FSCK (File System ChecK program --e.g., file system recovery on reboot), explain how to meet this guarantee. In particular,
  2. Write down the writes in the order they should occur.
  3. List the actions that the FSCK program must take to ensure the disk is brought to a correct state on recovery, and argue that these actions guarantee file system consistency.

  4. Suppose we want to ensure reliable updates using logging (as in a journaling file system). List the series of writes (to the disk and log) in the order they should occur. Also describe what actions (if any) must be taken on recovery after a crash.

Zero-copy I/O

In some operating systems, IO from/to disk is done directly to/from a buffer in the user process's memory. The user program does a system call specifying the address and length of the buffer (the length must be a multiple of the disk sector size).

The disk controller needs a physical memory address, not a virtual address. Your friend proposes that when the user does a write system call, the operating system should check that the user's virtual address is valid, translate it into a physical address, and pass that address and the length (also checked for validity) to the disk hardware.

This won't quite work. In no more than two sentences, what did your friend forget?

Virtual memory & File systems

Discuss the issues involved in picking a page size for a virtual memory system.
  1. Name one issue that argues for small page sizes? Name two that argue for large page sizes?
  2. How do the characteristics of disks influence the selection of a page size?

Review and synthesis

Considering all the pieces of the operating system we have discussed, describe the steps that the OS takes when performing a context switch. Assume that processes are waiting in the ready queue.

Handing in the homework

Use NYU Classes; there's an entry for this homework.

Last updated: Mon May 04 11:24:46 -0400 2015 [validate xhtml]