[운영체제] 가상 메모리 (3) 페이지 교체 알고리즘과 프로세스 적재 정책

독학사 운영체제 편을 공부하고 정리한 글입니다.

페이지 교체 알고리즘

 

페이지 부재 발생 시, 메모리가 꽉 찼을 경우 스왑 영역으로 내보낼 페이지를 결정하는 알고리즘

메모리에서 앞으로 사용할 가능성이 적은 페이지를 희생자 페이지로 선정한다.

 

페이지 교체 알고리즘 종류

- 이론적 페이지 교체 알고리즘

미래 메모리 접근 패턴을 전부 안다는 가정 하에 대상(희생자) 페이지를 결정한다.

가장 이상적인 교체 알고리즘으로 실제 구현이 불가능하지만 다른 알고리즘과 비교하기 위해 사용한다.

 

- 최적 페이지 교체 근접 알고리즘

LRU/LFU/NUR/2차 기회 페이지 알고리즘

 

- 간단한 알고리즘

FIFO 알고리즘

 

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

• 선입 선출 형식으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 내보낸다.
• 지역성을 전혀 고려하지 않기 때문에 적재가능한 프레임 수를 늘려도 페이지 부재 발생이 오히려 증가할 수 있다.

- 벨래디의 변이현상 : 할당하는 프레임 수가 증가하면 반대로 페이지 부재 비율이 증가하는 현상

 

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

• 가장 오랫동안 사용되지 않은 페이지를 스왑영역으로 내보낸다.
• 카운터나 참조 비트를 사용하여 구현한다.

3) LFU(Lesast Frequently Used) 페이지 교체 알고리즘

• 가장 적게 사용한 페이지를 스왑영역으로 내보낸다.
• 페이지마다 사용한 횟수를 기록해야하는 오버헤드가 있고 추가 공간이 필요하다.

4) NUR(Not Used Recently) 페이지 교체 알고리즘

• 페이지 테이블 엔트리의 참조 비트와 변경 비트만을 가지고 대상 페이지를 결정한다.
• 사용 통계를 기록하기위한 페이지 마다 추가 공간이 필요없다.
• 참조 비트: 페이지에 접근(read/execute)하면 1
• 변경 비트: 페이지가 변경(write/append)되면 1

대상 페이지 결정 우선 순위 (a,m); (0,0) > (0,1) > (1,0) > (1,1)

참조 비트 우선순위가 높다. 최근 변경된 페이지가 참조된 페이지보다 늦게 교체된다.

 

- FIFO 변형 페이지 교체 알고리즘

 

1) 2차 기회 페이지 알고리즘

FIFO 교체 알고리즘에서 페이지 부재 발생없이 접근 성공한 페이지를 큐의 맨뒤로 옮겨 기회를 한번 더 준다.

 

2) 시계 알고리즘

원형 큐를 사용하여 포인터는 대상 페이지를 가르키고 있다.

 

프로세스 정책

 

스래싱

스래싱

잦은 페이지 부재로 페이지 교체로 인한 오버헤드가 발생하여 시스템 효율이 떨어지는 현상이다.

CPU의 유휴 시간이 많아져서 사용률이 낮아진다.

물리 메모리를 늘리거나 멀티 프로그래밍의 정도를 조절하여 스래싱 현상을 방지한다.

 

프레임 할당

프로세스 초기에 개별로 얼마나 많은 프레임을 할당해줄 것 인지에 대한 문제

 

- 정적 할당 방식

균등 할당 vs 비례 할당

• 균등할당: 프로세스마다 균등한 수 만큼 프레임을 할당한다. 메모리가 큰 프로세스는 페이지 부재 발생 확률이 높다.
• 비례할당: 프로세스 크기에 비례하여 프레임을 할당한다. 유동적으로 크기가 변하는 프로세스르 반영하지 못한다.

- 동적 할당 방식

 

작업 집합 모델 (working set model)

• 지역성 이론을 바탕으로 최근에 접근한 프레임을 작업 집합에 포함 시킨다.
• 작업 집합의 크기를 작업 집합 윈도우 (woring set window)라고 하고 페이지 부재 발생을 줄이기 위해 적절한 크기로
• 조절하는 것이 필요하다.
• WSW가 너무 크다면 필요없는 메모리를 프로세스마다 크게 할당하여 메모리 낭비가 되고 너무 작다면 페이지 부재 발생률이 높아진다.

페이지 부재 빈도

페이지 부재 빈도에 따른 프레임 할당

• 프로세스가 필요로하는 페이지 양을 동적으로 결정하는 방법
• 페이지 부재 비율이 상한선을 초과하면 프레임를 더 할당하고 하한선을 초과하면 프레임를 회수하여 메모리 낭비를 줄인다.

페이지 크기에 따른 특징

1) 페이지 테이블 크기

  페이지 크기가 감소하면 페이지 수가 증가하여 페이지 테이블 크기가 증가한다.

2) 내부 단편화

  페이지 크기가 크다면 내부 단편화 발생가능성이 높아진다.

3) 디스크의 입출력 시간

  디스크의 입출력 시간은 페이지를 읽는 횟수에 비례하므로 페이지를 크게하여 읽는 횟수를 줄이는 것이 좋다.

4) 지역성과 페이지 부재 비율

  페이지 크기를 증가시켜야 페이지 부재 빈도를 줄일 수 있다.