CSE 221: Homework 3

Winter 2024

Due Tuesday, March 12 at 11:59pm

Answer the following questions. For questions asking for short answers, there may not necessarily be a "right" answer, although some answers may be more compelling and/or much easier to justify. I am interested in your explanation (the "why") as much as the answer itself. Also, do not use shorthand: write your answers using complete sentences.

1. (18 pts) We have read several papers that discuss CPU scheduling and networking, including Arachne, Demikernel, and Snap. Answer the two questions below in the context of each of the three systems:
   1. Work conservation. Is the system work conserving? If not, describe a situation in which it is not work conserving.
   2. Receive livelock. Can the system suffer from receive livelock? Explain briefly.

2. (32 pts) A reliability-induced synchronous write is a synchronous write that is issued by the file system to ensure that the file system's state (as represented by the system's metadata) is not left inconsistent if the system crashes at an inconvenient time.

   1. Let f be a new file created in a directory d. The file system will issue at least three disk operations to complete this operation. Ignoring any data blocks allocated for the directory or new file, what are these three disk operations for?
   2. In Unix FFS, at least two of these writes will be issued synchronously. Which are they, and what order should they be performed in? Briefly explain why.
   3. Consider the Soft Updates solution to this problem. Does it do any reliability-induced synchronous writes? If so, how does it differ from FFS? If not, why can it avoid doing so? Explain.
   4. Consider the same operation in LFS. Does LFS generate any reliability-induced synchronous writes? Explain.
   5. Consider the same operation with SplitFS. Are reliability-induced synchronous writes an issue with SplitFS? Explain. (Hint: See Section 2.1 in the Soft Updates paper.)