KOCW - 운영체제(이화여대 반효경 교수)
9장 가상 메모리

💽 가상 메모리

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것

  • I/O 양의 감소
  • Memory 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용

• valid / invalid bit의 사용

• invalid -> 사용되지 않는 주소 영역, 페이지가 물리적 메모리에 없는 경우

• 처음에는 모든 page entry가 invalid로 초기화

• 주소변환시에 invalid bit일 경우 -> page fault

• page fault가 일어나면 CPU가 자동으로 운영체제에 넘어가게 됨 -> 운영체제가 CPU를 가지고 page fault가 발생한 page를 물리 메모리에 올리게 됨

Page Fault

• invalid page에 접근 -> page fault 발생 -> kernel mode(CPU가 운영체제에 넘어감) -> page fault handler 실행

처리 순서

1. 잘못된 요청인지 확인(bad address, protection violation(접근 권한 침해)) => 잘못된 요청일 경우 abort process

2. Get an empty page frame(없으면 뺏어온다:replace)

3. 해당 페이지를 disk에서 memory로 읽어온다.

   (1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)

   (2) Disk I/O가 끝나면 page tables entry 기록, valid로 처리

   (3) ready queue에 process를 insert

4. CPU 다시 프로세스에 할당 후 실행

Performance of Demand Paging

• Effective Access Time -> page fault가 나는 비율까지 고려해서 계산, p에 page fault 발생으로 인해 발생한 overhead를 모두 더한 값을 곱해줌

Free frame이 없는 경우

• Page replacement : 어떤 framd을 빼앗아올지 결정해야 함

• 곧바로 사용되지 않을 page를 쫓아내느 것이 좋음

• Replacement Algorithm

  	* page-fault rate을 최소화하는 것이 목표

Replacement Algorithm

Optimal Algorithm

• 미래를 안다는 가정하에 진행하는 알고리즘(offline algorithm)

• 실제 시스템에 사용하는 것은 불가능

• 다른 실제 사용될 알고리즘의 upper bound 제공(이 알고리즘보다 더 좋은 결과를 낼 수가 없기 때문에)

FIFO(First In First Out) Algorithm

• First in First Out

• FIFO Anomaly -> 더 많은 메모리 프레임을 부여했더니, page fault가 더 발생하는 현상(성능 저하)

LRU Algorithm

• 가장 오래 전에 참조된 페이지를 삭제

LFU(Least Frequently Used) algorithm

• LFU : 참조 횟수가 가장 적은 페이지를 지움

LFU & LRU example

• Reference string : 왼쪽부터 순서대로 참조된 페이지

• LRU는 가장 오래 전에 참조한 1번 페이지 삭제

• LFU는 참조횟수가 1번으로 가장 적은 4번 페이지 삭제

LRU와 LFU의 구현

• LRU : 참조된 페이지들을 linked list 형태로 줄세우기(가장 최근에 참조된 페이지를 가장 끝에 줄 세움), 줄 세운 페이지 중 가장 앞에 있는 페이지 삭제

  	* 알고리즘 시간 복잡도 : O(1) 

• LFU : Heap 이용(정점 노드에 참조 횟수가 가장 적은 페이지를 배치)

  	* 시간 복잡도 : O(logn)

다양한 캐싱 환경

캐싱 기법

• 빠른 공간(캐쉬)에 어떤 것을 넣고 어떤 것을 쫓아낼지 정하는 기법

• 빠른 공간 : 물리적 메모리(개수가 한정 되어있음)

캐싱의 시간 제약

• 한 개의 요소를 교체하기 위해서 모든 요소를 순회하는 것은 시간적으로 매우 비효율적임 -> online으로 사용 불가능

• Buffer caching이나 web acching의 경우 O(1)에서 O(logn)까지 허용

• Paging system의 경우에는 LRU, LFU 사용 불가능 -> 사용하지 못하면 왜 설명했는가?

LRU, LFU 사용 가능한가?

• 이미 메모리에 존재하는 페이지가 사용이 될 경우 운영체제의 개입이 없이 사용이 되기 때문에 LRU와 같은 줄세우기를 할 수가 없음(운영체제가 해당 객체가 언제 사용됐는지 알 수가 없음, page fault가 일어난 경우에는 kernel mode로 직접 사용여부를 체크하기 때문에 알 수 있긴함)

-> 실제로는 LRU, LFU 사용 못함

Clock Algorithm

LRU를 근사시켜서 실제로 사용할 수 있도록 만든 알고리즘

• 각 페이지마다 0 또는 1이 적혀있음

• 1인 경우 최근에 사용된 페이지, 0인 경우 최근에 사용이 안된 페이지(정확한 LRU는 아니지만, 근사시킨 알고리즘)

• NRU(Not Recently Used), NUR(No Used Recently) 라고도 불림

구현

• 하드웨어가 페이지를 가져갔을 경우 1로 처리

• 시계바늘이 돌면서 0인 페이지를 만나면 해당 페이지를 교체, 1인 페이지는 0으로 처리

• 다시 돌아오는 동안에도 페이지가 사용이 되었으면 다시 1이 되어있을 것이기 때문에 LRU처럼 계속해서 쓰이는 페이지는 교체되지 않음

개선

• reference bit과 modified bit 함께 사용

• reference bit = 1일 경우 최근에 참조된 페이지

• modified bit = 1일 경우 최근에 변경된 페이지

Page frame 의 Allocation

각 프로세스마다 얼마만큼의 page frame을 할당할 것인가?

• 각 프로그램마다 최소로 필요한 메모리 공간(최소한 할당되어야 하는 frame)이 있음 -> 이 최소 공간이 없을 경우 매 루프마다 page fault가 발생할 것임

• 그렇기 때문에 각 프로세스마다 최소한의 page frame을 적절히 할당해주어야 한다.

할당 스키마(Allocation Scheme)

• Equal allocation : 모든 프로세스에 똑같이 할당

• Proportional allocation : 프로세스 크기에 비례하여 할당

• Priority allocation : 프로세스의 priority에 따라 다르게 할당

Global vs Local Replacement

• Global

  	* Replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다(경쟁, 다 뺏을 수도 다 뺏길 수도 있음.)

  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
  • Working set, PFF 알고리즘도 이에 포함

• Local

  	* 각 프로세스에게 frame을 할당

  • 할당된 frame 내에서 replacement
  • 같은 알고리즘이 사용되지만 global과 local의 차이가 있음

Thrashing Diagram

• X축은 메모리에 올라와 있는 프로세스의 개수로 이해하면 됨

• Y축은 CPU 이용률, 개수를 늘림에 따라 올라가다가 급격히 떨어지는 구간이 존재 -> page fault로 인해 CPU가 쓰이지 않는 상황 thrashing

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우

• 메모리에 너무 많은 프로그램이 올라가 있어서 CPU 이용률이 낮은데(page fault로 인해) 운영체제에서는 CPU 이용률이 낮기 때문에 프로세스를 메모리에 더 올리려고 한다. 위 그래프 상으로도 볼 수 있듯이 thrashing 이후 프로세스가 많아짐에 따라 CPU 이용률은 더 떨어지게 된다.

Working-Set Model

Thrashing을 막기 위한 방법

메모리 참조의 locality

• Locality set : 특정 시간에 집중적으로 참조되는 page들의 집합

• 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다

Working-set Model

• Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합

• 만약 메모리가 부족하여 어떤 프로세스의 working set이 메모리에 올라가지 못할 경우 모든 메모리를 반납하고 프로세스를 swap out(suspend)시킨다. swap out된 프로세스는 working set이 보장받을 만큼의 메모리 여유가 생겼을 경우 다시 실행

Working set의 결정

• Working set window를 통해 알아냄(과거를 통해 미래를 알아낸다)

• 과거에 델타만큼의 범위 내에서 사용된 페이지의 종류를 working set으로 판단

• 델타 범위를 10이라고 했을 때 두번째 경우에서는 2개의 페이지만 참조됐기 때문에 working set을 2개{3, 4}로 판단

• 여기서 정해진 working set을 통해서 프로세스를 메모리에 올릴지 말지 판단 -> Thrashing 방지

PFF (Page-Fault Frequency) Scheme

일정 page-fault를 유지시켜서 thrashing을 방지하는 알고리즘

• page-fault rate의 상한값과 하한값을 둔다

• page-fault rate이 상한값보다 클 경우 frame을 더 할당

• 반대의 경우에는 frame을 줄인다

• 빈 frame이 없을 경우 일부 process를 swap out

Page Size의 결정

전체 메모리(최근엔 32->64비트 주소 체계 사용) 규모가 커지면서 페이지 크기가 더 커지고 있음

• 그렇다면 전체 page size의 크기가 달라짐에 따라 전체 시스템에 어떤 영향이 갈까?

Page size를 감소 시킬 경우

• page table의 크기가 증가함(논리적인 주소, 페이지 수 가 늘어나기 때문에)

• 물리적인 메모리를 더 세밀하게 분할해서 사용(이 또한 page table의 증가를 야기함) -> 물리적인 메모리가 사용되면 인접한 위치의 메모리가 같이 사용될 가능성이 매우 높음 -> 정말 필요한 내용만 읽어왔기 때문에 또 다른 기계어를 실행하기위해 또 다른 메모리를 읽어야한다 -> page fault가 자주 발생, Disk transfer의 효율성 감소

• 필요한 정보만 메모리에 올라와서 메모리 이용 효율이 좋지만 Locality의 측면에서는 좋지 않음(인접한 메모리에 있는 정보까지 같이 읽어지기 때문에)