NSCT Operating Systems Revision: Concepts and Worked MCQs

Operating systems MCQs often ask you to calculate, not just recall: an average waiting time, a page-fault count, whether a state is safe. This guide revises the core topics and works through MCQ-style examples step by step, so you can check your method as well as your answer.

Operating Systems is one of the competency areas of the NSCT, which HEC runs with Virtual University of Pakistan as the testing body. The weightage published for the NSCT syllabus lists it at 5%; confirm the current figure in the official student guide on nsct.hec.gov.pk. Our NSCT syllabus page shows how every area maps to practice topics.

Processes and Threads

A process is a program in execution. The OS tracks each one in a Process Control Block (PCB) holding its ID, state, program counter, registers and scheduling and memory information.

A process moves through five states: New, Ready, Running, Waiting (Blocked) and Terminated. Running goes to Ready on preemption and to Waiting on an I/O request. When the I/O completes, a waiting process goes to Ready, never straight to Running.

A thread is a unit of execution inside a process. Threads of the same process share the code section, data section, heap and open files. Each thread has its own stack, registers and program counter.

In the many-to-one threading model, one blocking system call blocks every user thread of the process. Revise these points under Process Management.

Worked Example 1: Counting fork() Output

Question: How many times does this C program print "NSCT"?

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

• A) 3
• B) 6
• C) 7
• D) 8

Answer: D. Each fork() doubles the number of running processes. After the first call there are 2 processes, after the second 4, after the third 8. All 8 reach printf, so the line prints 8 times (2^n for n forks).

Why the others are wrong: 3 counts fork calls, not processes. 7 is the number of new child processes (2^3 − 1), a common trap. 6 has no basis.

CPU Scheduling

Scheduling criteria to remember: maximise CPU utilisation and throughput; minimise turnaround time, waiting time and response time.

• Turnaround time = completion time − arrival time
• Waiting time = turnaround time − burst time

The main algorithms:

• FCFS: non-preemptive, simple, suffers from the convoy effect when a long job arrives first.
• SJF: picks the shortest next burst. Gives the minimum average waiting time when all jobs are available at the same time. Its preemptive form is SRTF (Shortest Remaining Time First). It can starve long jobs.
• Priority: can starve low-priority processes; the fix is aging.
• Round Robin (RR): preemptive with a time quantum. A very large quantum behaves like FCFS; a very small one wastes time on context switches.

Worked Example 2: FCFS vs SJF vs Round Robin

Four processes arrive at time 0 in the order P1, P2, P3, P4. Ignore context-switch time.

FCFS runs them in arrival order.

| P1 | P2 | P3      | P4 |
0    6    9         17   19

Waiting times: P1 = 0, P2 = 6, P3 = 9, P4 = 17. Total 32, average 8.

SJF (non-preemptive) runs the shortest burst first: P4 (2), P2 (3), P1 (6), P3 (8).

| P4 | P2 | P1    | P3      |
0    2    5       11        19

Waiting times: P4 = 0, P2 = 2, P1 = 5, P3 = 11. Total 18, average 4.5.

Round Robin, quantum = 3. Trace the ready queue carefully:

• 0 to 3: P1 runs (3 left), goes to the back.
• 3 to 6: P2 runs and finishes at 6.
• 6 to 9: P3 runs (5 left).
• 9 to 11: P4 runs its 2 units and finishes at 11.
• 11 to 14: P1 runs its last 3 and finishes at 14.
• 14 to 17: P3 runs (2 left); it is the only process left.
• 17 to 19: P3 finishes at 19.

| P1 | P2 | P3 | P4 | P1 | P3 | P3 |
0    3    6    9    11   14   17   19

Completion times: P1 = 14, P2 = 6, P3 = 19, P4 = 11. Since all arrived at 0, waiting = completion − burst: P1 = 8, P2 = 3, P3 = 11, P4 = 9. Total 31, average 7.75.

Check your work: total waiting time always equals total turnaround time minus total burst time (19 here). For SJF, 37 − 19 = 18, which matches.

For "lowest average waiting time", the answer is SJF; Round Robin is the distractor, since it improves response time instead. Practise more variants in CPU Scheduling.

Process Synchronisation

A race condition happens when the result depends on the order in which concurrent processes access shared data. The code that touches shared data is the critical section. A correct solution must satisfy three requirements:

1. Mutual exclusion: only one process in the critical section at a time.
2. Progress: if no one is inside, the choice of who enters next cannot be postponed indefinitely.
3. Bounded waiting: there is a limit on how many times others can enter before a waiting process gets its turn.

A semaphore is an integer accessed only through two atomic operations: wait() (P) decrements it and signal() (V) increments it. A binary semaphore (0 or 1) works like a mutex lock. A counting semaphore controls access to a pool of identical resources.

In the bounded-buffer producer-consumer problem, the usual setup is mutex = 1, empty = N, full = 0. The producer must call wait(empty) before wait(mutex). If it swaps them and the buffer is full, it sleeps while holding the mutex, the consumer can never get in, and the system deadlocks.

Worked Example 3: Semaphore Arithmetic

Question: A counting semaphore is initialised to 7. Then 10 wait() (P) and 5 signal() (V) operations complete. What is its final value?

• A) 12
• B) 2
• C) −3
• D) 7

Answer: B. Each P subtracts 1 and each V adds 1: 7 − 10 + 5 = 2.

Why the others are wrong: 12 treats P as an increment and V as a decrement. −3 forgets the five signal operations. 7 assumes the operations cancel out. See Concurrency & Synchronization for mutex, monitor and classic-problem questions.

Deadlocks

A deadlock can occur only if all four Coffman conditions hold at the same time:

1. Mutual exclusion: at least one resource is non-shareable.
2. Hold and wait: a process holds resources while waiting for more.
3. No preemption: resources cannot be forcibly taken away.
4. Circular wait: a cycle of processes, each waiting for the next.

Handling strategies: prevention (break one condition, for example impose a global order on resource requests to stop circular wait), avoidance (Banker's algorithm), detection and recovery, or ignoring the problem (the "ostrich" approach).

In a resource-allocation graph, a cycle means deadlock if every resource has a single instance. With multiple instances, a cycle is necessary but not sufficient.

Worked Example 4: Banker's Algorithm

Two resource types, A and B. Available = (2, 1).

Safety check. Start with Work = (2, 1).

• P1 needs (1, 1) ≤ (2, 1). It finishes and releases (2, 1). Work = (4, 2).
• P3 needs (1, 1) ≤ (4, 2). Work = (5, 3).
• P0 needs (3, 2) ≤ (5, 3). Work = (6, 4).
• P2 needs (4, 2) ≤ (6, 4). Work = (9, 4).

Every process can finish, so the state is safe with the sequence P1, P3, P0, P2.

MCQ twist: P2 now requests (1, 1). Should it be granted?

The request passes the first two checks: (1, 1) ≤ Need (4, 2) and (1, 1) ≤ Available (2, 1). Pretend to grant it: Available = (1, 0), P2's Allocation = (4, 1), P2's Need = (3, 1). Now no process can proceed, because every Need has at least one unit of B and B is 0. The resulting state is unsafe, so the request is denied, even though enough resources were free at that moment.

The common wrong answer is "granted, because Available ≥ Request". That check is necessary but not sufficient. More practice: Deadlocks.

Memory Management

Contiguous allocation (first fit, best fit, worst fit) causes external fragmentation. Paging removes external fragmentation by splitting logical memory into fixed-size pages and physical memory into frames of the same size, but it still has internal fragmentation in the last page of a process. Segmentation suffers from external fragmentation.

Address Translation

With a 32-bit logical address and 4 KB (2^12 byte) pages:

• Offset = 12 bits, page number = 32 − 12 = 20 bits.
• The page table has 2^20 = 1,048,576 entries. At 4 bytes per entry, that is 4 MB per process, which is why multilevel page tables exist.

For logical address 13,000 with 4,096-byte pages: page number = 13,000 ÷ 4,096 = 3 (integer division), offset = 13,000 − 12,288 = 712.

The TLB caches recent page-table entries. With a TLB lookup of 20 ns, memory access of 100 ns and an 80% hit ratio, the effective access time is 0.8 × (20 + 100) + 0.2 × (20 + 100 + 100) = 96 + 44 = 140 ns. A miss costs an extra memory access to read the page table.

Virtual Memory and Page Replacement

With demand paging, a page is loaded only when referenced. A reference to a page not in memory causes a page fault. When a process has fewer frames than its working set, it faults constantly and CPU utilisation collapses; this is thrashing.

Worked Example 5: FIFO vs LRU Page Faults

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3 with 3 frames, all initially empty.

FIFO: 9 faults. LRU: 8 faults.

The key difference is at reference 3 (sixth position). FIFO evicts page 0 because it was loaded earliest, even though 0 was just used. LRU evicts page 1, the least recently used, so the next reference to 0 is a hit. For comparison, the Optimal algorithm (evict the page used farthest in the future) gives 6 faults on this string.

Also remember Belady's anomaly: with FIFO, adding frames can increase faults. On the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, FIFO gives 9 faults with 3 frames but 10 with 4. LRU and Optimal do not show this anomaly. More questions: Memory Management.

File Systems

FAT is a variant of linked allocation that keeps the links in a table, which speeds up random access. Unix uses inodes: each inode stores a file's metadata and block pointers (direct, single indirect, double indirect and triple indirect). The file name lives in the directory entry, not the inode.

• A hard link is another directory entry pointing to the same inode. It cannot cross file systems.
• A symbolic (soft) link is a separate file that stores a path. It can cross file systems but breaks if the target is deleted.

Worked Example 6: Links

Question: A file has two hard links, a.txt and b.txt. You delete a.txt. What happens?

• A) The data is deleted and b.txt becomes dangling
• B) The data remains accessible through b.txt
• C) b.txt becomes a symbolic link
• D) The file system reports an error

Answer: B. Both names point to the same inode. Deleting a.txt drops the link count from 2 to 1; the data is freed only when it reaches zero and no process has the file open.

Why the others are wrong: A describes a symbolic link whose target was removed. Link types never change (C), and deleting a hard link is a normal operation (D). Revise directory and allocation questions under File Systems.

Quick Revision Checklist

• Waiting time = turnaround − burst; verify totals before choosing an option.
• Threads share code, data, heap and files, but not stacks or registers.
• Deadlock needs all four Coffman conditions; Banker's algorithm is avoidance, not prevention.
• Paging removes external fragmentation, not internal fragmentation.
• FIFO can show Belady's anomaly; LRU and Optimal cannot.

For deeper explanations, the free textbook Operating Systems: Three Easy Pieces covers scheduling, concurrency and virtual memory clearly. Then test yourself in the Operating Systems practice area, part of NSCT Prep's 33,808+ free MCQs with explanations. Redo every calculation you got wrong until the method, not just the answer, is right.