가상 메모리 (Virtual Memory)

공룡책(10판) Chapter 10 요약

9장의 페이징에서의 스와핑 부분에서 10장의 언급이 있었다. 물리 메모리보다 큰 프로그램을 실행하는 기법 알아보도록 하자

배경 _ Background

이전에는 실행되고 있는 코드가 반드시 물리 메모리에 존재해야 하였고, 필요에 따라 동적 적재(dynamic loading) 방법을 사용하였다. 동적 적재는 전체 프로세스를 메모리에 올리는 제약을 완화하였지만 프로그래머에게는 여전히 부담이다.

메모리에 전체를 올려놓을 필요는 없다, 배열, 리스트, 테이블과 같은 자료구조들이나 거의 실행되지 않는 코드나 기능이 프로그램에 포함되어 있을 수 있기 때문이다. 프로그램의 일부분만 메모리에 올려놓고 실행함으로 다음과 같은 이점을 챙길 수 있다.

1. 프로그램이 물리 메모리 크기에 의해 제약받지 않음
2. 더 많은 프로그램 동시 수행 가능 - 응답 시간(response time, turn around time)은 늘어나지 않고 CPU 이용률(utilization)과 처리율(throughput)이 높아진다.
3. 프로그램을 메모리에 올리고 스왑(swap) 하는데 필요한 I/O 횟수가 줄어들어 프로그램이 빨리 실행된다.

가상 메모리는, 어떤 프로세스가 실행될 때 이를 실제 메모리에 올리지 않고 물리 메모리보다 프로세스의 메모리가 더 커도 실행가능하게 해준다. 실제의 물리 메모리 개념과 개발자의 논리 메모리 개념을 분리한 것이다. 사용하지 않는 메모리는 가상 메모리로써 서브 메모리(SSD나 HDD)에 올려둔다.

가상 주소 공간은 프로세스가 메모리에 저장되는 논리적인 모습이다. 논리 주소 상에는 연속적이나 실제 물리적으로는 연속적이지 않을 수 있다. 물리 -> 논리 페이지로 사상하는 것은 메모리 관리 장치에 달렸다.

논리 메모리를 물리 메모리로부터 분리해주는 것 말고도 가상 메모리는 페이지 공유(page sharing)을 통해 파일이나 메모리가 둘 이상의 프로세스들에 의해 공유할 수 있게 한다. (공유하는 파일과 메모리를 shared page에 두고 사용)

요구 페이징 _ Demand Paging

실행 프로그램을 보조저장장치에서 메모리로 적재하는 방법에 대해 생각한다. 여기서의 전략은 필요한 페이지 단위 올리는 것이다. 각각의 페이지를 올리는 시점은 필요한 요청, 요구가 있을 때이다. 그래서 요구 페이징 (demand paging) 이다.

- 기본 개념 _ Basic Concepts

프로세스가 실행되는 동안 일부 페이지는 메모리에, 일부는 보조저장장치에 있다. 이 둘을 구분하기 위해 하드웨어 지원이 필요하다. 즉 가상 메모리의 요구 페이지와 실행 중 요청되는 페이지를 구분하는 방법이 필요하다. 여기서 이전에 사용되었던 valid-invalid bit 개념을 다시 활용하여, 요구 페이징의 유효성 확인을 수행한다.

• valid: 해당 페이지가 메모리에 있다.
• invalid: 해당 페이지가 유효하지 않거나 보조저장장치(secondary storage)에 있다.

여기서 페이지 폴트(Page Fault)란 아직 메모리에 로딩 되지 않는 페이지에 액세스를 요청하는 것이다. 이 때 페이지 폴트 트랩을 발생시킨다. 페이지 폴트를 처리하는 과정은 다음과 같다.

1. 프로세스에 대한 내부 테이블 (internal table) 을 확인하여 메모리 참조(reference)가 유효한 페이지인지 확인
   • 무효한 참조라면 프로세스는 중단된다.
2. 유효한 참조인데 메모리에 올라오지 않았다면 일단 트랩, 보조저장장치로부터 가져와야 한다.
3. 비어 있는 프레임=가용 프레임(free frame)을 찾는다.
4. 보조저장장치에 있는 페이지를 해당 프레임으로 로드해준다. (OS가 free-frame list를 관리)
5. internal table이나 page table을 갱신, 메모리에 해당 페이지가 있다고 표시한다.
6. 트랩에 의해 중단되었던 명령어를 다시 수행한다. 프로세스는 그 페이지에 메모리가 있었던 것처럼 접근 가능하다.

순수 요구 페이징

극단적 경우에는 메모리에 페이지가 없는 상태로 프로세스를 실행할 수 있고, 처음에 메인 메모리에 아무것도 없기 때문에 첫번째 요청은 무조건 페이지 폴트가 발생한다. 프로세스가 사용하는 모든 페이지가 메모리에 올라올 때까지 필요할 때마다 페이지 폴트가 발생하고 모든 페이지가 적재하면 발생하지 않는데 이것을 순수 요구 페이징(Pure Demand Paging)이라 한다. 페이지가 필요해지기 전에는 해당 페이지를 메모리에 적재하지 않는 방법이다.

참조 지역성

프로세스가 여러 페이지에 접근하게 되면 동시다발적 페이지 폴트가 발생할 수 있다. 허나 다행히 이것은 드물다고 한다. 모든 프로그램은 참조 지역성(locality of reference) 이라는 성질이 있어 프로그램의 어느 한 특정 부분만 집중적으로 참고하여, 이것 덕분에 요구 페이징은 괜찮은 성능을 보여준다.

하드웨어

요구 페이징을 지원하기 위해 필요한 하드웨어는 페이징, 스와핑을 위한 하드웨어와 동일하다.

• 페이지 테이블(page table): 보호 비트들 혹은 유/무효 비트를 통해 특정 항목을 무효로 설정할 수 있어야 한다.
• 보조저장장치(Secondary memory): 페이징 스왑을 위해 스왑 공간(swap space)으로써 활용되어야 한다.

명령어 처리 재시작 (Instruction Restart)

요구 페이징을 위한 필수적인 사항으로 페이지 폴트 오류 처리 후 명령어 처리를 재시작할 수 있어야 한다. 페이지 폴트이 일어나면 실행중인 프로세스를 대기 큐(wait queue)에 보내서, paging in이 완료되면 wait queue에 신호를 줘서 프로세스의 명령어가 재시작하게 한다.

- 가용 프레임 리스트 _ Free Frame List

페이지 폴트가 발생하면 OS는 요청된 페이지를 보조저장장치에서 메인 메모리로 가져와야 하는데, 요청을 충족시키기 위해 가용 프레임 리스트를 관리하고 있다. 시스템이 시작되면 모든 가용 메모리가 가용 프레임 리스트에 넣어지고, 가용 프레임이 요청되면 가용 프레임 리스트의 크기가 줄어든다. 어느 시점에서 리스트는 0 혹은 특정 임계값으로 떨어지며 이후로 다시 채워진다.

OS는 일반적으로 zero-fill-on-demand라는 기법을 활용하여 가용 프레임 리스트를 관리한다. 할당되기 전에 0으로 모두 채워져 이전 내용이 지워진다. 프레임을 다시 할당하기 전에 프레임의 내용을 지워 주어야 한다. (보안 취약점이 될 수 있다.)

- 요구 페이징의 성능 _ Performance of Demand Paging

요구 페이징은 컴퓨터 시스템의 성능에 영향을 줄 수 있고, 이를 알아보기 위해 요구 페이지 메모리에 대한 실질 접근 시간(effective access time)을 계산할 수 있다. 페이지 폴트가 없으면 실질 접근 시간 = 메모리 접근 시간이다.

실질 접근 시간 = (1 - p) * ma + p * 페이지 폴트 시간

페이지 폴트의 확률이 p이고 (0 <= p < 1), 메모리 접근 시간은 ma(ns단위) 이다. 만약 평균 페이지 폴트 처리 시간이 8ms 이고 메모리 접근시간이 200ns라면

실질 접근 시간 = (1-p) * 200 + p * 8000000 = 200 + 7999800 * p

페이지 폴트율에 비례하게 된다. 1000번 중 한번 페이지 폴트가 발생하면 실제 접근 시간은 8.2마이크로 초로 요구 페이징 때문에 성능이 40배 느려진다고 할 수 있다.

쓰기 시 복사 _ Copy-on-Write

요구 페이징을 함으로 프로세스를 빠르게 시작할 수 있다. 그런데 fork() 시스템 콜을 통해 프로세스를 생성한다면 첫 요구 페이징도 생략할 수 있다. 앞서서 배운 fork()는 부모 프로세스의 페이지를 그대로 자식 프로세스에 복사하여 주소 공간을 구성하였다. 그런데 대부분의 자식은 곧 exec() 시스템 콜을 수행하여 덮어씌워버려 복사해온 페이지는 무쓸모가 된다. 그래서 부모의 페이지를 복사하는게 아닌 쓰기 시 복사(copy-on-write)를 사용할 수 있다. read할 때에는 굳이 복사하지 않고 부모의 페이지를 함께 사용하다가, write 작업이 이루어 지면 그 때 복사본 페이지를 만들어 자식 프로세스의 주소 공간에 사상시키는 것이다.

Linux, maxOS, BSD UNIX 등은 vfork()라는 시스템 콜을 제공하는데, 이는 쓰기 시 복사를 사용하지 않고 자식이 부모 주소 공간의 페이지를 변경할 수 있다. 이는 자식이 exec()를 하는 경우에 사용한다. 복사가 전혀 발생하지 않아 효율적이다.

페이지 교체 _ Page Replacement

시스템 메모리는 프로그램 페이지를 저장하는 용도로만 사용되는 것이 아니라 I/O 버퍼 등 다른 용도로도 사용된다. 프로세스가 실행되는 동안 페이지 폴트가 발생하였으나 메모리에서 페이지를 로드할 가용 프레임이 없는 경우가 발생할 수 있다. 이것을 메모리 과할당(over-allocating) 상태라고 한다. 이 때 메모리에서의 페이지 교체를 고려한다.

- 기본적인 페이지 교체 _ Basic Page Replacement

위의 요구 페이징에서의 과정에서 부분을 그대로 들고오면,

1. 비어 있는 프레임=가용 프레임(free frame)을 찾는다.
2. 보조저장장치에 있는 페이지를 해당 프레임으로 로드해준다. (OS가 free-frame list를 관리)
3. internal table이나 page table을 갱신, 메모리에 해당 페이지가 있다고 표시한다.

인데 이 루틴에서 가용 프레임을 찾는 부분이 페이지 교체를 포함하여 수정되어야 한다.

1. 빈 페이지 프레임을 찾는다.
   • 비어 있는 프레임이 있다면 그것을 사용한다.
   • 빈 프레임이 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동시킨다.
2. 희생될 페이지를 보조저장장치에 기록하고(필요한 경우), 관련 테이블을 수정한다.
3. 프레임에 새 페이지를 읽어오고 테이블을 수정한다.
4. 페이지 교체(page replacement) 가 완료되면 프로세스 계속..

요구 페이징 시스템은 두 가지 중요한 문제가 있다.

• 프레임 할당(Frame-allocation) 알고리즘: 각 프로세스에 얼마나 프레임을 할당해야 하는가?
• 페이지 교체(Page-replacement) 알고리즘: 어떤 페이지를 교체해야 하는가?

보조저장장치 I/O가 매우 많은 비용이 들고, 요구 페이징 방법이 개선되면 시스템 전체 성능이 향상된다. 여기서 페이지 교체 알고리즘의 성능은 페이지 폴트의 비율에 반비례하므로, 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 폴트 횟수를 계산하여 평가할 수 있다. 이런 메모리 주소의 나열을 참조열(reference string) 이라 부른다.

참조열 : 프로세서가 논리 주소를 통해서 어떤 주소를 요청하면 메모리의 주소들은 페이지 단위로 가져오는데, 이 때 페이지 번호가 연속되어 나타나면 페이지 폴트가 일어나지 않는다고 한다. 이는 메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문이란다. 프로세서의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 것이다.

다음과 같은 주소 열에서,

0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103, 0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105

이 열은 다음과 같은 참조열로 줄일 수 있다.

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

아래 페이지 교체 방법들을 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 참조 열로 알아보도록 하자.

- FIFO 페이지 교체 _ FIFO Page Replacement

가장 먼저 온 페이지를 먼저 내보내는 것, 자주 들어온 만큼 심플하다. 허나 성능이 항상 좋지는 않다. 교체된 페이지가 더 사용되지 않는 초기화 모듈이면 다행이나, 활발하게 사용되고 있는, 자주 사용되는 변수를 포함한 페이지일 경우 페이지 폴트율을 높이고 실행 속도를 떨어뜨린다.

페이지 폴트 15번

대개 프레임을 많이 주면 페이지 폴트율이 낮아지나, 항상 그런 것은 아니다. 이러한 현상을 벨라디의 모순 (Belady’s Anomaly)이라 한다. 프레임을 더 주는데도 page-fault가 더 증가하는 현상이다.

1,2,3,4,1,2,5,1,2,3,4,5 의 참조열에서 4개의 프레임의 경우 10번, 3개의 프레임의 경우 9번 발생한다.

- 최적 페이지 교체 _ Optimal Page Replacement

벨라디의 모순이 가져온 결과 중 하나로 최적 교체 정책에 대한 탐색이 이루어졌는데, 모든 알고리즘 중 가장 낮은 페이지 폴트율을 보이며 모순이 발생하지 않는 것으로 OPT 또는 MIN으로 불렸다. 이는 앞으로 사용하지 않을 것 같은 혹은 먼 시간 뒤에 사용될 거 같은 페이지를 내보내는 것을 의미한다.

페이지 폴트 9번 (처음 3개의 빈공간 채우는 폴트를 제외하면 FIFO보다 2배 더 좋다)

그러나 이 알고리즘의 실제 구현은 어렵다. 프로세스가 앞으로 메모리 참조를 어떻게 할 것인지 미리 알아야 하기 때문에.. 주로 연구 목적으로, 알고리즘의 페이지 교체 효율을 비교하기 위한 기준으로 사용된다.

- LRU 페이지 교체 _ LRU Page Replacement

LRU (Least Recently Used) 알고리즘은 최적 알고리즘의 근사 개념이다. OPT가 페이지가 사용될 시간을 이용한다면, 이것은 최근의 과거를 미래의 근사치로 보아 가장 오래 사용되지 않은 페이지를 교체하는 것이다. CPU 스케줄링에서 다루었던 최단 작업 우선 스케줄링 SJF (Shortest Job First)과 거의 유사하다. 효율이 좋고 자주 사용된다.

페이지 폴트 12번

LRU를 구현하기 위해서 프레임들을 최근 사용된 시간 순서로 파악할 수 있어야 하는데, 두 가지의 구현 방법이 있다.

• 계수기(counters): 간단한 방법으로, 각 페이지 항목에 사용 시간 필드를 넣고 CPU에 논리적 시계, 카운터를 추가한다. 메모리에 접근할 때마다 시간이 증가한다.
• 스택(stack): 페이지 번호의 스택을 유지하는 방법으로 페이지가 참조될 때마다 스택의 꼭대기는 항상 가장 최근에 사용된 페이지를 의미하게 된다. 반대로 바닥은 오랫동안 사용되지 않은 페이지..

최적 교체 처럼 LRU 교체도 Belady의 모순을 야기하지 않는다. LRU는 스택을 사용한 알고리즘으로, 이를 소프트웨어적으로 처리하려면 메모리 참조 때마다 인터럽트를 사용하게 되므로 메모리 참조 속도가 느려지고 프로세스의 속도를 저하하므로 하드웨어 지원이 필요하다.

LRU 근사 페이지 교체 _ LRU-Approximation Page Replacement

많은 OS가 LRU 지원을 위해 참조 비트(reference bit)를 제공해준다. 참조 비트는 페이지 테이블의 각 항목되 대응된다.

• 부가적 참조 비트 알고리즘 : 8비트의 참조 비트를 할당한다. 최근 8구간 동안 페이지의 사용 기록을 담고 있다. 시프트 레지스터(shift register)로 가장 작은 수를 갖는 페이지가 LRU 페이지가 되어 이를 교체한다.

• 2차 기회 알고리즘 (Second-Chance Algorithm): FIFO를 기반으로 하여 참조 비트를 사용한다. 선택된 페이지의 참조 비트가 0이면 바로 페이지 교체를 수행사고, 어딘가에서 참조되어 있어서 1이라면 FIFO를 이용하여 다음 페이지를 선택한다. 모든 페이지가 한번씩 참조되었으면 그냥 FIFO와 같다.

• 개선된 2차 기회 알고리즘: 변경 비트라고 불리는 1비트를 더 준다. 변경 비트를 활용하여, 네 가지 등급을 준다.

  1. (0,0) : 최근에 사용되지도 변경되지도 않았다 - 교체하기 가장 좋다.
  2. (0,1) : 최근에 사용되지 않았지만 변경은 되었다 - 이 페이지를 뺏으려면 디스크에 기록해야되므로 일단은 교체에 적합하지 않다.
  3. (1,0) : 최근에 사용되었으나 변경되지 않았다 - 곧 다시 사용될 가능성이 높다.
  4. (1,1) : 최근에 사용되고 변경도 되었다 - 곧 다시 사용될 것이며 뺏으려면 디스크에 기록해야한다. 각 페이지는 4등급 중 하나에 속하여 낮은 등급을 가지며 처음 만난 페이지를 교체한다. I/O 횟수를 줄이기 위함을 고려한다.

     낮은 등급을 잘 모르겠다. 1/3/4/2 순으로 높은 등급인 걸까?

프레임의 할당 _ Allocation of Frames

여러 개의 프로세스들에 제한된 가용 메모리를 어떻게 할당할 것인가에 대한 문제이다. 모두가 가용 프레임 리스트에 있을 때 사용자 프로세스들이 실행을 시작하면 일련의 페이지 폴트를 발생시키며, 가용 페이지가 없어지면 이미 사용한 페이지 중 하나를 선택해 페이지 교체를 한다.

n개의 프로세스에 m개의 프레임을 분할하는 방법으로는

• 균등 할당(Equal allocation): 모든 프로세스에게 같은 수의 프레임을 할당한다. 나누어 떨어지지 않으면 나머지는 가용 프레임 버퍼 저장소로 사용한다.
• 비례 할당(Proprtional allocation): 프로세스 사이즈가 큰 경우에게 더 많이 할당한다.

다수의 프로세스가 프레임 할당을 위해 경쟁하는 환경에서 교체 희생자를 찾기 위한 것으로 아래와 같은 방법이 있다.

• 전역 교체(Global replacement): 교체할 프레임을 모든 프레임을 대상으로 찾는 경우로 우선순위가 낮은 프로세스를 희생시킬 수 있다.
• 지역 교체(Local replacement): 각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 찾는 경우로 각 프로세스에게 할당된 프레임의 수는 변하지 않는다.

스래싱 _ Thrashing

프로세스에 충분한 프레임이 없는 경우 페이지 폴트를 일으키는데 페이지 교체해봤자 프레임이 부족하므로 어차피 금방 페이지 폴트가 발생, 과도한 페이징 작업이 발생한다. 이를 스래싱(thrashing)이라 한다. 요구 페이징을 사용하면서 가상메모리를 이용할 때, 실제 메모리보다 논리적으로 큰 프로그램을 다룰 수 있었는데 프레임이 부족하면, 이 경우 페이징 작업 즉 스왑인, 스왑아웃이 반복되며 CPU 이용률이 떨어진다.

다중 프로그래밍의 정도에 따라 CPU 사용량이 올라가는데, 어느 순간이 되면 스래싱이 발생, CPU 이용률이 떨어진다.

스래싱을 막기 위한 모델들이 있다.

- 작업 집합 모델 _ Working-Set Model

지역성을 토대로 하는 모델이다. 개념적으로 창(작업 집합 window)를 가지고 있다. 기본 아이디어는 최근 델타(working-set window)만큼의 페이지 참조를 관찰하는 것이다. 한 프로세스가 최근 델타 번 페이지를 참조하였으면 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합이라고 하는데, 페이지가 자주 사용되면 작업 집합에 포함되고 페이지가 더 사용되지 않으면 마지막 참조로부터 델타만큼의 페이지 참조 후 작업 집합에서 제외된다. 이 작업집합은 프로그램 지역성의 근사값이 된다.

델타 밖에 있는 페이지를 희생양으로 삼으면 페이지 폴트가 줄어든다는 결론이 나온다고 한다.

- 페이지 폴트 빈도 _ Page-Fault Frequency, PFF

작업 집합 모델은 선 페이징 시에는 유용하지만 스래싱을 조절하는건 약간 애매하다고 한다. PFF 방식은 페이지 폴트율의 상한과 하한을 정해 놓고 상한을 넘으면 프로세스에 프레임을 더주고, 하한보다 낮아지면 프레임 수를 줄이며 조절, 스래싱을 방지한다.

하나하나 보면 간단한 개념 같은데, 범위를 가지고 살펴보면 너무 알아먹기 힘들다. 책에서 요약하지 못한 부분도 더러 있는데 천천히 살펴봐야지…