가상 메모리

1. demand paging

- 대부분의 OS는 프로세스를 page 단위로 관리하여 가상메모리에 있는 page들을 요청이 있을 때에 메인 메모리로 옮겨와 이를 사용한다. 이처럼 가상메모리의 page를 필요할 때 메인 메모리로 옮겨와 사용하는 방식을 demand paging이라 한다.

- demand paging을 사용하면 다음 이점이 있다.

(1) 중요도가 높은 page를 메인 메모리로 옮겨와 사용하므로, I/O에 소모되는 시간을 절약할 수 있다.

(2) 중요도가 떨어지는 page를 디스크로 내리므로, 메모리를 효율적으로 사용할 수 있다.

(3) 멀티 프로그래밍 환경에서 많은 사용자에게 빠른 응답속도로 결과를 내보낼 수 있다.

2. page fault

- page table에서 어떤 엔트리가 invalid 상태로 돼있다면, 이는 그 부분에 해당하는 page가 (1)프로세스에서 사용되지 않는 영역이거나 (2)메인 메모리에 없고 디스크의 가상 메모리에 저장돼있음을 뜻한다. 당장 CPU에서 메인 메모리로 직접 접근할 수 없는 영역임은 분명하므로, 이러한 영역으로의 호출이 발생하면 프로세스는 trap을 발생시킨다(이 trap을 page fault라 한다).

- page fault 발생 시 OS는 다음과 같은 순서를 따라 이를 처리한다.

(1) 그 영역이 프로세스에서 사용되지 않는 영역인지, 접근권한이 없는 것인지 등을 확인한다. 이에 해당한다면 프로세스를 강제 종료하고, 그게 아니고 그 영역이 디스크의 가상 메모리에 저장돼있는 것이라면 다음 단계로 넘어간다.

(2) 메인 메모리에 빈 frame이 있는지 확인한다. 빈 frame이 없다면 메인 메모리의 page 중 어느 하나를 디스크로 옮긴다. (이를 swap out이라 하며, 이러한 일련의 swap in - swap out 과정을 page replacement라 한다. 여기서 어떤 page를 선택할 것인지가 메모리 효율과 관련해서 매우 중요한 문제가 된다. 예를 들어 호출되는 빈도가 높은 page를 자꾸 디스크로 옮기게 된다면, 디스크로 옮겨진 그 page를 계속 메인 메모리로 옮겨오는 과정에서 어마어마한 overhead가 발생하게 된다.)

(3) 호출된 page를 디스크에서 메인 메모리의 빈 frame으로 옮겨온다(이를 swap in이라 한다).

(4) 옮겨오는 작업이 끝나면, page table의 그 page에 해당하는 엔트리를 valid 상태로 바꾸고 다음 명령어를 처리한다.

3. caching과 page replaecement

- 데이터를 읽고 쓰는 속도가 느린 장치만을 사용해서 연산을 처리하면 연산 처리보다 데이터를 읽고 쓰는 데 드는 시간이 지나치게 길어지므로, 비용이 다소 들고 용량이 다소 적더라도 읽고 쓰는 속도가 빠른 보조적인 저장장치(cache)를 중간에 두어 효율을 개선하는 방법을 caching이라 한다. 컴퓨터 시스템에서 메인 메모리를 사용하여 디스크에 저장돼 있는 프로세스를 로드하여 연산을 처리하는 것, 캐시 메모리를 사용하여 메인 메모리에 있는 프로세스를 로드하여 더 빠른 속도로 연산을 처리하는 것, 버퍼를 사용하여 디스크에 저장돼 있는 파일을 로드하여 더 빠른 속도로 파일 I/O를 처리하는 것 또한 caching의 한 형태이다.

- caching은 공간이 한정돼 있으므로, 어떤 데이터를 cache에 오래 두고 어떤 데이터를 cache에서 지울지를 선택하는 것이 전체적인 효율 개선에 있어 중요한 문제가 된다. 특히 어떤 데이터를 cache에서 지울지를 선택하는 방법에 있어 다양한 알고리즘이 제시되는데, 이 알고리즘의 시간복잡도가 커지면 또 cache에서 뭘 지울지를 고르는 데 드는 시간이 느린 장치에서 데이터를 그냥 직접 로드하는 시간보다 더 길어질 수 있다. 따라서 cache에서 뭘 지울지를 고르는 알고리즘의 시간복잡도가 작을수록 유용하다. 일반적으로 시간복잡도가 O(logn) 이하일 때 유용한 알고리즘으로 본다.

- 디스크의 swap space에서 메인 메모리에 page를 swap in/out 해 사용하는 것 역시 caching의 한 형태이다. 이러한 page replacement 문제에선 전체적인 page-fault rate를 최소화 하도록 swap out할 page를 선택하는 것이 중요하며, 다음은 이러한 관점에서 제시된 ‘cache에서 지울 데이터 고르는 알고리즘’들이다.

1) Belady’s optimal algorithm

- page들이 앞으로 어떤 순서대로 요청될지를 처음부터 끝까지 다 알고 있다고 전제할 때, ‘현재 메모리에 있는 page 중 가장 나중에 참조될 page를 swap out 한다‘라는 알고리즘을 쓸 수 있으며 이 알고리즘이 page-fault rate를 최소로 하는 알고리즘이다.

- 실제 컴퓨터 시스템에서 ‘가장 나중에 참조될 page’는 알 수 없으므로, 이 알고리즘은 비현실적인 상황을 전제로 한 이론상의 알고리즘에 불과하다. 단, replacement 알고리즘 중 이보다 더 빠른 알고리즘은 존재하지 않으므로, replaecement 알고리즘을 논하는 데 있어 이 알고리즘을 하나의 기준으로 생각할 수 있다. (이 알고리즘으로부터, ‘replacement 알고리즘에서 가장 중요한 것은 앞으로 어떤 page가 가장 덜 참조될 것인지를 예측하는 것’이라는 힌트를 얻을 수 있다. 실제로 앞으로 논의할 모든 replacement 알고리즘이 여태 참조된 page들의 이력을 통해 각 page들이 앞으로 얼마나 더 참조될지를 유추해보는 알고리즘에 해당한다.)

2) FIFO(first in first out) algorithm

- ‘메모리에 swap in된 순서대로 swap out 한다’는 알고리즘이다. 이 알고리즘은 특이하게도, 메모리의 frame 수가 적을 때보다 frame 수가 많을 때 page-fault rate가 더 높을 때가 있다. 이러한 현상을 ‘FIFO abnomaly’라 한다.

3) LRU(least recently used) algorithm과 LFU(least frequently used) algorithm

- LRU는 ‘가장 오래 전에 참조된 page를 swap out 한다’는 알고리즘이다. ‘과거에 참조된 page일수록 앞으로 다시 참조될 가능성이 낮고, 최근에 참조된 page일수록 앞으로 다시 참조될 가능성이 높다’는 추측에 기반한 알고리즘이다. LFU는 ‘가장 적게 참조된 page를 swap out 한다’는 알고리즘이다. ‘여태까지 높은 빈도로 참조된 page일수록 앞으로도 참조될 가능성이 높고, 낮은 빈도로 참조된 page일수록 앞으로도 참조될 가능성이 낮다’는 추측에 기반한 알고리즘이다.

- LRU는 doubly linked list로 구현하면 O(1)로 구현할 수 있고, LFU는 heap으로 구현하면 O(logn)으로 구현할 수 있다.

- 이들 알고리즘은 paging system에서 유용할 것으로 여겨지는 알고리즘이기는 하지만, 실제 paging system에서는 사용되지 않는다. swap in/out은 그 과정에서 OS를 사용하지 않고 하드웨어가 직접 처리하는데, swap in/out 때마다 OS를 호출해 LRU/LFU 알고리즘을 수행한다면 그로 인해 낭비될 overhead가 너무 크기 때문이다. 따라서 LRU나 LFU를 paging system에서 실제로 사용하지는 않는다.

4) clock algorithm

- 하드웨어적인 방법으로 간단하면서 LRU와 비슷한 기능을 하는 알고리즘을 구현할 수 있다. (최근에 사용된 page는 메인 메모리에 그대로 남겨두고, 최근에 사용된 적 없는 page를 swap out 한다.) 이 알고리즘은 다음 방식대로 수행된다.

(1) 각 page에 초기값이 0인 한 자리 bit를 할당하여, 그 page가 이제 막 참조되었다면 그 직후 그 bit의 값을 1로 변경하도록 한다. (이 bit를 reference bit 또는 access bit이라 한다.)

(2) swap out할 page를 가리키는 포인터를 하나 설정하여, 처음에는 0번 인덱스의 page를 가리키도록 한다.

(3) 지금 swap out을 해야 하는 상황이라면, 포인터가 현재 가리키는 page의 reference bit를 확인한다.

• reference bit가 0: 그 page를 swap out한다.

• reference bit가 1: 그 값을 0으로 바꾸고, 포인터를 그 다음 인덱스로 이동시켜 그 위치의 reference bit를 확인한다. (page들을 끝까지 탐색한 뒤라면 0번으로 다시 돌아와 탐색을 진행한다.)

- 어떤 page는 쓰기 작업이 수행된 뒤라서, swap out을 하는 경우 그 변경 내용을 디스크에 반영해주어야 하는 경우가 있을 수 있다. 이러한 경우를 대비하여, 보통은 각 page에 초기값이 0인 한 자리 bit를 할당하여 쓰기 작업이 있었다면 이를 1로 표시해 디스크에 변경사항을 반영해야 하는 page임을 swap out할 때 알 수 있게 한다. (이때, 이 bit를 modified bit 또는 dirty bit라 한다.)

4. 각 프로세스에 할당되는 frame의 개수(page frame allocation)

- 모든 프로세스를 동시에 다 메인 메모리에 로드해 두는 것은 불가능하므로, 각 프로세스에게 얼만큼의 frame을 할당하는 것이 효율적인지가 문제가 된다.

(1) 특별히 프로세스 단위로 할당할 frame을 구분하지 않고, 당장 필요한 page를 일단 메인 메모리에 올린 후 clock algorithm으로 swap out할 page를 선택해 swap out하는 식으로 각 프로세스가 갖는 frame을 관리하는 방식(global replacement)

• page 사용량이 높은 프로세스일수록 많은 frame을 차지하고, page 사용량이 낮은 프로세스일수록 적은 frame을 차지하는 방식이다.

• thrashing 문제가 발생할 위험이 있다.

(2) 프로세스 단위로 할당할 frame의 개수를 정해서 그만큼씩만 frame을 할당하고, 각 프로세스는 할당받은 frame 개수만큼만 page들을 한꺼번에 메인 메모리에 올려둘 수 있게 하는 방식(local replacement)

• 프로세스 단위로 할당할 frame을 정하는 방식은 또 다시 (a)모든 프로세스에게 동등한 개수의 frame을 할당하는 방식 (b)크기가 큰 프로세스에게 더 많은 frame을 할당하는 방식 (c)우선순위가 더 높은 프로세스에게 더 많은 frame 할당하는 방식 세 가지가 있다.

5. thrashing을 고려한 replacement 알고리즘

- 모든 프로세스는 일반적으로 특정 시간 동안 연산을 처리하기 위해 특정 영역의 page들이 한꺼번에 메인 메모리에 로드돼 있을 것을 필요로 한다는 특성을 가진다. 예를 들어 현재 어떤 프로세스가 code 내 특정 함수나 루프를 수행하는 중이라면, 최소 그 함수 또는 루프에 해당하는 코드가 담겨 있는 page가 모두 메인 메모리에 로드돼 있어야 비로소 running 상태에 있을 수 있다. (이를 locality of reference라 하며, 이때의 page 집합을 locality set이라 한다.) 만약 필요한 최소한의 page 수가 메인 메모리에 로드돼 있지 않다면 그 프로세스는 blocked 상태에 빠져 swap space로부터 필요한 page를 swap in 하게 된다.

- 보통 메인 메모리에 로드되는 프로세스가 많을수록 CPU utilization이 높아지는 경향이 있지만(그러나 CPU utilization이 100%가 되는 경우는 없는데 결국 프로세스들이 I/O 작업을 하느라 어느 프로세스도 running 상태에 있지 못하는 때가 나타나기 때문이다), 메인 메모리에 로드된 프로세스 수가 지나치게 많아지면 어느 시점부터는 CPU utilization이 급격히 감소하는 양상이 나타난다. (이러한 양상을 thrashing이라 한다.) 이는 메인 메모리에 확보한 프로세스가 너무 많아 어떤 프로세스도 running 상태에 있기 위해 필요한 최소한의 page 수를 확보하지 못하게 돼 모든 프로세스가 I/O를 하러 blocked 상태가 돼버리기 때문이다. 그럼에도 OS는 ‘메인 메모리에 로드되는 프로세스 수를 늘려야 CPU utilization이 높아질 것’이라고 판단하고 프로세스를 더 많이 로드하게 되고, 결국 thrashing이 심해지게 된다.

- thrashing은 각 프로세스가 할당을 보장받을 수 있는 최소한의 frame 수가 없는 page replacement 방식을 사용할 때 나타나며(예를 들면 global replacement 등), local replacement 방식으로 각 프로세스가 할당을 보장받을 수 있는 최소한의 frame 수를 정해주면 이 문제를 해결할 수 있다. 또, 이 문제 해결을 위해 특별히 다음과 같은 알고리즘이 고안되어 있다.

1) working-set model

- working-set model에서는 locality set을 working set이라 한다. working-set model에서는 working set이 모두 메인 메모리에 로드될 수 있는 상황에서만 프로세스가 running 상태에 들어가고, working set이 모두 메인 메모리에 로드될 수 있는 상황이 아니면 모든 page를 swap out 하고 프로세스의 상태를 suspended로 설정한다.

- working-set model은 프로세스에게 일정 수 이상의 frame을 보장한다는 측면에서 local replacement와 유사하고, 모든 프로세스에게 항상 일정 수의 frame을 보장하는 게 아니며 우선순위가 낮은 프로세스의 page는 모두 swap out 된다는 점에서 global replacement와 유사하다.

- working-set model에서는 어떤 page들을 하나의 working set으로 분류할지 결정하는 문제가 중요한 문제가 된다. page replacement의 경우와 마찬가지로 앞으로 어떤 page가 참조될지 알 수 있다면 optimal한 알고리즘을 사용할 수 있으나 이는 불가능하므로, 과거 참조된 page들의 순서로 working set을 유추해 사용하게 된다. 보통 과거부터 현 시점까지 정해진 시간 동안(\(\Delta\)) 참조된 page들이 그 시점의 working set의 원소인 것으로 본다. 예를 들어 최근 10초 동안 10개의 page들이 참조되었다면 그 10개의 page들이 현 시점의 working set이 되며, 1초 뒤에는 10초 전 working set에 포함시킨 page가 working set에서 제외된다. 그리고 그 시점에서 참조되는 page가 여태 구성한 working set에 없다면 일단 이 프로세스를 suspended 상태로 만들고, 그 page를 swap in 할 수 있을 때 그 page를 swap in 한 후 프로세스는 다시 running 상태로 돌아간다.

2) PFF(page-fault frequency)

- 프로세스의 page-fault rate를 보고, page-fault rate가 일정 수(upper bound)보다 높다면 프로세스에 할당되는 frame 수를 늘리고 page-fault rate가 일정 수(lower bound)보다 낮다면 프로세스에 할당되는 frame 수를 줄이는 식으로 page replacement를 수행하는 방식이다.

- page-fault rate가 upper bound보다 높아져 그 프로세스에 할당돼야 하는 frame 수가 더 늘어야 함에도 메인 메모리에 여유 frame이 없다면 프로세스 전체를 swap out 한다. (따라서 PFF는 얼핏 보면 local replacement에 더 가까워 보이지만, 이렇게 global replacement에 가깝게 작동하는 경우도 있다.)

6. page의 크기 결정

- page 크기가 작아지면 internal fragmentation가 감소하고 필요한 정보만 메모리에 로드할 수 있어 메모리를 더 효율적으로 사용할 수 있게 되지만, page table의 크기가 지나치게 커져 이로 인한 낭비가 발생하고 swap in/out 때 디스크에서 가져와야 하는 page의 위치를 탐색하는 데 시간을 많이 쓰게 돼 전체적인 시스템의 효율이 떨어질 위험이 있다. 또 locality 측면에서도, 함께 사용되는 page들은 대개 인접한 영역에 붙어있어 많은 page를 쓰지 않더라도 프로세스가 suspended 되지 않고 running 상태가 될 수 있는데, page의 크기가 작아져 필요한 page 수가 늘어나게 되면 아주 작은 내용 하나만 없어도 전체가 suspended 되어야 하므로 page의 크기가 너무 작은 경우 시스템의 효율이 크게 떨어질 수 있다.

- 현재 대부분의 OS에서는 4KiB로 정해져 있지만, 여러 필요해 의해 page 크기를 더 크게 사용하는 방식이 제시되고 있다.