[CS] 가상 메모리 (Virtual Memory)

메모리 (Memory)

• 프로그램과 프로그램 수행에 필요한 데이터 및 코드를 저장하는 장치
• 메모리는 크게 내부 기억장치인 주기억장치(DRAM, CPU 안에 있는 레지스터와 캐시)와 외부 기억장치인 보조 기억장치(SSH, HDD)로 분류된다.

 

가상 메모리 등장 배경

1. 초창기 컴퓨터에서는 사용 가능한 RAM 의 용량이 가장 큰 실행 애플리케이션의 주소 공간보다 커야 했다.

• 그렇지 않을 경우 "메모리 부족" 오류로 인해 해당 애플리케이션을 실행할 수 없었다.
• 즉, 컴퓨터에 실제로 장착된 물리 메모리(RAM)의 최대 크기는 CPU 에 의해 제한되기 때문에 *운영체제는 물리 메모리보다 큰 *프로세스를 실행시킬 수 없었다.
  • 운영체제 : 컴퓨터 시스템의 핵심 소프트웨어로, 컴퓨터 하드웨어와 응용 프로그램 간의 상호작용을 관리하고 제어하는 역할을 한다.
  • 프로세스 : 운영체제로부터 필요한 메모리와 자원을 할당받아 실행되는 작업의 단위

2. 이후 컴퓨터에서는 프로그래머가 애플리케이션의 일부분만 기억장치에 올려 실행하도록 지정할 수 있게 하는 오버레이 기법을 사용하여 메모리 부족 문제를 해결하고자 했다.

• 하지만 오버레이를 사용하는 프로그램은 그렇지 않은 프로그램보다는 메모리를 덜 사용했지만, 애초에 시스템이 프로그램을 위한 충분한 메모리를 갖추고 있지 않은 경우에는 결국 똑같은 메모리 부족 오류가 발생하여 해결할 수 없었다.

3. 여기에서 더 발전한 가상 메모리 기법은 애플리케이션을 실행하는 데 얼마나 많은 메모리가 필요한지에 집중하지 않고, 대신 애플리케이션을 실행하는 데 최소한 얼마만큼의 메모리가 필요한가에 집중하여 문제를 해결하고자 했다.

• 이러한 접근 방식이 가능한 이유는 메모리 접근은 순차적이고 지역화되어 있기 때문이다.
• 이렇게 애플리케이션의 일부분만 메모리(기억장치)에 올려지고, 메모리에 올라가지 않는 나머지는 보조 기억장치인 디스크로 위치한다.
• 즉, 프로세스 전체가 메모리에 올라오지 않아도 실행이 가능하다.

 

가상 메모리 (Virtual Memory)

• 메모리가 실제 메모리보다 많아 보이게 하는 기술
• 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않더라도 실행이 가능하다는 점에 착안하여 고안된 메모리 기법
• 애플리케이션이 실행될 때, 실행에 필요한 일부분만 메모리에 올라가며 애플리케이션의 나머지는 디스크에 남게 된다.
  • 결국 빠르고 작은 기억장치(RAM)를 크고 느린 기억장치(디스크)와 병합하여, 하나의 크고 빠른 기억장치(가상 메모리)처럼 동작하게 하는 것이다.
• 가상 메모리를 구현하기 위해서는 컴퓨터가 특수 메모리 관리 하드웨어(MMU)를 갖추고 있어야만 한다.

 

MMU (Memory Management Unit)

• 가상 주소를 물리 주소로 변환하고, 메모리를 보호하는 기능을 수행한다.
• CPU 가 각 메모리에 접근하기 이전에 메모리 주소 번역 작업이 수행된다.
• 그러나 메모리를 일일이 가상 주소에서 물리 주소로 번역하게 되면 작업 부하가 너무 높아지므로, MMU 는 RAM 을 여러 부분(페이지)으로 나누어 각 페이지를 하나의 독립된 항목으로 처리한다.

 

가상 주소 (Virtual Address)

• 프로세스가 참조하는 주소
• 가상 주소는 프로세스마다 독립적으로 할당되며, 프로세스는 자신만의 가상 주소 공간을 가지고 있다고 생각한다. 
• 가상 주소는 논리적인 주소이다. 운영체제는 프로세스에게 연속된 가상 주소 공간을 제공하고, 이를 필요한 크기의 물리 메모리 페이지로 매핑한다. 이 작업으로 메모리 공간의 낭비를 최소화할 수 있다.
• 만약 가상 주소를 사용하지 않고 프로세스의 모든 데이터들을 물리 주소로 접근한다고 생각해 보면, 여러 개의 프로세스들이 실행되면서 같은 물리 주소를 접근해서 데이터를 수정하고, 민감 데이터를 쉽게 읽어온다면 오류가 발생할 것이다.
• 프로세스마다 다른 가상 주소를 사용하면 같은 물리 주소 위치를 가리키고 있을 수 있지만, 읽고 쓰고 할 수 있는 공간은 가상 주소 공간에서만 제한되므로 실제 물리 주소의 데이터들이 수정되거나, 프로세스들이 동시에 접근해서 충돌하는 일은 없을 것이다.

 

물리 주소 (Physical Address)

• 실제 메모리의 주소이며 하드웨어에서 직접 접근 가능한 주소이다.
• 시스템 전체적으로 공유되는 주소이며, 여러 프로세스가 공유 메모리 영역을 사용할 때 사용된다.
• 프로세스가 물리 주소로 접근하려면, 물리 주소를 가리키고 있는 가상 주소를 물리 주소로 변환해야 한다.

 

요구 페이징 (Demand Paging)

• 특정 페이지에 대해 CPU 요청이 들어온 후에 해당 페이지를 메모리에 적재한다.
• CPU 가 요청할 때 프로세스의 데이터를 메모리에 올리는 것을 의미한다.
• 처음부터 모든 데이터를 메모리로 적재하지 않고, 필요한 부분만 물리적 메모리에 페이지 단위로 적재한다.
• 메모리 사용량이 감소하고, 프로세스 전체를 메모리에 적재하는 입출력 *오버헤드도 감소하는 장점이 있다.
  • 오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간 · 메모리
• *유효/무효 비트(valid/invalid bit)를 두어 각 페이지가 메모리에 존재하는지 표시하게 된다.
  • 유효/무효 비트 : 해당 비트가 유효하면 메모리에 있음을 의미하고, 무효하면 메모리에 없음을 의미한다.

 

페이지 폴트 (Page Faults)

• 어떤 페이지에 접근하려고 했을 때 해당 페이지가 실제 물리 메모리에 부재할 때 뜨는 인터럽트
• 어떤 프로그램이 자신의 주소 공간(가상 메모리 공간)에는 존재하지만 시스템의 RAM 에는 현재 존재하지 않는 데이터·코드에 접근을 시도할 경우 발생하는 현상을 의미한다.
• 페이지 폴트가 발생하면 운영체제가 그 데이터를 메모리로 가져와서 문제를 해결한 뒤 다시 동일한 명령을 수행하는 식으로 동작한다.
• 자주 일어날수록 운영체제의 성능이 많이 저하되기 때문에 페이지 폴트가 일어나지 않도록 하는 것이 중요하다.
• 페이지 폴트를 최소화하기 위한 방법으로는 *페이지 교체 정책(page replacement policy)이 있다.
  • 메모리가 꽉 차있을 때 기존 페이지 중 하나를 물리 메모리에서 저장 매체로 내리고, 새로운 페이지를 방금 비워진 해당 물리 메모리 공간에 올린다. 이때 기존 페이지 중 어떤 것을 내리면 좋을지에 대한 알고리즘을 짠 것이 바로 *페이지 교체 알고리즘이다.

 

페이지 교체 알고리즘(정책)

1. FIFO (First In First Out)

• 메모리에 가장 먼저 올라온 페이지를 우선적으로 교체하는 알고리즘
• 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐에 저장하는 방식 등을 사용하여 수행한다.
• 단점 : 페이지의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있다.
  • 예를 들어, 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행 속도가 떨어질 위험이 있다.

 

2. LRU (Least Recently Used)

• 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘
• 최근에 참조된 페이지가 미래에 다시 참조될 가능성이 높다는 시간 지역성 성질을 활용했다.
• 각 페이지에 *카운터를 두어 마지막으로 사용된 시간을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거한다.
  
  • 카운터 : 각 페이지마다 존재하는 논리적인 시계(Logical Clock)로, 해당 페이지가 사용될 때마다 카운터를 0으로 초기화한 후 시간을 증가시킨다.
• 사용한 데이터를 큐에서 제거한 후, 해당 데이터를 맨 위로 다시 올린다. 만약 프레임이 부족할 경우, 큐의 맨 아래에 있는 데이터를 삭제하여 공간을 확보한다.
• 단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생한다.

 

3. LFU (Least Frequently Used)

• 참조 횟수가 가장 낮은 페이지를 교체하는 알고리즘
• 페이지의 참조 횟수로 교체할 페이지를 결정한다.
• LRU 는 직전 참조된 시점만을 반영하는 반면, LFU 는 참조 횟수를 기반으로 하여 장기적인 시간 규모에서의 참조 성향을 고려할 수 있다.
• 단점 : 가장 최근에 불러온 페이지가 교체될 수 있다. 구현이 더 복잡하다. 막대한 오버헤드가 발생한다.

 

4. NUR (Not Used Recently)

• 최근에 사용하지 않은 페이지를 교체하는 *클럭 알고리즘
  • 클럭 알고리즘 : 하드웨어적인 자원을 통해 기존(LRU, LFU) 알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식
• LRU 는 가장 오래전에 참조된 페이지를 교체하는 반면, NUR 은 오랫동안 사용하지 않은 페이지 중 하나를 교체한다.
  • 최근에 참조되지 않은 페이지를 교체 대상으로 선정한다는 측면에서 LRU 와 유사하지만, 교체되는 페이지의 참조시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU 를 근사시킨 알고리즘으로 볼 수 있다.
• 동일 그룹 내에서 선택 무작위
• 각 페이지마다 두개의 비트 *참조 비트(Reference Bit)와 *변형 비트(Modified Bit, Birty Bit)가 사용된다.
  • 참조 비트: 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)
  • 변형 비트: 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
• 우선순위 : 참조비트 > 변형비트

 

[ NUR 동작 방식 ]

1. 페이지가 메모리에 처음 적재될 때, 각 페이지에 참조 비트와 변형 비트를 0으로 초기화한다.
2. 읽기 작업이 발생하면 해당 페이지의 참조 비트를 1로 설정하고, 쓰기 작업이 발생하면 해당 페이지의 참조 비트와 변형 비트를 1로 설정한다.
3. 일정한 시간 간격으로 모든 페이지의 참조 비트를 0으로 초기화하여 최근 접근 여부를 새롭게 갱신할 수 있도록 준비한다. 변형 비트는 리셋하지 않고 유지한다.
4. 페이지 폴트가 발생했을 때, 메모리에 적재된 모든 페이지를 참조 비트와 변형 비트의 값에 따라 분류한다.
5. 우선순위가 가장 낮은 범주를 가진 페이지를 교체 대상으로 선택한다(동일한 범주의 페이지가 여러 개일 경우, 무작위로 선택한다).
6. 교체 대상이 변형 비트가 1인 경우, 해당 페이지를 디스크에 기록한 후 새로운 페이지를 적재하고, 변형 비트가 0인 경우, 바로 교체한다.

우선순위	참조 비트	변형 비트	내용
1 (가장 낮은 비용)	0	0	최근에 사용되지 않았고, 수정되지 않음.
2	0	1	최근에 사용되지 않았지만, 수정됨.
3	1	0	최근에 사용되었지만, 수정되지 않음.
4 (가장 높은 비용)	1	1	최근에 사용되었지만, 수정됨.

 

5. OPT (Optimal)

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 찾아 교체하는 알고리즘
• 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 전제조건이 필요하다.
  
• 이 전제 조건이 실제 활용에서는 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘 이다.

 

페이지 정보 캐시 (TLB : Translation Lookaside Buffer)

• 가상 메모리 주소를 물리적 주소로 변환하는 속도를 높이기 위해 사용하는 캐시
• 최근에 일어난 가상 메모리와 물리 주소의 변환 테이블을 저장해 둔다.
• CPU 가 가상 주소를 가지고 메모리에 접근하려고 할 때 우선은 TLB 에 접근하여 가상 주소에 해당되는 물리 주소를 찾고, 만약 TLB 에 매핑이 존재하지 않는다면 MMU 가 페이지 테이블에서 해당되는 물리 주소로 변환한 후 메모리에 접근하게 된다.
• MMU 에 포함되어 있는 작은 캐시로, 일종의 주소 변환 캐시라고 할 수 있다.
• 장점 : 물리 주소를 갖고 있으면 메모리(RAM)에 두 번 들릴 필요 없이, 바로 해당 물리 주소(in 메모리)를 찾아갈 수 있다.

 

캐시 메모리 (cache memory)

• 속도가 빠른 장치와 느린 장치 사이에서 속도 차에 따른 *병목 현상을 줄이기 위한 범용 메모리
  • 병목 현상 : 전체 시스템의 성능이나 용량이 하나의 구성 요소로 인해 제한을 받는 현상
• 예를 들어, CPU 에서의 캐시 메모리는 CPU 코어(고속)와 메모리(CPU 에 비해 저속) 사이에서 속도 차에 따른 병목 현상을 완화하는 역할을 한다.
• 또한, 인터넷 웹 브라우저에는 캐시 파일이라는 개념이 있는데 캐시 파일은 웹 페이지 상의 이미지 등을 하드디스크에 미리 저장해 두고, 다음번에도 해당 웹 페이지에 접근할 때 해당 사이트에 이미지를 다시 요청하는 게 아니라 하드디스크에서 이미지를 불러들여 로딩 속도를 높이는 역할을 한다.
• 즉 캐시 파일은 비교적 속도가 빠른 하드디스크와 상대적으로 느린 웹 페이지 가운데서의 병목을 줄이는 역할을 한다.

---

[운영체제] 가상 메모리(Virtual Memory System)

[운영체제] 가상 메모리란?

가상메모리(virtual memory)

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR

가상메모리-02-페이지 교체 알고리즘

[OS] 페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR)