Operating System

Seek time is the time taken by the disk arm to move the read/write head to the cylinder (track) containing the required sector.

Rotational delay (latency) is the additional time spent waiting for the required sector to rotate under the head once the head is on the correct cylinder; on average it is half a rotation.

Disk scheduling mainly tries to reduce total seek time.

Given: 100 cylinders (0 to 99), head at 43 (previous request at 25, so the head is moving towards higher cylinders). Queue: 86, 70, 13, 74, 48, 9, 22, 50, 30.

(a) FCFS (serve in arrival order): 43 → 86 → 70 → 13 → 74 → 48 → 9 → 22 → 50 → 30

$43+16+57+61+26+39+13+28+20 = 303 \text{ cylinders}$

(86$-$43 = 43, 86$-$70 = 16, 70$-$13 = 57, 74$-$13 = 61, 74$-$48 = 26, 48$-$9 = 39, 22$-$9 = 13, 50$-$22 = 28, 50$-$30 = 20; the sum is $43+16+57+61+26+39+13+28+20 = 303$.)

(b) SSTF (nearest request first): 43 → 48 → 50 → 70 → 74 → 86 → 30 → 22 → 13 → 9

$5+2+20+4+12+56+8+9+4 = 120 \text{ cylinders}$

(c) SCAN (move up to the last cylinder 99, then reverse): 43 → 48 → 50 → 70 → 74 → 86 → 99 → 30 → 22 → 13 → 9

$(99-43) + (99-9) = 56 + 90 = 146 \text{ cylinders}$

(d) LOOK (go only as far as the last request in each direction): 43 → 48 → 50 → 70 → 74 → 86 → 30 → 22 → 13 → 9

$(86-43) + (86-9) = 43 + 77 = 120 \text{ cylinders}$

Disk access time: the total time needed to read or write data on a disk. It is the sum of $\text{Access time} = \text{Seek time} + \text{Rotational latency} + \text{Transfer time}$ where seek time is the time to move the head to the required cylinder, rotational latency is the time for the required sector to rotate under the head, and transfer time is the time to read or write the data.

Disk response time: the time a request spends from its arrival until it is serviced; it is the waiting time in the queue plus the service (access) time. The variance of response time measures how predictable the scheduling is.

Given: head at 43 (previous request at 25, so the head is moving towards higher cylinders), cylinders 0-199, queue: 55, 58, 39, 18, 90, 160, 150, 38, 184.

(a) FCFS: 43 → 55 → 58 → 39 → 18 → 90 → 160 → 150 → 38 → 184

$12 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = \mathbf{465}\ \text{cylinders}$

(b) SSTF (nearest request first): 43 → 39 → 38 → 55 → 58 → 90 → 150 → 160 → 184 → 18

$4 + 1 + 17 + 3 + 32 + 60 + 10 + 24 + 166 = \mathbf{317}\ \text{cylinders}$

(c) C-SCAN (moving towards 199, then jump to 0 and continue upward): 43 → 55 → 58 → 90 → 150 → 160 → 184 → 199 → 0 → 18 → 38 → 39

$(199 - 43) + 199 + 39 = 156 + 199 + 39 = \mathbf{394}\ \text{cylinders}$

(If the return jump from 199 to 0 is not counted as head movement, it is $156 + 39 = 195$.)

(d) LOOK (moving up to the last request 184, then reversing to the lowest request 18): 43 → 55 → 58 → 90 → 150 → 160 → 184 → 39 → 38 → 18

$(184 - 43) + (184 - 18) = 141 + 166 = \mathbf{307}\ \text{cylinders}$

Summary: FCFS 465, SSTF 317, C-SCAN 394, LOOK 307. LOOK gives the least movement here.

Seek time is the time taken by the disk arm to move the read/write head to the cylinder (track) containing the desired sector.

Disk access time is the total time to read or write data on the disk:

$\text{Access time} = \text{seek time} + \text{rotational latency} + \text{transfer time}$

Rotational latency is the time for the desired sector to rotate under the head, and transfer time is the time to actually move the data.

Given: 5000 cylinders (0 to 4999), head at 2150, previous request at 1805 (so the arm is moving towards higher cylinders). Queue: 2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681.

(a) FCFS

Order: 2150 -> 2069 -> 1212 -> 2296 -> 2800 -> 544 -> 1618 -> 356 -> 1523 -> 4965 -> 3681

$81 + 857 + 1084 + 504 + 2256 + 1074 + 1262 + 1167 + 3442 + 1284 = 13011$

Total head movement = 13011 cylinders.

(b) SSTF (nearest request first)

Order: 2150 -> 2069 (81) -> 2296 (227) -> 2800 (504) -> 3681 (881) -> 4965 (1284) -> 1618 (3347) -> 1523 (95) -> 1212 (311) -> 544 (668) -> 356 (188)

$81 + 227 + 504 + 881 + 1284 + 3347 + 95 + 311 + 668 + 188 = 7586$

Total head movement = 7586 cylinders.

(c) C-SCAN (the arm moves up to the last cylinder 4999, then jumps to 0 and continues upward)

Order: 2150 -> 2296 -> 2800 -> 3681 -> 4965 -> 4999 -> 0 -> 356 -> 544 -> 1212 -> 1523 -> 1618 -> 2069

$(4999 - 2150) + (4999 - 0) + (2069 - 0) = 2849 + 4999 + 2069 = 9917$

Total head movement = 9917 cylinders (counting the return jump; it is 4918 if the return jump is not counted).

(d) C-LOOK (the arm goes only as far as the last request in each direction)

Order: 2150 -> 2296 -> 2800 -> 3681 -> 4965 -> 356 -> 544 -> 1212 -> 1523 -> 1618 -> 2069

$(4965 - 2150) + (4965 - 356) + (2069 - 356) = 2815 + 4609 + 1713 = 9137$

Total head movement = 9137 cylinders (counting the return jump).

Summary: SSTF 7586 < C-LOOK 9137 < C-SCAN 9917 < FCFS 13011.

Clock synchronisation

In a distributed system each computer has its own clock, and the clocks drift apart. Clock synchronisation keeps the clocks of different machines consistent, either with real time (physical clocks) or at least in agreement on the order of events (logical clocks). It is needed for things like timestamps in distributed files, transactions, and ordering of messages.

Berkeley algorithm (physical clocks)

It does not assume any machine has the correct time (no UTC server). A time daemon (master) polls all the machines, computes an average, and tells each to adjust.

1. The master asks every machine for its current time.
2. Each machine replies; the master corrects the values for round-trip delay.
3. The master computes the average of all clocks (including its own), ignoring clocks that are obviously faulty.
4. The master tells each machine by how much to adjust (not the new time, so message delay does not matter), which may be a positive or negative amount; clocks are slowed down rather than set back.

Example: master time 3:00, machine A reads 2:50, machine B reads 3:25. Differences from master: 0, $-10$, $+25$. Average difference $= (0-10+25)/3 = +5$ min. Corrected time $= 3{:}05$. Adjustments: master $+5$, A $+15$, B $-20$.

Lamport's logical clock algorithm

It orders events using the "happens-before" relation $\rightarrow$: if $a$ and $b$ are in the same process and $a$ occurs before $b$, then $a\rightarrow b$; if $a$ is sending a message and $b$ its receipt, $a\rightarrow b$. The rules:

1. Each process $P_i$ keeps a counter $C_i$. Before each event, $C_i = C_i + 1$.
2. When $P_i$ sends a message $m$, it includes timestamp $t_m = C_i$.
3. When $P_j$ receives $m$, it sets $C_j = \max(C_j, t_m) + 1$ before delivering it.

This guarantees $a \rightarrow b \Rightarrow C(a) < C(b)$.

Example: $P_1$ and $P_2$ start with $C=0$. $P_1$ has event $a$ ($C_1 = 1$), then sends message $m$ ($C_1 = 2$, $t_m=2$). $P_2$ has event $c$ ($C_2 = 1$), then receives $m$: $C_2 = \max(1,2)+1 = 3$. If $P_2$ had been at $C_2=5$, the receipt would get $\max(5,2)+1=6$. Thus the send always has a smaller timestamp than the receive, even if the physical clocks disagree.

Paging for memory management

Paging is a non-contiguous memory allocation scheme. Physical memory is divided into fixed-size blocks called frames, and the logical (process) address space is divided into blocks of the same size called pages. When a process runs, its pages are loaded into any available frames. A page table (one per process) maps each page number to a frame number.

A logical address generated by the CPU is split into: $\text{Logical address} = (\text{page number } p,\ \text{page offset } d)$ The page number indexes the page table to get the frame number $f$, and the physical address is $f \times \text{page size} + d$.

Advantages: no external fragmentation, easy allocation and swapping, and sharing of pages. Disadvantages: some internal fragmentation in the last page, and page table overhead. A TLB is used to speed up translation.

Paging vs segmentation

Segmentation is a memory-management technique in which the logical address space of a process is divided into variable-sized logical units called segments, such as the main program, functions, data, stack and symbol table. It matches the user's view of a program. Each segment has a name (number) and a length.

Use in memory management

A logical address is a pair $\langle s, d \rangle$: segment number $s$ and offset $d$ within the segment. The OS keeps a segment table for each process; each entry contains

• Base: starting physical address of the segment,
• Limit: length of the segment.

Address translation

1. The segment number $s$ is used as an index into the segment table.
2. The offset $d$ is compared with the limit. If $d \ge \text{limit}$, a trap (addressing error) is raised.
3. Otherwise the physical address is $\text{base} + d$.

$\text{Physical address} = \text{Base}[s] + d, \quad 0 \le d < \text{Limit}[s]$

Example: segment 2 has base 4300 and limit 400. Address $\langle 2, 53 \rangle$ maps to $4300 + 53 = 4353$; address $\langle 2, 500 \rangle$ causes a trap.

Advantages: supports the user's view of memory, protection and sharing of segments (e.g. shared code) are easy, no internal fragmentation, and segments can grow.

Disadvantages: suffers from external fragmentation, needs compaction, and allocation of variable-sized segments is more complex.

An operating system (OS) is system software that acts as an interface between the user and the computer hardware. It manages hardware and software resources and provides common services so that application programs can run conveniently and efficiently. Examples: Windows, Linux, macOS, Android.

Functions of an operating system

1. Process management: creates, schedules and terminates processes, and provides synchronisation, communication and deadlock handling.
2. Memory management: keeps track of which memory is used and by whom, allocates and deallocates memory, and implements virtual memory and paging.
3. File management: creates, deletes, reads, writes and organises files and directories, and controls access to them.
4. Device (I/O) management: controls devices through drivers, with buffering, caching and spooling.
5. Secondary storage management: free-space management, disk allocation and disk scheduling.
6. Protection and security: controls access to resources by users and processes, and provides authentication.
7. User interface: provides a command-line interpreter or GUI for the user.
8. Resource accounting and error handling: records resource usage and detects and handles errors.

A semaphore is an integer variable, accessed only through two atomic operations, used to synchronise processes and protect critical sections:

• wait(S) (P): while (S <= 0) ; S--;
• signal(S) (V): S++;

A binary semaphore takes values 0 or 1 (a mutex); a counting semaphore can take any non-negative value and controls access to a pool of identical resources.

Dining philosophers problem

Five philosophers sit at a round table with one chopstick between each pair of neighbours. A philosopher alternately thinks and eats, and needs both the left and the right chopstick to eat. The problem is to avoid deadlock and starvation.

Each chopstick is represented by a semaphore, chopstick[5], all initialised to 1. Philosopher $i$ does:

do {
    wait(chopstick[i]);            // pick up left
    wait(chopstick[(i+1) % 5]);    // pick up right
    /* eat */
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    /* think */
} while (true);

The semaphore guarantees that no two neighbours use the same chopstick at once (mutual exclusion). However, if all five philosophers pick up their left chopstick together, each waits forever for the right one, which is deadlock. Remedies using semaphores:

• allow at most four philosophers at the table (a counting semaphore initialised to 4);
• pick up both chopsticks only if both are available (inside a critical section guarded by a mutex);
• use an asymmetric order: odd philosophers pick the left first, even philosophers pick the right first.

Deadlock is not possible.

Each of the two processes needs at most 2 resources, and there are 3 resources in total.

For deadlock, every process must hold at least one resource while waiting for another. The worst case is that each process holds $1$ resource and needs one more: this uses 2 resources, so $3-2=1$ resource is still free. One of the waiting processes gets it, now holds its maximum of 2 resources, completes and releases them, after which the other process can get its second resource. So the system never gets stuck.

General rule: with $n$ processes each needing a maximum of $m$ resources, deadlock is impossible if

$R \ge n(m-1)+1$

Here $n=2$, $m=2$, so $n(m-1)+1 = 2(1)+1 = 3 \le R = 3$. The condition is satisfied, therefore the system is deadlock free.

Arrival rate $\lambda = 6$ processes per minute $= \dfrac{6}{60} = 0.1$ process per second.

Average service time $= 8$ s per process.

For a single processor, the fraction of time the CPU is busy (utilisation) is

$\rho = \lambda \times \text{service time} = 0.1 \times 8 = 0.8$

Equivalently, in one minute the CPU must do $6 \times 8 = 48$ s of work out of 60 s, i.e. $48/60 = 0.8$.

So the CPU is busy 80% of the time (and idle 20%). Since $\rho<1$, the system is stable.

Reference string: 0, 9, 0, 1, 8, 1, 8, 7, 8, 7, 1, 2, 8, 2, 7, 8, 2, 3, 8, 3 with 3 frames. (F = page fault; frames shown after each reference.)

(a) FIFO (oldest page in memory is replaced)

Page faults with FIFO $= 8$.

(b) LRU (page unused for the longest time is replaced)

LRU frame contents (least recent first): 0 | 0 9 | 9 0 | 9 0 1 | 0 1 8 (9 out) | 0 8 1 | 0 1 8 | 1 8 7 (0 out) | 1 7 8 | 1 8 7 | 8 7 1 | 7 1 2 (8 out) | 1 2 8 (7 out) | 1 8 2 | 8 2 7 (1 out) | 2 7 8 | 7 8 2 | 8 2 3 (7 out) | 2 3 8 | 2 8 3.

Page faults with LRU $= 9$.

A file is a named collection of related information stored on secondary storage. It is the smallest logical unit of storage visible to the user; it has attributes such as name, type, size, location, protection, owner and timestamps, and operations such as create, open, read, write, seek, delete and truncate.

Access control matrix

Protection is modelled by a matrix with domains (subjects: users or processes) as rows and objects (files, devices, printers, memory segments) as columns. The entry $access(i,j)$ is the set of rights that a process running in domain $D_i$ has on object $O_j$.

How it provides protection:

• When a process in domain $D_i$ attempts operation $M$ on object $O_j$, the OS looks up entry $(i,j)$ and allows the operation only if $M$ is in that set. Anything not listed is denied.
• Users get only the rights they need (least privilege), so one process cannot read or damage objects it was not granted.
• Rights can be changed dynamically through special rights such as copy, owner and control, which allow a domain to pass on, add or remove rights.
• Storing the matrix by column gives an access control list per object; storing it by row gives a capability list per domain.

One-time password (OTP)

A one-time password is a password that is valid for only one login session or transaction and cannot be reused. Each login uses a new password, so a password captured by sniffing, shoulder surfing or a keylogger is useless to an attacker afterwards.

It is generated by:

• a hash chain (the user supplies the previous value in the chain, which the server can check by hashing it);
• a time-based token (TOTP), where the password is derived from a shared secret and the current time and changes every 30 to 60 seconds;
• a counter-based token (HOTP), or an SMS or email code sent to the user's registered device.

It is usually combined with a normal password as two-factor authentication.

Worm versus virus

CPU scheduling criteria

• CPU utilisation: keep the CPU as busy as possible (maximise).
• Throughput: number of processes completed per unit time (maximise).
• Turnaround time: completion time $-$ arrival time (minimise).
• Waiting time: total time spent in the ready queue (minimise).
• Response time: time from submission until the first response is produced (minimise).

Data (burst in sec, lower priority number = higher priority)

Turnaround $=$ completion $-$ arrival; waiting $=$ turnaround $-$ burst.

(a) FCFS

Gantt chart: | A 0–7 | B 7–14 | C 14–16 | D 16–18 |

Average turnaround $= 46.96/4 = 11.74$ s; average waiting $= 28.96/4 = 7.24$ s.

(b) Shortest Remaining Time Next (preemptive)

At 2.01 B (7) arrives but A has 4.99 left, so A continues. At 3.01 C (2) arrives and A has 3.99 left, so C preempts A. D arrives at 3.02 with 2, but C has 1.99 left, so C continues. Then D (2), then A (3.99), then B (7).

Gantt chart: | A 0–3.01 | C 3.01–5.01 | D 5.01–7.01 | A 7.01–11.00 | B 11.00–18.00 |

Average turnaround $= 32.98/4 = 8.25$ s; average waiting $= 14.98/4 = 3.75$ s.

(c) Priority (non-preemptive)

A starts alone at 0 and runs to 7. Then among B (1), D (2), C (4) the order is B, D, C.

Gantt chart: | A 0–7 | B 7–14 | D 14–16 | C 16–18 |

Average turnaround $= 46.96/4 = 11.74$ s; average waiting $= 28.96/4 = 7.24$ s.

(d) Round Robin, quantum = 1 s

Gantt chart: | A 0–3 | B 3–4 | A 4–5 | C 5–6 | D 6–7 | B 7–8 | A 8–9 | C 9–10 | D 10–11 | B 11–12 | A 12–13 | B 13–14 | A 14–15 | B 15–18 |

(B runs alone from 15 to 18 in 1 s slices; A is in the queue ahead of B whenever it arrives together with it.)

Average turnaround $= 45.96/4 = 11.49$ s; average waiting $= 27.96/4 = 6.99$ s.

Summary

SRTN gives the smallest average waiting and turnaround time.

An operating system is system software that manages the hardware and software resources of a computer and provides a convenient interface between the user and the hardware.

As a resource manager

A computer has resources such as CPU, memory, disks, I/O devices and files. Many programs and users compete for them. The OS acts as a manager: it keeps track of who is using which resource, grants requests, resolves conflicting requests, and shares them fairly, safely and efficiently. For example, it schedules the CPU among processes, allocates memory to each, and queues print jobs. Sharing is done in time (CPU, printer: one program at a time, in turn) and in space (memory, disk: each program gets a part).

As an extended machine (virtual machine)

Raw hardware is difficult to program: the programmer would have to handle disk controller commands, interrupts, and registers. The OS hides these details and presents a simpler, cleaner and more powerful abstraction. For instance, instead of dealing with disk blocks, the programmer uses files with open, read, write and close. In this way the OS turns the bare machine into an "extended machine" that is much easier to use than the hardware itself, and the same interface works on different hardware.

Kernel

The kernel is the core part of the operating system that is always resident in memory and runs in privileged (kernel) mode. It directly interacts with hardware and provides basic services to all other parts of the system and to applications through system calls.

Role of the kernel

• Process management: creation, scheduling and termination of processes, context switching.
• Memory management: allocation, protection and virtual memory.
• Device management through device drivers and interrupt handling.
• File system management.
• Inter-process communication and synchronisation.
• Security and protection, and the system call interface between user programs and hardware.

Monolithic kernel versus microkernel

Disk of cylinders 0 to 200, head at 50 (previous at 35, so moving upward). Queue: 60, 190, 40, 125, 15, 150. Time per cylinder $= 6$ ms.

(a) FCFS: 50 → 60 → 190 → 40 → 125 → 15 → 150

$10 + 130 + 150 + 85 + 110 + 135 = 620 \text{ cylinders}$

$\text{Seek time} = 620 \times 6 = 3720 \text{ ms}$

(b) SCAN: the arm moves up serving 60, 125, 150, 190, goes on to the end (cylinder 200), then reverses and serves 40, 15.

50 → 60 → 125 → 150 → 190 → 200 → 40 → 15

$(200-50) + (200-15) = 150 + 185 = 335 \text{ cylinders}$

$\text{Seek time} = 335 \times 6 = 2010 \text{ ms}$

File: a named collection of related information recorded on secondary storage, the smallest unit of logical storage a user can write. It has attributes such as name, type, size, location, owner, protection and timestamps.

Directory: a special file that contains information about other files (name, type, location, size, etc.). It maps file names to the files themselves and organises the file system. Structures include single-level, two-level, tree-structured and acyclic-graph directories.

Access Control List (ACL)

An ACL is a list attached to each object (file or directory) that specifies which users or groups may perform which operations on it. Example for file report.doc:

When a user requests access, the OS scans the list for the user's entry and grants the access only if the right is present. Advantages: easy to see who can access a given object and to revoke access to it. Disadvantage: lists may be long, and finding all the rights of one user is difficult. UNIX owner/group/other permission bits are a short form of ACL.

Access Control Matrix (ACM)

The ACM is a two-dimensional table with domains (users/processes) as rows and objects as columns; entry $(i,j)$ gives the operations domain $i$ may perform on object $j$.

An ACL is the matrix stored column by column (per object); a capability list is the matrix stored row by row (per domain). The matrix is usually sparse, so it is not stored as a whole.

Biometric password

Biometric authentication identifies a user by a physical or behavioural characteristic that is unique to that person rather than by something they remember. Examples: fingerprint, iris or retina pattern, face, voice, hand geometry, signature or keystroke dynamics. A sensor captures the trait, converts it into a template, and compares it with the template stored at enrolment. Advantages: it cannot be forgotten or easily shared and is hard to forge. Disadvantages: costly hardware, false accept/false reject errors, and a biometric cannot be changed if compromised.

System threats

• Virus: code attached to a program that replicates when the host runs, and may damage files.
• Worm: a standalone program that replicates itself across a network, consuming resources (e.g. Morris worm).
• Trojan horse: a program that looks useful but performs hidden malicious actions, such as stealing data.
• Trap door (back door): a hidden entry point deliberately left in a program to bypass normal security.
• Logic bomb: code that triggers a harmful action when a certain condition occurs.
• Stack and buffer overflow: an attacker overwrites memory beyond a buffer to run malicious code.
• Denial of service (DoS/DDoS): flooding a system with requests so that legitimate users cannot use it.
• Port scanning, spyware, ransomware and phishing: probing for open services, secretly collecting information, encrypting data for ransom, and tricking users into revealing credentials.

A distributed operating system manages a collection of independent, networked computers and makes them appear to users as a single coherent system.

Why it is more applicable than a centralised operating system

Major goals

1. Resource sharing: hardware, software and data are available to users across the network.
2. Transparency: hiding the distribution from users: access, location, migration, replication, concurrency, failure and performance transparency.
3. Reliability and fault tolerance: the system keeps working despite failure of some components, using replication.
4. Performance and scalability: load balancing and parallel processing; the system should keep performing as users and nodes increase.
5. Openness: standard interfaces and protocols so that heterogeneous systems can interoperate and be extended.
6. Flexibility and security: support for different services and protection of data across machines.

(a) Producer-consumer problem

Also called the bounded-buffer problem. A producer process generates items and puts them in a shared buffer of size $N$; a consumer removes items from it. Requirements: the producer must wait when the buffer is full, the consumer must wait when it is empty, and access to the buffer must be mutually exclusive. A semaphore solution:

semaphore mutex = 1, empty = N, full = 0;

producer() {                 consumer() {
  while (true) {               while (true) {
    item = produce();            wait(full);
    wait(empty);                 wait(mutex);
    wait(mutex);                 item = remove_from_buffer();
    insert(item);                signal(mutex);
    signal(mutex);               signal(empty);
    signal(full);                consume(item);
  }                            }
}                            }

empty counts free slots, full counts filled slots, and mutex protects the buffer. Without proper synchronisation a race condition occurs on the shared buffer.

(b) Coalescing and compaction

Both deal with external fragmentation in variable-partition memory management.

• Coalescing: when a process leaves, its freed partition is merged with adjacent free holes to form one larger hole, so a larger process can later be placed.
• Compaction: the OS shuffles the allocated partitions towards one end of memory so that all the small scattered free holes combine into one big contiguous block. It is costly (processes must be relocated, and it requires dynamic relocation at execution time).

(c) Ubuntu

Ubuntu is a free and open-source Linux distribution based on Debian, developed by Canonical Ltd. It comes in desktop, server and cloud editions, uses the GNOME desktop by default, and the APT package manager (apt, .deb packages) for installing software. New releases come every six months, with long-term-support (LTS) releases every two years. It is popular for its ease of use, security and strong community support.

Page fault: it occurs when a process references a page that is not present in main memory. The hardware traps to the OS, which finds the page on disk, loads it into a free frame (replacing a page if necessary), updates the page table and restarts the instruction.

Thrashing: a condition in which a process (or the whole system) spends more time swapping pages in and out than executing, because it does not have enough frames to hold its working set. The page-fault rate becomes very high, CPU utilisation falls, and the OS may wrongly admit more processes, worsening it. It is controlled by the working-set model, page-fault-frequency control, or reducing the degree of multiprogramming.

Reference string: 1, 3, 5, 1, 7, 1, 5, 5, 1, 4, 2, 7, 6, 3, 4, 1 with 3 frames (F = fault).

(a) FIFO

FIFO page faults $= 12$.

(b) LRU

LRU page faults $= 11$.

(c) Optimal (replace the page not used for the longest time in the future)

Optimal page faults $= 9$.

Deadlock: a situation in which a set of processes is permanently blocked because each process holds a resource and waits for another resource held by some other process in the set. None of them can proceed, so none ever releases its resource.

Necessary conditions (Coffman conditions)

All four must hold together for a resource deadlock:

1. Mutual exclusion: at least one resource can be used by only one process at a time.
2. Hold and wait: a process holding at least one resource is waiting to acquire more resources held by others.
3. No preemption: a resource cannot be forcibly taken from a process; it is released only voluntarily.
4. Circular wait: a cycle of processes exists, $P_0 \to P_1 \to \dots \to P_n \to P_0$, where each waits for a resource held by the next.

Deadlock handling methods

1. Ignore the problem (ostrich algorithm). Assume deadlocks are rare and do nothing; the user restarts the system. Used by UNIX and Windows because prevention is expensive.

2. Deadlock prevention. Ensure at least one of the four conditions can never hold.

• Mutual exclusion: make resources sharable (e.g. spooling), not always possible.
• Hold and wait: a process must request all its resources at the start, or release all before requesting new ones (low utilisation, starvation).
• No preemption: if a request cannot be granted, the process releases what it holds, or its resources are preempted.
• Circular wait: impose a total ordering on resource types and require requests in increasing order.

3. Deadlock avoidance. The OS has advance information about the maximum needs of processes and grants a request only if the system stays in a safe state (there is an order in which all processes can finish). The Banker's algorithm uses Available, Max, Allocation and Need = Max $-$ Allocation; a request is granted only if it leads to a safe state, found by a safety algorithm. For single-instance resources a resource-allocation graph with claim edges can be used.

4. Deadlock detection and recovery. Allow deadlock to occur, detect it, then recover.

• Detection: for single instances, look for a cycle in a wait-for graph; for multiple instances, use a detection algorithm similar to the Banker's algorithm.
• Recovery: terminate all deadlocked processes or one at a time until the cycle breaks; or preempt resources from processes (select a victim, roll back, avoid starvation).

An operating system is system software that manages the hardware and software resources of a computer and acts as an interface between the user and the hardware. It handles process, memory, file and device management and provides security.

Batch operating system: similar jobs are collected into a batch and run one after another without user interaction. The CPU often sits idle during I/O, response time is long, and the user cannot interact or debug the program while it runs.

Multitasking operating system: several tasks are kept in memory and the CPU switches rapidly among them (time sharing), so each user or program gets a small slice of CPU time and seems to run simultaneously.

Is multitasking better than batch? Yes, for interactive and general use:

Justification: multitasking gives users quick response, keeps the CPU and devices busy, and lets many programs run at once. Batch systems are still adequate for large non-interactive jobs such as payroll or billing processing, where no interaction is needed and simplicity matters, but for most applications multitasking is the better choice.

Role of the scheduler

The scheduler is the part of the OS that decides which process (or job) is given a resource, mainly the CPU and memory, and when. Its role is to keep the CPU busy, share it fairly among processes, maximise throughput and minimise waiting and response times. There are three kinds:

• Long-term (job) scheduler: chooses which jobs from the job pool on disk are admitted to the ready queue in memory.
• Short-term (CPU) scheduler: chooses which ready process gets the CPU next.
• Medium-term scheduler: swaps processes out of and into memory to adjust the degree of multiprogramming.

Short-term versus long-term scheduler

Race condition: a situation in which two or more processes access and manipulate shared data concurrently, and the final result depends on the particular order in which their instructions are interleaved. For example, if two processes both execute counter++ (load, add, store) at the same time, one update can be lost. It is prevented by ensuring mutual exclusion on the critical section.

Semaphore solution for "S2 only after S1"

Use a semaphore synch initialised to 0.

semaphore synch = 0;

P1:                 P2:
  S1;                 wait(synch);
  signal(synch);      S2;

Working: if P2 reaches wait(synch) first, the value is 0, so P2 blocks. After P1 finishes S1 it executes signal(synch), making the value 1 and waking P2, which then executes S2. If P1 runs first, signal raises the value to 1, so P2's wait passes at once. Either way S2 executes only after S1 has completed.

CPU scheduling criteria

• CPU utilisation: keep the CPU as busy as possible.
• Throughput: number of processes completed per unit time.
• Turnaround time: completion time $-$ arrival time.
• Waiting time: time spent waiting in the ready queue.
• Response time: time from submission to the first response.

Multilevel queue scheduling

The ready queue is divided into separate queues, each with its own algorithm. Here queue 1 (higher priority) uses Round Robin with $q=2$ ms and queue 2 uses FCFS. The CPU serves queue 2 only when queue 1 is empty.

The process table is not reproduced in the question, so the method is shown with a typical set, all arriving at $t=0$:

Queue 1 under RR: P1 0–2, P2 2–4, P1 4–6, P2 6–7 (done), P1 7–8 (done). Then queue 2 under FCFS: P3 8–12, P4 12–14.

Gantt chart: | P1 0–2 | P2 2–4 | P1 4–6 | P2 6–7 | P1 7–8 | P3 8–12 | P4 12–14 |

Average turnaround time $= 41/4 = 10.25$ ms; average waiting time $= 27/4 = 6.75$ ms.

For any other table, always run the highest non-empty queue with its own algorithm (a newly arrived queue 1 process preempts queue 2), then use turnaround $=$ completion $-$ arrival and waiting $=$ turnaround $-$ burst.

Thrashing: a condition in which a process spends more time paging (swapping pages in and out of memory) than executing, because it does not have enough frames for the pages it is actively using. Page-fault rate becomes very high and CPU utilisation drops sharply. It is reduced by providing enough frames (working-set model), controlling the page-fault frequency, using local replacement, and lowering the degree of multiprogramming.

Memory management requirements

1. Relocation: the programmer does not know where a program will be loaded, and it may be swapped out and back into a different place. Memory references in the program must therefore be translated to actual physical addresses at run time (using base/relocation registers or paging).
2. Protection: a process must not be able to read or write memory belonging to another process or the OS. Checks must be made at run time by hardware (e.g. base and limit registers), because the address cannot be known in advance.
3. Sharing: several processes should be able to access the same memory area (shared code such as libraries, or shared data) without breaking protection.
4. Logical and physical organisation (also required): programs are organised as modules/segments in logical terms, while memory and disk are linear; the OS must map between them and manage movement between main and secondary memory.

Partitions (in order): 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Processes (in order): 212 KB, 417 KB, 112 KB, 426 KB. Left-over space in a partition is kept as a smaller hole.

First fit (first hole large enough)

• 212 KB goes to 500 KB, leaving 288 KB.
• 417 KB goes to 600 KB, leaving 183 KB.
• 112 KB goes to the 288 KB hole (the first that fits), leaving 176 KB.
• 426 KB: no hole is large enough (largest is 183 KB), so it must wait.

Best fit (smallest hole that is large enough)

• 212 KB goes to 300 KB, leaving 88 KB.
• 417 KB goes to 500 KB, leaving 83 KB.
• 112 KB goes to 200 KB, leaving 88 KB.
• 426 KB goes to 600 KB, leaving 174 KB.

Worst fit (largest hole)

• 212 KB goes to 600 KB, leaving 388 KB.
• 417 KB goes to 500 KB, leaving 83 KB.
• 112 KB goes to the 388 KB hole, leaving 276 KB.
• 426 KB: no hole is large enough (largest is 300 KB), so it must wait.

Conclusion: best fit makes the most efficient use of memory, because it is the only algorithm that places all four processes (first fit and worst fit leave the 426 KB process unplaced).

Programmed I/O is suitable when the CPU has nothing better to do while the device works, and when the transfer is small and simple. In programmed I/O the CPU issues the command and then repeatedly polls the device status register (busy waiting) until the device is ready, then moves each byte or word itself.

It is preferred over interrupt-driven I/O and DMA when:

• The device is very fast, so the polling wait is shorter than the cost of an interrupt and context switch.
• The system is a small dedicated embedded system or microcontroller with a single task, so there is no other process to run while waiting.
• The amount of data is small (a few bytes or control registers), where setting up DMA costs more than the transfer.
• Hardware must be kept cheap and simple, since no interrupt controller or DMA controller is required.
• Very predictable, low-latency response is needed, since there is no interrupt latency.

It is unsuitable for slow devices or bulk transfers because the CPU is wasted in the polling loop.

System threats

System threats are misuse of system services and network connections so that the whole system, not only one program, is attacked. The main types are:

1. Worm: a self-replicating program that uses the network (often a spawn mechanism) to copy itself to other machines without needing a host file. It consumes CPU, memory and bandwidth. Example: the Morris worm.
2. Virus: a code fragment embedded in a legitimate program that replicates when the host is executed, infecting other files. It needs a host and user action to spread.
3. Port scanning: an automated probe of a machine's ports to find open services and vulnerabilities, usually the first step of an attack.
4. Denial of Service (DoS / DDoS): flooding a target with requests so that legitimate users cannot use the service. The distributed form uses many compromised machines.
5. Trojan horse and trap door (related program threats) can be used to start a system-wide attack.

Total resources are not given, but they are not needed. Available (A, B, C, D) = (1, 5, 2, 0).

(a) Need matrix (Need = Max - Allocation)

(b) Safety algorithm

Work = (1, 5, 2, 0).

1. P0: Need (0,0,0,1) is not more than Work (1,5,2,0)? D needs 1 but Work D = 0, so P0 cannot run first. Check P1: (0,7,5,0) needs B = 7 > 5, no. P2: (1,0,0,2) needs D = 2 > 0, no. P3: Need (0,0,2,0) is at most (1,5,2,0), yes. So P3 runs first. Work = (1,5,2,0) + (0,6,3,2) = (1,11,5,2).
2. P0: (0,0,0,1) is at most (1,11,5,2), yes. Work = (1,11,5,2) + (0,0,1,1) = (1,11,6,3).
3. P1: (0,7,5,0) is at most (1,11,6,3), yes. Work = (1,11,6,3) + (1,0,0,0) = (2,11,6,3).
4. P2: (1,0,0,2) is at most (2,11,6,3), yes. Work = (2,11,6,3) + (1,3,5,4) = (3,14,11,7).
5. P4: (0,6,4,2) is at most (3,14,11,7), yes. Work = (3,14,12,11).

All processes finish, so the system is in a safe state with safe sequence $\langle P_3,\ P_0,\ P_1,\ P_2,\ P_4\rangle$

(c) Request of P1 = (0, 4, 2, 0)

• Request is not more than Need of P1 (0,7,5,0): yes.
• Request is not more than Available (1,5,2,0): yes.
• Pretend to allocate: Available = (1,1,0,0); Allocation of P1 = (1,4,2,0); Need of P1 = (0,3,3,0).

Safety check with Work = (1,1,0,0): P0 needs (0,0,0,1), D = 1 > 0, no. P1 needs (0,3,3,0), no. P2 needs (1,0,0,2), no. P3 needs (0,0,2,0), C = 2 > 0, no. P4 needs (0,6,4,2), no. No process can finish, so the new state is unsafe.

Therefore the request of P1 cannot be granted immediately; P1 must wait.

Second chance vs FIFO

FIFO replaces the page that has been in memory longest, without considering whether it is still being used, so a heavily used old page may be removed.

Second chance is a modification of FIFO that uses a reference bit for each page:

• Examine the oldest page (front of the queue).
• If its reference bit is 0, replace it.
• If its reference bit is 1, give it a second chance: clear the bit to 0, move it to the back of the queue (as if newly loaded) and examine the next page.

So frequently used pages stay in memory, which gives fewer page faults than FIFO. If all bits are 1, it degenerates to pure FIFO after one full cycle. It is implemented as a circular queue (clock algorithm).

Belady's anomaly

Normally, increasing the number of page frames reduces page faults. Belady's anomaly is the situation where, for some reference strings, increasing the number of frames increases the number of page faults. It occurs with FIFO (not with stack algorithms such as LRU and Optimal).

Example: reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

3 frames (FIFO)

Page faults = 9.

4 frames (FIFO)

Page faults = 10.

With 3 frames there are 9 faults but with 4 frames there are 10 faults, which demonstrates Belady's anomaly.

Operating System: An operating system (OS) is system software that acts as an intermediary between the user (and application programs) and the computer hardware. It manages hardware resources (CPU, memory, I/O devices, files) and provides a convenient and efficient environment for executing programs. Examples: Windows, Linux, macOS, Android.

Objectives of an operating system

1. Convenience: make the computer easy to use by hiding hardware complexity through a user interface (CLI/GUI) and system calls.
2. Efficiency: use hardware resources (CPU, memory, devices) in an efficient way, keeping the CPU busy and maximising throughput.
3. Resource management: allocate and deallocate processor time, memory, files and I/O devices fairly among competing processes.
4. Ability to evolve: be designed so that new system functions, hardware and fixes can be added without disturbing existing services.
5. Process and memory management: create, schedule and terminate processes; keep track of memory use.
6. Protection and security: prevent one user or process from interfering with another and guard against unauthorised access.
7. Error detection and handling: detect and respond to hardware and software errors to keep the system consistent.
8. Providing an execution environment: loading programs, file system services, networking and communication.

Producer-consumer problem: A producer produces items and places them in a shared bounded buffer of size $n$; a consumer removes items from it. The producer must wait when the buffer is full, the consumer must wait when it is empty, and access to the buffer must be mutually exclusive.

Solution with three semaphores

• mutex = 1: binary semaphore giving mutual exclusion on the buffer.
• empty = n: counts empty slots.
• full = 0: counts filled slots.

semaphore mutex = 1, empty = n, full = 0;

Producer:
do {
    item = produce_item();
    wait(empty);      // wait for an empty slot
    wait(mutex);      // enter critical section
    insert_item(item);
    signal(mutex);    // leave critical section
    signal(full);     // one more full slot
} while (true);

Consumer:
do {
    wait(full);       // wait for a filled slot
    wait(mutex);
    item = remove_item();
    signal(mutex);
    signal(empty);    // one more empty slot
    consume_item(item);
} while (true);

Working: The producer blocks on wait(empty) when the buffer is full, and the consumer blocks on wait(full) when it is empty. mutex ensures only one process manipulates the buffer at a time. The order of wait(empty) before wait(mutex) is important; reversing it can cause deadlock.

Preemptable resource: a resource that can be taken away from a process without causing any harm or loss of work. Examples: CPU, main memory (by swapping out).

Non-preemptable resource: a resource that cannot be taken away from the process holding it without causing the computation to fail. Examples: printer in the middle of printing, CD writer, tape drive, a locked file.

Deadlocks mainly involve non-preemptable resources.

Necessary conditions for deadlock (Coffman conditions)

All four must hold simultaneously:

1. Mutual exclusion: at least one resource is held in a non-sharable mode; only one process may use it at a time.
2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
3. No preemption: resources cannot be forcibly taken from a process; they are released only voluntarily after the task is finished.
4. Circular wait: there exists a set of processes $\{P_0, P_1, \dots, P_n\}$ such that $P_0$ waits for a resource held by $P_1$, $P_1$ for $P_2$, ..., and $P_n$ waits for a resource held by $P_0$.

If any one of these conditions is prevented, deadlock cannot occur.

Partitions (in order): 200K, 600K, 300K, 400K, 700K. Processes: 315K, 527K, 202K, 548K.

First-fit (first partition large enough)

• 315K goes to 600K (leaves 285K).
• 527K goes to 700K (leaves 173K), since 200K, 285K, 300K, 400K are too small.
• 202K goes to 285K (the remainder of the 600K partition; leaves 83K).
• 548K: no partition is large enough (remaining 200K, 83K, 300K, 400K, 173K). 548K must wait.

Best-fit (smallest partition that is large enough)

• 315K goes to 400K (leaves 85K).
• 527K goes to 600K (leaves 73K).
• 202K goes to 300K (leaves 98K).
• 548K goes to 700K (leaves 152K).

All four processes are placed.

Worst-fit (largest partition)

• 315K goes to 700K (leaves 385K).
• 527K goes to 600K (leaves 73K).
• 202K goes to 400K (leaves 198K).
• 548K: the largest remaining partition is 385K, so 548K must wait.

Conclusion: Best-fit makes the most efficient use of memory here, since it is the only algorithm that places all four processes. First-fit and worst-fit both fail to place the 548K process.

System threat: a threat in which operating system services and network connections are misused so that the system or network as a whole is attacked, rather than a single user program. (Program threat: a user program that misuses its legitimate access rights.)

Types of program threats

1. Trojan horse: a program that appears useful or harmless but contains hidden malicious code, which runs with the privileges of the user who runs it (e.g. a fake login program that records passwords). A related form is a spyware or a pop-up carrying program.
2. Trap door (back door): a hole deliberately left in software by its designer or programmer that lets someone bypass normal security checks, such as a special username that always logs in. Hard to detect because it is in the source code.
3. Logic bomb: code that stays dormant until a specific condition occurs (a date, a record deleted from payroll, etc.) and then performs a harmful action.
4. Stack and buffer overflow: a program writes more data into a buffer than it can hold and overwrites adjacent memory, including the return address on the stack, so that the attacker's code is run, often gaining root privileges.
5. Viruses: code fragments embedded in legitimate programs that replicate and spread when the host program is run (macro virus, boot-sector virus, file virus).

Defences: least privilege, code review, input validation, safe languages, antivirus software, and regular patching.

In a distributed system, processes on different machines have no shared memory, so they communicate by message passing over the network. The main methods are:

1. Message passing (send/receive): processes exchange messages using primitives send(destination, message) and receive(source, message). It may be synchronous (blocking) or asynchronous (non-blocking), and direct (named process) or indirect (through mailboxes/ports).
2. Remote Procedure Call (RPC): a process calls a procedure that executes on another machine as if it were local. The client stub marshals the parameters into a message, the network carries it, the server stub unmarshals it, runs the procedure and returns the result. It hides the communication details and gives transparency.
3. Remote Method Invocation (RMI): the object-oriented counterpart of RPC (e.g. Java RMI), where a method of a remote object is invoked through a proxy/stub.
4. Sockets: endpoints identified by an IP address and port number, used for TCP (reliable stream) or UDP (datagram) communication between processes; this is the basic low-level interface.
5. Message-oriented middleware / message queues and publish-subscribe: messages are stored in queues or topics, so sender and receiver need not be active at the same time (loose coupling).
6. Stream-oriented communication: continuous data, such as audio and video, is sent as a stream with timing requirements.
7. Group communication (multicast/broadcast): a message is delivered to a group of processes.

Issues to handle include reliability, ordering, failures, and naming of the remote parties.

(a) Access Control Matrix

An access control matrix is a protection model in which the system's protection state is represented by a two-dimensional matrix. Rows represent domains (users or processes) and columns represent objects (files, devices, programs). The entry $access(i, j)$ is the set of operations that a process executing in domain $D_i$ may invoke on object $O_j$ (read, write, execute, print, etc.).

When a process in a domain attempts an operation on an object, the system looks up the entry and allows it only if the operation is listed. The matrix is usually sparse, so it is stored as access control lists (by column, per object) or capability lists (by row, per domain). Access rights such as copy, owner and control can also be included to allow changes in the matrix.

(b) Process States

A process changes state as it executes. The states are:

1. New: the process is being created.
2. Ready: the process is in memory and waiting to be assigned the CPU.
3. Running: its instructions are being executed on the CPU.
4. Waiting (Blocked): the process waits for some event, such as I/O completion.
5. Terminated: the process has finished execution.

Transitions: New to Ready (admitted); Ready to Running (scheduler dispatch); Running to Ready (interrupt/time slice expired); Running to Waiting (I/O or event wait); Waiting to Ready (I/O or event completion); Running to Terminated (exit).

Fragmentation is the wasting of memory so that it cannot be used effectively.

Examples

Internal: with fixed partitions of 100 KB, a 70 KB process takes a whole partition, so 30 KB inside it is wasted. In paging with 4 KB pages, a 10 KB process takes 3 pages (12 KB) and 2 KB of the last page is wasted.

External: free holes of 20 KB, 30 KB and 15 KB are scattered in memory. A 50 KB process cannot be loaded although 65 KB is free in total, because no single hole is large enough.

Removing fragmentation

• Internal: use variable (dynamic) partitions, allocate memory in smaller units (smaller page size), or use best-fit allocation of partitions so that the size mismatch is small.
• External:
  1. Compaction: move all processes towards one end of memory so that all free holes merge into one large block. It needs dynamic relocation (run-time address binding) and costs time.
  2. Paging: allow the logical address space to be non-contiguous, so no external fragmentation occurs.
  3. Segmentation with paging: combine both to avoid external fragmentation.
  4. Good placement algorithms (best-fit/first-fit) reduce but do not remove it.

Kernel: the kernel is the core part of an operating system. It is loaded first into memory, stays resident, and runs in privileged (kernel) mode. It manages the CPU, memory, devices and system calls, and acts as the bridge between applications and hardware.

Types of kernel

1. Monolithic kernel: the whole operating system (process management, memory management, file system, device drivers) runs as a single large program in kernel space. Communication between parts is by direct function calls, so it is fast, but it is large, harder to maintain, and a bug in any part (e.g. a driver) can crash the whole system. Examples: Linux, traditional UNIX.
2. Microkernel: only the minimum essential functions (basic IPC, low-level memory and CPU scheduling) run in kernel space; other services such as file systems and drivers run as user-space servers. It is more modular, reliable and secure, and easy to extend, but slower due to message-passing overhead. Examples: Mach, QNX, MINIX.
3. Hybrid kernel: a combination of the two, keeping a microkernel-like structure but running more services in kernel space for speed. Examples: Windows NT, macOS (XNU).
4. Exokernel: provides only secure multiplexing of hardware and lets applications manage resources themselves using library operating systems.
5. Nanokernel: an even smaller microkernel that only offers hardware abstraction.

Process Control Block (PCB): the PCB, also called the task control block, is a data structure maintained by the operating system for every process. It holds all the information needed to manage the process and to resume it correctly after a context switch. A process exists in the system as long as its PCB exists.

Information contained in a PCB

1. Process ID (PID): unique identifier of the process (and the parent process ID).
2. Process state: new, ready, running, waiting or terminated.
3. Program counter: address of the next instruction to execute.
4. CPU registers: contents of the accumulator, index registers, stack pointers and general-purpose registers, saved on interrupt or context switch.
5. CPU scheduling information: process priority, pointers to scheduling queues and other scheduling parameters.
6. Memory-management information: base and limit registers, page tables or segment tables.
7. Accounting information: CPU time used, time limits, account numbers, job or process numbers.
8. I/O status information: list of I/O devices allocated to the process, list of open files.

Page fault: an interrupt (trap) generated when a process refers to a page that is not currently in main memory (the page table entry is marked invalid). The OS must bring the page in from the disk before the instruction can continue.

Thrashing: a condition in which a process (or the system) spends more time swapping pages in and out than executing, because it does not have enough frames for its working set. Page fault rate becomes very high, CPU utilisation falls, and the OS may wrongly add more processes, making it worse. It is controlled by the working-set model, page-fault frequency control, or reducing the degree of multiprogramming.

Demand paging with valid-invalid (protection) bit

In demand paging, pages are loaded into memory only when they are needed (lazy swapper). Each page table entry has a valid-invalid bit:

• Valid (1): the page is legal and currently in memory.
• Invalid (0): the page is either not in the process's logical address space, or is valid but currently on the disk.

Steps when a page is referenced:

1. The CPU checks the page table entry. If the bit is valid, the access proceeds.
2. If the bit is invalid, a page-fault trap occurs. The OS checks an internal table: if the reference was illegal, the process is terminated.
3. If it is legal but not in memory, the OS finds a free frame (or selects a victim page by a replacement algorithm).
4. A disk read is scheduled to load the page into the frame.
5. The page table is updated and the bit is set to valid.
6. The instruction that caused the fault is restarted.

Separate protection bits (read, write, execute) in the page table entry also stop illegal access, such as writing to a read-only page, which causes a trap.

Deadlock prevention means designing the system so that at least one of the four necessary conditions for deadlock can never hold.

1. Eliminating mutual exclusion: make resources sharable wherever possible (e.g. read-only files). This is not possible for intrinsically non-sharable resources such as printers, so it is rarely applicable in general.
2. Eliminating hold and wait: either (a) require a process to request all the resources it needs before it begins execution, or (b) allow a process to request resources only when it holds none (it must release all current resources first). Drawbacks: low resource utilisation and possible starvation.
3. Eliminating no preemption: if a process holding resources requests another that cannot be given immediately, all resources it currently holds are preempted (released) and it restarts only when it can get everything it needs. Alternatively, the resources of a waiting process can be taken by another requesting process. Suitable for resources whose state can be saved, such as CPU registers and memory.
4. Eliminating circular wait: impose a total ordering on all resource types, and require each process to request resources in increasing order of number. A process holding resource $R_i$ may request only $R_j$ with $j > i$, so a cycle cannot form. This is the most practical method.

Prevention is safe but can reduce device utilisation and system throughput, so other approaches (avoidance with the Banker's algorithm, or detection and recovery) are also used.

File access methods define how the records of a file are read or written.

1. Sequential access

Information is processed in order, one record after another. A read operation (read_next) reads the next record and advances the file pointer automatically; a write appends at the end. Rewind can reset to the beginning. It is the simplest method and is used by editors, compilers and tapes. Access to a record in the middle needs reading all records before it.

2. Direct (random / relative) access

The file is made of fixed-length records numbered $0, 1, 2, \dots, n$, and any record can be read or written directly in any order using its record number: read(n), write(n). It is based on the disk model of a file. It is suited to databases, airline reservations and large tables where immediate access is needed. Sequential access is easily simulated on top of it: $\text{position} = \text{position} + 1$

3. Indexed access (index sequential)

An index, which contains pointers to the blocks of the file, is built. To find a record, the index is searched (binary search) first and the pointer is used to access the record directly. For very large files, the index itself may be indexed in multiple levels. It is fast for search and is used in databases (ISAM).

Other methods may be built from these, such as hashed access.

Distributed system: a collection of independent computers (nodes) connected by a network that appear to the user as a single coherent system. The nodes have no shared memory or common clock and communicate by passing messages. Goals include resource sharing, scalability, reliability, transparency and performance. Examples: the Web, distributed databases, cloud systems.

Role of clock synchronization

Every node has its own physical clock, and these clocks drift at slightly different rates, so they show different times. Since there is no global clock, clock synchronization is needed to keep the clocks consistent. Its roles are:

• Ordering events: to decide which event happened first (e.g. which update to a file or database came earlier), so consistency is kept.
• Distributed mutual exclusion and coordination: timestamps are used to order requests fairly.
• Transactions and databases: consistent timestamps are required for concurrency control, commit protocols and replication.
• Deadlock detection and debugging: logs from different machines can be merged into a correct timeline.
• Real-time and security applications: authentication tokens and certificates with expiry times, and scheduling tasks, depend on correct time.
• File systems: tools such as make use file modification times across machines.

Methods

• Physical clock synchronization: Cristian's algorithm (a time server is queried and the delay is estimated), Berkeley algorithm (the time daemon averages the clocks of all machines), and NTP (Network Time Protocol).
• Logical clocks: Lamport's logical clocks give a "happened-before" ordering of events without real time; vector clocks capture causality exactly.

Critical section problem

A critical section is a segment of code in which a process accesses shared resources (variables, files, tables) that must not be accessed by more than one process at a time. The critical section problem is to design a protocol so that cooperating processes can use shared data without race conditions. A solution must satisfy:

1. Mutual exclusion: if one process is in its critical section, no other process can be in its critical section.
2. Progress: if no process is in its critical section and some want to enter, only those not in their remainder sections decide who enters next, and this decision cannot be postponed indefinitely.
3. Bounded waiting: there is a limit on the number of times other processes may enter before a waiting process gets its turn.

Each process has the structure: entry section, critical section, exit section, remainder section.

Solution using semaphores

A semaphore is an integer variable accessed only through the atomic operations wait(S) and signal(S):

wait(S):   while (S <= 0) ;  S--;
signal(S): S++;

Use a binary semaphore mutex initialised to 1:

do {
    wait(mutex);        // entry section
       /* critical section */
    signal(mutex);      // exit section
       /* remainder section */
} while (true);

The first process makes mutex = 0 and enters; others block in wait until it calls signal, so mutual exclusion is guaranteed.

Producer-consumer problem using mutex

A producer puts items into a bounded buffer of size $n$, and a consumer takes items out. The buffer is shared, so access needs a mutex, and counting semaphores to track the slots:

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

Producer:
do {
    item = produce_item();
    wait(empty);       // block if buffer is full
    wait(mutex);       // lock buffer
    insert_item(item);
    signal(mutex);     // unlock buffer
    signal(full);
} while (true);

Consumer:
do {
    wait(full);        // block if buffer is empty
    wait(mutex);
    item = remove_item();
    signal(mutex);
    signal(empty);
    consume_item(item);
} while (true);

The mutex ensures only one of the two modifies the buffer at a time, empty stops the producer overfilling, and full stops the consumer reading from an empty buffer.

Belady's anomaly

Normally, giving a process more page frames reduces (or does not increase) the number of page faults. Belady's anomaly is the phenomenon in which, for certain reference strings, increasing the number of frames increases the number of page faults. It occurs with FIFO page replacement, but not with stack algorithms such as LRU and Optimal.

Example: reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 under FIFO gives 9 page faults with 3 frames but 10 page faults with 4 frames.

Reference string (20 references): 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1, with 4 frames.

(a) FIFO

Frames are filled by 7, 2, 3, 1 (4 faults); then replacement is in arrival order: 5 replaces 7, 4 replaces 2, 6 replaces 3, 7 replaces 1, 1 replaces 5, 0 replaces 4, 5 replaces 6, 4 replaces 7, 6 replaces 1, 2 replaces 0, 3 replaces 5, 0 replaces 4, 1 replaces 6.

Faults: 7, 2, 3, 1, 5, 4, 6, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1 are the faulting references = 17 page faults (hits at the second 2, 3 and second 7).

(b) LRU: faults occur on 7, 2, 3, 1 (initial), 5 (replaces 7), 4 (replaces 1), 6 (replaces 2), 7 (replaces 5), 1 (replaces 3), 0 (replaces 4), 5 (replaces 6), 4 (replaces 7), 6 (replaces 1), 2 (replaces 0), 3 (replaces 5), 0 (replaces 4), 1 (replaces 6). Hits: second 2, second 3 and second 7 = 17 page faults.

(c) Optimal (replace the page not used for the longest time in the future):

• 7, 2, 3, 1 cause 4 faults; 2 hits.
• 5 replaces 2 (used last) giving a fault; 3 hits.
• 4 replaces 3 (next used last), fault.
• 6 replaces 4, fault.
• 7, 7, 1 hit.
• 0 replaces 7 (never used again), fault.
• 5 hits; 4 replaces 5 (never used again), fault; 6 hits.
• 2 replaces 4 (never used again), fault.
• 3 replaces 2 (never used again), fault.
• 0, 1 hit.

Total = 4 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 11 page faults.

Summary: FIFO 17, LRU 17, Optimal 11.

Use of DMA controller

A Direct Memory Access (DMA) controller transfers a block of data directly between an I/O device and main memory without the CPU moving each byte. The CPU only gives the controller the device address, memory address and byte count, and then continues other work. The controller transfers the data using the bus (cycle stealing) and sends one interrupt on completion. This frees the CPU, and is used for fast, bulk devices such as disks, network cards and graphics.

Available = (1, 5, 2, 0).

(a) Need matrix (Need = Max - Allocation)

(b) Safe state? Work = (1,5,2,0).

• P3: Need (0,0,2,0) is within Work, so run. Work = (1,11,5,2).
• P0: Need (0,0,0,1) is within Work. Work = (1,11,6,3).
• P1: Need (0,7,5,0) is within Work. Work = (2,11,6,3).
• P2: Need (1,0,0,2) is within Work. Work = (3,14,11,7).
• P4: Need (0,6,4,2) is within Work. Work = (3,14,12,11).

All processes can finish, so the system is in a safe state, with safe sequence $\langle P_3, P_0, P_1, P_2, P_4\rangle$.

(c) P2 requests (3, 4, 0, 2)

Check 1: Request $\le$ Need of P2 (1,0,0,2)? $3 > 1$, so no. The process has asked for more than its declared maximum claim, which is an error.

Check 2: Request $\le$ Available (1,5,2,0)? $3 > 1$ and $2 > 0$, so no.

Therefore the request cannot be granted immediately (it exceeds both the process's maximum claim and the available resources; P2 would have to wait, or the request is rejected as illegal).

Multitasking vs multiprocessing

Microkernel

A microkernel is an operating system design in which the kernel is kept as small as possible and contains only the essential mechanisms:

• basic low-level memory management and address spaces,
• CPU scheduling and thread management,
• inter-process communication (message passing).

All other services, such as the file system, device drivers, networking and the user interface, run as separate user-space server processes. A client talks to a server by sending a message through the microkernel.

Advantages: easy to extend (new services added in user space without modifying the kernel), portable, more reliable and secure (a failing driver does not crash the kernel), easy to maintain. Disadvantage: performance overhead from the frequent message passing and user-kernel mode switches. Examples: Mach, QNX, MINIX; Windows NT and macOS were influenced by it.

Critical section problem

A critical section is the part of a process's code that accesses shared data or resources. The critical section problem is to design a protocol that lets cooperating processes use shared data safely, so that when one process executes in its critical section no other does. A solution must provide mutual exclusion, progress and bounded waiting.

Peterson's solution

Peterson's algorithm is a software solution for two processes, $P_0$ and $P_1$ (with $i$ and $j = 1 - i$), which share two variables:

int turn;            // whose turn it is to enter
boolean flag[2];     // flag[i] = true means Pi wants to enter

Code for process $P_i$:

do {
    flag[i] = true;          // I want to enter
    turn = j;                // but give the other process the chance
    while (flag[j] && turn == j)
        ;                    // busy wait
        /* critical section */
    flag[i] = false;         // exit section
        /* remainder section */
} while (true);

How it achieves mutual exclusion

• $P_i$ enters only if either flag[j] is false (the other does not want to enter) or turn == i.
• If both want to enter, both set their flags true, but turn can hold only one value (the later write wins), so only one process passes the while loop; the other waits.
• When $P_i$ leaves, it sets flag[i] = false, which allows $P_j$ to enter.

So mutual exclusion holds because turn is either $i$ or $j$, never both. Progress holds because a process not interested has its flag false, so it cannot block the other. Bounded waiting holds because a waiting process enters after at most one turn of the other. Note that on modern hardware it may fail without memory barriers because of instruction reordering.

TLB (Translation Lookaside Buffer)

The TLB is a small, very fast, hardware associative (content-addressable) cache that stores recently used page-number to frame-number mappings. It reduces the time needed for address translation in paging.

Problem it solves: in paging, the page table is kept in main memory, so each data access needs two memory accesses (one for the page table entry, one for the data), which halves the speed.

Use in paging

1. The CPU generates a logical address with page number $p$ and offset $d$.
2. The page number is compared with all the TLB entries simultaneously.
3. TLB hit: the frame number is found in the TLB, so the physical address is formed at once with only one memory access for the data.
4. TLB miss: the page table in memory is consulted to get the frame number; then the entry is loaded into the TLB (replacing an old entry by an algorithm such as LRU or random) and the access continues.
5. Some TLBs store an address-space identifier (ASID) with each entry so they need not be flushed at a context switch.

Effective memory access time

With hit ratio $\alpha$, TLB search time $\epsilon$ and memory access time $m$: $EAT = \alpha\,(\epsilon + m) + (1 - \alpha)\,(\epsilon + 2m)$

For example, with $\alpha = 0.8$, $\epsilon = 20$ ns, $m = 100$ ns: $EAT = 0.8(120) + 0.2(220) = 96 + 44 = 140$ ns, compared with 200 ns without a TLB.

A distributed system is a collection of independent computers, connected by a network, that appears to its users as a single coherent system.

Advantages of a distributed system over a centralized system

1. Resource sharing: printers, files, databases and processing power on any node can be used from other nodes.
2. Computation speed-up: a large job can be split into sub-jobs that run concurrently on several machines (load sharing).
3. Reliability and fault tolerance: if one node fails, the others continue to work; a centralized system has a single point of failure.
4. Scalability: capacity grows by adding more machines, instead of replacing one big mainframe.
5. Economy: many cheap microcomputers give a better price/performance ratio than one large machine.
6. Communication and geographic distribution: users in different places can exchange data, mail and files, and data can be kept close to where it is used.
7. Availability: data can be replicated on several sites, so the service stays available.

Remote Procedure Call (RPC)

RPC lets a program call a procedure that runs on another machine as if it were a local call. The call is hidden by two stubs: the client stub and the server stub.

 Client machine                                   Server machine
+-----------------+                          +-----------------+
| Client program  |                          | Server procedure|
|   (1) call  ^(10) return                   |  (6) call ^(7) return
|       v     |                              |      v    |
| Client stub     |--(2) marshal, send------>| Server stub     |
|                 |<-(9) reply message-------|  (8) marshal    |
+-----------------+       (network)          +-----------------+

Functional steps

1. The client program calls the client stub as an ordinary local procedure call.
2. The client stub marshals (packs) the parameters into a message and asks the OS to send it.
3. The client OS sends the message to the remote machine over the network.
4. The server OS receives the message and passes it to the server stub.
5. The server stub unmarshals (unpacks) the parameters.
6. The server stub calls the actual server procedure with those parameters.
7. The procedure executes and returns its result to the server stub.
8. The server stub marshals the result into a reply message and gives it to the server OS.
9. The reply travels over the network to the client OS, which hands it to the client stub.
10. The client stub unmarshals the result and returns it to the client program, which continues as if a local call had been made.

Direct Memory Access (DMA) is a technique in which a special hardware unit, the DMA controller, transfers a block of data directly between an I/O device and main memory without involving the CPU for each byte or word. The CPU only starts the transfer and is interrupted once, when the whole block has been moved.

Why it is needed: in programmed I/O or interrupt-driven I/O, the CPU must handle every byte or word, which wastes CPU time for fast devices such as disks.

Components of a DMA controller: address register (memory address to read/write), word/count register (number of words to transfer), control register (direction, mode), and a data buffer/status register.

Steps of a DMA transfer (e.g. disk read)

1. The CPU programs the DMA controller by writing the memory address, the byte count and the direction (read/write) into its registers, and tells the disk controller to read data.
2. The DMA controller issues a read request to the disk controller.
3. The disk controller reads a block into its internal buffer and the DMA controller requests the bus.
4. The DMA controller writes the data into main memory at the given address (it acts as bus master, using cycle stealing or burst mode).
5. After each transfer the address register is incremented and the count register is decremented; steps 2-4 repeat until the count becomes zero.
6. When the count reaches zero, the DMA controller sends an interrupt to the CPU to signal completion. The CPU then resumes with the data already in memory.

Transfer modes: burst (block) mode, cycle-stealing mode, and transparent mode.

Advantage: the CPU is free to do other work during the transfer, giving high-speed data transfer and better overall performance.

File attributes

A file has a name and, besides its contents, extra information called attributes (metadata) kept in the directory entry or i-node:

1. Name: the human-readable name of the file.
2. Identifier: a unique number (e.g. i-node number) used by the file system.
3. Type: text, executable, binary, directory, etc.
4. Location: pointer to the device and the blocks where the file is stored.
5. Size: current size in bytes or blocks (and maximum allowed size).
6. Protection: access-control information (read, write, execute permissions for owner, group, others).
7. Time, date and user identification: creation, last modification and last access times and the owner. This is useful for protection, security and usage monitoring.
8. Flags: read-only, hidden, system, archive, temporary, lock flags.

Hierarchical directory system

A hierarchical (tree-structured) directory system allows a directory to contain files as well as other sub-directories, so the directories form a tree with a single root directory.

                 /  (root)
        +--------+--------+
      home      etc      usr
     +--+--+            |
   ram  sita          bin
    |
  notes.txt

Features:

• Every file has a unique path name: an absolute path starts from the root (/home/ram/notes.txt), a relative path starts from the current working directory.
• Users can create their own sub-directories to group related files, which gives good organisation.
• Two files with the same name can exist in different directories.
• Searching is efficient since only the relevant directory path is searched.
• Protection can be applied per directory; sharing is possible through links.

Authentication is the process of verifying the identity of a user (or process): "Who are you?" It confirms that the user is really who he or she claims to be, normally at login.

Authorization is the process of deciding what an authenticated user is allowed to do: "What can you access?" It uses access rights such as access-control lists or capabilities. Authentication always comes before authorization.

Authentication systems (methods)

1. Something the user knows: passwords and PINs. The user types a secret. Passwords are stored as one-way hashes (with salt) and compared at login. Weaknesses are guessing, dictionary attacks and sniffing. One-time passwords and challenge-response schemes reduce the risk.
2. Something the user has: physical objects. Smart cards, magnetic-stripe cards, hardware tokens or a mobile phone generating an OTP. The system checks possession of the object.
3. Something the user is: biometrics. Fingerprint, iris, retina, face or voice recognition. They are hard to forge but need special hardware and may give false accepts/rejects.
4. Multi-factor authentication: combines two or more of the above (for example password plus OTP), which is much stronger.
5. Challenge-response and cryptographic authentication: the server sends a random challenge and the client answers using a secret key (e.g. Kerberos tickets, digital certificates and signatures), so the secret is never sent over the network.
6. Location/other based: restricting login to particular terminals, IP addresses or times.

Internal fragmentation is the wasted memory inside an allocated block or partition. It happens when a process is given a block larger than it needs (fixed partitions, paging: the last page is partly empty). The unused part cannot be given to another process.

External fragmentation is the wasted memory between allocated blocks. Enough total free memory exists, but it is split into small non-contiguous holes, so a request for a larger contiguous block cannot be satisfied. It occurs with variable (dynamic) partitions and segmentation.

How external fragmentation occurs in segmentation

In segmentation each segment (code, data, stack) is of different length and must be placed contiguously in memory. When segments are loaded and later removed, holes of different sizes remain. For example, if segments of 100 KB, 50 KB and 200 KB are loaded and the 50 KB segment is removed, a 50 KB hole appears between the others. As more segments come and go, many small holes appear. A new 120 KB segment cannot be placed even if the sum of the holes is greater than 120 KB. This is external fragmentation; it is solved by compaction or by using paging.

Placement of processes

Partitions: P1 = 300, P2 = 600, P3 = 350, P4 = 200, P5 = 750, P6 = 125 (KB). Processes: 115, 500, 358, 200, 375.

First-fit (first hole in memory order that is large enough)

All five processes are placed.

Best-fit (smallest hole that fits)

All processes are placed; best-fit leaves the smallest leftovers.

Worst-fit (largest hole)

With worst-fit the 375 KB process must wait, since the remaining holes are 300, 242, 150, 200, 135 and 125 KB.

Conclusion: first-fit and best-fit place all five processes, while worst-fit fails for 375 KB. Best-fit is best here.

Four necessary (Coffman) conditions for deadlock

1. Mutual exclusion: a resource can be held by only one process at a time.
2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by others.
3. No preemption: a resource cannot be forcibly taken from a process; it is released only voluntarily.
4. Circular wait: there is a closed chain of processes, each waiting for a resource held by the next one.

All four must hold together for a deadlock.

Applying the sequence (a resource is granted if free)

Resource allocation graph (assignment edge: resource -> process; request edge: process -> resource)

   X ------> A ------> Y ------> B ------> Z ------> C
   ^                   ^                              |
   |                   +------------ C ---------------+  (request C -> Y)
   +---------------- request edge C -> X --------------+

Edges:

• Assignment: X -> A, Y -> B, Z -> C
• Request: A -> Y, B -> Z, C -> X, C -> Y

Cycle: A -> Y -> B -> Z -> C -> X -> A.

Is it a deadlock? Yes. Every resource has a single instance and the graph contains the cycle A -> Y -> B -> Z -> C -> X -> A. A waits for B, B waits for C and C waits for A, so none of the three processes can ever proceed.

Recovery from the deadlock

1. Process termination: abort all deadlocked processes, or abort them one at a time (for example C, then check again) until the cycle is broken. Choose the victim by priority, work done so far and resources held.
2. Resource preemption: take a resource from one process and give it to another. For example, preempt Y from B and give it to A; A can finish and release X, then C gets X and so on. The victim is rolled back to a safe state (rollback) and must restart, and starvation is avoided by counting rollbacks in the victim choice.
3. Rollback to a checkpoint: restart a process from an earlier saved state so that it gives up its resources.

A monolithic kernel is an operating system architecture in which the whole OS (process management, memory management, file system, device drivers, networking, IPC) runs as one large program in kernel mode, in a single address space. Components call each other directly through function calls. Examples: traditional UNIX, Linux, MS-DOS.

Difference between monolithic kernel and microkernel

In short, a monolithic kernel gives performance, whereas a microkernel gives modularity, reliability and security at the cost of overhead.

Multithreading is the ability of an operating system or a process to support several threads of execution within a single process. A thread is a lightweight unit of CPU execution with its own program counter, registers and stack, but sharing the code, data and open files of its process. Multithreading improves responsiveness, resource sharing, economy and use of multiprocessors.

Types of threads

1. User-level threads (ULT): managed by a thread library in user space; the kernel does not know about them and sees only one process.
   • Advantages: fast creation and switching (no kernel call), can run on any OS, scheduling can be customised.
   • Disadvantages: if one thread makes a blocking system call, the whole process blocks; cannot use multiple processors at the same time.
2. Kernel-level threads (KLT): created and managed directly by the kernel, which keeps a thread table.
   • Advantages: kernel can schedule threads on different CPUs; a blocked thread does not block the others.
   • Disadvantages: slower creation and switching because of kernel mode switch.
3. Hybrid threads: user threads are mapped onto kernel threads.

Multithreading models: many-to-one (many user threads to one kernel thread), one-to-one (each user thread has a kernel thread, e.g. Linux, Windows) and many-to-many (many user threads multiplexed onto a smaller or equal number of kernel threads, e.g. Solaris).

A process changes its state many times during execution. The main states are:

1. New: the process is being created (PCB being built, resources being allocated).
2. Ready: the process is in main memory, has all the resources it needs except the CPU, and waits in the ready queue for the scheduler to select it.
3. Running: the process's instructions are being executed on the CPU. On a single-processor system only one process is running at a time.
4. Waiting (Blocked): the process cannot continue until some event occurs, such as I/O completion or a signal, so it waits in a device or event queue.
5. Terminated (Exit): the process has finished execution or has been killed; the OS releases its resources.

Some systems add suspended ready and suspended blocked states when a process is swapped out to disk.

Transitions

 New --admit--> Ready --dispatch--> Running --exit--> Terminated
                  ^  <--timeout/preempt--   |
                  |                         | I/O or event wait
                  +-- I/O or event done -- Waiting <--+

• New -> Ready: the scheduler admits the process.
• Ready -> Running: the dispatcher gives the CPU to the process.
• Running -> Ready: time slice expires or a higher-priority process arrives (preemption).
• Running -> Waiting: the process requests I/O or waits for an event.
• Waiting -> Ready: the I/O or event completes.
• Running -> Terminated: the process finishes or is aborted.

Necessary conditions for deadlock (Coffman conditions)

1. Mutual exclusion: at least one resource is non-sharable, so only one process can use it at a time. Others requesting it must wait.
2. Hold and wait: a process holds at least one resource while waiting to obtain more resources that are held by other processes.
3. No preemption: a resource cannot be taken away forcibly from a process; the holder must release it voluntarily after completing its task.
4. Circular wait: there exists a set of processes $\{P_0, P_1, \dots, P_n\}$ such that $P_0$ waits for a resource held by $P_1$, $P_1$ waits for one held by $P_2$, ..., and $P_n$ waits for one held by $P_0$.

Deadlock can occur only if all four conditions hold at the same time.

Deadlock versus starvation

When a page fault occurs and there is no free frame, the OS must choose a page in memory to be removed (the victim) and replaced. A page replacement algorithm decides which page to replace, aiming at the fewest page faults.

1. FIFO (First-In First-Out): replaces the page that has been in memory the longest. Simple, using a queue, but may remove a heavily used page and suffers from Belady's anomaly (more frames may give more faults).

2. Optimal (OPT): replaces the page that will not be used for the longest time in the future. It gives the lowest page-fault rate and is used as a benchmark, but it cannot be implemented because future references are unknown.

3. LRU (Least Recently Used): replaces the page that has not been used for the longest time, based on the idea that the recent past predicts the near future. It is good but needs hardware support (counters or a stack) and is expensive.

4. Second chance (clock): a FIFO variant that checks a reference bit. If the bit is 1, it is cleared and the page is given a second chance; if 0, the page is replaced.

5. NRU (Not Recently Used): pages are grouped by reference (R) and modified (M) bits into four classes, and a page from the lowest non-empty class is removed.

6. LFU/MFU: replace the least (or most) frequently used page, using a count of references.

Example (FIFO, 3 frames): reference string 7, 0, 1, 2, 0, 3, 0, 4 gives faults on 7, 0, 1, 2 (removes 7), 3 (removes 0), 0 (removes 1), 4 (removes 2), that is 7 faults, while OPT gives fewer faults.

Security problems in operating systems

1. Malware: viruses, worms, Trojan horses, spyware and ransomware that damage or steal data.
2. Unauthorised access / weak authentication: guessed or stolen passwords, privilege escalation.
3. Buffer overflow and other software vulnerabilities: attackers inject code by overflowing buffers or exploiting bugs.
4. Denial of service (DoS): flooding the system or network so that legitimate users cannot be served.
5. Trap doors (back doors) and logic bombs: hidden entry points or code that triggers on a condition.
6. Eavesdropping and sniffing, spoofing, man-in-the-middle attacks on network communication.
7. Data theft or modification due to improper access control, and covert channels that leak information.

Role of clock synchronization in a distributed system

A distributed system has no common global clock; every computer has its own physical clock, and these drift apart (clock skew) because of different crystal frequencies. Clock synchronization keeps the clocks of different nodes consistent. Its roles are:

1. Ordering of events: to decide which event happened first across machines (e.g. which update of a replicated record is newer). Logical clocks (Lamport) give a consistent ordering when real time is unavailable.
2. Consistency and coordination: needed for distributed mutual exclusion, deadlock detection, and consistency of replicated data and distributed transactions.
3. Time stamping: time-stamp based concurrency control, authentication tickets (e.g. Kerberos), logs and file modification times (e.g. make) rely on common time.
4. Debugging and auditing: merging logs from different machines needs a common time base.

Algorithms: Cristian's algorithm (a client asks a time server and corrects for the round trip delay), Berkeley algorithm (the master averages the clocks of all machines) and NTP (Network Time Protocol) for the Internet.

Producer-consumer problem

The producer-consumer (bounded-buffer) problem has two processes sharing a fixed-size buffer of $N$ slots. The producer puts items into the buffer and the consumer removes items from it. The problem is to make sure that the producer does not add an item when the buffer is full, the consumer does not remove an item from an empty buffer, and they do not access the buffer at the same time (avoiding race conditions).

Solution using sleep and wakeup

sleep blocks the caller until another process wakes it; wakeup(p) wakes process p. A shared variable count holds the number of items in the buffer.

#define N 100
int count = 0;

void producer() {
    while (1) {
        item = produce_item();
        if (count == N) sleep();          // buffer full
        insert_item(item);
        count = count + 1;
        if (count == 1) wakeup(consumer); // buffer was empty
    }
}

void consumer() {
    while (1) {
        if (count == 0) sleep();          // buffer empty
        item = remove_item();
        count = count - 1;
        if (count == N - 1) wakeup(producer); // buffer was full
        consume_item(item);
    }
}

Problem (lost wakeup race condition): access to count is unprotected. Suppose the buffer is empty and the consumer reads count == 0, but is pre-empted just before calling sleep(). The producer inserts an item, sets count = 1 and sends wakeup to the consumer, which is not yet asleep, so the signal is lost. When the consumer runs again, it sleeps. The producer eventually fills the buffer and sleeps too; both sleep forever (deadlock). The fix would be a wakeup-waiting bit, but it does not generalise.

Solution using semaphores

Three semaphores are used: mutex (initially 1, mutual exclusion on the buffer), empty (initially $N$, number of empty slots), and full (initially 0, number of filled slots).

semaphore mutex = 1, empty = N, full = 0;

void producer() {
    while (1) {
        item = produce_item();
        down(&empty);      // wait for empty slot
        down(&mutex);      // enter critical region
        insert_item(item);
        up(&mutex);        // leave critical region
        up(&full);         // one more filled slot
    }
}

void consumer() {
    while (1) {
        down(&full);       // wait for filled slot
        down(&mutex);
        item = remove_item();
        up(&mutex);
        up(&empty);        // one more empty slot
        consume_item(item);
    }
}

down and up are atomic operations, so no wakeup can be lost.

Comparison