[혼자 공부하는 컴퓨터구조+운영체제]14장 가상 메모리

14-1 연속 메모리 할당

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

스와핑

• 스와핑: 메모리에서 사용하지 않는 프로세스를 보조기억창지로 내보내고, 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
  • 스왑 영역: 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
  • 스왑 아웃: 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
  • 스왑 인: 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
• 프로세스는 스왑인 될 때 스왑 아웃되기 전의 물리 주소와 다른 주소에 적재될 수 있음
• 여러 프로세스가 요구하는 메모리 주소 공간이 실제 메모리 크기보다 커도 스와핑을 이용해 동시 실행 가능

메모리 할당

• 최초 적합(first fit)
  • 운영체제가 메모리 내의 빈 공간을 순서대로 검색 → 적재할 수 있는 공간 발견 → 프로세스 배치
  • 검색을 최소화하여 빠른 할당 가능
• 최적 적합(best fit)
  • 운영체제가 빈 공간을 모두 검색 → 적재할 수 있는 공간 중 가장 작은 공간에 프로세스 배치
• 최악 적합(worst fit)
  • 운영체제가 빈 공간을 모두 검색 → 적재할 수 있는 공간 중 가장 큰 공간에 프로세스 배치

외부 단편화

• 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
• 프로세스가 메모리에 연속적으로 할당되면 반복되는 프로세스 실행과 종료로 인해 메모리 사이 사이에 빈 공간 발생
• 압축(compaction, 메모리 조각 모음)
  • 메모리 내에 저장된 프로세스를 재배치해 빈 공간을 하나로 모아 외부 단편화를 해결하는 방법
  • 압축을 하는 중에는 시스템이 하던 일을 중지해야 함
  • 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기
  • 어떤 프로세스를 어떻게 움직여 압축할지 명확하게 결정하기 어려움

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

• 연속 메모리 할당의 두 가지 문제
  1. 외부 단편화
  2. 물리 메모리보다 큰 프로세스 실행 불가
• 가상 메모리
  • 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
  • 페이징과 세그멘테이션 기법으로 관리

페이징이란

• 메모리의 물리 주소 공간을 프레임 단위로 자르고, 프로세스의 논리 주소 공간을 페이지 단위로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법
  • 프레임과 페이지는 동일한 크기를 갖는다.
• 페이징을 사용하면 프로세스 전체가 아닌 페이지 단위로 스왑 아웃/스왑 인 진행
  • 스왑 아웃/스왑 인 대신 페이지 아웃/페이지 인이라고도 부름
• 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요 없음 ⇒ 물리 메모리보다 더 큰 프로세스 실행 가능

페이지 테이블

• 프로세스가 메모리에 불연속적으로 배치 ⇒ 다음에 실행할 명령어를 찾기 어려움 ⇒ 프로세스가 논리 주소에는 연속적으로 배치되도록 페이지 테이블 이용
  • 논리 주소: CPU가 바라보는 주소
• 페이지 테이블의 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있음
• 페이지 테이블을 사용하면 CPU는 논리 주소를 순차적으로 실행하기만 하면 됨

내부 단편화

• 내부 단편화: 페이지의 크기가 잘린 프로세스의 크기보다 커서 생기는 메모리 낭비
• 페이징은 외부 단편화를 해결하지만 내부 단편화 발생 가능
• 페이지 크기를 적절히 조절해 내부 단편화 방지 가능
  • 페이지 크기가 작을 경우 ⇒ 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생하기 때문에 내부 단편화의 크기도 축소 가능
  • 페이지 크기가 너무 작을 경우 ⇒ 페이지 테이블의 크기가 커져 공간을 낭비

PTBR과 TLB

• 페이지 테이블 베이스 레지스터(PTBR): 프로세스의 페이지 테이블이 적재된 주소를 가리킴
  • 프로세스는 각자의 프로세스 페이지 테이블을 가짐
  • 프로세스의 페이지 테이블 정보는 PCB에 기록 ⇒ 문맥 교환 시 함께 교환됨
  • 프로세스 테이블은 메모리에 적재됨 ⇒ 메모리에 있는 페이지 테이블을 보고, 거기서 알게 된 프레임에 접근해야 하므로 총 두 번의 메모리 접근 필요 ⇒ 메모리 접근 시간이 두 배
• TLB(Translation Lookaside Buffer)
  • 일반적으로 MMU 내에 존재하는 페이지 테이블의 캐시 메모리
  • 참조 지역성에 근거해 최근에 주로 사용된 페이지 위주로 페이지 테이블의 일부 내용을 저장
  • TLB 히트: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있는 경우
    • 프레임을 알기 위해 메모리에 접근할 필요 없음 ⇒ 한 번의 메모리 접근 수행
  • TLB 미스: 페이지 번호가 TLB에 없는 경우
    • 프레임을 알기 위해 메모리에 접근해야 함 ⇒ 두 번의 메모리 접근 수행

페이징에서의 주소 변환

• 특정 주소에 접근하기 위해 필요한 두 가지 정보
  1. 어떤 페이지 혹은 프레임에 접근하고 싶은지 ⇒ 페이지 번호
     1. 하나의 페이지 혹은 프레임은 여러 주소를 포괄
  2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지 ⇒ 변위
• 페이징 시스템에서의 논리 주소 = 페이지 번호(page number) + 변위(offset)
• 논리 주소 <페이지 번호, 변위> → 페이지 테이블 → 물리 주소 <프레임 번호, 변위>

페이지 테이블 엔트리(PTE)

• 페이지 테이블의 각각의 행
• 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트 등의 정보 포함

유효 비트(valid bit)

• 해당 페이지에 현재 접근 가능한지를 나타내는 비트
  • 페이지가 메모리에 적재되어 있다면 1, 그렇지 않다면 0
• 페이지 폴트: 유효 비트가 0인 페이지에 접근할 때 발생하는 예외
• 페이지 폴트 처리 과정
  1. CPU가 기존의 작업 내용 백업
  2. 페이지 폴트 처리 루틴 실행
     1. 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
  3. 페이지 폴트 처리 후 페이지에 접근 가능

보호 비트(protection bit)

• 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
  • 읽기만 가능한 페이지는 1, 읽고 쓰기가 가능한 페이지는 0
• 세 개의 비트로 더 복잡하게 구현 가능
  • 읽기(r), 쓰기(r), 실행(x)의 조합으로 권한 조합을 나타냄

참조 비트(reference bit)

• CPU가 페이지에 접근한 적이 있는지를 나타내는 비트
  • 적재 이후 CPU가 읽거나 쓴 페이지는 1, 적재 이후 한 번도 읽거나 쓴 적 없는 페이지는 0

수정 비트(modified bit)

• 해당 페이지에 데이터를 쓴 적이 있는지 없는지를 나타내는 비트
  • 변경된 적 있는 페이지는 1, 변경된 적 없는 페이지는 0
  • 더티 비트(dirty bit)라고도 함
• 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 판단하기 위해 존재
  • CPU가 접근하지 않았거나 읽기만 한 페이지의 경우, 보조기억장치에 저장된 해당 페이지의 내용 = 메모리에 저장된 페이지의 내용
  • CPU가 쓰기 작업을 수행한 페이지의 경우, 보조기억장치에 저장된 해당 페이지의 내용 ≠ 메모리에 저장된 페이지의 내용 ⇒ 스왑 아웃될 경우 보조기억장치에 기록하는 추가 작업 필요

쓰기 시 복사

페이징을 이용하면 프로세스 간 페이지 공유가 가능하며 그 중 한 가지 방법이 쓰기 시 복사(copy on write)다.

• 쓰기 시 복사에서는
  1. fork 시스템 호출로 부모 프로세스의 자식 프로세스를 생성할 때
  2. 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리키게 한다.
     1. 따라서 부모 프로세스의 메모리 공간을 복사하지 않고, 동일한 코드 및 데이터 영역을 가리킬 수 있다.
  3. 이후 부모 또는 자식 프로세스가 하나의 프로세스에 쓰기 작업을 하면
  4. 그 순간 해당 페이지가 별도의 공간으로 복제되고
  5. 해당 페이지가 할당된 프레임 번호로 페이지 테이블을 갱신한다.

쓰기 시 복사를 통해 프로세스 생성 시간을 줄이고 메모리 공간을 절약할 수 있다.

계층적 페이징

• 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비 ⇒ 계층적 페이징(hierarchical paging) 등장
  • 모든 페이지 테이블을 메모리에 유지할 필요가 없어져 낭비되는 공간 절약 가능
• 계층적 페이징
  • 페이징 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
    • 다단계 페이지 테이블(multilevel page table) 기법
  • 보조기억장치에 몇 개의 페이지 테이블을 두고, 참조해야 할 때 메모리에 적재
• CPU와 가장 가까이 위치한 페이지 테이블(Outer 페이지 테이블)은 항상 메모리에 유지해야 함
• 계층적 페이징에서 논리 주소 = 바깥 페이지 번호 + 안쪽 페이지 번호 + 변위
  • 바깥 페이지: CPU와 근접한 곳에 있는(바깥에 위치한) 페이지 테이블
  • 안쪽 페이지: 페이지 테이블의 페이지
• 계층이 늘어날수록 페이지 폴트 발생 시 메모리 참조 횟수 증가

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

물리 메모리의 크기는 한정되어 있으므로,

1. 기존에 메모리에 적재된 불필요한 페이지는 보조기억장치로 보내고
2. 프로세스에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야 한다.

요구 페이징

• 요구 페이징(demand paging): 실행에 요구되는 페이지만 메모리에 적재하는 기법
• 요구 페이징 양상
  1. CPU가 특정 페이지에 접근하는 명령어 실행
  2. 해당 페이지가 현재 메모리에 있는 경우(유효 비트 1) CPU는 페이지가 적재된 프레임에 접근
  3. 해당 페이지가 현재 메모리에 없는 경우(유효 비트 0) 페이지 폴트 발생
     1. 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정하는 페이지 폴트 처리 루틴 실행
  4. 다시 1번 실행
• 순수 요구 페이징(pure demand paging) 기법
  • 메모리에 아무 페이지도 적재하지 않은 채 실행 ⇒ 프로세스의 첫 명령어 실행부터 페이지 폴트 발생
  • 실행에 필요한 페이지가 어느 정도 적재된 후에는 페이지 폴트 발생 빈도 감소
• 안정적인 요구 페이징을 위한 조건
  1. 페이지 교체
     1. 페이지 교체 알고리즘을 통해 보조기억장치로 내보낼 최적의 페이지 선택
  2. 프레임 할당

페이지 교체 알고리즘

• 좋은 페이지 교체 알고리즘 ⇒ 페이지 폴트가 적은 알고리즘
  • 페이지 폴트가 일어나면 보조기억장치에 접근해야 하므로 속도가 느려짐
• 페이지 참조열(page reference string)
  • 페이지 폴트 횟수를 구하는 데 사용
  • CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지 열
    • 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문에 생력
  • 예) 2 2 2 3 5 5 5 3 3 7 → 2 3 5 3 7

FIFO 페이지 교체 알고리즘

• First-In First-Out page replacement algorithm
• 적재된 순서대로 페이지를 교체하는 알고리즘
• 자주 참조되는 페이지가 메모리에 먼저 적재되었다고 해서 내쫓길 수 있는 문제 발생
• 2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
  • FIFO 페이지 교체 알고리즘의 단점 보완
  • 페이지의 참조 비트가 1인 경우 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 현재 시각을 적재 시각으로 설정

최적 페이지 교체 알고리즘

• optimal page replacement algorithm
• 앞으로의 사용 빈도가 가장 낮을 페이지를 교체하는 알고리즘
• CPU에 의해 참조되는 횟수를 고려
  • 메모리에 오래 남을 페이지 ⇒ 자주 사용될 페이지라는 가정
  • 메모리에 없어도 될 페이지 ⇒ 오래 사용되지 않을 페이지라는 가정
  • 따라서 보조기억장치로 내보낼 페이지 ⇒ 사용 빈도가 가장 낮은 페이지
• 가장 낮은 페이지 폴트율을 보장하는 알고리즘
• 앞으로 오랫동안 사용되지 않을 페이지 예측은 거의 불가능하기 때문에 실제 구현 불가
• 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위해 사용

LRU 페이지 교체 알고리즘

• Least Recently Used page replacement algorithm
• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
• 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라 가정

스래싱과 프레임 할당

• 프로세스가 사용할 수 있는 프레임 수가 적음 ⇒ 페이지 폴트 발생 빈도 증가
• 프로세스가 사용할 수 있는 프레임 수가 많음 ⇒ 페이지 폴트 발생 빈도 감소

스래싱(thrashing)

• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요해 성능이 저해되는 문제
  • 지나치게 빈번한 페이지 교체 ⇒ 낮은 CPU 이용률

• 멀티프로그래밍의 정도(degree of multiprogramming)
  • 메모리에서 동시에 실행되는 프로세스의 수
  • 필요 이상으로 증가하면 각 프로세스가 사용할 수 있는 프레임 수가 적어짐 ⇒ 페이지 폴트 발생 빈도 증가 ⇒ CPU 이용률 저하 ⇒ 성능 저하
• 스래싱이 발생하는 근본적인 문제
  • 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않음 ⇒ 빈번한 페이지 폴트 발생 ⇒ 스래싱 발생 확률 증가
  • 이를 해결하기 위해 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 이를 할당해주어야 함 ⇒ 적절한 프레임 할당 방식 필요

프레임 할당 방식

• 정적 할당 방식
  • 프로세스의 실행 과정을 고려하지 않고, 프로세스의 크기와 물리 메모리의 크기만 고려해 프레임을 할당하는 방식
  • 균등 할당(equal allocation)
    • 모든 프로세스에 균등하게 동일한 프레임을 할당하는 방식
    • 비효율적이며 합리적이지 못함
  • 비례 할당(proportional allocation)
    • 프로세스의 크기에 따라 프레임을 할당하는 방식
• 동적 할당 방식
  • 프로세스의 실행을 보고 할당할 프레임 수를 결정하는 방식
  • 작업 집합 모델(working set model) 기반 프레임 할당
    • 작업 집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
    • 프로세스가 일정 기간 참조한 페이지 집합을 기억하여 빈번한 페이지 교체 방지 ⇒ 작업 집합의 크기만큼 프레임을 할당

  • 페이지 폴트 빈도 기반 프레임 할당

    

    • 페이지 폴트율이 너무 높은 경우 ⇒ 프로세스가 너무 적은 프레임 소유
    • 페이지 폴트율이 너무 낮은 경우 ⇒ 프로세스가 너무 많은 프레임 소유
    • 페이지 폴트율의 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식