Virtual memory
- logical memory를 physical memory로 부터 분리
- 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법
- 파일의 공유를 쉽게 해주고 shared memory 구현을 가능하게 함.
- process 생성에 효과적
(맨 오른쪽 -> harddisk)
Demand Paging
- page가 실제로 필요할때만 memory로 가져옴.
- I/O 횟수 줄어듬
- 필요한 memory 줄어듬
- response time이 줄어듬 (faster response)
- user 늘어남
- 특정 page가 필요
- invalid regerence → abort
- not-in-memory → bring to memory
Valid-Invalid Bit
-
1→in-memory, 0→not-in-memory
-
0으로 초기화된 상태에서 시작
-
process가 memory에 올라와있지 않은 page(0)를 접근하려 하면 page fault 발생.
-
일부 page가 main memory에 없을때의 page table
Page Fault
- Invalid page에 대한 reference라면 그 프로세스는 중단된다.
- Valid reference인데 page가 단지 memory에 있지 않다면
- empty(free) frame을 가져온다
- page를 frame안으로 Swap (Disk에 frame으로 page를 읽어오도록 요청)
- table reset, validation bit =1로 한다
- instruction restart
- free frame이 없다면?
- 희생양 선택
- algorithm
- performance : page fault가 최소화되는 알고리즘이 좋음
- Same page가 여러번 memory위로 올라올 수 있음.
- 희생양 선택
Demand Paging의 성능
- Page Fault Rate 0 ≤ p ≤ 1.0
- p = 0 no page faults
- p = 1, every reference is a fault
- Effective Access Time (EAT)
ex)
- Memory access time = 1 microsecond
- 50% 확률로 page가 memory로 올라왔을 때 변경됨 → 변경되면 swapped out
- Swap Page Time = 10 msec = 10,000 microsec
Page Replacement
- page service routin은 page replacement를 포함해 memory over-allocation을 방지
- modify(dirty) bit
- page 전송 overhead 줄임.
- 수정된 페이지만 디스크에 기록됨
- page replacement로 logical과 physical memory 분리
- 더 작은 physical memory → 대용량 가상 메모리 제공 가능
- 디스크에서 필요한 페이지의 위치를 알아낸다
- 빈 페이지 프레임을 찾는다
- 빈 프레임이 있으면 그것을 사용
- 없다면 page replacement algorithm을 가동해 victim frame 선정
- 희생될 페이지를 디스크에 기록하고, 관련 테이블 수정
- 빼앗은 페이지를 디스크에 기록하고 테이블을 수정
- 사용자 프로세스 재시작
-
page fault rate가 낮은 알고리즘을 선택
-
측정 메모리 참조 string에서 알고리즘을 실행하여 알고리즘을 평가하고 해당 문자열에서 page fault 수 계산
-
Page Faults vs The Number of Frames
FIFO Algorithm
ex)
- regerence string : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
- FIFO Replacement – Belady’s Anomaly 비정상적 현상
- more frames ⇒ more page faults
- FIFO Illustrating Belady’s Anomaly
- FIFO Page Replacement
Optimal Algorithm
-
가장 장기간 사용하지 않을 page replacement
-
미래를 알아야함. 따라서 비현실적인 알고리즘
- 다른 알고리즘과 비교해서 그 알고리즘의 성능 측정. 즉 이 알고리즘이 100점짜리
-
5번 paging이 들어갈 때, 가장 오래 사용안할 것 같은 page는 4. 따라서 victim=4.
-
Optimal Page Replacement
Least Recently Used (LRU) Algorithm
- 가장 오랜기간동안 사용되지 않은 page 교체
- Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
- Counter 구현
- 모든 page entry에는 counter가 있다.
- page가 reference 될때 마다 entry를 통해 counter에서 clock을 복사한다.
- page를 변경해야 할 경우 counter를 확인해 변경할 page를 결정한다.
- Stack(LIFO)구현
- 페이지 번호 스택을 double link 형식으로 유지
- Page referenced
- TOP으로 이동
- 6 개의 pointer를 변경 요구됨
- Search for replacement 없음
- Stack을 사용한 Most Recent Page References
Counting-Based Page Replacement Algorithm
별로 안쓰임
- LFU (Least Frequently Used)
- 참조 횟수가 가장 작은 페이지를 교체하는 방법
- MFU (Most Frequently Used)
- 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거함
