제9장 가상 메모리 관리

개요 가상 메모리 관린 동적 주소 변환(dynamic address translation) 하나의 프로세스 전체가 한 번에 주기억장치 내에 존재하지 않고 일부만 있어도 수행하게 하는 방법 제공 실제 주소 공간의 크기에 구애 받지 않고 보다 큰 가상 주소 공간상에서 프로그래밍 가능 주기억장치보다 크기가 큰 프로세스의 수행 가능 동적 주소 변환(dynamic address translation) 수행 중인 프로세스가 참조하는 주소가상 주소(virtual address) 주기억장치상에서 이용할 수 있는 주소 실제주소(real address) 프로세스가 수행될 때 가상 주소를 실제 주소로 변환하는 대표적인 메커니즘 인위적 연속성(artificial continuity) 가상주소 공간 상의 연속된 주소들은 실기억 공간에서도 반드시 연속적일 필요는 없다는 특성

가상 주소 공간상의 주소와 실제 주소 공간상의 주소 간의 사상 개요 가상 주소 공간상의 주소와 실제 주소 공간상의 주소 간의 사상 가상 메모리

개요 블록 사상(block mapping) 페이지(page)/페이징(paging) 가상 메모리에 블록 단위로 분할 페이지(page)/페이징(paging) 같은 크기의 블록  페이지 페이지로 가상 메모리 구성  페이징 세그먼트(segment) /세그먼테이션(segmentation) 서로 다른 크기의 블록  세그먼트 세그먼트로 가상 메모리 구성  세그먼테이션 가상 주소는 v=(b, d)로 표시

블록 사상(mapping)을 통한 가상 주소 변환 개요 블록 사상(mapping)을 통한 가상 주소 변환

페이징(paging) 페이지 페이징 시스템에서의 가상 주소는 순서쌍 v=(p, d)로 표현 동적 주소 변환 일정한 크기의 블록 페이징 시스템에서의 가상 주소는 순서쌍 v=(p, d)로 표현 동적 주소 변환 가상 주소는 페이지 사상 테이블(page mapping table)통해 실제 주소를 구함 페이지 존재 비트(page residence bit) 주기억장치 내에 존재할 때 ‘1’로 표시 주기억장치 내에 존재하지 않을 때 ‘0’로 표시 순수 페이징 시스템에서의 가상주소

페이징(paging) 직접 사상(direct mapping) 아주 큰 페이지 사상 테이블은 보통 주기억장치에서 유지·관리 변환되는 가상주소와 페이지 사상테이블의 시작주소는 고속 레지스터에 보관 한 주기억장치 주기시간(cycle time) 내 수행 가능 직접 사상에 의한 페이지 주소 변환

페이징(paging) 연관 사상(associative mapping) 저장된 값을 이용하여 데이터를 접근하는 내용 주소화 메모리(CAM: Content Addressable Memory)와 찾고자하는 내용의 일부를 기억하는 데이터 레지스터가 운영됨 순수 연관 사상을 통한 주소 변환

페이징(paging) 연관/직접 사상 가장 최근에 참조된 페이지는 조만간 다시 사용되기 쉽다는 사실을 이용 연관기억장치에는 페이지 사상 테이블의 전체 항목 중 가장 최근에 참조된 일부 페이지 항목들만을 수용

페이징(paging) 연관/직접 사상을 통한 페이지 주소 변환

페이징(paging) 페이징 시스템의 공유 공유(share)가 가능한 페이지를 가능한 한 공유 순수 프로시듀어(pure procedure) 수정이 불가능한 프로시듀어 재진입가능 프로시듀어(reentrant procedure)라고도 함 순수 페이징 시스템에서의 공유

페이징(paging) 페이지 크기 페이지 크기는 얼마로 할 것인가? 페이지의 크기를 결정함에 있어 고려되어야 할 내용 페이지 크기가 작으면 작을수록 페이지 테이블의 크기가 증가하여 기억 공간이 낭비  테이블 단편화(table fragmentation) 페이지 크기가 작을수록 프로세스가 작업세트(working set)를 확보하는 데 도움 페이지가 크게 되면 참조되지 않을 많은 정보들까지 주기억장치로 옮겨지게 되어 기억공간의 낭비를 초래 프로그램 실행 중 입출력 전송의 횟수를 줄이기 위해서는 페이지 크기가 클수록 효과적

페이징(paging) 페이지 시스템에서의 내부 단편화

페이징(paging) 페이지 인출 기법 페이지 양도(page release) 요구 페이징(demand paging) 기법 실행 중인 프로세스에 의하여 명백히 참조되는 프로세스만이 보조기억장치로부터 주기억장치로 옮김 예상 페이징(anticipatory paging) 기법 운영체제가 예측하여 주기억장치에 여유가 있을 때 프로세스가 필요로 할 페이지들을 미리 적재 페이지 양도(page release) 더 이상 필요로 하지 않는 특정한 페이지를 작업세트로부터 제외 가장 효율적인 페이지 양도 방법은 컴파일러나 운영체제가 자동으로 페이지를 제거하여 작업세트 확보함

세그먼테이션(segmentation) 논리적 단위가 되는 프로그램 모듈이나 자료구조 등 직접 사상 가상 주소는 v=(s, d)로 표현 주기억장치에 옮겨지는 세그먼트는 그것이 들어갈 만큼의 충분한 주기억장치가 연속적으로 확보되어야 함 세그먼테이션 시스템에서의 가상 주소

세그먼테이션(segmentation) 순수 세그먼테이션 시스템에서의 가상 주소 변환

세그먼테이션(segmentation) 존재 비트(resident bit) r 해당 세그먼트가 주기억장치에 현재 존재하는지의 여부 세그먼트 사상 테이블 항목

세그먼테이션(segmentation) 공유 및 보호 공유

세그먼테이션(segmentation) 공유 및 보호 보호를 위한 접근(access) 제어 세그먼테이션 시스템의 또 다른 장점 중의 하나는 세심한 접근 제어가 가능 표 4-1 접근제어 유형

세그먼트/페이징 혼용 시스템에서의 가상 주소 세그먼트/페이징 혼용 기법 하나의 세그먼트를 정수 배의 페이지로 다시 분할하는 세그먼트/페이징 혼용 기법 가상 주소 v는 3차원의 요소로 구성 : v=(s, p, d) 시스템의 공유 세그먼트의 공유는 서로 다른 프로세스의 세그먼트 사상 테이블의 항목들이 동일 페이지 사상 테이블을 공유 세그먼트/페이징 혼용 시스템에서의 가상 주소

세그먼트/페이징 혼용 시스템에서의 연관/직접 사상을 통한 가상 주소 변환 세그먼트/페이징 혼용 기법 동적 주소 변환 세그먼트/페이징 혼용 시스템에서의 연관/직접 사상을 통한 가상 주소 변환

페이지 교체 알고리즘 주기억장치 공간을 확보하기 위하여, 현재 주기억장치를 차지하고 있는 페이지들 중에서 제거 할 페이지를 결정하기 위한 페이지 교체 기법 페이지 교체 기법 FIFO(First­In First­Out) 알고리즘 최적 교체(Optimal Replacement) 알고리즘 LRU(Least Recently Used) 알고리즘 2차 기회(second chance) 알고리즘 LFU(Least Frequently Used) 알고리즘

페이지 교체 알고리즘 FIFO(First­In First­Out) 알고리즘 가장 간단한 방법 가장 먼저 주기억장치에 들어와 있는 페이지를 교체시키는 방법 FIFO 알고리즘

페이지 교체 알고리즘 FIFO(First­In First­Out) 알고리즘 FIFO 모순(anomaly) 또는 Belady의 이변 어떤 페이지 호출에서는 프로세스에 할당된 페이지 프레임의 수가 증가될 때 현실적으로 페이지 부재가 더 증가하는 현상의 발생 FIFO 모순의 예

페이지 교체 알고리즘 최적 교체(Optimal Replacement) 알고리즘 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체시키는 것 최소의 페이지 부재율을 가지는 알고리즘 사전에 미리 파악하고 있어야 하기 때문에 다루기가 어렵고 비현실적 최적 교체 알고리즘

페이지 교체 알고리즘 LRU(Least Recently Used) 알고리즘 한 프로세스에서 사용되는 각 페이지마다 타임-스탬프용 카운터(counter)나 스택을 두어 현시점에서 가장 오래 전에 사용된 페이지를 제거하는 방법 LRU 알고리즘

페이지 교체 알고리즘 LRU(Least Recently Used) 알고리즘 카운터에 의한 방법 스택에 의한 방법 어떤 페이지에 대한 참조가 있을 때마다 그 시간 레지스터의 내용을 페이지 테이블 내에 있는 사용 시간 필드에 복사함 스택에 의한 방법 스택에 페이지 번호를 수록하여 페이지 호출 때마다 스택의 곡대기로 이동되며, 스택의 꼭대기에 있는 페이지가 가장 최근에 사용된 것임을 나타내고 바닥(bottom)에 있는 것이 가장 오랫동안 사용되지 않는 페이지임을 나타냄

페이지 교체 알고리즘 2차 기회(second chance) 알고리즘 LFU(Least Frequently Used) 알고리즘 하드웨어의 지원이 반드시 요구되는 LRU 알고리즘에 대한 접근 방안의 하나로서 참조 비트(reference bit)를 이용하는 방법 LFU(Least Frequently Used) 알고리즘 가장 적게 사용되거나 집중적이 아닌 페이지가 대체됨

페이지 교체 알고리즘 2차 기회 알고리즘

스래싱(thrashing) 페이지 부재가 계속적으로 발생되어 프로세스가 수행되는 시간보다 페이지 교체에 소비되는 시간이 더 많아지는 경우 스래싱

스래싱(thrashing) 구역성(locality) 국부적인 부분만 집중적으로 참조하는 특성 시간 구역성(temporal locality) 최근에 참조된 기억장소가 가까운 장래에도 계속 참조될 가능성이 높은 경향 예로는 순환(looping), 서브루틴, 스택, 카운팅(counting)과 집계(totaling)에 사용되는 변수 등 공간 구역성(spatial locality) 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향 예) 배열 수행, 순차 코드의 실행(sequential code execution), 프로그래머들이 관련된 변수들을 근처에 선언하는 경우 등

스래싱(thrashing) 구역성(locality) 메모리 참조패턴 예

스래싱(thrashing) 작업세트(working set) 페이지 부재율 프로세스에 의해 자주 참조되는 페이지들의 집합체 작업세트 모델 예 페이지 부재율 스래싱  페이지 부재가 너무 빈번하게 발생할 경우 생긴다.

스래싱(thrashing) 페이지 부재율 페이지 부재율이 상한을 넘으면; 그 프로세스에게 다른 프레임을 더 할당한다. 페이지 부재율이 하한보다 낮으면; 그 프로세스로부터 프레임을 회수한다.