This homework assignment is due Friday, February 28th at 23:59:59. As we intend to make solutions available on the web site immediately thereafter, please turn your solutions in on time.
Homework must be submitted in either PostScript or PDF format (not:
Microsoft Word, Word Perfect, Apple Works, LaTeX, XyWriter, WordStar,
etc.). Submit your answers by placing them in the appropriate
hand-in directory, i.e.,
/afs/cs.cmu.edu/academic/class/15412-s03-users/$USER/hw1 (by now
you know the drill).
As usual, you may discuss this assignment with others, but you must then go off by yourself to write up the solution. However, for your own benefit I would suggest that Question 4 will probably be most useful to you if you do it by yourself.
Slide 15 of Lecture 8 (January 29, "Synchronization 1") presents a proof sketch of the mutual exclusion property for the textbook's "Algorithm 3" solution to the critical-section problem (section 7.2.1.3, pp. 194-195). The slide is particularly sketchy toward the end. Turn the proof sketch I provided into a proof of the mutual exclusion property.
Do not worry about the progress or bounded-waiting requirements.
Don't be paranoid about the exact form of your proof, but seek to demonstrate that you understand why this algorithm provides mutual exclusion (assuming the old-fashioned atomic ordered memory model, NOT fancy new microprocessors with out-of-order write pipes which I discussed earlier in that lecture).
If you find yourself confused by i and j,
see the note at the beginning of 7.2.1.
Was deadlock prevention an option for Project 2? Justify your answer. You should provide either a brief paragraph explaining why or four brief paragraphs explaining why not.
Consider the following code:
/* macro designed to be simple rather than robust. */
#define CLIP(v,l,h) if (v<l) v=l; else if (v>h) v=h
int maze_test(int startA, int countA, int startB, int countB)
{
move_combo_t moves[4];
int nmoves = sizeof (moves) / sizeof (moves[0]);
int resultA, resultB, result;
maze_init();
w0m0 = maze_new_monster(WALL, 0, 0);
w0m1 = maze_new_monster(WALL, 0, 1);
w1m0 = maze_new_monster(WALL, 1, 1);
w1m1 = maze_new_monster(WALL, 2, 1);
moves[0].mon = w0m0; moves[0].dir = RIGHT;
moves[1].mon = w0m1; moves[1].dir = RIGHT;
moves[2].mon = w1m0; moves[2].dir = UP;
moves[3].mon = w1m1; moves[3].dir = UP;
CLIP(startA, 0, 3);
CLIP(countA, 1, nmoves - startA);
CLIP(startB, 0, 3);
CLIP(countB, 1, nmoves - startB);
resultA = maze_request_move(moves + startA, countA);
resultB = maze_request_move(moves + startB, countB);
if ((resultA == ERROR_LOCK) || (resultB == ERROR_LOCK))
result = ERROR_LOCK;
else
result = 0;
maze_abort();
maze_cleanup();
return (result);
}
(Since this code violates an assumption we allowed you to rely on for Project 2, you were not required to handle code such as this.)
(a) Assume countA == 2 and countB == 2.
Give values for startA,
and startB which should cause maze_test() to return ERROR_LOCK.
Draw a resource graph which would result in ERROR_LOCK being
returned. Of course, label your nodes.
(b) Specify a tuple of values for the four maze_test() parameters which could cause maze_test() to sleep forever if maze_request_move() relied on the assumption alluded to above.
(c) Specify a tuple of values for the four maze_test() parameters which causes maze_test() to return 0.
[Adaptation of Exercise 9.18 in text]
In the IBM System/370, memory protection is provided through the use of keys. A key is a 4-bit quantity. Each 2 KB block of memory has a key (the storage key) associated with it. The CPU also has a key (the protection key) associated with it. A store operation is allowed only if both keys are equal, or if either is zero.
(a) Explain why an operating system might typically arrange for memory pages allocated to a single user process to have different storage keys. Provide a concrete example.
(b) Explain why an operating system kernel might be designed so most kernel code would not execute with the protection key equal to zero. Again, be concrete.