Chapter 5 - CPU Scheduling

Question 1

what is the primary purpose of CPU scheduling?

Answer 1

to ensure that the computer is always working on a process (no idle time). it selects a process to run from the ready queue when the CPU goes idel

Question 2

what is the CPU/IO burst cycle?

Answer 2

the CPU alternates between CPU and IO bound tasks, often times it alternates between the two or has several CPU bound bursts in a row

Question 3

what is in the ready queue for the CPU scheduler?

Answer 3

PCB’s, process control blocks

Question 4

under what four circumstances to CPU scheduling decisions get made?

Answer 4

1. when a process switches from running to waiting
2. when a process switches from running to ready
3. when a process switches from waiting state to ready state
4. when a process terminates

Question 5

what is non-preemptive scheduling?

Answer 5

once the CPU has scheduled a process, it keeps the CPU until it releases it either by terminating or waiting

Question 6

what is preemptive scheduling?

Answer 6

the scheduler decides when the process should be moved back into a ready state

Question 7

what is the main drawback of preemptive scheduling?

Answer 7

it can cause race conditions if two processes share data and one is preempted for the other and the other updates the data that the first was going to update

Question 8

what is the dispatcher?

Answer 8

the module that gives control of the CPU’s core to the process selected by the scheduler

Question 9

what does the process of dispatching look like (handing off control to the process)

Answer 9

1. switching context from one process to another
2. switching to user mode
3. jumping to the proper location in the user program that it was last running at

Question 10

what is dispatch latency?

Answer 10

the time it takes for the dispastcher to stop one process and start the next

Question 11

what are the 5 criterium to think about when considering CPU scheduling algorithms?

Answer 11

CPU Utilization, Throughput, Turnaround Time, Waiting Time, Response Time

Question 12

What generally are the two things that get optimized for in scheduling algorithms?

Answer 12

CPU Utilization, Throughput

Question 13

what is generally considered the “simplest” scheduling algorithm?

Answer 13

First come first served! the process that requests the CPU first is allocated the CPU first….FIFO baby

Question 14

what is the drawback of FCFS?

Answer 14

making short processes wait behind long ones, it’s also non-preemptive

Question 15

why typically has longer bursts? CPU Bound or IO Bound processes?

Answer 15

CPU Bound

Question 16

What is the Convoy effect?

Answer 16

When CPU bound processes cause IO bound ones to wait

Question 17

What is Shortest Job First Scheduling? SJF?

Answer 17

it prioritizes the process with the shortest CPU burst, uses FCFS in event of a tie breaker

Question 18

how does Shortest Job First estimate the length of the CPU burst of a process?

Answer 18

the scheduler users historical data from the same process and it’s essentially a weighted average to predict the next cpu burst for that process

Question 19

what is Round Robin Scheduling?

Answer 19

same as FCFS but with the ability to preempt a process to allow the system to switch between processes more easily

Question 20

how does Round Robin Scheduling work?

Answer 20

it effectively makes the CPU bursts more uniform leading to a more consistent distribution of CPU burst time

Question 21

what is Priority CPU Scheduling?

Answer 21

a more general version of the SJF. it does this by taking the inverse of the next predicted CPU burst. The higher the CPU burst, the lower the priority

Question 22

what factors may play into priority scheduling?

Answer 22

cpu average burst time, memory requirements, open files

Question 23

what interruption scheme is priority scheduling?

Answer 23

can be both preemptive and non-preemptive

Question 24

what is a major problem with Priority Scheduling?

Answer 24

a long process could be completely starved of compute time

Question 25

what is a solution to idefinite blocking or process starvation?

Answer 25

including process age in the priority algorithm

Question 26

what is multilevel queue scheduling?

Answer 26

each priority level is placed into it’s own queue

Question 27

what is asymmetric multiprocessing?

Answer 27

when one core handles all the scheduling and the other cores just execute processes

Question 28

what is symmetric multiprocessing?

Answer 28

every processor is self scheduling

Question 29

how does symmetric multiprocessing solve race conditions?

Answer 29

by having each processor have it’s own thread/process queue

Question 30

What is chip multithreading (CMT) and why is it important?

Answer 30

CMT assigns multiple hardware threads to each processing core allowing the core to switch between threads if one stalls

Question 31

what are the two main types of multithreading for processing cores?

Answer 31

course-grained (switches on long latency events) and fine-graned (switches frequently at low cost)

Question 32

How many levels of scheduling are required for a multithreaded, multicore processor and what are they?

Answer 32

two levels:
1. OS Scheduling of software threads
2. Core level scheduling of hardware threads

Question 33

how does load balancing work in a symmetric multiprocessing environment?

Answer 33

each thread queue is evenly distributed so that each core doesn’t get too many processes

Question 34

what is processor affinity

Answer 34

when a process doesn’t want to change thread queues because there is some cached data it is relying upon

Question 35

what are the two types of high level scheduling concepts for an OS?

Answer 35

soft real time and hard real time…hard real time means a process has to run critically when it’s told to run

Question 36

what is rate-monotonic scheduling?

Answer 36

uses a priority policy with preemption. lower priority processes get preempted

Question 37

what is earliest deadline firs (EDF)

Answer 37

assigns priorities according to the deadline of when the process needs to be executed by

Question 38

what is proportional share scheduling?

Answer 38

allocations proportional CPU time to processes

Question 39

what scheduler does Linux kernel use?

Answer 39

the Completely Fair Scheduler. it uses priority classes