Operating Systems
Lecture 6 CPU Scheduling
Scheduling
Copyright By PowCoder代写 加微信 powcoder
FCFS/SJF/SRT scheduling Priority scheduling
RR scheduling
Multi-level queues
COMP 2432 2021/2022
An operating system executes a variety of programs for users.
When a program is executed, it becomes a process, i.e. a process is a program in execution.
In an OS, there are multiple processes executing at the same time.
Some computer systems have multiple CPUs, but most smaller ones have only one CPU.
When the number of processes is more than number of CPUs, each CPU can only be allocated to a process for execution at each moment.
Not all process can receive the CPU service at any moment.
Process would alternate between “served by a CPU” (running) and “waiting” (ready/waiting) states. There are other possibilities to the process state.
COMP 2432 2021/2022
Scheduling
We are concerned about the decision of which process should get the CPU when the CPU is not in used.
This is called CPU scheduling, and the operating system component that makes this decision is called the CPU scheduler.
The CPU scheduler needs to maximize CPU utilization in the presence of multi-programming.
A careful observation on CPU and I/O burst and distribution via histogram of CPU bursts suggests the real need of CPU scheduling.
A CPU burst is the consecutive amount of CPU time used by a process.
There are usually many relatively short CPU bursts.
One would like to serve the CPU bursts effectively.
COMP 2432 2021/2022
Scheduling
CPU and I/O bursts CPU burst histogram
Lecture 6 COMP 2432 2021/2022
Very few bursts lasting for 8 or more ms
Scheduling
CPU scheduling decisions may take place when a process:
COMP 2432 2021/2022
Needs to wait for I/O or special events.
Finishes execution.
Gives up the CPU willingly or non-willingly.
Completes its I/O or its special events happen.
The first two situations imply that current process can continue to hold CPU if it needs to (non- preemptive, i.e. no forced taken of CPU).
The last two situations imply that there is a choice of taking CPU to give to a chosen process (preemptive, i.e. possibly forced taken of CPU).
Scheduling
Non-preemptive scheduling is easy to do.
A process just uses the CPU until it wants to give it up when Terminated
Waiting for I/O
Execute a yield statement (in Java)
No special hardware for timer interrupt is needed. Used in Windows 3.1 and old systems.
determine which eligible process will be the next to get the CPU. COMP 2432 2021/2022
Preemptive scheduling is more complex.
A process will be deprived of the CPU when its allocated
time slice is used up or some other event happens.
A form of timer interrupt must be used so that OS can take control when it is time.
Used in most OS.
A scheduling algorithm is used by scheduler to
Scheduling
After CPU scheduler makes decision on which process is the next one to execute, the operating system will proceed to give the CPU to the chosen process.
OS needs to:
Perform context switching.
Switch to user mode.
Jump to the proper location in the user program to resume that program.
This time taken by the OS to stop the current process and start another process for running is called dispatch latency.
Dispatch latency is a form of overhead, since CPU time is spent without doing real work.
COMP 2432 2021/2022
Scheduling Consideration
CPU utilization
Percentage of CPU time used for real work (non-idle). Want high CPU utilization.
Throughput
Number of processes completing execution per time unit. Want high throughput.
Turnaround time
Amount of time to complete process execution since arrival. Want short turnaround time.
Waiting time
Amount of time a process spends waiting in ready queue. Want short waiting time.
until the first response is produced (may not be output).
Want short response time. COMP 2432 2021/2022
Response time
Amount of time from the moment a request was submitted
Scheduling Algorithms
First Come First Serve (FCFS)
Shortest Job First (SJF)
Shortest Remaining Time (SRT) Priority (PR)
Round Robin (RR)
Multi-Level Queue
Multi-Level Feedback Queue
COMP 2432 2021/2022
Convoy effect happens when a single long process is blocking a number of processes.
FCFS Scheduling
To dry-run scheduling algorithms, we need information about the burst time (execution time) and the arrival time of processes.
Process Burst Time Arrival Time P1 24 0
In FCFS, processes are served in their arrival order.
The for the schedule is
Waiting time for P1 = 0, for P2 = 23, for P3 = 25.
Average waiting time = (0 + 23 + 25)/3 = 16.
COMP 2432 2021/2022
Convoy effect !!
FCFS Scheduling
Assume that process P1 arrives later than P2 and P3. Process Burst Time Arrival Time
Now the for the schedule is
Waiting time for P1 = 4, for P2 = 0, for P3 = 2.
Average waiting time = (4 + 0 + 2)/3 = 2.
other processes. COMP 2432 2021/2022
This is much better than before.
No convey effect since the long process P1 does not block
FCFS Scheduling
Processes may arrive in around the same time.
Often the process pid could reflect the real arrival order,
since earlier process would normally receive a smaller pid. This is the case in Unix and Linux, but not for Windows.
P1 goes first in this example.
Process Burst Time Arrival Time P1 24 0
The for the schedule is
0 24 27 30
Waiting time for P1 = 0, for P2 = 24, for P3 = 27.
Average waiting time = (0 + 24 + 27)/3 = 17.
COMP 2432 2021/2022
FCFS Scheduling
Consider the example again, where time is in ms. Process Burst Time Arrival Time
TurnaroundtimeforP1 =24,forP2 =27,forP3 =30.
Average turnaround time = (24 + 27 + 30)/3 = 27.
Throughput = 3 process/0.03 s = 100 processes per second.
Let us assume that a process prints a hello message when it first gets executed, then response time would measure the moment it first gets execution (user sees a response).
ResponsetimeforP1 =0,forP2 =24,forP3 =27.
Average response time = (0 + 24 + 27)/3 = 17.
0 24 27 30
COMP 2432 2021/2022
SJF Scheduling
The convoy effect occurs when there is a long process using CPU, blocking many shorter processes.
It will cause the waiting time to become very large.
To reduce the convoy effect, it is a good idea to let
smaller jobs execute first.
To an extreme, smallest jobs will always be executed first.
This is called the Shortest Job First (SJF) scheduling algorithm.
It could be proved that SJF produces the smallest average waiting time and smallest average turnaround time for a given set of processes.
We say that SJF is optimal. COMP 2432 2021/2022
SJF Scheduling
Assume the following processes.
Process Burst Time Arrival Time P1 6 0
The for the schedule is
03 9 16 24
Waiting time: P1 = 3, P2 = 16, P3 = 9, P4 = 0.
Average waiting time = (3 + 16 + 9 + 0)/4 = 7.
Turnaround time: P1 = 9, P2 = 24, P3 = 16, P4 = 3.
Average turnaround time = (9 + 24 + 16 + 3)/4 = 13. COMP 2432 2021/2022
SJF Scheduling
It may not be so lucky that all processes arrive at 0. Process Burst Time Arrival Time
P3 9 2 P4 5 3
The for the schedule is
0 81217 26
Waitingtime:P1 = ,P2 = ,P3 = ,P4 =
Average waiting time =
Turnaroundtime:P1 = ,P2 = ,P3 = ,P4 =
Average turnaround time = COMP 2432 2021/2022
SRT Scheduling
Recall that the convoy effect occurs when there is a long process using CPU, blocking many shorter processes.
To beat the possible convoy effect in SJF when an early arriving long job is holding up the CPU, we could allow preemption of jobs in SJF.
The preemptive version of SJF is called Shortest Remaining Time (SRT).
In SRT, whenever a new process arrives, the remaining executing time of all existing processes are considered, and the one with the smallest remaining time (including the newly arriving one) will be executed.
If the one to be executed is different from the currently executing one, preemption has occurred.
It could be proved that SRT always produces the smallest average waiting time and smallest average turnaround time for a given set of processes.
We say that SRT is optimal (for preemptive scheduling).
SJF is optimal for non-preemptive scheduling. COMP 2432 2021/2022
SRT Scheduling
In this example, we allow P2 to preempt P1. Process Burst Time Arrival Time P1 8 0
P2 4 (small) 1
P3 9 2 P4 5 3
The for the schedule is P1
01 5 10 17 26
Waiting time: P1 = 9, P2 = 0, P3 = 15, P4 = 2.
Average waiting time = (9 + 0 + 15 + 2)/4 = 6.5.
Turnaround time: P1 = 17, P2 = 4, P3 = 24, P4 = 7.
Average turnaround time = (17+4+24+7)/4 = 13.
COMP 2432 2021/2022
SRT Scheduling
Try this on both SJF and SRT.
Process Burst Time Arrival Time P1 7 0
The s for the schedules are
0 78 12 16
02457 11 16
What are the waiting and turnaround time?
COMP 2432 2021/2022
Priority Scheduling
A priority number is associated with each process.
CPU is allocated to the process with highest priority.
In some systems, largest value in priority means highest priority (Windows), and in some others, smallest value means highest priority (Unix and Linux).
Again, priority scheduling could be either non-preemptive or preemptive, but the preemptive version is more commonly in use.
SJF is a form of priority scheduling where the priority is CPU burst time (with smaller value meaning higher priority).
FCFS is a form of priority scheduling where the
priority is process arrival time (with smaller value meaning higher priority). COMP 2432 2021/2022
Priority Scheduling
Assumethefollowingprocesses. Process Burst Time Priority
P2 1 1 (highest) P3 2 4
P4 1 5 (lowest) P5 5 2
The for the schedule is
Try also the case that 1 is lowest.
Arrival Time 0
COMP 2432 2021/2022
Waitingtime:P1 = ,P2 = ,P3 = ,P4 = ,P5 =
Averagewaitingtime=
Turnaroundtime:P1 = ,P2 = ,P3 = ,P4 = ,P5 =
Averageturnaroundtime=
Priority Scheduling
Try also the case that 1 is lowest.
Assumethefollowingprocesses(preemptiveapproach).
Process Burst Time Priority
P2 1 1 (highest) P3 2 4
P4 1 5 (lowest) P5 5 2
The for the schedule is
Arrival Time 0
COMP 2432 2021/2022
Waitingtime:P1 = ,P2 = ,P3 = ,P4 = ,P5 =
Averagewaitingtime=
Turnaroundtime:P1 = ,P2 = ,P3 = ,P4 = ,P5 =
Averageturnaroundtime=
Priority Scheduling
A problem with priority scheduling is that a low priority process may get no chance of execution, if there are higher priority processes that keep coming.
COMP 2432 2021/2022
This problem is called starvation.
The low priority process starves for the CPU that is
repeatedly consumed by high priority processes.
SJF and SRT are special cases of priority scheduling, so they also suffer from the same starvation problem.
A long process would not get a chance of execution under SJF and SRT.
Solutions:
Upgrade the priority of processes that wait for too long. Make a fairer usage of the CPU.
RR Scheduling
For FCFS, SJF, SRT, PR, there is good performance for the process at the head, but it is very poor for those at the tail.
We want a fair share of the CPU to everyone.
This is achieved in Round Robin (RR) scheduling.
Each process gets a small unit of CPU time in turn.
After this time has elapsed, the process is preempted and put back to the end of the ready queue.
This specific small unit of CPU time is called a time quantum, typically 10-100 milliseconds.
If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in blocks of at most q time units at once.
No process has to wait for more than the time it
takes for each other process to use the CPU once,
i.e. no more than q (n 1) time units. COMP 2432 2021/2022
RR Scheduling
When time quantum of a process is up, it will be put back to the end of the ready queue. Assume q = 4.
Process Burst Time Arrival Time P1 18 0
The for the schedule is
0 4 8 11 15 19 2324 2830
1 2 3 1 2 1 21 1 2312121 312
COMP 2432 2021/2022
RR Scheduling
When time quantum size changes, the performance could also change. Assume now q = 2.
Process Burst Time Arrival Time P1 18 0
The for the schedule is
0 2 4 6 81011131517192122 24262830
Waitingtime:P1 = ,P2 = ,P3 =
Average waiting time =
Turnaroundtime:P1 = ,P2 = ,P3 =
Average turnaround time =
COMP 2432 2021/2022
RR Scheduling
When arrival times are not all zero, the arrival order would affect ready queue. Assume q = 4 to compare.
Process Burst Time Arrival Time P1 18 0
The for the schedule is
0 4 8 12 15 19 2324 2830
1 2 2 1 1 3 2 1 2 1 1 1332121
COMP 2432 2021/2022
RR Scheduling
Now q = 2 and make all the comparisons. Process Burst Time Arrival Time P1 18 0
The for the schedule is
0 2 4 6 8101214161719212324262830 122 11
COMP 2432 2021/2022
RR Scheduling
Try this on RR with q = 40 and q = 20. Process Burst Time Arrival Time P1 53 0
P3 68 0 P4 24 0
The s for the schedules are q = 40
40 57 97 121 134 162
20 37 57 77 97 117121 134 154162
What are the waiting and turnaround time?
COMP 2432 2021/2022
RR Scheduling
Try this again on RR with q = 40 and q = 20. Process Burst Time Arrival Time
P3 68 6 P4 24 9
The s for the schedules are q = 40
20 37 57 77 97
121 134 162
117121 134 154162
Any observation on the results?
COMP 2432 2021/2022
RR Scheduling
Performance
Higher turnaround time, but better response time.
q large then becomes close to FCFS.
q small then context switching overhead will be very high. How many context switches in the previous example?
Time quantum versus context switching:
COMP 2432 2021/2022
Multi-Level Queue Scheduling
Some jobs want fast turnaround time but do not care about response time (batch jobs) and some others want fast response time (interactive jobs).
SJF/SRT is good for batch jobs, and RR is good for interactive jobs.
How to handle a job mix?
In Multi-Level Queue scheduling, the ready queue is partitioned into separate queues.
System queue, interactive queue, batch queue, etc.
Each queue has its own scheduling algorithm.
System (Priority), interactive (RR), batch (FCFS/SRT).
Scheduling must also be done between the queues. COMP 2432 2021/2022
Multi-Level Queue Scheduling
Fixed priority scheduling
Each queue has a priority and high priority queues will be
served before low priority queue. Possibility of starvation.
Time slicing
Each queue gets a certain amount of CPU time for scheduling its own
100 processes Example:
Allocate 50% to system jobs
Allocate 25% to interactive jobs
Allocate 25% to batch/other jobs.
COMP 2432 2021/2022
Multi-Level Feedback Queue
In Multi-Level Queue scheduling, a process may enter a wrong queue and get stuck.
When this could happen?
In Multi-Level Feedback Queue scheduling, a process is allowed to move between the queues when there is a need.
A typical multi-level feedback queue scheduler is defined by the following parameters:
Number of queues.
Scheduling algorithms for each queue.
Method used to determine when to upgrade a process to a higher priority queue.
Method used to determine when to downgrade a process to a lower priority queue.
Method used to determine which queue a process should enter when that process needs CPU. COMP 2432 2021/2022
Multi-Level Feedback Queue
We consider an example with three queues:
Q0 uses RR with time quantum 8 and max quantum 8.
Q1 uses RR with time quantum 16 and max quantum 16. Q2 uses FCFS.
P 2432 2021/2022
Multi-Level Feedback Queue
Scheduling for the example:
A new job enters queue Q0.
When it is scheduled, it receives 8 ms of CPU time.
If it does not finish in 8 ms, it is moved to queue Q1.
At Q1, when it is scheduled, it receives 16 ms of CPU time.
If it still does not complete, it is moved to queue Q2.
At Q2, those “longer” jobs are served in FCFS order.
At both Q0 and Q1, if a job waits for I/O before its time quantum expires, it will remain on the same queue.
Q0 has the highest priority and Q2 has the lowest priority.
Fixed priority scheduling is used.
So I/O bound jobs remain in Q0 and long batch jobs are downgraded to Q2.
Short jobs get fast execution and good response.
Do you see any problem with this arrangement?
COMP 2432 2021/2022
Scheduling
FCFS/SJF/SRT scheduling Priority scheduling
RR scheduling
Multi-level queues
COMP 2432 2021/2022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com