Scheduling: Completion Time vs. Response Time

1. Introduction

Scheduling refers to determining when and in what order tasks or processes should be executed in a computing system. Scheduling is a crucial component in modern computing systems as it helps to efficiently and effectively manage the available resources, such as CPU time and memory.

In this tutorial, we’ll discuss two important metrics used for evaluating the performance of a scheduling algorithm – Completion Time and Response Time.

2. Completion Time

Completion time in CPU scheduling refers to the point at which a process completes its execution and terminates normally. It is important in scheduling because it provides a metric to evaluate the overall performance of a system. A system with a low completion time is considered more efficient as tasks are completed in a shorter amount of time.

Some examples of scheduling algorithms that use completion time as a metric include Earliest Deadline First (EDF), Rate Monotonic Scheduling (RMS), and Least Laxity First (LLF).

It is the sum of the arrival time, the wait time, and the execution time:

Where:

• Arrival Time () is the time when a task arrives in the system and is ready to be executed
• Execution Time () is the amount of time it takes for a task to complete its execution once it starts
• Waiting Time () is the amount of time a task spends waiting in the queue to be executed before its execution begins

2.1. Factors Affecting Completion Time

The factors affecting completion time include the processing time required for each task, the number of tasks to be executed, and the priority assigned to each task.

3. Response Time

Response Time measures the time it takes for the first response to be received after a task has been initiated. It is important in scheduling because it provides a metric to evaluate the responsiveness of a system. A system with a low response time is considered more responsive as the first response is received quickly after a task is initiated.

Some examples of scheduling algorithms that use response time as a metric include Round Robin Scheduling and First-Come First-Served (FCFS) Scheduling.

The response time is calculated using the formula:

3.1. Factors Affecting Response Time

The factors affecting response time include:

• The processing time required for each task
• Number of tasks in the system
• Priority assigned to each task
• And the available system resources

4. An Example for Clarification

Let’s consider a scenario where 3 tasks (, , and ) need to be executed in a computing system. Given execution time and arrival time for each task:

Let’s assume that the tasks are executed using a First-Come First-Served (FCFS) scheduling algorithm, which prioritizes tasks based on their arrival time.

At time()=0, arrives and starts execution without waiting (i.e. Start time = 0, Wait time – 0):

At =1,   arrives and is still executing. waits in the wait queue:

At =2,  completes execution, arrives, and starts execution (i.e. wait time=1, while waits in the wait queue):

At =5,  completes execution. starts execution (i.e. wait time=3):

Finally At =6, completes execution:

The completion time can be calculated thus:

Completion Time for  = 0 + 2 + 0 = 2
Completion Time for  = 1 + 3 + 1 = 5
Completion Time for  = 2 + 1 + 3 = 6

Also, the response time can be calculated thus:

Response Time for A = 0 – 0 = 0
The Response Time for B = 2 – 1 = 1
Response Time for C = 5 – 2 = 3

5. Completion Time vs. Response Time

Let’s summarize the difference between Completion Time and Response Time by the aid of a table:

Completion time and response time are both important performance metrics in CPU scheduling. However, they measure different aspects of system performance. Completion time provides information about the total time it takes for a task to complete its execution. Whereas, response time provides information about the responsiveness of the system. Both metrics can be used to evaluate and improve the performance of CPU scheduling algorithms.

6. Conclusion

In this article, we discussed Completion Time and Response Time, two important metrics in CPU scheduling. They are used in scheduling to measure the performance of a system. Completion time measures the total amount of time it takes for a task to be completed, while response time measures the amount of time it takes for the first response to be received after a task has been initiated.

The choice between the two metrics will depend on the system’s specific requirements and the application being executed. It is important to carefully consider both metrics when designing a scheduling algorithm for a computing system to ensure that it meets its performance goals.