운영체제(OS) - 7. 가상메모리

# 가상메모리

각 프로그램이 0번지부터 시작하는

자기 자신만의 메모리주소공간을 가정하여 사용하는 것

---

  # 장점

  ▶ 주기억 장치의 효율적관리

 

     주기억장치를 하드디스크에 대한 캐시로 설정하여,

당장 사용하는 영역만 메모리에 올리고,

나머지는 하드디스크의 스왑영역(BackingStore, Swap area)에 내려놓는다.

 

  ▶ 메모리 관리의 단순화

 

각 프로세스마다 가상메모리의

통일된 주소공간을 배정할 수 있으므로

메모리 관리가 단순해짐

 

  ▶ 메모리 용량 및 안정성 보장

 

한정된 공간의 RAM이 아닌

거의 무한한 가상메모리 공간을 배정함으로써,

프로세스 간의 메모리 침범의 여지를 줄임

---

---

 

# 요구 페이징(demand paging) &

요구 세그멘테이션(demand segmentation)

 

프로세스의 주소공간을

메모리로 적재하는 단위에 따른

가상메모리기법의 분류

 

대부분 demand paging을 사용, 

demand segmentation을 사용하는 경우는

Paged Segmentation(OS, 6장 메모리관리 참조)을 사용하는 경우

 

즉, 세부적인 구현에서는 demand paging만 사용된다고 볼 수 있음.

 

# Demand Paging

프로세스의 모든 페이지를 한꺼번에 메모리에 올리는 것이 아닌,

당장 사용될 페이지만을 올리는 방식

 

특정 페이지에 대해 CPU의 요청이 발생해야

해당 페이지를 메모리에 적재

(메모리사용량↓, 메모리로드 입출력 오버헤드↓, 응답시간↑)

---

#유효-무효 비트(valid-invalid bit)

 

각 페이지가 메모리에 존재하는지 표시하는 비트

 

PTE마다 존재

(Pagetable의 각 항목마다 존재)

 

프로세스 실행 전은 비트가 모두 invalid로 초기화

특정 페이지가 참조되어 메모리에 적재시, valid로 변경

(OS, 6장 메모리관리 참조)

---

# 페이지 부재(Page Fault)

 

유무효비트가 무효로 세팅되어 있는 경우

(CPU가 참조하려는 페이지가 메모리에 적재되어있지 않은 경우)

---

# 페이지 부재처리(Handling Page Fault)

 

CPU가 무효페이지에 접근하면

MMU(Memory Management Unit)가

page fault trap을 발생시킴

(OS가 page fault handler 호출)

---

# Page Fault Handler(페이지부재 처리루틴)

 

1. 접근의 적법성 체크

(사용되지 않는 주소영역 or 접근권한위반)

(적법치 않을경우, 프로세스 강제종료)

 

 

2. 적법할 경우, free frame 할당 후 그 공간에 페이지 로드

만약, 프레임이 다 꽉차있다면 로드된 페이지 중 하나를 내쫒음

 

3.  디스크 입출력동안 해당 프로세스는 Blocked

 

4. 디스크 입출력완료 후 하드웨어 인터럽트 발생

 

5. Blocked 프로세스 Ready Queue 진입

---

---

# 요구페이징의 성능

 

Page Fault의 빈도수가 성능에 직결

(디스크->메모리 입출력 오버헤드 때문)

---

유효 접근시간 (EAT : Effective Access Time) : EAT

 

(PageFault 발생 비율 P)

 

EAT = (페이지부재 처리루틴+프로세스 재시작)*P + (메모리접근시간)*(1-P)

 

---

---

# 페이지 교체

(Page Replacement)

 

물리메모리에 Free Frame 이 존재하지 않을 경우 발생

---

# 교체 알고리즘

(Replacement Algorithm)

 

목표는 PageFault Rate를 최소화

 

즉, 가까운 미래에 참조될 가능성이

가장 적은 페이지를 Swap-out 하는것

 

Input은 페이지참조열(page reference string)

Output은 페이지 부재율

 

# 페이지 참조열

(Page Reference String)

 

참조되는 페이지들의 번호를

시간 순서에 따라 나열한 것

 

ex) 1,2,3,4,1,5,6,7,2,1

---

# 최적 페이지 교체 알고리즘

(Belady's Optimal Algorithm)

(= MIN, OPT)

 

Frame에 들어있는 Page 중

가장 먼 미래에 참조될 페이지를 Swap-Out 하는 알고리즘

 

미래 페이지 참조 순서를 미리 알고 있어야 하기에,

실제 시스템(온라인)에서 사용 불가능

(이를, 오프라인 알고리즘이라 부름)

 

대신 다른 알고리즘들의 성능에 대한

상한선(upper bound)를 제공

 

새로운 교체 알고리즘 개발시,

성능비교 척도로 사용

---

# 선입선출 알고리즘

(FIFO : First In, First Out)

 

물리적메모리에

가장 먼저 올라온 페이지를 Swap-Out

 

# FIFO anomaly

 

FIFO 알고리즘에서

물리적메모리의 크기를 증가시켰음에도 불구하고,

PageFault가 증가하는 현상

---

# LRU 알고리즘

(Least Recently Used Algorithm)

 

시간지역성을 활용하여,

메모리에 로드된 페이지 中,

가장 오래전에 참조가 이루어진 페이지를 Swap-Out

 

FIFO anomaly가 발생하지 않음

 

# 시간지역성

(temporal locality)

 

최근에 참조된 페이지가 가까운 미래에

다시 참조될 가능성이 높은 성질 및 경향

 

---

# LFU 알고리즘

(Least Frequently Used Algorithm)

 

과거 참조횟수(reference count)가

가장 적은 페이지를 Swap-Out

 

동일한 참조횟수일 경우,

임의로 하나 선택

(더 오래전에 참조된 페이지를 선택하는게 효율적)

 

# Incache-LFU

 

페이지가 메모리에 로드된 후 부터

참조 횟수를 카운트

(같은 페이지가 재적재 될경우,

count=0 부터 다시 시작)

 

# Perfect-LFU

 

메모리 로드 여부와 상관없이,

해당 페이지의 과거 총 참조 횟수를 카운트

(기록유지 오버헤드발생)

---

# LFU와 LRU의 극단적 비교

 

ex) 메모리의 프레임은 총 3개

 

주어진 페이지 참조열(Page Reference String)은

아래와 같음

 

1, 1, 1, 1, 3, 3, 2, 2, 2, 4

 

4 입장시,

---

LFU는 3번을 Swap-Out

(LFU는 1번의 참조횟수만 알뿐,

오래된 페이지인걸 인지하지 못함)

---

LRU는 1번을 Swap-Out

(LRU는 1번이 가장 오래된 페이지임은 인지하지만,

잦게 사용된 페이지임을 인지하지 못함)

---

# 클럭 알고리즘

(Clock Algorithm, NRU, NUR)

(not used recently)

 

LRU와 LFU는 페이지의 참조시각 및 횟수를

소프트웨어적으로 유지 및 비교

(PageTable에 기록)

 

그에 비해, 클럭알고리즘은 하드웨어의 지원을 통해

운영 오버헤드를 줄인 방식

 

대부분의 시스템에서 페이지 교체알고리즘으로

클럭 알고리즘을 채택

 

오랫동안 참조 되지않은 페이지를 교체대상으로 삼는다.

 

LRU와 유사하지만,

가장 오래된 페이지를 교체한다는 보장을 하지 못한다.

---

# 작동방식

 

메모리의 프레임마다 참조비트가 설정되어 있으며,

참조될때, 1로 자동세팅

 

시곗바늘은 계속 한칸씩 움직이며, 

1은 0으로 변경

0은 페이지교체

(즉, 적어도 Clock의 한 바퀴만큼은 페이지를 유지)

 

2차 기회 알고리즘이라고도 불림

(second chance alogorithm)

 

---

---

# 페이지 프레임의 할당

 

CPU에서 명령을 실행할 때에는 일반적으로 여러 페이지를 동시에 참조

(코드, 데이터, 스택등 각기 다른 영역을 참조)

 

따라서 프로세스를 정상적으로 수행하기 위해서는

일정수준 이상의 페이지 프레임을 보유해야함

 

반복문을 실행중인 프로세스는

반복문을 구성하는 페이지들을 한꺼번에 메모리에 올려놓는 것이 유리

(그렇지 않으면 매 반복마다 Page Fault)

 

---

 

---

# 균등할당

(equal allocation)

 

모든 프로세스에게

페이지 프레임을 균일하게 할당

---

# 비례할당

(proportional allocation)

 

프로세스 크기에 비례하여

페이지 프레임을 할당

(프로세스 크기를 고려한 균등할당)

---

#우선순위 할당

(priority allocation)

 

우선순위에 따른

페이지 프레임 할당

---

---

# 전역교체 & 지역교체

 

# 전역교체

 

모든 프레임을 대상으로 페이지 교체

(페이지가 어떤 프로세스에 속해있는지 고려하지 않음)

 

# 지역교체

 

프로세스 별로

할당된 프레임 내에서만 페이지 교체

 

---

# 스레싱

(Thrashing)

 

Page Fault Rate 가 크게 상승하여

CPU Utilization이 급격히 떨어지는 현상

(CPU가 대부분의 시간동안 일을 하지 않는 현상)

---

# CPU 이용률과 MPD의 관계

(CPU Utilization & MPD)

 

운영체제는 CPU 이용률이 낮을 경우

메모리에 올라온 프로세스의 수가 적기 때문이라 판단한다.

 

Ready Queue에 하나라도 프로세스가 존재하면,

CPU는 그 프로세스를 실행하므로 쉬지않고 일하게 된다.

 

CPU 이용률이 낮다는 것은

Ready Queue 가 비는 경우가 발생한다는 뜻이다.

 

메모리에 올라온 프로세스가 너무 적어,

모두 I/O 작업을 함으로써 Ready Queue가 비었다고 판단한다.

 

그리하여 OS는 CPU이용률이 낮으면

MPD(multi-programming degree)를 높이게 된다.

(=메모리에 올라가는 프로세스의 수를 늘린다)

---

MPD가 과도하게 상승하면,

각 프로세스에게 할당되는 메모리의 양이

지나치게 감소하여, Page Fault가 자주 발생한다.

 

Page Fault 발생시, Disk I/O 작업으로 인해

CPU가 다른프로세스에게 이양

 

이양 받은 프로세스 역시

Page Fault로 인해 CPU 이양

 

이로 인해, Swap-In-Out 만 하며,

CPU가 놀게되는 현상을 스레싱(Thrashing)이라 한다.

 

출처 : https://woodforest.tistory.com/15

---

---

# Thrashing 해결방법

(= MPD 조절방법)

 

 

# 워킹셋 알고리즘

(Working-Set Algorithm)

 

지역성 집합(locality set)이 메모리에 동시에 올라갈 수 있도록

보장하는 메모리 관리 알고리즘

 

워킹셋(working-set)이 한꺼번에 메모리에 적재될 수 있는 경우에만

프로세스에게 메모리를 할당

 

그렇지 않을 경우,

해당 프로세스의 주소공간 전체를 Swap-Out

(MPD 감소)

---

# 지역성 집합

(locality set)

 

집중적으로 참조되는 페이지들의 집합

---

# 워킹셋

(working-set)

 

프로세스가 일정시간 동안 원활히 수행되기 위하여,

한꺼번에 메모리에 적재되어야하는 페이지들의 집합

---

# 워킹셋 결정방법

 

워킹셋 윈도우(working-set window)를 사용

 

해당시각 t까지의 프로세스 참조열을

워킹셋 윈도우의 크기만큼 담아

서로 다른 페이지들의 집합을

워킹셋으로 정의

 

참조 : https://developyo.tistory.com/218

---

# 요약

 

메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이

메모리 전체 프레임수보다 클 경우,

 

Swap-Out 후 프로세스들의 워킹셋이

메모리에 모두 올라가게끔

일부 프로세스를 Swap-Out

---

메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이

메모리 전체 프레임수보다 작을 경우,

 

MPD를 증가시킨다.

---

윈도우의 크기가 너무 작으면,

지역성 집합을 모두 수용하지 못할 가능성 발생

 

윈도우의 크기가 너무 크면,

MPD가 감소하여 CPU 이용률이 낮아질 가능성 발생

 

---

# 페이지 부재 빈도 알고리즘

(Page Fault Frequency Algorithm, PFF)

 

프로세스의 페이지 부재율을 기반으로

각 프로세스에게 할당할 메모리양을 동적으로 조절

 

프로세스 A의 페이지 부재율이

상한값(upper bound)를 넘어서게 되면

A의 프레임의 수가 부족하다고 판단하여,

A에게 프레임을 추가로 할당

 

Free Frame 이 없을 경우,

일부 프로세스를 Swap-Out

(MPD 감소)

 

프로세스 A의 페이지 부재율이

하한값(lower bound)이하로 떨어지게 되면

A에게 프레임이 지나치게 할당된 것으로 판단하여,

A에게 할당된 프레임 수를 감소

 

이러한 프로세스로,

메모리 내에 존재하는 모든 프로세스에게

프레임을 할당 후에도 프레임이 남는 경우

MPD를 높인다.

 

---