운영체제 강의노트 정리 - 가상기억장치

Presto

2020-01-18

가상기억장치

배경

프로그램을 실행하는 동안 프로그램 전체를 모두 사용하지는 않는다.

예를 들어, 오류를 처리하는 루틴은 오류가 발생하지 않으면 사용되지 않으며, 배열 / 연결 리스트 / 테이블과 같은 구조는 실제로 사용되는 공간보다 많은 공간을 할당하여 사용한다. 또한 프로그램의 일부 기능과 특징은 거의 사용되지 않는 경우가 많다.

말하자면, 프로그램을 실행하는 어느 한 순간에 프로그램 전체를 필요로 하지 않는다.

프로그램의 일부만 주기억 장치에 올려 실행 가능하도록 하면, 프로그램은 물리적 주기억 장치의 크기에 제한을 받지 않게 되고, 여러 프로그램을 주기억 장치에 적재할 수 있게 되며, 프로그램을 적재하는데 걸리는 입출력 비용을 줄일 수 있다.

가상 기억 장치는 요구 페이징demand paging 기법을 이용하여 위를 구현한다. 이 때 세그먼테이션과 결합하여 사용될 수 있다.

요구 페이징

요구 페이징은 스와핑과 페이징을 결합하여 사용한다. 이는 프로세스 전체를 스왑하지 않고, 지연 스와퍼lazy swapper를 사용하여, 페이지가 필요한 경우에만 주기억 장치에 적재한다.

페이징에서는 스와퍼라는 용어 대신 페이저pager라는 용어를 사용한다.

기본 개념

프로세스가 스왑 인 될 때 페이저는 어떤 페이지를 사용할지 추측한 다음 그 페이지들만 스왑 인 한다.

이를 위해 주기억 장치에 있는 페이지와 디스크에 있는 페이지를 구분할 수 있어야 하며, 유효 비트를 사용하여 구분한다.

유효 비트가 1이면 주기억 장치에 있는, 0이면 디스크에 있거나 가상 주소 공간에 포함되지 않은 페이지임을 의미한다.

프로세스가 주기억 장치에 적재되지 않은 페이지에 접근하는 경우, 다음의 절차에 따라 그 페이지를 주기억 장치에 적재한다.

유효 비트가 0이므로 페이지 결함 트랩page fault trap이 발생한다.
트랩이 발생하면 프로세스의 PCB를 살펴 참조의 유효성을 검사한다. 프로세스의 가상 주소 공간을 벗어난 참조를 하여 참조가 유효하지 않은 경우 프로세스는 종료된다.
빈 프레임을 찾는다.
디스크 입출력을 이용하여 페이지를 프레임에 적재한다.
디스크 입출력이 종료되면 프로세스의 내부 테이블과 페이지 테이블을 수정한다.
페이지 결함 트랩을 발생시킨 명령어를 다시 수행한다.

순수 요구 페이징은 프로세스가 처음 실행될 때 주기억 장치에 페이지가 전혀 없는 상태로 시작하는 방식을 의미한다. 따라서 초기에는 페이지 결함이 자주 발생한다.

한 명령어를 실행한 결과로 여러 페이지 결함이 발생할 수 있으나, 참조의 지역성locality of reference 원리로 인해 이러한 경우는 매우 드물다.

하드웨어는 다음과 같은 부분에서 요구 페이징을 지원한다.

페이지 테이블에 대한 지원 : TLB, 유효 비트, 보호 비트
보조 기억 장치 : 디스크 일부분을 스왑 공간으로 사용

일반적으로 페이지 결함을 일으킨 명령어를 다시 실행하는 것은 문제가 되지 않는다.

힌 명령어가 두 개 이상의 다른 페이지에 접근하는 경우 명령어를 다시 실행하는 것이 간단하지 않은데, 이를 해결하기 위한 해결책은 다음과 같다.

명령어 수행에 필요한 모든 페이지를 미리 검사하여 이들을 주기억 장치에 적재한 후 명령어를 수행한다.
임시 레지스터를 이용하여 일시적으로 바꾼 위치의 기존 값을 보관하고, 페이지 결함이 발생하면 기존 값을 복원한 후 다시 명령어를 수행한다.

요구 페이징의 성능

(페이지 결함이 일어날 확률) * (페이지 결함을 처리하는 데 소요되는 시간) + (1 - 페이지 결함이 일어날 확률) * (주기억 장치 접근 소요 시간)

페이지 결함의 처리는 다음의 요소로 구성된다.

페이지 결함 인터럽트의 처리의 소요 시간은 마이크로초 단위를 갖는다.
디스크에 있는 페이지를 주기억 장치에 적재한다. 디스크 입출력에 소요되는 시간은 주기억 장치에 접근하는 시간과 비교했을 때 매우 크다.
디스크 입출력이 발생하므로 프로세스는 대기중 상태가 되며, CPU는 스케줄링 알고리즘에 따라 해당 프로세스를 스케줄링하여 중단된 프로세스를 재개한다.

페이지 결함을 처리하는 전체 시간은 디스크 입출력 시간에 비례한다.

스왑 공간에 대한 입출력은 디스크 내의 다른 공간으로부터의 입출력보다 상대적으로 빠르므로, 프로그램을 실행할 때 모두 스왑 공간으로 옮긴 후 스왑 공간에서 페이징이 일어나도록 하면 성능을 향상시킬 수 있다.

프로세스 생성

Copy-on-Write

프로그램을 처음 실행하면 디스크에 있는 실행 이미지를 이용하여 프로세스를 생성하며, fork 명령을 사용하여 자식 프로세스를 생성할 수 있다. 이 때 디스크 입출력은 필요 없다.

보통 자식 프로세스는 exec 명령을 통해 다른 프로그램을 실행하므로, 부모 프로세스의 주소 공간을 복사하는 것은 낭비다.

이 때 copy-on-write 기법을 사용하여, 변경하는 페이지만 복사되고 나머지는 부모 프로세스와 공유하도록 할 수 있다.

기억장치-사상 파일

디스크에 있는 파일에 접근할 때마다 디스크 입출력이 발생하므로, 파일에 처음 접근할 때 페이지 크기만큼의 데이터를 가상 기억 장치에 적재하고, 그 다음부터는 주기억 장치 접근을 통해 파일에 접근하는 방식이다.

페이지 교체

다중 프로그래밍의 정도를 높이면 프레임 공간이 부족할 수 있고, 주기억 장치의 모든 프레임을 사용자 프로세스에게 할당해줄 수 없다.

페이지 결함이 발생했을 때 페이지를 수용할 프레임이 없다면, 운영체제는 다음 중 한 가지 방법을 선택하여 이를 해결해야 한다.

프로세스 종료
프로세스 스왑 아웃 : 프로세스의 모든 페이지를 디스크로 스왑 아웃하여 다중 프로그래밍의 정도를 줄인다.
페이지 교체page replacement : 적재되어 있는 기존 페이지를 새로운 페이지로 교체

기본 방법

페이지 결함이 발생할 때, 다음의 절차로 페이지 교체가 이루어진다.

디스크에서 페이지의 위치를 찾는다.
빈 프레임을 찾는다. 빈 프레임이 있으면 그 곳에 페이지를 적재하고, 없으면 페이지 교체 알고리즘을 이용하여 희생 프레임을 선택한다. 희생 프레임에 있는 페이지를 디스크에 쓰고, 그 프레임에 새로운 페이지를 적재한다.
페이지 테이블과 프레임 테이블을 변경한다.
프로세스를 재개한다.

빈 프레임이 없는 경우 항상 두 번의 디스크 입출력이 필요하며, 변경 비트modify bit, dirty bit를 이용하여 줄일 수 있다.

변경이 없는 페이지가 희생자로 선택되면 이를 디스크에 쓸 필요가 없으나, 디스크에 이 페이지의 복사본이 없다면 변경 여부에 상관 없이 디스크에 써야 한다.

실행 전용 페이지는 무조건 디스크로 다시 옮겨질 필요가 없다.

다음의 알고리즘이 필요하다.

프레임 할당 알고리즘frame-allocation algorithm : 한 프로세스에게 할당할 프레임의 수를 결정
페이지 교체 알고리즘page-replacement algorithm : 빈 프레임이 없을 때 희생 프레임을 선택. 낮은 페이지 결함률을 제공할 수 있어야 한다.

일련의 주기억 장치 참조에 대하여 페이지 결함 수를 계산하여 알고리즘을 평가한다.

페이지 결함 수를 계산하기 위해서는 프로세스에게 할당된 프레임의 수를 알아야 하며, 프레임 수가 많을 수록 결함 발생 수는 적어진다.

FIFO 페이지 교체 알고리즘

First-In-First-Out

가장 오래 전에 들어온 페이지가 희생자로 선택된다.

프레임 수가 증가하면 페이지 결함 발생 수는 감소해야 정상이나, FIFO 알고리즘을 사용하는 경우 그 수치가 증가하는 경우가 있다.

OPT 페이지 교체 알고리즘

Optimal

가장 오랫동안 사용되지 않을 페이지가 희생자로 선택된다.

페이지 결함 수를 이 이상으로 줄일 수 없다.

미래의 참조를 예측하는 것이 어렵다는 것이 문제다.

LRU 페이지 교체 알고리즘

Least-Recently Used

가장 오래 전에 참조된 페이지가 희생자로 선택된다.

가장 널리 사용되는 기법이다.

카운터를 사용하여 구현할 수 있다. 각 페이지 테이블의 항에 카운터 필드를 추가하여 마지막으로 접근된 시간을 나타낸다.

이 방법을 사용하는 경우 교체가 필요할 때마다 테이블 전체를 검색해야 하며, 페이지가 접근될 때마다 페이지 테이블을 갱신해야 한다.

스택을 사용하여 구현할 수 있다. 스택의 가장 위에 가장 최근에 접근한 페이지를 유지하고, 가장 아래에 교체할 페이지를 유지한다. 스택 중간에 있는 페이지를 맨 위로 옮길 수 있어야 하므로 이중 연결 리스트를 이용하여 구현한다.

갱신 비용이 카운터보다 많이 소요되지만, 검색할 필요가 없어진다.

하드웨어의 지원이 반드시 필요하다. 소프트웨어로 테이블을 갱신하면 주기억 장치 접근마다 많은 시간이 소요된다.

근접 LRU 페이지 교체 알고리즘

LRU를 제공하기 위한 충분한 하드웨어 지원이 없는 경우 사용한다.

대부분의 컴퓨터는 참조 비트reference bit를 제공하며, 어떤 페이지가 참조되면 자동으로 해당 페이지 테이블을 갱신해준다. 이를 이용하여 LRU와 근접한 페이지 교체 알고리즘을 제공할 수 있다.

추가 참조 비트 알고리즘

각 페이지마다 참조 비트 외에 추가로 8비트를 두고, 주기적으로 오른쪽 쉬프트 연산을 수행하여, 지난 8주기 동안 각 페이지의 접근 여부를 유지하는 방법이다.

0000 0000이라면 8주기 동안 한 번도 접근되지 않은 페이지를 나타내며, 1100 0100인 페이지는 0111 0111인 페이지보다 최근에 접근되었음을 의미한다.

이를 유지하는 비트의 수는 다양할 수 있으며, 극단적으로 그 수를 0까지 줄일 수 있다.

기회를 한번 더 주는 알고리즘

참조 비트만 사용한다. 처음에 페이지에 접근하면 참조 비트가 1이 되고, 주기마다 이것을 다시 0으로 바꾸어 준다.

순환 버퍼를 이용하여 구현할 수 있다.

교체할 페이지는 순환 버퍼에서 비트 값이 0인 것이 선택되며, 이를 찾을 때까지 비트 값이 1인 것을 0으로 바꾼다.

새 페이지는 순환 버퍼에 교체되는 페이지 위치에 삽입된다.

순환 버퍼에 있는 모든 페이지의 값이 1이면 이 알고리즘은 FIFO와 같아지게 된다.

확장된 클럭 알고리즘

참조 비트와 변경 비트를 함께 사용한다. (참조 비트, 변경 비트)

1분류 (0, 0) : 최근에 사용되지 않고, 변경되지 않은 페이지
2분류 (0, 1) : 최근에 사용되지 않았으나 변경된 페이지. 교체시 디스크에 써야 한다.
3분류 (1, 0) : 최근에 사용되었으나 변경되지 않은 페이지
4분류 (1, 1) : 최근에 사용되고 변경된 페이지

낮은 분류에 속한 페이지를 먼저 교체한다. (사용되지 않은 페이지를 우선적으로 교체한다.)

검색 시간이 길어진다.

계수 기반 페이지 교체 알고리즘

LFU : Least-Frequently-Used

참조된 횟수를 기반으로 한다. 참조가 가장 적은 페이지를 교체한다.

초기에 많이 사용되었으나 더 이상 사용되지 않은 페이지는 교체되지 않을 수 있으며, 처음으로 교체되어 들어온 페이지는 바로 교체될 수 있다.

주기적으로 참조 횟수를 감소시켜 전자의 문제를 극복할 수 있다.

MFU : Most-Frequently-Used

참조가 가장 많은 페이지를 교체한다. 참조가 적은 것일수록 최근에 들어온 것으로 간주한다.

두 방법 모두 거의 사용되지 않는다.

페이지 버퍼링 알고리즘

고정된 수의 빈 프레임을 유지하여, 새로운 페이지를 희생자 프레임에 적재하지 않고 우선 빈 프레임 풀에 속한 프레임에 적재한다.

희생자 프레임이 디스크에 쓰여지면 이 프레임을 빈 프레임 풀에 추가한다.

빈 프레임 풀에 속한 각 프레임에 어떤 페이지가 적재되어 있는지 유지하여 페이지 교체 때 이를 활용할 수 있다.

변경된 페이지 목록을 유지하고, 페이징 장치가 유휴 상태이면 변경 페이지를 하나 선택하여 디스크에 쓰고 변경 비트를 재설정한다.

교체할 페이지가 항상 변경되지 않은 깨끗한 페이지일 확률을 높여준다.

프레임 할당

운영체제가 필요로 하는 만큼을 제외한 나머지 프레임은 모두 사용자 프로세스에게 할당된다. 이 중 일부는 항상 빈 프레임이 되게 할 수 있다.

최저 프레임 수

프로세스가 필요로 하는 최소 프레임 수 이상을 프로세스에게 할당해 주어야 한다.

최저 프레임 수는 명령어 집합 구조instruction set architecture가 결정한다. 하나의 명령어가 참조할 수 있는 모든 페이지를 수용할 수 있을 만큼의 프레임은 최소한 제공되어야 한다.

명령어가 위치한 프레임과, 명령어가 참조하는 페이지는 동시에 수용될 수 있어야 한다. 페이지 결함이 발생하면 그 페이지를 주기억 장치에 적재한 후 명령어를 다시 실행할 수 있어야 하기 때문이다.

할당 알고리즘

프레임의 개수가 n개이고, 프로세스의 개수가 m개일 때,

균등 할당equal allocation 알고리즘은 각 프로세스에게 n / m 개의 프레임을 할당한다.

비례 할당proportional allocation 알고리즘은 각 프로세스의 크기에 비례하여 할당한다.

우선순위 기반 알고리즘은 각 프로세스의 우선순위에 비례하여 프레임을 할당한다.

광역 및 지역 할당

다중 프로세스가 존재할 때, 페이지 교체 알고리즘은 다음과 같이 분류된다.

광역 교체 알고리즘global replacement algorithm : 다른 프로세스의 페이지가 희생자로 선택될 수 있음
지역 교체 알고리즘local replacement algorithm : 자신의 프로세스에 있는 페이지만 희생자로 선택될 수 있음

광역 교체는 우선순위가 높은 프로세스에게 우선순위가 낮은 프로세스를 희생시켜 할당된 프레임 수를 늘려줄 수 있으나, 프로세스 성능이 외부 상황에 의해 변화할 수 있다.

현재는 광역 교체 알고리즘을 많이 사용한다.

스레싱

Thrashing. 계속하여 페이지 결함이 발생하는 현상을 말한다.

실행 시간보다 페이지 결함을 처리하는 시간이 많아지면 스레싱이 발생하였다고 말한다.

프로세스에 할당된 프레임 수가 필요한 최소의 프레임 수 이하로 내려가면 스레싱이 발생한다.

스레싱의 원인

다중 프로그래밍의 정도가 낮으면 CPU 사용 효율이 떨어지며, 이를 높이기 위해 프로세스의 수를 과도하게 늘리면 스레싱이 발생하여 오히려 사용 효율이 떨어지게 된다.

지역 교체 알고리즘을 사용하면 스레싱 효과를 줄일 수 있다. 하나의 프로세스에서의 스레싱이 다른 프로세스에 영향을 주지 않기 때문이다.

하지만 스레싱이 발생한 프로세스는 대부분의 시간을 페이징 장치의 큐에서 보내게 되므로 다른 프로세스도 기다리는 시간이 길어지게 된다.

프로세스에게 필요한 만큼의 프레임을 할당해줄 수 있어야 스레싱을 예방할 수 있으나, 필요로 하는 프레임 수를 알기 어렵다.

지역성 모델locality model : 프로세스는 실행되는 동안 한 지역(현재 활동적으로 사용하고 있는 페이지 집합)에서 다른 지역으로 이동하는데, 현재 프로세스의 지역을 수용할 수 있는 만큼의 프레임을 할당해 주면 스레싱은 발생하지 않는다.

작업 집합 모델

Working-Set Model. 지역성 가정에 기반한 모델이다.

가장 최근에 참조한 페이지 집합을 말한다.

작업 집합이 작으면 현재 지역을 충분히 나타내지 못하며, 크면 다른 지역과 중첩될 수 있다.

운영체제는 각 프로세스의 작업 집합을 감시하여 각 프로세스의 현재 작업 집합을 수용할 수 있는 충분한 수의 프레임을 각 프로세스에게 할당한다.

새 프로세스를 수용할 만큼의 빈 프레임이 생기면 새 프로세스를 실행하며, 각 프로세스의 작업 집합 크기가 사용 가능한 프레임 수를 초과하면 하나의 프로세스를 일시 중단한다.

페이지 결함 빈도

페이지 결함 빈도에 따라 할당되는 프레임 수를 조절한다.

페이지 결함률의 상한과 하한을 정하여, 결함률이 상한보다 높으면 프레임을 추가로 할당하고, 하한보다 낮으면 프레임을 제거한다.

페이지 결함률이 상한을 넘었으나 추가로 할당해 줄 빈 프레임이 없으면 프로세스를 일시 중단한다.

다른 고려

선페이징

Prepaging.

순수 요구 페이징의 문제는, 초기에 많은 페이지 결함이 발생한다는 것이다. 또한 스왑 아웃된 프로세스를 다시 실행할 때에도 같은 현상이 발생한다.

선페이징 방식을 사용하여 초기 높은 페이지 결함률을 줄일 수 있다.

작업 집합 모델을 사용하는 경우, 스왑 아웃할 때 작업 집합 모델에 포함된 페이지 목록을 보관하였다가 다시 스왑 인 될 때 그 페이지 목록을 모두 적재한 후 프로세스를 재개한다.

선페이징의 비용이 페이지 결함을 처리하는 비용보다 적어야 효과가 있다.

페이지의 크기

페이지 크기가 클수록 페이지 테이블의 크기는 작아지나, 마지막 페이지에 존재하는 내부 단편화가 크다.

입출력 시간을 최소화하려면 페이지 크기가 큰 것이 좋다.

입출력의 전체 크기는 페이지 크기가 작은 것이 좋다. 페이지 크기가 작을 수록 지역성이 향상되어 불필요한 것이 주기억 장치에 적재될 확률이 낮아지기 때문이다.

페이지 결함률은 페이지 크기가 클수록 낮다. 페이지 결함이 낮을수록 페이지 결함을 처리하는 오버헤드가 적어진다.

최근에는 페이지 크기를 크게 하여 사용한다.

TLB 범위

TLB : 페이지 테이블을 구현하기 위한 하드웨어 지원. 캐시 역할

TLB 적중률hit ratio은, 페이지 테이블 대신 TLB에서 가상 주소 번역이 이루어지는 비율을 말한다.

TLB 범위reach는 TLB를 통해 접근 가능한 주기억 장치 공간을 말한다.

최소한 프로세스의 작업 집합은 TLB에 저장되어 있어야 한다.

페이지 크기를 늘리면 TLB 범위도 넓어지지만 내부 단편화가 증가할 수 있다.

프로그램의 구조

// (1)
for (i = 0; i < 128; ++i) {
  for (j = 0; j < 128; ++j) {
    a[j][i] = 0;
  }
}

// (2)
for (i = 0; i < 128; ++i) {
  for (j = 0; j < 128; ++j) {
    a[i][j] = 0;
  }
}

위의 코드에서, (1)은 (2)보다 효율적이지 않다. 배열은 행 중심이므로 (1)의 경우에 페이지 결함이 더 많이 발생할 수 있기 때문이다.

예를 들어 스택의 경우 항상 맨 위에 있는 스택 요소를 이용하여 조작하므로 페이징에 효율적이지만, 해시 테이블의 경우 접근 위치가 널리 퍼져 있으므로 페이징에 효율적이지 않다.

페이징에 유리한 코드를 작성하여 성능을 높이는 것이 좋다.

페이지 잠금

요구 페이징을 사용할 때, 어떤 페이지들은 교체될 수 없게 해야 하는 경우가 있다. 예를 들어 입출력을 요청한 프로세스가 입출력할 내용을 버퍼에 옮기고 입출력 대기 큐로 이동한 후, 광역 교체 알고리즘에 의해 큐로 이동한 프로세스의 버퍼 페이지가 교체되는 경우, 엉뚱한 데이터가 입출력될 수 있다.

이를 해결하기 위해 입출력은 항상 시스템에게 할당된 주기억 장치 영역에서 이루어지도록 할 수 있으나 추가 복사가 필요하게 된다.

각 프레임마다 잠금 비트lock bit를 연관시켜 희생자로 선택될 수 없게 할수도 있다.

입출력에 사용될 버퍼나 운영체제 커널에게 할당된 페이지는 잠금 비트를 설정하여 교체될 수 없도록 한다.

잠금 기법은 주의 깊게 사용되어야 한다. 사용자 페이지는 잠금 후 적절할 때에 잠금 해제되어 사용할 수 있는 프레임 수를 일정 수준으로 유지할 수 있게 해야 한다.