Operating Systems Important Questions (with Answers)

A process is a program in execution with its own address space (code, data, heap, stack) and resources such as open files, described by its process control block. A thread runs inside a process with its own program counter, registers and stack, but shares the code, data, heap and open files with the process's other threads.

Threads are cheaper to create and switch, and communicate through shared memory; processes need IPC. Processes are isolated, while a crashing thread can bring down its whole process.

New → Ready (admitted), Ready → Running (dispatched), Running → Ready (preempted, for example when the time slice ends), Running → Waiting (I/O or event wait), Waiting → Ready (I/O done or event occurred), Running → Terminated (exit).

A waiting process never goes straight to Running; it returns through Ready. Systems that swap processes out add suspended-ready and suspended-waiting states.

The process control block stores the process ID, state, program counter, registers, scheduling information, memory-management information (page table pointer), accounting data and open files.

In a context switch, the kernel saves the running process's state into its PCB and loads the next one's. It is pure overhead, and switching address spaces can also flush the TLB and leave caches cold. Switching between threads of one process avoids the address-space change.

fork();
fork();
fork();
printf("hello\n");

fork() returns the child's PID in the parent, 0 in the child, and −1 if no child was created. Each call doubles the processes running the remaining code, so n calls give 2ⁿ processes: here 8 (the original and 7 children), so hello is printed 8 times.

A zombie has exited, but its parent has not collected its exit status with wait(), so its process-table entry remains. An orphan is still running after its parent has exited; on Linux it is re-parented, usually to init or systemd (PID 1), which reaps it when it exits.

In non-preemptive scheduling a process keeps the CPU until it exits or blocks (FCFS, SJF). In preemptive scheduling the OS can take the CPU away on a timer interrupt or when a higher-priority or shorter process arrives (Round Robin, SRTF). Preemption improves response time at the cost of more context switches.

Under FCFS, short processes stuck behind one long CPU-bound process cause the convoy effect: long waits and idle I/O devices.

Moving a short job ahead of a longer one cuts the short job's wait by the long job's burst but adds only the short job's burst to the long job's wait, so the average falls. Hence SJF minimizes average waiting time for processes available together; its preemptive form, SRTF, extends this to staggered arrivals.

But the next burst length is unknown, so it is predicted: τ(n+1) = α × t(n) + (1 − α) × τ(n), where t(n) is the last actual burst and 0 ≤ α ≤ 1. SJF can also starve long processes.

Each process runs for at most one quantum q, then rejoins the back of the queue, so with n processes none waits more than (n − 1) × q for its next turn. A very large q turns Round Robin into FCFS; a very small q spends too much time on context switches. The quantum should be large compared with the switch time and, ideally, longer than most CPU bursts.

Starvation is indefinite waiting while others are always chosen first, as with low-priority processes under priority scheduling. Aging gradually raises the priority of processes that have waited long.

A multilevel feedback queue has queues of decreasing priority. New processes enter the top queue, which has a short quantum; a process that uses its whole quantum moves down to a queue with a longer one. CPU-bound processes sink while interactive ones stay high, and aging moves long-waiting processes back up.

A race condition occurs when the result depends on the timing of accesses to shared data. count++ is a load, an add and a store; if two threads interleave them, an increment is lost. A critical-section solution must provide:

1. Mutual exclusion: at most one process in the critical section.
2. Progress: if it is free, only processes wanting to enter decide who goes next, without indefinite delay.
3. Bounded waiting: a limit on how often others can enter before a waiting process does.

A mutex is a lock with an owner: only the thread that locked it may unlock it. A semaphore is an integer used only through wait(), which decrements it and blocks when no units are left, and signal(), which increments it and wakes a waiter. A counting semaphore set to N guards N identical resources. A binary semaphore has no owner, so it also works for signalling between processes.

// Process i; the other process is j = 1 - i
flag[i] = true;          // I want to enter
turn = j;                // but you go first
while (flag[j] && turn == j)
    ;                    // busy wait
/* critical section */
flag[i] = false;

If both processes want to enter, turn holds only one value, so the one that wrote it last waits: mutual exclusion. A waiting process enters as soon as the other resets its flag, giving progress and bounded waiting. Modern CPUs reorder memory operations, so real systems use atomic instructions such as compare-and-swap instead.

Use mutex = 1, empty = N (free slots) and full = 0 (filled slots).

// Producer                 // Consumer
wait(empty);                wait(full);
wait(mutex);                wait(mutex);
/* add item */              /* remove item */
signal(mutex);              signal(mutex);
signal(full);               signal(empty);

If the producer took mutex before empty while the buffer was full, it would block holding the mutex, the consumer could never free a slot, and both would deadlock.

Each of five philosophers picks up the left chopstick, then the right. If all pick up their left one at once, each waits forever for the right: circular wait. Fixes: allow at most four at the table; pick up both chopsticks only when both are free, inside a critical section; or have odd-numbered philosophers pick left first and even-numbered right first. Each prevents deadlock, but starvation needs a separate fairness guarantee.

1. Mutual exclusion: a resource can be held by only one process at a time.
2. Hold and wait: a process holds resources while waiting for more.
3. No preemption: resources are released only voluntarily.
4. Circular wait: a cycle of processes, each waiting for a resource held by the next.

All four must hold at once, so preventing any one prevents deadlock.

• Prevention makes a condition impossible, for example by requesting every resource at once (no hold and wait) or by numbering resource types and requesting them only in increasing order (no circular wait).
• Avoidance needs each process's maximum claim in advance and grants a request only if the resulting state is safe (Banker's algorithm).
• Detection and recovery allows deadlocks, finds them periodically with a wait-for graph or a detection algorithm, then aborts processes or preempts resources.

Four processes share resources A, B and C, with totals (8, 5, 5).

      Allocation   Max       Need = Max - Allocation
      A  B  C      A  B  C   A  B  C
P0    1  0  1      4  2  2   3  2  1
P1    2  1  1      3  2  2   1  1  1
P2    2  1  2      5  1  3   3  0  1
P3    1  1  0      2  2  1   1  1  1
 
Available = (8, 5, 5) - (6, 3, 4) = (2, 2, 1)

Safety. Start with Work = (2, 2, 1). P0's need (3, 2, 1) does not fit, but P1's (1, 1, 1) does, so P1 finishes and Work = (4, 3, 2). Then P2 fits: Work = (6, 4, 4). Then P3: Work = (7, 5, 4). Then P0: Work = (8, 5, 5). The state is safe, with safe sequence P1, P2, P3, P0.

Request. P0 asks for (2, 0, 0). That is within its need and within Available, so pretend to grant it: Available becomes (0, 2, 1). Every process still needs at least one A, so none can finish. The state would be unsafe, so P0 must wait.

Only if every resource type has a single instance; then a cycle is necessary and sufficient. With multiple instances, a cycle is necessary but not sufficient, because a process outside the cycle may release an instance and break it. With no cycle, there is no deadlock.

With n processes each needing at most k instances, the worst case is every process holding k − 1 and waiting for one more. One extra instance lets a process finish, so n(k − 1) + 1 instances guarantee no deadlock. For 3 processes needing up to 4 drives each: 3 × 3 + 1 = 10. With 9, each can hold 3 and wait forever.

Internal fragmentation is unused space inside an allocated block, such as the unused part of a process's last page. External fragmentation is free memory split into pieces each too small for a request, though together they would be enough; variable partitions and segmentation cause it. Compaction removes external fragmentation at a high cost, and paging avoids it entirely.

The logical address splits into page number p and offset d, and the page table maps p to frame f: physical address = f × page size + d.

With 1 KB pages and page 2 in frame 5, logical address 3000 has p = ⌊3000 / 1024⌋ = 2 and d = 3000 − 2048 = 952, so the physical address is 5 × 1024 + 952 = 6072.

With 32-bit addresses and 4 KB pages, the page number has 20 bits, so a flat page table has 2²⁰ entries, or 4 MB at 4 bytes each. Multi-level page tables avoid storing all of it.

With hit ratio h, TLB lookup time t and memory access time m: EAT = h × (t + m) + (1 − h) × (t + 2m), since a miss needs an extra access to the page table. For t = 20 ns, m = 100 ns and h = 0.8: 0.8 × 120 + 0.2 × 220 = 140 ns, against 200 ns without a TLB. Some textbooks ignore t, so state your assumption.

Reference   1  2  3  4  1  2  5  1  2  3  4  5
FIFO (3)    F  F  F  F  F  F  F  -  -  F  F  -    9 faults
LRU  (3)    F  F  F  F  F  F  F  -  -  F  F  F   10 faults
OPT  (3)    F  F  F  F  -  -  F  -  -  F  F  -    7 faults
FIFO (4)    F  F  F  F  -  -  F  F  F  F  F  F   10 faults

FIFO evicts the oldest page, LRU the least recently used, and Optimal the page used furthest in the future, which needs future knowledge and so serves as a benchmark. The last row shows Belady's anomaly: FIFO with 4 frames faults more than with 3. LRU and Optimal never show it.

Thrashing is when processes spend more time paging than executing, because the available frames are fewer than their combined working sets. CPU utilization drops, and admitting more processes makes it worse. Control it by giving each process frames for its working set and suspending processes when demand exceeds memory, or by adjusting frames to keep each process's page-fault frequency between two bounds.

• Contiguous: fast sequential and direct access, but external fragmentation and files are hard to grow.
• Linked: each block points to the next, so there is no external fragmentation, but direct access means following the chain and one bad pointer loses the rest. FAT keeps the pointers in a table.
• Indexed: an index block lists the file's blocks, giving direct access without external fragmentation at the cost of the index block. Unix inodes combine direct and indirect pointers.

An inode has 12 direct pointers plus single, double and triple indirect pointers. With 4 KB blocks and 4-byte pointers, a block holds 1024 pointers.

Maximum = (12 + 1024 + 1024² + 1024³) × 4 KB = 48 KB + 4 MB + 4 GB + 4 TB, about 4 TB. A real file system may set a lower limit through other fields.

A hard link is another directory entry for the same inode. The data is freed only when the inode's link count reaches 0, so deleting the original name does not break it; it cannot cross file systems. A symbolic link is a small file holding a path. It can cross file systems and point to directories, but dangles if the target is removed.

Cylinders 0 to 199, head at 50 moving up, queue 82, 170, 43, 140, 24, 16, 190.

FCFS  50→82→170→43→140→24→16→190   32+88+127+97+116+8+174 = 642
SSTF  50→43→24→16→82→140→170→190   7+19+8+66+58+30+20     = 208
SCAN  50→...→190→199→43→24→16      149 + 183              = 332
LOOK  50→...→190→43→24→16          140 + 174              = 314

SCAN reaches the end of the disk before reversing; LOOK reverses at the last request. For C-SCAN, textbooks differ on counting the return seek, so state your convention.