운영체제론[17]: 가상메모리 - 2

Page Replacement

페이지 폴트 서비스 루틴을 수정해서 메모리의 과다 할당을 방지

modify bit를 사용해서 페이지 전송의 오버헤드를 줄인다. (수정된 페이지만 디스크에 기록)

페이지 교체는 논리적 메모리와 물리적 메모리 간의 분리를 완료시킨다. (작은 물리적 메모리에서도 큰 가상 메모리 제공)

 

1. 디스크에서 원하는 페이지의 위치를 찾는다.

2. 빈 프레임을 찾는다.

- 존재하면 해당 프레임을 사용!

- 없으면 페이지 교체 알고리즘을 사용해서 대상 프레임을 선택한다. 변경된 프레임(victim)이 있다면 디스크에 기록한다.

3. 원하는 페이지를 빈 프레임에 가져와서 페이지와 프레임 테이블을 업데이트한다.

4. 트랩을 일으킨 명령을 다시 시작하여 프로세스를 계속 진행한다.

 

 

프레임 할당 알고리즘은 다음을 결정한다.

- 각 프로세스에 할당되는 프레임 수

- 어떤 프레임을 교체할 것인가

 

페이지 교체 알고리즘

- 첫 번째 액세스와 재액세스 모두에서 가장 낮은 페이지 폴트 비율을 추구

알고리즘을 평가하기 위해 특정한 메모리 참조 문자열에서 실행하고 해당 문자열에서 발생하는 페이지 폴트 수를 계산한다.

- 문자열은 페이지 번호만 포함하며 전체 주소가 아니다.

- 동일한 페이지에 반복적으로 액세스하는 것은 페이지 폴트를 일으키지 않는다.

- 결과는 사용 가능한 프레임 수에 따라 달라진다.

 

 

FIFO Algorithm

교체할 페이지 프레임으로 먼저 들어간 페이지 프레임을 선택한다.

 

페이지 프레임의 수를 증가시켰는데도 페이지 폴트가 더 많이 발생하는 현상이 생긴다.

이를 belady의 이상현상이라고 부른다.

 

 

 

Optimal Algorithm

가장 긴 시간동안 사용되지 않을 페이지를 교체한다.

최적이지만 미래를 예측해야하기에 구현하기 어렵다. 따라서 알고리즘의 성능을 측정하는데 쓰인다.

 

 

 

Least Recently Used (LRU) Algorithm

가장 오랫동안 사용되지 않은 페이지를 교체한다.

각 페이지에 마지막 사용 시간을 연결한다.

일반적으로 좋은 알고리즘이고, LRU 근사 알고리즘을 사용해서 구현할 수 있다.

 

 

카운터 구현

- 각 페이지 엔트리에 카운터가 있고, 해당 엔트리를 통해 페이지가 참조될 때마다 clock을 카운터에 복사한다.

- 페이지를 교체해야 할 때, 카운터에서 가장 작은 값을 찾는다. (테이블을 통해 검색이 필요)

 

스택 구현

- 페이지 번호를 이중 링크 형식으로 유지하는 스택

- 페이지가 참조되면 맨 위로 이동시킨다. (6개의 포인터를 변경)

- 갱신 비용이 더 비싸지만 교체를 위한 검색은 필요 없다.

- 스택 알고리즘 중 Belady의 이상현상이 없는 알고리즘이다. (OPT 또한 마찬가지)

 

위 두 방식은 하드웨어의 도움이 없으면 10배 이상 느려진다.

 

 

LRU Approximation Algorithm

LRU 알고리즘은 특별한 하드웨어를 필요로 하고 실행 속도가 느리다. 따라서 이를 근사하는 다른 알고리즘을 사용하는 경우가 많다.

 

Reference bit : 각 페이지와 연결된 비트를 사용

초기에는 0으로 설정되고, 페이지가 참조될 때마다 1로 설정된다. 이후 페이지를 교체할 때는 참조 비트가 0인 페이지를 교체한다. 하지만 이 방식으로는 페이지들이 참조된 순서를 알 수 없다.

 

Second-Chance Algorithm(clock replacement): FIFO + reference bit(하드웨어에서 제공)

교체해야 할 페이지를 결정할 때 참조비트가 0인 경우 해당 페이지를 교체한다.

만약 참조비트가 1인 경우 해당 페이지는 두 번째 기회를 받게 되며 참조 비트를 0으로 설정하고 메모리에 그대로 둔다.

그 다음으로 교체될 페이지는 동일한 규칙에 따라 결정된다.

 

 

Enhanced Second-Chance Algorithm

개선된 second-chance 알고리즘은 참조비트와 수정비트를 함께 사용한다. 이 알고리즘에서는 (참조, 수정)의 순서쌍을 사용한다.

참조	수정
0	0	최근에 사용되지도 않았고 수정되지도 않음. victim 최우선순위
0	1	최근에 사용되지 않았지만 수정된 페이지. 교체전 디스크에 쓰기를 해야한다 2순위
1	0	최근에 사용됐지만 수정되지 않은 페이지. 다시 사용 가능성 높다. 3순위
1	1	최근에 사용됐고 수정된 페이지. 다시 사용 가능성 높고 교체 전 디스크에 쓰기를 해야한다.

 

Additional reference bits algorithm : 타이머 인터럽트를 통해 OS가 주기적으로 오른쪽으로 한 비트씩 이동한다.

 

Demand paging and reference bit

Demand paging의 경우 페이지가 불려오면 조회되므로 reference bit은 1로 세팅한다.

second-chance algorithm을 사용하기 위해 주기적으로 모든 reference bit을 0으로 세팅하는 방법을 고려할 수 있다.

 

 

 

Counting Algorithms

각 페이지에 대해 참조 횟수를 카운터로 유지한다. (구현이 비싸고 OPT 알고리즘에 근접하지 못해서 일반적이지 않다.)

LFU(Lease Frequently Used) algorithm : 가장 작은 카운트를 가진 페이지를 교체한다.

MFU(Most Frequently Used) algorithm : 가장 큰 카운트를 가진 페이지를 교체한다. (가장 작은 카운트를 가진 페이지가 방금 로드됐고 아직 사용되지 않았다는 주장에 기반)

 

 

 

Page-Buffering Algorithms

항상 free-frame pool을 유지한다.

이 경우 필요할 때 프레임을 사용할 수 있고, 페이지 폴트가 발생할 때 탐색을 하지 않아도 된다.

또 페이지를 free-frame에 읽어들이고 제거할 희생자(victim)을 선택하여 free-frame pool에 추가한다.

편리할 때 victim을 제거한다.

 

modified pages의 목록을 유지할 수도 있다.

백업저장소가 다른 작업을 하지 않을 때, 미리 페이지를 백업 저장소에 쓰고 non-dirty 상태로 설정한다.

이는 시스템이 백업 저장소를 더 효과적으로 사용하도록 도와준다.

 

free-frame의 내용을 그대로 유지하고 그 안에 어떤 내용이 있는지 표시한다.

다시 참조되기 전에 재사용되면 디스크에서 내용을 다시 불러올 필요가 없다.

이 방법은 잘못된 victim frame이 선택된 경우의 패널티를 줄이는데 유용하다.

 

 

 

Applications and Page Replacement

이러한 모든 알고리즘들은 OS가 미래의 페이지 접근을 추측하고 있다는 것을 의미한다.

예를 들어, 어떤 페이지가 가장 먼저 메모리에서 제거될 것인지와 어떤 페이지가 가장 나중에 접근될 것인지 등을 추측한다.

 

데이터베이스와 같은 일부 애플리케이션들은 페이지 접근의 패턴을 알고 있을 수도 있으므로 그들 자신의 페이지 교체 전략을 구현할 수 있다.

메모리 집약적인 애플리케이션은 이중 버퍼링을 일으킬 수 있다. 이는 OS가 I/O 버퍼로서 메모리에 페이지의 복사본을 유지하고, 애플리케이션도 그것의 작업을 위해 메모리에 페이지를 유지하는 경우를 말한다.

 

운영체제는 애플리케이션에 디스크에 대한 직접적인 접근을 허용함으로써, 애플리케이션의 작업을 방해하지 않을 수 있다.

이를 raw disk mode라고 하고, 이 모드는 버퍼링, 락킹 등을 우회한다.

이를 통해 애플리케이션은 자신이 필요로 하는 방식으로 디스크에 접근할 수 있게 된다.

다만, 대부분의 응용프로그램은 그냥 파일시스템을 사용하는 것이 더 유리하다.