[컴퓨터 시스템] 가상 메모리

키워드

• 페이징

• 메모리 단편화

  • 내부 단편화

  • 외부 단편화

• 페이지 교체 알고리즘

• 세그맨테이션

 

가상메모리

메인 메모리를 보다 효율적으로 더 적은 에러를 가지도록 관리하기 위해 메인메모리의 추상화로서 가상메모리 virtual memory(VM)를 사용한다. 각 프로세스에 하나의 사적 주소 공간으로 존재한다. 때문에 각 프로세스의 주소공간을 다른 프로세스에 의해 침해받지 않도록 하여 에러를 줄일 수 있다. 또한 각 프로세스마다 통일된 주소공간이 존재하게되어 메모리 관리를 단순화 시키는 역할도 한다.

 

프로세스 전체가 메모리에 올라와있지 않아도 실행이 가능하기 때문에 프로세스가 물리 메모리보다 커도 프로그램을 실행시킬 수 있다는 장점이 있다.

 

 

물리 주소 방식

CPU가 메모리에 접근할 때 물리 주소(PA, physical address)를 사용하는 방식을 말한다. 

 

예를 들어, 

CPU가 load instruction을 실행할 때, 유효한 물리 주소를 생성하고 메모리 버스를 통해 메인 메모리에 전달된다. 메인 메모리는 해당 물리주소에 있는 데이터를 CPU에 돌려주고, 레지스터에 복사(저장)한다.

물리 주소 방식으로 load instruction을 수행할 때

가상 주소 방식

CPU가 메모리에 접근할 때 가상 주소(VA, virtual address)를 생성하여 메인 메모리에 접근하는 방식을 말한다.

 

CPU는 가상주소지정으로 가상주소를 생성하여 CPU 칩 내에 있는 메모리 관리 유닛(MMU, memory manage unit)이라는 메모리 번역기에 보낸다. 이는 메인 메모리에 있는 페이지 테이블을 사용하여 가상주소를 물리주소로 번역(주소 번역)한 후, 유효한 물리 주소를 메인 메모리로 보낸다.

가상 주소지정 방식으로 load instruction을 수행할 때

 

내부 단편화(internal Fragmentation)

할당받은 공간에 자투리 공간이 생겼을 때 발생

 

외부 단편화(External Fragmentation)

총 공간을 계산해보았을 때는 요청을 만족할만한 공간이 남았음에도 불구하고 빈 공간들이 단편화되어있어(가능한 공간들이 연속적이지 않아) 실제로는 해당 프로세스를 처리할 수 없을 때 발생

 

세그멘테이션(Segmentation)

세그멘테이션은 논리 단위로 프로세스를 나누기 때문에 페이징에 비해 보호와 공유가 더 효율적이다. 프로세스를 각 프로세스의 논리에 맞춰 세그먼트(segment) 단위로 분할되기 때문에 각 세그먼트의 크기는 같지 않다. 멀티 프로세싱에서 세그멘테이션은 외부 단편화 문제가 발생되기 쉽다. 세그먼트의 크기가 다르기 때문에 메인 메모리에서 hole이 생기고, 서로 다른 크기의 hole이 분산되어있어 메모리 낭비로 이어질 수 있기 때문이다.

 

 

페이징(Paging)

프로세스를 일정한 크기의 페이지로 잘라 메모리에 적재하는 방식

 

페이지(page)
 - Logic address space(가상 메모리)를 분할하여 나온 블럭

프레임(frame)
 - Physical memory를 분할하여 나온 블럭

 

 

페이지 테이블

MMU 내에 존재하는 주소 번역 하드웨어는 가상주소를 물리 주소로 번역할 때마다 페이지 테이블을 참조한다. 페이지 테이블은 물리 메모리(DRAM)에 저장되어 있다. 페이지 테이블은 페이지 테이블 엔트리(PTE, page table entry)의 배열이다.

 

페이징 구조 작동 방식

1. CPU가 현재 실행 해야할 가상주소 생성하여 MMU에 전달한다 (요구 페이징에 의해)

2. MMU 내의 주소 번역 하드웨어에서 가상주소를 읽고, VPN을 통해 Page Table에 있는 특정 PTE : Page Table entry에 접근

3. Page Table에서 해당 PTE의 유효비트를 확인한 후, 탐색하려는 페이지가 물리 메모리(메인 메모리 • DRAM)에 할당 되었는지 확인한다.

   •  1 == valid (페이지 적중): 해당 가상 페이지가 현재 DRAM에 캐시 되어 있는 경우.

   •  0 == invalid (Page Fault): 캐시되어있지 않은 경우 ( 이 과정이 많아질 경우 Thrashing 발생 )

     • Exception : page fault interrupt 발생, Disk에서 직접 해당 페이지를 찾고 이를 물리 메모리에 넣어준다(페이지 교체 알고리즘으로 희생된 페이지 위에 덮어씌운다).

4. PTE의 PPN과 가상주소의 VPO를 결합하여 물리주소가 만들어지고(주소 번역), 이 물리주소를 통해 메인메모리에 접근하여 데이터를 얻어낸다.

가상주소(VA, virtual address)
<VPN : virtual page number, VPO : virtual page offset>

물리주소(PA, physical address)
<PPN : physical page number, PPO : physical page offset>

⁕ PPO == VPO

PTE (Page Table Entry)
<valid bit, PPN : Physical page number>

＊이 과정에서 디스크와 메모리(DRAM) 사이에 페이지를 전송하는 동작을 스와핑(swapping) 혹은 페이징이라고 한다.

＊TLB(Translation Lookaside Buffer)를 통해 2, 3의 과정을 생략할 수 있다. 아래 참조.

 

페이지 교체 알고리즘

 

가상페이지를 메인 메모리에 캐싱할 때 사용되는 DRAM 캐시는 SRAM에 비해 최소 10배 느리기 때문에 상대적으로 DRAM 캐시 미스가 SRAM 캐시 미스에 비해서 손실이 더 크다. 때문에 캐시 미스 발생시 수행되는 페이지 교체 알고리즘이 SRAM 캐시에 대한 처리 과정보다 더 큰 중요성을 두고있다.

 

1. FIFO (First in First out)
   • 가장 먼저 적재된 페이지를 가장 먼저 교체
   • 간단한 구현
2. LRU (Least Recent Used)
   • 가장 오래전에 사용된 페이지 교체
   • 메모리 지역성을 고려했을 때, OPT 방식과 가장 유사한 성능을 보일 수 있다
3. LFU (Least Frequently Used)
   • 가장 적게 사용한 페이지를 가장 먼저 교체
4. NUR (Not Used Recently) 페이지 스왑 알고리즘
   
   • LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체
   • 각 페이지마다 (참조비트, 수정비트) 페어를 두어 교체 우선순위를 만든다. (0, 0) (0, 1) (1, 0) (1, 1) 순으로 페이지 교체

메모리 지역성 (memory locality)

좋은 지역성을 갖는 프로그램들은 동일한 집합의 데이터 원소들에 계속해서 접근하려고 한다. 한마디로 쓰던 것들만 계속 쓰게되면 지역성이 좋다고 이야기할 수있다. 그렇기 때문에 보통 지역성이 좋은 코드가 좀 더 상위 메모리 계층에서 더 많은 데이터에 접근하려고 하는 경향이 있어 실행 속도도 빠르다.

OPT (OPTimal Replacement Algorithm)

페이지 교체 알고리즘 중 하나이다. 앞으로 오랫동안 사용하지 않을 페이지를 예측하여 교체하는 방식인데 실제 OS에서는 구현이 힘들기 때문에 과거 기록을 기반으로 예측하는 LRU 방식이 그 대안이 된다.

 

TLB(Translation Lookaside Buffer) 페이지 정보 캐쉬

 

예를 들어, A라는 가상 주소가 있고 이의 물리 주소가 A'인 데이터가 있다고 가정하자. TLB는 이 정보를 TLB에 캐싱한다. 그리고 다시 CPU가 A라는 가상 주소로 메모리에 접근하려고 할 때, TLB를 먼저 확인하여 물리 주소인 A'를 얻게되면 Page Table을 참조하는 과정을 거치지 않고 바로 page에 접근 가능하다. 즉, 메모리 접근 횟수를 줄일 수 있게 도와주는 역할을 하는 것이 TLB이다.

 

메모리 접근 횟수를 줄이기 위해 고안된 TLB

⁎ CR3 레지스터에는 PTEA (page table entry address)가 담겨있다.