[OS] Memory Management

Logical VS Physical Address 

■ 메모리

ㅡ> 주소를 통해 접근

 

■ 주소

ㅡ> 논리적 주소 ▶ CPU가 참조하는 가상의 주소

ㅡ> 물리적 주소 ▶ 실제 메모리의 주소

 

■ 왜 필요한가

ㅡ> 논리적 주소 : 없으면 코드에 지정된 주소가 바로 물리적 주소가 되어, 프로그램간 충돌

ㅡ> 물리적 주소 : 없으면 프로그램이 어디에 있는지 못찾음

 

■ 주소 바인딩

ㅡ> 논리적 주소를 물리적 주소에 연결하는 것

 

■ Symbolic Address : 사람이 이해하기 쉽게 기호로 된 주소

ㅡ> ex) int x;에서 x

ㅡ> 컴파일러가 상징주소를 논리주소로 변환해줌

주소 바인딩 종류

시점에 따른 분류

3가지 종류

■ (임의로 만든 언어라 여기에 해석을 붙인다)

Add A B

ㅡ> A와 B를 더해서 A에 저장

Jump C

ㅡ> C로 가라

 

■ 그림

ㅡ> Symbolic ▶ Logical ▶ Physical 가면서 주소가 바뀌는 모습

 

■ Compile time binding

ㅡ> 컴파일 때 정해진 논리적 주소가 곧 물리적 주소

ㅡ> 비효율적이라 현대에는 안씀

ㅡ> absolute code : 컴파일을 다시 하지 않는 한, 주소가 바뀌지 않음

 

■ Load time binding

ㅡ> 실행해서 메모리에 올라갈 때, 비어있는 주소에 바인딩

ㅡ> 그림에서는 500번지

ㅡ> relocatable code : 실행 다시하면 주소 바꿀 수 있음

 

■ Run time binding

ㅡ> 실행해서 메모리에 올라갈 때, 비어있는 주소에 바인딩

ㅡ> 실행중에 바뀔 수도 있음

ㅡ> 그림에선 300번지에서 700번지로 바뀜

ㅡ> 주소가 계속 바뀌어서, CPU가 주소를 참조할 때마다 바인딩을 점검 ▶ 속도를 위해, 하드웨어적인 지원이 필요 (MMU)

Memory-Management Unit (MMU)

■ MMU

ㅡ> 하드웨어

 

■

현대 OS는 필요한 부분만 메모리에 올리고 나머지는 DISC로 쫓아내는 방식을 쓰지만

여기서는 통채로 메모리에 올리는 고전적인 방식을 다룬다

 

■ 사용자 프로그램

ㅡ> logical address만을 다룬다

■ 레지스터 2개를 사용해서 주소변환을 한다

ㅡ> base register (relocation register)

ㅡ> limit register

 

■ CPU에서 346번지(논리적 주소)를 요청하면

base register값에 346을 더해서 물리적 주소를 도출한다

(그림 참고)

 

■ limit register은 프로그램이 쓰는 메모리 최대 크기 ▶  범위를 벗어난 요청은 trap을 건다 (소프트웨어 인터럽트)

(그림 참고)

logical address < limit register

를 만족하면

relocation register + logical address

를 한다

메모리관리 4가지기법

 

여기있는 것들은

Runtime Binding을 기반으로 한다

ㅡ> 물리적 주소가 유동적이어야 메모리 빈공간을 효율적으로 사용하기 때문

Dynamic Loading

메모리에 동적으로 올리는 방법

 

프로그램은 자주 사용되지 않는 부분이 많음

(대부분 오류 처리 루틴)

 

그래서 프로그램 전체를 메모리에 올리는게 아니라

필요한 부분만 그때그때 올림

Overlays

메모리가 매우 작던 초창기시절

프로그램의 크기가 메모리보다 커서, 여러개로 쪼개야 했다

 

오버레이

ㅡ> 프로그램을 여러개의 세그먼트로 나눔

ㅡ> 메모리에 세그먼트들을 교체해가며 필요한부분만 올림

 

Manual Overlay

ㅡ> 사용자가 직접 프로그래밍

ㅡ> 코딩이 매우 복잡

ㅡ> 다이나믹 로딩은 라이브러리가 있지만 이건 개발자가 직접 코딩해야 됨

Swapping

메모리에 너무 많은 프로그램이 올라와있으면 비효율적이라

스와퍼가 쫓아냄

 

주로 CPU 우선순위가 낮은 프로그램을 swap out시킨다

 

디스크는 디스크 헤더가 움직이는 시간이 대부분이지만

swap time은 data 양이 너무 많아서 transfer time에 비례한다

 

페이징

ㅡ> 프로세스 전체를 쫓아내는게 아니라 프로세스를 쪼개서 일부만 쫓아내는 방법

Dynamic Linking

■ linking

프로그램 컴파일하고 링크해서 실행파일을 만든다

여러군데에 존재하던 컴파일의 파일들을 엮어서 하나의 실행파일 만드는 과정이 링킹

내가 만든 소스파일이나 누군가 만든 라이브러리 들을 링킹

 

■ Static linking

ㅡ> 라이브러리가 실행파일 코드에 포함

ㅡ> 단점 : 동일한 라이브러리를 각각 프로세스의 메모리에 올려서 메모리 낭비

 

■ Dynamic linking

ㅡ> 라이브러리가 코드가 실행파일에 포함되지 않고, 실행시 연결함

ㅡ> 라이브러리 위치를 찾을 수 있는 포인터(stub)만 가지고 있음

ㅡ> 동일한 라이브러리는 메모리에 하나만 올려도 됨

Physical Memory 관리

■ 연속할당

ㅡ> 프로그램을 통째로 올림

 

■ 불연속할당

ㅡ> 프로그램을 쪼개서 여기저기 분산되어 올림

ㅡ> 현대적인 방식

Contiguous allocation (연속 할당)

■ 고정 분할 방식

ㅡ> 메모리를 미리 나누어 놈

■ 가변 분할 방식

ㅡ> 메모리를 미리 분할x

 

■ 고정분할 방식

프로그램 A는 분할1에 올려놓음

프로그램B는 분할2보다 커서 분할3에 올려놓음

그러면 낭비되는 조각이 생기는데, 외부 조각과 내부 조각이 있다

 

■ 가변 분할 방식

ㅡ> 프로그램 B가 끝낫는데 프로그램 D를 넣기엔 공간이 작음

ㅡ> 프로그램 B가 끝난 자리는 외부 조각이 됨

■ 외부 조각

ㅡ> 프로그램의 크기가 분할보다 큼

 

■ 내부 조각

ㅡ> 분할의 크기가 프로그램보다 큼 (분할 내부에 남는 조각)

■ Hole

ㅡ> 가용 메모리 공간

 

■ 어떤 hole에 프로그램을 올리는게 좋을까?

ㅡ> Dynamic Storage-Allocation Problem

사이즈 n 이상인 hole중에 어떤 hole에 넣을 것인가

 

■ First-fit

ㅡ> 최초로 찾아지는 hole에 할당

■ Best-fit

ㅡ> 가장 작은 hole에 할당

ㅡ> 전체 hole을 탐색해야 함

ㅡ> 작고 많은 hole이 생성됨

■ Worst-fit

ㅡ> 가장 큰 hole에 할당

ㅡ> 전체 hole 탐색해야 함

ㅡ> 큰 hole들이 생성됨

■ compaction

ㅡ> 사용중인 메모리들을 한군데로 몰아서 hole을 다른 한곳으로 몰아냄

ㅡ> 매우 비용이 많이 드는 방법

Noncontiguous allocation (불연속 할당)

Paging

■

프로그램을 페이지 단위로 잘라서 페이지 단위로 메모리에 올렸다 내렸다 함

물리적 주소도 공간을 페이지 단위로 잘라 둠 (page frame)

 

■

hole에 대한 문제가 없어지고 아무 페이지 프레에나 넣어도 되는게 장점

ㅡ> Dynamic Storage-Allocation Problem이 없음

 

■

대신, 주소변환이 복잡해짐. 주소변환을 페이지별로 해야 됨 (MMU)

 

■

프로그램의 크기가 반드시 페이지크기로 나누어 떨어지지 않기 때문에

마지막 조각이 페이지 크기보다 작아서

내부조각이 생길 수 있다

Segmentation

■ 의미단위

프로그램을 같은 크기로 자르는게 아니라,

의미 있는 단위로 자름

 

code, data, stack으로 자를 수도 있고

더 자세히, 함수별로 자를 수도 있다

 

 

■ 불균일

크기가 불균일해서

Dynamic Storage-Allocation Problem 발생

Paging

페이징에서 주소변환을 위해서는

페이지 테이블이 필요하다

 

■ 페이지 테이블

ㅡ> 페이지 번호에 해당하는 엔트리에 프레임 번호를 바인딩

p ㅡ> 페이지 번호

f ㅡ> 프레임 번호

d ㅡ> 오프셋 (베이스에서 얼마나 떨어져있나)

Pagge Table 구현

■

프로그램 하나에 페이지가 백만개는 되는데

레지스터에는 백만개의 엔트리를 담을 수 없다 (용량부족)

ㅡ> 따라서, page table은 레지스터가 아닌 메모리에 올린다

ㅡ> 그래서 메모리에 접근할 때, 2번의 메모리 접근이 필요하다 (1.페이지 테이블  2. 데이터)

ㅡ> 2번 접근하다보니 속도가 느려져서, TLB라는 일종의 캐쉬 하드웨어를 사용해서 속도를 커버한다

 

■

베이스 레지스터가 여기서는 페이지 테이블의 위치를 가리키고

랭스 레지스터가 테이블의 크기를 보관한다

TLB

■ TLB는 캐쉬 메모리

ㅡ> 메인 메모리보다 접근 속도가 빠름

 

■

TLB에 page table 엔트리 일부를 저장해놓는다

■

CPU는 먼저 TLB를 확인하고 거기 없을때만 page table로 간다

■

page table에서는 위에서부터 순서대로 page number라고 보면 되지만

TLB는 페이지 일부만 있어서 page number을 따로 저장해야 한다

■

특정 page number가 있는지 TLB 전체를 탐색해야 되기 때문에

parallel search가 가능한 Associative Register을 사용한다

(안그러면 느림)

■

프로세스마다 page table이 다르기 때문에

프로세스가 바뀌면 TLB도 바뀌어야 한다

ㅡ> flush 해버린다

접근시간 효율

■

ε = TLB 접근 시간

1 = 메모리 접근 시간

α = TLB에서 주소변환 정보 찾아지는 비율

 

■

(1+ ε) = TLB 확인하고, 실제 메모리의 data로 접근하는 시간

(2 + ε) = TLB 확인하고, page table확인하고, 실제 메모리의 data로 접근하는 시간

 

■ 2+ ε - α 

ㅡ> 보통, ε 에 비해 α 가 커서 결과가 2보다 작음

ㅡ> page table만 있으면 결과는 2

Two-Level Page Table

■ 페이지 테이블이 2단계로 존재한다

ㅡ> 공간을 절약하기 위함

 

 

■ 32비트 주소체계

ㅡ> 2^32개의 번지가 있음

ㅡ> 각 번지는 1바이트의 크기

ㅡ> 4GB

 

ex) 페이지 하나의 크기가 4K

ㅡ> 4G의 메모리를 4K로 나누면 1M개의 페이지가 나온다

ㅡ> 페이지 엔트리 하나의 크기가 4B라고 하면, 프로세스 당 4MB의 page table가 필요하다

ㅡ> 대부분 프로그램은 페이지중 일부만 자주 사용하기 때문에, 이건 메모리 공간 낭비다

 ㅡ> 그래서 2단계 페이지 테이블을 사용

 

■ 쓰는이유 [why]

2단계 페이지 테이블을 꽉채우면

사실 공간도 손해고 시간도 손해임 

but, 안쓰는 페이지 테이블을 안만들어 버릴 수 있음

ㅡ> 공간 절약, 시간은 손해

 

■  1단계 vs 2단계 [how]

1단계 페이지 테이블에서는 배열로 인덱싱해서

잘 안쓰는 페이지에도 메모리 할당해야 됨

2단계 페이지 테이블에서는 포인터로 페이지 테이블을 인덱싱해서

잘 안쓰는 부분의 포인터를 null 해버려서 메모리 안씀

(포인터는 상위 페이지 테이블에서 찾음)

 

■ 안쪽 페이지 테이블

ㅡ> 안쪽 페이지 테이블은 메모리에 올려져있다

ㅡ> 그래서 안쪽 페이지 테이블의 크기 자체가 페이지 프레임의 크기와 같다

ex)

프레임 크기 4KB

안쪽 페이지 테이블 크기 4KB

테이블 엔트리 크기 4B

엔트리의 갯수 1K

p1으로 바깥 페이지 테이블의 위에서 몇번째인지 찾고

p2로 안쪽 페이지 테이블의 위에서 몇번째인지 찾고

d로 프레임 내에서 위에서 몇번째의 data인지 찾는다

예시

■ page offset

ㅡ> 페이지 하나의 크기가 4KB이다.

ㅡ> 4KB = 2^12 B  ▶ 2^12 번지까지 주소를 표현하려면 12자리의 숫자가 필요함 ▶ page offset = 12 비트

 

■  page number

ㅡ> 엔트리 갯수는 위에서 1K임을 도출했음 ▶ 안쪽 테이블을 위해 10비트가 필요함

ㅡ> 남은 10비트는 바깥쪽 테이블에게 사용

Multilevel Paging과 성능

■ 페이지 테이블을 다단계로 만들면

그만큼 메모리 접근을 여러번 해야돼서

속도가 느려진다 

ㅡ> TLB로 속도 커버

 

■ 그림에 나온 예시

ㅡ> TLB 사용하면 4단계 페이지 테이블 오버헤드가 평균 28ns정도만 추가된다

Page table의 부가적인 비트

Valid(v) / invalid(v) Bit

■ 페이지 테이블에는 사실 주소변환 정보만 있는게 아니라 부가적인 정보들이 있다

그 중 하나가 Valid Bit이다

 

■ 그림

v ㅡ> valid

i ㅡ> invalid

 

invalid 엔트리에 있는 주소변환 정보는

의미없는 정보임

Protection bit

■  어떤 연산에 대한 접근권한이 있느냐를 나타냄

ㅡ> code 영역 : read-only 

ㅡ> stack, data 영역 : read, write

Inverted Page Table

■  page table의 문제

ㅡ> 차지하는 용량이 큼

ㅡ> (S) inverted page table

Architecture

■  원래 프로세스별로 page table이 존재했는데

여기서는 시스템에 하나의 page table만 존재한다

 

■  원래는 프로세스 페이지 갯수만큼 엔트리 갯수가 있었는데

여기서는 페이지 프레임의 갯수만큼 엔트리 갯수가 있다

 

■  inverted

원래는 프로세스의 n번째 페이지면

테이블의 n번째 엔트리에서 물리적 메모리 주소가 나왔는데

여기서는 피지컬 메모리의 n번째 프레임이면

테이블의 n번째 엔트리에서 논리적 메모리의 주소가 나온다

ㅡ> pid : 어떤 프로세스의 페이지인지 (프로세스 id)

ㅡ> p : 몇번째 페이지인지

ㅡ> 논리적 메모리에서 인덱스로 찾아갈 수 없고 전체탐색을 해야되니 속도는 느려진다 ▶ associative register로 병렬탐색해서 오버헤드 줄임

ㅡ> 메모리는 절약된다

 

■  탐색

ㅡ> 테이블에서 pid와 p가 일치하는 엔트리를 찾는다

ㅡ> 그 엔트리의 인덱스가 프레임 번호다

Shared Page

■ 여러 프로세스가 쓰는 동일한 코드는

물리적 메모리에 1개만 올리고 각각 매핑한다

 

 

■ shared code가 만족해야할 조건

ㅡ> 메모리에 read-only로 올린다

ㅡ> 모든 프로세스에 동일한 logical address를 가져야 한다 (코드 내부의 점프(Jump)나 함수 호출(Call) 같은 주소 기반 동작 때문)

예시

■ '아래한글'을 3개의 프로세스로 돌리고 있으면

프로그램의 코드 부분은 3개의 프로세스가 똑같은 것을 써도 된다

ㅡ> shared code

Segmentation

■ 페이징

ㅡ> 고정된 크기로 분할

■ 세그멘테이션

ㅡ> 의미 단위로 분할

ㅡ> ex) code/data/stack

ex)

Architecture

■ 논리적 주소 구성

ㅡ> <segment-number, offset>

ㅡ> <세그먼트 번호, 세그먼트 안에서 얼마나 떨어져 있는지>

 

■ 세그먼트 테이블

ㅡ> 세그먼트 논리적 주소와 물리적 주소를 매핑

 

■ 레지스터

ㅡ> base : 세그먼트 테이블의 위치

ㅡ> length : 세그먼트 테이블의 길이 (= 세그먼트의 갯수)

■

단점 : 크기가 분귤일해서 외부조각 발생

장점 : 의미 단위로 일할때 좋음 (ex. Read Write Execution 권한), 그리고 대부분 segmentation이 paging보다 테이블이 작음

 

■

Protection은 세그먼트 단위로 해야 편함

페이지 단위로 하면, 어떤 페이지에는 code와 data가 같이 들어가는데

이걸 read-only로 해야되냐 write권한을 줘야하냐 이런게 복잡해짐

 

■

sharing할 때도 segment단위가 좋다

ex) sharing

■ sharing code는 논리적 주소가 같아야 한다는 특성

ㅡ> 두 프로세스에서 둘다 0번 세그먼트

 

■ 물리적 주소에서도 sharinge code인 'editor'는 하나만 있다

Hardwawre

■

s = segment number

d = offset

 

■

페이지와 다르게 세그먼트의 길이는 균일하지 않아서

테이블에 limit에다 길이를 저장해둔다

 

■ s < STLR

ㅡ> 세그먼트의 요청(s)이 세그먼트 테이블의 길이(STLR)보다 크면 트랩을 건다

 

■ d < limit

ㅡ> 오프셋이 세그먼트의 길이보다 길면 트랩을 건다

 

■ 주소

ㅡ> base + d

ㅡ> 시작위치 + 오프셋

Paged Segmentation

■ 세그먼트를 여러개의 페이지로 구성

ㅡ> 외부조각으로 인한 allocation문제 해결

ㅡ> 세그먼트 당 페이지 테이블이 하나 존재

 

■

세그먼트의 길이(segment length)보다 논리적 주소의 오프셋(d)이 크면

trap을 건다

 

■ 오프셋(d)

ㅡ> p와 d'로 분해

ㅡ> 세그먼트 안에서의 페이지 번호와, 그 페이지 안에서의 오프셋을 나타냄

 

■ f

ㅡ> 세그먼트 안에서 프레임 번호

여기서 OS의 역할은 없다

메모리관리 챕터에서 나오는 일은 하드웨어가 하는 일이다

 

OS가 관리하려면, 주소변환 할 때마다 CPU가 OS에 넘어가야 되는데

그건 말이 안된다

 

메모리가 아니라 I/O장치에 접근할 때 OS가 일한다

다음챕터인 버추얼 메모리도 OS가 일한다.