عکس پیش‌فرض نوشته

الگوریتم پترسون (Peterson) یک الگوریتم برنامه نویسی همزمان برای انحصار متقابل در برنامه نویسی همروند است که باعث میشود دو فرآیند بدون ایجاد هیچ مشکلی از منابع مشترک استفاده کرده و حافظه مشترک نیز تنها برای ارتباطات لازم مورد استفاده قرار گیرد.

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

 

الگوریتم های متفاوتی برای انحصار متقابل در سیستم عامل (Mutual Exclusion) ارائه شده است؛ یکی از آنها الگوریتم پترسون است که در این مطلب قصد داریم با الگوریتم و چگونگی کارکرد آن آشنا شویم.

در ابتدا باید با ناحیه بحرانی در سیستم عامل و انحصار متقابل آشنا شد.

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

در این گونه سیستم ها، هیچ دو فرآیندی اجازه ندارد به صورت هم زمان در ناحیه بحرانی خود قرار بگیرند؛ یعنی وقتی یک فرآیند در حال اجرای قطعه کد بحرانی است، هیچ فرآیند بحرانی دیگری اجازه اجرای کد بحرانی خود را ندارد.

بنابراین هر فرآیند برای ورود به ناحیه بحرانی خود، بایستی اجازه اجرای آن را بگیرد و در صورتی که مجوز اجرا صادر شد، وارد ناحیه بحرانی شود.

 

الگوریتم پترسون به عنوان یک راه حل نرم افزاری برای مدیریت و جلوگیری از به وجود آمدن مشکلات احتمالی، ارائه شده است.

کد زیر را در نظر بگیرید:

    Repeat
Flag[i] = True;
Turn = j;
While (Flag[j] and Turn==j)
    Critical Section
Flag[i] = False;
Remainder Section
Forever

 

بخش Critical ناحیه بحرانی کد و بخش Remainder سایر کدها (کدهای باقی مانده) فرآیند می باشد.

 

در این قطعه کد، فرآیند i و j از دو متغیر مشترک Flag[i] و Flag[j] به عنوان آرایه ای از متغیرهای منطقی (Boolean) و Turn به عنوان یک متغیر عددی Integer که به مقادیر i یا j مقداردهی میشود، استفاده میکنند.

در ابتدای کار Flag ها هر دو مقدار False را داشته و Turn به دلخواه 0 یا 1 خواهد بود.

ابتدا بررسی میکنیم که هیچ دو فرآیندی نمیتوانند به صورت همزمان وارد ناحیه بحرانی شوند. برای ورود به ناحیه بحرانی، فرآیند Pi مقدار Flag[i] را True کرده و سپس اعلام میکند که نوبت فرآیند بعدی است که وارد ناحیه بحرنی شود. (Turn = j)

در صورتی که دو فرایند i و j بخواهند به صورت همزمان وارد ناحیه بحرانی خود شوند، میتوان گفت که دو عملیات انتساب برای متغیر Turn در مدت زمان کوتاهی (تقریبا در یک لحظه)  انجام میشود که نهایتا در پایان یکی از این دو مقدار به عنوان مقدار اصلی Turn ذخیره خواهد شد.

در اصل مقداری که در متغیر Turn وجود دارد مشخص میکند که کدام یک از دو فرآیند موجود قبل از دیگری اجازه ورود به ناحیه بحرانی را خواهد داشت.

فرآیندی که مقدار Turn به آن نسبت داده شده باشد و یا Flag مربوط به فرآیند True باشد وارد ناحیه بحرانی اش میشود.

هیچ گاه ممکن نیست که Flag هر دو فرآیند همزمان True باشد، چون مقدار Turn در یک لحظه یکی از دو مقدار i یا j را درون خود دارد؛ بنابراین Pi و Pj نمیتوانند به صورت همزمان حلقه خود را اجرا کرده و با هم وارد ناحیه بحرانی شوند.

 

یک فرآیند تنها در صورتی نمیتواند وارد ناحیه بحرانی شود که فرآیند دیگر در داخل حلقه (ناحیه بحرانی) باشد و به عبارتی شرط حلقه while برای فرآیند مقابل برقرار باشد. مشابهاً اگر فرآیندی نخواهد وارد ناحیه بحرانی خود شود، فرآیند دیگر میتواند به راحتی وارد ناحیه بحرانی شده و از منابع مشترک استفاده کند.

به عنوان مثال اگر فرآیند Pj تمایل داشته باشد وارد ناحیه بحرانی خود شود (Flag[j]=True) آنگاه با اجرای حلقه و مقدار Boolean متغیر Trun که در حال حاضر برابر j است وارد ناحیه بحرانی میشود و در غیر اینصورت فرآیند Pi به ناحیه بحرانی مربوط به خود وارد میشود.

هنگامی که فرآیند Pj از ناحیه بحرانی خارج میشود، مقدار Flag مربوط به خود را نیز False کرده و در نتیجه به Pi اجازه میدهد که وارد ناحیه بحرانی شود. واضح است که فرآیند Pj بعد از True کردن Flag خود مقدار Turn را به i تغییر میدهد؛ به این معنی که فرآیند Pi با موفقیت وارد بخش بحرانی خواهد شد. (بعد از حداکثر یک ورود توسط Pj)

 

در اینجا الگوریتم پترسون را برای دو فرآیند بررسی کردیم؛ اما این الگوریتم را میتوان به صورت تعمیم یافته و برای N فرآیند استفاده کرد

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