요구페이징

앞에서 가상 메모리의 기초에 대해서 공부했습니다. 이번에는 가상 메모리를 어떻게 효율적으로 관리하는지에 대해 자세히 공부해보겠습니다. 먼저 요구페이징에 대해서 알아보겠습니다.

프로세스의 일부만 메모리에 가져오는 이유는 무엇일까요?

바로 메모리를 효율적으로 관리하기 위해서 입니다. 메모리가 가득차면 관리하기 어렵기 때문에 적은 양의 프로세스만 유지하는 것 입니다. 응답속도 향상을 위해 용량이 큰 프로세스를 전부 메모리로 가져와 실행하면 응답이 늦어져 필요한 모듈만 올려 실행합니다. 이 때 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구페이징이라고 합니다. 페이지를 미리 가져오는 경우 가져온 페이지를 쓰지 않을 경우 메모리 낭비를 하기 때문에 현재 운영체제에서는 요구페이징을 기본으로 사용합니다.

페이지 테이블 엔트리(PTE)의 구조

페이지가 스왑 영역에 있는 경우는 크게 두 가지입니다. 먼저 요구페이징으로 인해 처음부터 물리 메모리에 올라가지 못한 경우(현재 필요하지 않은 경우)와 메모리가 가득차서 스왑 영역으로 옮겨온 경우(가상 메모리 기초에서 살펴본 경우) 입니다.

앞에서 PTE는 페이지 번호와 프레임 번호로 구성된다고 했는데 정확히 페이지 번호, 플래그비트, 프레임 번호로 구성됩니다. 프레임 번호를 주소 필드(address field)라고도 합니다. 그렇다면 플래그비트는 무엇일까요?

• 접근비트(access bit) : 페이지가 메모리에 올라온 후 사용한 적이 있는지 알려주는 비트입니다. 해당 메모리에 읽거나 실행작업을 했다면 접근비트가 1이 됩니다.
• 변경비트(modified bit) : 페이지가 메모리에 올라온 후 데이터의 변경이 있었는지 알려주는 비트입니다. 해당 메모리에 쓰기나 추가 작업을 했다면 변경비트가 1이 됩니다.
• 유효비트(valid bit) : 페이지가 실제 메모리에 있는지 나타내는 비트입니다. 실제 메모리에 있으면 0, 없으면 1로 표시합니다.(가장 중요하지만 헷갈리는 부분입니다.)
• 읽기, 쓰기, 실행비트 : 페이지에 대한 권한을 나타내는 비트입니다. 읽기 권한이 없는 프로세스를 읽으려고 하거나 쓰기 권한이 없는 프로세스가 쓰려고 할 때 접근을 차단하는데 사용됩니다.
• 접근 비트와 변경 비트는 페이지가 메모리에 올라온 후 어떤 작업이 있었는지 알려주는 역할을 합니다.

유효비트를 통해 해당 페이지의 위치를 알 수 있기 때문에 유효비트는 굉장히 중요합니다. 따라서 유효비트에 대해 더 알아봅시다.

유효비트

• 유효비트 0 : 페이지가 메모리에 있으므로 주소 필드에 물리 메모리의 프레임 번호가 저장됩니다.
• 유효비트 1 : 페이지가 스왑 영역에 있으므로 주소 필드에 스왑 영역 내 페이지의 주소가 저장됩니다.

페이지 부재(Page fault)

프로세스가 페이지를 요청했을 때 해당 페이지가 물리 메모리에 없는 상황을 말합니다. 세그멘테이션 오류(segmentation fault)의 경우 사용자의 프로세스가 주어진 메모리 공간을 벗어나거나 접근 권한이 없는 곳에 접근할 때 발생하며 해당 프로세스를 강제 종료하며 해결하는 심각한 오류입니다. 하지만 페이지 부재(page fault)의 경우 해당 페이지가 물리 메모리에 없을 때 발생하는 자연스러운 오류로 스왑 영역에서 해당 페이지를 물리 메모리로 옮기면 해결됩니다.

페이지 부재가 발생하면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 합니다. 만약 메모리에 빈 프레임이 없을 때는 메모리에 있는 프레임 중 하나를 스왑 영역으로 보낸 후 해당 페이지를 가져올 수 있습니다. 어떤 페이지를 스왑 영역으로 보낼지 결정하는 알고리즘을 페이지 교체 알고리즘(page replacement algorithm)이라고 하며 페이지 교체 알고리즘에 의해 스왑 영역으로 보낼 페이지를 대상 페이지(victim page)라고 합니다. 그렇다면 대상 페이지는 어떻게 정해지고 페이지 교체 알고리즘에는 어떠한 것들이 있을까요?

지역성

대상 페이지와 페이지 교체 알고리즘의 선정 기준에 대해 이야기하기 전에 지역성에 대한 개념을 공부해야합니다.

지역성(locality)

• 메모리의 빈 공간이 없어 어떤 페이지를 스왑 영역으로 보낼 때는 자주 사용될 페이지를 보내면 시스템의 성능이 저하되므로 앞으로 사용하지 않을 페이지를 보내는 것이 좋습니다.
• 지역성은 기억 장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라 특정 영역에 집중되는 성질을 말합니다.
• 페이지 교체 알고리즘이 내보낼 페이지를 찾을 때 지역성을 바탕으로 합니다.

지역성의 종류에는 공간의 지역성, 시간의 지역성, 순차적 지역성이 있습니다. 기준점에 가까울수록 사용 가능성이 높기 때문에 기준점에 먼 페이지가 스왑 아웃될 가능성이 높습니다.

페이지 교체 알고리즘

페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘입니다. 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상시킵니다. 페이지 교체 알고리즘의 종류는 다음과 같습니다.

페이지 교체 알고리즘의 성능은 같은 메모리 접근 패턴을 사용하여 페이지 부재 횟수와 페이지 성공 횟수를 비교하여 측정합니다.

무작위 페이지 교체 알고리즘(random page replacement algorithm)

• 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있습니다.
• 특별한 로직 없이 무작위로 대상페이지를 선정합니다.
• 지역성을 전혀 고려하지 않기 때문에 성능이 좋지 않습니다.

FIFO 페이지 교체 알고리즘(first in, first out page replacement algorithm)

• 시간상으로 메모리에 가장 먼저 올라온 페이지를 대상 페이지로 지정하여 스왑 영역으로 보냅니다.
• 페이지의 부재는 F, 메모리에 있는 경우는 S로 표시합니다.
• 알고리즘은 큐로 구현하고 메모리 가장 위쪽에는 가장 오래된 페이지, 새로운 페이지는 맨 아래에 삽입합니다.
• 메모리가 가득 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들은 위쪽으로 이동합니다.
• 시간적 지역성을 고려했지만 무조건 오래된 페이지를 대상 페이지로 지정하기 때문에 성능이 떨어집니다.

최적 페이지 교체 알고리즘(optimal page replacement algorithm)

• 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮깁니다.
• 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 지정합니다.
• 이상적이지만 미래를 예측해야 하기 때문에 실현 불가능합니다.

LRU(least recently used) 페이지 교체 알고리즘

• 페이지에 접근한 시간을 기준으로 대상 페이지를 선정합니다.
• 최근 최소 사용 페이지 교체 알고리즘이라고도 합니다.
• 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 스왑 영역으로 옮깁니다.
• 최근에 사용된 페이지는 놔두고 오래 전에 사용된 페이지를 대상 페이지로 선정합니다.
• 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조 비트를 이용할 수도 있습니다.
• 참조 비트 시프트 방식의 경우 참조 비트의 초기 값은 0이며 페이지에 접근할 때마다 1로 바뀝니다. 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동하며 대상 페이지는 참조 비트 중 가장 작은 값을 선정합니다.
• 참조 비트 방식은 LFU 페이지 교체 알고리즘과 비슷합니다.

LFU(least frequently used) 페이지 교체 알고리즘

• 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정합니다.
• 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮깁니다. 사용 횟수가 같으면 가장 위에 있는 페이지를 대상 페이지로 지정합니다.

NUR(not used recently) 페이지 교체 알고리즘

• LRU, LFU 페이지 교체 알고리즘은 성능이 좋으나 페이지 접근을 표시해야 하기 때문에 추가적인 오버헤드가 큽니다.
• 이를 개선한 것이 NUR 알고리즘으로 두 개의 비트만으로 구현이 가능합니다.
• 최근 미사용 페이지 교체 알고리즘이라고도 부릅니다.
• 페이지마다 참조 비트와 변경 비트를 가집니다.
• 참조 비트는 페이지에 접근(read/execute)하면 1이 됩니다.
• 변경 비트는 페이지가 변경(write/append)되면 1이 됩니다.
• 모든 페이지의 초기 상태는 (0,0), 모든 값이 (1,1)이면 초기화 합니다.
• 대상 페이지를 찾을 때 참조 비트가 0인 페이지를 먼저 찾고 없으면 변경 비트가 0인 페이지를 찾습니다.
• 모든 페이지의 비트가 (1, 1)일 때는 어떤 페이지를 더 자주 사용했는지 알 수 없어 NUR을 적용할 수 없습니다. 따라서 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 초기화 합니다.

2차 기회 페이지 교체 알고리즘

• 큐를 사용하며 특이점은 특정 페이지에 접근해 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지 후보에서 제외하는 것 입니다.
• LRU, LFU, NUR보다 성능이 약간 낮고 FIFO 보다는 우수하다고 알려져 있습니다.
• 큐의 유지비용 및 중간에 있는 값을 이동하는 작업이 추가되는 단점이 있습니다.

시계 알고리즘

• 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용합니다.
• 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용합니다. 이 때 참조 비트가 1인 페이지는 0으로 만든 후에 건너뜁니다.(2차 기회를 줍니다.)
• 포인터가 큐의 맨 바닥으로 내려가면 다음 번에는 다시 큐의 처음을 가리키게 됩니다.
• 포인터가 시계처럼 한 방향으로 돌기 때문에 시계 알고리즘이라고 부릅니다.
• 참조 비트 1개가 추가되고 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경됩니다.

스레싱

하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재로 작업이 멈춘 것 같은 상태를 스레싱이라고 합니다. CPU가 작업하는 시간보다 스왑 영역으로 페이지를 보내고 새로운 페이지를 메모리에 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 되는 시점을 스레싱 발생 시점(threshing point)이라고 합니다. 물리 메모리의 크기를 늘리면 스레싱 발생 시점이 늦춰져서 프로세스를 원만하게 실행할 수 있습니다.

정적 할당과 동적 할당

프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 구분합니다. 정적 할당에는 균등 할당(equal allocation)과 비례 할당(proportional allocation)이 존재합니다. 균등 할당은 프로세스의 크기와 상관없이 사용 가능한 프레임을 모든 프로세스에 동일하게 할당하는 것 입니다. 비례 할당은 프로세스의 크기에 비례하여 프레임을 할당하는 것 입니다.

동적 할당에는 작업집합 모델(working set model)이 있습니다. 이는 지역성 이론에 근거하며 가장 최근에 접근한 프레임이 이후에도 다시 참조될 가능성이 높다는 가정하에 만들어집니다. 최근 일정 시간 동안 참조된 페이지들을 집합으로 만들고 이 집합에 있는 페이지들을 물리 메모리에 유지합니다. 작업집합 크기(working set size)는 작업집합 모델에서 물리 메모리에 유지할 페이지 크기입니다. 작업집합 윈도우는 작업집합에 포함되는 페이지 범위, 현재시점에서 최대 어느 범위까지 페이지를 살펴볼 것인가를 결정하는 것이 작업집합 윈도우입니다. 이 때 작업집합 윈도우를 너무 크게 잡으면 필요 없는 페이지가 메모리에 남아서 다른 프로세스에 영향을 미치고 너무 작게 잡으면 필요한 페이지가 스왑 영역으로 옮겨져서 프로세스의 성능이 떨어집니다 적정크기의 작업집합을 유지함으로써 메모리를 효율적으로 관리할 수 있습니다.