Question

In a Uniprocessor scheduler, what is the best algorithm? Why

Answer 1

In a Uniprocessor scheduler, what is the best algorithm? Why

The best algorthim is FCFS (First Come First Serve) because when designing a system, we often want to optimize for some specific system behavior(s). We can divide potential requirements into two categories: user-oriented and system-oriented. Each category can then be further divided into performance criteria that are quantitative and can be easily measured, and performance criteria that are more qualitative and are not as easily measured. This is not an exhaustive list, but only the ones that I think are the most important to examine.

User-oriented Criteria

User-oriented criteria is the behavior of the system as perceived by a single user.

Quantitative

Turnaround Time – The time from when a process is first added to the group of ready executable processes to the time when it finishes executing and exits. Discussed in much greater detail below.

Response Time – The time from when the request is first made to the time when the response starts to be received. From a user’s point of view, response time is a better measure than turnaround time because a process can produce feedback to the user while the process is still executing.

Qualitative

Predictability – For any given job, it should run in approximately the same amount of time regardless of the load on the system.

System-oriented

System-oriented criteria focus on effective and efficient utilization of the processor.

Quantitative

Throughput - The number of processes completed per unit of time. Depends a lot on the average length of the processes, but is still affected by the scheduling policy.

Processor Utilization – The percentage of time that the processor is busy. More important in multi-user systems than single user systems.

Qualitative

Fairness – Processes should be treated the same, and no process should suffer starvation.

Criteria Tradeoffs

It is impossible to optimize for all criteria concurrently. There is a tradeoff between user-oriented and system-oriented criteria when you maximize performance for one, you must give up performance in the other. For example, optimizing for response time would require a scheduling algorithm that switches between processes frequently. This increases overhead and reduces throughput.

Normalized Turnaround Time

In order to compare and contrast the different scheduling policies, a useful metric to consider is the normalized turnaround time (NTAT) for an individual process. Turnaround Time (TAT) not normalized is the total time a process spends in a system; this includes the time spent waiting for the processor and the time spent executing on the processor (aka service time):

Turnaround Time (TAT) = Waiting Time + Service Time

We normalize it by taking into account the ratio of the turnaround time to the service time:

Normalized Turnaround Time (NTAT) = TAT / Service Time

So, why is this important?

Well, the normalized turnaround time indicates the relative delay experienced by a process. For longer processes that require more service time, more delay is acceptable. A low NTAT value indicates less delay and a high quality level of service for a process; however, a high NTAT value indicates more delay and a poor quality level of service. The lowest and best possible NTAT value is 1.0. This happens when a process doesn’t experience any waiting time. To illustrate using the formula, NTAT = 0 + Service Time / Service Time = 1.0.