사용자 프로그램의 다단계 프로세스
주소 바인딩(Address binding)
주소 바인딩
- 프로그램 명령 및 데이터를 실제 메모리 주소에 연결하는 프로세스
바인딩 예
주소 바인딩의 세 단계
- 컴파일 시간 바인딩(Compile time binding)
- 로드 시간 바인딩(Load time binding)
- 실행 시간 바인딩(Execution time binding)
컴파일 시간 바인딩(Compile time binding)
- 컴파일 시간에 메모리 위치를 알면 절대 주소의 절대 코드를 생성할 수 있다.
- 시작 위치가 변경되면 코드를 재컴파일해야 한다.
로드 시간 바인딩(Load time binding)
- 컴파일 시간에 메모리 위치를 알 수 없는 경우, 상대 주소로 재배치 가능한 코드를 생성할 수 있다.
- 시작 위치가 변경된 경우에만 리로드하면 된다.
실행 시간 바인딩(Execution time binding)
- 실행 시간(run time)까지 바인딩이 지연된다.
- CPU가 주소를 생성할 때마다 바인딩이 확인된다.
- 주소 매핑을 위한 MMU와 같은 하드웨어 지원이 필요하다.
- 대부분의 OS에서 사용
메모리 관리 장치
논리적 주소(Logical address)
- = 가상 주소(virtual address)
- CPU에 의해 생성
물리적 주소(Physical address)
MMU
- 논리적 주소를 물리적 주소에 매핑하는 하드웨어
단순 MMU 체계
- 재배치 레지스터의 값은 CPU에 의해 생성된 모든 주소에 추가된다.
프로그램 & CPU
- 논리적 주소를 다루지만 물리적 주소는 보지 못한다.
동적 로딩(Dynamic Loading)
호출될 때까지 루틴이 로드되지 않는다.
메모리 공간 활용도 향상
대량의 오류 처리 코드가 필요할 때 유용
Load할 때마다 매번 동일한 address가 비어 있을까? No.
- → 어디든지 load될 수 있기 때문에 dynamic linking이 필요
동적 링킹(Dynamic Linking)
동적 링킹
공유 라이브러리
- 라이브러리가 필요한 모든 프로세스의 경우 메모리에 복사본 하나만 있으면 충분하다.
스와핑(Swapping)
스와핑
- 프로세스를 메모리 부족 상태에서 백업 저장소로 일시적으로 스왑할 수 있다.
- 그리고 나중에 메모리에 되살아난다.
백업 저장소(Backing store)
- 모든 이미지를 수용할 수 있을 정도로 빠르고 크다.
- 예) 디스크
스와핑의 개략도
연속 할당(Contiguous Allocation)
주 메모리의 두 개의 파티션
메모리 매핑 및 보호
- 재배치(Relocation) 레지스터 : 사용자 프로세스를 보호하는 데 사용
- 제한(Limit) 레지스터 : 다양한 논리 주소가 포함, 각 논리적 주소는 제한 레지스터보다 작아야 한다.
- MMU : 재배치 레지스터에 값을 추가하여 논리적 주소를 동적으로 매핑
연속 메모리 할당을 위한 하드웨어 지원
메모리 할당
- 홀(Hole) : 사용 가능한 메모리의 큰 블록, 다양한 크기의 홀이 메모리 전체에 흩어져 있다.
- 프로세스 생성 : 프로세스를 수용할 수 있을 만큼 큰 홀에서 메모리가 할당
- 운영 체제가 유지하는 정보 : 할당된 파티션, 사용 가능한 파티션(홀)
동적 스토리지 할당 문제
- First-fit : 충분한 크기의 첫 번째 홀을 할당
- Best-fit : 충분히 크기의 가장 작은 홀을 할당
- Worst-fit : 충분히 크기의 가장 큰 홀을 할당
외부 조각화(External Fragmentation)
- 요청을 충족하기 위한 총 사용 가능한 메모리 공간이 존재하지만 연속되지는 않는다.
- 압축으로 줄일 수 있다.
- 모든 사용 가능한 메모리를 하나의 큰 블록에 함께 배치
내부 조각화(Internal Fragmentation)
- 할당된 메모리가 요청된 메모리보다 약간 클 수 있다.
- 크기 차이는 파티션 내부에 있지만 사용되지 않는다.
페이징
메모리와 이미지를 각각 고정 크기로 나눈다.
- 페이지 프레임 및 페이지
- 크기는 2의 거듭제곱으로 512B에서 8KB 사이
전체 프로그램 이미지가 디스크에 있다.
프로그램이 시작되면 첫 페이지만 로드한다.
나머지 페이지는 on-demand 메모리에 로드된다.
프로그램의 특정 페이지 X
- 이미 메모리 페이지 프레임 Y에 로드
- 로드된 적이 없고 디스크에 있다.
페이지는 메모리의 모든 위치에 배치할 수 있다.
CPU가 주소를 표시할 때마다 MMU는 페이지 테이블(page table)을 검색한다.
- 논리적 주소를 물리적 주소로 변환하는 데 사용
페이지 테이블 예
다른 페이징 예
주소 변환 체계
- CPU에서 생성되는 논리적 주소는 두 부분으로 나뉜다.
- 예) 지정된 주소 길이 32 및 페이지 크기 4KB
- 페이지 번호(p)
- 페이지 테이블의 인덱스로 사용
- 물리적 메모리에 있는 각 페이지 프레임의 기본 주소를 포함
- 페이지 오프셋(d)
- 기본 주소와 결합되어 물리적 메모리 주소를 정의
공유 페이지
메모리 보호가 구현
- 보호 비트를 각 프레임에 연결
- Read-only, read-write, execute-only bit
- Valid-invalid bit
장점
- 물리적 메모리보다 큰 메모리 공간을 제공
- 32비트 프로세서라면 4GB의 논리적 주소 공간이 가능
- demand 페이징 지원
- 메모리 배치 정책이 필요 없다.
- 페이지 공유 제공
- 메모리 공간을 서로 보호
단점
- 시간적 오버헤드
- 공간 오버헤드
- → 다단계 페이지 테이블, 해시된 페이지 테이블, 역 페이지 테이블
페이지 테이블 구현
페이지 테이블은 메인 메모리에 보관
- PTBR(페이지 테이블 베이스 레지스터) : 페이지 테이블을 가리킨다.
모든 데이터/명령 액세스에는 두 개의 메모리 접근 필요
→ 두 가지 메모리 접근 문제를 해결할 수 있다.
TLB(번역 색인 버퍼)를 사용한 페이징
유효 접근 시간
- TLB 검색 시간 : ε
- 메모리 접근 시간 : 1
- 적중률: α
- 유효 접근 시간 = (1 + µ)α + (2 + µ)(1 – α) = 2 + µ – α
페이지 테이블을 저장하려면 추가 메모리 공간이 필요
프로그램에 주소 공간이 크다.
- 32비트 주소를 사용하면,
- → 4GB 크기의 프로그램 주소 가능
- → 100만 페이지 테이블 항목(페이지 크기가 4KB인 경우)
- → 4MB 페이지 테이블(항목 크기가 4B인 경우)
페이지 테이블은 프로세스별 데이터 구조
- 페이지 테이블을 저장할때 필요한 크기 : 4MB * N(프로세스 수)
페이지 테이블의 구조
- 계층적 페이지 테이블
- 2단계 페이지 테이블 구성표
- 3단계 페이지 테이블 구성표
- 해시된 페이지 테이블(hashed page table)
- 역 페이지 테이블(inverted page table)
2단계 페이지 테이블 구성표
2단계 페이지 테이블 구성표
- 페이지 표 자체도 페이지화
- 전체 페이지 테이블을 디스크에 저장
- 페이지 테이블의 페이지를 필요에 따라 로드
2단계 페이지 테이블 구조를 사용한 주소 변환
- 논리적 주소(페이지 크기가 4K인 32비트)가 분할
- 페이지 테이블 자체가 페이지로 되어 있기 때문에 페이지 번호가 더 구분
- 외부 페이지 테이블의 인덱스에 대한 10비트
- 내부 페이지 테이블의 인덱스에 대한 10비트
64비트 프로세서용 3단계 페이징
해시된 페이지 테이블
논리적 페이지 번호는 테이블로 해시
해시 테이블의 포함된 내용
논리적 페이지 번호를 다음과 비교
일치하는 항목이 발견되면,
역 페이지 테이블(inverted page table)
페이지 테이블의 공간 오버헤드
- 페이지 테이블의 크기는 프로그램 크기에 비례
- 사실, 한 번에 몇 페이지만 필요
역 페이지 테이블
- 각 페이지 프레임에 대해 하나의 페이지 테이블 항목
- 각 페이지 테이블 항목에는 process-id 포함
- 시스템에서는 한 페이지 테이블로 충분
- 연관 검색이므로 전체 테이블을 검색
- 각 페이지 테이블을 저장하는 데 필요한 메모리를 줄인다.
- 테이블을 검색하는 데 필요한 시간이 늘어난다.
- 따라서 해시 테이블 또는 연관 레지스터를 사용해야 한다.
세그먼트
프로그램은 세그먼트의 모음
세그먼트 테이블
논리적 주소 구성
세그먼트 테이블
- 각 테이블 항목
- base : 세그먼트가 메모리에 상주하는 시작 물리적 주소
- limit : 세그먼트의 길이
세그먼트 테이블 베이스 레지스터(STBR)
세그먼트 테이블 길이 레지스터(STLR)
- 프로그램에서 사용하는 세그먼트 수를 나타낸다.
- 세그먼트 번호는 < STLR인 경우 합법적
세분화 아키텍처를 통한 주소 변환
보호
코드 공유는 세그먼트 수준에서 발생
세그먼트의 길이가 다양한다.
- 동적 스토리지 할당 문제가 존재
- first-fit, best-fit, worst-fit
요약
- 주소 바인딩
- 프로그램 명령 및 데이터를 실제 메모리 주소에 연결하는 프로세스
- 컴파일 시간, 로드 시간, 실행 시간의 세 가지 단계에서 발생
- 실행 시간 바인딩 : 바인딩은 실행 시간까지 지연, CPU가 주소를 생성할 때마다 바인딩이 확인
- MMU(Memory Management Unit) : 논리적 주소를 물리적 주소에 매핑하는 하드웨어
- 페이징
- 전체 프로그램 이미지가 디스크에 상주
- 프로그램이 시작되면 첫 페이지만 로드
- 나머지 페이지는 on-demand 메모리에 로드
- 실제 메모리보다 큰 프로그램을 실행 가능
- 모든 데이터/명령어 접근에는 두 개의 메모리 액세스가 필요, 페이지 테이블용, 데이터/명령어용
- 다단계 페이지 테이블 구조 : 페이지 테이블 자체도 페이지로 이동
