Transcript Here - SIUE Computer Science - Southern Illinois University

CS 314 Operating Systems
Uniprocessor Process Management &
Process Scheduling
Department of Computer Science
Southern Illinois University Edwardsville
Spring, 2016
Dr. Hiroshi Fujinoki
E-mail: [email protected]
Process_Management/000
CS 314 Operating Systems
Three Different Layers of Process Scheduling
 Long-term Scheduling
• The scheduler invoked when a new process is started
by a human user or by another process already active
 Short-term Scheduling
• The scheduler that assigns a (the) processor to the processes
ready to run in the memory
 Medium-term Scheduling
• The scheduler that is performed to the ready processes to temporarily
swap them out of the memory (to make them temporarily inactive)
Process_Management/001
CS 314 Operating Systems
Long-Term Scheduling
Computer System
Processor
User(s)
Your program must be in
memory for the processor
to execute it
Multitasking requires
multiple processes
ready (waiting) in the
memory
Main Memory
Two reasons your request to start a new process can be rejected:
 Your system does not have enough memory
to hold more process (not enough memory)
Process_Management/002
CS 314 Operating Systems
Long-Term Scheduling
Computer System
Long-term
Schedule Queue
User(s)
Processor
Your program must be in
memory for the processor
to execute it
Multitasking requires
multiple processes
ready (waiting) in the
memory
Main Memory
Two reasons your request to start a new process can be rejected:
 Your system does not have enough memory
to hold more process (not enough memory)
Process_Management/003
CS 314 Operating Systems
Long-Term Scheduling
Computer System
Processor
Process
Completed
User(s)
Main Memory
Two reasons your request to start a new process can be rejected:
 Your system does not have enough memory
to hold more process
Process_Management/004
CS 314 Operating Systems
Long-Term Scheduling
Computer System
Processor
User(s)
Main Memory
Two reasons your request to start a new process can be rejected:
 Degree of multitasking exceeds its limit and thrashing
is happening (not enough processor resource)
Process_Management/005
CS 314 Operating Systems
Long-Term Scheduling
Long-term
Scheduling
Computer System
Processor
User(s)
Process_Management/006
Main Memory
CS 314 Operating Systems
Degree of Multitasking and Thrashing
7
Process 1
Process 2
5
Process 3
10
5
3 3
2 4
10
5
5
n
Processor is used for
n seconds
m
Processor is NOT used
for m seconds
2 3
This is “short-term scheduling”
Process 1
7
10
5
Process 2
2 3
2
Process 3
Process 4
5
5
1 3 1
3
5
Utilization = 17/32 = 53.1%
2
Utilization = 29/34 = 85.2%
5
2 3
Number of processes ready in the memory
= “Degree of multitasking”
Process_Management/007
Utilization = 42/44 = 95.5%
CS 314 Operating Systems
 Multiprogramming and Timesharing OS
Multiprogramming & Timesharing
User Programs
A
Computer System
B
CPU
C
D
E
D
Program Loader
Process_Management/008
user
user
C
B
A
Memory
user
user
CS 314 Operating Systems
Degree of Multitasking and Thrashing
Service time
(Time Slice)
user
user
user
user
user
user
Process_Management/009
Context Switching
• All registers in the
processor must be
saved
CS 314 Operating Systems
Degree of Multitasking and Thrashing

user
Overhead for Context Switching

user
user
user
user
user
Process_Management/010

If we try to keep the response time
for each user same, the service time
(time slice) for each user must shrink



CS 314 Operating Systems
Degree of Multitasking and Thrashing
Thrashing = A situation where most
of the processor cycles are used for
just switching between processes but
not for processing them
Throughput
Long-term scheduling controls
degree of multitasking so that
thrashing will not happen
Thrashing
Degree of Multitasking
Process_Management/011
(High)
CS 314 Operating Systems
Three Different Layers of Process Scheduling
New
System has enough
resources
user
System does not have
enough resources
Blocked
Ready
Selected for
execution
Processor
System has enough
resources
I/O access is
completed
Another process is
selected for execution
Blocked
Running
Process is making
I/O accesses
Completed
Process_Management/012
CS 314 Operating Systems
Three Different Layers of Process Scheduling
Short-term Scheduling
New
user
Ready
Blocked
Processor
Running
System does not have
enough resources
Blocked
Long-term Scheduling
Completed
Medium-term Scheduling
Process_Management/013
CS 314 Operating Systems
Short-term Scheduling
Major existing short-term scheduling algorithms:
 FCFS (a.k.a. “FIFO”)
 Round-Robin
 SJF (a.k.a. “SPN”)

 Preemptive
Non-Preemptive
 SRTF (Shortest Remaining Time First)
 HRRN (Highest Response Rate Next)
 Feed-back
Process_Management/014

Priority-based
(Highest Priority First)
CS 314 Operating Systems
Short-term Scheduling
• The scheduler schedules assignments of the processor to each process to
optimize some performance factor(s)
 Throughput
 Response time
 Resource utilization (especially processor utilization)
 Turnaround time
 Fairness (we can measure this as “customer satisfaction”)
Each short-term scheduling algorithm is good at optimizing
a performance factor, but it is hard to optimize all the factors
Process_Management/015
CS 314 Operating Systems
Uniprocessor Process Management
• Core of process management
Process scheduling
• Process scheduling = Decision-making for when to start (and stop) processes
• Why is process scheduling important?
Because it has significant impact to the following performance factors:
 Throughput
 Response time
 Resource utilization (especially processor utilization)
 Turnaround time
 Fairness (we can measure this as “customer satisfaction”)
Process_Management/016
CS 314 Operating Systems
Throughput
Throughput = Number of jobs completed in unit time
9
25
P14
P1
9
P4
4
P2
9
4
P7
P3
9
15
15
P5
4
4
P8
P10
4
P9
9
15
P6
25
4 4
9
15
4
P1
P2 P3 P4
P5
P6 P7 P8 P9
42
57 61
9
4 4
70 74 78
5 jobs / Minute
Process_Management/017
P12
P13
If all tasks
submitted
here
25 29 33
P11
15
9
P10
P11 P12
93
9
102 111
15
9
P13
P14
126
135
6 jobs / Minute
CS 314 Operating Systems
Response Time Response Time
Two questions:
 How
“average
response
=The time since submission
untilshould
the first
response
appears
time”
be defined?
9
25
P14
P1 can we improve “average
 How
9
response time (two methods)”?
9
P4
4
P2
4
P7
P3
15
4
P8
P10
4
P9
If all tasks
submitted
here
9
15
P6
P12
P13
25
4 4
9
15
4
P1
P2 P3 P 4
P5
P 6 P7 P8 P9
0
Process_Management/018
P11
15
P5
4
9
25 29 33
P2 waits for 25 sec.
42
57 61
9
4 4
70 74 78
15
9
P10
P11 P12
93
9
102 111
15
9
P13
P14
126
CS 314 Operating Systems
Response Time Response Time
=The time since submission until the first response appears
If all tasks
submitted
here
25
4 4
9
15
4
P1
P2 P3 P4
P5
P6 P7 P8 P9
0
25 29 33
42
57 61
9
4 4
15
9
P10
P11 P12
93
70 74 78
9
102 111
Average Response Time = 901/14 = 64.35
9
9
9
P2 P3 P6 P8 P9 P4
P7
P11 P12 P14
4 4 4 4 4
4 8 12 16 20
29
38
9
47
9
56
65
15
15
15
25
P5
P10
P13
P1
80
95
110
Average Response Time = 580/14 = 41.28
• Average Response Time
Process_Management/019
• What did we loose ?
Optimized 
15
9
P13
P14
126
CS 314 Operating Systems
Resource Utilization (processor utilization)
Process 1
Process 2
Process 3
7
7
10
12
2
10
10
5
5
6
5
3 3
n
Processor is used for
n seconds
m
Processor is NOT used
for m seconds
2 3
5
5
5
12
2
6
3 3
Process 2
Process 1
73
51
Utilization = 51/73 = 69.9%
Process_Management/020
10
2 3
Process 3
CS 314 Operating Systems
Turnaround Time Turnaround Time
= The time since submission to completion for each process
9
25
P14
P1
9
P4
4
P2
9
4
P7
P3
9
15
15
P5
4
P8
If all tasks
submitted
here
4
P10
4
P9
9
15
P6
P12
P13
25
4 4
9
15
4
P1
P2 P3 P 4
P5
P 6 P7 P8 P9
25 29 33
Process_Management/021
P11
42
57 61
9
4 4
70 74 78
15
9
P10
P11 P12
93
9
102 111
15
9
P13
P14
126
135
CS 314 Operating Systems
Fairness
• Reasonable resource allocation to each task (or process)
• Meaning of “fairness” depends on each system
 If some tasks are high-priority tasks
Assigning exactly the same amount of resource to all tasks
Will result in unfairness
 If all the tasks have exactly the same priority
Each task should be assigned the same amount of resource
 If some tasks have lower priority
Assigning more resource to high-priority tasks
Will result in starvation for low-priority tasks
Process_Management/022