8. 메모리 관리
Logical vs. Physical Address
- Logical address (= virtual address)
프로세스마다 독립적으로 가지는 주소 공간, CPU가 보는 주소 - Physical address
메모리에 실제 올라가는 위치 - 주소 바인딩 (주소 결정)
Symbolic address → Logical address → Physical address
주소 바인딩 (Address Binding)
Logical address가 Physical address로 바뀌는 시점이 언제인지
- Compile time binding
실행파일을 만들 때 주소 결정
여러 프로그램이 multi-tasking 되는 환경에서는 비효율적
절대 코드 (absolute code) - Load time binding
프로그램이 실행 시작되는 시점에 주소 결정
재배치가능코드 (relocatable code) - Execution time binding (= Run time binding)
프로그램이 실행 시작되는 시점에 주소 결정, 실행중에도 메모리 상 위치를 옮길 수 있음
주소가 계속 변환되기 때문에 CPU가 주소를 참조할 때마다 binding 점검
하드웨어 지원이 필요
Memory-Management Unit (MMU)
logical address를 physical address로 매핑해 주는 하드웨어 디바이스
MMU scheme
- Relocation register (Base register): 프로그램의 시작 위치
- Limit register: 프로그램의 크기
CPU가 요청한 논리 주소가 Limit register보다 큰 경우(악의적인 시도) 차단
정상적인 접근인 경우 주소 변환(시작 위치 + 논리 주소)
User program - logical address 만을 다룬다
Dynamic Loading
해당 루틴이 불려질 때 프로세스를 메모리에 load
memory utilization 향상
운영체제의 지원 없이 프로그램 자체에서 구현 가능 (라이브러리를 통해 지원)
Dynamic Linking
Linking을 실행 시간까지 미루는 기법
- Static linking (Static Library)
라이브러리가 실행 파일 코드에 포함
동일한 라이브러리가 각각의 메모리에 올라오므로 메모리 낭비 - Dynamic linking (Shared library
라이브러리가 실행시 연결(linking)됨
이미 메모리에 있으면 그 주소로 가고 없으면 디스크에서 읽어옴
운영체제의 도움이 필요
Overlays
프로세스에서 실제 필요한 정보만 메모리에 올림
프로세스의 크기가 메모리보다 클 때 유용
운영체제의 지원 없이 사용자에 의해 구현 (초창기 시스템 - 수작업으로 구현)
Swapping
프로세스를 일시적으로 메모리에서 backing store(=swap area)로 쫓아냄
중기 스케줄러에 의해 swap out될 프로세스 결정 - CPU 우선순위 낮은 프로세스
Run time binding이 지원되어야 함
swap time은 대부분 transfer time이다
Allocation of Physical Memory
- Contiguous allocation (연속 할당)
- Noncontiguous allocation (불연속 할당)
Contiguous allocation (연속 할당)
외부 조각 (External framgmentation)
프로그램 크기보다 분할의 크기가 작은 경우
내부 조각 (Internal fragmentation)
프로그램 크기보다 분할의 크기가 큰 경우
- 고정 분할 방식 (Fixed partition)
물리적 메모리 영구적 분할(partition)
분할 크기가 고정적이므로 내부 조각 / 외부 조각이 생길 수 있음 - 공간 낭비 - 가변 분할 방식 (Variable partition)
프로그램의 크기를 고려해서 할당
프로그램이 종료되면 외부 조각이 생길 수 있음
Hole
가용 메모리 공간 - 여러 hole이 메모리 여러 곳에 흩어져 있음
운영체제는 할당 공간과 가용 공간(hole)에 대한 정보를 유지
- Dynamic Storage-Allocation Problem
가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole 찾기
- First-Fit - 최초로 찾은 size n 이상인 hole에 할당
- Best-fit - size n 이상인 가장 작은 hole을 찾아서 할당, 모든 리스트 탐색
- Worst-fit - 가장 큰 hole에 할당First-fit과 Best-fit이 Worst-fit보다 효율적 - Compaction
external fragmentation 문제 해결 방법
외부 조각을 하나로 모아서 큰 hole을 만드는 것
최소한의 메모리 이동으로 compaction - 매우 복잡한 문제
프로그램의 물리 주소가 동적으로 바뀌어야 하기 때문에 run time binding에서만 사용 가능
Noncontiguous allocation (불연속 할당)
- Paging
프로세스의 logical memory를 동일한 사이즈의 page 단위로 나누어서 저장
일부는 backing storage에, 일부는 physical memory에 저장
physical memory → frame, logical memory → page (frame과 같은 크기)
page table을 사용하여 주소 변환
외부 조각 발생 X, 내부 조각 발생 가능 - Page table
32bit 주소 체계 / page 크기 4K = 100만개 이상의 paging entry 필요
main memory에 상주
Page-table base register(PTBR) - page table 시작 위치 / Page-table length register(PTLR) - page table 크기
page table 접근 1번, 실제 data 접근 1번 → 2번의 memory access
Translation Look-aside Buffer(TLB) 고속의 캐시 메모리 - associative register(parallel search 가능한 하드웨어)를 통해 구성
Two-level Page Table
32 bit address 사용시 4G의 주소 공간
→ page size 4K 이면 1M개의 page table entry 필요
→ page entry 4B 이면 4M의 page table 필요
→ 일부만 사용되므로 공간 낭비가 심함
- page number: 20 bit
- page number: 10 bit → P1 (outer page table의 index)
- page offset: 10 bit → P2 (page of page table)
- page offset: 12 bit
Multilevel Paging and Performance
Address space 커지면 다단계 페이지 테이블 필요
각 단계 페이지 테이블이 존재 - 더 많은 메모리 접근 필요
TLB를 통해 메모리 접근 시간 줄일 수 있음
Memory Protection
Page table의 각 entry마다 아래의 bit 추가
- Protection bit
page에 대한 접근 권한 - Valid-invalid bit
valid - 해당 주소 frame에 프로세스를 구성하는 유효한 내용이 있음 (접근 허용)
invalid - 해당 주소 frame에 유효한 내용이 없음 (접근 불허)
프로세스가 그 주소 부분을 사용하지 않는 경우 / 해당 페이지가 메모리에 있지 않고 swap area에 있는 경우
Inverted Page Table
모든 프로세스 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재 → page table 매우 커짐
Inverted page table (역방향)
- Page frame 하나 당 page table에 하나의 entry를 둔 것
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, logical address)
- 테이블 전체를 탐색해야 하는 단점 → associative register 사용
Shared Page
동일한 프로그램이 여러 프로세스에 의해 실행되면 동일한 코드가 각 메모리에 중복으로 올라가게 됨
Shared code = Re-entrant code = Pure code
- read-only로 하여 하나의 코드만 메모리에 올림
- 모든 프로세스의 logical address space에서 동일한 위치 (같은 page 번호)
Segment
프로그램을 의미 단위인 여러개의 segment로 나눔
일반적으로 code, data, stack 부분이 하나의 segment
<segment-number, offset>
- Segment table
- base - segment 시작 주소
- limit - segment 길이
- Segment-table base register (STBR) - segment table 시작 주소
- Segment-table length register (STLR) - segment table 수(길이)
Segmentation Architecture
- Protection - 각 segment 별로 protection bit
- Sharing - shared segment, same segment number
- Allocation - first fit / best fit, external fragmentation 발생
Segment는 의미 단위이기 때문에 공유와 보안에 있어 paging 보다 효과적
Segment 길이가 제각각이므로 가변 분할 방식에서의 문제점 발생
Segmentation with Paging
한 segment 여러 개의 page로 구성 → page 단위로 메모리에 올림
segment-table entry가 segment를 구성하는 page table의 base address를 가지고 있음
공유/보안 segment 차원에서 관리, 할당 문제 없음
