Operating Systems: Scheduling, Multiprocessing, and Real-Time Systems

Comprehensive vocabulary flashcards covering CPU scheduling concepts, scheduling queues, evaluation metrics, algorithms, Real-Time Operating Systems (RTOS), operating system definitions, and multiprogramming versus multiprocessing architectures.

Multiprogramming

An operating system technique where multiple programs reside in main memory simultaneously, enabling the CPU to switch to another process whenever the running process requests an I/O operation, thereby increasing CPU utilization and throughput.

Uniprogramming

A computing system mode where only one process runs at a time, causing the CPU to remain idle whenever the active process requires an I/O operation.

Throughput

The amount of work accomplished in a given time interval, defined as the number of processes completed per unit of time.

Scheduler

The component of an operating system responsible for selecting which runnable process is allocated CPU execution time when multiple processes are ready.

Job Queue

A queue consisting of all processes residing in mass storage waiting for the allocation of main memory.

Ready Queue

A list of all processes that reside in main memory, are in a ready state, and are waiting to be allocated CPU execution time.

Device Queue

A dedicated queue consisting of processes in a waiting or blocked state waiting for an I/O device.

Shareable Device Queue

A device queue for shareable hardware (such as printers, hard disks, and CD drives) that can accommodate multiple processes concurrently.

Non-Shareable Device Queue

A device queue for a dedicated, non-shareable device (such as a tape drive) that can never contain more than one process at a time.

Long-Term Scheduler

Also known as the Job Scheduler or admission scheduler; it selects processes from the job queue, loads them into main memory for execution, and controls the degree of multiprogramming.

Degree of Multiprogramming

The total number of processes present in main memory at a given time; it remains stable when the average process creation rate equals the average process departure rate.

Short-Term Scheduler

Also known as the CPU Scheduler; a very fast scheduler that frequently selects a process from the ready queue and allocates the CPU to it.

Medium-Term Scheduler

A scheduler used primarily in time-sharing systems that temporarily removes processes from main memory to secondary storage (swapping out) and later restores them (swapping in) to reduce the degree of multiprogramming.

CPU-Bound Process

A process that spends the majority of its execution time performing computational calculations and generates I/O requests infrequently.

I/O-Bound Process

A process that spends the majority of its operational time waiting on or executing I/O operations and generates CPU requests infrequently.

Non-Preemptive Scheduling Scheme

A scheduling scheme where a newly selected process executes until it voluntarily relinquishes the CPU, which occurs only when switching from the running state to the waiting state or upon termination.

Preemptive Scheduling Scheme

A scheduling scheme where the operating system can forcibly interrupt an executing process and reallocate the CPU, occurring when a process switches from running to ready or from waiting to ready.

Context Switch

The operating system task of saving the state of a currently running process and restoring the saved state of a new process, representing pure CPU overhead.

Dispatcher

The operating system module that gives control of the CPU to the process selected by the short-term scheduler, involving context switching, switching to user mode, and jumping to the restart location in the user program.

Turnaround Time

The total elapsed time from the moment a process is submitted until its final completion, encompassing time spent waiting for memory, waiting in the ready queue, executing on the CPU, and completing I/O.

Waiting Time

The cumulative duration of time that a process spends waiting in the ready queue to acquire CPU time.

Response Time

The duration of time from process request submission until the very first response is produced, which serves as a critical performance criterion in interactive systems.

First Come, First Served (FCFS) Scheduling

A non-preemptive scheduling algorithm that assigns the CPU to processes strictly in the order of their arrival, which typically results in long average waiting times.

Shortest Job First (SJF) Scheduling

A scheduling algorithm that selects and executes the process with the shortest predicted next CPU burst time first.

Priority Scheduling

A scheduling algorithm that allocates the CPU to the process with the highest assigned priority rank, resolving equal priority ties using FCFS order.

Starvation

A scheduling flaw where low-priority processes remain blocked in the ready queue indefinitely because higher-priority processes continuously monopolize the CPU.

Aging

A corrective technique for starvation that gradually increments the priority of a waiting process over fixed time intervals until it finally executes.

Round Robin (RR) Scheduling

A preemptive scheduling algorithm designed for time-sharing systems in which the ready queue is treated as a circular queue and each process is granted a fixed slice of execution time.

Time Quantum

Also called a time slice; a small discrete unit of CPU execution time allocated to each process in Round Robin scheduling, typically ranging from $10\,ms$ to $100\,ms$.

Multilevel Queue Scheduling

A scheduling algorithm that partitions the ready queue into distinct separate queues based on process classifications (such as system, interactive, or batch), where each queue maintains its own priority level and scheduling algorithm.

Multilevel Feedback Queue Scheduling

A versatile scheduling scheme where processes are dynamically moved between different queues depending on their CPU burst characteristics and wait times.

Homogeneous Multiprocessor System

A multiprocessor architecture consisting of identical processors sharing a single common ready queue, enabling any process to execute on any available processor for balanced workloads.

Heterogeneous Multiprocessor System

A multiprocessor architecture featuring different processor types where each processor has its own individual queue and scheduling algorithm, preventing programs designed for one processor from executing on another.

Deterministic Modeling

An analytic evaluation technique that calculates and compares the exact performance metrics of different CPU scheduling algorithms against a predefined, fixed workload.

Little's Formula

The fundamental queuing equation $n = \lambda \times w$, where $n$ is the queue length, $\lambda$ is the average arrival rate of new processes, and $w$ is the average waiting time per process.

Real-Time Operating System (RTOS)

A specialized operating system that processes data and responds to events within strict time constraints, where system correctness depends on both the logical accuracy of results and the time at which they are produced.

Hard Real-Time System

An RTOS category where task deadlines must never be missed, as missing a deadline causes total system failure or catastrophic consequences (e.g., airbag systems or medical life-support systems).

Soft Real-Time System

An RTOS category where deadlines are important but occasional delays are acceptable, resulting in degraded system performance rather than total system failure (e.g., multimedia streaming and online transaction systems).

Firm Real-Time System

An RTOS category where results delivered after their designated deadline are rendered useless, yet missing a deadline does not trigger a catastrophic system failure.

Interrupt Latency

The minimal elapsed time required by an operating system to detect and begin responding to a hardware or software interrupt.

Top-Down View of an Operating System

The perspective of an operating system defining it as an intermediary program between computer hardware and the user that abstracts hardware complexity to make the computer convenient to use.

Bottom-Up View of an Operating System

The perspective of an operating system defining it as a primary resource manager that arbitrates, allocates, and deallocates system hardware and software assets (CPU time, memory, disk space, and I/O devices).

Control Program

An operating system role that supervises the execution of user programs to prevent errors, conflicts, and unauthorized or improper use of computer resources.

Multiprocessing

A computer hardware and software configuration containing two or more processors (CPUs) that execute multiple instructions or processes concurrently in parallel.

Symmetric Multiprocessing (SMP)

A multiprocessing architecture where multiple identical processors share a common main memory, system bus, and I/O devices, with equal access and running under a single operating system without a dedicated master.

Asymmetric Multiprocessing (AMP)

A multiprocessing structure where a single master processor controls all operating system activities, memory, and scheduling, while subordinate slave processors execute specific assigned tasks.

Master Processor

The central controlling processor in an asymmetric multiprocessing architecture that handles operating system activities and schedules tasks for subordinate processors.

Slave Processor

A subordinate processing unit in an asymmetric multiprocessing architecture that executes only the specific tasks assigned to it by the master processor.

Resource Contention

A condition in multiprogramming and multiprocessing environments where multiple programs or processors simultaneously compete for shared resources (such as memory or system buses), causing conflicts and reduced performance.

Swapping

The operational process managed by the medium-term scheduler of temporarily transferring processes out of main memory to secondary storage (swapping out) and back into main memory (swapping in) to continue execution.