Scheduling

Question 1

What does the dispatcher do

Answer 1

it performs the actual process switch (mechanism)
- saving/restoring process context
-switching to user mode

Question 2

What does CPU scheduler do?

Answer 2

It selects the next process to run (policy)
-schedulers try to meet goals, provide fairness and adhere to priorities

Question 3

What are the two types of schedulers?

Answer 3

1. Short-term Scheduler: selects which process should be executed next and allocates CPU, it is invoked frequently
2. Long-term Scheduler: selects which processes should be brought into the ready queue, it is invoked infrequently, it controls the degree of multiprogramming

Question 4

enumerate three different process scheduling queues

Answer 4

1. Job queue: Set of all processes in the system
2. Ready queue: Processes in main memory, state: ready and waiting
3. Device queues: Process waiting for an I/O device

Question 5

Explain the following terms:
Throughput
Turnaround time
Response time
Waiting time

Answer 5

Throughput: # of processes that complete per time unit

Turnaround time: time from submission to completion of a job

Response time: Time from request to first response (first time it is dispatched)

Waiting time: time each process waits in the ready queue

Question 6

First-Come First-Served

Answer 6

Schedule the processes in the order of arrival
-prone to Convoy effect (a process with high burst time makes a process with lower burst time to wait until it’s completion)
=> Average turnaround time depends on arrival in queue

Question 7

Shortest Job First

Answer 7

• has optimal average turnaround, waiting and response times
• challenge: can’t know job lengths in advance
• solution: predict length of next CPU burst for each process -> schedule the process with the shortest burst next

Question 8

Preemptive Shortest Job First

Answer 8

Idea: SJF, but preempt periodically to make a new scheduling decision; at each time slice schedule job with the shortest remaining time next

Question 9

Round Robin

Answer 9

Idea: each process runs for a small unit of CPU time
preempt processes that haven’t blocked by the end of the time slice
append current thread to end of run queue, run next thread
time slice length needs to balance interactivity and overhead

Question 10

Virtual Round Robin

Answer 10

RR is unfair for I/O bound jobs, they block before they use up their entire quantum
Idea: Put jobs that didn’t use up their quantum into an additional queue

Question 11

Priority scheduling

Answer 11

Associate priority number with each process
Strict priority scheduling: processes with low priorities never execute if there is always a process runnable with a higher priority => starvation

Question 12

Multi-level Feedback Queue

Answer 12

Goals: give higher priority to I/O-bound jobs, give low priority to CPU-bound jobs, but run them for longer at a time
Idea: Different queues with different priorities and time slice lengths

Question 13

Priority Donation

Answer 13

Problem: process B may wait for result of process A (A has lower priority than B)
Solution: Give priority of B as long as B waits for a

Question 14

Lottery scheduling

Answer 14

Issue number of lottery tickets to processes
- more tickets for processes with higher priority
-amount of tickets controls average proportion of CPU for each process

Question 15

What is the purpose of scheduling

Answer 15

To find a mapping of processes to resources, so that each process will eventually get the resources it needs.

Question 16

what happens when a process is blocking?

Answer 16

It is the state transition from running to waiting. A process needs to wait when it wants to access a resource that isn’t immediately available. It can’t make progress on the CPU so it is not considered by the scheduler.
1. Waiting for I/O device: any request to devices such as hard disks has to wait a usually unknown time for completion.
2. Waiting for other processes: synchronization mechanisms such as mutexes can block a process.

Question 17

What quantitative metrics can be used to estimate the quality of a scheduling policy?

Answer 17

1. Processor utilization: Percentage of time that a processor is not idle
   2.Throughput: Number of processes/threads completed per unit of time
2. Turnaround time: Time from submission of a process to its completion including the time spent waiting in queues
3. Waiting time: Time a process spends in ready queue
4. Response time: Time from submission of a request until the first response is produced

Question 18

What kind of hardware support is required for an OS that implements a non-cooperative scheduling policy?

Answer 18

The OS must be able to interrupt a running process, as the OS can’t regain control by itself.

Question 19

Pros and cons of choosing short vs long timeslice lengths

Answer 19

(long)
+ fewer context switches per time unit => can improve throughput
- responsiveness of the system decreases as ready processes have to wait longer until they are allowed to run again

Question 20

Compare preemptive vs non-preemptive SJF

Answer 20

SJF: always selects the job with the shortest remaining time next

Preemptive SJF: Makes a new scheduling decision periodically and when a new process arrives in the ready queue.

Question 21

How can starvation be avoided with multilevel feedback queue?

Answer 21

Priority boost: After some time period S, move all the jobs in the system to the topmost queue