Peterson's Algorithm
PETERSON'S ALGORITHM
A Report on Software-Based Mutual Exclusion for Process Synchronization
Operating Systems – Process Synchronization
Page 1
Peterson's Algorithm
Table of Contents
TOC \h \o "1-2"
Page 2
Peterson's Algorithm
1. Introduction
Modern computer systems often execute multiple processes simultaneously. These
processes may need to access shared resources such as memory locations, files,
printers, databases, or network connections. When multiple processes attempt to
access the same resource at the same time, conflicts may occur, resulting in incorrect
outputs or data corruption.
To solve this problem, synchronization techniques are used. One of the most famous
synchronization algorithms is Peterson’s Algorithm, introduced by Gary L. Peterson in
1981. The algorithm provides a software solution to the Critical Section Problem for two
processes and guarantees mutual exclusion without requiring special hardware support.
Peterson’s Algorithm remains one of the most important concepts in Operating Systems
because it demonstrates how process synchronization can be achieved through
software alone.
2. Background of the Critical Section Problem
The Critical Section Problem arises when two or more processes share resources and
attempt to modify them simultaneously.
For example, consider a bank account with a balance of $1,000.
• Process A deposits $200.
• Process B withdraws $300.
If both operations occur simultaneously without synchronization, the final balance may
become incorrect due to overlapping operations.
This problem is known as a race condition and can lead to:
• Data inconsistency
• System crashes
• Corrupted files
• Incorrect calculations
The Critical Section Problem seeks to design protocols that allow safe access to shared
resources.
3. Objectives of Peterson's Algorithm
Peterson’s Algorithm was designed to achieve the following objectives:
1. Ensure mutual exclusion.
2. Prevent race conditions.
Page 3
Peterson's Algorithm
3. Guarantee fairness among processes.
4. Avoid deadlock.
5. Provide bounded waiting.
6. Allow processes to progress without unnecessary delays.
4. Key Concepts
4.1 Critical Section
A critical section is a portion of a program where shared resources are accessed.
Example:
balance = balance + 200;
If multiple processes execute this statement simultaneously, incorrect results may
occur.
4.2 Mutual Exclusion
Mutual exclusion guarantees that only one process enters the critical section at a time.
4.3 Race Condition
A race condition occurs when the system output depends on the order in which
processes execute.
4.4 Process Synchronization
Synchronization coordinates multiple processes to ensure correct execution and
consistency of shared data.
5. Structure of Peterson's Algorithm
Peterson’s Algorithm uses two shared variables.
5.1 Flag Array
bool flag[2];
The flag array records whether a process wants to enter the critical section.
• flag[0] = true → Process 0 wants to enter.
• flag[1] = true → Process 1 wants to enter.
5.2 Turn Variable
int turn;
Page 4
Peterson's Algorithm
The turn variable determines which process gets priority when both processes request
access simultaneously.
6. Working Principle of Peterson's Algorithm
The algorithm follows these steps:
1. A process indicates its intention to enter the critical section by setting its flag to
true.
2. It gives priority to the other process by updating the turn variable.
3. If the other process also wants to enter and has priority, the process waits.
4. Once the other process leaves the critical section, the waiting process proceeds.
5. Upon leaving, the process resets its flag to false.
This ensures that both processes cannot enter the critical section simultaneously.
7. Pseudocode Implementation
Process 0
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
Critical Section
flag[0] = false;
Process 1
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
Critical Section
flag[1] = false;
8. Diagrams and Flowcharts
Figure 1: Shared Resource Access
Shared Resource
|
-------------------------
| |
Process 0 Process 1
| |
Page 5
Peterson's Algorithm
-------------------------
|
Critical Section
Figure 2: Peterson's Algorithm Structure
Process 0 Process 1
| |
flag[0]=true flag[1]=true
| |
turn=1 turn=0
\ /
\ /
\ /
\ /
Check Conditions
|
v
Critical Section
|
v
Exit Section
Figure 3: Flowchart
Start
|
Set flag[i] = true
|
Set turn = j
|
Check:
flag[j] && turn == j ?
|
Yes
|
Wait
|
No
|
Enter Critical Section
|
Perform Operations
|
Exit Critical Section
|
Set flag[i] = false
|
End
9. Example Scenario
Suppose two processes share a printer.
Without Peterson's Algorithm
• Process A sends a print request.
• Process B sends another print request simultaneously.
• Print jobs become mixed.
Page 6
Peterson's Algorithm
With Peterson's Algorithm
• Process A enters the critical section first.
• Process B waits.
• After Process A finishes, Process B enters.
• Print jobs are executed correctly.
10. Requirements Satisfied by Peterson's Algorithm
10.1 Mutual Exclusion
Only one process can execute in the critical section at a time.
10.2 Progress
If no process is in the critical section, one of the waiting processes can enter.
10.3 Bounded Waiting
A process will not wait forever before entering the critical section.
11. Advantages
1. Simple and easy to understand.
2. Requires no special hardware.
3. Prevents race conditions.
4. Guarantees mutual exclusion.
5. Ensures fairness between processes.
6. Useful for learning synchronization concepts.
12. Disadvantages
1. Limited to two processes only.
2. Uses busy waiting.
3. Consumes CPU cycles during waiting.
4. Inefficient for modern multiprocessor systems.
5. Rarely used in real-world applications today.
13. Applications
Peterson’s Algorithm is used in:
Page 7
Peterson's Algorithm
• Operating Systems courses
• Computer Architecture studies
• Concurrency research
• Synchronization demonstrations
• Academic simulations
14. Comparison with Other Synchronization Techniques
Number of
Technique Busy Waiting Practical Use
Processes
Peterson's Algorithm 2 Yes Educational
Mutex Locks Many Sometimes High
Semaphores Many No Very High
Monitors Many No High
Specialized
Spinlocks Many Yes
Systems
Modern operating systems generally prefer mutexes, semaphores, and monitors
because they are more scalable and efficient.
15. Challenges and Limitations
Although Peterson’s Algorithm is theoretically correct, it has practical limitations:
• Difficult to scale beyond two processes.
• Performs poorly in multicore processors.
• Relies on strict memory ordering.
• Busy waiting wastes processing power.
Because of these limitations, modern systems use advanced synchronization
mechanisms.
16. Conclusion
Peterson’s Algorithm is a landmark software solution to the Critical Section Problem. It
demonstrates how synchronization can be achieved using shared variables without
hardware assistance. The algorithm successfully guarantees mutual exclusion,
progress, and bounded waiting for two processes.
Page 8
Peterson's Algorithm
Although it is rarely used in modern operating systems, it remains an essential concept
in computer science education and provides the foundation for understanding more
advanced synchronization techniques such as semaphores, mutexes, and monitors.
17. References
1. Peterson, G. L. (1981). Myths About the Mutual Exclusion Problem. Information
Processing Letters, 12(3), 115–116.
2. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts
(10th Edition). Wiley.
3. Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th Edition).
Pearson.
4. Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th
Edition). Pearson.
5. Deitel, H. M. (2012). Operating Systems (3rd Edition). Pearson Education.
6. Elmasri, R., & Navathe, S. (2017). Fundamentals of Database Systems (7th
Edition). Pearson.
Page 9