Quiz 4/CPU Scheduling Flashcards
Basic Concepts
Maximum CPU utilization obtained with multiprogramming.
CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait.
CPU burst followed by I/O burst.
CPU burst distribution is of main concern.
The final CPU burst ends with a system request to terminate execution.
CPU-burst times
An I/O-bound program typically has many short CPU bursts. A CPU-bound program might have a few long CPU bursts.
This distribution can be important in the selection of an appropriate CPU-scheduling algorithm.
CPU Scheduler
Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them
->Queue may be ordered in various ways (FIFO queue, priority queue, tree, unordered linked list).
->Records in the queue are generally PCBs of the processes.
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state (e.g., wait() for child)
2. Switches from running to ready state (e.g., an interrupt occurs)
3. Switches from waiting to ready (e.g., I/O completion)
4. Terminates
If Scheduling occurs only under 1 and 4 is nonpreemptive (preemptive can lead to race conditions)
->Once the CPU has been allocated to a process, the process keeps the CPU until it releases the CPU either by terminating or by switching to the waiting state.
All other scheduling is preemptive (used in real-time systems, allow interactivity)
->Consider access to shared data
->Consider preemption while in kernel mode
->Consider interrupts occurring during crucial OS activities
Dispatcher
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
- > switching context
- > switching to user mode
- > jumping to the proper location in the user program to restart that program (program counter contains the next instruction, this is used to determine where we “jump” to)
Dispatch latency – time it takes for the dispatcher to stop one process and start another running
Scheduling Criteria
Various scheduling algorithms compared based on:
CPU utilization – keep the CPU as busy as possible
->Typically from 40% (light load) to 90% (heavy load)
Throughput – # of processes that complete their execution per time unit
->May be 1 proc/hr (long processes) or 10 proc/hr (short processes)
Turnaround time – amount of time to execute a particular process (time it takes from process start to finish)
->(waiting to get into memory) + (waiting in the ready queue) + (executing on the CPU) + (doing I/O)
Waiting time – amount of time a process has been waiting in the ready queue
->Does NOT include I/O time!!!
Response time – amount of time it takes from when a request was submitted until the first response is produced,
- > Different from turnaround time!
- > Good for Timesharing systems.
Scheduling Algorithm Optimization Criteria
DESIRABLE: Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time
GENERALLY: optimize the avg measure.
->However, under some circumstances, we prefer to optimize the minimum or maximum values rather than the average. For example, to guarantee that all users get good service, we may want to minimize
the maximum response time.
- Variance could be minimized too*
- > Investigators have suggested that, for interactive systems (such as desktop
systems) , it is more important to minimize the variance in the response time than to minimize the average response time. A system with reasonable and predictable response time may be considered more desirable than a system that is faster on the average but is highly variable. However, little work has been done on CPU-scheduling algorithms that minimize variance.
First-Come, First-Served (FCFS) Scheduling
Nonpreemptive!
With this scheme, the process that requests the CPU first is allocated the CPU first.
Nonpreemptive algorithm!
The implementation of the FCFS policy is easily managed with a FIFO queue.
- > When a process enters the ready queue, its PCB is linked onto the tail of the queue.
- > When the CPU is free, it is allocated to the process at the head of the queue.
- > The running process is then removed from the queue.
On the negative side, the average waiting time under the FCFS policy is often quite long.
Convoy Effect
Seen in FCFS
Consider one CPU-bound & many I/O-bound processes…
convoy effect: all the other processes wait for the one big process to get off the CPU.
This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.
Not good for timesharing systems because it allows one process to keep the CPU for an extended period.
Shortest-Job-First (SJF) Scheduling
aka Shortest-Next-CPU-Burst
Can be preemptive or non-preemptive
Associate with each process the length of its next CPU burst
- > Use these lengths to schedule the process with the shortest time
- > If next CPU burst of two processes are the same, FCFS is used to break the tie.
SJF is optimal – gives minimum average waiting time for a given set of processes (for scheduling algorithms)
- > The difficulty is knowing the length of the next CPU request
- > Could ask the user
- ->For long-term jobs where the user specifies the process time limit upon job submission.
- –>Estimated Low: faster response but if too low it may exceed the time limit and require re-submission.
- –>Need to be an accurate estimation!
Since SJF cannot be implemented at the level of short-term CPU scheduling, we can use approximation to determine the length of the next CPU burst.
Determining Length of Next CPU Burst
Can only estimate the length – should be similar to the previous one
->Then pick process with shortest predicted next CPU burst
Can be done by using the length of previous CPU bursts, using exponential averaging
- 𝑡_𝑛= actual length of 𝑛^𝑡ℎ CPU burst
- 𝜏_(𝑛+1)= predicted value for the next CPU burst
- 𝛼, 0≤𝛼≤1
- Define: 𝜏_(𝑛=1 )= 𝛼𝑡_𝑛 + (1−𝛼)𝜏_𝑛. 𝜏_𝑛=𝑝𝑟𝑒𝑣𝑖𝑜𝑢𝑠 𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑒𝑑 𝑣𝑎𝑙𝑢𝑒
Commonly, α set to ½
α = 0, recent history has no effect
α = 1, only most recent CPU burst matters
α = 1/2, recent and past history equally weighted
->Since both α and (1 - α) are less than or equal to 1, each successive term has less weight than its predecessor!!
Preemptive version called shortest-remaining-time-first
Shortest-Remaining-Time-First
Preemptive SJF
The next CPU burst of the newly arrived process may be shorter than what is left of the currently executing process.
->A preemptive SJF algorithm will preempt the currently executing process, whereas
->A nonpreemptive SJF algorithm will allow the currently running process to finish its CPU burst
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Takes into consideration the remaining time! P1 remaining time at 1 is 7 when P2 arrives, since P2 has a burst of 3 we will switch to P2. When P3 arrives P2 is at 3, P1 is still at 7. P2 will continue running until P4 arrives, P1 is at 7, P2 is at 2, P3 is at 7, we continue with P2 until it finishes at 5….
Preemptive avg waiting time: 6.5ms
Nonpreemptive avg waiting time: 7.75
Priority Scheduling
A priority number (integer) is associated with each process
The CPU is allocated to the process with the highest priority (smallest integer -> highest priority)
- > Preemptive
- > Nonpreemptive
SJF is priority scheduling where priority is the inverse of predicted next CPU burst time
Problem (All priority based scheduling): Starvation – low priority processes may never execute
- > In a heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU
- > **Rumor has it that when they shut down the IBM 7094 at MIT in 1973, they found a low-priority process that had been submitted in 1967 and had not yet been run.
Solution: Aging – as time progresses increase the priority of the process
Round-Robin Scheduling
Preemptive FIFO
Good for interactive systems
Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.
If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.
Timer interrupts every quantum to schedule next process
Performance
- > q large (finish jobs before q is reached, CPU burst is higher than quantum) => RR turns into FIFO
- > q small => q must be large with respect to context switch, otherwise overhead is too high
**Rule of thumb: 80% of the CPU bursts should be shorter than the time quantum
Multilevel Queue
Ready queue is partitioned into separate queues (processes are divided into groups), e.g.:
- > foreground (interactive)
- > background (batch)
Process permanently in a given queue
Each queue has its own scheduling algorithm, example:
- > foreground – RR
- > background – FCFS
Scheduling must be done between the queues:
- > Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
- > Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes;
- ->i.e., 80% to foreground in RR
- ->20% to background in FCFS
Multilevel Feedback Queue
Most complex of the general scheduling algorithms
A process can move between the various queues; aging can be implemented this way (used to prevent starvation)
Multilevel-feedback-queue scheduler defined by the following parameters:
- > number of queues
- > scheduling algorithms for each queue
- > method used to determine when to upgrade a process
- > method used to determine when to demote a process
- > method used to determine which queue a process will enter when that process needs service
**It is the most complex algorithm since defining the best scheduler requires some means by which to select values for all the parameters.
