8 가상 메모리

학습목표 내용 가상 메모리의 개념과 요구 페이징의 장단점을 살펴본다. 페이지 대치 알고리즘 등 가상 메모리에 필요한 여러 알고리즘에 대해 배운다. 가상 메모리를 사용할 때 고려해야 할 사항에는 무엇이 있는지 확인한다. 내용 가상 메모리의 개념 요구 페이징 페이지 대치 알고리즘 프레임 할당 알고리즘 프로세스 적재 정책 기타 고려 사항

1. 가상 메모리의 개념 가상 메모리의 등장 배경 가상 메모리(Virtual Memory) 1960년 영국 맨체스터 대학교에서 제작된 아틀라스 컴퓨터 시스템에서 처음 등장. 메인 메모리보다 용량이 큰 기억 공간에 주소지정이 가능한 메모리 관리 기법. 메인 메모리에서 사용자와 논리 메모리를 물리적으로 분리, 프로그래머에게 가상에 메모리를 제공함. [그림 8-1] 메모리 계층 구조. - 페이징 시스템으로 가상 메모리 시스템을 구현. - 메인 메모리를 보다 효율적으로 사용할 수 있어 더 많은 작업을 메모리에 적재 가능. - 사용자(프로그래머)에게 메인 메모리의 제한된 용량 사용과 중첩 사용 문제를 해결해 줌. [그림 8-1] 메모리 계층 구조

1. 가상 메모리의 개념 동시에 실행되지 않는 프로그램의 특징을 이용. 가상 메모리 관리 기법의 운영 가능한 이유. 실제로 프로세스를 실행하는 데 꼭 필요한 부분만 메인 메모리에 저장, 나머지는 2차 기어장치(디스크)에 저장함. [그림 8-2] 가상 메모리 공간에 있는 프로세스 항목이 2차 기억장치에 분산 적재된 후 프로세스 실행에 따라 메인 메모리로 이동한 결과. [그림 8-2] 실행 중인 프로세스 항목이 2차 기억장치에서 메인 메모리로 이동 가상 메모리 관리 기법의 운영 가능한 이유. 실제적으로 모든 프로그램이 항상 동시에 사용되지 않음. 아래의 현상을 적절히 활용. - 예외적인 오류 조건을 처리하는 오류 코드 루틴의 경우, 자주 필요하지 않으며 발생하지 않을 수 있음. - 행렬(배열), 리스트, 테이블 등의 크기는 실제로 사용된 크기보다 정의된 크기가 항상 클 수 있음. - 문서 편집기(Text Editor)에서 자주 사용되지 않는 메뉴인 복사, 붙이기, 잘라내기, 삽입 등은 실제로 선택한 한 개의 메뉴만 적재, 나머지는 메모리에서 내보내도 됨.

1. 가상 메모리의 개념 장단점. 실행 중인 프로세스의 참조 주소와 메인 메모리에서 사용하는 주소가 분리되어야 함. 장점. - 프로그래밍 작업이 쉬우며, 공간의 제약이 없으므로 중첩을 작성할 필요가 없음. - 공간이 부족해도 부분 적재가 가능하여 많은 작업을 실행할 수 있어 프로세서의 이용률과 처리율 향상 . 단점. - 메모리와 디스크 공간 사이의 이동량 증가에 따른 교체 공간의 확보. - 어느 시기에 어느 페이지를 적재하고 다시 복귀시킬 것인가에 대한 페이징 알고리즘의 결정. - 페이지 부재에 대한 처리 방안 요구. 실행 중인 프로세스의 참조 주소와 메인 메모리에서 사용하는 주소가 분리되어야 함. 사상(Mapping) : 가상 주소를 실제 물리적 주소로 변환하는 과정. - 변환 함수로 표시하며 속도가 느리면 시스템 성능이 떨어짐. 프로그램 주소 공간(가상 주소)을 V, 메인 메모리 공간(실제주소)을 R이라 할 경우 사상(F)에 의해 가상 메모리는 아래와 같이 정의됨.

1. 가상 메모리의 개념 동적 주소 변환(DAT, Dynamic Address Translation) 기법. [그림 8-3] 가상 주소 V가 메인 메모리 R에 적재되어 있는 경우. [그림 8-3] 가상 기억 공간과 실제 주소 공간의 사상 동적 주소 변환(DAT, Dynamic Address Translation) 기법. 인위적 연속성 성질을 가지므로 프로세스의 가상 주소 공간에 있는 연속적인 주소를 물리 주소공간에 연속적으로 저장할 필요 없음. - 인위적 연속성 : 가상 주소 공간상의 연속적인 주소가 메인 메모리에서 연속적일 필요 없음. 사용자는 프로그램과 데이터의 적재 위치를 고려할 필요 없음. - 중첩 관련 작업 수행이 필요 없으며, 하드웨어 구조와 상관없이 알고리즘의 효율성과 프로그램 구조를 고려함. [그림 8-4] 동적 주소 변환(DAT)

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

1. 가상 메모리의 개념 블록 사상 블록 단위로 처리. 사상이 Byte, Word 단위로 이루어질 경우 주소 사상 테이블(Address Mapping Table) 유지를 위한 정보량이 커짐. 사상 정보의 양(테이블)을 줄이기 위해 주소를 블록 단위로 처리. - 블록은 가상 메모리의 분할 단위로, 블록의 크기가 일정하면 블록을 페이지라 하며 블록화 방법을 페이징 기법이라 함. - 블록의 크기가 다를 경우 세그먼트라 하며 세그먼테이션 기법이라 함. [그림 8-6] 가상 메모리와 보조기억장치(디스크)와의 사상. - 시스템이 블록의 위치만을 유지하고 추적하므로 효율적인 관리 가능. - 블록의 평균 크기가 클수록 주소사상의 정보의 양(테이블 크기)은 적어지나, 내부 단편화로 인한 2차 기억장치와 메인 메모리 주소사상 시간이 더 요구될 수 있음. [그림 8-6] 실제 메모리를 확장한 가상 메모리

1. 가상 메모리의 개념 블록 가상 시스템은 2차원적 주소체계를 가짐. [그림 8-7] 블록사상 시스템에서의 가상 주소체계 [그림 8-8] 프로세스 실행 동안 가상 주소 V=(b, d)로부터 메모리 주소 r로 변환되는 과정. - 시스템은 메모리에 각 프로세스의 블록 사상 테이블을 유지함. - 시작점 레지스터(Block Table Origin Register)에는 메모리 주소 a가 들어 있음. - 블록 사상 테이블의 항목은 블록번호(b)와 프로세스의 블록사상테이블의 기준 주소(a)를 더하여 메모리의 주소 b’을 얻음. - 변위 값을 더하여 실제 메모리 주소는 r= b’ + d로 계산되며, b’는 실제 메모리 주소 a + b의 위치에 있는 블록사상테이블의 셀에 저장됨. [그림 8-8] 블록 사상을 통한 가상 주소 변환

1. 가상 메모리의 개념 가상 주소와 테이블 항목 가상 주소는 순서를 가지는 쌍 V=(p, d) 표시, 페이지 번호와 페이지 변위로 구성. 16bit의 가상 주소가 1KB(=1024byte) 크기의 페이지를 사용할 경우. - 가상 주소 1502(0000 0101 1101 1110)의 경우 최하위 bit 10개는 페이지 변위(0111011110), 최상위 bit 6개(000001)는 페이지 번호(프레임)를 나타냄. 32bit의 논리 주소와 4KB(=212) 크기의 페이지를 사용할 경우. - 페이지 변위는 12bit(4KB=212), 페이지 프레임 번호는 20bit를 사용, 220(1,048,576)개의 페이지 테이블 항목(프레임)으로 구성됨. - 페이지 테이블은 항목 당 4byte(32bit) 크기를 유지함. 페이지는 블록 단위로 디스크에서 메인 메모리로 옮겨져 메인 메모리의 한 블록(페이지 프레임)에 자리 잡음. 메인 메모리는 가상 페이지와 같은 크기의 페이지 프레임들로 분할. 페이지는 사용 가능한 어떤 페이지 프레임에도 들어갈 수 있음.

1. 가상 메모리의 개념 [그림 8-9] 페이지 테이블 항목 구성. 제어비트와 프레임 번호로 구성됨. [그림 8-9] 페이징 시스템에서의 가상 주소와 페이지 테이블 항목 페이지 테이블 항목(PTE, Page Table Entry)의 제어비트. - P 플래그 : 참조 페이지의 메인 메모리 저장 여부. - R/W 플래그 : 쓰기/읽기 액세스 권한 포함. - U/S 플래그 : 사용자/슈퍼사용자에 대한 페이지(페이지 테이블) 액세스 권한 포함. - PWT, PCD 플래그 : 하드웨어 캐시에 의한 페이지(페이지 테이블) 처리. - A 플래그 : 페이지 프레임에 따른 페이징 단위 주소 적용. - D(M) 플래그 : 페이지 수정 여부. - PAT 플래그 :페이지 테이블 속성 색인. - G 프래그 : 페이지 테이블 항목 적용. - 나머지 bit는 시스템 프로그래머 사용 가능.

1. 가상 메모리의 개념 [그림 8-10] 가상(논리) 주소에서 물리 주소로 변환 과정. 가상 주소의 페이지 번호(0x2)를 페이지 테이블에서 색인, 프레임 번호 (0x8)을 얻음. - 현재 참조하고 있는 페이지가 메인 메모리에 있는 경우 프로세스 수행 불가능. 프레임 번호(0x8)와 페이지 변위에 접속, 메인 메모리의 주소(물리 주소)를 구함. 페이지 프레임 번호가 {1, 2, … n}이라 가정하면, 실제 메모리 주소 r(=프레임 번호ⅹ페이 지 크기 + d)로 나타냄. - 실제 물리 메모리 주소는 페이지 프레임 번호와 페이지 크기를 곱한 결과. [그림 8-10] 페이징 시스템에서의 가상 주소 변환

2. 요구 페이징 요구 페이징 기법 스왑 기법을 사용하는 페이징 시스템과 비슷함. 프로그램을 실행하기 위해 프로그램의 일부만을 메인 메모리에 적재. 순차적으로 작성되어 있는 프로그램의 일부(모듈)을 처리할 때 다른 부분은 실행되지 않는다는 사실을 이용함. 오류 처리 루틴의 실행 과정, 과도한 공간 확보, 모듈의 일부 처리 시 발생. - 오류 처리 루틴의 실행 과정 : 일부 오류 발생 시 해당 오류 처리 루틴만이 필요하고, 나머지 루틴은 디스크에 저장. - 과도한 공간 확보 : 배열 선언. 프로세스는 디스크에 저장되었다가 수행될 때, 직접 적재하지 않고 지연 교환기(Lazy Swapper)를 사용해 메인 메모리에 적재함. - 페이지 요구가 있을 때 요구 페이지를 메모리에 교체, 동시에 모든 페이지를 교체하지 않음. - 사용되지 않는 페이지를 메모리에 읽어 들이는 것을 예방, 교체시간, 기억 공간 감소 및 다중 프로그래밍 정도를 증가시킴. [그림 8-11] 연속된 디스크 공간에 교체시킨 페이지화된 메모리

2. 요구 페이징 요구 페이징의 기본 개념 타당-비타당을 나타내는 bit를 페이지 테이블의 각 항목에 추가함. [그림 8-12] 타당/비타당 비트가 추가된 페이지 테이블. - 타당 비트(v)로 설정된 경우 해당 페이지가 물리적 메모리에 있음을 의미함. - 비타당 비트(i)로 설정된 경우 페이지는 보조기억장치(디스크)에 있음을 의미함. - 저장되지 않은 페이지 사용 시 페이지 부재(Page Fault) 발생하며, 이때 액세스 방지를 위해 타당/비타당 비트를 이용하여 처리함. [그림 8-12] 타당/비타당 비트가 추가된 페이지 테이블

2. 요구 페이징 비타당 비트. 프로그램이 비타당 비트로 표시된 페이지에 액세스 하지 않는 경우 실행에 영향을 주지 않음. 프로그램이 액세스하는 경우 페이지 부재로 운영체제에 트랩 발생. - 무효 주소에 의한 오류. 페이지 부재. [그림 8-13] 페이징 시스템의 페이지 부재. - 프로세서에 의해 생성되니 가상(논리) 주소 V=(p, d)에서 페이지 번호(p)는 주소번역(페이지 테이블 레지스터)과정을 통해 페이지 테이블에서 해당 페이지 테이블 항목에 접속. - 메모리에 지정된 프레임의 저장 여부 확인. - 지정된 프레임 페이지가 저장되어 있지 않는 경우 프레임 번호와 변위 결합, 물리주소 생성. - 페이지 부재로 해당 페이지(프레임)가 디스크에 저장되어 있음을 의미하므로 명령 재시작. [그림 8-13] 페이징 시스템의 페이지 부재

2. 요구 페이징 [그림 8-14] 페이지 부재 처리 과정. ① 프로세스 제어 블록에 있는 내부 테이블 검사, 프로세스 참조가 메모리 액세스에 타당한지 부당한지 결정함. ② 프로세스 참조가 무효화될 경우 프로세스는 중단. 프로세스가 유효한 참조이나 페이지를 가져오지 않은 경우 페이지를 가져옴. ③ 비어있는 프레임 리스트 중 하나를 선택. ④ 할당된 프레임에 요구된 페이지를 읽어 들이기 위해 디스크 동작을 스케줄함. ⑤ 요구된 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 수정. ⑥ 주요 트랩에 의해 인터럽트된 명령어들을 다시 시작. [그림 8-14] 페이지 부재 처리과정

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

2. 요구 페이징 페이지 성능 요구 페이지된 메모리의 유효액세스시간. 단점. - 개별 프로그램들은 페이지에 처음 액세스할 때 약간의 지연이 발생함. - 프리 페이징은 마지막으로 수행한 몇 개의 페이지를 미리 불러오는 방법으로 성능을 향상시킴. - 낮은 비용, 낮은 성능의 시스템에 실행되는 프로그램은 페이지 대체를 지원하는 메모리 관리 장치가 없음. - 메모리 관리(페이지 교체)가 복잡함. 페이지 성능 요구 페이지된 메모리의 유효액세스시간. 메모리 액세스시간(Ma)은 대부분 10~ 200ns(Nano Second). 페이지 부재가 발생하지 않는 경우 유효액세스시간은 메모리액세스시간과 동일함. 페이지 부재 발생 시 보조기억장치에서 관련 페이지를 읽은 후 요구된 단어에 액세스하여 더 많은 시간이 소요됨. 페이지 부재의 확률이 p라고 가정함(0 ≤ p ≤ 1). - p는 0에 매우 가까운, 약간의 페이지 부재율이 있다고 가정함.

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

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

2. 요구 페이징 페이지 대치 페이지 대치의 필요성. [그림 8-15] 페이지 대치의 필요성. - 프로그램 카운터(PC)에 의해 사용자 1의 페이지 M을 적재하면 물리적 메모리에 비어있는 프레임이 없음을 발견. - 사용자 2의 페이지 B는 물리적 메모리에 적재할 수 없음. [그림 8-15] 페이지 대치의 필요성

2. 요구 페이징 페이지 대치 기법. 페이지 방식을 취하는 가상 메모리에서 페이지 부재 발생 시 메인 메모리에 있으면서 사용 되지 않는 페이지를 없애고 새로운 페이지로 변경. 아래와 같은 방식으로 액세스 됨. ① 비어 있는 프레임이 없다면 현재 사용하지 않는 프레임(희생자)을 찾음. 사용하지 않는 프레임이 있는 경우 발견한 프레임을 비우기 위해 프레임의 내용을 보조기억장치(디스크)에 저장. ② 페이지가 메모리에 더 이상 존재하지 않는다는 것을 알려주기 위해 페이지 테이블을 변화(비타당 비트로 전환)시킴으로써 프레임이 비게 됨. ③ 원하는 페이지(f)를 디스크로부터 읽어 프레임에 저장. ④ 새로운 페이지(f)를 위하여 페이지 테이블을 수정함. [그림 8-16] 페이지 대치

1. 가상 메모리의 개념 프로그램에 의해 빈 프레임은 부재된 페이지 수용을 위해 사용됨. 페이지 부재 서비스 루틴은 페이지 대치를 포함하도록 수정됨. 페이지 대치 과정. ① 디스크에서 요구한 페이지의 위치 확인. ② 빈 프레임을 찾음. - 빈 프레임이 발견되면 빈 프레임을 사용. - 빈 프레임이 발견되지 않으면 희생 프레임 선정을 위해 페이지 대치 알고리즘 사용. - 희생 페이지는 디스크에 기록, 페이지와 프레임 테이블을 수정함. ③ 요구된 페이지를 읽어 들이고 페이지와 프레임 테이블을 수정. ④ 사용자 프로세스를 시작함. 페이지 부재로 인한 페이지 대치 과정은 페이지 부재 처리 시간이 증가하는 결과를 가져와 액세스 시간이 증가하므로 시스템에 부담이 됨. - 페이지 두 개가 이동(하나는 나오고 하나는 들어감). - 수정된 비트를 활용하여 부담을 감소시킬 수 있음. 페이지 대치는 요구 페이징의 기본 요소로 논리적 공간과 실제 메모리 공간을 완벽히 분리 해주므로 프로그래머는 실제 메모리에서 매우 큰 가상 메모리(디스크)를 제공할 수 있음.

3. 페이지 대치 알고리즘 페이지 부재와 프레임 개수 참조 문자열을 이용한 페이지 부재 횟수와 프레임 개수와의 관계. 참조문자열은 메모리를 참조하는 페이지를 의미함. 프레임 수가 증가하면 페이지 부재수가 감소함. - 위의 참조 문자열에 대해 세 개 또는 그 이상의 프레임을 가진 경우, 총 3번의 페이지 부재 발생. - 한 프레임만 이용할 수 있는 경우 각 참조마다 페이지 대치가 필요하며 결과적으로 11번의 부재 발생. [그림 8-17] 페이지 부재와 프레임 개수 그래프. - 프레임 수가 증가함에 따라 페이지 부재의 수가 최소한도의 수준으로 내려감. [그림 8-17] 페이지 부재와 프레임 개수

3. 페이지 대치 알고리즘 선입선출(FIFO, First-In-First-Out) 대치 알고리즘 ※ 페이지 대치 알고리즘을 확인하기 위해 아래 참조 문자열을 프레임이 3개인 메모리에 사용함. 선입선출(FIFO, First-In-First-Out) 대치 알고리즘 각 페이지가 메모리 안으로 들어간 시간을 이용. 가장 오래된 페이지부터 우선 대치시킴. 페이지 부재 발생 시, 즉 제거해야 할 페이지 선택 후 보조기억장치로 이동 교체시키고 페이지 테이블의 타당/비타당 비트를 변경함. 새로운 페이지에 대한 페이지 테이블 항목 변경 후 FIFO 큐의 마지막 위치에 삽입. [그림 8-18] 선입선출(FIFO) 대치 알고리즘

3. 페이지 대치 알고리즘 선입선출 큐(FIFO Queue)에 의해 메모리의 모든 페이지가 관리됨. 큐의 헤드부분에 있는 페이지를 먼저 대치함. 큐에 있는 페이지가 메모리로 들어갈 때 큐의 끝 페이지가 삽입. 큐의 크기는 사용 가능한 메모리 프레임의 수에 해당됨. [그림 8-19] 선입선출(FIFO) 대치 알고리즘의 실행 - 세 개의 프레임을 사용할 수 있다 가정하고 앞의 참조 문자열을 실행, 페이지 부재는 15번 발생함. [그림 8-19] 선입선출(FIFO) 대치 알고리즘의 실행 ※ 알고리즘의 이해가 쉽고 프로그램의 작성이 쉬움.

3. 페이지 대치 알고리즘 문제점. 벨레디의 변이(Belady’s Anomaly) 발생. - 할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상. - 이로 인해 최적 페이지 대치 알고리즘을 추구하는 경향 발생. 아래의 참조 문자열을 적용하여 문제점 확인. [그림 8-20] 프레임별 실행결과 [그림 8-21] 벨레디의 변이 현상

3. 페이지 대치 알고리즘 최적(Optimal) 페이지 대치 알고리즘 모든 알고리즘 중 페이지 부재율이 가장 낮음. ‘앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 대치하라’는 사상을 표현. 고정된 프레임 수에 대해 가능한 가장 낮은 페이지 부재율이 보장됨. [그림 8-22] 최적 페이지 대치 알고리즘. - 앞의 참조 문자열을 적용한 경우, 총 9번의 페이지 부재가 발생함. [그림 8-22] 최적 페이지 대치 알고리즘 ※ 현실적인 구현이 어려우며, 비교 연구를 위해 주로 사용됨. - 참조 문자열이 언제 사용될 것인가에 대한 정확한 정보를 요구함.

3. 페이지 대치 알고리즘 최근 최소사용(LRU, Least Recently Used) 알고리즘 과거의 데이터를 이용, 미래를 예측하기 위한 통계적 개념. 메모리의 지역성을 이용한 알고리즘으로 각 페이지에 마지막으로 사용된 시간을 연관시킴. 페이지 대치 시, 오랫동안 사용하지 않은 페이지를 선택. - 시간적으로 거꾸로 찾는 최적 페이지 대치 알고리즘이라 할 수 있음. [그림 8-23] 최근 최소사용(LRU) 알고리즘. - 앞의 참조 문자열 적용 시, 12번의 페이지 부재를 일으킴. - 처음 5번의 부재 처리 과정은 최적 대치 알고리즘과 같으나, 이후 페이지 4에 대한 참조가 일어날 때 메모리 속 페이지 중 가장 늦게 사용한 페이지 2를 선택하여 대치함. - 만약 페이지 2에 부재 발생 시, {0, 3, 4} 중 가장 늦게 사용한 페이지 3으로 대치함. [그림 8-23] 최근 최소사용(LRU) 알고리즘 ※ 알고리즘의 구현을 위해 하드웨어 지원이 필요함. ※ 프레임(페이지)이 마지막에 사용된 기간을 이용, 정의되는 순서 결정을 위해 계수기 또는 스택을 사용하는 두 가지 방법으로 구현 가능함.

3. 페이지 대치 알고리즘 계수기를 이용한 순서 결정 방법. 스택을 이용한 순서 결정 방법. 각 페이지 테이블 항목과 사용시간 레지스터를 연관, 프로세서에 논리 클록이나 계수기를 덧붙여 프레임의 순서 결정. - 페이지에 대한 참조가 있을 때마다 클록은 증가함. 클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용시간 레지스터에 복사되어 각 페이지의 최소 참조에 대한 시간을 가짐. - 가장 작은 시간 값을 가진 페이지는 대치됨. 페이지 탐색과 페이지 테이블의 변화 과정을 유지해야 하는 부담을 고려해야 함. 스택을 이용한 순서 결정 방법. 순서 결정을 위해 페이지 번호를 스택(Stack)에 넣어 관리. 페이지가 참조될 때마다 페이지 번호를 스택의 꼭대기(Top)에 둠. - 꼭대기에 있는 페이지 번호는 가장 최근 사용한 페이지가 되며, 밑바닥(Bottom)에 있는 페이지 번호는 가장 늦게 사용한 페이지가 되어 페이지 부재 시 교체됨. 필드 비교, 업데이트, 계수기 등의 처리 과정은 생략되나, 스택의 중간에서 항목을 가져오므로 이중 링크의 조작이 필요하여 오버헤드를 증가시킬 수 있음. - 헤드와 꼬리 포인터를 가진 이중 연결리스트를 사용하여 해결 가능. - 탐색시간을 감소시킬 수 있음.

3. 페이지 대치 알고리즘 [그림 8-24] 최근의 페이지를 참조한 스택. - a 이전의 스택 정보는 꼭대기에 가장 최근에 사용한 페이지 2가 있으며, 밑 바닥에는 가장 오래 전에 사용한 페이지 4를 유지하고 있음. - b 이전의 스택에서는 꼭대기에 있는 페이지가 최근 사용한 페이지 7로 교체됨. [그림 8-24] 최근의 페이지를 참조한 스택

3. 페이지 대치 알고리즘 최근 최소사용 근접 알고리즘 시스템은 하드웨어의 지원 대신 참조 비트(Reference Bit)의 형태로 지원. 처음 모든 bit는 0으로 초기화한 후 사용자 프로세스가 수행될 때 참조된 각 페이지와 관련된 bit를 1로 변환, 어느 페이지가 사용되었는지 조사하여 확인 가능. 부분적인 순서 정보를 활용하여 최근 최소사용 알고리즘에 근사하게 대치 가능한 알고리즘 구현 가능. 부가된 참조비트 알고리즘. 각 페이지에 8bit(1byte) 정보에 일정한 간격으로 참조 비트를 기록. 8bit Shift Register를 이용하여 순서 정보를 얻음. - 각 페이지에 대한 참조비트(1)를 최상위 bit(8bit 위, 가장 왼쪽)로 삽입 이동하고 나머지 bit들은 한 비트씩 오른쪽으로 이동시켜 가장 낮은 자리 bit는 제거함. 8bit Shift Register는 최근 8번의 기간 동안 페이지 사용의 기록 정보를 유지함. - Shift Register의 값이 ‘00000000’인 경우 8번의 기간 동안 단 한 번도 사용되지 않음을 의미함. - ‘11000100(19610)’은 ‘01110111(11910)’보다 최근 사용되었음을 의미함.

3. 페이지 대치 알고리즘 [그림 8-25] 부가된 참조비트 예. - ‘00001011(11)’이 가장 사용빈도가 낮아 페이지 대치 대상임. [그림 8-25] 부가된 참조비트 예 8bit를 부호 없는 정수로 해석할 경우 가장 낮은 bit를 가진 페이지는 최근 최소사용(LRU) 페이지(오랫동안 미사용 페이지)이며, 대치 가능함. 참조 비트의 내용이 동일한 경우 발생 가능. - 모든 페이지 프레임이 갖는 참조 비트의 값이 유일하지 않기 때문에 발생함. 작은 정수값을 갖는 프레임이 두 개 이상 있는 경우 희생자 선정 시점에서 문제 발생. - 희생자를 선정하지 않는 경우는 문제 없음. - 가장 작은 정수값을 갖는 프레임 모두를 희생자로 선택하거나 FIFO의 원칙에 따라 하나를 희생자로 선택함.

3. 페이지 대치 알고리즘 시계(2차적 기회 대치) 알고리즘. 선입선출(FIFO) 대치 알고리즘을 기반으로 함. 최근 최소사용(LRU) 알고리즘과 성능은 비슷하나 과부하가 적음. - 각 프레임의 사용여부를 나타내는 참조(사용)비트를 추가. - 페이지가 메모리 내의 프레임에 처음 적재되었을 때 1로 설정한 후, 참조될 때마다 다시 1로 설정. - 프레임들은 원형 버퍼(큐)로 구성되고 각각 관련 포인터를 가짐. - 페이지 교체 시 포인터는 교체된 버퍼 다음 프레임을 가리키도록 설정. 운영체제가 페이지 교체 시기에 참조비트가 0인 프레임을 찾기 위해 원형 버퍼 검색. - 프레임의 참조비트가 ‘1’이면 ‘0’으로 조정하고 현재 시간으로 고침. - 수정한 페이지에 2차적 기회를 주고 다음 검사 시까지 대치시키지 않음. - 모든 사용비트가 1인 경우 각 페이지에 2차적 기회를 주며 포인터는 전체 큐를 한 바퀴 돌 수도 있음. - 처음 시작한 위치에서 중단하고 그 프레임을 교체대상으로 선택. 모든 bit가 1인 경우 2차적 알고리즘은 선입선출(FIFO) 대치와 같아짐. - 사용비트가 1인 프레임을 통과하는 과정을 제외하면 선입선출(FIFO) 대치 알고리즘과 비슷함. - 원형으로 배치된 것처럼 보여 시계 알고리즘이라고 함. [그림 8-26] 시계 페이지 대치 알고리즘

3. 페이지 대치 알고리즘 [그림 8-27] 간단한 시계 알고리즘의 예. - 메인 메모리 프레임 m개로 구성된 원형 버퍼가 버퍼 내의 페이지 1개를 새로운 페이지 420으로 교체하기 직전의 모습. [그림 8-27] 페이지 대치 이전의 버퍼와 페이지 대치 이후의 버퍼 상태 시계 알고리즘에 사용비트 추가 시 더 강력한 대치 알고리즘 작성 가능. - 사용 중인 페이지들은 메인 메모리의 각 프레임과 연관되므로 메인 메모리의 각 프레임의 상태를 나타내는 수정(타당/비타당 비트)를 이용. - 해당 프레임이 보조기억장치(디스크)에 저장되었는지 확인 가능함. - 페이지를 가져온 후 수정되지 않았으며 최근에 사용되지 않은 페이지를 찾을 수 있으므로 변경되지 않은 페이지가 우선 교체 대상이 되어 시간을 줄일 수 있음.

3. 페이지 대치 알고리즘 최소사용 빈도수(LFU, Least Frequently Used) 알고리즘. 각 페이지마다 참조 횟수에 대한 계수기가 있으며, 가장 작은 수를 가진 페이지를 대치함. - 많이 사용되는 페이지는 큰 참조 횟수 값을 가짐. 어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되나 그 후로 다시 사용되지 않을 경우 사용하기 어려움. - 큰 계수를 가진 페이지가 더 이상 필요하지 않음에도 메모리 속에 계속 남음. - 계수기를 어떤 일정한 시간 간격으로 하나씩 오른쪽으로 이동, 지수적으로 감소하는 평균 사용수를 형성하여 해결 가능함. 최대사용 빈도수(MFU, most Frequently Used) 알고리즘. 가장 작은 계수를 가진 페이지가 방금 들어온 것으로 아직 사용되지 않아, 앞으로 사용할 확률이 높다고 가정하여 대치 페이지 후보에서 제외시킴. 가장 많이 사용된 페이지(계수가 높은 페이지)를 대치함. ※ LFU, MFU는 구현 시 비용이 많이 들고 최적 페이지 대치에 비해 성능이 떨어져 일반적으로 사용되지 않음.

3. 페이지 대치 알고리즘 페이지 버퍼링(Page Buffering). FIFO 같은 성능 저하를 막기 위해 교체 대상으로 선택된 페이지를 즉시 교체하지 않고 잠시 동안 메인 메모리에 유지함. 포인터 리스트 두 개를 이용, 페이지를 관리하며, 페이지 대치 알고리즘은 FIFO임. VAX 컴퓨터의 VMS, XP, Mach에서 사용된 방식. [그림 8-28] 페이지 버퍼링 개념. - 수정 안 된 가용페이지 리스트. : 메모리에 적재된 후에 수정된 적이 없는 프레임 리스트로 교체 불필요. - 변경 페이지 리스트 : 메모리에 적재된 후 수정된 프레임의 리스트로 디스크에 재저장해야 하므로 디스크 기록을 대기함. [그림 8-28] 페이지 버퍼링 개념 변경되지 않은 페이지 교체 시, 교체된 페이지는 메모리에 남고 페이지 프레임은 가용 페이지 리스트의 끝에 추가됨. 변경된 페이지 교체 시, 페이지 프레임을 변경 페이지 리스트의 끝에 추가함.

3. 페이지 대치 알고리즘 페이지 교체 시. 페이지 읽을 때. - 페이지 테이블 내에 있는 항목만 삭제되어 가용 페이지 리스트나 변경 페이지 리스트에 놓임. - 포인터 리스트의 각 항목은 재배치되는 프레임의 번호 저장. - 가용 페이지 : 항상 사용 가능한 몇 개의 프레임들을 보유, 페이지를 읽어 들일 수 있는 페이지 프레임의 리스트. 페이지 읽을 때. - 가용 리스트의 헤드가 가리키는 페이지 프레임(가용 페이지 리스트 상의 첫 페이지)이 사용되고 그 페이지는 없어짐. - 페이지 부재 발생 시 리스트 두 개를 검색, 원하는 페이지가 아직 메모리에 있는 지 검사함. - 메모리에 없으면 가용 페이지 리스트의 첫 번째 프레임에 원하는 페이지 적재. 프로세스가 페이지를 참조하면 오버헤드 없이 페이지가 해당 프로세스의 작업에 추가 가능하여 페이지 부재가 해결됨. 변경 페이지 리스트에 있는 프레임은 일괄 처리되어, 입출력 연산 횟수가 감소하므로 디스크 액세스 시간을 줄여줌.

3. 페이지 대치 알고리즘 알고리즘의 비교 분석 배르(BAER, 1980년) 발표. [그림 8-29] 페이지 대치 알고리즘의 비교. - 분석에 사용한 페이지 크기는 256word이며, 프레임 수를 6, 8, 10, 12, 14개로 변경시키면서 실행. - 적은 수의 프레임을 사용할 경우 차이가 크게 나타남. [그림 8-29] 페이지 대치 알고리즘의 비교

4. 프레임 할당 알고리즘 단독 사용자 시스템 가상 메모리 시스템의 가장 간단한 구조. 메모리 크기가 128K인 단일 사용자 마이크로컴퓨터 시스템에서(페이지 크기는 1K), 이 중 운영체제가 35K를 차지한다면 남은 95K는 사용자 프로세스를 위해 남음. - 순수 요구 페이징 방법 적용 시, 프레임 93개 모두 사용가능 프레임 리스트에 포함됨. - 사용자가 프로세스 수행을 시작하면 페이지 부재가 발생함. - 93번까지의 페이지 부재는 사용가능 페이지 리스트에서 대기 중인 페이지를 모두 사용하게 됨. - 따라서 94번째 발생한 페이지 부재 해결을 위한 해결 방법 필요함. 사용가능 페이지가 없을 때, 페이지 부재 해결 방법. 페이지 대치 알고리즘을 사용. - 기억 장소 내에 있는 페이지 93개 중 하나를 선택하여 교체하며, 이때 페이지 대치 알고리즘을 호출. 사용되지 않는 경우 사용자 페이지로 변환시켜 사용. 사용가능 리스트(93개 중)에서 프레임 3개를 확보, 페이지 부재 발생 시 항상 사용가능 프레임이 존재하도록 함. ※ 다중 프로그래밍 환경에서 기억 장소 내에 동시에 프로그램이 두 개 이상 존재하므로, 여러 개의 프로세스에 프레임 할당 방법에 대한 문제 발생.

4. 프레임 할당 알고리즘 최소 프레임 수 할당해야 할 최소 프레임 수 존재. 기억 장소 할당은 제한이 있어 총 유효 프레임 수보다 많이 할당할 수 없으나, 할당 가능한 최소 프레임 수는 존재함. - 각 프로세스에 할당되는 프레임 수가 줄어들면서 페이지 부재율은 올라가며, 수행 속도는 저하됨. - 성능 저하를 막기 위해 할당해야 할 최소 프레임 수가 존재함. 최소 프레임 수는 명령어 구조에 의해 정의됨. - 수행 중인 명령이 끝나기 전에 페이지 부재 현상 발생 시 그 명령을 다시 시작해야 함. - 하나의 명령어 실행을 위해 명령어가 참조하는 모든 페이지를 수용할 수 있는 충분한 프레임이 필요함 . ※ 한 프로세스당 최소 프레임 수는 컴퓨터 구조에 의해 정의되나, 최대 수는 유효 실제 기억 장소의 양으로 정의됨.

4. 프레임 할당 알고리즘 균일과 비례할당 알고리즘 균일할당. 비례할당. 프로세스 n개에 프레임 m개를 할당할 때 각 프로세스에 똑같이 프레임 m/n개씩 나눔. 각 프로세스가 갖는 메모리의 요구량이 서로 다르므로 페이지 프레임 낭비 및 페이지 부재가 발생할 수 있음. 비례할당. 균일할당 방법의 문제점을 해결하기 위해 사용됨. 사용 가능한 메모리를 각 프로세스가 필요로 하는 메모리 양 또는 프로세스의 크기에 비례하여 할당. 운영체제가 활동 중인 프로세스에 대한 정보를 알고 있어야 하며, 소프트웨어 오버헤드를 가져옴. 프로세스 Pi의 가상 메모리 크기를 si라고 하면 전체 프로세스가 갖는 가상 메모리 공간의 크기 S는 아래와같이 정의됨. 사용가능 프레임의 총수를 m이라 하면 프로세스 Pi에 프레임 ai개를 할당하는데, 이때 ai는 대략 아래와 같음. - 이때 ai는 명령어 집합이 필요로 하는 최소 프레임 수보다는 크고 총합이 m을 넘지 않는 정수이어야 함. ※ 균일과 비례할당 기법 모두 다중 프로그램 정도에 따라 할당되는 양이 변하며, 우선순위를 고려하지 않음.

4. 프레임 할당 알고리즘 부하 제어(Load Control) 메인 메모리에서 실행할 프로세스의 개수 결정. 메인 메모리에 적재되어 실행되는 프로세스의 개수를 ‘다중 프로그래밍 수준’이라 함. 메모리 관리를 위해 매우 중요함. - 너무 적은 수의 프로세스가 메인 메모리에서 실행된다면 프로세스들의 보류 상태가 자주 발생, 빈번한 교체가 발생됨. - 많은 프로세스가 메인 메모리에 적재되면 각 프로세스의 적재집합을 구성하는 평균 페이지 수가 적어 페이지 부재가 자주 발생, 스레싱 현상을 일으킴. ※ 현대 운영체제에서는 고정(균일) 할당과 가변(비례)할당 정책을 이용.

5. 프로세스 적재 정책 스레싱(Thrashing) 페이지 교환이 계속 일어나는 현상. 스레싱 발생 원인. 어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 크면 ‘ 스레싱을 하고 있다’고 말함. 스레싱 발생 원인. 운영체제는 항상 프로세서의 효율성(이용률)을 감시하여 운영. 이용률이 떨어지면 이를 높이기 위해 새로운 프로세스를 도입, 다중 프로그래밍의 정도를 높임. - 새로운 프로세스가 수행 중인 프로세스의 페이지를 빼앗아서 수행을 시작할 경우 더 많은 페이지 부재 발생. - 프로세서가 요구하는 최소한의 수보다 페이지 프레임 수가 적으면 적을수록 페이지 부재율이 증가함. - 페이지 부재가 많이 일어날수록 프로세스가 페이징 처리장치를 기다리는 시간이 길어지므로 프로세스의 효율성은 떨어짐. ※ 페이지 부재로 프로세서의 이용률 감소 시 스레싱이 발생하여 시스템의 처리율은 낮아지 고 페이지 부재는 늘어나 유효 메모리 액세스 시간이 증가, 페이지 교체시간이 낭비됨.

5. 프로세스 적재 정책 [그림 8-30] 스레싱. 스레싱 예방. 프로세서의 이용률과 다중 프로그래밍의 정도에 따라 다름. - 다중 프로그래밍의 정도가 높아지면 프로세서의 이용률도 최대값이 될 때까지 증가. - 다중 프로그래밍의 정도가 더욱 커지면 스레싱이 발생, 프로세서의 이용률은 급격히 떨어짐. 프로세서의 이용률을 높이고 스레싱을 중단하려면 다중 프로그래밍의 정도를 낮춰야 함. [그림 8-30] 스레싱 스레싱 예방. 지역 교환 알고리즘이나 우선순위 교환 알고리즘을 사용하여 제한할 수 있음. - 지역 교환 알고리즘 사용 시 프로세스 하나에 스레싱이 발생하더라도 다른 프로세서에서 프레임을 가지고 올 수 없어 다른 프로세스는 스레싱 현상에 빠지지 않음. - 여러 프로세스에서 스레싱이 발생할 경우 프로세스들은 대부분의 시간을 페이징 처리장치를 기다리는 큐에서 보냄. - 스레싱은 발생하지 않으나 유효 액세스시간은 증가함.

5. 프로세스 적재 정책 지역성(국부성) 실행 중인 프로세스에 의해 나타나는 특성. 프로세스들은 실행기간 동안 메모리 내의 정보를 균일하게 액세스하는 것이 아닌 페이지 중 일부를 선호하여 지역적인 부분만을 집중적으로 참조하는 현상. 프로그램들의 순환(Looping)이나 부 프로그램, 스택, 변수들의 계산과 합계, 배열 순례, 순차적 코드의 실행 등으로 발생. 프로그래머들이 관련 있는 변수들을 서로 근처에 배치시키기 때문에 발생함. [그림 8-31] 여러 페이지에 대한 프로세스의 메모리 참조 유형. [그림 8-31] 메모리 참조 패턴의 지역성(출처: IBM Systems Journal. Ⓒ 1971)

5. 프로세스 적재 정책 지역성의 종류. 시간 지역성. 공간 지역성. - 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음을 의미함. - 순환구조의 루틴, 부프로그램, 스택, 계산이나 합계의 변수 등. 공간 지역성. - 프로세스가 어떤 기억장소를 한 번 참조하면, 이후에 참조한 기억장치 근처에 있는 기억장소를 참조할 가능성이 높음을 의미함. - 배열 순례(검색 작업), 순차적 코드의 실행, 근처의 관련 변수 선언 등. 스레싱 현상 방지를 위해 각 프로세스가 필요로 하는 프레임을 제공할 수 있어야 함. 지역성을 이용하여 현재의 지역 크기보다 적은 페이지 프레임 할당 시 페이지 부재 발생의 원인이 될 수 있음.

5. 프로세스 적재 정책 작업설정 모델(Working Set Model) 프로그램의 수행과정을 지역성 개념으로 설명하기 위해 데닝이 개발. 프로세스가 많이 참조하는 페이지 집합을 메모리 공간에 계속 상주시켜 빈번한 페이지 대치 현상을 줄이는 방법. 프로세스의 작업모델 구성을 위해 작업설정의 크기를 알아야 하며, 작업설정의 크기는 작업설정 창을 이용하여 구함. - 작업설정 창 정의를 위해 매개변수 ∆를 사용, ‘현재 시간(t)에서 최근의 일정 시간 단위(∆)’를 정하여 결정. - 작업설정 창의 크기는 매개변수인 ∆에 따라 달라짐. - 가장 최근의 ∆ 페이지 참조를 조사, 가상 시간 t로부터 프로세스가 참조한 페이지 집합을 나타냄. - 어떤 페이지가 실제로 사용되고 있으면 페이지는 작업설정에 포함, 마지막으로 참조된 후 ∆ 시간 동안 참조되지 않으면 더 이상 사용하지 않는 것으로 간주되어 작업설정에서 빠짐. - 따라서 가장 최근의 페이지 참조에 있는 페이지 집합을 작업설정이라 하며, 이때 작업설정은 프로그램의 지역 근사치임. 최근에 참조된 페이지들을 메인 메모리에 유지시켜 프로세스가 빠르게 실행될 수 있음. 새로운 프로세스들은 메인 메모리에 그들의 작업설정들이 적재할 수 있는 공간이 있을 때만 시작될 수 있음.

5. 프로세스 적재 정책 [그림 8-32] 프로세스 작업설정 정의. 데닝은 시간 t에서의 작업설정 WS(t, w)를 시간 (t-w)부터 t까지의 프로세스 시간 간격에 참조한 페이지들의 집합으로 정의. - t : 현재 프로세스 시간(프로세서를 점유하고 있는 시간). - w : 프로세스 창의 크기로 프로세스들의 작업설정을 계산할 때 과거 어느 시간까지 포함할 지를 나타 냄. [그림 8-32] 프로세스 작업설정 정의 [그림 8-33] 창 크기와 작업설정 - w가 증가함에 따라 작업설정의 크기가 변함. - 창의 크기(설정시간 간격) w가 커짐에 따라 메인 메모리에 유지하는 작업설정이 커지나, w가 너무 커지면 메인 메모리의 용량을 초과하므로 작업설정도 증가하지 않음. [그림 8-33] 창 크기와 작업설정

5. 프로세스 적재 정책 [그림 8-34] 작업설정 모델 예. 그림과 같이 메모리 참조 순서가 주어졌을 때(∆=10이라 가정), t1 시간의 작업설정은 {1,2,5,6,7}이 되며, t2 시간에는 {3,4}임. 작업설정의 정확성은 ∆ 의 선택에 따라 좌우됨. - ∆ 값이 너무 작으면 전체 작업설정을 충족시키지 못함. - ∆ 값이 너무 크면 여러 전체 프로그램이 됨. 매드닉(Madnick)과 도노반(Donovan)은 적절한 값으로 10,000을 제안함. [그림 8-34] 작업설정 모델(WS는 작업설정 집합)

5. 프로세스 적재 정책 작업설정의 가장 중요한 성질은 작업설정의 크기. 시스템 내의 각 프로세스에 대한 작업설정의 크기 WSSi를 계산하면 전체 요구 프레임 D는 아래와 같음. - 각 프로세스는 각 작업설정 내에 있는 페이지를 실제로 사용하고 있음. - 프로세스 i는 WSSi 프레임을 필요로 함. - 유효 프레임(m) 수보다 많이 요구하게 되면(D>m) 스레싱 발생. - 프로세스가 수행되는 동안, 작업설정은 계속 변화함. [그림 8-35] ∆ 값이 고정된 경우, 시간이 경과함에 따라 변화되는 작업설정 크기. - 대부분의 프로세스에서 작업설정의 크기가 비교적 변화가 없는 안정기와 급격하게 변화하는 과도기가 반복되는 현상을 보임. - 프로세스가 처음 시작(실행)되면 새로운 페이지를 참조하므로 작업설정의 크기가 급격하게 커짐. - 지역성의 원리에 의거하여 프로세스는 안정기에 접어들게 되며, 과도기는 프로세스가 다른 지역으로 이동(프로세스의 전환)함을 보여줌. [그림 8-35] 시간 경과에 따른 작업설정 크기 변화

5. 프로세스 적재 정책 작업설정 모델 사용법. 작업설정 모델에서 해결해야 할 문제점. 운영체제는 각 프로세스의 작업설정을 감시, 각 프로세스에 작업설정의 크기에 맞는 충분 한 프레임을 할당. 여분의 페이지 프레임이 있을 때는 준비상태에 있는 다른 프로세스를 불러들인 후 프레임 을 할당하여 다중 프로그래밍의 정도를 증가시킴. 모든 프로세스가 갖는 작업설정 크기의 합이 전체 유효 프레임의 수보다 커지게 되면 잠시 중지시킬 프로세스를 선정하여 페이지를 회수. ※ 가능한 다중 프로그래밍의 정도를 높이면서 스레싱을 방지하는 효과를 제공, 프로세서의 효율성을 최적화시킴. 작업설정 모델에서 해결해야 할 문제점. 우선 작업설정이 갖는 과거의 참조가 미래의 참조를 항상 보장하지는 않음. 작업설정의 크기와 구성 페이지들은 시간 경과에 따라 변함. 각 프로세스에 대한 작업설정을 모두 측정한다는 것은 현실적으로 불가능함. 작업설정은 프로세스가 실행됨에 따라 삭제, 추가되기도 하므로 변화가 심함. 각 프로세스가 참조한 페이지 시간과 시간 순서로 된 페이지 큐를 유지해야 하므로 작업설 정에 의한 메모리 관리는 복잡함. 작업설정 창의 크기를 나타내는 매개 변수인 ∆ 의 최적값이 알려져 있지 않으며, 처리되는 프로세스의 성격에 따라 ∆ 의 최적값은 매우 다양함. ※ 정확한 참조 대신 프로세스의 페이지 부재율에 관심을 갖고 프로세스 상주 집합의 크기를 늘리는 만큼 페이지 부재율은 낮아지는 효과를 활용한 결과로 많은 운영체제에서 사용됨.

5. 프로세스 적재 정책 [그림 8-36] 작업설정 크기에 따른 페이지 프레임 수와 페이지 부재율과의 관계. 작업설정 크기가 너무 작고 페이지 프레임 수가 적으면 페이지 부재율이 높아 프로세스의 실제 작업 페이지들이 메모리에 있지 않고 스레싱 현상을 일으킬 수 있음. 작업설정 크기가 너무 크고 페이지 프레임 수가 너무 많으면 프로세스의 실제 작업 페이지 들 뿐만 아니라 다른 페이지까지 메모리를 차지하여 메모리 낭비가 발생하며 다중 프로그 래밍의 정도를 감소시킬 수 있음. [그림 8-36] 작업설정 크기에 따른 페이지 프레임 수와 부재율과의 관계

5. 프로세스 적재 정책 페이지 부재 빈도(PFF, Page Fault Frequency) 스레싱 예방을 위한 직접적인 액세스 방법. 페이지 환경에서 프로세스의 실행을 측정하는 기준이 됨. 페이지 부재가 발생할 때 조절하여 작업설정 모델보다 오버헤드가 적음. - 작업설정 모델은 페이지가 메모리에 액세스할 때 조절. 스레싱은 페이지 부재에서 발생하므로 페이지 부재비율 조절이 필요함. - 페이지 부재 비율이 높음 = 프로세스가 더 많은 프레임을 필요로 함. - 페이지 부재 비율이 낮음 = 프로세스가 너무 많은 프레임을 갖고 있음. [그림 8-37] 페이지 부재 빈도. - 하나의 프로세스가 갖는 페이지 프레임 수에 따라 페이지 부재 비율이 변화화는 과정을 보여주는 그래프. [그림 8-37] 페이지 부재 빈도 ※ 페이지 부재 빈도 알고리즘은 페이지 참조가 새로운 지역으로 이동하는 과도기에는 제대로 작동하지 않음(페이지가 마지막으로 참조된 후 임의의 시간 단위(∆)가 경과되기 전까지 그대로 임).

6. 기타 고려 사항 대치 범위 여러 프로세스가 제한된 수의 프레임 사용을 위해 할당 기준이 필요함. 전역대치. 지역대치. - 페이지 대치 범위를 모든 프로세스에 적용(리눅스의 대치전략). - 프로세스가 교체할 프레임을 다른 프로세스로부터 획득. - 성능분석이 쉬움. 지역대치. - 프로세스를 개별적으로 제한(윈도우 XP의 대치전략). - 각 프로세스에 할당된 프레임들 중에서만 교체할 희생자를 선택가능. - 구현이 쉽고 부담이 적음. ※ 두 가지 모두 사용 가능한 빈 프레임이 없을 때 페이지 부재를 해결하기 위해 사용됨.

6. 기타 고려 사항 [그림 8-38] 전역대치와 지역대치의 차이점. - 새로운 프로세스 A6는 전역대치인 경우 페이지 B3과 교체되며, 지역대치인 경우 페이지 A5와 교체됨 . [그림 8-38] 지역대치와 전역대치

6. 기타 고려 사항 전역대치. 특정 페이지를 점유하고 있는 프로세스에 관계없이 메인 메모리에 있는 모든 페이지는 대 치 대상이 됨. - 프로세스가 교환할 프레임이 현재 다른 프로세스에게 할당되어 있어도 개별 프로세스의 동작(연산)과 상관없이 전체 프레임 중에서 하나를 선택해 프레임을 대치 가능. - 다른 프로세스는 교환을 위해 그 프레임을 선택하지 않는다는 가정하에 가능함. 프로세스에 할당하는 프레임의 수는 증가하며 똑같은 프로그램도 외부적 환경에 따라서 전혀 다르게 수행될 수 있음. 문제점. - 한 프로세스의 페이지 부재 처리를 위해 다른 프로세스의 페이지가 제거될 수 있어 각 프로세스의 페이지 부재비율을 조절할 수 없음. - 다른 프로세스의 영향을 받기 때문에 프로세스의 실행이 늦어지거나 빨라질 수 있음. ※ 개별 프로세스의 동작보다는 시스템 전반에 중점을 두므로 대형 시스템에 이용됨. 지역대치. 부재를 일으킨 프로세스의 상주 페이지에서 대치할 페이지를 선택. - 각 프로세스에 할당된 프레임 중에서만 교체할 페이지 프레임을 선택할 수 있음. - 각 프로세스에 할당된 프레임의 수는 변하지 않으며, 프로세스의 상대적인 중요도에 따라 메모리 할당을 조정, 성능을 향상시킴. ※ 각 프로세스에 대한 메모리 내의 페이지 집합은 각 프로세스의 페이지 기법에만 영향을 받고 지역대치의 할당 과정은 특정 프로세스로 지역화 됨.

6. 기타 고려 사항 프리 페이징(Prepaging) 처음에 발생하는 많은 페이지 부재를 방지하기 위한 기법. 예상되는 모든 페이지를 사전에 한꺼번에 메모리 내로 가져옴. 프리 페이징에 할당된 메인 메모리 크기와 한 번에 미리 가져올 수 있는 페이지 수 그리고 어떤 페이지를 미리 가져올 지 결정할 수 있는 경험적(공간적, 시간적 지역성에 따라 예상 하는) 알고리즘이 중요함. 입출력 인터럽트를 위해 연속된 페이지를 한 번에 메모리로 가져와 입출력을 여러 번 수행 하는 요구 페이징보다 좋은 성능을 보여줌. 문제점. - 프리 페이징 비용이 그에 상당하는 페이지 부재를 해결하는 데 드는 비용보다 적은지 확인이 필요함. - 페이징에 의해 메모리로 돌아온 페이지 중에서 상당 수는 사용되지 않을 수 있음. S개의 페이지가 프리 페이징 되었고 실제로는 확률 a(0 ≤ a ≤ 1)만큼 사용된다 가정. - 불필요한 (1-a)s개의 페이지를 프리 페이징하는 데 필요한 비용이 as개의 페이지 부재를 해결하는 데 필요한 비용보다 많은지 혹은 적은지에 대한 비교가 필요함. - a가 0에 가까우면 프리 페이징은 좋지 않음. - a가 1에 가까우면 프리 페이징의 효과는 좋음.

6. 기타 고려 사항 페이지 크기 최적 페이지 크기에 관해 결정. 일반적인 페이지 크기는 2의 거듭제곱, 256(=28)에서 4,096(=212)byte나 word. 페이지 크기 결정 시 페이지 테이블의 크기를 고려해야 함. - 가상 메모리 공간이 주어졌을 때, 페이지 크기를 감소시키면 페이지의 수가 증가, 페이지 테이블의 크기도 증가함. - 활동 중인 각 프로세스는 페이지 테이블의 사본을 가져야 하므로 페이지 크기가 큰 것이 좋음. 메모리는 크기가 작은 페이지가 이용하기 좋음. - 프로세스가 필요한 만큼 연속적으로 할당되면 프로세스는 정확히 페이지 경계에서 끝나지 않음. - 마지막 페이지의 어떤 부분은 할당되나 사용되지 않는 내부 단편화가 발생. - 프로세스의 크기, 페이지 크기와 관계없는 경우 평균적으로 각 프로세스의 마지막 페이지의 반은 낭비됨. 내부 단편화를 최소화하기 위해 크기가 작은 페이지가 필요하며, 한 페이지를 읽거나 기록하는 데 요구되는 시간도 중요함. - 입출력 시간은 회전지연과 전송 시간으로 구성. - 전송 시간은 전송되는 양에 비례하여, 작은 페이지 크기가 유리함을 의미함. - 회전지연 시간은 전송되는 양에 비례하지 않음.

6. 기타 고려 사항 [표 8-1] 페이지 크기 예. [표 8-1] 페이지 크기 예 프로세서 속도, 메모리 용량 증가 및 디스크 속도의 증가로 인해 오늘날 페이지 크기는 커짐. 페이지 크기 결정의 어려움. - 내부 단편화, 지역성 – 크기가 작은 페이지가 유리함. - 테이블 크기, 입출력 시간 – 크기가 큰 페이지가 유리함.

6. 기타 고려 사항 페이지 테이블 구조 일반적으로 각 프로세스는 하나의 페이지 테이블을 가짐. 페이지 테이블을 이용하여 가상(논리) 주소를 프레임 번호와 변위로 구성된 메모리 주소로 변환. 페이지 테이블의 크기가 매우 크므로 관리가 중요하며, 메인 메모리에서 유지하기 불가능 하여 가상 메모리에 페이지 테이블을 저장. ※ 페이지 테이블 역시 페이징의 대상이 됨. 64bit의 가상주소 공간과 4KB 크기의 페이지 그리고 512MB의 메모리 시스템에서 단일 수준 페이지 테이블 유지에 필요한 공간의 크기. - 가상 페이지당 하나의 항목 : 264-12 = 252 페이지 테이블 항목. - 페이지 테이블 항목 크기 : 약 4(22)byte. * 페이지 테이블 항목 : 액세스 제어 비트(약 1byte) + 물리적 페이지 번호(17bit). * 512MB = 229이므로, 229/212(페이지 크기) = 217 물리 페이지의 유지. - 전체 페이지 테이블 크기 : 252(페이지 테이블 항목 수)ⅹ 22(페이지 테이블 항목 크기) = 254(16,777,216GB = 16PB). 역 페이지 테이블의 개념. - 프로세스들이 물리적 페이지를 공유할 수 있도록 하나의 글로벌 페이지 테이블이 필요함.

6. 기타 고려 사항 [그림 8-39] 전통적인 페이지 테이블과 역 페이지 테이블의 구조. - 전통적인 페이지 테이블 : 각 페이지에 대한 항목을 유지, 크기는 가상 주소 공간의 크기에 비례하며 가상 페이지에 의해 색인 과정을 거침. - 역 페이지 테이블 : 해시에 의한 색인이 이루어짐. [그림 8-39] 전통적인 페이지 테이블과 역 페이지 테이블의 구조

6. 기타 고려 사항 역 페이지 테이블 구조. IBM의 AS/400, IBM RT-PC, PowerPC, HP 워크스테이션에 사용됨. 각 프레임에 대한 페이지 테이블 항목을 메인 메모리에 저장. - 페이지 테이블 항목의 수는 논리적(가상) 주소 공간이 아닌 물리 메모리의 크기에 비례함. - 페이지 테이블 항목은 프레임에 배치된 논리적 페이지에 대한 정보를 유지. - 물리적 메모리의 한 프레임에 대한 정보를 저장하지만, 논리적 페이지 번호가 아닌 페이지 프레임 번호로 색인. * 일반적인 페이지 테이블 참조와 비교 시 역(반대)임. - 2차 저장소(디스크)에 있는 페이지와 관련된 어떤 정보도 유지하지 않아 운영체제가 관리해야 함. 역 페이지 테이블의 형태. - 가장 단순한 형태는 선형 배열에 물리 페이지당 하나의 항목으로 이루어 짐(메모리 프레임마다 한 항목씩 할당) - 테이블은 공유되며, 각 항목은 프레임에 올라와 있는 페이지 주소, 페이지를 소유하고 있는 프로세스 의 ID를 표시. * 하나의 페이지 테이블과 테이블 내 각 항목은 메모리 한 프레임을 가리킴. - 물리 페이지는 가상 주소에 사상됨. * 각 항목의 내용은 물리 페이지 번호 대신 가상 페이지 번호가 됨. * 가상 페이지 번호에 따른 테이블 색인으로 물리적 페이지 번호는 저장되지 않음. - 가상 주소 변환을 위해 가상 페이지 번호와 현재의 프로세스 식별자를 각 항목(배열)과 순차적으로 비교함. * 가상 페이지 번호와 일치되는 항목을 찾으면 그 항목의 인덱스가 물리적 주소(프레임 번호)가 되며, 일치하는 경우가 없으면, 페이지 오류 발생.

6. 기타 고려 사항 [그림 8-40] 선형 역 페이지 테이블을 이용한 변환 절차. - 역 페이지 테이블에서 페이징 시스템의 가상 주소는 <프로세스 식별자(0), 가상 페이지 번호(0x1), 변위(0x123)>로 구성. [그림 8-40] 선형 역 페이지 테이블을 이용한 변환 절차 역 페이지 테이블에 대한 탐색이 비효율적임. - 가상 페이지 주소를 찾기 위해 페이지 테이블 전체를 탐색하거나 도는 페이지 크기의 메모리를 액세스해야 함. - 탐색시간 감소를 위해 해싱(해시 테이블)이 필요함.

6. 기타 고려 사항 해시 테이블 [그림 8-41] 해시 역 페이지 테이블 구조의 주소 변환. - 역 페이지 테이블을 지시하는 포인터를 포함하며, 역 페이지 테이블은 페이지 테이블 항목을 포함. - 다른 주소가 동일한 해시 테이블 항목에 사상(충돌)될 수 있으므로 체인 연결 기법을 사용. * 충돌 : 프로세스의 가상 페이지 수가 페이지 프레임 수보다 커서 여러 입력 값(가상 주소)이 동일한 해시값을 생성. * 충돌 시, 역 페이지 테이블은 해시 테이블의 동일한 셀에 들어가는 항목들이 다른 값으로 덮어쓰지 않도록 셀 항목의 위치를 가리키는 포인터(연결 리스트)를 추가함. [그림 8-41] 해시 역 페이지 테이블 구조의 주소 변환. [그림 8-41] 해시 역 페이지 테이블 구조의 주소 변환 ※ 가상 메모리 하나를 참조하려면 두 번의 메인 메모리 액세스가 필요함. ※ 액세스 시 해시 테이블 진입을 먼저 읽고 페이지 테이블을 읽으며, 최근 성능 향상을 이해 캐시를 사용하여 처리함.

6. 기타 고려 사항 변환 우선참조 버퍼(TLB, Translation Look-aside Buffer). 가상 메모리 참조를 위해 메모리 액세스 시간이 두 배로 증가하는 문제점을 해결. 페이지 테이블의 항목들을 위한 특별한 캐시를 사용(메모리의 캐시와 동일한 동작 수행). 프로세스의 전체 페이지 테이블 중 가장 최근에 참조한 페이지 일부만 저장. - 시간의 지역성에 따름. 가상 주소(V = ( p , d ) )가 주어지면, 프로세서는 먼저 변환 우선참조 버퍼를 조사, 페이지 p를 찾음. - 원하는 페이지 테이블의 항목이 있으면(TLB 적중) 프레임 번호(PFN)를 조사하여 메모리 주소를 작성. * 메모리 주소 작성을 위해 변환 우선참조 버퍼를 갱신(페이지 테이블 항목 포함). - 원하는 페이지 테이블 항목이 없다면(TLB 실패) 프로세스는 페이지 번호를 이용하여 해당 페이지 테이블 항목 조사. * 페이지 부재 현상이 발생, 운영체제를 호출하여 처리함. [그림 8-42] 변환 우선참조 버퍼를 이용한 페이징 시스템