[운영체제] 가상 메모리 관리 (요구 페이징, 페이지 교체 알고리즘)

요구 페이징 기법

 

: 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것

-> 페이지를 미리 가져 오는 방식은 가져온 페이지를 쓰지 않을 경우, 메모리를 낭비하게 된다. 따라서 요구 페이징을 사용하면 메모리의 절약, 메모리의 효율적 관리, 프로세스의 응답 속도 향상 등의 효과를 볼 수 있다.

 

 

요구 페이징과 스왑 영역

 

- 페이지가 스왑 영역에 있는 경우

(1) 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우

(2) 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우

 

 

페이지 테이블 엔트리(PTE)의 구성

1) 페이지 번호

2) 프레임 번호

3) 플래그 비트

   - 접근 비트(access bit): 페이지가 메모리로 올라온 후 사용한 적이 있는지 알려주는 비트

   - 변경 비트(modified bit): 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트

   - 유효 비트(valid bit): 페이지가 실제 메모리에 있는지를 나타내는 비트

          -> 유효 비트가 0인 경우: 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장된다.

          -> 유효 비트가 1인 경우: 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장된다.

   - 읽기(read), 쓰기(write), 실행(execute) 비트: 페이지에 대한 읽기, 쓰기, 실행 권한을 나타내는 비트

 

 

페이지 부재(page fault) / 페이지 교체

물리 메모리의 5번 공간이 비어있는 상황에서 D 페이지 요청이 들어왔을 때

: 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황 (스왑 영역에 있는 상황)

-> 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨줘야 한다.

->이때 물리 메모리에 빈 공간이 있다면 그 자리로 페이지를 가져오면 되지만 만약 빈 공간이 없이 물리 메모리가 가득 차 있는 상태라면 어떤 페이지 하나를 스왑 영역으로 내보내고(스왑 아웃) 원하는 페이지를 빈 공간에 넣어야 한다. (스왑 인)

 

페이지 교체: 페이지 부재가 발생하면 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 업데이트하는 과정

- 빈 프레임이 없을 때에는 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후에 해당 페이지를 가져올 수 있다. 

 

E 페이지를 요청하였는데 빈 프레임이 없을 때

1) 페이지 테이블 4번의 유효 비트를 확인해보니 1이다 즉, 스왑 영역에 있다는 뜻 -> 페이지 부재 발생 

2) 물리 메모리에 빈 프레임이 없으므로 스왑 영역으로 보낼 대상 페이지를 선정하여 스왑 영역으로 보낸다.(스왑아웃)-> 예시에서는 A

3) 페이지 테이블의 대상 페이지 유효 비트와 주소를 변경한다. (업데이트 1)

4) 대상 페이지가 나가고 생긴 빈 프레임에 요청 페이지를 가져온다.(스왑인)

5) 페이지 테이블의 요청 페이지 유효 비트와 주소를 변경한다. (업데이트 2)

-> 페이지 테이블 업데이트가 두번 일어난다.

 

 

페이지 교체 알고리즘

 

: 스왑 영역으로 보낼 페이지를 결정하는 알고리즘

 

대상 페이지(victim page): 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지

 

지역성(locality): 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질

-> 페이지 교체 알고리즘이 쫓아낼 페이지를 찾을 때 지역성을 바탕으로 한다.

  (1) 공간의 지역성: 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높다.

  (2) 시간의 지역성: 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다.

  (3) 순차적 지역성: 여러 작업이 순서대로 진행되는 경향이 있다.

 

메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킨다.

 

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정
	FIFO	처음 메모리에 올라온 페이지를 대상 페이지로 선정
이론적 알고리즘	최적	미래의 접근 패턴을 미리 보고 대상 페이지 선정
최적 근접 알고리즘	LRU	시간적으로 멀리 떨어진 페이지가 대상 페이지
	LFU	사용 빈도가 적은 페이지가 대상 페이지
	NUR	최근에 사용한 적이 없는 페이지가 대상 페이지
	FIFO 변형	FIFO 알고리즘을 변형하여 성능을 높임

-> 성능 평가 기준: 책에서는 메모리 접근 패턴을 동일하게 사용해서 페이지 부재 횟수와 페이지 성공 횟수를 비교한다.

공통으로 사용할 메모리 접근 패턴

 

 

무작위 페이지 교체 알고리즘 random page replacement algorithm

 

: 스왑 영역으로 쫓아낼 대상 페이지를 특별한 로직없이 무작위로 선정

- 지역성을 전혀 고려하지 않기 때문에 자주 사용하는 페이지가 대상 페이지로 선정되기도 하여 성능이 좋지 않다.

 

 

FIFO 페이지 교체 알고리즘 

 

: 시간상으로 메모리에 가정 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다.

: 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고, 나머지 페이지들은 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어온다.

- 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다.

 

 

최적 페이지 교체 알고리즘 optimal page replacement algorithm

 

: 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다.

: 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리있는 페이지를 대상 페이지로 선정한다.

- 이상적인 방법이지만 실제로 구현할 수는 없다.

 

 

최적 근접 알고리즘 optimal approximation algorithm

 

: 실제 구현이 가능하면서도 성능이 최적 근접 알고리즘에 근접한 알고리즘

(1) LRU 페이지 교체 알고리즘

(2) LFU 페이지 교체 알고리즘

(3) NUR 페이지 교체 알고리즘

(4) FIFO 변형 알고리즘

 

 

LRU(Least Recently Used) 페이지 교체 알고리즘

 

(= 최근 최소 사용 페이지 교체 알고리즘)

: 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮긴다.

: 최근에 사용된 페이지는 놔두고 오래 전에 사용된 페이지를 대상 페이지로 선정한다. 

-> 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용하는 방법도 있다.

 

(1) 페이지 접근 시간에 기반한 구현

: 페이지에 접근한 지 가장 오래된 페이지를 교체한다.

-> 페이지 성공 횟수: 4번

 

(2) 카운터에 기반한 구현

: 시간 대신 카운터를 사용하여 구현

 

(3) 참조 비트를 이용한 구현 -> 참조 비트 시프트 방식

: 각 페이지에 일정 크기의 참조 비트를 만드는 것

-> 참조 비트의 초기 값은 0이며 페이지에 접근할 때마다 1로 바뀐다.

-> 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동하므로, 오래될수록 오른쪽으로 1이 이동한다.

-> 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정한다

 

* 참조 비트 시프트 방식이 LFU가 아니라 LRU 페이지 교체 알고리즘인 이유

: 시각을 기준으로 하기 때문에!!!

-> 접근 횟수로 따지면 C가 가장 많지만 참조 비트 값은 C가 가장 작기 때문에 C가 대상 페이지가 된다.

 

 

LFU(Least Frequently Used) 페이지 교체 알고리즘

: 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정하는 알고리즘

: 현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮김

-> 페이지 성공 횟수: 5번

 

 

NUR 페이지 교체 알고리즘

 

(= 최근 미사용 페이지 교체 알고리즘)

: LRU, LFU 페이지 교체 알고리즘은 성능은 좋으나 추가적인 오버헤드가 크다. 이를 개선하기 위해 두 개의 비트만으로 구현한 알고리즘

- 페이지마다 참조비트와 변경비트를 가진다.

    페이지에 접근(read/execute)하면 참조 비트 1, 페이지가 변경(write/append)되면 변경 비트 1

- 모든 페이지의 초기 상태는 (0, 0)

- 모든 값이 (1, 1)이 되면 초기화한다.

- 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.

- 같은 비트의 페이지가 여러 개라면 무작위로 대상 페이지를 선정한다.

-> 페이지 성공 횟수: 5번 

 

 

FIFO 변형 알고리즘 

 

(1) 2차 기회 페이지 교체 알고리즘

: 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외시켜준다.

: 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 준다.

: FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용한다.

-> 페이지 성공 횟수: 4번

 

(2) 시계 알고리즘

: 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용한다.

: 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용한다.

: 포인터가 큐의 맨 바닥으로 내려가면 다음 번에는 다시 큐의 처음을 가리키게 된다.

- 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가되었다.

- 참조 비트의 초깃 값은 0, 메모리에 있는 페이지를 성공적으로 참조하면 1로 변경한다.

- 대상 포인터는 메모리가 꽉 찰 경우 스왑 영역으로 쫓아낼 페이지를 가리킨다.

- 가리키는 페이지가 스왑 영역으로 쫓겨나면 대상 포인터를 밑으로 이동하는데 이때 참조 비트가 1인 페이지는 0으로 만든 후 건너뛴다 (2차 기회를 주는 것)

-> 페이지 성공 횟수: 4번

 

* 쉽게 배우는 운영체제 책 참고