1. fetch(메모리로 프로세스와 데이터를 가져오기)

요구페이징

• 메모리 관리의 fetch, placement, replacement 중 fetch에 해당

  • 프로세스가 요청시 메모리로 가져오는 것

    • Cf. 미리 가져오기: 앞으로 필요할 것으로 예상되는 페이지 가져오기(예: 캐시)

      • 미리 가져왔다가 안 쓸 수도 있으니 현대에는 요구 페이징을 기본으로 사용

  • 프로세스의 일부만 가져와서 실행(lazy swapper) → 메모리 효율적 관리, 응답속도 향상

    • lazy swapper (사용자 요구하는 페이지만 메모리에 올림) ↔ swapping: 모든 페이지 올림

페이지 테이블(PTE)

• (페이지번호 +) 플래그비트 + 프레임 번호(=물리 메모리 주소 필드)

  • 플래그 비트(유효 비트)의 구성

    • 접근 비트(=참조비트:페이지가 메모리에 올라온 후 사용한 적 있으면 1, 읽기에 주로 해당)
    • 변경 비트(=더티 비트: 변경된 적 있으면 1, 쓰기)
    • 유효 비트(=현재비트: 스왑 영역에 있으면 1)
    • 읽기 쓰기 실행 비트(메모리에 대한 접근 권한)을 알려줌

페이지 부재(page-fault)

• 요청한 페이지가 메모리에 없을 때(유효비트가 1일 때)
• 스왑영역의 페이지를 비어 있는 프레임으로 스왑 인해서 가져오고 → 페이지 테이블의 유효비트, 프레임 업데이트

• 비어 있는 프레임이 없다면 페이지 교체 알고리즘으로 대상 페이지 victim page(어떤 프레임에 저장된 페이지를 내보낼지) 결정

  • 지역성: 기억장치에 접근하는 패턴에 메모리 전체에 골고루가 아닌 특정 영역에 집중

    • 공간, 시간, 순차적 지연성
    • 페이지 교체 알고리즘은 지역성을 기반으로 판단

2. 페이지 교체 알고리즘

알고리즘

• 다양한 알고리즘 있다.

  • 가장 간단(무작위, FIFO) → 이상적이나 구현 어려움(최적) → 이상에 가깝게 구현(LRU, LFU, NUR 등) → 2차 기회(FIFO변형)
• 무작위: 대상 페이지를 랜덤으로 선정 → 자주 사용하는 페이지가 선정될 수도 있음
• FIFO: queue 사용. but 시간의 지역성 있더라도 오래 전에 들어온 페이지가 자주 사용될 수도 있다.
• 최적: 가장 늦게 사용될 페이지를 선정해서 자리 확보. but 미래 예측 어려움
• LRU: Least Recently Used 현재로부터 가장 오래 전에 접속된 페이지 내보냄

• LFU: Least Frequently Used 현재로부터 가장 덜 사용된 페이지 내보냄

  • LRU, LFU는 예측이 어려운 최적 교체 알고리즘과 달리 과거의 데이터를 기반으로 예측
  • LRU는 시간 혹은 카운터 기록 위해, LFU는 페이지 접근 횟수 표시 위해 추가 공간 필요

• NUR: Not Used page Recently 참조 비트와 변경비트만 추가해서 선정 → 추가 용량 적다

  • (0,0): 페이지에 접근 없음(메모리에 올라온 후 읽혀진 적 없음) , 페이지가 변경된 적 없음 → 가장 우선순위로 선정
  • LRU, LFU, NUR은 성능 비슷하고, 그 중 NUR 가장 많이 사용

• FIFO 변형

  • 2차 기회: Second Change. FIFO처럼 큐 사용하지만, 특정 페이지 접근시 페이지 부재 없이 성공하면 그 페이지를 큐의 맨 뒤로 이동
  • 시계: 원형 큐를 사용하고 스왑영역으로 옮길 페이지를 포인터로 가리킴. 포인터가 큐의 맨 끝으로 가면 다시 처음을 가리킴. 참조비트가 1인 페이지는 건너뜀.

페이지교체의 대상

• 전역 교체 global replacement

  • 모든 프로세스에 NUR알고리즘 적용해서 교체(모든 프로세스 참조비트, 변경비트를 확인)
  • 장점: 가장 쓰인지 오래된 프레임을 제거 가능

• 지역 교체 local replacement

  • 장점: 특정 프로세스와 관련된 프레임만 스왑영역으로 내보내기에 다른 프로세스에 영향 안 미침
  • 단점: 특정 프로세스와 관련된 프레임 중에서만 NUR 알고리즘을 적용 → 자주 사용하는 페이지가 스왑영역으로 옮겨질 수도 있다. → 스레싱 발생 가능

  ⇒ 전체 시스템의 입장에서는 전역 교체 방식이 효율적

3. 스레싱과 프레임 할당

Threshing

• 하드 디스크 입출력 너무 많아짐 → 페이지 부재로 인해 작업이 멈춘 것 같은 상태

  • 멀티프로그래밍 정도 degree of multiprogramming(동시에 실행하는 프로그램의 수)가 너무 높으면 스레싱 발생하고, 그 지점을 threshing point라고 함

    • 즉, 물리 메모리가 (어느 정도까지는) 클수록 threshing point에 느리게 도달
  • 각 프로세스에 프레임을 어떻게 할당하는지도 스레싱과 관련

프레임 할당

• 정적 할당 static allocation: 프로세싱 실행 초기에 프레임 나누어 주고, 크기 고정

  • 균등 할당 equal allocation: 프로세스 크기 관계없이 프레임을 모든 프로세서에게 같게 할당 → 메모리 부재 혹은 낭비 빈번

  • 비례 할당 proportional allocation: 프로세스 크기 비례해서 프레임 할당

    • 작은 프로세스도 많은 메모리를 필요로 할 수 있고, 사용하지 않을 수 있는 메모리에 대해 미리 확보해서 공간 낭비

• 동적 할당 dynaminc alloction: 실행 중의 변화 수용

  • 작업 집합 모델 working set model: 가장 최근에 접근한 프레임이 이후에도 참조될 가능성이 높다 → 그 페이지들의 집합을 만들어서 물리 메모리에 유지

    • 작업집합 윈도우 WSW(작업집합에 포함되는 페이지의 범위)의 크기를 잘 조절 필요
  • 페이지 부재 빈도 page fault frequency: 페이지 부재 횟수를 기반으로 페이지 부재 비율 계산
    → 페이지 부재비율이 상한선 이상이면 할당한 프레임이 적으므로 프레임 늘리고, 부재비율이 하한선 이하이면 메모리 낭비이므로 할당한 프레임 회수

프레임 공유

• 쓰기 시점 복사 copy on write

  • 기존에 있던 것을 복사해서 공유할 수 있는 프레임은 공유
  • 공유할 수 없는 프레임(변수 등)의 메모리는 프로세스가 복사되는 때가 아닌 물리메모리에 write 될 때(새로운 프레임 할당) 복사

출처

• 조성호, 쉽게 배우는 운영체제(한빛아카데미, 2022)