CPU Scheduling
1. CPU and I/O Bursts in Program Execution
2. CPU-burst Time Distribution
Stage of executing machine language with CPU
Need for CPU Scheduling
CPU scheduling is needed because various types of jobs (=processes) are mixed
Need to provide appropriate response to interactive jobs
Use system resources like CPU and I/O devices efficiently and evenly
Allow I/O bound jobs to get CPU quickly
Because must give CPU first to use quickly and exit
Need to provide fast responsiveness because interact with people
I/O work happens immediately after using, so if cannot give CPU, not only cannot get CPU but also cannot do I/O
3. Process Characteristic Classification
(1) CPU-bound process
Work that uses CPU for long time and I/O for short time
Cases with much interaction with people (calculation-focused jobs, etc.)
few & very long CPU bursts
(2) I/O-bound process
Work that uses CPU for short time and I/O for long time
Cases where more time is needed for I/O than time holding CPU and calculating (scientific calculations, etc.)
many & short CPU bursts
4. CPU Scheduler & Dispatcher
Software, code inside OS that does CPU scheduling
(1) CPU Scheduler
Role of choosing which process to give CPU to this time among processes in Ready state
(2) Dispatcher
Hands over CPU control to process selected by CPU scheduler
That is, role of actually handing over CPU to decided process
Part of OS and this process is called context switch
(3) Cases where CPU Scheduling is Needed
When process has state changes like below
Running โ Blocked (e.g. system call requesting I/O)
Running โ Ready (e.g. timer interrupt due to allocation time expiration)
Blocked โ Ready (e.g. interrupt after I/O completion)
Terminate
Scheduling in 1, 4 is nonpreemptive (= don't forcibly take away, voluntary return)
Other scheduling is preemptive (= forcibly take away because others must use CPU alternately according to policy)
5. Scheduling Criteria
Performance Index (= Performance Measure)
Easy to understand if compared to Chinese restaurant chef
(1) CPU Utilization
keep the CPU as busy as possible
Don't let CPU idle, higher utilization is better
(2) Throughput
number of processes that complete their execution per time unit
Higher throughput is better
e.g. Better for Chinese restaurant chef to process many dishes
(3) Turnaround Time
amount of time to execute a particular process
Total time from doing CPU burst to going out to do I/O burst
Time waited for CPU in Ready Queue + time actually used CPU
e.g. Time eating + waiting time all combined
(4) Waiting Time
amount of time a process has been waiting in the ready queue
Not time waiting first time, but sum of total time waited after coming to use CPU
e.g. Time waited at Chinese restaurant.. sum of time each dish comes out: pickled radish โ jjajangmyeon โ tangsuyuk โ dessert
(5) Response Time
amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)
Time taken from entering to use CPU until first getting CPU
Note that it's not time from when process first started to first getting CPU. That is, among multiple bursts entering to use CPU, time taken from entering CPU burst to first getting CPU
e.g. Time taken to first receive pickled radish at Chinese restaurant
6. Scheduling Algorithms
(1) FCFS (First-Come First-Served)
Much better than previous case
Example
Features
Both cases processed first-come-first-served so seem no difference, but when averaging, reduced significantly
Why? Because if process with long CPU usage time comes first, waiting time of all processes becomes long โ Convoy effect
Convoy effect
short process behind long process
Process that takes long time arrives first and uses CPU for long time, so short process takes long time
(2) SJF (Shortest-Job-First)
Example
Features
Use each process's next CPU burst time for scheduling
Schedule process with shortest CPU burst time first
From waiting time perspective, most optimal method. Cannot make average waiting time shorter than this
SJF is optimal
Short average waiting time and guarantees minimum average waiting time
Preemptive SJF == also called SRTF (Shortest-Remaining-Time-First)
Optimal method from waiting time perspective
Allocate CPU to process with High Priority
SJF is kind of Priority Scheduling
Priority = predicted next CPU burst time
Two schemes
Nonpreemptive
Once get CPU, not preempted until this CPU burst completes
Even if shorter process appears suddenly, if already gave CPU, don't take away until that process uses it all
Preemptive
CPU is taken away when new process with shorter CPU burst time than remaining burst time of currently executing process arrives
More optimized method than Nonpreemptive
(3) SJF Disadvantages
Starvation occurs
SJF only thinks about efficiency too much, because gives priority to short processes
If queue keeps building up, long job may never get CPU
Prediction of Next CPU Burst Time
Don't tell who uses short and who uses long
Cannot know in advance when entering CPU queue
That is, because program doesn't proceed sequentially but situations differ each time like if statements
Then how can we know next CPU burst time?
If cannot know CPU burst, can estimate based on past CPU burst time
7. Priority Scheduling
A priority number (integer) is associated with each process
Features
Allocate CPU to process with highest priority (smallest integer)
preemptive: take away and give if priority is higher
nonpreemptive: don't take away, wait
SJF is kind of priority scheduling
Problems
Starvation: low priority processes may never execute
Solutions
Aging: as time progresses increase the priority of the process
Concept like seniority
8. Round Robin
Features
Each process has same size allocation time (time quantum)
When allocation time passes, process is preempted and goes to back of ready queue to line up again
If n processes are in ready queue and allocation time is q time units, each process gets 1/n of CPU time in maximum q time unit units
That is, no process waits more than (n-1) q time units
Performance
If allocation time is too long โ FCFS
If allocation time is too short โ context switch occurs too frequently
9. Multilevel Queue
Divide ready queue into multiple
(1) Divide ready queue into multiple
foreground: interactive
background: batch - no human interaction
(2) Each queue has independent scheduling algorithm
foreground: Round Robin
background: FCFS (long process executes continuously without context switch)
Need scheduling for Queue (giving wait to each queue)
(3) Fixed priority scheduling
serve all from foreground then from background
possibility of starvation
(4) Time slice
Allocate CPU time to each queue in appropriate ratio
e.g. 80% to foreground in RR, 20% to background in FCFS
Give priority to foreground but not unconditionally, give time weight to each queue
10. Multilevel Feedback Queue
(1) Features
Movement between queues is possible
Once decided queue doesn't change
Process can move to different queue
Higher queue has higher priority
Lower queue fills only when higher queue is empty
Can implement aging in this way
(2) Parameters defining Multilevel Feedback Queue Scheduler
Number of queues
Scheduling algorithm of each queue
Criteria for sending process to higher queue
Criteria for sending process to lower queue
Criteria for deciding which queue process enters when trying to receive CPU service
11. Example of Multilevel Feedback Queue
(1) Three queues
Q0 - time quantum 8 milliseconds
Q1 - time quantum 16 milliseconds
Q2 - FCFS
(2) Scheduling
new job enters queue Q0
If cannot finish within 8ms, goes down to queue Q1
Lines up in Q1 and waits, then gets CPU and executes for 16ms
If cannot finish within 16ms, gets evicted to queue Q2
12. Multiple-Processor Scheduling
When there are multiple CPUs, scheduling becomes more complex
(1) In case of Homogeneous processor
Can line up in one queue and let each processor take out by itself
If there are processes that must execute on specific processor, problem becomes more complex
(2) Load Sharing
Need mechanism to appropriately share load so jobs don't crowd on some processors
Method of having separate queues vs. method of using common queue
(3) Symmetric Multiprocessing (SMP)
Each processor decides scheduling by itself
(4) Asymmetric Multiprocessing
One processor is responsible for access and sharing of system data, others follow it
13. CPU Scheduling in Special Cases
(1) Load Balancing
Basically Load Balancing when there are multiple CPUs
Important for multiple CPUs to work evenly with balance
Otherwise overall performance drops
(2) SMP (Symmetric Multiprocessing)
Not one master CPU but multiple CPUs are equal
Therefore each processor decides scheduling by itself
(3) ASMP (Asymmetric Multiprocessing)
Method supplementing inefficient aspects of SMP
One CPU becomes master CPU responsible for data access and sharing, other CPUs follow it
14. Real-Time Scheduling
(1) Hard real-time systems
Must schedule to finish within fixed time
For this, sometimes know each process's CPU arrival time in advance and schedule so system follows โ Offline Scheduling
Must leave CPU considering how much load each task has
(2) Soft real-time computing
Must have higher priority compared to general processes
Good to guarantee deadline but expensive so mix with general processes
e.g. Increase priority of video playback process so it can get CPU first to prevent video from cutting off
15. Thread Scheduling
(1) Thread
Smallest execution unit running within process
Each thread shares memory and resources with other processes running in same one process
This structure facilitates communication between processes and enables efficient use of resources
(2) Local Scheduling
OS doesn't know thread's existence, user process itself has multiple threads inside so OS cannot make decision of which program to give CPU to
Instead, user-level thread library (User level thread) is responsible for scheduling between threads
These threads are managed at user level so can switch quickly without kernel intervention, but if one thread blocks, entire process can block
(3) Global Scheduling
Global scheduling occurs at kernel level, where OS can know thread's existence, and kernel scheduler decides which thread to execute
This is possible because each thread is managed as separate kernel object
That is, kernel's short-term scheduler decides which thread to schedule
This method is efficient in multiprocessor systems but may cost more for context switch than user-level threads
(4) Why Global Scheduling is Efficient in Multiprocessor Systems
In multiprocessor systems, multiple CPU cores work simultaneously, and in this environment global scheduling provides following benefits
a. Flexibility in Resource Distribution
In global scheduling, kernel recognizes and manages all threads. This provides flexibility to allocate system's threads to various processor cores. Therefore, can maximize overall system performance by evenly distributing workload to multiple cores.
b. Efficient Load Balancing
In multiprocessor systems, can monitor each processor's load and move threads to other processors to evenly distribute load. This plays important role in improving system efficiency through load balancing.
c. Optimization of Parallel Processing
In multiprocessor systems, multiple threads can execute simultaneously. Can optimize such parallel processing through global scheduling, which is especially important in work with much parallel computation.
d. Deadlock and Starvation State Management
In multiprocessor environment, Deadlock and Starvation states increase complexity of process and thread management. Global scheduling provides overall perspective needed to manage and solve such problems.
e. Maintaining Synchronization and Consistency
In multiprocessor environment, synchronization of data and resources is important challenge. Through global scheduling, can maintain data consistency and effectively manage conflicts that may occur when accessing resources.
16. Algorithm Evaluation
Criteria for evaluating which CPU scheduling algorithm is good
(1) Queueing models
Calculate various performance index values through arrival rate and service rate given by probability distribution
If requests pile up in queue when server processes requests, server processes, if not, remain in queue
Requests wanting to use CPU arrive in queue, how fast frequency they arrive โ this arrival rate is given by probability distribution
CPU's performance or capability is called 'processing rate'
After calculating complex formulas, Throughput and Waiting Time are derived
(2) Implementation and Measurement
Implement algorithm in actual system and measure and compare performance for actual workload
(3) Simulation
Write algorithm as simulation program then compare results using trace as input
Trace means data that becomes Input, must be credible enough to be similar to or represent pattern of programs running in actual system
Last updated