[컴퓨터 구조 - 하드웨어 - 메모리]
참고한 자료:
Computer Organization and Desgin 5th edition,
Operating System: Concepts 10th edition BY A.Silberschatz
cf. page and frame
Page는 가상 메모리에서 데이터를 저장하는 단위, frame은 물리 메모리에서 데이터를 저장하는 단위
<1> Virtual Memory
가상 메모리란, 앞선 접근은 프로세스 전체가 메모리에 올라와 실행된다는 전제하에 살펴봤던 반면, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법이다.
가상 메모리는 실제 physical memory와 유저의 logical memory의 개념을 분리함으로 작은 메모리를 가지고도 큰 가상 주소 공간을 제공받을 수 있다.
이러한 가상 메모리의 구현 방식으로 Demand Paging이 존재한다.
<1>-A. Demand Paging
앞선 가상 메모리에 이야기했듯이, 전체 프로그램을 메모리에 적재할 필요없기 때문에, 초기에 필요한 것들만 적재하는 전략을 취하는 것도 방법이다. 요구 페이징은 실행시간 동안 실제로 필요한 것에 대해 메모리 페이지를 로드하는 가상 메모리 구현 방식이다.
이러한 요구 페이징에서 page table은 valid-invalid bit라는 각 페이지의 상태를 나타내는 플래그를 통해 페이지의 상태를 확인한다. 필요로 하는 기능의 페이지만 적재하여 valid를, 그렇지 않고 HDD에 남아있는 것은 invalid 값으로 표시한다.
1) Valid 페이지를 접근할 때,
page가 physical memory에 적재된 상태이므로 바로 접근 가능하다.
2) Invalid 페이지를 접근할 때,
Page fault가 발생한다고 말한다.
Page Fault발생 시,
OS는 Secondary Storage로부터 해당 page를 가져와 physical memory에 적재시키며,
page table의 해당 entry를 업데이트하며,
valid-invalid bit를 1(valid)로 설정한다.
<1>-B. Copy-On-Write
COW는 가상 메모리 구현을 더 효과적으로 하기 위한 기술로, 데이터를 처음에는 공유하여 복사를 지연시키고, 실제로 데이터를 수정할 때만 복사를 수행하는 방식입니다.
즉, 간단히 정리하면
-
리소스 공유
-
Write 작업 시 Copy 발생시켜 원본 리소스를 복제하여 쓰기 작업을 수행
-
page table을 업데이트 (여전히 다른 프로세스는 원본 데이터 참조)
여느 Sharing과 관련한 부분과 마찬가지로,
리소스의 공유로 인한 consistency 문제가 존재할 수 있다.
Page Replacement
가상 메모리에서, 유저가 degree of multiprogramming을 계속해서 증가시키게 된다면,
(cf. degree of multiprogramming: main memory 내 존재하는 active job 개수)
메모리를 과도하게 할당하게 되어 필요한 페이지를 로드할 공간이 메모리에 부족하게 된다.
이러할 경우 최악에는 프로세스를 종료시킬 수 있기 때문에, 가장 일반적인 방법으로
기존의 페이지를 제거하거나 교체하는 작업인 page replacement 작업을 한다.
시나리오
교체될 페이지, 이하
victim page에 대해 page out시킨다.
(from physical memory (main memory) to secondary memory/HDD/backing storage)페이지 테이블 수정: valid-invalid bit의 값을 invalid로 바꿔준다.
요구되는 페이지를 page out 시킨 메모리에 page in 시킨다.
마찬가지로 페이지 테이블 수정하여 valid-invalid bit의 값을 valid로 바꿔준다.
시간 관계 상 생략하지만, page replacement와 관련하여 이해하기 위해 다음과 같은 개념을 찾아보는 것을 추천한다.
- Modify Bit
- Reference String
이러한 page replacement에 있어서, 다양한 방식의 알고리즘이 사용된다. 다만, 우리의 목적은 page fault를 최소화시키는 데에 있다는 것을 명심해야 한다.
-
Optimal Page replacement
-
FIFO (First in First out)
-
LRU (Least Recently Used)
-
LRU-Approximation: Second-Chance
-
Counting-Based : LFU (Least Frequently Used), MFU (Most Frequently Used)
-
Page Buffering
시간관계 상 해당 알고리즘들을 자세히 다루진 않겠으나, 개념적으로 몇가지만 설명하고자 한다.
Belady's Anomaly
직관적으로, frame이 많아질수록 page fault가 감소할 것이라는 자명하다. 그럼에도 이러한 기대와 달리 frame이 많아짐에도 주어진 process에 부적합한 page replacement 알고리즘으로 인해 (보통 FIFO의 경우다) 그렇지 않은 경우보다 page fault가 증가하는 현상이 나타난다. 이를 Belady's Anomaly라 한다.
3개의 프레임
Reference String: 1 2 3 4 1 2 5 1 2 3 4 5
Frame:[1][1 2][1 2 3][2 3 4][3 4 1][4 1 2][1 2 5][1 2 5][1 2 5][2 5 3][5 3 4][5 3 4]Total Page Fault: 9번
4개의 프레임
Reference String: 1 2 3 4 1 2 5 1 2 3 4 5
Frame:[1][1 2][1 2 3][1 2 3 4][1 2 3 4][1 2 3 4][2 3 4 5][3 4 5 1][4 5 1 2][5 1 2 3][1 2 3 4][2 3 4 5]Total Page Fault: 10번
cf. 이외에도 global page replacement, major/minor page fault 같은 개념을 찾아보는 것을 추천한다.
Thrashing
앞서서, 우리는 메모리 관리를 위해 page fault를 최소화하기 위해 page replacement를 다양한 알고리즘으로 적용함을 찾아보았다. 아이러니하게도, 이러한 목적에서 이루어지는 page replacement가 과도하게 발생하는 경우에, CPU와 메모리 간의 지속적인 데이터 이동으로 인해 실제로 유용한 작업을 수행하지 못하게 된다. 그로 인해 결국 시스템의 response time이 급격히 느려지고 CPU Utilization이 급격히 감소하여 마치 작업이 멈춘 것처럼 보이는 단계에 이르게 되는데 이를 Thrashing이라 한다.
(보통, Thrashing이란 프로세스가 실제 execution에 필요한 시간보다 더 많은 시간을 paging에 사용할 때를 일컫기도 한다.)
발생 시나리오
OS는 CPU의 사용률을 추적하여 너무 낮다면 새로운 process를 더 추가해 degree of multiprogramming을 높인다. 이 때 paging 과정에서 page fault가 발생해 page replacement 작업을 진행하는 동안 프로세스는 대기하게 되므로 CPU 사용률이 감소한다.
감소된 CPU 사용률을 보고 마찬가지로 프로세스를 추가하게 되고 이는 결국 더 많은 page fault와 paging으로 인한 대기 시간을 발생시켜, 종국에는 실제 main memory 접근 시간은 증가하고 paging하는 데에 시간을 소모하게 되어 작동이 멈춘 것처럼 보이게 된다.
Solution
결국에는 아이러니 하게도, CPU Utilization을 높이기 위해 증가시키던 degree of multiprogramming을, CPU Utilization이 감소하는 지점에서 낮춰야 한다.
이러한 솔루션은 Working-Set 모델 방식을 통해 해결한다.
이는 pt.1에서 언급한 locality 개념을 이용하여, 프로그램이 실행되는 동안, 해당 특정 시간 내 참조되는 위치를 지역성에 기반하여 일정 시간 동안 참조된 페이지들의 집합을 Working Set으로 간주하는 방식이다.
그 이외에도 Page fault Frequency에 기반한 쓰레싱 방지를 찾아보는 것을 추천한다.
