[운영체제] Ch10 가상메모리

박소미·2024년 12월 5일
운영체제

운영체제

목록 보기
10/10

10.1 물리 메모리의 최대 크기

📌주소 공간과 물리 메모리

  • 물리 메모리 크기는 CPU의 주소 버스 크기에 의해 결정됨.

    • 32비트 CPU: 물리 메모리 최대 크기 4GB (2³² 주소선).
    • 64비트 CPU: 물리 메모리 최대 크기 16엑사바이트(EB) (2⁶⁴ 주소선).하지만 현실적으로는 하드웨어 설계로 인해 최대 24TB 정도 지원.

실제 설치되는 물리 메모리

  • 64비트 컴퓨터 기준:

    • 대부분 8GB ~ 32GB 수준.
    • 시스템 요구사항 및 하드웨어 비용에 따라 제한됨.

📌물리 메모리의 한계와 해결 방안

문제: 물리 메모리의 크기 한계

  • 질문 1: 물리 메모리보다 큰 프로세스를 실행할 수 있는가?

  • 질문 2: 여러 프로세스를 합친 크기가 물리 메모리보다 클 때 모두 실행할 수 있는가?

기본 가정

  • 전제: 프로세스 전체가 물리 메모리에 적재되어야 실행 가능하다는 가정.

문제 상황

  1. 프로세스가 물리 메모리보다 큰 경우(예: 단일 프로세스가 물리 메모리 크기를 초과)

    • 실행 불가로 간주.

  2. 여러 프로세스를 합한 크기가 물리 메모리보다 큰 경우(예: 동시에 여러 프로그램을 실행)

    • 모든 프로세스를 동시에 메모리에 올릴 수 없음.

10.2 가상 메모리 개념

📌가상 메모리 개요

가상 메모리의 필요성

  • 문제: 물리 메모리의 크기 제한으로 인해 대형 프로그램 실행 및 다중 프로세스 동시 실행이 어려움.

  • 해결책: 가상 메모리를 통해 물리 메모리의 한계를 극복.

가상 메모리 기법의 핵심 요소

  1. 물리 메모리를 디스크 공간으로 확장

    • 프로세스를 물리 메모리와 하드 디스크(보조기억장치)에 나누어 저장.
    • 가정: 사용자와 프로세스가 충분히 큰 물리 메모리를 가진 것처럼 동작.
    • 효과:
      • 다중 프로세스 실행 가능.
      • CPU 활용률 및 처리율 증가.

  2. 스와핑(Swapping)

    • 정의: 물리 메모리가 부족할 때, 실행에 필요하지 않은 메모리 부분을 하드 디스크로 이동(Swap Out)하고, 필요할 때 다시 물리 메모리로 이동(Swap In).

📌가상 메모리 개념 정리

  1. 운영체제의 역할

    • 물리 메모리 영역을 하드 디스크로 확장하여 프로세스를 저장.
    • 메모리와 디스크를 나누어 사용하는 방식으로 물리 메모리 크기 한계를 극복.

  2. 프로세스 실행 방식

    • 프로세스 전체를 물리 메모리에 적재할 필요 없이, 실행에 필요한 코드나 데이터 일부만 메모리에 적재.
    • 나머지는 필요 시 하드 디스크에서 물리 메모리로 가져오는 방식.

  3. 메모리 부족 시 해결

    • 메모리가 부족하면 사용하지 않는 메모리 부분을 하드 디스크로 이동(Swap-Out).
    • 빈 메모리 공간을 확보하여 실행 중인 프로세스를 계속 유지.

  4. 메모리 확장 활용

    • 물리 메모리를 디스크 스왑 영역으로 확장.
    • 필요 시 디스크에서 메모리로 다시 가져오는 스왑-아웃, 스왑-인을 통해 동작.

  5. 사용자 관점의 편리성

    • 사용자는 물리 메모리의 한계를 의식하지 않고 무한한 메모리가 있는 것처럼 사용 가능.
    • 큰 프로그램 작성이나 다중 프로그램 실행에도 부담 없음.

  6. 운영체제별 구현 차이

    • 각 운영체제마다 가상 메모리를 구현하는 방식이 상이하며, 이에 따라 성능 차이가 발생.

📌가상 메모리를 사용하는 시스템에서 프로세스와 물리 메모리, 하드 디스크의 관계

  1. 프로세스와 물리 메모리

    • 각 프로세스는 물리 메모리와 하드 디스크의 스왑 영역에 나누어 저장됨.
    • 운영체제는 물리 메모리 크기의 한계를 극복하기 위해 필요한 데이터만 물리 메모리에 적재.

  2. 스왑(Swap) 영역

    • 물리 메모리에 빈 공간이 부족할 경우, 메모리의 일부를 하드 디스크의 스왑 영역으로 이동.
    • 스왑 영역은 임시 저장 공간으로 활용되며, 필요 시 다시 물리 메모리로 이동(Swap-In).

  3. 사용자 관점

    • 사용자와 프로세스는 무한대 메모리를 사용하는 것처럼 인식.
    • 프로세스는 논리적으로 연속된 메모리 공간에 저장되는 것처럼 보이지만, 실제로는 분산 저장됨.

  4. 운영체제 관점

    • 운영체제는 물리 메모리와 하드 디스크를 연동하여 효율적인 메모리 관리 수행.
    • 각 프로세스는 사용하지 않는 부분을 스왑 영역에 저장함으로써, 여러 프로세스가 동시에 실행될 수 있도록 지원.

  5. 디스크 관점

    • 하드 디스크의 스왑 영역은 물리 메모리를 보조하는 역할.
    • 파일 및 디렉터리 저장 공간과는 별도로 운영되며, 성능 최적화를 위해 사용.

📌가상 메모리 구현

  1. 요구 페이징 (Demand Paging)

    • 페이징 기법을 기반으로, 프로세스의 일부 페이지만 물리 메모리에 적재.

    • 요구 페이징 = 페이징 + 스와핑

    • 구성 요소:

      • 페이징(paging): 페이지 단위로 메모리를 관리.
      • 스와핑(swapping): 사용하지 않는 페이지를 스왑 영역으로 이동하고 필요 시 다시 적재.

  2. 요구 세그멘테이션 (Demand Segmentation)

    • 세그먼테이션 기법에 기반하며, 프로세스를 논리적인 세그먼트(코드, 데이터 등)로 나눔.
    • 필요한 세그먼트만 물리 메모리에 적재하고, 나머지는 디스크에 저장.
    • 세그먼트 스와핑을 통해 필요한 세그먼트만 스왑 인/아웃을 수행.

📌가상 메모리 기법에 대한 주요 의문들

  1. 스래싱 문제

    • 물리 메모리와 스왑 영역 사이에 입출력이 빈번히 발생할 경우 성능 저하를 어떻게 해결할 수 있을까?

  2. 페이지 테이블

    • 페이지 테이블은 어떤 방식으로 구성할지?

  3. 페이지 폴트 (Page Fault)

    • 페이지가 프레임에 없는 경우 이를 어떻게 처리할지?

  4. 페이지 할당

    • 어떤 페이지를 물리 메모리에 둘 것인지, 어떤 페이지를 하드 디스크로 이동할지 결정하는 기준은 무엇일까?

  5. 스왑 영역

    • 디스크의 스왑 영역 크기를 설정하는 적정 기준은?

  6. 프레임 할당

    • 각 프로세스에 할당할 프레임의 개수를 결정하는 정책은 무엇이 가장 효율적일까?

  7. 작업 집합

    • 일정 시간 동안 프로세스가 실제로 사용하는 프레임 수를 어떻게 측정하고 관리할 수 있을까?

  8. 페이지 교체 알고리즘

    • 어떤 프레임을 비워야 하는지? 그 프레임에 저장된 페이지는 어떻게 처리할 것인지?

  9. 쓰기 시 복사 (Copy-On-Write)

    • 자식 프로세스의 메모리 공간은 어떻게 되는지?

10.3 요구 페이징

📌요구 페이징 개념

  1. 개념

    • 실행에 필요한 일부 페이지만 물리 메모리에 적재하고, 나머지는 하드 디스크(스왑 영역)에 두는 방식이다. 필요할 때만 메모리에 적재하여 효율적으로 메모리를 관리한다.
    • 프로세스의 페이지가 있는 디스크 영역 = 스왑 영역 + 실행 파일

  2. 요구(Demand)의 의미

    • 페이지가 실행 중에 필요할 때 적재되는 방식을 의미한다.
    • swap in

  3. 요구 페이징 구현의 전형적 형태

    • 첫 페이지만 물리 메모리에 적재하고,
    • 실행 중 다른 페이지가 필요할 경우 해당 페이지를 적재한다.

  4. 스왑 영역

    • 리눅스(Linux): 디스크 내의 특정 위치 또는 스왑 파티션에 설정됨.
    • 윈도우(Windows): C:/pagefile.sys 파일을 스왑 영역으로 활용함.

📌페이지 테이블 항목

  1. present/valid bit (페이지 존재 비트)

    • 해당 페이지가 물리 메모리에 있는지 여부를 나타냄.
    • 값이 1인 경우: 해당 페이지는 물리 메모리에 적재되어 있음.
    • 값이 0인 경우: 해당 페이지는 디스크에 있음.

  2. modified/dirty bit (수정 여부 비트)

    • 페이지가 수정되었는지 여부를 나타냄.
    • 값이 1인 경우: 페이지가 수정되었으며, 쫓겨날 때 스왑 영역에 저장되어야 함.
    • 값이 0인 경우: 페이지가 수정되지 않았으며, 쫓겨날 때 추가 저장이 필요하지 않음.

  3. physical address (물리 주소)

    • present bit이 1인 경우: 물리 메모리의 프레임 번호를 나타냄.
    • present bit이 0인 경우: 디스크 상의 블록 번호를 나타냄.

페이지 폴트 (Page Fault)

  • CPU가 액세스하려는 페이지가 물리 메모리에 없을 때 발생.

  • 페이지 폴트가 발생하면:

    1. 빈 프레임이 있는지 확인.
    2. 없는 경우, 기존 페이지를 스왑 영역으로 쫓아내고 새 페이지를 적재.
    3. 디스크의 스왑 영역이나 실행 파일에서 해당 페이지를 물리 메모리에 적재.

📌요구 페이징 구성

  1. 프로세스 주소 공간

    • 프로세스는 여러 페이지로 나뉘며, 각 페이지는 논리 주소로 접근된다.
    • 필요한 페이지가 없을 경우 디스크의 스왑 영역에서 가져온다.

  2. 페이지 테이블

    • 페이지 테이블에는 각 페이지의 상태를 나타내는 비트와 물리적 주소 또는 디스크 블록 번호가 저장된다.

      • present 비트: 페이지가 물리 메모리에 있는지 여부를 나타냄.

      • modified 비트: 페이지가 수정되었는지 여부를 나타냄.

      • physical address: 페이지가 물리 메모리 상의 어느 프레임에 있는지를 나타냄.

      • disk block number: 페이지가 물리 메모리에 없는 경우 디스크 상의 위치를 나타냄.

  3. 물리 메모리

    • 페이지는 물리 메모리의 프레임 단위로 저장된다.
    • 스왑-인/스왑-아웃 과정을 통해 필요 없는 페이지는 디스크로 옮겨지고, 필요한 페이지는 메모리로 로드된다.

  4. 스왑 영역

    • 물리 메모리에 적재되지 않은 페이지는 디스크 내의 스왑 영역에 저장된다.
    • 실행 파일이나 데이터 파일의 일부로 저장되며, 필요 시 물리 메모리로 이동한다.

📌페이지 폴트 정의

  1. 발생 상황

    • CPU가 생성한 가상 주소의 페이지가 메모리의 프레임에 없는 경우 발생.
    • 이 과정에서 MMU(Memory Management Unit)가 주소 변환을 수행하지만 물리 메모리에 해당 페이지를 찾지 못함.

사례 설명

  • 상황:main() 함수와 전역 변수 n을 가진 C 프로그램.

    • 전역 변수 n의 가상 주소: 0x11111234.
    • 해당 주소는 가상 페이지 번호 0x11111에 속함.

기계어 코드

  1. mov eax, 10

    • 레지스터 eax에 값 10 저장.

  2. mov [11111234], eax

    • 값 10을 가상 주소 0x11111234에 저장하려고 시도.
    • 페이지 0x11111에 접근이 필요하지만 해당 페이지가 물리 메모리에 없으므로 페이지 폴트 발생.

페이지 폴트 발생 과정

  1. 페이지 폴트 트리거

    • mov [11111234], eax 명령 실행 시 CPU는 페이지 테이블에서 해당 주소를 확인.
    • 물리 메모리 프레임이 없는 경우, 페이지 폴트 신호 발생.

  2. 운영체제 개입

    • 운영체제가 스왑 영역 또는 실행 파일에서 해당 페이지를 적재.
    • 페이지 테이블 업데이트 후, 다시 명령 실행 재개.

페이지 폴트 발생 및 처리 과정

1. CPU 명령 실행 요청

  • CPU는 명령어 mov [11111234], eax를 실행하려고 한다.
  • 명령어에서 사용하는 가상 주소 0x11111234는 페이지 번호 0x11111과 오프셋 234로 나뉜다.

2. MMU에 의한 페이지 테이블 검색

  • MMU(Memory Management Unit)는 페이지 번호 0x11111을 페이지 테이블에서 검색한다.
  • 페이지 테이블의 해당 항목을 확인하여 물리 메모리에 페이지가 존재하는지 검사한다.

3. 페이지 폴트 발생

  • 페이지 테이블의 P 비트(Present Bit)가 0으로 설정되어 있다.
  • 이는 페이지가 물리 메모리에 존재하지 않음을 의미하며, 페이지 폴트가 발생한다.
  • 이후, 페이지 폴트 처리 루틴이 호출된다.

4. 페이지 폴트 핸들러 호출

  • 페이지 폴트 발생 시, 운영체제의 커널 코드인 페이지 폴트 핸들러가 실행된다.
  • 핸들러는 부족한 페이지를 물리 메모리로 가져오기 위한 작업을 수행한다.

5. 스왑 영역에서 페이지 검색

  • 페이지 0x11111에 해당하는 데이터가 스왑 영역 또는 실행 파일에 저장되어 있다.
  • 페이지 테이블의 disk block number를 참조하여 스왑 영역에서 데이터를 검색한다.

6. 빈 프레임 또는 교체 프레임 선택

  • 물리 메모리에 빈 프레임이 없으면, 교체 알고리즘(LRU 등)에 따라 기존 프레임을 선택하여 교체한다.
  • 이 경우, 프레임 55555가 교체 대상이 된다.

7. 스왑 아웃 및 스왑 인

  • 교체 대상 프레임(55555)의 데이터를 스왑 영역으로 이동(스왑 아웃).
  • 스왑 영역에서 페이지 0x11111 데이터를 읽어와 물리 메모리의 프레임 55555에 적재(스왑 인).

8. 페이지 테이블 갱신

  • 페이지 테이블에서 페이지 0x11111의 P 비트(Present Bit)를 1로 변경한다.
  • 물리 주소 필드를 갱신하여 프레임 55555와 매핑한다.

9. CPU 명령 재실행

  • 페이지가 물리 메모리에 적재되었으므로 CPU는 명령어 mov [11111234], eax를 다시 실행한다.
  • 가상 주소 0x11111234는 성공적으로 물리 주소 55555234로 변환된다.
  • 11111번 페이지 테이블 항목의 M비트는 1로 변경된다.

10. 정상 실행 완료

  • CPU가 물리 주소 55555234에 성공적으로 접근하며 명령어 실행을 완료한다.

페이지와 프레임을 구분해야 함
페이지는 프로세스를 자른 것이고 11111 (가상) 프레임은 물리 메모리를 자른 것이다. 55555

네모 칸 뚫어놓고 문제 낼 수도, 작년에는 순서 쓸 수 있게 1~10 비어두고 냄 (이건 안 낼 듯)

📌쓰기 시 복사(Copy-On-Write, COW)

1. 프로세스 생성

  • 프로세스는 fork() 시스템 호출을 통해 생성된다.

  • 이 호출은 운영체제마다 동작 방식은 다를 수 있지만, 새로 생성된 자식 프로세스는 부모 프로세스와 동일한 메모리 공간을 가진다.

  • 자식 프로세스는 부모의 메모리와 페이지 테이블을 복사하여 시작된다.

2. fork()가 메모리를 생성하는 방식

  1. 완전 복사 방식

    • 부모 프로세스의 모든 페이지를 자식 프로세스에 복사.
    • 단점: 비효율적이며, 특히 fork() 이후 바로 exec()로 실행 파일을 교체하는 경우 불필요한 복사가 발생.

  2. 쓰기 시 복사 방식 (Copy-On-Write)

    • 부모 프로세스의 페이지 테이블만 복사: 부모 프로세스의 메모리 프레임을 완전 공유

    • 자식 프로세스의 페이지 테이블 항목에 "쓰기 시 복사"로 표시.

    • 부모나 자식 프로세스 중 하나가 해당 페이지를 수정하려고 시도할 때:

      • 수정 요청 시, 운영체제는 새로운 물리 메모리 프레임을 할당.
      • 원래 프레임 데이터를 새 프레임으로 복사 후 수정 작업 수행.

📌완전 복사

1. 개요

  • 완전 복사는 fork() 시스템 호출을 통해 자식 프로세스를 생성할 때, 부모 프로세스의 메모리를 그대로 복사하는 방식이다.
  • 복사된 메모리는 부모와 자식 프로세스가 독립적으로 사용할 수 있다.

2. 과정

  1. 부모 프로세스의 상태

    • 부모 프로세스는 자신의 페이지 테이블을 가지고 있으며, 물리 메모리의 여러 프레임을 참조한다.
    • 페이지 테이블에는 각 페이지가 어떤 물리 메모리 프레임에 매핑되어 있는지 정보가 포함되어 있다.

  2. fork() 호출

    • 자식 프로세스가 생성되면서 부모 프로세스의 페이지 테이블과 물리 메모리 프레임이 동일하게 복사된다.
    • 자식 프로세스는 복사된 페이지 테이블을 통해 새로운 물리 메모리 프레임을 참조한다.

  3. 결과

    • 부모와 자식은 각각 독립적인 물리 메모리 프레임을 가지며, 서로 영향을 주지 않는다.
    • 메모리의 모든 내용이 복사되기 때문에, 부모와 자식 간의 데이터 충돌 가능성은 없다.

📌완전 복사의 비효율성

1. 개요

  • fork() 후 대부분의 자식 프로세스는 exec()를 호출하여 다른 프로그램을 실행한다.
  • 이 과정에서 복사된 부모 프로세스의 메모리는 exec() 호출과 함께 무효화된다.

2. 비효율적인 이유

  1. 불필요한 메모리 복사

    • fork()는 부모 프로세스의 페이지를 전부 복사한다.
    • 하지만, exec()가 호출되면 자식 프로세스는 복사된 페이지를 더 이상 사용하지 않고, 새로운 실행 파일(ls)의 페이지를 메모리에 적재한다.

  2. 성능 저하

    • 대규모 메모리를 복사하는 작업은 시간이 많이 소요된다.
    • 복사된 페이지가 무효화되므로 CPU, 메모리, 디스크 등의 리소스를 낭비하게 된다.

3. 예제 코드

int childPid = fork(); // 쉘을 복제한 자식 프로세스 생성
if (childPid == 0) {
    // 자식 프로세스 코드
    execlp("/bin/ls", "ls", NULL); // "/bin/ls" 실행
}
  • fork() 동작
    • 부모 프로세스의 메모리 페이지를 복사.
  • exec() 호출
    • 복사된 메모리 페이지는 모두 반환되고, 실행 파일(/bin/ls)의 페이지가 새로 메모리에 적재됨.

4. 메모리 동작 과정

  1. fork()

    • 부모 프로세스의 메모리를 복제하여 자식 프로세스를 생성.
    • 자식 프로세스는 부모 프로세스와 동일한 페이지 테이블을 가짐.

  2. exec()

    • 자식 프로세스의 기존 페이지는 모두 반환.
    • /bin/ls 실행 파일의 새로운 페이지가 메모리에 적재.

📌쓰기 시 복사(COW)로 자식 프로세스를 생성하는 과정

1. (a) 부모 프로세스 상태

  • 부모 프로세스는 페이지 테이블과 물리 메모리를 사용하여 데이터를 관리하고 있다.

  • 모든 페이지는 읽기/쓰기(Read/Write) 권한을 가짐.

  • 부모 프로세스만 페이지를 소유.

2. (b) fork() 호출 후

  • 페이지 공유:

    • 부모와 자식 프로세스는 동일한 물리 메모리의 페이지를 공유.
    • 공유된 페이지들은 읽기 전용(Read-Only) 상태로 설정.
    • 자식 프로세스는 부모의 페이지 테이블을 복사하지만 물리 메모리는 공유.

  • 효율성:

    • 페이지 복사를 최소화하여 메모리 사용량과 CPU 작업을 줄임.

3. (c) 자식 프로세스에서 쓰기 발생

  • 페이지 복사:

    • 자식 프로세스가 페이지에 쓰기 작업을 수행하려 하면, 쓰기 시 복사(Copy-On-Write)가 발생.
    • 운영체제는 새로운 프레임을 할당하고, 해당 페이지를 복사.
    • 이후 자식 프로세스는 새로운 페이지를 소유하고, 읽기/쓰기 권한을 가짐.

  • 원리:

    • 공유 페이지를 수정하려는 프로세스만 데이터를 복사하므로 불필요한 복사를 방지.

과정 요약

  1. fork() 호출:

    • 부모와 자식 프로세스가 동일한 물리 페이지를 공유.
    • 페이지는 읽기 전용(Read-Only)으로 설정.

  2. 쓰기 요청 발생:

    • 자식 프로세스가 페이지를 수정하려고 하면 쓰기 시 복사가 발생.
    • 운영체제는 새로운 물리 프레임을 할당하고, 데이터를 복사.

  3. 최종 상태:

    • 자식 프로세스는 수정된 페이지에 대한 독립적인 읽기/쓰기 권한을 가짐.
    • 부모와 자식 프로세스는 수정되지 않은 나머지 페이지는 여전히 공유.

📌쓰기 시 복사의 장점

1. 프로세스 생성 시간 절약

  • 페이지 테이블만 복사

2. 메모리 절약

  • 둘 다 읽기만 하는 페이지는 새로운 프레임을 할당 X (메모리 절약)

  • 예시: 프로세스의 코드 페이지 (읽기용 페이지 프레임은 자동 공유)

📌탐구 10-1 요구 페이징에 대해 생각해 볼 이슈

Q1. 요구 페이징은 필연적으로 페이지 폴트를 동반한다. 디스크와 메모리 사이의 빈번한 입출력으로 인해 시스템 성능이 떨어지지 않을까?

A1. 프로세스의 실행 초기에는 필요한 페이지를 메모리에 적재하기 위해 페이지 폴트가 계속 발생하겠지만 얼마 지나지 않아 필요한 페이지들이 메모리에 적재되면 그 이후부터는 간혈적으로 패이지 폴트가 발생한다.

페이지 폴트가 과도하게 발생하는 경우 스레싱이라고 부르며 설치된 메모리 량에 비해 과도하게 프로세스가 실행되고 있는 경우이다. 스래싱이 발생하면 많은 디스크 입출력으로 인해 시스템 성능이 떨어진다.

Q2. 프로세스의 실행 동안 페이지 폴트가 계속되면 언젠가 메모리에는 그 프로세스의 많은 페이지들이 존재하게 될 텐데 왜 처음부터 이들을 적재하지 않을까?

A2. 프로세스의 실행이 금방 종료될지 오랜 후에 종료될지, 모든 페이지들을 다 사용할 지 일부 페이지만 사용할지 실행 전에는 알 수 없다. 또 어떤 페이지는 오랫동안 사용되기도 하고 어떤 페이지는 한 번 사용된 후 사용되지 않기도 하므로 모든 페이지를 처음부터 메모리에 올려놓는 것은 메모리 낭비이다.

Q3. 한 프로세스에게 할당할 수 있는 메모리 프레임은 무한정인가 아니면 제한적인가?

A3. 운영체제마다 다르지만 일반적으로 프로세스 당 할당하는 메모리 프레임의 개수를 제한한다. 운영체제는 물리 메모리 량의 한계때문에 프로세스에게 적절한 수의 프레임만 할당한다.

Q4. 프로세스에게 할당하는 메모리 프레임 수와 페이지 폴트의 관계는?

A4. 프로세스에게 할당하는 프레임의 개수가 지나치게 작으면 페이지 폴트가 많이 발생하고 프레임의 개수가 너무 많으면 페이지 폴트의 횟수가 작아지지만 프레임이 낭비될 수 있다.

Q5. 페이지 폴트를 처리하는 과정에서 커널 코드나 커널 데이터가 적재된 메모리 프레임도 스왑-아웃되는 희생 프레임으로 선택되는가?

A5. 커널 코드와 커널 데이터가 적재된 프레임은 희생 프레임으로 선택하지 않는다. 즉 스왑-아웃되지 않는다. 만일 인터럽트 핸들러가 스왑-아웃되어 메모리에 업사면 인터럽트가 발생하였을 때 인터럽트 핸들러가 실행될 수 없거나 실행되는데 매우 긴 시간이 걸릴 것이다.

📌페이지 폴트와 스래싱 (Thrashing)

1. 페이지 폴트와 디스크 I/O

  • 현상: 페이지 폴트가 발생하면 디스크 I/O가 증가함.
  • 영향: CPU는 디스크 입출력 대기 상태가 되고 시스템 성능 저하.

2. 스래싱(Thrashing or Disk Thrashing)

  • 정의:

    • 메모리 프레임에 페이지가 반복적으로 교체되면서 디스크 입출력이 급증하는 현상.
    • 결과: CPU 활용률 감소 및 시스템 성능 저하.

  • 특징:

    • 스왑-아웃과 스왑-인 작업이 도미노처럼 발생.
    • 연속적인 페이지 폴트로 인해 스레드는 대기 상태로 빠짐.

3. 스래싱 원인

  1. 다중 프로그래밍 정도가 과도한 경우

    • 메모리에 비해 너무 많은 프로세스가 실행됨.
    • 프로세스 당 할당된 프레임 수가 부족하여 필요한 페이지가 적재되지 못함.

  2. 잘못된 메모리 할당/페이지 교체 알고리즘

    • 효율적인 알고리즘 미적용 시 스래싱 가능성 증가.

  3. 기본적으로 메모리량 부족

    • 물리적 메모리 용량 자체가 작은 경우.

  4. 특정 시점에 많은 프로세스 실행

    • 특정 시간대에 과부하가 발생하며 스래싱 유발.

📌스래싱 현상 관찰

스래싱이 발생하는 시점

  1. 다중 프로그래밍 정도(DOM)가 높아질수록 CPU 활용률 증가

    • 다중 프로그래밍의 정도가 높아질수록 시스템은 더 많은 프로세스를 동시에 처리할 수 있어 CPU 활용률도 증가.

  2. 임계점(M)을 초과하면 스래싱 발생

    • 특정 임계점(M)을 넘어가면 시스템이 처리해야 할 페이지 교체 작업이 급증하면서 스래싱 시작.
    • CPU 활용률 급감 및 I/O 요청이 증가하며 시스템 성능 저하.

(a) 메모리가 작은 경우

  • 다중 프로그래밍의 정도(DOM)가 커질수록 프로세스당 할당 가능한 메모리 프레임 수 감소.
  • 임계점(M)에 도달하면 디스크 I/O 급증과 함께 CPU 활용률이 감소하며 스래싱 발생.

(b) 메모리가 많은 경우

  • 메모리가 충분히 클 경우 임계점(M)이 더 높아짐.
  • 하지만 다중 프로그래밍 정도가 매우 높아져도 임계점을 초과하면 스래싱 발생 가능.

결론: 스래싱은 시스템 자원의 한계와 다중 프로그래밍 간의 균형이 무너질 때 발생.

📌스래싱 해결 및 예방

스래싱 감지 방법

  1. 운영체제에 따라 다름

    • 윈도우: Process Explorer와 같은 도구를 사용하여 CPU 활용률과 디스크 I/O 상태 확인.
    • 리눅스:
      • top, htop, vmstat 명령어를 통해 작업 부하 확인.
      • CPU 활용률이 낮고, 스왑-인/스왑-아웃 빈도가 높은지 검사하여 스래싱 여부 판단.

해결 및 예방 방법

  1. 다중 프로그래밍 정도(DOM) 줄이기

    • 몇몇 프로세스 종료

  2. 하드 디스크 대신 빠른 SSD 사용

    • 스래싱 시 발생하는 디스크 I/O 병목 현상을 완화하기 위해 SSD로 업그레이드.

  3. 메모리 용량 확장

    • 물리 메모리를 늘려 더 많은 프로세스를 수용 가능하도록 개선.

10.4 참조의 지역성과 작업 집합

📌프로그램의 실행 특성: 참조의 지역성(Reference of Locality)

참조의 지역성 정의

  1. 개념

    • CPU가 짧은 시간 내 특정 메모리 영역을 반복적으로 참조하는 경향.
    • 프로그램 실행 중 동일 데이터나 코드 부분에 집중적으로 접근.

  2. 특성

    • Locality(지역성):

      • 최근 참조한 데이터/코드를 다시 참조하는 경향.

    • 참조의 지역성은 시간적 지역성과 공간적 지역성으로 구분됨.

      • 시간적 지역성: 동일 데이터나 코드가 반복적으로 사용.
      • 공간적 지역성: 참조된 데이터 주변 영역도 참조.

  3. 90/10 규칙

    • "프로그램 코드의 10%가 실행 시간의 90%를 차지한다"는 경험적 법칙.

의미

  1. 효율적인 자원 관리

    • 프로그램 실행 패턴을 관찰하여 가까운 미래의 메모리 접근을 예측 가능.
    • 이를 통해 효율적인 메모리 할당 및 페이지 교체 전략에 활용 가능.

  2. 실행 패턴 활용

    • 지역성을 기반으로 캐시 메모리 및 페이지 교체 알고리즘 최적화 가능.

📌참조의 지역성 형태 (Types of Locality)

1. 시간 지역성 (Temporal Locality)

  • 정의: 시간적으로 가까운 시점에 같은 자원(코드, 데이터)이 반복적으로 사용되는 특성.

  • 주요 특징:

    • 최근 사용된 데이터나 코드가 다시 참조될 가능성이 높음.
    • 대표적인 사례: 반복문 실행.
      • 반복문 내부의 코드와 데이터가 계속 재참조됨.

2. 공간 지역성 (Spatial Locality)

  • 정의: 메모리 주소가 가까운 위치에 있는 데이터가 함께 사용되는 경향.

  • 주요 특징:

    • 지금 참조된 주소 주변에 있는 데이터나 코드가 가까운 미래에 참조될 가능성이 높음.
    • 대표적인 사례:
      • 배열 사용: 순차적으로 인덱스를 접근하기 때문에 공간적으로 가까운 메모리 참조가 발생.
      • 코드 실행 순서: 예를 들어, 100번지를 참조했다면, 다음엔 104번지를 참조할 가능성이 높음(인접 명령어 실행).

📌작업 집합(Working Set), 페이지 폴트(Page Fault), 스래싱(Thrashing)

1. 작업 집합(Working Set)

  • 정의: 일정 시간 범위 내에 프로세스가 액세스(참조)한 페이지들의 집합.

    • 작업 집합에 포함된 페이지들이 모두 메모리에 적재되어 있을 경우 프로세스 실행 성능이 가장 높음.

  • 시간 범위와 작업 집합의 크기:

    • 시간 범위가 커질수록 작업 집합 크기가 증가함.
    • 시간 범위를 어떻게 정할 것인지가 작업 집합 관리의 핵심.

  • 참조의 지역성과의 관계:

    • 참조의 지역성으로 인해 일정 시간 내에 작업 집합이 뚜렷하게 형성됨.

2. 작업 집합과 페이지 폴트

  • 프로세스 실행 중 페이지 폴트가 빈번히 발생하면 작업 집합에 포함된 페이지를 메모리에 적재하지 못함.

  • 시간이 지나면서 페이지 폴트가 줄어들고, 작업 집합이 안정적으로 형성됨.

3. 스래싱(Thrashing)과의 관계

  • 작업 집합이 메모리보다 커질 경우 스래싱이 발생:

    • 페이지 폴트가 너무 자주 발생하면서 디스크 I/O가 증가.
    • CPU가 유휴 상태에 빠지고 시스템 처리 성능이 급격히 저하됨.

📌작업 집합이 형성되는 과정

1. 초기 메모리 적재

  • 시작 시점: int main()이 호출되면서 실행이 시작됨.

  • 페이지 2(코드):

    • main() 함수가 있는 코드 영역의 페이지가 초기 적재됨.

2. 페이지 폴트 발생

  • for 루프 실행 중:

    • f() 함수를 호출하면서 페이지 5가 참조됨.

    • 이로 인해 페이지 5(코드)가 메모리에 적재됨(페이지 폴트 발생).

3. 페이지 폴트와 참조

  • void f() 함수:

    • 루프 내에서 n[j]와 같은 데이터가 참조됨.

    • 페이지 20(데이터)가 메모리에 적재됨(페이지 폴트).

4. 작업 집합 형성

  • 프로세스 실행이 반복되면서 특정 페이지 집합이 메모리에 유지됨.

  • 페이지 폴트를 줄이기 위해 작업 집합이 최적화됨:

    • 페이지 2, 5, 20 등이 작업 집합에 포함.

5. 시간에 따른 작업 집합 변화

  • 오른쪽 그래프:

    • 시간 축에 따라 참조되는 페이지의 수가 안정화.
    • 작업 집합 크기가 점차 수렴하며 효율적인 메모리 활용이 가능해짐.

📌작업 집합 이동

  1. 작업 집합의 이동:

    • 프로세스가 실행되는 동안 작업 집합은 참조 패턴의 변화에 따라 이동함.

    • 새로운 데이터나 코드 영역이 필요할 때 새로운 작업 집합이 형성됨.

  2. 그래프의 구조:

    • 페이지 폴트 발생:

      • 새로운 참조가 발생하여 작업 집합을 적재하는 과정에서 일어남.

    • 작업 집합 형성:

      • 메모리에 필요한 데이터가 적재되며 작업 집합이 안정화됨.

    • 작업 집합의 이동:

      • 시간이 지나며 기존 작업 집합이 메모리에서 제거되고 새로운 작업 집합이 형성됨.

  3. 시간 경과에 따른 안정화:

    • 작업 집합이 안정화된 후에는 페이지 폴트 빈도가 감소.
    • 프로세스가 일정 부분의 메모리만 반복 참조하면서 시스템 성능이 최적화됨.

📌스래싱 발발 원인

  • 작업 집합 모델 활용: 프로세스가 실행되는 동안 참조되는 페이지들의 집합을 작업 집합이라 하며, 메모리에 올릴 수 있는 페이지 범위를 제한함으로써 스래싱 발생 가능성을 분석할 수 있다.

📌스래싱 예방 방법

  • 충분한 메모리 할당: 작업 집합에 포함된 페이지들이 모두 메모리에 적재될 수 있도록 충분한 메모리를 확보한다.

📌요구 페이지의 필수 알고리즘 2개

1. 프레임 할당 (Frame Allocation) 알고리즘

  • 목적: 프로세스에 적절한 수의 프레임을 할당하여 페이지 폴트를 줄이는 것.

  • 기능:

    • 각 프로세스가 사용할 수 있는 프레임 수를 결정.
    • 작업 집합을 수용할 만큼의 프레임을 할당하여 성능 최적화.

2. 페이지 교체 (Page Replacement) 알고리즘

  • 목적: 페이지 폴트가 발생했을 때 교체할 프레임을 선택.
  • 기능:
    • 빈 프레임이 없을 경우, 희생 프레임(비운 프레임)을 결정.
    • 작업 집합에 속하지 않는 페이지를 우선적으로 교체하여 미래에 필요한 페이지는 유지.

10.5 프레임 할당

📌프레임 할당

목표

  • 작업 집합에 포함된 페이지들을 적절하게 메모리에 할당.
  • 페이지 폴트를 줄이고 스래싱을 예방.

2가지 프레임 할당 방법

  1. 균등 할당 (Equal Allocation)

    • 방법: 모든 프로세스에 동일한 개수의 프레임을 할당.

    • 장점:

      • 구현이 단순하여 관리가 쉬움.

    • 단점:

      • 작은 프로세스에서는 프레임이 낭비될 수 있음.
      • 큰 프로세스에서는 부족한 프레임으로 인해 페이지 폴트가 발생할 가능성이 높음.

  2. 비례 할당 (Proportional Allocation)

    • 방법: 프로세스 크기에 비례하여 프레임을 할당.

    • 장점:

      • 전체적으로 페이지 폴트의 수를 줄이는 데 효과적.

    • 단점:

      • 실행 전에 프로세스 크기를 정확히 예측해야 함.
      • 실행 중 작업 집합을 판단하기 어렵고 복잡함 (예: Windows 사례).

📌프로세스에게 할당할 적정 프레임의 개수 - 작업 집합을 약간 넘나드는 크기

그래프 설명

  1. X축: 프로세스에 할당된 프레임 수.

  2. Y축: 페이지 폴트 발생 횟수.

  3. 그래프 해석:

    • 왼쪽 영역 (부족한 프레임 할당):

      • 프로세스에 할당된 프레임이 너무 적을 경우 페이지 폴트가 급격히 증가.
      • 스래싱(Thrashing) 현상이 발생하여 성능이 급격히 저하됨.

    • 중앙 영역 (적정 프레임 할당):

      • 페이지 폴트가 최소화되는 구간.
      • 이 구간이 작업 집합(Working Set)의 크기와 일치.

    • 오른쪽 영역 (과도한 프레임 할당):

      • 프로세스에 너무 많은 프레임이 할당되면 추가적인 성능 향상은 미미.
      • 다른 프로세스에 할당할 메모리가 부족해질 수 있음.

  • 작업 집합(Working Set):

    • 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합.
    • 작업 집합에 필요한 만큼의 프레임을 할당하는 것이 성능 최적화의 핵심.

  • 스래싱(Thrashing):

    • 부족한 프레임 할당으로 인해 페이지 폴트가 지속적으로 발생.
    • 디스크 I/O가 과도하게 증가하여 CPU 활용률이 급격히 감소.

결론

  • 프레임 할당은 작업 집합의 크기를 약간 초과하는 수준이 가장 효율적이다.
  • 부족하거나 과도한 할당 모두 시스템 성능에 부정적인 영향을 미친다.

📌Windows의 프레임 할당(작업 집합 관리) 사례

작업 집합 관리의 어려움

  • 작업 집합 이동: 작업 집합 크기를 정확히 추정하는 것이 어렵다.

  • Windows는 이러한 문제를 해결하기 위해 프로세스 생성 시 최소, 최대 할당 프레임 수를 설정한다.

Windows의 작업 집합 관리 방법

  1. 최소/최대 프레임 수 예약:

    • 최소: Windows 7 기준 최소 50개.
    • 최대: 최대 345개.
    • 이 범위를 워킹셋(Working Set)이라고 부름.

  2. 프로세스 생성 시 처리 방식:

    • 프로세스가 실행되면 최소 워킹셋 수만큼 메모리 할당 시도.
    • 최대 워킹셋을 넘지 않는 선에서 메모리 추가 할당.
    • 가용 메모리가 충분하면 최대치를 초과해서도 메모리 할당.

  3. 작업 집합 정리(Working Set Trimming):

    • 주기적으로 시스템 메모리 사용량 스캔.
    • 일정 수준 이상 메모리가 사용 중이면 워킹셋 크기 축소:
      • 축소된 메모리는 스왑-아웃됨.
      • Windows는 시스템의 가용 메모리 확보가 최우선 목표.

  4. 프로세스 작업 집합 크기 변경 기능:

    • 프로세스는 SetProcessWorkingSetSize(), SetProcessWorkingSetSizeEx()를 통해 자신의 작업 집합 크기를 변경할 수 있음.

10.6 페이지 교체

📌페이지 교체

특징

  1. 페이지 폴트 처리 과정:

    • 페이지 폴트가 발생하면, 페이지 폴트 핸들러가 실행됨.
    • 메모리에서 새로운 페이지를 로드해야 할 경우, 기존에 할당된 프레임 중 하나를 교체해야 함.

  2. 희생 프레임(Victim Frame):

    • 비우기로 선택된 프레임.
    • 새로운 페이지를 적재하기 위해 비워질 프레임.

  3. 희생 페이지(Victim Page):

    • 희생 프레임에 저장되어 있던 페이지.
    • 희생 페이지는 스왑-아웃되며, 필요시 스왑-인됨.

페이지 교체 알고리즘의 목표

  1. 효율적인 페이지 선택:

    • 가깝거나 먼 미래에도 참조되지 않을 페이지를 희생 페이지로 선택.
    • 자주 참조될 페이지는 유지하여 효율을 높임.

  2. 페이지 폴트 횟수 감소:

    • 적절한 페이지 교체를 통해 불필요한 스왑-아웃과 스왑-인을 최소화함.

동작 흐름

  1. 새로운 페이지 요청:
    • 물리 메모리가 부족하면 페이지 폴트 발생.
  2. 희생 페이지 선택:
    • 교체 알고리즘에 따라 희생 프레임 결정.
  3. 스왑-아웃 수행:
    • 기존 희생 페이지를 스왑 영역에 저장.
  4. 요청된 페이지 스왑-인:
    • 요청된 페이지를 희생 프레임에 적재

📌희생 프레임의 선택 범위

1. 지역 교체(Local Replacement)

개념

  • 요청한 프로세스에 할당된 프레임 중에서 희생 프레임을 선택.

  • 프로세스 별로 독립적인 메모리 관리를 수행.

장점

  • 독립성 유지:

    • 스래싱이 다른 프로세스에 영향을 주지 않음.

  • 스래싱 대책:

    • 프로세스별로 메모리 사용량을 제한하여 스래싱에 효과적으로 대응.

  • 효율적 페이지 폴트 처리:

    • 프로세스 내에서 희생 프레임을 선택하여 빠르게 처리 가능.

2. 전역 교체(Global Replacement)

개념

  • 전체 메모리 프레임 중에서 희생 프레임을 선택.
  • 특정 프로세스에 국한되지 않고, 시스템 전체에서 프레임을 공유.

장점

  • 효율성 증대:

    • 지역 교체보다 효율적인 것으로 평가됨.
    • 더 나은 메모리 자원 활용.

  • 광범위 사용:

    • 리눅스, Windows 등 많은 운영체제에서 사용.
    • 시스템 전체의 성능을 고려한 메모리 교체가 가능.

선택의 기준

  • 지역 교체:

    • 프로세스 간 독립성이 중요한 환경에서 사용.
    • 개별 프로세스의 안정성 유지.

  • 전역 교체:

    • 시스템 성능 최적화가 중요한 환경에서 사용.
    • 전체 메모리 자원의 균형적 활용 가능.

📌페이지 교체 알고리즘에 대한 시각 변화

1. 과거: 다중프로그래밍 초기 시대

  • 페이지 교체 알고리즘은 뜨거운 연구 주제.
  • 메모리 자원이 한정적이었고, 교체 전략이 시스템 성능에 미치는 영향이 매우 큼.

2. 최근 컴퓨터 시스템의 구조 변화로 인한 시각 변화

(1) 전역 교체의 실효성 감소

  • RAM의 용량 증가:
    • 희생 프레임을 찾는 과정이 상대적으로 비효율적.
    • RAM 자체의 용량 증가로 인해 교체 필요성 감소.

(2) 캐시의 중요성 부각

  • CPU 캐시 활용이 메모리 자체보다 중요한 이슈로 대두.
  • 데이터 접근 속도를 높이기 위해 캐시 기반 시스템 최적화가 우선.

(3) 참조의 지역성 약화

  • 참조 패턴 변화로 인해 작업 집합이 모호해지는 경향.

    • 객체 지향 언어의 사용:
      • getter/setter 함수 호출이 많아져 여러 페이지를 참조.
    • 비연속적 데이터 구조:
      • 배열 대신 트리, 해시맵, 연결 리스트 등이 사용됨.
      • 메모리 상에서 데이터가 연속적으로 배치되지 않음.
    • 가비지 컬렉션:
      • 자바, 자바스크립트, 파이썬 등에서 메모리 관리 자동화.
      • 메모리 접근 패턴이 과거와 크게 달라짐.

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

1. 최적 교체 (Optimal Page Replacement)

  • 이론적 최적 알고리즘.

  • 가장 먼 미래에 사용될 페이지를 교체 대상으로 선택.

    • 현실적으로 미래의 페이지 사용 패턴을 알 수 없으므로 비현실적.
    • 그러나 다른 알고리즘의 평가 기준으로 사용됨.

2. FIFO (First In, First Out)

  • 가장 오래전에 적재된 페이지를 교체.
  • 구현이 단순하지만, 오래된 페이지라도 자주 사용될 경우 비효율적.

3. LRU (Least Recently Used)

  • 가장 최근에 사용되지 않았던 페이지를 교체.
  • 과거의 사용 패턴이 미래에도 유지된다는 가정 아래 효율적.

4. Clock

  • FIFO와 LRU를 결합한 방식.
    • LRU 구현을 단순화하여 효율적으로 작동.
  • 페이지의 사용 여부를 체크하여 교체할 대상을 선정.

📌최적 페이지 교체 (Optimal Page Replacement)

개념

  • 프로세스당 3개의 프레임이 주어진 상황에서 지역 교체(Local Replacement)를 가정.

  • 미래에 어떤 페이지가 사용될지 안다는 가정 하에 작동.

  • 페이지 요청이 들어올 때 가장 먼 미래에 사용될 페이지를 교체.

예시

  1. 요청 페이지: 0, 1, 2, 0, 3, 0, 1, 2, 3, 0, 2, 1, 0

  2. 초기 상태:

    • 메모리는 비어있음.
    • 페이지 요청마다 메모리 상태가 갱신됨.

  3. 페이지 폴트 발생:

    • 총 페이지 폴트 수: 6회.
    • 교체되는 페이지는 미래에 가장 늦게 사용되는 페이지.

특징

  • 효율성:

    • 최소한의 페이지 폴트를 보장.
    • 이론적으로 최적의 결과를 제공.

  • 한계:

    • 미래의 페이지 요청을 알 수 없으므로 현실적으로 구현 불가능.

📌FIFO (First In, First Out)

개념

  • 가장 오래 전에 적재된 페이지를 먼저 교체하는 방식.

  • 페이지가 적재된 시간을 기준으로 교체 순서를 결정.

예시

  1. 요청 페이지: 0, 1, 2, 0, 3, 0, 1, 2, 3, 0, 2, 1, 0.

  2. 초기 상태:

    • 메모리는 비어있음.
    • 요청된 페이지가 빈 프레임에 적재됨.

  3. 페이지 폴트:

    • 총 페이지 폴트 수: 10회.
    • 오래된 페이지(먼저 들어온 페이지)가 무조건 교체.

장점

  • 구현이 간단하며, 이해하기 쉬움.

  • 페이지 적재 시간만 저장하면 처리 가능.

단점

  • 성능 저하:

    • 오래된 페이지라도 자주 사용되는 경우 교체될 수 있음.
    • Belady’s anomaly가 발생할 가능성 있음(프레임 수가 늘어도 페이지 폴트가 감소하지 않을 수 있음).

📌LRU (Least Recently Used)

개념

  • 가장 최근에 사용되지 않은 페이지를 교체 대상으로 선택하는 알고리즘.

  • 페이지의 참조 시간을 기록하여, 가장 오래 참조되지 않은 페이지를 우선적으로 교체.

예시

  1. 요청 페이지: 0, 1, 2, 0, 3, 0, 1, 2, 3, 0, 2, 1, 0.

  2. 초기 상태:

    • 메모리는 비어있음.
    • 요청된 페이지가 빈 프레임에 적재됨.

  3. 페이지 폴트:

    • 총 페이지 폴트 수: 8회.
    • 가장 오래 참조되지 않은 페이지가 교체됨.

장점

  • 효율적인 성능:
    • 자주 사용되는 페이지는 메모리에 유지되므로 효율적.
    • 실제 사용 패턴을 반영.
  • 다양한 운영체제에서 사용:
    • 많은 운영체제에서 LRU를 기본적으로 채택하거나 변형된 형태로 사용.

단점

  • 구현 복잡성:

    • 페이지 참조 시간을 관리해야 하므로 추가적인 저장 공간 및 연산이 필요.
    • 페이지 참조마다 시간 기록을 갱신해야 하므로 성능에 부담이 될 수 있음.

📌LRU 구현 방법

1. 타임 스탬프 이용

  • 작동 원리:

    • 모든 프레임에 참조 시간을 기록할 수 있는 비트 추가.
    • CPU가 페이지를 참조할 때마다 해당 페이지의 참조 시간을 기록.
    • 교체 알고리즘은 참조 시간이 가장 오래된 페이지를 선택.

  • 장점:

    • 참조 시간 기반으로 정확한 교체 가능.

  • 단점:

    • 시간 기록 및 참조 시간 검사로 인한 오버헤드 발생.
    • 구현 및 유지 관리가 비교적 복잡.

2. 하드웨어 이용 (참조 비트 사용)

  • 작동 원리:

    • 페이지 테이블 항목에 참조 비트 (Reference Bit)를 추가.
    • CPU가 페이지를 참조할 때마다 하드웨어가 자동으로 참조 비트를 1로 설정.
    • 교체 알고리즘은 참조 값이 낮은(0) 페이지를 선택.

  • 특징:

    • 참조 비트는 단순히 1/0만 기록할 수도 있고, 시간 값을 기록할 수도 있음.
    • 주기적으로 참조 비트를 초기화 (0)하여 업데이트.

  • 장점:

    • 하드웨어 지원으로 성능 향상 가능.
    • 비교적 간단하게 구현 가능.

  • 단점:

    • 추가 하드웨어 비용 발생.
    • 페이지 테이블 항목이 증가하여 메모리 소모.

📌참조 비트(Reference Bit)를 사용한 LRU 교체 알고리즘

설명

  1. Ref Bit 초기 상태:

    • 페이지 테이블의 각 항목은 Presence Bit, Dirty Bit, Ref Bit, 그리고 Physical Address로 구성됨.
    • Ref Bit는 각 페이지가 최근에 참조되었는지를 나타냄.
      • 1: 최근에 참조됨.
      • 0: 최근에 참조되지 않음.

  2. Ref Bit 갱신 과정:

    • CPU가 페이지를 참조하면 해당 페이지의 Ref Bit가 1로 설정됨.
    • 주기적으로 운영체제는 모든 Ref Bit를 0으로 초기화하여 새 참조를 감지.
    • 교체 대상 페이지를 선택할 때, Ref Bit가 가장 오랫동안 0인 페이지를 선택.

  3. 페이지 교체 과정:

    • 페이지 폴트 발생 시, 교체할 페이지의 Ref Bit를 확인.
    • Ref Bit가 0인 페이지 중 하나를 선택하여 교체.

  4. 장점 및 단점:

    • 장점:
      • 효율적인 하드웨어 기반 참조.
      • 시간 기록을 생략하여 오버헤드 감소.
    • 단점:
      • 하드웨어 설계 및 추가 비용 발생.

📌Clock 알고리즘 개요

  • FIFO와 LRU를 결합한 알고리즘으로, 2차 기회 알고리즘(second chance algorithm)이라고도 불림.

  • LRU의 효율성과 FIFO의 간단함을 융합한 구조를 가짐.

특징

  1. 프레임당 1비트의 참조 비트(Reference Bit/Used Bit) 사용:

    • 페이지가 참조될 때마다 해당 프레임의 참조 비트를 1로 설정.
    • 참조 비트는 페이지가 최근에 사용되었는지를 나타냄.

  2. 프레임 관리:

    • 모든 프레임을 원형 큐(circular queue) 형태로 연결하여 관리.
    • 참조 비트는 큐의 각 프레임에 하나씩 존재.

페이지 교체 시 희생 프레임 선택 방법

  1. 포인터 사용:

    • 원형 큐에서 교체를 시작할 위치를 가리키는 포인터(pointer)를 사용.
    • 페이지 교체가 필요할 때, 포인터를 따라가며 프레임을 검사.

  2. 참조 비트 확인:

    • 참조 비트가 0이면 해당 프레임을 교체(희생 프레임으로 선택).
    • 참조 비트가 1이면 0으로 바꾸고, 포인터를 다음 프레임으로 이동.

  3. 한 바퀴 회전:

    • 포인터가 큐를 한 바퀴 돌면서 조건을 만족하는 프레임을 찾음.
    • 한 바퀴를 돌아도 교체할 프레임을 못 찾는 경우, 참조 비트가 초기화된 상태에서 다시 검색.

📌 Clock 알고리즘의 동작 사례

(1) 초기 상태: 포인터가 프레임 2를 가리킴

  • 현재 포인터는 원형 큐에서 프레임 2를 가리키고 있다.
  • 각 프레임의 참조 비트는 초기값이 설정되어 있다.

(2) CPU가 프레임 5를 참조

  • 프레임 5의 페이지가 참조되었기 때문에 참조 비트가 0에서 1로 갱신됨.
  • 포인터는 여전히 프레임 2를 가리키고 있음.

(3) 페이지 교체 요청 발생, 프레임 4 선택

  • 페이지 교체가 필요하여 포인터가 시계 방향으로 이동하며 참조 비트를 확인함.
  • 참조 비트가 0인 프레임 4를 희생 프레임으로 선택.
  • 희생 프레임의 기존 페이지를 제거하고 새로운 페이지를 적재.

(4) 다음 페이지 교체 요청 발생, 프레임 7 선택

  • 새로운 페이지 교체 요청으로 포인터가 계속 이동.
  • 참조 비트가 0인 프레임 7을 발견하여 희생 프레임으로 결정.
  • 포인터는 프레임 7 이후로 이동을 준비.

결론

  • 핵심 동작:

    1. 참조 비트가 0인 프레임을 희생 프레임으로 선택.
    2. 참조 비트가 1인 프레임은 0으로 초기화하면서 다음 프레임으로 이동.
    3. 원형 큐를 한 바퀴 돌면서 교체할 프레임을 반드시 찾음.

📌 Clock 알고리즘의 페이지 교체 사례

profile
박소미
이전 포스트

[운영체제] Ch9 페이징 메모리 관리

0개의 댓글