1. 요구페이징

1) 요구페이징 개요

• 요구페이징 : 프로세스가 요청할 때 메모리에서 가져오는 방법을 가져오기 정책이라 하는데, 이렇게 사용자가 요구할 때마다 가져오는것을 "요구페이징"이라 한다.

ex) 포토샵 (대형 프로그램)

1. 포토샵은 굉장히 큰 프로그램이기 때문에 모든 프로그램을 메모리에 올리면 비효율적이다.

2. 따라서, 본 프로그램은 메모리에 올리고, 나머지는 "사용자가 필요할 때"마다 가져오는것이 효율적이다. (요구 페이징)

2) 페이지 테이블 엔트리의 구조

• 사용자 프로세스는 물리메모리에 있거나, 스왑영역에 있다.

가. 스왑영역에 있는경우

1. 요구 페이징에 의해 처음부터 스왑영역에 있는 경우

2. 메모리가 꽉차서 스왑아웃 당한 경우

=> 어떤 경우든 페이지 테이블에는 페이지가 어디에 있는지 확인하는 "유효비트"로 확인해야한다.

[ 페이지 테이블 엔트리 구성 - PTE ]

• 페이지번호 / 플래그 비트/ 프레임번호 로 구성

• 플래그 비트

  1) 접근비트(a)
  :페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트
  (참조비트라고도 함)

  2) 변경비트(m)
  : 메모리에 올라온 후 데이터 변경이 있었는지를 체크
  => 변경비트는 데이터가 새로운 값으로 요염됬다고 하여 (더티비트) 라고도 한다.

  3) 유효비트(v)
  : 페이지가 실제 메모리에 있는지를 체크
  => 해당페이지가 메모리에 있는지를 나타내므로 "현재 비트"라고도 한다.

  4) 접근권한비트
  : 읽기, 쓰기, 실행

3) 페이지 부재

페이비 부재란, 사용자가 페이지를 요청했을때, 요구된 페이지가 물리메모리에 있지 않고 스왑영역에 있는것을 말한다.

<조치>

1. 스왑영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신한다.

2. 메모리에 자리가 없다면 프레임 중 하나를 스왑영역으로 내보낸 후에 가져온다.

3. 이때 "교체 알고리즘"을 사용하고 스왑으로 보낼페이지를 대상 페이지라고 한다. (스왑아웃)

• 세그먼테이션과 페이지 부재의 차이
  • 세그먼테이션 오류는 트랩으로 (강제종료) 되고, 페이지 부재는 교체이다.

4) 지역성

지역성이란, 기억장치에 고루 분포되는게 아닌, 특정 영역에 집중되는 성질이다.

⇨ 페이지를 스왑영역으로 보낼 때 "앞으로 사용하지 않을 페이지"를 쫒아내는게 좋다.

⇨ 페이지 교체 알고리즘이 쫒아낸 페이지를 찾을때는 "지역성"을 바탕으로 한다.

1. 공간의 지역성
   : 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거링 ㅔ있는 데이터에 접근할 확률보다 높다.

2. 시간의 지역성
   : 현재를 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높다.

3. 순차적 지역성
   : 여러 작업이 순서대로 진행되는 경향이 있는것을 의미
   (특별할 경우라 잘보지는 않는다.)

2. 페이지 교체 알고리즘

1) 페이지 교체 알고리즘의 개요

페이지 교체 알고리즘이란 스왑영역으로 보낼 페이지를 결정하는 알고리즘

2) 무작위 페이지 알고리즘

가장 간단하며 특별한 로직이 없이 무작위로 대상페이지를 선정한다.

3) FIFO 페이지 교체 알고리즘

가장 오래된 페이지를 대상페이지로 선장한다.

• 선입선출
• 메모리에 올라온 시간만을 고려한다.
• 자주 사용되는 페이지가 스왑아웃 될 수도 있다.

4) 최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 미리 살펴보고, 가장 멀리있는 페이지를 대상페이지로 선정한다.

• 가장 이상적이지만 구현 불가능하다.

• 미래의 접근 패턴을 알야하기 때문에 불가능하다.

5) LRU 페이지 교체 알고리즘

• 최적 근접 알고리즘 중 하나

최근 최소 사용페이지 교체 알고리즘

• 메모리에 올라온 후 가장 오랫동안 "사용되지 않은" 페이지를 지정한다.

<구현 방법>

가. 페이지 접근 시간에 기반한 구현

• 페이지에 접근한 시간을 기록하여 구현

• 연산이 이루어진 시간을 기준으로 페이지에 접근한 지 가장 오래된 페이지를 교체
  

​

나. 카운터에 기반한 구현

• 시간이 아닌 카운터 숫자로 구현

• 두 방법 모두 추가적인 멤리 공간을 필요로 해 사용자가 사용할 수 있는 공간이 낭비됨

​

다. 참조 비트 시프트 방식

• 각 페이지에 일정 크기의 참조 비트를 만들어 사용

• 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀜

• 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동

• 참조 비트 중 가장 작은 값(가장 오랫동안 접근하지 않은 페이지)을 대상 페이지로 선정
  

6) LFU 페이지 교체 알고리즘

사용된 횟수가 가장 적은 페이지를 대상페이지로 지정

• 최소 빈도 사용 알고리즘

• 사용빈도를 체크하는 메모리 필요

• 사용빈도가 같으면 FIFO

7) NUR 페이지 교체 알고리즘

• 불필요한 공간방비를 해결한 알고리즘

  최근 미사용 페이지 교체 알고리즘

8) FIFO 변형 알고리즘

1. 2차 기회 페이지 교체 알고리즘

   • 큐를 이용하여 구현

   • 페이지 부재없이 성고하면 해당페지를 큐의 맨 뒤로 이동(추가 기회 부여)

2. 시계 알고리즘

   • 원형 큐를 이용

   • 참조비트(1bit) 부여

   • 포인터 사용, (포인터가 한 방향으로 돈다)
     

3. 스레싱과 프레임 할당

1) 스레싱

스레싱이란, 메모리가 꽉찬 후 "잦은 페이지 부재:로 작업이 머춘것 같은 상태를 말한다.

2) 물리메모리의 크기와 스레싱

• 멀티 프로그래밍 정도 : 동시에 실행하는 프로그램의 수

• 멀티 프로그래밍 정도가 너무 높으면 스레싱이 발생한다.
  

• 스레싱 발생 시점: 메모리가 꽉 차 cpu가 작업하는 시간보다 교체 작업이 빈번해져 cpu가 작업할 수 없는 시점

• 물리 메모리의 크기를 늘리면 스레싱 발생 시점이 늦춰져 프로세스의 원만한 실행 가능

• 작업을 하는데 충분한 크기가 되면 크기를 더 늘려도 속도에 영향을 미치지 않음

3) 스레싱과 프레임 할당

• 실행중인 프로세스에 프레임을 얼마나 나누어주느냐에 따라 시스템 성능이 달라진다.

• 프레임을 할당하는 방식은 정적할당과 동적할당 2가지가 있다.

4) 정적 할당

실행 초기에 프레임을 나누어준 후 그 크기를 고정하는 것

• 균등할당, 비례할당 2가지 방법이 있음

1. 균등할당
   : 모든 프로세스에 동일하게 할당한다.

(단점)
: 크기가 큰 프로세스의 경우 필요한 만큼 할당할수 없다. ⇨ 페이지 부재 발생

2. 비례할당
   : 프로세스 크기에 비례하여 프레임을 할당하는 방식

(단점)
: 사용하지 않을 메모리를 미리 확보하여 메모리가 낭비된다.

5) 동적 할당

시시가각 변하는 요청을 수용하는 방식

가. 작업집합 모델 (지역성 이론이 바탕)

• 가장 최근에 접근한 프레임이 이후에도 또 참조도리 가능성이 크다.

• 최근 일정시간동안 참조된 페이지들을 집합으로 만든다.(WS)

• 워크셋(WS) : 작업집합 모델에서 물리메모리에 유지할 페이지의 크기

  • 워크셋의 크기는 얼마나 자주 갱신할 것인가를 의미한다.

• 작업집합 윈도우 : 작업집합에 포함되는 페이지의 범위

⇨ 작업집합 윈도우의 크기에 따라 성능이 달라진다.

---

나. 페이지 부재 빈도

• 작업집합 모델의 단점

1. 충분한 페이지를 할당하지 않으면 작업집합에 있는 페이지를 물리메모리에 유지하기 힘들다.

2. 작업집합 모델은 프로세스의 성능을 높이지만 UP / 스레싱은 해결하지 못한다. (스레싱 해결 불가)

• 페이지 부재 빈도

페이지 부재 빈도란, 페이지부재 횟수를 기록하여 상한선과, 하한선을 설정해 프레임을 추가로 할당할 것인지, 프레임을 회수할 것인지를 결정한다.