[CS] 운영체제 - 가상 메모리

가상 메모리의 기법은 전적으로 운영체제가 관리하고 있다.

 

Demand Paging

실제로 필요할 때 page를 메모리에 올리는 것을 말한다.

이렇게하면 I/O 양의 감소, Memory의 사용량 감소, 빠른 응답 시간, 더 많은 사용자 수용 등의 효과를 얻는다.
Valid / Invaild bit를 사용한다.
Invalid는 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우를 말한다.
처음에는 모든 page entry가 invalid로 초기화되고 주소 변환 시에 invalid bit이 설정되어 있다면 page fault라는 현상이 발생한다.

 

Page fault

invalid page를 접근하면 MMU가 trap을 발생시킨다. (page fault trap 이라고 불린다.)
kernel mode로 들어가서 page fault handler가 실행된다.
아래와 같은 순서로 page fault를 처리한다.

1. 잘못된 요청인지를 판단한다. 잘못된 요청이라면 => abort 시킨다.
2. 비어있는 page 프레임을 가져온다. (page replace)
3. 해당 page를 디스크에서 memory로 읽어온다.
   1. disk I/O가 끝나기까지 이 프로세스는 CPU를 뺏긴다.
   2. disk를 읽는 작업이 끝나면 page tables entry를 기록한다.
   3. ready queue에 프로세스를 넣는다.
4. 이 프로세스가 다시 CPU를 잡고 메모리 주소변환을 한다.
5. 중단되었던 작업을 재개한다.

대부분의 경우는 page fault가 나지 않는다.

 

Free frame이 없는 경우

page replacement

어떤 frame을 뺐어올지 결정해야 한다.
곧바로 사용되지 않을 page를 쫓아내는 것이 좋다. 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올수 있기 때문이다.

replacement algorithm

page-fault rate를 최소화하는 것이 목표이다.
Optimal algorithm

• 페이지 레퍼런스를 알고 있다는 가정하의 알고리즘이다. (누가 먼저 참조될지)
• 실제로 사용될 수는 없고 다른 알고리즘의 성능에 대한 참고로 제공된다.
• MIN: 가장 먼 미래에 참조되는 page를 replace

FIFO 알고리즘: 먼저 들어온 것을 먼저 내쫓는 알고리즘이다.
LRU (Least Recently Used) 알고리즘: 가장 오래 전에 참조된 것을 지우는 알고리즘이며, 가장 많이 쓰이는 알고리즘이다.
LFU 알고리즘: 참조 횟수가 가장 적은 페이지를 지운다. 최저 참조 횟수인 page가 여러개 있는 경우 임의로 선정한다. (성능 향상을 위해서 가장 오래전 참조된 page를 지우게 구현이 가능하다.)

 

다양한 캐싱 환경

캐싱 기법이란 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청시에 캐시로부터 직접 서비스하는 방식을 말한다.
paging system 외에도 캐시메모리, 버퍼 캐싱, 웹 캐싱등 다양한 분야에서 사용된다.
캐시 운영의 시간 제약

• 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.
• 버퍼 캐시나 웹 캐싱의 경우는 O(1)에서 O(log n)정도만 허용을 한다.
• paging system인 경우 page fault인 경우에만 OS가 관여한다.

 

Clock 알고리즘

LRU의 근사 알고리즘이다.
여러 명칭으로 불린다. Second Chance 알고리즘 이나 NUR (Not Used Recently) 또는 NRU (Not Recently Used)라고도 불린다.
Reference bit을 사용해서 교체 대상 페이지를 선정한다.
reference bit이 0인 것을 찾을 때까지 포인터를 앞으로 하나씩 이동한다.
포인터를 이동하는 중에 reference bit이 1이면 전부 0으로 바꾼다.
reference bit이 0인 것을 찾으면 그 페이지를 교체한다.
한 바퀴 돌아와서(second chance)도 0이면 그때는 교체한다.
자주 사용되는 페이지라면 한바퀴 돌아와서도 올 때 1로 세팅한다.
Clock 알고리즘의 개선방법

• reference bit과 modified bit(dirty bit)을 함께 사용하는 방법이있다.
• reference bit이 1일때 최근에 참조된 페이지이며 최근에 변경된 페이지라면 modified bit를 1로 세팅해서 두개 다 보는 방식으로 개선할 수 있다.

page frame의 allocation

allocation의 필요성

• 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 page를 동시에 참조한다. 명령어 수행을 위해서 최소한 할당되어야 하는 frame의 수가 있기 때문이다.
• 반복을 구성하는 page들은 한꺼번에 allocation 되는 것이 유리하다. 최소한의 allocation이 없으면 매 반복마다 page fault가 나기 때문이다.

allocation의 방법

• equal allocation: 모든 프로세스에 동일한 갯수의 page frame을 할당하는 방법이다.
• proportional allocation: 프로세스 크기에 비례하여 할당하는 방법이다.
• priority allocation: CPU 우선순위가 높은 프로세스에게 page를 더 많이 할당하는 방법이다.

 

Global replacement vs local replacement

Global replacement

• replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다.
• 프로세스별 할당량을 조절하는 또 다른 방법이다.
• FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다.

local replacement

• 자신에게 할당된 frame 내에서만 replacement하는 방식이다.

 

Thrashing

프로세스의 원할한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우에 발생한다.
page fault의 비율이 높아지며, CPU 이용성이 낮아진다.
OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단하고, 또 다른 프로세스가 시스템에 추가된다.
프로세스당 할당된 frame의 수가 더욱 감소한다.
프로세스는 page의 swap in/ swap out으로 바빠진다. 이로 인해서 대부분의 시간에 CPU는 한가하다.
위와 같은 문제를 해결하기 위한 알고리즘이 work-set, PFF 이다.

 

Working-set model

프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다. 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 한다.
Working-set model

• locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 working-set이라고 한다.
• working set 모델에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않은경우 모든 frame을 반납한 후 swap out 한다.
• thrashing을 방지하며, MPD를 조절한다.

working set 알고리즘
프로세스들의 working set size의 합이 page frame의 수보다 큰 경우 일부 process를 swap out 시켜서 남은 process의 working set을 우선적으로 충족시켜 준다.

 

PFF(Page-Fault Frequency)

page-fault rate의 상한값과 하한값을 두어서 page fault 비율이 상한선을 넘으면 frame을 더 할당하고, 하한값 이하이면 할당 frame 수를 줄인다.
빈 frame이 없으면 일부 프로세스를 swap out 시킨다.

 

Page size의 결정

page size를 감소시키면 아래와 같은 일이 일어난다.

• 페이지 수가 증가한다.
• 페이지 테이블의 크기가 증가한다.
• Internal fragmentation이 감소한다.
• Disk transfer의 효율성이 감소한다.
• 필요한 정보만 메모리에 올라와 메모리 이용이 효율적이 되지만 locality의 활용 측면에서는 좋지 않다.