6주차 학습 정리

Chapter 14 : 가상 메모리

14-1 : 연속 메모리 할당

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

스와핑

• 스와핑(swapping) : 메모리에 적재된 프로세스들 중 현재 실행되지 않는 프로세스들을 보조기억장치 일부 영역으로 쫓아내고, 해당 빈 공간에 다른 프로세스를 적재하여 실행하는 방식입니다.
  • 스왑 아웃 후 스왑 인될 때 스왑 아웃 전의 물리주소와는 다른 주소에 저재될 수 있습니다.
• 교체 대상 프로세스 : 입출력 작업 등의 이유로 대기 상태가 된 프로세스, 오랫동안 사용되지 않은 프로세스
• 스왑 영역(swap space) : 교체 대상 프로세스들이 임시로 보관될 보조기억장치의 일부 영역입니다.
• 스왑 아웃(swap-out) : 프로세스가 메모리에서 스왑 영역으로 옮겨오는 것입니다.
• 스왑 인(swap-in) : 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것입니다.

메모리 할당

• 메모리 할당 : 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식입니다.
• 대표적인 메모리 할당 방식
  • 최초 적합(first fit) : 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식입니다. 검색을 최소화 할 수 있고, 빠른 할당이 가능합니다.
  • 최적 적합(best fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식입니다.
  • 최악 적합(worst fit) : 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식입니다.

외부 단편화

• 외부 단편화(external fragmentation) : 프로세스들이 실행과 종료를 반복하여 메모리 사이의 빈 공간이 발생하여, 전체 빈 메모리는 충분히 존재하지만 각 빈 메모리 영역은 작아 해당 공간 보다 큰 프로세스르 적재할 수 없는 상황이 발생하여 메모리 낭비가 발생하는 것을 의미합니다.
• 외부 단편화 해결 방법
  • 압축(compaction) : 메모리 조각 모음, 메모리 내에 저장된 프로세스를 적당히 재배치시켜서 흩어져 있는 빈 공간들을 하나로 모으는 방식입니다.
    • 작은 빈 공간들을 모으는 동안 시스템이 하던 일이 중지되고, 많은 오버헤드를 야기하며, 오버헤드를 최소화하며 압축하기에 명확한 방법이 없습니다.
  • 페이징 기법 : 외부 단편화를 없앨 수 있는 또 다른 해결 방법입니다. (14-2에서 학습합니다.)

14-2 : 페이징을 통한 가상 메모리 관리

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

페이징이란

• 페이징(paging) : 프로세스의 논리 주소 공간을 페이지 단위로 자르고, 물리 메모리 주소 공간을 프레임 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법입니다.
  • 페이지(page) : 프로세스의 논리 주소 공간을 일정한 단위로 자른 것을 의미합니다.
  • 프레임(frame) : 물리 주소 공간을 페이지와 동일한 크기로 일당하게 자른 것을 의미합니다.
• 페이징 시스템의 스왑 인/아웃
  • 페이지 인(page in) : 페이징 시스템에서의 스왑 인
  • 페이지 아웃(page out) : 페이징 시스템에서의 스왑 아웃

페이지 테이블

• 페이지 테이블(page table) : 프로세스가 물리 주소에 불연속 재치되더라도, CPU가 사용하는 논리 주소에서는 연속적으로 배치되도록 사용하는 테이블입니다.페이지 번호와 프레임 번호를 짝지어 주는 이정표입니다.
• 페이지 테이블 베이스 레지스터(PTBR : Page Table Base Register) : 각 프로세스의 페이지 테이블이 적재된 주소를 가리키는 레지스터입니다.
• 각 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록되며, 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경됩니다.
• 페이지 테이블의 문제점 및 해결 방안
  • 문제점 : 메모리의 페이지 테이블에 한 번, 프레임에 접근하기 위해 한 번으로 메모리 접근 시간이 두 배로 늘어납니다.
  • 해결 방안 : CPU(일반적으로는 MMU 내) 곁에 TLB(Translation Lookaside Buffer)라는 페이지 테이블 캐시를 둬서 해결합니다.
    • CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히드(TLB hit)라고 합니다.
    • 페이지 번호가 TLB에 없는 경우 메모리 내의 테이블에 접근해야하며, 이 경우를 TLB 미스(TLB miss)라고 합니다.

내부 단편화

• 내부 단편화(internal fragmentation) : 페이징이 외부 단편화를 해결 할 수 있지만, 프로세스를 페이지 별로 할당하더라도 프로세스 크기가 페이지의 배수가 아닌 경우 마지막 페이지 할당 시 페이지 내부에서 낭비되는 메모리가 발생합니다. 해당 메모리 낭비를 내부 단편화라고 합니다.
• 내부 단편화 특징
  • 하나의 페이지 크기보다 작은 크기로 발생합니다.
  • 페이지 크기가 작은 경우 내부 단편화의 크기가 작아지지만, 페이지 크기가 너무 작을 경우 페이지 테이블의 크기가 커져서 페이지 테이블이 차지하는 공간이 낭비됩니다.

페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄하였으므로 접근하기 위한 두 가지 정보가 필요합니다.
  • 어떤 페이지 혹은 프레임에 접근할 것인지
  • 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
• 페이징 시시템의 구조
  • 페이지 번호(page number) : 접근하고자 하는 페이지 번호
  • 변위(offset) : 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보

페이지 테이블 엔트리

• 페이지 테이블 엔트리(PTE : Page Table Entry) : 페이지 테이블의 각 행들을 의미합니다.
• 페이지 테이블 엔트리에 저장 되는 주요 정보
  • 페이지 번호 및 프레임 번호 : 서로 매칭되는 정보를 저장합니다.
  • 유효 비트(valid bit) : 현재 해당 페이지에 접근 가능한지 여부를 알려줍니다.
    • 현재 페이지가 메모리에 적재되어있는지 아닌면 보조기억장치(스왑영역)에 있는지를 알려주는 비트로 메모리에 적재된 경우에는 1, 아닐 경우 0이 됩니다.
    • 페이지 폴트(page fault) : 유효 비트가 0인 메모리에 적재되지 않은 페이지로 접근하려고 하는 경우 발생하는 예외(Exception)입니다.
      • 페이지 폴트 처리 과정(하드웨어 인터럽트를 처리하는 과정과 유사)
        1. CPU는 기존 작업 내역을 백업합니다.
        2. 페이지 폴트 처리 루틴을 처리합니다.
        3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경해 줍니다.
        4. 페이지 폴트를 처리했다면 이제 CPU가 해당 페이지에 접근할 수 있게 됩니다.
  • 보호 비트(protection bit) : 페이지 보호 기능을 위해 존재하는 비트입니다.
    • 해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지 일기만 가능한 페이지인지 알려주는 비트로, 0일 경우 읽기만 가능한 페이지고, 1일 경우 읽고 쓰기가 모두 가능한 페이지입니다.
    • 비트가 0인 읽기 전용 영역인 경우(ex. 코드 영역)에 쓰기를 시도하면 운영체제가 이를 막아줍니다.
    • 보호 비트는 세 개로 복잡하게도 구현이 가능하며, 이 경우 각 비트는 읽기(Read), 쓰기(Write), 실행(eXecute)으로, 각 비트에 따라서 권한이 달라지게 됩니다.
  • 참조 비트(reference bit) : CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냅니다.
    • 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 적재 후 한 번도 읽거나 쓴 적이 없는 페이지는 0으로 유지됩니다.
  • 수정 비트(modified bit) : 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다.
    • 더티(dirty bit) 라고도 합니다.
    • 비트가 1이면 변경된 적이 잇는 페이지, 0이면 변경된 적이 없는 페이지(접근한 적이 없거나 읽기만 했던 페이지)입니다.
    • 수정 비트의 존재 이유
      • 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지 판단하기 위해서 존재합니다.
      • 수정한 페이지의 경우 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내요이 다른 값을 갔게되어서 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업을 추가해야 합니다.

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

• 외부 단편화 문제 해결 이외의 장점으로 쓰기 시 복사(copy on wirte)가 있습니다.
• 프로세스를 fork하여 동일한 프로세스 두 개가 복제될 경우 모든 자원이 복제되어 메모리에 적재되는데 복제 시 시간 낭비 및 메모리 낭비를 야기합니다.
• 쓰기 시 복사의 경우 자식 프로세스가 부모 프로세스와 동일한 프레임을 가리켜 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있으며, 부모 자식 프로세스가 메모리에 어떤 데이터도 쓰지 않고 읽기 작업만 한다면 이상태가 지속됩니다.
• 단, 부모 혹은 자식 프로세스 중 하나가 페이지에 쓰기 작업을 하는 경우 해당 페이지만 별도의 공간으로 복제됩니다.
• 쓰기 시 복사의 경우 프로세스 생성 시간의 단축 및 메모리 공간의 절약이 가능합니다.

계층적 페이징

• 계층적 페이징(hierarchical paging) : 프로세스를 이루는 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않는 방법으로 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식입니다.
  • 여러 단계의 페이지를 둔다는 점에서 다단계 페이지 테이블(multilevel page table)기법이라고도 합니다.
  • 프로세스의 페이지 테이블을 여러 개의 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 두어 잘린 페이지 테이블의 페이지들을 가리키게 하는 방식입니다.
  • 페이지 테이블 중 필요한 페이지 테이블만 메모리에 적재해서 사용합니다.
• 계층적 페이징을 사용하는 경우 논리 주소의 형태가 "바깥 페이지 번호", "안쪽 페이지 번호", "변위"로 구성됩니다.
• 2단계 페이징 대신 더 다중 계층의 페이지 테이블의 계층을 구성할 수 있으나 페이지 폴트 발생 시 메모리 참조 횟수가 늘어나게 됩니다.

14-3 : 페이지 교체와 프레임 할당

요구 페이징

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

페이지 교체 알고리즘

• 페이지 교체 알고리즘 : 요구 페이징 기법으로 페이지 적재 중 메모리가 가득 차서 적재된 페이지를 보조기억 장치로 내보낼 때 어떤 페이지를 내보낼지 결정하는 방법입니다.
  • 페이지 폴트 횟수 : 페이지 폴트가 발생한 횟수입니다.
  • 페이지 참조열(page reference string) : CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미합니다.
• 대표적인 페이지 교체 알고리즘
  • FIFO 페이지 교체 알고리즘(First-In First-Out Page Replacement Algorithm)
    • 메모리에 가장 먼저 올라온 페이지부터 교체하는 방식입니다.
    • 가장 오래 머물른 페이지를 내보내는 알고리즘 입니다.
    • 아이디어와 구현이 간단하지만, 페이지가 프로그램 실행 내내 사용하는 내용을 포함하고 있는 경우에는 페이지 폴트가 자주 발생할 것입니다.
  • 2차 기회 페이지 교체 알고리즘(Second Chance Page Replacement Algorithm)
    • FIFO의 부작용을 개선한 FIFO 페이지 교체 알고리즘의 변형입니다.
    • 기본적으로 FIFO 페이지 교체 알고리즘과 동일하게 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별하지만, 페이지의 참조 ㅍ비트가 1일 경우 바로 내보내지 않고, 참조 비트를 0으로 만든 뒤 현재 시간을 적재 시간으로 설정합니다.
    • 가장 오래 머물른 페이지의 참조 비트 0인 경우 가장 오래된 페이지면서 사용되지 않은 페이지로 판단하고 교체하게됩니다.
  • 최적 페이지 교체 알고리즘(Optimal Page Replacement Algorithm)
    • CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘입니다.
    • 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지로 해당 페이지를 교체하는 알고리즘입니다.
    • 가장 낮은 페이지 폴트율을 보장하는 알고리즘입니다.
    • 단, 최적 페이지 교체 알고리즘은 실제 구현이 어렵습니다. '앞으로 오랫동안 사용되지 않을 페이지'를 예측하는 것이 불가능에 가깝기 때문입니다.
    • 최적 페이지 교체 알고리즘은 운영체제에서 사용하기보다는 다른 페이지 교체 알고리즘의 이론상의 성능을 평가하기 위한 목적으로 사용됩니다.
  • LRU 페이지 교체 알고리즘(LRU : Least Recently Used Page Replacement Algorithm)
    • 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다.
    • 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것으로 보고 가장 사용이 적었던 페이지를 교체합니다.

스래싱과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유
  • 나쁜 페이지 교체 알고리즘
  • 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트가 자주 발생합니다.
• 스래싱(trashing) : 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
  • 스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문입니다.
• 프레임 할당 방식
  • 정적 할당 방식
    • 균등 할당(equal allocation) : 모든 프로세스에 균등하게 프레임을 제공하는 방식입니다.
    • 비례 할당(proportional allocation) : 프로세스의 크기에 따라서 큰 프로세스에는 많은 프로세스를 할당하는 방식입니다.
  • 동적 할당 방식
    • 작업 집합 모델(working set model) : 프로세스가 작업 집합을 기억하여 빈번한 페이지 교체를 방지하는 방식입니다.
      • 작업 집합(working set) : 일정 기간 동안 참조한 페이지 집합
    • 페이지 폴트 빈도(PFF : Page-Fault Frequency) : 페이지 폴트율이 상한선보다 높아지면 프레임을 추가로 할당하고, 하한선보다 낮아지면 프레임을 회수하는 방식입니다.
      • 페이지 폴트 빈도 기반 프레임 할당의 가정
        1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
        2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다.

Chapter 15 : 파일 시스템

15-1 : 파일과 디렉터리

파일

• 파일(file) : 보조기억장치에 저장된 관련 정보의 집합(논리적 단위)을 의미합니다.
• 파일 속성과 유형
  • 속성(attribute) or 메타데이터(metadata) : 파일 관련 부가 정보
  • 파일 속성의 종류
    • 유형 : 운영체제가 인지하는 파일의 종류를 나타낸다.
    • 크기 : 파일의 현재 크기와 허용 가능한 최대 크기를 나타낸다.
    • 보호 : 어떤 사용자가 해당 파일을 읽고, 쓰고, 실행할 수 있는지를 나타낸다.
    • 생성 날짜 : 파일이 생성된 날짜를 나타낸다.
    • 마지막 접근 날짜 : 파일에 마지막으로 접근한 날짜를 나타낸다.
    • 마지막 수정 날짜 : 파일이 마지막으로 수정된 날짜를 나타낸다.
    • 생성자 : 파일을 생성한 사용자를 나타낸다.
    • 소유자 : 파일을 소유한 사용자를 나타낸다.
    • 위치 : 파일의 보조기억장치상의 현재 위치를 나타낸다.
  • 파일 유형 : 운영체제가 인식하는 파일 종류, 확장자(extension)을 이용해서 운영체제에 파일 유형을 알려줍니다.
    • 실행 파일 : 없음, exe, com, bin
    • 목적 파일 : obj, o
    • 소스 코드 파일 : c, cpp, cc, java, asm, py
    • 워드 프로세서 파일 : xml, rtf, doc, docx
    • 라이브러리 파일 : lib, a, so, dll
    • 멀티미디어 파일 : mpeg, mov, mp3, mp4, avi
    • 백업/보관 파일 : rar, zip, tar
• 파일 연산을 위한 시스템 호출
  • 파일을 다루는 모든 작업이 운영체제에 의해 이뤄지므로, 파일 조작은 시스템 호출을 통해 운영체제에게 부탁해야합니다.
  • 대표적인 파일 시스템 호출 종류
    1. 파일 생성
    2. 파일 삭제
    3. 파일 열기
    4. 파일 닫기
    5. 파일 읽기
    6. 파일 쓰기

디렉터리

• 디렉터리(directory) : 파일을 일목요연하게 관리하기 위해 사용하며, 윈도우 운영체제에서는 폴더(folder)라고 합니다.
• 1단계 디렉터리(single-level directory) : 디렉터리가 하나만 존재하며, 모든 파일이 하나의 디렉터리 아래에 있는 구조입니다.
• 트리 구조 디렉터리(tree-structured directory) : 최상위 디렉터리가 있고 아래 서브(자식) 디렉터리가 있고, 서브 디렉터리 아래 또 다른 서브 디렉터리를 가지는 구조 입니다.
  • 최상위 디렉터리 : 루트 디렉터리(root directory)라고 부르고 슬래시(/)로 표현합니다. (윈도우는 C:\로 표현합니다.)
• 경로(path) : 디렉터리를 이용해 파일 위치, 파일 이름을 특정 짓는 정보입니다.
• 절대 경로와 상대 경로
  • 절대 경로(absolute path) : 모든 파일이 루트 디렉터리부터 자기 자신까지 이르는 고유한 경로를 의미합니다.
  • 상대 경로(relative path) : 현재 디렉터리부터 시작하여 파일까지의 경로를 의미합니다.
• 디렉터리 연산을 위한 시스템 호출
  • 대표적인 디렉터리 시스템 호출 종류
    1. 디렉터리 생성
    2. 디렉터리 삭제
    3. 디렉터리 열기
    4. 디렉터리 닫기
    5. 디렉터리 읽기
• 디렉터리 엔트리
  • 많은 운영체제에서 디렉터리를 '특별한 형태의 파일'이라고 간주합니다.
  • 디렉터리에 담겨있는 대상과 관련된 정보를 담고 있는 테이블(표) 형태 정보입니다.

15-2 : 파일 시스템

파티셔닝과 포매팅

• 파티셔닝(partitioning) : 저장 장치의 논리적인 영역을 구획하는 작업을 의미합니다.
  • 파티션(partition) : 파티셔닝 작업을 통해 나누어진 영역들을 의미합니다.
• 포매팅(formating) : 파일 시스템을 설정하여 어던 방식으로 파일을 저장하고 관리할 것인지 결정하고, 새로운 데이터를 쓸 준비를 하는 작업을 의미합니다.

파일 할당 방법

• 블록(block) : 운영체제에서 파일과 디렉터리를 읽고 쓸 단위입니다.
• 보조기억장치의 파일 할당 방법
  • 연속 할당(contiguous allocation) : 가장 단순한 방식으로 연속적인 블록에 파일을 할당하는 방식입니다.
    • 단점
      • 외부 단편화를 야기합니다.
  • 불연속 할당
    • 연결 할당(linked allocation) : 각 블록 일부에 다음 블록의 주속를 저장하여 각 블록이 다음 블록을 가리키는 형태로 할당하는 방식입니다.
      • 파일을 이루는 데이터를 연결 리스트로 관리합니다.
      • 단점
        • 반드시 첫 번째 블록부터 하나씩 차례대로 읽어야 합니다. 따라서 임의 접근(random access) 속도가 매우 느립니다.
        • 하드웨어 고장이나 오류 발생 시 해당 블록 이후 블록은 접근할 수 없습니다.
    • 색인 할당(indexed allocation) : 파일의 모든 블록 주소를 색인 블록(index block)이라는 하나의 블록에 모아 관리하는 방식입니다.
      • 파일 내 임의의 위치에 접근하기 쉽습니다.

파일 시스템 살펴보기

• FAT 파일 시스템 : 연결 할당의 단점을 보완한 파일 시스템입니다. 저용량 저장 장치에서 사용됩니다.
  • 파일 할당 테이블(FAT : File Allocation Table) : 다음 블록의 주소들을 한데 모아 테이블 형태로 관리하는 테이블입니다.
  • MS의 운영체제인 MS-DOS에서 사용되었고, USB 메모리, SD 카드 같은 저용량 저장 장치에서 사용됩니다.
• 유닉스 파일 시스템 : 색인 할당 방식으로, 유닉스 계열 운영체제에서 사용됩니다.
  • i-node(index node) : 유닉스 파일 시스템에서의 색인 블록입니다.
• NT 파일 시스템(NTFS) : 윈도우 운영체제에서 사용됩니다.
• ext 파일 시스템 : 리눅스 운영체제에서 사용됩니다.

---

6주차 미션

1. 기본 미션 : p. 400의 확인 문제 1번 풀고 인증하기

1.1. p. 400 : 확인 문제 1번 : 메모리 할당 방식에 대한 설명으로 올바른 것을 다음 보기에서 찾아 써 보세요.

보기

• 최초 적합
• 최적 적합
• 최악 적합

문제

1. 최초로 발견한 적재 가능한 빈 공간에 프로세스를 배치하는 방식
2. 프로세스가 적재될 수 있는 가장 큰 공간에 프로세스를 배치하는 방식
3. 프로세스가 적재될 수 있는 가장 작은 공간에 프로세스를 배치하는 방식

정답

1. 최초 적합
2. 최악 적합
3. 최적 적합

2. 선택 미션 : Ch.14(14-3)를 예시 풀어보기

예시

Ch.14(14-3) 프로세스가 사용할 수 있는 프레임이 3개 있고, 페이지 참조열이 '2414523423' 일 때 FIFO, 최적 페이지, LRU 페이지 교체 알고리즘으로 이 페이지를 참조한다면 몇 번의 페이지 폴트가 발생하는지 풀어보기

알고리즘별 풀이

FIFO : 페이지 폴트 4회 발생

페이지 참조열	2	4	1	4	5	2	3	4	2	3
페이지 폴트 발생 여부	X	X	X	X	O	O	O	O	X	X
프레임 1	2	2	2	2	5	5	5	4	4	4
프레임 2		4	4	4	4	2	2	2	2	2
프레임 3			1	1	1	1	3	3	3	3

최적페이지 : 페이지 폴트 2회 발생

페이지 참조열	2	4	1	4	5	2	3	4	2	3
페이지 폴트 발생 여부	X	X	X	X	O	X	O	X	X	X
프레임 1	2	2	2	2	2	2	2	2	2	2
프레임 2		4	4	4	4	4	4	4	4	4
프레임 3			1	1	5	5	3	3	3	3

LRU 페이지 교체 : 페이지 폴트 4회 발생

페이지 참조열	2	4	1	4	5	2	3	4	2	3
페이지 폴트 발생 여부	X	X	X	X	O	O	O	O	X	X
프레임 1	2	2	2	2	5	5	5	4	4	4
프레임 2		4	4	4	4	4	3	3	3	3
프레임 3			1	1	1	2	2	2	2	2

---

참조 자료

• 혼자 공부하는 컴퓨터 구조+운영체제 : Chapter 14 ~ 15