Page 32 - DCAP103_Principle of operating system

Unit 1: Operating System

Concurrent processes can only refer to and change a shared variable inside a structured statement Notes
called a critical region.
region v do S

This notation associates a statement S with a shared variable v.
Critical regions referring to the same variable exclude each other in time. They can be arbitrarily
interleaved in time. The idea of progressing towards a final result (as in a concurrent statement)
is therefore meaningless. All one can expect is that each critical region leaves certain relationships
among the components of a shared variable v unchanged. These relationships can be defined by
an assertion It is about v which must be true after initialization of v and before and after each
subsequent critical region associated with v. Such an assertion is called an invariant.
When a process enters a critical region to execute a statement S, a predicate P holds for the
variables accessible to the process outside the critical region and an invariant. It holds for the
shared variable v accessible inside the critical region. After the completion of S, a result R
holds for the former variables and invariant. It has been maintained. So a critical region has
the following axiomatic property:

“P “
region v do \P &I” S \R&I”;

“R”
Process Communication: Mutual exclusion of operations on shared variables makes it possible
to make meaningful statements about the effect of concurrent computations. But when processes
cooperate on a common task they must also be able to wait until certain conditions have been
satisfied by other processes. For this purpose it introduce a synchronizing primitive, await, which
delays a process until the components of a shared variable v satisfy a condition.

B:
region v do

begin . . . await B; . . . end
The await primitive must be textually enclosed by a critical region. If critical regions are nested,
the synchronizing condition B is associated with the innermost enclosing region.

“Consumer” “Producer”
region v do region v do S 2

begin await B; S end
1
The implementation of critical regions and await primitives is illustrated in Fig.1.7. When a
process, such as the consumer above, wishes to enter a critical region, it enters a main queue
Qv associated with a shared variable v. After entering its critical region, the consumer inspects
the shared variable to determine whether it satisfies a condition B. In that case, the consumer
completes its critical region by executing a statement S1; otherwise, the process leaves its critical
region temporarily and joins an event queue Qe associated with the shared variable.

LOVELY PROFESSIONAL UNIVERSITY 25