9. Intro to Scheduling

Question 1

What are the three states of a thread?

Answer 1

Running (executing instructions on a CPU), ready (not executing, but capable), and waiting/blocking/sleeping (not executing, not able to start yet)

Question 2

Why does a thread transition from running to ready?

Answer 2

it was descheduled

Question 3

Why does a thread transition from running to waiting?

Answer 3

it performed a blocking system call

Question 4

Why does a thread transition from waiting to ready?

Answer 4

the event the thread was waiting for happened

Question 5

Why does a thread transition from ready to running?

Answer 5

it was scheduled

Question 6

Why does a thread transition from running to terminated?

Answer 6

it exited or hit a fatal exception

Question 7

What is scheduling?

Answer 7

The process of choosing the next thread (or threads) to run on the CPU(s)

Question 8

Why do we schedule threads?

Answer 8

We generally have more threads than cores to run them on, so we need to multiplex the CPU.

We (with the kernel) are also in charge of allocating the CPU and must try to make good decisions so applications can run properly

Question 9

When are the 4 times that scheduling happens?

Answer 9

1. When a thread voluntarily gives up the CPU by calling yield().
2. When a thread makes a blocking system call and must sleep until the call completes
3. When a thread exits.
4. When the kernel decides that a thread has run for long enough (preemptive policy, not cooperative)

Question 10

What makes a scheduling policy preemptive as opposed to cooperative?

Answer 10

The kernel preempts (or stops) a thread that has not requested to be stopped

Question 11

What is the rationale behind having a way for threads to voluntarily give up the CPU?

Answer 11

yield() can be a useful way of allowing a well-behaved thread to tell the CPU that it has no more useful work to do (which is inherently cooperative)

Question 12

What is the mechanism component of scheduling?

Answer 12

How we switch between threads

Question 13

What is the policy component of scheduling?

Answer 13

How we choose the next thread to run

Question 14

How do we switch between threads?

Answer 14

Perform a context switch and move threads between the ready, running, and waiting queues

Question 15

Is this an example of scheduling policy or mechanism:

Deciding what thread to run

Answer 15

Policy

Question 16

Is this an example of scheduling policy or mechanism:

Context switch

Answer 16

Mechanism

Question 17

Is this an example of scheduling policy or mechanism:

Maintaining the running, ready, and waiting queues

Answer 17

Mechanism

Question 18

Is this an example of scheduling policy or mechanism:

Giving preference to interactive tasks

Answer 18

Policy

Question 19

Is this an example of scheduling policy or mechanism:

Using timer interrupts to stop running threads

Answer 19

Mechanism

Question 20

Is this an example of scheduling policy or mechanism:

Choosing a thread to run at random

Answer 20

Policy

Question 21

Why (and in what ways) does the scheduling implementation impact other parts of the system?

Answer 21

Using other system resources requires the CPU.

Intelligent scheduling makes a modestly-powered system seem fast and responsive.

Stupid scheduling makes a powerful system seem sluggish and laggy.

Question 22

What is system “responsiveness”?

Answer 22

When you give the computer an instruction or input, it responds in a timely manner (it doesn’t have to finish, just show you that it’s started)

Question 23

What are some examples of responsive tasks we use computers for?

Answer 23

Web browsing (clicking a link retrieves a webpage), editing (typing a key, it’s rendered on screen), chatting (hit send, text transmits to target)

Question 24

What is system “continuity”?

Answer 24

When you ask the computer to perform a continuous task, it does so smoothly

Question 25

How does system continuity imply active waiting?

Answer 25

You are not interacting with the computer, but you are expecting it to continue to perform a task you have initiated

Question 26

What are some examples of continuous tasks?

Answer 26

Blinking a cursor, playing music or a movie, and web animations

Question 27

What is system “completion”?

Answer 27

When we ask the computer to perform a task - or it performs one on our behalf - which we expect to take a long time, we want it to complete (eventually)

Question 28

How does completion imply passive waiting?

Answer 28

You are asking the computer to continue to deliver interactive performance while working on your long-running tasks (background tasks)

Question 29

What are some examples of background tasks?

Answer 29

Performing a system backup and indexing the files on my computer

Question 30

What are the conflicting goals of scheduling?

Answer 30

Scheduling is a balance between meeting deadlines and optimizing resource allocation.

Question 31

What does it mean to achieve optimal resource allocation?

Answer 31

Carefully allocate tasks so that all resources are constantly in use.

Question 32

Give an example of how responsiveness requires unpredictable deadlines for processes.

Answer 32

When the user moves the mouse, I need to be ready to stop the current process redraw the cursor

Question 33

Given an example of how continuity requires predicable deadlines

Answer 33

Every 5 ms I need to write more data to the sound card buffer

Question 34

What metrics do we use to evaluate a scheduling algorithm?

Answer 34

How well does it meet deadlines and how completely does it allocate system resources?

Note: on human-facing systems, deadlines (or interactivity) usually wins

Question 35

How can a failure to meet process deadlines result in a fatal error (as opposed to an annoying “laggy” experience)?

Answer 35

The motion_stop function needed to be called but the OS didn’t get around to scheduling the thread set to call that function before the robot drove off a cliff.