Phase 7Ch 7.3 GATE pattern drill≈ 45 min
GATE Operating Systems questions come back in a small number of shapes. For each shape: the cue in the question, the fastest method, and the lesson that teaches it.
| # | Pattern (cue) | Fastest method | Lesson |
|---|---|---|---|
| 1 | "how many times is X printed / processes created" (fork) | draw the process tree; n forks in a row → 2ⁿ processes, 2ⁿ − 1 children; trace && and || short-circuits | Lesson 1.1.2 |
| 2 | average waiting / turnaround time | draw the Gantt chart; TAT = CT − AT, WT = TAT − BT | Lesson 2.1.1 |
| 3 | SRTF or pre-emptive priority | re-decide at every arrival; compare with the remaining time | Lesson 2.1.2 |
| 4 | round robin, context switches | keep the queue on paper; arrivals join before the pre-empted process | Lesson 2.2.1 |
| 5 | CPU idle with I/O bursts | only CPU bursts compete; I/O overlaps; idle at the start and end | Lesson 2.2.2 |
| 6 | "possible values of x" | load/compute/store; one-after-other values + "both read, last store wins" | Lesson 3.1.1 |
| 7 | "which requirement fails" | try both-in (ME), both-stuck (progress), one-starved (bounded waiting) | Lesson 3.1.2 |
| 8 | semaphore value / waiters | initial − waits + signals; negative = number waiting | Lesson 3.2.1 |
| 9 | semaphore code: deadlock or order | counting wait before mutex wait; opposite orders deadlock | Lesson 3.2.2 |
| 10 | banker's safe sequence / request | Need = Max − Alloc; Need ≤ Work → Work += Alloc | Lesson 4.1.2 |
| 11 | resources so deadlock is impossible | Σ(kᵢ − 1) + 1 | Lesson 4.1.3 |
| 12 | first / best / worst fit | place one request at a time, update the holes | Lesson 5.1.1 |
| 13 | page-table size, address split | offset = log₂(page); entries = 2^(page bits); × PTE size | Lesson 5.2.1 |
| 14 | TLB EAT, levels of paging | h(t + m) + (1 − h)(t + (k + 1)m); levels = ⌈page bits / log₂(page/PTE)⌉ | Lesson 5.2.2 |
| 15 | EAT with page faults | (1 − p)·ma + p·s; convert ms to ns | Lesson 5.3.1 |
| 16 | count page faults | write frames in columns; FIFO oldest, LRU least recent, OPT farthest | Lesson 5.3.2 |
| 17 | maximum file size (inode) | k = B/P; (direct + k + k² + k³) × B | Lesson 6.1.2 |
| 18 | disk access time | seek + half a rotation + transfer | Lesson 6.2.1 |
| 19 | total head movement | list requests on a number line; SCAN to the edge, LOOK to the last request | Lesson 6.2.2 |
| 20 | CPU share of I/O | events per second × cost per event | Lesson 6.2.3 |
Time budget in the exam
1-mark questions: under 90 seconds. 2-mark questions: under 3 minutes. Scheduling and page-replacement traces are the slowest: draw the table once, neatly, and answer every sub-question from it.
8 questions · 16 marks · 45 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1 · NAT · 2 mark(s) — Pattern 1
How many processes exist in total (including the original) after fork(); if (fork() == 0) fork(); printf("x");?
Numerical answer: ________
Q2 · NAT · 2 mark(s) — Pattern 2
All arrive at 0 with bursts 6, 2, 8, 3, 4 (SJF). Average waiting time?
Numerical answer: ________
Q3 · NAT · 2 mark(s) — Pattern 6
c = 10. Three threads run c = c + 2, c = c − 3 and c = c + 1 concurrently (load/compute/store). How many different final values are possible?
Numerical answer: ________
Q4 · NAT · 2 mark(s) — Pattern 11
5 processes share 11 units of one resource; each needs at most K. Largest K that guarantees no deadlock?
Numerical answer: ________
Q5 · NAT · 2 mark(s) — Pattern 13
Logical addresses 40 bits, pages 16 KB, entries 8 bytes. Page-table size in MB?
Numerical answer: ________
Q6 · NAT · 2 mark(s) — Pattern 16
Reference string 4 3 2 1 4 3 5 4 3 2 1 5, 3 empty frames, optimal replacement. Number of faults?
Numerical answer: ________
Q7 · NAT · 2 mark(s) — Pattern 18
Average seek 8 ms, 7500 rpm, 200 sectors per track. Time to read 20 consecutive sectors in ms?
Numerical answer: ________
Q8 · NAT · 2 mark(s) — Pattern 19
Head at 80; requests 45, 130, 10, 175, 90, 60, 150 (cylinders 0–199). C-LOOK moving towards higher cylinders, counting the jump. Total head movement?
Numerical answer: ________
✓Answer Vault
Try the questions first. Open when you are ready to check.
🔐 Open the Answer Vault
Q1 Answer: 6 · 2 mark(s)
2 after the first fork; each forks again, and only the children of that second fork fork once more: 2 + 2 + 2.
Re-read: Lesson 1.1.2 — Creating processes with fork(), exec() and wait(); context switches and schedulers
Q2 Answer: 6.2 · 2 mark(s)
Order 2, 3, 4, 6, 8: waits 0, 2, 5, 9, 15.
Re-read: Lesson 2.1.2 — Shortest job first and shortest remaining time first
Q3 Answer: 7 · 2 mark(s)
Every value from 7 to 13 can occur.
Re-read: Lesson 3.1.1 — Race conditions and the critical-section problem
Q4 Answer: 3 · 2 mark(s)
5(K − 1) + 1 ≤ 11.
Re-read: Lesson 4.1.3 — Detection, recovery, and the minimum-resources formula
Q5 Answer: 512 · 2 mark(s)
2²⁶ entries × 8 B.
Re-read: Lesson 5.2.1 — Paging: pages, frames, page tables and the address split
Q6 Answer: 7 · 2 mark(s)
Optimal evicts the page needed farthest ahead.
Re-read: Lesson 5.3.2 — Page replacement: FIFO, optimal and LRU; Belady's anomaly
Q7 Answer: 12.8 · 2 mark(s)
8 + 4 + (20/200) × 8.
Re-read: Lesson 6.2.1 — Disk structure and access time
Q8 Answer: 310 · 2 mark(s)
95 up to 175, 165 back to 10, 50 up to 60.
Re-read: Lesson 6.2.2 — Disk scheduling: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK