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

الگوریتم پترسون یک الگوریتم برنامه نویسی همزمان برای انحصار متقابل است که به دو فرایند اجازه می‌دهد تا از یه منبع مشترک بدون هیچ تعارضی استفاده کنند و از حافظه مشترک تنها برای ارتباطات بهره ببرند. این الگوریتم توسط گری ال پترسون (به انگلیسی: Gary L. Peterson) در سال ۱۹۸۱ طراحی شد. از آنجایی که الگوریتم اصلی پترسون برای تنها دو فرایند قابل اجرا است، الگوریتم را می‌توان به صورت زیر برای بیش از دو فرایند تعمیم داد.
الگوریتم
الگوریتم از دو متغیر پرچم (به انگلیسی: flag) و نوبت (به انگلیسی: turn) استفاده می‌کند. درست بودن (به انگلیسی: true) مقدار flagn نشان دهنده‌ی درخواست برای ورود به بخش بحرانی است. ورود به بخش بحرانی برای فرایند P0 تضمین می‌کند که در صورت تمایل نداشتن فرایند P1 برای ورود به این بخش، وارد بخش بحرانی شود یا اگر فرایند P1 اولویت خود را با قرار دادن مقدار صفر برای نوبت، به فرایند P0 بدهد در این حالت نیز P0 وارد این بخش می‌شود.
bool flag0 = false;
bool flag1 = false;
int turn;
P0: flag0 = true;
P0_gate: turn = 1;
while (flag1 -- turn == 1)
// busy wait
// critical section
// end of critical section
flag0 = false;
P1: flag1 = true;
P1_gate: turn = 0;
while (flag0 -- turn == 0)
// busy wait
// critical section
// end of critical section
flag1 = false;
این الگوریتم دارای سه معیار اساسی برای حل مسئلهی بخش بحرانی است، بشرط آنکه متغییرهای turn ، flag0 و flag1 به صورت سریع و اتمی تغییر کنند. در این حالت این وضعیت حتی برای قبضه کردن فرایند نیز کارآمد است.
این سه معیار انحصار متقابل، پیشرفت و انتظار محدود است.
انحصار متقابل
فرایند P0 و P1 نمی‌توانند در یک زمان در بخش بحرانی باشند: اگر P0 در بخش بحرانی قرار داشته باشد پرچم مربوط به آن مقدار درست (به انگلیسی: true) را نشان می‌دهد. به علاوه، یا پرچم فرایند اول نشان دهنده‌ی مقدار نادرست (به انگلیسی: false) است (به این معنی که P1 بخش بحرانی را ترک کرده) یا نوبت برابر مقدار صفر است (به این معنی که P1 درحال تلاش برای ورود به بخش بحرانی است؛ اما از روی بخشندگی صبر می‌کند)، یا P1 در حالت P1_gate قرار دارد (بعد از قرار دادن پرچمش در وضعت درست و قبل از نسبت دادن مقدار صفر به نوبت و انتظار چرخشی، تلاش می‌کند وارد بخش بحرانی شود). بنابراین نمی‌تواند حالتی وجود داشته باشد که هر دو فرایند در آن در بخش بحرانی قرار داشته باشند.
پیشرفت
جریان گردشی به این صورت تعریف می‌شود: اگر هیچ فرایندی در بخش بحرانی وجود نداشته باشد و چندین فرایند خواستار ورود به این بخش باشند، تنها آن فرایندهایی که به ناحیه بحرانی نرسیده‌اند می‌توانند در تصمیم گیری درباره اینکه کدام فرایند وارد ناحیه بحرانی شود شرکت کنند. این انتخاب نمی‌تواند به صورت نامحدود به تعویق بیفتد. در حالیکه دیگر فرایند‌ها پرچم خود را به نشانه آمادگی برای ورود به بخش بحرانی بالا برده‌اند یک فرایند نمی‌تواند بلافاصله و مجددا وارد این بخش شود.
انتظار محدود
انتظار محدود به این معنی است که محدودیتی در تعداد یا زمان وجود دارد، دیگر فرایندها زمانی اجازه ورود به بخش بحرانی دارند که از قبل درخواست ورود را داده‌اند و این درخواست قبول شده باشد. در الگوریتم پترسون، فرایند بیشتر از یک نوبت در انتظار ورود به بخش بحرانی نمی‌ماند. بعد از دادن حق اولویت به فرایند دیگر، این فرایند برای تکمیل شدن پرچم خود را در حالت صفر قرار داده و به این وسیله به دیگر فرایندها اجازه ورود به بخش بحرانی را می‌دهد.
الگوریتم تعمیم یافته: الگوریتم پترسون برای N فرایند
این الگوریتم از N سطح متفاوت که هر کدام نشان دهنده‌ی یک "اتاق انتظار" قبل از بخش بحرانی است استفاده می‌کند. هر سطح حداکثر به یک فرایند اجازه پیشروی می‌دهد در حالیکه فرایند دیگر را منتظر نگه می‌دارد.
// initialization
levelN = { -1 ; // current level of processes 0…N-1
waitingN-1 = { -1 ; // the waiting process of each level 0…N-2
// code for process #i
for(l = 0; l <N-1; ++l) {
leveli = l;
waitingl = i;
while(waitingl == i --
(there exists k ≠ i, such that levelk ≥ l)) {
// busy wait
// critical section
leveli = -1; // exit section
توجه
زمانیکه در سطح سخت افزار فعالیت می‌کنید، به طور معمول نیازی به استفاده از الگوریتم پترسون برای دسترسی‌های اتمی ندارید. برخی فرایندها دستورالعمل خاص خود را دارند مانند، test-and-set یا Compare-and-swap که با قفل کردن گذرگاه حافظه می‌توانند انحصار متقابل را در سیستم‌های چند پردازشی متقارن ایجاد کنند.
اغلب پردازنده‌های امروزی برای بهبود اجرای فرایند از دسترسی مرتب به حافظه استفاده می‌کنند. پیاده سازی الگوریتم پترسون و دیگر الگوریتم‌های وابسته به آن، در فرایندهایی که خواهان دسترسی مرتب به حافظه هستند، نیازمند عملیاتی دقیق برای نظارت بر اجرای درست و به ترتیب فرایندها است.