혼공컴운

[혼공컴운] 14장. 가상 메모리

게으른 the lazy 2024. 8. 2. 22:41

https://www.computerscience.gcse.guru/theory/virtual-memory

14. 가상 메모리

  • 지금까지 OS가 프로세스를 어떻게 관리하는지 열심히 배웠다.
  • 핵심은 OS가 프로세스에게 자원을 어떻게 잘 배분하는가였다.
  • 그런데 프로세스는 메모리에 올라간다.
  • 프로세스를 메모리에 올리는 것도 분명히 OS가 관리해야 할 사항이다.
  • 그 과정에서 가상 메모리의 개념이 자연스럽게 등장하게 된다.

14.1 연속 메모리 할당

  • 연속 메모리 할당(contiguous memory allocation)은 프로세스를 메모리에 올리는 가장 간단한 방법이다.
  • 가장 먼저 실행될 프로세스를 메모리에 올리고, 그 다음 실행될 프로세스를 바로 뒤에 올린다.
  • 다만, 인터넷을 찾아보면 연속 메모리 할당도 두 가지 방법으로 세분화된다.
  • 책에 있는 것과 같이 빈틈 없이 메모리가 채워지는 것을 variable-size allocation이라고 부른다.

출처: https://www.geeksforgeeks.org/difference-between-fixed-partitioning-and-variable-partitioning/

  • 이와 달리 고정된 크기의 블록에 프로세스가 올라갈 수도 있는데, 이것을 fixed-size allocation이라고 부른다.

출처: https://www.geeksforgeeks.org/difference-between-fixed-partitioning-and-variable-partitioning/

  • 오랜만에 메모리를 다시 책상으로 비유해보자.
  • 지금 내 책상에는 PC 본체도 있고, 모니터도 있고, 키보드/마우스, 연필꽂이, 아이패드, 책, 이면지 등이 있다.
  • 그런데 자세히 보니 책 중 일부는 당장 안 볼 것들이다.
  • 굳이 책상 위 공간을 차지하고 있을 필요가 있을까?
  • 당분한 안 볼 것이라면 책장으로 보내는 것이 좋을 것이다.
  • OS도 비슷한 일을 한다. 놀고 있는 프로세스를 보조기억장치로 보내버린다.
  • 이것을 스와핑(swapping)이라고 부른다.
  • 프로세스가 유배(...) 가는 보조기억장치의 영역을 스왑 영역(swap space)이라고 부른다.
  • 프로세스가 스왑 영역으로 가는 것을 스왑 아웃(swap out)이라고 부른다.
  • 반대로 프로세스가 다시 메모리로 올라오는 것을 스왑 인(swap in)이라고 부른다.
  • 나는 메인으로 쓰는 웹 브라우저가 파이어폭스이다.
  • 워낙 탭을 많이 띄워놓아서 메모리를 꽤 많이 차지하고 있다.
    • 탭을 얼마나 띄워놨는지는 부끄러워서 말 못한다.
    • 그래도 요즘은 100개는 안 넘는다.
    • 한때는... (말잇못)
  • 그런데 종종 파이어폭스가 점유하는 메모리가 확 줄어드는 현상을 목격할 때가 있다.
  • 신기하다고 생각했는데, 어쩌면 스왑 인이 발생한 것일수도 있겠다는 생각이 든다.
  • 메모리의 비어 있는 공간에 프로세스를 올리는 방법에는 대표적인 3가지가 있다.
  • 최초 적합(first fit)
    • OS가 메모리 빈 공간을 검색하다가 공간이 보이면 바로 프로세스를 올린다.
    • 빠른 메모리 할당이 가능하다.
  • 최적 적합(best fit)
    • OS가 메모리의 빈 공간을 모두 검색한 후, 프로세스가 올라갈 수 있는 가장 작은 공간에 올린다.
    • 공간 낭비가 적고, 후술할 외부 단편화를 최소화하는 방식이다.
  • 최악 적합(worst fit)
    • OS가 메모리의 빈 공간을 모두 검색한 후, 프로세스가 올라갈 수 있는 가장 큰 공간에 올린다.
    • 남는 공간을 최대한 크게 만들겠다는 전략이다.
  • 그런데 바로 여기서 문제가 발생한다.
  • 프로세스가 메모리에 연속 할당된 상태에서 일부 프로세스가 스왑 아웃 됐다.
  • 그리고 새로운 프로세스를 다시 메모리에 올린다.
  • 큰 공간이 필요한 프로세스를 올리려는데, 연속된 메모리 공간이 준비되어 있다는 보장이 없다.
  • 이것을 외부 단편화(external fragmentation)라고 부른다.

출처: https://velog.io/@tjdtn0219/운영체제메모리-Segmentation과-Paging-기법-feat.-Fragmentation

14.1.1 확인 문제

  • 메모리 할당 방식에 대한 설명으로 올바른 것을 쓰시오.
    • 최초로 발견한 적재 가능한 빈 공간에 프로세스 배치
      • 최초 적합(first fit)
    • 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스 배치
      • 최악 적합(worst fit)
    • 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스 배치
      • 최적 적합(best fit)

14.2 페이징을 통한 가상 메모리 관리

  • 외부 단편화는 분명히 문제가 되므로 해결해야 한다.
  • 그 기법 중 하나가 가상 메모리를 이용하는 것이다.
  • 우선 가상 메모리(virtual memory)가 무엇인지부터 알아보자.
  • 메모리는 보조기억장치보다 작다. 책상이 책장보다 작은 것처럼.
  • 개인 PC의 메모리는 좀 크면 64 GB, 좀 많이 커도 128 GB 정도이다.
  • 요즘 보조기억장치는 TB 단위이다.
  • 그렇다면 메모리보다 큰 공간이 필요한 프로세스는 절대 못 돌리는 걸까?
  • 안될리가 있나.
  • 프로세스를 쪼개서 당장 필요한 부분만 메모리에 올리면 된다.
  • 나머지는? 보조기억장치에 그대로 둔다.
  • 이것을 가상 메모리라고 부른다. 메모리는 아니지만 메모리처럼 사용하기 때문이다.
  • 가상 메모리 구현에 필요한 것이 페이징이다.

14.2.1 페이징

  • 아이디어는 간단(?)하다. 메모리와 프로세스를 일정한 단위로 자른다.
  • 예를 들어 메모리와 프로세스를 모두 10 MB 단위로 자른다.
  • 그리고 각 프로세스 조각을 메모리에 올린다.
  • 불연속 할당의 문제가 있기는 하지만 어쨌든 프로세스는 올릴 수 있다.
  • 이때 프로세스의 논리 주소 공간을 페이지(page)라고 부르고, 메모리의 물리 주소 공간을 프레임(frame)이라고 부른다.

출처: https://byjus.com/gate/paging-in-operating-system-notes/

  • 이제 스왑 인/스왑 아웃은 프로세스 단위가 아니라 페이지 단위로 이루어진다.
  • 이것을 페이지 인/페이지 아웃이라고 부른다.

출처: https://scoutapm.com/blog/understanding-page-faults-and-memory-swap-in-outs-when-should-you-worry

  • 내가 쓰는 파이어폭스의 프로세스도 분명히 페이지 단위로 분할되어 있을 것이다.
  • 그래서인지 파이어폭스가 쓰는 메모리 양이 꽤 작은 단위로 바뀐다.

14.2.2 페이지 테이블

  • 그런데 CPU 입장에서는 좋은 상황이 아니다.
  • 실행할 프로세스가 메모리 상에 불연속적으로 퍼져 있기 때문이다.
  • 그래서 어떤 표를 하나 만들고, 페이지 번호와 프레임 번호를 나란히 적어둔다.
  • 이 표의 이름을 페이지 테이블(page table)이라고 부른다.
  • 이제 CPU는 페이지 테이블을 보고 각 프로세스의 정보를 순차적으로 가져올 수 있게 된다.

출처: https://velog.io/@jieuni/Paging-and-Page-Tables

  • 이 과정에서 내부 단편화(internal fragmentation)가 일어날 수 있다.
  • 외부 단편화가 프로세스 전체의 크기와 메모리 여유 공간의 불일치 때문에 생긴 것이라면,
  • 내부 단편화는 프로세스 크기와 프레임 크기의 불일치 때문에 발생한다.
  • 프로세스가 크기가 프레임 크기의 정수배가 아니라면 약간의 공간 낭비가 발생한다.
  • 하지만 이를 방지하기 위해 프레임을 너무 잘게 쪼개면 페이지 테이블이 커지는 단점이 있다.
  • 따라서 내부 단편화는 어느 정도 허용하더라도 적절한 프레임 크기를 설정하는 것이 필요하다.
  • 프로세스마다 자신의 페이지 테이블이 있다.
  • 페이지 테이블들은 메모리에 올라간다.
  • CPU 내의 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)에는 각 프로세스의 페이지 테이블이 올라간 주소가 저장된다.

출처: https://stackoverflow.com/questions/66180810/how-page-table-base-register-ptbr-is-used-to-locate-the-correct-frame-using-pa

  • 그런데 CPU 입장에서는 페이지 테이블이 메모리에 있는 것이 불만이다.
  • CPU 입장에서 메모리는 멀고 느리기 때문이다.
  • 그래서 CPU 근처 캐시 메모리에 페이지 테이블 일부를 저장한다.
    • 이 캐시는 일반적으로 MMU 내에 있다.
    • MMU는 6장에서 설명했다. (메모리 관리 유닛, Memory Management Unit)
  • TLB(Translation Lockaside Buffer)라고 부른다.
  • 이제 CPU는 TLB를 먼저 찾아보고, 있으면 가져다 쓰고, 없으면 메모리를 찾는다.
  • TLB에서 찾아지는 걸 TLB 히트, 안 찾아지는 걸 TLB 미스라고 부른다.
  • 사족으로, 윈도우에서 가상 메모리 크기를 확인 및 변경하는 방법은 이 글을 확인해보자.

14.3 페이지 교체와 프레임 할당

  • 앞에서 가상 메모리와 페이징에 대해서 간략하게 설명했다.
  • 이제 좀 더 구체적으로, OS가 어떻게 프로세스에 프레임을 할당하는지를 알아보자.

14.3.1 요구 페이징

  • 요구 페이징(demand paging): 프로세스를 메모리에 올릴 때 필요한 페이지만 올리는 기법
  • CPU 입장에서 프로세스를 실행하려면 아래와 같은 과정이 필요하다.
    • 프로세스 중 필요한 페이지에 접근을 시도한다.
    • 해당 페이지가 메모리에 없으면 페이지 폴트가 발생한다.
    • 페이지 폴트 처리 루틴이 해당 페이지를 메모리에 올린다.
    • CPU에게 준비됐음을 알린다.
  • 당연히 페이지 폴트가 적게 발생할 수록 좋다.
  • 기억할 것: 페이지 폴트가 발생하면 페이지를 아주아주 느린 보조기억장치에서 가져와야 한다!
  • 요구 페이징 방식이 효율적으로 동작하려면 페이지 교체와 프레임 할당에 대한 알고리즘이 필요하다.

14.3.2 페이지 교체 알고리즘

  • 페이지 참조열(page reference string): CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
  • 예를 들어 CPU가 아래의 순서로 페이지에 접근해야 한다고 가정하자.
  • 2 2 2 3 5 5 5 3 3 7
  • 연속된 페이지를 생략하면 아래와 같다.
  • 2 3 5 3 7
  • 이게 왜 필요하냐면, 연속된 페이지는 페이지 폴트를 발생시키지 않기 때문이다.
  • 이제 이 페이지 참조열을 기반으로 페이지 교체 알고리즘을 알아보자.
  • FIFO 페이지 교체 알고리즘 (FIFO = First-In First-Out)
  • 간단하다. 가장 먼저 올라온 페이지부터 내보내는 방식이다.
  • 예를 들어 프레임이 3개, 어떤 프로세스의 페이지가 5개라고 가정하자.
  • CPU는 아래 순서로 페이지를 가져오고 싶다.
  • 2 3 1 3 5 2 3 4 2 3
  • 먼저 앞의 3개를 채운다.

 

  • 3은 이미 올라와 있으므로 괜찮다.
  • 어어...? 5가 없다! 페이지 폴트 발생!
  • 맨 위에 있는 2를 쫓아내고 5를 데리고 온다.

 

  • 페이지 2를 봐야 하는데 또 없다! 페이지 폴트 발생!
  • 가장 오래된 3을 쫓아내고 2를 다시 데리고 온다.

 

  • 페이지 3를 봐야 하는데 또 없다! 페이지 폴트 발생!
  • 가장 오래된 1을 쫓아내고 3를 다시 데리고 온다.

 

  • 페이지 4를 봐야 하는데 또 없다! 페이지 폴트 발생!
  • 가장 오래된 5를 쫓아내고 4를 데리고 온다.

 

  • 다행히 2와 3은 이미 올라와 있으므로 페이지 폴트는 더 이상 발생하지 않는다.
  • 간단한 알고리즘은 그만큼 단점이 있기 마련이다. 오캄의 면도날은 통하지 않는다.
  • 가장 오래된 것이 가장 중요할 수도 있지 않은가?
  • 최적 페이지 교체 알고리즘 (optimal page replacement algorithm)
  • 앞으로 사용 빈도가 가장 낮을 페이지를 교체하는 것이다.
    • 표현에 조심해야 한다. 지금까지의 빈도가 낮은 것이 아니다. 앞으로 낮을 것이다.
  • 위와 동일한 예시에서 최적 페이지 교체 알고리즘을 적용하면 페이지 교체 흐름은 아래와 같다.

혼자 공부하는 컴퓨터 구조 + 운영체제

  • 이름에서 알 수 있듯 이론적으로 가장 낮은 페이지 폴트율을 보장한다.
  • 다만, 구현이 어렵다.
  • 또한 과거의 정보로 미래를 판단하는 것도 쉽지 않다. 당연히 보장되지도 않는다.
  • 따라서 다른 페이지 교체 알고리즘의 성능 평가용으로 쓰인다고 한다.
  • LRU 페이지 교체 알고리즘 (Least Recently Used page replacement algorithm)
  • 최적 페이지 교체 알고리즘의 문제점: 앞으로 어찌 될지 어케 아누?
  • 꼼수: 그럼 지금까지 정보를 이용하지 뭐!
  • 한 마디로, 가장 오랫동안 사용하지 않은 페이지를 교체하는 것이다.
  • 똑같은 예시를 들어보자.
2 3 1 3 5 2 3 4 2 3
  • 먼저 앞의 3개를 채운다.

 

  • 페이지 3까지는 문제없이 들어간다.
  • 페이지 5를 이용해야 한다? 현재 들어있는 1, 2, 3 중 가장 오래 안 쓴 것은? 페이지 2!
  • 2를 빼고 5로 교체한다.

 

  • 다시 페이지 2를 가져와야 한다.
  • 현재 들어있는 1, 3, 5 중 가장 오래 안 쓴 것은 1이다.
  • 1을 보내고 2를 데려온다.

 

  • 이 방식이 LRU 페이지 교체 알고리즘이다.

14.3.3 스래싱과 프레임 할당

  • 페이지 폴트는 나쁘다.
  • 그런데 그게 페이지 교체 알고리즘만의 잘못일까?
  • 애초에 프레임이 적은 것도 문제이지 않을까?
  • 이렇게 프로세스 실행 시간보다 페이징에 더 많은 시간을 쓰는 것을 스래싱(thrashing)이라고 부른다.
  • 우리는 CPU가 한 순간도 쉬지 않고 일을 했으면 좋겠다.
  • 하지만 프로세스가 너무 많으면 페이징 및 페이지 폴트 때문에 CPU가 노는 시간이 길어질 것이다.
  • 바로 아래 그래프처럼 말이다.

출처: https://truemind5.blogspot.com/2017/05/16-1.html

  • 그런데... 메모리 크기는 정해져 있는데, 그래서 뭐 어쩌라고? 싶을 수 있다.
  • 어쩌긴, 프레임을 잘 할당해야지. 그게 OS의 존재 이유이다.
  • 같은 양의 프레임이라도 프로세스마다 어떻게 할당할지에 따라서 성능은 달라질 수 있다.
  • 인생이란 그런 거다. 주어진 카드는 못 바꾸지만, 그 카드로 어떻게 플레이할지는 선택할 수 있다.
  • 몇 가지 방식이 있다.
  • 먼저 균등 할당(equal allocation)은 모든 프로세스에 같은 양의 프레임을 할당하는 것이다.
  • 당연히 좋은 방법이 아니다. 프로세스마다 크기가 다르기 때문이다.
  • 다른 방법은 비례 할당(proportional allocation)이다.
  • 프로세스 크기에 비례하여 프레임을 할당하는 것이다.
  • 비례 할당도 완벽하지는 않다.
  • 프로세스가 커서 프레임을 많이 줬는데, 특정 페이지만 많이 사용한다면 적은 프레임으로도 충분했을 수도 있다.
  • 그래서 아래의 두 가지가 나온다.
  • 작업 집합 모델(working set model)과 페이지 폴트 빈도(PFF; Page-Fault Frequency)이다.
  • 스래싱이 발생하는 이유는? 페이지 교체가 너무 잦기 때문이다.
  • 작업 집합 모델 기반 방식에서는 프로세스가 일정 시간동안 주로 참조한 페이지 수만큼 프레임을 할당한다.
  • 이 방식의 기반에는 참조 지역성 원리가 있다. (자주 쓰는 것은 자주 쓴다.)
    • 6장 캐시 메모리에서 설명했다.
  • 자세히 설명하려면 기니까, 이 페이지를 참고하도록 하자.
  • 다르게 생각해보자.
  • 페이지 폴트가 너무 잦다? 프로세스에게 프레임을 더 줘야 한다.
  • 페이지 폴트가 너무 없다? 프로세스에게서 프레임을 뺏어야 한다.
  • 모든 프로세스가 비슷한 정도로 페이지 폴트가 발생하는 것이 좋을 것이다.
  • 따라서 페이지 폴트율을 기준으로 프레임을 뺏고 주고 하는 방식이다.

14.3.4 확인 문제

  • 프로세스가 사용할 수 있는 프레임 3개
  • 페이지 참조열은 아래와 같음
  • 2 3 1 3 5 2 3 4 2 3
  • LRU 페이지 교체 알고리즘을 적용한다면 페이지 폴트가 몇 번 일어나는가?
  • 우선 참조열의 4개까지는 페이지 폴트가 일어나지 않는다.

 

  • 5를 넣기 위해, 가장 쓴지 오래된 2를 교체한다.

 

  • 2를 넣기 위해, 가장 쓴지 오래된 1을 교체한다.

 

  • 3은 이미 있으므로 패스. 4를 넣기 위해 가장 쓴지 오래된 5를 교체한다.

 

  • 그 뒤 페이지인 2와 3은 이미 있으므로 패스.
  • 총 3회의 페이지 폴트가 발생한다.
저작자표시 비영리 변경금지