Scheduling Flashcards
Why is scheduling relevant to the OS?
Kernel decides which process gets to run
What is the job of the scheduler?
Maximise utilisation of the CPU by swapping processes when it stops doing useful work
Why bother?
By interleaving execution when the process is idle, we can maximise CPU utilisation and reduce the time taken for jobs to finish.
What is a CPU scheduler?
CPU becomes idle, choose process to execute from the ready queue
What states can process be in?
Ready
Running
Blocked
Terminated
What is nonpreemptive scheduling?
Processes give up the CPU voluntarily (Co-operative)
What is preemptive scheduling?
Allows scheduling at any point
Why is concurrency control needed when scheduling?
Accessed shared application state may be left inconsistent. Requires coordination of access to shared state
When are processes preempted?
Only on IO block/after completion of system call as OS or Driver data structures may be left partially updated.
How is scheduling evaluated?
CPU Utilisation
Throughput
Turnaround time
Waiting time
Response time
Describe what is meant by CPU Utilisation.
Percentage of time for which CPU is busy.
Describe what is meant by Throughput.
Number of processes completed in a given time.
Describe what is meant by Turnaround time.
Time from submission of process to its completion
Describe what is meant by Waiting time.
Total time in the ready queue
Describe what is meant by Response time
Time from submission of process to time of first response.
What does the dispatcher do?
Switches from one task to another.
Performs needed tasks:
- switch context
- switch to user mode
- jump to proper location
What is FCFS?
First Come First Served.
FIFO ready queue. Ready processes added to the end of the queue., process at head allocated to CPU when available
What determines the average wait time of a FCFS queue?
Arrival order.
When is FCFS not good?
When there is overlap in execution of IO devices and CPU.
What does the SJF algorithm do?
Assign CPU to process with shortest next burst (impossible to implement as can’t predict the future).
Make best approximation as to how long burst will be.
How does priority scheduling work?
Assign a priority to each process, CPU is allocated to process with highest priority.
Potential problem of starvation of low priority processes, introduce ageing scheme
How is the priority of a process determined?
Internal measures; Memory requirements, CPU/IO burst ratio, System vs. user process
External measures; User-set priority, which use is running it
How is Round Robin scheduling implemented?
Set a time, quantum, as the maximum burst time. Use the FIFO queue and allow to run for the quantum
What are multi-level queues?
Used when processes can be easily classified into groups.
Partition the ready queue into several separate queues and reassign processes into these queues.
What is a multi-level feedback queue?
Extension of ML queue, allows processes to move between queues. Queues are separated according to CPU burst characteristics.
What is the algorithm of a feedback queue?
High priority processes in top queue.
If process exceed its quantum, move to a lower queue.
CPU bound processes sink, IO-bound have priority.
If processes waits for a long time, move to a higher queue
