오래 못 할 짓 하지 않기

[ 운영체제 ] 25. Virtual memory - Replacement 본문

3학년 1학기/운영체제 (OS)

[ 운영체제 ] 25. Virtual memory - Replacement

쫑알bot 2024. 6. 1. 23:21
728x90

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 ) 로 생각해봤을 때

 

 

https://4legs-study.tistory.com/54

 

페이지에 정보 수정이 일어났지만, DISK에는 저장이 안 되었음. 

 


수정되었다 = DISK에 업데이트를 해줘야 한다 = 교체할 때 업데이트 시간도 추가되므로 오래 걸린다.

 

※ Frame이 많을 때 Page faults 는?

 

대체로 줄어든다.

예외도 있다. = Belady’s anomaly

 

 

(참고)

 

한동대학교 고윤민 교수님 - 운영체제

https://4legs-study.tistory.com/54