운영체제 10] 가상 메모리

##본 포스팅은 운영체제 강의 '이화여자대학교 운영체제 강의 - 반효경 교수님'를 보고 정리한 내용입니다.

 

Demand Paging

가상 메모리에서의 주소 변환은 운영체제의 관여가 있다.

Demand Paging은 요청이 있으면 해당 page를 메모리에 올리는 것이다.

전체 page를 올리는 것이 아니라 '해당 page'만을 올려,
- I/O 양의 감소 : 필요한 I/O가 감소한다
- Memory 사용량 감소 : 일부분의 page만 올리기 때문에 사용하는 memory양이 감소한다
- 더 많은 사용자 수용/빠른 응답 시간
을 기대할 수 있다.

[Valid/Invalid bit의 사용]
Paging 기법에는 각 Page마다 valid/invalid bit가 있는데,
여기서는 아래와 같이 구성되어있다.

당장 필요한 부분은 Demand Paging에 의해 물리적 메모리에 올라가고, 그렇지 않은 영역은 스왑 영역으로 가게 된다.

Invalid의 의미 : 사용되지 않는 주소 영역인 경우 / 페이지가 물리적 메모리에 없는 경우

위의 페이지 테이블을 보면 사용되는 페이지들은 V비트로 표시되어있는 것을 볼 수 있다.

[메모리 접근 순서]
1) CPU가 페이지에 접근하기 위해 페이지 테이블을 확인한다
2) 페이지 테이블에서 I비트로 되어있다면, 실제 메모리에 올라가지 않았다는 의미이기에 I/O에게 요청(소프트웨어 interrupt)하여 물리 메모리에 올린다
(page fault 상황)

[Page Fault]
- invalid page를 접근하면 주소를 계산하는 MMU가 trap을 발생시킨다
- 운영체제에게 권한이 넘어가 page fault handler가 invoke 된다

*메모리에 페이지가 꽉차있다면, 하나를 쫓아내고 획득한다

위에서 디스크가 페이지를 물리 메모리에 올리는 과정은 매우 오래걸리는데, 이는 page fault rate가 영향을 끼친다.
0 <= p <= 1.0
대부분의 경우에는 page fault가 나지 않지만, 한번 나면 매우 오랜 시간이 걸리게 되며(오버 헤드)
effective access time = (1-p) x memory access + p + {......페이지를 올리는데 걸리는 과정의 시간들}이 걸리게 된다.

이 과정에서 페이지를 쫓아내는 것을 page replacement라고 부르는데,
이 때 어떤 frame을 빼앗아올지 결정해야하며 곧바로 사용되지 않을 page를 쫓아내는 것이 좋다.

Replacement 알고리즘은 추후의 page-fault를 최소화하는 것이 목표이며, 알고리즘의 평가를 통해 연산이 된다.

1) Optimal Algorithm
가장 먼 미래에 참조되는 page를 replace한다.
하지만 '미래에 참조되는 page'를 아는 것은 한 가정이며, Offline algoriithm이다.
(실제 시스템에서 사용되는 것이 불가하다)

2) FIFO(First In First Out) Algorithm
먼저 들어온 것을 먼저 내쫓는 것이다.
하지만 더 많은 프레임을 줬음에도 나쁜 성능을 보일 수 있기에 사용되지 않는다.

3) LRU(Least Recently Used) Algorithm
가장 오래전에 참조된 것을 지운다.
들어온 것 중에서 참조가 제일 오래된 것을 지운다는 의미이다.

 

4) LFU(Least Frequently Used) Algorithm
참조 횟수가 가장 적은 페이지를 지운다.
만일 최저 참조 횟수 page가 여러개 있는 경우에는 임의로 선정하거나, 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.

LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 떄문에 page의 인기도를 좀 더 정확히 반영할 수 있다는 장점이 있지만, LRU보다 구현이 복잡하며 참조 시점의 최근성을 반영하지 못한다는 단점이 있다.

 

다양한 캐슁 환경

캐슁 기법이란,
한정된 빠른 공간에 요청된 데이터를 저장해두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식이다.

paging system 외에도 cache memory, buffer caching, Web caching 등 다양한 분야에서 사용한다.

하지만, 교체 알고리즘에서 사용할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.

 

Clock Algorithm

실제로 페이징 시스템에서는 LFU, LRU를 사용할 수 없기떄문에,
LRU의 근사 알고리즘인 Clock Algorithm을 사용한다.

레퍼런스 비트, 엑세스 비트가 표기되어있으며
최근에 사용되었는지 아닌지를 의미한다.

참고로 비트를 바꾸는 것은 하드웨어가 하는 것이다.
reference bit과 modified bit을 함께 사용하며,
reference bit = 1이면 최근에 참조되 페이지를 의미하며, modified bit = 1이면 최근에 변경된 페이지이다.

 

Page Frame의 Allocation

Allocation problem : 각 프로세스에 얼마만큼의 page frame을 미리 할당할 것인가의 문제이다.

[Allocation의 필요성]
- 메모리 참조 명령어 수행시 명령어나 데이터 등은 여러 페이지를 동시에 참조할 수 있기에
- Loop을 구성하는 page들은 한꺼번에 allocate 되는 것이 유리하다

[Allocation Scheme]
- Equal allocation : 모든 프로세스에 똑같은 갯수 할당
- Proportional allocation : 프로세스 크기에 비례하여 할당
- Priority allocation : 프로세스의 priority에 따라 다르게 할당

 

Global vs Local Replacement

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

Local replacement
- 자신에게 할당된 frame 내에서만 replacement
- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

 

Working-Set Model

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

Working-set Model
- Locality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 매모리에 올라와 있어야 하는 page들의 집합을 Working Set 이라 정의함
- Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
- Thrashing을 방지함
- Multiprogramming degree를 결정함

*메모리를 너무 조금씩만 가지고 있기때문에 누구한테 cpu를 줘도 page fault가 나서 처리가 불가능한 상태이다.

이 때 Working set의 결정은,
Working set window를 통해 알아내며, 과거를 통해 알아낼 수 있다.