제 6 장 가상 기억 장치의 구성 Section 1 개 요 Section 2 페이징 기법 Section 3 세그먼테이션 기법

Presentation on theme: "제 6 장 가상 기억 장치의 구성 Section 1 개 요 Section 2 페이징 기법 Section 3 세그먼테이션 기법"— Presentation transcript:

1 제 6 장 가상 기억 장치의 구성 Section 1 개 요 Section 2 페이징 기법 Section 3 세그먼테이션 기법

2  가상 기억 장치(virtual memory) 1961년  2단계 기억장치
Section 1 개요  가상 기억 장치(virtual memory) 1961년  2단계 기억장치 ▸1차 기억장치: 프로세스가 실행되고, 실행중인 프로세스에 의해 참조되는 자료를 저장하는 주기억장치 ▸2차 기억장치: 주기억장치에 저장할 수 없는 프로그램과 데이터를 저장할 수 있는 보조기억 장치, 가상기억 장치 그림 6-1 2단계 기억 장치

3 ● 사용자가 보조 기억 장치의 용량에 해당하는 커다란 기억 장소를 갖고 있는 것처럼 생각하고 프로그램 작성 가능.
Section 1 개요  가상 기억 장치 ● 사용자가 보조 기억 장치의 용량에 해당하는 커다란 기억 장소를 갖고 있는 것처럼 생각하고 프로그램 작성 가능. ● 사용자의 오버레이 구조 해결 가능. ● 이는 다중 프로그래밍의 등장으로 사용 기억장치 양의 증대를 꾀할 수 있도록 하는 방식.  가상 주소와 실 주소 ● 가상 주소(virtual address) : 수행 중인 프로세스가 참조하는 페이지 주소 즉,. 보조기억 장치 번지를 가상 주소라고 하며, 이들 번지의 집합을 가상 주소 공간(virtual address space)이라 한다. ● 실 주소(real address) 또는 물리 주소(physical address): 주기억장치의 사용 가능한 주소, 이들 번지의 집합을 실 주소 공간(물리주소 공간 : real address space) 이라 한다.

4 ● 가상 주소 G 내의 주소 수는 |G|로 표시하고 실 주소 H 내의 주소 수는 |H|로 표시, 실제로 구현되는 가상기억 장치
Section 1 개요  가상 주소수와 실 주소 수 및 크기 ● 가상 주소 G 내의 주소 수는 |G|로 표시하고 실 주소 H 내의 주소 수는 |H|로 표시, 실제로 구현되는 가상기억 장치 ● 시스템에서는 |G| ＞ |H|. ● 가상 주소 변환(VAT : Virtual Address Translation) 기법 : 가상 주소를 실 주소로 변환하는 주소 변환 함수 Bt ● 세그먼트(segment), 프로그램을 가변크기로 나눈 것 ● 페이지(page) : 프로그램을 고정된 크기로 나눈 것 ● 페이징(paging), 세그먼테이션(segmentation) :  주 기억 장치와 보조기억 장치 사이에서 세그먼트나 페이지를 교환하면서 프로그램을 수행하기 위해 가상주소에서 물리 주소 (실 주소)로 실행시간(runtime)에 매핑(바인딩)하는 기법

5 1. 가상 주소 변환 1) 주소 공간 사상과정 ● 가상기억 장치 시스템은 이름 공간(name space), 가상주소,
Section 1 개요 1. 가상 주소 변환 1) 주소 공간 사상과정 ● 가상기억 장치 시스템은 이름 공간(name space), 가상주소, 물리주소를 구별. ● 심벌 이름에서 가상주소로 가상주소에서 물리주소로의 매핑(바인딩)하는 기법이 제공. 이 기법이 페이징(paging)과 세그먼테이션(segmentation) 그림 6-2 이름 공간, 가상 주소, 물리 주소로의 사상과정

6 1. 가상 주소 변환 2) 가상주소 변환(VAT) 기법  Bt : 가상 주소 공간 → 물리 주소 공간 ∪ {Ω}
Section 1 개요 1. 가상 주소 변환 2) 가상주소 변환(VAT) 기법  Bt : 가상 주소 공간 → 물리 주소 공간 ∪ {Ω} 그림 6-3 가상 주소 공간에서 실 주소로 공간으로의 주소 사상

7 1. 가상 주소 변환 3) 인위적인 연속성(artificial continuity)
Section 1 개요 1. 가상 주소 변환 3) 인위적인 연속성(artificial continuity)  모든 프로세스의 가상 주소 공간상의 연속된 페이지 주소들은 주 기억 공간상의 페이지 프레임 주소가 반드시 연속적일 필요가 없다는 의미 그림 6-4 인위적 연속성

8 ● 세그먼트는 <세그먼트번호, 오프 셋> 하나의 순서쌍으로 ● 세그먼테이션에서는 각 세그먼트 크기가 다르므로
Section 1 개요 2. 페이징과 세그먼테이션 비교 1) 세그먼테이션 ● 세그먼트는 적재되거나 적재되지 않은 프로그램 부분의 가변크기로 프로그래머가 정의 ● 세그먼트는 <세그먼트번호, 오프 셋> 하나의 순서쌍으로 된 가상 주소를 통해 참조 ● 세그먼테이션에서는 각 세그먼트 크기가 다르므로 가변크기 기억장치 할당에서처럼 외부 단편화가 발생 2) 페이징 ● 페이지는 하나의 세그먼트 내에서 마치 주소 셀(cell)처럼 사용되는 것과 같이 고정된 크기의 단일 성분의 주소를 사용 ● 페이지는 <페이지번호, 오프 셋> 하나의 순서쌍으로 된 가상 주소를 통해 참조 ● 페이징에서는 각 페이지의 크기가 같으므로 외부 단편화가 없고 마지막 페이지에 대하여 내부 단편화가 발생

9 Section 1 개요 2. 페이징과 세그먼테이션 비교 그림 6-5 페이지와 세그먼트 구조

10 Section 2 페이징 기법 1. 페이징 주소변환 방법 ● 페이징 시스템은 가상주소 0에서 G-1까지 각각의 페이지 크기가 c=2h인 n=2g 개 페이지 집합으로 사상, 프로세스는 G개의 가상주소 중에서 일부분인 k 개만큼만 사용 ● 주 기억 장치 주소 공간은 각 페이지 프레임의 크기가 c=2h이고, m=2i인 페이지 프레임의 집합. 프로세스에 할당된 주 기억 장치 크기는 H=2h+j 그림 6-6 페이지 프레임으로 분할된 주기억장치

11 1. 페이징 주소변환 방법 1) 페이징 가상 주소 변환  주소변환 Bt은 메모리 관리 장치(MMU)에 의해 수행
Section 2 페이징 기법 1. 페이징 주소변환 방법 1) 페이징 가상 주소 변환  주소변환 Bt은 메모리 관리 장치(MMU)에 의해 수행 그림 6-7 페이징에서의 주소변환 과정

12 1. 페이징 주소변환 방법 2) 페이지 부재 처리 Section 2 페이징 기법
● 프로세스가 페이지를 참조. 페이지 부재를 발생시킨 프로세스는 중단. ● 페이지 보호비트를 검사. ● 기억장치 관리자는 가상기억 장치에서 가용 페이지를 찾음. ● 페이지가 주기억장치에 적재되고 상황에 따라 다른 페이지가 해제되기도 함. ● 기억장치 관리자의 페이지 테이블은 갱신. ● 프로세스는 중단되었던 시점에서 다시 시작. 그림 6-8 페이지 부재시 처리과정

13 2. 연관사상/순수 페이징 혼용 방법  보다 적당한 비용으로 연관사상의 장점을 살릴 수 있는 절충 방안.
Section 2 페이징 기법 2. 연관사상/순수 페이징 혼용 방법  보다 적당한 비용으로 연관사상의 장점을 살릴 수 있는 절충 방안.  연관 사상표, 변환 버퍼(TLBs:Translation Look-aside Buffers) : 국부성에 의거, 최근에 가장 많이 참조된 페이지  페이지 사상표 : 연관 사상표에서 제외된 나머지 페이지  동적 주소변환 과정 ● 프로세스는 가상 주소 G=(p, d)를 참조하여 연관 사상표를 먼저 탐색. ● 페이지 p가 연관 사상표에 있다면, p'+ d = k로 물리 주소 k생성. ● 연관 사상표에 페이지 p가 없으면, 페이지 사상표를 탐색하여 직접 사상 방법에 의해 실 주소 k를 생성. ● 연관 기억장치 TLB는 이 정보를 포함하도록 갱신 ● 운영 체제가 연관 사상표에 페이지 사상표를 잘못 유지하면, 연관 사상표를 1차 탐색하고 페이지 사상표를 2차 탐색하므로 오히려 성능저하.

14 그림 6-9 연관/직접 사상을 혼용한 페이지주소 변환 과정
Section 2 페이징 기법 2. 연관사상/순수 페이징 혼용 방법 가상주소 G = (p, d) 물리 주소 k = p’+ d k 그림 6-9 연관/직접 사상을 혼용한 페이지주소 변환 과정

15 3. 페이지 테이블 구조 1) 계층구조 페이지 테이블(hierarchical page tables)
Section 2 페이징 기법 3. 페이지 테이블 구조 1) 계층구조 페이지 테이블(hierarchical page tables) ● 가상 주소 공간을 여러 단계의 페이지 테이블로 나누는 것. ● p1은 외부(outer) 페이지 테이블에 대한 인덱스, p2는 외부(outer) 페이지 테이블 내에서의 오프셋,변위 d는 페이지 내에서의 오프셋 그림 6-10(a) 2단계 페이지 테이블 구조

16 3. 페이지 테이블 구조 2) 해시 페이지 테이블(hashed page tables) 체인(chain) 형태의 연결 리스트
Section 2 페이징 기법 3. 페이지 테이블 구조 2) 해시 페이지 테이블(hashed page tables) ● 가상 페이지 번호가 페이지 테이블에 해싱(hashing) ● 페이지 테이블은 같은 위치에 해시되는 항목들에 대해 체인(chain) 형태의 연결 리스트 그림 6-10(b) 해시 페이지 테이블 구조

17 3. 페이지 테이블 구조 3) 역 페이지 테이블(inverted page tables) Section 2 페이징 기법
● 페이지 테이블 항목 검색을 최소한 하나 이하로 제한하기 위해 인덱스 된 해시 테이블을 사용 ● 주소변환 과정은 pid와 페이지 번호 p를 사용하여 페이지테이블을 검색. 일치되는 페이지를 찾으면 색인에 변위를 더하여 해당 페이지 프레임의 물리 주소를 계산 그림 6-10(c) 역 페이지 테이블 구조

18 4. 페이징 시스템의 공유  공유(Shared) 코드 ● 텍스트 편집기, 컴파일러, 윈도우 시스템 등
Section 2 페이징 기법 4. 페이징 시스템의 공유  공유(Shared) 코드 ● 텍스트 편집기, 컴파일러, 윈도우 시스템 등 읽기전용 (reentrant) 코드는 여러 프로세스에 의해 공유 ● 공유된 코드는 모든 프로세스의 가상 주소공간의 동일 위치에 존재  개인(Private)코드와 데이터 ● 각 프로세스는 분리된 코드와 데이터를 가짐 ● 개인 코드와 데이터에 대한 페이지는 가상주소 공간의 임의위치에  존재

19 Section 2 페이징 기법 4. 페이징 시스템의 공유 그림 6-11(a) 페이징 시스템에서의 공유

20 4. 페이징 시스템의 공유 Section 2 페이징 기법  공유(Shared) 예
● 세 개의 프로세스 p1, p2, p3이 각각 자신의 페이지 테이블에 공유하려 는 편집기 1,2,3에 대한 물리 주소를 동일하게 갖도록 함으로써 공유 그림 6-11(b) 페이징 시스템에서의 공유 예

21

22  가상 주소 : G = (s, d) s : 세그먼트 번호, d : 변위
Section 3 세그먼테이션 기법 1. 세그먼테이션 가상주소 변환  가상 주소 : G = (s, d) s : 세그먼트 번호, d : 변위  Bt : 세그먼트 공간 x 오프셋 공간 -> 물리 주소 공간 ∪ {Ω} Bt : [0:G-1] → <U, V)∪ {Ω} S: 세그먼트 이름 -> 세그먼트 번호 Bt (S (segmentName), j) = k N: 오프셋 이름 -> 오프셋 주소 Bt (S (segmentName), N (offsetName) ) = k ● S-map 은 세그먼트 이름을 세그먼트 번호로 번역 ● N-map은 심벌 오프셋을 수치 오프셋으로 번역. ● STBR( Segment Table Base Register) 주 기억 장치 내 세그먼트 테이블의 위치. ● STLR(Segment Table Length Register) 세그먼트 테이블 전체  길이. 세그먼트 번호 s가 < STLR이면 정상

23 세그먼트기법의 가상주소 V=(s,d) 세그먼트번호 s 변위 d 각 세그먼트는 고유한 명칭과 길이를 가짐

24 Section 3 세그먼테이션 기법 1. 세그먼테이션 가상주소 변환 그림 6-15 세그먼테이션에서의 주소 변환 과정

25 세그먼트기법의 주소변환 가상주소 세그먼트번호s 변위d b b+s d s s +d ´ r 사상테이블 테이블의 시작주소 b 실주소

26 2. 직접 사상방법 1) 정상적일 때 주소변환 과정 Section 3 세그먼테이션 기법
● 실행되는 프로세스는 가상 주소 G = (s, d)를 참조하여, ● 세그먼트 s에 세그먼트 사상표 시작점 레지스터 b와 더해져 s'를 얻음. ● 변위 d는 s'와 더해져 실제주소 k = s’ + d 생성. 그림 6-16(a) 세그먼트 기법에서 주소 변환 예

27 2. 직접 사상방법 2) 예외 발생 상황에 따른 주소변환 과정 Section 3 세그먼테이션 기법
r=0 세그먼트가 주기억 장치 내에 없는 경우 r=1 세그먼트가 주기억 장치 내에 있는 경우 R : read access W : write access E : execute access A : append access 액세스 유형 판독 기록 수행 첨가 약자 R W E A 설명 읽을 수 있다 수정 할수 있다 실행 할수 있다 끝에 정보 첨가가능

28 Section 3 세그먼테이션 기법 2) 예외 발생 상황에 따른 주소변환 과정 표 6-1 각 필드 내용과 값의 의미

29  세그먼트 기법에서의 주소 변환 과정. Section 3 세그먼테이션 기법 그림 6-16(b) 세그먼트 기법에서의

30 3. 세그먼트 시스템에서의 공유  두 프로세스가 텍스트 편집기를 공유방법.
Section 3 세그먼테이션 기법 3. 세그먼트 시스템에서의 공유  두 프로세스가 텍스트 편집기를 공유방법. ● 두 프로세스 P1, P2는 자신의 세그먼트 테이블에 주기억 장치 내에 있는 동일한 세그먼트주소를 가짐으로써 그 세그먼트를 공유 그림 6-17 순수세그먼트 시스템에서의 공유