센로그
9. Main Memory 본문
◆ 요점 정리
1. 메모리
- 메인 메모리
- 메모리 스톨 발생 가능성 → 캐시 사용
- 캐시
- 레지스터
- CPU 클락 한 사이클 내 접근 가능
2. 메모리 보호
- base-limit 레지스터
- 프로세스가 범위 어길 시 trap
- 운체는 모든 메모리 접근 가능
3. 주소 바인딩
- symbolic address
- relocatable address
- logical address
- absolute address
- physical address
- logical address → physical address
- 컴파일시/로드시/실행중 언제나 가능.
- 실행시 바인딩되는 경우 logical address를 virtual address라고도 부름
- 컴파일러/링커,로더/MMU
- 컴파일시/로드시/실행중 언제나 가능.
4. logical address vs physical address
- logical address: CPU와 프로세스가 보는 주소
- 프로세스별로 독립적
- 주로 0부터 시작
- physical address: 메모리가 보는 주소
5. MMU
- 실행 시 logical address를 physical address로 변환해주는 하드웨어 장치
- contiguous 방식: logical address 받아서 limit 레지스터 범위 내인지 체크하고 relocation 레지스터 값 더함
- 페이징 방식: 페이지 테이블 사용해서 valid-invalid 비트를 통해서 합법/불법 체크하고 해당 프레임+오프셋으로 이동
6. low memory vs high memory
- low memory: 운체
- high memory: 유저 프로세스
7. 메모리 할당 방식
- Contiguous allocation
- dynamic storage allocation problem
- First-fit
- Best-fit
- Worst-fit
- External/Internal Fragmentation 발생
- dynamic storage allocation problem
- Paging
- 프로세스 별 page table 존재
- logical address 구성: page number + page offset
- 한 페이지나 프레임 내에서는 연속적으로 저장되므로 offset을 통해 접근 가능
- External Fragmentation 해결. Internal은 발생 가능하나 그래도 Contiguous보단 성능 좋음
8. (페이징 시) TLB
- 페이징시 translation 정보 미리 캐싱해두는 하드웨어 캐시
- MMU 안에 존재
- translation 정보란 (페이지 넘버, 프레임 넘버)
- 프로세스 context switching시 초기화되나, 스레드 context switching 시에는 유지됨
9. 페이징 시, 메모리 보호
- valid-invalid bit를 protection bit로 사용
- 이를 통해 합법/불법 주소 판단
10. 페이징 시, 페이지 테이블 구조화 방법
- Hierachial Page Table
- Hashed Page Table
- Inverted Page Table
- (pid, p)
◆ 메인 메모리
기본적으로 프로그램은 디스크(non volatile)에 저장되어있음. 실행하려면, 디스크 → 메모리 → CPU 순으로 갖고와야 함.
이때 메모리는 중요한 역할을 함!!
ㆍCPU가 프로그램을 실행하려면 (프로그램 카운터 값에 따라) 메모리에 들어있는 instruction을 읽어와서 실행함
하이 레벨에서 메모리는 byte들의 배열로 표현됨. 각 byte에 자신의 주소가 부여되어 있어서, 이를 통해 byte 사이즈의 데이터에 접근할 수 있다.
ㆍ각 프로세스는 항상 프로세스(자신)의 adress space에 위치해야 함. 이는 메모리 위쪽(낮은 주소)에 위치해 있음.
프로그램을 로드하면 instruction들이 text 섹션으로 들어가는 것처럼, 실행중인 프로그램은 프로세스 안에 놓여야 한다는 뜻.
◆ 메모리 - 메인 메모리, 캐시, 레지스터
메인 메모리와 레지스터는 CPU가 직접 접근할 수 있는 유일한 저장소임!!
ㆍ 레지스터
- CPU 안에 있는 작은 저장소
- 레지스터에는 CPU의 연산 중간 결과 값 같은 게 저장됨
- 레지스터 접근은 엄청나게 빠름. CPU안에 레지스터가 있기 때문.
- 보통 CPU 한 클락 사이클 내에 접근 가능함(몇몇은 더 빨리도 가능). 저장소 중에서 젤 빠름!!
ㆍ 메인 메모리
- 프로그램의 data나 instruction들이 저장됨.
- 메인 메모리는 접근할 때 여러 사이클이 걸림
→ 레지스터와 달리 CPU 한 클락 사이클 내에 접근이 끝나는 게 아니기 때문에, CPU가 기다려야 할 수도 있음 → 메모리 스톨 발생! (Memory stall : 메모리에서 데이터를 가져오는 동안 코어가 잠시 동작을 멈추는 것을 의미함.)
메모리 스톨의 해결법은 CPU와 메인 메모리 사이에 빠른 메모리를 추가하는 것. 또는 하이퍼 스레딩을 쓰는 것.
→ 따라서 CPU칩 안에 추가한 메모리가 바로 캐시~
ㆍ 캐시
- CPU와 메인 메모리 사이에 있는 저장소
- 캐시의 역할은, 캐싱. 즉,CPU와 메인 메모리 사이에서 일부 데이터들을 미리 가져오는 것.
→ CPU가 instruction에 더 빨리 접근할 수 있게 도와준다.
- 보통 멀티 레벨로 되어있다. 각 코어마다 가지는 L1캐시, 코어들이 공유하는 L2캐시, ..이런 식.
- 캐시는 하드웨어 단에서 관리되기 때문에 OS의 컨트롤이 필요가 없다.
CPU가 데이터나 instruction들을 메모리에서 갖고오는 것 같아도 사실은 캐시에서 갖고오는 것 일 수도 있는데, 뭐 이런거까지는는 우리가 몰라도 된다는 뜻. 하드웨어가 알아서 잘 해줌~
※ 하이퍼 스레딩
: 한 코어에 두 스레드가 관리될 수 있도록 하는 것.
T1이 실행되다가 메모리 접근할 일이 생겨서 메모리 스톨이 발생하면, 어차피 그 동안은 T1을 실행 못하니까 그 때 바로 T2로 전환해서 실행하도록 하는 것
◆ Memory Protection
각 프로세스가 자신의 address space에 속하는 address만 접근해야 하도록 보장하는 것!!
메모리는 보호가 굉장히 중요함.
각각의 프로세스가 제대로 된 동작을 하기 위해서는 메모리가 프로세스별로 잘 보호되어야 한다.
ex)
프로세스 A의 주소 공간 중 text 섹션 안에는 A의 instruction들이 들어있을 텐데, 보호가 안 되어서 다른 프로세스 B가 접근해서 instruction을 다른 걸로 샥 바꿔버린다면? → 제대로 실행이 안 될 것임 ㅠㅠ.
즉, 메모리를 보호한다 == 각 프로세스가 자신의 address space에 속하는 address만 접근해야 하도록 보장해야 한다는 것.
이를 구현하기 위한 가장 간단한 접근법: base, limit register 쌍을 사용하는 방법이 있다.
■ base, limit register 동작 원리
다음은 메인 메모리 전체에 관한 그림이다.
커널이 있고, 각 프로세스가 메인 메모리의 일정 부분을 차지하고 있다(address space).
※ 그림은 base와 limit을 이해하기 쉽게 표현한 것이지, 원래는 메모리 위쪽에 주로 낮은 주소가 들어감.
실행중인 프로세스의 경우, 프로그램 카운터가 현재 실행중인 instruction의 address를 가리키고 있을것임
이때, 해당 프로세스의 주소 공간의 start address와 end address를 알면 그 사이만을 접근하도록 할 수 있음!
따라서 그 둘을 기록하기 위한 레지스터(base, limit)을 두는 것.
- Base 레지스터: start address(접근 가능한 물리적 메모리의 최저점)를 저장.
- Limit 레지스터: start address와 end address 사이의 크기를 저장.
이들은 항상 현재 실행중인 프로세스의 base와 limit 값을 저장하고 있어서, 허용 범위 안의 메모만 접근할 수 있도록 함.
Context switch 되면 다음 프로세스의 base와 limit 값을 저장하고… 이런 식.
두 레지스터 값을 통해 접근 가능한 메모리 구간이 어디인지 알 수 있음!!
- 유저 모드에서, 프로세스에 허용된 범위 이외의 메모리(커널의 메모리나 다른 프로세스의 메모리)에 접근하면, OS에 트랩을 보냄. 불법 주소 접근했다고.
- 반면 OS는, 모든 메모리 공간에 접근 가능함. 따라서 OS는 프로그램을 메모리에 올리거나 내리는 걸 관리해주고, 시스템 콜도 수행해주고.. 여러 서비스를 해줄 수 있음.
◆ Address Binding
디스크에 저장된 프로그램은 메모리로 올라올 준비(실행될 준비)가 되어있는 상태로 저장됨.
보통은, 실행 가능한 binary 파일 형태로 저장됨.
프로그램은 작성되고 실행되기까지 여러 단계들을 거치는데, 각 단계들에서 주소가 표현되는 방식이 각기 다름.
- 소스 코드에서의 주소는 symbolic address(기호적인 주소)임.
프로그래머가 프로그램을 작성할 때, 특정 변수에 값을 저장하거나 함수를 호출할 때 메모리의 특정 번지를 직접 지정하는 대신, 주로 심볼로 된 주소를 사용함.
(ex: 포인터를 통해 변수의 주소를 참조함)
- 컴파일된 주소는 이런 기호적인 주소가 relocatable address(위치를 바꿀 수 있는 주소)로 바인딩 된 것.
(ex: 이 모듈의 시작점으로부터 14바이트 떨어져있는 곳. Logical address)
- 그러면 이후에 링커나 로더가 이 relocatable address를 absolute address(절대 주소)로 바인딩 해줌.
(ex: 74014번 주소. Physical address)
■ logical address가 physical address로 바인딩되는 것은 컴파일/로드/실행중 세 단계 중 아무 때나 일어날 수 있음.
• compile time에 physical address에 바인딩되는 경우 (by 컴파일러)
• load time에 physical address에 바인딩되는 경우 (by 링커, 로더)
이 경우에 최종 바인딩은 로드 시(디스크에서부터 메모리로 가져오는 시간)까지 지연됨.
• execution time에 physical address에 바인딩되는 경우 (by MMU)
◆ Logical vs Physical Address Space
- logical address
: 각 프로세스마다 독립적으로 가지는 주소 공간이다. 각 프로세스마다 일반적으로 0번지부터 시작함.
- CPU에 의해 생성된 주소이며, CPU가 인식하는 주소. virtual address라고도 불림.
- CPU가 메모리 100번에 있는 걸 줘! 라고 하는 건 Logical Address 100번지를 요청하는 것임.
- 만약 프로그램의 Instruction 속에 다른 Logical Memory의 주소에 관한 내용이 있다고 하자. 실제로 메모리에 올라가면 각 'Instruction들의 주소'는 Logical Address → Physical Address로 바뀌지만, 그 안에 있는 'Instruction 내용상의 주소'는 그대로 바뀌지 않음. - physical address
: 메모리에 실제로 올라가는 위치.
메모리가 인식하는 주소.
메모리의 memory-address register에 저장하는 실제 메모리 주소를 의미함.
- 컴파일 시나 로드 시에 physical address에 바인딩된 logical address는 physical address와 동일하지만,
- 실행 시에 physical address에 바인딩된 logical address는 physical address와 다름. 달라질 수 있음.
정확히는, 이때의 logical address를 virtual address라 부름. (두 용어를 종종 혼용함)
(동일하다는 건 메모리 주소가 동일하다는 게 아니라, 1:1로 매핑될 수 있다는 뜻임)
- Logical address space : 프로그램이 생성한 logical address들의 집합
- Physical address space : 프로그램이 생성한 physical address들의 집합
◆ Memory Management Unit (MMU)
실행 시 virtual address를 physical address로 매핑해주는 하드웨어 장치
MMU의 메모리 관리(매핑) 기법에는 여러가지 방법이 존재함.
여기서는 그중 하나인 base-register scheme으로 일반화해서 이해해보자.
■ base-register scheme
이제는 base 레지스터를 relocation 레지스터라고 부를 것임.
- 유저 프로그램은 절대로 실제 physical address에 접근하지 않음. 오로지 logical address만 다룸.
- MMU는 유저 프로그램의 logical adress에다 relocation 레지스터의 값을 더해서, physical address로 재배치 함.
ex) 위 그림에서는 MMU가 유저 프로그램의 logical address 346번지에다 relocation 레지스터의 값인 14000을 더해서, physical address 14346번지에 매핑해줌. 이를 통해 실제 memory에 접근하고 있음.
◆ Contiguous Allocation
메모리를 연속적으로 할당하는 방식
메모리를 보통 두 영역으로 구분함
- low memory: 운영체제가 사용하는 메모리. 아래쪽에 있는 높은 주소
- high memory: 유저 프로세스가 사용하는 메모리. 위쪽에 있는 낮은 주소
메인메모리에는 OS와 여러 유저 프로세스들이 동시에 올라와야 함. 그러므로 최대한 효율적으로 할당을 해줘야 함.
여기서는 메모리 할당 방법 중, 초기 방법인 Contiguous Allocation(연속 메모리 할당) 방법을 설명할 것임.
각각의 유저 프로세스가 하나의 연속된 physical 메모리 공간을 사용하도록 하는 방법임.
이때 각 프로세스의 메모리 공간은 limit, base 레지스터를 통해 보호됨
- 각 프로세스의 logical address의 시작 주소는 0이므로, 각 logical address는 반드시 limit 레지스터(메모리 크기 나타냄)의 범위 내에 존재해야 함.
- 만약 이 범위 내에 존재하는 주소라면, MMU가 logical address에 relocation 레지스터 값을 더해줘서 physical address에 동적으로 매핑해줌. 이 주소를 통해 실제 메모리에 접근함.
- 범위를 벗어난다면 운영체제에 트랩 보냄.
CPU 스케줄러가 실행할 프로세스를 선택하게 되면 디스패처가 context switch의 일부 과정으로서 올바른 값의 재배치 레지스터랑 리미트 레지스터를 적재해줌. CPU가 생성한 모든 주소는 이 레지스터 값을 통해 합법인지 확인하게 될테니 운영체제 및 다른 사용자 프로세스의 자료가 현재 프로세스에 의해 수정되지 않도록 보호해줄 수 있음.
다시 돌아와보자.
메모리 할당하는 가장 간단한 법은 프로세스를 메모리에 딱 넣을 수 있을 만큼의 크기로 메모리를 분할하여 넣어주는 것임. 이런 방법을 Variable Partition Scheme이라고 함.
이 방법에서는 OS가 메모리 중 어느 부분이 사용 중이고, 어느 부분이 사용 가능한지 기록해야 함.
메모리 중 사용 가능한 메모리의 블록을 hole 이라고 함.
- 처음에는 하나의 거대한 hole이 있을 것임.
- 프로세스에 메모리가 할당되려면 프로세스가 요구하는 메모리 만큼의 크기의 hole이 있어야 함.
(만약 그만큼 크기의 hole이 없다? 그러면 걔 한테 지금은 메모리 할당 못함. 대기 큐에 넣어주거나, 너 실행 못한다고 하면 됨.) - 프로세스에 메모리를 할당하면, 원래 hole에서 프로세스가 쓰는 만큼의 메모리를 빼고 남은 leftover hole이 생김.
- 프로세스가 종료되면 해당 메모리 공간 만큼을 해제하므로, 그만큼의 hole이 생김.
이렇듯 주어진 hole들 목록에서 크기 n만큼의 메모리 요구 요청을 들어주는 방법을 찾는 문제를 dynamic storage-allocation problem 이라고 함.
■ dynamic storage-allocation problem
: 주어진 hole들 목록에서 크기 n만큼의 메모리 요구 요청을 들어주는 방법을 찾는 문제
이 문제에는 여러 종류의 해결 방식들이 존재함.
- First-fit
: 메모리를 탐색하다가, 처음으로 찾은 공간이 충분한 hole에 할당하는 방식 - Best-fit
: 공간이 충분한 hole들 중, 가장 크기가 작은 hole에 할당하는 방식
leftover hole 크기가 가장 작음 - Worst-fit
: 공간이 충분한 hole들 중, 가장 크기가 큰 hole에 할당하는 방식.
leftover hole 크기가 가장 큼
보통 First-fit이나 Best-fit이 속도 측면과 메모리 효용 측면에서 Worst-fit보다 나음.
그런데 얘네들은 사실.. 파편화(Fragmentation) 문제를 유발함. 말 그대로 메모리가 사용하지 못하는 여러 파편으로 쪼개지는 것을 의미함. 그 중에도 특히 External Fragmentation(외부 파편화)을 유발함.
파편화에는 두가지 유형이 있음
- External Fragmentation
: 사용 가능한 총 메모리 공간은 할당 해주기에 충분한데, 연속된 공간이 없어서 할당을 못 해주는 문제.
ex) 메모리 할당과 해제를 반복하는 과정에서, 다양한 위치에 다양한 사이즈의 hole이 생길 것. 큰 hole이 여러 개의 작은 hole로 나뉠 것임. 연속적으로 할당 하려면, 하나의 커다란 hole이 존재해야 하는데.. 이렇게 작은 hole들로 나뉘면 사용 가능한 메모리 공간 총량은 충분할지라도, 연속적인 메모리 공간이 없어져서 프로세스를 실행할 수 없게 됨.
- Internal Fragmentation
: 할당한 메모리와 요구한 메모리 간의 차로 인해 발생하는 파편화.
할당한 메모리가 요구한 메모리보다 조금 더 커서, 할당한 메모리 중 사용되지 않는 메모리 공간이 존재하는 것.
주로 메모리를 고정된 크기의 블록으로 나누고, 블록 단위로 할당해주는 방식에서 발생함.
외부 파편화에는 두가지 해결책이 있음.
- Compaction(압축)
: hole이 생기면 위치를 재배치해서 커다란 하나의 hole로 합치는 것.
- 이 방법은 주소 재배치가 동적으로 이루어지고, 실행 시간 내에 완료되는 경우에만 사용 가능함.
- 근데 이건 쫌 비싼 연산임. 엄청 느리고 오버헤드 큼. 사용 ㄴㄴ. - Paging(페이징)
: logical address space가 비연속적(noncontiguous)일 수 있도록 해주는 것.
이에 따라 physical address space에서 공간이 있는 곳마다 할당할 수 있게 해줌.
- 더이상 연속 할당 안 씀. 페이징이 컴퓨터 시스템에서 가장 일반적으로 사용하는 메모리 관리 기법임
◆ Paging
고정된 크기의 페이지 - 프레임을 1ㄷ1 매핑하는 방식.
페이징 기법을 쓰면, 프로세스의 physical address space가 비연속적이어도 됨.
→ 외부 파편화 문제 해결!!
→ 내부 파편화 문제는 일어날 수 있음. 그러나 내부 파편화된 메모리들을 다 합쳐도 contiguous 보다는 훨씬 적어서, 성능이 훨씬 좋아진다.
< 페이징 구현 방법 >
- 우선 physical memory를 고정된 크기의 블록, 즉 frame으로 나눔.
- 그리고 logical memory를 frame과 같은 크기의 블록으로 나눔. 이를 page라고 부름.
- 프로세스 실행 시, 프로세스의 page들이 physical memory 상의 사용 가능한 frame 위로 각각 올라감.
실행 시에 페이지와 프레임이 1:1로 매핑되는 것
각 프로세스들은 logical address를 physical address로 변환하기 위한 page table을 갖고 있음. (OS가 관리함.)
모든 logical address는 page number와 page offset으로 구성되어 있음.
- page number: (프로세스 별) 페이지 테이블의 인덱스로 쓰면, 각 페이지가 매핑되는 각 프레임의 시작 주소를 찾을 수 있음.
그림에서 0번 페이지 1번 프레임에, 1번 페이지 4번 프레임에, ... 매핑된 것. - page offset: 페이지 시작 지점에서 얼마나 떨어져 있는지를 의미함.
프레임 시작 주소와 합쳐져서, physical address로 변환됨.
■ Address Translation
그러면 실제로 paging 에서 MMU가 logical address가 physical address로 변환하는 과정을 보자.
이 변환을 위해서 참조하는 게 페이지 테이블이다.
ex)
페이징 예시를 살펴보자.
- logical address 크기 : 6 bit
- 한 page size : 4 byte
한 페이지 사이즈가 4바이트 이므로, 2비트로 페이지 오프셋을 표현할 수 있다.
따라서 logical address는 아래와 같이 구성된다.
다음 그림을 보자.
페이지 테이블을 보면, 0번 페이지가 5번 프레임에 위치한 것을 볼 수 있다.
이때 5번 프레임의 시작 주소는 5*페이지 사이즈(4)이므로, physical memory상 20번지에 있는 것을 확인할 수 있다.
※ 참고
한 페이지(또는 한 프레임)내에서는 데이터가 연속적으로 저장되어 있다.
따라서 페이지 내에서의 offset과 프레임 내에서의 offset은 같다.
◆ Page Table Implementation
페이지 테이블은 메인 메모리에 저장되어 있다.
레지스터로 페이지 테이블을 가리킬 수가 있는데,
페이지 테이블의 시작점을 가리키는 base 레지스터, 페이지 테이블의 길이를 가리키는 length 레지스터가 있을 수 있다.
- 각 프로세스는 자신만의 페이지테이블을 갖고 있으므로, base 레지스터는 프로세스마다 달라야 함.
- length 레지스터는 꼭 필요한 건 아님. 다만 프로세스 별로 페이지 사이즈를 다르게 하고 싶다면 필요함.
◆ Translation Look-Aside Buffer (TLB)
페이징 기법에서, 메모리 접근 속도를 높이기 위해서 translation 정보를 미리 캐싱해놓는 기술.
페이징 기법에서는, 결국 페이지 테이블을 읽어서 메모리에 접근해야 하니까, 한 메모리 접근을 위해 또 다른 메모리를 읽어서 접근하는 과정이 필요하다. 그래서 address translation 과정이 그렇게 빠르진 않다.
→ 따라서 이 속도를 높이고자 등장한 것이 TLB.
MMU 안에 있으며, 하드웨어 캐시의 일종이다. 캐시인 만큼 (보통) 크기가 작다.
TLB는 캐시의 address translation 정보(페이지 넘버와 이에 따른 프레임 넘버)를 미리 캐싱해준다.
구체적인 동작 과정을 살펴보자.
- MMU가 페이지가 저장되어있는 메모리에 접근하기 위해, 페이지에 대한 프레임 정보를 알아야 함
- 이때 바로 페이지 테이블에 가는 게 아니라 TLB에 먼저 접근해 봄
- 여기 내가 필요한 페이지에 대한 정보가 있으면(TLB Hit) → 바로 해당 프레임으로 접근할 수 있음
- 여기에 없으면(TLB Miss) → 페이지 테이블로 가야 함. 이때 TLB를 업데이트를 해줌.
페이지 넘버와 프레임 넘버를 TLB에 추가해주어 나중에 찾을 때 좀 더 빨리 찾을 수 있게 해줌.
- 프로세스의 Context Switch 시, 이전 프로세스에 대한 TLB는 초기화가 된다.
단, 프로세스 내 스레드의 Context Switch 시에는 TLB 초기화 안함!
◆ Memory Protection
페이징 기법을 사용할 때, 메모리 보호는 각 프레임 별로 존재하는 Protection bit를 사용해 처리함.
각 프레임이 read-only인지, read-write 접근이 허용되는지, ...를 나타내는 비트.
ex)
예를들어 메모리 공간 중 text 공간의 경우 코드 부분이라 읽기 전용이어야 함.
비트 하나로 페이지가 읽기 전용인지, 읽고 쓰기 둘 다 되는지를 표기해줄 수 있음. 메모리에 접근하려면 결국 페이지 테이블로 들어가 올바른 프레임 넘버를 얻어야 할텐데, 이때 동시에 보호 비트를 확인해서 읽기 전용 페이지인지를 확인할 수 있음. 만약 읽기 전용 페이지를 쓰려고 하는 순간 하드웨어 트랩이 발생하여 운영체제로 보내짐(혹은 메모리 보호 위반).
일반적으로 페이지 테이블에 이런 추가적인 비트에 관한 정보를 추가해줌.
이 비트를 valid-invalid bit라 부름.
그림과 같이 페이지 테이블에 추가적인 비트 하나가 존재해서, 현재 페이지가 valid인지 invalid인지 알려줌.
- valid: 주소가 합법이다. 즉 해당 페이지가 프로세스의 logical address space 범위 내에 있다.
- invalid: 주소가 불법이다. 즉 해당 페이지가 프로세스의 logical address space 범위 내에 없다.
invalid 상태인 페이지에 접근하는 경우 OS에 트랩을 보냄.
◆ Page Table Structure
페이지 테이블을 구조화하기 위한 기술들을 살펴볼 것임.
시스템이 32 비트의 logical address space를 갖는다고 할 때, 페이지의 크기가 4 KB(2^12)라면, 페이지 테이블이 거의 백만 개가 넘는(page offset이 12bit 이므로 page number는 20bit. 따라서 페이지는 2^20개까지 존재 가능) 엔트리를 가질 수도 있음
이때 페이지 테이블의 각 엔트리가 4 바이트 크기라고 가정한다면, 각 프로세스는 페이지 테이블 하나만 해도 최대 4 MB가 필요할 수도 있음...
너무 과함!!!
당연히 메인메모리에 페이지 테이블을 이만큼 연속적으로 할당할 건 아닐 것임.
이걸 해결할 수 있는 간단한 방법으로는 페이지 테이블을 좀 더 작은 부분으로 나누는 것임. 여러 방법으로 나눌 수 있음.
따라서 페이지 테이블을 구조화하기 위한 다양한 기술들이 존재함.
- Hierarchial Paging
- Hashed Page Tables
- Inverted Page Tables
◆ Hierarchial Page Table
logical address space를 여러 단계로 나눈 페이지 테이블
logical address space를 여러 단계로 나눈 것. 이중 포인터의 개념.
예를 들어 위에서 언급한 32 비트 logical address space와 4 KB 페이지 크기를 갖는 시스템의 경우, logical address가 20 비트의 페이지 넘버와 12 비트의 오프셋으로 나뉠 것임.
이젠 여기서 페이지도 페이징을 해줄테니, 페이지 넘버는 10비트의 페이지 넘버와 10비트의 페이지 오프셋으로 나뉨.
여기서 p1가 외부 페이지 테이블로의 index이고 p2가 페이지 내부의 페이지 테이블로의 오프셋임.
다음 그림을 보자.
p1을 사용해 페이지 포인터를 얻고, 여기로 가서 오프셋 p2만큼 따라가면 실제 프레임 넘버를 얻어냄.
이를 통해 실제 프레임에 접근한 후 오프셋 만큼 따라가면 우리가 원하는 데이터가 있다!
※ 64비트 logical address space의 경우, 이 방식은 적절하지 않음
예시를 보자.
- 64비트 logical address space와 4 KB 페이지 크기를 갖는 시스템의 경우, logical address가 52비트의 페이지 넘버와 12 비트의 오프셋으로 나뉠 것임.
- 52 비트면 2^52개의 엔트리까지 가능이라, 너무 과하니까, 2단계로 페이징으로 바꿈. 페이지 테이블을 페이징해주는 것. 그러면 42비트-10비트-12비트.
- 근데 이래도 2^42개까지 가능임. 그러면 3단계로 바꿈. 외부 페이지 테이블을 또 페이징 해주는 것. 32비트-10비트-10비트-12비트
- 이래도.. 아직도 너무 큼... 아무래도 여기서는 부적합한 것 같음 ㅠㅠ
따라서 logical address space 크기가 32비트보다 큰 경우 어떻게 처리할지에 대한 다양한 스킴이 나왔다.
(Hashed Page Table 등.)
◆ Hashed Page Table
Hash Function을 사용한 페이지 테이블.
페이지 넘버를 인풋으로 주고, 이를 해시 함수를 통해 어떤 숫자(해시 값)로 매핑하여 페이지 테이블에 접근하는 방식.
해시 함수에 따라서 충돌(다른 페이지 넘버들이 해시 함수 돌린 결과 같은 숫자로 매핑되는 것)이 있을 수 있으므로, 해결책들을 함께 사용함.
ex) linked list로 저장하는 방식. 한 칸에 여러 개 저장 가능하도록.
여기서 해시 값이 곧 가상 페이지 넘버가 되는 것임.
해시 테이블의 각 엔트리에는 (충돌 처리를 위해) 연결 리스트를 갖고 있음.
각 원소는 세 가지 부분으로 나뉨:
(1) 가상 페이지 넘버
(2) 매핑된 페이지 프레임의 값
(3) 연결 리스트의 다음 원소를 가리키는 포인터.
알고리즘은 다음과 같음:
가상 주소의 가상 페이지 넘버를 해싱하여 해시 테이블에서 찾아봄.
가상 페이지 넘버를 연결리스트의 1번 원소와 비교함.
만약 둘이 같다면 해당하는 페이지 프레임(두번째 원소)를 통해 원하는 물리 주소를 반환함.
만약 같은 원소가 없다면 연결리스트의 다음 원소와 비교함. 이거의 반복임.
◆ Inverted Page Table
원래는 페이지 테이블의 인덱스가 각 페이지 넘버를 나타냈으나, 그걸 반전시킨 거임.
Inverted Page Table에서는 각 인덱스가 프레임 넘버을 나타냄.
원래는 각 프로세스마다 대응하는 페이지 테이블을 하나씩 갖고 있었는데, 그걸 역전시키면?
전체 시스템에서 페이지 테이블이 딱 한개가 있는 거임. 누가 이걸 소유하거나 그런 개념이 아님.
→ 페이지 테이블에 드는 메모리가 크게 줄어듦. 그러나 전체 physical 메모리 공간을 매핑하는 테이블이 존재하는 것이므로, 찾는 데 시간이 오래 걸림.
핵심: 페이지 테이블의 각 엔트리는 pid를 저장한다는 것.
pid를 통해 특정 프로세스의 페이지가 대응하는 프레임에 매핑될 수 있음.
◆ Swapping
메인 메모리 한계가 있을 때, 프로세스를 디스크로 swap out하고 swap in 하는 방식
- Standard swapping: 프로세스가 필요로 하는 메모리 전체를 통째로 메모리↔디스크 왔다갔다 하는 거
- 단점: context switch가 오래걸릴 수 있다.
메모리에 프로세스를 전부 올려놨는데, 그걸 다시 디스크로 보내려면 데이터 카피하는 시간이 오래 걸릴 것
→ 일반적으로 페이지 단위의 스와핑을 함. Page out, Page int
◆ Swapping with Paging
페이지 단위로 메모리↔디스크 왔다갔다 하는 거
- Page out: 메모리 → 디스크
- Page in: 디스크 → 메모리
'CS > 운영체제' 카테고리의 다른 글
| 11. Mass-Storage Structure (0) | 2023.12.05 |
|---|---|
| 10. Virtual Memory (0) | 2023.12.04 |
| 8. Deadlocks (0) | 2023.10.16 |
| 7. Synchronization Examples (0) | 2023.10.16 |
| 6. Synchronization Tools (0) | 2023.10.14 |
