가상 기억장치 (Virtual Memory)

Presentation on theme: "가상 기억장치 (Virtual Memory)"— Presentation transcript:

1 가상 기억장치 (Virtual Memory)
Lecture #9 가상 기억장치 (Virtual Memory)

2 페이징(Paging) 및 세그먼트(Seg- mentation) 기법의 특징(1)
페이징 및 세그먼트 기법의 특징 메모리 참조는 실행시간에 동적으로 물리적 주소로 변환된다 프로그램은 실행시간에 메모리에 적재되어 시작주소가 결정된다 프로세스는 스와핑(swapping)으로 인해 메모리 내에서 옮겨 다닌다 프로세스는 페이지 또는 세그먼트로 분할되어 메모리에 적재되므로 메모리에 연속적으로 적재될 필요가 없다

3 페이징(Paging) 및 세그먼트(Seg- mentation) 기법의 특징(2)
결 론 프로세스의 모든 부분이 실행되는 동안 메모리에 적재될 필요가 없다  부분 적재(Partial Loading) 가능 프로세스 실행은 한 시점에 다음에 수행할 명령어 또는 처리할 데이터가 메모리에 적재된 페이지 또는 세그먼트에 있으면 진행될 수 있다

4 프로세스 실행 과정 (1) 부분 적재를 이용한 프로세스 실행 과정 :
운영체제는 하나의 프로그램을 실행할 때에 프로그램 의 일부 프레임만을 메모리에 적재한다 (시작 부분을 포함) 페이지/세그먼트 테이블에서 적재된 페이지/세그먼트 에 대한 항목의 present bit 을 설정한다 Present Bit : 페이지/세그먼트 테이블 항목의 필드 각각의 페이지 또는 세그먼트가 메모리에 적재되었는지 여부를 표시한다 Resident Set : 하나의 프로세스에 대해 현재 메모리에 적재된 페이지 또는 세그먼트의 집합 메모리에 적재되지 않은 페이지 또는 세그먼트 부분을 접근하면 인터럽트(memory fault)가 발생한다

5 프로세스 실행 과정 (2) 부분 적재를 이용한 프로세스 실행 과정(계속) : 운영체제는 현재의 프로세스를 대기 상태로 전환한다
운영체제는 필요한 페이지 또는 세그먼트을 메모리에 적재하기 위해 디스크 읽기 요구를 발생시킨다 현재의 프로세스는 디스크 읽기 요구가 완료될 때까지 대기 상태로 있는다 디스크 입출력이 실행되는 동안에 다른 프로세스가 디스패치되어 실행된다 디스크 입출력이 완료되면 인터럽트가 발생한다 운영체제는 이 인터럽트를 처리하는 동안 대기 상태에 있는 프로세스를 준비 상태로 전환한다

6 부분 적재(Partial Loading)의 장점
더 많은 프로세스가 메모리에 적재될 수 있다 각 프로세스의 일부 프레임만을 메모리에 적재하므로 더 많은 프로세스를 메모리에 적재할 수 있다 메모리에 많은 프로세스가 적재되면 모든 프로세스가 대기 상태로 전환될 가능성이 적어진다 프로세스가 메모리 크기보다 더 큰 경우에도 실행할 수 있다 논리적 주소를 위해 물리적 주소에 필요한 비트 수보다 더 많은 비트를 사용할 수 있다

7 가상 기억장치(Virtual Memory) (1)
‘물리적 주소’보다 더 큰 비트 수를 가진 ‘논리적 주소’를 사용 예: 16 비트의 물리적 주소를 사용하는 경우 64 KB(2^16=64)의 물리적인 메모리을 접근할 수 있다 페이지 크기를 1KB로 정하면 오프셋을 나타내기 위해 10 비트가 필요하다 물리적으로 페이지를 나타내기 위해 6 비트를 이용한다 논리적 주소에서 페이지 번호 부분은 6 비트 보다 더 많은 비트 수를 이용하여 나타낼 수 있다

8 가상 기억장치(Virtual Memory) (2)
논리적 주소로 접근할 수 있는 기억공간 보조기억장치(예: 디스크)에 유지된다 단지 필요한 프레임만을 주기억장치에 적재한다 더 나은 성능을 위하여 가상 기억장치는 파일 시스템을 통해 디스크에 저장되지 않고 스왑 공간(swap space)이라는 특별한 공간에 저장된다 더 큰 저장 블록을 사용한다 File lookups와 간접 할당 방식 등은 사용하지 않는다

9 가상 기억장치(Virtual Memory) (3)
물리적 기억장치 물리적 주소로 접근할 수 있는 기억공간 물리적으로 DRAM 장치에 저장된다 논리적 주소와 물리적 주소의 변환 메모리 관리 하드웨어가 페이지/세그먼트 테이블을 접근하여 논리적 주소를 물리적 주소로 변환한다

10 Trashing 가능성(1) 가능한 많은 프로세스를 메모리에 적재하기 위해서는 각 프로세스의 필요한 프레임만을 메모리에서 유지 하여야 한다 메모리가 모두 사용되고 있는 경우 : 운영체제가 실행중인 프로세스가 요구한 프레임을 위해 메모리에 있는 다른 프로세스의 프레임이나 실행중인 프로세스의 프레임을 swapping 하여야 한다(전역 교체 / 지역 교체) swapping 된 프레임이 다음에 사용할 예정이면 다시 swapping이 발생한다

11 Trashing 가능성(2) 빈번한 프레임 swapping 은 trashing 현상을 발생시킨다
CPU가 사용자 프로그램 실행보다 프로세스 swapping에 대부분의 시간을 사용하게 된다 CPU의 이용률이 급격하게 떨어진다 pp.434, 그림 8.19

12 작업 집합(Working Set) 모델 기법(1)
접근 지역성(locality of references) 원리: 프로세스 내의 메모리 접근은 하나의 메모리 영역에 집중되는 경향이 있다 pp 392, 그림 8.1 프로세스가 실행될 때에 짧은 기간 동안에는 프로세스의 기억공간의 일정한 부분만을 필요로 한다 작업 집합(Working Set) 최근의 k 개의 페이지 참조에 포함되는 페이지들의 집합 프로그램 지역성(locality)의 근사값 pp. 428, 그림 8.17

13 작업 집합(Working Set) 모델 기법(2)
운영체제는 각 프로세스에게 작업 집합 크기 만큼의 메모리를 할당한다 가능한 다중 프로그래밍 정도를 높인다 Thrashing 발생을 줄인다 프로세스의 작업 집합은 계속하여 변하므로 작업 집합을 추적하기 어렵다 작업 집합의 크기를 결정하기 어렵다 pp. 429, 그림 8.18

14 페이지 부재 빈도 (Page Fault Frequency) 기법
페이지 부재 비율의 상한과 하한을 설정하여 페이지 부재 빈도를 관리하는 기법 페이지 부재 비율이 상한을 넘으면 더 많은 프레임을 할당한다 페이지 부재 비율이 하한 이하로 내려가면 프레임을 회수한다 직접적으로 thrashing을 방지하면 페이지 부재 비율을 예측하고 관리하는 기법 pp. 403, 그림 8.9

15 가상 기억장치의 요구 사항 하드웨어 요구 사항 운영체제 요구 사항
메모리 관리 하드웨어는 페이징 또는 세그먼트 기법을 지원하여야 한다 운영체제 요구 사항 운영체제는 주기억장치와 보조기억장치 사이에 페이지 또는 세그먼트를 이동하는 것을 관리 하여야 한다

16 가상 기억장치의 하드웨어 구현 가상 기억장치의 하드웨어 구현 기법 페이징 기법(Paging)
세그먼트 기법(Segmentation) 페이징 & 세그먼트 결합 기법(Paged Segmentation)

17 가상 기억장치의 페이징 기법(1) 페이징 기법에서는 프로세스 별로 고유의 페이지 테이블이 생성된다
각각의 페이지 테이블 항목은 다음과 같이 구성된다 Present Bit Modified Bit Other Control Bits Frame Number

18 가상 기억장치의 페이징 기법(2) Present bit Modified bit Other control bits
해당 페이지가 메모리에 존재하는지 여부를 표시한다 만약 메모리에 있으면 frame number는 메모리에서 페이지가 배치된 프로임 번호를 저장한다 만약 메모리에 없으면 frame number는 디스크에서의 페이지 주소를 저장한단 Modified bit 해당 페이지가 메모리에 적재된 이후로 수정되었는지 여부를 표시한다 만약 수정되지 않았으면 swapping 할 때에 디스크에 현재 페이지를 쓸 필요가 없다 Other control bits 보호(protection) 목적으로 이용 a read-only/read-write bit protection level bit: kernel page or user page

19 페이징 시스템에서의 주소 변환

20 페이지 공유(1) 다른 사용자 사이에 동일한 프로그램 코드를 공유 한다면 메모리에 단지 하나의 프로그램 코드 복사본 만을 유지할 수 있다 공유 코드는 재진입 가능하여야 한다(reentrant) 2 개 이상의 프로세스가 동일한 프로그램 코드를 수행하여야 한다 페이징 시스템에서는 페이지 공유 공유 프로그램 코드에 대하여 메모리에 하나의 복사본만 둔다 공유 프로세스의 페이지 테이블 항목은 동일한 프레임을 가리키도록 프레임 번호를 저장한다 각 프로세스가 필요로 하는 데이터에 대해서는 프로세스별로 개별적인 데이터 페이지를 유지하여야 한다

21 페이지 공유(2): a text editor

22 TLB(Translation Lookaside Buffer)
페이지 테이블이 메모리에 있기 때문에 각각의 가상 기억장치에 대한 접근은 두 번의 물리적인 기억장치 접근을 요구한다 페이지 테이블 항목에 대한 접근 데이터에 대한 접근 메모리 접근 지연이 발생한다 TLB: Translation Lookaside Buffer 페이지 테이블 접근에 따른 지연 문제를 해결하기 위한 cache memory 가장 최근 사용된 페이지 테이블 항목을 유지한다 주기억장치의 cache memory와 유사하게 동작

23 Translation Lookaside Buffer 사용

24 TLB - 부연 설명 Associative mapping hardware를 사용
새로운 프로세스가 실행 상태가 될 때마다 TBL은 초기화한다 CPU는 각각의 가상 기억장치 참조에 대해 두 단계의 cache를 사용한다 첫번째- 논리적 주소를 물리적 주소로 변환하기 위해 TLB을 사용 두번째- 물리적 주소를 이용하여 데이터를 접근할 때에 주기억장치 cache memory를 사용

25 페이징 시스템의 문제점 대부분의 컴퓨터 시스템은 매우 큰 가상 주소 공간을 지원한다
논리적 주소를 위해 32~ 64 bits 주소를 사용 만약 32 bit 논리적 주소와 4KB의 페이지크기를 사용 한다면 하나의 페이지 테이블은 2^{20} 항목을 가질 수 있다 전체 페이지 테이블은 너무 많은 메모리를 사용한다 페이지 테이블도 가상 기억장치를 사용하여야 한다 프로세스가 실행 상태가 되면 현재 실행중인 페이지를 포함하여 페이지 테이블의 일부 항목만 메모리에 유지된다

26 다단계 페이지 테이블 (Multilevel Page Tables) (1)
일반적으로 페이지 테이블은 여러 개의 페이지에 저장된다 페이지 테이블을 다단계계층 구조로 구성하면 접근이 용이하다 다단계 페이지 테이블 When 2 levels are used (ex: 386, Pentium), the page number is split into two numbers p1 and p2 p1 indexes the outer page table (directory) in main memory who’s entries points to a page containing page table entries which is itself indexed by p2. Page tables, other than the directory, are swapped in and out as needed

27 다단계 페이지 테이블 (Multilevel Page Tables) (2)

28 역 페이지 테이블 (Inverted Page Table) (1)
Inverted Page Table (IPT) 큰 용량의 페이지 테이블 문제를 해결하기 위해 제시 전체 시스템을 위해 단지 하나의 IPT을 유지한다 IPT의 각 항목은 물리적 메모리의 한 프레임에 대한 정보를 저장한다 IPT 항목은 프레임에 배치된 논리적 페이지에 대한 정보를 유지한다 IPT는 전체 프레임 개수만큼의 항목을 가진다 논리적 주소를 물리적 주소를 변환할 때 논리적 주소를 가진 IPT 항목을 찾으면 그 항목의 인덱스가 물리적 프레임 번호가 된다 페이지 테이블 검색과는 역으로 검색한다

29 역 페이지 테이블 (Inverted Page Table) (2)
The process ID with the virtual page number could be used to search the IPT to obtain the frame # For better performance, hashing is used to obtain a hash table entry which points to a IPT entry

30 페이지 크기 문제 (1) 페이지 크기는 하드웨어에 의해 정의된다 정확하게 페이지 크기를 결정하는 것은 어렵다
페이지 크기를 2의 승수로 하면 논리적 주소를 물리적 주소로 효율적으로 변환할 수 있다 정확하게 페이지 크기를 결정하는 것은 어렵다 작은 페이지 크기를 사용하면 내부 단편화를 줄일 수 있으나, 전체 페이지 수가 늘어나 페이지 테이블이 커진다 큰 페이지 크기를 사용하면 페이지 테이블 크기가 작아진다 디스크의 블록 단위 데이터 입출력에 적합 TBL hit ratio을 높일 수 있다 내부 단편화가 커질 수 있다 큰 페이지 크기가 효율적

31 페이지 크기 문제 (2) 일반적으로 1KB에서 4KB 사이의 페이지 크기를 사용한다
최근 몇몇 프로세서는 다중 페이지 크기를 지원한다 Pentium supports 2 sizes: 4KB or 4MB R4000 supports 7 sizes: 4KB to 16MB

32 가상 기억장치의 세그먼트 기법 세그먼트 기법에서 각 프로세스 자신의 세그먼트 테이블을 가진다
세그먼트 테이블의 각 항목은 다음과 같이 구성된다 Present Bit Modified Bit Other Control Bits Segment Base Length

33 세그먼트 기법의 주소 변환

34 세그먼트 기법 - 부연 설명 각 세그먼트 테이블 항목은 세그먼트의 시작 주소와 길이를 저장한다
세그먼트는 필요에 따라 동적으로 변할 수 있다 접근 주소의 정상 여부는 길이 필드를 이용하여 쉽게 검사할 수 있다 동적 길이의 세그먼트는 외부 단편화를 야기하고 swapping 작업을 더욱 어렵게 한다 세그먼트 단계에서의 보호 및 공유 기능은 자연스럽게 제공할 수 있다 세그먼트는 프로그래머가 볼 수 있다 프로그램의 논리적 모듈 구조를 세그먼트로 쉽게 구현할 수 있다

35 세그먼트 공유 (1) 동일한 프로그램 코드를 실행시키는 프로세스는 프로그램 코드를 공유할 수 있다
2 개의 다른 프로세스의 세그먼트 테이블 항목에 동일한 물리적 위치를 저장함으로써 세그먼트를 공유할 수 있다 예: 다수의 사용자가 텍스트 편집기의 코드를 공유할 수 있다 텍스트 편집기 코드는 단지 하나의 복사본만이 메모리에 유지된다 각 사용자는 필요에 따라 개별적인 데이터 세그먼트를 유지하여야 한다

36 세그먼트 공유 (2)

37 페이징과 세그먼트 기법의 결합(1) 페이지화된 세그먼테이션(Paged Segmentation)
페이징 기법과 세그먼트 기법의 장점을 결합하기 위하여 몇몇 프로세서와 운영체제는 세그먼트를 페이지 단위로 분할한다 각각의 프로세스는 다음과 같은 배치 테이블을 가진다 하나의 세그먼트 테이블 여러 개의 페이지 테이블: 세그먼트 별로 하나의 페이지 테이블

38 페이징과 세그먼트 기법의 결합(2) 가상 주소의 구성 segment number:
세그먼트 테이블에서의 인덱스 세그먼트 테이블 항목은 세그먼트를 위한 페이지 테이블의 시작 주소를 저장한다 page number: 프레임 번호를 찾아오기 위한 페이지 테이블의 인덱스 offset: 프레임 내에서의 위치

39 페이지화된 세그먼테이션의 주소 변환

40 운영 제체의 메모리 관리 SW 메모리 관리 소프트웨어는 하드웨어의 구성에 따라 기능이 결정된다
페이징 세그먼테이션 페이지화된 세그먼테이션 순수한 세그먼테이션 시스템은 드물다 일반적으로 세그먼트는 페이지로 분할된다 메모리 관리 소프트웨어는 세그먼트의 페이지를 관리하여야 한다 좋은 성능을 얻기 위해서는 낮은 페이지 부재율을 유지하여야 한다

41 적재 기법(Fetch Policy) 하나의 페이지를 메모리에 적재할 때를 결정하는 기법 Demand paging
페이지에 대한 접근이 발생하였을 때에 페이지를 메모리에 적재한다 (i.e: paging on demand only) 프로세스가 실행을 시작할 때에 페이지 부재율이 높지만 많은 페이지가 적재될수록 페이지 부재율은 낮아진다 Prepaging 필요한 페이지 보다 더 많은 페이지를 적재하는 기법 참조 지역성을 이용하여 디스크에서 연속적으로 저장된 페이지를 미리 메모리에 적재한다 효율성이 일정하지 않다 접근하지 않는 페이지를 종종 적재하게 된다

42 배치 기법(Placement policy)
프로세스의 페이지를 실제 메모리에 적재할 위치를 결정하는 기법 순수 세그먼테이션 시스템의 경우: 동적 분할 기법과 동일 first-fit, next-fit, best-fit 등의 기법을 고려 페이징 또는 페이지화된 세그먼테이션 시스템의 경우: 모든 메모리 프레임이 동일하므로 페이지가 어느 곳에 배치되더라도 아무런 영향이 없다 하드웨어가 페이지를 배치할 위치를 결정한다

43 재배치 기법(Replacement Policy)(1)
새로운 페이지를 위한 메모리를 확보하기 위해 swapping할 페이지를 결정하는 기법 사용 가능한 메모리가 없을 때에 swapping 요구 재배치할 페이지를 결정하여야 한다 운영체제는 메모리에 있는 모든 페이지를 재배치하기 위해 선택할 수 없다 몇몇 프레임은 잠겨있어(locked) swapping할 수 없다 대부분의 커널 프레임이나 I/O buffer 프레임은 재배치 않지 않는다(locked)

44 재배치 기법(Replacement Policy)(2)
운영체제는 재배치할 페이지 집합을 다음과 같이 고려하여야 한다 페이지 부재가 발생한 프로세스의 페이지 집합 잠겨있지 않은 프레임에 있는 페이지 집합 resident set management strategy 재배치하기 위해 고려할 페이지 집합을 결정 각 프로세스에 얼마나 많은 페이지 프레임을 할당할 것인지를 결정

45 기본적인 재배치 알고리즘 최적의 재배치 알고리즘은 재배치하기 위한 페이지로 다음에 접근하기 위한 시간이 가장 긴 페이지를 선택 하여야 한다 가장 적은 페이지 부재율을 보인다 미래의 접근 가능성을 알아야 하므로 구현하기 어렵다 기본적인 재배치 알고리즘 Least recently used (LRU) First-in, first-out (FIFO) Clock

46 LRU(Least Recently Used) 기법 (1)
가장 긴 시간동안 접근하지 않은 페이지를 재배치하는 기법 참조 지역성의 원리에 의해 오랫동안 접근하지 않은 페이지가 가까운 장래에 접근하지 않는 페이지가 된다 거의 최적에 가까운 성능을 보인다 예제: A process of 5 pages with an OS that fixes the resident set size to 3

47 LRU(Least Recently Used) 기법 (2)
각 페이지에 대해 접근된 시간을 저장하여야 한다 LRU 기법은 가장 적은 시간을 가진 페이지를 재배치 페이지로 선택한다 많는 비용의 하드웨어 큰 오버헤드를 요구한다 메모리 접근이 발생할 때마다 해당 페이지의 접근 시간을 수정하여야 한다

48 FIFO(First-In First-Out) 기법
적재된 순서에 의해 재배치 페이지를 결정하는 기법 하나의 프로세스에 할당된 페이지 프레임을 순환 버퍼 형태로 유지 사용 가능한 버퍼가 없을 때에 가장 오래된 페이지를 재배치한다 자주 사용되는 페이지가 종종 오래된 페이지일 가능성이 높아 재배치가 자주 발생한다 구현하기 쉽다

49 LRU와 FIFO의 비교 LRU 기법은 페이지 2와 5가 자주 사용하는 페이지로 인식하나, FIFO 기법은 인식하지 못한다

50 Clock 기법 (1) 재배치하기 위해 고려할 페이지 프레임 집합을 순환 버퍼 형태로 유지한다
버퍼 안에서 한 페이지가 재배치되면 포인터는 다음 프레임을 가리키도록 한다 각 프레임의 use bit을 다음의 경우에 1로 설정한다 프레임에 하나의 페이지가 처음 적재되는 경우 프레임에 적재된 페이지가 접근되는 경우 재배치가 요구되면 포인터가 가리키고 있는 프레임 에서 시작하여 use bit가 0인 프레임을 재배치 한다 재배치를 위해 탐색하는 동안 1인 use bit를 0으로 설정한다

51 Clock 기법 (2): 예제

52 Clock 기법과 FIFO, LRU 기법의 비교(1)
‘*’ 표시가 use bit가 1임을 나타낸다 Clock 기법은 자주 접근되는 페이지에 대해 use bit를 1로 설정하여 보호한다

53 Clock 기법과 FIFO, LRU 기법의 비교(2)
수리적인 실험에서는 Clock 기법의 성능이 LRU 성능에 근접함을 보인다 각 프로세스에 할당된 프레임 수로 고정하거나 페이지 부재를 발생시킨 프로세스 내의 페이지만을 재배치하는 경우에 대해 실험을 하였을 때: 각 프로세스에 적은 수의 프레임(6 to 8)이 할당되는 경우에 LRU와 FIFO 사이에 페이지 부재율이 거의 2배의 차이가 발생한다 더 많은 프레임(12개 이상)을 할당하는 경우에는 페이지 부재율이 비슷하다 이 경우, 더 많은 메모리를 요구한다

54 페이지 버퍼링(Page Buffering) (1)
재배치되는 페이지는 FIFO와 같은 재배치 알고리즘의 성능 저하를 막기 위해 잠시 동안 메모리에 보관한다 버퍼링되는 재배치 페이지는 두 개의 포인터 리스트를 이용하여 관리한다 포인터 리스트의 각 항목은 재배치되는 프레임의 번호를 저장한다 free page list : 메모리에 적재된 후에 수정된 적이 없는 프레임의 리스트 – swapping 할 필요가 없다 modified page list: 메모리에 적재된 후에 수정된 프레임의 리스트 – 디스크에 재저장하여야 한다

55 페이지 버퍼링(Page Buffering) (2)
재배치되는 프레임은 두 개의 리스트 중에 하나에 추가되고 해당되는 페이지 테이블 항목의 present bit을 0 으로 설정한다 해당 페이지는 아직 프레임에 배치되어있다 페이지 부재가 발생할 때에 두 개의 리스트를 검색하여 원하는 페이지가 아직 메모리에 있는지 검사한다 만약 메모리에 있으면 해당된 페이지 테이블의 present bit를 1로 설정하고 관련된 버퍼링 리스트에 저장된 항목을 삭제한다 만약 메모리에 없으면 free frame list의 첫번째 frame에 원하는 페이지를 적재한다 – only overwriting Modified frame list에 있는 프레임은 개별적으로 백업되는 것이 아니라 그룹 단위로 디스크에 백업된다

56 클리닝 기법(Cleaning Policy)
수정된 페이지를 디스크에 백업(write-back)할 때를 결정하는 기법 Demand cleaning 페이지가 차지하고 있는 프레임이 재배치되기 위해 선택되었을 때에 백업하는 기법 페이지 부재를 처리하기 위해 두 페이지의 전송을 요구 Precleaning 수정된 페이지를 프레임이 필요로 하기 전에 batch 형태로 백업하는 기법 재배치되기 전에 다시 수정되는 경우에는 오버헤드가 크다 페이지 버퍼링 기법의 성능을 향상 시킬 수 있다 modified frame list에 있는 페이지를 batch 형태로 주기적으로 백업하고 free frame list로 옮긴다