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

floatFirstTOC: right

🖥️ 시작하며

🔍 Page Replacement (페이지 교체)

• Page faults가 발생하면, 운영체제는 해당 페이지를 디스크에서 페이지 프레임(물리 메모리)로 로드

🙋 그렇다면 어느 시점에서 물리 메모리가 꽉 차면 어떻게 되나? (물론 OS가 물리 메모리가 꽉 차지 않도록 조정하지만, 그 상태도 어차피 Page fault가 일어남) → 페이지 프레임을 확보하기 위해 페이지를 희생시켜야 하는 딜레마 발생!

🙋 그렇다면 어떤 페이지를 희생시킬 것인가?

💡 페이지를 교체하는 가장 좋은 방법이 무엇일까?

• Page fault가 발생할수록 성능 감소로 이어지니, 결국 Page Replacement Algorithm 의 궁극적인 목표는 교체시키기 가장 좋은 페이지를 교체하는 것

• 물론 가장 좋은 방법은 앞으로 쓰이지 않을 페이지의 교체일 것

💡 Belady’s Proof

• 향후 가장 오랫동안 사용되지 않을 페이지를 교체해야 함

• 근데 그걸 어떻게 예측할 거냐?
• Belady의 증명이 좋은 이유는 기준점으로 사용 가능함 (가장 좋은 알고리즘!)
→ 다른 알고리즘과 비교해 개선 여지 측정

1️⃣ FIFO (First-In First-Out)

• 장점
• 가장 오래 전에 가져온 페이지가 이제 사용되지 않을 수 있으므로 좋을 수 있음

• 단점
• 물론 해당 페이지가 계속 사용될 수 있음
• Belady의 모순이 발생, 메모리 크기가 켜져도 더 fault가 많이 일어날 수 있음

📎 예시

2️⃣ LRU (Least Recently Used)

• 더 나은 교체 결정을 위해 참조 정보를 이용 (Reference Bit)

• 과거로 미래를 예측하자는 아이디어 (History만 잘 가지고 있으면 됨, 추가적인 비용 발생)

• 구현 방법
• Counter 구현 : 타임스탬프 넣기
• Stack 구현 : 스택을 유지
→ 둘다 쉽지 않음!

📎 예시

📌 Counter-based LRU Approximation

• 작동 방식:
1. 각 페이지마다 카운터를 유지
2. 정기적인 간격으로 모든 페이지에 대해 다음을 수행:
• 참조 비트(R)가 0이면, 카운터를 증가 (페이지가 사용되지 않았음을 의미)
• 참조 비트(R)가 1이면, 카운터를 0으로 설정 (페이지가 사용되었음을 의미)
→ 카운터는 페이지가 참조되지 않은 시간 간격의 수
3. 가장 큰 카운터 값을 가진 페이지를 교체 (가장 오래 사용되지 않은 페이지).

• 일부 아키텍처에서는 참조 비트가 없는 경우 유효 비트를 사용하여 페이지 폴트를 유도함으로써 참조 비트를 시뮬레이션할 수 있음

📌 Second Chance Algorithm

• 작동 방식:
1. 페이지 프레임 배열과 참조 비트를 사용
2. 페이지 교체 시, FIFO 순서로 페이지를 검사
3. 참조 비트에 따라 다음을 수행:
1. 참조 비트가 0이면, 페이지를 교체
2. 참조 비트가 1이면, 참조 비트를 0으로 설정하고 해당 페이지를 FIFO 리스트의 끝으로 이동
4. 페이지가 참조될 때마다 참조 비트를 1로 설정

• 특징:
• 간단한 구현 가능 (운영체제가 수행, 하드웨어가 하는 것 아님)
• 최근에 사용된 페이지를 교체하지 않도록 보장
→ 교체된 페이지가 가장 오래 쓰이지 않았다는 보장 X
• Counter-based에 비해 오버헤드 적음 (상대적으로 간단)
 

3️⃣ NRU (Not Recently Used)

• 기존과 동일하게 참조 비트(R)도 사용하고 추가로 수정 비트(M)도 사용

• 주기적으로(각 클럭 인터럽트) 참조 비트를 초기화
→ 최근에 참조된 페이지와 그렇지 않은 페이지를 구분하기 위함

• 이해하기 쉽고, 최적은 아니지만 적절한 성능을 제공한다는 장점을 가짐

4️⃣ LFU, MFU

📌 LFU (Least Frequently Used) 

📌 MFU (Most Frequently Used) 

• 1 bit 개수를 세서 구현

• 통상적으로 LRU이 더 성능 좋음

🔍 프레임 할당 문제

• 멀티프로그래밍 시스템에서는 경쟁하는 프로세스에 물리 메모리 할당하는 방법 필요:
• 희생된 페이지가 다른 프로세스에 속하는 경우 어떻게 할 것인가?
• 각 프로세스에 얼마나 많은 메모리를 할당할 것인가?

📌 Fixed Space Algorithms (고정 공간 알고리즘)

• 각 프로세스는 사용할 수 있는 페이지 수의 한계를 가짐

• 한계에 도달하면 자신의 페이지 중에서 교체함

• 로컬 교체: 일부 프로세스는 잘 수행되지만, 다른 프로세스는 성능 저하

📌 Variable Space Algorithms (가변 공간 알고리즘)

• 프로세스의 페이지 집합이 동적으로 증가하고 감소함

• 글로벌 교체: 한 프로세스가 다른 모든 프로세스의 성능을 저하시킬 수 있음 (예: Linux)

🔍 Thrashing

• 문제점:
• 유용한 작업을 수행할 시간이 없음
• 시스템이 과부하 상태에 있음
• 어떤 페이지가 메모리에 있어야 Page fault를 줄일 수 있는지 알 수 없음
• 모든 프로세스에 충분한 물리 메모리가 없을 수 있음

• 가능한 해결법
• 프로세스 죽이기
• 메모리 추가 구매
 

📌 Working Set

• 정의
• WS(t, w) = { pages P such that P was referenced in the time interval (t, t-w) }
• t: 시간
• w: 워킹 셋 윈도우 크기 (페이지 참조 수로 측정)
• 페이지가 워킹 셋에 포함되는 조건: 마지막 w번의 참조에서 참조된 페이지

💡 w 인자에 대해 더 자세한 설명

1. 워킹 셋 윈도우 크기(w):
• w는 시간 간격이 또는 최근 페이지 참조 수를 의미
예를 들어 w=10이면, 최근 10번의 페이지 참조를 기준으로 워킹 셋을 정의
• 이는 프로세스의 최근 행동을 반영하여 현재 필요한 페이지 집합을 예측

2. 워킹 셋 정의:
• WS(t, w)는 시간 t에서 최근 w번의 페이지 참조 동안 참조된 모든 페이지의 집합
예를 들어 현재 시간이 t=100이고, w=10이면
→ t=90에서 t=100까지의 페이지 참조를 기준으로 워킹 셋을 정의

💡 예시

• 조건
• 프로세스 P1
• 페이지 참조 스트림: P1이 참조하는 페이지의 순서, 예를 들어, [1, 2, 1, 3, 1, 2, 4, 1, 2, 3]와 같이 페이지 참조가 발생
• 윈도우 크기 (Δ (or w)): 4 (최근 4개의 참조를 고려)

• 과정
1. 초기 상태
• 페이지 참조 스트림이 [1, 2, 1, 3]이라면:
• 워킹 셋: {1, 2, 3}
• 설명: 최근 4개의 참조가 1, 2, 1, 3이므로, 중복된 페이지 1을 제외하고 {1, 2, 3}이 워킹 셋에 포함
2. 다음 상태
• 페이지 참조 스트림이 [2, 1, 3, 1]이라면:
• 워킹 셋: {1, 2, 3}
• 설명: 최근 4개의 참조가 2, 1, 3, 1이므로, 중복된 페이지 1과 2를 제외하고 {1, 2, 3}이 워킹 셋에 포함
3. 다음 상태
• 페이지 참조 스트림이 [1, 3, 1, 2]이라면:
• 워킹 셋: {1, 2, 3}
• 설명: 최근 4개의 참조가 1, 3, 1, 2이므로, 중복된 페이지 1과 3을 제외하고 {1, 2, 3}이 워킹 셋에 포함
4. 다음 상태
• 페이지 참조 스트림이 [3, 1, 2, 4]이라면:
• 워킹 셋: {1, 2, 3, 4}
• 설명: 최근 4개의 참조가 3, 1, 2, 4이므로, 모든 페이지가 서로 다르므로 {1, 2, 3, 4}가 워킹 셋에 포함
5. 다음 상태
• 페이지 참조 스트림이 [1, 2, 4, 1]이라면:
• 워킹 셋: {1, 2, 4}
• 설명: 최근 4개의 참조가 1, 2, 4, 1이므로, 중복된 페이지 1을 제외하고 {1, 2, 4}가 워킹 셋에 포함

• 결과
• 워킹 셋 모델에서는 워킹 셋의 크기가 변할 수 있음
• 예를 들어, 페이지 참조 스트림이 [1, 2, 1, 3, 4, 5, 6]이라면 초기에는 워킹 셋이 {1, 2, 3}에서 {3, 4, 5, 6}으로 변할 수 있음
• 워킹 셋 크기가 메모리 크기보다 커지면 페이지 폴트가 증가하고, 메모리에 적재된 페이지가 자주 교체되어 스래싱이 발생할 수 있음

📌 Working Set Size (WSS)

• 프로그램의 지역성에 따라 변화
• 지역성이 좋지 않은 동안에는 더 많은 페이지가 참조됨
• (처음 선언되거나 int a[10000] 등등)
• 이 기간 동안 Working Set 크기가 커짐 (Frame 많이 요구)

• Working Set은 과도한 페이지 폴트(Thrashing)를 방지하기 위해 메모리에 있어야 함

• Working Set에 따라 멀티프로그래밍 정도를 제어:
• 각 프로세스에 WSS 파라미터를 연관시킴
• WSS 합계가 총 프레임 수를 초과하면 프로세스를 중단시킴
• 해당 프로세스의 WSS가 메모리에 맞을 때만 실행

📌 Working Set Page Replacement

1. Working Set 근사치를 구하기 위해 현재의 가상 시간 측정 (프로세스가 실제로 사용한 CPU 시간)

2. 페이지 교체 알고리즘 사용
• PTE마다 마지막 사용 시간 (Tlast) 필드를 유지
• 주기적인 클럭 인터럽트가 R 비트를 초기화
• Page fault가 발생할 때마다 페이지 테이블을 스캔하여 적절한 페이지를 찾아서 퇴거시킴
• Tlast : 페이지가 마지막으로 참조된 시간을 기록하는 필드
• 페이지 부재가 발생할 때:
• R = 1일 경우:
• 현재 가상 시간을 Tlast에 기록
• R = 0일 경우:
• 현재 가상 시간(Tcurrent)에서 Tlast를 뺀 값이 t(윈도우 크기)보다 크면 해당 페이지를 교체
• 그렇지 않으면 아무런 작업도 하지 않음

1️⃣ 주어진 조건

• 현재 가상 시간 (Current virtual time, Tcurrent): 2204

• 윈도우 크기 (t): 600

2️⃣ 워킹 셋 예측 및 페이지 교체 과정

1. 현재 가상 시간 (Tcurrent) 확인
• 현재 가상 시간은 2204입니다. 이는 프로세스가 지금까지 사용한 CPU 시간을 나타냅니다.

2. R 비트 확인 및 Tlast 갱신
• 페이지 테이블의 각 엔트리를 스캔하면서 R 비트를 확인합니다.
• R 비트가 1인 경우: 최근에 참조되었음을 의미하므로, Tlast를 현재 가상 시간으로 갱신합니다.
• R 비트가 0인 경우: 최근에 참조되지 않았음을 의미합니다. 이 경우, 페이지의 나이(Age)를 계산하여 t와 비교합니다.

3. 나이(Age) 계산
• 나이(Age)는 현재 가상 시간에서 마지막 사용 시간을 뺀 값입니다.
• 예를 들어, Tlast가 1213인 페이지의 나이는 2204 - 1213 = 991입니다.

4. 페이지 교체 조건 확인
• 나이가 t보다 큰 경우, 해당 페이지를 교체 후보로 고려합니다.
• 나이가 t보다 작은 경우, 해당 페이지는 워킹 셋의 일부로 유지됩니다.

3️⃣ 페이지 교체 결정

• 페이지 2084: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 2003: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 1980: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 1213: R = 0 (최근에 참조되지 않음) -> 나이 = 2204 - 1213 = 991 (t = 600보다 큼) -> 교체 후보

• 페이지 2014: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 2020: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 2032: R = 1 (최근에 참조됨) -> Tlast = 2204로 갱신

• 페이지 1620: R = 0 (최근에 참조되지 않음) -> 나이 = 2204 - 1620 = 584 (t = 600보다 작음) -> 교체하지 않음

💡 결론

• 페이지 1213은 나이(991)가 윈도우 크기(t = 600)보다 크기 때문에 교체 후보로 결정됩니다.

• 따라서, 주어진 조건에서 교체할 페이지는 페이지 1213입니다.

📌 PFF (Page Fault Frequnecy)

• fault rate 가 기준값보다 높을 시:
• 메모리가 부족하다는 의미
• 메모리를 더 많이 줘야 하지만, 완전한 해결책은 아님 (FIFO, Belady’s anomaly)

• fault rate 가 기준값보다 낮을 시:
• 너무 많은 메모리를 할당받았다는 의미
• 메모리를 빼앗음

• 만약 PFF가 증가하고 사용 가능한 프레임이 없는 경우
→ 일부 프로세스를 죽이던가 멈춤

🔍 Advanced VM Functionality

📌 Shared Memory

• 프로세스마다 가상 주소 공간은 서로로부터 보호됨 → 이로 인해 데이터 공유가 어려움
• 웹 서버나 프록시의 부모와 자식은 주소 공간을 복사하지 않고 인메모리 캐시를 공유하고자 함
• 읽기/쓰기(데이터 공유를 위한 액세스)
• 실행(공유 라이브러리)

• 공유 메모리를 사용해 프로세스가 직접 메모리 참조를 사용해 데이터를 공유할 수 있음
• 두 프로세스 모두 메모리 세그먼트에 대한 업데이트를 확인

🙋 공유 데이터에 대한 엑세스를 어떻게 조정하나? → 페이지를 공유함으로써 구현!

💡 구현

1. 두 프로세스의 Page Table Entry (PTE)가 동일한 물리적 프레임을 참조하도록 설정
• 각 PTE는 서로 다른 보호 값을 가질 수 있음 (Read, Write, Execute)
• 페이지가 무효화될 때 두 PTE 모두 업데이트 필요

2. 각 프로세스의 주소 공간에서 공유 메모리 매핑:
• 다른 가상 주소에 매핑:
• 유연성 높음 (주소 공간 충돌 없음)
• 공유 메모리 세그먼트 내의 포인터가 무효화됨
• 같은 가상 주소에 매핑:
• 유연성 낮음
• 공유 포인터가 유효함
 

📌 Copy On Write

1. 스레드 사용
• 주소 공간을 공유하는 것은 비용이 들지 않음

2. vfork() 시스템 호출 사용
• vfork()는 부모의 메모리 주소 공간을 공유하는 프로세스를 생성
• 자식이 종료하거나 새로운 프로그램을 실행할 때까지 부모의 실행이 차단됨 (데이터 덮어쓰기를 방지)
• 자식의 변경 사항은 부모가 다시 실행될 때 확인 가능
• 자식이 즉시 exec()을 실행하는 경우에 유용함

3. Copy On Write (COW)
• 기본 개념:
• 모든 페이지를 복사하는 대신, 부모 페이지를 자식 주소 공간에 공유 매핑으로 생성
• 공유 페이지는 자식 프로세스에서 읽기 전용으로 보호됨
• 작동 원리:
• 읽기: 평소와 같이 진행
• 쓰기: 보호 오류 발생, OS로 트랩
• OS 처리:
• 페이지를 복사하고
• 클라이언트 페이지 테이블에서 페이지 매핑 변경
• 쓰기 명령 재시작해서 쓰기 작업 완료
→ 디스크 공간을 많이 절약할 수 있음! VM에서도 자주 사용

📌 Memory-Mapped Files

• mmap() 시스템 호출: 파일을 가상 메모리 영역에 바인딩
• PTE가 가상 주소를 파일 데이터가 있는 물리적 프레임에 매핑
→ 메모리 다루듯이 파일을 다룰 수 있게 됨
• <가상 주소 베이스 + N> = <파일의 오프셋 N>

• 작동 원리:
• 초기에는 매핑된 영역의 모든 페이지가 무효로 표시됨
• 무효 페이지에 접근할 때, OS가 파일에서 페이지를 읽음
• 물리 메모리에서 페이지가 축출될 때, OS가 페이지를 파일에 씀
• 페이지가 더럽지 않으면(write되지 않았으면) 파일에 쓸 필요 없음