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.

Exercise 1

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.

Round RobinProcess SchedulingTurnaround TimeProcess Management

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.

Exercise 2

Problem: There are 5 processes P0–P4 and 3 resource types A(10), B(5), C(7). The resource allocation at time T0 is:

ProcessMax(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)
  1. Find the Need matrix and the Available vector at time T0.
  2. Is the system in a safe state at T0? If so, give a safe sequence.
Banker AlgorithmDeadlock AvoidanceSafe SequenceDeadlock

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.

Exercise 3

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.

SemaphoreProducer-ConsumerSynchronisationMutual Exclusion

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.

Exercise 4

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 numberFrame number
05
19
214
32

Find the physical address corresponding to the logical address 0x00003004.

PagingAddress TranslationPage TableMemory Management

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

  1. The page size is 4 KB = 2^12, so the offset is 12 bits wide.
  2. Logical address 0x00003004:
    • Page number = 0x00003004 >> 12 = 0x3 = 3
    • Offset = 0x00003004 & 0xFFF = 0x004 = 4
  3. Look up the page table: page 3 → frame 2.
  4. Physical address = frame number × page size + offset = 2 × 4096 + 4 = 8192 + 4 = 8196 = 0x2004.

Answer

The physical address is 0x2004 (8196).

Exercise 5

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.

Page ReplacementFIFOLRUOPTVirtual Memory

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%).

Exercise 6

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.

Combined IndexInodeFile AllocationFile System

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

  1. Pointers per disk block = 4 KB / 4 B = 1024.

  2. Direct blocks: 12 × 4 KB = 48 KB.

  3. Single-indirect: 1 × 1024 × 4 KB = 4 MB.

  4. Double-indirect: 1 × 1024 × 1024 × 4 KB = 4 GB.

  5. Triple-indirect: 1 × 1024 × 1024 × 1024 × 4 KB = 4 TB.

  6. 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.

Exercise 7

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.

Disk SchedulingSCANC-SCANI/O System

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.

Exercise 8

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.

Interrupt-Driven I/OI/O SystemCPU OverheadPerformance Analysis

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

  1. Device transfer rate = 2 MB/s = 2 × 1024 × 1024 B/s ≈ 2,097,152 B/s.
  2. Each interrupt transfers 4 bytes.
  3. Interrupts per second = 2,097,152 / 4 = 524,288.
  4. CPU cost per interrupt = 2 μs.
  5. CPU time per second for this device = 524,288 × 2 μs = 1,048,576 μs = 1.048576 s.
  6. 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.

Exercise 9

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.

SPOOLingI/O SystemVirtual DeviceDevice Sharing

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.

  1. 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
  2. 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
  3. 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.

Exercise 10

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.

Virtual MemoryEffective Access TimePage FaultPerformance Analysis

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

  1. Fault rate = (1000 − 700) / 1000 = 30% = 0.3, hit rate = 70% = 0.7.

  2. 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
  3. 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).


Glossary

TermAbbreviationExplanation
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 DemandMaxThe 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 RoutineISRThe kernel routine executed in response to an interrupt
Input Well-The disk area in which SPOOLing stores incoming jobs
Effective Access TimeEATThe 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

Found an issue with this content?

Tell us what could be improved.