Lamports Mutual exclusion algorithm lamport logical clock program in c

Lamports Mutual exclusion algorithm lamport logical clock program in c

Lamport’s Mutual Exclusion Algorithm uses Lamport’s Logical Clocks to order events in a distributed system and ensure mutual exclusion. This algorithm ensures that only one process can access the critical section at a time in a distributed environment.

Below is a simplified C implementation of Lamport’s Mutual Exclusion Algorithm using Lamport Timestamps. It simulates multiple processes communicating using messages (REQUEST, REPLY, RELEASE) with logical clocks.

Assumptions:

• Processes are simulated as threads.
• Communication is simulated using shared memory structures (queues).
• Focus is on algorithm logic, not actual distributed systems or sockets.

C Code: Lamport Mutual Exclusion with Logical Clocks

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

#define N 3 // number of processes
#define REQUEST 0
#define REPLY 1
#define RELEASE 2

typedef struct {
    int timestamp;
    int process_id;
    int type;
} Message;

int clock[N];
int replies[N];
int requesting[N];
int in_cs = 0;

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void send_message(int from, int to, Message msg);
void broadcast_message(int from, Message msg);
void receive_message(int to, Message msg);

void increment_clock(int pid) {
    clock[pid]++;
}

int compare_timestamp(Message a, Message b) {
    if (a.timestamp == b.timestamp)
        return a.process_id - b.process_id;
    return a.timestamp - b.timestamp;
}

void *process_thread(void *arg) {
    int pid = *(int *)arg;
    sleep(pid); // stagger the start

    // Request critical section
    pthread_mutex_lock(&lock);
    increment_clock(pid);
    requesting[pid] = 1;
    Message req = {clock[pid], pid, REQUEST};
    broadcast_message(pid, req);
    pthread_mutex_unlock(&lock);

    // Wait for replies
    while (replies[pid] < N - 1) {
        sleep(1);
    }

    // Enter critical section
    pthread_mutex_lock(&lock);
    printf("Process %d entering critical section (clock=%d)\n", pid, clock[pid]);
    in_cs++;
    sleep(2); // simulate work in CS
    printf("Process %d leaving critical section\n", pid);
    in_cs--;
    requesting[pid] = 0;

    increment_clock(pid);
    Message rel = {clock[pid], pid, RELEASE};
    broadcast_message(pid, rel);
    pthread_mutex_unlock(&lock);

    pthread_exit(NULL);
}

// Simulated communication between processes
void send_message(int from, int to, Message msg) {
    pthread_mutex_lock(&lock);
    // Synchronize clocks
    clock[to] = (clock[to] > msg.timestamp ? clock[to] : msg.timestamp) + 1;

    switch (msg.type) {
        case REQUEST:
            if (!requesting[to] || compare_timestamp(msg, (Message){clock[to], to, REQUEST}) < 0) {
                Message reply = {clock[to], to, REPLY};
                send_message(to, from, reply);
            }
            break;
        case REPLY:
            replies[from]++;
            break;
        case RELEASE:
            // Do nothing, since this is a simplified simulation
            break;
    }
    pthread_mutex_unlock(&lock);
}

void broadcast_message(int from, Message msg) {
    for (int i = 0; i < N; i++) {
        if (i != from) {
            send_message(from, i, msg);
        }
    }
}

int main() {
    pthread_t threads[N];
    int ids[N];

    for (int i = 0; i < N; i++) {
        clock[i] = 0;
        replies[i] = 0;
        requesting[i] = 0;
    }

    for (int i = 0; i < N; i++) {
        ids[i] = i;
        pthread_create(&threads[i], NULL, process_thread, &ids[i]);
    }

    for (int i = 0; i < N; i++) {
        pthread_join(threads[i], NULL);
    }

    return 0;
}

Explanation:

• Each process is a thread with its own logical clock.
• When a process wants to enter the critical section:
  • It sends a REQUEST message to all other processes.
  • It waits for REPLY messages from all other processes.
• When it receives all replies, it enters the critical section.
• Upon exiting, it sends a RELEASE message to others.

Notes:

• This is a simulation, not a real distributed system.
• For true distributed behavior, inter-process communication (e.g., sockets, MPI) would be required.

Would you like a version using actual inter-process communication (e.g., using sockets or MPI)?

Lamports Mutual exclusion algorithm lamport logical clock program in c

Lamport’s Clock limitations