Memory Management

Logical VS Physical Address

Logical Address(Virtual Address)

프로세스마다 독립적으로 가지는 주소 공간
각 프로세스마다 0번지부터 시작
CPU가 보는 주소는 Physical Address일 것 같지만, Logical Address임

Physical Address

실제 메모리에 올라가는 위치

주소 바인딩(Address Binding)

물리적인 메모리 주소를 결정하는 것

Symbolic Address → Logical Address → Physical Address

Compile Time Binding

물리적 메모리 주소(Physical Address)가 컴파일 시 알려짐
시작 위치 변경 시, 재컴파일
컴파일러는 절대 코드(Absolute Code)를 생성
컴파일 시 결정된 절대적인 위치에만 올라가 비효율적

Load Time Binding

Loader 책임 하에 물리적 메모리 주소 부여
컴파일러가 재배치 가능 코드(Relocatable Code)를 생성한 경우 가능

Execution Time Binding(Runtime Binding)

수행이 시작 된 이후에도, 프로세스의 메모리 상 위치를 옮길 수 있음
CPU가 주소를 참조할 때마다 Binding을 점검(Address Mapping Table)
하드웨어적 지원이 필요

base and limit registers, MMU

최근의 시스템

Memory Management Unit(MMU)

Logical Address를 Physical Address로 Mapping해주는 Hardware Device

MMU Scheme

사용자 프로세스가 CPU에서 수행되며 생성하는 모든 주소값에 대해 Base Register(Relocation Register)의 값을 더한다.

User Program

Logical Address만을 다룬다.
실제 Physical Address를 볼 수 없으며, 알 필요가 없다.

Dynamic Relocation

주소 변환

Hardware Support for Address Translation

운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터

Relocation Register(Base Register)

접근할 수 있는 물리적 메모리 주소의 최소값

Limit Register

논리적 주소의 범위

악성 프로그램이 Limit Register 범위 밖의 메모리를 접근하려고 하면 trap

Dynamic Loading

프로세스 전체를 메모리에 다 올리는 것이 아니라, 해당 루틴이 불려질 때 메모리에 load하는 것

Memory Utilization의 향상

가끔씩 사용되는 많은 양의 코드의 경우 유용

ex) 가끔씩 사용되는 오류 처리 루틴

운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 지원 가능)

OS가 지원하는 페이징이 아니라 프로그래머가 하는 것을 의미

하지만 섞어 쓰기도 함

Loading: 프로그램을 메모리로 올리는 것

Overlays

메모리에 프로세스의 부분 중 실제 필요한 정보만 올리는 것

프로세스의 크기가 메모리보다 클 때 유용

OS의 지원 없이 프로그래머에 의해 구현

작은 공간의 메모리를 사용하던 초창기 시스템에서 수작업으로 프로그래머가 구현

Manual Overlay
매우 복잡

Swapping

프로세스를 일시적으로 메모리에서 Backing Store로 쫓아내는 것

Backing Store(Swap Area)

디스크

많은 사용자의 프로세스 이미지를 담을 만큼 충분히 빠르고 큰 저장 공간

Swap in / Swap out

일반적으로 중기 스케쥴러(Swapper)에 의해 swap out 시킬 프로세스 선정
Priority-Based CPU Scheduling Algorithm

Priority가 낮은 프로세스를 Swapped out 시킴
Priority가 높은 프로세스를 메모리에 올려 놓음

Compile Time 혹은 Load Time Binding에서는 원래 메모리 위치로 Swap in 해야 함
Execution Time Binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
Swap Time은 대부분 Transfer Time(Swap되는 양에 비례하는 시간)임

Dynamic Linking

Linking을 실행 시간(Execution Time)까지 미루는 기법

Static Linking

라이브러리가 프로그램의 실행 파일 코드에 포함됨
실행 파일의 크기가 커짐
동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로, 메모리 낭비

ex) printf 함수의 라이브러리 코드

Dynamic Linking

라이브러리가 실행 시 연결(Link)됨
라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
라이브러리가 이미 메모리에 있으면, 그 루틴의 주소로 가고, 없으면 디스크에서 읽어옴
OS의 도움이 필요

Allocation of Physical Memory

메모리는 일반적으로 두 영역으로 나뉘어 사용

OS 상주 영역

Interrupt Vector와 함께 낮은 주소 영역 사용

사용자 프로세스 영역

높은 주소 영역 사용

사용자 프로세스 영역의 할당 방법

Contiguous Allocation

각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

Fixed Partition Allocation
Variable Partition Allocation

Non-Contiguous Allocation

하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

Paging
Segmentation
Paged Segmentation

Contiguous Allocation

고정 분할(Fixed Partition) 방식

물리적 메모리를 몇 개의 영구적 분할(Partition)로 나눔
분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
분할 당 하나의 프로그램 적재
융통성이 없음

동시에 메모리에 Load되는 프로그램의 수가 고정
최대 수행 가능 프로그램 크기 제한

Internal Fragmentation 발생(External Fragmentation도 발생)

프로그램 크기보다 분할의 크기가 작은 경우
하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
특정 프로그램에 배정되었지만 사용되지 않는 공간

가변 분할(Variable Partition) 방식

프로그램의 크기를 고려해서 할당
분할의 크기, 개수가 동적으로 변함
기술적 관리 기법 필요
External Fragmentation 발생

프로그램 크기보다 분할의 크기가 작은 경우
아무 프로그램도 배정되지 않은 빈 곳임에도, 프로그램이 올라갈 수 없는 작은 분할

Hole

가용 메모리 공간
다양한 크기의 Hole들이 메모리 여러 곳에 흩어져 있음
프로세스가 도착하면 수용 가능한 Hole을 할당
운영채제는 다음의 정보를 유지

할당 공간
가용 공간(Hole)

Dynamic Storage-Allocation Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 Hole을 찾는 문제

First-fit

Size가 n 이상인 것 중, 최초로 찾아지는 Hole에 할당

Best-fit

Size가 n 이상인 가장 작은 Hole을 찾아서 할당
Hole들의 리스트가 크기 순으로 정렬되지 않은 경우, 모든 Hole의 리스트를 탐색해야함
많은 수의 아주 작은 Hole들이 생성됨

Worst-fit

가장 큰 Hole에 할당
역시 모든 리스트를 탐색해야함
상대적으로 아주 큰 Hole들이 생성됨

First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐(실험적 결과)

Compaction

External Fragmentation 문제를 해결하는 한 가지 방법
사용 중인 메모리 영역을 한군데로 몰고, Hole들을 다른 한 곳으로 몰아 큰 Block을 만드는 것
비용이 매우 많이 듦
최소한의 메모리 이동으로 Compaction하는 방법(매우 복잡한 문제)
Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우(Execution Time Binding)에만 수행될 수 있다.

Non-Contiguous Allocation

Paging

Process의 Virtual Memory를 동일한 사이즈의 Page 단위로 나눔

Virtual Memory의 내용이 Page 단위로 Non-Continous하게 저장됨

일부는 Backing Storage에, 일부는 Physical Memory에 저장

Basic Method

Physical Memory를 동일한 크기의 Frame으로 나눔
Logical Memory를 동일 크기의 Page로 나눔(Frame과 같은 크기)
모든 가용 Frame들을 관리
Page Table을 사용하여 Logical Address를 Physical Address로 변환
External Fragmentation 발생 X
Internal Fragmentation 발생 가능

Paging Example

Address Translation Architecture

Paging Hardware with TLB

Associative Register

Associative Registers(TLB): Parallel Search 가능

TLB에는 Page Table 중 일부만 존재

Address Translation

Page Table 중 일부가 Associative Register에 보관되어 있음
만약 해당 Page #가 Associative Register에 있는 경우, 곧바로 Frame #를 얻음
그렇지 않은 경우, Main Memory에 있는 Page Table로부터 Frame #를 얻음
TLB는 Context Switch 때, Flush(Remove Old Entries)

Effective Access Time(EAT)

Associative Register Lookup Time = ε

Memory Cycle Time = 1

Hit ratio = α

Associative Register에서 찾아지는 비율

Effective Access Time(EAT)

Two-Level Page Table

현대 컴퓨터는 Address Space가 매우 큰 프로그램을 지원한다.

32 Bit Address 사용 시, 2^32(4G)의 주소 공간

Page Size가 4k 일 때, 1M개의 Page Table Entry가 필요
각 Page Entry가 4B 일 때, 프로세스당 4M의 Page Table 필요
그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로, Page Table 공간이 심하게 낭비됨

따라서 Page Table 자체를 Page로 구성
사용되지 않는 주소 공간에 대한 Outer Page Table의 엔트리 값은 NULL(대응하는 Inner Page Table이 없음)

Two-Level Paging Example

Logical Address(on 32-bit machine with 4k page size)의 구성

20 bit의 Page Number
12 bit의 Page Offset

Page Table 자체가 Page로 구성되기 때문에, Page Number는 다음과 같이 나뉜다. (각 Page Table Entry가 4B)

10 bit의 Page Number
10 bit의 Page Offset

따라서, Logical Address는 다음과 같다.

P1은 Outer Page Table의 Index

P2는 Outer Page Table의 Page에서의 변위(Displacement)

Address-Translation Scheme

2단계 Paging에서의 Address-Translation Scheme

Multi-Level Paging and Performance

Address Space가 더 커지면 다단계 Page Table이 필요

각 단계의 Page Table이 메모리에 존재하므로 Logical Address의 Physical Address 변환에 더 많은 메모리 접근 필요

TLB(Translation Lookaside Buffer)를 통해 메모리 접근 시간을 줄일 수 있음

4단계 페이지 테이블을 사용하는 경우

메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고
TLB Hit Ratio가 98%인 경우

Effective Memory Access Time = 0.98 * 120 + 0.02 * 520 = 120ns
결과적으로 주소 변환을 위해 28ns만 소요

Valid(v) / Invalid (i) Bit in a Page Table

Logical Memory / Page Table / Physical Memory

Page Table은 index로 접근하기 때문에 그 사이가 비어있어도 채워져있어야 한다.

Memory Protection

Page Table의 각 Entry마다 아래의 Bit를 둔다.

Protection Bit: 흔히 말하는 보안상 Protection은 아님(프로세스마다 메모리가 구분되어있어 애초에 접근 불가능함)

Page에 대한 접근 권한(Read/Write/Read-Only)

Valid-Invalid Bit

Valid는 해당 주소의 Frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
Invalid는 해당 주소의 Frame에 유효한 내용이 없음*을 뜻함(접근 불허)

* 1) 프로세스가 그 주소 부분을 사용하지 않는 경우 2) 해당 페이지가 메모리에 올라와 있지 않고, Swap Area에 있는 경우

Inverted Page Table

Page Table이 매우 큰 이유

모든 Process별로 그 Logical Address에 대응하는 모든 Page에 대해 Page Table Entry가 존재
대응하는 Page가 메모리에 있던 아니던 간에 Page Table에는 Entry로 존재

Inverted Page Table

Page Frame 하나 당 Page Table에 하나의 Entry를 둔 것(System-Wide)
각 Page Table Entry는 각각의 물리적 메모리의 Page Frame이 담고 있는 내용 표시(PID, Process의 Logical Address)
단점

테이블 전체를 탐색해야 함

해결책

Associative Register 사용(Expensive)

Inverted Page Table Architecture

Shared Page

Re-Entrant Code(== Pure Code)

Read-Only로 하여 프로세스 간에 하나의 code만 메모리에 올림 ex) text editors, compilers, window systems

Shared Code는 모든 프로세스의 Logical Address Space에서 동일한 위치에 있어야 함

Private Code and Data

각 프로세스들은 독자적으로 메모리에 올림
Private Data는 Logical Address Space의 아무 곳에 와도 무방

Shared Pages Example

Segmentation

프로그램은 의미 단위인 여러 개의 Segment로 구성

작게는 프로그램을 구성하는 함수 하나 하나를 Segment로 정의
크게는 프로그램 전체를 하나의 Segment로 정의 가능
일반적으로는 Code, Data, Stack 부분이 하나씩 Segment로 정의됨

Segment는 다음과 같은 Logical Unit들임

main()
function
global variables
stack
symbol table, arrays

Segmentation Architecture

Logical Address는 다음의 두가지로 구성

Segment-Number
Offset

Segment Table

각 Table Entry는 다음을 가진다.

Base: Starting Physical Address of the segment
Limit: Length of the segment

Segment-Table Base Register(STBR)

물리적 메모리에서의 Segment Table의 위치

Segment-Table Length Register(STLR)

프로그램이 사용하는 segment의 수

Segment Number s is legal if s < STLR
아니면 trap 발생

Protection

각 segment 별로 Protection Bit가 있음
Each Entry

Valid bit = 0 → Illegal Segment
Read/Write/Execution 권한 bit

Sharing

Shared Segment
Same Segment Number
Segment는 의미 단위이기 때문에 공유(Sharing)와 보안(Protection)에 있어 Paging보다 훨씬 효과적이다. (Paging은 같은 크기로 자르기 때문에, 어떤 것들은 Write가 가능하고, Read만 가능하고 이런 식으로 나누기 애매함)

Allocation

First Fit / Best Fit
External Fragmentation 발생
Segment의 길이가 동일하지 않으므로, 가변 분할 방식에서와 동일한 문제점 발생

Segment Hardware

Example of Segmentation

Segmentation with Paging

Pure Segmentation과의 차이점

Segment-Table Entry가 Segment의 Base Address를 가지고 있는 것이 아니라 Segment를 구성하는 Page Table의 Base Address를 가지고 있음

장점

메모리에는 Page 단위로 올라가고

→ Allocation 문제가 발생하지 않음

의미 단위로 해야하는 Sharing, Protection은 Segment Table 레벨에서 함

출처

반효경 운영체제