[운영체제] 가상 메모리

안녕하세요.

이번 글에서는 운영체제 중 가상메모리에 공부하고 정리한 글입니다.

가상 메모리(Virtual Memory)란

출처: https://www.fun-coding.org/post/virtualmemory.html#gsc.tab=0

프로세스가 Page라는 작은 단위(보통 4KB)로 구성된 논리 주소 공간(logical address space)을 사용하는 것을 가상 메모리라고 한다.

또한, 물리 메모리(physical memory)를 Page 크기와 동일한 크기인 Frame 단위로 관리해 Page Table을 통해 논리 주소 공간과 물리 주소 공간을 매핑한다.

이를 통해 CPU는 MMU(Memory Management Unit: CPU와 메모리 사이에서 논리 주소를 물리 주소로 변환하는 하드웨어 장치)를 통해 특정 Page와 매핑된 Frame을 참조하여 프로세스를 실행한다.

가상 메모리는 왜 필요했을까?

가상 메모리가 등장하기 전 프로세스를 메모리에 할당하기 위해 연속 할당 방식(Contiguous Allocation)이 일반적으로 사용되었다.

출처: https://forns.lmu.build/classes/spring-2018/cmsi-387/lecture-13R.html

연속 할당 방식은 프로세스를 물리 메모리의 비어있는 공간에 연속적으로 할당하는 방식이다. 연속 할당 방식의 문제는,

1. 남은 총 메모리 공간이 프로세스의 크기보다는 크지만, 남아있는 공간이 연속적이지 않아 프로세스를 할당할 수 없는 현상 즉, 외부 단편화(External Fragmentation) 문제가 발생
   • 압축(Compaction)을 통해 작은 조각을 큰 공간으로 만들 수 있지만, 메모리 이동 비용이 크다.
2. 물리 메모리 크기보다 큰 프로세스는 할당조차 할 수 없음

가상 메모리는 위 언급한 문제를 해결하기 위해 등장했다.

가상 메모리는 Page라는 작은 단위로 물리 메모리 공간에 불연속 할당(Non Contiguous Allocation)되기 때문에 외부 단편화 문제를 해결할 수 있다.

또한, 프로세스 전체를 한번에 할당하는 것이 아닌 수요(Demand)가 발생하면, 보조기억장치에서 해당 Page를 읽어와 물리 메모리의 빈 공간(free frame)에 할당 후 실행한다. 이를 Page Fault라고 한다.

때문에 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 된다

Page Table

페이지 테이블은 가상 메모리의 페이지 번호를 물리 메모리의 프레임 번호로 변환할 때 사용되는 일종의 표이다.

Page Table은 운영체제에 따라 관리하는 정보와 관리 방식이 달라질 수 있다. 하지만, 공통적으로 저장하고 있는 요소가 있다.

• Page Number와 Frame Number
  • page 번호에 해당하는 frame 번호
• Vaild Bit
  • 해당 page가 물리 메모리에 로드되어 있는지 여부를 나타내는 값
  • 메모리에 로드되어 있지 않다면 Page Fault 발생
• Protection Bit
  • page의 일기/쓰기/실행 권한을 나타내는 값
• Dirty Bit
  • 해당 페이지의 데이터가 수정이 발생했는지 나타내는 값
  • 수정이 발생했다면, 보조기억장치에 저장되어 있는 값 또한 변경이 필요하기 때문에 이를 판단하기 위한 값으로 사용
• Reference Bit
  • CPU가 해당 페이지의 접근 여부를 나타내는 값
  • 페이지 교체 알고리즘에 사용되는 값

페이지 교체 알고리즘(Page Replacement Algorithm)

특정 page가 Demand 돼서 물리 메모리의 frame에 할당되어야 할 때 비어있는 frame(free-frame)이 없을 때 해당 더 이상 사용되지 않는 프레임(victim frame)을 찾아 Demand Page와 Page Fault 시키는 알고리즘을 페이지 교체 알고리즘(Page Replacement Algorithm)이라고 한다.

Page Fault는 보조기억창지로 부터 읽어와 메모리에 로드 시키는 과정이 필요하기 때문에 꽤 많은 처리 시간이 발생한다.

때문에 Page Fault가 발생하는 횟수가 곧 알고리즘의 선능을 나타내는 지표가된다.

Page Fault의 발생 확률에 따른 성능

EAT = (1 - p) * MA + p * (Page Fault Time)

• MA  (Memory Access Time, 메모리 접근 시간)
  • 페이지 폴트가 발생하지 않았을 때 메모리에 접근하는 데 걸리는 시간
• p  (Page Fault Rate, 페이지 폴트 발생 확률)
  • 페이지 폴트가 발생할 확률
• Page Fault Time (페이지 폴트 처리 시간)
  • 페이지 폴트가 발생했을 때, 디스크에서 페이지를 읽어오고 처리하는 데 걸리는 시간

FIFO

FIFO 알고리즘은 먼저 메모리에 page-in 한 page를 page-out 시키는 알고리즘.

다음과 같은 Reference String이 주어졌을 때, 총 15번의 Page Fault가 발생

FIFO 알고리즘은 가장 단순하고 구현이 쉽다는 장점이 있다. 하지만 성능이 떨어짐.

OPT(Optimal Page Replacement Algorithm)

OPT 알고리즘은 앞으로 가장 오랫동안 사용되지 않은 page를 우선적으로 page-out 시키는 알고리즘.

다음과 같은 Reference String이 주어졌을 때, 총 9번의 Page Fault가 발생

하지만, OPT 알고리즘은 이론적인 알고리즘으로 현실적으로 구현할 수 없음. victim frame 선정하는 시점에서 미래에 사용되지 않을 프레임을 알아야하기 때문이다.

OPT는 페이지 교체 알고리즘 성능의 기준으로 사용되는 경우가 많음.

LRU(Least Recently-Used)

LRU 알고리즘은 과거에 가장 오래 사용되지 않은 page를 우선적으로 page-out 시키는 알고리즘.

다음과 같은 Reference String이 주어졌을 때, 총 12번의 Page Fault가 발생

LRU는 특정 page가 Demand 되면 앞으로도 Demand될 가능성이 높다는 가정하에 등장했다.

실제로 한번 Demand된 page는 일정 시간동안 지속적으로 사용될 가능성이 높다.

실현 가능한 알고리즘 중 LRU가 OPT에 가장 가까운 성능을 보인다. 하지만, LRU는 마지막으로 사용된 페이지를 추적해야 하기 때문에 메모리와 연산 시간이 많이 필요하다.

따라서 운영체제 및 캐시 시스템에서는 LRU에서 파생된 알고리즘이 많이 사용된다.

앞서 언급한 페이지 테이블의 참조 비트를 활용한 페이지 교체 알고리즘(대표적으로 CLOCK 알고리즘)이 운영체제에서 널리 사용된다.

Thrashing

Thrashing이란, 동시에 동작하는 프로세스에 수가 증가함에 따라 CPU 사용률이 증가하다가 급 감소하는 지점

Thrashing은 프로세스들이 충분한 프레임을 확보하지 못하여 페이지 폴트가 과도하게 발생할 때 발생한다. 이때 프로세스당 할당된 프레임 수가 부족하면 페이지 폴트가 빈번하게 발생한다.

페이지 폴트가 자주 발생하면,

1. 운영체제가 페이지 교체 작업을 반복적으로 수행
2. 그로 인해 CPU는 페이지 폴트 처리를 위한 운영체제 작업에 많은 시간을 소비
3. 그 결과 프로세스의 실제 실행보다는 운영체제의 페이지 교체 작업에 CPU 리소스가 집중
4. 시스템 성능이 급격히 저하

Frame Allocation

Thrashing으로 인한 CPU 성능 저하를 최소화 하기 위해 프로세스 마다 프로세스 구동에 충분한 프레임을 할당해줘야 한다.

작업 집합 모델(Working-Set Model)

작업 집합 모델은 지역성(locality)에 대한 가정에 기반한다. 윈도우의 크기(Δ)를 설정하고, 윈도우 크기안에 들어온 page 수 만큼 frame을 할당한다.

때문에 원도우의 사이즈에 따라 성능이 좌우된다. 원도우의 사이즈가 너무 크면 필요 이상으로 frame이 할당되고, 너무 작으면 page fault 확률이 늘어난다.

작업 집합 모델의 윈도우는 슬라이딩 원도우 형태이기 때문에 한쪽으로 새로운 page가 들어오고 반대쪽으로 빠져나간다. 때문에 작업 집합 모델은 지역성에 따라 집합이 전환되는 구간에서 집중적으로 page fault가 발생한다.

새로운 지역성을 처음으로 수요(demand-paging)하게 되면 페이지 page fault율이 높아진다. 그러나 일단 이 새로운 지역성에 속한 페이지들이 원도우에 모두 올라오면 페이지 page fault율은 다시 떨어진다.

즉, 한 피크에서 다음 피크가 시작되기까지의 시간 구간은 이전 워킹셋에서 새로운 워킹셋으로의 전환 기간을 의미한다.

페이지 폴트 빈도(Page-Fault Frequency, PFF)

PFF는 작업 집합 모델보다 단순하지만, 효과적일 수 있다.

PFF는 page fault 비율에 따라 빈번하게 발생하면 해당 프로세스의 frame 수를 늘리고, 반대의 경우 frame 회수해 다른 프로세스가 사용할 수 있도록 하여 page fault 횟수를 일정하게 유지하는 방법이다.