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

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

اسلاید 1: به نام خدا اصول و مفاهیم طراحی سیستم های عاملخلاصه فصل ششم1 / 48

اسلاید 2: زمانبندی CPUزمانبندی CPU، اساس سیستم های عامل چندبرنامه ای است. با حرکت CPU بین فرایندها، سیستم عامل می تواند بهره وری کامپیوتر را افزایش دهد.مفاهیم اساسی زمانبندی :هدف چندبرنامه ای این است که همیشه چندین فرایند در حال اجرا باشند تا بهره وری CPUبیشینه شود. اگر فرایندهای بیشتری وجود داشتند، بقیه منتظر می مانند تا CPU آزاد شود و بتواند دوباره زمانبندی شود.ایده چندبرنامه ای ساده است. هر فرایند به اجرایش ادامه می دهد تا برای یک عمل I/O در انتظار بماند.در یک سیستم کامپیوتری ساده، در این مدت CPU باید بیکار بماند. بنابراین، تمام این زمان های انتظار هدر می روند، یعنی کار مفیدی انجام نمی شوند. در چندبرنامه ای، سعی می شود که از این زمان ها به نحو احسن استفاده شود.2 / 48

اسلاید 3: چرخه انفجار CPU-I/Oموفقیت زمانبندی CPU به این خاصیت فرایندها بستگی دارد که اجرای فرایند شامل چرخه ای از اجرای CPU و انتظار I/O است.اجرای فرایند با انفجار CPU شروع می شود. به دنبال آن یک انفجار I/O قرار دارد و به همین ترتیب ادامه می یابد. سرانجام، آخرین انفجار CPU با درخواست سیستم برای خاتمه اجرا، پایان می پذیرد. مدت این انفجارهای CPU اندازه گیری شده اند و این مدت ها از فرایندی به فرایند دیگر و از کامپیوتری به کامپیوتر دیگر فرق می کند.3 / 48

اسلاید 4: ...Load storeAdd storeRead from fileانفجار CPUانتظار برای I/Oانفجار I/OStore incrementIndexWrite to fileانفجار CPUانتظار برای I/Oانفجار I/OLoad storeAdd storeRead from fileانفجار CPUانفجار I/Oانتظار برای I/O...دنباله ای از انفجارهای CPU و I/O4 / 48

اسلاید 5: زمان های انفجار CPUمدت انفجار (میلی ثانیه)فرکانسچرخه انفجار CPU-I/O برنامه مقید به I/O معمولا دارای چند انفجار کوچک CPU است. برنامه مقید به CPU معمولا چند انفجار بلند CPU دارد. این توزیع می تواند در انتخاب الگوریتم زمانبندی CPU مهم باشد.5 / 48

اسلاید 6: زمانبندی CPUهروقت CPU بیکار می شود، سیستم عامل باید یکی از فرایندهای موجود در صف آمادگی را برای اجرا انتخاب کند. این انتخاب توسط زمانبند کوتاه مدت (یا زمانبند CPU) انجام می گیرد. زمانبند، فرایندی را از بین فرایندهای موجود در حافظه که آمادگی اجرا دارند انتخاب می کند و CPU را به ان تخصیص می دهد. از نظر مفهومی، تمام فرایندهای موجود در صف آمادگی، منتظر به دست آوردن CPU هستند تا اجرا شوند.6 / 48

اسلاید 7: زمانبندی با قبضه کردنتصمیمات زمانبندی CPU ممکن است تحت چهار شرط زیر اتخاذ شوند:وقتی که فرایندی از حالت اجرا به حالت انتظار می رود (مثل در خواست I/O، یا فراخوانی انتظار برای خاتمه یکی از فرایندهای فرزند).وقتی فرایندی از حالت اجرا به حالت آمادگی می رود (مثل وقتی که رویدادی رخ می دهد).وقتی که فرایندی از حالت انتظار به حالت آمادگی می رود (مثل تکمیل I/O).وقتی که فرایندی خاتمه می یابد.برای شرایط 1و 4، انتخابی بر حسب زمانبندی وجود ندارد اما برای شرایط 2و 3 امکان انتخاب وجود دارد. وقتی زمانبندی تحت شرایط 1و 4 انجام می گیرد، الگوی زمانبندی را بدون قبضه کردن می نامیم. و در غیر اینصورت، آنرا قبضه کردن می نامیم. در زمانبندی بدون قبضه کردن وقتی CPU به فرایندی تخصیص یافت، آنقدر آنرا نگه می دارد تا اینکه خاتمه یابد یا به حالت انتظار برود. متاسفانه زمانبندی با قبضه کردن هزینه دارد. زمانبندی با قبضه کردن در طراحی هسته سیستم عامل موثر است.7 / 48

اسلاید 8: توزیع کنندهتوزیع کننده در زمانبندی CPU دخالت دارد. توزیع کننده پیمانه ای است که کنترل را به پردازنده ای می دهد که توسط زمانبند کوتاه مدت انتخاب شده است. این عمل شامل موارد زیر است:تعویض بسترتغییر به حالت کاربرپرش به محل مناسبی در برنامه کاربر و آغاز مجدد آن برنامهتوزیع کننده باید سرعت بالایی داشته باشد.8 / 48

اسلاید 9: معیارهای زمانبندیمعیارهای متعددی برای مقایسه الگوریتم های زمانبندی پیشنهاد شده اند. معیارهای مورد استفاده عبارتند از:بهره وری CPU: می خواهیم تا آنجا یی که ممکن است CPUمشغول باشد.توان عملیاتی (حاصل کار): اگر CPU مشغول اجرای فرایندها باشد، کاری درحال انجام است. یک معیار کار، تعداد فرایندهایی است که در واحد زمان کامل می شوند و توان عملیاتی نام دارد.زمان برگشت: فاصله زمانی از زمان تحویل فرایند تا زمان کامل شدن اجرای آن، زمان برگشت نام دارد. زمان برگشت مجموع زمان انتظار برای قرار گرفتن در حافظه، زمان قرار گرفتن در صف آمادگی، اجرا در CPU و عمل I/O است.زمان انتظار: معیار دیگر زمان تحویل یک درخواست و دریافت اولین پاسخ است. این معیار، زمان انتظار نام دارد. زمان انتظار، مدت زمان لازم برای شروع پاسخ است و شامل زمان خروجی پاسخ نمی شود.زمان پاسخ: معیار دیگر، زمان تحویل یک درخواست تا دریافت اولین پاسخ است. این معیار که زمان پاسخ نام دارد، مدت زمانی است که مدت زمانی است که طول می کشد پاسخ داده شود، نه مدت زمانی که طول می کشد تا آن پاسخ چاپ شود.9 / 48

اسلاید 10: الگوریتم های زمانبندی زمانبندی ارائه خدمت به ترتیب ورود(FCFS):در این الگوریتم، فرایندی که زودتر CPU را درخواست کرد، زودتر آنرا در اختیار می گیرد. پیاده سازی سیاست FCFS با یک صف FIFO انجام می شود. مجموعه فرایندهای زیر را در نظر بگیرید:اگر فرایندها به ترتیب p3,p2,p1 بیایند و به ترتیب FCFS خدمات بگیرند،نمودار به صورت زیر است:زمان انتظار برای P1 برابر صفر، برای P2 برابر 24 و برای P3 برابر با 27 است. بنابراین، زمان انتظار میانگین برابر (0+24+27)/3=17 است.میانگین زمان انتظار تحت سیاست FCFS کمینه نیست و ممکن است با تغییرات زیادی که در انفجار CPU انجام می شود، تغییر کند.فرایندP1P2P3زمان انفجار2433P1P2P30 24 27 30الگوریتم زمانبندی FCFS انحصاری نیست. همچنین در این الگوریتم بهره وری دستگاهها و CPU کاهش می یابد.10 / 48

اسلاید 11: زمانبندی بر حسب کوتاهترین کار (SJF):این الگوریتم به هر فرایند، طول انفجار CPU بعدی اش را می دهد. وقتی CPU مهیا باشد، به فرایندی نسبت داده می شود که انفجار CPU بعدی کوچکتری داشته باشد. اگر طول انفجار CPU بعدی دو فرایند یکسان باشد، برای انتخاب یکی از آنها، از زمانبندی FCFS استفاده می شود. زمانبندی در این الگوریتم با بررسی طول انجار CPU بعدی فرایند انجام می شود (نه طول کلی آن). به عنوان مثال فرایندهای زیر را در نظر بگیرید:با استفاده از زمانبندی SJF، این فرایندها بر اساس نمودار زیر زمانبندی می شوند:الگوریتم های زمانبندی فرایندP1P2P3P4زمان انفجار6873P4P1P3P2 24 16 9 3 0زمان انتظار برای فرایند P1 برابر با 3، برای P2 برابر با 16، برای P3 برابر با 9 و برای P4 برابر با 0 است. بنابراین میانگین زمان انتظار برابر با (3+16+9+0)/4=7 است. اگر از الگوی زمانبندی FCFS استفاده می کردیم، میانگین زمان انتظار برابر با 10.25 می شد.11 / 48

اسلاید 12: زمانبندی بر حسب کوتاهترین کار (SJF) (ادامه...)مشکل عمده الگوریتم SJF این است که در طول درخواست بعدی CPU باید مشخص باشد. برای زمانبند بلندمدت در یک سیستم دسته ای، حد زمانی را که کاربر هنگام تحویل کار تعیین کرده است به عنوان طول فرایند درنظر گرفته و سعی می شود که این حد زمانی دقیقا برآورد شود .زمانبندی SJF در زمانبندی بلندمدت کاربرد زیادی دارد.الگوریتم SJF نمی تواند در سطح زمانبندی کوتاه مدت به کار گرفته شود. زیرا طول انفجار بعدی را نمی دانیم اما می توانیم اندازه اش را پیش بینی کنیم. با تخمین این اندازه می توانیم فرایندی را محاسبه کنیم که طول انفجار بعدی آن کوتاهتر است.انفجار محاسباتی بعدی، به صورت میانگین نمایی طول های محاسبه شده انفجارهای محاسباتی قبلی پیش بینی می شود. فرض کنید tn طول nامین انفجار محاسباتی و τn+1 مقدار پیش بینی شده برای انفجار محاسباتی بعدی باشد. آنگاه برای 0 ≤ α ≤ 1 فرمول زیر را تعریف می کنیم:= α tn + (1 – α) τn τn+1 مقدار tn شامل جدیدترین اطلاعات است، به طوری که τn سابقه گذشته را ذخیره می کند و تخمین nام است. پارامتر α وزن نسبی سابقه فعلی و گذشته را در پیش بینی ما کنترل می کند.12 / 48

اسلاید 13: پیش بینی طول انفجار محاسباتی بعدیtiτiزمان... 13 13 13 4 6 4 6 انفجار محاسباتی(ti)... 12 11 9 5 6 6 8 10 پیش بینی (τi)شکل زیر یک میانگین نمایی را با α = نشان می دهد. مقدار را می توان به صورت یک مقدار ثابت یا میانگین کل سیستم تعریف کرد.τ013 / 48

اسلاید 14: الگوریتم SJF ممکن است با قبضه کردن یا بدون قبضه کردن باشد. برای زمانبندی SJF با قبضه کردن 4 فرآیند زیر را درنظر بگیرید:با استفاده از زمانبندی SJF با قبضه کردن، این فرایندها بر اساس نمودار زیر زمانبندی می شوند:میانگین زمان انتظار:((10-1)+(1-1)+(17-2)+(5-3))/4=6.5 در زمانبندی SJF بدون قبضه کردن، میانگین زمان انتظار برابر با 7.75 میلی ثانیه خواهد بود.زمانبندی بر حسب کوتاهترین کار (SJF) (ادامه...)فرآیندزمان رسیدنزمان انفجارP108P214P329P435P1P2P4P1P3 26 17 10 5 1 014 / 48

اسلاید 15: زمانبندی اولویتالگوریتم SJF حالت خاصی از الگوریتم زمانبندی اولویت است. به هر فرایند یک اولویت نسبت داده می شود و CPU به فرایندی تخصیص می یابد که بالاترین اولویت را دارا باشد. فرایندهایی با اولویت یکسان، به ترتیب FCFS زمانبندی می شوند.به عنوان مثال، فرایندهای زیر را در نظر بگیرید، به طوری که در زمان صفر به ترتیب P1,P2,…,P5 رسیده اند:با استفاده از زمانبندی اولویت، این فرایندها بر اساس نمودار زیر زمانبندی می شوند:میانگین زمان انتظار در این مثال، 8.2 میلی ثانیه است.فرایندزمان انفجاراولویتP1103P211P324P415P552P2P5P1P3P4 19 18 16 6 1 015 / 48

اسلاید 16: زمانبندی اولویت می تواند با قبضه کردن یا بدون قبضه کردن باشد.مسئله عمده در الگوریتم زمانبندی اولویت، انسداد نامحدود یا گرسنگی(قحطی)است. الگوریتم زمانبندی اولویت می تواند منجر به این شود که فرایندهایی با اولویت پایین، به مدت نامحدودی منتظر CPU باشند. در یک سیستم کامپیوتری با بار زیاد، فرایندهایی با اولویت بالا، مانع از این می شوند که CPU به فرایندهایی با اولویت پایین تعلق یابد، که ممکن است فرایند با تاخیر بسیار زیادی انجام شود و یا اینکه سیستم از کار بیافتد و تمام فرایندهای با اولویت پایین، از بین بروند.راه حل مسئله انسداد نامحدود با اولویت پایین، کهنگی است. در این تکنیک، اولویت فرایندی که به مدت زیادی در سیستم منتظر مانده است، به تدریج افزایش می یابد.زمانبندی اولویت (ادامه ...)16 / 48

اسلاید 17: زمانبندی نوبت گردشی (RR)الگوریتم نوبت گردشی (RR) مخصوص سیستم های اشتراک زمانی طراحی شده است. این الگوریتم شبیه FCFS است، با این تفاوت که در حرکت بین فرایندها، از زمانبندی قبضه کردن استفاده می شود. یک واحد زمانی کوچک، به نام کوانتوم زمانی یا برهه زمانی تعریف می شود. صف آمادگی به صورت یک صف چرخشی در نظر گرفته می شود. زمانبند CPU در طول صف آمادگی حرکت می کند و CPU را حداکثر به مدت یک کوانتوم زمانی به هر فرایند تخصیص می دهد.میانگین زمان انتظار در الگوریتم RR، اغلب زیاد است. فرایندهای زیر را درنظر بگیرید که در زمان 0 می رسند:با استفاده از زمانبندی RR، این فرایندها بر اساس نمودار زیر زمانبندی می شوند:میانگین زمان انتظار در این مثال، 5.66= میلی ثانیه است.فرایندP1P2P3زمان انفجار2433P1P2P3P1P1P1P1P1 30 26 22 18 14 10 7 4 0 17 / 48

اسلاید 18: در الگوریتم زمانبندی نوبت چرخشی، CPU به هیچ فرایندی در یک سطر، بیش از یک کوانتوم زمانی تخصیص نمی یابد. اگر انفجار محاسباتی فرایندی بیش از یک کوانتوم زمانی شود، آن فرایند قبضه می شود و در انتهای صف آمادگی قرار می گیرد. الگوریتم صف RR، با قبضه کردن همراه است.کارایی الگوریتم RR به اندازه کوانتوم زمانی بستگی دارد. از یک طرف، اگر کوانتوم زمانی بسیار بزرگ باشد (نامحدود)، سیاست RR شبیه FCFS خواهد بود. اگر کوانتوم زمانی خیلی کوچک باشد اینطور وانمود می شود که هر n فرایند، پردازنده مخصوص به خودش را دارد که سرعت هرکدام به اندازه سرعت پردازنده واقعی است.زمانبندی نوبت گردشی (RR) (ادامه ...)18 / 48

اسلاید 19: کوانتوم زمانی کوچک منجر به تعویض بستر می شود.10= زمان فرایند0610100 10 9 8 7 6 5 4 3 2 1 0تعویض بستر کوانتوم زمانی 0 12 1 69 1در نرم افزار باید اثر تعویض بستر را در کارایی زمانبندی RR درنظر بگیریم. فرض می کنیم فقط یک فرایند با 10 واحد زمانی داریم. اگر کوانتوم زمانی برابر با 12 واحد زمانی باشد، فرایند در کمتر از یک کوانتوم زمانی خاتمه می یابد و سرباری ندارد. اگر کوانتوم زمانی برابر با 6 واحد زمانی باشد، این فرایند به دو کوانتوم زمانی نیاز دارد و منجر به تعویض بستر می شود. اگر کوانتوم زمانی برابر با یک واحد زمانی باشد، نیاز به 9 تعویض بستر است و بدین ترتیب اجرای فرایند کند می شود. بنابراین، برای مقابله با تعویض بستر، علاقه مند هستیم که کوانتوم زمانی بزرگ باشد.19 / 48

اسلاید 20: تغییر زمان برگشت بر اساس کوانتوم زمانیکوانتوم زمانیمیانگین زمان برگشتفرایندزمانP16P23P31P4720 / 48

اسلاید 21: زمان برگشت نیز به اندازه کوانتوم بستگی دارد. همانطور که از شکل پیداست، میانگین زمان برگشت مجموعه ای از فرایندها، با افزایش اندازه کوانتوم زمانی، الزاما بهبود نمی یابد.به طور کلی، میانگین زمان برگشت در صورتی بهبود می یابد که اغلب فرایندها انفجار محاسباتی بعدی خودشان را فقط در یک کوانتوم زمانی به اتمام برسانند.با درنظر گرفتن زمان تعویض بستر، هرچه کوانتوم زمانی کوچکتر باشد، میانگین زمان برگشت افزایش می یابد، زیرا نیاز به تعویض بستر بیشتری است. از طرف دیگر اگر کوانتوم زمانی بسیار بزرگ باشد، زمانبندی RR به FCFS تبدیل می شود.تغییر زمان برگشت بر اساس کوانتوم زمانی (توضیح شکل)21 / 48

اسلاید 22: زمانبندی صف چندسطحیدسته دیگری از الگوریتم های زمانبندی برای وضعیت هایی ایجاد شدند که در آنها، فرایندها می توانند به دو گروه تقسیم شوند.الگوریتم زمانبندی صف چندسطحی، صف آمادگی را به چند بخش مجزا تقسیم می کند. هر فرایند بر اساس خواصی که دارد در صفی قرار می گیرد . این صفات عبارتند از: اندازه حافظه، اولویت فرایند، یا نوع فرایند. هر صف الگوریتم زمانبندی خاص خودش را دارد. علاوه بر این، بین صف ها نیز باید زمانبندی وجود داشته باشد که بر اساس زمانبندی همراه با قبضه کردن و با اولویت ثابت، پیاده سازی می شود.امکان دیگر، استفاده از برهه زمانی در بین صف ها است. هر صف بخشی از زمان صف را به خود اختصاص می دهد و بین فرایندهای مختلف آن صف زمانبندی می کند.22 / 48

اسلاید 23: زمانبندی صف چندسطحیفرایندهای سیستمفرایندهای محاوره ایفرایندهای ویرایشی محاوره ایفرایندهای دسته ایفرایندهای دانشجوبالاترین اولویتپایین ترین اولویتدر این شکل هر صف نسبت به صف های با اولویت پایین تر، اولویت مطلقی دارد.23 / 48

اسلاید 24: زمانبندی صف بازخوردی چندسطحیمعمولا در الگوریتم زمانبندی صف چندسطحی، فرایندها هنگام ورود به سیستم در صفی قرار می گیرند، به طوری که از صفی به صف دیگر نمی روند. اما زمانبندی صف بازخوردی چندسطحی به فرایندها اجازه می دهد از صفی به صف دیگر منتقل شوند. فلسفه این کار این است که ویژگی های انفجارهای محاسباتی فرایندها با یکدیگر متفاوت است. اگر فرایندی به مدت زیادی CPU را در اختیار گیرد، به صفی با اولویت پایین تر منتقل می گردد. بدین ترتیب، فرایندهای مقید به I/O و محاوره ای، در صف هایی با اولویت بالا قرار می گیرند. به طور مشابه، فرایندی که به مدت زیادی در صفی با اولویت پایین تر منتظر می ماند، ممکن است به صفی با اولویت بالاتر منتقل شود. در این شکل کهنگی، از مشکل گرسنگی جلوگیری می شود.24 / 48

اسلاید 25: صف های بازخورد چندسطحیکوانتوم زمانی = 8کوانتوم زمانی = 16FCFS25 / 48

اسلاید 26: به طور کلی، زمانبند صف بازخورد چندسطحی، توسط پارامترهای زیر تعریف می شوند:تعداد صف ها.الگوریتم زمانبندی برای هر صف.روشی که تعیین می کند چه هنگامی یک فرایند با صفی با اولویت بیشتر منتقل شود.روشی که تعیین می کند چه هنگامی یک فرایند با صفی با اولویت کمتر منتقل شود.روشی که تعیین می کند فرایندی که نیاز به خدمات دارد، به چه صفی وارد شود.این الگوریتم می تواند طوری پیکربندی شود که با سیستمی که درحال طراحی است سازگاری داشته باشد.زمانبندی صف بازخوردی چندسطحی (ادامه ...)26 / 48

اسلاید 27: زمانبندی چندپردازنده ایاگر چندین CPU در سیستم وجود داشته باشند، مسئله زمانبندی پیچیده تر می شود. در سیستم های چندپردازنده ای سیستم های همگن (کارایی پردازنده در آن یکسان است) را درنظر می گیریم. هر پردازنده آماده می تواند هر فرایند موجود در صف را اجرا کند. فرض می کنیم دستیابی به حافظه به طور یکنواخت صورت می گیرد. در سیستم های همگن که پردازنده های آنها متفاوتند فقط برنامه هایی که برای پردازنده کامپایل شده اند بر روی آنها قابل اجرا می باشند.در پردازنده های همگن (کارایی پردازنده آنها یکسان است) نیز محدودیت هایی برای زمانبندی وجود دارد. در یک دستگاه I/O که به یک گذرگاه اختصاصی یک پردازنده وصل شده است فرایندهایی می خواهند از این دستگاه استفاده کنند زمانبندی شوند تا بر روی آن پردازنده اجرا شوند در غیراینصورت قادر به استفاده از آن دستگاه نخواهند بود.27 / 48

اسلاید 28: اگر چند پردازنده همگن در سیستم موجود باشند، مسئله اشتراک بار پیش خواهد آمد. می توان برای هر پردازنده یک صف جداگانه درنظر گرفت. در این الگو، می توان از دو روش زمانبندی استفاده کرد. در روش اول، هر پردازنده خودش را زمانبندی می کند. برای این منظور، هر پردازنده صف آمادگی مشترک را بررسی می کند و فرایندی را برای اجرا انتخاب می کند. در روش دوم، یک پردازنده می تواند پردازنده دیگر را زمانبندی کند و بدین ترتیب یک ساختار رئیس/مرئوس به وجود می آید.زمانبندی چندپردازنده ای (ادامه ...)28 / 48

اسلاید 29: زمانبندی بی درنگمحاسبات بی درنگ بر دو نوع اند. سیستم های بی درنگ سخت لازم است یک وظیفه حیاتی، در زمان معینی به اتمام برسد. معمولا فرایند همراه با مدت زمان موردنیاز برای کامل شدن آن یا اجرای I/O، به پردازنده تحویل داده می شود. زمانبند ممکن است فرایند را بپذیرد و تضمین کند که آن فرایند به موقع به اتمام برسد، یا در صورت غیرممکن بودن اجرای آن، از پذیرفتنش خودداری کند. این عمل رزرو کردن منبع نام دارد.محاسبات بی درنگ نرم محدودیت کمتری دارد. این محاسبات مستلزم این است که فرایندهای حیاتی اولویت بیشتری داشته باشد. پیاده سازی عملیات بی درنگ نرم مستلزم طراحی دقیق زمانبند و جنبه های دیگری از سیستم عامل است که به زمانبند مرتبط هستند. اولا سیستم بایدزمانبندی اولویت داشته باشد و فرایندهای بی درنگ بالاترین اولویت را دارا باشند. ثانیا تاخیر توزیع باید کوچک باشد. 29 / 48

اسلاید 30: به راحتی می توان مطمئن شد که ویژگی اول در سیستم برقرار است ولی حصول اطمینان از ویژگی دوم کمی پیچیده است زیرا اغلب سیستم های عامل مجبور می شوند که قبل از تعویض بستر منتظر بمانند تا یک فراخوان سیستم کامل شود یا عمل I/O مسدود گردد. تاخیر توزیع در این سیستم ها می تواند طولانی باشد.برای اینکه تاخیر توزیع اندک باشد، فراخوان سیستم باید قابل قبضه شدن باشد. برای رسیدن به این هدف می توان به روش های گوناگونی عمل کرد. یک روش این است که در فراخوان های سیستم طولانی، از نقاط قبضه شدن استفاده گردد که در این نقاط کنترل می شود که آیا لازم است فرایندی با اولویت بالا اجرا شود یا خیر. راه حل دیگر این است که کل هسته قابل قبضه شدن باشد.اگر فرایندی با اولویت بالا نیاز به خواندن و تغییر ساختمان داده ای از هسته داشته باشد که در حال حاضر در اختیار فرایندی با اولویت کمتر است، چه اتفاقی می افتد؟ فرایندی با اولویت بالاتر منتظر می ماند تا فرایندی با اولویت بالاتر به اتمام برسد. این وضعیت را اولویت معکوس می نامند.زمانبندی بی درنگ (ادامه ...)30 / 48

اسلاید 31: این مسئله را می توان از طریق پروتکل وراثت اولویت حل کرد که در آن تمام فرایندهایی که منابعی را دراختیار دارند که مورد نیاز فرایندی با اولویت بالاتر است، اولویت بالا را به ارث ببرند تا منابع موردنظر را دراختیار گیرند. وقتی کارشان انجام شد، اولویت اولیه خود را دارا خواهند شد.مرحله برخورد تاخیر توزیع دارای دو مولفه است:قبضه کردن هر فرایندی که در هسته درحال اجراست.فرایندهایی با اولویت پایین تر، منابع موردنیاز فرایندهای با اولویت بالاتر را رها می کنند.زمانبندی بی درنگ (ادامه ...)31 / 48

اسلاید 32: تاخیر توزیعبرخوردهاتوزیعاجرای فرایند بی درنگپردازش وقفهفاصله زمانی پاسخرویدادپاسخ به رویدادزمانتاخیر توزیعمهیا شدن فرایند32 / 48

اسلاید 33: ارزیابی الگوریتم های زمانبندیاولین مسئله، تعیین معیارهای انتخاب الگوریتم است. معیارهای ما ممکن است شامل مقیاس های گوناگونی باشد:بیشترین بهره وری CPU در حالتی که حداکثر زمان پاسخ برابر با 1 ثانیه است.بیشترین توان عملیاتی، به طوری که میانگین زمان برگشت، به طور خطی مناسب با کل زمان اجراست.پس از تعریف معیارهای انتخاب، آنها را با ملاحظات خاصی بررسی می کنیم.33 / 48

اسلاید 34: مدلسازی قطعییکی از مهمترین روش های ارزیابی الگوریتم ها، ارزیابی تحلیلی نام دارد. ارزیابی تحلیلی، با استفاده ار الگوریتم و بارکاری سیستم، فرمول یا عددی را تولید می کند که کارایی الگوریتم را برای آن بار سیستم ارزیابی می کند. یک نوع ارزیابی تحلیلی به نام مدلسازی قطعی است. این روش، یک بار کاری از قبل تعیین شده ای می گیرد و کارایی هر الگوریتم را برای آن بار کاری تعریف می کند.به عنوان مثال 5 فرایند زیر را در نظر بگیرید که همگی در زمان صفر وارد می شوند:فرایندP1P2P3P4P5انفجار محاسباتی1029371234 / 48

اسلاید 35: الگوریتم FCFS:میانگین زمان انتظار: 28=5/(49+42+39+10+0)الگوریتم SJF:میانگین زمان انتظار: (10+32+0+3+20)/5=13الگوریتم RR (با کوانتوم زمانی 10 میلی ثانیه):میانگین زمان انتظار: (0+32+20+23+40)/5=23با این ارزیابی ها مشاهده می کنیم که در این حالت، میانگین زمان انتظار نصف زمانبندی FCFS است و مقدار آن در الگوریتم RR متوسط است.مدلسازی قطعی (ادامه ...)P1P2P3P4P5 61 49 42 39 10 0P3P4P1P5P261 32 20 10 3 0P2P5P2P5P4P3P2P161 52 50 40 30 23 20 10 035 / 48

اسلاید 36: مدلسازی قطعی، سریع و ساده است. اعداد دقیقی را ارائه می کند که برای مقایسه الگوریتمها به کار می روند. ولی به تعداد دقیقی از ورودی ها نیاز دارد و پاسخ آن نیز برای همان ورودی ها صادق است.کاربردهای مدلسازی قطعی، توصیف الگوریتم های زمانبندی و ارائه مثال هاست. در مواردی که یک برنامه باید بارها و بارها اجرا شود و نیازمندی های پردازش آن دقیقا قابل سنجش باشد، استفاده از مدلسازی قطعی برای انتخاب الگوریتم زمانبندی، مناسب است. با اجرای مدلسازی قطعی بر روی مثال های متفاوت رفتارهایی مشاهده می شود که به طور جداگانه قابل تحلیل و اثبات خواهند بود.مدلسازی قطعی (ادامه ...)36 / 48

اسلاید 37: مدل های صف بندیسیستم کامپیوتری به صورت شبکه ای از کارگزاران توصیف می گردد. هر کارگزار صفی از فرایندهای درحال انتظاردارد. CPU کارگزاری است که دارای صف آمادگی است و سیستم I/O نیز دارای صف های دستگاه است. با داشتن نرخ رسیدن فرایندها و نرخ های خدمات، می توان بهره وری، میانگین طول صف، میانگین زمان انتظار و غیره را تعیین کرد. این روش را تحلیل شبکه صف بندی می نامند.تحلیل صف در مقایسه الگوریتم های زمانبندی مفید واقع می شوف اما محدودیت هایی دارد. فعلا الگوریتم ها و توزیع هایی که می توانند پردازش شوند، بسیار محدود است. کار کردن با ریاضیات الگوریتم ها یا توزیع های پیچیده، دشوار است. تحلیل صف بندی نیتزمند ساخت فرضیه های مستقلی است که ممکن است دقیق نباشند. به طور کلی، مدل های صف، تقریبی از سیستم واقعی را نشان می دهد. در نتیجه، دقت محاسبات آن زیر سوال است.37 / 48

اسلاید 38: شبیه سازی هابرای ارزیابی دقیق تر الگوریتم های زمانبندی، می توانیم از شبیه سازی استفاده کنیم. شبیه سازی مستلزم برنامه نویسی یک مدل سیستم کامپیوتری است. ساختمان داده های نرم افزاری، اجزای اصلی یک سیستم را می سازند. داده های شبیه سازی به روش های گوناگونی تولید می شوند. متداولترین روش، استفاده از مولد اعداد تصادفی است که برای تولید فرایندها، زمان های انفجار CPU، زمان های رسیدن فرایندها، زمان های خروج و غیره برحسب توزیع های احتمالی به کار می رود.شبیه سازی برحسب توزیع، مکن است به دلیل روابط بین رویدادهای متوالی در سیستم واقعی، دقیق نباشد. توزیع فراوانی فقط نشان می دهد که هر رویداد چقدر اتفاق می افتد و چیزی در مورد ترتیب وقوع آنها ارائه نمی کند. برای حل این مسئله از نوارهای ردیابی استفاده می شود. نوار ردیابی با نظارت بر سیستم واقعی و ثبت دنباله ای از رویدادهای واقعی ایجاد می شود. این روش می تواند نتایج دقیقی را بری وردی هایش ایجاد کند. شبیه سازی می تواند گران تمام شود. زیرا گاهی ساعت ها وقت کامپیوتر را به خود اختصاص می دهد.38 / 48

اسلاید 39: ارزیابی زمانبندی های CPU با شبیه سازیاجرای فرایند واقعیشبیه سازیFCFSشبیه سازیSJFشبیه سازیRR(q=14)آمارهای کارایی برایFCFSآمارهای کارایی برایSJFآمارهای کارایی برایRR(q=14)نوار ردیابی...CPU 10I/O 213CPU 12I/O112CPU 2I/O 147CPU 173…39 / 48

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

اسلاید 41: مدل های زمانبندی فراینددر این بخش، زمانبندی فرایند را در سیستم های سولاریس 2، ویندوز 2000 و لینوکس بررسی خواهیم کرد. قبل از پرداختن به این مدل ها بندها را با زمانبندی فرایند ارتباط می دهیم.در فصل 5 بندها را در مدل فرایند معرفی کردیم و در نتیجه هر فرایند می تواند چندین بند از کنترل را در اختیار داشته باشد.بندهای سطح کاربر توسط کتابخانه بندها مدیریت می شود و هسته از آنها خبر ندارد. برای اجرا شدن بر روی CPU، بندهای سطح کاربر به بند هسته مربوطه نگاشت می شود، ممکن است این نگاشت به طور غیرمستقیم و از طریق فرایند سبک (LWP) باشد.کتابخانه بند، بندهای سطح کاربر را طوری زمانبندی می کند که بر روی LWP آماده اجرا شوند. این طرح زمانبندی محلی فرایند نام دارد که در آن زمانبندی بند در یک برنامه کاربردی به طور محلی صورت می گیرد. هسته با استفاده از زمانبندی سراسری سیستم تصمیم می گیرد که کدام بند هسته باید زمانبندی شود.41 / 48

اسلاید 42: سولاریس 2سولاریس 2 از زمانبندی مبتنی بر اولویت فرایندها استفاده می کند. چهار رده از زمانبندی را در اختیار دارد که به ترتیب اولویت عبارتند از: بی درنگ، سیستم، اشتراک زمانی و محاوره ای. هر رده شامل اولویت ها و الگوریتم های زمانبندی مختلفی است، ولی اشتراک زمانی و محاوره ای از یک سیاست زمانبندی استفاده می کنند.فرایند با یک LWP شروع می شود و قادر است در صورت نیاز LWPهای جدیدی ایجاد کند. هر LWP، رده زمانبندی و اولویت فرایند پدر را به ارث می برد.رده زمانبندی فرضی برای فرایند، اشتراک زمانی است. به طور پیش فرض رابطه معکوسی بین اولویت ها و برش های زمانی وجود دارد. سولاریس 2 برای اجرای فرایندهای هسته از رده سیستم استفاده می کند. سیاست زمانبندی برای رده سیستم، برش زمانی نیست. بند متعلق به رده سیستم آنقدر اجرا می شود تا متوقف شود یا توسط بندی با اولویت بیشتر قبضه گردد. 42 / 48

اسلاید 43: در رده بی درنگ، بندها بالاترین اولویت را دارند. فرایندهای این رده قبل از فرایندهای موجود در رده های دیگر اجرا می شوند. به طور کلی، تعداد اندکی از فرایندها به رده بی درنگ تعلق دارند. هر رده زمانبندی شامل مجموعه ای از اولیتها است. اما، زمانبند اولویت های ویژه رده را به اولویت های سراسری تبدیل می کند و بندی را برای انتخاب اجرا می کند که اولویت سراسری آن بالاترین است. بند انتخاب شده در CPU اجرا می شود تا یکی از موارد رخ دهد:مسدود شود.از برش زمانی خود استفاده کند (اگر بند، سیستم نیست).توسط بندی با اولویت بالاتر قبضه شود.اگر اولویت چندین بند یکسان باشد، زمانبند از صف نوبت چرخشی استفاده می کند.سولاریس 2 (ادامه ...)43 / 48

اسلاید 44: زمانبندی در سولاریس 2اولویت سراسریبالاترینترتیب زمانبندیاولیاولویت ویژه ردهرده های زمانبندصف اجراسیستممحاوره ای و اشتراک زمانیپایین ترینآخریبندهای سطح هسته مربوط بهLWP های بی درنگبندهای خدمات هستهبندهای سطح هسته محاوره ایو LWP های اشتراک زمانی بی درنگ44 / 48

اسلاید 45: ویندوز 2000ویندوز 2000 بندها را با استفاده از الگوریتم زمانبندی قبضه کردن مبتنی بر اولویت، زمانبندی می کند. زمانبند ویندوز 2000 تضمین می کند که بندی با بالاترین اولویت همیشه اجرا می شود. بخشی از هسته ویندوز 2000 که زمانبندی را انجام می دهد، توزیع کننده نام دارد. بندی که توسط توزیع کننده برای اجرا انتخاب شد، آنقدر اجرا می شود تا توسط بندی با اولویت بالاتر قبضه شود، خاتمه یابد، کوانتوم زمانی ان به پایان برسد، یا فراخوان سیستم مسدود کردن را اجرا نماید. ویندوز 2000 تضمین نمی کند که یک بند بی درنگ دراثنای محدوده زمانی خاصی اجرا شود.توزیع کننده از طرح اولویت 32 سطحی برای تعیین ترتیب اجرای بندها استفاده می کند. اولویت ها به دو رده تقسیم می شوند: رده متغیر و رده بی درنگ. توزیع کننده مجموعه ای از صف ها را از بالاترین به پایین ترین اولویت پیمایش می کند تا بندی را بیابد که آماده اجرا است. اگر هیچ بندی آماده ای پیدا نشود، توزیع کنندهف بند ویژه ای را با نام بند بیکار را اجرا می نماید. اولویت هر بند به رده اولویتی که به آن تعلق دارد، و به اولویت نسبی در داخل آن رده بستگی دارد. هر بند دارای یک اولویت پایه است.45 / 48

اسلاید 46: وقتی کوانتوم زمانی بندی به اتمام برسد، آن بند دچار وقفه می شود. اگر آن بند در رده اولویت متغیر باشد، اولویت ان کاهش می یابد. اولویت هیچگاه از اولویت پایه کمتر نمی شود. وقتی بندی با اولویت متغیر از یک عملیات انتظار آزاد می شود، توزیع کننده، اولویت انرا افزایش می دهد.ویندوز 2000 بین فرایند پیش زمینه و پس زمینه تمایز قائل می شود. فرایند پیش زمینه اجازه دارد قبل از وقوع قبضه کردن اشتراک زمانی، سه برابر بیشتر اجزا شود.ویندوز 2000 (ادامه ...)اولویت بیکارزیرنرمالنرمالبالای نرمالبالابی درنگبحران زمانی151515151531بالاترین6810121526بالاتر از نرمال579111425نرمال468101324زیر نرمال35791223پایین ترین24681122بیکار111111646 / 48

اسلاید 47: لینوکسلینوکس دو الگوریتم زمانبندی را برای فرایندها ارائه می دهد. یکی از آنها الگوریتم اشتراک زمانی منصف برای زمانبندی قبضه کردن بین چندین فرایند است. دیگری مربوط به وظایف بی درنگ است که در ان اولویت های مطلق مهمتر از منصفانه است. لینوکس اجازه می دهد که فقط فرایندهایی که در حالت کاربر اجرا می شوند، قبضه گردند. اگر فرایندی در حالت هسته درحال اجرا باشد، حتی اگر فرایند بی درنگی با اولویت بتلاتر آماده شود، نمی تواند آنرا قبضه کند.اولین رده زمانبندی مربوط به فرایندهای اشتراک زمانی است. از نظر سنتی، لینوکس برای فرایندهای اشتراک زمانی از الگوریتم مبتنی بر اعتبار استفاده می کند. این الگوریتم دو عامل را ترکیب می کند: سابقه و اولویت فرایند.سیستم اعتباردهی، به طور خودکار، اولویت های بالا را به فرایندهای محاوره ای و مقید به I/O می دهد. علتش این است که زمان پاسخ این فرایندها مهم است. استفاده از اولویت فرایند در محاسبه اعتبارات جدید، موجب می شود تا اولویت یک فرایند، قابل تنظیم باشد.47 / 48

اسلاید 48: لینوکس دو رده از زمانبندی بی درنگ را پیاده سازی می کند که موردنیاز POSIX.1b است: خدمات به ترتیب ورود (FCFS) و نوبت گردشی (RR). زمانبندی بی درنگ لینوکس، زمانبندی نرم است.کد هسته لینوکس، نمی تواند توسط کد حالت کاربر قبضه شود. اگر وقتی که هسته در حال اجرای فراخوان سیستم در فرایند دیگری باشد، وقفه ای به یک فرایند بی درنگ وارد شود، این فرایند بی درنگ باید منتظر بماند تا فراخوان سیستمی که در حال اجراست کامل یا مسدود شود.لینوکس (ادامه ...)48 / 48

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

اسلاید 50: 50 سهیلا ابراهیمی صبا صفحات 1 تا 16 مهسا فرجو صفحات 17 تا 32 مهشید ابراهیم نژاد صفحات 33 تا 48 تنظیمات