클럭 알고리즘(clock algorithm)

출처: https://steady-coding.tistory.com/526

 

출처: https://velog.io/@holicme7/OS-%EB%A9%94%EB%AA%A8%EB%A6%AC%EA%B4%80%EB%A6%AC7-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%981

 

문제)

시스템의 페이지 프레임 수는 4개입니다. 페이지 참조 시퀀스는 다음과 같습니다. 1, 2, 3, 4, 1, 2 ,5 1, 2 모든 페이지의 참조 비트는 초기에 0으로 설정됩니다. Clock알고리즘을 사용하여 각 페이지 참조 후의 페이지 프레임 상태로 아래 표를 채우시오.

 

해답)

페이지 참조	프레임 상태	시계 바늘 위치	참조 비트	페이지 폴트 발생	비고
1	[1, -, -, -]	[1, 0, 0, 0]	[1, 0, 0, 0]	X	원리(1)+(2)
2	[1, 2, -, -]	[1, 0, 0, 0]	[1, 1, 0, 0]	X	원리(1)+(2)
3	[1, 2, 3, -]	[1, 0, 0, 0]	[1, 1, 1, 0]	X	원리(1)+(2)
4	[1, 2, 3, 4]	[1, 0, 0, 0]	[1, 1, 1, 1]	X	원리(1)+(2)
1	[1, 2, 3, 4]	[1, 0, 0, 0]	[1, 1, 1, 1]	X	원리(2), 이미 참조되어 있으므로, 통과
2	[1, 2, 3, 4]	[1, 0, 0, 0]	[1, 1, 1, 1]	X	원리(2), 이미 참조되어 있으므로, 통과
5	[5, 2, 3, 4]	[1, 0, 0, 0]	[1, 0, 0 ,0]	O	원리(3)+(4) 페이지 교체 -> 시계바늘 한바퀴 돌면서 0을 찾아나선다. + 찾지 못했으면 시계 바늘은 다음 페이지로 움직이면서 머물렀던 페이지를 0으로 초기화해줌.
1	[5, 1, 3, 4]	[0, 1, 0, 0]	[0, 1, 0, 0]	O	원리(3)->원리(4)
2	[5, 1, 2, 4]	[0, 1, 0, 0]	[0, 1, 1, 0]	X	원리(2), 이미 참조되어 있으므로, 통과

 

생각해볼 문제 - 응용)

만약, 1, 2, 3, 4, 5, 2 , 6, 1, 2의 순서로 참조된다면,

페이지 참조	프레임 상태	시계 바늘 위치	참조 비트	페이지 폴트 발생
1	[1, -, -, -]	[1, 0, 0, 0]	[1, 0, 0, 0]	X	원리(1)+(2)
2	[1, 2, -, -]	[1, 0, 0, 0]	[1, 1, 0, 0]	X	원리(1)+(2)
3	[1, 2, 3, -]	[1, 0, 0, 0]	[1, 1, 1, 0]	X	원리(1)+(2)
4	[1, 2, 3, 4]	[1, 0, 0, 0]	[1, 1, 1, 1]	X	원리(1)+(2)
5	[5, 2, 3, 4]	[1, 0, 0, 0]	[1, 0, 0, 0]	O	원리(3)+(4) 페이지 교체 -> 시계바늘 한바퀴 돌면서 0을 찾아나선다. + 찾지 못했으면 시계 바늘은 다음 페이지로 움직이면서 머물렀던 페이지를 0으로 초기화해줌.
2	[5, 2, 3, 4]	[1, 0, 0, 0]	[1, 1, 0, 0]	X	원리(2), 이미 참조되어 있으므로, 통과
6	[5, 2, 6, 4]	[0, 0, 1, 0]	[0, 0, 1, 0]	O	참조비트가 0인 페이지를 찾아나섬-> 원리(3)
1	[5, 2, 6, 1]	[0, 0, 0, 1]	[0, 0, 0, 1]	O	원리(3)->원리(4)
2	[5, 2, 6, 1]	[0, 0, 0, 1]	[0, 1, 0, 1]	X	원리(2), 이미 참조되어 있으므로, 통과

 

원리)

(1) 참조 비트 초기화:

모든 페이지의 참조 비트는 초기에 0으로 설정

(2) 페이지 참조 시 참조 비트 설정:

페이지가 참조될 때마다 해당 페이지의 참조 비트가 1로 설정된다

(3) 페이지 교체:

시스템이 페이지를 교체해야 할 때, clock 알고리즘은 '시계 바늘'이 가리키는 페이지부터 순차적으로 검사한다. 참조 비트가 0인 페이지를 찾을 때까지 시계 바늘을 한 칸씩 이동시키며, 참조비트가 1인 페이지를 만나면 그 비트를 0으로 설정하고 다음 페이지로 이동한다.

(4) 교체 대상 선정:

참조 비트가 0인 페이지를 찾으면, 그 페이지가 교체 대상으로 선정된다. 이 페이지는 새로운 페이지로 교체되면, 교체된 페이지의 참조 비트는 1로 설정된다.

 

시계 바늘이 이동시점) 페이지 부재 발생시에 페이지 교체가 일어나면서