{"id":2730,"date":"2025-06-07T14:29:13","date_gmt":"2025-06-07T14:29:13","guid":{"rendered":"https:\/\/diznr.com\/?p=2730"},"modified":"2025-06-07T14:29:13","modified_gmt":"2025-06-07T14:29:13","slug":"lamports-mutual-exclusion-algorithm-lamport-logical-clock-program-c-in","status":"publish","type":"post","link":"https:\/\/www.reilsolar.com\/pdf\/lamports-mutual-exclusion-algorithm-lamport-logical-clock-program-c-in\/","title":{"rendered":"Lamports Mutual exclusion algorithm lamport logical clock program in c"},"content":{"rendered":"<p>Lamports Mutual exclusion algorithm lamport logical clock program in c<\/p>\n<p>[fvplayer id=&#8221;87&#8243;]<\/p>\n<p>Lamport\u2019s Mutual Exclusion Algorithm uses <strong>Lamport&#8217;s Logical Clocks<\/strong> to order events in a distributed system and ensure <strong>mutual exclusion<\/strong>. This algorithm ensures that only one process can access the critical section at a time in a distributed environment.<\/p>\n<p>Below is a <strong>simplified C implementation<\/strong> of Lamport\u2019s Mutual Exclusion Algorithm using <strong>Lamport Timestamps<\/strong>. It simulates multiple processes communicating using messages (REQUEST, REPLY, RELEASE) with logical clocks.<\/p>\n<hr \/>\n<h3>\u26a0\ufe0f Assumptions:<\/h3>\n<ul>\n<li>Processes are simulated as threads.<\/li>\n<li>Communication is simulated using shared memory structures (queues).<\/li>\n<li>Focus is on algorithm logic, not actual distributed systems or sockets.<\/li>\n<\/ul>\n<hr \/>\n<h3>\u2705 C Code: Lamport Mutual Exclusion with Logical Clocks<\/h3>\n<pre><code class=\"language-c\">#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n#include &lt;pthread.h&gt;\n#include &lt;unistd.h&gt;\n\n#define N 3 \/\/ number of processes\n#define REQUEST 0\n#define REPLY 1\n#define RELEASE 2\n\ntypedef struct {\n    int timestamp;\n    int process_id;\n    int type;\n} Message;\n\nint clock[N];\nint replies[N];\nint requesting[N];\nint in_cs = 0;\n\npthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;\n\nvoid send_message(int from, int to, Message msg);\nvoid broadcast_message(int from, Message msg);\nvoid receive_message(int to, Message msg);\n\nvoid increment_clock(int pid) {\n    clock[pid]++;\n}\n\nint compare_timestamp(Message a, Message b) {\n    if (a.timestamp == b.timestamp)\n        return a.process_id - b.process_id;\n    return a.timestamp - b.timestamp;\n}\n\nvoid *process_thread(void *arg) {\n    int pid = *(int *)arg;\n    sleep(pid); \/\/ stagger the start\n\n    \/\/ Request critical section\n    pthread_mutex_lock(&amp;lock);\n    increment_clock(pid);\n    requesting[pid] = 1;\n    Message req = {clock[pid], pid, REQUEST};\n    broadcast_message(pid, req);\n    pthread_mutex_unlock(&amp;lock);\n\n    \/\/ Wait for replies\n    while (replies[pid] &lt; N - 1) {\n        sleep(1);\n    }\n\n    \/\/ Enter critical section\n    pthread_mutex_lock(&amp;lock);\n    printf(\"Process %d entering critical section (clock=%d)\\n\", pid, clock[pid]);\n    in_cs++;\n    sleep(2); \/\/ simulate work in CS\n    printf(\"Process %d leaving critical section\\n\", pid);\n    in_cs--;\n    requesting[pid] = 0;\n\n    increment_clock(pid);\n    Message rel = {clock[pid], pid, RELEASE};\n    broadcast_message(pid, rel);\n    pthread_mutex_unlock(&amp;lock);\n\n    pthread_exit(NULL);\n}\n\n\/\/ Simulated communication between processes\nvoid send_message(int from, int to, Message msg) {\n    pthread_mutex_lock(&amp;lock);\n    \/\/ Synchronize clocks\n    clock[to] = (clock[to] &gt; msg.timestamp ? clock[to] : msg.timestamp) + 1;\n\n    switch (msg.type) {\n        case REQUEST:\n            if (!requesting[to] || compare_timestamp(msg, (Message){clock[to], to, REQUEST}) &lt; 0) {\n                Message reply = {clock[to], to, REPLY};\n                send_message(to, from, reply);\n            }\n            break;\n        case REPLY:\n            replies[from]++;\n            break;\n        case RELEASE:\n            \/\/ Do nothing, since this is a simplified simulation\n            break;\n    }\n    pthread_mutex_unlock(&amp;lock);\n}\n\nvoid broadcast_message(int from, Message msg) {\n    for (int i = 0; i &lt; N; i++) {\n        if (i != from) {\n            send_message(from, i, msg);\n        }\n    }\n}\n\nint main() {\n    pthread_t threads[N];\n    int ids[N];\n\n    for (int i = 0; i &lt; N; i++) {\n        clock[i] = 0;\n        replies[i] = 0;\n        requesting[i] = 0;\n    }\n\n    for (int i = 0; i &lt; N; i++) {\n        ids[i] = i;\n        pthread_create(&amp;threads[i], NULL, process_thread, &amp;ids[i]);\n    }\n\n    for (int i = 0; i &lt; N; i++) {\n        pthread_join(threads[i], NULL);\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n<hr \/>\n<h3>\ud83d\udd0d Explanation:<\/h3>\n<ul>\n<li>Each process is a thread with its own logical clock.<\/li>\n<li>When a process wants to enter the critical section:\n<ul>\n<li>It sends a REQUEST message to all other processes.<\/li>\n<li>It waits for REPLY messages from all other processes.<\/li>\n<\/ul>\n<\/li>\n<li>When it receives all replies, it enters the critical section.<\/li>\n<li>Upon exiting, it sends a RELEASE message to others.<\/li>\n<\/ul>\n<hr \/>\n<h3>\ud83d\udccc Notes:<\/h3>\n<ul>\n<li>This is a <strong>simulation<\/strong>, not a real distributed system.<\/li>\n<li>For true distributed behavior, inter-process communication (e.g., sockets, MPI) would be required.<\/li>\n<\/ul>\n<p>Would you like a version using actual inter-process communication (e.g., using sockets or MPI)?<\/p>\n<h3><a href=\"https:\/\/www.cs.unc.edu\/~anderson\/papers\/lamport.pdf\" target=\"_blank\" rel=\"noopener\">Lamports Mutual exclusion algorithm lamport logical clock program in c<\/a><\/h3>\n<h3 class=\"LC20lb MBeuO DKV0Md\"><a href=\"https:\/\/therenegadecoder.com\/wp-content\/uploads\/2019\/07\/osu-cse-6431-distributed-mutual-exclusion-part-2.pdf\" target=\"_blank\" rel=\"noopener\">Lamport&#8217;s Clock limitations<\/a><\/h3>\n","protected":false},"excerpt":{"rendered":"<p>Lamports Mutual exclusion algorithm lamport logical clock program in c [fvplayer id=&#8221;87&#8243;] Lamport\u2019s Mutual Exclusion Algorithm uses Lamport&#8217;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 [&hellip;]<\/p>\n","protected":false},"author":71,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[947],"tags":[],"class_list":["post-2730","post","type-post","status-publish","format-standard","hentry","category-c-notes"],"_links":{"self":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2730","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/users\/71"}],"replies":[{"embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/comments?post=2730"}],"version-history":[{"count":0,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/posts\/2730\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/media?parent=2730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/categories?post=2730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.reilsolar.com\/pdf\/wp-json\/wp\/v2\/tags?post=2730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}