등장 배경

  • 1960년대 영국 멘처스터 대학교에서 제작된 아틀라스 컴퓨터 시스템에서 처음 등장
  • 메인 메모리보다 용량이 큰 기억공간에 주소지정이 가능한 메모리 관리 기법
  • 메인 메모리에서 사용자와 논리 메모리를 물리적으로 분리, 프로그래머에게 가상 메모리를 제공

계층 구조

  • 페이징 시스템으로 가상 메모리 시스템을 구현
  • 메인 메모리를 보다 효율적으로 사용할 수 있어 더 많은 작업을 메모리에 적재 가능
  • 프로그래머에게 메인 메모리의 제한된 용량 사용과 중첩 사용 문제를 해결

동시성

  • 실제로 프로세스를 실행하는데 꼭 필요한 부분만 메인 메모리에 저장, 나머지는 2차 기억장치(디스크)에 저장
  • 가상 메모리 공간에 있는 프로세스 항목이 2차 기억장치에 분산 적재된 후, 프로세스 실행에 따라 메인 메모리로 이동한 결과 가상 메모리 관리 기법의 운영이 가능한 이유
  • 실제로 모든 프로그램이 항상 동시에 사용되지 않는다.
  • 행렬, 리스트, 테이블 등의 크기는 실제로 사용된 크기보다 정의된 크기가 항상 클 수 있다.
  • 문서 편집기에서 자주 사용되지 않는 메뉴 중 복사, 붙이기, 잘라내기, 삽입 등은 실제로 한 개의 메뉴만 적재하고 나머지는 메모리에서 내보내도 된다.

가상 메모리 장점

  • 프로그래밍 작업이 쉽다. 공간의 제약이 없으므로 중첩을 작성할 필요가 없다.
  • 공간이 부족해도 부분적재가 가능하며, 많은 작업을 실행할 수 있어 프로세서의 이용률과 처리율이 향상된다.

가상 메모리 단점

  • 메모리, 디스크 공간 사이의 이동량 증가에 따른 교체 공간의 확보
  • 어느 시기에 어느 페이지를 적재하고 다시 복귀시킬 것인가에 대한 페이징 알고리즘의 결정
  • 페이지 부재에 대한 처리 방안 요구

주소 분리

  • 사상(Mapping): 가상 주소를 실제 물리적 주소로 변환하는 과정, 변환 함수로 표시하며 속도가 느리면 시스템 성능이 떨어진다.
  • 프로그램 주소 공간(가상주소)를 V 라고 하고, 메인 메모리 공간(실제주소)를 R 이라고 할 경우 사상(F)에 의해 가상 메모리는 아래와 같이 정의된다.
    • F:V > R || 가상 주소(V) 실제 주소® 분리

동적 주소 변환(DAT, Dynamic Address Translation)

  • 인위적 연속성 성질을 가지므로 프로세스의 가상 주소 공간에 있는 연속적인 주소를 물리 주소 공간에 연속적으로 저장할 필요가 없다.
  • 사용자는 프로그램과 데이터의 적재 위치를 고려할 필요가 없다.

메모리 관리 기법

  • 여러 사용자가 메인 메모리 공유를 위해 메인 메모리보다 큰 보조기억장치에 데이터나 프로그램을 저장, 유지할 수 있는 방법 필요
  • 2단계 메모리 관리 기법
    • 1단계: 프로세스가 수행되고 참조 데이터를 저장하는 1차 기억장소인 메인 메모리
    • 2단계: 제한된 메인 메모리에 들어갈 수 없는 데이터를 저장하는 디스크와 같은 대용량의 2차 기억장치

블록 사상

  • 블록 단위로 처리
  • 사상이 바이트, 워드 단위로 이루어 질 경우 주소 사상 테이블(Address Mapping Table) 유지를 위해 정보량이 커진다.
  • 사상 정보의 양(테이블)을 줄이기 위해 주소를 블록 단위로 처리한다.

2차원 주소 체계

  • 블록 가상 시스템은 2차원적인 주소 체계를 가진다.
  • 시스템은 메모링에 각 프로세스의 블록 사상 테이블을 유지한다.
  • 시작점 레지스터(Block Table Origin Register)에는 메모리 주소 a 가 들어있다.
  • 변위 값을 더하여 실제 메모리 주소는 r = b’ d 로 계산되며, b’ 실제 메모리 주소 a + b 의 위치에 있는 블록 사상 테이블의 셀에 저장된다.

가상 주소, 테이블 항목

  • 가상 주소는 순서를 가지는 쌍 V = (p, d) 표시, 페이지 번호, 페이지 변위로 구성
  • 16비트의 가상 주소가 1킬로바이트(1024 byte) 크기의 페이지를 사용할 경우 가상 주소 1502(0000 0101 1101 1110)의 경우 최하위 비트 10개는 페이지 변위(011101110), 최상위 비트 6개 (000001)는 페이지 번호를 나타낸다.
  • 32비트의 논리 주소, 4킬로바이트 크기의 페이지를 사용하는 경우
  • 페이지 테이블 항목당 4바이트(32비트) 크기 유지
  • 페이지는 블록 단위로 디스크에서 메인 메모리로 옮겨져 메인 메모리의 한 블록(페이지 프레임)에 자리를 잡는다.
  • 메인 메모리는 가상 페이지와 같은 크기의 페이지 프레임들로 분할
  • 페이지는 사용가능한 어떤 페이지 프레임에도 들어갈 수 있다.

페이지 테이블 항목 구성(PTE, Page Table Entry)

  • P flag: 참조 페이지의 메인 메모리 저장 여부
  • P/W flag: 쓰기/읽기 액세스 권한 포함
  • PWT, PCD flag: 하드웨어 캐시에 의한 페이지(페이지 테이블) 처리
  • A flag: 페이지 프레임에 따른 페이징 단위 주소 적용
  • D(W) flag: 페이지 수정 여부
  • PAT flag: 페이지 테이블 속성 확인
  • G flag: 페이지 테이블 항목 확인
  • 나머지 bit: 시스템 프로그래머 사용 가능

가상(논리)주소에서 물리주소로 변환과정

  • 가상 주소의 페이지 번호(0x2)를 페이지 테이블에서 색인, 프레임 번호 (0x8)를 얻는다. 현재 참조하고 있는 페이지가 메인 메모리에 있는 경우 프로세스 수행이 불가능하다.
  • 프레임 번호(0x8), 페이지 변위에 접속, 메인 메모리의 주소 (물리 주소)를 구한다.
  • 페이지 프레임 번호가{1, 2, 3, … n}이라 가정하면, 실제 메모리 주소 r(= 프레임 번호 * 페이지 크기 + d) 실제 물리 메모리 주소는 페이지 프레임 번호와 페이지 크기를 곱한 결과이다.

비 타당 비트

  • 프로그램이 비 타당 비트로 표시된 페이지에 액세스 하지 않는 경우 실행에 영향을 주지 않는다.
  • 프로그램이 액세스하는 경우 페이지 부재로 운영체제에 트랩 발생

페이지 부재

  • 페이징 시스템의 페이지 부재
  • 프로세서에 의해 생성되니 가상(논리) 주소 V= (p, d)에서 페이지번호 (p)는 주소 번역(페이지 테이블 레지스터) 과정을 통해 페이지 테이블에서 해당 페이지 테이블 항목에 접속한다.
  • 메모리에 저장된 프레임의 저장 여부 확인
  • 지정된 프레임 페이지가 저장되어 있지 않는 경우 프레임 번호와 변위 결합, 물리 주소 생성
  • 페이지 부재로 해당 페이지 (프레임)이 디스크에 저장되어 있음을 의미하므로 명령 재시작.

순수 요구 페이징

  • 요구가 계속될 때까지 페이지를 메모리에 들어놓지 않는 방법
  • 메모리에 실행할 프로세스의 페이지가 없어도 프로세스가 수행을 시작할 수 있다.
  • 프로세스는 최소의 명령으로 페이지 부재를 일으킨다.
  • 페이지가 메모리로 들어온 후, 프로세스는 수행을 계속하면서 수행에 필요한 모든 페이지가 메모리에 적재될 때까지 필요할 때마다 페이지 부재를 발생시킨다.
  • 수행에 필요한 모든 페이지가 메모리에 적재되면 프로세스는 더 이상 페이지 부재를 발생시키지 않고 수행을 계속한다.
장점
  • 다중 프로그래밍의 정도를 증가 시키고, 액세스 되지 않은 페이지를 로드 하지 않아 메모리가 절약된다.
  • 프로그램을 시작할 때 적재(로딩)지연이 적다.
  • 적은 수의 페이지를 읽으므로 초기 디스크 오버헤드가 적다.
  • 보호 오류를 페이지 오류로 사용 가능하므로 페이징에 필요한 별도의 하드웨어 지원이 불필요하다.
  • 적재된 페이지들 중 하나가 수정될 때까지 페이지들은 여러 프로그램에 의해 공유되므로 공유 페이지(코드 공유) 기술은 보다 많은 자원 절약이 가능하다.
  • 프로그램을 실행할 충분한 메모리가 없는 시스템에서도 대용량 프로그램을 실행 가능하며, 프로그래머는 이전 중첩(오버레이) 기법보다 쉽게 구현 가능하다.
단점
  • 개별 프로그램들은 페이지에 처음 액세스 할 때 약간의 지연이 발생한다.
  • 프리 페이징은 마지막으로 수행한 몇 개의 페이지를 미리 불러오는 방법으로 성능을 향상 시킨다.
  • 낮은 비용, 낮은 성능의 시스템에 실행되는 프로그램은 페이지 대체를 지원하는 메모리 관치 장치가 없다.
  • 메모리 관리(페이지 교체)가 복잡하다.

페이징 성능

  • 요구 페이지된 메모리의 유효 액세스 시간
  • 메모리 액세스 시간(Ma)는 대부분 1 ~ 200ns(Nano Second)
  • 페이지 부재가 발생하지 않는 경우 유효 액세스 시간은 메모리 액세스 시간과 동일하다.
  • 페이지 부재 발생 시 보조기억장치에서 관련 페이지를 읽은 후 요구된 단어에 액세스하여 더 많은 시간이 소요된다.
  • 페이지 부재의 확률이 p라고 가정한다.(0 <= p <= 1)

페이지 부재 시간 계산

  • 유효 액세스 시간 계산을 위해 페이지 부재 시간을 계산해야한다.
  • 페이지 부재 시에 처리하는 인터럽트 처리 시간과 페이지 교체시간, 프로세스 재시작 과정이 필요하다.
  • 인터럽트 처리 및 프로세스 재시작 과정은 수백개의 명령어로 구성, 짧은 시간(약 1 ~ 1000 micro second 범위)에 처리 가능하다.
  • 페이지 교체 시간은 디스크의 헤드 이용에 따른 탐색 시간(5 milli second-ms), 지연 시간(3ms), 전송 시간(0.05ms) 등 으로 대략 8ms 으로 예상된다.
  • 소프트웨어, 하드웨어 시간을 포함한 총 페이지 부재 시간 처리는 약 8ms 이다.
  • 평균 페이지 부재 처리 시간이 8ms, 메모리 액세스 시간이 200ns 일 경우 := 유효 액세스 시간 : (1 - p) * 200 + p * 8,000,000

유효 액세스 시간 감속

  • 유효 액세스 시간은 페이지 부재율에 비례한다.
  • 1000개 중 한 개의 액세스에 페이지 부재 발생 시 유효 액세스 시간은 8.2(8199.8ns) micro second
  • 요구 페이징으로 인해 유효 액세스 시간은 40배(메모리 액세스 시간은 200ns) 감속
  • 유효 액세스 시간은 10% 미만으로 감속, 메모리 액세스 시간을 200ns 보다 적게 유치하기 위한 조건
  • 페이징으로 인한 감속을 적당한 수준에서 유지하기 위해 399990(= 1/0.00000250006250)번 중 한 번의 메모리 액세스가 페이지 부재 발생율보다 더 낮은 비율로 발생해야 한다.
  • 페이지 부재율이 높을 경우 유효 액세스 시간이 증가하며, 프로세스 수행시간이 늦어진다.
  • 대부분의 페이지가 처음 참조될 때 부재가 발생하고 이후에는 메모리에 저장되어 있어 페이지 부재율이 발생하지 않을 수 있다.

페이지 대치

  • 페이지 부재와 프레임 개수
  • 참조 문자열을 이용한 페이지 부재 횟수와 프레임 개수와의 관계
  • 참조 문자열은 메모리를 참조하는 페이지를 의미한다.

선입선출(FIFO, First In First Out)

  • 페이지가 메모리안으로 들어간 시간을 이용한다.
  • 가장 오래된 페이지부터 우선 대치한다.
  • 페이지 부재 발생 시, 즉 제거해야 할 페이지 선택 후 보조기억장치로 이동 교체 시키고 페이지 테이블의 타당/비타당 비트를 변경한다.
  • 새로운 페이지에 대한 페이지 테이블 항목 변경 후 FIFO Queue 의 마지막 위치에 삽입
문제점
  • 벨레디의 변의 변생: 할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상

최적 페이지 대치 알고리즘

  • 모든 알고리즘 중 페이지 부재율이 가장 낮다.
  • ‘앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 대치하라.’ 사상을 표현
  • 고정된 프레임 수에 대해 가능한 가장 낮은 페이지 부재율이 보장된다.

최근 최소 사용(LRU, Least Recently Used)

  • 과거의 데이터를 이용, 미래를 예측하기 위한 통계적 개념이다.
  • 메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용된 시간을 연관시킨다.
  • 페이지 대치 시, 오랫동안 사용하지 않은 페이지를 선택한다.
  • 시간적으로 거꾸로 찾는 최적 페이지 대체 알고리즘이라 할 수 있다.

계수기를 이용한 순서 결정방법

  • 각 페이지 테이블 항목과 사용 시간 레지스터를 연관, 프로세스에 논리 클록이나 계수기를 덧붙여 프레임의 순서 결정
  • 클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용 시간 레지스터에 복사되어 각 페이지의 최소 참조에 대한 시간을 가진다.
  • 페이지 탐색과 페이지 테이블의 변화 과정을 유지해야 하는 부담을 고려해야한다.
  • 부가된 참조 비트 알고리즘, 각 페이지에 8비트 정보에 일정한 간격으로 참조 비트를 기록한다.
  • 8비트 shift register 를 이용하여 순서 정보를 얻는다.
  • 8비트 shift register 는 최근 8번의 기간 동안 페이지 사용의 기록 정보를 유지한다.
  • shift register 값이 00000000 인 경우 8번의 기간 동안 단 한번도 사용되지 않음을 의미한다.
  • 11000100 는 `01110111 보다 최근 사용되었음을 의미한다.

시계(2차적 기회 대치 알고리즘)

  • 선입선출(FIFO) 대치 알고리즘을 기반으로 한다.
  • 최근 최소 사용 알고리즘과 성능은 비슷하나 과부하가 적다.
  • 각 프레임의 사용여부를 나타내느 참조(사용)비트를 추가한다.
  • 페이지가 메모리 내의 프레임에 처음 적재되었을 때 1로 설정한 후, 참조될 때마다 다시 1로 설정한다.
  • 프레임들은 원형 버퍼(큐)로 구성되고 각각 관련 포인터를 가진다.
  • 페이지 교체 시 포인터는 교체된 버퍼 다음 프레임을 가리키도록 설정한다.

최소 사용 빈도 수 (LFU, Least Frequently Used)

  • 각 페이지마다 참조 횟수에 대한 계수기가 있으며, 가장 적은 수를 가진 페이지를 대치한다.
  • 어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되나 그 후로 다시 사용되지 않을 경우 사용하기 어렵다.
  • 가장 작은 계수를 가진 페이지가 방금 들어온 것으로 아직 사용되지 않아, 앞으로 사용할 확률이 높다고 가정하여 대치 페이지 후보에서 제외시킨다.
  • 가장 많이 사용된 페이지(계수가 높은 페이지)를 대치한다.
  • LFU, MFU 는 구현 시 비용이 많이 들고 최적 페이지 대치에 비해 성능이 떨어져 일반적으로 사용되지 않는다.

페이지 버퍼링(Page Buffering)

  • FIFO 같은 성능저하를 막기 위해 교체 대상으로 선택된 페이지를 즉시 교체하지 않고 잠시 동안 메인 메모리에 유지한다.
  • 포인터 리스트를 이용, 페이지를 관리하며, 페이지 대체 알고리즘은 FIFO 이다.
  • 프로세스가 페이지를 참조하면 오버헤드 없이 페이지가 해당 프로세스의 작업에 추가 가능하여 페이지 부재가 해결된다.
  • 변경 페이지 리스트에 있는 프레임은 일괄처리되어, 입출력 연산 횟수가 감소하므로 디스크 액세스 시간을 줄여준다.

알고리즘 비교분석

  • 베르(baer, 1980)
  • 페이지 크기는 256워드, 프레임 수 6, 8, 10, 12, 14개로 변경시키면서 실행
  • 적은 수의 프레임을 사용할 경우 차이가 크게 나타난다.