[Study] 운영체제 아주 쉬운 세가지 이야기 17장~19장

운영체제 아주 쉬운 세가지 이야기 책에 대한 스터디를 진행한다.
이 글에서는 가상화에 대해 다룬 17장부터 19장까지의 내용을 정리한다.

17장. 빈 공간 관리

빈 공간 관리가 어려운 경우는 관리하는 공간이 가변-크기 빈 공간들의 집합으로 구성되어 있는 경우다. (세그멘테이션)
이러한 경우에는 외부 단편화가 존재한다.
이번장에서 이 문제를 해결하고자 한다.

17.1 가정

외부 단편화 방지에 중점을 둔다.
하지만 반대로 내부 단편화 문제가 있을 수 있다.
할당기가 요청한 크기보다 더 큰 메모리 청크를 할당할 경우, 요청되지 않은 공간에 대해 할당 청크의 내부에서 낭비가 발생하기 때문에 내부 단편화라고 한다.

17.2 저수준 기법들

할당기에서 사용되는 기법에 대해 논의한다.

• 분할(splitting) 과 병합(coalescing)
• 할당된 영역의 크기를 빠르고 상대적으로 쉽게 파악할 수 있는 방법
• 빈 공간과 사용 중인 공간을 추적하기 위해 빈 공간 내에 간단한 리스트 구현

분할과 병합

힙의 빈 공간 리스트에 2개의 원소가 있다고 가정한다.
하나는 10 바이트의 빈 세그멘트(바이트 0-9) 이고 나머지는 빈 세그멘트(바이트 20-29) 를 표현한다. 10 바이트를 초과하는 모든 요청은 실패할 것이고 작은 요청은 쉽게 충족할 것이다.

1바이트만 요청하게 된다면 할당기는 분할(splitting) 작업을 수행한다.
두 번째 원소를 사용해서 충족했다고 가정하면 두 번째 빈 공간은 20이 아닌 21에서 시작하고 길이는 9가 된다.

분할데 동방되는 기법은 병합(coalescing) 이다.
힙의 중간에 존재하는 공간을 반환하면 빈 공간들을 병합함으로써 하나의 큰 빈 공간으로 만든다.

할당된 공간의 크기 파악

메모리 영역의 크기를 파악하여 공간을 빈 공간 리스트에 추가하기 위해 할당기는 헤더(header) 블럭에 추가 정보를 저장한다.
여기서 주의할 점으로 빈 영역의 크기는 헤더 크기 + 사용자에게 할당된 영역의 크기로 된다. (n 바이트 + 헤더 크기의 청크를 찾음)
헤더는 다음과 같은 정보들을 저장할 수 있다.

• 할당된 공간의 크기
• 추가의 포인터
  • 해제 속도 향상
• 매직넘버
  • 부가적인 무결성 검사 제공
• 기타 정보

빈 공간 리스트 내장

새로운 노드를 위한 공간을 할당하기 위해 빈 공간 내에 리스트를 구축해야 한다.
요청하기에 충분한 크기가 있다면 요청 크기 + 헤더 크기를 충족하는 청크와 빈 청크 두 개로 분할한다.

메모리 반환이 일어나면 라이브러리는 빈 공간의 크기를 파악하고 빈 청크를 빈 공간 리스트에 삽입한다.
그리고 단편화가 발생되지 않도록 리스트를 순회하면서 인접한 청크를 병합한다.

힙의 확장

대부분의 전통적인 할당기는 적은 크기의 힙으로 시작하여 부족하면 운영체제에게 메모리를 요청한다.
할당기는 힙을 확장하기 위해 특정 시스템 콜(sbrk)을 호출한다.

17.3 기본적략

할당기는 속도가 빠르고 단편화를 최소로 해야 한다.
빈 공간 할당을 위한 몇 가지 기본 정책에 대해 알아본다.

최적 적합(Best Fit)

• 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 메모리 청크를 찾음
• 후보자 그룹중 가장 작은 크기의 청크 반환 (최적 청크, 최소 적합)

장점

• 공간 낭비 최소화
• 빈 공간 리스트를 한번만 순회하면 정확한 블럭을 찾음

단점

• 정교하지 않은 구현은 항상 전체 검색하기 때문에 성능 저하

최악 적합(Worst Fit)

• 최적 적합의 반대
• 가장 큰 빈 청크를 찾아 요청된 크기 만큼만 반환하고 남은 부분은 빈 공간 리스트에 유지

장점

• 최적 적합 방식에서 발생되는 작은 청크 방지

단점

• 항상 빈 공간 리스트 전체를 탐색하는 오버헤드 존재

최초 적합(First Fit)

• 요청보다 큰 첫 번째 블럭을 찾아 반환

장점

• 전체 탐색할 필요가 없어서 속도가 빠름

단점

• 리스트 시작에 작은 객체가 많이 생길 수 있음
  • 빈 공간 리스트 순서 관리 필요 (ex. 주소-기반 정렬, address-based ordering)

다음 적합(Next Fit)

• 리스트 처음부터 탐색이 아닌 마지막으로 찾았던 원소를 가리키는 추가의 포인터 유지
• 전체 탐색을 하지 않기 때문에 최초 적합의 성능과 비슷

장점

• 빈 공간 탐색을 리스트 전체에 균등하게 분산
• 첫 부분에만 단편이 발생하는 것을 방지

17.4 다른 접근법

기본적인 접근 방식외에도 메모리 할당을 향상시키 위한 방법에 대해 알아본다.

개별 리스트

• 별도의 개별리스트(segregated list)
• 자주 요청하는 크기가 있다면 그 크기의 객체를 관리하기 위한 별도의 리스트 유지

장점

• 단편화 가능성 감소
  • 특정 크기의 요청을 위한 메모리 청크를 유지하기 때문
• 요청된 크기의 청크만 존재하여 할당과 해제 요청을 신속히 처리

단점

• 지정된 크기의 메모리 풀과 일반적인 풀에 얼만큼 메모리 할당을 해야할지 결정하는 추가적인 오버헤드 존재
  • 슬랩 할당기(slab allocator) 는 이문제를 해결 (할당된 캐시공간이 부족하면 추가 슬랩 요청)

버디 할당

• 이진 버디 할당기(binary buddy allocator) 합병을 간단히 하는 방법 중 하나임
• 빈 메모리는 2의 거듭제곱 크기로 생각하고 메모리 요청이 발생하면 충분한 공간이 발견될 때까지 빈 공간을 2개로 분할

장점

• 블럭이 해제될 때는 다음 블럭이 비어있는지 확인하고 합병하는 식으로 재귀 합병이 발생됨

단점

• 2의 거듭제곱 크기만큼의 블럭만 할당되어 내부 단편화 발생될 수 있음

기타 아이디어

위의 방식들은 확장성에 문제가 있음
빈 공간들의 개수가 늘어갈수록 리스트 검색이 느려질 수 있음 정교한 할당기는 복잡한 자료구조를 사용하여 이 비용을 줄임

• 균형 이진트리(balanced binary tree)
• 스플레이 트리(splay tree)
• 부분 정렬 트리(partially ordered tree)

18장. 페이징: 개요

공간 관리 문제를 해결하기 위한 방법에는 두 가지가 있다.

• 세그멘테이션 기법
  • 가변 크기의 조각들로 분해하는 것
  • 단편화(fragmented) 가 발생될 수 있음
• 페이징 기법
  • 프로세스 주소 공간을 고정 크기의 조각(페이지, page)으로 분할
  • 상응하는 물리메모리는 페이지 프레임(page frame) 이라는 고정 크기의 슬롯 배열으로 생각
  • 프레임에는 하나의 가상 메모리 페이지 저장 가능

18.1 간단한 예제 및 개요

주소 공간의 총 크기는 64바이트이면서 4개의 16바이트 페이지로 구성된 작은 주소 공간을 가정한다.
물리 메모리는 고정 크기의 슬롯들로 구성된다.
가상 주소 공간의 페이지들은 위 그림과 같이 물리 메모리 전체에 분산 배치되어 있다.

운영체제는 주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위해 프로세스마다 페이지 테이블(page table) 자료 구조 유지
페이지 테이블은 주소 공간의 가상 페이지 주소 변환(address translation) 정보 저장 (역 페이지 테이블(inverted page table) 라는 예외 기법도 존재)

프로세스가 생성한 가상 주소 변환을 위해 가상 주소를 가상 페이지 번호(virtual page number, VPN) 와 페이지 내의 오프셋 2개의 구성요소로 분할한다.
위 예에서 가장 주소 공간의 크기가 64바이트 이므로 가상주소는 6비트가 필요하다.
주소 공간은 16바이트 이기 때문에 페이지는 4개를 선택해야 하므로 최상위 2비트가 VPN 을 가지게 된다.
나저미 비트는 오프셋 으로 바이트의 위치를 나타낸다.

가상 페이지 번호와 페이지 테이블의 인덱스를 이용하면 물리 프레임 번호(physical frame number, PFN) 혹은 물리 페이지 번호(phsyical page number, PPN) 를 알 수 있다.

페이징 장점

• 유연성
  • 프로세스의 주소 공간 사용방식과 상관 없이 효율적으로 주소 공간 개념 지원
• 빈 공간 관리의 단순함
  • 주소 공간을 물리 메모리에 배치를 원한다면 비어있는 페이지만 찾으면 됨
  • 운영체제는 페이지의 빈 공간 리스트를 유지하며 리스트의 첫 페이지 목록을 선택

18.2 페이지 테이블은 어디에 저장되는가

페이지 테이블은 세그멘트 테이블에 비해 매우 커질 수 있다.
물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위한 페이지 테이블 항목(page table entry, PTE) 이 메모리를 많이 차지할 수 있다.
그래서 각 프로세스의 페이지 테이블을 MMU 보다 메모리에 저장한다. (디스크에 스왑될 수 있음)

18.3 페이지 테이블에는 실제 무엇이 있는가

페이지 테이블은 가상 주소 (또는 가상 페이지 번호)를 물리 주소(물리 프레임 번호)로 매핑하는데 사용되는 자료다.
간단한 형태로는 선형 페이지 테이블(linear page table) 이다. 운영체제는 가상 페이지 번호(VPN) 으로 배열 항목에 접근하고 페이지 테이블 항복(PTE) 를 검색하여 물리 프레임 번호(PFN) 를 찾는다.

• Valid bit
  • 특정 변환의 유효 여부 표현 (ex. 스택과 힙 사이의 미사용된 공간은 무효(invalid) 로 표시)
  • 무효로 표시된 메모리에 접근하면 운영체제는 트랩 발생
• protection bit (P)
  • 페이지 읽기, 쓰기, 실행 가능 여부를 표시
  • 허용되지 않은 방식이라면 트랩 발생
• present bit
  • 물리 메모리에 있는지 디스크에 있는지 가리킴 (스왑 아웃 여부)
• dirty bit (D)
  • 메모리에 반입된 후 페이지 변경 여부
• reference bit (또는 access bit, A)
  • 페이지가 접근되었는지 추적하기 위함
  • 페이지 교체 알고리즘에 사용

18.4 페이징: 너무 느림

페이지 테이블의 크기가 메모리 상에 크게 증가할 수 있어서 처리 속도가 저하될 수 있다.
시스템은 프로세스의 페이지 테이블에서 적절한 페이지 항목을 가져오고, 변환 수행 후, 물리 메모리에서 데이터를 탑재한다.

페이지 테이블 베이스 레지스터(page table base register) 가 페이지 테이블의 시작 주소를 저장한다고 가정한다.
모든 메모리 참조에 대해 페이지 테이블에서 변환 정보를 반입해야 하기 때문에 메모리 참조가 많이 발생된다.
그래서 페이지 테이블로 인해 시스템이 느려질 수 있으며, 많은 메모리를 차지하게 된다.

18.5 메모리 트레이스

페이징을 사용했을 때 메모리 접근이 많이 발생된다. (ex. 페이지 테이블 접근, 데이터 및 명령어 접근) 간단한 코드에도 실제 응용 프로그램의 메모리 동작은 굉장히 복잡하게 발생된다.

19장. 페이징: 더 빠른 변환 (TLB)

페이징은 성능 저하를 유발할 수 있다.
주소를 빠르게 변환하여 실행 성능을 개선하기 위해 메모리 관리부(memory-management unit, MMU) 의 일부인 변환-색인 버퍼(translation-lookside buffer, TLB) 라는 하드웨어의 도움을 받는다.
TLB는 가상 주소-실주소 변환 정보를 저장하는 하드웨어 캐시다. (주소-변환 캐시(address-translation cache) 라고도 함)

19.1 TLB의 기본 알고리즘

TLB 에 변환 정보가 있는 경우(TLB 히트)

1. 가상 주소에서 가상 페이지 번호(virtual page number, VPN) 추출
2. VPN 의 TLB 존재 여부 검사 (존재하면 TLB 히트, 변환 값을 가지고 있음)
3. TLB 에서 페이지 프레임 번호(page frame number, PFN) 추출
4. 페이지 접근 권한 검사
5. 가상 주소의 오프셋과 합쳐 원하는 물리 주소(PA) 구성 후 메모리 접근

TLB 에 변환 정보가 없는 경우(TLB 미스)

1. 가상 주소에서 가상 페이지 번호(virtual page number, VPN) 추출
2. VPN 의 TLB 존재 여부 검사 (존재하지 않으면 TLB 미스)
3. 변환 정보를 찾기 위해 페이지 테이블 접근
4. 가상 메모리 참조가 유효하고 접근가능 하면 변환 정보를 TLB로 읽어옴
5. TLB 가 갱신되면 명령어 재실행

19.2 예제: 배열 접근

• 공간 지역성(spatial locality) 으로 성능 개선 가능
  • 페이지에 한번 접근하면 인접한 항목도 같은 페이지에 존재하기 때문에 TLB 히트
  • 페이지 크기가 두 배가 되면 미스 횟수 감소 (일반적으로 페이지 크기는 4KB)
• 시간 지역성(temporal locality) 으로 성능 개선 가능
  • 한번 참조된 메모리 영역이 짧은 시간 내에 재 참조될 가능성이 높음

19.3 TLB 미스는 누가 처리할까

미스 처리를 담당하는 방법은 두 가지가 있다.

하드웨어 관리 TLB

• CISC(complex instruction set computers) 기반 컴퓨터
• 인텔 x86 CPU 가 대표적인 예로 멀티 레벨 페이지 테이블(multi-level page table) 을 사용

1. 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾음
2. 필요한 변환 정보 추출
3. TLB 갱신
4. TLB 미스가 발생한 명령어 재실행

소프트웨어 관리 TLB

• RISC(reduced instruction set computing) 기반 컴퓨터
• 하드웨어 변경없이 페이지 테이블 구조를 자유롭게 변경할 수 있음
• 하드웨어는 할 일이 별로 없기 때문에 단순함

1. TLB 에서 주소 찾는 것을 실패하면, 하드웨어 예외(exception) 시그널 발생
2. 예외를 받은 운영체제는 명령어 실행 중지
3. 실행 모드를 커널모드로 변경하여 커널 코드 실행 준비
4. 트랩 핸들러(trap handler) 실행
   • 시스템 콜 호출 시 다음 라인부터 실행되는 것과 다르게 트랩을 발생시킨 명령을 다시 실행 (TLB 히트)
   • TLB 미스가 무한 발생되지 않도록 주의 필요
5. 페이지 테이블 검색하여 변환 정보 찾기
6. TLB 접근 가능한 특권 명령어(privileged instruction)를 사용하여 TLB 갱신 후 리턴

19.4 TLB의 구성: 무엇이 있나?

일반적인 TLB 는 32, 64, 128 개의 엔트리를 가지며, 완전 연관(fully associative) 방식으로 설계된다.
변환 정보는 TLB 내 어디든 위치할 수 있으며, 변환 정보 검색은 병렬적으로 수행된다.

VPN | PFN | 다른 비트들

TLB 의 각 항목에는 가상 페이지 번호(VPN) 와 물리 페이지 번호(PFN) 가 존재한다.
비트들에는 다음과 같은 정보들이 있다.

• valid bit : 유효한 변환 정보인지를 나타내는 비트
• 보호(protection) 비트: 페이지가 어떻게 접근될 수 있는지 나타내는 비트
• 주소 공간 식별자(address-space identifier)
• 더티 비트(dirty bit)

19.5 TLB의 문제: 문맥 교환

TLB 를 사용하면 변환 정보는 해당 프로세스에서만 유효하기 때문에 문제가 발생한다.
TLB 가 멀티 프로세스 간의 가상화를 지원하기 위해서는 추가 기능이 필요하다.

다음 프로세스가 실행되기 전 TLB 내용 비우면 된다.
비우는 작엄은 모든 valid bit 를 0으로 설정하는 것이다.
하지만 문맥 교체가 빈번하다면 TLB 미스가 발생되어 성능이 저하될 수 있다.

• 소프트웨어 기반의 시스템
  • 특별한 하드웨어 명령어로 TLB 를 비움
• 하드웨어 기반 시스템
  • 페이지 테이블 베이스 레지스터가 변경될 때 비우기 시작

이 문제를 해결하기 위해 문맥 교환이 발생해도 TLB 를 유지할 수 있도록 주소 공간 식별자(address space identifier, ASID) 필드를 추가했다.
프로세스 식별자(process identifier, PID) 와 비슷한 개념이다.

주소 공간 식별자를 통해 프로세스 별로 TLB 변환 정보를 구분할 수 있다.
운영체제는 문맥 교환이 발생하면 새로운 ASID 값을 정해진 레지스터에 저장한다.

19.6 이슈: 교체 정책

일반적인 TLB 캐시 교체(cache replacement) 정책들을 알아본다.

• 최저 사용 빈도(least-recently-used, LRU)
  • 가장 오랫동안 사용되지 않은 항목을 교체
• 랜덤(random)
  • 교체 대상을 무작위로 선택
  • 잘못된 결정을 할 수 있음
  • 구현이 간단하고 예외 상황의 발생을 피할 수 있음

19.7 실제 TLB

실제 TLB 인 MIPS R4000 구성에 대해 알아본다.
MIPS 는 소프트웨어로 관리되는 TLB 를 사용한다. MIPS 는 32비트 주소 공간에 4KB 페이지를 지원한다.

• VPN: 19비트 할당
  • 전체 주소 공간의 절반만 사용자 주소 공간으로 할당되어 있기 때문
• PFN: 24비트 할당
• ASID: 8비트 할당
• G: 전역비트
  • 프로세스들 간에 공유되는 페이지들을 위해 사용
• C: 3비트 할당
  • 일관성 비트(coherence)
  • 페이지가 어떻게 캐시되어 있는지 판별
• D: 1비트 할당
  • 더티 비트
• V: 1비트 할당
  • 유효 비트
  • 유효한 변환 정보 존재 여부

19.8 요약

TLB 형대 시스템에서 페이징을 사용하기 위한 필수요소다. 하지만 짧은 시간 동안 접근하는 페이지들이 TLB 에 들어갈 수 있는 수보다 많아지면 TLB 미스가 발생되고 느리게 동작하게 될 것이다.
이러한 현상을 TLB 범위(TLB coverage) 를 벗어난다고 한다.

이 현상을 해결하기 위한 방법 중 하나로 더 큰 페이지 크기를 지원하는 것인데,
큰 페이지들을 지원하기 위해서는 데이터베이스 관리 시스템(database management system, DBMS) 같은 프로그램이 주로 사용된다.

또 다른 문제로 CPU 파이프라인에서 TLB 접근은 병목이 될 수 있다.
특히, 물리적으로 인덱스된 캐시(physically-indexed cache) 가 사용될 경우에는 주소 변환이 캐시 접근 전에 이루어져야 하는데 이런 경우 상당히 느려진다.
가상적으로 인덱스된 캐시(virtually indexed cache) 로 일부 성능 문제를 해결하지만 새로운 하드웨어 설계 문제들이 생긴다.