CPU Scheduling Flashcards
What is a CPU - I/O Burst
Process execution consists of a cycle of CPU execution and
I/O wait
- Data transfers from disk to memory
are handled by the system bus. - This means that the processor is available to
process data during disk I/O.
What is a Short-term scheduler?
Selects which process should be executed next and allocates CPU
* Sometimes the only scheduler in a system
* Short-term scheduler is invoked frequently (milliseconds) (must be fast)
What is a Long-term scheduler scheduler?
Long-term scheduler (or job scheduler): selects which processes should be brought into the ready queue
* Long-term scheduler is invoked infrequently (seconds, minutes)
* The long-term scheduler controls the degree of multiprogramming
What are the type of process scheduled
- I/O-bound process: spends more time doing I/O than computations, many short CPU bursts
- CPU-bound process: spends more time doing computations; few very long CPU bursts
What is Medium-Term Scheduling?
- Medium-term scheduler can be added if degree of multiple
programming needs to decrease - Remove process from memory, store on disc, bring back in from disc to continue execution: swapping
What is the dispatcher?
The module that gives control of the CPU to the
process selected by the scheduler. This function involves:
* Switching context.
* Switching to user mode.
* Jumping to the proper location in the newly loaded program.
What CPU short-term scheduling decisions may take place? 4 points
- Switches from running to waiting state
- Switches from running to ready state
- Switches from waiting to ready
- Terminates
Scheduling under 1 and 4 is non-pre-emptive
When can Pre-emptive scheduling cause problems?
When two processes share data, one process may get interrupted in the middle of updating shared data structures
CPU Scheduling Criteria
CPU utilisation: keep the CPU as busy as possible
* Throughput: # of processes that complete their execution per
time unit
* Turnaround time: amount of time to execute a particular process
* Waiting time: amount of time a process has been waiting in the
ready queue
* Response time: amount of time it takes from when a request was
submitted until the first response is produced, not output (for timesharing environment)
Scheduling Algorithm Optimisation Criteria 5 key points
- Max CPU utilisation
- Max throughput
- Min turnaround time
- Min waiting time
- Min response time
Scheduling Criteria (User Orientated) 4 points
- Performance-related
- Turnaround time
- Response time
- Deadlines
Other:
* Predictability
Scheduling Criteria (System-Orientated) 3 points
- Performance-related:
- Throughput
- CPU Utilisation
Other:
* Fairness
* Enforcing priorities
* Balancing resources
Scheduling Algorithms
- FCFS – First Come First Served
- SJF – Shortest Job First
- SRT – Shortest Response Time
- Priority
- HRRN – Highest Response Ratio Next
- RR – Round Robin
- Multi-Level Queue
What is asymmetric multiprocessing?
Only one processor accesses the system
data structures, alleviating the need for data sharing
What is symmetric multiprocessing (SMP)?
Each processor is self-scheduling, all processes in common ready queue
* or Each has its own private queue of ready processes
* Currently, most common
What is Processor affinity?
- Processor affinity – process has affinity for processor on which it is
currently running - soft affinity
- hard affinity
- Variations including processor sets
What is Load balancing?
Load balancing attempts to keep workload evenly distributed
What is Push migration?
Periodic task checks load on each processor,
pushes task from overloaded CPU to other CPUs
What is Pull migration?
Pull migration – idle processors pulls waiting task from busy
processor
Real-time Scheduling Unique requirements with respect to:
- Determinism
- Predictable behaviour guarantees deadlines are met.
- Responsiveness
- Immediate handling of critical events; low latency.
- User control
- Fine-grained control over priorities, task scheduling, and deadlines.
- Reliability
- Fault-tolerant operation with mechanisms to ensure no single point of
failure. - Fail-soft operation
- Graceful degradation under failure conditions, focusing on maintaining core
functionalities and critical tasks.
What is Real-time Scheduling?
Real-time computing is the “type of computing in which the
correctness of the system depends not only on the logical result of
the computation but also on the time at which the results are
produced.”
