#클럭 알고리즘과 2차 기회 알고리즘

클럭(Clock) 알고리즘과 2차 기회(Second Chance) 알고리즘

1. 클럭(Clock) 알고리즘

주기적으로 0으로 재설정하지 않는 시스템을 가정하며, 주기억장치에 적재된 페이지들을 환형리스트로 보고 각 페이지를 시계 방향으로 움직이는 포인터를 사용하여 교체될 페이지를 선정한다. 원칙은 다음과 같다.

① 현재 포인터가 가리키는 페이지의 참조 비트 검사 ② 해당 페이지가 리스트에 있고 참조 비트가 0이라면 1로 재설정. 이 때 포인터는 움직이지 않음 ③ 그 값이 0이면 해당 페이지를 교체하고 포인터를 시계 방향으로 한 단계 진행 후 선정 과정 종료 ④ 그 값이 1이면 해당 페이지의 참조비트를 0으로 재설정하고 포인터를 한 단계 진행 후 단계①부터 반복

페이지 프레임이 4개이고 각 페이지 프레임에 a, b, c, d가 적재되어 있을 때, 다음 참조 스트링을 처리하는 동안 페이지 부재가 몇 회 발생하는지 분석하라. 참조비트는 모두 1로 설정되어 있다. (→:포인터 위치)

참조스트링 = c a d b e b a b c d

시간	0	1	2	3	4	5	6	7	8	9	10
참조 스트링		c	a	d	b	e	b	a	b	c	d
프레임0/참조비트		→a/1	→a/1	→a/1	→a/1	e/1	e/1	e/1	e/1	→e/1	d/1
프레임1		b/1	b/1	b/1	b/1	→b/0	→b/1	b/0	b/1	b/1	→b/0
프레임2		c/1	c/1	c/1	c/1	c/0	c/0	a/1	a/1	a/1	a/0
프레임3		d/1	d/1	d/1	d/1	d/0	d/0	→d/0	→d/0	c/1	c/1
페이지 부재 발생		X	X	X	X	O (a→e)	X	O (c→a)	X	O (d→c)	O (e→d)

2. 2차 기회(Second Chance) 알고리즘

기본적으로 클럭 알고리즘과 유사하며, 페이지 교체 과정에서 갱신 비트도 함께 검사한다. 원칙은 다음과 같다

① 현재 포인터가 가리키는 페이지의 참조 비트(r)와 갱신 비트(m) 검사 ② 해당 페이지가 리스트에 있고 참조 비트가 0이라면 1로 재설정. 이 때 포인터는 움직이지 않음 ③ 아래의 표에 따라 과정 수행
(r, m)	수행
(0, 0)	● 해당 페이지를 교체 ● 포인터를 시계 방향으로 한 단계 진행 후 선정 과정 종료
(0, 1)	● (0, 0)으로 설정 ● 해당 페이지를 소거 대상 리스트에 추가 ● 포인터를 시계 방향으로 한 단계 진행 후 단계① 반복
(1, 0)	● (0, 0)으로 설정 ● 포인터를 시계 방향으로 한 단계 진행 후 단계① 반복
(1, 1)	● (0, 1)로 설정 ● 포인터를 시계 방향으로 한 단계 진행 후 단계① 반복

페이지 프레임이 4개이고 각 페이지 프레임에 a, b, c, d가 적재되어 있을 때, 다음 참조 스트링을 처리하는 동안 페이지 부재가 몇 회 발생하는지 분석하라. 참조비트는 모두 1로 설정되어 있다. (→:포인터 위치, 지수w: 갱신 형태의 페이지)

참조스트링 = c  d  e b  b c d

시간	0	1	2	3	4	5	6	7	8	9	10
참조 스트링		c		d		e	b		b	c	d
프레임0/참조비트		→a/10	→a/11	→a/11	→a/11	a/00	a/00	a/11	a/11	→a/11	a/00
프레임1		b/10	b/10	b/10	b/11	b/00	b/10	b/10	b/10	b/10	d/10
프레임2		c/10	c/10	c/10	c/10	e/10	e/10	e/10	e/10	e/10	→e/10
프레임3		d/10	d/10	d/10	d/10	→d/00	→d/00	→d/00	→d/00	c/10	c/00
페이지 부재 발생		X	X	X	X	O (c→e)	X	X	X	O (d→c)	O (b→d)

참조 교재 :『컴퓨터 운영체제론』, 생능출판사

참조 영상 : (Youtube) Ghadeer Alhasan, 『 Clock replacement algorithm 』