قسمت سوم: آشنایی با مفاهیم پردازش و شیوه کار پردازنده (CPU)
سه شنبه 8 دی 1394 9:34 PM
به عنوان مثال، برای تضمین اینکه تمام کاربران سرویسهای خوبی دریافت می کنند، می خواهیم حداکثر زمان پاسخ را می نیمم کنیم. سیستمی با زمان پاسخ قابل پیش بینی و معقول را می توان مطلوبتر از سیستمی دانست که بر اساس میانگین سریعتر می باشد، اما به شدت متغیر است. با این حال، برای حداقل کردن تغییرات چندان کار زیادی بر روی زمانبندی های CPU صورت نگرفته است.
با بررسی الگوریتمهای مختلف ، می توانیم عملکرد انها را مشخص کنیم. یک تصویر سازی دقیق می تواند خیلی از فرایندها را درگیر کند، و هر یک رشته ای از صدها اجرای مربوط به I/O و CPU می شود. برای ساده سازی این تصویرسازی، تنها یک اجرا از CPUرا (برحسب میکروثانیه) در هر فرایند مثالهای خود بررسی می کنیم. معیار ما در مقایسه میانگین زمان انتظار است.
تا به حال آسانترین الگوریتم زمانبندی CPU الگوریتم برنامه ریزی اولین ورودی، اولین سرویس دهی (FCFS) بود. با این طرح، فرایندی که اول CPU را فراخوانی می کند، ابتدا در CPU جایابی می شود. پیاده سازی سیاستهای FCFS با یک صف FIFO به اسانی مدیریت می شود. وقتی یک فرایند وارد صف آمادگی می شود، PCB آن در انتهای صف قرار می گیرد. زمانی که CPU آزاد باشد، جایابی آن در ابتدای صف آمادگی خواهد بود. کد زمانبندی FCFS برای خواندن بسیار راحت است و فهمیدن آن نیز راحت است.با این حال، زمان انتظار میانگین تحت سیاستهای FCFS ، معمولا خیلی طولانی است. مجموعه فرایندهای زیر را که در زمان صفر می رسند در نظر بگیرید، با در نظر داشتن طول زمان اجرای CPU بر حسب میکروثانیه خواهیم داشت:
فرایند زمان اجرا
P1 24
P2 3
P3 3
اگر فرایندهای وارد شده به ترتیب p1، p2 و p3 باشد، و به صورت FCFS مرتب شوند، نتایج به صورت زیر در نمودار گانت نشان داده می شود:
|
P1 |
P2 |
P3 |
|
|
30 |
27 |
24 |
0 |
اولویتها را می توان به صورت درونی یا بیرونی تعریف کرد. اولویتهای درونی از کمیتها یا مقادیر قابل اندازه گیری برای محاسبه اولویت یک فرایند دارند. مثلا، محدودیتهای زمانی، نیازمندی های حافظه، تعداد فایلهای باز، و نرخ میانگین اجرای I/O تا میانگین اجرای CPU در اولویتهای محاسباتی مورد استفاده قرار می گیرند. اولویتهای بیرونی توسط معیارهایی مشخص می شوند که در خارج سیستم عامل قرار دارند، مثل اهمیت فرایند، نوع و مقدار بودجه ای که برای هر کامپیوتر مصرف می شود، اسپانسرینگ سازمانها و دیگر عوامل که عمدتا سیاستگذاری ها می باشند، مربوط می شود.زمانبندی اولویت را می توان پیشگیرانه و غیر پیشگیرانه دانست. زمانیکه یک فرایند به صف آمادگی می رسد، اولویت آن با اولویت فرایندهای در حال اجرا مقایسه می شود.اگر اولویت فرایند تازه وارد شده بالاتراز اولویت فرایندی باشد که در حال حاضر در حال اجرا است، اولویت پیشگیرانه الگوریتم زمانبندی موجب می شود، CPU درگیر می شود.الگوریتم زمانبندی اولویت غیر پیشگیرانه به سادگی فرایند جدید را در ابتدای صف آمادگی قرار می دهد.
مشکل اصلی با الگوریتم زمانبندی اولویت به صورت بلوک کنندگی نامتناهی است. فرایندی که اماده اجرا است اما CPU را در اختیار ندارد، می توان آن را بلوک شده در نظر گرفت و منتظر CPU می ماند. یک الگوریتم زمانبندی می تواند چندین فرایند کم اهمیت را تا مدت نامعلومی از CPU بگیرد. در یک سیستم کامپیوتری پرکار یک جریان ثابت از فرایندهای پر اولویت وجود دارد که می تواند از اینکه یک برنامه کم اولویت مدت زیادی CPU را به خود اختصاص دهد، جلوگیری کند. عموما ، یکی از دو حالت روی می دهد. یا فرایند اجرا می شود (در ساعت 2 صبح یکشنبه زمانی که سیستم کاملا بیکار است) یا سیستم کامپیوتر از کار می افتد و تمام فرایندهای کم اهمیت نا تمام باقی می مانند. (شایعه ها حاکی از ان است که زمانی که در MIT کامپیوتر 7094 IBM را از کار انداختند، فرایندهای کم اهمیت یافتند که در سال 1967 ارسال شده بود و هنوز هم اجرا نشده بود).پاسخ این مسئله در مورد بلوک شدن نامتناهی فرایندهای کم اولویت ، AGING است. AGING روشی برای افزایش تدریجی اولویت فرایندها یی است که در یک سیستم برای مدت طولانی منتظر می مانند. مثلا، اگر اولویتها از صفر (پایین) تا 127 (بالا) درجه بندی شوند، می توانیم اولویت انتظار فرایند را با 1 در هر 14 دقیقه افزایش دهیم. نهایتا، حتی یک فرایند در با یک اولویت درونی صفر می تواند بالاترین اولویت را در سیستم داشته باشد و می تواند اجرا شود. در واقع، بیشتر از 32 ساعت برای فرایند اولویت صفر نسبت به اولویت 127 برای ماندگاری زمان مصرف نمی شود.
الگوریتم زمانبندی RR مخصوصا برای سیستم های اشتراک زمانی طراحی شده است. یک واحد کوچکی از زمان ، به نام کوانتوم زمانی، یا تکه زمانی، تعریف می شود. صف آمادگی مثل یک صف دایره ای عمل می کند.اگر فرایندی مدت زمان ریادی را از cpu بگیرد، به صف فرایندهای کم اهمیت منتقل می شود. این طرح باعث می شود که از محدود شدن به I/O و فرایندهای تعاملی در صفهای اولویت بالا خلاص شود. به طور مشابه، اگر فرایندی مدت زمان زیادی در یک صف کم اهمیت مانده باشد، ممکن است به صف اولویت بالا منتقل شود. این نوعی از AGING می باشد که می تواند موجب جلوگیری از قحطی زدگی شود.مثلا یک زمان بندی کننده صف فیدبک چندسطحی با 3 سطح در نظر بگیرید که از صفر تا 2 شماره گذاری شده است. برنامه زمان بند اول فرایندهای صف 0 را ایجاد می کند. زمانی که فرایندهای سطح صفر اجرا شدند،فرایندهای سطح 1 اجرا می شوند. به طور مشابه، فرایندهای سطح 2 اگر صفهای صفر و 1 خالی باشند، اجرا می شوند. یک فرایند که برای سطح 1 می رسد موجب عدم دسترسی به سطح 2 می شود. و اگر برای سطح 1 فرایندی برسد، ار اجرا شدن برنامه های سطح 1 جلوگیری می شود.
به سطح 0 صف امادگی فرایندی وارد می شود. فرایند صف صفر یک کوانتوم زمانی دارد که برابر 8 میلی ثانیه است. اگر در مدت زمان مربوطه این فرایند تمام نشد، به انتهای فرایندهای سطح 1 وارد می شود. اگر صف صفر خالی باشد، اولین فرایند سطح 1 که دارای کوانتوم 16 میلی ثانیه می باشد اجرا می شود. اگر کامل نشد ، از اجرای ان جلوگیری به عمل می آید، و به صف 2 اضافه می شود. فرایندهای صف 2 اگر صفهای 1 و 0 خالی باشند، بر اساس FCFS اجرا می شوند.این الگوریتم زمانبندی بالاترین اولویت را به هر فرایندی که در زمان اجرای 8میلی ثانیه ای و یا کمتر زمان CPU را بخواهد ، می دهد. چنینی فرایندی سریعا وارد CPU شده و اجرای ان صورت می گیرد، و برای اجرا در i/o سریعا از CPU خارج می شود. فرایندهایی که به زمانی بیش از 8 نیاز دارند، اما کمتر از 24 هستند، به سرعت مورد محاسبه قرار می گیرند، اگر چه که اولویت آن پایینتر از فرایندهای کوتاهتر است.
در حالیکه پردازنده دیگری خیلی مشغول بود برای جلوگیری از این موقعیت، از یک صف آمادگی رایج استفاده می کنیم.تمام پردازنده ها وارد یک صف می شوند و برای هر یک از پردازنده ها زمانبندی می شوند.در چنین طرحی، یکی از دو راهکار زمانبندی را می توان مورد استفاده قرار داد. در یک راهکار، هر پردازنده، خود زمانبندی را افزایش می دهد. هر پردازنده صف امادگی را امتحان می کند و فرایندی را برای اجرا انتخاب می کند. همانطور که در فصل 5 می بینیم، اگر چندین پردازنده داشته باشیم، که می خواهند به یک سازمان داده ای رایج دسترسی داشته باشند و آن را ارتقا دهند؛ هر پردازنده باید به دقت برنامه ریزی شود. باید مطمئن شویم که دو پردازنده یک فرایند را انتخاب نمی کنند. و این پردازشها از صف گم نمی شوند. راهکار دیگر از این مشکل جلوگیری می کند و این کار را با قراردادن یک پردازنده به عتوان زمانبند دیگر پردازنده ها مشخص می کند. بنابراین ایجاد یک سازمان ارباب/رعیتی را موجب می گردد.
ادامه دارد...
