Scheduling Flashcards
What is scheduling in the context of an OS?
It usually means the assignment of threads to processors
What are the problem variants for scheduling?
- Monoprocessor / Multiprocessor
- Dynamic or static thread set?
- Scheduling at runtime or prior to runtime?
- Execution times known in advance?
- Preemption possible?
- Dependencies between threads.
- Communication times considered?
- Setup times (switching) considered?
- Priorities considered?
- Deadline considered?
- Which goal should be achieved? (either user-oriented such as maximum response time or system oriented goals such as throughput)
What are the goals and our assumptions for scheduling for multiprogramming?
Goals include:
- High efficiency: processor highly utilized
- Low response time: with interactive programs
- high throughput: batch-processing
- fairness and capacity: fair distribution of processor and waiting times to threads
Assumptions include:
- Homogeneous multiprocessor system
- Dynamic set of threads
- No dependencies between threads
- Dynamic on-line scheduling
- No deadlines
What are the scheduling levels in relation to thread states? And what is the focus in multiprogramming scheduling?
- Long-term: creating/deleting - non-existent/inactive
- Medium-Term: activating/deactivating - inactive/ready
- Short-term: assigning/relinquishing - ready/running
Here we focus on short-term scheduling.
What are the standard strategies for multiprogramming scheduling? and dicsuss preference to short/long threads for each.
- FCFS: First Come First Served (execute threads in order of arrival at ready list, occupy processor until end voluntary yield)
- LCFS: Last Come First Served (execute threads in reverse order of arrival at ready list, occupy processor until end or voluntary yield)
- LCFS-PR (Preemptive Resume): Newly arrived thread at ready list preempts currently running thread. Preempted thread is appended to ready list, in case of no further arrivals, ready list is processed without preemption). Short thread has good chance to end before another thread arrives, long thread is likely to be preempted several times. => Preference to short threads.
- RR : Round-Robin (processing of threads in order of arrival, after some prespecified time, preemption takes place and we switch to next thread). Goal is even distribution of processor capacity and waiting time to competing threads. Selection of time slice length is optimization problem (large time slice and we have FCFS, small time slice and we have penalty for frequent switching overhead).
- PRIO-NP: Priorities-Non Preemptive (newly arriving threads are inserted in ready list according to their priority, once assigned they stay running on the processor until end of voluntary yield).
- PRIO-P: Priorities-Preemptive (Like PRIO-NP but we check preemption if newly ready thread has higher priority than currently running thread).
- SPN: Shortest Process Next (thread with shortest service time is executed next until it finishes or voluntary yield, like PRIO-NP if we consider service time as the priority criterion). Favor short threads and shorter mean response times than FCFS
- SRTN: Shortest Remaining Time Next (thread with shortest remaining service time is executed next, currently running thread may be preempted). In SRTN and SPN, we need the knowledge of service times which can only be available as estimates. Long threads may starve if shorter threads keep coming.
- Highest Response Ratio Next (HRRN): Response ratio is defined as (waiting time + service time) / service time, calculate and use as priority criterion (highest value is selected). Non-preemptive. Shorter threads favored but unlike SRTN and SPN, long threads score points by waiting to bump them up the priority.
- FB: Multilevel Feedback (when we do not know service time a priori, but want to favor short threads, we can reduce its priority stepwise at each CPU-usage, individual waiting queues can be managed according to round robin, different values of time slices for individual queues are possible).
Categorize scheduling strategies to preemption (w/ or w/e), priorities (w/ or w/e) and service time dependency.
04_scheduling slide 27
What is the difference between static and dynamic thread priorities?
Static priorities express absolute importance of a task (low overhead, O(1) complexity). They are subject to priority inversion.
Dynamic priorities: thread priority is adapted over time so that short running tasks can get preference over long running tasks). They can be realized on top of an implementation of static priorities.
What is priority inversion?
priority inversion is a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that high-priority tasks can only be prevented from running by higher-priority tasks. Inversion occurs when there is a resource contention with a low-priority task that is then preempted by a medium-priority task.
See 04_scheduling slide 32,33
What is the difference between normalized response times for shorter processes and longer processes?
Shorter Processes: priority with preemption (constant) < priority (linear) < no priority (exponential)
Longer Processes: no priority < priority < priority with preemption (all exponential)
See 04_scheduling slides 29,30,31
What are the solutions for priority inversion?
- Priority Inheritance: Lower priority thread that is blocking the resource from higher priority thread inherits higher priority until it releases the resource under contention while medium priority thread is left unchanged.
See 04_scheduling slide 34
- Proportional Share Scheduling: a type of scheduling that preallocates certain amount of CPU time to each of the threads. In a proportional share algorithm every job has a weight, and jobs receive a share of the available resources proportional to the weight of every job. Tasks with a small share get CPU time, but not as much as tasks with larger shares. This avoids priority inversion and is much more complex than a strategy based on priorities.
Define and model the time related variables for scheduling.
t: mean service time (pure execution time)
w: mean waiting time
r: mean response time (including waiting times): r = w+t
r_n: normalized response time: r_n = r/t
ntt: normalized response time: ntt = response time / service time
What is CPU burst and CPU burst time?
The duration (time slice) for which a thread gets control of the CPU is the CPU burst time, and the concept of gaining control of the CPU is the CPU burst.
Similarly, an I/O burst is the concept of performing I/O operations.
How to estimate the CPU Burst?
The behavior of the most recent past is a good predictor for the short-term future. Therefore, we can estimate the CPU burst time of the i’th compute phase of a thread by looking at the execution time recorded in previous < i compute phases for that thread.
The formula is in 04_scheduling slide 40
S[n+1] = 1/n * T[n] + ((n-1/n) S[n] = (1/n) * sum_1_n(T[i])
Because younger more recent values usually characterize the future behavior better than older ones, they should obtain higher weight so we can apply exponential averaging to the formula above:
S[n+1] = a * T[n] + (1-a) S[n] with 0 < a < 1.
If a > 1/n, younger values get higher weights.
When enrolling this recursion, the weights of older measurements fade out exponentially. High a leads to better responsiveness (response to change in behavior), smaller a leads to better stability (to filter outliers). The first estimate S[1] can be initialized with 0 to give new threads high priority. See 04_scheduling slides 42 and 43 for the effect of exponential decay of weights.
What is the problem with multiprocessor scheduling?
We have to decide not only when to execute a task but also where (on which processor).
Additionally, even if processors are identical, these processors/cores might share limited resources including caches, memory bandwidth might be limited and share by cores, logical cores might share the execution units within one physical core.
What is the concept of processor affinity in multiprocessor scheduling?
If a thread was running on a processor, corresponding caches were filled with data belonging to it. If the thread is scheduled again, there is a chance that significant parts of the cache still belong to that thread so processor affinity means that the scheduler favors the recently used processor but it may happen that a thread with higher priority is waiting for its favored processor while another thread with lower priority is running.
