페이지 교체 알고리즘과 프레임 할당

https://ukgi-dev.tistory.com/179

가상 메모리와 페이징

위의 포스팅에서 페이징의 개념과 페이지 테이블을 통해 어떻게 프레임으로 할당되는지 정리해보았다.

가상 메모리를 사용하는 이유는 작은 물리 메모리보다 큰 프로세스를 실행하기 위함이라고 했다. 그럼에도 물리 메모리의 크기는 한정되어 있다. 따라서 OS는 기존에 메모리에 적재된 불필요한 페이지를 선별하여 스왑 아웃해야하고, 프로세스에게 적절한 갯수의 프레임을 할당해서 페이지를 할당할 수 있어야한다.

 

이번 포스팅에서는 OS의 페이지 관리와 관련된 요구 페이징, 페이지 교체 알고리즘, 프레임 할당에 대해 정리하자.

 

요구 페이징

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하는 것이 아니라 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 한다.

요구 페이징의 기본적인 양상은 다음과 같다.

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1) CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0) 페이지 폴트 인터럽트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

위의 과정을 반복하다보면 페이지로 인해 메모리가 가득 차게 된다. 메모리가 가득 차면 지금 실행에 필요한 페이지만을 남겨두고 나머지를 보조기억장치로 내보내야한다. 이 때 어떤 페이지를 내보낼 것인가 결정하는 것이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은 페이지 폴트를 가장 적게 일으키는 알고리즘이다. 

왜냐하면 페이지 폴트가 자주 일어나면 그만큼 보조기억장치에 자주 접근해서 스왑 인을 해야한다. 메모리에 적재된 페이지에 접근하는 것보다 속도가 느려질 수 밖에 없기 때문이다.

 

그렇기에 페이지 폴트 횟수를 알 수 있어야 한다. 이것은 페이지 참조열을 통해 알 수 있다.

예를 들어 CPU가 아래와 같은 순서로 페이지에 접근했다고 가정하자.

2 2 2 3 5 5 5 3 3 7

 

여기서 연속된 페이지는 이미 메모리에 적재된 페이지이기 때문에 페이지 폴트 횟수에 포함하지 않아도 된다.

즉, 연속된 페이지를 생략한 것이 페이지 참조열이 된다.

2 3 5 3 7

 

FIFO 페이지 교체 알고리즘

그렇다면 페이지 참조열을 바탕으로 FIFO 페이지 교체 알고리즘의 성능에 대해 평가해보자.

FIFO 페이지 교체 알고리즘은 페이지를 교체할 때 가장 오래 머물렀던 페이지를 교체해주는 알고리즘이다.

 

예를 들어 페이지 참조열이 아래 그림과 같고, 사용할 수 있는 프레임이 4개라고 한다면 FIFO 페이지 알고리즘은 그림과 같이 진행된다. 페이지가 부재이고 메모리가 가득 찼으면 가장 오래 머무르고 있는 페이지를 보조기억장치로 빼준다.

FIFO 페이지 교체 알고리즘

 

하지만 자주 참조되는 페이지가 먼저 적재되었다는 이유로 내쫓길 수 있는 문제점이 있다.

이를 보완하고자 2차 기회 페이지 교체 알고리즘이 등장하였다.

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

FIFO 페이지 알고리즘은 가장 오래 머무른 페이지를 내쫓는 알고리즘이다. 여기서 기회를 한번 더 주는 것이 2차 기회 페이지 교체 알고리즘이다. 즉, 가장 오래 머무른 페이지더라도 CPU가 참조한 기록이 있다면 내쫓지않고 기회를 주는 것이다.

 

다섯개의 프레임을 가진 메모리에 페이지가 3, 1, 5, 2, 4 순번으로 적재되어있다.

이때 페이지 6을 새롭게 적재하려면 FIFO 교체 알고리즘은 페이지 3이 가장 오래 적재되었기 때문에 페이지 3을 보조기억장치로 옮겨야한다. 하지만 참조비트가 1이라는 것은 CPU가 참조한 기록이 있다는 것이다. 따라서 페이지 3에게 기회를 한번 더 준다. 참조비트를 0으로 바꾸고 가장 최근에 적재된 페이지로 간주한다. 그 다음 가장 오래 머문 페이지는 페이지 1이다. 페이지 1은 참조비트가 0이므로 해당 페이지를 보조기억장치로 옮기고 페이지 6을 페이지 1이 적재되었던 프레임에 적재하면 된다.

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

최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다.

해당 알고리즘은 가장 낮은 페이지 폴트율을 보장하지만 현실적으로 구현하기 어렵다.

사용 빈도가 가장 낮을 페이지를 결정하는 것, 미래의 일을 예측하는 것은 굉장히 까다롭기 때문이다.

최적 페이지 교체 알고리즘

LRU 페이지 교체 알고리즘

LRU(Least Recenty Used Page Replacement Algorithm)은 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.

 

참고로 캐시 메모리 알고리즘이긴 하지만 LRU 알고리즘 관련 코딩 테스트 문제가 있어 링크를 걸어둔다.

https://school.programmers.co.kr/learn/courses/30/lessons/17680

프로그래머스

---

 

스래싱과 프레임 할당

페이지 교체 알고리즘이 존재하는 이유는 페이지 폴트의 빈도수를 낮추기 위함이다.

사실 페이지 폴트가 자주 발생하는 근본적인 이유는 프로세스가 사용할 수 있는 프레임 수가 적기 때문이다.

프레임 수가 극단적으로 적다면 새로운 페이지에 참조할 때마다 페이지 폴트가 발생할 것이고 페이지 폴트 루틴을 처리하는 동안 CPU의 이용률은 떨어질 수 밖에 없다. 이처럼 지나치게 빈번한 페이지 교체로 인해 CPU 이용률이 낮아지는 문제를 스래싱(thrashing)이라고 한다.

 

이 그래프를 살펴보면 동시에 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 비례해서 증가하는 것이 아님을 나타낸다. 동시에 실행되는 프로세스 수가 늘어나면 그만큼 각 프로세스가 사용할 수 있는 프레임이 적어지기 때문에 페이지폴트가 빈번하게 발생하고 CPU의 이용률이 떨어지게 된다. 그 구간이 바로 스래싱이다.

degree of multiprogramming

 

따라서 OS는 각 프로세스들을 무리없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에게 적절한 수만큼 프레임을 할당할 수 있어야 한다.

 

OS가 프로세스에게 적절한 프레임을 할당하는 방식에는 정적 할당 방식과 동적 할당 방식이 있다.

정적 할당 방식은 모든 프로세스에게 균등한 프레임을 제공하는 균등 할당과 프로세스의 크기에 맞게 프레임을 나눠주는 비례 할당이 있다. 하지만 프로세스가 얼마나 많은 프레임을 필요로 하는지는 프로세스를 직접 실행해야 알 수 있다.

따라서 프로세스가 실행하는 과정에서 프레임을 결정하는 동적 할당 방식이 있고, 여기에는 작업 집합 모델을 사용하는 방식과 페이지 폴트 빈도를 사용하는 방식이 있다.

 

 

작업 집합 모델 기반 프레임 할당 방식은 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합인 작업 집합을 기반으로 빈번한 페이지 교체를 방지하는 방식이다.

그림처럼 시간 간격이 5일 때 t1에서의 작업 집합은 {3, 4, 5} 이다.

이 말의 의미는 이 프로세스가 시간 t1에 최소 세 개의 프레임이 필요하다는 뜻이다.

 

페이지 폴트 빈도 기반 프레임 할당 방식은 다음과 같은 가정에서 생겨난 아이디어이다.

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

 

그림과 같이 페이지 폴트율이 상한선보다 높아지면 그 프로세스는 너무 적은 프레임을 갖고 있다고 볼 수 있다. 이 경우에는 프레임을 더 할당해주면 된다. 반대로 페이지 폴트율이 하한선보다 낮으면 그 프로세스는 너무 많은 프레임을 가지고 있다고 볼 수 있다. 이 경우에는 프레임을 회수한다.