P3L1 Scheduling - Introduction

Question 1

Visual Metaphor

An OS scheduler is like ___________________________

1. Toy shop manager dispatches orders immediately as they arrive is like ___________
   
   • This method reduces ______________
2. Toy shop manager dispatches simple orders first is like ________________
   
   • This method maximizes ___________
3. Toy shop manager dispatches complex orders first is like ______________
   
   • This method utilizes ____________

Answer 1

… a toy shop manager

1. Toy shop manager dispatches orders immediately as they arrive is like First Come First Served (FCFS)
   
   • This method reduces order processing overhead
2. Toy shop manager dispatches simple orders first is like Shortest Jobs First (SJF)
   
   • This method maximizes throughput
3. Toy shop manager dispatches complex orders first is like scheduling complex tasks first, interleave short jobs
   
   • This method utilizes resources (like CPU, devices, memory)

Question 2

As in the toy shop manager metaphor for OS scheduling, list 3 approaches an OS can take to scheduling tasks (threads/processes) and the advantages of each:

Answer 2

1. first come first served (less overhead to decide things)
2. Shortest Job First (SJF) - high throughput
3. Complex jobs first - uses resources, cpu, memory, devices .. once in a while do short jobs to keep throughput high

Question 3

The CPU scheduler decides how and when the processes (and their threads) access the ______ _____ .

The scheduler concerns the scheduling of both ____ level tasks and _____ level tasks.

The scheduler selects one of the tasks in the ______ ______ and then schedules it on the ____.

Answer 3

The CPU scheduler decides how and when the processes (and their threads) access the shared CPUs.

The scheduler concerns the scheduling of both user level tasks and kernel level tasks.

The scheduler selects one of the tasks in the ready queue and then schedules it on the CPU.

Question 4

List 4 ways a task may become ready for scheduling

Answer 4

1. I/O request - An I/O operation they have been waiting on is completed
2. Time slice expired - Wake interrupt
3. Fork - Task was created
4. Wait for interrupt - Interrupted thread (was ready on the CPU, so when interrupted goes right on the ready queue)

Question 5

The OS scheduler runs when the CPU becomes ______.

For example, if a task makes an I/O request and is placed on the ______ queue for that device, the scheduler has to select a new task from the _______ queue to run on the CPU.

Answer 5

The OS scheduler runs when the CPU becomes idle.

For example, if a task makes an I/O request and is placed on the wait queue for that device, the scheduler has to select a new task from the ready queue to run on the CPU.

Question 6

A common way that schedulers share time within the system is by giving each task some amount of time on the CPU. This is known as a _______. When a _______expires, the scheduler must be run.

Once the scheduler selects a task to be scheduled, that task is dispatched onto the _______.

The operating system

1. ______ ______ to the new task
2. enters _____ mode
3. sets the _______ ______, and execution begins.

In summary, the objective of the OS scheduler is to choose the next task to run from the ready queue.

Answer 6

A common way that schedulers share time within the system is by giving each task some amount of time on the CPU. This is known as a timeslice. When a timeslice expires, the scheduler must be run.

Once the scheduler selects a task to be scheduled, that task is dispatched onto the CPU.

The operating system

1. context switches to the new task
2. enters user mode
3. sets the program counter, and execution begins.

In summary, the objective of the OS scheduler is to choose the next task to run from the ready queue.

Question 7

In one sentence, what is the objective of the OS scheduler?

Answer 7

The objective of the scheduler is to choose the next task to run from the ready queue

Question 8

What’s a task in the context of scheduling?

Answer 8

A process or a thread

Question 9

List 2 questions to answer in the design of an OS scheduler

Answer 9

1. Which task to select? (scheduling policy/algorithm).
2. How to schedule?(runqueue data structure)

Question 10

What’s the name of the main scheduling data structure?

Answer 10

runqueue

Question 11

True or False?

For each scheduling algorithm, the scheduling data structure is different.

Answer 11

True because runqueue scheduling algorithm is tightly coupled to the data structure that best supports it.

Question 12

In summary, the objective of the OS scheduler is to choose the next task to run from the ________ ________

How do we decide which task to be selected? This depends on the scheduling policy/algorithm.

How does the scheduler accomplish its job?

This depends very much on the structure of ready queue, also known as a runqueue.

The design of the _______ and the _________ algorithm are tightly coupled: a _____ _________that is optimized for one ________ may be a poor choice for implementing another.

Answer 12

In summary, the objective of the OS scheduler is to choose the next task to run from the ready queue.

How do we decide which task to be selected? This depends on the scheduling policy/algorithm.

How does the scheduler accomplish its job?

This depends very much on the structure of ready queue, also known as a runqueue.

The design of the runqueue and the scheduling algorithm are tightly coupled: a data structure that is optimized for one algorithm may be a poor choice for implementing another.