OS-operating systems- ch05 (CPU Scheduling) ...

operating systems , ch-05, (CPU Scheduling), 3rd level, College of Computers, Seiyun University. انظمة التشغيل لطلاب المستوى الثالث بكلية الحاسبات بجامعة سيئون المحاضرة 05

1. Chapter 5: CPU Scheduling

2. •CPUschedulingisthecentralinmulti-programming
system.
2
•Maximum CPU utilizationobtainedwith
multiprogramming (prevent CPU from being idle).
•Processes residing in the main memory is selected by
the Scheduler that is:
Concerned with deciding a policy about which process is
to be selected.
Process selection based on a scheduling algorithm.
BasicConcepts

3. BasicConcepts
3

4. BasicConcepts
4

5. •Processexecutionconsistsofacycleof
CPUexecutionandI/Owait.
•Processesalternatebetweenthesetwo
states.Processexecutionbeginswitha
CPUburst.ThatisfollowedbyanI/O
burst,whichisfollowedbyanother
CPUburst,thenanotherI/Oburst,and
soon.
•CPUburstsvarygreatlyfromprocessto
processandfromcomputertocomputer.
BasicConcepts
5

6. Schedulers
•Long-termschedulerchoosessomeofthemtogoto
memory(readyqueue).
•Then,short-termscheduler(orCPUscheduler)chooses
fromreadyqueueajobtorunonCPU.
•Medium-termschedulermaymove(swap)some
partially-executedjobsfrommemorytodisk(toenhance
performance).
6
BasicConcepts

7. CPU Scheduler
•WhenevertheCPUbecomesidle,theoperatingsystem
mustselectoneoftheprocessesinthereadyqueuetobe
executed.Theselectionprocessiscarriedoutbytheshort-
termscheduler,orCPUscheduler.
7
BasicConcepts

8. CPUschedulingdecisionsmaytakeplace whena process:
1.Switchesfromrunningtowaiting state
2.Switchesfromrunningto readystate
3.Switchesfromwaitingtoready
4.Terminates
8
BasicConcepts

9. Scheduling can be
•Non-preemptive
Oncea processisallocatedthe
CPU,itdoesnot leave until terminate.
•Preemptive
OScanforce(preempt)a process
fromCPUat anytime.
Say, to allocate CPU to another higher-priority process.
9
BasicConcepts

10. Non-preemptive and Preemptive
•Preemptiveisharder:Needtomaintainconsistencyof
datasharedbetweenprocesses,andmoreimportantly,
kerneldatastructures(e.g.,I/Oqueues).
10
BasicConcepts

11. Dispatcher
•DispatchermodulegivescontroloftheCPUtothe
processselectedbytheshort-termscheduler;thisinvolves:
Switchingcontext.
Switchingtousermode.
Jumpingtotheproperlocationintheuserprogramtorestart
thatprogram.
•Dispatchlatency–timeittakesforthedispatchertostop
oneprocessandstartanotherrunning.
11
BasicConcepts

12. •CPUutilization–keeptheCPUasbusyaspossible.
•Throughput–numberofprocessesthatcompletetheir
executionpertimeunit.
•Turnaroundtime–amountoftimetoexecuteaparticular
process.(timefromsubmissiontotermination)
•Waitingtime–amountoftimeaprocesshasbeenwaitingin
thereadyqueue.
•Responsetime–amountoftimeittakesfromwhenarequest
wassubmitteduntilthefirstresponseisproduced,notoutput.
12
SchedulingCriteria

13. SchedulingAlgorithmOptimizationCriteria
•MaxCPUutilization.
•Maxthroughput.
•Minturnaroundtime.
•Minwaitingtime.
•Minresponsetime.
13
SchedulingCriteria

14. •TherearemanydifferentCPU-schedulingalgorithms:
1.First Come,FirstServed(FCFS).
2.ShortestJobFirst(SJF).
PreemptiveSJF.
Non-PreemptiveSJF.
3.Priority.
4.RoundRobin.
5.Multilevelqueues.
14
SchedulingAlgorithms

15. 1.First-Come,First-Served(FCFS)Scheduling
SchedulingAlgorithms
Process BurstTime
P
1 24
P
2 3
P
3 3
Suppose that the processes arrive in the order: P
1 , P
2 , P
3
The Gantt Chart for the schedule is:
Note:A process may have many CPU bursts, but in the following
examples we show only one for simplicity.

16. First-Come, First-Served (FCFS) Scheduling
Process Burst Time
P
1 24
P
2 3
P
3 3
Suppose that the processes arrive in the order: P
1, P
2, P
3
The Gantt Chart for the schedule is:
P
1 P
2 P
3
24 27 300
Waiting Time
??????�??????�??????�
0 24 27
Averagewaitingtime:
(0+24+27)/3=17
TurnaroundTime
??????�??????�??????�
24 27 30
Averageturnaroundtime:
(24+27+30)/3=27
Response Time
??????�??????�??????�
0 24 27
Averageresponsetime:
(0+24+27)/3=17

17. FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order
P
2, P
3, P
1
The Gantt chart for the schedule is:
P
1P
3P
2
63 300
Waiting Time
??????�??????�??????�
6 0 3
Averagewaitingtime:
(6+0+3)/3=3
Turnaround Time
??????�??????�??????�
30 3 6
Averageturnaroundtime:
(30+3+6)/3=13
Response Time
??????�??????�??????�
6 0 3
Averageresponsetime:
(6+0+3)/3=3
•Much better than previous case
•Convoy effectshort process behind long process

18. Shortest-Job-First (SJR) Scheduling
Associate with each process the length of its next CPU
burst. Use these lengths to schedule the process with the
shortest time
Two schemes:
nonpreemptive –once CPU given to the process it
cannot be preempted until completes its CPU burst
preemptive –if a new process arrives with CPU burst
length less than remaining time of current executing
process, preempt. This scheme is know as the
Shortest-Remaining-Time-First (SRTF)
SJF is optimal –gives minimum average waiting time for a
given set of processes

19. Process Arrival Time Burst Time
P
1 0.0 7
P
2 2.0 4
P
3 4.0 1
P
4 5.0 4
SJF (non-preemptive)
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Example of Non-Preemptive SJF
P
1 P
3 P
2
73 160
P
4
8 12

20. Example of Preemptive SJF
Process Arrival Time Burst Time
P
1 0.0 7
P
2 2.0 4
P
3 4.0 1
P
4 5.0 4
SJF (preemptive)
Average waiting time = (9 + 1 + 0 +2)/4 = 3
P
1 P
3P
2
42
110
P
4
5 7
P
2 P
1
16

21. Priority Scheduling
A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest
priority (smallest integer highest priority)
Preemptive
nonpreemptive
SJFis a priority scheduling where priority is the predicted
next CPU burst time
Problem Starvation –low priority processes may never execute
Solution Aging –as time progresses increase the priority of the
process

22. 3.PriorityScheduling
SchedulingAlgorithms
(2/25)
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart
22

23. 3.PriorityScheduling
SchedulingAlgorithms
(2/25)
Process Burst Time Priority
P
1 10 3
P
2 1 1 Highest priority
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart
23

24. 3.PriorityScheduling
SchedulingAlgorithms
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart
24

25. 3.PriorityScheduling
SchedulingAlgorithms
(3/25)
25
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart

26. 3.PriorityScheduling
SchedulingAlgorithms
(3/25)
26
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart

27. 3.PriorityScheduling
SchedulingAlgorithms
(3/25)
27
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart

28. 3.PriorityScheduling
SchedulingAlgorithms
28
Process Burst Time Priority
P
1 10 3
P
2 1 1
P
3 2 4
P
4 1 5
P
5 5 2
PriorityschedulingGanttChart
Waiting Time
??????�??????�??????�??????�??????�
6 0 1618 1
AverageWaitingtime=
[6+0+16+18+1]/5= 8.2msec
Turnaround Time
??????�??????�??????�??????�??????�
161 18196
AverageTurnaroundtime=
[16+1+18+19+6]/5= 12msec
Response Time
??????�??????�??????�??????�??????�
6 0 16 18 1
AverageResponsetime=
[6+0+16+18+1]/5=8.2msec

29. Round Robin (RR)
Each process gets a small unit of CPU time (time quantum),
usually 10-100 milliseconds. After this time has elapsed,
the process is preempted and added to the end of the ready
queue.
If there are nprocesses in the ready queue and the time
quantum is q, then each process gets 1/nof the CPU time in
chunks of at most qtime units at once. No process waits
more than (n-1)q time units.
Performance
qlarge FIFO
q small q must be large with respect to context switch,
otherwise overhead is too high

30. Example of RR with Time Quantum = 20
Process Burst Time
P
1 53
P
2 17
P
3 68
P
4 24
The Gantt chart is:
Typically, higher average turnaround than SJF, but better response
P
1P
2P
3P
4P
1P
3P
4P
1P
3P
3
02037577797117121134154162

31. Time Quantum and Context Switch Time

32. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 dnuoR .
:mutnauq fo gniludehcs )RR( niboR4 ms
32

33. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
33
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1
0 4 7 10 14 18 22 26 30
P
2
P
3
P
1
P
1
P
1
P
1
P
1

34. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
34
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1
0 4 7 10 14 18 22 26
30
P
2
P
3
P
1
P
1
P
1
P
1
P
1

35. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
35
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
0 4 7 10 14 18 22 26 30
P
1
P
2
P
3
P
1
P
1
P
1
P
1
P
1

36. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
36
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1
P
2
P
3
P
1
0 14 18 22 26 30
P
1
P
1
P
1
P
1
4 7 10

37. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
37
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1
P
2
P
3
P
1
P
1
0 18 22 26 30
P
1
P
1
P
1
144 7 10

38. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
38
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1
P
1
0 18 26 30144 7 10 22
P
1 P
2 P
3 P
1 P
1 P
1

39. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
39
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1 P
2 P
3 P
1 P
1 P
1 P
1 P
1
0 18 3026144 7 10 22

40. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
40
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 .
:mutnauq fo gniludehcs )RR( niboR dnuoR4 ms
P
1 P
2 P
3 P
1 P
1 P
1 P
1 P
1
0 18 3026144 7 10 22

41. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
41
Process BurstTime
P
1 24
P
2 3
P
3 3
All the processes arrive at the same time 0 niboR dnuoR .
:mutnauq fo gniludehcs )RR(4 ms
4 7 10
#ofcontextswitches=7
P
1 P
2 P
3 P
1 P
1 P
1 P
1 P
1
0 18 302614 22

42. 4. RoundRobin(RR)Scheduling
SchedulingAlgorithms
(11/25)
Process BurstTime
P
1 24
P
2 3
P
3 3
Alltheprocessesarriveatthesametime0.
RoundRobin(RR)schedulingofquantum:4ms
P
1 P
2 P
3 P
1 P
1 P
1 P
1 P
1
42
0 18 3026144 7 10 22
Waiting Time
??????�??????�??????�
0( +10 −4) 4 7
Averagewaitingtime:
(6+4+7)/3=5.667ms
Turnaround
Time
??????�??????�??????�
30 7 10
AverageTurnaroundtime:
(30 + 7 + 10)/3 = 15.667ms
Response Time
??????�??????�??????�
0 47
AverageResponsetime:
(0+4+7)/3=3.667 ms

43. CHAPTER 5 -PART 2

44. SchedulingAlgorithms
(16/25)
5. Multilevel Queue Scheduling
Scheduling must be done between the queues:
Fixed priority scheduling; (i.e., serve all from foreground
then from background).Possibility of starvation.
Time slice –each queue gets a certain amount of CPU time
which it can schedule amongst its processes; i.e., 80% to
foreground in RR.
20% to background in FCFS.

45. SchedulingAlgorithms
(17/25)
5. Multilevel QueueScheduling

46. SchedulingAlgorithms
(18/25)
5. Multilevel QueueScheduling
Threequeues:
Q
0–RRwithtimequantum8milliseconds
Q
1–RRtimequantum16milliseconds
Q
2–FCFS

47. SchedulingAlgorithms
(19/32)
5.MultilevelQueueScheduling
Scheduling
Anewjob enters queue�0which is servedFCFS
WhenitgainsCPU,jobreceives8milliseconds.
Ifitdoesnotfinishin8 milliseconds,jobismovedtoqueue �1.
At�1jobisagainservedFCFSandreceives16additionalmilliseconds
Ifitstilldoesnotcomplete,it ispreemptedandmovedtoqueue�2.

48. SchedulingAlgorithms
(20/32)
5. Multilevel Queue Scheduling
Now we add the concepts of varying arrival times and preemption to the
analysis
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60
P
3 2 20
P
4 3 40
Multilevel Queue Fixed priority
non-preemptive
Using multi-processors
or multi-core processor

49. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2P
3
P
4
Arrival TimeBurst Time
0 7
160
220
340
�0
�1
�2
�0
�1
�2

50. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
3
�1
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60
P 2 20
P
4 3 40
7ms
�0
�1
�2
�0
�1
�2
7ms

51. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
3
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60
P 2 20
P
4 3 40
7ms
7ms 8ms
�1 �2
�0
�1
�2
�0
�1
�2

52. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2P
Arrival TimeBurst Time
0 7
1
2
3
6052
20
40
�1 �2
�0
�1
�2
�0
�1
�2
3
P
4
15ms
7ms 8ms

53. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2P
Arrival TimeBurst Time
0 7
1
2
3
6052
20
40
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
3
P
4
15ms
7ms 8ms 8ms

54. SchedulingAlgorithms
(21/32)
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 605244
P
3 2 2012
P
4 3 40
�1 �2
�
2
�3
�0
�1
�2
5. Multilevel QueueScheduling
�0
�1
�2
23ms
7ms 8ms 8ms

55. SchedulingAlgorithms
(21/32)
�0
�1
�2
5. Multilevel QueueScheduling
�0
�1
�2
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 605244
P
3 2 2012
P
4 3 40
23ms
7ms 8ms 8ms 8ms
�1 �2 �3 �4
�2

56. SchedulingAlgorithms
(21/32)
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60524436
P
3 2 2012
P
4 3 4032
�1 �2
�2
�3
�0
�1
�2
5. Multilevel Queue Scheduling
�0
�1
�2
31ms
�4
7ms 8ms 8ms 8ms
16ms

57. SchedulingAlgorithms
(21/32)
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60524436
P
3 2 2012
P
4 3 4032
�1 �2
�2
�3
�0
�1
�2
5. Multilevel Queue Scheduling
�0
�1
�2
31ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms12ms
36ms

58. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
6052443624
2012
4032
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
43ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms 12ms
36ms

59. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
6052443624
2012
4032
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
43ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms
�4
12ms 16ms
36ms

60. SchedulingAlgorithms
(21/32)
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60524436248
P
3 2 2012
P
4 3 403216
�1 �2
�2
�3
�0
�1
�2
5. Multilevel Queue Scheduling
�0
�1
�2
59ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms
�4
12ms 16ms
36ms

61. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
60524436248
2012
403216
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
67ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms
�4
12ms 16ms
36ms

62. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
60524436248
2012
403216
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
67ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms
�4
12ms 16ms
36ms
�4
16ms

63. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
60524436248
2012
403216
�1 �2
�2
�3
�0
�1
�2
�0
�1
�2
83ms
�4
7ms 8ms 8ms
�2
�3
8ms
16ms
�4
12ms 16ms
36ms
�4
16ms

64. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(21/32)
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
60524436248
2012
403216
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms

65. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(22/32)
ProcessArrivalTime
P
1
P
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Waiting Time
??????�??????�??????�??????�

66. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(22/32)
ProcessArrivalTime
P
1
P
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Waiting Time
??????�??????�??????�??????�
0
= �

67. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(22/32)
ProcessArrivalTime
P
1
P
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Waiting Time
??????�??????�??????�??????�
07 − 1
= �= �

68. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(22/32)
ProcessArrivalTime
P
1
P
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Waiting Time
??????�??????�??????�??????�
07 − 115 + 8 − 2
= �= �= ��

69. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(22/32)
ProcessArrivalTime
P
1
P
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Waiting Time
??????�??????�??????�??????�
07 − 115 + 8 − 223 + 12 + 8 − 3
= �= �= ��= ��

70. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(23/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Turnaround Time
??????�??????�??????�??????�

71. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(23/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Turnaround Time
??????�??????�??????�??????�
7 − 0
= �

72. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(23/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Turnaround Time
??????�??????�??????�??????�
7 − 067 − 1
= �= ��

73. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(23/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Turnaround Time
??????�??????�??????�??????�
7 − 067 − 143 − 2
= �= ��= ��

74. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(23/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Turnaround Time
??????�??????�??????�??????�
7 − 067 − 143 − 283 − 3
= �= ��= ��= ��

75. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(24/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Response Time
??????�??????�??????�??????�

76. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(24/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Response Time
??????�??????�??????�??????�
0 − 0
= �

77. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(24/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Response Time
??????�??????�??????�??????�
0 − 07 − 1
= �= �

78. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(24/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Response Time
??????�??????�??????�??????�
0 − 07 − 115 − 2
= �= �= ��

79. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(24/32)
Process
P
1 P
ArrivalTime
2
P
3
P
4
0
1
2
3
�1 �2
�
2
�0
�1
�2
�0
�1
�2
83ms
�3 �4
7ms 8ms
�2
�3
16ms
�4
12ms 16ms
36ms
�4
16ms
59ms67ms43ms7ms15ms23ms31ms
8ms 8ms
Response Time
??????�??????�??????�??????�
0 − 07 − 115 − 223 − 3
= �= �= ��= ��

80. SchedulingAlgorithms
(25/32)
5. Multilevel Queue Scheduling
Now we add the concepts of varying arrival times and preemption to the
analysis
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 60
P
3 2 20
P
4 3 40
Multilevel Queue Fixed priority
non-preemptive
Using single-core
processor

81. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(26/32)
�0
�1
�2
�0
�1
�2
1
ProcessArrival TimeBurst Time
P 0 7
P
2 1 60
P
3 2 20
P
4 3 40

82. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
�1
�0
�1
�2
7ms
1
ProcessArrival TimeBurst Time
P 0 7
P
2 1 60
P
3 2 20
P
4 3 40
7ms

83. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
�1
�0
�1
�2
7ms
1
ProcessArrival TimeBurst Time
P 0 7
P
2 1 60
P
3 2 20
P
4 3 40
7ms

84. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 6052
P
3 2 20
P
4 3 40
�
1�2
7ms8ms
15ms
7ms

85. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 6052
P
3 2 2012
P
4 3 40
7ms8ms
�
1�2�
3
15ms
7ms23ms

86. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
6052
2012
4032
�
1�2�
3�
4
15ms31ms
7ms23ms
7ms8ms8ms8ms

87. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4
Arrival TimeBurst Time
0 7
1
2
3
605236
2012
4032
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms

88. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
4032
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms

89. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
4032
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms

90. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
403216
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms
�4
16ms
75ms

91. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
403216
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms
�4
16ms
75ms
�2
36ms
111ms

92. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
403216
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms
�4
16ms
75ms
�2
36ms
111ms

93. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
403216
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms

94. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(27/32)
�0
�1
�2
Process
P
1P
2
P
3P
4 605236
2012
403216
7ms23ms
�
1�2�
3�
4
15ms31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
Arrival TimeBurst Time
0 7
1
2
3
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms

95. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(28/32)
ProcessArrival TimeBurst Time
P
1 0 7
P
2 1 605236
P
3 2 2012
P
4 3 403216
15ms
7ms23ms
�
1�2�
3�
4
31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms

96. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(29/32)
ProcessArrival Time
P
1 0
P
2 1
P
3 2
P
4 3
15ms
7ms23ms
�
1�2�
3�
4
31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms
Waiting Time
??????�??????�??????�??????�
0 6 + 16
+ 28
13 + 2420 + 28
+ 36
= �= ��= ��= ��

97. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(30/32)
ProcessArrival Time
P
1 0
P
2 1
P
3 2
P
4 3
15ms
7ms23ms
�
1�2�
3�
4
31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms
Turnaround Time
??????�??????�??????�??????�
7 − 0 111 − 159 − 2127 − 3
= �= ���= ��= ���

98. 5. Multilevel QueueScheduling
SchedulingAlgorithms
(31/32)
ProcessArrival Time
P
1 0
P
2 1
P
3 2
P
4 3
15ms
7ms23ms
�
1�2�
3�
4
31ms
7ms8ms8ms8ms
�2
16ms
47ms
�3
12ms
59ms
�4
16ms
75ms
�2
36ms
111ms127ms
�4
16ms
Response Time
??????�??????�??????�??????�
0 − 0 7 − 1 15 − 2 23 − 3
= �= �= ��= ��

99. SchedulingAlgorithms
(32/32)
Student Example:
Using a Multilevel Queue Scheduling algorithm in Fig.1. Consider the
following processes with the relative CPU bursts.
ProcessArrival TimeBurst Time
P
1 0 20
P
2 1 60
P
3 2 5
P
4 2 40
Multilevel Queue Fixed priority
non-preemptive
Fig.1