가상메모리 정리

본 글은 반효경교수님의 운영체제 수업과 강의를 보고 필요한 부분만 정리되어있으며 제 생각이 적혀있어 정확하지 않을 수도 있습니다.(피드백 주세요:-))

가상 메모리(Virtual Memory)

메모리 관리편에서는 모든 걸 사실 하드웨어 부분만 다뤘지만, 가상 메모리에서는 운영체제가 관리하는 부분을 살펴 보자.

Demand Paging(요구 페이징)

Demand Paging은 요청이 있으면 그 페이지를 메모리에 올리겠다는 의미다.

실제로 필요할 때 필요한 부분에 대해서 Page를 메모리에 올리게 된다.

메모리에 필요없는 코드까지 올려놓으면 사용하지 않게 되면 낭비가 된다. 이 부분을 해결해준다.

필요한 부분만 올리기 때문에 IO 양이 감소하게 된다.

그래서 메모리 사용량을 절감할 수 있다.

메모리 공간이 확보가 되니 많은 프로그램을 올릴 수 있으니 빠른 응답 시간을 제공해줄 수 있다.

더 많은 사용자 또한 수용할 수 있다.

자 그러면 어떤 걸 올리고 어떤걸 내리고 어떤 식으로 올리고 내리는지 알아보자.

페이지 테이블에는 ValidInvalid bit를 가지고 있다고 전에 말한 적이 있다.

Invalid는 사용되지 않은 주소 영역을 의미하고, 또는 페이지가 물리 메모리에 없는 경우를 뜻한다.

처음에는 모든 Page EntryInvalid 로 초기화 되어있습니다. 그리고 특정 주소에 접근하는 작업이 들어가게 되면,

Invalid Bittrue 라면 Page Fault 라는 현상이 발생하게 된다.

Page Fault는 요청한 페이지가 메모리에 없는 현상을 의미하겠죠? 그러면 그 뒤로

CPU는 내가 찾고자하는게 없으니, 트랩(인터럽트)이 발생하게 된다.

트랩이 발생하면 운영체제로 CPU 제어권이 넘어가게 됩니다.

운영체제는 이 트랩을 받아서 핸들러가 Page Fault 난 페이지를 메모리에 올리는 작업을 도와주게 된다.

invalid-valid

출처 반효경P 운영체제 PPT

그림을 보자.

6번과 7번은 사용되지 않는 공간이라서 invalid 체크로 되어있고 1,3,4번은 메모리에 안올라가 있어서 invalid로 체크되어있는 것을 볼 수 있다.

위 그림으로 보면 물리 메모리에 사용되는 페이지만 올리가 있고 사용되지 않은 페이지는 안 올라가 있는 부분을 볼 수 있다.

자 그러면 더 자세히 Page Fault에 대해서 알아보자.

Page Fault

Invalid Bit 인 페이지(Page)에 접근하면, MMUTrap을 발생시킨다. (Page Fault Trap)

그러면 커널 모드(운영체제)로 들어가서 Page Fault Handler가 호출된다.

그러면 요청한 주소가 잘못된 주소 요청이 아닌지, 또는 접근 권한에 문제가 없는지 체크하고 있다면, 거절 처리를 하게 된다. 펭지 아니면 다음으로 넘어가는데, 메모리에 공간이 없다면, 메모리를 비어주는 작업을 하게 된다.

그리고 해당 페이지를 디스크에서 메모리로 읽어온다.

디스크에서 데이터를 읽어올 때, CPU는 마냥 기다리지 않는다.

디스크 IO가 끝나기까지는 이 프로세스는 CPU를 선점 당해버린다.

즉, 프로세스 상태는 Block된 상태로 된다.

이 시간 동안 CPU는 다른 일을 처리하고, 디스크 IO가 끝났다면

page table entryvalid로 기록하게 된다.

그리고 그 프로세스를 Ready Queue에 넣게 된다.

그러면 자기 차례에 올 때, Running 상태로 바뀐다. 그리고 전에 있던 작업을 계속 수행하게 된다.

처리 과정

출처 반효경P 운영체제 PPT

그림으로 살펴보자.

  1. 프로세스가 특정 페이지를 찾는다. (그림 상 i === Invalid)
  2. invalid면 트랩을 발생시킨다. 트랩을 발생시키니깐, 운영체제(커널)에 CPU 제어권이 넘어간다.
  3. 운영체제는 해당 페이지를 Backing Store(디스크)에서 가져오라는 명령을 하게된다.
  4. 디스크에서 메모리로 데이터를 가져오게 된다.
  5. 페이지 테이블을 InvalidValid로 수정한다.
  6. Ready Queue에서 대기하다가 Running상태로 바뀌면서 명령어를 다시 시작한다.

그러면, 페이지 폴트가 많이 일어날 수록 위 작업이 반복되니깐 페이지 폴트가 적은게 좋다는 것을 알 수 있다.

페이지 폴트 비율

출처 반효경P 운영체제 PPT

이 그림은 페이지 폴트가 얼마나 나느냐에 따라 성능을 대략적으로 볼 수 있는 수식이다.

빨간색 글자가 페이지 폴트가 발생했을 때 수행되는 작업들이다.

다시 한번 페이지 폴트가 나면 시간이 오래걸리게 된다.

하지만 대부분의 경우 페이지 폴트가 나지 않는다고 합니다.

물리 메모리에 공간이 없을 경우엔

물리 메모리에 공간이 없을 경우, 어떤 페이지 프레임을 내려야겠죠?

그런데 아무거나 내리면 안되겠죠.

그래서 효율적으로 내리고 올리기 위해서 알고리즘들이 많이 나와있다.

자. 먼저

페이지를 교체할 때, 어떤 페이지를 빼앗아 올지 결정 해야하고, 곧바로 사용되지 않을 페이지를 내쫒는 것이 좋다.

어쨋거나 Page Fault Rate를 최소화하는 것이 목표이다.

그러면 빼앗길 희생되는 페이지(victim)을 어떤 알고리즘으로 정할지 봅시다.

페이지 교체 알고리즘

Optimal Algorithm

먼저, 이 알고리즘은 말 그대로 최적의 알고리즘인데, 가정해본 알고리즘이기 때문에 실제 시스템에서는 사용하지 못한다.

MIN 알고리즘 또는 OPT 알고리즘이라고도 불린다.

가장 먼 미래에 참조되는 Page를 교체하는 알고리즘이다.

MIN 페이지 폴트 테이블

출처 반효경P 운영체제 PPT

그림을 보자.

4개의 페이지 프레임이 있고, 거기에 순서대로 1,2,3,4,1,2,5,1,2,3,4,5 가 들어왔을 떄 모습이다.

빨강색이 페이지 폴트 난 부분이다.

FIFO(First In First Out) Algorithm

먼저 들어온 페이지를 페이지에서 쫒아내는 알고리즘입니다.

FIFO 페이지 폴트 테이블

출처 반효경P 운영체제 PPT

이 알고리즘은 특이한 성질을 가지고 있다.

프레임이 커지면 페이지 폴트가 더 많이 발생되는 현상이 있다.

그래서 이런 현상을 FIFO Anomaly 또는 Belady's Anomaly라고 부릅니다.

LRU(Least Recently Used) Algorithm

가장 오래 전에 참조된(사용된) 것을 쫒아냅니다.

LRU 페이지 폴트

출처 반효경P 운영체제 PPT

LFU(Least Frequently Used) Algorithm

참조 횟수(Reference Count)가 가장 적은 페이지를 지웁니다.

만약 참조 횟수가 작은게 여러 개 있다면, LFU 알고리즘 자체에서는 여러 Page 중 임의로 선택해서 내쫒을 수도 있고, 성능 향상을 위해서 가장 오래 전에 참조된 Page를 내쫒게 할 수 있다.

LRU처럼 근처인 직접 참조 시점만 보는 것이 아니고, 장기적인 시간 규모로 보기 때문에 Page의 인기도를 좀 더 정확하게 반영할 수 있다는 장점을 가지고 있다.

예로 LRU는 여러 번 쓰이는 페이지랑 상관없이 그냥 최근에 사용되면 살려두는 방식인데요, 엄청 많이 빈번하게 사용하다가 특정 시점에 사용 안하고 있으면 우선순위가 밀리게 되는데 LRU는 빈번히 사용되든 간에 내쫒아버린다.

반대로 LFU는 최근성을 반영하지 못한다. 이제 막 특정 페이지를 많이 쓰려고 들어왔는데 빈도수 기준으로 봤을 땐, 신참이니깐 그 친구를 내쫒을 수 있다.

LRU-LFU

출처 반효경P 운영체제 PPT

LRU : 가장 오래 전에 참조 되었지만, 빈도수가 많은 것을 고려하지 못한다.

LFU : 비록 4번이 1번 사용되었지만, 만약 이제 막 여러번 호출 할 예정이라면 문제가 발생한다.

LRU와 LFU 알고리즘 구현 방식

LRU-LFU

출처 반효경P 운영체제 PPT

LRU는 시간 복잡도가 O(1)이다.

어떤 부분이 참조 되었을 때, 그 부분을 맨 아래쪽에 링크드 리스트에 연결해놓기만 하면 된다.

LFUO(n)이 나온다. 왜냐하면 어떤 부분이 참조 되었을 때, 빈도수를 비교해야하므로 자신보다 앞에 있는 친구들을 하나씩 비교하게 된다.

그래서 LFUheap을 이용하게 된다. O(n)은 느리거든요..

LFU-개선

출처 반효경P 운영체제 PPT

LFU-개선1

출처 반효경P 운영체제 PPT

LFU-개선2

출처 반효경P 운영체제 PPT

이렇게 자료구조를 힙을 사용하게 되면 lonN번 비교해서 자신의 자리를 찾아가니 O(log n)이 나오게 된다.

아래로 내려갈 수록 높은 빈도수를 의미한다.

여기까지 대표적인 페이지 교체 알고리즘들을 살펴보자.

하지만, 운영체제는 LRULFU를 사용할 수 없다.

왜냐하면 물리 메모리에 데이터가 있다고 한다면, CPU는 그 부분을 가져와서 사용하게 되는데, 이 과정에서 운영체제는 관여하지 않기 때문이다.

무슨 말이냐면, 데이터가 물리 메모리에 있으면, CPU는 그냥 가져다가 쓰겠죠? 그 때 운영체제가 관여를 하지 않는다.

그래서 그 데이터가 언제 쓰였는지, 몇번 쓰였는지 기록을 못한다…

그래서 페이징 시스템에서 특정 페이지를 교체하기 위해서 어떤 정보를 사용할까?

바로 Clock Algorithm가 있다.

Clock Alogorithm

클락 알고리즘은 LRU와 비슷한 알고리즘

NUR(Not Used Recently) 또는 NRU(Not Recently Used)라고도 불린다.

Clock

출처 반효경P 운영체제 PPT

Circular List(원형 리스트)에서 Reference Bit을 사용해서 교체 대상이 되는 페이지를 선정하게 된다.

Reference Bit가 0인 것을 찾을 때까지 포인트를 하나씩 앞으로 이동하게 된다.

이동하는 중에는 Reference Bit값이 1인 경우 0으로 바꿔주면서 이동하게 되죠.

그리고 만약 Reference Bit이 0인 것을 찾으면 그 페이지를 교체한다.

(만약 특정 부분이 한 바퀴 돌고 와서 그 때 0 이면 그 때는 그 페이지가 교체 당한다.)

Reference Bit 말고도 Modified Bit(=Dirty Bit)을 함께 사용하게 되는데

Reference Bit값 1은 최근에 참조된 페이지라고 볼 수 있다.

Modified Bit의 값이 1인 경우에는 최근에 변경된 페이지 라고 보면된다.

Write가 일어났을 때를 의미한다. 어떤 페이지에 데이터가 1에서 2로 바꼈을 때 Modifed Bit은 1로 바뀐다.

만약에 Modified Bit이 1이라는 것은 메모리에 올라온 이후에 적어도 1번은 수정했다는 것을 의미한다.

이런 페이지는 메모리에서 쫒겨날 때, 백킹 스토어(디스크)에 수정 된 내용을 반영하고 내쫒게 된다.

때로는 백킹 스토어(디스크)에 쓰는 작업이 오버헤드가 있는 경우에는 내쫒지 않을 수도 있다.

페이지 프레임 할당(Page Frame Allocation)

이제는 페이지 프레임 할당에서 알아보자.

할당 할 때 어떤 문제를 고려해야할까.

각 프로세스에 얼마만큼의 페이지 프레임을 할당 할 것인지가 중요하겠지..

일단은 명령어를 수행하기 위해서 최소한의 프레임을 할당해줘야 프로그램이 메모리를 참조하면서 작동하겠지..

그리고 반복을 구성하는 페이지들은 한꺼번에 할당해놓는 것이 유리하겠죠.

만약 그렇지 않으면 매 반복이 돌 때마다 페이지 폴트가 발생할테니까.

만약에 프로세스에 할당 프레임수가 2개이고, 반복 돌면서 요청하는 페이지가 3개라면 루프 돌 때마다 페이지 폴트가 발생하게 된다.

2개는 있지만 1개는 없으니깐 2개중 하나 내리고 새로 가져오고, 그리고 또 반복 돌다 보니 또 없어서 또 내리고 가져오고…

프로세스에 프레임을 할당하는 방법 3가지가 있습니다.

  1. Equal Allocation(동일 할당) : 모든 프로세스에 똑같은 개수를 할당합니다. 이는 비효율적입니다. 어떤 프로그램은 크고 어떤 프로그램은 작으면 말이죠.
  2. Proportional Allocation(비례 할당) : 프로세스 크기에 비례하여 할당하게 됩니다.
  3. Priority Allocation(우선순위 할당) : 프로세스의 우선순위에 따라 다르게 할당합니다.

Global VS Local Replacement

글로벌과 로컬은 다른 느낌입니다. 일단 로컬은 위에서 말한 3가지 방법을 사용한 경우이고,

글로벌 리플레이스는 어떤 프로그램이 메모리에 많이 필요하면 많이 올라가게 된다.

상대적으로 다른 프로그램은 쫒아내지고 그때 그때 메모리 할당량이 자동으로 조절되니깐 위 3가지 방법을 사용할 필요가 없다.

Global Replacement

교체 시에 다른 프로세스에 할당된 프레임을 뺴앗아 올 수 있습니다.

즉, 물리 메모리 전역적으로 할당된 프레임을 빼앗을 수 있죠.

Globla Replacement는 프로세스별 할당량을 조절하는 또다른 방법이다.

Global Replacement는 FIFO, LRU, LFU 등의 알고리즘을 사용할 수도 있다.

그 보다 뒤에서 살펴볼 Working Set, PFF알고리즘을 사용하게 된다.

이 알고리즘들은 프로그램이 최소한 필요로 하는 할당량을 보장 해야하는 알고리즘입니다.

Local Replacement

위 3가지 방법이 사용되어서 프로세스마다 프레임이 할당되었다고 하면, 각 프로세스는 할당 프레임 내에서만 교체를 할 수 있습니다.

Local Replacement도 FIFO, LRU, LFU 등의 알고리즘을 각 프로세스별로 사용되어진다.

즉, 정리하자면 Global 같은 경우에는 다른 프로세스 프레임 영역까지 빼앗을 수 있지만, Local 에서는 각 프로세스가 할당 받은 프레임 안에서만 빼앗을 수 있다.

Thrashing

이제 쓰레싱에 대해서 알아보자.

쓰레싱은 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당 받지 못한 경우 발생하는 현상이다.

이러면 페이지 폴트 비율이 매우 높아지고, CPU 이용률도 낮아지게 된다.

쓰레싱

출처 반효경P 운영체제 PPT

먼저, 페이지 폴트 비율이 올라가면 CPU 사용률이 떨어진다.

그러면 CPU 사용률이 떨어졌으니 CPU한테 열심히 일을 시켜야한다.

  1. 운영체제는 Degree of Muliprogramming(여러개 프로세스 횟수)를 높혀야 한다고 판단하게 된다.
  2. 또 다른 프로세스가 추가가 되고, 다른 프로세스가 추가되면 프로세스 당 할당된 프레임의 수가 점점 감소하게 된다.
  3. 프로세스는 실행될 때마다 필요한 페이지를 사용할 텐데 없으니 페이지를 불러오는 Swap In이 빈번하게 일어나고, 물리 메모리에 공간이 없으니 Swap Out으로 페이지를 내보내고를 계속 반복한다.매우 바쁘게..
  4. 그래서 대부분의 시간은 Swap In, Swap Out 작업을 주로하다 보니 CPU는 한가해지니, 이용률이 떨어진다.
  5. 그러게 되면 처리량이 낮아지겠죠~

그래서 어느 정도 페이지 할당을 보장해줘야하는데, 그걸 해주는 알고리즘 또는 모델이 Working Set, PFF이다.

Working Set Model

프로세스는 특정 시간 동안에는 일정한 장소만을 집중적으로 참고하는 경향이 있다.

집중적으로 참조되는 해당 Page들의 집합을 Locality Set이라고 한다.

Working Set ModelLocality에 기반하여 프로세스가 일정 시간 동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 Page들의 집합을 Working Set이라고 정의한다.

만약에 Working Set페이지 크기가 5인데, 물리 메모리에 페이지가 3개 밖에 없다면 그 프로세스는 모든 걸 통째로 반납해버린다.

즉, 프로세스의 Working Set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않은 경우 모든 프레임을 반납하고 Swap out으로 Suspend상태로 간다.

이는 쓰레싱을 방지한다. 페이지 폴트를 적게 나게 도와주니깐!

그러면 PFF는 뭘까..

PFF(Page Fault Frequency) Scheme

PFF

출처 반효경P 운영체제 PPT

이 모델 또는 스낌은 페이지 폴트가 어느 정도 났는지 보는 형태이다.

페이지 폴트가 많이 났다면, 페이지 프레임을 더 주고, 만약 적게 났다면, 빼앗는 방식이다. 유연한 느낌이긴하네

페이지 폴트 비율의 상한값과 하한값을 두고, 그 기준에 맞춰서 상한값을 넘으면 프레임을 더 할당하고, 페이지 폴트 비율이 하한값보다 낮으면 프레임 수를 줄인다.

그래서 Bound로 최소를 보장해주게 됩니다.

이제 잡다한 부분을 봅시다.

Page Size 결정

페이지 사이즈를 줄이면 어떻게 될까요?

  1. 페이지 수가 증가!
  2. 페이지 테이블 크기 증가
  3. 외부 조각 감소(더 잘게 써니깐요)
  4. 디스크 데이터 전달하는데 효율성이 감소 할 수 도 있습니다. 왜냐하면 탐색하는 시간(seek)이 길기 때문이다. Seek할 때, 100 크기가 필요하다면 페이지 큰거 하나 100사이즈 1번만 가져오기만 하면 되지만, 페이지 크기가 작은 10짜리라고 하면 10번을 가져와야하기 때문에 Seek를 10배나 더 한다.
  5. 필요한 정보만 메모리에 올라와 메모리 이용이 효율적입니다. 페이지 크기가 작다면 필요한 부분이 작은 것이라도 올라와도 되니깐 메모리적으로 효율적입니다. 하지만 Locality의 활용 측면에서는 좋지 않다. 페이지 크기가 큰 것이 수용할 수 있는 Locality가 크기 때문이다. 페이지 크기가 작으면 여러개를 올려야하니깐 활용 측면에서는 좋지 않다.

트랜드는 페이지 사이즈를 크게한다.

캐슁 기법

한정된 빠른 공간(=캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식이다. 이게 무슨 말인지 풀자면, 속도가 빠른 공간에 데이터를 두어서 요청이 들어오면 빠르게 데이터를 제공한다는 의미이다.

캐시는 Paging System 외에도 Cache Memory, Buffer Caching, Web Caching 등 다양한 분야에서 캐슁 기법을 사용한다.


@kwonmory
성장을 위해 노력하고 있는 모리입니다.

깃허브