페이지 교체 알고리즘

앞 글에서 빈 프레임이 없을 때 페이지 폴트가 나면 기존 페이지 하나를 내보내야 한다는 것을 보았습니다. 어떤 페이지를 내보낼지는 성능을 크게 좌우합니다. 곧 다시 쓸 페이지를 내보내면 바로 다시 폴트가 나서 그 페이지를 읽어 와야 하고, 이런 잘못된 선택이 쌓이면 시스템 전체가 디스크 입출력에 묶여 멈추다시피 하는 스래싱으로 이어집니다. 이 글에서는 내보낼 페이지를 고르는 대표적인 알고리즘들을 같은 입력으로 비교하고, 스래싱이 왜 생기고 어떻게 막는지 살펴봅니다.

알고리즘을 비교하는 방법

페이지 교체 알고리즘은 참조 문자열(reference string)에 대해 페이지 폴트가 몇 번 나는지로 비교합니다. 참조 문자열은 프로세스가 접근하는 페이지 번호를 차례로 적은 것입니다. 이 글에서는 다음 참조 문자열과 프레임 3개를 기본으로 씁니다.

7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

공정하게 비교하려면 참조 문자열, 프레임 수, 처음 상태를 모두 같게 해야 합니다. 이 글에서는 프레임이 모두 비어 있는 상태에서 시작하므로, 처음 들어오는 페이지들도 폴트로 셉니다. 다음 코드는 이 글에서 다룰 알고리즘 가운데 FIFO, OPT, LRU, Clock 네 가지를 한꺼번에 구현한 시뮬레이터입니다. 각 알고리즘의 원리는 아래에서 차례로 설명합니다.

def simulate(policy, pages, num_frames):
    frames, faults = [], 0               # frames: 정책마다 순서의 뜻이 다르다
    ref_bits, hand = {}, 0               # Clock이 쓰는 참조 비트와 시계 바늘
    for i, page in enumerate(pages):
        if page in frames:               # 적중
            if policy == "LRU":
                frames.remove(page)
                frames.append(page)      # 가장 최근에 쓴 것을 맨 뒤로
            ref_bits[page] = 1
            continue
        faults += 1
        if len(frames) < num_frames:
            frames.append(page)
        elif policy in ("FIFO", "LRU"):
            frames.pop(0)                # FIFO는 가장 먼저 들어온 것, LRU는 가장 오래 안 쓴 것
            frames.append(page)
        elif policy == "OPT":
            future = pages[i + 1:]
            victim = max(frames, key=lambda f: future.index(f) if f in future else len(future))
            frames[frames.index(victim)] = page   # 가장 늦게 다시 쓰일 페이지를 내보낸다
        elif policy == "Clock":
            while ref_bits[frames[hand]]:          # 참조 비트가 1이면 0으로 바꾸고 지나간다
                ref_bits[frames[hand]] = 0
                hand = (hand + 1) % num_frames
            del ref_bits[frames[hand]]
            frames[hand] = page
            hand = (hand + 1) % num_frames
        ref_bits[page] = 1
    return faults

pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
for policy in ("FIFO", "OPT", "LRU", "Clock"):
    print(f"{policy:5}: 프레임 3개 {simulate(policy, pages, 3):2}번, 4개 {simulate(policy, pages, 4):2}번")

belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for policy in ("FIFO", "LRU"):
    print(f"Belady 문자열 {policy}: 프레임 3개 {simulate(policy, belady, 3)}번, 4개 {simulate(policy, belady, 4)}번")

FIFO : 프레임 3개 15번, 4개 10번
OPT  : 프레임 3개  9번, 4개  8번
LRU  : 프레임 3개 12번, 4개  8번
Clock: 프레임 3개 14번, 4개  9번
Belady 문자열 FIFO: 프레임 3개 9번, 4개 10번
Belady 문자열 LRU: 프레임 3개 10번, 4개 8번

프레임 3개에서 FIFO는 15번, LRU는 12번, Clock은 14번 폴트를 내고, 이론상 가장 좋은 OPT는 9번입니다. 아래에서 각 결과가 어떻게 나왔는지 살펴보겠습니다.

FIFO: 가장 먼저 들어온 페이지부터

FIFO(first-in, first-out)는 메모리에 가장 먼저 들어온 페이지를 가장 먼저 내보냅니다. 페이지가 들어온 순서대로 큐에 넣어 두고 맨 앞에서 꺼내면 되므로 구현이 가장 단순합니다. 하지만 들어온 시점만 볼 뿐 얼마나 자주 쓰이는지는 보지 않으므로, 처음부터 계속 쓰이는 중요한 페이지도 오래되었다는 이유로 내보냅니다. 그래서 프레임 3개에서 15번으로 가장 많은 폴트를 냅니다.

벨러디의 모순

FIFO에는 이상한 성질이 있습니다. 프레임을 늘렸는데 오히려 폴트가 늘어나는 경우가 있는 것입니다. 시뮬레이터 출력의 마지막 두 줄이 그 예로, 참조 문자열 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5에서 FIFO는 프레임 3개일 때 9번, 4개일 때 10번 폴트를 냅니다. 메모리를 더 주었더니 더 느려진 셈입니다. 1969년 라슬로 벨러디(László Bélády)가 발견해 벨러디의 모순(Belady's anomaly)이라고 부릅니다.

같은 참조 문자열에서 LRU는 프레임 3개일 때 10번, 4개일 때 8번으로, 프레임을 늘리면 폴트가 줄어듭니다. LRU와 OPT는 스택 알고리즘(stack algorithm)이라는 성질을 가집니다. 프레임이 $n$개일 때 메모리에 있는 페이지들이 언제나 프레임이 $n + 1$개일 때 메모리에 있는 페이지들에 포함된다는 성질로, 이 성질이 있으면 프레임을 늘려서 폴트가 늘어나는 일이 생길 수 없습니다. FIFO는 이 성질이 없어서 모순이 생깁니다.

OPT: 앞으로 가장 늦게 쓰일 페이지를

OPT(optimal) 알고리즘은 앞으로 가장 오랫동안 쓰이지 않을 페이지를 내보냅니다. 앞으로 다시 쓰일 때까지 가장 많이 남은 페이지를 내보내면, 그 페이지를 다시 읽어 오는 일을 가장 늦출 수 있기 때문입니다. 같은 참조 문자열과 프레임 수에서 OPT보다 폴트가 적은 알고리즘은 없음이 증명되어 있고, 스택 알고리즘이므로 벨러디의 모순도 없습니다.

문제는 앞으로 어떤 페이지를 언제 쓸지를 알아야 한다는 것입니다. 시뮬레이터는 참조 문자열 전체를 미리 알고 있으므로 pages[i + 1:]로 미래를 볼 수 있지만, 실행 중인 운영체제는 미래의 접근을 알 수 없습니다. 그래서 OPT는 실제로 쓸 수 없고, 다른 알고리즘이 얼마나 좋은지를 재는 기준선으로 씁니다. 어떤 알고리즘의 폴트 수가 OPT에 가깝다면, 더 개선할 여지가 적다는 뜻입니다.

LRU: 가장 오래 쓰지 않은 페이지를

LRU(least recently used)는 가장 오랫동안 쓰이지 않은 페이지를 내보냅니다. 최근에 쓰이지 않은 페이지는 앞으로도 한동안 쓰이지 않을 가능성이 높다는 시간 지역성에 기대어, 과거로 미래를 짐작하는 것입니다. OPT가 미래를 보고 가장 늦게 쓰일 페이지를 고른다면, LRU는 과거를 보고 가장 오래 쓰이지 않은 페이지를 고르는 셈입니다. 프레임 3개에서 12번으로, FIFO보다 OPT에 가깝습니다.

FIFO와 LRU의 차이는 적중했을 때 드러납니다. 시뮬레이터에서 LRU는 적중한 페이지를 목록의 맨 뒤로 옮기지만, FIFO는 그대로 둡니다. 참조 1, 2, 3, 1, 4를 프레임 3개로 처리해 보면, 넷째 참조 1에서 LRU는 1을 가장 최근 것으로 옮겨 목록이 [2, 3, 1]이 되고, 다섯째 참조 4가 들어올 때 가장 오래된 2를 내보냅니다. FIFO는 1이 다시 쓰였는데도 들어온 순서만 보므로, 4가 들어올 때 가장 먼저 들어온 1을 내보냅니다. 방금 쓴 1을 내보낸 FIFO는 그 뒤에 1을 다시 쓰면 또 폴트를 냅니다.

정확한 LRU를 구현하기 어려운 이유

LRU를 정확히 구현하려면 모든 메모리 접근마다 순서 정보를 고쳐야 합니다. 페이지마다 마지막으로 접근한 시각을 기록하는 방법은 접근할 때마다 시각을 써야 하고, 내보낼 때는 모든 페이지의 시각을 비교해야 합니다. 접근한 페이지를 이중 연결 리스트의 맨 뒤로 옮기는 방법은 내보낼 페이지를 바로 찾을 수 있지만, 접근할 때마다 리스트의 연결을 고쳐야 합니다. 메모리 접근은 1초에 수십억 번 일어나므로, 하드웨어가 이를 대신해 주지 않는 한 어느 방법도 감당할 수 없습니다. 그래서 실제 운영체제는 LRU를 근사합니다.

Clock: 참조 비트로 LRU를 흉내 내기

대부분의 CPU는 페이지가 접근될 때 페이지 테이블 항목의 참조(accessed) 비트를 하드웨어가 1로 만들어 줍니다. 이 비트로는 언제 접근되었는지는 알 수 없지만, 마지막으로 비트를 0으로 지운 뒤에 접근된 적이 있는지는 알 수 있습니다. Clock 알고리즘은 이 비트 하나로 LRU를 흉내 내며, 2차 기회(second chance) 알고리즘이라고도 부릅니다.

Clock은 프레임들을 원형으로 늘어놓고, 시계 바늘처럼 도는 포인터를 하나 둡니다. 페이지를 내보내야 할 때 바늘이 가리키는 페이지의 참조 비트를 확인합니다. 비트가 0이면 최근에 쓰이지 않은 것이므로 그 페이지를 내보냅니다. 비트가 1이면 최근에 쓰인 것이므로 한 번 더 기회를 주어 비트를 0으로 지우고 바늘을 다음으로 옮깁니다. 모든 페이지의 비트가 1이라면 바늘이 한 바퀴를 돌며 모두 0으로 지운 뒤, 처음 페이지로 돌아와 그 페이지를 내보내므로 FIFO와 같아집니다.

기회를 얻은 페이지는 바늘이 한 바퀴 돌아올 때까지 다시 쓰이면 비트가 다시 1이 되어 또 살아남고, 쓰이지 않으면 다음에 바늘을 만났을 때 내보내집니다. 그래서 자주 쓰이는 페이지는 남고, 한동안 쓰이지 않은 페이지가 나가게 됩니다. 시뮬레이터에서 Clock은 프레임 3개에서 14번으로 LRU보다는 많지만 FIFO보다는 적습니다. 접근할 때마다 소프트웨어가 할 일은 없고, 하드웨어가 비트를 켜 주므로 정확한 LRU보다 훨씬 싸게 구현할 수 있습니다.

바뀐 페이지를 함께 고려하기

개선된 Clock 알고리즘은 참조 비트(R)와 함께 변경 비트(M)도 봅니다. 바뀐 페이지를 내보내려면 디스크에 써야 하므로, 같은 조건이라면 바뀌지 않은 페이지를 먼저 내보내는 것이 쌉니다.

첫째 부류부터 찾아 내보내면, LRU를 흉내 내면서도 디스크에 써야 하는 일을 줄일 수 있습니다. Linux는 이런 생각을 확장해, 페이지를 활성 목록과 비활성 목록 두 개로 나누어 LRU를 근사하고, 6.1부터는 페이지를 여러 세대로 나누어 관리하는 다세대 LRU(multi-generational LRU, MGLRU)도 선택할 수 있게 했습니다.

LFU와 MFU: 사용 횟수로 고르기

LFU(least frequently used)는 쓰인 횟수가 가장 적은 페이지를 내보냅니다. 자주 쓰인 페이지는 앞으로도 자주 쓰일 것이라는 가정입니다. 하지만 예전에 많이 쓰였다가 이제는 쓰이지 않는 페이지가, 쌓아 둔 높은 횟수 덕분에 오랫동안 내보내지지 않는 문제가 있습니다. 그래서 일정한 간격마다 횟수를 반으로 줄여, 오래전의 접근일수록 영향을 덜 주게 하는 감쇠(aging)를 함께 씁니다. 이는 5장의 에이징과 이름은 같지만, 기다린 작업의 우선순위를 올리는 것이 아니라 오래된 기록의 무게를 줄이는 것입니다.

반대로 MFU(most frequently used)는 쓰인 횟수가 가장 많은 페이지를 내보냅니다. 횟수가 적은 페이지는 방금 들어와 아직 쓰일 기회가 적었을 뿐이라는 생각입니다. 두 알고리즘 모두 횟수를 세는 비용이 크고, 어느 쪽이 나은지는 참조 패턴과 횟수를 같게 셀 때의 처리 규칙에 따라 달라져, 범용 운영체제의 페이지 교체에는 잘 쓰이지 않습니다.

알고리즘 비교

그림처럼 각 알고리즘은 서로 다른 정보로 판단합니다. FIFO는 들어온 순서, OPT는 미래의 다음 참조, LRU는 마지막으로 쓴 시점, Clock은 최근에 쓰였는지를 나타내는 비트 하나, LFU는 쓰인 횟수를 봅니다. 그래서 같은 참조 문자열과 프레임 수에서만 공정하게 비교할 수 있으며, 한 입력에서 나온 결과를 모든 입력으로 넓혀 말할 수는 없습니다.

스래싱

페이지 폴트가 지나치게 많아져, 프로세스들이 실제 일보다 페이지를 내보내고 들여오는 데 더 많은 시간을 쓰는 상태를 스래싱(thrashing)이라고 합니다. 고전적인 설명은 다음과 같은 악순환입니다. 실행 중인 프로세스가 너무 많아, 각 프로세스가 자주 쓰는 페이지들을 모두 합친 양이 물리 메모리보다 커집니다. 그러면 모든 프로세스가 끊임없이 폴트를 내고, 디스크 입출력을 기다리느라 CPU 사용률이 떨어집니다. 이때 CPU가 한가한 것만 보고 프로세스를 더 실행하면, 메모리가 더 모자라져 상황이 더 나빠집니다. 오늘날의 운영체제가 모두 이렇게 프로세스를 더 넣는 것은 아니지만, 자주 쓰는 페이지를 메모리에 다 담을 수 없다는 근본 원인은 같습니다.

작업 집합 모델

이를 막으려면 각 프로세스가 지금 자주 쓰는 페이지가 얼마나 되는지 알아야 합니다. 앞 글에서 본 작업 집합(working set)을 이용합니다. 시각 $t$의 작업 집합은 그 직전 $\Delta$번의 참조에 나온 페이지들의 집합입니다. 다음 코드는 한 참조 문자열에서 시각과 창의 크기에 따라 작업 집합이 어떻게 달라지는지 계산합니다.

def working_set(pages, t, delta):
    """시각 t까지의 최근 delta번 참조에 나온 페이지들"""
    return sorted(set(pages[max(0, t - delta + 1): t + 1]))

pages = [1, 2, 1, 3, 1, 2, 4, 5, 4, 5, 4, 6, 5, 4]
for t in (4, 9, 13):
    for delta in (3, 6):
        ws = working_set(pages, t, delta)
        print(f"t={t:2}, 창 {delta}: {ws} ({len(ws)}개)")

t= 4, 창 3: [1, 3] (2개)
t= 4, 창 6: [1, 2, 3] (3개)
t= 9, 창 3: [4, 5] (2개)
t= 9, 창 6: [1, 2, 4, 5] (4개)
t=13, 창 3: [4, 5, 6] (3개)
t=13, 창 6: [4, 5, 6] (3개)

프로그램은 처음에 페이지 1, 2, 3을 주로 쓰다가, 뒤에는 4, 5, 6을 주로 씁니다. 작업 집합은 이 변화를 따라갑니다. 창의 크기 $\Delta$를 고르는 것이 중요합니다. 창이 너무 작으면 지금 쓰는 페이지 일부를 놓치고, 너무 크면 이미 쓰지 않게 된 예전 페이지까지 포함합니다. 시각 9에서 창이 6이면 이미 쓰지 않는 1과 2가 함께 들어가 4개가 되지만, 창이 3이면 지금 쓰는 4와 5만 들어갑니다.

운영체제가 각 프로세스의 작업 집합 크기 $WSS_i$를 알면, 모두를 합친 요구량 $D = \sum WSS_i$를 쓸 수 있는 프레임 수 $m$과 비교할 수 있습니다. $D$가 $m$보다 크면 모든 프로세스의 작업 집합을 담을 수 없으므로 스래싱의 위험이 큽니다. 이때는 새 프로세스를 들이지 않거나, 일부 프로세스를 잠시 멈추고 그 프레임을 회수해, 남은 프로세스들의 작업 집합이 메모리에 들어가게 합니다. 다만 여러 프로세스가 함께 쓰는 공유 라이브러리 페이지는 여러 번 세지 않아야 하고, 회수할 수 있는 페이지 캐시도 따로 생각해야 하므로, 실제 계산은 이 식보다 복잡합니다.

Linux에서 스래싱 진단하기

스래싱이 의심되면 다음 명령으로 여러 지표를 함께 봅니다. vmstat 1과 sar -B 1은 1초마다 새 줄을 찍는 반면, /proc/pressure/memory는 읽을 때마다 최근 10초, 60초, 300초 동안의 평균을 한꺼번에 보여 줍니다. sar는 sysstat 패키지에 들어 있어 따로 설치해야 할 수 있습니다.

vmstat 1          # si, so: 스왑 입출력, wa: 입출력 대기, us, sy, id: CPU 사용
sar -B 1          # majflt/s: 초당 메이저 폴트, pgscank/s: 회수할 페이지를 찾느라 훑은 수
cat /proc/pressure/memory   # 메모리를 기다리느라 멈춘 시간의 비율(PSI)

스래싱 상태에서는 vmstat의 si와 so가 계속 크고, CPU 시간의 대부분이 입출력 대기(wa)로 가며, 사용자 코드(us)는 거의 실행되지 않습니다. 다만 si와 so는 스왑의 입출력만 보여 주므로, 파일에서 온 페이지를 버렸다가 다시 읽는 일이 되풀이되는 경우는 sar -B의 메이저 폴트 수로 함께 봐야 합니다. Linux 4.20부터 제공하는 PSI(pressure stall information)는 메모리가 모자라 작업들이 멈춰 있던 시간의 비율을 직접 보여 주므로, 메모리 압박의 정도를 판단하는 데 특히 유용합니다. vmstat의 첫 줄은 부팅한 뒤의 평균이므로 둘째 줄부터 읽어야 한다는 점도 기억해 두세요. 한 순간의 값보다 이 지표들이 시간에 따라 함께 나빠지는지를 봐야 합니다.

스래싱을 풀려면 메모리 요구를 줄이거나 메모리를 늘려야 합니다. 동시에 실행하는 작업을 줄이고, 메모리 누수가 있는 프로세스를 찾아 고치거나 다시 시작하며, 근본적으로는 메모리를 늘립니다. 스왑을 더 빠른 SSD로 옮기면 증상은 덜해지지만, 메모리가 모자라다는 원인은 그대로이므로 임시방편일 뿐입니다.

OOM 킬러

페이지를 회수하고 스왑을 써도 메모리가 모자라 더 할당할 수 없게 되면, Linux 커널은 마지막 수단으로 OOM 킬러(out-of-memory killer)를 실행해 프로세스 하나를 강제로 끝내고 그 메모리를 회수합니다. 어떤 프로세스를 끝낼지는 주로 메모리를 얼마나 쓰는지로 계산한 oom_score로 정하며, 점수가 가장 높은 프로세스가 희생자가 됩니다.

pid=1234                               # 살펴볼 프로세스의 PID로 바꾼다
cat /proc/$pid/oom_score               # 지금의 OOM 점수
cat /proc/$pid/oom_score_adj           # 점수 조정값(-1000부터 1000까지)
dmesg | grep -i "killed process"       # OOM 킬러가 끝낸 프로세스의 기록

oom_score_adj를 높이면 그 프로세스가 먼저 희생되고, 낮추면 덜 희생되며, -1000으로 정하면 OOM 킬러의 대상에서 아예 빠집니다. 데이터베이스처럼 중요한 프로세스를 지키려고 쓰기도 하지만, 그만큼 다른 프로세스가 대신 희생되고, 그 프로세스 자체가 메모리를 끝없이 쓰는 경우라면 시스템 전체가 위험해질 수 있으므로 신중하게 써야 합니다. 컨테이너에서는 cgroup의 메모리 한도를 넘으면 그 cgroup 안에서 OOM 킬러가 실행되므로, 컨테이너가 이유 없이 재시작된다면 dmesg나 컨테이너 런타임의 기록에서 OOM으로 끝났는지부터 확인합니다.

더 깊이: 참조 비트를 묶어서 읽는 다세대 LRU

Clock 알고리즘은 페이지마다 참조 비트를 확인하는데, 실제 커널에서는 이 확인이 생각보다 비쌉니다. 하드웨어가 세우는 참조 비트는 페이지 테이블 항목에 있으므로, 물리 페이지 하나가 쓰였는지 알려면 그 페이지를 매핑한 페이지 테이블 항목들을 역매핑(reverse mapping, rmap)으로 찾아야 하기 때문입니다. MGLRU 설계 문서는 매핑된 페이지를 주로 쓰는 작업에서 이 탐색이 페이지 회수 경로의 가장 큰 CPU 비용이 될 수 있다고 설명합니다. 그래서 MGLRU는 프로세스의 페이지 테이블을 차례로 훑어 최근에 쓰인 항목을 한꺼번에 찾고 참조 비트를 지우는 방법을 rmap과 함께 씁니다.

MGLRU는 비슷한 시기에 쓰인 페이지들을 세대(generation)로 묶습니다. 노화(aging)는 새 세대를 만들어 최근에 쓰인 페이지를 젊은 세대로 옮기고, 축출(eviction)은 가장 오래된 세대부터 페이지를 내보냅니다. 관리자 안내서에 따르면 CONFIG_LRU_GEN으로 빌드한 커널에서는 /sys/kernel/mm/lru_gen/enabled로 이 기능을 켜고 끕니다.

스래싱을 막는 설정도 있습니다. /sys/kernel/mm/lru_gen/min_ttl_ms에 N을 쓰면 최근 N밀리초 동안 쓰인 작업 집합은 내보내지 않고, 그 작업 집합을 메모리에 둘 수 없으면 OOM 킬러가 실행됩니다. 안내서는 1000 정도면 스래싱으로 생기는 견디기 힘든 지연이 대개 사라지고, 값을 키울수록 지연은 줄지만 OOM 킬러가 너무 일찍 실행될 위험이 커진다고 설명합니다. 기본값 0은 이 기능을 끈 상태입니다.

정리

• 페이지 교체 알고리즘은 같은 참조 문자열과 프레임 수, 처음 상태에서 페이지 폴트 수로 비교합니다.
• FIFO는 가장 먼저 들어온 페이지를 내보내 구현이 단순하지만, 프레임을 늘려도 폴트가 늘 수 있는 벨러디의 모순이 있습니다.
• OPT는 앞으로 가장 늦게 쓰일 페이지를 내보내 폴트가 가장 적지만, 미래를 알아야 하므로 기준선으로만 씁니다.
• LRU는 가장 오래 쓰지 않은 페이지를 내보내 OPT에 가깝지만, 정확히 구현하기 어려워 참조 비트를 쓰는 Clock으로 근사합니다. LRU와 OPT는 스택 알고리즘이어서 벨러디의 모순이 없습니다.
• 스래싱은 자주 쓰는 페이지들을 모두 메모리에 담을 수 없을 때 생기며, 작업 집합의 합을 프레임 수와 비교해 위험을 판단하고, 작업을 줄이거나 메모리를 늘려 풉니다.
• 메모리를 끝내 마련할 수 없으면 Linux의 OOM 킬러가 oom_score가 가장 높은 프로세스를 끝냅니다.

연습 문제

1. 짧은 참조 문자열로 세 알고리즘 비교하기

참조 문자열 1, 2, 3, 1, 4, 1, 2를 빈 프레임 3개로 처리합니다. FIFO, LRU, OPT 각각의 폴트 수와, 페이지 4가 들어올 때 내보내는 페이지를 구하세요. OPT가 이 결과를 내려고 쓴 정보는 무엇인가요?

2. 공유 페이지와 작업 집합의 합

같은 시간 창에서 세 프로세스의 작업 집합이 W1 = {A, B, C}, W2 = {B, C, D}, W3 = {D, E}이고, 쓸 수 있는 프레임은 6개입니다. 같은 글자가 여러 프로세스가 함께 쓰는 같은 물리 페이지를 뜻하는 경우와, 글자가 같아도 프로세스마다 따로 있는 페이지를 뜻하는 경우에 각각 필요한 프레임 수를 구하고 스래싱의 위험을 판단하세요.

3. 메모리를 늘렸더니 느려졌다

FIFO 페이지 교체를 쓰는 작은 임베디드 시스템에서, 메모리를 늘렸더니 어떤 작업의 페이지 폴트가 오히려 늘었다는 보고가 들어왔습니다. 이것이 가능한 일인지 설명하고, 같은 일이 생기지 않게 하려면 교체 알고리즘을 어떻게 바꾸면 되는지 제안하세요.

다음 장의 파일의 개념과 속성에서는 운영체제가 관리하는 또 다른 핵심 자원인 파일 시스템으로 넘어가, 파일이 무엇이고 운영체제가 파일을 어떻게 다루는지 살펴봅니다.