[Operating System Concepts 10th] 10. Virtual Memory 리뷰 (2)

본 글은 Operating System Concepts 10th (운영체제) 책을 보며 내용을 개인 공부에 목적으로 정리했습니다.
이전에 운영체제 관련 강의들을 들으면서 정리한 시리즈 글들이 있는데,
지식을 습득하는 데 있어 가장 느리지만 가장 빠른 방법이 원본책을 자세히 보는 것이라 생각됩니다.
책 내용들을 최대한 이해하기 위해 거의 모든 내용을 담고 있습니다.

책 pdf 링크 : Operating System Concepts 10th Edition by Abraham Silberschatz Peter B Galvin Greg Gagne pdf free download
연습 문제 정답지 : Solutions of Practice Exercises, Tenth Edition of Operating System Concepts, AVI SILBERSCHATZ

이전 글 링크 : [Operating System Concepts 10th] 10. Virtual Memory 리뷰 (1)

10.4 Page Replacement

• 메모리의 초과 할당은 다음과 같이 나타난다.
  • 프로세스가 실행되는 동안 페이지 폴트가 발생한다.
  • 운영체제는 필요로 하는 페이지가 보조저장장치에 저장된 위치를 알아내지만 가용한 프레임 목록에 가용한 프레임이 없음을 발견한다.
    • 즉, 모든 메모리가 사용 중이다.

• 대부분의 운영체제는 페이지 스와핑과 페이지 교체를 결합한다.

10.4.1 Basic Page Replacement

• 페이지 교체는 다음과 같이 행해진다.
  • 만약 빈 프레임이 없다면 현재 사용되고 있지 않는 프레임을 찾아서 그것을 비워버린다.
  • 그 프레임의 내용을 스왑 공간에 쓰고 그 페이지가 메모리에 이제는 존재하지 않는다는 것을 나타내기 위해, 페이지 테이블들(모든 다른 테이블들)을 변화시킴으로써 프레임을 비어 있게 한다.
  • 이제 비워진 프레임을 페이지 폴트를 발생시킨 프로세스에서 사용할 수 있게 된다.

• 페이지 폴트 서비스 루틴(page-fault service routine)이 페이지 교체를 포함하여 다음과 같이 수정되어야 한다.

1. 보조저장장치에서 필요한 페이지의 위치를 알아낸다.
2. 빈 페이지 프레임을 찾는다.
   1. 비어 있는 프레임이 있다면 그것을 사용한다.
   2. 비어 있는 프레임이 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동시킨다.
   3. 희생될 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
4. 페이지 폴트가 발생한 지점에서부터 프로세스를 계속한다.

• 페이지 교체(Page Replacement)는 요구 페이징의 기본이다.
  • 이를 통해 논리적 메모리와 물리 메모리 간의 분리가 완성된다.
  • 이 기법을 통해 매우 작은 물리 메모리로도 프로그래머에게 광대한 가상 메모리를 제공할 수 있다.
• 요구 페이징은 논리 주소 공간의 크기가 물리 메모리에 의한 제약에서 벗어나도록 해준다.
  • 예를 들어 어떤 프로세스가 20개의 페이지로 이루어져 있으면, 10 프레임만 가지고도 요구 페이징과 필요할 때마다 빈 페이지를 찾아주는 교체 정책(replacement policy)을 이용해 이 프로세스를 실행할 수 있다.
  • 교체되려는 페이지가 변경된 경우에는 디스크에 복사된다.
  • 나중에 이 페이지를 참조하게 되면 페이지 폴트가 발생한다.
  • 그때 페이지는 메모리로 다시 돌아오게 된다.

• 요구 페이징 시스템은 2가지 중요한 문제를 해결해야 하는데, 프레임 할당(frame-allocation) 알고리즘과 페이지 교체(page-replacement) 알고리즘이다.
  • 즉, 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정해야 한다.
  • 또한, 페이지 교체가 필요할 때마다 어떤 페이지를 교체해야 할지 결정해야 한다.
• I/O가 비용이 매우 많이 든다는 것을 고려할 때, 이러한 문제를 해결할 수 있는 적절한 알고리즘을 설계하는 것은 중요한 일이다.
• 많은 페이지 교체 알고리즘이 존재하는데 일반적으로는 페이지 폴트율이 가장 낮은 것을 선정한다.

• 페이지 교체 알고리즘의 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 폴트 발생 횟수를 계산하여 평가한다.
  • 이러한 메모리 주소의 나열을 참조열(reference string)이라 한다.
  • 페이지 참조열(page reference string) : CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법 ¹
    • 참조되는 페이지들의 번호를 시간순으로 나열한 것이다.

• 일반적으로 가용 페이지 프레임 수와 페이지 폴트율은 Fig 10.11과 같은 상관관계를 나타낸다.

• 아래에서는 페이지 교체 알고리즘을 설명하기 위하여 3개의 프레임을 가진 메모리를 가정하고 페이지 참조열은 아래와 같다고 가정한다.
  • 해당 참조열이 있으면 안 바꿔도 되지만, 없다면 바꿔야 한다. 이 때 어떻게 바꿀 것인가가 앞으로 나온다.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

10.4.2 FIFO Page Replacement

• FIFO 교체 알고리즘은 어떤 페이지를 교체해야 할 때, 메모리에 올라온 지 가장 오래된 페이지를 내쫓는다.

• 그림에서는 페이지 폴트가 일어날 때마다 어떤 페이지가 3개의 프레임 속에 들어 있는가를 보여준다.
• 과정은 다음과 같다.
  • 처음에는 3개의 프레임이 비어 있다.
  • 처음 3개의 참조(7, 0, 1)는 페이지 폴트를 발생시키고 빈 프레임에 적재된다.
  • 그다음의 참조는 0인데, 0은 이미 메모리 속에 있기 때문에 페이지 폴트를 발생시키지 않는다.
  • 3에 대한 참조는 페이지 0을 교체시킨다.

• FIFO 페이지 교체 알고리즘은 이해하기도 쉽고, 프로그램하기도 쉽다.
• 그러나 성능이 항상 좋지는 않다.
  • Belady’s anomaly은 프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율은 더 증가하는 현상을 일컫는다.

10.4.3 Optimal Page Replacement

• 최적 교체 정책(Optimal Page Replacement)은 모든 알고리즘보다 낮은 페이지 폴트율을 보이며 Belady의 모순이 발생하지 않는 것이다.
• 즉, 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾는 것이다.
• 이 알고리즘은 할당된 프레임 수가 고정된 경우 가장 낮은 페이지 폴트율을 보장한다.

• 과정은 다음과 같다.
  • 처음 3번의 참조는 부재를 일으키고 3개의 비어 있는 프레임을 채운다.
  • 페이지 2에 대한 참조는 페이지 7을 교체한다.
    • 왜냐하면 7은 18번째 참조가 되어야 비로소 다시 사용되기 때문이다.
  • 페이지 3에 대한 참조는 페이지 1을 교체한다.
    • 왜냐하면 페이지 1은 메모리 속에 있는 3개의 페이지 가운데 가장 뒤에 참조되는 것이기 때문이다.

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

10.4.4 LRU Page Replacement

• FIFO 알고리즘이 페이지가 메모리로 들어온 시간을 이용하는 데 비해 OPT 알고리즘은 페이지가 사용될 시간을 이용한다는 것이다.
• LRU(least-recently-used) 알고리즘은 최근의 과거를 가까운 미래의 근사치로 본다면 가장 오랜 기간 도안 사용되지 않은 페이지를 교체하는 기법이다.
• LRU 알고리즘은 페이지마다 마지막 사용 시간을 유지한다.
• 페이지 교체 시에 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택한다.
  • 이 정책은 미래 대신 과거 시간에 대해 적용한 최적 교체 정책으로 생각할 수 있다.

• 과정은 다음과 같다.
  • 처음 5번의 부재는 최적 알고리즘과 같다.
  • 그러나, 페이지 4에 대한 참조가 일어날 때 페이지 2가 가장 오랫동안 사용된 일이 없기 때문에 페이지 2를 교체한다.
  • LRU 알고리즘은 12번의 페이지 폴트를 일으킨다.

• LRU 정책은 좋은 알고리즘으로 인정받고 있다.
• 문제는 어떻게 이 알고리즘을 구현하느냐 하는 것이다.
• 이에 프레임들을 최근 사용된 시간 순서로 파악할 수 있어야 한다.
• 2가지의 구현 방법이 가능하다.
  • 계수기(counters) : 각 페이지 항목마다 사용 시간 필드를 넣고 CPU에 논리적인 시계나 계수기를 추가한다.
    • 메모리가 접근될 때마다 시간은 증가한다.
    • 페이지에 대한 참조가 일어날 때마다 페이지의 사용 시간 필드에 시간 레지스터의 내용이 복사된다.
    • 이렇게 각 페이지의 마지막 참조 시간을 유지할 수 있다.
    • 시간 값이 가장 작은 페이지가 교체된다.
  • 스택(stack) : 페이지 번호의 스택을 유지하는 방법이다.
    • 페이지가 참조될 때마다 페이지 번호는 스택 중간에서 제거되어 스택 꼭대기(top)에 놓이게 된다.

    

스택 알고리즘(stack algorithm)은 n개의 프레임에 수록되는 페이지의 집합이 항상 n + 1개의 프레임에 수록되는 페이지 집합의 부분집합이 되는 알고리즘이다.

10.4.5 LRU Approximation Page Replacement

• 많은 시스템은 참조 비트(reference bit)의 형태로 지원을 한다.
• 페이지 참조가 있을 때마다 하드웨어가 그 페이지에 대한 참조 비트를 설정한다.
  • 참조 비트는 페이지 테이블에 있는 각 항목과 대응된다.
• 처음에 모든 참조 비트는 운영체제에 의해 0으로 채워진다.
• 프로세스가 실행되면서 참조되는 페이지의 비트는 하드웨어가 1로 세팅한다.

10.4.5.1 Additional-Reference Bits Algorithm

• 일정한 간격마다 참조 비트들을 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다.
• 각 페이지에 대해 8비트의 참조 비트를 할당한다.
• 일정한 시간 간격마다 타이머 인터럽트(timer interrupt)를 걸어서 운영체제가 참조 비트를 8비트 정보의 최상위 비트로 이동시키고 나머지 비트들은 하나씩 오른쪽으로 이동시킨다.
• 이 8비트 시프트 레지스터(shift register)는 가장 최근 8구간 동안의 그 페이지의 사용 기록을 담고 있다.
  • ex. 01110111
• 이 8비트 값을 정수로 생각하면 가장 작은 수를 갖는 페이지가 LRU 페이지가 되고 이를 교체할 수 있다.

10.4.5.2 Second-Chance Algorithm

• 2차 기회 알고리즘의 기본은 FIFO 교체 알고리즘이다. 그러나 페이지가 선택될 때마다 참조 비트를 확인한다.
• 참조 비트가 0이면 페이지를 교체하고 1이면 다시 한번 기회를 주고 다음 FIFO 페이지로 넘어간다.
• 한 번 기회를 받게 되면 참조 비트는 해제되고 도착 시간이 현재 시각으로 재설정된다.
• 이에 따라 그 페이지는 다른 모든 페이지가 교체될 때까지 교체되지 않는다.
• 따라서, 참조 비트가 계속 설정되어 있을 정도로 자주 사용되는 페이지는 전혀 교체되지 않을 것이다.

• 2차 기회 알고리즘을 구현하는 하나의 방법은 순환 큐(circular queue)를 이용하는 것이다.
• 이 큐에는 포인터가 있어서 다음에 교체될 페이지를 가리킨다.

10.4.5.3 Enhanced Second-Chance Algorithm

• 위에서 설명한 알고리즘은 참조 비트와 변경 비트를 사용하면 더 개선할 수 있다.
  • 변경 비트(modify bit)는 CPU가 페이지 내의 어떤 바이트라도 쓰게 되면 페이지가 변경되었음을 나타내기 위해 설정된다.
  • 변경 비트가 설정되어 있으면 페이지 내용이 원래 보조저장장치상의 그 페이지 내용과 달라졌다는 것을 알 수 있다.
• 이 2개의 비트를 조합하여 사용하면 다음 4가지의 등급이 가능하다.

1. (0,0) 최근에 사용되지도 변경되지도 않은 경우 - 교체하기 가장 좋은 페이지이다.
2. (0,1) 최근에 사용되지는 않았지만 변경은 된 경우 - 이 페이지는 뺏어 오려면 디스크에 내용을 기록해야 하므로 교체에 적당하지 않다.
3. (1,0) 최근에 사용은 되었으나 변경은 되지 않은 경우 - 이 페이지는 곧 다시 사용될 가능성이 높다.
4. (1,1) 최근에 사용도 되었고 변경도 된 경우 - 아마 곧 다시 사용될 것이며 뺏으려면 역시 디스크에 그 내용을 먼저 기록해야 한다.

10.4.6 Counting-Based Page Replacement

• 각 페이지를 참조할 때마다 계수를 하여 다음과 같은 2가지 기법을 만들 수 있다.
• LFU(least frequently used) 알고리즘 : 참조 횟수가 가장 작은 페이지를 교체하는 방법이다.
  • 활발하게 사용되는 페이지는 큰 참조 횟수 값을 갖게 될 것이다.
• MFU(most frequently used) 알고리즘 : 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거한다.

• 하지만 MFU나 LFU는 일반적으로 잘 쓰이지는 않는다.
• 왜냐하면 이들 알고리즘을 구현하는 데에 상당한 비용이 많이 들기 때문이다.

10.5 Allocation of Frames

• 여러 개의 프로세스들에 제한된 가용 메모리를 어떻게 할당할 것인지 알아본다.

10.5.1 Minimum Number of Frames

• 메모리 할당에는 다양한 제한이 존재한다.
• 예를 들어, 페이지 공유가 없으면 가용 프레임 수보다 더 많이 할당할 수는 없다.
• 또한 최소한 몇 페이지는 할당해야만 한다.
• 이는 성능과 관련 있는데, 각 프로세스에 할당되는 프레임 수가 줄어들면 페이지 폴트율은 증가하고 프로세스 실행은 늦어지게 된다.
• 또한, 명령어 수행이 완료되기 전에 페이지 폴트가 발생하면 그 명령어를 재실행되어야 한다.

10.5.2 Allocation Algorithms

• n개의 프로세스에 m개의 프레임을 분할하는 가장 쉬운 방법은 모두에 같은 몫 m/n 프레임씩 주는 것이다.
  • 이러한 방법을 균등 할당(equal allocation)이라 한다.
• 또 다른 대안은 프로세스마다 그 크기가 다르다는 점을 고려하는 것이다.
  • 이 문제를 풀기 위해 가용 메모리를 각 프로세스의 크기 비율에 맞추어 할당하는 방법인 비례 할당(proportional allocation) 방식을 사용할 수 있다.

10.5.3 Global Versus Local Allocation

• 다수의 프로세스가 프레임 할당을 위해 경쟁하는 환경에서 페이지 교체 알고리즘은 크게 전역 교체(global replacement)와 지역 교체(local replacement)로 나눌 수 있다.
  • 전역 교체는 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우이다.
  • 지역 교체는 각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택할 수 있는 경우이다.

• 전역 페이지 교체 정책을 구현하는 방법을 살펴본다.
• 이 방법을 사용하면 가용 프레임 리스트의 모든 메모리 요청을 충족할 수 있지만 리스트 항목의 개수가 특정 임계값 아래로 떨어지면 페이지 교체를 시작한다.
  • 이 전략은 새로운 요청을 충족시키기에 충분한 여유 메모리가 항상 남아 있도록 보장하려고 노력한다.
  • 이 임계값 아래로 떨어지면 시스템의 모든 프로세스에서 페이지를 회수하기 시작하는 커널 루틴이 촉발되는데, 이러한 커널 루틴을 리퍼(reaper)라고 부른다.

10.5.4 Non-Uniform Memory Access

• 지금까지의 가상 메모리에 관한 논의는 모든 메인 메모리가 동등하게 또는 동일하게 접근된다는 것을 가정했다.
• 하지만 여러 개의 CPU를 가진 NUMA 시스템에서 이것은 사실이 아니다.
  • 이러한 시스템에서 특정 CPU는 메인 메모리의 일정 영역을 다른 영역보다 빠르게 접근할 수 있다.
  • 시스템의 CPU와 메모리의 연결 방식이 이러한 성능의 차이를 야기한다.
• 이러한 시스템은 각각 자신의 로컬 메모리가 있는 여러 CPU로 구성된다. (Fig 10.19)
  • CPU는 공유 시스템 상호 연결을 사용하여 구성되며, CPU는 다른 CPU의 로컬 메모리보다 자신의 로컬 메모리에 빠르게 액세스 할 수 있다.

• 만약 프로세스가 페이지 폴트를 일으키면 NUMA 인식 가상 메모리 시스템은 프로세스가 실행 중인 CPU에 최대한 가까운 프레임을 할당한다.
  • 가까운의 정의는 최소 지연시간을 가짐을 뜻한다.

• NUMA를 고려하면 스케줄러는 프로세스가 마지막으로 실행된 CPU를 추적해야만 한다.
• 스케줄러는 각 프로세스를 직전에 실행된 CPU에 스케줄하고 가상 메모리 시스템은 스케줄 된 CPU와 가까운 프레임을 할당한다면, 그 결과 캐시 적중률이 높아지고 메모리 접근 시간이 감소하게 될 것이다.

References

1. 운영체제 24장 - 메모리 관리(11) : 페이지 교체 알고리즘 by ChocoPeanut ↩