1. Memory background
- 메모리는 현대 컴퓨터의 핵심 자원
- CPU가 직접 접근 가능한 유일한 저장소는 Main memory, Registers
- Register 접근은 한 개 이하의 CPU clock cycle
- Main memory 접근은 여러 cycle -> memory stall
- 프로그램은 실행 전에 디스크에서 메모리로 로드되어야 함
- Cache: CPU와 주기억장치에 위치하여, hardware에 의해 조절됨
2. Memory Space
- 논리 주소(Logical Address): CPU가 생성한 주소 (가상 주소)
- 물리 주소(Physical Address): 실제 메모리 장치에서 사용하는 주소
- 주소 바인딩
- 컴파일/로드 시: 논리 주소 = 물리 주소
- 실행 시: 논리 주소 ≠ 물리 주소 → MMU가 변환 수행
- 메모리 관리 장치(MMU)가 실행 시간에 논리 주소를 물리 주소로 변환
3. Contiguous Allocation(연속 할당)
- Main Memory를 운영체제 + 사용자 프로세스 모두를 지원
- Resident OS: 낮은 주소 영역 (Interrupt vector 포함)
- User Processes: 높은 주소 영역, 각각이 하나의 연속적인 메모리 구역에 할당
- Reloction Register를 사용하여 사용자의 프로세스 간 보호
- Base Register + Limit Register → 접근 제어
가변 파티션 & 동적 할당
- Variable Partition Scheme(가변 파티션): 크기가 다른 홀(Hole)에 프로세스 할당
- Hole: 사용 가능한 메모리 블록
- 동적 할당 알고리즘: 크기 n개의 요청을 여러 holes 중에서 어떻게 만족시킬 것인가?
- First-fit: 처음으로 충분한 공간
- Best-fit: 가장 적절한 작은 공간 → 남는 공간 최소
- Worst-fit: 가장 큰 공간 → 남는 공간 최대
→ 일반적으로 First/Best-fit > Worst-fit
4. Fragmentation
- 외부 단편화: 충분한 메모리가 있지만 연속적이지 않아 할당 불가
- 내부 단편화: 요청보다 큰 메모리 블록이 할당되어 일부가 낭비됨
- 해결법:
- 압축(compaction): 메모리 재배열 필요
- logical address space를 비연속으로 허용 → Paging 으로 해결
5. Paging
- Physical address space는 연속적일 필요 없음, 외부 단편화는 해결 가능
- 페이지(Page) & 프레임(Frame): 고정 크기 단위 (보통 2의 거듭제곱)
- physical memory를 고정 크기 블록(Frame) 으로 분할
- logical memory를 동일한 크기의 페이지(Page) 로 분할
→ 프로세스 실행 시에, pages를 frame에 로드
- page table: 논리 주소를 물리 주소로 변환
- 논리 주소 = page number(p) + page offset(d) 구조
MMU 변환 절차
- p 추출 → 페이지 테이블에서 프레임 번호 f 조회
- 논리 주소의 p를 f로 바꿔서 최종 물리 주소 생성
- (ex) 6비트 논리 주소에 4바이트 페이지 크기가 사용된다면, 주소는 상위 4비트는 페이지 번호, 하위 2비트는 오프셋으로 구성
6. Page Table Implementation
- 페이지 테이블은 주기억장치에 저장
- PTBR(Page Table Base Register): 페이지 테이블 시작 주소
- PTLR(Page Table Length Register): 페이지 테이블 크기
- 모든 접근 시 메모리를 2번 조회 (페이지 테이블 + 실제 데이터)
7. TLB (Translation Look-Aside Buffer)
- 주소 변환을 빠르게 하기 위한 고속 하드웨어 캐시
- 보통 64~1024개 항목, 연관 메모리(associative memory)라고도 불림
- TLB 미스 시 페이지 테이블에서 가져와 TLB에 저장
- ASID(Address Space Identifier) 를 저장하면
- 각 프로세스를 구분하여 address-space protection
- 그렇지 않으면, 모든 context switch마다 flush 필요(TLB를 비워야 함)
Address translation(p,d)
- p가 TLB에 있으면 → 즉시 프레임 번호(frame #) 반환
- 없으면 → 메모리의 페이지 테이블 조회
8. Memory Protection
- 각 프레임마다 Protection bit를 설정하여 read-only/read-write/execute-only 등 제어
- 유효(valid) / 무효(invalid) 비트:
- valid: 이 페이지가 프로세스의 논리 주소 공간에 있음
- invalid: 해당 페이지는 현재 프로세스가 사용할 수 없음
- 또는 PTLR(Page Table Length Register) 를 사용
- 위반 시 커널로 trap 발생
9. Page Table Structure
- 32비트 주소 + 4KB 페이지 크기 → 페이지 테이블 항목 약 100만 개 (2²⁰)
- 항목당 4바이트면 → 프로세스당 4MB 소비
→ 연속 할당은 비효율적
- 항목당 4바이트면 → 프로세스당 4MB 소비
- 개선 기법:
- 계층적 페이징 (Hierarchical)
- 해시 기반 테이블 (Hashed Page Table)
- 역방향 페이지 테이블 (Inverted Page Table)
Hierarchical Page Tables
-
logical address space → 여러 page table로 분할 → page table도 page 단위로 분할
Two-level Paging
ex) 32bit & 4K page size → p1 (10비트) | p2 (10비트) | offset d (12비트)
- p1 → 외부 페이지 테이블 인덱스
- p2 → 내부 페이지 테이블 인덱스
-
메모리 절약, 관리 효율 증가
-
순서: p1을 사용하여 외부 페이지 테이블 접근 → 해당 항목에서 내부 페이지 테이블의 주소 획득 → p2로 내부 테이블 접근 → 프레임 번호 추출 → 오프셋 d와 결합하여 물리 주소 결정
Hashed Page Table
- Virtual page number를 hash하여 page table에 매핑
- 동일 해시값끼리는 체인 형태로 연결
- 항목: virtual page number, 매핑된 프레임 값, 다음 항목을 가리키는 pointer
Inverted Page Table
- 모든 logical pages가 아닌, 모든 physical pages(frames)를 추적
- 항목: 가상 주소, 소유 프로세스 정보
→ 메모리 사용 감소, 하지만 탐색 시간 증가
10. Swapping
- 프로세스를 일시적으로 backing store로 이동시켰다가 다시 메모리로 복귀
- 전체 프로세스 메모리 공간이 물리 메모리를 초과할 수 있음
- Standard swapping: 전체 프로세스 단위로 main memory <-> backing store 이동
→ context switching 시간 증가 - 현대 시스템(Linux, Windows 등): 페이지 단위로 swapping 가능
Swapping with Paging
- Page-out: Memory → backing store
- Page-in: backing store → Memory
