همگام‌سازی فرایندها برای کنکور: سه تلاش برای ناحیهٔ بحرانی، سمافور و اشتباه رایج در ترتیب

مسئله و سه شرط

دو فرایند یک متغیر مشترک را تغییر می‌دهند. بخشی از کد که به آن متغیر دست می‌زند ناحیهٔ بحرانی است. هر راه‌حل باید این سه شرط را داشته باشد:

• انحصار متقابل: هیچ‌وقت دو فرایند هم‌زمان در ناحیهٔ بحرانی نباشند.
• پیشرفت: اگر ناحیهٔ بحرانی خالی است و کسی می‌خواهد وارد شود، تصمیم دربارهٔ اینکه چه کسی وارد شود بی‌نهایت عقب نیفتد.
• انتظار محدود: فرایندی که درخواست داده، بعد از تعداد محدودی نوبتِ دیگران وارد شود.

تلاش ۱: اول بررسی، بعد پرچم

هر فرایند i یک پرچم دارد. برای ورود: تا وقتی پرچم دیگری بالاست صبر کن؛ بعد پرچم خودت را بالا ببر و وارد شو. هنگام خروج پرچم را پایین بیاور.

درهم‌آمیختگی بد: هر دو فرایند پرچم دیگری را پایین می‌بینند، هر دو از حلقهٔ انتظار رد می‌شوند، بعد هر دو پرچمشان را بالا می‌برند و هر دو وارد ناحیهٔ بحرانی می‌شوند. انحصار متقابل شکسته شد. بررسی همهٔ درهم‌آمیختگی‌ها هم دقیقاً همین حالت را پیدا کرد.

تلاش ۲: اول پرچم، بعد بررسی

جای دو خط را عوض می‌کنیم: اول پرچم خودت را بالا ببر، بعد تا وقتی پرچم دیگری بالاست صبر کن.

حالا انحصار متقابل حفظ می‌شود، چون هر کس وارد شده، پرچمش قبلاً بالا بوده و دیگری را پشت در نگه می‌دارد. ولی درهم‌آمیختگی بد دیگری هست: هر دو پرچمشان را بالا می‌برند و بعد هر دو منتظر پایین آمدن پرچم دیگری می‌مانند؛ تا ابد. شرط پیشرفت شکسته شد و بررسی کامل هم همین حالت گیر را پیدا کرد.

تلاش ۳: الگوریتم پترسون

یک متغیر مشترک turn اضافه می‌کنیم. برای ورود فرایند i: پرچم خودت را بالا ببر، turn را برابر شمارهٔ فرایند دیگر بگذار و تا وقتی «پرچم دیگری بالاست و turn مال اوست» صبر کن.

چرا کار می‌کند؟ اگر هر دو هم‌زمان بخواهند وارد شوند، هر دو turn را به نفع دیگری می‌نویسند و فقط آخرین نوشتن می‌ماند. پس دقیقاً یکی منتظر می‌ماند و دیگری وارد می‌شود؛ هم انحصار حفظ می‌شود و هم کسی گیر نمی‌کند. بعد از خروج، پرچمش پایین می‌آید و دیگری وارد می‌شود؛ پس انتظار محدود هم برقرار است. همهٔ ۲۰ حالت ممکن این الگوریتم را بررسی کردیم: در هیچ‌کدام دو فرایند هم‌زمان در ناحیهٔ بحرانی نبودند و از هیچ حالتی سیستم گیر نمی‌کرد.

سمافور

سمافور یک شمارندهٔ صحیح با دو عمل اتمی است. P یا wait: اگر مقدار مثبت است یکی کم کن، وگرنه منتظر بمان. V یا signal: یکی اضافه کن و اگر کسی منتظر است بیدارش کن. مقدار اولیهٔ سمافور یعنی چند فرایند هم‌زمان می‌توانند از آن رد شوند. با مقدار اولیهٔ ۱، ناحیهٔ بحرانی حداکثر یک فرایند دارد و با ۲ حداکثر دو فرایند؛ این را هم روی همهٔ حالت‌های ممکن سه فرایند بررسی کردیم.

تولیدکننده و مصرف‌کننده، و اشتباه رایج در ترتیب

یک بافر محدود داریم. سه سمافور لازم است: empty با مقدار اولیهٔ اندازهٔ بافر، full با مقدار اولیهٔ صفر و mutex با مقدار اولیهٔ ۱. تولیدکننده P(empty)، P(mutex)، گذاشتن، V(mutex)، V(full) انجام می‌دهد و مصرف‌کننده P(full)، P(mutex)، برداشتن، V(mutex)، V(empty).

حالا اگر تولیدکننده ترتیب دو P اولش را عوض کند، یعنی اول P(mutex) و بعد P(empty)، چه می‌شود؟ فرض کن بافر پر است. تولیدکننده mutex را می‌گیرد و روی P(empty) منتظر می‌ماند. مصرف‌کننده برای برداشتن باید mutex بگیرد، ولی mutex دست تولیدکننده است. هر دو منتظر هم‌اند؛ بن‌بست. بررسی کامل با بافر یک‌خانه‌ای همین حالت را پیدا کرد، و با ترتیب درست در هیچ حالتی بن‌بست نبود.

قاعدهٔ کلی: سمافورهای «منتظر شرط»، مثل empty و full، را قبل از سمافور قفل بگیر. فرایندی که قفل را نگه داشته نباید منتظر شرطی بماند که فقط کسی که پشت همان قفل است می‌تواند برقرارش کند.

پرسش‌های پرتکرار

سه شرط راه‌حل ناحیهٔ بحرانی کدام‌اند؟

انحصار متقابل، پیشرفت و انتظار محدود. انحصار یعنی دو فرایند هم‌زمان داخل نباشند، پیشرفت یعنی اگر ناحیه خالی است تصمیم ورود بی‌نهایت عقب نیفتد، و انتظار محدود یعنی هر درخواست‌کننده بعد از تعداد محدودی نوبت وارد شود.

چرا الگوریتم پترسون درست است؟

چون وقتی هر دو فرایند می‌خواهند وارد شوند، هر کدام turn را به نفع دیگری می‌نویسد و فقط آخرین نوشتن باقی می‌ماند؛ پس دقیقاً یکی منتظر می‌ماند. وقتی فقط یکی می‌خواهد وارد شود، پرچم دیگری پایین است و منتظر نمی‌ماند.

مقدار اولیهٔ سمافور چه معنایی دارد؟

تعداد فرایندهایی که می‌توانند بدون منتظر ماندن از P رد شوند. سمافور با مقدار اولیهٔ ۱ مثل قفل عمل می‌کند و با مقدار اولیهٔ صفر برای همگام‌سازی ترتیبی به کار می‌رود؛ مثلاً اینکه B فقط بعد از A اجرا شود.

چرا ترتیب P(mutex) و P(empty) مهم است؟

اگر تولیدکننده اول mutex را بگیرد و بعد منتظر empty بماند، وقتی بافر پر است مصرف‌کننده هم نمی‌تواند mutex را بگیرد تا جای خالی درست کند. هر دو منتظر هم می‌مانند و بن‌بست پیش می‌آید.

قدم بعدی تو

در تلاش ۲، یک ترتیب دقیق از قدم‌های دو فرایند بنویس که به حالت گیر برسد. بعد در پترسون نشان بده اگر خط «turn را برابر شمارهٔ فرایند دیگر بگذار» را با «turn را برابر شمارهٔ خودت بگذار» عوض کنیم، چه شرطی شکسته می‌شود.

جواب‌ها: در تلاش ۲ کافی است هر دو فرایند اول پرچمشان را بالا ببرند و بعد هر دو به حلقهٔ انتظار برسند. در پترسون با turn برابر شمارهٔ خود، انحصار متقابل می‌شکند: فرایند ۰ پرچمش را بالا می‌برد، turn را ۰ می‌گذارد و چون پرچم ۱ پایین است وارد می‌شود. حالا فرایند ۱ پرچمش را بالا می‌برد و turn را ۱ می‌گذارد؛ شرط انتظارش «پرچم ۰ بالا و turn برابر ۰» است که درست نیست، پس او هم وارد می‌شود. بررسی همهٔ حالت‌های این نسخه هم همین مسیر را پیدا کرد.