CS Week 3 - 운영체제(3)

¿curious_jin¿·2026년 1월 7일

COW CS FIFO LFU LRU MMU PFF PTE Second Chance WSClock mmap mpd page fault tlb 세그먼테이션 스래싱 운영체제 페이징

CS(Computer Science) 독학

목록 보기

3/3

Table of Content

이전 WEEK 2 - 운영체제 (1)에서 프로세스와 CPU의 할당을 주된 내용으로 학습하였다면 이번 WEEK 3 - 운영체제 (2)에서는 실제 메모리와 관련된 여러 메커니즘들을 위주로 공부할 차례이다.

주제	세부 핵심 내용
1. 가상 주소와 가상 메모리 - 독립된 가상 공간	- 논리(가상) 주소와 물리 주소
	- MMU(Memory Management Unit) 이란 ?
	- PTE(Page Table Entry) 란 ?
	- 가상 메모리(Virtual Memory)
2. 세그먼테이션(논리적 단위) vs 페이징(고정 단위) - 고전적인 두 가지 메모리 관리 기법	- 세그먼테이션(Segmentation)
	- 페이징(Paging)
3. 페이징과 페이지 테이블 설계 - 세부 페이징 기법	- 단일 레벨 페이지 테이블 구현
	- 다단계 페이지 테이블(Multi-Level Paging) 구현
	- Huge Page 구현
4. TLB (Translation Lookaside Buffer) - TLB 란 ?	- TLB의 역할
	- TLB의 문제점
	- TLB의 구조
	-프로세스 전환
5. Demand Paging & Page Fault - 메모리 관리의 필수 Page Fault !	- Demand Paging
	- Page Fault란 ?
	- Page Fault의 실제 과정
6. 페이지 교체 알고리즘 - 메모리 관리의 “교체”	- OPT (Belady’s Optimal) - 이론적인 하한선
	- FIFO(First In First Out)
	- LRU(Least Recently Used)
	- Clock (Second Chance)
	- LFU(Least Frequently Used)
	- WSClock
7. 스래싱(Thrashing)·워킹셋(WS)·프레임 할당 - 메모리 관리의 “분배”	- 스래싱(Thrashing)이란 ?
	- 워킹셋(Working Set, WS( $\Delta$ ) )에 대해
	- 해결방안 1 : 프레임 할당 정책
	- 해결방안 2 : PFF(Page Fault Frequency) 제어 정책
	- 해결방안 3 : MPD(Multi-Programming Degree) 제어 정책
8. Copy-on-Write·공유메모리·메모리맵 - 메모리 관리의 “공유”	- Copy-On-Write(COW) : 공유 규칙 1
	- 공유 메모리 (Shared Memory) : 공유 규칙 2
	- mmap : 연결 방법
9. 문제 - 페이지 교체 알고리즘 위주	- 문제 P1. (FIFO vs LRU)
	- 문제 P2. (Clock)
	- 문제 P3. (AMAT in VM)

1. 가상 주소와 가상 메모리 - 독립된 가상 공간

메모리가 실제로 어떻게 점유되고 어떻게 사용되는지를 알기 위해서는 먼저 그 뼈대가 되는 매커니즘을 이해해야 한다.

그렇기에 실제로 CPU는 각각의 가상 주소를 어떻게 다루고 이를 활용해 가상 메모리라는 것을 어떻게 이용하는지 알아보자.

논리(가상) 주소와 물리 주소

이전 시간 프로세스에 대해 배우며 각각의 프로세스는 침범없이 독립적으로 시행되어야 하므로 운영체제는 이들에게 실제 RAM의 주소, 물리 주소를 내어주지 않고 별도의 가상 주소를 만들어 이들을 독립적으로 관리한다고 하였다.

그렇기에 각각의 프로세스는 자신이 사용하는 주소를 메모리의 주소라고 인식하지만 실제로는 가상 주소를 사용하게 된다. 어떻게 이것이 가능하느냐 ?

각 프로세스는 메모리의 주소에 접근하기 위해 운영체제의 시스템 콜을 이용, 커널에게 작업을 넘기게 된다. 이 과정에서 커널이 CPU를 활용하여 이 작업을 하게 된다. 그런 CPU라는 하드웨어 옆에 달린 주소 번역 담당 통역기, MMU(Memory Management Unit)이 이 가상 주소를 실제 RAM에 해당하는 물리 주소로 바꾸어 특정 레지스터에 저장, 실제 작업을 하게 되는 것이다.
MMU(Memory Management Unit) 이란 ?

MMU란 메모리 관리를 위해 별도로 통역기 역할을 하는 하드웨어로 CPU 옆에 달린 “주소 번역 담당 통역기”라고 보면 된다.

내부적으로 CPU가 가상 주소를 받아 MMU에 넘기면 MMU는 이를 주소 변환 캐시, TLB(Translation Lookaside Buffer)에서 찾아보게 된다.

만일 TLB Hit 발생 시 TLB에서 물리 주소를 반환받아 주소 담당 레지스터에 이를 저장하게 되고, TLB에 해당 가상 주소가 없어 TLB Miss 발생 시 전체 페이지 테이블(PTE, Page Table Entry)에서 실제 물리 주소를 가져오게 된다.

PTE(Page Table Entry) 란 ?

앞서 살펴보았듯 각각의 프로세스들이 독립된 자신만의 가상 공간을 구축하도록 하기 위해 각각의 프로세스마다 고유한 가상 주소 공간을 할당, 이들을 한데 모아놓은 것을 페이지 테이블(PTE)이라고 한다.

이들은 RAM 상에 존재하는 커널의 메모리 공간에 저장되며, 각 프로세스 별 내용이 들어있는 PCB에 PTE의 주소 포인터가 들어있는 식이다. 프로세스가 실행되면 커널은 이 포인터를 타고 들어가 PTE를 로드, MMU와 TLB를 통해 주소 변환을 하게 된다.

이러한 가상 주소 → 물리 주소 변환 테이블은 RAM으로 향하는 통로와도 같기에 운영체제는 여기에 별도의 메타 데이터, “Flag”를 지정하여 관리한다. 플래그는 PTE에 직접 접근하는 MMU의 접근 권한과 상태를 판단하는 기준이 되는 여러 메타 데이터를 말한다. 이를 한 번 살펴보자.

플래그	이름	의미 / 역할
P (Present bit)	존재 비트	1이면 물리 메모리에 있음, 0이면 디스크에 있음 → 0일 때 접근 시 Page Fault 발생
R/W (Read/Write)	읽기·쓰기 권한	0 = Read only, 1 = Read/Write 가능
U/S (User/Supervisor)	접근 레벨	0 = 커널만 접근, 1 = 사용자도 접근 가능
A (Accessed)	접근됨	최근 접근 여부 표시 (교체 알고리즘에서 사용, 예: LRU 근사)
D (Dirty)	수정됨	해당 페이지에 쓰기가 발생했는지 표시 (수정 알고리즘에서 사용)
NX (No eXecute)	실행 금지	코드 실행 금지(데이터 영역 보호)
PWT / PCD	캐시 제어	Page Write-Through, Page Cache Disable — 특정 페이지를 캐시할지 여부 결정
G (Global)	전역 페이지	컨텍스트 전환 시 TLB에서 flush 안 함 (성능 최적화용)

특정 데이터에 대해 사용자 / 커널만이 접근하여 읽기 / 쓰기 중 할 수 있는 행동을 제한하는 권한과 관련된 내용부터 이 데이터가 언제 접근되었고 언제 수정되었는지와 같은 상태 정보까지 모두 PTE에서 담고 있다.

데이터가 들어있는 실제 물리 주소 상에 이러한 메타 데이터를 저장하기 보다는 그곳으로 향하는 통로에 메타 데이터를 저장하는 것이 맞아 보인다.

가상 메모리(Virtual Memory)

가상 주소라는 매커니즘을 통해 운영체제는 프로세스 간의 독립성과 안정성을 확보할 수 있었다. 하지만 챙기지 못한 것이 있었으니 바로 “효율성”이다.

프로세스는 실행될 때 자신의 모든 내용을 주기억장치인 RAM상에 올리게 된다. 이는 말그대로 프로세스와 관련된 “모든” 내용이며 실제 사용자가 이들 모두를 당장 필요로 할 가능성은 0에 수렴한다.

그렇기에 등장한 것이 가상 메모리라는 개념으로 프로세스가 자신의 주소로 인식하는 페이지 테이블, PTE 상에는 모든 데이터의 주소를 넣어놓지만 실제로 RAM 상에는 프로그램 실행 시 자주 사용되는 내용만을 올려놓고 나머지는 가상 메모리, 실제 디스크 상에 냅두는 것이다.

이를 구현하기 위해 PTE의 플래그 중 Present bit, P가 존재하는 것이며 만일 커널이나 사용자가 자주 사용되지 않던 프로그램의 내용에 접근하고자 하면 이는 PTE에는 존재하지만 실제 RAM 상에 아직 올라오지 않았으므로 P = 0 플래그를 가지며 이 경우 MMU가 Page Fault 오류를 발생시키게 된다.

이 오류가 발생하면 커널은 디스크에서 해당 페이지를 읽어 RAM에 다시 올리게 되고 비로소 P = 1로 플래그가 갱신, 사용자나 커널이 해당 주소에 다시 접근할 수 있게 된다.

이와 같은 페이지 요청을 요구 페이징(Demand Paging)이라고 하며, 이처럼 실제로 RAM에 올라와 있지 않고 디스크 상에서 Page Fault만을 기다리는 데이터 공간을 스왑 영역(Swap Space)이라고 한다.

가상 메모리는 이처럼 실제로 프로세스가 전체 프로그램을 필요로 하지 않는다는 전제에서 출발하여 작은 메모리 공간만을 효율적으로 사용해 프로세스를 돌릴 수 있도록 만들어주는 희소 사용(Sparce Use)을 기반으로 하고 있다.

2. 세그먼테이션(논리적 단위) vs 페이징(고정 단위) - 고전적인 두 가지 메모리 관리 기법

이제 프로세스가 실행된다고 해당 프로그램의 모든 내용을 RAM 상에 올리는 것이 말이 안된다는 것을 알았다.

그렇다면 이를 쪼개서 하나하나 올려야 할텐데 “어떻게 쪼갤래 ?” 인 메모리 관리에 대한 고전적인 두 가지 방법을 살펴보자.

세그먼테이션(Segmentation)

가장 먼저 나왔던 개념인 세그먼테이션이란, 프로세스의 각 내용을 논리적인 의미 단위로 나누어 RAM 상에 올리는 방법이다.

이는 가상 주소를 통해 물리 주소로 변환하는 페이지 테이블 이전에 나온 개념으로 하나의 프로세스를 논리적인 의미에 따라 몇 개의 세그먼트로 나누어 RAM 상에 저장, 주소 요청 시 세그먼트 번호와 오프셋을 요청하여 원하는 데이터를 읽는 구조로 이루어졌다.

이전 주소 과정에서 설명했듯이 세그먼트 번호에 따라 RAM 상의 base 주소를 받고, 오프셋을 통해 base 주소 기준 몇 번째 바이트에 원하는 데이터가 있는지 계산하게 된다.

논리적인 의미에 따른 분류란 프로세스를 구성하는 내용인 코드 / 데이터 / 스택 / 힙 공간을 기준으로 나눈다는 의미이다.

장점 )

쉽게 말해 역할에 의해 매우 큰 단위로 나누었다는 뜻으로 논리적인 의미별로 메모리 공간을 분리하였으므로 이를 나타내는 세그먼트 번호를 통해 앞서 PTE의 플래그에 의해 구현되었던 데이터와 관련된 여러 권한과 상태를 관리할 수 있다.

예를 들어 프로세스의 코드 영역은 프로세스의 고유한 행동 방침이 담겨있는 공간으로 사용자에 의해 수정될 일이 없다. 그렇기에 코드 영역을 0번째 세그먼트에 담을 시 0번째 세그먼트에 대해서는 수정이 불가능하도록 설정하는 것만으로 프로세스의 모든 코드 영역을 보호할 수 있게 되는 것이다.

단점 )

반면 크나큰 단점 역시 존재하는데 바로 너무 크고 가변적인 단위 설정으로 인해 실제 RAM 상에 이러한 세그먼트들을 간편하게 배치하기가 너무나 어렵다는 점이다.

이를 외부 단편화(External Fragmentation)라고 부르며 세그먼트의 길이가 너무나 다양하고 커서 각각의 세그먼트별로 “딱 맞는 RAM 공간”을 찾기가 어렵고 이에 따라 추가적인 RAM 공간 할당이 제한적이라는 의미를 가진다.
페이징(Paging)

결국 외부 단편화, “효율성”을 챙기기 위해 나온 메모리 관리 방식이 바로 페이징이다.

페이징 방식은 앞서 지속적으로 나온 개념으로 프로세스 전체 내용의 주소를 가상 주소로 변환하여 이들을 “동일한 크기의 페이지”로 나누어 관리하는 방식을 말한다.

이렇게 되면 하나의 페이지에 담겨있는 내용은 다양하지만 그 크기는 일정하게 유지되므로 메모리의 공간을 똑같이 “동일한 크기의 프레임”으로 나누어 페이지를 그대로 담아낼 수 있다. 운영체제가 관리하기 굉장히 용이하다는 뜻. 이 크기는 4KB, 8KB 등으로 고정된 크기로 각각의 물리적인 메모리 단위 공간을 “프레임”이라고 한다.

예를 들어 특정 데이터를 찾기 위해서는 페이지 번호를 통해 base 주소를 받고, 오프셋을 통해 이를 기준으로 데이터를 찾는 식이다.

장점 )

페이징 기법에서는 프로세스와 메모리 공간을 모두 동일한 크기로 나누어 관리하므로 앞서 세그먼테이션 기법에서 발생하였던 외부 단편화 문제가 깔끔하게 해결된다. 모두 동일한 크기를 가지기에 어떤 페이지든 아무 프레임에 넣고 base 주소만을 저장해놓으면 되기 때문.

이는 단순히 “프로세스의 한 부분이 담긴 하나의 페이지를 메모리 상에 올리는 것이 쉽다”에서 그치는 것이 아니라 페이지를 메모리 상에 넣고 교체하고 제거하는 페이지 교체 알고리즘의 구현과 가상 메모리 구현에 큰 장점을 가진다는 의미를 가진다.

단점 )

반면 세그먼테이션에 비해 아주 작은 크기를 가지는 페이징은 그 작은 크기만큼이나 많은 수의 페이지 테이블, PTE를 필요로 하게 되어 메모리 오버헤드가 자연스레 증가하게 되고 이를 캐싱하기 위한 별도의 캐시 공간인 TLB를 필요로 하게 된다.

또한, 페이지 크기를 고정해놓았기에 메모리 공간 상이 아니라 하나의 페이지 블록 내에서의 여유 공간이 남게 되는 내부 단편화 문제가 발생하게 된다.

“단편화”란 결국 데이터를 잘게 쪼개 관리하는 과정에서 낭비되는 여유 공간이 발생하는 문제를 말한다. 페이징의 경우 메모리 공간을 모두 동일하게 설정하여 관리하는 바람에 예컨대 4KB 보다 작은 조각의 데이터는 낭비되는 공간이 생길 수 밖에 없고 세그먼테이션의 경우 반대로 여러 크기의 데이터 조각을 이용하기 때문에 딱 맞는 메모리 공간을 찾기 위해 딱 맞지 않는 다른 메모리 공간이 낭비되는 문제가 발생하는 것이다.

세그먼테이션의 보호 기능과 페이징의 메모리 관리 효율성을 모두 챙기기 위해 최근에는 둘을 결합한 시도로, 1차적으로 세그먼테이션에 의한 선형 주소를 부여 및 검사, 실제 메모리 관리는 페이징을 이용하는 기법도 생겨나게 되었다.

3. 페이징과 페이지 테이블 설계 - 세부 페이징 기법

이제 더 핵심이 되는 페이징 과정이 실제로 어떻게 구현되는지 살펴보자.

단일 레벨 페이지 테이블 구현
1. 가상 주소 공간 크기 계산
  
  한 페이지의 크기를 4KB(4096 bytes) 라고 생각해보자.
  
  가상 주소의 경우 “각 페이지 번호 bits”에 “페이지 내 offset bits”를 더해 만들어진다.
  
  Offset bits란 페이지 내 시작 바이트를 찾기 위한 비트 수로, 한 페이지 내에서 4096개의 바이트 중 하나의 위치를 표현하기 위해서는 $2^{12}$ , 12 bits가 필요하게 된다.
  
  현대 x86-64 등의 CPU 아키텍쳐는 약 256 TB( $\simeq 2^{48}$ )의 주소 공간 크기를 표현할 수 있는 48 bit 가상 주소를 이용하기에 이 중 offset 12 bit를 제외한 36 bit가 페이지 번호를 표현하는 값으로 남게 된다.
  
  → 현대 주소 공간 : 48 bit = 페이지 번호 36 bit + 오프셋 12 bit (페이지 크기 4KB)
  이는 단일 프로세스가 256 TB의 메모리를 차지할 수 있으며 총 48 bit의 주소를 통해 관리된다는 의미이다.
  또한, 그 주소는 세부적으로 단일 프로세스가 $2^{36} \simeq 687억$ 개의 페이지를 가질 수 있으며 하나의 페이지는 $2^{12} \simeq 4096$ 바이트를 가진다는 의미를 담고 있다.
2. 물리 주소 공간 크기 계산
  
  주소 저장의 경우 DRAM 상에서 동일한 크기로 나뉜 프레임의 base의 실제 물리 주소만을 페이지 테이블에 저장, 이후 오프셋과의 결합을 통해 최종 물리 주소를 찾게 된다.
  
  현대의 x86-64등의 CPU 아키텍쳐는 약 52bit 크기의 실제 물리 주소를 제공한다. 이는 $2^{52} \simeq 4\;petabytes$ 의 값으로 미래 확장성을 고려한 크기이다.
  
  → 실제 물리 주소 공간 : 52 bit
  이는 전체 DRAM, 메모리 공간이 최대 4 PB의 크기를 가질 수 있으며 총 52 bit의 주소를 통해 관리된다는 의미이다.
3. PTE 크기 계산
  
  그럼 하나의 페이지를 표현하기 위해 PTE는 얼만큼의 메모리를 차지하는가 ?
  
  페이지 테이블에서 하나의 페이지에는 페이지의 base 주소가 되는 위 실제 물리 주소, 52 bit에 더해, 앞서 PTE에서 설명한 여러 권한 및 상태 정보(ex. Present, No Execute, R/W, U/S 등)를 담기 위해 한 페이지 당 64 bit(8 바이트)를 차지하도록 설계되어있다.
  
  → 페이지 하나의 크기 : 64 bit(8 바이트) = 실제 물리 주소 52 bit + 보호 정보 12 bit
  이는 단일 프로세스의 입장에서 48 bit 짜리 가상 주소를 입력하였을 때 이를 실제 52 bit 짜리 물리 주소로 변환해주는 페이지 하나가 64 bit(8 바이트)의 크기를 가진다는 의미이다.
  
  단일 프로세스는 앞서 계산했듯이 이 경우 약 687억 개의 페이지를 가지므로 각 페이지의 크기를 곱하면 단일 프로세스가 점유하는 메모리 크기는 $687억 \times 8B\simeq512 GB$ 가 된다.
  
  대부분의 프로세스는 해당 크기의 메모리를 필요로 하지 않으므로 이 경우 대부분의 메모리 공간이 PTE에 의해 낭비되게 되는데 이는 프로세스의 이론상 가능한 최대 크기를 전부 주소로 변환하여 메모리 공간에 올리려 하였기 때문에 발생한 문제이다.
다단계 페이지 테이블(Multi-Level Paging) 구현

위 문제를 해결하기 위해 등장한 다단계 페이지 테이블은 프로세스의 주소 공간을 여러 레벨로 나누어 실제로 쓰이는 주소만을 PTE로 작성, 메모리 공간에 올리는 방법이다.

x86-64 아키텍쳐의 경우 기존 48 bit의 가상 주소를 4단계로 나눈 4단 페이지 테이블을 이용한다.
```
[9]  PML4   (Page Map Level 4)
[9]  PDPT   (Page Directory Pointer Table)
[9]  PD     (Page Directory)
[9]  PT     (Page Table)
[12] offset (Page offset)
```
이와 같은 상위/하위 레벨의 주소를 이용하여 사용되지 않는 디렉토리의 하위 테이블을 전부 비워놓는 식으로 희소 공간에 대응, 매우 큰 메모리를 절약하게 된다.

“1. 가상 주소와 가상 메모리”에서 보았듯 프로세스 내에서 사용되지 않는 부분은 애초에 DRAM에 올라오지 않으며 PTE 조차 실제로 메모리 상에 만들어지지 않는 것이다.
Huge Page 구현

하지만 이와 같은 4KB의 작은 크기를 가지는 페이지는 실제로 이용하는 코드나 데이터의 크기가 수 GB 수준으로 올라오게 되는 경우 이를 표현하기 위해 수많은 페이지를 TLB 상에서 훑어보게 되며 그 과정에서 굉장히 많은 양의 TLB Miss가 발생하게 된다.

이를 해결하기 위해 등장한 것이 Huge Page. 4KB로 조금씩 조금씩 데이터를 불러오지 말고 한 번에 수 MB 크기의 데이터를 불러와서 사용하자는 방식이다. 그러면 매번 TLB Miss를 만나고 매번 다시 PTE를 찾아보는 오버헤드가 줄어들 것이다.

단, 이와 같은 방법의 경우 실제 이용 코드가 아무리 작더라도 최소 페이징 단위를 맞춰야 하기에 내부 단편화 문제가 다시금 부각되기 마련이다.

4. TLB (Translation Lookaside Buffer) - TLB 란 ?

TLB의 역할

결국 프로세스 별 가상 메모리 공간을 최대한 활용하기 위해서는 그 변환 테이블인 PTE가 필수적이며, 너무 큰 PTE를 캐싱하기 위한 메모리 공간인 TLB가 필수적이다.

이는 가상 주소 → 실제 물리 주소로 변환해주는 테이블인 PTE가 DRAM에 존재하지만, 이를 더 효과적으로 접근, 다루기 위해 CPU 옆에 별도의 캐싱용 메모리 공간인 TLB가 존재하는 것이다. CPU 옆에 존재하는 주소 변환용 별도 하드웨어인 MMU가 사용하는 용도로 마치 L1-L2-DRAM의 데이터 메모리 구조와 유사.

애초에 DRAM에 존재하는 PTE 자체가 프로세스의 모든 내용을 담고 있지 않고 필요한 일부 데이터만을 저장하고 추가 접근 시 Page Fault를 발생시켜 추가 데이터를 불러오는 방식이기에 TLB는 그보다 더 자주 쓰이는 주소들을 캐싱하게 된다.

그 크기는 수 십 ~ 수 백 개의 엔트리만을 가지고 있으며 만일 요청되는 가상 주소가 TLB내에 존재하여 TLB Hit이 발생하게 되면 그 접근 속도는 하나의 파이프라인 수준에서 처리되며 TLB Miss 발생 시 PTE로 접근하게 된다.
TLB의 문제점

이러한 TLB는 당연하게도 프로세스에서 사용되는 데이터의 주소들을 담기에는 너무나 작기에 여러 가지 문제점이 발생하게 된다.
1. TLB 용량 초과
  
  만일 하나의 프로세스에서 “동시에” 사용하는 데이터에 해당하는 페이지의 주소 크기가 TLB 자체의 용량을 초과하게 될 경우 이들은 전부 동시에 캐싱되지 못하므로 계속해서 PTE에 접근해야하는 오버헤드가 크게 발생하게 된다.
2. 랜덤 접근
  
  캐시 메모리의 특성 상 “자주 쓰이는” 데이터가 아니라 랜덤한 데이터에 대한 접근이 늘어나면 늘어날수록 TLB Miss의 비율이 늘어나게 된다.
TLB의 구조
1. 다단 TLB
  
  위와 같은 문제점을 해결하기 위해 TLB는 기존 메모리와 동일하게 여러 다단계의 구조를 가지도록 발전해왔다. 기존처럼 CPU 옆에 붙어 MMU가 바로 활용하도록 하는 L1 TLB와 별도로 조금 더 넓지만 조금 더 먼 L2 TLB를 활용하는 식이다. 이를 통해 L1 TLB Miss 시 PTE가 아닌 L2 TLB를 살펴보도록 만들었다.
2. 페이지 크기별 분리
  
  프로세스가 대용량의 연속된 메모리 사용을 요구할 경우 앞서 설명한 Huge Page가 작동하게 되는데 기존 4KB에 해당하는 TLB와 Huge Page에 해당하는 TLB를 분리하여 관리하게 된다.
  
  이는 데이터를 효율적으로 관리하기 위해 필요되는 Huge Page는 하나의 페이지가 기존 페이지에 비해 매우 큰 크기를 가지므로 낮은 엔트리 개수를 가지게 되기에 TLB Hit 비율에서 크게 다른 성향을 보이고, 그렇기에 애초에 물리적인 분리를 통해 관리하는 경우가 대부분이다.
프로세스 전환

그러면 만일 사용자가 하나의 프로세스만을 사용하지 않고 여러 프로세스를 사용하는 경우에는 어떻게 작동하게 되느냐 ?

서로 다른 프로세스는 각각의 가상 주소를 통해 별도로 관리되어야 하므로, 그 가상 주소를 실제 물리 주소로 변환해주는 TLB에서 역시 이들은 별도로 분리되어 관리되어야 한다.

이는 가상 주소를 표현하는 비트 수 자체가 실제 물리 주소에 비해 작게 관리되는 탓에, 서로 다른 프로세스가 동일한 가상 주소를 가지는 경우가 쉽게 발생하기 때문이다.

가장 먼저 떠오르는 것은 프로세스 변환, 즉 컨텍스트 스위칭이 일어나는 경우 기존 TLB를 아예 비워버리는 TLB Flush를 시행하는 것이다. 하지만 이 경우 잦은 프로세스 변경 과정에서 매우 큰 초기 오버헤드가 발생하게 되므로 아래 두 방법이 등장하게 되었다.
1. ASID (Address Space ID)
  
  TLB 내에 가상 주소를 저장할 때 해당 페이지, 해당 TLB 엔트리에 별도의 프로세스 식별자 태그를 붙여 관리하는 것이다.
  
  이러한 프로세스 식별자 태그는 언뜻 보기에는 기존 PCB에 담겨있던 프로세스 별 고유한 ID인 PID를 이용하면 될 듯 싶지만 실제로는 별도의 식별자인 ASID를 만들어 사용하게 된다.
  
  → (VPN, ASID) -> PPN
  
  이는 기존 PID가 모든 프로세스를 표현하기 위해 너무나 큰 크기를 가지기 때문으로, ASID의 경우 8~12 비트 수의 작은 크기로 그때그때 각 프로세스에 할당되어 PCB 상에 저장되며 이용이 끝난 후 expired 된다.
2. PCID (Process-Context ID)
  
  PCID의 경우 위 ASID와 동일한 기능을 하는 식별자 태그를 일컫지만 서로 다른 아키텍쳐에서 사용된 경우이다.
  
  CPU를 효율적으로 만들기 위해 대표적으로 CISC(Complex Instruction Set Computer)와 RISC(Reduced Instruction Set Computer)라는 설계 철학이 존재하였다. 이들은 각각 Software-Friendly / Hardware-Friendly로 명령어를 기본적으로 복잡하게 / 단순하게 유지하자는 설계 철학이다.
  
  기본적으로 하나의 CPU 명령어가 복잡한 일을 처리하는 CISC는 위와 같은 ASID 개념이 없었고, 이에 나중에 “프로세스의 컨텍스트를 참고한 ID”라는 개념에서 만들어낸 것이 PCID이다.

5. Demand Paging & Page Fault - 메모리 관리의 필수 Page Fault !

이제 프로세스를 실행하기 위해 각각의 프로세스마다 고유한 가상 주소를 부여하고, 이들을 RAM 상에서 분리함과 동시에 더 빠른 접근을 위해 TLB라는 캐시 메모리를 이용하였으며 이 주소 공간을 담는 메모리 내에서의 프로세스 분리를 위해 ASID와 같은 별도의 식별자를 이용한다는 사실을 알게 되었다.

이제는 RAM에 존재하는 PTE로부터 주소 값을 가져와 TLB에 저장하는 세부적인 내용에 대해 알아보자.

Demand Paging

Demand Paging이란 앞서 이야기한 알고리즘 자체를 이야기하는 것으로 프로세스의 모든 페이지를 RAM 상에 올리지 않고 그때 그때 요구되는 페이지만을 RAM 상에 올리는 기법을 말한다.

사실상 페이징 기법을 이용하기 위해 요구되는 필수적인 요소, 혹은 페이징 기법 그 자체.
Page Fault란 ?

그럼 그 확인은 어떻게 하느냐 ?

앞서 주소 공간의 크기를 살펴볼 때 “페이지 하나의 크기 : 64 bit(8 바이트) = 실제 물리 주소 52 bit + 보호 정보 12 bit” 라는 이야기를 했었다.

그 보호 정보 12bit 내에 1bit는 존재 비트, Present(P) 비트를 나타내게 되는데 이 값이 곧 현재 해당하는 주소가 RAM 상에 로드된 상태이다라는 내용을 나타내주는 비트가 된다.

따라서 운영체제가 어떤 프로세스의 가상 주소 → 물리 주소 변환을 시도하게 될 때, 가장 먼저 옆에 있는 TLB를 뒤져보게 되고 TLB Hit 시 그대로 이용, TLB Miss 시 RAM 상에 존재하는 PTE를 찾아보게 되는데 이때 해당하는 가상 주소에 해당하는 Present Bit 가 1일 때(=PTE Hit) 그대로 이용, Present Bit가 0일 때(=PTE Miss) “Page Fault”를 발생시키게 된다.

Page Fault란 결국 요청되는 가상 주소에 해당하는 실제 물리 주소가 아직 PTE 상에 올라오지 않았다는 시스템적인 내용인 것이다.

이 경우 더 멀리 있는 디스크 상에서 이 값을 불러와야만 한다.
Page Fault의 실제 과정

방금 얕게 살펴본 CPU의 주소 변환 과정을 더 자세히 다뤄보자.

1️⃣ CPU가 주소 변환을 위해 가장 먼저 TLB에 접근

2️⃣ TLB Hit → 그대로 이용 / TLB Miss → PTE에 접근

3️⃣ PTE Hit → 그대로 이용 / PTE Miss = Present Bit가 0 → Page Fault 발생 !!
```
(별도 커널)

i. PTE에 빈 페이지 존재 → 그대로 불러옴 / **빈 페이지 X → 교체 알고리즘 !!**

ii.  페이지 교체 (I/O

iii. Present Bit = 1로 PTE 정보 최신화
```
4️⃣ TLB 최신화

5️⃣ 명령어 재실행

이와 같은 과정을 통해 결국 어떤 명령어가 들어왔을 때 이를 실행시키기 직전 단계에서 가상 주소 변환을 마치게 되고 명령어를 언제나 정상적으로 시행할 수 있게 된다.

주의해야 할 점은 TLB와 PTE Hit의 경우 그 지연 시간이 크게 차이가 나지 않지만 디스크 I/O를 거치는 경우 그 지연 시간이 수 백 만 배가 될 정도로 커질 수도 있기 때문에 결국 성능을 결정하는 가장 큰 요인은 디스크에서 한 번 페이지를 불러올 때 올바르게 잘 교체해야한다는 점이다.

6. 페이지 교체 알고리즘 - 메모리 관리의 “교체”

그럼 그렇게 중요하다는 페이지 교체 알고리즘에 대해 알아보자.

OPT (Belady’s Optimal) - 이론적인 하한선

벨라디안 최적이라고 불리는 이 알고리즘은 이론적인 알고리즘으로 “가장 늦게 쓰일 페이지를 퇴출시키자”라는 알고리즘이다.

실제로는 미래에 어떤 명령어가 어떤 주소를 필요로 할 지 모르기에 구현이 불가능하며 비교용으로만 사용된다.
FIFO(First In First Out)

다른 곳에서도 많이 쓰이는 FIFO 알고리즘은 이름 그대로 가장 먼저 들어왔던 페이지가 가장 먼저 퇴출되는 것이다.

굉장히 구현이 간단하고 유용해보인다는 장점을 가지지만 오히려 시간 개념이 없어 자주 쓰이는 유용한 페이지가 퇴출되는 경우도 생기기에 단순함이 장점일 뿐이다.
LRU(Least Recently Used)

시간 개념을 장착한 단순한 알고리즘이다. 역시 다른 곳에서도 많이 쓰이는 LRU 알고리즘은 가장 오래 쓰이지 않은 페이지가 가장 먼저 퇴출되는 방식이다.

실제로 페이지가 얼마나 유용한지를 올바르게 반영하기에 단순하지만서도 OPT에 가장 근접하다고 볼 수 있다. 하지만 이를 구현하기 위해서는 매 명령어의 주소 변환 과정마다 매 페이지의 “최근 시간”을 갱신해야 한다는 문제가 발목을 잡는다. → 사실상 근사만 가능
Clock (Second Chance)

Clock 알고리즘은 LRU의 비용적인 문제를 해결하기 위해 나온 LRU 근사 알고리즘으로 모든 페이지의 시간적인 순서를 기억하는 대신, 최근에 해당 페이지가 쓰인 적 있다 / 없다 만을 기억하는 알고리즘이다.

기본적인 매커니즘은 FIFO를 바탕으로 가장 먼저 들어온 페이지 순서로 퇴출하지만, 이에 R 매커니즘을 더해 해당 페이지가 최근에 쓰인 적이 있다면 (R=1) 이를 갱신하고 (R=0) 다음 순서로 미루게 된다.

그래서 붙은 이름이 Second Chance.

실제 모든 순서를 기억하는 LRU에 비해 각각의 페이지가 최근에 쓰인 적이 있느냐만을 기억하기에 그 비용이 현실적으로 다가온다.
LFU(Least Frequently Used)

LRU의 친구로, 가장 오래 쓰이지 않은 페이지를 제거하는 대신 가장 덜 쓰이는 페이지를 제거하는 기법이다.

얼핏 보기에 실제로 페이지의 유용성을 LRU보다도 더 잘 반영한 것처럼 보이지만 실제로는 여러 번 쓰이다가 이후로 계속 안 쓰이는 주소들이 많은 현실 프로세스의 특성 상 생각보다 유용하지는 않다.

위 문제를 개선하기 위해 이전 스케줄링에서도 보았던 Aging 매커니즘을 추가하기도 한다.

+) Aging 매커니즘이란 ?

기존 퇴출 알고리즘과 별개로 사용없이 특정 시간이 지나게 되면 자동으로 퇴출 대상이 되는 알고리즘.
WSClock - 현실적인 최대 타협안

WSClock 알고리즘은 Clock 알고리즘을 보완하여 등장한 알고리즘으로 기존 Clock 알고리즘이 그저 페이지가 “최근이 쓰인 적이 있다”만을 기록하는데에 반해 WSClock 알고리즘은 그래서 얼마나 오래전에 쓰였는데 ? 를 추가한 알고리즘이다.

이 알고리즘은 각 페이지마다 R 값을 할당하여 최근 사용 여부를 기록함과 동시에 last-use 시간을 기록한다. 이후 R 값에 의해 퇴출 대상이 된 페이지는 정해져 있는 전역 변수인, 별도의 $\Delta$ (Working Set Window)과 현재 시간을 통해 최근에 쓰였는지 여부를 한 번 더 확인하게 된다.

이를 통해 버리는 페이지는 “최근”에 쓰이지 않은 페이지로 정해지게 된다.

7. 스래싱(Thrashing)·워킹셋(WS)·프레임 할당 - 메모리 관리의 “분배”

이제 메모리 공간을 어떤 방식으로 쪼개고 관리하는지에 대해 알아보았다.

위 페이지 교체가 메모리 관리의 한 축이라면 여기서 다룰 프레임 할당은 메모리 관리의 다른 한 축을 담당하고 있다. 이에 대해 알아보자.

스래싱(Thrashing)이란 ?

“스래싱”이란 메모리 관리 시 가장 유의해야 할 문제점으로 Page Fault가 너무 빈번하게 발생하여 CPU가 계산하는 시간에 비해 I/O 대기 시간이 훨씬 많이 걸리는 문제를 말한다.

이 원인에 대해 조금 더 파헤쳐보자.

메모리를 쪼갠 각 페이지를 담는 물리적인 공간을 프레임이라고 하는데 결국 운영체제가 사용할 수 있는 최대 프레임은 RAM 전체에 해당하는 공간을 프레임 각각의 공간 크기로 나눈 개수로 정해져 있다. 운영체제는 이러한 프레임을 각각의 프로세스에 일정량 할당하여 해당 프로세스를 관리하게 된다.

그러면 Page Fault가 너무 많이 일어난다는 것은 해당 프로세스에 할당된 프레임 수가 너무 작아 쓸 수 있는 가상 주소가 너무 적기 때문이 아닌가 ?

더 할당해주면 되는 것 아닌가 ?

대부분의 경우 아니며, 스래싱이 발생하는 주된 이유는 할당된 프레임 수가 작기 때문도 있지만 그 본질적인 이유는 모든 프로세스의 요구되는 프레임 수의 합이 너무 크기 때문이다. 따라서 한 프로세스에 프레임 수를 더 할당해주더라도 그만큼 다른 프로세스의 프레임 수가 줄어들기에 본질적으로 스래싱 문제를 해결하지 못하는 것이다.

이들을 감지하는 방법으로는 Page Fault의 발생 빈도수, Page Fault Frequency(PFF)를 측정하는 방법이 존재한다. PFF가 급격히 증가하는 경우 아래 설명하는 워킹셋의 추정치가 급격히 증가하여 I/O 대기 시간이 폭증, 스래싱이 발생하게 된다.
워킹셋(Working Set, WS( $\Delta$ ) )에 대해

현재 가동중인 프로세스들이 필요로 하는 최소한의 프레임 수의 합을 “워킹셋(Working Set)”이라고 한다. 즉, 일정 시간 $\Delta$ 동안 “실제로” 접근한 페이지의 수를 말한다.

결국 이 워킹셋의 크기가 사용가능한 가용 프레임 수보다 크게 되면 위 스래싱이 발생하게 되는 것이다.

주의해야 할 점은 위 워킹셋은 특정 시간( $\Delta$ ) 동안 실제로 접근한 페이지 수로, $\Delta$ 를 너무 크게 잡을 경우 현재 필요없는 과거에 이용한 페이지까지 워킹셋에 포함될 우려가 있고 $\Delta$ 를 너무 작게 잡을 경우 현재 이용중인 페이지들을 모두 포함하지 못할 가능성이 있다는 점이다.

특히나 프로세스들은 특정 단계마다 이용하는 페이지가 급변하므로 이 경우 WS 역시 급변한다는 특징을 가지고 있다.
해결방안 1 : 프레임 할당 정책

프레임 할당 정책이란 운영체제가 전체 RAM에 해당하는 프레임을 각 프로세스에 어떻게 할당할지 정하는 정책을 말한다.
1. 지역(Local) 할당
  
  지역 할당 정책은 각 프로세스마다 고정된 크기의 프레임 수를 할당해주는 정책이다.
  
  프로세스마다 분리된 공간을 이용하기에 안정성이 매우 뛰어나지만 하나의 프로세스에서 요구 프레임 수가 급증하여 스래싱이 발생하게 될 경우 이를 막을 수 없으며, 단편화 문제로 인해 낭비되는 유후 프레임이 많아진다는 단점이 존재한다.
2. 전역(Global) 할당
  
  전역 할당 정책은 모든 프로세스가 전체 RAM 공간을 공유하는 정책을 말한다.
  
  각 프로세스가 본인의 워킹셋에 해당하는 프레임을 자유롭게 할당받을 수 있기에 낭비되는 유후 프레임 수가 줄어들고 효율이 증가한다는 장점이 있지만 반대로 전체 워킹셋의 크기가 가용 프레임의 크기를 넘어서게 될 경우 프로세스 간의 “간섭”이 발생하여 연쇄적인 스래싱이 발생할 수 있다는 큰 단점이 존재한다.
결국 개별 프로세스가 최소한으로 간섭받도록 하며 전체 효율성을 챙기기 위해서는 위 두 정책을 합친 “최소 프레임 + 공유 프레임”의 구조를 택하는 것이 현실적이다.

각 프로세스마다 정해진 최소 프레임을 보장받도록 한 뒤, 프레임을 더 요구하는 경우 공유 풀에서 프레임을 나눠주는 식이다.

그럼 프레임을 더 할당해주는 기준은 어떻게 될까 ?
해결방안 2 : PFF(Page Fault Frequency) 제어 정책

앞서 보았듯 추가 프레임을 더 할당해주는 기준은 PFF에 의해 정해진다.

이론적으로는 각 프로세스마다 요구되는 프레임 셋의 크기인 워킹셋에 맞추어 프레임을 할당해주는 것이 제일 효율적이지만, 급변하고 예측 불가능한 워킹셋을 참고하는 것은 어렵기에 그 대안으로 PFF를 사용하는 것*이다.

예컨대, 특정 프로세스의 PFF가 폭증할 경우 요구되는 워킹셋의 크기가 급증한다는 의미이므로 해당 프로세스에 대해 운영체제는 공유 프레임을 나눠주게 된다. 반대로 특정 프로세스의 PFF가 줄어드는 경우 요구되는 워킹셋의 크기가 줄어들어 유후 프레임이 발생한다는 의미이므로 이 경우 운영체제는 공유 프레임을 뺏게 된다.

PFF를 통해 할당 프레임 수를 조절하는 방법은 계산이 비교적 간단하다는 장점이 존재하지만 phase 변화에 의해 워킹셋의 크기가 급변하게 되는 경우 즉각적인 반영은 어렵다는 단점이 존재한다.
해결방안 3 : MPD(Multi-Programming Degree) 제어 정책

결국 PFF 폭증에 대비하는 추가적인 수단이 바로 MPD(Multi-Programming Degree)를 제어하는 방법이다.

MPD란 한 번에 실행중인 전체 프로세스의 수를 나타내는 값으로 더 자세히는 실행되기 위해 RAM 상에 올라와 있는 전체 후보 프로세스의 수를 말한다. 이들은 언제 CPU를 할당받아 실행될 지 모르므로 전부 프레임을 차지한 상태가 된다.

만일 전체 PFF가 모두 폭증하여 앞선 PFF 제어 정책, 공유 프레임 재할당만을 가지고 이를 해결할 수 없을 지경이 되면 그때가 바로 MPD 제어 정책이 빛을 발할 때이다.

이는 결국 $전체\,\, Working \,\,Set > 가용\,\, 프레임 \,\,수$ 인 경우로 운영체제는 프레임을 재할당하는 대신 실행 후보 수, MPD 자체를 낮추어 총합 WS를 낮추게 된다.

결국 메모리 관리 방식 중 프레임 할당의 경우 각 프로세스의 안정성과 효율성을 챙기기 위해 Local / Global 프레임 관리를 혼합하여 사용하며 그 공유 프레임의 미세 조정을 위해 PFF 제어 정책을 채용, PFF 폭증의 비상 상황을 대비해 MPD 제어 정책을 채용하는 것이다.

여기서 등장한 현재 사용중인 프레임, WS을 활용한 페이지 교체 알고리즘이 앞서 살펴본 WSClock이 된다.

8. Copy-on-Write·공유메모리·메모리맵 - 메모리 관리의 “공유”

여태까지 운영체제가 어떻게 메모리를 가상화하고, 이들을 분배하고 교체하는지에 대해 알아보았다.

마지막으로 남은 것은 “그러면 서로 다른 프로세스가 동일한 메모리를 공유해도 돼?” 라는 공유 차원에서의 문제를 풀어볼 시간이다. 관련된 중요 개념들을 살펴보자.

Copy-On-Write(COW) - 공유 규칙 1

메모리 관리에 있어 “공유”는 성능을 크게 좌지우지하는 요소 중 하나이다.

Copy-On-Write(COW)란 부모 프로세스를 동일하게 복사하여 자식 프로세스를 만들고 싶은 경우(fork()) 부모 프로세스의 모든 내용을 즉시 복사하지 않고 Page Fault 를 트리거로 만들어 자식 프로세스가 그때 그때 필요한 내용만을 복사하도록 하는 “메모리 지연 복사 기법” 이다.

조금 더 상세히 보자면 부모 프로세스의 모든 내용을 복사하는 대신 COW는 동일한 물리 메모리 공간을 가리키는 새로운 가상 주소를 만들어 자식 프로세스에 할당한 뒤, 그 쓰기 권한을 압수, Read-Only로 관리하게 된다. 이를 통해 fork() 과정에서 복사되는 데이터는 말 그대로 0 이며, 자식 프로세스는 모든 내용을 읽을 수 있게 된다.

이후 1️⃣ 자식 프로세스가 해당 데이터에 접근, 수정하려고 할 경우 2️⃣ 그 권한 오류에 의해 Page Fault가 발생하게 되고 운영체제는 해당 페이지에 대해 3️⃣ 새로운 프레임을 할당하고 그 부분만을 실제로 복사하게 된다. 이후 4️⃣쓰기 권한을 추가한 뒤 남은 명령어를 실행하게 된다.

COW는 결국 프로세스 생성, 복사 비용을 획기적으로 줄여주는 페이지 지연 복사 전략이다.

추가적으로 서로 다른 프로세스는 서로 다른 물리적 공간을 점유하고 있기에 동일한 데이터, 코드를 이용하기 위해 메모리를 공유하는 경우는 오직 동일한 프로세스의 다중 실행, 즉 부모-자식 관계의 프로세스에만 국한될 것처럼 보이지만 실상은 그렇지 않다. 서로 다른 프로세스더라도 동일한 데이터를 공유할 수 있지만 사용 내용이 완전히 동일한 부모-자식 프로세스 관계에서 이 효과가 두드러질 뿐이다.
공유 메모리 (Shared Memory) - 공유 규칙 2

위 COW는 초기 복사 시 주소만을 복사해놓고 이후 실제 접근 시 파일을 디스크에서 가져오는 read() 를 호출하는 방식의 메모리 관리 기법이다.

반면 공유 메모리란 서로 다른 프로세스들이 동일한 데이터를 이용할 경우 이들을 복사하여 개별적으로 관리하지 않고 아예 같이 사용하는 것 자체를 말한다.

물리적인 메모리 공간이 분리되지 않을 경우 본래 공유되는 데이터가 한 쪽에 의해 수정될 경우 다른 쪽에서 이 수정 여부를 모르기에 데이터가 깨지는 현상이 발생하게 된다.

따라서, 공유 메모리 전략은 데이터가 수정되는 경우 이를 공유하는 모든 프로세스가 수정된 데이터를 즉시 다시 읽는 동기화 전략을 추가적으로 사용하여 이를 방지한다.

동기화 전략이란 ?

동기화 전략이란 동일한 물리적인 메모리 공간을 어떤 순서로 어떻게 개입하여 읽고 쓸 지 정하는 전략으로 사용자 레벨 / 커널 레벨 / 하드웨어 레벨 등 다양한 레벨에서 전략이 나뉘지만 그 중 사용자 레벨에서 다루는 두 가지 동기화 전략에 대해서만 알아보자.
1. Mutex(Mutual Exclusion)
  
  Mutex 전략은 말 그대로 상호 배제 전략으로 동일한 메모리 공간을 여러 프로세스가 공유하지만, 한 번에 하나만 접근 가능하도록 하는 사용자 레벨에서의 전략이다.
  
  이는 별도의 락 객체를 여러 프로세스가 공유함으로 구현되며, 락 객체는 한 번에 하나의 프로세스 진입만을 허용하게 된다. 다른 프로세스들은 락 객체에 의해 진입이 막히며 계속해서 재진입을 시도하는 “스핀”을 걸게 된다.
  
  만일, 스핀이 계속되면 컨텍스트 스위칭 비용이 지속적으로 증가하므로 Lock 을 이용한 동기화는 이 경우에 대해 커널 레벨에서 자동으로 프로세스를 다운시키는 sleeping을 걸도록 진화하였다.
  
  조금 더 상위 레벨에서의 구현이지만 실제 프로젝트에서 사용한 예시를 들고와 보았다.
```
from threading import Lock

_PIPELINE_LOCK = Lock()    # 락(Lock) 객체
_PIPELINE_CONTEXT = {
	"qwen_generator":<QWEN MODEL>,
	"exa_generator":<EXAONE MODEL>,
	}

def _get_context(qwen_model:str, exa_model:str):
	key = (qwen_model, exa_model)
	with _PIPELINE_LOCK:
		cached = _PIPELINE_CONTEXT.get(key)
	return cached
	
def _run_pipeline(qwen_model:str, exa_model:str, ...):
	...
	cached = get_context(qwen_model, exa_model)
	...
	return result

def pipeline_batch(batch_size:int, ...):
	for i in range(batch_size):
		_run_pipeline(...)
```
  스핀과 Sleeping은 패키지 내부적으로 구현되어 코드 상에 드러나 있지 않지만 그럼에도 사용자 레벨에서 배치 처리를 하는 과정에 있어 캐시 메모리 충돌을 방지하기 위해 Lock 객체를 이용한 모습이다.
2. Semaphore
  
  Semaphore는 위 Mutex의 상호 배제 원리를 커널 수준으로 낮추고 사용자 레벨에서는 1개가 아니라 N개를 통과시키는 전략이다.
  
  실행 프로세스 수를 담는 카운터를 이용해 카운터에 여유가 없는 경우 wait()을 이용하여 프로세스를 잠들도록 하며, 여유가 생긴 경우 signal() 을 이용하여 대기 프로세스를 다시 깨우게 된다.
  
  이러한 동기화 전략 하에서 공유 메모리는 서로 독립적으로 관리되는 프로세스 간의 통신, IPC(Inter-Process Communication)의 여러 종류 중에서 가장 빠른 통신 기법으로 사용될 수 있다.
mmap - 연결 방법

mmap이란 memory map의 줄임말로 위에서 설명한 공유 메모리의 개념을 실제로 실현시키는 하나의 시스템 콜, 커널을 말한다.

mmap은 디스크에 존재하는 어떤 파일을 가상 주소에 연결하는 시스템 콜, 커널로 어떤 프로세스가 로딩될 때 디스크에 존재하는 여러 데이터나 파일을 필요로 하게 되는데 이들을 가상 주소에 매핑해주는 것이다. 즉, 디스크 파일의 직접 로딩(read() / write())를 늦춰주는 메모리 지연 로딩(Lazy Loading)의 핵심 주역이라고 할 수 있다.

본래라면 프로세스 로딩 시 요구되는 모든 데이터를 전부 RAM에 올려야 하며(read() / write()) 이 경우 당장 필요없는 데이터도 누적될 뿐더러 초기 오버헤드가 말도 안되게 커지게 된다. mmap는 따라서 프로세스 로딩 시 별도의 PTE 공간을 만들어 디스크 속 각 데이터의 물리 주소와 가상 주소를 매핑만 해주는 것으로 이 과정을 넘기게 된다.

이후 실제 데이터를 이용하고자 하는 요청이 들어오게 될 경우 디스크에서 데이터를 읽게 되고 이를 RAM에 올린 뒤 이후에 RAM에서 데이터를 읽는 요청을 처리하게 된다(load() / store()).

mmap를 통해 운영체제는 각 프로세스의 첫 실행 오버헤드를 안정적으로 관리할 수 있으며 필요한 데이터를 그때 그때 페이지 단위로 불러와 이용할 수 있게 된다. 또한, mmap가 불러온 페이지 캐시는 RAM에 저장되어 이후 서로 다른 프로세스들에 의해 이용될 수 있게 된다.

이러한 가상 주소 매핑 커널인 mmap가 어떤 공유 정책을 이용하느냐에 따라 두 갈래로 나뉘게 된다.
1. MAP_SHARED
  
  서로 다른 프로세스더라도 동일한 파일이라면 이를 공유해서 사용하자는 “공유 메모리”에 대한 정책을 말한다.
  
  이 경우 앞서 설명했듯이 서로 다른 프로세스가 동일한 메모리에 접근하고자 할 경우 mutex / semaphore 등의 동기화 정책을 통해 한 메모리 공간을 공유하게 된다.
2. MAP_PRIVATE
  
  서로 다른 프로세스더라도 동일한 파일이라면 이들을 처음에는 공유하지만, 누군가 내용을 쓰고자 할 경우 이들을 분리하자는 “COW”에 대한 정책을 말한다.
  
  이 경우 앞서 설명했듯이 서로 다른 프로세스가 초기에는 동일한 물리적인 메모리 공간을 공유하고 있지만 누군가 내용을 변경하고자 할 경우 Page Fault가 발생, 메모리 공간이 분리되게 된다.
이와 같은 mmap 커널은 데이터를 읽는 기본 시스템 콜인 read() 의 특수 버전으로 “주소를 걸어두고 Page Fault로 데이터를 읽는 시스템 콜”이라고 할 수 있겠다.

당연히 언제나 기본 read() 커널보다 좋은 것은 아니고 그 특성에 맞게 공유 데이터가 많거나, 초기 데이터 로드 오버헤드가 너무 크거나(대용량 데이터), 데이터 접근 패턴이 랜덤할 경우 유리하게 작용한다.

9. 문제 - 메모리 교체 알고리즘 위주

문제 P1. (FIFO vs LRU)

참조열: 1 2 3 4 1 2 5 1 2 3 4 5, 프레임=3

a) FIFO page fault 수

페이지 교체 알고리즘 중 FIFO의 경우 First In First Out, 즉 큐로 구현된 가장 간단한 교체 알고리즘이다. 그 Page Fault의 수는 아래와 같이 계산된다.
```
# 내 풀이
1 F
1 2 F
1 2 3 F
2 3 4 F
3 4 1 F
4 1 2 F
1 2 5 F
2 5 1
5 1 2
1 2 3 F
2 3 4 F
3 4 5 F
=> 총 10회의 Page Fault 발생

# 오답 풀이
FIFO는 "가장 오래된" 기준이기에 새롭게 쓰인다고 해서 순서가 뒤로 밀리지 않는다.
따라서
1 F
1 2 F
1 2 3 F
2 3 4 F
3 4 1 F
4 1 2 F
1 2 5 F
1 2 5
1 2 5
2 5 3 F
5 3 4 F
5 3 4
=> 총 9회의 Page Fault 발생
```
b) LRU page fault 수

페이지 교체 알고리즘 중 LRU의 경우 Least-Recently Used, 즉 안 쓰인 가장 오래된 페이지를 교체하는 알고리즘이다. 이상적인 방법.
```
1 F
1 2 F
1 2 3 F
2 3 4 F
3 4 1 F
4 1 2 F
1 2 5 F
2 5 1
5 1 2
1 2 3 F
2 3 4 F
3 4 5 F
=> 총 10회의 Page Fault 발생
```
c) 여기서 Belady’s anomaly가 일어날 수 있는지 설명

Belady’s anomaly란 페이지 교체에 있어 할당된 프레임 수를 늘려도 Page Fault의 수가 증가하는 현상을 말한다. 이는 공간적, 시간적 지역성을 전혀 고려하지 않는 알고리즘 채택 시 주로 발생한다.

지역성을 반영하지 않는 a) FIFO 시 발생할 수 있다.

문제 P2. (Clock)

프레임=4, 각 엔트리는 (R비트, D비트) 초기 (0,0)

참조: A B C D A E A F

Second-Chance(R=1이면 0으로 내리고 패스, R=0이면 교체)로 교체 과정을 간단히 서술

Second-Chance 알고리즘은 구현이 간단한 FIFO 알고리즘을 채택하는 대신, 최근에 쓰인건 봐주자라는 개념을 탑재한 알고리즘이다.

# 기존 풀이
A(R=1) F
A(R=1) B(R=1) F
A(R=1) B(R=1) C(R=1) F
A(R=1) B(R=1) C(R=1) D(R=1) F
B(R=1) C(R=1) D(R=1) A(R=1)
C(R=1) D(R=1) A(R=1) B(R=0)
D(R=1) A(R=1) B(R=0) C(R=0)
A(R=1) B(R=0) C(R=0) D(R=0)
B(R=0) C(R=0) D(R=0) A(R=0)
C(R=0) D(R=0) A(R=0) E(R=1) F
C(R=0) D(R=0) E(R=1) A(R=1)
D(R=0) E(R=1) A(R=1) F(R=1) F

# 오답 풀이
기본 알고리즘을 FIFO가 아니라 LRU 베이스로 풀어버렸다. 다시 풀면 아래와 같다.

A1 F
A1 B1 F
A1 B1 C1 F
A1 B1 C1 D1 F
A1 B1 C1 D1 <- hit
B1 C1 D1 A0
C1 D1 A0 B0 
D1 A0 B0 C0 
A0 B0 C0 D0 
B0 C0 D0 E1 F
C0 D0 E1 A1 F
D0 E1 A1 F1 F
=> 총 7회의 Page Fault 발생

문제 P3. (AMAT in VM)

TLB hit=1ns, TLB miss 시 page-table walk=20ns, 메모리 접근=80ns, TLB hit률=98%, 페이지 폴트 없음(모두 present).

평균 주소변환+메모리 접근 시간을 근사 계산(원히트 1회 접근 가정).

# 기존 풀이
1ns*0.98 + (20ns + 80ns)*0.02 = 1ns

# 오답 풀이
"메모리 접근"이란 얻어낸 실제 물리 주소를 가지고 메모리에 접근해 데이터를 가져오는데 걸리는 시간이다.
다시 말해 TLB hit 이든 PTE hit 이든 상관없이 걸린다는 소리.
(1ns + 80ns)*0.98 + (20ns + 80ns)*0.02 = 81.38 ns

¿curious_jin¿

궁금증이 많은 아이

이전 포스트