[운영체제] 쓰레싱 및 커널메모리

쓰레싱(Thrashing)

• 프레임이 충분히 할당되지 않은 프로세스는 page fault가 발생할 가능성이 높다. page fault가 발생할 때마다 페이지 교체가 필요하게 되지만, 나머지 프레임들도 이미 활발하게 사용중이므로 어떤 페이지가 교체되든 바로 다시 필요해질 것이다.
• 결과적으로 계속 반복하여 page fault가 발생하게 되는 악순환이 생긴다. 이렇게 과도한 페이징 작업을 쓰레싱이라고 부른다. 즉, 어떤 프로세스가 실제 실행보다 페이징에 더 많은 시간을 사용할 경우 쓰레싱이 발생했다고 한다.
• 이러한 쓰레싱 현상은 CPU 스케줄러에 의해 야기되기도 한다. 운영체제는 CPU의 이용률을 감시하면서 이용률이 떨어지는 것을 확인하면 이용률을 높이기 위해 새로운 프로세스를 추가해 다중 프로그래밍의 정도를 높인다. 그에 따라 새로 실행되는 프로세스는 실행중인 프로세스들로부터 프레임을 가져오려고 시도하면서 더 많은 page fault와 더 긴 페이징 장치 대기 시간을 야기한다. 결과적으로 CPU 이용률은 다시 떨어지고 CPU 스케줄러는 또 다시 다중 프로그래밍의 정도를 높이려고 시도한다. 이러한 악순환은 결과적으로 쓰레싱을 발생시킨다. 실질적인 메모리 접근 시간은 증가하고 프로세스들은 페이징하는 데 시간을 다 소비하게 되어 아무 작업도 처리할 수 없게 된다.
• 이렇듯 다중 프로그래밍 정도는 점점 늘어날수록 CPU 이용률을 증가시키지만 일정 수준을 넘기면 쓰레싱이 발생하면서 CPU 이용률이 급격히 떨어진다. 이를 해결하기 위해선 희생할 프로세스를 선정, 수행을 중단시켜야한다.

---

작업 세트 모델

• 이러한 쓰레싱 현상을 방지하려면 각 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해주어야 한다.
• 지역(locality) : 집중적으로 함께 참조되는 페이지들의 집합
• 지역성 모델(locality model) : 프로세스가 실행될 때 항상 어떤 특정 지역에서 메모리를 집중적으로 참조함을 뜻한다. 이러한 지역성은 page fault의 변화에서도 나타난다. 주로 특정 지역에서 특정 지역으로 빠져나가면서 page fault rate가 급격히 변화한다.
• 작업 세트 : 최근 Δ개 페이지 참조의 서로 다른 페이지의 집합
• Δ는 작업세트 윈도우라고 한다. 페이지가 작업집합윈도우 내에서 한 번이라도 참조되었으면 작업 세트에 포함된다. 페이지가 더 이상 사용하지 않게 되면 마지막 참조로부터 Δ만큼의 페이지 참조 후엔 작업 세트에서 제외된다.
• 즉, 작업 세트는 프로그램 지역성의 근사값이 되어 준다.
• 이런 작업 세트의 정확도는 Δ값에 따라 좌우된다. Δ가 너무 작으면 지역을 제대로 포함하지 못할 것이고, Δ가 너무 크면 여러 지역을 과도하게 포함할 수 있다. 극단적으로 Δ가 커지면 프로세스가 실행중에 만난 모든 페이지가 작업 세트가 된다.
• 작업 세트 모델 : 이러한 프로세스 실행의 지역성 모델을 기반으로 최수 프레임 개수를 추정한다. 각 프로세스가 실제로 사용중인 프레임 수가 몇 개인지를 지속적으로 세면서 작업 세트 크기 변화를 관찰한다.
• 이러한 작업세트에 포함된 페이지 갯수는 시시각각 변화하는데, 이 갯수가 작아지면 특정 지역에 들어갔음을 의미한다. 이를 안정기라고 한다. 반대로 갯수가 많다는 뜻은 아직 지역에 제대로 들어가지 못했음을 의마한다. 이를 과도기라고 한다.
• 쓰레싱이 시작되는 시점은 각 프로세스들이 필요로 하는 작업세트에 포함된 페이지 갯수가 전반적으로 늘어나, 서로간의 프레임이 부족해질 때이다. 작업 세트 개념을 통해 이러한 순간을 감지해낸다.

쓰레싱 감시에 작업 세트 활용

• 작업세트에 포함된 갯수, 즉, 작업세트 크기의 총합을 구한다. 프로세스 i가 요구하는 작업세트 크기를 WSSi라고 하면, 전체 프로세스의 요구 크기는 시그마 WSSi가 될 것이다. 이를 D로 표현한다.
• 만약 D가 시스템이 보유한 총 페이지 수 m보다 커진다면 (D > m) 쓰레싱이 발생할 수 있다. 이런 원리로 쓰레싱을 감지한다.
• 작업세트 윈도우 값인 Δ값만 정해지면 각 프로세스 작업 세트를 지속적으로 산출해내면서, 각 프로세스에 작업세트 크기에 맞는 충분한 개수의 프레임을 할당한다. 이 작업 후에도 프레임에 여유가 있다면 새로운 프로세스를 시작할 수 있다.
• 그러다 프로세스 수가 많아지면서 D가 m보다 커지면 운영체제는 프로세스를 하나 선택해 해당 프로세스의 페이지를 빼앗고, 연기시킨다. 그리고 해당 페이지를 다른 프로세스에 준다.
• 이러한 작업을 '중기 스케줄링'이라고 하며, 해당 프로세스에 대해 스왑 아웃(swap-out) 및 스왑 인(swap-in)이 일어난다.
• 이와 같이 스왑인과 스왑아웃을 활용하면서 m을 기준으로 쓰레싱이 일어나지 않는 한도내에서 프로세스의 개수를 탄력적으로 조정하면 시스템의 이용률을 최고로 끌어 올릴 수 있을 것이다.
• 참고로 총 프레임 개수 m = M(메모리 사이즈)/S(페이지 크기) 이다.

작업세트 모델 구현

• 이러한 작업세트 모델을 실질적으로 사용할 수 있도록 구현할 때 어려운 점은 작업 세트를 매번 추적하는 일이다.
• 작업 세트는 메모리 참조가 일어날 때마다 한 쪽에서는 새로운 페이지들이 추가되고, 다른 쪽에서는 가장 오래된 참조부터 제외된다.
• 작업 세트 창의 어디에서라도 참조되는 페이지는 작업 세트에 속한다.
• 이러한 작업 세트를 지속적으로 얻어내기 위해 타이머 인터럽트와 참조비트를 사용한다.
• 타이머 인터럽트가 걸릴 때마다 각 페이지의 현재 참조 비트의 값을 저장하고 참조 비트를 0으로 재설정한다. page fault가 발생하면 바로 앞 현재 참조 비트와 앞서 저장된 2개의 참조 비트 값을 검사한다. 셋 중 하나의 비트라도 1인 페이지는 작업 집합이 된다.
• 그러나 이 방법은 정확한 것은 아니어서 그 페이지에 대한 참조가 과거 5,000번 중 어디에서 일어났는지까지를 정확히 알 수없다.
• 과거를 기억하는 비트 수를 늘리고 타이머 인터럽트 빈도를 높이면 좀 더 정확해질 것이다. 하지만 그렇게 할 경우 인터럽트 처리 오버헤드가 증가할 수 있다.

페이지 부재 빈도

• 작업 세트 모델은 작업 세트를 알 수 있어 지역성을 유지하는 장점이 있지만 작업 세트 크기의 변화를 통해 쓰레싱을 조정하므로 한계가 분명하다.
• 페이지 부재 빈도 (PFF) 방식 : 쓰레싱은 결국 page fault가 높다는 것을 의미하고, page fault rate가 높다는 것은 그 프로세스가 더 많은 프레임을 필요로 한다는 의미있다. 반대로 page fault rate가 너무 낮으면 프로세스가 너무 많은 프레임을 가지고 있다는 것을 의미한다. 이에 대한 page fault rate의 상한과 하한을 정해놓고, 만약 page fault rate가 상한을 넘으면 해당 프로세스에 프레임을 더 할당하고, 하한보다 작아지면 프레임을 줄여준다. 이렇게 직접적으로 각 프로세스의 page fault rate를 관찰하고 조정하는 방식으로 쓰레싱을 방지한다.
• page fault rate가 높아져 새 프레임이 필요한데 현재 남는 프레임이 없으면 한 프로세스를 선택해 해당 프로세스를 예비 저장 장치로 스왑 아웃해야 한다. 이렇게되면 해당 프로세스에 할당되었던 프레임이 page fault rate가 높아진 프로세스에게 분배되어 쓰레싱을 피할 수 있게된다.

Kernel Memory Allocation

• 커널 메모리는 보통 사용자 모드 프로세스들에게 할당해주기 위한 프레임 리스트와는 별도의 메모리 풀에서 할당된다.
• 커널은 다양한 크기의 자료구조를 위해 메모리를 할당받는데, 해당 자료구조들은 페이지 크기보다 작은 크기를 갖기도 한다. 따라서 커널은 메모리를 조심스럽게 사용해야 하고, 단편화에 의한 낭비는 최소화할 필요가 있다.
• 많은 운영체제가 커널 코드나 커널이 사용하는 데이터를 위해 페이징을 하지는 않기 때문에 더 중요하다.
• 사용자 모드 프로세스에게 할당되는 페이지들은 물리 메모리상에서 굳이 연속일 필요는 없다. 하지만 가상 메모리 인터페이스를 통하지 않고 물리 메모리에 직접 접근하는 특정 하드웨어 장치는 물리적으로 연속적인 메모리를 필요로 할 수 있다.
• 이러한 이유로 커널의 메모리 관리는 가상메모리기법과 다른 기법을 사용한다. 이러한 기법에는 버디 시스템과 슬랩 할당이 있다.

버디 시스템

• 버디 시스템 : 물리적으로 연속된 페이지들로 이루어진 고정된 크기의 세그먼트로부터 메모리를 할당받는다. 메모리는 해당 세그먼트로부터 'Power-of-2 allocator'에 의해 2의 거듭제곱 단위로 할당 된다. (4KB, 8KB, 16KB, ...)
• 만약 2의 거듭제곱 단위가 아닌 메모리 요구가 생기면 가장 가까운 2의 제곱 크기로 올림되어 할당된다.
• 간단한 예를 들어보자. 메모리 세그먼트의 크기는 초기에 256KB이다. 커널은 21KB의 메모리를 요구했다. 세그먼트는 AL, AR로 표시하는 128KB 크기의 두개의 버디로 나누어진다. 그러나 21KB의 가장 가까운 2의 거듭제곱은 32KB이므로 AL이 BL,BR로, 또 BL이 CL, CR로 나뉘어 이 버디 중 하나가 21KB의 요구를 처리하기 위해 사용된다.
• 버디 시스템의 이점 중 하나는 합병이라고 부르는 과정으로 서로 인접한 버디들이 손쉽게 하나의 큰 세그먼트로 합쳐질 수 있다는 것이다. 앞서 든 예시에서 CL을 할당받은 커널이 CL을 다시 해제하면 시스템은 CL와 CR를 다시 하나의 세그먼트로, BL과 BR도 하나의 세그먼트로 만들 수 있다. 결국 원래의 256KB 세그먼트로 돌아온다.
• 버디 시스템의 단점은 2의 거듭제곱 단위를 사용하기 때문에 할당된 세그먼트에서 단편화가 발생한다는 것이다.

슬랩 할당

• 슬랩 : 하나 또는 그 이상의 연속된 페이지
• 캐시 : 하나 혹은 그 이상의 슬랩으로 구성
• 커널이 사용하는 각 자료구조마다 하나의 캐시가 존재한다. 즉, PCB를 위한 캐시, 파일 객체를 위한 캐시, 세마포어를 위한 캐시 등이 별도로 존재하는 것이다. 각 캐시는 각 커널 자료 구조의 인스턴스에 해당하는 객체로 채워진다.
• 예를 들면 세마포어를 위한 캐시에는 세마포어 객체가, PCB를 위한 캐시에는 PCB 객체가 채워진다.
• 즉, 캐시란 같은 자료구조의 객체를 위한 전용 저장소라고 할 수 있다.
• 슬랩 할당 알고리즘은 커널 객체를 저장하기 위해 캐시를 운용한다. 캐시가 생성되면 초기에 free라고 표시한 객체들을 캐시에 미리 마련한다. 즉, preallocation해놓는다.
• 캐시 내 객체 수는 슬랩의 크기에 좌우된다. 예를 들어 한 페이지가 4KB인 경우 12KB 슬랩은 3개의 페이지로 구성, 2KB 객체를 6개 포함할 수 있다.
• 초기에는 캐시 내 모든 객체를 free로 표시한다. 그러다 커널이 해당 자료구조의 객체를 필요로 하면 free 객체들 중 하나를 캐시로부터 할당해준다. 그리고 할당된 객체는 used라고 표시한다.
• 예를 들어 커널이 슬랩 할당기에게 PCB 객체를 위한 메모리 공간을 요구한다고 해보자. Linux 시스템에서 PCB는 struct taskstruct 자료 구조로 표현되며 대략 1.7 KB 정도를 요구한다. Linux 커널은 새로운 프로세스를 생성할 때 캐시에게 struct task-struct 객체를 위한 메모리 할당을 요청한다. 그러면 캐시는 이 요청을 처리하기 위해 이미 슬랩에 할당되어 있던 free로 표시된 struct taskstruct 객체에서 하나를 신속하게 할당해주고 used로 표시를 하게 되는 것이다.
• 이러한 슬랩 할당 방법을 사용하면 내부단편화도 없고, 할당 속도도 매우 빨라질 것이다.

슬랩 할당의 상태

• 이런 방법으로 운영하는 캐시가 가지고 있는 슬랩은 세 가지 상태 중 한 가지 상태를 가진다.
• Full : 슬랩 내의 모든 객체가 used로 표시된 상태
• Empty : 슬랩 내의 모든 객체가 free로 표시된 상태
• Partial : used, free 객체가 섞여 있는 상태
• 슬랩 할당기는 가장 먼저 Partial 슬랩의 free 객체를 이용해 요청을 처리하려고 시도한다. 만약, Partial 슬랩이 없으면 Empty 슬랩으로부터 free 객체들 할당한다. 만약 Empty 슬랩 조차도 없는 경우에는 연속된 물리 메모리에서 새로운 슬랩이 할당되어 캐시에 주어진다. 그러면 객체는 이 새로운 슬랩에서 할당된다.
• 슬랩 할당은 각 커널 객체마다 캐시가 존재하고 해당 캐시는 객체의 크기로 나누어지는 '청크(chunk)'들로 구성되므로, 단편화가 발생하지 않는 장점이 있다. 또한 객체들이 미리 생성되어 있어 캐시에서 쉽게 할당할 수 있기 때문에 메모리 요청이 매우 빠르게 처리된다. 따라서 할당과 해제가 빈번한 자료구조를 처리하는데 특히 효율적이다.