페이지 교체 알고리즘: 두 판 사이의 차이

기술노트
(Gemini 벌크 업로더로 자동 업로드)
 
(Gemini 벌크 업로더로 자동 업로드)
 
1번째 줄: 1번째 줄:
== 🔄 페이지 교체 알고리즘 (FIFO, LRU, LFU 등) ==
== 페이지 교체 알고리즘 ==


'''페이지 교체 알고리즘'''은 운영체제(OS)의 가상 메모리 시스템에서 '''페이지 부재(Page Fault)'''가 발생했을 때, 즉 CPU가 참조하려는 페이지가 현재 물리 메모리(RAM)에 없을 때, '''물리 메모리에서 어떤 페이지를 스와프 영역(하드 디스크)으로 내보내고 새로운 페이지를 가져올지 결정하는''' 알고리즘입니다.
'''페이지 교체 알고리즘'''은 가상 메모리 시스템에서 페이지 폴트(Page Fault)가 발생하고, 물리 메모리(RAM)에 빈 프레임이 없을 때, 어떤 페이지를 디스크로 내보내고(Swap Out) 새로운 페이지를 가져올지(Swap In) 결정하는 전략입니다. 목표는 페이지 폴트 발생률을 최소화하여 시스템 성능을 최적화하는 것입니다.


이 알고리즘의 목표는 페이지 부재 발생 횟수를 최소화하여 시스템의 성능을 향상시키는 것입니다.
----
 
=== 🔄 페이지 교체 알고리즘의 필요성 ===
 
* '''페이지 폴트 (Page Fault)''' : CPU가 접근하려는 페이지가 현재 물리 메모리에 없는 경우 발생합니다. 페이지 폴트가 발생하면 디스크 I/O가 발생하며, 이는 매우 느린 작업이므로 시스템 성능에 큰 영향을 미칩니다.
* '''프레임 부족''' : 물리 메모리의 프레임이 모두 사용 중일 때, 새로운 페이지를 로드하려면 기존 페이지 중 하나를 디스크로 내보내야 합니다. 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘의 역할입니다.
* '''목표''' : 미래에 가장 오랫동안 사용되지 않을 페이지를 예측하여 교체함으로써, 페이지 폴트 발생률을 최소화하는 것입니다.


----
----


=== 📚 주요 페이지 교체 알고리즘 ===
=== ⚙️ 주요 페이지 교체 알고리즘 ===


* '''FIFO (First-In, First-Out)''' : '''가장 먼저 물리 메모리에 들어온 페이지를 먼저 내보내는''' 방식입니다. 큐(Queue) 자료구조를 사용합니다.
* '''FIFO (First-In, First-Out)'''
> * '''장점''': 구현이 가장 간단합니다.
> * '방식': 물리 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체합니다.
> * '''단점''': 가장 오래된 페이지가 항상 가장 적게 사용되는 것은 아니므로, 비효율적일 수 있습니다. '벨라디의 변이(Belady's Anomaly)' 현상이 발생할 수 있습니다.
> * '장점': 구현이 간단합니다.
> * '단점': '''Belady의 모순(Belady's Anomaly)''' 발생 가능. 페이지 프레임 수를 늘려도 페이지 폴트 수가 오히려 증가하는 현상입니다. 또한, 자주 사용되는 페이지가 일찍 들어왔다는 이유로 교체될 수 있어 비효율적입니다.


* '''LRU (Least Recently Used)''' : '''가장 오랫동안 사용되지 않은 페이지를 내보내는''' 방식입니다. 최근에 사용된 페이지는 미래에도 사용될 가능성이 높다는 '지역성(Locality)' 원리에 기반합니다.
* '''LRU (Least Recently Used)'''
> * '''장점''': FIFO보다 효율적이며, 실제 시스템에서 많이 사용됩니다.
> * '방식': 가장 오랫동안 사용되지 않은(참조되지 않은) 페이지를 교체합니다. '시간 지역성(Temporal Locality)'을 활용합니다.
> * '''단점''': 각 페이지의 사용 시점을 기록해야 하므로 구현이 복잡하고 오버헤드가 발생합니다.
> * '장점': FIFO보다 효율적이며, Belady의 모순이 발생하지 않습니다.
> * '단점': 구현이 복잡하고 오버헤드가 큽니다. 각 페이지의 사용 시간을 기록하거나, 연결 리스트로 관리해야 하므로 추가적인 하드웨어 지원이 필요할 수 있습니다.


* '''LFU (Least Frequently Used)''' : '''가장 적게 사용된(참조된) 페이지를 내보내는''' 방식입니다. 사용 횟수를 카운트하여 관리합니다.
* '''LFU (Least Frequently Used)'''
> * '''장점''': LRU보다 더 정확하게 페이지의 사용 빈도를 반영합니다.
> * '방식': 참조 횟수가 가장 적은(가장 적게 사용된) 페이지를 교체합니다.
> * '''단점''': 사용 횟수를 계속 기록해야 하므로 구현이 복잡하고 오버헤드가 큽니다. 초기에 많이 사용되고 나중에 사용되지 않는 페이지가 계속 남아있을 수 있습니다.
> * '장점': 자주 사용되는 페이지는 계속 메모리에 유지됩니다.
> * '단점': 구현이 복잡하고 오버헤드가 큽니다. 한 번 많이 사용되고 더 이상 사용되지 않는 페이지가 메모리에 오래 남아있을 수 있습니다.


* '''OPT (Optimal Replacement)''' : '''가장 먼 미래에 사용될 페이지를 내보내는''' 방식입니다. 가장 이상적인(최적의) 알고리즘이지만, 미래를 예측해야 하므로 실제 구현은 불가능합니다. 다른 알고리즘의 성능을 평가하는 기준으로 사용됩니다.
* '''OPT (Optimal Page Replacement)'''
> * '방식': 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. (미래를 예측)
> * '장점': 이론적으로 가장 낮은 페이지 폴트율을 보장하는 최적의 알고리즘입니다.
> * '단점': 미래를 예측해야 하므로 실제 시스템에서는 구현 불가능합니다. 다른 알고리즘의 성능을 평가하는 기준(benchmark)으로 사용됩니다.


----
----


=== 💡 정보처리기사 핵심 Point ===
=== 💡 개발자 핵심 Point ===


* 페이지 교체 알고리즘은 가상 메모리 시스템의 '''성능에 직접적인 영향'''을 미칩니다.
* 페이지 교체 알고리즘은 가상 메모리 시스템의 성능에 직접적인 영향을 미칩니다.
* 정보처리기사 시험에서는 각 알고리즘의 '''개념, 동작 방식, 장단점, 그리고 특정 페이지 참조열에 대한 페이지 부재 횟수 계산''' 문제가 자주 출제됩니다.
* '''LRU의 근사 알고리즘''' : LRU는 이론적으로 효율적이지만 구현 비용이 높아, 실제 운영체제에서는 LRU의 아이디어를 근사하여 구현한 알고리즘들을 사용합니다. (e.g., Clock Algorithm, Second Chance Algorithm)
* 특히 FIFO, LRU, LFU는 반드시 정확히 이해하고 계산할 수 있어야 합니다.
* '''작업 세트 (Working Set)''' : 프로세스가 일정 시간 동안 집중적으로 참조하는 페이지들의 집합. 운영체제는 각 프로세스의 작업 세트를 물리 메모리에 유지하려고 노력하여 스래싱(Thrashing)을 방지합니다.
* 개발자는 직접 페이지 교체 알고리즘을 구현할 일은 거의 없지만, 어떤 알고리즘이 어떤 상황에 유리하고 불리한지 이해하는 것은 메모리 관련 성능 문제를 진단하고 해결하는 데 도움이 됩니다.

2025년 9월 11일 (목) 16:50 기준 최신판

페이지 교체 알고리즘

페이지 교체 알고리즘은 가상 메모리 시스템에서 페이지 폴트(Page Fault)가 발생하고, 물리 메모리(RAM)에 빈 프레임이 없을 때, 어떤 페이지를 디스크로 내보내고(Swap Out) 새로운 페이지를 가져올지(Swap In) 결정하는 전략입니다. 목표는 페이지 폴트 발생률을 최소화하여 시스템 성능을 최적화하는 것입니다.

🔄 페이지 교체 알고리즘의 필요성

  • 페이지 폴트 (Page Fault) : CPU가 접근하려는 페이지가 현재 물리 메모리에 없는 경우 발생합니다. 페이지 폴트가 발생하면 디스크 I/O가 발생하며, 이는 매우 느린 작업이므로 시스템 성능에 큰 영향을 미칩니다.
  • 프레임 부족 : 물리 메모리의 프레임이 모두 사용 중일 때, 새로운 페이지를 로드하려면 기존 페이지 중 하나를 디스크로 내보내야 합니다. 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘의 역할입니다.
  • 목표 : 미래에 가장 오랫동안 사용되지 않을 페이지를 예측하여 교체함으로써, 페이지 폴트 발생률을 최소화하는 것입니다.

⚙️ 주요 페이지 교체 알고리즘

  • FIFO (First-In, First-Out)

> * '방식': 물리 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체합니다. > * '장점': 구현이 간단합니다. > * '단점': Belady의 모순(Belady's Anomaly) 발생 가능. 페이지 프레임 수를 늘려도 페이지 폴트 수가 오히려 증가하는 현상입니다. 또한, 자주 사용되는 페이지가 일찍 들어왔다는 이유로 교체될 수 있어 비효율적입니다.

  • LRU (Least Recently Used)

> * '방식': 가장 오랫동안 사용되지 않은(참조되지 않은) 페이지를 교체합니다. '시간 지역성(Temporal Locality)'을 활용합니다. > * '장점': FIFO보다 효율적이며, Belady의 모순이 발생하지 않습니다. > * '단점': 구현이 복잡하고 오버헤드가 큽니다. 각 페이지의 사용 시간을 기록하거나, 연결 리스트로 관리해야 하므로 추가적인 하드웨어 지원이 필요할 수 있습니다.

  • LFU (Least Frequently Used)

> * '방식': 참조 횟수가 가장 적은(가장 적게 사용된) 페이지를 교체합니다. > * '장점': 자주 사용되는 페이지는 계속 메모리에 유지됩니다. > * '단점': 구현이 복잡하고 오버헤드가 큽니다. 한 번 많이 사용되고 더 이상 사용되지 않는 페이지가 메모리에 오래 남아있을 수 있습니다.

  • OPT (Optimal Page Replacement)

> * '방식': 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. (미래를 예측) > * '장점': 이론적으로 가장 낮은 페이지 폴트율을 보장하는 최적의 알고리즘입니다. > * '단점': 미래를 예측해야 하므로 실제 시스템에서는 구현 불가능합니다. 다른 알고리즘의 성능을 평가하는 기준(benchmark)으로 사용됩니다.

💡 개발자 핵심 Point

  • 페이지 교체 알고리즘은 가상 메모리 시스템의 성능에 직접적인 영향을 미칩니다.
  • LRU의 근사 알고리즘 : LRU는 이론적으로 효율적이지만 구현 비용이 높아, 실제 운영체제에서는 LRU의 아이디어를 근사하여 구현한 알고리즘들을 사용합니다. (e.g., Clock Algorithm, Second Chance Algorithm)
  • 작업 세트 (Working Set) : 프로세스가 일정 시간 동안 집중적으로 참조하는 페이지들의 집합. 운영체제는 각 프로세스의 작업 세트를 물리 메모리에 유지하려고 노력하여 스래싱(Thrashing)을 방지합니다.
  • 개발자는 직접 페이지 교체 알고리즘을 구현할 일은 거의 없지만, 어떤 알고리즘이 어떤 상황에 유리하고 불리한지 이해하는 것은 메모리 관련 성능 문제를 진단하고 해결하는 데 도움이 됩니다.
원본 주소 "https://technote.wiki/index.php?title=페이지_교체_알고리즘&oldid=1091"