Operating System : Process Scheduling

Process Scheduling:

Objectives of multiprogramming is to have some process running at all times, to maximize CPU utilization. Objectives of time sharing is to switch the CPU among process so frequently that user can interact with each program while it is running. The process scheduler selects an available process for program execution on the CPU. In single processor system, there will never be more than one running process. If there are more process, the rest will have to wait until the CPU is free & can be rescheduled.

1.    Scheduling Queues

As processes enter the system, they are put into a Job queue, which consists of all processes in the system. The process that are residing in main memory & are ready and waiting to execute are kept on a list called Ready Queue. Queue is generally stored as Linked list. Ready Queue header contains pointers to the first & final PCB’s in the list. Each PCB includes a pointer field that points to the next PCB in Ready Queue. The list of processes waiting for a particular I/O device is called as Device Queue. Each device has its own device queue. A common representation of process scheduling is a Queuing Diagram. Each rectangle box represents a Queue.

Two types of Queues:

1.    Ready Queue

2.    Set of Device Queue

The circle represent the resource that serve the queues. Arrow indicate the flow of processes in the systems. It waits there until it is selected for execution or dispatched. Once the process is allocated the CPU and is executing, one of the several events could occur.

·        The process could issue an I/O request & then be placed in an I/O queue.

·        The process could create a new child process & wait for child’s termination.

·        The process could be removed from the CPU, as a result of an interrupt & be put back in Ready Queue.                                                                                                        

Process eventually switches from the Waiting state to Ready state & is then put back in the Ready Queue.

Process continues this cycle until it terminates once it is removed PCB & resources are deallocated.

Schedulers:

A process migrate among the various scheduling queues throughout its lifetime. The selection process is carried out by the appropriate scheduler.

1.    Long-Term Scheduler  (or) Job Scheduler

It selects processes from this pool and loads then into memory for execution. It executes much less frequently. Minutes may separation the creation of one new processes & the next. It controls the degree of multiprogramming, It may be need to be invoked only when a process leaves the system. It takes more time to decide which process should be selected for execution. CPU bound process, generates I/O requests infrequently, using more of its time doing computations.

2.    Short-Term Scheduler (or) CPU Scheduler

It selects from among the processes that are ready to execute & allocates the CPU to one of them. It selects new processes for the CPU frequently. A process may execute only for a few milliseconds before waiting for an I/O request. It executes at least once every 100 milliseconds. If it takes 10 milliseconds to decide to execute a process for 100 milliseconds, then 10/(100+10)=9% of CPU is being used simply for scheduling the work.

3.    Medium-Term Scheduler

Sometimes it can be advantageous to remove a a process from memory & thus reduce the degree of multiprogramming. The process can be reintroduced into the memory & its execution can be continued where it left off, called as Swapping. The process is swapped out, and is latter swapped in by the Medium Term Scheduler. Swapping may be necessary to improve the process mix or because a change in memory requirement has overcommitted available memory, requiring memory to be freed up.

Context Switch

When an interrupt occurs, the system needs to save the current control of the process running on the CPU so that it can restore the content when it’s processing is done, essentially suspending the process & resuming it. It includes the value of CPU registers, process state & memory management information. We perform state save of CPU registers, process state & memory management information. We perform state save of the current state of the CPU, be it in kernel or User mode. State Restore to restore operations. Switching the CPU to another process requires performing a state save of the current process & a state restore for different process. This task is known as Context Switch.