Comprehensive Exercises
These ten exercises are deliberately cross-chapter: each one asks you to combine two modules, which is how operating system questions usually arrive. Work them after the five chapters, and use the reference answers to check not only whether your result is right but also whether your reasoning is the one an examiner expects.
Problem: A system uses round-robin scheduling with a time slice of 10 ms. Four processes P1, P2, P3 and P4 all arrive at time 0, with burst times of 20 ms, 15 ms, 30 ms and 10 ms respectively. Find the turnaround time of each process and the average turnaround time.
Approach
Draw the timeline first: the time slice advances in 10 ms steps, and each slot records which process runs and how much of its burst is left. The moment a process finishes is the moment its turnaround time is fixed, so collect the four completion times and average them.
Steps
Scheduling sequence (time slice = 10 ms):
- 0–10 ms: P1 (10 ms left)
- 10–20 ms: P2 (5 ms left)
- 20–30 ms: P3 (20 ms left)
- 30–40 ms: P4 (finishes, turnaround time = 40 ms)
- 40–50 ms: P1 (finishes, turnaround time = 50 ms)
- 50–55 ms: P2 (finishes, turnaround time = 55 ms)
- 55–65 ms: P3 (10 ms left)
- 65–75 ms: P3 (finishes, turnaround time = 75 ms)
Turnaround times:
- P1: 50 ms
- P2: 55 ms
- P3: 75 ms
- P4: 40 ms
Average turnaround time = (50 + 55 + 75 + 40) / 4 = 220 / 4 = 55 ms.
Answer
P1 = 50 ms, P2 = 55 ms, P3 = 75 ms, P4 = 40 ms, and the average turnaround time is 55 ms.
Problem: There are 5 processes P0–P4 and 3 resource types A(10), B(5), C(7). The resource allocation at time T0 is:
| Process | Max(A,B,C) | Allocation(A,B,C) |
|---|---|---|
| P0 | (7,5,3) | (0,1,0) |
| P1 | (3,2,2) | (2,0,0) |
| P2 | (9,0,2) | (3,0,2) |
| P3 | (2,2,2) | (2,1,1) |
| P4 | (4,3,3) | (0,0,2) |
- Find the Need matrix and the Available vector at time T0.
- Is the system in a safe state at T0? If so, give a safe sequence.
Approach
The Need matrix is Max minus Allocation, and Available is what the system has left over. Then repeatedly look for a process whose Need is no larger than Available; if running it and releasing its allocation still leaves enough for the next process, you have a safe sequence. If you can walk the whole set, the state is safe.
Steps
(1) Need = Max − Allocation:
- P0: (7,5,3) − (0,1,0) = (7,4,3)
- P1: (3,2,2) − (2,0,0) = (1,2,2)
- P2: (9,0,2) − (3,0,2) = (6,0,0)
- P3: (2,2,2) − (2,1,1) = (0,1,1)
- P4: (4,3,3) − (0,0,2) = (4,3,1)
Available = total resources − total allocated
Total allocated = (0+2+3+2+0, 1+0+0+1+0, 0+0+2+1+2) = (7,2,5)
Available = (10,5,7) − (7,2,5) = (3,3,2)
(2) Safety check:
- Available = (3,3,2)
- P1 Need = (1,2,2) ≤ (3,3,2), run P1, then Available = (3,3,2) + (2,0,0) = (5,3,2)
- P3 Need = (0,1,1) ≤ (5,3,2), run P3, then Available = (5,3,2) + (2,1,1) = (7,4,3)
- P0 Need = (7,4,3) ≤ (7,4,3), run P0, then Available = (7,4,3) + (0,1,0) = (7,5,3)
- P2 Need = (6,0,0) ≤ (7,5,3), run P2, then Available = (7,5,3) + (3,0,2) = (10,5,5)
- P4 Need = (4,3,1) ≤ (10,5,5), run P4
Safe sequence: P1 → P3 → P0 → P2 → P4.
Answer
(1) The Need matrix is as listed above and Available = (3,3,2). (2) The system is in a safe state, with the safe sequence P1 → P3 → P0 → P2 → P4.
Problem: Use semaphores to solve the producer-consumer problem. The buffer holds n items; producers place items into the buffer and consumers take items out. Write the pseudocode for mutual exclusion and synchronisation.
Approach
Three semaphores, each with one job: mutex guards mutual access to the buffer, empty counts the free slots, and full counts the filled slots. The producer advances as P(empty) → P(mutex) → put → V(mutex) → V(full), and the consumer mirrors it. Every P must be matched by exactly one V.
Steps
Declare the semaphores:
- mutex = 1 (mutual exclusion on the buffer)
- empty = n (number of empty buffer slots)
- full = 0 (number of filled buffer slots)
Producer process:
while (true) {
produce_item();
P(empty); // wait for an empty slot
P(mutex); // enter the critical section
put_item_into_buffer();
V(mutex); // leave the critical section
V(full); // one more filled slot
}Consumer process:
while (true) {
P(full); // wait for a filled slot
P(mutex); // enter the critical section
take_item_out_of_buffer();
V(mutex); // leave the critical section
V(empty); // one more empty slot
consume_item();
}Note that the order of the P operations matters: P(empty) or P(full) must come before P(mutex), otherwise the two processes can deadlock. The order of the V operations does not matter.
Answer
The pseudocode above, using the three semaphores mutex, empty and full.
Problem: A system uses paging with a page size of 4 KB, a 32-bit logical address space, and a 24-bit physical address space. The page table is partly given below:
| Page number | Frame number |
|---|---|
| 0 | 5 |
| 1 | 9 |
| 2 | 14 |
| 3 | 2 |
Find the physical address corresponding to the logical address 0x00003004.
Approach
Address translation has three steps: split the address into a page number and an offset using the page size, look the page number up in the page table to get the frame number, then recombine the frame number with the offset to form the physical address.
Steps
- The page size is 4 KB = 2^12, so the offset is 12 bits wide.
- Logical address 0x00003004:
- Page number = 0x00003004 >> 12 = 0x3 = 3
- Offset = 0x00003004 & 0xFFF = 0x004 = 4
- Look up the page table: page 3 → frame 2.
- Physical address = frame number × page size + offset = 2 × 4096 + 4 = 8192 + 4 = 8196 = 0x2004.
Answer
The physical address is 0x2004 (8196).
Problem: In a demand-paging system the page size is 1 KB, a process has the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, and it is given 3 physical frames. Compute the number of page faults and the page fault rate under FIFO, LRU and OPT.
Approach
The three algorithms differ only in which resident page they evict: FIFO evicts the one that arrived earliest, LRU evicts the one unused for the longest time, and OPT evicts the one that will be used furthest in the future. Scan the reference string once, maintaining the three frames and a fault counter.
Steps
Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (12 references), number of frames = 3.
FIFO:
- 1(fault), 2(fault), 3(fault), 4(fault, evict 1), 1(fault, evict 2), 2(fault, evict 3), 5(fault, evict 4), 1(hit), 2(hit), 3(fault, evict 5), 4(fault, evict 1), 5(fault, evict 2)
- Page faults: 9
- Page fault rate: 9/12 = 75%
LRU:
- 1(fault), 2(fault), 3(fault), 4(fault, evict 1), 1(fault, evict 2), 2(fault, evict 3), 5(fault, evict 4), 1(hit), 2(hit), 3(fault, evict 5), 4(fault, evict 1), 5(fault, evict 2)
- Page faults: 10
- Page fault rate: 10/12 ≈ 83.3%
OPT:
- 1(fault), 2(fault), 3(fault), 4(fault, evict 3), 1(hit), 2(hit), 5(fault, evict 4), 1(hit), 2(hit), 3(fault, evict 5), 4(fault, evict 1), 5(fault, evict 2)
- Page faults: 7
- Page fault rate: 7/12 ≈ 58.3%
Answer
FIFO takes 9 page faults (75%), LRU takes 10 page faults (83.3%), and OPT takes 7 page faults (58.3%).
Problem: A file system uses combined index allocation. Its inode holds 12 direct block pointers, one single-indirect pointer, one double-indirect pointer, and one triple-indirect pointer. The disk block size is 4 KB and each block pointer occupies 4 bytes. Find the maximum file size the file system can support.
Approach
First compute how many pointers fit in one disk block (block size divided by pointer size), then add up the number of blocks each level can reach — direct, single-indirect, double-indirect, and triple-indirect — and sum the results.
Steps
-
Pointers per disk block = 4 KB / 4 B = 1024.
-
Direct blocks: 12 × 4 KB = 48 KB.
-
Single-indirect: 1 × 1024 × 4 KB = 4 MB.
-
Double-indirect: 1 × 1024 × 1024 × 4 KB = 4 GB.
-
Triple-indirect: 1 × 1024 × 1024 × 1024 × 4 KB = 4 TB.
-
Maximum file size = 48 KB + 4 MB + 4 GB + 4 TB.
Answer
The maximum file size is 4 TB + 4 GB + 4 MB + 48 KB, roughly 4.004 TB.
Problem: The disk request queue contains tracks 98, 183, 37, 122, 14, 124, 65 and 67. The head is currently at track 53 and is moving towards increasing track numbers. Compute the total head movement for SCAN (the elevator algorithm) and for C-SCAN.
Approach
Both algorithms sort the request queue first and then serve the requests along the current direction. SCAN reverses at the far end; C-SCAN jumps straight back to the beginning and serves requests in one direction only. Add up the distance of each segment.
Steps
Request queue: 98, 183, 37, 122, 14, 124, 65, 67 Current head: 53, direction: increasing track numbers.
SCAN:
Serve in the increasing direction first, then reverse.
- 53 → 65 (12) → 67 (2) → 98 (31) → 122 (24) → 124 (2) → 183 (59) → 37 (146) → 14 (23)
- Total head movement = 12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299
C-SCAN:
Serve in the increasing direction up to the furthest request, then jump back to the lowest track and continue upwards.
- 53 → 65 (12) → 67 (2) → 98 (31) → 122 (24) → 124 (2) → 183 (59) → 14 (169, jump) → 37 (23)
- Total head movement = 12 + 2 + 31 + 24 + 2 + 59 + 169 + 23 = 322
Note: whether the 183 → 14 jump counts depends on the implementation; it is usually counted. If the jump is excluded, the total is 153.
Answer
SCAN moves 299 tracks in total; C-SCAN moves 322 tracks in total, including the jump.
Problem: An I/O device exchanges data with the CPU in interrupt mode, transferring 4 bytes per interrupt, and the interrupt service routine takes 2 μs. The device transfer rate is 2 MB/s. Find the fraction of CPU time spent on I/O for this device.
Approach
Convert the transfer rate into bytes per second, divide by the number of bytes per interrupt to get the interrupts per second, multiply by the CPU cost of one interrupt, and divide by one second to obtain the fraction of CPU time.
Steps
- Device transfer rate = 2 MB/s = 2 × 1024 × 1024 B/s ≈ 2,097,152 B/s.
- Each interrupt transfers 4 bytes.
- Interrupts per second = 2,097,152 / 4 = 524,288.
- CPU cost per interrupt = 2 μs.
- CPU time per second for this device = 524,288 × 2 μs = 1,048,576 μs = 1.048576 s.
- CPU time fraction = 1.048576 / 1 = 104.86%.
This exceeds 100%, which means interrupt-driven I/O cannot meet the transfer requirements of this device and DMA must be used instead.
Answer
The CPU time fraction is about 104.9%, above 100%, so interrupt-driven I/O cannot meet the requirement and DMA should be used.
Problem: A system uses SPOOLing to manage a printer. The print jobs are 100 KB, 200 KB and 50 KB; the disk transfer rate is 10 MB/s and the printer speed is 50 KB/s. Find the total time to handle the three jobs, measured from the start of input for the first job until the last job has finished printing.
Approach
SPOOLing decouples input from output: first compute the total time to write all the jobs into the input well, then the total time to read them out and print them. Because input and printing overlap, the total is the longer of the two, not their sum.
Steps
SPOOLing process: the jobs are written to disk (the input well) first, then read back from disk and printed.
-
Input time (writing to disk):
- Total data = 100 + 200 + 50 = 350 KB
- Disk write time = 350 KB / 10 MB/s = 350 / 10240 s ≈ 0.0342 s = 34.2 ms
-
Printing time (reading from disk and printing):
- Printing is the bottleneck, at 50 KB/s
- Total printing time = 350 KB / 50 KB/s = 7 s
-
SPOOLing lets input and printing overlap, and printing is the bottleneck.
- The first job can start printing as soon as its input completes
- More precisely: the first job’s input time is 100 KB / 10 MB/s ≈ 9.8 ms, after which printing starts
- Total printing time is 7 s, while the remaining input finishes quickly (34.2 ms) while printing is under way
- Total time ≈ 9.8 ms + 7 s ≈ 7.01 s
Answer
The total time is about 7.01 seconds; printing is the bottleneck, and input overlaps with it.
Problem: A computer system uses virtual memory management with a page size of 4 KB. A process has a logical address space of 64 pages, and physical memory holds 32 pages. Its page reference string has length 1000, of which 700 references hit. On a page fault, the handling time is 1 μs if a free frame is available; 10 μs if a page must be replaced and the replaced page is unmodified; and 20 μs if the replaced page is modified. Assume that 30% of the faults require a replacement of a modified page, 50% require a replacement of an unmodified page, and 20% find a free frame. Find the effective access time, assuming a memory access time of 100 ns.
Approach
First derive the fault rate from the hit count and the length of the reference string. Then weight the three kinds of fault — free frame, replacement of an unmodified page, replacement of a modified page — to get the average fault handling time, and finally combine the hit path and the fault path into the effective access time.
Steps
-
Fault rate = (1000 − 700) / 1000 = 30% = 0.3, hit rate = 70% = 0.7.
-
Average page fault handling time:
- Free frame (20%): 1 μs = 1000 ns
- Replacement, unmodified (50%): 10 μs = 10000 ns
- Replacement, modified (30%): 20 μs = 20000 ns
- Average = 0.2 × 1000 + 0.5 × 10000 + 0.3 × 20000 = 200 + 5000 + 6000 = 11200 ns
-
Effective access time (EAT):
EAT = hit rate × memory access time + fault rate × (fault handling time + memory access time) = 0.7 × 100 + 0.3 × (11200 + 100) = 70 + 0.3 × 11300 = 70 + 3390 = 3460 ns = 3.46 μs
Answer
The effective access time is 3460 ns (3.46 μs).
| Term | Abbreviation | Explanation |
|---|---|---|
| Time Slice | - | The fixed CPU time a process may use before the scheduler switches to another process |
| Turnaround Time | - | The interval between a process arriving and its completion |
| Maximum Demand | Max | The maximum amount of each resource a process may need |
| Need Matrix | - | The outstanding request of each process, equal to Max minus Allocation |
| Available Vector | - | The resources not currently allocated to any process |
| Safe Sequence | - | An ordering of all processes in which each one can finish with the resources available at that moment |
| Mutex | - | A semaphore of value 1 used to guard a critical section |
| Empty / Full | - | Semaphores counting the free and the occupied buffer slots |
| P / V Operation | - | The wait and the signal primitives of a semaphore |
| Page Fault | - | The trap raised when the referenced page is not resident in memory |
| Frame Number | - | The physical frame a page is loaded into |
| Physical Address | - | The address on the physical memory bus, formed from the frame number and the offset |
| Single / Double / Triple Indirect | - | Levels of indirection through which a file’s block addresses are reached |
| SCAN | - | The elevator disk scheduling algorithm, which sweeps in both directions |
| C-SCAN | - | The circular disk scheduling algorithm, which serves requests in one direction only |
| Head Movement | - | The total number of tracks the disk head travels to serve a request queue |
| Interrupt Service Routine | ISR | The kernel routine executed in response to an interrupt |
| Input Well | - | The disk area in which SPOOLing stores incoming jobs |
| Effective Access Time | EAT | The average time of one memory reference, weighted over hits and page faults |
| Working Set | - | The set of pages a process references over a given time window |
