Linux Case Study: Architecture, File System, IPC, Disk I/O & Resource Allocation

1. Linux Kernel Architecture

1.1 Definition

The Linux kernel is the core component of the operating system that manages hardware resources, provides system services, and enforces security. It follows a monolithic design, meaning most services (memory management, scheduler, file system, network stack) run in kernel space, but it supports loadable kernel modules (LKMs) that can be inserted or removed at runtime.

1.2 Main Sub‑systems

1.3 How It Works – A Simple Boot Trace

1. BIOS/UEFI loads the bootloader (GRUB).
2. GRUB loads the Linux kernel image (vmlinuz) into memory and passes the initramfs.
3. Kernel entry point (start_kernel) initializes:
   • Interrupt descriptor table (IDT)
   • Memory management (paging structures)
   • Scheduler (runqueue)
   • VFS (mount root file system)
4. The first user‑space process, PID 1 (init/systemd), is created via kernel_thread.
5. init starts system services, loads required LKMs, and eventually launches the login manager.

This trace shows the tight coupling of hardware initialization and software services that characterises a monolithic kernel.

---

2. Linux File System

2.1 Definition

A Linux file system is a method for storing and retrieving files on block devices. The most common is ext4 (fourth extended file system), which extends ext3 with larger volumes, extents, and delayed allocation.

2.2 Key Concepts

• Inode – metadata structure (owner, permissions, timestamps, block pointers).
• Directory entry – maps a filename to an inode number.
• Extent – a contiguous range of blocks, reducing fragmentation.
• Journaling – logs metadata changes before committing them to the main file system, enabling fast recovery after crashes.

2.3 How ext4 Works – Example of File Creation

Assume a 1 GB ext4 partition with block size 4 KB.

1. touch hello.txt triggers sys_open with O_CREAT.
2. Kernel allocates a new inode (e.g., inode 12345) and reserves an extent for the file data (initially 0 blocks).
3. The directory entry for the current directory (.) is updated to include hello.txt → 12345.
4. The journal records the inode allocation and directory update.
5. When the file is written (echo "Hi" > hello.txt), the kernel allocates a data block, updates the inode’s extent list, writes the data, and logs the changes in the journal.

If a power failure occurs after step 4 but before step 5, the journal replay on reboot restores the directory entry without a dangling inode, preserving file‑system consistency.

2.4 Comparison with Other Linux File Systems

Advantages of ext4: mature, stable, low overhead, good for general‑purpose desktops and servers.
Disadvantages: lacks native snapshots and advanced data integrity features found in Btrfs.

---

3. Process Management in Linux

3.1 Process Creation – Fork‑Exec Model

1. fork() – creates a child process that is an exact copy of the parent’s address space (implemented using copy‑on‑write).
2. execve() – replaces the child’s memory image with a new program binary.

Worked Example: Running ls -l

pid_t pid = fork();
if (pid == 0) {               // Child
    char *argv[] = {"ls", "-l", NULL};
    execve("/bin/ls", argv, environ);
    _exit(1);                 // execve failed
} else if (pid > 0) {         // Parent
    waitpid(pid, &status, 0); // Wait for child to finish
}

• After fork(), both processes share the same code, but page tables are marked COW.
• execve() loads /bin/ls into the child, discarding the previous image.
• The parent blocks on waitpid() until the child exits, retrieving its exit status.

3.2 Scheduling

Linux uses the Completely Fair Scheduler (CFS). Each runnable task gets a virtual runtime; the scheduler picks the task with the smallest virtual runtime, ensuring proportional CPU share.

3.3 Signals

Signals are asynchronous notifications (e.g., SIGINT, SIGKILL). A process can set a handler with sigaction() or ignore a signal.

3.4 Process States

---

4. Inter‑Process Communication (IPC) in Linux

4.1 Overview

Linux provides several IPC mechanisms, each with distinct semantics and performance characteristics.

4.2 Worked Example: Producer‑Consumer with Shared Memory & Semaphore

/* Producer (creates shared memory and writes numbers 1..5) */
int shm_id = shmget(IPC_PRIVATE, sizeof(int), IPC_CREAT | 0666);
int *buf = (int *)shmat(shm_id, NULL, 0);
int sem_id = semget(IPC_PRIVATE, 1, IPC_CREAT | 0666);
semctl(sem_id, 0, SETVAL, 1);   // binary semaphore = 1

for (int i = 1; i <= 5; ++i) {
    struct sembuf p = {0, -1, 0};   // wait
    semop(sem_id, &p, 1);
    *buf = i;                       // critical section
    struct sembuf v = {0, 1, 0};    // signal
    semop(sem_id, &v, 1);
}
shmdt(buf);

/* Consumer (reads numbers) */
int shm_id = /* obtain same key */;
int *buf = (int *)shmat(shm_id, NULL, 0);
int sem_id = /* obtain same semaphore id */;

for (int i = 0; i < 5; ++i) {
    struct sembuf p = {0, -1, 0};
    semop(sem_id, &p, 1);
    printf("Read %d\n", *buf);
    struct sembuf v = {0, 1, 0};
    semop(sem_id, &v, 1);
}
shmdt(buf);

The semaphore guarantees exclusive access to the shared integer, preventing race conditions.

4.3 Advantages / Disadvantages

• Pipes/FIFOs: Easy to use, but limited to byte streams and unidirectional.
• Message Queues: Provide message boundaries and priorities, but have size limits.
• Shared Memory: Highest throughput, but requires explicit synchronization, increasing complexity.
• Sockets: Flexible (local or network), but incur protocol overhead.

---

5. Disk Access in Linux

5.1 Block Devices and I/O Path

1. User request (read(), write()) → system call.
2. VFS translates pathname to inode, obtains the block device (/dev/sda).
3. Block layer creates a bio (block I/O) structure.
4. I/O scheduler orders bios according to policy.
5. Device driver sends commands to the hardware (via SATA, NVMe, etc.).
6. Interrupt signals completion, kernel copies data to/from user buffer.

5.2 I/O Scheduling Policies

5.3 Worked Trace: Write Request under Deadline Scheduler

Assume three pending requests:

• R1: Read block 100 (deadline 5 ms)
• W1: Write block 200 (deadline 20 ms)
• R2: Read block 150 (deadline 8 ms)

Step 1 – Scheduler sorts reads by deadline: R1 (5 ms), R2 (8 ms).
Step 2 – Serves R1, then R2.
Step 3 – After reads, serves writes in FIFO order, so W1 is dispatched.

Result: All reads meet their deadlines; write is delayed but still within its larger deadline.

5.4 Disk Access Optimisations

• Write‑back cache – buffers writes in RAM, flushes later to improve throughput.
• Read‑ahead (readahead) – pre‑fetches sequential blocks.
• Trim (for SSDs) – informs the device about freed blocks, maintaining performance.

---

6. Resource Allocation Graph (RAG) in Linux

6.1 Definition

A Resource Allocation Graph is a directed bipartite graph used to model the allocation of resources to processes and the requests they make. Vertices are processes (P) and resources (R); edges represent allocation (R → P) or request (P → R).

6.2 Detecting Deadlock

• Cycle detection: If the graph contains a cycle, a deadlock may exist.
• Single‑instance resources: A cycle is a sufficient condition for deadlock.
• Multiple‑instance resources: A cycle is necessary but not sufficient; need to apply the Banker’s algorithm or resource‑count analysis.

6.3 Example

Consider two processes P1, P2 and two resources R1, R2 (each single instance).

1. P1 holds R1 → edge R1 → P1.
2. P1 requests R2 → edge P1 → R2.
3. P2 holds R2 → edge R2 → P2.
4. P2 requests R1 → edge P2 → R1.

The graph forms a cycle: P1 → R2 → P2 → R1 → P1, indicating a deadlock.

6.4 Using RAG in Linux

Linux’s /proc/locks file lists current lock holders (e.g., file locks, POSIX semaphores). Administrators can map these to a RAG to visualise potential deadlocks, especially in multi‑threaded server applications.

Advantages: Provides a clear visual model, useful for debugging complex lock interactions.
Disadvantages: Manual construction is tedious; not scalable for large systems without automated tools.

---

7. Summary of Linux Case Study Topics

---

Exam tip

• Short‑note questions (e.g., “IPC in Linux”) expect concise definitions, a list of mechanisms, and one practical example; keep the example to ≤ 2 lines of code.
• For disk‑access or file‑system notes, mention the journal’s role and give a brief creation trace; the examiner often looks for the sequence syscall → VFS → block layer → driver.
• When asked about Resource Allocation Graph, draw a minimal graph (3‑4 nodes) and explicitly state the deadlock condition (cycle).
• Memorise the comparison table of I/O schedulers and file‑system features; a one‑sentence advantage/disadvantage per entry scores high.
• Practice fork‑exec traces; the exam frequently asks to identify parent/child PIDs and the purpose of waitpid().

Focus on clear, bullet‑pointed explanations and include at least one short code snippet per major subtopic to demonstrate practical understanding.