Scheduling Flashcards
Explain the relationship between multi-programming and multitasking.
Multiprogramming allows for multiple jobs to be queued up to use the CPU. This, when executed well, can give the illusion to users of being able to do more than one task at the same time on the one PC.
What is the difference between pre-emptive and co-operative multitasking?
Give an example for each.
Pre-emptive multitasking allows the OS to interrupt the running process after a given quantum and check on them. Usually on the order of milliseconds (10-100). Almost all modern OS’s (Linux, Windows) are pre-emptive.
Co-operative multitasking trusts programs themselves to give up control of the CPU when they are done. The original Macintosh used this.
Should it be possible to pre-empt system calls? Discuss the potential benefits
and problems, and give examples of operating systems which allow and
disallow kernel pre-emption.
Pre-empting syscalls can often leave the system in an inconsistent state and as such the practice is discouraged. Problems include the kernel itself introducing a race condition / deadlock / starvation due to bad programming and causing the entire OS to hang as a result.
When run on a single core, some kernels allow pre-emption to be disabled during syscalls, but mutlicores do not.
Latest Linux kernel, for example, allows pre-empting the kernel except at critical sections.
Three processes are competing for CPU time. They arrive at different times and
have different expected CPU burst duration:
P1 P2 P3 Arrival time 0 ms 1 ms 3 ms Burst duration 6 ms 4 ms 3 ms
Show the schedule, average wait time, and average turnaround time for:
i. Shortest Job First scheduler.
ii. Round Robin scheduler.
Remember that shortest job first will attempt to order them based on heuristics. Doesn’t look like this question cares, but the formula is:
Tn+1 = atn + (1-a)tn
Round Robin will push job to back of queue if it exceeds the quantum, but we don’t seem to have a quantum here. Assume 10ms and continue.
Since burst durations are not known in advance, how can they be estimated
from previous bursts?
Using the heuristic:
Tn+1 = atn + (1-a)tn
Explain the difference between a user-level thread implementation and a kernel-level thread implementation. Describe two advantages presented by the kernel-level approach.
User-level thread implementation means that the kernel is not thread aware. All threading operations are implemented in userspace. In a kernel-level thread implementation, the kernel IS thread aware and can deal with them, but the actual creation is done by userspace libraries.
In a kernel-level approach, the kernel can take advantage of multiple cores and limit context switching across processes, allowing best-of-both-worlds thread use.
Describe the context of a process and identify the parts of the context that are private to individual threads.
A process context includes; registers, stack, heap, bss, static, and code segments.
As threads are very lightweight (for context switching), they only keep their stack and registers private. Everything else is shared.
Explain why it might be advantageous for a scheduler to give priority to IO-
bound jobs.
I/O bound jobs need minimal CPU time, so can execute then use downtime when not being executed to fetch from IO. CPU bound jobs need more CPU time, so let them run once IO jobs are blocking on actual IO.
Describe, with the aid of a diagram, how a multi-level feedback queue
automatically identifies IO-bound jobs.
MLFQ has round-robins on each level. Each level has an increasing quantum (allowing jobs to run for longer) but a decreasing priority.
Once a job exceeds the quantum for a level, it is pushed down to a lower level of the queue.
IO bound jobs stay high priority (they tend not to exceed quantum) but CPU bound jobs sink.
Imagine a CPU scheduler that always schedules the process that has used the
least total amount of CPU time. Describe the following:
A suitable data structure and how this data structure is used.
Why such a scheduler suffers from starvation and how the
scheduling policy can be altered to ensure that starvation is avoided.
How such a scheduler might implement user or kernel defined
priority.
1) A multi-level feedback queue with a SJF algorithm to determine priority at the highest level.
2) This would suffer starvation because a large number of short-running processes would completely block the ability for a long-running process to ever begin executing after its first chance. Remove the SJF algorithm.
3) The algorithm for SJF with weight is:
Tn+1 = atn + (1-a)tn
where a is a weight. The user and kernel defined priority could be translated into a weight and used in in place of a standard SJF algorithm.
