Peterson’s Algorithm for Critical Section Problem in Operating System

August 21, 2019

Peterson’s Algorithm For Critical Section Problem –

  • This is a software based solution to Critical Section Problem.
  • Doesn’t work on modern architectures.
  • It’s for 2 processes which alternate execution between then critical section and remainder section. Say, P1 is the first process and P2 is the second process.
  • The 2 processes should share 2 data items with each other.

                 int turn

                 Boolean flag [2]

  •  Turn – It indicates the process who should enter into its critical section.
  • Flag Array – It tells whether a process is ready to enter its critical section. Let flag[0] indicate process P1. If flag[0] = true , then Process P1 is ready to execute in its critical section. flag[1] indicates process P2. If flag[1] = true, then Process P2 is ready to execute in its critical section.

 Now let’s take a look at peterson’s Algorithm –

  • First , p1 sets flag[0] true, then sets turn to j . So that if  P2 wants to enter Critical Section, it can do so.
  • If P1 , P2 try to execute at same time, then turn is first changed to i, then j or it could be vice-versa. But, the important point is, only one of these 2 process is allowed to enter its critical section. The second value gets overwritten.

Features of Peterson’s Solution Algorithm –

  • Does not require any special hardware.
  • Uses Busy waiting ( Spinlock ).

What is Race Around Condition ?

If many kernel processes in OS, it may lead to race around condition.

Eg – Consider a kernel data structure that maintains a list of all open files in system. List is modified if a new file is opened or closed. If 2 process simultaneously try to open files , it may separate updates to list leading to race around condition

 

Operating System Process Synchornization

      Read More

    1. Process Synchronization
    2. Critical Section
    3. Inter-Process Communication
    4. UEFI(Unified Extensible Firmware Interface) and how is it different from BIOS
    5. Mutex
    6. Semaphore
    7. Mutex vs. Semaphore
    8. Atomic Operations in OS
    9. Peterson’s Algorithm for Mutual Exclusion (Only important for Cisco and Arista Networs)
      1. Java
      2. C
      3. Python
    10. Peterson’s Algorithm for Critical Section Problem (Only important for Cisco and Arista Networs)
    11. Readers-Writers Problem
Go to Operating System Tutorials Main Page