Main Memory
Background
메모리는 각각 고유한 주소를 가진 바이트 배열로 구성됨
프로그램은 디스크에서 메모리로 가져와 프로세스 내에 배치되어야함
메인 메모리와 레지스터는 CPU가 직접 접근 가능한 유일한 저장소임
레지스터 접근은 CPU 클럭으로 수행됨
CPU와 메인 메모리 사이에 있는 캐시는 하드웨어로만 관리 가능함
Logical vs Physical Address Space
Logical Address
CPU에 생성되는 가상의 주소
Logical address space에 속함
Physical Address
실제 메모리 장치 주소
Physical address space에 속함
컴파일 타임 바인딩이랑 로드 타임 바인딩일 때는 둘이 같음
실행 시간 바인딩일 때는 둘이 다름
MMU(Memory Management Unit)
실행 시 Logical Address를 Physical Address로 매핑하는 하드웨어 장치
Simple Memory Management Scheme
MMU 안에는 relocation register라는 기본 레지스터가 들어감
각 프로세스가 생성한 모든 주소마다 relocation register의 값이 더해짐(값은 프로세스마다 다름)
사용자 프로그램은 logical address는 볼 수 있는데 physical address는 못봄
Contiguous Allocation
메인 메모리는 OS와 사용자 프로세스 모두 지원해야해서 효율적으로 할당을 해줘야 함
메인 메모리는 interrupt vector 등을 포함한 저메모리에 있는 resident OS와
단일 연속 섹션을 바탕으로 한 고메모리에 있는 user process로 나뉨
이때, relocation register는 user process를 서로 보호하고 운영 체제 코드와 데이터를 변경하지 않도록 함
Base register는 가장 작은 physical address의 값을 가짐
Limit register는 logical address의 범위를 가짐
밑에 그림처럼 프로세스들을 가변적인 크기의 파티션들에 할당해줌
hole이란 사용가능한 메모리 블록을 말함
프로세스가 도착하면 프로세스의 크기보다 큰 hole에 프로세스를 할당함
프로세스가 종료되면 메모리 블록을 해제하고 hole이 생김
Dynamic Storage Allocation Problem
이때, 프로세스를 어떤 hole에 할당해야 효율적일까라는 고민이 생겼고 여러 방법들이 있음
First-fit 충분히 큰 첫번째 hole에 할당
Best-fit 충분히 큰 가장 작은 hole에 할당, 가장 작은 남겨진 hole 생성 -> 정렬되어 있지 않는한 전체를 검색해야 함
Worst-fit 충분히 큰 첫번째 hole에 할당, 가장 큰 남겨진 hole 생성
First-fit은 speed가 좋고, Best-fit은 util이 좋고, Worst-fit은 그냥 안 좋음
Fragmentation
External Fragmentation 메모리를 가변적인 크기로 할당하니 총 메모리는 충분한데 메모리 블록이 연속적이지 않음
Internal Fragmentation 메모리를 요청보다 조금 큰 고정적인 크기로 할당하니 파티션 내부에 남은 메모리 공간이 생김
Compaction(압축)을 통해 external fragmentation을 줄일 수 있음
재배치가 동적일 때만 가능한데 메모리를 셔플해서 남은 메모리들을 하나의 거대한 블록에다 배치하는거임
모든 프로세스를 메모리 한 쪽 끝에 놓는 것이 제일 간단함
Paging 기법도 해결책임
logical address space를 비연속적으로 허용하고 프로세스가 해당 메모리를 사용할 수 있는 physical memory에 할당되도록 함
Paging
physical address space는 비연속적일 수 있음
internal fragmentation은 있을 수 있는데 external fragmentation을 방지함(가변적 크기의 메모리 청크 문제 해결함)
physical memory는 2의 거듭제곱의 크기를 가진 고정된 크기의 frame으로 나뉨
locial memory는 frame과 같은 크기의 page로 나뉨
page와 frame은 서로 매칭됨
각 프로세스는 page table이 필요함(logical->physical)
logical address 밑에 두개로 나뉨
Page number physical memory안의 base address를 가진 page table의 index
Page offset base address와 결합해 정확한 physical memory address를 정의
page table의 인덱스값은 page number이고 데이터값은 frame number임
logical address를 physical address로 변환하는 단계(MMU가 함)
- 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용
- 페이지 테이블에서 해당 프레임 번호 f를 추출
- 논리 주소의 페이지 번호 p를 프레임 번호 f로 대체
대충 이렇게 하면 됨
Page Table Implementation
page table은 main memory의 kernel쪽에 보관됨
Page-table base register(PTBR)가 page table을 가리킴
Page-table length register(PTLR)가 page table의 크기를 나타냄
MMU는 page table에 대한 접근과 프로세스의 데이터, 코드에 대한 접근 총 2번의 메모리 접근을 시행함
Translation Look-Aside Buffer
TLB는 빠른 참조를 위한 하드웨어 캐시로 page table의 일부이며 크기가 매우 작음
TLB miss가 나면 다음 접근을 위해 값이 TLB에 올라감
일부 TLB는 각 TLB 항목에 process Id인 address-space identifiers(ASIDs)를 고유하게 저장함
각 프로세스를 식별해 해당 프로세스에 대한 주소 공간 보호를 위함
안 그러면 모든 컨텍스트 스위치마다 flush해야함
기존에서 TLB만 추가된 구조임
Memory Protection
read 또는 read-write 허용을 타나내는 protection bit가 frame마다 있음
용도마다 다른 비트를 커스텀할 수도 있음
Valid-invalid bit은 page table의 엔트리에 하나씩 붙어 있음
valid : page가 프로세스의 logical address space에 있음
invalid : page가 프로세스의 logical address space에 없음
접근 가능 범위를 확인하기 위해 PTLR을 쓰기도 함
위반하면 kernel에 trap을 발생시킴
Page Table Structure
Hierarchical Page Tables
logical address space를 여러 개의 page table로 나눔
Two-Level Paging
위 구조를 적용하면 이렇게 page number가 2개 이상이 됨
p1은 outer page table index, p2는 inner page table offset
Hashed Page Table
virtual page number가 page table로 해시됨
hash function은 모듈러 연산을 통해 더 작은 범위로 mapping시키는 구조임
Linked List로 이루어져 있으며 virtual page number, frame의 값, 다음 요소의 포인터로 구성됨
Inverted Page Table
기존 page table이랑 아예 다른 구조임
기존에는 index, page number로 구성되었다면 얘는 frame number, pid 및 페이지의 주소로 구성됨
전체 시스템에서 page table을 한 개만 관리하는 상남자 구조임
용량은 이득인데, 페이지 접근속도는 손해임
보통 RAM 용량이 작을 때 씀
Swapping
프로세스를 일시적으로 memory에서 backing store로 교체한 다음 memory로 가져와 계속 실행할 수 있음
프로세스의 총 physical memory space가 physical memory를 초과할 수 있음
표준 Swapping은 메인 메모리와 백업 저장소 간의 전체 프로세스(pages) 이동임
Page out page를 memory -> backing store
Page in page를 backing store -> memory
