Top 25 - Part 2

1. What are Semaphores?

A semaphore is an integer variable used to control access to shared resources, protected by two atomic operations:

• wait (P / down) — if the value is 0, block; otherwise decrement and proceed.
• signal (V / up) — increment the value, waking a blocked process if any.

Two kinds:

• Binary semaphore (0 or 1) — acts like a mutex, allowing one process into a critical section.
• Counting semaphore (0, 1, 2, …) — allows up to N processes to access a resource concurrently (e.g., N database connections).

How a semaphore works:

              Semaphore
             value = 1
                 │
          ┌──────┴──────┐
          │             │
       wait(P)       signal(V)
          │             │
       value--        value++
          │             │
     ┌────┴────┐       │
     │          │       │
 value > 0    value=0   │
     │          │       │
  Proceed     Block     Wake
     │          │       │
     └──────────┴───────┘

Because wait/signal are atomic, semaphores safely coordinate concurrent access without race conditions.

---

2. What is a Mutex?

A mutex is a mutual exclusion lock: only one thread may hold it at a time. Any other thread trying to acquire it blocks until it’s released.

Mutex concept:

Thread A                         Thread B
   │                                │
   │ lock()                         │ lock()
   ▼                                ▼
┌─────────┐                    ┌─────────┐
│ MUTEX   │                    │ MUTEX   │
│ LOCKED  │◄──── owns it ─────│ BLOCKED │
└────┬────┘                    └─────────┘
     │
     ▼
┌─────────────────┐
│ Critical        │
│ Section         │
└────────┬────────┘
         │
         ▼
     unlock()
         │
         ▼
┌─────────────────┐
│ Thread B gets   │
│ the mutex       │
└─────────────────┘

The key property is ownership — the thread that locks the mutex must be the one to unlock it. This is different from a semaphore, where one thread can signal and another can wait.

mutex_lock(&m);        // only one thread gets past this
// ... critical section ...
mutex_unlock(&m);      // must be the same thread

Mutexes are the go-to tool for protecting a shared resource inside one process.

---

3. GUI vs. CLI — compare.

• GUI (Graphical User Interface) — windows, icons, menus, mouse. Visual and intuitive, great for beginners and everyday tasks.
• CLI (Command Line Interface) — text commands typed into a shell. Precise, scriptable, and efficient once you know it.

                 User
                  │
          ┌───────┴────────┐
          │                │
        GUI               CLI
          │                │
     Click / Mouse     Type Commands
          │                │
          └───────┬────────┘
                  │
                  ▼
            Operating System
                  │
                  ▼
               Hardware

	GUI	CLI
Interaction	Visual, mouse-driven	Text, keyboard
Learning curve	Gentle	Steeper
Scripting	Limited	Full automation
Use case	General users	Admins, automation

The two aren’t competitors — most systems offer both. Power users often combine them: GUI for browsing, CLI for scripting and precise control.

---

4. Program vs. Process — differentiate.

• Program — a static set of instructions stored on disk. It’s a passive file that does nothing by itself.
• Process — an active, dynamic instance of a program currently executing in memory, with its own resources and state.

Visualize it:

        PROGRAM
     (stored on disk)
            │
            │ Execute
            ▼
      ┌─────────────┐
      │   Process   │
      │  Running    │
      └─────────────┘
        │    │    │
        ▼    ▼    ▼
      CPU   RAM  Resources

Example: The chrome binary on disk is a program. Every open Chrome window/tab is a process (or several). The same program can spawn many processes.

              Chrome Program
              (one file)
                   │
        ┌──────────┼──────────┐
        ▼          ▼          ▼
    Process 1   Process 2   Process 3
      Tab A       Tab B       Tab C

	Program	Process
Nature	Passive (file)	Active (running)
Storage	Disk	Memory
Lifetime	Permanent file	From creation to termination

One program → many processes.

---

5. What are RAID Levels (0–6)?

RAID combines multiple disks for performance or redundancy (or both):

RAID 0 — Striping

Data:       A B C D E F G H

Disk 1:     A       C       E       G
Disk 2:       B       D       F       H

       → Faster parallel access
       → No redundancy
       → One disk failure = data loss

RAID 1 — Mirroring

             Data
              │
        ┌─────┴─────┐
        ▼           ▼
     Disk 1       Disk 2
    [A B C D]    [A B C D]
        │           │
        └── Mirror ─┘

       → Same data on both disks
       → One disk can fail

RAID 5 — Distributed Parity

Disk 1      Disk 2      Disk 3      Disk 4
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
│  A1  │    │  A2  │    │  A3  │    │  P1  │
├──────┤    ├──────┤    ├──────┤    ├──────┤
│  B1  │    │  B2  │    │  P2  │    │  B3  │
├──────┤    ├──────┤    ├──────┤    ├──────┤
│  C1  │    │  P3  │    │  C2  │    │  C3  │
└──────┘    └──────┘    └──────┘    └──────┘

       → Distributed parity
       → Survives 1 disk failure

RAID 6 — Dual Parity

Disk 1      Disk 2      Disk 3      Disk 4
┌──────┐    ┌──────┐    ┌──────┐    ┌──────┐
│ Data │    │ Data │    │  P   │    │  Q   │
├──────┤    ├──────┤    ├──────┤    ├──────┤
│ Data │    │  P   │    │  Q   │    │ Data │
└──────┘    └──────┘    └──────┘    └──────┘

       → Two parity blocks
       → Survives 2 disk failures

• RAID 0 (striping) — data split across disks in parallel. Fast, but no redundancy — one disk failure loses everything.
• RAID 1 (mirroring) — exact copy on two disks. Redundant, but doubles cost.
• RAID 5 (striping + distributed parity) — parity spread across all disks. Tolerates one disk failure.
• RAID 6 (dual parity) — two parity blocks. Tolerates two disk failures.

Level	Performance	Redundancy	Tolerates
0	High	None	0 failures
1	Mirror write cost	Full copy	1 failure
5	Good	Distributed parity	1 failure
6	Good	Dual parity	2 failures

---

6. What is a Bootstrap Program?

The bootstrap (or bootloader) is the code that starts the computer:

       Power ON
           │
           ▼
   ┌───────────────┐
   │ Firmware /    │
   │ UEFI / BIOS   │
   └───────┬───────┘
           │
           ▼
         POST
   Hardware Check
           │
           ▼
   Find Boot Device
           │
           ▼
       Bootloader
       (e.g. GRUB)
           │
           ▼
      OS Kernel
           │
           ▼
   Operating System

1. Initializes hardware — CPU, memory, devices.
2. Runs POST (Power-On Self-Test) — checks the hardware is working.
3. Locates the OS kernel — finds it on the boot device.
4. Loads the kernel into memory and hands over control.

Because nothing can run until the OS is loaded, the bootstrap lives in firmware (ROM), which survives power-off.

Common bootloaders: GRUB (Linux) and UEFI firmware (modern PCs). The name “bootstrap” comes from “pulling yourself up by your bootstraps.”

---

7. What is an Assembler?

An assembler translates assembly language (human-readable mnemonics like MOV, ADD) into machine code that the CPU executes.

High-Level Language
       │
       │ Compiler
       ▼
   Machine / Byte Code

Assembly Language
       │
       │ Assembler
       ▼
    Machine Code
       │
       ▼
       CPU

The key difference from a compiler:

• Compiler — high-level language (C, Java) → machine/byte code. One high-level line can become many machine instructions.
• Assembler — assembly → machine code with a 1:1 mapping. Each mnemonic corresponds to one machine instruction.

Because assembly is close to the hardware, assemblers are simple, and the output is highly predictable. They’re used when you need exact control over the CPU — device drivers, embedded systems, bootloaders.

---

8. What is Locality of Reference?

Locality is the observation that programs tend to access memory in clusters, not randomly. Two forms:

Temporal Locality

CPU accesses X
      │
      ▼
   [ X ]
      │
      │ likely accessed again soon
      ▼
   [ X ]
      │
      ▼
   [ X ]

Spatial Locality

Memory:

[A][B][C][D][E][F][G][H]
     ↑
  Access B

Likely next:
       ↑
  C or nearby data

• Temporal locality — data accessed recently is likely to be accessed again soon (e.g., a loop variable).
• Spatial locality — data near recently accessed data is likely to be accessed next (e.g., array elements in sequence).

Why it matters:

       CPU
        │
        ▼
      Cache
   ┌─────────┐
   │ Recent  │
   │ /Nearby │
   │  Data   │
   └────┬────┘
        │
        │ Cache miss
        ▼
       RAM
        │
        ▼
      Disk

Caching and virtual memory depend on it. When a page/cache line is loaded because of one access, the system bets the neighboring data will be used soon. Locality is why caches work — without it, they’d be useless.

---

9. What are Disk Scheduling Algorithms?

Disk scheduling orders the pending I/O requests to minimize seek time — the time the read/write head spends physically moving.

Example disk requests:

Disk tracks:

0    20    40    60    80    100
|-----|-----|-----|-----|-----|
              ↑
         Head at 50

Requests:
20, 40, 60, 80, 100

Different algorithms choose a different order:

FCFS:
50 → 20 → 80 → 40 → 100 → 60

SSTF:
50 → 40 → 60 → 20 → 80 → 100

SCAN:
0 ← 20 ← 40 ← 50 → 60 → 80 → 100
                         then reverse

C-SCAN:
0 ← 20 ← 40 ← 50 → 60 → 80 → 100
                         │
                         └── jump back to 0

• FCFS — serve requests in arrival order. Fair, but the head zigzags inefficiently.
• SSTF (Shortest Seek Time First) — always serve the request closest to the current head position. Efficient, but far requests can starve.
• SCAN (elevator) — the head sweeps in one direction, serving everything in its path, then reverses. Like an elevator — consistent and starvation-free.
• C-SCAN — like SCAN but only services requests in one direction, then jumps back. More uniform wait times.

The goal across all of them: arrange request order so the mechanical head moves as little as possible.

---

10. Classical Synchronization Problems — Dining Philosophers, Readers-Writers.

These are classic thought experiments that expose real concurrency problems.

Dining Philosophers

Five philosophers sit around a table, each needing two forks to eat, with five forks shared.

                    Philosopher 1
                         │
                    Fork     Fork
                  /                   \
        Philosopher 5               Philosopher 2
              │                         │
            Fork                       Fork
              \                         /
               \                       /
                Philosopher 4 ─ Fork ─ Philosopher 3

The deadlock situation can be visualized as:

P1 holds F1 → waits for F2
P2 holds F2 → waits for F3
P3 holds F3 → waits for F4
P4 holds F4 → waits for F5
P5 holds F5 → waits for F1

        ┌─────────────────────┐
        │       DEADLOCK      │
        │                     │
        │ P1 → P2 → P3 → P4  │
        │ ↑                 ↓ │
        │ └──── P5 ←────────┘ │
        └─────────────────────┘

If all grab their left fork simultaneously, everyone waits forever for the right one — a deadlock. Even without deadlock, a philosopher can starve. The solutions teach careful resource ordering and mutual exclusion.

Readers-Writers

Multiple readers can read shared data simultaneously, but only one writer at a time, and no reading while writing.

                 Shared Data
                     │
          ┌──────────┴──────────┐
          │                     │
       Readers                Writer
          │                     │
    ┌─────┼─────┐               │
    ▼     ▼     ▼               ▼
   R1    R2    R3              W1

R1 + R2 + R3
   can read together

Writer W1
   must be alone

The challenge can be visualized as:

Readers keep arriving
        │
        ▼
R1 → R2 → R3 → R4 → R5 → ...
                          │
                          ▼
                     Writer waits
                          │
                          ▼
                       STARVATION

The opposite can also happen if writers are continuously prioritized.

Readers-Writers goal:

Readers:
R1 ──┐
R2 ──┼──► Shared Data ◄── Writer
R3 ──┘

Multiple readers → allowed
Reader + writer  → NOT allowed
Multiple writers → NOT allowed

Both scenarios aren’t just puzzles — they model real multi-threaded systems where these exact problems (deadlock, starvation, race conditions) occur.