Introduction, Processes, Threads & Processor Scheduling

An Operating System is system software that acts as the interface between the user and the computer hardware. It manages the hardware and software resources of the system and provides services to application programs, so programs never touch hardware directly. Examples: Microsoft Windows, Linux, macOS, Android.

Functions of an OS

Process vs program

A program is a passive set of instructions stored on disk. When the user runs it, the OS loads it into main memory and creates a process — a program in execution, an active entity with a program counter, registers, stack and allocated resources.

Example from the book: MS Word installed on your computer is a program; when you open it and it starts running, it becomes a process.

1. Program execution — loads the program into memory and decides the order of execution using a scheduling algorithm (FCFS, SJF, …). When two programs become ready it keeps them from interfering, and it also handles deadlock.
2. I/O operations — manages input/output and communicates with device drivers so a program can read or write without knowing how the hardware works, and keeps devices in sync.
3. Communication between processes — transfers data between processes; when they are on different machines joined by a network, the OS manages that too.
4. File management — grants file access, enforces read-only / read-write permissions, and decides how data is stored and retrieved on disk.
5. Memory management — checks whether enough free space exists before loading a program, allocates it at a suitable location, and stops a program using memory that is not its own.

Multiprogramming increases CPU utilisation by organising jobs (code and data) in main memory so the CPU always has one to execute; if the running job goes for I/O, the CPU is assigned to another job. Multitasking is a logical extension of it — the ability of an OS to execute more than one task simultaneously on a CPU, with those tasks sharing common resources such as CPU and memory.

One-liner to open with: “Multiprogramming keeps several jobs in memory so the CPU is never idle; multitasking keeps several tasks running at once by switching very fast.”

Batch OS — popular in the 1970s. Jobs with similar requirements are grouped and executed as a batch to speed up processing. Users do not interact with the computer directly: each prepares a job on an offline device such as a punch card and hands it to the operator, who sorts similar programs into batches.

Time-sharing OS — uses CPU scheduling and multiprogramming to give each user a small portion of a shared computer. Each user has at least one program in memory; a program runs a short time before finishing or requesting I/O. That interval is the time slice / time slot / quantum, typically 10–100 ms.

Draw the batch diagram → Diagram Bank · Simple batch system.

Related: multiprogramming vs multitasking · multiprogramming vs multiprocessing vs multitasking · multiprogramming, time sharing and RTOS in detail.

Multiprogramming — one or more programs are loaded in main memory ready to execute, but only one is on the CPU at a time. If the running program starts an I/O task (which by definition does not need the CPU), the OS may interrupt it and give control to another ready program — a context switch. No CPU time is wasted waiting for I/O. The goal is to keep the CPU busy as long as processes are ready. The OS must also protect each program's memory area from the others, and must handle programs that do not fit in memory at once — solved by paging and virtual memory.

Multiprocessing — refers to the hardware: more than one CPU (cores on one die, or several packages). Several programs execute at the same instant. A system can be both multiprogrammed and multiprocessed.

Multitasking — the general modern term for running multiple programs, processes, tasks or threads at the same time when they share a common processing resource. At any instant the CPU executes one task only; the illusion of parallelism comes from reassigning the CPU so quickly (a fair share called a quantum) that all seem to run together. A task here is often a “thread of execution”, not a whole application.

Hook: multiprogramming = many programs in memory · multiprocessing = many processors · multitasking = many tasks in time. Both multiprogramming and multitasking systems are CPU time-sharing systems.

A real-time system is an OS designed to respond to events within a strict time limit (a deadline). Correctness depends on both the result and the time at which the result is produced. Such systems are like super-fast computers that handle tasks needing quick responses.

Two types

• Hard real-time — missing a deadline is unacceptable; “like urgent missions, they must be done exactly on time or something really bad could happen”. Examples: aircraft control systems, pacemakers, nuclear power plant control systems.
• Soft real-time — important, but occasional late responses are tolerable. Examples: multimedia streaming, online gaming, video conferencing.

Working of an RTOS

1. External events generate interrupts.
2. The RTOS immediately schedules the highest-priority task.
3. Tasks are executed within predefined deadlines.

Why they are critical

1. Multiprogramming OS

Keeps multiple programs in main memory at the same time and executes them concurrently. When one process waits for I/O, the CPU switches to another, ensuring maximum CPU utilisation.

Working: several jobs are loaded into memory → the CPU executes one job → if that job needs I/O it is put into a waiting state → the CPU is assigned to another ready job → this continues until all jobs complete.

Example: Program A waiting for I/O, Program B running on CPU, Program C in the ready queue. When B finishes or waits for I/O, the CPU switches to C.

Advantages: better CPU utilisation · increased throughput · reduced CPU idle time · efficient use of system resources.
Disadvantages: complex memory management · requires CPU scheduling · possibility of deadlocks · longer response time for users.

2. Time-sharing OS

Allows multiple users or processes to share the CPU simultaneously by allocating a small time slice (quantum) to each.

Working: CPU divided into small time slices → each process gets a fixed quantum → when the quantum expires the CPU switches to the next process → switching is so fast that users feel they have exclusive access.

Example: with quantum = 2 ms, P1 → P2 → P3 → P1 → P2 → P3; each process gets CPU time round-robin.
Applications: multi-user systems · online reservation systems · shared computing environments.

Advantages: fast response time · supports multiple users simultaneously · fair CPU allocation · efficient resource sharing.
Disadvantages: frequent context-switching overhead · requires more memory · security and data-integrity issues · performance may degrade with many users.

3. Real-Time Operating System (RTOS)

Designed to respond to events within a strict time limit (deadline); correctness depends on both the result and when it is produced. Hard RTOS — missing a deadline is unacceptable (aircraft control, pacemakers, nuclear plant control). Soft RTOS — occasional misses acceptable (streaming, online gaming, video conferencing).

Advantages: predictable response time · high reliability · efficient task scheduling · suitable for mission-critical applications.
Disadvantages: expensive development · complex design · limited flexibility · higher hardware requirements.

Parallel systems

• More than one processor inside one computer system, closely coupled.
• Tightly coupled — processors share main memory and a clock (symmetric or asymmetric multiprocessing); loosely coupled — each has its own memory.
• Extra reliability: if one processor fails, the others take over its work at reduced speed (graceful degradation / fail-safe mode).
• Higher throughput than a single processor for the same load.

Distributed systems

• Several independent machines with their own memory and CPU, joined by a network — loosely coupled.
• Resources (files, printers, CPU cycles) are shared across sites; the user sees one logical system.
• Communication happens by message passing, not shared memory.
• Benefits: load sharing, easy expansion, faster problem solving, site-failure tolerance. Costs: needs a protocol stack, weaker security model, no single global clock.

The 2019 print reads “Compare and Constrain Network, Parallel and distributed operating systems” — Constrain is the book's typo for contrast. Reproduced as printed so you recognise it.

A personal-computer system is a single-user microcomputer system. Its OS exists mainly to maximise user rather than system performance, because CPU and memory are cheap and the human is the bottleneck. Programs are run directly by the user, and most such systems historically were not designed to run multiple programs at once. Windows, macOS and desktop Linux provide a GUI, support applications and games, and give the user direct control of the hardware.

The OS acts as a manager of the hardware and software resources of a computer. Those resources include CPU (processor), memory (RAM), disk storage, input/output devices, files and data, and processes and programs. The OS decides who gets what, how much and for how long, so that all programs and users get fair and efficient access without conflict or waste.

Every allocation request passes through three OS actions: decide (is the resource free and is the request legal?), record (update the table saying who holds what), and release (return the resource when the process finishes or blocks).

For 2 marks the table plus one closing line is enough: “The OS is the arbiter — it grants, tracks and reclaims each resource so no two processes use the same one at the same time.”

Definition

A process is a program in execution — an active entity needing CPU time, memory, files and I/O. The objective of multiprogramming is to have some process running at all times to maximise CPU utilisation; the objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it runs. To meet these objectives the process scheduler selects an available process (from the set of several available processes) for program execution on the CPU.

On a single-processor system there will never be more than one running process; if there are more processes, the rest must wait until the CPU is free and can be rescheduled.

Five states

1. New — the process is being created.
2. Ready — admitted to memory, waiting only for CPU time.
3. Running — instructions are being executed.
4. Waiting / Blocked — waiting for an event other than CPU (I/O completion, a signal).
5. Terminated — finished; the OS reclaims its resources.

Extended (seven-state) version

How the PCB is used in a context switch

1. A timer interrupt or quantum expiry stops the running process.
2. The OS saves the CPU registers and program counter into that process's PCB and sets its state to ready (or waiting).
3. The scheduler picks the next process and reads its PCB.
4. The OS restores registers and program counter from the new PCB, sets the state to running and jumps to the restored address.

Practice the numbers from this section → Numericals · CPU Scheduling.

A Process Control Block (PCB) — also called a process descriptor or task control block — is the data structure the OS uses to store everything it needs about one process. With the creation of a process a PCB is created, which controls how that process is being carried out. Its aim is to help the OS manage the enormous number of tasks being carried out: the OS creates a PCB for every process, and it contains all the important information about that process, which the OS later uses to manage and run processes efficiently.

Block diagram — fields of a PCB

A cleaner, bigger version for exam practice → Diagram Bank · PCB block diagram.

Primary terminologies related to the PCB

A process is an independent program in execution with its own address space. A thread is the smallest unit of CPU execution within a process — a lightweight process. One process may contain several threads that share the same code, data and resources but execute independently.

Example

• Process: open a web browser, a music player and a text editor — three separate processes.
• Thread: inside the one browser process, one thread draws the user interface, one downloads pages, one plays video.

An interrupt is a signal to the CPU that some event needs attention. The CPU suspends the current instruction stream, saves just enough state to come back, and jumps to a kernel routine that services the event. Interrupts are how the OS gets control without the program's cooperation — without them there would be no preemption, no I/O completion and no time sharing.

What the handler does

1. The device raises the interrupt line; the CPU finishes the current instruction.
2. The CPU saves the program counter and flags on the kernel stack.
3. The interrupt vector — a table of handler addresses — is indexed by the interrupt number to find the right interrupt service routine.
4. The ISR services the device and, for an I/O interrupt, moves the waiting process from waiting to ready in its PCB.
5. On return the OS may run the scheduler; if a higher-priority process is now ready, a context switch happens instead of returning to the interrupted process.

Advantages of IPC

1. Enables processes to communicate with each other and share resources, leading to increased efficiency and flexibility.
2. Facilitates coordination between multiple processes, leading to better overall system performance.
3. Allows the creation of distributed systems that can span multiple computers or networks.
4. Can be used to implement various synchronisation and communication protocols such as semaphores, pipes and sockets.

Shared memory vs message passing

Diagram → Diagram Bank · Shared memory and message passing.

Producer–Consumer with a bounded buffer

Two processes share a common buffer. The producer puts items in; the consumer takes them out. The unbounded-buffer version places no limit on size, so the producer never waits. The bounded-buffer version allows at most n items, so the producer must wait when the buffer is full and the consumer must wait when it is empty — and because both touch the buffer at the same time, access must be mutually exclusive.

semaphore mutex = 1;   // protects the buffer
semaphore full  = 0;   // number of filled slots
semaphore empty = n;   // number of free slots

Producer                 Consumer
while (true) {           while (true) {
  produce an item;         wait(full);
  wait(empty);             item = remove from buffer;
  wait(mutex);             signal(mutex);
  add item to buffer;      signal(empty);
  signal(mutex);           consume the item;
  signal(full);          }
}

Full synchronisation treatment → Synchronization.

The 2018 paper asks this as a comparison of IPC with mutual exclusion — the shared-memory row is the answer to both framings.

In a process, a thread refers to a single sequential activity being executed; these activities are also known as threads of execution or thread control. Any OS process can execute a thread, so a process may have multiple threads. When a thread moves through the system it is always in one of five states (excluding the CREATION and FINISHED end points): 1. Ready · 2. Running · 3. Waiting · 4. Delayed · 5. Blocked.

How a thread moves between them

1. When an application is to be processed, it creates a thread.
2. Required resources (for example a network) are allocated to it and it enters the READY queue.
3. The thread scheduler (like a process scheduler) assigns it a processor — it enters RUNNING.
4. If the thread needs some external event to be triggered first (another process completing), it moves RUNNING → WAITING.
5. A thread that can deliberately sleep for a fixed time moves RUNNING → DELAYED. Example: the snooze function of an alarm — after it rings once and is not switched off, it rings again after a set interval; during that interval the thread is put to sleep.
6. If the thread generates an I/O request and cannot move further until it is done, it moves RUNNING → BLOCKED.
7. After the process is completed, the thread moves RUNNING → FINISHED.

A thread is the smallest unit of CPU execution within a process. A process may contain one or more threads that share the same memory, code and resources but execute independently. Example: in a web browser, thread 1 = user interface, thread 2 = downloading web pages, thread 3 = playing video — all belonging to the same browser process.

User-Level Threads (ULT)

Managed by a thread library in user space, without direct support from the OS kernel. Thread creation and management are done by the user-level library; the kernel is unaware of these threads.

• Characteristics: faster to create and switch; low overhead; portable across operating systems.
• Disadvantages: if one thread performs a blocking system call the entire process may block, because the kernel sees only one process; cannot fully utilise multiple CPUs.

Kernel-Level Threads (KLT)

Managed directly by the operating system kernel, which schedules each thread independently. Each thread is known to the OS.

• Advantages: one blocked thread does not block the entire process; better support for multiprocessor systems; true parallel execution is possible.
• Disadvantages: thread creation and switching are slower; higher overhead due to kernel involvement.

When is one better than the other?

Related short question (Jun 2019 Q.4(c)): a thread needs only a stack, program counter and register set when created; a process needs all of that plus its own address space, page table, file table and PCB.

Process scheduling is the activity of the process manager that removes the running process from the CPU and selects another process based on a particular strategy. It is an essential part of a multiprogramming operating system: such systems allow more than one process to be loaded into executable memory at a time, and the loaded processes share the CPU using time multiplexing.

The three schedulers

The queueing diagram itself → Diagram Bank · Scheduling queues. Draw it every time this question is worth 5+ marks.

Scheduling falls into one of two categories:

• Non-preemptive — once the CPU has been allocated to a process, the process keeps the CPU until it finishes or voluntarily blocks. Its resources cannot be taken away before it is done; when the running process finishes and moves to the waiting state, resources are released and switched.
• Preemptive — the OS assigns resources for a predetermined period. The process switches from running to ready, or from waiting to ready, during resource allocation; this happens because the CPU may give other processes priority and substitute the currently active process for a higher-priority one.

Worked mini-example (printed in the Oct-2025 paper)

Two processes: P1 AT 0, BT 10 ms and P2 AT 2, BT 4 ms.

Preemptive (SRTF): P1 starts at 0. At time 2, P2 arrives with a shorter burst, so the CPU interrupts P1 and runs P2 to completion at 6; P1 then resumes and finishes at 14. That interruption of P1 is what makes the scheduling preemptive.

Non-preemptive (FCFS): P1 starts at 0, P2 arrives at 2 but must wait until P1 finishes at 10, then runs to 14. P1 is never interrupted — that is non-preemptive scheduling.

Why strict non-preemptive scheduling is unlikely in modern systems

• Poor responsiveness — once a process starts it runs to completion regardless of the priority or urgency of other tasks, so an interactive command can wait behind a long batch job.
• Not suitable for multitasking — in older OSs one whole program kept running until it blocked; in modern OSs time sharing is best manifested because each running process takes only a fair quantum of CPU time.
• Blocking issues — a CPU-bound process holds the CPU while I/O-bound processes wait, so I/O devices sit idle and then all queue up at once (the convoy effect).
• No interrupt handling — the OS could not react to a timer or a device in the middle of a process, so deadlines and preemption become impossible.

There are several criteria to check when deciding which scheduling algorithm is “best”. In general CPU utilisation and throughput are maximised while the other factors are reduced for proper optimisation.

Formulas and worked numbers → Numericals · CPU Scheduling · Revision · Formula sheet.

Real-time scheduling

Real-time systems are like super-fast computers that handle tasks needing quick responses. There are two types of tasks:

• Hard real-time tasks — like urgent missions; they must be done exactly on time or something really bad could happen.
• Soft real-time tasks — important too, but it is okay if they are a bit late sometimes; nothing terrible will happen.

Real-time tasks are the super-important missions that need quick responses: some must be done right away (hard), others can wait a little (soft). The scheduler's job is to guarantee that deadlines are met, which is why it is priority-driven and preemptive.

Demand scheduling

Scheduling is the process by which the process manager removes an active process from the CPU and selects another process based on a specific strategy. Process scheduling is an integral part of a multiprogramming application set: more than one process is loaded into usable memory at a time and the loaded processes share the CPU using repetition time (time multiplexing). There are three types of process schedulers — long term (job), short term (CPU) and medium term.

Objectives of demand scheduling

• Utilisation of CPU at maximum level — keep the CPU as busy as possible.
• Allocation of CPU should be fair.
• Throughput should be maximum — the number of processes that complete their execution per time unit should be maximised.
• Minimum turnaround time — time taken by a process to finish execution should be the least.
• Minimum waiting time — and the process should not starve in the ready queue.
• Minimum response time — the time when a process produces its first response should be as less as possible.

The Convoy Effect is a phenomenon associated with the First Come First Serve (FCFS) algorithm in which the whole operating system slows down because of a few slow processes.

FCFS is non-preemptive: once CPU time has been allocated to a process, other processes get CPU time only after the current process has finished. This property produces the convoy situation.

How it happens, step by step

1. Suppose one CPU-intensive process (large burst time) is in the ready queue, together with several processes with relatively less burst time that are I/O-bound.
2. The I/O-bound processes are allocated CPU time first — they are quickly executed and then go to their I/O queues.
3. Now the CPU-intensive process is allocated CPU time. Because its burst time is high it takes a long time to complete.
4. While it is running, the I/O-bound processes complete their I/O operations and are moved back to the ready queue.
5. However, the I/O-bound processes are made to wait, because the CPU-intensive process still has not finished. This also leaves the I/O devices idle.
6. When the CPU-intensive process ends it is sent to the I/O queue so it can access an I/O device. Meanwhile the I/O-bound processes get CPU time and move back to the I/O queue.
7. But now they are made to wait again because the CPU-intensive process is still accessing its I/O device — so the CPU sits idle.

Hence in the convoy effect one slow process slows down the performance of the entire set of processes and wastes CPU time and other devices.

Round Robin — the two things that decide everything

• If the quantum is very large (larger than every burst), RR degenerates into FCFS.
• If the quantum is very small, context-switch overhead dominates and throughput collapses.
• Rule of thumb: keep the quantum much larger than the context-switch time; typical values are 10–100 ms.

Aging

The remedy for starvation in priority scheduling: gradually increase the priority of a process that has waited a long time, so it eventually reaches the head of the queue.