[시구] 가상 메모리

• 가상 메모리(Virtual Memory)
• 메인 메모리보다 큰 기억공간에 주소를 지정할 수 있는 메모리 관리 기법
• 메인 메모리에서 사용자를 논리 메모리를 물리적으로 분리하여, 개발자(사용자)에게 가상 메모리로 제공함.
• 페이징 시스템으로 가상메모리 구현.
• 메인 메모리보다 더 많은 공간 사용으로, 더 많은 작업을 메모리 적제가능
• 사용자(개발자)에게 더 많은 메모리 제공하고, 중첩 문제 해결.
• 프로그램이 동시에 실행되지 않는다는 아이디어에서 시작됨. 
• 장점
• 프로그래밍이 쉬우며, 공간제약이 없으므로 중첩을 작성하지 않아도 됨. 
• 공간이 부족해도 부분적재가 가능하며, 많은 작업을 수 행할 수 있으므로 이용률과 처리율이 향상됨
• 단점
• 메모리와 디스크 사이의 이동량이 증가함에 따라 교체를 위한 공간 필요
• 페이지 적제와 복귀 시점을 결정하기 위한 페이징 알고리즘 필요
• 페이지 부재에 대한 처리 방안 필요함
• 사상(Mapping)
• 가상 주소를 실제 주소로 변환하는 과정이 필요하며, 속도가 느리면 시스템 성능 저하됨.
• 블록 사상(Block Mapping)
• 블록 단위로 처리함(byte, word 단위로 처리하는 경우 주소사상테이블(Address Mapping Table)을 유지하기 위한 정보량이 커짐.
• 사상 정보의 량을 줄이기 위해 블록단위로 처리함.
• 블록은 가상메모리의 분할 단위
• 일정한 크기의 블록은 페이지라고 하며, 이러한 블록화 방법을 페이징 기법이라고 함.
• 다른 크기의 블록은 세그먼트라고 하며, 이러한 블록화 방법을 세그멘테이션 기법이라고 함. 
• 요구 페이징
• 프로그램을 실행하기위해 프로그램의 일부만 메인 메모리에 적재
• 페이지 대치 알고리즘
• FIFO(선입선출)
• 가장 오래된 페이지 부터 대치함
• 벨레디(Belady) 변이 현상 발생(할당 되는 프레임수가 증가되어도 페이지 부재가 증가하는 현상)
• OPT(Optimal replacement : 최적교체)
• 가장 오랫동안 사용하지 않을 페이지 대체
• 미리 예측해야하므로 실현가능성 희박 (비교 연구를 위해 사용됨)
• LRU(Least Recently Used:  최근 최소 사용)
• 알고리즘 구현을 위해 하드웨어 필요
• 프레임(페이지)이 마지막에 사용된 기간을 활용, 계수기, 스택을 사용하는 두가지 방법이 있음.
• 계수기: 페이지 참조시마다 클럭 증가(제일 적은 클럭이 최근 최소 사용)
• 스택 : 페이지가 참조될 때 스택의 Top에 페이지 번호 표시, Top은 최근 사용된 페이지임. 맨 하단에 교체 대상.
• NUR(Not Used Recently)
• 참조비트 사용으로 하드웨어 지원 필요없음.
• LRU(최근 최소 사용)와 유사 기능 수행
• SCR(Second Chance Replacement: 시계 알고리즘, 2차적 기회 대치)
• 페이지가 처음 적재될 때 참조비트 1로 세팅, 참조될 때마다 1로 세팅
• 교체시점에 대상이 1이면 0으로 교체하고 기회를 한번 줌(해당 시점에 0이면 교체, 만약 모든 참조비트가 1이면 FIFO방식으로 교체.
• LFU(Least Frequently Used:최소 사용 빈도수)
• 참조회수가 가장 작은 페이지 대체
• 참조가 많을수록 참조 계수기는 큰값을 가짐.
• 큰 값을 갖는 페이지가 더이상 사용되지 않는 경우에도 남게 됨.
• MFU(Most Frequently Used: 최대 사용 빈도수)
• 가장 많이 사용된 페이지를 대체함
• 가장 작은 계수를 갖는 페이지가 방금 들어온것으로 인식, 사용확률이 가장 높다고 판단하여 대체 페이지 후보에서 제외시킴
• LFU/MFU는 성능이 좋지 않아, 일반적으로 사용하지 않음.
• 페이지 할당 알고리즘
• 단독 사용자 시스템
• 가장 간단한 구조
• 페이지 대체 알고리즘 사용, 사용가능 페이지가 없을때 페이지 부재 해결
• 사용가능 리스트 3개를 확보, 페이지 부재시 사용.
• 동시에 프로그램이 두개이상 존재하므로 여러개의 프로세스에서 프레임 할당방법에 관한 문제 발생
• 최소 프레임 수
• 할당해야할 최소 프레임 수 존재
• 최소 프레임 수는 명령어 구조에 의해 결정됨. 
• 균일과 비례할당 알고리즘
• 균일할당
• 프로세스마다 프레임을 동일하게 나눔
• 페이지 부재, 페이지 낭비 있음
• 비례할당
• 프로세스 크기에 따라 비율로 할당
• 프로세스 정보를 알이야하는 오버헤드 존재함.
• 균일/비례 두가지 방법 모두 할당되는 양이 변하는 구조이며, 우선순위 고려되지 않음.
• 부하제어
• 메인메모리에서 사용할 프로세스 개수 결정
• 현대 운영체제에서는 고정(균일)과 가변(비례)할당 정책을 이용함.
• 프로세스 적재 정책
• 스레싱(Thrashing)
• 페이지 교환이 계속해서 일어나는 현상
• 발생원인 
•  효율성을 위해서 이용률을 감시, 이용률이 떨어지면 새로운 프로세스 도입. 
• 페이지 부재로 프로세스 이용률 감소시, 스레싱이 발생하여 시스템 처리율이 낮아지고, 페이지 부재는 늘어나 유효 메모리 엑세스 시간이 증가되며, 페이지 교체 시간이 낭비됨.
• 스레싱의 예방
• 다중 프로그래밍의 정도를 낮춰야 함.
• 지역교환 알고리즘이나 우선순위교환 알고리즘을 사용하여 제한 할 수 있음
• 지역성(Locality)
• 시간 지역성
• 가까운 미래에 계속 참조될 가능성이 높음
• 공간 지역성
• 한번 어떤 기억장소를 참조하면 이후에 그 근처에 있는 기억장소를 참조할 가능성이 높음
• 작업 설정 모델(Working Set Model)
• 프로그램의 수행과정을 지역성 개념으로 설명하기 위해 데닝이 개발
• 프로세스가 많이 참조하는 페이지 집합을 메모리 공간에 상주시켜 빈번한 페이지 대치 현상을 줄임
• 프로세스의 작업모델을 구성하기 위해 작업 설정의 크기를 알아야하며, 크기는 작업설정 창을 이용하여 구함.
• 최근에 참조된 페이지를 메인 메모리에 상주시켜 프로세스를 빠르게 실행시킬 수 있음.
• 새로운 프로세스는 메인메모리에 작업 설정을 적재할 수 있는 공간이 있을때만 시작할 수 있음.
• 작업 설정 모델의 사용법
• 운영체제는 각 프로세스의 작업설정을 감시, 각 프로세스의 작업설정에 맞게 충분한 프레임을 할당
• 여분의 프레임이 있을 때에는 준비 상태에 있는 프로세스를 불러들여 프레임을 할당해줌으로써 다중 프로그래밍의 정도를 높임. 
• 모든 프로세스가 갖는 작업설정의 크기의 합이 전체 유효 프레임수보다 커지게 되는경우 잠시 중단시킬 프로세스를 선정하여 페이지를 회수.
• 가능한 다중 프로그래밍의 정도를 높이면서 스레싱을 방지 하는 효과를 제공하며, 프로세서의 효율성을 높임
• 정확한 참조 대신, 프로세스의 페이지 부재율에 관심을 갖는 모델로, 프로세스 상주 집합의 크기를 늘리는 만큼 페이지 부재율이 낮아지는 효과를 활용하며, 많은 운영체제에서 사용하고 있음.
• 작업 설정 모델의 문제점
  
• 우선 작업 설정이 갖는 과거의 참조가 미래의 참조를 항상 보장하지는 않음
• 작성 설정의 크기와 구성 페이지는 시간에 따라 변함
• 각 프로세스에 대한 작업설정을 모두 측정하는 것은 현실적으로 불가능
• 작업설정의 프로세스의 변화(추가,삭제)에 따라 변화가 심함
• 작업설정에 의한 메모리 관리가 복잡함
• 작업설정 창의 크기를 나타내는 매개변수의 최적값이 알려져 있지 않고, 프로세스의 성격에 따라 매우 다양함.
• 페이지 부재 빈도(PFF, Page Fault Frequency)
• 스레싱을 예방하는 방법
• 페이지 환경에서 프로세스의 실행 측정 기준
• 페이지 부재가 발생할 때 조절하므로, 작업설정 모델보다 오버헤드가 적음
• (작업설정 모델은 페이지가 메모리에 엑세스할때 조절)
• 스레싱은 페이지 부재로 인해 발생하므로 페이지 부재 비율 조절이 필요함
• 페이지 부재 비율 높음: 프로세스가 더 많은 프레임을 필요로 함
• 페이지 부재 비율 낮음: 프로세스가 너무 많은 프레임을 가지고 있음
• 페이지 부재 빈도 알고리즘은 페이지 참조가 새로운 지역으로 이동하는 과도기에는 제대로 작동하지 않음.
• 기타 고려사항
• 대치 범위
• 여러 프로세스가 제한된 수의 프레임을 사용하므로 할당 기준이 필요함
• 전역대치
• 모든 프로세스를 대상으로 함(리눅스)
• 대형시스템에 이용
• 성능분석이 쉬움
• 지역대치
• 프로세스를 개별적으로 제한(windows XP)
• 구현쉽고 부담적음
• 프리 페이징
• 최초 발생하게 되는, 많은 페이지 부재를 방지하기 위한 기법
• 페이지 크기
• 최적의 페이지 크기 결정
• 페이지 크기 결정시 테이블의 크기를 고려해야함
• 메모리는 크기가 작은 페이지가 이용하기 좋음.
• 내부 단편화를 최소화 하기 위해 크기가 작은 페이지가 필요하며, 한 페이지를 읽거나 기록하는데 소요되는 시간도 중요함.
• 페이지 테이블 구조
• 일반적으로 각 프로세스는 하나의 페이지 테이블을 가짐
• 페이지 테이블 역시 페이징 대상임.
• 전통적인 페이지 테이블
• 각 페이지에 대한 항목을 유지, 가상 주소공간의 크기에 비례하며, 가상 페이지에 의해 색인 과정을 거침.
• 역 페이지 테이블
• 프로세스 전체가 공통으로 사용하는 페이지 테이블
• 메모리 공간을 작게 사용
• 주소변환 시간이 더 오래 걸림
• 해시에 의한 색인이 이루어짐.

용어

• 프레임과 페이지는 메모리를 일정한 크기의 공간으로 나누어 관리하는 단위이며 프레임과 페이지의 크기는 같음.

  • 페이지(Page) : 가상 메모리를 일정된 한 크기로 나눈 블록이다.
  • 프레임(Frame) : 물리 메모리를 일정된 한 크기로 나눈 블록이다.