메모리 관리

운영체제는 프로세스를 구성하는 모듈을 전부 메모리에 올리지 않고 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때 메모리로 불러 사용한다.

- 메모리를 효율적으로 관리하기 위해서. 메모리가 꽉 차면 관리하기 어렵다.

- 응답 속도를 향상시키기 위해서. 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있다.

요구 페이징: 사용자가 요구할 때 해당 페이지를 메모리로 가지고 오는 것.

미리 가져오기: 예상되는 페이지를 미리 가져오는 방식. 대표적으로 캐시

 

페이지 테이블 구조

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

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

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

페이지 부재: 프로세스가 페이지를 요청했을 때 그 페이지가 메모리에 없는 상황. 페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.

페이지 부재가 발생하면 스왑 영역에 있는 페이지를 메모리의 빈 영역에 올리고 페이지 테이블을 갱신한다. 메모리에 빈 프레임이 있으면 작업이 수월하지만, 메모리에 빈 프레임이 없는 경우에는 메모리에 있는 프레임 중 하나를 스왑영역으로 내보낸 후 해당 페이지를 가지고 올 수 있다. 이때 어떤 페이지를 스왑영역으로 보낼지 결정하는 알고리즘을 ‘페이지 교체 알고리즘’이라고 한다. 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지라고 한다. (420 페이지 참조)

 

페이지 교체 알고리즘

사용이유: 프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생한다. 페이지 부재가 발생하면 스왑 영역에서 페이지 메모리로 가져오는데, 만약 메모리가 가득 찼다면 메모리에 있는 페이지를 스왑영역으로 내보내야 한다. 페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템 성능을 향상시킨다.

성능 평가 기준: 페이지 교체 알고리즘을 평가할 때는 성능뿐만 아니라 유지 비용도 고려를 해야한다. 아무리 성능이 뛰어난 알고리즘이라고 계산을 많이 해야 하거나 메모리를 많이 차지한다면 좋은 알고리즘이 아니다.

 

무작위 페이지 교체 알고리즘: 페이지 교체 알고리즘 중 가장 간단하게 구현 가능한 방식이다. 스왑영역으로 쫓아낼 대상 페이지를 특별한 로직 없이 무작위로 선정한다. 하지만 성능이 좋지 않아 거의 사용하지 않는다.

 

FIFO페이지 교체 알고리즘 

선입선출 페이지 알고리즘이다. 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑영역으로 쫓아낸다.

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

FIFO 페이지 교체 알고리즘은 무조건 오래된 페이지를 대상페이지로 선정하기 때문에 성능이 떨어진다.

 

최적 페이지 교체 알고리즘

앞으로 사용하지 않을 페이지를 스왑영역으로 옮긴다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다.

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

 

LRU 페이지 교체 알고리즘

페이지에 접근한 시간을 기준으로 대상 페이지를 선정한다. 최근 최소 사용 페이지 교체 알고리즘이라고도 한다. 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑영역으로 옮기는데 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정한다.

- 접근 시간에 기반한 구현: LRU 페이지 교체 알고리즘의 가장 간단한 형태는 페이지에 접근한 시간을 기록하여 구현하는 것이다. 페이지에 접근한지 가장 오래된 페이지를 교체하며, 이는 페이지에 읽기, 쓰기, 실행과 같은 연산이 이루어지는 시간을 기준으로 한다.

-  카운터에 기반한 구현: 접근 시간을 기록하든 카운터를 하든 두 방법 모두 메모리 공간이 추가로 더 들어간다는 단점이 있다. 이러한 추가 공간으로 인해 사용자가 사용할 수 있는 공간이 줄어든다.

- 참조 비트 시프트 방식: 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다. 단점으로 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다.

 

LFU 페이지 교체 알고리즘

페이지가 사용된 횟수를 기준으로 대상 페이지를 선정한다. 최소 빈도 사용 알고리즘이라고도 한다. 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 즉 현재 프레임에 있는 페이지마다 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑영역으로 옮긴다. 하지만 낭비되는 메모리공간이 많다는 단점이 있다. 페이지 접근 횟수(빈도)를 표시하는데 추가 공간이 필요하므로 그만큼 메모리가 낭비된다.

 

NUR 페이지 교체 알고리즘

LRU, LFU과 알고리즘 성능이 비슷하지만 불필요한 공간 낭비 문제를 해결하였다. 최근 미사용 페이지 교체 알고리즘이라고 불린다.

 

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

 

FIFO 변형 알고리즘

 메모리에 올라온 순서만 고려하고 자주 사용하는 페이지를 고려하지 않은 기존 FIFO알고리즘의 단점을 개선한 알고리즘으로 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다.

2차 기회 페이지 알고리즘

 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다. 그러나 큐를 유지하는 비용이 높고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동하는 작업이 추가된다는 단점이 있다. 

시계 알고리즘

스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다, 포인터가 시계 모양으로 돌기 때문에 시계 알고리즘이라고 부른다. (435페이지 참조)

 

스레싱과 프레임 할당: CPU의 속도도 빠라야 하지만 물리 메모리의 크기도 커야 성능이 좋다.

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

 

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

스레싱은 메모리의 크기가 일정할 경우 프로그램의 수와 밀접한 관계가 있다. 동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도라고 하는데 이 정도가 너무 높으면 스레싱이 발생한다.

CPU 사용률이 계속 증가하다가 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리로 가져오는 작업이 빈번해져서 CPU가 작업을 할 수 없는 상태에 이르게 된다. 이 시점을 스레싱 발생 지점이라고 한다.

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

 

스레싱은 각 프로세스에 프레임을 할당하는 문제와도 연관된다. 실행 중인 여러 프로세스에 프레임을 얼마나 나누어 주느냐에 따라 시스템의 성능이 달라진다. 남아있는 프레임을 실행중인 프로세스에 적절히 나누어 주는 정책이 필요한데, 할당하는 방식에 따라 정적할당과 동적할당으로 구분한다.

 

정적할당

 프로세스 실행 초기에 프레임을 나누어 준 후 그 크기를 고정하는 방식으로 균등할당 방식과 비례할당 방식이 있다. 하지만 프로세스를 실행하는 초기에 프레임을 할당하기 때문에 프로세스를 실행하는 동안 메모리 요구를 반영하지 못한다는 단점이 있다.

균등할당

 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당한다. 크기가 큰 프로세스의 경우 필요한 만큼 프레임을 할당받지 못하기 때문에 페이지 부재가 빈번하게 발생되고, 크기가 작은 프로세스의 경우 메모리가 낭비된다.

비례 할당

프로세스의 크기에 비례하여 프레임을 할당하는 방식이다. 비례 할당은 프로세스의 크기를 고려하지 않는 고정 할당보다 좀더 현실적인 방식이지만 다음과 같은 문제가 있다.

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

-- 사용하지 않을 메모리르 처음부터 미리 확보하여 공간을 낭비한다.

 

동적할당

시시각각 변하는 요청을 수행하는 방식이다. 잡업집합 모델과 페이지 부재 빈도를 사용하는 방법으로 구분할 수 있다.

작업 집합 모델

지역성이론을 바탕으로 하며, 가장 최근에 접근한 프레임이 이후에도 참조될 가능성이 높다는 가정에서 출발한다. 작업 집합 모델에서 물리 메모리에 유지할 페이지의 크기를 ‘작업집합 크기’라고 하는데, 이는 작업 집합에 들어갈 최대 페이지 수를 의미한다. 작업집합에 포함되는 페이지의 범위를 작업집합 윈도우라고 한다. 현재 시점에서 최대 어느 범위까지의 페이지를 살펴볼 것인가를 결정하는 것이 작업집합 윈도우이다. 작업 집합 모델에서 작업집합 윈도우의 크기에 따라 프로세스의 실행 성능이 달라진다. 작업집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미치고 너무 작에 잡으면 필요한 페이지가 스왑영역으로 옮겨져서 프로세스 성능이 떨어진다.

-- 단점: 충분한 페이지를 할당하지 않으면 작업 집합에 있는 페이지를 물리 메모리에 유지하기 힘들다. 작업 집합 모델에서는 어떤 프레임을 물리 메모리에 유지해야 하는지는 알 수 있지만 프레임을 얼마나 할당해야 하는지는 알 수 없다. 작업집합 모델은 성능을 높이는 방법이지만 스레싱 문제를 해결하지 못한다.

- 페이지 부재 빈도: 프로세스가 필요로 하는 페이지 양을 동적으로 결정하는 방법이다. 페이지 부재 횟수를 기록하여 페이지 부재 비율을 계산하는 방식으로 페이지 부재 비율의 상한선과 하한선을 설정한다. 페이지 부재 비율이 상한선을 초과하면 할당 프레임이 적다는 의미이므로 프레임을 추가하여 늘린다. 반대로 페이지 부재 비율이 하한선 밑으로 내려가면 메모리가 낭비된다는 의미이므로 할당한 프레임을 회수한다. 프로세스가 처음 시작될 때는 페이지 할당량을 예측하기 어렵다. 그러므로 페이지 부재 빈도 방식에서는 프로세스를 실행하면서 추가적으로 페이지를 할당하거나 회수하여 적정 페이지 할당량을 조절한다.

 

전역교체

전체 프레임을 대상으로 교체 알고리즘을 적용한다. 물리 메모리의 모든 프레임을 대상으로 스왑영역에 보낼 페이지를 찾는다.

 

지역교체

현재 실행중인 프로세스의 프레임을 대상으로 교체 알고리즘을 적용한다. 물리 메모리의 프로세스와 관련된 프레임을 대상으로 스왑 영역에 보낼 페이지를 찾는다.

- 장점: 자신에게 할당된 프레임의 전체 개수에 변화가 없기 때문에 페이지 교체가 다른 프로세스에 영향을 미치지 않는다. 전체 프로세스에 할당된 프레임의 수가 변하지 않기 대문에 스레싱을 줄일 수 있다.

- 단점: 자주 사용하는 페이지가 스왑영역으로 옮겨지면 시스템 효율이 떨어진다.

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