1. Segmentation의 문제점

1. 메모리 단편화

• 유휴 메모리 공간(free memory)가 작게 조각나서 사용되지 못하는 문제

2. 메모리 단편화의 종류

• 외부 단편화(external fragmentation)
  -> 할당되지 않은 메모리(free memory)가 조각난 상황
• 내부 단편화(internel fragmentation)
  -> 할당된 메모리 내에 사용되지 않는 공간 존재

2. 페이징(paging)

1. 프로세스의 가상메모리를 불연속적인 페이지로 구성

• 가상 메모리를 동일한 크기의 블록(page)로 나눔
• 물리 메모리를 동일한 크기의 블록(frame)으로 나눔
• 페이지(또는 프레임)의 크기는 2의 승수(일반적으로 4kB~16KB)

2. 메모리 관리의 용이성

• OS는 free 프레임들을 관리하기 쉬워짐
  -> linked list 이용
• 프로세스 실행시 n개의 페이지를 요청하면 n개의 유휴프레임을 해당 프로세스에 할당하여 제공
  -> 외부 단편화 문제 해소
• 페이지 테이블을 구성하여 n개의 가상 페이지에 n개의 물리 프레임을 연결

3. 주소 변환

1. Dynamic Relocation

가상 주소에서 물리 주소로 변환하는 방법(32bit 일때)

1. 페이지 번호

• 가상주소의 상위비트(20bit in 32bit 4KB page)는 가상메모리상 페이지 번호 뜻함
• 페이지 번호는 page table을 통해 물리 메모리의 프레임 번호로 변환

2. 페이지 내 주소

• 가상주소의 하위 비트(12bit in 4KB page)는 페이지 내의 주소를 뜻함
• 가상메모리 페이지 번호를 물리 페이지 번호로 변환

3. 결과

• 물리 메모리의 프레임 번호로 변환된 가상 메모리의 페이지 번호 + 페이지 내 주소
• 이것을 통해 물리 메모리를 찾아감

4. 보호(protection)

1. 다른 프로세스 또는 OS의 메모리 접근 및 수정 불가능

페이지 테이블의 내용은 OS만 채워 넣을 수 있음

• 페이지 테이블은 커널메모리에 저장됨
• 다른 프로세스 또는 OS의 메모리에 접근 불가

컨텍스트 스위칭 시에 MMU에 페이지 테이블의의 위치 정보 제공

2. 페이지 단위의 보호

페이지 테이블 엔트리(PTE)에 protection 정보 저장

Valid/Invalid bit

• Set 된 경우, 해당 가상페이지가 유효한 물리프레임에 연결됨
• Clear된 경우, 해당 가상페이지에 연결된 물리프레임이 없음
  -> 즉 이것으로 접근 불가능한 주소영역으로 만들어 줌

페이지 단위로 접근 권한 설정 가능

• 읽기 전용, 읽기 쓰기, 실행 가능

3. 페이지 테이블 엔트리(PTE)

1. V(valid)

해당 가상 페이지의 유효 여부를 저장

• 가상 주소가 접근될 때마다 valid bit를 테스트

2. R(reference)

해당 가상 페이지가 최근에 접근 되었는지 여부

• 가상 주소가 접근될 때, 해당 reference bit가 set됨

3. M(modify)

해당 가상페이지에 쓰기가 발생했는지 여부

• 가상 주소에 쓰기(write 또는 store 명령어)가 발생하면 set됨

4. Prot(protection)

해당 가상페이지의 접근 권한

• 읽기, 쓰기, 실행 권한 등

5. PFN(Page Frame Number)

해당 가상 페이지에 연결된 물리 프레임 번호

5. 요구 페이징(demand paging, memory hierarchy)

1. OS는 메인메모리(물리메모리)를 디스크의 캐시로 사용

• 데이터가 접근되는 경우 메인메모리에 탑재
• 사용되지 않는 물리 프레임은 제거
• 퇴거된 페이지는 디스크에 write back
• 페이지의 디스크-메모리 사이 이동은 프로세스가 모름
  -> 프로세스는 가상메모리만 알고 있기 때문

2. 장점

• 디스크 I/O 횟수 감소
• 필요한 메모리만 사용하여 메모리 절약
• 빠른 응답속도
• 더 많은 프로세스 동작 가능

3. 페이지 폴트

페이지 폴트 처리 모습

• 현대 CPU들이 요구 페이징을 구현하는데 활용하는 예외상황(exception)
• Invalid bit 가 set(또는 valid bit 가 clear)된 PTE의 가상페이지를 접근하는 경우 발생

3가지 페이지 폴트 종류

1. 메이저 페이지 폴트

• 가상 페이지는 유효하나, 해당 가상페이지가 메모리에 적재(loading)되지 않은 경우
• OS의 Page Fault handelr는 해당 가상 페이지의 디스크 위치를 찾아 메모리에 적재 수행
• 디스크 I/O가 필요한 폴트에 해당

2. 마이너 페이지 폴트

• 가상 페이지는 유효하나 PTE의 invalid bit가 set 된 경우
• 지연 할당에 사용(stack, heap등의 영역에서 접근되는 가상 페이지만 물리프레임을 할당)
• 디스크 I/O가 필요없는 폴트에 해당

3. Invalid page fault

• 통상 segmentation fault로 지칭되는 유효하지 않은 가상페이지에 접근한 경우
• ex) 유저 프로세스가 커널 메모리에 접근, heap의 범위를 벗어나는 주소 접근

3. 페이징의 활용

1. 공유 메모리

1. 구현 방법

– 각 프로세스 의 PTE에 동일한 물리 프레임 저장
– 각 PTE는 동일한 또는 다른 접근권한 설정 가능
– 공유 페이지가 퇴거(evict)되는 경우 연관된 PTE의 valid bit가 clear되어야 함

2. 공유 메모리 가상메모리에 할당시 고려사항

1. 서로 같은 주소에 연결하는 경우

• 공유 메모리 내에 공유하는 포인터 사용가능
• 하지만 동일하게 비어있는 가상 주소 찾는 어려움

2. 서로 다른 주소에 연결하는 경우

• 공유 포인터 사용 불가능
• 하지만 동일하게 비어있는 가상주소 찾을 필요 없음

2. Memory-Mapped Files

1. 메모리 접근으로 디스크 파일 접근 가능

• 파일 API(read(), write()) 사용할 필요 없음
• mmap(): 파일을 가상메모리에 연결하는 기능

2. 구현 방법

• mmap()이 된 경우 해당 가상메모리 영역에 invalid flag 설정
• mmap()된 가상주소에 접근 시 페이지 폴트 발생

  • OS는 해당 주소가 파일에 매핑된 영역임을 확인

• 디스크에서 해당 가상페이지에 대응되는 데이터를 물리 프레임에 적재
• 물리 프레임을 해당 가상 페이지에 연결
• 물리 프레임이 퇴거 대상이 될 경우 dirty 페이지인 경우 파일 쓰기 수행

3. 장점

• 파일 데이터, 메모리 데이터(지역/전역 변수) 구분 없이 데이터 접근
• 메모리 복사를 더 적게 할 수 있음
  -> 파일 API는 OS 버퍼에서 유저 메모리 버퍼로 복사 수행
• 여러개의 프로세스가 같은 파일을 공유해서 접근 가능
  -> 공유 라이브러리, 공유 파일들

4. 단점

• 데이터의 이동에 프로세스 개입이 어려움
• 스트리밍 입출력에 적합하지 않음
  -> ex) pipes, sockets, ...

3. Copy on Write

1. 메모리 복사를 지연하는 기법

• 쓰기 발생시 복사 수행

2. 구현

• 프로세스 각자 독립된 copy를 가져야 하는 상황이지만 만약 같은 내용을 볼 수 있는 상황이면, 물리 프레임을 PTE를 통해 공유
• 대신 각 프로세스는 PTE에 쓰기 권한을 해제
• 쓰기 발생 시 페이지 폴트 핸들러에서 새로운 물리프레임 할당 및 복사 수행

3. 용도

• fork() 시 부모/자식간 물리 프레임 공유
• 0으로 초기화된 새로운 페이지 할당시
  -> ex) heap, stack, mmap(ANON)

4. Copy on write during fork()

• fork() 의 문맥은 부모와 동일한 가상메모리를 자식에게 새로 할당하는 것
  -> 각자의 가상 메모리를 갖지만 내용은 동일
• 물리 페이지를 새로 할당하고 복제하는 대신 자식 프로세스의 가상메모리에 부모 프로세스의 물리 페이지를 연결
• 공유되는 페이지의 PTE 쓰기 권한 해제
• 읽기는 공유프레임에 그대로 동작
• 쓰기 발생 시 페이지 폴트 발생
  -> OS 핸들러에서 새 프레임 할당 및 데이터 copy

4. 페이징의 장점과 단점

1. 장점

1. 외부 단편화 문제 없음

2. 빠른 할당/해제 성능

• 유휴 프레임 관리에 용이(linked list 또는 bitmap)
  -프레임 할당/해제에 연속된 메모리 관리 필요 없음

3. 페이지 단위의 유연한 메모리 관리

• 필요한 페이지만 메모리에 적재하고 사용
  -> PTE 의 valid bit 활용
• 페이지 단위의 접근 권한/보호 적용 가능
• 작은 단위(page)의 메모리 공유 가능

2. 단점

1. 내부 단편화

• 페이지 크기가 큰 경우 페이지 내에 유휴 공간 존재 증가

2. 메모리 참조(reference) 성능 하락

• 모든 메모리 접근이 2번(또는 그 이상)의 메모리 접근 유발

3. 페이지 테이블 크기 부담

• 페이지 테이블은 연속 (선형적)이어야 함

5. TLB

1. 페이징의 주소 변환 과정

1. 가상 주소에서 가상 페이지 번호(VPN: Virtual Page Number) 추출
2. 페이지 테이블에서 PTE 주소 결정
3. PTE에서 메모리 읽기
4. PTE에서 물리 프레임 번호(PFN: Physical Frame Number) 추출
5. 드디어 물리 메모리 주소 완성해서 물리 메모리 접근

기존 페이징의 주소 변환과정은 느리다!

• 메모리 접근 1번을 위해 실제로는 2번 접근 해야 함
• 다중 페이지 테이블 구조에서는 메모리 접근 횟수 증폭이 3~10배 증가
  -> 가상 머신 기술의 가상화(memory virtualization)이 적용된 경우

2. 따라서 TLB 등장

TLB의 주소 변환 과정

1. Translation Lookside Buffer

• 빈번하게 사용되는 주소 변환 정보를 저장하는 일종의 캐시
• CPU에서 가상 메모리 제공시 성능에 핵심적인 요소

2. TLB는 지역성을 활용

1. 시간 지역성(Temporal locality)

• 최근에 접근된 명령어나 데이터는 다시 접근될 확률이 높음
• ex> loop 에서 접근하는 데이터 및 명령어

2. 공간 지역성(Spatial locality)

• 접근된 메모리 주소에 인접한 데이터가 접근될 가능성이 높음
• ex) 배열 요소 접근, 스택, ...

6. Multi-level 페이지 테이블

1. 선형 페이지 테이블의 메모리 낭비 문제

• A 32-bit 주소공간 with 4KB 페이지 (4 bytes/PTE):
  220 * 4 = 4MB (프로세스당)
• A 64-bit 주소공간 with 8KB 페이지 (8 bytes/PTE):
  251 * 8 = 254 = 32PB (프로세스당)

2. 해결 방안

• 특징: PTE중 불필요한 것이 많음
• 가상메모리 주소공간 중에서 필요한(접근되는 또는 유효한) 가상 페이지에 대해서만 PTE를 유지

3. 따라서 Multi-level 페이지 테이블

• 페이지 테이블이 비선형적(불연속적)으로 할당 가능
• 가상 주소를 3개로 구분
  

  • Outer page table: outer page # -> secondary page table 연결

• Secondary page table: secondary page # -> page frame #
  

7. 페이지 교체

1. 임계치(threshold) 기반 교체 수행

• OS 는 유휴 메모리량을(free memory) 관리
• 유휴 메모리량이 임계치보다 작아지면
  -> 페이지 프레임 회수를 통해 불필요한 페이지 선별 및 퇴거 수행
• 유휴 메모리량이 임계치보다 커지면
  -> 프레임 회수 중단
• 백그라운드에서 동작하는 교체 데몬(kswap in Linux)를 통해 페이지 교체 수행

2. 페이지 교체 정책

1. 어떠한 페이지(프레임)을 퇴거 대상으로 선정할지 결정

• 퇴거 대상이 선정된 경우
  -> Dirty 페이지인 경우 페이지를 디스크에 쓰기 선행
  -> Clean 페이지의 경우 페이지를 바로 버림

2. 페이지 교체 정책의 목표: 페이지 폴트 수 최소화

• 이유: 메모리의 miss penalty는 매우 크기 때문
• 페이지 폴트 수가 많아지면 성능에 큰 영향을 줌

3. LRU

1. Least Recently Used

• 가장 먼 과거에 접근했던 페이지를 교체 대상으로 선정
• 미래를 예측하기 어려우나, 과거가 미래를 대변할 것이라고 추축
• 미래를 예측할 수 있는 경우, Optimal 알고리즘을 사용함
• 스택 알고리즘을 통해 구현

하지만 가상 메모리에 적용하기 어렵다는 단점 존재

• 페이지가 접근된 시점을 관리하기 어렵기 때문
• 메모리 명령어 접근마다 페이지의 접근 시점을 관리하는 오버헤드가 크다

2. 스택 알고리즘

• 페이지 프레임이 접근될 때마다 그것을 stack top에 push
• Stack 의 bottom 에서 메모리 크기를 넘어가는 것이 퇴거 대상

4. Clock

1. LRU 근사 알고리즘

• PTE(Page Table Entry)의 R비트를 활용
• 페이지(프레임)을 원형으로 구성
• 최근 접근된 페이지는 R비트가 set되어 있기 때문에 퇴거 대상이 안됨