프로세스에 "충분한" 프레임이 없는 경우, 즉 작업 집합의 페이지를 지원하는 데 필요한 최소 프레임 수가 없는 경우는 고려하면, 프로세스는 빠르게 페이지 폴트(page fault)를 발생시킨다. 이 시점에서 프로세스는 특정 페이지를 교체해야 한다. 그러나 모든 페이지가 사용 중이므로, 즉시 다시 필요한 페이지를 교체해야 한다. 결과적으로, 프로세스는 즉시 다시 가져와야 하는 페이지를 교체하면서 계속해서 페이지 폴트를 발생시킨다.
이러한 높은 페이징 활동을 thrashing이라고 한다. 프로세스가 실행 시간보다 페이징에 더 많은 시간을 소모하는 경우, 프로세스가 스래싱을 겪고 있다고 한다. 스래싱은 심각한 성능 문제를 야기한다.
10.6.1 Cause of Thrashing
초기 페이징 시스템의 실제 동작을 기반으로 한 다음 시나리오를 고려하면, 운영 체제는 cpu 사용률을 모니터링한다. cpu 사용률이 너무 낮으면, 시스템에 새로운 프로세스를 도입하여 다중 프로그래밍의 정도를 높인다. 글로벌 페이지 교체 알고리즘을 사용하는데, 이 알고리즘은 페이지가 속한 프로세스와 관곙벗이 페이지를 교체한다. 프로세스가 실행의 새로운 단계에 진입하여 더 많은 프레임을 필요로 한다고 가정하면, 이 프로세스는 폴트를 발생시키고 다른 프로세스로부터 프레임을 가져간다. 하지만 이 프로세스들은 해당 페이지가 필요하기 때문에 폴트를 발생시키고, 다른 프로세스로부터 프레임을 가져간다. 폴트를 발생시킨 프로세스는 페이징 디바이스를 사용하여 페이지를 스왑 인/아웃해야한다. 페이징 디바이스를 대기열에 추가하면 ready 큐가 비워진다. 프로세스가 페이징 디바이스를 기다리는 동안, cpu 사용률은 감소한다.
cpu 스케줄러는 cpu사용률 감소를 감지하고 결과적으로 멀티프로그래밍 수준을 높인다. 새 프로세스는 실행 중인 프로세스에서 프레임을 가져와 시작하려고 시도하는데, 이로 인해 페이지 폴트가 더 많이 발생하고 페이징 디바이스의 대기열이 길어진다. 결과적으로 cpu 사용률은 더 떨어지고 cpu 스케줄러는 멀티프로그래밍의 수준을 더 높이려고 한다. 스래싱이 발생하고 시스템 처리량이 급감하고 페이지 폴트 발생률이 급격히 증가한다. 결과적으로 유효 메모리 액새스 시간이 증가한다. 프로세스가 모든 시간을 페이징에 소비하기 때문에 아무런 작업도 수행되지 않는다.
이러한 현상은 그림 10.20에서 멀티프로그래밍 정도에 따른 cpu 사용률을 나타낸 그림이다.
멀티프로그래밍 정도가 증가함에 따라 cpu 사용률도 증가하지만, 최대치에 도달할 때까지 속도가 더 느리다. 멀티프로그래밍 정도가 증가함에 따라 cpu 사용률도 증가하지만, 최대치에 도달할 때까지 속도가 더 느리다. 멀티프로그래밍 정도가 더 증가하면 스래싱현상이 발생하고 cpu 사용률은 급격히 떨어진다. 이 시점에서 cpu 사용률을 높이고 스레싱 현상을 멈추려먼 멀티프로그래밍 정도를 낮춰야 한다.
local replacement 알고리즘(또는 우선순위 교체 알고리즘)을 사용하여 스래싱의 영향을 제한할 수 있다. 앞서 언급했듯이, 지역적 교체는 각 프로세스가 자신에게 할당된 프레임 집합에서만 프레임을 선택하도록 요구한다. 따라서 한 프로세스가 스레싱을 시작하더라도 다른 프로세스의 프레임을 훔쳐 다른 프로세스도 스레싱하게 만들 수 없다. 하지만 문제가 완전히 해결된 것은 아니다. 프로세스가 스레싱을 시작하면 대부분의 시간 동안 페이징 디바이스 대기열에 머무르게 된다. 따라서 페이지 폴트 발생 시 평균 서비스 시간이 증가한다. 페이징 디바이스의 대기열이 길어지기 때문이다. 따라서 스래싱을 하지 않는 프로세스의 경우에도 유효 액세스 시간이 증가한다.
스래싱을 방지하려면 프로세스에 필요한 만큼의 프레임을 제공해야 한다. 하지만 프로세스에 필요한 프레임이 몇 개인지 어떻게 알 수 있을까? 한 가지 전략은 프로세스가 실제로 얼마나 많은 프레임을 사용하고 있는지 확인하는 것에서 시작된다. 이 접근 방식은 프로세스 실행의 지역성 모델을 정의한다. 지역성 모델은 프로세스가 실행됨에 따라 지역에서 지역으로 이동한다고 설명한다. 지역성은 함께 활발히 사용되는 페이지들의 집합이다. 실행 중인 프로그램은 칠반적으로 여러 지역성으로 구성되며, 서로 겹칠 수 있다. 예를 들어, 함수가 호출되면 새로운 지역성이 정의된다. 이 지역성에서, 메모리 참조는 함수 호출의 명령어, 지역 변수, 그리고 전역 변수의 일부에 대해 이루어진다. 함수를 종료하면, 함수의 지역 변수와 명령어가 더 이상 사용되지 않으므로 프로세스는 이 지역성을 벗어난다. 나중에 이 지역성으로 돌아갈 수 있다.
그림 10.21은 지역성 개념과 프로세스의 지역성이 시간에 따라 어떻게 변하는지 보여준다.
(a)시점에서 지역성은 {18,19,20,21,22,23,24,29,30,33} 페이지 집합이다. (b)시점에서 지역성은 {18,19,20,24,25,26,27,28,29,31,32,33}으로 변경된다. 일부 페이지(예: 18,19,20)가 두 지역성에 모두 속하므로 중복되는 부분이 있을 수 있다.
따라서 지역성은 프로그램 구조와 데이터 구조에 의해 정의된다. 지역성 모델은 모든 프로그램이 이러한 기본적인 메모리 참조 구조를 갖는다고 명시한다. 지역성 모델은 이 책에서 지금까지 캐싱에 대해 논의한 내용의 근간이 되는 원칙이다. 어떤 유형의 데이터든 접근이 패턴화되지 않고 무작위로 이루어진다면 캐싱은 무용지물이 될 것이다.
프로세스에 현재 지역성을 수용할 만큼 충분한 프레임을 할당했다고 가정하면, 프로세스는 모든 페이지가 메모리에 들어올 때까지 지역 내의 페이지에 대해 폴트를 발생시키고, 비역성을 변경할 때까지 다시 폴트를 발생시키지 않는다. 현재 지역성의 크기를 수용할 만큼 충분한 프레임을 할당하지 않으면 프로세스는 현재 사용 중인 모든 페이지를 메모리에 유지할 수 없기 때문에 스래싱 현상을 겪게 된다.
10.6.2 Working-Set Model
working-set 모델은 지역성의 가정을 기반으로 한다. 이 보델은 매개변수 ∆를 사용하여 working-set 윈도우를 정의한다. 가장 최근의 ∆ 페이지 참조에 포함된 페이지 집합이 working set(그림 10.22)이다. 페이지가 활성 상태이면 working set에 포함된다. 더 이상 사용되지 않으면 마지막 참조 후 ∆ 시간 단위만큼 working set에서 삭제된다. 따라서 working set은 프로그램 지역성의 근사치이다.
예를 들어, 그림 10.22에 표시된 메모리 참조 시퀀스에서 ∆ = 10개의 메모리 참조가 있을 때, 시간 에서 working set은 {1,2,5,6,7}이다. 시간 에서 작업 집합은 {3,4}로 변경되었다. working set의 정확도는 ∆의 선택에 따라 달라진다. ∆가 너무 작으면 전체 지역성을 포괄하지 못하고, 너무 크면 여러 지역성과 겹칠 수 있다. 극단적으로 ∆가 무한대이면 작업 집합은 프로세스 실행 중 접촉된 페이지들의 집합이된다.
따라서 작업 집합의 가장 중요한 속성은 크기이다. 시스템의 각 프로세스에 대해 작업할 크기 를 계산하면 다음과 같다.
여기서 는 프레임에 대한 총 수요이다. 각 프로세스는 working set에 있는 페이지를 활발하게 사용하고 있다. 따라서 프로세스 는 프레임을 필요로 한다. 총 수요가 사용 가능한 프레임의 총 개수보다 큰 경우 (D>m), 일부 프로세스에 충분한 프레임이 없기 때문에 스레싱이 발생한다.
∆가 선택되면 작업 집합 모델을 사용하는 것은 간단하다. 운영체제는 각 프로세스의 working set을 모니터링하고 해당 working set에 working set 크기에 맞는 충분한 프레임을 할당한다. 충분한 여유 프레임이 있으면 다른 프로세스를 시작할 수 있다. working set 크기의 합이 증가하여, 사용 가능한 프레임의 총 개수를 초과하면 운영 체제는 일시 중단할 프로세스를 선택한다. 해당 프로세스의 페이지는 기록(스왑)되고, 프레임은 다른 프로세스에 재할당된다. 일시 중단된 프로세스는 나중에 다시 시작할 수 있다.
이 working-set 전략은 멀티프로그래밍 수준을 최대한 높게 유지하면서 스래싱을 방지한다. 따라서 cpu 사용률을 최적화한다. working set 모델의 어려움은 working set을 추적하는 것이다. working-set 윈도우는 움직이는 윈도우이다. 각 메모리 참조에서, 한쪽 끝에 새로운 참조가 나타나고 가장 오래된 참조는 반대쪽 끝으로 사라진다. working set 윈도우의 어느 곳에서나 참조되는 겅우 해당 페이지는 working set에 있다.
고정 간격 타이머 인터럽트와 참조 비트를 사용하여 working set 모델을 근사할 수 있다. 예를 들어, ∆가 10,000번의 참조이고 5,000번의 참조마다 타이머 인터럽트를 발생시킬 수 있다고 가정해보면, 타이머 인터럽트가 발생하면 각 페이지의 참조 비트 값을 복사하고 지운다. 따라서 페이지 폴트가 발생하면 현재 참조 비트와 메모리 내 두 비트를 검사하여 페이지가 최근 10,000번에서 15,000번의 참조 기간 동안 사용되었는지 확인할 수 있다. 사용된 경우, 이 비트 중 적어도 하나는 켜져있을 것이다. 사용되지 않은 경우, 해당 비트는 꺼진다. 하나 이상의 비트가 켜진 페이지는 working set에 있는 것으로 간주된다.
이 배열은 5,000번의 간격 내에서 참조가 발생한 위치를 알 수 없기 때문에 완전히 정확하지는 않다. 히스토리 비트 수와 인터럽트 빈도를 증가시키면 불확실성을 줄일 수 있다(예: 10비트, 1,000번의 참조마다 인터럽트 발생). 그러나 이렇게 빈번하게 발생하는 인터럽트를 처리하는 데 드는 비용은 그만큼 높아진다.
10.6.3 Page-Fault Frequency
working-set 모델은 성공적이고, working set에 대한 지식은 프리페이징(prepage)(섹션 10.9.1)에 유용할 수 있지만, 스래싱을 제어하는 데는 다소 불편해보인다. page-fault frequency(PFF)를 사용하는 전략은 더 직접적인 접근방식을 취한다.
구체적인 문제는 스래싱을 어떻게 방지할 것인가이다. 스래싱은 페이지 부재율이 높다. 따라서 페이지 부재율을 제거해야 한다. 페이지 부재율이 너무 높으면 프로세스에 더 많은 프레임이 필요하다. 반대로 페이지 부재율이 너무 낮으면 프로세스에 프레임이 많을 수 있다. 원하는 페이지 부재율의 upper와 lower bound를 설정할 수 있다(그림 10.23). 실제 페이지 부재율이 상한을 초과하면 프로세스에 다른 프레임을 할당한다. 페이지 부재율이 하한값 아래로 떨어지면 프로세스에서 프레임을 제거한다. 따라서 페이지 부재율을 직접 측정하고 제어하여 스래싱을 방지할 수 있다.
working-set 전략과 마찬가지로 프로세스를 교체해야할 수도 있다. 페이지 부재율이 증가하고 사용 가능한 여유 프레임이 없는 경우, 일부 프로세스를 선택하여 백업 저장소로 교체해야 한다. 그런 다음 확보된 프레임은 페이지 부재율이 높은 프로세스에 배포된다.
10.6.4 Currnet Practice
실제로 스래싱과 그에 따른 스와핑은 성능에 매우 큰 영향을 미친다. 현재 컴퓨터 시스템을 구현할 때 가장 좋은 방법은 가능한 충분한 물리적 메모리를 포함시켜 스래싱과 스와핑을 방지하는 것이다. 스마트폰부터 대규모 서버에 이르기까지 극한의 상황을 제외하고는 모든 working set을 동시에 메모리에 보관할 수 있는 충분한 메모리를 제공하면 최상의 사용자 경험을 제공할 수 있다.
