[운영체제] 가상 메모리, 페이징, 세그멘테이션, 페이지 교체 기법

메모리 관리 전략에서 얘기한 고정 분할을 처리하는 페이징과 가변 분할을 처리하는 세그멘테이션에 대해 알아보고 가상 메모리란 무엇인가를 알아보도록 하자.

가상 메모리(Virtual Memory)란?

보조기억장치(하드디스크)에 있는 프로그램은 주기억장치인(RAM)에 올라가야지 CPU에서 사용할 수 있게 된다. 그러나 메인 메모리의 크기가 한정되어 있으므로 물리적인 메모리 크기보다 크기가 큰 프로세스를 실행시킬 수 없다. 

예로 100MB 메인 메모리에서 200MB 크기의 프로세스를 실행할 수 없게 되는 것이다. 그렇다면 메인 메모리보다 크기가 큰 프로세스를 실행시키고 싶으면 어떻게 해야 할까? 그래서 나온 방법이 바로 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법인 가상 메모리이다.

 

페이징 (Paging)

페이지란? 주 메모리의 크기를 고정 분할한 크기를 말한다.

이미지 출처 https://byeongmoo.tistory.com/6

필요한 프로그램을 페이지 크기로 분할해서 주 메모리에 적재한다. 1, 2, 3, 4로 분할된 프로그램을 주 메모리에 적재를 하게 된다. 하지만 5번부터 문제가 발생한다. 주 메모리에 공간이 없는데, 어디에 적재해야 하는가? 에 대한 문제이다.

간단하게 FIFO로 설명하겠다. 5번 페이지는 1번을 빼주고 그 자리에 들어간다. 마찬가지로 6번 역시 2번이 빠지고 들어가게 된다. 이때 메모리에 페이지가 적재될 때 Page-in, 교체되어 나갈 때 page-out이라 하고 swapping이라고 불린다. 

이러한 교체가 일어날 때 하드디스크와 주메모리 사이에 페이지에 대한 정보를 처리하는데 걸리는 시간 차이가 존재한다. 이때 사용하는 게 Page Table으로 페이지 프레임에 적재할 때 속도 향상을 위해 캐시 메모리처럼 사용하는 방식이다.

따라서 프로그램을 가져올 때 Page Table에 저장하고, 메인 메모리에 적재해서 사용한다. 그 후 프로그램을 다시 사용할 때 테이블에 존재한다면 하드디스크에서 가져오는 게 아니라 테이블에서 가져와 더 빠르게 페이지 교체를 해서 프로그램을 사용한다.

페이지 교체 기법

• FIFO ( first in first out )

  • 가장 오래된 페이지를 Page-out 하는 방식
  • 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 정하는 방식으로 사용할 수 있다.
  • 장점 : 이해가 쉽고, 구현이 간단하다.
  • 단점 : 1번 페이지가 교체되었는데 그다음 바로 1번 페이지를 요구한다면? 따라서 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행 속도가 떨어질 위험이 있다.

• 최적 ( Optimal ) 페이지 교체

  • 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식
  • 때문에 전제조건으로 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다.
  • 하지만 미리 안다는 건 실제로 알 방법이 없기에 구현 불가능한 알고리즘이다.
  • 장점 : 가장 페이지 교체 수가 적다.
  • 단점 : 구현의 어려움 ( 연구 목적이다. )

• LRU ( least-recently-used )

  • 가장 오래 사용되지 않은 페이지를 교체하는 방식
  • 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법이다.
  • 미리 알 수 없다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측( 가장 오랜 기간 사용되지 않은)하여 교체하는 것이다
  • 장점 : 최적보다 교체 횟수가 높지만 FIFO보다 효율적이다. LRU 알고리즘은 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘으로 평가받고 있다.

• 계수-기반(Counting-Based) 페이지 교체

  페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅 하는 방식이며 두 가지 알고리즘이 있다.

• LFU ( least-frequently-used )

  • 참조 횟수가 가장 작은 페이지를 교체하는 방식
  • 만약 교체 대상인 페이지가 여러 개(횟수가 동일) 일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지를 교체한다.
  • 단점 : 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않을 경우 문제가 될 수 있다. 앞으로 사용하지 않아도 초기에 사용된 참조 횟수가 높기 때문이다.

• MFU ( most-frequently-used )

  • LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 방식
  • 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다고 판단한다.
  • 여기에서도 교체 대상이 여러 일 경우 LRU 알고리즘을 따른다. 

→ 참고. LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.

• 구현에 상당한 비용이 들고
• 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문이다.

 

세그멘테이션 (Segmentation)

이미지 출처 https://byeongmoo.tistory.com/6

세그멘테이션 기법 역시 페이징 기법과 마찬가지로 나누고 테이블을 이용해 어떤 세그먼트의 분할된 프로그램인지 현재 페이지 번호는 몇 번인지, 크기와 메모리에 올라와 있는지 등 정보를 가지고 프로그램을 실행시켜준다.

당장 필요 없는 프로그램과 필요한 프로그램을 교체해주는데 페이징과 다르게 고정된 크기가 아니고 가변 분할된 크기 이기 때문에 가변 분할에서 발생하는 외부 단편화가 발생하게 된다.

이때 남는 공간들을 효율적으로 사용하기 위해 "압축"을 하게 되고, 압축된 공간을 활용하여 프로그램을 적재하는 방식이다. 압축의 예로는 디스크 조각모음을 생각해보면 좋다.

 

→ 실제로는 세그먼테이션 기법을 사용하는데 그 안에 세그먼트를 다시 페이지처럼 고정크기로 분할하여 혼합해서 사용하는 경우가 많다고 한다.

→ 페이지 크기는 작을수록 좋을까? 정답은 없다. 너무 작게 되면 페이지의 부재가 커지고, 계속해서 페이지 교체가 이루어지기 때문에 속도 저하 문제가 발생한다. 
그렇다고 페이지의 크기가 너무 커지면 메인 메모리의 크기는 적은데, 페이지 프레임의 크기가 늘어나게 되는 현상이 발생되고, 다른 프로그램들을 사용할 수 있는 공간이 줄어들기 때문에 적절한 분할이 중요하다.

 

 

출처

dduddublog.tistory.com/32?category=801842
byeongmoo.tistory.com/8?category=835016

mynamewoon.tistory.com/12