[OS] 가상 메모리의 의미 및 할당 기법들

1. Non-continuous Memory Allocation

1) 의미

- 사용자 프로그램을 여러 개의 block으로 분할

- 실행 시에는 필요한 block들만 메모리에 적재하고, 나머지 block들은 swap device에 존재

- Virtual memory(가상 메모리)가 이 원리를 따름

 

2) 구조 및 동작

Virtual address는 v=(b,d)로 표현할 수 있다.

여기서 b는 블록의 번호이고, d는 블록의 시작점으로부터 떨어진 정도에 대한 값이다.

※ d를 offset이라고도 함

 

 

Address mapping 정보 관리는 Block Map Table(BMT)이 맡으며, 이 table은 Kernel 공간에 프로세스마다 하나씩 있다.

그리고 BMT의 residence bit는 메모리상에 적재되어 있는가의 여부를 나타내는 비트다.

residence bit가 1인 경우에는 BTM에서 b에 대한 실제 주소 a를 가져오고,

residence bit가 0인 경우에는 swap device(가상 메모리)에서 해당 블록을 메모리로 가져오고 BTM을 업데이트한 뒤에, 업데이트한 BTM에서 b에 대한 실제 주소 a를 가져오게 된다.

 

 

2. 메모리 할당 기법들

1) Paging System

(1) 의미

- 프로그램을 같은 크기의 블록으로 분할하는 기법을 이용한 시스템

- Page는 프로그램의 분할된 block을 의미함

- Page frame는 메모리상에 있는 Page의 틀이며, Page와 같은 크기로 분할됨

※ Window의 page size는 일반적으로 4KB임

 

(2) 특징

- 구현과 관리가 간단함

- 프로그램을 일정 크기로 자르다보니 논리적 구조를 고려할 수 없기 때문에, Page 공유 및 보호 과정이 복잡함

> Segmentation System으로 해결 가능

- 크기 문제로 메모리에 못 들어가는 경우는 없으므로 외부 단편화는 발생하지 않음

- 프로그램을 정해진 크기로 나누고 남은 부분에 의한 내부 단편화는 발생할 수 있음

 

(3) Mapping 방법들

<1> Direct Mapping(직접 매핑)

① 구조

- v = (p, d) [p=page number, d=displacement(offset)]

- PMT(Page Map Table)

 

② 동작

동작은 Block mapping과 유사하다.

그리고 residence bit이 0인 경우를 page fault★라고 하는데, page fault는 Context switching을 발생시키기 때문에 Overhead가 큰 편이다. 즉, page fault를 가능한 줄이기 위한 기법들이 요구된다.

 

③ 문제점

- 메모리 접근 횟수가 높음

- PMT를 위한 메모리 공간 필요

 

④ 해결 방안

- Associative mapping(TLB)

- PMT 전용 기억 장치 사용(Dedicated register or cache memory)

- 계층 페이징, 해시 테이블, 변환 테이블 등

 

<2> Associative Mapping(연관 매핑)

① 구조

- TLB(Translation Look-aside Buffer)★ : Table을 넣어두는 버퍼이며, 속도가 빠름(전용 HW)

TLB : 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시 - 위키 백과

- 그 외의 구조는 직접 매핑과 유사

 

② 동작

TLB에서는 병렬 탐색이 가능하도록 구현되어 있기 때문에 속도가 빠른 것이다.

 

③ 문제점

- 비싼 하드웨어이기 때문에 큰 PMT를 다루기 어려움

 

<3> Hybrid Direct/Associative Mapping

① 의미 및 구조

- Direct Mapping, Associative Mapping을 혼합 : HW 비용 감소, Associative Mapping의 장점 활용

- 작은 크기의 TLB 사용 : PMT 중 일부 entry들만 적재(Locality 활용)

※ Locality(지역성) : 한 번 접근한 영역 혹은 그 인접 영역을 다시 접근하는 특성

 

② 동작

프로세스의 PMT가 TLB에 적재되어 있는지 추가로 확인해야 한다.

TLB에 적재되어 있는 경우에는 residence bit를 검사하고 page frame번호를 확인하면 되고,

TLB에 적재되어 있지 않은 경우에는 Direct mapping으로 page frame번호를 확인하고 해당 PMT entry를 TLB에 적재한다.

 

(4) Frame Table

<1> 의미 : Page frame을 관리하기 위한 table

<2> 구조

- AV : 사용 가능한 프레임의 시작점

- link : 사용 가능한 프레임들을 Linked list로 연결

 

(5) Page Sharing

<1> 의미 : 여러 프로세스가 특정 page를 공유하는 것

<2> 공유 가능한 page들

- 순수 코드

- Read-only data

- Read-write data(병행성 제어 기법 필요)

<3> 발생 가능한 문제들

① page 내에서 page number값을 참조하는 로직이 존재할 경우

프로세스간에 page number값이 다를 경우 문제가 생길 수 있는데, 공유 페이지에 대해서는 프로세스간에 page number값을 통일하도록 약속함으로써 해결할 수 있다.

② 보호 문제

Protection bit를 사용하여 프로세스에게 동작별 권한을 부여하면 된다. 동작으로는 메모리 적재 여부, 읽기 여부, 수정 여부, 실행 여부가 있다.

<4> 예시

 

 

2) Segmentation System

(1) 의미

- 프로그램을 논리적 block으로 분할하기 때문에 block의 크기가 서로 다를 수 있음

- Variable Partition Multiprogramming(VPM)과 유사함

- Segment sharing/protection이 용이함

- Address mapping 및 메모리 관리의 Overhead가 큼

- 내부 단편화는 발생하지 않지만 외부 단편화는 발생할 수 있음

- 예) stack, heap 등

 

(2) 구조

- v = (s, d) [s=segment number, d=displacement(offset)]

- SMT(Segment Map Table)

 

(3) 동작

Page System과 유사하다. 물론 Segment mapping overhead를 줄이기 위해 TLB를 이용할 수도 있다.

단, d가 segment 길이보다 큰 경우에는 segment overflow 예외 처리 모듈을 호출하고,

protection bit을 확인해봐서 허가되지 않은 연산일 경우에는 segment protection 예외 처리 모듈을 호출하는 작업이 필요하다.

resident bit=0인 경우를 segment fault라고 한다.

 

(4) Partition Table / State Table

<1> 의미 : Segment 적재를 관리하기 위한 table

<2> 구조

 

 

3) Hybird paging/segmentation System

(1) 의미

- 프로그램을 논리 단위의 segment로 분할 후, 각 segment를 고정된 크기의 page로 다시 분할

- Page sharing/protection이 쉬움

- 메모리 할당/관리 overhead가 작음

- 내부 단편화가 발생할 수 있지만, 외부 단편화는 발생하지 않음

 

(2) 구조

- v=(s, p, d) [s=segment number, p=page number, d=displacement(offset)]

- SMT, PMT 모두 사용(SMT는 각 프로세스마다, PMT는 각 segment마다 존재)

- Fixed Partition Multiprogramming(FPM)과 유사함

 

(3) Hybird에서의 SMT

실제로 메모리에 올라가는 것은 segment가 아니기 때문에 resident bit는 사라지고,

PMT 주소가 새로운 필드로 추가되었다.

 

(4) 동작

 

(5) 문제점

전체 테이블의 수가 증가하므로 메모리 소모가 크며 mapping 과정이 복잡함

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN