Transcript Channels - METU Computer Engineering

Chapter 8
Channels
1
Concurrent Programming Constructs


So far we have seen contructs based on shared memory
concept (shared directly – buffer - or through a shared
service of an OS – semaphores and monitors)
Now, we will see constructs based on communications
(processes send and receive messages) which may be



Synchronous in which the exchange of message is an atomic
operation requiring participation of both the sender and the
receiver (receiver is blocked is message is not send yet or sender is
blocked if receiver is not ready yet
Asynchronous in which messages are saved somewhere and sender
nor receiver is blocked
This chapter is on synchronous communication methods
(channels and ADA rendezvous)
2
Channels




A channel connects a sending process with a
receiving process
Channels are typed, meaning that they must be
declared
The exchange of messages is synchronous, that is
sender and receiver have to wait for each other
Channels in operating systems are called pipes
3
Producer - Consumer Using a Channel

At p2 and q1 both processes must wait for each
other
4
Conway’s Problem



inC is the input channel for a sequence of characters send by
some process
outC is the output channel for a sequence of transformed
characters to be received by some other process
Transformation



2 ≤ n ≤ 9 occurrences of the same character is replaced by n and
the character (compress process)
A newline character is appended following every K’th character
(output process)
Pipe is the channel connecting compress to output
5
Conway’s Problem
6
Transputer and OCCAM Language




The transputer was a microprocessor developed by
Inmos Corporation to support the OCCAM
programming model.
The IMS 800 transputer contained a fast 32-bit
processor, a floating point processor, a small amount of
on-chip memory (4K) and four bi-directional high-speed
serial communication links.
Each of these communication links implement a pair of
occam channels (for example, north, east, south and
west).
OCCAM was a parallel computation language designed
for the transputer architectures
7
IMS 800 Transputer Architecture
x
External
Memory
Interface
8
A Matrix Multiplication Example






To multiply two matrices A * X, a process is allocated for each A[i,j].
The elements of X are fed from the top (an input channel)
The partial sums are passed from right to left until they emerge from
the array of processes with the final result
At the right, a set of processes feed in zeros to initialize the sums
At the bottom, sink processes absorb the elements of X as they leave
the bottom row. This is necessary since matrix element processes are
identical and need not to know if they are at a particular edge of the
array
Matrices:
123
102
4 2 6
456
x
012
=
10 5 18
789
100
16 8 30
9
Computation of One Element
789
x
2
2
0
= 7x2+8x2+9x0 = 14+16+0 = 30
10
Processor Array for Multiplication
11
Multiplier Processes
(one for each A[i,j] .. 9 in total)
12
Occam Syntax


Every statement in occam is a process. It is up to the programmer to indicate
whether the statements will be combined in sequence or parallel. For example,
SEQ
statement_1
statement_2
statement_3
PAR
statement_1
statement_2
statement_3
Indentation is used instead of punctuation (';') to show program structure. Input
and output statements have the form
channel ? variable
channel ! value
respectively.
13
Multiplier Process in Occam Syntax
WHILE TRUE
SEQ
north ? x
south ! x
east ? sum
sum := sum + a * x
west ! sum
14
Multiplier Process Made More Paralel


north ? x -- read first x
WHILE TRUE
SEQ
PAR
south ! x
east ? sum
temp := a * x
PAR
west ! sum + temp
north ? X
After reading the x value, transferring value to south, reading the partial sum
from east and multiplication of a*x can be done in parallel. Similarly,
transferring new sum and reading next x value can be done in parallel after
waiting for the first set of parallel computations.
15
The Dining Philosophers with Channels




A fork is a process which is connected by a channel to the philosopher on its left
and right
Before eating a philosopher waits for an input from the left and right channels (value
is not important – but both forks must be available) in p2 and p3
A fork process sends a “true” value down the channel when the fork is free (q1) and
then waits for the fork to become free again after eating (q2)
The philosopher releases the forks after eating in steps p5 and p6
16
Rendezvous in ADA



Communication in ADA is synchronous and unbuffered
Two processes (tasks in ADA) must meet in a rendezvous in
order to communicate. This means one of the two processes
must wait for the other to come to the rendezvous point
One of the two processes is called the calling task and the
other as an accepting task
 The calling task must know the identity of the
accepting task and the name of the rendezvous location
called the entry
 The accepting task does not know the identity of the
calling task
17
ADA Tasks

An ADA task has two sections:
 A specification (declaration) section contains the
declarations of the entries (their names)
 The body (code) section contains the entry points
and the code to be executed in the rendezvous
18
Comparison of Communication Methods
ADA Way
Other Methods
Consumer
Producer
Buffer
Process
Producer
Consumer
Buffer Data Structure
19
Producer-Consumer With a Degenerate Bounded Buffer
(Task Specification)
task buffer is
entry append(i: in integer);
entry take(i: out integer);
end buffer;

The above task specification declares two entry
points (append, take) for the accepting task
20
Producer-Consumer With a Degenerate Bounded Buffer
(Task Body)
task body buffer is
buf
:array(0..n-1) of integer;
in_ptr, out_ptr
:integer:= 0;
count
:integer:= 0;
begin
loop
accept append(i: in integer) do
buf(in_ptr) := i;
end append;
count:= count+1;
in_ptr := (in_ptr+1) mod N;
accept take(i : out integer) do
i:= buf(out_ptr);
end take;
count:= count-1;
out_ptr:= (out_ptr+1) mod N;
end loop;
end buffer;
21
Producer and Consumer Processes
procedure producer;
var i
:integer;
begin
repeat
produce(i);
buffer.append(i);
until false
end;
procedure consumer;
var i
:integer;
begin
repeat
buffer.take(i);
consume(i);
until false
end;
22
Comments

Producer and consumer processes interact with the
buffer task using the entry points buffer.append(i) and
buffer.take(i)

Producer, consumer and buffer tasks execute
concurrently. Sometime later, one of the processes,
producer or consumer, try to make a rendezvous with
the buffer task by calling the appropriate entry point.
The process then stops and waits until the rendezvous is
accomplished
23
Comments (Cont.)

The buffer process executes until execution reaches one
of the accept statements (append or take). Let us assume
that it reaches the accept append. This entry point is
for the producer to pass a value.



If the producer had called buffer.append(i) before, the buffer
task executes its accept append body
If the producer had not called buffer.append(i), the buffer task
stops and waits for the rendezvous
When the accept body execution is finished, the value
from the producer is stored in the buffer task and both
processes (consumer and buffer) start to execute
concurrently
24
Comments (Cont.)


In the buffer process, the task makes two rendezvous. Note
that, buffer process works in a synchronized fashion.
Producer produces a value, puts it in buffer by calling
buffer.append(i). The next append rendezvous happens after
a take rendezvous.
Other producer processes may call buffer.append(i) causing
them to be queued in a FIFO manner. Similarly, consumer
processes are queued up at take entries assuming that there
are several producers and consumers active at the same time
25
The Select Statement



The previous solution is a degenerate because it has no
provisions for refusing a rendezvous with a full or empty
buffer.
Furthermore, there is a strict alternation between producing
and consuming
The select statement allows a task to select an entry call
amoung several alternatives (like a case statement in
Pascal) and also conditionally accept an entry call
26
Task Body with a Select Statement
task body buffer is
buf
:array(0..n-1) of integer;
in_ptr, out_ptr
:integer:= 0;
count
:integer:= 0;
begin
loop
select
when count < N =>
accept append(i: in integer) do
buf(in_ptr) := i;
end append;
count:= count+1;
in_ptr := (in_ptr+1) mod N;
or
when count > 0 =>
accept take(i : out integer) do
i:= buf(out_ptr);
end take;
count:= count-1;
out_ptr:= (out_ptr+1) mod N;
end select;
end loop;
end buffer;
27
Comments



The boolean expressions prefixed to the accept statements are
called quards. If the expression is true, the alternative is an open
alternative permitting a rendezvous else it is a closed alternative
denying a rendezvous
When the buffer is empty (count = 0), the take alternative is
closed. When the buffer is full (count = N), only the take
alternative is open
When “0 < count < N”, buffer task will wait for the first caller
that calls an entry. If there are calling tasks waiting in both entry
queues, the task is chosen according to an implementation
algorithm (first open alternative for example). In the bounded
buffer case, first open alternative is a good choice to fill an empty
buffer or empty a full buffer
28
General Form of a Select Statement



Arbitrary number of quarded accept statements
separated with or’s
The quard may be missing implying “when true =>”
The last alternative may be
Else followed by a sequence of statements
 Delay T followed by a sequence of statements
 Terminate

29
Semantics

The quards are evaluated to determine open alternatives.
There must be at least one open alternative else it is a
fatal error. The quards are not re-evaluated during
the execution of the select statement


If all open alternative queues are empty, the accepting
task is suspended until a caller asks for a rendezvous
If open alternative queues are not empty, the first
process from one of the alternative queue is chosen
(depending on the implementation algorithm)
30
Programming with Rendezvous

A simple rendezvous is a remote procedure call.
The calling task calls a procedure which belongs
to another task, namely the accepting task
Producer
Buffer.append(i)
Buffer
Accept append
End append;
31

Emulation of Binary Semaphores in
ADA
Null accept bodies may be used for synchronization of
tasks. As an example, consider the following emulation of
binary semaphores in ADA
Task body semaphore is
Begin
loop
accept wait;
accept signal;
end loop;
End semaphore;
32
Semaphore Example Continued ..
Task body producer is
Begin
loop
produce;
semaphore.wait;
put-in-buffer;
semaphore.signal;
end loop;
End producer;
Task body consumer is
Begin
loop
semaphore.wait;
get-from-buffer;
semaphore.signal;
consume;
end loop;
End consumer;
33