Critical Section Problem
Critical Section Problem – A piece of code inside a process that wants access to shared resources and that need not be executed while another process is in a corresponding section of code.
Consider system of n processes {p0, p1, … pn-1}
■ Every process has critical section segment of code
– Process may be changing common variables, writing file, updating table, etc
–No two processes can be executing in their critical sections at the same time.
■ Critical section problem is to design procedure to solve this:
■ Every process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section
Indirect Communication
Overall structure of process Pi
Solution for the critical-section problem must fulfil the following three requirements:
■ Mutual exclusion. In case of a process P is executing in its critical section, then no other processes can be executing in their critical sections.
■ Progress. In case of no process is running in its critical section and some other processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can take part in the decision on which will enter its critical section next, and this selection cannot be postponed indefinitely.
■ Bounded waiting. The limit exists on the number of times the process has applied to enter its critical section and before this request is granted.
■ Two common approaches are used to handle critical sections in operating systems: preemptive kernels and non-preemptive kernels.
■ A preemptive kernel allows a process to be preempted while it is running in kernel mode.
■ A non-preemptive kernel does not preempt a process running in kernel mode; a kernel mode process will run up until it exits kernel mode, blocks or voluntarily transfers control of the CPU.
Peterson’s Solution
Good algorithmic representation of the resolution of the problem
■ Process solutions are
Suppose that the instructions for loading and storing the machine are atomic; It cannot be interrupted
■ Both processes share two variables:- int tower;- Boolean flag [2]
■ The variable turn indicates which turn to enter in the critical section
■ The flag table is used to point out if a process is ready to enter the critical section. Flag [i] = true implies that the pi process is ready!
■ If tour = = i, then process P; is allowed to run in its critical section. The table of flags is used to identify in case of if a process is ready to enter its critical section. For example, if Flag [i] is true, this value indicates that P; is ready to enter his critical section.
Algorithm
do {
flag[i] = true;
turn = j;
while (flag[j] && turn = = j);
critical section
flag[i] = false;
remainder section
} while (true);
Provable that the three CS requirement are met:
1. Mutual exclusion is conserved
Pi enters CS only if:
either flag[j] = false or turn = i
2. Progress condition is satisfied
3. Bounded-waiting condition is met
