📘 ❞ طرق جدولة المعالج CPU scheduling ( Short Term Scheduling ) ❝ كتاب

عن كتاب طرق جدولة المعالج CPU scheduling ( Short Term Scheduling ):
شرح خورزميات الجدوله من كتاب operating system concepts (انظمه تشغيل )



شرح خورزميات الجدوله ch5


طرق جدولة المعالج
CPU scheduling
( Short Term Scheduling )


1- First Come First Server
2- Shortest Job First
A- non preemptive
B- preemptive
3- Priority
A- Non preemptive
B- preemptive
4- Round Robin

First Come First Server (FCFS)
الطريقة تعتمد على زمن وصول العمليات إلى ready Queue .
العملية process التي تصل أولا إلى ready Queue هي التي يختارها المعالج processor (CPU) للتنفيذ.
Average waiting time is generally not minimal
FCFS is non-preemptive
Not good for time sharing systems where each user needs to get a share of the CPU at regular intervals
الخوارزمية : non preemptive
مثال :-
Process Ready queue arrive time Cpu burst time
P1 0 3 ms
P2 1 4 ms
P3 4 6 ms
P4 2 4 ms
P5 6 1 ms

أوجد الآتي:-
1. ارسم Gantt chart
2. احسب turnaround time لكل عملية وأحسب average turnaround time
3. احسب waiting time لكل عملية وأحسب average waiting time
الحل :-
1- رسم Gantt chart
Gantt chart هو مخطط يوضع ترتيب تنفيذ العمليات في المعالج CPU والفترة الزمنية لتنفيذ هذه العمليات.

2- حساب turnaround time
قاعدة (1)
حساب Turnaround time لعملية معينة
terminate time هو زمن انتهاء العملية
acceptable time (starting time) هو زمن قبول العملية (الزمن لحظة إنشاء العملية ).

P1 : 3 - 0 = 3 ms
P2 : 7 - 1 = 6 ms
P3 : 17 – 4 = 13 ms
P4 : 11 – 2 = 9 ms
P5 : 18 – 6 = 12 ms
____________________________________
Total = 43 ms
Average turnaround time = 43 / 5 = 8.6 ms
قاعدة (2)
حساب Turnaround time لعملية معينة

Job queue waiting time : زمن الانتظار في job queue
ready queue waiting time : زمن الانتظار في ready queue ويسمى waiting time
CPU burst time : زمن تنفيذ العملية في المعالج
I/O burst time : زمن تنفيذ العملية في وحدات الإدخال والإخراج
waiting (I/O wait + event wait) : زمن الانتظار في صفوف انتظار عمليات الإدخال والإخراج وأحداث الانتظار الأخرى.

3- حساب waiting time
قاعدة (3)
حساب waiting time لعملية معينة
n تمثل عدد مرات دخول العملية للمعالج
Start executing in CPU(i) هو زمن دخول العملية للمعالج CPU في المرة رقم i
وهو نفس الوقت الذي خرجت فيه العلمية من ready queue
Ready queue arrive time (i) هو ومن وصول العملية إلى ready queue
في حالة طرق الجدولة non preemptive :-
(أ‌) إذا لا توجد عمليات I/O ولا توجد عمليات witting للعملية ( process )
ستنفذ العملية كاملة من أول مرور على المعالج (N=1).
(ب‌) في حالة وجود عمليات I/O أو عمليات witting للعملية ( process )
ستنفذ العملية على عدة مراحل في المعالج (N>1).
P1 : 0 - 0 = 0 ms
P2 : 3 - 1 = 2 ms
P3 : 11 – 4 = 7 ms
P4 : 7 – 2 = 5 ms
P5 : 17 – 6 = 11 ms
_____________________________________
Total = 25 ms
Average waiting time = 25 / 5 = 5 ms



استخدام نفس القاعدة (2)
P1 : 3 - 3 = 0 ms
P2 : 6 - 4 = 2 ms
P3 : 13 – 6 = 7 ms
P4 : 9 – 4 = 5 ms
P5 : 12 – 1 = 11 ms
_____________________________________
Total = 25 ms
Average waiting time = 25 / 5 = 5 ms
مثال (تعديل طفيف على المثال السابق):-
Process Job Queue arrive time Ready queue arrive time CPU burst time
P1 0 0 3 ms
P2 0 1 4 ms
P3 2 4 6 ms
P4 1 2 4 ms
P5 5 6 1 ms
أوجد الآتي:-
1. ارسم Gantt chart
2. احسب turnaround time لكل عملية وأحسب average turnaround time
3. احسب waiting time لكل عملية وأحسب average waiting time
الحل :-
1- Gantt chart



2- turnaround time
Turnaround time = terminate time – acceptable time (starting time)
P1 : 3 - 0 = 3 ms
P2 : 7 - 0 = 7 ms
P3 : 17 – 2 = 15 ms
P4 : 11 – 1 = 10 ms
P5 : 18 – 5 = 13 ms
____________________________________
Total = 48 ms
Average turnaround time = 48 / 5 = 9.6 ms
3- waiting time

waiting time = Start executing in CPU - Ready queue arrive time
P1 : 0 - 0 = 0 ms
P2 : 3 - 1 = 2 ms
P3 : 11 – 4 = 7 ms
P4 : 7 – 2 = 5 ms
P5 : 17 – 6 = 11 ms
_____________________________________
Total = 25 ms
Average waiting time = 25 / 5 = 5 ms
بطريقة أخرى
Waiting time = Turnaround time - Job queue waiting time - CPU burst time - I/O burst time - waiting (I/O wait + event wait)
P1 : 3 – 0 – 3 = 0 ms
P2 : 6 – 1 – 4 = 2 ms
P3 : 13 – 2 – 6 = 7 ms
P4 : 9 – 1 – 4 = 5 ms
P5 : 12 – 1 – 1 = 11 ms
_____________________________________
Total = 25 ms
Average waiting time = 25 / 5 = 5 ms