OS - 9. Virtual Memory(1)

1. 배경

  

 메모리에 프로세스의 프레임이 모드 올라가지 못하여도 프로세스가 동작할 수 있도록 해주는 기술이다. 한 프로세스의 가상 주소 공간은 그 프로세스가 메모리에 저장되는 논리적인 모습을 말한다. 그러나 해당 프로세스의 프레임이 모두 메모리에 올라가 있는 것이 아니라 몇 개만 올라가져있고 가상 메모리 상의 프레임과 맵핑되어 있다.

가상 메모리 내부에서는 스택이 아래로 쌓이며 힙이 위쪽으로 확장한다. 이때 이 공백을 포함하는 가상 주소 공간을 Sparse(성간) 주소 공간이라고 한다. 해당 공간에는 공유 라이브러리도 들어올 수 있다.

2. Demand Paging(요구 페이징)

  

 요구 페이징이란 초기에 필요한 것들만 메모리에 적재하구 이후 필요할때 요구하여 적재한다. 가상 메모리는 대개 요구 페이징 방식으로 구현되며 대개는 하나의 세그먼트가 다시 여러 페이지로 나뉘어진 페이지된 세그먼테이션 기법을 사용한다.

3. Demand Paging - 기본 개념

  

 CPU는 메모리에 존재하는 페이지만 접근을 할 수 있다. 만약 메모리에 없다면 해당 페이지를 디스크에서 메모리로 가져와야한다. 이때 메모리에 해당 페이지가 있다 없다는 페이지 테이블의 vaild-invalid bit로 판단한다. 만약 CPU가 접근하려는 페이지가 vaild이면 바로 접근을 하고 invaild이면 페이지 부재 트랩을 발생 페이지를 디스크에서 가져온다.

 프로그램이 실행되면 운영체제는 명령 포인터의 값을 프로세스의 첫 명령으로 설정한다. 그러나 이 명령은 메모리에 존재하지 않는 페이지에 있고, 페이지 부재가 발생하며 필요 페이지가 모두 올라 올때까지 페이지 부재가 계속 발생한다. 초기에는 아무것도 안 올라와 있기 때문에 페이지 부재가 많이 발생하며 모두 적재가 되면 더 이상 부재가 발생하지 않는다. 이후 요구가 있을 때까지 페이지를 적재하지 않는다. 이를 순수 요구 페이징이라고 한다.

 요구 페이징을 위한 필수적인 요구 사항은 페이지 부재 오류 처리 후에 명령어 처리를 다시 시작할 수 있어야 한다. 만약 3-주소 명령어의 C=A+B를 생각해보자

1. 명령어(ADD) 인출

2. A인출

3. B인출

4. A+B

5. C에 저장

만약 C의 페이지가 메모리에 없다면 해당 페이지를 가져오고 명령을 처음부터 다시 해야한다. 운영체제는 어디까지 되돌아가 가야하는지 생각해야하며 임시 레지스터나 마이크로 코드로 롤벡을 줄일 수 있다.

3. Demand Paging - 성능

  

 실질 접근 시간을 계산하기 위해서는 페이지 부재를 처리하는 시간을 알아야한다.

 EAT = (1-p) x memory access 

+ p{페이지 부재 오버헤드 + 스압 페인지 아웃 + 스압 페이지 인 + restart overhead}

4. Copy on write

  

 fork() 시스템 호출을 통해 프로세스를 생성 할 때에는 페이지 공유로서 첫 요구 페이징 조차 생략이 가능하다.

단 쓰기로 인한 독립적으로 관리되어야 하는 페이지는 메모리에 따로 복사하여 생성한다.

5. 페이지 교체

  

 필요한 페이지가 메모리에 없을 시, 또한 메모리에 새로운 페이지를 올릴 공간이 없을 때 페이지는 교체되어야한다. 희생 페이지 선정은 페이지 교체 알고리즘에 의해 선정되며 효율을 높이기 위해 modify bit와 같이 다양한 방법이 사용된다. 그 외에도 하나의 프로세스에게 몇 개의 페이지를 할당할 것인지에 대해 고려해야한다.

6. FIFO 페이지 교체

  

 말 그대로 먼저들어온 페이지가 먼저 나간다. 이해하기가 쉽지만 성능이 좋지 않다.

위 도표를 봤을때 프로세스에 할당된 프레임의 개수가 3일때 보다 4일때 페이지 부재가 더 많이 발생한다. 이를 Belady의 모순이라 부른다.

7. 최적 페이지 교체 (OPT 알고리즘)

  

 앞으로 가장 오랜 기간 동안 사용되지 않을 페이지를 교체한다. 이페이지 교체 방법은 성능은 좋으나 구현이 어렵다. 앞으로에 대한 요구 페이지를 미리 알아야 하기 때문이다.

8. LRU 페이지 교체

  

 최적 알고리즘이 구현이 불가능하다면 최적 알고리즘의 근사한 알고리즘을 만들면 된다. LRU 알고리즘은 가장 오랜 기간 동안 사용되지 않은 페이지를 교체한다. 오래 되었다라는 정보는 다음 두가지 구현방법으로 구현 가능하다.

1. counter : 각 페이지 항목마다 사용 시간 필드를 넣고 CPU에 논리적인 시계나 계수기를 추가한다. 이 방법은 마지막 참조 시간을 적는 쓰기 작업과 제일 오래된 페이지를 찾는 탐색이 필요하다. 또한 시간값의 overflow도 고려해야한다.

2. stack : 스텍을 이용하여 페이지 번호를 관리한다. 교체시 맨 스텍 맨 아래 있는 것을 올려 빼버리고 참조시 맨위로 올린다. 이것은 MMU가 관리한다.

8. LRU 근사 페이지 교체

  

 LRU 페이지 교체 지원을 충분히 할 수 있는 하드웨어는 거의 없다. 그래서 많은 시스템은 참조 비트의 형태로 LRU와 유사한 알고리즘을 지원한다.

1. Additional-Reference Bits Algorithm : 각 페이지에 대해 8비트의 참조 비트를 할당한다. 일정 시간마다 타이머 인터럽트를 걸어 오른쪽으로 shift를 한후 참조비트를 맨 왼쪽에 넣는다. 참조 비트의 수는 달라질 수 있으며 극단적인 경우 하나의 bit로 구분한다. 이것이 2차 기회 알고즘이다.  

2. Second-Chance Algorithm : 2차 기회 알고리즘의 기본은 FIFO 교체 알고리즘이다. 그러나 페이지가 선택될 때마다 참조비트를 확인한다. 이때 참조 비트가 0이면 페이지를 교체하고 1이면 0으로 바꾸고 맨 뒤로 간다. 

3. Enhanced Second Chance Algorithm : reference bit 뿐만 아니라 bit를 하나 추가하여 modify bit도 비교한다.

1. (0, 0) : 사용도 변경도 안된 페이지

2. (0, 1) : 사용은 안됬지만 변경은 된 페이지, 교체시 저장해야함

3. (1, 0) : 사용은 됬지만 변경은 안 된 페이지

4. (1, 1) : 사용도 변경도 된 페이지

2와 3은 시스템에 따라 우선순위가 변경된다.

9. Counting Based Page Replacement

  

 1. LFU Algorithm : 카운트를 두어 참조 회수가 가장 적은 페이지를 교체하는 방법이다. 이 방법은 초기에 많이 사용되고 뒤에 사용안될 시 계속 페이지 테이블에 남아 있는것이 문제점이다. 이는 쉬프트로 처리하면 된다.

2. MFU Algorithm : 가장 많은 참조 회수를 가진 페이지를 교체하는 방법이다. 참조 회수가 적으면 최근에 교체된 페이지라고 판단하여 유지한다.

10. Page-Buffering Algorithm

  

 페이지 부재가 발생하면 가용 프레임 풀은 디스크에서 해당 프레임을 가져옵니다. 프레임 풀이 페이지를 가져오는 동안 교체될 프레임은 디스크에 기록되고 있습니다. 이후 기록이 완료되면 자유 프레임 풀에 있는 교체 프레임과 교체합니다.

11. Applications and Page replacement

  

  페이지 교체 정책은 환경에 따라 달라야 한다.

1. 데이터 베이스 : 자체적인 메모리 관리와 입출력 버퍼링을 수행하고 있는 데이터 베이스를 다룰 때 운영체제가 페이지-버퍼링 알고리즘을 쓰면 입출력에 대한 메모리 사용이 2번 사용된다.

2. 데이터 웨어하우스 : 연속적인 읽기가 끝난 후 계산과 쓰기 작업을 하는 데이터 웨어하우스는 오래된 페이지를 내보내려는 MFU가 최신에 들어온 페이지를 내보내는 LRU보다 더 효율적이다.

위 같은 이유로 특수한 저장 장치 서비스를 구현하는데는 해당 저장 장치가 알아서 관리하도록 운영체제에게 메모리를 따로 요청한다. 이를 raw disk mode라고 한다.