이전 글들을 통해 페이징을 이용해서 물리 메모리보다 큰 프로세스를 실행할 수 있다는 것을 배웠다. 그럼에도 물리 메모리의 크기는 한정되어 있다.
따라서
-
기존에 적재된 불필요한 페이지를 선별해 보조기억장치로 내보내기 (페이지 교체)
-
프로세스들에게 적절한 수의 프레임 할당하기 (프레임 할당)
운영체제는 이 두 가지를 수행할 수 있어야 한다!
그 전에 앞서 '요구 페이징' 이라는 것에 대해 알고 가자.
요구 페이징
처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
-> 요구되는 페이지만 적재하는 기법
요구 페이징이 실행되는 과정은 아래와 같다.
- CPU가 특정 페이지에 접근하는 명령어 실행
- 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1), CPU는 페이지가 적재된 프레임에 접근한다.
- 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0), 페이지 폴트 발생
- 페이지 폴트 처리 루틴은 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정한다.
- 다시 1번을 수행한다.
참고) 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행하는 방법을 순수 요구 페이징이라고 한다.
요구 페이징이 안정적으로 작동하려면, 페이지 교체와 프레임 할당 문제를 해결해야 한다.
페이지 교체 알고리즘
요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득 차게 된다.
당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억장치로 내보내야하는데, 어떤 페이지를 내보내야 할까?
이를 결정하는 알고리즘이 페이지 교체 알고리즘이다.
그 전에, 무엇이 좋은 페이지 교체 알고리즘일까?
페이지 폴트가 적은 알고리즘이 효율적인 알고리즘이다.
페이지 폴트가 발생하게 되면, 보조기억장치로부터 필요한 페이지에 접근해야 한다.
예를 들어 특정 페이지 교체 알고리즘을 사용하여 고른 페이지를 스왑 아웃 시켰을 때, 페이지 폴트가 발생하지 않으면 좋은 알고리즘이라고 볼 수 있다.
페이지 폴트의 횟수를 어떻게 알 수 있을까?
페이지 참조열(page reference string)
: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
을 사용할 수 있다.
예를 들어, 어떤 CPU가 [2 2 2 3 5 5 3 3 7] 순으로 페이지를 참조했을 때, 연속된 페이지를 생략한 [2 3 5 7]을 페이지 참조열이라고 한다.
연속된 페이지를 생략할 수 있는 이유?
만약 처음 등장한 5에서 페이지 폴트가 발생하면, 이미 5를 가져왔기 때문에 그 바로 뒤에 등장한 5에 대해서는 일어나지 않는다.
FIFO 페이지 교체 알고리즘
- 가장 단순한 방식
- 메모리에 가장 먼저 올라온 페이지부터 내쫒는 방식
- 오래 머물렀다면 나가라
- 프로그램 실행 내내 사용될 페이지까지 보조기억장치로 내보낼 수 있기 때문에 성능이 좋지는 않다.
페이지 교체에서 발생하는 페이지 폴트만 페이지 폴트로 간주
페이지 참조열 2,3,1,3 까지는 그대로 진행되고, 5를 참조할때는 가장 먼저 들어온 2를 보조기억장치로 내보낸다.
그 다음 2를 참조할때는 또 가장 오래된 3을 내보내고 2를 들여온다.
이런 방식
2차 기회 페이지 교체 알고리즘
- FIFO 알고리즘의 보완책
- 참조 비트 1을 CPU가 한 번 참조한 적이 있을 때, 참조 비트 0을 CPU가 참조한 적이 없을 때로 둔다.
- 참조 비트가 1이면, 참조 비트를 0으로 바꾸고 적재된 시간을 현재 시간으로 두고(가장 최근에 적재된 페이지라고 생각) 다시 맨 끝으로 보냄.
참조 비트 1 -> 한번 더 기회를 주기
참조 비트 0 -> 내쫒기
위의 상황에서 FIFO의 경우 보조기억장치로 보낼 페이지는 3번이지만, 2차 기회인 경우 3번 페이지의 참조비트가 1이기때문에 0으로 바꾼 뒤 가장 최근 페이지로 옮긴다. 그 후 1번 페이지를 내보낸다.
최적 페이지 교체 알고리즘
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
- 가장 낮은 페이지 폴트율을 보장하는 페이지 교체 알고리즘
- 하지만 예측이 어려워서 실제 구현이 어렵다.
CPU에 의해 참조되는 횟수를 고려하여, 자주 사용될 페이지는 메모리에 오래 남기고, 오랫동안 사용되지 않을 페이지는 메모리에 남기지 않는다.
여기서도 마찬가지로 페이지 참조열 2,3,1,3까지는 그대로 진행되고, 5번에서 페이지 폴트가 발생한다. 여기서 앞으로 가장 오래 사용하지 않을 페이지는 1번이니 1번을 내보낸다. 그 다음 4번에서 다시 한번 페이지 폴트가 나타나면 가장 오래 사용하지 않을 페이지인 5번을 내보낸다.
다만 사용하지 않을 페이지 예측이 어렵기 때문에 다른 알고리즘을 평가하는 도구로 사용한다.
LRU(Least Recently Used) 페이지 교체 알고리즘
-
가장 오래 사용하지 않은 페이지를 교체하는 알고리즘
-
최적 페이지 교체 알고리즘에 비해 구현이 쉬움
최적 페이지 교체 알고리즘은 가장 오래 사용되지 않을 페이지를 교체하지만,
LRU는 가장 오래 사용되지 않은 페이지를 교체한다.
예시 자료를 다시 보자. 같은 상황으로 5번 페이지에서 페이지 폴트가 일어나면, 이번에는 가장 오랫동안 사용하지 않았던 페이지인 2번을 내보낸다.
그 다음 2번을 적재할 때 또 페이지 폴트가 일어나는데, 이번에는 1번 페이지를 내보낸다.
스레싱과 프레임 할당
페이지 폴트가 발생하는 이유는 나쁜 페이지 교체 알고리즘을 사용해서도 있지만, 프로세스가 사용할 수 있는 프레임 자체가 적은 경우도 있다.
스레싱(thrashing)은 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 CPU 이용률, 즉 성능이 저해되는 문제를 말한다.
메모리가 작은 컴퓨터에서는 스레싱이 잘 일어나게 된다.
스헤싱을 그래프로 표현하면 다음과 같다.
동시에 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 높아지는 것이 아니라는 것을 알 수 있다.
스레싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
이를 해결하기 위해서는
각 프로세스가 필요로하는 최소한의 프레임 수를 파악하고, 프로세스들에게 적절한 프레임을 할당해 주어야 한다.
그렇다면 프레임 할당하는 다양한 방법에 대해 알아보자.
균등 할당
모든 프로세스들에게 균등하게 프레임을 할당하는 방식, 가장 단순한 할당 방식이다.
당연히 비합리적!
비례 할당
프로세스의 크기를 비례하여 프레임을 할당하는 방식이다.
But, 프로세스가 커도 적은 프레임을 필요로 할 수 있고, 그 반대의 경우도 있다. 결국 프로세스가 필요로 하는 프레임 수는 실행을 해 봐야 안다.
아래 두 방식은 실행을 하는 과정에서 결정하는 방식이다.
작업 집합 모델
프로세스가 실행하는 과정에서 배분할 프레임을 결정하는 방식이다.
스레싱이 발생하는 이유가 빈번한 페이지 교체때문이라면,
CPU가 특정 시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 될 것이다.
작업 집합을 구하려면 프로세스가 어떤 페이지를 참조했는 지, 어떤 시간 간격동안에 참조한 페이지들을 구할 것인지를 알아야 한다.
해당 예시를 보면, t1일 때의 작업 집합은 [5,6,7]이다. 최소 3개의 프레임이 필요하다는 것을 알 수 있다.
t2에서는 [1,2,4,7,8]이다. 최소 5개의 프레임이 t2라는 순간에 필요하다.
페이지 폴트 빈도
- 페이지 폴트율이 너무 높으면 프로세스는 너무 적은 프레임을 가지고 있다.
- 페이지 폴트율이 너무 낮으면 프로세스는 너무 많은 프레임을 가지고 있다.
두 가지 가정에서 생겨난 아이디어로, 프로세스가 실행하는 과정에서 배분할 프레임을 결정하는 방식이다. 페이지 폴트율에 상한선과 하한선을 정하고 그 내부 범위 안에서만 프레임을 할당하게 된다.
이 그래프에서 임의의 상한선과 하한선을 지정하여 프레임이 너무 많거나 적은지를 결정할 수 있도록 한다.
작업 집합 모델과 페이지 폴트 빈도는 동적할당 방식이라고도 부른다.
페이징의 이점과 계층적 페이징
페이징의 대표적인 이점은 외부 단편화를 해결해주는 것도 있지만, 프로세스 간 자원을 공유할 수 있게 해주는 쓰기 시 복사가 있다.
쓰기 시 복사
프로세스는 기본적으로 자원을 공유하지 않는다.
이론적으로, fork를 하면 부모 프로세스가 적재된 별도의 공간에 자식 프로세스가 통째로 복제되어 메모리에 적재된다. 이는 메모리의 낭비이며 프로세스가 생성되는 시간을 지연하기도 한다.
이를 해결하기 위한 방법이 쓰기 시 복사이다.
부모 프로세스와 동일한 자식 프로세스가 복제되어 생성되면,
자식 프로세스는 부모 프로세스와 동일한 프레임을 가리킨다. (쓰기 작업이 없다면 이 상태를 유지)
이 상태에서(부모,자식이 동일한 프레임을 가르키는 상태) 부모 또는 자식 프로세스 중 하나가 페이지에 쓰기 작업을 수행하면, 해당 페이지는 별도의 공간으로 복제된다.
이렇게 하면 프로세스 생성 시간과 메모리가 절약된다.
프로세스 테이블의 크기는 생각보다 작지 않기 때문에 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 낭비이다.
이를 전부 메모리에 유지하지 않으려면 어떻게 해야할까?
계층적 페이징
그 방법은 계층적 페이징으로, 페이지 테이블을 페이징하여 여러 단계의 페이지 페이지를 두는 방식이다.
이렇게 하나의 페이지 테이블이 있다면, 이 테이블 전체를 메모리에 두기보다는 여러 조각으로 쪼갠 뒤 그것들을 가리키는 페이지인 Outer 페이지 테이블만 메모리에 담는 방식이다.
계층적 페이징을 이용하는 곳에서의 논리주소는
[ 바깥 페이지 번호 / 안쪽 페이지 번호 / 변위 ] 로 구성된다.
4단계, 5단계의 계층도 가능하지만 페이지 폴트 발생시 그만큼 메모리를 참조해야하는 횟수도 늘어나기 때문에 항상 좋은 것은 아니다.
출처 한빛미디어 혼자 공부하는 컴퓨터 구조+운영체제
