가상 메모리 (Virtual Memory System)

: 메모리가 실제 메모리보다 많아 보이게 하는 기술

• 실제 사용하는 메모리는 작다는 점에 착안해서 고안된 기술
• 프로세스간 공간 분리, 프로세스 이슈가 전체 시스템에 영향을 주지 않을 수 있음

• 실제 각 프로세스마다 충분한 메모리를 할당하기에는 메모리 크기가 한계가 있음
  • 예: 리눅스는 하나의 프로세스가 4GB
  • 통상 메모리는 8GB, 16GB, 32GB
• 폰노이만 구조 기반이므로, 코드는 메모리에 반드시 있어야 함

가상 메모리가 필요한 이유

• 하나의 프로세스만 실행 가능한 시스템(배치 처리 시스템등)에서는 쓸 이유가 거의 없고,

1. 프로그램을 메모리로 로드(load)
2. 프로세스 실행
3. 프로세스 종료 (메모리 해제)

• 여러 프로세스 동시 실행 시스템일 때 필수적으로 자주 쓰인다.

1. 메모리 용략 부족 이슈
2. 프로세스 메모리 영역간에 침범 이슈

기본 메커니즘

• 프로세스는 가상 주소를 사용하고, 실제 해당 주소에서 데이터를 읽고/쓸때만 물리 주소로 바꿔주면 된다.
• virtual address(가상 주소): 프로세스가 참조하는 주소 (0 ~ 4GB)
• physical address(물리 주소): 실제 메모리 주소

CPU가 특정 프로세스의 공간을 참조할 때 가상주로를 먼저 찾게되고, 이 가상주소가 어느 물리주소에 들어가 있는지 알아야 한다. 그래서, 가상주소를 물리주소로 변환을 시켜주는 메커니즘이 가상메모리 안에 있다. 그런데, 매번 가상주소를 참조할 때마다 가상주소→물리주소 변환해야 되기 때문에 시간이 많이 걸릴 수 있다. 이 시간을 짧게 하려고, MMU칩을 사용한다.

• MMU (Memory Management Unit)
  • CPU에 코드 실행시, 가상 주소 메모리 접근이 필요할 때, 해당 주소를 물리 주소값으로 변환해주는 하드웨어 장치
    👉 가상메모리 주소를 물리주소로 빠르게 변환 시켜주는 역할을 한다.

전체 프로세스의 데이터를 특정 시간에 한 번에 다 참조하지 않는다, 일부분만 물리주소에 넣는다. 그 동작이 원활하게 작동하려면 가상주소→물리주소로 변환시키는 메커니즘만 있으면 된다. 추가로, 빠른 변환을 위해 가상 메모리 시스템은 하드웨어 (MMU)지원도 필요로 하다.

가상 메모리와 MMU

• CPU는 가상 메모리를 다루고, 실제 해당 주소 접근시 MMU 하드웨어 장치를 통해 물리 메모리 접근
  

CPU는 무조건 가상메모리만을 참조해달라고 요청하고, 그 가상메모리 주소가 실제 어느 물리 주소에 있는지 MMU가 변환 시켜주고, 그 해당 물리 메모리에 접근을 하여 그 해당 데이터를 CPU에 전달한다.

페이징 시스템(paging system)

가상 메모리 시스템에서 가장 많이 쓰이는 시스템

개념:

• 크기가 동일한 페이지로 가상 주소 공간과 이에 매칭하는 물리 주소 공간을 관리

  👉 프로세스 영역이 0~4GB라고 하면 모두 4KB단위로 page 쪼개고 각각의 page마다 번호를 매긴다.
  그리고 그 페이지 단위로 물리 메모리에 넣는다. 찾을 때도, 페이지 단위로 그 해당 주소를 찾는다.

• 하드웨어 지원이 필요
  • 예) Intel x86 시스템(32bit)에서는 페이지 사이즈 단위를 4KB, 2Mb, 1GB 지원
• 리눅스에서는 4KB 단위로 paging 지원
• 페이지 번호를 기반으로 가상 주소/물리 주소 매핑 정보를 기록/사용

페이징 시스템(paging system)

• 프로세스(4GB)의 PCB에 Page Table 구조체를 가리키는 주소가 들어 있음.
• Page Table에는 페이지 각각의 번호별로 가상주소와 그에 해당하는 물리 주소를 매핑 정보가 있다.
  • 가상주소→물리주소 변환시 전체 Page Table정보를 메모리에 올린다.

• 해당 프로세스에서 특정 가상 주소 엑세스를 하려면
  • 해당 프로세스의 page table에 해당 가상 주소가 포함된 page번호가 있는지 확인
  • page 번호가 있으면 이 page가 매핑된 첫 물리 주소를 알아내고(p')
  • p' + d가 실제 물리 주소가 됨

페이징 시스템 구조

• page또는 page frame: 고정된 크기의 block(4KB)
  • 데이터 사이즈가 1KB여도 물리 메모리에 넣을 땐 4KB 블록으로 들어간다 (3KB는 공란으로)
• paging system
  • 가상 주소 v = (p, d)
    • p: 가상 메모리 페이지
    • d: p안에서 참조하는 위치 (변위/오프셋)

• 예) 페이지 크기가 4KB
  • 가상 주소의 0bit에서 11bit가 변위(d)일 경우,
  • 12bit 이상부터가 페이지 번호가 될 수 있음

그림 예시

페이징 시스템과 MMU(컴퓨터 구조)

• CPU는 가상 주소 접근시
  • MMU 하드웨어 장치를 통해 물리 메모리 접근

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

다중 단계 페이징 시스템

• 32bit 시스템에서 4KB 페이지를 위한 페이징 시스템은

  • 하위 12bit는 오프셋
  • 상위 20bit가 페이징 번호이므로, 2^20(1048576)개의 페이지 정보가 필요함

• 페이징 정보를 단계를 나누어 생성 (page directory만듦)

  • 필요없는 페이지는 생성하지 않으면, 공간 절약 가능

• 페이지 번호를 나타내는 bit를 구분해서, 단계를 나움 (리눅스는 3단계, 최근 4단계)

MMU와 TLB(컴퓨터 구조)

• MMU가 물리 주소를 확인하기 위해서 메모리를 갔다와야 함

(1) CPU가 가상메모리를 요청하면,
(2) MMU가 CR3레지스터 값을 가지고 Page Table에 가서
(3) 물리주소를 가지고 올 것이고,
(4) 그 물리주소에 MMU가 접근해서,
(5) 해당 페이지의 해당 데이터를 CPU에 전달한다.

문제는 레지스터를 처리할 때보다 메모리에 왔다갔다 하는 시간이 더 많이 걸린다. 이것을 해결하기 위해서 별도의 하드웨어를 놓는다.

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

(3') 메모리에서 얻은 물리주소를 TLB에 저장을 한다
👉 최근에 가상주고가 물리주소로 변환된 정보를 TLB에 넣어둠.

(1') CPU가 가상주소를 요청하면, MMU는 TLB를 검색해보고,
(4') 만약 동일한 물리주소가 있다면, 2번 3번 과정을 안 거치고 물리주소로 바로 메모리에 접근한다.

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

• 프로레스간 동일한 물리 주소를 가리킬 수 있음 (공간 절약, 메모리 할당 시간 절약)

4GB 프로세스A를 통째로 프로세스B로 복사하지 않고 프로세스A가 들고 있는 물리메모리 공간을 프로세스B도 가리키게만 해놓는다. 그러면, 새로운 프로세스를 생성하는 시간을 단축시킬 수 있다.

• 물리 주소 데이터 변경시
  • 물리 주소에 데이터 수정 시도시, 물리 주소를 복사할 수 있음 (copy-on-write)

만약 프로세스A 또는 생로 생성된 프로세스B가 그 해당 물리메로리 공간에 '쓰기'를 할 경우, 프로세스A와 B는 완전히 다른 프로세스이기 때문에 A가 변경한 것을 B가 공유하면 안된다. 그래서, 물리메모리 공간에 따로 복사를 하고 프로세스B의 페이지 테이블에 물리주소만 변경하면 된다.

커널든, 공유 메모리든 공유하는 데이터는 물리메모리에 별도의 공간이 필요 없다. 물리 메모리 공간은 공유가 가능하다. 페이지 테이블에 해당 페이지 물리 주소만 바꾸면 공간 절약이 가능하다.

요구 페이징(Demand(ed) Paging)

• 프로세스 모든 데이터를 메모리로 적재하지 않고, 실행 중 필요한 시점에서만 메모리로 적재함
  • 선행 페이징(anticipatory paging 또는 prepaging)의 반대 개념: 미리 프로세스 관련 모든 데이터를 메모리에 올려놓고 실행하는 개념 (실제로는 일부는 미리 올려 놓음)
  • 더 이상 필요하지 않은 페이지 프레임은 다시 저장매체에 저장, 또는 내려준다 (페이지 교체 알고리즘 필요)

페이지 폴트(page fault)

: 페이지 폴트 인터럽트이다

• 어떤 페이지가 실제 물리 메모리에 없을 때 일어나는 인터럽트
• 운영체제가 page fault가 일어나면, 해당 페이지를 물리 메모리에 올림

페이지3이란 데이터를 가지고 오려고 한다치면, 페이지 테이블에 해당 페이지3에 대한 valid bit가 invalid일 경우, page fault 인터럽트를 운영체제에 날려주고, 해당 인터럽트를 받은 운영체제는 해당 페이지를 물리메모리에 올려준다. 그러면, 페이지 테이블 물리주소와 valid-invalid bit도 업데이터/변경된다.

페이지 폴트와 인터럽트

(2) CR3 레지스터리를 가지고 page tabe에 접근한다.
이 때 valid-invalid bit를 통해 물리주소가 메모리에 저장되어 있는지 확인한다.

ㄴ🔸 만약 물리주소에 저장이 되어 있다면 MMU가 해당 물리주소 접근해서, 해당 페이지의 데이터를 CPU에 전달한다.

ㄴ🔸 만약 메모리에 물리주소가 invalid라면,
(3) page fault 인터럽트가 운영체제로 보내짐

여기서 잠깐❗: OS가 인터럽트를 받으면 IDT에 가서
page fault번호에 대한 OS함수를 호출하게 되고
그 함수가 (4)~ 작업을 한다.

(4) 운영체제는 인터럽트를 처리하기 위해서 해당 프로세스 페이지를 저장매체에서 찾아서,
(5) OS는 그 해당 데이터를 메모리에 올려주고
(6) page table을 업데이트 해준다.
(7) 그리고 CPU에게 다시 실행하라고 요청

생각해보기

• page fault가 자주 일어나면?
  • 실행되기 전에, 해당 페이지를 물리 메모리에 올려야함
    • 시간이 오래 걸림
• page fault가 안 일어나게 하려면?
  • 향후 실행/참조될 코드/데이터를 미리 물리 메모리에 적정하게 올리면 됨
    • 앞으로 있을 일을 예측해야 함 - 신의 영역..
      ㄴ 내가 앞으로 할 행동을 예측하는 것과 같다

페이지 교체 정책 (page replacement policy)

• 운영체제가 특정 페이지를 물리 메모리에 올리려 하는데, 물리 메모리가 다 차있다면?
  • 기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고(저장)
  • 새로운 페이지를 해당 물리 메모리 공간에 올린다.

FIFO

• FIFO Page Replacement Algorithm
  • 물리주소에 가장 먼저 들어온 페이지를 내린다

OPT

• OPTimal Replacement Algorithm) 최저 페이지 교체 알고리즘
  • 앞으로 가장 오랫동안 사용하지 않을 페이지를 내린다
  • page fault가 안 나는 알고리즘이지만, 일반 OS에서는 구현 불가능 - 신의 영역..

LRU

• LRU(Least Recently Used) Page Replacement Algorithm
  • 가장 오래전에 사용된 페이지를 교체
  • OPT 교체 알고리즘이 구현이 불가하므로, 과거 기록을 기반으로 시도

LFU

• LFU(Least Frequently Used) Page Replacement Algorithm
  • 가장 적게 사용된 페이지를 내리자

NUR

• NUR(Not Used Recently) Page Replacement Algorithnm

  • LRU와 마찬가지로 최근에 사용하지 않은 페이지부터 교체하는 기법
  • 각 페이지마다 참조 비트(R)[-읽었는지], 수정 비트(M)[-수정했는지]를 페어로 묶어서(R,M) 정보를 유지한다.
    • (0,0), (0,1), (1,0), (1,1)순으로 페이지 교체
      ㄴ (0,0) 페이지부터 가장 먼저 교체

  스레싱(Thrashing)

• 프로그램을 많이 실행할 경우, 반복적으로 페이지 폴트가 발생해서, 과도하게 페이지 교체 작업이 일어나, 실제로는 아무일도 하지 못하는 상황

  

세그멘테이션

가상 메모리 메커니즘 중 하나인 기법

실제로는, 페이징 시스템이 가장 많이 쓰인다

• 가상 메모리를 서로 크기가 다른 논리적 단위인 세그먼트(Segment)로 분할
  • 예: x86리얼모드 (최대 1GB사용 가능)
    • CS(Code Segment), DS(Data Segment), SS(Stack Segment), ES(Extra Segment)로 세그먼트를 나누어, 메모리에 접근

페이징 기법에서는 가상 메모리를 같은 크기의 블록으로 분할

세그멘테이션 기법

세그먼트 가상주소 (페이징 시스템과 유사)
ㄴ v = (s,d): s는 세그먼트 번호, d는 블록 내 세그먼트의 변위

segmentation vs paging

참고:

• 내부 단편화 (페이지 기법)
  ㄴ 페이지 블록만큼 데이터가 딱 맞게 채워져있지 않을 때 공간 낭비 (4KB 중 1KB 사용하면 3KB 빈공간)

• 외부 단편화 (세그멘테이션 기법)
  ㄴ 물리 메모리가 원하는 연속된 크기의 메모리를 제공해주지 못하는 경우
  ㄴ 자리 조금 채워져 있으면 전부 못 넣음.
  

• 세그멘테이션/페이징 모드 하드웨어의 지원 필요
  ㄴ 다양한 컴퓨터 시스템에 이식성을 중요시하는 리눅스는 페이징 기법을 기반으로 구현