xv6 FCFS Scheduling
- 学习xv6 FCFS(First Come First Serve) Scheduling
1.FCFS Scheduling
By default, xv6 uses a simple RR algorithm to schedule processes. In this lab, we will explore its scheduling policy and in subsequent labs we will implement some other policies such as first-come-first-served (FCFS) and priority scheduling.
First come first serve (FCFS) scheduling algorithm simply schedules the jobs according to their arrival time. The job which comes first in the ready queue will get the CPU first. The lesser the arrival time of the job, the sooner will the job get the CPU. FCFS scheduling may cause the problem of starvation if the burst time of the first process is the longest among all the jobs.
- First Come First Serve, is just like FIFO(First in First out) Queue data structure, where the data element which is added to the queue first, is the one who leaves the queue first.
- This is used in Batch Systems.
- It’s easy to understand and implement programmatically, using a Queue data structure, where a new process enters through the tail of the queue, and the scheduler selects process from the head of the queue.
- A perfect real life example of FCFS scheduling is buying tickets at ticket counter.
1.1.Advantages of FCFS
- Simple
- Easy
- First come, First serv
1.2.Disadvantages of FCFS
- The scheduling method is non preemptive, the process will run to the completion.
- Due to the non-preemptive nature of the algorithm, the problem of starvation may occur.
- Although it is easy to implement, but it is poor in performance since the average waiting time is higher as compare to other scheduling algorithms.
2.Calculating Average Waiting Time
For every scheduling algorithm, Average waiting time is a crucial parameter to judge it’s performance.
Average waiting time is the average of the waiting times of the processes in the queue, waiting for the scheduler to pick them for execution.
Lower the Average Waiting Time, better the scheduling algorithm.
For example:
In the Following schedule, there are 5 processes with process ID P0, P1, P2, P3 and P4. P0 arrives at time 0, P1 at time 1, P2 at time 2, P3 arrives at time 3 and Process P4 arrives at time 4 in the ready queue. The processes and their respective Arrival and Burst time are given in the following table.
The Turnaround time and the waiting time are calculated by using the following formula：
Arrival Time: Time at which the process arrives in the ready queue.
Burst Time: Time required by a process for CPU execution.
Completion Time: Time at which process completes its execution.
Turn Around Time: Time Difference between completion time and arrival time.
Waiting Time(W.T): Time Difference between turn around time and burst time.Turn Around Time = Completion Time - Arrival Time
Waiting Time = Turn Around Time - Burst Time
The average waiting Time is determined by summing the respective waiting time of all the processes and divided the sum by the total number of processes.
3.xv6 FCFS source code: FCFS github source code