اگر ۵ فرآیند به فواصل زمانی ۱ با شروع از لحظه ۰ به سیستمی وارد شده و هر کدام ۱/۵ واحد زمانی نیاز به پردازش داشته باشند. زمان کامل (Turnaround Time)برای الگوریتم های زمان بندی چرخشی (RR) با کوانتوم زمانی q=1 و NP-LCFS به ترتیب برابر است با: (توجه: ۱- از بین فرآیند ورودی از لحظه T به فرایندی که در لحظه T پردازنده را رها کرده، اولویت با فرایند ورودی است. ۲- منظور از زمان کامل، فاصله بین لحظه ورود و پایان کار یک نخ است.)
(کاشناسی ارشد IT- سراسری ۸۸)
جواب: RR: 3.3 و ۲/۵ :NP-LCFS
دوستان یک توضیح در مورد حل این مسئله بدهند.
از کتاب حقیقت نتونستم این مسئله رو دقیق بفهمم. (رسم نمودار گانت رو کامل نفهمیدم)
روش LCFS چون تو صورت سوال گفته NP تو این مثال مانند FIFO یا همون FCFS حل میشه.
نمودار گانت RR رو هم براتون میذارم.
رنگ بنفش فرآیندهای موجود در صف رو نشون میده
در لحظه ۰ که فقط P0 رو داریم که تا رمان ۱ اجرا میشه.
در لحظه ۱ ، P1 ورد میشه و طبق صورت سوال ولویت با این فرآینده. پس P1 تو صف جلوتر از P0 هستش.
در لحظه ۲ ، p0 سر صف هست و الان P1 باید پردازنده رو رها کنه و بعد از p0 قرار بگیره ولی فرآیند P2 وارد میشه که اولویت بیشتری داره پس P2 بعد از P0 قرار میگیره و P1 بعد از P2
از ۲ تا ۲/۵ P0 اجا میشه. بعد نوبت P2 هست که چون کوانتوم ۱ ازه زمانیه تا زمان ۳/۵ اجرا میشه.
در لحظه ۳/۵ پردازنده از P2 گرفته میشه و P2 باید ره تو صف. P1 اول صف بود. بعد فرآیند جدید P3 در زمان ۳ وارد صف شده. فرآیند P2 هم میره آخر صف.
از ۳/۵ تا ۴ P1 اجرا میشه
در لحظه ۴ فرآیند P4 وارد میشه ولی چون اولویتش فقط از فرآیندی که تازه پردازنده رو رها کرده (یعنی P1 ) بیشتره پس اولویت کمتری نسبت به P3,P2 که تو صف بودن داره پس میره آخر صف.
بقیه اش هم که معلومه!
نقل قول: روش LCFS چون تو صورت سوال گفته NP تو این مثال مانند FIFO یا همون FCFS حل میشه.پس چرا تو کتاب پارسه p2 رو برده آخر. مگه نمیگید مثل FIFO باید باشه؟
[attachment=8872]
نقل قول: p0 سر صف هست و الان P1 باید پردازنده رو رها کنه و بعد از p0 قرار بگیره ولی فرآیند P2 وارد میشه که اولویت بیشتری داره پس P2 بعد از P0 قرار میگیره و P1 بعد از P2چرا؟
مگه تو سوال نگفته " از بین فرآیند ورودی در لحظه t و فرآیند در لحظه t، اولویت با فرآیند ورودی است". پس چرا در اینجا فرآیند ورودی (یعنی P2) رو رها کرد و فرآیند قبلی را انتخاب کرد؟
در مورد LCFS اشتباه کردم . درسته در لحظه ۳ که p3 وارد میشه P2 سر استک هست ولی p3 اولویت بیشتری داره. پس p3 اجرا میشه تا ۴/۵
بعد در ۴ p4 وارد میشه و باز p2 سر استک هست ولی اولویت p4 بیشتره پس p2 میره آخر.
در مورد RR هم گقته فرآیند ورودی فقط نسبت به فرآیندی اولویت داره که تازه پردازنده رو رها کرده نه همه فرآیندهای داخل صف.
پس نسبت به p1 اولویت داره نه p0
(۲۴ دى ۱۳۹۱ ۱۲:۴۹ ب.ظ)egm1176 نوشته شده توسط: فرآیند ورودی فقط نسبت به فرآیندی اولویت داره که تازه پردازنده رو رها کرده نه همه فرآیندهای داخل صف.
خوب همین حرف شما.
مگه نمی فرمائید فرایند ورودی نسبت به فرایندی که تازه پردازنده رو رها کرده اولویت داره؟
پس چرا در زمان ۲ به جای p2 پردازنده به p0 اختصاص یافته است؟ مگه فرایند p2 تازه وارد نشده، پس باید اولویت داشته باشد.
این برداشت اشتباه است؟
دوستان کسه دیگه ای نظری نداره؟
ببینید قدم به قدم مسئله رو جلو می بریم.
** هر فرآیندی که پردازنده رو رها کرد به آخر صف میرود مگر آنکه فرآیند جدیدی وارد سیستم شده باشد.**
در لحظه ۰ که فقط P0 موجود پس ۱ کوانتوم اجرا میشه. خب حالا شرط ** برقراره. چون P1 وارد شده.
پس اول P1 میره تو صف بعد P0
تا اینجا مشکلی نیست؟
تا اینجا مشکلی نیست و گرفتم.
خب در لحظه ۱ صف رو ببینید : اول P1 ، بعد P0
پس P1 باید اجرا بشه. که این اتفاق در زمان ۱ تا ۲ میافته.
P0 همچنان تو صفه. چون ما که هیچ فرآیندی که تو صف بوده رو بیرون نمی کشیم. بلکه برای اون فرآیندهایی که میخوان وارد بشن اولویت تعیین میکنیم که اگه در یک لحظه چند تا با هم میخواستند وارد صف بشن ما دچار ابهام نشیم.
پس در لحظه ۲، P0 تو صفه . P1 فرآیندیه که تازه پردازنده رو رها کرده. و دوباره میخواد وارد صف بشه. در همین لحظه P2 هم وارد سیستم میشه و میخواد وارد صف بشه.
با توجه به شرط ** P2 اولویت بیشتری داره. پس اول P2 وارد میشه و بعد P1
تا اینجا مشکلی نیست؟
گرفتم.
خوب.
خب ، پس در لحظه ۲ ترتیب صف اینه : اول P0 بعد P2 و بعد P1
پس باید p0 اجرا بشه که فقط ۰/۵ ثانیه از زمانش مونده که از زمان ۲ تا ۲/۵ اجرا میشه.
در زمان ۲/۵ هنوز فرآیند جدیدی وارد نشده پس صف تغییری نکرده. پس نوبت اجرای P2 میشه. که به اندازه یک کوانتوم اجرا میشه. از ۲/۵ تا ۳/۵
درسته؟
مشکل دقیقا تا اینجاست.
چطور شد که وقتی P0 کارش در ۱ ثانیه کوانتوم زمانی تمام شد در صف بعد از فرآیند P1 که فرآیند تازه وارد بود قرار گرفت. (فرآیند تازه وارد اومد بالای صف)
ولی وقتی P1 کارش در ۱ ثانیه کوانتوم زمانی تمام شد و طبق صف نوبت P0 خواهد بود ولی در این زمان فرایند جدید یعنی P2 وارد شد.
مگه نباید طبق ** P2 اجرا بشه؟
** هر فرآیندی که پردازنده رو رها کرد به آخر صف میرود مگر آنکه فرآیند جدیدی وارد سیستم شده باشد.**
در مورد RR هم گقته فرآیند ورودی فقط نسبت به فرآیندی اولویت داره که تازه پردازنده رو رها کرده نه همه فرآیندهای داخل صف.
پس نسبت به p1 اولویت داره نه p0
نکته تو همینجا بود ،خیلی نکته ی ساده ایه ولی من روز علافش بودم
ممنون