가상메모리(2)

<요구 페이징의 필수 알고리즘>
- 성능에 크게 영향을 미침
  - 프레임 할당 알고리즘
    - 프로세스 당 할당할 frame의 개수를 결정
      - 프로세스의 작업 집합에 포함될 page들을 수용할만한 개수의 frame을 할당하여 페이지 부재를 줄일 수 있도록

  - 페이지 교체 알고리즘
    - 페이지 부재가 발생했으나 빈 frame이 없는 경우 비울 frame을 결정
      - 작업 집합에 속하지 않은 page가 담긴 frame을 선택해서 미래에 사용될 page가 교체되지 않도록 유지




<최소 page frame의 수>
- 각 프로세스 마다 실행에 필요한 최소 page frame수가 확보되어야 한다
  - Frame수 감소시 page fault rate 증가
  - Page fault 발생 시 instruction cycle의 재실행 필요

- 한 instruction이 참조하는 모든 page는 동시에 메모리에 적재되어 있어야 한다
  - 여러 page에 걸쳐있는 instruction/data
  - 메모리 간접참조





<할당할 적정 프레임 개수>
- 작업 집합을 약간 넘나드는 크기 정도 할당

<프레임의 할당(Allocation of Frame)>
- 프로세스 당 frame 수
  - 최소 frame 수
    - 컴퓨터(instruction set)구조에 좌우됨
    - 한 명령어 수행위해 참조하는 모든 페이지를 수용할 수 있는 충분한 수의 프레임 존재 필요

  - 최대 frame 수
    - 가용 메모리 용량에 의해 좌우됨






<할당 알고리즘(Allocation Algorithm)>
- 균등 할당(Equal allocation)
  - 모든 프로세스들에게 같은 수의 frame을 할당
  - 작은 size의 프로세스에게는 과할당 발생가능

- 비례 할당(Proportional allocation)
  - 각 프로세스의 크기에 비례하여 할당

- 우선순위 할당(Priority Allocation)
  - 각 프로세스의 우선순위에 따라 할당
  - 더 높은 우선순위의 프로세스가 더 빨리 수행토록




<참고 : 할당해야 할 최소 프레임의 수>
- 한 명령이 처리되는데 필요한 페이지수 
  - CPU 명령어의 주소 모드(addressing mode)에 좌우




<참고 : MS-윈도의 프레임 할당 예>
- 작업 집합의 이동으로 프로세스의 작업 집합 크기를 정확히 파악하기는 어려움
- 윈도는 프로세스 생성시 최소/최대 할당 프레임 수를 정함
  - 윈도 7에서는 최소 50개, 최대 345개
    - 워킹셋(working set)이라 부름

- 프로세스 생성 시 
  - 최소/최대 워킹셋 수가 예약됨
  - 프로세스가 실행되면, 페이지 폴트 시 최수 수까지 메모리 할당할 수 있도록 노력
  - 기본적으로는 최대 수를 넘어서는 메모리 할당은 불허
    - 가용 메모리가 충분한 경우 큰 프로세스의 최대치를 증가

- 주기적으로
  - 워킹셋 트리밍 알고리즘(working set trimming algorithm)으로 시스템 메모리 사용량 스캔
  - 일정 수준 이상 메모리가 사용되면 프로세스들의 워킹셋을 줄임(스왑-아웃 시킴)
    - 가용 메모리를 확보할 때까지 계속됨





<윈도의 작업 관리자>
- 메모리에 적재된 페이지의 크기를 나타냄
  - 현재 프로세스의 워킹셋이라 부름
    - 프로세스의 전체 크기가 아님
    - 프로세스의 모든 페이지가 적재된 것도 아님





<가용 frame이 부족하다면?>
- 프로세스의 일부 page를 디스크로부터 가져올 때 free frame이 없다면?

- 메모리에 적재된 page들 중 일부를 swap area로 swap out 해야함
  - Page fault 서비스 루틴에 페이지 교체 알고리즘을 포함시켜 메모리의 과할당 방지
    - Page fault를 최소화 할 수 있는 알고리즘은?!
  - Modify-bit(혹은 dirty-bit)를 사용하여 변경된 page만 swap-out





<페이지 교체(Page Replacement)>
- 메모리 frame 중 하나를 선택해 비우고, 이곳에 요청된 page를 적재하는 과정
  - 페이지 폴트 핸들러에서 실행되는 작업
  - 희생 페이지는 스왑-아웃, 요청 페이지는 스왑-인
    - 희생 프레임(victim frame) : 비우기로 선택된 frame
    - 희생 페이지(victim page) : 희생 frame에 들어 있는 page

  - 현재 작업 집합에 포함되지 않거나 가까운 미래에 참조되지 않을 page를 희생 page로 선택
    - 페이지 부재 횟수를 줄임

<기본적인 페이지 교체>
1. 디스크에서 필요한 page의 위치를 파악
2. Free frame을 찾음
  - Free frame이 있으면 그곳을 사용
  - 없으면 페이지 교체 알고리즘으로 희생될 frame(victim frame)선정
  - (필요시)Victim frame을 디스크에 기록

3. Page를 디스크로부터 읽어 frame에 저장
  - page/frame table 수정

4. 프로세스 재실행






<지역 교체와 전역 교체>
- 지역 교체(Local replacement)
  - 각 프로세스는 자신이 사용중인 frame들 중에서만 교체 대상 frame을 선정
  - 각 프로세스는 할당된 frame수 불변
    - 잘 안쓰는 frame이 낭비

- 전역 교체(Global replacement)
  - 전체 frame 중에서 교체 대상 frame을 선정
  - 각 프로세스에 할당된 frame수가 변할 수 있음
    - 다른 프로세스의 frame을 뺏어올 수도 있음
  - 각 프로세스는 자신이 page fault rate 조절 불가
    - 같이 수행되는 다른 프로세스에 의해 영향받음 





<페이지 교체 알고리즘>
- 낮은 page fault rate이 요구됨

- 성능 평가
  - 임의의 메모리 참조열(reference string)에 대해 알고리즘을 적용하여 page fault 회수 계산
    - reference string
      - 난수를 통한 임의 생성하거나 메모리 접근 기록을 로깅
  - 가정
    - frame 수 : 3개
    - reference string 
      - 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1





<Page fault 횟수 vs. frame 수> 

<페이지 교체 알고리즘의 종류>
- FIFO
- Optimal Algorithm(MIN)
- LRU(Least Recently Used) Algorithm
- LRU Approximation Algorithm
- CLOCK(FINUFO : First-In-Not-Used-First-Out)
- Counting Algorithm
  - LFU(Least Frequently Used) Algorithm
  - MFU(Maximal Frequently Used) Algorithm
- LIFO(Last-In-First-Out) Algorithm
- Random Algorithm






<FIFO 페이지 교체>
- First-In-First-Out
- 가장 오래된 page frame을 교체
  - 각 frame은 메모리에 적재되는 순서(시간)에 따라 순번이 매겨짐
  - FIFO 큐 이용
- 가장 간단하며 구현이 용이





<FIFO Illustrating Belady's Anomaly>

<Optimal Algorithm(MIN Algorithm)>
- 최적 페이지 교체 알고리즘
- Belady에 의해 제안
- 앞으로 가장 오랫동안 사용되지 않을 page frame을 교체
- page fault 횟수를 최소화 함
- 비현실적
  - 향후 프로그램 수행 예측은 불가능하기에
- 다른 교체 알고리즘들의 성능 비교를 위한 기준으로 사용






<Optimal Algorithm의 예>

<최근 최소사용 알고리즘, LRU(Least Recently Used) Algorithm)>
- 가장 오랫동안 상되지 않은 page frame을 교체 
  - 오랫동안 미사용 = 앞으로도 미사용
- 일반적으로 좋은 성능
  - Belady 모순 현상이 나타나지 않음
- 각 page frame마다 마지막 사용 기간 유지
- Age counter 혹은 LRU 스택으로 구현
  - 잦은 메모리 조작 발생
  - TLB 같은 하드웨어 지원 필요





<LRU Algorithm의 구현_1>
- Age Counter 사용
- 각 page frame마다 하나의 counter 설정
- 각 page frame이 참조될 때마다 참조 시간을 해당 pgae frame의 counter에 복사
- 교체 시 각 page frame의 counter를 보고 가장 오래 전에 참조된 frame 선택
- Page table에 접근이 필요
  - LRU 교체 page를 찾기 위해
  - 매 메모리 참조시 마다 counter 갱신 위해





<LRU Algorithm의 예>

<LRU Algorithm의 구현_2>
-  Strack에 page 번호 유지
- 최근에 참조된 page 번호를 스택의 top에 위치 시킴
  - 교체 대상이 되는 page는 스택의 bottom에서 얻음
  - 교체 대상을 찾기 위한 검색 불필요

- 이중 연결 리스트로 스택 구현
  - 스택 중간에서 항목 제거 위해





<스택을 위한 page 참조의 기록>

<LRU 근접 알고리즘(LRU Approximation Algorithm)>
- LRU page 교체 지원을 충분히 할 수 있는 하드웨어는 거의 없음
  -> 일반적으로 reference bit(참조 비트) 형태로 어느 정도만 지원

- Reference bit
  - 각 page 마다 할당, 초기에 OS에 의해 reset
  - 해당 page의 참조가 발생하면 set
=> 정확한 사용 순서는 알 수 없지만, 각 page의 참조 여부는 확인 가능






<부가된 참조 비트 알고리즘(Additional Reference Bit Algorithm)>
- 일정 시간 간격마다 참조 비트를 기록하여 대략적인 선후 관계를 알 수 있게 함
  - 타이머 인터럽트와 우측 쉬프트 레지시터 이용
  - 참조비트가 가장 작은 수의 페이지를 교체

- ex) 각 page마다 8bit의 참조 비트를 할당
  - 0000 0000 : 한 번도 참조 안됨
  - 1111 1111 : 각 간격마다 1번 이상씩 참조됨
  - 1100 0110(최근 사용) > 0111 0111(교체 대상)
    - 교체대상 중 FIFO 적용하여 선택 가능





<2차-기회 알고리즘(Second-Chance Algorithm)>
- Clock Algorithm
- FINUFO(First-In-Not-Used-First-Out) Algorithm
- 기본은 FIFO 알고리즘 + page 선택시 마다 참조 비트 확인
  - 참조 비트 0 : 바로 교체
  - 참조 비트 1 : reset 후 한 번 더 기회 제공
- 순환 큐와 포인터(P)를 이용하여 구현
  - ex)
if USE(*P) = 1 then
  - USE(*P) = 0; P = P+1 until finding USE(*P)=0;
  - REPLACE(*P); P = P+1;
else /*USE(*P)=0*/
  - REPLACE(*P) and P = P+1;





<2차 기회 알고리즘의 예>

<Enhanced Second-Chance Algorithm>
- Second-Chance Algorithm + (참조/변경 비트)
  - page 선택시 마다 등급 확인
    - 디스크 입출력 회수 고려

<Counting Algorithms>
- 각 page frame의 참조 회수를 counter에 유지
- LFU(Least Frequently Used) Algorithm
  - 가장 작은 count 값을 가진 page 교체
    - 적게 참조한 page는 참조될 가능성이 적다 가정

- MFU(Maximal Frequently Used) Algorithm
  - 가장 큰 count 값을 가진 page를 교체
    - 많이 참조한 page는 충분히 사용했다 가정
    - 가장 작은 count 값을 가진 page는 적재된지 얼마 되지 않아 더 사용할 가능성이 있따 가정