CS代写｜CS167 Homework Assignment 3

[All questions have fairly short answers.]

a.[4%] Suppose each block pointer, in addition to containing a checksum, also contains the time at which the block was created, known as the block’s creation time (note that blocks are never modified in place, thus the creation time for a particular file-system block on disk doesn’t change). Explain how this information can be used to determine that a block was created after a particular snapshot. (Hint: might timestamps be associated with snapshots as well?)

b.[8%] Suppose a block is freed from the current file system (but might still be referenced by a snapshot). Explain how it can be determined whether there exists a snapshot that is referring to it.

c.[12%] When a block is freed, we can’t simply get rid of it if it is referred to by some snapshot. So, rather than get rid of it, we maintain a list of blocks we’d like to get rid of, a list we call the retired list. Thus, if a block being freed cannot be reclaimed because some snapshot is referring to it, a reference to it is appended to the file-system’s retired list. When a new snapshot is created, we create a retired list for it that’s a copy of the file system’s retired list, and then set the file-system’s retired list to empty.

Let’s assume no snapshots have ever been deleted. We say that a snapshot is responsible for the existence of a block if the block’s creation time is later than the creation time of the previous snapshot, and the block was freed before the creation time of the next snapshot (or of the file system if this is the most recent snapshot). In other words, the only reason the block cannot be reclaimed is because this snapshot exists. Are all blocks for which a snapshot is responsible listed in the next snapshot’s retired list (or in the current file system’s retired list if this is the most recent snapshot)? Explain.

d.[8%] Suppose a snapshot is deleted (it is the first one to be deleted). How can we determine which blocks to reclaim?

e.[8%] We’d like this reclamation algorithm to work for subsequent deletions of snapshots.

Part c describes an invariant: all blocks for which a snapshot is responsible appear in the next snapshot’s retired list (or in the retired list of the file system if it’s the most recent snapshot). What else must be done when a snapshot is deleted so that this invariant is maintained and the algorithm continues to work?

a.[4%] Recall that the effect of executing a fork system call is to create an exact copy of the calling process. Let’s assume that our system does nothing to optimize the making of this copy, i.e., that it does not employ copy on write and that all the pages of the parent process are copied to create the child. How long would it take to copy all relevant memory when creating the child? (Note: page tables are included in relevant memory.

They must be copied, then modified; we won’t include the cost of modifying them.)

b.[2%] Early Unix systems employed the vfork system call as an optimization of fork when the call to fork was to be followed by a call to exec. In this optimization, the child process executes in the parent’s address space (on the same stack as the parent) until it calls exec,then a new address space is created for it. How long would it take to copy all relevantmemory as part of the implementation of vfork?

c.[4%] Weenix (and other Unix-based systems) optimize fork by using copy-on-write techniques. In particular, the child process’s initial address space is virtually identical to that of the parent, but copy-on-write techniques are used to avoid copying any memory.(Note that new page tables and a new page directory are created.) How long would it take to copy all relevant memory as part of this optimized fork?

d.[4%] Continuing with this optimized version of fork, suppose our process makes a few changes to file descriptors and then calls exec. Though nothing is modified in the first read-write region of memory, a maximum of 256 bytes of memory are pushed onto the stack. In addition to the cost of storing new items to the stack, how much time is spent copying relevant memory?

e.[4%] We’d like to improve the optimization used in part c. What might we do to do so? (Hint: consider using copy on write on additional data structures, perhaps some used for address translation.) With your new optimization, how long would it take to copy all relevant memory as part of the fork implementation and then place its call to exec?

f.[2%] There’s a relatively new system call known as posix_spawn that has the effect of combining fork and exec into a single system call (it has all the arguments used by exec, as well as additional arguments indicating how file descriptors should be modified). If it were implemented optimally (with respect to the copying of the parent process’s address space), how much cheaper would it be for our process than the optimized version of fork (followed by exec) used in part d?

a.[10%] Give an example showing how the chain of shadow objects may grow arbitrarily long.

b.[10%] Describe the circumstances under which such a chain may be made shorter.

Trivia Questions