پاسخ امتحانک دوم سیستم عامل – نیمسال اول ۹۳-۹۴
مدت زمان کوییز: ۲۰ دقیقه بالای برگه خود حتما نام و نام‌خانوادگی را بنویسید.
１- الگوریتم‌های زمان‌بندی که تاکنون خوانده‌اید (FCFS, SJF, SPN, SRT, Priority, RR, MultiLevel Queue, …) را درنظر بگیرید و به سوالات زیر با استدلال پاسخ دهید:
الف) کدام الگوریتم(ها) بیشترین بهره‌ی پردازنده را دارد؟ ب) کدام الگوریتم(ها) کمترین زمان گردش کار را دارد؟
ج) کدام الگوریتم(ها) کمترین زمان انتظار را دارد؟ د) کدام الگوریتم(ها) کمترین زمان پاسخ‌دهی را دارد؟
پاسخ:
２- با زبان مهندسی خودتان توضیح دهید برتری روشی مانند مانیتور به سمافور به چه دلیل است؟ برای توضیح یک مسئله را به دلخواه خودتان با تکنیک سمافور حل کنید و سپس همان مسله را با مانیتور حل کنید. آنگاه به مقایسه این ۲روش بپردازید.
پاسخ: در کلاس حل تمرین به تفصیل بحث و بررسی شده است.
３- در جدول زیر کد اجرایی سه فرآیند را می‌بینید که برای شش منبع با یکدیگر رقابت می‌کنند. در این مورد:
|
void P0() { while (true) { get(A); get(B); get(C); // critical region: // use A, B, C release(A); release(B); release(C); } } |
void P1() { while (true) { get(D); get(E); get(B); // critical region: // use D, E, B release(D); release(E); release(B); } } |
void P2() { while (true) { get(C); get(F); get(D); // critical region: // use C, F, D release(C); release(F); release(D); } } |
الف) گراف تخصیص منابع را برای این سه فرآیند رسم کنید و در مورد احتمال رخداد بن بست استدلال کنید.
پاسخ: برای تشخیص بن‌بست باید ۴شرط به طور همزمان ایفا شود:
１- وجود انحصار متقابل (Mutal Exclusion)
２- نگهداری و انتظار (Hold & Wait)
３- غیرقابل بازپس گیری(No Preemption)
４- انتظار حلقوی (Circular Waiting)
بنابراین توجه داشته‌باشید که باید هر چهار شرط بررسی شود.
تشخیص انحصار متقابل، نگهداری و انتظار و غیرقابل بازپس‌گیری بسیار ساده‌است و به دانش مهندسی شما مربوط می‌شود. هرچند که در سوالات مربوط به بن‌بست این شروط به‌طور پیش‌فرض وجود دارد.
تشخیص انتظار حلقوی ساده‌نیست. برای این منظور باید از تکنیک‌های ریاضی استفاده کنیم. برای این منظور از گراف‌‌جهت‌دار استفاده می‌کنیم. چون می‌دانیم گراف‌ها به خوبی انتظار حلقوی را به تصویر می‌کشد.برای تحلیل شکل‌های انتظار حلقوی از فایل پیوست استفاده کنید. در فایل پیوست تشریحی در مورد انواع گراف‌ها و رخداد‌ها توضیح داده شده است.
حال که شکل پیوست را دیده‌اید باید بررسی کنیم در این مسئله بن‌بست داریم یا نه؟
اصولا اینکه می‌گوییم سیستم‌عامل می‌تواند جلوی بن‌بست را بگیرد از این مسئله نشأت می‌گیرد که سیستم‌عامل درحقیت نحوه تخصیص منابع را مدیریت می‌کند. یعنی سیستم‌عامل به درخواست‌های فرآیندها طوری پاسخ می‌دهد که هیچ‌گاه منجر به بن‌بست نشود. حال برای تشخیص بن‌بست در چنین مسئله‌هایی باید یک ترتیبی از نحوه درخواست منابع را پیدا کنیم که منجر به رخداد بن‌بست می‌شود. بنابراین باید به دنبال یک حالت خاص باشیم. مثلا فرض کنید ترتیب اختصاص منابع به صورت زیر است:
باتوجه به ینکه اجرای فرآیندها موازی است:
P2.get(C) à P1.get(D) à P0.get(A) à P0.get(B)
یعنی ابتدا C را به P2 می‌دهیم و …
بنابراین گراف حاصل مطابق با شکل‌زیر خواهد بود:
اختصاص بی‌خطر: هرگاه برای یک منبع فقط یک درخواست داشته باشیم اختصاص بی‌خطر است. (به عنوان مثال فقط یک متقاضی داشته‌باشد)
اختصاص خطرناک: هرگاه برای یک منبع بیش‌از یک درخواست داشته باشیم اختصاص خطرناک است. (به عنوان مثال چند متقاضی داشته‌باشد)
یال‌های درخواستی: این یال‌ها درواقع همان get(…) ها می‌باشند.
با کمی دقت در شکل بالا متوجه وجود یک دور خواهید شد.
ب) ترتیب نحوه درخواست فرآیندها به منابع را طوری تغییر دهید که تخصیص منابع کاملا امن باشد. توجه کنید منابع نباید میان فرآیندها جابجه شود. یعنی فقط در داخل فرآیندها ترتیب اختصاص را تغییر دهید.
پاسخ: برای حل کردن این قسمت از شکل بالا بهره بگیرید و سپس طوری یال‌بندی نمایید که دوری به وجود نیاید.
و در نتیجه کد فوق به صورت زیر خواهد بود:
|
void P0() { while (true) { get(A); get(B); get(C); // critical region: // use A, B, C release(A); release(B); release(C); } } |
void P1() { while (true) { get(E); get(B); get(D); // critical region: // use D, E, B release(E); release(B); release(D); } } |
void P2() { while (true) { get(F); get(D); get(C); // critical region: // use C, F, D release(F); release(D); release(C); } } |
با آرزوی موفقیت برای شما دوستان عزیز
زندی
برای دریافت نسخهPDF پاسخ کوییز از لینک استفاده نمایید.
