Concurrent Programming¶
Concurrent and parallel¶
Sequential
Execution progresses in a predefined order, one step at a time.
Concurrent
The execution order of more than one component is not defined. Also called logically concurrent.
Parallel
More than one step is executed at the same time by more than one hardware. Also called physically concurrent.
Concurrent does not necessarily mean parallel. Single CPU can execute concurrent tasks by switching them.
Preemptive
A task has a chance to be switched at any time. Switching usually occurs on timer interrupts or I/O events.
Non-preemptive
A task will not be switched against its will.
Synchronization¶
Thread
A flow of control, or a unit of execution that holds its context such as CPU registers and contents of stack. One thread executes a program sequentially, while more than one threads execute a program concurrently.
Synchronization
To put a constraint on execution of threads at a certain point of a program.
Cooperation synchronization
When we simply say synchronization, it usually means cooperation synchronization. It includes several cases: for example, a fast thread waits for another slow thread, a thread sends data to another thread, etc.
Competition synchronization
It is also called mutual exclusion. When a certain resource cannot be accessed by more than one thread at the same time, a constraint should be put so that only one thread access it at a time.
Critical section
A part of program that needs mutual exclusion.
Competition
Suppose the initial value of a variable x is 1. Both threads A
and B will increment x by 1.
A reads 1 (the value of
x).B reads 1 (the value of
x).A computes 1+1 (result of increment)
B computes 1+1 (result of increment)
A writes 2 to
xB writes 2 to
x
Deadlock and starvation¶
If a thread locks a shared resource, other threads cannot access it until the thread unlocks it.
Deadlock
All threads are waiting for some shared resources to be unlocked. No threads can proceed.
Starvation
A certain thread cannot access a shared resource forever while others can do.
Dining philosophers problem
There is a chance that deadlock occurs.
loop
Pick up the left folk.
Pick up the right folk.
Eat for a while.
Put the both folks down.
Think for a while.
end
Now, philosphers get smarter
Still, there is a chance that starvation occurs.
loop
Pick up the left folk.
if (the right folk is not available)
then
Put the left folk down.
else
Pick up the right folk.
Eat for a while.
Put the both folks down.
Think for a while.
end
end
Exercise 19
If philosophers sit in a row, instead of a circle, deadlock will not occur. Explain why.
[Answer]
Semaphore¶
A semaphore is an abstract data type used for managing synchronization. It consists of a counter and a thread queue.
P operation
If the counter is greater than 0, decrement it by 1. Otherwise, suspend the current thread, and put it into the queue.
V operation
If the thread queue is empty, increment the counter by 1. Otherwise, pick a thread from the queue, and let it continue.
Usually provided as a library.
Error-prone. Mistakes easily cause deadlock.
Producers-consumers problem (without mutual exclusion)
In Ada, wait and release conrrespond to P operation and V
operation respectively.
semaphore fullspots, -- Number of filled spots in the buffer
emptyspots; -- Number of empty spots in the buffer
fullspots.count := 0; -- Initially no spots are filled
emptyspots.count := BUFLEN; -- Initially all spots are empty
task producer;
loop
-- Produce a data
wait(emptyspots); -- Wait if no spot is empty
-- Put the data into the buffer
release(fullspots); -- Increment the number of filled spots
end loop
end producer;
task consumer;
loop
wait(fullspots); -- Wait if no spot if filled
-- Get a data from the buffer
release(emptyspots); -- Increment the number of empty spots
-- Consume the data
end loop
end consumer;
Producer-consumer problem (with mutual exclusion)
Accessing the shared buffer should be a critical section. A
semaphore exclusion is used to lock the buffer.
semaphore exclusion, fullspots, emptyspots;
exclusion.count := 1;
fullspots.count := 0;
emptyspots.count := BUFLEN;
task producer;
loop
-- Produce a data
wait(emptyspots);
wait(exclusion); -- Lock the buffer
-- Put the data into the buffer
release(exclusion); -- Unlock the buffer
release(fullspots);
end loop
end producer;
task consumer;
loop
wait(fullspots);
wait(exclusion); -- Lock the buffer
-- Get a data from the buffer
release(exclusion); -- Unlock the buffer
release(emptyspots);
-- Consume the data
end loop
end consumer;
Monitor¶
A monitor is a syntactical structure of mutual exclusion.
Inside a monitor, only one thread can be executed at a time. This enforces mutual exclusion.
A thread can sleep in a monitor, which enables another thread to enter the monitor.
A thread can wake up another thread sleeping in a monitor.
It is less likely to make a mistake about mutual exclusion, compared to semaphore. Still, it is difficult to write cooperation synchronizations.
Producer-comsumer problem in Concurrent Pascal
type databuf =
monitor
const bufsize = 100;
var buf : array [1..bufsize] of integer;
next_in, next_out : 1..bufsize;
filled : 0..bufsize;
sender_q, receiver_q : queue;
procedure entry deposit(item : integer);
begin
if filled = bufsize
then delay(sender_q);
buf[next_in] := item;
next_in := (next_in mod bufsize) + 1;
filled := filled + 1;
continue(receiver_q)
end ;
procedure entry fetch(var item : integer) ;
begin
if filled = 0
then delay(receiver_q);
item := buf[next_out];
next_out := (next_out mod bufsize) + 1;
filled := filled - 1;
continue(sender_q)
end;
begin
filled := 0;
next_in := 1;
next_out := 1
end;
type producer = process(buffer: databuf);
var new_value : integer;
begin
cycle
(* generate a data *)
buffer.deposit(new_value);
end
end;
type consumer = process(buffer: databuf);
var stored_value : integer;
begin
cycle
buffer.fetch(stored_value);
(* consume a data *)
end
end;
Exercise 20
Which features in Java correspond to the following concepts?
monitor
sleeping in a monitor
waking up another thread
[Answer]
Channel¶
Since it is error-prone to use shared memory with mutual exclusion, there is an idea that communication should be used for synchronization. It is theoretically based on process algebras.
Occam¶
Occam was developed for Transputer, a microprocessor architecture for parallel computing of the 1980s.
Concepts of Occam are taken from the communicating sequential processes (CSP) which is one of process algebras. Its program is a collection of processes communicating with each other through channels. A channel is a one-to-one, uni-directional, and synchronous (i.e. sending and receiving must take place simultaneously) communication devise.
Go¶
Go was first announced by Google in 2009, and Version 1 was released in March 2012.
A goroutine is a function executing concurrently with others. Two goroutines can communicate via a channel. A channel may be buffered (asynchronous) or unbuffered (synchronous).