Frame
메인 메모리에서 사용되는 고정 길이의 블록
Page
고정 길이의 메모리 블록으로
페이지를 일시적으로 메인 메모리의 프레임에 올릴 수 있다
Segment
가변 길이의 메모리 단위
전체 세그먼트를 메인 메모리에 일시적으로 올릴 수 있고(세그멘테이션),
페이지 단위로 나눈 세그먼트의 페이지를 개별적으로 메인 메모리에 올릴 수도 있다 (세그멘테이션과 페이징의 결합)
메모리 관리 요구사항
재배치(Relocation)
보호(Protection)
공유(Sharing)
논리적 구성(Logical organization)
물리적 구성(Physical organization)
재배치(Relocation)
프로세스들이 스왑 아웃되었다가 스왑 인될때, 메모리의 동일한 영역로 돌아오는 것은 시스템 상 제한을 초래하므로,
다른 영역으로 재배치하는 기능이 필요하다
보호(Protection)
Memory Protection은 OS가 아니라 하드웨어에 의해 충족
OS가 일일이 메모리 참조 위반이 없는지 매번 확인하는 것은 지나치게 많은 시간을 소모하게 되기 때문이다
Hardware Address Protection
합법적인 주소 범위를 판단할 수 있는 기능
Base register: 가장 작은 합법적인 물리적 메모리 주소를 저장
Limit or Bounds register: 주소 범위의 크기를 저장
베이스 레지스터에 300040이 저장되어 있고 리밋 레지스터에 120900이 저장되어 있다면,
300040부터 420939까지의 모든 주소에 합법적으로 접근 가능
(Base ~ Base+Limit)인 주소에는 합법적으로 접근할 수 있다
CPU는 사용자 모드에서 발생하는 모든 메모리 접근이 해당 사용자의 베이스와 리밋 사이에 있는지 반드시 검사해야 한다.
공유(Sharing)
여러 프로세스가 동일한 프로그램을 실행할 경우, 별도의 복사본을 가지기보다 동일한 복사본에 접근할 수 있도록 하는 것
논리적 구성(Logical Organization)
메인 메모리는 linear address로 구성.
프로그램은 nonlinear하며, 모듈 단위로 작성
모듈은 독립적으로 작성 및 컴파일. 모듈별로 보호도 다르게. 모듈은 여러 프로세스 간에 공유 가능
세그멘테이션은 이러한 요구사항에 적합
물리적 구성(Physical Organization)
프로그래머가 메모리 관리를 맡는 것은 바람직하지 않다.
- 구현 프로그램이 가용 데이터보다 클 수 있다
Overlay를 사용해 필요할 때마다 모듈들이 특정 메모리 영역에 교체, 로딩, 실행
- 프로그래머가 가용 공간의 크기나 위치를 알 수 없다
Overlay: 작은 메모리에서 큰 프로그램을 실행하기 위해 필요한 부분만 교체하며 사용하는 기법
메모리는 프로세서 실행을 위해 프로세스를 메인 메모리로 불러온다
- 가상 메모리 (세그멘테이션, 페이징 or 둘 다)
- 메모리 파티셔닝(더 단순한 방법, Simple Paging, Simple Segmentation..)
고정 분할(Fixed Partitioning)
시스템 생성 시점에 메모리를 정해진 크기와 개수의 분할로 나눈다
단점1: 내부 단편화의 발생
단점2: 활성 프로세스 수가 분할 개수만큼으로 제한된다
내부 단편화(Internal fragmentation)
고정 크기로 메모리 블록을 할당할 때, 실제 필요 공간보다 더 큰 블록이 할당되어 낭비되는 공간들
Equal-size Fixed Partitions
구현이 간단하고 오버헤드가 적다
프로그램이 분할 크기보다 크면 오버레이(overlay)를 사용하도록 설계되어야 함
Unequal-size Fixed Partitions
가용 공간에서 내부 단편화를 최소화하도록 프로세스를 할당 가능한 분할 중 가장 작은 분할에 할당한다
(1) 분할별로 스케줄링 큐 사용: 큰 분할들은 잘 사용되지 않을 수 있으므로, 시스템 전체 관점에서는 최적이 아니다
(2) 싱글 큐를 사용: 모든 분할이 사용 중이면 스와핑을 하여야 한다
가변 분할(Dynamic Partitioning)
프로세스가 필요한 만큼의 메모리를 정확히 할당받음
내부 단편화가 없다, 외부 단편화를 제거하기 위해 컴팩션이 필요하다
단점: 외부 단편화로 컴팩션 오버헤드가 발생한다
외부 단편화 (External Fragmentation)
동적으로 메모리의 할당과 해제를 반복하면서, 사이 사이에 조각나서 낭비되는 작은 공간들
압축 (Compaction)
외부 단편화를 해소하기 위해 OS가 메모리 내 프로세스를 연속되게 재배치하여 빈 공간을 하나로 모으는 기법
First-fit
메모리의 처음부터 스캔하여 할당 가능한 첫 번째 빈 공간에 할당하는 방식
간단하고 기징 빠른 성능
Next-fit
이전 할당 위치부터 스캔하여 할당 가능한 다음 빈 공간에 할당하는 방식
전체적으로 할당이 일어나기 때문에 Compaction이 더 자주 필요하다
Best-fit
요청 크기와 가장 가까운 크기의 빈 공간에 할당하는 방식 (외부 단편화가 가장 작게 생기도록)
외부 단편화가 너무 잘게 만들어지기 때문에 컴팩션이 자주 필요
Worst-fit
가장 큰 빈 공간에 할당하는 방식
실제로 가장 비효율적 (큰 공간들이 사라지면서 컴팩션이 더 자주 필요하다)
버디 시스템(Buddy System)
고정 분할과 동적 분할 기법의 절충안
초기에는 전체 공간이 크기 2^U인 하나의 블록으로 취급
2^U는 할당 가능한 전체 메모리 크기
메모리 블록은 크기 2^K 단위, L ≤ K ≤ U
(2^L = 할당 가능한 가장 작은 블록 크기)
(2^U = 할당 가능한 가장 큰 블록 크기(대개 전체 메모리 크기)
버디 시스템(Buddy System) 알고리즘
2^(k-1) < s ≤ 2^k를 만족할 때까지 분할하고, 2^k인 블록을 할당한다
인접한 버디를 직전의 더 큰 분할 크기로 합칠 수 있을 때 합친다
(같거나 살짝 큰 단위까지 나눈다)
페이징(Paging)
메인 메모리는 동일 크기의 여러 프레임으로 나뉘고
프로세스가 프레임과 같은 크기의 여러 페이지로 나뉘고,
페이지들을 연속될 필요 없이 가능한 프레임에 적재하는 방식
외부 단편화는 없으나, 프로세스의 마지막 페이지에 작은 내부 단편화가 발생할 수 있다.
페이지 테이블(Page Table)
프로세스의 페이지가 위치한 프레임 정보를 담고 있다.
페이지 번호(0부터 시작)를 인덱스로 사용
메인 메모리의 사용되지 않는 프레임을 관리하는 하나의 free-frame list를 관리
프로세서는 logical addresss(페이지 번호, 오프셋)를 page table을 통해 physical address(프레임 번호, 오프셋)로 변환
고정 분할과 유사하지만, (1) 분할 크기가 매우 작고 (2) 연속적일 필요 없다는 점에서 다르다
페이지 번호(p): 페이지 테이블의 인덱스로 사용, 물리 메모리 내 각 페이지의 base address를 가리킨다
페이지 오프셋(d): base address에 더해져 실제 물리 메모리 주소를 구할 수 있고, 이 주소가 메모리로 전달됨
세그멘테이션(Segmentation)
프로세스가 최대 길이가 정해져 있는 가변적 길이의 여러 개의 세그먼트로 나뉘고
세그먼트들을 연속될 필요 없이 가능한 분할에 적재하는 방식
Logical Address는 (Segment #, Offset)
동적 분할과 유사지만, 연속적이지 않아도 되는 분할에 적재
내부 단편화는 없지만 외부 단편화는 발생할 수 있다
Simple segmentation 기법은
각 프로세스마다 세그먼트 테이블과 빈 블록 리스트를 사용
1. 논리 주소의 왼쪽 n비트를 세그먼트 번호로 추출
2. 세그먼트 번호를 인덱스로 세그먼트 테이블에서 해당 세그먼트의 Base를 찾는데, 논리 주소의 오른쪽 m비트로 Offset이 세그먼트 Length보다 크거나 같으면 주소가 유효하지 않다.
3. 원하는 물리 주소는 세그먼트 Base address와 offset의 합이다
(페이징과 유사하나, 세그먼트 테이블에 length가 추가적으로 있어서 offset과의 비교를 통해 유효한 주소인지 확인한다)
가상 메모리
보조 기억 장치를 마치 메인 메모리의 일부처럼 프로그램 주소를 변환해 사용하는 저장 방식
프로그램 주소는 물리 주소와 구별
프로그램이 생성한 주소는 자동으로 기계 주소로 변환
가상 저장 공간의 크기는 주소 정책이나 보조 기억 장치의 용량에 의해 제한
실행 중에 프로세스의 모든 페이지나 세그먼트가 메인 메모리에 있을 필요는 없다
필요한 주소가 메인 메모리에 없을 경우, 페이지 폴트 인터럽트가 발생한다.
운영체제는 인터럽트가 발생한 프로세스를 블로킹 상태로 전환
논리적 주소를 포함하는 프로세스 조각이 메인 메모리로 불러져 와야 한다
운영체제는 디스크 I/O 읽기 요청을 수행
디스크 I/O가 수행되는 동안, 다른 프로세스가 실행된다.
디스크 I/O가 완료되면 인터럽트가 발생하고 제어가 운영체제로 돌아가며, 운영체제는 해당 프로세스를 레디 상태로 전환
(페이지 테이블 확인했을 때, 메인 메모리에 있으면 물리 주소를 계산해서 메인 메모리로 접근)
(페이지 테이블을 확인했을 때, 메인 메모리에 없으면(i) 해당 프로세스를 블로킹한다음 디스크로 가서 메인 메모리로
가서 가져온 다음 레디 상태로 전환)
가상 메모리의 장점
(1) 더 많은 프로세스를 메모리에 수용 가능해서 CPU Utilization이 높아짐
(2) 프로세스의 크기가 물리적 메모리의 크기보다 커질 수 있다
지역성의 원리: 프로그램은 짧은 시간 동안 한정된 메모리 영역만을 집중적으로 참조하는 경향이 있다는 원리
Thrashing: OS가 페이지 교체에 과도하게 많은 시간을 소비하여 실제 작업은 거의 수행되지 않는 상태
(사용되기 직전의 조각을 계속해서 내보낸다면 비효율적으로 작동하게 됨)
OS는 최근 사용 이력을 기반, 가까운 미래에 사용될 가능성이 가장 낮은 조각을 추측하여 내보내려고 한다.
가상 메모리가 효과적으로 동작하기 위해서:
하드웨어 지원(주소 변환)
OS는 어떤 페이지가 들어가고 나오는지를 관리하는 소프트웨어를 포함해야함
각 프로세스는 고유한 페이지 테이블을 가진다
각 PTE(Page Table Entry)는 메모리 내 해당 페이지의 프레임 번호, 컨트롤 비트(P-bit, M-bit)
OS는 free-frame list를 관리
P bit(valid-invalid bit): 페이지가 메모리에 존재함을 나타냄
M bit: 페이지가 변경되었음을 나타냄
[Paging]
Virtual address: Page #, Offset
PTE: Page #, Frame #, Control bit(P-bit, M-bit)
Physical address: Frame #, Offset
[Inverted Page Table]
Virtual address: Page #, Offset
Inverted Page Table: Index(Frame #), Pid, VPN, Chain, Control bit
Physical address: Frame #, Offset
[Segmentation]
Virtual address: Segment #, Offset
STE: Segment #, Length, Base, Control bit
Physical address: Base + Offset
Two Level Hierarchical Page Table
한 페이지의 크기 4KB(2^12) , 32비트(2^32 = 2^20개 * 한 개당 2^12) 주소를 가정
4GB(2^32) 가상 주소 공간은 2^20개 페이지로 구성
총 용량: 4GB(2^32) = 2^20개 * 4KB(2^12)
따라서 하나의 페이지 테이블은 2^20개의 PTE로 구성되고 하나의 PTE는 4Byte(32비트)
user 페이지 테이블 용량: 4MB = 2^20개 * 4Byte
각 프로세스마다 페이지 테이블 용량으로 4MB(2^22)차지
root 페이지 테이블 용량: 4KB = 엔트리 2^10개 * 엔트리당 4Byte
프로세스들은 4KB(4 * 2^10)의 root 페이지 테이블만 메인 메모리에 상주시키고
나머지는 필요할 때만 디스크에서 가져온다
4GB 저장하는데
1계층이었으면 프로세스당 페이지 테이블을 저장하는데 4M 필요했는데
2계층으로 구성함으로써 프로세스당 페이지 테이블 저장하는데 4K만 필요
(2 * 2^10 = 2^12)
(2^12 * 2 ^10 = 2^22)
페이지 테이블의 크기가 virtual address space(VAS)의 크기에 비례
=> 대안 : Inverted Page Table
각 엔트리는 다음을 포함
VPN (페이지 번호) – 가상 주소(Virtual Address)의 페이지 번호
pid – 이 페이지의 소유 프로세스
제어 비트
chain 포인터 – 체인 내 다음 항목의 인덱스 값
Hash (PID, VPN(Virtual Page Number)) => Index(Frame #)
Inverted Page Table에서 해당 테이블 인덱스의 항목에서,
pid, VPN이 같으면 => (Index == Frame #) + Offset 해서 실제 주소로 이동
pid, VPN이 다르면 => 체인을 타고 다음 인덱스 항목으로 넘어간다
가상 페이지마다 하나씩이 아니라, 실제 물리적 메모리 프레임마다 엔트리들이 존재
프레임 번호로 페이지 테이블 항목(PTE)을 인덱싱
(페이지 번호 X, 프레임 번호 O)
TLB
가상 메모리 참조는 두 번의 메모리 접근을 유발(한 번은 페이지 테이블, 한 번은 데이터)
최근에 사용된 PTE를 저장하는 캐시
Direct Mapping:
PTE를 TLB의 고정된 엔트리에 매핑하고, 찾는 방식
Associative Mapping:
PTE를 TLB의 어떤 엔트리에든 저장할 수 있으며, 하드웨어가 동시에 모든 엔트리를 한방에 확인하는 방식
캐쉬는 블록단위로 불러오고 블록단위로 저장 (지역성의 원리를 활용하기 위해서)
TLB 히트 + 캐쉬 히트 시, 메모리에 한 번도 접근하지 않고 값을 바로 가져올 수 있다
Page Size
페이지 크기 결정 시 고려 세 요소
내부 단편화 감소: 페이지 크기가 작을수록 내부 단편화는 줄지만, 페이지 수 증가로 페이지 테이블이 커진다.
페이지 폴트 감소: 큰 페이지는 PTE 수를 줄여서 해당 페이지 테이블이 메인 메모리에 유지될 확률을 높여서
이중 페이지 폴트를 줄일 수 있으나, 내부 단편화가 발생할 수 있다
효율적인 데이터 블록 전송: 큰 페이지 크기가 I/O 성능에 유리하나, 내부 단편화가 발생한다
페이지 폴트율
1. 큰 페이지는 지역성의 효과를 약화시켜 페이지 폴트율을 증가시킬 수 있지만, 페이지 크기가 프로세스 크기에 가까워지면 다시 감소한다.
2. 페이지 폴트율은 페이지 크기뿐만 아니라 프로세스에 할당된 프레임 수에도 영향을 받는다(SW issue)
(할당 프레임 수가 증가함에 따라 확 줄다가 서서이 줄어든다)
Segmentation Only
메모리를 세그먼트로 나누어서 관리
장점: 동적 구조 처리, 모듈화, 공유 및 보호 지원
P-bit: 세그먼트가 이미 메모리에 있는지 확인
M-bit: 세그먼트가 수정되었는지 확인
(Simple Segmentation과 유사하게 동작)
Combining Paging and Segmentation
각 세그먼트는 페이지 여러 개로 나뉜다.
장점:
- 세그멘테이션은 프로그래머에게 visible
- 동적 구조 처리, 모듈화, 공유 및 보호 지원
- segmentation과 달리, 외부 단편화가 없다
- 매핑이 단순
- segment 테이블에서 꺼내는 base address로 page 테이블을 찾고
- Page 테이블에서 page #로 frame #를 찾아 물리 주소로 변환
(프로세스마다 세그먼트 테이블)
(세그먼트 별로 페이지 테이블)
(메모리를 3번 접근해야 한다는 단점이 있다)