운영체제. 가상 메모리 관리
Replacement Strategies(교체 기법)
Fixed allocation
- MIN(OPT, B0) algorithm
- Random algorithm
- FIFO(First In First Out) algorithm
- LRU(Least Recently Used) algorithm
- LFU(Least Frequently Used) algorithm
- NUR(Not Used Recently) algorithm
- Clock algorithm
- Second change algorithm
Variable allocation
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
- VMIN(Variable MIN) algorithm
지난번까지 Fixed allocation을 알아봤고, 이번 강의부턴 variable allocation을 공부합니다!
Variable Allocation
- 할당하는 메모리의 크기가 가변적인 방법이다.
총 3가지 방법이 있다: WS(Working Set) algorithm, PFF(Page Fault Frequency) algorithm, VMIN(Variable MIN) algorithm
1. WS(Working Set) algorithm
- 1968년 Denning이 제안
- Working set
- Process가 특정 시점에 자주 참조하는 page들의 집합
- 최근 일정 시간(Δ)동안 참조된 page들의 집합
- 시간에 따라 변함
- W(t, Δ)
- The working set of a process at time t
- Time interval(t-Δ, t)동안 참조된 pages들의 집합
- Δ: window size, system parameter
- Locality에 기반
- Working set을 메모리에 항상 유지
- Page fault rate(thrashing) 감소
- 시스템 성능 향상
- Window size(Δ)는 고정
- Memory allocation은 가변
- Δ값이 성능 결정 짓는 중요한 요소
- locality 때문에 윈도우가 커져도 working set사이즈 증가율이 감소하는 지점이 온다.(쓰는 것만 계속 쓰기 때문에.)
성능 평가
- Page fault수 외 다른 지표도 함께 봐야 함
- Example
- Time interval [1,10]
- # of page fault = 5
- 평균 할당 page frame 수 = 3.2
- 평가
- 평균 3.2개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
특성
- 적재되는 page가 없더라도 메모리를 반납하는 page가 있을 수 있음
- 새로 적재되는 page가 있더라도, 교체되는 page가 없을 수 있음
단점
- Working set management overhead(윈도우 지속적으로 관찰해야 함)
- Residence set(상주 집합)을 page Fault가 없더라도 지속적으로 관리해야 함.
Mean number of frames allocated vs page fault rate
- window size가 증가하면 page fault는 감소하지만, 메모리 lifetime도 증가하기 때문에 page 유지비용이 증가한다.
- 이런 것들을 고려해서 적절한 지점을 잘 찾아야 한다.
2. PFF(Page Fault Frequency) algorithm
- Residence set size를 page fault rate에 따라 결정
- Low page fault rate(long inter-fault time)
- Process에게 할당된 PF 수를 감소
- High page fault rate(short inter-fault time)
- Process에게 할당된 PF 수를 증가
- Resident set 갱신 및 메모리 할당
- Page fault가 발생시에만 수행
- Low overhead
Criteria for page fault rate
- IFT > τ('타우' 라고 읽는다): Low page fault rate
- IFT < τ: High page fault rate
- τ: threshold value
- System parameter
- IFT: Inter Fault Time(페이지 폴트간의 시간 간격)
Algorithm
## 3. VMIN(Variable MIN) algorithm
Example
성능 평가
- 평균 3.7개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
특징
- 메모리 상태 변화가 page fault 발생 시에만 변함
- Low overhead
3. Variable MIN(VMIN) algorithm
- Optimal algorithm(최적의, 이상적인, 구현 불가능한)
- 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 Optimal
- 실현 불가능한 기법(Unrealizable)
- Page reference string을 미리 알고 있어야 함
- 기법
- [t, t+ Δ]을 고려해서 교체할 page 선택
Algorithm
- Page r이 t 시간에 참조 되면, Page r이 (t, t+ Δ) 사이에 다시 참조되는지 확인
- 참조 된다면, page r을 유지
- 참조 안 된다면, apge r을 메모리에서 내림
Example
성능 평가
- 평균 1.6개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
최적 성능을 위한 Δ값
총 3가지 방법이 있다: WS(Working Set) algorithm, PFF(Page Fault Frequency) algorithm, VMIN(Variable MIN) algorithm
- Process가 특정 시점에 자주 참조하는 page들의 집합
- 최근 일정 시간(Δ)동안 참조된 page들의 집합
- 시간에 따라 변함
- W(t, Δ)
- The working set of a process at time t
- Time interval(t-Δ, t)동안 참조된 pages들의 집합
- Δ: window size, system parameter
- Page fault rate(thrashing) 감소
- 시스템 성능 향상
- Memory allocation은 가변
- Δ값이 성능 결정 짓는 중요한 요소
- Time interval [1,10]
- # of page fault = 5
- 평균 할당 page frame 수 = 3.2
- 평가
- 평균 3.2개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
- Low page fault rate(long inter-fault time)
- Process에게 할당된 PF 수를 감소
- High page fault rate(short inter-fault time)
- Process에게 할당된 PF 수를 증가
- Page fault가 발생시에만 수행
- Low overhead
- System parameter
- Low overhead
- 평균 메모리 할당량과 page fault 발생 횟수 모두 고려했을 때의 Optimal
- Page reference string을 미리 알고 있어야 함
- [t, t+ Δ]을 고려해서 교체할 page 선택
--------------------------------------------------
Other Considerstaions
- Page size
- Program restructuring
- TLB reach
1. Page Size
- 일반적인 page size
Small page size
- Page Table이 크다. (오버헤드 큼)
- 내부 단편화 감소
- I/O 시간 증가
- Locality 향상
- Page fault 증가
Large page size
- page table이 작다. (오버헤드 작음)
- 내부 단편화 증가
- I/O시간 감소
- Locality 저하
- Page fault 감소
페이지 크기는 클수록 좋은걸까? 아니면 작을수록 좋은걸까?
- No best Answer
- 하지만 요즘은 페이지 크기가 점점 커지는 추세다. 이유는?
- HW의 발전 경향과 연관이 있다.
- CPU 성능도 증가하고 메모리 사이즈도 등가하는 추세.
- 메모리 속도 보다 CPU 속도의 증가가 압도적이기 때문에, I/O를 최소화하는게 좋다.(I/O많으면 CPU가 메모리 기다리느라 병목현상 생김)
2.Program restructuring
- 가상 메모리 시스템의 특성에 맞도록 프로그램을 재구성
- 사용자가 가상 메모리 관리 기법(예, paging system)에 대해 이해하고 있다면, 프로그램의 구조를 변경하여 성능을 높일 수 있음
- 예를 들어 이중 for loop을 비효율 적으로 도는 아래 코드를 수정하며 성능을 개선할 수 있다.
3.TLB reach
- Direct Address Mapping 할 때 느린 속도의 한계를 개선하기 위해 두는 HW.
TLB Reach란?
- TLB를 통해 접근할 수 있는 메모리의 양
- the number of entries \* the page size
TLB의 Hit ratio를 높이려면?
- TLB 크기 증가
- Expensive
- Page 크기 증가 or 다양한 page size 지우너
- OS의 지원이 필요
Author And Source
이 문제에 관하여(운영체제. 가상 메모리 관리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@kpl5672/운영체제.-가상-메모리-관리
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
- HW의 발전 경향과 연관이 있다.
- CPU 성능도 증가하고 메모리 사이즈도 등가하는 추세.
- 메모리 속도 보다 CPU 속도의 증가가 압도적이기 때문에, I/O를 최소화하는게 좋다.(I/O많으면 CPU가 메모리 기다리느라 병목현상 생김)
- TLB를 통해 접근할 수 있는 메모리의 양
- the number of entries \* the page size
- Expensive
- OS의 지원이 필요
Author And Source
이 문제에 관하여(운영체제. 가상 메모리 관리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kpl5672/운영체제.-가상-메모리-관리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)