[운영체제] 가상 메모리, 프레임 할당 알고리즘

기말 레포트 제출기한 6/10일

프로그래머의 입장에서는 물리 메모리와 가상메모리 모두 "하나의 논리 주소 공간에서 작업한다" 라고 생각하고 쓰면된다.
-> 나누어서 생각할 필요가 없다는 뜻


* 가상 메모리 관리 기법의 성공적으로 우녕 가능한 이유
 1. 실제적으로 모든 프로그램이 항상 동시에 사용되지 않음

* 장점
 1. 프로그래밍 작업이 쉬우며, 공간의 제약이 없으므로 중첩을 작성할 필요가 없음
 2. 공간이 부족해도 부분적재가 가능하여 많은 작업을 실행할 수 있어 프로세서의 이용률과 처리율 향상

* 단점
 1. 메모리와 디스크 공간 사이의 이동량 증가에 따른 교체 공간의 확보
 2. 어느 시기에 어느 페이를 적재하고 다시 복귀시킬 것인가에 대한 페이징 알고리즘의 결정
 3. 페이지 부재에 대한 처리 방안 요구


* 주의 점
 1. 실행 중인 프로세스의 참조 주소와 메인메모리에서 사용하는 주소가 분리되어야 한다.
  1) 사상(매핑) : 가상 주소를 실제 물리적 주소로 변환하는 과정
   - 변환 함수로 표현하며 소고가 느리면 시스템 성능이 떨어짐
  2) 프로그램 주소 공간(가상주소)을 V, 메인 메모리 공간(실제주소)을 R이라 할 경우 사상(F) 에 대해
     F(함수) :V->R     || 가상 주소(V)와 실제주소(R)의 분리


* 동적 주소 변환 기법

* 메인 메모리 공유를 위한 메모리 관리  기법 활용

---------
* 블록 사상
 1. 블록 단위로 처리
  1) 매핑이 byte, word 단위로 이루어질 경우 주소 매핑 테이블 유지를 위한 정보량이 커짐
  2) 이를 줄이기 위해 주소를 블록 단위로 처리
 2. 블록 가상 시스템(페이징방식, 세그먼트 방식) 은 2차원적 주소체계를 가짐
   가상주소 V = (b,d)  b: 블록 번호,  d : 블록 시작점으로부터의 변위(페이지,세그먼트)

*가상 주소와 테이블 항목
 1. 가상주소는 순서를 가지는 쌍 v=(p,d)표시, 페이지 번호와 페이지 변위로 구성

 2. 페이지 테이블 항목 구성
  1) 제어비트와 프레임 번호로 구성


* 요구 페이징 기법
 1. 스왑 기법을 사용하는 페이징 시스템과 비슷
  1) 프로그램을 실행하기 위해 프로그램의 일부만을 메인 메모리에 적재

* 요구 페이징 기본 개념
 1. 타당(물리적 메모리에 있음)-비타당(디스크의 가상 메모리에 있음)을 나타내는 bit를 페이지 테이블의 각 항목에 추가함
 2. 비타당 비트 i
  1) 프로그램이 i 에 엑세스 않으면 실행에 영향 없음
  2) 엑세스하면 페이지 부재로 OS에서 트랩 발생
 3. 페이지 부재

 4. 순수 요구 페이징
  1) 요구가 있을 때까지 페이지를 메모리에 들여놓지 않는 방법
   (1) 메모리에 실행할 프로세스의 페이지가 없어도 프로세스는 수행을 시작할 수 있음
   (2) 프로세스는 최초의 명령으로 페이지 부재를 일으킴
   (3) 페이지가 메모리로 들어온 후, 프로세스는 수행을 계속하면서 수행에 필요한 모든 페이지가 메모리에 적재될 때까지 필요할 때마다 페이지 부재를 발생시킴
   (4) 수행에 필요한 모든 페이지가 메모리에 적재되면 프로세스는 더 이상 페이지 부재를 발생시키지 않고 수행을 계속함

  2) 장단점
   (1) 장점
    1> 다중 프로그래밍의 정도를 증가, 메모리 절약
    2> 로딩 지연이 적음
    3> 초기 디스크 오버헤드가 적음
    4> 페이징에 필요한 별도의 하드웨어 지원 불필요함 
    5> 적재된 페이지들 중 하나가 수정될 때까지 페이지들은 여러 프로그램에 의해 공유되므로 이 때는 많은 자원 절약 가능
    6> 적은 메모리의 시스템에서도 대용량 프로그램 실행 가능, 오버레이 기법보다 구현이 쉬움

   (2) 단점
    1> 개별 프로그램들은 페이지에 처음 엑세스 할때 약간의 지연(페이지 부재 처리)가 발생
    2> 프리 페이징은 마지막으로 수행한 몇개의 페이지를 미리 불러오는 방법으로 성능을 향상 시킴
    3> 낮은 비용, 낮은 성능의 시스템에 실행되는 프로그램은 페이지 대체를 지원하는 메모리 관리 장치가 없음
    4> 메모리 관리(페이지 교체)가 복잡함


* 페이지 성능
 1. 요구 페이지된 메모리의 유효엑세스시간
 2. 페이지 부재 시간
 3. 유효엑세스 시간 감속 
  1) 유효엑세스시간은 페이지 부재율이 비례
  2) 유효엑세스시간을 10%미만으로 감속, 메모리 엑세스시간을 220ns보다 적게 유지하기 위한 조건
 % 페이지 부재율이 높을 경우 유효엑세스시간이 증가, 프로세스 수행시간이 늦어짐.
 % 대부분의 페이지가 처음 참조될 때 부재가 발생하고 이후에는 메모리에 저장되어 있어 페이지 부재율이 발생하지 않을 수 있음
 % 메모리에 올라온 페이지의 수가 많을 수록 부재율이 감소함


* 페이지 대치
 1. 페이지 대치의 필요성 
  1) 비어있는 프레임이 없어 더이상 배치할 수 없을 때
 2. 페이지 대치 기법
  1) 페이지 방식을 취하는 가상 메모리에서 페이지 부재 발생 시 메인 메모리에 있으면서 사용되지 않는 페이지를 없애고 새로운 페이지로 변경
  2) 엑세스 순서
   (1) 비어있는 프레임이 없다면 현재 미사용의 프레임(희생자)를 선택. 프레임을 가지고 있다면 프레임 내요의 내용을 디스크에 저장
   (2)
   (3)
   (4)
  3) 프로그램에 의해 빈 프레임은 부재된 페이지 수용을 위해 사용됨
  4) 페이지 부재 서비스 루틴은 페이지 대치를 포함하도록 수정됨
  5) 페이지 대치 과정
   (1) 디스크에서 요구한 페이지의 위치 확인
   (2) 빈프레임 검색
    1> 빈프레임이 발견되면 빈 프레임 사용
    2> 발견 안되면 희생 프레임 선정을 위해 대치 알고리즘 사용
    3> 희생 페이지는 디스크로 이동, 페이지와 테이블을 수정하여 invalid 상태(사용 가능 영역)로 변경
   (3) 요구된 페이지를 읽어 들이고 페이지와 프레임 테이블 수정(v: 사용중)
   (4) 사용자 프로세스 시작
  6) 페이지 부재로 인한 대치 과정은 부재 처리 시간이 증가하므로 엑세스 시간 증가 -> 시스템에 부담
   (1) 페이지 두개가 이동(입/출)
   (2) 수정된 비트를 활용하여 부담을 감소 ???
  7)


03. 페이지 대치 알고리즘
* 페이지 부재와 프레임 개수 - 프레임 개수가 늘면 부재는 줄어듬 (반비례 관계)
*FIFO(큐형) 대치 알고리즘
 1. 각 페이지가 메모리 안으로 들어간 시간을 이용
  1) 가장 오래된 페이지부터 우선 대치(삭제)
  2) 부재 발생 시, 제거할 페이지 선택 후 디스크로 이동 교체시키고 페이지 테이블의 v/i 비트를 변경
  3) 새로운 페이지에 대한 페이지 테이블 항목 변경후 FIFO큐의 마지막 위치에 삽입

 2. FIFO 큐에 의해 메모리의 모든 페이지가 관리 됨
  1) 큐의 헤드부분에 있는 페이지를 먼저 대치
  2) 새로 삽입될 때는 큐 끝에 삽입
  3) 큐의 크기는 사용 가능한 메모리 프레임의 수에 해당됨
  % 알고리즘이 쉽고 작성도 쉬움

 3. 문제점
  1) 할당되는 프레임 수가 증가해도 페이지 부재율이 증가하는 현상

* 최적(Optimal) 페이지 대치 알고리즘
 1. 모든 알고리즘 중 페이지 부재율이 가장 낮음
  1) '앞으로 가장 오랜 기간 동안 사용하지 않을 페이지를 대치하라' 는 매핑을 표현
  2) 고정된 프레임 수에 대해 가능한 가장 낮은 페이지 부재율이 보장됨
 % 현실적인 구현이 어려우며, 비교 연구를 위해 주로 사용됨
   - 참조 문자열이 언제 사용될 것인가에 대한 정확한 정보를 요구함

* 최근 최소사용(LRU) 알고리즘
 1. 과거의 데이터를 이용, 미래를 예측하기 위한 통계적 개념
% 알고리즘 구현을 위해 하드웨어 지원이 필요
% 프레임(페이지) 이 마지막에 사용된 기간을 이용, 정의되는 순서 결정을 위해 계수기 또는 스택을 사용하는 두가지 방법으로 구현 가능함

 2. 계수기를 이용한 순서 결정 방법
  1) 각 페이지 테이블 항목과 사용시간 레지스터를 연관, 프로세서에 논리 클록이나 계수기를 덧붙여 프레임의 순서 결정
  2) 클록 레지스터의 내용은 페이지의 해당 페이지 테이블에 있는 사용시간 레지스터에 복사되어 각페이지의 최소 참조에 대한 시간을 가짐
  3) 페이지 탐색과 페이지 테이블의 변화 과정을 유지해야 하는 부담을 고려해야 함.

 3. 스택을 이용한 순서 결정 방법
  1) 순서 결정을 위해 페이지 번호를 스택에 넣어 관리
  2) 


* 최근 최소사용 근접 알고리즘
 1. 시스템은 하드웨어의 지원 대신 참조비트(Reference Bit)의 형태로 지원
 2. 부가된 참조비트 알고리즘
 3. 숫자가 작은 것은 오랫동안 사용되지 않았음을 의미하므로 대치 우선순위가 높음을 나타냄
 4. 작은 정수값을 프레임이 두 개 이상 있는 경우 희생자 선정 시점에서 문제 발생
  - 희생자를 선정하지 않는 경우는 문제 없음
  - 가장 작은 정수값을 갖는 프레임 모두를 희생자로 선택


* 시계  (2차적 기회 대치) 알고리즘
 1. FIFO 대치 알고리즘을 기반으로 함
 2. LRU 알고리즘과 성능은 비슷하나 과부하가 적음
 3.

* 최소사용 빈도수(LFU) 알고리즘
 1. 각페이지마다 참조 횟수에 대한 계수기가 있으며, 가작 작은 수를 가진 페이지를 대치함
  1) 많이 사용되는 페이지는 큰 잠조 횟수 값을 가짐
  2) 어떤 프로세스의 초기 단계에서 한 페이지가 많이 사용되나 그 후로 다시 사용되지 않을 경우 사용하기 어려움
   (1) 큰 계수를 가진 페이지가 더 이상 필요하지 않아도 메모리에 남음
   (2) 계수기를 일정 시간 간격으로 하나씩 오른쪽으로 이동(2진 비트이동), 지수적으로 감소하는 평균 사용수를 형성하여 해결 가능함

* 최대 사용 빈도수(MFU)
 1. 가장 작은 계수를 가직 페이지가 방금 들어온 것으로 아직 사용되지 않아, 앞으로 사용할 확률이 높다 가정하여 대치 페이지 후보에서 재외시킴
 2. 가장 많이 사용된 페이지(계수가 높은 페이지)를 대치함
 % LFU, MFU는 구현시 비용이 많이 들고 최적 페이지 대치에 비해 성능이 떨어져 일반적으로 사용되지 않음

* 페이지 버퍼링
 1. FIFO같은 성능 저하를 막기 위해 교체 대상으로 선택된 페이지를 즉시 교체하지 않고 잠시 동안 메인 메모리에 유지
 2. 포인터 리스트 두개를 이용, 페이지를 관리하며, 페이지 대치 알고리즘은 FIFO임.


* 알고리즘의 비교 분석
 1. 배르(BAER, 1980) 발표
  1) 적은 수의 프레임을 사용할 경우 차이가 크게 나타남
 2. 부재발생 수 :  선입선출  > 시계 > LRU(최근 최소 사용) > OPT(최적페이지)  순으로 느림