4.6 Competing for Resources
One of the keys problems of parallel programming is several processes competing for limited resources and using them in such a way that does not lead to deadlock.
“Dining Philosophers” is a well-known textbook example used to demonstrate the problems of competition for resources and of possible deadlock. The philosophers’ (usually 5 of them) spend their time thinking and eating. They sit around a circular table with forks placed between them. There are only as many forks as philosophers, they need to share them and, as they eat spaghetti, a philosopher can only eat when both left and right forks are available. This means that none of the particular philosopher’s neighbors can be using forks for him to begin to eat. If the philosophers were undisciplined enough to grab forks when one was available and then wait for the other one, this would quickly lead to deadlock, which in this case would mean each philosopher holding one fork and forever waiting for the other one to become available.
Ability to code this abstract example in a clear and brief manner has been for a long time a test of parallel programming techniques. Dealing with such issue in straightforward, natural fashion has been a declared goal of stress-flow. The best prior art method of SCOOP/Eiffel proposed solving this issue by issuing some “eat” call with proper left and right forks as parameters. To indicate that forks were shared resources competed for, the arguments were proceeded with keyword “separate.” A compiler would generate proper code to obtain access to both forks as part of the call to “eat.” This is a fairly good method, but it still does have some big problems. First is the fact that the programmer still has to remember to mark everything “separate” as such. This undermines ideal object-oriented principle in which object “fork” should declare itself the right way to be used and disallow all other ways. Second problem is even more troubling. If object B is separate from A and C is separate from B, how do we make A not be separate from C if we so desire?
FIG. 6: Simple/inferior syntax for coding synchronized atom operation
Stress-flow method of solving this issue needs a fork object to have a properly defined “take” atom; while using two forks at once requires calls to both atoms to be declared as one instruction. Stress-flow language could do it by defining some “synchronized” keyword beginning a block listing all compounded instructions there as shown on FIG 6. This method simply declares a list of things to do together without much flexibility – one level, ordered list of instructions. Fortunately, there is a more concise and easier to understand way. We do it by making calls to both forks part of the same instruction. Many languages already allow an expression where even two calls not returning values or even say two variable assignment instructions can be combined into a single expression. This is done by means of the comma operator. For example, “i=5,k=8,exit(1);” is a completely legal single C/C++ instruction.
FIG. 7: “Dining Philosophers” example coded using stress-flow
Listing of the “Dining Philosophers” program coded using stress-flow language is shown on FIG. 7. This is a complete code that includes all necessary declarations, all synchronization, all process initialization. Brevity shows the advantages over all prior art, which required several times more code to accomplish the same goal. Two objects are defined “Fork” and “Philosopher.” Objects that have all their elements inside a single detach statement can have the detach keyword placed as modifier of the entire object. This feature was used declaring object “Fork” – which has only one element - a stress-flow atom “take.” Object “Philosopher” declares a static array of forks, function “eat”, function “think”, and the Philosopher constructor. The array of forks is declared static because it is shared among all the philosophers. The Philosopher constructor function is a stress-flow atom with instructions in both stressed and relaxed parts. The stressed part needs to store information identifying the philosopher location so that proper forks are used. Static int variable Ph_Cnt keeps count of philosophers allocated so far. Fork pointers to be used by the current philosopher object are calculated from it. If these instructions were erroneously placed inside the relaxed sections and got executed in parallel, wrong fork pointers would often be stored. The “return” instruction marks the end of the stressed section and this is where “Philosopher” begins his cycle of thinking and eating. Since this “for” loop is placed in relaxed section, all philosophers “live their lives” simultaneously. As it needs no cooperation with others, the thinking step involves just calling the proper “think” routine. Eating part involves obtaining both forks and then doing actual eating and this is exactly what our compounded eating instruction says:
LeftFork->take(), RightFork->take(), eat();
Logical meaning of it is exactly what it says: take the left fork, while still holding it take the right fork, and while still holding both – eat. When stress-flow calls are compounded together like that they work as one. If we wanted to change some data after all the locks are reserved but before any of the stress atoms run, we could do it in the same instruction as well:
k=1,LeftFork->take(), RightFork->take(), eat();
This method can be used, among other things, to safely pass parameters to called stress atoms by member or global variables, rather than by parameters.
Here is how this code is compiled. Every time a single instruction is compiled, the compiler identifies all stress-flow atoms used in the instruction and builds a list of them. Instructions for going through entire list and reserving lock of every stress-flow atom found in the compiled instruction are placed before the regular compilation of the expression. Calling a stress-flow atom was previously defined as a multiple step process precisely because the lock reserving/releasing steps had to be separated from the other steps and placed together with reserving/releasing instructions of other compounded stress-flow atoms.
Unless all locks on the list can be reserved together, none of them are. The way this is done in practice is by going through the list and reserving each of them if they are free. If a lock is not free, the code needs to go back and free all locks reserved so far, and then issue lock reserving instruction for the busy lock. This will place our execution thread in queue waiting for the busy lock and then suspend it. All suspended threads will therefore queue in currently most contested resource and will be restored one by one as the previous user frees it. Thus restored thread will try to reserve the entire list of the needed locks again.
FIG. 7A: A modification of declarations in “Dining Philosophers” example
If the “eat” procedure had to do some interfacing with the “Fork” objects, it is perfectly OK as entire eat (or its stressed section if it were a stress-flow atom) runs while both needed forks are reserved. All three atoms/routines could now safely interface with each other any way it was necessary while in their stressed section and then do some processing fully independently in their relaxed sections if this was desired. To make this matter between forks and eating even more clear, both “eat” procedure and the Fork definitions could be placed inside an detach statement as shown on FIG. 7A. The extra lock is not at all necessary, but Forks would be shown to be a resource only accessed when eat is its stressed state.
The process of encapsulating entire expression within lock operation instructions would be applied to all expressions, therefore, the result would be the same if “take” function of Fork object returned values and, for example, these values were added. Exactly the same happens in case stress atom functions called from expressions used as parameters to other calls. This way, if the “take” routine returned some pointers or IDs needed by the eat routine, the whole philosopher “eating” step could look like this:
The ordering of instructions would be same as before due to order in which the compiler must always process such instructions: parameters must be evaluated before the “eat” call. Furthermore, if function “take” was implemented as C++ pointer/ID type operator overloading or simply were some data placed in the “detach” block, the instruction could just look like this:
This roughly mimics the goals of SCOOP prior art method with the very important difference that here it is just only one of many coding options naturally available through far more powerful and clear syntax and method, while in SCOOP this was the only method accomplished by declaring parameters to “eat” as “separate.” But even that mimicked syntax carries extremely important difference. In our example, simple definition of each fork created all necessary mechanisms to properly use that fork rather than requiring/trusting that function on every possible user of forks. Another critical difference is that in stress-flow the forks create themselves as needed rather than having to be created ahead of time as was the case with SCOOP prior art.
The “separate” parameter method as means of synchronization is also very ambiguous in case where more than one level of operations are to be performed: if a separate argument needs to be passed further, does it remain only one-level separate or is separate from the first “separate” process/call? No such ambiguities are at all possible with the stress-flow method, where critical synchronization rules of using a specific object can be clearly defined within that object itself rather than by having to be declared by its users. SCOOP programs also could not even begin to express the flexibility and power of stress-flow accomplished through the stressed/relaxed code composition idea.
Send mail to
firstname.lastname@example.org with questions or