Operating System

The memory wall is the growing gap between processor speed and memory speed. CPU performance improved about 50-60% per year for decades, while DRAM access time improved only about 7% per year. As a result the processor often waits for data from memory, so overall performance is limited by memory latency and bandwidth rather than by CPU speed.

Consequences: idle CPU cycles, larger relative cost of cache misses and page faults, and lower effective throughput.

Ways of reducing it

• Multi-level caches (L1, L2, L3) that exploit locality of reference.
• Prefetching and out-of-order execution to hide latency.
• Wider and faster memory buses, DDR memory and higher bandwidth (HBM).
• Multithreading and multicore processors, which switch to other work during a stall.
• Better OS memory management: good page replacement, working-set and locality-aware scheduling.
• Processing-in-memory and 3D-stacked memory.

Process

A process is a program in execution. It is an active entity, unlike a program, which is a passive file on disk. A process has its code (text), data, heap, stack, program counter, registers and other resources, all described by a Process Control Block (PCB).

Process state model

During its life a process passes through several states:

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

Transitions

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

• New -> Ready (admitted): the long-term scheduler accepts the process.
• Ready -> Running (dispatch): the short-term scheduler selects it and gives it the CPU.
• Running -> Ready (interrupt / time-out): its time quantum expires or a higher-priority process arrives (pre-emption).
• Running -> Waiting (I/O or event wait): the process requests I/O or waits for an event.
• Waiting -> Ready (I/O or event completion): the awaited event occurs.
• Running -> Terminated (exit): the process completes or is killed.

Some systems also add suspended ready and suspended wait states when processes are swapped out of memory.

Round Robin, time quantum = 3 ms

Each process runs for at most 3 ms, then goes to the back of the ready queue. Arriving processes join the queue before a pre-empted process is re-added; P3 and P5 both arrive at 2, so P3 is queued first.

Gantt chart

Remaining times after each slice: P1 6->3->0, P2 8->5->2->0, P3 7->4->1->0, P4 6->3->0, P5 9->6->3->0.

Calculation

$TAT = CT - AT, \qquad WT = TAT - BT$

$\text{Average TAT} = \frac{15+31+31+26+34}{5} = \frac{137}{5} = 27.4 \text{ ms}$

$\text{Average WT} = \frac{9+23+24+20+25}{5} = \frac{101}{5} = 20.2 \text{ ms}$

Check: total burst time is $6+8+7+6+9 = 36$ ms, which equals the finishing time of P5.

Race condition

A race condition occurs when two or more processes (or threads) access and change shared data at the same time, and the final result depends on the exact order in which their instructions are interleaved. Example: two processes execute counter++ on a shared variable. Each does load, add, store. If both load the value 5 before either stores, both store 6 and one increment is lost (the correct result is 7).

The part of the code that accesses shared data is the critical section. Race conditions are avoided by mutual exclusion: only one process may be inside its critical section at a time. A correct solution needs mutual exclusion, progress, and bounded waiting.

Types (methods) of mutual exclusion

1. Software solutions

   • Lock variable: a shared flag (0 = free, 1 = busy). It fails because testing and setting the flag is not atomic.
   • Strict alternation (turn variable): processes take turns. It guarantees mutual exclusion but violates progress, because a process outside its critical section can block the other.
   • Peterson's solution: uses flag[i] and turn. A process sets flag[i] = true; turn = j; and waits while flag[j] && turn == j. It satisfies all three requirements for two processes.

2. Hardware solutions

   • Disabling interrupts: simple, but unsafe for user programs and not usable on multiprocessors.
   • Test-and-Set (TSL) instruction: atomically reads a lock and sets it to true; a process spins until it reads false.
   • Swap / compare-and-swap: atomic exchange used to build locks.

3. Operating-system / language-level solutions

   • Semaphores: an integer variable accessed only by the atomic operations wait(P) and signal(V). A binary semaphore (mutex) initialised to 1 gives mutual exclusion:

   wait(mutex);
   // critical section
   signal(mutex);
   

   • Monitors: a high-level construct in which only one process can be active inside the monitor at a time; condition variables handle waiting.
   • Message passing: processes coordinate through send and receive.

Busy-waiting solutions (lock variable, TSL, Peterson) waste CPU, while semaphores and monitors block the process instead.

Direct Memory Access (DMA)

DMA is a technique in which a special hardware unit, the DMA controller, transfers a block of data directly between an I/O device and main memory without involving the CPU in each byte or word transferred. The CPU only starts the transfer and is interrupted when it is complete.

Block diagram

        +---------+            +-----------+
        |   CPU   |<---------->|  Memory   |
        +----+----+            +-----+-----+
             ^  | (address/data/control bus)  ^
             |  v                             |
  ===========+============+====================+========== System bus
                          |                    |
                +---------+---------+          |
  Interrupt <---|  DMA controller   |----------+
  Request/      | - Address register|  (reads/writes memory directly)
  HOLD/HLDA     | - Count register  |
                | - Control register|
                +---------+---------+
                          |  DREQ / DACK
                    +-----+------+
                    | I/O device |
                    | (disk etc.)|
                    +------------+

Working

1. The CPU programs the DMA controller: it loads the memory start address, the byte count, and the direction (read or write).
2. The device raises a DMA request (DREQ).
3. The DMA controller asks the CPU for the bus (HOLD); the CPU finishes its current bus cycle and grants it (HLDA).
4. The controller acknowledges the device (DACK) and transfers data directly between device and memory, incrementing the address and decrementing the 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.

How DMA improves I/O efficiency

• In programmed I/O the CPU waits in a loop and moves every byte; in interrupt-driven I/O the CPU is interrupted for every byte or word. With DMA, the CPU is interrupted only once per block, so interrupt overhead drops greatly.
• The CPU is free to run other processes while the transfer proceeds.
• Data moves directly to or from memory, not through the CPU registers, so large blocks transfer at high speed.
• Modes such as burst (block) mode and cycle stealing (the DMA takes one bus cycle at a time) balance transfer speed against CPU use.

Example: reading a 4 KB disk block with interrupts per byte needs about 4096 interrupts; with DMA, it needs one.

Security

Security in an operating system is the protection of the system's resources (data, programs, CPU, memory, devices) from unauthorised access, modification, destruction or disclosure, whether accidental or malicious. It covers the three goals of the CIA triad: confidentiality (only authorised users read data), integrity (data is not altered improperly), and availability (resources are usable when needed). Threats include viruses, worms, Trojan horses, logic bombs, denial of service, and password cracking.

User authentication

Authentication verifies the identity of a user ("who are you?") before access is granted. Methods:

1. Something the user knows: passwords, PINs. Passwords are stored as hashes (often with salt) to protect them; weaknesses are guessing, dictionary attacks, and sharing. One-time passwords reduce replay risk.
2. Something the user has: smart card, security token, mobile OTP.
3. Something the user is: biometrics such as fingerprint, iris, face or voice.
4. Multi-factor authentication: combining two or more of the above, for example password plus OTP, for much stronger security.
5. Other measures: CAPTCHA, account lockout after repeated failures, digital certificates and Kerberos tickets in networks.

Authorization

Authorization decides what an authenticated user is allowed to do ("what can you do?"). It happens after authentication.

• Access matrix: rows are domains (users), columns are objects (files, devices), and each cell lists permitted rights (read, write, execute).
• Access Control List (ACL): for each object, a list of users and their rights (a column of the matrix); used by Windows (NTFS).
• Capability list: for each user, a list of objects and rights (a row of the matrix).
• Unix permissions: read, write, execute for owner, group and others (for example, rwxr-xr--).
• Role-based access control: rights are given to roles, and users are assigned roles.

Difference: authentication proves identity; authorization grants permissions to that identity. A system should follow the principle of least privilege, giving users only the rights they need.

Design principles of Linux

Linux is a multiuser, multitasking, UNIX-compatible operating system, first developed by Linus Torvalds in 1991. Its design goals are:

• Compatibility with UNIX/POSIX standards: so UNIX applications can run with little or no change.
• Speed, efficiency and standardisation: performance matters more than elegance; implementation follows standards such as POSIX and System V.
• Modularity: a monolithic kernel for speed, yet with loadable modules for flexibility.
• Multiuser and multitasking: many users and processes run concurrently, with protection between them.
• Everything is a file: devices, pipes and sockets are accessed through the file interface.
• Portability and open source: runs on many hardware architectures, and the source code is freely available (GPL).
• Security and stability: user mode and kernel mode separation, file permissions, and the ability to run for long periods.

The system has three main parts: the kernel (the abstract hardware layer in kernel mode; handles process, memory, file and device management), the system libraries (standard functions through which applications call the kernel), and the system utilities (programs for setup tasks, such as shells and daemons).

Kernel modules

A kernel module is a piece of code (for example, a device driver, file system or network protocol) that can be loaded into or unloaded from the running kernel on demand, without recompiling or rebooting. Modules are stored as .ko files.

Module support has three components:

1. Module management: loads the module into kernel memory and resolves symbols with the kernel's symbol table. Commands: insmod, rmmod, modprobe, lsmod.
2. Driver registration: the module registers itself with the kernel (for example, character device, block device, file system, or network driver tables) so the kernel knows what services are available.
3. Conflict resolution: prevents modules from using the same hardware resources (I/O ports, IRQs, DMA channels) at the same time, by reserving resources.

Advantages: the kernel stays small; drivers load only when needed; development and updates are easier; no reboot is needed. Disadvantage: a faulty module runs in kernel mode and can crash the whole system.

Process vs thread

A process is a program in execution with its own address space and resources. A thread is a lightweight unit of execution within a process; threads of the same process share the code, data and open files, but each has its own program counter, registers and stack.

How threads increase multiprocessing (concurrency) of the CPU

• Parallelism on multiple CPUs: the threads of one process can run at the same time on different processors or cores, so a single program uses all the CPUs. A single-threaded process can use only one.
• Better CPU utilisation: while one thread waits for I/O (for example, disk or network), other threads of the same process continue to run, so the CPU does not idle.
• Responsiveness: in a web browser, one thread can keep the interface alive while another downloads a page; the program keeps running even if part is blocked.
• Resource sharing and low overhead: threads share memory, so creating them and switching between them is cheap. This allows many more threads than processes, so the system can keep many tasks active.
• Scalability: a task can be split into sub-tasks (for example, a server using one thread per client) so throughput grows as processors are added.

RAID (Redundant Array of Independent Disks) is a technology that combines several physical disks into one logical unit to improve performance, reliability, or both. Data is spread over the disks (striping), duplicated (mirroring) or protected with parity.

Common RAID levels

• RAID 0 (striping): data is split across disks without redundancy. High speed and full capacity, but no fault tolerance; one failure loses everything.
• RAID 1 (mirroring): each disk has an exact copy. High reliability and fast reads, but 50% of capacity is used for the copy.
• RAID 2: bit-level striping with Hamming-code error correction (rarely used).
• RAID 3: byte-level striping with a dedicated parity disk.
• RAID 4: block-level striping with a dedicated parity disk.
• RAID 5: block-level striping with parity distributed over all disks. Survives one disk failure; good balance of speed, capacity and redundancy (minimum 3 disks).
• RAID 6: like RAID 5 with two parity blocks; survives two failures (minimum 4 disks).
• RAID 10 (1+0): a stripe of mirrors; high performance and reliability, needs at least 4 disks.

Benefits: better performance through parallel I/O, fault tolerance through redundancy, larger capacity.

UNIX operating system

UNIX is a powerful, multi-user, multitasking, portable and time-sharing operating system. It was developed at AT&T Bell Laboratories in 1969-70 by Ken Thompson and Dennis Ritchie, and was rewritten in the C language in 1973, which made it easily portable to different hardware. Its many variants include BSD, System V, Solaris, AIX, HP-UX, and the UNIX-like Linux and macOS.

Architecture (layered):

   Users / applications
   +-----------------------------+
   | Shell and utilities (ls, cp)|
   +-----------------------------+
   | System call interface       |
   +-----------------------------+
   | Kernel (process, memory,    |
   |  file system, device mgmt)  |
   +-----------------------------+
   | Hardware                    |
   +-----------------------------+

• Kernel: the core which controls the hardware, schedules processes, manages memory, and provides the file system and system calls.
• Shell: command interpreter (sh, csh, bash, ksh) which accepts commands from the user and runs them. It also supports scripting, pipes and I/O redirection.
• Utilities and application programs: editors, compilers and tools.

Main features:

1. Multi-user and multitasking: many users and programs run at the same time.
2. Portability, since most of it is written in C.
3. Hierarchical file system: a single tree starting from the root /, where everything (files, directories, devices) is treated as a file.
4. Pipes and filters: the output of one command can be fed into another, for example ls | wc -l.
5. Security through file permissions (read, write, execute for owner, group and others) and passwords.
6. Networking support and a rich set of tools for programmers.
7. Demand-paged virtual memory in modern versions.

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

(i) LRU (replace the page unused for the longest time)

(At 5, page 3 is least recently used; at 6, page 5 is; at the second 5, page 1 is.)

Page faults = 6.

(ii) FIFO (replace the oldest page)

Page faults = 8.

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

(At 5, page 3 is never used again; at 6, page 1 is never used again.)

Page faults = 5.

Summary: LRU = 6, FIFO = 8, Optimal = 5.

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 1 2 0 (15 references), 3 frames.

(i) LRU

Faults = 12, hits = 3. Hit ratio = 3/15 = 0.20 (20%), fault ratio = 12/15 = 0.80 (80%).

(ii) FIFO

Faults = 12, hits = 3. Hit ratio = 3/15 = 20%, fault ratio = 12/15 = 80%.

(iii) Optimal (OPR)

Faults = 8, hits = 7. Hit ratio = 7/15 = 0.467 (46.7%), fault ratio = 8/15 = 0.533 (53.3%).

(iv) Clock (second chance)

Frames are arranged in a circle with a use bit and a hand. On a hit the use bit is set to 1; on a fault the hand skips (and clears) pages with use bit 1 and replaces the first page with bit 0, then moves on. Frames (F1, F2, F3) after each reference:

Faults = 12, hits = 3. Hit ratio = 20%, fault ratio = 80%.

Summary

Disk scheduling is the method by which the OS chooses the order in which pending disk requests are serviced, so that seek time is reduced and disk throughput is improved.

Given: 200 cylinders (0-199), head at 48, previous request at 50 (head moving downwards). Queue: 82, 170, 40, 140, 24, 16, 180.

(i) FCFS

Order: 48 → 82 → 170 → 40 → 140 → 24 → 16 → 180

$34+88+130+100+116+8+164 = 640$

Total distance = 640 cylinders.

(ii) SSTF

Order: 48 → 40 → 24 → 16 → 82 → 140 → 170 → 180

$8+16+8+66+58+30+10 = 196$

Total distance = 196 cylinders.

(iii) SCAN (initially moving downwards)

The arm moves down servicing 40, 24, 16, continues to cylinder 0, then reverses and services 82, 140, 170, 180.

Order: 48 → 40 → 24 → 16 → 0 → 82 → 140 → 170 → 180

$(48-0) + (180-0) = 48 + 180 = 228$

Total distance = 228 cylinders.

SSTF is best here (196), SCAN is next (228), FCFS is worst (640).

Page fault

A page fault is a trap raised by the hardware (MMU) when a running process refers to a page that is in its logical address space but is not currently present in main memory (the valid bit in the page table is 0). The OS then locates the page on disk, finds a free frame (or selects a victim page using a replacement algorithm), loads the page, updates the page table and restarts the instruction.

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

i. LRU (the page unused for the longest time is replaced; frames shown from least to most recently used)

Page faults = 12, hits = 3.

ii. FIFO (the oldest page is replaced; frames shown oldest first)

Page faults = 12, hits = 3.

iii. Optimal (OPR) (the page whose next use is farthest in the future is replaced)

For example, at reference 2 the pages 7, 0, 1 are in memory, and 7 is never used again, so 7 is replaced. At reference 3 (second use), 1 is used farthest in future, so it is replaced. Page faults = 8, hits = 7.

Hit ratio and fault ratio

$\text{Hit ratio}=\frac{\text{hits}}{\text{total references}},\qquad \text{Fault ratio}=\frac{\text{faults}}{\text{total references}}$

The optimal algorithm gives the fewest faults, but it cannot be implemented in practice because the future reference string is unknown. It is used as a benchmark.

Disk has cylinders 0 to 199. Head is at 50, the previous request was at 60, so the arm was moving towards lower cylinders. Queue (FIFO): 82, 170, 43, 140, 24, 16, 190.

i. FCFS (requests are served in arrival order)

Path: $50\to82\to170\to43\to140\to24\to16\to190$

$32+88+127+97+116+8+174 = 642$

Total head movement = 642 cylinders.

ii. SSTF (the request nearest to the current head position is served next)

Path: $50\to43\to24\to16\to82\to140\to170\to190$

$7+19+8+66+58+30+20 = 208$

Total head movement = 208 cylinders.

iii. SCAN, initially moving downwards (the arm goes to the end of the disk, then reverses)

Path: $50\to43\to24\to16\to0\to82\to140\to170\to190$

$(50-0) + (190-0) = 50+190 = 240$

Total head movement = 240 cylinders. (Requests 43, 24, 16 are served on the way down; after reaching cylinder 0 the arm reverses and serves 82, 140, 170, 190.)

iv. LOOK, initially moving upwards (the arm goes only as far as the last request in the current direction, then reverses)

Path: $50\to82\to140\to170\to190\to43\to24\to16$

$(190-50) + (190-16) = 140+174 = 314$

Total head movement = 314 cylinders.

SSTF gives the least movement here, though it can cause starvation of far-away requests.

Security threats in an operating system

Operating system security means protecting the system's resources (CPU, memory, files, devices) and the information stored in it from unauthorised access, modification or destruction. The main threats are:

• Malware: programs that harm the system. Types include virus (attaches itself to a file and spreads when it is run), worm (spreads by itself over a network), Trojan horse (looks useful but contains hidden harmful code), logic bomb (triggers when a condition is met), spyware and ransomware (encrypts data and demands payment).
• Intruders / unauthorised access: attackers who guess or steal passwords, or who exploit weak authentication to get access.
• Denial of Service (DoS / DDoS): flooding a system with requests so that legitimate users cannot be served.
• Buffer overflow and other software vulnerabilities: writing more data than a buffer can hold overwrites adjacent memory and may let an attacker run their own code.
• Trap door (back door): a hidden entry point left in a program that bypasses normal authentication.
• Eavesdropping and sniffing: capturing data passing through a network.
• Masquerading, phishing and social engineering: pretending to be a legitimate user or tricking users into revealing information.
• Insider threats and physical theft.

Protection from the threats

1. Authentication: strong passwords, one-time passwords, biometrics, smart cards and multi-factor authentication to verify identity.
2. Authorisation and access control: access matrix, access control lists (ACL) and capability lists, with the principle of least privilege, so each user or process gets only the rights it needs.
3. Memory and process protection: base and limit registers, user mode versus kernel mode, and non-executable stack to limit buffer overflow.
4. Cryptography: encrypting stored data and network traffic, and using digital signatures.
5. Antivirus and anti-malware software, regular OS patching and updates, and avoiding untrusted software.
6. Firewalls and intrusion detection and prevention systems to filter and monitor network traffic.
7. Auditing and logging of security-relevant events, and regular backups for recovery.
8. User training against phishing, and physical security of machines.

Page fault

A page fault is an interrupt (trap) generated by the memory management hardware when a process accesses a page that is mapped in its address space but is not present in main memory. The OS handles it by finding the page on disk, bringing it into a free frame (replacing a victim page if no frame is free using a page replacement algorithm), updating the page table, and restarting the instruction.

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

i. FIFO (frames shown oldest first)

Page faults = 18 (hits = 2).

ii. Optimal (OPR) (the page used farthest in the future is replaced)

Page faults = 14 (hits = 6).

iii. LRU (frames shown from least recently used to most recently used)

Page faults = 17 (hits = 3).

Summary

OPR gives the least number of faults (it is the theoretical minimum), LRU is close to it in practice, and FIFO is the worst and may even show Belady's anomaly.

Security threats in an operating system

Security is concerned with protecting the system's resources and information against unauthorised access, alteration or destruction. The main threats are:

• Malicious programs: virus, worm, Trojan horse, logic bomb, spyware, ransomware, rootkits.
• Unauthorised access by intruders, through guessed or stolen passwords and masquerading.
• Denial of Service (DoS/DDoS) attacks which overload a system so that legitimate users are denied service.
• Software vulnerabilities such as buffer overflow, and trap doors (back doors) left by programmers.
• Network attacks: eavesdropping (sniffing), man-in-the-middle, spoofing and replay attacks.
• Social engineering and phishing, and insider threats.

Protection

1. Authentication (passwords, one-time passwords, biometrics, smart cards, multi-factor authentication).
2. Access control: access control lists, capabilities and the principle of least privilege; separation of user mode and kernel mode; memory protection with base and limit registers.
3. Antivirus and anti-malware tools, and regular OS patching and updates.
4. Firewalls, and intrusion detection and prevention systems.
5. Auditing and logging, and regular backup of data.
6. Cryptography, as explained below.
7. Physical security and user awareness.

Importance of a cryptosystem

A cryptosystem is a method of transforming readable data (plaintext) into an unreadable form (ciphertext) using an encryption algorithm and a key, and recovering it with decryption. Its components are plaintext, ciphertext, encryption and decryption algorithms, and the keys.

• Symmetric-key cryptosystem: the same secret key is used for encryption and decryption (DES, AES). It is fast but the key must be shared securely.
• Asymmetric (public-key) cryptosystem: a public key encrypts and a private key decrypts (RSA). It solves the key distribution problem but is slower.

Importance:

1. Confidentiality: only authorised parties can read the data, even if it is intercepted on a network or stolen from a disk.
2. Integrity: hash functions and message authentication codes detect any change of data.
3. Authentication: confirms the identity of users, hosts and software, for example with digital certificates.
4. Non-repudiation: digital signatures prevent a sender from denying a message that they sent.
5. It protects stored passwords (hashing), files (file system encryption), and communication (SSL/TLS, VPN), and supports safe e-commerce and e-banking.

Operating system

An operating system (OS) is system software that manages the computer hardware and provides a base on which application programs run. It acts as an interface between the user and the hardware, and as a resource manager that allocates the CPU, memory, files and I/O devices. Examples: Windows, Linux, macOS, Android.

Types of operating system

1. Batch operating system: Similar jobs are collected into batches and run one after another with no user interaction while a job runs. It keeps the CPU busy, but turnaround time is long and debugging is hard. Example: early IBM mainframe systems, payroll processing.
2. Multiprogramming operating system: Several jobs are kept in memory at once. When one job waits for I/O, the CPU switches to another, so CPU utilisation rises.
3. Time-sharing (multitasking) operating system: The CPU is given to each user or process for a short time slice, switching so quickly that every user feels they have the machine to themselves. It gives good response time. Example: UNIX, Linux.
4. Multiprocessor (parallel) operating system: Uses two or more CPUs that share memory and the bus. It gives higher throughput and reliability (if one CPU fails the others continue).
5. Distributed operating system: Many independent computers connected by a network appear to the user as one system. Resources and load are shared, and it is fault tolerant and scalable. Example: LOCUS, Amoeba.
6. Network operating system: Runs on a server and lets clients share files, printers and users over a network, with each computer keeping its own OS. Example: Windows Server, Novell NetWare.
7. Real-time operating system (RTOS): Must respond within a fixed deadline. Hard real time never misses a deadline (missile control, pacemaker); soft real time tolerates occasional misses (video streaming). Example: VxWorks, QNX.
8. Embedded / mobile operating system: Small, specialised systems in devices such as phones, ATMs, washing machines. Example: Android, iOS.
9. Single-user and multi-user systems: A single-user OS (MS-DOS) serves one user at a time, while a multi-user OS (UNIX, Linux) allows many users to use the system concurrently.

System call

A system call is the programmatic interface through which a user program requests a service from the operating system kernel. User programs run in user mode and cannot directly access hardware, so they execute a system call (a trap instruction) that switches the CPU to kernel mode, the kernel performs the service, and control returns to the program. Programs normally use them through library functions (for example, printf() ends in the write() system call).

Types of system calls

1. Process control: create, terminate, load and execute processes, wait for events, allocate and free memory. Examples: fork(), exec(), exit(), wait(), abort().
2. File management: create, delete, open, close, read, write and reposition files, and get or set attributes. Examples: open(), close(), read(), write(), lseek(), unlink().
3. Device management: request and release devices, read, write and reposition them, and attach or detach devices. Examples: ioctl(), read(), write(), request device, release device.
4. Information maintenance: get or set system data such as time, date, process or file attributes. Examples: getpid(), time(), getattr(), setattr(), alarm().
5. Communication: create and delete communication connections, send and receive messages, and attach to shared memory. Examples: pipe(), shmget(), mmap(), socket(), send(), recv().
6. Protection: control access to resources and set permissions. Examples: chmod(), chown(), umask().

Example: in Linux, the program fork()s a child, the child calls exec() to run a new program, and the parent calls wait() for it to finish.

Inter-Process Communication (IPC)

IPC is the set of mechanisms by which cooperating processes exchange data and synchronise their actions.

Need for IPC

• Information sharing: several processes use the same data (for example, a shared file or database).
• Computation speed-up: a task is divided into sub-tasks that run in parallel and exchange results.
• Modularity: a system is divided into separate processes or modules that communicate.
• Convenience: a user can edit, print and compile at the same time.
• Synchronisation: processes must coordinate access to shared resources to avoid race conditions.

Two basic models are shared memory (processes read and write a shared region; fast) and message passing (processes use send and receive; easier for distributed systems). Pipes, FIFOs, message queues, semaphores and sockets are common IPC tools.

Thread models (multithreading models)

A thread is a lightweight unit of CPU execution inside a process. Threads are of two kinds: user-level threads (managed by a library) and kernel-level threads (managed by the OS). The mapping between them gives three models:

1. Many-to-One: many user threads map to one kernel thread.
   • Advantages: thread management is efficient and done in user space.
   • Disadvantages: one blocking system call blocks the whole process; threads cannot run in parallel on multiple CPUs.
2. One-to-One: each user thread maps to its own kernel thread.
   • Advantages: more concurrency; a blocking thread does not block others; true parallelism on multiprocessors.
   • Disadvantages: creating a user thread needs creating a kernel thread, which is costly, so the number of threads is limited. Used by Linux and Windows.
3. Many-to-Many: many user threads are multiplexed onto a smaller or equal number of kernel threads.
   • Advantages: the developer can create as many user threads as needed, and they still run in parallel; a blocking call lets the kernel schedule another thread.
   • Disadvantage: complex to implement. A variation is the two-level model, which also allows a user thread to be bound to one kernel thread.

Page fault

A page fault is a trap raised by the hardware (MMU) when a process references a page that is in its logical address space but is not currently in main memory. The OS finds the page on disk, loads it into a free frame (or replaces a victim page if no frame is free), updates the page table, and restarts the instruction.

Reference string (20 references, 3 frames, initially empty):

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6

(a) FIFO (the page that has been in memory longest is replaced; frames listed oldest first)

FIFO: 4 hits, so $20 - 4 = 16$ page faults.

(b) LRU (the page unused for the longest time is replaced; frames listed least recently used first)

LRU: 5 hits, so $20 - 5 = 15$ page faults.

(c) Optimal (the page whose next use is farthest in the future, or never, is replaced)

Optimal: 9 hits, so $20 - 9 = 11$ page faults.

Summary

Optimal gives the fewest faults, but it needs knowledge of future references, so it is used only as a benchmark.

Swapping

Swapping is a memory-management technique in which a process is temporarily moved out of main memory to a backing store (a fast disk area), and later brought back into memory to continue execution. It lets the total memory demanded by all processes exceed the physical memory, and so raises the degree of multiprogramming.

• Swap out: a process (for example, a low-priority or blocked one) is written to the backing store, freeing its memory.
• Swap in: the process is read back into memory when it is to run again.
• In priority-based scheduling, a lower-priority process is swapped out so a higher-priority one can be loaded (this is called roll out, roll in).
• Context-switch time is high because it includes the transfer time. For example, swapping out a 10 MB process at a transfer rate of 40 MB/s takes $10/40 = 0.25$ s = 250 ms (plus latency), and the same again to swap in.
• A process waiting for I/O must not be swapped out unless the I/O uses OS buffers.

Logical vs physical address space

• A logical (virtual) address is generated by the CPU while a program runs. The set of all logical addresses is the logical address space.
• A physical address is the actual location seen by the memory unit (loaded in the memory address register). The set of all of them is the physical address space.
• The Memory Management Unit (MMU) maps logical to physical addresses at run time. With a simple relocation (base) register:

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

Example: if a program is loaded at base address (relocation register) 14000 and the CPU generates logical address 346, the MMU produces the physical address $14000 + 346 = 14346$. The program only ever sees addresses 0 to its size, while the hardware sees addresses starting at 14000. In compile-time and load-time binding the two are the same; they differ in execution-time binding.

Disk scheduling

Disk scheduling is the method used by the operating system to decide the order in which pending disk I/O requests are served. The aim is to reduce the seek time (the time to move the head to the required track), and so reduce total head movement and improve throughput.

Given: 200 tracks (0 to 199), head at 143, previous request at 125 (so the head is moving towards higher tracks). Queue: 86, 147, 91, 177, 94, 150, 102, 175, 130.

(i) FCFS (requests served in arrival order)

Path: 143 -> 86 -> 147 -> 91 -> 177 -> 94 -> 150 -> 102 -> 175 -> 130

$\text{Total} = 57+61+56+86+83+56+48+73+45 = 565 \text{ tracks}$

(ii) SSTF (the request closest to the current head is served next)

Path: 143 -> 147 -> 150 -> 130 -> 102 -> 94 -> 91 -> 86 -> 175 -> 177

$\text{Total} = 4+3+20+28+8+3+5+89+2 = 162 \text{ tracks}$

(iii) SCAN (the head moves towards higher tracks, serving requests on the way, goes to the end of the disk at 199, then reverses)

Path: 143 -> 147 -> 150 -> 175 -> 177 -> 199 -> 130 -> 102 -> 94 -> 91 -> 86

$\text{Up: } 199 - 143 = 56, \qquad \text{Down: } 199 - 86 = 113$

$\text{Total} = 56 + 113 = 169 \text{ tracks}$

(If the head turns back at the last request, 177, instead of going to 199 (the LOOK variant), the total is $(177-143) + (177-86) = 34 + 91 = 125$.)

Summary

SSTF gives the least movement here, but it can cause starvation of far-away requests; SCAN avoids starvation.

File system

A file system is the part of the operating system that organises, stores, names, retrieves and protects data on secondary storage as files and directories. It gives users a logical view (files, folders) over the physical disk blocks. Examples: FAT32, NTFS, ext4.

Implementation of a file system

1. On-disk structures

• Boot control block (boot block): information needed to boot an OS from that volume.
• Volume control block (superblock): number of blocks, block size, free-block count and pointers, free FCB count and pointers.
• Directory structure: maps file names to their file control blocks (in UNIX, to inode numbers).
• File Control Block (FCB / inode): permissions, owner, size, dates, and pointers to the data blocks.

2. In-memory structures

• Mount table: information about each mounted volume.
• Directory cache: recently accessed directory information.
• System-wide open-file table: copy of the FCB of every open file.
• Per-process open-file table: pointer into the system-wide table, plus the current file position and access mode.

3. Creating and opening a file

To create a file, the system allocates an FCB, reads the directory into memory, adds the new entry, and writes the directory back. To open a file, open() searches the system-wide table (adding the FCB if absent), then creates an entry in the per-process table and returns a file descriptor (index). read() and write() use this index; close() removes the entry.

4. Layered design

Application programs -> logical file system (directories, FCBs, protection) -> file-organisation module (maps logical blocks to physical blocks, free-space manager) -> basic file system (issues generic block commands) -> I/O control (device drivers, interrupt handlers) -> devices.

5. Directory implementation

• Linear list: simple, but slow to search.
• Hash table: fast lookup, but fixed size and collisions must be handled.

6. Allocation methods

• Contiguous: each file occupies consecutive blocks; fast access, but external fragmentation and file growth problems.
• Linked: each block points to the next; no external fragmentation, but slow direct access and pointer overhead (FAT improves this).
• Indexed: an index block holds all the block pointers; supports direct access (UNIX inodes use direct and indirect pointers).

7. Free-space management

Bit vector (bitmap), linked list of free blocks, grouping, and counting.

File attributes

File attributes (metadata) are the properties the OS stores about a file, normally in its directory entry or inode:

• Name: the human-readable identifier.
• Identifier: a unique number (for example, the inode number) used internally.
• Type: text, executable, image, and so on (needed by systems that support multiple types).
• Location: pointer to the device and the disk blocks.
• Size: current size in bytes or blocks.
• Protection: access permissions for read, write and execute.
• Time, date and user identification: creation, last modification and last access, and the owner.

Directory structures

A directory is a file that holds information about other files. The main structures are:

1. Single-level directory: all files are in one directory.
   • Advantages: simple to implement and understand; fast searching for few files.
   • Disadvantages: every file name must be unique; no grouping; different users clash; hard to manage many files.
2. Two-level directory: a Master File Directory (MFD) contains one User File Directory (UFD) per user.
   • Advantages: different users can use the same file names; efficient searching; isolation between users.
   • Disadvantages: no grouping within a user's files; users cannot easily share files; cooperation between users is hard.
3. Tree-structured directory: a root directory with subdirectories to any depth; a path name (absolute or relative) identifies a file.
   • Advantages: users can create subdirectories and group files logically; efficient searching; the same name can be reused in different directories.
   • Disadvantages: sharing a file between users is difficult; long path names; deleting a non-empty directory needs care.
4. Acyclic-graph directory: a tree that allows shared subdirectories and files through links.
   • Advantages: supports file and directory sharing; changes are visible to all sharers.
   • Disadvantages: a file may have several names (aliases); deletion is complex (dangling pointers, reference counts are needed).
5. General-graph directory: links can create cycles.
   • Advantages: maximum flexibility in sharing.
   • Disadvantages: searching may loop forever; needs garbage collection or cycle detection; deletion is difficult.

Deadlock prevention

A deadlock is a situation in which a set of processes are all blocked, each holding a resource and waiting for a resource held by another in the set. Deadlock can occur only if four conditions hold together (Coffman conditions). Deadlock prevention makes sure that at least one of them can never hold.

1. Mutual exclusion: a resource can be used by one process at a time. Prevention: make resources sharable where possible (for example, read-only files). It cannot be denied for inherently non-sharable resources such as printers.
2. Hold and wait: a process holds some resources while waiting for others. Prevention: require a process to request all its resources before it starts (or to release all held resources before requesting new ones). Disadvantages: low resource utilisation and possible starvation.
3. No pre-emption: resources cannot be forcibly taken. Prevention: if a process holding resources requests one that is not available, it releases everything it holds and restarts later; or the OS pre-empts the resources of a waiting process. This suits resources whose state can be saved, such as CPU registers and memory.
4. Circular wait: a cycle of processes each waiting for the next. Prevention: assign a number to every resource type and force processes to request resources only in increasing order. This makes a cycle impossible.

Prevention is safe but can reduce device utilisation and throughput. It differs from deadlock avoidance (for example, the Banker's algorithm), which uses advance information to keep the system in a safe state.

Device controller

A device controller (adapter) is the electronic hardware component that operates a particular I/O device (or group of similar devices) and connects it to the computer's bus. Each controller has:

• Registers: a command (control) register, a status register, and a data buffer register that the CPU reads or writes through I/O ports or memory-mapped addresses.
• A local buffer to hold data while it is transferred between device and memory.
• Logic to convert signals, detect errors, and in some cases perform DMA.

The controller handles low-level work such as moving a disk arm, converting serial bits to a block of bytes, and checking error-correcting codes. Examples: disk controller, USB controller, graphics adapter.

Device driver

A device driver is a software module in the operating system kernel that communicates with a specific device controller. It receives general I/O requests from the upper layer of the OS (for example, "read block n") and translates them into the specific commands, register values and sequences that the controller understands. It also handles interrupts from the device and reports status or errors back.

Roles: initialise the device, accept requests and queue them, issue commands to the controller, handle interrupts, and report errors. Drivers are device-specific and are usually written by the device manufacturer, which lets the OS support new hardware without changing its core.

Difference: the controller is hardware attached to the device or bus; the driver is software that runs on the CPU and controls that hardware.

Security levels in Linux

Linux security is based on UNIX-style discretionary access control:

• Authentication: user name and password, stored as salted hashes in /etc/shadow; Pluggable Authentication Modules (PAM) allow other methods.
• Users and groups: each user has a UID and belongs to groups (GID). The root user (UID 0) has full privileges.
• File permissions: read (r), write (w) and execute (x) for owner, group and others, such as rwxr-xr-- (754), changed with chmod and chown. Special bits: setuid, setgid and sticky bit.
• Access Control Lists and SELinux / AppArmor: mandatory access control that confines programs.
• Other tools: sudo for limited privilege escalation, iptables/firewalld firewall, and kernel/user mode separation.

Security levels in Windows

• Authentication: user accounts with passwords (stored in the SAM or Active Directory); Windows logon, Kerberos, and multi-factor options such as Windows Hello.
• Security identifiers (SID) identify users and groups; an access token is created at logon.
• Access Control Lists: each object (file, folder, registry key) has a security descriptor with a DACL (permissions) and a SACL (auditing). NTFS permissions include full control, modify, read & execute, read and write.
• User Account Control (UAC) limits administrator rights, and BitLocker and EFS encrypt data.
• Other tools: Windows Defender antivirus, Windows Firewall, auditing and group policy.

Both systems follow the principle of least privilege; Linux typically uses simple permission bits, and Windows uses fine-grained ACLs. The US DoD "Orange Book" also defines security levels D, C1, C2, B1, B2, B3 and A1; Linux and Windows (NT onward) can be configured to C2 level.

Operating system

An operating system (OS) is system software that manages computer hardware and software resources and provides common services for programs. It acts as an intermediary between the user and the hardware, so that the computer is convenient to use and its resources are used efficiently. Examples: Windows, Linux, macOS, Android.

Major functions of an operating system

1. Process management: creating and deleting processes, scheduling the CPU among them, suspending and resuming them, and providing mechanisms for synchronisation, communication and deadlock handling.
2. Memory management: keeping track of which parts of memory are used and by whom, allocating and deallocating memory when processes start and end, deciding which processes to load, and supporting techniques such as paging, segmentation, swapping and virtual memory.
3. File management: creating, deleting, reading and writing files and directories, mapping files onto secondary storage, controlling access, and backing up data.
4. Device (I/O) management: hiding the hardware details through device drivers, buffering, caching and spooling, and allocating and scheduling I/O devices.
5. Secondary storage management: free-space management, storage allocation and disk scheduling.
6. Security and protection: authenticating users, controlling access to files, memory and the CPU, and protecting against unauthorised use.
7. User interface (command interpreter): providing a command-line interface (shell) or graphical interface so users can interact with the system.
8. Networking and communication: allowing processes on different computers to communicate through message passing or sockets.
9. Error detection and resource accounting: detecting and responding to hardware or program errors and recording resource usage by users and processes.

Virtual machine (VM)

A virtual machine is a software emulation of a complete computer that behaves like separate physical hardware. A layer called the virtual machine monitor (hypervisor) runs on the host hardware and creates several isolated virtual machines. Each VM gets its own virtual CPU, memory, disk and network, and runs its own guest operating system, though all share the one physical machine.

Types of hypervisor:

• Type 1 (bare metal): runs directly on hardware (VMware ESXi, Xen, Hyper-V).
• Type 2 (hosted): runs on a host OS (VirtualBox, VMware Workstation).

Another example is the Java Virtual Machine, which runs Java bytecode on any platform.

Benefits: isolation and protection (a crash or virus stays inside the VM), running multiple OSs on one machine, easy testing and development, easy backup, migration and cloning, and better hardware utilisation. Drawbacks: lower performance than native hardware and difficulty sharing resources directly between VMs.

System interfaces

The OS provides several interfaces through which users and programs reach its services:

1. Command-line interface (CLI) / command interpreter (shell): the user types commands (ls, cp, dir), and the shell interprets them and calls system routines. It is powerful and scriptable (bash, cmd).
2. Graphical user interface (GUI): windows, icons, menus and a pointer (mouse); intuitive and easy for non-technical users (Windows, GNOME).
3. Touch-screen interface: gestures on mobile systems (Android, iOS).
4. System call interface / API: programs request kernel services (file, process, memory, I/O) through system calls, usually via an API such as POSIX, the Win32 API or the Java API. The library hides the trap into kernel mode.
5. Batch interface: commands are placed in a file (shell script or batch file) and executed without interaction.

Naming of a file

A file is a named collection of related information stored on secondary storage. The name is the way users refer to the file, so when a file is created it is given a name and keeps it until deleted. Naming rules differ between systems:

• Length: MS-DOS allowed 8 characters plus a 3-character extension; modern systems (NTFS, ext4) allow up to 255 characters.
• Allowed characters: letters, digits and some symbols; certain characters (such as / \ : * ? " < > | in Windows) are not permitted.
• Case: UNIX/Linux names are case-sensitive (Data.txt and data.txt differ); Windows names are case-insensitive.
• Extension: the part after the dot (.txt, .exe, .jpg) tells the type of the file to the user and to applications.

File types

Besides regular files, UNIX also has directories and special files (character and block device files). The OS recognises types through the extension, a magic number inside the file, or the creator attribute.

File attributes

These are kept in the directory entry or in the file control block (inode).

Swapping

Swapping is a memory-management technique in which a process is temporarily moved from main memory to a backing store (disk), and brought back later to continue. A swap out frees memory for another process and a swap in restores the swapped process. It allows more processes than fit in memory, increasing the degree of multiprogramming, but swap time is high because it depends on the amount of data transferred (a 10 MB process on a 40 MB/s disk needs $10/40 = 0.25$ s = 250 ms each way).

Page table structures

In paging, memory is divided into fixed-size frames and the logical address is divided into a page number $p$ and an offset $d$. The page table maps $p$ to a frame number. For large address spaces (for example, 32-bit with 4 KB pages there are $2^{20}$ pages, so about 4 MB of table per process), a simple table is too large, so structured page tables are used.

1. Hierarchical (multi-level) paging: the page table is itself paged. In two-level paging, the logical address is split into $p_1$ (index into the outer table), $p_2$ (index into the inner page table) and $d$. Only the inner tables in use need to be in memory. Example: a 32-bit address with 4 KB pages is split 10 bits ($p_1$) + 10 bits ($p_2$) + 12 bits ($d$). The outer table has $2^{10} = 1024$ entries, each pointing to an inner table of 1024 entries.
2. Hashed page table: used for address spaces larger than 32 bits. The virtual page number is hashed to an entry in a hash table; each entry is a chain of elements (page number, frame number, next pointer). The system hashes the page number and walks the chain to find a match.
3. Inverted page table: one global table with one entry per physical frame, each entry holding (process id, page number). Memory used is small (proportional to physical memory), but searching is slow, so a hash table is often added. Used by PowerPC and UltraSPARC.
4. Translation Lookaside Buffer (TLB): not a table structure but a small fast associative cache of recent page-to-frame mappings that speeds up all of the schemes above. With hit ratio 90%, TLB time 20 ns and memory access 100 ns, the effective access time is $0.9(20+100) + 0.1(20+100+100) = 108 + 22 = 130$ ns.

Simple example: with page size 1 KB, logical address 2100 lies on page $p = \lfloor 2100/1024 \rfloor = 2$ with offset $d = 2100 - 2048 = 52$. If the page table gives frame 5 for page 2, the physical address is $5 \times 1024 + 52 = 5172$.

Swapping

Swapping is a memory-management technique in which a process is moved temporarily from main memory to a backing store (disk) and brought back later for continued execution. It lets the system run more processes than fit in physical memory. A process is swapped out when memory is needed for another (for example, a higher-priority process), and swapped in when it is scheduled again. Its drawback is the long transfer time during context switches.

Fragmentation

Fragmentation is the wasting of memory in small pieces that cannot be used. Strictly, fragmentation is not something we "need": it is an unwanted side-effect of allocating memory, and memory management tries to reduce it. It arises because processes are loaded and removed, leaving memory broken into pieces.

Types of fragmentation

1. Internal fragmentation: memory is allocated in fixed-size blocks (fixed partitions or paging), so a process may be given more than it needs; the unused part inside the allocated block is wasted. Example: with 4 KB frames, a 9 KB process needs 3 frames (12 KB), and 3 KB is wasted inside the last frame.
2. External fragmentation: total free memory is enough to satisfy a request, but it is not contiguous, being scattered in small holes between allocated areas (variable partitions, segmentation). Example: free holes of 5 KB, 4 KB and 6 KB give 15 KB in total, but a request of 10 KB cannot be satisfied.

Overcoming fragmentation

• Compaction: shuffle the memory contents to collect all free holes into one large block. It is possible only with dynamic (execution-time) relocation and is costly in time.
• Paging: divide memory into fixed-size frames and the process into pages, so a process need not be contiguous; this removes external fragmentation (only a small internal fragmentation remains in the last page). Using smaller pages reduces the internal waste.
• Segmentation with paging: gives logical segments without contiguous physical allocation.
• Better allocation strategies: first fit, best fit and worst fit reduce the creation of unusable holes (best fit leaves the smallest hole, first fit is fastest).
• Variable-size partitions (instead of fixed ones) reduce internal fragmentation.
• Swapping and coalescing: when adjacent holes become free, they are merged into one larger hole.

Device controller

A device controller (I/O controller or adapter) is the electronic part of an I/O device that operates the device and connects it to the system bus. The device itself is mechanical (e.g. a disk drive) while the controller is electronic; the OS talks to the controller, not to the device. It contains:

• Registers - control, status and data registers the CPU reads and writes.
• Local buffer - holds a block of data being moved.
• Logic - converts serial bit streams to blocks, does error checking (e.g. ECC), and controls the device.

The OS communicates with it via a device driver, using port-mapped or memory-mapped I/O. When an operation finishes the controller raises an interrupt.

DMA (Direct Memory Access)

DMA lets the DMA controller move blocks of data between a device and main memory without CPU involvement for every word. The CPU sets up the address, count and direction, and receives one interrupt at the end.

DMA data-transfer methods

1. Burst (block) mode - the DMA controller takes the bus and transfers the entire block in one continuous burst before releasing it. It is the fastest, but the CPU is kept off the bus for the whole burst.
2. Cycle stealing mode - the controller takes the bus for one word (one cycle) at a time and then returns it to the CPU, repeating until the block is done. The CPU is slowed but never blocked for long.
3. Transparent (hidden) mode - the DMA transfers data only when the CPU is not using the bus (e.g. during internal operations). There is no CPU slowdown, but the transfer is slower and needs more complex hardware.

Another classification is by the number of bus cycles: fly-by (single-cycle) transfer moves data directly from device to memory in one cycle, while two-cycle (flow-through) transfer first reads the data into the controller and then writes it to memory.

Distributed operating system

A distributed OS controls a group of independent, networked computers and presents them to the user as a single system. Each node has its own processor and memory, and there is no shared memory or clock; nodes communicate by messages. It provides transparency (the user does not know where a file or process is), resource sharing, load balancing and fault tolerance.

Key components: distributed file system, remote process execution and migration, naming service, synchronisation of clocks and mutual exclusion, and RPC-based communication.

Advantages: resource sharing, faster computation, reliability, scalability. Challenges: network latency, security, complexity of synchronisation and failure handling.

Cloud-based operating system

A cloud OS manages and delivers computing, storage and application services over the Internet from a data centre, using virtualisation to pool many physical servers. Users access it through a browser or thin client and often do not run an OS locally (Chrome OS is a client-side example; OpenStack, Google Cloud and AWS provide cloud-level management).

Characteristics:

• On-demand self-service and elasticity: resources are scaled up or down automatically.
• Resource pooling through virtualisation: many virtual machines or containers share the same hardware.
• Pay-per-use metered service.
• Broad network access from any device.
• Service models: IaaS, PaaS and SaaS.

Advantages: low cost, scalability, accessibility from anywhere, easy maintenance and updates by the provider, built-in backup. Disadvantages: needs an Internet connection, security and privacy concerns, dependence on the provider.

Comparison: a distributed OS aims at making many machines work as one system and is usually owned by one organisation, whereas a cloud OS is service-oriented, relies on virtualisation and offers resources on demand to many tenants over the Internet.

Logical address (virtual address): the address generated by the CPU while a program runs. The set of all logical addresses generated by a program is its logical address space. The program sees only these addresses.

Physical address: the actual address of a location in main memory, loaded into the memory-address register. The set of all physical addresses corresponding to the logical addresses is the physical address space.

The two are identical in compile-time and load-time binding, but differ in execution-time binding. The memory-management unit (MMU) translates logical to physical addresses at run time. In the simplest scheme a relocation (base) register is added to every logical address: if the relocation register holds 14000, logical address 346 maps to physical address $14000 + 346 = 14346$. A limit register checks that the logical address is within range for protection.

Interrupt: a signal sent to the CPU by hardware (I/O device, timer) or software (trap, system call, exception) indicating an event that needs immediate attention. It makes the CPU suspend the current program, handle the event, and then resume.

Steps in interrupt handling

1. A device raises an interrupt signal on the interrupt request line.
2. The CPU finishes the current instruction, sees the signal and checks that it is not masked.
3. The CPU saves the state (program counter, PSW, registers) of the running process on the stack or PCB.
4. The CPU uses the interrupt number as an index into the interrupt vector table to find the address of the interrupt service routine (ISR), and jumps to it.
5. The ISR identifies the cause, services the device (e.g. copies data from a controller buffer, acknowledges the device), and may wake a blocked process.
6. After completion, the saved state is restored (return from interrupt) and the interrupted process resumes, or the scheduler picks another process.

Types and features

• Maskable (can be disabled) and non-maskable interrupts (e.g. hardware errors).
• Interrupt priority levels allow higher-priority interrupts to preempt lower ones.
• Hardware interrupts (I/O, timer), software interrupts / traps (system calls, divide by zero, page fault).
• Polling is the alternative, but it wastes CPU time; interrupts are more efficient.

OS as a resource manager

A computer has many resources: CPU time, memory, files, disks and I/O devices. Many programs and users compete for them. The OS is called a resource manager because it:

• keeps track of the status of each resource (who is using it, which are free);
• decides who gets which resource, when, and for how long (allocation and scheduling policies);
• allocates resources when requested and reclaims them when released;
• protects them so one program cannot interfere with another;
• shares them fairly and efficiently, e.g. CPU time-slicing and memory partitioning.

For example, the CPU scheduler allocates the CPU, the memory manager allocates memory, and the I/O manager controls devices.

Types of operating systems

1. Batch OS - similar jobs are grouped into batches and run one after another with no interaction. Efficient for large repetitive jobs, but no interactivity and long turnaround.
2. Multiprogramming OS - several jobs are kept in memory; when one waits for I/O the CPU switches to another, increasing CPU utilisation.
3. Time-sharing (multitasking) OS - the CPU is switched rapidly among users or tasks in small time slices, giving each an interactive feel (UNIX).
4. Multiprocessor (parallel) OS - two or more CPUs share memory and I/O; gives higher throughput and reliability.
5. Real-time OS - guarantees response within strict time limits. Hard real-time (missile control, pacemaker) never misses a deadline; soft real-time (multimedia) tolerates occasional misses.
6. Distributed OS - a collection of independent computers connected by a network that appears to users as a single system.
7. Network OS - runs on servers and provides file, printer and user sharing over a network; users are aware of the multiple machines.
8. Embedded and mobile OS - small OS for devices such as phones and appliances (Android, iOS).

The structure of an OS describes how its components are organised and interconnected.

1. Simple (monolithic) structure

The whole OS is one large program running in kernel mode; any procedure may call any other. Fast but hard to maintain and one bug can crash the system. Examples: MS-DOS, early UNIX.

+------------------------------+
|      Application programs    |
+------------------------------+
|   Resident system programs   |
+------------------------------+
|  MS-DOS device drivers       |
+------------------------------+
|        ROM BIOS drivers      |
+------------------------------+

2. Layered structure

The OS is divided into layers; layer N uses only services of layers below it (layer 0 hardware, layer N the user interface). Easy debugging and verification, but layers must be carefully defined and performance suffers from the overhead of passing through layers.

Layer N   : User interface
  ...
Layer 3   : I/O management
Layer 2   : Operator-process communication
Layer 1   : Memory management
Layer 0   : Hardware

3. Microkernel structure

Only the essential functions (basic process and memory management, IPC) remain in the kernel; other services (file system, device drivers, networking) run as user-level server processes communicating by message passing. Advantages: easy to extend and port, more reliable and secure. Disadvantage: message-passing overhead. Examples: Mach, QNX.

User space: [Application] [File server] [Device drivers] [Network]
                     ^ message passing ^
Kernel    : [ IPC | basic memory mgmt | CPU scheduling ]
Hardware

4. Modular structure

The kernel has a set of core components and loads others dynamically as modules (Linux, Solaris). Like layers but more flexible, and like a microkernel without message passing.

5. Hybrid structure

Combines approaches for performance and flexibility. Examples: Windows NT (microkernel plus kernel-mode services), macOS (Mach microkernel plus BSD components).

6. Virtual machine structure: a hypervisor layer lets several guest operating systems share one hardware platform.

Context switching

A context switch is the act of the OS saving the state (context) of the currently running process and loading the saved state of another one, so that the CPU can be given to the new process. The context is stored in the process control block (PCB): program counter, CPU registers, stack pointer, memory-management information, open files and scheduling information.

Steps: (1) an interrupt or system call occurs (timer expiry, I/O wait, higher-priority process ready); (2) the kernel saves the context of the running process into its PCB and sets its state; (3) the scheduler selects the next process; (4) the context of the chosen process is loaded from its PCB; (5) execution resumes. Context switching is pure overhead (no useful work is done), typically microseconds, and depends on hardware support.

How the OS decides which process runs

The CPU scheduler picks a process from the ready queue according to a scheduling algorithm: FCFS, shortest job first, round robin (time quantum), priority scheduling, multilevel queue and multilevel feedback queue. The choice depends on criteria such as CPU utilisation, throughput, turnaround time, waiting time and response time. Scheduling occurs when a process blocks, terminates, a time slice ends, or a higher-priority process arrives (preemptive scheduling).

Role of process priority

Each process is assigned a priority (internal: based on time limits, memory needs, I/O-to-CPU ratio; external: importance, user, payment). The scheduler runs the highest-priority ready process. A preemptive system stops a lower-priority process when a higher one arrives. Problem: starvation of low-priority processes, solved by aging (gradually increasing the priority of waiting processes).

Priority inversion

A situation in which a high-priority process H is indirectly blocked by a low-priority process L. L holds a lock on a resource that H needs; a medium-priority process M preempts L, so L cannot finish and release the lock, and H waits for M. (The Mars Pathfinder suffered this bug.)

Ways to manage it:

• Priority inheritance protocol: L temporarily inherits the priority of the highest-priority process waiting on its resource, so M cannot preempt it; L's priority is restored after it releases the resource.
• Priority ceiling protocol: each resource has a ceiling equal to the highest priority of any process that can use it; a process holding the resource runs at that ceiling priority.
• Disabling interrupts in short critical sections, and avoiding sharing of resources between very different priorities.

Arrival times: P1 = 0, P2 = 0, P3 = 2, P4 = 2, P5 = 2. Burst (service) times: P1 = 10, P2 = 1, P3 = 2, P4 = 1, P5 = 5. Priorities (5 is highest): P1 = 3, P2 = 1, P3 = 5, P4 = 4, P5 = 2.

Formulae: turnaround time (TAT) = completion time - arrival time; waiting time (WT) = TAT - burst time; throughput = number of processes / total time. Total burst = 19, so the schedule always finishes at time 19 and throughput = 5/19 = 0.263 process per unit time in every case.

(i) FCFS

Gantt chart:

Average TAT = 61/5 = 12.2, average WT = 42/5 = 8.4, throughput = 5/19 = 0.263.

(ii) SRTF (preemptive shortest remaining time first)

Gantt chart:

Average TAT = 32/5 = 6.4, average WT = 13/5 = 2.6, throughput = 0.263.

(iii) Priority scheduling (preemptive, 5 = highest)

Gantt chart:

Average TAT = 53/5 = 10.6, average WT = 34/5 = 6.8, throughput = 0.263.

(iv) Round Robin (quantum = 1)

Gantt chart (each slot is one time unit):

Average TAT = 43/5 = 8.6, average WT = 24/5 = 4.8, throughput = 0.263.

SRTF gives the smallest averages; FCFS is the worst because the long job P1 delays the others.

IPC (Inter-Process Communication) is the set of mechanisms by which cooperating processes exchange data and synchronise their actions. The two main models are shared memory and message passing; other mechanisms include pipes, FIFOs, message queues, semaphores, signals and sockets. Because processes sharing data can interfere with each other, synchronisation tools (semaphores, monitors) are needed to avoid race conditions.

The Readers-Writers problem

A shared data set (file or database) is accessed by two kinds of processes:

• Readers only read the data; any number may read at the same time.
• Writers read and modify the data; a writer needs exclusive access (no reader and no other writer at that time).

First readers-writers problem (readers' priority): no reader waits unless a writer already holds the data. This can starve writers. The second version gives priority to waiting writers, which can starve readers.

Solution with semaphores (readers' priority)

Shared variables: int readcount = 0; semaphore mutex = 1 (protects readcount) and semaphore wrt = 1 (exclusive access to the data).

Writer:

do {
    wait(wrt);
    /* writing is performed */
    signal(wrt);
} while (true);

Reader:

do {
    wait(mutex);
    readcount++;
    if (readcount == 1)
        wait(wrt);        // first reader locks out writers
    signal(mutex);

    /* reading is performed */

    wait(mutex);
    readcount--;
    if (readcount == 0)
        signal(wrt);      // last reader lets writers in
    signal(mutex);
} while (true);

Explanation

• The first reader to arrive executes wait(wrt), blocking writers; later readers just increment readcount and read concurrently.
• The last reader to leave executes signal(wrt), letting a waiting writer enter.
• A writer must obtain wrt, so it excludes both readers and other writers.
• mutex ensures readcount is updated atomically.

Drawback: writers may starve if readers keep arriving. The writers' priority version adds a second semaphore and a writer count so that new readers wait whenever a writer is waiting.

Deadlock: a state in which every process in a set is waiting for a resource held by another process in the set, so none of them can proceed. It requires mutual exclusion, hold and wait, no pre-emption and circular wait to hold simultaneously.

Resource Allocation Graph (RAG)

A RAG is a directed graph used to describe resource allocation.

• Vertices: processes $P_1,\dots,P_n$ (circles) and resource types $R_1,\dots,R_m$ (rectangles; dots inside show instances).
• Request edge $P_i \to R_j$: $P_i$ is waiting for an instance of $R_j$.
• Assignment edge $R_j \to P_i$: an instance of $R_j$ is allocated to $P_i$.

Rules: if the graph has no cycle, there is no deadlock. If there is a cycle and each resource type has a single instance, deadlock exists. If resource types have multiple instances, a cycle is necessary but not sufficient.

Example: $P_1$ holds $R_1$ and requests $R_2$; $P_2$ holds $R_2$ and requests $R_1$. Edges: $R_1\to P_1$, $P_1\to R_2$, $R_2\to P_2$, $P_2\to R_1$. This forms the cycle $P_1 \to R_2 \to P_2 \to R_1 \to P_1$, so with single instances both processes are deadlocked.

Banker's algorithm (deadlock avoidance)

Used for resource types with multiple instances. Each process declares its maximum need in advance. A request is granted only if the system stays in a safe state (there exists a sequence in which every process can finish).

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

• Available[m] - free instances of each type.
• 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 Finish[i] = true for all $i$, the state is safe.

Resource-request algorithm for $P_i$ with Request[i]: if Request $>$ Need, error; if Request $>$ Available, wait; otherwise pretend to allocate (Available -= Request, Allocation += Request, Need -= Request) and run the safety algorithm. If safe, the allocation stands; if not, restore the old state and make $P_i$ wait.

Example

Five processes, resource types A, B, C with Available = (3, 3, 2).

• Work = (3,3,2). P1 needs (1,2,2) $\le$ Work: run; Work = (3,3,2)+(2,0,0) = (5,3,2).
• P3 needs (0,1,1) $\le$ (5,3,2): run; Work = (5,3,2)+(2,1,1) = (7,4,3).
• P4 needs (4,3,1) $\le$ (7,4,3): run; Work = (7,4,3)+(0,0,2) = (7,4,5).
• P2 needs (6,0,0) $\le$ (7,4,5): run; Work = (7,4,5)+(3,0,2) = (10,4,7).
• P0 needs (7,4,3) $\le$ (10,4,7): run; Work = (10,5,7).

Safe sequence: $\langle P_1, P_3, P_4, P_2, P_0\rangle$, so the state is safe.

Coalescing

Coalescing is the merging of two or more adjacent free memory blocks (holes) into a single larger free block. When a process terminates and releases memory next to another free hole, the two holes are combined. This reduces external fragmentation and makes large requests easier to satisfy. Example: holes of 4 KB and 6 KB next to each other become one 10 KB hole.

Compaction

Compaction is the shuffling of the memory contents of allocated blocks to one end of memory so that all free holes join into one large contiguous block. It solves external fragmentation but is possible only when relocation is dynamic (done at execution time using relocation registers), and it is expensive since it consumes CPU time moving data. Example: allocated blocks at 0-10 KB, 20-30 KB and 50-60 KB are moved together to 0-30 KB, leaving a single 70 KB hole.

Paging versus segmentation

Example

Paging: with 1 KB pages, logical address 2600 gives page $= \lfloor 2600/1024 \rfloor = 2$ and offset $= 2600 - 2048 = 552$. If page 2 is in frame 7, physical address $= 7 \times 1024 + 552 = 7720$.

Segmentation: if segment 2 has base 4000 and limit 500, logical address (2, 300) maps to $4000 + 300 = 4300$. Address (2, 600) is invalid since $600 > 500$ and causes a trap.

File attributes

Attributes are the metadata kept about a file: name, identifier (inode number), type, location (pointer to disk blocks), size, protection (read, write, execute permissions), and time, date and user identification (creation, last modification, last use, owner). They are kept in the directory entry or inode.

File allocation methods

These define how disk blocks are allocated to files.

1. Contiguous allocation

Each file occupies a set of consecutive blocks. The directory stores the starting block and the length. A file starting at block $b$ with length $n$ occupies $b, b+1,\dots,b+n-1$.

Advantages:

• Simple; supports both sequential and direct access (block $i$ is at $b+i$).
• Minimal seek time and fast access.

Disadvantages:

• External fragmentation; compaction needed.
• File size must be known when created; growth is difficult.
• Finding space for a new file (first fit, best fit) is costly.

2. Linked list allocation

Each file is a linked list of disk blocks that may be scattered. Each block contains data and a pointer to the next block; the directory stores the first (and last) block.

Advantages:

• No external fragmentation; files can grow dynamically.
• File size need not be known in advance.

Disadvantages:

• Only efficient for sequential access; direct access to block $i$ needs $i$ pointer follows.
• Pointer space reduces usable block size.
• Poor reliability: a lost or damaged pointer breaks the chain.

3. Linked list allocation using an index (FAT / indexed allocation)

Pointers are collected from the blocks into a table. In the File Allocation Table (FAT) each disk block has one entry holding the number of the next block (or an end-of-file mark); the directory stores the first block number. In indexed allocation each file has an index block whose $i$-th entry points to the $i$-th data block of the file.

Advantages:

• Whole block is available for data.
• Random access is efficient (the chain is in the table, which can be cached in memory).
• No external fragmentation.

Disadvantages:

• The table (or index block) occupies space; the FAT of a large disk must be held in memory and grows with disk size.
• An index block wastes space for small files and a single index block limits file size unless linked or multilevel indexes are used.

Distributed operating system

A distributed operating system manages a collection of independent computers (nodes), each with its own processor and memory, connected by a network, and makes them appear to users as a single coherent system. Users need not know where a resource or process is located. Resources, computation and files are shared across the nodes (e.g. Amoeba, LOCUS). Typical features are transparency (location, migration, replication, failure), process migration and distributed file systems.

Advantages over a centralized operating system

1. Resource sharing: a user at one node can use files, printers and CPU power on other nodes.
2. Computation speed-up (load sharing): a job is divided into sub-computations that run in parallel on different nodes, and load is balanced by moving processes to lightly loaded nodes.
3. Reliability and fault tolerance: the failure of one node does not stop the whole system; other nodes take over, and replicated data survives failures. A centralized system has a single point of failure.
4. Scalability: capacity grows by adding more nodes, while a central machine is limited by hardware.
5. Better price/performance: many cheap computers offer more power per unit cost than a large mainframe.
6. Communication: users and applications on different sites can exchange messages, files and e-mail easily.
7. Availability and response time: local nodes serve local users, giving quicker response and lower contention.
8. Incremental growth and geographic distribution: resources can be placed near users.

Disadvantages (for balance): complex software, network dependence, security issues and difficult coordination.

Remote Procedure Call (RPC) is a communication mechanism that allows a program on one machine to call a procedure that executes on another machine over a network, as if it were a local procedure call. It hides the details of message passing, so distributed applications are easier to write.

Working (client-server model)

1. The client calls a local client stub with the parameters.
2. The stub marshals (packs) the parameters into a message and asks the OS to send it.
3. The message is transmitted over the network to the server machine.
4. The server stub receives the message, unpacks (unmarshals) the parameters and calls the actual procedure on the server.
5. The result is marshalled and sent back; the client stub unmarshals it and returns it to the caller.

Client -> Client stub -> network -> Server stub -> Server procedure
Client <- Client stub <- network <- Server stub <- Server procedure

Issues: differences in data representation (handled by external data representation such as XDR), binding of client to server (through a name or port-mapper service), failures (call semantics such as at-most-once or at-least-once), and the slower speed compared with local calls. Examples: Sun RPC, Java RMI, gRPC.

Windows security protects users, data and system resources through several cooperating features.

• Authentication: users sign in with a password, PIN, biometrics (Windows Hello) or smart card; in domains Kerberos is used. Each user and group has a unique security identifier (SID).
• Access tokens: at login the system creates a token holding the user's SID, group SIDs and privileges, which is attached to every process the user starts.
• Authorization: each object (file, registry key, process) has a security descriptor with a DACL listing access control entries (allow/deny for a user or group) and a SACL for audit logging. The Security Reference Monitor compares the token to the DACL on each access.
• User Account Control (UAC): runs applications with standard rights unless the user approves elevation.
• NTFS permissions and EFS/BitLocker: file-level permissions and encryption of files or whole disks.
• Windows Defender / Firewall: antivirus and network traffic filtering; Windows Update delivers security patches.
• Other: Group Policy, Secure Boot, audit policies and event logs.

Operating system

An operating system is a program that manages the computer hardware and provides a basis for application programs; it acts as an interface between the user and the hardware and as a manager of resources (CPU, memory, files, devices).

 +-------------------------------+
 |           Users               |
 +-------------------------------+
 |  Application programs         |
 +-------------------------------+
 |      Operating system         |
 +-------------------------------+
 |  Hardware (CPU, memory, I/O)  |
 +-------------------------------+

Types of operating system

1. Batch operating system

Jobs with similar needs are collected into a batch by an operator and run one after another. The user does not interact with the job while it runs.

Jobs -> [Batch queue] -> [Operating system / CPU] -> Output

Advantages: good for large repetitive work. Disadvantages: no interaction, CPU idle during I/O, long turnaround time.

2. Multiprogramming operating system

Several jobs reside in memory; when one waits for I/O, the CPU runs another. This raises CPU utilisation.

3. Time-sharing (multitasking) operating system

The CPU is given to each task for a short time quantum in turn, so many users can use the system interactively at once.

User1 -\
User2 --> [Scheduler (round robin)] -> CPU
User3 -/

4. Multiprocessor (parallel) operating system

Several CPUs share the bus, memory and devices and run processes simultaneously. Gives higher throughput and fault tolerance.

5. Real-time operating system

Processing must be done within fixed time constraints. Hard real-time systems (air-traffic control, medical devices) cannot miss deadlines; soft real-time systems (video streaming) can tolerate some delay.

6. Distributed operating system

Many independent computers, each with its own processor and memory, are connected through a network and cooperate so that the user sees one system. Advantages: resource sharing, speed-up, reliability, scalability.

 [Node A]--+
 [Node B]--+--- Network ---+-- Users see one system
 [Node C]--+

7. Network operating system

Runs on a server and provides services (file, print, security) to client computers over a network; users know which machine they use (Windows Server, Novell NetWare).

8. Embedded/mobile operating systems such as Android and iOS are designed for devices with limited resources.

Process state transition

A process changes state during its life. The main states are:

• New: the process is being created.
• Ready: loaded in memory, waiting for the CPU.
• Running: its instructions are being executed.
• Waiting (blocked): waiting for an event such as I/O completion.
• Terminated: finished execution.

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

Transitions: new→ready (admitted), ready→running (dispatched), running→ready (timer interrupt/preemption), running→waiting (I/O request or event wait), waiting→ready (event occurred), running→terminated (exit).

Process control block (PCB)

A data structure the OS keeps for every process; it represents the process in the system. Contents:

• Process state and process ID.
• Program counter and CPU registers (saved at context switch).
• CPU-scheduling information (priority, pointers to queues).
• Memory-management information (base/limit registers, page tables).
• Accounting information (CPU time used, time limits).
• I/O status information (open files, allocated devices).
• Parent and child pointers.

Operations on processes

1. Process creation: a parent process creates children using a system call such as fork() (UNIX) or CreateProcess(). The child gets its own PID; resources are shared or not and the parent either waits or continues. A process is created at system start, by a user request, or by another process.
2. Process termination: a process ends with exit() after its last statement, and resources are deallocated. A parent can terminate a child with abort/kill if the child exceeds resources, its task is no longer needed, or the parent exits.
3. Process scheduling / dispatching: selecting a process from the ready queue and giving it the CPU.
4. Blocking and waking up: a process waiting for an event is blocked, and awakened when the event occurs.
5. Suspension and resumption: a process can be suspended (swapped out) and resumed later.
6. Process communication and synchronisation between cooperating processes.

Processes: P1 (AT 0, BT 3, Pr 2), P2 (AT 2, BT 7, Pr 4), P3 (AT 4, BT 4, Pr 1), P4 (AT 4, BT 2, Pr 2), P5 (AT 3, BT 4, Pr 5).

TAT = completion time - arrival time.

(i) FCFS (order of arrival: P1, P2, P5, P3, P4)

TAT: P1 = 3, P2 = 8, P3 = 14, P4 = 16, P5 = 11.

$\text{Average TAT} = \frac{3+8+14+16+11}{5} = \frac{52}{5} = 10.4$

(ii) LJF (longest job first, non-preemptive)

At time 3 only P2 has arrived, so it runs. At time 10, P5 (4), P3 (4) and P4 (2) are waiting; P5 and P3 tie, so the earlier arrival P5 is taken first.

TAT: P1 = 3, P2 = 8, P5 = 11, P3 = 14, P4 = 16.

$\text{Average TAT} = \frac{52}{5} = 10.4$

(iii) Priority (preemptive) - a larger number means higher priority; ties are broken by earlier arrival.

P2 (priority 4) preempts P1 at time 2, and P5 (priority 5) preempts P2 at time 3.

TAT: P1 = 14, P2 = 11, P3 = 16, P4 = 12, P5 = 4.

$\text{Average TAT} = \frac{14+11+16+12+4}{5} = \frac{57}{5} = 11.4$

(iv) Round Robin (quantum = 3)

Ready queue: a process arriving at the same moment as a preempted one is queued first.

Completion: P1 = 3, P4 = 14, P5 = 18, P3 = 19, P2 = 20.

TAT: P1 = 3, P2 = 18, P3 = 15, P4 = 10, P5 = 15.

$\text{Average TAT} = \frac{3+18+15+10+15}{5} = \frac{61}{5} = 12.2$

Deadlock: a situation in which a set of processes are all blocked, each holding some resources while waiting for a resource held by another process in the set, so none can ever proceed.

Deadlock can occur only if all four Coffman conditions hold at the same time: mutual exclusion, hold and wait, no pre-emption and circular wait. Deadlock prevention ensures that at least one of them can never hold.

1. Eliminating mutual exclusion Make resources sharable where possible (read-only files need no exclusive access). Intrinsically non-sharable resources such as printers cannot be handled this way; spooling can help by letting only the spooler daemon use the printer.

2. Eliminating hold and wait

• Protocol A: a process must request and be allocated all resources before it begins execution.
• Protocol B: a process may request resources only when it holds none; it must release everything before asking for more.

Disadvantages: poor resource utilisation (resources are held long before use) and possible starvation of processes needing popular resources.

3. Allowing pre-emption If a process holding resources requests another that cannot be given immediately, all its held resources are taken away; it is restarted only when it can regain the old and the new resources. Alternatively, resources are taken from a waiting process on demand. Practical for resources whose state can be saved and restored (CPU registers, memory pages), not for printers or tape drives.

4. Eliminating circular wait Assign each resource type a unique number and require processes to request resources in increasing order of number. If a process holding resource $R_i$ requests $R_j$, then $j > i$ is required. A cycle would need some process to request a lower-numbered resource, so none can form. Disadvantage: the order may not suit the natural order of use and reduces convenience.

Conclusion: prevention is simple and guarantees no deadlock, but it constrains how resources are requested and lowers utilisation and throughput. This is why systems also use avoidance (Banker's algorithm), detection and recovery.

File types

• Regular files - user information in ASCII (text) or binary form (executables, images).
• Directories - system files that maintain the structure of the file system.
• Special files - character special files (terminals, printers) and block special files (disks) in UNIX.
• Common categories by extension: executable (exe), source (c, java), object (obj), text (txt), archive (zip), multimedia (mp3, jpg).

File structures

How the contents of a file are organised:

1. Unstructured byte sequence - the OS sees only bytes; the application gives meaning (UNIX, Windows). Most flexible.
2. Record sequence - a file is a sequence of fixed-length records; read/write works on one record (used in old mainframes).
3. Tree of records - records of variable length, each with a key field, organised in a tree and searched by key (used in commercial data processing, e.g. ISAM).

File access methods

• Sequential access - information is processed in order, one record after another (read next, write next); a pointer moves automatically. Used by editors and compilers.
• Direct (random) access - the file consists of fixed-length blocks; any block can be read or written directly by number (read n, write n). Used by databases.
• Indexed access - an index holds pointers to blocks/records; the index is searched (often by binary search) to find the record, and then the data is accessed directly. Used with large files, such as indexed sequential access method (ISAM).

Memory hierarchy

Memory hierarchy arranges the different storage devices of a computer in levels according to speed, cost and capacity. Going down the hierarchy, access time and cost per bit fall, while capacity grows. The aim is to give the CPU the illusion of a memory that is as large as the cheapest level and as fast as the fastest level. This works because of the principle of locality of reference (programs tend to reuse recently used data and nearby addresses).

        Registers            (smallest, fastest, costliest)
        Cache (L1, L2, L3)
        Main memory (RAM)
        Secondary storage (SSD / hard disk)
        Tertiary storage (optical disk, tape)   (largest, slowest, cheapest)

Data move between adjacent levels in blocks. A hit is when the CPU finds the data in the upper level, and a miss means it must be fetched from the next lower level.

Contiguous memory allocation

Each process is loaded into one single block of consecutive memory addresses. Main memory is divided into the OS area (usually low memory) and the user area.

• Fixed (static) partitioning: memory is divided into partitions of fixed size in advance. A process is placed in a partition large enough to hold it. The unused part inside the partition is wasted (internal fragmentation). The degree of multiprogramming is limited by the number of partitions.
• Variable (dynamic) partitioning: a partition is created exactly as large as the process needs. Holes are left when processes terminate, producing external fragmentation (enough total free memory but not in one piece). Holes are chosen by first-fit, best-fit or worst-fit, and compaction can remove the fragmentation.

Example: memory has partitions of 100 KB, 500 KB, 200 KB, 300 KB and 600 KB. A process of 212 KB is placed in the 300 KB partition by best fit, so 88 KB is lost as internal fragmentation. Another example with a 1000 KB user area: loading P1 (200 KB), P2 (300 KB), P3 (400 KB) leaves 100 KB free. If P2 leaves and a 350 KB process arrives, the 300 KB hole and the 100 KB hole are separate, so it cannot be loaded even though 400 KB is free in total. This is external fragmentation.

Advantages: simple, little overhead, fast access with base and limit registers. Disadvantages: fragmentation, the whole process must fit in memory, no sharing, poor utilisation.

Non-contiguous memory allocation

A process is divided into parts which can be placed in different, scattered areas of memory. This removes the need for one large hole and reduces external fragmentation. The main techniques are:

• Paging: the logical address space is divided into fixed-size pages and physical memory into frames of the same size. A page table maps each page to a frame. Example: a 10 KB process with 4 KB pages needs 3 pages. They may be loaded into frames 5, 2 and 9 and the page table is $0\to5$, $1\to2$, $2\to9$. Only the last page has internal fragmentation (2 KB).
• Segmentation: the process is divided into logical variable-sized segments (code, data, stack) and a segment table stores base and limit of each segment.
• Segmented paging: each segment is further divided into pages.

Advantages: better memory utilisation, no or little external fragmentation, supports virtual memory and sharing. Disadvantages: more complex hardware (page and segment tables, MMU), extra memory reference for address translation.

Distributed system

A distributed system is a collection of independent computers (nodes), connected by a network and equipped with distributed system software, that appears to its users as a single coherent system. The nodes do not share memory or a clock and communicate only by passing messages. Examples are the World Wide Web, cluster computing, and banking networks.

Advantages over a centralized system

1. Resource sharing: users at one site can use printers, files and processors at other sites.
2. Computation speedup: a job can be split and run in parallel on several nodes (load sharing).
3. Reliability and fault tolerance: if one node fails, the others continue, so the whole system does not stop.
4. Scalability: the system can grow by adding more nodes (incremental growth).
5. Better price/performance: many cheap computers give more power per cost than one large mainframe.
6. Communication: users can exchange mail, files and messages easily.
7. Geographic distribution: data and processing can be kept close to the users, which improves response time.

Disadvantages

1. Complexity: designing, implementing and debugging distributed software is much harder.
2. Security and privacy: data travel over a network and can be intercepted, and more points are open to attack.
3. Network dependence: a network failure or congestion can cut off the system or slow it.
4. Synchronization and consistency: there is no global clock or shared memory, so keeping data consistent and ordering events is difficult.
5. Higher setup and maintenance cost for networking equipment and administration.
6. Less software available than for centralized systems, and difficulty with heterogeneity (different hardware and OS).
7. Concurrency problems such as distributed deadlock and partial failure that are hard to detect.

OS as an extended machine (top-down view)

The raw hardware is very difficult to program. A programmer writing to a disk would have to deal with controller registers, seek, rotation, error codes and so on. The operating system hides these ugly details and presents a simpler, cleaner, higher-level abstraction, such as the file, process, address space and socket. For example, the programmer just calls read(fd, buf, n) without knowing how the disk works. The OS thus turns the bare hardware into an "extended" or "virtual" machine that is easier to use, portable across different hardware, and offers uniform services through system calls.

OS as a resource manager (bottom-up view)

A computer has many resources: CPU, memory, disks, printers, network interfaces and files. Many programs and users compete for them at the same time. The OS acts as a manager that:

• keeps track of the status of each resource (who is using what),
• decides which process gets a resource, when, and for how long (CPU scheduling, memory allocation),
• allocates and later reclaims the resource,
• protects processes from each other and resolves conflicting requests (for example, two programs sending output to the printer at once),
• shares resources in two ways, in time (CPU, printer, taken in turns) and in space (memory, disk, each gets a part).

This ensures orderly, fair and efficient use of the hardware. Both views are consistent: the OS hides complexity from users (extended machine) and controls the hardware for them (resource manager).

Types of kernel

The kernel is the core part of the OS which runs in privileged mode and manages the CPU, memory and devices.

1. Monolithic kernel: the whole OS (scheduler, memory manager, file system, device drivers) runs in a single large program in kernel space. Services call each other directly, so it is fast, but it is large, hard to maintain, and one faulty driver can crash the whole system. Examples: traditional UNIX, Linux.
2. Microkernel: only the minimum functions (inter-process communication, basic scheduling, low-level memory management) stay in the kernel. Other services such as file system and drivers run as user-space servers. It is more reliable, secure and easy to extend, but slower because of the message passing between the user processes. Examples: Mach, QNX, MINIX.
3. Hybrid kernel: combines both approaches, keeping a microkernel-like structure but running more services in kernel space for speed. Examples: Windows NT, macOS (XNU).
4. Exokernel: the kernel only allocates and protects the hardware resources, and applications manage them directly through library operating systems. It gives high performance and flexibility.
5. Layered / modular kernels: the OS is divided into layers or loadable modules, each using the services of the layer below (for example, THE system, Linux loadable modules).

Memory management with swapping

Swapping is a memory management technique in which a process is temporarily moved from main memory to a backing store (a fast disk area, called swap space) and later brought back into memory to continue execution. It allows the total memory required by all processes to exceed the physical memory, and so increases the degree of multiprogramming.

        Main memory                     Backing store (disk)
   +------------------+   swap out   +------------------+
   |  OS              |              |                  |
   |  Process P1  ----+------------->|  P1 image        |
   |  Process P2      |   swap in    |                  |
   |  Process P3  <---+--------------|  P4 image        |
   +------------------+              +------------------+

Working:

1. When memory is full, or a process blocks for long (or a higher-priority process arrives), the memory manager (medium-term scheduler) selects a victim process and swaps it out. Its image is written to the disk, and the memory is freed.
2. When the process is ready to run again, it is swapped in to a free area (not necessarily the same place, if address binding is done at execution time).
3. In priority-based scheduling the swapping policy is called roll out, roll in.

Points to note:

• Swapping time is mostly the transfer time, which is proportional to the size of the process. For example, a 100 MB process at 50 MB/s needs about 2 s each way.
• A process waiting for I/O must not be swapped out if the I/O is going into its memory, unless the I/O uses OS buffers.
• Swapping with variable partitions leads to holes in memory, which are handled by coalescing adjacent holes or by compaction.
• Modern systems swap pages rather than whole processes (paging), and this is the basis of virtual memory.

Advantages: more processes can be run than fit in memory, better CPU utilisation, and simple implementation. Disadvantages: large swap time overhead, wasted CPU time if too much swapping occurs (thrashing), and fragmentation.

Operating system

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

Structure of operating systems

1. Monolithic structure

The entire OS is a single program running in kernel mode, composed of a collection of procedures that can call each other freely. There is little information hiding. User programs request services through system calls (trap into the kernel). Simple and fast, but difficult to debug, modify and maintain, and a bug anywhere can crash the system. Examples: early UNIX, MS-DOS (mostly).

2. Layered structure

The OS is divided into a number of layers; layer 0 is the hardware and layer N is the user interface. Each layer uses only the services of the lower layers.

 Layer N   : User interface
 Layer N-1 : ...
 Layer 3   : I/O management
 Layer 2   : Operator-process communication
 Layer 1   : Memory management
 Layer 0   : Hardware / CPU scheduling

Advantages are simple design, easy debugging and verification, and modularity. Disadvantages are the difficulty of defining the layers (a layer can only use lower ones), and lower speed because a request passes through many layers. Example: THE system.

3. Microkernel structure

Only the essential functions (process and memory basics, IPC) stay in the kernel; file systems, drivers and other services run as user-level processes which communicate by message passing. It is reliable, secure and easy to extend and port. The main disadvantage is the performance overhead of message passing. Examples: Mach, QNX, MINIX.

4. Modular structure

The kernel has a set of core components and other modules are loaded dynamically at boot or run time (for example Linux loadable kernel modules, Solaris). It is like the layered approach but more flexible, since any module can call any other.

5. Client-server model

A variation of the microkernel in which servers (file server, process server) offer services to clients through messages, which fits easily into distributed systems.

6. Virtual machines

A virtual machine monitor (hypervisor) runs on bare hardware and creates several virtual copies of the hardware, each of which can run its own OS (for example VMware, VirtualBox, IBM VM/370).

7. Hybrid structure

A mix of the above, for example Windows NT and macOS, which combine a microkernel design with monolithic-style performance.

Can a process exist without a state? No.

A process is a program in execution. At every instant of its life, the OS must know what the process is doing, whether it is running on the CPU, ready and waiting for the CPU, or blocked waiting for some event. This status is its state, and the scheduler's decisions depend on it. A process without a state cannot be scheduled, resumed or tracked, so every process must always be in exactly one state, and it changes state only by the defined transitions. Even a newly created process is in the "new" state and a finished one is in "terminated" state until the OS clears its entries.

Process state transition diagram (five-state model)

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

Transitions:

• New to Ready: the process is created and admitted to the ready queue.
• Ready to Running: the scheduler dispatches the process to the CPU.
• Running to Ready: its time quantum expires or a higher-priority process arrives (preemption).
• Running to Blocked: the process requests I/O or waits for an event.
• Blocked to Ready: the I/O or event completes.
• Running to Terminated: the process finishes or is killed.

Process Control Block (PCB)

The state is stored along with all other information about the process in a data structure called the PCB (task control block), one per process. It is created when the process is created and removed when the process terminates. A PCB holds:

1. Process identifier (PID) and parent PID.
2. Process state (new, ready, running, blocked, terminated).
3. Program counter, the address of the next instruction.
4. CPU registers and stack pointer, saved on a context switch.
5. CPU scheduling information: priority, pointers to scheduling queues.
6. Memory management information: base and limit registers, page or segment tables.
7. Accounting information: CPU time used, time limits, job number.
8. I/O status information: open files, allocated devices.

When the process is moved from Running to Ready or Blocked, the OS saves the CPU context into its PCB, and when it is dispatched again the context is reloaded from the PCB. Thus the state field of the PCB is what represents the process in the transition diagram, and a process cannot exist without it. Hence the view is justified: a process always has a state, and the PCB records it.

Critical region (critical section)

The part of a program in which a process accesses shared resources (shared variables, files, devices) is called its critical region or critical section. If two processes execute their critical sections at the same time, the result depends on the order of execution (a race condition) and shared data may become inconsistent. Hence a solution must satisfy these conditions:

1. Mutual exclusion: no two processes may be inside their critical regions at the same time.
2. Progress: a process outside its critical region must not block others from entering it.
3. Bounded waiting: no process should wait forever to enter (no starvation).
4. No assumptions about CPU speed or the number of CPUs.

Ways to achieve mutual exclusion

1. Disabling interrupts: a process disables interrupts before entering the critical region, and enables them after. It is simple but dangerous for user processes and does not work on multiprocessors.
2. Lock variables: a shared flag is tested and set before entering. It fails because testing and setting are separate steps (a race on the lock itself).
3. Strict alternation: processes take turns using a shared variable turn. It uses busy waiting and violates progress, since a slow process blocks a fast one.
4. Peterson's solution: a software solution for two processes (below).
5. Hardware support: the TSL (test and set lock) instruction or the swap instruction, which test and set a memory word atomically.
6. Sleep and wakeup, semaphores, mutexes and monitors: blocking primitives which avoid busy waiting.
7. Message passing.

Peterson's solution

Peterson's algorithm (1981) solves the critical section problem for two processes, say $P_0$ and $P_1$, using two shared variables: turn, indicating whose turn it is to enter, and an array flag[2], where flag[i] = TRUE shows that process $i$ wants to enter.

#define FALSE 0
#define TRUE  1
#define N     2

int turn;               /* whose turn is it? */
int flag[N];            /* all values initially FALSE */

void enter_region(int process)      /* process is 0 or 1 */
{
    int other = 1 - process;
    flag[process] = TRUE;           /* show interest */
    turn = other;                   /* give the turn to the other process */
    while (flag[other] == TRUE && turn == other)
        ;                           /* busy wait */
}

void leave_region(int process)
{
    flag[process] = FALSE;          /* leaving the critical region */
}

Use:

   enter_region(i);
   /* critical section */
   leave_region(i);
   /* remainder section */

How it works: a process first sets its flag, then politely gives the turn to the other. It waits only if the other process also wants to enter and it is the other's turn. If both processes call enter_region at almost the same time, both set their flags, but turn is overwritten by whichever writes last; the one that wrote first gets in, and the other waits until the first calls leave_region.

Proof of the properties: mutual exclusion holds, because for both to be in the critical section, both would need turn to equal the other's number at the same time, which is impossible as turn has a single value. Progress and bounded waiting hold, since a process waits for at most one turn of the other process. Its drawbacks are busy waiting (wasted CPU time), and that it handles only two processes.

Formulae: Turnaround time (TAT) = Completion time (CT) - Arrival time (AT); Waiting time (WT) = TAT - Burst time (BT).

i. First Come First Serve

Gantt chart:

| P1 | P2 | P3 | P4 |
0    11   25   57   76

$\text{Avg TAT}=\frac{11+22+52+67}{4}=\frac{152}{4}=38 \text{ s},\qquad \text{Avg WT}=\frac{0+8+20+48}{4}=\frac{76}{4}=19 \text{ s}$

ii. Shortest Job First (non-preemptive)

At time 0 only P1 is present, so it runs to completion at 11. P2 (14), P3 (32) and P4 (19) are then waiting; the shortest is P2, then P4, then P3.

| P1 | P2 | P4 | P3 |
0    11   25   44   76

$\text{Avg TAT}=\frac{11+22+71+35}{4}=\frac{139}{4}=34.75 \text{ s},\qquad \text{Avg WT}=\frac{0+8+39+16}{4}=\frac{63}{4}=15.75 \text{ s}$

iii. Round Robin (quantum = 5)

Ready queue changes: P1 runs 0-5 (6 left), P2 and P3 have arrived and queue is P2, P3, P1; P4 arrives at 9, and so on.

|P1|P2|P3|P1|P4|P2|P3|P1|P4|P2|P3|P4|P3|P4|P3|P3|P3|
0  5  10 15 20 25 30 35 36 41 45 50 55 60 64 69 74 76

(P1: 0-5, 15-20, 35-36; P2: 5-10, 25-30, 41-45; P3: 10-15, 30-35, 45-50, 55-60, 64-69, 69-74, 74-76; P4: 20-25, 36-41, 50-55, 60-64.)

$\text{Avg TAT}=\frac{36+42+71+55}{4}=\frac{204}{4}=51 \text{ s},\qquad \text{Avg WT}=\frac{25+28+39+36}{4}=\frac{128}{4}=32 \text{ s}$

iv. Shortest Remaining Time Next (preemptive SJF)

At 3, P2 (14) arrives but P1 has only 8 left, so P1 continues. At 5, P3 (32) and at 9, P4 (19) arrive, both longer than P1's remaining time. So P1 finishes at 11, then P2 (14), P4 (19) and P3 (32) run in order of remaining time. No further preemption happens.

| P1 | P2 | P4 | P3 |
0    11   25   44   76

$\text{Avg TAT}=\frac{139}{4}=34.75 \text{ s},\qquad \text{Avg WT}=\frac{63}{4}=15.75 \text{ s}$

Summary

SJF and SRTN give the least waiting time here; Round Robin gives the worst averages for these long jobs because of the frequent switching, though it is better for response time.

Deadlock

A deadlock is a situation in which a set of processes is permanently blocked, each waiting for a resource that is held by another process in the same set, so none of them can ever proceed. Example: process P1 holds the printer and requests the scanner, while P2 holds the scanner and requests the printer; both wait forever.

Necessary conditions (Coffman conditions)

A deadlock can occur only if all four of the following hold at the same time:

1. Mutual exclusion: at least one resource is non-sharable, 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 after the task completes.
4. Circular wait: there is a cycle of processes $P_0, P_1, \dots, P_n$ where each $P_i$ waits for a resource held by $P_{i+1}$ and $P_n$ waits for one held by $P_0$.

Deadlock prevention

Prevention means ensuring that at least one of the four conditions can never hold.

1. Eliminating mutual exclusion: make resources sharable where possible (for example read-only files, or spooling a printer). Some resources are inherently non-sharable, so this is not always possible.
2. Eliminating hold and wait: a process must request all its resources at once before it starts (and gets them only if all are available), or it must release all its held resources before requesting new ones. Disadvantages are low resource utilisation and possible starvation.
3. Eliminating no preemption: if a process holding resources requests another one that is not available, all of its resources are preempted (released) and it restarts later when it can get all of them; or a resource is taken from a waiting process if requested by another. It works for resources whose state can be saved (CPU, memory) but not for printers or tape drives.
4. Eliminating circular wait: assign a unique number to every resource type and require processes to request resources only in increasing order of number. If a process holds resource $R_i$ it may request only $R_j$ with $j>i$. This breaks cycles, and is the most practical method, though the ordering may be inconvenient for programmers.

Other approaches: deadlock avoidance (for example the Banker's algorithm), deadlock detection and recovery, and ignoring the problem (the ostrich algorithm, used in UNIX and Windows).

Partitions (in order): 100 KB, 500 KB, 200 KB, 300 KB, 600 KB. Processes: 212 KB, 417 KB, 112 KB, 426 KB.

First-fit (allocate the first partition that is big enough)

• 212 KB goes to 500 KB partition (the first that fits); leftover $500-212=288$ KB.
• 417 KB: 100 no, 288 no, 200 no, 300 no, 600 yes. Placed in 600 KB; leftover $600-417=183$ KB.
• 112 KB: 100 no, 288 yes. Placed in the leftover of the 500 KB partition; leftover $288-112=176$ KB.
• 426 KB: free blocks are 100, 176, 200, 300, 183 KB. None is large enough, so 426 KB must wait.

Best-fit (allocate the smallest partition that is big enough)

• 212 KB: candidates 500, 300, 600; smallest is 300 KB. Leftover 88 KB.
• 417 KB: candidates 500, 600; smallest is 500 KB. Leftover 83 KB.
• 112 KB: candidates 200 (and 600 etc.), smallest is 200 KB. Leftover 88 KB.
• 426 KB: only 600 KB is large enough. Leftover 174 KB.

All four processes are placed.

Worst-fit (allocate the largest partition)

• 212 KB goes to 600 KB. Leftover 388 KB.
• 417 KB: largest is 500 KB. Leftover 83 KB.
• 112 KB: largest is 388 KB (leftover of the 600 KB). Leftover 276 KB.
• 426 KB: free blocks are 100, 83, 200, 300, 276 KB. No block fits, so 426 KB must wait.

Summary

Most efficient: best-fit is the most efficient here, because it is the only algorithm that places all four processes. First-fit and worst-fit leave the 426 KB process waiting, since they break the large partitions into pieces that are too small.

Virtual memory management

Virtual memory is a technique that allows a process to execute even when only a part of it is in main memory. The logical (virtual) address space of a process can be much larger than the physical memory. The rest of the process is kept on disk (swap area) and brought in when needed. The programmer is freed from the memory-size limit, and more processes can be kept in memory at the same time, which improves CPU utilisation.

It is usually implemented by demand paging: a page is loaded only when it is referenced. The page table has a valid/invalid bit for each page. If a reference is made to a page not in memory, a page fault occurs; the OS loads the page from disk into a free frame (using a replacement algorithm like FIFO, LRU or optimal if no frame is free), updates the page table and restarts the instruction. It works because of locality of reference. Virtual memory can also be implemented by demand segmentation.

Management issues include the fetch policy (demand or prepaging), the placement policy, the replacement policy, the frame allocation policy, and thrashing control (excessive paging activity, handled by the working set model or page-fault frequency control).

Advantages: large programs can run, more multiprogramming, and less I/O for loading. Disadvantages: more complex hardware and software, page fault overhead and possible thrashing.

Paging versus segmentation

Queue: 98, 183, 41, 122, 14, 124, 65, 67. Head starts at track 50 and moves upwards first; the last track is 199 (tracks 0 to 199).

a) FCFS

Path: $50\to98\to183\to41\to122\to14\to124\to65\to67$

$48+85+142+81+108+110+59+2 = 635$

Total head movement = 635 tracks.

b) SSTF

Path: $50\to41\to65\to67\to98\to122\to124\to183\to14$

$9+24+2+31+24+2+59+169 = 320$

Total head movement = 320 tracks.

c) SCAN (moving upwards first to the end of the disk, then reversing)

Path: $50\to65\to67\to98\to122\to124\to183\to199\to41\to14$

$(199-50)+(199-14) = 149+185 = 334$

Total head movement = 334 tracks.

d) LOOK (moving upwards first up to the last request only, then reversing)

Path: $50\to65\to67\to98\to122\to124\to183\to41\to14$

$(183-50)+(183-14) = 133+169 = 302$

Total head movement = 302 tracks.

LOOK gives the smallest movement for this queue, since it does not travel to the end of the disk unnecessarily.

File

A file is a named collection of related information stored on secondary storage. It is the logical unit of storage for the user, an abstraction of the physical device. A file has attributes (name, type, size, location, protection, time and date), and the OS provides operations on it (create, open, read, write, seek, delete, truncate). File types include text, source, executable and binary files. The file system must decide how to allocate disk blocks to files, so that disk space is used effectively and files can be accessed quickly.

Contiguous allocation

Each file occupies a set of consecutive blocks on the disk. The directory entry stores the starting block and the length (number of blocks). If a file starts at block $b$ and has $n$ blocks, it occupies $b, b+1, \dots, b+n-1$.

 Directory:  file A: start 2, length 3     file B: start 9, length 4

 Block:  0  1 [2  3  4] 5  6  7  8 [9 10 11 12] 13 ...
               A  A  A              B  B  B  B

Advantages:

• Simple to implement; only start and length are needed.
• Excellent performance: very little head movement, and fast sequential access.
• Supports direct (random) access: block $i$ of the file is at $b+i$.

Disadvantages:

• External fragmentation: free space is broken into small holes. Compaction is expensive.
• The file size must be known when it is created, and a file cannot easily grow; it may have to be moved to a larger hole.
• Finding a hole for a new file requires first-fit or best-fit searching.

Linked list allocation

Each file is a linked list of disk blocks that may be scattered anywhere on the disk. The directory contains the pointers to the first (and last) block, and each block contains a pointer to the next block (the last one has a null pointer).

 Directory: file A: start = 4

  [4 | ->9]  -->  [9 | ->1]  -->  [1 | ->14]  -->  [14 | nil]

Advantages:

• No external fragmentation; any free block can be used.
• Files can grow dynamically, and the size need not be known in advance.
• No compaction is required.

Disadvantages:

• Only efficient for sequential access. Direct access to block $i$ requires following $i$ pointers, each needing a disk read.
• Space is wasted for the pointers in every block (for example 4 bytes of 512), and the usable data size per block is no longer a power of 2.
• Poor reliability: a lost or damaged pointer breaks the chain.
• A variation, the File Allocation Table (FAT), keeps all pointers in a table in memory to improve random access.

Advantages of a distributed system over a centralized system

1. Resource sharing: users can access files, printers and processors located at other sites.
2. Speedup: a computation can be divided into parts and run in parallel on several machines (load balancing).
3. Reliability: failure of one node does not stop the whole system, so the system is fault tolerant and highly available.
4. Scalability: capacity can be increased by adding nodes.
5. Economy: many low-cost microcomputers give a better price/performance ratio than a mainframe.
6. Communication between users at distant locations (e-mail, file transfer), and data are available near the users.

Disadvantages

1. Complex software that is hard to design, test and debug.
2. Security problems, since data move over the network and are easier to intercept.
3. The system depends on the network, and network failure or congestion degrades it.
4. No shared memory or global clock, so synchronization, consistency and deadlock handling are difficult.
5. Higher administration and maintenance costs, and little ready-made software.

Remote Procedure Call (RPC)

RPC is a communication mechanism that allows a program on one machine (client) to call a procedure that executes on another machine (server) as if it were a local procedure call. The programmer does not have to deal with the sockets and message passing; the details are hidden by stubs.

 Client process                                   Server process
 +-------------+                                  +-------------+
 | call proc() |                                  | procedure   |
 +------+------+                                  +------^------+
        v                                                |
 +-------------+   request message (network)     +-------+------+
 | client stub |-------------------------------->| server stub  |
 | (marshal)   |<--------------------------------| (unmarshal)  |
 +-------------+   reply message                 +--------------+

Steps:

1. The client calls the local procedure, i.e. the client stub, passing the parameters.
2. The client stub marshals (packs) the parameters into a message, and the OS sends it to the server.
3. The server OS passes the message to the server stub, which unmarshals the parameters.
4. The server stub calls the actual procedure on the server, which executes.
5. The result is marshalled and sent back to the client stub, which returns it to the caller.

Issues: parameter passing (pointers cannot be passed directly, and data representation may differ between machines), binding the client to the server (using a name or directory service), and failures (lost request or reply, server crash), handled by timeouts and semantics such as at-least-once or at-most-once. RPC is the basis for systems like NFS and Java RMI.

Coalescing and compaction

Both are techniques used with variable (dynamic) partitioning to deal with fragmentation, the splitting of free memory into pieces that are too small to use.

Coalescing

When a process terminates and releases its memory, the new free hole may be next to another free hole. Coalescing merges such adjacent free holes into one single larger hole. For example, if holes of 40 KB and 60 KB are adjacent, they are combined into a 100 KB hole. Without coalescing, memory would end up with many small holes even though a large contiguous block is actually free. It is done by the memory manager when a block is freed, by checking the neighbours in the free list, and it is cheap (no data movement).

Compaction

Even after coalescing, free holes may be scattered between allocated areas, so a request can fail although the total free memory is enough (external fragmentation). Compaction shifts all allocated processes towards one end of memory so that all the free holes join into one large block at the other end.

 Before:  | OS | P1 | free 50 | P2 | free 30 | P3 | free 20 |
 After :  | OS | P1 | P2 | P3 | free 100 |

Requirements and costs: relocation must be dynamic (execution-time address binding using a relocation register), because the processes are moved. It takes considerable CPU time, because of copying memory contents, and the system may have to stop other work meanwhile. The cost can be reduced by moving the minimum number of processes, or by combining it with swapping. Compaction is not needed in paging, because non-contiguous allocation avoids external fragmentation.

Multiprogramming versus multiprocessing

Different structuring of operating systems

1. Monolithic structure

The whole OS is one large program in which every procedure can call any other. Advantages: simple design and fast, because there is little overhead in calls between components. Disadvantages: hard to understand, debug and modify; a bug in any part can crash the whole system; poor security.

2. Layered structure

The OS is built as a hierarchy of layers, where layer $n$ uses only the services of layers below it. Advantages: modular, easy to design, debug and verify layer by layer. Disadvantages: careful planning is needed to decide the order of layers; each request passes through many layers, so it is slower.

3. Microkernel structure

Only the minimum functions (IPC, basic scheduling and memory management) run in the kernel. Services such as file system and device drivers run as user processes. Advantages: easy to extend and port, more reliable and secure because a failing service does not crash the kernel. Disadvantages: communication overhead from message passing reduces performance.

4. Modular structure

The kernel has core components and loadable modules that are linked at boot or run time. Advantages: flexible, extensible, efficient since modules call each other directly. Disadvantages: less strict separation than a microkernel, so a faulty module can still harm the kernel.

5. Virtual machine structure

A hypervisor creates multiple virtual machines on a single physical machine, and each virtual machine runs its own OS. Advantages: complete isolation and protection, and it can run different operating systems at once and is useful for testing. Disadvantages: hard to implement exactly, and performance overhead because of virtualisation.

6. Client-server model

Processes are split into servers that offer services and clients that request them by passing messages. Advantages: suits distributed systems and is simple; disadvantages: message overhead and server dependence.

Mutual exclusion

Mutual exclusion is the property that when one process is executing in its critical section (the part of the code that accesses shared data or resources), no other process is allowed to execute in its own critical section for the same resource. It prevents race conditions, where the result of a computation depends on the order in which processes access shared data. For example, if two processes increment a shared counter at the same time, one update can be lost.

A good solution must satisfy mutual exclusion, progress (a process outside its critical section cannot stop others from entering) and bounded waiting (no process waits indefinitely), without any assumption about speed or the number of CPUs.

Peterson's solution

Peterson's algorithm is a software solution to the mutual exclusion problem for two processes $P_0$ and $P_1$. They share two variables:

• int turn; whose turn it is to enter the critical section.
• boolean flag[2]; flag[i] = true means process $i$ is ready to enter. Both are initially false.

#define N 2
int turn;
int flag[N];

void enter_region(int i)           /* i = 0 or 1 */
{
    int j = 1 - i;                 /* the other process */
    flag[i] = 1;                   /* I want to enter */
    turn = j;                      /* but let the other go first */
    while (flag[j] == 1 && turn == j)
        ;                          /* wait */
}

void leave_region(int i)
{
    flag[i] = 0;                   /* I have left */
}

Each process executes:

do {
    enter_region(i);
    /* critical section */
    leave_region(i);
    /* remainder section */
} while (1);

Explanation:

• If only $P_i$ wants to enter, flag[j] is false, so the loop ends at once and it enters.
• If both want to enter at the same time, both set their flags, and both set turn (each to the other's number). Only the value written last survives. If turn finally equals $j$, then $P_i$ waits and $P_j$ enters; otherwise the opposite. So only one gets in.
• When the process in the critical section leaves, it resets its flag, and the waiting process then proceeds.

Proof: mutual exclusion holds, because if both were in the critical section then flag[0] = flag[1] = true, and turn would have to be 1 for $P_0$ to pass and 0 for $P_1$ to pass, which is impossible for a single variable. Progress and bounded waiting hold because a process that wants to enter waits for at most one entry of the other process.

Limitations: it works for only two processes, uses busy waiting (wastes CPU time), and on modern processors with out-of-order execution it needs memory barriers.

Preemptive versus non-preemptive scheduling

Formulae: TAT = CT - AT, WT = TAT - BT.

1. Preemptive SJF (shortest remaining time first)

P0 runs from 0 and finishes at 3 (P1 with 6 has arrived but is longer). P1 runs 3-4; at 4, P2 (4) is shorter than P1's remaining 5, so P2 preempts. P2 runs to 8 (P3 with 5 does not preempt, since P2 has only 2 left). At 8, P4 (2) is the shortest. Then P1 (5 left) and P3 (5) tie, and P1 arrived earlier, so P1 runs, followed by P3.

| P0 | P1 | P2 | P4 | P1 | P3 |
0    3    4    8    10   15   20

$\text{Avg WT}=\frac{0+7+0+9+0}{5}=\frac{16}{5}=3.2 \text{ ms},\qquad \text{Avg TAT}=\frac{3+13+4+14+2}{5}=\frac{36}{5}=7.2 \text{ ms}$

2. Round Robin (quantum = 2)

|P0|P1|P0|P2|P1|P3|P2|P4|P1|P3|P3|
0  2  4  5  7  9  11 13 15 17 19 20

Ready queue at each step (new arrivals are queued before the preempted process): after 2: P1, P0; after 4: P0, P2, P1; after 5: P2... and so on, giving the order above.

$\text{Avg WT}=\frac{2+9+5+9+5}{5}=\frac{30}{5}=6 \text{ ms},\qquad \text{Avg TAT}=\frac{5+15+9+14+7}{5}=\frac{50}{5}=10 \text{ ms}$

3. Highest Response Ratio Next (HRN, non-preemptive)

$\text{Response ratio}=\frac{\text{waiting time}+\text{burst time}}{\text{burst time}}$

• t = 0: only P0 is present, so it runs 0-3.
• t = 3: only P1 has arrived, so it runs 3-9.
• t = 9: P2 ratio $=(5+4)/4=2.25$; P3 ratio $=(3+5)/5=1.6$; P4 ratio $=(1+2)/2=1.5$. P2 is chosen, running 9-13.
• t = 13: P3 ratio $=(7+5)/5=2.4$; P4 ratio $=(5+2)/2=3.5$. P4 is chosen, running 13-15.
• t = 15: P3 runs 15-20.

| P0 | P1 | P2 | P4 | P3 |
0    3    9    13   15   20

$\text{Avg WT}=\frac{0+1+5+9+5}{5}=\frac{20}{5}=4 \text{ ms},\qquad \text{Avg TAT}=\frac{3+7+9+14+7}{5}=\frac{40}{5}=8 \text{ ms}$

Summary