1. Background
- 프로그램은 Disk에서 메모리로 올려져야 실행 가능
- CPU가 직접 접근할 수 있는 저장소는 Main memory와 Register 뿐
- Register 접근: 1 CPU clock cycle 이하
- Main memory 접근: 여러 cycle 소요
- Cache가 Main memory와 Register 사이에 위치하여 속도 격차를 완화
- Memory protection이 올바른 동작을 보장하기 위해 필요
2. 프로그램의 처리 단계
Source program → Compile time → Load time → Execution time(Run time)을 거쳐 메모리에서 실행된다.
3. Address Binding (주소 바인딩)
명령어와 데이터의 메모리 주소가 결정되는 시점에 따라 세 가지로 구분:
| 바인딩 시점 | 설명 | 특징 |
|---|---|---|
| Compile time | 컴파일 시 각 심볼의 절대 주소를 알아야 함 | Absolute code 생성. 시작 위치 변경 시 재컴파일 필요 |
| Load time | Loader가 절대 주소를 할당 | Relocatable code (상대 주소) 생성 |
| Execution time | 실행 중 프로세스가 메모리 내 위치를 이동할 수 있음 | CPU가 주소를 생성할 때마다 주소 매핑 필요. 하드웨어 지원 필수 (Base/Limit register, MMU) |
4. Logical vs Physical Address
| Logical Address | Physical Address | |
|---|---|---|
| 생성 | CPU가 생성 | Memory unit이 인식 |
| 별칭 | Virtual address | 실제 메모리 주소 |
| Compile/Load time binding | Logical = Physical (동일) | |
| Execution time binding | Logical != Physical (다름) |
5. MMU (Memory-Management Unit)
Virtual address → Physical address 변환을 수행하는 하드웨어 장치.
- Relocation register의 값을 CPU가 생성한 모든 주소에 더함
- 사용자 프로그램은 Logical address만 다루며, 실제 Physical address를 알지 못함
6. Base and Limit Register
- Base register (= Relocation register): 프로세스의 물리 주소 공간의 시작 주소
- Limit register: Logical address의 범위 (프로세스 크기)
동작:
- CPU가 Logical address 생성
- Limit register와 비교 → 초과하면 Trap (Addressing error)
- 범위 내이면 Relocation register 값을 더하여 Physical address 산출
7. Swapping
- 프로세스를 일시적으로 메모리에서 Backing store(빠른 디스크)로 내보내고, 나중에 다시 메모리로 불러옴
- Swap time의 대부분은 전송 시간(Transfer time) - Swap되는 메모리 양에 비례
- Swapping은 Dynamic relocation을 필요로 함
8. Contiguous Allocation (연속 할당)
Main memory를 두 영역으로 분할:
- Low memory: OS (Interrupt vector 포함)
- High memory: 사용자 프로세스
8.1 Hole
- Hole: 사용 가능한 메모리 블록
- 메모리 전체에 다양한 크기의 Hole이 산재
- 프로세스 도착 시 충분히 큰 Hole에서 할당
8.2 Dynamic Storage-Allocation Problem
빈 Hole 목록에서 크기 n의 요청을 어떻게 만족시킬 것인가:
| 전략 | 설명 | 특성 |
|---|---|---|
| First-fit | 충분히 큰 첫 번째 Hole에 할당 | 빠름 |
| Best-fit | 충분히 큰 것 중 가장 작은 Hole에 할당 | 전체 리스트 탐색 필요. 작은 잔여 Hole이 많이 생김 |
| Worst-fit | 가장 큰 Hole에 할당 | 전체 리스트 탐색 필요. 가장 큰 잔여 Hole 생성 |
First-fit과 Best-fit이 Worst-fit보다 저장소 활용률이 좋다.
8.3 Fragmentation (단편화)
| 유형 | 설명 |
|---|---|
| External fragmentation | 전체 빈 메모리는 충분하지만 연속적이지 않아 할당 불가 |
| Internal fragmentation | 할당된 메모리가 요청보다 약간 커서, 파티션 내부에 사용되지 않는 공간 발생 |
해결: Compaction - 메모리 내용을 재배치하여 모든 빈 공간을 하나로 합침. Dynamic relocation이 가능할 때만 수행 가능.
9. Paging
9.1 개념
Paging은 주소 공간이 비연속적(Non-contiguous)이어도 되는 방식이다.
- Physical memory를 고정 크기 블록으로 나눔 - Frame (크기: 2의 거듭제곱, 512B ~ 8MB)
- Logical memory를 같은 크기 블록으로 나눔 - Page
- 크기 n pages인 프로그램을 실행하려면 n개의 Free frame을 찾아 로드
- Page table이 Logical → Physical 주소 변환 수행
- Internal fragmentation은 있지만, External fragmentation 없음
9.2 주소 변환 (Address Translation)
CPU가 생성하는 주소는 두 부분으로 나뉜다:
| Page number (p) | Page offset (d) |
(m - n) bits n bits
- p: Page table의 Index - 해당 Page의 Physical memory Frame 기본 주소 조회
- d: Frame 기본 주소에 더해져 실제 Physical address 산출
- Logical address space = 2^m, Page size = 2
9.3 Paging 예제
4-byte page, 4-bit logical address 예제:
- Page number = 주소 / Page size (상위 2비트)
- Offset = 주소 % Page size (하위 2비트)
9.4 Free Frame 할당
- Free frame list에서 빈 Frame을 찾아 Page를 로드
- Page table에 매핑 기록
- Page가 연속적인 Frame에 있을 필요 없음 - 어떤 빈 Frame이든 사용 가능
10. Page Table 구현
10.1 기본 구현
- Page table은 Main memory에 저장
- PTBR (Page-Table Base Register): Page table의 시작 주소를 가리킴
- PTLR (Page-Table Length Register): Page table의 크기를 나타냄
문제: 모든 메모리 접근이 두 번의 메모리 접근을 필요로 함 - Page table 조회 1번 + 실제 데이터/명령어 접근 1번
10.2 TLB (Translation Look-aside Buffer)
TLB는 특수한 고속 하드웨어 Cache (Associative memory)로, Page table의 일부를 저장한다.
동작:
- CPU가 Logical address (p, d) 생성
- TLB에서 p를 병렬 검색 (Parallel search)
- TLB hit: TLB에서 Frame 번호를 즉시 가져옴 - 메모리 접근 1번
- TLB miss: Main memory의 Page table에서 Frame 번호 조회 - 메모리 접근 2번
Context switch 시 TLB flush - 이전 프로세스의 오래된 엔트리 제거. 일부 TLB는 ASID(Address-Space Identifier)를 저장하여 빈번한 Flush를 방지.
10.3 Effective Access Time (EAT)
- e = TLB lookup 시간
- b = Memory access 시간
- a = Hit ratio (TLB에서 찾을 확률)
EAT = (e + b) x a + (e + 2b) x (1 - a)
= e + (2 - a) x b
11. Memory Protection
11.1 Valid-Invalid Bit
Page table의 각 엔트리에 Protection bit를 연결:
| 비트 | 의미 |
|---|---|
| Valid (v) | 해당 Page가 프로세스의 Logical address space에 존재하는 합법적인 Page |
| Invalid (i) | 해당 Page에 대한 접근 불허 |
- PTLR을 사용하여 주소의 유효성을 검사할 수도 있음
12. Shared Pages
- Shared code: 여러 프로세스가 읽기 전용(Read-only, Re-entrant) 코드의 복사본 하나를 공유 (예: Editor, Compiler, Window system)
- 공유 코드는 모든 프로세스의 Logical address space에서 같은 위치에 나타나야 함 (Self-reference를 위해)
- Private code and data: 각 프로세스가 별도의 데이터 복사본 유지. Logical address space의 아무 곳에나 위치 가능