First Come First Served FCFS Scheduling

Scheduling Policies

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 scheduling

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.

Process	CPU time or Burst time (in ms)
P1	5
P2	15
P3	12
P4	25
P5	5

Burst time is the time required by the CPU to execute the process.

Gantt chart: Pictorial or graphical representation of process execution.

We can draw the Gantt of the above process as shown below. Assume that all processes are arrived at time 0.

Gantt chart

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

                                          = 114/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

                                                = 176/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

                                    = (114)/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

      NEXT: SJF Scheduling 

Previous: CPU Scheduling 

      Index : Operating System