메모리 할당

• 연속 메모리 할당 - 프로세스에 연속적으로 메모리 공간을 할당하는 것

• 스왑핑 - 현재 사용되지 않는 프로세스들을 보조 기억장치의 영역인 스왑영역으로 쫓아내고(swap out), 이 과정에서 생긴 빈 자리에 새로운 프로세스를 적재하는 것(swap in)

  • 이 덕분에 프로세스들이 요구하는 메모리 공간의 크기가 실제 메모리 공간보다 커도 실행이 가능하다
  • 만약 A, B, C, D 4개의 프로세스들의 요구하는 메모리 공간의 크기가 메모리 공간의 총량보다 크다면, 나중에 실행해도 되는 프로세스들은 swap out. 추후에 실행이 완료된 프로세스들이 swap out한 자리에 스왑 영역에 있던 프로세스들이 swap in
    
    

• 프로세스가 실행되기 위해서는 메모리의 빈 공간에 적재되어야 한다. 연속 메모리 할당에서는 어떠한 방식을 따르냐에 따라서 3가지 방식으로 나뉜다.

  • 최초 적합(first fit) - 운영체제가 메모리 내의 빈 공간을 순서대로 탐색하다, 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식. 검색 횟수가 적고, 빠르게 할당이 가능하다.
  • 최적 적합(best fit) - 운영체제가 빈 공간을 모두 검색한 뒤, 적재 가능한 가장 최적의 공간에 적재하는 것.
  • 최악 적합(worst fit) - 빈 공간을 모두 검색한 뒤, 적재 가능한 가장 큰 공간에 할당하는 것
    
    

• 하지만, 이렇게 메모리에 프로세스를 ‘연속적으로’ 할당하는 방식은 메모리를 효율적으로 사용하는 방법이 아니다. 외부 단편화(external fragmentation)을 유발할 수 있기 때문이다.

  • 외부 단편화(external fragmentation) - 프로세스들이 실행되고 종료되기를 반복하면서, 메모리 사이사이에 빈 공간이 발생하고, 이러한 빈 공간들은 프로세스를 할당하기에는 너무 작기 때문에, 빈 공간의 총합에 여유가 있음에도 불구하고, 프로세스가 적재되지 못하는 것.
  • 내부 단편화(internal fragmentation) - 프로세스가 필요로 하는 메모리보다 큰 메모리가 할당되어 메모리 공간에 낭비가 발생하는 것.
    
    

• 해결방안

  • 메모리 압축 - 흩어져 있는 빈 공간들을 하나로 모으는 방식. 흩어져 있는 프로세스들을 재배치하는 과정에서 오버헤드가 발생한다.
  • 가상 메모리 기법(paging) - 현대 운영체제가 사용하고 있는 기법. 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술.
    
    

페이징(Paging)

외부 단편화의 근본적인 문제 → ‘각기 다른 크기’의 프로세스들이 메모리에 연속적으로 할당되었기 때문. 만약 모든 프로세스들의 크기가 동일했다면, 외부 단편화는 일어나지 않았을 것이다.

• 페이징이란?

  • 프로세스의 가상 메모리 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리의 물리주소 공간을 프레임(frame)이라는 페이지와 동일한 단위로 자른 뒤, 페이지를 프레임에 할당하는 가상 메모리 관리 기법.
  • 페이징에서의 스왑 인을 페이지 인, 스왑 아웃을 페이지 아웃 이라고 한다.
  • 프로세스를 실행하기 위해 모든 페이지가 적재될 필요는 없기 때문에, 물리 메모리보다 용량이 큰 프로세스도 실행될 수 있다.

• 페이지 테이블

  • 프로세스가 실제 메모리 내부의 물리적 주소에 불연속적으로 배치되더라도, CPU의 주소인 논리 주소에는 연속적으로 배치되도록 하는 방법. 페이지 번호와 프레임 번호를 짝지어주는 일종의 이정표이다.
  • 물리적으로 분산되어 저장되어 있더라도, CPU의 관점에서는 연속적으로 저장된것 처럼 보인다.
  • 프로세스마다 개별적인 페이지 테이블을 보유하고 있다.
  • 외부 단편화를 해결할 수 있지만, 내부 단편화를 유발할 수 있다.

• PTBR

  • 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
  • 프로세스마다 페이지 테이블이 있고, 각 페이지 테이블은 CPU내의 프로세스 테이블 베이즈 레지스터(PTBR)가 가리킨다.

• TLB

  • PTBR을 사용하면, 메모리에 저장되어 있는 페이지 테이블을 참조하기 위해 한번, 페이지 테이블을 통해서 프레임에 접근하기 위해 한번. 이렇게 총 2번 메모리에 접근하게 된다.
  • 이를 어느정도 방지하기 위해서 페이지 테이블의 일부를 저장한 것이다. TLB를 통해서 메모리 접근횟수를 줄일 수 있다.
  • CPU가 접근하려고 하는 논리주소가 TLB에 있다면, TLB HIT, 아니면 TLB MISS

• Paging에서의 주소변환

  • 특정 주소에 접근하기 위해서는 어떤 페이지에 접근하고 싶은지, 그 주소가 해당 페이지에서 얼마나 떨어져 있는지를 알아야 한다.
  • 그렇기 때문에, 페이징 시스템에서의 논리주소는 페이지 번호(page number)와 변위(offset)으로 이루어져 있다.

• PTE

  • 페이지 테이블의 각각의 행

    • 페이지 번호

    • 프레임 번호

    • 유효비트(Valid Bit) - 현재 페이지에 접근 가능한지. 만약 유효비트가 0이라면, page fault발생. 원하는 페이지를 메모리로 가져온 뒤, 유효비트를 1로 변경해준다.

    • 보호비트 - 읽기, 쓰기, 실행가능 여부

    • 참조비트 - CPU가 페이지에 접근한 적이 있는지

    • 수정비트 - CPU가 이 페이지에 데이터를 쓴 적이 있는지

      
      

디맨드 페이징(Demand Paging)

• 디맨드 페이징

  • 처음부터 모든 페이지를 적재하지 않고, 필요한 페이지만 메모리에 적재하는 기법.
  • 페이지 테이블의 유효비트를 보고 판단한다.
  • 해당 페이지가 현재 메모리에 있는 경우(유효비트가 1), CPU는 적재된 프레임에 접근한다.
  • 해당 페이지가 현재 메모리에 없는 경우(유효비트가 0), page fault가 발생한다. → 해당 페이지를 적재하고, 유효비트를 1로 설정한다.

• 페이지 교체 알고리즘

  • 디맨드 페이징 기법으로 페이지를 적재하다보면, 언젠가는 메모리의 용량이 가득 차게 될 것이다. 당장 필요한 페이지를 적재하기 위해서는 사용하지 않는 페이지를 보조 기억장치로 내보내야한다.

  • 좋은 페이지 교체 알고리즘이란? → page fault가 적게 발생하는 것. page fault가 많이 발생한다면 보조기억장치에 접근을 자주해야하기 때문에, 성능이 저하된다.

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

    FIFO 페이지 교체 알고리즘

  • 가장 단순한 방식

  • 메모리에 가장 먼저 올라온 페이지부터 방출하는 것

  • 자주 사용되는 페이지도 방출될 우려가 있다.

    Second-Chance 알고리즘

  • FIFO 페이지 교체 알고리즘의 보완책

  • 참조비트를 참고하여, CPU가 현재 방출하려는 페이지를 참조한 적이 있으면, 이를 0으로 설정.

  • 말 그대로 기회를 한번 더 주는 것

    최적 페이지 교체 알고리즘

  • CPU에 의해서 참조되는 횟수를 고려한 것

  • 메모리에 오래 남아있어야 할 페이지는 자주 사용될 페이지이다

  • 앞으로의 사용빈도가 가장 낮은 페이지를 고체하는 알고리즘

  • page fault가 가장 적게 일어나지만, 앞으로의 행동을 예측하는것이 불가능하기 때문에 구현이 어렵다.

    LRU(Least-Recently-Used)페이지 교체 알고리즘

  • 가장 오랫동안 사용되지 않은 페이지를 교체하는 것
    
    

프레임 할당

• Page fault가 자주 발생하는 이유는 적절하지 않은 페이지 교체 알고리즘을 사용해서 일수도 있지만, 프로세스가 사용할 수 있는 프레임 자체가 적어서 일 수도 있다.
• 스레싱
  • 프로세스가 실행되는 시간보다, pagin에 더 많은 시간을 소요해서 성능이 저해되는 문제
  • CPU의 효율은 무한정 높아지지는 않는다. 증가의 한계점이 있다.
    
    
• 프레임 할당방식

  균등할당

  • 가장 단순한 방식

  • 모든 프로세스들에게 균등하게 프레임을 할당하는 방식

    비례할당

  • 프로세스의 크기에 비례하여 프레임 할당

    작업 집합 모델을 활용한 방식

  • CPU가 특정 시간동안 주로 참조한 페이지 갯수만큼만 프레임을 할당

  • 프로세스가 일정기간 동안 참조한 페이지 집합을 기억하여, 빈번한 페이지 교체를 방지하는 것

    Page fault빈도 기반의 방식

  • 프로세스가 실행하는 과정에서 페이지 할당을 결정

  • page fault율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식