PINTOS 4-5주차 VM

개요

이번 주차에서는 가상메모리(Virtual Memory)에 대해 다루었다. 이 문서에는 operating system: three easy pieces의 VM 내용을 대략적으로 살펴보려 한다.

메로리 가상화란

운영체제가 각 프로세스마다 자신만의 커다란 전용 메모리를 가진다는 환상을 제공하는 것

13 주소 공간의 개념

13.1 초기 시스템

• 초기 컴퓨터에서, 운영체제는 메모리에 상주하는 라이브러리의 집합이었을 뿐이다

13.2 멀티프로그래밍과 시분할

• 멀티 프로그래밍(multi-programming)의 시대가 되어 컴퓨터를 공유하기 시작했다
• 프로세스 전환을 통해 CPU의 이용률, 효율성을 개선했다.
• 시분할(time-sharing)의 시대, interactivity의 중요성 부각
• 여러 프로그램이 메모리에 동시에 존재하면서 보호(protection)가 중요한 문제로 부각

13.3 주소 공간

• 사용하기 쉬운 메모리 개념
• 주소공간은 실행 프로그램의 모든 메모리 상태를 가짐
• 코드, 스택(함수 호출 지역변수, 인자, 반환 값 등), 힙(동적 할당) 등
• 실제로는 변환되어 임의의 물리 주소(physical address)에 탑재

13.4 VM의 목표

1. 투명성(transparency): 실행 중인 프로세스가 가상 메모리의 존재를 인지하지 못하도록 해야 함(오히려 자신의 전용 물리 메모리를 소유한 것처럼 행동해야 함)
2. 효율성(efficiency): 시간, 공간적으로 효율적으로 작동해야 함(멀티 레벨, TLB 등을 통해 구현)
3. 보호(protection): 자신의 주소 공간 밖에 접근할 수 없다

볼 수 있는 모든 주소는 가상 주소이다

• C 프로그램에서 포인터로 출력할 수 있는 주소는 모두 가상 주소이다

14 메모리 관리 API

14.1 메모리 공간의 종류

• 스택: 컴파일러에 의해 할당, 반환이 암묵적으로 이루어지는 자동(automatic) 메모리
• 힙: 할당과 반환이 프로그래며에 의해 명시적으로 처리된다

14.4 흔한 오류

• 메모리 할당 잊어버리기
• 메모리 부족하게 할당받기: 버퍼 오버플로우(buffer overflow)
• 할당받은 메모리 초기화하지 않기
• 메모리 해제하지 않기: 메모리 누수(memory leak)
• 메모리 사용이 끝나기 전에 메모리 해제하기
• 반복적으로 메모리 해제하기
• free() 잘못 호출하기

15 주소 변환의 원리

• 효율성: 하드웨어 지원 활용
• 제어: 응용 프로그램이 자기 자신의 메모리 이외의 다른 메모리에 접근하지 못하는 것을 운영체제가 보장
• 유연성: 프로그래머가 원하는 대로 주소 공간을 사용하고, 프로그래밍하기 쉬운 시스템
• 주소 변환(address translation): 가상주소를 실제 존재하는 물리 주소로 변환
• 목표: 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만드는 것

15.3 동적 재배치(베이스와 바운드)

• 2개의 레지스터: 베이스(base) 레지스터, 바운드(bound) 레지스터
• PA(physical address) = VA(virtual address) + base
• 바운드 레지스터는 보호(protection)를 지원하기 위해 존재
• 베이스, 바운드 레지스터는 CPU 칩상에 존재하는 하드웨어(MMU, memory management unit)의 일부

동적 재배치를 위한 하드웨어 요구사항

• 특권모드: 사용자 모드 프로세스가 특권 연산을 실행하는 것을 방지하기 위해 필요
• 베이스/ 바운드 레지스터: 주소 변환과 범위 검사를 지원
• 가상주소 변환, 범위 내 검사: 간단한 회로를 통해 지원
• 베이스/ 바운드 갱신을 위한 특권 명령어: 프로그램 시작 전 운영체제가 베이스, 바운드 레지스터 값을 지정할 수 있어야 함
• 예외 핸들러 등록을 위한 특권 명령어: 운영체제가 예외 처리 코드를 하드웨어에게 알려줄 수 있어야 함
• 예외 발생 기능: 프로세스가 특권 명령어 실행을 시도하거나 범위를 벗어난 메모리의 접근을 시도할 때 예외를 발생시킬 수 있어야 함

15.5 운영체제 이슈

1. 프로세스 생성시, 운영체제는 주소 공간이 저장될 메모리 공간을 찾아 조치를 취해야 한다(free-list 등)
2. 프로세스 종료시, 프로세스가 사용하던 메모리를 회수해 다른 프로세스 혹은 운영체제가 재사용할 수 있어야 한다
3. 문맥교환(context switch)시 베이스, 바운드 쌍을 저장하고 복원해야 한다(PCB: process control block)
4. 예외 핸들러 제공: 운영체제는 부팅할 때 특권 명령어를 사용하여 예외 핸들러를 설치한다

16 세그멘테이션

• 베이스/ 바운드 방식은 메모리 낭비가 심하다(스택과 힙 사이의 사용하지 않는 공간)
• 주소 공간이 물리 메모리보다 큰 경우 실행 어렵다
• 유연성이 없다

16.1 세그멘테이션: 베이스/바운드(base/ bound)의 일반화

• MMU 안에 오직 한 쌍의 베이스/ 바운드 레지스터가 있는 것이 아니라 주소 공간의 논리적인 세그먼트마다 베이스/ 바운드 쌍이 존재한다
• 각 논리 세그먼터(코드, 힙, 스택)마다의 오프셋을 통해 위치 파악
• 세그먼트 폴트(segment fault): 하드웨어가 주소 범위를 벗어났다는 것을 감지하고 운영체제에 트랩 발생

16.2 세그먼트 종류의 파악

• 가상 주소 최상위 2 bit 혹은 1 bit를 세그먼트 구분을 위해 할당
• 가상 주소의 나머지 bit를 해당 세그먼트에서의 offset으로 활용
• 혹은 묵시적(implicit) 접근방식: 주소가 어떻게 형성되었는지를 관찰하여 세그먼트를 결정

16.3 스택

• 스택은 다른 세그먼트와 달리 반대 방향으로 확장
• 간단한 하드웨어가 추가로 필요: 1 bit 할당하여 음의 방향으로 확장한다는 정보 표시
• offset도 다른 방식으로 얻는다: 보수(complement) 계산 방식이랑 비슷하다
• (기존 오프셋 - 최대 세그먼트 크기)로 음(-)의 오프셋을 얻는다

16.4 공유 지원

• protection bit를 통해 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 가능하다
• 코드 세그먼트를 읽기 전용으로 설정하여 주소 공간의 독립성을 유지하면서, 여러 프로세스가 주소 공간의 일부를 공유할 수 있다

16.5 운영체제의 지원

• 문맥교환(context switch)시 세그먼트 레지스터의 저장과 복원
• 미사용 중이 물리 메모리 공간의 관리: free-list
• 외부 단편화(external fragmentation): 물리 메모리 압축(compact), free-list관리 기법(best-fit, worst-fit, first-fit 등)
• 좋은 알고리즘은 외부 단편화를 가능한 줄이는 것이 목표이다
• 외부 단편화를 해결하는 "최선"의 해결책은 존재하지 않는다

세그먼트 문제

• 세그먼트 크기가 일정하지 않기 때문에 외부 단편화 발생(불가피함)
• 유연하지 못함

17 빈 공간 관리

• 메모리 가상화 뿐만 아니라 메모리 관리 시스템의 근본적인 측면
• malloc 라이브러리, 프로세스 주소 공간, 운영체제 자체 등 빈 공간의 관리
• 고정 크기단위로 나뉜 경우(페이징) 빈 공간 관리는 쉽다
• 가변 크기의 빈 공간들의 집합일 경우 외부 단편화 발생

17.2 저수준 기법: 분할과 병합

• 분할: 비교적 큰 빈 공간에 할당할 경우 할당 공간/ 남는 빈 공간으로 분할하여 "남는 빈 공간"을 새로 빈 공간 리스트에 추가한다
• 병합: 새로 해제된 메모리 청크의 인접 청크가 빈 공간이라면 그들을 합쳐 하나의 큰 메모리 청크로 만들어 관리한다
• 할당된 공간 크기의 파악: 추가 정보(meta-data)를 헤더 블록에 저장
• 사실 빈 영역의 크기는 "헤더 크기 + 사용자에게 할당된 영역의 크기"이다

기본 전략들

• 속도가 빠르고 단편화를 최소로 해야 한다
• 어떠한 전략도 잘 맞지 않는 입력(메모리 할당 패턴)을 만나면 성능이 매우 좋지 않을 수 있다
• 최선은 없다, 장단점이 있을 뿐이다

1. 최적 적합(best fit)

• 후보자 그룹(할당 가능한 빈 공간들)에서 가장 작은 크기의 청크를 할당
• 사용자가 요청한 크기에 가까운 블럭을 반환함으로써 공간의 낭비를 줄이려고 노력
• 성능 저하(높은 비용): 항상 전체를 검색

2. 최악 적합(worst fit)

• 후보자 그룹에서 가장 큰 청크에 할당
• 많은 작은 청크를 남기는 대신 커다란 빈 청크를 남기려고 시다
• 성능 저하(높은 비용): 항상 전체를 검색
• 엄청난 단편화 발생

3. 최초 적합(first fit)

• 요청보다 큰 첫 번째 빈 블록 할당
• 속도가 빠르다
• 리스트의 시작 부분(앞부분)에 크기가 작은 객체가 많이 생길 수 있다

4. 다음 적합(next fit)

• 최초적합과 같으나 탐색 시작이 마지막으로 찾았던 원소 다음
• 리스트의 첫부분에만 단편이 집중적으로 발생하는 현상 방지

5. 개별 리스트(segregated list)

• 크기별로 리스트 운용

6. 슬랩 할당기(slab allocator)

18 페이징

• 세그멘테이션(가변 크기 분할)은 단편화 발생
• 페이징은 공간을 동일 크기의 조각으로 분할
• 물리 메모리도 페이지 프레임(page frame)으로 불리는 고정 크기의 슬롯의 배열이라고 간주한다

페이징 개요

• 유연성: 프로세스의 주소 공간 사용 방식(힙, 스택)과 상관 없이 효율적으로 주소 공간 개념 지원
• 빈 공간 관리의 단순함: 모든 비어있는 페이지의 빈 공간 리스트를 관리하고 비어있는 n개의 칸을 찾으면 된다
• 운영체제는 프로세스마다 페이지 테이블(page table)이라는 자료구조 유지(## 페이지 테이블은 프로세스마다 존재한다 ##)

주소 변환 (VA to PA)

• 가상 주소를 두 부분으로 나눔: VA(virtual address) = VPN(virtual page number) + OFS(offset)

• VPN: 해당 페이지의 번호(페이지 테이블에서 몇 번째 페이지인지)

• OFS: 그 페이지에서 몇 번째에 해당하는 위치

• ex) 32bit주소체계: VA = |<--- VPN 20 bit --->|<--- OFS 12 bit --->|

• 주소 변환을 통해 VPN을 PFN으로 변환하고 실제 물리 주소를 만든다: PA(physical address) = PFN(physical frame number) + OFS

• PFN: 해당 물리 프레임의 번호(실제 물리 메모리에서 몇 번째 프레임인지)

• OFS는 동일하다: 해당 프레임에서 해당하는 위치는 (가상 페이지 내부에서의 위치와) 같다

• ex) PA = |<--- PFN n bit --->|<--- OFS 12 bit --->|

페이지 테이블

• 가상주소의 VPN을 물리 주소의 PFN으로 매핑하는 자료구조
• 페이지 테이블은 메모리에 위치하나, 트리 구조로 단계를 높일 경우 디스크에 스왑될 수 있다(중요한 첫 부분은 메모리 상주)
• 선형 자료구조 이외에도 트리 등 고급 자료구조 활용
• 각 PTE(page table entry)에는 VPN에 해당하는 PFN 이외에도 valid bit, protection bit, dirty bit, reference bit, 읽기/쓰기 비트, 사용자/관리자 비트로 각 페이지에 대한 추가 정보를 전한다

페이징 단점

• 느리다: 물리 주소를 알기 위해 페이지 테이블에 접근해야 함(메모리에 2번 접근) --> TLB(하드웨어) 도입
• 메모리 낭비: PTE가 많을 경우 페이지 테이블을 위해 많은 메모리를 할당해야 함 --> 멀티 레벨 페이지 테이블 도입

19 TLB(translation lookaside buffer)

• 주소 변환을 위해 페이지 테이블에 접근하려면 메모리에 한번 이상 접근해야 한다 --> 느리다!!
• 하드웨어의 도움을 통해 실행 속도를 향상: TLB
• TLB: 자주 참조되는 "가상주소 - 실제 주소"의 변환 정보를 저장하는 하드웨어 캐시
• 가상메모리 참조 시, 페이지 테이블(메모리)을 참조하기 전 TLB(빠른 캐시)에 정보가 있는지 먼저 확인
• 지역성 활용

1. 시간 지역성(temporal locality): 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다(반복문)
2. 공간 지역성(spatial locality): 참조된 데이터에 인접한 데이터에 접근될 확률이 높다(배열)

가상 주소 참조 순서

1. 가상 주소에서 VPN 추출하여 TLB에 존재하는지 검사 --> TLB 히트 --> 물리 주소 획득
2. TLB 미스의 경우, 페이지 테이블 접근
3. 가상메모리 참조가 유효하고 접근 가능한 경우 해당 정보를 TLB에 갱신
4. 가상 주소 참조 재실행 --> TLB 히트

TLB 미스의 처리

1. 하드웨어의 관리

• CISC(complex instruction set computers)
• 하드웨어 관리 TLB

2. 소프트웨어(운영체제) 관리:

• RISC(reduced instruction set computing)
• 예외 시그널 박생, 커널모드 변경, 트랩 핸들러
• 유연성: 하드웨어 변경 없이 페이지 테이블 구조 변경 가능
• 단순함: 하드웨어가 할 일이 별로 없음, TLB 미스 핸들러가 처리함

TLB valid bit != 페이지 테이블 vaild bit

• TLB valid bit: TLB에 탑재된 정보가 유효한지
• PT valid bit: 해당 페이지가 프로세스에 할당되었는지 여부

TLB의 문제: 문맥 교환(context switch)

• 문맥교환시, 기존 TLB 내용 지우기: TLB valid bit = 0
• 교체 정책: LRU(least-recently-used), 랜덤

20 더 작은 테이블

• 페이지 테이블 엔트리(PTE)가 많아지면 페이지 테이블 자체의 크기가 커져, 메모리를 많이 차지한다

20.1 해법1: 더 큰 페이지

• 페이지를 크게 하면 VPN bit가 줄어들어 PTE가 감소한다
• 다만 페이지 크기가 커지면 페이지 내부의 낭비 공간이 증가할 수 있다(내부 단편화: internal fragmentation)

20.2 하이브리드: 페이징과 세그먼트

• 논리 세그먼트마다 페이지 테이블을 따로 둔다
• 세그먼트마다 베이스/ 바운드 레지스터를 따로 둔다
• 세그먼테이션을 사용하기 때문에 유연하지 못함
• 외부 단편화

20.3 멀티 레벨 페이지 테이블

• 선형 페이지 테이블을 트리 구조로 표현
• 페이지 테이블을 페이지 크기로 나눈다
• 페이지 디렉토리(page directory)를 두어 각 엔트리마다 나뉘어진 페이지 테이블의 할당 여부와 위치를 파악한다
• 장점1: 사용된 주소공간에 비례해서 페이지 테이블 공간이 할당 --> 적은 크기의 페이지 테이블로 주소 공간 표현 가능
• 장점2: 페이지 테이블을 페이지 크기로 분할하여 메모리 관리가 용이함(페이지 테이블을 할당하거나 확장할 때, 빈 페이지를 가져다 쓰면 된다)
• 단점1: 추가 비용 발생(TLB 미스시, 주소 변환을 위해 2번 이상의 메모리 로드 발생)
• 단점2: 복잡도
• 변환 과정

1. VPN 추출하여 TLB에 존재하는지 확인 --> TLB 히트
2. TLB 미스시, VPN에서 페이지 디렉토리 항목 추출 --> 페이지 테이블 참조
3. 페이지 테이블에서 PTE(페이지 테이블 엔트리) 추출 --> TLB에 추가
4. 다시 시도 --> TLB 히트

21 물리 메모리 크기의 극복: 메커니즘(mechanism)

• 큰 주소 공간을 지원하기 위해 운영체제는 주소 공간 중에 현재는 크게 필요하지 않은 일부를 보관해 둘 공간이 필요하다
• 스왑 공간이 추가되면 운영체제는 실행되는 각 프로세스들에게 큰 가상 메모리가 있는 것 같은 환상을 줄 수 있다

21.1 스왑 공간

• 스왑공간: 디스크에 페이지들을 저장할 공간
• swap out: 메모리 페이지를 읽어서 스왑 공간에 쓴다
• swap in: 스왑 공간에서 페이지를 읽어 메모리에 탑재
• 운영체제는 스왑 공간에 있는 모든 페이지들의 디스크 주소를 기억해야 한다
• file-backed 페이지들은 디스크에 원본이 있으므로 스왑 영역 이외에 swap out할 수 있다(원본 영역)

21.3 페이지 폴트(page fault)

• 페이지 폴트: 물리 메모리에 존재하지 않는 페이지에 접근하는 행위
• 페이지 폴트 발생 시, 운영체제로 제어권이 넘어가 페이지 폴트 핸들러(page fault handler)가 실행된다
• 요청된 페이지가 메모리에 없고, 디스크로 스왑되었다면, 운영체제는 페이지를 메모리로 스왑해온다
• 해당 페이지의 스왑 공간상의 위치는 페이지 테이블에 저장되어있다
• 페이지 폴트를 하드웨어로 처리하지 않는 이유는 페이지 폴트로 인한 디스크 접근이 느리기 때문이다
• 그리고 페이지 폴트 처리를 위해 하드웨어가 스왑 공간의 구조, 디스크에 I/O 요청 등 세부 사항을 알아야 한다
• TLB 미스 발생 시, 세 가지의 중요한 경우가 있다

1. 페이지 유효o/ 존재o: TLB미스 핸들러가 PTE(페이지 테이블)에서 PFN을 가져와 TLB 갱신 후 재시도 --> TLB 히트
2. 페이지 유효o/ 존재x: 페이지 폴트 핻들러 실행 --> 물리 메모리에 페이지 탑재 후 재시도
3. 페이지 유효x: 무효한 접근에 대한 트랩 핸들러 실행

• 페이지 폴트의 처리 과정:

1. 탑재할 물리 프레임 확보
2. 교체 알고리즘 실행: 메모리에서 내보낼 페이지 결정 후 여유공간 확보
3. I/O 요청으로 스왑 영역에서 페이지를 읽어온다
4. 페이지 테이블 갱신 후 명령어 재시도
5. TLB 미스 처리 후 명령어 재시드 --> TLB 히트

22 물리 메모리 크기의 극복: 정책(policy)

• 교체 정책(replacement policy): 메모리에 여유 공간이 없을 경우, 내보낼 페이지를 결정하는 방식

22.1 캐시 관리

• 메인 메모리는 시스템의 가상 메모리(VM) 페이지를 가져다 놓기 위한 캐시로 생각할 수 있다
• 캐시 미스의 최소화: 디스크로부터 페이지를 가져우는 횟수를 최소로 만드는 것
• 캐시 히트 횟수 최대화: 접근된 페이지가 이미 존재하는 횟수를 최대로 하는 것
• 평균 메모리 접근 시간(AMAT, average memory access time) = P_hit * T_M + P_miss * T_D
• P_hit(캐시 히트 확률), P_miss(캐시 미스 확률), T_M(메모리 접근 비용), T_D(디스크 접근 비용)
• T_D 디스크 접근 비용이 매우매우 크기 때문에 P_miss를 줄여야한다!
• 캐시 미스를 최대한 줄여야 하는 것이 교체 정책의 목표이다

최적 교체 정책(the optimal replacement policy)

• Belady 선생께서 말씀하시길, "가장 나중에 접근될 페이지를 교체하는는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다"
• 가장 먼 시점에 필요한 페이지보다 캐시에 존재하는 다른 페이지들이 더 중요하다
• 미래를 알 수 없기에 최적 기법의 구현은 불가능
• 다른 정책의 비교 기준으로 사용 --> "정답에 얼마나 가까운지"

FIFO

• 가장 먼저 들어온 페이지부터 교체
• 순차 반복 입력에서 안좋은 성능

무작위 선택(random)

• 내보낼 페이지 무작위로 선택

과거 정보의 사용: LRU(least recently used)

• 미래 예측을 위해 과거 사용 이력 확인
• 지역성의 원칙: 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높을 것
• 순차 반복 입력에서 안좋은 성능
• 구현이 어려움: 어떤 페이지가 가장 최근, 오래 전에 참조되었는지 관리하기 위해 모든 메모리 참조 정보를 기록해야 함
• LRU 근사 정책 출현

LRU 근사 정책

• use bit(reference bit) 사용: 페이지가 참조될 때마다 하드웨어에 의해 use bit = 1로 설정, use bit = 0으로 바꾸는 것은 운영체제의 몫
• clock algorithm: 페이지를 환형 리스트로 구성하고, 페이지 교체 시 현재 바늘이 가리키고 있는 페이지의 use bit 검사
• use bit = 1 이면 최근에 참조된 페이지 --> 0 으로 변경 후 다음 페이지 이동
• use bit = 0 인 페이지를 발견할 때까지 반복 --> use bit = 0 인 페이지는 최근에 참조된 적이 없는 페이지

갱싱된 페이지 고려: dirty bit

• 변경된 페이지 내보낼 때, 디스크에 변경 내용을 기록해야 함
• 더티 페이지(변경된 페이지)를 내보낼 때 추가적인 I/O 필요하기 때문에 깨끗한 페이지(변경되지 않은 페이지)를 내보내는 것 선호
• 이를 위해 dirty bit를 추가하여 페이지 변경 상태를 기록
• 예를 들어, 시계 알고리즘에서 "사용되지 않은 상태(use bit = 0)이고, 깨끗한(dirty bit = 0)인 페이지"를 먼저 찾도록 함

기타 용어들

• 요구 페이징 정책(demanding paging): 페이지가 실제로 접근될 때, 운영체제가 해당 페이지를 메모리로 읽어들인다.
• 클러스터링(clustering), 모으기(gathering): 운영체제가 변경된 페이지를 디스크에 반영할 때, 기록해야 할 페이지들을 모은 후 한번에 디스크에 기록( 디스크는 여러 개의 작은 쓰기 요청을 처리하는 것보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있다)
• 쓰래싱(thrashing): 메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 시스템은 끊임없이 페이징 시도