[CS] Chapter 09 가상 메모리 관리

프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것이 가져오기 정책입니다. 일반적인 방법은 프로세스가 요청할 때 메모리로 가져오는 것으로 이를 요구 페이징이라고 합니다.

📌 요구 페이징의 개요

1. 요구 페이징의 개요

프로세스의 일부만 메모리로 가져오는 이유는 다음과 같습니다.

1. 메모리를 효율적으로 관리하기 위해서입니다. 메모리가 꽉 차면 관리하기 어려우므로 가능하면 적은 양의 포르세스만 유지합니다.

2. 응답 속도를 향상하기 위해서입니다. 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있으므로 필요한 모듈만 올려 실행합니다.

프로그램 일부만 가져와 실행하고 사용자가 특정 기능을 요구할 때 해당 모듈을 메모리에 올리면 메모리의 절약과 효율적 관리, 프로세스의 응답 속도 향상 등의 효과를 볼 수 있습니다. 이처럼 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구페이징(demand paging) 이라고 합니다.

요구 페이징과 반대로 앞으로 필요할 것이라고 예상되는 페이지를 미리 가져오는 방식이 미리 가져오기입니다. 미리 가져오기의 대표적인 예가 캐시입니다. 캐시는 앞으로 필요할 것이라고 예상되는 부분을 고속의 캐시 메모리에 가져다 놓음으로써 시스템 성능을 향상합니다. 그러나 미리 가져온 데이터가 쓸모없게 되면 피해가 매우 큽니다. 따라서 현대의 운영체제는 요구 페이징을 기본으로 사용합니다.

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

가상 메모리의 크기는 물리 메모리와 스왑 영역을 합친 것입니다.

가상 메모리 세스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있습니다. 이 때 페이지가 스왑 영역에 있는 경우는 크게 두 가지입니다.

1. 요구 페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우

2. 메모리가 꽉 차서 스왑 영역으로 옮겨 온 경우

어떤 것이든 페이지 테이블에는 페이지가 메모리에 있는지, 스왑 영역에 있는지 표시해야 합니다. 이때 사용하는 비트가 유효 비트입니다.

PTE를 구성하는 프레임 번호는 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려주는 자료구조로 페이지 테이블의 핵심입니다. PTE의 가운데에는 접근 비트, 변경 비트, 유효 비트, 읽기 비트, 쓰기 비트, 실행 비트 등을 모아놓은 플래그 비트가 있습니다.

• 접근 비트(access bit) : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려줍니다.

• 변경 비트(modified bit) : 페이지가 메모리에 올라온 후 데이터 변경이 있었는지 알려줍니다.

• 유효 비트(valid bit) : 페이지가 실제 메모리에 있는지를 나타냅니다.

• 읽기 비트, 쓰기 비트, 실행 비트(execute bit) : 페이지에 대한 읽기 권한 쓰기 권한, 실행 권한을 나타냅니다.

3. 페이지 부재

가상 메모리의 페이지 테이블에는 페이지가 물리 메모리에 있는지, 스왑 영역에 있는지 표시하기 위해 유효 비트를 사용합니다.

페이지 부재 (page fault) : 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황

페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 합니다.

페이지 부재가 발생하면 위와 같은 과정을 거쳐 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신(업데이트)합니다. 메모리에 빈 프레임이 있어서 작업이 수월하지만, 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역으로 내보낸 후에야 해당 페이지를 가져올 수 있습니다.

세그먼테이션 오류와 페이지 부재는 비슷해 보여도 많은 차이가 있습니다. 세그먼테이션 오류는 사용자 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생합니다. 즉, 사용자 프로세스에 의해 발생하는 것으로 해당 프로세스를 강제 종료하여 오류를 해결합니다. 반면, 페이지 부재는 해당 페이지가 물리 메모리에 없을 때 발생하는 것으로 사용자 프로세스와 무관합니다. 페이지 부재가 발생하면 메모리 관리자는 스왑 영역에 해당 페이지를 물리 메모리로 옮긴 후 작업을 진행합니다.

📌 요구 페이징의 개요

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

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

페이지 교체 알고리즘의 종류

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 살펴보고 대상 페이지를 선정하므로 성능이 가장 좋지만 사실상 구현이 불가능합니다.

종류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정하여 스왑 영역으로 보냅니다.
간단한 알고리즘	FIFO	처음 메모리에 올라온 페이지를 스왑 영역으로 보냅니다.
이론적 알고리즘	최적	미래의 메모리 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보냅니다.
최적 근접 알고리즘	LRU	시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보냅니다.
최적 근접 알고리즘	LFU	사용 빈도가 적은 페이지를 스왑 영역으로 보냅니다.
최적 근접 알고리즘	NUR	최근에 사용한 적이 없는 페이지를 스왑 영역으로 보냅니다.
최적 근접 알고리즘	FIFO 변형	FIFO 알고리즘을 변형하여 성능을 높입니다.

페이지 교체 알고리즘의 성능 평가 기준

같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 비교해 봅니다. 한편, 페이지 교체 알고리즘을 평가할 때는 성능뿐 아니라 유지 비용도 고려해야 합니다. 아무리 성능이 뛰어난 알고리즘이라도 계산을 많이 해야 하거나 메모리를 많이 차지한다면 좋은 알고리즘이 아닙니다.

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

무작위 페이지 교체 알고리즘(random page replacement alghorithm)은 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방식입니다. 이 알고리즘은 성능이 좋지 않아 거의 사용되지 않습니다

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

선입선출 페이지 교체 알고리즘이라고도 하는 FIFO 페이지 교체 알고리즘(First In First Out page replacement algorithm)은 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아냅니다.

FIFO 페이지 교체 알고리즘은 큐로 구현합니다. 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입됩니다. 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며, 새로운 페이지가 아래쪽의 남은 공간에 들어옵니다.

메모리에 먼저 올라왔어도 자주 사용되는 페이지가 있기도 하고, 나중에 올라왔어도 한 번만 사용되는 페이지가 있기도 합니다. FIFO 페이지 교체 알고리즘은 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어집니다. 이러한 문제점을 개선한 것이 2차 기회 페이지 교체 알고리즘입니다.

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

최적 페이지 교체 알고리즘(optimal page replacement algorithm)은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮깁니다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상으로 선정합니다.

최적 페이지 교체 알고리즘은 미래의 메모리 접근 패턴을 보고 대상 페이지르 ㄹ결정하기 때문에 성능이 좋습니다. 하지만 미래의 접근 패턴을 알기는 불가능합니다. 결국 최적 페이지 교체 알고리즘은 이상적인 방법이지만 실제로는 구현할 수 없습니다.

최근 최소 사용 알고리즘인 LRU(Least Recently Used), 최소 빈도 사용 알고리즘인 LFU(Least Frequently Used), 최근 미사용 알고리즘인 NUR(Not Used Recently) 등이 개발되었습니다. 이러한 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘(optimal approximation algorithm)이라고 부릅니다.

• LRU 페이지 교체 알고리즘 : 페이지에 접근한 시간을 기준으로 대상 페이지를 선정합니다.

• LFU 페이지 교체 알고리즘 : 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정합니다.

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

LRU 페이지 교체 알고리즘(Least Recently Used page replacement algorithm)은 '최근 최소 사용 페이지 교체 알고리즘'이라고도 합니다. 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮기는데 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정합니다.

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

LRU 페이지 교체 알고리즘의 가장 간단한 형태는 페이지에 접근한 시간을 기록하여 구현하는 것입니다.

카운터에 기반한 구현

LRU 페이지 교체 알고리즘은 페이지 접근 시간을 기록하여 구현할 수도 있지만 카운터를 사용하여 구현할 수도 있습니다. 맨 위의 숫자를 시각(초)이 아니라 카운터 숫자라고 생각하면 됩니다.

참조 비트 시프트 방식

참조 비트 시프트 방식은 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것입니다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀝니다.

이와 같은 방식으로 참조 비트를 갱신하다가 대상 페이지를 선정할 필요가 있으면 참조 비트 중 가장 작은 값을 대상 페이지로 선정합니다.

LRU 페이지 교체 알고리즘의 단점은 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다는 것입니다.

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

최적 근접 알고리즘 중 LFU 페이지 교체 알고리즘(Least Frequently Used page replacement algorithm)은 '최소 빈도 사용 알고리즘'이라고도 합니다. LFU 페이지 교체 알고리즘은 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정합니다.

LFU 페이지 교체 알고리즘이 LRU 페이지 교체 알고리즘보다 한 번 더 성공했지만 일반적인 경우 두 알고리즘의 성능이 비슷하다고 알려져 있습니다. LRU, LFU 페이지 교체 알고리즘은 둘다 FIFO 페이지 교체 알고리즘보다 성능이 우수합니다.

LFU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다는 것입니다. 페이지 접근 횟수(빈도)를 표시하는 데 추가 공간이 필요하므로 그만큼 메모리가 낭비됩니다.

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

NUR 페이지 교체 알고리즘(Not Used Recently page replacement algorithm)은 LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결하였습니다. NUR 페이지 교체 알고리즘은 '최근 미사용 페이지 교체 알고리즘' 이라고도 불립니다.

알고리즘에서 접근 시간이든 접근 빈도든 정확한 값을 유지하는 것은 공간만 많이 차지할 뿐 의미가 없습니다. NUR 페이지 교체 알고리즘은 이러한 경향을 반영한 방식으로, 추가 비트 2개만 사용하여 미래를 추정합니다.

NUR 페이지 교체 알고리즘에서는 페이지마다 참조 비트와 변경 비트를 가지므로 페이지마다 추가되는 메모리 공간이 2bit뿐입니다.

• 참조 비트 : 페이지 접근(read/execute)하면 1이 됩니다.

• 변경 비트 : 페이지가 변경(write/append)되면 1이 됩니다.

NUR 페이지 교체 알고리즘에서 대상 페이지를 선정할 때는 (0, 0) (0, 1), (1, 0), (1, 1) 중 하나를 고르는데, 가장 먼저 (0, 0)인 페이지를 선정합니다. 즉 접근한 적도, 변경한 적도 없는 페이지를 스왑 영역으로 옮깁니다. 만약 (0, 0)인 페이지가 없다면 (0, 1)인 페이지를, (0, 1)인 페이지가 없다면 (1, 0)인 페이지를, (1, 0)인 페이지도 없다면 최종적으로 (1, 1)인 페이지를 스왑 영역으로 옮깁니다.

최적 근접 알고리즘인 LRU, LFU, NUR 페이지 교체 알고리즘의 성능은 거의 비슷하며 FIFO 페이지 교체 알고리즘보다 우수합니다. 이 중에서 NUR 페이지 교체 알고리즘은 2bit만 추가하여 다른 알고리즘과 유사한 성능을 낼 뿐만 아니라 쉽게 구현할 수 있다는 장점 때문에 가장 많이 사용되고 있습니다.

8. FIFO 변형 알고리즘

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

2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)은 FIFO 페이지 교체 알고리즘과 마찬가지로 큐를 사용하지만, 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다는 차이점이 있습니다. 다시 말해 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줍니다.

일반적으로 2차 기회 페이지 교체 알고리즘의 성능은 LRU, LFU, NUR 페이지 교체 알고리즘보다 약간 낮고 FIFO 페이지 교체 알고리즘보다 약간 높은 것으로 알려져 있습니다. 그러나 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다는 단점이 있습니다.

시계 알고리즘

2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용하는 것이 가장 큰 차이점입니다.

시계 알고리즘에서는 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 다음번에는 다시 큐의 처음을 가리키게 됩니다. 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부릅니다.

시계 알고리즘은 대상 포인터와 각 페이지당 참조 비트 하나만 추가하면 되기 때문에 NUR 페이지 교체 알고리즘보다 추가 공간이 적게 들지만 알고리즘이 복잡하고 계산량이 많다는 것이 단점입니다.

📌 스레싱과 프레임 할당

1. 스레싱

스레싱의 개념

CPU의 속도도 빨라야 하지만 물리 메모리의 크기도 커야 성능이 좋습니다.

스레싱 (threshing) : 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태

스레싱은 보관 창고에서 재료를 도마로 가져오거나 도마의 재료를 보관 창고로 옮기는 작업이 너무 많아져서 요리사가 요리를 하지 못하는 경우와 같습니다.

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

동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도(degree of multiprogramming)라고 하는데, 멀티 프로그래밍 정도가 너무 높으면 스레싱이 발생합니다.

프로그램의 수가 적을 때는 CPU 사용률이 계속 증가하다가 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리로 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 됩니다.이러한 시점을 스레싱 발생 지점(threshing point)라고 합니다.

자주 사용하는 프로세스가 필요로 하는 메모리보다 물리 메모리가 작다면 스레싱 발생 지점에 빨리 도달하여 컴퓨터가 전체적으로 느려집니다. 따라서 물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦춰져서 프로세스를 원만하게 실행할 수 있습니다.

물리 메모리가 작업하는 데 충분한 크기가 되면 그 이후에는 크기를 늘려도 작업 속도에 영향을 미치지 않습니다.

스레싱과 프레임 할당

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

2. 정적 할당

정적 할당 (static allocation) 방식 : 프로세스 실행 초기에 프레임을 나누어 준 후 그 크기를 고정하는 것

균등 할당

균등 할당(equal allocation) 방식에서는 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당합니다.

비례 할당

비례 할당(proportional allocation) 방식은 프로세스의 크기에 비례하여 프레임을 할당하는 방식입니다.

• 프로세스가 실행 중에 필요로 하는 프레임을 유동적으로 반영하지 못합니다.

• 사용하지 않을 메모리를 처음부터 미리 확보하여 공간을 낭비합니다.

3. 동적 할당

동적 할당(dynamic allocation) : 시시각각 변하는 요청을 수용하는 방식

작업집합 모델

작업집합 모델(working set model)은 지역성 이론을 바탕으로 하며, 가장 최근에 접근한 프레임 이후에도 참조될 가능성이 높다는 가정에서 출발합니다.

현재 시점에서 최대 어느 범위까지의 페이지를 살펴볼 것인가를 결정하는 것이 작업집합 윈도우입니다.

작업집합 모델에서는 작업집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라집니다. 작업집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미치고 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스 성능이 떨어집니다.

페이지 부재 빈도

프로세스가 필요로 하는 페이지 양을 동적으로 결정하는 방법 중 페이지 부재 빈도(page fault frequency)를 이용하는 방법이 있습니다. 이는 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식으로 페이지 부재 비율의 상한선과 하한선을 설정합니다. 페이지 부재 비율이 상한선을 초과하면 할당한 프레임이 적다는 의미이므로 프레임을 추가하여 늘립니다. 반대로 페이지 부재 비율이 하한선 밑으로 내려가면 메모리가 낭비된다는 의미이므로 할당 프레임을 회수합니다.

4. 전역 교체와 지역 교체

페이지 교체 알고리즘에 따라 페이지를 교체할 때는 전역 교체 global replacement) 방식 또는 지역 교체(local replacement) 방식을 적용합니다.

• 전역 교체 : 전체 프레임을 대상으로 교체 알고리즘을 적용합니다.

• 지역 교체 : 현재 실행 중인 프로세스의 프레임을 대상으로 교체 알고리즘을 적용합니다.

전역 교체 방식에서는 물리 메모리의 모든 프레임을 대상으로 스왑 영역에 보낼 페이지를 찾습니다. 지역 교체 방식에서는 물리 메모리의 프로세스 A와 관련될 프레임을 대상으로 스왑 영역에 보낼 페이지를 찾습니다. 지역 교체 방식에서는 전체 프로세스에 할당된 프레임의 수가 변하지 않기 때문에 스레싱을 줄일 수 있습니다.

지역 교체 방식의 단점은 자주 사용하는 페이지가 스왑 영역으로 옮겨지면 시스템 효율이 떨어진다는 것입니다.

지역 교체 방식은 다른 프로세스의 스레싱은 줄일 수 있지만 반대로 실행 중인 프로세스의 성능을 떨어뜨릴 수도 있습니다. 그러므로 전체 시스템의 입장에서는 전역 교체 방식이 지역 교체 방식보다 효율적입니다.