가상 메모리에 대한 짧은 메모

Short Memos on Virtual Memory

Sigrid Jin

9 min readDec 5, 2021

가상 메모리란?

가상 메모리는 물리 메모리의 용량 한계를 극복하려는 목적을 지니고 있다. 예를 들어, 물리 메모리가 100MB인데 200MB의 소프트웨어를 구동하고자 하는 것이다.
당장 필요한 부분만 메모리에 적재시켜 구동하는 방식을 이용한다. 기본적으로 가상 메모리의 용량은 무제한이지만, 실질적으로는 물리 메모리의 용량에 국한된다. 가상 메모리의 용량은 물리 메모리 + 스왑영역이다.

Demanding Paging

페이징이란 논리 메모리 == 가상 주소를 fixed-size로 분할하는 것을 의미하고, 프레임이란 물리 메모리를 fixed-size로 분할하는 것을 의미한다. 참고
페이징 기법은 고정 분할 방식을 이용하는데, 물리 주소 공간을 같은 크기 로 분할하는 것을 의미한다. 페이지와 프레임은 서로 크기가 같으므로, 1:1 매핑이 가능하다. 매핑 내역은 Page Table에 기록된다.
현재 프로세스 실행에 요구되는 페이지만 메모리에 올리는 것을 Demanding Paging이라고 한다. Page Table에는 Valid bit이 추가되어, 해당 페이지-프레임의 메모리 상 존재 여부를 나타낸다. 만약 현재 페이지가 메모리에 적재되어 있다면 1을, 적재되어 있지 않다면 0을 나타낸다.
현재 페이지 2번이 메모리에 적재되어 있지 않고, Valid bit도 0으로 표시되어 있다. 페이지 2번을 메모리에 적재시키는 과정을 한 번 살펴보도록 하자.

CPU에서 P1의 2번째 페이지에 접근하는데 valid bit값이 0이다. 그러면 CPU에 인터럽트 신호를 발생시켜서 OS 내부의 ISR로 점프한 후, 디스크 내부에 있는 프로세스 P1에 있는 2번째 페이지를 메모리에 할당하는 작업을 수행한다.

Page Fault (페이지 실패)

CPU가 접근하려는 페이지가 메모리에 없는 경우이다. 다시 말해서, 페이지 테이블의 valid bit가 0인 경우이다. Page Fault가 발생했을 때 처리하는 과정이다.

2. 해당 페이지가 메모리에 있는 지 보기 위해 valid bit을 확인한다. valid bit이 0이라면, CPU에 인터럽트 신호를 보내어 OS 내부의 해당 ISR로 jump한다.

3. 해당 ISR에서 디스크[backing store]를 탐색하여, 해당 프로세스의 페이지를 찾는다. 해당 페이지를 비어있는 프레임에 할당한다. 페이지 테이블에, 프레임 번호를 설정하고 valid bit이 1로 변경하여 해당 테이블을 갱신한다.

4. 다시 명령어로 돌아가서 실행한다.

Pure Demanding Paging

프로세스가 최초로 실행될 때는 어떤 페이지가 필요한지 알 수 없으므로, 아무 페이지도 올리지 않는다.
그러므로 프로그램을 실행하자마자 page fault가 발생한다. 즉, 순수하게 필요한 페이지만 올리는 것을 말한다.
Pure Demanding Paging의 장점은 메모리를 최대한 효율적으로 사용할 수 있다. 하지만 시작부터 page fault가 발생하므로 속도 면에서 느리다.

Pre-paging

pure demanding paging과 반대 개념이다.
프로그램을 실행할 때 필요할 것이라 판단되는 페이지를 미리 올리는 것이다.
장점은 page fault가 발생할 확률이 적으므로 속도면에서 빠르지만, 단점으로 미리 올라간 페이지를 사용하지 않는다면 메모리가 낭비된다.

Swapping & Demanding Paging

공통점은 둘 다 메모리와 backing store 사이를 서로 오고 가는 기능을 수행한다.
차이점은 Swapping은 프로세스 단위로 이동하고 Demanding Paging은 페이지 단위로 이동한다.

Effective Access Time

Demanding Paging은 페이지 테이블에 해당 페이지가 없으면 backing store에서 메모리로 가져오는 과정이 있다. 따라서, 페이지 테이블에 해당 페이지가 있을 때와 없을 때 시간 차이가 발생한다.
이러한 시간 차이를 고려하여 평균적으로 어느 정도 소요되는지 계산하는 것을 유효 접근 시간이라 한다.

p: 페이지 부재 확률(probability of a page fault = page fault rate)
Tm: 메모리를 읽는 시간
Tp: Page fault가 발생했을 때 소요되는 시간(대부분 backing store(디스크)를 읽는 시간이 차지한다.)
T = (1-p)Tm + pTpTm = 200nsec (DRAM)
Tp = 8msec (seek time + rotational delay + transfer time)
T = (1-p)200 + p(8,000,000) = 200 + 7,999,800 * p
p = 1/1,000 => T = 8.2usec (40배 정도 느림)
p = 1/399,990 => T = 220nsec (10% 정도 느림)

페이지 부재의 확률은 극히 낮다. 지역성의 원리(Locality of reference)에 의하기 때문이다. 지역성의 원리는 시간적 지역성, 공간적 지역성이 있다.
시간적 지역성: CPU는 어느 메모리 공간을 읽은 후, 시간이 지나도 그 공간을 다시 읽을 확률이 매우 높다는 것을 의미한다.
공간적 지역성: CPU는 어느 메모리 공간을 읽을 때, 인접한 범위 내에서 읽는다는 것을 의미한다. 특히, 절차적 프로그래밍으로 구현되어 있을 경우 순서대로 읽는 경우가 빈번하다.

Page Replacement

Demanding Paging은 요구되는 페이지만 backing store에서 가져온다. 하지만 프로그램들이 계속 실행함에 따라, 요구 페이지도 계속 늘어나게 된다. 그러다보면, 언젠가는 메모리가 가득 차게 될 것이다.
여기서, 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면, 이미 메모리에 적재되어 있는 backing store로 보내고 — 이를 page-out이라고 한다.
한 편으로, 이미 backing store로 page-out이 된 페이지를 victim page이라고 한다.

Victim Page

그러면 어느 페이지를 탈락시켜야 할 것인가? 메모리에 올라가 있는 페이지 중, CPU에 수정(modify)되지 않는 페이지를 골라야 한다.
수정되지 않은 페이지는 page-out이 될 때, backing store에 쓰기(write) 연산을 하지 않아도 된다. backing store는 읽기(read) 시간도 느리기 때문에, 쓰기 연산까지 하면 시간이 더욱 느려질 것이다.
해당 페이지가 수정되었는 지, 수정되지 않았는지 파악하기 위하여 페이지 테이블에 modified bit(dirty bit)를 추가하여 이를 검사한다. 해당 페이지가 수정되었다면 modified bit을 1로, 수정되지 않았다면 0으로 둔다.
만약 수정되지 않은 페이지가 여러 개가 있다면, 랜덤으로 하거나 FIFO로 하는 등 알고리즘을 경우에 따라 선택할 수 있다.

Other Parameters in Page Table Entry

Page base addresses
Flag bit
Accessed bit: 접근 여부를 알려준다.
Dirty bit: 내용이 수정 여부를 알려준다.
Present bit: 현재 페이지에 할당된 프레임이 있는지를 알려준다.
Read/Write bit: 읽기와 쓰기 권한이 있는지를 알려준다.

페이징 기법의 동적 주소 변환 과정

가상 메모리의 스왑 공간에 있는 가상 주소를 물리 메모리의 실제 주소로 변환하는 과정을 동적 주소 변환 이라고 한다.

가상 주소를 물리 주소로 변환하는 과정

가상 주소 30번지가 어느 페이지에 있는지 찾음 -> 페이지 3의 0번째 위치
페이지 테이블의 페이지 3으로 가, 해당 페이지가 프레임 1에 있음을 알아냄
물리 메모리 프레임 1의 0번째 위치에 접근 -> 가상 주소 30번지의 물리 주소

가상 주소에 값을 저장할 때의 주소 변환 과정

가상 주소 18번지가 어느 페이지에 있는지 찾음 -> 페이지 1의 8번째 위치
페이지 테이블의 페이지 1로 가, 해당 페이지가 프레임 3에 있음을 알아냄
프로세스가 저장하려는 값을 프레임 3의 8번 위치에 저장

부족한 물리 메모리의 크기 == 스왑 영역으로 대체
페이지 테이블 수는 프로세스의 크기와 일치

페이지 테이블의 매핑 방식

직접 매핑

페이지 테이블 전체가 운영체제 영역에 위치하는 경우
모든 페이지 테이블이 물리 주소에 있다.
변환속도가 빠르다.
메이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터(PTBR)가 가지고 있다.

연관 매핑

페이지 테이블 전부가 스왑영역에 위치하는 경우
일부 테이블만 무작위로 선정하여 물리 메모리로 가져온다.

Translation Lookasider Buffer (TLB)

가상 메모리 주소를 물리적인 주소를 변환하는 속도를 높이기 위해 사용하는 버퍼
페이지 테이블은 주 기억장치(물리)에 기본적으로 위치하므로, 페이지 테이블에 접근하는 과정 하나와 기억 장치에 필요한 데이터 두 번을 액세스하는 과정이 필요함
TLB가 hit일 경우 가상 주소를 물리 주소로 변환하기 위한 페이지 테이블에 접근할 필요가 없음.
TLB는 메모리가 아닌 프로세서에 내장되어 있기에 훨씬 빠름.
TLB의 프레임 주소를 토대로 데이터를 불러오기 위한 1번의 메모리 접근만 있으면 됨.
탐색 과정: TLB를 사용하여 페이지가 물리 메모리(프레임)에 올려져 있는지 확인한다.