클럭 알고리즘: 두 판 사이의 차이
IT 위키
(새 문서: 클럭 알고리즘(Clock algorithm)은 페이지 교체 알고리즘 중 하나로, LRU(Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다. ==개념== 클럭 알고리즘은 각 페이지마다 1비...) |
편집 요약 없음 |
||
| 1번째 줄: | 1번째 줄: | ||
클럭 알고리즘(Clock algorithm)은 [[페이지 교체 알고리즘]] 중 하나로, [[LRU]](Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다. | 클럭 알고리즘(Clock algorithm)은 [[페이지 교체 알고리즘]] 중 하나로, [[LRU]](Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다. | ||
==개념== | ==개념 == | ||
클럭 알고리즘은 각 페이지마다 1비트의 '''참조 비트(reference bit)'''를 유지한다. 이 비트는 페이지가 참조될 때마다 1로 설정되며, 페이지 교체가 필요할 때 이를 기준으로 교체 대상을 판단한다. | 클럭 알고리즘은 각 페이지마다 1비트의 '''참조 비트(reference bit)'''를 유지한다. 이 비트는 페이지가 참조될 때마다 1로 설정되며, 페이지 교체가 필요할 때 이를 기준으로 교체 대상을 판단한다. | ||
==동작 방식== | ==동작 방식 == | ||
1. 각 페이지 프레임은 원형 큐로 연결되고, 참조 비트와 함께 관리됨 2. 페이지 폴트가 발생하면, "초침"이 가리키는 페이지부터 확인 3. 참조 비트가 0이면 → 해당 페이지를 교체 4. 참조 비트가 1이면 → 0으로 초기화하고 다음 페이지로 이동 5. 교체 대상이 결정될 때까지 반복 | 1. 각 페이지 프레임은 원형 큐로 연결되고, 참조 비트와 함께 관리됨 | ||
2. 페이지 폴트가 발생하면, "초침"이 가리키는 페이지부터 확인 | |||
3. 참조 비트가 0이면 → 해당 페이지를 교체 | |||
4. 참조 비트가 1이면 → 0으로 초기화하고 다음 페이지로 이동 | |||
5. 교체 대상이 결정될 때까지 반복 | |||
==예시== | ==예시== | ||
페이지 프레임 수: 4 프레임 상태: [A<sup>1</sup>, B<sup>1</sup>, C<sup>0</sup>, D<sup>1</sup>] → C의 참조 비트가 0이므로 C가 교체 대상이 됨 | 페이지 프레임 수: 4 프레임 상태: [A<sup>1</sup>, B<sup>1</sup>, C<sup>0</sup>, D<sup>1</sup>] → C의 참조 비트가 0이므로 C가 교체 대상이 됨 | ||
==개선형: Second-Chance 알고리즘== | ==개선형: [[2차 기회 알고리즘|Second-Chance 알고리즘]]== | ||
*FIFO 기반 교체 대상에서 참조 비트가 1이면 제거하지 않고 기회를 한 번 더 줌 | *FIFO 기반 교체 대상에서 참조 비트가 1이면 제거하지 않고 기회를 한 번 더 줌 | ||
*클럭 알고리즘은 Second-Chance를 순환 큐로 구현한 형태 | *클럭 알고리즘은 Second-Chance를 순환 큐로 구현한 형태 | ||
| 16번째 줄: | 24번째 줄: | ||
*정확한 LRU가 아니므로 참조 순서를 완전히 반영하지는 못함 | *정확한 LRU가 아니므로 참조 순서를 완전히 반영하지는 못함 | ||
*페이지 수가 많을 경우, 교체 대상 탐색에 시간이 걸릴 수 있음 | *페이지 수가 많을 경우, 교체 대상 탐색에 시간이 걸릴 수 있음 | ||
==실제 활용== | == 실제 활용== | ||
*UNIX 계열 운영체제의 페이지 교체 구현 | *UNIX 계열 운영체제의 페이지 교체 구현 | ||
*Linux의 기본 페이지 교체 알고리즘 중 하나 | *Linux의 기본 페이지 교체 알고리즘 중 하나 | ||
| 27번째 줄: | 35번째 줄: | ||
*[[참조 비트]] | *[[참조 비트]] | ||
*[[가상 메모리]] | *[[가상 메모리]] | ||
==참고 문헌== | == 참고 문헌== | ||
*Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley | *Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley | ||
*Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson | *Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson | ||
2025년 4월 4일 (금) 02:22 기준 최신판
클럭 알고리즘(Clock algorithm)은 페이지 교체 알고리즘 중 하나로, LRU(Least Recently Used) 알고리즘을 근사화한 방식이다. 하드웨어적으로 효율적인 구현이 가능하며, 운영체제에서 널리 사용된다. 원형 큐 형태의 구조를 사용해 마치 시계의 초침처럼 순환하며 페이지를 검사한다는 의미에서 "클럭"이라는 이름이 붙었다.
1 개념[편집 | 원본 편집]
클럭 알고리즘은 각 페이지마다 1비트의 참조 비트(reference bit)를 유지한다. 이 비트는 페이지가 참조될 때마다 1로 설정되며, 페이지 교체가 필요할 때 이를 기준으로 교체 대상을 판단한다.
2 동작 방식[편집 | 원본 편집]
1. 각 페이지 프레임은 원형 큐로 연결되고, 참조 비트와 함께 관리됨
2. 페이지 폴트가 발생하면, "초침"이 가리키는 페이지부터 확인
3. 참조 비트가 0이면 → 해당 페이지를 교체
4. 참조 비트가 1이면 → 0으로 초기화하고 다음 페이지로 이동
5. 교체 대상이 결정될 때까지 반복
3 예시[편집 | 원본 편집]
페이지 프레임 수: 4 프레임 상태: [A1, B1, C0, D1] → C의 참조 비트가 0이므로 C가 교체 대상이 됨
4 개선형: Second-Chance 알고리즘[편집 | 원본 편집]
- FIFO 기반 교체 대상에서 참조 비트가 1이면 제거하지 않고 기회를 한 번 더 줌
- 클럭 알고리즘은 Second-Chance를 순환 큐로 구현한 형태
5 장점[편집 | 원본 편집]
- LRU와 유사한 효과를 하드웨어 없이 구현 가능
- 간단한 구조, 낮은 오버헤드
- 실제 시스템에서 많이 사용됨 (예: Linux)
6 단점[편집 | 원본 편집]
- 정확한 LRU가 아니므로 참조 순서를 완전히 반영하지는 못함
- 페이지 수가 많을 경우, 교체 대상 탐색에 시간이 걸릴 수 있음
7 실제 활용[편집 | 원본 편집]
- UNIX 계열 운영체제의 페이지 교체 구현
- Linux의 기본 페이지 교체 알고리즘 중 하나
- 일부 시스템은 클럭 + Aging 알고리즘 혼합 사용
8 같이 보기[편집 | 원본 편집]
9 참고 문헌[편집 | 원본 편집]
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson
- Linux Kernel Documentation - Page Replacement Algorithms
