Chapter 9+10

Question 1

What is difference between logical and physical addresses?

Answer 1

Logical address: generated by CPU during program execution (virtual address). Physical address: actual location in physical memory. MMU translates logical to physical addresses.

Question 2

Why are page sizes always powers of 2?

Answer 2

Makes address translation efficient using bit shifting. Page number = address&raquo_space; offset_bits. Offset = address & (page_size - 1).

Question 3

What happens when two page table entries point to same frame?

Answer 3

Creates shared memory between processes. Useful for copying large memory quickly - both pages reference same physical memory. Update in one page visible in other page.

Question 4

How many bits in logical address for 64 pages of 1024 words?

Answer 4

16 bits total. 6 bits for page number (2^6 = 64 pages). 10 bits for offset (2^10 = 1024 words per page).

Question 5

How many bits in physical address for 32 frames of 1024 words?

Answer 5

15 bits total. 5 bits for frame number (2^5 = 32 frames). 10 bits for offset (same as page size).

Question 6

How do first-fit best-fit worst-fit algorithms work?

Answer 6

First-fit: allocate in first partition large enough. Best-fit: allocate in smallest partition that fits. Worst-fit: allocate in largest available partition.

Question 7

How to calculate page number and offset for address 3085 with 1KB pages?

Answer 7

Page size = 1024 bytes. Page number = 3085 / 1024 = 3. Offset = 3085 % 1024 = 13. Address 3085 is on page 3 offset 13.

Question 8

How many entries in single-level page table for 21-bit virtual address?

Answer 8

2^21 / 2^11 = 2^10 = 1024 entries (21-bit address 11-bit page size = 10-bit page number).

Question 9

How many entries in inverted page table?

Answer 9

One entry per physical frame. With 16-bit physical address and 2KB pages: 2^16 / 2^11 = 32 entries.

Question 10

What is difference between internal and external fragmentation?

Answer 10

Internal: wasted space within allocated memory block (unused space in page). External: free memory exists but not contiguous enough for allocation.

Question 11

What is required for dynamic memory allocation in contiguous allocation?

Answer 11

Must be able to expand process memory region. Requires free space adjacent to current allocation or ability to relocate entire process.

Question 12

What is required for dynamic memory allocation in paging?

Answer 12

Allocate additional pages as needed. Page table grows to include new pages. No need for contiguous physical memory.

Question 13

Why don’t mobile OS support swapping?

Answer 13

Limited storage speed (flash memory wear). Battery life concerns from frequent disk I/O. Solid state storage has limited write cycles. Better to terminate processes.

Question 14

When do page faults occur?

Answer 14

When referenced page not in physical memory. Page table entry marked invalid or not present. Hardware generates page fault interrupt.

Question 15

What actions does OS take during page fault?

Answer 15

Save process state. Determine which page caused fault. Check if reference is valid. Find free frame or use page replacement. Load page from storage. Update page table. Resume process.

Question 16

What is minimum number of page faults for any algorithm?

Answer 16

At least n page faults where n is number of distinct pages in reference string (cold start misses).

Question 17

What is maximum number of page faults for any algorithm?

Answer 17

At most p page faults where p is length of reference string (worst case: every reference is a fault).

Question 18

Rank page replacement algorithms from bad to good.

Answer 18

FIFO (suffers Belady’s anomaly) < LRU (no Belady’s anomaly) < Optimal (no Belady’s anomaly best possible).

Question 19

How does locality of reference affect page faults?

Answer 19

Good locality: recently referenced pages likely to be referenced again reducing page faults. Poor locality: random access pattern causes more page faults.

Question 20

Why does column-major array access cause more page faults?

Answer 20

Accesses elements far apart in memory. Each array row may be on different page. Row-major access has better locality staying within same page longer.

Question 21

How many page faults occur in reference string analysis?

Answer 21

Depends on number of frames and replacement algorithm. LRU and FIFO may have different fault counts. Optimal always has minimum possible faults.

Question 22

Does Belady’s anomaly indicate non-optimal algorithm?

Answer 22

Yes. Optimal algorithms cannot have Belady’s anomaly. If algorithm shows more page faults with more frames it cannot be optimal.

Question 23

What does CPU 13% disk 97% utilization indicate?

Answer 23

Thrashing: excessive paging. Processes spend more time waiting for pages than executing. Decrease multiprogramming degree.

Question 24

What does CPU 87% disk 3% utilization indicate?

Answer 24

Good balance: CPU busy but minimal paging. Can possibly increase multiprogramming degree to use more CPU.

Question 25

What does CPU 13% disk 3% utilization indicate?

Answer 25

Underutilization: processes may be I/O bound or waiting for other resources. Paging not the bottleneck. May increase multiprogramming.

Question 26

Can page table simulate base and limit registers?

Answer 26

Yes. Set up page table so all valid pages are contiguous starting from base address. Set pages beyond limit as invalid.

Question 27

How does address translation work with page tables?

Answer 27

Split virtual address into page number and offset. Use page number as index into page table. Get frame number from page table entry. Combine frame number and offset for physical address.

Question 28

What is Translation Lookaside Buffer (TLB)?

Answer 28

Hardware cache for page table entries. Stores recent address translations. Much faster than accessing page table in memory. Improves address translation performance.

Question 29

What causes TLB miss?

Answer 29

Referenced page not found in TLB cache. Must access page table in memory to get translation. More expensive than TLB hit.

Question 30

How does multi-level page table work?

Answer 30

Break page number into multiple parts. Each part indexes into different level of page table. Reduces page table size for sparse address spaces.

Question 31

What is page table entry structure?

Answer 31

Contains frame number valid bit dirty bit reference bit protection bits. May include other control bits depending on architecture.

Question 32

How does copy-on-write work?

Answer 32

Parent and child initially share same physical pages. Pages marked read-only. When either process writes to page OS copies page and updates page tables.

Question 33

What is demand paging?

Answer 33

Load pages only when referenced. Start process with no pages in memory. Generate page faults and load pages as needed. Reduces initial loading time.

Question 34

How does page replacement algorithm selection affect performance?

Answer 34

FIFO: simple but may replace frequently used pages. LRU: better performance but more complex. Optimal: best performance but requires future knowledge.