OS-10) 가상 메모리

topics 700-컴퓨터과학 704 운영체제
types 이론 학습
tags

가상 메모리

사용자 논리 메모리와 물리 메모리의 분리

  • 프로세스는 필요한 부분만 메모리에 올려서 실제로 메모리(물리 주소 공간)에 올라가는 프로세스의 크기를 최소화시키면 됨
    • 나머지는 논리 주소 공간에 올림
  • 물리적으로는 불연속 But 논리적으로 연속
    • 프로세스들이 연속된 물리적 메모리 공간처럼 여기게 만들 수 있음
  • 실제보다 많은 메모리를 사용 가능하게 함
  • 적재 스왑 프로세스에 필요한 I/O 감소

가상 메모리 공간

200

둘 사이의 미사용 공간을 Hole로 두어 사용 가능하게 한다.

Paging

외부 단편화 방지 & compaction의 필요성 제거

400

용어 설명
Frame 물리 메모리를 일정한 크기로 나눈 블록
Page 가상 메모리를 일정한 크기로 나눈 블록
Page Table 물리 주소와 가상 주소를 매핑하는 테이블. 메인 메모리에 유지됨
PTBR (Page-table base register) 페이지 테이블을 가리킨다
PTLR (Page-table length register) 페이지 테이블 크기를 지시한다

Frame과 Page의 크기는 같아야 한다.

주소 변환

500

구성 요소 설명
p (page number) 페이지의 물리 메모리 시작 주소를 저장. 해당 페이지가 할당되는 프레임의 시작 주소. 페이지 테이블의 인덱스
d (page offset) 해당 페이지 내부에 데이터의 인덱스

if 논리 주소 공간 크기 = 2^m and 한 페이지 크기 = 2^n:

  • p = m - n
  • d = n

400

페이지 할당 교체

free frame 하나를 찾아서 할당하거나 교체한다.

Free Frames

  • 빈 프레임을 빈 프레임 리스트에서 정보를 저장하고 있다
  • 할당할 때 빈 프레임 리스트에서 목록을 보고 할당한다

빠른 메모리 접근

하드웨어 캐시로 가능하다.

방식 설명
Associative(연관) 메모리 병렬 검색
TLBs (Translation Look-aside Buffers) 페이지 테이블 캐시

먼저 연관 메모리나 TLBs에 있는지 확인하고 있으면 (hit하면) 바로 물리 주소로 변환하고 아니면 페이지 테이블을 확인한다.

유효 접근 시간 (Effective Access Time)

연관 메모리 검색 시간 = at
적중률 = h
메모리 접근 시간 = mt

EAT = (mt + at) * h + (2mt + at) * (1 - h)

메모리 보호

비트 설명
보호 비트 각 프레임별로 읽고 쓰기 등 권한을 표시
유효-무효 비트 페이지 테이블의 각 항목에 포함됨
  • valid: 연관 페이지가 논리 주소 공간에 속함 = 합법적
  • invalid: 페이지가 논리 주소 공간에 존재하지 않음
  • or PTLR을 사용
  • 보호 위반 시 커널로 트랩 인터럽트를 발생

페이징 메모리 구조

계층적 페이징 (Hierarchical Paging)

논리 주소 공간을 여러 페이지 테이블로 나눔. 페이지 테이블을 다시 페이징한다.

예: Two Level Paging

400

if page 크기 1K and 32bit 기기:

  • page offset(d) = 10 (2^10이니까)
  • page no(p) = 22
  • page no에서 페이지가 두 개이기 때문에 번호가 다시 2개로 나뉜다
  • p1(outer) no = 12, p2(inner) offset = 10
  • forward-mapped page table이라고 함

해시 페이지 테이블 (Hashed Page Tables)

400

  • 가상 페이지 번호가 페이지 테이블로 해시됨
    • 번호를 사용하여 체인을 검색
  • 각 페이지 테이블은 같은 위치로 해싱되는 원소 체인을 가지고 있다
  • 원소: 가상 페이지 번호, 매핑된 프레임 값, 다음 원소를 가리키는 포인터를 저장
  • 64bit 주소를 위해 변형된 방식을 클러스터 페이지 테이블이라 함

역 페이지 테이블 (Inverted Page Tables)

  • 메모리 프레임마다 하나의 페이지 테이블 항목을 할당
  • 프로세스 증가와 관계없이 크기가 고정된 페이지 테이블에 프로세스를 매핑하여 할당
  • 논리 주소에 pid를 추가하여 페이지 테이블에서 인덱스로 찾는 게 아니라 pid를 검색해서 찾는다
  • 최소 공간을 사용하지만 최악의 경우 테이블 전체 탐색이 발생하여 성능 저하가 발생

Demand Paging (요구 페이징)

프로그램 실행 동안 메모리를 적재하는 방법이다.

  • 적재 시 프로세스 전체 또는 필요한 페이지 일부만 메모리로 가져올 수 있음
  • Lazy swapper: 페이지가 필요해지기 전까지 메모리로 스왑하지 않음
  • Valid/Invalid Bit 사용
    • 주소 변환 중 유무효 비트가 i면 페이지 폴트 발생

200

Page Fault

300

Invalid Page 참조 시 MMU가 trap을 발생시킨다. 이후 커널 모드로 들어가고 Page Fault Handler가 실행된다.

처리 순서:

  1. 물리 메모리에서 가용한 프레임을 찾음
  2. 디스크 I/O 요청으로 해당 페이지 프레임을 스왑한다
  3. 페이지가 메모리에 있다는 것을 표시하기 위해 테이블을 재지정한다 → 유효무효 비트 v로 변경
  4. 페이지 폴트 유발한 명령어를 다시 실행

오버헤드가 있다.. 다시 실행해야 함..

많은 페이지 폴트의 문제

문제 설명
Thrashing (스레싱) 충분한 페이지가 없어서 페이지를 스왑인 스왑아웃 하느라 바쁜 상황. 페이지 폴트가 많아지고, 다중 프로그래밍 정도를 높여야 한다고 생각해서 높이면 오히려 CPU 이용률이 줄어듦
Working Set Model 지역성에 기반을 둠. D는 전체 요구 프레임 개수, m은 메모리 사이즈. D > m이면 스레싱 발생

EAT with Fault

p: page fault rate
s: swapout + swap in
m: memory access
po: page fault overhead
ro: restart overhead
pst: page-fault service time = po + ro + s

EAT = (1 - p) * m + p * pst

페이지 교체 알고리즘

문제!

  • 각 프로세스에게 얼마나 많은 프레임을 할당할 것인가?
  • 어느 프레임을 교체할 것인가? → page fault가 작을수록 좋다
알고리즘 설명
FIFO 먼저 들어온 페이지를 먼저 교체. Belady의 모순: 프로세스에게 더 많은 프레임을 줬는데도 페이지 폴트가 더 많이 일어남
OPT (Optimal) 미래에 가장 오랫동안 사용되지 않을 것 같은 페이지를 교체
LRU (Least Recently Used) 과거 가장 오랫동안 사용되지 않았던 페이지를 교체. 카운터나 스택으로 구현 가능
LFU (Least Frequently Used) 각 페이지가 접근된 횟수를 기록하는 카운터를 유지. 접근이 가장 적은 걸 교체
MFU (Most Frequently Used) 접근이 가장 많은 걸 교체

Segmentation

내부 단편화 방지 & 사용자 관점의 메모리 관리 기법

  • 가상 메모리를 서로 크기가 다른 논리적 단위인 세그먼트로 분할하고 메모리를 할당하여 실제 메모리 주소로 변환
  • 각 세그먼트는 연속적인 공간에 저장되어 있음
  • 세그먼트들의 크기가 다르기 때문에 미리 분할할 수 없고 메모리에 적재될 때 빈 공간을 찾아 할당

주소 변환

400

논리 주소는 2tuple로 구성: <segment-number, offset>

세그먼트 테이블: 2차원 물리 주소를 매핑

구성 요소 설명
base 세그먼트가 위치하는 메모리 시작 물리 주소
limit 세그먼트 길이를 지정
STBR (Segment-table base register) 세그먼트 테이블의 메모리 위치를 가리킴
STLR (Segment-table length register) 프로그램이 사용하는 세그먼트 개수를 나타냄
  • 유효 비트와 특권(권한) 관련 정보가 포함된다
  • 코드 공유는 세그먼트 수준에서 일어난다

관련 문서