D686 - Operating Systems - Chapter 6

cycle

Repeating loop

CPU burst

Scheduling process state in which the process executes on CPU.

I/O burst

Scheduling process state in which the CPU performs I/O.

CPU scheduler

Kernel routine that selects a thread from the threads that are ready to execute and allocates a core to that thread.

nonpreemptive

Under nonpreemptive scheduling, once a core has been allocated to a thread the thread keeps the core until it releases the core either by terminating or by switching to the waiting state.

cooperative

A form of scheduling in which threads volunarily move from the running state.

preemptive

A form of scheduling in which processes or threads are involuntarily moved from the running state (by for example a timer signaling the kernel to allow the next thread to run).

____ is the number of processes that are completed per time unit.

Throughput

throughput

Generally the amount of work done over time. In scheduling, the number of threads completed per unit time.

First-come first-served (FCFS)

The simplest scheduling algorithm - the thread that requests a core first is allocated the core first, and others following get cores in the order of their requests.

Gantt chart

A bar chart that is used in the text to illustrate a schedule.

convoy effect

A scheduling phenomenon in which threads wait for the one thread to get off a core, causing overall device and CPU utilization to be suboptimal.

shortest-job-first (SJF)

A scheduling algorithm that associates with each thread the length of the threads next CPU burst and schedules the shortest first.

exponential average

A calculation used in scheduling to estimate the next CPU burst time based on the previous burst times (with exponential decay on older values).

shortest-remaining-time-first (SJRF)

Similar to SJF, this scheduling algorithm optimizes for the shortest remaining time until thread completion.

round-robin (RR)

A scheduling algorithm that is designed especially for time-sharing systems - similar to FCFS scheduling, but preemption is added to enable the system to switch between threads.

time quantum/slice

A small unit of time used by scheduling algorithms as a basis for determining when to preempt a thread from the CPU to allow another to run.

priority-scheduling

A scheduling algorithm in which a priority is associated with each thread and the free CPU core is allocated to the thread with the highest priority.

starvation/infinite blocking

A scheduling risk in which a thread that is ready to run never gets put onto the CPU due to the scheduling algorithm - it is starved for CPU time.

aging

A solution to scheduling starvation and involves gradually increasing the priority of threads as they wait for CPU time.

real-time

systems where tasks must be completed within specific time limits

hard real-time systems

systems where tasks must meet deadlines without exception

soft real-time systems

systems that are not critical when tasks are important but missing a deadline

real-time scheduling 

the process of organizing tasks so they meet their deadlines

online scheduler

a scheduler that makes decisions about tasks while the system is running

offline scheduler

a scheduler that plans tasks before the system starts running

static scheduler

a scheduler that makes a fixed schedule before tasks start

feasibility tests/schedulability tests

methods to check if tasks in a system can be completed on time

dynamic scheduler

a scheduler that adjusts the task schedule based on current conditions

preemptive scheduler

scheduler that can interrupt a currently running task to start or resume another task, ensuring that higher-priority tasks receive CPU time as needed

non-preemptive scheduler

a scheduler that allows a task to run to completion before switching to another task, ensuring that once a task starts, it is not interrupted until it finishes

multilevel queue

a scheduling algorithm dividing the ready queue into multiple distinct queues

foreground

refers to an interactive thread actively receiving input or engaging with user interaction

background

describes a thread or process not actively receiving user input or interaction, often running in batch mode or idle

multilevel feedback queue

a scheduling algorithm allowing processes to move between different priority queues based on their CPU characteristics 

symmetric multiprocessing (SMP)

each processor manages its own scheduling, handling both kernel and user threads with potential contention for system resources

asymmetric multiprocessing (AMP)

A system where one processor handles all system tasks and scheduling, while other processors execute only user code

chip multithreading (CMT)

CPUs with multiple cores, each supporting numerous hardware threads, that enhance overall processing efficiency

load balancing

distributing workload evenly across processors in an SMP system to maximize efficiency and prevent idle processors

push migration

load-balancing technique where a task redistributes threads from overloaded processors to those with lighter loads

pull migration

load-balancing method where an idle processor retrieves tasks from busy processors to balance the workload

processor affinity

keeping a thread on the same processor to benefit from its cache and reduce cache invalidation costs

soft affinity

strategy where the operating system aims to keep a thread on the same processor but allows it to migrate if necessary

hard affinity

A strategy where the operating system allows a thread to specify a set of processors on which it can run, ensuring it stays within this set

memory stall

a delay in thread execution when accessing memory that is not currently in the CPU cache, requiring retrieval from main memory

hardware threads

threads that a CPU core can manage, either one per core or multiple, to optimize performance by switching threads during stalls

What is the method used to determine which processes will be assigned to the CPU for execution?

CPU scheduling

How does a preemptive scheduling algorithm differ from a non-preemptive scheduling algorithm?

Preemptive scheduling can interrupt a running process to assign the CPU to another process.

Which criterion measures the total time taken from the submission of a process to its completion?

Turnaround time

Which scheduling criterion aims to keep the CPU as busy as possible?

Utilization

Which scheduling algorithm executes the process that arrives first?

First-come, first-served (FCFS)

How does shortest job first scheduling determine the order of process execution?

By the length of the next CPU burst of each process

Which scheduling algorithm allocates a fixed time slice to each process in the ready queue?

Round-robin

How is real-time scheduling different from traditional scheduling algorithms?

Real-time scheduling ensures processes meet deadlines.

Which type of scheduling uses multiple queues, each with its own scheduling algorithm?

Multilevel queue

What is the purpose of load balancing in multiprocessor scheduling?

To ensure equal distribution of tasks across processors