سیستم عامل/بن‌بست

'

بن‌بست

'

سیستم عامل

همزمانی فرآیندها و اصول همزمانی : پایه اصلی چند برنامگی دریک سیستم عامل،قابلیت اجرای چندین برنامه با یکدیگر است.اجرای چند برنامه با یکدیگر در یک محیط تک پردازنده بدین مفهوم است که هرچند در هر زمان یک برنامه در حال اجراست ولی چندین برنامه در سیستم عامل هستند که اجرای آنها شروع شده ولی پایان نیافته اند. عموماً در محیط های چند برنامه ای تعدادی از برنامه ها با یکدیگر دارای نواحی داده ای مشترک یا حافظه مشترک می باشند.برای استفاده صحیح از این داده ها بدون بروز خطا،باید هماهنگی بین آنها وجود داشته باشد. یک فرآیند همکار فرآیندی است که می تواند به سایر پردازشهای در حال اجرا اثر گذارد و یا از آنها تاثیر بگیرد.فرآیندهای همکار ممکن است یا مستقیماً یک فضای آدرس را به اشتراک گذارد و یا اجازه داشته باشد داده های یکدیگر را تغییر دهند.به وضعیتی که دو یا چند فرآیند به متغیر های اشتراکی دسترسی دارند و در نتیجه فرآیندها بستگی به زمان فرآیندها دارد شرایط مسابقه ای یا Race condition گویند. ناحیه بحرانی (critical section) : سیستمی متشکل از n فرآیند که هر فرآیند دارای ناحیه ای در کد است که در آن ناحیه ممکن است متغیرهای مشترک تغییر نمایند یا جدولی به هنگام شود و یا فایلی به اشتراک گذاشته شود.به این بخش از کد ناحیه بحرانی می گویند. برای برطرف کردن شرایط رقابتی راه حل مختلفی وجود دارد.هر راه حل باید بتواند سه شرایط زیر را ارضا کند:

1- Mutual exclusion: انحصار متقابل – دو به دو ناسازگار – مانعه الجمعی اگر فرآیندی در حال اجرا در ناحیه بحرانی باشد در آن صورت هیچ فرآیندی در ناحیه بحرانی خود نمی تواند اجرا شود.(هیچ دو فرآیندی نباید همزمان در ناحیه بحرانی باشند.)

2- Progress (پیشرفت): اگر هیچ فرآیندی در ناحیه بحرانی نباشد و فرآیندهای دیگری تمایب برای ورود به ناحیه بحرانی داشته باشند فقط آن فرآیندهایی که به ناحیه بحرانی نرسیده اند می توانند در تصمیم گیری درباره اینکه کدام فرآیند وارد ناحیه بحرانی شود شرکت کنند.به عبارت دیگر هیچ فرآیندی در بیرون از ناحیه بحرانی خود نمی توانند فرآیندهای دیگر را بلوک کنند.

3- Bounded waiting (انتظار محدود): یک فرآیند نباید به طور نامحدود برای ورود به ناحیه بحرانی باقی بماند.

در کل چهار راه حل برای حل مشکل شرایط رقابتی وجود دارد:

• راه حل نرم افزاری : خود فرآیندها بدون هیچ حمایتی از جانب سیستم عامل مشکل خود را حل کنند.

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

• سیستم عامل

• حمایت زبان های برنامه نویسی

1- از کار انداختن وقفه ها: هر فرآیند قبل از ورود به ناحیه بحرانی می تواند وقفه ها را از کار بیاندازد و بعد از خروج دوباره فعال کند.با این روش CPU نمی تواند فرآیندهای دیگر را سوئیچ کند.

1- شاید کاربر وقفه ها را روشن نکرد (خطرناک)

2- چند CPU:فقط CPU جاری از کار می افتد و بقیه هنوز کار می کنند.

3- تناوب قطعی: در این روش از یک Flag(نوبت) به نام Turn استفاده می شود که می تواند 0 یا 1 باشد.اگر 1بود نوبت P1 و اگر 0 بود نوبت با P0 است که وارد ناحیه بحرانی شود.

مثلاً اگر P1 کارش تمام شود و نوبت را به P0 دهد ولی P0 نخواهد وارد ناحیه بحرانی شود P1 نیز نمی تواند وارد ناحیه بحرانی شود.در واقع در این روش فرآیندها باید متناوباً وارد ناحیه بحرانی شوند.

While (turn ==1){ };

   ناحیه بحرانی

Turn = 1; While (turn ==0) { };

   ناحیه بحرانی

Turn = 0; مثلاً اگر P1 کارش تمام شود و نوبت را به P0 دهد ولی P0 نخواهد وارد ناحیه بحرانی شود P1 نیز نمی تواند وارد ناحیه بحرانی شود.در واقع در این روش فرآیند ها باید متناوباً وارد ناحیه بحرانی شوند. 4- Flag:به هر فرآیند یک Flag اختصاص می یابد که توسط خود فرآیند قابل تغییر است و توسط فرآیندهای دیگر فقط قابل چک شدن است.هر فرآیند در صورت تمایل برای ورود به ناحیه بحرانی فلگ خود را 1 می کند همچنین هر فرآیند قبل از ورود به ناحیه بحرانی فلگ دیگری را نیز چک می کند.مقدار اولیه هر دو فلگ صفر است. P0 P1 F2 = 1; While (F1==1); ناحیه بحرانی F2 = 0; F1 = 1; While (F2==1)

ناحیه بحرانی

F1=0; مشکل: هر دو فرآیند در While می مانند. 5- همان راه حل چهارم است اما ست کردن فلگ ها بعد از While قرار می گیرد.

P0 P1 While (F1 == 1) F0 = 1; ناحیه بحرانی F0 = 0; While (F0 == 1) F1 = 1;

ناحیه بحرانی

F1=0; مشکل: هردو فرآیند وارد ناحیه بحرانی می شوند.چون F0 = 0 است پس از P1 از حلقه While رد می شود اما قبل از F1= 1 سوئیچ به P0،P0 هم F1=0 را کنترل کرده و وارد ناحیه بحرانی می شود و سوئیچ به P1 می کند،P1هم وارد ناحیه بحرانی می شود.

6- (TSL (Test and Set Lock : این یک روش با حمایت سخت افزاری است.پردازنده باید دستوری با عملکرد TSL داشته باشد.دستور TSL بصورت اتمیک و غیر قابل تجزیه انجام می شود.دستور TSL یک فلگ را چک کرده و مقدار آن را ست می کند.چون این کار به صورت اتمیک انجام می شود وقفه ای بین آن رخ نمی دهد.(برای متغیر قفل استفاده می شود)

7- دستور العمل Swap: اگر دستور Swap بصورت اتمیک و با کارکرد زیر تعریف کنیم:

Proc swap (a, b)

  {
       temp = a;
       a = b;
       b = temp;
  }

دستور Swap می تواند انحصار متقابل را با روش زیر فراهم کند.

Key = true; Repeat

          Swap (lock, key);

Until key = false;

ناحیه بحرانی Lock = false; Repeat … until زمانی اجرا می شود که شرط حلقه غلط باشد و به محض آن که درست شد از حلقه خارج می شود.یک متغیر برای Lock با مقدار اولیه F و یک متغیر محلی Key برای هر فرآیند داریم.

8- راه حل پیتر سون (Peterson): این راه حل از یک متغیر turn و یک آرایه منطقی استفاده می کند. Flag [i] = true; Trun=j; While (flag [i] == true and turn ==j); ناحیه بحرانی Flag[i] = false; روش های سخت افزاری و نرم افزاری برای حل مشکل ناحیه بحرانی می باشند اما نقصی که در آنها مشاهده می شود نیاز به وضعیتی به نام انتظار مشغول یا busy waiting است.به این معنا که هنگام ورود فرآیند به ناحیه بحرانی اگر امکان ورود وجود داشته باشد فرآیند در یک حلقه انتظار قرار می گیرد و این روش باعث اتلاف وقت CPU می شود.علاوه بر آن این روش ممکن است اثرات غیر قابل انتظاری را در بر داشته باشد. بن بست (Dead lock): در یک محیط چند برنامه ای این امکان وجود دارد که فرآیندهای متفاوتی برای بدست آوردن تعداد محدودی منبع با یکدیگر رقابت کنند.یک فرآیند منابعی را درخواست می کند و در صورتی که این منابع در آن لحظه در دسترس نباشد فرآیند به حالت انتظار وارد می شود.حال اگر منابع محدود درخواست آنها در اختیار فرآیند منتظر دیگری باشد این فرآیند از وضعیت انتظار خارج نمی شود،این وضعیت را بن بست گویند.

شرایط وقوع بن بست

وضعیت بن بست در یک سیستم فقط هنگامی می تواند رخ دهد که چهار شرایط کافمن بطور همزمان برقرار گردند:

1- Mutual exclusion (انحصار متقابل): حداقل باید یک منبع به صورت غیر اشتراکی کنترل شود.یعنی فقط یک فرآیند در هرزمان می تواند از منبع استفاده کند.

2- Hold & wait(گرفتن و انتظار): باید فرآیندی موجود باشد که حداقل یک منبع را در اختیار داشته باشد و در حال انتظار برای دریافت منبع دیگر به سر برد که این منبع جدید خود در تصرف فرآیند دیگری است.

3- Non preemption(منبع انحصاری): یک منبع فقط توسط فرآیندی که آن را در اختیار دارد می تواند رها گردد.این رها سازی بر حسب اراده آن فرآیند و بعد از اتمام کار فرآیند است.

4- Circular wait(انتظار چرخشی): مجموعه ای از فرآیندهای در حال انتظار باید وجود داشته باشند به طوری که P0 در حال انتظار برای منبعی باشد که بوسیله P1 نگهداشته می شود وP1 در حال انتظار برای منبعی باشد که بوسیله P2نگداشته شده است و ... و Pn در حال انتظار برای منبعی باشد که بوسیله P0 نگهداری می شود.

Resource Allocation Graph این گراف از مجموعه ای از لبه ها و راس ها تشکیل شده است.رئوس متشکل اند از: P = {P1,P2…Pn} R = {R1,R2…Rn} لبه ها به دو صورت هستند: 1- از Pi à Rj به این مفهوم که فرآیند Pi نمونه ای از منبع Rj را در خواست کرده و منتظر آن منبع است.(Request edge لبه تقاضا)

2- از Ri à Pj به این مفهوم که منبع Ri به فرآیند Pj اختصاص یافته است.(Assignment edge)

معمولا فرآیند ها را با دایره و منابع را با مربع نشان می دهیم. از آنجا که هر منبع می تواند دارای نمونه های محدود باشد هر نمونه را داخل یک مربع با یک ▪ نشان می دهیم.

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