Process Scheduling

Submitted by abhishek on Sat, 11/17/2007 - 04:54
    In multiprogramming systems, when there is more than one ready process, the operating system must decide which one to activate.
    The decision is made by the part of the operating system called the scheduler, using a scheduling algorithm.
    The scheduler is concerned with deciding policy, not providing a mechanism
The Keywords:

Process: A process us a sequential program in execution. The components of a process are the following

  1. The Object Program (or code) to be executed.

  2. The data on which the program will execute

  3. Resources required by the program

  4. The status of Program execution

CPU Burst (Usage Time): The amount of time a process needs to be in the running state before it is completed

Turnaround Time : The amount of time between the moment of process first enters the ready state and the moment the process exits the running state for the last time.

Waiting Time : The time the process spends waiting in the ready state before its first transition to the running state.

Time Quantum (time slice): The amount of time between timer interrupts. (Used when process manager use an interval timer).

Scheduling Policies

The scheduling policy determines when it is time for a process to be removed from the CPU and which ready process should be allocated the CPU next.

Preemptive: A strategy for time-multiplexing the processor whereby a running process is removed from the processor whenever a higher-priority process becomes ready to execute.

Non Preemptive: A strategy for time-multiplexing the processor whereby a process does not release the processor until it has completed its work.

Scheduling Algorithms

First Come First Served: FCFS, also known as First-In-First-Out (FIFO), is the simplest scheduling policy. Arriving jobs are inserted into the tail (rear) of the ready queue and the process to be executed next is removed from the head (front) of the queue.

Shortest Job First : SJF policy selects the job with the shortest (expected) processing time first. Shorter jobs are always executed before long jobs. long running jobs may starve, because the CPU has a steady supply of short jobs. 

Round Robin: RR reduces the penalty that short jobs suffer with FCFS by preempting running jobs periodically. The CPU suspends the current job when the reserved quantum (time-slice) is exhausted. The job is then put at the end of the ready queue if not yet completed.

 Priority : Each process is assigned a priority. The ready list contains an entry for each process ordered by its priority. The process at the beginning of the list (highest priority) is picked first. A variation of this scheme allows preemption of the current process when a higher priority process arrives.