سلام دوستان. این مثال منو تو ابهام برده. حالا میگم. سوالو ببینی:
جدول زمان ورود و زمان خدمت زیر را در نظر بگیرید. و متوسط زمان انتظار برای هر یک از سیاستهای زمان بندی rr و srt و fcfs را به دست اورید. کوانتوم زمانی ۳ ثانیه می باشد؟
فرایند D C B A
زمان ورود ۰ ۲ ۵ ۸
زمان خدمت ۱۲ ۵ ۴ ۱۵
دوستان این الگوریتم SRT از کوانتومی که گفته شده استفاده می کنه یا نه؟؟؟؟ این کوانتوم ۳ ثانیه که گفته شده فقط برای RR هست؟؟؟؟
میشه حلش کنید؟ یه دنیا ممنون میشم.. تو این ماه رمضونی اجرتون با خدای عزیز
من هر سه روش رو توضیح میدم ولی متوسط زمان انتظار رو خودتون زحمتش رو بکشید. یعنی این توضیحات رو که میگم, روی کاغذ در قالب نمودار گانت پیاده کنید و بعدش دیگه, پیدا کردن متوسط زمان انتظار راحت میشه.
در ابتدا روش fcfs) fcfs یک الگوریتم زمانبندی انحصاری هست) رو توضیح میدم.
فرآیند A که در زمان ۰ وارد سیستم میشه و به مدت ۱۲ میلی ثانیه اجرا میشه و تموم میشه یعنی توو نمودار گانت از زمان صفر شروع میشه تا زمان ۱۲/ فرآیند B هم که از زمان ۲ وارد سیستم شده بود حالا از زمان ۱۲ باید وارد سیستم بشه یعنی پس از تموم شدن اجرای کامل فرآیند A . چرا اینجوری شد؟ به خاطر اینکه fcfs یک الگوریتم زمانبندی انحصاری هست یعنی فرآیندی که CPU رو در اختیار می گیره تا همه زمان خدمتش تموم نشه از سیستم خارج نمیشه. به همین خاطر هست که فرآیند A تا زمان ۱۲ CPU رو به صورت انحصاری در اختیار خودش داره و نمیخواد که به فرآیند دیگه ای بده. خوب در ادامه توضیحات خدمتتون عرض کنم که همونطور که قبلا" گفته شد حالا فرآیند B از زمان ۱۲ وارد سیستم میشه و مطابق با زمان خدمتش به مدت ۵ میلی ثانیه اجرا میشه یعنی توو نمودار گانت از زمان ۱۲ شروع میشه تا زمان ۱۷/ فرآیند بعدی هم که فرآیند C هست که در زمان ۱۷ وارد سیستم میشه یعنی پس از تموم شدن اجرای کامل فرآیند B و فرآیند C هم مطابق با زمان خدمتش به مدت ۴ میلی ثانیه اجرا میشه یعنی توو نمودار گانت از زمان ۱۷ شروع میشه تا زمان ۲۱/ فرآیند بعدی هم که باید وارد سیستم بشه فرآیند D هست که در زمان ۲۱ وارد سیستم میشه یعنی پس از تموم شدن اجرای کامل فرآیند C و فرآیند D هم مطابق با زمان خدمتش به مدت ۱۵ میلی ثانیه اجرا میشه یعنی توو نمودار گانت از زمان ۲۱ شروع میشه تا زمان ۳۶/
فعلا" الگوریتم fcfs رو تمرین بکنید و زمان انتظارش رو بدست بیارین. ان شاا... فردا اون دو تا الگوریتم باقیمانده رو هم توضیح میدم. ببخشید که نتونستم الان توضیح بدم چون یه کاری پیش اومد.امیدوارم که مطالب به دردتون بخوره. تا فردا
خیلی ممنون. من منتظرم که الگوریتم str را زود تر توضیح بدهید.
با سلام
در ادامه , الگوریتم SRT رو توضیح میدم.(الگوریتم SRT , یک الگوریتم زمانبندی غیرانحصاری هست و به کارهای کوتاهتر اولویت می دهد و کارهای طولانی عقب تر می افتند.) در ضمن الگوریتم SRT از کوانتوم استفاده نمیکنه.
در این الگوریتم, فرآیند A در زمان ۰ وارد سیستم میشه و تا زمان ۲ به جلو پیش میره (چرا تا زمان ۲ به جلو پیش میره؟ به خاطر اینکه در زمان ۲ قراره که فرآیند B وارد سیستم بشه و زمان خدمتش مورد مقایسه قرار بگیره.) و بدین ترتیب از زمان خدمت فرآیند A دو واحد کم می شود و بنابراین زمان خدمت فرآیند A از ۱۲ میلی ثانیه به ۱۰ میلی ثانیه کاهش پیدا میکنه چون که تا زمان ۲ که فرآیند A اجرا شده, پس ۲ میلی ثانیه از زمان خدمتش رو استفاده کرده . حالا چرا به ۱۰ میلی ثانیه کاهش پیدا کرد و مثل الگوریتم fcfs به طور کامل اجرا نشد و تموم نشد؟ به خاطر اینکه اولا این الگوریتم غیرانحصاری است و ثانیا چون این الگوریتم به فرآیندهای کوتاهتر اولویت می دهد پس فرآیند B که زمان خدمتش ۵ میلی ثانیه است که از ۱۰ میلی ثانیه فرآیند A کوتاهتر است پس در زمان ۲ به فرآیند B سوییچ می کنیم و فرآیند B هم تا زمان ۵ به جلو پیش میره (چرا تا زمان ۵ به جلو پیش میره؟ به خاطر اینکه در زمان ۵ قراره که فرآیند C وارد سیستم بشه و زمان خدمتش مورد مقایسه قرار بگیره.) و بنابراین زمان خدمت فرآیند B سه تا کم میشه و به ۲ میلی ثانیه کاهش پیدا میکنه و از طرف دیگه چون قراره که در زمان ۵ فرآیند C وارد سیستم بشه بنابراین زمان باقیمانده فرآیند B که ۲ میلی ثانیه هست و زمان خدمت فرآیند C که ۴ میلی ثانیه است با هم مقایسه میشن و چون زمان خدمت باقیمانده فرآیند B کوتاهتر است یعنی ۴>2 بنابراین فرآیند B اون ۲ میلی ثانیه باقیمانده رو هم به جلو حرکت میکنه و زمان خدمتش رو به طور کامل استفاده میکنه و کارش با سیستم تموم میشه. الان فرآیند B در زمان ۷ دیگه تموم میشه. از طرف دیگه هم هنوز دو تا فرآیند A و C که قبلا وارد سیستم شده بودند هنوز کارشون تموم نشده و زمان خدمتشون هنوز مونده و چون زمان خدمت فرآیند C کوتاهتر از فرآیند A است یعنی ۱۰>4 بنابراین فرآیند C در زمان ۷ وارد سیستم میشه و یک واحد از زمان خدمتش رو استفاده میکنه و زمان خدمتش به ۳ میلی ثانیه کاهش پیدا میکنه و همچنین از زمان ۷ تا زمان ۸ به جلو پیش میره (چرا تا زمان ۸ به جلو پیش میره؟ به خاطر اینکه در زمان ۸ قراره که فرآیند D وارد سیستم بشه و زمان خدمتش مورد مقایسه قرار بگیره.) در این موقع زمان باقیمانده فرآیند C که ۳ میلی ثانیه هست و زمان خدمت فرآیند D که ۱۵ میلی ثانیه است با هم مقایسه میشن و چون زمان خدمت باقیمانده فرآیند C کوتاهتر است یعنی ۱۵>3 بنابراین فرآیند C اون ۳ میلی ثانیه باقیمانده رو هم به جلو حرکت میکنه و زمان خدمتش رو به طور کامل استفاده میکنه و کارش با سیستم تموم میشه. الان فرآیند C در زمان ۱۱ دیگه تموم میشه. از طرف دیگه هنوز دو تا فرآیند A و D که قبلا وارد سیستم شده بودند هنوز کارشون با سیستم تموم نشده و زمان خدمتشون هنوز مونده و چون زمان خدمت فرآیند A کوتاهتر از فرآیند D است یعنی ۱۵>10 بنابراین فرآیند A در زمان ۱۱ وارد سیستم میشه و همه ۱۰ میلی ثانیه باقیمانده خودش رو یکجا استفاده میکنه و تا زمان ۲۱ به جلو حرکت میکنه و در زمان ۲۱ کارش با سیستم تموم میشه. و در نهایت فرآیند D که زمان خدمتش از مابقیه فرآیندها خیلی طولانی تر بود در زمان ۲۱ وارد سیستم میشه و ۱۵ واحد به جلو حرکت میکنه یعنی تا زمان ۳۶ به جلو حرکت میکنه و بنابراین در زمان ۳۶ کارش با سیستم تموم میشه.
بدین ترتیب توضیحات الگوریتمSRT هم به اتمام رسید و همه فرآیندها نیز از تمام زمان خدمتشون استفاده کردند.
در نهایت, الگوریتم RR رو توضیح میدم.(الگوریتم RR , یک الگوریتم زمانبندی غیرانحصاری هست و به صورت اشتراک زمانی عمل میکنه یعنی هر کدام از فرآیندها در یک بازه خاص به طور مساوی از CPU استفاده می کنند و به این بازه خاص اصطلاحا کوانتوم میگن.)
در این الگوریتم, فرآیند A در زمان ۰ وارد سیستم میشه و تا زمان ۳ به جلو پیش میره (چرا تا زمان ۳ به جلو پیش میره؟ به خاطر اینکه کوانتوم زمانی گفته شده در صورت سوال, ۳ میلی ثانیه ذکر شده.) و بدین ترتیب از زمان خدمت فرآیند A سه واحد کم می شود و بدین ترتیب زمان خدمت فرآیند A از ۱۲ میلی ثانیه به ۹ میلی ثانیه کاهش پیدا میکنه چون که تا زمان ۳ فرآیند A اجرا شده, پس ۳ میلی ثانیه از زمان خدمتش رو استفاده کرد . حالا نوبت به فرآیند B میرسه چون که این فرآیند در زمان ۲ وارد سیستم شده بود یعنی در واقع در زمان ۲ می خواست وارد سیستم بشه ولی چون که سیستم مورد استفاده فرآیند دیگه ای بود نتونست وارد بشه و بنابراین منتظر فرآیند A بود که کار فرآیند A تموم بشه تا بتونه وارد سیستم بشه و حالا که کار فرآیند A با سیستم تموم شده, میتونه از سیستم استفاده کنه بدین ترتیب فرآیند B در زمان ۳ وارد سیستم میشه و تا زمان ۶ به جلو حرکت میکنه و از زمان خدمت فرآیند B هم سه تا کم میشه و به ۲ میلی ثانیه کاهش پیدا میکنه و به صورت موقت حق فرآیند B هم به اتمام رسید و از طرف دیگه چون قرار بود که در زمان ۵ فرآیند C وارد سیستم بشه بنابراین این فرآیند در زمان ۶ وارد سیستم میشه و تا زمان ۹ به جلو پیش میره و از زمان خدمت فرآیند C هم سه تا کم میشه و به ۱ میلی ثانیه کاهش پیدا میکنه و به صورت موقت حق فرآیند C هم به اتمام رسید و از طرف دیگه چون قرار بود که در زمان ۸ فرآیند D وارد سیستم بشه بنابراین این فرآیند در زمان ۹ وارد سیستم میشه و تا زمان ۱۲ به جلو پیش میره و از زمان خدمت فرآیند D هم سه تا کم میشه و به ۱۲ میلی ثانیه کاهش پیدا میکنه و به صورت موقت حق فرآیند D هم به اتمام رسید. چون همه فرآیندها از سیستم استفاده کردن دوباره به اولین فرآیند بر میگردیم یعنی به فرآیند A و این فرآیند هم دوباره ۳ تا به جلو حرکت میکنه و به زمان ۱۵ میرسه و زمان خدمت باقیماندش میشه ۶ میلی ثانیه. نوبت به فرآیند B میرسه چون که زمان خدمت باقیمانده این فرآیند ۲ میلی ثانیه بود و این ۲ میلی ثانیه از زمان کوانتوم کمتر هست و این فرآیند دیگه میتونه از همه زمان خدمت باقیمانده خودش استفاده کنه و بنابراین در زمان ۱۷ کار فرآیند B با سیستم تموم میشه. نوبت به فرآیند بعدی یعنی C میرسه چون که زمان خدمت باقیمانده این فرآیند ۱ میلی ثانیه بود و این ۱ میلی ثانیه از زمان کوانتوم کمتر هست و این فرآیند هم میتونه از همه زمان خدمت باقیمانده خودش استفاده کنه و بنابراین در زمان ۱۸ کار فرآیند C با سیستم تموم میشه. نوبت به فرآیند D میرسه این فرآیند هم دوباره ۳ تا به جلو حرکت میکنه و به زمان ۲۱ میرسه و زمان خدمت باقیماندش میشه ۹ میلی ثانیه. چون همه فرآیندها از سیستم استفاده کردن دوباره به اولین فرآیند بر میگردیم یعنی به فرآیند A و این فرآیند هم دوباره ۳ تا به جلو حرکت میکنه و به زمان ۲۴ میرسه و زمان خدمت باقیماندش میشه ۳ میلی ثانیه. و در اینجا چون دو تا فرآیند B و C قبلا کارشون با سیستم تموم شده بود, دیگه با این فرآیندها کاری نداریم و مستقیم میریم سراغ فرآیند D این فرآیند هم دوباره ۳ تا به جلو حرکت میکنه و به زمان ۲۷ می رسیم و زمان خدمت باقیماندش میشه ۶ میلی ثانیه.
دوباره به فرآیند A برمی گردیم و این فرآیند هم ۳ واحد به جلو حرکت میکنه و بنابراین در زمان ۳۰ کار فرآیند A با سیستم تموم میشه. نوبت به فرآیند D میرسه این فرآیند هم دوباره ۳ تا به جلو حرکت میکنه و به زمان ۳۳ میرسه و زمان خدمت باقیماندش میشه ۳ میلی ثانیه. چون که دیگه فرآیندی به جز فرآیند D باقی نمونده, دوباره ۳ تا به جلو حرکت میکنه و بنابراین این فرآیند نیز از همه زمان خدمت خودش مثل بقیه فرآیندها استفاده کرد و بنابراین در زمان ۳۶ کار فرآیند D با سیستم تموم میشه.
بدین ترتیب توضیحات الگوریتمRR هم به اتمام رسید و همه فرآیندها نیز از تمام زمان خدمتشون استفاده کردند.
سعی کردم که مطالب رو به صورت ساده و روان توضیح بدم. امیدوارم که مطالب به دردتون بخوره. اگه هم که خوب نبود ببخشید.
باز هم اگه سوالی باشه در خدمتتون هستم.
خیلی ممنون بابت توضیحات خوب و عالی تون. واقعا ممنونم. اجرتون با خدا..
فقط اگه امکانش هست تو محاسبه میانگین زمان انتظار هم کمکم کنید..
ببینیn اینا درسته؟؟
fcfs: 0+12+17+21/4=12.5
srt: (11-2)+ (2-2)+ (7-5)+(21-8)/4=6.25
برای rr را اگر امکانش هست برام توضیح بدین..
یه دنیا ممنون
با سلام
خواهش می کنم . خیلی ممنون از لطفتون. فقط ازتون التماس دعا دارم و دعا یادتون نره.
در ابتدا متوسط زمان انتظار الگوریتم fcfs رو توضیح میدم.
فرآیند A که در زمان ۰ وارد سیستم میشه و به مدت ۱۲ میلی ثانیه اجرا میشه و تموم میشه یعنی هیچ انتظاری رو نکشیده پس زمان انتظار فرآیند A میشه عدد صفر. فرآیند B که در صورت سوال زمان ورودش ۲ است ولی در زمان ۱۲ وارد سیستم میشه پس ۱۲ منهای ۲ میشه ۱۰ بنابراین زمان انتظار فرآیند B میشه عدد ۱۰/ فرآیند C که در صورت سوال زمان ورودش ۵ است ولی در زمان ۱۷ وارد سیستم میشه پس ۱۷ منهای ۵ میشه ۱۲ بنابراین زمان انتظار فرآیند C میشه عدد ۱۲/ فرآیند D که در صورت سوال زمان ورودش ۸ است ولی در زمان ۲۱ وارد سیستم میشه پس ۲۱ منهای ۸ میشه ۱۳ بنابراین زمان انتظار فرآیند D میشه عدد ۱۳/
بنابراین متوسط زمان انتظار الگوریتم fcfs به صورت زیر محاسبه میشه:
۸/۷۵ = ۳۵/۴ = ۴ / ۱۳ + ۱۲ + ۱۰ + ۰
راه حل متوسط زمان انتظار الگوریتم SRT رو درست حل کردی ولی جوابش میشه ۶ اعداد رو با هم تفریق و بعدش جمع بزنی میشه ۲۴
۲۴ هم تقسیم بر ۴ میشه ۶ یه اشتباه کوچولو انجام دادی.
در نهایت, متوسط زمان انتظار الگوریتم RR رو توضیح میدم. به علت اینکه یه مقدار توضیح دادن الگوریتم RR پیچیده است به همین خاطر برای توضیح دادن این الگوریتم از شکلی که در پیوست ضمیمه کردم استفاده کنید. فقط در رابطه با شکل عرض کنم که خط های آبی رنگ وسط شکل, زمان های ورود و خروج فرآیندها به سیستم رو نشون میده مثلا" بار اول که فرآیند A میخواد وارد سیستم بشه از زمان صفر شروع میشه تا زمان ۳ که دقیقا اولین خط آبی رنگ است. اعداد قرمز رنگ وسط خط های آبی هم زمان انتظار فرآیندها رو نشون میده. مجموع این اعداد, زمان های انتظار هر کدام از فرآیندها رو نشون میده برای مثال زمان انتظار فرآیند A که برابر ۱۸ میشه از جمع اعداد جلوی فرآیند A بدست می آید و به همین ترتیب زمان انتظار بقیه فرآیندها هم همین جوری به دست می آید. برای متوجه شدن شکل زیر به توضیحات پست قبلی که در مورد الگوریتم RR دادم مراجعه کنید و کلمه به کلمه توضیحات الگوریتم رو دنبال کنید و روی شکل به خودتون توضیح بدین تا کامل متوجه بشین.
[attachment=19080]
بنابراین متوسط زمان انتظار الگوریتم RR به صورت زیر محاسبه میشه:
۱۲/۵ =۴ /۵۰ = ۴ / ۱۳ + ۹ + ۱۰ + ۱۸
بازم ممنون. خیلی خوب توضیح میدین. براتون دعا کردم. مرسی.
فقط برای d زمان های انتظار این نمیشه: ۱۰
۳
۳
اینجوری: ۱۸-۸=۱۰
۲۱-۲۴=۳
۳۰-۲۷=۳
یا من اشتباه کردم.
با سلام
خواهش می کنم . خیلی ممنون از لطفتون. التماس دعا.
شما بار اول که فرآیند D وارد سیستم میشه و اجرا میشه رو در نظر نگرفتین. اونم باید در نظر بگیرین.
خوب به عکس نگاه کنید فرآیند D بار اول از زمان ۹ تا ۱۲ اجرا میشه و از اونجایی که زمان ورودش طبق صورت سوال ۸ است پس یه دونه با تاخیر وارد سیستم میشه یعنی از ۹ وارد شده و ۱ میلی ثانیه تاخیر داشته و دیر اجرا شده یعنی در واقع ۱ میلی ثانیه منتظر شده تا نوبت اجراش برسه. بار دوم از زمان ۱۸ تا ۲۱ اجرا میشه ولی از زمان ۱۲ تا ۱۸, ۶ میلی ثانیه منتظر بقیه فرآیندها شده تا اونها CPU رو رها کنند تا خودش بتونه CPU رو به دست بگیره پس اینجا هم ۶ میلی ثانیه منتظر شده . بار سوم از زمان ۲۴ تا ۲۷ اجرا میشه ولی از زمان ۲۱ تا ۲۴ منتظر فرآیند A شده پس اینجا هم ۳ میلی ثانیه منتظر فرآیند A شده.
بار چهارم از زمان ۳۰ تا ۳۳ اجرا میشه ولی از زمان ۲۷ تا ۳۰ منتظر فرآیند A شده پس اینجا هم ۳ میلی ثانیه منتظر فرآیند A شده.
بار پنجم هم از زمان ۳۳ تا ۳۶ اجرا میشه ولی اینجا دیگه منتظرهیچ فرآیندی نیست و پشت سرهم اجرا میشه چون که بقیه فرآیندها قبلا" اجرا شدن و تموم شدن و فقط همین خودش مونده.
پس اگه بخواهیم زمان های انتظار فرآیند D رو جمع بزنیم این جوری میشه:
۱۳ = ۳ + ۳ + ۶ + ۱
بنابراین زمان انتظار فرآیند D برابر است با ۱۳ میلی ثانیه.