Virtual Memory II

Tom Kelliher, CS42

Nov. 4, 1996

Placement Policies

How are frames allocated to processes?

Issues:

1. Minimum # of frames.

2. Static vs. dynamic policies.

3. Global vs. local.

4. Thrashing.

5. Optimizations.

6. Interaction with I/O subsystem.

Minimum Number of Frames

Must have sufficient frames in memory to execute an instruction.

Requirements:

1. Instruction fetch: One or two frames.

2. Operand fetch/store: One or two frames per operand.

3. Massive indirection?

Simple Allocation Policies

1. Equal allocation.
   1. How realistic?

2. Proportional allocation.
   1. Allocated space according to need.
      1. Process i needs pages.

      2. Total need is pages.

      3. Memory broken into m frames.

      4. Process i granted frames.

   2. How realistic?

   3. Can be generalized to priority schemes.

Problems with static policies.

Suppose we re-adjusted proportional at intervals. Any improvement?

Global and Local Replacement

If a victim page must be selected, what is the candidate pool?

1. Local: page frames of only the faulting process.

   Processes's fault rate not dependent on other process' behavior.

2. Global: any page frame.
   1. Frame stealing.

   2. Interdependence of processes.

3. Combined policy.

Thrashing

1. Degree of multiprogramming vs. CPU utilization.

2. Effect of page fault rate on CPU utilization.

3. Effect of too few frames on page fault rate.

CPU utilization low due to paging, so more processes started, making memory situation worse, leading to more paging, lowering CPU utilization, so more processes started, ...

Adaptive Allocation Policies

Attempt to adapt to process behavior.

Action on memory over-commitment?

Working Set Model

Idea:

1. ``Locality.''

2. Number of pages for each locality.

3. This is the working set.

How do we determine the working set?

1. : working set window.

2. : working set interval.

3. Every time units, examine last references and determine number of unique references. That number is the working set size.

4. How do we implement this?
   1. Must have hardware support.

   2. Reference bit.

   3. Concatenate a few reference bits.

5. What happens if the window straddles two localities, etc.?

Page Fault Frequency

1. Ultimate goal: maintain each process' page fault rate within some target region.

2. Implementation: Track each process' fault rate
   1. If above target region: allocate more frames to process.

   2. If below target regions: de-allocate frames.

3. Implementation?

Optimizations

1. Pre-paging.

2. Page Size:
   1. Reasons for large page size:
      1. Smaller page table.

      2. Maximize I/O efficiency.

   2. Reasons for small page size:
      1. Better match localities.

      2. Decrease internal fragmentation.

   3. Page sizes have increased over time to accommodate faster CPUs, memory, making page faults more costly.

3. Program Structure:
   1. Burroughs Algol: Each row of a 2-D array is allocated in a separate segment.

   2. A 1-D array is allocated in a single segment.

   3. For most speed, simulate a 2-D array with a 1-D array.

VM and the I/O Subsystem

What happens if I/O is occurring to a page and it gets paged out?

Solutions:

1. Lock buffer pages in memory.

2. All I/O occurs to kernel space with memory copies to/from user space.

3. Copies expensive; is there another way?