Peterson’s Algorithm for Critical Section Problem

January 20, 2023

About Peterson’s Algorithm in OS

On this page, we will learn the concepts of Peterson’s algorithm for critical section problem in operating system.Peterson’s algorithm is a programming algorithm which allows multiple processes to use the same resource single handedly with the help of shared memory for communication.

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.

Priority Scheduling

CPU Scheduling

FCFS Scheduling

Preemptive Scheduling

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

do {
    flag[i] = true;
    turn = j;
    
    while(flag[j]&& turn==j);
    
    // Critical Section

    flag[i]= false;
     
    // Remainder Section
    
} While(true);

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

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others