-
All programs consist on mainly two types of operations, CPU Burst and I/O Burst, which alternate in execution sequence. The first and last bursts in a program are usually of type CPU Burst. In between we have an alternating sequence of CPU bursts and I/O bursts.
-
In order for a job to prepare for loading into main memory for execution, it must go from a NEW STATE to READY STATE. A job can only be executed by the CPU only when it is in a READY STATE. When the CPU is executing the job the state changes to ACTIVE STATE. After the job's final CPU burst is finished the state changes to HALTED STATE.
-
When the job or process performs I/O burst operation then you can remove it from CPU and put into a state called WAITING STATE or I/O WAITING STATE. During this transition of state the CPU become available and can perform the CPU burst of another job or process.
-
After waiting state the job can be moved to either ready state or active state. There is no way of guarantee that the CPU will be ready to continue execution of the job since it might also be executing the CPU burst operation of another process. A cleaner way to deal with the execution of the job is to move it into ready state, so that the CPU can execute it when it becomes available. This allows for a multiprocessing system even when there is just one CPU available.
-
The OS must have an idea about what is next CPU burst duration of a job. This way it can decide on what job to execute from the READY queue. There is no way to know the exact time of the next job's CPU burst, so there has to be a predicted value instead. This is only needed for the SJF (Shortest job first) scheduling algorithm and not the FCFS (first come first serve) scheduling algorithm. In this way the job with the shortest CPU burst is to be executed first.
-
There is another type of scheduling called the Priority Scheduling, where you can specify different priority levels for jobs. In this type of scheduling the job with the highest priority level is executed first and not necessarily the job with the shortest CPU burst as in the SJF algorithm. In fact, the SJF algorithm is considered a special type of priority scheduling where the job with the shortest CPU burst time is given higher priority.
-
FCFS, SJF, and PRIORITY scheduling are also known as Non-preemptive scheduling. The difference with non-preemptive and preemptive is that preemptive scheduling allows a job that is being executed by the CPU to be interrupted and stopped to make the CPU available to other jobs or processes. SJF and PRIORITY can be modified to become a preemptive scheduling. That is, now the OS looks at the READY queue for jobs that are coming in and if the new job requires less CPU burst time than the first job then the first job is halted and then the new job with the new shortest CPU burst time is executed. Essentially, the READY queue is constantly being monitored for new job arrivals. Another way to think about preemptive scheduling is that the OS keeps comparing the remaining time of the current job being processed by the CPU and comparing it with all the time units of the jobs in the READY queue, including the newly arrived ones. If there is another job that requires less time, then the current job is halted and the CPU is made available for the newly arrived job. When SJF scheduling is modified to operate as a preemptive scheduling algorithm it is renamed to SRT or SHORTEST REMAINING TIME scheduling.
-
On the other hand, when the PRIORITY scheduling algorithm is modified to operate as a preemptive scheduling algorithm there is a high possibility that a job -- that was already in the READY queue -- will starve of CPU time; there is a job that will never be executed if the priority of the newly arrived job is always higher. (OBSERVATION: Assuming jobs that require low executing time keep coming into the READY queue, one job (already in the READY queue) with high execution time will probably never obtain CPU time to be executed. This problem can be subsided through a concept commonly known as aging. This means that the priority of a job is not only decided by the system administrator but also by the amount of time it has remained in the READY queue. This ensures that a job that was initially set with very low priority and had spent some time in the READY queue to never starve of CPU time.
-
Concretely, preemptive scheduling allows for a job to go from an ACTIVE STATE to READY STATE directly, without needing to go to a WAITING STATE. This whole process of changing a job state is called the Process State Diagram.
-
A job that requires significantly more CPU burst time than I/O burst time is also known and CPU-bound or compute-bound jobs. Conversely, a job that requires significantly more I/O burst time than CPU burst time is also known as I/O bound jobs.
-
In the event that there is too much compute-bound jobs or too much I/O-bound jobs in the READY queue, there will be inefficient use of resources by the computer system. The desired case would be to have a balanced mix of compute-bound jobs and i/o-bound jobs inserted into the READY queue. One way to maintain this balance is to have a scheduler deciding what type of jobs that are taken from the NEW STATE into the READY queue. Similarly, there is a scheduler that moves a job from a READY state into an ACTIVE state and it is known as SHORT TERM SCHEDULER. A scheduler that puts a job from the NEW queue into the READY queue is known as LONG TERM SCHEDULER.
-
The main difference between the long-term and short-term schedulers is the time taken to move a job into the different states. Short-term scheduler deals with the important task of moving a job from READY state (usually residing in memory) into ACTIVE state (resides in CPU). Therefore, it is important that this scheduler is fast and efficient. Whereas for the long-term scheduler is just deciding what jobs go into the READY queue so it is not required to be as fast as short-term scheduler.
-
A round-robin scheduling is a form of preemptive scheduling, where all jobs are treated equally and taken from the head of the queue. The jobs are scheduled for execution on a first-come, first-serve basis. In this model, there is a timer set by the CPU on the jobs. If a job required more that the time set by the CPU, then that job is processed and then moved back to the READY state. Other jobs that meet the criteria of time set by the CPU, are completely executed and then moved into a HALT state or I/O waiting state (if it needs I/O processing). This model needs a programmable timer, which is in charge of interrupting jobs that require more time than what the CPU has been set to execute.
-
A Multi-Level Queue (MLQ) scheduling allows for multiple READY queues where jobs can be categorized in different queues. Some jobs may be categorized by CPU burst time requirement. This means that jobs which are CPU bound (require more CPU time) loose priority. The jobs which are in the first queue are I/O bound (require less CPU time) and are executed first before executing jobs in the remaining queues.
-
The disadvantage of MLQ is that some jobs might become I/O bound (require less CPU time) but they cannot be moved from the designated queue. To fix this problem, there is another queue called the Multi-level feedback queue (MLFQ). Here jobs can be moved around the different level of queues depending on their requirements. Each job is executed and interrupted by the timer if the CPU time is above the time requirements set by the CPU. Once the timer interrupts then the job goes back into the queue depending on how much remaining time it requires. Similarly, jobs that are in the bottom queues (CPU bound jobs) can be moved to higher-priority queues if they require less CPU time. The difference between the MLQ and MLFQ is that MLFQ allows for checking of the nature of the job so as to make the necessary shifting between queues.
-
In summary, there are two types of scheduling which are categorized into preemptive and non-preemptive scheduling:
| Non-Preemptive | Preemptive |
|---|---|
| FCFS | SRT |
| SJF | Round Robin |
| Priority | Multi-level queue |