The critical section problem is used to design a protocol followed by a group of processes, so that when one process has entered its critical section, no other process is allowed to execute in its critical section.

The critical section refers to the segment of code where processes access shared resources, such as common variables and files, and perform write operations on them.

Since processes execute concurrently, and process can be interrupted mid-execution. In the case of shared resources, partial execution of processes can lead to data inconsistencies. When two processes access and manipulate the shared resource concurrently, and the resulting execution outcome depends on the order in which processes access the resource; this is called a race condition.

Race Conditions lead to inconsistent states of data. Therefore, we need a synchronization protocol that allows processes to cooperate while manipulating shared resources, which essentially is the critical section problem.

Solutions to the Critical Section problem

Any solution to the critical section problem must satisfy the following requirements:

  • Mutual Exclusion: When one process is executing in its critical section, no other process is allowed to execute in its critical section.
  • Progress: When no process is executing in its critical section, and there exists a process that wishes to enter its critical section, it should not have to wait indefinitely to enter it.
  • Bounded waiting: There must be a bound on the number of times a process is allowed to execute in its critical section, after another process has requested to enter its critical section and before that request is accepted.

Most solutions to the critical section problem utilize locks implemented on software. Solutions include (refer to OSTEP LOCKS):

The general architecture of these solutions is shown in the picture:

critical-section

  • test_and_set: Uses a shared boolean variable lock and the test_and_set instruction that executes atomically and sets the passed parameter value to true.
  • compare_and_swap: Same as test_and_set, except that the passed parameter value is set to true if it is equal to expected in the parameter of the compare_and_swap instruction.
  • Mutex locks: Software method that provides the acquire() and release() functions that execute atomically.
  • Semaphores: More sophisticated methods that utilize that wait() and signal() operations that execute atomically on Semaphore S, which is an integer variable.
  • Condition variables: Utilizes a queue of processes that are waiting to enter the critical section.