제 4 장 가상 메모리 관리

제 4 장 가상 메모리 관리

4.1 개요

• 가상 메모리는 하나의 프로세스 전체가 한 번에 주기억 장치 내에 존재하지 않고 일부만 있어도 수행하게 하는 방법을 제공함 .

• 가상 메모리를 사용하면 사용자는 실제 주소 공간의 크기에 구애 받지 않고 보다 큰 가상 주소 공간상에서 프로그래밍을 할 수 있을 뿐만 아니라 , 주기 억장치보다 크기가 큰 프로세스를 수행시킬 수 있다 .

4.1.1 동적 주소 변환 (dynamic address translation)

• 주소 사상 기법

• 동적 주소 변환 (DAT : Dynamic Address Translation) 기법 : 프로세스가 수행될 때 가상 주소를 실제 주소로 변환하는 대표적인 메커니즘

4.1.2 블럭 사상 (block mapping)

• 블럭 사상 시스템에서의 가상 주소

Slide 2 (of 24)

• 블럭 사상 (mapping) 을 통한 가상 주소변환

4.2 페이징

• 페이징 시스템에서의 가상 주소는 순서쌍 v=(p, d) 로 표현

 p 는 가상 메모리 내에서 참조될 항목이 속해 있는 페이지 번호

 d 는 페이지 p 내에서 참조될 항목이 위치하고 있는 곳의 변위

• 순수 페이징 시스템에서의 가상 주소

가상 주소 v=(p, d⁾

페이지 번호 p 변위 d

• 페이징 기법 하에서의 동적 주소 변환

 실행 중의 프로세스가 참조하는 가상 주소를 v=(p, d) 라고 할 때 , 페이지 사상 테이블 (page mapping table) 에서 페이지 p 를 찾고 ,

 페이지 p 가 페이지 프레임 p' 에 있음을 알아낸다 .

 그 후 p' 와 d 를 더하여 주기억장치 상의 실제 주소 r=p'+d 를 구한다 .

Slide 4 (of 24)

• 페이징 예

4.2.1 직접 사상 (direct mapping)

• 직접 사상에 의한 페이지 주소 변환

 직접 사상 방법에서 아주 큰 페이지 사상 테이블은 보통 주기억장치에서 유지․관리된다 . 또한 변환되는 가상 주소와 페이지 사상 테이블의 시작 주소는 제어장치 내의 고속 레지스 터에 보관함으로써 페이지 사상 테이블의 참조는 한 주기억장치 주기 시간 (cycle time) 내에서 수행된다

Slide 6 (of 24)

4.2.2 연관 사상 (associative mapping)

• 연관 기억장치 (associative memory) 에 페이지 사상 테이블 전체를 넣는 방법

• 내용 주소화 기억장치 (Content-addressable memory): CAM 에서는 사용자가 검색 어를 제공하면 , CAM 은 자신의 메모리 공간 전체를 탐색하여 해당 검색어가 위치하고 있는 주소를 반환한다 .

• 순수 연관 사상을 통한 페이지 주소 변환

4.2.3 연관 / 직접 사상

• 적당한 비용으로 캐시나 연관기억장치 기법에 의한 장점을 살릴 수 있는 절충 방안

• 가장 최근에 참조된 페이지는 조만간 다시 사용되기 쉽다는 사실을 이용하여 , 연관기 억장치에는 페이지 사상 테이블의 전체 항목 중 최근에 참조된 일부 페이지 항목들만 을 수용 .

• 연관 / 직접 사상을 통한 페이지 주소 변환

Slide 8 (of 24)

•

4.2.4 페이징 시스템의 공유

• 순수 페이징 시스템에서의 공유

A프로세스의 페이지 사상 테이블

실기억장치

페이지 5

페이지 6

페이지 7

페이지 8

페이지 9

페이지 10

페이지 11 프로세스

A만 사용 프로세스 A, B가

공유

프로세스 A, B, N이 공유

프로세스 B, N이 공유

B프로세스의 페이지 사상 테이블

프로세스 N의 페이지 사상 테이블

Slide 10 (of 24)

4.2.5 페이지 크기

• 페이지의 크기를 결정함에 있어 고려되어야 할 내용

 테이블 단편화 (table fragmentation)

 페이지 크기가 작을수록 프로세스가 작업세트 (working set) 를 확보하는 데 도움이 된다 . 프로세스들은 구역성을 가지며 이 구역 내에서는 비교적 소량의 정보만을 필요로 하기 때문 이다 .

 마지막 페이지가 거의 찬 상태일 수도 있고 또는 거의 빈 상태일 수도 있기 때문에 평균적으 로 1/2 페이지의 단편화가 생기게 된다 . 따라서 페이지 크기가 작을수록 내부의 단편화는 감소된다 .

 페이지가 크게 되면 참조되지 않을 많은 정보들까지 주기억장치로 옮겨지게 되어 기억공간 의 낭비를 초래하게 된다 .

 디스크로부터의 입출력 전송은 많은 시간이 소비되기 때문에 , 프로그램 실행 중 입출력 전 송의 횟수를 줄이기 위해서는 페이지 크기가 클수록 효과적이다 .

4.2.6 페이지 인출 기법

• 요구 페이징 (demand paging) 기법

 실행 중인 프로세스에 의하여 명백히 참조되는 프로세스만이 보조기억장치로부터 주기억 장치로 옮겨진다 .

• 예상 페이징 (anticipatory paging) 기법

 프로세스가 필요로 할 페이지들을 운영체제가 예측하여 주기억장치에 여유가 있 을 때 이 페이지들을 미리 적재시킨다 .

4.2.7 페이지 양도 (page release)

• 더 이상 필요로 하지 않는 특정한 페이지가 존재한다면 , 작업세트로부터 그것을 제외 시켜 페이지 프레임을 유용하게 만든다 .

• 컴파일러나 운영체제가 자동으로 페이지 제거를 실행하여 작업세트를 확보

Slide 12 (of 24)

4.3 세그먼테이션 (segmentation)

• 세그먼트 : 논리적 단위가 되는 프로그램 모듈이나 자료 구조 4.3.1 직접 사상

• 세그먼테이션 시스템에서의 가상 주소

가상 주소 v=(s, d)

세그먼트 번호 s 변위 d

• 순수 세그먼테이션 시스템에서의 가상 주소 변환

4.3.2 공유 및 보호

• 공유

 세그먼테이션 시스템에서의 세그먼트 공유

처리기문서

세그먼트 0 데이터 1 세그먼트 1

처리기문서

세그먼트 0 데이터 2 세그먼트 1 논리적 기억장치

(사용자 1)

문서 처리기

데이터 1

데이터 2

실기억장치 세그먼트시작주소

32151 57737

세그먼트시작주소

32151 81112 세그먼트 테이블

(사용자 1)

세그먼트 테이블 (사용자 2) 0

1

0 1

32151

57737 61662

81112 87442

Slide 14 (of 24)

• 보호를 위한 접근 (access) 제어

 세그먼트 사상 테이블의 항목

r=0 : 세그먼트가 주기억장치 내에 없는 경우 R: 판독 접근 r=1 : 세그먼트가 주기억장치 내에 있는 경우 W: 기록 접근 보호 비트 : (1 예 , 0 아니오 )E: 수행 접근

A: 첨가 접근

 접근 제어 유형

접근형태 약 자 설 명

판독 R 이 블럭은 읽힐 수 있다 . 기록 W 이 블럭은 수정될 수 있다 . 수행 E 이 블럭은 수행될 수 있다 .

첨가 A 이 블럭의 끝에 정보를 첨가할 수 있다 .

4.4 페이징 / 세그먼테이션 혼용 기법

• 페이징 / 세그먼테이션 시스템에서의 가상 주소 양식

가상 주소 v=(s, p, d)

세그먼트 번호 s 페이지 번호 p 변위 d

• 페이징 / 세그먼테이션 혼용 시스템에서의 연관 / 직접 사상을 통한 가상 주소

변환

Slide 16 (of 24)

페이지 부재 처리 과정

4.5 페이지 교체 알고리즘

• 페이지 교체 기법은 새로이 적재될 페이지를 위한 주기억장치 공간을 확보하 기 위하여 , 현재 주기억장치를 차지하고 있는 페이지들 중에서 어떤 페이지 를 선택하여 가상 공간으로 보낼 것인가를 결정하는 기법

4.5.1 FIFO(First In First Out) 알고리즘

• 페이지가 교체될 필요가 있을 때 가장 먼저 주기억장치에 들어와 있는 페이지와 교체 시키는 방법

• FIFO 알고리즘

8 1 2 3 1 4 1 5 3 4 1 4 3 2 3 1 2 8 1 2

8 8 1

8 1 2

3 1 2

3 4 2

3 4 1

5 4 1

5 3 1

5 3 4

1 3 4

1 2 4

1 2 3

8 2 3

8 1 3

8 1 2 페이지 호출 순서

페이지 프레임

Slide 18 (of 24)

4.5.2 최적 교체 (Optimal Replacement) 알고리즘

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체시킨다 .

• 최소의 페이지 부재율을 가지는 알고리즘이다 .

• 최적 교체 알고리즘

8 1 2 3 1 4 1 5 3 4 1 4 3 2 3 1 2 8 1 2

8 8 1

8 1 2

3 1 2

3 1 4

3 5 4

3 1 2

8 1 2 3

1 4 페이지 호출 순서

페이지 프레임

 9 번의 페이지 부재

4.5.3 LRU(Least Recently Used) 알고리즘

• 현시점에서 가장 오래전에 사용된 페이지를 제거하는 방법

• LRU 알고리즘

8 1 2 3 1 4 1 5 3 4 1 4 3 2 3 1 2 8 1 2

페이지 프레임 페이지 호출 순서

8 8 1

8 1 2

3 1 2

3 1 4

5 1 4

5 1 3

5 4 3

1 4 3

2 4 3

2 1 8 2

1 3

 12 번의 페이지 부재

Slide 20 (of 24)

4.5.4 2 차 기회 (second chance) 알고리즘

• 페이지 테이블의 각 항목에 한 개의 참조 비트를 연관시킨 후 , 처음에 운영체제에 의해 모든 참 조 비트는 0 로 된다 . 그 후 한 프로세스가 수행되면서 참조한 각 페이지와 관계된 비트는 값이 1 로 바뀐다

• 페이지 교체를 위하여 페이지의 참조 비트를 조사하여 그 값이 0 이면 그 페이지를 교체하고 , 참 조 비트가 1 이면 그 페이지에게 2 차 기회를 주고 다음 페이지를 조사하기 위하여 FIFO 방식으 로 진행한다 .

• 2 차 기회 알고리즘

0

0 1

1 0

0

1

1

0

참조비트 페이지

교체

페이지의 환형큐 nth (n+1)th

2차 기회

교체 기회2차

4.5.5 LFU(Least Frequently Used) 알고리즘

• 각 페이지의 사용이 얼마나 집중적으로 되었는가에 관심을 갖고 , 가장 적게 사용되거 나 집중적이 아닌 페이지가 대체된다 .

4.5.6 NUR(Not Used Recently) 알고리즘

• 최근에 사용되지 않은 페이지는 가까운 미래에 사용되지 않는 경향에 따라 그것들을 참조되는 페이지와 교체시킨다 .

• 각 페이지에 대해 두 개의 하드웨어 비트를 첨가하게 된다 .

① 참조된 비트 =0 : 그 페이지가 참조되지 않았을 경우 참조된 비트 =1 : 그 페이지가 참조되었을 경우

② 변형된 비트 =0 : 그 페이지가 변형되지 않았을 경우 변형된 비트 =1 : 그 페이지가 변형되었을 경우

• 페이지 교체 시 참조 비트가 0 인 페이지를 찾는다 . 만일 모든 페이지의 참조 비트가 1 일 때는 변형 비트가 0 인 것을 찾는다 .

Slide 22 (of 24)

4.6 쓰래싱 (thrashing)

• 쓰래싱 : 어떤 프로세스가 어느 정도의 프레임을 갖고 있지 않다면 , 페이지 부재가 발생하게 되어 프레임 안에 있는 사용 중인 어떤 페이지를 교체하여야 하는데 , 이러한 페이지 부재가 계속적으로 발생되어 프로세스가 수행되는 시간보다 페이지 교체에 소비되는 시간이 더 많아지는 경우

중앙처리장치의 효율성

다중 프로그래밍의 정도

쓰래싱

4.6.1 구역성 (locality)

• 쓰래싱을 방지하기 위하여 한 프로세스가 효율적인 수행을 위하여 제공받아야 할 프레 임의 수를 알아야 한다 .

• 구역성이란 ‘프로세스가 기억장치 내의 모든 정보를 균일하게 참조하는 것이 아니라 국부적인 부분만을 집중적으로 참조한다’는 것을 의미한다 .

• 시간 구역성 (temporal locality)

 최근에 참조된 기억장소가 가까운 장래에도 계속 참조될 가능성이 높음을 의미한다 .

 예 : 순환 (looping), 서브루틴 , 스택 , 카운팅 (counting) 과 집계 (totaling) 에 사용되는 변수

• 공간 구역성 (spatial locality)

 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향이 있음을 의미한 다 .

 예 : 배열 수행 , 순차 코드의 실행 (sequential code execution), 프로그래머들이 관련된 변수

Slide 24 (of 24)

4.6.2 작업세트 (working set)

• 작업세트 : 프로세스에 의해 자주 참조되는 페이지들의 집합

4.6.3 페이지 부재율

프레임 회수 상한계

하한계 프레임 할당

페이지부재율

프레임의 수