운영체제(OS) - 6. 메모리 관리

1. 주소바인딩

 

프로세스의 논리적 주소를 물리적 메모리 주소로 연결시켜주는 작업

 

---

 # 주소 바인딩의 종류

1. 컴파일 타임 바인딩(Compile time binding)

• 컴파일 시점에 해당 프로그램의 물리적 메모리위치를 결정 및 고정
• 절대 주소로 프로그램이 적재된다는 뜻에서 절대코드(absolute cod)를 생성하는 바인딩 방식이라 칭함
• 물리적 메모리 위치 변경 요구시, 컴파일을 다시 해야하므로 현대 시분할 컴퓨팅에서 잘 사용하지 않는다

2. 로드 타임 바인딩(load time binding)

• 프로그램의 실행 시작시 물리적 메모리위치가 결정
• 로더(loader)가 물리적 메모리 주소를 부여
• 프로그램 종료까지 물리적 메모리 위치가 고정
• 컴파일러가 relocatable code를 생성한 경우에 가능한 방식

 # 로더(loader)

   사용자 프로그램을 메모리에 적재시키는 프로그램

 

3. 실행시간 바인딩(executiton time binding = run time binding)

• 프로그램 실행 후에도 프로그램의 물리적 메모리상의 주소가 변경될 수 있는 바인딩 방식
• CPU가 주소 참조를 할때마다, 주소 매핑 테이블을 이용해 바인딩을 점검함
• Base Register 와 Limit Register, 그리고 MMU(Memory Management Unit)의 하드웨어적인 지원이 필요
• 프로세스가 CPU를 얻을때마다 Base Register 값과 Limit Register 값을 재설정

---

  # MMU(Memory Management Unit)

    논리적 주소를 물리적 주소로 매핑해주는 하드웨어 장치

 

  # MMU 기법 (MMU Scheme)

   - 프로그램의 주소공간이 물리적 메모리에 연속적으로 적재되는 것으로 가정

   - 프로세스가 CPU를 얻을때마다 Base Register 값과 Limit Register 값을 재설정 

   - 물리적 주소값  = 논리적 주소값 + Base register(=reloaction register) 값

   - 논리적 주소값이 OffSet 역할

   - Limit register은 메모리보안(memory protection) 역할을 수행

    (논리적 주소값이 한계레지스터 값보다 작은지 체크, 그렇지 않다면 트랩발생 후 프로세스 강제종료) 

MMU Scheme 물리적 주소값 매핑기법 및 데이터 접근 방법

---

 

2. 메모리 관리와 관련된 용어설명

 

1. 동적로딩(dynamic loading)

여러 프로그램이 동시에 메모리에 올라가서 수행되는 multi-programming 환경에서

메모리 사용효율을 높이기 위해 사용되는 기법 중 하나

 

프로세스 시작시 해당 프로세스의 주소공간 전체를 메모리에 다 올려놓는 것이 아닌,

실행에 필요한 부분이 call 될 때마다 그 부분만을 메모리에 적재하는 방식

 

프로그램의 오류 처리루틴과 같은 특별한경우에 가끔씩 사용되는 방어용 코드들로 인한

메모리낭비를 막을수 있음

 

프로그램 자체에서 구현 가능, 운영체제가 라이브러리를 통해 지원할 수도 있음

 

 

 

---

2. 동적연결(dynamic linking)

 

# 목적 파일(Object File)

작성된 소스코드가 컴파일되면서 

기계어나 RTL과 같은 이진 코드로 변형된 파일

 

# 연결(Linking)

Object File 과 Library File 을 잇는 행위

이 행위를 통하여 실행파일을 생성하는 경우를 정적연결이라 칭함

---

# 정적연결(Static Linking)

 

실행파일(executable file)

=

목적파일(object file) + 라이브러리 파일(library file)

 

같은 라이브러리 코드가

각 프로세스에 독립적으로 존재하여 메모리낭비를 유발

 

---

 

# 동적연결(Dynamic Linking)

 

실행파일(executable file)

=

목적파일(object file)

 

라이브러리 함수를 호출할 때, 라이브러리와 실행파일을 연결

 

실행파일의 라이브러리 호출 부분에

해당 Library의 위치 검색을 위한

Stub이라는 작은 코드를 생성

 

Library 호출시, 

Stub 을 통하여 해당 Library가 메모리에 존재하는 지 체크

그렇지 않다면,

디스크에서 동적 라이브러리 파일을 찾아 메모리에 적재

 

다수의 프로그램이 공통으로 사용하는 Library를 한번만 적재 후

다수의 프로그램이 Stub을 통해

같은 Library를 메모리낭비 없이 함께 사용가능

 

운영체제의 지원을 필요로함

 

---

3. 중첩(overlays)

 

프로세스의 주소공간을 분할해 실제 필요한 부분을 메모리에 적재하는 기법

 

동적로딩은 다중프로그래밍 환경에서 메모리 이용률을 향상 

 

중첩은 프로세스 1개 조차도 메모리에 한꺼번에 올릴 수 없을때,

주소 공간을 분할하여 당장 필요한 부분을 메모리에 올려 실행

 

운영체제의 지원 없이 프로그래머에 의해 구현되어야 했으며,

작은 공간의 메모리를 사용 하던 시절에 손수 구현 했다 하여 Manual Overlays 라고도 부른다.

 

 

---

4. 스와핑(swapping)

 

메모리에 올라온 프로세스의 주소공간 전체를

디스크의 스왑영역에 일시적으로 내려놓는 것을 칭함

 

프로세스당 메모리양이 지나치게 적어져

시스템성능이 저하되는것을 방지함

 

스왑 영역(swap area)은 백킹스토어(backing store)이라고도 부르며,

디스크 내의 파일시스템과는 별도로 존재하는 일정영역을 칭한다

 

# Swap-In

디스크 -> 메모리

 

# Swap-out

메모리 -> 디스크

---

# Swapper (=Medium-term scheduler)

 

스왑 아웃시킬 프로세스를 선정

(= 메모리에 존재하는 프로세스의 수를 조절)

(=Adjusting degree of multi-programming)

 

스왑 아웃 대상 프로세스는 주소공간 내용을

통째로 디스크에 스왑아웃

---

 

 

---

3. 물리적 메모리 할당 방식

 

 

 

1. 메모리 분할 방식

 

# 고정분할(fixed partition allocation)

메모리를 임의의 고정된 크기로

미리 분할하여 나누어둔 방식

 

 # 가변분할(variable partition allocation)

프로그램 실행과 종료에따라

동적으로 분할을 관리하는 방식

 

 

---

2. 사용자 프로세스 영역 메모리 관리방법

# 연속할당 (contiguous allocation)

 각각의 프로세스를 물리적 메모리의 연속적인 공간에 적재하는 방식

 하나의 분할에 하나의 프로세스가 위치

---

# 불연속할당 (noncontiguous allocation)

 하나의 프로세스를 물리적 메모리의

여러 영역에 분산하여 적재하는 방식

 

 #_1 페이징(paging) 기법

 각 프로세스의 주소 공간을 동일한 크기의

페이지(page)단위로 메모리에 적재 

 

#_2 세그먼테이션(segmentation) 기법

 프로그램의 주소 공간을 코드, 데이터, 스택등 의미있는 단위인

세그먼트 단위로 적재

 

 #_3 페이지드 세그먼테이션(paged segmentation) 기법

 세그먼트 하나를 다수의 페이지로 구성하여 적재

 

---

3. 연속할당방식 

 

# 고정분할 연속할당

 

메모리를 주어진 갯수만큼 나누며,

각 메모리 분할의 크기는 자유롭지만 분할 후 고정된다.

 

즉, 동시에 나누어진 갯수만큼만

프로그램을 적재할 수 있다.

 

고정분할 방식에서는

외부조각(external fragmentation)와

내부조각(internal fragmentation)이

발생할 수 있다.

---

# External Fragmentation

 

해당 분할이 비어있음에도 불구하고,

프로그램의 크기가 해당 분할보다 커서

적재되지 못하여 발생하는 메모리 공간을 일컫음

 

프로그램이 적재되지 않았기에 추후에 활용 가능한 공간

 

 

# Internal Fragmentation

 

해당 분할에 프로그램을 적재하고 남는 메모리공간

프로그램의 크기가 분할의 크기보다 작은경우 발생하는 메모리공간

 

프로그램이 적재 되었기에 추후에 활용 불가능한 공간

---

# 가변분할 연속할당

 

메모리에 적재되는 프로그램의 크기에 따라

분할의 크기 및 갯수가 동적으로 변하는 방식

 

크기에 따라 계산하여 분할하기 때문에

내부조각은 발생하지 않는다.

 

프로그램의 종료시 빈공간이 생기고

새롭게 할당되는 프로그램이 그 공간보다 크다면

외부조각은 발생할 수 있다.

---

# 동적메모리 할당 문제(Dynamic Storage-Allocation Problem)

 

주소 공간의 크기가 n인 프로세스를 메모리에 적재할 때,

물리적 메모리 가용공간 중

어떤 위치에 적재할 것인지 결정하는 문제

 

운영체제는 이미 사용중인 메모리와 가용공간에 대한 정보를

각각 유지하고 있다.

---

#_1 최초적합(first-fit) 방식

 

프로그램을 적재할 수 있는 가용공간이 최초로 발견되면,

그 공간에 적재시키는 방식

---

#_2 최적적합(best-fit) 방식

 

프로그램을 적재할 수 있는 가용공간 중,

가장 작은 가용공간에 적재시키는 방식

 

다수의 매우작은 가용공간이 생성될 수 있다는 문제점

 

하지만, 공간적인 측면에서는 외부조각의 크기가 작아지므로 효율적

 

가용공간 리스트의 정렬과 검색으로 인한 시간적 오버헤드 발생

---

#_3 최악적합(worst-fit) 방식

 

프로그램을 적재할 수 있는 가용공간 중,

가장 큰 가용공간에 적재시키는 방식

 

더 큰 프로그램을 담을 수 있는 가용공간을

빨리 소진한다는 문제점

 

가용공간 리스트의 정렬과 검색으로 인한 시간적 오버헤드 발생

---

실제 시스템 실험결과, First-Fit 과 Best-Fit이

속도와 공간 이용률 측면에서 효과적인 것으로 나타남

---

# Compaction

 

외부조각 문제를 해결하기 위한 방법

 

프로세스에 의해 사용중인 메모리와 가용공간을 각각 다른방향으로 모아서

하나의 큰 가용공간을 만드는 방법

 

수행중인 프로세스의 메모리 위치를 옮겨야하므로,

비용이 매우 많이드는 작업이며,

Runtime Binding 방식이 지원되는 환경에서만 수행될 수 있다.

---

4. 페이징(paging)

 

불연속 할당 기법의 방식 중 하나

 

프로세스의 주소공간을 동일한 크기의 Page 단위로

물리적 메모리의 서로 다른위치에 적재하는 방식

 

각 프로세스의 주소공간 중,

일부는 Backing Store(=Swap Area)에 

일부는 물리적 메모리에 혼재시키는 것이 가능

 

물리적 메모리를 페이지(page)와 동일한 크기의 프레임(frame) 으로 

미리 나누어 둔다.

 

즉, 프레임(frame) 단위로 나누어 두었기에,

동적메모리 할당문제와 외부 조각의 문제가 발생치 않으나,

프로그램이 항상 page크기의 배수가 아니므로,

내부조각은 발생할 수 있다.

 

논리적 주소를 물리적 주소로 변환하는 작업이

Base register + 논리적주소로 변환하던

기존과 다르게 새롭게 정의되어야 한다. 

---

# 페이징의 주소변환(address translation) 기법

 

하나의 프로세스를 page 단위로 나누고

각 page에 페이지 번호(p, index)를 붙인다.

 

프로세스의

page table 자료구조에 각 페이지의 Index(p) 별로

실제 물리적 메모리 시작주소(base address)를 저장해놓는다. 

 

각 페이지별로 데이터에 offset(d)개념을 두어

각 데이터에도 d를 설정하고 저장해둔다.

 

원하는 데이터를 찾으려면

page table의 p번째 항목(=물리적메모리 시작주소)에 접근한 후,

그 값에 offset값인 d를 더하여 접근한다.

 

프로세스의 각 데이터는(p,d) 순서쌍을 담고 있다.

---

# 페이지 테이블(Page Table)

 

페이징 기법에서 주소변환을 하기위한 자료구조이며,

물리적 메모리에 저장한다.

(페이지 테이블의 갯수는 전체 페이지의 갯수와 동일)

 

페이징 기법에서 메모리 접근연산은

주소 변환을 위해 페이지테이블에 접근 - ①

변환된 주소에서 offset 을 더하여 실제데이터에 접근 - ②

총 두번 접근하는 오버헤드가 발생한다.

 

접근 오버헤드를 줄이고, 메모리 접근 속도를 향상시키기 위해

TLB(Tanslation Look-Aside Buffer)라고 불리는

고속 주소변환용 하드웨어 캐시가 사용되기도 한다.

---

# PTE(Page Table Entry) 

 Page Tabe의 레코드

 Page Base Address 와 플래그 비트가 저장됨

 

#플래그 비트

접근 비트(Accessed bit) : 페이지에 대한 접근 유무

변경 비트(Dirty bit) : 페이지 내용에 대한 변경 유무

존재 비트(Present bit) : 현재 페이지에 할당된 프레임 존재 유무

읽기/쓰기 비트(Read/Write bit) : 읽기/쓰기에 대한 권한 유무

---

# TLB(Translation Look-aside Buffer)

캐시 메모리의 가격특성상

빈번히 참조되는 페이지 정보만 저장한다.

(검색 오버헤드가 발생)

 

이러한 검색 오버헤드를 줄이기 위하여,

TLB는 병렬탐색이 가능한 연관 레지스터를 사용한다.

 

병렬탐색은 TLB 내의 모든 항목을 동시에 탐색할 수 있는 기능 

 

PageTable 과는 다르게

페이지번호와 대응하는 프레임 번호가 쌍으로 저장 되어있다.

 

# TLB 연관레지스터 사용시 평균 메모리 접근시간

 

평균 메모리 접근시간 (EAT : Effective Access Time) : EAT

메모리에 접근하는 시간을 1 ,

연관 레지스터 접근하는 시간을 B ,

요청된 페이징 정보가 TLB에 존재할 확률 P ,

 

EAT = (1+B)*P + (2+B)*(1-P)

= 2 + B - P

 

P와 곱해지는 (1+B)는 존재했을시 걸리는 시간

(즉, TLB에 접근[B] + 메모리의 실데이터 접근[1])

 

(1-P)와 곱해지는 (2+B)는 존재치 않았을시 걸리는 시간

(즉, TLB 접근[B] + 메모리의 PageTable 접근[1] + 메모리의 실데이터 접근[1])

 

---

Paging with TLB

# 계층적 페이징(Hierarchical Paging)

 

현대 컴퓨터는 주소공간이 매우 큰 프로그램을 지원

 

예를 들어, 32비트 주소 체계를 사용하는 컴퓨터는

2의 32제곱 byte(=4GB)의 주소공간을 지원할 수 있다.

 

이러한 환경에서 page 크기가 4KB라면

1M(=4GB/4KB)개의 PTE(Page Table Entry)가 필요

 

즉, PTE 한 개당 4byte씩 필요로 한다면

PageTable의 크기는 1M*4byte = 4MB가 되며

전체 메모리중 4MB가 PageTable로 사용됨

(일반적으로 PageTable은 프로세스당 하나씩 가지고 있다.)

 

이러한 공간낭비를 줄이기 위해

2단계 페이징 기법(two-level paging)을 사용한다

---

# Two-level Paging

 

외부페이지 테이블(outer page table)과

내부페이지 테이블(inner page table)을 두어

사용되지 않는 주소공간에 대해서는 테이블의 항목을 NULL로 설정하여

대응하는 내부페이지테이블을 생성하지 않는 것

(메모리 중 해당 프로세스가 올라간 영역만 내부페이지테이블을 생성한다는 뜻)

 

내부 페이지 테이블 자체를 하나의 프레임(4KB로 예시)에 보관한다.

 

즉, 논리주소의 32비트 중,

(CPU가 생산하는 주소 = 논리주소)

4K개의 오프셋(1 byte)을 구분하기 위해 12비트가 필요

1K개의 PTE(4 byte, 내부페이지)를 구분하기 위해 10비트가 필요

 32비트 중 남은 10비트에 외부페이지 테이블의 인덱스를 할당

 

메모리공간 Down, 메모리접근 횟수 Up

=> TLB로 해결

---

# 역페이지 테이블

(Inverted Page Table)

 

 

모든 프로세스의 모든 페이지에 대해 PTE를 생성하는 틀을 깨는 발상

 

논리주소가 아닌 물리적 주소에 페이지 테이블을 만드는 것

(There's only one page table in system-wide)

 

PTE의 각 항목은 [PID, PageNo] 를 가짐

 

주소변환이 다소 비효율적

(주소변환 요청 -> 페이지 테이블 전체 탐색)

 

따라서 메모리가 아닌,

연관 레지스터에 역페이지 테이블을 보관하는게 일반적

 

---

# 공유 페이지

---

# 공유코드

(Shared Code, Re-Entrant Code, Pure Code)

 

여러프로세스에 의해 공통으로 사용될 수 있도록

작성된 read-only 코드

---

공유페이지란, 공유코드를 담고 있는 페이지

 

공유페이지는 그 페이지를 공유하는 모든 프로세스의 주소공간에서

동일한 페이지번호를 가져야함

 

Shared Page

# 사유 페이지(Prviate page)

프로세스들이 공유하지 않고 독자적으로 사용하는 페이지

(프로세스의 논리적주소공간 중 어떠한 위치에 있어도 무방)

 

---

                                                                                               

5. 메모리 보호

(Memory Protection)

 

PTE에는 보호비트(protection bit) 와 유무효 비트(valid-invalid bit) 를 둔다

---

# Protection bit 

 

각 페이지에 대한 접근 권한 

다른프로세스의 주소공간은 침해할 수 없으므로 Who가 아닌 How 에 대한 접근 권한을 설정

각 페이지에 대한 Read, Write, ReadOnly 같은 권한 설정

---

# Valid-Invalid bit

 

해당 페이지의 변환된 주소정보가 Valid 

1. 물리적 메모리에 해당 페이지가 존재

 

해당 페이지의 변환된 주소정보가 Invalid

1. 물리적 메모리에 해당 페이지 존재하지않음

(스왑영역(Backing Store)에 있음)

 

2. 프로세스가 해당 주소부분을 사용하지 않음

---

6. 세그먼테이션

(Segmentation)

 

메모리를 물리적 크기(Physical Unit)인 Page 와 달리,

의미적단위(Logical Unit)인 Segment로 나누는 기법

 

일반적으로 프로세스를 구성하는 주소공간에서

Code, Data, STack 등 기능단위로 Segment를 정의

 

함수 하나하나를 세그먼트로 정의할 수도 있음.  

---

# 프로그램의 논리적 주소

 

<세그먼트 번호(s), 오프셋(d)> 으로 사용

---

# 주소변환

 

세그먼트 테이블을 사용

 

세그먼트 테이블의 엔트리(STE)는 Base와 Limit을 가짐

(물리적 메모리내 세그먼트 시작주소 & 길이)

 

레지스터는 STBR(Segment-Table Base Register)과

(*해당 프로세스의 Segment Table 위치를 저장)

 

STLR(Segment-Table Length Register) 를 사용

(*해당 프로세스의 주소공간의 세그먼트 총 갯수를 저장)

 

1. CPU의 논리적 주소생산 (s,d)

2. 요청된 세그먼트 번호와 STLR값 비교

3. 논리적 주소의 d(offset)값과 해당세그먼트의 길이를 비교

(=STE의 Limit과 비교)

(주소변환전)

 

---------------------------------Valid Memory Access------------------------------------

 

(위의 조건을 모두 만족할시 주소변환 실행)

4.  주소변환 실행

5. STE의 보호비트들을 통해 검증

(유효비트는 주소변환정보가 유효한지를 검증)

---

# 공유세그먼트

공유페이지 개념과 동일

(동일한 논리주소)

 

# 세그먼테이션의 장점

페이징 보다 공유와 보안측면에서 우수

(의미적 크기로 공유와 보안을 하기 때문)

 

*동일 페이지에 사유데이터와 공유데이터가 같이 있는 경우가 발생

 

# 세그멘테이션의 단점

외부조각의 발생가능성

---

# 세그먼트 가용공간 할당방식

 

First fit, Best fit

 

---

7. 페이지드 세그먼테이션

(Pageds Segmentation)

 

페이징과 세그먼트의 장점만을 취하는 주소변환기법

 

분할방식은 의미단위의 세그먼트 채용

메모리 적재방식은 물리적단위의 페이지 채용

(단, 세그먼트는 페이지의 배수여야함)

 

=> 외부조각 해결 + 세그먼트 단위 공유 및 보호 가능

---

# 프로그램의 논리적 주소

<세그먼트번호(s), 오프셋(d)>

---

# 주소변환

 

2단계 테이블을 사용

(외부 : 세그먼트 테이블)

(내부 : 페이지 테이블)

 

테이블의 참조로 인해,

세그먼트 마다 페이지테이블을 가지는 구조

 

 

1.  <s,d>의 s를 이용한 STE 접근

2. STE의 Base와 Limit으로 유효성 검사 

3. d의 상위비트로 s의 Base로 부터 d에 위치한 페이지 접근

4. 접근한 페이지의 PTE에서 물리적메모리 시작주소 획득

5. d의 하위비트로 물리적메모리의 원하는 데이터에 접근

---

---