오래 못 할 짓 하지 않기
[ 운영체제 ] 25. Virtual memory - Replacement 본문
https://min-h-study-review.tistory.com/259
Page Replacement
demand paging 의 문제점은 2가지가 있다.
1. Page replacement 알고리즘을 어떤 걸로 할건지 (우린 이걸 알아볼거임)
: page fault를 가능한 조금 내는 방향의 알고리즘
= Backing store에 접근하는 시간이 많이 걸리니까 그걸 최대한 줄이려는 것
2. Frame allocation 알고리즘은 어떤 걸로 할건지
: 한 프로세스당 얼만큼의 프레임을 줘야 할지
어느 프레임에 교체할지
Page replacement 알고리즘
● 돌아가는 방식:
Page fault 가 일어났을 때 Free frame이 없다면, 현재 사용되지 않는 frame을 찾아야 한다.
위 사진에서 보면, B를 사용하려고 page table을 봤을 때 invalid 이다.
▶ Backing store 에서 B를 찾아서 Physical mem에 넣으려고 하는데 이미 자리가 없다
▶ 그럼 누굴 빼고 B를 넣을거냐?
= Page Replacement 알고리즘에 따라 다르다
1. Disk에서 필요한 page의 위치를 찾는다.
2. Free Frame을 찾는다.
3. 필요했던 page를 Frame에 넣고, Page,Frame table을 업데이트 한다.
4. Page fault 로 인해 진행되지 않았던 명령어를 다시 실행한다.
▲ EAT랑 관련있음
2가 들어왔을 때 누가 빠질지를 정해야 한다.
● 사용하는 알고리즘
- FIFO page replacement
- Optimal page replacement
- Least-recently-used(LRU) page replacement
- LRU-approximation page replacement
FIFO page replacement
먼저 들어왔던 애가 가장 먼저 나간다
= 제일 오래 있었던 애가 나간다.
7 0 1 순서로 입력들은 그 전에는 비어있으니 그냥 들어옴
그 후에 2가 들어오려고 하면 자리가 없다.
▶누가 나가야하나?
▶ 7이 가장 먼저 들어온 ( 오래 있었던) 애니까 나간다.
● 문제점 : Belady's anomaly가 발생한다.
= 프레임 수는 더 많은데, fault 수가 늘어나는 경우
Optimal page replacement
앞으로 가장 (오랜 기간) 쓰이지 않을 애를 내보낸다.
● 문제점 : 쓰일지 안 쓰일지 어떻게 알아낼거임?
Least Recently Used (LRU) Page Replacement
쓰인지 제일 오래 된 애를 뺀다.
= 최근에 쓰인 애들을 냅둔다.
현재로서는 가장 최적으로 알려져 있음
7-0-1 하고 2가 들어온 시점에, 7이 가장 마지막에 쓰였으니 뺌
= 2-0-1 로 교체됨. ,
그 뒤에 0이 들어왔을 때는 최근 쓰인 순서가 1 - 2 - 0 이다.
이 상태에서 3이 들어오면 가장 예전에 쓰인 1이 빠진다.
= 2-0-3
그럼 이 LRU는 어떻게 구현해야 할까?
● Counter ( 시간 측정 )
: 페이지를 Reference 할 때마다 counter(현재 시간)을 복사해서 저장한다.
= Victim은 counter값이 가장 작은 값
Entry에 Time-of-used field 를 추가한다.
● page를 Stack으로
: Page들을 Stack에 넣는다.
하지만 중간에 있던 애가 다시 Reference되면 Stack 꺼내서 다시 위로 보낼 수 있다
= 완벽히 Stack이라고 하기엔 좀 모순이 있음
그냥 이렇게 구현하기보단 Hardware의 지원을 받는 게 나을 것 같은데 지원받을 수 있는 게 많이 없다.
그래서 고안된 게 아래와 같다.
LRU - approximation algorithm
여기엔 2가지가 있는데
◼ Additional-reference-bit algorithm
◼ Second-chance algorithm
Additional-reference-bit algorithm
: 각 페이지마다 Reference bit를 만들어서 돌리자.
모든 page에 변수를 추가해서, 0으로 초기화 시킨다.
▶ page가 referenced 되면 1로 설정한다.
▶ 만약 replace해야한다면, reference bit가 0인 걸 바꾼다.
- 한계점
1. Reference 가 다 된 상태에서는..??
2. 0이 여러 개일 땐 누굴 빼야함..?
Second-chance algorithm
: FIFO + Reference bit
reference bit이 0이면 바로 replace한다.
bit이 1이면, bit를 0으로 바꾼다 (이제 replace될 수 있는 상태)
두 번 문 두드려야 replace된다.
Victim을 찾고 있음.
> reference bit이 0이면 replace / 1이면 0으로 바꾸고 점프
> 현재 가리키는 애가 1임, 0으로 바꾸고 점프 , 그 다음 애도 똑같음
> 현재 가리키는 애에서 밑에 밑에 애는 0. 걔가 victim이 된다.
1인 애들은 기회 2번임. 2번째에 당한다.
Second-chance Algorithm 에서 한 단계 더 나가면
Modify bit도 추가된다.
( reference bit , modify bit ) 로 생각해봤을 때
페이지에 정보 수정이 일어났지만, DISK에는 저장이 안 되었음.
수정되었다 = DISK에 업데이트를 해줘야 한다 = 교체할 때 업데이트 시간도 추가되므로 오래 걸린다.
※ Frame이 많을 때 Page faults 는?
대체로 줄어든다.
예외도 있다. = Belady’s anomaly
(참고)
한동대학교 고윤민 교수님 - 운영체제
https://4legs-study.tistory.com/54
'3학년 1학기 > 운영체제 (OS)' 카테고리의 다른 글
[ 운영체제 ] 27. Storage Management (0) | 2024.06.11 |
---|---|
[ 운영체제 ] 26. Virtual memory - Frame allocation / Thrashing (0) | 2024.06.03 |
[ 운영체제 ] 24. Virtual memory (0) | 2024.05.28 |
[ 운영체제 ] 23. Page Table / Swapping (0) | 2024.05.24 |
[ 운영체제 ] 22. Page / Frame (0) | 2024.05.21 |