569.27K

4- CPU scheduling - new

CPU Scheduling
◉ Scheduler types and goals of scheduling
◉ Scheduler types
◉ Scheduling criteria
◉ Goals of scheduling
◉ Proess scheduling
◉ Scheduling algorithms
◉ FCFS, SJF & SRT, HPF, RR, HRRN, Multi-level queue algorithm, Multilevel feedback
algorithm
2

3.

1
Scheduler types and
goals of scheduling
3

4.

Types of Schedulers
◉ Long term scheduler (high-level scheduler, Job scheduler )
◉ Job
◉ Less frequently (every few minutes)
◉ Tasks
◉ It determines which programs are admitted to the system for
◉
processing
◉ It selects processes from the job queue and loads them into memory
for execution.
◉ Process loads into the memory for CPU scheduling
Primary aim of the Job Scheduler is to maintain a good degree of
Multiprogramming
4

5.

Types of Schedulers
◉ Short term scheduler (low-level scheduler, CPU scheduler)
◉ Process in memory
◉ Runs very frequently (every 10-100 ms)
◉ Tasks
◉ decides which of the ready, in-memory processes is to be executed
(allocated a CPU)
◉ Medium term scheduler (Swapping)
◉ It removes the processes from the memory and later swaps in.
◉ It reduces the degree of multiprogramming.
◉ It is in-charge of handling the swapped out-processes.
5

6.

7.

Scheduling criteria
◉
CPU utilization---high is good; the system works best when the CPU is kept as
busy as possible
◉ Throughput -- the number of processes that complete their execution per time
unit.
◉ Turnaround time -- amount of time to execute a particular process
◉ Waiting time --- amount of time a process has been waiting in the ready queue
◉ Response time ---amount of time it takes from when a request was submitted
until the first response is produced, not output (for time-sharing systme)
It makes sense to look at averages of these matrices
7

8.

Goals of Scheduling
◉ Maximum CPU usage---◉ Fairness
◉ Short average turnaround time
1 n
T [ Ti ]
n i 1
T average turnaround time;
Ts service time or CPU time
1 n Ti
W
n i 1 Ts
Ti turnaround time
8

9.

2
Process scheduling
9

10.

CPU Scheduling
◉ CPU scheduler
◉ It selects a process among the processes that are ready to execute and allocates
◉
◉
CPU to one of them
Known as dispatchers, make the decision of which process to execute next.
If there is no process in the ready queue, the system will schedule an idle process
◉ Scene
◉ N process in ready queue, waiting for CPU
◉ M CPU, M>= 1 (multicore system)
◉ Decide: assign which CPU to which process
10

11.

Procedure of CPU scheduling
◉ Preserve the processor information
◉ Choose a process in the ready queue according to an scheduling algorithm
◉ Assign the CPU to the process
11

12.

Parts of the scheduler
◉ Enqueuer
◉ It adds a pointer or reference to the process’ PCB, which is usually a collection of
linked lists.
◉ Dispatcher
◉ The part that implements the scheduling algorithm to pick the next process to run
◉ Context Switcher
◉ Loads the selected process onto the CPU as the running process.
12

13.

Parts of the scheduler
13

14.

Three issues that need to be addressed
in CPU scheduling
◉ What: On what principles to choose the next process to be executed
◉ Scheduling algorithm
◉ When: When to schedule
◉ Scheduling circumtances
◉ How: How to make the selected process run on the CPU
◉ Scheduling process (context switching of processes)
14

15.

CPU scheduling circumstances
◉ CPU scheduling decisions may take place under the following four
circumstances: (preemptive, non-preemptive )
◉
◉
◉
◉
When a process switches from the running state to the waiting state(for I/O
request or invocation of wait for the termination of one of the child processes).
( A new process must be selected)
When a process switches from the running state to the ready state (for example,
when the timeslice is uesed up). (To either continue running the current process,
or select a different one.)
When a process switches from the waiting state to the ready state(for example,
completion of I/O or a return from wait()). (To either continue running the current
process, or select a different one.)
When a process terminates. ( A new process must be selected)
15

16.

Scheduling---Process switch
◉ Process switch refers to the procedure in which one process gives up the
processor and another process takes up the processors
◉ Two tasks
◉
◉
Switch global page directory to load a new address space
Switch kernel stack and hardware context, which contains all the information the
kernel needs to execute a new process, such as CPU related registers
The process switch includes
protection of various states of the original running
process
and restore the various states of the new process
16

17.

Process context switch
Scene: process A is taken off and process B takes up CPU
◉
Save the context of process A (program counter, Program Status Word, other
registers ...)
◉
◉
◉
◉
Update process A's PCB with new status and other relevant information
Move process A to an appropriate queue (ready, blocked ...)
Set the state of process B to running
Restore context from the PCB of process B (program counter, Program Status Word,
other registers ...)
17

18.

Cost of process context switch
◉ Direct cost : CPU time used by the kernel to complete the switch
◉
Save and restore registers ...
◉
Switching address space (relevant instructions are more expensive)
◉ Indirect cost:
○ Invalidate Cache, Buffer Cache and TLB(Translation Look-aside Buffer)
18

19.

3
Scheduling algorithms
19

20.

Issues while designing scheduling algorithms
◉ Process priorities
◉ Preemptive and non-preemptive scheduling
◉ I/O bound and CPU bound processes
◉ Time slice
20

21.

Process priorities
◉ Priority level & Priority number
◉ Static & dynamic
◉ Static priority (fixed priority)
◉ It is allocated during creation without changing during runtime.
◉ Dynamic priority
◉ It is allocated during creation while it can be changed dynamically.
◉ For example: a process with a long waiting time can increase its priority
21

22.

Preemptive and non-preemptive scheduling
◉ Preemptive scheduling
◉
Preemptive scheduling allows a running process to be interrupted by a high
priority process
◉ Non-preemptive scheduling
◉
Any new process has to wait until the running process finishes its CPU cycle.
22

23.

I/O bound and CPU bound processes
◉
I/O bound-----In computer science, I/O bound refers to a condition in which the time it takes to
◉
complete a computation is determined principally by the period spent waiting for input/output
operations to be completed.
CPU bound----When the time for it to complete a task is determined principally by the speed of the
CPU .
23

24.

Time slice
◉ Time slice, time quantum or quantum
◉ The period of time for which a process is allowed to run is generally called the time
◉
slice or quantum.
The scheduler is run once every time slice to choose the next process to run
◉ How to choose a time slice size?
Process switching cost
response time requirement
number of ready processes
CPU capability
........
24

25.

FCFS (First Come First
Serve)
25

26.

FCFS
◉
◉
◉
◉
First In First Out (FIFO)
It simply queues processes in the order that they arrive in the ready queue.
Non- preemptive
Pros
◉
◉
fairness----Every process will get a chance to run, so starvation doesn't occur.
pretty simple and easy to implement
◉ Cons
◉ If a process executes for a long time, the processes in the back of the queue will
have to wait for a long time before they get a chance to be executed.
26

27.

FCFS case1
◉
◉
◉
Three processes are ready in order: P1, P2, P3
CPU time: P1-- 24s, P2 ---3s, P3---3s
Gantt chart
Throughput: 3 / 30 = 0.1 process/s
Turnaround time: P1: 24, P2:27, P3: 30
Average turnaround time: (24+27+30)/3 = 27 s
27

28.

FCFS case2
◉
◉
◉
◉
Three processes are ready in order: P1, P2, P3
CPU time: P1-- 24s, P2 ---3s, P3---3s
Change the scheduling order, P2, P3, P1
Gantt chart
Throughput: 3 / 30 = 0.1 process/s
Turnaround time: P1: 30, P2:3, P3: 6
Average turnaround time: (30+3+6)/3 = 13 s
28

29.

SJF (Shorted Job First) &
SRTF(Shorted Remaining Time First)
29

30.

SJF & SRTF
◉
◉
◉
◉
◉
Idea: Complete short jobs first to improve
turnaround time for short jobs
Shortest job first (SJF) or Shortest Job Next(SJN)
It is a scheduling policy that selects the waiting process with the smallest
execution time to execute next.
Non- preemptive or preemptive
◉
Preemptive
Jobs are put into the ready queue as they come. Although a process with short
burst time begins, the current process is removed or preempted from execution,
and the job which is shorter is executed first.
◉
Userally used in long-term scheduling
Shortest Remaining Time First (SRTF): The processor is allocated to the job closest to
completion.
30

31.

SJF case
Average turnaround time
Non-preemptive:
(7+10+4+11)/4 =8
Preemptive: P1: 7+9=16;
P2:4+1=5; P3:1; P4:4+2=6
(16+5+1+6)/4 = 7
Non-preemptive SJF
Preemptive SJF
31

32.

◉
SJF
Pros
◉
Maximizes “task throughput”
◉ By running tasks which take less time to complete first, we can complete
more tasks in a given amount of time
◉ Cons
◉ Unfair to larger tasks
◉ – Larger tasks do not get an opportunity to run if smaller tasks keep
◉
entering the system
◉ starvation
Computers are not psychic
◉ – It is not feasible to accurately predict how long a task’s CPU burst-time
could be.
32

33.

HPF (Highest Priority First)
33

34.

HPF
◉
◉
◉
◉
◉
◉
◉
◉
◉
Highest Priority First ----HPF
Select the highest priority process to run
In general:
◉
◉
system process has higher priority than user process
The foreground process has higher priority than the background process
Preemptive and non-preemptive
Priority can be static or dynamic.
Process priority basis-----Process type, resource requirements, user
requirements
Ready queues can be organized by priority
Pros----Easy to implement
Cons-----Not fair, starvation
34

35.

HPF
◉
Dynamic priority level: The priorities are calculated during the execution of the
system, i.e.
◉
The longer waiting time, the higher priority
◉
In preemptive scheduling, the longer running time, the lower priority, which prevent the
long-term jobs to take up CPU for a long time
35

36.

HPF case
Non-preemptive HPF
Calculate average turnaroud time and average weighted turnaroud time
Process
Priority
Arrival
Time
Service
Time
Starting
Time
End
Time
Turnaroud
Time
Weighted
Turnaroud
Time
Sequence
P1
P2
P3
P4
4
3
2
1
0
3
5
13
5
2
6
10
0
11
5
13
5
13
11
23
5
10
6
10
1
5
1
1
1
3
2
4
Turnaroud Time 5+10+6+10 /4=31/4=7.75
Weighted Turnaroud Time 1+5+1+1 /4=2

37.

HPF case------Preemptive HPF
Process
Priority
Arrival
Time
Service
Time
Starting
Time
End
Time
Turnaroud Weighted
Time
Turnaroud
Time
P1
P2
P3
P4
4
3
2
1
0
3
5
13
5
2
6
10
0
3
5
13
13
5
11
23
13
2
6
10
P1 P2 P3
0
3
5
P1
11
13
P4
23
Turnaroud Time 13+2+6+10 /4=31/4=7.75
Weighted Turnaroud Time 2.6+1+1+1 /4=1.4
2.6
1
1
1

38.

HRRN (Highest Response Ratio Next)
38

39.

HRRN
◉
◉
◉
◉
◉
This is a non-preemptive algorithm in which, the scheduling is done on the
basis of an extra parameter called Response Ratio.
A Response Ratio is calculated for each of the available jobs and the Job with
the highest response ratio is given priority over the others.
Non-preemptive
It was developed as an improvement of SJF
Response Ratio is calculated by the given formula.
Response ratio = (W+S)/S = 1+ W/S
Where
W: Waiting time
S: Service time or Burst time
39

40.

Job
Arrival
Time
Service
Time
J1
J2
J3
J4
0
5
10
15
20
15
5
10
SJF
Job
Arrival
Time
Service
Time
J1
J3
J4
J2
0
10
15
5
20
5
10
15
HRRN
Response
Ratio
J1
J3
J2
J4
20
25
40
2026/5/12
0
50
40

41.

RR (Round Robin) in time sharing system
41

42.

RR
◉
Run process for one time slice, then
move to back of queue. Each process
gets equal share of the CPU.
◉
Aim:
◉
Improve average response time for short
tasks
◉
Ideas
◉
◉
◉
Periodic switching
Each process is assigned a time slice
Clock interrupt → switch
42

43.

RR case
Processes A,B,C,D,E with CPU times are 2, 4, 6, 8, 10 minutes
RR: slice time is 2 minutes
Calculate turnaround time and weighted turnaround time

44.

Process
Starting time
CPU time
End time
Turnaround
time
Weighted
turnaround
time
A
0
2
2
2
1
B
2
4
12
12
3
C
4
6
20
20
3.3
D
6
8
26
26
3.25
E
8
10
30
30
3
A
0
B
2
C
4
D
6
E
8
B
10
C
12
D
14
E
16
C
18
D
20
E
22
D
24
E
26
Average Turnaround time 18, Weighted turnaround time2.71
E
28
30

45.

RR
◉
How to choose the right time slice?
◉
Too long-------greater than typical
interaction time
◉
◉
◉
Downgrade to FCFS algorithm
Increase the response time of
short processes
Too short------less than typical
interaction time
◉
Process switching wastes CPU
time
45

46.

RR
◉
Pros
◉
◉
◉
Fair to small tasks
Facilitates interactive calculation and fast response time
Cons:
◉
◉
Context-Switch Overhead
No gain for tasks with equal run time
◉
If we have ten tasks in the system which take ten seconds to run, then we will not have a
single completed task until 100 seconds have passed. In the FIFO case, we would have
our first task complete in 10 seconds, the second task complete in 20 seconds, etc. As a
result, the “task throughput” is potentially lower
46

47.

Cases
◉ 4 processes A, B, C, D with simultaneous arrival ; 4 processes
are run 11,7,2, and 4 time units respectively, with a time slice
of 1 per rotation. Calculate
◉ Turnaround time ?
◉ Weighted turnaround time ?
◉ Average turnaround time ? 16.25
◉ Average weighted turnaround time? 3.01
47

48.

Multi-level queue scheduling
algorithm
48

49.

Multi-level queue scheduling algorithm
◉
◉
It partitions the ready queue into several separate queues.
The processes are permanently assigned to one queue, generally based on
some property of the process, such as memory size, process priority, or process
type.
◉
◉
◉
Each queue has its own scheduling algorithm.
Preemptive or non-preemptive
For example
◉
◉
A common division is made between foreground(or interactive) processes and
background (or batch) processes.
Foreground queue----- Round Robin; Background queue ---- FCFS
49

50.

Case
◉
Let us consider an example of a multilevel queue-scheduling algorithm with
five queues:
◉
System Processes, Interactive Processes, Interactive Editing Processes, Batch
Processes, Student Processes
◉
◉
Each queue has absolute priority over lower-priority queues.
No process in the batch queue, for example, could run unless the queues for
system processes, interactive processes, and interactive editing processes were
all empty.
◉
If an interactive editing process entered the ready queue while a batch process
was running, the batch process will be preempted.
50

51.

52.

Multi-level queue scheduling algorithm
◉
Pros
◉
◉
◉
Flexible implementation
Enable short CPU-bound jobs to be processed quickly
Cons
◉
Queues require monitoring, which a costly activity
52

53.

Multi-level feedback scheduling
algorithm
53

54.

Multilevel feedback scheduling algorithm
◉
In a multilevel queue-scheduling algorithm, processes are permanently
assigned to a queue on entry to the system. Processes do not move between
queues. This setup has the advantage of low scheduling overhead, but the
disadvantage of being inflexible.
◉
Multilevel feedback queue scheduling, however, allows a process to move
between queues.
◉
If a process uses too much CPU time, it will be moved to a lower-priority
queue. Similarly, a process that waits too long in a lower-priority queue may be
moved to a higher-priority queue. This form of aging prevents starvation.
54

55.

RR
55

56.

Multilevel feedback scheduling algorithm
◉
In general, a multilevel feedback queue scheduler is defined by the following
parameters:
◉
◉
◉
◉
◉
The number of queues.
The scheduling algorithm for each queue.
The method used to determine when to upgrade a process to a higher-priority queue.
The method used to determine when to demote a process to a lower-priority queue.
The method used to determine which queue a process will enter when that process
needs service.
56

57.

Multilevel feedback scheduling algorithm
◉ Result approximates SRTF
◉ CPU bound jobs rapidly to lower queues
◉ Short-running I/O bound jobs stay near the top
◉ Scheduling must be done between the queues
◉ Fixed priority scheduling: serve all from the highest priority, then the next
priority, etc.
◉
Time slice: each queue gets a certain amout of CPU time
(e.g.. 70% to the highest, 20% next, 10% lowest)
57

58.

Case:
Process: A,B,C,D,E,F,G,H,I; Initial time slice is 2 minutes; 4 ready queues
Calculate turnaroud time and weighted turnaround time. (Question: How about 3 ready queues?)
Process Starting time
CPU time
A
2
0
B
6
C
10
D
14
E
18
F
22
G
26
H
30
I
34
End time
Turnaround
Time
Weighted
turnaround
time

59.

Proc CPU
ess Time
A
2
B
6
C
10
D
14
E
18
F
22
G
26
H
30
I
34
Ready Q1 2m
Starting
End
Ready Q2 4m
left
Starting
End
Ready Q3 8m
left
Starting
End
Ready Q4 16m
left
Starting
End
left

60.

Proc
ess
CPU
time
Ready Q1 2m
Ready Q2 4m
Starting
End
Left
A
2
0
2
0
B
6
2
4
C
10
4
D
14
E
Ready Q3 8m
Starting
End
Left
4
18
22
0
6
8
22
26
6
8
12
26
18
8
10
16
F
22
10
12
G
26
12
H
30
I
34
Ready Q4 16m
Starting
End
Left
4
50
54
0
30
8
54
62
0
30
34
12
62
70
20
34
38
16
70
14
24
38
42
20
14
16
28
42
46
16
18
32
46
50
Analysis: A 0->2
E 8->106
I 16->162
Starting
End
Left
4
102
106
0
78
8
106
114
0
78
86
12
114
126
0
24
86
94
16
126
142
0
28
94
102
20
142
158
4
B 2->22
C 4->54
D 6->62
F 10->114
G 12->126
H 14->142

61.

Key points
◉
◉
◉
◉
◉
◉
◉
Discuss CPU scheduling and its relevance to operating systems;
Illustrate CPU scheduler category
Explain the general goals of CPU scheduling;
Describe the components of CPU scheduler.
Describe the process scheduling circumstances and the context switch.
Discuss classical CPU scheduling algorithms
Master related calculations (CPU utilization, average turnaround time, average
waiting time, average weighted waiting time, Gantt chart )
61

62.

Thanks!
Any questions ?
62

English Русский Rules