지역성·워킹 셋·스래싱

프로그램은 한동안 몇 안 되는 페이지를 되풀이해 쓰는데, 이 쏠림이 지역성이고 최근에 쓴 페이지들의 모음이 워킹 셋입니다. 프로세스가 워킹 셋만큼 프레임을 받지 못하면 페이지 부재가 끝없이 이어져, CPU가 거의 일하지 못하는 스래싱이 생깁니다.

페이지 교체 알고리즘에서 LRU가 OPT에 다가간 것은 최근에 쓴 페이지를 곧 다시 썼기 때문입니다. 이 쏠림 덕분에 프로세스는 페이지 일부만 프레임에 두고도 부재 없이 돌 수 있습니다. 남은 물음은 프로세스 하나에 프레임을 몇 칸 주어야 하는가입니다. 아래 그림은 참조열 위로 워킹 셋을 재고, 프레임 열 칸을 나눠 받는 프로세스를 늘려 가며 CPU 이용률이 오르다 떨어지는 모습을 보입니다.

1지역성 — 시간 지역성과 공간 지역성

지역성(locality)은 프로그램이 한동안 일부 페이지만 몰아서 쓰는 쏠림입니다. 자료에 따라 구역성·국부성이라고도 부릅니다. 쏠리는 방향에 따라 둘로 나눕니다.

클러스터링과 데이터 지역화에서 따로 센 순차 지역성(저장된 차례대로 읽기)은 공간 지역성의 좁은 경우라, 자료에 따라 이렇게 둘로만 가릅니다.

2워킹 셋 — 최근에 쓴 페이지 모음

워킹 셋(working set)은 최근 Δ(델타)번의 참조에 나온 페이지들의 모음입니다. 데닝(Denning)이 내놓은 개념으로, 프로세스가 지금 쓰는 페이지가 무엇인지 재는 잣대입니다. Δ는 몇 번의 참조를 돌아볼지 정한 창의 크기입니다.

참조열 1 2 1 3 2 1 4 5 4 6 4 5를 Δ = 5로 보면 6번째까지의 워킹 셋은 1·2·3이고 12번째까지는 4·5·6입니다. 쓰는 페이지가 옮겨 가는 8번째 무렵에는 1~5 다섯 페이지로 잠깐 커집니다.

워킹 셋에 든 페이지를 모두 프레임에 두면 부재가 드뭅니다. 그래서 운영체제는 프로세스마다 워킹 셋만큼 프레임을 주려고 합니다.

3스래싱이 생기는 까닭과 막는 법

주기억장치에 함께 올린 프로세스 수를 다중 프로그래밍 정도(degree of multiprogramming)라 합니다. 이 수를 늘리면 처음에는 CPU 이용률이 오릅니다. 한 프로세스가 입출력을 기다리는 동안 다른 프로세스가 CPU를 쓰기 때문입니다(프로세스와 스레드).

그런데 프레임 수는 정해져 있어, 프로세스가 늘수록 저마다 받는 프레임이 줄어듭니다. 프레임이 워킹 셋보다 적어지면 부재가 몰리고, 프로세스들이 디스크를 기다리느라 CPU가 놉니다. 이것이 스래싱(thrashing)입니다. 이때 CPU가 노는 것을 보고 프로세스를 더 올리면 프레임이 더 모자라 스래싱이 깊어집니다.

예제

참조열 1 2 1 3 2 1 4 5 4 6 4 5에서 Δ = 5일 때 몇 순간의 워킹 셋을 셉니다.

워킹 셋은 참조 횟수를 세지 않고 나온 페이지를 한 번씩만 모읍니다. 이 참조열을 LRU로 세면 프레임 셋(워킹 셋 크기)일 때 부재 6번으로 페이지마다 처음 들어올 때뿐이고, 프레임 둘이면 부재가 9번으로 늘어납니다.

시험 포인트

• 필기: 지역성은 시간 지역성(방금 쓴 곳을 곧 다시 씀)과 공간 지역성(가까운 곳을 이어서 씀)입니다. 워킹 셋은 최근 Δ번의 참조에 나온 페이지 모음이고, 워킹 셋만큼 프레임을 주면 부재가 드뭅니다. 스래싱은 프레임이 워킹 셋보다 모자라 부재가 몰려, 프로세스를 늘렸는데 CPU 이용률이 떨어지는 현상입니다. 막는 법은 워킹 셋만큼 프레임 주기, 다중 프로그래밍 정도 낮추기, 페이지 부재 빈도(PFF)입니다. 사례를 주고 어느 지역성인지, 현상의 이름이 무엇인지 묻습니다.
• 실기: 이름은 시간 지역성(Temporal Locality), 공간 지역성(Spatial Locality), 워킹 셋(Working Set), 스래싱(Thrashing), 페이지 부재 빈도(PFF, Page Fault Frequency)로 씁니다.

확인 문제

1. 공간 지역성(spatial locality)을 보이는 것을 고르세요.

• ① 반복문이 돌 때마다 합계 변수를 다시 읽고 고친다.
• ② 2차원 배열을 행 차례로 한 칸씩 이어서 읽는다.
• ③ 같은 함수를 1초에 수백 번 부른다.
• ④ 방금 읽은 설정 값을 화면을 그릴 때마다 다시 읽는다.

2. 다음 (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

• (가) 게임이 화면을 다시 그릴 때마다 같은 캐릭터 좌표 변수를 읽습니다.
• (나) 문자열을 첫 글자부터 끝 글자까지 차례로 검사합니다.
• (다) 지난 열 번의 참조에 나온 페이지 4·7·9를 모으니, 이 프로세스가 요즘 쓰는 페이지가 보입니다.
• (라) 함께 띄운 프로그램이 너무 많아 디스크 표시등이 쉬지 않고, 마우스를 움직여도 화면이 한참 뒤에 따라옵니다.

3. 예제의 참조열에서 Δ를 5가 아니라 3으로 잡습니다. 8번째와 12번째까지의 워킹 셋을 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.

4. 프로세스 P가 디스크에서 페이지를 읽어 오는 일이 정해 둔 상한보다 잦아지자, 운영체제가 P에게 프레임을 한 칸 더 주었습니다. 이 방식의 이름을 한글 이름과 영문 약어·원어로 쓰고, 그 일이 하한보다 드물어지면 무엇을 하는지 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.