Operating System (BSc CSIT, CSC259): the questions likely to come

Critical Section Problem

When multiple processes share data, each process has a segment of code called the critical section (CS) in which it accesses the shared resource. The problem is to design a protocol so that no two processes execute their critical sections at the same time.

A correct solution must satisfy three requirements:

1. Mutual Exclusion – if a process is in its CS, no other process may be in its CS.
2. Progress – if no process is in its CS, only the processes not in their remainder section participate in deciding who enters next, and the decision cannot be postponed indefinitely.
3. Bounded Waiting – there is a bound on the number of times other processes can enter their CS after a process has requested entry and before that request is granted (no starvation).

General structure of a process:

do {
    entry section
        critical section
    exit section
        remainder section
} while (true);

Peterson's Solution (two processes)

A classic software solution for two processes $P_0$ and $P_1$. It uses two shared variables:

• int turn; – whose turn it is to enter.
• boolean flag[2]; – flag[i] is true if $P_i$ wants to enter.

// Process Pi  (j = the other process)
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);   // busy wait
        /* critical section */
    flag[i] = false;
        /* remainder section */
} while (true);

Why it works: $P_i$ enters only when the other process does not want to enter (flag[j]==false) or it is $P_i$'s turn (turn==i). Since turn can hold only one value, only one process passes the while test → mutual exclusion. Progress and bounded waiting also hold because a waiting process is admitted as soon as the other leaves. (Limitation: works for only 2 processes and assumes no instruction reordering.)

Semaphores

A semaphore $S$ is an integer variable accessed only through two atomic operations:

wait(S):  while (S <= 0);   // busy-wait (or block)
          S--;
signal(S): S++;

Mutual exclusion using a binary semaphore (initialised to 1):

wait(mutex);
    // critical section
signal(mutex);
    // remainder

The first process to call wait(mutex) makes mutex = 0; any other process blocks until the first calls signal(mutex). To avoid busy waiting, the OS implementation blocks the process on a waiting queue and wakes it on signal. Counting semaphores (initial value = number of available resources) generalise this to control access to a pool of identical resources.

Conclusion: The critical-section problem requires mutual exclusion, progress and bounded waiting. Peterson's solution provides a correct software solution for two processes, while semaphores offer a general, hardware-supported synchronization primitive usable for any number of processes.