Info
Scheduling cheatsheat.
Multi-tasking operating systems support running simultaneous processes simultaneously.
Scheduling
First Come First Serve (FCFS)
Non-pre-emptive.
- Similar to a supermarket queue
- Processes are executed in order of arrival
- If a process takes too long, other processes have to wait for it to finish
- Completes the task at hand
- Other tasks will not run
- *Despite being somewhat fair, it is not practically effective
Shortest Job First (SJF)
Non-pre-emptive.
- Picks the process that has the shortest amount of time to execute
- Completes the small tedious tasks first
- If there is countless small tasks, they will keep getting pushed back and may not execute
- Needs to know how long a process will take
- Lacks extremely in fairness
Shortest Remaining Time (SRT)
Similar to SJF
- Picks the process that has the shortest amount of remaining time to execute
- More adaptve than SJF
- May rapidly switch between two close processes
Round-robin (RR)
- Slices up an allocated time block to be appropriately allocated for several processes
- Extremely fair
- Potentially ineffective
- Real-world application: serves a basis to the Windows scheduler and Linux CFR scheduler
Multi-Level Feedback Queues (MLFQ)
- Multi-core by design
- Not effective standalone
- Real-world application: serves a basis to Windows scheduler
“Multiple-level queue scheduling is a scheduling algorithm that attempts to categorize processes and then place them in multiple queues or levels with different priorities. Tasks are executed by level, such that all of the processes in the topmost level are executed first before moving on to lower levels. If a process is placed in a higher level while a longer one is being processed, the scheduler will move back up to take care of the higher level task first.”
Summary
| Scheduling Algorithm | FCFS | SJF | RR | SRT | M(L)FQ |
|---|---|---|---|---|---|
| Description | The first job to enter the ready queue is the first to enter the running state. | Jobs are sorted in the ready queue according to the estimate processor time needed. | Each process is given a maximum length of processor time in the running state after which it is put back into ready queue. | The ready queue is sorted on the estimated time to complete the process. Processes that arrive having a shorter time to complete than the current running process are moved to the running state. | Several ready queues are used each with a different scheduling algorithm. Jobs are able to move between queues as their priorities change. |
| Pre-emptive? | :LiCross: | :LiCross: | :LiCheck: | :LiCheck: | :LiCheck: |
| Ranking of fairness | 5 | 4 | 1 | 3 | 2 |