주소 공간에 대해

이제 단일 프로세스가 아니다...

• 초기 시스템의 경우, 간단하게 운영체제는 메모리에 상주하는 라이브러리의 집합. 물리 메모리에 하나의 프로세스가 존재, 나머지 메모리를 사용하였지만...

멀티 프로세스

• 여러 프로세스가 실행 준비 상태에 있고, 운영체제는 이를 전환하며 실행.
• CPU 이용률 증가, 효율성 개선 필요.

시분할 시스템

• 일괄처리방식 컴퓨팅의 한계.
• 많은 사용자가 동시에 컴퓨터 사용.
• 구현 방법 :
  - 하나의 프로세스를 짧은 시간 동안 실행시키는 것.
  - 해당 기간 동안 프로세스에 모든 메모리를 접근할 권한이 주어짐.
  - 프로세스 중단, 중단 시점의 모든 상태를 디스크에 저장.
  - 다른 프로세스의 상태를 탑재.
  - 다시 짧은 시간 동안 실행. 무한반복...
• 위와 같은 구현의 문제점 :
  - 메모리 내용을 디스크에 저장하여 너무 느림;
• 시분할로 인한 OS 새로운 요구사항 :
  - 여러 프로그램이 메모리에 동시에 존재하려면 보호 필요.

주소 공간에 대한 고민 필요

주소 공간의 구조

• 실행 프로그램의 모든 메모리 상태 가짐.
• 프로그램의 코드(명령어)
  - 프로그램이 실행되며 추가 메모리를 필요로 하지 않기 때문에 주소 공간 상단에 배치.
• 스택 : 현재 실행 함수 위치, 지역 변수, 함수 인자, 반환 값 등 저장.
  - 하단에 존재. (예를 들어 프로시저 호출 시) 위로 확장 가능.
• 힙 : 동적 할당 메모리.
  - 상단에 존재. (예를 들어 malloc 시) 아래로 확장 가능.
• 배치는 정해진 것이 아니며 다른 방식으로 배치 가능.

메모리 가상화 필요

• 프로세스는 특정 주소의 메모리에 탑재되고, 매우 큰 전용 주소 공간을 가지는 것처럼 구현.
• 프로세스가 가상 주소 0에서 연산을 수행할 때, 운영체제는 하드웨어의 지원을 통해 물리 주소0이 아닌 실제 프로세스가 탐재된 메모리 부분 n을 읽도록 보장해야 한다.

메모리 가상화의 목표는

멋지게 가상화 하기

투명성

• 운영체제는 프로세스가 가상 메모리의 존재를 인지하지 못하게 구현해야.
• 프로세스는 전용 물리 메모리를 이용하는 것처럼 행동하게 해야.

효율성

• 운영체제는 가상화가 시간/공간 측면에서 효율적이게 구현해야.
• 시간적 : 프로세스가 너무 느리면 안 됨.
• 공간적 : 가상화 구현을 위해 너무 많은 메모리를 사용해선 안 됨.
• TLB 등 하드웨어 기능이 지원.

보호

• 운영체제/프로세스들은 서로 고립되어 보호받아야.
• 프로세스가 탑재, 저장, 명령어 등을 실행할 때 다른 프로세스/운영체제의 메모리에 접근하거나 영향을 줘서는 안 됨.

---

Memory API

메모리 공간의 종류

스택

• 할당과 반환이 컴파일러에 의해 암묵적으로 이루어지는 '자동 메모리'.
• 함수를 작성하고 일반 변수를 선언하면:
  - 컴파일러가 알아서 함수 호출 시 스택에 공간을 확보.
  - 함수에서 리턴하면 컴파일러가 메모리를 반환.

힙

• 모든 할당과 반환이 프로그래머에 의해 명시적으로 처리.
• malloc을 호출
  - 변수를 위한 공간을 힙으로부터 요구.
  - 반환된 변수의 주소가 스택에 저장되어 사용 됨.
  

malloc() 함수

• 호출 :
  - 힙에 요청할 공간의 크기를 넘겨줌.
  - 성공 시, 새로 할당된 공간에 대한 포인터를 반환.
  - 실패 시, NULL 반환.
• void 타입에 대한 포인터를 반환.
  - 주소만 넘겨주고 어떤 타입을 저장할지는 개발자가 결정하게 하는 방식.

free() 함수

• 할당된 힙 메모리를 해제.
• malloc()에 의해 반환된 포인터를 인자로 받아 해제.

(malloc, free 사용 시) 흔한 오류

자동 메모리 관리

• 대부분 새로운 언어들은 자동 메모리 관리를 제공.
• 이러한 조~흔 언어들은 할당을 위해서는 특정 루틴을 호출하지만, 해제를 위해서는 호출하지 않는다.
• garbage collector가 실행되어 참조되지 않는 메모리는 자동으로 해제된다.

메모리 할당 잊어버리기

많은 루틴들은 호출 전에 필요한 메모리가 이미 할당되었다고 가정한다.
ex) 할당하지 않은 채 strcpy()하면 쥬금...

메모리를 부족하게 할당받기

버퍼 오버플로우 : 할당된 공간 이상의 범위를 접근하는 경우에 발생.

할당받은 메모리 초기화하지 않기

malloc을 호출했으나 실수로 초기화하지 않은 경우, 해당 영역에 접근하면 버그 발생.

메모리 해제하지 않기

메모리 누수 : free로 메모리 해제를 잊었을 때 발생.

• 메모리가 정리되지 못하고 천천히 누수되다가 메모리 부족으로 쥬금...

메모리 사용이 끝나기 전에 메모리 해제하기

dangling pointer : 해제한 메모리 영역에 접근하면 쥬금...

반복적으로 메모리 해제하기

double free : 이미 해제한 메모리를 한 번 더 해제하는 경우 발생. 쥬금...

free() 잘못 호출하기

invalid free : malloc으로 할당받은 포인터가 아닌 이외의 값을 해제 시도.

회사에서 다 겪어본 것들이군...

운영체제의 지원

malloc/free

• 시스템 콜이 아닌 라이브러리 함수.
• 라이브러리 자체는 더 많은 메모리를 요구하고 반환하는 시스템 콜 기반으로 구축.

brk

• 프로그램 break 위치를 변경하는 데 사용.
  - break : 힙의 마지막 위치를 나타냄.
• 새로운 break 주소를 인자로 전달받아 현재 break보다 큰지/작은지에 따라 힙의 크기 증가/감소.
• 직접 호출하면 안 되고 메모리 할당 라이브러리에 의해 사용.

mmap

• 운영체제로부터 메모리를 얻을 수 있음.
• 프로그램에 anonymous 메모리 영역 생성.
  - anonymous 영역 : 특정 파일과 연결되어 있지 않고 스왑 공간과 연결. 힙처럼 취급.
  

기타 함수들

calloc : 메모리 할당 영역을 0으로 채워 반환.
realloc : 이미 할당된 공간을 확장.

---

address Translation

주소 변환의 원리

가상화 제공과 함께

• 효율성 추구
  - 하드웨어 지원을 활용. 레지스터 및 TLB, 페이지 테이블 등 하드웨어 활용.
• 제어
  - 프로세스가 자신의 메모리 이외의 다른 메모리에 접근하지 못하는 것을 보장.
• 유연성
  - 개발자 마음대로 주소 공간 사용, 개발하기 쉬운 시스템.

하드웨어 기반 주소 변환

• 제한적 직접 실행 방식에 부가적으로 사용되는 기능.
• 주소 변환을 통해 하드웨어는 명령어 반입, 탑재, 저장 등 가상 주소를 실제 물리 주소로 변환.
• 프로세스의 모든 메모리 참조를 실제 메모리 위치로 재지정하기 위해 하드웨어가 주소 변환.
• 정확한 변환을 위해 하드웨어 및 운영체제의 도움이 필요.
  - 운영체제는 메모리 빈 공간과 사용 중인 공간을 알고 있어야 하고, 메모리 사용을 제어 및 관리.
• 목표 : 프로세스가 각자 자신의 전용 메모리를 소유하고 그 안에 자신의 코드/데이터가 있다는 환상을 갖게 하는 것.

사례

주소 변환 구현을 위해 어떤 것이 왜 필요한지?

• 프로세스 관점에서 주소 공간은 0부터 시작하여 n까지. 모든 메모리 참조는 0~n 이내에 있어야 함.
• 메모리 가상화를 위해 운영체제는 프로세스를 물리 메모리 주소 0이 아닌 다른 곳에 위치시킴.
• 이때 어떻게 프로세스 모르게 다른 위치에 메모리를 재배치하느냐가 관건.
• 즉, 실제로는 다른 물리 주소에서 시작하는데, 프로세스는 주소 0부터 시작한다고 느낌.

동적 (하드웨어 기반) 재배치

동적 재배치

• 하드웨어 기반 주소 변환의 아주 간단한 사례로, 베이스와 바운드라고도 함.
• 각 CPU마다 2개의 하드웨어 레지스터가 필요.
  - base 레지스터 : 프로세스가 탑재될 물리 메모리 시작 위치.
  - bound(limit) 레지스터 : 보호 지원. 메모리 참조가 합법적인가를 판단하기 위해 가상 주소가 바운드(범위) 안에 있는지 확인. base와 마찬가지로 주소 공간의 크기를 저장하거나 마지막 물리 주소를 저장.
• 레지스터 쌍으로 원하는 위치에 주소 공간을 배치 및 프로세스가 해당 주소 공간에만 접근할 수 있게 한다.
• 운영체제는 프로세스가 탐재될 물리 메모리 위치를 정하고, 베이스 레지르터를 지정.
• 프로세스에 의해 생성되는 모든 주소가 프로세서에 의해 physical address = virtual address + base로 변환.
• 즉, base 레지스터 + 가상 메모리 주소를 이용해 물리 메모리 주소에 접근함으로써 가상 메모리 주소는 0부터 시작하는 것처럼 사용된다.
• 이러한 주소의 재배치는 실행 시 발생하고 실행 이후에도 주소 공간을 이동할 수 있기 때문에 동적 재배치라고 한다.

하드웨어 지원: 요약

두 가지 CPU 모드가 필요.

• 커널(특권) 모드 : 운영체제가 커널 모드로 실행되며 컴퓨터 전체의 접근 권한을 가짐.
• 사용자 모드 : 응용 프로그램은 제한된 권한을 가짐.

프로세스서 상태 워드 : 한 비트가 CPU의 현재 실행 모드를 나타냄. 시스템 콜 또는 인터럽트 등으로 인해 CPU는 모드를 전환.

베이스/바운드 레지스터 : 가상 주소에 값을 더해 실제 물리 주소로 변환 가능.

• 하드웨어는 이 레지스터 값을 변경하는 명령어 제공.
• 커널 모드에서 레지스터 변경 가능.

예외 핸들러

• CPU는 사용자 프로그램이 바운드를 벗어난 주소로 불법적인 메모리 접근을 시도하려는 상황에서 예외를 발생시킬 수 있어야 함.
• 프로세스의 실행을 중지하고, 운영체제의 예외 핸들러가 실행되도록 조치.

운영체제 이슈

하드웨어 지원 + 운영체제 관리 == 간단한 가상 메모리 구현

베이스/바운드 방식의 가상 메모리 구현을 위한 운영체제 개입 시점

• 프로세스가 생성될 때, 주소 공간이 저장될 메모리 공간을 찾아 조치 취해야 함.
  - 새로운 주소 공간 할당에 필요한 영역을 찾기 위해 빈 공간 리스트 검색.
• 프로세스가 종료될 때, 메모리를 회수하여 다른 프로세스에서 사용할 수 있게 해야 함.
  - 종료된 프로세스의 메모리를 다시 빈 공간 리스트에 넣고 연관된 자료 구조를 모두 정리.
• 문맥 교환이 일어날 때, 프로세스 전환 시 베이스/바운드 쌍을 저장/복원 해야 한다.
  - 운영체제가 실행 중인 프로세스를 중단시키기로 하면, 운영체제는 메모리에 존재하는 프로세스 별 자료 구조 안에 베이스/바운드 레지스터 값을 저장.
  - 이 자료구조를 프로세스 제어 블럭이라고 함.
  - 프로세스가 중단되면, 운영체제는 메모리 현 위치에서 다른 위치로 주소 공간을 쉽게 옮길 수 있음. (주소 공간 복사 및 베이스 레지스터 갱신을 통해) 이때 프로세스는 다른 위치로 옮겨진 것을 인식하지 못함.
• 예외 핸들러 또는 호출된 함수를 제공해야 함.
  - 운영체지는 부팅할 때 특권 명령어로 핸들러 설치.
  - 예를 들어 프로세스가 바운드 밖의 메모리에 접근하려는 경우, CPU는 예외를 발생시키고, 운영체제는 이에 대한 조치를 취해야 함.
  - 운영체제가 개입하여 프로세스를 종료시키고 메모리 해제, 프로세스 테이블에서 항목 정리.
  

---

Segmentation

내부 단편화

• 동적 재배치는 비효율적.
• 예를 들어 프로세스 스택과 힙이 아주 크지 않을 때, 둘 사이의 공간이 낭비.
• 즉, 할당 영역의 내부 공간이 사용되지 않아 단편화가 발생되어 낭비 됨.
• 물리 메모리의 사용률을 높이고 내부 단편화 방지를 위해 base-and-bound 일반화 즉, 세그멘테이션 기법을 사용.

세그멘테이션: base/bound의 일반화

세그멘테이션

• MMU 안에 하나의 베이스/바운드 쌍만 존재하는 것이 아니라, 주소 공간의 논리적인 segment마다 베이스/바운드 쌍이 존재한다.
• 이때의 세그멘트는 특정 길이를 가지는 연속적인 주소 공간.
• 세그멘테이션을 이용해 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지.

세그멘트의 종류

하드웨어는 가상 주소가 어느 세그멘트를 참조하는지, 오프셋은 얼마인지 어떻게 앎?

• 일반적인 접근법 : 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그멘트로 나누기.
  - 예를 들어 최상위 2비트가 00이면 가상 주소가 코드 세그멘트를 가리킨다고 가정하고, 코드 세그멘트의 베이스/바운드 쌍을 사용하여 주소를 물리 메모리에 재배치.
  - 최상의 2비트는 세그멘트의 종류, 하위 12비트는 세그멘트 내의 오피셋.
  - 오프셋을 이용해 바운드보다 작은지 여부를 검사 가능.
  - 세그멘트 종류를 나타내는 데 2비트를 쓰고, 종류는 코드/힙/스택 세 가지이므로 주소 공간의1/4는 사용 불가능.
  - 이를 해결하기 위해 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하는 식으로 세그멘트 종류 구별에 1비트만 사용.
• 묵시적 접근 방식 : 주소가 어떻게 형성되었나를 관찰해 세그멘트를 결정.
  - PC에서 생성되었다면 코드 세그멘트, 스택/베이스 포인터에 기반을 둔다면 스택 세그멘트, 이외는 힙...
  

스택

스택의 큰 차이점 : 다른 세그멘트들과는 반대 방향으로 확장

스택의 변환 방법

• 간단한 하드웨어가 추가로 필요.
  - 하드웨어는 세그멘트가 어느 방향으로 확장하는지도 알아야 함.
  - 예를 들어 1비트를 사용하여 1이면 커지는 쪽으로 확장, 0이면 작아지는 쪽으로 확장.

공유 지원

세그멘트 공유

• 메모리를 절약하기 위해 주소 공간 사이에 특정 메모리 세그멘트를 공유. 특히 코드 공유.
• protection bit
  - 공유 지원을 위해 세그멘트마다 비트 추가.
  - 세그멘트를 읽거나 쓸 수 있는지, 세그멘트의 코드를 실행시킬 수 있는지를 나타냄.
  - 코드 세그멘트를 읽기 전용으로 설정하면, 주소 공간의 독립성을 유지하면서 여러 프로세스가 주소 공간의 일부를 공유할 수 있음.

소단위 대 대단위 세그멘테이션

대단위 세그멘테이션

• 코드/스택/힙으로 소수의 세그멘트만 지원하는 경우, 비교적 큰 단위로 분할하는 대단위 세그멘테이션.

소단위 세그멘테이션

• 일부 초기 시스템의 경우, 주소 공간을 작은 크기의 공간으로 분할하는 것이 허용.
• 많은 수의 세그멘트를 지원하기 위해서 여러 세그멘트 정보를 메모리에 저장할 세그멘트 테이블이 필요.

운영체제의 지원

세그멘테이션이 제기하는 문제

• 문맥 교환 시 운영체제는 세그멘트 레지스터의 저장과 복원을 해야 함.
• 미사용 중인 물리 메모리 공간의 관리.
  - 새로운 주소 공간이 생성되면 운영체제는 세그멘트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 함.
• 외부 단편화.
  - 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워짐.
  - 이 공간들은 세그멘트에 할당/확장하기 어려운 단편화 된 공간.

해결책

• 기존의 세그멘트를 정리하여 물리 메모리를 압축.
  현재 실행 중인 프로세스 중단, 데이터를 하나의 연속된 공간에 복사, 세그멘트 레지스터가 새로운 물리 메모리 위치를 가리키게 함.
  but 세그멘트 복사는 메모리 부하가 크고, 많은 프로세서 시간을 사용하므로 비용이 높음.
• 빈 공간 리스트 관리 알고리즘 사용.
  할당 가능한 메모리 영역들을 리스트 형태로 유지하여 최적 적합/최초 적합/버디 알고리즘 등을 이용해 할당.
  

---

Free Space Management

저수준 기법들

분할과 병합

분할

• 10~20은 사용 중이지만, 0~10과 20~30(주소 20, 길이 10)이 빈 공간 리스트인 경우, 일반적으로 10바이트를 초과하는 요청은 실패.
• 만약 1바이트의 메모리를 요청했을 때, 할당기는 분할 수행.
• 요청을 만족시킬 수 있는 청크를 찾아 둘로 분할.
• 첫 청크는 호출자에게 반환, 두 번째 청크는 리스트에 남음.
• 만약 주소 20에 해당하는 주소를 반환하기로 하였으면, 빈 공간 리스트는 0~10, 21~30(주소 21, 길이 9)이 남게 됨.
• 이렇게 요청이 특정 빈 청크의 크기보다 작은 경우, 분할 기법 사용.

병합

• 프로세스가 free(10)을 호출하여 힙의 중간에 존재하는 공간을 반환하면 주소 10/길이 10, 주소0/길이10, 주소 20/길이 10이 빈 공간 리스트에 존재.
• 힙 전체가 비어있지만, 10바이트 길이의 청크 3개로 나눠져 있게 됨.
• 이때 사용자가 20바이트를 요청하면 단순한 리스트 탐색의 경우, 빈 20짜리 청크를 발견하지 못하고 반환 실채.
• 메모리 청크가 반환될 때 빈 공간들을 병합 필요.
• 해제되는 청크의 주소와 인접한 빈 청크의 주소가 있는지 확인하여 인접해있다면 하나의 청크로 병합.

할당된 공간의 크기 파악

헤더

• 대부분의 할당기는 추가 정보를 헤더 블럭에 저장.
• 헤더 블럭은 메모리에 유지되며, 해제된 청크 바로 직전에 위치.
• 할당된 공간의 크기, 해제 속도를 향상시키기 위한 추가의 포인터, 무결성 검사를 제공하기 위한 매직 넘버, 기타 정보들을 저장.
• 헤더를 가리키는 포인터를 얻으면 매직 넘버가 기대하는 값과 일치하는지 비교하여 안전성 검사 실시, 해제된 영역의 크기를 계산.

힙의 확장

힙 공간이 부족한 경우

• 전통적인 할당기는 적은 크기의 힙으로 시작하여 모두 소진 시 운영체제로부터 더 많은 메모리를 요청.
• 할당기는 힙 확장을 위해 특정 시스템 콜을 호출, 확장도니 영역에서 새로운 청크를 할당.
• 운영체제는 빈 물리 페이지를 찾아 요청 프로세스의 주소 공간에 매핑한 후, 새로운 힙의 마지막 주소를 반환.

기본 전략

이상적인 할당기는 속도가 빠르고 단편화를 최소화.

최적 적합

• 빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청크를 찾음.
• 그룹 중 가장 작은 크기의 청크 반환.
• 빈 공간을 한 번 순회하여 반환할 블럭 찾음.
• 공간의 낭비를 줄일 수 있으나, 항상 전체를 검색해야하므로 성능 저하.

최악 적합

• 최적 적합의 반대.
• 가장 큰 빈 청크를 찾아 요청된 크기 만큼 반환.
• 성능 저하 + 단편화 발생.

최초 적합

• 요청에 부합하는 첫 블럭을 찾아 요청 만큼 반환.
• 전체를 탐색할 필요가 없어 속도가 빠름.
• 할당기가 빈 공간 리스트의 순서를 주소-기반 정렬 등으로 관리하면 병합이 쉽고 단편화 감소.

다음 적합

• 처음부터가 아니라 마지막으로 찾았던 원소를 가리키는 추가의 포인터를 두어 해당 위치부터 탐색.
• 빈 공간 탐색을 리스트 전체에 균등하게 분산시켜 리스트 첫 부분에만 단편이 발생하는 것을 방지.

다른 접근법

개별 리스트

• 특정 프로세스가 자주 요청하는 크기가 있다면, 해당 크기의 객체를 관리하기 위한 리스트를 별도로 유지.
• 특정 크기의 요청에 대한 메모리 청크를 유지하여 단편화 가능성 줄임.
• 복잡한 리스트 검색이 필요 없으며 할당과 해제 요청이 빠름.
• But... 지정된 크기의 메모리 플과 일반 풀에 얼마씩 메모리를 할당해야?
  - 슬랩 할당기 : 특수 목적 할당기로 위 문제 해결.
  - 커널 부팅 시, 커널 객체를 위한 여러 객체(락, 아이노드 등) 캐시가 할당.
  - 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트로, 메모리 할당 및 해제 요청 속도 증진.
  - 기존에 할당된 캐시 공간이 부족하면 상위 메모리 할당기에게 추가 슬랩 요청, 참조 횟수가 0이 되면 상위 메모리 할당기가 슬랩을 회수.
  - 슬랩 할당 방식은 빈 객체들을 사전에 초기화 된 상태로 리스트에 유지하여 개별 리스트 방식보다 개선.
  - 즉, 객체 당 잦은 초기화와 반납 작업을 피할 수 있어 오버헤드 감소.

버디 할당

이진 버디 할당기

• 빈 공간의 합병은 할당기의 중요 기능.
• 빈 메모리는 처음에는 크기 2^n인 하나의 큰 공간으로 생각되며, 메모리 요청 발생 시 충분한 공간이 발견될 때까지 빈 공간을 2개로 분할하여 반환.
• 2의 거듭제곱 크기 만큼의 블럭만 할당 가능하므로 내부 단편화가 대량 발생 가능.
• 블럭이 해제될 때, 빈 공간 리스트에 반환하면 할당기는 그 크기의 "버디" (2개로 쪼개졌던 반대쪽)가 비어있는지 확인.
• 비어있다면 두 블럭을 병합하여 하나의 블럭으로 만듦.
• 그 뒤에 합쳐진 블럭 크기의 버디가 있는지 확인, 합병을 반복.
• 재귀 합병 과정이 트리를 따라 전체 빈 공간이 복원되거나 버디가 사용 중이란게 확인 될때까지 반복.

기타 아이디어

확장성

• 위 접근 방식들에는 확장성 문제가 있음.
• 빈 공간 개수가 늘어남에 따라 리스트 검색이 매우 느려질 수 있음.
• 정교한 할당기는 균형 이진 트리, 스플레이 트리, 부분 정렬 트리 등 복잡한 자료 구조를 사용하여 비용을 줄이고 성능 향상.
• glibc의 할당기?

---

Paging

세그멘테이션의 문제점

• 세그멘테이션 : 메모리 공간을 가변 크기의 논리 세그멘트 조각으로 분할하는 것.
• 다양한 크기의 청크로 분할할 때, 공간이 단편화 됨.

페이징

• 메모리 공간을 동일 크기의 조각으로 분할하는 것.
• 페이지 : 고정 크기의 단위.
• 페이지 프레임 : 물리 메모리의 고정 크기 슬롯 배열.
• 프레임 당 하나의 가상 메모리 페이지 저장.

개요

페이징의 구성

• 물리 메모리는 고정 크기의 슬롯들로 구성.
• 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치.
• 프로세스가 생성한 가상 주소의 변환을 위해, 우선 가상 주소를 가상 페이지 번호와 페이지 내의 오프셋 2개의 구성 요소로 분할.
• 프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환.
• 예를들어 가상 주소가 21(010101)이면, 이 가상 주소를 검사하고 가상 페이지 번호와 오프셋으로 나눈다. 가상 페이지 01의 0101(5)번째 바이트다.
• 가상 페이지 번호(VPN)를 갖고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다.
• 물리 프레임 번호(PFN)/물리 페이지 번호(PPN) : VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있음.

페이징의 장점

• 유연성
  - 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념 지원. 힙/스택이 어느 방향으로 커지는가, 어떻게 사용되는 가 신경 X.
• 빈 공간 관리의 단순함.
  - 비어있는 페이지 빈 공간 리스트를 유지하고 요청 받은 공간 만큼 선택하여 반환.
  - 각 가상 페이지의 물리 메모리 위치 기록을 위해 운영체제는 프로세스마다 페이지 테이블 자료 구조를 유지.
  - 페이지 테이블 : 프로세스마다 존재하며, 주소 공간의 가상 페이지 주소 변환 정보를 저장. 각 페이지가 저장된 물리 메모리 위치가 어디인지 알려줌.
  

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

• 페이지 테이블은 실행 중인 프로세스와 할당 메모리에 따라 매우 커지기 때문에, 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지 않음.
• 대신, 각 프로세스의 페이지 테이블을 메모리에 상주.
• 페이지 테이블은 운영체제 가상 메모리에 저장할 수도 있고 디스크에 스왑될 수도 있음.

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

선형 페이지 테이블

• 가장 단순한 배열 형태.
• 물리 프레임 번호를 찾기 위해 가상 페이지 번호로 배열 항목에 접근, 항목의 페이지 테이블 항목을 검색.
• 각 페이지 테이블 항목에는 여러 비트들이 존재.
  - Valid bit : 특정 변환의 유효 여부. 할당되지 않은 주소 공간 표현.
  - protection bit : 페이지를 읽을 수/쓸 수/실행될 수 있는지를 표시.
  - Present bit : 페이지가 물리 메모리에 있는지, 디스크에 있는지(스왑 아웃 되었는지).
  - dirty bit : 메모리에 반입된 후 페이지가 변경되었는지.
  - reference bit : 페이지가 접근되었는지 추적.
  

페이징 : 너무 느림

페이지 테이블 크기로 인해 처리 속도가 저하될 수 있음.

• 하드웨어에서 주소 변환 시, 페이지 테이블에서 적절한 페이지 테이블 항목을 가져오고, 변환 수행 뒤에 물리 메모리에 데이터를 탑재.
• 이를 위해 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야 함.
• 페이지 테이블 베이스 레지스터를 이용해 메모리에서 PTE 반입, PFN 추출 및 가상 주소의 오프셋과 연결하여 원하는 물리 주소를 만듦.
• 하드웨어는 메모리에서 원하는 데이터를 가져와 eax 레지스터에 탑재.

위와 같이 많은 메모리 참조 작업이 필요.
메모리 참조는 비용이 높고 프로세스가 느려짐.

메모리 트레이스

프로세스의 메모리 참조

• 프로세스가 실행되면, 각 명령어의 반입 시 메모리가 두 번 참조.
  - 명령어 위치 파악하기 위한 페이지 테이블 접근.
  - 명령어 자체.
  - mov 명령어는 메모리 참조를 한 번 함. (페이지 테이블 접근, 배열 자체 접근)
• 전체 트레이스에서 루프 당 10번의 메모리 접근이 존재. 네 번의 명령어 반입, 한 번의 메모리 갱신, 이 주소 변환을 위한 총 다섯 번의 페이지 테이블 접근.

---

Translation Lookaside Buffers

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

페이징

• 프로세스 주소 공간을 작은 고정 크기로 나누고, 각 페이지의 실제 위치를 메모리에 저장.
• 매핑 정보 저장을 위해 큰 메모리 공간을 요구.
• 페이지 테이블 접근을 위한 메모리 읽기 작업은 성능 저하 유발.

변환-색인 버퍼 (TLB)

• 주소 변환을 빠르게 하기 위해 사용.
• 자주 참조되는 가상 주소-실 주소 변환 정보를 저장하는 하드웨어 캐시.
• 가상 메모리 참조 시, TLB에 먼저 변환 정보가 있는지 확인. 있다면 페이지 테이블을 통하지 않고 빠르게 변환 가능.

TLB 기본 알고리즘

가상 주소 변환... 이제 TLB를 곁들인

• 선형 페이지 테이블과 하드웨어로 관리되는 TLB로 구성.
• 가상 주소에서 가상 페이지 번호를 추출, 해당 VPN의 TLB 존재 여부를 검사.
• 존재한다면 TLB 히트. TLB가 변환 값을 갖고 있다는 것.
• TLB 항목에서 페이지 프레임 번호를 추출 가능.
• 해당 페이지에 대한 접근 권한 검사가 성공하면, 정보를 원래 가상 주소의 오프셋과 합쳐 원하는 물리 주소를 구성, 메모리 접근 가능.
• 만약 TLB에 변환 정보가 존재하지 않는다면, 페이지 테이블 접근, 가상 메모리 참조가 유효하고 접근 가능하다면 해당 변환 정보를 TLB로 읽어와야 함. (시간이 많~이 걸림)
• TLB 미스가 발생하면 메모리 참조가 많이 추가되며 페이징 비용이 커짐.

배열 접근

자세한 TLB 작동 과정

• 예를들어 배열의 0, 1, 2번이 하나의 페이지에, 3, 4, 5, 6이 하나의 페이지에, 7, 8, 9가 하나의 페이지에 들어있다고 가정.
• 배열들을 돌며 읽을 때, TLB가 초기화 되어있는 경우, 처음으로 접근하는 페이지에 대해서는 TLB 미스가 발생하며 TLB 갱신이 일어난다. 두 번째로 접근할떄는 TLB 히트가 발생.
• 0~9까지 읽어올 때 미스, 히트, 히트, 미스, 히트, 히트, 히트, 미스, 히드, 히트가 발생.
• 공간 지역성 : 배열이 처음 접근되었지만, TLB는 공간 지역성으로 인해 성능 개선 가능. 배열들이 페이지 내에서 인접해있기 때문에 페이지의 첫 항목을 접근할 때만 TLB 미스 발생.
• 페이지 크기는 TLB의 효용성에 매우 중요한 역할. 페이지 크기가 두 배가 되면 TLB 미스 횟수가 훨씬 줄어들을 것.
• 시간 지역성 : 루프 종료 후에도 배열을 사용한다면 모든 주소 변환 정보가 TLB에 탑재되어 있기 때문에 성능은 더욱 개선.

TLB 미스는 누가 처리?

TLB 미스 처리

• 하드웨어 (CISC)
  - 하드웨어가 페이지 테이블에 대한 명확한 정보를 갖고 있어야 함. 메모리 상 위치와 정확한 형식을 알아야.
  - 미스 발생 시, 페이지 테이블에서 원하는 페이지 테이블 엔트리를 찾고, 필요한 변환 정보를 추출하여, TLB 갱신 후, TLB 미스 발생 명령어를 재실행.
• 소프트웨어 관리 TLB (RISC)
  - TLB 미스 발생 시, 하드웨어는 예외 시그널 발생.
  - 예외 시그널을 받은 운영체제는 명령어 실행 중지, 실행 모드를 커널 모드로 변경, 트랩 핸들러 실행. 이때 실행되는 트랩 핸들러는 TLB 미스의 처리를 담당하는 운영체제 코드.
  - 트랩 핸들러는 페이지 테이블을 검색해 변환 정보를 찾고, TLB 접근이 가능한 특권 명령어를 사용해 TLB 갱신 후 리턴.
  - 리턴되면 하드웨어가 명령어 재실행.

TLB의 구성

하드웨어 TLB

• 32, 64 또는 128 개의 엔트리를 가지며, 완전 연관 방식.
• 완전 연관 방식 : 변환 정보는 TLB 어디든 위치 가능. 변환 정보를 찾는 검색은 TLB 전체에서 병렬적으로 수행.
• 변환 정보 저장 위치에 제약이 없도록 각 항목마다 VPN, PFN이 있음.

TLB의 문제: 문맥 교환

• TLB에 있는 가상 주소와 실제 주소 간의 변환 정보는 탑재시킨 프로세스에서만 유효.
• 문맥 교환으로 인해 프로세스가 변환되었을때, 어떤 프로세스를 위한 항목인지 알 수 없음.
• 즉, TLB가 정확하고 효율적으로 멀티 프로세스 간의 가상화를 지원하기 위해 추가적 기능이 필요.

문맥 교환 시 기존 TLB 내용 비우기

• 모든 valid bit를 0으로 설정하여 지움.
• 문맥 교환할때마다 TLB를 비우면, 잘못된 변환 정보를 사용하는 것을 방지가능.
• But, 문맥 교체 발생 시마다 페이지 접근으로 인한 TLB 미스가 발생하며 성능에 부담을 가져올 수 있다.

TLB 내용 보존

• 위 문제를 개선하기 위해 몇 시스템에서는 문맥 교환 시 TLB 내용을 보존할 수 있는 하드웨어 기능 추가.
• TLB에 주소 공간 식별자 필드(ASID)를 추가. 프로세스 식별자와 유사하며, 좀 더 적은 비트를 갖고 있음.
• ASID 정보를 추가하면 프로세스 별로 TLB 변환 정보를 구분할 수 있음.
• 문맥 전환 시, 운영체제는 새로운 ASID 값을 정해진 레지스터에 탑재.

이슈: 교체 정책

캐시 교체 정책

• TLB에 새로운 항목을 탑재할 때, 현재 존재하는 항목 중 어떤 것을 교체 대상을 해야 할지?
• 흔한 방법 : 최저 사용 빈도
  - 오랫동안 사용되지 않은 항목을 교체.
• 랜덤 정책
  - 무작위. 구현이 간단하고 예외 상황의 발생을 피함.

---

Advanced Page Tables

페이징: 더 작은 테이블

• 페이지 테이블이 크면 많은 메모리 공간을 차지한다는 문제점.

간단한 해법: 더 큰 페이지

• 페이지 크기를 증가시켜 페이지 테이블의 크기를 줄일 수 있음.
• 페이지 내부의 낭비 공간이 증가하는 내부 단편화 문제가 발생.

하이브리드 접근 방법: 페이징과 세그멘트

하이브리드

• 두 방식을 조합하여 장점을 취함.
• 프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 대신, 논리 세그멘트마다 따로 페이지 테이블을 둔다.
• 세그멘테이션에서는 세그멘트 물리 주소 시작 위치를 나타내는 base, 크기를 나타내는 bound 레지스터가 있음.
• MMU에 비슷한 구조를 사용. 베이스는 세그멘트 시작 주소가 아니라 세그멘트의 페이지 테이블의 시작 주소를 가짐. 바운드는 페이지 테이블의 끝을 나타내기 위해 사용.
• 문맥 교환 시, 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치값으로 변경.
• TLB 미스가 발생하면 하드웨어는 세그멘트 비트를 이용해 어떤 베이스/바운드 쌍을 사용할지 결정.
• 선형 페이지 테이블의 동작과 유사하되, 하나의 페이지 테이블 베이스 레지스터가 아니라 셋 중 하나의 세그멘트 베이스 레지스터를 사용하는 점이 다르다.
• 이를 통해 선형 페이지 테이블에 비해 메모리 사용을 개선시킬 수 있음. 스택/힙 사이의 할당되지 않은 페이지들은 페이지 테이블 상에 더 이상 공간을 차지하지 않음.
• But 문제점
  - 여전히 세그멘테이션을 사용. 세그멘테이션은 주소 공간에 패턴을 가정하기 때문에 유연성이 떨어짐. 드문드문 사용되는 힙의 경우에는 여전히 페이지 테이블 낭비가 존재.
  - 외부 단편화 유발.

멀티 레벨 페이지 테이블

멀티 레벨 페이지 테이블

• 선형 페이지 테이블을 트리 구조로 표현.
• 페이지 테이블을 페이지 크기의 단위로 나눔. 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않음.
• 페이지 디렉터리 자료 구조를 사용하여 페이지 테이블의 각 페이지의 할당 여부와 위치 파악.
• 페이지 디렉터리
  - 페이지 디렉터리 항목들로 구성. 유효 비트, 페이지 프레임 번호를 갖고 있음.
• 장점
  - 사용된 주소 공간의 크기에 비례하여 페이지 테이블 공간 할당. 보다 작은 크기의 페이지 테이블로 주소 공간 표현 가능.
  - 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 용이. 각 페이지들이 물리 메모리에 산재해있어도 페이지 디렉터리를 이용해 위치를 파악 가능하여 공간 할당이 매우 유연.
• 단점
  - 추가 비용 발생. TLB 미스 시, 주소 변환을 위해 두 번의 메모리 로드 발생. 페이지 테이블 크기는 줄였으나 메모리 접근 시간이 증가. TLB 히트 시에 성능은 같지만, 미스 시에는 두 배의 시간 소요.
  - 복잡도. 페이지 테이블 검색의 구현이 복잡함.
  

2단계 이상 사용

트리의 단계를 더 증가시킬 수 있다.

• 페이지 디렉터리가 너무 커지면 멀티 레벨 페이지 테이블의 목적이 훼손.
• 페이지 디렉터리 자체를 멀티 페이지들로 나눠 트리의 단계를 늘릴 수 있음.
• 페이지들을 가리킬 수 있도록 그 위에 새로운 페이지 디렉터리를 추가.
• 가상 주소의 최상위 비트들을 사용하여 상위 단계의 페이지 디렉터리에서 엔트리를 찾고, 유효하다면 상위의 물리 주소와 두 번째 단계의 페이지 디렉터리 인덱스를 결합해 물리 페이지를 구함.
• 유효할 경우, PTE 주소는 두 번째 단계의 페이지 디렉터리 항목에서 얻은 물리 주소와 페이지 테이블 인덱스를 결합하여 구함.

역 페이지 테이블

• 여러 개의 페이지 테이블 대신 시스템에 하나의 페이지 테이블만 둔다.
• 페이지 테이블은 물리 페이지를 가상 주소 페이지로 변환.
• 역 페이지 테이블의 각 항목은 해당 물리 페이지를 사용 중인 프로세스 번호 가상 페이지 번호를 갖고 있음.
• 주소 변환을 위해 전체 테이블을 검색해 가상 주소 페이지 항목을 찾아야 하므로 순차 탐색은 느림. 탐색 속도 향상을 위해 주로 해시 테이블 사용.

페이지 테이블을 디스크로 스와핑

• 여전히 모든 페이지 테이블을 메모리에 상주시키기에는 양이 너무 클 수 있음.
• 페이지 테이블을 커널 가상 메모리에 존재시키거나 디스크로 스왑.

---

wapping: Mechanisms

물리 메모리 크기의 극복: 메커니즘

• 메모리 계층에 레이어를 추가하고 큰 주소 공간을 제공하면 더 많은 걱정이 사라진다.

스왑 공간

• 디스크에 페이지들을 저장할 수 있는 일정 공간.
• 입출력 단위는 페이지.
• 운영체제는 스왑 공간의 모든 페이지들의 디스크 주소를 기억해야 함.
• 시스템이 사용할 수 있는 메모리 페이지의 최대 수를 결정하기 때문에 크기가 매우 중요.

Present Bit

일반적인 메모리 참조 과정

• 메모리가 참조될 때, 프로세스가 가상 메모리 참조를 생성. 하드웨어는 메모리에서 원하는 데이터를 가져오기 전에 가상 주소를 물리 주소로 변환.
• 하드웨어는 먼저 가상 주소에서 VPN을 추출한 후에 TLB에 해당 정보가 있는지 검사.
• TLB에서 찾을 수 없다면, 하드웨어는 페이지 테이블의 메모리 주소를 파악하고 VPN을 인덱스로 하여 PTE 추출, PTE에서 PFN 추출 및 TLB에 탑재, 명령어 재실행.

Present Bit

• 페이지가 디스크로 스왑되는 것을 가능하게 하려면, 하드웨어가 PTE에서 해당 페이지가 물리 메모리에 존재하지 않는다는 것을 표현해야 함.
• present bit를 사용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는지를 표현.
• 만약 비트가 0으로 설정되어 있다면 메모리에 해당 페이지가 존재하지 않고 디스크 어딘가에 있음을 나타냄.
• 만약 물리 메모리에 존재하지 않는 페이지를 접근하면 페이지 폴트 발생.

페이지 폴트

• 페이지 폴트 발생 시, 운영체제의 페이지 폴트 핸들러가 처리 메커니즘을 규정.
• 만약 요청된 페이지가 메모리에 없고 디스크로 스왑되었다면, 운영체제는 해당 페이지를 메모리로 스왑해옴.
• 원하는 페이지의 스왑 공간상에서의 위치를 보통 페이지 테이블에 저장.
• 페이지 폴트 발생 시, 운영체제는 페이지 테이블의 항목에서 해당 페이지의 디스크 상 위치를 파악하여 메모리로 탑재.
• 디스크 I/O가 완료되면 운영체제는 해당 PTE의 PFN 값을 탑재된 페이지의 메모리 위치로 갱신.
• 위 작업 완료 시, 페이지 폴트를 발생시킨 명령어 재실행.
• 재실행에서 TLB 미스 발생 가능. 미스 처리 과정에서 TLB 값 갱신.
• 마지막 재실행 시 TLB에서 주소 변환 정보를 찾게 되고, 물리 주소에서 원하는 데이터를 가져옴.

메모리에 빈 공간이 없으면?

페이지 교체 정책

• 메모리에 여유 공간이 없을 때, 새로운 페이지 탑재를 위해 페이지들을 먼저 페이지 아웃 해야 할 수 있음.
• 교체할 페이지를 선택하는 것을 페이지 교체 정책.

페이지 폴트의 처리

TLB 미스 발생 시, 세 가지 경우.

• 페이지가 존재하며 유효한 경우. TLB 미스 핸들러가 PTE에서 PFN을 가져와서 명령어를 재시도.
• 페이지가 유효하지만 존재하지 않는 경우. 페이지 폴트 핸들러가 반드시 실행되어야 함.
• 페이지가 유효하지 않는 경우. 버그 등으로 잘못된 주소를 접근하는 경우이며, 운영체제의 트랩 핸들러에 의해 처리되도록 해야 함.

페이지 폴트 처리 과정

• 운영체제는 탑재할 페이지를 위한 물리 프레임 확보.
• 여유 프레임이 없다면, 교체 알고리즘을 실행해 메모리에서 페이지를 내보내고 여유 공간 확보.
• 물리 프레임 확보 후, I/O 요청을 통해 스왑 영역에서 페이지를 읽어옴.
• 운영체제는 페이지 테이블을 갱신, 명령어 재시도.
• TLB 미스가 발생, 다시 한 번 재시도하면 TLB 히트 및 접근 가능.

교체는 실제 언제 발생하는가

• 메모리에 항상 여유 공간을 비워두기 위해 대부분 운영체제들은 여유 공간 최댓값/최솟값을 설정해 교체 알고리즘 작동에 활용.

여유 공간 비워두기

• 운영체제가 여유 공간의 크기가 최솟값보다 작아지면 여유 공간을 확보하는 스왑 데몬(페이지 데몬) 스레드가 실행.
• 스레드는 여유 공간의 크기가 최댓값에 이를 때까지 페이지 제거.
• 다수의 페이지들을 클러스터/그룹으로 묶어 한 번에 스왑 파티션에 저장함으로써 디스크 효율 개선. 클러스터링은 디스크의 탐색과 회전 지연에 대한 오버헤드를 경감시킴.

---

Swapping: Policies

물리 메모리 크기의 극복: 정책

• 빈 메모리 공간이 거의 없으면 운영체제는 메모리 압박 해소를 위해 다른 페이지들을 강제적으로 페이징 아웃.
• 내보낼 페이지의 선택은 운영체제의 교체 정책에 의해 정해짐.

캐시 관리

• 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수 최소화. 즉, 디스크로부터 페이지를 가져오는 횟수 최소화. (== 캐시 히트 횟수 최대화)
• 캐시 히트/미스 횟수를 안다면 프로그램의 평균 메모리 접근 시간을 계산 가능.
• 현대 시스템에서는 디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 줌.
• 디스크 속도 수준으로 느리게 실행되는 것을 방지하기 위해서는 적절한 정책을 만들고 미스를 최대한 줄여야 함.

최적 교체 정책

• 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킴.
• 현재 탑재되어 있는 각 페이지들의 미래를 살펴보아, 가장 먼 미래에 접근 될 페이지를 내보냄.
• 일반적으로 미래의 접근을 미리 알 수 없으므로 구현이 불가.

간단한 정책: FIFO

• 단순하게 큐의 마지막에 있는, 가장 먼저 들어온 페이지를 내보냄.
• 구현하기 매우 쉬우며, 성능은 떨어짐.

또 다른 간단한 정책: 무작위 선택

• 구현하기 쉬우며 평균적으로 FIFO보다는 약간 더 좋은 성능을 보임.

과거 정보의 사용: LRU

• 과거 사용 이력을 활용하여, 가까운 과거에 한 페이지에 접근했다면 가까운 미래에 그 페이지를 다시 접근할 것이라고 추측할 수 있음.
• 활용 가능한 과거 정보는 빈도 수, 최근성이 있음. 이는 지역성의 원칙에 기반을 둠.
• LFU 정책 : 가장 적은 빈도로 사용된 페이지를 교체.
• LRU : 가장 오래 전에 사용했던 페이지를 교체.

워크로드에 따른 성능 비교

지역성이 없는 경우

• 접근되는 페이지들의 집합에서 페이지가 무작위적으로 참조되는 경우.
• 어느 정책을 사용하든 큰 상관이 없음. LRU, FIFO, 무작위 선택 모두 동일한 성능을 보이며, 히트율은 캐시의 크기에 의해 결정 됨.
• 캐시가 충분히 크면 어느 정책을 사용하든 상관 없음.

80 대 20의 경우

• 20%의 페이지에서 80%의 참조 발생, 나머지 80%의 페이지에서 20%의 참조만 발생하는 경우.
• 인기있는 페이지들을 캐시에 오래 두는 LRU가 가장 좋은 성능. FIFO와 랜덤 정책도 나쁘지 않은 성능.

순차 반복의 경우

• 순서대로 모든 페이지를 반복하여 참조하는 경우.
• LRU와 FIFO에서 가장 안 좋은 성능을 보임.
• 랜덤의 경우 훨씬 좋은 성능을 보임.

과거 이력 기반 알고리즘 구현

LRU의 경우

• 완벽히 구현하기 위해서는 각 페이지 접근마다 해당 페이지가 리스트 가장 앞으로 이동하도록 자료 구조를 갱신해야 함.
• 어떤 페이지가 언제 사용되었는지 관리하기 위해 모든 메모리 참조 정보를 기록해야 함.
• 이를 효율적으로 하기 위해 하드웨어의 지원을 받을 수 있다. 예를 들어 페이지 접근이 있을때마다 메모리 시간 필드를 갱신.

LRU 정책에 근사하기

• 연산량을 고려했을 때, 완벽한 LRU를 만들기보다 LRU에 근사하는 식으로 만들면 훨씬 쉬움.
• use bit
  - 시스템의 페이지마다 하나의 use bit를 둠.
  - 페이지가 참조될 때마다 하드웨어에 의해 use bit가 1로 설정.
  - 시계 알고리즘에 의해 주기적으로 use bit를 지워가며 교체 대상을 찾는 방식.

갱신된 페이지 고려

• 만약 어떤 페이지가 변경된 경우, 그 페이지를 내보내기 위해 비용(I/O) 지불 필요. 만약 변경되지 않았다면 내보낼 때 추가 비용이 없이 다른 용도로 재사용될 수 있음.
• 따라서 dirty 페이지보다 깨끗한 패이지를 내보내는 것을 선호.
• modified bit를 이용해 교체 대상을 선택.
  - 페이지가 변경될 때마다 비트가 1로 설정.
  - 시계 알고리즘에 의해 교체 대상을 선택할 때 사용되지 않고 깨끗한 페이지를 먼저 찾도록.

다른 VM 정책들

페이지 선택

• 언제 페이지를 메모리로 불러들일지도 결정해야 함.
• 대부분 요구 페이징 정책 사용.
  - 요청된 후 즉시 해당 페이지를 메모리로 읽어들임.
• 어떤 페이지가 곧 사용될지 예상하면 미리 메모리로 읽어들이느 선반입 가능.
  - 성공 확률이 높을 때에만 해야 함.

클러스터링

• 변경된 페이지를 디스크에 반영하는 방식에 관한 정책.
• 디스크 드라이브는 여러 개의 작은 크기의 쓰기 요청보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있으므로 보통 모아서 한 번에 효율적으로 기록.

Thrashing

쓰래싱

• 메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 어떻게 해야?
• 끊임없이 페이징 하게 되는 상황을 쓰래싱이라고 함.
• 발견과 해결 기법
  - 진입 제어 : 다수의 프로세스가 존재할 때, 일부 프로세스의 실행 중지.
  - out-of-memory killer : 메모리 요구가 초과되면 많은 메모리를 요구하는 프로세스를 골라 죽임.

과도한 페이징에 대한 최적의 해결책 : 더 많은 메모리를 구입해라!!

---

Case Study: VAX

VAX/VMS 가상 메모리 시스템 배경

VMS

• 컴퓨터의 구조적 결함을 소프트웨어로 보완한 사례.

메모리 관리 하드웨어

VAX-11

• 하이브리드 구조. 주소 공간 절반은 프로세스 공간, 각 프로세스마다 다르게 할당.
• VAX 하드웨어의 페이지 크기가 512바이트로 매우 작음. 선형 페이지 테이블 크기가 지나치게 커짐. -> VMS가 페이지 테이블 저장을 위해 메모리를 소진하는 것을 막아야.
  - 사용자 주소 공간을 두 개의 세그멘트로 나눠 프로세스마다 각 영역을 위한 페이지 테이블을 갖게 함. 스택과 힙 사이 사용되지 않는 주소 영역을 위한 페이지 테이블 공간이 필요 없게 됨.
  - 사용자 페이지 테이블들을 커널의 가상 메모리에 배치하여 메모리 압박을 줄임. 페이지 테이블을 할당하거나 크기를 키울 때, 가상 메모리, 세그멘트 내에 공간을 할당. 메모리 고갈 시, 페이지 테이블의 페이지들을 디스크로 스왑하여 물리 메모리를 다른 용도로 사용할 수 있게 함.

페이지 교체

VAX 페이지 테이블 항목이 갖고있는 비트

• 유효 비트, 보호 필드, 변경 비트, 운영체제 예약 필드, 물리 메모리 페이지 위치를 저장하기 위한 물리 프레임 번호.
• reference bit가 없음. 어떤 페이지가 자주 사용 중인지를 하드웨어 지원 없이 판단해야 함.
• 메모리를 너무 많이 사용하는 프로그램에 대한 대비책이 없음.

세그멘트된 FIFO 교체 정책

• 각 프로세스들은 상주 집합 크기라는 메모리 유지할 수 있는 최대 페이지 개수를 지정.
• 각 페이지들은 FIFO 리스트에 보관. 페이지 개수가 RSS보다 커지만 제일 먼저 들어왔던 페이지가 방출.
• 추가적으로 전역 클린-페이지 프리 리스트와 더티-페이지 리스트라고 하는 두 개의 second-chance list를 도입.
  - 메모리에서 제거되기 전에 페이지가 보관.
  - 다른 프로세스에서 빈 페이지가 필요하면 전역 클린 리스트에서 첫 프리 페이지를 꺼냄.
  - 원래의 프로세스가 해당 페이지가 회수되기 전에 폴트를 발생시키면, 프리 리스트에서 페이지를 가져와 다시 사용하는 식으로 디스크 접근을 피함.
• 전역 second-chance list 크기가 클수록 세그멘트된 FIFO 알고리즘은 LRU와 유사하게 동작.

페이지 클러스터링

• VMS의 작은 페이지 크기 극복
• 페이지의 크기가 작을수록 스왑할 때 디스크 I/O가 비효율적.
• 클러스터링 기법을 써서 전역 더티 리스트의 페이지들을 작업 묶음으로 만들어 한 번에 디스크로 보내서 성능 향상.

그 외의 VM 기법들

demand zeroing

• 페이지가 주소 공간에 추가되는 시점에, 페이지 테이블에 접근 불가능 페이지라고 표기하고 항목 추가.
• 프로세스가 추가된 페이지를 읽거나 쓸때 트랩 발생.
• 트랩을 처리하며 물리 페이지를 0으로 채우고, 프로세스의 주소 공간으로 매핑하는 등 필요한 작업을 함.
• 프로세스가 해당 페이지를 전혀 접근하지 않는다면 이 작업들을 피할 수 있다는 장점.

copy-on-write

• 운영체제가 한 주소 공간에서 다른 공간으로 페이지를 복사할 필요가 있을 때, 복사하지 않고 해당 페이지를 대상 주소 공간으로 매핑, 해당 페이지 테이블 엔트리를 양쪽 주소 공간에서 읽기 전용으로 표시.
• 만약 양쪽 주소 공간이 읽기만 하면 더 이상 처리 필요 없이 빠른 복사 가능.
• 둘 중 하나가 페이지 쓰기를 시도하면 운영체제 트랩 발생.
• 운영체제는 해당 페이지가 COW 페이지인 것을 파악, 새로운 페이지 할당, 데이터 복사, 주소 공간에 매핑.