(운영체제,OS) 가상메모리-2

Page Fault 

• 프로세스가 메모리에 올라와 있지 않는 페이지를 접근하려고 하면 페이지 부재트랩을 발생시킨다.
• 순수 페이징 요구 – 어떤 페이지가 필요해지기 전에는 결코 그 페이지를 메모리로 적재하지 않는 방법
•  참조 지역성 – 프로그램의 어느 한 특정 작은 부분만 한동안 집중적으로 참조 요구 페이징은 만족할 만한 성능을 보인다.

 

 

1. 페이지 테이블 : 유 무 비트 또는 보호 비트의 특수값이용해서 설정할 수 있어야 한다

2. 보조 기억장치 : 주 메모리에 없는 모든 페이지들을 가지고 있다. 디스크 영역을 스왑장치 스왑공간이라고 한다.

 

페이지 부재율 p 0<=p<=1

p가 0이면 페이지 부재율이 없음

p가 1이면 페이지 모두가 부재

Effective Access Time(EAT) =(1-p)xmemory access+px페이지 부재시간

 

Memory access time=200 nanoseconds

Average page-fault sevice time= 8milliseconds

EAT=(1-p)*200+p*(8,000,000)

1000개의 access에 1개의 page default가 발생했다면 EAT=8.2 microseconds

컴퓨터는 요구 페이지 때문에 40배나 느려지는 것이다.

 

만약 성능 저하를 10% 이내로 낮추고 싶다면 다음 조건이 필요

220 > 200 + 7,999,800 x p

20 > 7,999,800 x p

p < .0000025

< one page fault in every 400,000 memory accesses

 

페이징으로 인해 느려지는 것을 제한하기 위해서는 399,990 번중 1번 이하의 페이지 부재가 발생해야 한다.

 

 요구페이징의 또 다른 특성중 하나는 스왑 공간의 관리이다. 

 스왑공간에서의 디스크 입출력은 일반적으로 파일 시스템에서의 입출력보다 빠른데 그 이유는 스왑 공간은 파일 시스템보다 더 큰 블록을 사용하고, 또 스왑 공간과 입출력을 할 때는 파일 탐색이나 간접 할당 방법 등은 사용하지 않기 때문이다. 

 그러므로 시스템은 프로세스를 시작시킬 때 그 파일 이미지 전체를 스왑 공간으로 복사한 후 스왑 공간으로부터 요구 페이징을 처리함으로써 보다 나은 페이징 처리율을 얻을 수 있다. 또는 페이지들이 교체될 때는 스왑 공간에 페이지를 기록하는 것

 

어떤 시스템들은 실행파일(binary file)을 스왑 공간에 넣지 않음으로써 스왑 공간의 크기를 줄이기도 한다. Solaris and current BSD

 

Copy-on-write(COW)

 

• 부모 와 자식 프로세스를 메모리의 같은 페이지에 공유함
• 만일 프로세스가 공유된 페이지에 수정 된다면 그 페이지만 복사를 한다.
• 자식 프로세스가 시작할 때 부모페이지를 당분간 함께 사용하도록 한다.
• COW는 수정된 페이지가 복사함에 따라 효율적인 프로세스를 생성을 허락한다.

 

 

• COW 처리 과정에서 페이지 복사본을 만들 때 빈 페이지를 어떻게 할당받는지 중요하다
• 많은 운영체제에서 그러한 요구를 처리하기 위한 빈 페이지 집합을 유지하고 있다.
• 빈 페이지가 프로세스에게 할당 되는 겨우는 COW복사 할 때, 그리고 스택이나 힙 공간을 확장 해야 할 때이다. 운영체제는 보통 0으로 채우기(Zero-fill-on-demand)기법으로 페이지를 할당한다. 페이지를 할당 할 때 그 내용을 전부 0으로 채워 이전 내용을 지우게 된다.

 

• vfork()를 하면 부모 프로세스는 보류되고 자식이 부모의 주소 공간의 페이지를 수정하게 되면 변경된 페이지가 재 실행시 부모 프로세스에 그대로 보여진다.
• vfork()할 경우 자식이 부모의 주소 공간의 페이지들에 변경을 가하지 않도록 주의해야함.
• 페이지가 전혀 복사되지 않으므로 매우 효율적

 

 

proccess 1이 페이지 C를 수정한 후.

 

 

 

 

 

page replacement

• 페이지 교체는 빈 프레임이 없다면 현재 사용되고 있지 않은 프레임을 찾아서 그것을 비운다. 
• 그 프레임의 내용을 스왑 공간에 쓰고 그 페이지가 메모리에 더 이상 존재하지 않는다는 것을 나타내기 위해 페이지 테이블을 수정하여 프레임을 빈 상태로 만든다.
• 비워진 프레임을 프로세스가 페이지 부재를 일으킨 페이지를 저장하기 위해 사용할 수 있다.

 

빈 프레임이 없는 경우 디스크를 2번 읽어야 한다. 

 이 상황에서 페이지 부재 처리 시간(page fault service time)이 2배 소요되며, 실질 접근 시간도 증가한다.

 

-> 이러한 오버헤드는 비트변경(modify bit 또는 dirty bit)를 사용해서 감소시킬 수 있다.

각 페이지나 프레임은 자신과 관련된 변경 비트를 하드웨어에 갖게 된다. 변경 비트는 CPU가 페이지 내의 어떤 워드나 바이트라도 쓰게 되면 페이지가 변경되었음을 나타내기 위해 설정

 

요구 페이징 시스템은 두 가지 중요한 문제를 해결

frame-allocation 알고리즘 : 

• 각 프로세스에 얼마나 많은 프레임을 할당해야 하는지
• 어떤 페이지를 교체해야 할지

 

page-replacement 알고리즘 : 

• 성능은 특정 메모리 참조 나열에 대해 알고리즘을 적용하여 페이지 부재 발생 회수를 계산하여 평가.
• 처음 접근과 재접근에 페이지 부재율이 낮은 것
•  

 

 

 

 

FIFO교체

• 각 페이지마다 메모리에 적재된 시간을 기억한다. 어떤 페이지를 교체해야 할 때 메모리에 오라온 기간이 가장 오래된 페이지를 내쫒는다. 페이지들이 올라온 순서를 큐를 만들어 유지하고 있어도 된다. 큐의 머리 부분을 페이지를 교체 새로 올라온 것을 큐의 끝에 삽입.

 

Balady`s Anomaly(모순) : 프레임을 추가하면 더욱더 페이지 부재가 발생한다.

 

Optimal Page Relacement(최적 페이지 교체)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하라.
• 페이지가 고정된 경우 가장 낮은 페이지 부재율을 보장한다. 연구목적 사용

 

LRU page Remlacement

• FIO와 OPT의 차이는 FIFO 알고리즘이 페이지가 메모리로 들어온 시간을 이용하는데 비해 OPT알고리즘은 페이지가 사용될 시간을 이용한다는 것이다.
• 각각의 페이지에 마지막 사용된 시간을 연결한다.
• 페이지 교체 시 LRU는 가장 오랫동안 사용되지 않은 페이지를 선택한다. 과거시간 적용

 

Counter implementation

• 모든 page entry는 카운터를 가지고 있다. 매패이지 시간은 entry를 참조하고 카운터의 시간 정보를 복사한다. 각 페이지의 마지막 참조 시간을 유지할 수 있다.
• 페이지 변화가 필요할 때 카운터의 값을 찾아 시간 값이 작은 페이지가 교체된다.

 

Stack implementation

• 스택에 페이지 번호를 유지한다. 페이지 참조( 스택 꼭대기로 이동) 바닥은 가장 오랫동안 이용되지 않는 페이지이다. 업데이트 비용이 많이 들지 않는다. 교체가 일어날 경우 페이지를 탐새갈 필요가 없게된다. 
• LRU와 OPT는 모순이 일어나지 않으므로 stack algorithms 으로 부른다.

 

LRU 근사 페이지 교체

• Additional-Reference Bits Algorithm
• 일정한 주기로 참조 비트들을 기록함으로써 추가적인 선후 관계 정보를 얻을 수 있다.
• 8비트 시프트 레지스터는 가장 최근 8구간 동안 페이지의 사용 기록을 담고 있다
• 최근 사용 11000100 > 01110111

 

Second-chance algorithm

• 페이지가 선택 될 때마다 참조 비트를 확인한다. 참조비트가 0이면 페이지를 교체하고, 1이면 다시 한 번 기회를 주고 다음 FIFO페이지를 선택하기 위해 이동한다.
• 순환 큐를 이용. 다음 교체될 페이지를 가르킨다. 프레임이 필요해지면 ,포인터는 참조 비트가 0인 페이지를 발견할 때까지 포인터를 전진한다. 포인터가 전진하면서 참조비트 0으로 바꾼다. 희생 페이지가 발견되면 페이지는 교체되고 새로운 페이지가 순환 큐 해당위치에 삽입.

 

개선된 2차 기회 알고리즘

• 0,0 최근에 사용되지고 변경되지도 않은 경우 교체하기 가장 좋은 페이지
• 0,1 최근에 사용되지 않았지만 변경이 된 경우 페이지는 뺏오 오려면 디스크에 내용을 기록해 야하기 때문에 교체에 적당하지 않음
• 1,0 최근에 사용은 되었으나 변경은 되지 않은 경우 페이지는 곧 다시 사용될 가능성 높음
• 1,1 최근에 사용되었고 아마 곧 다시 사용되고 교체시키려면 디스크에 내용을 기록해야함.

 

1. LFU Algorithm : (Least Frequently Used) 참조 회수가 가장 작은 페이지를 교체하는 방법
2. MFU Algorithm :（Most Frequently Used) 가장 작은 참조 회수를 가진 페이지가 가장 최근에 메모리로 적재되었고, 앞으로 계속 사용될 것이라는 판단에 근거.

 

Page-Buffering Algorithm

• 자유 프레임의 pool을 유지한다.
• Then frame available when needed, not found at fault time
• Read page into free frame and select victim to evict and add to free pool
• When convenient, evict victim
• 변경된 페이지 리스트를 유지하는 방법이 있다. 페이징 장치가 유휴 상태일 때마다 변경된 페이지들을 선택하여 디스크에 쓴 후에 페이지의 변경 비트를 0으로 되돌려 놓는다.