07. Memory Management

CS/운영체제

07. Memory Management

호프 2023. 11. 25. 00:16

Memory Address

Logical Address (= virtual address)

프로세스마다 독립적으로 가지고 있는 주소 공간
각 프로세스마다 0번지로부터 시작
CPU가 보는 주소는 logical address

Physical Address

메모리에 실제로 올라가는 위치
DRAM에서의 변하지 않는 실제 주소

Symbolic Address

프로그래머가 사용하는 변수나 레이블과 같은 기호적인 이름으로 표시된 주소

Address Binding

Address Binding

Symbolic Address -> Logical Address -> Physical Address

(1) Compile Time Binding

컴파일 시 정적으로 물리적 주소가 결정됨
프로그램의 시작 위치를 변경하려면 전체 프로그램을 재컴파일해야 함
컴파일러는 절대 코드 (absolute code) 생성: 프로그램이 메모리에 로드되면 주소가 변경되지 않음

프로그램의 시작 위치 == 프로그램이 메모리에 로드될 때, 해당 프로그램이 상주하는 메모리 영역의 시작 주소

(2) Load Time Binding

Loader가 물리적 주소 부여: 프로그램이 메모리에 로드될 때, loader가 물리적 주소를 부여
컴파일러가 재배치가능한 코드 (relocatable code)를 생성한 경우 가능: 프로그램의 시작 위치를 변경하더라도, 컴파일된 코드를 수정하지 않고도 로더가 물리적 주소를 조정할 수 있음

(3) Execution Time Binding (= Run Time Binding)

프로그램이 실행된 이후에도 프로세스의 메모리 상 위치를 옮길 수 있음
CPU가 주소를 참조할 때마다 binding을 점검 (address mapping table): CPU가 주소를 참조할 때마다 주소 매핑 테이블을 검사하여 실제 메모리 주소로 변환
하드웨어적인 지원이 필요 (e.g. MMU)

MMU: Memory-Management Unit

logical address를 physical address로 매핑해주는 Hardware device
사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register (= relocation register)의 값을 더한다.
- context switch가 발생하면 MMU의 base register 값도 바뀐다.
사용자 프로그램은 logcal address만을 다루며 physical address를 알 수 없고 알 필요도 없다.

Base register(= Relocatioin register): 접근할 수 있는 물리적 메모리 주소의 최솟값
Limit register: 논리적 주소의 범위
- if logical address > limit register: trap (addressing error) 발생

Terminologies

Dynamic Loading

프로세스 전체를 메모리에 미리 다 올리는 것이 아니라 해당 루틴이 불려질 때 메모리에 load하는 것
memory utilization 향상
가끔식 사용되는 많은 양의 코드의 경우 유용 - ex. 오류 처리 루틴
운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능

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

Dynamic Linking

라이브러리가 실행 시 연결 (link) 됨
라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둔다.
라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어 온다.
운영체제의 도움이 필요함

Static Linking

라이브러리가 프로그램의 실행 파일 코드에 포함되므로 실행 파일의 크기가 커진다.

동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비 발생

컴파일(Compilation): 소스 코드를 컴파일하여 오브젝트 파일 생성.

링킹(Linking): 여러 오브젝트 파일을 하나의 실행 파일로 결합.

로딩(Loading): 실행 파일을 메모리에 로드하여 초기화 및 실행.

Overlays

프로그램이 실행되는 동안에 필요한 부분만 메모리에 로드하는 방법
메모리 제약으로 인해 프로세스의 전체 크기를 한 번에 메모리에 올릴 수 없을 때 사용되는 메모리 관리 기술 중 하나
운영체제의 지원 없이 사용자에 의해 구현

Dynamic Loading(동적 로딩): 실행 중에 필요한 모듈이나 라이브러리를 동적으로 로드하는 것. 필요한 부분을 메모리에 로드하고 사용하는 것이지만, Overlays처럼 수작업으로 구현하는 것이 아니라 운영체제가 지원합니다.

Overlays: 프로세스의 크기가 메모리보다 클 때, 프로그래머가 직접 부분적으로 메모리를 관리하는 방법.

Swapping

프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
Backing store (= swap area): 디스크, 충분히 빠르고 큰 저장 공간
Swap in / Swap out
- 일반적으로 중기 스케줄러 (swapper)에 의해 swap out 시킬 프로세스 선정
- priority-based CPU scheduling algorithm: priority가 낮은 프로세스를 swap out 시키고 높은 프로세스를 메모리에 올림
- Compile time 혹은 Load time binding에서는 원래 메모리 위치로 swap in 해야 함
- Execution time binding에서는 추후 빈 메모리 영역 아무 곳에나 올릴 수 있음
- swap time은 대부분 trasfer time (swap되는 양에 비례하는 시간)이다.

Allocation of Physical Memory

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

OS 상주 영역: interrupt vector와 함께 낮은 주소 영역 사용
사용자 프로세스 영역: 높은 주소 영역 사용

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

Contiguous allocation: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 방법
- Fixed partition allocation / Variable partition allocation
Noncontiguous allocation: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라가는 것
- Paging / Segmentation / Paged Segmentation

Contiguous Allocation

Fixed partition allocation

물리적 메모리를 몇 개의 영구적 분할 (partition)으로 나누고 partition당 하나의 프로그램 적재
partition의 크기가 모두 동일한 방식 vs 서로 다른 방식
융통성이 없다: 동시에 메모리에 load되는 프로그램 수 고정, 최대 수행 가능 프로그램 크기 제한
Internal fragmentation, External fragmentation 발생

Variable partition allocation

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

External fragmentation: 프로그램 크기보다 partition 크기가 작은 경우 발생하는 외부 조각

아무 프로그램에도 배정되지 않은 빈 곳인데 프로그램이 올라갈 수 없는 작은 partition

Internal fragmentation: 프로그램 크기보다 parition 크기가 큰 경우 발생하는 내부 조각

하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각
특정 프로그램에 배정되었지만 사용되지 않는 공간

Hole: 가용 메모리 공간

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

Dynamic Storage-Allocation Problem

Variable partition allocation 방식에서 size n 인 요청을 만족하는 가장 적절한 hole을 찾는 문제
(1) First-fit: 최초로 찾아지는 hole에 할당
(2) Best-fit: Size n 이상인 가장 작은 hole을 찾아서 할당, 정렬되지 않은 경우 모든 hole 탐색해야 함, 많은 수의 아주 작은 hole들이 생성
(3) Worst-fit: 가장 큰 hole에 할당, 정렬되지 않은 경우 모든 리스트 탐색해야 함, 상대적으로 아주 큰 hole들이 생성됨
- (1), (2)번이 (3)번보다 속도와 공간 이용률 측면에서 효과적

Compaction

external fragmentation 문제를 해결하는 방법 중 하나로 사용 중인 메모리 영역을 한 군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block을 만드는 것
매우 비용이 많이 드는 방법 - 최소한의 메모리 이동으로 compaction하는 방법을 찾는 것은 매우 복잡한 문제
Compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다. - Execution time binding

Paging

Paging

프로세스의 logical memory (virtual memory)를 동일한 사이즈의 page 단위로 나누고 noncontiguous하게 저장
일부는 backing storage에, 일부는 physical memory에 저장한다.
physical memory를 동일한 크기의 frame으로 나눔
logical memory를 frame과 동일한 크기의 page로 나눔
page table을 사용하여 Logical address를 physical address로 변환
External fragmentation & Internal fragmentation 발생 X

CPU는 다음 두 가지로 구성된 virtual address를 사용한다.

Page number (p): page table의 index로 사용, 해당 index에는 그 페이지의 물리적 메모리 상의 base address가 저장됨
Page offset (d): base address와 더해져서 physical address가 구해짐

Implementation of Page Table

page table은 main memory에 상주
PTBR(Page-table base register)가 page table을 가리킴
PTLR(Page-table length register)가 테이블 크기를 저장
모든 메모리 접근 연산에는 2번의 memory access 필요: page table 접근 -> 실제 data/instruction 접근
속도 향상을 위해 associative register 혹은 translation look-aside buffer (TLB)라 불리는 고속의 lookup hardware cache 사용

Asssociative Register (TLB)

parallel search 가능
Addres translatioin
- page table 중 일부가 TLB에 저장되어 있음
- 해당 page #가 TLB에 있는 경우 바로 frame #를 얻을 수 있고, 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
- TLB는 context switch 발생하면 flush

Effective Access Time

Associative register lookup time = t
memory cycle time = 1
Hit ratio: associative register에서 찾아지는 비율: a
Effective Access Time (EAT) = (1 + t)a + (2 + t)(1 - a) = 2 + t - a

Two-Level Page Table

Two-Level Page Table

프로그램이 사용하는 주소 공간이 매우 큰 경우, 해당 프로그램의 페이지 테이블도 매우 커짐 -> But, 대부분의 프로그램은 주소 공간 중 일부분만 사용하므로 메모리 낭비 발생

👉 Page table 자체를 page로 구성

👉 사용되지 않는 주소 공간에 대한 Outer page table의 엔트리 값은 NULL (대응하는 inner page table 없음)

Multilevel Paging and Performance

Address space가 커지면 multilevel table 필요 -> 더 많은 메모리 접근 필요
캐쉬 메모리를 통해 메모리 접근 시간을 줄일 수 있다.

Memory Protection

Page table의 각 entry마다
- Protection bit: page에 대한 접근 권한 (read / write / read-only)
- Valid-invalid bit: valid(1)=해당 주소의 frame에 해당 페이지가 있음 (접근 허용), invalid(0)

Inverted Page Table

일반적인 페이지 테이블은 가상 주소를 물리 주소로 변환하는데 사용되는 매핑 정보를 저장하는데 비해, Inverted page table은 물리 주소를 가상 주소로 변환하는데 사용
역페이지 테이블은 물리 메모리 프레임을 인덱스로 사용하여 구성, 각 엔트리는 물리 메모리 프레임에 대한 정보를 저장
공간 효율성: 일반적인 페이지 테이블은 가상 주소 공간의 크기에 따라 크기가 결정되지만, 역페이지 테이블은 물리 메모리 프레임의 개수에 따라 크기가 결정되므로 더 효율적입니다.
빠른 검색: 역페이지 테이블에서는 물리 주소가 인덱스로 사용되므로 특정 물리 메모리 프레임에 대한 가상 주소 매핑 정보를 빠르게 찾을 수 있습니다.
단점: 테이블 전체를 탐색해야 함

Shared Page

Shared Code: Re-entrant Code (= Pure code)
- read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (물리적 메모리에 하나의 코드만 존재)
- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무 곳에 와도 무방

Segmentation

Segment

프로그램은 의미 단위인 여러 개의 segment로 구성 (= logical unit)
작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의, 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨

Segmentation Architecture

Logical address: <segment-number, offset>
Segment table: each table entry has
- 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 & offset d is legal if d < limit
Protection: 각 세그먼트 별로 protection bit 존재
- Valid bit: 1 == valid (legal) <-> 0 == invalid (illegal)
- read / write / execution 권한 bit
Sharing: shared segments have same segment number
- segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 더욱 효과적이다.
Allocation
- first-bit, best-bit
- external fragmentation 발생
- segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점 발생

Segmentation with Paging

segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음 == segment를 page로 나눈다.
fragmentation이 줄어든다는 장점, 로직이 복잡해진다는 단점

저작자표시 (새창열림)