Scheduling
Scheduling Criteria
Copyright By PowCoder代写 加微信 powcoder
Used for evaluating and comparing the different scheduling algorithms 1. CPU Utilisation – time CPU is kept busy.
2. Throughput – number of processes completed per time unit.
3. Turnaround time – time from process submission to completion.
4. Waiting time – time process spends in waiting queue.
5. Response time – time between the submission and first response of a request.
Example #1
Order of arrival Arrival times Burst times
P1 P2 P3 0 0 0 24 3 3
process time
GANTT CHART
Turn around time Waiting time Response time
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
Example #1
Order of arrival Arrival times Burst times
P1 P2 P3 0 0 0 24 3 3
process time
GANTT CHART
Turn around time Waiting time Response time
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
Example #1
Order of arrival Arrival times Burst times
P1 P2 P3 0 0 0 24 3 3
process time
GANTT CHART
Turn around time Waiting time Response time
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
Example #1
Order of arrival Arrival times Burst times
P1 P2 P3 0 0 0 24 3 3
process time
GANTT CHART
Turn around time Waiting time Response time
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
Example #1
Order of arrival Arrival times Burst times
process time
GANTT CHART
Turn around time Waiting time Response time
24 27 0 24 0 24
30 27 27 17 27 17
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
0 0 0 24 3 3
Example #1
Order of arrival Arrival times Burst times
process time
GANTT CHART
Turn around time Waiting time Response time
24 27 0 24 0 24
30 27 27 17 27 17
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
0 0 0 24 3 3
suffers from convoy effect
Example #1
Order of arrival Arrival times Burst times
process time
GANTT CHART
Turn around time Waiting time Response time
24 27 0 24 0 24
30 27 27 17 27 17
First Come First Served
FCFS – processes are scheduled in the order they arrive.
P3 Average
0 0 0 24 3 3
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #2
If the processes arrive in a different order:
Order of arrival P2 Arrival times 0 Burst times 3
Turn around time Waiting time Response time
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #2
If the processes arrive in a different order:
Order of arrival P2 Arrival times 0 Burst times 3
P3 P1 0 0 3 24
Turn around time Waiting time Response time
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #2
If the processes arrive in a different order:
Order of arrival P2 Arrival times 0 Burst times 3
P3 P1 0 0 3 24
Turn around time Waiting time Response time
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #2
If the processes arrive in a different order:
Order of arrival P2 Arrival times 0 Burst times 3
Turnaroundtime 30 Waiting time 6 Response time 6
3 6 13 0 3 3 0 3 3
P2 P3 Average
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #2
If the processes arrive in a different order:
Order of arrival P2 Arrival times 0 Burst times 3
Turnaroundtime 30 Waiting time 6 Response time 6
3 6 13 0 3 3 0 3 3
P2 P3 Average
Substantially reduced
Example #2
If the processes arrive in a different order:
process time
GANTT CHART P2P3 P1
First Come First Served
FCFS – processes are scheduled in the order they arrive.
Order of arrival P2 Arrival times 0 Burst times 3
Turnaroundtime 30 Waiting time 6 Response time 6
3 6 13 0 3 3 0 3 3
P2 P3 Average
The average waiting time under an FCFS policy is generally not minimal and may vary substantially if the processes’ CPU burst times vary greatly.
First Come First Served
FCFS – processes are scheduled in the order they arrive. Example #3
suffers from convoy effect
First Come First Served
FCFS – processes are scheduled in the order they arrive.
Note also that the FCFS scheduling algorithm is nonpreemptive. Once the CPU has been allocated to a process, that process keeps the CPU until it releases the CPU, either by terminating or by requesting I/O.
particularly troublesome for interactive systems, where it is important that each process get a share of the CPU at regular intervals. It would be disastrous to allow one process to keep the CPU for an extended period
Priority Scheduling
Shortest Job First
The Shortest Job First algorithm is a priority-scheduling algorithm. Each process has a priority and the CPU is always allocated to the highest priority process.
The SJF algorithm simply defines the priority of the process according to its next CPU burst requirement, the lower this value, the higher the priority.
High priority jobs are scheduled before low priority jobs.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
In this example, we have 3 processes with different burst time requirements, arriving at different times
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Process C is started at time 0, since it is the only process in the queue at t=0.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=3, Process B arrives with burst time requirement of 4. Although this is smaller than the burst requirement of process C, the SJF policy is non-preemptive and so process C keeps the CPU.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=5, Process A arrives with burst time requirement of only 1. Again, although this is smaller than the burst requirement of process C, the SJF policy is non- preemptive and so process C keeps the CPU.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=10, Process C finishes its job. With the SJF scheme, process A is selected next for processing as it has the least amount of burst time requirement.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=10, Process A is started.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=11, process A finishes its job. The CPU is allocated next to process B as it is the only one left in the queue.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
At time t=11, Process B is scheduled, allowing it to finish its job at time t=15.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Process A arrived at t=5, and completed its job at t=11. Its turnaround
time is therefore (11-5) is 6. Process B has a turnaround time of (15-3)
12, while process C has (10-0) 10.
Process A had to wait for 5 time units before being served.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Process B arrived at t=3, but only started receiving service at t=11, so its waiting time is 8.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Process C didn’t have to wait at all.
The response time is computed from the time of submission until the first response is produced.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Process A arrived at t=5, but the first response came at t=10. Its response time is therefore (10-5) 5.
Process B arrived at t=3, but the first response came at t=11. Its response time is therefore (11-3) 8.
Note that the waiting times and response times are the same for the processes because SJF is non pre- emptive algorithm.
Shortest Job First
SJF – selects the process with the smallest next CPU burst requirement.
Priority Scheduling
Shortest Job First
The priority of a job is often defined with an integer and all that really matters is whether the priority of one job is higher or lower than another.
It should be noted that there is not a general rule of whether 0 represents the highest priority job or the lowest. Either convention can do the same thing but its obviously important to know which one is being used.
Priority Scheduling
Shortest Job First
Priority scheduling algorithms may be either preemptive or nonpreemptive. This will determine whether the job is run in its entirety all at once or whether it may be preempted when another job with a higher priority arrives in the queue.
The preemptive version of the SJF algorithm is the SRTF algorithm.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
To see the effects of pre-emption, let us apply SRTF to the same problem we solved earlier using SJF.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
The CPU is allocated to Process C, as it is the only process to arrive at t=0.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
At t=3, process B arrives (with a burst time requirement of 4).
At this stage, process C needs 7 burst times to complete. Therefore, process C has a lower priority than process B and is preempted by B.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
At t=5, process A arrives (with a burst time requirement of 1).
At this stage, process B needs 2 burst times to complete, while process C needs 7 burst times to complete. A has the lowest burst time requirement – highest priority.
Process A preempts process B, and is allowed to finish its job until t=6.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
At t=6, after process A has completed, process B ranks top of the list (with a burst time requirement of 1).
Process B is allowed to finish its job until t=8.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
At t=8, only one process was left, process C, and so it is allowed to finish its job until t=15.
Process A arrived at t=5, and was able to complete its job at t=6.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
Its turnaround time is therefore (6-5) =1.
Process B arrived at t=3, and was able to complete its job at t=8.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
Its turnaround time is therefore (8-3) =5.
Process C arrived at t=0, and was only able to complete its job at t=15.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
Its turnaround time is therefore (15 – 0) =0.
Process A didn’t have to wait to be processed when it arrived at t=0, so its waiting time is 0.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
Process B arrived at t=3 and was immediately serviced at that time.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
However, it was eventually pre- empted and had to wait from time t=5 to t=6; therefore, its waiting time is 1.
Process C had to wait from time t=3 to t=8; therefore, its waiting time is 5.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
The CPU immediately responded to the request of all processes in this example (due to their high priority level at their time of arrival, so all response times are 0 in this example.
Shortest Remaining Time First
SRTF – a pre-emptive algorithm that will schedule the process with the fewest remaining next CPU burst requirement
Shortest Remaining Time First
Length of Next CPU Burst
The SJF scheduling algorithm is provably optimal.
It guarantees to produce the minimum average waiting time for a given set of processes.
However, it cannot be implemented at the level of CPU scheduling, as there is no way to know the length of the next CPU burst.
Nevertheless, we can approximate SRTF scheduling. We may not know the length of the next CPU burst but it can be predicted as an exponential average of the measured lengths of previous CPU bursts.
Shortest Remaining Time First
Determining Length of Next CPU Burst
The next CPU burst can be predicted as an exponential average of the measured lengths of previous CPU bursts.
• The parameter α controls the relative weight of recent and past history in our prediction.
• α is typically set less than 1.
Priority Scheduling
Shortest Job First
There is a major problem with priority scheduling algorithms called indefinite blocking or starvation.
A low-priority process may be left sitting in the ready queue (blocked) for an indefinite amount of time while the priority scheduling always chooses to run higher priority processes first.
This can occur in a heavily loaded computer system.
Priority Scheduling
Shortest Job First
In a case like this the low priority jobs will either eventually be run when the system runs out of high priority jobs to work on or else it will sit there forever until the machine eventually crashes.
There is a rumour that during a shutdown of an IBM 7094 at MIT in 1973 a low-priority process was discovered that had been originally submitted in 1967 had still not been run.
Priority Scheduling
Shortest Job First
A solution to this starvation problem is to use a method called aging which will slowly increase the priority of a process over time to avoid a low-priority process from waiting indefinitely.
Eventually as a low-priority process sits in the queue its priority will eventually become the highest and the job will be run.
Round Robin Scheduling
The Round-Robin scheduling algorithm is designed for time-sharing systems where many processes will be executed at once. A unit of time called the time quantum is defined that represents the maximum amount of time a process is allowed to run at once.
If the process is still running after the time quantum has passed, it will be preempted and another process will run instead.
Round Robin Scheduling
The Round-Robin algorithm will essentially treat the ready queue as a FIFO queue for processes.
The scheduler will always select the process from the front of the queue and allow it to execute. If the process burst completes or the time-quantum expires then the process will be added to the back of the queue and the next process will be allowed to execute.
Any time a new process is added, it will join at the back of the queue.
Time quantum = 3
process time
GANTT CHART
B A qCueue, aBnd so it getsCprocessed first for a
Order of arrival C Arrival times 0 Burst times 10
Turn around time 7 Waiting time 6 Response time 6
11 15 11 7 5 6 3 0 3
Round Robin
0 3 67 1011 1415
We have 3 processes arriving at the same time, but Process C is at the head of the
maximum time of q=3.
Eventually, process C goes to the tail of the queue.
A B C Average
Time quantum = 3
process time
similarlCy, it gets processed
Turn around time 7 Waiting time 6 Response time 6
11 15 11 7 5 6 3 0 3
Round Robin
Order of arrival C B A Arrival times 0 0 0 Burst times 10 4 1
GANTT CHART
next. It has 4 bursts but
0 3 67 1011 1415
A B C Average
Process B is scheduled
for a maximum time of q=3.
Process B goes to the tail of the queue eventually.
Time quantum = 3
process time
GANTT CHART
Process A is processed next. It has only 1 burst r e q u i r e Cm e n t a n d s o i t finishes early at t=7.
Turn around time 7 Waiting time 6 Response time 6
11 15 11 7 5 6 3 0 3
Round Robin
Order of arrival C B A Arrival times 0 0 0 Burst times 10 4 1
0 3 67 1011 1415
A B C Average
Time quantum = 3
process time
7 burstCrequirement, but
Turn around time 7 Waiting time 6 Response time 6
11 15 7 5 3 0
Round Robin
Order of arrival C B A Arrival times 0 0 0 Burst times 10 4 1
GANTT CHART
scheduled next. It still has
0 3 67 1011 1415
At t=7, Process C is
has to be pre-empted at
Time quantum = 3
process time
GANTT CHART CBACBC
Order of arrival C Arrival times 0 Burst times 10
The RR scheduling continues until all processes complete their jobs.
Turn around time 7 Waiting time 6 Response time 6
11 15 11 7 5 6 3 0 3
Round Robin
0 3 67 1011 1415
A B C Average
Round Robin Scheduling
With the round-robin algorithm, if there are n processes in the ready queue and the time quantum is q then each process will get 1/n of the CPU time in chunks of at most q time units.
Each process will have to wait at most (n − 1)q time units until it next executes.
If there are 8 processes and a time quantum of 30 milliseconds then each process will get up to 30 milliseconds of every (n*q=8*30) 240 milliseconds and will have to wait at most [(n-1)q = 7*30] 210 milliseconds between executions.
Round Robin Scheduling
The performance of the RR algorithm will be heavily dependent on the
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com