가상 메모리 관리

가상 메모리

• 분산 메모리 할당(Non-continuous allocation)에서 사용하는 메모리
• 페이징/세그먼테이션 시스템

가상 메모리 관리의 목적

• 시스템 성능 최적화
  • cost model을 만들어 성능을 측정하여 최적화함.
  • 그 외 다양한 기법이 있음.

cost model의 측정 방법

• 페이지 부재 발생 빈도(Page fault frequency)
• 페이지 부재 발생률(Page fault rate)

페이지 부재가 발생하면 문맥교환이 생기므로 오버헤드가 커짐.
페이지 부재 발생률을 최소화 하도록 전략을 설계해야 함.

페이지 부재 발생률을 구하는 방법

• 페이지 참조 문자열(Page reference string)을 만듦.
  • 참조한 페이지 번호가 순서대로 적혀있음
• 페이지 부재 발생률 = 페이지 부재 횟수/총 페이지 개수

가상 메모리 하드웨어 구성

주소 변환 장치(Address translation device)

• 주소 변환을 효율적으로 하기 위해 사용
• TLB(분산메모리 연관 사상에서 사용하는 테이블), 캐시 메모리 등

Bit Vectors

• 페이지 프레임이 모두 꽉 찼을 때 다음 페이지가 어디에 들어가야 할지 기준이 필요함. 그러기위해 각 페이지 프레임에 들어간 페이지 별로 정보가 필요함.
• 페이지 사용 상황에 대한 정보를 기록하는 비트들

참조 비트(Reference bits)

• 메모리에 적재된 페이지가 최근에 참조되었는지 여부를 표시.
• '최근' 참조 여부가 기준이기 때문에 주기적으로 모든 참조 비트를 0으로 초기화 함.
• 즉, 참조 비트를 통해 최근에 참조된 페이지들을 알 수 있음.

갱신 비트(Update bits,modified bits,write bits,dirty bits)

• 페이지가 메모리에 적재된 후 프로세스에 의해 수정 여부를 표시.
• 수정이 되었으면 swap device의 데이터와 메모리상에 데이터가 달라지기 때문에, 이 비트를 확인하여 페이지가 메모리에서 나갈 때 swap device에 데이터를 업데이트 할지를 정함.
• 주기적 초기화 없음. 즉, 메모리에서 페이지가 나갈 때 갱신 비트를 초기화 해주면 됨.

가상 메모리 소프트웨어 구성

할당 전략(Allocation Strategies)

각 프로세스에게 메모리를 얼만큼 할당할 것인가?

고정 할당(Fixed allocation)

• 프로세스의 실행 동안 고정된 크기의 메모리 할당.
• 즉, 할당할 페이지 프레임 개수를 정하는 것.

가변 할당(Variable allocation)

• 프로세스 실행 동안 할당하는 메모리의 크기가 유동적.
• 즉, 할당할 페이지 프레임 개수를 정하지 않는 것.

고려 사항

• 프로세스 실행에 필요한 메모리 양을 예측해야함.
• 너무 큰 메모리를 할당하면 메모리가 낭비됨.
• 너무 작은 메모리를 할당하면 페이지 부재 발생률이 커져 시스템 성능 저하.

적재 전략(Fetch Strategies)

특정 페이지를 메모리에 언제 적재할 것인가?

요구 패치(Demand fetch, Demand pageing)

• 프로세스가 해당 페이지를 요구할 때 적재
• 페이지 부재로 인한 오버헤드가 생김
• 대부분 시스템이 사용하는 전략

예측 패치(Anticipatory fetch, pre-paging)

• 참조될 가능성이 높은 페이지를 미리 예측하여 적재
• 예측 성공 시, 페이지 부재에 대한 오버헤드가 없음
• 예측하기 위한 오버헤드 발생
• 잘못된 예측 시 자원 낭비가 심함

배치 전략(Placement Strategies)

페이지/세그먼트를 어디에 적재할 것인가?

• 페이징 시스템에서는 페이지 프레임의 크기가 일정하므로 불필요.
• 세그먼트 시스템에서 배치 기법은 이전 글에 정리되어있음.
  (first-fit, best-fit, worst-fit, next-fit)

교체 전략(Replacement Strategies)

빈 프레임이 없는 경우 새로운 페이지를 어떤 페이지와 교체 할 것인가?

Fixed allocation을 위한 교체 기법

고정된 프레임 개수

• Min Algorithm(OPT algorithm)
  • 가장 좋은, 최적의 해결책
  • 앞으로 가장 오랫동안 참조되지 않을 페이지를 교체하는 기법
  • 그러나 다음에 어떤 페이지가 참조될 지 알고있어야하므로 실현이 불가능함.
  • 교체 기법의 성능 평가 도구로 사용됨.
    이 알고리즘 성능에 가장 가까운 알고리즘이 좋은 알고리즘이 됨.
• Random Algorithm
  • 무작위로 교체할 페이지 선택
  • 오버헤드가 적음
  • 교체 기법의 성능 평가 도구로 사용됨.
    이 알고리즘 보다 안 좋으면 쓸모없는 알고리즘.
• FIFO Algorithm
  • 가장 오래된 페이지를 교체
  • 자주 사용되는 페이지가 교체 될 가능성이 높음
  • 페이지가 적재된 시간을 기억하고 있어야 함
  • 자원을 늘렸는데 성능은 줄어드는 현상이 발생할 수 있음(FIFO anomaly)
    왜냐하면 locality를 생각하지 않았기때문
• LRU(Least Recently Used) Algorithm
  • 가장 오랫동안 참조되지 않은 페이지를 교체(locality를 활용함)
  • 페이지 참조 시 마다 시간을 기록해야함(오버헤드 발생)
  • MIN Algorithm에 근접한 성능을 보여줌
  • 실제로 가장 많이 활용되는 기법
  • 루프(for문)을 실행 할 때 필요한 크기보다 작은 수의 페이지 프레임이 할당 된 경우, 페이지 부재가 급격히 증가함.
    (1,2,3) -> (4,2,3) -> (4,1,3) -> (4,1,2) ... 계속 페이지 부재가 발생함
• LFU(Least Frequently Used) Algorithm
  • 가장 참조 횟수가 적은 페이지를 교체(locality를 활용)
  • 페이지 참조 시마다 참조 횟수를 누적 시켜야함
  • 적게 참조 되었지만 다음에 참조될 가능성이 높은 페이지가 교체될 가능성이 존재
• NUR(Not Used Recently) Algorithm
  • 최근 참조 되지 않은 페이지를 교체
  • 횟수를 기록해야하는 LRU보다 적은 오버헤드로 비슷한 성능 달성이 목적
  • Bit vector를 사용함.
    Reference bit가 1이면 최근 사용했다는 의미, Update bit가 1이면 최근 수정이 일어났다는 의미.
• Clock Algorithm
  • NUR 알고리즘을 실제로 구현한 알고리즘
  • Reference bit만 사용하고, 주기적인 초기화는 하지않음
  • 포인터(시계침)가 한번 지나간 페이지의 Reference bit를 초기화함(1->0)
  • 시계처럼 페이지 프레임들을 순차적을 가리키는 포인터를 사용하여 교체될 페이지 결정.
  • FIFO와 유사하게 먼저 적재된 페이지가 교체될 가능성이 높음
  • Reference bit를 사용하기 때문에 locality를 활용함.
    
• Second Chance Algorithm
  • clock algorithm과 유사
  • Reference bit와 update bit 둘 다 고려

Variable allocation을 위한 교체 기법

유동적인 프레임 개수

• Working Set Algorithm
  • 프로세스가 특정 시점(locality)에 자주 참조하는 페이지들의 집합을 메모리에 올림
  • 시간에 따라 워킹셋이 변함
  • 자주 참조하는 페이지들을 메모리에 올리니 페이지 부재가 감소하여 시스템 성능 향상
  • 워킹 셋을 관리하는 오버헤드
  • 페이지 부재가 일어나지 않아도 워킹 셋을 변경 시킬 수 있음
• Page Fault Frequency Algorithm
  • 페이지 부재 비율이 낮으면 할당하는 페이지 프레임 개수를 감소
  • 페이지 부재 비율이 높으면 할당하는 페이지 프레임 개수를 증가
  • 현재 페이지 부재 시간에서 이전 페이지 부재 시간을 뺌
  • ws 알고리즘은 페이지 부재가 발생하지 않아도 계속 업데이트가 되어 부하가 생겼음
    그래서 그 단점을 보완하려고 이 알고리즘은 페이지 부재가 발생시에만 수행함(낮은 오버헤드)
• Variable MIN Algorithm
  • 가장 좋은, 최적의 해결책
  • 평균 메모리 할당량과 페이지 부재 발생 횟수 모두 고려함
  • 다음에 어떤 페이지가 참조될지 알고있어야하므로 실현 불가능한 기법
  • 특정 시간동안 어떤 페이지 r 이 다시 참조되는지 확인.
    참조가 되면 페이지 유지, 참조가 안되면 메모리에서 내림

정리 기법(Cleaning Strategies)

변경된 페이지를 언제 스왑 디바이스에 저장할 것인가?(wirte-back)

요구 정리(Demand cleaning)

• 해당 페이지가 메모리에서 내려올 때 write-back
• 대부분 시스템이 사용하는 기법

예측 정리(pre-cleaning)

• 더 이상 변경될 가능성이 없다고 판단 할 때, 즉, 읽기만 계속할 것 같을 때, 미리 write-back
• 페이지 교체 시 발생하는 write-back 시간 절약.
• 예측 실패로 write-back을 했는데 내용이 수정되면 오버헤드가 발생

부하 제어 전략(Load Control Strategies)

• 시스템의 프로세스 수를 조절.
• 적정 수준의 프로세스 수를 유지해야함.
• 저부하 상태
  • 처리할 수 있는 수보다 프로세스 수가 적을 때
  • 시스템 자원 낭비
• 고부하 상태
  • 처리할 수 있는 수보다 프로세스 수가 많을 때
  • 자원에 대한 경쟁 심화, 성능 저하
  • 과도한 페이지 부재가 발생하는 스레싱(Thrashing) 현상이 발생

페이지 크기