Process Synchronization – I

WHY PROCESS SYNCHRONIZATION?

As discussed in previous post, a Cooperating Process can affect or be affected by other processes executing in the system.

Cooperating processes can share

  • logical address space (both code and data) : using threads
  • data through files or messages → might lead to data inconsistency → need mechanisms to ensure orderly execution of cooperating processes → hence, Process Synchronization

 Let us discuss an example to illustrate how concurrent or parallel execution of processes can contribute to issues related to data integrity.

Revisiting Bounded Buffer Problem

Solution discussed → allowed BUFFER_SIZE – 1 items in the buffer at the same time

Modification → Add one integer variable “counter”, initialized  to 0.

  • increment counter by 1 as new item is added to the buffer
  • decrement counter by 1 as an item is removed from the buffer

 Code for consumer and producer processes : 

Why doesn’t this solution work?

  • These routines work in a correct manner separately, but not together
  • Let us say that the value of the counter is currently 2, and then execution of counter++ and counter– can make its value 1, 2 or 3.
  • The correct value, 2, is obtained only when producer and consumer execute separately.

How do 3 different values occur? It depends on the order of interleaving of lower-level statements for post-increment and post-decrement operators.

  • register1 and register2 might be the same register or different register. Their contents will be saved and restored by the interrupt handlers.
  • Let us take one example of interleaving of execution of counter++ and counter- – in lower-level statements. This sequence leads us to incorrect value of 1.

     

    A

    B

    C

    D

    1

    Timestamp

    Execution of

    Statement

    Values

    2

    T0

    Producer

    register1 = counter

    register1 = 2

    3

    T1

    Producer

    register1 = register1 + 1

    register1 = 3

    4

    T2

    Consumer

    register2 = counter

    register2 = 2

    5

    T3

    Consumer

    register2 = register2 – 1

    register2 = 1

    6

    T4

    Producer

    counter = register1

    counter = 3

    7

    T5

    Consumer

    counter = register2

    counter = 1

     

  • Similarly, in another order of interleaving, one can reach another incorrect value.

     

    A

    B

    C

    D

    1

    Timestamp

    Execution of

    Statement

    Values

    2

    T0

    Producer

    register1 = counter

    register1 = 2

    3

    T1

    Producer

    register1 = register1 + 1

    register1 = 3

    4

    T2

    Consumer

    register2 = counter

    register2 = 2

    5

    T3

    Consumer

    register2 = register2 – 1

    register2 = 1

    6

    T4

    Consumer

    counter = register2

    counter = 1

    7

    T5

    Producer

    counter = register1

    counter = 3

     

  • We reached incorrect states. Reason → allowed both processes to manipulate the counter variable in tandem. This leads to a race condition.

Race Condition

  • Several processes access and manipulate same data concurrently
  • outcome in these cases depend on the particular order in which access takes place
  • This condition is called Race condition
  • Preventing race condition → require Process synchronization.
  • Example of Race condition in OSs
    • Race condition might occur due to several kernel-mode processes that may be active at a given time in the OS.
    • Kernel level data structures maintain
      • list of open files
      • memory allocation information
      • interrupt handling
    • Consider a kernel-level data structure that maintains a list of open files in the system.
    • When will this list be modified? → Whenever a new file is opened or an open file is closed.
    • Consider a case when two processes simultaneously open and close a file. A race condition might occur in that case.
    • Onus of Kernel developers to ensure no race conditions

THE CRITICAL SECTION PROBLEM
Problem Statement

  • Given a system of n processes : {P0, P1, P2, ……., Pn-1}
  • Design a protocol that the N processes use to cooperate. [subject to the following conditions]
  • Each process has :
    • Critical section 
      • Segment of code in which the code may be changing common variables, writing a file, updating a table, and so on,
      • Once a process is executing in its critical section, no other process is allowed to execute its critical section.
    • Entry Section :
      • Each process must request permission to enter its critical section.
      • Entry section is the segment of code that implements this request.
    • Exit Section
      • Section of code which follows critical section.
    • The remaining part of code is Remainder section.

General structure of a process

Requirements to be fulfilled by a solution to Critical section problem

Assumption: Each process executes at non-zero speed.

No assumption made about relative speeds of n processes.

  1. Mutual Exclusion
    1. At a particular time, only one process can execute its critical section.
    2. If a process is executing in its critical section, then no other processes can be executing in their critical sections.
  2. Progress
    1. Given that no process is executing in its critical section.
    2. Now, if some process wishes to enter its critical section, then only those processes which are not executing in their remainder sections can participate in deciding which process will enter the critical section next.
    3. Selection of next process for executing in critical section cannot be postponed indefinitely.
  3. Bounded waiting
    1. After a process has made a request to enter critical section, and before that request is granted → in this time interval, there exists a limit on the number of times other processes are allowed to enter their critical sections.
    2. In other words, a process will not wait indefinitely to execute its critical section. The waiting period is bounded.

Note: Differences between Preemptive and non-preemptive kernels

 

Attribute

Preemptive kernel

Non-Preemptive kernel

1

Property

allows a process to be preempted while it is running in kernel mode

Does not allow a process to be preempted while it is running in kernel mode. A kernel mode process will run until it exits kernel mode, blocks or voluntarily yields control of the CPU.

2

Race conditions

Can happen. Developers need to ensure against race conditions

free from race conditions because only one process can be executed at a time

3

Advantages

More responsive than non-premptive kernels because there is less risk that a kernel-mode process will run for arbitrarily long period before relinquishing control of the processor to waiting processes.

easy to design as freedom from race conditions is ensured by design

Note

A preemptive kernel is more suitable for real-time programming, as it will allow a real-time process to preempt a currently running kernel process .


PETERSON’S SOLUTION

  • Classic software-based solution to critical section problem.
  • Does not guarantee correct solution to critical section problem due to the way modern computer architectures perform basic machine-language instructions, such as load and store.

Understanding Peterson’s solution

  • Restricted to 2 processes that alternate execution between critical sections and remainder sections.
  • The processes numbered as : Pi and Pj, where j = 1-i.
  • The solution requires for the two processes to share two data items:
  • turn
    • indicates whose turn it is to enter its critical section.
    • turn == i → process Pi is allowed to enter critical section.
  • flag
    • boolean array : used to indicate if process is ready to enter critical section.
    • flag[i] == 1 → process Pi is ready to enter its critical section.
  • Algorithm
    • Process Pi wants to enter critical section → indicates its intent by setting flag[i] equal to 1
    • Then it sets turn = j, which is an assertion to indicate that if the other process wishes to enter critical section, it may do so.

Note that if both the processes try to enter their critical section at the same time,

  • then turn will be set to both i and j at roughly the same time.
  • Since only one of the assignments will last and the other will be overwritten immediately.
  • the eventual value of turn will determine which of the two processes is allowed to enter its critical section first.

Structure of a process in Peterson’s solution

Proof of correctness of Peterson’s Solution

We need to prove the three requirements of solution to the Critical Section Problem.

  •  Mutual exclusion is preserved.
    • Pi enters critical section → from the while condition above, either flag[j] == 0 or turn == i
    • If both processes execute their critical sections at the same time, then flag[i] == flag[j] == 1.
    • From the above 2 observations, it is clear that both the processes cannot successfully execute their while conditions at the same time, since the value of turn can be either 0 or 1 but not both.
  • Progress requirement and bounded waiting is satisfied
     

    flag[i]

    flag[j]

    turn

    In critical section

    Comments

    1

    0

    0

    0

    No process ready to enter critical section

    2

    0

    0

    1

    No process ready to enter critical section

    3

    0

    1

    0

    Pj ready to enter critical section. but turn is of Pi

    4

    0

    1

    1

    Pj 

    Pi not ready to enter critical section.

    5

    1

    0

    0

    Pi

    Pj not ready to enter critical section.

    6

    1

    0

    1

    Pi ready to enter critical section. but turn is of Pj

    7

    1

    1

    0

    Pi

    Pj ready to enter critical section. Waits for flag[i] to turn 0 in exit section of Pi and setting of turn to 1 in entry section of Pi. Thus, Pj will enter critical section (progress) after at most one entry by Pi. (Bounded waiting)

    8

    1

    1

    1

    Pj

    Pi ready to enter critical section. Waits for flag[j] to turn 0 in exit section of Pj and setting of turn to 0 in entry section of Pj.Thus, Pi will enter critical section (progress) after at most one entry by Pj. (Bounded waiting)

In the next post, we will continue our discussion on process synchronization. Until then, keep reading and sharing 🙂