BSc CSIT (TU) Science Operating System (BSc CSIT, CSC259) Question Paper 2081 Nepal

Critical Section Problem

When multiple processes share data, each process has a segment of code called the critical section (CS) in which it accesses the shared resource. The problem is to design a protocol so that no two processes execute their critical sections at the same time.

A correct solution must satisfy three requirements:

1. Mutual Exclusion – if a process is in its CS, no other process may be in its CS.
2. Progress – if no process is in its CS, only the processes not in their remainder section participate in deciding who enters next, and the decision cannot be postponed indefinitely.
3. Bounded Waiting – there is a bound on the number of times other processes can enter their CS after a process has requested entry and before that request is granted (no starvation).

General structure of a process:

do {
    entry section
        critical section
    exit section
        remainder section
} while (true);

Peterson's Solution (two processes)

A classic software solution for two processes $P_0$ and $P_1$. It uses two shared variables:

• int turn; – whose turn it is to enter.
• boolean flag[2]; – flag[i] is true if $P_i$ wants to enter.

// Process Pi  (j = the other process)
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);   // busy wait
        /* critical section */
    flag[i] = false;
        /* remainder section */
} while (true);

Why it works: $P_i$ enters only when the other process does not want to enter (flag[j]==false) or it is $P_i$'s turn (turn==i). Since turn can hold only one value, only one process passes the while test → mutual exclusion. Progress and bounded waiting also hold because a waiting process is admitted as soon as the other leaves. (Limitation: works for only 2 processes and assumes no instruction reordering.)

Semaphores

A semaphore $S$ is an integer variable accessed only through two atomic operations:

wait(S):  while (S <= 0);   // busy-wait (or block)
          S--;
signal(S): S++;

Mutual exclusion using a binary semaphore (initialised to 1):

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

The first process to call wait(mutex) makes mutex = 0; any other process blocks until the first calls signal(mutex). To avoid busy waiting, the OS implementation blocks the process on a waiting queue and wakes it on signal. Counting semaphores (initial value = number of available resources) generalise this to control access to a pool of identical resources.

Conclusion: The critical-section problem requires mutual exclusion, progress and bounded waiting. Peterson's solution provides a correct software solution for two processes, while semaphores offer a general, hardware-supported synchronization primitive usable for any number of processes.

Paging

Paging is a non-contiguous memory-management scheme that eliminates external fragmentation by dividing both logical and physical memory into fixed-size blocks:

• Page – fixed-size block of logical (virtual) memory.
• Frame – physical-memory block of the same size as a page.

When a process is loaded, its pages are placed into any available frames; they need not be contiguous. A page table (one per process) stores the frame number that holds each page, so the logical address space appears contiguous to the program even though physical placement is scattered.

Address Translation

The CPU generates a logical address that is split into two parts:

• $p$ = page number (high-order bits) → index into the page table.
• $d$ = page offset (low-order bits) → displacement within the page.

If the page size is $2^n$, the low $n$ bits form $d$ and the remaining bits form $p$.

Translation steps:

1. Extract page number $p$ and offset $d$ from the logical address.
2. Use $p$ to index the page table → obtain the frame number $f$.
3. Form the physical address as $f \times (\text{page size}) + d$, i.e. concatenate $f$ and $d$.

Example: page size = 4 KB ($2^{12}$). Logical address $0x2A3F$ with page number indexing the table to frame 5 → physical address = $5 \times 4096 + 0x\text{A3F}$.

TLB (Translation Look-aside Buffer)

Every memory reference would need two physical accesses (one to read the page table, one for the data), doubling memory time. A TLB is a small, fast associative (content-addressable) cache that holds recently used (page → frame) mappings.

Translation with a TLB:

1. Present page number $p$ to the TLB.
2. TLB hit – frame number is returned immediately; combine with $d$ → physical address (fast).
3. TLB miss – consult the page table in memory to get the frame, then update the TLB with this entry (replacing one if full).

Effective Access Time (EAT): with hit ratio $\alpha$, TLB lookup time $t$, memory access time $m$:

A high hit ratio keeps EAT close to one memory access. The TLB therefore makes paging practical by avoiding the page-table lookup on most references.

Advantages of paging: no external fragmentation, easy allocation, supports virtual memory; disadvantage: internal fragmentation in the last page and page-table storage overhead.

Virtual Memory

Virtual memory is a memory-management technique that allows the execution of processes that may not be completely in main memory. It separates logical memory (as seen by the program) from physical memory, so programs larger than physical RAM can run, more processes fit in memory (higher multiprogramming), and less I/O is needed to load/swap programs.

Demand Paging

In demand paging, a page is brought into memory only when it is referenced, not in advance. Each page-table entry has a valid/invalid bit:

• valid → page is in memory.
• invalid → page is on disk (or illegal).

When the CPU accesses an invalid page, a page fault trap occurs. The OS then: (1) checks the reference is legal, (2) finds a free frame (or selects a victim to replace), (3) reads the page from disk into the frame, (4) updates the page table to valid, and (5) restarts the faulting instruction. Bringing pages only on demand is called lazy swapping and reduces I/O and memory use.

Page Replacement Algorithms

Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames.

FIFO (First-In First-Out)

Replaces the oldest loaded page.

FIFO page faults = 9. Simple, but suffers Belady's anomaly (more frames can give more faults).

Optimal (OPT / MIN)

Replaces the page that will not be used for the longest time in the future.

Processing the same string yields page faults at: 7, 0, 1, 2, 3, 4, then 2 and 0 cause faults later → Optimal page faults = 7. It gives the lowest possible fault count but is unimplementable (needs future knowledge); used as a benchmark.

LRU (Least Recently Used)

Replaces the page that has not been used for the longest time in the past (approximates Optimal using recent history).

For this string, LRU page faults = 9 (some textbook orderings give 10–12 depending on tie handling); it is better than FIFO on most workloads, avoids Belady's anomaly, but needs hardware support (counters or a stack).

Comparison

Conclusion: Optimal gives the fewest faults but is theoretical; LRU is a good, practical approximation; FIFO is simplest but can perform worst and suffers Belady's anomaly.

Producer–Consumer (Bounded-Buffer) Problem

The producer–consumer problem is a classic synchronization problem involving two cooperating processes that share a bounded buffer of fixed size $n$:

• The producer creates data items and places them into the buffer.
• The consumer removes (consumes) items from the buffer.

The challenge:

• The producer must not add an item when the buffer is full.
• The consumer must not remove an item when the buffer is empty.
• Both access the shared buffer (and count), so updates must be mutually exclusive to avoid a race condition.

Semaphore solution uses three semaphores:

• mutex = 1 – mutual exclusion for buffer access.
• empty = n – number of empty slots.
• full = 0 – number of filled slots.

// Producer                      // Consumer
wait(empty);                     wait(full);
wait(mutex);                     wait(mutex);
  add item to buffer;              remove item from buffer;
signal(mutex);                   signal(mutex);
signal(full);                    signal(empty);

This guarantees the producer blocks when the buffer is full, the consumer blocks when it is empty, and only one process touches the buffer at a time.

Dining Philosophers Problem

Five philosophers sit around a circular table. Each alternates between thinking and eating. There are five chopsticks, one between each pair of philosophers. To eat, a philosopher needs both the left and right chopsticks; when finished, they put both down and resume thinking.

It is a classic synchronization problem that illustrates the difficulty of allocating several shared resources among many processes without deadlock or starvation.

Naive semaphore solution – one semaphore per chopstick (chopstick[5], each = 1):

do {
    wait(chopstick[i]);            // pick left
    wait(chopstick[(i+1)%5]);      // pick right
        /* eat */
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5]);
        /* think */
} while (true);

Problem: if all five philosophers pick up their left chopstick simultaneously, each waits forever for the right one → deadlock (circular wait), and a philosopher may also starve.

Remedies:

1. Allow at most four philosophers at the table at once.
2. A philosopher picks up chopsticks only if both are available (do it in a critical section).
3. Asymmetric rule – odd-numbered philosophers pick left then right, even-numbered pick right then left (breaks the circular wait).

These ensure mutual exclusion on chopsticks while avoiding deadlock and starvation.

Thrashing

Thrashing is a condition in which a process (or the system) spends more time paging (servicing page faults) than executing useful work. It happens when a process does not have enough frames to hold its working set, so almost every memory reference causes a page fault; pages are continuously swapped in and out.

Cause: As the OS raises the degree of multiprogramming, the frames per process drop. Page-fault rate rises, CPU utilisation falls, and the scheduler (seeing idle CPU) admits more processes — making it worse. Beyond a point, CPU utilisation collapses sharply.

Prevention / Control

1. Working-Set Model – track each process's working set (set of pages referenced in a window $\Delta$). Allocate enough frames to hold it; suspend/swap out a process if the total demand exceeds available frames.
2. Page-Fault Frequency (PFF) – monitor each process's fault rate; if it is too high, give the process more frames; if too low, take frames away. Suspend a process if no frames are free.
3. Limit the degree of multiprogramming – reduce the number of active processes (swap some out) so each retains enough frames.
4. Use local replacement so one thrashing process cannot steal frames from others.
5. Provide more physical memory or use prepaging of the working set.

These techniques keep each process's allocated frames close to its working set, eliminating excessive paging.

Logical vs Physical Address Space

A logical (virtual) address is generated by the CPU during program execution; a physical address is the actual location in main memory (RAM) seen by the memory unit. The Memory Management Unit (MMU) translates logical addresses to physical addresses at run time (e.g., physical = logical + relocation/base register, or via a page table).

In compile-time and load-time binding the two addresses are identical; in execution-time binding they differ, and the MMU performs the translation.

Segmentation

Segmentation is a memory-management scheme that supports the user's view of memory. A program is regarded as a collection of variable-length, logical units called segments — e.g. main program, functions, stack, arrays, global variables, symbol table — rather than a single linear array of bytes.

Each logical address consists of two parts:

A segment table maps each segment to physical memory; each entry has:

• Base – starting physical address of the segment.
• Limit – length of the segment.

Address translation: for logical address $(s, d)$ —

1. If $d \ge \text{limit}[s]$ → addressing error (trap, protects against overflow).
2. Otherwise physical address = $\text{base}[s] + d$.

Two registers help: STBR (segment-table base register) and STLR (segment-table length register).

Advantages:

• Matches the programmer's logical view; eases sharing and protection (read/write/execute bits per segment).
• No internal fragmentation.

Disadvantages:

• Variable-size segments cause external fragmentation, requiring compaction.

(Combining segmentation with paging — segmented paging — overcomes external fragmentation.)

Semaphore

A semaphore is an integer synchronization variable that, apart from initialisation, is accessed only through two atomic (indivisible) operations: wait() (also called P or down) and signal() (also called V or up). It is used to enforce mutual exclusion and to coordinate the ordering of cooperating processes.

wait(S):   while (S <= 0);   // wait / block
           S--;
signal(S): S++;

In practice wait blocks the calling process on a queue (instead of busy-waiting) and signal wakes one waiting process.

Binary vs Counting Semaphore

A binary semaphore is the special case of a counting semaphore restricted to the values 0 and 1.

Monitor

A monitor is a high-level synchronization construct (abstract data type) that encapsulates shared variables together with the procedures that operate on them, providing automatic mutual exclusion. It was introduced because semaphores are low-level and error-prone (a misplaced or omitted wait/signal causes deadlock or race conditions).

Key property: Only one process can be active inside the monitor at a time — the compiler/runtime guarantees mutual exclusion automatically, so the programmer need not place explicit wait/signal around the critical region.

monitor MonitorName {
    // shared variables
    condition x, y;            // condition variables

    procedure P1(...) { ... }
    procedure P2(...) { ... }

    initialization code { ... }
}

Condition variables: To allow processes to wait inside a monitor, condition variables are used with two operations:

• x.wait() – the calling process is suspended (and releases the monitor) until another process signals x.
• x.signal() – resumes exactly one process waiting on x; if none is waiting, it has no effect (unlike a semaphore's signal).

Because only one process runs in the monitor, signalling needs a discipline such as signal-and-wait or signal-and-continue to decide who proceeds.

Advantage: safer and easier to use than semaphores — mutual exclusion is enforced automatically, reducing programming errors.

Preemptive vs Non-Preemptive Scheduling

CPU scheduling decisions occur when a process (1) switches running→waiting, (2) running→ready, (3) waiting→ready, or (4) terminates. Scheduling that occurs only under (1) and (4) is non-preemptive; if it also occurs under (2) and (3) it is preemptive.

Summary: Preemptive scheduling improves responsiveness and fairness at the cost of more context switches and synchronization needs, whereas non-preemptive scheduling is simpler and has lower overhead but can make short jobs wait behind long ones (convoy effect).

RAID

RAID (Redundant Array of Independent/Inexpensive Disks) is a technology that combines multiple physical disk drives into a single logical unit to improve performance (through parallelism / data striping) and/or reliability (through redundancy — mirroring or parity). Data is distributed across the drives according to the chosen RAID level.

Two RAID Levels

RAID 0 – Striping (no redundancy)

Data is split into blocks (stripes) and written across all disks in parallel.

• Advantage: highest performance (parallel reads/writes), full capacity usable.
• Disadvantage: no redundancy — failure of any single disk loses all data. Needs at least 2 disks. Reliability is lower than a single disk.

RAID 1 – Mirroring

Every block is written identically to two (or more) disks (an exact copy/mirror).

• Advantage: high reliability — if one disk fails, its mirror still has the data; good read performance.
• Disadvantage: 50% storage overhead (usable capacity is half the raw capacity); writes go to both disks.

(Other common levels: RAID 5 – block-level striping with distributed parity; RAID 6 – double distributed parity; RAID 10 – mirrored stripes.)