14.1 연속 메모리 할당

• 연속 메모리 할당 방식: 프로세스에 연속적인 메모리 공간을 할당하는 방식

14.1.1 스와핑

• 메모리에 적재된 프로세스들 중에는 현재 실행되지 않는 프로세스가 존재
  • 입출력 작업의 요구로 대기 상태가 된 프로세스
  • 오랫동안 사용되지 않은 프로세스
• 스와핑; swapping: 이러한 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메 모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식
• 스왑 영역; swap space: 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• 스왑 아웃; swap-out: 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
• 스왑 인; swap-in: 반대로스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
• 스왑 아웃되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리 주소와는 다른 주소에 적재될 수 있다

• 스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행 가능
• 프로세스 A, B, C, D의 크기를 합하면 메모리의 크기보다 크지만, 스와핑을 통해 네 개의 프로세스를 동시에 실행 가능

14.1.2 메모리 할당

• 프로세스는 메모리 내의 빈 공간에 적재되어야 한다.

  • 여기에는 세 가지 방식이 존재

14.1.2.1 최초 적합, first fit

• 최초 적합은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 바로 프로세스를 배치하는 방식

• 최초 적합 방식은 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식이므로 검색을 최소화 및 빠른 할당이 가능

14.1.2.2 최적 적합, best fit

• 최적 적합 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
• 최적 적합 방식으로 메모리를 할당하면 프로세스는 빈공간 C에 할당됩니다.

14.1.2.3 최악 접합, worst fit

• 최악 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식
• 최악 적합 방식으로 메모리를 할당하면 프로세스는 빈공간 B에 할당됩니다.

14.1.3 외부 단편화

• 연속 메모리 할당은 언뜻 들으면 당연하게 느껴질 수 있지만, 사실 이는 메모리를 효율적으로 사용하는 방법이 아니다.

• 왜냐하면 외부단편화; external fragmentation 라는 문제를 내포하고 있기 때문

• 프로세스들이 메모리에 연속적으로 할당되는 환경에서는 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다.

• 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어짐

• 이러한 현상을 외부단편화; external fragmentation 라 한다.

• 외부 단편화: 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상

• 외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축; compaction(메모리 조각 모음) 하는 방법이 존재

  • 흩어져 있는 빈 공간들을 하나로 모으는 방식으로 프로세스를 재배치시켜 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법

• 압축 방식은 여러 단점 존재

  • 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고,

  • 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며,

  • 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어려움

• 이에 외부 단편화를 없앨 수 있는 또 다른 해결 방안 - 오늘날까지도 사용되는 가상 메모리 기법, 그 중에서도 페이징 기법

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

• 프로세스를 메모리에 연속적으로 할당하는 방식은 두 가지 문제를 내포

  1. 외부 단편화

  2. 물리 메모리보다 큰 프로세스를 실행할 수 없다는 점

• 가상 메모리 virtual memory는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술

  • 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 존재
  • 페이징 기법을 이용하면 물리 메모리보다 큰 프로세스를 실행할 수 있을 뿐만아니라, 앞선 절에서 배운 외부 단편화 문제도 해결할 수 있다.
    • 현대 대부분의 운영체제가 사용

14.2.1 페이징이란

• 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문

• 페이징은 메모리의 물리 주소 공간을 프레임; frame 단위로 자르고,
• 프로세스의 논리 주소 공간을 페이지; page 단위로 자른 뒤, 각 페이지(page, 논리) 를 프레임(frame, 물리) 에 할당하는 가상 메모리 관리 기법

• 페이징에서도 스와핑을 사용할 수 있다.
  • 페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌, 페이지 단위로 스왑 아웃/스왑 인 된다.
• 즉, 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃(페이지 아웃) 되고,
• 실행에 필요한 페이지들은 메모리로 스왑 인(페이지 인) 되는 것

• 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다.
  • 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고,
  • 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있다.
  • 이와 같은 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다

14.2.1.1 페이징의 이점 - 쓰기 시 복사

• 운영체제에서 fork 시스템 호출을 하면 부모 프로세스의 복사본이 자식 프로세서로서 만들어짐.

  • 복사 작업은 프로세스 생성 시간을 늦출 뿐만 아니라 불필요한 메모리 낭비를 야기

    

• 부모 프로세스 혹은 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 하면, 그 순간 해당 페이지가 별도의 공간으로 복제

  • 각 프로세스는 자신의 고유한 페이지가 할당된 프레임을 가리키킴, 이것이 쓰기 시 복사; copy on write 이다.
  • 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간 절약도 가능

14.2.1.2 계층적 페이징

• 페이지 테이블의 크기는 작지 않다.
  • 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 메모리 낭비
• 이에 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법이 등장
  • 계층적 페이징; hierarchical Paging

• 계층적 페이징은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
  • 여러 단계의 페이지를 둔다는 점에서 다단계 페이지 테이블; multilevel page table 기법으로 불린다.
• 페이지 테이블을 여러 개의 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지들을 가리키게 하는 방식
• 페이지 테이블을 이렇게 계층적으로 구성하면 모든 페이지 테이블을 항상 메모리에 유지할 필요가 없다.
• 페이지 테이블들 중 몇 개는 보조기억장치에 있어도 무방하며, 추후 해당 페이지 테이블을 참조해야 할 때가 있으면 그때 메모리에 적재
  • 다만 CPU와 가장 가까이 위치한 페이지 테이블(Outer 페이지 테이블)은 항상 메모리에 유지해야 한다.

• 계층적 페이징을 이용하는 환경에서의 논리 주소는 아래와 같은 형태로 만들어짐.
  • 바깥 페이지 번호에 해당하는 항목은 CPU와 근접한 곳에 위치한 (바깥에 위치한) 페이지 테이블 엔트리를 가리키고
  • 안쪽 페이지 번호는 첫 번째 페이지 테이블 바깥에 위치한 두 번째 페이지 테이블, 즉 페이지 테이블의 페이지 번호를 가리킴

• 논리 주소를 토대로 주소 변환은 다음과 같이 이루어짐
  1. 바깥 페이지 번호를 통해, 페이지 테이블의 페이지를 찾기
  2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기

• 페이지 테이블의 계층이 늘어날수록 페이지 폴트가 발생했을 경우 메모리 참조 횟수가 많아짐.
  • 계층이 많다고 해서 반드시 좋다고 볼 수는 없다.

14.2.2 페이지 테이블

• 여기서 문제가 있다. 프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서 이를 순차적으로 실행할 수가 없다.
  • 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 모두 알고 있기란 어렵기 때문입
  • 즉, 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 ‘다음에 실행할 명령어 위치’ 를 찾기가 어려움
• 이를 해결하기 위해 페이징 시스템은 프로세스가 비록 (실제 메모리 내의 주소인) 물리 주소에 불연속적으로 배치되더라도
• (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 페이지 테이블; page table을 이용
• 페이지 테이블은 페이지 번호와 프레임 번호를 짝지어 줌 (매핑)
  • CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 한다.
  • 페이지 테이블은 현재 어떤 페이지가 어떤 프레임에 할당되었는지를 알려줌.

• 프로세스마다 각자의 페이지 테이블을 가지고 있고 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다.
• CPU 내의 Page Table Base Register; PTBR는 각 프로세스의 페이지 테이블이 적재된 주소를 가리킴

• 이러한 각 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록

• 프로세스의 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경

• 페이지 테이블을 메모리에 두면 문제가 발생 - 두 번의 메모리 접근이 필요하게 됨
  • 메모리에 있는 페이지 테이블을 보기 위해 한 번
  • 그렇게 알게 된 프레임에 접근하기위해 한 번

• 이 문제를 해결하기 위해, CPU 곁에 (MMU 내에) TLB; Translation Lookaside Buffer라는 페이지 테이블의 캐시 메모리를 둔다.
  • CPU 곁에는 TLB가 있다.
  • TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장
  • 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장

• CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB hit 라 한다.

  • 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요가 없다. 그렇기에 메모리 접근을 한 번만 하면 됩니다.

• 페이지 번호가 TLB에 없을 경우, 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근하는 수 밖에 없다. - TLB miss

14.2.3 내부 단편화

• 페이징은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화(internal fragmentation) 문제를 야기할 수 있다.

  • 페이징은 프로세스의 논리 주소 공간을 페이지라는 일정한 크기 단위로 자름
  • 그런데 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다, 모든 프로세스 크기가 페이지의 배수는 아니다.
  • 가령 페이지 크기가 10 KB인데, 프로세스의 크기가 108 KB 인 경우, 마지막 페이지는 2(=110-108) KB 만큼의 크기가 남음

• 이러한 메모리 낭비를 내부 단편화라고 합니다.

• 내부 단편화는 하나의 페이지 크기보다 작은 크기로 발생

• 하나의 페이지 크기가 작다면 발생하는 내부 단편화의 크기는 작아질 것으로 기대할 수 있다.

• 하지만 하나의 페이지 크기를 너무 작게 설정하면, 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비

• 그렇기에 내부 단편화를 적당히 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지의 크기를 조정하는 것이 중요

  • 일부 운영체제에서는 기본적으로 설정된 페이지 크기보다 더 큰 크기의 페이지; 대형 페이지(huge page) 도 일부 허용하며 메모리에 유지하는 경우도 있다.

14.2.4 페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄, 그렇기에 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요

  1. 어떤 페이지 혹은 프레임에 접근하고 싶은지 (페이지 번호)
  2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지(offset)

• 그렇기에 페이징 시스템에서는 모든 논리 주소 페이지 번호 page number와 변위; offset로 이루어져 있습니다.
  • 가령 CPU가 32비트 주소를 내보냈다면, 이 중 N비트는 페이지 번호, 32-N 비트는 변위
• 페이지 번호: 말 그대로 접근하고자 하는 페이지 번호
  • 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있음
• 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보
  • 즉, 논리 주소 [페이지 번호, 변위] 는 페이지 테이블을 통해 물리 주소 [프레임 번호, 변위] 로 변환

14.2.5 페이지 테이블 엔트리

• 페이지 테이블 엔트리PTE; Page Table Enty: 페이지 테이블의 각각의 행들

14.2.5.1 유효 비트; valid bit

• 유효 비트 현재 해당 페이지에 접근 가능한지 여부를 알려줌 (중요한 정보)

• 일반적으로 프로세스를 이루는 모든 페이지가 메모리에 있지 않는다. (스와핑 때문)

  • 일부 페이지는 보조기억장치(스왑 영역) 에 있는 경우가 많다.

• 유효 비트는 현재 페이지가 메모리에 적재되어 있는지(=1) 아니면 보조기억장치에 있는지를 알려주는 비트(=0)

• 만일 CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면, 페이지 폴트; Page fault 라는 예외(Exception)가 발생

• CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사

  1. CPU는 기존의 작업 내역을 백업
  2. 페이지 폴트 처리 루틴을 실행
  3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해 준다.
  4. 페이지 폴트를 처리했다면, CPU는 해당 페이지에 접근 가능

14.2.5.2 보호 비트; protection bit

• 보호 비트는 페이지 보호 기능을 위해 존재하는 비트입니다.
• 보호 비트를 통해 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있다.
• 보호 비트는 읽기(Read, r), 쓰기(Write, w), 실행(eXecute, x)의 조합으로 읽기, 쓰기, 실행하기 권한의 나타낸다.
  • 보호 비트가 100인 페이지의 경우 1은 1, w와 x는 0이므로 이 페이지는 읽기만 가능
  • 보호 비트가 110인 페이지의 경우 이 페이지는 읽고 쓰기만 가능하고 실행은 불가능
  • 보호 비트가 111인페이지는 읽기, 쓰기, 실행이 모두 가능

14.2.5.3 참조 비트; reference bit

• 참조 비트 CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냄.
• 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 이후 읽거나 쓴 적이 없는 페이지는 0으로 유지

14.2.5.4 수정 비트; modified bit, dirty bit

• 수정 비트는 해당 페이지에 데이터를 쓴 적(write) 이 있는지 없는지 수정 여부를 알려줌.

• 이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지(한 번도 접근한 적 없거나, read만 했던 페이지)임을 나타냄.

• 수정 비트는 페이지가 메모리에서 사라질 때, 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재

  • 이렇게 수정된 적이 있는 페이지가 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 함.
  • 페이지 테이블 엔트리에 수정 비트를 통해 이 작업 필요성을 판단

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

14.3.1 요구 페이징

• 요구 페이징; demand paging: 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
• 요구 페이징의 기본적인 양상
  1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
  2. 해당 페이지가 현재 메모리에 있을 경우 (유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근한다.
  3. 해당 페이지가 현재 메모리에 없을 경우 (유효 비트가 0일 경우) 페이지 폴트가 발생한다.
  4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
  5. 다시 1번을 수행한다.

14.3.2 페이지 교체 알고리즘

• 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가 메모리가 가득 참

  • 이때는 당장 실행에 필요한 페이지를 적재하기 위해 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다.

• 페이지 교체 알고리즘: 메모리에 적재된 많고 많은 페이지 중 어떤 페이지를 내보내는 것이 최선인지 결정하는 방법

  • 쫓아낼 페이지를 결정하는 방법

• 좋은 페이지 교체 알고리즘

  • 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘
  • 어떤 알고리즘을 통해 고른 페이지를 스왑 아웃시켜도 페이지 폴트가 자주 발생하지 않는다면 이는 성능 저하를 방지하는 좋은 알고리즘
  • 페이지 폴트가 일어나면 보조기억장치로부터 페이지를 가져와야 하기에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문

• 한 알고리즘을 통해 고른 페이지를 스왑 아웃시켰을 때 페이지 폴트가 자주 발생하면 이는 좋은 알고리즘이 아님.

  • 내보내면 안 되는 페이지를 보조기억장치로 내보냈기 때문

• 페이지 교체 알고리즘을 이해하려면 페이지 폴트 횟수를 알 아야 한다.

  • 페이지 폴트 횟수는 페이지 참조열; page reference sting을 통해 알 수 있다.

• 페이지 참조열; page reference sting: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열

  • 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문

14.3.2.1 FIFO, 페이지 교체 알고리즘

• First-in First-Out 이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
  • “오래 머물렀다면 나가라"는 알고리즘
• 장점: 아이디어와 구현이 간단
• 단점: 실행 초기에 적재된 페이지 속에는 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있다.
  • 이런 페이지는메모리에 먼저 적재되었다고 해서 내쫓아내는 것은 비효율

14.3.2.1 Optimal(최적), 페이지 교체 알고리즘

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

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

  • 잘 생각해 보면 메모리에 오랫동안 남아야 할 페이지는 자주 사용될 페이지
  • 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지

• 장점: 타 페이지 교체 알고리즘에 비해 페이지 폴트 발생 빈도가 가장 낮다.

• 단점: 최적 페이지 교체 알고리즘은 실제 구현이 어려움: ‘앞으로 오랫동안 사용되지 않을 페이지’를 예측하기란 어렵다.

  • 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 미리 알아야 하는데, 이는 현실적으로 불가능

• 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용

  • 최적 페이지 교체 알고리즘(하한선)에 비해 얼만큼 페이지 폴트 횟수가 발생하느냐를 통해 페이지 교체 알고리즘을 평가하기 위해 사용

14.3.2.1 LRU, 페이지 교체 알고리즘

• 가장 오랫동안 사용되지 ‘않은’ 페이지를 교체하는 알고리즘은 구현이 가능, Least Recenty Used
• ‘최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것’이라는 아이디어를 토대로 만들어짐
• 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체

14.3.3 스래싱과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유에 나쁜 페이지 교체 알고리즘만 있는 건 아니다.
• 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생
  • 사실 이것이 더 근본적인 이유라고 볼 수 있다.
• 이처럼 프레임이 부족하면 CPU는 페이지 폴트가 자주 발생할 수밖에 없다.
  • 실행의 맥이 탁 탁끊기고, 결과적으로 CPU의 이용률도 떨어짐
  • 페이지 교체에 너무 많은 시간을 쏟으면 당연히 성능에도 큰 악영향
• 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 것을 스래싱; thrashling 이라 한다.

• 가로축인 멀티프로그래밍의 정도를 통해 메모리에 올라와 있는 프로세스의 수를 알 수 있다.

  • 멀티프로그래밍의 정도: 메모리에서 동시 실행되는 프로세스의 수
  • 멀티프로그래밍의 정도가 높다면 현재 메모리에는 많은 프로세스가 동시에 실행 중이라는 이야기

• 동시에 실행되는 프로세스의 수 (멀티프로그래밍의 정도)를 늘린다고 해서 CPU 이용률이 비례해서 증가하는 것이 아님

• 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 지나치게 빈번히 발생

• 스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문

• 균등 할당; equal allocation: 모든 프로세스에 균등하게 프레임을 제공하는 방식

  • 실행되는 프로세스들의 크기는각기 다른데, 천편일률적으로 동일한 프레임 개수를 할당하는 것은 비합리적
  • 가장 단순한 형태의 프레임 할당 방식

• 비례 할당; proportional allocation: 프로세스의 크기가 크면 프레임을 많이 할당하고 크기가 작으면 프레임을 적게 나눠주는 방식

  • 프로세스의 크기와 프레임이 필요한 경우의 수는 비례하지 않을 수 있다.
  • 한계점: 프로세스가 실제로 얼마나 많은 프레임이 필요할지는 결국 실행해 봐야 아는 경우가 많다.

균등 할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만을 고려한 방식이라는 점에서 정적 할당 방식 이라 한다.

• 프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식 (동적 할당 방식)
  • 작업 집합 모델; working set model 을 사용하는 방식
  • 페이지 폴트 빈도 PPF; Page-Fault Frequency를 사용하는 방식
  • 이 두 개 방식은 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식 이라 한다.

• 작업 집합; working set: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
• 작업 집합 모델 기반 프레임 할당 방식은 ‘프로세스가 일정 기간 동안 참조한 페이지 집합’을 기억하여 빈번한 페이지 교체를 방지
  • CPU가 메모리를 참조할 때에는 참조 지역성의 원리에 의거해 주로 비슷한 구역을 집중적으로 참조
  • 만약 CPU가 어떤 프로세스를 실행하는 동안 3초에 20개의 페이지를 집중적으로 참조했다면
  • 운영체제는 그 프로세스를 위해 그 순간만큼은 최소 20개의 프레임을 할당하면 된다.

• 페이지 폴트 기반, 두 개의 가정에서 생겨난 아이디어

  1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
  2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.

• 만일 페이지 폴트율이 상한선보다 더 높아지면 그 프로세스는 너무 적은 프레임을 갖고 있다고 볼 수있다.

  • 이 경우 프레임을 더 할당해 주면 됩니다.

• 반대로 페이지 폴트율이 하한선보다 더 낮아지면 그 프로세스는 너무 많은 프레임을 갖고 있다고 볼 수 있다.

  • 이 경우 다른 프로세스에 할당하기 위해 프레임을 회수합니다.

• 페이지 폴트 빈도 기반 프레임 할당 방식은 페이지 폴트율 에 상한선과 하한선을 정하고, 이 범위 안에서만 프레임을 할당

Reference

• 혼자 공부하는 컴퓨터구조+운영체제 (강민철, 한빛미디어) https://product.kyobobook.co.kr/detail/S000061584886