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

2 thoughts on “Implementing Peterson Algorithm with Python”

Leave a Reply to Ziru Wang Cancel reply

Your email address will not be published. Required fields are marked *