[발표자료]페이징 VS 세그먼테이션

메모리 이중성

우리는 많은 프로세스를 동작 시켜야 하기 때문에 메모리를 꾸준하게 잘 관리해야 합니다. 그렇지만 여러 작업을 동시에 처리하면 메모리 관리에 문제가 생기기 마련입니다. 그래서 복잡한 메모리의 관리는 메모리 관리시스템이 담당합니다. 늘 그렇듯이 프로세스 입장에서는 메모리를 독차지하고 싶어하고, 메모리 관리자 입장에서는 관리를 효율적으로 하고 싶어 하는데 이를 메모리의 이중성이라고 합니다.

일괄 처리 시스템에서 한 번에 한가지 작업만 처리하면 관리가 어렵지 않은데, 시분할 시스템에서 운영체제를 포함한 모든 응용프로그램이 메모리에 올라와 있기 때문에 메모리 관리가 복잡합니다.

 

메모리 관리

메모리 관리는 크게 가져오기, 배치 재배치로 나눌 수 있습니다.

가져오기는 실행할 프로세스와 데이터를 메모리로 가져오는 것을 말합니다. 그런데 때때로 상황에 따라서 데이터의 일부만 가져와도 동작합니다. 여기에 대한 자세한 설명은 조금 뒤에 하겠습니다.

배치는 가져온 프로세스와 데이터를 어느 부분에 올려 놓을지 결정하는 작업입니다. 또한 배치 작업전에 메모리를 얼마나 작고, 크게 자를 것인지 크기를 결정하는 것이 중요합니다. 왜냐하면 크기에 따라서 관리의 복잡성이 달라지기 때문입니다. 우리가 흔히 게임이 배치 작업중이라고 하는 것이 바로 이 작업입니다. 서버에 업데이트된 데이터를 올리는 작업인데 이것을 메모리에 어떻게 최적화해서 올릴지 고민하는 단계라고 볼 수 있습니다.

재배치는 새로운 프로세스를 가져와야 하는데 메모리가 가득 찼다면 메모리에 있는 프로세스를 하드 디스크에 옮겨 놓아야 새로운 프로세스를 메모리에 가지고 올 수 있습니다. 이처럼 꽉 찬 메모리에 새로운 프로세스를 가져오기 위해서 오래된 프로세스를 내보내는 작업을 메모리 재배치 작업이라고 합니다. 새로운 옷을 사서 옷장에 넣어야 하는데 공간이 없어서 못 들어간다면 오래되고 낡은 옷부터 버리는 것을 생각하면 됩니다.

 

스왑

여기서 쫓겨난 프로세스가 가는 저장장치의 공간을 스왑영역이라고 하며, 만약 쫓겨난 프로세스가 다시 필요해서 불러들이는 작업을 스왑인이라고 합니다. 쫓겨나는 과정을 스왑아웃이라고 하며, 메모리 오버 레이에서는 메모리보다 큰 프로그램을 실행할 때 프로그램의 메모리보다 작은 크기의 모듈로 나누어서 사용한다. 여기에 스왑을 이용하면 스왑영역의 크기가 메모리의 크기로 인식됩니다. 사용자는 실제 메모리와 스왑영역의 크기를 합쳐서 전체 메모리의 크기로 인식하고 사용할 수 있습니다.

 

메모리 오버레이

우리는 종종 실제 메모리 보다 큰 프로그램도 실행시켜야 하는 경우가 발생합니다. 이때 사용하는 것이 메모리 오버레이 입니다. 예를 들어서 컴퓨터의 램 용량이 4gb인데 배그를 하면서 디코를 하려면 총 12GB의 램이 필요하다고 할 때 사용하는 것입니다. 프로그램의 크기가 실제 메모리보다 클 때 전체 프로그램을 메모리에 가져오는 대신 적당한 크기로 가져오는 기법입니다.

 

가변 분할 방식 VS 고정 분할 방식

사실 한 번에 여러 프로세스를 동시에 실행하는 경우 메모리 관리가 더욱 복잡합니다. 프로세스들의 크기가 달라 메모리를 어떻게 나누어 사용할 것인지가 제일 문제입니다. 이렇게 메모리를 어떤 크기로 나눌 것인가 고민하는 것이 메모리 배치 정책에 해당합니다.

우리는 크게 가변분할 방식과 고정분할 방식으로 구분할 수 있습니다.

가변 분할 방식은 프로세스의 크기에 따라 메모리를 나누며 세그먼테이션이라고 부르기도 합니다.

세그먼테이션 기법은 가변 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 메모리를 프로세스 크기에 따라 가변적으로 나누어 사용합니다.

또한 고정 분할 방식은 프로세스의 크기에 상관없이 메모리를 일정하게 나눕니다.

페이징 기법은 고정 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 주소 공간을 같은 크기로 나누어 사용한다. 페이지 테이블의 크기는 물리 주소의 크기가 아니라 프로세스의 크기에 비례한다. 롤에서 체력 퍼 데미지를 생각하면 됩니다. 물리 주소의 크기와 상관없이 가상 주소를 많이 사용하면 페이지 테이블의 크기가 늘어나고, 적게 사용하면 페이지 테이블의 크기가 줄어든다.

가변분할은 유도리 있게 덩치를 보고 배식을 해주는 것이고 고정 분할은 유도리 없이 늘 일정한 양만 주는 것입니다. 아마 군대 다녀오신 분들은 맛도리 있는 음식 더 안주는 패급과 에이스를 생각하면 될 것입니다.

 

가변 분할 방식

그리고 이렇게 가변분할 방식에서 프로세스가 스왑 영역으로 빠졌을 때, 즉 종료되었다면 빈공간이 발생합니다. 그렇지만 가변분할에서는 이 공간의 크기가 일정하지 않습니다. 여기 보이듯이 카톡과 vscode가 종료되고 4칸을 필요로 하는 디스코드가 들어오려고 하는데 필요로 하는 자원보다 남은 자원이 작아서 들어오지 못하는 현상을 외부 단편화 라고 합니다.

조금 더 자세하게 말해서 외부 단편화란 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적이지 않아 발생하는 현상이다. 그리고 이러한 문제는 메모리 배치방식이나 조각 모음을 사용해서 해결합니다. 참고로 가변 분할 방식은 프로세스를 하나의 연속된 주소로 둔다는 장점이 있습니다.

 

고정 분할 방식

이제 고정 분할 방식에서 프로세스가 스왑영역으로 빠졌을 경우를 한번 살펴봅시다. 이 페이지에서 보이는 것과같이 디스코드가 스왑영역으로 나가고 그 자리에 카카오톡이 들어왔을 때 1자리가 남게 되는데, 이 1자리에 그 어떤 프로세스도 들어올 수 없어 계속해서 자리가 남아 돌아 낭비되는 것을 내부 단편화라고 합니다. 더 자세하게 이야기하면 내부 단편화란 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말합니다.

참고로 고정 분할 방식은 크기가 큰 프로세스가 메모리에 올라오면 여러 조각으로 나뉘어 배치됩니다. 하지만 그렇기 때문에 프로세스의 여러 곳으로 나뉠 수 있습니다. 참고로 늘 같은 크기로 나뉘기 때문에 관리하기 편합니다. 그리고 현대의 대부분 메모리 관리 기법은 고정분할방식인 페이징 기법을 사용하고 있습니다.

메모리 오버레이를 다룰 때 프로세스가 여러 곳에 나뉘어 배치되거나 일부만 물리 메모리에 있고 나머지는 스왑영역에 있어도 실행에 문제가 없기 때문에 고정 분할 방식은 가변 분할 방식보다 메모리 관리 측면에서 우세하다고 볼 수 있습니다. 그래서 현대 운영체제에서 메모리 관리는 기본적으로 고정 분할 방식을 사용합니다.

 

캐시 메모리

초반부에 이야기했듯이 캐시의 메모리 적중률 즉 캐시히트의 확률이 높으면 메모리 효율성이 좋다고 이야기 했습니다. 그렇다면 어떻게 이 효율성을 좋게 만들 수 있을까요?

바로 기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질인 지역성 이론을 적용하면 됩니다. 여기에는 공간의 지역성, 시간의 지역성, 순차적 지역성이 있습니다.

공간의 지역성은 현재 위치에서 가까운 데이터에 접근할 확률이 먼 거리에 있는 데이터에 접근할 확률보다 높음을 이야기합니다. 우산 없이 길거리를 걷다가 비가오면 가장 가까운 편의점으로 들어가 우산을 사는 것과 같습니다.

시간의 지역성은 현재 기준으로 가장 가까운 시간에 접근한 데이터가 더 먼 시간에 접근한 데이터보다 사용될 확률이 높음을 이야기합니다. 아무래도 우리가 과거로 갈 때 복권번호를 외워가지 않겠습니까? 저도 기억력이 나빠서 아마 가장 최신 회차의 복권번호를 외워서 가장 최근의 토요일로 돌아가는 것이 복권 1등될 확률이 높은 것과 같습니다.

순차적 지역성은 작업이 순서대로 진행되는 것을 말합니다. 음식 할 때 레시피 순서대로 따라만 해도 1인분은 한다는 것을 생각하면 될 것 같습니다.

페이지 교체 알고리즘도 이 지역성 이론을 기반으로 하며, 페이지 교체 알고리즘은 메모리가 꽉 차 특정 페이지를 스왑으로 보내야만 새로운 페이지를 받을 수 있는 상황에서 물리 메모리에 있는 페이지 중 하나를 골라 보낼 때 사용합니다.

 

이전에 봤듯이 운영체제는 프로세스를 구성하는 모듈을 전부 메모리에 올리지 않고 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때 메모리로 불러 사용한다. 왜냐하면 메모리를 효율적으로 관리하기 위해서입니다. 메모리가 꽉 차면 관리하기 어렵고, 응답 속도를 향상시키기 위해서. 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어질 수 있기 때문입니다.

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

여기에서는 메모리가 가득 차 있어서 다음 프로세스인 롤을 실행시켜야 하는데, 동작중인 그 어느 프로세스도 스왑영역으로 가고 싶어 하지 않아 결국에는 페이지 교체 알고리즘을 통해서 보내는 것으로 쉽게 생각하면 될 것 같습니다.

 

페이징 알고리즘은 FIFO, LFU, NUR, LRU, FIFO 변형 알고리즘이 있습니다. 그리고 FIFO변형 알고리즘인 2차 기회 페이지 알고리즘과 시계 알고리즘이 있습니다.

 

페이징 알고리즘

FIFO는 메모리의 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입된다. 메모리가 꽉 차면 맨 위의 페이지가 스왑영역으로 들어가고 나머지 페이지들이 위로 이동하며, 새로운 페이지가 아래쪽의 남은 공간으로 들어온다. 무조건 오래된 페이지를 대상페이지로 선정하기 때문에 성능이 떨어집니다

최적 페이지 교체 알고리즘은 앞으로 사용하지 않을 페이지를 스왑영역으로 옮깁니다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정합니다. 최적 페이지 교체 알고리즘은 미래에 메모리 접근 패턴을 보고 대상 페이지를 결정하기 때문에 성능이 좋습니다. 하지만 미래에 접근 패턴을 알기는 불가능합니다. 결국 최적 페이지 교체 알고리즘은 이상적인 방법이지만 실제로 구현할 수 없습니다.

LRU 페이지 교체 알고리즘은 페이지에 접근한 시간을 기준으로 대상 페이지를 선정합니다. 최근 최소 사용 페이지 교체 알고리즘이라고도 합니다. 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑영역으로 옮기는데 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정합니다. 카운터에 기반한 구현과 참조 비트 시프트 방식이 있습니다.

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

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

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

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

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

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

 

간단 요약

이번에도 역시 지금까지 한 내용을 요약해 보겠습니다.

 

면접 문제 후보

그리고 배운 내용을 바탕을 나올 수 있는 면접 문제입니다.