지금까지 가상 주소 공간이 비현실적으로 작아서 모두 물리 메모리에 탑재가 가능한 것으로 가정하였다. 사실 실행 중인 프로세스의 전체 주소 공간이 메모리에 탑재된 것으로 가정하고 있었다. 이제 !! 가정을 없어지는 순간!!!

우리는 이를 위해서 메모리 계층에 레이어의 추가가 필요하다. 지금까지는 모든 페이지들이 물리 메모리에 존재하는 것을 가정하였다. 하지만 큰 주소 공간을 지원하기 위해서 운영체제는 주소 공간 중에 현재는 크게 필요하지 않는 메모리 일부를 보관해둘 공간이 필요하다. 보통 HDD, SDD가 이용된다.

한 가지 짚고 넘어가야하는 것, 왜 프로세스에게 굳이 큰 주소 공간을 제공해하는가?
→ 편리함과 사용 용이성, 주소 공간이 충분히 크면, 프로그램의 자료구조들을 위한 충분한 메모리 공간이 있는지 걱정하지 않아도 된다. 필요시 메모리 할당을 OS에게 요청하기만하면 된다.

멀티프로그래밍과 사용 편의성 등의 이유로 실제 물리 메모리보다 더 많은 용량의 메모리가 필요하게 되었다. 이것이 현대 Virtual Memory의 역할이다. 이제 그 방식을 배워보자.

즉, 현대 Vritual Memory의 역할은 멀티 프로그램과 사용 편의성에 의해서 물리 메모리보다 더 많은 용량의 메모리를 필요로 한다.

OS는 어떻게 Disk,Ssd를 사용하면서

                         커다란 주소 공간이 있다고 착각을 주게 해줄까?

Swap Space

가장 먼저 할 일은 1. 디스크에 페이지들을 저장할 수 있는 일정 공간을 확보하는 것이다.
이 일정 공간을 → swap space라고 한다. os는 swap space에 있는 모든 페이지들의 디스크 주소를 기억해야한다. → 잊어버리면 안되는게 당연

Swap space의 크기는 매우 중요하다. 시스템이 사용할 수있는 메모리 페이지의 크기를 결정하기 때문이다. 문제를 단순화하기 위해서 ↓
Assumption: Swap space는 매우 가정하자.

예: 물리 메모리와 swap space에는 각각 4개의 페이지와 8개의 페이지를 위한 공간이 존재한다. 이 예에서는 3개의 프로세스 0, 1, 2가 물리 메모리를 공유하고 있다. 이들 세 프로세스는 몇개의 유효한 페이지들만 메모리에 올려 놓았으며 나머지 페이지들은 디스크에 swap out되어있다. 4번째 프로세스 Proc3의 모든 페이지들은 disk로 swap out되어 있어 현재 실행 중이 아니다. swap space 내의 하나의 블럭이 비어있다. 예제를 통해 swap space를 이용하면, 실제 물리적으로 존재하는 메모리 공간보다 더 많은 공간이 존재하는 것처럼 가장할 수 있다는 사실을 알 수 있다.

The Present Bit

디스크에 swap space을 확보했으니 이제 page swap을 위한 기능을 다루자.
Assumption: A hardware기반의 TLB를 사용하는 시스템이 존재한다.

0. 먼저 메모리를 참조되는 가정을 기억해보자.
1. 프로세스가 가상 메모리 참조를 생성한다.
2. (명령어 탑재, 데이터 접근 등) 하드웨어는 메모리에서 원하는 데이터를 가져오기 전에, 우선 가상 주소를 물리 주소로 변환한다.
3. 하드웨어는 먼저 가상 주소에서 VPN을 추출한 후에 TLB에 해당 정보가 있는지 검사한다.(TLB HIT)
   3-1.만약 HIT가 되면 물리 주소를 얻은 후에 메모리에 가져온다.
   3-2.만약 VPN을 TLB에서 찾을 수 없다면?(TLB MISS).
   3-2-1.하드웨어는 페이지 테이블의 메모리 주소를 파악하고, VPN을 인덱스로 하여 원하는 페이지 테이블 항목(PTE)을 추출한다.
   3-2-2.해당 페이지 테이블 항목이 유효하고 관련 페이지가 물리 메모리에 존재하면 하드웨어는 PTE에서 PFN 정보를 추출하고 그 정보를 TLB에 탑재한다.
   3-2-3.TLB 탑재 후 명령어를 재실행한다. 이번에는 TLB에서 HIT된다.

페이지가 디스크로 Swap되는 것을 가능케하려면 많은 기법을 추가되어야한다. ⇒ 그 중 특히, 하드웨어가 PTE에서 해당 페이지가 물리 메모리에 존재하지 않다는 것을 표현해야한다.
하드웨어는 present bit를 사용하여 각 PTE에 어떤 페이지가 존재하는지를 표현한다.
Present bit = 1로 설정되어 있다면, 물리 메모리에 해당 페이지가 존재한다는 것이고 위에 설명한대로 동작한다.
Present bit = 0으로 설정되어있다면, 해당 페이지가 존재하지 않고 디스크 어딘가에 존재한다는 것을 나타낸다. 존재하지 않는 페이지를 접근행위를 일반적으로 PAGE FAULT라한다.
Page fault가 발생하면, Page fault를 처리하기위해 os로 제어권이 넘어간다. page-fault handler가 실행된다.!

The Page Fault!

TLB 미스의 처리 방법에 따라 두 종류의 시스템이 있었다.

1. 하드웨어 기반의 TLB(하드웨어가 페이지 테이블을 검색하여 원하는 변환 정보 찾기)
2. 소프트웨어 기반의 TLB(OS가 처리하는 것)이다.
   둘 중 어느 것이던, page fault가 발생하면 os가 그 처리를 담당한다. os의 page fault handler가 그 처리 매커니즘을 규정한다.

만약 요청된 페이지가 메모리에 없고, 디스크로 스왑되었다면, 운영체제는 해당 페이지를 메모리로 스왑해 온다. → 자연적으로 등장하는 질문이 있다. 원하는 페이지의 위치를 어떻게 파악할까?

많은 시스템들에서 해당 정보 즉 해당 페이지의 스왑 공간상에서의 위치를 페이지 테이블에 저장한다. 운영체제는 PFN과 같은 PTE비트들을 페이지의 디스크 주소를 나타내는 데 사용할 수 있다.
페이지 폴트 발생 시, 운영체제는 페이지테이블 항목에서 해당 페이지의 디스크 상 위치를 파악하여, 메모리로 탑재한다.

디스크I/O가 완료가 되면 운영체제는 해당 페이지 테이블 항목(PTE)의 PFN값을탑재된 페이지의 메모리 위치로 갱신한다. 이 작업이 완료되면 페이지 폴트를 발생시킨 명령어가 재실행된다.

재실행으로 인해 TLB미스가 발생될 수 있다. TLB미스 처리과정에서 TLB값이 갱신된다(이를 피하기 위한 대안으로 페이지 폴트를 처리 시 함께 TLB를 갱신하도록 할 수도 있다).
최종적으로, 마지막 재실행 시에 TLB에서 주소 변환정보를 찾게 되고, 이를 이용하여 물리 주소에서 원하는 데이터나 명령어를 가져온다.

I/O전송 중에는 해당 프로세스가차단된(blocked) 상태가 된다는 것을 유의해야한다. 페이지 폴트 처리 시 운영체제는 다른 프로세스들을 실행할 수 있다. I/O실행은매우 시간이 많이 소요되기 때문에 한 프로세스의I/O작업(페이지 폴트)과 다른 프로세스의 실행을 중첩(overlap)시키는 것은 멀티 프로그램된 시스템에서 하드웨어를최대한 효율적으로 사용하는 방법 중 하나다.

Page Fault Control Flow

1. 페이지가 존재하며 유효한가? 18-21

1-1. TLB 미스 핸들러가 PTE에서 PFN을 가져와 명령어를 재시도(여러번) 한다. → TLB HIT

2. 22-23 페이지가 유효하지만 존재하지 않는 경우→ 페이지 폴트 핸들러가 반드시 실행
   프로세스가 사용할 수 있는 제대로 페이지 이기는 하지만 물리 메모리에 존재하지 않을 수 있다.
3. 페이지가 유효하지 않는 경우
   프로그램 버그 등으로 잘못된 주소에 접근하는 경우의 처리를 나타냄. 13-14
   ptE의 다른 비트는 의미가 없다. 이 경우 os의 트랜 핸들러로 처리한다.

운영체제가 PAGE FAULT 처리

1. OS는 LODE할 페이지를 위한 물리 프레임을 확보한다. 만약 여유 프레임이 없다면 교체 알고리즘을 실행하여 메모리에서 페이지를 내보내고 여유 공간을 확보한다.
2. 물리 프레임을 확보한후, I/O 요청을 통해 스왑 영역에서 페이지를 읽어온다.
3. 이 느린 작업이 완료되면 OS는 페이지 테이블을 갱신하고 명령어를 재시도한다. 재시도 하게 되면 TLB 미스가 발생하고 또한번 재시도하면 TLB히트가 된다.

세그멘테이션을 사용하지 않고 페이지 테이블을 줄이는 방법을 생각해보자.

멀티 레벨 페이지 테이블은 선형 페이지 테이블을 트리 구조로 표현한다.
→ 매우 효율적이기 때문에 현대 시스템에서 사용되고 있다.

멀티 레벨 페이지의 기본 개념:

1. 페이지 테이블을 페이지 크기의 단위로 나눈다.
2. 페이지 테이블의 페이지가 유효하지 않는 항목만 있으면, 해당 페이지를 할당하지 않는다.(할당하지 않는다 → PTE를 만들지 않는다)
   3.Page directory란 자료구조를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다.

페이지 디렉터리는 페이지 테이블을 구성하는 각 페이지의 존재 여부와 위치 정보를 가지고 있다.

좌측 그림은 전형적인 선형 페이지 테이블이다. 페이지 테이블의 중앙부에 해당하는 주소공간을 사용되고 있지 않다. 그러나 페이지 테이블에서 항목들이 할당되어 있다.
우측 그림은 동일한 주소 공간을 다루는 멀티 레벨 페이지 테이블이다. 페이지 디렉터리에는 유효한 페이지가 있다.(첫 번째와 마지막). 유효 페이지 두개는 메모리에 존재한다. 이 예를 통해 멀티 레벨 페이지 테이블의 동작을 좀 더 쉽게 알 수 있다.

선형 페이지 테이블에서 사용되었던 페이지들은 더 이상 필요없고, 페이지 디렉터리를 이용하여 페이지 테이블의 어떤 페이지들이 할당되었는지를 관리한다.
간단한 2 level 테이블에서, 페이지 디렉터리의 각 항목은 페이지 테이블의 한 페이지를 나타낸다.
페이지 디렉터리는 page directory entries, PDE들로 구성된다. 각 항목(PDE)의 구성은 페이지 테이블의 각 항목과 유사하다. 유효(vaild)비트와 page frame number, PFN을 갖고 있다. 실제 구현에 따라 추가 구성 요소가 존재할 수 있다.
하지만, PTE와 유효 비트와 PDE의 유효 비트는 약간 다르다. PDE 항목이 유효하다는 것은, 그 항목이 가리키고 있는 PFN을 통해서 페이지들 중 최소한 하나가 유효하다는 것을 의미한다. 즉, PDE가 가리키고 있는 페이지 내의 최소한 하나의 PTE의 vaild bit가 1로 설정되어 있다. 만약 PDE의 항목이 유효하지 않다면, PDE는 실제 페이지가 할당되어 있지 않을 것이다.

Muti-level page tables 장점

첫째, 멀티 레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다. 그렇기 때문에 보다 작은 크기의 페이지 테이블로 주소 고간을 표현할 수 있다.
둘째, 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다. 페이지 테이블을 할당하거나 확장할 때, 운영체제는 FREE 페이지 풀에 있는 빈 페이지를 가져다 쓰면 된다.
<!— 선형 페이지 테이블은 연속된 메모리 공간을 차지한다. 큰 페이지 테이블 4MB의 경우, 해당 크기의 연속된 빈 메모리를 찾는 것이 쉽지 않다. —> <!!— 멀티 레벨 페이징에서는 페이지 디렉터리를 사용하여 각 페이지 테이블 페이지들의 위치를 파악한다. 페이지 테이블의 각 페이지들이 물리 메모리에 산재해 있더라도 페이지 디렉터리를 이용하여 그 위치를 파악할 수 있으므로, 페이지 테이블을 위한 공간 할당이 매우 유연하다. —>

Muti-level page tables 단점

1. 멀티 레벨 테이블은 추가 비용이 발생한다. TLB 미스 시, 주소 변환을 위해 두번의 메모리 로드가 발생한다.(페이지 디렉터리와 PTE접근을 위해 한번씩). 선형 페이지 테이블은 한 번의 접근만으로 주소 정보를 TLB로 LOAD한다. 멀티 레벨 테이블은 시간(페이지 테이블 접근 시간)과 공간(페이비 테이블 공간)을 상호 절충(time-space-trade-offs)한 예라 할 수 있다.
   즉, 페이지 테이블의 크기를 줄이는데 성공하였으나, 대신 메모리 접근 시간이 증가했다.
   TLB 히트 시(대부분 메모리 접근은 TLB 히트다.) 성능은 동일하지만, TLB 미스 시에는 두배의 시간이 소요된다.
2. 복잡도. 페이지 테이블 검색이 단순 선형 테이블의 경우보다 복잡해진다. 검색을 하드웨어로 구현하느냐 혹은 OS로 구현하느냐 여부와 무관하다. 대부분의 경우, 성능 개선이나 부하 경감을 위해, 우리는 보다 복잡한 기법을 도입한다. 멀티 레벨 페이지 테이블의 경우에는 메모리 자원의 절약을 위해, 페이지 테이블 검색을 좀 더 복잡하게 만들었다.

예제

개념을 이해하기 위해서 예제를 하나 살펴보자.
14bit 가상 주소 공간이 있고 주소 공간은 2^14bit = 16KB 크기를 갖는다. Page는 64Bite를 갖는다고 생각하자. offset은 Page가 64B이므로 2^6이므로 6비트이며 VPN은 14-6 =8이다.
선형 페이지 테이블은 2^8(256)개 ENTRY로 구성된다. 주소 공간에서 작은 부분만 사용된다 하더라도, 선형 페이지 테이블의 크기는 변하지 않는다.

이 예제에서는 가상 페이지 0과 1은 코드. 가상페이지 4와 5는 힙, 가상페이지 254와 255는 스택으로 이용된다. 주소 공간의 나머지 페이지들은 미사용 중이다.

이 주소 공간을 2단계 페이지 테이블로 구성해보자. 선형 페이지 테이블을 페이지 단위로 분할한다. 전체 테이블은 총 256개의 항목을 갖고 있다. 각 PTE는 4바이트라 가정한다. 페이지 테이블의 크기는 1KB(256*4BITE)이다. 페이지가 64바이트라고하면 1KB 페이지 테이블은 16개의 64바이트로 분할된다. 각 페이지에는 16개의 PTE가 있다.
이제 VPN으로부터 페이지 디렉터리 인덱스를 추출하고, 페이지 테이블의 각 페이지 위치를 파악하는 법을 살펴보자. 페이지 디렉터리, 페이지 테이블의 모두 항목의 배열이라는 것을 기억해야한다. VPN을 이용하여 인덱스를 구성하는 법만 찾으면 된다.

먼저 페이지 데릭터리의 인덱스를 만들어보자. 예제의 작은 페이지 테이블은 256개의 항목으로 16개의 페이지로 나뉘어 있다. 페이지 디렉터리는 페이지 테이블의 각 페이지마다 하나씩 있어야하기 때문에 총 16개의 항목이 있어야한다.
결과적으로 VPN의 4개의 비트를 이용하여 디렉터리를 구성하며, 여기서는 VPN의 상위 4비트를 다음과 같이 사용한다.

VPN에서 page-directory index→PDIndex를 추출한 뒤 →
PDEAddr = PageDirBase+(PDIndex*sizeof(PDE))란 간단한 식을 사용하여
page-directory entry, PDE의 주소를 찾을 수 있다.

페이지-디렉터리의 해당 항목이 무효(inavlid)라고 표시되어 있으면, 이 주소 접근은 유효하지 않다. 예외가 발생한다. 해당 PDE가 유효하다면 추가 작업을 해야 한다. 구체적으로 살펴보자. 이 페이지 디렉터리 항목이 가리키고 있는 페이지 테이블의 페이지에서 원하는 페이지 테이블 항목을 읽어 들이는 것이 목표다. 이 PTE를 찾기 위해서 VPN의 나머지 비트들을 사용한다.

이 page-table index PTIndex는 페이지 자체 인덱스로 사용된다. PTE의 주소를 다음과 같이 계산한다.
PTEAdrr = (PDE.PFN << SHIFT) + (PTIndex*sizeof(PTE)). PTE의 주소를 생성하기 위해서는 페이지-디렉터리 항목에서얻은 페이지-프레임번호(page-frame number, PFN)를 먼저 좌측 쉬프트 연산하고 그 값을 페이지 테이블 인덱스에 합산한다.

이 모든 것이 제대로 작동하는지를 보기 위해, 멀티 레벨 페이지 테이블에 실제 값을 넣은 후에 하나의 가상 주소를 변환해보면 알 수 있다.

Bigger Pages

페이지 테이블의 크기를 간단하게 줄일 수 있는 방법이 한 가지 있다. 페이지 크기를 키우면 된다.
32비트 주소 공간에서, 이번에는 16KB 페이지를 가정해보자.
이 때 Offset은162^10 = 2^42^10 =2^14 즉, offset은 14bit가 필요하다.

자연스럽게 나머지 32-14= 18비트가 VPN을 표현하는데 사용한다.
이렇게 18비트의 VPN과 14비트의 offset을 갖게 된다.
Page Table은 VPN수에 의해 정해진다. 각 PTE가 4byte이면 42^18 = 2^20byte = 1MB 즉, Page Table은 1MB가 된다.
기존 테이블 대비 크기가 1/4로 감소된다.( 테이블의 크기가 1/4로 감소한 것은 페이지 크기가 4배 증가했기 때문이다.)
!— 페이지 크기의 증가는 부작용이 있다. 가장 큰 문제는 페이지 내부의 낭비 공간이 증가한다. 이를 내부 단편화 (*internal fragmentation**)라 한다.(할당된 내부에서 낭비가 발생하기 때문이다.)
응용 프로그램이 여러 페이지를 할당 받았지만, 할당 받은 페이지의 일부분만 사용하는 터에, 결국 컴퓨터 시스템의 메모리가 금방 고갈되는 현상이 발생한다. 이런 이유로 많은 컴퓨터 시스템들은 비교적 작은 페이지들을 사용한다. → page가 크면 internal fragmentation이 발생 → 메모리 고갈

하이브리드 접근 방법: Paging & Segment

힙과 스택에서 실제로 전체 공간 중 작은 부분만 사용되는 경우를 생각해보자.
먼저 1KB 크기의 페이지를 갖는 16KB의 주소 공간을 예로 들자(왼쪽 Virtual Address Space).
이 주소 공간을 위한 페이지 테이블은 아래 그림과 같다.

이 예제에서 VPN 0→ 물리 페이지 10번을, VPN 4→ 23번 물리 페이지에 매핑되어 있다. 가상 주소 공간의 끝 부분에 두 개의 스택 페이지 (VPN 14, 15)가 물리 페이지 28번, 4번에 매핑되어있다. 그림을 보면 페이지 테이블 대부분이 비어 있다. 엄청난 낭비가 발생한다. ←(Internal fragmentation)
16KB 크기의 아주 작은 주소 공간에서도 이렇게 발생하는데 32비트 주소 공간에서는 더 심할 것이다. 이를 해결하기 위한 방법을 생각해보자.!!!
프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신(이전 방식),
논리 세그멘트마다 따로 페이지 테이블을 두면 어떨까?

← 뭔 소리여 ㅋㅋㅋ

즉, Code, Heap, Stack Segment에 각각 페이지 테이블을 두는 것이다.
세그멘테이션에서는 세그멘트의 물리 주소 시작 위치를 나타내는 base 레지스터, 크기를 나타내는 bound(limtit) 레지스터가 있다. 우리의 결합 방식에서도 MMU에 비슷한 구조를 사용한다.
base 레지스터는

세그멘트 시작 주소를 가리키는 것이 아니라

세그멘트의 페이지 테이블 시작 주소를 갖는다. 바운드 레지스터는 페이지 테이블의 끝을 나타내기 위해서 사용한다.
예를 보면서 이해해보자. ← 이해가 될까? 휴먼?

가상 주소

4KB 페이지를 갖는 32비트 가상 주소 공간이 4개의 세그멘트로 나누어져 있다고 가정하자.
하지만 이 예제에서는 3개의 세그멘트만 사용하도록하자. 하나는 CODE, 다른 하나는 HEAP, 또 하나는 STACK을 위해서 사용한다. 소속 세그멘트를 나타내기 위해 상위 두 비트를 사용한다.
미사용 세그멘트: 00, CODE: 01, HEAP: 10, STACK: 11을 나타낸다고 가정하자.
↑ 가상 주소는 위 사진과 같이 나타낼 수 있다.

하드웨어에 세개의 base/bound 레지스터 쌍이 CODE와 HEAP, STACK을 위해서 존재한다고 가정하자. 실행 중인 세그멘트 페이지 테이블의 시작 물리 주소를 갖는다. 이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 갖는다. context Switch시(문맥 교환), 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치 값으로 변경된다.

TLB 미스가 발생하면, (하드웨어 기반 TLB에서) 하드웨어는 SN(세그멘트 비트)를 사용하여 어떤 base, bound쌍을 사용할지 결정한다. 하드웨어는 레지스터에 들어 있는 물리주소를 VPN과 다음과 같은 형식으로 조작하여 PTE의 주소를 얻는다.

동작 순서는 눈에 익숙하다. 앞에서 살펴 보았던 선형 페이지 테이블의 작동과 거의 동일하다. 유일한 차이가 있다면 하나의 페이지 테이블 베이스 레지스터를 사용하는 대신 세 개중의 하나의 세그멘트 베이스 레지스터를 사용하는 것이다.

하이브리드 기법에서 핵심은 세그멘트마다 바운드 레지스터가 존재한다는 것이다. 각 바운드 레지스터의 값은 세그멘트의 최대 유효 페이지의 개수를 나타낸다. 해당 세그멘트의 범위가 넘어가는 곳에 대한 메모리 접근은 예외를 발생시키고, 해당 프로세스는 종료될 것이다.
이와 같은 방식으로 선형 페이지 테이블에 비해 메모리 사용을 개선시킬 수 있다. 스택과 힙 사이의 할당되지 않는 페이지들은 페이지 테이블 상에서 (유효하지 않다는 것을 표시하기 위해서) 더 이상 공간을 차지하지 않는다.

문제점

1. 여전히 Segmentation을 사용해야한다. 이전에 언급했듯이 Segmentation은 주소 공간의 사용에 있어 특정 패턴을 가정하기때문에 우리가 원하는 만큼 유연하지 않다. 큰 공간을 커버하지만 드문 드문 사용되는 힙의 경우에는 여전히 페이지 테이블의 낭비가 발생한다.
   즉, Segmentation은 특정 패턴을 가정해야하기때문에 유연하지 않고 힙의 성격과 맞지 않아 페이지 테이블의 낭비가 발생한다.
2. 하이브리드 기법은 외부 단편화를 유발한다. 페이지 테이블의 크기에 제한이 없으며 다양한 크기를 갖는다. 물론 페이지 테이블의 크기는 테이블 항목 크기의 정수배가 되어야한다. 이런 이유로메모리 상에서 페이지 테이블용 공간을 확보하는 것이 더 복잡하다.
   즉, 하이브리드 기법에서는 페이지 크기가 다양하기때문에 외부 단편화가 발생한다는 것.

Faster Translations(TLBs)

Paging은 상당한 성능 저하를 가져올 수 있다.
↑은 프로세스 주소 공간을 작은 고정된 크기, page로 나누고 각 page의 실제 위치(mapping information)을 메모리에 저장한다. 그리고 mapping information을 저장하는 자료구조를 page table이라 한다.
mapping intormaion을 저장을 위해 큰 memroy space를 요구된다.

Address-translation cashe(Translation-lookaside buffer)

TLB는 Memory-management unit, MMU의 일부이다. 자주 참조되는 가상 주소-실주소 변환정보를 저장하는 하드웨어 캐시이다. address-translation chase가 좀 더 적합한 명칭이다.

요즘날엔 MMU와 TLB는 CPU안에 존재한다.

[운영체제] MMU, page table, inverted page table, TLB

MMU와 TLB에 더 자세한 내용

가상 메모리 참조 시

1. 하드웨어는 먼저 TLB에 원하는 정보가 있는지 확인한다.
2. 만약 있다면 page table을 통하지 않고 변환을 (빠르게) 수행한다.
3. 없다면 조금 힘들어진다.

TLB Basic Algorithm

TLB: Address Translation 과정에서 VPN을 PFN으로 변환하려면 Page Table에 접근하여야 한다.
이 과정을 더 빠르게 하기 위해 자주 쓰이는 Translation들을 Memory Management Unit(MMU)에 저장하여 사용하는데 이렇게 저장한 Cache를 TLB라 한다.

위 코드는 Linear page table, 하드웨어로 관리되는 TLB로 구성되어 있다.

기본 알고리즘 정리:

1. Translation 요청이 들어오면 주소값에서 VPN을 추출한다.
2. 해당하는 Translation이 TLB에 있는 지 확인한다.
   3-1. TLB에 있다면 VPN을 PFN으로 변환하여 반환한다. (TLB Hit)
   3-2. TLB에 없다면 Page Table에 접근하여 PFN으로 변환하여 반환한다. (TLB Miss)
   그 후 해당 Translation을 TLB에 업데이트한다

Example: Accessing An Array

배열의 원소의 합을 구하는 예제

int sum = 0;
for(i=0; i<10; i++) sum += a[i];

위 코드는 총 10번의 translation이 발생한다. 하지만 이 때 a[0], a[3],a[7]에서는 TLB Miss가 발생하여 Page Table에서 변환해야하지만 나머지 7번의 접근, 즉 전체 Translation 중 70%에서는 TLB Hit가 발생하여 시간 절약이 가능하다. 이는 배열이 연속된 주소 공간에 있기 때문에 가능하다. 이를
Spatial locality(공간 지역성이라 한다.)

• 풀어쓴 내용
• a[0]은 가상주소 100번이다.→ 하드웨어는 VPN을 추출한다.→ VPN은 06이고, 이 때 TLB는 완전 초기화되어있기때문에(처음이라) TLB MISS가 뜬다. → 그 이후 VPN 06에 대한 Physical page number를 찾아 TLB를 검색한다. →이후 a[1],a[2]는 VPN 06과 같은 page이므로 TLB HIT가 뜬다.
  아래 3-9도 똑같다

배열 원소를 읽는 TLB 동작 중 HIT는 70%였고, 배열이 처음으로 접근되었지만 TLB는 공간 지역성(spatial locality)으로 인해 성능을 개선할 수 있다. (배열의 항목들이 page 내에 서로 인접해 있었기 때문)
page의 크기는 TLB 효용성에 매우 중요한 역할을 한다. PAGE 크기가 두배가 된다면 MISS 횟수가 더 줄어든다. 예제 프로그램이 루프 종료 후에도 배열을 사용한다면. TLB가 모든 주소 변환 정보를 저장할 정도로 크다면, 다 HIT가 뜬다. 이 경우 시간 지역성(temporal locality)로 인해 TLB 히트율이 높아진다.

실제로 많은 프로그램들이 공간 지역성(spatial locality), 시간지역성(temporal locality)을 띄고 있다.

※Spatial Locality: 프로그램이 메모리 x에 접근했다면, 다음번에는 x 근처의 메모리에 접근할 가능성이 높다
※Temporal Locality: 프로그램이 접근했던 메모리는 가까운 시간 내에 다시 접근할 가능성이 높다.

캐싱은 컴퓨터 시스템에서 사용되는 가장 근본적인 성능 개선 기술들 중 하나.
일반적인 경우를 빠르게(make the common case fast)하기 위해 오랜 시간 적용된 방법이다.
하드웨어 캐시 사용의 근본 취지는 명령과 데이터 참조에 있어서 locality을 활용하는 것이다. 일반적으로 지역성에는 두가지가 있다. temporal locality, spatial locality다!!!
temporal locality은 최근에 접근된 명령어 또는 데이터는 곧 다시 접근될 확률이 높다는 사실에 근거한다. for, while 등 반복문을 생각해보자.
spatial locality은 메모리 주소 x를 읽거나 쓰면, x와 인접한 메모리 주소를 접근할 확률이 높다는 사실에 근거한다. 배열을 순차적으로 읽는 프로그램이 spatial locality을 가지는 대표적인 예다.

모든 하드웨어 캐시의 목적은 필요한 메모리 내용을 매우 빠른CPU칩 내의 메모리에위치시키고, 접근 지역성을 최대한 활용하는 것이다. 이 원리는 명령어 캐시, 데이터캐시, 그리고 주소 변환 캐시 등(TLB)모든 하드웨어 캐시에 적용된다,CPU가 메모리내용을 참조할 때, (느린) 메모리를 직접 접근하는 것이 아니라, 우선 캐시에 사본이있는지 먼저 확인한다. 만약 캐시에 원하는 내용이 존재하면 프로세서는 원하는 내용을빠르게 접근할 수 있으며(즉, 몇CPU사이클 내에), 메모리를 접근하기 위해 비싼 시간(수nsec)을 쓰지 않아도 된다

그럼 캐시를 크게 만들면 되지 않을까? 크게 만들면 느려진다. 작으면 크기가 작다. 밸런스가 맞아야 빠르다!

Who Handles the TLB Miss?

TLB Miss 처리는 두가지 방법이 있다. 하드웨어, 소프트웨어.

Hardware-managed TLB(CISC)

하드웨어가 페이지 테이블에 대한 명확한 정보를 가지고 있어야한다. 메모리 상 위치(위 코드의 page-table base register를 통해서)와 정확한 형식을 파악하고 있어야한다.

Miss 발생 시 다음과 같은 일을 한다.

1. Page Table에서 PTE를 찾는다.
2. 필요한 변환 정보를 추출한다.
3. TLB로 갱신한 한다.
4. TLB 미스가 발생한 명령어를 재실행한다.

인텔 x86 CPU가 하드웨어로 관리되는 TLB의 대표적인 예다.
x86 CPU는 multi-level page table을 사용한다.

▪CIRS = complex-instruction set computers

Software-managed TLB(RISC)

1. 하드웨어가 예외(exception) 시그널 발생시킨다. 위 코드 11번째 줄
2. 예외 시그널을 받은 운영체제는 명령어 실행 잠정 중지하고, 실행 모드를 변경하여, 커널 모드로 변경하여 커널 코드 실행을 준비한다.

• 실행 모드를 커널 모드로 변경하는 작업의 핵심은 커널 주소 공간을 접근할 수 있도록 특권 레벨(privilege level)로 상향 조정하는 것이다.

3. 커널 모드로 변경이 되면 Trap handler를 실행한다.
   이때 실행되는 Trap handler는 TLB 미스의 처리를 담당하는 운영체제 코드이다.
4. 트랩 핸들러는 페이지 테이블을 검색하여 변환 정보를 찾고, TLB 접근이 가능한 privileged instruction를 사용하여 TLB를 갱신한 후에 리턴한다.
5. Trap handler에서 리턴되면 하드웨어가 명령어를 실행한다.
6. Trap handler가 TLB를 갱신했으므로 이제는 TLB HIT가 날 것이다.

▪RISC = reduced instruction set computing

두 가지 중요한 사항을 다시 짚어보자.
첫 번째, TLB 미스를 처리하는 트랩 핸들러는 시스템 콜 호출시 사용되는 트랩 핸들러와의 차이가 있다.

System call의 호출의 경우는 Trap handler에서 리턴 후 System Call을 호출한 명령어의 "다음"명령어를 실행한다. 일반적인 프로시저 콜과 동일하다.
TLB의 경우는 다르다. TLB 미스 처리의 경우, Trap에서 리턴하면 Trap을 발생시킨 명령을 "다시" 실행해야하며, 재실행 시에는 TLB에서 히트가 발생한다. 트랩이 발생하면 운영체제는 트랩핸들러가 종료되었을 때 다시 실행을 계속할 명령어 주소(Program Counter 값)를 저장한다.
중요한 사실을 알 수 있다. 운영체제는 트랩 발생의 원인에 따라 현재 명령어의 PC값 혹은 다음 명령어의 PC값을 저장해야한다.

두 번째, TLB 미스 핸들러를 실행할 때, TLB 미스가 무한 반복되지 않도록 주의를 해야 한다. TLB 미스 핸들러를 접근하는 과정에서 TLB 미스가 발생하는 상황이다. 이를 위해 다양한 해법이 존재한다.

1. TLB 미스 핸들러를 물리 메모리에 위치 시키는 것도 한 방법이다. TLB 미스 핸들러의 주소는 '물리' 주소로 표시된다. 이 경우 해당 TLB 미스 핸들러는 unmap되어 있으며 주소 변환이 필요없다.
2. TLB의 일부를 핸들러 코드 주소를 저장하는 데 영구히 할당하는 것이다. 이렇게 되면 TLB 핸들러는 항상 TLB에서 히트된다. 이를 연결(wired) 변환이라 한다.

TLB를 소프트웨어로 관리하는 방식의 주된 장점은 유연성이다. 운영체제는 하드웨어 변경없이 페이지 테이블 구조를 자유로이 변경할 수 있다.

또 다른 장점은 단순함이다. TLB 제어 흐름에서 보는 것과 같이 미스가 발생하였을 때 하드웨어는 별로 할 일이 없다. 예외가 발생하면 운영체제의 TLB 미스 핸들러가 나머지 일을 처리한다.

TLB 구성

일반적인 TLB는 32, 64,128개의 entry를 가지며 fully associative 방식으로 설계된다. fully associative 방식에서 변환정보는 TLB 내에 어디든 위치할 수 있으며, 원하는 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행된다.

TLB의 Entry는 PTE와 비슷하지만 VPN이 index 역할을 할 수 없기 때문에 VPN이 같이 저장되어야 한다. 그리고 뒤 쪽에는 PTE처럼 vaild, protection bit와 같은 flag들이 저장된다.

🔲TLB는 용량이 작기 때문에 여러 프로세스가 나누어 사용해야 하므로 Context Swich가 발생하면 기존에 남아있는 TLB Entry들 때문에 다른 프로세스가 엉뚱한 메모리로 접근하는 것을 막을 방법이 필요하다. → 이를 막기 위해 Context Switch 시마다 TLB를 비우면 되지만 이는 매우 비효율적인 방법이다.

Smashicons 디자인의 무료 벡터 아이콘

OS는 거의 모든 공간 문제를 해결할 때 두가지 방법이 있다. ↓

• Segmetation
  가변 크기의 조각들로 분할하는 것, 공간을 다양한 크기의 청크로 분할 할때 공간 자체가fragmented(단편화) 될 수 있고, 할당은 더 어려워진다.
• Paging
  프로세스의 주소 공간을 고정 크기의 단위로 나눈다. 고정 크기의 단위를 page라 부른다. 이에 맞게 Phsycal Memory를 page frame이라고 불리고 고정 크기의 슬롯의 배열이라고 생각한다.
  각각의 frame에 하나의 가상 메모리 페이지를 저장할 수 있다.

우리의 문제: Page를 사용하여 어떻게 Memory를 가상화할 수 있을까?

간단한 예제 및 개요

총 크기 64bite, 각 page는 16bite 페이지로 구성된 작은 주소 공간을 통해 이해해보자.
단위 이야기 1B = 8bit

Physical Memory는 위와 같이 고정 크기의 슬롯들로 구성되고 위 경우 8개의 page frame, 총 128bite로 이루어진 비현실적인으로 작은 physical memory다. 가상 주소 공간의 page들은 physical memory 전체에 분산 배치 되어있다. (18.1 그림이 phsical memory에 배치되어있다고 생각해보자)

paging은 이전 방식(segmention, base-bound pair)에 비해 많은 장점을 가지고 있다.
가장 중요한 개선은 유연성(flexibility)이다. paging을 사용하면 process의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. - heap, stack이 어느 방향으로 커지는가, 어떻게 사용하는 가에 대해서 가정을 하지 않아도 된다.-
또 다른 장점은 free space 관리의 단순함이다. 예를 들어 OS가 우리의 작은 64bite 주소 공간을 8개의 8 page 물리 메모리에 배치하기를 원한다고 할 때, OS는 비어있는 네개의 page만 찾으면 된다. 아마 이를 위해 OS는 모든 비어 있는 page의 free space list를 유지하고 리시트의 첫 네 개의 페이지를 선택할 것이다. ← 이를 위해서 OS는 모든 비어 있는 페이지의 free list를 유지하고 list의 첫 4개 페이지를 선택할 것이다.

Page table
주소 공간의 각 가상 page에 대한 phsical memory 위치 기록을 위하여 os는 process마다 page table이란 자료구조를 유지한다.
주요 역할: 주소 공간의 가상 페이지 address translation 정보를 저장하는 것이다.
각 페이지가 저장된 physical memory가 어디인지 알려준다. 위에 예제에서는 4개의 항목을 가진다.
(vp 0→ pf 3), (vp 1→ pf 7), (vp2→pf 5), (vp 3→pf2)
vp = virtual page, pf = physical frame

page table은 process마다 존재한다는 사실을 숙지해야한다.

위에 예에서는 다른 프로세스를 실행해야한다면 os는 이 process를 위한 다른 page table이 필요하다. → 새 process의 virtual page는 다른 physical page에 존재하기 때문이다.(공유 page가 없다는 가정하에)

address translation

작은 주소 공간(64bite)을 가진 procee가 다음 메모리 접근을 수행한다고 가정하자.
movl <virtual address>, %eax 구체적으로 의 데이터를 eax 레지스터에 load하는데에 집중하자.
process가 생성한 가상 주소의 변화를 위해 먼저 가상 주소를 VPN(virtual page number)와 page내의 offset 2개의 구성 요소로 분할한다.

Virtual address → Virtual Page Number
→ offset

이 예에서는 address space가 64bite라 각 address space는 6bit가 필요하다 (2^6=64)

Va5가 최상위 비트이고 Va0은 최하위 비트이다. 우리는 page 크기를 알고 있어서 총 16bite 다음과 같이 표기한다.

VPN은 2비트를 가졌고, 나머지 비트(4페이지) offset은 우리가 원하는 bite의 위치를 나타낸다.
21을 이진 형식으로 변환하면 010101을 얻고 이 가상 주소를 검사하고 vpn과 offset으로 나눈다.

VPN에 해당하는 1을 Address Translation을 한다면 7 이진수 → 111을 얻는다.

VPN을 PFN으로 교체하여 교체하여 가상 주소를 변환한다. offset은 그대로다
최종 physical address는 1110101(117)이고 이곳이 load할 데이터가 저장된 정확한 위치다..

Page Table은 어디에 저장될까?

이전 segment talbe이나 base-bound pair에 비해서 Page table은 매우 커질수 있다.
예를들어 4KB 크기의 Page를 가지는 32bit 주소 공간을 생각해보면, 이 가상 주소는 20비트의 VPN과 12 bit의 offset으로 구성된다. 1KB Page 크기를 위해 10Bit가 필요하다. 여하튼 page table크기는 매우 크고 이를 MMU 안에 존재할 수가 없다. 그래서 OS가 있는 곳에 저장되고 점점 os가 차지하는 공간이 커지는 것이다.

Page Table에 무엇이 저장되어있을까?

🛎페이지 테이블은 가상주소를 물리 주소로 mapping하는데 사용되는 자료구조다.
가장 간단한 형태로 linear page table이 있다. PFN(Physical Table Number)을 찾기 위해 VPN(virtual page number)로 배열의 항목에 접근하고 그 항목의 PTE( Page table entry(항목) )를 검색한다.

각 PTE에는 심도 있는 이해가 필요한 비트가 존재한다.
Valid bit: 할당되지 않은 주소 공간 표현
Protection bit: 페이지가 읽기, 쓰기, 실행 중에 어느 것을 허용하는지 표현.
Present bit: 이 페이지가 물리 메모리 혹은 disk에 있는지 표현.
dirty bit: 메모리에 반입된 후 페이지가 변경되었는지 여부를 나타낸다.
reference bit: 때때로 페이지가 접근되었는지를 추적하기 위해 사용된다.

PAGE TABLE은 PAGE TABLE ENTRY로 구성된다.

Free Space Management

새 주소 공간을 만들었더니 듬성 듬성 빈 공간이 생겼어!! Oh my god!! 지져스!
이 빈 공간을 정리를 하고 싶어! 어떻게? 할까..잘하면 돼!!!

모든 메모리 관리 시스템에 대한 근본적인 측면에 대한 논의, 바로 Free space management다!
이 장은 메모리 가상화와는 거리가 조금 멀다.

관리하고 있는 공간이 고정 크기의 단위로 나누어져있다면 관리가 쉽다. 그런 경우 고정 크기 단위의 리스트를 유지하고 클라이언트가 그 중 하나를 요청하면 첫 번째 항목을 반환하면 되기 때문이다.
하지만 그렇게 쉬우면 이 챕터를 하지 않았겠지?

빈 공간 관리가 더 어렵고 흥미로운 경우는 관리하는 공간이 가변-크기 빈공간의 집합으로 구성되어있는 경우다. 영문으로 variable-sized units!
그리고 malloc(), free()에서 처럼 사용자 수준 메모리 할당 라이브러리에서,
Physcial Memory를 Segmentaion으로 관리시 External fragmentation이 발생한다.

단편화 = fragmentation

내부 단편화 Internal fragmentation
일정 크기의 페이지에 프로세스 할당시 프로세스의 크기가 페이지 보다 작을 경우 발생
외부 단편화 External fragmentation
여유 공간이 여러 조작으로 나뉘는 현상

외부단편화와 내부단편화

외부, 내부 단편화

Q. 30바이트의 공간을 메모리 공간에 요청해도, Free space 공간의 합이 30이라도 응 요청이 실패된다. 이게 문제라서 이제부터 Free Space를 관리해보자!

Assumptions

malloc(size_t size) and free(void *ptr)

• malloc(size_t size) takes a single parameter, which is time number of bytes requested by the application.
  free(void *ptr) takes a pointer and frees the corresponding chunk → the user does not inform the library of its size → the library must be able to figure out how big a chunk of memory.

The space for memory allocation is heap.

The generic data structure used to manage free space in the heap is some kind of free list.

• This structure contains references to all of the free chunks of space in the managed region of memory.

Internal fragmentation

• If allocator hands out chunks of memory bigger than that requested, any unasked-for space in such a chunk is considered internal fragmentation.
  We will focus on external fragmentation.

Once the memory is handed out to a client, it cannot be relocated to another location in memory
→ No compaction of free space is possible.

The allocator manages a contiguous region of bytes.

Low-level Mechanisms~!

First, we’ll discuss the basics of splitting and coalescing(병합), common techniques in most any allocator.
Second, we’ll show how one can track the size of allocated regions quickly and with relative ease.
Finally, we’ll discuss how to build a simple list inside the free space to keep track of what is free and what isn’t.

Splitting and Coalescing

A free list contains a set elements that describe the free space still remaining(남아) in the heap.

The free list for this heap would have two elements on it.
One entry describes the first 10byte free segment (bytes 0-9), and one entry describes the other free segment (bytes 20-29)

🏳‍🌈 10바이트를 초과하는 모든 요청은 실패하여 NULL를 반환할 것이다.
→그럼 10바이트보다 작은 값을 요청하면 어떻게 될까????

이 경우 splitting이 일어난다. 요청을 만족시킬 수 있는 빈 chunk를 찾아 이를 둘로 분할한다.
1바이트 요청이 발생하고 allocator가 리스트의 두번째 원소를 사용하여 요청을 충족시켰다고 가정하자. malloc()은 20을 반환하고 최종 리스트는 위 그림과 같이 된다.

요청이 특정 빈 청크의 크기보다 작은 경우 Splitting기법을 사용한다. Splitting에 동반되는 기법은 빈 공간의 coalescing이다.

응용 프로그램이 free(10)을 요청하여 힙 중간 공간을 반환하면 free space가 list에 추가된다.
하지만 10bite 길이의 chunk 3개로 나누어져 있어서 만약 사용자가 20bite를 요청할 시 단순 list 탐색시 빈 청크를발견하지 못하고 실패한다. 탐색: traversal

! allocator가 이 문제를 방지하기 위하여 할 수 있는 일은 memroy chunk가 반환될 때 free space를 병합하는 것이다. < 엄청 간단하지? 그렇지만 이해는 쉽지 않단다. ㅎㅎ..>:
→ 메모리 청크를 반환할 때 청크의 주와 바로 인접한 빈 청크의 주소를 살펴본다. 새로 해제된 빈 공간이 왼쪽의 빈청크와 바로 인접해있다면 그들을 하나의 더 큰 빈 청크로 병합한다.

이 상태가 할당이 한번도 일어나지 않은 최초의 힙 리스트의 모양이다. coalescing 기법을 사용하여 allocator가 커다란 빈 공간을 응용 프로그램에게 제공할 수 있다는 것을 더 보장할 수 있다.

Tracking The Size of allocated Regions 할당된 공간의 크기 파악

free(void ptr) Interface는 size를 매개변수로 받지 않는다. (포인터를 할당받아서 리턴하는걸요?)
*우리는 포인터가 인자로 전달되면 malloc 라이브러리는 해제되는 메모리 영역의 크기를 신속하게 파악하여 그 공간을 빈 공간 리스트에 추가할 수 있다고 가정한다. 이 작업을 보통 allocator는 추가 정보를 header block에 저장한다. header block은 메모리에 유지되며 보통 해제된 chunk 바로 직전에 위치한다.

Ex) ptr이 가리키는 크기 20bite의 할당된 블록을 검토하고 있다.

사용자는 malloc()을 호출하고 그 결과를 ptr에 저장하였다고 가정하자.
예를 들어 ptr = malloc(20); Header는 적어도 할당된 공간의 크기는 저장해야한다(이 경우 20)

typedef struct __header_t{
    int size;
    int magic; // 부가적인 무결성 검사를 제공하기 위한 변수
} header_t; 

void free(void *ptr){
    header_t *hptr = (void *)ptr - sizeof(header_t);
...

↑ 사용자가 free(ptr)을 호출하면 라이브러리는 header의 시작 위를 파악하는 간단한 포인터 연산

헤더를 가리키는 포인터를 얻어내면, 라이브러리는 매직 넘버가 기대하는 값과 일치하는지 비교하여 sanity check를 실시한다. (assert(htpr→magic == 1234567)) 그 다음 새로 헤제된 영역의 크기를 간단한 수학을 토해 계산한다.(즉 헤더의 크기를 영역의 크기에 더함)
<!— 주의할 점이 있다. 빈 영역의 크기는 헤더 크기 더하기 사용자에게 할당된 영역의 크기가 된다.

Embedding A Free List

지금까지 free list의 개념만 다루었지만 이제는 구현을 생각해보자. 보통 새로운 노드를 위한 공간을 할당할 때 malloc()을 호출한다. 하지만 메모리 할당 라이브러리 루틴에서는 불가능하다. 대신 빈 공간 내에 리스트를 구축해야한다.
4096바이트 크기의 메모리 chunck가 있다고 하자. 즉 힙의 크기는 4KB이다. 이를 free list로 관리 하기 위해서는 먼저 list를 초기화해야한다. 처음에 리스트는 (4096-헤더 size)길이의 항목 하나를 가지고 있다.

// 이 list의 노드에 대한 코드
typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

heap을 초기화하고 heap에 free list의 첫 번째 요소를 넣는 코드를 살펴보자. heap은 system call mmap()을 호출하여 얻어진 영역에 구축된다고 가정한다. 이 방법은 유일한 방법은 아니다.

// mmap()이 free list의 chucnk에 대한 포인터를 반환
node_t *head = mmap(NULL, 4096, PROT_READIPROT_WRITE,
        MAP_ANONIMAP_PRIVATE, -1, 0);
head->size = 4096-sizeof(node_t);
head->next = NULL;

이 코드의 실행 후 리스트는 크기 4088의 항목 하나만을 가지게 된다. 매우 작은 힙이다. head 포인터는 이 영역의 시작 주소를 담고 있다. 영역의 시작 주소를 16KB라고 가정하자.

이때 heap의 모양은 위 그림과 비슷할 것이다.
이제 100bite 메모리 chucnk가 요청되었다고 생각해보자.
이 요청을 처리하기 위해 라이브러리는 먼저 충분한 크기의 chunk를 찾는다. 하나의 빈 청크(4088)만이 존재하기 때문에 이 청크가 선택된다. 요청을 처리하기에 충분히 큰 크기, 앞서 말한 것처럼 빈 영역의 크기 더하기 헤더의 크기를 충족시킬 수 있는 청크와 나머지 빈 청크 두 개로 분할한다.

100바이트에 대한 요청이 오면 라이브러리는 기존 하나의 빈 청크 중 108바이트를 할당하고 할당 영역을 가리키는 ptr를 반환한다. 그리고 free()를 사용할 수 있도록 할당된 공간 직전 8바이트에 헤더 정보를 넣는다. 그런 후 하나 남은 빈 노드를 3980바이트로 축소한다.

이제 100바이트씩 3번 할당한 힙을 보자. 이번에는 free()를 통해 일부 메모리를 반환하면 어떤 일이 벌어질까?
free list는 여전히 head가 가리키는 하나의 노드로 구성되어 있지만 세번의 분할 이후 3764로 축소된 모습이다.

이 예제에서 free(16500)을 호출하여 할당 영역 중 가운테 chunck를 반환한다. 16500은 메모리 영역의 시작 주소 16384, 이전 메모리 청크의 크기 108, 해제되는 청크의 헤더 8바이트를 모두 더해서 나온 값이다. 그림에서는 sptr로 나타난다.

라이브러리는 신속히 빈 공간의 크기를 파악하고, 빈 청크를 free list의 헤드 쪽에 삽입한다고 가정한다면 위그림과 동일하다.

이제 빈 공간 리스트의 첫번째 원소는 작은 빈 청크(100바이트크기이며 list의 헤드가 가리킨다.) 두번째 원소는 큰 빈 청크 3764이다. 드디어 우리 리스트가 하나 이상의 원소를 가진다.

마지막으로 마지막 2개의 사용 중인 청크가 헤제된다고 하자. 병합이 없으면 17.7과 같이 작은 단편으로 이루어진 free list가 될 것이다. 해결책은 리스트를 순회하면서 인접한 청크를 Coalescing 하면 된다.

Growing The Heap

heap space가 부족한 경우 단순히 NULL을 반환하면된다. 어떤 경우에도 유일한 대안이다.

졌잘싸다. ㅋㅋㅋㅋㅋ
대부분의 전통적인 allocator는 적은 크기의 힙으로 시작하며 모두 소진하면 OS로부터 더 많은 메모리를 요청한다. allocator는 heap을 확장하기 위해서 특정 시스템콜(Unix 시스템에서는 sbrk)을 호출한다. sbrk 요청을 수행하기 위해서 OS는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간을 매핑한 후, 새로운 힙의 마지막 주소를 반환한다. 이로써 큰 힙을 사용할 수 있고 요청은 성공적으로 충족될 수 있다.

Basic Strategies

strategies:전략
일부 기법에 대해 간략히 살펴보았고, 빈 공간 할당을 위한 기본 전략에 대해 살펴보자..

Best Fit

So simple!

1. free list를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾는다.
2. 후보자 그룹 중에서 가장 작은 크기의 청크를 반환한다. 이를 best-fit chunk라고 부른다.
   배경: 사용자가 요청한 크기에 가까운 블럭을 반환함으로써 best fit은 공간의 낭비를 줄이려고 노력한다. 이 행동에 비용도 수반된다. 정교하지 않는 구현은 해당 빈 블럭을 찾기 위해서 항상 전체를 검색해야하기때문에 엄청난 성능 저하를 초래한다.

Worst Fit ↔ Best Fit

가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 free list에 계속 유지한다. Worst Fit은 Best Fit방식에서 발생할 수 있는 수많은 작은 청크 대신에 커다란 빈 청크를 남기려고 시도한다. 그러나 다시 한번 항상 빈 공간 전체를 탐색해야 하기 때문에 이 방법 역시 높은 비용을 지불해야한다.

First Fit

First Fit는 간단하게 요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 먼저와 같이 남은 빈 공간은 후속 요청을 위해 계속 유지한다. First Fit은 속도가 빠르다는 점이 장점이다. 원하는 블럭을 찾기 위해 항상 free list 전체를 탐색할 필요가 없다. 때때로 list의 시작에 크기가 작은 객체가 많이 생길 수 있다. 따라서 allocator는 free list의 순서를 관리하는 방법이 쟁점이다. 한가지 방법으로 address-based ordering(주소-기반 정렬)을 사용하는 것이다. 리스트를 주소로 정렬하여 coalescing을 쉽게하고, 단편화로 감소시킨다.

Next Fit

항상 리스트의 처음부터 탐색하는 대신 다음 적합 알고리즘은 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 유지한다. 아이디어는 free space 탐색을 list 전체에 더 균등하게 분산시키는 것이다. list의 첫부분에만 단편이 집중적으로 발생하는 것을 방지한다. 이러한 접근 방식은 전체 탐색을 하지 않기때문에 First Fit의 성능과 비슷하다.

마치 구름이 낀 것 마냥 앞이 보이지 않는다.

가정: 프로세스 주소 공간 전체를 Memory에 loding했다.
base, bound 레지스터로 OS는 Process를 Physcial Memory의 다른 부분으로 쉽게 재배치할 수 있다.
Stack, Heap 사이에 사용되지 않는 큰 공간이 존재한다. not in use 공간 때문에 낭비가 심하다. Address Space공간이 Physcial Memory보다 큰 경우 실행이 매우 어렵다.

Segmentation

대용량 주소 공간을 어떻게 자원할까?
↑ 4GB, 32GB bit 주소 공간을 상상해보자.
프로그램은 단지 수 MB만 사용함에도 불하고 주소 공간 전체에 메모리 LOAD 어떻게 할까?
Basic idea: Instead of having just one base and bounds pair in our MMU, why not have a base and bounds pair per logical segment of the address space?

• Segmentation 논리
• 각각의 address space 단 한쌍의 base ,bound 레지스터를 이용해서 표현하는 것이 아닌, address space에 존재하는 logical segement마다 base랑 bound 레지스터 pair를 할당하는 것

A segment is just a contiguous portion of the address space of a particular length.

Segmentation을 사용하면 OS는 각 Segment를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지할 수 있다.

1960년초 아이디어: MMU 안에 오직 하나의 base, bound 쌍이 존재 X, address space의 논리적인 segement마다 base bound 쌍이 존재한다.

세그멘트 위반(segment violation) or 세그멘트 폴트(segment fault) : 프로세스가 자신의 주소 범위를 넘어 잘못된 접근을 하여 하드웨어가 트랩을 발생시키고 OS는 프로세스를 종료시키는 것

우리가 기준으로 삼는 address space에는 CODE, STACK, Heap 세 종류의 Segment가 있고, 실제 OS에서는 여러개의 segment가 있다.

Ex) 주소 공간을 물리 메모리에 배치하려고 한다. 각 세그멘트의 base와 bound 상을 이용하여 Segment들을 독립적으로 물리 메모리에 배치할 수 있다.

64KB의 물리 메모리에 3개의 Segment와 OS용으로 예약된 16KB 영역이 존재한다.

사용 중인 메모리에만 Physical space이 할당된다.

Address translation

가상 주소 100번지를 참조한다고 가정하자. 가상 주소 100번지는 Code Segment에 속한다. 참조가 일어나면 하드웨어는 base 값에 이 Segment의 Offset을 더해 물리 주소를 만든다.

↑ ( offset(100) + start address of code segment (32KB) = 100 + 32KB = 32868 )

가상 주소 4200의 Heap을 살펴보자. 가상 주소 4200에 Heap의 base 34KB를 더하면 물리 주소 39016이 나온다. 이 주소는 올바른 주소가 아니다. 먼저 Heap 안에서의 offset를 알아한다. Heap은 가상 주소 4KB(4096)에서 시작하기 때문에 offset은 실제로 4200-4096 = 104이다.

↑ ( offset(104) + start address of code segment (34KB) = 104 + 34KB = 34920 )

SUMMARY

접근하고자 하는 주소에 접근하는 방법

virtual address space 상에서 각 segment 시작 부분에서 접근하고자 하는 주소까지의 offset을 먼저 구해야함.

offset + 접근하고자 하는 segment의 base regset 값 = 실제 Physical address

Segment 구분하는 방법 2가지:

Explicit approach( address에 segment 정보를 추가하는 방법 )

가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 segement를 나누는 것을 말한다.
주소 공간을 Segment로 나타내기 위해서 최상위 2비트를 이용한다.
00→ Code segment
01→Heap segment
11→Stack segment
나머지 비트는 offset으로 사용한다.

이 Virtual address.는 14bit짜리다.

↑ The virtual address of 4200 → 4200 이진 숫자 01 0000 0110 1000
By adding the base register to the offset, the hardware arrives at the final physical address.
offset은 bound 검사도 쉽게 만든다.
offset이 bound보다 작은지 여부만 검사하면 된다. 그렇지 않으면 주소가 잘못된 것이다.
base와 bound 쌍을 배열 형식으로 저장할 경우 (segment당 하나의 항목), 원하는 물리 주소를 얻기 위하여 다음과 같은 작업을 하게 된다.

Implict approach

주소가 어떻게 생성되었나를 관찰하여 Segement를 결정한다. 만약 주소가 PC(program counter)에 생성되었다면 (즉, Instruction fectch) 주소는 Code segment에 있을 것이고, Stack 혹은 base Pointer에 있다면 Stack segment에 있는 것이다. 나머지 경우에는 Heap영역에 있을 것이다.

What About The Stack?

Stacks grow backwards → translation must proceed differently.
negative offset < offset - Stack_Max_Szie이 나온다.

순방향 1, 역방향 0을 표시하는 1bit 추가.

이 예에서 가상주소 15KB에 접근하려고 가정해보자. 이 주소는 물리주소 27KB에 매핑되어야 한다. 이 가상 주소를 이진 형태로 바꾸면 11 1100 0000 0000이 된다. 하드웨어는 상위 2비트 11를 사용하여 세그멘트를 지정한다. 이를 고려하면 3KB offset 이 남는다. 올바른 음수 오프셋을 얻기위해서 3KB에서 Segment의 최대 크기를 빼야한다. 이 예에서는 4KB이고 3KB-4KB = -1KB이다. 이제 Base(28KB)에 더하면 올바른 물리 주소 27KB를 얻게 된다. Bound 검사는 음수 Offset의 절대값이 Segment의 크기보다 작다는 것을 확인하여 계산할 수있다.

Support for sharing

Protection bit

메모리 절약을 위해서 때로는 메모리 세그먼트를 공유한다. 코드 공유가 일반적이고, 공유를 지원하 위해서 Protection bit를 하나 추가하여 지원한다.

By setting a code segment to read-only, the same code and be shared across multiple processes.

The OS secretly shares memory which cannot be modified by the process.

다음 장 내용:

OS Support

위와 같은 방식으로 이용한다면 여러 군데 듬성듬성 not in use 공간이 생기고 이는 OS가 재정렬, 재집합을 해준다. 이에 대한 내용은 다음장에서 설명해준다.

 CPU Virtualization 부분에서, LDE(Limited direct execution) 기법에 대해 집중적으로 다룬다.
CPU 가상화의 아이디어는 간단하다. → 대부분 프로그램은 하드웨어에서 직접 실행된다.
But 프로세스가 System Call을 호출하러가나 Timer Interrupt 발생할 때 특정 순간에는 OS가 개입하여 Process issue가 발생하지 않도록 한다.
OS는 약간의 hardware지원을 받아 efficient Virtualization을 제공하기 위해 실행 프로그램의 방해가 안 되도록한다. 중요한 순간에는 OS가 관여하여 하드웨어를 직접 제어한다.
현대 OS의 목표: efficiency, Control

Virtualizing memory

Virtualization을 제공하는 동시에 efficiency and control을 모두 추구한다.
Efficiency → Hardware 지원 활용할 수 밖에 없다.
처음에 몇개의 Register만 사용 점점 TLB → page table 등으로 사용하는 것이 늘어난다. 점점 복잡해진다.
Control → 응용 프로그램이 자기 자신의 메모리 이외에는 다른 메모리에 접근하지 못한다는 것을 OS가 보장한다는 것을 의미한다. → 쉽게 말해서 OS가 메모리 침범을 막아준다.
↑ 하드웨어의 도움이 필요하다.

flexibility 측면에서→ VM system이 필요한 상황이 있다.

• 원하는 대로 주소공간을 사용하기
• 프로그래밍하기 쉬운 시스템을 만들기를 원한다.

핵심 문제는 아래 참고 ↓

Quecstions

How can we build efficient virtualization of memory?
How do we provide the flexibility needed by applications?
How do we maintain control over which memory locations an application can access,
and thus ensure that application memory accesses are properly restricted?
How do we do all of this efficiently?

Hardware-based address translation →(짧게) address translation

address translation은 Limited Direct Execution에서 부가적으로 사용되는 기능이라고 생각할 수 있다.

• the hardware transforms each memory access (e.g., an instruction fetch, load, or store), changing the virtual address provided by the instruction to a physical address where the desired information is actually located.
• Hardware만으로 Memory Virtualzation을 구현할 수 없다. low level 기능들을 제공하여 translation을 가속화시키는 도움을 주지만 혼자서는 안된다.
  OS는 정확한 변환이 일어날 수 있도록 하드웨어를 셋업하기 위하여 관여한다. OS는 메모리의 빈 공간과 사용중인 공간을 알고 있어야하고, 메모리 사용을 제어하고 관리한다.

The program has its own private memory, where its own code and data reside.
↑ illusion을 만들어야한다.
Reality(현실) → Many programs are actually sharing memory at the same time.

Assumptions

Simple memory virtualization

1. The user's address space must be placed continuously in physical memory.
2. The size of the address space is not too big → it is less than the size of physical memory.
3. Each address space is exactly the same size.

차차 가정을 완화하면서 실제적인 Memory Virtualzation을 이끌어낸다.

Example

void func(){
    int x = 3000;
    x = x+3;
}

→
128: movl 0x0(%ebx), %eax; 0+ebx를 eax에 저장
132: addl $0x03, %eax; eax 레지스터에 3을 더한다.
135: movl %eax, 0x0(%ebx); eax를 메모리에 다시 저장.

• 컴파일러는 이 코드를 어셈블리 코드로 변환하고 그결과 x86 어셈블리로 위 코드처럼 표기된다.

The three-instruction code sequence is located at address 128.
The value of the variable x at address 15KB. The initial value of x is 3000.
The sequence of memory accesses.

• Fetch instruction at address 128
• Execute this instruction (load from address 15 KB)
• Fetch instruction at address 132
• Execute this instruction (no memory reference)
• Fetch the instruction at address 135
• Execute this instruction (store to address 15 KB)

프로그램 관점에서 address space은 주소 0부터 시작하여 최대 16KB까지이다.
→ 프로그램이 생성하는 모든 메모리 참조는 이 범위 내에 있어야한다.
To virtualize memory, the OS wants to place the process somewhere else in physical memory, not necessarily at address 0.

프로세스 주소

공간이 실제로는 다른 물리 주소에 배치되어 있을 때, 주소 0번지부터 시작하는 가상 주소 공간의 환상을 어떻게 제공할 수 있을까?

Dynamic(Hardware-based) Relocation = base and bound

1950년 후반의 첫번째 time-sharing machines에게 base and bound 아이디어가 채택되었다.
base and bound을 dynamic relocation라고도 함.

각 CPU마다 2개의 hardware register가 필요하다. 바로 base, bound(limit) register이다.

base와 bound

• 우리가 원하는 위치에 주소 공간을 배치할 수 있게 한다.
• 배치와 동시에 프로세스가 오직 자신의 주소 공간에만 접근한다는 것을 보장한다.

Each program is written and compiled as if it is loaded at address zero.

When a program starts running, the OS decides where in physical memory it should be loaded and sets the base register to that value.

When any memory reference is generated by the process, it is translated.

위의 예제를 분석하며 이해하기

128: movl 0x0 (%EBX), % eax
PC(Program counter)는 128로 설정된다. hardware가 이 instruction을 fech할 때, 먼저 PC값을 base register의 값 32KB(32768)에 더해 32896의 물리주소를 얻는다.

그런 후 hardware는 물리주소에서 명령어를 가져온다. 그리고 프로세서는 명령어의 실행을 시작한다. 얼마후 프로세스는 15KB의 값을 load하라는 명령어를 내린다. 이 주소를 프로세서가 받아 다시 base register(32KB)를 더하고 물리주소 47KB에 원하는 내용을 탑재한다.

↑ address translation: Transforming a virtual address into a physical address.
그리고 이 주소의 재배치는 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있기 때문에, dynamic relocation 이라고도 불린다.

그럼 bound(limit) register는 어디다 쓸까?

bound register는 보호를 지원하기 위해 존재한다. 앞에서 다룬 간단한 예에서 bound register는 항상 16KB로 설정된다. Process가 bound보다 큰 가상 주소 또는 음수인 가상 주소를 참조하면 CPU는 예외를 발생시키고 Process는 종료될 것이다. → bound의 요점은 프로세스가 생성한 모든 주소가 합법적이고 프로세스의 범위에 있다는 것을 확인하는 것이다.
The bounds register is there to help with protection. Specifically, the processor will first check that the memory reference is within bounds to make sure it is legal.

Memory Management unit→ MMU

base와 bound register는 cpu 칩 상에 존재하는 hardware structer이다. CPU당 1쌍.
Address translation에 도움을 주는 Processer의 일부를 MMU라고 부르기도 한다.

bound register 두가지 방식으로 정의

1. 주소 공간의 크기를 저장하는 방식

하드웨어는 가상 주소를 base 레지스터에 더 하기전에 먼저 bound 레지스터와 비교한다.

1. 주소 공간의 마지막 물리주소를 저장하는 방식

하드웨어는 먼저 base 레지스터를 더하고 그 값이 bound 앞에 있는지 검사한다.

두가지 모두 논리적으로 같다.

Example Translations

A process with an address space of size 4KB(비현실적) has been loaded at the physical address of 16KB.
예에서 볼수 있는 것처럼 Physcial address를 얻기 위해서는 간단하게 Virtual address에 base address를 더해주면 된다.
! virtual address가 너무 크거나 음수 일경우에 Fault를 일으키고 예외가 발생하게 된다.

Hardware Support

Two different CPU modes(Kernel, user mode)

• The OS runs in privileged mode(or kernel mode), where it has access to the entire machine.
• Applications run in user mode, where they are limited in what they can do.

Processor status word의 A single bit → indicates which mode the CPU is currently running in.

특정한 순간(system call, 다른 종류의 예외나 interrupt 발생) CPU는 모드를 전환한다.
The hardware must also provide the base and bounds registers themselves, as part of MMU of the CPU.
The hardware should provide special instructions to modify the base and bounds registers.

↑ CPU가 하나라고 가정했을 때, 프로세스가 변경되니 base, bound 값도 변경되어야한다.
The CPU must be able to generate exceptions in situations where a user program tries to access memory illegally.

• The CPU should stop executing the user program and arrange for the OS “out-of-bounds” exception handler to run.

• 번역

Virtual address는 Program Counter에 존재한다.

뜬금포 지식 → Free list

운영체제는 프로세스에게 메모리를 할당할 수 있도록 사용되지 않는 메모리 공간의 리스트를 유지한다. 다양한 자료구조가 사용될 수있으나, 가장 간단한 자료구조는 free list다.
이 리스트는 현재 사용 중이지 않은 물리 메모리 영역의 리스트다.

Operating System Issues

하드웨어 지원과 OS 관리가 결합되면 간단한 Virtual Memory를 구현할 수있다. →base and boud 방식의 virtual memory구현을 위해서 OS가 반드시 개입해야하는 세개의 시점이 존재한다.

First, the OS must take action when a process is created, finding space for its address space in memory.
↑ Fortunately, given our assumptions that each address space is (a) smaller than the size of physical memory and (b) the same size, this is quite easy for the OS

• When a new process is created, the OS will have to search a data structure (often called a free list) to find room for the new address space and then mark it used.

Second, the OS must do some work when a process is terminated (i.e., when it exits gracefully, or is forcefully killed because it misbehaved), reclaiming all of its memory for use in other processes or the OS. 프로세스가 종료하면, 운영체제는 종료한 프로세스의 메모리를 다시 free list에 넣고 연관된 자료구조를 모두 정리한다.

Third, the OS must also perform a few additional steps when a context switch occurs.
-There is only one base and bounds register pair on each CPU, after all, and their values differ for each running program
-The OS must save and restore the base-and-bounds pair when it switches between processes.
-When the OS decides to stop running a process, it must save the values of the base and bounds registers to memory, in some per-process structure such as the process structure or process control block (PCB).

The OS must provide exception handlers

• 정리
• 사용자가 특정 프로그램 실행을 지시하는 순간 프로세스 생성 → 프로세스가 사용할 address space할당
  할당을 위해서 시스템 메모리에서 빈 공간을 찾아 프로세스가 사용할 공간 마련
  빈 공간과 사용중인 공간 중에 어느 프로세스가 어느 공간을 사용하고 있는지, 어떤 공간이 비어있는지 기록할 free list가 존재
  프로세스의 동작이 종료되었을 때(동작을 완료해서/강제종료)OS가 이 프로세스가 사용하던 주소 공간을 회수함.
  회수하고 이 프로세스의 주소 공간에 있던 모든 정보를 삭제하고 free list에 정보처리
  정보처리 방법 1. 메모리에 존재하고 잇는 정보를 안 지우고 free list에 비어있다 기록 2. 메모리에 있는 정보 초기화도 하고 free list에 기록도 함.

1. 실행 중인 프로세스를 중단시킨다.
2. 현재 위치에서 새 위치로 주소 공간을 복사한다.
3. 프로세스 구조체에 저장된 base 레지스터를 새 위치를 가리키도록 갱신한다.
4. 예외 핸들러 혹은 호출된 함수를 제공한다.

• 부팅할 때 커널 명령어를 사용하여 핸들러를 설치한다.