CSCI P415/515 | Fri Jan 6 15:18:04 EST 2012 [SDJ] |
If a protocol fails to satisfy a property, analyze failure scenarios and clearly explain why. Statements like, "Version 2 isn't safe," are not adequate.
Clarity counts. you may (but are not required to) use sequence diagrams, vw screenshots, or other means to help clarify your explanations. Consult man vw learn how to manage trace information.
In each version, the statements NONCRITICAL and CRITICAL represent arbitrary regions code. A process in its NONCRITICAL region runs for an indefinite, possibly infinite, period of time. A process in its CRITICAL region runs for an indefinite, but finite, period of time. The portion of the protocol just before the CRITICAL region is often called the entry protool; and the portion just after the exit protocol.
Version 1. According to Deitel, this version is safe but not live in the most general sense, because processes are forced to alternate. That is, they are not independent.
bool turn; /* unspecified no initial value in {0, 1}. */ procedure p[i] /* i: {0, 1} */ { while (1) do { NONCRITCIAL; while (turn == (-i)) do {/* nothing */}; CRITICAL; turn = (-i); } }
Version 2. According to Deitel, this version is not safe.
bool T[2] = {0, 0}; /* Who's trying */ procedure p[i] /* i: {0, 1} */ { while (1) do { NONCRITCIAL; while T[-i] do {/* nothing */;} T[i] = 1; CRITICAL; T[i] = 0; } }
Version 3. I leave it to you to figure out what the problem is with this version.
bool T[2] = {0, 0}; /* Who's trying */ procedure p[i] /* i: {1, 0} */ { while (1) do { NONCRITICAL; T[i] = 1; while T[-i] do {/* nothing */;} CRITICAL; T[i] = 0; } }
Version 4. This example is interesting because it is close to a basic protocol used in hardware and communications (Ethernet, for example). Even though it is not correct in a absolute sense, it is "statistically valid." Be sure to explain in your report how you model RANDOM_DELAY, the idea that the process pauses for an a while.
bool T[2] = {0, 0}; /* Who's trying */ procedure p[i] /* i: {1, 0} */ { while (1) do { NONCRITICAL; T[i] = 1; while T[-i] do { T[i] = 0; RANDOM_DELAY; T[i] = 1; } CRITICAL T[i] = 0; } }
Version 5 (Dekker's algorithm) Deitel claims this protocol, published by E. Dijkstra who attributes it to Dekker, is a solution to two-process mutual exclusion.
bool turn; /* turn: {0, 1} */ bool T[2] = {0, 0}; /* Who's trying */ procedure p[i] /* i: {1, 0} */ { while (1) do { NONCRITICAL; T[i] = 1; while T[-i] do { if (turn = (-i)) then { T[i] = 0; while (turn = (-i)) do {/* nothing */}; T[i] = 1; } } CRITICAL; turn = (-i); T[i] = 0; } }
Version 6 (Peterson's algorithm). Deitel claims this protocol, due to G. L. Peterson, is a simpler solution.
bool turn; /* turn: {0, 1} */ bool T[2] = {0, 0}; /* Who's trying */ procedure p[i] /* i: {1, 0} */ { while (1) do { NONCRITICAL; T[i] = 1; turn = -i; while (T[-i] && turn = (-i)) do {/* nothing */;} CRITICAL; T[i] = 0; } }
Notes