ECS 150 – Process scheduling
Prof. Joël Porquet-Lupine
UC Davis – 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine – CC BY-NC-SA 4.0 International License /
1 / 19
Process
Definition (recap)
A process is the abstraction used by the OS to execute programs
Comprehensive set of features
Protection against other processes Isolation from OS/kernel
Intuitive and easy-to-use interface (syscalls) Portable, hides implementation details Can be instantiated many times
Efficient and reasonable easy to implement
Characteristics
1. Address space 2. Environment 3. Execution flow
PCB
User Kernel
Process
PID=1
state ctxt files …
2 / 19
/
Process
Address space
Each process has its own address space
int i = 1;
int main(void)
{
int j = 10;
int *k = malloc(sizeof(int));
*k = 4;
if (fork()) { i = i + 1; j = j – 1;
*k = *k * 1; } else {
i = i + 2;
j = j – 2;
*k = *k * 2;
}
printf(“i=%d, &i=%p\n”, i, &i);
printf(“j=%d, &j=%p\n”, j, &j);
printf(“k=%d, &k=%p\n”, *k, &k);
return 0; }
address_space.c
$ ./address_space
i=2, &i=0x5634b1f6f048 j=9, &j=0x7ffc70ffaaec k=4, &k=0x7ffc70ffaaf0 i=3, &i=0x5634b1f6f048 j=8, &j=0x7ffc70ffaaec k=8, &k=0x7ffc70ffaaf0
3 / 19
/
Process
Environment
Contained in PCB
Defines all the specific characteristics of a process
Process ID, Process group ID User ID, Group ID
Link to parent process
List of memory segments
text, data, stack, heap Open file tables
Working directory Process state Scheduling parameters Space for saved context
PC, SP, general-purpose registers Etc.
PCB
User Kernel
Process
PID=1
state ctxt files …
4 / 19
/
Process
Execution flow
Single sequential execution stream
Statements executed in order
Can only be at one location in the code at a time Can only be (slightly) disrupted by signals
Process
Run main() function
Run signal handler
Continue running from main() function
Load process
Acknowledge timer Signal pending
Resume process
void sig_hndl(int signo)
{
statement#1;
statement#2;
statement#3;
…
statement#N;
}
int main(void)
{
statement#1;
statement#2;
statement#3;
statement#4;
statement#5;
…
statement#N;
}
Dispatch (first entry)
Timer interrupt
Dispatch (signal handler)
Return from signal handler
Dispatch (resume)
Kernel
5 / 19
/
Scheduling concepts
Definition
Single-processor systems only allow one process to run at a time Scheduler in charge of determining which process should run
Ready queue contains all processes ready to run
Ready queue
PPP
Blocked queue
PPP
Running
P
Processor
I/O completed
Completed
Block on I/O
6 / 19
/
Scheduling concepts
CPU-I/O burst cycles
int main(void) { int fd;
int i;
char buf[256];
fd = open(“input.txt”, O_RDONLY); read(fd, buf, sizeof(buf)); close(fd);
for (i = 0; i < sizeof(buf); i++) { if (isupper(buf[i]))
/* I/O burst */
/* CPU burst */
/* I/O burst */
}
buf[i] = tolower(buf[i]);
fd = open("output.txt", O_RDONLY); write(fd, buf, sizeof(buf)); close(fd);
return 0; }
CPU-bound vs I/O-bound
CPU-bound processes (e.g., scientific calculations) I/O-bound processes (e.g., BitTorrent)
Mix CPU-I/O-bound processes (e.g., compiler)
7 / 19
/
Scheduling concepts
Multitasking
Goal of maximizing CPU utilization among multiple processes When process is performing I/O burst, give CPU to next process Scheduling policy determines which process is next
Cooperative
Process can hold unto CPU during long CPU bursts
Only yields voluntarily, or during I/O bursts
Preemptive
Process can be forcefully suspended, even during long CPU bursts
Use of hardware timer interrupts
Ensures guarantee in CPU sharing between multiple processes
int main(void)
{
for () { /* CPU burst */
... }
sched_yield(); /* Yield CPU */
scanf(); /* I/O burst */
... }
int main(void)
{
... }
scanf();
... }
for () {
/* CPU burst */
/* I/O burst */
8 / 19
/
Scheduling concepts
Process lifecycle
Process states
Ready Running Blocked Zombie
Ready
Process collected
Blocked yield or preempted
elected to run
Zombie
Running
normal or
abnormal termination
Process created
Orphaned processes
Special scenario if parent's process terminates before process Depends on whether process is running from terminal or not
Delivery of SIGHUP signal or reparenting
9 / 19
/
I/O request
I/O complete
ECS 150 - Process scheduling
Prof. Joël Porquet-Lupine
UC Davis - 2020/2021
Copyright © 2017-2021 Joël Porquet-Lupine - CC BY-NC-SA 4.0 International License /
10 / 19
Recap
Process
Address space
Each process has it own address space
Environment
Mostly represented by OS' PCB
Execution flow
Single sequential execution stream
Scheduling concepts
Share processor resource among ready processes
CPU bursts vs IO bursts
CPU-bound vs IO-bound processes
/* I/O burst */
fd = open("input.txt", O_RDONLY); read(fd, buf, sizeof(buf)); close(fd);
/* CPU burst */
for (i = 0; i < sizeof(buf); i++) { if (isupper(buf[i]))
}
buf[i] = tolower(buf[i]);
Process lifecycle
Blocked yield or preempted
elected to run
Zombie
Cooperative vs preemptive
Process created
Ready
Process collected
Running
normal or
abnormal termination
11 / 19
/
I/O request
I/O complete
Scheduling algorithms
Vocabulary
I/O
CPU timeline
T1T2 T3
Turnaround time
Waiting time
Response time(s)
Submission time
Submission time: time at which a process is created
Turnaround time: total time between process submission and completion
Response time: time between process submission and first execution or first response (e.g., screen output, or input from user)
Waiting time: total time spent in the ready queue
12 / 19
/
Scheduling algorithms
FCFS (or FIFO)
First-Come, First-Served
Most simple scheduling algorithm (e.g., queue at DMV)
Example 1
Task
Submission
Length
A
0
10
B
0
10
C
0
10
A
B
C
0 20 40 60 80 100 120 Avg turnaround time: 10+20+30 = 20
0 20 40 60 80 100 120
Avg turnaround time: 100+100+110 = 103.33 3 Problem known as convoy effect
3
Example 2
A
B
C
Task
Submission
Length
A
0
100
B
0
10
C
0
10
13 / 19
/
Scheduling algorithms
SJF
Shortest Job First
Optimal scheduling but requires to know task lengths in advance
Use predictions instead (based on past behavior)
Example 1
Task
Submission
Length
A
0
100
B
0
10
C
0
10
B
C
A
0 20 40 60 80 100 120 Avg turnaround time: 10+20+120 = 50
Example 2
3
Task
Submission
Length
A
0
100
B
10
10
C
10
10
A
B
C
0 20 40 60 80 100 120
Avg turnaround time: 100+100+110 = 103.33 3
14 / 19
/
Scheduling algorithms
Preemptive SJF
Also known as SRTF (Shortest Remaining Time First) New shorter jobs can interrupt longer jobs
Example
Task
Submission
Length
A
0
100
B
10
10
C
10
10
A
B
C
A
0 20 40 60 80 100 120 Avg turnaround time: 120+10+20 = 50
Can lead to starvation
3
15 / 19
/
Scheduling algorithms
Turnaround time vs response time
Optimizing for turnaround time great for (old) batch systems
Length of tasks known (or predicted) in advance
Tasks mostly CPU-bound
With interactive systems, need to optimize for response time
User wants reactivity Tasks of unknown length
SJF (again)
Task
Submission
Length
A
0
10
B
0
10
C
0
10
A
B
C
0 10 20 30
Avg turnaround time: 10+20+30 = 20
Avg response time: 0+10+20 = 10 3
3
16 / 19
/
Scheduling algorithms
Round-robin (RR)
Tasks run only for a (short) time slice at a time Relies on preemption (via timer interrupts)
Task
Submission
Length
A
0
10
B
0
10
C
0
10
A
B
C
A
B
C
A
B
C
A
B
C
0 10 20 30 Avg response time: 0+2.5+5 = 2.5
Avg turnaround time: 25+27.5+30 = 27.5 3
3
Characteristics
Prevents starvation
Time slice duration matters
Response time vs context switching overhead Poor turnaround time
17 / 19
/
Scheduling algorithms
Multi-level queue scheduling
Classify tasks into categories
E.g., foreground (interactive) tasks vs background (batch) tasks Give different priority to each category
E.g., Interactive > batch
Schedule each categorize differently
E.g., optimize for response time or turnaround time
High priority
System processes
P P P FCFS Interactive processes
RR
SJF
Characteristics
Adapt to each task’s type
More flexible than strict FCFS, SJF, or RR algorithm
Potential starvation issues
PPP
Low priority
PPP
Batch processes
18 / 19
/
Scheduling algorithms
Multi-level feedback queue
No predetermined classification
All process start from highest priority
Dynamic change based on actual behavior
CPU-bound processes move to lower priorities
I/O-bound processes stay at or move up to higher priorities
High priority
New task
Shorter time slice
P P P
Time slice expiration
PPP
Characteristics
Responsiveness Low overhead Prevents starvation
Increase task’s priority if not getting fair share
Used in real OSes
Windows, macOS, Linux (old versions)
PPP
Low priority
Longer time slice
19 / 19
/