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

이 문서의 내용은 Operating System Concepts 10th의 슬라이드에 기반하고 있습니다.

배경

우리가 롤을 한다고 생각해보자. 롤에는 많은 챔피언이 존재하고 모드도 다양하다. 따라서 롤에서 사용되는 모든 코드를 메모리 상에 적재해야 한다면 아마 메모리가 남아나지 않을 것이다.

그런데 사실 생각해보면 롤 프로그램을 시작한다고 내부에서 사용되는 모든 에셋 및 코드를 항상 메모리 상에 올려놓을 필요는 없다. 게임 한 판을 생각해보자. 한 판의 게임에는 기껏해야 10 종류의 챔피언이 사용되며, 일단 게임이 시작되면 해당 정보는 변경되지 않기 때문이다. 단일 모드에서 티모 vs 가렌의 경기가 펼쳐졌다면 사실 메모리 상에는 티모 및 가렌에 대한 스킬 정보와 스킨, 그 외 기타 게임 관련 정보만 올라가면 된다. 만약 해당 게임에 쓸데 없이 아칼리 관련 정보가 메모리에 적재되어 있다면? 이는 메모리 낭비가 될 것이다.

마찬가지로 다양한 프로세스들은 다양한 코드를 가지지만 모든 코드의 사용률이 높은 것은 아니다. 따라서 프로그램의 일부만 부분적으로 로딩한 후 나머지는 필요한 시점에 불러와도 크게 상관 없을 것이다. 이 경우 프로세스를 필요한 만큼만 로딩한다면 더 많은 프로그램이 동시에 실행될 수 있으므로 response time 이나 turnaround time의 증가 없이도 CPU utilization을 높일 수 있으며 메모리 공간도 더 많이 남기 때문에 load & swap 으로 인한 시간이 감소하기 때문에 각각의 프로그램도 더 빨리 동작할 수 있게 된다.

이런 장점을 누리기 위해서는 프로그램을 실제 물리적 주소가 아닌 가상 주소로 대응시킨 후, 사용하지 않는 일부 코드는 하드웨어 상의 해당 코드의 위치를 가리키게 하는 등의 방법을 강구해야 할 것이다.

Virtual Memory

가상 메모리는 실제 물리적 주소와 독립된 논리적 주소 체계를 의미한다. 논리적 주소는 물리적 주소에 대한 매핑을 제공하는 MMU( Memory Management Unit ) 을 통해 실제 주소를 참조할 수 있다.

앞서 언급했듯이 프로그램이 실행되기 위해 모든 소스코드를 메모리에 적재할 필요는 없다. 따라서 프로그램에 대한 가상 메모리 공간 중 현재 실행되어야 하는 영역은 실제 물리적 주소로 매핑하고, 나머지 영역은 여전히 하드웨어에 존재하다가 필요한 시점에 코드를 불러와서 물리적 주소에 대응한다고 해도 상관없다. 따라서 논리적 주소가 존재하는 공간은 실제 물리적 주소 공간보다 훨씬 커도 되며, 이로 인해 실제 메모리보다 큰 주소 영역을 커버할 수 있게 된다. 단 Virtual Memory 에 의한 공간이 너무 크면 load & swap이 많이 발생하기 때문에 적절한 크기로 설정해야 한다.

virtual address space

가상 메모리를 통해 표현되는 메모리 영역으로, 물리적 메모리로 커버할 수 있는 공간보다 크게 할당할 수 있다. 가상 메모리 역시 Paging 기법을 사용하기 때문에 페이지는 물리적 메모리 공간의 프레임과 MMU를 통해 매핑된다.

가상 메모리는 다음 방법으로 구현될 수 있다.

Demanding Paging
Demanding Segmentation

가상 메모리라고는 해도 "메모리" 공간이므로 기존에 배웠었던 메모리 개념이 동일하게 적용된다( CPU 역시 가상 메모리를 사용한다 ). Stack 과 Heap은 서로 반대 방향으로 확장되며 둘 사이의 free hole을 stack 혹은 heap 에 할당된 메모리가 차지한다고 해서 실제 물리적 메모리에 대응되지는 않는다.

다양한 라이브러리들 역시 가상 메모리 공간에 적재된 후 공유된다. 공유 라이브러리의 경우 Shared Page 에 적재되어 여러 프로세스들로부터 참조된다.

Demand Paging

가상 메모리 공간은 실제 물리적 메모리와 관계없이 동작하며, 프로세스가 실행될 때는 가상 메모리 중 현재 실행되어야 하는 코드가 존재하는 페이지만 MMU에 의해 프레임에 적재되면 된다. 따라서 실제로 필요한 시점이 되어서야 페이지에 대응되는 프레임을 요구하여 물리적 메모리에 할당해도 상관 없는데, 이렇듯 페이지가 필요한 load time에 실제 페이지를 프레임에 대응시키는 기법을 Demand Paging이라고 한다.

다음과 같은 장점이 존재한다.

실제 메모리에 모든 코드를 적재하는 것이 아니므로 가용 메모리 영역이 많다. 따라서 메모리 공간 부족으로 인한 스와핑 등 I/O 작업이 줄어든다.
프로그램에서 필요한 영역만 할당하여 사용하므로 전반적으로 메모리가 덜 필요하다.
응답 속도가 좋아지며, 한번에 더 많은 프로세스를 적재할 수 있다.

페이지가 필요한 시점에는 해당 페이지가 가리키는 값을 찾아가면 된다.

만약 페이지가 가리키고 있는 자원이 물리적 메모리 상에 이미 존재하면 그대로 사용하면 된다.
페이지가 잘못된 대상을 가리키고 있다면 오류가 났다고 알리고 동작하지 않는다. (abort)
만약 아직 메모리 상에 존재하지 않는다면 메모리로 가져온다.

Valid-Invalid Bit

선택적으로 적재하면 기존 방식에 비해 메모리를 좀더 활용도 있게 사용할 수 있다는 것은 알겠다. 그런데 문제가 있다. 현재 조건에서는 특정 페이지가 가리키는 대상이 유효한지 여부를 알 방법이 없다. 따라서 각 페이지가 유효한지 정보를 알려주는 비트를 둬서 이를 처리해야 하는데 이때 사용되는 비트를 Valid-Invalid bit라고 한다.

v : 현재 페이지에 대응되는 메모리 상의 프레임이 존재한다.
i : 현재 페이지는 메모리 상에 존재하지 않는다.

만약 접근한 페이지의 bit가 i라면 운영체제에 trap을 걸어 page fault 을 발생시킨다. 이때 실행중이던 프로세스는 동작을 멈추고 waiting queue로 이동한다.

처음 방문하는 페이지는 반드시 trap을 통해 page fault을 발생시킨다.
운영체제는 테이블의 valid-invalid 비트를 보고 다음 사항을 판단한다.
1. v : 주소가 유효한 경우 -> 그냥 사용
2. v : invalid reference -> abort
3. i : 현재 메모리 상에 존재 하지 않으므로 메모리 적재 준비
현재 사용가능한 Free Space 을 준비한다.
현재 페이지에 들어갈 내용을 디스크에서 꺼내와서 준비된 Free Frame과 swap 한다.
테이블 비트를 v로 초기화한다.
page fault을 발생시킨 instruction을 다시 시작한다( Restart ).

1번 케이스를 생각해보면, 운영체제를 맨 처음 시작하면 메모리 내에 어떤 페이지도 존재하지 않는다. 따라서 맨 처음 페이지에 방문하는 경우 반드시 페이지를 새로 할당받아야 하므로 page fault을 발생시킨다. 어떤 프로세스도 해당 동작을 피할 수 없으며, 순수하게 요구한다고 해서 pure demanding page 라고 한다.

사실 프로세스가 반드시 하나의 페이지로 구성되는 것은 아니므로, 초기에 모든 페이지에 대해 page fault가 발생하는 것은 심한 성능 저하를 불러올 수 있다. 다행히도 각각의 페이지가 가리키는 레퍼런스들은 지역성(locality) 가 존재하여 메모리 공간을 점프하여 사용해야 하거나 하는 문제는 적다. 예를 들어 특정 함수를 호출한다고 치면 보통 로컬 변수를 사용하며, 대부분 다른 함수와 공유하지 않는다. 따라서 해당 함수를 실행하는데 필요한 코드들은 다 해당 함수에 해당하는 코드 정도에 국한된다. 이러한 정보들은 메모리 상에 비슷한 위치에 저장될 것이므로 메모리 점프로 인한 성능 저하는 거의 발생하지 않는다. 이를 locality of reference 라고 한다.

Demanding paging 기법을 이용하기 위해서는 하드웨어적인 지원이 필요하다.

page table with valid / invalid bit
Secondary memory ( swap space )
Instruction restart

Free Frame List

페이지 폴트가 발생한 경우, 운영체제는 해당 페이지에 대한 정보를 보조 기억장치에서 메모리 영역으로 옮긴다. 이때 운영체제는 자체적으로 가지고 있는 사용 가능한 프레임들에 대한 리스트를 통해 특정 페이지를 현재 사용 가능한 특정 프레임 영역에 할당한다.

이러한 Free-Frame List는 운영체제가 시작하는 도중에 만들어져서 stack이나 heap 영역에서 관리되어야 한다.

Demand Paging의 성능

Page Fault Rate : 0 ≤ p ≤ 1
- p = 0 : 페이지 폴트 X. 요구된 페이지가 모두 메모리 상에 있는게 아닌 이상 불가능에 가깝다.
- p = 1 : 모든 reference가 page fault 을 발생시킬 때 ( ex 부팅할 때 )
EAT ( Effective Access Time )
- EAT = (1 - p) * ma + p * ( o + page_in + page_out )
  - ma : 메모리 엑세스에 걸리는 시간
  - o : 페이지 폴트로 인해 발생하는 오버헤드

ex)

Memory Access Time : 200 nanoseconds
Average page-fault service time : 8 milliseconds
Page Fault Rate = A) 1 / 1000 , B 1 / 400000

EAT = (1 - p) * 200 + p * (8000000) = 200 + 7999800 * p

A ~ 8200 nano seconds ( 대략 40배 느려짐 )

B ~ 220 ( 대략 10배 느려짐. 역산 가능 )

Demanding Paging Optimization

page fault 가 천번에 한번만 일어나더라도 속도는 40배가 느려진다. 따라서 page fault의 수를 최대한 줄이는 것이 Demanding Paging 기법에 대한 최적화 방법이라고 할 수 있다.

swap space가 일반적인 파일 시스템보다 속도가 빠르므로, swap 공간의 크기를 늘린다.
load time에 프로세스의 정보를 이미지채로 swap space 에 복사하고, 해당 공간에서 page in & out 수행한다.
프로그램을 한번에 최대한 많이 디스크에서 읽어 적재한 후, 공간이 부족할 때 paging out 한다.

Copy-on-Write

페이지를 아끼기 위한 기법 중 하나로, 부모 프로세스가 자식 프로세스를 for을 통해 만든 경우 자식 프로세스가 코드를 변경하는 행위를 수행하기 전까지는 자식 프로세스도 동일한 페이지를 가리키도록 하다가 실제로 코드가 변경되는 상황에서 관련된 페이지를 자식 프로세스에게 복사하여 제공하는 방식을 의미한다.

자식 프로세스가 단순히 printf 와 같이 write 연산이 배제된 작업을 목적으로 생성된다면 부모 프로세스와 환경의 차이는 발생하지 않으므로 굳이 자식 프로세스를 위한 페이지를 따로 생성하여 제공할 필요가 없다. 특히 자식 프로세스에서 exec을 수행하는 경우 어차피 모든 정보를 날릴 예정이므로 할당하는 것 자체가 아깝다. 따라서 실제로 코드 수정 등 부모와 달라지지 않는 이상 그냥 부모 프로세스의 페이지 정보를 사용하도록 하며, 변경되는 점이 존재하는 경우 변경된 부분만 복사해서 사용하고 나머지는 여전히 부모 프로세스의 페이지들을 사용하도록 한다.

(좌) 동일 코드를 가리키는 프로세스들 (우) 변경 사항이 있는 page C에 대해서만 카피를 만드는 모습

Free Frame이 존재하지 않는 경우

free frame이 존재하지 않는다는 것은 현재 사용 가능한 메모리 자원이 없다는 것을 의미한다. 따라서 현재 요청된 프로세스를 메모리로 올리려면 반드시 현재 메모리 상에 존재하는 정보를 내린 후 프로세스를 올려야 한다. 이때 메모리 상의 대체될 프로세스는 다음과 같은 방법을 통해 처리 가능하다.

terminate : 프로세스를 죽이고, 나중에 다시 실행한다.
swap out : 프로세스 통째로 보조기억장치에 저장한다.
replace page : 페이지 단위로 일부 저장한다.

이중 앞 두가지 방식은 페이지 기반의 환경에서 굳이 선택할 선택지는 못된다. 여기서는 page replacement을 설명한다.

Page Replacement

page fault가 발생했지만 free Frame 존재하지 않을 때, 현재 물리적 메모리에 적재된 프레임 중 일부를 디스크에 저장하고, 현재 요청한 페이지를 디스크에서 불러와 적재하는 것을 의미한다.

현재 요청된 페이지를 물리적 메모리에 저장하기 위해서는 어떤 프레임을 디스크 공간으로 보내서 물리적 메모리 상에 사용 가능한 공간을 만들어 줄 필요가 있다. 이때 희생자가 되는 프레임을 victim frame이라고 한다.

만약 page replacement을 수행할 때마다 victim frame의 정보를 디스크에 써야 한다면 오버헤드가 클 것이다. page fault가 발생하면 swap in / swap out 과정에서 페이지 정보를 두번 작성해야 하기 때문이다. 그런데 사실 victim frame에 저장되어 있는 정보가 적재 이후 한번도 수정된 적이 없다면 디스크 상의 정보와 동일하므로 변경할 필요가 없다. 따라서 각각의 frame에 대해 현재 frame 정보가 변경되었는지 여부를 검사하는 비트를 부여하는데, 이를 dirty(modify) bit 라고 한다.

대략적인 알고리즘은 다음과 같다.

요구된 페이지의 디스크 상 위치를 찾는다.
free frame을 찾는다.
1. free frame이 존재 : 그냥 해당 프레임을 이용한다.
2. free frame이 존재하지 않음 : 알고리즘을 이용하여 victim frame을 결정한다. dirty bit가 설정되어 있다면 변경 내역을 디스크에 저장할 시간을 준다.
요구된 페이지를 새로 생긴 free frame에 대응시키고, page / frame 테이블을 업데이트한다.
trap을 발생시킨 instruction부터 다시 시작하여 프로세스를 재개한다.

Page and Frame Replacement Algorithm

Frame-allocation algorithm
: 각 프로세스에 얼마나 많은 페이지를 할당해야 할지 / 어떤 프레임을 교체해야 할지 결정.
Page-replacement algorithm
: first-access / re-access에 page fault를 가장 적게 발생시키는 방법을 결정.

일반적으로 frame 개수가 증가하면 page fault는 감소한다. 그러나 어떤 경우에는 frame이 증가했음에도 불구하고 page fault 도 덩달아 증가한다. 이런 현상을 Belady's Anomaly 라고 한다. 이런 현상은 FIFO 에서 발생한다.

(좌)page fault 와 frame 개수의 대략적인 관계 (우) FIFO에서 발생하는 Belady's Anomaly

First-In-First-Out (FIFO) Algorithm

메모리에 적재되어 참조 대상이 되는 일련의 페이지들을 해당 페이지의 번호로 나타내고, 이를 연속적으로 나타낸 것을 Reference string 이라고 하자. FIFO 알고리즘은 일련의 페이지들을 들어온 순서대로 적재하는 방식을 말한다. 구현은 단순하지만 페이지 사용의 경향성 등을 고려하지 않으므로 효율적이라고 말하기는 힘들다.

위 그림은 특정 프로세스가 사용가능한 프레임의 개수를 3개로 두고 페이지들을 FIFO 알고리즘 하에 적재하는 모습을 보여주고 있다. 해당 예시에서는 총 15번의 page fault가 발생했다.

Optimal Algorithm

페이지를 프레임에 할당하기 위한 가장 좋은 힌트는 미래에 올 페이지 정보를 미리 알고 있는 것이다. Optimal Algorithm은 미래에 적재할 페이지 목록을 미리 안 상태에서 현재 시점으로부터 가장 오랫동안 사용되지 않을 페이지를 제거한다.

위와 동일한 예시에 대해 최적 조건( 미래를 알고 있음 )이 있는 경우 9번의 page fault만 발생했다. 그러나 이 방법은 절대 실제로는 사용할 수 없다. 우리는 미래에 어떤 페이지를 사용하게 될지 모르기 때문이다.

Least Recently Used (LRU) Algorithm

미래를 예측하는 대신 과거의 정보를 이용하는 것은 어떨까? 과거의 정보는 충분히 알 수 있으므로 가장 오랫동안 사용되지 않았던 페이지를 가장 먼저 제거할 수 있다. LRU에서는 이렇듯 과거의 정보를 기반으로 가장 오래 사용되지 않은 순으로 페이지를 희생자로 삼는다.

동일 예제에 대해 LRU을 수행한 결과 총 12번의 page fault가 발생했다. 이는 optimal 보다는 못하지만 FIFO 방식보다는 더 좋다고 볼 수 있다. 최적 알고리즘을 유사하게 나타낸다고 해서 근사 알고리즘이라고 부르기도 한다.

LRU 구현 방법

2가지 방식으로 구현할 수 있다.

Counter Implementation
: 각각의 페이지 엔트리에 카운터를 두고 동일 페이지를 가리킬 때마다 카운터를 증가시킨다. frame 꽉 찬 경우 카운터에 저장된 값이 가장 작은 페이지 엔트리의 대상을 Victim으로 삼는다.
Stack Implementation
: 양방향 링크드리스트 형식으로 스택을 구성하고, 해당 스택에 페이지 번호를 저장한다. 가장 최근에 온 페이지를 최상단으로 올려 오래된 페이지가 스택의 가장 하단에 오도록 한다. 만약 page replacement가 필요하면 최하단의 페이지를 Victim으로 삼는다.

Stack Implementation은 제거가 매우 간편하다는 장점이 있으나, 최신 페이지를 최상단으로 이동시키는 과정에서 전체 페이지 엔트리에 대한 재배치가 필요해 업데이트 과정은 비효율적이다. 그렇기는 해도 운영체제는 보통 이 방식으로 구현된다고 한다.

LRU 근사 알고리즘

LRU는 특별한 하드웨어가 필요하며, 여태까지 설명한 구현 방식으로는 속도가 좀 느리다. 따라서 실제로는 하나에서 두개의 비트를 이용하여 LRU을 근사하는 알고리즘을 이용한다.

Reference Bit
:각각의 페이지에 대해 참조가 되었는지, 되지 않았는지를 나타내는 비트.
- 참조 O : 1
- 참조 X : 0

Second-Chance Algorithm

FIFO에 하드웨어 기반의 reference bit을 추가한 방식으로, 원형 큐처럼 각각의 엔트리를 돌아가면서 평가한다. Second-Chance 인 이유는 최근에 참조되어 reference bit의 값이 1인 페이지에게 1 코인을 더 주는 것처럼 동작하기 때문이다.

현재 가리키는 위치의 페이지 엔트리에 대한 reference bit을 조사한다.
reference bit = 1 : 0으로 변경하고 next victim을 다음 페이지 엔트리로 옮긴다.
reference bit = 0 : 해당 페이지 엔트리에 존재하는 대상에 대해 page replacement을 수행한다.

reference bit 이외에 dirty(modify) bit을 추가하여 알고리즘을 좀 더 향상시켜볼 수도 있겠다.

(0, 0) : 최근에 사용된적도, 수정된 적도 없음 -> 대체하기 딱 좋다.
(0, 1) : 최근에 사용은 안됬는데, 수정된 적 있음 -> 나쁘지는 않은데 반드시 write 작업 수행해야
(1, 0) : 최근에 사용되었으나, 수정된 적 없음 -> 또 사용될 수도 있으니 대체하기 곤란
(1, 1) : 최근에 사용 + 수정 -> 또 사용될 수도 있는데다가 write 작업도 필요하므로, 선택 X

비트를 2개 사용해서 알고리즘을 구현하는 경우 여러번 원형 큐를 순회해서 victim을 선정해야 할 수도 있다.

Counting Algorithms

참조된 횟수를 기록하여, 해당 횟수를 victim 정할 때 사용하는 경우도 존재한다.

Least Frequently Used (LFU) Algorithm
: 가장 적게 참조된 놈은 가장 덜 중요할테니 얘를 교체하자.
Most Frequently Used (MFU) Algorithm
: 가장 많이 참조된 놈은 할만큼 했으니 얘를 교체하자.

실제 상황에서는 프로그램 실행 초반에 바짝 참조되고 이후 사용되지 않는 경우가 존재하여, MFU 알고리즘을 사용하는 편이 더 효율적인 경우가 많다고 한다. 예를 들어 특정 데이터를 로딩하는 코드는 프로그램 시작 시점에 바짝 사용되어 빈도가 높지만, 이후에는 이미 모든 정보를 로딩했으므로 계속 가지고 있을 필요가 없다. 이런 경우 MFU를 이용하여 참조될만큼 된 놈들을 제거한다고 한다.

Page-Buffering Algorithms

이전까지의 page replacement 전략은 page fault 가 발생했을 때 희생자를 하나 설정하고, 요구된 페이지를 해당 페이지와 교체하는 방식으로 동작했다. 이때 page fault가 진작에 덜 발생할 수 있도록 평소에도 free frame을 미리 만들어 두는 방식은 어떨까? 어차피 적재해야 하는 데이터인데 그냥 page fault가 발생하기 전에 적재해서 사용할 수 있는 공간을 미리 미리 확보해 두는 것이다.

Page-Buffering Algorithm 에서는 free frame pool을 계속 관리하다가 free frame이 필요한 시점에 해당 풀에서 꺼내 제공한다. Victim Frame에 대해서는 자원을 반환하고 해당 공간을 공실로 만들어 free frame pool에 넣는다. 즉, free frame 의 제공과 free frame의 획득을 따로 구분해서 처리한다.

이런 방식에도 이전에 언급했던 비트 처리가 가능하다. free frame의 제공과 획득이 따로 동작한다고는 해도 어차피 victim을 정하는 과정은 위에서 언급한 방식을 사용해야 하기 때문이다.

Application & Page Replacement

일반적으로는 운영체제가 page replacement을 관리하지만, DBMS 등 경우에 따라 자신들의 고유한 알고리즘을 이용하여 전체 데이터를 처리하는 경우 운영체제의 개입을 원하지 않을 수 있다. 이런 상황에 대해 운영체제는 어플리케이션 스스로 자신에게 부여된 메모리나 I/O 버퍼 등을 처리할 수 있도록 권한을 부여하기도 하는데, 이를 Raw Disk mode라고 한다. Raw Disk Mode 을 이용하는 어플리케이션은 자신들의 내부 구조에 맞게 스스로 구현한 페이징 기법을 이용하여 스스로 메모리를 관리할 수 있다.

Frame Allocation

여태까지는 페이지를 어떻게 할당할 것인지 논했는데, 사실 각각의 프로세스에게 몇개의 프레임을 설정할지도 중요한 문제 중 하나다. 프레임의 개수는 한정되어 있으므로 각각의 프로세스에 대해 최소한의 프레임만 제공하는 것이 전체적인 관점에서 긍정적일 것이다.

다양한 방법이 있으나, Fixed allocation 및 Priority allocation 이 주된 방식이라고 한다.

Fixed Allocation

전체 프레임을 고정된 크기로 프로세스들에게 분할하는 방식을 의미한다.

Equal Allocation : 전체 프레임을 프로세스의 수로 나눠서 모두 동등하게 사용하도록 하는 방식
Proportional Allocation : 전체 비율에 대해 해당 프로세스의 비율만큼 프레임을 할당하는 방식.

Global Allocation
: 전체 프레임에 대해 해당 프로세스가 할당받지 않았더라도 필요하면 뺏어서 쓰는 방식. 프로세스마다 실행 시간이 크게 달라질 수 있기는 하지만, 성능적으로는 좋다.
Local Allocation
: 자신이 할당받은 프레임만 사용하는 방식. 모든 프로세스에 대해 일관된 성능을 보이나, 프로세스마다 CPU 사용 수준이 다르다는 점을 고려하지 않아 CPU utilization이 낮아진다.

Non-Uniform Memory Access

여태까지는 모든 메모리를 동등한 수준으로 접근한다고 생각했는데, 특수한 상황에서는 자신과 가까운 CPU를 사용하는 등의 방법을 통해 성능을 높일 수도 있다.

NUMA는 현재 자신과 가까운 메모리에 접근하는 방식. 근접한 메모리에 대한 속도는 빠르지만, 멀리 있는 메모리는 system bus 등을 거쳐 접근하기 때문에 상대적으로 속도가 느려진다. 이런 구조에서는 CPU마다 자신이 관리하는 프로세스나 스레드를 계속 자신이 관리하게 만드는 편이 속도 측면에서 좋을 것이다. 이런 동작은 Igroups 등을 통해 가능하다고 한다.

Thrashing

프로세스들이 본인들을 동작시키기에 충분한 프레임을 가지고 있지 않은 경우 계속 page fault을 발생시켜 페이지가 교체되게 만든다. 이때 페이지 교체는 CPU 동작 속도에 비해 매우 느리기 때문에, 메모리는 전부 사용되는데 반해 CPU 사용률은 낮아진다.

문제는 운영체제가 이런 상황을 CPU가 놀고 있다고 판단할 수 있다는 점이다. 운영체제는 낮은 CPU utilization을 보고 이를 여유롭다고 판단하여 추가적인 프로세스를 메모리 상에 배치함으로써 메모리를 좀 더 포화 상태로 만들고, 이는 CPU utilization을 다시 낮추는 악순환을 만든다.

이처럼 프로세스들이 수행되기 위한 적절한 프레임의 개수를 가지고 있지 않아, 페이지 교체가 자주 발생하여 CPU 이용률이 낮아지는 현상을 thrashing 이라고 한다.

일반적으로 CPU 이용률이 낮은 경우 프로세스를 추가하여 CPU가 놀지 못하게 만들 수 있다. 그런데, 일정 이상 프로세스가 많아지게 되면(멀티 프로그래밍 수준이 높아지면) 각 프로세스에 할당되는 메모리가 충분하지 않아 페이지를 자주 변경하기 때문에, 오히려 CPU 사용률이 낮아진다.

Working-Set Model

우리가 프로그램을 작성할 때 연관성 있는 코드끼리 모아서 작성하는 경우가 많다. 함수를 작성한다고 하면, 함수 내에서 사용되는 변수는 보통 지역 변수로 지정해두는 것 처럼 말이다. 따라서 특정 기능을 수행하는 코드는 인접한 페이지에 저장될 확률이 높으며, 이들은 함께 사용되는 경우가 많다.

위 그림은 시간이 지남에 따라 실행되는 페이지 레퍼런스의 변화를 보여주고 있다. 특정 시기에 특정 페이지들이 동시에 사용되고 있는 모습이 드러난다. 어떻게 보면 당연한게, 당장 워드 문서를 하나 연다고 생각하면 워드 프로그램을 시작하는데 사용되는 코드, 문서를 읽어오는 코드 및 문서를 수정하기 위한 코드는 각각의 지역성을 가지지만 워드가 각종 정보를 초기화하는 동시에 문서를 읽어오는 것은 아닐 것이기 때문에 다른 영역의 코드가 시간에 따라 다르게 사용되는 것이 합당할 것이다.

따라서 특정 업무를 진행할 때 사용하게 되는 페이지 목록을 이러한 locality에 기반하여 추려낼 수 있게 된다. 업무의 단위를 instruction으로 두고 고정된 개수의 instruction을 수행하는데 필요한 페이지들의 리스트(개수)를 구하면 특정 시간대에 사용되는 페이지를 얻어낼 수 있게 된다. 이때 해당 페이지 리스트 영역을 Working Set이라고 한다.

Working Set Window의 크기에 따라 성질이 달라진다.

너무 작은 경우 : locality 도 커버하지 못함.
너무 큰 경우 : 전체 프로그램을 다 커버하므로 의미가 없음.

모든 프로세스에 대한 Working Set을 전부 더하면 특정 기간에 필요한 프레임(D)이 된다. Thrashing은 지역적으로 사용되는 모든 프레임의 합이 전체 프레임의 개수보다 클 때(D > m) 발생하므로, Working Set의 총 합을 전체 프레임의 크기보다 작게 유지한다면 발생하지 않는다. 따라서 이런 현상이 발생하면 swap 등을 통해 멀티프로그래밍의 정도를 감소시킨다.

Working Set은 특정 시점에서 사용된 페이지를 모아서 만든다. 차후 유사한 instruction 목록이 실행될 때도 Working Set에 존재하는 페이지들을 사용할 것이므로, 해당 정보를 미리 얻어두는 것이다. 페이지는 일정 간격 ( interval timer ) 마다 부여된 Reference bit에 지정된 값을 파악하여 대략적으로 만들 수 있다. 검사하는 비트의 수를 늘리고 검사하는 시간 단위를 더 잘게 자르면 예측이 더 정확해질 것이다.

Page Fault Frequency

Working Set을 만들어 두면 프레임을 분배하기 좋은 것은 사실이나, 현실적으로 Working Set을 일일이 만들어서 이를 체크하는 것 자체가 어렵다. 대신 감수할만한 수준의 page fault frequency라면 그냥 받아들이는 방식을 이용한다.

page-fault rate가 정해진 바운더리 안에 있다면 그냥 감수한다. 너무 높다면 프레임이 더 필요하다는 의미이므로 일부 페이지를 희생자(victim)으로 삼아 내보낸다. 너무 낮다면 현재 자원이 낭비되고 있는 것이므로 프로세스를 추가한다.

Working Set & Page Fault Rates

프로그램은 일반적으로 초반에 page fault가 잔뜩 난 후 실행되는 구조를 가진다. 위와 같은 구조의 범위를 working set으로 설정하는 것이 이상적이지만, 알고리즘 등 고려할 점이 많아 실제로 크게 사용하지는 않는 듯 하다.

Memory Mapped Files

파일을 읽거나 쓸 경우 open 을 통해 파일 디스크립터를 생성하고, 우리는 해당 디스크립터를 이용하여 파일에 접근할 수 있다. 과거의 경우 파일 디스크립터가 그때 그때 요구할 때마다 물리적 장치로부터 정보를 읽어들인 후 이용했지만, 최근에 와서는 처음부터 메모리 상에 파일 내용을 올려둔 후 마치 I/O 장치를 다루는 것 처럼 처리된다.

파일은 일정 크기로 잘라 읽을 수도 있지만, 그냥 처음부터 끝까지 읽어 메모리에 올릴 수도 있다. 두 경우 모두 현대에는 메모리 상에 올려 처리하는 것이므로 실제 파일에 완전히 대응된다고 보기는 어렵다. 예를 들어 파일 디스크립터를 이용하여 입출력을 수행하는 코드를 짜는데 close을 안넣어서 입력이 하나도 반영되지 않은 기억이 한번쯤은 있을 것이다. 이는 파일 디스크립터가 하드웨어에 바로 대응되는 대신, 속도를 위해 메모리에 매핑되는 구조를 가지기 때문이다. 메모리에서 작성된 입력 값은 close을 통해 명시적으로 메모리로부터 보조기억장치로 반영되기 때문에, 우리의 실수가 입력을 하나도 받지 않은 상황을 가져왔던 것이다.

일반적으로 프로세스는 자신이 접근할 수 있는 메모리 영역이 존재한다. 만약 동시간대에 동일한 파일에 접근하여 동시에 수정해야 하는 경우가 존재한다고 생각해보자. 만약 해당 작업을 수행하는 프로세스들이 메모리에 매핑된 파일을 각각 user space에 가지고 있다면 각각의 프로세스의 수정 내역은 다른 프로세스들에게 아무런 영향을 주지 않을 것이고, 결국 맨 마지막에 close을 한 프로세스의 변경 사항만이 수정 내역에 저장될 것이다. 파일을 각각의 프로세스에 딸린 메모리로 매핑한 순간 해당 파일들은 별개의 존재가 되기 때문이다. 이런 문제를 해결하기 위해 운영체제는 파일 입출력에 대한 메모리를 커널 영역에 할당해준 후, 작업은 커널 영역에서 다 수행하고 나중에 유저 영역에 전달될 수 있도록 한다. 이 경우 메모리를 2번 접근하는 오버헤드가 발생하기는 하나, 유저 입장에서는 동작하는게 장땡이기 때문에 충분히 감수할 수 있다는 입장이다. 경우에 따라 Copy-On-Write 방식 혹은 system call 기반의 shared memory을 사용할 수도 있다.

memory mapped file을 실제 파일인것 양 사용하는 프로세스들

memory mapped file 을 공유 메모리에 두고 여러 프로세스에서 사용하는 모습

Allocating Kernel Memory

여태까지는 유저 입장에서의 메모리 관리 방식을 다뤘다. 유저 입장에서는 모든 프로세스가 동등한 수준에서 동작해야 했음에 반해, 커널 입장에서는 유저가 불편함을 느끼지 않도록 어떻게든 메모리를 처리하면 된다. 꼭 커널 영역의 모든 프로세스가 동일한 수준으로 동작할 필요는 없다는 이야기다.

또한 I/O 디바이스 관련 데이터 등 커널 메모리 영역에서 다루는 정보들은 연속 적재 되는 편이 전반적으로 더 좋은 경우가 있다. 따라서 user space에서의 메모리 관리 방식과는 다른 방법을 사용한다.

Buddy System

2의 n승 형태로 메모리를 할당하는 power-of-2 allocator을 이용하는 방식이다. 할당되는 메모리들은 물리적으로 연속적인 페이지를 구성하는 고정 사이즈의 형태를 지닌다. 메모리가 부족하면 현재 메모리 크기만큼의 페이지를 연속하는 위치에 할당한다. 현재 페이지 중 사용하지 않는 부분이 절반정도 된다면 현재 페이지를 절반으로 쪼갠다.

예를 들어 128KB의 페이지가 있다고 하자. 필요한 메모리의 크기가 140KB가 되는 경우, 현재 페이지의 크기인 128KB 만큼을 물리적으로 연속되게 할당하여 현재 페이지의 크기를 256KB로 만든다. 반대로 128KB 중 30KB만 사용하고 있다면 현재 페이지를 절반의 크기인 64KB로 쪼갠다.

사용하지 않는 메모리 영역을 커다란 청크에 반환할 수 있다는 장점이 존재하나, 내부 단편화가 발생할 수 있다.

Slab Allocator

물리적으로 연속된 페이지를 모아두고, 이를 Slab이라고 부른다. 캐시는 이들을 관리하며, 각각의 캐시는 커널에서 사용되는 unique 한 자료구조 하나 하나에 대응된다. 처음 자료구조가 만들어지면 free ( 사용 가능 )가 되며, 어떤 값이 저장되는 경우 used 상태가 된다.

Slab이 used object로 꽉 차면 다른 빈 Slab에 채우기 시작한다. 만약 이것도 다 차면 새로 Slab을 할당한다.

특정 자료구조의 크기만큼만 메모리를 딱 할당하는 구조를 가지기 때문에 내부 단편화 현상도 존재하지 않는다.

이외 고려할만한 사항들

Prepaging

Prepaging은 페이지 폴트를 없애기 위해 프로세스 시작 시점에 미리 정보들을 올려두는 방식이다. 모든 페이지가 골고루 사용된다면, 필요할 때마다 페이지를 가져오기 보다는 처음부터 모두 메모리에 올리는게 좋을 것이다. 이 경우 모든 페이지에 대한 반응속도가 빨라진다는 장점이 존재한다.

그런데, 대부분의 경우에는 모든 페이지가 골고루, 자주 사용되지는 않는다. 특히 거의 사용되지 않는 페이지는 Prepaging으로 인한 프레임 부족 때문에 실행하기도 전에 swap 될 가능성이 높으므로 오히려 I/O 및 메모리 낭비이다.

따라서 Prepaging 된 페이지가 실제로 사용되는 확률을 기반으로 사용 여부를 고려할 수 있다.

s : prepaging 된 페이지 개수
a : 실제로 사용된 페이지 비율
s * a > s * (1 - a) : prepaging 고려할만 함
s * a <= s * (1 - a ) : 실제로 사용되지 않은 페이지가 더 많으므로 고려 대상 아님.

Page Size

페이지 사이즈를 구성할 때 다음과 같은 것들을 고려해야 한다.

Fragmentation ( 작으면 )
: 페이지의 크기가 클수록 단편화로 인한 손해도 커진다. 따라서 페이지가 작아질수록 좋다.
Page Table Size ( 크면 )
: 동일 크기 메모리에 대해 페이지가 작아지면 페이지 엔트리 개수는 커지므로 페이지 테이블의 크기 역시 커진다. 페이지 테이블은 커질수록 관리하기 어려우므로 페이지 크기가 큰 것이 좋다.
Resolution ( 작으면 )
: 특정 페이지가 특정 정보만 가지고 있는 특성을 의미한다. 페이지의 규모가 작아질수록 내가 원하는 내용만 페이지에 들어있을 수록 커지므로 페이지 크기가 작을수록 좋다.
I/O overhead ( 크면 )
: 개별 페이지가 작아지면 페이지의 개수는 증가한다. 이에 따라 I/O의 수도 증가하므로 페이지가 클수록 좋다.
Number of Page Fault ( 크면 )
: 페이지가 많아질수록 페이지 폴트도 많이 발생한다.
Locality ( 크면 )
: 페이지가 너무 작으면 지역성도 만족하지 못할 수 있다.
TLB size & 효율 ( 크면 )
: 페이지가 너무 작아서 수가 많으면 TLB로 커버할 수 있는 영역이 줄어든다.

TLB Reach

TLB로 커버할 수 있는 메모리의 크기를 의미한다.

TLB Reach = TLB Size * Page Size

TLB가 모든 페이지를 전부 커버할 수 있는 상황이 가장 이상적이기는 한데, 이런 것은 하드웨어 상 불가능하다. 대신 페이지의 크기를 키워 커버해야 하는 페이지 범위를 줄이거나 페이지 자체의 크기를 여러개로 둬서 fragmentation 증가 없이 페이지의 사이즈를 증가시키는 방법도 좋겠다.

프로그램 구조

프로그램을 어떻게 작성하는가에 따라 page fault가 달리 발생하기도 한다.

(A) 16384 번의 page fault 가 발생하는 경우 / (B) 128번의 page fault 가 발생하는 경우

(A) 는 배열이 저장된 구조에서 인덱스를 반대로 접근하고 있다. 이때 이차원 배열은 1차원 배열에 대한 배열로 볼 수 있는데, 컴퓨터 프로그램 상 1차원 배열 단위로 정보를 저장하므로 이는 마치 페이지를 뛰어넘는듯한 결과를 가져온다. 따라서 128 개의 페이지에 대해 128개의 값을 탐색하기 위해 페이지를 검색하게 되므로 page fault가 16384번 발생한다. 실제로 이렇게 극단적으로 동작하지는 않겠지만, 페이지 때문만이 아니더라도 메모리 점프때문에 실제로 (A)가 (B)보다 성능이 나쁘다. 최근 컴파일러들은 좌측의 바보같은 코드를 우측으로 바꿔준다고 한다.

I/O Interlock

디스크 상의 특정 파일을 읽거나 쓰기 위해 버퍼 작업을 하는 경우, 이런 정보가 담긴 페이지들은 교체 대상이 되면 안된다. 해당 페이지에 대해 몇가지 대안이 존재한다.

우선 디스크로 들어오는 데이터를 커널 영역에 두는 두고 삭제할 수 없게 만드는 방법이 있다. 이 경우 작성된 데이터를 이후 유저 공간에 복사해야 하기에 메모리를 두번 읽어 오버헤드가 발생한다는 단점이 있긴 하다.

다른 방법으로는 각각의 페이지에 대해 현재 페이지가 교체 대상이 될 수 있는지 여부를 지정하는 비트를 둬서 페이지에 락을 거는 방법이다. 어떤 운영체제들은 해당 비트의 지정을 유저가 직접 정할 수 있게 한다. 문제는 컴퓨터를 사용하는 모든 유저에게는 자신의 작업이 가장 중요하므로 비트를 모두 1로 설정할 것이며, 오류로 1로 설정된 페이지를 초기화하지 못하면 더 이상 사용할 수 없게 된다는 점이다. 다행이도 운영체제는 초반에는 1로 지정된 페이지를 존중하지만, 계속 사용할 수 있는 공간이 없으면 그냥 무시하고 page replacement 을 수행한다고 한다.

'CS > 운영체제' 카테고리의 다른 글

[운영체제] 뮤텍스, 세마포어, 튜링 동치 (0)	2024.09.10
[운영체제] 파일시스템 (0)	2022.05.31
[운영체제] 페이징 기법 (0)	2022.05.16
[운영체제] 메모리 (0)	2022.05.09
[운영체제] 데드락 (0)	2022.04.30