SCHEDULING AND SCHEDULERS
In this "SCHEDULING AND SCHEDULERS" article, You can learn PROCESS SCHEDULING, PROCESS SCHEDULING QUEUES, TWO-STATE PROCESS MODEL, PROCESS SCHEDULER, LONG TERM SCHEDULER, SHORT TERM SCHEDULER, MEDIUM TERM SCHEDULER, COMPARISON AMONG SCHEDULER, CONTEXT SWITCH, CPU SCHEDULING, SCHEDULING TYPES, CPU SCHEDULER OR SHORT-TERM SCHEDULER, JOB SCHEDULER OR LONG-TERM SCHEDULER, ARRIVAL TIME, BURST TIME, EXIT TIME, RESPONSE TIME, WAITING TIME, TURNAROUND TIME, and THROUGHPUT.
PROCESS SCHEDULING
The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy.
Process scheduling is an essential part of a Multi programming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing.
PROCESS SCHEDULING QUEUES
The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue.
The Operating System maintains the following important process scheduling queues −
· Job queue − This queue keeps all the processes in the system.
· Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.
· Device queues − The processes which are blocked due to unavailability of an I/O device constitute this queue.
The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.). The OS scheduler determines how to move processes between the ready and run queues which can only have one entry per processor core on the system; in the above diagram, it has been merged with the CPU.
TWO-STATE PROCESS MODEL
The two-state process model refers to running and non-running states which are described below −
| S.N. | STATE & DESCRIPTION |
| 1 | RUNNING When a new process is created, it enters into the system as in the running state. |
| 2 | NOT RUNNING Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute. |
PROCESS SCHEDULER
Schedulers are special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run.
Schedulers are of three types −
- Long-Term Scheduler
- Short-Term Scheduler
- Medium-Term Scheduler
LONG TERM SCHEDULER
It is also called a job scheduler. A long-term scheduler determines which programs are admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling.
The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system.
On some systems, the long-term scheduler may not be available or minimal. Time-sharing operating systems have no long term scheduler. When a process changes the state from new to ready, then there is use of long-term scheduler.
SHORT TERM SCHEDULER
It is also called as CPU scheduler. Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them.
Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers.
MEDIUM TERM SCHEDULER
Medium-term scheduling is a part of swapping. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-processes.
A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix.
COMPARISON AMONG SCHEDULER
| S.N. | Long-Term Scheduler | Short-Term Scheduler | Medium-Term Scheduler |
| 1 | It is a job scheduler | It is a CPU scheduler | It is a process swapping scheduler. |
| 2 | Speed is lesser than short term scheduler. | Speed is fastest among other two. | Speed is in between both short and long term scheduler. |
| 3 | It controls the degree of multiprogramming | It provides lesser control over degree of multiprogramming | It reduces the degree of multiprogramming. |
| 4 | It is almost absent or minimal in time sharing system | It is also minimal in time sharing system | It is a part of Time sharing systems. |
| 5 | It selects processes from pool and loads them into memory for execution | It selects those processes which are ready to execute | It can re-introduce the process into memory and execution can be continued |
CONTEXT SWITCH
A context switch is the mechanism to store and restore the state or context of a CPU in Process Control block so that a process execution can be resumed from the same point at a later time. Using this technique, a context switcher enables multiple processes to share a single CPU. Context switching is an essential part of a multitasking operating system features.
When the scheduler switches the CPU from executing one process to execute another, the state from the current running process is stored into the process control block. After this, the state for the process to run next is loaded from its own PCB and used to set the PC, registers, etc. At that point, the second process can start executing.
Context switches are computationally intensive since register and memory state must be saved and restored. To avoid the amount of context switching time, some hardware systems employ two or more sets of processor registers. When the process is switched, the following information is stored for later use.
Program Counter
Scheduling information
Base and limit register value
Currently used register
Changed State
I/O State information
Accounting information
In order to known in details, please study Memory Management Note.
When we are dealing with some CPU scheduling algorithms then we encounter some confusing terms like Burst time, Arrival time, Exit time, Waiting time, Response time, Turnaround time, and throughput. These are the parameters used to find the performance of a system.
CPU SCHEDULING
CPU scheduling is a process that allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU. The aim of CPU scheduling is to make the system efficient, fast, and fair.
Six types of process scheduling algorithms are: First Come First Serve (FCFS), 2) Shortest-Job-First (SJF) Scheduling 3) Shortest Remaining Time 4) Priority Scheduling 5) Round Robin Scheduling 6) Multilevel Queue Scheduling.
The main objective of any CPU scheduling algorithm is to keep the CPU as busy as possible. Theoretically, CPU utilization can range from 0 to 100 but in a real-time system, it varies from 40 to 90 percent depending on the load upon the system. (CPU UTILIZATION)
CPU SCHEDULER OR SHORT-TERM SCHEDULER
Schedules the execution of processes in the ready queue of the system.
Sometimes it is the only scheduler in the Operating System.
It is invoked frequently (in milliseconds) so it must be fast.
JOB SCHEDULER OR LONG-TERM SCHEDULER
Selects which processes to be brought to the ready queue of the CPU.
Invoked infrequently (in seconds, sometimes minutes), it may be slow.
It controls the degree of multiprogramming.
Different CPU scheduling algorithms have different properties and the choice of a particular algorithm depends on the various factors. Many terms have been suggested for comparing CPU scheduling algorithms.
ARRIVAL TIME
Arrival time means when a program is loaded into main memory for execution, then it is called Process. The process then further enters into the Ready queue for execution, the time when it has arrived at the ready state for execution is called the Arrival time of that process.
BURST TIME
After arriving in the Ready state, Every Process in the computer system is selected for execution for some amount of time. This time is both the CPU time and the I/O time. The CPU time is the time taken by the CPU to execute the process. While the I/O time is the time taken by the process to perform some I/O operation. In general, we ignore the I/O time and we consider only the CPU time for a process. So, Burst time is the total time taken by the process for its execution on the CPU.
EXIT TIME
After completion of execution, Every process terminates. Exit time is the time when a process completes its execution and exit from the system.
RESPONSE TIME
During execution, if an interrupt occurs, then the process is either going to a ready state or waiting state for some time. Here, Response time means the First time when Process gets the CPU. Response time is the time spent when the process is in the ready state and gets the CPU for the first time. In the context-switching scenario, Response time is easy to understand. Otherwise, Response time is similar to Arrival time.
Response time = Time at which the process gets the CPU for the first time - Arrival time
WAITING TIME
For execution, a process may be in the waiting state. The amount of time spent in the waiting state is called Waiting time. Waiting time is the total time spent by the process in the ready state or waiting state waiting for CPU.
Waiting time = Turnaround time - Burst time
There is a difference between waiting time and response time. Response time is the time spent between the ready state and getting the CPU for the first time. But the waiting time is the total time taken by the process in the ready state.
TURNAROUND TIME
It can be described into two ways,
Turnaround time = Burst time + Waiting time
or
Turnaround time = Exit time - Arrival time
In short, the total time of a process enters into the Ready State(at beginning) till it's termination. Turnaround time is the total amount of time spent by the process from coming in the ready state for the first time to its completion.
THROUGHPUT
Throughput is a way to find the efficiency of a CPU. It can be defined as the number of processes executed by the CPU in a given amount of time. Discussed more in MEMORY MANAGEMENT NOTE.
FAQ:
Q. What are the properties that a good scheduling algorithm should maintain?
Be fair – give each process a fair share of the CPU, allow each process to run in a reasonable amount of time.
Be efficient – keep the CPU busy all the time.
Maximize throughput – service the largest possible number of jobs in a given amount of time; minimize the amount of time users must wait for their results.
Minimize response time – interactive users should see good performance.
Be predictable – a given job should take about the same amount of time to run when run multiple times. This keeps users sane.
Minimize overhead – don’t waste too many resources. Keep scheduling time and context switch time at a minimum.
Maximize resource use – favor processes that will use underutilized resources. There are two motives for this. Most devices are slow compared to CPU operations. We’ll achieve better system throughput by keeping devices busy as often as possible. The second reason is that a process may
be holding a key resource and other, possibly more important, processes cannot use it until it is released. Giving the process more CPU time may free up the resource quicker.
Avoid indefinite postponement – every process should get a chance to run eventually.
Enforce priorities – if the scheduler allows a process to be assigned a priority, it should be meaningful and enforced.
Degrade gracefully – as the system becomes more heavily loaded, performance should deteriorate gradually, not abruptly
In short, When the process terminated it is denoted as the Turnaround time. When the process enters into the execution part at that time minus arrival time is noted as Waiting time. Every process has its own waiting time and Turnaround time. The amount of time when the process gets CPU for execution is called Burst time.
Round Robin Scheduling, FCFS Scheduling, SJF Scheduling, SRTF Scheduling and Priority Scheduling is discussed in Scheduling Algorithms.
Hope you learned something new today. Keep Learning :)
Comments
Post a Comment