# Chp 10 Virtual Memory

###### tags: `作業系統`

## P.5~7

### Virtual memory
* separation of user logical memory from physical memory

### Virtual address space
* logical view of how process is stored in memory

## P.8 Virtual-address Space

## P.9

## P.10 Demand Paging

* Bring a page into memory only when it is needed

## P.11

## P.12~13 Valid-Invalid Bit

## P.14,15 Page Fault


## P.16 Aspects of Demand Paging

* Locality of reference
Avoid multiple page faults

## P.17~20 Demand Paging

* **Effective Access Time**(EAT)
$EAT = (1 – p) \times \text{memory access} \\ ~~~~~~~~~~~~~+ p \times (\text{page fault overhead} + \text{swap page out} + \text{swap page in} )$

## P.22~24 Copy-on-Write
* Allows both parent and child processes to initially **share** the same pages in memory.

## P.26~29 Page Replacement

* Prevent over-allocation of memory
* Use **modify (dirty) bit** to reduce overhead of page transfers

### Replacement

* Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to select a victim frame
- Write victim frame to disk if dirty


## P.30 Page and Frame Replacement Algorithms

## P.31~43 Page-replacement algorithm

### FIFO Algorithm


* **Belady’s Anomaly**
Adding more frames can cause more page faults
$e.g.$ 1,2,3,4,1,2,5,1,2,3,4,5

### Optimal Algorithm

* Replace page that will not be used for **longest period of time**
* Not that possible to implement

### Least Recently Used (LRU) Algorithm


### LRU Approximation Algorithms

### Enhanced Second-Chance Algorithm

### Counting Algorithms

#### Lease Frequently Used (LFU) Algorithm
replaces page with
smallest count

#### Most Frequently Used (MFU) Algorithm

### Page-Buffering Algorithms