1.2.1 Flashcards
Are these scheduling algorithms pre-emptive or non pre-emptive
(RR, SRT, MLFQ, FCFS, SJF)
Pre-emptive: RR, SRT, MLFQ
Non pre-emptive: FCFS, SJF
How does round robin work
A queue is made holding all processes that are ready to run. When the first process is loaded it is given a certain amount of CPU time to use. If the process is completed in that time the next process in the queue is loaded immediately, if not it is moved to the back of the queue to wait for another turn.
RR advantages and Disadvantages
Advantages
It is simple to implement. Round Robin is good if all the processes are more or less the same size and priority
Disadvantages
- It doesn’t take into account the priority of a process. High priority processes have to wait just as long as the lower priority processes
- It does not consider that some processes are much longer than others. If processes vary a lot, Round Robin is an inefficient way to allocate time and resources.
First come first served
The algorithm lines up all the processes that are ready to run in a first in first out queue. Each process is allowed to run to completion before the next one begins. New processes are loaded into memory when the one before finishes.
FCFS advantages and disadvantages
Advantages
- It is simple to implement and ensures that once a process is started it will run to completion in minimal time
Disadvantages
- Once a job starts it prevents other jobs from being processed until it’s completed
- A job that need to access a slow resource (a printer) wastes processor time whilst it’s waiting for the resource
- It does not take into account priority. High priority processes are put behind low ones if they arrive later
- It does not consider the length of the process. A long process will delay shorter ones behind it
Shortest job first
The processes are arranged in a queue ordered by how much time each process needs to complete. If a new process comes along, the scheduler works out its processing time and it gets slotted into the queue at the appropriate point. If it is shorter than any of the queue, the current process is interrupted and the shorter process runs immediately.
SJF advantages and disadvantages
Advantages
- It ensures the maximum number of jobs are completed
- It ensures that short jobs aren’t kept waiting while long processes tie up the CPU
- It minimises the average time a process takes to complete
Disadvantages
- Does not take into account priority. A long process of high priority can be kept waiting while shorter, unimportant process complete
- If a long job is nearly completed it will be interrupted and put back in the queue when the shorter job arrives
- The scheduler can only estimate how long a job will take to complete, this estimation can be wrong
- Long jobs many never complete if shorter jobs keep jumping the queue
Shortest time remaining
A big problem with shortest job first is that if a job that is 1000 cycles long gets to the front of the queue and starts running, it will still be interrupted if a job 700 cycles long comes along. This happens even if it only has 1 cycle left to complete, since the total length of the new job is shorter than the total length of the old job. The shortest time remaining algorithm fixes this by ordering the jobs by how much time they have remaining.
STR advantages and disadvantages
Advantages
- It allows short processes to be handled very quickly
- It ensures the maximum number of processes are completed in a given time
Disadvantages
- It does not take into account the priority of the process
- Long jobs may never complete if shorter jobs keep jumping the queue
Multi-Level
This algorithm maintains a number of queues with different priority levels. Every job is given a priority by the scheduler when it arrives and is sorted into the relevant queue. The queues themselves are also sorted by one of the previously discussed algorithms. The high priority queue is completed first. The scheduler is able to re-prioritise jobs at any time, moving them into the queue appropriate for their new priority. It may do this based on new information, or simply because the low priority job has been waiting too long.
Multi level advantages and disadvantages
Advantages
- Makes sophisticated use of process priority
- It ensures that higher priority process run on time
Disadvantages
- Complex to implement
- Not very efficient if all jobs have similar priority
- Low priority jobs may take a very long time to complete if the queue algorithm does not compensate for wait time
Why is scheduling necessary
- To process as many jobs as possible in the shortest possible time
- Ensure all jobs are processed fairly
- Make efficient use of processor time
