Implementing Peterson Algorithm with Python
Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict.
Implementing Peterson algorithm is straightforward, here is the pseudocode in C style.
/* Globally Init */
int flag[2] = {false, false};
int turn = 0;
void enter_region (int process) {
flag[1 - process] = true;
turn = process;
while (flag[process] && turn == process);
}
void leave_region() {
flag[1 - process] = false;
}
/* thread-0 */
while (true) {
enter_region(0);
// Critical Section
leave_region(0);
}
/* thread-1 */
while (true) {
enter_region(1);
// Critical Section
leave_region(1);
}
We can see that Peterson algorithm use a busy waiting approach to solve. Controlled by two variables flag
and turn
. Now let's see how this method works. In the beginning, no process was in the critical section, now thread-0 calls enter_region
. It expresses that it wants to enter the critical section by setting the flag
to 1 and setting turn
to 0. Since thread-1 does not want to enter the critical section, enter_region
returns soon. If thread-1 now calls enter_region
, thread-1 will be suspended here until flag[1]
becomes false
, which will only happen when thread-0 calls leave_region
to exit the critical section.
Now let's coding it in Python.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import threading
import time
cs = 0
flag_0 = False
flag_1 = False
turn = 0
def thread_0():
global cs, flag_0, flag_1, turn
flag_0 = True
turn = 1
while (flag_1 and turn == 1):
continue
for i in range(10):
cs += 1
print("Thread 0: cs =", cs)
time.sleep(0.1)
flag_0 = False
def thread_1():
global cs, flag_0, flag_1, turn
flag_1 = True
turn = 0
while (flag_0 and turn == 0):
continue
for i in range(10):
cs += 1000
print("Thread 1: cs =", cs)
time.sleep(0.1)
flag_1 = False
if __name__ == "__main__":
t0 = threading.Thread(target=thread_0)
t1 = threading.Thread(target=thread_1)
t0.start()
t1.start()
and when we run it, the console output like this. Then we implement the Peterson algorithm successfully.
❯ py peterson.py
Thread 0: cs = 1
Thread 0: cs = 2
Thread 0: cs = 3
Thread 0: cs = 4
Thread 0: cs = 5
Thread 0: cs = 6
Thread 0: cs = 7
Thread 0: cs = 8
Thread 0: cs = 9
Thread 0: cs = 10
Thread 1: cs = 1010
Thread 1: cs = 2010
Thread 1: cs = 3010
Thread 1: cs = 4010
Thread 1: cs = 5010
Thread 1: cs = 6010
Thread 1: cs = 7010
Thread 1: cs = 8010
Thread 1: cs = 9010
Thread 1: cs = 10010