P3L1: Scheduling

Question 1

What decides how and when process (and their threads) access shared CPUs?

Answer 1

CPU Scheduler

Question 2

What is the CPU Scheduler concerned with?

Answer 2

Schedules tasks running user-level processes/threads as well as kernel-level threads

Question 3

What events kick off the CPU Scheduler?

Answer 3

• CPU becomes idle
• New task becomes ready (checks for priority on new task and previous tasks to potentially interrupt current running task)
• timeslice expired timeout (when a running thread has used up its time on the CPU)

Question 4

Describe the Steps for when the Scheduler dispatches a thread on the CPU

Answer 4

1. context switch
2. enter user mode
3. set program counter
4. execute/run

Question 5

Choose task from ready queue means?

Answer 5

Scheduling

Question 6

Name the scheduling type that, as soon as a task is assigned to the CPU, it will run until it finishes/completes

Answer 6

Run-to-Completion Scheduling

Question 7

Define the First-Come First-Servce (FCFS) Algorithm for scheduling

Answer 7

• Schedules tasks in order of arrived
• A runqueue is useful, the runqueue should be First-In First-Out (FIFO)

Question 8

Define the Shortest Job First (SJF) algorithm for scheduling

Answer 8

• Schedules tasks in order of their execution time
• Runqueue will maintained as an ordered queue by task execution time OR utilize a tree where the nodes are organized by execution time

Question 9

Formula for Throughput

Answer 9

Throughput = (# of Tasks) / (Total Execution Time, or "Makespan")

Question 10

Formula for Avg. Completion Time

Answer 10

Avg. Completion Time = (Sum of Times to Complete Each Task) / (# of Tasks)

Order of Task is important!!!!

Question 11

Formula for Avg. Wait Time

Answer 11

Avg. Wait Time = (Total Wait Time to Start Each Tasks) / (# of Tasks)

Order of Task is important!!!!

Question 12

What does it mean to preempt (what is preemption)?

Answer 12

Interrupt a task to start another

Question 13

How do we determine execution time?

Answer 13

heuristics based on history are utilized to determine job running time/execution time

Question 14

What is Windoqwed Average?

Answer 14

The average execution time of a task over the last n times

Question 15

What is Priority Scheduling?

Answer 15

When tasks have different priority levels that help indicate which tasks to schedule

• highest priority task gets scheduled next or preempts the current running task

Question 16

How does Priority Scheduling determine priority?

Answer 16

• Different runqueues for each priority level
• Tree ordered based on priority level

Question 17

What is a drawback/danger of Priority Scheduling and how do we address it?

Answer 17

• Low priority task stuck in a runqueue (due to higher priorty tasks being always present); “runqueue starvation”
• “Priority Aging” - priority = f(actual priority, time spent in runqueue)
  We can change the priority of a task through some function, based on the original priority and the time it has spent in the current runqueue

Question 18

Describe Priority Inversion and how we might combat it

Answer 18

Priority Inversion is when the completion of tasks does not follow the exact priority scheduling due to conflicts in mutex locks. We can combat this through temporarily boosting the priority of the current mutex owner until they do not need the mutex anymore, ensuring that the mutex is then unlocked for higher priority tasks. We lower the priority of the tasks once it releases the mutex

Question 19

Define Round Robin Scheduling

Answer 19

1. Pick up first task from queue (like FCFS)
2. Task my yield, to wait on I/O (unlike FCFS)
3. Next task is picked up while first task waits on I/O to finish. First task is placed at end of queue.
4. Second task will run to completion or until it has to wait, at that point is yields to next task in queue and is put in back of queue

and so on / this goes on until all tasks are complete

Question 20

How does Round Robin Scheduling work with priorities?

Answer 20

Basic Round Robin Scheduling but with the inclusion on preemption based on priority level

Question 21

What is the maximum amount of uninterrupted time given to a task?

Answer 21

timeslice or “time quantum”

Question 22

Can a task run for less than the set timeslice time?

Answer 22

True - could end early, or have to wait on I/O, synchronization, mutex, etc.

task will be placed on the queue if interrupted

higher priority tasks will also interrupt/preempt

Question 23

How do we minimize overheads for scheduling that uses timeslices?

Answer 23

the timeslice value should be larger than the context switch time by a significant enough time

Question 24

What are benefits/downsides of adding Timeslice Scheduling to RoundRobin?

Answer 24

Benefits
- short tasks finish sooner
- more responsive
- lengthy I/O operations initiated sooner

Downsides
- overheads: interrupt, schedule, context switches

Question 25

For CPU bound tasks is it better to have lower or higher timeslice values?

Answer 25

Higher, in fact inifinite time for timeslice value will yield the best throughput and avg. completion time (CPU bound tasks specifically)

Question 26

For I/O bound tasks is it better to have lower or higher timeslice values

Answer 26

Lower, I/O bound tasks get more chances to start running, issue their I/O request, respond to users, and keeps CPU and I/O devices busy (I/O bound tasks)

Question 27

CPU Utilization Formula

Answer 27

[cpuRunningTime / (cpuRunningRime + contextSwitchOverheads)] * 100 Helpful Steps to Solve: 1. Determine a consistent, recurring interval 2. In the interval, each task should be given an opportunity to run 3. During that interval, how much time is spent computing? This is the cpu_running_time 4. During that interval, how much time is spent context switching? This is the context_switching_overheads 5. Calculate!

Question 28

List Runqueue Data Structures

Answer 28

List Multiple Lists Tree etc

Question 29

Given n number of tasks with three levels of I/O intensity, how might configure the runqueue datastructure, timeslice values, and priority?

Answer 29

Separate the tasks by the I/O intensity, highest being given the shortest timeslice value and highest priority and lowest I/O intensity getting the longest timeslice and lowest priority.

Question 30

How do we determine I/O intensity of tasks?

Answer 30

- History based heuristics - treat multiple runqueues as not totally separate, if a task uses the full timeslice from one queue, move it to the next queue with the largest timeslice value (or vice versa, moving a task up in priority if it interrupts before timeslice value is used) => Multi-Level Feedback Queue (MLFQ)

Question 31

Describe Multi-Level Feedback Queue

Answer 31

multiple runqueues with increasing timeslice values and decreasing priority (higher timeslice == lower priority). Each runqueue has a different policy associated to it as well. If tasks use full timeslice time for high priority queues, move them to the lower priority queue with higher timeslice value. If task is interrupted before full timeslice value is used, move it to higher priority queue with lower timeslice.

Question 32

Describe the Linux O(1) Scheduler

Answer 32

Constant time to select/add task, regardless of task count. Preemptive, priority-based - real time (0 to 99 priority levels), 0 being highest - timesharing (100 to 139), user processes, default is 120 adjusted by a "nice value" (-20 to 19) Timeslice Value - depends on priority - smallest for low priority - highest for high priority Feedback - sleep time: waiting/idling - longer sleep => interactive, so boost the priority by subtracting 5 - smaller sleep => compute-intensive, lower priority by adding 5 Runqueue 2 arrays of tasks Active - used to pick next task to run - constant time to add/select - tasks remain in queue in active array until timeslice expires Expired - inactive list - when no more tasks in Active arry => swap active and expired

Question 33

What are some issues with the O(1) Linux Scheduler?

Answer 33

- performance of interactive tasks - fairness not guarenteed

Question 34

Describe the Linux Completely Fair Scheduler (CFS)

Answer 34

Default since 2.6.23 and is the scheduler for Nonreal-time tasks. Realtime tasks are scheduled by a real-time scheduler Runqueue == Red-Black Tree - dynamic tree structure - As nodes are added/removed then the tree will self balance itself so all paths from the root to the leaves are aproximately the same size - ordered by "vruntime" - vruntime == tiome spent on CPU - children on left spend lest time on CPU, children on right spend more time on CPU CFS always picks the leftmost node, will periodically adjust vruntime of current running task and compare it to leftmost node's vruntime - if smaller, continue running - if larger, preemptand place appropriately in the tree vruntime progress rate depends on priority and niceness - rate faster for low priority - rate slower for high priority Same tree for all priorities! Performance - Select Task => O(1) - Add Task => O(logN)

Question 35

Why is it important to and how do we schedule a task back to the same CPU is previously was on?

Answer 35

Cache-Affinity - keep tasks on the same CPU as much as possible - cache is hot with the data that task needs - hiearachical scheduler architecture Per CPU schedulers that are handed tasks by a load balancer - load balance across CPUs - base on queue length or when CPU is idle For multiple memory nodes, want to utilize the memory node on the CPU closer to the where the state of the task is => NUMA-Aware (Non-Uniform Memory Access Aware) Scheduling

Question 36

Describe Non-Uniform Memory Access (NUMA)

Answer 36

- multiple memory nodes - memory node closer to a "socket" of multiple processors - access to local memory node faster than access to remote memory node

Question 37

Define Hyperthreading

Answer 37

- multiple hardware-supported execution contexts - still one CPU but with very fast context switch CPU has multiple registers with their own threads/execution contexts. It is faster two context switch between these execution contexts than others Also known as "hardware multithreading," "multithreading," "chip multithreading (CMT)," "simultaneous multithreading (SMT)