(이전 게시물에 이어서)

2차 기회 알고리즘(Second-Chance Algorithm)

• 참조 비트 사용하고 클록 교체(clock replacement)라고도 함
• 교체될 페이지를 순서대로 조사
  • 참조 비트가 1이면 0으로 세트하고 한 번 더 기회를 줌
  • 참조 비트가 0이면 해당 페이지를 교체
• 순환 큐(circular queue)를 사용하여 구현
  • 포인터(시계의 침)가 다음에 교체될 페이지를 가리킴

개선된 2차 기회 알고리즘 (Enhanced Second-Chance Algorithm)

• (참조비트, 변경비트) 두 개의 비트를 조합하여 등급을 설정
  • (0, 0) 최근에 사용되지도 변경되지도 않은 경우 : 교체하기 가장 좋은 페이지
  • (0, 1) 최근에 사용되지는 않았지만 변경은 된 경우 : 이 페이지가 교체되면 디스크에 내용을 기록해야 하기 때문에 교체에 적당하지 않음
  • (1, 0) 최근에 사용은 되었으나 변경은 되지 않은 경우 : 이 페이지는 곧 다시 사용될 가능성이 높음
  • (1, 1) 최근에 사용도 되었고 변경도 된 경우 : 아마 곧 다시 사용될 것이며 교체되면 역시 디스크에 그 내용을 먼저 기록해야 함
• 페이지 교체가 필요할 때 클록 알고리즘과 같은 방법을 사용
  • 가장 낮은 등급을 가지면서 처음 만난 페이지를 교체

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

• 각 페이지를 참조할 때마다 계수(count)
• LFU (Least Frequently Used) 알고리즘
  • 참조 횟수가 가장 작은 페이지를 교체
  • 프로세스가 초기 단계에서는 한 페이지를 집중적으로 사용 후 다시 사용하지 않은 경우에 판단 틀림 : 참조 횟수를 일정한 시간마다 하나씩 오른쪽으로 이동해서 지수적으로 그 영향력을 감소시켜서 해결
• MFU (Most Frequently User) 알고리즘
  • 가장 작은 참조 횟수를 가진 페이지가 가장 최근 참조된 것이고 앞으로 사용될 것이라는 판단에 근거

페이지-버퍼링 알고리즘 (Page-Buffering Algorithms)

• 페이지 교체 알고리즘과 병행하여 적용
• 가용 프레임 여러 개를 풀(pool)에 저장 (버퍼링)
• 가용 프레임 풀은 유지하면서 프레임의 임자 페이지를 기억할 수도 있음
  • 이 프레임을 재 참조 시 디스크를 읽을 필요 없음
  • 희생될 페이지를 잘못 선정한 경우 유용

🥰 페이지 교체 응용

• 앞의 모든 알고리즘들은 페이지의 향후 사용을 예측하여 동작
• 일부 응용들은 메모리 사용 동작에 대해 많은 지식을 가짐 : DB 응용 등
• 메모리를 많이 사용하는 범용 응용들은 이 중으로 버퍼링
  • OS가 입출력 버퍼 등과 같은 메모리에 페이지를 복사
  • 응용은 자신의 작업을 위해 페이지를 메모리에 유지
• 특수한 응용들을 위해 운영체제는 디스크에 직접 접근하는 수단을 제공
  • raw disk mode (?)
  • 파일 시스템의 요구 페이징, 파일 잠금, 버퍼링 등의 서비스를 우회(bypass)

🦼 프레임의 할당 (Allocation of Frame)

• 각 프로세스에게 할당해야 하는 프레임 수 결정
  • 각 프로세스 당 필요한 최소의 프레임 수는 아키텍처에 의해 결정
  • 각 프로세스 당 최대 할당 프레임 수는 가용물리 메모리에 의해 결정

🦏 할당 알고리즘 (allocation algorithm)

• 균등 할당 (equal allocation)
  • 모든 프로세스에게 똑같이 할당
  • ex) 5개의 프로세스, 93개 프레임 : 18개 씩(18*5=90), 3개의 자유 프레임 버퍼 풀
• 비례 할당 (proportional allocation)
  • 각 프로세스의 크기 비율에 맞추어 할당
• 우선순위 할당 (priority allocation)
  • 비례 할당 방법을 사용하면서 프레임 비율을 프로세스의 크기가 아닌 우선순위를 사용하여 또는 크기와 우선순위의 조합을 사용하여 결정

🌭 전역 대 지역 할당 (Global Versus Local Allocation)

• 전역 교체 (global replacement)
  • 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우
  • 프로세스 실행 시간이 크게 변함
  • 높은 메모리 이용율
• 지역 교체 (local replacement)
  • 각 프로세스가 자기에게 할당된 프레임들 중에서만 교체될 희생자를 선택
  • 일관된 프로세스의 성능
  • 낮은 메모리 이용율

🍱 비균등 메모리 접근 (Non-Uniform Memory Access)

• 위는 모든 주 메모리에 동등하게 접근한다는 가정
• 메모리 접근 시간이 차이가는 NUMA(Non-Uniform Memory Access) 시스템
  • CPU와 메모리가 같은 보드인 경우 접근
  • 시스템 버스로 상호 연결된 메모리에 접근
• 프로세스(스레드)가 실행 중인 CPU에 가장 가까운 메모리 프로세임에 할당하는 것이 최적의 성능
  • 스케줄러가 가능하면 같은 시스템 보드 상에 스레드를 스케줄
  • Solaris lgroup이라는 개체를 생성하여 해결
    • CPU/메모리 지연이 작은 그룹들을 추적
    • 프로세스의 모든 스레드와 메모리 할당을 lgroup 단위로 처리

🚙 스레싱(Thrashing)

• “충분한” 프레임을 할당 받지 목한 프로세스는 빈번한 페이지 부재가 발생하여 다음 상황 초래
  • 낮은 CPU 이용률 (CPU utilization)
  • OS는 새로운 프로세스를 시스템에 더 추가(스왑 인 스왑 아웃)해서 다중 프로그래밍의 정도(degree of multiprogramming)를 높임
  • 다른 프로세스가 시스템에 추가되어 페이지 부재 빈도는 더 높아지고 CPU 이용률은 더 악화
  • 다시 프로세스를 추가 반복 (스왑 인 스왑 아웃 반복)
• 스레싱 (thrashing) : 교체된 페이지가 얼마 지나지 않아 다시 사용되는 반복적인 페이지 부재가 발생하는 상황

💎 요구 페이징과 스레싱

• 요구 페이징(demand paging)은 지역성 모델(locality model)에 기반하여 동작
  • 지역성 모델이란 프로세스가 실행될 때에는 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 의미
  • 지역성(locality)이란, 집중적으로 함께 참조되는 페이지들의 집합을 의미
    • 시간 지역성 : 최근에 참조된 주소의 내용은 곧 다음에 다시 참조되는 특성
    • 공간 지역성 : 대부분의 실제 프로그램이 참조된 주소와 가까운 주소의 내용이 참조되는 특성
    • 순차 지역성 : 데이터가 순차적으로 액세스되는 경향 (공간에 편입되어 설명되기도 함)

• 스레싱 발생 원인
  • 어떤 프로세스가 새로운 지역으로 진입할 때 필요한 크기보다 적은 프레임을 할당하게 되면 페이지 부재가 자주 발생하여 스레싱 유발
• 스레싱 방지
  • 프로세스가 필요하는 최소한의 프레임의 수 보장
  • 작업 집합(working set)방법 사용하여 프로세스가 사용하는 프레임 수 조사

🔒 작업 집합 모델 (Working-Set Model)

• 작업 집합 창(working set window), Δ
  • Δ = 고정된 페이지 참조 횟수
  • 최근 Δ 만큼의 페이지 참조를 관찰
  • 한 프로세스가 최근 Δ번 페이지를 참조했다면 그 안에 들어 있는 서로 다른 페이지들의 집합을 작업 집합(working set, WS) 이라고 함

• 작업 집합의 정확도
  • Δ 값이 너무 작으면 전체 지역성을 포함하지 못함
  • Δ 값이 너무 크면 여러 지역성을 과도하게 수용
  • Δ가 무한히 크면 프로세스가 실행 중에 만난 모든 페이지의 집합 수용
• (모든 프로세스의 전체 프레임 요구량)이 (가용한 총 프레임수) 보다 크면 프로세스 중 하나를 중지하고 그 프로세스의 페이지들을 다른 프로세스에게 할당하여 스레싱 예방

👠 페이지 부재 빈도 (Page-Fault Frequency)

• 페이지 부재 빈도 바식은 보다 더 직접적으로 스레싱을 조절
• 수용 가능한 페이지 부재율(page-fault rate) 설정
  • 페이지 부재율이 상한보다 높음 - 그 프로세스에게 프레임을 더 할당
  • 페이지 부재율이 하한보다 낮음 - 그 프로세스의 프레임 수를 줄임

🪑 메모리 사상 파일 (Memory-Mapped Files)

• 메모리 사상 파일 입출력은 디스크의 블록 메모리 참조로 변환
  • 메모리 내의 페이지와 관련시켜 사상(mapping)
  • 처음 파일 접근 시 요구 페이징으로 페이지 부재가 발생하여 페이지 크기의 파일 부분이 메모리의 물리 페이지로 적재되고, 이 후 파일 읽기/쓰기는 일반 메모리 접근으로 처리
• 파일 read()/write() 시스템 호출 대신 메모리를 통해 파일 입출력을 하기 때문에 파일 접근과 사용을 단순화
• 메모리 내의 페이지들이 공유되어 여러 프로세스들이 같은 파일 사상될 수 있음

• 메모리 사상 파일을 이용한 공유 메모리 : 윈도우 시스템에서는 공유 메모리를 메모리 사상 파일을 이용하여 구현

❎ 커널 메모리의 할당

• 커널 메모리는 사용자 프로세스의 메모리와 다르게 관리
• 커널 메모리는 별도의 메모리 풀(memory pool)에서 할당 받음
  • 커널은 다양한 크기의 자료구조를 위한 메모리를 요청
    • 페이지보다 작은 크기의 자료구조 사용
    • 많은 운영체제들이 커널 코드나 데이터에 페이징을 사용하지 않음
  • 일부 커널 메모리는 연속적인 할당이 필요
    • 물리 메모리에 직접 접근하는 하드웨어 장치

🎢 버디 시스템 (Buddy System)

• 물리적으로 연속된 페이지들로 구성된 고정된 크기의 세그먼트로부터 메모리를 할당
  • 세그먼트에서 2의 거듭제곱의 크기 단위로 할당
  • 2의 거듭제곱이 아닌 메모리 요구는 요구 크기보다 큰 가장 가까운 2의 거듭제곱으로 할당
  • 내부 단편화 가능성

🍪 슬랩 할당

• 슬랩(slab)은 하나 이상의 연속된 페이지들로 구성
• 캐시(cache)는 하나 이상의 슬랩들로 구성
  • 각 커널 자료구조마다 하나의 캐시를 가짐
  • 각 캐시는 커널 자료 구조의 인스턴스로 구성된 객체(object)가 할당
• 슬랩 할당
  • 캐시가 생성되면 초기에 free라고 표시된 객체들이 캐시에 할당
  • 커널 자료구조를 위한 객체가 필요하면 캐시 내의 free 객체 중 하나를 할당하고 used로 표시
  • 슬랩들이 모두 할당되어 사용 중이면 새로운 슬랩들을 할당
• 단편화에 의해 메모리 낭비되고 메모리 요청이 빠르게 처리
  

🦴 참고

• Operating System Concepts, 10th Ed.
• https://itwiki.kr/w/%EC%B0%B8%EC%A1%B0_%EC%A7%80%EC%97%AD%EC%84%B1