14. 가상 메모리

1) 연속 메모리 할당

스와핑

프로세스를 보조기억장치의 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 당장 필요한 프로세스를 적재하는 메모리 기법

• 스왑 아웃(swap-out) : 프로세스를 보조기억장치의 일부 영역으로 쫓아내는 것
  • 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨짐
• 스왑 인(swap-in) : 스왑 아웃된 프로세스를 메모리에 적재하는 것
• 스왑 영역 (swap space): 스왑 아웃된 프로세스가 적재되는 보조기억장치 영역
  • 프로세스들이 쫓겨나는 보조기억장치의 일부 영역

메모리 할당

프로세스는 메모리 내의 빈 공간에 적재되어야 한다. 빈 공간이 여러 개 있다면 프로세스를 어디에 배치해야할 지

• 최초 적합(first fit) : 최초로 발견한 적재 가능한 빈 공간에 프로세스를 즉시 배치하는 방식
  • 검색을 최소화, 빠른 할당 가능
• 최적 적합(best fit) : 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식
• 최악 적합(worst fit) : 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식

연속 메모리 할당

프로세스를 메모리에 연속적으로 배치하는 방식

• 부작용 : 외부 단편화
  • 프로세스들이 실행되고 종료되길 반복하며 빈 공간이 생기는 메모리 낭비 현상
  • 프로세스 B, D 실행 종료로 남아 있는 공간은 50MB이지만, 실제 50MB 프로세스를 적재할 수는 없다.

연속 메모리 할당	외부 단편화

외부 단편화

프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 의미함

• 해결 방법
  1. 메모리 압축 (compaction) : 메모리 조각 모음
     • 메모리 내에 저장된 프로세스를 적당히 재배치 시켜서 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
     • 단점 : 압축하는 동안에 시스템이 하는 일을 중지해야하며, 옮기는 작업은 많은 오버헤드를 야기한다.
  2. 페이징 기법
     • 메모리와 프로세스를 일정 단위로 자르고, 잘라진 공간에 프로세스를 할당하는 방법으로 해결한다.

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

프로세스를 메모리에 연속적으로 할당하는 방식에서의 두가지 문제점

1. 외부 단편화
2. 물리 메모리보다 큰 프로세스를 실행할 수 없다.

가상 메모리(virtual memory)

• 프로세스의 일부만을 적재하여 실제 물리 메모리보다 더 큰 프로세스를 실행하는 기술
• 가상 메모리 관리 기법
  1. 페이징은 현대 운영체제에서 가장 대중적으로 사용되는 가상 메모리 관리 기법
  2. 세그멘테이션

페이징

• 물리 메모리를 프레임(frame)이라는 일정한 크기로 나누고
• 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 크기로 나눈 뒤
• 페이지를 프레임에 매핑(할당)하는 메모리 관리 방식

페이징

페이징 시스템의 핵심

• 논리 주소 공간(Logical Address Space): 프로세스가 사용하는 주소 공간으로, 페이지(page)로 나뉜다. 각 페이지는 프로그램 코드, 데이터, 스택 등을 포함할 수 있는 메모리의 연속적인 블록이다.
• 물리 메모리(Physical Memory): 실제 메모리 주소 공간으로, 프레임(frame)으로 나뉜다. 각 프레임은 페이지와 동일한 크기의 메모리 블록으로, 페이지가 실제로 저장되는 위치이다.
• 페이지 테이블(Page Table): 프로세스의 각 페이지가 물리 메모리의 어느 프레임에 매핑되어 있는지를 나타내는 테이블이다. 운영 체제는 이 테이블을 사용하여 논리 주소를 물리 주소로 변환한다.

• 페이징에서도 스와핑을 사용할 수 있다.

  • 프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌, 페이지 단위로 스왑 아웃/스왑 인(페이지 아웃/페이지 인)된다.

  • 하나의 프로세스를 실행하기위해 프로세스 전체가 메모리에 적재될 필요가 없다. 실행에 필요한 일부 페이지만 메모리에 적재하고 그렇지않은 페이지들은 보조기억장치 들에 남겨둘 수 있다.

    

페이지 테이블

프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 ‘다음에 실행할 위치’를 찾기 힘들어진다.

물리주소(실제 메모리 내의 주소)에 불연속적으로 배치되어도 논리 주소(CPU가 바라보는 주소)에는 연속적으로 배치되도록 페이지 테이블 이용한다.

• 어떤 페이지가 어떤 프레임에 매핑되었는지 확인하기 위함
• 프레임과 페이지의 매핑 정보를 담고 있는 표 형태의 데이터로, 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다.
• 프로세스마다 페이지 테이블을 가지고 있다.
  

• 물리 주소상에서는 분산되어있지만, CPU입장에서 바라본 논리 주소는 연속적으로 보인다.(페이지 테이블을 바라 보는 것)

  내부 단편화

  외부 단편화를 해결하는 페이징은 내부 단편화 문제를 야기할 수 있다.

  원인 :

  • 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것이 아니다.(모든 프로세스의 크기가 페이지의 배수가 아니기 때문)
  • 하나의 페이지 크기보다 작은 크기로 발생.
  • 페이지 크기를 너무 적게 설정하면 페이지 테이블의 크기가 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비된다.

  해결방법 : 내부 단편화를 적당히 방지하면서 너무 크지않은 페이지 테이블이 만들어 지도록 페이지의 크기를 조정한다.

페이지 테이블 베이스 레지스터(PTBR)

• 각 프로세스의 페이지 테이블 위치(주소)를 가리키는 레지스터
• MMU(Memory Management Unit)가 논리 주소를 물리 주소로 변환할 때 해당 페이지 테이블에 접근한다.

페이지 테이블이 메모리에 있을 경우, CPU에서 메모리로의 두 번 접근하기 때문에 메모리 접근 시간이 두 배 소요 된다.

⇒ TLB 사용

TLB(Translation Look-aside Buffer)

• MMU 내에(CPU 곁) 존재하는 페이지 테이블의 캐시 메모리
• TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용 저장한다.
• 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와서 저장한다.

  캐싱 원리는 참조 지역성(Principle of Locality)의 원리를 기반으로 한다.

  이를 활용하여, 최근에 접근된 데이터나 그 주변 데이터를 미리 캐시에 저장함으로써, 다음에 같은 데이터에 접근할 때 더 빠른 속도로 데이터에 접근할 수 있도록 한다.

  참조 지역성은 프로그램 실행 도중 메모리의 특정 부분이 집중적으로 사용된다는 관찰에 근거한 개념이다. 이 원리는 두 가지 형태로 나타난다:

  1. 시간 지역성(Temporal Locality): 한 번 참조된 데이터는 가까운 미래에 다시 참조될 가능성이 높다는 원리. 예를 들어, 루프 내에서 반복적으로 사용되는 변수가 이에 해당한다.
  2. 공간 지역성(Spatial Locality): 메모리 상에서 서로 인접한 위치에 있는 데이터들이 연속적으로 참조될 가능성이 높다는 원리이다. 예를 들어, 배열을 순차적으로 접근하는 경우가 이에 해당한다.

• CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 존재 여부
  • 있을 경우, TLB히트 : 페이지가 적재된 프레임을 알기 때문에 메모리 접근 불필요
  • 없을 경우, TLB 미스 : 메모리내에 페이지 테이블 접근 필요

TLB

페이징에서의 주소 변환

하나의 페이지 혹은 프레임은 여러 주소를 포함 하기 때문에, 특정 주소에 접근하려면 두 가지 정보 필요하다.

1. 어떤 페이지 혹은 프레임에 접근하고싶은지
2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

• 논리주소 = 페이지 번호 + 변위
  • ex) CPU가 32비트 주소를 내보냈다. 이 중 N 비트는 페이지 번호, 32-N비트는 변위
  • 페이지 번호 : 접근하고자 하는 페이지 번호
  • 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼마나 떨어져 있는지에 대한 정보
  • 논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환 된다.

페이지 테이블 엔트리

페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라한다.

페이지 테이블 엔트리에는 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트들의 정보가 있다.

• 유효 비트(valid bit)
  • 접근하려는 페이지가 보조기억장치에 있는지, 메모리에 있는지

    • 1 : 해당 페이지가 실제 메모리에 적재되어 있음을 의미한다. 따라서, CPU는 해당 페이지에 직접 접근할 수 있다.

    • 0 : 페이지가 메모리에 적재되어 있지 않음을 나타낸다. 이 경우, 접근하려는 페이지가 보조기억장치(예: 하드 드라이브)에 있으므로, 시스템은 다음 단계를 따라 페이지 폴트 처리 과정을 진행한다:

      페이지 폴트 처리 과정

      1. 기존 작업 내역 백업: 현재 CPU 상태를 저장하여 나중에 작업을 재개할 수 있도록 한다.
      2. 페이지 폴트 루틴 실행: 운영 체제는 페이지 폴트 핸들러 또는 루틴을 실행하여, 접근하려는 페이지를 보조기억장치에서 찾아 메모리로 적재한다.
      3. 유효 비트 1로 변경: 페이지가 메모리에 성공적으로 적재되면, 페이지 테이블 내 해당 페이지의 유효 비트를 1로 변경하여, 이제 메모리에 존재함을 표시한다.
      4. 접근하려는 페이지 접근: 이제 CPU는 페이지에 접근하여 필요한 작업을 계속 진행할 수 있다.

• 보호 비트(protection bit)
  • 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
  • 접근하려는 페이지의 'r', 'w', 'x' 권한이 페이지 단위로 적용된다.
    • r(Read) : 읽기 가능한 페이지
    • w(Write) : 쓰기 가능한 페이지
    • x(eXecute) : 실행 가능한 페이지
• 참조 비트(reference bit)
  • 접근한적이 있는 페이지 있는지 확인
    • 1 : 적재 이후 CPU가 읽거나 쓴 페이지
    • 0 : 적재 이후 한 번도 접근한 적이 없는 페이지
  • 주로 페이지 교체 알고리즘에서 사용된다.
• 수정 비트 (modify bit / dirty bit)
  • 쓰기 작업을 한 적 있는 페이지 인지
    • 1 : 수정한 적 있는 페이지
      • 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용이 서로 다른값을 가진다.
      • 변경 된 값을 보조기억장치에 기록하는 작업이 추가로 필요하다.
    • 0 : 수정한 적 없는 페이지
      • 새로 적재된 페이지로 덮어쓰기 하면된다.
  • 페이지가 스왑 아웃될 때 수정되었는지 여부를 나타내므로, 수정된 페이지만 보조기억장치에 다시 쓰기 위해 사용된다.
  • 주로 페이지 교체 알고리즘에서 사용된다.

페이징의 이점

1. 외부 단편화 문제 해결
2. 프로세스 간에 페이지를 공유할 수 있다. ⇒ 쓰기 시 복사 (copy on write)

멀티프로세스에서

• 프로세스를 fork하여 동일한 프로세스 두 개가 복제되면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 메모리에 적재된다.
• 프로세스를 통째로 메모리에 중복 저장하지 않으면서 프로세스끼리 자원을 공유하지 않는 방법도 있다.
  • 부모 프로세스의 메모리 영역이 다른 영역에 자식 프로세스로서 복제되고, 각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킨다.
  • 이는, 생성 시간을 늦추고 불필요한 메모리 낭비를 야기한다.

쓰기 시 복사

• 부모 프로세스와 동일한 자식 프로세스가 생성되면,
  • 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리킨다.
  • 굳이 부모 프로세스의 공간을 복사하지 않고 동일한 코드 및 데이터 영역을 가리킬 수 있다.
  • 프로세스 간에는 자원을 공유하지않기 때문에 쓰기 작업을 하게 되면, 그 수간 해당 페이지가 별도의 공간으로 복제된다.
    • 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리킨다.

계층적 페이지

프로세스를 이루는 모든 페이지 엔트리를 메모리에 두는 것은 메모리 낭비로, 항상 메모리에 유지않지 않을 수 있는 방법

• 페이지 테이블을 페이징하여 여러 단계 페이지를 두는 방식

  • 페이지 테이블을 여러 개의 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리키게 하는 방식

    논리주소

    • 페이징 논리주소 = 변위 + 페이지 번호
    • 계층적 페이지를 이용하는 논리 주소 = 바깥 페이지 번호 + 안쪽 페이지 번호 + 변위
      • 바깥 페이지 번호 : CPU와 근접한 곳에 위치한 페이지 테이블 엔트리
      • 안쪽 페이지 번호 : 페이지 테이블의 페이지 번호 (첫 번째 페이지 테이블 바깥에 위치한 두 번째 페이지 테이블)

    논리 주소 ⇒ 물리주소 주소변환

    1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기
    2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기

• 메모리 관리의 복잡성을 줄이고, 물리적 메모리 사용을 더 효율적으로 만든다
  • 큰 주소 공간을 관리할 때 발생할 수 있는 메모리 낭비를 줄이는 데 도움이 된다.

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차 기회 FIFO 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘의 변형

• 기본적으로 가장 오래 메모리에 머물렀던 페이지부터 페이지-아웃
• 다만 참조 비트가 1일 경우, 이를 0으로 변경 후 한번 더 기회 부여
• 참조 비트가 0일 경우 페이지-아웃

최적 페이지 교체 알고리즘

앞으로의 사용 빈도가 가장 낮은 페이지부터 교체하는 알고리즘

• 앞으로 쓸 일이 잘 없는 페이지
• 가장 낮은 페이지 폴트 빈도율을 보장하는 알고리즘
• 문제 : CPU가 어떤 페이지를 얼마나 참조할지 예측하기란 매우 어렵다.
• 이론적으로 페이지 교체 알고리즘의 성능을 평가할 때 주로 사용되는 알고리즘

LRU 페이지 교체 알고리즘

• 가장 적게 참조할 페이지는 예측하기 어려워도 계산하기가 쉽다.
• 최근에 사용되지 않은 페이지를 페이지-아웃

6주차 미션

진도: Chapter 14 ~ 15

기본 미션: p. 400의 확인 문제 1번 풀고 인증하기

선택 미션: Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

기본 미션 : p. 400의 확인 문제 1번 풀고 인증하기

선택 미션: Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2313523423' 일 때 LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

사용할 수 있는 프레임 : 3개

페이지 참조열 : 2 3 1 3 5 2 3 4 2 3

LRU페이지 교체 알고리즘 : 가장 오랫동안 사용되지 않은 페이지를 교체

페이지 참조열	2	3	1	3	5	2	3	4	2	3
프레임1	2	2	2	2	5	5	5	4	4	4
프레임2		3	3	3	3	3	3	3	3	3
프레임3			1	1	1	2	2	2	2	2
보조기억장치					2	1		5
페이지 폴트 발생					발생	발생		발생

페이지 폴트는 총 3번 발생한다.

6주차 회고