Race condition আর critical section — Peterson-এর সমাধান

১ · এক লাইনের কোডে লুকানো তিন ধাপ — producer, consumer আর count

পর্ব ১৫-এ দুটি থ্রেড একই counter-এ counter++ করে লাখ লাখ যোগ হারিয়েছিল, আর mutex দিয়ে তা সারানো হয়েছিল। এই পর্বে প্রশ্নটি আরও মৌলিক: mutex নিজে কীভাবে বানানো যায়? কোন নিয়ম মানলে একটি সমাধানকে “সঠিক” বলা যায়, আর সেটি প্রমাণ করা যায় কীভাবে? শুরু করি পাঠ্যবইয়ের পরিচিত উদাহরণ দিয়ে।

একটি producer-consumer ব্যবস্থা ভাবুন। Producer থ্রেড জিনিস বানিয়ে একটি shared buffer-এ রাখে, consumer সেখান থেকে তুলে নেয়। Buffer-এ এখন কয়টি জিনিস আছে, তার হিসাব রাখে একটি shared ভ্যারিয়েবল count:

/* producer */                          /* consumer */
while (true) {                          while (true) {
    item = produce();                       while (count == 0) ;   /* empty */
    while (count == BUF) ;  /* full */      item = buffer[out];
    buffer[in] = item;                      out = (out + 1) % BUF;
    in = (in + 1) % BUF;                    count--;
    count++;                                consume(item);
}                                       }

আলাদাভাবে দুটিই ঠিক। কিন্তু একসাথে চললে বিপদ। count++ C-তে এক লাইন, CPU-র কাছে তিনটি machine instruction:

count++ :  register1 = count            count-- :  register2 = count
           register1 = register1 + 1               register2 = register2 - 1
           count = register1                        count = register2

প্রতিটি থ্রেডের নিজের register আছে (এক CPU-তে চললে context switch-এর সময় সেগুলো আলাদা করে সংরক্ষিত হয়, পর্ব ৯)। ধরুন count = 5, আর producer একটি জিনিস রাখল, consumer একটি তুলল — ফল হওয়ার কথা আবার 5. কিন্তু ছয়টি instruction যেকোনো ক্রমে মিশতে পারে। এই মেশানো ক্রমকে বলে interleaving. নিচে ধাপে ধাপে দেখুন:

1// Producer: count++2register1 = count3register1 = register1 + 14count = register15// Consumer: count--6register2 = count7register2 = register2 - 18count = register2

এমন অবস্থাকে বলে race condition: একাধিক প্রসেস বা থ্রেড একই ডেটা একসাথে ছোঁয় আর ব্যবহার করে, আর ফল নির্ভর করে তারা ঠিক কোন ক্রমে চলল তার ওপর. নামটি এসেছে দৌড় থেকে — কে আগে পৌঁছাবে, তার ওপর ফল। পর্ব ১৫-এ দেখা data race হলো এর সবচেয়ে সাধারণ কারণ, তবে দুটি এক জিনিস নয়:

সমাধানের মূল ভাবনা একটিই: count++-এর তিন ধাপ আর count---এর তিন ধাপ যেন কখনো না মেশে — একজন শুরু করলে অন্যজন অপেক্ষা করবে, যতক্ষণ না প্রথমজনের তিন ধাপ শেষ হয়। বাকি পর্বটি এই “অপেক্ষা”কে কীভাবে নির্ভুলভাবে বানানো যায়, তার গল্প।

২ · Critical-section সমস্যা — চার অংশ আর তিনটি শর্ত

কোডের যে অংশে shared ডেটা ছোঁয়া হয় (উপরের count++), তার নাম critical section. ১৯৬০-এর দশকে Edsger Dijkstra সমস্যাটিকে একটি সাধারণ কাঠামোয় বাঁধেন, যাকে আজ বলা হয় critical-section problem. n টি প্রসেস (P₀ … P_n−1) প্রত্যেকে চিরকাল এই চক্রে ঘোরে:

while (true) {
    entry section        /* ask permission: "may I enter?"           */
        critical section /* touch the shared data                     */
    exit section         /* announce: "I am out"                      */
        remainder section/* everything else; may run as long as it likes */
}

Entry section অনুমতি চায়, exit section জানিয়ে দেয় কাজ শেষ, আর remainder section বাকি সব কাজ — যেখানে প্রসেস যতক্ষণ খুশি থাকতে পারে, এমনকি চিরকাল। সমস্যাটি হলো entry আর exit section এমনভাবে লেখা, যাতে নিচের তিনটি শর্ত পূরণ হয়।

তিনটি শর্তের সঙ্গে চারটি অনুমানও সংজ্ঞার অংশ — পরীক্ষায় এগুলো লিখতে ভুলবেন না:

• প্রতিটি প্রসেস শূন্য নয় এমন গতিতে চলে — অর্থাৎ যে প্রসেস entry, critical বা exit section-এ আছে, সে একসময় পরের ধাপে যাবে; critical section-এর ভেতর চিরকাল আটকে থাকবে না।
• প্রসেসগুলোর আপেক্ষিক গতি নিয়ে কোনো অনুমান নেই — একজন আরেকজনের চেয়ে হাজার গুণ ধীর হতে পারে, বা যেকোনো মুহূর্তে থেমে থাকতে পারে।
• CPU-র সংখ্যা নিয়েও কোনো অনুমান নেই — সমাধান এক core-এ পালা করে চলা আর বহু core-এ সত্যিকারের একসাথে চলা, দুই ক্ষেত্রেই সঠিক হতে হবে।
• মৌলিক machine instruction (একটি load বা একটি store) অবিভাজ্য — একটি শব্দ পড়া বা লেখা মাঝপথে ভাঙে না। (এর বাইরে কোনো বিশেষ hardware instruction ধরা হয় না; সেগুলো পর্ব ২৩-এ।)

শর্ত তিনটি দুই জাতের। Mutual exclusion একটি safety property — “খারাপ কিছু কখনো ঘটবে না”; ভাঙলে একটি নির্দিষ্ট মুহূর্ত দেখানো যায় যখন দুজনই ভেতরে। Progress আর bounded waiting liveness property — “ভালো কিছু একসময় ঘটবেই”; ভাঙা দেখাতে হলে একটি অসীম ক্রম দেখাতে হয়, যেখানে কেউ চিরকাল আটকে থাকে। লক্ষ করুন, progress থাকলেও starvation হতে পারে (সবসময় কেউ না কেউ ঢুকছে, কিন্তু একই জন বারবার বাদ পড়ছে) — তাই bounded waiting আলাদা শর্ত।

৩ · Kernel-এর ভেতরেও race — preemptive আর non-preemptive kernel

Race শুধু আপনার প্রোগ্রামের সমস্যা নয়; kernel নিজেই সবচেয়ে বড় concurrent প্রোগ্রাম। খোলা ফাইলের তালিকা, মেমরি বরাদ্দের হিসাব, প্রসেসের তালিকা, interrupt-এর ডেটা — সব shared. পাঠ্যবইয়ের একটি উদাহরণ: দুটি প্রসেস প্রায় একসাথে fork() ডাকল (পর্ব ১০), আর kernel পরের খালি PID রাখে একটি ভ্যারিয়েবল next_pid-এ:

Kernel-এর নকশা এখানে দুই ভাগে পড়ে। Non-preemptive kernel-এ একটি প্রসেস kernel mode-এ চলার সময় তাকে জোর করে সরানো হয় না — যতক্ষণ না সে kernel থেকে বেরোয়, নিজে block হয়, বা স্বেচ্ছায় CPU ছাড়ে। এক CPU-র মেশিনে তাই kernel-এর ডেটায় প্রসেসে-প্রসেসে race প্রায় হয় না (interrupt handler-এর সঙ্গে race তবু থাকে)। Preemptive kernel-এ kernel mode-এ চলা প্রসেসকেও মাঝপথে সরিয়ে আরেকজনকে চালানো যায় (preemption). এটি নকশায় কঠিন — প্রতিটি shared ডেটা রক্ষা করতে হয় — কিন্তু সাড়া দ্রুত হয়, আর real-time কাজের জন্য প্রায় অপরিহার্য: একটি ধীর system call পুরো সিস্টেম আটকে রাখতে পারে না।

পুরোনো Unix আর Linux 2.4 পর্যন্ত kernel মূলত non-preemptive ছিল; Linux 2.6 (২০০৩) থেকে kernel preemption একটি কনফিগারেশন-বিকল্প, আর Windows NT-ধারার kernel শুরু থেকেই preemptive. কিন্তু খেয়াল করুন: multicore মেশিনে non-preemptive হওয়া কোনো রক্ষা নয় — দুটি core একই মুহূর্তে kernel-এর ভেতর চলতে পারে। তাই আধুনিক সব kernel-এ shared ডেটার জন্য lock লাগেই।

Interrupt বন্ধ করা — এক CPU-র সহজ সমাধান

এক CPU-তে একটি প্রসেস থেকে আরেকটিতে যাওয়া ঘটে মূলত interrupt-এর কারণে — timer interrupt-এ scheduler জাগে (পর্ব ৯)। তাহলে সবচেয়ে সরল সমাধান: critical section-এর আগে interrupt বন্ধ, পরে চালু। x86-এ এর instruction cli আর sti; Linux kernel-এ local_irq_save() আর local_irq_restore(); Windows kernel-এ একই কাজ হয় IRQL বাড়িয়ে।

unsigned long flags;
local_irq_save(flags);      /* this CPU: no interrupts, so no preemption */
pid = next_pid;             /* critical section: short!                  */
next_pid = pid + 1;
local_irq_restore(flags);   /* interrupts back to how they were          */

এক CPU-র kernel-এ ছোট critical section-এর জন্য এটি সত্যিই কাজ করে, কারণ interrupt না এলে কেউ CPU কাড়তে পারে না। কিন্তু তিনটি কারণে এটি সাধারণ সমাধান নয়:

1. Multiprocessor-এ অকেজো: cli শুধু নিজের CPU-র interrupt বন্ধ করে। অন্য core-গুলো তখনো চলছে, আর তারাও একই next_pid পড়তে পারে। সব CPU-কে বার্তা পাঠিয়ে সবার interrupt বন্ধ করা যায়, কিন্তু তা ধীর, আর প্রতিবার critical section-এ ঢুকতে পুরো মেশিন থামানো অসম্ভব রকম ব্যয়বহুল।
2. User প্রোগ্রামের জন্য নিষিদ্ধ: cli একটি privileged instruction. সাধারণ প্রোগ্রাম চালালে CPU trap করে, আর Linux প্রসেসটিকে সাধারণত SIGSEGV দিয়ে বন্ধ করে। অনুমতি থাকলেও বিপদ: একটি বাগওয়ালা প্রোগ্রাম interrupt বন্ধ করে অসীম লুপে পড়লে পুরো কম্পিউটার জমে যেত।
3. সময়ের ক্ষতি: Interrupt বন্ধ থাকলে কি-বোর্ড, নেটওয়ার্ক, ডিস্কের সংকেত দেরিতে সাড়া পায়, আর interrupt latency বাড়ে। তাই kernel এটি করে খুব ছোট অংশে, আর multicore-এ সাধারণত একটি spinlock-এর সঙ্গে মিলিয়ে (spin_lock_irqsave, পর্ব ২৩)।

তাহলে প্রশ্ন দাঁড়াল: শুধু সাধারণ load আর store দিয়ে, কোনো বিশেষ hardware সাহায্য ছাড়া, user প্রোগ্রাম কি নিজেরাই mutual exclusion বানাতে পারে — যেকোনো সংখ্যক CPU-তে? উত্তর “হ্যাঁ”, কিন্তু পথটি ভুলে ভরা।

৪ · সফটওয়্যারের ব্যর্থ চেষ্টা — একটি turn আর দুটি flag

দুটি প্রসেস P₀ আর P₁ নিয়ে শুরু করি। লেখার সুবিধায় P_i নিজে, আর P_j অন্যজন (j = 1 − i). Shared ভ্যারিয়েবল ছাড়া এদের মধ্যে যোগাযোগের কোনো পথ নেই।

চেষ্টা ১ — একটি shared turn: পালা করে

int turn = 0;                 /* shared: whose turn is it? */

/* process i */
while (true) {
    while (turn != i) ;       /* entry: wait for my turn            */
    /* critical section */
    turn = j;                 /* exit: give the turn to the other   */
    /* remainder section */
}

Mutual exclusion ঠিক আছে: turn একসময়ে একটিই মান ধরে — 0 বা 1 — আর P_i ঢোকে কেবল turn == i হলে, এবং ভেতরে থাকার সময় কেউ turn বদলায় না (বদলায় শুধু exit). তাই দুজন একসাথে ভেতরে থাকতে পারে না। কিন্তু এই কোড প্রসেসগুলোকে কঠোরভাবে পালা করতে বাধ্য করে — P₀, P₁, P₀, P₁ … একে বলে strict alternation, আর এর দাম progress:

1int turn = 0;          // shared2while (turn != i) ;    // entry3/* critical section */4turn = j;              // exit5/* remainder section */

চেষ্টা ২ — দুটি flag: “আমি ঢুকতে চাই”

সমস্যা ছিল এই যে turn জানে না কে আসলে ঢুকতে চায়। তাই প্রতিটি প্রসেসের জন্য একটি flag: flag[i] = true মানে “P_i ঢুকতে চায় বা ভেতরে আছে”। দুটি স্বাভাবিক ক্রম আছে, আর দুটিই ভুল — দুই ভিন্ন ভাবে।

bool flag[2] = {false, false};

while (flag[j]) ;         /* wait while the other wants in */
flag[i] = true;           /* now I am in                    */
/* critical section */
flag[i] = false;

bool flag[2] = {false, false};

flag[i] = true;           /* I want in                      */
while (flag[j]) ;         /* wait while the other wants in  */
/* critical section */
flag[i] = false;

দুটি চেষ্টা থেকে শিক্ষা: শুধু turn জানে “কার পালা”, কিন্তু জানে না “কে চায়”; শুধু flag জানে “কে চায়”, কিন্তু টাই ভাঙতে পারে না। সঠিক সমাধানের জন্য দুটিই লাগবে।

flag[i] = true;
while (flag[j]) {             /* the other also wants in            */
    if (turn == j) {          /* and it is the other's turn:        */
        flag[i] = false;      /*   step back ...                    */
        while (turn == j) ;   /*   ... wait for my turn ...         */
        flag[i] = true;       /*   ... then try again               */
    }
}
/* critical section */
turn = j;                     /* exit: give priority to the other   */
flag[i] = false;

এটি সঠিক, কিন্তু নেস্টেড লুপের কারণে বোঝা আর প্রমাণ করা কঠিন। প্রায় দুই দশক পরে একটি অনেক ছোট সমাধান আসে।

৫ · Peterson-এর সমাধান (১৯৮১)

১৯৮১ সালে Gary L. Peterson Information Processing Letters-এ একটি ছোট প্রবন্ধ প্রকাশ করেন — “Myths About the Mutual Exclusion Problem”. তাঁর সমাধানে flag আর turn দুটিই আছে, কিন্তু turn-এর ভূমিকা উল্টো: যে ঢুকতে চায়, সে নিজের flag তুলে turn দিয়ে দেয় অন্যজনকে — “আমি চাই, তবে আপনি আগে যান”। দুজন একসাথে ভদ্রতা দেখালে, যার ভদ্রতা পরে লেখা হলো সে-ই অপেক্ষা করে।

bool flag[2] = {false, false};   /* shared */
int  turn;                        /* shared: 0 or 1 */

/* process i  (j = 1 - i) */
while (true) {
    flag[i] = true;               /* 1. I want to enter       */
    turn = j;                     /* 2. but you may go first  */
    while (flag[j] && turn == j)  /* 3. wait only if you want */
        ;                         /*    AND it is your turn   */
    /* critical section */
    flag[i] = false;              /* 4. exit: I no longer want */
    /* remainder section */
}

Entry section-এর লুপে প্রসেস কিছুই করে না, শুধু বারবার শর্ত দেখে — একে বলে busy waiting (spinning). এটি CPU খরচ করে; পর্ব ২৪-এ দেখবেন কীভাবে অপেক্ষারত প্রসেসকে ঘুম পাড়ানো যায়। এবার দেখি দুজন একেবারে একসাথে চাইলে কী হয়:

1flag[i] = true;               // I want in2turn = j;                     // after you3while (flag[j] && turn == j) ;4/* critical section */5flag[i] = false;              // exit6/* remainder section */

প্রমাণ — তিনটি শর্তই কেন পূরণ হয়

প্রমাণে ধরে নেওয়া হচ্ছে, প্রতিটি load আর store অবিভাজ্য আর সব প্রসেস সব লেখা একই ক্রমে দেখে (sequential consistency). অংশ ৭-এ দেখবেন, এই অনুমানটিই আধুনিক CPU-তে ভাঙে।

(১) Mutual exclusion. বিপরীতটি ধরি: কোনো মুহূর্ত t-তে P₀ আর P₁ দুজনই critical section-এ। তাহলে t-তে flag[0] = flag[1] = true, কারণ প্রত্যেকে ঢোকার আগে নিজের flag তুলেছে আর বেরোনোর আগে নামায় না। প্রত্যেকে ঢোকার আগে turn-এ একবার লিখেছে; ধরা যাক (নাম বদলে নেওয়া যায় বলে সাধারণতা না হারিয়ে) P₁-এর লেখা turn = 0 পরে ঘটেছে, P₀-এর turn = 1 আগে। P₁-এর লেখার পর থেকে t পর্যন্ত আর কেউ turn-এ লেখেনি (দুজনের পরের লেখা আসবে কেবল পরের entry-তে), তাই ওই পুরো সময় turn = 0. P₁ নিজের লেখার পরে লুপের শর্ত দেখে বেরিয়েছে, অর্থাৎ তখন হয় flag[0] false, নয় turn == 1. turn তখন 0, তাই সে নিশ্চয়ই flag[0] false পড়েছে। কিন্তু P₀ নিজের flag তুলেছিল নিজের turn-লেখার আগে — যা P₁-এর turn-লেখার আগে — আর t পর্যন্ত নামায়নি। অর্থাৎ P₁-এর পড়ার সময় flag[0] true. বিরোধ। তাই দুজন একসাথে ভেতরে থাকতে পারে না। ∎

(২) Progress. P_i আটকাতে পারে কেবল এক জায়গায় — লুপে, যখন flag[j] true এবং turn == j. P_j কোথায় আছে, সেই অনুযায়ী চারটি ক্ষেত্র: (ক) P_j ঢুকতে চায় না, remainder-এ আছে — তাহলে flag[j] false, তাই P_i সঙ্গে সঙ্গে ঢোকে; remainder-এর প্রসেস কাউকে আটকায় না। (খ) দুজনই লুপে — turn-এর মান একটিই, 0 বা 1, আর লুপে থাকার সময় কেউ turn বদলায় না। তাহলে turn যার নামে নয়, তার শর্ত মিথ্যা, আর সে ঢোকে। (গ) P_j entry-র মাঝপথে — সে শিগগির turn = i লিখবে, তখন P_i-এর শর্ত মিথ্যা হয়ে যায়। (ঘ) P_j critical section-এ — অনুমান অনুযায়ী সে সসীম সময়ে বেরিয়ে flag নামাবে, তারপর (ক) বা (গ)। দুজন একসাথে চিরকাল ঘুরতে পারে না, আর সিদ্ধান্তে অংশ নিচ্ছে শুধু entry-তে থাকা প্রসেসরা (তাদের flag আর turn-লেখা)। ∎

(৩) Bounded waiting (সীমা = ১). ধরুন P_i নিজের turn = j লিখে লুপে অপেক্ষা করছে। P_j এখন ভেতরে থাকলে বেরোনোর সময় flag[j] = false করবে। এরপর P_j আবার ঢুকতে চাইলে নিজের entry-তে লিখবে turn = i — আর তখন P_j-এর নিজের শর্ত দাঁড়ায় flag[i] && turn == i = true, তাই P_j আটকে যায়, অথচ P_i-এর শর্ত (turn == j) মিথ্যা হয়ে যায়। অর্থাৎ P_i অপেক্ষা শুরুর পর P_j সর্বোচ্চ একবার ঢুকতে পারে (যে প্রবেশটি আগেই চলছিল বা শুরু হচ্ছিল), তারপর P_i-এর পালা নিশ্চিত। ∎

নিজে যাচাই — সব interleaving গুনে দেখা

হাতের প্রমাণে ভুল থাকতে পারে — concurrent অ্যালগরিদমের ইতিহাসে বহু “প্রমাণিত” সমাধান পরে ভুল প্রমাণিত হয়েছে। আরেকটি পথ: দুটি প্রসেসের ছোট অ্যালগরিদমে সম্ভাব্য অবস্থার সংখ্যা সীমিত (প্রতিটি প্রসেস কোন লাইনে, আর flag আর turn-এর মান), তাই কম্পিউটার সব অবস্থা আর সব interleaving ঘুরে দেখতে পারে। একে বলে model checking. নিচের প্রোগ্রামটি এই পর্বের চারটি অ্যালগরিদমের প্রতিটির জন্য তা-ই করে — প্রতিটি ধাপে একটিমাত্র load বা store, আর remainder-এ থাকা প্রসেস চাইলে চিরকাল সেখানে থেকে যেতে পারে (halt). তারপর তিনটি শর্ত যাচাই করে:

// pc: 0 remainder, 1..5 entry section, 9 critical section (CS). One step = one read OR one write.
const CS = 9, A = {   // step(s, i, j): run one step of process i; staying on the same pc = still spinning
  'strict alternation': { spin: [1], step: (s, i) => { if (s.turn === i) s.pc[i] = CS; } },
  'two flags: set, then wait': { spin: [2], step: (s, i, j) => {
    if (s.pc[i] === 1) { s.flag[i] = 1; s.pc[i] = 2; } else if (!s.flag[j]) s.pc[i] = CS; } },
  'two flags: wait, then set': { spin: [1], step: (s, i, j) => {
    if (s.pc[i] === 1) { if (!s.flag[j]) s.pc[i] = 2; } else { s.flag[i] = 1; s.pc[i] = CS; } } },
  'Peterson': { spin: [3, 4], step: (s, i, j) => { const p = s.pc[i];   // while (flag[j] && turn == j);
    if (p === 1) { s.flag[i] = 1; s.pc[i] = 2; } else if (p === 2) { s.turn = j; s.pc[i] = 3; }
    else if (p === 3) s.pc[i] = s.flag[j] ? 4 : CS; else s.pc[i] = s.turn === j ? 3 : CS; } },
};
for (const [name, { spin, step }] of Object.entries(A)) {
  const key = (s) => JSON.stringify(s), seen = new Map(), next = new Map(), todo = [];
  const add = (s) => { const k = key(s); if (!seen.has(k)) { seen.set(k, s); todo.push(s); } return k; };
  add({ pc: [0, 0], flag: [0, 0], turn: 0, halt: [0, 0], over: [0, 0] });   // over[j]: entries by i while j spins
  while (todo.length) { const s = todo.pop(), out = [];
    for (const i of [0, 1]) {
      if (s.halt[i]) continue;
      const j = 1 - i, t = structuredClone(s), pc = s.pc[i];
      if (pc === 0) { const h = structuredClone(s); h.halt[i] = 1; out.push(add(h)); t.pc[i] = 1; }  // may stay out forever
      else if (pc === CS) { if (name === 'strict alternation') t.turn = j; else t.flag[i] = 0; t.pc[i] = 0; t.over[i] = 0; }
      else { step(t, i, j); if (t.pc[i] === CS && spin.includes(s.pc[j])) t.over[j] = Math.min(t.over[j] + 1, 3); }
      out.push(add(t));
    }
    next.set(key(s), out);
  }
  const all = [...seen.values()], good = new Set(all.filter((s) => s.pc.includes(CS)).map(key));
  for (let grew = true; grew; ) { grew = false;      // good = states from which someone can still reach the CS
    for (const [k, out] of next) if (!good.has(k) && out.some((o) => good.has(o))) { good.add(k); grew = true; } }
  const me = all.find((s) => s.pc[0] === CS && s.pc[1] === CS);
  const stuck = all.find((s) => !good.has(key(s)) && s.pc.some((p) => p > 0 && p < CS));
  const show = (s) => JSON.stringify({ pc: s.pc, flag: s.flag, turn: s.turn, halt: s.halt });
  const bw = Math.max(...all.map((s) => Math.max(...s.over)));
  console.log(`${name}: ${seen.size} states`);
  console.log('  mutual exclusion :', me ? 'VIOLATED  e.g. ' + show(me) : 'holds');
  console.log('  progress         :', !stuck ? 'holds' : (stuck.halt.includes(1) ? 'VIOLATED (other stays in remainder)'
    : 'VIOLATED (deadlock)') + '  e.g. ' + show(stuck));
  console.log('  bounded waiting  :', bw >= 3 ? 'NO bound (3+ entries seen)' : `other enters at most ${bw} time(s)`);
}

strict alternation: 40 states
  mutual exclusion : holds
  progress         : VIOLATED (other stays in remainder)  e.g. {"pc":[0,1],"flag":[0,0],"turn":0,"halt":[1,0]}
  bounded waiting  : other enters at most 1 time(s)
two flags: set, then wait: 24 states
  mutual exclusion : holds
  progress         : VIOLATED (deadlock)  e.g. {"pc":[2,2],"flag":[1,1],"turn":0,"halt":[0,0]}
  bounded waiting  : other enters at most 0 time(s)
two flags: wait, then set: 121 states
  mutual exclusion : VIOLATED  e.g. {"pc":[9,9],"flag":[1,1],"turn":0,"halt":[0,0]}
  progress         : holds
  bounded waiting  : NO bound (3+ entries seen)
Peterson: 112 states
  mutual exclusion : holds
  progress         : holds
  bounded waiting  : other enters at most 1 time(s)

৬ · n প্রসেসের জন্য — Lamport-এর bakery algorithm

Peterson দুটি প্রসেসের জন্য। তিন বা হাজার প্রসেস হলে? ১৯৭৪ সালে Leslie Lamport Communications of the ACM-এ একটি সমাধান দেন, যার নাম bakery algorithm — বেকারির দোকানের টোকেন-ব্যবস্থার নামে।

bool choosing[n] = {false};   /* shared: "I am picking a ticket" */
int  number[n]   = {0};       /* shared: 0 = not interested      */

lock(i):
    choosing[i] = true;
    number[i] = 1 + max(number[0], ..., number[n-1]);
    choosing[i] = false;
    for (j = 0; j < n; j++) {
        while (choosing[j]) ;                        /* let j finish picking */
        while (number[j] != 0 &&
               (number[j], j) < (number[i], i)) ;   /* j is ahead of me     */
    }
unlock(i):
    number[i] = 0;

এখানে (a, b) < (c, d) মানে a < c, অথবা a = c আর b < d — অভিধানের মতো তুলনা। একটি ছোট উদাহরণ, তিনটি প্রসেস:

ফল: P1, P2, P0 — যে আগে টোকেন নিয়েছে, সে আগে, অর্থাৎ first-come, first-served; তাই bounded waiting স্বাভাবিকভাবেই আসে (n − ১ জনের বেশি কেউ আপনাকে টপকাতে পারে না)। choosing কেন লাগে? ধরুন P1 আর P2 একই নম্বর 1 পাবে, কিন্তু P2 আগে লেখা শেষ করে লুপে ঢুকল, তখনো P1-এর number[1] 0 দেখাচ্ছে (P1 হিসাব করছে, লেখেনি)। choosing না থাকলে P2 ভাবত P1 আগ্রহী নয়, আর ঢুকে পড়ত; তারপর P1 লিখত 1, দেখত (1, 1) < (1, 2), আর সেও ঢুকত — দুজন ভেতরে। choosing[1] P2-কে বাধ্য করে P1-এর নম্বর লেখা শেষ হওয়া পর্যন্ত অপেক্ষা করতে।

দুটি দুর্বলতাও আছে: টোকেনের নম্বর সীমাহীনভাবে বাড়তে পারে (সবসময় কেউ না কেউ ভেতরে থাকলে নম্বর কখনো 0-তে ফেরে না), আর প্রতিটি lock-এ n টি প্রসেসের ঘর পড়তে হয় — n বড় হলে ধীর। তাই বাস্তবের সিস্টেমে bakery চলে না; কিন্তু “টোকেন নিয়ে FIFO ক্রম” ধারণাটি বেঁচে আছে ticket lock-এ, যা Linux kernel x86-এ বহু বছর spinlock হিসেবে ব্যবহার করেছে (পর্ব ২৩)।

৭ · আধুনিক CPU-তে Peterson কেন ভাঙে — store buffer আর reordering

এতক্ষণের সব প্রমাণ একটি অনুমানের ওপর দাঁড়িয়ে: প্রতিটি প্রসেস প্রোগ্রামের ক্রমেই মেমরিতে লেখে আর পড়ে, আর সবাই একই ক্রম দেখে। আধুনিক CPU আর compiler গতির জন্য এই অনুমান ভেঙে দেয়।

প্রতিটি core লেখাগুলো সঙ্গে সঙ্গে cache-এ পাঠায় না; আগে রাখে নিজের একটি ছোট সারিতে — store buffer. ফলে core পরের instruction-এ এগিয়ে যেতে পারে, ধীর মেমরির জন্য থামতে হয় না। কিন্তু এর মানে, একটি core-এর লেখা অন্য core কিছুক্ষণ দেখতে পায় না। x86-এও (যাকে “শক্ত ক্রমের” CPU বলা হয়) ঠিক এই একটি reordering অনুমোদিত: আগের store-এর আগেই পরের load ঘটে যেতে পারে (ভিন্ন ঠিকানায়)। আর Peterson-এর entry ঠিক এই ধাঁচের — আগে flag[i] লেখা, পরে flag[j] পড়া:

প্রত্যেকে নিজের লেখা দেখে (নিজের buffer থেকে), কিন্তু অন্যেরটা দেখে না — আর দুজনই ঢুকে পড়ে। ARM বা RISC-V-এর মতো দুর্বলতর ক্রমের CPU-তে আরও বেশি ধরনের reordering হয়। Compiler-ও একই কাজ করতে পারে: সাধারণ ভ্যারিয়েবলের পড়া লুপের বাইরে তুলে নেওয়া, বা দুটি লেখার ক্রম বদলানো। সাধারণ C ভ্যারিয়েবলে Peterson লেখা তাই C11 মানদণ্ডে data race — undefined behavior. নিচের প্রোগ্রামে compiler-কে থামাতে volatile দেওয়া হয়েছে, কিন্তু CPU-কে থামানোর কিছু নেই:

#include <pthread.h>
#include <stdio.h>
#define LOOPS 1000000
static volatile int flag[2], turn;       /* volatile: the COMPILER must touch memory, */
static volatile long counter;            /* but the CPU may still reorder           */

static void *worker(void *arg) {
    int i = (int)(long)arg, j = 1 - i;
    for (int k = 0; k < LOOPS; k++) {
        flag[i] = 1;                     /* store ...                       */
        turn = j;
        while (flag[j] && turn == j)     /* ... then load: x86 may let this */
            ;                            /* load pass the store above       */
        counter++;                       /* critical section */
        flag[i] = 0;
    }
    return NULL;
}
int main(void) {
    pthread_t t0, t1;
    pthread_create(&t0, NULL, worker, (void *)0L);
    pthread_create(&t1, NULL, worker, (void *)1L);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    printf("counter = %ld, expected %d, lost updates = %ld\n",
           counter, 2 * LOOPS, 2L * LOOPS - counter);
    return 0;
}

run 1: counter = 1999167, expected 2000000, lost updates = 833
run 2: counter = 1996962, expected 2000000, lost updates = 3038
run 3: counter = 1999934, expected 2000000, lost updates = 66

সমাধান: compiler আর CPU-কে বলে দেওয়া যে এই ভ্যারিয়েবলগুলোর লেখা-পড়া প্রোগ্রামের ক্রমেই সবার কাছে দৃশ্যমান হতে হবে। C11-এর <stdatomic.h>-এ atomic_store আর atomic_load-এর ডিফল্ট ক্রম memory_order_seq_cst — sequential consistency, ঠিক যা প্রমাণে ধরা হয়েছিল। x86-64-এ GCC এমন store-কে সাধারণত xchg (অথবা mov-এর পরে mfence) হিসেবে বানায় — দুটিই একটি পূর্ণ memory barrier, যা store buffer খালি না হওয়া পর্যন্ত পরের load-কে আটকে রাখে:

#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdio.h>
#define LOOPS 200000
static atomic_int flag[2], turn;        /* atomic_* ops default to seq_cst */
static long counter;                     /* plain variable, guarded by the lock */

static void lock(int i) {
    int j = 1 - i;
    atomic_store(&flag[i], 1);           /* "I want to enter"            */
    atomic_store(&turn, j);              /* "but you may go first"       */
    while (atomic_load(&flag[j]) && atomic_load(&turn) == j)
        sched_yield();                   /* busy wait, but give the CPU away */
}
static void unlock(int i) { atomic_store(&flag[i], 0); }

static void *worker(void *arg) {
    int i = (int)(long)arg;              /* 0 or 1 */
    for (int k = 0; k < LOOPS; k++) {
        lock(i);
        counter++;                       /* critical section */
        unlock(i);
    }
    return NULL;
}
int main(void) {
    pthread_t t0, t1;
    pthread_create(&t0, NULL, worker, (void *)0L);
    pthread_create(&t1, NULL, worker, (void *)1L);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    printf("counter = %ld, expected %d: %s\n", counter, 2 * LOOPS,
           counter == 2 * LOOPS ? "mutual exclusion held" : "BROKEN");
    return 0;
}

counter = 400000, expected 400000: mutual exclusion held

৮ · সারসংক্ষেপ — কোন সমাধান কোন শর্ত মানে

প্রতিটি সফটওয়্যার-সমাধানের সাধারণ দুর্বলতা দুটি: busy waiting, আর memory ordering-এর ওপর নির্ভরতা। তাই পরের পর্বগুলোর পথ: hardware-এর atomic instruction আর spinlock (পর্ব ২৩), ঘুমিয়ে অপেক্ষার mutex আর semaphore (পর্ব ২৪), condition variable আর monitor (পর্ব ২৫), আর ক্লাসিক সমস্যাগুলোতে এগুলোর প্রয়োগ (পর্ব ২৬)।

৯ · AI-এর যুগে race condition আর lock-এর কোড

“দুই থ্রেডের জন্য একটি lock লিখে দাও” — AI মুহূর্তে Peterson বা একটি flag-ভিত্তিক lock দেবে, আর আপনার ল্যাপটপে কয়েক হাজার বার চালিয়ে হয়তো ঠিকই দেখাবে। কিন্তু উপরে দেখেছেন, ভুলটি ২০ লাখে মাত্র কয়েক ডজন বার আসতে পারে। এ বিষয়ে AI-এর সাধারণ ভুল:

AI-এর দেওয়া lock বা প্রমাণ ব্যবহারের আগে — চেকলিস্ট

• প্রতিটি “ভাঙে” দাবির interleaving হাতে মিলিয়েছি — প্রতিটি সারিতে মানগুলো আগের সারি থেকে সত্যিই আসে
• ছোট অ্যালগরিদম হলে সব interleaving একটি model checker-এ (যেমন উপরের JS প্রোগ্রাম) যাচাই করেছি
• Shared flag/turn ভ্যারিয়েবলগুলো atomic (seq_cst) বা barrier দিয়ে রক্ষিত; volatile-এ ভরসা রাখিনি
• লাখবার লুপে, একাধিক core-এ, -O0 আর -O2 দুই ভাবেই চালিয়ে আর -fsanitize=thread দিয়ে পরীক্ষা করেছি
• কাজের কোডে নিজের বানানো lock-এর বদলে OS বা ভাষার mutex ব্যবহার করা যায় কি না ভেবেছি