First-Come-First-Served
Dr. Sridhar R. Iyer, IIT Bombay,Mumbai
=================================================================================================

The summer vacations were approaching and everyone was keen on working on some job during the summer. Srinath was in the final stages of an interview. The interviewer said, "As you know, we have several applicants who seem to be equally qualified. So we have devised a task which each of you have to complete. Whoever completes the task at the earliest, will get the job." Seeing that Srinath remained silent, the interviewer continued, "First you need to get this medical evaluation form filled by a doctor whose office is on the 2nd floor. Then you need to get a copy of it from the photocopy department on the 1st floor. Finally you have to deliver it to our Administration office on the 3rd floor and come back here." Srinath, who liked puzzles, now smiled and said, "Ok. So what is the catch?"

The interviewer laughed and said, "The first catch is: There are three doctors who have consulting rooms on the 2nd floor. Each of them uses a different policy for seeing patients, so you have to choose carefully before joining any of the queues. Once you join a queue, you cannot leave it and go to another. If you choose the wrong queue, it may take you too long to get the medical evaluation done." "The second catch is: There are two persons operating the photocopy machines on the 1st floor. Again, you have to choose carefully, otherwise you may wait for too long in the wrong queue.", the interviewer concluded.

Srinath said, "This is interesting. Let me try." He took a form and set out for the 2nd floor. He reached the 2nd floor and looked into the first consulting room. There was a notice saying, "Please take a token. The doctor will see patients in the First-Come-First-Served order." Srinath saw that there were five people waiting. He thought, "Since it is first-come-first-served, I am sixth in line to see the doctor. But I dont know how long each of these five people will take, so let me see the other rooms."

In the second room, there were again five people waiting. A nurse was enquiring the purpose of the visit and was then deciding who should see the doctor next. One of the persons was arguing with the nurse, "Look here, I was the first in the queue but you have been sending others to see the doctor before me." The nurse explained, "Yes, you were the first but your consultation with the doctor will take a long time. Some of these other people are here only for routine medical evaluation or are sales representatives. Each of them will take only a few minutes with the doctor. So when the doctor becomes free, the person who is likely to require the Shortest Time goes in First."

Srinath thought, "Hmm. Since mine is only a routine medical evaluation, my turn is likely to come faster here. But what if more people arrive while I am waiting? Suppose they require less time than me then my turn will get delayed. Let me see the last room before deciding."

In the third room also there were five people waiting. But now there were three separate queues. There was a notice saying, "Patients should join queue no. 1, Medical evaluations should join queue no 2 and Sales representatives should join queue no 3. The doctor will see people in a Round-Robin order." Srinath thought, "Round-Robin means that the doctor will see one person from the first queue, then one person from the second, then one person from the third queue. After that he will start from the first queue again. Right now there is no one in the patients queue, one person in the medical evaluation queue and four people in the sales representatives queue. So I should be the third person to see the doctor." Can you guess which room he entered?

After the medical evaluation, Srinath went to the 1st floor for photocopying the report. He found that the operator of the first photocopy machine was using a First-Come-First-Served policy. Moreover, he was already engaged in making copies of a big document and there were two people waiting. "I don’t want to wait forever", thought Srinath and moved on to see what the second operator was doing.

The second operator was also engaged in making copies of a big document. Again there were two people waiting. While Srinath was wondering what to do, the operator asked, "How many pages do you have for copying?" One of the people waiting said, "Five" and the other said "Seven". Srinath understood the second operator's policy. He quickly joined the queue and said "Two". Now the operator immediately kept the current document aside and took up Srinath's report. He made a copy of the report and gave it to Srinath. The operator then did the work of the person having five pages, followed by the work of the person having seven pages, before resuming with the earlier document. But hey, Srinath was not waiting there to see all this! As soon as his work had been done, he had run up to the 3rd floor and completed his task in record time. Do you think he'll get the job?

Not surprisingly, similar principles called 'scheduling techniques' are used in many areas of computer applications. Scheduling techniques are used in operating systems (to share the processor time among tasks) as well as in routers (to share bandwidth among various packet traffic). First-Come-First-Served, Shortest Time First and Round-Robin are all examples of different types of scheduling. The reason for scheduling is for tasks to access shared resources in a orderly manner. In the above story, the people waiting to see the doctor correspond to the tasks. The doctor corresponds to a resource. Often, the main requirement in scheduling is to provide 'fair' access and minimize 'starvation'. Fair access means that no task should monopolize the resource. Minimizing starvation means that no task should be made to wait indefinitely. Another important term is called 'Turnaround Time'. This is the time taken from the point a task joins the queue for waiting for the resource, till the point when the task completes using the resource. So minimizing the turnaround time for each task is also important.

In First-Come-First-Served (FCFS) scheduling, each task is given access to the resource in the order in which it arrives, without other biases or preferences. For example, FCFS policy is usually employed when seating people at a restaurant. The key advantage of FCFS is that it is very simple and easy to implement. However, the key disadvantage is that the turnaround time for the various tasks depends on the arrival order. So if some long (time-consuming) tasks arrive earlier and short tasks arrive later, the short tasks may be stuck waiting for the long tasks to complete.

In Shortest-Job-First (SJF) scheduling, the task that requires the shortest time is given access to the resource first, even though some other tasks may have arrived earlier. For example, SJF policy is usually employed when multiple documents are to be photocopied. The key advantage of SJF is that it minimizes the turnaround time of short tasks. However, the key disadvantage is that it is hard to predict when a task will get access to the resource, since shorter tasks may continue to arrive. As a result, long tasks may never get access to the resource, leading to starvation.

In Round-Robin (RR) scheduling, each task is given access to the resource for a specific duration, in a cyclic manner. For example, RR policy is usually employed when many people take turns to watch different channels on TV at the same time. They can use RR scheduling by watching each channel of interest for some time! The key advantage of RR is that the tasks get a fair share of the resource and short tasks finish relatively quickly. However, the key disadvantage is that RR may not be very useful when there are many tasks, because each task is given access to the resource only for a very short time. Imagine watching TV where you get to see your favorite channel only for a few minutes before the channel is changed!

In Shortest-Remaining-Time-First (SRTF) scheduling, a newly arrived task is substituted for the current task, if the new task requires less time than the remaining time of the current task. This mechanism of substitution is called 'pre-emption'. For example, SRTF policy is usually employed in a cycle shop. If the mechanic is mending a punctured tube, and someone comes in only to fill air, the mechanic pre-empts the longer task and completes the shorter task first.

SRTF is also employed when a tailor puts aside the making of a dress to attend to a new customer. The key advantage of SRTF is that short tasks that arrive later are not kept waiting for long tasks to complete. However, the key disadvantage is that if many short tasks come one after the other, a longer task may have starvation. Imagine if a large number of people suddenly arrive at the cycle shop, while you are waiting for the puncture to be mended!

Figure: Scheduling policies

While scheduling may sound simple, there are a lot of intricacies. For example, what happens when some tasks are more important than others? More complex techniques take into account priority, or the importance of the task. This allows some tasks to use more time than others or get earlier access to the resource. Priority often goes hand-in-hand with pre-emption. If a task is being processed, and a more important task arrives, the earlier task is pre-empted in favour of the task with higher priority. We will meet such scheduling techniques in a later article!

Some interesting related websites are:

http://en.wikipedia.org/wiki/Scheduling

http://oscar.iitb.ac.in/onsiteDocumentsDirectory/scheduling/scheduling/index.html

http://www.kom.e-technik.tu-darmstadt.de/projects/iteach/itbeankit/lessons/scheduling/index.html

Key-words:
Scheduling: The process of assigning tasks to a set of resources. It is an important concept in many areas such as computing and production processes.
Starvation: The condition wherein a task is made to wait for very long time in order to access the resources. <>