일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 앨런
- forEach
- IOS
- Algorithm
- 가상 메모리
- 알고리즘
- 오브젝트
- core data
- 동기화
- 인프런
- 프로세스 스케줄링
- async
- Codable
- deadlock
- 비동기
- 상호배제
- SwiftUI
- @state
- 데드락
- COLOR
- 동시성
- Linked List
- struct
- Swift
- 파일 시스템
- Apple Developer Academy
- decode
- 운영체제
- 100 days of SwiftUI
- UserDefaults
Archives
- Today
- Total
기어가더라도 제대로
[운영체제-김덕수 교수님] 가상 메모리 관리(5/6) - 가변 할당에서 교체 전략 본문
프로세스에게 할당되는 페이지 프레임의 개수가 실시간으로 변하는 상황에서,
페이지 프레임 교체전략을 알아보자.
그런데 한가지 고민이 되는 것이 있다. 앞으로 들어올 Page frame 은 예측할 수 없다.
예측 할 수 없는 실체를 어떻게 교체한단 말인가?
페이지 프레임 이외에 새로운 단위가 필요할 것 같다.
시간이라는 요소를 좀더 적극적으로 사용한 Working Set algorithm, PFF algorithm, VMIN algorithm 을 배워보자
목차.
1. 개요
2. Working Set(WS) algorithm
1. WS에서 메모리 관리
2. Window size 와 Working Set size
3. Working Set Transition
4. 성능 평가
5. 특징 및 장단점
3. Page Fault Frequency(PFF) algorithm
1. Page Fault rate 의 기준
2. PFF algorithm
3. 성능 평가
4. VMIN algorithm
1. algorithm
2. 성능 평가
3. 최적의 𝛥(델타)
5. 결론
1. 개요
- Variable allocation
- 프로세스에게 주는 메모리 공간의 크기가 프로세스 실행 중 실시간으로 변화 가능한 할당 전략
- 종류
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
- VMIN(Variable MIN) algorithm
2. Working Set(WS) algorithm
- 1968년 Denning 제안
- Working Set
- Process가 특정 시점에 자주 참조하는 page 들의 집합
- 최근 일정시간(t) 동안 참조된 page들의 집합
- window: 우리가 바라봐야하는 영역
- 예상 페이지의 개수
- 최소 : 1
- 최대 : 𝛥 + 1
- 시간에 따라 변함
- W(t, 𝛥)
- The working set of a process at time t
- Time interval [t-𝛥, t] 동안 참조된 pages 들의 집합
- 𝛥(델타): window size, system parameter
2.1. Working set memory management
- Locality에 기반을 둠
- Working set 을 메모리에 항상 유지
- Page fault rate(thrashing) 감소
- 시스템 성능 향상
- window size(𝛥) 는 고정
- Memory allocation 은 가변
- MA 가 고정 and 𝛥 가 가변 => LRU
- 𝛥 값이 성능을 결정 짓는 중요한 요소
- Memory allocation 은 가변
2.2. Window size vs. Working Set size
- locality 때문에 확 급증하다가, 점차 감소세를 띔
- 그 이유는 아무리 윈도우 사이즈를 키워도, 프로세스가 참조하는 페이지 프래임은 한 곳에 모여있을 가능성이 높아서
일정 수준을 지나면 증가세가 둔화를 띔
- 그 이유는 아무리 윈도우 사이즈를 키워도, 프로세스가 참조하는 페이지 프래임은 한 곳에 모여있을 가능성이 높아서
2.3. Working set transition
- WS 이 전환할 때 일시적으로 페이지 프레임의 수가 늘어나는 현상
- 설명하기가 너무 까다롭네요. 영상을 직접 보시길..ㅠㅠ
2.4. 성능 평가
- page fault 수 외 다른 지표도 함께 봐야 함
- Example
- Time interval[1,10]
- # of page fault = 5
- 평균 할당 page frame 수 = 3.2
- 평가
- 평균 3.2개의 page frame을 할당 받은 상태에서 5번의 page fault 발생
- Time interval[1,10]
page fault 뿐 아니라 평균 page frame 도 성능 평가시 고려해야함
2.5. 특징 및 장단점
- 적재 되는 page 가 없더라도, 메모리를 반납하는 page가 있을 수 있음
- 새로 적재되는 page 가 있을 지라도, 교체 되는 page가 없을 수 있음
단점
- working set management overhead
- Residence set(상주 집합)을 page fault 가 없더라도, 지속적으로 관리해야함
window size 가 클수록 lifeTime 도 길고 page fault rate 도 적어지지만 비용이 많이 든다.
그리고 교차점이라고 꼭 선택해야하는 것은 아니다.
3. Page Fault Frequency (PFF) 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 수를 증가
- Low page fault rate(long inter-fault time)
- Resident set 갱신 및 메모리 할당
- page fault 가 발생시에만 수행
- Low overhead
3.1. Criteria for page fault rate
- IFT > 𝜏 : Low page fault rate
- IFT < 𝜏 : High page fault rate
- 𝜏(타우) : threshold value
- System parameter
- IFT
- Inter Fault Time: page fault 가 일어난 간격의 시간
3.2. PFF Algorithm
- Page fault 발생시, IFT 계산
- IFT > 𝜏 (Low page fault rate)
- residence set <- [𝜏c-1, 𝜏c] 동안 참조 된 page 들 만 유지
- 나머지 page들은 메모리에서 내림
- 메모리 할당(# of page frame) 유지 or 감소
- IFT <= 𝜏 (higg page fault rate)
- 기존 pages 들 유지
- + 현재 참조된 page 를 추가 적재
- 메모리 할당(# of page frames) 증가
3.3. 성능 평가
- Page fault 수 외 다른 지표도 함께 봐야 함
- Example
- Time Interval [1,10]
- # of page fault = 5
- 평균 할당 page frame 수 = 3.7
- 평가
- 평균 3.7 개의 page frame 을 할당 받은 상태에서 5번의 page fault 발생
- Time Interval [1,10]
- 특징
- 메모리 상태 변호가 page fault 발생 시에만 변함
- Low overhead
- 메모리 상태 변호가 page fault 발생 시에만 변함
4. Variable MIN(VMIN) algorithm
- Variable allocation 기반 교체 기법 중 optimal algorithm
- 평균 메모리 할당량과 page fault 발생 횟수 모두 고려 했을 때의 Optimal
- 실현 불가능한 기법(Unrealizable)
- Page reference string을 미리 알고 있어야 함
- 기법
- [t, t + 𝛥]을 고려해서 교체할 page 선택
4.1. Algorithm
- page r 이 t 시간에 참조 되면
- page r 이 (t, t + 𝛥] 사이에 다시 참조되는지 확인
- 참조 된다면, page r을 유지
- 참조 안된다면, page r을 메모리에서 내림
- 잘 모르겠습니다. 문송합니다.
4.2. 성능 평가
- page fault 수 외 다른 지표도 함께 봐야 함
- Example
- Time interval[1,10]
- # of page fault = 5
- 평균 할당 page frame 수 = 1.6
- 평가
- 평균 1.6개의 page frame을 할당 받은 상태에서 5번의 page fault 가 발생
- Time interval[1,10]
4.3. 최적의 성능을 위한 𝛥(델타) 값은?
- 𝛥 = R / U
- U: 한번의 참조 시간 동안 page 를 메모리에 유지하는 비용
- R: page fault 발생 시 처리 비용
- R > 𝛥 * U (𝛥 가 작으면)
- 처리 비용 > page 유지 비용
- R < 𝛥 * U( 𝛥가 크면)
- page fault 처리비용 < 유지 비용
5. 결론
TO. 미래의 나
과거의 너는 잘 이해를 못했는데,
나중에 추가적인 자료를 보면 잘 이해하기를 바란다.
'CS > 운영체제' 카테고리의 다른 글
[운영체제-김덕수교수님] 디스크 시스템 (1/5) (0) | 2022.08.17 |
---|---|
[운영체제-김덕수 교수님] 가상 메모리 관리(6/6) - 다른 고려사항 (0) | 2022.08.17 |
[운영체제-김덕수 교수님] 가상 메모리 관리(4/6) - 교체 전략 - 고정 할당(2/2) (0) | 2022.08.17 |
[운영체제-김덕수 교수님] 가상 메모리 관리(4/6) - 고정할당 시 교체 전략 (0) | 2022.08.15 |
[운영체제-김덕수 교수님] 가상 메모리 관리(2/6) - 소프트웨어 컴포넌트 (0) | 2022.08.15 |
Comments