운영체제 9장 Virtual Memory Management

Chapter 9. Virtual Memory Managment

Virtual Memory는 실행중인 프로세스가 전부 메모리에 없어도 되게 해주는 테크닉이다. 가장 큰 장점은 프로그램이 Physical Memory보다 커질 수 있다는 것이다.

 

9.1 Background

실행되게 위해서는 인스트럭션들이 피지컬 메모리에 반드시 있어야 한다는 것은 당연해보이지만 이것은 프로그램의 사이즈가 물리 메모리의 크기에 제한되게 한다. 많은 경우에 모든 인스트럭션이 사용되지는 않는다.(ex>에러처리, 배열, 특정 옵션)

프로그램이 부분적으로 메모리에 있게 하는 것은 많은 장점이 있다.

-물리 메모리의 크기에 제한받지 않는다.

-많은 프로그램이 동시에 실행될 수 있어서 응답시간의 증가 없이 CPU 이용률과 스루풋을 높인다.

-swap시 필요한 I/O가 덜 든다. 그래서 빨라진다

Virtual Memory는 physical memory로부터 유저들에 의해 받아들여지는 논리 메모리의 분리를 포함한다. 이 separation은 physical memory 공간이 매우 적게 남았더라도 매우 큰 프로그램을 실행할 수 있도록 한다.

virtual address space는 프로세스가 메모리에 저장된 logical view를 보여준다. 이것은 연속적으로 보이고 앞장에서 언급했듯이 실제 피지컬에서는 noncontiguous하다. MMU에 의해서 관리된다. 버츄얼 메모리에서 스택은 아래로 자라고 힙은 아래에서 위로 자라는데 중간의 holes을 sparse address spaces라고 한다. 이것은 스택이나 힙이 자랄 때에만 사용하면 되기 때문에 유용하다.

또한 버츄얼 메모리는 파일과 메모리가 여러 프로세스에서 공유될 수 잇도록 한다.

-virtual address space가 다르지만 같은 actual page를 접근할 수 있도록 한다.(ex>라이브러리)

-공유 메커니즘으로 shared memory를 사용할 수 있따.

-가상 메모리는 fork()시스템콜의 속도를 증가시킨다.

 

9.2 Demand Paging

프로그램을 실행할 때 전체 프로그램을 한 번에 올리는 방법이 있을 텐데 그 경우에는 쓸모없는 부분까지 다 올린다. 그래서 demand paging 방법이 virtual memory system에서 사용된다. 메모리 접근이 필요할 때만 페이지가 로드된다. 이것은 앞에서 나왔던 swapping 시스템과 비슷한데 swapping은 전체의 프로세스를 로드할 때 사용하는 용어이므로 부적합하며 앞으로는 demad paging에 있어서는 pager라는 용어를 사용한다.

 

9.2.1 Basic Concepts

전체 프로세스를 swapping 하는 대신, pager는 사용되는 페이지만 가지고 온다. 그러므로 메모리에 있는 페이지와 디스크에 있는 페이지를 식별하는 하드웨어를 필요로 한다. 앞에서 언급되었던 page entry의 valid/invalid 비트를 이용한다. 페이지가 invalid이면 완전히 invalid한 것이거나 디스크에서는 valid한 경우 일 것이다. 만약 CPU가 memory resident 페이지만 접근하면 문제가 없지만 invalid한 페이지를 접근하면 page fault가 발생한다. page fault 발생시 하드웨어는 OS에 트렙을 발생시키고 os는 이에 대한 핸들링을 수행한다. 절차는 다음과 같다.

1. internal table(주로 PCM에 있는)을 검사하여 레퍼런스가 valid한지 검사한다.

2. invalid하면 프로세스를 중지시키고, valid하지만 페이지에 아직 들어오지 않았다면 페이지를 가지고 온다.

3. 프리 프레임을 찾는다.

4. 디스크 오퍼레이션을 수행하여 페이지를 읽어온다.

5. 디스크 read가 끝나면 테이블을 수정하여 메모리를 가리키도록 한다.

6. 트랩에 의해 중지되었던 동작을 재개한다.

demand가 없을때까지 메모리에 전혀 올리지 않는 것을 pure demand paging이라고 한다.

어떠한 프로그램은 여러 새로운 페이지를 계속 접근하는데 그러면 계속 page fault가 발생하고 성능에 문제가 발생할 수 있다. 하지만 프로세스를 분석하여 locality of reference를 분석하면 demand paging에서 퍼포먼스를 행상시킬 수 있다.

사용되는 하드웨어는 swapping과 동일하다.(페이지 테이블, secondary memory)

 

9.2.2 Performance of Demand Paging

effective access time = (1-page fault의 확률)ⅹ메모리 access time + 확률ⅹpage fault time

페이지 폴트에 영향을 미치는 세가지 major point는 1.page fault interrupt 2. page read 3. restart process 이다.

effective access time은 page-fault rate에 정비례한다.

디맨드 페이징의 부가적인 aspect는 swapspace를 사용하고 다루는 것이다. 첫째로 file system의 데이터를 disk로 전부 옮겨놓는 것이고 둘째 옵션은 처음에는 파일시스템으로 직접 페이지를 요청하고 페이지가 swap space에서 replace 될 때만 그 데이터를 파일 시스템에 쓰도록 한다.

 

 

9.3 Copy on Write

fork()의 경우에 부모와 자식이 페이지를 공유하는 메커니즘으로 COW를 사용한다.

보통 fork()다음에 exec()로 실행하기 때문에 fork()를 실행한다고 페이지들을 다 복사하는 것은 비합리적이기 때문에 copy-on-write를 사용하게 되면 자식은 부모와 페이지를 공유하다가 어느 한프로세스가 페이지에 write를 시도하게 되면 그 때 다른 페이지를 접근한다. c-o-w메커니즘에서 어떠한 free page를 할당하는 것인지 결정하는 게 중요한데 많은 os는 free page들의 pool을 제공한다. 이러한 프리 페이지들은 프로세스들이 스택이나 힙을 확장하거나 copy-on-write가 수행될 때 할당된다. 이때 사용되는 기법을 zero-fill-on-demand라 한다. 할당되기 전에 기존의 데이터를 모두 날린다.

리눅스의 vfork()는 무조건 같은 페이지를 공유하므로 주의해야 한다.

 

9.4 Page Replacement

멀티프로그래밍의 degree를 증가시키면 메모리를 over-allocating 하게 된다. 또한 I/O의 버퍼도 메모리를 사용하므로 공간을 위해 경쟁하게 되고 page fault가 일어나 disk에 있는 페이지를 찾고 할당하려고 해도 공간이 없으므로 이것에 대한 해결책이 필요하다.

첫째는 프로세스를 종료 시키는 것인데 demand paging의 목적 자체가 컴퓨터 시스템의 utlization과 스루풋을 증가시키는 것이고 사용자는 그들의 프로세스가 페이지 시스템에서 돌아간다는 것을 알아서는 안되고 그것은 transparent 해야 하므로 좋은 선택이 아니다.

둘째는 프로세스 하나를 swap out 하는 것으로 특정 환경에서는 좋을 수 있다.

여기서는 가장 일반적인 솔루션 page replacement를 다룬다.

 

9.4.1 Basic Page Replacement

page replacement를 적용하여 page fault service routine을 다음과 같이 바꾼다.

1. disk의 desired page를 찾는다.

2. free frame을 찾는다

a. 있으면, 사용한다.

b. free frame이 없으면, page replacement algorithm을 사용하여 victim frame을 찾는다.

c. victime frame을 disk에 쓰고 페이지와 프레임 테이블을 바꾼다.

4. 사용자 프로세스를 재시작한다.

free 프레임이 없으면 2번의 transfer가 일어나므로 effective access time이 증가한다. 그러므로 modify bit를 적용한다. 하드웨어적으로 구현하며 해당 페이지에 대해 modify가 일어날 경우 set, 아니면 0으로 둔다. replacement 발생시 bit가 set되어있으면 디스크에 write하지만, 아니라면 버려진다. 이 방법은 I/O타임을 절반으로 줄이기 때문에 페이지가 모디파이 되지 않았을 때 페이지 fault에 드는 시간을 반으로 줄인다.

page replacement는 demand paging의 기본이고 logical과 physical 메모리의 분리를 완성한다. 이러한 디맨드 페이징에서는 logical의 크기는 더이상 physical에 의해 제한받지 않는다.

demand paging에 있어서 두 가지 문제를 완성해야 하는데 frame-allocation problem과 page-replacement algorithm이다. 적절한 태스크를 선택하여야 하며 low-page fault rate를 가지는 것이 제일 좋은 알고리즘이다.

 

9.4.2 FIFO Page Replacement

가장 간단한 replace algorithm이 FIFO이며 순서대로 나간다.

구현하기도 이해하기도 쉽지만 성능이 항상 좋지는 않다. 심지어 active use인 것을 replace할 수도 있다.

나쁜 replace alogorithm 선택은 page-fault rate를 증가시키고 성능을 감소시키지만 오동작 하지는 않는다. 심지어 어떤 경우에는 할당 프레임을 증가시킴에 따라서 page-fault rate가 증가하기도 한다. 이것을 Belady’s anomaly라고 한다.

 

9.4.3 Optimal Page Replacement

이 알고리즘은 page-fault rate를 최소로 만들며 Belady’s anomaly가 생기지 않는다.

가장 오랜시간동안 사용되지 않을 페이지를 Replace한다.

그러나 이 알고리즘은 미래에 접근될 스트링에 대한 정보를 필요로 하기 때문에 구현하기 어렵다.(프로세스 스케쥴링의 SJF와 유사하다)

이 알고리즘은 comparsion study에 이용된다.

 

9.4.4 LRU Page Replacement

optimal algorithm은 실현 불가능하므로 optimal 알고리즘의 approximation이 가능하다. 가장 오랜 시간동안 사용되지 않았던 페이지를 replace한다. 이것이 LRU(least-recently used) 알고리즘이다.

이상하게도 레퍼런스 스트링의 page fault rate와 스트링의 reverse의 page fault rate와 같다.

가끔 합리적이지 않은 선택을 할 때도 있지만 적어도 FIFO보다는 훨씬 효율적이며 좋은 알고리즘으로 여겨진다. 문제는 어떻게 이것을 구현할 것인가이다. 어떠한 LRU알고리즘은 hardware support를 필요로 하기도 한다.

(1) counters

간단하게 각 페이지 테이블 엔트리에 사용한 시간의 필드를 가지도록 한다. 이 필드는 모든 메모리 접근때 증가한다. 각각 가장 최근에 접근된 시간을 기록하며 이 경우에 우리는 시간 값을 알고 있어야 한다. 이 값은 context switch가 일어나더라도 유지되어야 한다.

(2) Stack

page number의 스택을 만든다. reference되면 스택의 맨 위로 올린다. 그러므로 victim page는 항상 맨 아래에 위치한다. 주로 double 링크드 리스트로 구현되며 update는 조금 비용이 발생하지만 replace를 위해 search할 필요가 없다.

LRU와 OPT는 stack algorithms라고 불린다. 이 알고리즘들은 belady’s anomaly를 보이지 않는다. 스택 알고리즘은 n프레임일 때의 page의 set은 항상 n+1프레임일때의 page의 subset임을 보여준다.

두 LRU구현방법은 TLB레지스터 이상의 하드웨어 assistance를 필요로한다.

우리가 만약 매 레퍼런스마다 interrupt를 사용한다면 유저 프로세스는 매우 느려질 것이다.

 

9.4.5 LRU-Approximation Page Replacement

많은 시스템은 reference bit 형태로 하드웨어의 도움을 필요로 한다. 페이지가 레퍼런스 된다면 레퍼런스 비트가 set된다. 처음에 모든 비트는 0으로 클리어되고 user프로세스가 실행되면 연관 비트가 1로 세트된다. 이를 통해 순서는 몰라도 사용여부를 판단할수 있다. 그리고 이것이 LRU를 Approximate하는 많은 알고리즘의 기본이 된다.

9.4.5.1 Additional-Reference-Bits Algorithm

각각의 페이지 테이블 엔트리에 8bit를 유지한다. 정기적으로 타이머 인터럽트가 발생하면 os는 레퍼런스 비트를 8bit의 high order bit에 값을 전달하고 기존의 값을 right shift시킨다. 이것은 8 time period의 reference history를 보여준다. 이 값을 해석하여 LRU처럼 수행할 수 잇다. bit의 수는 변화할 수 있으며 업데이트를 가능한 빨리 할 수 있도록 선택된다. 극단적인 경우에 이 숫자는 0이 될 수도 있으며 레퍼런스 비트 그 자체만을 이용한다. 이것이 second chance algorithm이다.

9.4.5.2 Second-Chance Algorithm(Clock Algorithm)

기본적으로는 FIFO와 동일하다. page가 선택되면 ref 비트를 검사하고 0이면 page out 시킨다. 하지만 1이라면 이 page에게는 second chance를 주고 ref bit를 클리어 한 후 다음 page를 검사한다. 또한 arrival time또한 새로운 값으로 설정한다. 이것은 보통 circular queue로 구현된다. 포인터는 다음에 replace될 페이지를 가리킨다. 프레임이 필요할 때 포인터는 ref 비트가 0인 것을 찾을때까지 반복하며 최악의 경우에는 한바퀴를 돌게 되고 FIFO와 동일해진다.

9.4.5.3 Enhanced Second-Chance Algorithm

reference bit와 modify bit의 쌍을 고려하여 clock 알고리즘을 적용한다. modify bit의 의미는 페이지 replace시 I/O 동작을 해야 한다는 의미이므로 I/O를 줄여서 성능을 향상시킬 수 있다.

 

9.4.6 Counting Based Page Replacement

ref 카운트를 이용한다.

-Least frequently used(LFU) 알고리즘 : active하게 사용될 경우 count값이 클 것이기 때문에 count가 적은 값을 이용한다. 문제점은 초기에 많이 사용되고 안사용될 경우 계속 남아있을 수 있다는 것인데 일정 시간마다 shift시키도록 하여 해결할 수 있다.

-MFU 알고리즘 : 가장 최근에 사용된 것이 카운트가 적을 것이라는 판단아래 교체하는 알고리즘이다.

둘다 OPT알고리즘과 유사하지 않고 비싸다.

 

9.4.7 Page-Buffering Algorithms

free frame들의 pool을 유지한다. 혹은 modified page의 list를 유지하고 페이징 디바이스가 아이들할때마다 디스크에 쓰여지고 bit를 reset 한다. clean할 확률을 증가시킨다.

또다른 방법은 free frame의 pool을 유지하고 페이지가 어느 프레임에 있었는지를 기억하는 것이다.

 

9.4.8 Applications and Page Replacement

특정 경우에 os의 virtual memory를 통하여 데이터에 접근하는 것이 직접하는 것 보다 나쁠 때가 있다. 그 예로 db가 있다. 이와같이 어플리케이션이 더 효율적이면 I/O를 위한 메모리의 양을 더 많이 준다. 또한 예전 데이터가 최근 데이터보다 더 많이 쓰일 확률이 있을 경우도 있다. 이러한 경우에는 MFU가 더 적합하다.

위 문제들 때문에 어떠한 os는 특정 프로그램들에게 disk partition을 logical block의 어레이처럼 사용할 수 있도록 해준다. 이 array를 raw disk라 하고 I/O를 raw I/O라 한다. 어떠한 시스템은 os의 file system보다 더 효율적이기 때문이다.

 

 

9.5 Allocation of Frames

다양한 변종들이 있지만 기본은 같다 : 사용자 프로세스는 어느 free frame에라도 할당될 수 있다.

 

9.5.1 Minimum Number of Frames

최소 할당 프레임의 이유는 성능과 관련있다. 각 프로세스의 프레임 수가 감소함에 따라 페이지 폴드 비율이 증가한다. 또한 instruction 끝나기 전에 page fault가 발생하면 인스트럭션이 재시작되어야 한다. 따라서 한 인스트럭션이 레퍼런스할 수 있는 모든 다른 페이지만큼의 프레임은 가지고 있어야 한다.

최악의 경우는 indirect방식으로 모든 virtual memory를 접근하는 경우인데 이 때는 모든 페이지가 프레임에 할당되어야 한다. 그래서 indirection counter를 이용하여 최대 수를 정해놔야 한다.

 

9.5.2 Allocation Algorithms

프로세스 별로 프레임의 수를 동등하게 할당하는 것을 equal allocation이라 한다. 그리고 프로그램의 size가 크면 더 많이 사용할 것이기 때문에 size별로 프레임을 제공하는 것이 propotional allocation이다. 이것은 프로세스들이 필요에 따라 프레임을 나누어 갖는 것이다.

두 경우 모두 멀티프로그래밍 레벨에 따라 할당받는 프레임의 수가 늘어나고 줄어든다.

만약 우선순위를 적용하고 싶다면 size뿐만 아니라 우선순위도 proptional 알고리즘에 적용시키면 된다.

 

9.5.3 Global vs Local Allocation

global replacement는 프로세스가 replacement frame을 모든 프레임에서 선택할 수 있다. local은 각자의 set에서만 할당할 수 있다.

global의 문제는 프로세스가 자신의 page-fault rate를 조절할 수 없다는 것이다. 다른 프로세스의 paging behavior에도 영향을 받는다. 반대로 local의 경우에는 자기 자신의 behavior에만 영향을 받는다. 하지만 로칼의 경우에는 어떠한 프로세스는 거의 사용되지 않음에도 불구하고 다른 프로세스의 프레임을 가져올 수 없다. 그래서 성능문제때문에 global이 더 흔히 사용된다.

 

9.5.4 Non-uniform Memory Access

일반적으로 메모리에 접근하는 속도는 다 유사할 것이라 생각하지만 특정 시스템에서는 다르다. 각각 CPU와 메모리를 가지는 시스템 보드가 bus로 연결된 시스템의 경우에는 어느 메모리에 프레임이 위치하냐에 따라 속도가 매우 다르다. 이러한 시스템을 non-uniform memory access(NUMA) system이라고 한다. 각 페이지가 어느 메모리의 프레임에 할당되었느냐가 중요하므로 스케쥴러는 각 프로세스가 마지막으로 실행한 CPU의 위치를 기억하고 메모리 관리 시스템은 CPU에 가까운 곳에 프레임을 할당하려고 한다. 그래서 솔라리스같은 os에서는 lgroup이라는 개념을 도입하여 같은 보드에 할당되도록 한다.

 

 

9.6 Thrasing

만약 어떠한 프로세스의 프레임의 수가 컴퓨터 아키텍쳐에 의해 요구되는 최소 숫자보다 아래로 떨어진다면 프로세스를 중단시키고 남은 페이지를 모두 page-out해야한다. 이것은 intermediate CPU scheduling의 swap in swap out level을 도입한다.

실행하기에 충분한 프레임을 가지지 못하는 프로세스나, 모든 페이지가 실제로 사용된다면 그 프로세스는 곧 페이지를 replace할 것이다. 그리고 계속 fault가 일어날 것이다. 실행보다 paging의 시간이 더 긴 이 상태를 thrashing 상태라고 한다.

 

9.6.1 Cause of thrashing

쓰래싱은 심각한 성능 문제를 가져온다.

os는 CPU utlization을 모니터하고 있으며 utlization이 너무 낮으면 멀티프로그래밍의 디그리를 증가시킨다. 글로벌 페이지 교체 알고리즘이 사용된다. 어떠한 프로세스가 프레임이 더 필요해 진다. 이것은 fault가 생기고 다른 프로세스의 page를 가져온다. 이 프로세스들은 페이지가 필요하고 또한 fault한다. 이 faulting process들은 paging device를 사용해야 하고 페이징 디바이스 사용을 위해 디바이스 큐에 쌓이게 되고 레디 큐는 empty되어 CPU utlization은 줄어든다. CPU스케쥴러는 cpu utlization 감소를 모니터하고 멀티프로그래밍의 디그리를 증가시킨다. 이에 따라 utlization은 더 감소하여 page fault rate는 극도로 치솟는다. 이로인해 effective memory access time이 증가한다. 이 문제 해결을 위해서는 멀티프로그래밍의 디그리를 감소시켜야한다. 이 경우에 local replacement algorithm을 이용하여 쓰래싱을 제한할 수 있다. 그러나 문제가 완전히 풀리지는 않는다. 페이징 디바이스의 큐에서 대부분의 시간을 쓰기 때문에 스래싱이 아니라도 effective access time이 증가한다.

스래싱을 막기 위해서는 프로세스가 필요한 만큼의 프레임을 제공해야 한다. working set strategy가 얼마나 많은 프레임을 프로세스가 실제로 사용하는지 보기 위해 시작되었으며 이것은 프로세스 실행의 locality model을 정의한다. locality는 실제로 같이 사용되는 페이지들의 집합이다.

우리가 현재 로칼리티의 크기를 수용할만한 충분한 프레임을 할당하지 않는다면 프로세스는 스래싱상태가 될것이다.

 

9.6.2 Working Set Model

working set model은 locality의 가정에 근거한다. 이것은 ∇라는 파라미터를 가지며 working set window를 정의한다. ∇ 페이지 레퍼런스를 검사하는 것이다. 최근의 ∇ 페이지 레퍼런스의 페이지의 집합이 working set이다. 그러므로 워킹 셋은 프로그램의 로칼리티의 approximation이다.

워킹 셋에서는 그 크기가 제일 중요하다. 각각의 프로세스의 워킹셋의 합이 프레임의 수를 초과하면 스래싱이 생긴다.

∇의 숫자가 정해지면 워킹셋 모델의 사용은 간단하다. OS는 각 프로세스의 워킹셋을 모니터하고 각각 프레임을 할당한다. 프레임이 남으면 새로운 프로세스를 시작한다. 워킹셋의 크기가 증가되어 프레임의 개수를 초과하면 프로세스를 중지시키고 swapped out 한다.

워킹셋 스트래티지를 이용해 가능한 멀티프로그래밍의 디그리를 증가시키면서 스래싱을 막을 수 있다. 그러므로 이것은 CPU 이용률을 최적화시킨다.

어려운 점은 워킹셋을 기록하는 것이다. 계속 변하기 때문이며 fixed interval timer와 ref bit를 이용하여 유사하게 구현할 수 있다. interval이 크면 불명확할 수 있으며 interval이 작으면 비용이 많이 든다.

 

9.6.3 Page-Fault Frequency

워킹 셋 모델보다 직접적으로 접근하는 것이 page-fault frequency(PFF)이다. 스래싱을 막는 것은 high page fault rate를 막는 것과 동일하므로 이에 의거하여 프레임의 수를 조절한다.

 

 

9.7 Memory Mapped Files

디스크의 파일을 접근할 때 시스템 콜과 디스크 접근을 필요로 한다. 다른 방법으로 file I/O를 메모리 접근처럼 하는 virtual memory technique이 있는데 그것이 memory mapping이다. I/O의 퍼포먼스를 증가시킬 수 있다.

 

9.7.1 Basic Mechanism

내일 이어서