اصول و مفاهیم طراحی سیستم های عامل 2

صفحه 1:
۳ از ‎ih‏ ار a ih i @ 0 0 ow 

صفحه 2:
1 91 سیستم عامل می تواند بهره وری کامپیوتر را مفاهیم اساسی زمانبندی : هدف چندبرنامه ای این است که هميشه چندین فرایند در حال اجرا باشند تا بهره وری 200 شود. اگر فرایندهای بیشتری وجود داشتند» بقیه منتظر می مانند تا 2)۳00) آزاد شود و بتواند دوباره زمانبندی شود. ‎oa!‏ چندبرنامه ای ساده است. هر فرایند به اجرايش ادامه می دهد تا برای یک عمل 1/0 در انتظار بماند. ‏در یک سیستم کامپیوتری ساده. در اين مدت (۳6)() باید بیکار بماند. بنابراین» تمام این زمان های انتظار هدر می روند» یعنی کار مفیدی انجام نمی شوند. در چندبرنامه ای» سعی می شود که از این زمان ها به نحو احسن استفاده شود. ‎ ‎0 

صفحه 3:
چرخه انفجار ۱/0-(600) 1 موفقیت زمانبندی (6۳0() به این خاصیت فرایندها بستگی دارد که اجرای فرایند شامل چرخه ای از اجرای 00500 و انتظار 41/0 است. ] اجرای فرایند با انفجار 26<00) شروع می شود. به دنبال آن یک انفجار 1/0 قرار دارد و به همین ترتیب ادامه می یابد. سرانجام» آخرین انفجار 00800 با درخواست سیستم برای خاتمه اجرا» پایان می پذیرد. 7 مدت این انفجارهای (26۳0) اندازه گیری شده اند و این مدت ها از فرایندی به فرایند دیگر و از کامپیوتری به کامپیوتر دیگر فرق می کند. 99 

صفحه 4:
انفجار 71/0 OPO Jes) انفجار 7/0 CPO Jos! انفجار 71/0 6/06 ‎Pe‏ ما امس ‎ 

صفحه 5:
sl 9 40 32 24 16 مدت انفجار (ميلى ثانيه) 

صفحه 6:
زمانبندی 620۳0 | هروقت ‎OPO‏ بيكار مى شودء سيستم عامل بايد يكى از فرايندهاى موجود در صف آمادكى را براى اجرا انتخاب كند. اين انتخاب توسط زمانبند كوتاه مدت (يا زمانبند (2۳)) انجام می گیرد. زمانبند. فرایندی را از بین فرایندهای موجود در حافظه که آمادگی اجرا دارند انتخاب می کند و 0020 را به ان تخصيص می دهد. | از نظر مفهومی, تمام فرایندهای موجود در صف آمادگی» منتظر به دست آوردن (00) هستند تا اجرا شوند. 91 0 

صفحه 7:
زمانبندی با قبضه کردن | تصمیمات زمانبندی 70۳60) ممکن است تحت چهار شرط زیر اتخاذ شوند: ۷ وقتی که فرایندی از حالت اجرا به حالت انتظار می رود (مثل در خواست (1/6» یا فراخوانی انتظار برلی خاتمه یکی از فرایندهای فرزند). ”3 وقتی فرایندی از حالت اجرا به حالت آمادگی می رود (مثل وقتی که رویدادی رخ می دهد). 7 وقتی که فرایندی از حالت انتظار به حالت آمادگی می رود (مثل تکمیل 1/0). 7 وقتی که فرایندی خاتمه می یابد. 1 برای شرایط و 6 انتخابی بر حسب زمانبندی وجود ندارد اما برائ شرليط كو © امكان التخاب وجود دارد. وقتی زمانبندی تحت شرایط و *) انجام می گیرد» الگوی زمانبندی را بدون قبضه كردن می نامیم. و در غیر اینصورت. آنرا قبضه کردن می نامیم. 0 0 در زمانبندی بدون قبضه کردن وقتی 20*00) به فرلیندی تخصیص یافت» آنقدر آنرا نگه می دارد تا اينكه خاتمه يابد يا به حالت انتظار برود. متاسفانه زمانبندی با تبضه کردن هزینه دارد. زمانبندی با | قیضه کردن در طراحی هسته سیستم عامل موثر است. eo 

صفحه 8:
توريع کننده 1 توزيع كننده در زمانبندى 00000 دخالت دارد. توزيع كننده ييمانه اى است كه كنترل را به يردازنده اى مى دهد كه توسط زمانبند كوتاه مدت انتخاب شده است. اين عمل شامل موارد زير است: ۷ تعویض بستر 7 تغییر به حالت کاریر پرش به محل مناسبی در برنامه کاربر و آغاز مجدد آن برنامه ۷ توزیع کننده باید سرعت بالایی داشته باشد. 9 9 

صفحه 9:
معیاررهای زمانبندی | معیارهای متعددی برای مقایسه الگوریتم های زمانبندی پیشنهاد شده اند. معیارهای مورد استفاده عبارتند از: بارتند از: 7 بهره وری 00۳0 می خواهیم تا آنجا یی که ممکن است (0<6()مشغول باشد. توان عملیاتی (حاصل کار): اگر 6۳60) مشغول اجرای فرایندها باشد کاری درحال انجام است. یک معیار کارء تعداد فرایندهایی است که در واحد زمان کامل می شوند و توان عملیاتی نام دارد. 7 زمان برگشت: فاصله زمانی از زمان تحویل فرایند تا زمان کامل شدن اجرای آن؛ زمان برگشت نام دارد. زمان برگشت مجموع زمان انتظار برای قرار گرفتن در حافظه» زمان قرار گرفتن در صف آمادكى؛ اجرا در 00۳00 و عمل 1/0 است. ۲ زمان انتظار: معیار دیگر زمان تحویل یک درخواست و دریافت اولین پاسخ لست. اين معیاره زمان انتظار نام دارد. زمان لنتظار» مدت زمان لازم برای شروع پاسخ است و شامل زمان خروجی پاسخ نمی شود. 7 زمان پاسخ: معیار دیگر» زمان تحویل یک درخواست تا دریافت اولین پاسخ است. اين معیار که زمان پاسخ نام دارد» مدت زمانی است که مدت زمانی است که طول مى کشد پاسخ داده شود؛ نه ,ی مدت زمانی که طول می کشد تا آن پاسخ چاپ شود. مم 

صفحه 10:
1 زمانبندی ارائه خدمت 4 ‎(POPE) 3543 B85‏ در اين الگوریتم» فرایندی که زودتر 6000) را درخواست کرد زودتر آنرا در اختیار می گیرد. بياده سازى سياست 000208 با يك صف 10:0) انجام مى شود. مجموعه فرایندهای 0 7 ee ‎OF 6‏ زمان نفبار ‏اكر فرايندها به ترتيب ,م,نم,نم بيايند و به ترتيب 00009)) خدمات بكيرند نمودار به صورت زيراست: ‎ ‎ ‎ ‎ ‏۵ | و 9 ‏مه ۵ 5۴ © زمان انتظار برای ,6 برابر صفر ‎CP whe Py Gly‏ و برای پم برابر با 07۵ است. بنابراین» زمان ‎ar‏ میانگین برابر (۵6+0+/۲۵<6[/)8) است. ‎POPS Saree Sty ee 0‏ رکمینه نیست و ممکن است با تغییرات زیادی که ‏ی 17 ‏يكم فر موز ى #استكاهها و 00000 كاهش مى يابد. ‎00 / 0 ‎ ‎ 

صفحه 11:
1 زمانبندی بر حسب کوتاهترین کار (02ل6): 0 اين الگوریتم به هر فرایند. طول انفجار 000000 بعدى اش را مى دهد. وقتى 00000 مهيا باشد» به فرايندى نسبت داده مى شود كه انفجار 00800 بعدى كوجكترى داشته باشد. اكر طول انفجار ‎CPO‏ بعدى دو فرايند يكسان باشدء براى انتخاب يكى از آنهاء از زمانبندى 005)9)) استفاده مى شود. زمانبندى در اين الكوريتم با بررسى طول انجار (۳6)) بعدی فرایند انجام می شود (نه طول كلى آن). به عنولن مثال فرايندهاى زير را در نظر بكيريد: با استفاده از زمانبندى 9002© اين فرايندها بر اساس نمودار زير زمانبندى مى شوند: Pe Py Pe Pe er 6 3 8 © 0 ‏زمان انتظار براى فرايند ,) برابر با © براى ..8) برابر با ©1» براى ,4 برابر با © و براى .م) برابر با‎ ‏است. بنابراين ميانكين زمان انتظار برابر با (©+©5-0:/)0+6+0/ است.‎ ‏كرديم؛ ميانكين زمان انتظار برابر با 000.06 می شد.‎ (ge sale POPE ‏/ال از الكوى زمانبندى‎ eo 

صفحه 12:
] مشکل عمده الگوریتم 906۴) این است که در طول درخواست بعدی (650() باید مشخص باشد. برای زمانبند بلندمدت در یک سیستم دسته اى» حد زمانی را که کاربر هنگام تحويل كار تعيين کرده است به عنوان طول فرایند درنظر گرفته و سعی می شود که این حد زمانی دقيقا برآورد شود .زمانبندی *906) در زمانبندی بلندمدت کاربرد زیادی دارد. الگوریتم 906۴) نمی تواند در سطح زمانبندی کوتاه مدت به کار گرفته شود. زیرا طول انفجار بعدی را نمی دانیم اما می توانیم اندازه اش را پیش بینی کنیم. با تخمین این اندازه می توانیم فرایندی را محاسبه کنیم که طول انفجار بعدی آن کوتاهتر است. 1 انفجار محاسباتی بعدیء به صورت میانگین نمایی طول های محاسبه شده لنفجارهای محاسباتی قبلی پیش بینی می شود. فرض کنید ,) طول »امین انفجار محاسباتی و ,ر.7 مقدار پیش بینی شده برای انفجار محاسباتی بعدی باشد. آنگاه برای 00 < 0 > 0 فرمول زیر را تعریف می کنیم: 0۱+ 4-0 7, Tag = ‎Sie‏ شامل ‎gh 4 cal GLE AL! Oy fate‏ که ,7 سابقه گذشته را ذخیره می کند و تخمین »ام است. پارامتر 0 وزن نسبی سابقه فعلی و گذشته را در پیش بینی ما کنترل می كن ‎16۱ ‎۰0 ‎ 

صفحه 13:
1 شکل زیر یک میانگین نمایی را باه < نشان می دهد. مقدارم7 را می توان به صورت یک مقدار ثابت یا میانگین کل سیستم تعریف کرد. 2 ‎fe‏ + 8 6 / 4 2 هل زمان © © © © و ه هو انفجار محاسباتى() ‎wl‏ 6 0 وه و ۵ ۵ 9 4۵ پیش بینی (7) 0 

صفحه 14:
و اند 0 الكوريتم 900) ممكن است با قبضه كردن يا بدون قبضه كردن باشد. 1 براى زمانبندى *0ل9) با قبضه كردن *©0 فرآيند زير را درنظر بكيريد: 6 3 0 ‎6٠‏ 0 5 9 5 و 6 9 ۳ ا با استفاده از زمانبندى <900) با قبضه كردنء اين فرايندها بر اساس نمودار زير زمانبندى مى شوند: و ۳ ‎Py Ps Py‏ 70 0 01 ۴ 0 7 ميانكين زمان انتظار:((0-000)+(0-0)+(28)-©)+(0-6))/ 6-60 © ] در زمانبندی <96) بدون قبضه کردن میانگین زمان انتظار برابر با ۵.۳20 میلی ثانیه خواهد بود. ‎ey‏ 0 ۰0 

صفحه 15:
1 الگوریتم 906 حالت خاصی از الگوریتم زمانبندی اولویت است. به هر فرایند یک اولویت نسبت داده می شود و (۳60)() به فرایندی تخصیص می یابد که بالاترین اولویت را دارا باشد. فرایندهایی با اولویت یکسان؛ به ترتیب ۳)()۳69) زمانبندی می شوند. ] به عنوان مثال» فرایندهای زیر را در نظر بگیرید. به طوری که در زمان صفر به ترئتیب ...بم),۳) رسیده اند: ری 8 10 ,@ 0 0 0 ‎e, e «e‏ ‎Py q 9‏ ‎e, 9 e‏ ‎Ul‏ با استفاده از زمانبندی اولویت اين فرایندها بر اساس نمودار زیر زمانبندی می شوند: ‎ ‎ ‎ ‎ ‎ ‏هاوه ۳ و اوه ‎a 9 0‏ 1 میانگین زمان انتظار در اين مثال» 0.0 میلی ثانیه لست. ‎o‏ ‎9۸ ‎9 ‎ ‎ 

صفحه 16:
زمانبندی اولویت (ادامه ...) 0 زمانبندی اولویت می تواند با قبضه کردن يا بدون قبضه کردن باشد. مسئله عمده در الگوریتم زمانبندی اولویت انسداد نامحدود یا گرسنگی(قحطی)است. الگوریتم زمانبندی اولویت می تواند منجر به این شود که فرایندهایی با اولویت پایین» به مدت نامحدودی منتظر (2080) باشند. در یک سیستم کامپیوتری با بار زیاد» فرایندهایی با اولویت بالاء مانع از اين می شوند که 00000 به فرايندهايى با اولويت پایین تعلق یابده که ممکن است فرایند با تاخیر بسیار زیادی انجام شود و یا اينکه سیستم از کار بیافتد و تمام فرایندهای با اولویت پایین؛ از بين بروند. 1 راه حل مسئله انسداد نامحدود با اولویت پایین» کهنگی است. در این تکنیک. اولویت فرایندی که به مدت زیادی در سیستم منتظر مانده است. به تدریج افزايش می یابد. aol 0 

صفحه 17:
7 الگوریتم نوبت گردشی (001)) مخصوص سیستم های اشتراک زمانی طراحی شده است. این الگوریتم شبیه 3)(669) است با اين تفاوت که در حرکت بین فرایندهاء از زمانبندی قبضه کردن استفاده می شود. یک واحد زمانی کوچک؛ به نام کوانتوم زمانی یا برهه زمانی تعریف می شود. صف آمادگی به صورت یک صف چرخشی در نظر گرفته می شود. زمانبند (6)() در طول صف آمادگی حرکت می کند و (600() را حداکثر به مدت یک کوانتوم زمانی به هر فرایند تخصیص می دهد. میانگین زمان انتظار در الگوریتم 6808» اغلب زیاد است. فرایندهای زیر را درنظر بگیرید که در زمان () می رسند: با استفاده از زمانبندی ۰430 این فرایندها بر اساس نمودار زیر زمانبندی می شوند: ‎e, | ® ©,‏ © | وه | وه | مه ‎do ar 60 ee 80 90‏ 5 م 17 ‎off!‏ زمان انتظار در اين مثالء ©©. 3-6 ميلى ثانيه است. 

صفحه 18:
2 0 222 (... ais) (RR) A زمانبندی نوبت | در الگوریتم زمانبندی نوبت چرخشی» 26000) به هیچ فرایندی در یک سطر. بیش از یک کوانتوم زمانی تخصیص نمی یابد. اگر انفجار محاسباتی فرایندی بیش از یک کوانتوم زمانى شود أن فرايند قبضه می شود و در انتهای صف آمادگی قرار می گیرد. الكوريتم صف ‎(RR‏ با قبضه کردن همراه است. لا کارایی الگوریتم ‎616٩‏ به اندازه کوانتوم زمانی بستگی دارد. از یک طرف اگر کوانتوم زمانی بسیار بزرگ باشد (نامحدود)» سیاست 6۲) شبیه ۳)()۳6۵) خواهد بود. اگر کوانتوم زمانی خیلی کوچک باشد اینطور وانمود می شود كه هر فرايند؛ پردازنده مخصوص به خودش را دارد که سرعت هرکدام به اندازه سرعت پردازنده واقعی است. 9۸ 0 

صفحه 19:
در نرم افزار باید اثر تعویض بستر را در کارایی زمانبندی 808) درنظر بگیریم. فرض می کنیم فقط ی فرایند با (0) واحد زمانی داریم. اگر کوانتوم زمانی برابر با 40 واحد زمانی باشد» فرایند در کمتر از یک کوانتوم زمانی خاتمه می یابد و سرباری ندارد. لگر کوانتوم زمانی برابر با 0 واحد زمانی باشده اين فرایند به دو کوانتوم زمانی نیاز دارد و منجر به تعویض بستر می شود. اگر کوانتوم زمانی برابر واحد زمانی باشد» نیاز به 6 تعویض بستر است و بدین ترتیب اجرای فرایند کند می شود. بنابرلين؛ ب مقابله با تعویض بسترء علاقه مند هستیم که کوانتوم زمانی بزرگ باشد. تعویض بستر ‏ کوانتوم زمانی زمان‌فرلیند 40 oO de {ao 1 @m@ eee? ‏ا © 6 © و و‎ eo 

صفحه 20:
& 12.0 2 115 3002 9 2 10.5 10.0 ميانكين زمان برگشت 95 7 6 5 4 3 2 1 20 کوانتوم زمانی 0 

صفحه 21:
تغییر زمان برگشت بر اساس کوانتوم زمانی (توضیح شکل) | زمان نیز به اندازه کوانتوم بستگی دارد. همانطور که از شکل پیداست» میانگین زمان برگشت مجموعه ای از فرایندهاء با افزایش اندازه کوانتوم زمانی» الزاما بهبود نمی یابد.به طور کلی» میانگین زمان برگشت در صورتی بهبود می یابد که اغلب فرایندها انفجار محاسباتی بعدی خودشان را فقط در یک کوانتوم زمانی به اتمام برسانند. ] با درنظر گرفتن زمان تعوبض بستر» هرچه کوانتوم زمانی کوچکتر باشد» میانگین زمان برگشت افزایش می یابده زیرا نیاز به تعویض بستر بیشتری است. از طرف دیگر اگر کوانتوم زمانی بسیار بزرگ باشده زمانبندی ‎)۷6٩‏ به ۳606۳69) تبدیل می شود. 601 266 

صفحه 22:
زمانبندی صف چندسطحی 1 دسته دیگری از الگوریتم های زمانبندی برای وضعیت هایی ایجاد شدند که در آنها» فرایندها می توانند به دو گروه تقسیم شوند. [] الگوریتم زمانبندی صف چندسطحی؛ صف آمادگی را به چند بخش مجزا تقسیم می کند. 1 هر فرایند بر اساس خواصی که دارد در صفی قرار می گیرد . اين صفات عبارتند از: اندازه حافظه. اولویت فرایند یا نوع فرایند. هر صف الگوریتم زمانبندی خاص خودش را دارد. علاوه بر اين» ‎gu‏ صف ها نیز باید زمانبندی وجود داشته باشد که بر اساس زمانبندی همراه با قبضه کردن و با اولویت ثابت پیاده سازی می شود. 0 امكان ديكرء استفاده از برهه زمانی در صف را به خود اختصاص می دهد و بین فرایندهای مختلف آن صف زمانبندی می کند. صف ها است. هر صف بخشی از زمان 991 0 

صفحه 23:
فا رداق ۳ ‎SS‏ > > سا كد فرایندهای دسته ای د فرايندهاى دانشجو ‎a SI‏ — پایین ترین اولویت تب اين شكل هر صف نسبت به صف های با اولویت پایین تر» اولویت مطلقی دارد. 60 

صفحه 24:
] معمولا در الگوریتم زمانبندی صف چندسطحی فرایندها هنكام ورود به سیستم در صفی قرار می گيرند. به طوری که از صفی به صف دیگر نمی روند. اما زمانبندی صف بازخوردی چندسطحی به فرایندها اجازه می دهد از صفی به صف دیگر منتقل شوند. 1 قلسفه اين كار اين است که ویژگی های انفجاررهای محاسباتی فرایندها با یکدیگر متفاوت است. اگر فرایندی به مدت زیادی 20۳60) را در اختیار گیرد» به صفی با اولویت پایین تر منتقل می گردد. بدين ترتيب» فرایندهای مقید به 41/0 و محاوره ایء در صف هايى با اولویت بالا قرار می گیرند. / به طور مشابه» فرایندی که به مدت زیادی در صفی با اولویت پایین تر منتظر می ماند» ممکن است به صفی با اولویت بالاتر منتقل شود. در این شکل کهنگی» از مشکل , م‌گرسنگی جلوگیری می شود. 0 

صفحه 25:


صفحه 26:
زمانبندی صف بازخوردی چندسطحی (ادامه ...) 1 به طور کلی» زمانبند صف بازخورد چندسطحی, توسط پارامترهای زیر تعریف می شوند: ۷ تعداد صف ها. 7 الگوریتم زمانبندی برای هر صف. 7" روشی که تعیین می کند چه هنگامی یک فرایند با صفی با اولویت بیشتر منتقل شود. ” روشى كه تعيين مى كند جه هنگامی یک فرایند با صفی با اولویت کمتر متثقل شود. ۷ روشی که تعیین می کند فرایندی که نیاز به خدمات دارد» به جه صفى وارد شود. |العباين الكوريتم مى تواند طوری پیکربندی شود که با سیستمی که درحال طراحی 0است سازگاری داشته باشد. 

صفحه 27:
زمانبندی چندپردازنده ای 1 اگر چندین (0<00() در سیستم وجود داشته باشند. مسئله زمانبندی پیچیده تر می شود. | در سیستم های چندپردازنده ای سیستم های همگن (کارایی پردازنده در آن یکسان است) را درنظر می گیریم. هر پردازنده آماده می تواند هر فرایند موجود در صف را اجرا کند. فرض می کنیم دستیابی به حافظه به طور یکنواخت صورت می گیرد. در سیستم های همگن که پردازنده های آنها متفاوتند فقط برنامه هایی که برای پردازنده کامپایل شده اند بر روی آنها قابل اجرا می باشند. در پردازنده های همگن (کارایی پردازنده آنها یکسان است) نیز محدودیت هایی برای زمانبندی وجود دارد. در یک دستگاه 41/0 که به یک گذرگاه اختصاصی یک پردازنده وصل شده است فرایندهایی می خواهند از اين دستگاه استفاده کنند زمانبندی شوند تا بر روی آن پردازنده اجرا شوند در غیراینصورت قادر به استفاده از آن دستگاه نخواهند رت eo 

صفحه 28:
زمانبندی چندپردازنده ای (ادامه ...) 1 اگر چند پردازنده همگن در سیستم موجود باشند» مسئله اشتراک بار پیش خواهد آمد. می توان برای هر پردازنده یک صف جداگانه درنظر گرفت. 1 در اين الكوء می توان از دو روش زمانبندی استفاده کرد. در روش اول» هر پردازنده خودش را زمانبندی می کند. برای اين منظور» هر پردازنده صف آمادگی مشترک را بررسی می کند و فرایندی را برای اجرا انتخاب می کند. 1 در روش دوم» یک پردازنده می تواند پردازنده دیگر را زمانبندی کند و بدین ترتیب یک ساختار رئیس/مرئوس به وجود می آید. 99 0 

صفحه 29:
زمانبندی بی درنگ 1 محاسبات بی درنگ بر دو نوع اند. سیستم های بی درنگ سخت لازم است یک وظیفه حیاتی؛ در زمان معینی به اتمام برسد. معمولا فرایند همراه با مدت زمان موردنیاز برای کامل شدن آن یا اجرای 1/0» به پردازنده تحویل داده مى شود. زمانبند ممكن است فرایند را بپذیرد و تضمین کند که آن فرایند به موقع به اتمام برسد» یا در صورت غیرممکن بودن اجرای آن» از پذیرفتتش خوددارى كند. اين عمل رزرو كردن منبع نام دارد. ] محاسبات بی درنگ نرم محدودیت کمتری دارد. این محاسبات مستلزم این است که فرایندهای حیاتی اولویت بیشتری داشته باشد. پیاده سازی عملیات بی درنگ نرم مستلزم طراحی دقیق زمانبند و جنبه های دیگری از سیستم عامل است که به زمانبند مرتبط هستند. اولا سیستم مانبندی اولویت داشته باشد و فرایندهای بی درنگ بالاترین اولویت را دارا باشند. ثانیا تاخیر توزیع باید کوچک باشد. ear eo 

صفحه 30:
0 ار عن يوان مطملن و و در اطمینان از ویژگی دوم كمى بيجيده است زيرا اغلب سيستم هاى عامل مجبور مى شوند كه قبل از تعويض بستر منتظر بمانند تا يك فراخوان سيستم كامل شود يا عمل 41/0 مسدود كردد. تاخير توزيع در اين سيستم ها مى تواند طولانى باشد. ل براى اينكه تاخير توزيع اندك باشدء فراخوان سيستم بايد قابل قبضه شدن باشد. براى رسيدن به اين هدف مى توان به روش هاى كوناكونى عمل كرد. يك روش اين است كه در فراخوان های سیستم طولانی از نقاط قبضه شدن استفاده كردد كه در اين نقاط كنترل مى شود كه آيا لازم است فرايندى با اولويت بالا اجرا شود يا خير. راه حل ديكر اين است كه كل هسته قابل قبضه شدن باشد. اگر فرایندی با اولویت بالا نیاز به خواندن و تغيير ساختمان داده اى از هسته داشته باشد كه در حال حاضر در اختيار فرايندى با اولويت كمتر استء جه اتفاقى مى افتد؟ فرايندى با اولويت بالاتر منتظر مى ماند تا فرايندى با اولويت بالاتر به اتمام برسد. اين وضعيت را اولويت معكوس مى نامند. / ه60 6م 

صفحه 31:
زمانبندی بی درنگ (ادامه ...) 1 اين مسئله را می توان از طریق پروتکل ورائت اولویت حل کرد که در آن تمام فرایندهایی که منابعی را دراختیار دارند که مورد نیاز فرایندی با اولویت بالاتر است؛ اولویت بالا را به ارث ببرند تا منابع موردنظر را دراختیار گیرند. وقتی کارشان انجام شد. اولویت اولیه خود را دارا خواهند شد. ] مرحله برخورد تاخیر توزیع دارای دو مولفه است: 7 قبضه کردن هر فرایندی که در هسته درحال اجراست. ” فرایندهایی با اولویت پایین ترء منابع موردنیاز فرایندهای با اولویت بالاتر را رها می 91 0 

صفحه 32:
پاسخ به رویداد پردازش وقفه ‎ws‏ برخوردها ‏98۱ تسم ‎eo‏ زمان 

صفحه 33:
+ 2 - ۰ اه و ارزیابی الگوریتم های زمانبندی | اولین مسئله. تعیین معیارهای انتخاب الگوریتم است. معیارهای ما ممکن است شامل مقباس های گوناگونی باشد: ‎Y‏ بیشترین بهره وری (6۳0) در حالتی که حداکثر زمان پاسخ برابر با 4 ثانیه است. ۲ بیشترین توان عملیاتی. به طوری که میانگین زمان برگشت. به طور خطی مناسب با كل زمان اجراست. | پس از تعریف معیارهای انتخاب؛ آنها را با ملاحظات خاصی بررسی می کنیم. 99 0 

صفحه 34:
مدلسازی قطعی 1 یکی از مهمترین روش های ارزیابی الگوریتم هاء ارزیابی تحلیلی نام دارد. ارزیابی تحليلى؛ با استفاده ار الگوریتم و بارکاری سیستم» فرمول یا عددی را تولید می کند که کارایی الگوریتم را برای آن بار سیستم ارزیابی می کند. یک نوع ارزیابی تحلیلی به نام مدلسازی قطعی است. این روش یک بار کاری از قبل تعیین شده ای می كيرد کارایی هر الگوریتم را برای آن بار کاری تعریف می کند. 1 به عنوان مثال 0 فرایند زیر را در نظر بگیرید که همگی در زمان صفر وارد می شوند: = 0 0 انفجار محاسبتی 66 / 

صفحه 35:
مدلسازی الكوريتم 0:00:08 وه ۶ | وه و T ۹ ۳ 99 do )000+۵ ‏میانگین زمان انتظار: مود مر زوم + هبو‎ ] Pe ‏و نا‎ Pe :)006 ‏الگوریتم‎ 7 9 10 9 9 ميانكين زمان انتظار: (60+6+0+۵6+00) 49-9 0 الكوريتم 0408 (با كوانتوم زمانى 000 ميلى ثانيم): ,© | و6 || مه | وه | وه | Se] BD 0 po 998 00 0 oO 1 میانگین زمان انتظار: (69-6/)60+۵+60+۵6+۵ | ربا این ارزیابی ها مشاهده می کنیم که در این حالت میانگین زمان انتظار نصف زمانبندی 5-8 0005" است و مقدار آن در الگوریتم ‎)6٩‏ متوسط است. 20 

صفحه 36:
مدلسازی قطعی (ادامه ...) ] مدلسازی قطعی. سریع و ساده است. اعداد دقیقی را ارائنه می کند که برای مقایسه الگوریتمها به کار می روند. ولی به تعداد دقیقی از ورودی ها نیاز دارد و پاسخ آن نیز برای همان ورودی ها صادق است. 0 کاربردهای مدلسازی قطعیء توصیف الگوریتم های زمانبندی و ارائه مثال هاست. در مواردی که یک برنامه باید بارها و بارها اجرا شود و نیازمندی های پردازش آن دقیقا قابل سنجش باشده استفاده از مدلسازی قطعی برای انتخاب الگوریتم زمانبندی» مناسب اسث. با اجرإى مناسازى قطعى بر روى متال.هاى.متفاوت رفتار هابى مشاهده مي شود كه به طور جداكانه قابل تحليل و اثبات خواهند بود. 99 0 

صفحه 37:
سيستم کامپیوتری به صورت شبکه ای از کارگزاران توصیف می گردد. هر کارگزار صفی از فرایندهای درحال انتظاردارد. ‎Gul GEIS CPO‏ که دارای صف آمادگی است و سیستم 1/0 نیز دارای صف های دستگاه است. با داشتن نرخ رسیدن فرایندها و نرخ های خدمات» می توان بهره وری» میانگین طول صف میانگین زمان انتظار و غیره را تعیین کرد. اين روش را تحلیل شبکه صف بندی می نامند. تحلیل صف در مقایسه الگوریتم های زمانبندی مفید واقع می شوف اما محدودیت هایی دارد. فعلا الگوریتم ها و توزیع هایی که می ت کار کردن با ریاضیات الگوریتم ها یا توزیع های پیچیده. دشوار است. تحلیل صف بندی نیتزمند ساخت فرضیه های مستقلی است که ممکن است دقیق نباشند. به طور کلی. مدل های صف» تقریبی از سیستم واقعی را نشان می دهد. در نتیجه؛ دقت محاسبات آن زیر سوال است. پردازش شوند. بسیار محدود است. ors 0 

صفحه 38:
شبیه سازی ها براى ارزيابى دقيق تر الگوریتم های زمانبندی» می توانیم از شبیه سازی لستفاده کنیم. شبیه سازی مستلزم برنامه نویسی یک مدل سیستم کامپیوتری است. ساختمان داده های نرم افزاری؛ اجزای اصلی یک سیستم را می سازند. داده های شبیه سازی به روش های گوناگونی تولید می شوند. متداولترین روش لستفاده از مولد اعداد تصادفی است که برای تولید فرایندهاء زمان های ‎ula dj OPO jedi!‏ رسیدن فرایندهاء زمان های خروج و غیره برحسب توزیع های احتمالی به کار می رود. | شبیه سازی برحسب توزیع» مکن است به دلیل رولبط بین رویدادهای متوالی در سیستم واقعیء دقیق نباشد. توزیع فراوانی فقط نشان می دهد که هر رویداد چقدر لتفاق می افتد و چیزی در مورد ترتیب وقوع آنها ارائه نمی کند. برای حل اين مسئله از نوارهای ردیابی استفاده می شود. نولر ردیابی با نظارت بر سیستم واقعی و ثبت دنباله ای از رویدادهای واقعی ایجاد می شود. این روش می تواند نتایج دقیقی را بری وردی هايش ایجاد کند. شبیه سازی می تواند گران تمام شود. زیرا گاهی ساعت ها وقت کامپیوتر را به خود اختصاص می دهد. 99 0 

صفحه 39:
آمارهای کارایی برای ‎ORG‏ آمارهای کارایی برای ‎Ge‏ آمارهای کارایی برای ‎RRP)‏ 99 9 enone) 055 096 25 6 0م00 ۰ 1/0 9 9 نوار ردیابی اجرای فرایند واقعی 

صفحه 40:
شبیه سازی نیز دقت محدودی دارد. دقیقترین روش ارزیابی الگوریتم های زمانبندی؛ نوشتن به کارگیری آن در سیستم و مشاهده عملکرد آن است. دراین روش, الگوریتم واقعی در واقعی اجرا و ارزیابی می شود. | مشکل این روش» هزینه آن لست. هزینه این روش, نه تنها به نوشتن الگوریتم و اصلاح سیستم عامل برای پشتیبانی از آن و ساختمان دلده های مربوط به آن مربوط می شود بلکه تعامل کاربران با سیستم عاملی که هميشه در حال تغییر است» مربوط می شود. سیستم عاملی که دانما تغییر می کند» نمی تواند برای اجرای کار کاربران به آنها کمک کند. 1 مشکل دیگر لرزیابی انگوریتم این است که محیطی که الگوریتم در ان به کار گرفته می شوده تغییر می کند. تغییر محیط فقط ناشی از نوشتن برنامه های جدید و تغییر انواع مسئله ها نیست. بلکه به کارایی زمانبند نیز مربوط می شود. اگر قابلیت انعطاف الگوریتم های زمانبندی زیاد باشد» مدیران سیستم یا کاربران می توانند آنها را تغییر دهند. متاسفانه. سیستم های عامل اندکی از اين نوع زمانبندی قابل تنظیم را مجاز می ‎RD /‏ eo 

صفحه 41:
1 مدل های زمانبندی فرایند در اين بخشء زمانبندی فرایند را در سیستم های سولاریس ۰ ویندوز 600060 و لینوکس بررسی خواهیم کرد. قبل از پرداختن به این مدل ها بندها را با زمانبندی فرایند ارتباط می دهیم. در فصل 0 بندها را در مدل فرایند معرفی کردیم و در نتیجه هر فرایند می تولند چندین بند از کنترل را در اختیار داشته باشد. بندهای سطح کاربر توسط کتابخانه بندها مدیریت می شود و هسته از آنها خبر ندارد. برای اجرا شدن بر روی (6۳0()» بندهای سطح کاربر به بند هسته مربوطه نگاشت می شود» ممکن است این نگاشت به طور غیرمستقیم و از طریق فرایند سبک ‎AU LOP)‏ کتابخانه بنده بندهای سطح کاربر را طوری زمانبندی می کند که بر روی 6۳()ر| آماده اجرا شوند. اين طرح زمانبندی محلی فرایند نام دارد که در آن زمانبندی بند در یک برنامه کاربردی به طور محلی صورت می گیرد. هسته با استفاده از زمانبندی سراسری سیستم تصمیم می گیرد که کدام بند هسته باید زمانبندی شود. ۹ 0 

صفحه 42:
سولاریس © سولاریس 0 از زمانبندی مبتنی بر اولویت فرایندها استفاده می کند. چهار رده از زمانبندی را در اختیار دارد که به ترتیب اولویت عبارتند از: بی درنگ» سیستم» اشتراک زمانی و محاوره ای. هر رده شامل اولویت ها و الگوریتم های زمانبندی مختلفی است» ولی اشتراک زمانی و محاوره ای از یک سیاست زمانبندی استفاده می کنند. | فرایند با یک 06۳)را شروع می شود و قادر است در صورت تیاز 6()راهای جدیدی ایجاد کند. هر 00)ا» رده زمانبندی و اولویت فرایند پدر را به ارث می برد.رده زمانبندی فرضی برای فراینده اشتراک زمانی است. به طور پیش فرض رابطه معکوسی بین اولوبت ها و برش های زمانی وجود دارد. | سولاریس 0 برای اجرای فرایندهای هسته از رده سیستم استفاده می کند. سیاست زمانبندی برای رده سیستم. برش زمانی نیست. بند متعلق به رده سیستم آنقدر اجرا می شود تا متوقف شود یا توسط بندی با اولویت بیشتر قبضه گردد. 9 0 

صفحه 43:
i. aia) 8 ‏سولاریس‎ در رده بی درنگ بندها بلاترین اولویت را دارند. فرايندهاى اين رده قبل از فرايندهاى موجود در رده هاى ديكر لجرا مى شوند. به طور کلی» تعداد اندکی از فرایندها به رده بی درنگ تعلق دارند. ‎fl‏ هر رده زمانبندی شامل مجموعه ای از اولیتها است. اماء زمانبند اولویت های ویژه رده را به اولویت های سراسری تبدیل می کند و بندی را برای انتخاب اجرا می کند که اولویت سراسری آن بالاترین است. بند انتخاب شده در 00۳60 اجرا می شود تا یکی از موارد رخ دهد: ‏7# ماود شود ‏از برش زمانی خود استفاده کند (اگر بنده سیستم نیست). ‏۷ توسط بندی با اولویت بالاتر قبضه شود. ‎ ‏1 اگر لولویت چندین بند یکسان باشد» زمانبند از صف نوبت چرخشی استفاده می کند. ‎9 ‎0 

صفحه 44:
ار صف اجرا رده های زمانبند اولويت ويزه رده ترتيب زمانبندی ws) = 7 ‏بی درنگ‎ a Uy sa Aah Lg ‏هویی‌درنگ‎ 0 بندهای خدمات هسته بنهای سطح هسته محاوره ای و اشتراک زمانی محاوره ای و ۱,0 های اشتراک زمانی ۰ si ‏هم آخری‎ اولويت سراسرى بالاترين بايين ترين 

صفحه 45:
ویندوز 560060 ! ویندوز 0000000 بندها را با استفاده از الگوریتم زمانبندی قبضه کردن مبتنی بر اولویت» زمانبندی می کند. زمانبند ویندوز 60606060 تضمین می کند که بندی با بالاترین اولویت هميشه اجرا می شود. بخشی از هسته ویندوز ‎CODD‏ که زمانبندی را لنجام می دهد» توزیع کننده نام دارد. بندی که توسط توزیع کننده برلی اجرا انتخاب شد. آنقدر اجرا می شود تا توسط بندی با اولویت بالاتر قبضه شود؛ خاتمه یابد» کوانتوم زمانی آن به پایان برسد. یا فراخوان سیستم مسدود کردن را اجرا نماید. ویندوز 07600060 تضمین نمی کند که یک بند بی درنگ دراثنای محدوده زمانی خاصی اجرا شود. توزیع کننده از طرح اولویت ‎abe OC‏ برای تیب اجرلی بندها استفاده می کند. اولویت ها به دو رده تقسیم می شوند: رده متغير و رده بی درنگ. توزیع کننده مجموعه ای از صف ها را از بالاترین به پایین ترین اولویت پیمایش می کند تا بندی را بیابد که آماده اجرا است. اگر هیچ بندی آماده ای پیدا نشود» توزیع کنندهف بند ویژیه ای را با نام بند بیکار را اجرا می نماید. اولویت هر بند به رده اولویتی که به آن تعلق دارد» و به اولویت نسبی در داخل آن رده بستگی دارد. هر بند دارای یک اولویت پایه است. 9 €o 

صفحه 46:
1 وقتی کوانتوم زمانی بندی به اتمام برسد. آن بند دچار وقفه می شود. اگر آن بند در رده اولویت متغیر باشد» اولویت ان کاهش می یابد. اولویت هیچگاه از اولویت پایه کمتر نمی شود. وقتی بندی با اولویت متغیر از یک عملیات انتظار آزاد می شود» توزیع کننده اولویت انرا افزایش فى دهد. | ويندوز (00000© بين فرايند بيش زمينه و بس زمينه تمايز قائل مى شود. فرايند بيش زمينه اجازه دارد قبل از وقوع قبضه كردن اشتراک زمانیء سه برابر بيشتر اجزا شود. ‎Soa‏ بل ‎od ‎3 ‎é ‏ترمال ‏06 ‏آولویت بیکار 6 بحران زماتی ‎po ‏بالقر از ترمال ترمل ‏كد |6 |6 |8 ۵ 8 ‏ه (© (ه أه ‏زیر رمل ‎a ‎8 ‏8 هه اه هاه 8 أه & 8 2 2 9 ۱ه اد ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 47:
لینوکس دو الگوریتم زمانبندی را برای فرایندها ارائه می دهد. یکی از آنها الگوریتم اشتراک زمانی منصف برای زمانبندی قبضه کردن بین چندین فرایند است. دیگری مربوط به وظایف بی درنگ است که در ان اولویت های مطلق مهمتر از منصفانه است. لینوکس اجازه می دهد که فقط فرایندهایی که در حالت کاربر اجرا می شوند. قبضه گردند. اگر فرایندی در حالت هسته درحال اجرا باشده حتی اگر فرایند بی درنگی با اولویت بتلاتر آماده شود؛ نمی تواند آنرا قبضه کند ل اولین رده زمابندی مربوط به فرایندهای اشتراک زمانی است. از نظر سنتی, لینوکس برای فرایندهای اشتراک زمانی از الگوریتم مبتتی بر اعتبار استفاده می کند. این الگوریتم دو عامل را ترکیب می کند: سابقه و اولویت فرایند. سیستم اعتباردهی به طور خودکار» اولویت های بالا را به فرایندهای محاوره ای و مقید به می دهد. علتش این است که زمان پاسخ اين فرایندها مهم است. استفاده از اولویت فرایند در محاسبه اعتبارلت جدید. موجب می شود تا اولویت یک فرایند. قابل تنظیم باشد. ee / 0 

صفحه 48:
لینوکس (ادامه ‎ae‏ | لینوکس دو رده از زمانبندی بی درنگ را پیاده سازی می کند که موردنیاز 2009.0 است: خدمات به ترتيب ورود (0*00208) و نوبت كردشى (۲09)). زمانبندى بى درنك لينوكسء زمانبندى نرم است. كد هسته لينوكسء نمى تواند توسط كد حالت كاربر قبضه شود. اگر وقتی که هسته در حال اجرای فراخوان سیستم در فرایند دیگری باشد. وقفه ای به یک فرایند بی درنگ وارد شود؛ اين فرایند بی درنگ باید منتظر بماند تا فراخوان سیستمی که در حال لجراینت کلمل یا معیدود شود. 9 0 

صفحه 49:
اعضای گروه: ۰ جهو مهسا فرجو * سهیلا ابراهیمی صبا * * مهشید ابراهیم تژاد 

صفحه 50:
80 

به نام خدا اصول و مفاهیم طراحی سیستم های عامل خالصه فصل ششم 1 / 48 زمانبندی CPU زمانبندی ،CPUاساس سیستم های عامل چندبرنامه ای است .با حرکت CPUبین فرایندها، سیستم عامل می تواند بهره وری کامپیوتر را افزایش دهد. مفاهیم اساسی زمانبندی : ه00دف چندبرنام00ه ای این اس00ت ک00ه همیش00ه چن00دین فراین00د در ح00ال اج00را باش00ند ت00ا به00ره وری ‏CPUبیشینه شود .اگر فرایندهای بیشتری وجود داشتند ،بقیه منتظ00ر می مانن00د ت00ا CPUآزاد شود و بتواند دوباره زمانبندی شود. ایده چندبرنامه ای ساده است .هر فرایند به اجرایش ادامه می ده00د ت00ا ب00رای ی00ک عم00ل I/Oدر انتظار بماند. در یک سیستم کامپیوتری ساده ،در این مدت CPUباید بیکار بماند .بن00ابراین ،تم00ام این زم00ان های انتظار هدر می روند ،یعنی کار مفیدی انجام نمی شوند .در چندبرنام00ه ای ،س00عی می ش00ود که از این زمان ها به نحو احسن استفاده شود. 2 / 48 چرخه انفجار CPU-I/O موفقیت زمانبندی CPUبه این خاصیت فرایندها بستگی دارد که اجرای فراین00د ش00امل چرخه ای از اجرای CPUو انتظار I/Oاست. اجرای فرایند با انفجار CPUش00روع می ش00ود .ب00ه دنب00ال آن ی00ک انفج00ار I/Oق00رار دارد و به همین ترتیب ادام0ه می یاب0د .س0رانجام ،آخ0رین انفج0ار CPUب0ا درخواس0ت سیستم برای خاتمه اجرا ،پایان می پذیرد. مدت این انفجارهای CPUاندازه گیری شده اند و این مدت ها از فراین00دی ب00ه فراین00د دیگر و از کامپیوتری به کامپیوتر دیگر فرق می کند. 3 / 48 . . . I/O وCPU دنباله ای از انفجارهای Load store Add store Read from file CPU انفجار I/O انتظار برای I/O انفجار Store increment Index Write to file CPU انفجار I/O انتظار برای I/O انفجار Load store Add store Read from file I/O انتظار برای . . . CPU انفجار I/O انفجار 4 / 48 چرخه انفجار CPU-I/O زمان های انفجار CPU برنامه مقید به I/Oمعموال دارای چند انفجار کوچک CPUاست .برنامه مقید به CPUمعموال چند انفجار بلند CPUدارد .این توزیع می تواند در انتخاب الگوریتم زمانبندی CPUمهم باشد. فرکانس 5 / 48 مدت انفجار (میلی ثانیه) زمانبندی CPU هروقت CPUبیکار می شود ،سیستم عامل باید یکی از فراین00دهای موج00ود در ص00ف آمادگی را برای اجرا انتخ0اب کن0د .این انتخ0اب توس0ط زمانبن0د کوت0اه م0دت (ی0ا زمانبن0د )CPUانجام می گیرد .زمانبند ،فراین00دی را از بین فراین00دهای موج00ود در حافظ0ه ک00ه آمادگی اجرا دارند انتخاب می کند و CPUرا به ان تخصیص می دهد. از نظر مفه00ومی ،تم00ام فراین00دهای موج00ود در ص00ف آم00ادگی ،منتظ00ر ب00ه دس00ت آوردن CPUهستند تا اجرا شوند. 6 / 48 زمانبندی با قبضه کردن تصمیمات زمانبندی CPUممکن است تحت چهار شرط زیر اتخاذ شوند: وقتی که فراین0دی از ح00الت اج0را ب0ه ح0الت انتظ0ار می رود (مث0ل در خواس0ت ،I/Oی0ا فراخ0وانی انتظار برای خاتمه یکی از فرایندهای فرزند). وقتی فرایندی از حالت اجرا به حالت آمادگی می رود (مثل وقتی که رویدادی رخ می دهد). وقتی که فرایندی از حالت انتظار به حالت آمادگی می رود (مثل تکمیل .)I/O وقتی که فرایندی خاتمه می یابد. برای شرایط 1و ،4انتخابی بر حسب زمانبندی وجود ندارد اما برای ش00رایط 2و 3امک00ان انتخ00اب وجود دارد .وقتی زمانبندی تحت شرایط 1و 4انجام می گیرد ،الگوی زمانبندی را بدون قبضه کردن می نامیم .و در غیر اینصورت ،آنرا قبضه کردن می نامیم. ‏ در زمانبندی بدون قبضه کردن وقتی CPUبه فرایندی تخصیص یافت ،آنقدر آن00را نگ00ه می دارد ت00ا اینکه خاتمه یابد یا به حالت انتظار برود .متاسفانه زمانبندی با قبضه ک00ردن هزین00ه دارد .زمانبن00دی ب00ا قبضه کردن در طراحی هسته سیستم عامل موثر است. 7 / 48 توزیع کننده توزیع کننده در زمانبندی CPUدخالت دارد .توزیع کننده پیمانه ای است که کنترل را به پردازنده ای می دهد که توسط زمانبند کوتاه مدت انتخاب شده اس00ت .این عم00ل ش00امل موارد زیر است: تعویض بستر تغییر به حالت کاربر پرش به محل مناسبی در برنامه کاربر و آغاز مجدد آن برنامه توزیع کننده باید سرعت باالیی داشته باشد. 8 / 48 معیارهای زمانبندی معیارهای متعددی برای مقایسه الگوریتم های زمانبن00دی پیش00نهاد ش00ده ان00د .معیاره00ای م00ورد اس00تفاده عبارتند از: بهره وری :CPUمی خواهیم تا آنجا یی که ممکن است CPUمشغول باشد. توان عملیاتی (حاصل کار) :اگر CPUمشغول اجرای فراین00دها باش00د ،ک00اری درح00ال انج00ام اس00ت. یک معیار کار ،تعداد فرایندهایی است که در واحد زمان کامل می شوند و توان عملیاتی نام دارد. زمان برگشت :فاصله زمانی از زمان تحویل فرایند تا زمان کامل شدن اجرای آن ،زمان برگشت ن00ام دارد .زمان برگشت مجموع زمان انتظار برای قرار گرفتن در حافظه ،زمان ق00رار گ00رفتن در ص00ف آمادگی ،اجرا در CPUو عمل I/Oاست. زمان انتظار :معیار دیگر زمان تحویل یک درخواست و دریافت اولین پاسخ است .این معیار ،زم00ان انتظار نام دارد .زمان انتظار ،مدت زمان الزم برای شروع پاسخ است و شامل زمان خروجی پاس00خ نمی شود. زمان پاسخ :معیار دیگر ،زمان تحویل ی0ک درخواس0ت ت0ا دری0افت اولین پاس0خ اس00ت .این معی0ار ک0ه زمان پاسخ نام دارد ،مدت زمانی است که مدت زمانی اس00ت ک00ه ط00ول می کش00د پاس00خ داده ش00ود ،ن00ه مدت زمانی که طول می کشد تا آن پاسخ چاپ شود. 9 / 48 الگوریتم های زمانبندی زمانبندی ارائه خدمت به ترتیب ورود(:)FCFS در این الگ0وریتم ،فراین0دی ک0ه زودت0ر CPUرا درخواس0ت ک0رد ،زودت0ر آن0را در اختی0ار می گیرد .پیاده سازی سیاست FCFSبا یک صف FIFOانجام می شود .مجموعه فراین00دهای زیر را در نظر بگیرید: فرایند ‏P1 ‏P2 ‏P3 24زمان انفجار 3 3 اگر فرایندها به ترتیب p3,p2,p1بیایند و به ترتیب FCFSخدمات بگیرند،نمودار به صورت زیر است: ‏P1 ‏P2 ‏P3 30 27 24 0 زمان انتظار برای P1برابر صفر ،برای P2براب00ر 24و ب00رای P3براب00ر ب00ا 27اس00ت. بنابراین ،زمان انتظار میانگین برابر ( 17=3/)27+24+0است. ‏ میانگین زمان انتظار تحت سیاست FCFSکمینه نیست و ممکن است ب0ا تغی0یرات زی0ادی ک0ه الگوریتم زمانبندی FCFSانحصاری نیست. در انفجار CPUانجام می شود ،تغییر کند. همچنین در این الگوریتم بهره وری دستگاهها و CPUکاهش می یابد. 10 / 48 الگوریتم های زمانبندی زمانبندی بر حسب کوتاهترین کار (:)SJF این الگوریتم به هر فرایند ،طول انفجار CPUبعدی اش را می دهد .وقتی CPUمهیا باشد، به فرایندی نسبت داده می شود که انفجار CPUبعدی کوچکتری داشته باشد .اگر طول انفج00ار CPUبعدی دو فرایند یکسان باشد ،برای انتخاب یکی از آنها ،از زمانبندی FCFSاس00تفاده می شود .زمانبندی در این الگوریتم با بررسی طول انجار CPUبعدی فراین00د انج00ام می ش00ود (نه طول کلی آن) .به عنوان مثال فرایندهای زیر را در نظر بگیرید: ‏P4 3 ‏P1 P2 6 8 ‏P3 7 فرایند زمان انفجار با استفاده از زمانبندی ،SJFاین فرایندها بر اساس نمودار زیر زمانبندی می شوند: ‏P2 0 3 ‏P3 9 16 ‏P1 ‏P4 24 زمان انتظار برای فرایند P1برابر با ،3برای P2برابر با ،16برای P3برابر ب00ا 9و ب00رای P4براب00ر ب00ا 0 است .بنابراین میانگین زمان انتظار برابر با ( 7=4/)0+9+16+3است. 11از الگوی زمانبندی FCFSاستفاده می کردیم ،میانگین زمان انتظار برابر با 10.25می شد. /اگر 48 زمانبندی بر حسب کوتاهترین کار ()SJF (ادامه)... مشکل عمده الگوریتم SJFاین است که در طول درخواست بعدی CPUباید مشخص باش00د. برای زمانبند بلندمدت در یک سیستم دسته ای ،حد زمانی را که کاربر هنگام تحوی00ل ک00ار تع00یین کرده است به عنوان طول فرایند درنظر گرفته و سعی می شود که این حد زم00انی دقیق00ا ب00رآورد شود .زمانبندی SJFدر زمانبندی بلندمدت کاربرد زیادی دارد. الگوریتم SJFنمی تواند در سطح زمانبندی کوتاه مدت به کار گرفته شود .زیرا ط00ول انفج00ار بعدی را نمی دانیم ام00ا می ت00وانیم ان00دازه اش را پیش بی00نی ک0نیم .ب00ا تخمین این ان00دازه می ت00وانیم فرایندی را محاسبه کنیم که طول انفجار بعدی آن کوتاهتر است. انفجار محاسباتی بعدی ،به صورت میانگین نمایی طول های محاسبه شده انفجاره00ای محاس00باتی قبلی پیش بینی می شود .فرض کنید tnطول nامین انفجار محاسباتی و τn+1مقدار پیش بینی ش00ده برای انفجار محاسباتی بعدی باشد .آنگاه برای α ≤ 1 ≤ 0فرمول زیر را تعریف می کنیم: = α tn + (1 – α) τn τn+1 مقدار tnشامل جدیدترین اطالعات اس00ت ،ب00ه ط00وری ک00ه τnس00ابقه گذش00ته را ذخ00یره می کن00د و تخمین nام است .پارامتر αوزن نسبی سابقه فعلی و گذشته را در پیش بینی ما کنترل می کند. 12 / 48 پیش بینی طول انفجار محاسباتی بعدی شکل زیر یک میانگین نمایی را با = αنشان می دهد .مقدار τ0را می توان به صورت یک مقدار ثابت یا میانگین کل سیستم تعریف کرد. ‏τi ‏ti زمان 13 / 48 13 ... 12 ... 6 4 13 13 6 6 5 9 11 4 6 8 10 انفجار محاسباتی()ti پیش بینی ()τi زمانبندی بر حسب کوتاهترین کار ()SJF (ادامه)... الگوریتم SJFممکن است با قبضه کردن یا بدون قبضه کردن باشد. برای زمانبندی SJFبا قبضه کردن 4فرآیند زیر را درنظر بگیرید: زمان انفجار 8 4 9 5 فرآیند ‏P1 ‏P2 ‏P3 ‏P4 زمان رسیدن 0 1 2 3 با استفاده از زمانبندی SJFبا قبضه کردن ،این فرایندها بر اساس نمودار زیر زمانبندی می شوند: 26 ‏P3 17 ‏P1 10 ‏P4 ‏P2 5 میانگین زمان انتظار6.5=4/))3-5(+)2-17(+)1-1(+)1-10((: در زمانبندی SJFبدون قبضه کردن ،میانگین زمان انتظار برابر با 7.75میلی ثانیه خواهد بود. 14 / 48 ‏P1 1 0 زمانبندی اولویت الگوریتم SJFحالت خاصی از الگوریتم زمانبندی اولویت اس00ت .ب00ه ه00ر فراین00د ی00ک اول00ویت نسبت داده می شود و CPUبه فرایندی تخصیص می یابد ک00ه ب00االترین اول00ویت را دارا باش00د. فرایندهایی با اولویت یکسان ،به ترتیب FCFSزمانبندی می شوند. به عنوان مثال ،فرایندهای زی00ر را در نظ00ر بگیری00د ،ب00ه ط00وری ک00ه در زم00ان ص00فر ب00ه ت00رتیب P1,P2,…,P5رسیده اند: اولویت 3 1 4 5 2 فرایند ‏P1 ‏P2 ‏P3 ‏P4 ‏P5 زمان انفجار 10 1 2 1 5 با استفاده از زمانبندی اولویت ،این فرایندها بر اساس نمودار زیر زمانبندی می شوند: ‏P 19 4 ‏P3 18 ‏P1 16 میانگین زمان انتظار در این مثال 8.2 ،میلی ثانیه است. 15 / 48 ‏P5 6 ‏P2 1 0 زمانبندی اولویت (ادامه )... زمانبندی اولویت می تواند با قبضه کردن یا بدون قبضه کردن باشد. مسئله عمده در الگوریتم زمانبندی اول00ویت ،انس0داد نامح0دود ی0ا گرس0نگی(قحطی)اس00ت. الگوریتم زمانبندی اولویت می تواند منجر به این شود که فرایندهایی با اولویت پایین ،به مدت نامحدودی منتظر CPUباشند .در یک سیستم کامپیوتری با بار زیاد ،فرایندهایی با اولویت باال ،مانع از این می شوند که CPUب00ه فراین00دهایی ب00ا اول00ویت پ00ایین تعل00ق یابد ،که ممکن است فرایند با تاخیر بسیار زیادی انج00ام ش00ود و ی00ا اینک00ه سیس00تم از ک00ار بیافتد و تمام فرایندهای با اولویت پایین ،از بین بروند. راه حل مسئله انسداد نامحدود ب0ا اول0ویت پ0ایین ،کهنگی اس0ت .در این تکنی0ک ،اول0ویت فرایندی که به مدت زیادی در سیستم منتظر مانده است ،به تدریج افزایش می یابد. 16 / 48 زمانبندی نوبت گردشی ()RR الگوریتم نوبت گردشی ( )RRمخصوص سیستم های اش00تراک زم00انی ط00راحی ش00ده اس00ت .این الگوریتم شبیه FCFSاست ،ب00ا این تف00اوت ک00ه در ح00رکت بین فراین00دها ،از زمانبن00دی قبض00ه کردن استفاده می شود .یک واحد زمانی کوچک ،به نام کوانتوم زمانی ی00ا بره00ه زم00انی تعری00ف می شود .صف آمادگی به صورت یک صف چرخشی در نظر گرفته می شود .زمانبن00د CPU در طول صف آمادگی حرکت می کند و CPUرا حداکثر به مدت یک کوانتوم زم00انی ب00ه ه00ر فرایند تخصیص می دهد. میانگین زمان انتظار در الگوریتم ،RRاغلب زیاد است .فرایندهای زیر را درنظر بگیری00د ک00ه در زمان 0می رسند: ‏P3 ‏P2 ‏P1 فرایند 3 3 24 زمان انفجار با استفاده از زمانبندی ،RRاین فرایندها بر اساس نمودار زیر زمانبندی می شوند: ‏P1 26 30 ‏P1 ‏P1 22 17 /میانگین زمان انتظار در این مثال=5.66 ، 48 ‏P1 18 ‏P1 14 میلی ثانیه است. ‏P3 10 ‏P2 ‏P1 7 4 0 زمانبندی نوبت گردشی ()RR (ادامه )... در الگوریتم زمانبندی نوبت چرخشی CPU ،به هیچ فراین00دی در ی00ک س00طر ،بیش از یک کوانت00وم زم00انی تخص00یص نمی یاب00د .اگ00ر انفج00ار محاس00باتی فراین00دی بیش از ی00ک کوانتوم زمانی شود ،آن فرایند قبضه می شود و در انتهای صف آمادگی قرار می گیرد. الگوریتم صف ،RRبا قبضه کردن همراه است. ک00ارایی الگ00وریتم RRب00ه ان00دازه کوانت00وم زم00انی بس00تگی دارد .از ی00ک ط00رف ،اگ00ر کوانتوم زمانی بسیار بزرگ باشد (نامحدود) ،سیاست RRشبیه FCFSخواهد بود. اگر کوانتوم زمانی خیلی کوچک باشد اینطور وانمود می شود که هر nفرایند ،پردازنده مخصوص به خ00ودش را دارد ک00ه س00رعت هرک00دام ب00ه ان00دازه س00رعت پردازن00ده واقعی است. 18 / 48 کوانتوم زمانی کوچک منجر به تعویض بستر می شود. در نرم افزار باید اثر تعویض بستر را در کارایی زمانبندی RRدرنظر بگیریم .فرض می کنیم فقط یک فرایند با 10واحد زمانی داریم .اگر کوانتوم زمانی برابر با 12واحد زمانی باشد ،فرایند در کمتر از یک کوانتوم زمانی خاتمه می یابد و س0رباری ن0دارد .اگ0ر کوانت0وم زم0انی براب0ر ب0ا 6واح0د زم0انی باش0د ،این فرایند به دو کوانتوم زمانی نیاز دارد و منجر به تعویض بستر می شود .اگر کوانت00وم زم00انی براب0ر ب00ا ی0ک واحد زمانی باشد ،نیاز به 9تعویض بستر است و بدین ترتیب اجرای فرایند کند می شود .بن00ابراین ،ب00رای مقابله با تعویض بستر ،عالقه مند هستیم که کوانتوم زمانی بزرگ باشد. تعویض بستر زمان فرایند =10 کوانتوم زمانی 12 0 6 1 0 10 10 119 / 48 0 6 9 1 2 3 4 5 6 7 8 9 10 تغییر زمان برگشت بر اساس کوانتوم زمانی 6 ‏P1 3 ‏P2 1 ‏P3 7 ‏P4 میانگین زمان برگشت 20 / 48 زمان فرایند کوانتوم زمانی تغییر زمان برگشت بر اساس کوانتوم زمانی (توضیح شکل) زمان برگشت نیز به اندازه کوانتوم بستگی دارد .همانطور که از شکل پیداست ،میانگین زمان برگشت مجموعه ای از فرایندها ،با افزایش ان00دازه کوانت00وم زم00انی ،الزام00ا بهب00ود نمی یابد.ب00ه ط00ور کلی ،می00انگین زم00ان برگش00ت در ص00ورتی بهب00ود می یاب00د ک00ه اغلب فراین00دها انفج00ار محاس00باتی بع00دی خودش00ان را فق00ط در ی00ک کوانت00وم زم00انی ب00ه اتم00ام برسانند. با درنظر گرفتن زمان تع00ویض بس00تر ،هرچ00ه کوانت00وم زم00انی کوچک00تر باش0د ،می0انگین زمان برگشت افزایش می یابد ،زی00را نی00از ب00ه تع00ویض بس00تر بیش00تری اس00ت .از ط00رف دیگر اگر کوانتوم زمانی بس00یار ب00زرگ باش00د ،زمانبن00دی RRب00ه FCFSتب00دیل می شود. 21 / 48 زمانبندی صف چندسطحی دسته دیگری از الگوریتم های زمانبندی برای وض00عیت ه00ایی ایج00اد ش00دند ک00ه در آنه00ا، فرایندها می توانند به دو گروه تقسیم شوند. الگوریتم زمانبندی صف چندسطحی ،صف آمادگی را به چند بخش مجزا تقسیم می کند. هر فرایند بر اساس خواصی که دارد در صفی قرار می گیرد .این صفات عبارتند از: اندازه حافظه ،اولویت فرایند ،یا نوع فرایند .هر صف الگوریتم زمانبندی خاص خ00ودش را دارد .عالوه بر این ،بین صف ها نیز باید زمانبندی وجود داشته باش00د ک00ه ب00ر اس00اس زمانبندی همراه با قبضه کردن و با اولویت ثابت ،پیاده سازی می شود. امکان دیگر ،استفاده از برهه زمانی در بین صف ها است .ه00ر ص00ف بخش00ی از زم00ان صف را به خود اختصاص می دهد و بین فرایندهای مختلف آن صف زمانبندی می کند. 22 / 48 زمانبندی صف چندسطحی باالترین اولویت فرایندهای سیستم فرایندهای محاوره ای فرایندهای ویرایشی محاوره ای فرایندهای دسته ای فرایندهای دانشجو پایین ترین اولویت در این شکل هر صف نسبت به صف های با اولویت پایین تر ،اولویت مطلقی دارد. 23 / 48 زمانبندی صف بازخوردی چندسطحی معموال در الگ00وریتم زمانبن00دی ص00ف چندس00طحی ،فراین00دها هنگ00ام ورود ب00ه سیس00تم در صفی قرار می گیرند ،به طوری که از صفی به ص00ف دیگ00ر نمی رون00د .ام00ا زمانبن00دی صف بازخوردی چندسطحی به فرایندها اجازه می دهد از ص00فی ب00ه ص00ف دیگ00ر منتق00ل شوند. فلسفه این کار این است که ویژگی های انفجارهای محاسباتی فرایندها با یکدیگر متفاوت است .اگر فرایندی به مدت زیادی CPUرا در اختیار گیرد ،به صفی با اولویت پ00ایین تر منتقل می گردد .بدین ترتیب ،فرایندهای مقید به I/Oو محاوره ای ،در ص00ف ه00ایی با اولویت باال قرار می گیرند. به طور مشابه ،فرایندی که به مدت زیادی در صفی با اولویت پایین تر منتظر می ماند، ممکن اس00ت ب00ه ص00فی ب00ا اول00ویت ب00االتر منتق00ل ش00ود .در این ش00کل کهنگی ،از مش00کل گرسنگی جلوگیری می شود. 24 / 48 صف های بازخورد چندسطحی کوانتوم زمانی = 8 کوانتوم زمانی = 16 ‏FCFS 25 / 48 زمانبندی صف بازخوردی چندسطحی (ادامه )... به طور کلی ،زمانبند صف بازخورد چندسطحی ،توسط پارامترهای زیر تعریف می شوند: تعداد صف ها. الگوریتم زمانبندی برای هر صف. روشی که تعیین می کند چه هنگامی یک فرایند با صفی با اولویت بیشتر منتقل شود. روشی که تعیین می کند چه هنگامی یک فرایند با صفی با اولویت کمتر منتقل شود. روشی که تعیین می کند فرایندی که نیاز به خدمات دارد ،به چه صفی وارد شود. 26 /این الگوریتم می تواند طوری پیکربندی شود که با سیستمی که درحال طراحی 48است سازگاری داشته باشد. زمانبندی چندپردازنده ای اگر چندین CPUدر سیستم وجود داشته باشند ،مسئله زمانبندی پیچیده تر می شود. در سیستم های چندپردازنده ای سیستم های همگن (کارایی پردازنده در آن یکسان است) را درنظر می گیریم .هر پردازنده آماده می تواند هر فراین00د موج00ود در ص00ف را اج00را کند .فرض می کنیم دستیابی به حافظه به طور یکنواخت ص00ورت می گ00یرد .در سیس00تم های همگن که پردازنده های آنها متفاوتند فقط برنامه ه00ایی ک00ه ب00رای پردازن00ده کامپای00ل شده اند بر روی آنها قابل اجرا می باشند. در پردازنده های همگن (کارایی پردازنده آنها یکسان است) ن0یز مح0دودیت ه0ایی ب0رای زمانبندی وجود دارد .در یک دستگاه I/Oکه به یک گذرگاه اختصاصی یک پردازن00ده وصل شده است فرایندهایی می خواهند از این دستگاه استفاده کنند زمانبندی شوند ت00ا ب00ر روی آن پردازنده اجرا شوند در غیراینصورت ق00ادر ب00ه اس00تفاده از آن دس00تگاه نخواهن00د بود. 27 / 48 زمانبندی چندپردازنده ای (ادامه )... اگر چند پردازنده همگن در سیستم موجود باشند ،مسئله اشتراک بار پیش خواهد آمد .می توان برای هر پردازنده یک صف جداگانه درنظر گرفت. در این الگو ،می توان از دو روش زمانبندی استفاده کرد .در روش اول ،هر پردازنده خودش را زمانبندی می کند .برای این منظور ،هر پردازنده صف آمادگی مشترک را بررسی می کند و فرایندی را برای اجرا انتخاب می کند. در روش دوم ،یک پردازنده می تواند پردازنده دیگر را زمانبندی کند و بدین ترتیب یک ساختار رئیس/مرئوس به وجود می آید. 28 / 48 زمانبندی بی درنگ محاسبات بی درنگ بر دو نوع اند .سیستم های بی درنگ سخت الزم است ی00ک وظیف00ه حیاتی ،در زمان معینی به اتمام برس00د .معم00وال فراین00د هم00راه ب00ا م00دت زم00ان موردنی00از برای کامل شدن آن یا اج00رای ،I/Oب00ه پردازن00ده تحوی00ل داده می ش00ود .زمانبن00د ممکن است فرایند را بپذیرد و تضمین کند که آن فرایند به موقع به اتمام برسد ،ی00ا در ص00ورت غیرممکن بودن اجرای آن ،از پذیرفتنش خودداری کند .این عمل رزرو کردن منب00ع ن00ام دارد. محاسبات بی درن00گ ن00رم مح00دودیت کم00تری دارد .این محاس00بات مس00تلزم این اس00ت ک00ه فرایندهای حیاتی اولویت بیشتری داشته باشد .پیاده سازی عملیات بی درنگ نرم مستلزم طراحی دقیق زمانبند و جنبه های دیگری از سیستم عام00ل اس00ت ک00ه ب00ه زمانبن00د مرتب00ط هستند .اوال سیس0تم بایدزمانبن0دی اول0ویت داش0ته باش0د و فراین0دهای بی درن0گ ب0االترین اولویت را دارا باشند .ثانیا تاخیر توزیع باید کوچک باشد. 29 / 48 زمانبندی بی درنگ (ادامه )... به راح00تی می ت00وان مطمئن ش00د ک00ه وی00ژگی اول در سیس00تم برق00رار اس00ت ولی حص00ول اطمینان از ویژگی دوم کمی پیچیده است زیرا اغلب سیستم های عامل مجبور می ش00وند که قبل از تعویض بستر منتظر بمانند تا یک فراخوان سیس00تم کام00ل ش00ود ی00ا عم00ل I/O مسدود گردد .تاخیر توزیع در این سیستم ها می تواند طوالنی باشد. برای اینکه تاخیر توزیع اندک باشد ،فراخوان سیستم باید قاب00ل قبض00ه ش00دن باش00د .ب00رای رسیدن به این هدف می توان به روش های گوناگونی عمل کرد .یک روش این است که در فراخوان های سیس00تم ط00والنی ،از نق00اط قبض00ه ش00دن اس00تفاده گ00ردد ک00ه در این نق00اط کنترل می شود که آیا الزم است فرایندی با اولویت باال اجرا شود یا خیر .راه حل دیگ00ر این است که کل هسته قابل قبضه شدن باشد. اگر فرایندی با اولویت باال نیاز به خواندن و تغییر ساختمان داده ای از هسته داشته باشد که در حال حاضر در اختیار فرایندی با اولویت کمتر است ،چه اتفاقی می افتد؟ فرایندی با اولویت باالتر منتظر می ماند تا فرایندی با اولویت باالتر به اتمام برسد .این وض00عیت را اولویت معکوس می نامند. 30 / 48 زمانبندی بی درنگ (ادامه )... این مس00ئله را می ت00وان از طری00ق پروتک00ل وراثت اول00ویت ح00ل ک00رد ک00ه در آن تم00ام فرایندهایی که منابعی را دراختیار دارند که مورد نیاز فرایندی با اول00ویت ب00االتر اس00ت، اولویت باال را به ارث ببرند تا منابع موردنظر را دراختیار گیرند .وقتی کارش00ان انج00ام شد ،اولویت اولیه خود را دارا خواهند شد. مرحله برخورد تاخیر توزیع دارای دو مولفه است: قبضه کردن هر فرایندی که در هسته درحال اجراست. فرایندهایی با اولویت پایین تر ،منابع موردنیاز فرایندهای ب00ا اول00ویت ب00االتر را ره00ا می کنند. 31 / 48 تاخیر توزیع پاسخ به رویداد رویداد فاصله زمانی پاسخ مهیا شدن فرایند پردازش وقفه تاخیر توزیع اجرای فرایند بی درنگ توزیع 32 / 48 برخوردها زمان ارزیابی الگوریتم های زمانبندی اولین مسئله ،تعیین معیارهای انتخاب الگوریتم اس00ت .معیاره00ای م00ا ممکن اس00ت ش00امل مقیاس های گوناگونی باشد: بیشترین بهره وری CPUدر حالتی که حداکثر زمان پاسخ برابر با 1ثانیه است. بیشترین توان عملیاتی ،به طوری که میانگین زمان برگشت ،ب00ه ط00ور خطی مناس00ب ب00ا کل زمان اجراست. پس از تعریف معیارهای انتخاب ،آنها را با مالحظات خاصی بررسی می کنیم. 33 / 48 مدلسازی قطعی یکی از مهمترین روش های ارزیابی الگ00وریتم ه00ا ،ارزی00ابی تحلیلی ن00ام دارد .ارزی00ابی تحلیلی ،با استفاده ار الگوریتم و بارکاری سیستم ،فرمول یا عددی را تولی00د می کن00د ک00ه کارایی الگوریتم را برای آن بار سیستم ارزیابی می کن00د .ی00ک ن00وع ارزی00ابی تحلیلی ب00ه نام مدلسازی قطعی است .این روش ،یک بار ک00اری از قب00ل تع00یین ش00ده ای می گ00یرد و کارایی هر الگوریتم را برای آن بار کاری تعریف می کند. به عنوان مثال 5فراین00د زی00ر را در نظ00ر بگیری00د ک00ه همگی در زم00ان ص00فر وارد می شوند: ‏P5 12 34 / 48 ‏P4 7 ‏P3 3 ‏P2 29 ‏P1 10 فرایند انفجار محاسباتی مدلسازی قطعی (ادامه )... الگوریتم :FCFS ‏P5 10 ‏P4 39 ‏P3 42 ‏P2 49 ‏P1 61 0 میانگین زمان انتظار: )0+10+39+42+49(/5=28 الگوریتم :SJF ‏P2 3 ‏P5 10 میانگین زمان انتظار: 20 ‏P1 ‏P ‏P4 613 0 32 (13=5/)20+3+0+32+10 الگوریتم ( RRبا کوانتوم زمانی 10میلی ثانیه): ‏P1 0 10 ‏P2 ‏P 23 20 3 ‏P4 30 ‏P2 ‏P5 40 ‏P 550 ‏P2 52 (23=5/)40+23+20+32+0 میانگین زمان انتظار: با این ارزیابی ها مشاهده می کنیم که در این حالت ،میانگین زمان انتظار نصف زمانبندی FCFS35 /است و مقدار آن در الگوریتم RRمتوسط است. 48 61 مدلسازی قطعی (ادامه )... مدلسازی قطعی ،س00ریع و س00اده اس00ت .اع00داد دقیقی را ارائ00ه می کن00د ک00ه ب00رای مقایس00ه الگوریتمها به کار می روند .ولی به تعداد دقیقی از ورودی ها نیاز دارد و پاسخ آن ن00یز برای همان ورودی ها صادق است. کاربردهای مدلسازی قطعی ،توصیف الگوریتم های زمانبندی و ارائ0ه مث0ال هاس0ت .در مواردی که یک برنامه باید بارها و بارها اجرا شود و نیازمندی های پ00ردازش آن دقیق00ا قابل سنجش باشد ،استفاده از مدلسازی قطعی برای انتخاب الگ00وریتم زمانبن00دی ،مناس00ب است .با اجرای مدلسازی قطعی بر روی مثال های متفاوت رفتارهایی مشاهده می ش00ود که به طور جداگانه قابل تحلیل و اثبات خواهند بود. 36 / 48 مدل های صف بندی سیستم کامپیوتری به صورت شبکه ای از کارگزاران توصیف می گ0ردد .ه0ر ک0ارگزار ص00فی از فراین00دهای درح00ال انتظ00اردارد CPU .ک00ارگزاری اس00ت ک00ه دارای ص00ف آمادگی است و سیستم I/Oنیز دارای صف های دستگاه اس00ت .ب00ا داش00تن ن00رخ رس00یدن فرایندها و نرخ های خدمات ،می توان بهره وری ،میانگین طول ص00ف ،می00انگین زم00ان انتظار و غیره را تعیین کرد .این روش را تحلیل شبکه صف بندی می نامند. تحلیل صف در مقایسه الگوریتم های زمانبندی مفید واقع می شوف اما مح00دودیت ه00ایی دارد .فعال الگوریتم ها و توزیع هایی که می توانند پردازش شوند ،بسیار مح00دود اس00ت. کار کردن با ریاضیات الگوریتم ها ی0ا توزی0ع ه0ای پیچی0ده ،دش0وار اس0ت .تحلی0ل ص0ف بندی نیتزمند ساخت فرضیه های مس00تقلی اس00ت ک00ه ممکن اس00ت دقی00ق نباش00ند .ب00ه ط00ور کلی ،م00دل ه00ای ص00ف ،تقری00بی از سیس00تم واقعی را نش00ان می ده00د .در نتیج00ه ،دقت محاسبات آن زیر سوال است. 37 / 48 شبیه سازی ها برای ارزیابی دقیق تر الگوریتم ه0ای زمانبن0دی ،می ت0وانیم از ش0بیه س0ازی اس0تفاده ک0نیم .ش0بیه سازی مستلزم برنامه نویسی یک مدل سیستم کامپیوتری است .ساختمان داده ه00ای ن00رم اف00زاری، اجزای اصلی یک سیستم را می سازند .داده های شبیه سازی به روش های گون00اگونی تولی00د می شوند .متداولترین روش ،استفاده از مولد اعداد تصادفی است که برای تولید فرایندها ،زمان های انفجار ،CPUزمان های رسیدن فراین00دها ،زم00ان ه00ای خ00روج و غ00یره برحس00ب توزی00ع ه00ای احتمالی به کار می رود. شبیه سازی برحسب توزیع ،مکن است به دلیل روابط بین رویدادهای مت00والی در سیس00تم واقعی، دقیق نباشد .توزیع فراوانی فقط نشان می دهد که ه00ر روی00داد چق00در اتف00اق می افت00د و چ00یزی در مورد ترتیب وقوع آنها ارائه نمی کند .برای حل این مسئله از نوارهای ردیابی استفاده می ش00ود. نوار ردیابی با نظارت بر سیس00تم واقعی و ثبت دنبال00ه ای از روی00دادهای واقعی ایج00اد می ش00ود. این روش می تواند نتایج دقیقی را بری وردی هایش ایجاد کند .شبیه سازی می تواند گ00ران تم00ام شود .زیرا گاهی ساعت ها وقت کامپیوتر را به خود اختصاص می دهد. 38 / 48 ارزیابی زمانبندی های CPUبا شبیه سازی آمارهای کارایی برای ‏FCFS شبیه سازی ‏FCFS ... آمارهای کارایی برای ‏SJF آمارهای کارایی برای )RR(q=14 شبیه سازی ‏SJF شبیه سازی )RR(q=14 39 / 48 ‏CPU 10 ‏I/O 213 ‏CPU 12 ‏I/O112 ‏CPU 2 ‏I/O 147 ‏CPU 173 … نوار ردیابی اجرای فرایند واقعی پیاده سازی ارزیابی الگوریتم شبیه سازی نیز دقت محدودی دارد .دقیقترین روش ارزیابی الگوریتم ه00ای زمانبن00دی ،نوش00تن و به کارگیری آن در سیستم و مشاهده عملکرد آن اس00ت .دراین روش ،الگ00وریتم واقعی در سیس00تم واقعی اجرا و ارزیابی می شود. مشکل این روش ،هزینه آن است .هزینه این روش ،نه تنها به نوشتن الگوریتم و اص00الح سیس00تم عامل برای پش00تیبانی از آن و س00اختمان داده ه00ای مرب00وط ب00ه آن مرب00وط می ش00ود ،بلک00ه تعام00ل کاربران با سیستم عاملی که همیشه در حال تغییر است ،مربوط می شود .سیستم عاملی که دائم00ا تغییر می کند ،نمی تواند برای اجرای کار کاربران به آنها کمک کند. مشکل دیگر ارزیابی الگوریتم این است که محیطی که الگوریتم در ان به ک00ار گرفت00ه می ش00ود، تغییر می کند .تغییر محیط فقط ناشی از نوشتن برنامه های جدید و تغییر انواع مسئله ها نیس00ت، بلکه به کارایی زمانبند نیز مربوط می شود. اگر قابلیت انعطاف الگوریتم های زمانبندی زیاد باشد ،مدیران سیستم یا کاربران می توانن00د آنه00ا را تغییر دهند .متاسفانه ،سیستم های عامل اندکی از این نوع زمانبن00دی قاب00ل تنظیم را مج00از می دانند. 40 / 48 مدل های زمانبندی فرایند در این بخش ،زمانبندی فرایند را در سیستم های سوالریس ،2ویندوز 2000و لینوکس بررسی خواهیم کرد .قبل از پرداختن به این مدل ها بندها را با زمانبندی فرایند ارتباط می دهیم. در فصل 5بندها را در مدل فرایند معرفی کردیم و در نتیجه هر فرایند می تواند چندین بند از کنترل را در اختیار داشته باشد. بندهای سطح کاربر توسط کتابخانه بندها مدیریت می شود و هسته از آنها خبر ندارد .برای اجرا شدن بر روی ، CPUبندهای سطح کاربر به بند هسته مربوطه نگاشت می شود ،ممکن است این نگاشت به طور غیرمستقیم و از طریق فرایند سبک ( )LWPباشد. کتابخانه بند ،بندهای سطح کاربر را طوری زمانبندی می کند که بر روی LWPآماده اجرا شوند .این طرح زمانبندی محلی فرایند نام دارد که در آن زمانبندی بند در یک برنامه کاربردی به طور محلی صورت می گیرد .هسته با استفاده از زمانبندی سراسری سیستم تصمیم می گیرد که کدام بند هسته باید زمانبندی شود. 41 / 48 سوالریس 2 سوالریس 2از زمانبندی مبتنی بر اولویت فرایندها استفاده می کند .چه00ار رده از زمانبن00دی را در اختیار دارد که به ترتیب اولویت عبارتند از :بی درنگ ،سیستم ،اش00تراک زم00انی و مح00اوره ای .هر رده شامل اولویت ها و الگ00وریتم ه00ای زمانبن00دی مختلفی اس00ت ،ولی اش00تراک زم00انی و محاوره ای از یک سیاست زمانبندی استفاده می کنند. فرایند با یک LWPشروع می شود و قادر است در صورت نیاز LWPهای جدیدی ایجاد کن00د. هر ،LWPرده زمانبندی و اولویت فرایند پدر را به ارث می ب00رد.رده زمانبن00دی فرض00ی ب00رای فرایند ،اشتراک زمانی است .به طور پیش فرض رابطه معکوسی بین اول00ویت ه00ا و ب00رش ه00ای زمانی وجود دارد. سوالریس 2برای اجرای فراین00دهای هس00ته از رده سیس00تم اس00تفاده می کن00د .سیاس00ت زمانبن00دی برای رده سیستم ،برش زمانی نیست .بند متعلق به رده سیستم آنقدر اجرا می شود تا متوقف شود یا توسط بندی با اولویت بیشتر قبضه گردد. 42 / 48 سوالریس 2 (ادامه )... در رده بی درنگ ،بندها باالترین اولویت را دارند .فرایندهای این رده قبل از فرایندهای موج00ود در رده های دیگر اجرا می شوند .به طور کلی ،تعداد اندکی از فرایندها به رده بی درنگ تعل00ق دارند. هر رده زمانبندی شامل مجموعه ای از اولیتها است .اما ،زمانبند اول00ویت ه00ای وی00ژه رده را ب00ه اولویت های سراسری تبدیل می کند و بندی را برای انتخاب اجرا می کند که اول00ویت سراس00ری آن باالترین است .بند انتخاب شده در CPUاجرا می شود تا یکی از موارد رخ دهد: مسدود شود. از برش زمانی خود استفاده کند (اگر بند ،سیستم نیست). توسط بندی با اولویت باالتر قبضه شود. اگر اولویت چندین بند یکسان باشد ،زمانبند از صف نوبت چرخشی استفاده می کند. 43 / 48 زمانبندی در سوالریس 2 صف اجرا بندهای سطح هسته مربوط به LWPهای بی درنگ رده های زمانبند اولویت ویژه رده ترتیب زمانبندی اولویت سراسری اولی باالترین بی درنگ سیستم بندهای خدمات هسته بندهای سطح هسته محاوره ای و LWPهای اشتراک زمانی 44 / 48 محاوره ای و اشتراک زمانی آخری پایین ترین ویندوز 2000 ویندوز 2000بندها را ب00ا اس00تفاده از الگ00وریتم زمانبن00دی قبض00ه ک00ردن مبت00نی ب00ر اول00ویت، زمانبندی می کند .زمانبند ویندوز 2000تضمین می کند که بندی با باالترین اولویت همیش00ه اجرا می شود .بخشی از هسته ویندوز 2000که زمانبن00دی را انج00ام می ده00د ،توزی00ع کنن00ده نام دارد .بندی که توسط توزیع کننده برای اجرا انتخاب شد ،آنقدر اجرا می شود ت00ا توس00ط بن00دی با اولویت باالتر قبضه شود ،خاتمه یابد ،کوانتوم زمانی ان ب00ه پای00ان برس00د ،ی00ا فراخ00وان سیس00تم مسدود کردن را اجرا نماید .ویندوز 2000تضمین نمی کند که یک بن00د بی درن00گ دراثن00ای محدوده زمانی خاصی اجرا شود. توزیع کننده از طرح اولویت 32س00طحی ب00رای تع00یین ت00رتیب اج00رای بن00دها اس00تفاده می کن00د. اولویت ها به دو رده تقسیم می شوند :رده متغیر و رده بی درنگ .توزی00ع کنن00ده مجموع00ه ای از صف ها را از باالترین به پایین ترین اولویت پیم00ایش می کن00د ت00ا بن00دی را بیاب00د ک00ه آم00اده اج00را است .اگر هیچ بندی آماده ای پیدا نشود ،توزیع کنندهف بند ویژه ای را با نام بند بیک00ار را اج00را می نماید .اولویت هر بند به رده اولویتی که به آن تعل00ق دارد ،و ب00ه اول00ویت نس00بی در داخ00ل آن رده بستگی دارد .هر بند دارای یک اولویت پایه است. 45 / 48 ویندوز 2000 (ادامه )... وقتی کوانتوم زمانی بندی به اتمام برسد ،آن بند دچار وقفه می شود .اگر آن بن00د در رده اول00ویت متغیر باشد ،اولویت ان کاهش می یابد .اولویت هیچگ00اه از اول00ویت پای00ه کم00تر نمی ش00ود .وق00تی بندی با اولویت متغیر از یک عملیات انتظار آزاد می شود ،توزی00ع کنن00ده ،اول00ویت ان00را اف00زایش می دهد. ویندوز 2000بین فرایند پیش زمین00ه و پس زمین00ه تم00ایز قائ00ل می ش00ود .فراین00د پیش زمین00ه اجازه دارد قبل از وقوع قبضه کردن اشتراک زمانی ،سه برابر بیشتر اجزا شود. بی درنگ باال باالی نرمال نرمال زیرنرمال اولویت بیکار 31 15 15 15 15 15 بحران زمانی 26 15 12 10 8 6 باالترین 25 14 11 9 7 5 باالتر از نرمال 24 13 10 8 6 4 نرمال 23 12 9 7 5 3 زیر نرمال 22 11 8 6 4 2 پایین ترین 16 1 1 1 1 1 بیکار 46 / 48 لینوکس لینوکس دو الگوریتم زمانبندی را برای فرایندها ارائ00ه می ده00د .یکی از آنه00ا الگ00وریتم اش00تراک زمانی منصف برای زمانبندی قبضه کردن بین چندین فرایند است .دیگری مربوط به وظایف بی درنگ است که در ان اولویت های مطلق مهمتر از منصفانه اس00ت .لین00وکس اج00ازه می ده00د ک00ه فقط فرایندهایی که در حالت کاربر اجرا می شوند ،قبضه گردن00د .اگ00ر فراین00دی در ح00الت هس00ته درحال اجرا باشد ،حتی اگر فرایند بی درنگی با اولویت بتالتر آماده شود ،نمی تواند آن00را قبض00ه کند. اولین رده زمانبندی مربوط به فرایندهای اش00تراک زم00انی اس00ت .از نظ00ر س00نتی ،لین00وکس ب00رای فرایندهای اشتراک زمانی از الگوریتم مبتنی بر اعتبار اس00تفاده می کن00د .این الگ00وریتم دو عام00ل را ترکیب می کند :سابقه و اولویت فرایند. سیستم اعتباردهی ،به طور خودکار ،اولویت ه00ای ب00اال را ب00ه فراین00دهای مح00اوره ای و مقی00د ب00ه I/Oمی دهد .علتش این است که زمان پاسخ این فرایندها مهم اس00ت .اس00تفاده از اول00ویت فراین00د در محاسبه اعتبارات جدید ،موجب می شود تا اولویت یک فرایند ،قابل تنظیم باشد. 47 / 48 لینوکس (ادامه )... لین000وکس دو رده از زمانبن000دی بی درن000گ را پی000اده س000ازی می کن000د ک000ه موردنی000از POSIX.1bاست :خ00دمات ب00ه ت00رتیب ورود ( )FCFSو ن00وبت گردش00ی (.)RR زمانبندی بی درنگ لینوکس ،زمانبندی نرم است. کد هسته لینوکس ،نمی تواند توسط کد حالت کاربر قبضه شود .اگ00ر وق00تی ک00ه هس00ته در حال اجرای فراخوان سیستم در فرایند دیگری باشد ،وقفه ای ب00ه ی00ک فراین00د بی درن00گ وارد ش00ود ،این فراین00د بی درن00گ بای00د منتظ00ر بمان00د ت00ا فراخ00وان سیس00تمی ک00ه در ح00ال اجراست کامل یا مسدود شود. 48 / 48 اعضای گروه: مهسا فرجو سهیال ابراهیمی صبا مهشید ابراهیم نژاد 49 تنظیمات سهیال ابراهیمی صبا صفحات 1تا 16 مهسا فرجو مهشید ابراهیم نژاد 48 50 صفحات 17تا 32 صفحات 33تا