OS - 가상메모리

Virtual Memory (가상메모리)

가상메모리 기법은 전적으로 OS가 관리한다
현대 OS 대부분의 사용중인 paging기법을 통해서 알아볼 예정

Demand Paging (페이지 요청 기법)

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

os_11_1

프로세스가 자주 사용하는 주소공간은 전체 중에서 매우 일부.

자주 사용되지 않는 부분은 거의 대부분 방어코드이다.
특히 좋은 프로그램일수록 방어코드가 많고 이런 코드들은 예외가 발생하지 않는 이상 사용되지 않는다.

Demand Paging 은 드물게 사용하는 코드들은 요청이 들어오기 전에는 메모리에 상주시키기 않는 방법이다

이로써 얻는 장점은 다음과 같다.

  1. I/O양의 감소
  2. 빠른 응답시간
  3. Memory 사용량 감소
  4. 더 많은 사용자 수용

자주 사용하지 않는 메모리를 디스크로 내림으로써 시스템 전체적으로 I/O요청이 감소하고 성능이 향상된다.

Logical Memory 를 보면 A~F page는 실제 프로그램이 사용하는 page들이고 G H 는 사용하지 않는 page 이다
Disk(swap area, backing store) 를 보면 사용하는 코드만 올라가 있고
물리메모리를 보면 그중에서도 자주 사용하는 A G F 만 올라가 있다.

Demand Paging 기법에서 맨 처음 page table 의 valid-invalid bit는 모두 invalid로 설정돼있을 것이고
해당 page 가 사용되면서부터 valid 로 설정되고 page table 해당 entry 에 frame 번호가 적용될 것이다.

예를 들어 1번 page(B) 를 접근하려고 page table 에 갔더니 invalid 일 경우
page fault trap 을 MMU 가 발생시키고 CPU제어를 자동적으로 OS로 넘긴다.
그럼 OS에 있는 처리루틴(page fault handler)를 invoke 하고 처리과정은 다음과 같다.

Page Fault 처리과정

  1. Invalid Reference
    프로세스 주소가 잘못됐는지, 접근권한(읽기, 쓰기)이 맞는지 검사한다.
    Invalid Reference일 경우 강제 종료(abort process)시킨다.
  2. Get an empty page frame
    합당한 요청일 경우 빈 frame 을 하나 얻어야하는데 물리메모리가 각종 프로세스들의 page들로 꽉 차 남는 frame 이 없을 수 있다. 이런 경우 하나를 뺏어야한다(replace)
  3. 해당 페이지를 disk에서 memory로 읽어오기
    disk I/O 를 하게 되면 CPU는 page를 요청한 프로세스를 block상태로 preempt, disk컨트롤에 I/O 요청하고 다른 프로세스에게 넘어간다.
    disk I/O 가 끝나면 CPU는 인터럽트가 걸리고 page table entry 를 valid bit 로 수정, frame 번호를 기입하고 ready queue 에 해당 프로세스를 insert시킨다.
    이 과정을 그림으로 표현하면 아래와 같다.

os_11_2

page fault 가 나면 당연히 I/O 작업이 발생하게 되고 이는 메모리 접근 시간을 좌지우지한다.

page fault 비율이 0~1 사이 일 때 실제 OS에서 비율을 조사해보면 거의 0.09~0.098 정도의 값이 나온다
(거의 발생하지 않는다).

os_11_3

(1-p) 는 page fault 가 나지 않는 비율
p 는 page fault 가 나는 비율

발생 소요 시간 구하는 항목이 매우 많다
OS와 HW에서 page fault시 나는 오버헤드(문맥교환등), 메모리 빈공간 없을시 swap되는 과정 등이 추가된다.

Page Replacement

메모리에 자리가 없는 경우에 frame에서 page를 쫓아내는 과정을 Page Replacement 이라 한다.

사용되는 알고리즘을 Replacement Algorithm
가급적 page fault비율이 0에 가깝도록 하는 것이 목표이다.

os_11_4

어떤 page 가 희생양이 될 건지 구하고 swap out한다,

만약 victim page 가 기존에 swap out 되어있었다 다시 물리메모리에 올라온 경우일 때
swap in 되고나서 변경된 내용이 있다면 다시 swap out 할 때 disk 에 I/O작업을 새로 해줘야 하고
변경된 내용이 없다면 물리메모리에서 지우기만 하면 된다.

page 가 swap out 되면 invalid bit 로 변경하고 필요한 page 를 swap in 한다.
이 역할들은 모두 OS가 담당한다.

page 교체 알고리즘

페이지에 숫자를 붙이고 사용되는 순서가 아래와 같을경우

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

한정된 메모리 안에서 어떻게 메모리가 올라가는지 어떤 알고리즘이 제일 좋은지 알아보자.

Optimal Algorithm(최적 알고리즘)

미래에 참조되는 페이지 순서를 다 안다고 가정했을 때 사용되는 알고리즘이다.
그래서 실제 시스템에 적용해 볼 수 는 없다(미래를 알 수는 없으니까).
Offline algorithm이라고도 한다.

os_11_5

이 알고리즘은 가장 먼 미래에 사용되는 알고리즘을 가장 먼저 쫓아낸다.
빨강은 page fault 가 난 경우를 뜻하고 연분홍은 page fault가 나지 않는 경우를 뜻한다.

5번 page가 들어오는 경우를 보면 1, 2, 3, 4 중에서 가장 먼 미래에 사용되는 4를 쫓아내고 5를 집어넣었다.

미래를 알고있을 때 사용하는 알고리즘으로 이보다 더 좋은 알고리즘은 없다.
그런 의미로 Optimal Algorithm은 모든 page교체 알고리즘의 성능 기준을 제공한다

이러한 기준을 upper bound라 함 아무리 좋아도 이거보단 안 좋음

FIFO(First In First Out) Algorithm

먼저 들어온 page 를 먼저 내쫓는 알고리즘

os_11_6

이상한 건 frame수를 늘려줬는데 page fault수가 증가했다는 것
오히려 성능이 나빠졌다. 이러한 현상을 FIFO Anomaly(이상)라 한다

LRU(Least Recently Used) Algorithm

현재 시스템에서 가장 많이 사용되는 알고리즘.

os_11_7

가장 오래전에 참조된, 덜 최근에 사용된 page 를 내쫓는다.
최근에 참조된 것이 가까운 미래에 참조될 가능성이 높은 성질을 이용한 알고리즘이다.

LFU Algorithm(Least Frequently Used)

참조 횟수가 가장 적은 page 를 내쫓는다.

os_11_8

과거에 참조된 적이 많은 page 는 미래에 참조될 가능성이 높은 성질을 이용한 알고리즘이다.

참조횟수가 동률일 경우 아무거나 내쫓는데, 조금이라도 성능을 높이고 싶다면 덜 최근에 사용한 page 를 내쫓으면 된다.

LRU, LFU둘다 장단점이 있다

오른쪽 그림은 page들의 참조시점을 시각적으로 표시한 그림, page5 를 물리메모리에 올릴 때 예시이다.

LRU는 가장 덜 최근에 사용된 page1을 내쫓고
LFU는 가장 사용률이 적은 Page4 를 내쫓는다.

LRU LFU 비교

이 알고리즘들이 실제 어떤식으로 구현되는지 그림으로 알아보자.

os_11_9

LRU 는 최근에 참조된 시간 순으로 메모리에 올라와있는 page를 줄 세운다.
Doubly linked list(양쪽에 모두 포인터)형식으로 구현돼있기 때문에 새로운 page가 추가되거나 순서가 바뀌는 것도 문제없다.
맨 위에 있는 page가 가장 오래전에 참조된page, 제일 아래가 가장 최근에 참조된 page이다.

만약 어떤 page가 새로 메모리에 들어오거나 재참조 될 경우 가장 아래로 보내면 되고
쫓아낼 때는 가장 위에 있는 page 를 쫓아내면 된다.
List형태로 구현해 비교가 필요 없기 때문에 시간복잡도는 O(1)된다.

LFU도 Linked list로 한 줄로 구현할 경우 효율이 가장 좋을까?
참조횟수를 page별로 일일이 비교를 해야 하기 때문에 좋지한다. 최악의 경우 모든 page와 모두 비교해야한다.
따라서 힙으로 구연한다.

os_11_10

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.

참조횟수가 가정 적은 page를 맨 위의 노드로, 아래 자식들은 자신보단 참조횟수가 적다.
참조횟수가 늘어 아래로 이동해야할 경우 자신 밑의 자식들과 비교하면 되기 때문에 트리의 높이만큼만 비교하면 된다.
쫓아낼 때는 최상위 노드를 쫓아내고 재구성 하면 된다. 복잡도는 O(log N) 이다.

page 교체 알고리즘에서 시간복잡도는 최소 O(1) ~ O(log N)까지여야 한다.

사실 LRU 와 LFU 알고리즘은 실제 시스템에서 사용되지 않는다.

os_11_11

프로세스A 가 CPU를 사용 중일 때 2번째 page 를 참조하는 그림이다.

2번 page 는 이미 6번 frame 에 올라가 있기 때문에 주소변환만해서 접근하면 되서 Page fault 가 나지 않는다.
이는 곧 I/O작업을 할 필요가 없기 때문에 OS개입도 없다는 뜻이다.

OS개입이 없기 때문에 OS는 2번 page가 언제 몇 번 사용됐는지 체크할 수가 없다
(LFU, LRU 사용할 정보부족).

즉 page fault 가 일어날 경우만 사용시간, 사용횟수를 체크해 줄 세울 수 있기 때문에 LRU, LFU 알고리즘 실제 시스템에서 사용하는 것이 어렵다.

Clock Algorithm

실제 시스템에서 page 교체를 위해 사용되는 알고리즘은 Clock Algorithm 이다.

os_11_12

frame 상에 있는 0 ~ 15번까지의 page 를 둥글게 줄 세워놓은 circular queue 이다.
안의 숫자는 reference bit 다른말로 access bit이다
(1bit크기, frame에 할당된 page마다 하나씩 있음).

  • 비트가 1일경우 최근에 사용된 페이지
  • 비트가 0일경우 최근에 사용되지 않은 페이지

비트를 바꾸는 건 주소변환을 담당하는 하드웨어가 담당한다.

Clock Algorithm 은 0과 1로만 최근에 사용했냐 안했냐를 표시한다.
frame 에 사용할 page 가 이미 있다면 reference bit 를 1로 변경하고 page를 가져간다.

만약 frame에 사용할 page 가 없다면 page fault 인터럽트가 발생되고 OS가 그림처럼 frame 을 돌면서 쫓아낼 page 를 찾는다.

쫓아낼 page를 찾는 과장중 OS는 아래 순서로 움직인다.

  1. 가리킨 frame 이 최근에 사용된 reference bit 가 1이었다면 0으로 변경
  2. frame 을 page로 이동.
  3. 최근에 사용되지 않은 reference bit=0 인 frame 을 만날 때 까지 반복.
  4. reference bit=0 frame 을 만나면 해당 frame 의 페이지를 쫓아낸다.

Clock Algorithm의 개선

Reference bit 외에도 frame 에 modified bit(dirty bit) 라는 것을 추가.

page 에 최근에 읽기작업과 쓰기작업을 했는지 구분하기 위해 사용하는데
읽기가 발생했을 땐 reference bit 를 1로, 쓰기가 발생했을 땐 reference bit와 modified bit를 둘다 1로 설정한다.

따로 modified bit 를 추가한 이유는 나중에 page가 사용되지 않아 쫓겨날 때
그냥 쫓아내기만 하면 되는지, 아니면 쓰기작업이 발생해 swap area 에 갱신까지 해서 쫓아내야 하는지 구분하기 위해서다.

따라서 modified bit는 메모리에 올라와 쓰기작업이 한번이라도 발생했다면 계속 1로 유지된다.

page 교체 운용방법

page frame 할당

각프로그램마다 적어도 어느정도 page frame을 할당해 놓아야 원활하게 동작한다.

예로 루프를 1000번 정도 도는 프로세스가 frame을 5개만 할당 받으면 page fault 없이 동작한다 가정했을 때

프로세스에 frame 5개를 할당하지 않고 3개만 준다면 루프 돌때마다 page fault 가 여러 번 발생할 것이고 이는 비효율로 이어질 것이다.

frame 2개 차이로 발생한 overhead치고는 대가가 너무 크다.

page frame 의 할당방법

  1. equal allocation
    모든 프로세스한테 같은 크기만큼 frame 할당.
    프로세스마다 크기가 다르기 때문에 공평하지만 효율적이진 않다.
  2. proportional allocation
    프로세스 크기에 비례해서 frame 할당
  3. priority allocation
    프로세스의 priority 에 따라 다르게 할당
    CPU를 바로 사용할 수 있는 프로세스에게 메모리를 많이 할당해주는 것이 효울적이기 때문에 CPU를 바로 사용할 확률이 높은, priority가 높은 프로세스에게 frame을 많이 주는방법.

위의 방법들은 모두 프로세스에 요구조건을 따라 어느정도 메모리를 할당시켜두는 방법이다.

page frame 할당은 각 프로세스 마다 메모리를 어느정도 할당해 놓고 운영하는 방법,
그리고 아예 할당 개념 없이 모든 프로세스가 경쟁하면서 메모리를 사용하는 방법이 있다.

page frame 교체

Global replacement
프로세스 마다 메모리를 할당해 놓지 않고 운용하는 방법.
페이지를 쫓아 낼 때 어느 프로세스의 page인지 개의치 않고 page 교체 알고리즘 에 따라 쫓아내는 방식.
모든 프로세스들이 경쟁해야 하기 때문에 자동적으로 정말 메모리를 많이 사용하는 프로세스에게 frame이 많이 할당되고, 메모리를 적게 사용하는 프로세스에겐 frame이 적게 할당된다.
문제는 양극화가 점점 커지기 때문에 starvation이 발생할 수 있다.

Local replacement
프로세스마다 할당 해놓고 운용하는 방법. 프로세스A가 page fault가 발생하면 할당된 frame 중에서 쫓아낼 page를 골라야 한다.
프로세스별로 page 교체 알고리즘 운영한다.
현대 OS에선 위 두가지 개념을 적절히 잘 섞어서 사용한다.

Thrashing

프로세스 개수에 따른 CPU 사용률을 보여준다.

그림처럼 메모리에 올라간 프로세스 개수에 따라 CPU 이용률도 어느정도 늘어나다 갑자기 CPU이용률이 뚝 떨어진다.
뚝 떨어지는 현상을 Thrashing 이라 한다.

os_11_13

  • X 축: 메모리에 올라가있는 프로세스 개수
  • Y 축: CPU 이용률

CPU 이용률이 100%가 되도록 사용하지 못하는 이유는 도중에 프로세스가 I/O작업을 하러가면 CPU가 놀게 되기 때문이다.

프로세스가 메모리에 여러 개 올라가게 되면 I/O작업시에 발생되는 텀을 다른 프로세스가 사용할 수 있게 됨으로 CPU 이용률이 늘어나게 된다.
즉 메모리의 모든 프로세스가 I/O작업을 하지 않는 이상 CPU는 계속 일한다.

너무 많은 프로세스를 동시에 올려 놓아 모든 프로세스가 원활히 동작하기 위해 필요한 최소한의 메모리도 확보 못한 경우에 발생한다.

모든 프로세스가 최소한의 메모리도 없으니 계속 page fault 가 발생하면서 되려 CPU이용률이 떨어진다.
page fault 처리하느라 CPU가 계속 놀게 되는 현상이다.

Thrashing 을 막기위한 방법은 프로세스에게 필요한 최소한의 메모리를 보장하는 것이다
(아까 말한 Local replacement).

Locality of reference (page 참조의 집중성)

프로세스는 특정시간동안 특정 메모리공간만을 집중적으로 사용하는 특성을 뜻한다.

예를 들어 특정 함수를 사용할 때 함수구성 code의 page 를 집중적으로 사용할 것이고
루프를 돌 때로 해당 루프구성 code의 page를 집중적으로 사용할 것이다.

이렇게 집중적으로 사용되는 page의 집합을 Locality set이라 한다.
이런 Locality set을 위한 메모리 할당은 보장해줘야 프로세스가 원활이 동작한다.

Locality set 은 프로세스의 page reference 는 특정 페이지를 집중반복 참조하는 특성도 있지만 참조한 page 주변 page를 참조할 가능성이 크다는 특징도 있다.

Working set Model

Locality set 이랑 같은 뜻을 가진 용어, Working set 집중적으로 사용되는 page 들의 집합이다.
만약 메모리 공간이 부족해서 해당 프로세스의 Working set이 모두 올라가지 못할 경우
Working set 의 일부분만 올리는 것이 아니라 해당 프로세스의 메모리를 모두 swap out 후 suspended 시키는 알고리즘이다.

이전에 메모리에 올라가 있는 프로세스의 Working set 이라도 유시시키는 전략이다.

나중에 여유가 생겨 메모리에 모든 Working set을 올릴 수 있을 때
swap out됐던 프로세스를 메모리에 올린다.

Working set 은 Global Replacement와 Local Replacement 를 적절히 섞어 놓은 방법이다.
각 프로세스별로 Working set만큼의 메모리를 할당하되 프로세스끼리 경쟁하는 방법이다.

os_11_14

  • WS: Working set
  • $\Delta$: window size

시간 순서에 따라 특정 프로세스의 page참조를 나열해 놓았다.
과거에 많이 사용된 page 를 기준으로 Working set을 구성해야 한다.

$\Delta$ 의 page참조 횟수를 분석해 만든 WS 각각 아래와 같다.

  • t1: {1, 2, 5, 6, 7}
  • t2: {3,4}

전에도 말했듯이 Working set은 메모리에 전부 상주하거나 상주하지 못할시 프로세스 전체가 swap out된다.

t 에 따른 WS 변화그림.

os_11_14-1

Working set bit

위에서 LFU, LRU 를 사용 못하는 이유가 물리메모리에 바로 접근해서 page접근 시 page참조 횟수를 OS가 기록 못하기 때문이라 했는데
위 그림의 Working set 에서 page reference table 의 page 참조 횟수는 누가 구하는지 알아보자.

WS을 구현 가능한 이유는 Working set-bit 가 프로세스 별로 존재하며 이는 하드웨어가 shift 연산을 통해 Working set을 최신화 시켜준다.

os_11_14-2

Working set bit 에 1이 하나라도 있으면 WS에 포함되어 있다는 뜻이고
window size(10) 만큼 shift되어도 1이 남아 있다면 계속 Working set에 존재,
1이 사라져 모두 0이 된다면 Working set 에서 퇴출당한다.

Window size 에 따라 Working set 허용 개수와 Working set-bit 크기가 결정된다.

참고자료: http://www.cs.cornell.edu/courses/cs4410/2016su/slides/lecture13.pdf

PFF(page fault frequency) schema

Working set 이 자주사용되는 page 를 할당시키는 방법이라면
PFF 는 frame 할당 비율을 적정 수준 유지시키는, 각 프로세스의 page fault 비율을 봐 가면서 메모리를 더 줄지 주지 않을지 결정하는 방법이다.

os_11_15

  • x축: 프로세스에 할당된 frame 개수
  • y축: 그에 따른 page fault 비율

그림처럼 어느정도 frame 이 할당되면 page fault 감소비율이 점점 줄어든다
(할당받은 frame값을 못함).

frame 할당을 늘리거나 줄여서 Upper bound와 Lower bound 사이를 유지하는 것이 적절하다.

이 방식 또한 적절한 구간에 들어가기 위한 메모리가 부족할 경우 프로세스 전체를 swap out시키고 메모리 여유가 생길 동안 대기시킨다.

Page size의 결정

32bit OS에선 page size를 4KB를 쓴다. 하지만 요즘은 대부분 64bit OS를 쓰고 메모리크기도 많이 늘었다. 이에 따라 page 크기도 4kb보다 크게 바뀌는 추세이다(아직까지는 4KB를 가장 많이씀).

page 사이즈가 변하면 page table , frame 크기도 같이 변한다.

즉 메모리 효율이 증가하면(page크기가 작아지면) 시스템 성능이 떨어지고,
메모리 효율이 나빠지면(page크키가 커지면) 성능은 올라간다.

page크기가 작으면 page fault가 연쇄적으로 많이 일어나겠지만
page 크기가 커지면 크기에 비례해서 page fault 발생이 적어진다.

참고