Process Scheduling Flashcards
Processor manager
Uses one or more scheduling algorithms to dispatch processes.
Non-preemptive scheduling
Process stays on the CPU until it terminates or blocks for I/O, implements multiprogramming.
Preemptive scheduling
Implements multitasking and can be interrupted and replaced with another process.
Processor Manager Objectives
Maximise throughput
Minimise turnaround time
Minimise waiting time
Maximise CPU efficiency
Minimise latency
Its not possible to have all of these criteria fulfilled at once as they clash with one another, therefore the processor manager tries to ensure fairness.
Burst Time
Time a process takes on the CPU before it blocks or terminates.
Arrival Time
Time a process is first put into the ready state.
First Come First Served
Deals with processes according to their arrival time.
Uses a FIFO order to store ready processes.
When a new process is added, its PCD is added to the back of the ready queue.
FCFS Average Wait Time
The time can change if the biggest one is last, as the biggest time is not considered as part of the equation.
FCFS Advantages and Disadvantages
Advantages:
- Very simply implementation.
- Scheduling overhead is minimal during content switch, since you just get the next one in the ready queue that the pointer points to.
- No starvation of processes, which means they will run eventually.
Disadvantages:
- Throughput can be low due to long processes staying on CPU.
- Average wait time is not minimal.
- Turnaround time and latency are therefore hard to predict.
- No ability to prioritise processes.
If bigger processes went last, speed would increase.
Shortest Job First
When the CPU becomes free, the scheduler will choose the process with the shortest burst time. If two are the same, we just choose by arrival time. Similar to FCFS, it stays there until terminated.
SJF Average Wait Time
The average wait time will be shorter than FCFS, because it does the minimal one first.
SJF Advantages and Disadvantages
Advantages:
- Reduces overall average wait time.
- Probably optimal in giving AWT for given (average wait time) processes.
Disadvantages:
- Can lead to process starvation, could lead to starving the OS.
- Difficult to estimate burst times for new processes, since it relies on prior history.
Shortest Remaining Time First
Instead of looking at burst time, it simply just looks at how long it has left to process. So whatever is on the CPU can be taken off before it finishes, and whatever has a shorter remaining time until it terminates or it is blocked. This is very hard to calculate, and therefore it is hard to draw a Gaant chart for.
SRTF Advantages and Disadvantages
Advantages:
- Short processes are handled very quickly.
- Gives maximum throughput in most situations.
- Requires little overhead during context switch.
Disadvantages:
- Starvation is still possible.
- Introduces extra context switches.
- Waiting time can increase for longer processes.
Throughput
-> get through x amount of processes in y amount of time.
Minimise Turnaround Time
-> minimise time taken for processes to complete.
Minimise waiting time
-> reduce time processes spend in ready state.
Maximise CPU efficiency
-> keep CPU constantly busy.
Minimise latency
-> reduce time taken between request and response.
Priority Scheduling
A preemptive algorithm that gives preferential treatment to important processes; each process has priority assigned to it, with the highest priority getting onto the CPU first.
Equal priority just uses FCFS, and if a new process arrives with a higher priority arrives than the current priority, it interrupts it and places itself on the CPU.
Priorities can depend on things like memory usage, I/O throughput, total CPU time and time already elapsed.
Priority Scheduling Average Wait Time
Add up priorities in terms of their wait time (ms).
Priority Scheduling Advantages
- Smaller wait time and latency for higher priority.
- Important priorities are dealt with quickly.
Priority Scheduling Disadvantages
- Bigger wait times and latency for lower priority.
- Starvation is possible.
Round Robin Scheduling
Preemptive, and uses time slice (quantum; typically between 10ms and 100ms) to give a set amount of CPU time to each process.
Similar to FCFS but can be interrupted before they terminate or block.
The ready state is similar to a circular FIFO queue:
- New processes arrive back of queue.
- Scheduler takes next process from front.
- Process runs for set amount of time.
- Context switch moves current process to back of queue and dispatches next in line.
- This repeats.
If the burst time is less than the quantum time, the process will terminate or block for I/O, and will immediately take next process from queue and place on CPU. If quantum time < burst time, it will be interrupted and context switch will happen (preempted).
If quantum is too big, similar to FCFS.
If quantum is too small, similar to SJF.
Round Robin Turnaround and Wait Time
To calculate AWT, we use turnaround time and wait time.
Turnaround -> time when it was terminated - when it arrived
Equations = wait time + burst time
or
Completion time - arrival time
Wait -> turnaround - burst.
Round Robin Advantages
- Easy to implement as queue.
- No guessing times.
- Response time based upon number of processes, not burst time.
- No starvation
- Balanced throughput
Round Robin Disadvantages
- Depends on selecting good quantum times
- Extensive overhead if quantum is too short.
