Classic Concurrency Problems.

1. Mutual Exclusion.

Let's assume that two processess want to access critical section of code. They are acting as such:

process P;

begin
  while true do
  begin
    personal_affairs;
    begining_protocol;
    critical_section;
    ending_protocol;
  end
end;

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.

See also: Petersen's Algorithm.

2. Producers & Consumers.

There are P>0 processes in system, which produce certain data, and K>0 processes which receive data from producers. Between producers and consumers there can be buffer with capacity B, whose task is balancing temporary differences during processes execution time. Processes that produce data we'll call producers, and processes receiving data --- consumers. Task is about synchronizing work of producers and consumers, such as that:

* Consumer would wait for data receive in situation when buffer is empty.
* Producer, when putting data in buffer would not overwrite data already written, but not received yet by consumer. It requires stopping temporarily producer in situation when there is no empty space in buffer.
* If many consumers wait for when data arrives in buffer, and if constantly new data is produced, then each waiting consumer will get something from buffer.
* Won't happen such situation, that certain consumer will wait infinitely for getting data, if data arrives in buffer constantly.
* If many producers wait for buffer's free space, and consumers constantly get something from buffer, then each of waiting producers will be able to put something into buffer. There won't happen situation such as certain producer will wait infinitely, if constantly something is taken from buffer.

There are variants to this problem:

* Buffer might be infinite.
* Cyclic buffer with finite space.
* No buffer at all.
* Many producers or only one.
* Many consumers or only one.
* Data might be produced and consumed at quicker rate (more than one unit at once).
* Data has to be read in writing order, or not.

Producers and consumers problem is abstraction of many situations existing in computer systems, for example: keyboard data write to buffer by keyboard device driver, and it's read by operating system.

3. Readers and Writers.

There are C>0 processes working in system. They read certain data. There are P>0 processes which write data. Processes writing data we'll call writers, processes reading data --- readers. Moment when processes have access to data, we'll call 'reading room visit' or 'reading room stay'.

Let's notice that many processes can read data at once. If someone wants to modify that data, then it's reasonable to block access to this data for all other processes for the time of read. It prevents read of inconsistent data (for example, partially modified data). Overall schema for processes work is such:

process Reader;

begin
  repeat
    personal_affairs;
    begining_reader_protocol;
    READ;
    ending_reader_protocol;
  until false
end

process Writer;

begin
  repeat
    personal_affairs;
    begining_writer_protocol;
    WRITE;
    ending_writer_protocol;
  until false
end

Beginning and ending protocols of selected processes should be written in a way, that allows for these conditions to be met:

* Many readers should have simultaneous access to reading room.
* If in reading room there's writer, then no one else does not write or read.
* Each reader, which wishes for data read, at some point will read them.
* Each writer, which wishes for data modification, at some point will write such modifications.

There are variants to this problem:

* In reading room many readers can spend their time at once.
* Reading room may have limited capacity.
* Writers may have priority over readers (but then we'll resign from readers liveness).
* Readers may have priority over writers (but then we'll resign from writers liveness).

4. Five Philosophers.

This problem does not have practical analogies, unlike previous classic problems, but it very well illustrates problems happening when concurrent programs are made.

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.

Scheme of such philospoher is such then:

process Philospher (i: 0..4);

begin
  repeat
    think;
    beginning_protocol;
    eating;
    ending_protocol;
  until false
end;

Task is to write beginning and ending protocols, such as following conditions would 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.

Solution to this riddle is to use waiter to let only four philosophers at the dining table at the same time, and let fifth wait. When philosopher is done eating, he leaves table and joins queue and can only return to table when waiter allows him to do this.


See also, if You wish: Basics of Concurrent Programming.

Basics of Concurrent Programming.

Concurrent work is multiple works happening at the same time, processor time quants are divided among many processes.

Process is a running program.

Thread (lightweigh process, LWP) is object inside heavyweight process that has it's own control & that shares resources with other threads in the same process.


Critical Section.

Critical section is a code section that can be accessed by only one process or thread at the same time.

Critical section has uses for example in banking: we do not want data to be overwritten as it's written by other process, or read during writing.

Example pseudocode:

process P;

begin
  while true do
  begin
    personal_affairs;
    begining_protocol;
    critical_section;
    ending_protocol;
  end
end;

Readers & Writers.

In computer science, the readers-writers problem is an example of a common computing problem in concurrency.

Shared resource is abstracted as a Reading Room.

More than one Reader may be in a Reading Room, but if writer is in a Reading Room - no one else can be there.


An example algorithm for handling the readers-writers problem is as follows:

Reader's beginning protocol:
  reader waits (goes asleep), if there's writer in a reading room.

Writer's beginning protocol:
  writer waits (goes asleep), if there's someone in a reading room.

Reader's end protocol:
  if is last exitting person, then awakens & lets writer in - if writer waits.

Writer's end protocol:
  if readers wait, then awakens them all, otherwise, if writer waits, awakens one.


There should be a limit on maximum number of readers let in in a reading room, when writer(s) is/are awaiting.


See also: Petersen's Algorithm, Classic Concurrency Problems.

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");