4.7: Exercises

Last updated
Save as PDF

Page ID: 58521

Jerome H. Saltzer & M. Frans Kaashoek
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Exercise \(\PageIndex{1}\)

1994–3–2

You are developing a storage system for a application that demands unusually high reliability, so you have decided to use a three-replica durable storage scheme. You plan to use three ordinary disk drives D1, D2, and D3, and arrange that D2 and D3 store identical mirror copies of each block stored on D1. The disk drives are of a simple design that does not report read errors. That is, they just return data, whether or not it is valid.

a) You initially construct the application so that it writes a block of data to the same sector on all three drives concurrently. After a power failure occurs during the middle of a write, you are unable to reconstruct the correct data for that sector. What is the problem?

b) Describe a modification that solves this problem.

c) One day there is a really awful power glitch that crashes all three disks in such a way that each disk corrupts one random track. Fortunately, the system wasn’t writing any data at the time. Describe a procedure for reconstructing the data and explain any cases that your procedure cannot handle.

Exercise \(\PageIndex{2}\)

1999–3–04

What assumptions does the design of the RECONCILE procedure of Section 4.5.2 make with respect to concurrent updates to different replicas of the same file?

A. It assumes that these conflicts seldom happen.

B. It assumes that these conflicts can be automatically detected.

C. It assumes that all conflicts can be automatically resolved later.

D. It assumes that these conflicts cannot happen.

Exercise \(\PageIndex{3}\)

1997–0–03

Mary uses RECONCILE to keep the files in her laptop computer coordinated with her desktop computer. However, she is getting annoyed. While she is traveling, she works on her email inbox, reading and deleting messages, and preparing replies, which go into an email outbox. When she gets home, RECONCILE always tells her that there is a conflict with the inbox and outbox on her desktop because while she was gone the system added several new messages to the desktop inbox, and it dispatched and deleted any messages that were in the desktop outbox. Her mailer implements the inbox as a single file and the outbox as a single file. Ben suggests that Mary switch to a different mailer, one that implements the inbox and outbox as two directories, and places each incoming or outgoing message in a separate file. Assuming that no one but the mail system touches Mary's desktop mailboxes in her absence, which of the following is the most accurate description of the result?

A.RECONCILE will still not be able to reconcile either the inbox or the outbox.

B. RECONCILE will be able to reconcile the inbox but not the outbox.

C. RECONCILE will be able to reconcile the outbox but not the inbox.

D. RECONCILE will be able to reconcile both the inbox and the outbox.

Exercise \(\PageIndex{4}\)

2008–3–2

Which of the following statements are true of the RECONCILE program of Section 4.5.2?

A. If RECONCILE finds that the content of one copy of a file differs from the other copy of the same file, it indicates a conflict.

B. You create a file X with content "a" in file set 1, then create a file X with content "b" in file set 2. You then delete X from host 1, and run RECONCILE to synchronize the two file sets. After RECONCILE finishes you’ll see a file X with content "b" in file set 1.

C. If you accidentally reset RECONCILE's variable named last_reconcile_time to midnight, January 1, 1900, you are likely to need to resolve many more conflicts when you next run RECONCILE than if you had preserved that variable.

Exercise \(\PageIndex{4}\)

Here is a proposed invariant for a file reconciler such as the program RECONCILE of Section 4.5.2: At every moment during a run of RECONCILE, every file has either its original contents, or its correct final contents. Which of the following statements is true about RECONCILE?

A.RECONCILE does not attempt to maintain this invariant.

B. RECONCILE maintains this invariant in all cases.

C. RECONCILE uses file creation time to determine the most recent version of a file.

D. If the two file sets are on different computers connected by a network, RECONCILE would have to send the content of one version of each file over the network to the other computer for comparison.