Mutual Exclusion

Critical Region

A critical region is a language-level construct that restricts access to a shared variable to inside a REGION block, with mutual exclusion guaranteed by the compiler, one step up from raw P/V. A conditional critical region (CCR) adds an AWAIT expression that must be true before the region body runs.

Why move from semaphores to regions?

Because P/V are error-prone: you can forget the matching V, use the wrong semaphore, or deadlock by nesting in the wrong order. A REGION binds the lock to the data: you name the variable, and the compiler places the acquire/release for you. That eliminates a whole class of programmer mistakes, but not deadlock from nested regions acquired in different orders.

Critical region syntax

VAR v : SHARED INTEGER
REGION v DO
    // critical section — mutual exclusion on v guaranteed
END REGION

Compiler emits the equivalent of v_lock.acquire(); ... v_lock.release();.

Problems

• Simultaneous reads impossible, even pure readers serialize.
• Nesting ⇒ deadlock, task1: REGION x DO REGION y DO vs. task2: REGION y DO REGION x DO is the classic AB/BA.
• Reading outside the region ⇒ torn reads.

Conditional Critical Region (CCR)

Add a predicate:

REGION v DO
    AWAIT conditional-expression
    ...
END REGION

If the predicate is false, the region lock is released and entry is retried (naive busy-wait). Smart implementation: block on the region’s wait queue; on every exit, scan blocked tasks and unblock any whose predicate is now true.

VAR Q : SHARED QUEUE<INT,10>
REGION Q DO
    AWAIT NOT EMPTY( Q )
    // take an item from front
END REGION

Related

• Mutual Exclusion
• Monitor
• Semaphore