P3L1 Scheduling - Design

Question 1

True or False?

The runqueue is always implemented as a FIFO queue

Answer 1

False. The runqueue data structure is only logically a queue. It can be implemented as multiple queues or even a tree.

What’s important is that the data structure is designed so that the scheduler can easily determine which task should be scheduled next.

Question 2

The runqueue data structure is designed so that the scheduler can easily determine which task should be scheduled ______.

For example, if we want I/O and CPU bound tasks to have different timeslice values, we can either place I/O and CPU bound tasks in the same runqueue and have the scheduler check the ______, or we can place them in ________ runqueues.

One common data structure is a ______ queue structure that maintains _________ distinct queues, each differentiated by their _______ value.

I/O intensive tasks will be associated with the queue with the ________ timeslice values, while CPU intensive tasks will be associated with the queue with the _________ timeslice values.

Answer 2

The runqueue data structure is designed so that the scheduler can easily determine which task should be scheduled next.

For example, if we want I/O and CPU bound tasks to have different timeslice values, we can either place I/O and CPU bound tasks in the same runqueue and have the scheduler check the type, or we can place them in separate runqueues.

One common data structure is a multi queue structure that maintains multiple distinct queues, each differentiated by their timeslice value.

I/O intensive tasks will be associated with the queue with the smallest timeslice values, while CPU intensive tasks will be associated with the queue with the largest timeslice values.

Question 3

Describe the Multi Level Feedback Queue (for which Fernando Corbato received the Turing Award)

Answer 3

When a new task enters the system, we will place it on the topmost queue (the one with the lowest timeslice). If the task yields before the timeslice has expired, we have made a good choice! We will place this task back on this queue when it becomes runnable again. If the task has to be preempted, this implies that the task was more CPU intensive than we thought, and we push it down to a queue with a longer timeslice. If the task has to be preempted still, we can push the task down even further, to the bottom queue.

If a task in a lower queue begins to frequently release the CPU due to I/O waits, the scheduler may boost the priority of that task and place it in a queue with a smaller timeslice.