가상 메모리

가상 메모리는 컴퓨터의 물리적 메모리보다 큰 프로그램이나 데이터를 실행할 수 있도록 하는 기술입니다.
가상 메모리는 물리적 메모리를 여러 조각으로 나누고, 필요한 부분만 실제 메모리에 적재하고, 나머지는 디스크에 저장합니다.
이렇게 하면 실제 메모리의 크기에 제한되지 않고, 더 많은 양의 정보를 처리할 수 있습니다.

장점

• 프로그램이나 데이터의 크기가 물리적 메모리보다 커도 실행할 수 있습니다.

• 여러 프로세스가 동시에 실행될 수 있으며, 각 프로세스는 자신만의 가상 메모리 공간을 가집니다.

• 메모리의 효율성과 보안성이 향상됩니다. 필요한 부분만 실제 메모리에 적재하므로, 낭비되는 공간이 줄어들고, 다른 프로세스의 메모리 영역에 접근할 수 없습니다.

단점

• 디스크와 메모리 사이의 데이터 이동이 빈번하게 발생하므로, 성능 저하가 일어날 수 있습니다. 이를 페이징이라고 합니다.

• 가상 메모리의 관리를 위한 추가적인 하드웨어와 소프트웨어가 필요합니다. 예를 들어, 페이지 테이블이라는 자료구조를 사용하여 가상 주소와 물리 주소를 매핑해야 합니다.

가상 주소와 물리 주소(실주소)

가상 주소

가상 주소란 프로세스가 사용하는 메모리 주소입니다.
프로세스는 자신의 메모리 공간을 가상 주소로 인식하고, 이를 통해 데이터를 읽고 쓸 수 있습니다.
가상 주소 공간은 물리 메모리보다 크거나 작을 수 있으므로, 메모리의 낭비를 줄이고 다양한 크기의 프로그램을 실행할 수 있습니다. 또한, 각 프로그램은 자신의 가상 주소 공간만을 사용하므로, 다른 프로그램의 메모리에 접근할 수 없습니다.

가상 주소는 실제 메모리에 직접 매핑되는 것이 아니라, 운영체제와 하드웨어의 협력을 통해 변환되어야 합니다.
이때 사용되는 것이 물리 주소입니다.

물리 주소

물리 주소란 실제 메모리에 할당된 주소입니다.
가상 주소는 물리 주소로 변환되어야만 실제 메모리에 접근할 수 있습니다.
이러한 변환 과정을 주소 변환(address translation)이라고 합니다. 주소 변환은 운영체제가 관리하는 페이지 테이블(page table)과 하드웨어가 제공하는 MMU(Memory Management Unit)를 이용하여 수행됩니다.

사용 목적

가상 주소와 물리 주소의 사용 목적은 메모리 관리를 효율적으로 하기 위함입니다.
가상 주소를 사용하면 프로세스마다 독립적인 메모리 공간을 제공할 수 있으며, 메모리 보호, 공유, 확장 등의 기능을 구현할 수 있습니다. 또한, 물리 메모리보다 큰 가상 메모리를 사용할 수 있어서 메모리 부족 문제를 완화할 수 있습니다.

가상 주소를 물리 주소(실주소)로 변환하는 방법

가상 주소를 물리 주소로 변환하는 과정을 가상 주소 변환(virtual address translation)이라고 합니다.

가상 주소 변환은 운영체제의 메모리 관리 기능 중 하나입니다.
운영체제는 가상 주소 공간(virtual address space)을 여러 개의 페이지(page)라는 단위로 나눕니다. 각 페이지는 일정한 크기를 가지며, 물리 메모리에 있는 프레임(frame)이라는 공간에 매핑됩니다. 운영체제는 페이지 테이블(page table)이라는 자료구조를 사용하여 각 페이지와 프레임의 관계를 저장합니다.

가상 주소 변환은 다음과 같은 단계로 이루어집니다.

1. 프로그램이 가상 주소를 생성합니다.

2. 운영체제는 가상 주소의 상위 비트를 페이지 번호(page number)로, 하위 비트를 오프셋(offset)으로 해석합니다.

3. 운영체제는 페이지 테이블을 검색하여 페이지 번호에 해당하는 프레임 번호(frame number)를 찾습니다.

4. 운영체제는 프레임 번호와 오프셋을 결합하여 물리 주소를 생성합니다.

5. 운영체제는 물리 주소를 사용하여 메모리에 접근합니다.

Swapping

Swapping은 컴퓨터에서 메모리 관리를 위한 기법 중 하나입니다.
Swapping은 메모리에 적재된 프로세스 중 일부를 디스크와 같은 보조 기억 장치에 임시로 저장하고, 필요할 때 다시 메모리로 불러오는 과정을 말합니다. Swapping은 메모리 공간이 부족하거나 효율적으로 사용되지 않을 때 발생합니다.
Swapping을 통해 메모리에 여유 공간을 확보하고, 프로세스의 실행 속도를 높일 수 있습니다.

Swapping의 과정

1. 운영체제는 메모리에 적재된 프로세스들의 우선순위, 실행 시간, 메모리 사용량 등을 고려하여 swapping-out할 프로세스를 선정합니다.

2. 선정된 프로세스의 메모리 상태를 보조 기억장치의 swap space라는 공간에 저장합니다. 이때, 프로세스의 PCB(Process Control Block)도 함께 저장됩니다.

3. 메모리에서 해제된 공간에 swapping-in할 프로세스를 적재합니다. 이때, 보조 기억장치에서 읽어올 때는 프로세스의 PCB를 먼저 읽어와서 메모리에 복구하고, 그 다음에 프로세스의 코드와 데이터를 읽어옵니다.

4. 적재된 프로세스의 상태를 준비(ready) 상태로 변경하고, CPU 스케줄링을 통해 실행(running) 상태로 전환합니다.

장점

• 메모리 공간을 효율적으로 사용할 수 있습니다.
  Swapping을 통해 메모리에 필요한 프로세스만 적재하고, 필요하지 않은 프로세스는 보조 기억 장치에 저장할 수 있습니다. 이렇게 하면 메모리의 낭비를 줄이고, 더 많은 프로세스를 실행할 수 있습니다.

• 프로세스의 우선 순위를 조정할 수 있습니다.
  Swapping을 통해 우선 순위가 높은 프로세스를 메모리에 적재하고, 우선 순위가 낮은 프로세스는 보조 기억 장치에 저장할 수 있습니다. 이렇게 하면 중요한 프로세스에 더 많은 메모리 자원을 할당할 수 있습니다.

• 멀티태스킹을 지원할 수 있습니다.
  Swapping을 통해 여러 개의 프로세스를 동시에 실행할 수 있습니다. 각 프로세스는 메모리와 보조 기억 장치 사이에서 교체되며, 사용자는 여러 작업을 동시에 수행할 수 있습니다.

단점

• Swapping 시간이 오래 걸릴 수 있습니다.
  Swapping은 프로세스를 메모리와 보조 기억 장치 사이에서 이동시키는 작업입니다. 이 작업은 시간이 많이 소요되며, 프로세스의 실행 속도를 저하시킬 수 있습니다. 특히, 보조 기억 장치의 입출력 속도가 느릴 경우, Swapping 시간이 더욱 길어질 수 있습니다.

• Swapping 과정에서 데이터 손실이 발생할 수 있습니다.
  Swapping은 프로세스의 일부분만 보조 기억 장치에 저장합니다. 이때, 보조 기억 장치에 저장된 데이터가 손상되거나 유실될 경우, 프로세스의 정상적인 실행이 불가능해질 수 있습니다. 따라서, Swapping 과정에서 데이터의 안전성을 보장하는 것이 중요합니다.

• Swapping 알고리즘의 성능이 낮을 수 있습니다.
  Swapping 알고리즘은 어떤 프로세스를 보조 기억 장치에 저장하고, 어떤 프로세스를 메모리로 불러올지 결정하는 방법입니다. Swapping 알고리즘의 성능이 낮으면, Swapping 횟수가 많아지거나, 필요한 프로세스가 보조 기억 장치에 남아있게 될 수 있습니다. 이러한 경우, Swapping의 효과가 감소하고, 시스템 성능이 저하될 수 있습니다.

페이지 교체

페이지 교체란 메모리에 적재된 페이지 중 하나를 디스크로 내보내고, 다른 페이지를 메모리로 가져오는 과정입니다.
페이지 교체는 메모리가 부족할 때 발생하며, 운영체제가 교체할 페이지를 선정하는 알고리즘을 사용합니다.
페이지 교체 알고리즘의 목적은 페이지 부재(page fault)의 횟수를 최소화하는 것입니다.
페이지 부재란 참조하려는 페이지가 메모리에 없는 상황을 말합니다. 페이지 부재가 발생하면 디스크에서 해당 페이지를 읽어와야 하므로 시간이 많이 소요됩니다.

페이지 부재를 최소화하는 방법

페이지 부재(page fault)란 메모리에 접근하려는 프로세스가 요청한 페이지가 메모리에 없는 상황을 말합니다.
이때 운영체제는 디스크에서 해당 페이지를 찾아 메모리로 가져오고, 페이지 테이블을 업데이트하고, 프로세스를 재시작합니다. 이 과정은 시간이 많이 걸리므로, 페이지 부재가 자주 발생하면 시스템 성능이 저하됩니다.

페이지 부재를 최소화하기 위해서는 다음과 같은 방법들이 있습니다.

• 적절한 페이지 교체 알고리즘을 사용합니다.
  페이지 교체 알고리즘은 메모리가 가득 찼을 때 어떤 페이지를 교체할지 결정하는 방법입니다.
  예를 들어, FIFO(First-In First-Out), LRU(Least Recently Used), LFU(Least Frequently Used) 등의 알고리즘들이 있습니다. 각 알고리즘은 장단점이 있으므로, 프로세스의 특성과 요구에 맞게 선택해야 합니다.

• 적절한 페이지 크기를 설정합니다.
  페이지 크기가 너무 작으면 페이지 테이블의 크기가 커지고, 내부 단편화가 줄어듭니다.
  반면, 페이지 크기가 너무 크면 외부 단편화가 커지고, 필요하지 않은 데이터까지 메모리에 올라갑니다.
  따라서, 페이지 크기는 프로세스의 메모리 접근 패턴과 하드웨어의 특성에 따라 적절하게 조정해야 합니다.

• 적절한 페이징 기법을 사용합니다.
  페이징 기법은 프로세스의 주소 공간을 여러 개의 페이지로 나누는 방법입니다.
  예를 들어, 단순 페이징(simple paging), 세그멘테이션(segmentation), 세그멘테이션 페이징(segmentation paging) 등의 기법들이 있습니다. 각 기법은 장단점이 있으므로, 프로세스의 구조와 요구에 맞게 선택해야 합니다.

페이지 교체 알고리즘

FIFO(First-In First-Out)

FIFO(First-In First-Out)는 가장 간단한 페이지 교체 알고리즘입니다.
FIFO는 메모리에 적재된 순서대로 페이지를 교체합니다. 즉, 가장 먼저 메모리에 들어온 페이지가 가장 먼저 나가게 됩니다.
FIFO는 구현이 쉽고 공정한 방식이라는 장점이 있습니다. 하지만, FIFO는 벨라디의 모순(Belady's anomaly)이라는 현상이 발생할 수 있습니다. 벨라디의 모순이란 메모리의 크기를 늘려도 페이지 부재가 증가하는 현상을 말합니다. 예를 들어, 다음과 같은 페이지 참조 열이 있다고 가정해봅시다.

페이지 참조 열 : 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

메모리의 크기가 3일 때, FIFO 알고리즘을 적용하면 다음과 같은 결과가 나옵니다.

참조 열	메모리 상태	페이지 부재 유무
1	1	O
2	1, 2	O
3	1, 2, 3	O
4	2, 3, 4	O
1	3, 4, 1	O
2	4, 1, 2	O
5	1, 2, 5	O
1	2, 5, 1	X
2	5, 1, 2	X
3	1, 2, 3	O
4	2, 3, 4	O
5	3, 4, 5	O

총 페이지 부재 횟수는 9번입니다.

메모리의 크기가 4일 때도 FIFO 알고리즘을 적용해보면 다음과 같은 결과가 나옵니다.

참조 열	메모리 상태	페이지 부재 유무
1	1	O
2	1, 2	O
3	1, 2, 3	O
4	1, 2, 3, 4	O
1	2, 3, 4, 1	X
2	3, 4, 1, 2	X
5	4, 1, 2, 5	O
1	1, 2, 5, 1	X
2	2, 5, 1, 2	X
3	5, 1, 2, 3	O
4	1, 2, 3, 4	O
5	2, 3, 4, 5	O

총 페이지 부재 횟수는 10번입니다.

메모리의 크기가 3에서 4로 증가했음에도 불구하고, 페이지 부재 횟수가 9에서 10으로 증가했습니다. 이것이 바로 벨라디의 모순입니다. 이러한 현상은 FIFO 알고리즘뿐만 아니라 다른 알고리즘에서도 발생할 수 있습니다. 따라서, 페이지 교체 알고리즘을 선택할 때는 벨라디의 모순이 발생하지 않는지 확인해야 합니다.

LRU(Least Recently Used)

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
LRU는 페이지가 얼마나 자주 사용되는지가 아니라, 얼마나 오래전에 사용되었는지를 기준으로 합니다. LRU는 가장 최근에 사용된 페이지가 가장 빨리 다시 사용될 가능성이 높다고 가정합니다.
따라서 LRU는 메모리에 적재된 각 페이지의 마지막 참조 시간을 기록하고, 가장 오래전에 참조된 페이지를 교체합니다.

장점

• 간단하고 직관적입니다.

• LRU 알고리즘은 시간적 지역성을 잘 반영할 수 있습니다.
  시간적 지역성이란, 한 번 참조된 페이지가 곧 다시 참조될 가능성이 높다는 특성을 말합니다.

단점

• 구현이 복잡하고 비용이 많이 듭니다.
  LRU 알고리즘은 메모리에 적재된 모든 페이지의 마지막 참조 시간을 관리해야 합니다. 이를 위해서는 별도의 자료구조와 하드웨어적인 지원이 필요합니다.
  예를 들어, 스택이나 링크드 리스트와 같은 자료구조를 사용하여 페이지의 순서를 유지하거나, 타임스탬프나 카운터와 같은 방법으로 마지막 참조 시간을 기록해야 합니다.
  이러한 작업들은 추가적인 메모리 공간과 CPU 시간을 소모합니다.

LFU(Least Frequently Used)

LFU(Least Frequently Used)는 가장 적게 사용된 페이지를 교체하는 알고리즘입니다.
각 페이지마다 참조 횟수(reference count)를 기록하고, 참조 횟수가 가장 낮은 페이지를 선택하여 교체합니다.
이 알고리즘은 장기적인 사용 빈도를 고려하기 때문에, 한 번만 사용되고 다시 사용되지 않을 페이지를 효과적으로 제거할 수 있습니다.

문제점

하지만 LFU에는 한 가지 문제점이 있습니다. 바로 오래된 페이지가 계속해서 메모리에 남아있을 수 있다는 것입니다.
예를 들어, 처음에 많이 사용되었던 페이지가 나중에는 사용되지 않더라도, 참조 횟수가 높아서 교체 대상에서 제외될 수 있습니다. 이런 경우, 메모리에 불필요한 페이지가 남아있게 되고, 페이지 부재가 늘어나게 됩니다.

문제점 해결 방법

이러한 문제점을 해결하기 위해, LFU의 변형 알고리즘들이 제안되었습니다.
예를 들어, 시간 감쇠(time decay) 기법을 사용하여, 오래된 참조 횟수에 감쇠 인자(decay factor)를 곱하여 참조 횟수를 감소시키는 방법이 있습니다. 이렇게 하면, 오래된 페이지의 우선 순위를 낮출 수 있습니다.

클럭 알고리즘

FIFO(First In First Out) 알고리즘을 개선한 방법입니다.
FIFO 알고리즘은 가장 먼저 적재된 페이지를 교체하는데, 이는 최근에 사용된 페이지가 교체될 가능성이 있습니다.
클럭 알고리즘은 각 페이지에 참조 비트(reference bit)를 부여하여, 참조 비트가 0인 페이지만 교체 대상으로 고려합니다. 참조 비트는 페이지가 사용될 때마다 1로 설정되고, 교체할 페이지를 선택할 때마다 0으로 초기화됩니다. 이렇게 하면 최근에 사용된 페이지는 참조 비트가 1이므로 교체에서 제외되고, 오랫동안 사용되지 않은 페이지는 참조 비트가 0이므로 교체될 가능성이 높아집니다.

진행 순서

1. 메모리에 적재된 모든 페이지의 참조 비트를 0으로 초기화합니다.

2. 새로운 페이지를 적재할 때, 현재 가리키고 있는 페이지의 참조 비트를 확인합니다.

3. 참조 비트가 0이면, 해당 페이지를 새로운 페이지로 교체하고, 포인터를 다음 페이지로 이동시킵니다.

4. 참조 비트가 1이면, 해당 페이지의 참조 비트를 0으로 초기화하고, 포인터를 다음 페이지로 이동시킵니다. 이 과정을 반복하여 참조 비트가 0인 페이지를 찾습니다.

쓰레싱

쓰레싱은 컴퓨터 시스템에서 메모리가 부족할 때 발생하는 현상입니다.
집중적으로 참조되는 페이지들의 집합을 메모리에 한꺼번에 적재하지 못하면 페이지 부재율이 크게 상승해 CPU 이용률이 급격히 떨어질 수 있는데 이와 같은 현상을 쓰레싱이라고 합니다.

쓰레싱은 시스템의 성능을 저하시키는 주요 원인 중 하나입니다. 쓰레싱이 발생하면 메모리와 디스크 사이에 데이터를 옮기는 시간이 많이 소요되어, 실제로 프로세스가 실행되는 시간이 줄어들게 됩니다.
즉, 시스템은 데이터를 옮기느라 바쁘고, 프로세스는 실행되지 못하는 상태가 되는 것입니다.

쓰레싱을 방지하거나 줄이는 방법

• 메모리 용량을 늘리기
  메모리 용량을 늘리면 가상 메모리를 사용할 필요가 줄어들어, 쓰레싱의 발생 가능성이 낮아집니다.

• 프로세스 관리하기
  프로세스의 개수와 우선순위를 적절하게 조절하여, 메모리의 사용량을 균형있게 유지할 수 있습니다.

• 스와핑 정책 변경하기
  스와핑은 메모리에 있는 프로세스를 디스크로 옮기는 작업입니다. 스와핑 정책을 변경하여, 자주 사용되는 프로세스는 메모리에 유지하고, 잘 사용되지 않는 프로세스는 디스크로 옮기도록 할 수 있습니다.

• 알고리즘을 사용해 MPD를 적절히 조절하기
  MPD(Multi-Programming Degree)란 메모리에 동시에 올라가 있는 프로세스의 수를 의미합니다.
  MPD를 적절히 조절해 CPU 이용률을 높이는데 워킹셋 알고리즘과 페이지 부재 빈도 알고리즘이 사용됩니다.

워킹셋 알고리즘

프로세스는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있습니다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라고 합니다.

워킹셋 알고리즘은 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 뜻합니다.
워킹셋 알고리즘에서는 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 워킹셋이라고 정의하고, 프로세스의 워킹셋을 구성하는 ㅍ이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당합니다.
만약 그렇지 않은 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킵니다.
이와 같은 방법으로 워킹셋 알고리즘은 MPD를 조절하고 스레싱을 방지하게 됩니다.

워킹셋을 구하는 방법

워킹셋 윈도우를 사용합니다.
윈도우의 크기를 L이라고 했을 때 시간 [T - L, T] 사이에 참조된 서로 다른 페이지들의 집합을 워킹셋으로 정의합니다.

메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장합니다.
이는 MPD를 줄이는 효과를 발생시킵니다.
반면 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당함으로써 MPD를 증가시킵니다.
이러한 방식으로 CPU 이용률을 높게 유지하면서 MPD를 적절히 조절해 스레싱을 방지합니다.

적절한 윈도우 크기의 중요성

윈도우의 크기가 너무 작으면 지역성 집합을 모두 수용하지 못할 수 있습니다.
윈도우의 크기가 너무 크다면 여러 규모의 지역성 집합을 수용할 수 있는 반면 MPD가 감소해 CPU 이용률이 낮아질 수 있습니다.

워킹셋 크기의 변화

워킹셋의 크기는 시간이 흐름에 따라 변합니다.
위의 그림에서 시간이 t1일 땐 워킹셋이 5개의 페이지로 구성되는 반면, t2일 때에는 워킹셋이 2개의 페이지로 구성됩니다.
워킹셋 알고리즘은 이처럼 프로세스가 메모리를 많이 필요로 할 때에는 많이 할당하고 저게 필요로 할 때에는 적게 할당하는 일종의 동적인 프레임 할당 기능까지 수행합니다.

페이지 부재 빈도 알고리즘

프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해서 각 프로세스에 할당할 메모리 양을 동적으로 조절합니다.

어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에 할당된 프레임의 수가 부족하다고 판단하여 이 프로세스에게 프레임을 추가로 더 할당합니다.
이때 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라가 있는 프로세스의 수를 조절합니다.

반면 프로세스의 페이지 부재율이 하한값 이하로 떨어지면 이 프로세스에게 필요 이상으로 많은 프레임이 할당된 것으로 간주해 할당된 프레임의 수를 줄입니다.
이런 방식으로 메모리 내에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높입니다.

이러한 원리로 MPD를 조절하면서 CPU 이용률을 높이는 동시에 스레싱을 방지합니다.

참고

운영체제와 정보기술의 원리 - 반효경

iboysoft

geeksforgeeks