شرح خورزميات الجدوله من كتاب 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

طرق جدولة المعالج CPU scheduling ( Short Term Scheduling )
شرح خوارزميات الجدولة
خوارزميات الجدولة في نظم التشغيل pdf
جدولة العمليات في نظم التشغيل
شرح priority scheduling
cpu scheduling شرح
cpu scheduling algorithms شرح
cpu scheduling pdf
شرح خوارزمية sjf