Second Page Algorithm

#####. 페이지 교체 알고리즘

###. 페이지 교체 알고리즘

#. 최적의 성과를 얻기 위해서는 페이지 프레임에 있는 페이지 중 이후로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택하면 되는데 이를 '최적화 원칙 (principle of optimality)'라고 한다.

 

#. 최적화 원칙

 - 다른 페이지 교체기법이얼마나 최적성을 갖고 있는지 비교하는데 사용

 - 좋은 결과를 내리면서 교체 대상을 선택하기 위한 시간, 공간의 오버헤드가 적은 방법을 선택해야함

 - 효율 좋은 페이지는 교체하지 않게한다.

 - 효율 좋은 페이지

 : 페이징을 위한 코드영역

 : 커널에 속하지 못한 보조기억장치 드라이버 영역

 : 시간을 맞춰 동작해야하는 코드영역

 : DMA등에 의해 입출력장치로부터 직접 데이터가 교환되어야하는 버퍼 영역

 

#. FIFO 페이지 교체

 - First-In First-Out 페이지 알고리즘은 메모리 내에 가장 오래 있었던 페이지를 교체 대상으로 선택하여 교체

 - 큐를 이용

 - 타당해 보이지만 실제로 메모리에 가장 오래 있었던 페이지는 앞으로도 사용될 가능성이 높기 떄문에 효율 좋은 페이지를 교체할 가능성이 있다.

 

#. LRU 페이지 교체

 - Least Recently Used 페이지 교체 알고리즘은 메모리 내에서 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하여 교체

 - 최근 상황이 가까운 미래에 대한 좋은 척도라는 국부성 휴리스틱에 의존하는 것

 - 국부성(locality)이란 프로세스는 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라 어느 한순간에 특정 부분을 집중적으로 참조한다는 것

 - 시간 국부성 / 공간 국부성

 : 시간국부성 : 처음에 참조된 기억장소가 가까운 미래에도 참조될 가능성이 높다는 것을 의미

 : 공간국부성 : 일단 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조 될 수 있음을 의미

 

 - LRU 페이지 교체의 2가지 방법

 : 참조시간을 이용하는 방법 : 참조 될 때마다 시간을 테이블에 기록하고 시간이 오래 된 것을 교체 대상으로 선택

 : 리스트를 이용하는 방법 : 메모리에 적재된 페이지 번호를 저장하는 리스트를 이용해 페이지를 액세스하면 해당 페이지 번호를 리스트 선두에 옮기고, 후두에 리스트를 교체 대상으로 선택

 

 - LRU기법은 Belady의 이상현상이 발생하지 않고 많은 경우 최적화 원칙에 근사한 선택을 할 수 있다. 하지만 경험적 판단이 맞지 않는 상황도 존재 가능

 - Belady 이상현상 : Belady's anomaly(벨라디의 이상현상)은 페이지 교체 알고리즘의 동작에 따라 페이지 부재(Page fault)가 더 많이 발생할 수 있는 현상

 

 - 단점 : 하나의프로세스가 여러 페이지로 구성되는 커다란 루프를 가지고 있을 떄는 가장 오랫동안 사용되지 않은 페이지가 바로 가까운 장레에 사용될 페이지가 되어 즉시 다시 메모리로 호출한다. 매번 시간을 기록하고 오래된 참조시간을 찾거나 리스트를 유지하는 것은 모두 구현상 오버헤드가 크다.

 

 

#. LFU 페이지 교체

 - Least Frequently Used 페이지 교체는 LRU기법과 비슷하게 시간이 아닌 빈도로 페이지 교체하는 알고리즘이다.

 - 단점 : 가장 드물게 사용하던 페이지가 최근 메모리로 옮겨진 페이지일 경우 자주 사용하는 페이지가 다시 호출된다. 마찬가지로 오버헤드가 크다.

 

#. 2차 기회 페이지 교체

 - second chane 페이지 교체 알고리즘은 FIFO 페이지 교체를 보완한 기법으로 2번의 기회를 준다는 의미

041424342404142434

 

 - 이거 이해하는데 2시간 걸렸다...

 - 위에 놈이 한거 틀렸다... 하...정말 사경을 헤맷다.. 위엣놈 때문에...

 - 방통대 공부하다가 이게 왠 날벼락인지..ㅋㅋ 근데 재밋었음..ㅋㅋㅋㅋ

 - 하.. 시X 위엣놈 새객기...

 - 먼저 FIFO라는 관점에서 시작하고 초기화라는 말이 가장 관건이다...

 - 필자가 이렇게까지 그려놨으니 이해해보길 바란다.

 

 - ps. chat GPT 새객기...

 - 이 놈 때문에도 겁나게 헤맷네..

 - 후.. 나의 가장 큰 무기는 끝까지 포기하지 않는다는 것

 - 2차 기회 페이지 교체에서 큐를 변형된 원형 큐로 관리하는 경우를 특별히 클럭 페이지 교체 알고리즘 이라고 한다.

 

#. 클럭 페이지 알고리즘

 - 설명안해도 바로 이해가 되지만 설명하자면

 - 원형 시계(클락 틱톡 : clock) 모양으로 1이면 건너뛰고 0을 바꾸고 다음 주소를 가리킨다.

 

###. 프로세스별 페이지 집합관리

#. 각프로세스가 사용할 수 있는 페이지 프레임의 개수를 제한할 필요가 있는데, 이 개수 또한 컴퓨터 시스템의 성능에 영향을 준다. 프로세스마다 사용할 수있는 페이지 프레임의 개수만큼 페이지들을 메모리에 유지할 수 있고 이를 프로세스별 페이지 집합이라고 두면, 집합의 크기가 작을수록 메모리에 적재할 수 있는 프로세스의 수는 많아져서 시스템 처리량이 증대될 수 있다. 대신 각 프로세스별 페이지 부재는 자주 발생할 수 있어 성능이 저하될수 있다. 반면, 페이지 집합의 크기가 클수록 메모리에 적재될 수 잇는 프로세스 수는 줄어들지만 프로세스별 페이지 부재는 덜 발생할 것

#. 이러한 성질에 기반하여 페이지 집합 관리하는 알고리즘 워킹세트, PFF 알고리즘 이 있다.

 

#. 워킹세트 알고리즘

 - working set는 한 프로세스가 최근에 참조한 페이지 집합

 - 페이지 부재비율을 감소 시키기 위해 데닝(Denning)이 제안한 모델

 - 프로세스의 워킹세트는 진행된 시각을 포함한 진행 직전의 시간동안 참조한 페이지의 집합을 의미

 - 프로세스가 수행됨에 따라 페이지가 삭제되기도하고 추가되기도하며, 변함없이 유지되기도 한다. 또한 위도우 크기가 고정되어 있떠라도 워킹 세트의 크기는 달라질 수 있다.

 - 단점 : 하나의 프로세스가 효퓰적으로 수행되기 위해서는 그 프로세스의 워킹 세트가 메모리 내에 유지되어야 하며, 그렇지 않은 경우는 프로세스가 보조기억장치로부터 계속 페이지를 요구하게 되므로 쓰래싱이 유발된다.

 - 쓰래싱 (thrashing) : 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체처리에 너무 많은 시간을 소비함으로써 시스템의 처리량이 급격히 저하되는 현상

 

#. PFF 알고리즘

 - 페이지 교체가 자주 발생하면 프로세스별 페이지 집합이 너무 작다고 볼 수 있는 반면, 페이지 교체가 너무 발생하지 않는다면 프로세스별 페이지 집합이 너무 크다고 볼 수 있다. PFF(Page Fault Trequency) 페이지 부재 빈도를 이용하여 프로세스별 페이지 집합 크기를 변화시키는 기법

 - 페이지 부재 빈도는 얼마나 자주 페이지 부재로 교체가 발생하는지를 나타내는 척도

 - 페이지 부재 빈도의 상한과 하한을 정해두고 페이지 부재 빈도가 상한보다 높으면 페이지 프레임의 개수를 1증가 낮으면 하락 시켜 자동으로 프레임 개수를 조절해준다.