LQ2 - Operating Systems - CPU Scheduling

CPU–I/O Burst Cycle

consists of a cycle of CPU execution and I/O wait

false

short bursts are more frequent than long bursts

True or False: there are a small number of short bursts, while there are a large number of long bursts

CPU scheduler

selects from among the processes in ready queue, and allocates a CPU core to one of them

nonpreemptive

If scheduling takes place only under the following circumstances: (1) switches from running to waiting state, and (2) terminates; what scheduling scheme does it use?

Dispatcher

this module gives control of the CPU to the process selected by the CPU scheduler. This involves switching context, switching to user mode, and jumping to the proper location in the user program to restart that program.

Dispatch latency

time it takes for the dispatcher to stop one process and start another running

Throughput

Number of processes that complete their execution per time unit

Turnaround time

Amount of time to execute a particular process

Waiting time

Amount of time a process has been waiting in the ready queue

Response time

Amount of time it takes from when a request was submitted until the first response is produced.

Shortest-Job First (SJF) Scheduling

Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time.

Shortest-Job First (SJF) Scheduling

is optimal—gives minimum average waiting time for a given set of processes

shortest-remaining-time-first

Preemptive version of SJF

Round Robin (RR)

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.

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)

Starvation

a problem with priority scheduling where low priority processes may never execute

Aging

as time progresses, increase the priority of the processes

Priority Scheduling with Round-Robin

Run the process with the highest priority. Processes with the same priority run round-robin.

Multilevel Queue

With priority scheduling, have separate queues for each priority.

Multilevel Feedback Queue

A process can move between the various queues.

Symmetric multiprocessing (SMP)

is where each processor is self scheduling

Multiple-Processor Scheduling

CPU scheduling with multiple CPUs available

Multicore Processors

• Recent trend to place multiple processor cores on same physical chip

• Faster and consumes less power

• Multiple threads per core also growing

  • Takes advantage of memory stall to make progress on another thread while memory retrieve happens

Multithreaded Multicore System

• Each core has >1 hardware threads

• If one thread has a memory stall, switch to another thread

Chip-multithreading (CMT)

assigns each core multiple hardware threads. (Intel refers to this as hyperthreading.)

load scheduling

If SMP needs to keep all CPUs loaded for efficiency, ____ ____ attempts to keep workload evenly distributed.

Push migration

periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs

Pull migration

idle processors pulls waiting task from busy processor

Soft affinity

the operating system attempts to keep a thread running on the same processor, but no guarantees.

Hard affinity

allows a process to specify a set of processors it may run on.

Multiple-Processor Scheduling - Processor Affinity

When a thread has been running on one processor, the cache contents of that processor stores the memory accessed by that thread.

NUMA-aware

If the operating system is _______, it will assign memory closest to the CPU the thread is running on.

Soft real-time systems

A real time system where critical real-time tasks have the highest priority, but no guarantee as to when tasks will be scheduled.

Hard real-time systems

A real time system where task must be serviced by its deadline.

runqueue

For the Linux scheduling version 2.5, all run-able tasks tracked in per-CPU ____ data structure

Two scheduling classes in Linux scheduling version 2.6.23+

• default

• real-time

virtual run time, vruntime

CFS scheduler maintains per task ____ ____ ____ in variable _____

The Linux Completely Fair Scheduler (CFS)

provides an efficient algorithm for selecting which task to run next. Each runnable task is placed in a red-black tree

red-black tree

a balanced binary search tree whose key is based on the value of vruntime.

Scheduling domain

is a set of CPU cores that can be balanced against one another.

Idle thread

In Windows scheduling, If no run-able thread, runs ____ ___

User-mode scheduling (UMS)

Windows 7 added ____ ____:

• Applications create and manage threads independent of kernel

• For large number of threads, much more efficient

• They come from programming language libraries like C++ Concurrent Runtime (ConcRT) framework

preemptive, nonpreemptive

Scheduling algorithms may be either ___ (where the CPU can be taken away from a process) or ___ (where a process must voluntarily relinquish control of the CPU). Almost all modern operating systems are preemptive.

CPU scheduling

is the task of selecting a waiting process from the ready queue and allocating the CPU to it. The CPU is allocated to the selected process by the dispatcher.

First-come, first-served (FCFS) scheduling

is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes.

Shortest-job-first (SJF)

scheduling is demonstrably optimal, providing the shortest average waiting time. Implementing this algorithm is difficult because it is hard to predict the length of the next CPU burst.

Round-robin (RR) scheduling

allocates the CPU to each process for a time quantum. If the process does not relinquish the CPU before its time quantum expires, the process is preempted, and another process is scheduled to run for a time quantum.

Priority scheduling

assigns each process a priority, and the CPU is allocated to the process with the highest priority. Processes with the same priority can be scheduled in FCFS order or using RR scheduling.

Multilevel queue scheduling

partitions processes into several separate queues arranged by priority, and the scheduler executes the processes in the highest-priority queue. Different scheduling algorithms may be used in each queue.

Multilevel feedback queues

are similar to multilevel queues, except that a process may migrate between different queues.

Multicore processors

place one or more CPUs on the same physical chip, and each CPU may have more than one hardware thread. From the perspective of the operating system, each hardware thread appears to be a logical CPU.

Load balancing

on multicore systems equalizes loads between CPU cores, although migrating threads between cores to balance loads may invalidate cache contents and, therefore, may increase memory access times.

Linux

uses the completely fair scheduler (CFS).

Completely Fair Scheduler (CFS)

Assigns a proportion of CPU processing time to each task. The proportion is based on the virtual runtime (vruntime) value associated with each task.

Windows scheduling

uses a preemptive, 32-level priority scheme to determine the order of thread scheduling.

Solaris

identifies six unique scheduling classes that are mapped to a global priority. CPU-intensive threads are generally assigned lower priorities (and longer time quantums), and I/O-bound threads are usually assigned higher priorities (with shorter time quantums.)