Page 33 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes Figure 1.7: Scheduling of Conditional Critical Regions V by Means of
Process Queues Q and Q e
v

Q e

Q v V

All processes waiting for one condition or another on variable v enter the same event
queue. When another process (here called the producer) changes v by a statement S inside
2
a critical region, it is possible that one or more of the conditions expected by processes in
the event queue will be satisfied. So, after completion of a critical region, all processes in
the event queue Q are transferred to the main queue Q to enable them to reenter their
e
v
critical regions and inspect the shared variable v again. It is possible that a consumer will
be transferred in vain between Q and Q several times before its condition B holds. But
v
e
this can only occur as frequently as producers change the shared variable. This controlled
amount of busy waiting is the price we pay for the conceptual simplicity achieved by using
arbitrary Boolean expressions as synchronizing conditions. The desired invariant it for the
shared variable v must be satisfied before an await primitive is executed. When the waiting
cycle terminates, the assertion B & I holds.
As an example, consider the following resource allocation problem—two kinds of concurrent
processes, called readers and writers, share a single resource. The readers can use the resource
simultaneously, but the writers must have exclusive access to it. When a writer is ready to
use the resource, it should be enabled to do so as soon as possible. This problem is solved by
Algorithm 2. Here variable v is a record consisting of two integer components defining the
number of readers currently using the resource and the number of writers currently waiting
for or using the resource. Both readers and writers are initialized to zero. var v: shared record
readers, writers: integer end w: shared Boolean;

“Reader” “Writer”
region v do region v do
begin begin

await writers = 0; writers := writers + 1;
readers := readers + 1; await readers = 0;
end end

read; region w do write;
region v do region v do
readers := readers ¡ 1; writers := writers ¡ 1;

Algorithm 2: Resource sharing by readers and writers
Mutual exclusion of readers and writers is achieved by letting readers wait until the number of
writers is zero, and vice versa. Mutual exclusion of individual writers is ensured by the critical
region on the Boolean w. The priority rule is obeyed by increasing the number of writers as
soon as one of them wishes to use the resource. This will delay subsequent reader requests until
all pending writer requests are satisfied. Algorithm 2 demonstrates the conceptual advantage
of a structured notation.

26 LOVELY PROFESSIONAL UNIVERSITY