Operating System

Goals of an interactive system. Interactive (time-sharing) systems serve users who wait at a terminal for responses, so scheduling aims at:

• Fast response time: respond to requests quickly (low latency to first output).
• Proportionality: meet users' expectations; short, simple requests should finish quickly.
• Fairness: every process gets a fair share of the CPU, with no starvation.
• Balance: keep all parts of the system (CPU, I/O devices) busy.

Interactive scheduling algorithms: round robin (RR), priority scheduling, multiple (multilevel) queues, multilevel feedback queue, shortest process next, guaranteed scheduling, lottery scheduling and fair-share scheduling.

Process data

(a) Round Robin, quantum = 10.

The ready queue is kept in order of arrival (a process arriving at the same moment as a preemption is queued before the preempted one).

Gantt chart: | A 0-10 | C 10-20 | A 20-26 | B 26-36 | C 36-46 | B 46-56 | C 56-61 | B 61-71 | B 71-78 |

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

$\text{Average turnaround time} = \frac{26 + 66 + 54}{3} = \frac{146}{3} = 48.67$

$\text{Average waiting time} = \frac{10 + 29 + 29}{3} = \frac{68}{3} = 22.67$

(b) Priority scheduling (a smaller number means higher priority; A has the highest priority).

A is the only process at time 0 and starts. It has the highest priority, so it is not preempted when C (priority 3) and B (priority 2) arrive. After A finishes at 16, B (priority 2) runs before C (priority 3).

Gantt chart: | A 0-16 | B 16-53 | C 53-78 |

$\text{Average turnaround time} = \frac{16 + 41 + 71}{3} = \frac{128}{3} = 42.67$

$\text{Average waiting time} = \frac{0 + 4 + 46}{3} = \frac{50}{3} = 16.67$

The preemptive and non-preemptive versions give the same result here.

FIFO page replacement keeps pages in a queue in the order they were loaded and, on a page fault with no free frame, evicts the page that has been in memory longest, ignoring whether it is still being used. A heavily used old page may therefore be removed and immediately faulted back in.

Second Chance is a modification of FIFO that adds a reference bit $R$ to every page.

• The oldest page (head of the queue) is examined.
• If $R = 0$, the page is old and unused, so it is replaced.
• If $R = 1$, the page was used recently: its bit is cleared, it is moved to the tail of the queue as if it had just arrived (given a second chance), and the search continues.
• The hardware sets $R = 1$ whenever the page is referenced.
• If all pages have $R = 1$, the algorithm degenerates to pure FIFO after all bits have been cleared.

So Second Chance evicts the oldest page that has not been referenced recently, rather than simply the oldest page, which gives fewer faults than FIFO. (The clock algorithm is an efficient implementation using a circular list and a moving hand.)

Belady's anomaly. For some page replacement algorithms (notably FIFO), increasing the number of page frames can increase the number of page faults, contrary to the expectation that more memory means fewer faults. Stack algorithms such as LRU and Optimal never show this anomaly.

Example. Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with FIFO.

3 frames:

Faults = 9.

4 frames:

Faults = 10.

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

Objective of disk scheduling. Disk access time is dominated by seek time (moving the head to the required track) and rotational delay. Disk scheduling algorithms order the pending I/O requests so as to minimise total seek time (head movement), and thereby maximise throughput and reduce average response time, while keeping the service fair.

Why SSTF is not practically feasible. Shortest Seek Time First always serves the request nearest to the current head position. It suffers from:

• Starvation: requests far from the head may be postponed indefinitely if new requests keep arriving close to it.
• Unfairness and high variance in response time, which is unacceptable for interactive systems.
• It is not optimal globally and the head tends to stay in one region.
• It needs the pending requests to be searched and the distance to be recalculated at every step (overhead).

Calculation. Tracks 0 to 99, head at 35, request queue: 52, 67, 27, 11, 43, 85, 18, 75, 92, 8. Seek time is measured as the total head movement in tracks. The direction of movement is not given, so assume the head first moves towards higher-numbered tracks.

Sorted requests: 8, 11, 18, 27 (below 35) and 43, 52, 67, 75, 85, 92 (above 35).

SCAN (elevator). The head moves to the end of the disk (track 99), serving requests on the way, then reverses.

Order: 35 → 43 → 52 → 67 → 75 → 85 → 92 → 99 → 27 → 18 → 11 → 8

$\text{Seek} = (99 - 35) + (99 - 8) = 64 + 91 = 155 \text{ tracks}$

LOOK. The head goes only as far as the last request in each direction before reversing.

Order: 35 → 43 → 52 → 67 → 75 → 85 → 92 → 27 → 18 → 11 → 8

$\text{Seek} = (92 - 35) + (92 - 8) = 57 + 84 = 141 \text{ tracks}$

Thus SCAN needs 155 and LOOK needs 141 track movements. (If the head moved towards track 0 first: SCAN $= 35 + 92 = 127$ and LOOK $= (35 - 8) + (92 - 8) = 111$.) LOOK is better since it avoids the unnecessary travel to the disk end.

Two modes of operation.

• User mode: the mode in which ordinary application programs run. The mode bit is 1. Privileged instructions (I/O, memory management registers, halting the CPU) cannot be executed, and the program can access only its own memory.
• Kernel mode (supervisor/system mode): the mode in which the operating system runs. The mode bit is 0. All instructions and all hardware are accessible. A user program enters kernel mode through a system call or interrupt/trap, and returns to user mode afterwards.

The two modes protect the OS and other programs from faulty or malicious user programs.

Operating system structures

1. Monolithic system: the entire OS is one large program running in kernel mode, as a collection of procedures that can call each other freely. Efficient, but hard to maintain and a bug can crash the whole system (early UNIX, MS-DOS style).
2. Layered system: the OS is divided into layers, each built on the one below (layer 0 hardware ... top layer user programs). A layer uses only the services of lower layers. It is easy to debug and verify, but layer definition is difficult and the overhead is higher (THE system).
3. Microkernel: only the minimum functions (IPC, basic scheduling, memory management) stay in the kernel; file systems, drivers and so on run as user-mode servers. It is more reliable, secure and extensible, but message passing makes it slower (Minix, QNX, Mach).
4. Client-server model: a variation in which processes are clients requesting service from server processes via messages.
5. Virtual machine: a virtual machine monitor (hypervisor) runs on the hardware and provides several virtual copies of it, each able to run its own OS (VM/370, VMware).
6. Exokernel and modular/hybrid kernels: exokernels give applications direct resource control; modern systems such as Linux and Windows use loadable modules or a hybrid of monolithic and microkernel designs.

When threads are better than processes.

• When an application has several activities that can run in parallel and share the same data (e.g. a word processor with threads for typing, spell checking and auto-save; a web server handling many requests).
• Cheaper creation and switching: a thread has only its own stack, registers and program counter, so creation and context switch are much faster than for a process, which needs a new address space.
• Shared memory: threads share code, data and open files of their process, so communication needs no IPC mechanism.
• Responsiveness: if one thread blocks on I/O, the others continue.
• Multiprocessor use: threads of one process can run on different CPUs simultaneously.
• Less resource use (memory) than separate processes.

Processes are preferable when isolation and protection between activities is needed, since a faulty thread can corrupt the whole process.

User-level threads. User-level threads are implemented entirely by a thread library in user space; the kernel knows only about the process and is unaware of the threads.

• Each process has its own thread table (program counter, registers, stack, state) maintained by the run-time system.
• Thread operations (create, yield, schedule, destroy) are library procedure calls, not system calls, and so are very fast.
• Scheduling of threads is done by the library, so each process can have its own scheduling algorithm.
• It works on an OS that has no thread support (e.g. POSIX pthreads in user mode, Java green threads).

Advantages: fast creation and switching (no kernel trap), portable across operating systems, custom scheduling per application.

Disadvantages:

• If one thread makes a blocking system call, the entire process blocks, because the kernel sees only one flow of control.
• A page fault in one thread blocks all of them.
• The kernel schedules the process as a single unit, so multiple threads of a process cannot run on multiple CPUs simultaneously.
• There is no pre-emption within a process, unless threads call yield or a clock interrupt is arranged.

Kernel-level threads avoid these problems at the cost of slower operations.

Multiprogramming vs. monoprogramming

CPU utilisation. If a process spends a fraction $p$ of its time waiting for I/O, and $n$ processes are in memory, the probability that all of them are waiting at the same time is $p^n$ (assuming independence). Hence

$\text{CPU utilisation} = 1 - p^n$

Here $p = 0.60$ and $n = 6$:

$p^n = 0.6^6 = 0.046656$

$\text{CPU utilisation} = 1 - 0.046656 = 0.953344 \approx 95.3\%$

For comparison, a single process (monoprogramming) would give only $1 - 0.6 = 40\%$.

Managing free disk space. The file system must keep track of which disk blocks are free. The two main methods are:

1. Bitmap (bit vector): one bit per block (1 = free, 0 = allocated). A disk of $n$ blocks needs an $n$-bit map. It is simple and makes it easy to find contiguous free blocks, but the map must be kept in memory for speed.
2. Linked list of free blocks: the free blocks are chained together.

Other variants are grouping and counting (a list of runs of contiguous blocks).

Linked list approach. Each free block contains the number (pointer) of the next free block; the system keeps just the pointer to the first free block in a fixed location (and in memory). Alternatively, each free block holds a list of many free block numbers, the last entry pointing to another such block (to reduce I/O).

Example: let blocks 2, 5, 6, 9 and 13 be free.

Head -> [2] -> [5] -> [6] -> [9] -> [13] -> NULL

• Allocation: to allocate a block, take the block pointed to by Head (block 2) and set Head to the pointer stored inside it (5). Now the free list is 5 → 6 → 9 → 13.
• Freeing: when block 7 is released, its pointer is set to the current Head and Head is made to point to 7: 7 → 5 → 6 → 9 → 13.

Advantages: wastes no extra space (the list is stored in the free blocks themselves), and only one pointer is needed in memory.

Disadvantages: finding many free blocks (or contiguous ones) requires reading the blocks one by one, which is slow; the list is fragile if a pointer is damaged.

Programmed I/O (polling or busy waiting): the CPU starts the I/O operation and repeatedly checks the device status register until the device is ready, transferring each byte or word itself.

Programmed I/O is suitable when

• the system is simple, dedicated to one task and the CPU has nothing else useful to do (e.g. small embedded systems);
• the device is very fast, or the amount of data is small, so the waiting is very short;
• the cost and complexity of interrupt or DMA hardware must be avoided.

It wastes CPU time when devices are slow, since the CPU is busy for the entire transfer.

I/O using DMA (Direct Memory Access). A DMA controller transfers a block of data between a device and main memory without continuous CPU involvement. The steps are:

1. The CPU programs the DMA controller by writing to its registers: the memory address, the byte count, the direction (read/write) and the device. It then continues with other work.
2. The DMA controller issues a read request to the disk controller (device).
3. The disk controller transfers data into its internal buffer.
4. The DMA controller moves the data to the specified memory address through the bus (cycle stealing, one word at a time), increments the address and decrements the count.
5. This repeats until the count reaches zero.
6. When the whole block has been transferred, the DMA controller sends an interrupt to the CPU, which then handles the completion.

DMA interrupts the CPU once per block rather than once per byte, so CPU overhead is greatly reduced and the CPU is free to execute other processes during the transfer. DMA is used for disks, network cards and other high-speed devices.

Deadlock vs. starvation

Deadlock detection with multiple resources of each type. Let there be $n$ processes $P_1 \ldots P_n$ and $m$ resource classes. The algorithm uses matrices and vectors:

• $E$ = existing resource vector (total of each class)
• $A$ = available resource vector (currently free)
• $C$ = current allocation matrix ($C_{ij}$ = units of resource $j$ held by $P_i$)
• $R$ = request matrix ($R_{ij}$ = units of resource $j$ that $P_i$ still wants)

At all times $\sum_i C_{ij} + A_j = E_j$.

Algorithm (compares vectors element by element):

1. Mark every process as unmarked (initially none is known to be able to finish).
2. Look for an unmarked process $P_i$ whose row of $R$ is $\le A$.
3. If found, add row $i$ of $C$ to $A$ (the process finishes and returns its resources), mark $P_i$, and go back to step 2.
4. If no such process exists, stop. Any process still unmarked is deadlocked; if all are marked, there is no deadlock.

Example: $E = (4, 2, 3, 1)$, $A = (2, 1, 0, 0)$,

$C = \begin{pmatrix} 0&0&1&0 \\ 2&0&0&1 \\ 0&1&2&0 \end{pmatrix}, \quad R = \begin{pmatrix} 2&0&0&1 \\ 1&0&1&0 \\ 2&1&0&0 \end{pmatrix}$

$P_1$ needs $(2,0,0,1) > A$, $P_2$ needs $(1,0,1,0)$ but the third resource is 0, so no; $P_3$ needs $(2,1,0,0) \le (2,1,0,0)$, so $P_3$ runs, and $A = (2,2,2,0)$. Now $P_2$ ($1,0,1,0$) can run, $A = (4,2,2,1)$, then $P_1$ can run. No process is left unmarked, so there is no deadlock.

The algorithm may be run at regular intervals, or whenever CPU utilisation drops. After detection, recovery is by preemption, rollback or killing processes.

Problems with semaphores.

• Hard to use correctly: the programmer must place down (P/wait) and up (V/signal) operations correctly in every process; they are low level and scattered through the program.
• Wrong order gives deadlock. E.g. in the producer-consumer problem, if the producer does down(mutex) before down(empty) and the buffer is full, the producer sleeps holding the mutex, and the consumer can never enter: deadlock.
• Omitting or duplicating operations: forgetting up(mutex) blocks everyone forever; omitting down(mutex) or swapping them (up ... down) breaks mutual exclusion.
• Priority inversion and starvation are possible.
• Difficult to verify and debug, since errors depend on timing and are not reproducible.
• Correctness depends on all programmers following the discipline; there is no compiler support.

Monitors. A monitor, proposed by Hoare and Brinch Hansen, is a high-level synchronisation construct provided by a programming language. It is a collection of procedures, variables and data structures grouped together in a special module or class.

• Mutual exclusion is automatic: only one process can be active inside a monitor at a time. When a process calls a monitor procedure, the compiler-generated code checks whether another process is active in the monitor; if so, the caller is blocked until it leaves.
• Shared data is accessible only through the monitor's procedures (encapsulation).
• Condition variables support waiting inside a monitor: wait(c) blocks the calling process on condition $c$ and releases the monitor so another can enter; signal(c) wakes one process waiting on $c$. Unlike semaphores, a signal with no waiting process is lost.

Producer-consumer sketch:

monitor ProducerConsumer
  condition full, empty;
  integer count = 0;
  procedure insert(item)
    if count == N then wait(full);
    insert_item(item); count++;
    if count == 1 then signal(empty);
  procedure remove()
    if count == 0 then wait(empty);
    item = remove_item(); count--;
    if count == N-1 then signal(full);

Monitors make concurrent programs simpler and safer, but they require language support (Java synchronized, wait/notify, Pascal Concurrent, C# lock).

Why relocation and protection are important.

In multiprogramming, several programs reside in memory simultaneously, and a program is usually compiled assuming it starts at address 0.

• Relocation: a program may be loaded at a different physical address each time (or even moved while running), so the addresses it generates must be translated to its actual memory location. Without relocation, two programs loaded in different places would both use absolute addresses such as 100 and clash, and programs could not be loaded freely wherever space is available.
• Protection: one process must not read or write the memory of another process or of the operating system, whether by accident (a bug) or maliciously. Without protection, a faulty program could crash the whole system or steal data.

Technique: base and limit registers. The hardware has two special registers for each running process:

• Base register: holds the starting physical address of the process's partition.
• Limit register: holds the length of the process's partition (its size).

Every memory address generated by the program (logical address) is handled by the hardware as follows:

$\text{Physical address} = \text{Base} + \text{Logical address}$

and the address is first checked:

$\text{Logical address} < \text{Limit}$

If the logical address is not within the limit, the hardware raises a trap (addressing error) to the OS. Otherwise the base is added dynamically, at run time.

Example: a process is loaded at address 16000 with limit 4000. The instruction JMP 28 becomes a jump to $16000 + 28 = 16028$. An access to logical address 5000 fails since $5000 > 4000$.

Operation: on each context switch the OS loads the base and limit registers of the next process (they are privileged, and can be changed only in kernel mode). This gives both relocation (programs run wherever loaded, and can be moved by changing the base) and protection (cannot address outside the partition). The drawback is an addition and comparison on every memory access. Paging and segmentation are more general techniques.

(a) Linux file system

Linux uses a hierarchical (tree-structured) file system with a single root directory /; all devices and file systems are attached (mounted) into this tree. A Virtual File System (VFS) layer gives applications a uniform interface (open, read, write, close) regardless of the underlying type, so that ext2/ext3/ext4, FAT, NTFS, NFS and others can coexist.

Main features:

• Everything is a file: regular files, directories, devices (/dev), pipes and sockets.
• Standard directories: /bin, /etc, /home, /usr, /var, /tmp, /dev, /proc.
• Inode-based: each file has an inode that stores its metadata (owner, group, permissions, size, timestamps, link count) and pointers to data blocks: 12 direct pointers, plus single, double and triple indirect pointers. File names are stored in directories, which map names to inode numbers; this permits hard links, and symbolic links.
• Permissions: read, write and execute for owner, group and others (e.g. rwxr-xr--).
• ext4 (the usual native file system) adds journaling for crash recovery, extents, large file and volume sizes.
• The file system is divided into a boot block, superblock (global information), inode table/block groups and data blocks.

(b) Resource allocation graph

A resource allocation graph (RAG) is a directed graph used to describe resource allocation and to detect deadlock.

• Vertices: a set of processes $P = \{P_1, \ldots, P_n\}$ drawn as circles, and resource types $R = \{R_1, \ldots, R_m\}$ drawn as rectangles, with dots inside for the number of instances.
• Request edge $P_i \rightarrow R_j$: process $P_i$ is waiting for an instance of $R_j$.
• Assignment edge $R_j \rightarrow P_i$: an instance of $R_j$ is allocated to $P_i$.

Deadlock detection by the graph:

• If the graph has no cycle, there is no deadlock.
• If it has a cycle and each resource has a single instance, a deadlock exists (necessary and sufficient).
• If it has a cycle but resource types have multiple instances, deadlock is possible but not certain (the cycle is necessary but not sufficient).

Example: $P_1$ holds $R_1$ ($R_1 \rightarrow P_1$) and requests $R_2$ ($P_1 \rightarrow R_2$), while $P_2$ holds $R_2$ ($R_2 \rightarrow P_2$) and requests $R_1$ ($P_2 \rightarrow R_1$). The cycle $P_1 \rightarrow R_2 \rightarrow P_2 \rightarrow R_1 \rightarrow P_1$ means $P_1$ and $P_2$ are deadlocked. A claim edge (dashed) is added in the avoidance version of the graph.

Sleep and wakeup. To avoid busy waiting, a process that cannot enter its critical region (or cannot proceed) calls sleep(), which blocks it, and another process later calls wakeup(process) to make it ready again. The classic use is the producer-consumer (bounded buffer) problem.

The problem: lost wakeup (race condition). A wakeup sent to a process that is not yet asleep is lost. The sleep-or-not decision (testing the shared variable count) and the actual sleep are not atomic, so if a context switch happens in between, the signal is lost and both processes may sleep forever (deadlock).

#define N 100
int count = 0;                       /* items in buffer */

void producer(void) {
  int item;
  while (TRUE) {
    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(void) {
  int item;
  while (TRUE) {
    if (count == 0) sleep();         /* buffer empty */
    item = remove_item();
    count = count - 1;
    if (count == N - 1) wakeup(producer);
    consume_item(item);
  }
}

Failing scenario.

1. The buffer is empty (count == 0). The consumer reads count, sees 0, and decides to sleep, but the scheduler switches to the producer just before it executes sleep().
2. The producer inserts an item, sets count = 1, and since count == 1 calls wakeup(consumer). The consumer is not asleep yet, so the wakeup signal is lost.
3. The consumer runs again, continues with its already-made decision, and calls sleep().
4. The producer keeps producing until the buffer is full (count == N) and also sleeps.

Both processes are asleep forever: deadlock.

A wakeup waiting bit (to remember a pending wakeup) only patches this one case and fails with more processes. Also, the access to the shared variable count itself is unprotected, which is another race condition.

Solution. Use a synchronisation primitive which makes the check-and-block atomic: semaphores (down and up store the signal in a counter, so it is never lost), mutexes with condition variables or monitors.

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

producer: down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full);
consumer: down(&full);  down(&mutex); item = remove_item(); up(&mutex); up(&empty);

Why OPT is best but not practical. The Optimal (OPT/OPR) algorithm replaces the page that will not be used for the longest time in the future. It gives the lowest possible page-fault rate for a given number of frames and never suffers from Belady's anomaly, so it is the best. But it requires knowing the future sequence of page references, which the operating system cannot know when a program runs. It is therefore not implementable in a real system; it is used only as a benchmark to compare other algorithms.

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

(a) OPT

Faults: refs 1, 3, 4, 2, 5, 1, 2, 6, 1, 4 give 10 page faults.

(Replacements: 2 replaces 1 (1 is used farthest in future); 5 replaces 2 (2 is next used latest); 1 replaces 5 (5 is never used again); 2 replaces 1; 6 replaces 4; 1 replaces 3 (3 never used again); 4 replaces 1.)

(b) LRU (replace the least recently used page)

Faults: 14 page faults (hits only at the 5th, 8th and 17th references).

(c) Clock (circular list with reference bits; the hand points to the next candidate; a referenced page has its bit cleared and is skipped).

Frames shown as page(bit) in positions 1, 2, 3; hand position after each fault.

Faults: 15 page faults.

Summary

OPT is lowest, as expected; LRU and Clock are practical approximations.

Safe, unsafe and deadlocked states. A state is safe if there is an ordering of the processes (a safe sequence) in which every process can obtain its maximum remaining demand and finish, even if all request their maximum. An unsafe state has no such sequence. A deadlocked state is one in which a set of processes is actually blocked waiting for each other and none can ever proceed.

An unsafe state is not itself a deadlock; it only means deadlock may occur, depending on the order of future requests (some processes might release resources early or not request their maximum). A deadlocked state is always unsafe, but an unsafe state need not yet be deadlocked. The banker's algorithm grants a request only if the resulting state is safe.

Given. Total resources = Has (2+1+2+3 = 8) + Free (2) = 10.

Free = 2.

(i) D requests 1 resource. Pretend to grant it: D has 4, need 4, Free = 1.

With Free = 1, only C (need 1) can finish. After C finishes, Free = 1 + 2 = 3. Now A needs 4, B needs 4, D needs 4, and none can be satisfied with 3. No safe sequence exists, so the new state is unsafe. The request is denied (D must wait).

(ii) A requests 1 resource. Pretend to grant it: A has 3, need 3, Free = 1.

1. C needs 1 $\le$ Free 1: C runs to completion, Free = 1 + 2 = 3.
2. A needs 3 $\le$ 3: A finishes, Free = 3 + 3 = 6.
3. B needs 4 $\le$ 6: B finishes, Free = 6 + 1 = 7.
4. D needs 5 $\le$ 7: D finishes, Free = 10.

Safe sequence: $\langle C, A, B, D \rangle$. The new state is safe, so the request is granted.

A system call is the controlled interface through which a user program requests a service from the operating system kernel, such as file I/O, process creation or memory allocation. User programs run in user mode and cannot directly execute privileged instructions or access hardware, so they use system calls to switch into kernel mode and ask the OS to do the work on their behalf. Examples: fork(), exec(), open(), read(), write(), close(), wait(), exit().

Process of handling a system call (e.g. read(fd, buffer, nbytes)):

1. The user program pushes the parameters (fd, buffer address, count) on the stack or into registers and calls the library wrapper routine (e.g. read in libc).
2. The library routine places the system call number in a designated register and executes a trap instruction (syscall/int 0x80). This switches the CPU from user mode to kernel mode and transfers control to a fixed kernel entry point.
3. The kernel saves the user context (registers, program counter), then the system call handler uses the call number as an index into the system call table (dispatch table) to find the address of the required kernel routine.
4. The kernel routine validates the parameters (checks the pointers and permissions) and performs the requested service, possibly blocking the process while I/O completes.
5. The result or error code is stored in a register, the user context is restored, and a return-from-trap instruction switches the CPU back to user mode.
6. The library routine returns to the caller, which continues with the next instruction and examines the return value.

Parameters can be passed in registers, in a table in memory whose address is passed in a register, or on the stack.

A lock variable is a software solution for mutual exclusion that uses a single shared variable (lock) to guard the critical section. The lock has two values: $0$ means the critical section is free and $1$ means it is occupied.

Working: before entering its critical section a process tests the lock. If the lock is $0$, it sets it to $1$ and enters; if it is $1$, it waits (busy waits) until it becomes $0$. On leaving, the process sets the lock back to $0$.

int lock = 0;                 /* shared */

void process(void) {
    while (1) {
        while (lock != 0);    /* entry: wait until free */
        lock = 1;             /* take the lock */
        critical_section();
        lock = 0;             /* exit: release the lock */
        remainder_section();
    }
}

Problems:

1. Violates mutual exclusion (race condition). Testing and setting the lock are two separate steps and are not atomic. Suppose process $P_1$ reads lock == 0 and is pre-empted just before executing lock = 1. Process $P_2$ then also reads lock == 0, sets lock = 1 and enters the critical section. When $P_1$ is rescheduled it continues, sets lock = 1 and also enters. Both processes are now in the critical section together, so the lock variable itself is a shared resource with the same race it was meant to solve.
2. Busy waiting. A process that finds the lock set keeps looping and wastes CPU time.
3. No bounded waiting. There is no guarantee about who gets the lock next, so a process can starve.
4. It works only in the sense of an unreliable heuristic; correctness needs hardware support (an atomic Test-and-Set Lock or swap instruction) or constructs such as semaphores and Peterson's algorithm.

Internal vs external fragmentation

Numerical. The question gives the partitions as 150 KB, 200 KB, 250 KB, 100 KB and 300 KB (the "100 KB" total is clearly a typo, since the partitions total 1000 KB). Processes: A = 175 KB, B = 125 KB, loaded in that order.

Best-Fit (smallest hole that is large enough):

• A (175 KB): holes that fit are 200, 250, 300, and the smallest is 200 KB. Leftover $200-175=25$ KB.
• B (125 KB): holes that fit are 150, 250, 300, and the smallest is 150 KB. Leftover $150-125=25$ KB.

Worst-Fit (largest hole):

• A (175 KB): largest hole is 300 KB. Leftover $300-175=125$ KB.
• B (125 KB): the holes are now 150, 200, 250, 100, 125, so the largest is 250 KB. Leftover $250-125=125$ KB.

File attributes are the metadata that the operating system keeps about each file, in addition to its data. Typical attributes:

• Name: the human-readable symbolic name.
• Identifier: a unique number (e.g. inode number) used by the file system internally.
• Type: text, executable, binary, etc.
• Location: pointer to the device and disk blocks where the file is stored.
• Size: current size in bytes or blocks.
• Protection: permissions for read/write/execute for owner, group and others.
• Time, date and user identification: creation, last modification and last access, and owner.
• Flags: read-only, hidden, system, archive, etc.

This information is stored in the directory structure, which is kept on disk.

Implementation of directories: linear list

A directory is a file that maps file names to the files themselves. In the simplest implementation, the directory is a linear list of entries, each holding a file name together with a pointer to its data blocks or to its attributes.

Examples of an entry:

• MS-DOS/CP/M: each entry holds the file name, extension, attributes, size, time/date and the number of the first disk block. The remaining blocks are found through the FAT.
• UNIX: each entry holds just the file name and the inode number; the attributes and the block addresses are stored in the inode.

Operations:

• Create a file: search the list to be sure the name is not already used, then add a new entry at the end (or in a free slot).
• Open/search a file: search the list linearly for the name and read the pointer.
• Delete a file: search for the name, then release its space and mark the entry free (set a special name, or copy the last entry into the gap, or keep a free-entry list).

Advantages: very simple to program.

Disadvantages: searching is slow, taking $O(n)$ time for $n$ entries, and since directories are searched often this is noticeable for large directories. This is usually reduced by keeping the list sorted (binary search, but the list must be kept sorted on each insertion), by caching recently used entries, or by using a hash table with the linear list, which gives nearly constant-time lookup at the cost of collisions and a fixed table size.

Disk interleaving is the technique of numbering the sectors on a track not consecutively but with a gap between logically consecutive sectors, so that logical sector $n+1$ is physically placed a few sectors after sector $n$. The gap is called the interleave factor.

Why it is needed. After the controller reads a sector, it needs some time to transfer the data to memory (and perhaps check the error-correcting code). During this time the disk keeps rotating. If the sectors were numbered consecutively (interleave 1:1), the head would already have passed the beginning of the next sector by the time the controller is ready to read it, and the system would have to wait for almost a full rotation to read the next sector. Interleaving places the next logical sector so that it arrives under the head just when the controller is ready, thus avoiding the wasted revolution and improving throughput.

Example. Take a track with 8 sectors.

• No interleaving (1:1): physical order 0 1 2 3 4 5 6 7. Having read sector 0, the controller needs the time of about one sector to process it, so sector 1 has gone past and it must wait for nearly one complete rotation. Reading all 8 sectors takes about $8$ rotations.
• Single interleaving (2:1): physical order 0 4 1 5 2 6 3 7. Logical sector 1 sits two positions after sector 0. While sector 0's data is being transferred, the disk moves across the intermediate sector, and sector 1 arrives just in time. All 8 sectors are read in about $2$ rotations.
• Double interleaving (3:1) places the next sector two positions away, for slower controllers.

The correct factor depends on the speed of the controller and the CPU relative to the rotation speed. Modern disks, with buffering and fast controllers, do not need interleaving (the factor is 1:1), but the concept remains important for slow controllers and floppy-disk-era hardware.

A resource allocation graph (RAG) is a directed graph used to describe the allocation state of the system precisely. It has:

• A set of vertices $V$, divided into processes $P=\{P_1,\dots,P_n\}$ (drawn as circles) and resource types $R=\{R_1,\dots,R_m\}$ (drawn as rectangles, with dots for the instances).
• A request edge $P_i \to R_j$: $P_i$ is waiting for an instance of $R_j$.
• An assignment edge $R_j \to P_i$: an instance of $R_j$ is allocated to $P_i$.

Deadlock detection with a single instance of each resource. When every resource type has exactly one instance, a RAG can be converted into a wait-for graph by removing resource nodes: an edge $P_i \to P_j$ exists if $P_i$ is waiting for a resource currently held by $P_j$ (i.e. $P_i\to R\to P_j$ in the RAG). The rule is:

A deadlock exists if and only if the wait-for graph contains a cycle.

The system periodically runs a cycle-detection algorithm (a depth-first search, $O(n^2)$ for $n$ vertices); every process on the cycle is deadlocked. If a cycle is found, recovery is by process termination or resource preemption.

Example. Resources $R_1$ and $R_2$ each have a single instance.

• $R_1 \to P_1$ ($P_1$ holds $R_1$)
• $R_2 \to P_2$ ($P_2$ holds $R_2$)
• $P_1 \to R_2$ ($P_1$ requests $R_2$)
• $P_2 \to R_1$ ($P_2$ requests $R_1$)

RAG cycle: $P_1 \to R_2 \to P_2 \to R_1 \to P_1$.

The wait-for graph is $P_1 \to P_2 \to P_1$, a cycle. $P_1$ is waiting for $P_2$ to release $R_2$, and $P_2$ is waiting for $P_1$ to release $R_1$, so neither can proceed and both processes are deadlocked.

If $P_2$ did not request $R_1$, there would be no cycle in the graph ($P_1\to R_2\to P_2$ ends), $P_2$ could finish and release $R_2$, and no deadlock would exist.

Shortest Job First (SJF) is a CPU scheduling algorithm in which the CPU is allocated to the ready process with the smallest next CPU burst. It is non-preemptive: once a process starts, it runs to completion of its burst. It gives the minimum average waiting time for a given set of processes, but it can cause starvation of long jobs and needs the burst length in advance (estimated using exponential averaging).

Shortest Remaining Time Next (SRTN) is the preemptive version of SJF. Whenever a new process arrives, its burst is compared with the remaining time of the running process, and if it is shorter, the running process is pre-empted.

Example.

SJF (non-preemptive). P1 runs from 0 to 8 (only one process is available at 0). At 8, P3 (2) is shorter than P2 (4), so P3 runs 8 to 10, then P2 runs 10 to 14.

Gantt chart: | P1 (0-8) | P3 (8-10) | P2 (10-14) |

Waiting times: P1 $=0$, P2 $=10-1=9$, P3 $=8-2=6$. Average $=(0+9+6)/3=5$.

SRTN (preemptive).

• 0 to 1: P1 runs (remaining 7).
• At 1, P2 (4) < P1 (7): P2 runs 1 to 2 (remaining 3).
• At 2, P3 (2) < P2 (3): P3 runs 2 to 4 and finishes.
• Then P2 runs 4 to 7, and P1 runs 7 to 14.

Gantt chart: | P1 (0-1) | P2 (1-2) | P3 (2-4) | P2 (4-7) | P1 (7-14) |

Completion times: P3 $=4$, P2 $=7$, P1 $=14$. Waiting $=$ turnaround $-$ burst: P1 $=14-8=6$, P2 $=(7-1)-4=2$, P3 $=(4-2)-2=0$. Average $=(6+2+0)/3=2.67$.

SRTN gives a lower average waiting time than SJF here, but it involves more context switches.

The file system must keep track of which disk blocks are free so that they can be allocated to new files. The common approaches are:

1. Bit map (bit vector): one bit per block, $1$ = free and $0$ = allocated (or vice versa). It is simple, and finding $n$ consecutive free blocks is easy, but the map takes space (a 1 TB disk with 4 KB blocks needs $2^{28}$ bits $=32$ MB).
2. Linked list: free blocks are chained together.
3. Grouping: the first free block holds the addresses of $n$ other free blocks; the last of these holds the addresses of the next $n$ free blocks.
4. Counting: each entry stores the address of the first free block together with the count of contiguous free blocks that follow.

Linked list approach. The free blocks are linked: a pointer to the first free block is kept at a special location on the disk (and cached in memory), and each free block contains the address of the next free block. To allocate a block, the first block in the list is taken and the head pointer is moved to the next one. When a file is deleted, its blocks are added to the list.

Example. Suppose blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25 and 26 are free, and the others are in use. The head pointer holds 2. The chain is:

$2 \to 3 \to 4 \to 5 \to 8 \to 9 \to 10 \to 11 \to 12 \to 13 \to 17 \to 18 \to 25 \to 26 \to \text{null}$

If a file needs 3 blocks, blocks 2, 3 and 4 are allocated and the head moves to block 5. Freeing them later puts them back at the head of the list.

Advantages: no extra space is needed other than the pointer (the list uses the free blocks themselves), and only the head needs to be kept in memory.

Disadvantages: traversing the list to find many free blocks requires reading each block from disk, which is slow; it is difficult to find a contiguous run of blocks; and a damaged pointer breaks the chain.

IPC in Linux

Inter-process communication (IPC) mechanisms let processes in Linux exchange data and synchronise. The main ones are:

• Pipes: unidirectional byte streams created with pipe(), used between related processes (parent and child). Shell pipelines such as ls | wc -l use them.
• Named pipes (FIFOs): pipes with a name in the file system, created with mkfifo, which allow unrelated processes to communicate.
• Signals: asynchronous notifications sent to a process with kill() (e.g. SIGINT, SIGKILL, SIGUSR1); the receiver handles them with a signal handler.
• Message queues: the kernel keeps a list of typed messages (msgget, msgsnd, msgrcv).
• Shared memory: a memory region mapped into the address space of several processes (shmget, shmat); this is the fastest method, but it needs synchronisation.
• Semaphores: counters used for synchronising access to shared resources (semget, semop).
• Sockets: for communication between processes on the same or on different machines.

Disk access

Accessing a disk involves moving data between the disk surface and memory. The time to read or write a block consists of:

1. Seek time: time to move the read/write head to the required cylinder (usually the largest component).
2. Rotational latency: time for the required sector to rotate under the head, on average half a rotation $=\frac{1}{2}\cdot\frac{60}{\text{RPM}}$ seconds.
3. Transfer time: time to transfer the data, $=\dfrac{\text{bytes to transfer}}{\text{transfer rate}}$.

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

For a 7200 RPM disk, the rotational latency is $\tfrac12\times 8.33 = 4.17$ ms. The OS uses disk scheduling algorithms (FCFS, SSTF, SCAN, C-SCAN) and caching to reduce the total seek time, and the disk controller carries out the actual operations, often through DMA.

Single-level and two-level directory systems

Single-level directory. All files of all users are kept in one directory.

• Simple to implement and understand, and file lookup is easy for a small number of files.
• Every file must have a unique name, and name clashes occur when many users exist.
• No grouping of files is possible, and searching becomes slow with many files.
• No protection or separate space per user.

Two-level directory. A Master File Directory (MFD) holds one entry for each user, and each entry points to that user's User File Directory (UFD), which contains only that user's files.

• Different users can use the same file name, since the full name is (user, file name).
• Searching is efficient because only the user's own UFD is searched, and users are isolated from each other (protection).
• Disadvantages: users cannot group their files into sub-groups, and sharing files between users is hard (needs a path name such as /user2/file).

Banker's algorithm problem

a. Need = Max − Allocation

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

1. P0: Need $(0,0,0,0)\le(1,5,2,0)$, so P0 runs. Work $=(1,5,2,0)+(0,0,1,2)=(1,5,3,2)$.
2. P2: Need $(1,0,0,2)\le(1,5,3,2)$. Work $=(1,5,3,2)+(1,3,5,4)=(2,8,8,6)$.
3. P3: Need $(0,0,2,0)\le(2,8,8,6)$. Work $=(2,8,8,6)+(0,6,3,2)=(2,14,11,8)$.
4. P1: Need $(0,7,5,0)\le(2,14,11,8)$. Work $=(2,14,11,8)+(1,0,0,0)=(3,14,11,8)$.
5. P4: Need $(0,6,4,2)\le(3,14,11,8)$. Work $=(3,14,12,12)$.

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

c. P1 requests $(0,4,2,0)$.

• Request $\le$ Need of P1 $(0,7,5,0)$: yes.
• Request $\le$ Available $(1,5,2,0)$: yes.

Pretend to grant it: Available $=(1,1,0,0)$, Allocation of P1 $=(1,4,2,0)$, Need of P1 $=(0,3,3,0)$.

Safety check: P0 (need 0000) runs, Work $=(1,1,1,2)$. P2 need $(1,0,0,2)\le(1,1,1,2)$, Work $=(2,4,6,6)$. P3 need $(0,0,2,0)$, Work $=(2,10,9,8)$. P1 need $(0,3,3,0)$, Work $=(3,14,11,8)$. P4 need $(0,6,4,2)$ runs. All finish with safe sequence $\langle P_0,P_2,P_3,P_1,P_4\rangle$, so the state is safe and the request can be granted immediately.

Race condition. A race condition occurs when two or more processes access shared data (memory, file, variable) at the same time, and the final result depends on the exact order in which their instructions are interleaved by the scheduler. For example, two processes executing counter++ each do load, increment, store. If a context switch occurs between the load and the store, one update is lost. For instance, with counter = 5, both read 5, both write 6, and the result is 6 instead of 7. Race conditions are avoided by ensuring mutual exclusion on the critical sections that touch shared data.

Busy waiting. Busy waiting (spinning) is when a process repeatedly tests a condition in a loop while waiting to enter its critical section, using CPU cycles without doing useful work:

while (lock == 1);   /* spin */

It wastes CPU time, and can even cause the priority inversion problem (a high-priority process spins waiting for a lower-priority process holding the lock, which never gets the CPU). A lock handled this way is called a spin lock.

Sleep and wakeup. Instead of spinning, a process that cannot proceed calls sleep(), which blocks it (it is moved out of the ready queue, so uses no CPU). When another process changes the condition, it calls wakeup(process), which makes the blocked process ready again.

Classic example, the producer-consumer problem with a bounded buffer of $N$ items and a shared count:

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

No CPU is wasted on waiting. However, this solution still has a race condition: if the consumer reads count == 0 and is pre-empted just before it calls sleep(), the producer inserts an item and sends wakeup, which is lost because the consumer is not yet asleep. Then the consumer sleeps, the producer eventually fills the buffer and sleeps, and both sleep forever. The fix is to store wakeup signals (a wakeup waiting bit) or, better, to use semaphores (down / up) or monitors, which make the check-and-sleep atomic.

Shell. A shell is a command interpreter, the program that provides the user interface to the operating system. It reads commands typed by the user (or from a script), interprets them, and asks the OS (by system calls) to run them. Examples: bash, sh, csh, zsh in Unix/Linux and cmd.exe in Windows. It supports I/O redirection, pipes, variables and scripting.

System call. A system call is the interface through which a user program requests a service from the kernel (file operations, process control, memory, communication). It uses a trap instruction to move from user mode to kernel mode, e.g. open(), read(), fork().

Disk scheduling. Cylinders 0 to 200, head at 95, queue: 82, 170, 43, 140, 24, 16, 190.

FCFS (service in arrival order): $95\to82\to170\to43\to140\to24\to16\to190$

$|95-82|+|82-170|+|170-43|+|43-140|+|140-24|+|24-16|+|16-190|$ $=13+88+127+97+116+8+174=\mathbf{623}\text{ cylinders}$

SSTF (nearest request first): $95\to82\to43\to24\to16\to140\to170\to190$

• $95\to82$: 13
• $82\to43$: 39 (43 is closer than 140, which is 58 away)
• $43\to24$: 19
• $24\to16$: 8
• $16\to140$: 124
• $140\to170$: 30
• $170\to190$: 20

$13+39+19+8+124+30+20=\mathbf{253}\text{ cylinders}$

SCAN (elevator; assuming the arm is moving toward cylinder 0 first): $95\to82\to43\to24\to16\to0\to140\to170\to190$

$(95-0)+(190-0)=95+190=\mathbf{285}\text{ cylinders}$

(If the head were moving toward the higher end first: $95\to140\to170\to190\to200\to16$ gives $(200-95)+(200-16)=105+184=289$ cylinders.)

C-SCAN (moving toward higher cylinders, jump back to 0 at the end, then continue upward): $95\to140\to170\to190\to200\to0\to16\to24\to43\to82$

$(200-95)+200+(82-0)=105+200+82=\mathbf{387}\text{ cylinders}$

(counting the return jump of 200; excluding the return it is $105+82=187$).

Seek time is proportional to the head movement, so SSTF performs best on this request set.

Starvation vs deadlock

Scheduling using multiple queues. In multilevel queue scheduling the ready queue is divided into several separate queues, for example (1) system processes, (2) interactive processes, (3) interactive editing, (4) batch processes, (5) student processes.

• Each process is permanently assigned to one queue according to its type, priority or memory size.
• Each queue has its own scheduling algorithm (e.g. RR for the interactive queue, FCFS for the batch queue).
• Scheduling is done between the queues too: either with fixed priority (a lower queue is served only when all higher ones are empty, which can cause starvation) or by time slicing (e.g. 80% of CPU time to the foreground RR queue and 20% to the background FCFS queue).

In multilevel feedback queue scheduling, processes can move between queues. A process that uses too much CPU time is moved to a lower-priority queue, and a process that waits too long in a low-priority queue is moved to a higher one (aging), preventing starvation.

Demerits of disabling interrupts for mutual exclusion

1. Not suitable for user processes. Giving a user process the power to disable interrupts is dangerous: if it forgets to enable them again, or enters an infinite loop, the whole system halts, since the clock interrupt and scheduler can no longer pre-empt it.
2. Does not work on multiprocessors. Disabling interrupts affects only the CPU that executed the instruction; other CPUs continue to run and can still access the shared memory.
3. Interrupts disabled for long cause loss or delay of device interrupts, hurting response time.

Fixed and variable partitioning

Fixed (static) partitioning. Main memory is divided into a fixed number of partitions at system start-up. The partitions may be of equal or unequal size. A process is loaded into a partition large enough for it, either using a separate queue per partition or a single queue.

• Simple, with little OS overhead.
• Causes internal fragmentation (the unused part of a partition), the degree of multiprogramming is limited by the number of partitions, and a process larger than the largest partition cannot be run.

Variable (dynamic) partitioning. Partitions are created dynamically during loading, with the exact size a process needs. The OS keeps a table or list of free holes and allocates by first-fit, best-fit or worst-fit.

• No internal fragmentation and better memory utilisation, and the number and size of partitions vary.
• As processes terminate and others are loaded, many small scattered holes appear, giving external fragmentation, which can be removed by compaction (at a cost in time).
• Requires more complex allocation and bookkeeping.

SJF (non-preemptive).

• P0 is the only process at $t=0$, so it runs from 0 to 7.
• At $t=7$, P1 (4), P2 (1), P3 (4) are ready. P2 is shortest and runs 7 to 8.
• P1 and P3 tie at 4; P1 arrived earlier, so P1 runs 8 to 12, then P3 runs 12 to 16.

Gantt chart: | P0 (0-7) | P2 (7-8) | P1 (8-12) | P3 (12-16) |

Waiting time = start − arrival: P0 $=0$, P1 $=8-2=6$, P2 $=7-4=3$, P3 $=12-5=7$.

$\text{Average waiting time (SJF)}=\frac{0+6+3+7}{4}=\frac{16}{4}=\mathbf{4}$

SRTN (preemptive SJF).

• $t=0$ to 2: P0 runs (remaining $7-2=5$).
• $t=2$: P1 (4) arrives; $4<5$, so P1 pre-empts P0. P1 runs 2 to 4 (remaining 2).
• $t=4$: P2 (1) arrives; $1<2$, so P2 runs 4 to 5 and finishes.
• $t=5$: P3 (4) arrives. Remaining: P0 = 5, P1 = 2, P3 = 4. P1 runs 5 to 7.
• P3 runs 7 to 11, then P0 runs 11 to 16.

Gantt chart: | P0 (0-2) | P1 (2-4) | P2 (4-5) | P1 (5-7) | P3 (7-11) | P0 (11-16) |

Completion: P0 $=16$, P1 $=7$, P2 $=5$, P3 $=11$. Turnaround $=$ completion $-$ arrival: $16,\ 5,\ 1,\ 6$. Waiting $=$ turnaround $-$ burst: P0 $=9$, P1 $=1$, P2 $=0$, P3 $=2$.

$\text{Average waiting time (SRTN)}=\frac{9+1+0+2}{4}=\frac{12}{4}=\mathbf{3}$

In linked list allocation, each file is stored as a linked list of disk blocks. Each block holds the data and a pointer to the next block of the file; the directory entry stores the address of the first block (and often the last). The blocks may be scattered anywhere on the disk. A variant keeps all the pointers in a table in memory, the File Allocation Table (FAT).

Advantages

1. No external fragmentation: every free block can be used, so no disk space is lost to fragmentation (apart from the unused part of the last block).
2. A file can grow dynamically; the size need not be declared at creation, and new blocks are linked on as needed.
3. The directory entry needs only the address of the first block, so it is simple.
4. Free-space management and allocation are easy, as any free block can be used.

Disadvantages

1. Slow random (direct) access: to reach the $n$-th block the system must follow $n$ pointers from the first block, each being a disk read. Only sequential access is efficient.
2. Pointer overhead: part of each block (e.g. 4 bytes) is used for the pointer, so the data capacity per block is not a power of two, which complicates reading and wastes space.
3. Reliability: if one pointer is lost or damaged, the rest of the file is lost, and bugs can link to a wrong block.
4. Blocks scattered over the disk cause extra seek time.

The FAT variant fixes the random access problem (the chain is followed in memory), but the whole table must be kept in memory, which is large for big disks.

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, with 4 frames. (OPR in the question is read as the optimal replacement algorithm.)

FIFO (replace the oldest page in memory)

The page loaded first (7) is replaced by 3, then 0 is replaced by 4, then 1 is replaced by 0.

FIFO page faults = 7

Optimal (replace the page that will not be used for the longest time)

• 7, 0, 1, 2: four faults, filling the frames {7, 0, 1, 2}.
• 0: hit.
• 3: fault. Future references 0, 4, 2, 3, 0, 3, 2 never use 7 again, so replace 7. Frames {3, 0, 1, 2}.
• 0: hit.
• 4: fault. Future references 2, 3, 0, 3, 2 never use 1, so replace 1. Frames {3, 0, 4, 2}.
• 2, 3, 0, 3, 2: all hits.

Optimal page faults = 6

Direct Memory Access (DMA) is a technique in which a special hardware unit, the DMA controller, transfers blocks of data directly between an I/O device and main memory without CPU involvement for each byte. Without DMA, the CPU would have to copy every byte or word itself (programmed I/O or interrupt-driven I/O), which wastes CPU time for fast devices such as disks.

Components of the DMA controller: an address register (memory address to read/write), a count register (number of bytes/words to transfer), a control register (direction, mode, etc.), and a data buffer, plus the request/acknowledge lines to the device and the bus.

Working mechanism

1. The CPU programs the DMA controller: it writes the memory address, the byte count, and the direction (read/write) to its registers, and starts the transfer. The CPU then continues with other work.
2. The DMA controller requests the disk controller to read a block from the disk into its internal buffer (for a read).
3. The DMA controller gets control of the bus (bus request/hold; the CPU grants the bus with a bus grant/hold acknowledge), and writes the data to the memory address by itself, incrementing the address register and decrementing the count register after each transfer.
4. The device controller sends an acknowledgement for each transfer. Steps 2 and 3 are repeated until the count reaches zero.
5. On completion, the DMA controller interrupts the CPU to say that the transfer is finished. Only one interrupt is generated per block rather than one per byte.

Transfer modes: burst (block) mode, where the DMA keeps the bus for the entire transfer; cycle stealing, where it takes the bus for one word at a time, slowing the CPU slightly; and transparent mode, where it uses the bus only when the CPU does not need it.

Advantage: the CPU is free to do other work during the transfer, so system throughput is much higher for bulk transfers.

Task of the disk controller

The disk controller is the hardware unit between the disk drive and the system bus/memory, which controls the operation of the drive. Its tasks include:

• Accepting commands from the CPU/OS (read, write, seek, format) and carrying them out by controlling the head movement (seek) and selecting the sector.
• Converting the logical block address into a physical cylinder, head and sector.
• Controlling the drive motor, and the read/write operations on the surface, and serialising and de-serialising data bits.
• Buffering a block (sector) in its internal buffer and transferring it to memory, often by DMA.
• Performing error detection and correction (ECC), and handling bad sectors.
• Reporting the status and interrupting the CPU after an operation completes.

Drawbacks of segmentation

1. External fragmentation: segments are of variable size, so as segments are loaded and removed, free memory is split into small unusable holes. Compaction is costly.
2. Complex memory allocation: finding a suitable hole for a segment (first-fit, best-fit) takes time.
3. Overhead of the segment table (base and limit for each segment) and extra memory access for each address translation, unless hardware registers or a cache are used.
4. A segment must be completely contiguous in memory, and a large segment may not fit even if the total free memory is sufficient.
5. Swapping large segments in and out is slow, and segmentation alone does not give good support for virtual memory without combining with paging.

The Translation Look-aside Buffer (TLB) is a small, fast, associative hardware cache inside the memory management unit that holds recently used page-table entries. In a paging system, every memory reference would otherwise require two memory accesses: one to read the page table entry and one for the data itself. The TLB reduces this.

Structure. The TLB is a small associative memory (typically 64 to 1024 entries). Each entry has two parts:

(Entries often also hold valid, protection/dirty bits and an address-space identifier, ASID.) All entries are compared with the page number simultaneously (associative search).

Operation. The CPU produces the logical address $(p, d)$.

• The page number $p$ is looked up in the TLB. If found (TLB hit), the frame number $f$ is available immediately, and the physical address $(f, d)$ is formed with only one memory access.
• If not found (TLB miss), the page table in memory is consulted, then the entry is added to the TLB (replacing an old entry by LRU or random), and the memory is accessed.

Effective access time. With hit ratio $h$, TLB search time $\epsilon$ and memory access time $m$:

$EAT = h(\epsilon + m) + (1-h)(\epsilon + 2m)$

For example, with $h=0.9$, $\epsilon=20$ ns, $m=100$ ns: $EAT = 0.9(120)+0.1(220)=130$ ns, compared with 200 ns without a TLB.

Advantages

1. Speeds up address translation significantly, since most references hit the TLB because of locality of reference.
2. Reduces the number of memory accesses per reference from two to nearly one.
3. Transparent to the user program, and the OS only has to flush or invalidate entries on a context switch (unless ASIDs are used).
4. Makes paging practical with large page tables.

Need for locality of reference

Locality of reference is the observation that during execution a program tends to access a relatively small set of pages or addresses over any short period of time. It has two forms: temporal locality (a recently used location is likely to be used again soon, e.g. loops and variables) and spatial locality (locations near a recently used one are likely to be used soon, e.g. sequential code and arrays).

We need this concept because:

1. It makes virtual memory and demand paging feasible: only the current working set of a process need be in memory, and page faults remain infrequent. Without locality, programs would cause constant page faults (thrashing).
2. It makes caches and the TLB effective, as most accesses hit the fast memory.
3. It guides page replacement (e.g. LRU) and the working-set model for deciding how many frames to give to a process.

Round Robin (RR) algorithm. Each process gets the CPU for a fixed time quantum; if it does not finish, it is pre-empted and put at the end of the ready queue.

Advantages

• Fair: every process gets an equal share of CPU, and there is no starvation.
• Good response time for interactive and time-sharing systems.
• Simple to implement, and the waiting time for a process is bounded: with $n$ processes and quantum $q$, no process waits more than $(n-1)q$.

Disadvantages

• The performance depends heavily on the quantum: too large makes it behave like FCFS, and too small causes excessive context-switch overhead.
• The average waiting and turnaround times are often longer than SJF.
• No distinction of priority or importance between processes.
• Long context-switching overhead if there are many processes.

Switching from user mode to kernel mode

The CPU runs user programs in user mode, where privileged instructions and direct hardware access are not allowed. It switches to kernel mode when:

1. A process makes a system call (a trap/syscall instruction) to ask for an OS service.
2. A hardware interrupt occurs (timer, disk, keyboard).
3. An exception/trap occurs (page fault, divide by zero, illegal instruction).

After the OS has handled the event, it returns to user mode. Example: when a program calls printf("Hello"), the library calls write(); the trap instruction switches the CPU to kernel mode, the kernel writes the bytes to the terminal device, and control then returns to the program in user mode.

Scheduling problem

Turnaround time (TAT) $=$ completion $-$ arrival; waiting time (WT) $=$ TAT $-$ burst.

FCFS

Gantt chart: | P0 (0-5) | P1 (5-8) | P2 (8-16) | P3 (16-22) |

Average WT $=\dfrac{0+4+6+13}{4}=\mathbf{5.75}$; average TAT $=\dfrac{5+7+14+19}{4}=\mathbf{11.25}$.

Priority (non-preemptive, 4 = highest)

P0 starts at 0 (alone). At $t=5$, P1 (4), P2 (2) and P3 (3) are waiting, so the order is P1, P3, P2.

Gantt chart: | P0 (0-5) | P1 (5-8) | P3 (8-14) | P2 (14-22) |

Average WT $=\dfrac{0+4+12+5}{4}=\mathbf{5.25}$; average TAT $=\dfrac{5+7+20+11}{4}=\mathbf{10.75}$.

Round Robin (quantum = 2)

Processes arriving at the same time as a pre-emption enter the queue before the pre-empted process.

Gantt chart: | P0 (0-2) | P1 (2-4) | P2 (4-6) | P0 (6-8) | P3 (8-10) | P1 (10-11) | P2 (11-13) | P0 (13-14) | P3 (14-16) | P2 (16-18) | P3 (18-20) | P2 (20-22) |

Average WT $=\dfrac{9+7+12+11}{4}=\dfrac{39}{4}=\mathbf{9.75}$; average TAT $=\dfrac{14+10+20+17}{4}=\dfrac{61}{4}=\mathbf{15.25}$.

Critical section. A critical section is the part of a program in which a process accesses shared resources (shared variables, files, devices) and which must not be executed by more than one process at a time. We recognise it by looking for code that reads and updates shared data, where the result may depend on the order of execution. A process structure is: entry section, critical section, exit section, remainder section.

A correct solution must satisfy mutual exclusion (only one process in the critical section), progress (processes outside it cannot block others from entering) and bounded waiting (no process waits forever).

Why synchronise it. If several processes enter at once, the interleaving of their instructions on shared data creates race conditions, leading to inconsistent or lost updates. For example, two processes doing balance = balance + 100 on a shared variable can both read the same old value and one update is lost. Synchronisation (semaphores, mutexes, monitors, Peterson's algorithm) ensures that updates take place one at a time and data stays consistent.

Page replacement (4 frames). Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2.

FIFO

FIFO page faults = 7

LRU (replace the least recently used page)

• At ref 3, the least recently used page is 7, so it is replaced.
• At ref 4, the recency order is 1 (oldest), 2, 3, 0, so 1 is replaced.
• Pages 2, 3, 0 are then all in memory, so the remaining references hit.

LRU page faults = 6

Deadlock with preemptive resources

Deadlock normally involves non-preemptive resources (printers, tape drives, locked records), which cannot be forcibly taken away from the process holding them. A preemptive resource (such as the CPU or memory pages) can be taken from a process without ill effects, e.g. memory can be swapped out to disk and restored later. Since the "no preemption" condition does not hold, deadlock cannot occur over purely preemptive resources: if process $A$ needs memory held by $B$, the OS can pre-empt $B$'s memory, so the circular wait is broken. Deadlocks arise from non-preemptive resources.

Conditions for deadlock (Coffman conditions) — all four must hold together:

1. Mutual exclusion: a resource can be used by only one process at a time.
2. Hold and wait: a process holding at least one resource waits to acquire additional resources held by others.
3. No preemption: a resource can be released only voluntarily by the process holding it.
4. Circular wait: there is a circular chain of processes $P_0,P_1,\dots,P_n$ in which each waits for a resource held by the next, and $P_n$ waits for one held by $P_0$.

Resource allocation graph. It is a directed graph $G=(V,E)$ describing the allocation state. $V$ consists of processes (circles) and resource types (rectangles, with dots for instances). A request edge $P_i\to R_j$ shows that $P_i$ is waiting for $R_j$; an assignment edge $R_j\to P_i$ shows that an instance of $R_j$ is held by $P_i$.

• If the graph has no cycle, there is no deadlock.
• If it has a cycle and each resource has a single instance, there is a deadlock.
• If it has a cycle and resources have multiple instances, deadlock is possible but not certain.

Example. Resources $R_1$, $R_2$ with one instance each.

Edges: $R_1\to P_1$, $R_2\to P_2$, $P_1\to R_2$, $P_2\to R_1$.

The cycle $P_1\to R_2\to P_2\to R_1\to P_1$ exists. $P_1$ holds $R_1$ and waits for $R_2$, while $P_2$ holds $R_2$ and waits for $R_1$, so both are deadlocked.

If a further process $P_3$ is added with a request edge $P_3\to R_1$, it also waits but is not part of the cycle (it is blocked behind the deadlock).

Memory allocation strategies decide how memory is given to processes. They can be divided into contiguous and non-contiguous allocation.

1. Contiguous allocation. Each process is loaded in a single contiguous block of memory.

• Fixed (static) partitioning: memory is divided into fixed-size partitions, each holding one process. It is simple, but suffers from internal fragmentation and a fixed degree of multiprogramming.
• Variable (dynamic) partitioning: a partition is created with the exact size needed. It avoids internal fragmentation, but gives rise to external fragmentation, solved by compaction.

Placement strategies (choosing a free hole for a new process):

• First-fit: allocate the first hole that is large enough. Fast.
• Next-fit: like first-fit, but the search starts from where the previous search ended.
• Best-fit: allocate the smallest hole that is large enough. Minimises the leftover but leaves many tiny holes and needs a full search.
• Worst-fit: allocate the largest hole, so that the leftover hole is large enough to be useful. Usually performs poorly.
• Buddy system: memory is split into blocks of size power of 2; a request is rounded up to the next power of 2, and a block is halved repeatedly until the right size is reached. Freed buddies are merged. It is fast but causes internal fragmentation.

2. Non-contiguous allocation. A process may be placed in several separate parts of memory.

• Paging: logical memory is divided into fixed-size pages and physical memory into frames of the same size; a page table maps pages to frames. There is no external fragmentation, only some internal fragmentation in the last page.
• Segmentation: the process is divided into logical segments (code, data, stack) of variable size, each with a base and limit in the segment table. It matches the programmer's view, but suffers from external fragmentation.
• Segmented paging: segments are divided into pages, combining both.

3. Virtual memory (demand paging). Pages are loaded only when referenced, so a process can be larger than physical memory; page replacement algorithms (FIFO, LRU, Optimal) decide which page to evict.

Given: 201 cylinders (0 to 200), head at 10 moving inward (towards higher cylinder numbers), queue: 30, 85, 90, 100, 105, 110, 135, 145.

FCFS (requests served in arrival order):

$10\to30\to85\to90\to100\to105\to110\to135\to145$

$\text{Total seek} = 20+55+5+10+5+5+25+10 = 135 \text{ cylinders}$

SSTF (always serve the request closest to the current head position): every request lies ahead of the head (all are above cylinder 10). From each position the nearest pending request is the next higher one, so the service order is exactly $30, 85, 90, 100, 105, 110, 135, 145$.

$\text{Total seek} = 20+55+5+10+5+5+25+10 = 135 \text{ cylinders}$

Both algorithms give a total seek of 135 cylinders, because the queue is already sorted in the direction of head movement.

An interrupt is a signal sent to the CPU by a device or by software which causes the CPU to suspend the current instruction stream, save its state, run an interrupt service routine (ISR), and then resume the interrupted work.

Advantages of using interrupts

1. Efficient CPU utilisation. Without interrupts the CPU must poll a device repeatedly (busy waiting) to know whether it is ready. With interrupts the CPU does useful work and is notified only when the device needs service.
2. Overlap of I/O and computation. While a slow device such as a disk or printer transfers data, the CPU can execute another process. This is the basis of multiprogramming.
3. Fast response to events. Urgent events (power failure, timer expiry, keyboard input, network packet arrival) are handled immediately rather than waiting for the next polling cycle.
4. Higher throughput. Less CPU time is wasted on checking status registers, so more jobs are completed per unit time.
5. Priority handling. Interrupts have priority levels; a higher-priority interrupt can pre-empt a lower-priority ISR, so critical devices are serviced first.
6. Support for system calls, exceptions and time-sharing. Software interrupts (traps) let user programs request OS services, page faults and divide-by-zero are handled as exceptions, and the timer interrupt lets the OS pre-empt processes for fair CPU sharing.
7. Simpler device handling. Each device has an ISR registered in the interrupt vector table, so the main program does not have to contain device-specific checking code.

Belady's anomaly. In some page replacement algorithms, notably FIFO, increasing the number of page frames allocated to a process can increase the number of page faults instead of decreasing it. This unexpected behaviour is called Belady's anomaly.

Example with FIFO and reference string $1,2,3,4,1,2,5,1,2,3,4,5$: with 3 frames there are 9 page faults, but with 4 frames there are 10 page faults. Stack algorithms such as LRU and Optimal never show the anomaly.

Benefits of multiprogramming over uniprogramming

1. Better CPU utilisation. In uniprogramming the CPU sits idle while the single program waits for I/O. In multiprogramming another process is run during that time, so the CPU stays busy.
2. Higher throughput. More jobs are completed per unit time.
3. Better utilisation of other resources (memory, disk, I/O devices), because several jobs use different resources simultaneously.
4. Reduced average waiting and response time for short jobs, which need not wait for a long job to finish.
5. Economical. The same hardware serves many users/jobs, which reduces the cost per job.
6. Basis for time-sharing, which gives interactive use to several users at once.

Mutual exclusion means that when one process is executing in its critical section, no other process may enter its own critical section for the same shared resource. It prevents race conditions. It can be achieved in the following ways.

1. Disabling interrupts. A process disables all interrupts before entering the critical section and enables them on leaving. The CPU cannot switch to another process meanwhile. This works only on a single processor and is unsafe to allow user processes to do; it is used inside the kernel.

2. Lock variables. A shared variable lock is 0 when free. A process tests it and sets it to 1 before entering. This alone fails, because two processes can both read 0 before either sets 1.

3. Strict alternation. A shared variable turn decides whose turn it is; the processes enter alternately.

while (1) {
    while (turn != 0) ;   /* busy wait */
    critical_section();
    turn = 1;
    noncritical_section();
}

It guarantees mutual exclusion but violates the progress condition, since a process outside its critical section can block the other.

4. Peterson's solution. Uses flag[2] and turn:

flag[i] = true; turn = j;
while (flag[j] && turn == j) ;
/* critical section */
flag[i] = false;

It satisfies mutual exclusion, progress and bounded waiting for two processes.

5. Hardware support (TSL/Test-and-Set, Swap). The atomic instruction TSL reads a lock and sets it in one indivisible step, so only one process gets the lock. It works on multiprocessors but still uses busy waiting (spin lock).

6. Semaphores and mutexes. A binary semaphore initialised to 1: wait(mutex) before the critical section, signal(mutex) after it. A blocked process sleeps instead of spinning.

7. Monitors. A high-level language construct where only one process can be active inside the monitor at a time, with condition variables for synchronisation.

Difference between thread and process

Process state transition diagram

                 admitted                     interrupt
      New  ----------------->  Ready  <-------------------+
                               ^   |                       |
                               |   | scheduler dispatch    |
        I/O or event completion|   v                       |
                               |  Running  ----------------+
                               |   |   \
                               |   |    \ exit
                               |   |     v
                               |   |   Terminated
                               |   | I/O or event wait
                               |   v
                               +--- Waiting (Blocked)

• New to Ready: the process is created and admitted to the ready queue.
• Ready to Running: the scheduler dispatches it to the CPU.
• Running to Ready: its time quantum expires, or a higher-priority process pre-empts it (interrupt).
• Running to Waiting: it requests I/O or waits for an event.
• Waiting to Ready: the I/O or event completes.
• Running to Terminated: it finishes execution (exit).

Page fault. A page fault occurs when a running process references a page that is in its logical address space but is not currently in main memory (its valid/present bit is 0 in the page table). The MMU raises a trap to the operating system. The OS then:

1. Checks that the reference is legal (otherwise the process is terminated).
2. Finds a free frame (or selects a victim page using a replacement algorithm and writes it back to disk if it is dirty).
3. Reads the required page from the backing store (disk) into that frame.
4. Updates the page table (sets the frame number and valid bit).
5. Restarts the instruction that caused the fault.

Page faults are normal in demand paging, where a page is loaded only when first referenced.

Structure of a page table. The page table has one entry for each page of the process, indexed by page number. A typical entry:

+---------+--------+-----------+-------+------------+-------------+
| Present | Dirty  | Reference | Prot. |  Caching   | Page frame  |
| /Valid  |(Modif.)|  (R bit)  | (R/W/X)| disabled  |   number    |
+---------+--------+-----------+-------+------------+-------------+

• Page frame number: the main goal of the mapping.
• Present/valid bit: 1 if the page is in memory, 0 causes a page fault.
• Protection bits: read, write, execute permission.
• Modified (dirty) bit: set when the page is written, so it must be saved before replacement.
• Referenced bit: set on any access, used by replacement algorithms.
• Caching disabled bit: for pages mapped to device registers.

Address translation: logical address $=(p,d)$; the page table entry $p$ gives frame $f$, and the physical address is $f\times\text{page size}+d$.

Segmentation divides the logical address space of a process into variable-size segments such as main program, procedures, data, stack. Each logical address is a pair $(s,d)$, where $s$ is the segment number and $d$ is the offset within that segment.

Segment table. Each process has a segment table. Each entry holds:

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

Translation of logical to physical address

 CPU --> (s, d)
          |    \
          |     \ d
          v      v
   +-------------+      d < limit ?
   | Segment     |----> yes: physical address = base + d  --> Memory
   | table       |      no : trap (addressing error)
   | s -> limit,base
   +-------------+

Steps:

1. The CPU generates logical address $(s,d)$.
2. The segment number $s$ indexes the segment table (located using the segment-table base register, STBR, and checked against STLR, the segment-table length register).
3. The entry gives the limit and base of the segment.
4. If $d<\text{limit}$, the physical address is $PA = \text{base} + d$ otherwise the hardware traps to the OS with an addressing error.

Example: if segment 2 has base 4300 and limit 400, then address $(2,53)$ maps to $4300+53=4353$, while $(2,500)$ causes a trap.

Advantages

• Matches the user's logical view of the program.
• No internal fragmentation.
• Easy sharing and protection of segments (a code segment can be shared, with read-only protection).
• Segments can grow dynamically (for example, stack or heap).
• Supports dynamic linking and modular programming.

Disadvantages

• Suffers from external fragmentation; compaction may be required.
• Allocation of variable-size segments is harder (first/best fit needed).
• Segment table adds memory overhead and an extra memory access per reference (reduced by a TLB).
• Segments must be contiguous in memory, so large segments may not fit.
• Swapping of whole segments is slow.

Given: tracks 0 to 150, head at 30 moving outward (towards track 0), queue: 35, 70, 45, 15, 65, 20, 80, 90, 75, 130.

Sorted requests: 15, 20, 35, 45, 65, 70, 75, 80, 90, 130. Below the head: 20, 15. Above the head: 35, 45, 65, 70, 75, 80, 90, 130.

SCAN (elevator). The head moves outward serving 20 and 15, continues to track 0, reverses and serves all requests up to 130.

Order: $30\to20\to15\to0\to35\to45\to65\to70\to75\to80\to90\to130$

$\text{Seek} = (30-0)+(130-0) = 30+130 = 160 \text{ tracks}$

C-SCAN. The head moves outward to track 0, then jumps to the other end (track 150) and again moves outward, serving the remaining requests.

Order: $30\to20\to15\to0\to150\to130\to90\to80\to75\to70\to65\to45\to35$

$\text{Seek} = 30 + 150 + (150-35) = 30+150+115 = 295 \text{ tracks}$

(If the return jump is not counted, the seek is $30+115=145$ tracks.)

LOOK. The head goes outward only as far as the last request (15), then reverses to the farthest request (130).

Order: $30\to20\to15\to35\to45\to65\to70\to75\to80\to90\to130$

$\text{Seek} = (30-15)+(130-15) = 15+115 = 130 \text{ tracks}$

C-LOOK. The head goes outward to 15, jumps to the farthest request on the other side (130), and continues outward.

Order: $30\to20\to15\to130\to90\to80\to75\to70\to65\to45\to35$

$\text{Seek} = (30-15) + (130-15) + (130-35) = 15+115+95 = 225 \text{ tracks}$

(Without counting the jump from 15 to 130: $15+95=110$ tracks.)