가상 메모리

연속 메모리 할당

메모리 공간에 프로세스를 연속적으로 할당하는 방식을 연속 메모리 할당 이라고 한다.

프로세스들을 실행하다보면 메모리 공간이 가득 차게 되는데 그러면 새로운 프로세스를 할당할 수 없게 된다.
이 때, 오랫동안 사용하지 않은 프로세스를 보조기억장치 일부 영역으로 임시로 쫒아내고
그렇게 마련된 빈 공간에 새 프로세스를 적재하곤 하는데 이릘 스와핑(swapping) 이라고 한다.

• 스왑 영역 (swap space)
  쫒겨난 프로세스를 임시로 보관하는 보조기억장치의 일부 영역

• 스왑 아웃 (swap out)
  현재 실행되지 않는 프로세스를 메모리에서 스왑 영역으로 옮기는 것

• 스왑 인 (swap in)
  스왑 영역에 있던 프로세스를 다시 메모리로 옮겨오는 것
  기존의 물리 주소와는 다른 곳에 적재될 수 있다

이를 통해 프로세스들이 요구하는 메모리 공간 크기가 실제 메모리 크기보다 큰 경우에도
문제 없이 프로세스를 동시에 실행할 수 있다.

메모리 내 빈 공간이 여러 개 있을 때 프로세스를 할당하는 방식은 여러 가지가 있지만
그 중 대표적인 세 가지를 알아보도록 하겠다.

• 최초 적합 (front fit)
  운영체제가 메모리 내 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 배치
  검색을 최소화하여 빠른 할당 가능

• 최적 적합 (best fit)
  운영체제가 메모리 내 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 배치
  잉여 공간의 최소화 가능

• 최악 접합 (worst fit)
  운영체제가 메모리 내 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 배치

연속 메모리 할당은 단순하고 간편하지만 외부 단편화 (external fragmentaion) 문제를 내포하고 있다.
이것은 프로세스를 할당하기 어려울 만큼 작은 공간들로 인해 메모리가 낭비되는 현상이다.
이러한 잉여 공간들이 쌓이면 낭비되는 공간이 상당히 많기 때문에 반드시 해결해야 하는 문제다.

외부 단편화 문제를 해결하기 위해 메모리를 압축 (compaction) 할 수 있는데,
잉여 공간을 한 데 모으는 동안의 오버헤드가 크기 때문에 단점이 많다.

이 문제를 해결하는 다른 방법으로는 페이징 기법이 있다.

더 알아보기
[컴퓨터 공학 기초 강의] 37강. 연속 메모리 할당

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

프로세스의 일부만 메모리에 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행할 수 있는 기법을
가상 메모리(virtual memory) 라고 하며, 크게 페이징, 세그멘테이션의 두 가지 기법이 있다.

현재 대부분의 운영체제는 페이징 기법을 통해 가상 메모리를 구현한다.

페이징(paging) 은 메모리와 프로세스를 일정한 단위로 자르고
프로세스를 메모리에 불연속적인 조각 단위로 할당하는 기법이다.

• 페이지 (page)
  프로세스의 논리 주소 공간을 일정한 크기 단위로 자른 것

• 프레임 (frame)
  메모리의 물리 주소 공간을 일정한 크기 단위로 자른 것

페이지와 프레임은 동일한 크기로 설정되며, 이 크기 단위로 메모리 할당이 이루어진다.

프로세스 크기가 페이지 단위의 배수로 나누어 떨어지지 않기에 마지막 페이지에는 잉여 공간이 생길 수 있는데
이를 내부 단편화(internal fragmentation) 라고 하지만, 외부 단편화보다는 훨씬 적은 양이다.

페이지 또한 스왑 인/아웃 될 수 있는데, 이 때는 프로세스 단위가 아닌 페이지 단위로 이동한다.
프로세스 단위의 이동과 구분하여 페이지 아웃 (page out), 페이지 인 (page in) 이라고도 한다.

페이지를 사용하면 외부 단편화 문제를 해결할 수 있을 뿐만 아니라, 물리 메모리보다 큰 프로세스도 실행할 수 있다.

페이지는 메모리에 불연속적으로 적재되기 때문에 그대로 사용하기 어려운데
논리 주소의 연속성을 유지한 채 불연속적인 페이지와 맵핑하기 위해 페이지 테이블(page table) 을 이용한다.

페이지 테이블은 페이지 번호와 프레임 번호를 맵핑해둠으로써
CPU가 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 해준다.
이를 통해 CPU는 프로세스들이 메모리에 분산되어 있더라도 논리 주소를 통해 순차적으로 실행한다.

각각의 프로세스는 고유의 페이지 테이블을 메모리에 가지고 있으며
PCB의 페이지 테이블 베이스 레지스터(PTBR) (page table base register) 에 그 시작 주소가 담긴다.

페이지 테이블은 메모리에 저장되기 때문에, 이를 통해 페이지에 접근하면
메모리 접근을 두 번 해야 한다는 문제가 있어 참조 지역성에 근거한 일종의 캐시 메모리를 두는데
일반적으로 MMU 내에 존재하며 TLB (translation lookaside buffer) 라고 부른다.
캐시 메모리와 마찬가지로 참조하고자 하는 페이지 존재 유무를 TLB 히트/미스 (TLB hit/miss) 라고 하며
TLB 미스 시 페이지 테이블을 참조하기 위해 메모리에 접근한다.

특정 주소에 접근하기 위해서는 두 가지 정보가 필요한데,
이에 따라 페이징 시스템의 논리 주소는 두 부분으로 이루어져 있다.

• 페이지 번호 (page number)
  접근하고자 하는 페이지가 무엇인지 나타내는 N 비트
• 변위 (offset)
  접근하고자 하는 주소가 페이지 내 어디에 저장되어 있느닞 나타내는, N 비트를 제외한 나머지 비트

<페이지 번호, 변위>로 구성된 논리 주소는 페이지 테이블을 거쳐 <프레임 번호, 변위>로 구성된 물리 주소로 변환된다.

페이지 테이블의 각각의 행들은 페이지 테이블 엔트리(page table entry) 라고 하는데
페이지 번호, 프레임 번호 외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트 등의 정보가 포함되어 있다.

• 유효 비트 (valid bit)
  현재 해당 페이지에 접근 가능한지 여부
  아직 적재되지 않았거나 스왑 아웃되었을 경우 0이 되며, 접근 시도 시 페이지 폴트 page fault 예외 발생

• 보호 비트 (protection bit)
  읽고 쓰기가 가능한 페이지인지 여부
  쓰기가 가능하면 1, 읽기 전용일 경우 0의 값
  읽기/쓰기/실행하기의 3개 비트로 보다 상세한 권한을 설정하도록 구현할 수도 있다

• 참조 비트 (reference bit)
  CPU가 접근한 적 있는지 여부

• 수정 비트 (modified bit)
  해당 페이지에 데이터를 쓴 적 있는지 수정 여부
  더티 비트 dirty bit 라고도 한다
  메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 결정

프로세스의 모든 테이블 페이지 엔트리를 메모리에 유지하는 것은 비효율적이기 때문에
계층적 페이징 hierarchical paging 을 통해 여러 단계의 페이지를 두기도 한다.

더 알아보기
[컴퓨터 공학 기초 강의] 38강. 페이징을 통한 가상 메모리 관리

페이지 교체와 프레임 할당

프로세스를 메모리에 적재할 때 모든 페이지를 적재하지 않고 필요한 페이지만 적재하는 기법을
요구 페이징(demand paging) 이라고 한다.

그 중에서도 처음엔 아무 페이지도 적재하지 않은 채 실행부터 하고서
페이지 폴트가 발생할 때마다 하나씩 적재하는 방식을 순수 요구 페이징(pure demand paging) 이라고 한다.

요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당이 잘 이루어져야 한다.

요구 페이징 기법으로 페이지를 적재하다보면 메모리가 가득 차게 되어 스왑 아웃을 해야 하는데
어떤 페이지를 스왑 아웃 할 것인지 결정하는 방법을 페이지 교체 알고리즘 이라고 한다.
페이지 교체 알고리즘은 페이지 폴트를 적게 일으킬수록 좋은 알고리즘이다.

페이지 교체 알고리즘의 성능 측정 지표가 되는 페이지 폴트 횟수는
페이지 참조열(page reference string) 을 통해 알 수 있다.
CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지열을 페이지 참조열이라고 한다.

대표적인 페이지 교체 알고리즘으로는 다음과 같은 것들이 있다.

• FIFO 페이지 교체 알고리즘 (First-In First-Out page replacement algorithm)
  가장 단순한 방법으로, 메모리에 가장 먼저 올라온 페이지부터 교체 대상으로 삼는 방식
  초기에 적재된 페이지는 초반에만 실행되고 말 수도 있지만,
  프로그램 실행 내내 사용할 내용을 포함할 경우 비효율적일 수 있다

• 2차 기회 페이지 교체 알고리즘 (Second Chance page replacement algorithm)
  FIFO 페이지 교체 알고리즘을 보완하여 두 번째 기회를 주는 방식
  교체 대상 페이지가 참조된 적 없는 페이지일 경우 그냥 교체하지만
  참조된 적 있는 경우 참조 비트를 0으로 만든 후 현재 시각을 적재 시각으로 설정하여
  오래되었지만 자주 쓰이는 페이지가 쫒겨나지 않도록 한다

• 최적 페이지 교체 알고리즘 (Optimal page replacement algorithm)
  CPU에 의해 참조되는 횟수를 고려하는 방식
  자주 사용될 페이지는 남기고 앞으로 오랫동안 사용하지 않을 페이지는 교체할 수 있도록 한다
  "앞으로 오랫동안 사용하지 않을 페이지"를 예측하기 어려워 실제적으로 사용되기 보다는 이론 상의 성능 지표

• LRU 페이지 교체 알고리즘 (Least Recently Used page replacement algorithm)
  최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라고 예측하는 방식
  마지막 사용 시각을 토대로 사용한지 가장 오래된 페이지를 교체

비효율적인 페이지 교체 알고리즘을 사용할 때뿐만 아니라
프로세스가 사용할 수 있는 프레임 수가 적은 경우에도 페이지 폴트가 자주 발생한다.
이게 과해지면 프로세스 실행 시간보다 페이징에 더 많은 시간을 소요하여 성능 저하가 발생하는데
이러한 문제를 스레싱(thrashing) 이라고 한다.

메모리에서 동시 실행되는 프로세스가 늘어 멀티프로그래밍의 정도(degree of multiprogrammming) 가 높아지면
어느 정도까지는 CPU 이용률이 높아지며 성능이 좋아지다가 어느 순간 스레싱이 발생하여 성능이 저하된다.
그 근본적인 원인 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.

• 정적 할당 방식
  프로세스의 실행 과정은 고려하지 않고 단순히 프로세스 크기와 물리 메모리의 크기만 고려한 프레임 할당 방식

  • 균등 할당 (equal allocation)
    프로세스 개수에 따라 정확히 1/N 하여 할당하는 방식
  • 비례 할당 (proportional allocation)
    프로세스 크기에 따라 비례하게 할당하는 방식

• 동적 할당 방식
  프로세스의 실행을 보고 할당할 프레임 수를 결정하는 방식

  • 작업 집합 모델 (working set model) 을 이용하는 방식
    프로세스가 일정 기간 동안 참조한 페이지 집합을 기억하여 작업 집합 working set 을 만들고
    이 작업 집합의 크기에 따라 프레임을 할당하는 방식
  • 페이지 폴트 빈도 (page fault frequency) 를 이용하는 방식
    페이지 폴트율이 높으면 프레임 수가 적다고 판단하여 늘리고
    페이지 폴트율이 낮으면 프레임 수가 많다고 판단하여 줄이는 방식

더 알아보기
[컴퓨터 공학 기초 강의] 39강. 페이지 교체와 프레임 할당
[컴퓨터 공학 기초 강의] 40강. 페이징의 이점과 계층적 페이징