#가변 할당 기반 교체 기법

가변 할당 기반 교체 기법

가변 할당 기반의 교체 기법은 프로세스의 실행 중 주기억장치 할당 공간의 양을 변화시켜 페이지 부재 횟수를 줄인다.

1. 워킹셋(working set)

임의의 시점에 집중적으로 참조되는 페이지들을 모두 주기억장치에 적재시켜 프로세스로 하여금 페이지 부재를 거의 발생시키지 않고 실행할 수 있도록 한다. 워킹 셋은 현재 시점을 기준으로 최근 (window size)만큼의 시간동안 프로세스가 참조한 페이지들의 집합으로 정의된다. 즉, 최근 일정 시간동안 참조한 페이지들의 집합이 워킹 셋이며, 이 기법은 프로세스가 현재 시간 이후에도 어느 정도 시간 동안은 이 집합에 속한 페이지들을 집줃적으로 참조할 것이라는 지역성을 기반으로 한다. 이는 프로세스의 워킹 셋이 주기억장치에 적재되어 있지 않을 경우 프로세스의 실행 과정에서 페이지 부재가 과도하게 발생하는 스래싱(thrashing) 현상으로 인해 시스템 성능의 저하를 방지하고자 제시되었다.

아래 예시에서 =3이며, [1, 10]의 시간 동안 페이지 부재 발생 횟수는 5회이며, 평균 주기억장치 할당량은 3.2개이다.

시간		-2	-1	0	1	2	3	4	5	6	7	8	9	10
참조 스트링		4	3	0	2	2	3	1	2	4	2	4	0	3
주기억 장치	페이지0	?	?	0	0	0	0	-	-	-	-	-	0	0
	페이지1	?	?	-	-	-	-	1	1	1	1	-	-	-
	페이지2	?	?	-	2	2	2	2	2	2	2	2	2	2
	페이지3	?	?	3	3	3	3	3	3	3	-	-	-	3
	페이지4	?	?	4	4	-	-	-	-	4	4	4	4	4
페이지 부재 발생여부		?	?	?	F			F		F			F	F
적재 페이지		?	?	?	2			1		4			0	3
교체 페이지		?	?	?		4		0			3	1
주기억장치 할당량		?	?	-	4	3	3	3	3	4	3	2	3	4

시간2, 시간7, 시간8에서 적재되는 페이지가 없는데도 페이지 교체가 발생하며, 시간6에서 추가로 적재되는 페이지가 있어도 교체 페이지가 없다. 이는 가변 할당 기반의 기억장치 관리 기법이기 때문이다. 음영으로 표시된 부분에서 프레임이 매순간마다 변하는 것을 알 수 있다.

그러나 워킹 셋은 매 순간 상주 집합(resident set)을 조정해야 하므로 매우 큰 오버헤드를 유발한다. 이를 해결하기 위해 제시된 기법이 PFF기법이다.

2. PFF(Page Fault Frequency) 기법

PFF 기법에서는 임계값(threshold value)이라 불리는 미리 정해진 시간 간격인 파라메타 를 사용하는데, 실제 프로세스의 페이지 부재 발생 간격(IFT)을 와 비교하여 프로세스의 페이지 부재율의 높고 낮음을 결정한다.

IFT >	- 페이지 부재율이 낮음 - 참조된 페이지들만이 주기억장치에 적재되며, 나머지 페이지들은 모두 교체
IFT ≦	- 페이지 부재율이 높음 - 상주 집합은 그대로 주기억장치에 유지하고, 현재 참조된 페이지가 주기억장치에 추가로 적재되며, 프로세스에 할당된 페이지 프레임 수가 증가함

아래의 예시에서는 =2라고 가정한다.

시간		-2	-1	0	1	2	3	4	5	6	7	8	9	10
참조 스트링		4	3	0	2	2	3	1	2	4	2	4	0	3
주기억 장치	페이지0	0	0	0	0	0	0	-	-	-	-	-	0	0
	페이지1	-	-	-	-	-	-	1	1	1	1	1	-	-
	페이지2	-	-	-	2	2	2	2	2	2	2	2	2	2
	페이지3	3	3	3	3	3	3	3	3	3	3	3	-	3
	페이지4	4	4	4	4	4	4	-	-	4	4	4	4	4
페이지 부재 발생여부		F			F			F		F			F	F
적재 페이지		4			2			1		4			0	3
교체 페이지		?						0, 4					1, 3
주기억장치 할당량		-	-	-	4	4	4	3	3	4	4	4	3	4

평균 할당 시간 = (4+4+4+3+3+4+4+4+3+3)/10=3.7

PFF 기억장치 관리 기법은 프로세스가 페이지 부재를 발생시키는 빈도에 따라 주기억장치 할당량을 변화시키는 기법으로, 페이지 부재가 있을 때에만 상주 집합을 조정하기 때문에 매순간 상주 집합을 조정하는 워킹 셋에 비해 오버헤드를 크게 줄일 수 있다.

3. VMIN(Variable MIN) 알고리즘

이 기법은 가변 할당 기반의 페이지 교체 기법들 중 최적의 성능을 내기 위한 것이며,미래의 참조 스트링이 미리 알려져 있어야 하는 기법으로 현실적으로는 사용할 수 없다.

이 기법에서는 워킹 셋과 마찬가지로 (window size)를 사용하며, 상주 집합을 매순간마다 갱신한다. 즉, 프로세스가 실행하는 과정의 매 시점 t마다 [t, t+]에 해당하는 미래의 시간 간격 동안의 페이지 참조 스트링을 보고 주기억장치 상태를 변화시킨다.

아래의 예시는 =4라고 가정한다.

시간		0	1	2	3	4	5	6	7	8	9	10
참조 스트링			2	2	3	1	2	4	2	4	0	3
주기억 장치	페이지0	-	-	-	-	-	-	-	-	-	0	-
	페이지1	-	-	-	-	1	-	-	-	-	-	-
	페이지2	-	2	2	2	2	2	2	2	-	-	-
	페이지3	3	3	3	3	-	-	-	-	-	-	3
	페이지4	-	-	-	-	-	-	4	4	4	-	-
페이지 부재 발생여부			F			F		F			F	F
적재 페이지			2			1		4			0	3
교체 페이지						3	1			2	4	0
주기억장치 할당량		-	2	2	2	2	1	2	2	1	1	1

평균 할당 시간 = (2+2+2+2+1+2+2+1+1+1)/10=1.6

참조 자료

엄영익·정태명 공저, 『컴퓨터 운영체제론』, 생능출판사

http://metro9780.tistory.com/4