정보처리기사/프로그래밍 언어 활용

운영체제 7

RangA 2023. 5. 31. 14:59

03. 기억 장치 관리

04. 주기억 장치 관리 전략

1) 주기억 장치 관리 전략의 종류

  1. 반입(Fetch) 전략
    • 프로그램/데이터를 주기억 장치로 가져오는 시기를 결정하는 전력
    • 요구 반입(Demand Fetch)
      • 새로 반입된 데이터나 프로그램을 주기억 장치에 언제 위치 시킬 것인가를 결정하는 방법
    • 예상 반입(Anticipatory Fetch)
      • 앞으로 요구될 가능성이 큰 데이터 또는 프로그램을 예상하여 주기억 장치로 미리 옮기는 방법
  2. 배치(Placement) 전략
    • 프로그램/데이터를 주기억 장치 내의 어디로 위치 시킬 것인가를 결정하는 전략
    • 최초적합, 최적적합, 최악적합이 있음
  3. 교체(Replacement) 전략(= 페이지 교체 알고리즘)
    • 주기억 장치 내의 빈 공간 확보를 위해 제거할 프로그램/데이터를 선택하는 전략
    • 당장 필요한 페이지와 교체할 페이지를 선택하는 전략

2) 배치(Placement) 전략

1. 최초 적합(First Fit)

  • 입력된 작업을 주기억 장치 내에서 그 작업을 수용할 수 있는 첫 번째 공백에 배치함
  • 초기 결정력이 가장 빠름
  • 운영체제 다음부터가 시작점
  • 처음부터 순차적으로 검색하여 적재될 수 있는 공백이면 배치함

2. 최적 적합(Best Fit)

  • 입력된 작업을 주기억 장치 내의 공백 중에서 그 작업에 가장 잘 맞는 공백에 배치함
  • 내부 단편화가 가장 작거나 없는 공백에 배치함
  • 가장 잘 맞는 공백을 찾아야 하므로 결정력이 느림

3. 최악 적합(Worst Fit)

  • 입력된 작업을 주기억 장치 내에서 가장 잘 맞지 않는 공백, 즉 가장 큰 공백에 배치함
  • 내부 단편화가 가장 큰 공백에 배치함
  • 가장 잘 맞지 않는 공백을 찾아야 하므로 결정력이 느림

3) 교체(Replacement) 전략

1. 교체 전력(페이지 교체 알고리즘)

  • 주기억 장치에 적재된 페이지들을 대상으로 새롭게 적재될 페이지와 교체할 페이지를 선택하는 전략
  • 당장 적재할 페이지가 주기억 장치 내의 페이지 프레임에 있으면 성공(Hit) 되었다고 함
  • 당장 적재할 페이지가 주기억 장치 내의 페이지 프레임에 없으면 실패 혹은 페이지 부재(Page Fault)가 되었다고 함
  • 페이지 적중률(Hit Ratio)이 높도록 교체 전략을 선택해야 함
    • 페이지 적중률 = 성공(Hit) 수 / 페이지 참조 수
  • 효율적인 교체 전략은 프로그램의 실행 속도를 향상시킴

2. 교체 전략의 종류

  • 최적화, FIFO, LRU, LFU, NUR, Second Chance, PFF 등이 있음

4) 최적화(OPTtimal replacement) - 교체 전략

  • 앞으로 가장 오랫동안 사용되지 않을 페이지와 교체함
  • 앞으로 사용할 페이지를 미리 확인하여 교체하는 방법
  • 실제 알고리즘에서는 미리 확인할 수 없음
  • Belady의 알고리즘으로 이상적이지만 실현 가능성이 희박함
  • 페이지 부재의 횟수가 가장 적으므로 페이지 적중률이 가장 높음

5) FIFO(First In First Out) - 교체 전략

  • 주기억 장치 내에 가장 오래 있던 페이지와 교체함
  • 각 페이지가 주기억 장치에 적재될 때마다 그떄의 시간을 기억시켜 두고, 주기억 장치 내에 가장 오래 있었던 페이지를 교체함
  • 알고리즘이 가장 간단함
  • 페이지 부재가 가장 많이 발생함
  • Belady 모둔이 발생함
    • 프로세스에 할당된 페이지 프레임 수가 증가하면 페이지 부재의 수가 감소하는 것이 당연하지만 페이지 프레임 수가 증가할 때, 현실적으로 페이지 부재가 더 증가하는 모순 현상

6) LRU(Least Recently Used) - 교체 전략

  • 페이지 대체 알고리즘에서 계수기(시간 기억 영역)를 두어 가장 오랫동안 사용(참조)하지 않은 페이지를 교체할 페이지로 선택하는 방법
  • 사용(참조된)한 지 가장 오래된 페이지를 대상으로 교체함
  • 현시점에서 가장 오랫동안 사용하지 않은 페이지와 교체함

7) LFU(Least Frequently Used) - 교체 전략

  • 사용(참조된)한 횟수가 가장 적은 페이지와 교체함
  • 사용한 횟수를 기억할 참조 변수를 페이지마다 갖게 하여 사용할 때마다 1씩 증가함

8) NUR(Not Used Recently) - 교체 전략

  • 최근에 호출하지도 사용하지도 않은 페이지를 제거함
  • 두 개의 하드웨어 비트인 참조 비트(Referenced Bit)와 변형 비트(Modified Bit)를 사용
  • 참조 비트가 0이면 오래전에 호출, 1이면 최근에 호출한 것
  • 변형 비트가 0이면 오래전에 사용, 1이면 최근에 사용한 것
  • 참조 비트와 변형 비트는 주기적으로 갱신됨

9) Second Chance와 PFF - 교체 전략

1. Second Chance(이차 기회)

  • 가장 오래된 페이지가 최근에 사용할 가능성이 클 것이라는 가정 하에 가장 오래된 페이지는 교체 대상에서 제외하고 사용한 것으로 취급함
  • 각 페이지에 프레임을 FIFO 순으로 유지하면서 LRU와 근사 알고리즘으로 참조 변수를 갖게 함
  • FIFO의 2차 기회 부여 방법

2. PFF(Page Fault Frequency)

  • 워킹 셋에 존재하는 페이지들을 관찰하여 최근에 자주 사용되고 있지 않은 페이지와 워킹 셋에 속하지 않은 페이지 중에 자주 사용하는 페이지와 교체함
저작자표시 비영리 변경금지