4장 가상 기억장치 관리 4.1 가상 기억 장치의 개요 4.2 주소사상 기법 4.3 블록 사상(block mapping) 4.4 페이징 시스템 4.5 세그먼테이션(segmentation) 시스템 4.6 페이지 교체 알고리즘 4.7 기타 고려 사항 연습문제

4.1 가상 기억 장치의 개요 가상 기억장치란? 실제로 하나밖에 존재하지 않는 주소공간 외에 또 다른 가상의 주소공간이 존재하는 것처럼 취급하는 기법 목적 다중 프로그래밍의 정도를 높이고 좀더 효율적으로 주기억장치를 관리함으로써 시스템 성능을 향상

4.2 주소사상 기법 보조기억공간의 가상 주소를 주기억장치의 실 주소로 변환하는 방법 주소사상 : 프로세스의 수행이 계속되는 동안 가상주소가 실 주소로 변환 주소 사상은 빨리 이루어져야 함 그렇지 않으면 시스템 성능이 허용 불가능할 정도로 저하 또한 오버헤드가 발생되어 컴퓨터 효율을 감소 인위적인 연속성 : 가상주소 공간상의 연속적인 주소가 주기억장치에서도 연속적일 필요는 없음

4.2 주소사상 기법 [그림 6.1] 주소 사상 기법

4.3 블록 사상(block mapping)1 동적 주소 변환 기법에서 가상 주소를 실 주소로 변환하기 위한 메카니즘 사상 테이블 : 가상 주소와 대응되는 실 주소를 저장 사상 : 워드 단위 또는 바이트 단위로 이루어진다면 사상에 필요한 정보량이 너무 많음 블록 사상 : 프로그램 정보를 블록 단위로 구분하고 블록 단위로 주소 사상 정보를 기록하여 사용하는 기법

4.3 블록 사상(block mapping)2 블록의 크기를 크게 했을 경우 블록의 크기를 작게 했을 경우 장점 : 사상 테이블의 사상 정보의 크기가 작아지게 되어주소 사상 빨라짐 단점 : 필요 없는 부분이 적재될 가능성이 많아지며 각 블록을 전송 시간이 길어짐 블록의 크기를 작게 했을 경우 장점 : 각 블록이 차지하는 주 기억 공간이 작아지며 전송 시간이 짧아짐 단점 : 사상 테이블의 사상 정보의 크기가 커지며 주소 사상에 필요한 시간이 길어짐

4.3 블록 사상(block mapping)3 페이징(paging) 블록 크기가 일정할 경우를 페이지(page)라 하고 그와 관련된 가상 기억 장치 구성을 페이징이라고 함 세그먼테이션(segmentation) 블록이 서로 다른 크기를 가질 경우 그것을 세그먼트(segment)라고 하며, 그와 관련된 가상 기억 장치 구성을 세그먼테이션이라고 함

블록 사상 시스템에서 주소는 2차원 배열의 원소 형태로 표시 4.3 블록 사상(block mapping)4 블록 사상 시스템에서 주소는 2차원 배열의 원소 형태로 표시 [그림 6.2] 블록 사상을 통한 가상 주소변환

4.3 블록 사상(block mapping)5 가상 주소를 실 주소로 변환 과정 먼저 참조될 항목에 속해 있는 블록번호 b를 블록 사상 테이블의 시작 주소 a에 더함 해당 프로세스의 블록 사상 테이블 접근 블록 사상 테이블에서 블록 b에 대한 엔트리를 찾음. 찾아진 엔트리의 존재 비트를 검사 존재 비트가 주기억장치에 적재되어 있는 경우에는 1, 존재하지 않을 경우에는 0으로 기록 블록 b에 대한 b'을 가지고 있으며, 실제 주소 b'에 변위 d를 더함으로써 구하고자 하는 실제 주소 r=(b'+d)를 구함 실 주소 r로 주기억장치에 접근

4.4 페이징 시스템 여러 개의 페이지 프레임(page frame)이라는 고정된 크기의 블록으로 나눔 가상 주소공간의 크기를 같은 페이지라는 고정된 크기의 블록 구성 기억공간 할당 : 요구 프로세스의 페이지들을 적재하기에 충분한 수의 가용한 페이지 프레임을 찾는 것으로 시작 페이지 프레임 : 분할된 주기억장치 영역들 페이지 크기 : 4096바이트 페이지 프레임들로 구성 페이징 사상 기법 직접 사상(direct mapping) 연관 사상(associative mapping) 직접/연관 혼합 사상 기법

4.4.1 직접 사상 주소 변환1 프로세스의 가상 저장장치를 구성하는 모든 페이지에 대한 항목이 페이지 사상 테이블에 포함 페이지 사상 테이블은 보통 주기억장치에서 유지/관리 변환되는 가상 주소와 페이지 사상 테이블의 시작 주소는 제어장치 내의 고속 레지스터에 저장

4.4.1 직접 사상 주소 변환2 [그림 6.3] 직접 사상에 의한 페이지 주소 변환

4.4.1 직접 사상 주소 변환3 주소 변환 과정 페이지 사상 테이블 시작점 레지스터내의 시작 주소 a를 페이지 p에 더하여, 페이지 사상테이블 내의 p에 항목의 주소 a+p를 구함 해당 프로세스의 블록 사상 테이블에 접근 블록 사상 테이블에서 블록 b에 대한 엔트리를 찾음 존재 비트가 주기억장치에 적재되어 있는 경우에는 1, 존재하지 않을 경우에는 0으로 기록 블록 p의 실기억장치 상의 실제주소 p'을 가지고 있으며, 실제 주소 p'에 변위 d를 더하여 실제 주소 r=(p'+d)구함

4.4.2 연관 사상 주소 변환1 동적 주소 변환을 주기억장치에서 보다 약 10여배 정도 빠른 연관 기억장치에 페이지 사상 테이블을 넣어서 수행하는 방법(캐시 메모리) 장점 : 연관 사상은 빠른 동적 주소 변환이 가능 단점 : 캐시 메모리가 고가이기 때문에 페이지 사상 테이블 전체를 연관 기억장치에 설치하기에는 비용 부담

4.4.2 연관 사상 주소 변환2 [그림 6.4] 연관 사상에 의한 페이지 주소 변환

4.4.2 연관 사상 주소 변환3 변환 과정 현재 수행 중인 프로세스가 가상 주소 v = (p, d)를 참조 페이지 p에 해당되는 페이지 프레임(frame) p'이 발견되면, d와 접속하여 실 주소 r = p'+d를 얻음

4.4.3 혼합 사상 주소 변환 이 사상은 연관 사상 기법의 장점을 취하되 이에 따르는 하드웨어의 비용을 줄여보자는 의도에서 직접 사상 기법과 연관 사상 기법을 같이 사용하는 기법 소규모의 연관 기억 장치를 사용하며 이 기억장치에 프로세스의 페이지 사상 테이블의 일부 내용만 적재하고 페이지 사상 테이블의 전체 내용은 직접 사상 기법에서와 같이 주기억장치의 커널 공간에 둠 결국 연관 기억장치에는 페이지 사상 테이블의 전체 내용 중 최근에 사용된 페이지에 대한 엔트리만을 적재 캐시 기억장치만을 사용한 연관 사상 구현은 주기억장치보다 비용이 너무 많이 들기 때문에 보다 적당한 비용으로 각각의 장점을 살릴 수 있는 방법이 혼합 사상 주소 변환

4.5 세그먼테이션(segmentation) 시스템 서로 다른 크기의 블록들로 분할하는 방법 직접 사상 연관 사상 직접/연관 사상

4.5 세그먼테이션(segmentation) 시스템1 [그림 6.5] 직접 사상에 의한 세그먼테이션 주소 변환

4.5 세그먼테이션(segmentation) 시스템1 변환 과정 현재 수행 중인 프로세스가 가상 주소 v = (s, d)를 참조 페이지 사상 테이블 시작점 레지스터내의 시작 주소 a를 페이지 s에 더하여, 페이지 사상테이블 내의 s에 항목의 주소 a+s를 얻음 가상 페이지 s에 대응하는 s'와 변위 d를 접속하여 실 주소 r=(s'+d)를 얻음

4.6 페이지 교체 알고리즘 4.6.1 FIFO 교체 알고리즘 4.6.2 LRU 교체 알고리즘 4.6.3 최적 교체 알고리즘 4.6.4 LFU(Least Frequently Used) 교체 알고리즘 4.6.5 2차 기회 알고리즘

4.6.1 FIFO 교체 알고리즘1 주기억장치 내에 가장 오랫동안 있었던 페이지를 교체시키는 방법

4.6.1 FIFO 교체 알고리즘2 프레임 할당량이 증가하여도 오히려 페이지 부재율이 증가하는 비정상적인 현상 시간적으로 가장 먼저 주기억장치에 적재된 페이지를 교체시키는 알고리즘 보통 FIFO 프로세스 당 페이지 프레임이 증가할수록 페이지 부재율이 감소되는 것이 일반적 Belady 변이(FIFO 모순) 프레임 할당량이 증가하여도 오히려 페이지 부재율이 증가하는 비정상적인 현상

4.6.1 FIFO 교체 알고리즘3 Beady 변이 예 [그림 6.7] FIFO 교체 알고리즘(페이지 프레임 4개 예)

4.6.1 FIFO 교체 알고리즘4 장점 단점 FIFO 알고리즘은 다른 알고리즘에 비해 이해하기 쉽고 설계가 간단 계속 사용되고 있는 페이지가 오랫동안 있었다는 이유로 교체되어야 하는 불합리를 발생 Belady 변이 또는 FIFO 모순이 발생되는 단점

4.6.2 LRU 교체 알고리즘1 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체시키는 방법 가장 최근에 사용된 페이지가 교체되지 않는다고 할 수 있음 이 알고리즘은 페이지 참조의 시간적 구역성을 고려하여 FIFO 알고리즘의 모순을 개선하기 위해 고안 즉, 프로그램의 구역성을 고려할 때 최근에 참조된 페이지는 앞으로도 참조될 가능성이 많고, 최근에 참조되지 않은 페이지는 앞으로도 참조되지 않을 가능성이 많다는 사실을 알 수 있음

4.6.2 LRU 교체 알고리즘2 [그림 6.8] LRU 교체 알고리즘

4.6.2 LRU 교체 알고리즘3 장점 실제로 대부분의 프로그램들이 구역성이라는 특성을 갖고 있기 때문에 이 기법은 일반적으로 좋은 성능을 보이는 것으로 평가되어 왔으며, 따라서 LRU 기법은 실제로 가장 많이 사용되고 있는 기법 또한 시스템의 특성에 따라 이 기법을 여러 가지 형태로 변형하여 사용 단점 각 페이지들이 호출될 때마다 그 때의 시간을 테이블에 기억시켜야 하므로 오버헤드 발생 이로 인한 알고리즘이 복잡

4.6.3 최적 교체 알고리즘1 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 장점 단점 최소의 페이지 부재율을 가지는 알고리즘 Belady가 제안한 것으로 FIFO의 모순을 피할 수 있는 알고리즘 단점 최적성을 갖기 위해서는 페이지 참조에 대한 예측 필요 그러나 정확한 예측이 불가능하기 때문에, 일반적으로 이 기법은 실현 불가능한 것으로 알려져 있음

4.6.3 최적 교 알고리즘2 [그림 6.9] 최적 교체 알고리즘

4.6.4 LFU(Least Frequently Used) 교체 알고리즘1 참조된 횟수가 가장 적은 페이지를 교체시키는 방법 만일 교체 대상인 페이지가 여러 개일 경우에는 LRU 기법에 따라 페이지를 교체 주기억장치에 적재되어 있는 페이지들이 참조될 때마다 그 참조 횟수를 누적

4.6.4 LFU(Least Frequently Used) 체 알고리즘2

4.6.4 LFU(Least Frequently Used) 체 알고리즘3 장점 LRU 기법이 갖는 오버헤드를 줄이면서 LRU 기법에서처럼 프로그램의 지역성을 이용하여 프로세스의 실행 과정에서 발생하는 페이지 부재 횟수를 적게 하고자 고안된 기법 단점 최근에 주기억장치에 적재된 페이지가 이후 참조될 가능성이 많음에도 불구하고 이를 교체시킬 가능성이 많음 각 페이지들이 참조될 때마다 해당 페이지의 참조 횟수를 증가시키는 일이 어느 정도 오버헤드로 작용할 수 있음

4.6.5 2차 기회 알고리즘 FIFO 알고리즘의 변형으로 페이지 테이블의 각 항목에 한 개의 참조 비트를 두는 방식 참조 비트의 초기값은 그 페이지가 처음으로 적재될 때 운영체제에 의해 '0'으로 설정 그 후 프로세스가 수행되면서 참조된 페이지는 '1'로 바뀜 참조 비트가 '1'인 페이지는 '0'인 페이지보다 최근에 사용되었음을 알 수 있음 만약 새로운 페이지가 주기억장치에 적재되어야 할 경우에는 우선 모든 페이지의 참조 비트를 조사하여 '0'이면 그 페이지를 교체하고, '1'이면 그 페이지에게 2차 기회 부여 다음 페이지는 FIFO 방식으로 진행하면서 교체

4.7.1 페이지 크기1 가상 기억장치 시스템에서 페이지의 크기는 시스템의 성능에 많은 영향 줌 페이지 크기 결정 고려사항 : 디스크를 접근하는데 소요되는 시간 디스크를 접근하는데 소요되는 시간 탐색시간 회전 지연시간 전송시간 전송시간은 페이지 크기에 비례하기 때문에 크기가 작을수록 유리 탐색시간과 회전 지연 시간은 페이지 크기와 무관하며 전송시간에 비해 상당히 많이 소요

4.7.1 페이지 크기2 페이지의 크기가 큰 경우 페이지 크기를 작게 하면 페이지 사상 테이블(PMT)의 크기가 줄어들어 주기억장치의 공간을 절약 디스크와 주기억장치간에 대량의 바이트 단위로 이동되기 때문에 오버헤드 감소 참조하고자 하는 정보와 무관한 정보가 주기억 장소 적재 페이지 단편화로 인해 많은 기억 공간을 낭비 초래 페이지 크기를 작게 하면 동일한 크기의 프로그램에 더 많은 수의 페이지가 필요하게 되어 주소 변환에 페이지 사상 테이블의 공간이 크기가 늘어 주기억장치 공간 낭비 페이지 단편화를 감소시키고 특정한 참조 지역성만을 포함하기 때문에 기억 장치 효율 향상

4.7.2 스래싱(Thrashing)1 [그림 6.11] 스래싱 프로세스들이 진행되는 과정에서 페이지 부재가 너무 빈번하게 발생되어 실제로 프로세스들을 처리하는 시간보다 페이지 교체 시간이 더 많아 CPU의 효율이 떨어지는 현상 [그림 6.11] 스래싱

4.7.2 스래싱(Thrashing)2 스래싱을 방지하기 위한 가장 좋은 방법 페이지 부재율이 너무 높으면 더 많은 페이지 프레임 필요 너무 낮으면 너무 많은 프레임을 할당 페이지 부재율의 상한과 하한을 정해 놓고, 페이지 부재 빈도가 상한선에 도달하게 되면 스래싱 현상이 발생할 위험이 있으므로 운영체제는 임의의 프로세스 일부를 회수하여 스래싱을 방지 반대로 페이지 부재 빈도수가 하한에 도달하게 되면 많은 프레임을 할당되고 있음을 나타내고 있기 때문에 임의의 프로세스를 더 할당하여 다중 프로그램의 정도를 높임.

4.7.2 스래싱(Thrashing)3 [그림 6.12] 페이지 부재 빈도

4.7.3 구역성(locality)1 실행중인 프로세스는 시간에 따라 그 주소 공간의 일정 부분만을 집중적으로 참조하는 한 프로세스가 실행되는 동안 현재 실행되는 주소 부근에서만 분기 등의 작업이 발생 대부분의 프로그래밍 언어들이 제공하는 기능들 중에 반복 구조가 있고 거의 모든 프로그램들이 이 반복 구조를 사용하여 작성되기 때문 반복 구조에 속해 있는 명령들은 지정된 횟수만큼 또는 일정한 조건이 만족할 때까지 반복 실행되므로 다른 명령들에 비해 실행 횟수가 많아짐

4.7.3 구역성(locality)2 구역성의 시간 및 공간적인 특성 시간 구역성(temporal locality) 최근에 참조된 기억 장소의 일정 부분이 그 후에도 계속 참조될 가능성이 높음을 의미 공간 구역성(spatial locality) 일단 어느 기억 장소가 참조되면 그 기억 장소 부근이 계속 참조될 가능성이 높음을 의미

4.7.4 작업 세트(working set)1 실행 중인 프로세스가 일정시간 동안에 참조하는 페이지의 집합을 말함 임의의 프로세스가 효율적으로 실행되기 위해서는 그 프로세스의 작업 세트가 주기억장치 내에 존재 그렇지 못한 경우에는 필요한 페이지를 위해서 자주 교체함으로 인해서 스래싱이 발생 한 사용자가 프로그램의 실행을 요구하면 첫 번째 페이지가 주기억장치에 적재되고 실행이 계속되면서 더 많은 페이지가 적재 적재되는 페이지들에는 변수 선언, 명령어, 데이터 등

4.7.4 작업 세트(working set)1 일정 시간이 지나면 대부분의 프로그램은 상당히 안정된 상태에 도달하고 추가적인 페이지 부재가 거의 발생하지 않고 실행을 계속 바로 이 시점이 작업의 작업 세트가 주기억장치에 적재되어 있는 상태 프로그램은 한동안 많은 페이지 부재를 발생하지 않고 실행 그 후 시간이 지나면 작업을 진행하기 위해 또 다른 페이지들의 집합을 필요로 하는 다른 국면을 만나게 되며, 이는 또 다른 작업 세트를 형성 따라서 수행중인 프로그램이 주기억장치안에 작업 세트를 유지시키고 있다면 CPU의 효율을 향상

연습 문제 1. 가상기억장치의 개념을 설명하시오. 2. 주소 사상 기법이 무엇이며, 왜 주소 사상이 필요한지 설명하시오. 3. 페이지 사상 테이블에 대해서 설명하시오. 4. 페이지와 세그먼트에 대해서 비교 설명하시오. 5. 페이지를 크게 했을 때와 작게 했을 때 어떤 차이가 있는지 설명하시오. 6. 연관 사상과 직접 사상을 비교하고, 장.단점이 무엇인지 7. FIFO 교체 알고리즘과 LRU 교체 알고리즘을 비교 설명하시오. 8. 가상 기억장치 관리를 위한 교체 기법 중 LRU 기법이 제안된 배경이 무엇인가에 대해 설명하시오. 9. 스래싱이 왜 발생하는지 설명하시오.