P3L1 Scheduling - Run to Completion

Question 1

What is Run to Completion scheduling?

Answer 1

Run To Completion scheduling assumes that

once a task is assigned to a CPU, it will run on that CPU until it is finished.

Question 2

List 4 metrics used to compare schedulers

Answer 2

When it comes to comparing schedulers, some common metrics include:

1. throughput
2. average job completion time
3. average job wait time
4. CPU utilization

Question 3

The first and the simplest algorithm is _______________________. In this algorithm, the tasks are simply scheduled in the order in which they arrive. When a task completes, the scheduler will pick the ______ task in order.

A simple way to organize these tasks would be a queue structure, in which the tasks can be enqueued to the ______ of the ______, and dequeued from the ______ of the ______ by the scheduler in a _______ manner. All the scheduler needs to know is the head of the queue, and how to dequeue tasks.

Answer 3

The first and the simplest algorithm is First Come First Serve (FCFS). In this algorithm, the tasks are simply scheduled in the order in which they arrive. When a task completes, the scheduler will pick the next task in order.

A simple way to organize these tasks would be a queue structure, in which the tasks can be enqueued to the back of the queue, and dequeued from the front of the queue by the scheduler in a FIFO manner. All the scheduler needs to know is the head of the queue, and how to dequeue tasks.

Question 4

Shortest Job First (SJF) algorithm:

1. What type of data structure?
2. How is it used?
3. Assuming no preemption and all jobs arrive at same time. Tasks T1 (1 second), T2 (10 seconds), T3 (1 seconds). Using SJF, calculate:

• Throughput
• Average completion time
• Average wait time

Answer 4

1. ordered queue or ordered tree (try to mitigate insertion overhead)
2. For queue, keep ordered, just pull from front. Or for tree, keep it balanced and then take leftmost leaf node
3. Tasks T1 (1 second), T2 (10 seconds), T3 (1 seconds) arrive in that order. Calculate:

• 3 tasks take 12 seconds .. so 3/12 .. 0.25 sec
• Total completion time 1 + 2 + 12 = 15
  Then for average: 15/3 = 5 sec
• Wait: (0 + 1 + 2). Then 3/3 = 1 sec

Question 5

First Come First Served (FCFS) algorithm:

1. What type of data structure?
2. How is it used?
3. Tasks T1 (1 second), T2 (10 seconds), T3 (1 seconds) arrive in that order. Calculate:

• Throughput
• Average completion time
• Average wait time

Answer 5

1. queue, like linked list
2. Add to back, pull out from front, maintain the head and tail
3. Tasks T1 (1 second), T2 (10 seconds), T3 (1 seconds) arrive in that order. Calculate:

• 3 tasks take 12 seconds .. so 3/12 .. 0.25 sec
• Total completion time 1 + 11 + 12 = 24
  Then for average: 24/3 = 8 sec
• Wait: (0 + 1 + 11). Then 12/3 = 4 sec