Chapter 5 - CPU Scheduling Flashcards
what is the primary purpose of CPU scheduling?
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
what is the CPU/IO burst cycle?
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
what is in the ready queue for the CPU scheduler?
PCB’s, process control blocks
under what four circumstances to CPU scheduling decisions get made?
- when a process switches from running to waiting
- when a process switches from running to ready
- when a process switches from waiting state to ready state
- when a process terminates
what is non-preemptive scheduling?
once the CPU has scheduled a process, it keeps the CPU until it releases it either by terminating or waiting
what is preemptive scheduling?
the scheduler decides when the process should be moved back into a ready state
what is the main drawback of preemptive scheduling?
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
what is the dispatcher?
the module that gives control of the CPU’s core to the process selected by the scheduler
what does the process of dispatching look like (handing off control to the process)
- switching context from one process to another
- switching to user mode
- jumping to the proper location in the user program that it was last running at
what is dispatch latency?
the time it takes for the dispastcher to stop one process and start the next
what are the 5 criterium to think about when considering CPU scheduling algorithms?
CPU Utilization, Throughput, Turnaround Time, Waiting Time, Response Time
What generally are the two things that get optimized for in scheduling algorithms?
CPU Utilization, Throughput
what is generally considered the “simplest” scheduling algorithm?
First come first served! the process that requests the CPU first is allocated the CPU first….FIFO baby
what is the drawback of FCFS?
making short processes wait behind long ones, it’s also non-preemptive
why typically has longer bursts? CPU Bound or IO Bound processes?
CPU Bound
What is the Convoy effect?
When CPU bound processes cause IO bound ones to wait
What is Shortest Job First Scheduling? SJF?
it prioritizes the process with the shortest CPU burst, uses FCFS in event of a tie breaker
how does Shortest Job First estimate the length of the CPU burst of a process?
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
what is Round Robin Scheduling?
same as FCFS but with the ability to preempt a process to allow the system to switch between processes more easily
how does Round Robin Scheduling work?
it effectively makes the CPU bursts more uniform leading to a more consistent distribution of CPU burst time
what is Priority CPU Scheduling?
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
what factors may play into priority scheduling?
cpu average burst time, memory requirements, open files
what interruption scheme is priority scheduling?
can be both preemptive and non-preemptive
what is a major problem with Priority Scheduling?
a long process could be completely starved of compute time
what is a solution to idefinite blocking or process starvation?
including process age in the priority algorithm
what is multilevel queue scheduling?
each priority level is placed into it’s own queue
what is asymmetric multiprocessing?
when one core handles all the scheduling and the other cores just execute processes
what is symmetric multiprocessing?
every processor is self scheduling
how does symmetric multiprocessing solve race conditions?
by having each processor have it’s own thread/process queue
What is chip multithreading (CMT) and why is it important?
CMT assigns multiple hardware threads to each processing core allowing the core to switch between threads if one stalls
what are the two main types of multithreading for processing cores?
course-grained (switches on long latency events) and fine-graned (switches frequently at low cost)
How many levels of scheduling are required for a multithreaded, multicore processor and what are they?
two levels:
1. OS Scheduling of software threads
2. Core level scheduling of hardware threads
how does load balancing work in a symmetric multiprocessing environment?
each thread queue is evenly distributed so that each core doesn’t get too many processes
what is processor affinity
when a process doesn’t want to change thread queues because there is some cached data it is relying upon
what are the two types of high level scheduling concepts for an OS?
soft real time and hard real time…hard real time means a process has to run critically when it’s told to run
what is rate-monotonic scheduling?
uses a priority policy with preemption. lower priority processes get preempted
what is earliest deadline firs (EDF)
assigns priorities according to the deadline of when the process needs to be executed by
what is proportional share scheduling?
allocations proportional CPU time to processes
what scheduler does Linux kernel use?
the Completely Fair Scheduler. it uses priority classes
