Skip to content
Tutorials Center
My learning

Topics

Lesson 66 of 66 ยท Projects and Practice

Operating Systems Practice Problems with Solutions

Twelve worked operating systems exam-style problems on paging, TLB, page faults, inodes, disk access, RAID, disk scheduling, round robin, page replacement and the Banker's algorithm, checked by Python.

Operating systems exams, interviews and certification tests share a small set of problem types: a calculation about memory or disks, a scheduling table, a page-replacement trace, a deadlock check. They are not hard once you know the formula, but they are easy to get wrong through arithmetic slips. This lesson gives you twelve typical problems, the reasoning for each, and a Python program that computes the answer, so you can check your own work or modify the numbers and practice again.

How to use it: read each problem, solve it on paper, then run the solver. If your answer differs, trace which step went wrong. Change the inputs and repeat.

Part 1: memory and files

Q1. Effective access time with a TLB. A TLB lookup takes 10 ns, a memory access 100 ns, and the TLB hit ratio is 90%. With single-level paging, what is the effective memory access time (EAT)?

Reasoning: on a hit you pay the TLB plus one memory access (110 ns). On a miss you pay the TLB, the page-table access and the data access (210 ns). EAT = 0.9 x 110 + 0.1 x 210 = 120 ns. See paging and the TLB.

Q2. Page fault rate. Memory access takes 200 ns and servicing a page fault takes 8 ms. What fault rate keeps the slowdown below 10%?

Reasoning: EAT = (1 - p) x 200 + p x 8,000,000 must be at most 220. Solve for p, as in demand paging.

Q3. Page table size. A system has 32-bit virtual addresses, 4 KB pages and 4-byte page table entries. How large is a single-level page table?

Q4. Two-level paging. If the 32-bit address is split as 10 + 10 + 12 bits, how many entries does each table hold, and why is that split convenient?

Q5. Maximum file size. An inode has 10 direct pointers, one single-indirect and one double-indirect pointer. Blocks are 1 KB and pointers 4 bytes. What is the maximum file size?

Q6. Disk access time. A 7,200 RPM disk has an average seek of 8 ms and transfers 100 MB/s. What is the average time to read a random 64 KB chunk?

Q7. RAID capacity. Eight disks of 2 TB each. What is the usable capacity under RAID 0, 1, 5, 6 and 10?

Q8. Disk scheduling. Head at track 100, moving up, tracks 0-199, pending requests: 23, 89, 132, 42, 187. Find the total head movement under SSTF and under LOOK (continue up first).

Python Solver for Q1 to Q8

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notes on the answers:

  • Q2: the allowed fault rate is roughly 1 in 400,000. A page fault is so slow that memory must almost never fault.
  • Q3: a flat table for a 32-bit space needs a million entries (4 MB) for every process, which is why page tables are multilevel (Q4). With 10 + 10 + 12 bits, each table has 1,024 entries of 4 bytes, exactly one page, so tables can be paged in and out like any other data.
  • Q5: (10 + 256 + 65,536) x 1 KB = 65,802 KB, about 64.26 MB. The double-indirect block contributes almost everything.
  • Q6: seek and rotation (12.2 ms) dwarf the transfer (0.6 ms). Compare with disk structure.
  • Q7: RAID 5 loses one disk to parity, RAID 6 two, RAID 1 and 10 half.
  • Q8: SSTF takes the nearest request each time and travels 273 tracks; LOOK sweeps up to 187, then down to 23, for 251 tracks. See disk scheduling.

Part 2: scheduling, replacement and deadlock

Q9. Round robin. Processes (arrival, burst): P1 (0, 10), P2 (1, 5), P3 (2, 8). Quantum 4. A process arriving at the same time a quantum expires is queued ahead of the preempted one. Find each finish time and the average waiting time.

Q10. LRU. Reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 4 frames. How many page faults under LRU?

Q11. Banker's algorithm. Available = (3, 3, 2). Five processes with Allocation and Max matrices as in the code. Is the state safe? Give a safe sequence.

Q12. Race condition. Two threads each increment a shared counter 1,000 times without any lock. What can the final value be?

Python Solver for Q9 to Q12

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notes on the answers:

  • Q9: P2 finishes at 17, P3 at 21 and P1 at 23; the waiting times are 11, 11 and 13, average 11.67. Draw the Gantt chart yourself: P1 (0-4), P2 (4-8), P3 (8-12), P1 (12-16), P2 (16-17), P3 (17-21), P1 (21-23).
  • Q10: LRU with 4 frames gives 8 faults on this string (compare with FIFO's 10 faults, Belady's anomaly, in the page replacement lab).
  • Q11: the need matrix is Max - Allocation. The state is safe, for example with the sequence P1, P3, P4, P0, P2: each process can finish with the resources available at its turn and then release what it holds. See deadlocks.
  • Q12: the printed result of 1,000 shows the worst case of the interleaving in the demo, but in general the final value of an unprotected counter can be anything from 1,000 up to 2,000. Use a mutex or atomic operation.

Part 3: conceptual drills

Answer these in a sentence each, then compare with the text of the relevant lesson.

  1. Why does a system call switch to kernel mode, and what stops a user program from jumping to arbitrary kernel code?
  2. What is the difference between a process and a thread, and which resources do threads share?
  3. State the four necessary conditions for deadlock. Which one does ordering the resources break?
  4. Why does a larger page size reduce page-table size but increase internal fragmentation?
  5. How does a journaling file system recover after a crash?
  6. Why is SSTF unfair, and how does SCAN fix that?
  7. Why does a hash alone not protect passwords, and what do salts and slow hashes add?
  8. How does a container differ from a virtual machine, and which resources do namespaces and cgroups each control?

Strategy for exam problems

  • Write the formula first, then substitute. Most marks go to the setup.
  • Check units. Milliseconds against nanoseconds and KB against bytes cause half of all errors.
  • For scheduling tables, draw a Gantt chart, then compute turnaround = finish - arrival and waiting = turnaround - burst.
  • For page replacement, write the frame contents after every reference and count faults as you go.
  • For deadlock questions, compute Need = Max - Allocation first.
  • Sanity-check results: hit ratio between 0 and 1, EAT between the best and worst case, RAID capacity less than raw capacity.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With a TLB lookup of 20 ns, memory access of 100 ns and a hit ratio of 80%, what is the effective access time for single-level paging?

    Hit 0.8 x (20 + 100) = 96. Miss 0.2 x (20 + 100 + 100) = 44. Total 140 ns.
  2. 2. A 32-bit system uses 8 KB pages and 4-byte entries. How large is a single-level page table?

    There are 2^32 / 2^13 = 2^19 pages. At 4 bytes each the table is 2^21 bytes = 2 MB.
  3. 3. 6 disks of 1 TB in RAID 5. What is the usable capacity?

    RAID 5 spends one disk's worth of space on parity, so usable capacity is (6 - 1) x 1 TB.
  4. 4. In the Banker's algorithm, how do you compute the Need matrix?

    Need is what each process may still request: its declared maximum minus what it already holds.

Summary

  • Most OS numerical problems reduce to a formula: effective access time, page-table size, inode reach, disk access time, RAID capacity, head movement.
  • Scheduling and replacement problems are solved by tracing: draw a Gantt chart or the frame contents step by step.
  • The Banker's algorithm computes Need = Max - Allocation and searches for a sequence in which every process can finish.
  • Let code check your arithmetic, then change the numbers and try again.

That completes the Operating Systems track. Return to the track overview to revisit any chapter.