프로세스 적재 정책

스레싱(Thrashing)
페이지 교환이 계속 일어나는 현상.
어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 크면 ‘스레싱을 하고 있다’고 말함.

스레싱 발생 원인.
운영체제는 항상 프로세서의 효율성(이용률)을 감시하여 운영.
이용률이 떨어지면 이를 높이기 위해 새로운 프로세스를 도입, 다중 프로그래밍의 정도를 높임.
- 새로운 프로세스가 수행 중인 프로세스의 페이지를 빼앗아서 수행을 시작할 경우 더 많은 페이지  부재 발생.
- 프로세서가 요구하는 최소한의 수보다 페이지 프레임 수가 적으면 적을수록 페이지 부재율이 증가함.
- 페이지 부재가 많이 일어날수록 프로세스가 페이징 처리장치를 기다리는 시간이 길어지므로  프로세스의 효율성은 떨어짐.

※ 페이지 부재로 프로세서의 이용률 감소 시 스레싱이 발생하여 시스템의 처리율은 낮아지고 페이지 부재는 늘어나 유효 메모리 액세스 시간이 증가, 페이지 교체시간이 낭비됨.

[그림 8-30] 스레싱.
프로세서의 이용률과 다중 프로그래밍의 정도에 따라 다름.
- 다중 프로그래밍의 정도가 높아지면 프로세서의 이용률도 최대값이 될 때까지 증가.
- 다중 프로그래밍의 정도가 더욱 커지면 스레싱이 발생, 프로세서의 이용률은 급격히 떨어짐.
프로세서의 이용률을 높이고 스레싱을 중단하려면 다중 프로그래밍의 정도를 낮춰야 함.

스레싱 예방.
지역 교환 알고리즘이나 우선순위 교환 알고리즘을 사용하여 제한할 수 있음.
- 지역 교환 알고리즘 사용 시 프로세스 하나에 스레싱이 발생하더라도 다른 프로세서에서 프레임을  가지고 올 수 없어 다른 프로세스는 스레싱 현상에 빠지지 않음.
- 여러 프로세스에서 스레싱이 발생할 경우 프로세스들은 대부분의 시간을 페이징 처리장치를  기다리는 큐에서 보냄.
- 스레싱은 발생하지 않으나 유효 액세스시간은 증가함.

지역성(국부성)
실행 중인 프로세스에 의해 나타나는 특성.
프로세스들은 실행기간 동안 메모리 내의 정보를 균일하게 액세스하는 것이 아닌 페이지 중 일부를 선호하여 지역적인 부분만을 집중적으로 참조하는 현상.
프로그램들의 순환(Looping)이나 부 프로그램, 스택, 변수들의 계산과 합계, 배열 순례, 순차적 코드의 실행 등으로 발생.
프로그래머들이 관련 있는 변수들을 서로 근처에 배치시키기 때문에 발생함.
[그림 8-31] 여러 페이지에 대한 프로세스의 메모리 참조 유형.

지역성의 종류.
시간 지역성.
- 참조된 기억장소는 가까운 미래에도 계속 참조될 가능성이 높음을 의미함.
- 순환구조의 루틴, 부프로그램, 스택, 계산이나 합계의 변수 등.
공간 지역성.
- 프로세스가 어떤 기억장소를 한 번 참조하면, 이후에 참조한 기억장치 근처에 있는 기억장소를  참조할 가능성이 높음을 의미함.
- 배열 순례(검색 작업), 순차적 코드의 실행, 근처의 관련 변수 선언 등.

스레싱 현상 방지를 위해 각 프로세스가 필요로 하는 프레임을 제공할 수 있어야 함.
지역성을 이용하여 현재의 지역 크기보다 적은 페이지 프레임 할당 시 페이지 부재 발생의 원인이 될 수 있음.

작업설정 모델(Working Set Model)
프로그램의 수행과정을 지역성 개념으로 설명하기 위해 데닝이 개발.
프로세스가 많이 참조하는 페이지 집합을 메모리 공간에 계속 상주시켜 빈번한 페이지 대치 현상을 줄이는 방법.
프로세스의 작업모델 구성을 위해 작업설정의 크기를 알아야 하며, 작업설정의 크기는 작업설정 창을 이용하여 구함.
- 작업설정 창 정의를 위해 매개변수 ∆를 사용, ‘현재 시간(t)에서 최근의 일정 시간 단위(∆)’를  정하여 결정.
- 작업설정 창의 크기는 매개변수인 ∆에 따라 달라짐.
- 가장 최근의 ∆ 페이지 참조를 조사, 가상 시간 t로부터 프로세스가 참조한 페이지 집합을 나타냄.
- 어떤 페이지가 실제로 사용되고 있으면 페이지는 작업설정에 포함, 마지막으로 참조된 후 ∆ 시간  동안 참조되지 않으면 더 이상 사용하지 않는 것으로 간주되어 작업설정에서 빠짐.
- 따라서 가장 최근의 페이지 참조에 있는 페이지 집합을 작업설정이라 하며, 이때 작업설정은  프로그램의 지역 근사치임.
최근에 참조된 페이지들을 메인 메모리에 유지시켜 프로세스가 빠르게 실행될 수 있음.
새로운 프로세스들은 메인 메모리에 그들의 작업설정들이 적재할 수 있는 공간이 있을 때만 시작될 수 있음.

[그림 8-32] 프로세스 작업설정 정의.
데닝은 시간 t에서의 작업설정 WS(t, w)를 시간 (t-w)부터 t까지의 프로세스 시간 간격에 참조한 페이지들의 집합으로 정의.
- t : 현재 프로세스 시간(프로세서를 점유하고 있는 시간).
- w : 프로세스 창의 크기로 프로세스들의 작업설정을 계산할 때 과거 어느 시간까지 포함할 지를 나타냄.

[그림 8-33] 창 크기와 작업설정
- w가 증가함에 따라 작업설정의 크기가 변함.
- 창의 크기(설정시간 간격) w가 커짐에 따라 메인 메모리에 유지하는 작업설정이 커지나, w가 너무  커지면 메인 메모리의 용량을 초과하므로 작업설정도 증가하지 않음.

[그림 8-34] 작업설정 모델 예.
그림과 같이 메모리 참조 순서가 주어졌을 때(∆=10이라 가정), t1 시간의 작업설정은 {1,2,5,6,7}이 되며, t2 시간에는 {3,4}임.
작업설정의 정확성은 ∆ 의 선택에 따라 좌우됨.
- ∆ 값이 너무 작으면 전체 작업설정을 충족시키지 못함.
- ∆ 값이 너무 크면 여러 전체 프로그램이 됨.

매드닉(Madnick)과 도노반(Donovan)은 적절한 값으로 10,000을 제안함.

작업설정의 가장 중요한 성질은 작업설정의 크기.
시스템 내의 각 프로세스에 대한 작업설정의 크기 WSSi를 계산하면 전체 요구 프레임 D는 아래와 같음.

- 각 프로세스는 각 작업설정 내에 있는 페이지를 실제로 사용하고 있음.
- 프로세스 i는 WSSi 프레임을 필요로 함.
- 유효 프레임(m) 수보다 많이 요구하게 되면(D>m) 스레싱 발생.
- 프로세스가 수행되는 동안, 작업설정은 계속 변화함.
[그림 8-35] ∆ 값이 고정된 경우, 시간이 경과함에 따라 변화되는 작업설정 크기.
- 대부분의 프로세스에서 작업설정의 크기가 비교적 변화가 없는 안정기와 급격하게 변화하는  과도기가 반복되는 현상을 보임.
- 프로세스가 처음 시작(실행)되면 새로운 페이지를 참조하므로 작업설정의 크기가 급격하게 커짐.
- 지역성의 원리에 의거하여 프로세스는 안정기에 접어들게 되며, 과도기는 프로세스가 다른 지역으로  이동(프로세스의 전환)함을 보여줌.

작업설정 모델 사용법.
운영체제는 각 프로세스의 작업설정을 감시, 각 프로세스에 작업설정의 크기에 맞는 충분한 프레임을 할당.
여분의 페이지 프레임이 있을 때는 준비상태에 있는 다른 프로세스를 불러들인 후 프레임을 할당하여 다중 프로그래밍의 정도를 증가시킴.
모든 프로세스가 갖는 작업설정 크기의 합이 전체 유효 프레임의 수보다 커지게 되면 잠시 중지시킬 프로세스를 선정하여 페이지를 회수.
※ 가능한 다중 프로그래밍의 정도를 높이면서 스레싱을 방지하는 효과를 제공, 프로세서의 효율성을 최적화시킴.

작업설정 모델에서 해결해야 할 문제점.
우선 작업설정이 갖는 과거의 참조가 미래의 참조를 항상 보장하지는 않음.
작업설정의 크기와 구성 페이지들은 시간 경과에 따라 변함.
각 프로세스에 대한 작업설정을 모두 측정한다는 것은 현실적으로 불가능함.
작업설정은 프로세스가 실행됨에 따라 삭제, 추가되기도 하므로 변화가 심함.
각 프로세스가 참조한 페이지 시간과 시간 순서로 된 페이지 큐를 유지해야 하므로 작업설정에 의한 메모리 관리는 복잡함.
작업설정 창의 크기를 나타내는 매개 변수인 ∆ 의 최적값이 알려져 있지 않으며, 처리되는 프로세스의 성격에 따라 ∆ 의 최적값은 매우 다양함.

※ 정확한 참조 대신 프로세스의 페이지 부재율에 관심을 갖고 프로세스 상주 집합의 크기를  늘리는 만큼 페이지 부재율은 낮아지는 효과를 활용한 결과로 많은 운영체제에서 사용됨.

[그림 8-36] 작업설정 크기에 따른 페이지 프레임 수와 페이지 부재율과의 관계.
작업설정 크기가 너무 작고 페이지 프레임 수가 적으면 페이지 부재율이 높아 프로세스의 실제 작업 페이지들이 메모리에 있지 않고 스레싱 현상을 일으킬 수 있음.
작업설정 크기가 너무 크고 페이지 프레임 수가 너무 많으면 프로세스의 실제 작업 페이지들 뿐만 아니라 다른 페이지까지 메모리를 차지하여 메모리 낭비가 발생하며 다중 프로그래밍의 정도를 감소시킬 수 있음.

페이지 부재 빈도(PFF, Page Fault Frequency)
스레싱 예방을 위한 직접적인 액세스 방법.
페이지 환경에서 프로세스의 실행을 측정하는 기준이 됨.
페이지 부재가 발생할 때 조절하여 작업설정 모델보다 오버헤드가 적음.
- 작업설정 모델은 페이지가 메모리에 액세스할 때 조절.
스레싱은 페이지 부재에서 발생하므로 페이지 부재비율 조절이 필요함.
- 페이지 부재 비율이 높음 = 프로세스가 더 많은 프레임을 필요로 함.
- 페이지 부재 비율이 낮음 = 프로세스가 너무 많은 프레임을 갖고 있음.
[그림 8-37] 페이지 부재 빈도.
- 하나의 프로세스가 갖는 페이지 프레임 수에 따라 페이지 부재 비율이 변화화는 과정을 보여주는  그래프.

※ 페이지 부재 빈도 알고리즘은 페이지 참조가 새로운 지역으로 이동하는 과도기에는 제대로 작동하지  않음(페이지가 마지막으로 참조된 후 임의의 시간 단위(∆)가 경과되기 전까지 그대로 임).