Virtual Memory 에 대해서

이 글은…

이번 포스팅에서는 virtual memory에 대해서 다룬다. 그런데 virtual memory를 제대로 이해하기 위해서는 필요한 배경지식이 상당히 많고 여러가지 개념들이 기초가 되어 virtual memory 시스템을 만들게 되는 것 같다.

그래서 글 초반부에는 virtual memory에 들어가기 전에 관련 배경 지식들에 대해서 설명한다. 먼저 우리가 프로그램을 실행시킬 때 어떻게 메모리에 올라갈지부터 고민을 시작한다. 그래서 어떻게 하면 하나의 메모리에 여러 개의 프로세스를 올릴 수 있는지, 여러 개의 프로세스들에게 어떻게 효율적으로 메모리를 분배할지에 대해서 정리한다.

그리고 그 뒤에 virtual memory에 대해서 정리를 시작하는데 virtual memory는 기존의 방법으로 메모리를 프로세스에게 할당할 때 발생하는 문제점을 해결하기 위해서 등장했다. 어떻게 virtual memory 시스템이 이러한 문제를 해결했는지에 대해서 살펴본다.

너무 구체적인 토픽들에 대해서는 다루지 않았다. 최대한 virtual memory가 등장하게된 배경과 큰 개념들을 정리하려고 노력했다. 글을 쓰면서도 좀 더 자세히쓰면 좋지 않을까, 혹은 이 부분은 너무 추상화해서 쓴 것 같은데 하는 부분이 있지만 그랬다가는 이 글을 다 못 끝낼 것 같아서 너무 구체적이거나 메모리와 관련이 없는 토픽들은 쳐냈다.

Background

Physical Memory

실행가능한 바이너리 파일이 실행되기 위해서는 파일이 물리 메모리에 올라가야하고 프로그램이 실행되는 동안 사용되는 변수들이나 중간 연산 결과들도 물리 메모리에 올라가야한다. 왜냐하면 모든 연산은 CPU를 통해서 수행되는데 CPU는 연산의 타겟이 되는 값들을 모두 물리 메모리에서 읽기 때문이다.

그럼 여기서 고민이 생긴다. 우선 바이너리 파일의 크기가 물리 메모리 크기보다 작다고 가정을 했을 때 바이너리 파일을 물리 메모리 중 어느 위치에 시작하도록 해야할까?

물리 메모리는 단순하게 보면 0부터 시작하는 길이 N의 배열이라고 생각할 수 있다. 그리고 각각의 인덱스에는 물리 메모리의 주소가 붙는다. 우리가 실행하려고하는 바이너리 파일은 길이 m의 배열이라 생각할 수 있고 [latex] m << N [/latex] 이라고 생각할 수 있다.

우리의 컴퓨터가 한 번에 하나의 프로그램만 동작하도록 설계되었다면 별 고민 없이 ‘아무’ 곳이나 길이 m의 바이트 배열을 전체 물리 메모리 중에 올리면 된다. 그런데 실제 컴퓨터는 한 순간에 여러 개의 프로그램이 떠 있을 수 있다.

Memory Protection

프로세스가 여러 개 떠 있을 수 있다면 고민해야할 것이 늘어나는데 그 중 하나가 하나의 프로세스가 다른 프로세스의 메모리 영역을 침범하지 않도록 해야한다는 것이다.

왜냐하면 서로 다른 프로세스가 분리된 영역에 해당 프로세스를 실행시킬 수 있는 데이터와 인스트럭션이 올라와있어야 여러 프로그램을 안전하게 동시에 (혹은 동시처럼 보이지만 순차적으로) CPU 제어권을 각각의 프로세스로 넘기면서 실행시킬 수 있기 때문이다.

그래서 어떤 프로세스의 주소 공간을 참조할 때 해당 주소가 다른 프로세스의 주소 공간을 침범하지 않았는지 검사를 한다. 이는 퍼포먼스 이슈로 하드웨어 레벨에서 주소 검증 검증이 이뤄지고 일반적으로 두 개의 레지스터를 통해서 이루어진다.

base register는 특정 프로세스의 주소 공간 중 가장 작은 주소 값을 담고 있다. 그리고 limit register는 해당 프로세스가 가지고 있는 주소 공간의 크기를 가지고 있다. 예를 들어 base register가 300040이라는 값을 가지고 있고 limit register가 120900이라는 값을 가지고 있다면 해당 프로세스의 주소 영역은 300040부터 420940 (= 300040 + 120900)가 된다.

CPU 제어권이 특정 프로세스로 넘어가면 context switching 과정이 일어나고 이 때 커널은 base register와 limit register의 값을 다시 PCB에서 불러와 저장한다. CPU는 이전에 실행했던 PC의 다음 주소의 인스트럭션을 실행시키면서 여러 메모리 값을 읽고 다시 쓴다. 이 때 메모리 주소에 대한 검증을 거친다. 지금 내가 읽고 있는 메모리 주소가 다른 프로세스의 주소 영역은 아닌지 커널 영역의 주소 영역은 아닌지에 대한 체크를 하는 것이다.

1. CPU가 참조하려는 메모리 주소를 먼저 base register에 저장된 주소 값과 비교한다.
2. CPU가 참조하려는 메모리 주소를 base register에 저장된 주소 값 + limit register에 저장된 크기 값과 비교한다.

참조하는 주소는 1번 값보다 같거나 커야하고 2번 값보다 작아야 유효한 주소로 인정이 된다. 만약 그렇지 않다면 trap이 발생한다.

하나 기억할 것은 이러한 주소 영역에 대한 검증은 user mode로 동작할 때 이루어진다는 것이다. kernel mode로 동작할 때는 주소 접근 제한이 없어진다. 그렇기 때문에 커널은 시스템콜이 발생했을 때 커널 주소 영역에서 해당 시스템 콜 핸들러를 동작시키기도하고 I/O 과정을 수행할 수도 있는 것이다.

Address Binding

소스 코드로부터 실행 가능한 바이너리 파일이 되고 실행되기까지를 컴파일 시점(Compile time), 로딩 시점(Loading time), 실행 시점(Execution time)으로 세 단계로 구분할 수 있다.

각 단계에서는 사실 복잡한 일들이 일어나지만 우선은 프로그램이 올라갈 메모리 주소가 어떻게 결정되는지에 대해서 집중해서 살펴보자.

• 컴파일 시점 (Compile time): 컴파일 시점 (Compile time)에 해당 바이너리 파일이 물리 메모리 중 어떤 주소에서 실행될지 결정될 수 있다. 그런데 컴파일 시점에 최종적으로 물리 메모리 몇 번 째 주소에 올라갈지 절대 주소가 결정되면 다음과 같은 문제점이 발생할 수 있다. 예를 들어 카카오톡, 트위치같은 사용자 프로그램이 서로 겹치는 주소 영역에 올라가도록 절대 주소가 결정되었다면 두 프로그램을 동시에 실행시키기 위해서 둘 중 한 프로그램을 다른 주소 영역에 올라갈 수 있도록 새로 컴파일 해주어야하는 번거로움이 생긴다.
• 로딩 시점 (Loading time): 로딩 시점에 메모리 주소를 결정한다고 하면 컴파일 단계에서 소스 코드의 변수나 함수와 같은 심볼들에 대해서 각각 relocatable 주소를 생성해주게 된다. relocatable 주소는 간단히 말하면 해당 프로그램의 시작점으로부터의 상대적인 주소를 나타낸다. 그리고 이 상대적인 주소는 로딩 시점에 해당 프로그램이 물리 메모리의 몇 번째 시작 주소로 올라갈지 결정되면서 최종적으로 절대 주소가 결정된다.
• 실행 시점 (Execution time): 그런데 만약에 실행되고 있는 프로세스의 메모리의 영역이 프로그램이 실행되고 있는 도중에 바꾸고 싶다면 로딩 시점에 최종 절대 주소가 결정되면 문제가 된다. 이와 같은 경우 절대 주소는 별도의 하드웨어의 도움을 받아 실행 도중에 동적으로 주소가 결정되어야 하는데 이는 뒤에서 살펴볼 예정이다.

Logical Address Space vs. Physical Address Space

로딩 시점과 실행 시점에 주소가 결정될 때 언급된 상대적인 주소를 더욱 잘 이해하기 위해서는 Logical Address Space와 Physical Address Space에 대해서 이해할 필요가 있다.

CPU가 바이너리 파일의 인스트럭션으로부터 읽는 주소는 logical address 라고 부른다. 이는 실제 물리 메모리 주소 값이 아닌데 memory-management unit (MMU)가 logical address를 실제 물리 메모리의 주소 physical address로 바꾸게 된다.

컴파일 시점과 로딩 시점에서 절대 주소가 바인딩 된다면 logical address와 physical address는 동일한 값을 가진다. 실행 시점에 주소가 결정될 때만 logical address와 physical address가 달라지는데 이 때 일반적으로 logical address를 virtual address라고 부른다.

위에서도 이야기했지만 virtual address를 physical address로 바꿔주는 곳은 MMU라는 하드웨어에서 이루어지고 하드웨어마다 어떻게 변환시킬지에 대한 알고리즘은 다르다. 위의 예시에서는 base register가 해당 프로세스가 시작하는 베이스 주소를 가지고 있고 virtual address에 이 주소 값을 더해서 physical address로 변환시켜주고 있다. 이전에 소개되었던 base register를 이제 relocation register라고 부를 것이고 MMU는 relocation register를 통해서 주소 변환을 한다.

이렇게 실행 시점에 MMU를 통해서 주소가 변환되는 경우 사용자 프로그램에서는 자신이 어떤 주소에 올라갈지 알 수 없다. 그리고 알 필요도 없다. 사용자 프로그램은 logical address를 통해 값을 불러오고 연산하고 저장하는 로직을 전개하면 된다. 

정리하면 주소를 바라보는 뷰는 두 가지 방식이 존재한다. 

하나는 virtual address space로 바라보는 방식이고 이는 사용자 프로그램이 컴퓨터 메모리를 바라보는 시점이다. 이 주소 공간은 0 ~ max 값의 범위로 이루어진 공간이다. 

두 번째는 physical addresse space로 바라보는 방식이다. 이는 주로 운영체제가 주소 공간을 바라보는 방식인데 전체 메모리를 여러 개의 프로세스가 나눠 쓸 수 있고 하나의 프로세스가 사용할 수 있는 주소 공간의 범위는 [latex]R + 0[/latex] 부터 [latex]R + max[/latex] 값으로 표현할 수 있다. [latex]R[/latex]은 해당 프로세스가 시작하는 physical address의 시작 주소를 나타낸다. 그리고 virtual address가 사용되기 전에 해당 주소는 반드시 physical address로 매핑되어야 한다.

Swapping

그런데 우리가 할당할 수 있는 물리 메모리 양보다 더욱 많은 프로세스들을 띄우고 싶다. 이럴 때 사용할 수 있는 방법 중 하나가 당장 실행할 필요가 없는 프로세스가 있다면 해당 프로세스가 점유하고 있는 메모리를 backing store라는 곳으로 잠시 보관해두는 것이다. 그리고 나중에 다시 필요할 때 가져와서 물리 메모리에 올려놓는다.

이러한 메커니즘을 swapping이라고 부른다. backing store는 일반적으로 디스크를 사용한다. backing store는 모든 프로세스의 메모리 이미지를 저장할 수 있을 만큼 커야하고 직접 접근할 수 있어야 한다.

CPU 스케쥴러는 어떤 프로세스를 실행시킬지를 결정하고 dispatcher를 호출한다. dispatcher는 이제 실행시킬 프로세스의 메모리 이미지가 물리 메모리에 올라와있는지를 확인한다. 있다면 CPU 제어권을 사용자 프로세스로 넘겨서 실행시키면 되지만 그렇지 않다면 dispatcher는 다시 물리 메모리를 살펴 프로세스가 사용할 수 있는 메모리가 충분히 있는지 확인한다. 

공간이 충분하다면 backing store로부터 프로세스 메모리 이미지를 가져와서 올리면 된다. 그런데 만약 공간이 충분하지 않다면 공간을 확보하기 위해 현재 올라와 있는 프로세스 중에 backing store로 swap out할 프로세스를 정하여 swap out을 마치고 실행시킬 프로세스의 이미지를 메모리에 올린다.

이런 식으로 프로세스 전체를 swap-in, swap-out하는 방식은 오버헤드가 크기 때문에 사용되지 않는다. 이후에 살펴볼 paging과 virtual memory 부분을 살펴보면서 swapping 메커니즘이 다시 나타난다.

Memory Allocation

글 초반부에 프로그램이 프로세스가 되기 위해서는 물리 메모리에 올라가야한다고 이야기했다. 이는 결국 누군가가 프로세스가 사용할 수 있는 물리 메모리 중 일부를 확보하여 이것을 사용할 수 있도록 하게 만들어야한다는 뜻이다.

이러한 작업들은 운영체제가 담당하는데 프로세스가 메모리를 사용할 수 있도록 물리 메모리 중 특정 부분을 할당해준다. 그런데 하나의 물리 메모리를 여러 프로세스에게 최대한 효율적으로 사용할 수 있도록 나누어주어야한다. 어떻게 하는 것이 가장 효율적인 방법일까?

Contiguous Memory Allocation

가장 간단하게 떠올릴 수 있는 방법은 하나의 프로세스에서 필요한 메모리 영역을 물리 메모리에 연속된 영역에 올리는 방법이다. 다른 프로세스는 이전 프로세스가 끝나는 바로 다음 주소부터 시작해서 인접하게 올리는 것이다.

그리고 각각의 프로세스가 차지하고 있는 메모리 영역을 테이블에 기록하고 현재 해당 영역이 사용되고 있는지를 체크한다. 그리고 프로세스가 종료되면 해당 영역을 사용가능 하다고 테이블에 표시한다.

다른 프로그램을 실행시키기 위해서는 테이블을 보고 해당 프로그램을 실행시키는데 필요한 메모리 영역이 있는지를 확인한다. 만약에 충분한 영역이 있다면 해당 영역의 메모리를 할당하여 프로세스에게 넘겨주면 된다. 충분한 영역이 없다면 다른 프로세스가 끝나서 충분한 메모리 공간이 나올때까지 기다린다.

이러한 과정을 반복하다보면 메모리 중간중간에 크고 작은 구멍(hole)이 생긴다. 운영체제는 실행되기를 기다리는 프로세스 큐에서 대기 중인 프로세스를 살펴보고 현재 남은 메모리 공간에 올릴 수 있는 프로세스가 존재하는지를 살펴본다.

위와 같이 추상적으로 정리하고 이 부분은 마무리하겠다. 왜냐하면 메모리 중 어떤 영역에 프로세스를 스케쥴링 시킬지, 어떤 프로세스를 스케쥴링할지에 대해서는 다양한 알고리즘이 존재하기 때문이다. First fit, Best fit, Worst fit이 이러한 알고리즘에 속하고 우선은 큰 흐름을 보는 것이 더 중요하기 때문에 여기서 마무리한다.

Segmentation

지금까지 메모리를 어떤 바이트들의 청크들로 바라보았다. 하지만 개념적으로 우리는 프로세스가 할당되는 메모리를 단순한 바이트의 배열로 바라본다기 보다는 ‘어떤 함수가 사용하는 메모리’, ‘어떤 자료 구조가 사용하는 메모리’와 같이 소스 코드에서 표현되는 심볼들을 기반으로 메모리를 바라보는 것에 더욱 익숙하다.

심볼들을 기반으로 메모리를 바라보았을 때 각각의 심볼들이 사용하는 메모리의 구체적인 위치들은 중요하지 않다.

Segmentation은 이와 같이 사용자 프로그램이 사용하는 logical address space를 관리하는 기법 중에 하나이다. 이전에는 별 의미 구분없이 logical address space는 하나의 덩어리였다면 이제는 이 영역을 큰 의미 단위로 나눠서 어떤 부분은 코드를 저장하고 다른 부분은 스택(stack)이나 힙(heap) 영역에 대한 데이터를 저장한다. 그리고 이 영역 각각을 segment라고 부른다.

Segmentation은 프로그램을 링킹(linking) 하는 부분에서도 자세히 등장한다. 이 때는 주로 소스 코드에서 등장하는 심볼들에 대해서 어떻게 logical address를 부여할지에 대해서 다룬다. 그런데 지금은 segmentation을 메모리 할당, 관리라는 측면에서 살펴볼 것이다.

그래서 결국 logical address space는 여러 개의 segment들로 구성된다. 각각의 segment는 이름과 해당 영역의 길이가 존재한다.

각 segment 내에 속한 구체적인 심볼들에 대한 logical address를 찾을 땐 해당 심볼이 어떤 segment에 속하는지, 그리고 해당 segment 내에 offset에 대한 정보를 통해서 찾을 수 있다.

그렇다면 Segmentation이 메모리 관리 측면에서는 어떤 장점이 있을까?

Segmentation 방식의 장점을 생각해보기 위해서는 각 segment에 속한 심볼들의 physical address가 어떻게 계산되는지를 살펴봐야한다.

Contiguous memory allocation 방식에서는 프로세스가 사용하는 메모리를 연속적인 영역으로 바라보았다. 그렇기 때문에 프로세스가 시작되면 CPU는 base register에 등록된 PC 주소부터 인스트럭션을 읽어서 순차적으로 실행했다.

그런데 segmentation 방식에서는 조금 다르다. segmentation 방식에서는 각 segment의 영역에 대한 정보를 담고 있는 segment table이 존재한다. segment table은 각 segment 영역을 나타내는 segment base와 segment limit에 대한 값이 존재한다.

그리고 segmentation 방식을 이용하는 프로세스는 logical address를 segment number, $s$와 segment 내의 offset 값 [latex]d[/latex]로 구분할 수 있다. [latex]s[/latex]를 이용하여 해당 segment가 시작하는 physical address를 찾고 [latex]d[/latex]를 이용해서 정확한 physical address를 계산한다.

구체적인 계산 방식을 살펴보기보다는 주소를 계산하는 방식에 집중해보자. 이제는 각 segment들에 대한 정보가 segment table에 저장되어있다. 그렇기 때문에 하나의 프로세스의 메모리 영역이 연속되어있을 필요가 없다!

이제 하나의 프로세스가 필요한 메모리 영역이 하나의 큰 청크에서 작은 조각들로 나누어졌기 때문에 전체 물리 메모리 중 구멍(hole)의 비율이 더욱 더 낮아질 것이다. 다른 말로 메모리 utilization이 전보다 더욱 증가할 것이다.

Paging

그러나 segmentation 기법은 여전히 문제점이 존재한다. 각 segment는 고정된 길이를 가지지 않기 때문에 여전히 외부 단편화(external fragmentation)가 발생할 수 있다. 또한 특정 segment를 backing store로 swap-out을 할 때에도 해당 segment를 저장할 수 있는지 확인을 해야하고 backing store 내에서도 단편화 문제가 발생할 수 있다.

Paging 기법은 이러한 문제점을 해결해준다. 그리고 오늘날 대부분의 운영 체제에서도 paging 기법을 활용한 메모리 관리 방식이 사용되고 있다.

Paging 기법의 아이디어는 physical memory와 logical memory를 고정된 사이즈의 블럭들로 나누는 것이다. physical memory의 블럭을 frame이라고 부르고 logical memory의 블럭을 page라고 부른다.

전체 메모리를 고정된 사이즈의 블럭으로 나누고 메모리를 page, frame을 단위로 할당하기 때문에 더이상 외부 단편화가 존재하지 않게된다. 이는 backing store에서 발생하는 문제도 해결된다.

Paging 기법에서 logical address를 physical address로 변환하는 방식에 대해서 살펴보자.

Paging 기법에서 주소를 변환하기 위해 page table을 활용한다. Page table은 각 페이지가 시작하는 physical address의 정보를 page number 별로 담고 있다. 그리고 logical address는 page number([latex]p[/latex])와 page offset([latex]d[/latex])로 표현될 수 있는데 여기서 p 와 page table을 통해 physical address의 시작 주소를 찾고 frame의 사이즈와 page의 사이즈는 동일하기 때문에 시작 주소에서 [latex]d[/latex]를 더한 값이 최종 physical address가 된다. 

logical address space, physical address space 그리고 page table의 구조를 도식으로 표현하면 아래와 같다.

프로그램이 실행되어 프로세스가 되기 위해서는 메모리를 할당받아야한다. Paging 기법을 사용하는 운영 체제에서 프로세스가 실행되기 전에 해당 프로세스가 필요로하는 page 개수를 먼저 받는다. 그리고 해당 페이지 개수만큼 물리 메모리에서 frame을 할당할 수 있는지 확인한다.

물리 메모리의 공간이 충분하다면 프로세스를 스케쥴링 한다. 프로세스가 시작을 하면서 자신이 사용하는 첫 번째 page를 할당받은 frame 중 하나에 올려놓고 page table에 해당 frame number를 기록해놓는다. 그리고 추가적으로 page를 물리 메모리에 올려야하면 마찬가지 방식으로 진행된다.

이와 같이 paging 기법에서는 page table과 MMU를 매개로 사용자가 바라보는 메모리 뷰와 실제로 사용되는 메모리 뷰를 분리시킬 수 있다. 

logical address와 physical address 매핑 정보를 담고 있는 Page table은 운영 체제에 의해서 관리되고 실제적인 주소 변환은 MMU 하드웨어를 통해서 이루어진다.

사용자 관점에서는 프로그램이 자신에게 주어진 logical address space를 통째로 쓰고 있는 것처럼 보이게 만든다. 유저 프로세스는 page table을 통해서만 physical memory에 접근할 수 있기 때문에 자신이 할당 받은 영역 이외의 다른 공간에 대한 메모리 참조는 할 수 없다. 사용자 프로세스가 I/O 처리와 같은 시스템콜을 할 때에도 데이터의 주소는 해당 프로세스가 할당 받은 physical address에 저장되어야한다.

운영 체제는 이러한 것을 가능하게 하기 위해서 page table의 복사본을 프로세스 별로 보관하고 있다. 그래서 I/O 결과물을 사용자 프로세스가 사용하도록 하기 위해서, context switching 이전에 page table의 복사본을 통해 결과가 저장되어야할 physical address에 해당 데이터를 저장해놓을 수 있다.

Physical address space 관점에서는 하나의 프로세스가 사용하는 메모리는 frame 단위로 여기저기에 흩어져있고 동시에 하나의 프로그램만 메모리에 올라올 수 있는 것이 아니라 frame을 할당 받은 프로세스는 모두 실행될 수 있다.

Virtual Memory

위에서 살펴본 여러 가지 메모리 관리 기법들은 결국 하나의 물리 메모리에서 동시에 여러 가지 프로세스들을 동작시키기 위해서 탄생했다. 그렇지만 소개된 방법 모두는 프로세스를 실행할 수 있을 만큼 충분한 메모리가 남아있어야 했다.

그런데 대부분의 프로그램들은 전체 프로세스 라이프 사이클 중에서 전체 인스트럭션, 데이터 영역 중 일부만 사용한다. 전체 사용한다하더라도 동시에 전체가 필요한 것은 아니다.

Virtual memory의 기본 아이디어는 프로세스가 필요로 하는 전체 메모리를 물리 메모리에 먼저 할당하는 것이 아니라 필요한 부분들을 물리 메모리에 그때 그때 올리는 것이다.

이러한 아이디어를 적용하면 다음과 같은 장점이 있다.

• 더 이상 프로그램을 개발할 때 컴퓨터의 물리 메모리 사이즈보다 더 큰 virtual address space 크기를 기준으로 프로그램을 작성할 수 있다. 그리고 이 크기는 항상 일정하다.
• 또한 각각의 프로세스들이 이전보다 더욱 적은 물리 메모리의 영역을 사용할 수 있기 때문에 더욱 많은 프로세스를 동시에 물리 메모리에 올릴 수 있다. 이상적으로 CPU utilization과 처리량을 이전보다 늘릴 수 있다.

Demand Paging

Demand paging은 virtual memory의 가장 기본 아이디어인 당장 필요한 page를 물리 메모리에 올리는 특징을 말한다. 그렇기 때문에 프로세스 라이프 사이클 동안 필요 없는 영역들은 한번도 물리 메모리에 올릴 필요가 없다.

이러한 메커니즘은 paging 기법과 초반에 살펴본 swapping을 합친 개념과 비슷하다. 프로세스가 실행되면 당장 필요없는 영역들은 디스크와 같은 backing store에 저장된다. 그리고 page 단위로 필요할 때마다 backing store에서 물리 메모리로 swap-in 된다. 그리고 이렇게 어떤 page가 swap-in되고 swap-out 할지 결정해주는 컴포넌트를 pager라고 부른다.

Pager는 프로세스가 스케쥴링될 때 어떤 page들이 사용될지 추측한다. 그리고 프로세스 전체를 swap-in 하는 것이 아니라 몇 개의 page들만 swap-in 한다. 이러한 것들을 가능하게 하기 위해서 pager는 page table의 valid-invalid bit를 활용한다.

Page table의 특정 엔트리의 valid-invalid bit가 ‘valid’라면 해당 페이지는 현재 유효하고 물리 메모리에 올라와 있다는 것을 의미한다. 반대로 ‘invalid’라면 해당 페이지는 아직 backing store에 있다는 것을 의미한다.

프로세스는 자신의 라이프 사이클 동안 각 page에 들어있는 인스트럭션이나 데이터를 읽어나간다. 만약 자신이 읽는 page가 page table에 valid 상태라면 현재 물리 메모리에 올라와있다는 뜻이므로 CPU는 MMU를 통해 주소 변환을 거쳐서 물리 메모리의 데이터를 읽으면 된다.

그런데 만약 invalid 상태라면 어떻게 될까?

CPU는 logical address를 page number와 page offset으로 변환하고 page table에서 해당 page number에 해당 하는 엔트리를 읽는다. 그런데 해당 엔트리의 valid-invalid bit가 invalid로 설정되어있다면 page fault trap을 걸어서 CPU 제어권을 커널로 넘긴다. 이후에 커널은 다음과 같이 동작한다.

• 우선 커널은 PCB 등에서 해당 프로세스의 page table 복사본을 통하여 프로세스가 참조한 logical address가 유효한 주소인지 확인한다.
• 만약 유효하지 않은 참조라면 해당 프로세스를 종료시킨다. 유효하다면 필요한 page가 backing store에 있는지 확인한다.
• 해당 page를 page-in 할 frame을 물리 메모리에서 찾는다. 찾았다면 해당 위치에 디스크에 저장된 page를 읽고 쓰기 위해서 디스크 I/O 작업을 스케쥴링한다. (찾지 못했다면 뒤에서 설명할 Page replacement를 통해서 빈 frame을 만든다.)
• 디스크 I/O 작업을 마치고 다시 CPU 제어권을 얻었다면 이제 frame에 page의 데이터가 올라와 있는 상태이고 커널은 내부적으로 관리하는 page table과 해당 프로세스의 page table의 valid-invalid bit를 업데이트한다.
• CPU 제어권을 다시 프로세스로 넘겨서 실패했던 인스트럭션부터 다시 실행하도록 만든다. 이제 참조하려는 page table 엔트리의 valid-invalid bit가 valid이므로 CPU는 MMU를 거쳐 해당 페이지 내용을 읽는다.

Copy-on-Write

앞서 virtual memory 시스템에서 demand paging 을 통해서 최초로 프로세스가 시작하였을 때 어떻게 필요한 page를 메모리를 올리는지에 대해서 살펴보았다.

fork()와 같은 시스템콜 요청이 들어온 경우 프로세스는 자식 프로세스를 만들고 부모 프로세스의 상태(변수 값 등)을 그대로 가지게 된다. virtual memory 시스템에서 이러한 기능을 구현할 때 부모 프로세스가 현재 물리 메모리에 올려둔 frame들을 그대로 복사해서 다른 frame에 올려두는 것은 비효율적이다.

Paging 기법에서 만약 특정 page가 프로그램의 code 영역을 담고 있고 해당 code 영역에 thread safe한 코드만 있다면 해당 page를 여러 프로세스에서 공유할 수 있다.

예를 들어 특정 상황에서 여러 프로세스에서 code 영역은 동일하고 data 영역이 다를 수 있다. 이 때 실제 물리 메모리에 code 영역에 해당하는 frame들은 물리 메모리에 한 세트만 올려 두고 각각의 프로세스의 page table에서는 해당 frame을 가리키도록 매핑하면 불필요한 frame 사용을 막을 수 있다.

다시 fork() 를 하는 상황으로 넘어가보자. fork() 를 통해 생성된 자식 프로세스는 생성된 순간에는 부모 프로세스와 동일한 code 영역과 data 영역을 가진다. 그런데 만약 자식 프로세스가 새로운 데이터를 page에 쓰려고 한다면 어떻게 될까?

부모 프로세스와 공유하고 있는 frame에 해당 데이터를 쓰면 안된다. 이러한 문제를 해결하기 위해서 copy-on-write 기법이 등장했다.

이와 같이 자식 프로세스가 부모 프로세스의 page를 공유하게될 때 해당 page들을 copy-on-write page로 마킹을 해둔다. 이렇게 마킹이된 page에 대해서 하나의 프로세스에서 데이터를 쓰려고 할 때 공유하고 있던 page를 그 순간에 복사해서 변경하고자하는 내용을 복사본에 쓰게 된다.

운영 체제에서 copy-on-write page들을 관리하고 생성하는데 이렇게 필요한 경우에 새로운 page를 복사하여 메모리에 올리는 것을 zero-fill-on-demand 이라고 하는데 zero-fill-on-demand를 통해 생성된 page들은 0으로 값이 초기화된다.

결과적으로 lazy하게 메모리 사용을 최대한 아끼다가 필요한 순간에 추가적으로 page를 생성하여 변경을 하려는 프로세스에게 할당을 해준다.

Page Replacement

Demand Paging 섹션에서 예시로 든 시나리오에서 특정 프로세스의 page를 메모리로 swap-in을 하려는데 비어있는 frame이 없을 수도 있다. 이런 경우 virtual memory 시스템에서는 현재 당장 사용되지 않는 frame 중 일부를 다시 backing store로 swap-out 시킨다. 이러한 과정을 page replacement라고 부른다.

Page replacement 과정은 다음과 같다.

• 비어있는 frame이 없는 경우 빈 frame을 만들기 위해서 현재 올라와있는 frame들 중 swap-out 시킬 victim frame을 선정한다.
• victim frame의 내용을 backing store에 쓰고 해당 프로세스의 page table 내용을 업데이트하고 커널도 frame table과 PCB의 내용을 업데이트한다.
• 그리고 swap-in 하려는 페이지를 I/O 작업을 거쳐 빈 frame에 쓴다. 그리고 다시 page table과 frame table의 정보를 업데이트한다.
• CPU 제어권을 다시 프로세스로 넘겨준다.

위의 과정을 살펴보면 두 번의 I/O 작업이 발생한다. 이 오버헤드를 줄이기 위해서 modify bit (dirty bit) 개념이 도입되었다. CPU가 page를 읽고 쓰는 과정에서 특정 page의 내용이 변경되었다면 해당 page의 modify bit를 업데이트한다.

그리고 victim frame을 선정하였을 때 해당 page의 modify bit이 세팅되어있다면 해당 내용이 변경되었다는 뜻이기 때문에 I/O 과정을 거쳐야하지만 만약에 세팅되어있지 않다면 backing store에 있는 내용과 다르지 않기 때문에 I/O 과정을 거칠 필요가 없다.

여기서 간단히 넘어간 몇 가지 문제들이 있다. 예를 들어 어떤 frame을 프로세스에게 할당할지를 결정하는 frame-allocation 알고리즘 그리고 어떤 page를 victim page로 선정할지 결정하는 page-replacement 알고리즘 등이 있는데 이러한 구체적인 알고리즘들은 여기서 다루지 않고 넘어가겠다.

Working-Sets and Page Fault Rate

그렇지만 하나만 생각해보고 넘어갈만한 포인트가 있다. 만약 스케쥴링되는 프로세스들에게 적은 수의 frame들을 할당해주면 어떤 현상이 벌어질까?

우선 프로세스마다 할당되는 frame이 적으니 같은 사이즈의 물리 메모리를 쓴다고하면 더 많은 수의 프로세스들이 동시에 올라올 수 있다. 그래서 동시에 실행될 수 있는 프로세스의 숫자가 늘어나게 된다.

그런데 무작정 할당 frame 숫자를 줄여버리면 문제가 발생한다. 해당 프로세스는 frame 수가 얼마 안되기 때문에 빠른 시간 내에 page fault가 발생할 것이다. 그렇다면 page를 다시 올리기 위해서 다른 곳의 page를 swap-out 해야한다. 그렇지만 이제 다른 곳에서도 비슷한 문제가 발생한다.

swapping은 backing store I/O 과정이 필요하다. 그렇다면 운영체제가 page를 가져오는 동안 해당 프로세스는 멈춰있게 된다. swap의 횟수가 늘어나면 날수록 프로세스가 실행되는 시간보다 page를 backing store로부터 가져오고 가져다 넣는 시간의 비중이 늘어난다. 이처럼 전체 시간 중에 swapping 활동의 비중이 높아지는 현상을 thrashing이라고 한다.

그렇다면 thrashing 현상을 막기 위해서는 어떻게 해야할까? 이 현상을 방지하기 위한 방법 중 하나가 working-set모델이다.

Working-set 모델에서는 프로세스가 주로 얼마만큼의 frame을 쓰는지를 살펴본다. 이 때 프로세스가 사용하는 page들의 locality 특성을 이용하는데 locality 특성은 프로세스가 실행되는 과정에서 주로 같이 사용되는 page들이 존재한다는 것을 말한다. Working-set 모델에서는 특정 시간 [latex]\Delta[/latex] 동안 참조된 page 들을 살펴본다. 그리고 참조된 page들을 그룹으로 묶어서 이것을 working set이라고 부른다. 그리고 시간이 지나면서 더이상 참조되지 않는 page들은 working set에서 빠뜨린다.

우리는 working set의 크기를 통해서 프로세스가 얼마만큼의 frame이 필요할지를 알 수 있고 그렇다면 운영체제에서는 이 값을 합한 것보다 현재 사용되고 있는 frame 수가 전체 frame 수보다 적다면 새로운 프로세스를 띄워도 thrashing이 발생할 가능성이 줄어드는 것이다.

이처럼 working-set 모델을 통해서 degree of multiprogramming은 높이면서 thrashing이 일어날 가능성을 최소화할 수 있다.

Memory-Mapped Files

우리가 일반적으로 open(), read(), write() 와 같이 시스템콜을 통해서 디스크에 존재하는 파일들을 읽고 쓸 때 파일 데이터 중 일부를 버퍼에 담고 운영체제는 버퍼의 데이터를 프로세스가 사용할 수 있도록 프로세스 주소 공간에 해당 데이터를 복사해놓는다.

Virtual memory 기법을 이용하여 프로세스가 디스크 I/O 작업을 수행해서 데이터를 읽어야할 때 마치 메모리에 있는 데이터에 접근하듯이 파일 데이터를 읽고 쓸 수 있는데 이러한 기법을 우리는 memory mapping이라고 한다. Memory mapping을 통해서 디스크 I/O 횟수를 줄일 수 있고 결과적으로 퍼포먼스 향상으로 이어진다.

Memory mapping은 읽고자 하는 디스크 블럭을 page로 매핑을 시킨다. 프로세스에서 파일에 접근하고자할 때 demand paging 루틴이 발생한다. 파일에 대한 데이터가 메모리에 올라와있지 않은 상태이기 때문에 page fault가 발생한다. 이 때 디스크 I/O 과정에서 page 사이즈만큼의 파일 데이터를 디스크에 읽어서 page fault 대상이 되었던 page의 frame에 올려둔다.

그리고 이후에 발생하는 read(), write() 에 대해서는 이전에 살펴보았던 메모리의 데이터를 읽고 쓰듯이 접근한다. 메모리 접근 방식으로 동작하기 때문에 시스템콜로 인한 context-switching 같은 불필요한 오버헤드가 사라지게 된다.

매핑된 frame에 발생하는 변경사항들이 곧바로 디스크에 반영되는 것은 아니다. 이는 시스템마다 다른 전략을 취할 수 있는데 주기적으로 변경사항을 디스크로 내리는 방식이 있을 수도 있고 파일이 닫힐 때 변경사항을 체크하여 한번에 디스크에 쓸 수도 있다.

마치며…

이 글은 스스로 virtual memory에 대해서 다시 한번 정리하려는 목적이 가장 컸다. 이 글을 내가 이해할 수 있는 문장으로 써보면서 좀 더 완전하게 이해할 수 있게 된 것 같다. virtual memory를 정리해야겠다는 생각이 든 것은 Kubernetes Pod의 메모리 사용량을 모니터링하면서 부터였다. Kubernetes는 자체적으로 리소스 사용량에 대해 다양한 메트릭들을 제공해준다. 그런데 그 중 메모리와 관련된 메트릭들은 이 글에서 정리한 virtual memory에 대해서 이해하고 있으면 각각의 지표가 어떤 것을 나타내는지 더욱 완벽하게 이해할 수 있을 것 같았다.

이 글을 읽는 다른 모든 분들도 이 글이 도움이 되었으면 좋겠다.

이 글은 주로 다음 두 개의 책을 읽으면서 정리하였다.

• Operating Systems Concepts 9 Edition. Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
• Computer Systems: A Programmer’s Perspective, 3 Edition.  David R. O’Hallaron Randal E. Bryant