CS代考计算机代写 flex compiler algorithm ECS 150 – Process scheduling

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
/