Aircraft systems
Posted by and classified in Computers
Written at on 
English with a size of 10.6 KB.
New jobs are admitted into the system
-- long-term or high-level scheduling
Once in the system, processes go through a number of state changes
-- short-term or low-level or CPU scheduling
A process is a "running program" or "program in execution"
Processes have a variety of states:
RUNNING READY WAITING (on I/O)
STATE STATE STATE
+-----+ +-----------------------+
| | +--------------------+ | P2 P8 |
| CPU | <== |="" p3="" |="" p6="" |="" p5="" |="" ...="">==><== i/o="" subsystem="" p13="" |="" |="" p11="" |="" +--------------------+="" |="" |="" +-----+="" +-----------------------+="" (a="" cpu="" burst="" is="" a="" set="" of="" assembly="" instructions="" that="" are="" executed="" by="" the="" cpu="" for="" a="" given="" process)="" (an="" i/o="" burst="" is="" one="" or="" more="" i/o="" operations="" for="" a="" given="" process)="" running="" state:="" process="" is="" actually="" using="" the="" cpu="" (i.E.,="" executing="" its="" instructions)="" ready="" state:="" process="" is="" ready="" to="" use="" the="" cpu="" (idle="" in="" the="" ready="" queue)="" waiting="" state:="" process="" is="" waiting="" for="" i/o="" operation(s)="" to="" complete="="> multiclass-system.Png
CPU Scheduling (a.K.A. Short-Term Scheduling)
-- The scheduling system enables one process to use the CPU
While other processes are waiting in the ready queue to use
The CPU (or waiting in the I/O subsystem)
-- The goals of CPU scheduling are to make efficient use of the CPU
And to minimize the turnaround and wait times for each running process
-- We also want to achieve "fairness" among all processes
-- The task of the CPU scheduler is, when the CPU becomes free,
To select the next process from the ready queue
(more specifically, maintain the ready queue in a specific process order)
-- CPU Scheduling Algorithms:
First Come First Served (FCFS)
Shortest Job First (SJF)
Shortest Remaining Time (SRT)
Priority Scheduling
Round Robin (RR)
-- Preemption occurs when the currently running process is
Preempted (i.E., "kicked out" or replaced) from using the CPU
-- might be because of a newly arriving (more important) process
-- might be because of a timeout (i.E., the RR algorithm)
Processes in a multiprogramming system COMPETE for the CPU
(but they also often need to COOPERATE with one another via IPC)
Whenever we switch a process out of the CPU and bring the next process
In to use the CPU, we have a CONTEXT SWITCH
-- the state of the currently running process is saved in
A process control block (PCB), which includes registers,
Program counter, page table, memory maps, etc.
-- the state of the next (or replacement) process is loaded from its PCB
OVERHEAD!!!!!!
Other challenges of CPU scheduling include:
-- Processes alternate bursts of CPU time and I/O time;
How do we best handle the process mix?
+---------+ blocked +--------------------------+ +--------------+
P1 |CPU burst|---------| CPU burst |--| CPU burst |-->
+---------+ on I/O +--------------------------+ +--------------+
+---+ blocked on I/O +-----+
P2 |CPU|-----------------------------------------| CPU |--------------->
+---+ +-----+
P1 is a CPU-bound or compute-bound process;
P2 is an I/O-bound or interactive process
We can model this as follows:
-- Consider CPU usage from a probabilistic viewpoint
-- Suppose processes spend fraction p of their time
Waiting for I/O to complete
-- Given n processes in memory (i.E., the degree of multiprogramming is n),
Then the probability that all n processes are waiting for I/O is:
N
P
N
-- CPU utilization is then: 1 - p
-- Scheduling decisions:
-- When does the OS make a scheduling decision?
-- fork() -- how do we schedule a new child process?
-- process termination
-- process blocks on I/O (or enters a waiting/suspended state)
-- I/O interrupt (the process re-enters the ready queue or maybe
Causes a preemption)
-- Which process does the OS select next?
-- The above depends on the types of processes
-- batch: no users are waiting (lower priority --- non-preemptive)
-- interactive: users are waiting for a (quick) response; also
Servers serving up file/webpages/etc. (higher priority --- preemptive)
-- real-time: preemption not usually necessary because processes
Already are designed to "know" that they need to run quickly
All types of processes:
-- fairness
-- balance
Batch systems:
-- Throughput --- maximize the number of jobs completed per unit time
-- Turnaround time --- minimize time between arrival and completion
-- CPU utilization --- keep CPU as busy as possible
Interactive systems:
-- Response time -- respond to user requests quickly
For each CPU burst per each process:
WAIT TIME: How much time does a process spend in the ready queue
Waiting for time with the CPU?
TURNAROUND TIME: How much time is required for a process to complete
Its CPU burst, from the time it enters the ready queue
Through to when it completes its CPU burst
TURNAROUND TIME = WAIT TIME + CPU BURST TIME
TURNAROUND TIME = WAIT TIME + CPU BURST TIME + OVERHEAD
(context switches)
First Come First Served (FCFS)
Pid CPU burst times (assume that all processes arrive at time 0)
P1 18 ms
P2 3 ms
P3 4 ms
Ready queue is ordered: P1 P2 P3
Context switch context switches
V v v v
+--------------------+---+----+--------------->
FCFS: | P1 |P2 | P3 | ...........
+--------------------+---+----+--------------->
T: 0 18 21 25
P1 has 0 wait time P1 has 18 ms turnaround time
P2 has 18 ms wait time P2 has 21 ms turnaround time
P3 has 21 ms wait time P3 has 25 ms turnaround time
Advantages: very simple; easy to implement; very low overhead
Disadvantages: processes with larger CPU burst times will likely cause
Long delays for other (shorter) processes
Shortest Job First (SJF)
Pid CPU burst times (assume that all processes arrive at time 0)
P1 18 ms
P2 3 ms
P3 4 ms
Ready queue is ordered: P2 P3 P1 (priority queue)
Context switches context switch
V v v v
+---+----+--------------------+--------------->
SJF: |P2 | P3 | P1 | ........
+---+----+--------------------+--------------->
T: 0 3 7 25
P1 has 7 ms wait time P1 has 25 ms turnaround time
P2 has 0 wait time P2 has 3 ms turnaround time
P3 has 3 ms wait time P3 has 7 ms turnaround time
Advantages: lower average wait/turnaround times (versus FCFS)
Good low turnaround times for interactive or I/O-bound processes
Disadvantages: processes with larger CPU burst times might end up
Facing INDEFINITE BLOCKING or STARVATION
Higher overhead versus FCFS due to the priority queue
Irl we have no way of knowing ahead of time exactly what
The CPU burst times will be for each process.....
.......But we can predict the CPU burst times
Both FCFS and SJF are non-preemptive algorithms
-- once a process starts using the CPU for its CPU burst,
It will continue uninterrupted until the burst is complete
-- what if we added preemption to SJF?
-- i.E., when new process B arrives, it can potentially preempt
(replace) the currently running process A if B's CPU burst time
Is less than the remaining burst time for process A
Shortest Remaining Time (SRT)
-- SJF with preemption
Pid CPU burst times arrival times
P1 18 ms 0 ms
P2 3 ms 2 ms
P3 4 ms 3 ms
P4 3 ms 5 ms
TO DO: draw the diagram for these processes and calculate
The turnaround/wait times for each
Ready queue: P1
Context switches
V v v v v v
+--+---+---+----+----------------------+------>
SRT: |P1pP2 |P4 | P3 | P1 | ...
+--+---+---+----+----------------------+------>
T: 0 2 5 8 12 28
P1 has wait time of 10 ms and turnaround time is 28 ms
(the wait time is the sum of all time spent in the ready queue
During the end-to-end turnaround time for each process)
To do: calculate the rest of the wait/turnaround times
Advantages: similar to SJF;
Better at getting I/O-bound/interactive processes
Through the CPU more quickly?
Disadvantages: processes with larger CPU burst times might end up
Facing INDEFINITE BLOCKING or STARVATION
Higher overhead versus FCFS due to the priority queue;
Also more context switches are likely
Irl we have no way of knowing ahead of time exactly what
The CPU burst times will be for each process.....
.......But we can predict the CPU burst times
Priority scheduling
-- Each process is assigned a priority based on:
-- CPU burst times (e.G., SJF/SRT) <===== estimated/predicted...="" --="" ratio="" of="" cpu="" to="" i/o="" activity="" (predicted/expected)="" --="" system="" resource="" usage="" --="" arbitrary="" or="" hard-coded="" --="" the="" process="" with="" the="" highest="" priority="" gets="" scheduled="" with="" the="" cpu="" first="" --="" when="" multiple="" processes="" have="" the="" same="" priority,="" we="" need="" a="" tie-breaker,="" which="" is="" a="" secondary="" algorithm="" on="" that="" subset="" (e.G.,="" just="" use="" fcfs)="" --="" we="" decide="" (ahead="" of="" time)="" whether="" the="" algorithm="" is="" preemptive="" or="" not="" --="" to="" help="" avoid="" starvation="" or="" indefinite="" blocking,="" we="" can="" use="" aging:="" --="" if="" a="" given="" process="" is="" in="" the="" ready="" state="" (i.E.,="" in="" the="" ready="" queue)="" for="" some="" x="" amount="" of="" time,="" then="" we="" increase="" the="" priority="" of="" that="" process="" by="" y="">=====>==>