[Chapter 9. 가상 메모리] 스레싱

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

스레싱 (Thrashing)

---

스레싱은 과도한 페이징 작업으로

프로세스들이 실제 실행되는 시간보다 페이지를 교체하는 데에 더 많은 시간을 사용하고 있는 현상을 말한다.

 

 

운영체제는 CPU의 이용률(utilization)을 계속 감시하고 있다.

 

만약 CPU 이용률이 너무 낮아지면 이때 운영체제는 새로운 프로세스를 시스템에 더 추가하여

다중 프로그래밍의 정도(degree of mulitprogramming)을 높인다.

 

이때 전역 페이지 교체 알고리즘을 사용해서 어떤 프로세스의 페이지인지에 대한 고려 없이 교체를 수행하게 된다.

 

발생 원인

1.

어떤 프로세스가 새로운 실행 단계로 진입하여 더 많은 프레임을 필요로 할 때

페이지 부재가 발생하면서 다른 프로세스로부터 프레임들을 가져오게 된다.

 

2.

만약 교체된 페이지들이 해당 프로세스에서 필요로 하는 것이었다면

그 프로세스에도 역시 페이지 부재가 발생하여 또 다른 프로세스에서 프레임을 가져오게 될 것이다.

 

이런 프로세스들은 페이지 스왑 인, 스왑 아웃을 위해 페이징 장치를 사용해야 하는데,

이들이 페이징 장치를 기다리는 동안 CPU의 이용률은 떨어진다.

 

3.

CPU 스케줄러는 이용률이 떨어지는 것을 보고,

이용률을 높이기 위해 새로운 프로세스들을 추가하여 다중 프로그래밍의 정도를 높이려고 한다.

 

하지만 새로 시작하는 프로세스는 실행중인 프로세스들로부터 프레임을 가져오고자 할 것이며

이것은 더 많은 페이지 부재와 더 긴 페이징 장치 대기 시간을 일으키게 된다.

 

4.

CPU 이용률 계속해서 더 떨어지고 CPU 스케줄러는 다중 프로그래밍 정도를 더 높이려고 한다.

 

 

따라서 실질 메모리 접근 시간은 증가하고,

프로세스들은 페이징을 하는데에 시간을 다 소비하게 되어서 결국 아무런 일도 할 수 없게 된다.

 

 

작업 집합 모델 (Working-Set Model)

스레싱을 방지하기 위해서는 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 한다.

 

그렇다면 각 프로세스가 현재 시점에서 필요로 하는 최소한의 프레임 개수를 알 수 있는 방법이 필요한데,

지역성 모델(locality model)에 근거한 작업 집합 모델을 활용하는 것이 한 방법이 된다.

 

 

 

지역(locality)은 집중적으로 함께 참조되는 페이지들의 집합을 의미하고,

지역성 모델(locality model)은 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말한다.

 

한 프로그램은 여러 개의 지역으로 구성되어 있고, 이 지역들은 서로 겹칠 수 있다.

 

 

작업 집합(Working-Set)이란 가장 최근의 △개 페이지 참조에 들어있는 서로 다른 페이지의 집합을 말한다.

 

작업 집합은 지역성의 근사값이 되며, 정확도는 △의 선택에 따라 좌우된다.

* △가 작으면 전체 지역을 충분히 포함하지 못함

* △가 크면 여러 지역성을 과도하게 수용하게 될 것임 (지역이 서로 겹침)

 

작업 집합 모델

 

---

운영체제는 작업 집합을 스레싱 감시에 활용하게 된다.

 

각 프로세스가 WSS.i 만한 크기의 공간을 작업 집합의 크기로 요구한다면 모든 프로세스 전체의 요구량 D는 다음과 같다.

* WSS : Working Set Size

만약 요구량 D가 시스템이 보유한 총 프레임 수 m보다 커지면 (D > m)

어떤 프로세스는 지역을 위한 충분한 프레임을 할당받을 수 없게 되기 때문에 해당 시점부터 스레싱이 발생 가능하다고 볼 수 있다.

* m = M / S (M : 메모리의 총 크기, S : 페이지의 크기)

 

 

 

따라서 운영체제는 각 프로세스의 작업 집합의 크기에 맞는 충분한 프레임을 할당하고,

여분의 프레임이 있으면 새로운 프로세스를 시작시킬 수 있다.

 

각 작업 집합의 크기 총 합(D)이 유효 프레임 수(m)보다 커지게 되는 경우

운영체제가 프로세스를 하나 선택하여 그 프로세스를 중지시키는 것을 통해 스레싱을 예방한다.

(중기 스케줄러 차원에서 Swap-in과 Swap-out을 통해 스레싱이 일어나지 않는 한도 내에서 프로세스의 개수를 탄력적으로 조정)

 

 

이 방법을 통해 가능한 최대의 다중 프로그래밍의 정도를 유지하면서 스레싱을 방지할 수 있게 되며, CPU의 이용률도 최적화된다.

 

---

하지만 작업 집합을 추적하는 작업이 필요하게 된다.

 

작업 집합은 메모리 참조마다 한쪽에서는 새로운 페이지들이 추가되고 다른 쪽에서는 가장 오래된 참조부터 제외된다.

작업 집합 창 내의 어디에서라도 참조되는 페이지는 작업 집합에 속한다.

 

우리는 일정 간격 타이머 인터럽트(fixed-interval timer interrupt)와 참조 비트(reference bit)을 통해

어느 정도 유사한 모델을 근사할 수 있다.

 

 

 

운영 방법

1. 타이머 인터럽트가 걸릴 때마다 각 페이지의 현재 참조 비트의 값을 저장해두고, 참조 비트는 0으로 재설정한다.

(ex. △ = 10,000, 매 5,000번의 참조마다 타이머 인터럽트를 걸음)

 

2. 페이지 부재가 발생하면 바로 앞 현재 참조 비트와 앞서 저장된 2개의 참조 비트 값을 검사한다.

(바로 앞 10,000에서 15,000번의 참조 사이에 그 페이지가 사용되었는가를 알기 위함)

 

3. 셋 중 어느 한 비트라도 1인 페이지는 작업 집합에 속하는 페이지이다.

 

 

 

이 방법은 페이지에 대한 참조가 어디에서 일어났는지 까지는 정확하게 알 수 없기 때문에 완전히 정확한 것은 아니다.

 

과거 기억 비트 수를 늘리고, 타이머 인터럽트 빈도를 높이면 정확도를 높일수는 있으나

인터럽트 처리 오버헤드는 그에 따라 증가하게 되는 것을 유의해야 한다.

 

페이지 부재 빈도 (Page-Fault Frequency, PFF)

스레싱은 결국 페이지 부재 빈도 문제이다.

우리가 원하는 것은 페이지 부재율을 조절하는 것이다.

 

페이지 부재율이 높다는 것은 그 프로세스가 더 많은 프레임을 필요로 한다는 것을 의미하고,

페이지 부재율이 낮다는 것은 프로세스가 너무 많은 프레임을 갖고 있다는 것을 의미한다.

 

 

따라서 임의 프로세스에 대하여 원하는 페이지 부재율의 상한선과 하한선을 정해놓고,

1. 페이지 부재율이 상한선을 넘으면 더 많은 프레임을 할당

2. 페이지 부재율이 하한선을 넘으면 프레임을 회수

 

 

이렇게 하는 방식으로 직접적으로 부재율을 관찰, 조절하는 것을 통해 스레싱을 방지할 수 있다.