[운영체제] 가상메모리

가상메모리

다중 프로그래밍을 실현하기 위해서는 많은 프로세스들을 동시에 메모리에 올려두어야한다. 가상 메모리는 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이며, 프로그램이 물리 메모리보다 커도 된다는 주요 장점이 있다.

배경

실행되는 코드의 전부를 물리 메모리에 존재시켜야했고, 메모리 용량보다 큰 프로그램은 실행시킬 수 없었다.

프로그램의 일부분만 메모리에 올릴 수 있다면

• CPU의 용량보다 큰 프로세스를 실행할 수 있다.
• 더 많은 프로그램을 동시에 실행할 수 있게 된다. 응답시간은 유지되고, CPU 이용률과 처리율은 높아진다.
• swap에 필요한 입출력이 줄어들기 때문에 프로그램들이 빠르게 실행된다.

하는 일

가상 메모리는 실제 물리 메모리 개념과 사용자의 논리 메모리 개념을 분리한 것이다. 용량이 작은 메인 메모리를 마치 큰 용량을 가진 것처럼 사용할 수 있다.

프로그램을 여러 개의 작은 블록 단위로 나누어서 가상 메모리에 보관해놓고 실행 시 요구되는 블록만 메인 메모리에 불연속적으로 할당하여 처리한다.

가상 주소 공간

한 프로세스가 메모리에 저장되는 논리적인 모습을 가상 메모리에 구현한 공간이다. 프로세스가 요구하는 메모리 공간을 가상메모리에서 제공함으로써 현재 직접적으로 필요치 않은 메모리 공간은 실제 메모리에 올리지 않는 것으로 물리 메모리를 절약할 수 있다.

예를 들어, 한 프로그램이 실행되며 논리 메모리로 100KB가 요구 되었다고할 때, 실행까지 필요한 메모리 공간의 합이 40KB라면 나머지 60KB은 필요시에만 물리 메모리에 요구한다.

Stack free (60KB) HeapDataCode

프로세스간의 페이지 공유

• 시스템 라이브러리가 여러 프로세스들 사이에 공유될 수 있도록 한다. 각 프로세스들은 공유 라이브러리를 자신의 가상 주소 공간에 두고 사용하는 것처럼 인식하지만, 라이브러리가 올라가 있는 물리 메모리 페이지들은 모든 프로세스에 공유되고 있다.
• 프로세스들이 메모리를 공유하는 것을 가능하게하고, 프로세스들은 공유 메모리를 통해 통신할 수 있다. 각 프로세스들은 각자 자신의 주소 공간처럼 인식하지만, 실제 물리 메모리는 공유되고 있다.
• fork()를 통한 프로세스 생성 과정에서 페이지들이 공유되는 것을 가능하게 한다.

가상 메모리 페이징

필요한 페이지만 메인 메모리에 올린다는 점에서 다르다. Swap in-out 기능을 지원한다

page table은 메인 메모리에 있고 page table을 가리키는 포인터 PTBR (Page Table Base Register)를 만든다. Page table은 가상 주소와 물리적 주소의 매핑 테이블이며, 개별 매핑 데이터를 Page Table Entry PTE라고 한다.

PTE는 해당 page가 메인 메모리에 있는지 확인하기 위한 Valid bit(P)와 해당 page 내용이 수정됐는지 안됐는지 확인을 위한 Dirty bit(M)을 가지며 프레임 번호를 저장한다.

페이징 기법은 프로세스의 주소 공간을 같은 크기로 나누어 물리적 메모리에 올리는 방식으로 먼저 PTE를 통해 논리적 주소를 물리적 주소로 변환해야하기 때문에 PTBR를 통해 PTE에 접근해야하고, 변환된 물리적 주소로 실제 데이터에 접근해야하기 때문에 오버헤드가 크다. 이러한 오버헤드를 줄이고 메모리 접근 시간을 줄이기 위해서 캐시 메모리인 TLB에 번번히 접근 하는 PTE를 담아 두고 가상 페이지 주소 VPN을 통해 접근한다.

TLB는 <Page#, Frame#>로 구성되어 있다. MMU는 가상 주소에서 추출한 Page#로 TLB를 체크한다. 만약 해당 페이지 번호의 PTE가 있으면 Frame 번호를 반환하고 이를 TLB HIT라고 한다. 만약 없으면 TLB Miss이며 메모리 에 있는 페이지 테이블을 체크한다. 만약 page table에 PTE가 있으면 present bit = 1으로 PTE를 TLB로 로드한 후 프레임 번호를 리턴한다. 없으면 present bit = 0으로 page fault exception이 발생하며 이후 OS가 처리한다.

메모리 관리 전략

반입 전략 (Fetch)

프로그램이나 데이터를 주기억장치에 언제 적재 할 것인가?

• 요구 반입(Demand Fetch) : 프로세스가 특정 프로그램이나 데이터 등의 참조를 요구할 때
• 예상 반입(Anticipatory Fetch): 프로세스에 의해 참조될 프로그램이나 데이터 등을 미리 예상하여 적재

배치 전략 (Placement)

프로그램이나 데이터를 주기억장치에 어디에 위치 시킬 것인가?

• 최초 적합(First Fit) : 프로그램이 들어갈 수 있는 크기의 빈 분할 영역 중 첫 번째 영역에 배치
• Next-fit: 마지막으로 placement된 위치에서부터 스캔에서 가능한 블럭에 선택
• 최적 적합(Best Fit): 프로그램이 들어갈 수 있는 크기의 빈 분할 영역 중 단편화를 가장 작게 남기는 영역에 배치
• 최악 적합(Worst Fit): 프로그램이 들어갈 수 있는 크기의 빈 분할 영역 중 단편화를 가장 크게 남기는 영역에 배치

교체 전략 (Replacement)

주기억장치의 모든 영역이 이미 사용 중일 때 새로운 프로그램이나 데이터를 어느 영역을 교체하여 사용할 것인지를 결정하는 전략

FIFO, OPT, LRU, LFU, NUR, SCR ...

페이지 교체 알고리즘

메모리 과할당

페이지 기법과 같은 메모리 관리 기법은 가상 메모리를 사용해서 실제 메모리보다 큰 사이즈의 메모리를 프로세스에 할당한 상황이다. 아래와 같은 경우가 있다.

1. 프로세스 실행 중 페이지 폴트 발생
2. 페이지 폴트를 발생시킨 페이지 위치를 디스크에서 찾음
3. 메모리의 빈 프레임에 페이지를 올려야하는데 모든 메모리가 사용 중일 경우

이를 해결하기 위해서는 빈 프레임을 확보할 수 있어야 한다.

1. 메모리에 올라와 있는 한 프로세스를 종료시켜 빈 프레임을 얻음
2. 프로세스 하나를 swap out하고, 이 공간을 빈 프레임으로 활용

Demand Paging(요구 페이징)

프로그램 실행 시작시에 프로그램 전체를 디스크에서 물리 메모리에 적재하는 대신, 초기에 필요한 것들만 적재하는 전략을 요구 페이징이라고 하며, 가상 메모리 시스템에서 많이 사용된다. 가상 메모리는 대개 페이지로 관리되는데, 요구 페이징을 사용하는 가상 메모리에서는 실행 과정에서 필요해질 때 페이지들이 적재된다. 한번도 접근되지 않은 페이지는 물리 메모리에 적재되지 않는다.

프로세스 내의 개별 페이지들은 페이저에 의해 관리된다. 페이저는 프로세스 실행에 필요한 페이지들만 메모리로 읽어 옮으로써, 사용되지 않을 페이지를 가져오는 시간 낭비와 메모리 낭비를 줄일 수 있다.

페이지 교체

프로그램 실행 시에 모든 항목이 물리 메모리에 올라오지 않기 때문에, 프로세스의 동작에 필요한 페이지를 요청하는 과정에서 페이지 부재(page Fault)가 발생하게 되면, 원하는 페이지를 보조저장장치에서 가져오게 된다. 하지만 만약, 물리 메모리가 모두 사용 중인 상황이라면 페이지 교체가 이뤄져야한다. 이때 어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법이 페이지 교체 알고리즘이다.

페이지 교체가 이루어지면 아무 일이 없었던 것처럼 프로세스를 계속 수행시켜주면서 사용자가 알지 못하도록 해야한다. 이를 위해서는 페이지 교체시에 오버헤드를 최대한 줄여야한다.

오버헤드가 발생하는 이유

어떤 프레임을 선택해서 비울 때, 해당 프레임에 페이지를 올릴 때 이렇게 두 번의 디스크 접근이 이루어지기 때문에 페이지 교체가 많아지면 입출력 연산이 많이 발생하게 되면서 오버 헤드 문제가 발생하게 된다.

방식

물리 메모리가 모두 사용 중인 상황에서의 메모리 교체 흐름이다.

1. 디스크에서 필요한 페이지의 위치를 찾는다.
2. 빈 페이지 프레임을 찾는다.
   1. 페이지 교체 알고리즘을 통해 희생될 페이지를 고른다.
   2. 희생될 페이지를 디스크에 기록하고, 관련 페이지 테이블을 수정한다.
3. 새롭게 비워진 페이지 테이블 내 프레임에 새 페이지를 읽어오고, 프레임 테이블을 수정한다.
4. 사용자 프로세스 재 시작

OPT (OPTimal replacement) 최적 교체

앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘이다.

장점: 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.

단점: 구현의 어려움이 있다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문이다.

 

FIFO

먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게된다.

장점

• 이해하기 쉽고 프로그래밍하기도 쉽다.

단점

• 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다.
• 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
• Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재한다.

LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다. FIFO 보다 대체로 우수하고 OPT보다는 그러지 못한 모습을 보인다.

 

LFU (Least Frequently Used)

사용 빈도가 가장 적은 페이지를 교체하는 기법이다. 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.

 

NUR (Not Used Recently)

최근에 사용하지 않은 페이지를 교체하는 기법으로 최근에 사용되지 않은 페이지는 향후에도 사용하지 않을 가능성이 높다는 것을 전제로 LRU에서 나타나는 오버헤드를 줄일 수 있다.

 

SCR

FIFO 기법의 단점을 보완하는 기법이다.

 

MFU 페이지 교체(Most Frequently Used)

참조 회수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다. 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

가상 메모리 이슈

페이지 크기

페이지 크기를 늘리면 PTE의 갯수가 줄어 들어 페이지 테이블의 사이즈는 줄어들지만 관리 측면에서 효율이 떨어지고 internal fragment가 발생할 수 있다.

페이지 크기를 줄이면 불필요한 내용이 주기억 장치에 적재될 확률이 적으므로 효율적인 워킹 셋을 유지할 수 있다. Locality에 더 일치할 수 있기 때문에 효율이 높아지고 단편화가 감소된다.

하지만 PTE의 개수가 늘어나 매핑 속도가 늦어지며 디스크 접근 횟수가 많아져서 오버헤드가 생긴다.

Smaller tables

32bit 컴퓨터에서 page size가 4KB라면 12bit는 offset이고 나머지 22bit가 PTE의 개수가 된다. 따라서 2^20개의 PTE가 존재하는데 만약 PTE가 4B라면 20^20^4 = 4MB로 너무 큰 메모리 사이즈가 page table에 할당된다는 문제가 있다. 따라서 page table size를 최대한 작게 해야하며 3가지 방법이 있다.

Combined paging and segmentation

페이징 기법과 세그먼트 기법을 융합한 방법으로 주소 공간을 segment로 쪼갠 후에 고정 길이의 page로 다시 쪼개는 방법이다.

Segment table은 base와 bound, other control bits를 가진다.

• base: 해당 세그먼트의 페이지 테이블 위치
• bound: PTE의 번호를 저장한다.

PTE는 원래대로 <page#, frame#>를 가진다. 페이지 테이블의 메모리 오버헤드를 줄일 수 있고 메모리 할당을 간단히 할 수 있다. 외부 단편화는 일어나지 않지만 내부 단편화는 일어날 수 있다. 기본 페이징 기법에 비해 복잡도가 올라간다.

Hierachical Paging

page table을 작은 여러개의 page table chunk들로 나눈다. 만약 PTE의 전체 페이지가 invalid하다면 page table chunk를 할당하지 않는다. 2개 레벨의 page table을 두는데 page table 그 자체도 page화 된다.

page table이 물리적 메모리에서 연속적으로 저장되지 않기 때문에 메모리 낭비를 줄일 수 있지만 메모리로 부터 추가적인 로드가 필요하다는 단점이 있다.

Inverted Page Table

메모리의 각 frame별로 하나의 entry를 두는 방법으로 시스템에 하나의 페이지 테이블이 존재한다. PTE 번호 는 PFN과 같다. PFN를 인덱스로 활용한다. 각 entrys는 <pid, page#, offset>을 가진다. 페이지 테이블을 저장할 메모리를 줄일 수 있지만 참조된 페이지를 찾는데 시간이 걸린다는 단점이 있다. hash table을 사용해 해결 할 수 있다.

Faster Translation

page table을 접근하는데 추가적인 메모리 접근이 필요해 성능이 떨어진다는 문제를 PTE를 TLB에 캐시해 해결할 수 있다.

TLB에 context switch가 일어날 경우 이전 프로세스에서 TLB는 의미가 없어진다는 문제가 있는데 해결을 위한 두 가지 방법이 있다.

• Flush를 이용해 모든 valid bit들을 0으로 설정하는 방법
• ASID를 사용해 PID를 같이 저장해 프로세스를 구별하는 방법

Locality

프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론이다. 스레싱을 방지하기 위한 워킹셋 이론의 기반이 되었다.

• 시간 구역성: 최근에 참조된 주소의 내용은 곧 다음에도 참조되는 특성
• 공간 구역성: 실제 프로그램이 참조된 주소와 인접한 주소의 내용이 다시 참조되는 특성

Working set

프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

시간에 따라 자주 참조하는 페이지들의 집합이 변하기 때문에 워킹 셋은 시간에 따라 변경된다.

Thrashing

스레싱은 프로세스의 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상이다.

다중 프로그래밍 시스템이나 가상 기억 장치를 사용하는 시스템에서 하나의 프로세스 수행 과정 중 자주 페이지 부재가 발생함으로써 나타나는 현상으로, 전체 시스템의 성능이 저하된다.

다중 프로그래밍의 정도가 높아짐에 따라 CPU 이용률은 어느 특정 시점까지는 높아지지만, 다중 프로그래밍의 정도가 더욱 커지면 스레싱이 나타나고 CPU의 이용률은 급격히 감소하게 된다.

해결 방안

• 워킹 셋을 유지한다.
• 임계치를 예상하여 운영한다.
• 부족한 자원을 증설하고, 일부 프로세스를 중단시킨다.
• 다중 프로그래밍 정도를 적정 수준으로 유지한다.
• 페이지 부재 빈도를 조절하여 사용한다