Peterson’s Solution in OS

Algorithm for Peterson's solution

Structure of Process Pi.

do {
   // Critical Section
    flag[i] = true; // It means process pi is ready to enter its critical section
    turn = j; // It means thatif pj wants to enter than allow it to enter and pi will wait

    // Condition to check if the flag of pj is true and turn is equal to pj, this will only break when one of the conditions gets false.
    while (flag[j] && turn == [j]);

    // Remainder Section
    // It  sets the flag of pi to false because it has completed its critical section.
    flag[i] = false;
} while (true);

Similarly, Structure of Process Pj will be.

do
{
    // Critical Section
    // It means process pi is ready to enter its critical section
    flag[j] = true;

    turn = i; // It means that if pi wants to enter then allow it to enter and pj will wait

    // Condition to check if the flag of pi is true and turn is equal to pi, this will only break when one of the conditions gets false.
    while (flag[i] && turn == [i]);

    // Remainder Section
    //it  sets the flag of pj to false because it has completed its critical section.
    flag[j] = false;
} while (TRUE);

Explanation of Peterson's Algorithm

The algorithm utilizes two main variables, which are a turn and a flag. turn is an integer variable that indicates whose turn it is to enter the critical section. flag is an array of Boolean variables. Each element in the array represents the intention of a process to enter the critical section. Let us look at the explanation of how Peterson's algorithm in OS works:

1. Firstly, both processes set their flag variables to indicate that they don't currently want to enter the critical section. By default, the turn variable is set to the ID of one of the processes, it can be 0 or 1. This will indicate that it is initially the turn of that process to enter the critical section. 
    
2. Both processes set their flag variable to indicate their intention to enter the critical section. 
    
3. Then the process, which is having the next turn, sets the turn variable to its own ID. This will indicate that it is its turn to enter the critical section. For example, if the current value of turn is 1, and it is now the turn of Process 0 to enter, Process 0 sets turn = 0.
    
4. Both processes enter a loop where they will check the flag of the other process and wait if necessary. The loop continues as long as the following two conditions are met: 
   i. The other process has expressed its intention to enter the critical section (flag[1 - processID] == true for Process processID).
   ii. It is currently the turn of the other process (turn == 1 - processID).
   If both conditions are satisfied, the process waits and yields the CPU to the other process. This ensures that the other process has an opportunity to enter the critical section.
    
5. Once a process successfully exits the waiting loop, then it can enter the critical section. It can also access the shared resource without interference from the other process. It can perform any necessary operations or modifications within this section.
    
6. After completing its work in the critical section, the process resets its flag variable. Resetting is required to indicate that this process no longer wants to enter the critical section (flag[processID] = false). This step ensures that the process can enter the waiting loop again correctly if needed.

Implementation of Peterson's Algorithm

Steps for implementing Peterson's Algorithm are:

• We are creating a class to implement Peterson's algorithm.
• Inside the class, declare to variables flag and turn.
• After that, implement two functions, one for locking the flag value as 1 and the other for unlocking the flag value.
• In the lock function, change the thread's priority, wait for the thread to get executed, and change the flag value.
• In the unlock function, mark the thread that no longer has to be executed in the critical section.
• Now create a function that will reserve the value for which each thread will try lock-in Peterson's algorithm, increment an integer value entered by the user, and then unlock the thread.
• The above process will run 2 hundred million times because it is very time-independent and may take a few iterations to seal this problem.
• In the main function, we have initialized an integer value to 0, created a Peterson object p, created two threads, and waited for them to join and print the final value.

The process of ensuring mutual exclusion can be performed by two processes simultaneously. Both processes create and initialize shared variables before starting. Neither of the processes is currently interested in the critical section, so flags [0] and [1] are set to FALSE. In this instance, the turn is set either to 0 or 1 randomly (or it can always be set to 0). 

Assuming there are two processes, pi, and pj, you must write a program that guarantees mutual exclusion between the two without additional hardware support.  

Implementation in C

• C

C

#include 
#include 

void *work(void *s);
int flag[2];
int turn, val = 0;

// Simple main function for implementing Peterson's Algorithm
void main()
{
    pthread_t t1, t2;
    val = 0; // shared value

    lock_init();

    // Creating threads
    pthread_create(&t1, NULL, work, (void *)0);
    pthread_create(&t2, NULL, work, (void *)1);

    // wait for the threads to join
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    // Printing the result
    printf("Final Value: %d\n", val);
}

void lock_init()
{
    // They are reset by resetting their preference to acquire locks. This is done by giving one of them a turn.
    flag[0] = flag[1] = 0;
    turn = 0;
}

// function for locking Petersons Algorithm
void lock(int other)
{
    flag[other] = 1;  // Marking this thread wants to enter the critical section
    turn = 1 - other; // Assuming that the order thread has priority
    while (flag[1 - other] == 1 && turn == 1 - other);
}

// Method for unlocking Petersonbs algorithm

void unlock(int other)
{
    flag[other] = 0; // Marking that this thread is no longer wants to enter the critical section
}

// function to know which thread is entered
void *work(void *s)
{
    int i = 0;
    int other = (int *)s;

    printf("Thread : %d\n", other);
    lock(other);

    for (i = 0; i < 100000000; i++) // 100000000 or 1e-9 means "one times ten to the negative ninth power
        val++;

    unlock(other);
}

You can also try this code with Online C Compiler

Run Code

Output:

Thread : 0

Thread : 1

Final Value: 200000000

Also Read - Kadanes Algorithm

Examples of Peterson’s Solution

Peterson's solution is mainly used as a simple illustration of mutual exclusion in concurrent programming. There are a few examples of scenarios where Peterson's solution can be applied:

• When two processes try to access a shared printer: We can use Peterson's solution when a system with two processes needs to print documents on a shared printer. Peterson's solution can be used to ensure that only one process accesses the printer at a time.
   
• When two processes try to read from and write to a shared file: We can use Peterson's solution when two processes need to read from and write to a shared file. 
   
• When two processes compete for a shared resource: We can use Peterson's solution, suppose there are two processes competing for a limited resource, such as a network connection or a critical hardware component. 

Also, read about - Dekker's Algorithm

Advantages of Peterson’s Solution

There are some advantages of Peterson's solution mentioned below:

• It is relatively simple and easy to understand compared to more complex synchronization mechanisms. 
   
• It can be implemented using basic programming constructs. It does not necessarily rely on specific hardware features or operating system functionalities. 
   
• It only requires a few variables to be maintained for each process. This makes it lightweight in terms of memory and processing overhead. 
   
• It is widely used in academic settings to teach the concept of mutual exclusion and concurrency. 

Disadvantages of Peterson’s Solution

There are some disadvantages of Peterson's solution mentioned below:

• It is designed specifically for scenarios involving two concurrent processes. 
   
• It employs a busy waiting approach, where processes continuously check the flag and turn variables in a loop until they can proceed. 
   
• It assumes certain properties, such as the atomicity of certain operations and a low level of concurrency. These assumptions may not hold in all systems. The algorithm may fail to provide the expected mutual exclusion in such cases.
   
• It does not guarantee fairness among processes. It is possible for a process to be indefinitely delayed or starved if the other process continually holds the turn, resulting in a lack of fairness in accessing the critical section.

Mutual Exclusion in OS

Operating systems use mutual exclusion to guarantee that only one process at a time can access an important component (shared resource) in order to avoid disagreements and maintain data integrity. This is typically achieved using synchronization mechanisms like semaphores or mutex locks.  The resource is locked when a process enters the critical area, preventing anyone else from accessing it. The resource must first be unlocked before any other processes can use it. By limiting concurrent access, this minimizes data corruption or consistency issues. Other processes can enter once a process completes its crucial portion and releases the lock. This guarantees controlled and ordered access to shared resources.
 

Frequently Asked Questions

What is Peterson's solution to two processes?

Peterson's solution is a software-based algorithm ensuring mutual exclusion for two processes by using flags and turn variables to coordinate access to a critical section.

How does Peterson's algorithm prevent starvation?

Peterson's algorithm prevents starvation by fairly alternating access to the critical section using the "turn" variable, ensuring both processes eventually get access.

What are the three requirements of Peterson's solution?

Shared memory, atomic flag operations, and strict alternation are Peterson's solution requirements for achieving mutual exclusion in a two-process system.

What is Peterson's solution restricted to?

Peterson's solution is restricted to two processes running alternatively between critical sections. We will call these processes Process 0 and Process 1. 

Why Peterson's solution Cannot be used for modern OS?

In systems with multiple CPUs, the algorithm may fail to work because the program order of events occurring on one CPU may be perceived differently on another.

Does Peterson's solution satisfy bounded waiting?

Yes, Peterson's solution satisfies bounded waiting because it allows mutual exclusion, and bounded waiting is one of the characteristics of mutual exclusion. So eventually, bounded waiting will also be satisfied by Peterson's solution.

How many processes are applicable to Peterson's solution?

At maximum, there can only be 2 processes of consideration for Peterson's solution. As mutual exclusion can ensure or allow only one process from two to access the critical section.

Conclusion

As a solution to the problem of critical sections, Peterson's algorithm uses shared memory to declare intentions. 

A concurrent programming algorithm for mutual exclusion allows two or more processes to communicate using only shared memory and thus share a single resource without conflict. 

Recommended Readings

• Demand Paging in OS
• Process Synchronisation
• Introduction to Threads
• Multithreading in C#

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top Tech Companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Check out some of the amazing Guided Paths on topics such as Operating Systems, Data Structure and Algorithms, Competitive Programming, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio.