Monday, December 12, 2011

Explain and Solve : First Come First Served (FCFS) of Operating System Concepts


If you haven't read/tried the earlier problems then click the links follow:

                    01. Shortest Job First (SJF).
                    02. Round Robin (RR).
                    03. Priority Scheduling.


First Come First Served (FCFS): CPU gets a lot of processes to handle. The problem is shortening the waiting time for a process to reach CPU and get processed. Now consider a CPU and also consider a list in which the processes are listed as follows,

Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1


Here, Arrival is the time when the process has arrived the list, Process Number is used instead of the process name, and Burst Time is the amount of time required by the process from CPU. Well, as the unit of time you can take anything like nano-second, second, minute etc whatever. We consider it as second.

Now for an instance, consider the above list as the ready queue for the CPU, that is the CPU will take processes from this list and will process it.

Here in FCFS, CPU will take the first process in the list and will process it, then it will take the second process and so on. So this is a very easy thing to do huh ! Ok. So, lets see what CPU is doing,

At Time 0s Doing 1s time Unit Job of Process-1, so Process-1 has left 2s Time Unit Job
At Time 1s Doing 1s time Unit Job of Process-1, so Process-1 has left 1s Time Unit Job
At Time 2s Doing 1s time Unit Job of Process-1, so Process-1 has left 0s Time Unit Job
At Time 3s Doing 1s time Unit Job of Process-2, so Process-2 has left 1s Time Unit Job
At Time 4s Doing 1s time Unit Job of Process-2, so Process-2 has left 0s Time Unit Job
At Time 5s Doing 1s time Unit Job of Process-3, so Process-3 has left 0s Time Unit Job

We can show the above thing as the following time-line

Process-1
Process-1
Process-1
Process-2
Process-2
Process-3
0s
1s
2s
3s
4s
5s

A shortened view of the above time-line is as follows,


 | Process-1
|  Process-2
|  Process-3
|
0                
3
5
6

So now came the main thing, Waiting Time. Ok, Look carefully,

Process-2 Arrived at the List of Process at 1s with a Burst Time of 2s. But CPU started processing Process-2 at 3s. So process-2 waited for 2s.

Process-1
Process-1
Process-1
Process-2
Process-2
Process-3
0s
1s
2s
3s
4s
5s

But process-1 had not wait because it Arrived at 0s and also the CPU started processing it at 0s.

But Process-3 Arrived at the List of Process at 2s with a Burst Time of 1s. But CPU started processing Process-3 at 5s. So process-3 waited for 3s.

Process-1
Process-1
Process-1
Process-2
Process-2
Process-3
0s
1s
2s
3s
4s
5s

So total waiting time = (Waiting Time of Process-1)+ (Waiting Time of Process-2)
                                      + (Waiting Time of Process-3)
                                   = (0+2+3)s
                                   = 5s

So the average waiting time is = (Total waiting time / Number of Processes)s
                                                 = (5/3)s
                                                 = 1.66s

Ok...I think you have understood the thing. Now lets talk about the program.

Input: You will ask the user for the number of processes. Then for each process you will take its Process Number, Arrival Time and its Burst time. You don’t have to worry, the number of processes wont be more than 5 or 6, Arrival time of a process can only be equal or greater than the arrival time of its previous process and Process will be entered as a serial number, so no problem.

Output: In the output you will have to print out the shortened time-line we showed you above. For example, if the input is as follows,

Arrival
Process
Burst Time
0
1
3
1
2
2
2
3
1

Then the shortened time-line will be,


 | Process-1
|  Process-2
|  Process-3
|
0                
3
5
6



You can also print out the time-line vertically if you want (thats what I have done, see the output of my program)

Ok beneath this shortened time-line you will have to print a table as follows,

Process
Arrival
Finish
Total
Wait
1
0
2
3
0
2
1
4
2
2
3
2
5
1
3
                                             
Beneath this, you will have to show the Average Waiting Time.


I know you have understood, now see a screen-shot of exactly what I was talking about,







Exception: One exception is that, I said “Arrival time of a process can only be equal or greater than the arrival time of its previous process”. So take a look at the following list of process,

Arrival
Process
Burst Time
0
1
3
55
2
2
60
3
1


You see, the Job of Process-1 will complete at 2s, thus from 3s to 54s the CPU will remain idle. Again the job of Process-2 will complete at 56s and thus from 57s to 59s the CPU will again remain as idle. You have to show this in the output and also notice that none of the processes has waited. See the following screenshot,



You can download my program (.exe only) to try it out. Download from HERE.

After you have written the program upload the .exe (not the code) and let me and others try it. I am sure you will enjoy it. However, this is the first program of Process Scheduling and the easiest one. Later we will work on, Shortest Job First, Priority Scheduling and Round Robin. I am sure you will love them all.

6 comments:

  1. In the program u should sort Arrival time so that your program will work even if i input in wrong order

    ReplyDelete
    Replies
    1. In this program, I wasn't in need to do that as in real case, the arrival time will never come unsorted. However, thanks for suggestion.

      Delete
  2. Available codes for HTML ?

    ReplyDelete
    Replies
    1. You want code of this solution in HTML !!!!!!!!!!!!!!!!!!!!!

      Delete
  3. Replies
    1. sorry, i am supposed to describe and inspire, not to distribute work.

      Delete

Leave your valuable thoughts before leaving..