[OS] 가상메모리(Virtual Memory)

가상 메모리 개념

제한된 물리적 메모리 크기

• 실제 메모리의 사용 가능한 공간보다 큰 프로그램은 실행할 수 없다.

일반 프로그램 실행 패턴

• 프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않는다.
  
  • 오류 코드,예외 코드
  • 배열 100x100 요소이지만 10x10 요소만 사용
  • 프로그램의 특정 옵션 및 기능은 거의 사용되지 않는다.
• 전체 프로그램이 필요한 경우에도 모든 프로그램이 동시에 필요하지 않을 수 있다.

가상 메모리

• 메모리에 완전히 저장되지 않은 프로세스를 실행할 수 있다.
• 프로그램의 일부는 실행을 위해 메모리에 있어야 한다.
• 논리 메모리 주소 공간과 실제 메모리 주소 공간의 분리
• 논리 메모리 주소 공간은 물리적 메모리 주소 공간보다 클 수 있다.

가상 주소 공간

 

---

요구 페이징(Demand Paging)

가상 메모리는 요구 페이징을 통해 구현할 수 있다.

필요한 경우에만 페이지를 메모리로 가져온다.

• 적은 I/O가 필요
• 적은 메모리가 필요

페이지를 주고받을 수 있어야 한다.

페이지를 참조할 때,

• 유효한(valid) 참조 → 참조
• 잘못된(invalid) 참조 → not-in-memory → 메모리로 가져온다.

valid–invalid 비트는 각 페이지 테이블 항목과 연결된다.

• v → in-memory
• i → 메모리에 없거나 올바르지 않습니다(잘못된 주소, 보호 위반)
• 주소 변환 중 valid–invalid 비트가 i인 경우 페이지 오류(page fault)

일부 페이지가 메인 메모리에 없는 경우 페이지 테이블

잘못된 페이지에 액세스하면 페이지 오류(page fault) 발생

→ OS 내의 페이지 오류 처리기(Page fault handler)가 호출

페이지 오류 처리기(Page fault handler)

1. 잘못된(invalid) 참조
   
   • 잘못된 주소 또는 보호 위반 → 프로세스 중단
   • 메모리에 없는 경우 → 2
2. 빈 페이지 프레임을 가져온다.
   
   • 빈 페이지 프레임이 없는 경우 일부 페이지 프레임을 바꾼다.
3. 페이지 프레임에 페이지를 읽는다.
   
   • 이 프로세스는 디스크 I/O가 수행될 때까지 차단된다.
   • 디스크 I/O가 완료되면 페이지 테이블 항목을 유효(valid)로 설정
   • 프로세스를 준비 대기열(ready queue)에 다시 삽입하고 나중에 발송(dispatch)
4. 페이지 오류를 발생시킨 명령을 재시작

페이지 오류 처리(Page fault handling)

페이지 오류율(Page Fault Rate) 0 ≤ p ≤ 1.0

• p = 0 : 페이지 오류 없음
• p = 1 : 모든 참조가 오류

유효 액세스 시간(EAT, Effective Access Time)

• EAT = (1 – p) x 메모리 액세스 시간 + p x 페이지 오류 서비스 시간
• 예)
  
  • 메모리 액세스 시간 = 200ns
  • 평균 페이지 오류 서비스 시간 = 8ms(=8,000,000ns)
  • EAT = (1 – p) x 200 + p x 8,000,000 = 200 + p x 7,999,800
  • 1,000개의 액세스 중 하나가 페이지 오류를 유발하는 경우
    
    • EAT = 8,200 ns
    • 이는 40배로 둔화된 것

페이지 오류율을 낮게 유지하는 것이 중요

• 좋은 페이지 교체(page replacement) 정책이 필요

 

---

페이지 교체(Page Replacement)

페이지 교체

• 실제로 사용하지 않는 페이지를 찾기 → 페이지 교체
• 좋은 페이지 교체 알고리즘
  
  • 페이지 오류의 최소화

참조 위치(Locality of reference)

• 같은 페이지를 여러 번 메모리에 저장할 수 있다.
• 실제 대부분의 프로그램에서 관찰되는 현상
• 일정 시간에 극히 일부 페이지만 집중적으로 참조하는 프로그램 동작
  
  • Loop
• 페이징 시스템이 성능이 좋게 되는 근거

페이지 교체를 포함한 페이지 오류 처리기(Page fault handler)

1. 디스크에서 원하는 페이지의 위치를 찾는다.
2. 빈 프레임을 찾는다.
   
   • 빈 프레임이 있는 경우 : 사용
   • 빈 프레임이 없는 경우 : 페이지 교체 알고리즘 사용, 대상 선택
3. 원하는 페이지를 (새로) 빈 프레임으로 가져와서 페이지 테이블을 업데이트
4. 프로세스 재시작

이상적인 알고리즘

• 페이지 오류율이 가장 낮다.

알고리즘 평가

• 특정 메모리 참조 문자열에서 실행
  
  • 참조 문자열
• 해당 문자열의 페이지 오류 수를 계산

일부 예에서 참조 문자열

• 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

페이지 오류 수 vs 프레임 수

 

---

FIFO 페이지 교체

FIFO(First In First Out) 순서로 대체하는 페이지 교체

15 page faults

참조 문자열

• 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

3프레임

4프레임

벨라디의 변칙(Belady’s Anomaly)

• 더 많은 프레임 → 더 많은 페이지 오류

벨라디의 변칙을 보여주는 FIFO

 

---

최적의(Optimal) 페이지 바꾸기

장기간 사용되지 않는 페이지 교체

다른 프레임 예제

• 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
•  

이것을 어떻게 아는가?

알고리즘의 성능을 측정하는 데 사용

• 최적 알고리즘은 페이지 오류율의 하한을 나타낸다.

 

---

LRU(Least Recently Used, 가장 최근 사용)

가장 최근에 사용하지 않은 페이지를 바꾼다.

참조 문자열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

구현 방법

• 각 페이지마다 참조 시간을 기록
• 참조 시간이 가장 오래된 페이지를 찾는다.
• 공간 및 시간 오버헤드가 너무 큼
  
  • → 많은 근사 알고리즘이 제안

카운터 구현

• 모든 페이지 항목에는 카운터 존재
• 페이지가 참조될 때마다 클럭이 증가
• A페이지가 참조되면 A의 카운터에 클럭를 복사
• 가장 작은 카운터 값으로 페이지를 바꾼다.

스택 구현

• 페이지의 스택을 유지
• 페이지가 참조되면 맨 위로 이동
• 교체 검색이 없다.

스택 구현

 

---

LRU 근사 알고리즘

LRU 페이지 교체의 경우,

• 많은 시스템이 하드웨어 지원을 제공

참조 비트

• 각 페이지에 대한 비트로, 처음에는 0으로 설정
• 페이지 참조 시 1로 설정
• 0인 것을 교체 (있는 경우)
  
  • 하지만, 우리는 참조 순서를 모른다.

두 번째 기회 페이지 교체 알고리즘(클럭 알고리즘)

• 교체할 페이지에 기준 비트 1이 있을 경우,
  
  • 페이지를 메모리에 남긴다.
  • 참조 비트 0을 설정
  • 참조 비트가 0인 페이지를 찾을 때까지 다음 대상에 대한 사전 포인터

 

---

카운팅 알고리즘

LFU(최빈도 사용) 알고리즘

• 작성된 참조 번호를 유지
• 가장 작은 카운트로 페이지를 교체

---

할당

이전 교체 알고리즘

• 페이지 오류가 발생하면 대상을 선택
  
  • 그들은 변수 할당이 아닌 고정 할당을 가정
• 페이지 오류 시 페이지 프레임을 하나 더 할당하는 것을 고려?

할당 문제

• 페이지 오류에서 할당 크기를 결정
  
  • 고정 할당(fixed allocation)
  • 우선 할당(prioity allocation)

 

---

고정 할당(Fixed Allocation)

균등 할당(Equal allocation)

• 프레임이 100개이고 프로세스가 5개인 경우,
  
  • 각 공정에 20프레임을 제공

우선순위 배분(prioity allocation)

• 프로세스 규모에 따른 배분

 

---

우선 순위 할당(Priority Allocation)

• 비례 할당 체계 사용
  
  • 크기보다는 우선순위 사용
  • 상위 프로세스에 더 많은 메모리 제공

 

---

글로벌 vs. 로컬 할당

글로벌 교체

• 프로세스는 모든 프레임 집합에서 교체 프레임을 선택
• 한 프로세스가 다른 프로세스의 프레임을 가져올 수 있다.

로컬 교체

• 각 프로세스는 고유한 할당된 프레임 집합에서만 선택

 

---

스레싱(Thrashing)

프로세스에 "충분한" 페이지가 없으면 페이지 오류율이 매우 높다.

• 낮은 CPU 활용률
• 운영 체제 : 멀티프로그래밍의 정도를 높여야 힌다.
• 다른 프로세스가 시스템에 추가

스레싱

• 페이지를 주고받을 때 프로세스가 사용 중

스레싱 발생 이유

• 로컬 사이즈 크기의 합 > 총 메모리 크기

 

---

작업 세트(Working-set) 모델

메모리 참조 패턴의 지역성(Locality)

• 시간적 지역성 : 상대적 짧은 시간 내에 특정 데이터 및/또는 리소스를 재사용
• 공간적 지역성 : 비교적 가까운 저장 위치 내에서 데이터 요소를 사용

작업 세트 모델

• 지역성을 전제
• ∆ ≡ working-set window ≡ 고정된 수의 페이지 참조

WSSi(프로세스 Pi의 작업 세트)

• 가장 최근에 참조된 총 페이지 수 ∆
  
  • ∆이 너무 작으면 : 전체 지역을 포함 X
  • ∆이 너무 크면 : 여러 지역을 포함
    
    • ∆ = ∞ : 전체 프로그램을 포함

D = Σ WSSi ≡ 총 수요 프레임

• D > m 인 경우 스래싱
• → 프로세스 중 하나를 일시 중단

---

페이지-오류 빈도 체계

"허용 가능한" 페이지 오류율을 설정

• 실제 비율이 너무 낮으면 : 공정에서 프레임이 손실
• 실제 비율이 너무 높으면 : 공정이 프레임을 획득

 

---

요약

• 가상 메모리
  • 메모리에 완전히 있지 않은 프로세스를 실행할 수 있는 메커니즘
• 요구 페이징
  • 필요할 때만 페이지를 메모리로 가져온다.
• 페이지 오류율을 낮게 유지하는 것이 중요 → 좋은 페이지 교체 정책 필요
• LRU(가장 최근에 사용) : 가장 최근에 사용되지 않은 페이지를 대체
• 프로세스에 페이지 프레임이 충분하지 않으면 스레싱이 발생