Operating Systems — Complete Study Companion

Definition

An operating system (OS) is a system software that acts as an intermediary between the user and the computer hardware. It is a program that manages all the resources of a computer system — CPU, memory, storage, and I/O devices — and provides an environment in which user programs can execute conveniently and efficiently.

Famous definitions: “An OS is a program that controls the execution of application programs and acts as an interface between the user and the computer hardware” and Tanenbaum's view — “the OS is the government: it provides an environment in which other programs can do useful work.”

Why is an OS required?

• Convenience — hardware is low-level and hard to use directly; the OS offers simple abstractions (files, folders, windows, processes) through a user interface (CLI/GUI).
• Process management — creates, schedules, and terminates processes; allows multiprogramming so the CPU is never idle.
• Memory management — allocates and frees main memory among programs, protecting them from each other.
• Resource allocation & sharing — fairly distributes CPU time, memory, devices and files among competing users/programs.
• File management — organises data into files and directories on storage devices and controls access to them.
• I/O handling — hides the complexity of device controllers and drivers behind uniform system calls.
• Protection & security — isolates users and processes, prevents unauthorised access to data and resources.
• Error detection & handling — constantly monitors the system for errors (CPU, memory, devices) and takes corrective action.
• Accounting & performance — keeps statistics on resource usage for billing, tuning and planning.

Definition

A system call is the programmatic interface through which a user program requests a service from the operating system kernel. When a program needs something only the kernel may do (I/O, memory, creating a process), it invokes a system call, which raises a trap / software interrupt, switching the CPU from user mode to kernel mode; the kernel executes the request and returns the result to the program.

Categories of system calls

1. Batch Operating System

Jobs with similar needs are batched together and executed as a group by an operator; there is no direct user interaction. Early systems (IBM mainframes) worked this way.

• Users submit jobs on cards/tape; the OS processes them one after another in a batch.
• Jobs share the same nature/requirements, so the operator groups them to reduce setup time.
• High throughput, but no interactivity — turnaround time can be long, and debugging is hard.
• Modern usage: payroll processing, bank statement generation, report printing.

2. Real-Time Operating System (RTOS)

Guarantees that results are produced within a fixed, bounded deadline; correctness depends not only on the result but also on when it is delivered.

• Hard real-time: deadlines must never be missed — critical physical tasks (missile guidance, airbags, pacemakers).
• Soft real-time: missing a deadline only degrades quality (video streaming, online games, multimedia).
• Event-driven, minimal jitter, priority-based scheduling, small kernels; used in embedded/industrial control systems.

3. Time-Sharing Operating System

The CPU is switched rapidly among multiple users/programs (multiprogramming with a time quantum) so each gets the illusion of having its own machine — also called multitasking.

• Many users share the system simultaneously via terminals — interactive processing.
• Each user gets a small time slice; response time is short (typically < 1 second).
• Uses CPU scheduling, swapping/virtual memory and spooling; improves CPU utilisation and gives faster response.
• Examples: UNIX, Linux, Windows multi-user servers.

4. Distributed Operating System

Multiple independent, networked computers appear to users as a single coherent system; the OS coordinates them via message passing.

• Each node has its own memory and CPU; no shared physical clock or memory.
• Resource sharing, load balancing, computation speedup, and high availability (graceful degradation if a node fails).
• Communication takes place over a network using messages/RPC — slower than shared memory.
• Examples: LOCUS, Amoeba, cluster and cloud systems.

5. Parallel Operating System (Multiprocessor / Multicore)

Runs on systems with two or more processors in close communication sharing the bus, clock, memory and peripherals, executing multiple tasks truly simultaneously.

• Increased throughput — more work per unit time; economical — resources are shared.
• Increased reliability — graceful degradation / fault tolerance if one processor fails.
• Symmetric multiprocessing (SMP): all processors are peers running one OS copy; asymmetric: a master controls slaves.
• Key issue: cache coherence and synchronisation among processors.

An OS provides services both to users (making the system convenient) and to programs (making execution efficient):

• Program execution — loads a program into memory and runs it; handles scheduling and normal/abnormal termination.
• I/O operations — every program needs input/output; the OS performs them on behalf of the user via device drivers (file or device read/write).
• File-system manipulation — create/delete files and directories, read/write/search, list, and control permissions (read/write/execute).
• Communication — allows processes to exchange information via shared memory or message passing, on the same machine or across a network.
• Error detection — continuously checks CPU, memory, I/O devices and programs for errors; reports and recovers to keep the system consistent.
• Resource allocation — allocates CPU cycles, memory, files, storage and devices to multiple users/jobs running at the same time (using schedulers, partitioning, queues).
• Accounting — records which resources, how much, and for whom — for billing, usage statistics and performance tuning.
• Protection & security — controls access to system resources (mode bits, permissions) and authenticates users so one user/process cannot harm another.
• User interface — CLI (command interpreter / shell), GUI (windows, icons, menus, pointer), or touch/voice interfaces.

Yes. Both views (Tanenbaum's) describe the OS completely — one looks upward (service provider), the other downward (manager).

1. OS as an Extended Machine (Top-down view)

The bare machine's hardware is complicated: disk drives, timers, GPUs each expose messy, low-level interfaces. The OS hides the hardware details and presents the user with a cleaner, easier, more abstract “virtual machine” — files instead of disk blocks, processes instead of CPU registers, virtual memory instead of physical RAM addresses.

• Users see abstractions: processes, files, directories, sockets, pipes, virtual memory.
• The abstraction is simpler to use and portable across different hardware.
• Hence the OS extends the machine: hardware + OS = a more powerful virtual machine.

2. OS as a Resource Manager (Bottom-up view)

A computer has limited resources — CPU time, memory, disk space, devices — demanded by many competing programs. The OS allocates, schedules, shares and protects these resources among processes fairly and efficiently.

• Multiplexing in time — different programs take turns using the CPU (scheduling).
• Multiplexing in space — memory and disk are divided among programs (allocation).
• Also ensures protection (no process steals another's resources), accounting, and resolves conflicts between users.

OS structure refers to how the components of the operating system are organised and how they interact with the hardware and user programs — i.e., the internal architecture of the OS. Three classic structures:

1. Simple / Monolithic Structure (MS-DOS)

The OS is written as one big program with no clear separation between layers — applications and the OS can call almost anything. It is simple to build and fast, but poorly structured and fragile: any bug can crash the whole system, and it is hard to extend or port.

2. Layered Structure (THE Operating System)

The OS is divided into N levels (layers): layer 0 is the hardware and layer N is the user interface. Each layer only uses the services of the layer directly below it.

• Advantages: modular design — easier to debug and verify (errors are localised to one layer), easy to replace/extend a layer, information hiding.
• Disadvantages: hard to define layers properly (each must use only lower layers), performance cost of crossing many layers; less efficient than monolithic.
• Examples: THE system (Dijkstra, 6 layers), Multics (8 layers), MULTICS ring model.

3. Virtual Machine Structure

A virtual machine treats the hardware + host OS as if it were bare hardware: the VM monitor creates the illusion that each process/user has its own dedicated processor with its own (virtual) memory and devices. Each guest can run its own complete OS on top of the host.

• Implemented by a Virtual Machine Monitor (hypervisor) — e.g., VMware, VirtualBox, Hyper-V, JVM (for Java bytecode), IBM CP/CMS.
• Advantages: complete protection & isolation of VMs; different OSes on one physical machine; easy research, development and testing; snapshots, live migration and cloud computing are possible.
• Disadvantages: implementing the virtual CPU/devices is difficult; exact simulation of hardware introduces overhead (virtualisation cost).

Preemptive scheduling: the CPU can be taken away from a running process before it finishes (on timeout, or when a higher-priority process arrives). Non-preemptive (cooperative): once a process gets the CPU it keeps it until it terminates or voluntarily switches to waiting state.

(i) Gantt Charts

(ii) Waiting Time (WT = Start-time in CPU total − Burst… i.e. time spent in ready queue)

WT = Turnaround − Burst. RR e.g. P5 runs at 4,7,9,11,13 and finishes at 14 ⇒ WT = 14 − 5 = 9.

(iii) Turnaround Time (TAT = Completion − Arrival, arrival = 0)

(iv) Conclusion

Why IPC is required

Each process has its own isolated address space, so cooperating processes cannot simply share variables. Inter-process communication (IPC) — provided by the OS via shared memory or message passing — is needed because:

• Information sharing — several processes (e.g., a web server and its helpers) must access the same data.
• Computation speedup — a big task can be split among processes/cores running in parallel.
• Modularity — a system is designed as separate cooperating modules (compiler, editor, shell) that need to talk.
• Convenience — a user may work on many tasks at once (edit, compile, browse) which exchange data.
• Synchronization & coordination — processes must signal events (producer tells consumer that data is ready).

User thread vs Kernel thread

The two levels are combined by multithreading models:

Definition

A race condition is a situation where several processes access and manipulate shared data concurrently, and the final result depends on the particular order (timing) in which their accesses are interleaved. To avoid it, the shared-data accesses must be made mutually exclusive — execution must not be interleaved inside the region that touches shared data.

Classic example: two processes execute counter++ (registers: load → increment → store). If both read counter = 5 and interleave their stores, the final value becomes 5 instead of 7 — one update is lost.

Techniques for avoiding race conditions

1. Disabling interrupts (hardware approach) — a process entering the critical section turns interrupts off, so no timer preemption can interleave another process. Simple for a single CPU, but dangerous to give user programs this power and does not scale to multiprocessors.
2. Lock variables (software busy-wait) — a shared boolean; test-and-set it before entering. A naive single lock variable itself suffers a race — safe only when done with atomic instructions.
3. Strict alternation — an integer turn alternates entry rights between the two processes (0, 1, 0, 1…). It gives mutual exclusion, but violates progress: a process must wait even when the other is not interested in entering.
4. Peterson's solution (pure software) — two-process protocol using a flag[] array and turn variable; guarantees mutual exclusion, progress and bounded waiting.
5. Atomic hardware instructions — TSL / Test-and-Set, swap — the instruction reads and writes a lock atomically, used to build spinlocks that work even on multiprocessors.
6. Sleep & wakeup primitives — instead of busy-waiting, a blocked process goes to sleep and the process whose action unblocks it issues a wakeup (the basis of the sleeping implementations in producer–consumer; the classic risk is a lost wakeup if signals are not remembered — solved by semaphores).
7. Mutex locks — an OS-provided lock: acquire() before the critical section, release() after; blocks (sleeps) instead of busy-waiting; has ownership.
8. Semaphores — an integer counter manipulated atomically by wait() / signal(); enforces mutual exclusion (binary semaphore) and ordering/resource counting (counting semaphore); waiters are put to sleep, so no busy waiting.
9. Monitors — a high-level language construct: shared data + procedures inside one object where only one process may be active at a time; condition variables handle waiting (e.g., Java synchronized).

Peterson's Solution

A classic software-based solution to the critical-section problem for two processes P₀ and P₁. It uses two shared variables: int turn (whose turn it is to enter) and boolean flag[2] (is a process ready to enter?).

// shared:  int turn;  boolean flag[2] = {false, false};
// code for process P[i]  (j = other process)
do {
    flag[i] = true;      // I want to enter
    turn    = j;          // but let the other go first
    while (flag[j] && turn == j) ;  // busy wait

        critical section

    flag[i] = false;      // I am done
        remainder section
} while (true);

• Mutual exclusion: P_i and P_j cannot both be inside — only the one whose flag is true and whose turn it is enters.
• Progress: if the other process is not interested (flag[j] = false), P_i enters immediately.
• Bounded waiting: turn = j ensures P_j enters after at most one entry by P_i.
• Caveat: on modern out-of-order CPUs it may fail without memory barriers — it is of historical/conceptual value.

TSL (Test-and-Set Lock instruction)

Definition: an atomic hardware instruction: TSL lock, R1 reads the old value of lock into R1 and writes TRUE to lock in one indivisible step (memory is locked on the bus during it).

Purpose: to build mutual exclusion that cannot race — whoever executes TSL first gets the lock; others spin. It fixes the weakness of pure software locks and works on multiprocessors; used to implement spinlocks.

enter_region:
    TSL REGISTER, LOCK      // atomically copy & set lock
    CMP REGISTER, #0        // was lock free?
    JNE enter_region        // no – keep trying (spin)
    RET                     // yes – critical section entered
leave_region:
    MOVE LOCK, #0           // release
    RET

Mutex (Mutual Exclusion lock)

Definition: an OS-level locking variable with ownership: only the thread that locked a mutex may unlock it. Calls: acquire()/lock() before and release()/unlock() after the critical section.

Purpose: protect a shared resource from concurrent access with no busy waiting — if the lock is taken, the thread is put to sleep (block) and woken when released. Simplest tool when a resource is used by one thread at a time.

Semaphore

Definition: an integer variable S accessed only through two atomic operations: wait(S) / P (decrement, block if S < 0) and signal(S) / V (increment, wake a waiter).

wait(S){ while(S <= 0); S--; }   signal(S){ S++; }  // spin version; OS version sleeps

Purpose: a general-purpose synchronisation tool — binary semaphore (0/1) gives mutual exclusion like a mutex but without ownership; counting semaphore manages N identical resources or counts events; can also enforce execution ordering (P₂ waits on a semaphore P₁ signals). Semaphores avoid busy waiting when implemented with blocked queues.

Problem: 5 philosophers sit around a circular table, alternating between thinking and eating. Between every two adjacent plates lies one chopstick (5 total). A philosopher must pick up both the left and the right chopstick to eat, and put both down when finished. The problem models the allocation of multiple exclusive resources among competing processes and shows how naive resource allocation leads to deadlock and starvation.

Naive (deadlock-prone) solution with semaphores

// chopstick[0..4] : semaphores, all initialised to 1
philosopher(i):
    while(true){
        think();                    // non-critical work
        wait(chopstick[i]);          // pick up RIGHT chopstick
        wait(chopstick[(i+1)%5]);    // pick up LEFT chopstick
        eat();
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]);
    }

Why it fails: if every philosopher picks up the right chopstick simultaneously, each waits forever for the left one — circular wait ⇒ deadlock.

Correct solutions

1. Allow at most 4 philosophers at the table — add wait(room) with room = 4; someone always gets both sticks.
2. Pick up both chopsticks atomically (a monitor/mutex region: take them together or not at all).
3. Asymmetric (odd–even) rule — odd philosophers pick the left stick first, even ones the right first; the circular wait chain is broken.

// fix (c): asymmetric pick-up — breaks circular wait
if (i % 2 == 0) { wait(c[i]);      wait(c[(i+1)%5]); }
else           { wait(c[(i+1)%5]); wait(c[i]); }

Problem (bounded buffer): a producer process generates items and puts them into a fixed-size circular buffer of size N; a consumer removes and uses them. The two share the buffer, so three conditions must be enforced: the producer must not insert when the buffer is full, the consumer must not remove when it is empty, and insertions/removals (shared counter/indices) must be mutually exclusive.

Semaphore solution

// shared:
#define N 10
semaphore mutex = 1;   // binary — protects buffer & counter
semaphore empty = N;   // counting — free slots
semaphore full  = 0;   // counting — filled slots

Producer:                       Consumer:
while(true){                    while(true){
  item = produce_item();          wait(full);   // any item?
  wait(empty);  // free slot?      wait(mutex);
  wait(mutex);                    item  = remove_item();
  insert_item(item);              signal(mutex);
  signal(mutex);                  signal(empty); // +1 free slot
  signal(full); // +1 full slot     consume_item(item);
}                               }

Problem: A barbershop has one barber, one barber chair, and a waiting room with N chairs. The barber sleeps when there are no customers. A customer who arrives and finds a free waiting chair sits down and wakes the barber; if the shop is full the customer leaves. The barber cuts one customer's hair, then checks the waiting room. It models resource allocation with a limited service provider and bounded queue (a generalisation of producer–consumer with a finite waiting room).

• Shared state: number of waiting customers, protected by a mutex.
• Signals: customers — barber waits on it (sleeps when 0); barber — customer waits on it for his turn.

// shared:
#define N 5                          // waiting-room chairs
semaphore customers = 0;              // waiting customers (barber sleeps if 0)
semaphore barber    = 0;              // barber ready signal
semaphore mutex     = 1;              // guards 'waiting' counter
int waiting = 0;                      // customers in waiting room

Barber:                               Customer:
while(true){                          wait(mutex);
  wait(customers);  // sleep if none  if (waiting < N){
  wait(mutex);                            waiting++;
  waiting--;                              signal(customers);
  signal(barber);   // invite one        signal(mutex);
  signal(mutex);                          wait(barber); // wait for turn
  cut_hair();                             get_haircut();
}                                     }
                                          else signal(mutex); // shop full → leave

How it works

1. Barber starts: wait(customers) blocks — he sleeps.
2. A customer increments waiting, signals customers → barber wakes and decrements the count.
3. Barber signals barber — exactly one waiting customer takes the chair; others keep waiting.
4. If waiting == N on arrival, the customer releases the mutex and leaves (no deadlock, no lost wake-ups).

Process vs Thread

A process is a program in execution with its own address space, file descriptors, registers and PCB. A thread is the basic unit of CPU execution inside a process — it shares the process's address space and resources with sibling threads but has its own program counter, register set, stack and state (TCB).

Process State Transition Model (5-state)

As a process executes, it moves through states. Transitions:

• Admitted — job submitted; PCB created; moves New → Ready.
• Dispatch — scheduler selects it; Ready → Running.
• Interrupt / time-out — higher priority arrives or quantum expires; Running → Ready.
• Event wait (I/O request) — Running → Blocked/Waiting.
• Event completion — the awaited I/O finishes; Blocked → Ready.
• Exit — Running → Terminated; OS reclaims resources.

Extended (7-state) model adds Ready-suspend and Blocked-suspend states, when the OS swaps blocked processes out to disk to free memory.

Definition

Each process has a segment of code, the critical section (CS), in which it accesses shared data / resources (variables, files, tables). When one process is executing in its critical section, no other process may enter its own critical section that touches the same shared data — otherwise race conditions corrupt the data.

do {
   entry section        // request permission (acquire lock)
      CRITICAL SECTION  // touch shared data
   exit section         // release lock
   remainder section    // other code
} while(true);

Minimum requirements of any CS solution

1. Mutual exclusion — at most one process may execute inside its critical section at a time.
2. Progress — if the CS is free and some processes wish to enter, only those processes participate in choosing who enters next, and the choice cannot be postponed indefinitely.
3. Bounded waiting — there is a limit on how long a process waits to enter after requesting (no starvation).

Software solution — Peterson's algorithm

The best-known two-process software solution (full code in Q3 above): it combines a flag[] array (interest in entering) with the turn variable (permission when both are interested).

// Process Pi  (Pj = the other)   — satisfies all 3 requirements
flag[i] = true;      // entry section: express interest
turn    = j;         // politely yield turn
while (flag[j] && turn == j);   // wait while other interested & has turn
   CRITICAL SECTION
flag[i] = false;     // exit section

Why it works: P_i can enter only if flag[j] == false (P_j not interested ⇒ no conflict) or turn == i (it is P_i's turn). Both conditions can hold for both processes only if both set turn = j and turn = i simultaneously — impossible; hence mutual exclusion. turn alternates, giving bounded waiting.

Mutual exclusion

Mutual exclusion is the guarantee that when one process is executing in its critical section, no other process can execute in its critical section (for the same shared resource) — i.e., the shared accesses are serialised so the result never depends on interleaving.

Achieving it with Peterson's solution

// Shared variables
int turn;
boolean flag[2] = {false, false};

// Structure of process Pi (i = 0 or 1, j = 1 - i)
do {
   flag[i] = true;          // 1. I want to enter
   turn    = j;             // 2. you may go first
   while (flag[j] && turn == j) ;  // 3. busy-wait (entry)

      /* ---- CRITICAL SECTION ---- */

   flag[i] = false;         // 4. exit: I am out
      /* remainder section */
} while (true);

Proof of mutual exclusion

P_i enters the CS only when flag[j] == false or turn == i. Suppose both P₀ and P₁ were inside: then flag[0] == flag[1] == true. Each set turn last to the other's number, so turn can hold only one value (say 1). Then P₀'s entry condition flag[1] && turn == 1 is true — so P₀ must still be waiting — a contradiction. Hence at most one process is ever in the CS ⇒ mutual exclusion holds. (Progress: a waiting process is blocked only while the other is genuinely interested; Bounded waiting: turn alternates, so P_j waits at most one CS execution of P_i.)

Definition

IPC (Inter-Process Communication) is the mechanism provided by the OS that allows cooperating processes to exchange data and synchronise their actions. It has two fundamental models: shared memory (fast; processes read/write a common region; user-managed synchronisation) and message passing (slower; kernel transmits send()/receive() messages; good for distributed systems).

Logical implementation methods of message passing

1. Naming — direct vs indirect
   Direct: processes address each other explicitly (send(P, msg), receive(Q, msg)) — one link per pair, automatic bidirectional.
   Indirect: messages go to mailboxes/ports (send(A, msg)) — a link exists only if both share a mailbox; a mailbox can be owned by a process or by the OS; supports many-to-many communication.
2. Synchronisation — blocking vs non-blocking
   Blocking (synchronous): sender waits until the message is received; receiver waits until a message arrives — tight synchronisation (rendezvous).
   Non-blocking (asynchronous): sender continues immediately; receiver polls or is signalled later.
3. Buffering — capacity of the queue on the link
   Zero capacity: no queue — sender must block until receiver ready (message systems become rendezvous).
   Bounded capacity: finite queue of n messages — sender blocks only when the queue is full.
   Unbounded capacity: infinite queue — sender never waits.
4. Message format & addressing — fixed-size messages (simple, low overhead, used in OS kernels) vs variable-size (flexible, used in distributed systems); send by copy vs send by reference.
5. Queueing discipline — FIFO ordering of messages, or priority queues for urgent messages.
6. Exceptions / extra: mailbox ownership, message acknowledgement, timeouts and failure handling in distributed settings.

Deadlock

A deadlock is a situation in which a set of processes is blocked because each process holds a resource and waits for a resource held by another process in the set. Since nobody releases what the others need, none can ever proceed — they wait forever.

Example: P1 holds printer, requests tape drive; P2 holds the tape drive and requests the printer. Both block permanently.

Preemptable vs Non-preemptable resources

A Resource Allocation Graph (RAG) is a directed graph that describes the state of resource allocation in the system — who holds what and who is waiting for what.

• Vertices: circles = processes P_i; rectangles = resource types R_j (dots inside a rectangle = number of instances of that resource).
• Request edge P_i → R_j (process waiting for a resource).
• Assignment edge R_j → P_i (an instance is held by the process).

Interpretation rules

• No cycle in the graph ⇒ no deadlock (safe).
• Cycle + only single instances of each resource in the cycle ⇒ deadlock exists (cycle is necessary and sufficient).
• Cycle with multiple instances ⇒ cycle is only necessary; deadlock may exist (need the detection algorithm to decide).

A deadlock can arise if and only if all four of the following conditions hold simultaneously:

1. Mutual exclusion — at least one resource is non-sharable: only one process can use it at a time; any other requesting process must wait (e.g., a printer, a locked record).
2. Hold and wait — a process is holding at least one resource while waiting to acquire additional resources held by others.
3. No preemption — resources cannot be forcibly taken from a process; they are released only voluntarily when the process finishes using them.
4. Circular wait — there exists a circular chain of processes {P0, P1, …, Pn} such that P_i waits for a resource held by P_{(i+1) mod n}; each process waits for the next one's resource, forming a cycle.

Before recovery: deadlock detection

• Single instance per resource type: build the wait-for graph (collapse resource nodes out of the RAG) — a cycle in it means deadlock; run the check periodically or on every request.
• Multiple instances: use a detection algorithm identical in shape to Banker's safety test: Work = Available, Finish[i] = false (or Allocation_i = 0); repeatedly pick a process with Request_i ≤ Work and add its Allocation into Work. If some Finish stays false, those processes are deadlocked.

When detection finds a deadlock, the system must break the circular wait. Recovery techniques:

1. Process termination
   a) Abort all deadlocked processes — certain but very costly (all their work is lost).
   b) Abort one process at a time until the cycle breaks — after each kill, re-run the detection algorithm; choose the victim by cost (CPU time used, resources held, priority, how long to completion).
2. Resource preemption — forcibly take resources from some processes and give them to others until the cycle is broken. Requires three issues to be handled:
   • Selecting a victim — minimise cost (resources held, time consumed).
   • Rollback — the robbed process cannot continue normally; return it to some safe state (checkpoint) and restart it later. Since a safe state is hard to determine, total restart is often used.
   • Starvation — the same victim may always be picked; include the number of rollbacks in the cost to guarantee finite progress.
3. Manual / operator intervention — kill processes by hand (e.g., task manager), used in practice on interactive systems.

Prevention ensures the system never enters a deadlocked state by breaking at least one of the four necessary conditions by design:

1. Attack mutual exclusion — make resources sharable where possible (read-only files, spooling: a printer daemon accepts jobs so no process holds the printer directly). Limitation: some resources are inherently non-sharable.
2. Attack hold-and-wait — require every process to request all its resources at once and block until all are available; or allow a request only when the process holds nothing. Drawbacks: low resource utilisation and possible starvation.
3. Attack no-preemption — if a process holding some resources requests another that cannot be granted immediately, preempt (take back) all resources it holds and it must re-request them later; or preempt resources from waiting processes. Works for state-saveable resources (CPU, memory) but not for printers mid-job.
4. Attack circular wait — impose a total ordering on resource types (numbered 1…n) and force every process to request resources in strictly increasing order (and release in decreasing order). No cycle can form, hence no deadlock. Most practical method (e.g., always lock A before B).

The Banker's algorithm (Dijkstra) is a deadlock avoidance technique for multiple instances of resources. Named because it works like a banker never granting loans that could leave him unable to satisfy all customers: the OS never grants a request if granting could lead to an unsafe state (one from which deadlock is possible).

Data structures (n processes, m resource types)

• Available[m] — instances of each resource currently free.
• Max[n][m] — maximum demand of each process.
• Allocation[n][m] — resources currently held by each process.
• Need[n][m] = Max − Allocation — resources still needed.

Safety algorithm (is the state safe?)

1. Let Work = Available and Finish[i] = false for all i.
2. Find an i with Finish[i] = false and Need[i] ≤ Work. If none exists, go to step 4.
3. Process P_i can finish: Work = Work + Allocation[i], set Finish[i] = true; go to step 2.
4. If all Finish[i] = true, the system is in a safe state; the order of completion is a safe sequence. Otherwise the state is unsafe.

Request-resource algorithm (when P_i requests Request_i)

1. If Request_i ≤ Need_i, go to 2; else error (exceeded declared maximum).
2. If Request_i ≤ Available, go to 3; else the process must wait (resources not free).
3. Pretend to allocate: Available −= Request_i; Allocation_i += Request_i; Need_i −= Request_i. Run the safety algorithm — if the resulting state is safe, grant the request; otherwise roll back and let P_i wait.

Applying the Banker's algorithm to the given snapshot (10 instances of A, 5 of B, 7 of C):

(i) Safety algorithm — Work starts at Available = (3, 3, 2)

(ii) Request from P1 = (1, 0, 2)

Step 1 — Request ≤ Need_P1: (1,0,2) ≤ (1,2,2) ✓   Step 2 — Request ≤ Available: (1,0,2) ≤ (3,3,2) ✓

Step 3 — pretend allocation: Available = (3,3,2) − (1,0,2) = (2,3,0); Allocation_P1 = (3,0,2); Need_P1 = (0,2,0).

Memory management is the OS function that controls and coordinates the use of main memory: it keeps track of every memory location (free or allocated), allocates memory to processes when they need it and reclaims it when they finish, and translates logical addresses to physical addresses.

Main functions

• Keeping track of which parts of memory are in use, by whom, and which are free.
• Allocation & deallocation of memory to processes (contiguous or paged) as needed.
• Address translation (MMU) — mapping logical/virtual addresses generated by the CPU onto physical addresses in RAM.
• Protection & sharing — a process may not touch memory outside its space; controlled sharing is possible (base + limit registers).
• Multiprogramming support — bringing more processes into memory to raise CPU utilisation: swapping, paging, segmentation, virtual memory.

Goal: maximise memory utilisation and multiprogramming degree while keeping translation fast and protecting processes from each other.

Paging splits memory into equal-sized blocks so that physical memory can be allocated non-contiguously:

• Frame (page frame): a fixed-size block of physical memory (RAM). Physical memory is divided into frames — the containers.
• Page: a block of the same fixed size in logical (virtual) memory of a process — the contents that get loaded into frames.
• Common sizes: 4 KB; always a power of 2 (256 B – 1 GB). Page size = frame size, so any page can go into any free frame.
• The OS keeps a page table per process recording which frame holds each page — logical address = (page number p, offset d) → physical address = (frame number f, offset d), with d unchanged.
• Consequences: no external fragmentation (all frames equal), but possible small internal fragmentation in a process's last page.

Logical (virtual) address: the address generated by the CPU while a program runs — what the program "sees". The set of all logical addresses forms the logical address space (0 … 2ⁿ−1).

Physical address: the actual location in main memory (what the memory unit sees, loaded into the address register). The set of all physical addresses forms the physical address space, corresponding to the real RAM frames.

The MMU (memory management unit) hardware converts logical → physical at run time using the relocation/base register and page table.

Swapping is temporarily moving a process (or part of it) from main memory to a backing store (swap area on disk) and later bringing it back for continued execution. It lets the total memory committed to processes exceed physical RAM, increasing the degree of multiprogramming.

• Swap out: an idle/blocked process is copied to the backing store to free RAM for others.
• Swap in: when memory frees or the process becomes runnable, it is brought back (possibly into a different location — dynamic relocation needed).
• Cost: swap time dominates — transfer of the whole process image on the disk bus; decided by the medium-term scheduler.

Allocation techniques

• Fixed (static) partitioning — memory pre-divided into fixed regions (equal or unequal); one process per partition → internal fragmentation.
• Dynamic partitioning — a partition exactly as big as the process is created on demand → external fragmentation, solved by compaction.
• Placement strategies for a free hole: First-fit — first hole big enough (fastest); Best-fit — smallest sufficient hole (least leftover, but tiny useless fragments); Worst-fit — largest hole (leaves large usable leftovers).
  (Next-fit = first-fit restarting from the last allocated point.)
• Non-contiguous schemes — paging (fixed-size pages/frames) and segmentation (variable-size logical segments).

Paging is a memory-management scheme that breaks the logical address space of a process into fixed-size pages and physical memory into same-size frames, and loads any page into any free frame — physical memory allocation becomes non-contiguous. A per-process page table maps page numbers to frame numbers.

Address: logical address = (p, d) — page number p indexes the page table to get frame f; offset d stays unchanged; physical address = f × page-size + d. Example: page size 4 KB ⇒ a 32-bit address has p = upper 20 bits, d = lower 12 bits.

Why paging is required

• No external fragmentation — all holes are the same size, so any free frame is usable.
• A process need not sit in one contiguous block ⇒ no compaction, higher memory utilisation, more multiprogramming.
• Simple allocation — keep a list of free frames; grab any.
• Foundation of virtual memory — pages can be brought in on demand (demand paging), shared (common code), and protected per page (read/write bits).

Segmentation is a memory-management scheme that supports the user/programmer view of memory: a program is a collection of variable-size logical units — main program, functions, objects, stack, arrays, global variables — called segments. Each segment is allocated contiguously, but different segments need not be adjacent.

Address: logical address = (segment number s, offset d). The segment table stores per segment a base (start physical address) and limit (length): hardware checks d < limit (else trap — protection), then physical = base + d.

Why segmentation is required

• Matches the programmer's logical view — code vs data vs stack treated separately, unlike paging's meaningless one-dimensional memory.
• Protection per logical unit — e.g., mark the code segment execute-only, shared library segments read-only; limit check catches invalid access.
• Sharing — a single segment (library, text editor) can be shared by many processes by pointing at the same base.
• Grows naturally — a stack segment can grow independently of the data segment.
• Drawback: variable sizes ⇒ external fragmentation (needs compaction / best-fit placement).

Extra points: paging is faster/simpler to allocate (any free frame); segmentation gives finer per-logical-unit protection & sharing; modern systems combine both (segmentation with paging).

Fragmentation is wasted memory that cannot be used effectively. It occurs in two forms:

Internal fragmentation

• What: unused space inside an allocated block/partition — the waste is internal to the allocated region.
• How it occurs: when memory is handed out in fixed-size units. A process needing, say, 18 KB in 4 KB pages gets 5 pages = 20 KB, but the last page is only ¾ used — 2 KB inside it can never be used by anyone else.
• Seen in: fixed partitioning, paging (last page of a process), filesystem blocks.

External fragmentation

• What: free memory exists in scattered small holes between allocations — total free space is enough for a request, but no single contiguous hole is big enough.
• How it occurs: processes of different sizes are repeatedly loaded and removed from variable-size (dynamic) partitions, chopping memory into non-contiguous pieces.
• Seen in: dynamic partitioning, segmentation. Solved by compaction or by switching to paging.

Virtual memory is a technique that allows the execution of processes that are not completely in main memory. The programmer sees a very large, uniform logical address space; the OS + hardware keep only the active parts of each process in RAM and the rest on disk, transparently moving data as needed (paging/segmentation on demand).

Why it is required

• Run programs larger than physical RAM — user is freed from the memory-size limit.
• Higher CPU utilisation / multiprogramming — more processes fit in RAM at once, so the CPU rarely idles.
• Less I/O for load/swap — only the needed pages are loaded, so processes start faster.
• Efficient process creation — copy-on-write (fork shares pages until written) and memory-mapped files become possible.
• Programs need not worry about memory size — no manual overlays; the same program runs on machines with different RAM.
• Enables page sharing and per-page protection between processes.

Implemented with demand paging + page replacement; governed by locality of reference, bounded below by thrashing if over-committed.

Demand paging is the implementation of virtual memory in which a page is brought into memory only when it is actually referenced (demanded) during execution — a "lazy swapper" (pager) loads pages, instead of swapping the whole process in at start.

• Pages needed at startup are loaded; others are marked invalid in the page table ("not in memory").
• Page fault: reference to an invalid page traps to the OS → the pager locates the page on disk → finds/replaces a free frame → reads the page in → updates the page table (valid) → restarts the faulting instruction; the process continues as if nothing happened.
• Hardware support: page table with valid/invalid bit, backing store, and (optionally) a reference/dirty bit.
• Effective access time = (1 − p) × memory-access + p × page-fault-time, where p = page-fault rate — performance depends critically on locality keeping p tiny.

Pure demand paging: start with zero pages and fault everything in. Advantages: less I/O, less memory used, faster response, more users.

Page replacement is the mechanism used when a page fault occurs and no free frame exists: the OS chooses a victim page currently in memory, writes it back to disk (if modified), and loads the requested page into the freed frame.

Why it is required

• With demand paging, total pages needed by all processes exceed physical frames — someone must give up a frame when memory is full.
• The choice of victim decides performance: replacing a page that will be used again soon causes more faults (and more disk I/O, which costs ~10⁵× a memory access).
• Good algorithms (LRU/Optimal approximations) minimise the fault rate by exploiting locality of reference, keeping the working set of each process resident and avoiding thrashing.

Overhead to minimise: two page transfers per replacement (out + in) — reduced with a modify (dirty) bit: clean victims need no write-back.

• FIFO: replace the page that has been in memory the longest (oldest arrival) — implemented with a simple queue. Easy, but ignores usage; suffers Belady's anomaly (more frames can cause more faults, e.g., string 1,2,3,4,1,2,5,1,2,3,4,5 gives 9 faults with 3 frames but 10 with 4).
• Optimal (OPT/MIN): replace the page that will not be used for the longest time in the future. Provably the lowest possible fault rate, but needs future knowledge — used only as a benchmark; practical algorithms approximate it.
• LRU (Least Recently Used): replace the page that has not been used for the longest time in the past — the past is a good predictor of the future (locality). Optimal in practice; needs hardware help: counters/time-stamps or a stack of references (expensive to implement exactly).
• Second chance (clock): FIFO plus a reference bit. When a page is chosen as victim, if its reference bit = 1, clear the bit and give it a "second chance" (move to the tail); if 0, replace it. Pages used recently survive; approximates LRU with cheap queue bookkeeping.
• LFU (Least Frequently Used): replace the page with the smallest reference count. Cheap counters, but a page that was heavily used in the past keeps a high count even when no longer needed (fix: shift/right-decay the counters periodically). It is the mirror image of MFU, which argues the least-used page was probably just loaded.

All three algorithms succeed in placing all three processes (30K used of 61K total).

With 3 frames

With 4 frames

Summary & conclusion

• 3 frames: Optimal performs best (9 < LRU 12 < FIFO 15).
• 4 frames: LRU and Optimal tie at 8 faults, both better than FIFO (10).
• Overall: Optimal is the theoretical best; LRU is the best practical algorithm; FIFO is the worst — it is the only one that can suffer Belady's anomaly.

Coalescing

The act of merging physically adjacent free blocks (holes) into one larger hole. When a block is freed, the allocator checks whether its left and/or right neighbours are free; if so, they are combined into a single bigger free block instead of remaining as tiny useless fragments. It reduces external fragmentation without moving any data (used in dynamic partitioning and malloc-style allocators).

Compaction

The act of shuffling all allocated processes to one end of memory so that all free space is collected into one large contiguous block. It requires dynamic relocation (addresses bound at execution time) and is expensive — large data movement and CPU time — but completely removes external fragmentation. Best when coalescing is not enough; impossible with static binding. (Coalescing = merge adjacent holes in place; compaction = physically move processes.)

Paging hardware with TLB

Every memory access needs a page-table lookup: without help, one logical access = two memory accesses (page table + data) — doubling effective time. The Translation Look-aside Buffer (TLB) is a small, fast associative cache of recent page→frame entries:

1. CPU issues (p, d) → the page number is searched in the TLB in parallel.
2. TLB hit: frame number is available immediately — the page-table walk is skipped; physical address formed in one memory access.
3. TLB miss: the page table in RAM is consulted, the translation is loaded into the TLB (replacing an old entry — LRU/round-robin), then the access proceeds.

Effective access time = h·(TLB-time + memory) + (1−h)·(TLB-time + memory + page-table-access). With hit ratio h = 0.90–0.99 (thanks to locality), EAT ≈ 1.1–1.2 memory accesses instead of 2 — a huge gain. Some TLBs also cache the ASID (address-space identifier) to avoid flushing on context switch.

A file is a named collection of related information recorded on secondary storage — the smallest unit of logical storage; anything can be put in one (program, document, image, data). Files are mapped by the OS onto physical devices and are managed in directories.

File attributes

• Name — the symbolic name kept in the directory (human-readable).
• Identifier (inode number) — unique internal tag that names the file within the file system.
• Type — text, binary, executable, etc. (needed by systems that support different file types).
• Location — pointer(s) to the device and to the disk blocks where the file's data resides.
• Size — current size of the file (bytes/words/blocks); may also include a maximum allowed size.
• Protection — access-control information: who (owner, group, others) may read / write / execute.
• Time, date & user identification — creation, last modification and last use times; owner/user id — used for protection, security and monitoring.

All these attributes (except the name, which lives in the directory) are kept in the file control block / inode.

1. Sequential access — information is processed in order, record by record (read-next / write-next, with a reset-to-start option); a file pointer moves automatically. Simplest, matches tape/line-printer model; used by editors and compilers reading source files.
2. Direct (relative / random) access — a file is a numbered sequence of blocks; the program may read/write block n directly (seek(n) then read) with no ordering. Ideal for databases and immediate access to large amounts of information.
3. Indexed access — built on top of direct access: an index (like a card catalogue) holds pointers to blocks containing records keyed by an attribute. Search the small index first, then access the block directly; multi-level indexes handle very large files (e.g., ISAM).
4. Memory-mapped access — the file is mapped into a process's virtual address space; ordinary memory instructions read/write it (modern convenience method).

Boot Control Block (per volume)

Contains everything needed to boot an operating system from that volume. If the volume holds a bootable OS, it holds the bootstrap loader's location — in UNIX it is the boot block; in NTFS it is the boot sector. At power-on, firmware loads the code from here, which then loads the full OS.

File Control Block — FCB (per file)

Contains all the metadata of a single file: permissions, ownership, file size, dates of creation/modification/access, and the locations of the file's data blocks on disk. The directory entry typically holds only name + FCB number. In UNIX it is the inode (index node); in NTFS it is stored inside the master file table (MFT).

1. Contiguous allocation — each file occupies consecutive disk blocks; the directory stores (start block, length). + Excellent sequential & direct access, few seeks. − External fragmentation, hard to grow a file, must declare size in advance.
2. Linked allocation — each block holds data + a pointer to the next block; directory stores first & last block. + No external fragmentation, file grows freely. − Direct access is slow (must chase pointers), pointers consume space, one lost pointer breaks the chain. Variant: FAT (File Allocation Table) — all next-pointers collected into one table at volume start, cached in memory.
3. Indexed allocation — all of a file's block pointers are gathered in one index block; the directory points to the index block. + Direct access without external fragmentation. − Index block overhead; large files need linked/multilevel indexes (UNIX inode: 12 direct pointers + single, double and triple indirect blocks).

Free-space management is how the file system keeps track of which disk blocks are free so they can be granted to new files and reclaimed on deletion.

1. Bit vector (bitmap) — one bit per block: 1 = free (or vice-versa). Easy to find contiguous runs (count zero-bits); but for a 1 TB disk with 4 KB blocks the bitmap itself is ~32 MB and must be kept partly in memory. Optimisations: bit volumes, grouping free regions with start/count pairs.
2. Linked list — a chain through all free blocks: each free block stores the number of the next free one. No space waste, but traversal is I/O-costly and finding contiguous runs is hard.
3. Grouping — the first free block holds the addresses of n other free blocks (the last of which also holds more addresses) — addresses become reachable quickly.
4. Counting — exploits contiguity: keep (first-free-block, count-of-contiguous-free-blocks) triples in a list; ideal after contiguous allocation.
5. Space maps / FAT-as-free-list — modern file systems (ZFS) store per-metasmide free/run info; FAT doubles as allocation and free-space structure.

A directory is a special file containing symbolic name → file metadata (FCB) mappings. The directory structure is the way directories and files are organised and related across the volume (single-level, two-level, tree, acyclic graph).

Why required:

• Organisation & fast search — thousands of files must be found by name efficiently; grouping related files (per project/user/topic) makes lookup, listing and management easy.
• Unique naming — lets different users use the same file name without conflict (two-level and beyond).
• Grouping & sharing — related files can be shared, moved or protected as one unit (subdirectories, links, per-directory permissions).
• Provides the basis of path names (absolute/relative) used by every command and open() call.

1. Single-level directory — one directory holds all files of all users. Simple, but name conflicts between users and no grouping — searching gets harder as files grow.
2. Two-level directory — a Master File Directory (MFD) points to one User File Directory (UFD) per user; each UFD lists only that user's files. Solves name clashes (same name in different UFDs) and speeds search; but still no grouping within a user's files, and sharing is awkward.
3. Tree-structured directory — directories may contain subdirectories recursively, forming a tree with a root. Supports absolute and relative path names, a current working directory, and natural grouping; files may not be shared across branches. Deletion: files = free space; empty dirs removed; recursive removal for non-empty ones.
4. Acyclic-graph directory — allows shared subdirectories/files while forbidding cycles: the same file/subdirectory appears in two places via a link. Sharing is cheap and natural; but deletion becomes tricky (dangling links) — solved with reference counts (UNIX: hard links + inode count) or by deleting only the link (symbolic links point by path).

Directory implementation is the choice of data structure used to store the directory entries (name → FCB mappings) in memory and on disk — it directly decides how fast files can be located, created and deleted.

A common compromise: a sorted linear list for correctness/ordering, with a hash table maintained as an index for fast lookup.

I/O management is the part of the operating system that controls and coordinates all input/output operations between the computer and its external devices (keyboard, mouse, monitor, disks, SSDs, network cards, printers, USB devices). It hides device-specific details behind a uniform interface: user program → system call → device driver → device controller → device.

Why is it required?

• Device diversity — hundreds of very different devices need a common, portable interface for programs.
• Preventing conflicts — without coordination, programs would clash while accessing the same devices.
• Speed mismatch — devices are far slower than CPU/RAM; buffering, caching and spooling are needed so the CPU is not wasted waiting.
• Efficiency & sharing — devices must be allocated fairly, shared among processes and kept busy (else devices stay idle and transfers become slow).
• Error handling & protection — device faults must be detected, reported and isolated from user programs; user programs must not bypass the OS to touch hardware.

1. Device control via drivers — device-driver modules encapsulate device-specific code; the OS issues commands to device controllers (via registers) and interprets status.
2. Device sharing & allocation — grants devices to processes, queues competing requests, and makes exclusive devices (printer) shareable via spooling.
3. Buffering — holds data temporarily in memory between transfers to smooth speed differences and size mismatches (single/double/circular buffer).
4. Caching — keeps copies of frequently used blocks (disk cache) so repeated accesses avoid device I/O.
5. Scheduling I/O requests — orders the queue of pending requests for fairness and throughput (e.g., disk scheduling: SSTF, SCAN).
6. Error handling — detects, retries and reports device errors to applications in a consistent way.
7. Interrupt handling & polling — manages the two ways devices signal completion; services interrupt handlers quickly.
8. Protection & abstraction — user processes cannot command devices directly (mode bit); the OS exposes only named files/sockets via system calls (device independence).

I/O hardware consists of the physical devices plus the pieces that connect them to the CPU:

• Devices — the actual hardware: keyboard, monitor, printer, SSD, network card…
• Device controllers (adapters) — electronic modules between device and system: each has registers (data-in, data-out, status, control) and possibly its own processor/memory; they translate serial device signals into the computer's bus protocol. (The software module that operates it is the device driver.)
• I/O ports & buses — connection points and shared communication channels (PCIe, USB, SATA, SCSI) that carry address, data and control lines.
• CPU + memory bus — executes drivers, processes interrupts; the DMA module also sits here for block transfers.

I/O devices are the pieces of hardware used by humans or other systems to communicate with a computer — input (keyboard, mouse), output (monitor, printer) or both (modem, network card, touch screen).

Categories

1. Human-readable devices — communicate with the user: keyboards, mouse, monitors, printers, touchscreens.
2. Machine-readable devices — communicate with electronic equipment: disk drives, tape drives, sensors, controllers, actuators, robotics devices.
3. Communication devices — communicate with remote devices: network interface cards (NICs), modems, routers, serial lines.

By data transfer behaviour:

• Block devices — store information in fixed-size, individually addressable blocks (disk, SSD, USB drive); support seeking; typically use DMA.
• Character (stream) devices — deliver/receive a byte stream with no block structure (keyboard, serial port, printer, network).
• Network devices — have their own interface family: sockets with select/read/write, packet-based rather than block/character.
• Clocks & timers — special devices the OS uses to measure time: the interval timer drives time-sharing quantum expiry, and sleep()/alarm() are implemented on them.
• Blocking vs non-blocking interface — a blocking call (read() with no data) suspends the process until data arrives; a non-blocking call returns immediately (e.g., "no data yet"), useful for polling-style apps; asynchronous I/O notifies completion later via signal/callback.
• Others: input vs output vs storage; synchronous vs asynchronous; speed classes from human-speed to network speed.

Polling: the CPU periodically reads the device's status register in a loop (busy-waiting) until the controller reports "ready/done" — the simplest way to detect I/O completion.

Interrupts: the device controller signals the CPU (hardware interrupt) when it needs attention; the CPU finishes the current instruction, saves state, jumps to the interrupt handler (via the interrupt vector), processes the I/O result and resumes. The CPU does no waiting in between.

DMA (Direct Memory Access) is a technique in which a dedicated DMA controller transfers a whole block of data directly between a device and main memory, without the CPU copying every word. The CPU only sets up the transfer (device address, memory address, count, direction) and is interrupted once, when the entire block finishes.

How it works

1. CPU programs the DMA controller (source, destination, byte count).
2. DMA controller takes the system bus and streams data device ↔ memory, "stealing" bus cycles (cycle stealing).
3. On completion it raises one interrupt; the CPU resumes, never having touched the data.

Why it is required

• Without DMA the CPU would execute one interrupt/copy per byte or word — for a disk block of thousands of bytes this drowns the CPU in I/O work.
• Frees the CPU to run other processes during the whole transfer → better throughput and multitasking.
• Fast, bulk transfers for disks, SSDs, network and graphics controllers at device speed.
• Lower interrupt overhead — one interrupt per block instead of thousands.

Disk scheduling decides the order in which pending disk requests are serviced to minimise seek time (head movement) and maximise throughput.

RAID (Redundant Array of Independent Disks) combines several physical disks into one logical unit to gain reliability (redundancy) and/or performance (parallel access).

Protection — goals and domains

• Protection is the mechanism for controlling which processes may access which resources (objects) and in what ways. Goal: enforce the access policy — ensure objects (files, memory, devices, CPU) are used only as intended, and follow the principle of least privilege (a process gets no more rights than it needs).
• Protection domain — the set of (object, rights) pairs a process may use. Domains are modelled by the access matrix: rows = domains, columns = objects, cells = rights (read / write / execute). A domain switch lets a process change its rights (e.g., user mode → kernel mode).
• Implementation of the matrix: per-object Access Control Lists (ACLs) or per-domain capability lists; UNIX realises domains with user/group IDs — the same file checked against rwx for owner/group/others.

Security problems

• Program threats: Trojan horse (useful-looking program hiding malicious code), virus (attaches to files/programs, replicates on execution), worm (self-replicating over the network), logic/time bomb (fires on a condition/date), buffer overflow (overwriting memory to hijack execution).
• System & network threats: denial of service (DoS) — exhaust a resource so legitimate users are blocked; port scanning, eavesdropping, man-in-the-middle, spoofing.

Authentication & one-time passwords

• Authentication = verifying a user's identity via something you know (password/PIN), something you have (smart card, token), or something you are (biometrics — fingerprint, face, iris).
• Passwords must be stored hashed and salted — never in plain text; long passphrases beat short complex ones.
• One-time passwords (OTP): a password valid for a single login or a few seconds, so a stolen one is useless. Types: counter-based tokens, time-synchronised codes (TOTP apps like Google Authenticator), challenge–response grid cards. They defeat replay attacks.

Threats & threat monitoring

• Threat monitoring: keep audit logs and continuously scan system activity for suspicious behaviour using intrusion detection systems (IDS): anomaly detection (flag deviation from the user's normal profile) and signature/misuse detection (match known attack patterns) — plus antivirus scanners and firewalls filtering traffic between networks.

Encryption

Real systems combine them: TLS/HTTPS uses asymmetric crypto to agree a session key, then symmetric crypto for the traffic; hash functions (SHA-256) add integrity checks/digital signatures. Ciphertext should look random — security rests on the key, never on the secrecy of the algorithm (Kerckhoffs's principle).