Implementing Peterson Algorithm with Python

# 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. (Chinese: 实现互斥锁的并发)

Implementing Peterson algorithm is straightforward, here is the pseudocode in C style.

/* Globally Init */
int flag = {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;
}

while (true) {
enter_region(0);
// Critical Section
leave_region(0);
}

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 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 time

cs = 0
flag_0 = False
flag_1 = False
turn = 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

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.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