CPU Scheduling Flashcards
What is a burst cycle?
CPU does not work continuously. It computes in bursts, before waiting for a I/O burst. The distribution of these bursts, is the main concern of the OS.
Do most processes use short CPU bursts or longer bursts?
Most OS processes are interactive, therefore spend the majority of their time waiting for I/O, interleaved with short bursts of computation.
Which two state transition scenarios doesn’t require any decisions from the scheduler?
From running to wait state, and process termination.
What is the difference between pre-emptive and co- operating scheduling?
Pre-emptive is when OS interrupts process while it is running. This leads to race conditions. Co-operative scheduling means the process releases CPU when it doesn’t need it anymore.
Why is pre-emptive scheduling preferred?
CPU is most valuable resource. OS should keep control over how it used.
What does the dispatcher do?
It does a context switch. Save current process info to its PCB, and move in PCB of new process. It may have to switch hardware from user to kernel mode or vice versa. may also have to jump to the correct location in the current program instructions.
What is the dispatch latency?
The time it takes for the dispatcher to do a context switch.
What is the CPU utilization criteria?
Keep the CPU as busy as possible
What is throughput?
How many process finish execution in a given time unit
What is turnaround time?
The amount of time it takes to execute a process from creation to termination.
What is waiting time?
How long a process spends in ready queue.
What is response time?
How long it takes from request submission till first response.
Explain FCFS.
First Come First Serve. Non-preempitive. CPU is allocated to whichever process comes first, and the process is allowed to run till it terminates.
Advantages of FCFS?
Minimal context-switches (only when process is finished). scheduler doesn’t have to make any decisions so time saved.
Disadvantages of FCFS?
Convoy Effect. If computationally intensive process comes first, then all other processes has to wait till it finishes. Severely decreases response time. Affects interactivity.
Explain Round Robin
Preemptive version of FCFS. Processes are switched after time slice in the order they came in.
Explain Round Robin
Pre-emptive version of FCFS. Processes are switched after time slice in the order they came in.
How does time slice length affect RR.
Context switches are expensive. Short time slice results in more switches decreasing CPU utilisation. Longer slice increases throughput, but will get closer and closer to FCFS.
Disadvantages of RR
processes are not prioritised. Higher priority processes will have to wait for lower priority.
Explain SJF.
Shortest Job First. Most optimal algorithm, however it is impossible to calculate process CPU burst. Can be estimated based on how long it took last time, but not very accurate.
Is there a pre-emptive version of SJF?
Yes. We also need to know arrival time of processes. While a process is running, if a shorter process arrives, the running process is pre-empted, and has to wait until the shorter one finishes. It’s leftover burst time is updated.
Explain Priority Scheduling
Higher priority processes are scheduled first. Can be pre-emptive with arrival times, similar to SJF.
What are the two types of priority allocation in the ready queue?
Explicit (can’t change once in ready queue) or Variable.(can be changed while running)
What is starvation in priority scheduling?
If priorities cannot change, there is a possibility that lower priority processes may never execute as they are constantly pre-empted by the arrival of higher-priority processes.
What is the solution to starvation?
Variable priority. Priority of processes in ready queue are increased based on how long it has been waiting.
What is multi-level scheduling?
Ready queue has levels based on process types. For example, different algorithms for foreground processes (interactive) vs background processes (CPU bound).
Parameters for establishing a multilevel scheduler.
Criteria for deciding which queue a process should go into
Scheduling algorithm to use for each queue
Scheduling between queues, how are the queues switched?
Number of queues?
Can a process move between queues?
What is SMP?
Symmetric multiprocessing. Each CPU core has its own scheduler. Ready queue can be shared, or separate.
Issues with shared ready queue with multicore CPU?
Race conditions. Queue needs to be locked while a scheduler is accessing it.
Issues with separate ready queues in multicore CPU?
Load balancing. One core might have a big ready queues, while others sit idly.
What is real-time scheduling?
Sometimes processes must be executed by a set time. For example in time sensitive situations like autonomous vehicles where system must react to events happening.
What is soft real-time scheduling?
Critical tasks are assigned higher priority. No gurantee whether they will finish by deadline.
What is hard real-time scheduling?
Tasks will finish by deadline. No exceptions.
What is event latency?
Time elapsed from event occurs till it is served.
How can event latency be split?
Interrupt latency - Time from event arrival till start of service routine. OS needs to figure out interrupt type.
Dispatch latency - Time for service routine to pre-empt current process.
What is the extra component needed for make a soft real-time system into a hard real-time system?
Deadlines. Each CPU burst must finish before deadline.
What is a periodic process?
A process that requires CPU time at constant intervals. E.g., polling, monitoring, sampling, etc.
What is a sporadic process?
Event driven. E.g. fault detecting, change in environment, etc.
What does c, p, and d stand for in real-time CPU Scheduling?
c = computation time for process
p = period of process
d = deadline
Does it matter if p and d are the same?
No. They can be the same. p can be less than d or the same. p can change depending on system load
c <= d <= p
How is the computation time for periodic processes known?
Through simulation and analysis.
What happens if computation is finished before the next period?
The process is blocked till the next period.
How does p changes for sporadic processes?
p is now the minimum between events
Can p be 0?
Yes, these are for sporadic process that occurred at the same time.
How does the scheduler deal with simultaneous sporadic events?
No right way to do it. It’s up to the OS, and it doesn’t generally matter which order they are serviced.
What are Cyclic Executives (CE)?
Pre-scheduled tasks that are already programmed. E.g. wash cycle. They are highly predictable, but inflexible and difficult to maintain.
How is major cycle time calculated for CEs?
LCM of process periods.
How is frame time calculated for CEs?
GCD of process periods.
What is Rate Monotonic algorithmn?
Fixed priority. The shortest period is given highest priority.
What is Least Compute Time?
Fixed priority. The shortest computation time is given highest priority. Similar to SJF.
What is Shortest Completion Time (SCT)?
Same as pre-emptive SJF. In real-time systems the computation time is known therefore this is feasible.
What is slack time?
Time till deadline - computation time left.
What is EDF?
Earliest deadline first. Process with closest deadline is prioritised first.
What type of scheduling is required for real-time OS?
pre-emptive, priority based.
