Linda & Concurrency.

There are four classic concurrency problems:

1. Critical Section / Mutual Exclusion,
2. Readers & Writers,
3. Producers & Consumers,
4. Five Dining Philosophers.


Linda - Tuple Space - has uses in Concurrency.

To achieve required results, not only code needs to be written ... tuple space also needs to be filled with initial state.

Critical Section / Mutual Exclusion.	Readers & Writers.
Let's assume that two or more processess want to access critical section of code. Critical section is this program fragment, that can be executed by at most one process at once. We assume that each process which enters critical section, will leave it in finite time. process PCS; begin   repeat     personal_affairs();     Input("ticket");     critical_section();     Output("ticket");   until false end; -- initial state: * ("ticket");	The readers-writers problem relates to an object such as a file that is shared between multiple processes. Some of these processes are readers i.e. they only want to read the data from the object and some of the processes are writers i.e. they want to write into the object. The readers-writers problem is used to manage synchronization so that there are no problems with the object data. For example - If two readers access the object at the same time there is no problem. However if two writers or a reader and writer access the object at the same time, there may be problems. To solve this situation, a writer should get exclusive access to an object i.e. when a writer is accessing the object, no reader or writer may access it. However, multiple readers can access the object at the same time. process Reader; var   r: int32; begin   repeat     personal_affairs();     Input (r: int32, 0);     Output (r+1, 0);     do_read();     Input (r: int32, w: int32);     Output (r-1, w);   until false end; process Writer; begin   repeat     personal_affairs();     Input (r: int32, 0);     Output (r, 1);     Input (0, 1);     do_write();     Output (0, 0);     until false end; -- initial state: * ( 0, 0 );
Producers & Consumers.	Five Dining Philosophers.
There are P > 0 processes in system, which produce certain data, and C > 0 processes which receive data from producers. Between producers and consumers there can be buffer B with capacity BCAPACITY, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data - consumers. Let's notice that a Tuple in Linda - Tuple Space is not a Buffer/FIFO Queue that do_produce() & do_consume() operate on. a Tuple in Tuple Space is only used to store amount of used 'places' in a Buffer/FIFO Queue. BCAPACITY is a constant, total number of 'places' in a Buffer/FIFO Queue. process Producer; const   // B Capacity: 0 ... 107.   int32 BCAPACITY = 107; begin   repeat     personal_affairs();     Input(n: int32);     if (n < BCAPACITY) {       do_produce();       Output(n+1);     } else {       Output(BCAPACITY);     }   until false; end; process Consumer; begin   repeat     personal_affairs();     Input(n: int32);     if (n > 0) {       do_consume();       Output(n-1);     } else {       Output(0);     }   until false; end; -- initial state: * (0);	Five philosophers dine by round table. Before each there's plate. Between plates lie forks. In middle of the table there's serving dish with fish. Each philosopher thinks. When he gets hungry, he reaches for forks laying at his right and left side, then starts eating. When he's done eating, he puts forks away and again devotes himself to thinking. Following conditions have to be met: * Only one philospoher ate with the same fork at the same time. * Each of the philosophers ate only and always with two (and always those which lay near his plate) forks. * No philosopher would die of starvation. * Also we want that each of the philosophers would act the same way. process Philosopher(i); var   int32 i; begin   repeat     think();     Input("room ticket");     Input("fork", i);     Input("fork", (i+1) mod 5);     eat();     Output("fork", i);     Output("fork", (i+1) mod 5);     Output("room ticket");   until false; end; -- initial state: * ("fork", 0); * ("fork", 1); * ("fork", 2); * ("fork", 3); * ("fork", 4); * ("room ticket"); * ("room ticket"); * ("room ticket"); * ("room ticket");