01 가상 메모리의 이해
- 1 가상 메모리의 개념과 원리
- 2 가상 주소와 테이블 항목
02 요구 페이징
03 페이지 대치 알고리즘
04 프레임 할당 알고리즘
- 1 프레임 할당 알고리즘의 필요성
- 2 균일, 비례 프레임 할당 알고리즘
05 메모리를 관리하는 프로세스 적재 정책
06 메모리 관리와 관련된 기타 이슈

8. 가상 메모리

IT COOK BOOK 운영체제 (개정 3판, 구현회 저, 한빛 아카데미) 를 정리한 내용입니다.

01 가상 메모리의 이해

사용자와 논리적 주소를 물리적으로 분리해 사용자가 메인 메모리 용량을 초과한 데이터를 보조 기억장치에 할당 후, 주소를 지정해 메모리를 제한 없이 사용할 수 있도록 하는 것

가상 주소(논리적 주소, 프로그램 주소)는 실행 중인 프로그램이 직접 참조하며, 이 가상 주소를 이용해 물리적 주소를 얻어내는 과정을 매핑(Mapping)이라 하며, 성능에 큰 영향을 미친다.

:green_circle: PROS

+ 가상 메모리 주소를 이용해 다중 프로그래밍 환경 등에서 메인 메모리보다 더 큰 저장 공간을 제공할 수 있다.
+ 프로세스의 전체를 동시에 적재하지 않아도 스왑과 캐시를 통해 실행 가능
+ 중첩을 고려하지 않고 더욱 쉽게 프로그래밍 가능
+ 프로세서 이용률과 처리율 향상, 단 응답시간과 반환 시간은 향상되지 않음.

:orange_circle: CONS

- 메모리와 디스크 사이의 이동량과 스와핑 증가와 이를 위한 공간 필요
- 페이지 적재 및 복귀를 위한 알고리즘 구현 필요
- 페이지 부재 시 처리를 위한 알고리즘 구현 필요
- 페이지 부재가 잦을 경우 심각한 성능 저하

1 가상 메모리의 개념과 원리

실제 메모리 사용 시, 프로세스는 다음과 같은 방식으로 사용하므로, 메모리를 동시에 적재할 필요 없다.

모든 메모리를 동시에 사용하지 않는다.
예외 처리, 오류 처리 코드는 자주 혹은 전혀 사용하지 않음
배열, 리스트, 테이블 등은 실제 사용한 크기보다 넉넉히 크게 사용한다.
문서 편집기의 복사하기, 붙이기, 잘라내기, 삽입하기 메뉴는 선택한 메뉴 하나만 메인 메모리에 적재해도 됨
라인 : 메인 메모리와 캐시 사이에서 데이터 이동시 캐시의 공간 지역성을 활용하기 위해, 캐쉬는 라인 단위의 데이터를 가져오게 된다.

위 그림처럼 보조 장치에 있는 데이터는 논리적 주소 공간에 할당되며, 데이터가 불려질 경우, 메인 메모리로 이동된다.

가상 주소를 물리적 주소로 매핑하는 과정은 위 그림처럼 표시한다.

매핑 방법 중 동적 주소 변환(DAT, Dynamic Address Translation)을 나타낸 그림.
- 가상 주소가 연속적으로 배치된다고 하여, 메인 메모리에서도 연속적일 필요가 없어(인위적 연속성), 사용 시, 데이터의 적재 위치를 고려하지 않아, 프로그래밍이 쉽다.

2단계 메모리 관리 방법 : 2차 기억 장치에 저장된 프로세스를 실행하려면 사용할 코드와 데이터를 모두 메인 메모리에 옮겨야 하며, 이를 통해 여러 사용자가 메모리를 효율적으로 공유 가능

2 가상 주소와 테이블 항목

페이지는 디스크에서 메인 메모리로 블록 단위로 옮겨져 페이지 프레임에 적재됨.
이때 페이지 프레임은 가상 페이지 크기와 동일하며, 어떠한 페이지든지 들어갈 수 있다.
이렇게 가상주소와 물리적 위치는 페이지 테이블 항목을 통해 매핑되게 됨.

페이징 시스템에서 가상 주소는 아래 그림과 같이 구성됨.

가상 페이지 번호(p)
페이지 오프셋(d)

예시
32 비트의 가상 주소, 4KB($2^{12}$) 크기의 페이지일 경우,

페이지 크기 만큼의 오프셋이 필요하므로 12 bit는 페이지 오프셋
32비트 중 나머지 중 20 bit로 가상 페이지 번호 (20bit) = 총 프레임 $2^{20}$(1048576)개로 구성
예를 들어, 가상 주소가 0x009B18A0일 경우, 가상 페이지 번호는 2481, 페이지 오프셋은 2208

가상 주소 변환을 위한 테이블 항목은 위 그림과 같다.
보통 한 항목에 32비트이며, 세부적으로 메인 메모리 저장 여부를 표시하는 제어 비트와 페이지 프레임 번호 비트로 구성됨.

위 그림은 가상 주소를 물리적 주소로 매핑하는 과정이다.

가상 주소 페이지 번호 0x2로 페이지 테이블 항목 찾음
페이지 테이블 항목에서 프레임 번호 0x8을 얻음
프레임 번호와 가상 주소의 오프셋을 결합해 물리적 주소 획득
프레임 번호 $\times$ 페이지 크기 + 오프셋 = 데이터의 물리적 위치

02 요구 페이징

1 요구 페이징의 개념

요구 페이징은 프로세스 시작 시, 디스크에서 메인 메모리로 모든 프로세스 데이터를 스와핑하는 순수 스와핑과 달리, 실행 중인 프로세스들의 요구 페이지만 반입한다.
이를 지연 기술 또는 지연 스와퍼(lazy swapper)이라 하며, 마찬가지로 페이지 테이블을 유지한다.

주로 가상 메모리에서 많이 사용하며, 프로그램들이 모듈을 순차적으로 사용하는 특징을 이용한다.

요구 페이징의 페이지 테이블은 해당 페이지가 메모리에 적재되어 있는 지를 1과 0으로 표기하는 타당-비타당 비트가 추가로 존재한다.

1은 유효, 0은 유효하지 않은 페이지이다.

위 그림의 경우 페이지 A,C,F는 메인 메모리에 존재하므로 타당 비트가 1이며, 나머지는 0이다.

2 페이지 부재

만약, 프로세스가 요구한 페이지의 타당 비트가 1(=메인 메모리에 적재 중)일 경우, 신속히 사용할 수 있다.
하지만 페이지가 메모리에 적재되어 있지 않을 경우 이를 페이지 부재(page fault)라고 하며, 운영체제에 하드웨어가 트랩을 걸게 되며, 아래 그림과 같은 과정을 거쳐 처리한다.

프로세스 B가 가상 주소의 페이지 번호가 1인 가상 페이지에 액세스
페이지 테이블의 타당-비타당 비트 검사, 1일 경우 명령 처리, 0일 경우 페이지 부재
페이지 부재로 트랩이 발생하여 제어권이 운영체제로 넘김, 운영체제는 해당 페이지를 디스크에서 가져오기로 함
메모리에서 빈 프레임 하나 선택, 없을 경우 나중에 배울 교체 혹은 큐잉 필요
할당된 프레임에 요구된 페이지를 디스크에 가져오며, 그 동안 프로세서는 다른 프로세스의 동작 스케줄링
해당 페이지를 디스크에서 메모리로 가져옴
요구된 페이지가 메모리에 적재 완료, 페이지 테이블 항목의 타당 비트 설정
주소 트랩을 발생시켜 인터럽트 명령어 재시작

🟢 PROS
+ 다중 프로그래밍의 정도를 증가, 액세스하지 않을 시 적재하지 않으므로 메모리 효율적
+ 초기 시작 시 프로그램의 적재 지연 감소, 디스크 오버헤드 감소
+ 적재된 페이지 중 하나를 수정할 때까지 페이지들은 여러 프로그램이 공유하므로 쓰기복사(COW, Copy-On-Write) 기술로 더 많은 자원을 저장할 수 있다.
+ 프로그램을 실행할 충분한 메모리가 없는 시스템에서도 대용량 프로그램 실행 가능
+ 프로그래머가 중첩 구조보다 더욱 쉽게 구현 가능

:orange_circle: CONS
- 나중에 배울 프리 페이징(미리 페이지 가져옴)에 비해 약간의 초기 지연 발생
- 낮은 비용, 낮은 성능의 시스템에서는 페이지 대체를 지원하기 위한 하드웨어 없음
- 페이지 교체 알고리즘을 포함하는 메모리 관리가 복잡
- 페이지 액세스 시간은 페이지 부재로 인해 예측이 어려움

쓰기복사(COW, Copy-On-Write)

여러 작업이 메모리나 디스크에 저장된 동일한 자원을 사용 시, 별도의 복사본을 만들지 않고 동일한 자원 포인터를 부여할 수 있다.
공유 페이지와 다른 점은 쓰기복사는 읽기 전용 뿐만 아니라 쓰기 작업이 가능하다는 점이다.

또한 다중 스레드 시스템의 잠금을 이용한 방법 대신 내부 참조 카운터의 증가와 감소를 이용해 구현(참조를 아무도 안하면(= 참조 카운터가 0이면) 안전히 해제 가능)

:green_circle: PROS
+ 따라서 효율적인 메모리 사용과 쓰기 작업이 동시에 가능
+ 동일한 자원을 사용하는 프로세스 간의 메모리 공유 가능
+ 메모리를 불연속적으로 사용 가능

:orange_circle: CONS
- 수정이 많아지면 메모리 사용량 증가
- 커널 수준 쓰기 복사를 구현하기 복잡함
- 파일 디스크상 연속성(인접성)을 차단, 단편화로 인한 디스크 탐색량 증가

여러 운영체제에서 사용 중이며, 데이터베이스의 스냅샷(snapshot) 등에도 이용

위의 그림은 쓰기 복사의 예시이다.

각 논리 파일 블록 3곳($L_0, L_1, L_2$)은 물리적 비연속 블록 3곳($P_0, P_2, P_3$)을 가리키고 있다.
이때, $L_1$이 새로운 쓰기를 실행하였다.
새로운 내용을 가진 $P_2$은 이를 빈 새로운 물리 블록 $P_6$에 할당한다.
논리 파일 블록 $L_2$가 가르키는 번호를 $P_6$로 옮긴다.
- 만약 $P_2$를 참조하던 다른 프로세스는 아무변화 없이 사용할 수 있다.

3 페이지 성능

페이지 부재 확률을 $p$, 메모리 액세스 시간을 MAT(Memory Access Time, 보통 10~200나노초)이라고 할때 유효 액세스 시간(EAT, Effective Access Time)은 다음과 같이 계산된다.

\[페이지\ 부재\ 확률: 0 \leq p \leq 1 \\ 유효\ 액세스\ 시간 = (페이지\ 적중\ 확률) \times MAT + (페이지\ 부재\ 확률) \times (페이지\ 부재\ 해결\ 시간)\\ = (1-p)\times MAT + p \times (페이지\ 부재\ 해결\ 시간)\]

페이지 부재 해결 시간은 크게 다음 항목들의 합이다.

인터럽트 처리 시간 : 아래에 포함
프로세스 재시작 시간 : 인터럽트 처리시간을 합쳐도 명령어 수백개, 1~100 마이크로초
페이지 교체 시간 : 디스크의 헤드 이동에 따른 탐색 시간(5ms)+ 지연시간(3ms)+ 전송시간(0.05ms) = 약 8밀리초($10^{-3}$)

즉, 페이지 부채를 처리하는데는, 인터럽트 처리와 프로세스 재시작은 오래걸리지 않지만, 페이지 교체 시간이 가장 많이 차지한다.
이를 이용해 유효 액세스 시간을 계산하면 $200+p\times7,999,800$이다.

액세스 1000개 중 하나의 페이지 부채만 생겨도 40배의 시간이 지체되며, 10퍼센트 정도의 성능만 희생 시키려면 페이지 부채는 399,990번 중 한번만 발생해야 한다.

즉, 페이지 부재를 적게 일으키기 위한 알고리즘과 정책이 필요하다.

4 페이지 성능을 높이는 페이지 대치

만약, 프로세스들이 요구하는 페이지가 갑자기 늘어나 메모리의 프레임이 부족해지게 되면 페이지 대치로 해결.

페이지 대치는 페이지 부재 발생 시, 메인 메모리에 있는 사용하지 않는 페이지를 새로운 페이지로 바꾸며, 페이지 대치를 담당하는 핸들러(서비스 루틴)은 프로그램에게 이를 통보한다.

페이지 대치 과정은 위 그림과 같다.

페이지 부재로 발생한 페이지 대치 과정은 페이지 2개가 스왑 인, 아웃하는 과정이므로, 액세스 시간이 증가, 시스템에 부담
하지만 위의 CONs을 수정된 비트를 활용해 감소 가능하며, 보조기억장치를 활용할 수 있게 된다.

03 페이지 대치 알고리즘

1 페이지 부재와 프레임 수

메인 메모리에 프레임 수가 많을 수록, 많은 페이지를 메인 메모리에 담을 수 있으므로, 페이지 부재가 줄어든다.

위 그림은 (a)와 같은 참조가 이루어질시 프레임 수에 따른 페이지 부재 횟수이다.

2 선입선출(FIFO, First In First Out) 대치 알고리즘

대기 큐 내에서 가장 오래 기다린 페이지부터 대치하는 알고리즘.

새로운 페이지는 페이지 테이블 항목을 변경 후, 선입선출 큐의 마지막 위치에 삽입한다.

큐의 길이는 곧 프레임의 수이다.

:green_circle: PROS

+ 프로그램 작성이 쉬움

🟠 CONS

- 성능이 항상 좋진 않다.

벨레디의 변이 (Belady’s anomaly) : 프레임이 오히려 많아지는데 페이지 부재 횟수가 늘어남(위 그림의 프레임 수 3~4 구간)

3 최적 페이지 대치(OPT, OPTimal replacement algorithm) 알고리즘

모든 알고리즘 중 페이지 부재 비율이 가장 낮은 이상적인 알고리즘.

앞으로 가장 오랫동안 사용하지 않을 페이지를 대치한다.

하지만 이는 미래에 참조할 페이지를 정확히 알 수 없는 현재 기술로는 구현 불가능한 이상적인 알고리즘이며, 비교 연구에 주로 사용된다.

4 최근 최소 사용 대치(LRU, Least Recently Used) 알고리즘

오랫동안 사용하지 않은 페이지를 최우선적으로 대치하는 알고리즘

과거에 오랫동안 사용하지 않았다면, 미래에도 오랫동안 사용하지 않을 것이라는 근사치와 지역성을 이용한 정책이다.

최근 최소 사용 대치 알고리즘은 하드웨어를 요구하는 경우가 많은데, 아래 두 가지 방법으로 많이 구현한다.

4.1 카운터(계수기)를 이용한 순서 결정 방법

각 페이지 테이블 항목에 사용 시간 레지스터를 매핑
프로세서에 논리 클록을 추가 후, 카운터 필드를 덧붙임
메모리 관리 장치(MMU)가 페이지 참조 때마다 클록 증가
클록 레지스터의 내용은 복사되어 페이지의 해당 페이지 테이블에 있는 사용시간 레지스터에 추가, 즉 최후 참조 시간을 페이지에 넣게 된다.
가장 낮은 카운터 값(=가장 오랫동안 사용하지 않음)의 페이지 제거

페이지 탐색 시간과 페이지 테이블 변화 과정 만큼의 오버헤드가 존재

4.2 스택을 이용한 순서 결정 방법

페이지 번호를 스택에 넣어 관리하고 페이지 참조마다 페이지 번호를 스택의 톱에 두어 순서를 결정하는 방법

따라서 스택의 가장 위는 가장 최근에 사용한 페이지가 된다.
가장 아래에 있는 페이지가 가장 오래된 페이지가 되며, 페이지 부재 발생 시 교체된다.

+ 필드 비교, 업데이트, 계수기 등이 필요 없음
- 스택의 중간에 내용을 꺼내야 하므로 이중 연결 리스트로 구현해야 하며, 따라서 오버헤드가 생긴다.

5 최근 최소 사용 근접 알고리즘

최근 최소 사용 알고리즘의 구현에 필요한 하드웨어와 성능 때문에 참조 비트를 이용한 근접 알고리즘을 이용함.

참조 비트(reference bit) : 참조되거나 참조에 관련된 페이지는 1로, 아니면 주기적으로 0으로 초기화하여 대치의 대상이 되게 한다.

5.1 참조 비트 알고리즘

각 페이지마다 8비트(1바이트) 정보에 일정한 간격으로 참조 비트를 기록
가장 최상위 비트에 참조를 표기하고, 매 참조 시마다 비트를 오른쪽으로 쉬프트한다.
각 페이지마다 참조 비트를 비교하여 크기가 클수록 참조를 최근에 했거나 참조 횟수가 빈번한 것이다.
따라서 가장 작은 참조 비트를 가진 페이지는 교체된다. 크기가 같은 경우 선입선출로 결정된다.

각 페이지의 참조 비트의 크기만큼 참조 기록을 유지하게 된다.

5.2 시계(2차적 기회 대치) 알고리즘

각 프레임의 사용 여부를 나타내는 참조 비트와 원형 버퍼, 포인터를 이용한 알고리즘.

:green_circle: PROS
+ 자주 사용하는 페이지의 대치를 방지할 수 있음

+ 최근 최소 사용 알고리즘과 성능은 비슷, 오버헤드는 더 적음

+ 시계 알고리즘에 사용 비트를 추가 시, 수정 여부, 디스크 저장 여부 등을 이용해 더 강력한 페이지 대치 알고리즘을 작성 가능

페이지가 메모리에 처음 들어오면 참조 비트를 1로 설정한다. 이후, 참조될 때마다 참조 비트를 1로 설정한다.
페이지가 프레임에 할당되면 해당 프레임은 원형 큐로 들어가며, 큐 내의 다음 프레임을 가르키는 포인터를 가지게 되며, 다음 프레임을 가리키던 프레임은 방금 추가된 프레임을 가르키게 된다.
페이지 대치가 일어나면, 원형 큐 내의 버퍼를 조사한다.
만약, 프레임의 참조 비트가 1이라면, 0으로 조정하고, 현재 시간으로 고친다.(2차적 기회)
만약, 프레임의 참조 비트가 0이라면, 즉시 프레임을 새로운 페이지로 대치하고 1로 돌아간다.
만약, 원형 큐를 한바퀴 조사하는 동안에 참조 비트가 모두 1이였다면, 3으로 돌아간다.

위 그림은 간단한 시계 알고리즘의 예시이다.

선입선출 알고리즘보다 나은 성능을 보여준다.

5.3 NUR(Not Used Recently) 알고리즘

참조 비트과 수정 비트을 이용해 최근 사용하지 않은 페이지를 교체하는 알고리즘

참조 비트(R) : 해당 페이지의 액세스 여부를 확인해서 최근에 사용한 페이지들을 유지(초기값 : 0=참조 안함)
수정 비트(M) : 페이지의 수정 여부 확인(초기값 : 0=수정 안함)

이때, 두 비트 (R, M)를 확인해 (0, 0), (0, 1), (1, 0), (1, 1) 순서로 대치된다.

참조한 페이지는 미래에 다시 사용될 가능성이 높음
페이지 부재 발생 시, 수정한 페이지는 해당 페이지를 디스크에 복사한 뒤 제거 되어야 하므로 디스크 엑세스가 한번 더 필요함.
- 수정되지 않은 페이지는 원본이 디스크에 그대로 있으므로 복사하지 않아도 된다.

따라서, 최대한 수정이나 참조가 되지 않은 페이지를 고른다.

5.4 최소 사용 빈도수(LFU, Least Frequently Used) 알고리즘

각 페이지마다 참조 횟수 카운터가 있으며, 수가 가장 작은 페이지를 대치
시간이 지나면 참조 횟수가 점점 줄어들게 만들어, 과거에 참조가 많았던 쓸모없는 페이지를 대체되게 할 수 있다.

5.5 최대 사용 빈도수(MFU, Most Frequently Used) 알고리즘

위와 반대로, 계수가 높으면 충분히 사용했다고 생각하여 제거하는 방식.
보통 성능도 떨어지고 비용도 많이 들어서 사용하지 않는다.

5.6 페이지 버퍼링

페이지 버퍼링은 대체 대상으로 선택된 페이지를 즉시 교체하지 않고, 포인터 리스트 2개를 이용해 잠시 동안 메인 메모리에 유지하는 방식이다.
다른 대체 알고리즘과 병행하여 성능을 높일 수 있다.

수정 안된 가용 페이지 리스트, 혹은 자유 프레임 풀은 비어있거나 수정한 적이 없는 페이지 프레임의 리스트며, 페이지 테이블 항목만 삭제하고 메모리 데이터를 해제하지 않고 대기한다.
- 수정한 적없는 프레임은 다른 페이지를 넣기 위해 대치 요청이 들어오면 해제한다.
변경 페이지 리스트는 수정한 적이 있는 페이지 프레임들의 모임으로, 매 페이지는 페이지 테이블 항목만 삭제하고 메모리를 해제하지 않고 대기한다.
- 변경 페이지 프레임들은 일정 시기마다 일괄적으로 디스크에 복사된 후, 가용 페이지 리스트로 빈 프레임을 보내어 효율적인 디스크 액세스를 달성한다.
페이지 부재가 일어나면, 운영체제는 해당 두 리스트의 대기하고 있는 프레임들을 확인한 뒤, 리스트 내에 존재한다면, 리스트에서 제외하고, 페이지 테이블 항목만 추가하여, 디스크에 엑세스하지 않고 즉시 적재할 수 있다.
페이지 대치 알고리즘의 비교

페이지 대치 알고리즘은 가용한 프레임 수가 적을 때 더욱 유용하다는 것을 알 수 있다.

04 프레임 할당 알고리즘

1 프레임 할당 알고리즘의 필요성

여러 프로세스를 한 시스템에서 사용할 때, 프레임 할당 방법으로

모두 한꺼번에 공유하면, 불공정하게 일부 프로세스가 프레임을 독점할 수 있다.
균일하게 배분하면 메모리를 크게 사용하는 프로세스는 스래싱이, 메모리를 적게 사용하는 프로세스는 낭비가 일어날 수 있다.
따라서, 공정하고 페이지 부재를 줄이면서, 효율적인 메모리 사용을 위해 프레임 할당 알고리즘 또한 중요하다.

보통 프로세스들은 작업에 필요한 최소 프레임 수를 정의하고 있으며, 명령어 하나를 실행 중에 페이지 부재가 일어나면 프레임을 할당받고 처음부터 다시 시작한다.

예를 들어 메모리 참조 명령은 직접 참조는 프레임 하나, 간접 참조이면 프레임 셋이 필요해야 실행 가능하다.

따라서 최소 프레임 수와, 최대 할당 가능한 프레임 수 사이에 적절한 프레임 수를 할당해야 한다.

2 균일, 비례 프레임 할당 알고리즘

앞서, 균일 프레임 할당은 낭비와 페이지 부재가 일어날 수 있다고 하였다.
비례 프레임 할당 알고리즘은 프로세스의 가상 메모리 크기에 비례에 프레임을 할당 하는 방법으로 예시를 들자면,
최대 프레임 갯수가 개인 프로세스 $P_i$의 가상 메모리 크기를 $s_i$라고 하면, 전체 프로세스가 갖는 가상 메모리 공간의 크기 $S$와 비례 프레임 할당 갯수 $a_i$는 다음과 같다.
$S=\sum s_i\\ a_i=s_i/S\times m$
- 단, 이 방법은 미리 소프트웨어의 메모리 정보를 알고 있어야 하므로 오버헤드가 생긴다.
추가로 우선순위를 결합하여, 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스에 의해 페이지 대치가 될 수 있게 할 수 있다.
현대에서는 균일과 비례 프레임 할당 방법 둘을 혼합하여 사용한다.

05 메모리를 관리하는 프로세스 적재 정책

메인 메모리에 너무 적은 수의 프로세스가 상주하면 프로세스가 메모리에 적재되기 위해 대기시간이 너무 길어지고, 효율성이 떨어진다.
반대로 너무 많은 수의 프로세스가 상주하면 프로세스들이 차지하는 평균 페이지 감소로 페이지 부재가 자주 발생할 수 있다.

1 스래싱(thrashing)

1.1 스래싱의 개념

할당된 프레임 수가 너무 부족해 실제 프로세스 작업 수행보다 페이지 교환에 더욱 시간을 보내게 되어 시스템 성능이 급격히 낮아지는 현상.

1.2 스래싱의 발생 원인

운영체제는 프로세서의 이용률을 감시하며, 이용률이 적다면 다중 프로그래밍 수준을 올리기위해 프로세스 수를 늘리게 되고, 따라서 페이지 부재가 생겨난다.
심지어, 페이지 부재를 프로세서 대신 페이징 처리 장치가 처리하면서, 프로세서의 이용률이 낮아지고, 이를 감지한 운영체제가 더욱 더 프로세스를 늘려 페이지 부재가 점점 심화될 수 있다.

따라서 위의 그림처럼 어느 순간부터 오히려 프로세서 이용률이 떨어지는 스래싱이 발생하며, 이를 막기 위해서는 다중 프로그래밍의 정도를 낮추어야 한다.

1.3 스래싱의 예방

시스템이 프로세서 이용률과 시스템 페이지 부재 비율을 동시에 감시하면 스래싱을 감지할 수 있다.

주로 프로세서 이용률은 낮고 시스템 페이지 부재 비율이 치솟으면 스래싱이다.

지역 교환 알고리즘이나 우선순위 교환 알고리즘을 통해 미리 완화할 수 있다.

지역 교환 알고리즘 : 자기에게 할당된 프로세스 이외에는 대치 불가, 다른 프로세스로의 스래싱 전염을 막음.
우선순위 교환 알고리즘 : 우선순위가 높은 프로세스에서 일방적으로 낮은 우선순위의 프로세스의 프레임을 뺏음.

다만 위 두 경우는 여러 프로세스가 동시에 페이지 부재에 들어가 스래싱이 발생하는 것을 막을 수 없다.

따라서 다음 두가지 방법으로 적절한 프레임 수를 파악해 막을 수 있다.

작업 집합(Working set) 모델 : 프로세스가 실제로 얼만큼 프레임을 많이 사용하는지 검사해 지역 모델을 정의
지역 모델 : 프로세스 실행 시 프로그램은 보통 지역 몇 개로 중첩해서 구성하므로 한 지역에서 다른 지역으로 이동할 때 해당 지역의 크기만큼 프레임 할당
- 지역 : 적극적으로 동시에 사용하는 페이지의 집합(서브루틴, 함수, 변수, 리스트 등…), 보통 하나의 지역에서 수행을 마치고 다른 지역으로 이동하는 방식으로 사용됨.

데닝은 다중 프로그래밍 정도를 50% 정도로 제안

2 지역성(구역성, 국부성, locality)

실행 중인 프로세스에서 나타나는 동일한 값이나 관련 저장 위치를 자주 액세스 하는 현상
한번 참조한 동일한 데이터나 저장 위치 근처의 데이터를 짧은 시간 안에 다시 참조하는 현상
어느 실행 단계 동안 메모리의 정보를 균일하게 액세스하는 것이 아니라 선호하는 특정 페이지만 집중적으로 참조하는 현상

잠시동안 적은 양의 데이터만 집중적으로 참조하다 데이터의 또 다른 작은 규모의 데이터 덩어리로 이동하는 경향이 존재
주로 프로그램들의 루프, 서브 프로그램, 스택, 변수들의 계산, 합계, 배열 순례, 순차적 코드 실행 등으로 발생

크게 시간 지역성과 공간 지역성으로 분류한다.

시간 지역성
- 특정 동일한 자원, 메모리 위치를 상대적으로 짧은 시간 안에 재사용한다.
  순환(루프), 서브 프로그램, 스택, 계산이나 합계에 사용하는 변수 등이 예시
공간 지역성
- 프로세스가 메모리의 어떤 위치를 참조하면 그 근처를 이후에도 계속 참조할 가능성이 높다.
  데이터 정렬, 1차원 배열의 요소 탐색 같은 순차적 지역성, 배열 검색, 순차적 코드 실행, 근처의 관련 변수 선언 등이 예시

이를 이용해 적절한 프레임 수를 할당하여 스래싱을 예방할 수 있다.

예를 들어 위의 그림은 프로세스의 메모리를 참조하는 실제 그래프이며, 특정 시간에 특정 번호와 그 주변을 집중적으로 참조함을 알 수 있다.

3 작업 집합 모델(WSM, Working Set Model)

작업 집합 모델을 이용하면 많이 참조하는 페이지 집합을 메모리 공간에 상주시켜 페이지 대치 현상 줄일 수 있다.

작업 집합(Working set)이란, 가장 최근의 페이지 참조에 있는 페이지 집합을 의미하며, 프로그램의 지역 근사치가 된다.

프로세스의 작업 집합 모델 내의 페이지들, 즉 최근에 참조한 페이지만 메인 메모리에 유지시키는 방법이다.
그리고 새로운 프로세스들은 메인 메모리에 자신들의 작업 집합을 적재할 수 있는 공간이 있을 때만 시작할 수 있다.

작업 집합 모델 생성을 위해 :arrow_right: 작업 집합의 크기 정보 필요 :arrow_right: 작업 집합의 크기 정보는 작업 집합 창으로 구함.
작업 집합 창은 현재 시간부터 특정 과거까지 참조한 페이지를 포함하는 범위를 의미한다.

위 그림의 w이 작업 집합 창의 크기이다. w가 커질 수록, 과거 어느 시간까지 작업 집합에 포함할지 결정된다.

따라서 작업 집합의 크기는 위 그림처럼 일정하게 증가하다 프로그램 크기에 가까워질수록 증가량이 둔화된다.
너무 크면, 작업 집합이 전체 프로그램이 되어 비효율적이며, 너무 작으면 페이지 부재 비율이 늘어날 것이다.

작업 집합 창과 시간에 따른 작업 집합의 예시이다.
매드닉과 도노반은 100000을 제안했다.

작업 집합에서 가장 주요한 성질은 작업 집합 크기(WSS, Working Set size)로, 각 프로세스들의 작업 집합 크기의 합을 통해 전체 요구 프레임을 다음과 같이 구할 수 있다.
$D = \sum WSS_i$
사용 가능한 유효 프레임 수보다 D값이 더 커지면 스래싱이 발생된다.
운영체제에서는 이를 최대한 막기위해 작업집합을 예상하고 충분한 프레임을 할당한다.
하지만 일시적으로 D가 커져 스레싱이 발생할 순간에는 프로세스 하나를 선택해 일시중단한 후, 해당 프로세스의 프레임을 다른 프로세스에 할당하여 스래싱을 예방한다.

프로세스를 수행하는 동안 작업 집합의 크기는 위 그림처럼 계속 변하는데, 작업집합 크기가 일정한 안정기와 급격하게 변하는 과도기로 나뉜다.
주로 새로운 페이지를 참조하거나, 다른 지역으로 이동, 프로세스의 전환 등에 의해 급격히 커지며, 새로운 지역성이 이전 지역을 대체해 급격히 작아진다.

운영체제는 각 프로세스의 작업 집합을 감시하고 각 프로세스에 작업 집합 크기에 맞는 충분한 프레임을 할당한다.
여분의 페이지 프레임이 있을 때는 준비 상태에 있는 다른 프로세스를 불러들인 후 프레임을 할당해 다중 프로그래밍의 정도를 증가시킨다.
전체 작업 집합 크기의 합이 전체 유효 프레임 수보다 커지면 잠시 중지시킬 프로세스를 선정해 페이지를 회수하여 스래싱을 방지한다.

🟢 PROS
+ 페이지 부재 비율 감소
+ 유동적이고 효율적인 메모리 사용
+ 프리페이징(prepaging)에 유용

:orange_circle: CONS
- 작업 집합이 미래의 참조 페이지를 보장하지 않음(=페이지 부재는 사라지지 않음, 스래싱 조절 힘듦)
- 작업 집합 크기와 구성 페이지들은 주기적으로 감시되고 변해야 한다.
- 각 프로세스에서 작업 집합을 모두 측정하는 것은 현실적으로 불가능
- 참조한 페이지 시간과 시간 순서로 된 페이지 큐 유지 관리 필요
- 최적의 작업 집합 창의 크기 정하기 어려움

작업 집합의 크기와 페이지 부재 비율의 그래프는 위와 같다.
작업 집합의 크기가 클수록 부재 비율이 감소하지만, 메모리 효율이 나쁘다.
작업 집합의 크기가 작으면 부재 비율이 높지만, 메모리 효율이 좋다.
부재 비율 대 메모리 효율이 적절한 중간 지점을 찾는게 중요하다.

4 페이지 부재 비율(PFF, Page Fault Frequency)

페이지 부재가 일어난 비율, 페이지 환경에서 프로세스의 실행 측정 기준으로 사용

페이지 부재 비율이 증가하는데 유효 프레임이 없으면 프로세스를 중단한 후, 페이지 부재 비율이 높은 프로세스에 할당한다.
만약 페이지 부재 비율이 너무 낮다면 유효 프레임이 너무 많다는 것이므로, 프레임을 줄인다.

그림 위 처럼 상한 값과 하한 값 사이의 적절한 값을 유지하는것이 관건이다.

+ 작업 집합 모델 비해 페이지 부재 시마다 프레임 수를 조절할 수 있게 해주어 오버헤드가 적음
- 단, 페이지 부재 비율 알고리즘은 페이지 참조가 새로운 지역으로 이동하는 과도기에는 제대로 작동하지 않는다.

06 메모리 관리와 관련된 기타 이슈

1 대치 범위

대치가 일어나 희생될 페이지를 고르는 기준은 모든 프로세스의 페이지가 대상인 전역 대치(리눅스)와 프로세스 개별로 제한된 지역 대치(윈도우 XP)가 있다.
보통 전역 대치는 구현이 쉽고 부담이 적고, 지역 대치는 성능 분석이 쉽다.

1.1 전역 대치

메인 메모리에 있는 모든 페이지를 자유롭게 선택하여 대치, 즉 다른 프로세스에게 프레임을 뺏길 수 있다.
소프트웨어로 유지관리되며, 프레임이 모두 조사 가능하도록 잠금 해제 되어 있어야 함.

+ 작업집합이 더 많거나 더 적은 페이지 프레임 할당에 따라 증가 및 감소됨.
+ 구현이 쉽고 부담이 적다.
+ 다량의 프레임이 필요한 커다란 프로세스가 존재하는 경우 유용, 대형 시스템에서 주로 사용
+ 프로세스당 필요한 할당 추측 가능
+ 대기 프로세스의 메모리가 낭비되지 않음

- 뺏는데 시간이 천차 만별이므로 프로그램의 수행 시간이 불안정해진다.
- 프로세스 별 차별적인 조절 불가

1.2 지역 대치

페이지 부재를 발생한 프로세스의 상주 페이지에서 대치할 페이지를 선택. 즉, 자기에게 할당된 프레임만 사용 가능.

+ 고정 분할이나 작업 지합 모델 기반 균형 설정으로 메모리 할당을 조정한다.
+ 프로세스의 중요도나 크기에 따라 메모리 할당을 조정해 성능을 향상시킬 수 있다.
+ 성능이 일관되며 프로세스가 자신의 페이지 부재 비율을 월등히 제어할 수 있다.
+ 확장성이 있으며, 프로세스가 공유 자원을 두고 경쟁하지 않아도 된다.

- 단, 구현이 어렵고 부담이 크다.

2 프리 페이징(prepaging)

시작시 지역성 형성을 위해 많은 페이지 부재가 생기는 요구 페이징의 단점을 방지하는 방법
예상되는 모든 페이지를 사전에 한꺼번에 메모리 내로 가져온다.

+ 입출력 인터럽트 한번만 발생시켜 연속된 페이지를 한번에 메모리로 가져오므로 요구 페이징보다 성능이 좋다.
예를 들어 어떤 프로세스가 입출력이나 프레임 부족 등으로 쉬게 되었다면, 작업 집합을 기억했다가 시작하기 전에 모든 페이지를 자동으로 가져온다.

- 만약, 사용할 페이지를 잘못 예측하면 오히려 요구 페이징보다 성능이 떨어질 수 있으므로, 예측 알고리즘 성능이 중요하다.

3 페이지 크기

페이지 크기 또한 하드웨어 디자인에 매우 중요한 요소이다.
페이지의 크기는 보통 2의 지수승이며, 256~4096 바이트나 워드이며, 메인 메모리의 크기와 프로그램 크기 자체에 영향을 받는다.

페이지 크기가 작은 경우, 전송속도가 빠르지만, 전송 속도는 워낙 빨라 성능에 큰 영향을 끼치지 않는다.
입출력 회전 지연시간과 오버헤드 때문에 페이지의 입출력의 경우 페이지 크기가 큰 편이 유리한다.

페이지 크기는 컴퓨터 종류별, 프로세서 속도와 메모리 용량 별로 천차 만별이고, 이는 적절한 페이지 크기를 결정하는 것은 어려운 일임을 알 수 있다.

4 페이지 테이블의 구조

각 프로세스에는 페이지 테이블을 가지고 있으며, 이를 이용해 가상 주소를 프레임 번호와 오프셋으로 구성된 물리적 주소로 변환한다.
페이지 테이블 또한, 메모리에 저장해야 하므로 페이징의 대상이며, 프로세스마다 하나씩 가지므로 크기를 줄이는게 관건이다.

예를 들어 64비트 가상 주소(64bit 운영체제), $2^{12}$ 비트의 페이지 크기, 4GB=$2^{32}$ 비트의 메모리인 시스템에서 단일 수준 페이지 테이블을 유지하는데 필요한 공간은 다음과 같이 계산한다.

페이지 테이블 항목 수 : 가상 주소 논리적 주소 수 = 64 비트 중 12비트는 페이지 크기 4KB 때문에 오프셋으로 사용 = 52비트의 논리적 주소 수 = $2^{52}$개
페이지 테이블 항목 크기 :
- 물리적 페이지의 수(메모리 크기 $2^{32}$ / 페이지 크기 $2^{12}$) = $2^{20}$개
- 액세스 제어 비트(1비트) + 물리적 페이지 번호(20비트) = 21 비트 = 약 4 바이트 = 32비트(2의 지수승이어야 하므로)
전체 페이지 테이블 크기 : $2^{52} \times 2^2$바이트 = $2^{54}$바이트 = $2^{4}$PB = 16PB
4GB의 메모리를 유지하기 위해 백그라운드 프로세서를 포함해서 10개의 프로세스가 있다면 메모리 160PB가 소모되며, 연속적인 메모리 배치도 불가능하다.
4바이트 테이블에 10비트 주소 공간의 계층 구조 테이블을 이용하면, [52/10]=6단계에 걸쳐 액세스할 수 있지만, 디스크 접근 성능이 떨어진다.

이를 대신해, 메모리의 물리적 주소를 이용하는 역 페이지 테이블이 존재하다.
+ 역 페이지 테이블 항목은 가상 주소의 논리적 주소 대신 물리적 주소를 이용하며, 시스템 당 하나만 존재해도 된다.

같은 시스템에서 역 페이지 테이블이 차지하는 크기를 알아보자

페이지 테이블 항목 수 : 물리적 주소 수 = 메모리 용량 $2^{32}$ / 페이지 크기 $2^{12}$ = $2^{20}$개
페이지 테이블 항목 크기 : 물리적 페이지 주소(20비트) + 액세스 제어 비트 포함 기타 정보(12 비트) + 프로세스 ID (16비트) = 48비트 = 8바이트(2의 지수승)

즉 역 페이지 테이블의 크기는 $2^{20}\times 2^3Byte$=$2^{23}Byte = 8MB$이다. 뿐만 아니라 시스템에 단 하나만 존재해도 된다.(프로세스 100개 기준 8MB VS 160PB)
- 2차 저장소(디스크)에 있는 페이지와 관련된 어떤 정보도 유지하지 않아 운영체제가 관리해야 한다.

상단의 그림은 선형 역 페이지 테이블을 이용한 변환 절차이다.
역 페이지 테이블의 가상 주소는 프로세스 식별자, 가상 페이지 번호, 오프셋으로 구성된다.

가상 페이지 번호와 프로세서 식별자를 이용해 색인 값인 물리 페이지 번호를 알 수있다.
하지만, 가상 페이지 주소를 찾으려면 테이블 전체를 탐색하거나 페이지 크기의 메모리를 액세스 해야하므로, 탐색 시간을 줄이려면 해싱 테이블을 이용해 시간을 줄일 수 있다.

+ 해시를 이용하면 해시 함수를 적용시 바로 색인값이 나오기 때문에 곧바로 접근할 수 있다.
해시 테이블에는 프로세서 ID와 VPN 값에 해쉬 함수를 적용해 생성되는 색인값이 존재하며, 이를 통해 페이지 테이블에 접근할 수 있다.
해시테이블은 충돌의 가능성이 있으므로, 페이지 테이블의 항목들은 연결 리스트 체인을 통해 연결되어 있고, VPN 값을 비교해 찾은 색인 값을 물리 페이지 번호로 이용한다.

위 그림은 해쉬 역 테이블에서 물리 페이지를 찾아내는 과정이다.
만약 탐색 결과가 Null이라면 페이지 부재이므로 디스크에서 해당 값을 가져온다.

+ 이곳에 추가로 캐쉬를 적용하면 더욱 빨라진다.

변환 우선 참조 버퍼(TLB, Translation Look-aside Buffer)는 프로세스의 전체 페이지 테이블 중 가장 최근에 참조한 페이지 일부를 저장하는 캐쉬이다.

가상 주소 [V=(p,d)]를 참조 시 먼저 변환 우선참조 버퍼를 조사해 페이지 P를 찾는다.
존재한다면 저장한 프레임 번호(PFN)을 이용해 접근한다.
존재하지 않는다면 페이지 테이블 항목을 조사해 접근한다.

_articles/computer_science/OS/IT_COOK_BOOK_OS_정리/OS 정리-Chap 8-가상 메모리.md

ROADVIRUSHN

▶ COMPUTER_SCIENCE

▶ WEB

▶ ETC

▶ AI

Recent views

8. 가상 메모리

01 가상 메모리의 이해

1 가상 메모리의 개념과 원리

2 가상 주소와 테이블 항목

02 요구 페이징

1 요구 페이징의 개념

2 페이지 부재

쓰기복사(COW, Copy-On-Write)

3 페이지 성능

4 페이지 성능을 높이는 페이지 대치

03 페이지 대치 알고리즘

1 페이지 부재와 프레임 수

2 선입선출(FIFO, First In First Out) 대치 알고리즘

3 최적 페이지 대치(OPT, OPTimal replacement algorithm) 알고리즘

4 최근 최소 사용 대치(LRU, Least Recently Used) 알고리즘

4.1 카운터(계수기)를 이용한 순서 결정 방법

4.2 스택을 이용한 순서 결정 방법

5 최근 최소 사용 근접 알고리즘

5.1 참조 비트 알고리즘

5.2 시계(2차적 기회 대치) 알고리즘

5.3 NUR(Not Used Recently) 알고리즘

5.4 최소 사용 빈도수(LFU, Least Frequently Used) 알고리즘

5.5 최대 사용 빈도수(MFU, Most Frequently Used) 알고리즘

5.6 페이지 버퍼링

페이지 대치 알고리즘의 비교

04 프레임 할당 알고리즘

1 프레임 할당 알고리즘의 필요성

2 균일, 비례 프레임 할당 알고리즘

05 메모리를 관리하는 프로세스 적재 정책

1 스래싱(thrashing)

1.1 스래싱의 개념

1.2 스래싱의 발생 원인

1.3 스래싱의 예방

2 지역성(구역성, 국부성, locality)

3 작업 집합 모델(WSM, Working Set Model)

4 페이지 부재 비율(PFF, Page Fault Frequency)

06 메모리 관리와 관련된 기타 이슈

1 대치 범위

1.1 전역 대치

1.2 지역 대치

2 프리 페이징(prepaging)

3 페이지 크기

4 페이지 테이블의 구조