[OS] 가상 메모리의 관리

 

관리를 위한 다양한 기법들

 

적재 정책(Fetch Strategy)

요구 적재(Demand Fetch) : 

• 요구 페이징이라고도 하며 페이지가 참조될 때 적재하는 기법
• 페이지들만으로 메모리를 사용하게 되므로 메모리에 관한 오버헤드가 없음.
• 페이지가 적재될 때까지 해당 프로세스를 대기 상태로 만드는 문맥 교환과 디스그와의 입출력 부담

예측 적재(Anticipatory Fetch) :

• 선 페이징이라고도 하며 예측을 통해 확률적으로 참조될 가능성이 높다고 판단되는 페이지를 미리 적재시키는 기법
• 예측이 잘 될 경우 페이지 부재 빈도를 낮춤.
• 예측이 안 될 경우 예측을 위한 오버헤드와 참조되지 않을 페이지를 적재한 메모리의 낭비 발생

---

배치 정책(Placement Strategy)

• 페이징 시스템의 경우 빈 프레임만 발견되면 어떤 프레임을 적재하든 문제 없기 때문에 배치 정책을 따로 신경 쓰지 않아도 된다.
• 세그먼테이션을 사용할 경우 세그먼트의 크기가 얼마든지 다를 수 있으므로 다양한 크기의 세그먼트를 수용할 배치 정책이 요구된다. (최초 적합, 최적 적합, 최악 적합)

---

할당 정책(Allocation Strategy)과 교체 범위

• 개수가 변동 없도록 운영한다면 고정할당, 프로세스에 부여된 프레임의 수에 변동이 있도록 한다면 가변할당
• 교체 정책에서 교체의 대상을 선택할 때 그 범위를 정하는 데에 있어 할당 정책과 밀접한 연관
• 할당된 프레임 중 교체될 페이지를 선택하면 지역 교체, 메모리의 모든 프레임들이 대상이 되면 전역 교체
• 고정 할당을 하게 되면 전역 교체 불가능

---

교체 정책(Replacement Strategy)

 

최적(Optimal) 기법 :

• 현시점에서 가장 오랫동안 참조되지 않을 페이지를 선택하여 교체하는 기법
• 페이지 부재를 최소로 해주지만 프로세스들이 앞으로 어떤 페이지를 참조할지를 미리 알 수 없으므로 현실적으로 구현이 불가능

참조 : Operating System Concepts 8th

1. 7번이 가장 나중에 참조되어 2번과 교체 
2. 1번이 가장 나중에 참조되어 3번과 교체
3. 0번이 가장 나중에 참조되어 4번과 교체....

---

FIFO 기법 :

• 적재된 지 가장 오래된 페이지를 교체하는 기법
• 시간들을 비교하여 가장 오래된 페이지를 찾는데 걸리는 오버헤드 발생

참조 : Operating System Concepts 8th

1. 적재된지 가장 오래된 7번을 2번으로 교체
2. 적재된지 가장 오래된 0번을 3번으로 교체
3. 적재된지 가장 오래된 1번을 0번으로 교체....

• FIFO에서는 부재율을 낮추기 위해 프레임을 더 주었을 경우 오히려 부재율이 올라가는 현상이 나타난다.
• FIFO 모순 (FIFO Anomaly) , Belady's Anomaly
• 자료구조인 큐를 사용하는 방법 참고 하기...

---

LRU(Least Recently Used) 기법

• 참조된 지가 가장 오래된 페이지가 교체 대상
• FIFO와 마찬가지의 오버헤드를 감수해야 함

참조 : Operating System Concepts 8th

1. 참조된 지 가장 오래된 7번을 2번으로 교체
2. 참조된지 가장 오래된 1번을 3번으로 교체
3. 참조된지 가장 오래된 2번을 4번으로 교체.....

• FIFO보다 나은 성능으로 구현될 수 있음
• 최근 자주 참조된 페이지가 앞으로 당분간 자주 참조될 것이라는 판단에 근거한 기법
• 자료구조인 스택을 사용하는 방법 참고 하기...

---

Second-chance (Clock) 기법

• FIFO의 변형 또는 LRU에 근접한 기법
• 적재된 후 한 번이라도 더 참조된 페이지를 바로 교체시키지 않고 한 번 더 메모리에 머물 기회를 주는 기법

참조 : Operating System Concepts 8th

• 참조 비트가 0이면 바로 교체되고, 1일 경우, 적재된 후 한번 이상 참조되었다면 이 비트를 0으로 만들면서 큐의 맨 뒤로 보냄으로써 메모리에 머무를 기회를 한 번 더 준다.
• 순환 큐를 사용하는 방법은 포인터가 이동하는 모습이 시계를 닮았다고 해서 clock 기법이라고도 한다.

---

NUR(Not Used Recently) 기법

• 최근 사용되지 않은 페이지를 교체 , 참조 비트와 갱신 비트가 사용된다.
• 참조 0, 갱신 0인 페이지는 최근 사용하지도 변경되지도 않은 페이지, 교체 1순위
• 참조 0, 갱신 1인 페이지는 최근 사용하지는 않았지만 변경된 페이지, 교체 2순위
• 참조 1, 갱신 0인 페이지는 최근 사용했지만 변경되지 않은 페이지, 교체 3순위
• 참조 1, 갱신 1 인 페이지는 최근 사용도 했고 변경도 한 페이지. 교체 4순위

---

LFU(Least Frequently Used)와 MFU(Most Frequently Used) 기법

적재되어 있는 동안 참조된 횟수를 주적 하여 기록한 후 그 값으로 교체 대상을 선택하는 기법

• LFU는 많이 참조된 페이지는 앞으로도 참조될 확률이 높을 거라 판단해 값이 가장 작은 페이지 선택
• MFU는 많이 참조된 페이지는 충분히 참조가 이루어져 더 이상 참조되지 않을 거라 판단하여 값이 가장 큰 페이지를 선택
• 편향된 시각에 근거함으로 실제로 구현되는 경우는 매우 드물다.

---

페이지 버퍼링(Page Buffering) 기법

적재가 가능한 가용 프레임 몇 개를 풀(Pool)로 유지하면서 부재가 생긴 경우 적재될 페이지는 바로 풀의 한 프레임으로 가져오고, 교체 대상으로 선택된 페이지는 변경된 경우에 한해 디스크로 쓰이고 난 후 풀에 보태진다.

이렇게 되면 교체 대상으로 선택된 페이지가 적재 중 갱신된 경우, 그 내용을 디스크에 쓰고 난 다음 프레임에 적재시키는 시간적인 순서를 지키지 않아도 되므로 빠른 응답을 기대할 수 있다.

교체될 페이지들을 가능한 메모리(가용 프레임 풀)에 남겨두어 디스크 입출력 횟수를 줄이고, 동시에 이 페이지가 다시 참조될 경우 바로 사용할 수 있다는 장점이 있다.

---

지역성(Locality)

• 시간대별로 일부 명령들 또는 프로그램의 특정 부분이 집중적으로 실행되는 현상(반복문, 배열, 행렬...)
• 현재 실행되는 명령어나 접근되는 데이터는 당분간 다시 실행되거나 접근될 확률이 높고 이들과 인접한 명령어나 데이터가 실행되거나 접근될 확률도 높다.
• 지역성은 메모리 관리 특히, 교체 정책의 선택과 밀접한 연관이 있다.
• 잠시 후 참조될 페이지의 반복적인 교체가 과도한 페이지 부재를 야기하여 결과적으로 시스템의 성능을 떨어트리는 스레싱(Thrashing)을 겪을 수 있다.
• 스레싱을 피하기 위해서는 현시점에서 지역성을 보이는 페이지들은 메모리에 적재되도록 해야 한다.

---

Working set 이론

• 프로세스가 특정 시점에서 집중적으로 참조하는 페이지들의 집합을 Working set이라 하고, Working set을 메모리에 적재되도록 함으로써 페이지의 부재를 최소화하겠다는 이론이다.
• Working set 이론에서 윈도 크기를 정하는 것은 중요하다. 너무 크게 잡으면 지역성에 포함되는 페이지들 외에 다른 페이지들도 Working set에 포함될 수 있게 되어 메모리의 낭비가 심해진다.
• 윈도 크기를 너무 작게 잡으면 지역성에 포함되는 페이지들 조차 Working set에서 빠져 스레싱을 겪게 될 것이므로 시스템의 다양한 상황을 반영하여 세심한 결정이 필요하다.

참조 : Operating System Concepts 8th

• 참조되는 페이지들이 부재를 겪으면서 WS(t1)의 크기가 5가 된다. 이후 WS(t2)로 넘어가면서 크기가 2로 줄어들고 강한 지역성을 갖는다.
• 크기에 변동이 있으므로 Working set이 작아지면 프레임을 회수하고 커지게 되면 그만큼 프레임을 더 할당해 주는 가변 할당이 필요하다.

---

하드웨어의 사용

가상 메모리가 효율적으로 운영되기 위해서는 사상에 걸리는 시간을 최소화해야 한다. 

• TLB 추가 하드웨어 사용
• 페이지 테이블의 저장을 캐시와 같은 더 빠른 기억 장치에 저장하는 방법
• 테이블의 일부분을 올릴 수 있는 다수의 레지스터를 사용

사상을 빨리하기 위해 추가의 비용을 들여 필요한 하드웨어를 장착하여 활용

---

몇 가지 고려할 점들

 

페이지 크기

페이지의 크기를 작게 했을 때 예측할 수 있는 점들 (크게 할 경우는 반대의 현상)

• 페이지 테이블이 커질수록 이것을 메모리에 적재해야 하는 부담도 커짐
• 프레임의 크기도 작아지므로 메모리 전체 프레임 개수가 늘어나고 이를 관리해야 할 커널의 부담도 커짐
• 페이지 개수가 증가하므로 적재와 교체 횟수를 증가시켜 잦은 입출력 발생
• 불필요한 내용까지 한 페이지에 들어가지 못하여 꼭 필요한 내용을 담은 페이지들로 Working set이 구성됨
• 프로그램에서 마지막 페이지의 반은 내부 단편화를 가지는데 페이지가 작으면 단편화의 크기가 줄어듦

---

프레임 잠금(Frame Locking)

메모리의 프레임 중 일부를 잠금으로써 교체되지 않도록 해주는 것이 요구될 때가 있다. 

• 부재를 처리하는 루틴을 가진 프레임이 교체되어 버리는 경우
• 입출력해야 할 페이지가 입출력 전에 교체되는 경우
• 실시간으로 처리되어야 할 영역을 가지는 프레임이 교체될 경우

---

 

참고 자료

• OS? Oh Yes! , 김주균 지음

• Operating System concepts 8th