الگوریتم پترسون

الگوریتم پترسون یک الگوریتم برنامه نویسی همزمان برای انحصار متقابل است که به دو فرایند اجازه می‌دهد تا از یه منبع مشترک بدون هیچ تعارضی استفاده کنند و از حافظه مشترک تنها برای ارتباطات بهره ببرند. این الگوریتم توسط‌گری ال پترسون (به انگلیسی: Gary L. Peterson) در سال ۱۹۸۱ طراحی شد. از آنجایی که الگوریتم اصلی پترسون برای تنها دو فرایند قابل اجرا است، الگوریتم را می‌توان به صورت زیر برای بیش از دو فرایند تعمیم داد.^[۱]^[۲]^[۳]

الگوریتم

الگوریتم از دو متغیر پرچم (به انگلیسی: flag) و نوبت (به انگلیسی: turn) استفاده می‌کند. درست بودن (به انگلیسی: true) مقدار flag[n] نشان دهندهٔ درخواست برای ورود به بخش بحرانی است. ورود به بخش بحرانی برای فرایند P0 تضمین می‌کند که در صورت تمایل نداشتن فرایند P1 برای ورود به این بخش، وارد بخش بحرانی شود یا اگر فرایند P1 اولویت خود را با قرار دادن مقدار صفر برای نوبت، به فرایند P0 بدهد در این حالت نیز P0 وارد این بخش می‌شود.

bool flag[0]   = false;
bool flag[1]   = false;
int turn;

P0:      flag[0] = true;
P0_gate: turn = 1;
         while (flag[1] && turn == 1)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[0] = false;

P1:      flag[1] = true;
P1_gate: turn = 0;
         while (flag[0] && turn == 0)
         {
             // busy wait
         }
         // critical section
         ...
         // end of critical section
         flag[1] = false;

این الگوریتم دارای سه معیار اساسی برای حل مسئلهی بخش بحرانی است، بشرط آنکه متغیرهای turn، flag[0] و flag[1] به صورت سریع و اتمی تغییر کنند. در این حالت این وضعیت حتی برای قبضه کردن فرایند نیز کارآمد است.

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

انحصار متقابل

فرایند P0 و P1 نمی‌توانند در یک زمان در بخش بحرانی باشند: اگر P0 در بخش بحرانی قرار داشته باشد پرچم مربوط به آن مقدار درست (به انگلیسی: true) را نشان می‌دهد. به علاوه، یا پرچم فرایند اول نشان دهندهٔ مقدار نادرست (به انگلیسی: false) است (به این معنی که P1 بخش بحرانی را ترک کرده) یا نوبت برابر مقدار صفر است (به این معنی که P1 در حال تلاش برای ورود به بخش بحرانی است؛ اما از روی بخشندگی صبر می‌کند)، یا P1 در حالت P1_gate قرار دارد (بعد از قرار دادن پرچمش در وضعت درست و قبل از نسبت دادن مقدار صفر به نوبت و انتظار چرخشی، تلاش می‌کند وارد بخش بحرانی شود). بنابراین نمی‌تواند حالتی وجود داشته باشد که هر دو فرایند در آن در بخش بحرانی قرار داشته باشند.

پیشرفت

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

انتظار محدود

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

الگوریتم تعمیم یافته: الگوریتم پترسون برای N فرایند

این الگوریتم از N سطح متفاوت که هر کدام نشان دهندهٔ یک "اتاق انتظار" قبل از بخش بحرانی است استفاده می‌کند. هر سطح حداکثر به یک فرایند اجازه پیشروی می‌دهد در حالیکه فرایند دیگر را منتظر نگه می‌دارد.

// initialization
level[N] = { -1 };     // current level of processes 0...N-1
waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2

// code for process #i
for(l = 0; l <N-1; ++l) {
    level[i] = l;
    waiting[l] = i;
    while(waiting[l] == i &&
          (there exists k ≠ i, such that level[k] ≥ l)) {
        // busy wait
    }
}

// critical section

level[i] = -1; // exit section

توجه

زمانیکه در سطح سخت افزار فعالیت می‌کنید، به‌طور معمول نیازی به استفاده از الگوریتم پترسون برای دسترسی‌های اتمی ندارید. برخی فرایندها دستورالعمل خاص خود را دارند مانند، test-and-set یا Compare-and-swap که با قفل کردن گذرگاه حافظه می‌توانند انحصار متقابل را در سیستم‌های چند پردازشی متقارن ایجاد کنند.

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

منابع

↑ G. L. Peterson: "Myths About the Mutual Exclusion Problem", Information Processing Letters 12(3) 1981, 115–116
↑ As discussed in Operating Systems Review, January 1990 ("Proof of a Mutual Exclusion Algorithm", M Hofri).
↑ Silberschatz. Operating Systems Concepts: Seventh Edition. John Wiley and Sons, 2005., Pages 194