배경지식
프로그램은 실행되기 위해 disk에서 memory로 로드되어 프로세스 내에 배치되어야 한다.
CPU가 직접 접근할 수 있는 저장소는 main memory와 registers뿐이며, memory unit은 주소와 read 요청, 또는 주소와 데이터 및 write 요청의 스트림만을 인식한다.
성능 특성은 다음과 같다:
- Register access: 1 CPU clock 이하의 시간
- Main memory access: 여러 사이클이 소요되어 stall을 유발
- Cache: main memory와 CPU registers 사이에 위치하여 성능 향상
올바른 동작을 위해서는 memory protection이 필요하다.
Base and Limit Registers
Base register와 limit register의 쌍이 logical address space를 정의한다.
CPU는 user mode에서 생성되는 모든 memory access가 해당 사용자의 base와 limit 사이에 있는지 확인해야 한다.
작동 방식:
- Base register: 프로세스의 시작 주소를 저장
- Limit register: 프로세스가 사용할 수 있는 메모리 크기를 저장
- 접근하려는 주소가 범위를 벗어나면 trap: addressing error 발생
각 프로세스의 base/limit register 값은 PCB(Process Control Block)에 저장되며, context switch시 교체된다.
Hardware Address Protection
Address Binding
프로그램의 주소는 여러 단계에서 다양한 형태로 표현된다:
주소 형태의 변화:
- Source code: 심볼릭 주소 (변수명, 상수 등)
- Compiled code: relocatable 주소 ("모듈 시작부터 14바이트")
- Linked code: absolute 주소 (예: 74014)
Address Binding의 3가지 시점
1. Compile Time Binding
- 메모리 위치가 컴파일 시점에 알려진 경우
- Absolute code 생성
- 시작 위치 변경 시 재컴파일 필요
2. Load Time Binding
- 컴파일 시점에 메모리 위치를 모르는 경우
- Relocatable code 생성
3. Execution Time Binding
- 실행 중 프로세스가 다른 메모리 세그먼트로 이동 가능한 경우
- Hardware support 필요 (base/limit registers)
Multistep Processing of User Program
프로그램 처리 과정은 다음과 같다:
- Source Program → Compiler/Assembler (compile time)
- Object Module → Linkage Editor (load time)
- Load Module → Loader (execution time)
- In-memory Binary Memory Image
각 단계에서 dynamic linking을 통해 system library와 연결될 수 있다.
Logical vs Physical Address Space
Logical Address (Virtual Address)
- CPU에 의해 생성되는 주소
- 프로그램이 참조하는 논리적 주소 공간
Physical Address
- Memory unit이 실제로 보는 주소
- 물리적 메모리의 실제 위치
주소 공간의 관계:
- Compile-time/Load-time binding: logical address = physical address
- Execution-time binding: logical address ≠ physical address
Memory-Management Unit (MMU)
MMU는 runtime에 virtual address를 physical address로 매핑하는 hardware device이다.
Simple MMU Scheme:
- Relocation register 값을 user process가 생성한 모든 주소에 더함
- Physical address = logical address + relocation register
- 사용자 프로그램은 logical address만 다루며, 실제 physical address는 보지 않음
Dynamic Relocation using a Relocation Register
- routine(루틴)은 호출될 때까지 메모리에 로드되지 않는다.
- 사용되지 않는 routine은 로드되지 않으므로, memory-space utilization(메모리 공간 활용도)이 향상된다.
- 모든 routine은 disk에 relocatable load format(재배치 가능한 로드 포맷)으로 저장된다.
- infrequently occurring cases(드물게 발생하는 상황) 처리를 위해 대량의 코드가 필요할 때 유용하다.
- 특별한 operating system(OS)의 지원 없이 프로그램 설계만으로 구현 가능하다.
- OS가 동적 로딩(dynamic loading) 구현을 위한 라이브러리(library) 제공 가능하다.
Dynamic Linking
- Static linking(정적 연결)
- loader(로더)가 system libraries(시스템 라이브러리)와 program code(프로그램 코드)를 결합하여 binary program image(이진 프로그램 이미지)를 생성한다.
- Dynamic linking(동적 연결)
- linking(연결)이 실행 시간까지 연기된다.
- stub(스텁)이라는 작은 코드 조각이 메모리 상의 적절한 library routine(라이브러리 루틴) 위치를 찾는다.
- stub은 자신을 routine의 주소로 대체하고 routine을 실행한다.
- OS는 routine이 process의 memory address(메모리 주소)에 있는지 확인한다.
- routine이 address space(주소 공간)에 없으면 추가한다.
- dynamic linking은 library에 특히 유용하며, shared libraries(공유 라이브러리)라고도 한다.
- 시스템 라이브러리 패치(patching) 시 적용 가능성 고려, versioning(버전 관리) 필요할 수 있다.
Swapping
- process(프로세스)는 일시적으로 memory에서 backing store(백업 저장소, 빠른 디스크)로 swap out(스왑 아웃)되고, 다시 memory로 swap in(스왑 인)되어 실행을 계속한다.
- 전체 process의 physical memory space(물리 메모리 공간) 합이 실제 physical memory(물리 메모리)를 초과할 수 있다.
- backing store는 모든 사용자의 memory image(메모리 이미지) 복사본을 저장할 수 있을 만큼 크고, 직접 접근이 가능해야 한다.
- roll out, roll in은 priority-based scheduling(우선순위 기반 스케줄링)에서 저우선순위 프로세스를 swap out하여 고우선순위 프로세스를 실행하는 방식이다.
- swap time(스왑 시간)의 대부분은 transfer time(전송 시간)이며, 전송 시간은 스왑되는 메모리 크기에 비례한다.
- 시스템은 디스크에 메모리 이미지를 가진 ready-to-run process(실행 준비 프로세스) queue를 유지한다.
Swapping의 추가 고려사항
- swap out된 process가 동일한 physical address(물리 주소)로 swap in되어야 하는지는 address binding method(주소 바인딩 방식)에 따라 다르다.
- process memory space에서 pending I/O(대기 중인 입출력)가 있는 경우 고려 필요하다.
- UNIX, Linux, Windows 등에서는 modified swapping(수정된 스와핑) 사용, threshold(임계값) 초과 시에만 swapping 활성화, 임계값 이하로 감소하면 비활성화된다.
Context Switch Time including Swapping
- CPU에 올릴 다음 process가 memory에 없으면, 다른 process를 swap out하고 target process를 swap in해야 한다.
- context switch time(문맥 전환 시간)이 매우 길어질 수 있다.
- 예: 100MB process를 50MB/sec 속도로 하드디스크에 swap out하면 2000ms, swap in까지 총 4000ms(4초) 소요.
- 실제 사용 중인 memory만 swap하면 시간을 줄일 수 있다.
- request_memory(), release_memory() 시스템 콜로 OS에 메모리 사용량을 알릴 수 있다.
Swapping 과정에서의 추가 제약 사항
swapping(스와핑)에는 단순한 메모리 이동 외에도 여러 제약 조건이 존재한다.
- pending I/O(대기 중인 입출력) 작업이 있는 경우, 해당 프로세스를 swap out(스왑 아웃)할 수 없다.
- 이유: I/O 작업이 잘못된 프로세스의 메모리 공간에 접근할 위험이 있기 때문이다.
이를 해결하기 위한 방법으로, 모든 I/O를 kernel space(커널 공간)로 먼저 전송한 뒤 I/O device(입출력 장치)로 전달하는 double buffering(이중 버퍼링) 기법이 있다.
- double buffering은 시스템 오버헤드(overhead)를 증가시킨다.
- 표준 swapping(standard swapping)은 현대 운영체제에서는 거의 사용되지 않는다.
- 대신, free memory(여유 메모리)가 극히 부족할 때에만 동작하는 수정된 방식(modified version)이 일반적으로 사용된다.
Swapping on Mobile Systems
- mobile system(모바일 시스템)에서는 일반적으로 swapping을 지원하지 않는다.
- flash memory(플래시 메모리)는 공간이 적고, write cycle(쓰기 횟수)이 제한되어 있으며, CPU와의 throughput(처리량)이 낮다.
- iOS는 app에 자발적 메모리 반환을 요청하며, read-only data는 필요 시 재로딩한다.
- Android는 free memory(여유 메모리)가 부족하면 app을 종료하지만, 먼저 application state(앱 상태)를 flash에 저장해 fast restart(빠른 재시작)를 지원한다.
- 두 OS 모두 paging(페이징) 기법을 지원한다.
Contiguous Allocation
연속 할당은 초기 메모리 할당 방법 중 하나이다:
메모리 분할:
- Low memory: Resident OS (interrupt vector 포함)
- High memory: User processes
- 각 프로세스는 single contiguous section에 배치
보호 메커니즘:
- Base register: 가장 작은 physical address 값 저장
- Limit register: logical address 범위 저장
- MMU가 logical address를 동적으로 매핑
이러한 메모리 관리 기법들은 process isolation, memory protection, efficient resource utilization을 보장하여 안정적인 multiprogramming 환경을 제공한다.
Hardware Support for Relocation
Multiple-partition allocation
- 메모리를 여러 파티션으로 분할하여 관리하는 방식이다.
- Degree of multiprogramming은 파티션의 수에 의해 제한되며, 프로세스의 필요에 따라 가변적인 크기의 파티션(variable-partition sizes)을 할당한다.
- 메모리 전체에 scattered된 다양한 크기의 hole(사용 가능한 메모리 블록)을 활용하여 프로세스가 도착하면 충분히 큰 hole을 할당한다.
- 프로세스 종료 시 해당 파티션을 해제하고 인접한 free 파티션을 병합한다.
- 운영체제는 allocated partitions과 free partitions 정보를 지속적으로 관리한다.
Dynamic Storage-Allocation 문제
크기 n의 메모리 요청을 처리하기 위한 전략은 다음과 같다:
- First-fit: 요청 크기 이상의 첫 번째 hole 선택
- Best-fit: 요청을 수용할 수 있는 가장 작은 hole 선택 → 가장 작은 잔여 홀 생성
- Worst-fit: 가장 큰 hole 선택 → 가장 큰 잔여 홀 생성 일반적으로 first-fit과 best-fit이 worst-fit보다 속도와 메모리 활용 효율성이 우수하다.
Fragmentation(단편화)
Fragmentation(단편화)란 운영체제에서 메모리를 할당하고 해제하는 과정에서, 사용 가능한 메모리 공간이 여러 개의 작은 조각들로 나뉘어져 효율적으로 사용할 수 없는 현상을 말합니다.
External Fragmentation(외부 단편화)
- 총 메모리 공간은 요청을 충족시킬 수 있지만 non-contiguous(비연속적)로 분포된 상태
- First fit(최초 적합) 방식 분석 시 N개 블록 할당 시 0.5N 블록이 fragmentation으로 손실
- 50% 규칙: 사용 가능 메모리의 1/3이 실제로 활용 불가능할 수 있음
Internal Fragmentation(내부 단편화)
- 프로세스가 필요로 하는 메모리보다 더 큰 블록이 할당되어, 남는 공간이 생기고 이 공간이 낭비되는 현상입니다.
- 할당된 메모리가 요청된 크기보다 약간 큰 경우 발생
- 예시: 4KB 블록이 할당됐지만 실제로는 1KB만 사용하면, 3KB가 낭비됨
- partition(파티션) 내부에서 사용되지 않는 메모리 공간
Compaction
Compaction(압축): 메모리 내용 재배치하여 free memory(여유 공간)를 하나의 큰 블록으로 통합
- 동적 재배치(dynamic relocation)가 가능한 시스템에서만 실행 시간에 수행
- I/O 문제 해결을 위해:
- I/O 작업 중인 프로세스 메모리 고정
- 모든 I/O를 OS buffers(운영체제 버퍼)를 통해 처리
- backing store(백업 저장소)도 동일한 단편화 문제 발생 가능
Segmentation(세그멘테이션)
Segmentation(세그멘테이션)은 운영체제에서 메모리 관리 기법 중 하나로, 프로세스의 메모리를 의미론적(논리적) 단위인 세그먼트(segment)로 나누어 관리하는 방법입니다
- 사용자 관점의 메모리 관리를 지원하는 기법
- 프로그램을 logical unit(논리적 단위)의 세그먼트 집합으로 구성
- 예: main program, procedure, stack, symbol table 등
Segmentation Architecture
- 논리 주소: <segment-number(세그먼트 번호), offset(오프셋)> 형식의 2-tuple
- 세그먼트 테이블 구조:
- base: 물리 메모리 시작 주소
- limit: 세그먼트 길이
사용되는 레지스터
- STBR(Segment-table base register): 세그먼트 테이블 위치 저장
- STLR(Segment-table length register): 프로그램이 사용하는 세그먼트 수 지정
하드웨어 지원
- 세그먼트 번호가 STLR 값보다 작은지 검증
- 물리 주소 = base + offset (offset < limit 확인 필수)
Paging(페이징)
- 물리 메모리를 frame(프레임)이라는 고정 크기 블록으로 분할
- 논리 메모리를 page(페이지)라는 동일 크기 블록으로 분할
- page table(페이지 테이블)을 통해 논리 주소 → 물리 주소 변환
주소 변환 방식
- CPU 생성 주소 = page number(p) + page offset(d)
- p: 페이지 테이블 인덱스 (base 주소 추출)
- d: base 주소와 결합하여 물리 주소 생성
- 예시: 32-byte 메모리에서 4-byte 페이지 사용 시 8개 페이지 생성
- 32 = 2^5 -> m = 5
- 4 = 2^2 -> n = 2
- m-n = 3 -> 2^3 = 8 개 페이지 생성
논리 주소에서 물리 주소로의 변환 과정
CPU가 생성하는 logical address(논리 주소)는 두 부분으로 구성된다:
- page number(p): 논리 주소의 상위 비트, 해당 주소가 속한 페이지 번호
- page offset(d): 페이지 내에서의 오프셋(offset), 하위 비트
page number(p)는 page table(페이지 테이블)의 인덱스로 사용된다.
- page table은 각 페이지가 물리 메모리의 어느 frame(프레임)에 위치하는지 저장한다.
- page table entry에는 해당 페이지의 frame number(f)(프레임 번호, base address)가 저장되어 있다.
변환 과정:
- CPU가 논리 주소(p, d)를 생성한다.
- page number(p)를 page table의 인덱스로 사용하여 frame number(f)를 찾는다.
- frame number(f)와 offset(d)를 결합하여 physical address(물리 주소)를 생성한다.
- 물리 주소 = (frame number × frame size) + offset
페이징 매핑 예시
- 위 그림처럼, 논리 메모리의 각 페이지(page 0, page 1, ...)는 page table을 통해 물리 메모리의 임의의 프레임(frame 0, frame 1, ...)에 매핑된다.
- 예를 들어, page 0은 frame 1에, page 1은 frame 4에, page 2는 frame 3에, page 3은 frame 7에 저장될 수 있다.
- 이 구조 덕분에 논리 메모리와 물리 메모리의 연속성이 필요 없으며, 외부 단편화(external fragmentation)를 방지할 수 있다.
- 오른쪽 예시에서는 논리 주소 <1,2>(page 1, offset 2)가 page table을 통해 frame 4로 매핑되고, 물리 주소는 frame 4의 시작 주소 + 2가 된다.
Paging의 Internal fragmentation 문제
Free Frames(여유 프레임) 관리
- 메모리는 여러 개의 frame(프레임)으로 나뉘며, 각 프레임은 동일한 크기를 가진다.
- 프로세스가 실행되기 위해 필요한 page(페이지) 수만큼 free frame을 할당받는다.
- 할당 전에는 free-frame list에 모든 빈 프레임이 나열되어 있고, 할당 후에는 프로세스의 각 페이지가 프레임에 매핑된다.
- 예시 그림에서, new process의 page 0, page 1, page 2, page 3이 free frame에 각각 할당되는 과정을 볼 수 있다.
Implementation of Page Table(페이지 테이블 구현)
- page table(페이지 테이블)은 main memory(주기억장치)에 저장된다.
- Page-table base register (PTBR): 페이지 테이블의 시작 주소를 저장
- Page-table length register (PTLR): 페이지 테이블의 크기(엔트리 개수)를 저장
- 데이터/명령어 접근 시 두 번의 메모리 접근이 필요하다:
- page table 접근(프레임 번호 획득)
- 실제 데이터/명령어 접근
이중 접근 문제는 associative memory(연관 메모리) 또는 translation look-aside buffer(TLB)라는 고속 캐시를 사용해 해결할 수 있다.
TLB와 Address-space Identifiers(ASID)
- 일부 TLB는 각 엔트리에 address-space identifier(ASID)를 저장한다.
- ASID는 각 프로세스를 고유하게 식별하여, 프로세스별 주소 공간 보호를 제공한다.
- ASID가 없으면 context switch마다 TLB를 flush(비움)해야 한다.
- TLB는 일반적으로 64~1,024 엔트리로 작게 구성된다.
- TLB miss 발생 시, 해당 값을 page table에서 읽어와 TLB에 적재한다.
- Replacement policy(교체 정책)를 고려해야 하며, 일부 엔트리는 영구적으로 fast access를 위해 wired down될 수 있다.
Associative Memory(연관 메모리)와 주소 변환
- associative memory는 병렬 검색(parallel search)이 가능하다.
- 주소 변환(address translation)은 (p, d) 형식으로 이루어진다.
- p(page number)가 associative register에 있으면, 해당 frame 번호를 바로 얻는다.
- 없으면, page table에서 frame 번호를 읽어온다.
Paging Hardware with TLB(페이징 하드웨어와 TLB)
- CPU가 논리 주소(logical address)를 생성하면, page number가 TLB에 있는지 먼저 확인한다.
- TLB hit: TLB에서 바로 frame number를 얻어, 물리 주소(physical address) 생성
- TLB miss: page table에서 frame number를 찾아 TLB에 적재 후, 물리 주소 생성
- 최종적으로 변환된 물리 주소가 physical memory로 전달된다.
- 이 구조는 메모리 접근 속도를 크게 향상시킨다.
성능 분석 : Effective Access Time(EAT) 계산
- EAT = (1 + ε)α + (2 + ε)(1 - α)
- α : TLB hit 경우, TLB에서 바로 frame number를 얻은후(ε), 물리 메모리에 바로 접근(1)
- (1 - α) : TLB miss 인 경우, page table에서 frame number를 찾아(1) TLB에 적재 후(ε), 물리 메모리에 접근(1)
- α: TLB 히트 비율, ε: TLB 검색 시간
- 예시: α=80%, ε=20ns, 메모리 접근 100ns → EAT=120ns
반응형
댓글