Go back
Peterson's Algorithm: The Polite Programmer’s Guide to IPC
October 3rd, 2025 8:09 AM
inter-process communications
Image Courtesy:Pixabay
Believe it or not the first section of this blog was something that was added in the last.
So let's just take a quick glance over how processor works.
A processor fetches instructions, executes them, and writes the results back to the specified locations. A script you write is essentially just a sequence of instructions that the CPU runs one by one. However, modern computers can run multiple processes in truly-parallel or in pseudo-parallel (concurrent) fashion. The distinction would go a little beyond the scope of this blog, so we’ll skip it here—but the key takeaway is this: because of parallelism, a process’s execution speed won’t be uniform and probably not even reproducible if the same processes are run again.
Now, sometimes processes need to communicate or share data. Consider two processes accessing the same variable and modifying it. Process A might read the variable’s value, but before it finishes computing, process B could read and mutate that same variable. Suddenly, A is working with an outdated value, and if your program relies on it, the results can be inconsistent—or downright disastrous—especially in large systems.
This is a type of software bug caused by a race condition. The example we just discussed is called time-of-check to time-of-use (TOCTOU, TOCTTOU, or TOC/TOU). As the name suggests, it involves checking the state of a system component and then acting on that check. If the system changes between the check and the action, unexpected or incorrect behavior can occur.
Believe it or not, at the 2023 Pwn2Own competition in Vancouver, a team of hackers managed to exploit this very bug to compromise the gateway of a fully updated Tesla Model 3. 1
1#define FALSE 0
2#define TRUE 1
3#define N 2
4
5int turn; int interested[N];
6
7void enter_region(int process)
8{
9 int other;
10 other = 1− process;
11 interested[process] = TRUE;
12 tur n = process;
13 while (turn == process && interested[other] == TRUE) ;
14}
15
16void leave_region(int process) {
17 interested[process] = FALSE;
18}
19Stumbled accross this piece in the classic Modern Operating Systems (actually a couple of years ago, not recently). And back then it had me scratching my head, pondering it's meaning and I couldn't find a good enough explanation that helped me build an intuitive understanding of it.
Here’s my attempt, for any curious minds out there.
The first two lines in the enter_region function are pretty easy to wrap your head around, they simply calculate the id of the other process. It’s worth noting that, although this algorithm is designed for 2 processes, extending it to N processes wouldn’t be too difficult.
This is a fairly neat solution developed by Gary L. Peterson in 1981, and I must say, despite the simplicity of its implementation, I’m always astounded at how hard it was for me to wrap my head around it—let alone invent it.
This one almost pulled a KMP algorithm. Well, not really. KMP algorithm is it's own tier lol.
The idea is simple. Each process, during its turn assigned by the CPU, gets a 'voice' to express its desire to enter the critical region. Oh before we dive furthe into this, if there’s one thing I could change about this code, it would be the variable name turn. Honestly, something like i_am_so_nice_what_can_i_say_i_will_wait_but_hey_you_better_not_skip_me_once_you_are_done would be more… descriptive. Just sayin'.
It’s like taking turns for the toilet—and hey, it’s 2025, toilets are basically a luxury now. You signal your interest and stand in line… and just then, a two-year-old bursts in, unable to hold it. You sigh, heroically set i_am_so_nice_what_can_i_say_i_will_wait_but_hey_you_better_not_skip_me_once_you_are_done to true, and let him go first. But wait—polite reminder: it was my turn! I’m just generously lending it to you because, well… i_am_so_nice_what_can_i_say_i_will_wait_but_hey_you_better_not_skip_me_once_you_are_done.
Well, I’m interested, but since I’m so nice, I’ll wait— and the while condition beautifully encapsulates that idea.
So, yeah it is my turn and you want to use bath so go, but as soon as you are done i.e., you are not interested in the toilet anymore you better come out and let me go in.
But again: as soon as you’re done—that is, as soon as you’re no longer interested in the toilet—you better come out and express your lack of desire in the leave_region function, so I can finally take my turn back kiddo.
After all, the while loop exists to make me patient… not to let you hog the bathroom forever!
Two Processes, One Toilet, Zero Fights: A Concurrency Story.
The brilliance here lies in the simplicity: with just two flags (interested) and one courtesy variable (turn).
It ensures:
Precursors to Peterson's Solutions like Disabling Interrupts, Simple Locks or Strict Alteration had those issues. Want me to expand on these? Comment section for ya mah' folks, just let me know yaknow?
Peterson’s solution is like a masterclass in humility:
That’s it. Two lines of code, and humanity’s politeness distilled into an algorithm.
Yes, modern computers no longer execute instructions in lockstep. Processors are like caffeinated squirrels, jumping ahead, reordering instructions, and doing a million things at once.
But does that stop me from marveling at Peterson’s Algorithm?
Well, clearly not.
Of course, there are better solutions out there, ones that leverage the hardware’s ability to make certain instructions atomic and eliminate the issue Priority Inversion Problem. What's that? That’s something for another time!
Copyright © 2026 Karunika