Segmentation
Identify the Algorithm – 100 pts
A process requests 18 units.
The free list of holes (in memory units): [10, 25, 12, 20]
After allocation, the hole sizes become [10, 7, 12, 20].
Which algorithm was used?
What is Best Fit ?
Reasoning: 25 was the smallest hole large enough for 18 → leftover 7 units.
Clue:
A system has a segment table:
Segment Base Limit
0 1000 200
1 5000 500
If a program generates logical address (1, 300), what happens?
Offset 300 > limit 500 → valid? Check: 300 < 500 → valid
Physical address = base + offset = 5000 + 300 = 5300
Given: shared variable x=0, two threads increment x 3 times each. If mutex used, final x=?
Without Mutex
Same as above but no mutex → possible final x values?
3+3 = 6
Without Mutex:
Any integer between 3 and 6, depending on interleaving
Identify the Algorithm
Process | Arrival | Burst | Start | Finish
P1 | 3 | 30 | 57 | 87
P2 | 7 | 25 | 32 | 57
P3 | 2 | 30 | 2 | 32
Average Response Time and Turnaround Time?
What is Preemptive Shortest Remaining Time First (SRTF)
Why: P3 starts at time 2 and runs until 32 (it had burst 30 → ran continuously). P2 first runs starting at 32 (P2 arrived at 7, P1 at 3 but P2 finishes earlier than P1). The ordering indicates scheduler picks the process with shortest remaining time as new arrivals occur — fits SRTF
Response time = start − arrival.
P1: start 57 − arrival 3 = 54
P2: start 32 − arrival 7 = 25
P3: start 2 − arrival 2 = 0
Sum responses = 54 + 25 + 0 = 79.
Average response = 79 / 3 = 26.333... → 26.33 (rounded to 2 dp).
Turnaround = finish − arrival.
P1: 87 − 3 = 84
P2: 57 − 7 = 50
P3: 32 − 2 = 30.
Average turnaround = 164 / 3 = 54.666... → 54.67.
| PID | Arrival | Burst |
|-----|--------|------|
| P1 | 0 | 10 |
| P2 | 2 | 4 |
| P3 | 5 | 6 |
Scheduler: FCFS
Compute: Average Turnaround Time.
Round-Robin q=4
Compute Average Response Time.
SJF non-preemptive
Compute Average Response Time.
Avg TAT = (10+12+15)/3 = 12.33
RR
Response time = start−arrival: P1=0, P2=4−2=2, P3=8−5=3
Avg = (0+2+3)/3 = 1.67
SJF non-preemptive
Response times: P1=0−0=0, P2=10−2=8, P3=14−5=9
Avg = (0+8+9)/3 = 5.67
Identify the Algorithm
Free list before: [8, 15, 22, 30]
A process requests 20 units.
After allocation, the list becomes [8, 15, 2, 30].
Which algorithm?
What is First Fit?
Reasoning: The allocator picks the first hole that fits the process (hole 22) without checking for smallest or largest.
Given a virtual address 0x12345678 and page size 4 KB, what is the page number and offset?
Page size = 4 KB = 2¹² → offset = lower 12 bits = 0x678
Page number = remaining upper bits = 0x12345
✅ Page # = 0x12345, Offset = 0x678
Producer-Consumer
Buffer size=3, producer produces 5 items, consumer consumes 5. Minimum buffer state after first 5 steps?
0 (consumer can keep pace)
Identify the Algorithm
Process | Arrival | Burst | Start | Finish
P1 | 3 | 30 | 32 | 62
P2 | 7 | 25 | 62 | 87
P3 | 2 | 30 | 2 | 32
Find average Response & Turnaround
What is First-Come First-Served (FCFS)?
Why: Execution order: P3 (arrived 2) runs first 2→32, then P1 (arrived 3) runs 32→62, then P2 (arrived 7) runs 62→87. That matches arrival order (2,3,7) with no preemption.
Avg response = 84 / 3 =
What is 28.00?
Avg turnaround = 169 / 3 = 56.33
What is 56.33?
1. Free list = [10, 15, 20, 5]
Allocate 12 units using Best Fit → new list
2. Start with [10, 3, 20, 5]
Allocate 12 units using Worst Fit → new list?
1.
Smallest hole ≥12 → 15 → remaining=3
New list: [10, 3, 20, 5]
2.
Largest hole = 20 → 20−12=8
New list: [10, 3, 8, 5]
Clue:
Free list: [9, 15, 8, 2]
Need: 12 units
Apply First Fit.
First hole large enough = 15
Allocate 12 → leftover = 3
New list: [9, 3, 8, 2]
Address Translation
A machine uses paging with page size 1 KB. The page table is stored in memory. A process issues virtual address 0x0FA3. Page table starts at physical frame 0x2000, and page 0xF maps to frame 0x300. What is the physical address?
What is Physical Address 0xC03A3 ?
Deadlock
Given 2 resources R1,R2 and 2 threads T1,T2:
T1 locks R1 then R2
T2 locks R2 then R1
Will deadlock occur?
Yes → classic circular wait
Identify Algorithm
Process | Arrival | Burst | Start | Finish
P1 | 3 | 30 | 32 | 61
P2 | 7 | 25 | 7 | 32
P3 | 2 | 30 | 2 | 90
What is Preemptive Priority or Shortest-Job? — actually this is Priority (preemptive)
Reasoning: P2 starts at time 7 (immediately when it arrives) and finishes at 32. P1 starts at 32 and finishes at 61. P3 started at 2 but then CPU was given to P2 at 7 and P3 finishes last at 90 and had large total finish. If dispatching at arrival 7 preempted P3 in favor of P2 (which arrived later), that implies P2 had a higher priority than P3 — a priority preemptive scheduler. It could match a priority-based preemption more naturally than SRTF because P2 ran to completion even though P1 had arrived earlier than P2 but P1 only started after P2 finished. So label as Preemptive Priority (explain in class that some input ambiguity can exist; check additional data like remaining times to disambiguate).
(If you want strict SRTF: you'd expect the shortest remaining to preempt; but numbers here align better with priority preemption.)
Avg response = 29 / 3 = 9.67
Avg turnaround = 171 / 3 = 57.00
16-bit virtual address, page size = 256 bytes. Virtual address = 0x1234 → Page # and Offset?
Page size=256=2⁸ → offset = lower 8 bits = 0x34
Page number = upper 8 bits = 0x12
Page#=0x12, Offset=0x34
Free list: [9, 3, 8, 2]
Need: 5 units
Previous allocation ended at index 2 (the hole with 3 units).
Apply Next Fit starting after the 3-unit hole.
Start after index 2 (hole with size 3 → next is 8)
Hole 8 fits 5 → leftover = 3
New list = [9, 3, 3, 2]
Next search pointer moves to index 3.
A 64-bit machine uses a 3-level page table. Page size = 4 KB. Each page table entry = 8 bytes. How many bytes are required to store the page table for a 4 GB process?
4 GB = 2³² bytes → number of pages = 2³² / 2¹² = 2²⁰ pages
Each entry = 8 bytes → total entries = 2²⁰ → total bytes = 8 * 2²⁰ = 2²³ bytes = 8 MB
✅ Total page table = 8 MB
32-bit virtual address, 4 KB pages, 2-level table. Compute entries per level.
Page size=4 KB=2¹², 32-bit → 2²⁰ pages total → 2¹⁰ entries per level
Identify Algorithm
Process | Arrival | Burst | Start | Finish
P1 | 3 | 30 | 7 | 87
P2 | 7 | 25 | 12 | 62
P3 | 2 | 30 | 2 | 82
Average Response and Turnaround time
What is Round-Robin (RR) with quantum leading to many context switches ?
Why: Start times overlap and none of the processes run to completion early; P1 first runs at 7 (not arrival 3) which suggests some rotation; P2 starts at 12; P3 started at 2. The long duration to completion with interleaving is typical of RR. To be certain we’d need slice-by-slice trace; but treating it as RR is consistent with the mixed start/finish order.
Avg response = 9 / 3 = 3.00
Avg turnaround = 219 / 3 = 73.00
| Segment | Base | Limit |
|---------|------|-------|
| 0 | 2000 | 100 |
| 1 | 4000 | 200 |
Logical address = (1, 150) → Physical?
Segment table same as above. Logical address = (0, 250) → valid?
Offset 150 < limit 200 → valid
Physical = 4000+150 = 4150
Offset 250 > limit 100 → invalid → segmentation fault
A system uses segmentation with the following segment table for a process:
Segment Base Limit
0 200 100
1 400 50
2 1000 150
If the CPU generates the logical address (2, 120), what is the physical address?
If it generates (1, 75), what happens?
For (2, 120): offset 120 < limit 150 → valid
→ physical = base + offset = 1000 + 120 = 1120
For (1, 75): offset 75 ≥ limit 50 → Segmentation fault (out of bounds)
Memory Management:
Page Fault Calculation
Accesses=1000, fault rate=2%, service=10ms → total penalty?
10000.0210ms=200ms
Free Space Management
Bitmap: 16 bits, bits=1 if allocated [1,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0] → next free block?
Index 1
Processes:
P1: arrival 0, burst 8
P2: arrival 1, burst 4
P3: arrival 2, burst 9
Show the RR order (q=5), compute response and turnaround averages
What is
t=0..5: P1 runs for 5 (remaining P1=3). P1’s first start = 0.
t=5..10: queue at t=5 has P2 (arr1) and P3; next is P2 (arrived 1). P2 runs for min(5,4)=4 → completes at t=9. P2 first start = 5.
t=9..14: next is P3 (arr 2). P3 runs for 5 → remaining P3=4; first start = 9.
t=14..17: back to P1 remaining 3 → runs 3, completes at t=17.
t=17..21: P3 remaining 4 → runs 4, completes at t=21
Avg response = 11/3 = 3.67
Avg turnaround = 44/3 =14.67
Priority Scheduling
Processes with priority (lower # = higher priority):
| PID | Burst | Priority |
|-----|-------|---------|
| P1 | 5 | 3 |
| P2 | 3 | 1 |
| P3 | 4 | 2 |
Compute execution order and average turnaround time.
P2→P3→P1, TAT: P2=3, P3=7, P1=12 → Avg=7.33