 7장 메모리 관리

운영체제 강의노트

 교재 : 운영체제(개정판)

 출판사 : 한빛미디어(2010년 11월 발행)

 저자 : 구현회

 7장 메모리 관리

1. 메모리 관리 개념

• 메모리 관리를 위한 3대 정책

• 반입 정책(fetch policy)

• 프로세스를 언제 메모리로 적재할 것인지를 결정하는 행위

• 요구 반입(demanded fetch)

• 사용자 또는 프로세스의 요구가 있을 때 주기억장치 로 적재하는 정책으로 정확하지만 시간 지연 발생

• 예상 반입(anticipatory fetch)

• 사용자 또는 프로세스의 요구가 있기 전에 필요할 것으로 보고 미리 주기억장치에 적재하는 정책으로 시간을 감소시키지만 부정확함

• 배치 정책(placement policy)

• 주기억장치의 어느 공간으로 적재할 것인지를 결정하는 행위

• 재배치 정책(replacement policy)

• 주기억장치에 빈 공간이 없을 때 어느 프로세스를 보조기억 메모리 관리 기법

1. 메모리 관리 개념

• 물리적 주소

• 실제 데이터나 프로그램이 저장되는 공간

• 메모리 칩이나 디스크 공간에 바이트 단위로 만들어짐

• 논리적 주소

• 프로그래머가 프로그래밍에 사용하는 공간

• 목적 코드가 저장된 공간과 프로그램에서 사용하는 자료 구조 등 메모리 해석에 대한 두가지 관점

메모리 관리 장치 (MMU)

프로세서 메모리

고정분할 동적분할(가변분할)

페이징(paging) 세그먼트(segmentation)

페이지화된 세그먼트(paged segmentation)

프로그램

(논리 또는 가상주소)

하드웨어

(물리 또는 실제주소) 주소변환

변환 기법

1. 메모리 관리 개념

• 연속 메모리 할당 방식

• 프로그램이 연속적인 하나의 메모리 블록에 저장될 수 있도록 메 모리를 할당

• 그러기 위해서는 메모리 자체를 여러 개의 고정된 크기로 분할하 여 프로세스에게 제공하게 되는데 이 방식은 메모리의 낭비를 초 래함

• 따라서, 각 프로세스의 크기에 맞는 블록으로 메모리를 분할해야 한다는 필요성이 제기됨

• 이 방식은 프로그램이 반드시 연속적인 하나의 메모리 블록에 저 장될 필요가 없음을 제기하게 됨

• 불연속(분산) 메모리 할당 방식

• 디스크에 있는 프로그램이 프로세스화하여 메모리로 옮겨올 때 다양한 방식으로 분할되어 작은 크기로 적재되고, 불연속적인 메 모리에 적재되면서 링크됨

메모리 관리 방식

1. 메모리 관리 개념

• 프로그래머는 고급 언어를 이용하여 프로그래밍하면서 ‘변수’라는 개 념으로 주소를 사용 → 논리적 주소임

• 바인딩(binding)

• 논리적 주소를 물리적 주소로 변환하는 과정

• 즉, 프로그램상의 주소를 절대주소로 바꾸어 주기억장치의 고정 된 부분에 적재하는 것을 의미하고 통상 다음과 같이 구분

• 컴파일 시간 : 고급 언어로 만들어진 소스 코드를 목적 코드 로 만드는 과정

• 목적 코드는 프로그래머가 만든 소스 코드를 기계가 이 해하는 전기 신호로 바꾼 코드로 목적 코드에게 부여하는 주소를 물리적 주소라고 함

• 적재 시간 : 컴파일시 물리적 주소를 알려주지 않으면 상대 주소를 생성하여 시작 주소를 0으로 하여 나머지는 재적재

• 수행 시간 : 현대 운영체제가 주로 사용하는 기법으로 디스 크에 있던 프로세스가 실행됨과 동시에 바인딩

주소 바인딩

1. 메모리 관리 개념

• 중첩(overlay) 기법사용 예

• 패스 1 : 70KB, 패스 2 : 80KB

• 심볼 테이블 : 20KB

• 공통 루틴 : 30KB

• 오버레이 드라이버 : 10KB 중첩

심볼테이블 공통 루틴 오버레이 드라이버

20KB 30KB 10KB

200KB

패스 1 ^140KB

70KB 패스 2 80KB

1. 메모리 관리 개념

• 프로세스 교체

• 메모리에 적재된 프로세스 중 완전 종료된 프로세스나 상당 기간 실행되지 않을 프로세스를 다시 디스크로 보내고 당장 필요로 하는 프로세스를 메모리에 적재하는 것

• 메모리 밖으로 내보내는 것을 swap out, 메모리로 불러오는 것을 swap in이라고 하는데 CPU를 사용하는 시간은 swap in 또는 swap out하는데 소요되는 시간보다 길어야 함

프로세스 교체

P1

P2 운영체제

사용자 영역

주기억장치 보조기억장치

2. 연속 메모리 할당

• 메모리 공간을 운영체제 영역과 사용자 영역으로 양분

• 메모리 제어권이 사실상 사용자에게 있음

• 메모리 제어권을 잘못 행사하면 운영체제가 적재된 부분을 침범하 여 운영체제를 파괴하는 것이 가능

• 이런 일이 없도록 하기 위해 운영체제 영역과 사용자 영역을 구 분하는 경계 레지스터(bound register)를 둠

단일 사용자 연속 메모리 할당

메모리 관리 장치 기준 레지스터

+

1400

프로세서 ^{346 1746}

논리적주소 물리적주소 메모리

2. 연속 메모리 할당

• 메모리 공간을 고정된 크기의 여러 블록으로 구분

• 프로세스의 크기와 메모리의 빈 블록의 크기를 비교하여 빈 블록의 크기 가 크거나 같으면 적재

고정 분할 다중 프로그래밍

200KB 200KB 200KB 200KB 200KB P1(180KB)

P2(240KB)

P3(90KB)

20KB 남음

110KB 남음

×

× ×

※ P1이 할당되고 남은 20KB와 P3가 할당되고 남은 110KB를 internal fragmentation이라고 함 주기억장치

2. 연속 메모리 할당

• 단편화(fragmentation)란?

• 메모리 블록에 적재되는 프로세스의 크기가 메모리 블록보다 작아 서 남는 메모리 자투리

• 고정 분할 메모리 관리에서 발생하는 단편화는 내부 단편화라고 함 고정 분할 다중 프로그래밍에서의 단편화

200KB 200KB 200KB 200KB 200KB

P1 : 190KB P2 : 180KB P3 : 200KB P4 : 185KB P5 : 195KB P6 : 20KB P1(190KB)

P2(180KB)

P3(200KB) P4(185KB) P5(195KB)

fragmentation

10KB 20KB

15KB 5KB

2. 연속 메모리 할당

• 메모리 공간을 여러 블록으로 미리 나누어놓지 않고 적재할 프로세스가 생길 때마다 크기에 맞게 메모리를 분할해서 적재

• 현재 대기 큐에 P1 : 60KB, P2 : 100KB, P3 : 30KB, P4 : 70KB, P5 : 50KB이 적재를 기다리고 있다고 가정

가변 분할 다중 프로그래밍

운영체제 P1

P2

P3 216KB

운영체제

0 40KB

256KB

0 40KB

256KB

운영체제 P1

P3

0 40KB

256KB 100KB

200KB

230KB

200KB

230KB 100KB

운영체제 P1

P3

0 40KB

256KB 200KB

230KB 100KB

P4

170KB

운영체제

P3

0 40KB

256KB 200KB

230KB 100KB

P4

170KB

운영체제

P3

0 40KB

256KB 200KB

230KB 100KB

P4

170KB

P5

90KB

2. 연속 메모리 할당

• 메모리 공간이 분할될 때마다 각 블록의 시작 위치, 크기, 사용 여부 를 관리하는 테이블이 있어야 함

• 초기에는 큰 메모리 공간이 하나 있는 상태이고, 프로세스가 적재될 때마다 큰 메모리 블록이 분할됨

• 프로세스가 실행을 종료하고 디스크로 빠져나갈 때마다 빈 공간이 생 기게 됨

• 메모리 블록의 크기가 가변적이기 때문에 적재를 대기하고 있는 프로 세스들의 크기와 메모리 블록의 크기를 비교해서 적재 가능 여부를 판 단함

• 프로세스의 크기가 모든 빈 메모리 블록의 크기보다 크게 되면 적재 불가

• 빈 메모리 블록이 있음에도 불구하고 크기가 맞지 않아서 어떤 프로세스도 사용하지 못하게 되는 것을 외부 단편화(external fragmentation)이라고 함

• 외부 단편화는 내부 단편화와는 달리 인접한 단편화끼리 통합하 여 더 큰 메모리 블록을 만드는 것이 가능함

2. 연속 메모리 할당

• 새로 적재하는 프로세스를 빈 메모리 블록 중 어느 곳으로 할당할 것 인지를 결정하는 정책

• 최초 적합 기법(first-fit)

• 사용 가능한 빈 메모리 공간 중 가장 앞에 있는 빈 공간으로 적재

• 빈 공간을 빨리 찾을 수 있다는 장점이 있지만, 앞 쪽에 단편 화들이 많이 발생함

• 최적 적합 기법(best-fit)

• 사용 가능한 빈 메모리 공간 중 프로세스의 크기와 가장 유사 한 빈 공간으로 적재

• 단편화가 전 메모리 영역에서 고루 분포하지만 모든 빈 공간 을 검색해야 하기 때문에 시간 지연 발생

•최악 적합 기법(worst-fit)

• 사용 가능한 빈 메모리 공간 중 프로세스의 크기와 가장 차이 가 많이 나는 빈 공간으로 적재

메모리 배치기법

2. 연속 메모리 할당

• 내부 단편화는 인접해있다고 하더라도 기본적으로 통합이 불가능

• 왜냐하면 메모리 블록의 주소가 고정적으로 정해져 있기 때문에 변경 불가능

• 외부 단편화는 인접해있는 인접해있지 않든 통합 가능

• 통합 : 인접해있는 2개의 빈 공간을 하나로 만드는 과정

• 빈 공간에 대한 시작 주소와 크기를 조정

• 압축 : 인접해있지 않은 빈 공간을 하나로 만드는 과정

• compaction이라고도 함

• 적재되어 있는 프로세스들의 자리를 이동하여 빈 공간을 하 나로 모아야 함

• 압축은 프로세스들을 이동해야 하는 어려움이 있고, 비용도 많이 들어서 현실적으로 잘 사용하지는 않는 기법임

• 이에 비해 디스크 조각 모음은 비교적 안전한 작업이므 로 주기적으로 해주는 것이 시스템 성능 향상을 위해서 바 외부 단편화

2. 연속 메모리 할당

운영체제

3KB

7KB

10KB

통합 & 압축

운영체제

3KB

7KB

10KB

10KB

P1 종료

운영체제

7KB

10KB

13KB

통합

운영체제

7KB

P3(8KB)

10KB

13KB

압축

운영체제

P3(8KB)

10KB

20KB

통합

운영체제

P3(8KB)

10KB

20KB

압축

• 통합과 압축은 별도로 수행되기도 하지만 연계하여 수행되기도 함

• 통합과 압축 과정

• 압축 시 어느 방향으로 압축하는 것이 좋은가에 대한 결정도 시스템 성 능 변화에 영향을 줄 수 있음

2. 연속 메모리 할당

• 단편화 문제를 해결하기 위해 버디 시스템(buddy system)이 제안됨

• 버디 시스템은 큰 메모리 블록을 반복적으로 이등분하여 아주 작은 공간 으로 분할

• 프로세스들에게 메모리를 할당할 때 메모리 공간의 크기가 작으면 2개의 인접한 메모리 블록을 통합하여 크게 만들어서 할당하는 기법 버디 시스템

64

32

32

32

16 16

32

16 8

3. 분산 메모리 할당

• 페이지(page)

• 프로세스들을 2의 누승 단위로 잘게 분할한 것

• 페이지 프레임(page frame)

• 페이지 하나가 적재될 수 있는 동일한 크기의 메모리 공간

• 페이징 기법

• 프로세스 단위로 메모리에 적재됨으로 해서 발생하는 문제점 해 결

• 프로세스의 단위가 크기 때문에 단편화 발생

• 하나의 프로세스가 반드시 연속적인 메모리 공간에 적재되어 야 할 필요성 없음

• 페이징 기법이란 메모리에 적재되는 프로세스를 분할하여 크기를 작게 하여 단편화를 줄이고, 여기 저기 산재한 메모리 블록에 분산 저장함으로써 메모리 사용 효율을 높이는 메모리 관리 기법임

• 그러나, 페이지마다 페이지 번호를 부여해서 관리해야 하고, 분산 배치되어 있는 페이지를 링크시키는데 시간이 소요됨

페이징 기법

3. 분산 메모리 할당

• 페이지 사상 테이블(PMT : Page Map Table)

• 어떤 페이지가 메모리 내의 어떤 페이지 프레임으로 사상되었는가 를 관리하는 테이블

• 논리 페이지는 PMT에서 해당 페이지가 적재된 페이지 프레임 번호 를 알아서 물리 메모리로 이동하여 해당 페이지를 찾게 됨

페이징 시스템 하드웨어

페이지 0 페이지 1 페이지 2 페이지 3 논리 메모리

1 4 3 7

0

1

2

3

PMT

페이지 0

페이지 2 페이지 1

페이지 3

0 1 2 3 4 5 6

프레임번호

3. 분산 메모리 할당

• 페이지 크기

• 페이지와 프레임의 크기는 하드웨어에 의해 결정

• 레지스터, 메모리 등의 특성에 따라 페이지 크기가 결정되면 그 크 기를 소화할 수 있는 운영체제가 만들어짐

• 일반적으로 512워드 ~ 2048워드로 2의 누승으로 증가

• 워드의 크기는 32비트 또는 64비트 페이지 번지

페이지 번호 페이지 내 변위

논리주소(32비트)

24비트

12비트 12비트

미사용

페이지 주소로 32비트를 사용하는 예

• 예를 들어, 페이지 크기가 프로그 램 100행인 경우, 325행은 4개의 페 이지가 필요함

• 325행의 페이지 번호는 4페이지의 25번째 행이 됨

3. 분산 메모리 할당

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

• PMT가 주기억장치 또는 캐시 메모리에 구현

• 가상주소 V=(p,d)에서 p는 페이지 번호이고, d는 변위인데 p를 읽고 해당 페이지로 가고 d만큼 떨어진 위치로 주소를 변환

페이지 테이블의 구현

b

p d

페이지테이블 b의 기준주소 페이지테이블

기준 레지스터

+

페이지 번호 변위

가상주소 V=(p,d)

P’ d

P’

p

p b

b+p 실제 메모

리주소 r

3. 분산 메모리 할당

• 연관 사상에 의한 페이지 주소 변환

• 프로세서에 의해 생성된 논리 주소는 프로세서의 페이지 번호와 프 로세서에 대응하는 프레임 번호를 가지고 있는 연관 레지스터의 집합 으로 표현

• 연관 레지스터에 어떤 항목이 표현되면 모든 키와 비교하고, 항목이 발견되면 대응하는 값 부분 출력

P’ d

P P’ 실제 메모

리주소 r

P d

페이지 번호 변위

프레임 번호 변위

연관사상표

3. 분산 메모리 할당

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

• 최근 페이지만 연관 메모리에 유지하고 연간 메모리에 그 페이지가 없을 때는 직접 사상

P’ d

P P’

실제 메모 리주소 r

P d

페이지 번호 변위

프레임 번호 변위

부분 연관사상표 (자주 이용되는 페이지만 저장 이것을

먼저 수행

P’

연관사상표에서 일치하는 항목 이 없을 때

페이지 테이블 b의 기준주소

페이지 사상표 시작 점 레지스터

+

b

p

p b

직접 사상표 (모든 페이지 수록)

3. 분산 메모리 할당

• 여러 사용자에게 공유될 수 있는 페이지는 기억 공간의 절감을 유도

• 40명의 사용자가 200KB의 문서편집기를 공유하고, 각각 50KB의 데이터 공간을 사용하고 있는 경우

• 200KB를 공유하지 않으면 (200+50)×40=10,000KB=9.8MB

• 200KB를 공유하면 50×40+200=2,200KB=2.1MB 공유 페이지

ed 1 ed 2 ed 3 data 1

ed 1 ed 2 ed 3 data 3

ed 1 ed 2 ed 3 data 2 3

4 6 1

3 4 6 2

3 4 6

프로세스 P1 7

프로세스 P3

프로세스 P2 P1을 위한 페

이지테이블

P3을 위한 페 이지테이블

P1를 위한 페 이지테이블

data 1 data 3 ed 1 ed 2

ed 3 data 2

4. 세그먼트 메모리 관리 기법

• 페이징 시스템의 단점

• 프로세스를 고정되고 균일한 크기로 분할한 것이 페이지이므로 고 정된 크기로 분할하면 효율이 떨어지는 경우에는 단점을 보임

• 세그먼트

• 프로세스를 고정되고 균일한 크기로 분할하지 않고 논리적 특성을 고려하여 연관성이 높은 부분은 다른 페이지로 분리되지 않게 분할 한 조각. 즉, 동일한 함수는 동일한 블록으로 포함될 수 있도록 프로 세스를 분할

세그먼트 메모리 할당

서브루틴 스택

함수 sqrt

메인함수

심볼테이블

4. 세그먼트 메모리 관리 기법

페이징 시스템 세그먼트 시스템

논리 메모리

메모리관리장치(MMU)

• 세그먼트의 크기가 다름

• 프로세스의 논리적 특성을 중시하여 연관성 있는 부분을 같은 블록 으로 만들었기 때문

• 따라서 세그먼트 프레임 역시 크기가 다르며, 가변 분할 기법으로 메모리 할당

메모리관리장치(MMU)

논리메모리

4. 세그먼트 메모리 관리 기법

세그먼테이션의 예

서브루틴

스택

함수 sqrt 메인함수

심볼테이블

논리 주소 공간

세그먼트 0

세그먼트 1

세그먼트 2 세그먼트 3

세그먼트 4

프로세서

세그먼트 0

세그먼트 3 세그먼트 2 세그먼트 4

세그먼트 1

1400 2400

3200

4300 4700

5700 6300 6700

3 250

논리 주소 한계 기준

1000 1400 400 6300 400 4300 1100 3200 1000 4700

세그먼트 테이블

# 0 1 2 3 4

<

+

4. 세그먼트 메모리 관리 기법

세그먼트 공유

편집기

데이터 1

편집기

데이터 2

세그먼트 0

세그먼트 0

세그먼트 1 세그먼트 1

한계 기준 25286 43062

4425 68348

# 0 1

한계 기준 25286 43062

8500 90063

# 0 1

사용자 1의 세그먼트 테이블

사용자 2의 세그먼트 테이블

편집기

데이터 1

데이터 2

43062

68348

72773

90003

98553

물리적 메모리