가상메모리④ - 페이지 교체 알고리즘과 프레임 할당 기법, 스래싱(Thrashing)

페이징을 통해 물리 메모리보다 큰 프로세스를 실행할 수 있지만

그럼에도 물리 메모리의크기는 한정되어 있다.

 

따라서 운영체제 입장에서는 두 가지 문제를 해결해야 한다.

• 기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내고 ⭢ 페이지 교체 알고리즘
• 프로세스들에게 적절한 수의 프레임을 할당해야한다. ⭢ 프레임 할당

---

요구 페이징(Demand Paging)

• 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
• 요구되는 페이지만 적재하는 기법

* 페이지 폴트(page fault) : 유효 비트가 0인 페이지에 접근하려고 하면? 페이지 폴트(page fault)라는 인터럽트가 발생

* 순수 요구페이징(Pure Demand Paging) : 아무런 페이지도 메모리에 적재하지 않은 채 실행부터 하는 것.

 

요구 페이징이 시스템이 안정적으로 작동하려면 해결해야 할 문제?

• 페이지 교체
• 프레임 할당

---

페이지 교체 알고리즘

요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득차게 된다

당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야 한다.

 

이때 어떤 페이지를 내보낼지 결정하는 방법이 페이지 교체 알고리즘

 

어떤 페이지 교체 알고리즘이 좋은 알고리즘일까?

• 페이지 폴트(Page Fault)가 적은 알고리즘 
  • 페이지 폴트가 발생하면 보조기억장치에 접근해야 해서 성능 저하
  • 즉, 보조기억장치로 내보내야 할 페이지를 잘못 골랐다
• 그렇다면 페이지 폴트 횟수는 어떻게 알 수 있을까?
  • 페이지 참조열(page reference string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
    • 2 2 2 3 5 5 5 3 3 7
    • >> 2 3 5 3 7

---

❶ FIFO 페이지 교체 알고리즘

• 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
• 가장 단순한 방식
• "오래 머물렀으면 나가라!"

• 단점
  • 프로그램 실행 초기에 잠깐 실행될 페이지는 괜찮지만
  • 초기에 적재되었지만 프로그램 실행 내내 사용될 페이지는 먼저 적재되었다고 내쫓아선 안되기 때문

---

❷ 2차 기회 (second-chance) 페이지 교체 알고리즘

• FIFO 페이지 교체 알고리즘의 보완책. 
• 기본적으로 FIFO로 진행.
• 하지만 참조비트가 1인 경우 방문한 적이 있다는 것이므로 바로 내쫓지 않고 적재된 시간을 현재 시간으로 바꾸어 맨 끝으로 보내게 된다. (즉, 가장 최근에 적재된 것으로 간주) 
  • 참조 비트 1: CPU가 한 번 참조한 적이 있는 페이지
    • 한 번 더 기회를 준다. (참조 비트 0으로 초기화 후 적재 시간을 현재 시간으로 설정)
  • 참조 비트 0: CPU가 참조한 적이 없는 페이지
    • 내쫓기

---

❸ 최적 페이지 교체 알고리즘

• CPU에 의해 참조되는 횟수를 고려
  • 메모리에 오래 남아야 할 페이지는 자주 사용될 페이지
  • 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지
   
• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘

FIFO에 비해 페이지 교체 빈도가 확연히 낮다

 

• 단점
  • 가장 낮은 페이지 폴트율을 보장하지만, 실제 구현이 어렵다
  • "앞으로 오랫동안 사용되지 않을 페이지? 어떻게 예측하지?"
  • 다른 페이지 교체 알고리즘 성능을 평가하기 위한 하한선으로 간주 (즉, 이론적 방법으로 생각)

---

❹ LRU(Least-Recently-Used) 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 너무 이상적, 비슷하게는 만든 것이 이것

• 최적 페이지 교체 알고리즘: 가장 오래 사용되지 않을 페이지 교체
• LRU 페이지 교체 알고리즘: 가장 오래 사용되지 않은 페이지 교체
  • "최근에 사용되지 않은 페이지는 앞으로도 사용되지 않지 않을까?"

 

기타 페이지 교체 알고리즘

 

이외에도 많은 페이지 교체 알고리즘들이 있다.

ex. LRU 페이지 교체 알고리즘의 파생 알고리즘 등

---

프레임 할당과 스래싱 (Thrashing)

• 페이지 폴트가 자주 발생하는 이유
  • 나쁜 페이지 교체 알고리즘을 사용해서
  • 프로세스가 사용할 수 있는 프레임 자체가 적어서

---

스래싱(Thrashing)

 

프로세스가 실행되는 시간보다 페이징(페이지 교체)에 더 많은 시간을 소요하여 성능(CPU 이용률)이 저해되는 문제.

지나치게 페이지 교체를 자주해서 CPU 성능이 현저하게 떨어지는 것.

CPU 이용률 = CPU가 얼마나 쉴 새없이 일을 하고 있는지, 멀티 프로그래밍의 정도: 메모리에 동시에 실행되는 프로세스의 수

그래프에서,

동시에 실행되는 프로세스의 수를 늘린다고 CPU의 이용률이 높아지는 것은 아니다. (비례하는 것은 아니다)

 

CPU 이용률이 현저히 낮아진 시점이 스레싱이 발생한 시점!

페이지 폴트가 너무 많이 발생해서 막상 실행해야할 프로그램은 실행하지 못하는 상태

 

• 스래싱이 발생한 이유
  • 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
• 스래싱 해결 방법
  • 각 프로세스가 필요로하는 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다

---

정적 할당 방식 

프레임의 크기 등만 고려한 방식.

---

① 균등할당 (equal allocation)

가장 단순한 할당 방식.

모든 프로세스들에게 균등하게 프레임을 할당하는 방식.

 

ex) 300프레임, 10개 프로세스 >> 30개씩

 

단점: 프로세스의 크기가 각각 다를텐데 천편일률적으로 동일하게 할당하는 것은 비합리적

---

② 비례할당(proportional allocation)

프로세스의 크기를 고려하여, 크기에 비례하여 프레임을 할당하는 방식.

 

한계)

크기가 큰 프로세스인데 막상 실행해보니 많은 프레임을 필요로 하지 않는다거나,

크기가 작은 프로세스인데 막상 실행해보니 많은 프레임을 필요로 하면?

 

결국 프로세스가 필요로하는 프레임 수는 실행해봐야 알기 때문!

---

동적 할당 방식

① 작업 집합 모델 (working set model)

프로세스가 실행하는 과정에서 프레임 결정.

 

스래싱(Thrashing)이 발생하는 이유는 빈번한 페이지 교체 때문.

⭢ 그렇다면 CPU가 특정 시간 동안 주로 참조한 페이지 개수(작업 집합)만큼만 프레임을 할당하면 된다.

 

*참조지역성의 원리: 비슷한 구역을 참조한다.

 

'프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하며 빈번한 페이지 교체를 방지

• 작업 집합: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
  • 작업 집합을 구하려면? - 프로세스가 참조한 페이지 / 시간 간격이 필요하다.

---

② 페이지 폴트 빈도 기반의 프레임 할당

프로세스가 실행하는 과정에서 배분할 프레임 결정

 

두 개의 가정에서 생겨난 아이디어

• 1.페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다
• 2.페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다

 

 

즉, 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식