Virtual Memory II
Tom Kelliher, CS42
Nov. 4, 1996
How are frames allocated to processes?
- Minimum # of frames.
- Static vs. dynamic policies.
- Global vs. local.
- Interaction with I/O subsystem.
Must have sufficient frames in memory to execute an instruction.
- Instruction fetch: One or two frames.
- Operand fetch/store: One or two frames per operand.
- Massive indirection?
- Equal allocation.
- How realistic?
- Proportional allocation.
- Allocated space according to need.
- Process i needs pages.
- Total need is pages.
- Memory broken into m frames.
- Process i granted frames.
- How realistic?
- Can be generalized to priority schemes.
Problems with static policies.
Suppose we re-adjusted proportional at intervals. Any improvement?
If a victim page must be selected, what is the candidate pool?
- Local: page frames of only the faulting process.
Processes's fault rate not dependent on other process' behavior.
- Global: any page frame.
- Frame stealing.
- Interdependence of processes.
- Combined policy.
- Degree of multiprogramming vs. CPU utilization.
- Effect of page fault rate on CPU utilization.
- 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, ...
Attempt to adapt to process behavior.
Action on memory over-commitment?
- Number of pages for each locality.
- This is the working set.
How do we determine the working set?
- : working set window.
- : working set interval.
- Every time units, examine last references and
determine number of unique references. That number is the working set
- How do we implement this?
- Must have hardware support.
- Reference bit.
- Concatenate a few reference bits.
- What happens if the window straddles two localities, etc.?
- Ultimate goal: maintain each process' page fault rate within some
- Implementation: Track each process' fault rate
- If above target region: allocate more frames to process.
- If below target regions: de-allocate frames.
- Page Size:
- Reasons for large page size:
- Smaller page table.
- Maximize I/O efficiency.
- Reasons for small page size:
- Better match localities.
- Decrease internal fragmentation.
- Page sizes have increased over time to accommodate faster CPUs,
memory, making page faults more costly.
- Program Structure:
- Burroughs Algol: Each row of a 2-D array is allocated in a
- A 1-D array is allocated in a single segment.
- For most speed, simulate a 2-D array with a 1-D array.
What happens if I/O is occurring to a page and it gets paged out?
- Lock buffer pages in memory.
- All I/O occurs to kernel space with memory copies to/from user space.
- Copies expensive; is there another way?
Thomas P. Kelliher
Fri Nov 1 22:29:05 EST 1996