페이지 교체 알고리즘에 대하여...

시작하기에 앞서,

오늘 내용 설명에 필요한 단어들 먼저 간단히 설명 하겠습니다.

 

---

 

중앙처리장치 (CPU : Center Processing Unit) :

  컴퓨터의 중심에서 모든 데이터 처리를 담당하며,

  컴퓨터의 두뇌 역할을 수행하는 장치입니다.

 

 

 

주기억장치 (Computer Memory, Primary Memory) :

  CPU 가 일하기 위해 쓰는 업무 공간입니다.

• ROM (Read Only Memory) :

        읽기 작업만 가능하며 비휘발성 메모리라

        전원이 꺼져도 데이터가 그대로 유지됩니다.

        부품 제조 단계에서 시스템에 입력하고,

        변화되면 안되는 데이터를 보관하는 장소입니다.

        예) BIOS 데이터.

• RAM (Random Access Memory) :

        읽기뿐만 아니라, 쓰기도 가능하며, 휘발성 메모리입니다.

        즉, 전원이 꺼지면 보관했던 데이터가 사라집니다.

        주로 응용프로그램, 운영체제 등을 불러와서

        CPU 가 작업하는 공간으로 쓰이며,

        수시로 작업중인 파일을 보조기억장치에 저장하고,

        해당 프로그램을 다시 실행하면,

        보조기억장치에 보관된 데이터를 다시 주기억장치로 불러와서

        CPU 가 데이터를 처리하게 됩니다.

 

 

보조기억장치 (Auxiliary Memory, Secondary Memory) :

  데이터를 영구적으로 보관하기 위한 장치이며,

  따라서 읽기만 가능하거나 (ROM),

  데이터가 보관됐다 휘발되는 (RAM) 주기억장치보다는 느립니다. 

 

• HDD (Hard Disk Drive) : 디스크가 고속회전하며 데이터를 저장하는 장치.
• SSD (Solid State Drive) : HDD 의 한계를 개선한 반도체 기반의 장치.

*Disc 와 Disk 의 차이 : 광학용 디스크 (음악, 동영상 에 쓰이는 CD) 는 Disc,

                                     자기용 디스크 (HDD 나 플로피 디스크) 는 Disk 라고 합니다. 

---

 

 

페이지 교체 알고리즘이란?

  페이지 교체 알고리즘은 페이지 부재 (Page Fault) 가 발생하면,

  가상기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데,

  이때 주기억장치의 모든 페이지 프레임이 사용중이면,

  "어떤 페이지 프레임을 선택하여 교체할 것인지를 결정하는 기법" 입니다.

 

    *페이지 부재란 CPU가 액세스한 가상페이지가

    주기억장치에 없는 경우를 말합니다.

    페이지 부재가 생기면 해당 페이지를

    보조기억장치에서 주기억장치로 가져와야 합니다.

 

페이지 교체 알고리즘의 종류.

  OPT, FIFO, LRU, LFU, NUR, SCR 등이 있습니다.

 

OPT (Optimal replacement : 최적 교체) :

  페이지가 교체되는 주기와 패턴을 분석하여

  앞으로 가장 사용되지 않을 것으로 추측되는 페이지를 교체하는 기법.

  이론상 페이지 부재가 가장 적게 발생하지만,

  미래를 예측해야 한다는 이유로 구현이 불가능합니다.

  (개인적인 생각은,

   빅데이터가 쌓이면 비슷한 방식의 알고리즘을 쓸 수 있을 것 같습니다.)

 

FIFO (First In First Out) :

  참 여기저기 많이 나오는 개념입니다.

  단어 그대로 '선입선출' 로써,

  주기억장치가 페이지가 저장된 시간을 기억해뒀다가,

  페이지 교체가 필요한 상황이 발생하면,

  가장 먼저 적재됐던 페이지를 교체하는 기법입니다. 

  

LRU (Least Recently Used) :

  가장 오랫동안 사용되지 않은 페이지를 교체하는 기법입니다.

  페이지마다 계수기 (Counter : 시간 재는 것) 혹은 스택을 두고,

  그것을 페이지가 참조될 때마다 초기화시킵니다.

  페이지 교체가 필요한 상황이 발생하면,

  각 페이지의 카운터나 스택이 가장 큰 페이지를 교체합니다.

 

    * 카운터 혹은 스택을 두는것 자체가

    시간이나 메모리 상의 오버헤드가 발생하기 때문에,

    이것이 LRU 알고리즘의 특징이며 단점입니다.

 

LFU (Least Frequently Used) :

  사용빈도가 가장 적은 페이지를 교체하는 기법입니다.

  얼핏 좋아보이지만,

  비율로써 빈도를 측정하는 것이 아닌,

  단순히 참조 횟수를 측정하기 때문에,

  초반에 참조가 많이된 페이지는,

  뒤로 가면서 참조가 되지 않아도

  메모리에 계속 남아있을 수 있다는 단점이 존재합니다.

 

NUR (Not Used Recently) :

  개념적으로 LRU 와 흡사한 알고리즘으로써,

  최근에 사용하지 않은 페이지를 교체하는 기법입니다.

 

  LRU 기법이 카운터를 사용하는 알고리즘이기 때문에

  오버헤드가 발생한다는 점을 보완하기 위해,

 

  NUR 은 카운터가 아닌 참조 비트와 변형 비트를 통해

  페이지의 참조 여부와 변경 여부를 확인한 뒤,

  두 비트의 값에 따라 교체 순서가 결정되는 기법입니다.

참조 비트 (Reference Bit) : 호출 여부 확인	0	0	1	1
변형 비트 (Modified Bit, Dirty Bit) : 페이지 내용 변경 여부 확인	0	1	0	1
교체 순서	1	2	3	4

 

 

SCR (Second Chance Replacement : 2차 기회 교체) :

  SCR 기법은 

  FIFO 를 기반해서 페이지를 교체하는데,

  각 페이지에 참조 비트를 둠으로써

  교체될 페이지의 참조 비트가 1이면 비트를 0으로 변경한 뒤

  큐의 마지막으로 보내서 2번째 기회를 주는 기법입니다.