ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SW 정글 85일차] Page Replacement Algorithm
    기타/SW 사관학교 정글 2021. 10. 27. 01:27

    오늘은 page replacement algorithm에 대해 공부를 했다.

    memory mapped files의 다음 과제인 swap in/ swap out에서는 메모리가 모두 차지된 경우에 새로운 페이지가 메모리에 swap in되기 위해서는 현재 메모리에 매핑된 page들 중에 victim page를 선택하여 swap out을 해야한다.

    여기서 어떠한 victim page를 선택하냐에 따라 추후에 page fault횟수를 줄일 수도 있다.

    page fault 과정을 보면 I/O작업이 필요하기에 더 많이 날수록 많은 비용이 들고 시스템적으로 좋지는 않다.

    그래서 좋은 page replacement algorithm을 사용하여 page fault가 최대한 적게 나오게 해주는 것이 좋다.

    그러면 지금부터 오늘 공부한 내용을 바탕으로 정리를 시작하자.

     

     

     

    1. Optimal Algorithm

    Optimal Algorithm은 앞으로 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다.

    앞으로라는 말이 붙었다는 것은 미래를 모두 안다는 것인데 실제로 시스템에 적용하는 것은 불가능한 알고리즘이다.

    그러면 왜 정의를 해놓은 것일까?

    실제로는 사용되지는 않지만 다른 page replacement algorithm의 성능에 대한 upper bound를 제공하여 연구 목적을 위해 주로 사용된다.

    즉, 아무리 성능이 좋은 알고리즘이 나와도 optimal algorithm보다 성능이 좋을 수 없다는 것이다.

    여기서 성능이 좋은 알고리즘이라는 것은 page fault 횟수가 적게 발생하는 것을 말한다.

    출차: https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

    위 예시 그림은 optimal algorithm을 적용했을 때 어떻게 page가 replace되는지를 보여준다.

    1 2 3 4까지는 page fault가 발생하고 1 2는 메모리에 존재하므로 hit되고 5번이 들어오고자 할 때 메모리가 꽉 찬 상태이므로 victim page를 swap out해주어야한다.

    optimal algorithm에 의하면 1, 2, 3, 4 중 4번이 가장 늦게 참조되므로 4번 페이지가 swap out된다.

    그러면 위 예시에서는 총 6번의 page fault가 발생하고 아무리 좋은 알고리즘을 가져와도 6번의 page fault보다 적게 일어날 수는 없다.

     

     

     

     

    2. FIFO(First In First Out) Algorithm 

    FIFO 알고리즘은 실제로 시스템에 적용할 수 있는 알고리즘으로 메모리에 올라온 지 가장 오래된 페이지를 교체하는 알고리즘이다.

    쉽게 얘기하면 메모리에 있는 프레임 중에 가장 먼저 들어왔던 프레임을 victim으로 지정하여 swap out시켜주는 것이다.

    이 알고리즘을 구현하기 위해 각 페이지가 올라온 시간을 페이지에 기록하거나 페이지가 올라온 순서를 큐에 저장하는 방식 등을 사용할 수 있다.

     

    출차: https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

    위 예시그림은 FIFO algorithm을 적용한 것으로 1 2 3 까지는 page fault가 일어나고 다음에 4가 들어올 때 victim page를 찾아야한다.

    FIFO algorithm에 의해 가장 먼저들어온 페이지는 1번이므로 1번이 빠지고 4번이 들어올 수 있게 된다.

    이렇게 하면 9번의 page fault가 발생한다.

     

    FIFO algorithm은 구현이 간단하다는 장점이 있지만 성능이 언제나 좋다는 것을 장담할 수 없다.

    아래의 그림을 봐보자.

    출차: https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

    메모리의 frame 수가 늘었는데 page fault도 그 만큼 늘어났다.

    이를 FIFO Anomaly 혹은 Belady's Anomaly라고 하고 frame의 갯수가 늘어났지만 더 많은 page fault가 발생하는 것을 말한다.

     

    또 하나의 단점으로는 Locality를 고려하지 않은 FIFO의 한계로인해 page fault가 일어날 확률이 증가하고 이로 인해 성능 저하 및 스래싱이 발생한다.

    스래싱(thrasing)이란 메모리 영역에 접근할 때,페이지 부재(=페이지 폴트(Page fault)율이 높은 것을 의미하며, 심각한 성능 저하를 초래한다. 
    [https://jwprogramming.tistory.com/56]

     

     

     

     

    3. LRU(least-recently-used) Algorithm

    LRU Algorithm은 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘으로 Optimal algorithm의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이다.

    Optimal algorithm을 위에서 봤듯이 페이지가 미래에 언제 사용될 지를 미리 알아야한다.

    미리 안다는 것은 현실적으로 불가능하고 이를 대체하는 것은 과거를 보는 것이다.

    과거에 얼마나 오랫동안 사용안되었는지를 보고 이를 근거로 페이지를 교체하는 것이다.

     

    출차: https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

    위 예시 그림은 LRU algorithm을 적용한 것으로 초기 4개의 페이지 1 2 3 4는 page fault가 발생하고 이 후 1 2는 이미 메모리에 존재하므로 hit되고 5번이 들어올 때 LRU algorithm을 통해 victim을 정하여 swap out시킨다.

    가장 오래 사용되지 않은 페이지는 3번이 되므로 3번을 victim으로 지정하고 swap out시키고 5번을 swap in시킨다.

    이렇게 끝까지 가면 총 8번의 page fault가 발생하고 Optimal Algorithm보다는 성능이 좋지는 않지만 FIFO보다는 성능이 좋은 것을 볼 수 있다.

    LRU algorithm은 많은 운영체제가 채택하는 알고리즘이다.

     


    [오늘의 나는 어땠을까?]

    어제 memory mapped files 과제를 하면서 '이것만 끝내고 자자'라고 생각하며 시간이 꽤 지나서 3시쯤 잠에 들었다.

    그러고 오늘 기강확립 스터디를 위해 7시 30분에 눈을 떴고 8시 전에 강의실에 도착했다.

    알고리즘 문제를 풀 때까지는 컨디션이 괜찮았지만 알고리즘을 다 풀고 30분 정도 지나니 피곤함이 느껴졌다.

    그래도 정신을 잡고 HTTP 완벽 가이드 책을 읽으려고 했는데 계속 졸음이 쏟아져서 휴게실에서 30분정도 잠을 잤다.

    좀 괜찮아진 듯 했으나 점심을 먹고나서도 계속 피곤함이 유지됐다.

    거의 저녁 8시까지는 이 피곤함이 계속 느껴진 것같다.

     

    그래도 다행히 8시부터는 컨디션이 돌아와서 공부하는데 방해가 되는 졸음이 오지 않았다.

    아무래도 이제는 5시간 미만으로 자는 것은 나의 체력이 따르지 않는 것같다.

    정글에 들어오기 전에 꾸준히 했던 농구, 운동 덕분에 체력이 쌓여있는 상태여서 초반 2개월 반정도는 버틸만했다.

    하지만 지금은 무리이다...

    나의 상태를 파악하고 좋은 컨디션으로 공부를 하기위해 계획을 세우자.

    이제는 무리하게 잠을 줄인다고 효율적으로 공부할 수 있는 것은 아니다.

     

     


    <참고 자료>

    https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266

    댓글

Designed by Tistory.