Operating Systems

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

Time-sharing versus real-time operating systems.

Batch operating system

Jobs with similar requirements are grouped into batches and run one after another without user interaction. The operator collects jobs (punched cards or tape), the resident monitor loads and runs each job automatically, and output is returned later.

• Advantages: reduces setup time and idle CPU time; good for large repetitive jobs.
• Disadvantages: no interaction; long turnaround time; CPU idle during I/O; difficult debugging.

Time-sharing operating system

A logical extension of multiprogramming where the CPU is switched among many interactive users so quickly (each gets a short time quantum, using round robin) that every user feels they have a dedicated machine. Users interact with the computer through terminals.

• Advantages: short response time; many users share the computer; CPU idle time is reduced; interactive debugging.
• Disadvantages: needs more complex scheduling, memory management and protection; overhead from context switching; security of user data.

Examples: UNIX, Linux, Multics.

Cylinders 0-99, head at 45, request queue: 88, 72, 13, 74, 48, 9, 22, 50, 35, 30.

FCFS (serve in arrival order): $45 \to 88 \to 72 \to 13 \to 74 \to 48 \to 9 \to 22 \to 50 \to 35 \to 30$

$43 + 16 + 59 + 61 + 26 + 39 + 13 + 28 + 15 + 5 = 305 \text{ cylinders}$

SSTF (always go to the nearest pending request): $45 \to 48 \to 50 \to 35 \to 30 \to 22 \to 13 \to 9 \to 72 \to 74 \to 88$

$3 + 2 + 15 + 5 + 8 + 9 + 4 + 63 + 2 + 14 = 125 \text{ cylinders}$

SCAN (elevator), assuming the head is initially moving towards higher cylinders:

$45 \to 48 \to 50 \to 72 \to 74 \to 88 \to 99$ (end), then reverse: $99 \to 35 \to 30 \to 22 \to 13 \to 9$

$(99 - 45) + (99 - 9) = 54 + 90 = 144 \text{ cylinders}$

If the head were initially moving towards 0, the path is $45 \to 35 \to 30 \to 22 \to 13 \to 9 \to 0 \to 48 \to 50 \to 72 \to 74 \to 88$, giving $45 + 88 = 133$ cylinders.

SSTF gives the least movement here, though it can starve requests far from the head.

Critical section. The part of a process's code in which it accesses shared resources (shared variables, files, buffers). Only one process may execute its critical section at a time, otherwise the result depends on the order of execution (a race condition). A solution must provide mutual exclusion, progress and bounded waiting.

Semaphore operations. A semaphore is an integer variable accessed only through two atomic operations:

• wait(S) (also P or down): while (S <= 0) ; S = S - 1; It blocks the process if $S \le 0$.
• signal(S) (also V or up): S = S + 1; It wakes a blocked process, if any.

A binary semaphore takes the values 0 and 1 (used for mutual exclusion). A counting semaphore can take any non-negative value (used for resource counting). An initialisation operation sets the starting value.

Producer-consumer (bounded buffer) using semaphores. A producer puts items into a buffer of size $N$, and a consumer removes them. Three semaphores are used:

semaphore mutex = 1;   // mutual exclusion on buffer
semaphore empty = N;   // number of empty slots
semaphore full  = 0;   // number of filled slots

Producer:                    Consumer:
while (true) {               while (true) {
    produce item;                wait(full);
    wait(empty);                 wait(mutex);
    wait(mutex);                 remove item from buffer;
    insert item into buffer;     signal(mutex);
    signal(mutex);               signal(empty);
    signal(full);                consume item;
}                            }

How it works:

• The producer waits on empty, so it blocks when the buffer is full.
• The consumer waits on full, so it blocks when the buffer is empty.
• mutex ensures only one process manipulates the buffer at a time, which prevents a race condition.
• Each signal tells the other side that a slot or an item has become available.

The order of the wait calls matters. Waiting on mutex before empty or full could cause deadlock.

Why virtual memory is used.

• It lets a program larger than physical memory run, since only the needed parts are kept in RAM and the rest stays on disk.
• It allows more processes to be in memory at once, which raises CPU utilisation and multiprogramming.
• It frees the programmer from memory limits, because each process sees its own large, contiguous address space.
• It gives protection and isolation between processes, and less I/O is needed to load or swap programs.

It is implemented by demand paging or demand segmentation.

Logical address. The address generated by the CPU during program execution. It is also called a virtual address. The set of all logical addresses is the logical address space. The memory management unit (MMU) translates it into a physical address, the actual location in main memory.

Logical-to-physical translation in single-level paging.

Logical memory is divided into fixed-size pages and physical memory into frames of the same size. A logical address is split into:

• page number $p$: the index into the page table
• page offset $d$: the position inside the page

If the page size is $2^n$, the low $n$ bits are the offset and the remaining high bits are the page number.

Steps:

1. The CPU generates a logical address $(p, d)$.
2. The page number $p$ indexes the page table (located using the page table base register), giving the frame number $f$.
3. The physical address is formed by joining $f$ and $d$:

$\text{Physical address} = f \times \text{page size} + d$

Example: page size 1 KB, page 2 is in frame 5. Logical address $2\times1024 + 100 = 2148$ gives $p=2$, $d=100$, so the physical address is $5\times1024 + 100 = 5220$.

If the page is not in memory (valid bit 0), a page fault occurs and the OS loads the page from disk into a free frame. A TLB (translation look-aside buffer) is normally used to cache recent page-table entries and speed up the lookup.

Kernel. The core part of an operating system. It is loaded first, stays in memory, and runs in privileged mode. It manages the CPU (process scheduling), memory, devices and system calls, and acts as the bridge between hardware and application software.

Monolithic kernel versus microkernel.

DMA (Direct Memory Access) is a technique in which a special hardware controller, the DMA controller, transfers a block of data directly between an I/O device and main memory without passing each byte through the CPU. This frees the CPU for other work during large transfers.

How it works.

1. The CPU programs the DMA controller with the memory address, the byte count, the direction of transfer (read or write) and the device.
2. The DMA controller requests the bus from the CPU (bus request or HOLD).
3. The CPU grants the bus (bus grant or HLDA) and pauses its use of it. This is cycle stealing, or burst mode for a block.
4. The controller transfers data between the device and memory directly and updates the address and count after each transfer.
5. When the count reaches zero, the controller releases the bus and sends an interrupt to the CPU to signal completion.

Diagram.

        +-------+        +--------+        +-----------+
        |  CPU  |<------>|  Main  |<------>|    DMA    |<--- I/O device
        |       |        | Memory |        | controller|     (disk, etc.)
        +-------+        +--------+        +-----------+
            ^   |  Address / data / control bus  ^   |
            |   +--------------------------------+   |
            |   Bus request / Bus grant              |
            +-------- Interrupt on completion -------+

The DMA controller contains an address register, a count register and a control register.

Types of files.

• Regular (ordinary) files: contain user data, either text (ASCII lines) or binary (executables, images).
• Directories: system files that hold the names and attributes of other files.
• Character special files: model serial I/O devices such as terminals and printers.
• Block special files: model block devices such as disks.
• Other types include links (symbolic files) and pipes or sockets.

Sequential access. Records are read or written in order, one after another, from the beginning. A read moves a file pointer forward, and a rewind goes back to the start. To reach record $n$, all earlier records must be passed. It suits tapes and batch processing, and is simple but slow for locating a specific record.

Random (direct) access. Any record or byte can be read or written directly, in any order, by giving its position, e.g. with seek(offset) or read(n). The file is treated as a numbered sequence of fixed-size blocks. It suits disks, databases and any application needing fast lookup. A sequential read can be simulated on a random-access file, but not the reverse.

The five-state model describes the life cycle of a process using five states.

States.

• New: the process is being created (PCB set up) but is not yet admitted to the ready pool.
• Ready: the process is in memory and waiting for the CPU.
• Running: its instructions are being executed on the CPU.
• Blocked (waiting): the process cannot continue until some event occurs, such as I/O completion.
• Exit (terminated): the process has finished or was aborted, and the OS reclaims its resources.

Diagram.

             admit              dispatch              release
   New  ------------> Ready  ------------> Running  ------------> Exit
                       ^  ^  <-----------    |
                       |  |   timeout /      |
                       |  |   preemption     | event wait (I/O request)
                       |  |                  v
                       |  +------------  Blocked
                       |   event occurs
                       +-------------------

Transitions.

• New to Ready: the OS admits the process.
• Ready to Running: the scheduler dispatches it.
• Running to Ready: its time slice expires or it is preempted.
• Running to Blocked: it requests I/O or waits for an event.
• Blocked to Ready: the awaited event occurs.
• Running to Exit: it completes or is terminated.

Deadlock. A situation in which a set of processes is permanently blocked, because each process holds some resources and waits for a resource held by another process in the set. None can proceed, so none can release what it holds.

Example: process P1 holds resource R1 and requests R2, while P2 holds R2 and requests R1.

Necessary (Coffman) conditions. All four must hold at the same time for deadlock to occur.

1. Mutual exclusion: at least one resource is non-shareable, so only one process can use it 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 by the process holding it.
4. Circular wait: there is a closed chain of processes $P_0, P_1, \dots, P_n$ such that each $P_i$ waits for a resource held by $P_{i+1}$ and $P_n$ waits for one held by $P_0$.

Deadlock is prevented by ensuring at least one of these conditions can never hold. It is avoided using algorithms such as the Banker's algorithm.

Thread. A thread is the basic unit of CPU utilisation, often called a lightweight process. It has its own thread ID, program counter, register set and stack, but shares the code, data and open files of its process with other threads. Multithreading allows several tasks to run concurrently within one process, and creation and switching are cheaper than for processes.

User-level threads (ULT).

• Managed by a thread library in user space, and the kernel is unaware of them.
• Thread creation and switching are fast, with no system call or kernel mode switch.
• Scheduling can be customised per application, and they run on any OS.
• Drawback: if one thread makes a blocking system call, the whole process blocks. They also cannot use multiple processors in parallel.

Kernel-level threads (KLT).

• Managed directly by the operating system kernel, which keeps a thread table.
• The kernel can schedule threads on different CPUs, so they give true parallelism.
• A blocking thread does not block the others in its process.
• Drawback: creation and context switching are slower because they need system calls and kernel involvement.

Many systems combine both with many-to-one, one-to-one or many-to-many mapping models.

In bitmap (bit vector) free-space management, one bit represents each disk block: 1 for free and 0 for allocated (or the reverse).

Disk size $= 2\text{ GB} = 2 \times 2^{30}$ bytes $= 2^{31}$ bytes

Block size $= 2\text{ KB} = 2^{11}$ bytes

$\text{Number of blocks} = \frac{2^{31}}{2^{11}} = 2^{20} = 1{,}048{,}576$

The bitmap needs one bit per block, so it has $2^{20}$ bits.

$\text{Bitmap size} = \frac{2^{20}}{8}\text{ bytes} = 2^{17}\text{ bytes} = 131{,}072\text{ bytes} = 128\text{ KB}$

Result: the bitmap is 128 KB, which occupies $128/2 = 64$ disk blocks.

All processes arrive at time 0 in the order A, B, C, D. Total burst time $= 8 + 9 + 10 + 6 = 33$.

Round Robin (quantum = 3).

Gantt chart:

Completion times: A = 26, B = 29, C = 33, D = 24.

Turnaround time = completion $-$ arrival, and waiting time = turnaround $-$ burst.

Average turnaround $= 112/4 = 28$. Average waiting $= 79/4 = 19.75$.

Priority scheduling (non-preemptive; larger number = higher priority, so D is highest).

Order of execution: D (4), A (3), C (2), B (1).

Gantt chart:

Average turnaround $= 77/4 = 19.25$. Average waiting $= 44/4 = 11$.

An operating system (OS) manages hardware and provides services to programs. Operating systems are classified by how they schedule and serve work.

Types of operating system.

1. Batch OS: similar jobs are collected into batches and run one after another without user interaction. Jobs are submitted (originally on punch cards), and output is returned later. It gives high throughput but long turnaround, no interaction, and the CPU is often idle during I/O. Example: early IBM mainframe systems, payroll processing.
2. Multiprogramming OS: several jobs are kept in memory, and when one waits for I/O the CPU switches to another. This increases CPU utilisation.
3. Time-sharing (multitasking) OS: the CPU is switched rapidly among users or processes using small time slices, so each gets interactive response. Example: UNIX, Linux.
4. Multiprocessor (parallel) OS: several CPUs share memory and I/O under one OS, which gives higher throughput and fault tolerance.
5. Distributed OS: a collection of independent computers connected by a network appears to the user as a single system, sharing resources and load. Example: Amoeba, LOCUS.
6. Network OS: runs on a server and offers shared files, printers and services to client computers, with users aware of the separate machines. Example: Windows Server, Novell NetWare.
7. Real-time OS (RTOS): processes must complete within strict time deadlines. A hard RTOS treats a missed deadline as failure (airbags, pacemakers), while a soft RTOS tolerates occasional misses (multimedia streaming).
8. Embedded and mobile OS: small OSes built into devices, e.g. Android, iOS, FreeRTOS.

Real-time versus batch OS.

Kernel. The kernel is the core component of the operating system. It is loaded at boot, remains in main memory, and executes in privileged (kernel) mode. It controls process management, memory management, file systems, device drivers and I/O, and provides the interface between hardware and user programs.

System call. A system call is the programmatic way in which a user program requests a service from the kernel (such as file open, read, write, fork, exec). It switches the CPU from user mode to kernel mode in a controlled way.

Process of a system call (example: read(fd, buffer, n)):

1. The user program calls the library routine (e.g. read in the C library) as an ordinary function call.
2. The library routine puts the system call number in a register and the parameters in registers (or on the stack, or in a table whose address is passed).
3. The library executes a trap instruction (software interrupt), which switches the CPU from user mode to kernel mode and jumps to a fixed kernel address.
4. The kernel's system call handler uses the call number to index a dispatch table and finds the service routine.
5. The kernel service routine runs and performs the work, e.g. it reads from the device or file into memory.
6. When finished, the kernel stores the result or return code and returns from the trap, switching back to user mode.
7. Control returns to the library routine and then to the user program, which continues after the call.

Diagram.

 User space                         Kernel space
+---------------------+            +-------------------------+
| User program        |            |  System call handler    |
|  read(fd,buf,n) ----+--(1)       |   (dispatch table)      |
|        |            |            |        |                |
|  Library routine    |            |        v                |
|   load call number  |--(2) TRAP->|  Service routine        |
|   & parameters      |            |   (e.g. sys_read)       |
|        ^            |            |        |                |
|        |            |<--(3) return to user mode------------+|
+---------------------+            |  Hardware / devices     |
                                   +-------------------------+

Resource Allocation Graph (RAG). A directed graph used to describe the resource state of a system and detect deadlock.

• Vertices: a set of processes $P=\{P_1,\dots\}$ (circles) and a set of resource types $R=\{R_1,\dots\}$ (rectangles), where dots inside a rectangle represent the instances.
• Request edge $P_i \to R_j$: process $P_i$ is requesting an instance of $R_j$.
• Assignment edge $R_j \to P_i$: an instance of $R_j$ is allocated to $P_i$.

If the graph has no cycle, there is no deadlock. If there is a cycle and each resource has only one instance, there is deadlock. If resources have multiple instances, a cycle indicates only a possible deadlock.

Necessary conditions for deadlock.

1. Mutual exclusion: some resource can be used by only one process at a time.
2. Hold and wait: a process holds a resource while waiting for another.
3. No preemption: resources cannot be forcibly taken away.
4. Circular wait: a cycle of processes exists, each waiting for a resource held by the next.

Banker's algorithm.

Total resources: $A=17,\ B=8,\ C=10$.

Total allocated: $A = 3+3+4+1+2 = 13$, $B = 1+1+1+0+0 = 3$, $C = 1+0+1+1+1 = 4$.

$\text{Available} = (17-13,\ 8-3,\ 10-4) = (4,\ 5,\ 6)$

Safety check: a process can run if Need $\le$ Work. When it finishes it returns its Allocation to Work.

All processes can finish, and the final Work $(17, 8, 10)$ equals the total resources, confirming the calculation.

Safe sequence: $\langle P_2, P_4, P_3, P_1, P_5 \rangle$. The system is in a safe state.

Operating system. An operating system is system software that manages computer hardware and software resources and provides a convenient, efficient interface between the user and the hardware. Its functions include process, memory, file and device management, protection and security.

Three-state process model. A process is, at any moment, in one of three states.

• Ready: the process is in memory and waiting to be assigned the CPU.
• Running: the process's instructions are currently being executed by the CPU.
• Blocked (waiting): the process is waiting for an event, such as I/O completion, before it can continue.

Diagram.

              dispatch (scheduler picks)
        +----------------------------------+
        |                                  v
     +-------+                         +---------+
     | Ready |<------------------------| Running |
     +-------+   timeout / preemption  +---------+
        ^                                  |
        |                                  | wait for event / I/O
        |        +-----------+             |
        +--------|  Blocked  |<------------+
   event occurs  +-----------+
   (I/O complete)

Transitions.

1. Ready to Running: the scheduler dispatches the process to the CPU.
2. Running to Ready: its time quantum expires, or a higher-priority process preempts it.
3. Running to Blocked: it requests I/O or waits for an event.
4. Blocked to Ready: the awaited event occurs.

Race condition. A situation where two or more processes access and manipulate shared data concurrently, and the final result depends on the particular order in which their accesses are interleaved. For example, if two processes both execute counter++ on the same shared variable at once, the final value may be wrong because each reads the old value before the other writes.

Critical section solution using a lock variable. This is a software solution for two or more processes using a shared variable lock, where 0 means the critical section is free and 1 means it is occupied.

int lock = 0;            // shared

do {
    while (lock != 0)    // entry section: wait until free
        ;                // busy wait
    lock = 1;            // take the lock
    /* critical section */
    lock = 0;            // exit section: release the lock
    /* remainder section */
} while (true);

How it works: a process checks the lock. If it is 0, the process sets it to 1 and enters the critical section. Others loop until it is released.

Drawback. The solution does not guarantee mutual exclusion. The test (lock != 0) and the set (lock = 1) are not atomic. If process P0 reads lock = 0 and is pre-empted before setting it to 1, process P1 can also read 0 and set it to 1. Both then enter the critical section together. The race moves into the lock variable itself. It also wastes CPU time through busy waiting.

To fix this, the test and set must be one indivisible hardware instruction (TestAndSet), or semaphores, Peterson's algorithm or mutexes are used.

Memory compaction. Compaction is the technique of shifting all the allocated memory blocks together towards one end of memory so that all the scattered free holes combine into one large contiguous free block. It removes external fragmentation, but it is time-consuming and requires dynamic relocation of processes (run-time address binding).

Best-fit allocation. In dynamic partitioning, the best-fit strategy searches the whole list of free holes and allocates the smallest hole that is large enough for the requesting process. It leaves the smallest leftover and keeps large holes available, but it needs a full search (unless the list is sorted by size) and tends to leave many tiny, unusable fragments.

Example. Free holes in memory, in order: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Processes arrive: 212 KB, 417 KB, 112 KB, 426 KB.

All four processes are placed. Holes left: 100, 83, 88, 88 and 174 KB (these are in different places). First fit, by comparison, would have left P4 (426 KB) unplaced in this example, since P1 would have taken the 500 KB hole and P2 the 600 KB hole, leaving no hole of 426 KB.

RAID (Redundant Array of Independent Disks). A technology that combines several physical disks into one logical unit to improve performance (by striping data across disks), reliability (by redundancy such as mirroring or parity), or both. Different RAID levels (0 to 6) offer different trade-offs among capacity, speed and fault tolerance.

RAID Level 2 (bit-level striping with Hamming-code error correction).

• Data is striped at the bit level across the data disks, and the check bits of a Hamming error-correcting code (ECC) are stored on additional dedicated disks.
• Example: with 4 data disks, 3 ECC disks are needed.
• On a read, the ECC is checked and any single-bit error can be corrected, and on disk failure the lost bits are rebuilt from the code.
• All disks are accessed in parallel and kept in synchronised rotation, giving high transfer rate for large sequential transfers.
• Drawback: it requires many extra disks, so it is expensive, and it is rarely used today since modern disks already include their own error detection.

RAID Level 3 (byte-level striping with a dedicated parity disk).

• Data is striped at the byte (or bit) level across several data disks, and one dedicated disk stores the parity (XOR) of the corresponding bytes.
• Because the disk controller can identify the failed disk, a single parity disk is enough to reconstruct the lost data (XOR of the remaining disks and parity).
• Overhead is just one extra disk, so it is cheaper than RAID 2, and it has high throughput for large transfers.
• Drawbacks: every I/O touches all disks (poor for many small random requests), and the single parity disk is a bottleneck. It tolerates only one disk failure.

Threads versus processes.

User-level threads. They are created and scheduled by a thread library in user space, and the kernel sees only one process. Switching is fast and needs no system call, and they can run on any OS with custom scheduling. However, a blocking system call by one thread blocks the whole process, and they cannot run in parallel on multiple CPUs.

Kernel-level threads. They are supported and scheduled directly by the kernel, which keeps a thread table. The kernel can schedule different threads of a process on different processors, and one blocked thread does not block the others. However, creation and switching are slower since they involve the kernel and system calls.

Reference string: 3, 2, 1, 3, 4, 2, 8, 9, 7, 4, 2, 9, 8, 3 with 4 frames (F = fault, H = hit).

Optimal (replace the page whose next use is farthest in the future)

• At 8, frames {3,2,1,4}: 1 is never used again, so 1 is replaced. At 9, 7 and later, pages with the farthest next use (3, then 8/2) are replaced.
• Page faults (Optimal) = 9

LRU (replace the least recently used page)

• Page faults (LRU) = 11

So Optimal gives 9 faults and LRU gives 11 faults.

TLB (Translation Lookaside Buffer) is a small, very fast associative cache inside the MMU that stores recently used page-number to frame-number mappings from the page table.

Working in address translation

1. The CPU generates a logical address = (page number $p$, offset $d$).
2. $p$ is looked up in the TLB, in parallel for all entries.
3. TLB hit: the frame number $f$ is obtained immediately; the physical address is $(f, d)$.
4. TLB miss: the page table in main memory is consulted (one extra memory access), the frame number is obtained and the entry is loaded into the TLB (replacing an old entry if full).

Importance

• Without a TLB every memory reference needs two accesses (one for the page table, one for the data), which halves speed.
• Because of locality of reference, hit ratios are typically 90-99%, so the effective access time is close to a single memory access: $EAT = h\,(t_{TLB}+t_{mem}) + (1-h)\,(t_{TLB}+2\,t_{mem})$
• For example, with $t_{TLB}=20$ ns, $t_{mem}=100$ ns and $h=0.9$: $EAT = 0.9(120)+0.1(220)=130$ ns, instead of 200 ns.
• Entries may carry address-space IDs so the TLB need not be flushed on every context switch.

In a FAT file system the table has one entry per disk block.

Number of blocks

$\text{Blocks} = \frac{500\ \text{GB}}{5\ \text{KB}} = \frac{500 \times 2^{30}}{5 \times 2^{10}} = 100 \times 2^{20} = 104{,}857{,}600$

FAT size

$\text{FAT size} = 104{,}857{,}600 \times 4\ \text{B} = 419{,}430{,}400\ \text{B} = 400\ \text{MB}$

So the file allocation table needs 400 MB (about 1.05 x 10^8 entries).

Direct Memory Access (DMA) lets an I/O device transfer a block of data to or from main memory without the CPU copying each byte. A special DMA controller does the transfer.

Working mechanism

1. The CPU programs the DMA controller registers: the memory address, the byte count, the direction (read/write) and the device. This is done by the device driver.
2. The controller asks the device (disk controller) to read a block into its internal buffer.
3. The DMA controller requests the bus and transfers the data directly to/from memory (using cycle stealing, burst, or transparent mode), incrementing the address and decrementing the count after each transfer.
4. When the count reaches zero, the DMA controller sends an interrupt to the CPU.
5. The CPU runs the interrupt handler, which marks the transfer complete.

Advantages: the CPU is interrupted once per block instead of once per byte or word, so it is free to run other processes during the transfer, and bulk transfer is faster.

Why virtual memory is used

• It lets a program larger than physical memory run, because only the needed pages are kept in RAM and the rest stays on disk.
• More processes can be in memory at once, which raises CPU utilization and multiprogramming.
• Each process gets its own large, uniform address space, which gives protection and simplifies programming (no overlays).
• Pages are loaded on demand, so less I/O is needed at start-up. Sharing of pages is also possible.

Logical address

A logical (virtual) address is the address generated by the CPU for a process. It is divided into a page number $p$ and a page offset $d$. For a logical space of $2^m$ with page size $2^n$, the high $m-n$ bits give $p$ and the low $n$ bits give $d$. It is translated by the MMU to a physical address at run time.

Translation using a TLB

1. The CPU issues the logical address $(p, d)$.
2. The MMU searches the TLB (a fast associative cache of page-table entries) for $p$.
3. TLB hit: the frame number $f$ is read directly.
4. TLB miss: the page table is read from memory using $p$. If the valid bit is 1, $f$ is obtained and the entry is copied into the TLB. If the valid bit is 0, a page fault occurs: the OS finds the page on disk, loads it into a free frame (replacing a page if needed), updates the page table and restarts the instruction.
5. The physical address is $f \times \text{page size} + d$.

With hit ratio $h$, $EAT = h(t_{TLB}+t_{mem}) + (1-h)(t_{TLB}+2t_{mem})$, so a high hit ratio makes the cost of paging small.

Why Optimal is the best but impractical

Optimal (OPT/MIN) replaces the page that will not be used for the longest time in the future. It gives the lowest possible number of page faults for any reference string and never suffers Belady's anomaly, so it is the benchmark for other algorithms. It is impractical because it requires knowledge of the future reference string, which the OS cannot know in advance. It is used only for comparison.

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

Page faults

• Optimal = 10
• LRU = 14
• FIFO = 14

Gantt charts and results (turnaround = completion - arrival; waiting = turnaround - burst)

FIFO (FCFS): P1(0-8), P2(8-13), P3(13-23), P4(23-36), P5(36-53)

Average TAT = $127/5 = 25.4$ ms; average WT = $74/5 = 14.8$ ms.

SRTF (preemptive SJF): P1(0-1), P2(1-6), P1(6-13), P3(13-23), P4(23-36), P5(36-53)

At $t=1$, P2 (5) is shorter than the remaining 7 of P1, so P2 preempts. After that the order is by remaining time.

Average TAT = $125/5 = 25.0$ ms; average WT = $72/5 = 14.4$ ms.

Round Robin (q = 4)

P1(0-4), P2(4-8), P3(8-12), P4(12-16), P5(16-20), P1(20-24), P2(24-25), P3(25-29), P4(29-33), P5(33-37), P3(37-39), P4(39-43), P5(43-47), P4(47-48), P5(48-52), P5(52-53)

Average TAT = $183/5 = 36.6$ ms; average WT = $130/5 = 26.0$ ms.

Summary

Number of blocks

$\frac{2\ \text{GB}}{4\ \text{KB}} = \frac{2^{31}}{2^{12}} = 2^{19} = 524{,}288$

FAT size

$2^{19} \times 4\ \text{B} = 2^{21}\ \text{B} = 2\ \text{MB}$

The file allocation table is 2 MB.

Coalescing merges adjacent free blocks (holes) into one larger free block. It is done when a block is freed and its neighbour is also free. Nothing is moved.

Before:  | Used A | Free 10K | Free 20K | Used B |
After:   | Used A |     Free 30K       | Used B |

Compaction moves the allocated processes together toward one end of memory, so that all the scattered free holes combine into one large contiguous block. It needs relocation (dynamic binding) and takes CPU time because memory is copied.

Before:  | OS | P1 | hole 5K | P2 | hole 8K | P3 | hole 4K |
After:   | OS | P1 | P2 | P3 |        hole 17K            |

Head starts at cylinder 143; queue: 25, 17, 119, 197, 194, 15, 182, 115, 183.

(a) FCFS (service in arrival order)

143 -> 25 -> 17 -> 119 -> 197 -> 194 -> 15 -> 182 -> 115 -> 183

$118 + 8 + 102 + 78 + 3 + 179 + 167 + 67 + 68 = 790$

Total head movement = 790 cylinders.

(b) SSTF (go to the nearest request each time)

Order: 143 -> 119 -> 115 -> 182 -> 183 -> 194 -> 197 -> 25 -> 17 -> 15

$24 + 4 + 67 + 1 + 11 + 3 + 172 + 8 + 2 = 292$

Total head movement = 292 cylinders.

Process: a program in execution. It is an active entity that includes the program code, the program counter, registers, stack, data section and heap, and it is the unit of work and resource allocation in the OS.

Three-state process model

          admit/dispatch
   Ready ------------------> Running
     ^  <------------------     |
     |      time-out/preempt    |
     |                          | event wait (I/O)
     |      event occurs        v
     +------------------- Blocked (Waiting)

• Running: the process is currently executing on the CPU.
• Ready: the process has everything it needs and waits in the ready queue for the CPU.
• Blocked (waiting): the process waits for an event such as I/O completion and cannot run even if the CPU is free.

Transitions

1. Ready -> Running: the scheduler dispatches the process.
2. Running -> Ready: time slice expires or a higher priority process arrives (preemption).
3. Running -> Blocked: the process requests I/O or waits for an event.
4. Blocked -> Ready: the awaited event occurs.

Memory-mapped I/O

The registers and data buffers of a device controller are mapped into the same address space as main memory. Each control register is assigned a unique memory address, so the CPU reads and writes the device with ordinary load/store instructions (e.g. MOV) without special I/O instructions.

• Advantages: no special I/O instructions; device drivers can be written in C; protection is done through page tables; any memory instruction can test the device.
• Disadvantages: part of the address space is used; caching of device registers must be disabled; a single bus is needed for memory and I/O.

Device-independent I/O software

This layer of the OS performs functions common to all devices and gives a uniform interface to the user and drivers:

• Uniform interfacing for device drivers.
• Buffering of data between device and process.
• Error reporting to higher layers.
• Allocating and releasing dedicated devices (e.g. printer).
• Providing a device-independent block size and naming/protection of devices.

User programs say "read from file" and need not know the type of device.

Deadlock vs starvation

Deadlock detection with multiple resources of each type

Let $n$ = processes, $m$ = resource classes. Data structures:

• $E$ (existing), $A$ (available) vectors of length $m$
• $C$ ($n\times m$): current allocation matrix
• $R$ ($n\times m$): request matrix

Algorithm:

1. Mark all processes as unmarked.
2. Find an unmarked process $P_i$ whose row of $R$ is $\le A$ (can be satisfied).
3. If found, add row $C_i$ to $A$ (it finishes and releases its resources), mark $P_i$, and repeat step 2.
4. If no such process exists, stop. Any process still unmarked is deadlocked.

The algorithm is run periodically or when CPU utilization drops. Recovery: preemption, rollback, or killing processes.

Process vs program

Process Control Block (PCB)

The PCB is the data structure the OS keeps for each process, and it represents the process in the OS. It contains:

• Process ID (PID) and parent ID
• Process state (ready, running, blocked)
• Program counter and CPU registers (saved on a context switch)
• CPU scheduling information (priority, queue pointers)
• Memory management information (page tables, base/limit)
• Accounting information (CPU time used)
• I/O status information (open files, devices allocated)

In message passing, processes communicate using two primitives, send(destination, message) and receive(source, message), and no shared memory or semaphore is needed. The OS provides mutual exclusion on the message queue. To avoid overflow, the buffer is limited to $N$ messages: the consumer first sends $N$ empty messages to the producer.

#define N 100                      /* number of slots */

void producer(void) {
    int item; message m;
    while (TRUE) {
        item = produce_item();
        receive(consumer, &m);     /* wait for an empty message */
        build_message(&m, item);   /* put item in message */
        send(consumer, &m);        /* send item to consumer */
    }
}

void consumer(void) {
    int item, i; message m;
    for (i = 0; i < N; i++) send(producer, &m);   /* send N empties */
    while (TRUE) {
        receive(producer, &m);     /* get message containing item */
        item = extract_item(&m);
        send(producer, &m);        /* send back empty reply */
        consume_item(item);
    }
}

How it works

• The producer blocks in receive if no empty message is available, which means the buffer is full.
• The consumer blocks in receive if no filled message exists, which means the buffer is empty.
• The total number of messages is always $N$, so the buffer cannot overflow and no race condition occurs.

System call: the programming interface through which a user program requests a service from the operating system kernel (e.g. file creation, process control, I/O). It switches the CPU from user mode to kernel mode.

Steps in a system call (e.g. read(fd, buffer, nbytes))

1. The user program pushes the parameters (fd, buffer, nbytes) on the stack, or into registers.
2. It calls the library procedure read.
3. The library procedure puts the system-call number in a register.
4. It executes a TRAP instruction, switching to kernel mode and jumping to a fixed address in the kernel.
5. The kernel's dispatcher uses the system call number to index the system call table and finds the handler.
6. The handler runs and performs the requested work (it may block the process and call the scheduler).
7. When finished, control returns to the library procedure (return from trap, back to user mode).
8. The library procedure returns to the user program, which removes the parameters from the stack and continues.

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

User thread vs kernel thread

Scheduling (turnaround = completion - arrival; waiting = turnaround - burst)

FCFS by arrival: C(0-1), B(1-12), A(12-21), D(21-23), E(23-30)

Average TAT = $77/5 = 15.4$; average WT = $47/5 = 9.4$.

Round Robin (q = 2)

Ready queue order: C at 0; B at 1; A at 2; D at 3; E at 4.

Gantt: C(0-1), B(1-3), A(3-5), D(5-7), B(7-9), E(9-11), A(11-13), B(13-15), E(15-17), A(17-19), B(19-21), E(21-23), A(23-25), B(25-27), E(27-28), A(28-29), B(29-30)

Average TAT = $85/5 = 17.0$; average WT = $55/5 = 11.0$.

When does a page fault occur?

A page fault occurs when a process references a page that is not currently in main memory (its valid/present bit in the page table is 0). The hardware traps to the OS, which locates the page on disk, loads it into a free frame (or replaces a victim page), updates the page table and restarts the instruction.

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 frames (F = fault, H = hit).

Explanation

• First four references fill the frames {7,0,1,2}.
• At 3: Optimal evicts 7 (never used again); FIFO evicts 7 (oldest); Second Chance gives 0 a second chance (its reference bit was set by the hit), clears bits, then evicts 7.
• At 4: Optimal evicts 1 (never used again) giving {0,3,4,2}; FIFO evicts 0 (now oldest) giving {1,2,3,4}; Second Chance evicts 1, giving {0,3,4,2}.
• Later: FIFO faults on 0 (evicts 1), then everything is present. Optimal and Second Chance hold {0,2,3,4} and have only hits.

Number of page faults

• Optimal = 6
• FIFO = 7
• Second Chance = 6

Device controller

An I/O device has a mechanical part and an electronic part. The electronic part is the device controller (adapter card). It converts the serial bit stream from the device into a block of bytes, does error correction, and makes the block available in its local buffer and registers (control, status, data). The OS talks only to the controller, through its driver, by writing commands to its registers.

Memory-mapped I/O

The registers and buffers of every controller are mapped into the normal address space, each with a unique address. The CPU accesses them with ordinary load/store (MOV) instructions, so no special I/O instructions or separate I/O space are needed. Drivers can be written in a high-level language and protection is done with the memory protection mechanism. The drawbacks are that caching of device registers must be disabled and part of the address space is consumed.

Interrupt-based I/O vs DMA-based I/O

System call: the interface between a running user program and the operating system. It is a request made through a controlled entry (TRAP) that changes the CPU from user mode to kernel mode so that the OS performs a privileged service, for example fork(), open(), read(), write(), exit().

Objectives

• Provide a service interface to the OS for user programs (process control, file management, device management, information and communication).
• Protection and security: user programs cannot execute privileged instructions directly; the kernel validates every request.
• Hardware abstraction: programs use a uniform interface without knowing the details of hardware.
• Resource management: allow controlled and fair access to CPU, memory, files and devices.
• Portability and simplicity: programmers use library wrappers such as the POSIX API, hiding mode switching.

An operating system consists of the following main components.

• Process management: creating and deleting processes, scheduling, synchronization, inter-process communication and deadlock handling.
• Main memory management: keeps track of which memory is used by whom, allocates and de-allocates memory, and handles paging, segmentation and virtual memory.
• File management: creating, deleting, reading and writing files and directories, access control, and mapping files to secondary storage.
• I/O system management: device drivers, buffering, caching and spooling for a uniform interface to devices.
• Secondary storage (disk) management: free-space management, storage allocation and disk scheduling.
• Protection and security: controls access of processes and users to resources.
• Networking: supports communication between computers in a distributed system.
• Command interpreter (shell): the interface between the user and the OS, which accepts and executes commands.

Banker's algorithm is a deadlock avoidance algorithm. It grants a resource request only if the system stays in a safe state afterwards, that is, if there exists some order in which all processes can run to completion.

Data structures ($n$ processes, $m$ resource types)

• $Available[m]$: free units of each resource
• $Max[n][m]$: maximum demand of each process
• $Allocation[n][m]$: currently allocated
• $Need[n][m] = Max - Allocation$

Safety algorithm

1. $Work = Available$; $Finish[i]=false$ for all $i$.
2. Find $i$ with $Finish[i]=false$ and $Need_i \le Work$. If none, go to step 4.
3. $Work = Work + Allocation_i$; $Finish[i]=true$; go to step 2.
4. If all $Finish[i]$ are true, the state is safe; otherwise it is unsafe.

Resource-request algorithm (process $P_i$ requests $Request_i$)

1. If $Request_i > Need_i$, raise an error (it exceeded its maximum claim).
2. If $Request_i > Available$, $P_i$ must wait.
3. Pretend to allocate: $Available -= Request_i$; $Allocation_i += Request_i$; $Need_i -= Request_i$.
4. Run the safety algorithm. If safe, the allocation is made; otherwise the old state is restored and $P_i$ waits.

It requires that maximum needs are declared in advance and that the number of processes is fixed.

Segmentation and paging each have a weakness, and combining them removes both.

• Pure segmentation matches the programmer's view (code, data, stack), and supports sharing and protection per segment, but segments have variable size, so it suffers from external fragmentation and needs the whole segment to be contiguous.
• Pure paging removes external fragmentation, but it has no logical view of the program, and protection and sharing are less natural.

Segmentation with paging

The logical address is $(s, d)$. Each segment has its own page table: the segment table entry gives the base of that page table. The offset $d$ is split into page number $p$ and page offset $w$. Address translation: segment table -> page table of the segment -> frame -> physical address.

Advantages

• Keeps the logical view, sharing and protection of segmentation.
• A segment need not be contiguous in memory, so external fragmentation is eliminated (only small internal fragmentation in the last page).
• Segments can be larger than free contiguous memory, and only needed pages need to be in memory (virtual memory).
• Allocation is easy because all frames are the same size.

The drawback is extra table space and an extra memory reference, which is reduced with a TLB. Intel x86 and MULTICS use this scheme.

Formatting

A new disk is a blank magnetic surface and must be formatted before use.

• Low-level (physical) formatting: divides the disk into sectors. Each sector gets a header (sector number, cylinder number), a data area (typically 512 bytes or 4 KB) and a trailer containing an error-correcting code (ECC). It is usually done at the factory.
• Partitioning: the disk is divided into one or more groups of cylinders, each treated as a separate logical disk.
• Logical formatting: the OS creates a file system on a partition: boot block, free-space structures, root directory and empty file system data structures.
• The boot block (bootstrap loader) is stored in the first sector or in the boot partition.

Error handling (bad blocks)

Disks have defects, so some sectors become bad.

• Manual handling: during formatting, bad sectors are marked in the FAT or a bad-block list, so they are never allocated (e.g. chkdsk).
• Sector sparing (forwarding): the controller keeps spare sectors; a bad sector is remapped logically to a spare.
• Sector slipping: sectors are shifted so that the spare sector comes next to the bad one.
• ECC detects and corrects small errors during reading; if the error is not correctable, a "soft error" is reported to the OS.
• Each read is checked with the stored ECC, and a parity or checksum is used to detect errors; unrecoverable errors cause the controller to report an I/O error.

File system

A file system is the part of the OS that stores, organizes, names, retrieves and protects files on secondary storage. A file is a named collection of related information. The file system provides operations such as create, delete, open, close, read, write and seek, and attributes like name, type, size, location, protection and time stamps.

Layers of implementation: application programs -> logical file system (metadata, directory, FCB) -> file organization module (logical to physical block mapping, free-space management) -> basic file system -> I/O control (device drivers) -> devices.

On-disk structures: boot control block, volume control block (superblock), directory structure and per-file File Control Block (inode).

Allocation methods: contiguous, linked (FAT), indexed (inode with direct and indirect blocks).

Directory system implementation

A directory maps file names to the file's attributes and disk location.

• Linear list: a list of (file name, pointer to data blocks); simple but searching is $O(n)$.
• Hash table: a hash of the file name gives the entry; fast lookup, but collisions and fixed size are issues.

In MS-DOS the directory entry holds the name, attributes and the first block number (then chain through FAT). In UNIX the directory entry holds only the file name and the i-node number, and attributes are in the inode.

Directory structures: single-level, two-level, tree-structured and acyclic-graph directories (shared files through links).

Interrupt: a signal sent to the CPU by hardware (an I/O device) or software (a trap) that requests immediate attention. The CPU suspends the current program, saves its state, runs the interrupt service routine (handler) found through the interrupt vector, and then resumes the interrupted program.

Device controller

The device controller is the electronic component of an I/O device that works as the interface between the device and the system bus. It has:

• registers (control, status and data) that the CPU reads and writes through the driver,
• a local data buffer to hold a block of data,
• logic to convert the serial bit stream from the device into bytes and perform error checking/correction.

The OS communicates only with the controller (through the device driver); the controller operates the actual device and signals completion by raising an interrupt.

Virtual machine: a software abstraction that makes one physical computer appear as several separate, complete computers. A virtual machine monitor (hypervisor) multiplexes the hardware among guest operating systems, each running in its own VM with the illusion of its own CPU, memory and disk. Examples are VMware, VirtualBox and the JVM (process VM). It lets different OSes run on one machine, isolates systems, and allows safe testing.

System protection

Protection controls access of programs, processes and users to the resources defined by the system, so that one user cannot interfere with another or with the OS.

• Dual-mode operation: user mode and kernel mode; privileged instructions run only in kernel mode.
• Memory protection: base and limit registers (or page tables) restrict each process to its own address space.
• CPU protection: a timer prevents a process from holding the CPU forever.
• I/O protection: all I/O instructions are privileged and done through system calls.
• Access control: a protection domain defines (object, rights) pairs, implemented with an access matrix, access control lists or capability lists.

P1 = 6 ms, P2 = 4 ms, P3 = 5 ms, all arriving at 0 (turnaround = completion time).

FCFS: P1(0-6), P2(6-10), P3(10-15)

$\text{Avg TAT} = \frac{6+10+15}{3} = \frac{31}{3} = 10.33\ \text{ms}$

SJF (non-preemptive): P2(0-4), P3(4-9), P1(9-15)

$\text{Avg TAT} = \frac{4+9+15}{3} = \frac{28}{3} = 9.33\ \text{ms}$

Round Robin (q = 2):

P1(0-2), P2(2-4), P3(4-6), P1(6-8), P2(8-10), P3(10-12), P1(12-14), P3(14-15)

Completion times: P1 = 14, P2 = 10, P3 = 15.

$\text{Avg TAT} = \frac{14+10+15}{3} = \frac{39}{3} = 13\ \text{ms}$

Reference string: 0, 1, 7, 2, 3, 2, 7, 1, 0, 3 with 4 initially empty frames (F = fault, H = hit).

FIFO

At 3, the oldest page 0 is replaced. At 0, the oldest page 1 is replaced.

Page faults (FIFO) = 6

LRU

• At 3: LRU page is 0, replaced -> {1,7,2,3}.
• 2, 7, 1 are hits; recency order (old to new) becomes 3, 2, 7, 1.
• At 0: replace 3 (least recently used) -> {0,1,7,2}.
• At 3: replace 2 (LRU) -> a fault.

Page faults (LRU) = 7

Advantages of DMA

• Frees the CPU: the CPU only starts the transfer and is free to run other processes while the DMA controller moves the data.
• Fewer interrupts: one interrupt per block rather than one per byte or word.
• Higher transfer speed: data goes directly between device and memory at bus speed, which suits fast devices such as disks and network cards.
• Better system throughput and CPU utilization.
• Efficient bulk transfer of large blocks of data, with lower overhead than programmed or interrupt-driven I/O.

Structure of a disk

A magnetic disk consists of one or more circular platters coated with magnetic material, stacked on a spindle that rotates at constant speed (e.g. 7200 rpm).

• Each platter surface has a read/write head on a movable arm assembly.
• Each surface is divided into concentric tracks, and tracks are divided into sectors (the smallest unit, e.g. 512 B or 4 KB).
• The set of tracks at the same arm position on all surfaces forms a cylinder.
• A disk address is (cylinder, head, sector) or a logical block number.

Access time = seek time (moving the arm to the cylinder) + rotational latency (waiting for the sector to come under the head) + transfer time.

Time sharing is needed because it gives interactive, responsive computing to many users at the same time on one computer.

• The CPU is allocated to each process for a short time slice (quantum) in round-robin fashion, and the switching is so fast that every user feels the machine is theirs alone.
• It gives a short response time, which is essential for interactive work such as editing, compiling and debugging.
• It improves CPU utilization, because when one process waits for I/O the CPU runs another.
• It lets many users share an expensive computer economically.
• It avoids the long turnaround time and lack of interaction in batch systems; short jobs are not blocked behind long ones.
• It supports multiprogramming, memory protection and virtual memory so that many programs can be in memory together.

UNIX and Linux are examples.

Address space: the set of addresses that a process can use to address memory. The logical (virtual) address space is the set of addresses generated by the CPU for the process (e.g. 0 to max), while the physical address space is the set of actual addresses of the memory hardware. Each process has its own address space, which gives protection.

Limitations of batch systems

• No user interaction: the user cannot interact with the job while it runs, so debugging is difficult.
• Long turnaround time: jobs wait until the whole batch is processed.
• CPU idle time: the CPU sits idle during slow I/O because only one job runs at a time.
• Poor resource utilization: no multiprogramming, so memory and devices are under-used.
• Starvation/delay: a long job delays all the short jobs after it.
• Limited protection: an error in one job may affect following jobs.

A separate kernel stack for each process is used when control moves from user mode to kernel mode (interrupt, trap or system call), for the following reasons.

• Security: the user stack is under the control of the user program. A malicious program could set its stack pointer to an invalid or kernel address, and the kernel writing there (saving registers, return address) would corrupt kernel memory or leak data. Kernel data on a user stack could also be read or modified by the user.
• Reliability: the user stack pointer may be invalid or the stack may have no space left (overflow), and a fault in the handler on that stack could crash the system.
• Isolation: the kernel code and its saved state must not be visible or modifiable by user code, and it keeps the kernel's data trusted.
• Correct context switch: the trap frame (saved registers, program counter) for each process is kept on its own kernel stack, so the process can be blocked in the kernel and resumed later without being overwritten.

A file system is implemented with several on-disk and in-memory structures arranged in layers.

On-disk structures

• Boot control block: information needed to boot an OS from the volume.
• Volume control block (superblock): number of blocks, block size, free-block count and pointers.
• Directory structure: maps file names to files (name -> inode or first block).
• File control block (inode): permissions, owner, size, time stamps and the data block pointers.

In-memory structures: mount table, system-wide open-file table, per-process open-file table, and directory cache.

Creating and opening a file: a new FCB is allocated, the directory is updated, and open() searches the directory and copies the FCB into the open-file table, returning a file descriptor.

Allocation of disk blocks

• Contiguous: fast access but external fragmentation.
• Linked / FAT: each block points to the next, no external fragmentation, but direct access is slow (improved by FAT).
• Indexed (inode): an index block holds all block pointers; supports direct access, and UNIX uses direct, single, double and triple indirect pointers.

Free-space management: bitmap, linked list, grouping and counting.

Directory implementation: linear list or hash table.

Layers: application -> logical file system -> file-organization module -> basic file system -> I/O control (device drivers) -> device.

Can a clock interrupt preempt a thread?

Yes for kernel-level threads: the kernel's clock interrupt can preempt the running thread when its time quantum expires and schedule another one. For user-level threads the answer depends: the clock interrupt can preempt the process (the whole process is given up), but the kernel does not know about the individual threads, so it cannot switch from one user thread to another. The thread library can use its own timer only if it has asked for run-time clock signals; otherwise a thread runs until it voluntarily yields.

Biggest advantage of user-space threads

They are fast and efficient: thread creation, switching and scheduling are done by a library procedure in user space without a system call or a kernel trap, so no mode switch and no kernel involvement is needed. Also, they can be implemented on an OS that does not support threads and each process can have its own scheduling algorithm.

Internal fragmentation: memory wasted inside an allocated block or partition because the block given is larger than the request. The unused part cannot be given to anyone else. Example: a process of 18 KB is given a fixed 20 KB partition (or a 4 KB page frame is only partly used), wasting 2 KB inside.

External fragmentation: total free memory is enough to satisfy a request, but it is split into many small non-contiguous holes outside the allocated blocks, so the request cannot be met. Example: holes of 5 KB, 8 KB and 4 KB cannot hold a 15 KB process. It can be solved by compaction.

Which occurs in paging? Internal fragmentation occurs, in the last page of each process (on average half a page). There is no external fragmentation because any free frame can be used.

SSTF (Shortest Seek Time First) disk scheduling: the request closest to the current head position (smallest seek distance) is served next.

Working

1. Note the current head position.
2. Among the pending requests, compute the seek distance to each.
3. Move to the nearest cylinder and serve it; it becomes the new head position.
4. Repeat until the queue is empty.

Example: head at 53; queue: 98, 183, 37, 122, 14, 124, 65, 67 (cylinders 0-199).

Order: 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

$12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236$

Total head movement = 236 cylinders (FCFS needs 640 for the same queue).

SSTF gives a lower average seek time than FCFS, but it may cause starvation of requests far from the head and it is not optimal.

In programmed (polling) I/O the CPU repeatedly tests the device status register in a busy-wait loop until the device is ready, which wastes a lot of CPU time because devices are far slower than the processor.

Interrupt-driven I/O is needed because:

• The CPU starts the I/O operation and then continues running other processes. The device sends an interrupt when it is ready or finished, so no busy waiting.
• It gives better CPU utilization and throughput, which is vital in multiprogramming.
• It allows quick response to asynchronous events such as keyboard input, network packets or timer expiry.
• It supports priorities among devices, so urgent events are handled first.
• Overhead is proportional to the number of events and not to the device's slow speed.

Working: process issues I/O -> driver starts the device and the process blocks -> CPU runs another process -> device raises interrupt -> handler saves state, services the device, wakes the process -> the scheduler resumes it.

No, deadlock is not possible.

Let each of the two processes need a maximum of 2 resources, and there are 3 identical resources in total.

Reasoning

Deadlock needs every process to be holding some resources while waiting for more, with no free resource left. The worst case is when each process holds $1$ resource and each needs one more:

$\text{Resources held} = 1 + 1 = 2 < 3$

So one resource is still free. Either process can take it, which gives it its maximum of 2, so it completes and releases its resources, and the other can then also get what it needs.

In general, deadlock is impossible if

$R \ge \sum_{i}(m_i - 1) + 1 = (2-1)+(2-1)+1 = 3$

and here $R = 3$ so the condition is satisfied. A circular wait cannot occur, and the system is always in a safe state.