3.10: Exercises

Exercise \(\PageIndex{1}\)

1995–3–2a…c

Locking up humanities: The registrar’s office is upgrading its scheduling program for limited-enrollment humanities subjects. The plan is to make it multithreaded, but there is concern that having multiple threads trying to update the database at the same time could cause trouble. The program originally had just two operations:

status ← REGISTER (subject_name)
DROP (subject_name)

where subject_name was a string such as "21W471". The REGISTER procedure checked to see if there is any space left in the subject, and if there was, it incremented the class size by one and returned the status value ZERO. If there was no space, it did not change the class size; instead it returned the status value \(-1\). (This is a primitive registration system—it just keeps counts!)

As part of the upgrade, subject_name has been changed to a two-component structure:

structure subject
    string subject_name
    lock slock

and the registrar is now wondering where to apply the locking primitives,

ACQUIRE (subject.slock)
RELEASE (subject.slock)

Here is a typical application program, which registers the caller for two humanities subjects, hx and hy :

procedure REGISTER_TWO (hx, hy)
    status ← REGISTER (hx)
    if status = 0 then
        status ← REGISTER (hy)
        if status = –1 then
            DROP (hx)
    return status;

a) The goal is that the entire procedure REGISTER_TWO should have the before-or-after property. Add calls for ACQUIRE and RELEASE to the REGISTER_TWO procedure that obey the simple locking protocol.

b) Add calls to ACQUIRE and RELEASE that obey the two-phase locking protocol, while postponing every ACQUIRE as late as possible and performing every RELEASE as early as possible.

Louis Reasoner has come up with a suggestion that he thinks could simplify the job of programmers creating application programs such as REGISTER_TWO. His idea is to revise the two programs REGISTER and DROP by having them do the ACQUIRE and RELEASE internally. That is, the procedure

procedure REGISTER (subject)
    { current code }
    return status

would become instead:

procedure REGISTER (subject)
    ACQUIRE (subject.slock)
    { current code }
    RELEASE (subject.slock)
    return status

c) As usual, Louis has misunderstood some aspect of the problem. Give a brief explanation of what is wrong with this idea.

Exercise \(\PageIndex{2}\)

2006-0-1

Ben and Alyssa are debating a fine point regarding version history transaction disciplines and would appreciate your help. Ben says that under the mark point transaction discipline, every transaction should call MARK_POINT_ANNOUNCE as soon as possible, or else the discipline won't work. Alyssa claims that everything will come out correct even if no transaction calls MARK_POINT_ANNOUNCE. Who is right?

Exercise \(\PageIndex{3}\)

Ben and Alyssa are debating another fine point about the way that the version history transaction discipline bootstraps. The version of NEW_OUTCOME_RECORD given in the text uses TICKET as well as ACQUIRE and RELEASE. Alyssa says this is overkill—it should be possible to correctly coordinate NEW_OUTCOME_RECORD using just ACQUIRE and RELEASE. Modify the pseudocode of Figure \(3.5.6\) to create a version of NEW_OUTCOME_RECORD that doesn't need the ticket primitive.

Exercise \(\PageIndex{4}\)

1997–0–02

You have been hired by Many-MIPS corporation to help design a new 32-register RISC processor that is to have six-way multiple instruction issue. Your job is to coordinate the interaction among the six arithmetic-logic units (ALUs) that will be running concurrently. Recalling the discussion of coordination, you realize that the first thing you must do is decide what constitutes "correct" coordination for a multiple-instruction-issue system.

Correct coordination for concurrent operations on a database was said to be: No matter in what order things are actually calculated, the final result is always guaranteed to be one that could have been obtained by some sequential ordering of the concurrent operations.

You have two goals: (1) maximum performance, and (2) not surprising a programmer who wrote a program expecting it to be executed on a single-instruction-issue machine.

Identify the best coordination correctness criterion for your problem.

A. Multiple instruction issue must be restricted to sequences of instructions that have non-overlapping register sets.

B. No matter in what order things are actually calculated, the final result is always guaranteed to be one that could have been obtained by some sequential ordering of the instructions that were issued in parallel.

C. No matter in what order things are actually calculated, the final result is always guaranteed to be the one that would have been obtained by the original ordering of the instructions that were issued in parallel.

D. The final result must be obtained by carrying out the operations in the order specified by the original program.

E. No matter in what order things are actually calculated, the final result is always guaranteed to be one that could have been obtained by some set of instructions carried out sequentially.

F. The six ALUs do not require any coordination.

Exercise \(\PageIndex{5}\)

1982–3–3a,b

In 1968, IBM introduced the Information Management System (IMS) and it soon became one of the most widely used database management systems in the world. In fact, IMS is still in use today. At the time of introduction IMS used a before-or-after atomicity protocol consisting of the following two rules:

• A transaction may read only data that has been written by previously committed transactions.
• A transaction must acquire a lock for every data item that it will write.

Consider the following two transactions, which, for the interleaving shown, both adhere to the protocol:

1	BEGIN (t1)	BEGIN (t2)
2	ACQUIRE (y.lock)
3	temp1 ← x
4		ACQUIRE (x.lock)
5		temp2 ← y
6		x ← temp2
7	y ← temp1
8	COMMIT (t1)
9		COMMIT (t2)

Previously committed transactions had set x ← 3 and y ← 4.

a) After both transactions complete, what are the values of x and y ? In what sense is this answer wrong?

b) In the mid-1970s, this flaw was noticed, and the before-or-after atomicity protocol was replaced with a better one, despite a lack of complaints from customers. Explain why customers may not have complained about the flaw.

Exercise \(\PageIndex{6}\)

1994–3–3

A system that attempts to make actions all-or-nothing writes the following type of records to a log maintained on non-volatile storage:

< STARTED i >	action i starts
< i, x, old, new >	action i writes the value new over the variable old for the variable x
< COMMITTED i >	action i commits
< ABORTED i >	action i aborts
< CHECKPOINT i, j >	at this checkpoint, actions i, j, ... are pending

Actions start in numerical order. A crash occurs, and the recovery procedure finds the following log records starting with the last checkpoint:

< CHECKPOINT 17, 51, 52 >
< STARTED 53 >
< STARTED 54 >
< 53, y, 5, 6 >
< 53, x, 6, 4 >
< COMMITTED 53 >
< 54, y, 6, 4 >
< STARTED 55 >
< 55, z, 3, 4 >
< ABORTED 17 >
< 51, q, 1, 9 >
< STARTED 56 >
< 55, y, 4, 3 >
< COMMITTED 54 >
< 55, y, 3, 7 >
< COMMITTED 51 >
< STARTED 57 >
< 56, x, 9, 2 >
< 56, w, 0, 1 >
< COMMITTED 56 >
< 57, u, 2, 1 >
*************** crash happened here ***************

a) Assume that the system is using a rollback recovery procedure. How much farther back in the log should the recovery procedure scan?

b) Assume that the system is using a roll-forward recovery procedure. How much farther back in the log should the recovery procedure scan?

c) Which operations mentioned in this part of the log are winners and which are losers?

d) What are the values of x and y immediately after the recovery procedure finishes? Why?

Exercise \(\PageIndex{7}\)

1994–3–4

The log of exercise \(\PageIndex{7}\) contains (perhaps ambiguous) evidence that someone didn't follow coordination rules. What is that evidence?

Exercise \(\PageIndex{8}\)

1994–3–5

Roll-forward recovery requires writing the commit (or abort) record to the log before doing any installs to cell storage. Identify the best reason for this requirement.

A. So that the recovery manager will know what to undo.

B. So that the recovery manager will know what to redo.

C. Because the log is less likely to fail than the cell storage.

D. To minimize the number of disk seeks required

Exercise \(\PageIndex{9}\)

1997–3–03

Two-phase locking within transactions ensures that

A. No deadlocks will occur.

B. Results will correspond to some serial execution of the transactions.

C. Resources will be locked for the minimum possible interval.

D. Neither gas nor liquid will escape.

E. Transactions will succeed even if one lock attempt fails.

Exercise \(\PageIndex{10}\)

1994–3–7

Pat, Diane, and Quincy are having trouble using email to schedule meetings. Pat suggests that they take inspiration from the two-phase commit protocol.

a) Which of the following protocols most closely resembles two-phase commit?

1. a. Pat requests everyone’s schedule openings.
   b. Everyone replies with a list but does not guarantee to hold all the times available.
   c. Pat inspects the lists and looks for an open time.
         If there is a time,
           Pat chooses a meeting time and sends it to everyone.
        Otherwise
           Pat sends a message canceling the meeting.
    
2. a-c, as in Protocol 1.
   d. Everyone, if they received the second message,
         acknowledge receipt.
      Otherwise
         send a message to Pat asking what happened.
    
3. a-c, as in Protocol 1.
   d. Everyone, if their calendar is still open at the chosen time
          Send Pat an acknowledgment.
       Otherwise
          Send Pat apologies.
   e. Pat collects the acknowledgments. If all are positive
          Send a message to everyone saying the meeting is ON.
       Otherwise
          Send a message to everyone saying the meeting is OFF.
   f. Everyone, if they received the ON/OFF message,
          acknowledge receipt.
       Otherwise
          send a message to Pat asking what happened.
    
4. a-f, as in Protocol 3. 
   g. Pat sends a message telling everyone that everyone has confirmed.
   h. Everyone acknowledges the confirmation.

b) For the protocol you selected, which step commits the meeting time?

Exercise \(\PageIndex{11}\)

Alyssa P. Hacker needs a transaction processing system for updating information about her collection of 97 cockroaches.\(^*\)

a) In her first design, Alyssa stores the database on disk. When a transaction commits, it simply goes to the disk and writes its changes in place over the old data. What are the major problems with Alyssa’s system?

b) In Alyssa’s second design, the only structure she keeps on disk is a log, with a reference copy of all data in volatile RAM. The log records every change made to the database, along with the transaction which the change was a part of. Commit records, also stored in the log, indicate when a transaction commits. When the system crashes and recovers, it replays the log, redoing each committed transaction, to reconstruct the reference copy in RAM. What are the disadvantages of Alyssa’s second design?

To speed things up, Alyssa makes an occasional checkpoint of her database. To checkpoint, Alyssa just writes the entire state of the database into the log. When the system crashes, she starts from the last checkpointed state, and then redoes or undoes some transactions to restore her database. Now consider the five transactions in the illustration:

Figure \(\PageIndex{1}\): Transactions T2, T3, and T5 committed before the crash, but T1 and T4 were still pending.

When the system recovers, after the checkpointed state is loaded, some transactions will need to be undone or redone using the log. For each transaction,

c) When the system recovers, after the checkpointed state is loaded, some transactions will need to be undone or redone using the log. For each transaction, mark off in the table whether that transaction needs to be undone, redone, or neither.

	Undone	Redone	Neither
T1
T2
T3
T4
T5

d) Now, assume that transactions T2 and T3 were actually nested transactions: T2 was nested in T1, and T3 was nested in T2. Again, fill in the table

	Undone	Redone	Neither
T1
T2
T3
T4
T5

---

\(^*\)Credit for developing exercise \(\PageIndex{11}\) goes to Eddie Kohler.

Exercise \(\PageIndex{12}\)

2008–3–11

Alice is acting as the coordinator for Bob and Charles in a two-phase commit protocol. Here is a log of the messages that pass among them:

1	Alice ⇒ Bob:	please do X
2	Alice ⇒ Charles:	please do Y
3	Bob ⇒ Alice:	done with X
4	Charles ⇒ Alice:	done with Y
5	Alice ⇒ Bob:	PREPARE to commit or abort
6	Alice ⇒ Charles:	PREPARE to commit or abort
7	Bob ⇒ Alice:	PREPARED
8	Charles ⇒ Alice:	PREPARED
9	Alice ⇒ Bob:	COMMIT
10	Alice ⇒ Charles:	COMMIT

At which points in this sequence is it OK for Bob to abort his part of the transaction?

A. After Bob receives message 1 but before he sends message 3.

B. After Bob sends message 3 but before he receives message 5.

C. After Bob receives message 5 but before he sends message 7.

D. After Bob sends message 7 but before he receives message 9.

E. After Bob receives message 9.