اصول و مفاهیم طراحی سیستم های عامل 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