What is critical region in operating systems?

Answer 1

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.