Post

Operating System Concepts - Page Replacement

Posted
Preview Image
By Hyeon Jae Kim
20 min read
Operating System Concepts - Page Replacement

가상 메모리

10.4 페이지 교체


Over Allocating (메모리 과할당)

전체 10 페이지 중 실제로는 5페이지만을 사용하는 프로세스가 있다면, 요구 페이징을 통해 사용되지 않는 나머지 5페이지를 로드하는 I/O를 피할 수 있다.

ex) 40 프레임을 사용할 수 있는 시스템이 있다고 할 때, 10페이지를 모두 로드해야 하는 상황이였다면 4개의 프로세스를 사용할 수 있겠지만, 요구 페이징을 사용한다면 10개 중 5개는 사용되지 않으므로 8개의 프로세스를 사용할 수 있다.


그보다 더 많은 프로세스를 실행하게 되면 메모리 과할당(over-allocating) 발생

만약 10개의 페이지 중 5개만을 사용하는 6개의 프로세스를 실행시킨다면, 10개의 프레임은 남겨놓으면 높은 CPU 활용률과 처리율을 얻을 수 있다.


Q) 10 페이지를 모두 사용해야 하는 상황이 일어나면?

시스템에서는 40 프레임만 사용할 수 있는데 60 프레임을 필요로 하게 된다.


메모리 과할당은 발생 순서

  1. 프로세스가 실행하는 동안 페이지 폴트 발생
  2. 운영체제가 필요로 하는 페이지가 보조 저장장치에 저장된 위치를 알아냄
  3. 가용할 수 있는 프레임이 없음을 발견

이 시점에서 운영체제는 몇 가지 선택을 할 수 있다.



10.4.1 기본적인 페이지 교체

페이지 교체

만약 빈 프레임이 없다면 현재 사용되고 있지 않은 프레임을 찾아서 그것을 비운다.

그 프레임의 내용을 스왑 공간에 쓰고 그 페이지가 메모리에 이제는 존재하지 않는다는 것을 나타내기 위해, 페이지 테이블을 변화시킴으로써 프레임을 비어 있게 한다.

이후 비워진 프레임을 페이지 폴트를 발생시킨 프로세스에서 사용할 수 있게 된다.


  1. 보조저장장치에서 필요한 페이지의 위치를 알아낸다.

  2. 빈 페이지 프레임을 찾는다. a. 비어 있는 프레임이 있다면 그것을 사용한다. b. 비어 있는 프레임이 없다면 희생될 프레임(victim)을 선정하기 위하여 페이지 교체 알고리즘을 수행한다. c. 희생될 페이지를 보조저장장치에 기록하고(필요한 경우), 관련 테이블을 수정한다.

  3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.

  4. 페이지 폴트가 발생한 시점에서부터 프로세스를 계속한다.


이때 빈 프레임이 없는 경우 디스크에 두 번 접근해야 한다. (한 번은 프레임을 비울 때, 다른 한 번은 읽어 들일 때) 따라서 페이지 폴트 처리 시간이 2배 소요되며 그에 따라 실질 접근 시간도 증가한다.

페이지 폴트 처리 시간이 2배인 이유는 비어 있는 프레임이 있었다면 읽어들이는 작업만 하면 되지만, 그렇지 않았을 경우 비우는 작업도 필요하기 때문이다.


이러한 오버헤드는 변경 비트(modify bit 또는 dirty bit)를 사용해서 감소시킬 수 있다. 페이지가 변경되지 않았다면, 메모리로 읽혀 들어온 후 변경되지 않았다는 것이다.

따라서 해당 페이지를 보조저장장치에 기록할 필요가 없다. 이 기법은 읽기 전용 페이지들에도 적용된다. 이렇게 처리하면 I/O 시간을 반으로 줄일 수 있으므로 페이지 폴트 처리 시간을 많이 줄일 수 있다.


요구 페이징 시스템이 해결할 두 가지 문제

  1. 프레임 할당 알고리즘 : 얼마나 프레임을 할당할지
  2. 페이지 교체 알고리즘 : 어떤 기준으로 페이지를 교체할지

페이지 교체 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 폴트 발생 횟수를 계산하여 평가한다. 이때 사용되는 메모리 주소 나열을 참조열(reference string)이라 부른다. 참조열은 인공적으로 생성할 수도 있고, 주어진 시스템을 추적하여 매 메모리 참조 시의 주소를 기록할 수도 있다.



10.4.2 FIFO 페이지 교체

FIFO(First-In First-Out) 알고리즘

메모리에 올라온 지 가장 오래된 페이지를 내쫓는다.

위 예시로 보면 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다.

다음으로 2번 페이지의 요청에서 페이지 결함이 발생하고, FIFO 알고리즘에서는 가장 먼저 프레임을 할당받았던 7번 페이지를 Victim으로 선택해, 7번 페이지를 디스크에 기록하고 원래 7번이 할당받은 프레임을 2번 페이지에 새로 할당한다.

Belady의 모순

프로세스에 프레임을 더 주었는데 오히려 페이지 폴트가 더 증가하는 현상

1

1,2,3,4,1,2,5,1,2,3,4,5

이러한 참조열이 있을때 프레임이 3개 일 경우에는 페이지 폴트가 9번 발생하지만, 프레임이 4개 일 경우에는 페이지 폴트가 10번 발생한다.

더 많은 프레임을 할당하였지만 오히려 페이지 폴트율이 증가하는 현상을 의미한다. 프레임을 할당하면 성능이 좋아질 것으로 생각하지만 항상 옳지는 않다.



10.4.3 Optimal Page Replacement (최적 페이지 교체)

앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체한다.

이 알고리즘은 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.

위 예시를 비교하면 fifo 알고리즘은 15번의 page fault가 발생하지만, opt 알고리즘은 9번의 page fault를 발생시킨다.


최적 페이지 교체 알고리즘은 프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아야 하기 때문에 실제 구현이 어렵다. (따라서 주로 비교 연구 목적을 위해 사용됨)



10.4.4 LRU Page Replacement (LRU 페이지 교체)

LRU(least recently used) 알고리즘은 가장 오래 사용되지 않은 페이지를 교체한다.

페이지마다 마지막 사용 시간을 유지한다.

이를 통해 페이지 교체 시에 가장 오랫동안 사용되지 않은 페이지를 선택한다.


3개의 프레임이 비어있는 상태로 시작한다면 처음 3개(7, 0, 1)의 참조는 페이지 폴트를 발생시키고 빈 프레임에 적재된다.

이후부터는 어떤것이 가장 오래 사용되지 않았는지 확인한 후 교체한다. 그 다음의 참조(2)는 페이지 7을 교체한다. (7은 세 프레임 중 가장 이전에 사용되었다.)

그 다음의 참조(0)은 이미 메모리 속에 있기 때문에 페이지 폴트를 발생하지 않는다. (마지막 사용 시간은 갱신한다.)

그 다음의 참조(3)은 페이지 1을 교체한다. (1은 세 프레임 중 가장 이전에 사용되었다.)


LRU 구현

  1. Counter
  • 각 페이지 항목마다 사용 시간 필드를 넣고 CPU에 논리적인 시계나 계수기를 추가
  • 메모리가 접근될 때마다 시간은 증가
  • 페이지에 대한 참조가 일어날 때마다 페이지의 사용 시간 필드에 시간 레지스터의 내용이 복사됨
  • 이 방식을 통해 각 페이지의 마지막 참조 시간을 유지
  1. Stack
  • 페이지가 참조될 때 마다 페이지 번호는 스택의 중간에서 제거되어 스택 꼭대기에 놓임
  • 스택의 꼭대기 : 항상 가장 최근에 사용된 페이지
  • 스택의 밑바닥 : 항상 가장 오랫동안 이용되지 않은 페이지
  • 스택의 중간 항목을 제거할 필요가 있으므로 doubly linked list 로 구현



10.4.5 LRU Approximation Page Replacement (LRU 근사 페이지 교체)

LRU가 지원되지 않는 하드웨어를 위한 방식, 참조 비트(Referenct bit) 를 사용하여 페이지 사용 정보를 관리

참조 비트는 페이지 테이블 항목에 존재하며, 페이지가 참조될 때 하드웨어에 의해 설정된다.

참조 비트는 최초 0으로 초기화되어 있으며, 사용자 프로세스가 실행되면 각 참조되는 페이지들에 대한 참조 비트는 1로 설정된다.


이 참조 비트를 통해 어떤 페이지가 프레임에 할당된 후 사용되지 않았는지 알 수 있지만, 페이지가 사용된 순서는 알 수 없다. 이 정보가 많은 LRU-Approximation 페이지 교체 알고리즘 의 기반이 된다.



10.4.5.1 부가적 참조 비트 알고리즘 (Aging)

각 페이지에 대해 8비트의 참조 비트를 할당한다.

일정한 시간 간격마다 타이머 인터럽트를 걸어서 운영체제가 참조 비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들은 하나씩 오른쪽으로 이동시킨다.

이 8비트 시프트 레지스터는 가장 최근 8구간 동안의 그 페이지의 사용 기록을 담고 있다.


ex)

  • 만약 시프트 레지스터 값이 00000000 이라면 페이지를 8번의 구간동안 한 번도 사용하지 않았다는 뜻이고, 구간마다 최소한 한 번 이상 사용된 페이지는 11111111의 시프트 레지스터 값을 가진다.

  • 레지스터 값이 11000100인 페이지는 01110111인 페이지보다 더 최근에 사용되었다. (맨 왼쪽 1이 더 빠르므로)

이 8비트 값을 이용하여 가장 작은 수를 갖는 페이지가 LRU 페이지가 되고 이를 교체할 수 있다.


10.4.5.2 2차 기회 알고리즘

FIFO 교체 알고리즘이 베이스. 페이지가 선택될 때마다 참조 비트를 확인한다. 참조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 페이지로 넘어간다. 한 번 기회를 받게 되면 참조 비트는 해제된다.


2차 기회 알고리즘은 순환 큐로 구현할 수 있다.


10.4.5.3 개선된 2차 기회 알고리즘

참조 비트와 변경 비트 두 가지를 함께 사용한다. ( 참조비트 , 변경비트 ) 의 형태

  • 0,0 : 최근에 사용되지도 변경되지도 않은 경우 - 교체하기 가장 좋음.

  • 0,1 : 최근에 사용되지는 않았지만 변경은 된 이유 - 이 페이지는 뺏어 오려면 디스크에 내용을 기록해야 하므로 교체에 적당하지 않음.

  • 1,0 : 최근에 사용되었으나 변경은 되지 않은 경우 - 이 페이지는 곧 다시 사용될 가능성이 높음.

  • 1,1 : 최근에 사용도되었고 변경도 된 경우, 아마 곧 다시 사용될 것이며 뺏으려면 역시 디스크에 그 내용을 먼저 기록해야 함.

**2차 기회 알고리즘과의 차이는 I/O 횟수를 줄이기 위해 변경된 페이지에 대해 우선순위를 준다는 것 **



10.4.6 NRU (Not Recently Used) 페이지 교체

NRU 알고리즘은 최근에 사용된 페이지를 메모리에 유지하는 것을 선호하는 알고리즘이다.

각 페이지마다 두 개의 비트를 사용한다

  • 참조 비트(Reference bit): 페이지가 참조될 때 설정
  • 수정 비트(Modified bit): 페이지가 수정될 때 설정

일정한 시간 간격마다 타이머 인터럽트가 발생하여 모든 페이지의 참조 비트를 클리어한다.


4가지 클래스 분류

운영체제는 페이지들을 네 가지 클래스로 나누고 가장 낮은 클래스에서 무작위로 페이지를 선택해서 교체한다.

  • Class 0 : 참조 안됨, 수정 안됨 (최우선 교체 대상)
  • Class 1 : 참조 안됨, 수정됨
  • Class 2 : 참조됨, 수정 안됨
  • Class 3 : 참조됨, 수정됨 (최후순위)



10.4.7 NFU (Not Frequently Used) 페이지 교체

NFU 알고리즘은 각 페이지마다 카운터를 유지하여 사용 빈도를 추적한다.

각 페이지의 카운터는 초기에 0으로 설정한다.

클록 간격마다 해당 간격 내에 참조된 모든 페이지의 카운터를 1씩 증가하고, 페이지 교체가 필요할 때 가장 낮은 카운터를 가진 페이지를 교체한다.

문제점 : 사용 시점을 고려하지 않고 단순히 빈도만 추적

ex) 첫 번째 패스에서 많이 사용된 페이지들이 두 번째 패스에서 불필요해져도 높은 빈도 카운터 때문에 메모리에 남아있게 됨.



10.4.8 Random 페이지 교체

메모리에서 무작위로 페이지를 선택하여 교체한다.

  • 장점: 페이지 참조를 추적하는 오버헤드 비용을 완전히 제거

  • 성능: 일반적으로 FIFO보다 우수하며, 루프 메모리 참조에서는 LRU보다 나은 경우도 있음

  • 실제 특정 워크로드에서 복잡한 알고리즘의 오버헤드가 이익을 상쇄할 때 사용:
    • OS/390에서 LRU 근사치를 사용하다가 LRU 성능이 저하될 때 Random으로 전환

References

운영체제
OS
This post is licensed under CC BY 4.0 by the author.