Post

운영체제 - 반효경 9강

Posted
By sunjong0214 10 min read

Demand Paing

  • 실제로 필요할 때 page를 메모리에 올림

  • Valid/Invalid bit 사용

    • Invalid의 의미 : 사용되지 않는 주소 영역, 페이지가 물리적 메모리에 없는 경우

    • 처음에는 모든 entry page가 invalid로 초기화

    • address translation 시에 invalid bit이면 -> page fault

image

Page Fault

  • invalid page를 접근하면 MMU라 trap(page fault)를 발생
  • kernel mode로 들어가서 page fault handler가 invoke됨
  • page fault 처리 순서
    • 잘못된 요청인지 확인 (bad address 등) -> abort 시킴
    • 빈 page frame을 찾음 (없으면 뺏어옴: replace)
    • 해당 page를 disk에서 memory로 읽어옴 (I/O 작업)
    • kernel mode -> 프로세스로 전환되고 다시 running

image

  • Page Fault는 성능에 큰 영향을 미침
  • Page Fault가 얼마나 일어나는가에 따라 시스템의 성능이 좌우됨

Page replacement

  • Free frame이 없는 경우 페이지 프레임에서 자리를 뺏어야 함
  • 어떤 frame을 빼앗아올지 결정해야 함 (곧바로 사용되지 않을 page를 쫓아내야 함)
  • Replacement algorithm
    • page-fault rate를 최소화하는 것이 목표

image

Optimal Algorithm

  • 미래에 어떤 page가 사용되는지 알고 있다고 가정
  • 그렇기 때문에 가장 적은 page fault를 일으킴
  • MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace

image

  • 하지만 미래의 참조를 현실적으로 알 수 없다 (offline algorithm으로 불림)
  • 보통 다른 알고리즘의 성능에 대한 upper bound 제공하는 용도로 사용

FIFO Algorithm

  • 먼저 들어오는 것을 먼저 내쫓음

image

  • FIFO Anomaly : 페이지 프레임(할당 메모리를 높여주면)이 늘어나면 page fault 수가 늘어남

LRU(Least Recently Used) Algorithm

  • 가장 오래 전에 참조된 것을 지움

image

LFU(Least Frequently Used) Algorithm

  • 참조 횟수가 가장 적은 페이지를 지움
    • 참조 횟수가 같을 경우 : 임의로 선정 or 가장 오래전에 참조된 page 지움

LRU / LFU 예제

image

  • LRU : 참조 횟수를 고려하지 않기 때문에 문제
  • LFU : 이제 막 참조를 시작한 4번의 경우 이어서 참조를 계속할 가능성이 있음을 고려 X

LRU / LFU 구현

image

  • LRU : Linked List와 같은 자료구조를 사용해 구현 -> 최근 참조된 것을 끝으로 보내고, 지울 땐 맨 위에 있는 page를 지움
  • LFU : heap으로 구현 -> 지울 때 root에 있는 page 지움(그 뒤 트리 재구성), 새로운 참조 있을 때 트리를 내려가면서 확인

다양한 캐싱 환경

  • 캐싱 기법
    • 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다고 후속 요청시 캐시로부터 직접 받는 방식
    • paging system 외에도 cache memory, buffer caching, web caching 등이 있음
  • 캐시 운영의 시간 제약
    • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 너무 많은 시간이 걸리는 경우 사용 불가능
    • Buffer caching 이나 web caching의 경우 : O(1) ~ O(log n)까지 허용, LRU LFU 사용 가능
    • Paging system인 경우
      • page fault의 경우 OS가 관여
      • 앞서 살펴봤던 알고리즘에 필요한 모든 page의 참조시각 등의 정보를 OS는 모름
      • page fault가 일어났을 때만 OS가 관여하고 나머지 page가 이미 memory에 올라가 있으면 CPU, memory같은 하드웨어 단에서 처리하기 때문(이미 메모리에 올라간 page의 참조 시각은 OS까 알 수 없음)
      • OS는 disk -> memory에 올라간 시점만 알 수 있음
      • LRU이나 LFU 사용 불가능

Clock Algorithm

image

  • Paging system에 사용하는 교체 알고리즘
  • LRU의 근사 알고리즘
  • reference bit을 사용해서 교체 대상 페이지 선정
  • CPU가 page를 사용하게 되면 reference bit을 1로 변경
  • reference bit은 페이지 테이블에 존재
  • reference bit가 0인 것을 찾을 때까지 포인터를 하나 씩 앞으로 이동
  • 포인터가 이동하면서 bit이 1이면 0으로 바꿈

  • reference bit이 0인 것을 발견하면 해당 페이지 교체

  • modified bit(drity bit)
    • reference bit과 홤께 사용
    • 최근에 변경된(write 같은) 페이지를 나타냄(I/O를 동반)
    • write와 같이 데이터가 변경되면 page를 쫓아낼 때 disk에 변경 내역을 반영해야됨 -> 성능 이슈
    • clock algorithm에서 modified bit이 1인 것보다 0인 것을 우선해서 쫓아냄

Page frame의 allocation

  • page allocation 시 각 process에 얼마만크의 page frame을 할당할 것인가에 대한 문제(한정된 page frame을 얼마나 효율적으로 할당할 것인가)
  • Allocation의 필요성
    • 프로세스를 실행하는데 원활히 돌아가기 위한 page frame 수가 있다
    • Loop의 경우 loop를 도는데 필요한 page frame이 3개인데 2개만 할당된 경우 -> loop를 돌 때마다 page fault 발생
  • Allocation Scheme
    • Equal allocation : 모든 프로세스에 똑같이 할당
    • Proportional allocation : 프로세스 크기에 비례해서 할당
    • Priority allocation : priority에 따라 할당

Global VS Local Replacement

  • Global replacement

    • process 별로 할당하지 않고 교체 알고리즘을 통해 관리
    • FIFO, LRU, LFU 등의 알고리즘을 사용해 replace 하다보면 많이 사용하는 프로세스는 frame을 많이, 적게 사용하는 프로세스는 frame 적게 가져가게 됨
    • Working set, PFF 알고리즘 사용

  • Local replacement

    • 프로세스 별로 할당

    • 각 프로세스 별로 교체 알고리즘 운영

Thrashing

  • 프로세스 별로 원할한 수행을 위한 최소한의 page frame을 할당 받지 못한 경우
  • 프로세스를 실행 시 page fault 가 아주 빈번히 일어남

스크린샷 2024-08-27 145306

  • Thrashing 일어나는 시나리오
    1. frame이 적게 할당 -> page fault rate 높아짐
    2. CPU utilization 낮아짐
    3. OS는 MPD(Multiprogramming degree)를 높여야 된다고 판단
    4. 프로세스 늘어남 -> 프로세스 별로 할당되는 frame 수 감소
    5. 모든 프로세스 실행 시 page fault 발생 -> CPU가 놀게 됨
  • 이런 문제 때문에 MPD를 관리해야 함 -> Working-set algorithm, PFF 사용

Working-Set Algorithm

  • 프로세스는 특정 시간 동안 일정 page들만 집중 참조(loop를 도는 등) -> 이 page 집합을 locality set(working-set)이라 함
  • 이 working-set을 최소한으로 보장해줘야 page fault가 잘 안 일어남
  • 만약, 이 working-set을 보장해주지 못한다면(MPD등에 의해) 모든 page frame들을 반납 -> 해당 프로세스는 disk로 swap out(suspend) 됨

image

PFF(Page-Fault Frequency) Scheme

image

  • page-fault rate의 상한값과 하한값을 두고 관리

  • PFF도 working-set algorithm과 같이 빈 frame이 없으면 해당 프로세스를 swap out 함

Page size의 결정

  • Page size를 감소 시키면
    • 페이지 수 증가 -> 페이지 테이블 크기 증가
    • internal fragmentation 감소
    • Disk transfer 효율성 감소 : seek를 여러번 해야 됨
    • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
      • 그런나 Locality 측면에서는 안 좋음
      • 페이지 사이즈가 클 때 page fault가 났다면 disk에서 한번 memory 해당 page를 올리고 나면 그 다음부터는 page fault가 안 남
  • 최근에 트랜드는 Page size를 키움

출처)

[운영체제 - 이화여자대학교KOCW 공개 강의](http://www.kocw.net/home/cview.do?cid=3646706b4347ef09)
CS, OS
cs os
This post is licensed under CC BY 4.0 by the author.