Solutions to Homework 1 (15-412, Spring 2003)

Question 1

First, something that is NOT a solution. To go this route you would need to use temporal logic, which is capable of talking about when in time predicates with changing truth-values are true. The obvious FOPL approach is insufficient, since turn is sometimes equal to 0 and sometimesequal to 1.

01. Assume pid0 and pid1 are both in the critical section.
02. pid0 in critical section (1)
03. pid1 in critical section (1)
04. want[0] = 1 (2. code)
05. want[1] = 1 (3, code)
06. !(want[1] && turn == 1) (2, code)
07. !(want[0] && turn == 0) (3, code)
08. !want[1] || !(turn == 1) (6, demorgans)
09. !want[0] || !(turn == 0) (7, demorgans)
10. turn == 1 (5, 8)
11. turn == 0 (4, 9)
12. turn == 0 && turn == 1 (10, 11)
Contradiction (10, 11)

Let both processes be in the critical section. Then we know that both while loops must have exited. Since (turn == 0 && turn == 1) is not possible, the while loop must have either exited first in process 0 or process 1.

Case 1 (loop exited first in process 0):
Then turn = 0 before turn = 1. Thus process 1 reached line 2 before process 0 reached line 2. To exit the loop, process 0 would have to execute line 2. Once it did, however, turn = 1 (and will not revert to 0, by earlier fact). If turn == 1, process 0 cannot exit the loop --> contra.

Case 2 (loop exited first in process 1):
Then turn = 1 before turn = 0. Thus process 0 reached line 2 before process 1 reached line 2. To exit the loop, process 1 would have to execute line 2. Once it did, however, turn = 0 (and will not revert to 1, by earlier fact). If turn == 0, process 1 cannot exit the loop --> contra.

Thus both processes cannot be in the critical section.

Other proofs are possible. For example, an argument can be made that, in order for both processes to be in the critical section, two stores to the same word would need to be executed in one order but observed by the processes in the reverse order. This cannot happen with the sort of memory system envisioned by the text.

Question 2

Deadlock prevention is an approach based on using pre-computed static rules to ensure/prove that no sequence of application requests can result in deadlock.

Since deadlock requires all of the four conditions, deadlock prevention requires some rule that constantly ensures one of the conditions cannot hold.

1. The game requires mutual exclusion, since two monsters cannot occupy the same space.
2. This game does not allow one monster to pre-empt another (though one could imagine an alternate world in which monsters could push each other out of the way).
3. Hold & wait is fundamental, since a monster always holds one resource (the square it is standing on) and the job of maze_request_move() is to wait for other resources.
4. Finally, probably the most-practiced deadlock prevention approach is to avoid wait cycles by imposing a total order on locks and requiring processes to acquire locks only according to that order. While it is possible to impose a total order on a two-dimensional space, the result would be that monsters would be permanently and always forbidden to make reservations in at least one direction, e.g., standing on a square and attempting to reserve a square to the left would violate the locking order, so no monster could ever plan a leftward move.

Question 3

The first thing to work out is what the resources and processes are. Most people realized that the maze squares are the resources, but there was some confusion about processes. Individual monsters are not processes--you can model them as requesting resources, but they cannot sleep. It is possible to consider each thread as a process (threads request resources and can block), but it turns out that the greatest traction is probably obtained by considering a move_combo_t to be a process.

(a)Consider maze_test(0, 2, 2, 2). The resource graph is below. w0 will be used as a shorthand to designate the process specified by the contents of the move_combo_t containing the wall-zero monsters.

The arcs marked "0" reflect the fact that the monsters are currently allocated the squares they are standing on. The arcs marked "1" are the result of maze_request_move(moves + 0, 2). In particular, the straightforward action to take is to assign (1,0) to w0m0. However, (1,1) cannot be assigned to w0m1 at present, so a request arc is created. The arcs marked "2" are the result of maze_request_move(moves + 2, 2). Once again, it is straightforward to assign (2,0) to w1m1, but (1,0) cannot be assigned to w1m0 because it has already been assigned to w0m0.

At this point there is a cycle running from w1 through (1,0), w0, (1,1), and back to w1.

Some students implemented deadlock detection for Project 2 in ways which cause this piece of code to behave differently. For example, at least one group considered threads to be the process objects in the resource graph. This is an acceptable approach.

However, some groups chose not to assign (1,0) to w0 because they could not assign (1,1) at the same time. In general, this approach invites starvation. To see this, consider a level with walls of various lengths. A long wall could easily find itself in a situation where it can never simultaneously acquire all the squares it needs, while shorter walls can move around freely for an unbounded period of time. Also, there is an argument that it is undesirable from a monster's viewpoint to be stuck indefinitely in a polling loop insize maze_request_move() when it might well prefer for the situation to proceed to a deadlock so it would be informed of the error and have an opportunity to change direction.

Some groups would have immediately returned a deadlock indication for the first call (maze_request_move(moves + 0, 2)) as soon as they observed that some requests could not be satisfied immediately. This is not (yet, maybe never!) a deadlock situation.

(b)Consider maze_test(2, 2, 0, 2). The effect will be that w1 will be allocated (1,0) and (2,0), resulting in a successful completion of maze_request_move(). However, in violation of a handout assumption, no calls to maze_move_monster() will be issued before the second maze_request_move(). Most maze libraries will not detect that there is a dependency between the two calls to maze_request_move(), so the second call will hang forever.

(c)It is easy to pick four parameter values which result in no waiting: maze_test(0, 1, 3, 1).

In terms of grading this question, the main criterion will be the degree to which you demonstrate understanding of the problem (i.e., if you made different design decisions in your maze library than we did, and those decisions are reasonable, you should not be injured as a result).

Question 4

(a)An operating system which wanted to share read-only program code among processes could choose a storage key to use for all text regions and a different storage key to use for all data and stack regions. Each process running in user mode would have the protection key set to the latter value so it could update its data and stack, but not the shared program text.

(b)Operating system kernels, like all programs, contain bugs. It is easy to imagine protecting some parts of kernel memory permanently as soon as the boot process completes (program text, interrupt vector table). Some operating systems go so far as to guard against stores through wild pointers by protecting critical data structures against casual modification: code which needs to update the data structure uses a three-step protocol:

1. Adjust either the processor privilege level or the memory protection to enable access
2. Modify data structure,
3. Re-adjust privileges to disable access.

In this example, the operating system would typically execute with protection key equal to (say) 1, and most data memory would have storage key 1, but these critical data structures would be assigned storage key 2.