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

강의 링크

연속 메모리 할당

• 연속 메모리 할당
  • 프로세스에 연속적인 메모리 공간을 할당

스와핑

• 현재 사용되지 않는 프로세스들을 보조기억장치의 영역으로 쫓아냄
• 그렇게 생긴 빈 공간에 새 프로세스 적재
• 프로세스들이 요구하는 메모리 공간 크기 > 실제 메모리 크기인 상황에도 실행 가능
• 스왑 영역 크기 확인하기
  • free, top 명령어

메모리 할당

• 프로세스는 메모리의 빈 공간에 할당되어야 함
• 만약 빈 공간이 여러 개 있다면
  • 최초 적합 (first-fit)
    • 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치
    • 검색 최소화, 빠른 할당
  • 최적 적합 (best-fit)
    • 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 작은 공간에 할당
  • 최악 적합 (worst-fit)
    • 운영체제가 빈 공간을 모두 검색해본 뒤, 적재 가능한 가장 큰 공간에 할당

외부 단편화

• 사실 프로세스를 연속적으로 메모리에 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아님
• 외부 단편화 (external fragmentation) 문제 발생하기 때문
  • 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
• 해결 방법
  • 메모리 압축 (compaction)
    • 흩어진 빈 공간들을 하나로 모으는 방식
    • 프로세스들을 적당히 재배치시켜 흩어진 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
  • 가상 메모리 (paging)

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

• 연속 메모리 할당의 두 가지 문제점
  • 외부 단편화
  • 물리 메모리보다 큰 프로세스 실행 불가

가상 메모리

• 실행하고자 하는 프로그램을 일부만 메모리에 적재
• 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
• 페이징, 세그멘테이션

페이징

• 외부 단편화가 발생한 근본적인 문제
  • 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문
• 프로세스를 일정 크기로 자르고 이를 메모리에 불연속적으로 할당
  • 프로세스의 논리 주소 공간을 페이지(Page)라는 일정 단위로 자름
  • 메모리의 물리 주소 공간을 프레임(Frame)이라는 페이지와 동일한 단위로 자름
  • 페이지를 프레임에 할당하는 가상 메모리 관리 기법
• 페이징에서의 스와핑
  • 프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
  • 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
  • 실행에 필요한 페이지들은 메모리로 스왑 인
  • 프로세스를 실행하기 위해 모든 페이지가 적재될 필요 없음
  • 달리 말해 물리 메모리보다 큰 프로세스도 실행될 수 있음
• 명령어
  • getconf PAGESIZE

내부 단편화

• 프로세스의 크기가 페이지 크기의 배수가 되지 않을 수 있음
• e.g. 페이지 크기가 10KB, 프로세스 크기가 108KB
  • 2KB: 내부 단편화
• 하나의 페이지 크기보다 작은 크기로 발생

페이지 테이블

• 페이징의 문제
  • 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 일일이 알기 어려움
  • 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없음
  • CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워짐
• 페이지 테이블
  • (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도
  • (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 하는 방법
  • 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표
  • 프로세스마다 페이지 테이블 존재
  • 물리적으로는 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보임
  • CPU는 논리 주소를 순차적으로 실행하면 됨

PTBR

• 프로세스마다 페이지 테이블 있음
• 각 페이지 테이블은 CPU 내의 프로세스 테이블 베이스 레지스터(PTBR)가 가리킴
• 하지만 페이지 테이블이 메모리에 있으면 메모리 접근 시간이 2배가 됨
  • 페이지 테이블 참조하기 위해 한 번 (페이지 테이블 접근)
  • 페이지 참조하기 위해 한 번 (프레임 접근)

TLB

• CPU 곁에 페이지 테이블의 캐시 메모리
• 페이지 테이블의 일부를 가져와 저장
• CPU가 접근하려는 논리 주소가 TLB에 있다면 = TLB 히트
  • 메모리 접근 한 번
• CPU가 접근하려는 논리 주소가 TLB에 없다면 = TLB 미스
  • 메모리 접근 두 번

페이징에서의 주소 변환

• 특정 주소에 접근하고자 한다면 필요한 정보
  • 어떤 페이지/프레임에 접근하고 싶은지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• 페이징 시스템에서의 논리 주소
  • 페이지 번호(Page number)와 변위(Offset)
  • 페이지 테이블을 통해 프레임 번호와 변위로 변환
  • 변위의 경우 동일

• e.g. 논리주소(<페이지 번호, 변위>)가 <5, 2>인 곳에 접근하려면
  • 논리주소 공간 5번 페이지는 프레임 1번에 할당
  • 1번 프레임은 8번지부터 시작, 변위가 2이므로 10번지에 접근

페이지 테이블 엔트리

• 페이지 테이블 각각의 행 = 페이지 테이블 엔트리 (PTE)
  • 현재까지 설명한 PTE = 페이지 번호, 프레임 번호
• 유효 비트
  • 현재 해당 페이지에 접근 가능한지 여부
  • 메모리에 적재된 페이지 (1), 메모리에 적재되지 않은 페이지 (0)
  • 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트(page fault)라는 인터럽트 발생
    • 1. CPU는 기존의 작업 내역을 백업
    • 2. 페이지 폴트 처리 루틴을 실행
    • 3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
    • 4. 페이지 폴트를 처리했다면 CPU는 해당 페이지에 접근 가능
• 보호 비트
  • 페이지 보호 기능을 위해 존재하는 비트
  • 읽기 전용 페이지 (0), 읽기/쓰기 페이지 (1) 혹은 r(읽기), w(쓰기), x(실행)에 대해 각각 권한을 달리 설정할 수도 있음
• 참조 비트
  • CPU가 이 페이지에 접근한 적 있는지 여부
  • 접근한 적 있는 페이지 (1), 접근한 적 없는 페이지 (0)
• 수정 비트 (= dirty bit)
  • CPU가 이 페이지에 데이터를 쓴 적이 있는지 여부
  • 수정된 적 있는 페이지 (1), 수정된 적 없는 페이지 (0)
  • 해당 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야하는지 여부를 판단할 때 활용
    • 메모리에서 수정된 페이지는 스왑 아웃될 때 보조기억장치에도 쓰기 작업을 거쳐야 함

쓰기 시 복사와 계층적 페이징

쓰기 시 복사

• 이론적인 fork()
  • 프로세스는 기본적으로 자원을 공유하지 않음
    • 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 적재
    • 프로세스 생성 시간 지연, 메모리 낭비
• 쓰기 시 복사
  • 부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면 자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킴
    • 쓰기 작업 없다면 이 상태 유지
  • 부모 프로세스/자식 프로세스 둘 중 하나가 페이지에 쓰기 작업 수행 시 해당 페이지는 별도의 공간으로 복제
    • 프로세스 생성 시간 절약, 메모리 절약

계층적 페이징

• 프로세스 테이블의 크기는 생각보다 작지 않음
  • 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비
• 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 방법
  • 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
  • 페이지 테이블을 여러 페이지로 쪼개고 이 페이지를 가리키는 페이지 테이블 (outer 페이지 테이블)을 두는 방식
  • = 다단계 페이지 테이블
• 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없어짐
  • CPU와 가장 가까이 위치한 페이지 테이블(outer 페이지 테이블)은 항상 메모리에 유지
• 계층적 페이징을 이용하는 환경에서의 논리 주소
  • 바깥 페이지 번호 - 안쪽 페이지 번호 - 변위
    
  • 1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기
  • 2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로써 물리 주소 얻기
    • 위에서 보인 2단계 말고도 n단계 (n>=2)로 구성 가능
    • 다만 단계가 많을 경우 page fault가 났을 경우 메모리를 더 많이 참조해야 한다는 단점 존재

페이지 교체와 프레임 할당

• 물리 메모리보다 큰 프로세스를 실행할 수 있으나 그럼에도 물리 메모리의 크기는 한정적
• 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고 (=페이지 교체)
• 프로세스들에게 적절한 수의 프레임을 할당해야 (=프레임 할당)

요구 페이징

• 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재
• 요구되는 페이지만 적재
• 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당의 문제를 해결해야
  
• c.f. 순수 요구 페이징
  • 메모리에 아무런 페이지도 적재하지 않고 프로세스를 실행하는 방법
  • 처음부터 페이지 폴트가 발생, 시간이 지남에 따라 페이지 폴트 발생 빈도 적어짐

페이지 교체 알고리즘

• 요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득 차게 됨
• 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야
• 어떤 페이지를 내보낼지 결정하는 방법이 페이지 교체 알고리즘
• 좋은 페이지 교체 알고리즘이란
  • 페이지 폴트가 적은 알고리즘
  • 페이지 폴트가 발생하면 보조기억장치에 접근해야 해 성능이 저하
  • 페이지 폴트 횟수를 알기 위해 페이지 참조열(page reference string) 활용
    • CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

FIFO 페이지 교체 알고리즘

• 가장 단순한 방식
• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• 프로그램에 실행 초기에 잠깐 실행될 페이지 vs. 프로그램 실행 내내 사용될 페이지
  • 먼저 적재되었다고 내쫓아서는 안 됨
• 보완책 = 2차 기회(second-chance) 페이지 교체 알고리즘
  • 참조 비트 1: CPU가 한 번 참조한 적이 있는 페이지
    • 참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정 (한 번 더 기회를 줌)
  • 참조 비트 0: CPU가 참조한 적이 없는 페이지
    • 내쫓음

최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려
• 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
• 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
  • 페이지 참조열을 참고해 이후에 가장 사용되지 않을 페이지를 내쫓음
• 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
  • BUT 실제 구현이 어려움
  • 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주

LRU (Least-Recently-Used) 페이지 교체 알고리즘

• 최적 페이지 교체 알고리즘 = 가장 오래 사용되지 않을 페이지 교체
• LRU 페이지 교체 알고리즘 = 가장 오래 사용되지 않은 페이지 교체
  • 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 가정

기타 페이지 교체 알고리즘

• 이외에도 많은 페이지 교체 알고리즘들이 있음
  • e.g. LRU 페이지 교체 알고리즘의 파생 알고리즘

스레싱과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유
  • 나쁜 페이지 교체 알고리즘을 사용해서
  • 프로세스가 사용할 수 있는 프레임 자체가 적어서

스래싱

• 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제
  
  • 동시 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것은 아님
  • 멀티프로그래밍의 정도 = 메모리에 동시에 실행되는 프로세스의 수
• 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
• 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야

균등 할당 (equal allocation)

• 가장 단순한 할당 방식
• 모든 프로세스들에게 균등하게 프레임을 할당하는 방식
• 정적 할당 방식
  • 프로세스의 실행 과정 고려 X, 프로세스 혹은 물리 메모리 크기만 고려

비례 할당 (proportional allocation)

• 프로세스의 크기를 고려
• 프로세스 크기에 비례하여 프레임 할당
• 정적 할당 방식
• BUT 프로세스가 필요로 하는 프레임 수는 실행해봐야 알 수 있음
  • 크기가 큰 프로세스인데 실행하니 많은 프레임을 필요로 하지 않거나
  • 크기가 작은 프로세스인데 실행하니 많은 프레임을 필요로 하거나

작업 집합 모델

• 프로세스가 실행하는 과정에서 배분할 프레임 결정
• 스래싱이 발생하는 이유는 빈번한 페이지 교체 때문
  • CPU가 특정 시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당
• 프로세스가 일정 기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지
  • 작업 집합이란 실행 중인 프로세스가 일정 시간동안 참조한 페이지의 집합
• 작업 집합을 구하려면 1. 프로세스가 참조한 페이지 2. 시간 간격이 필요
• 동적 할당 방식

페이지 폴트 빈도

• 프로세스가 실행하는 과정에서 배분할 프레임 결정
• 두 개의 가정에서 생겨난 아이디어
  
  • 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있음
  • 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있음
• 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당
• 동적 할당 방식