Peterson’s Algorithm in Process Synchronization

The producer-consumer problem (or bounded buffer problem) describes two processes, the
producer and the consumer, which share a common, fixed-size buffer used as a queue.
Producers produce an item and put it into the buffer. If the buffer is already full then the
producer will have to wait for an empty block in the buffer.

Consumers consume an item from the buffer. If the buffer is already empty then the consumer
will have to wait for an item in the buffer.
Implement Peterson’s Algorithm for the two processes using shared memory such that there is
mutual exclusion between them. The solution should have free from synchronization problems.

What is synchronization in concurrent programming?

Synchronization refers to the coordination of multiple processes or threads to achieve a desired

outcome.
It involves using synchronization mechanisms like locks, semaphores, or mutexes to control
access to shared resources and prevent race conditions or conflicts.
Common synchronization mechanisms include locks, semaphores, condition variables,
monitors, and atomic operations.
These mechanisms provide ways to control access to shared resources and coordinate the
execution of concurrent processes or threads.

Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual
exclusion that allows two or more processes to share a single-use resource without conflict, using
only shared memory for communication.
It was formulated by Gary L. Peterson in 1981.[1] While Peterson's original formulation worked
with only two processes, the algorithm can be generalized for more than two.
Peterson's solution is the synchronization algorithm which is basically used in Operating systems.
Peterson's solution is used to provide the operating system with a functionality called mutual
exclusion, where two concurrent processes can share the same resource with any problem or
collision.
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 thatif pi wants to enter than 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]==trueforProcessprocessID).
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 for 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.

Peterson’s algorithm is used for mutual exclusion and allows two processes to share a single-use
resource without conflict. It uses only shared memory for communication. Peterson’s formula
originally worked only with two processes, but has since been generalized for more than two.

Peterson's solution is a classic solution to the critical section problem. The critical section problem
ensures that no two processes change or modify a resource's value simultaneously.

What are the three requirements of Peterson's solution?

Peterson's Solution:
 Mutual Exclusion is assured as only one process can access the critical section at any time.
 Progress is also assured, as a process outside the critical section does not block other processes
from entering the critical section.
 Bounded Waiting is preserved as every process gets a fair chance.
What is the difference between Peterson's algorithm and Dekker's algorithm?
Peterson's algorithm is scalable to more than two processes, as it requires only two shared flags
and a turn variable for all the processes. Deadlock and starvation: Dekker's algorithm avoids
deadlock and starvation, meaning that both processes can eventually enter the critical section if
they are ready.
What is the Dekker's algorithm used for?
Operating systems − Dekker's Algorithm can be used in operating systems to prevent multiple
processes from accessing a shared resource simultaneously. For example, if two processes need to
access a file, Dekker's Algorithm can be used to ensure that only one process accesses the file at
any given time
What is the Dekker's solution?
Dekker's algorithm was the first probably-correct solution to the critical section problem. It allows
two threads to share a single-use resource without conflict, using only shared memory for
communication.
What are the disadvantages of Dekker's algorithm?
One disadvantage is that it is limited to two processes and makes use of busy waiting instead of
process suspension. (The use of busy waiting suggests that processes should spend a minimum
amount of time inside the critical section.)

What is the correctness of Dekker's algorithm?

Dekker's algorithm is correct: it satisfies the mutual exclusion property and it is free from deadlock
and starvation. The correctness properties by can be proved by constructing and analyzing a state
diagram

Peterson’s Solution The algorithm satisfies the three essential criteria to solve the critical section
problem, provided that changes to the variables turn, flag[0], and flag[1] propagate immediately
and atomically. The while condition works even with preemption

. The three criteria are mutual exclusion, progress, and bounded waiting. Since turn can take on
one of two values, it can be replaced by a single bit, meaning that the algorithms requires only
three bits of memory

bool flag[2] = {F;F};

int turn;

P0: flag[0] = true;

P0_gate: turn = 1;

while (flag[1] && turn == 1)

{ // busy wait } // critical section // end of critical section flag[0] = false;

P1: flag[1] = true;

P1_gate: turn = 0;

while (flag[0] && turn == 0)

{ // busy wait } // critical section ... // end of critical section flag[1] = false;
 What is Peterson's algorithm concurrency?
Peterson's algorithm is a synchronization algorithm used to solve the critical section problem in
concurrent programming. The critical section refers to a section of code that should be executed by
only one process at a time to avoid race conditions or data inconsistencies.

What are the two types of concurrency?

There are two common models for concurrent programming: shared memory and message
passing.
 Shared memory. In the shared memory model of concurrency, concurrent modules interact by
reading and writing shared objects in memory.
 Message passing. ...
 Process. ...
 Thread.
Why Peterson's solution has bounded waiting?
The bounded waiting says that there is a limit to how many times a process can be stopped from
getting into its critical section so that no process gets starved. But here there is no counter for that
and processes share just these two variables among themselves in this solution: int turn; boolean
flag[2];

What is principle of concurrency?

Concurrency is the execution of the multiple instruction sequences at the same time. It happens in
the operating system when there are several process threads running in parallel. The running
process threads always communicate with each other through shared memory or message passing.

Why Peterson's solution has mutual exclusion?

Peterson's solution is used to provide the operating system with a functionality called mutual
exclusion, where two concurrent processes can share the same resource with any problem or
collision. In this algorithm, a critical section is created, which is nothing but a block of code where
the shared resources exist.

What is difference between process and threads?

A process is an instance of a program that is being executed or processed. Thread is a segment of a
process or a lightweight process that is managed by the scheduler independently. Processes are
independent of each other and hence don't share a memory or other resources. Threads are
interdependent and share memory.
 What is the difference between Peterson and Dekker algorithm?
Peterson's algorithm is scalable to more than two processes, as it requires only two shared flags
and a turn variable for all the processes. Deadlock and starvation: Dekker's algorithm avoids
deadlock and starvation, meaning that both processes can eventually enter the critical section if
they are ready.

Does Peterson's algorithm implement mutual exclusion?

The Peterson algorithm provides a software-based solution for achieving mutual exclusion
between two processes or threads. By utilizing flag variables and a turn variable, it ensures that
only one process can enter the critical section at any given time, preventing race conditions and
ensuring consistency.

What are the advantages of Peterson's algorithm?

Advantages of Peterson's Solution

 Peterson's solution allows multiple processes to share and access a resource without conflict
between the resources.
 Every process gets a chance of execution.
 It is simple to implement and uses simple and powerful logic.

 It assures Mutual Exclusion, as only one process can access the critical section at a time.
 It assures progress, as no process is blocked due to processes that are outside.
 It assures Bound Waiting as every process gets a chance.

Disadvantages of Peterson’s solution:

1. Peterson’s solution is limited to two processes.

2. It involves Busy Waiting.

What is the Dekker's algorithm used for?

Operating systems − Dekker's Algorithm can be used in operating systems to prevent multiple
processes from accessing a shared resource simultaneously. For example, if two processes need to
access a file, Dekker's Algorithm can be used to ensure that only one process accesses the file at
any given time.
 What is critical section problem?
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.

What are the disadvantages of Dekker's algorithm?

One disadvantage is that it is limited to two processes and makes use of busy waiting instead of
process suspension. (The use of busy waiting suggests that processes should spend a minimum
amount of time inside the critical section.)

What is difference between mutual exclusion and mutex?

What Does Mutual Exclusion Mean? A mutual exclusion (mutex) is a program object that prevents
simultaneous access to a shared resource. This concept is used in concurrent programming with a
critical section, a piece of code in which processes or threads access a shared resource.

What are the advantages of mutual exclusion?

Advantages:
 Algorithm guarantees mutual exclusion by letting one process at a time into each critical region.
 It is also fair as requests are granted in the order in which they are received.
 No process ever waits forever so no starvation.
 What is the objective of mutual exclusion?
 Mutual exclusion is a property of concurrency control, which is instituted for the purpose of
preventing race conditions. It is the requirement that one thread of execution never enters its
critical section at the same time that another concurrent thread of execution enters its own
critical section.

Peterson's solution was proposed to resolve the critical section problem involving only two
processes. This solution guarantees that it provides mutual exclusion, bounded waiting, and
progress of the processes.

• Peterson’s Solution is a classical software based solution to the critical section problem.

• In Peterson’s solution, we have two shared variables:

(a) Boolean flag[i] :Initialized to FALSE, initially no one is interested in entering the critical
section