Please enable JavaScript.
Coggle requires JavaScript to display documents.
Chapter 5: CPU Scheduling (Scheduler Metrics (CPU Utilization (Percentage…
Chapter 5: CPU Scheduling
Process Scheduling
Definition
The act of determining which process in the ready state should be moved to the running state. That is, decide which process should run on the CPU next
Goal
Implement the virtual machine in such a way the user perceives that each process is running on it’s own computer
Bound Process Type
I/O
Waiting for the completion of input or output (I/O) are I/O Bound
CPU
Implementing algorithms with a large number of calculations
Type of Scheduler
Non-preemptive scheduling
Currently executing process gives up the CPU voluntarily
Preemptive scheduling
OS decides to favor another process, preempting the currently executing process
Components of Scheduler
Enqueuer
Adds a pointer or reference to the process’ PCB as per the desired data structure of the ready queue
Dispatcher
Implements the scheduling algorithm to pick the next process to run
Context Switcher
Loads the selected process onto the CPU as the running process
Scheduler Metrics
CPU Utilization
Percentage of time that the CPU is busy
Throughput
Number of processes that are completed per time unit
Waiting time
Sum of the time spent in the ready queue during the life of the process
service time
Amount of CPU time that a process will need before it either finishes or voluntarily exits the CPU
Turnaround time
Amount of time between the time a process arrives in the ready state to the time it exits the running state for the last time
response time
Time from first submission of the process until the first running
Scheduling Algorithms
First-Come , First-Served (FCFS)
Jobs are executed on first come, first serve basis
non-preemptive
Easy to understand and implement
Poor in performance as average wait time is high
Shortest Job Next (SJN)
A.k.a shortest job first (SJF)
non-preemptive
Minimize waiting time
Easy to implement in Batch systems where required CPU time is known in advance
The CPU should know in advance how much time process will take
Priority Based Scheduling
non-preemptive
Each process is assigned a priority. Process with highest priority is to be executed first and so on
Processes with same priority are executed on first come first served basis
Shortest Remaining Time (SRT)
preemptive version of the SJN algorithm
The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion
Round Robin Scheduling
preemptive process
Each process is provided a fix time to execute, it is called a quantum
Context switching is used to save states of preempted processes
Once a process is executed for a given time period, it is preempted and other process executes for a given time period
Multiple-Processor Scheduling
The scheduler has to decide which process to run and which central processing unit to run
Approaches
Asymmetric
simple and reduces the need of data sharing
Scheduling decisions and I/O processing are handled by Master Server and the other processors executes only the user code
Symmetric
each processor is self scheduling
All processes may be in a common ready queue or each processor may have its own private queue for ready processes
Processor Affinity
A processes has an affinity for the processor on which it is currently running
Types
Soft Affinity
When OS has a policy of attempting to keep a process running on the same processor but not guaranteeing it will do so
Hard Affinity
allows a process to migrate between processors
Load Balancing
workload is evenly distributed across all processors in an SMP system
Approaches
Push Migration
A task routinely checks the load on each processor and if it finds an imbalance then it evenly distributes load on each processors by moving the processes from overloaded to idle or less busy processors
Pull Migration
occurs when an idle processor pulls a waiting task from a busy processor for its execution
Real-Time Scheduling
Type of latency
Interrupt
Time from arrival of interrupt to start of routine that services interrupt
Dispatch
Time for schedule to take current process off CPU and switch to another
Event latency
The amount of time that elapses from when an event occurs to when it is serviced