32.페이지 교체와 프레임 할당

1.요구 페이징

 1)정의 : 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한

 페이지만을 메모리에 적재하는 기법.

 -요구페이징 시스템이 안정적으로 작동하려면 필연적으로 두 가지를 해결해야한다.

 -하나는 페이제 교체이고 다른하나는 프레임할당이다.

 *요구 페이징 과정

 

 

 2)순수 요구 페이징(pure demand paging)

  -실행부터 페이지를 메모리에 적재하지 않은 채 무작정 실행하여 연속적인 페이지 폴트를 처리함으로써

   실행 이후의 페이지폴트의 빈도를 떨어뜨리는 기법.

 

2.페이지 교체 알고리즘

 1)정의 및 개요

  -요구 페이징 기법으로 페이즈를 적재하다 보면 메모리는 가득 차게 되고 필요한 페이지를 적재하기

   위해 보조기억장치와의 페이지 교환이 이루어진다.

  -어떤 페이징를 내보내는 것이 최선의 방법인지 결정하는 방법이 페이지 교체 알고리즘이다.

  -페이지를 폴트를 적게 발생하는 것이 좋은 알고리즘으로 평가된다.

  -그것을 알기 위해 페이지 폴트 횟수와 페이지 참조열이 있다.

  2)페이지 참조열(page reference string)

  -페이지 폴트 횟수를 알 수 있는 방법으로 연속된 페이지를 생략한 페이지열이다.

 의 중복된 번호를 제거하여

  로 만든다. 

  -중복된 페이지를 참조하는 것은 페이지 폴트가 일어나지 않기 때문이다.

  -필요한 것은 페이지 폴트의 횟수다.

 

3.FIFO 페이지 교체 알고리즘(First in First out Page Replacement Algorithm)

 1)정의

  -먼저 올라간 페이지부터 메모리에서 방출하는 방식으로 제일 오래된 페이지부터 메모리에 해서 해제된다.

  -단점으로는 프로그램 실행되는 동안 사용되는 페이지 같은 경우 해제되면 안되기에

   오래된 것을 무작정 해제하는 것은 좋지 않다.

4.최적 페이지 교체 알고리즘(optimal page replacement algorithm)

 1)정의

  -CPU에 의해 참조되는 횟수 고려하는 페이지 교체 알고리즘

  -자주 사용되는 페이지는 오래 존재 해야하는 페이지이기에 참조횟수를 고려하는 것.

 

  -어떤 페이지가 사용되지 않을지 예측하기가 쉽지 않기에 가장 페이지 폴트가 적은 알고리즘이지만 

   실제 구현이 어렵다.

 5.LRU 페이지 교체 알고리즘(LRU: Least Recently Used Replacement algorithm)

  1)정의

   -최적 페이지 교체 알고리즘을 비슷하게 구현한 알고리즘.

   -사용되지 '않을' 페이즈를 예측하는 것은 어렵지만 가장 오랫동안 사용되지 '않은' 페이지를

    교체하는 알고리즘 구현.

   -페이지마다 마지막으로 사용된 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.

 

  

 6.스레싱

 1)개요

  -페이지 폴트가 일어나는 이유 중에는 프로세스가 사용할 수 있는 프레임 수가 적어도 발생한다.

  -사용할 수 있는 프레임 수가 많으면 일반적으로 페이지 폴트의 빈도는 감소한다.

  

2)스레싱(thrashing)

   -프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여

   성능이 저해되는 것을 말한다.

3)스레싱의 그래프 표현

 -세로축을 CPU 이용률 가로축을 메모리에서 동시 실행되는 프로세스수(멀티프로그래밍 정도)로 하여

  나타내는 스레싱 그래프.

 -CPU 이용률은 CPU가 일을 하는 작업량의 척도이다.

 -멀티프로그래밍의 정도가 높다면 많은 프로세스가 가동중인 것이다.

 -멀티프로그래밍 정도와 CPU는 비례하여 올라가지만 프로세스를 과하게 늘리면 각 프로세스가

   사용할 수 있는 프레임 수가 적어지고 페이지 폴트가 발생한다.

 -그렇게 되면 CPU의 이용률이 떨어지게 되고 멀티프로그래밍의 값이 높지만 CPU 이용률이 떨어지는

  구간이 스레싱이 일어난다는 표시이다.

 7.프레임 할당 방식

  1)정의

  -스레싱의 발생을 감소하게 하기 위해서는 프레임을 할당하는 방식이 적절해야한다.

  2)균등할당(equal allocation)

  :각 프로세스에 프레임을 균등하게 할당하는 방식. 하지만 프로세스에 크기가 각기 다르기에 필요한 프레임

  을 제공해주기 어럽다.

  3)비례할당(proportional allocation)

   :프로세스의 크기에 비례하여 프레임을 할당하는 방식. 하지만 프로세스가 클지라도 필요한 프레임수가

   맞지 않을 수가 있다.

 *균등할당과 비례할당은 실행과정을 고려하지 않고 프로세스 크기와 물리메모리만을 고려한 방식이란

  점에서 정적할당방식이라고도 한다.

  4)작업 집합 모델(working set model)'

   -작업집합이란 프로세스가 일정기간 동안 참조한 페이지의 집합을 말한다.

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

  5)페이지 폴트 빈도 기반 방식(PFF: Page-Fault Frequency)

  

 

    -페이지 폴트 기반 방식은 위와 같은 전제 조건하에 사용되는 방식이다.

  

   -페이지 폴트율을 세로축 할당한 프레임수를 가로축으로 하고 상한선과 하한선을 정하여

    그 범위 안에서 프레임을 할당하는 방식