CSCI-UA.0202 Spring 2015 Homework 9

Handed out Friday, April 24, 2015
Due 10:00 AM, Friday, May 1, 2015

Homework 9

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.

NFS

The network file system (NFS) protocol provides reliability via which of the following? Justify your answer.
* at-most-once semantics
* at-least-once semantics
* two-phase commit
* transactions
The NFS authors had a goal of transparency. They wanted applications to be unable to distinguish whether a file system was (a) a remote file system served from an NFS server; or (b) a typical, local Unix file system. They did not succeed. (In fact, their goal was impossible.) State precisely one way in which application code can experience different behavior when interacting with a remote NFS file system versus a local Unix file system. Your answer should be in terms of what application code sees (rather than in terms of what a global observer sees). Furthermore, please give the reason why it was impossible to provide transparency for the use case you stated.

Transactions

In class, we saw that a key component for implementing transactions with atomicity (which we sometimes called “all-or-nothing atomicity”) was a logging protocol plus a recovery protocol. This question will ask you to adjust the logging protocol. Recall that the system assumes (a) an on-disk log and (b) separate on-disk data structures (such as a database’s tables), known as stable storage. The log protocol includes several record types, all of which include a transaction identifier:

BEGIN: indicates the start of a transaction.
CHANGE (also called UPDATE): logs a particular change that the system wishes to make to stable storage. Includes an “undo” action (which, if applied, undoes the change) and a “redo” action (which is the requested change).
OUTCOME: includes whether the result of the transaction is COMMIT or ABORT. Expresses to the recovery protocol (which reads the log) what the actual result of the transaction was.
END: indicates that the transaction is “complete”, in the sense given below.

The logging protocol enforces two invariants:

The system writes a change to stable storage only after logging the corresponding CHANGE record. (Here “logging” means “putting the log entry on disk”.)
The system writes the END record only after the transaction is fully applied to stable storage (or fully aborted in the sense that no trace of the transaction’s updates appears in stable storage).

Finally, recall that recovery after a crash is a two-pass process: the system scans backwards from the end of the log, undoing some changes, and then scans forwards, redoing some changes.

What modification or addition to the invariants above could we make so that recovery could consist of only a single undo pass?
What modification or addition to the invariants above could we make so that recovery could consist of only a single redo pass?

Two-phase Commit

Consider the following statement: "If machines were guaranteed not to crash, we would not need two-phase commit: the coordinator could, in one phase, decide whether a distributed transaction would commit, and then instruct the workers to apply their piece of the transaction."
Is the above statement true or false? Justify your answer.

In two-phase commit, suppose the coordinator fails after writing "COMMIT" to disk and sending "COMMIT" to all participating nodes but before any of the nodes receive this message. Suppose that the "COMMIT" message reaches i of the n participants and that the participants implement a protocol in which they communicate with one another when they suspect that the coordinator has failed.
What is the minimum number of participants that must receive the "COMMIT" message to allow the participants to complete the transaction without waiting for the coordinator to recover?

Virtual Memory

For the statements below, please state whether they are true Always, Sometimes, or Never. Justify each answer.

"On the x86, if a given memory reference (load or store) causes a page fault exception, then that memory reference also causes a TLB miss."
"On the x86, if a given memory reference from user mode results in a TLB miss, then the memory reference also causes a page fault."
"On the x86, if a given memory reference from kernel mode results in a TLB miss, then the memory reference also causes a page fault."
"On the x86, if a page table entry's PTE_P and PTE_U bits are set, then it is permissible for the process to load from the corresponding virtual address."
"On the x86, if a page table entry's PTE_P and PTE_U bits are set, then it is permissible for the process to store to the corresponding virtual address."

Threads & Processes

On Linux, why are threads sometimes called "lightweight processes"?

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]