Tutorial Week 10

Questions and Answers

Virtual Memory

Q1: What effect does increasing the page size have?

• Increases internal fragmentation
• Decreases number of pages
• Increases TLB coverage
• Increases page fault latency
• Increases swapping I/O throughput

Q2: Why is demand paging generally more prevalent than pre-paging?

Pre-paging requires predicting the future (which is hard) and the penalty for making a mistake may be expensive (may swap out a needed page for an unneeded page).

Q3: Describe four replacement policies and compare them.

• Optimal
  • Toss the page that won’t be used for the longest time
  • Impossible to implement
  • Only good as a theoretic reference point: The closer a practical algorithm gets to optimal, the better
• FIFO
  • First-in, first-out: Toss the oldest page
  • Easy to implement
  • Age of a page is isn’t necessarily related to usage
• LRU
  • Toss the least recently used page
  • Assumes that page that has not been referenced for a long time is unlikely to be referenced in the near future
  • Will work if locality holds
  • Implementation requires a time stamp to be kept for each page, updated on every reference
  • Impossible to implement efficiently
• Clock
  • Employs a usage or reference bit in the frame table.
  • Set to one when page is used
  • While scanning for a victim, reset all the reference bits
  • Toss the first page with a zero reference bit.

Q4: Translate the following virtual addresses to Physical Addresses using the TLB. The system is a R3000. Indicate if the page is mapped, and if so if its read-only or read/write.

The EntryHi register currently contains 0x00000200.

The virtual addresses are 0x00028123, 0x0008a7eb, 0x0005cfff,0x0001c642, 0x0005b888, 0x00034000.

See page 6-2 of the MIPS R3000 Hardware Guide for revising TLB operation.

Results
VAddr	PhysAddr	Access
0x00028123		Invalid
0x0008a7eb		Invalid (ASID mismatch)
0x0005cfff	0x006a8fff	Global bit, R/W
0x0001c642	0x00a97642	R/W
0x0005b888	0x002af888	Read-only
0x00034000	0x001fc000	R/W

Q5: Describe programmed I/O and interrupt-driven I/O in the case of receiving input (e.g. from a serial port). Which technique normally leads to more efficient use of the CPU? Describe a scenario where the alternative technique is more efficient.

For programmed I/O, the CPU waits for input by continuously reading a status register until it indicates input data is ready, afterwhich, the CPU can read the incoming data, and then return to reading the status register wainting for further input.

For interrupt-driven I/O, the serial port device sends an interrupt to the CPU when data is ready to be read. The interrupt handler is then invoked, which acknowledges receiving the interrupt, reads the data from the device, and returns from the interrupt. The CPU is free for other activities while not interrupt processing.

Programmed I/O is normally less efficient as the CPU is busy waiting for input when input is unavailable.

Programmed I/O can be more efficient in circumstances where input it frequent enough such that the overhead of interrupts (getting into and out of the interrupt handler) is more than the average time spent busy waiting. A realistic example is fast networking where packets are nearly always available.

Q6: A device driver routine (e.g. read_block() from disk) is invoked by the file system code. The data for the filesystem is requested from the disk, but is not yet available. What do device drivers generally do in this scenario?

They block on a synch primitive that is later woken up by the disk interrupt handler when the block is available.

Q7: An example operating system runs its interrupt handlers on the kernel stack of the currently running application. What restriction does this place on the interrupt handler code? Why is the restriction required?

The interrupt handler must not block waiting for a resource, as it indirectly blocks the application that was running.

If the application has the resource the interrupt handler requires (e.g. memory buffers), the system is deadlocked.

Page last modified: 11:57am on Monday, 18th of May, 2009

Print Version