What are the names of the two processes associated with the bounded buffer problem

---

1. Language features for concurrency
   1. Semaphores
   2. Monitors
   3. Message Passing

Language features for concurrency

Three major mechanisms:

1. Semaphores (for mutual exclusion)
   Nội dung chính Show

   • Language features for concurrency
   • Semaphores
   • Message Passing
   • What are the names of the two processes associated with the Boundedbuffer problem?
   • What is the bounded buffer problem also known as?
   • What are the two operations that can be performed on a semaphore?
   • How many buffers are there in the bounded buffer problem?
2. Monitors (for mutual exclusion)

3. Message passing (using "tasks")

Focus here on producer/consumer or bounded buffer problem.
Two processes cooperating, one by adding items to a buffer, the other removing items. Ensure not remove when nothing there and not overflow buffer as well.

Text also focuses on parallel matrix multiplication (read on own).

Text also discusses some ways of handling with simple extensions of existing languages:

• Parallel for loops

• library routines for spawning and managing processes.

Coroutines also worth noting (part of Modula-2). Iterators were a special case.

Idea is co-equal routines which pass control back and forth.
E.g., our Modula-2 has library supporting routines:

    NewCoroutine(P: PROC; workspaceSize:CARDINAL; VAR q: COROUTINE);

Starts up new coroutine, q, by executing procedure P.

        Transfer(VAR from, to: COROUTINE)

Transfers control from one coroutine to another.

Can have multiple coroutines executing same procedure or can all be distinct.

Usually run on single processor.

Can think of as supporting multi-tasking. Good for writing operating systems.

See Modula-2 code in text for bounded buffer problem with coroutines.

Semaphores

Support mutual exclusion and synchronization in shared-memory model.

Three operations:

    InitSem(S: Semaphore; value: integer);
    Wait(S: Semaphore);
    Signal(S: Semaphore);

InitSem starts up semaphore with an initial (non-negative) value.

Wait(S): If S > 0 then S := S - 1 else suspend self

Signal(S): if processes are waiting, then wake up a process, else S := S + 1;

Think of Wait(S) as claiming a resource so that no one else can get it, while Signal(S) releases the resource.

In order to solve mutual exclusion problem, must ensure that Wait and Signal execute atomically (i.e., cannot be interrupted and no one else can execute at same time).

If start w/S = 1 then protect a critical region by:

    Wait(S);    -- grab token
    {Critical region}
    Signal(S);  -- release token

Can also start with other values of S, e.g., if start w/S = 0 and call Wait(S) then suspend execution until another process executes Signal(S).

Solution to bounded buffer:

Suppose also have procedures:

    CreateProcess(p:PROC; workspacesize: CARDINAL);
        Creates nameless process
    StartProcesses;  -- starts all processes which have been created.
    Terminate;  -- stop execution of process

When all processes are terminated control returns to unit calling StartProcesses.

Main program:
CreateProcess(Producer,WorkSize);   
                                        -- create at least one producer
CreateProcess(Consumer,WorkSize);   
                                        -- create at least one consumer
BufferStart := 1;  BufferEnd := 0
InitSem(NonEmpty, 0)    
            -- semaphore w/initial value of  0 to indicate empty
InitSem(NonFull, MaxBuffSize)   
            -- semaphore w/initial value of size of buffer
InitSem(MutEx,1)        -- semaphore used for mutual exclusion
StartProcesses
end;

Procedure Producer;
begin
    loop
        read(ch)
        Wait(NonFull);
        Wait(MutEx);
        BufferEnd := BufferEnd MOD MaxBuffSize + 1;
        Buffer[BufferEnd] := ch;
        Signal(MutEx);
        Signal(NonEmpty);
    end loop;
end;

Procedure Consumer;
begin
    loop
        Wait(NonEmpty);
        Wait(MutEx);
        ch := Buffer[BufferStart];
        BufferStart := BufferStart MOD MaxBuffSize + 1;
        Signal(MutEx);
        Signal(NonFull);
        Write(ch)
    end loop
end;

Why is there a MutEx semaphore?

Technically it is not necessary here since Producer only changes BufferEnd, while Consumer only changes BufferStart, but if they both changed a count of the number of items in the buffer would be important to keep them from executing at the same time!

What would go wrong if you changed the order of the two Wait's at the beginning of either Producer or Consumer?

Biggest problem with semaphores is that they are too low level and unstructured. Accidentally reversing order or Wait'ing twice could be disastrous.

Monitors

Monitors are a much higher-level construct to support mutual exclusion and synchronization.

The idea is to provide an ADT with "condition variables", each of which has an associated queue of processes and suspend (or delay) and continue ops for en and dequeuing processes. Suspend always stops current, continue starts up new if any waiting.

Concurrent Pascal uses monitors.

• Continue by process in monitor causes it to be immediately suspended.

• Each queue can only hold one suspended process at a time. (owise error)

type buffer = monitor;

var store: array[1..MaxBuffSize] of char;
    BufferStart, BufferEnd, BufferSize: integer
    nonfull, nonempty: queue;

procedure entry insert(ch: char);
begin
    if BufferSize = MaxBuffSize then delay(nonfull);
    BufferEnd :=BufferEnd mod MaxBuffSize + 1;
    store[BufferEnd] := ch;
    BufferSize := BufferSize + 1;
    continue(nonempty)
end;

procedure entry delete(var ch: char);
begin
   if BufferSize = 0 then delay(nonempty);
   ch := store[BufferStart];
   BufferStart := BufferStart mod MaxBuffSize + 1;
   BufferSize := BufferSize -1;
   continue(nonfull);
end;

begin (* initialization *)
   BufferEnd := 0;
   BufferStart := 1;
   BufferSize := 0
end;

type producer = process (b: buffer);
var ch: char;
begin
    while true do begin
       read(ch);
       b.insert(ch)
    end;
end

type consumer = process(b: buffer);
var ch: char;
begin
    while true do begin
        b.delete(ch);
        write(ch)
    end
end;

var p: producer;
    q: consumer;
    b:buffer;
begin
    init b, p(b), q(b)
end.

Notice improved structure!

See text for simple way of emulating Semaphores w/ Monitors.

Message Passing

With distributed systems, cannot rely on shared variables for synchronization and communication.

With message passing, rely on send and receive operations:

    Procedure Send(To: Process; M: Message);
    Procedure Receive(From: Process; M: Message);

Variants exist in which drop "To" and "From" fields (broadcast messages).

Synchronization questions:

• Does sender have to wait for receiver to accept message or keep in buffer?

• Does receiver have to wait for message or can just check to see if any?

If wait for each other, called "rendezvous". Owise often use a mailbox to store messages.

Ada's tasks combine features of monitors and message passing.

Process in Ada is called a task (defined much like a package).

Task exports entry names to world (like a monitor) which can be "called".

• Entries can have parameters as well.

• Each entry has associated queue (managed as FIFO)

Task accepts an entry call via "accept" statement (not name sender).

Select allows choice of which accept is selected.

Syntax:

    select
      [when  =>] 
        {or [when  =>] }
       [else ]
    end select

when statements form guards.

System determines which "when" conditions are true and select one which has an "accept" process waiting. If several than choose arbitrary one.

Caller is blocked only during body of "accept" clause.
Can have other statements outside the "accept".

Ex from Ada:

task Buffer is      -- specification
    entry insert(ch: in CHARACTER);
    entry delete(ch: out CHARACTER);
end;

task body Buffer is
    MaxBuffSize: constant INTEGER := 50;
    Store: array(1..MaxBuffSize) of CHARACTER;
    BufferStart: INTEGER := 1;
    BufferEnd: INTEGER := 0;
    BufferSize: INTEGER := 0;
begin
    loop
        select
            when BufferSize < MaxBufferSize =>
                accept insert(ch: in CHARACTER) do
                   BufferEnd := BufferEnd mod MaxBuffSize + 1;
                   Store(BufferEnd) := ch;
                end;
                BufferSize := BufferSize + 1;
            or when BufferSize > 0 =>
                accept delete(ch: out CHARACTER) do
                    ch := Store(BufferStart);
                end;
                BufferStart := BufferStart mod MaxBufferSize + 1;
                BufferSize := BufferSize -1;
        end select;
    end loop
end Buffer;

task type Producer;
task body Producer is
    ch: CHARACTER;
begin
    loop
        TEXT_IO.GET(ch);
        Buffer.insert(ch);
    end loop;
end Producer;

task type Consumer;
task body Consumeris
    ch: CHARACTER;
begin
    loop
        Buffer.delete(ch);
        TEXT_IO.PUT(ch);
    end loop;
end Consumer;

Note Producer/Consumer run forever - no entries.

Exit from task when at end and no open subprocesses or waiting with "terminate" alternative open and parent has executed to completion. If this true of all children of process then all terminate simultaneously.

Comparing semaphores and monitors and tasking:

Semaphores very low level.

Monitors are passive regions encapsulating resources to be shared (mutual exclusion). Cooperation enforced by delay and continue statements.

Everything active in Ada tasks (resources and processes)

Monitors and processes can easily be structured as Ada tasks and vice-versa.

Ada tasks better represents behavior of distributed system.

What are the names of the two processes associated with the Boundedbuffer problem?

What is the bounded buffer problem also known as?

What are the two operations that can be performed on a semaphore?

How many buffers are there in the bounded buffer problem?