[OS] 6. 가상메모리

1. 가상메모리

다중 프로그래밍을 실현하기 위해서는 다수의 프로세스들이 메모리 위에 올라와 있어야 한다. 하지만 메모리의 용량은 한정되어있고, 다중프로그래밍을 하려면 메모리 용량이 부족하기 마련이다.

 가상메모리는 이런상황을 대비해 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다. 이 기법의 장점 중 하나는 사용자 프로그램이 물리 메모리보다 커져도 된다는 점이다. 가상메모리는 사용자 관점의 논리 메모리와 물리 메모리의를 분리시켜 주 메모리를 균일한 크기의 저장공간으로 구성된 엄청나게 큰 배열로 추상화 시켜준다.

 이번 포스팅에는 가상메모리를 구현하는 요구페이징에 대해서 알아보는 시간을 갖겠다.

 

- 가상메모리의 필요성

• 잘 발생하지 않는(거의 실행하지 않는) 오류 상황을 처리하는 코드가 종종 존재한다.
• 어떤 옵션, 기능은 거의 사용되지 않는다. ex) 정부 컴퓨터의 현금영수증 정산 루틴은 연말연시에만 사용된다.
• 전체 프로그램이 필요한 경우 그 모든 부분이 동시에 요구되지 않는다.
• 메인 메모리보다 큰 프로그램을 사용하는 경우

- 가상메모리의 이점

• 물리메모리 크기의 제약을 벗어날 수 있다.
• 더 많은 프로그램을 사용할 수 있다. (메모리공간의 크기가 사실상 실제보다 매우 크기 때문)
• 스와팡(swapping) 횟수가 줄어 프로그램들 실행속도가 증가된다.(프로그램 전체를 올리고 내릴 필요가 없기 때문이다.)

2. 요구페이징

프로그램을 메모리에 적재할 때 필요한 부분들만 적재하는 전략이다. 이후 다른 부분이 필요하다면 필요한 시점에 적재를 하게 된다. 요구페이징 기법은 필요한 프로세스를 메모리에 불러오면서 프로세스를 보조메모리에 저장한다는 점에서 스와핑(swapping) 기법과 유사하다. 하지만 프로세스 전체를 불러오지 않고 필요한 부분만 적재한다는 점에서 게으른 스와퍼(lazy swapper)라고 한다. 즉, 프로세스를 하나의 연속된 공간이라고 보지 않고 페이지들의 연속으로 본다는 것이다.

 스와퍼와 페이저의 차이점은 프로세스를 관리하는지 페이지를 관리하는지로 나뉘게된다.

 

1) 요구페이징 과정

 기본적으로 페이저는 swap in, swap out을 하기전에 프로세스 전체를 확인하지 않고, 사용할 프로세스만 swap in하게 된다. 이에 따라 시간과 공간의 낭비를 줄일 수 있다.

 이런 절차를 위해서 해당 프로세스의 페이지가 메모리에 올라 왔는지를 관리해야 한다. 이는 페이지 테이블의 유효/무효비트를 통해 충족시킬 수 있다.

 

위와 같은 상황에서 A, C, F는 이미 페이지 테이블 내에 존재하여 이 페이지들에 접근 할 경우 유/무효 비트가 유효인 v(valid)로 되어 있기 때문에 정상적으로 사용할 수 있다. 하지만 B, D, F 의 경우 무효인 i(invalid)로 설정되어 있기때문에 페이지가 메모리에 올라오지 않은 페이지 부재 트랩(page-fault trap)을 발생시킨다(무효비트로 설정되어 있을 경우 디스크에 없을 수 도 있음). 페이지 부재 트랩이 발생하면 보조 메모리에 있는 페이지를 swap in 시켜야한다. 이 과정을 요구에 따라 페이지를 적재한다는 의미의 요구페이징이라고 한다.

 

2) 페이지 부재 처리과정

페이지 부재를 처리하는 과정은 다음과 같다.

 

1. 필요한 부분이 물리메모리에 적재되어 있는지 페이지테이블의 유/무효 비트를 통해 확인한다.
2. 무효비트(i)로 표시되어있다면 페이지 부재 트랩을 걸어 디스크에 존재하지 않는 무효한 참조이라면 프로세스를 종료한다.
3. 만일 디스크에 존재하지만 메모리에 올라오지 않은 참조라면 디스크에서 원하는 부분을 찾는다.
4. 물리 메모리에서 자유프레임(메모리를 할당 할 수 있는 부분)을 찾고, 디스크에서 찾은 페이지를 해당 자유 프레임에 읽어들인다.
5. 디스크에서 물리 메모리로 페이지 적재가 완료되면 페이지 테이블을 갱신한다.(i->v, 해당 자유 프레임 번호 등..)
6. 트랩에 의해 중단되었던 명령어를 다시 수행한다. 이후로는 해당 페이지에 항상 접근 가능하다.

 - 순수 요구페이징

극단적인 경우에는 페이지가 메모리에 하나도 없는 상태에서 운영체제가 명령 포인터 값을 프로세스의 첫 명령어로 설정하는 순간 요구페이징을 하며 프로세스 실행을 할 수 있다. 즉, 처음 부터 필요한 모든 페이지가 메모리에 적재될 때까지 페이지 부재를 일으키게 되는데 이것을 순수 요구 페이징이라고 한다.

 

요구페이징을 위한 필수적인 조건은 페이지 부재 오류를 마치고 나서 명령어를 다시 시작할 수 있어야 하는 것이다. 

 어떤 기억 공간 참조 시에도 페이지 부재가 일어날 수 있다.

만약 명령 인출 시에 발생했다면 명령을 메모리로 읽어 온 후 다시 수행을 시도, 오퍼랜드를 인출하는 동안 발생했다면 나중에 그 명령어를 다시 읽어오고 해독하여 오퍼랜드를 인출하면 된다.

만일  매우 긴 명령을 실행하고 결과를 저장하는 과정에서 페이지 부재가 발생할 경우 마지막 페이지를 불러온 후 다시 명령어를 실행해야할 경우가 발생할 수 있다. 

 

이에 대한 해결책은 두가지가 있는데

 먼저 마이크로 코드로 양 블록의 두 끝을 계산하여 겹치지 않는 것을 확인한 후 접근을 시도하는 것이다. 만약 페이지 부재가 발생될 가능성이 있다면 어떤 것도 수정하기 전에 페이지 부재를 발생시킨다.

 다른 해결법은 이동에 의해 이전의 내용이 지워질 기억장소의 값을 보존하는 임시 레지스터들을 사용하는 것이다. 페이지 부재에서 돌아왔을 경우 기억공간을 다시 복구할 수 있다.

 

3. 쓰기 시 복사

 순수요구 페이징을 할 경우 fork()_ 프로세스 복사(child 프로세스만들기) 시스템 호출을 통해 프로세스를 생성할 때는 페이지 공유와 비슷한 기법으로 첫 요구 페이징 조차 생략할 수 있다. 또한, 새롭게 할당되어야 하는 페이지의 수도 최소화 할 수 있다.

 

 fork()를 실행한 후 자식 프로세스는 보통 exec() 시스템 호출을 하여 부모로 부터 복사한 페이지들은 다 쓸모가 없어지게 된다. 따라서 부모페이지들을 모두 복사하는 대신 쓰기 시 복사(copy- on write) 방식을 사용할 수 있다. 처음에는 자식 프로세스가 부모의 페이지를 같이 쓰다가 둘 중 공유 페이지에 쓰기를 할 때 복사하겠다는 것이다.

 

위 그림에서 페이지 A, B, C를 같이 쓰고 있다가 둘중 한 프로세스가 C페이지를 사용하기 위해 C를 복사한 것이다. 이것을 쓰기 시 복사 라고 한다.

4. 페이지 교체 알고리즘

  페이지 부재가 발생했을 시 메인메모리에 자유프레임이 없다면 메모리에 사용중인 페이지를 swap out 해야한다. 이때 어떤 페이지를 swap out 할지 정하는 알고리즘이 페이지 교체 알고리즘이다. 즉, 페이지 부재 처리과정의 4번에서 자유페이지가 없을 때 희생될 프레임을 선정하는 방법이다.

 

페이지를 교체할 경우 기존의 페이지를 디스크에 저장하면서 한번 디스크에 있는 내용을 프레임에 올리는 데 한번 총 2번 접근을 해야하는데 변경비트를 따로 만들어 변경이 없는 페이지의 경우 다시 디스크에 저장을 하지 않아도 되도록 처리하면 1회의 디스크 접근만으로 페이지를 교체 할 수 있다.

 

페이지 교체 알고리즘의종류는 다음과 같다.

1) FIFO 페이지 교체

선입선출의 페이지 교체로 메모리에 올라온지 가장 오래된 페이지를 디스크로 내리는 알고리즘이다.

※ FIFO 알고리즘은 대체적으로 프레임수가 증가할 수록 페이지 부재 횟수가 감소한다(공룡책 9.4절 그림 9.11). 하지만 해당 프로세스에 할당한 프레임이 더 늘어 났을 때 페이지 부재 횟수가 오히려 증가하는 현상이 발생할 수 있는데 이것을 Belady의 모순이라고 한다.(공룡책 9.4절 그림 9.13)

2) 최적페이지 교체

최적 페이지 교체는 앞으로 가장 오래동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 이는 가장 낮은 페이지 부재율을 보장한다. 하지만 사실상 구현이 어려운 알고리즘이다. 앞으로 어떤 메모리가 쓰일지 미리 알아야 하기 때문이다. 따라서 연구목적으로 사용한다.

 

3) LRU 페이지 교체(Least- Recently-Used)

최근 과거를 미래의 근사치로 보아 가장 오래동안 사용되지 않은 페이지를 희생될 페이지로 선정하는 방법이다. LRU에서는 페이지 별 가장 마지막에 사용한 시간을 기록하여 그 시간이 가장 오래된 페이지를 선택한다.

 

4) LRU 근사 페이지 교체

LRU를 지원할 수 있는 하드웨어는 거의 없지만 많은 시스템들은 참조빝트 형태로 어느정도 지원을 하고 있다. LRU의 변형이라고 볼수 있는 알고리즘은 다음과 같다.

[1] 부가적 참조비트 알고리즘

 각 페이지에 대해 8비트의 참조비트를 할당하고 사용될 때 1을 왼쪽에 추가하고 한 구간이 지나가면 모든 페이지의 참조비트를 오른쪽으로 쉬프트 한다.

 만일 이번 구간에서 사용이 되었다면 참조비트는 10000000 일것이고 이전 구간에서 사용되었다면 01000000의 식으로 오른쪽으로 쉬프트 되는 것이다.

 따라서 이 참조비트의 비교를 가지고 더 작은 값을 가지는 페이지를 교체하는 것이다.

[2] 이차기회 알고리즘

 부가적 참조비트알고리즘 방법인데 1비트를 부여하고, 0이면 교체, 1이면 0으로 만들고 교체하는 것이다. 또한, 구간에 따라 비트를 변경시키는 것이 아니라 페이지별 참조비트로 순환 큐를 만들어 참조비트가 0인 페이지를 찾는다. 만일 찾은 값의 참조비트가 1일경우 0으로 바꾸며 0인 페이지를 찾는다. 최악의 경우 모든 페이지의 참조비트가 1일 경우에는 한바퀴를 순환 한 후 FIFO와 같은 알고리즘이 된다.

[3] 개선된 이차기회 알고리즘

 참조비트를 2개 부여하며 아래와 같이 바꾼다.

1. (0, 0) 최근에 사용, 변경 된적없음 -> 교체하기 좋은 페이지
2. (0, 1) 최근에 사용되지 않았지만 변경은 된 경우 ->
3. (1, 0) 최근에 사용은 되었으나 변경은 되지 않은 경우 -> 다시 사용될 가능성이 높다.
4. (1, 1) 최근에 사용되었으며 변경된 경우 -> 다시사용될 것이며 뺏으려면 디스크에 내용을 기록해야한다.

위 네가지의 등급에 따라 교체될 페이지를 찾는다. 이는 큐를 여러번 순환 할 수 있다.

 

5) 계수기반 페이지교체(Counting-Based)

 페이지를 참조할 때마다 계수를 하며 교체의 척도로 사용한다.

• LFU(least frequently used)
   참조 횟수가 가장 작은 페이지를 교체하는 방법이다. 이 방법에는 문제점이 있는데 초기단계에서 일정 페이지를 집중적으로 사용하지만 그 후로는 더이상 사용하지 않더라도 메모리에 계속 머무를 수 있을 때 한계가 있다. 시간이 지남에 따라 그 참조횟수를 줄이며 영향력을 감소시키는 해결책이 있다.
• MFU(least frequently used)
   참조 횟수가 가장 많은 페이지를 교체하는 방법이다. 가장 작은 참조 횟수를 가진 페이지가 가장 최근에 참조된 것이고 앞으로 많이 사용될 것이라는 점에서 LFU와 반대되는 알고리즘이다.

5. 쓰레싱(Thrashing)

프레임을 충분히 할당받지 못한 프로세스는 페이지 부재가 빠르게 발생할 것이다. 이때 메모리에는 활발한 페이지 들로 구성되어 있다면 swap-out당하는 페이지는 머지않아 다시 적재되야 할 것이고 그 페이지를 적재하기위해서는 또 다른 활발한 페이지를 내려야 할 것 이다. 이렇게 발생하는 과도한 페이징 작업을 스레싱이라고 부른다.

 

1) 원인

1.  운영체제는 CPU의 이용률을 감시한다. 만약 CPU 이용률이 너무 낮아지면 새로운 프로세스를 시스템에 추가해 다중 프로그래밍 정도를 높인다. 
2. 이때 전역(메모리 전체에 대해) 페이지 교체 알고리즘을 사용하여 어떤 프로세스의 페이지인지 고려하지 않고 교체한다.
3. 어떤 프로세스가 새로운 실행단계로 진입하여 더 많은 프레임이 필요해 졌을 때 다른 프로세스로 부터 프레임을 가져오게 될 것이다.
4. 이때 교체된 프레임에 있던 프로세스가 해당 프로세스에서 필요한 것이었다면 해당 프로세스 역시 다른 프로세스로 부터 프레임을 가져올 것이다.
5. 이런 swap-out, swap-in을 위해 페이징 장치에 대한 큐잉이 진행되며 준비완료큐는 비게 되고 CPU이용률을 떨어지게된다.
6. 1번으로 돌아가 새로운 프로세스를 추가하며 악순환된다.

쓰레싱을 제한할 수 있는 방법은 다음과 같다.

 

[1] 지역 교환 알고리즘

•  다른 프로세스로 부터 프레임을 뺏을 수 없고, 다른 프로세스는쓰레싱으로 부터 자유로울 수 있다.
• 그러나 쓰레싱이 시작되면 디스크 큐에서 대부분의 시간을 보내게 되어 쓰레싱과 관련 없던 프로세스들도 디스크 입/출력 시간을 많이 소모하게 된다.
• 따라서 최소한의 프레임 수를 보장하는 방법으로 수정이 필요하다. 최소의 수는 지역성 모델을 바탕으로 실제 사용 프레임 수를 참조하는 것이다.

[2] 워킹셋(Working Set)

• 프로세스가 많이 참조하는 페이지 집합을 메모리 공간에서 계쏙 상주시켜 빈번한 페이지 교체 현상을 줄이는 방법