[운영체제] 가상 메모리

가상 메모리

컴퓨터 아키텍처 배경부터 짤막하게 설명드리자면, 폰 노이만 아키텍처 기반으로 된 코드들은 반드시 메모리RAM에 적재되어 실행되어야 해요.

이 말대로라면 실제로 각 프로세스마다 메모리를 할당하기에는 메모리 크기에 한계가 있어요. 일반적으로 저희는 16~32GB의 RAM을 컴퓨터에 장착시켜요(상황에 따라 더 넣는 경우도 있지만요). 그런데 우리는 게임을 실행시키고(이건 프로그램 크기가 엄청나죠), 유튜브를 검색하면서 음악도 듣거나 아니면 중간에 넷플릭스도 틀죠. 그럼에도 컴퓨터는 이걸 전부 다 끊김없이 잘만 실행시켜요.

바로 이걸 가능케 하는게 가상 메모리Virtual Memory 시스템이에요. 가상 메모리는 적은 메모리로 여러 프로세스를 실행시키기 위한 시스템이에요. 이는 메모리가 실제 메모리보다 많아 보이게 하는 기술이에요. 프로세스 크기 자체는 엄청나지만, 실제로 프로세스가 사용하는 메모리는 작다는 점에 착안해서 고안되었어요. 프로세스간 공간 분리로 프로세스 이슈가 전체 시스템에 영향을 주지 않게 할 수 있어요.

작동 매커니즘

프로세스는 가상 주소를 사용해서 실제 해당 주소에서 데이터를 읽고 쓸 때만 물리 주소로 바꿔줘요.

가상 주소와 물리 주소

• 가상 주소 : 프로세스가 참조하는 주소
• 물리 주소 : 실제 메모리RAM 주소

Memory Management Unit(MMU)

가상 메모리 시스템을 작동하기 위해 MMU에서 가상 메모리 주소와 물리 주소를 관리해요.

CPU는 가상 메모리를 다루고 실제 해당 물리 주소를 접근할 때 MMU 장치를 통해 가상 주소와 매칭된 물리 주소를 접근해요.

MMU는 하드웨어 장치에요. 왜냐하면 소프트웨어 방식보단 하드웨어 장치가 주소 변환이 더 빠르기 때문이에요. 그래서 별도의 장치를 통해 주소 변환을 이루어요.

페이징 시스템

메모리 주소 관련 이슈를 어떻게 관리하는지 알아봤으니, 어떠한 방식으로 작동하는지 알아봐요.

페이징 시스템Paging System은 크기가 동일한 페이지로 가상 주소 공간과 매칭하는 물리 주소 공간을 관리해요.

프로세스가 실행될 때 전체를 메모리에 적재시킬 필요가 없어요. 그때마다 필요한 공간만 적재시켜서 실행시키고, 적재가 안된 부분을 실행해야 하면 그때 메모리에 적재시켜 실행하면 되기 때문이에요. 바로 이 공간을 페이지Page 단위로 나뉘어서 메모리 적재시키고 프로세스를 실행시켜 물리 메모리를 효율적으로 사용하는 거에요. 그리고 이 페이지를 관리하는 시스템을 페이징 시스템이라 해요.

페이징 시스템은 하드웨어의 지원이 필요해요. Intel x86(32-bit) CPU 기준 하나의 페이지 단위는 4KB, 2MB, 1GB이에요. '소프트웨어'인 리눅스는 4KB로 페이징을 해요. 페이지Page 번호를 기반으로 가상 주소 및 물리 주소 매핑 정보를 기록하고 사용해요.

리눅스를 기준으로 예를 들어봐요

리눅스는 프로세스 크기를 4GB로 고정해요. 프로세스의 PCB에 페이지 테이블Page Table 구조체를 가리키는 주소가 들어있어요. 가상 주소와 물리 주소간 매핑 정보가 존재해요.

페이징 시스템 구조

페이징 시스템은 페이지 또는 페이지 프레임Page frame라 불리는 고정된 크기의 block(4KB)로 나눠요.

이 또한 수도 코드Pseudo-code로 표현할 수 있어요.

p : 가상 메모리 페이지
d : p 안에서 참조하는 위치

페이지 크기가 4KB인 것을 예로 들면,

• 가상 주소의 0-bit에서 11-bit가 변위d를 나타내요.
• 12-bit 이상이 페이지 번호가 될 수 있어요.

프로세스가 4GB를 사용하는 이유

32-bit 시스템에선 $2^{32}$-bit, 즉 4GB의 시스템에서 다 표현할 수 있기 때문이에요.

페이지 테이블(Page Table)

물리 주소에 있는 페이지 번호와 해당 페이지의 첫 물리 주소 정보를 매핑한 표에요.

해당 프로세스에서 특정 가상 주소를 접근하기 위해선,

1. 해당 프로세스의 페이지 테이블에 해당 가상 주소가 포함된 페이지 번호가 있는지 확인해요.
2. 페이지 번호가 있다면 이 페이지가 매핑된 첫 물리 주소를 알아낼 수 있어요 $\to$ p'
3. p' + 변위d가 실제 물리 주소가 되요.

앞서 말씀드렸듯이 프로세스의 페이지는 항상 물리 메모리에 적재될 필요가 없어요. 그래서 적재가 되지 않은 페이지는 페이지 테이블에 Vaild/Invalid bit로 적재 여부 정보를 담아요.

페이징 시스템과 MMU

개념을 설명드렸으니 개괄적인 매커니즘을 말씀드리자면,

1. CPU는 가상 주소 접근 시 MMU 장치를 통해 물리 메모리를 접근해요.
2. 프로세스가 생성되면, 페이지 테이블 정보가 생성되요.

   1. PCB 등에서 해당 페이지 테이블 접근이 가능하고, 관련 정보는 물리 메모리에 적재해요.
   2. 프로세스가 구동되면, 해당 페이지 테이블 base 주소가 별도 레지스터CR3에 저장되요.
   3. CPU가 가상 주소를 접근하면 MMU가 페이지 테이블 base 주소를 접근해서 물리 주소를 가져와요.

다중 단계 페이징 시스템

페이징 시스템을 좀더 깊게 들어가볼게요.

실제로 프로세스는 4GB를 넘는 경우가 거의 없어요. 우리가 간단하게 Hello World!를 출력하는 프로그램부터 해서, 대부분 프로세스는 4GB까지 공간을 필요로 하지 않아요. 따라서 하나의 프로세스가 4GB를 모두 차지하는 것은 매우 비효율적이에요.

그래서 페이지 정보를 단계로 나눠서 생성해요. 필요 없는 페이지를 생성하지 않으면 그만큼 공간 절약이 가능해요.

💡32-bit 시스템에서 4KB를 위한 페이징 시스템
하위 12-bit는 오프셋, 상위 20-bit는 페이징 번호 이므로, $2^{20}$(1048576)개의 페이지 정보가 필요해요.

공간 절약을 위해 위와 같이 페이지 번호를 나타내는 bit를 구분해서 단계를 나눠요.

본래 상위 20-bit를 페이지 정보로 활용했지만, 이렇게 단계를 나눠 상단의 10-bit는 페이지 경로Page Directory, 그 다음 10-bit는 실제로 사용하는 페이지 테이블Page Table로 나눠 효율적인 공간 관리하는 시스템을 구축했어요.

CR3 레지스터에 페이지 디렉토리 시작 주소를 등록하여 찾아가고, 페이지 디렉토리엔 페이지 테이블의 시작 주소를 가지고 있어 페이지 테이블을 접근해 실제 물리 메모리의 프레임 주소를 찾아 데이터를 가져오는 방식이에요.

그림 상에선 3단계로 나눴지만, 리눅스는 최근 4단계까지 나눈다고 해요.

MMU와 Translation Lookaside Buffer(TLB)

메모리 접근에 대한 내용을 상세적으로 다뤄봐요. 실제 물리 주소를 접근할 때 MMU를 활용한다고 했는데, 실은 추가적으로 하드웨어 보조장치를 활용해서 접근하는데, 이를 Translation Lookaside Buffer, TLB라고 해요.

왜 이렇게 하나면,

그림에서 알 수 있듯이, 메인 메모리 접근시간보다 레지스터 접근 시간이 현저하게 빨라요. 그래서 데이터 접근할 때마다 메인 메모리보단 과거에 사용한 적이 있다면 이를 따로 레지스터에 캐싱Caching해서 접근 속도를 높이는 보조장치를 두는 TLB, 페이지 정보 캐시 장치로 접근 속도 향상을 시킬 수 있게 하기 위해 따로 보조장치를 두는 거에요.

매커니즘 with TLB
1. 가상 주소 요청 $\to$ MMU
2. MMU는 TLB에서 최근에 가상 주소에서 물리 주소로 변환한 정보가 있는지 확인, 있다면 해당 정보를 활용!
3. TLB에 없다면 CR3에 등록된 base 주소로 접근해 메인 메모리에서 데이터를 찾아요.
4. 찾았다면 메인 메모리는 MMU에 물리 주소를 반환시켜줘요.
5. 그리고 MMU는 해당 정보를 TLB에 캐싱하고 이 물리 주소를 기반으로 메인 메모리에 접근해요.
6. 그리고 메인 메모리는 해당 데이터를 CPU에 적재시켜서 프로세스를 수행해요.

페이징 시스템과 공유 메모리

프로세스는 동일한 물리 주소를 가리킬 수 있어요. 실행 중인 프로세스들이 서로 동일한 로직을 수행한다면 굳이 따로 메모리에 적재되서 실행될 거 없이 동일한 공간에서 프로세스를 수행하는거에요. 이렇게 되면 당연히 따로 공간을 만들지 않으니 메모리 절약이 되요.

fork()는 실행 중인 프로세스에게 동일한 자식 프로세스를 만들어줘요. 동일하니까 로직도 같으니 read만 수행한다면 따로 메모리 공간을 할당시킬 필요가 없어, 동일한 공간에서 로직을 수행해요. 이러면 공간 절약과 동시에 메모리 할당할 시간도 절약이 되요.

다만, 특정 프로세스에서 write, 물리 주소에서 데이터가 변경되면 두 프로세스는 서로 다른 로직을 수행해요. 그래서 물리 주소 복사를 이때 수행해서 필요할 때만 공간 할당을 수행해서 효율성을 높여요. 이를 copy-on-write라고 해요.

요구 페이징(Demand Paging)

가상 메모리는 프로세스의 모든 데이터를 메모리에 적재하지 않고 실행 중에 필요한 시점에만 적재한다고 했어요.

💡미리 프로세스와 관련된 모든 데이터를 메모리에 올려 놓고 실행하는 선행 페이징Anticipatory Paging와는 반대 개념이에요.

그렇다면, 더 이상 필요하지 않은 페이지 프레임은 다시 저장매체에 저장을 해야해요. 이때 이를 위한 페이징 교체 알고리즘도 필요해요.

페이지 폴트(Page Fault)

어떤 페이지가 실제 물리 메모리에 없을 때 일어나는 인터럽트Interupt에요. 운영체제가 Page Fault를 발생시키면 해당 페이지를 물리 메모리에 올리는 방식이에요.

문제는 Page Fault가 발생하면 운영체제한테 Trap을 요청하고 이를 저장 매체에서 불러와 메모리에 적재하는 작업을 해요.

아까 언급되었듯이 메인 메모리에 접근하는 시간은 비교적 큰 비용이 든다 했어요. 따라서 향후에 실행 및 참조될 코드와 데이터를 미리 물리 메모리에 올릴 수 있어야 해요. 물론 정확하게 예측하는 건 매우 이상적이긴 하지만 이는 신의 영역이죠(정리하면서 떠올랐는데, 이마저도 머신러닝으로 예측하는 건 어떤가 생각이 드네요 ㅎㅎ).

페이지 교체 정책

운영체제가 특정 페이지를 물리 메모리에 올리려 할 때, 물리 메모리가 다 차게 되면,

1. 기존 페이지 중 하나를 물리 메모리 $\to$ 저장 매체로 내리고,
2. 새로운 페이지를 해당 공간에 올려요.

여기서 어떤 메모리를 내릴 것인가를 정하는 것이 바로 페이지 교체 알고리즘이에요.

FIFO 알고리즘

단순히 처음에 들어온 페이지를 내리고 새 페이지를 해당 공간에 올려요.

최적 교체 알고리즘(Optimal Replacement, OPT)

앞으로 가장 오랫동안 사용하지 않을 페이지를 내려요. 가장 이상적인 알고리즘이라 구현이 어렵고, 일반적인 운영체제에선 구현할 수 없어요. 이를 예측하는건 신의 영역이니까요 ㅎㅎ.

Least Recently Used(LRU) 알고리즘

가장 최근에 사용한 페이지를 교체해요. 한번 사용했으니 또 사용할 일은 없을 것이라는 전제 하에 수행하는 알고리즘이에요. 가장 오랫동안 사용되지 않은 페이지를 교체해요(잘못 알고 있었네요 ㅎㅎ).

Least Frequently Used(LFU) 알고리즘

가장 적게 사용한 페이지를 교체해요. 처음에 초기화한 중요 데이터가 있는 페이지를 교체할 가능성이 있어요.

Not Used Recently(NUR)

각 페이지마다 참조 비트R, 수정 비트M를 쌍으로 묶어서 정보를 유지해요. 참조 여부 $\to$ 수정 여부 순으로, 즉, (0,0), (0,1), (1,0), (1,1) 순으로 페이지를 교체해요.

예를 들면 처음에 1, 2, 3번 페이지가 있어요. 각각 (1,1), (1,0), (1,1)로 구성되어 있어요. 마지막에 4번 페이지를 참조하였는데, 물리 메모리에 공간이 없어요. 그래서 교체 순서 로직에 따라 2번 페이지가 교체가 되요.

교체 알고리즘에 대한 정리는 여기까지에요. 그리고 메모리의 특성에 대해 좀더 알아봐요.

데이터 지역성(Data Locality)

캐시 메모리에 적재된 데이터는 접근하기 빠르지만 공간도 작아서 어떤 데이터를 유지시킬건지 결정하는 일종의 논리가 필요해요.

시간적 지역성(Temporal Locality)

for나 while 같은 반복문에 사용하는 조건 변수처럼 한 번 참조된 데이터는 잠시 후에 또 참조될 가능성이 높다는 원리에요.

공간 지역성(Spatial Locality)

A[0], A[1]과 같은 데이터 배열에 연속으로 접근할 때 참조된 데이터 근처에 있는 데이터가 잠시 후에 사용될 가능성이 높다는 원리에요.

LRU 알고리즘은 이 공간 지역성 특성을 잘 호라용한 케이스라 OPT를 대체하는 교체 알고리즘으로 자주 사용되요.

스레싱(Threshing)

반복적으로 페이지 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무일도 하지 못하는 상황이에요.

세그멘테이션(Segmentation) 기법

페이징 시스템과 비교되는 기법 중하나에요. 실제론 페이징 시스템을 더 많이 사용해요.

가상 메모리를 서로 크기가 다른 논리적 단위인 세그먼트Segment로 분할해요. 같은 크기의 block으로 분할하는 페이징 기법과 다소 상이해요.

페이징 vs. 세그멘테이션

페이징 시스템을 더 많이 활용한다지만, 그렇다고 페이징이 완벽한 건 아니에요. 여기에 Trade-off가 존재해요.

내부 단편화(페이징 기법)

페이지를 블록만큼 데이터가 딱 맞게 채워져 있지 않으면 공간 낭비가 발생해요.

4KB로 페이지를 나눴는데 프로그램이 3KB면 그만큼 1KB를 낭비하게 되는거죠.

외부 단편화(세그멘테이션 기법)

물리 메모리가 원하는 연속된 크기의 메모리를 제공 못하게 되는 경우에요.

세그멘테이션 기법으로 인해 메모리에 남는 찌꺼기 데이터 때문에 공간이 충분히 있음에도 적재를 할 수 없는 상태가 되는거죠.

💡 세그멘테이션, 페이징 모두 하드웨어 지원이 필요해요. 다양한 컴퓨터 시스템에 이식성을 중시하는 리눅스는 페이징 기법을 기반으로 구현되어 있어요.