A variety of scheduling policies are available; each of them is suited to the needs of a particular type of scheduler. In general, scheduling disciplines may be preemptive or non-preemptive.
A non-preemptive policy always processes a scheduled request to completion. In non-preemptive scheduling , the running process retains the ownership of allocated resources including the processor, until it voluntarily surrenders control to the operating system. Non-preemptive scheduling is attractive due to its simplicity. Since the scheduling is performed only when the previously scheduled request completes, the list of pending requests never contains a preempted request.
With pre-emptive scheduling, a running process may be replaced by a higher-priority process at any time. This is accomplished by activating the scheduler whenever an event that changes the state of the system is detected. A preemptive scheduling is much responsive as compared to non-preemptive, but it imposes higher overheads to the operating system since each process rescheduling requires a complete process switch.
First-Come-First-Served (FCFS) Scheduling
FCFS scheduling is the simplest scheduling policy. The implementation of FCFS is straightforward and has least overhead in its execution. In FCFS, requests are scheduled in the order in which they are arrive in the system. The list of pending requests is organized as a queue.
FCFS is a non-preemptive scheduling policy. Thus, once a process has the CPU, it runs to completion. It is fair in the formal sence but somewhat unfair in that long jobs make short jobs wait, and unimportant jobs make important jobs waits. FCFS is not suitable in interactive environments because it cannot guarantee good response time.
For example, consider the following five processes P1, P2, P3, P4, P5 in the same order of arrival.
CPU time or Burst time
Burst time is the time required by the CPU to execute the process.
Gantt chart: Pictorial or graphical representation of process execution.
Now we can calculate some important values.
Average waiting time
Waiting time for P1= 0
Waiting time for P2= 5
Waiting time for P3= 20
Waiting time for P4= 32
Waiting time for P5= 57
Average waiting time= (0+5+20+32+57)/5
= 22.8 ms
Average turn around time
Turn around time for P1 = 5
Turn around time for P2 = 20
Turn around time for P3 = 32
Turn around time for P4 = 57
Turn around time for P5 = 62
Average turn around time = (5+20+32+57+62)/5
= 35.2 ms
Average response time
Response time = first response – arrival time
Response time for P1= 0
Response time for P2= 5-0 = 5
Response time for P3= 20-0 = 20
Response time for P4= 32-0 = 32
Response time for P5= 57-0 = 57
Average response time = (0+5+20+32+57)/5
= 22.8 ms
Average weighted turnaround time
Weighted turn around time = (turn around time) / (Execution (burst) time)
Weighted turn around time of P1= 5/5 = 1.0
Weighted turn around time of P2= 20/15 = 1.33
Weighted turn around time of P3= 32/12 = 2.67
Weighted turn around time of P4= 57/25 = 2.28
Weighted turn around time of P5= 62/5 = 12.40
Average weighted turnaround time = (1+1.33+2.67+2.28+12.40) / 5
= 19.68 / 5
= 3.94 ms
Previous: CPU Scheduling
Index : Operating System