Operating System

A system call is the programmatic interface through which a user program requests a service from the operating system kernel (such as file, process or memory operations), switching from user mode to kernel mode. Examples: open(), read(), fork().

The main types of kernels are: monolithic kernel, microkernel, hybrid kernel, exokernel and nanokernel.

The Process Control Block (PCB) stores all the information about a process that the OS needs to manage it, such as process ID, state, program counter, CPU registers, scheduling information, memory management information and open files, so that the process can be suspended and resumed correctly (context switching).

A race condition occurs when two or more processes or threads access and modify shared data concurrently and the final result depends on the order (timing) in which they execute, leading to incorrect or unpredictable results. It is prevented by synchronization (locks, semaphores, mutexes).

A resource allocation graph is a directed graph used to describe deadlocks. Vertices are processes and resources; a request edge $P_i \rightarrow R_j$ shows a process waiting for a resource, and an assignment edge $R_j \rightarrow P_i$ shows the resource is allocated to the process. A cycle indicates a possible deadlock (a certain one if every resource has a single instance).

In variable (dynamic) partitioning, memory is not divided in advance; each process is given a partition of exactly the size it needs when it is loaded. This removes internal fragmentation but causes external fragmentation over time, which can be reduced by compaction or by placement strategies (first-fit, best-fit, worst-fit).

Paging is a memory-management technique in which the logical address space is divided into fixed-size blocks called pages and physical memory into frames of the same size. Pages are mapped to frames through a page table, so a process need not occupy contiguous memory. In virtual memory (demand paging) only the needed pages are loaded into memory, and a page fault brings others in from disk when required. This removes external fragmentation.

The file system organizes, stores, names, retrieves and protects data on secondary storage in the form of files and directories. It manages free space, allocation of disk blocks, access control and file operations (create, read, write, delete).

OS security is needed to protect the system's resources (data, files, memory, CPU) from unauthorized access, malware, viruses and attacks, to ensure confidentiality, integrity and availability, and to make sure that users and processes cannot interfere with each other.

A distributed operating system lets many networked computers work together as a single system, so it gives better resource sharing, higher reliability and fault tolerance (no single point of failure), faster computation through parallel processing, and easy scalability compared with a centralized system.

A semaphore is an integer variable accessed only through the atomic operations wait(S) and signal(S). If the operating system can disable interrupts, it makes these operations atomic by running each of them with interrupts turned off.

• wait(S): disable interrupts; if $S > 0$, decrement $S$; otherwise put the calling process in the semaphore's waiting queue and block it (call the scheduler); then enable interrupts.
• signal(S): disable interrupts; if some process is waiting in the queue, remove one and move it to the ready queue; otherwise increment $S$; then enable interrupts.

With interrupts disabled, no context switch can occur, so no other process can interleave with the test-and-update of $S$. This works well on a single processor. On a multiprocessor, disabling interrupts on one CPU does not stop the others, so spinlocks or atomic instructions are also needed.

In preemptive scheduling the CPU can be taken away from a running process (for example on a time-slice expiry or when a higher-priority process arrives). In non-preemptive scheduling a process keeps the CPU until it terminates or blocks for I/O.

Preemptive scheduling (Round Robin, SRTF, preemptive priority)

• Advantages: good response time for interactive systems; no process can monopolise the CPU; important or short jobs get the CPU quickly.
• Disadvantages: context-switch overhead; needs shared data to be protected from race conditions; more complex to implement.

Non-preemptive scheduling (FCFS, SJF, non-preemptive priority)

• Advantages: simple; low overhead because context switches are few; no race conditions from sudden preemption.
• Disadvantages: a long job can make others wait (convoy effect); poor response time; a high-priority process may have to wait; unsuitable for real-time and time-sharing systems.

• Logical (virtual) address: the address generated by the CPU while a program runs. The set of all logical addresses is the logical address space. The program sees it starting from 0.
• Physical address: the actual address of a location in main memory, seen by the memory unit. The set of all physical addresses is the physical address space.

The Memory Management Unit (MMU) maps logical to physical addresses at run time. With a relocation register, for example:

$\text{Physical address} = \text{Logical address} + \text{Relocation (base) register}$

If the base is 14000 and the logical address is 346, the physical address is 14346.

Logical addresses are used by the user program and are not directly visible in memory. Physical addresses are used by the hardware. The two are the same only in compile-time and load-time binding. They differ in execution-time binding, which allows relocation, protection and virtual memory.

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. This avoids the overhead of programmed I/O for large transfers.

Steps of a DMA transfer (for example a disk read):

1. The CPU programs the DMA controller with the memory address, the byte count and the direction (read or write) and the device.
2. The DMA controller asks the device to transfer data and handles the data transfer to memory.
3. The DMA controller gains control of the bus (cycle stealing or burst mode), puts the memory address on the bus and writes each word, increments the address and decrements the count.
4. When the count reaches zero, the DMA controller sends an interrupt to the CPU to signal that the transfer is complete.

The CPU is free to run other processes during steps 2-3, and is interrupted only once per block instead of once per byte.

A critical section is the part of a process's code where it accesses shared resources (shared variables, files, tables) that must not be accessed by more than one process at the same time. Concurrent access can cause a race condition, where the result depends on the order of execution.

A solution must satisfy three requirements:

1. Mutual exclusion: only one process is in its critical section at a time.
2. Progress: if no process is in its critical section, a process wishing to enter is not postponed indefinitely.
3. Bounded waiting: there is a limit to how long a process waits to enter after requesting.

Structure of a process: entry section, critical section, exit section, remainder section.

It is managed using:

• Software solutions such as Peterson's algorithm.
• Hardware support such as TestAndSet and Swap atomic instructions, or disabling interrupts.
• Semaphores: wait(mutex); critical section; signal(mutex);
• Monitors / mutex locks: language-level constructs that allow only one process to be active inside at a time.

Memory management techniques

1. Contiguous allocation: each process gets one contiguous block. Fixed (static) partitioning causes internal fragmentation; variable (dynamic) partitioning causes external fragmentation (placement by first fit, best fit, worst fit; compaction can reduce it).
2. 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. No external fragmentation, only a little internal fragmentation in the last page.
3. Segmentation: the program is divided into logical units (code, stack, data) of variable size. Each logical address is (segment number, offset) and a segment table holds the base and limit.
4. Segmentation with paging: each segment is paged, combining both.
5. Virtual memory / demand paging: only the needed pages are loaded; page faults bring others in with a page replacement algorithm (FIFO, LRU, Optimal).
6. Swapping: moving processes between main memory and backing store.

Paging vs segmentation

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

Faults occur at references 1-7, then 10 and 11, so there are 7 + 2 = 9 faults, and 3 hits.

Total page faults = 9

Non-preemptive SJF: at each completion the arrived process with the shortest burst is chosen.

• At $t=0$ only P1 has arrived, so P1 runs from 0 to 8.
• At $t=8$ the ready processes are P2 (4), P3 (9), P4 (5), P5 (2). Order: P5, P2, P4, P3.

Gantt chart

Waiting time = start time - arrival time:

$\text{Average waiting time} = \frac{0+9+17+11+4}{5} = \frac{41}{5} = 8.2 \text{ ms}$

(Average turnaround time $= 69/5 = 13.8$ ms.)

The disk arm is at cylinder 150, and we assume that it first moves towards the higher cylinders (the usual SCAN assumption). The highest request is 800, so the arm sweeps up to 800 and then reverses to serve 100.

Order of service: $150 \to 200 \to 350 \to 420 \to 600 \to 700 \to 750 \to 800 \to 100$

• Upward sweep: $800 - 150 = 650$
• Reverse to the lowest request: $800 - 100 = 700$

$\text{Total head movement} = 650 + 700 = 1350 \text{ cylinders}$

If the arm initially moved towards cylinder 0, it would go $150 \to 0$ (150) and then up to 800 (800), giving 950 cylinders.

File system layout

A file system is stored on a disk, which is divided into partitions. A typical layout is:

• Boot block / MBR: holds the code to boot the system and the partition table.
• Superblock: key information about the file system (type, number of blocks, size of the free-block list, pointer to the root directory).
• Free-space management: a bitmap or linked list of free blocks.
• i-nodes / FAT / file control blocks: metadata for each file (owner, size, permissions, block pointers).
• Root directory: the top-level directory.
• Data blocks: the contents of files and directories.

The allocation method decides how a file's blocks are placed on the disk.

1. Contiguous allocation

Each file occupies a set of consecutive blocks. The directory stores the start block and length.

• Advantages: simple; excellent read performance (little seek time); supports both sequential and direct (random) access easily; only start and length need to be stored.
• Disadvantages: external fragmentation; file size must be known in advance; a file cannot grow easily; compaction is expensive.

2. Linked list allocation

Each file is a chain of blocks; each block contains a pointer to the next block. The directory stores the first block.

• Advantages: no external fragmentation; files can grow dynamically; no need to know the size in advance.
• Disadvantages: random access is very slow (the chain must be followed from the start); space is lost to pointers in every block; one damaged pointer loses the rest of the file; the block data size is no longer a power of two.

3. Linked list allocation using a table in memory (FAT)

The pointers are moved out of the data blocks into a File Allocation Table, one entry per disk block, held in memory. The directory stores the first block number; the FAT entry for a block gives the next block (end-of-file marker for the last).

• Advantages: whole block is used for data; random access is faster because the chain is followed in memory, not on disk; no external fragmentation.
• Disadvantages: the entire table must be kept in memory, so it is large for big disks (a 1 TB disk with 1 KB blocks needs about a billion entries); still needs table traversal for random access; the table is a critical structure and must be protected.

Comparison

Deadlock

A deadlock is a situation in which a set of processes is blocked because each process holds a resource and waits for a resource held by another process in the set. None of them can proceed. For example, P1 holds the printer and requests the scanner, while P2 holds the scanner and requests the printer.

Four necessary conditions (Coffman conditions)

All four must hold at once:

1. Mutual exclusion: a resource can be used by only one process at a time (for example a printer).
2. Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by others (P1 holds the printer and waits for the scanner).
3. No preemption: a resource cannot be forcibly taken away; it is released only voluntarily (the printer cannot be taken from P1 mid-job).
4. Circular wait: there is a cycle of processes $P_0 \to P_1 \to \dots \to P_n \to P_0$, each waiting for a resource held by the next (P1 waits for P2 and P2 waits for P1).

Deadlock handling techniques

1. Prevention: make at least one condition impossible. Examples: request all resources at the start (no hold and wait); release held resources when a request fails (allow preemption); impose a total ordering on resources and request in increasing order (no circular wait). It is safe but wastes resources and lowers utilisation.
2. Avoidance: the OS knows maximum needs in advance and grants a request only if the system stays in a safe state. Uses the Banker's algorithm or a resource-allocation graph. Better utilisation than prevention, but needs advance information and has run-time overhead.
3. Detection: allow deadlocks to occur, then detect them using a wait-for graph (single instance resources) or a detection algorithm similar to the Banker's algorithm (multiple instances). Run periodically or when the CPU utilisation drops. No restriction on requests, but detection costs time.
4. Recovery: after detection, break the deadlock by process termination (abort all deadlocked processes or one at a time) or resource preemption (take resources from some processes, roll back, avoid starvation by limiting how often one victim is chosen).

Comparison

Many general-purpose systems simply ignore the problem (the ostrich approach), since deadlocks are rare.