What is critical region in operating systems?
1) CRITICAL REGIONS
a) Motivation
The time dependent errors can be easily generated when
semaphores are used to solve
the critical section problem. To overcome this difficulty a new
language construct, the
critical region was introduced.
b) Definition and notation
A variable v of type T, which is to be shared among many
processes, can be declared:
VAR v: SHARED T;
The variable v can be accessed only inside a region statement of
the following form:
REGION v DO S;
This construct means that while statement S is being executed,
no other process can access the variable v. Thus, if the two
statements,
REGION v DO S1;
REGION v DO S2;
are executed concurrently in distinct sequential processes, the
result will be equivalent
to the sequential execution S1 followed by S2, or S2 followed by
S1.
To illustrate this construct, consider the frames CLASS defined
in abstract data type.
Since mutual exclusion is required when accessing the array
free, we need to declare
it as a shared array.
VAR free: SHARED ARRAY [l..n] OF boolean;
The acquire procedure must be rewritten as follows;
PROCEDURE ENTRY acquire (MAR index: integer);
BEGIN
REGION free DO
FOR index := 1 TO n DO
IF free[index] THEN
BEGIN
free[index] := false;
exit;
END;
index := 1;
END;
The critical-region construct guards against some simple errors
associated with the semaphore solution to the critical section
problem which may be made by a programmer.
c) Compiler implementation of the critical region construct.
For each declaration
VAR v: SHARED T;
the compiler generates a semaphore v-mutex initialized to 1. For
each statement,
REGION v DO S;
the compiler generates the following code:
p(v-mutex);
S;
V(v-mutex);
Critical region may also be nested. In this case, however,
deadlocks may result.
Example of deadlock)
VAR x, y: SHARED T;
PARBEGIN
Q: REGION x DO REGION y DO S1;
R: REGION y DO REGION x DO S2;
PAREND;
2) CONDITIONAL CRITICAL REGIONS
The critical region construct can be effectively used to solve
the critical section problem.
It cannot, however, be used to solve some general
synchronization problems. For this
reason the conditional critical region was introduced.
The major difference between the critical region and the
conditional critical region
constructs is in the region statement, which now has the
form:
REGION v WHEN B DO S;
where B is a boolean expression.
As before, regions referring to the same shared variable exclude
each other in time.
Now, however, when a process enters the critical section region.
the boolean expression
B is evaluated if the expression is true, statement S is
executed. if it is false, the
process relinquishes the mutual exclusion and is delayed until B
becomes lame and no
other process is in the region associated with v.
Example for bounded buffer problem)
VAR buffer: SHARED RECORD
pool: ARRAY [0..n-l] OF item;
count, in. out: integer;
END;
The producer process inserts a new item nextp in buffer by
executing
REGION buffer WHEN count < n DO
BEGIN
pool[in] := nextp;
in := in + i MOD n;
count := count + 1;
END;
The counter process removes an item from the shared buffer and
puts it in nextc by
executing:
REGION buffer WHEN count > 0 DO
BEGIN
nextc := pool[out];
out := out +1 MOD n;
count := count - 1;
END;
However, the CLASS concept alone cannot guarantee that such
sequences will be
observed.
* A process might operate on the file without first gaining
access permission to it;
* A process might never release the file once it has been
granted access to it;
* A process might attempt to release a file that it never
required;
* A process might request the same file twice;
Not that we have now encountered difficulties that are similar
in nature to those that
motivated us to develop the critical region construct in the
first place. Previously, we
had to worry about the correct use of Semaphores. Now we have to
worry about the
correct useo higher-level programmer-defined operations, with
which the comelier can
no longer assist us.
