D686: Operating Systems for Computer Scientists (chapter 6 & 7)

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)

dispatcher

The dispatcher is the kernel routine that gives control of a core to the thread selected by the scheduler

dispatch latency

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

Throughput

If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput.

CPU utilization

the percentage of time the CPU is actively working; the optimal utilization is around 90 percent, as sustained 100 percent use can impact system performance and stability

turnaround time

the total time from process submission to completion, including waiting, execution, and I/O time

waiting time

the time a process spends waiting in the ready queue before it gets CPU time

response time

the time from the submission of a request to the first response being produced by the process, particularly important in interactive systems

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

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.

time slice

See time quantum

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.

infinite blocking

See starvation

starvation

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

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

multilevel queue

A multilevel queue scheduling algorithm partitions the ready queue into several separate queues.

foreground

A thread that is interactive and has input directed to it (such as a window currently selected as active or a terminal window that is currently selected to receive input).

background

A thread that is not currently interactive (has no interactive input directed to it) such as one in a batch job or not currently being used by a user.

multilevel feedback queue

The multilevel feedback queue scheduling algorithm that allows a process to move between queues.

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 usage 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

deadlock

a condition where two or more processes or threads are unable to proceed because each is waiting for the other to release a required resource

exclusive access

permission allowing only one process or thread to access a resource at a time

release

the action of freeing a resource after use.

request

the action of asking for a resource

resources

items or data used by processes in computing, such as memory, CPU time, or files, which need to be managed and shared among different processes

use

the process of utilizing a requested resource

system resource-allocation graph

A directed graph for precise description of deadlocks

request edge

In a system resource-allocation graph, an edge (arrow) indicating a resource request

assignment edge

In a system resource-allocation graph, an edge (arrow) indicating a resource assignment.

assignment edge

a directed edge from a resource to a thread or process, showing resource allocation

circular wait

a set of threads exists where each thread is waiting for a resource held by the next thread in the set, forming a cycle

edges

connections between nodes representing relationships or allocations

graph

a collection of nodes (or vertices) and edges (or lines) connecting them

hold and wait

a thread holds at least one resource while waiting to acquire additional resources held by other threads

mutual exclusion

at least one resource must be held exclusively by one thread at a time, blocking others until released

no preemption

resources cannot be forcibly taken from a thread; they can only be released voluntarily by the thread holding them

nodes (vertices)

entities in the graph representing resources, threads, or processes

request edge

a directed edge from a thread or process to a resource, indicating a request for the resource

system resource-allocation graph

directed graph used to describe deadlock situations precisely

allocation

the process of assigning resources to different tasks or processes

Banker's algorithm

an algorithm that prevents deadlocks by ensuring resource allocation does not lead to an unsafe state

deadlock avoidance

strategies that dynamically allocate resources only if they ensure that the system remains in a safe state where deadlock is impossible

deadlock prevention

techniques to ensure that deadlock cannot occur by systematically denying conditions that lead to deadlock, like holding onto resources indefinitely

dynamic allocation

assigning resources to processes as needed, rather than fixing them in advance

resource manager

system component that controls and allocates resources among processes

resource request

when a process asks for resources, it needs to complete a task

resource release

when a process finishes using a resource and makes it available for others

resource sharing

allowing multiple processes to use the same resource without interfering with each other

safe state

a state where the system can allocate resources to processes in some order and avoid deadlock

static allocation

assigning resources to processes before they start and not changing them during execution

synchronization

coordinating processes to ensure they do not interfere with each other when accessing resources

unsafe state

a state where the system cannot guarantee deadlock avoidance

wait-for graph

In deadlock detection, a variant of the resource-allocation graph with resource nodes removed; indicates a deadlock if the graph contains a cycle

thread dump

In Java, a snapshot of the state of all threads in an application; a useful debugging tool for deadlocks.

recovery mode

A system boot state providing limited services and designed to enable the system admin to repair system problems and debug system startup.

rollback

reverting a process to a previous safe state to recover from