Implementing Peterson’s Algorithm for Mutual Exclusion in C Language

After studying the section on process mutual exclusion, I thought I would try to implement it using user-level multithreading in C, which led to this article.

Complete Code

Peterson’s algorithm combines the single flag method and the double flag method to achieve true mutual exclusion for accessing critical resources (without violating two important principles: allowing entry when free, and waiting when busy).

To verify correctness, I also wrote comparative code, which readers can uncomment for debugging. The code can be run directly.

The code is as follows:

// Created by Linzepore on 2025/5/1.
#include "iostream"
#include "pthread.h"
using namespace std;
bool flag[2];
int turn;
typedef struct {
    int arg1;
    int arg2;
} thread_arg;
void *sharing_resource(void *arg) {
    int *now = (int *) arg;
    cout << "[Thread " << *now << "] accessing critical section" << endl;
    for (int i = 0; i < 3000; ++i) {
        cout << *now << " ";
    }
    cout << endl;
    return nullptr;
}
void *twait(void *arg) {
    thread_arg *args = (thread_arg *) arg;
    flag[args->arg1] = true;
    turn = args->arg2;
    while (flag[args->arg2] && turn == args->arg2) {
        cout << "[Thread " << args->arg1 << "] is waiting...";
    };
    sharing_resource(&args->arg1);
    flag[args->arg1] = false;
    return nullptr;
}
int main() {
    /*pthread_t t1, t2;
    pthread_create(&t1, NULL, twait, new thread_arg{0, 1});
    pthread_create(&t2, NULL, twait, new thread_arg{1, 0});
    int k = 0;
    while (k++ < 10000) {
        pthread_join(t1, nullptr);
        pthread_join(t2, nullptr);
        return 0;
    }*/
    // Compare with direct race access
    /*pthread_t t3,t4;
    pthread_create(&t3,NULL,sharing_resource,new int{3});
    pthread_create(&t4,NULL,sharing_resource,new int{4});
    int k = 0;
    while(k++ < 10000) {
        pthread_join(t3, nullptr);
        pthread_join(t4, nullptr);
        return 0;
    }*/
}

Next is the implementation idea. It is actually quite simple and is basically consistent with the ideas in the reference book.

Algorithm Concept

For thread t1 (here threads are used to simulate processes, so there may be mixed references to processes and threads in this article):

flag[0] = true;①
turn = 1;②
while(flag[1] && turn == 1);③
//...critical section
flag[0] = false;

For thread t2 (similarly simulating processes):

flag[1] = true;④
turn = 0;⑤
while(flag[0] && turn == 0);⑥
//...critical section
flag[1] = false;

By combining the steps one through six, we can see that mutual exclusion is achieved, allowing for exclusive access to the critical section.

Implementation Process

Defining the Critical Section

Regarding the implementation of the code, the critical section is represented by a shared function. To comply with the parameter requirements of <span>pthread_create</span>, the input and output parameters are changed to pointer form:

void *sharing_resource(void *arg) {
    int *now = (int *) arg;
    cout << "[Thread " << *now << "] accessing critical section" << endl;
    for (int i = 0; i < 3000; ++i) {
        cout << *now << " ";
    }
    cout << endl;
    return nullptr;
}

Defining Shared Variables

Clearly, shared variables for requesting and yielding access are essential:

bool flag[2];
int turn;

Defining Thread Functions

Here, the parameters are also changed to pointer form to meet the requirements of <span>pthread_create</span>. The first parameter is the name of the current thread, and the second parameter is the other thread’s name. The function mainly checks if any thread is accessing the critical section; if so, it spins in wait, otherwise it exits the loop.

void *twait(void *arg) {
    thread_arg *args = (thread_arg *) arg;
    flag[args->arg1] = true;
    turn = args->arg2;
    while (flag[args->arg2] && turn == args->arg2) {
        cout << "[Thread " << args->arg1 << "] is waiting...";
    };
    sharing_resource(&args->arg1);
    flag[args->arg1] = false;
    return nullptr;
}

Defining the Main Function

In the main function, we use functions from the <pthread.h> library to create two threads, passing them the thread names and functions along with their parameters, simulating continuously running threads. Conversely, in the counterexample, the function passed is directly the critical section, simulating direct competition.

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, twait, new thread_arg{0, 1});
    pthread_create(&t2, NULL, twait, new thread_arg{1, 0});
    int k = 0;
    while (k++ < 10000) {
        pthread_join(t1, nullptr);
        pthread_join(t2, nullptr);
        return 0;
    }
    // Compare with direct race access
    /*pthread_t t3,t4;
    pthread_create(&t3,NULL,sharing_resource,new int{3});
    pthread_create(&t4,NULL,sharing_resource,new int{4});
    int k = 0;
    while(k++ < 10000) {
        pthread_join(t3, nullptr);
        pthread_join(t4, nullptr);
        return 0;
    }*/
}

Comparing Results

In thread competition, when they access resources, it may happen that the previous thread has not completed, and due to scheduling reasons, another thread gains execution rights, leading to both threads accessing the same critical section, resulting in a race condition:

When we use the algorithm, this situation does not occur. The thread, upon discovering that another thread is accessing the critical section, will actively yield and wait until it is finished, but will still occupy its time slice. This means that thread 0 will wait for thread 1 to finish before it can access the critical section.

#Technical Sharing #408 Notes