[SOLVED] CS flex compiler algorithm ECS 150 Process scheduling

ECS 150 Process scheduling
Prof. Joel Porquet-Lupine
UC Davis 2020/2021
Copyright 2017-2021 Joel 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
, i, &i);
printf(j=%d, &j=%p
, j, &j);
printf(k=%d, &k=%p
, *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-boundCPU-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 conceptsMultitaskingGoal 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 nextCooperativeProcess can hold unto CPU during long CPU burstsOnly yields voluntarily, or during I/O burstsPreemptiveProcess can be forcefully suspended, even during long CPU burstsUse of hardware timer interruptsEnsures guarantee in CPU sharing between multiple processesint 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 lifecycleProcess statesReady Running Blocked ZombieReadyProcess collectedBlocked yield or preemptedelected to runZombieRunningnormal orabnormal terminationProcess created Orphaned processesSpecial scenario if parent’s process terminates before process Depends on whether process is running from terminal or notDelivery of SIGHUP signal or reparenting9 / 19/I/O requestI/O complete ECS 150 – Process schedulingProf. Joel Porquet-LupineUC Davis – 2020/2021Copyright 2017-2021 Joel Porquet-Lupine – CC BY-NC-SA 4.0 International License /10 / 19RecapProcessAddress spaceEach process has it own address spaceEnvironmentMostly represented by OS’ PCBExecution flowSingle sequential execution streamScheduling conceptsShare processor resource among ready processesCPU bursts vs IO burstsCPU-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 preemptedelected to runZombieCooperative vs preemptiveProcess createdReadyProcess collectedRunningnormal orabnormal termination 11 / 19/I/O requestI/O complete Scheduling algorithms VocabularyI/OCPU timelineT1T2 T3Turnaround time Waiting time Response time(s)Submission time Submission time: time at which a process is createdTurnaround time: total time between process submission and completionResponse 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 queue12 / 19/ Scheduling algorithmsFCFS (or FIFO)First-Come, First-ServedMost simple scheduling algorithm (e.g., queue at DMV) Example 1 Task Submission LengthA 0 10 B010 C 0 10 A B C0 20 40 60 80 100 120 Avg turnaround time: 10+20+30 = 200 20 40 60 80 100 120Avg turnaround time: 100+100+110 = 103.33 3 Problem known as convoy effect3 Example 2 A B C Task Submission LengthA 0 100 B010 C 0 1013 / 19/ Scheduling algorithmsSJFShortest Job FirstOptimal scheduling but requires to know task lengths in advanceUse predictions instead (based on past behavior)Example 1 Task Submission Length A0100B010 C 0 10 B C A0 20 40 60 80 100 120 Avg turnaround time: 10+20+120 = 50Example 23Task Submission LengthA 0 100 B1010 C 10 10 A B C0 20 40 60 80 100 120Avg turnaround time: 100+100+110 = 103.33 3 14 / 19/ Scheduling algorithmsPreemptive SJFAlso known as SRTF (Shortest Remaining Time First) New shorter jobs can interrupt longer jobs Example Task Submission LengthA 0 100 B1010 C 10 10 A B C A0 20 40 60 80 100 120 Avg turnaround time: 120+10+20 = 50Can lead to starvation315 / 19/ Scheduling algorithmsTurnaround time vs response timeOptimizing for turnaround time great for (old) batch systemsLength of tasks known (or predicted) in advanceTasks mostly CPU-boundWith interactive systems, need to optimize for response time User wants reactivity Tasks of unknown lengthSJF (again) Task Submission LengthA 0 10 B010 C 0 10 A B C0 10 20 30Avg turnaround time: 10+20+30 = 20Avg response time: 0+10+20 = 10 33 16 / 19/ Scheduling algorithmsRound-robin (RR)Tasks run only for a (short) time slice at a time Relies on preemption (via timer interrupts)Task Submission LengthA 0 10 B010 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.5Avg turnaround time: 25+27.5+30 = 27.5 3 3 CharacteristicsPrevents starvationTime slice duration mattersResponse time vs context switching overhead Poor turnaround time17 / 19/ Scheduling algorithmsMulti-level queue schedulingClassify tasks into categoriesE.g., foreground (interactive) tasks vs background (batch) tasks Give different priority to each categoryE.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 tasks 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 tasks priority if not getting fair share
Used in real OSes
Windows, macOS, Linux (old versions)
PPP
Low priority
Longer time slice
19 / 19
/