Dear DDJ,
In "Programming Paradigms," DDJ issue #164, entitled "Complex Systems, Fractals, and Chaos," Michael Swaine briefly discusses a problem known as the "Dining Philosophers" problem. This problem was first stated and solved by E. W. Dijkstra in "Cooperating Sequential Processes" (Technical Report EWD-123. Eindhoven, The Netherlands: Technological University, 1965). Since Dijkstra's original paper, this problem has been considered a classic process synchronization problem, not because it has practical importance, but because it is an example for a large class of concurrency control problems.
The problem may be stated as follows, derived from the description in Operating Systems Concepts by James L. Peterson and Abraham Silberschatz, (Reading, Massachusetts: Addison-Wesley, 1985). Five philosophers spend their entire lives thinking and eating. These philosophers share a circular table with five place settings. The table is set with five plates of rice, and five chopsticks. When a philosopher thinks, he does not interact with the other four philosophers. On occasion, a philosopher gets hungry and tries to pick up the chopsticks to his left and right, in either order, so that he can eat a plate of rice. A philosopher may only take one chopstick at a time, and, obviously, cannot take a chopstick that is in use by one of his neighbors. When a hungry philosopher has both of his chopsticks, he eats without releasing his chopsticks until he finishes. When finished eating, a philosopher puts both of his chopsticks back on the table and starts thinking again.
In reference to this problem, Mr. Swaine makes the following statement on page 123,
The Dining Philosophers problem, discussed here and more fully in David Harel's book, Algorithmics (Addison-Wesley, 1987), is a classic case of deadlock that cannot be resolved without introducing an element of randomness. Any strictly deterministic solution to the Dining Philosophers problem is guaranteed to fail.
Apparently, either Mr. Swaine or Mr. Harel has not done his homework thoroughly enough, as this assertion is at odds with the information to be found in the relevant literature. Since the column is not specific as to whether Mr. Harel's book makes this same assertion or not, I cannot tell whose homework did not get done.
This assertion is also at odds with the concepts taught at the university level. I received a Bachelor of Science in Information and Computer Science from the Georgia Institute of Technology in 1987. This curriculum included a senior-level operating systems course, in which each student must solve the dining philosophers problem in a manner that is both deterministic and provably free of both deadlocks and starvation. Further, each student must provide a proof of correctness with the solution. My own class implemented the solution using Logitech Modula-2 and an instructor-provided module allowing pre-emptive multitasking of multiple instances of a single procedure. The Peterson and Silberschatz book was the text for this course when I attended it, and was the genesis of our programming assignment.
Peterson and Silberschatz provide three solutions which are guaranteed to be free of deadlocks:
All of these solutions can be proven to be free of deadlocks. The correctness proofs for these three solutions are not provided in the text, because, unfortunately, none of them meets the additional criterion that starvation must be avoided. The author indicates that a deadlock- and starvation-free solution is possible but leaves the development, implementation, and proof of correctness of the solution as an exercise for the reader.
The discussion of this problem in Operating Systems: Design and Implementation by Andrew S. Tanenbaum (Englewood Cliffs, New Jersey: Prentice-Hall, 1987) casts it in a slightly different light, but differing from the characterization of Peterson and Silberschatz in details only: In Tanenbaum the philosophers are trying to eat very slippery spaghetti which requires two forks. Mr. Tanenbaum goes into more depth with his discussion of the possible solutions. The following quotation is from page 77 of Tanenbaum's book (the figures mentioned are included at the end of this letter, following the references). [Editor's Note: See Example 1 and Example 2.]
Now you might think, " If the philosophers would just wait a random [amount of] time instead of the same [amount of] time after failing to acquire the righthand fork [chopstick], the chance that everything would continue in lock step for even an hour is very small." Of course this is true, but in some applications one would prefer a solution that always works and cannot fail due to an unlikely series of random numbers. (Think about safety control in a nuclear power plant.)
One improvement to Fig. 2 - 19 [see Example 1] that has no deadlock and no starvation is to protect the five statements following the call to think by a binary [mutual exclusion] semaphore....
From a theoretical viewpoint, this solution is adequate. From a practical one, it has a performance bug [inefficiency]: Only one philosopher can be eating at any instant. With five forks [chopsticks] available we should be able to allow two philosophers to eat at the same time.
The solution presented in Fig. 2 - 20 [see Example 2] is correct and also allows the maximum parallelism for an arbitrary number of philosophers.
I find it quite disturbing that Mr. Swaine would assert that a sequencing problem of this sort can be solved with randomness. Nondeterminism can definitely solve the problem, since a non-deterministic solution can be found to any problem that can be solved deterministically. However, nondeterminism and randomness are not only different, but radically so. Chaos theory might be able to solve the problem, since chaos is deterministic but wildly fluctuating, but this is not necessary, as the problem admits of a deterministic solution anyway. True randomness, however, is completely unpredictable, so nothing can be guaranteed about the processes controlled by randomness.
I don't have the memory to exhaustively prove it without significant research, but I suspect that no sequencing problem of this type can be provably solved if randomness is involved in the solution. In a truly random situation, one can make no assumptions about the series of random numbers that will be involved. The only assumptions that can be made involve the stochastic properties of the probable sequences of the numbers
Therefore, one can reach no provable conclusions about the operational sequences bgoverned by random numbers. As mentioned above in the excerpt from Tanenbaum, an unlikely sequence of random numbers could, and probably will, eventually crop up and destroy one's assumptions, inviting or incurring disaster.
Certainly, one could design a random number generator that would be deadlock- and starvation-free by using a particular combination of computer and language, with a specified number of philosophers. However, if any part of the machine, the language (possibly even the optimization options or the language implementation), or the number of philosophers is changed, you will almost certainly have to redesign the random number generator to get a sequence that will provably not cause deadlocks. This is not what I would call a useful, provably correct, solution to the problem.
I sincerely hope that the folks out there that write nuclear reactor safety code for a living were trained from the same literature that I was, and not that used by Mr. Swaine for his information. If I find out that those folks believe, first, that no deterministic solution is possible, and, second, that an approach based on random numbers, or worse yet, pseudorandom numbers, is realizable, I shall strongly consider the prudence and efficacy of moving to some location very, very distant from the societies using nuclear power.
Douglas N. Franklin Atlanta, Georgia
#define N 5 /* number of philosophers */
#define take_fork (num) down(s[num]) /* grab fork or block */
#define put_fork (num) up (s[num]) /* release fork */
typedef int semaphore; /* semaphores are special kind
of int */
semaphore s[N]; /* one semaphore per fork */
philosopher (i) /* philosopher number, 0-4 */
int i;
{
while (TRUE) {
think (); /* philosopher is thinking */
take_fork (i); /* take left fork */
take_fork ((i+1) % N); /* take right fork, % is modulo oper
#define N 5 /* number of philosophers */
#define LEFT (i-1) %N /* number of i's left neighbor */
#define RIGHT (i+1) %N /* number of i's right neighbor */
#define THINKING 0 /* philosopher is thinking */
#define HUNGRY 1 /* philosopher is trying to get forks */
#define EATING 2 /* philosopher is eating */
typedef int semaphore; /* semaphores are special kind of int */
int state [N]; /* array to keep track of everyone's
state */
semaphore mutex = 1; /* mutual exclusion for critical regions
*/
semaphore s[N]; /* one semaphore per philosopher */
philosopher (i) /* philosopher number, 0 to N-1 */
int i;
{
while (TRUE) { /* repeat forever */
think (); /* philosopher is thinking */
take_forks (i); /* acquire two forks or block */
eat (); /* yum-yum, spaghetti */
put_forks (i); /* put both forks back on table */
}
}
take_forks(i) /* philosopher number, 0 to N-1 */
int i;
{
down (mutex); /* enter critical region */
state [i] = HUNGRY; /* record the fact that philosopher i is
hungry */
test(i); /* try to acquire 2 forks */
up(mutex); /* exit critical region */
down (s[i]); /* block if forks were not acquired */
}
put_forks(i) /* philosopher number, 0 to N-1 */
int i;
{
down(mutex); /* enter critical region */
state[i] = THINKING; /* philosopher has finished eating */
test(LEFT); /* see if left neighbor can now eat */
test(RIGHT); /* see if right neighbor can now eat */
up(mutex); /* exit critical region */
}
test(i) /* philosopher number, 0 to N-1 */
int i;
{
if ( state[i] == HUNGRY && state[LEFT] != EATING &&
state[RIGHT] != EATING ){
state[i] = EATING;
up (s[i]);
}
}
Dear DDJ,
The articles by Paterson and Abrash in the March issue of DDJ were top notch. Thanks. However, it turns out that there is a better way to convert a binary number in AL to the appropriate ASCII character. I originally came up with the following:
cmp al, 10 cmc adc al, 30h daa
which is two cycles faster, as it uses a CMC in place of one of the DAAs. It turns out, however, that the above can be further optimized:
cmp al, 10 sbb al, 69h das
which is one byte shorter and four cycles faster on an 8088 (although with the 8088's prefetch queue, maybe I should say "one byte faster," not one byte shorter ...). Thanks again for a great magazine.
Tim Lopez San Jose, California
Dear DDJ,
I was pleased to see the article in the March 1990 DDJ about OOP assembly language. I was surprised, though, to see that messaging was not implemented by the author. I used the same techniques as Mr. Hyde as far as structures go, but in addition I added messaging as a simple jump table. Each object handled its own messages, eliminating the need for the caller to know the procedure name of the desired method.
Greg Messer Houston, Texas
Dear DDJ
I enjoyed Michael Swaine's "Programming Paradigms" column on fractals in the May 1990 DDJ. For the record, however, I would like to mention that by no means is Benoit Mandelbrot the "discoverer" of fractals. Indeed, Mandelbrot deserves credit for studying them, popularizing them, and coining the term "fractal." But von Koch had discovered the snowflake curve by 1904, and Hausdorff defined and studied fractional-dimensional sets in 1919.
Also, to get slightly technical, self-similarity is not a requirement for a set to be fractal, at least not in Mandelbrot's own definition; the set must only have fractional Hausdorff dimension.
These facts are all extracted from Mandelbrot's Fractal Geometry of Nature (Freeman, 1982), albeit with difficulty.
Daniel Asimov Berkeley, California
Dear DDJ,
I read with interest Jeff Duntemann's column "Grinding the Speckled Axe" (DDJ, May 1990) in which he talks about the difficulty of drawing the line between parent and child. He gave two object hierarchies for accepting user input:
What interests me is that this situation is not specific to OOP, but actually occurs in any language that supports functions or procedures. The first hierarchy is roughly equivalent to writing functions GetStringField(), GetIntegerField(), and GetDateField(). (Admittedly, the common code would have to be copied manually rather than neatly encapsulated as in the Field object.) The second hierarchy is equivalent to writing a function GetStringField(), and then writing functions GetIntegerField() and GetDateField that call GetStringField() to get raw data, and then validate it appropriately. The first solution duplicates a lot of code, but it allows each character to be validated as the user types. The second solution is code-efficient, but the user's errors aren't detected until <Enter> is pressed. Which is better? I don't know, either. There's still no firm answer after all these years of procedural languages, and I suspect there never will be.
Steve Corwin Shelton, Connecticut
Dear DDJ,
This is in response to the April 1990 "C Programming" column by Al Stevens. I was gratified to see that Mr. Stevens likes TopSpeed C, and does not hesitate to recommend it to others. However, Mr. Stevens does raise several points about TopSpeed C to which I'd like to respond.
TopSpeed C does allow an application to call INTERRUPT functions. However, it must be done through the library's _CHAIN_INTR () function.
While TopSpeed C does not provide the _FLAGS pseudovariable, it is fairly easy to implement such a function. TopSpeed C allows the programmer to control many aspects of how functions are called. This function declaration allows the CPU's flags to be read, as in Example 3. Similarly, this function declaration allows the CPU's flags to be set, as in Example 4. In these two examples, compiler pragmas are used to:
As you can see, TopSpeed C provides the programmer with a considerable amount of power. Since no C compiler could possibly provide intrinsic functions for everything that every programmer would want to do, we designed TopSpeed C to allow the programmer to define functions which are called with the same efficiency as those which are intrinsic to the compiler.
Mr. Stevens's comments on the documentation are correct. Fortunately, we only made a small print run of this set of manuals. We will make corrections to the manuals for inclusion in the next print run, and will make the corrected manuals available to customers with an older set.
Mr. Stevens has provided us with useful recommendations on how to improve the WATCH utility. While a fully configurable utility (as Mr. Stevens wishes WATCH was) could be marketed as a product all by itself, we will continue to provide WATCH as a utility within the TopSpeed products and are working to expand its capabilities.
Don Dumitru JPI Mountain View, California
#pragma save
#pragma call (reg_saved=>(bx,cx,dx,si,di,ds,es,st1,st2), inline=>on)
static int_flags (void) = {0x9c /* pushf */,
0x58 /* pop ax */};
#pragma restore
/* usage: i = _flags(); */
#pragma save
#pragma call (reg_saved=>(ax,bx,cx,dx,si,di,ds,es,st1,st2),
inline=>on)
static void_set_flags(int i)= {0x50 /* push ax */,
0x9d /* popf */};
#pragma restore
/* usage: _set_flags(i); */