CIS 307: Protected Bounded Buffers
Protected Bounded Buffers are treated in Tanenbaum Figure 2.11
We assume that we are given an Abstract Data Type, or class, BBuffer that
is probably a queue. It has operations InitBBuffer, BEnqueue, and BDequeue.
It can hold N objects of type item.
We want to define another ADT called PBBuffer which will be usable by
concurrent processes. [Remember that the standard implementation for
Bounded Buffers is unsafe when used in a concurrent program.]
Protected Bounded Buffers can be used in all Producer-Consumer situations.
constant N = ....;
type item = ....;
type PBBuffer = record
full, empty, mutex : semaphore;
b : BBuffer;
end;
procedure InitPBBuffer(R : in out PBBuffer) is
begin
InitSem(R.full,0); InitSem(R.empty,N);
InitSem(R.mutex,1); InitBBuffer(R.b);
end;
procedure PBEnqueue (R : in out PBBuffer; I : item) is
begin
1. P(R.empty);
2. P(R.mutex);
BEnqueue(R.b,I);
V(R.mutex);
V(R.full);
end;
procedure PBDequeue (R : in out PBBuffer; I : out item) is
begin
3. P(R.full);
P(R.mutex);
BDequeue(R.b,I);
V(R.mutex);
V(R.empty);
end;
Notes:
- In 1. the calling process makes sure that the buffer is not full.
- In 3. the calling process makes sure that the buffer is not empty.
- If statements 1. and 2. are reversed we may have a deadlock.
- Notice what we have done: We have assumed a class, BBuffer, and defined
a new class, PBBuffer. We built a new abstraction in terms of existing
abstractions.
ingargiola.cis.temple.edu