[CS] 혼공컴운 Chapter 14. 가상 메모리

14-1 연속 메모리 할당

프로세스에 연속적인 메모리 공간을 할당하는 방식.

스와핑

메모리에 적재된 프로세스들 중 현재 실행되지 않는 프로세스들(입출력 작업의 요구로 대기 상태이거나, 오랫동안 사용되지 않은 프로세스)을 임시로 보조기억장치 일부 영역으로 쫒아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식을 스와핑(swapping)이라고 한다. 

• 스왑 영역(swap space): 프로세스들이 쫒겨나는 보조기억장치의 일부 영역.
• 스왑 아웃(swap-out): 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것.
• 스왑 인(swap-in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것.
• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
• 다음 그림과 같이 프로세스A, B, C, D의 크기를 합하면 메모리의 크기보다 크지만, 스와핑을 통해 네 개의 프로세스를 동시에 실행할 수 있다.

 

메모리 할당

• 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식는 최초 적합, 최적 적합, 최악 적합의 세 가지 방식이 있다.

 

• 최초 적합(first fit)은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식.
  • 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.

 

• 최적 적합(best fit)은 운영체제가 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식.
  • 앞선 예시에서 프로세스가 적재될 수 있는 빈 공간 중 가장 작은 공간은 빈 공간 C 이므로, 최적 적합 방식으로 메모리를 할당하면 프로세스는 빈 공간 C에 할당된다.

 

• 최악 적합(worst fit)은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식.
  • 앞선 예시에서 프로세스가 적재될 수 있는 빈 공간 중 가장 큰 공간은 빈 공간 B 이므로, 최악 적합 방식으로 메모리를 할당하면 프로세스는 빈 공간 B에 할당된다.

 

외부 단편화

• 연속 메모리 할당은 메모리를 효율적으로 사용하는 방법이 아닌데, 이는 외부 단편화(external fragmentation)라는 문제를 내포하고 있기 때문이다.
• 메모리가 할당되고 해제되는 작업이 반복적으로 일어날 때, 할당된 메모리와 메모리 사이 사이에 사용하지 않는 빈 공간들이 생긴다.
• 빈 공간의 합은 충분하지만, 실제 할당 가능한 공간보다 부족하여 큰 프로세스를 할당할 수 없어 메모리가 낭비되는 현상을 외부 단편화라고 한다.

• 외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축(compaction)하는 방법이 있다.
• 메모리 내에 저장된 프로세스를 적당히 재배치시켜 빈 공간들을 하나의 큰 공간으로 만드는 방법.
• 단, 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.
• 따라서 오늘날까지 사용되고 있는 가상 메모리 기법인 페이징 기법이라는 또 다른 해결방안이 등장하였다.

 

14-2 페이징을 통한 가상 메모리 관리

가상 메모리(virtual memory)는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다. 이를 가능케 하는 가상 메모리 기법에는 페이징과 세그멘테이션이 있지만, 이 책에서는 현대 대부분의 운영체제가 사용하는 페이징 기법만을 다루고 있다.

페이징

• 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.
• 메모리와 프로세스를 일정한 단위로 자르고, 이를 불연속적으로 할당하기 때문에 외부 단편화가 발생하지 않는다.

• 페이징에서도 스와핑을 사용할 수 잇다. 프로세스 전체가 스왑 아웃/스왑 인 되는 것이 아닌 페이지 단위로 페이지 아웃/페이지 인 되며, 메모리에 적재될 필요가 없는 페이지들은 보조 기억장치에 남겨두고, 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하는 방식.

 

페이지 테이블

• 프로세스가 불연속적으로 배치되어 있기 때문에 CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워진다.
• 이를 해결하기 위해 페이징 시스템은 논리 주소에는 연속적으로 배치되도록 페이지 테이블(page table)을 이용한다.

• 페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표 역할.
• CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 한다.
• 즉, 프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

 

 

• 페이징은 외부 단편화를 해결 할 수 있지만, 내부 단편화(internal fragmentation)라는 문제를 야기할 수 있다.
• 메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리가 할당되어서 프로세스에서 사용하는 메모리 공간이 낭비되는 상황을 내부 단편화라고 한다.
• 내부 단편화는 페이지 크기보다 작은 크기로 발생하기 때문에 페이지 크기가 작다면 발생하는 내부 단편화의 크기도 작아질 것으로 기대할 수 있다. 하지만 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다.

 

 

• 프로세스마다 각자의 페이지 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다.
• CPU 내의 페이지 테이블 베이스 레지스터(PTBR: Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
• 그런데 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어나는 문제가 있다. 메모리에 있는 페이지 테이블에 접근과 그렇게 알게 된 프레임에 접근 총 두 번의 메모리 접근이 필요하기 때문이다.
• 이를 해결하기 위해 CPU 곁에 TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둔다. TLB는 참조 지역성에 근거해 최근에 사용된 페이지 위주로 가져와 저장.
• CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트라고 한다. 이 경우 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없어 메모리 접근을 한 번만 하면된다.
• 하지만 페이지 번호가 TLB에 없을 경우(TLB 미스) 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근하는 수 밖에 없다.

 

페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다. 그렇기에 특정 주소에 접근하려면 두 가지 정보가 필요하다.
  • 어떤 페이지 혹은 프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

• 따라서 페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(page number)와 변위(offset)로 이루어져 있다.
  • 페이지 테이블에서 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있다.
  • 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보.
  • 즉, 논리 주소 < 페이지 번호, 변위 > 는 페이지 테이블을 통해 물리 주소 < 프레임 번호, 변위 >로 변환된다.

 

페이지 테이블 엔트리

• 페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(PTE: Page Table Entry)라고 한다.
• 페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 뿐만 아니라 유효 비트, 보호 비트, 참조 비트, 수정 비트와 같은 중요한 정보들도 있다.
  • 유효비트(valid bit)는 현재 해당 페이지에 접근 가능한지 여부를 알려준다.
  • 보호 비트(protection bit)는 페이지 보호 기능을 위해 존재하는 비트.
  • 참조 비트(reference bit)는 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타낸다.
  • 수정 비트(modified bit)는 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려준다.

 

14-3 페이지 교체와 프레임 할당

가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스도 실행할 수 있다고는 하지만, 그럼에도 불구하고 여전히 물리 메모리의 크기는 한정되어 있다. 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야한다.

요구 페이징

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법.
  1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
  2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1) CPU는 페이지가 적재된 프레임에 접근한다.
  3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0) 페이지 폴트가 발생한다.
  4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
  5. 다시 1번을 수행.
• 순수 요구 페이징: 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 할 수도 있다. 이 경우 프로세스의 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하게 되고 실행에 필요한 페이지가 어느 정도 적재된 이후부터는 페이지 폴트 발생 빈도가 떨어진다.
• 요구 페이징 시스템이 안정적으로 작동하려면 두 가지 문제를 해결해야 한다.
  • 페이지 교체
  • 프레임 할당

 

페이지 교체 알고리즘

• 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 차게 되는데, 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 하는데, 어떤 페이지를 내보내는 것이 최선일지를 결정하는 방법이 페이지 교체 알고리즘이다.
• 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 페이지 교체 알고리즘으로 평가한다. 페이지 폴트가 일어나면 보조기억장치로부터 필요한 헤이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다.
• 페이지 참조열: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열.

CPU가 페이지에 접근한 순서 -> 2 2 2 3 5 5 5 3 3 7

• 여기서 연속된 페이지를 생략한 페이지열, 다시 말해 아래 숫자열이 페이지 참조열이다.

2 3 5 3 7

 

FIFO 페이지 교체 알고리즘

• 가장 단순한 방식으로, 메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식.

2 3 1 3 5 2 3 4 2 3

• 아래와 같이 진행되어 총 네 번의 페이지 폴트 발생. 페이지가 초기에 적재될 때 발생할 수 있는 페이지 폴트는 고려하지 않고, 적재된 페이지를 교체하기 위해 발생한 페이지 폴트만을 페이지 폴트로 간주.

• 알고리즘의 아이디어와 구현이 간단하지만 막 사용하면 안되는 이유는, 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지에서는 좋겠지만, 프로그램 실행 내내 사용될 페이지는 메모리에 먼저 적재되었다고 해서 내쫒아서는 안되기 때문이다.

 

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려하는 방식. 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘.

2 3 1 3 5 2 3 4 2 3

• 아래와 같이 총 두 번의 페이지 폴트 발생.

• 가장 낮은 페이지 폴트율을 보장하는 알고리즘. 하지만 구현이 매우 복잡한데, '앞으로 오랫동안 사용되지 않을 페이지'를 예측하는 것이 쉽지 않기 때문이다. 따라서 최적 페이지 교체 알고리즘은 그 자체를 운영체제에서 사용하기보다는, 주로 다른 페이지 교체 알고리즘에 이론상 성능을 평가하기 위한 목적으로 사용된다.

 

LRU 페이지 교체 알고리즘

• 최적 페이지 교체 알고리즘을 변형해, '가장 오랫동안 사용되지 않은 페이지'를 교체하는 알고리즘으로 구현.
• 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.
• 아래와 같이 총 세 번의 페이지 폴트 발생.

 

스래싱과 프레임 할당

• 스래싱(thrashing):프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제.

 

• 스래싱을 그래프로 표현하면 다음과 같다. 세로축인 CPU이용률은 CPU가 얼마나 쉴 새 없이 일을 하고 있는지를 알 수 있고, 가로축인 멀티프로그래밍의 정도를 통해 메모리에 올라와 있는 프로세스의 수를 알 수 있다.
• 멀티프로그래밍의 정도(메모리에서 동시 실행되는 프로세스의 수)를 늘린다고 해서 CPU 이용률이 그에 비례해서 증가하는 것이 아님을 알 수 있다.
• 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 빈번히 발생하고, 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저해되기 때문이다.

• 스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
• 따라서 운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.

 

프레임 할당 방식

• 정적 할당 방식
  • 균등 할당: 모든 프로세스에 동일한 프레임을 배분하는 방식
  • 비례 할당: 프로세스 크기에 따라 프레임을 배분하는 방식
  • 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 하는 경우가 많다.

 

• 동적 할당 방식
  • 작업 집합 모델(working set model): 프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지.
    • 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합이라고 함.
    • CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함해 운영체제는 작업 집합의 크기만큼만 프레임을 할당해 주면 된다.

 

 

• 페이지 폴트 빈도(PFF: Page-Fault Frequency): 프로세스 실행 과정에서 배분할 프레임을 결정. 페이지 폴트율에 상한선과 하한선을 결정하고 그 내부 범위 안에서만 프레임을 할당하는 방식.
  • 아래의 두 가정에 의해 생겨난 아이디어 
  • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
  • 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.

• 페이지 폴트율이 상한선보다 더 높아지면 그 프로세스는 너무 적은 프레임을 갖고 있다고 볼 수 있으며 프레임을 더 할당.
• 반대로 페이지 폴트율이 하한선보다 더 낮아지면 그 프로세스는 너무 많은 프레임을 갖고 있기 때문에 다른 프로세스에 할당하기 위해 프레임 회수.