[운영체제] 10. Virtual Memory

Virtual Memory Concepts

Restricted physical memory size

• 물리적 메모리 크기의 제한
  • 물리적 메모리 공간보다 큰 프로그램은 실행될 수 없음.

General program execution pattern

• 일반적인 프로그램 실행 패턴
  • 프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않음.
    • 오류 코드 및 예외 코드
    • 100x100 배열 중 10x10 요소만 사용됨.
    • 프로그램의 특정 옵션 및 기능이 드물게 사용됨.
  • 전체 프로그램이 필요할 때조차도 모든 부분이 동시에 필요하지 않을 수 있음.

Virtual memory

• 가상 메모리
  • 메모리에 완전히 들어가지 않은 프로세스의 실행을 허용.
  • 프로그램의 일부만 메모리에 있어도 실행 가능.
  • 논리적 메모리 주소 공간과 물리적 메모리 주소 공간의 분리.
  • 논리적 메모리 주소 공간이 물리적 메모리 주소 공간보다 클 수 있음.

Virtual Address Space

• 가상 주소 공간
  • (프로그램의 코드, 데이터, 힙, 스택이 각각의 세그먼트로 나뉘어 가상 메모리 공간에 배치됨.)
  • (힙과 스택은 서로 반대 방향으로 성장함.)

 

Demand Paging

Virtual memory can be implemented via demand paging.

• 가상 메모리는 요청 페이징(demand paging)을 통해 구현될 수 있음.
  • 페이지가 필요할 때만 메모리에 가져옴.
    • I/O가 적게 필요함.
    • 메모리가 적게 필요함.
  • 페이지가 교체(swapped in and out)될 수 있어야 함.

When a page is referenced,

• 페이지가 참조될 때,
  • 유효한 참조면 참조.
  • 유효하지 않은 참조면 메모리에 가져옴.

 

• 유효-무효 비트(valid-invalid bit)가 각 페이지 테이블 항목과 연관됨. 
  • v(valid) = 메모리에 있음.
  • i = 메모리에 없거나 합법적이지 않음.(bad address, protection violation)
  • 주소 변환 중, 유효-무효 비트가 i면 페이지 폴트(page fault).

---

Page table when some pages are not in main memory.

• 일부 페이지가 메인 메모리에 없는 경우의 페이지 테이블.
  • (논리적 메모리에서 페이지가 물리적 메모리와 매핑됨. 유효-무효 비트를 통해 페이지의 존재 여부를 확인.) 

Access to invalid page causes page fault.

• 유효하지 않은 페이지 접근은 페이지 폴트를 일으킴.
  • 운영 체제 내의 페이지 폴트 핸들러가 호출됨.

Page fault handler deals with the page fault as follows.

• 페이지 폴트 핸들러가 다음과 같이 페이지 폴트를 처리함.
  1. 유효하지 않은(invalid) 참조인가?
  • 만약 주소 오류나 보호 위반이면 프로세스 중단.
  • 만약 메모리에 없으면 계속 진행.
  1. 빈 페이지 프레임 가져오기.
  • 빈 페이지 프레임이 없으면 일부 페이지 프레임 교체.
  1. 페이지를 페이지 프레임에 읽어오기.
  • 디스크 I/O가 완료될 때까지 프로세스가 차단됨.
  • 디스크 I/O 완료 시 페이지 테이블 항목을 유효(valid)로 설정.
  • 프로세스를 준비 큐(ready quie)에 다시 삽입하고 나중에 dispatch.
  1. 페이지 폴트를 유발한 명령어 재시작.

---

Demand Paging

Page fault handling

• 페이지 폴트 처리
  • (페이지 폴트 핸들러가 운영 체제에서 참조를 처리함.)
  • (페이지가 디스크에서 메모리로 가져와짐.)
  • (페이지 테이블이 리셋되고 명령어가 재시작됨.)

---

Page Fault Rate 0 ≤ p ≤ 1.0

• 페이지 폴트 비율 0 ≤ p ≤ 1.0
  • p = 0이면 페이지 폴트 없음.
  • p = 1이면 모든 참조가 폴트.

Effective Access Time (EAT)

• 유효 접근 시간 (EAT)
  • EAT = (1 - p) * 메모리 접근 시간 + p * 페이지 폴트 서비스 시간
  • 예:
    • 메모리 접근 시간 = 200 ns
    • 평균 페이지 폴트 서비스 시간 = 8 ms (8,000,000ns)
    • EAT = (1 - p) * 200 + p * 8,000,000
    • 1,000번 접근 중 1번이 페이지 폴트를 일으키면
      • EAT = 8,200 ns
      • 40배 느려짐.

It is important to keep the page fault rate low.

• 페이지 폴트 비율을 낮게 유지하는 것이 중요함.
  • 좋은 페이지 교체 정책(good page replacement policy) 필요.

---

Page Replacement

Page replacement

• 페이지 교체
  • 실제로 사용되지 않는 페이지를 찾아 교체.
  • 좋은 페이지 교체 알고리즘은 최소한의 페이지 폴트를 발생시킴.

Locality of reference

• 참조의 지역성
  • 동일한 페이지가 여러 번 메모리에 불러들여질 수 있음.
  • 실제 대부분의 프로그램에서 관찰되는 현상.
  • 일정 시간에 일부 페이지만 집중적으로 참조하는 프로그램 동작.
    • 루프
  • 페이징 시스템의 성능을 좋게 하는 근거.

페이지 폴트 핸들러(page fault handler)에는 페이지 교체가 포함됩니다.

1. 디스크에서 원하는 페이지의 위치를 찾습니다.
2. 여유 프레임(free frame)을 찾습니다.
   • 여유 프레임이 있으면 사용합니다.
   • 여유 프레임이 없으면, 페이지 교체 알고리즘(page replacement algorithm)을 사용하여 희생자(victim)를 선택합니다.
3. 원하는 페이지를 (새로) 여유 프레임에 가져옵니다; 페이지 테이블을 업데이트합니다.
4. 프로세스를 다시 시작합니다.

Page Replacement Diagram

참고)

• 1. 희생 페이지(victim page)를 스왑 아웃합니다.
  2. 페이지 테이블의 유효-무효(valid-invalid) 비트를 무효로 변경합니다.
  3. 원하는 페이지를 스왑 인합니다.
  4. 새로운 페이지에 대해 페이지 테이블을 리셋합니다.

Evaluating Page Replacement Algorithms

• 이상적인 알고리즘(Ideal Algorithm)
  • 가장 낮은 페이지 폴트(page-fault) 비율을 얻습니다.
• 알고리즘 평가 방법
  • 특정 메모리 참조 문자열(reference string)에서 실행하고,
  • 해당 문자열에서 페이지 폴트 수를 계산합니다.
• 예시
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Page Faults vs. Frames

• 페이지 폴트 수 대 프레임 수
  • (페이지 폴트 수와 프레임 수 간의 관계를 나타내는 그래프를 보여줍니다.)

FIFO Page Replacement

• FIFO(First In First Out) 순서로 교체합니다.
• 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• 페이지 폴트 수: 15

FIFO Page Replacement Example

• FIFO 페이지 교체 예시(FIFO Page Replacement Example)
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 3 프레임: 9 페이지 폴트
  • 4 프레임: 10 페이지 폴트
  • 벨라디의 역설(Belady's Anomaly)
    • 더 많은 프레임이 더 많은 페이지 폴트를 초래합니다.

 

 

 

 

 

 

 

---

FIFO Illustrating Belady’s Anomaly

• 벨라디의 역설을 보여주는 FIFO
  • (프레임 수와 페이지 폴트 수의 관계를 보여주는 그래프입니다.)

Optimal Page Replacement

• 최적 페이지 교체(Optimal Page Replacement)
  • 가장 오랜 기간 사용되지 않을 페이지를 교체합니다.
  • (LRU랑 헷갈리지 말자. 미래의 페이지 참조를 미리 알고 있다고 가정하고, 가장 나중에 참조되는 페이지를 교체하는 방식임! 미래를 봐야해!)
  • 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Optimal Page Replacement Example

• 최적 페이지 교체 예시(Optimal Page Replacement Example) 
  • 참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 페이지 폴트 수: 6
  • 알고리즘 성능 평가에 사용됩니다.
    • 최적 알고리즘은 페이지 폴트 비율의 하한을 제시합니다.

 

---

Least Recently Used (LRU)

• LRU (Least Recently Used)
  • 가장 최근에 사용되지 않은 페이지를 교체합니다.
  • 참조 문자열(reference string): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

• LRU (Least Recently Used)
  • 참조 문자열(Reference string): 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
  • 8 페이지 폴트(page faults)

• 구현 방법? (How to implement it?)
  • 각 페이지에 대한 참조 시간을 기록해야 합니다.
  • 가장 오래된 참조 시간을 가진 페이지를 찾아야 합니다.
  • 너무 큰 공간과 시간 오버헤드 (Too large space and time overhead)
    • 많은 근사 알고리즘이 제안되었습니다.

• 카운터 구현 (Counter implementation)
  • 모든 페이지 엔트리는 카운터를 가집니다.
  • 페이지가 참조될 때마다 시계(clock)가 증가합니다.
  • 페이지 A가 참조될 때, 클럭을 A의 카운터에 복사합니다.
  • 가장 작은 카운터 값을 가진 페이지를 교체합니다.
• 스택 구현 (Stack implementation)
  • 페이지의 스택을 유지합니다.
  • 페이지가 참조될 때, 그것을 최상위로 이동합니다.
  • 교체를 위한 검색이 필요 없습니다.

• 스택 구현 (Stack implementation)
  • 참조 문자열 (reference string): 4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 7, 1, 2
  • 스택 변경 전 (stack before a): [2, 1, 0, 7, 4]
  • 스택 변경 후 (stack before b): [7, 2, 1, 0, 4]

LRU Approximation Algorithms

• LRU 근사 알고리즘 (LRU Approximation Algorithms)
  • LRU 페이지 교체를 위해, 많은 시스템들이 하드웨어 지원을 제공합니다.
•  참조 비트 (Reference bit)
  • 각 페이지에 대한 비트가 있고, 초기값은 0입니다.
  • 페이지가 참조될 때 1로 설정됩니다.
  • 0인 페이지를 교체합니다 (존재하는 경우).
  • 그러나 참조 순서를 알 수 없습니다.

• 세컨드 찬스 페이지 교체 알고리즘 (Second chance page replacement algorithm) 
  • 시계 알고리즘 (clock algorithm)
    • 교체할 페이지가 참조 비트 1을 가지면,
      • 페이지를 메모리에 남겨 둡니다.
      • 참조 비트를 0으로 설정합니다.
      • 다음 희생자를 찾기 위해 포인터를 이동합니다.

Counting Algorithms

• 카운팅 알고리즘 (Counting Algorithms)
  • LFU (Least Frequently Used) 알고리즘
    • 참조된 횟수를 기록합니다.
    • 가장 적은 횟수를 가진 페이지를 교체합니다.

Allocation

• 할당 (Allocation)
  • 이전 교체 알고리즘
    • 페이지 폴트가 발생하면 희생자를 선택합니다.
      • 고정 할당(fixed allocation)을 가정했으며, 가변 할당(variable allocation)은 아닙니다.
    • 페이지 폴트 시 한 페이지 프레임을 더 할당하는 것을 고려하지 않았습니다.
  • 할당 문제 (Allocation problem)
    • 페이지 폴트 시 할당 크기를 결정합니다.
      • 고정 할당 (fixed allocation)
      • 우선순위 할당 (priority allocation)

Fixed Allocation

• 고정 할당 (Fixed Allocation)
  • 균등 할당 (Equal allocation)
    • 100개의 프레임과 5개의 프로세스가 있다면, 각 프로세스에 20개의 프레임을 할당합니다.
  • 비례 할당 (Proportional allocation)
    • 프로세스 크기에 따라 할당합니다.

Priority Allocation

• 우선순위 할당 (Priority Allocation)
  • 크기보다 우선순위를 사용하는 비례 할당 방식 사용.
  • 더 높은 우선순위를 가진 프로세스에 더 많은 메모리를 할당합니다.

Global vs. Local Allocation

• 전역 교체 (Global replacement)
  • 프로세스가 모든 프레임 집합에서 교체 프레임을 선택합니다.
  • 하나의 프로세스가 다른 프로세스에서 프레임을 가져갈 수 있습니다.
• 지역 교체 (Local replacement)
  • 각 프로세스가 할당된 프레임 집합에서만 선택합니다.

Thrashing(스레싱)

• Thrashing : 프로세스가 "충분한" 페이지를 가지고 있지 않다면, 페이지 폴트 비율이 매우 높아지는 현상
• 이로 인해 
  • 낮은 CPU 사용률 (low CPU utilization)
  • 운영체제는 멀티프로그래밍의 정도를 증가시켜야 한다고 생각합니다.
  • 또 다른 프로세스가 시스템에 추가됩니다.
• 스레싱 (Thrashing)
  • 프로세스가 페이지를 교환하는데 바쁩니다.

Why does thrashing occur?

• 왜 스레싱이 발생하는가? (Why does thrashing occur?)
  • 지역성 크기의 합이 총 메모리 크기를 초과합니다 (∑ size of locality > total memory size).

Working-set Model

• 작업 집합 모델 (Working-set Model)
  • 메모리 참조 패턴의 지역성 (Locality in a memory-reference pattern) 을 나타낸다
    • 시간적 지역성 (Temporal locality): 상대적으로 짧은 시간 동안 특정 데이터 및/또는 자원의 재사용.
    • 공간적 지역성 (Spatial locality): 상대적으로 가까운 저장 위치 내에서 데이터 요소의 사용.

• 작업 집합 모델 (Working set model)
  • 지역성(locality) 가정에 기반합니다.
  • Δ는 작업 집합 윈도우 (working-set window)로, 고정된 페이지 참조 수를 의미합니다.
• WSS_i (프로세스 P_i의 작업 집합)
  • 가장 최근의 Δ에서 참조된 페이지의 총 수
    • Δ가 너무 작으면 전체 지역성을 포괄하지 못합니다.
    • Δ가 너무 크면 여러 지역성을 포함하게 됩니다.
      • Δ가 무한대이면 전체 프로그램을 포괄하게 됩니다.
• D = ∑ WSS_i = 총 요구 프레임 수 (total demand frames)
  • 만약 D > m 이면, 스레싱이 발생합니다.
  •  --> 프로세스 중 하나를 중단합니다 (suspend).

• 위는 작업 집합 예시 (Working set example)

Page-Fault Frequency Scheme

• 페이지 폴트 빈도 방식 (Page-Fault Frequency Scheme)
  • "허용 가능한" 페이지 폴트 비율을 설정합니다.
    • 실제 비율이 너무 낮으면, 프로세스는 프레임을 잃습니다.
    • 실제 비율이 너무 높으면, 프로세스는 프레임을 얻습니다.