Operating System : Concepts - 가상 메모리 (Virtual Memory) (2)

https://github.com/BOOOO0/linux-operating-system

GitHub - BOOOO0/linux-operating-system: 리눅스 명령어, 이론과 운영체제 실습

깃허브에 더 많은 내용이 있습니다.

 

페이지 교체 (Page Replacement)

---

페이지 교체는 메모리에 로드되어야 할 페이지의 수가 현재 free-frame의 수보다 많을 경우에 필요하다.

 

 

 

 

 

물리 메모리에 남은 프레임이 없는 상태에서 새로운 페이지를 로드시키고 싶다면 하나의 프레임을 선정해서 page out 시켜야한다.

 

1. 희생될 프레임의 메모리 할당을 해제하고 page table에 해당 페이지의 비트를 invalid로 수정한다.
2. 해당 프레임에 새 페이지를 읽어오고 page table을 valid로 수정한다.
3. page fault가 발생한 시점부터 프로세스를 재개한다.

 

 

 

요구 페이징 (Demand Paging)은 두가지 major problem을 해결해야 하는데 프레임 할당 알고리즘과 페이지 교체 알고리즘이다. 

 

이것이 중요한 이유는 Secondary Storage에 I/O하는 것은 비용이 많이 든다.

 

요구 페이징의 방법을 약간만 개선해도 시스템 성능이 크게 향상될 수 있다.

 

성능의 평가는 페이지 부재율이 낮을수록 좋은 알고리즘이며 이것을 평가하기 위해서 참조열 (Reference String)을 사용한다.

 

 

FIFO 페이지 교체 (FIFO Page Replacement)

---

First-in-First-out으로 가장 간단한 알고리즘이고 가장 먼저 들어온 오래된 페이지를 page out 시킨다.

 

하지만 위 예시에서처럼 15번의 page fault가 발생한다.

 

그리고 더 치명적인 오류가 있는데 그것은 Belady's Anomaly 라는 것이다.

 

 

Belady's Anomaly

---

Belady의 모순은 일반적으로 프레임의 수가 늘어나면 페이지의 부재가 줄어들어야 하는 원리가 적용되지 않는 경우를 말하고 FIFO 알고리즘을 사용할 때에 일어난다.

 

증명하기 위해 직접 구현한 코드는 다음과 같다.

 

 

let pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];

function Belady(N) {
  let memory = [];
  let pageFault = 0;
  for (let page of pages) {
    if (memory.length === N) {
      if (memory.includes(page)) {
        continue;
      } else {
        memory.shift();
        memory.push(page);
        pageFault++;
      }
    } else {
      memory.push(page);
      pageFault++;
    }
  }
  console.log("Memory Size " + N + " Page Faults : " + pageFault);
}
Belady(1);
Belady(2);
Belady(3);
Belady(4);
Belady(5);

 

 

당연하게도 이러한 문제점은 새로운 알고리즘의 탐구를 야기한다.

 

 

최적 페이지 교체 (Optimal Page Replacement)

---

앞으로 가장 늦게 사용될 페이지를 찾아 교체하는 방식이다.

 

그런데 여기서 들었던 의문은 미래에 발생할 페이지 부재를 참조열이 아닌 실제 페이징에서는 어떻게 알고서 최적 페이지 교체를 할 수 있는걸까?

 

책에 그에 대한 해답이 있었는데 실제 구현이 어려운 것이 맞다. 앞으로 참조할 것이 무엇인지를 알아야 하는데 그것을 정확히 알아내는 것은 어렵기 때문에 최적 페이지 교체는 주로 연구의 목적으로 사용된다고 한다.

 

그런데 이것은 SJF 스케줄링의 상황과 비슷하다.

SJF 스케줄링은 다음 프로세스의 CPU 버스트를 알 수 없기 때문에 이전의 버스트를 기반으로 다음 CPU 버스트를 예측한다.

 

 

 

이러한 개념과 비슷한 방식으로 고안된 알고리즘이 LRU 페이지 교체 알고리즘이다.

 

 

 

LRU 페이지 교체 (Least-Recently-Used Page Replacement)

---

LRU 알고리즘 또한 과거를 가까운 미래의 근사치로 보고 가장 오래 사용되지 않은 페이지를 교체 대상으로 삼는다.

 

 

 

그런데 LRU를 구현하기 위해서는 프레임이 언제 마지막으로 사용되었는가를 어떻게 계산을 해낼것인가가 중요하다.

 

이 계산의 과정이 복잡하거나 오래걸린다면 효율성이 떨어질 수 있기 때문에 하드웨어의 지원이 필요하다고 하며 Counter와 Stack으로 지원이 가능하다고 한다.

 

Counter

• 페이지가 참조될 때 system clock의 시간을 copy 해둔다.
• 그리고 victim을 선정해야할 때 가장 작은 값을 가진 것이 가장 오래전에 참조된 것이기 때문에 가장 작은 값을 가진 프레임을 교체시킨다.

Stack

• page number를 stack에 넣는다.
• 그런데 일반적인 stack의 운용과 많이 다르게 중간에 위치한 번호가 참조될 때 그 위치를 stack의 최상단으로 올리는 상황이 있고 후입선출의 원리에서 많이 벗어나 있는 것 같다.

 

LRU 근사 페이지 교체 (LRU-Approximation Page Replacement)

---

LRU는 하드웨어의 지원이 필요하고 많은 시스템은 그 지원을 참조 비트의 형태로 지원한다.

 

 

참조 비트 (Reference Bit)

페이지 테이블 처럼 각 페이지들과 대응되고 운영체제에 의해 0으로 초기화 된다. 페이지가 참조가 되면 하드웨어가 1로 set한다.

 

 

 

2차 기회 알고리즘 (Second-Chance Algorithm)

LRU 근사 페이지 교체 알고리즘의 하나이며 FIFO 교체 알고리즘을 사용하는데 참조 비트를 확인한다.

 

 

 

참조 비트가 0이라면 바로 페이지를 교체하고 비트가 1이라면 비트를 0으로 바꾸면서 한번의 기회를 더 준 다음 다음 프레임으로 넘어간다.

원형 큐의 형태로 구현되어 있기 때문에 페이지를 순회하다 보면 한번의 기회를 받았던 페이지를 다시 만나게 되는데 그때는 참조 비트가 0이기 때문에 페이지 교체의 victim이 되는 것을 피할 수 없다.