[OS] 05. Virtual Memory

Background

실행을 위해서는 코드가 메모리에 있어야 하지만, 프로그램의 일부 부분은 드물게 사용됨
(Error code / Unusual code / Large Data Structure)

전체 코드가 동시에 필요하지는 않음

부분적으로 로드된 프로그램의 실행을 고려

• 프그램은 더 이상 물리 메모리의 제한에 제약을 받지 않음
• 각 프로그램은 실행 중에 더 적은 메모리를 사용 -> 더 많은 프로그램이 동시에 실행 가능
  -> CPU Utilization과 Throughput이 증가
• 메모리로 프로그램을 로드/스왑하기 위해 필요한 I/O가 감소 -> 사용자 프로그램이 더 빠르게 실행

Virtual Memory

• 물리 메모리로부터 사용자 논리 메모리를 분리
• 실행에 필요한 프로그램의 일부 부분만 메모리에 있음
• 논리 주소 공간이 물리 주소 공간보다 훨씬 클 수 있음
• 여러 프로세스가 주소 공간을 공유 가능
• 프로세스 생성(Creation)이 빠름
• 더 많은 프로그램이 동시에 실행
• 프로세스 로드/스왑을 위한 I/O가 감소

Virtual address space

• 프로세스가 메모리에 저장되는 논리적인 관점
• 주소 0부터 시작하여 공간의 끝까지 연속적인 주소가 이어짐
• 물리 메모리는 Page Frame으로 조직되어 있으므로, MMU가 논리 주소를 물리 주소로 매핑해야 함
• 가상 메모리의 구현 방법 : Demand Paging / Demand Segmentation

---

Virtual-address Space

 

일반적인 논리 주소 공간에서 Stack은 최대 논리 주소에서 시작하여 아래로 확장

Heap은 반대로 위로 확장

두 영역 사이의 사용되지 않는 공간을 “Hole”이라고 함

힙 또는 스택이 새로운 페이지로 확장할 때까지 물리 메모리는 필요하지 않음

확장, 동적으로 연결된 라이브러리 등을 위하여 Hole을 남겨두어 희소한(sparse) 주소 공간을 가능하게 함

시스템 라이브러리는 가상 주소 공간으로 매핑되어 공유됨

fork( ) 동안 페이지는 공유될 수 있으며, 프로세스 생성(Creation)을 빠르게 함

 

---

Demand Paging

Load Time에 전체 프로세스를 메모리에 올릴 수 있지만 이는 낮은 메모리 효율성을 보임

 

Demand Paging

• 필요할 때만 페이지를 메모리로 가져옴
• I/O 작업이 줄고, 불필요한 I/O 작업이 없음
• 메모리가 덜 필요
• 빠른 응답(Response)

스와핑(Swapping)을 사용하는 페이징 시스템과 유사

Pager : 페이지를 다루는 Swapper

 

페이지가 필요하면

1. 해당 페이지에 대한 참조 발생
2. 유효하지 않은 참조인 경우, abort (중단)
3. 메모리에 없는 페이지인 경우, 메모리로 해당 페이지를 가져옴

메모리에 있는 페이지의 집합을 결정하는 방법 : 새로운 MMU 기능이 필요
메모리에 이미 필요한 페이지가 있는 경우 : Demand Paging을 사용하지 않는 것과 같음
메모리에 필요한 페이지가 없는 경우 : 해당 페이지를 저장 장치에서 찾고 메모리로 로드함
(프로그램 동작에 영향을 미치지 않고, 프로그래머가 코드를 변경하지 않아야 함)

 

Valid-Invalid Bit in Page Table

• 각 페이지 테이블 엔트리에 valid-invalid bit가 연관 (v : in-memory / i : not-in-memory)
• 초기의 valid-invalid bit는 모두 i로 설정
• MMU 주소 변환 중, 페이지 테이블 엔트리의 valid-invalid bit가 i라면 Page Fault 발생

 

Page Fault

페이지에 대한 참조가 있을 경우, 그 페이지에 대한 첫 번째 참조는 OS로의 Trap을 발생 (Page Fault)

1. OS는 내부 테이블을 확인 후 결정을 내림 (유효하지 않은 참조(abort) vs 메모리에 없는 경우)
2. Free Frame을 찾음
3. 디스크 연산을 통해 프레임으로 페이지를 스왑(Swap)
4. 페이지가 이제 메모리에 있다는 것을 표시하기 위해 테이블 재설정 (validation bit를 v로 설정)
5. Page Fault를 발생시킨 명령을 다시 시작

Pure Demand Paging

• 극단적 경우
• 메모리에 어떤 페이지도 없는 상태에서 프로세스가 시작
• OS는 프로세스의 첫 번째 명령어로 명령 포인터를 설정 / 메모리에 아무것도 없으므로 page fault 발생
• 다른 모든 페이지도 첫 접근에 page fault가 발생

Multiple Page Faults

• 특정 명령어는 여러 페이지에 접근 가능
• 두 개의 서로 다른 메모리에서 숫자를 가져와서 결과를 다시 메모리에 저장하는 명령어를 가져오고 decode하는 경우
• page fault로 인한 오버헤드는 참조의 지역성(Locality of Reference)으로 인해 감소 가능

Demand Paging을 위한 하드웨어 지원

• valid-invalid bit를 가지는 페이지 테이블
• 보조 메모리 (Swap Space를 가지는 Swap Device) - 명령어 재시작

Demand Paging의 단계

1. OS로 Trap 발생
2. 사용자 레지스터와 프로세스 상태 저장
3. 인터럽트가 page fault인지 확인
4. 페이지 참조가 합법인지 체크 후, 디스크에서 페이지의 위치를 확인
5. 디스크에서 Free Frame으로 읽기 작업 수행
    - 읽기 요청이 서비스될 때까지 이 장치를 위해 큐에서 대기
    - 장치의 Latency time 동안 대기
    - Free Frame으로의 페이지 전송 시작
6. 대기 중에 CPU는 다른 사용자에게 할당
7. 디스크 I/O 서브 시스템으로부터 인터럽트를 수신 (I/O 완료)
8. 다른 사용자를 위한 레지스터와 프로세스 상태 저장
9. 인터럽트가 디스크에서 발생했는지 확인
10. 페이지 테이블과 다른 테이블을 수정하고 페이지가 이제 메모리에 있음을 나타냄
11. CPU가 다시 이 프로세스에 할당되기를 기다림
12. 사용자 레지스터, 프로세스 상태, 새 페이지 테이블을 복원하고 중단된 명령어를 다시 실행

Demand Paging의 3가지 주요 활동

• 인터럽트 서비스 : 수백 개의 명령어가 필요
• 페이지 읽기 : 많은 시간 소요
• 프로세스 재시작 : 적은 시간 소요

Page Fault Rate가 0 ≤ p ≤ 1 이면 / p = 0이면 page fault가 없음 / p = 1이면 모든 참조가 fault

Effective Access Time (EAT) = (1 – p) x memory access + p x (page fault overhead + swap page out + swap page in)

 

EAT 예제

• Memory access time = 200 nanosec
• Average page-fault service time = 8 millisec
• EAT = (1 – p) x 200 + p x 8,000,000 = 200 + p x 7,999,800
• 만약 1000번 엑세스 중 1번이 page fault를 일으킨다면 / EAT = 8.2 microsec (성능 저하율 40배)
• 성능 저하를 10% 미만으로 줄이려면 / 200 + p x 7,999,800 < 220
• 즉, p < 0.0000025 / 400,000번 중 1번 미만의 page fault를 유발해야 함

Demand Paging 최적화 (Optimization)

• Swap space I/O는 일반적으로 같은 장치에 있더라도 파일 시스템 I/O보다 빠름
   - Swap은 더 큰 Chunk로 할당되며 파일 시스템보다 적은 관리를 요구
• Process Load time에 전체 프로세스 이미지를 Swap space로 복사하는 것
   -> Swap space로 페이지를 읽고 쓰는 작업은 Load time에 큰 오버헤드 유발 -> 오래된 BSD Unix에서 쓰임
• 해결 : Page in은 디스크로부터 하고 Page out을 Swap space로 시킴
   - 현재의 BSD와 Solaris에서 사용
   - 바이너리 파일(read only)은 Swap space로 Page out 시키지 않고 덮어쓸 수 있음
   - Write는 여전히 Swap space에 해야 함 
   (파일과 연관 없는 페이지 & 메모리에서 수정되었지만 파일 시스템에 써지지 않은 페이지)
• Anonymous memory : 파일과 연관 없는 페이지(Stack과 Heap 등)
• Mapped memory : 파일과 연결된 메모리
• 모바일 시스템은 일반적으로 Swapping을 지원X
• 대신 파일 시스템에 Demand Paging하고 Read-only page(Code 등)를 Dump out 시킴

---

Copy-on-Write

 

Copy-on-Write(COW)는 부모와 자식 프로세스가 초기에 메모리의 동일한 페이지를 공유할 수 있게 해줌
둘 중 하나의 프로세스가 공유된 페이지를 수정할 때, 다른 페이지는 복사됨
COW는 수정된 페이지만 복사하므로 더 효율적인 프로세스 생성이 가능
일반적으로 Free Page는 Zero-fill-on-demand 페이지의 Pool에 할당
Pool은 빠른 Demand page 실행을 위해 항상 Free Frame을 가져야 함
Page Fault 시에 Frame을 해제하고 다른 프로세스를 수행하는 일이 없도록 함
vfork( )는 fork( )의 변형 / 부모는 일시 중단, 자식은 부모의 복사본을 사용
자식이 exec( )를 호출할 것으로 예상하고 디자인 / 매우 효율적

---

Page Replacement

Free Frame이 없다면?

• 프로세스 페이지에 사용 / 커널과 I/O 버퍼에서도 요구
• Page Replacement : 메모리에 있는 페이지가 실제 사용 중이 아니라면 Page out을 함
• Page fault의 수가 최소가 되는 알고리즘이 필요 (terminate? swap out? replace?)
• 동일한 페이지가 여러 번 메모리로 가져와질 수 있음
• 메모리의 Over-allocation을 방지하기 위해 Page fault 서비스 루틴에 Page replacement를 포함시킬 수 있음
• 페이지 전송의 오버헤드를 줄이기 위해 Modify (Dirty) bit를 사용
• Page replacement는 논리 메모리와 물리 메모리 사이의 분리를 완료
• 더 큰 가상 메모리를 더 작은 물리 메모리에서 제공할 수 있게 함

기본적인 Page Replacement 알고리즘

1. 디스크 상에서 원하는 페이지의 위치를 찾음
2. Free Frame을 찾음
    - 만약 Free Frame이 있다면 그것을 사용
    - 없다면 Victim Frame을 선정하기 위해 Page replacement 알고리즘을 사용
    - Victim Frame이 dirty면 디스크에 기록
3. 원하는 페이지를 Free Frame으로 가져오고 페이지와 프레임 테이블을 업데이트
4. Trap을 발생시킨 명령어를 다시 실행하고 프로세스를 계속함
    - Page fault로 인해 2번의 페이지 전송이 발생할 수 있음 (Dirty인 경우) –> EAT가 증가함

Page and Frame Replacement Algorithms

• Frame-allocation algorithm
   - 각 프로세스에 얼마나 많은 프레임을 할당할지 결정
   - 어떤 프레임을 교체(replace)할 것인지 결정 
• Page-replacement algorithm
   - 첫 번째 접근과 재접근 모두 가장 낮은 page fault 확률을 원함
• 알고리즘을 평가하기 위해, 메모리 참조의 특정 문자열에서 실행 후, 그 문자열에서 page fault 수를 계산
   - 문자열은 오직 페이지 넘버이며 전체 주소가 아님
   - 같은 페이지에 반복된 접근을 하면 page fault가 발생하지 않음
   - 결과는 사용 가능한 프레임의 수에 따라 결정됨

---

Page Replacement Algorithms

Reference String의 예시 : 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

 

First-In-First-Out (FIFO) Algorithm

• 3개의 프레임 존재
• 즉, 3개의 페이지가 메모리에 동시 존재 가능
• 성능은 Reference String에 따라 달라질 수 있음
• 프레임을 추가하면 오히려 더 많은 page fault가 발생할 수 있음 (Belady’s Anomaly)
• 페이지의 age를 추적하는 방법 : FIFO 큐를 이용

Belady’s Anomaly (이상 현상) : 프레임 개수는 증가했지만 오히려 Page Fault가 더 증가하는 현상

 

Optimal (Belady’s) Algorithm

• 가장 오랜 시간 동안 사용되지 않을 페이지를 교체
• 미래를 알 수 없으므로 예측만 할 수 있음 / 단지 알고리즘의 성능을 측정하는 데 사용

Least Recently Used (LRU) Algorithm

• 과거 지식을 활용하여 미래를 예측
• 가장 오랜 시간 동안 사용되지 않은 페이지를 교체
• 각 페이지의 마지막 사용 시간을 관련지어 예측

LRU Algorithm 구현

• Counter 구현
   - 모든 페이지 엔트리는 카운터를 가짐 / 페이지가 참조될 때마다 해당하는 카운터는 증가
   - 페이지가 교체되어야할 때, 카운터를 확인 후 가장 작은 값을 찾음 / 테이블 검색이 필요
• Stack 구현
   - 페이지 넘버의 스택을 이중 링크 형태로 유지
   - 페이지가 참조될 때마다 해당 페이지를 스택의 Top으로 이동
   - 각 업데이트마다 비용이 많이 듦 / 교체를 위한 검색이 필요하지 않음

LRU Approximation Algorithm

LRU는 특수 하드웨어가 필요하며 느림 (LRU가 좋은 이유 : Reference Locality)

 

Reference Bit

• 각 페이지와 관련된 비트 / 초기값 = 0
• 페이지가 참조될 때, Reference Bit는 1로 세팅
• Reference Bit가 0인 페이지가 존재한다면 그것과 교체
• 그러나 페이지의 순서를 알 수는 없음

Second-chance Algorithm

• 일반적으로 FIFO와 함께 하드웨어에서 제공하는 Reference Bit를 사용
• = Clock Replacement
• 만약 교체할 페이지의 Reference Bit가 0이면 교체
• 1이면 Reference Bit를 0으로 세팅하고 페이지를 메모리에 남겨둠
• 같은 규칙으로 다음 페이지를 교체

Enhanced Second-chance Algorithm

• Reference Bit와 Modify Bit를 사용하여 알고리즘을 개선
   - 순서쌍을 이용 (Reference, Modify) 
•  - (0, 0) : 최근에 사용되지 않고 수정되지 않음 / 교체하기 가장 좋은 페이지
   - (0, 1) : 최근에 사용되지 않고 수정은 됨 / 교체하기 전에 Write out 해야 함
   - (1, 0) : 최근에 사용되었고 Clean / 아마 곧 다시 사용될 것
   - (1, 1) : 최근에 사용되고 수정됨 / 아마 곧 다시 사용될 것, 교체 전에 Write할 필요가 있음
• Page replacement가 필요한 경우, Clock Scheme를 사용하고 4가지의 클래스를 이용
   - 원형 큐를 여러 번 검색할 필요가 있을 수 있음

Counting Algorithm

참조할 때마다 계수를 하여 그 값으로 판단하는 알고리즘

• LFU(Least Frequently Used) 알고리즘
   - 참조 횟수가 가장 작은 페이지를 교체하는 방법
   - 일시적인 시점에 집중적으로 사용되고 나중에 사용되지 않다라도 메모리에 남게되어 판단이 빗나갈 수 있음
   - 구현 방법 : 참조 횟수를 일정 시간마다 오른쪽으로 Shift하여 영향력을 감소시킴
• MFU(Most Frequently Used) 알고리즘
   - 가장 작은 참조 횟수를 가진 페이지가 앞에 사용될 것이라는 판단
   - 입출력 횟수를 줄임으로써 성능을 향상시킬 수 있음
   - 구현에 드는 비용이 높으나 성능이 최적 알고리즘에 근사하지 못해 잘 사용되지 않음

Page-Buffering (페이지 버퍼링) 알고리즘

• 페이지 교체 알고리즘과 병행하여 여러 가지 버퍼링을 사용
• 가용 프레임 여러 개를 Pool로 유지
   - Page Fault 시에 교체될 프레임을 찾지만 그 내용을 디스크에 기록하기 전에 가용 프레임에
     새로운 페이지를 읽어 들이는 방식으로 프로세스가 빠르게 시작함
   - 나중에 디스크에 기록하고 가용 프레임 Pool에 추가
• 위 개념의 확장으로 변경된 페이지 리스트를 유지하는 방법
   - 디스크가 쉴 때마다 변경된 페이지를 차례로 디스크에 쓴 후, 변경 비트를 0으로 설정
   - 추후 교체 시에 쓰기 작업을 하지 않아도 된다는 장점
• 가용 프레임을 유지하지만, 원래 주인 프로세스가 누구였는지 기록하는 방법
   - 가용 Pool 속 프레임 내용을 디스크에 썼다고 하더라도 프레임이 사용되기 전까지는 다시 사용 가능
   - Page Fault 시에 가용 프레임 Pool에서 찾아봄

---

Allocation

Allocation of Frames
컴퓨터 시스템의 성능 향상을 위해서는 동시에 동작하는 여러 프로세스에게 제한된 가용 메모리 공간을 효과적으로 할당할 수 있는 방법을 고려해야 함
각 프로세스에게 할당되는 메모리 프레임 수를 정해야 함

• 프레임 수의 최솟값
   - 프로세스에 할당되는 프레임 수가 줄면, Page Fault 발생 확률이 늘어남 -> 성능 저하
   - 명령어 실행이 끝나기 전에 Page Fault가 발생하면, 그 명령어는 재실행해야 함
   - 프로세서의 명령어 집합 구조(Instruction Set Architecture)에 의해 결정
• 프레임 수의 최댓값
   - 물리 메모리에 의해 결정
   - 예시 : 두 숫자를 더하는 연산 -> 최소 3개에서 최대 6개의 페이지가 존재해야 함

Allocation Algorithm

• Equal allocation : 100개의 프레임과 5개의 프로세스가 있으면 20개씩 할당
  Free Frame은 Buffer Pool에 유지됨
• Proportional allocation : 프로세스의 크기에 따라 프레임을 할당
  다중 프로그래밍의 정도에 따라 동적으로 조정
• Priority allocation : 크기 대신 우선순위를 사용하여 Proportional allocation 방식을 적용
  Size와 필요한 프레임의 수가 비례하지 않을 수 있기 때문에 사용하는 방식

Global Allocation -> Global replacement 발생

• 프로세스는 모든 프레임의 집합에서 교체할 프레임을 선택
• 한 프로세스가 다른 프로세스의 프레임을 가져갈 수 있음 (보통은 그룹을 지어서 그 안에서 선택)
• 프로세스 실행 시간이 크게 다를 수 있음
• 할당된 프레임의 수가 동적으로 변경됨

Local Allocation -> Local replacement 발생

• 각 프로세스는 자신에게 할당된 프레임의 집합에서만 희생 프레임을 선택
• 프로세스의 각 성능은 더 일관적임 (모든 프로세스에게 유사한 실행 시간 부여 가능)
• 메모리의 낮은 효율성을 초래할 수 있음

Non-Uniform Memory Access (NUMA)

• Uniform Memory Access : 모든 메모리 요청이 동일하게 접근되는 시스템
• NUMA : 메모리에 대한 접근 속도가 다양한 시스템
   - 최적의 성능은 프로세스가 스케줄된 CPU에 가까운 메모리에 할당하는 것으로부터 옴
• Solaris는 lgroups를 생성함으로써 문제를 해결
   - lgroups : CPU와 메모리 낮은 지연 그룹(latency groups)을 추적하는 구조
   - 가능하다면, 모든 프로세스를 lgroup 내의 메모리 프레임에 스케줄하고 할당

---

Thrashing

Thrashing : Page in, out의 Swapping으로 프로세스가 바쁜 상태인 상황
만약 프로세스가 충분한 페이지를 가지고 있지 않으면 Page Fault Rate는 높음
Page Fault는 페이지를 가져오고 기존 프레임을 교체하지만 교체된 프레임은 빠르게 필요하게 됨
 -> 낮은 CPU 활용률을 초래
 -> OS는 다중 프로그래밍의 정도를 높여야 한다고 판단하여 시스템에 다른 프로세스가 추가됨

Demand Paging이 작동하는 이유? -> Locality model - 프로세스가 하나의 Locality(지역성)에서 다른 Locality로 이동함

Thrashing의 발생 이유? -> Locality 크기의 총합이 총 메모리의 크기보다 커질 때

Local replacement 또는 Priority page replacement를 이용하여 효과를 제한할 수 있음

---

Working Set Model

∆ = Working Set window = 페이지 참조의 고정된 수

WSSi (working set of Process Pi) = 최근 ∆동안 참조한 페이지 수의 총합

∆가 너무 작으면 전체 Locality를 포함하지 못함

∆가 너무 크면 여러 Locality를 포함할 수 있음

∆가 무한대이면, 전체 프로그램을 포함

D = ∑ WSSi = Demand 프레임의 총합 / Locality의 근사치

D > m(total memory size) 이면 Thrashing 발생 -> 이런 경우, 한 프로세스를 정지하거나 Swap out함

 

예시 : ∆ = 10,000

• 타이머는 매 5,000 단위 시간마다 인터럽트를 발생
• 각 페이지에 대해 2비트를 메모리에 유지
• 타이머가 인터럽트를 발생시킬 때마다, 모든 참조 비트의 값을 복사하고 0으로 설정
• 메모리에 있는 비트 중 하나가 1이면, Working set에 있는 page임

정확성 향상을 위해서 참조 비트의 수를 늘리고 타이머 사이클을 줄임
위의 예제에서 10개의 비트를 사용하고 1,000 단위 시간을 사용 -> 단점 : 인터럽트 오버헤드 증가

---

Page-Fault Frequency

WSS보다 더 직접적인 방식
허용 가능한 Page-Fault Frequency(PFF) 비율을 설정하고 Local replacement 정책을 사용

• PFF가 너무 낮으면 프로세스가 프레임을 잃음
• PFF가 너무 높으면 프로세스가 프레임을 얻음

Working Set과 Page Fault 비율에는 직접적인 관계가 있음
Working Set은 시간이 지나면서 변화하고 Peak와 Valley가 생김

---

Allocation Kernel Memory

사용자 모드에서 수행 중인 프로세스가 추가적인 메모리를 요구하면 커널이 관리하는 페이지 프레임 중에서 할당
커널 메모리는 보통 사용자 모드 프로세스와 달리 별도의 메모리 Pool에서 할당하는 정책을 사용
커널은 다양한 크기의 자료 구조를 위해 메모리를 할당받음
단편화에 의한 낭비를 줄여야 하지만 커널 코드나 데이터는 페이징하지 않음
사용자 모드 프로세스의 페이지는 연속적일 필요는 없으나, 물리 메모리에 직접 접근하는 장치는
물리적으로 연속적인 메모리를 필요로 하는 경우가 있음

 

Buddy System

물리적으로 연속된 페이지로 이루어진 고정 크기 세그먼트에 메모리를 할당
2의 제곱인 Allocator를 사용하여 메모리를 할당

• 2의 제곱 승 크기 유닛으로 요구를 만족
• 다음 크기의 2의 제곱만큼 반올림
• 사용 가능한 메모리보다 작은 할당이 필요한 경우, 현재 Chunk를 낮은 2의 제곱 크기의 2개 버디로 분할
• 이 방식을 적절한 크기의 Chunk가 가능할 때까지 반복
• 256KB의 Chunk가 가능하고 커널이 21KB를 요청한 경우 / 128KB, 64KB, 32KB로 순서대로 분할
• 장점 : 사용하지 않는 Chunk를 큰 크기의 Chunk로 빠르게 합칠 수 있음(coalesce)
• 단점 : 단편화 발생 (Internal 단편화가 생기지만 연속적인 공간을 모을 수 있기 때문에 사용)

Slab Allocator

슬랩(Slab) : 하나 또는 그 이상의 연속된 페이지들로 구성
캐쉬(Cache) : 하나 혹은 그 이상의 슬랩으로 구성
각 커널 구조마다 캐시가 존재
프로세스 기술자, 파일 객체, 세마포어 등을 위한 캐시가 존재
각 캐시는 커널 자료 구조의 instantiation에 해당하는 객체들로 채워져 있음
Slab Allocator는 커널 객체를 저장하는 캐시를 사용
캐시가 생성되면 초기에는 Free라고 표시된 몇 개의 객체들이 캐시에 할당
커널 자료 구조를 위한 객체가 필요하면 Free 객체들 중 하나를 캐시로부터 할당하고 Used라고 표시
Linux의 슬랩 상태 : Full / Empty / Partial

Slab Allocator는 단편화에 의한 메모리 낭비가 없고, 메모리 요청이 빠르게 수행됨