운영체제(9) : 가상 메모리 관리

📍목차

---

1. 요구 페이징
2. 페이지 교체 알고리즘
3. 스레싱과 프레임 할당

1️⃣ 요구 페이징

---

이전 포스팅에서는 가상 메모리 기법에서의 메모리 배치 정책에 대해 살펴봤다.
본 포스팅에서는 가져오기 정책과 재배치 정책에 대해 살펴보자.

가져오기 정책은 프로세스가 필요로 하는 데이터를 언제 메모리에 적재할 것인가를 결정하는 정책이다.

✔️ 요구 페이징 개념

요구 페이징이란, 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 의미한다.

즉, 프로세스를 구성하는 모듈을 전부 올려놓는 것이 아닌 사용자가 필요로 할 때마다 가져오는 것이다.
프로세스의 일부만 메모리로 가져오는 이유는 아래와 같다.

1. 메모리를 가능한 적게 사용해 효율적으로 관리하기 위함이다.
2. 용량이 큰 프로세스를 전부 메모리에 적재하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 응답 속도를 향상한다.

추가로 이러한 요구 페이징과는 반대로, 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식을 사용하는 대표적인 곳이 캐시다.

✔️ 페이지 테이블 엔트리의 구조

아래는 페이지 테이블의 한 행을 의미하는 페이지 테이블 엔트리의 구성을 나타낸다.

비트	역할
접근 비트	해당 메모리에 읽기나 실행 작업을 했다면 1
변경 비트	메모리에 올라온 후 변경된 적이 있으면 1
유효 비트	페이지가 스왑 영역에 있으면 1
읽기 비트	읽기 권한이 있으면 1
쓰기 비트	쓰기 권한이 있으면 1
실행 비트	실행 권한이 있으면 1

메모리가 꽉 차서 어떤 페이지를 스왑 영역으로 옮길지 선택할 때 접근 비트와 변경 비트를 사용한다.
이에 대해서는 아래쪽에서 살펴보자.

가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다.
따라서 페이지 테이블에는 페이지가 메모리에 있는지 스왑 영역에 있는지 표시해야 하는데, 이때 유효 비트를 사용한다.

유효 비트가 0일 때는 페이지가 메모리에 있으므로, 주소 필드에 물리 메모리의 프레임 번호가 저장된다.
유효 비트가 1일 때는 페이지가 스왑 영역에 있으므로, 주소 필드에 스왑 영역 내 페이지 주소가 저장된다.

✔️ 페이지 부재

프로세스가 페이지를 요청했을 때, 페이지가 메모리에 없는 상황을 페이지 부재라고 한다.

프로세스가 페이지 3을 요청한 경우, 페이지 테이블 엔트리 3의 유효 비트가 1이므로 스왑 영역의 0번에 있다.
페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.

페이지 부재가 발생했을 때 물리 메모리에 빈 공간이 있다면, 스왑 영역의 페이지를 빈 공간으로 가져온 후 페이지 테이블을 갱신함으로써 원하는 데이터에 접근할 수 있게된다.

이번에는 물리 메모리에 빈 공간이 없는 경우를 살펴보자.

사용하려는 페이지가 스왑 영역에 있으나 메모리에 빈 영역이 없는 경우, 메모리에 적재된 페이지 중 하나를 스왑 영역으로 내보내야 한다.

이때 스왑 영역으로 내보낼 페이지를 대상 페이지라고 하며,
대상 페이지를 결정하는 알고리즘을 페이지 교체 알고리즘이라고 한다. 이어서 페이지 교체 알고리즘에 대해 알아보자.

2️⃣ 페이지 교체 알고리즘

---

페이지 교체 알고리즘이란, 물리 메모리에서 스왑 영역으로 내보낼 페이지를 결정하는 알고리즘이다.
앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 성능을 향상한다.

페이지 알고리즘의 종류

페이지 교체 알고리즘의 종류와 특징을 정리한 표다.

FIFO 변형 방식에는 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다.

각 알고리즘에 대해 하나씩 알아보기 전에, 페이지 교체 알고리즘의 성능을 평가하는 기준을 간단히 언급해보자.
평가 기준은 다양하게 존재한다. 두 알고리즘의 페이지 부재 횟수를 비교할 수도 있고, 페이지 요청 후 실제 작업에 들어가기까지의 평균 대기 시간을 비교할 수도 있고, 전체 작업에 걸리는 시간을 비교할 수도 있다.

본 포스팅에서는 같은 메모리 접근 패턴을 사용해 페이지 부재 횟수와 페이지 성공 횟수를 비교한다.
메모리 접근 패턴은 A B C D B A B A C A 순으로 고정한다.
이제 각 알고리즘에 대해 자세히 알아보자.

🔑 무작위 페이지 교체 알고리즘

가장 간단한 방식으로, 말그대로 대상 페이지를 기준없이 무작위로 선정한다.
대부분 프로세스의 메모리 접근 패턴은 공간적 지역성을 가지나, 무작위 알고리즘은 이러한 지역성을 전혀 고려하지 않는다.
따라서 자주 사용하는 페이지가 대상 페이지로 선정될 수 있으며, 성능이 좋지 않아 사용되지 않는다.

🔑 FIFO 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정한다.

선입선출 구조를 가지며, 큐를 통해 구현한다.

메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입된다.
즉, FIFO 알고리즘은 먼저 들어온 페이지를 항상 스왑 영역으로 옮긴다.

이는 시간의 지역성을 고려한 방식이나, 메모리에 올라온 지 오래됐더라도 자주 사용하는 페이지가 있다.
또한 메모리에 늦게 올라왔더라도 조금 사용되는 페이지도 있다.
위 사진을 보면 B 페이지는 6번에서 쫓겨났다가 7번에서 다시 메모리에 적재된다.

이러한 FIFO 알고리즘은 성능이 떨어지기 때문에, 이를 개선한 것이 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이다.

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

2차 기회 페이지 교체 알고리즘은 FIFO와 같이 큐를 사용하나, 특정 페이지가 페이지 부재 없이 성공할 경우 대상 페이지에서 제외한다.

메모리 접근 순서 5번을 보면 페이지 B가 페이지 부재 없이 성공하여 큐의 맨 뒤로 옮겨지는 것을 알 수 있다.

2차 기회 페이지 교체 알고리즘은 FIFO 방식보다 성능이 좋으나, 큐 유지 비용이 높고 큐의 중간에 있는 값을 맨 뒤로 이동하는 작업이 추가된다는 단점이 있다.

🔑 시계 알고리즘

시계 알고리즘은 원형 큐를 통해 구현되며, 대상 페이지를 가리키는 포인터가 원형 큐를 순회한다.
페이지 참조에 성공하면 포인터는 해당 페이지를 건너뛰고, 이를 위해 참조 비트를 사용한다.

참초 비트의 초기값은 0이고, 메모리 내 페이지를 성공적으로 참조하면 1로 변경된다.
시계 알고리즘은 포인터가 가리키는 페이지를 스왑 영역으로 쫓아낸 후 포인터를 밑으로 이동하는데,
이때 참조 비트가 1인 페이지는 건너뛴다. 이후 참조 비트를 다시 0으로 변경한다.
이는 2차 기회 페이지 교체 알고리즘처럼 기회를 한 번만 더 주기 위함이다.

🔑 최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 앞으로 사용하지 않을 페이지를 스왑아웃 한다.
메모리가 앞으로 사용할 페이지를 미리 살펴보고, 사용 시점이 가장 멀리 있는 페이지를 대상 페이지로 선정한다.

메모리 접근 순서 4번에서 페이지 C를 사용하는 시점이 가장 멀기 때문에, C를 스왑 영역으로 내보낸다.

그러나 미래의 접근 패턴을 아는 것은 불가능하기 때문에, 실제로는 구현이 불가능하다.
이에 대한 대안으로 구현이 가능하며 최적 페이지 교체 알고리즘에 근접하는 성능을 보이는 알고리즘이 LRU, LFU, NUR 알고리즘이다.

🔑 LRU(Least Recently Used) 알고리즘 : 최근 최소 사용

LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 대상 페이지로 선정한다.

LRU 알고리즘을 구현하는 세 가지 방식에 대해 알아보자.

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

가장 간단한 형태로, 페이지에 접근한 시간을 기록한다.

메모리 접근 순서 4번을 보면, 접근한 지 가장 오래된 페이지 A번이 스왑아웃되는 것을 볼 수 있다.
일반적으로 FIFO 알고리즘보다 성능이 우수하나, 접근 시간 기록을 위한 추가 메모리 공간이 요구된다는 단점이 있다.

2. 카운터에 기반한 구현

페이지 접근 시간에 기반한 구현에서는 접근 시간을 기록했다면, 카운터에 기반한 구현은 전역 카운터를 사용한 카운터 값을 기록한다.
즉, 대상 페이지를 선정할 때 카운터 값이 가장 작은 값을 선정하게 된다.
카운터에 기반한 구현 역시 카운터 값 기록을 위한 추가 메모리 공간이 요구된다는 단점이 있다.

3. 참조 비트 시프트 방식

참조 비트 시프트 방식은, 각 페이지의 일정 크기의 참조 비트를 만들어 사용한다.
페이지에 접근할 때마다 참조 비트를 1로 변경하고, 주기적으로 오른쪽으로 한 칸씩 이동한다.

즉, 참조 비트 중 가장 작은 값을 대상 페이지로 선정하게 된다.
위 사진에서는 페이지 C가 대상 페이지로 선정된다.

비록 1B이기는 하지만, 여전히 추가 메모리 공간이 요구된다.

결론적으로, LRU 알고리즘의 단점은 시간이나 참조 비트를 위한 메모리가 추가로 필요하다는 것이다.

🔑 LFU(Least Frequently Used) 알고리즘 : 최소 빈도 사용

LFU 알고리즘은 지금까지 사용한 횟수가 가장 적은 페이지를 대상 페이지로 선정한다.

즉, 페이지가 사용될 때마다 사용 횟수를 기록한다.

일반적으로 LRU 알고리즘과 성능이 유사하며, 마찬가지로 페이지 접근 횟수 표시를 위한 메모리 추가 공간이 요구된다는 단점이 있다.

🔑 NUR(Not Used Recently) 알고리즘 : 최근 미사용

NUR 알고리즘은 참조 비트와 변경 비트를 통해 최근 사용이 되지 않은 페이지를 대상 페이지로 선정한다.

NUR 알고리즘은 LRU, LFU 알고리즘과 성능이 유사하나 불필요한 공간 낭비 문제를 해결했다.

LRU, LFU 알고리즘은 페이지가 사용된 시간 혹은 횟수를 정확히 기록했다면,
NUR 알고리즘도 페이지 접근 이력을 고려하지만 정확할 필요는 없다라는 이론에 기반한다.

즉, 90번 접근한 페이지와 92번 접근한 페이지 중 어떤 페이지를 쫓아내도 상관없다고 판단한다.
정확한 값을 유지하는 것은 메모리만 낭비할 뿐 의미가 없으므로, 추가 비트 2개만 사용하여 미래를 추정한다.

• 참조 비트 : 페이지에 접근하면 1이 된다. (read, excute)
• 변경 비트 : 페이지가 변경되면 1이 된다. (write, append)

모든 페이지의 초기 상태는 (0, 0)이며, 페이지에 '접근'하면 (1, 0)이 된다.
이어서 페이지에 '변경'이 발생하면 (1, 1)이 되는 형태다.

NUR 알고리즘에서 대상 페이지를 선정하는 순서는 아래와 같다.

참조 비트	변경 비트
0	0
0	1
1	0
1	1

즉, 접근과 변경이 모두 없는 페이지를 1순위로 쫓아내며, 접근과 변경이 모두 있는 페이지는 최대한 쫓아내지 않는다.
만일 모든 페이지가 (1, 1)이 되면, 페이지 비트를 모두 (0, 0)으로 초기화한다.

위 사진을 보면 처음 메모리에 올라온 페이지의 비트는 (0, 0)이고, 페이지에 접근하면 (1,0)이 되어 대상 페이지에서 제외되는 것을 알 수 있다.
만일 (0, 0)인 페이지가 여러 개라면, 가장 위에 있는 페이지가 대상 페이지가 된다.

NUR 알고리즘은 추가 2bit만으로 우수한 성능을 보이고, 쉽게 구현할 수 있어 가장 많이 사용되는 알고리즘이다.

3️⃣ 스레싱과 프레임 할당

---

운영체제는 물리 메모리의 공간이 부족할 때, 프로세스에 프레임을 어떻게 나누어 주느냐에 대한 문제를 맞닥뜨린다.
프레임 할당과 관련한 이론과 방법에 대해 알아보자.

✔️ 스레싱

스레싱이란, 하드디스크의 입출력이 너무 많아 페이지 부재로 인해 작업이 멈춘 듯한 상태를 의미한다.

메모리가 꽉 찬 후 새로운 프로그램을 메모리에 올리기 위해 기존 프로그램을 스왑아웃하는 빈도가 잦아질 때 발생한다.

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

동시에 실행하는 프로그램의 수가 많아지면 스레싱이 발생하게 된다.
프로그램의 수가 증가할수록 CPU 사용률이 증가하다가, 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑인과 스왑아웃 작업이 더 많아져 CPU가 작업할 수 없는 상태에 도달하게 된다. 이를 스레싱 발생 지점이라고 한다.

• 물리 메모리의 크기를 늘리면 왜 컴퓨터가 빨라질까?
  프로세스가 필요로하는 메모리보다 물리 메모리가 작다면 스레싱 발생 지점에 더 빠르게 도달하기 때문이다.

• 그렇다면 물리 메모리의 크기를 무한정 늘리면 속도도 끝없이 빨라질까?
  그렇지 않다. 512MB에서 4GB로 늘리는 경우, 512MB의 크기로는 여러 프로그램을 적재하기에 많이 부족해 4GB로 늘림으로써 스왑 작업이 크게 줄어든다.
  그러나 4GB의 크기라면 충분히 여러 프로그램을 적재할 수 있어 16GB로 늘린다고 해서 스왑 작업이 크게 줄어들지 않기 때문이다.

스레싱과 프레임 할당

스레싱은 각 프로세스에 프레임을 얼마나 주느냐에 따라 발생 지점이 달라진다.
어떤 프로세스에 너무 많은 프레임을 할당하면 메모리가 낭비되고, 너무 적은 프레임을 할당하면 페이지 부재가 잦아진다.

따라서 남은 프레임을 프로세스에 나누어 주는 정책이 필요한데, 크게 정적 할당과 동적 할당으로 구분된다.

✔️ 정적 할당

정적 할당 방식은 초기에 프레임을 나누어 준 후, 그 크기를 고정한다.

정적 할당 방식에는 균등 할당 방식과 비례 할당 방식이 있다.

균등 할당 방식

균등 할당 방식은 프로세스의 크기와 상관없이 같은 수의 프레임을 할당한다.

프로세스 A, B, C가 각각 6개, 3개, 9개의 프레임을 요구한다고 가정하자.

균등 할당 방식의 경우, 프로세스 B와 같이 크기가 작다면 프레임이 남게되어 메모리 낭비가 발생하고,
프로세스 C와 같이 절반도 못 미치는 프레임을 할당받게 될 수도 있다.

비례 할당 방식

비례 할당 방식은 프로세스의 크기에 비례하여 프레임을 할당한다.

비례 할당 방식에서 각 프로세스가 프레임을 할당받는 방식은 아래와 같다.

• 할당 가능한 프레임 수 : $12$
• 전체 프로세스의 프레임 수 : $6 + 3 + 9 = 18$
• 프로세스 A : $6 \times 12 \div 18 = 4$
• 프로세스 B : $3 \times 12 \div 18 = 2$
• 프로세스 A : $9 \times 12 \div 18 = 6$

그러나 비례 할당 방식은 여전히 아래와 같은 두 가지 문제점이 있다.

1. 프로세스 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못한다.
   동영상 플레이어와 같이 프로그램 자체의 크기는 작지만 동영상의 크기가 큰 경우, 플레이어보다 훨씬 큰 메모리를 필요로 한다.
2. 사용하지 않을 메모리를 처음부터 미리 확보해 공간을 낭비한다.
   요구 페이징 방식에서는 처음부터 프로세스의 모듈을 모두 메모리에 적재하지 않는다. 당장 필요하지 않는 프레임으로 인해 메모리가 낭비되기 때문이다.

✔️ 동적 할당

이와 같이 실행 중에 따라 달라지는 요청을 수용하기 위해 동적 할당 방식을 사용한다.

동적 할당 방식은 프로세스의 요구에 따라 할당하는 프레임 수를 변화시킨다.

동적 할당 방식에는 작업집합 모델과 페이지 부재 빈도를 사용하는 방식이 있다.

작업집합 모델

작업집합 모델은 최근 일정 시간 동안 참조된 페이지들을 물리 메모리에 유지한다.

이는 가장 최근에 접근한 프레임이 이후에도 참조될 가능성이 높다는 지역성 이론을 바탕으로 한다.

물리 메모리에 유지할 페이지의 수를 작업집합 크기라고 하는데, 여기선 5라고 가정하자.
작업집합에 포함되는 페이지의 범위를 작업집합 윈도우라고 한다. 여기선 10으로 가정하자.

작업집합에는 현재 시간부터 가까운 페이지부터 삽입된다.
따라서 $t1$ 시점에서는 작업집합이 {1, 7, 5, 2, 3}이 되고, $t2$ 시점에는 {2, 3, 4, 1, 7}이 된다.

작업집합 모델에서는 작업집합 윈도우의 크기에 따라 실행 성능이 달라진다.
너무 크면 필요없는 페이지가 메모리에 남고, 너무 작으면 필요한 페이지가 스왑 영역으로 옮겨지게 된다.

작업집합 모델의 한계

작업집합 모델은 프로세스의 성능을 높일 수 있으나, 스레싱 문제를 해결하지는 못한다.
어떤 프레임을 물리 메모리에 유지해야 하는지 알 수 있을 뿐, 프레임을 얼마나 할당할지는 알 수 없기 때문이다.

페이지 부재 빈도

페이지 부재 빈도는 페이지 부재 비율이 상한선과 하한선 사이로 유지되게끔 프레임을 할당한다.

페이지 부재 비율을 계산하는 방식으로 페이지 부재 비율의 상한선과 하한선을 결정한다.

페이지 부재 비율이 상한선을 초과하면, 할당한 프레임이 적다고 판단하여 프레임을 추가 할당한다.
반대로 페이지 부재 비율이 하한선보다 내려가면, 메모리가 낭비된다고 판한하여 프레임을 회수한다.

프로세스가 처음 시작될 때는 할당량을 예측하기 어려우므로, 프로세스를 실행하면서 적정 페이지 할당량을 조절한다.

✔️ 전역 교체와 지역 교체

앞서 다양한 종류의 페이지 교체 알고리즘을 살펴보았다.
페이지 교체 알고리즘에 따라 페이지를 교체할 때는 전역 교체 혹은 지역 교체 방식을 적용한다.

• 전역 교체 : 전체 프레임을 대상으로 페이지 교체 알고리즘을 적용한다.
  • 프로세스 A의 프레임을 스왑인 하기 위해 프로세스 B의 프레임이 스왑아웃 될 수 있다.

• 지역 교체 : 현재 실행 중인 프로세스의 프레임을 대상으로 페이지 교체 알고리즘을 적용한다.
  • 프로세스 A의 프레임을 스왑인 하기 위해선 프로세스 A의 프레임이 스왑아웃 되어야 한다.

NUR 알고리즘을 적용한 상태에서 전역 교체와 지역 교체 방식을 비교해보자.
물리 메모리에 없는 A4 프레임을 스왑에서 가져오고자 하는 상황이다.

전역 교체 방식에서는 물리 메모리의 모든 프레임을 대상으로 대상 페이지를 결정한다.
따라서 참조 비트와 변경 비트가 (0, 0)인 C2 프레임이 대상 페이지가 된다.

지역 교체 방식에서는 동일한 프로세스인 프로세스 A의 프레임을 대상으로 대상 페이지를 결정한다.
따라서 참조 비트와 변경 비트가 (0,1)인 A2 프레임이 대상 페이지가 된다.

지역 교체 방식의 장단점

지역 교체 방식의 장점은, 자신에게 할당된 프레임의 전체 수가 동일하므로 페이지 교체가 다른 프로세스의 영향을 미치지 않는다는 점이다.
다른 프로세스의 프레임을 빼앗음으로써 해당 프로세스는 스레싱이 발생할 수 있기 때문이다.

지역 교체 방식의 단점은, 프로세스 내에서 자주 사용되는 페이지가 스왑 영역으로 옮겨질 수 있다는 점이다.
이로 인해 자주 사용되는 페이지가 지속적으로 교체되어 스레싱이 발생할 수 있다.

지역 교체 방식은 다른 프로세스의 스레싱을 줄일 수 있으나, 자기 자신 프로세스의 성능이 저하될 수 있다.
따라서 전체 시스템의 입장에서는 전역 교체 방식이 더 효율적이다.

👏 마무리

---

지금까지 가상 메모리 관리 기법에서의 가져오기 방식과 재배치 방식에 대해 알아보았다.
다음 포스팅부터는 저장장치 관리에 대한 내용을 알아보자.
어느덧 3개의 Chapter 밖에 남지 않았다.

---

참고 자료

쉽게 배우는 운영체제

---