Non-continuous allocation
- 사용자 프로그램을 여러 개의 block을 분할
- 실행 시, 필요한 block들만 메모리에 적재
-> 나머지 block들은 swap device에 적재
- 기법들
ㆍPaging System
ㆍSegmentation System
ㆍHybrid Paging / Segmentation System
Continuous allocation
- Relative address (상대주소)
ㆍ프로그램의 시작 주소를 0으로 가정한 주소
- Relocation (재배치)
ㆍ메모리 할당 후, 할당된 주소(allcation address)에 따라 상대 주소들을 조정하는 작업
Address Mapping
Non-continuous allocation
- Virtual address (가상주소) = relative address
ㆍLogical address (논리 주소)
ㆍ연속된 메모리 할당을 가정한 주소
- Real address (실제주소) = absolute (physical) address
ㆍ실제 메모리에 적재된 주소
- Address mapping
ㆍVirtual address -> real address 작업을 address mapping이라고 한다.
Non-continuous allocation의 경우, 실제 주소가 연속적이지 않음에도 불구하고, 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행 할 수 있음.
Block Mapping
- 사용자 프로그램을 block 단위로 분할/관리
ㆍ 각 block에 대한 address mapping 정보 유지
- Virtual address : v = (b,d)
ㆍ b = block number
ㆍ d = displacement (offest) in a block
- Block map table (BMT)
ㆍ Address mapping 정보 관리
-> Kernel 공간에 프로세스마다 하나의 BMT를 가짐
-> Residence bit : 해당 블록이 메모리에 적재되었는지 여부 (0/1)
/* block 단위로 분할/관리한다고 되어있는데, 이는 단일 주소만 관리하는 것인가 아니면 real address의 집합을 하나의 블록 주소가 관리하는 것인가? */
Block Mapping의 흐름은 다음과 같다.
1. virtual address는 (b, d)로 구성되어있다.
2. b로 block number를 찾아서, 이 주소가 할당받은 주소인지 검사한다. (residence bit의 True / False 검사)
3-1. 만약 할당받은 주소가 있다면, (residence bit = True)b에 해당하는 real address (a)를 찾는다.
3-2. 만약 할당받은 주소가 없다면, (residence bit = False) swap device에서 해당 블록을 메모리로 가져온다.
4. 실제 메모리는 a에서 d만큼 떨어진 곳이므로, a+d 로 실제 주소 (r)를 찾는다.
Paging System
- 프로그램을 같은 크기의 블록으로 분할 (Pages)
- Terminologies
ㆍPage
-> 프로세스를 분할하고, 분할한 것중 하나를 Page라고 부른다.
ㆍPage Frame
-> 메모리의 분할 영역
->Page와 같은 크기로 분할
- Page와 Page Frame의 차이 : Page는 '프로세스'를 분할한 것이고, Page Frame은 '메모리'를 분할하여, Page를 넣은 곳을 말한다.
Paging System의 특징
- 논리적 분할이 아님 : 크기에 따른 분할
ㆍPage 공유 (Sharing) 및 보호 (Protection) 과정이 복잡함
-> 예를 들어, 프로세스를 function 단위로 분할한다면 논리적 분할이 되겠지만, Paging system은 몇 줄씩 끊어버려서 나눠버리는 것이다.
-> Segmentation 대비
ㆍSimple and Efficient
-> Segmentation 대비
ㆍNo external fragmentation
-> Page와 Page Frame은 같은 크기를 유지하기 때문에, Page Frame의 총 여유 공간이 충분한데, Page가 못 올라가는 경우는 없다.
-> Internal fragmentation 발생 가능
/* 하지만, Internal fragmentation이 발생한다면, External Fragmentation이 발생할 수 있지 않는가? */
Address Mapping
- Virtual Address : v = (p,d)
ㆍp : page number
ㆍd : displacement (offset)
- Address Mapping
ㆍPMT (Page Map Table) 사용
-Address Mapping Mechanism
ㆍDirect mapping (Block mapping과 거의 유사)
ㆍAssociative mapping
ㆍHybird direct / associative mapping
PMT에서 page frame을 찾는 흐름
1. page number를 가져온다.
2. page number에 데이터가 담겨있는지 살펴본다. (residence bit == True 체크)
3. residence bit가 True라면, swap device의 어느 영역에 있는지 본다. (secondary starge address)
/* secondary ~ otherfiled는 다단계 페이징 기업에서 page와 page frame number 사이에 있는 pml4, 디렉터리 포인터, 디렉터리 등을 의미하는 것일까? */
4. 그리고 page frame number를 가져온다.
Direct Mapping
- Block mapping 방법과 유사하다.
ㆍPMT를 커널 안에 저장
ㆍPMT entry size = entrySize (그림 4에서 page 한 개의 크기를 말한다.)
ㆍPage size = pageSize (그림 4에서 page frame 한 개의 크기를 말한다.)
1. virttual address가 (p, d)라고 해보자. 그리고 PMT base address를 알고 있다고 해보자.
2. p는 page number를 의미하므로 b에다가 p*page entry size를 더하면, page frame number (p`)가 적혀져 있는 주소를 찾을 수 있다.
3. 여기에 p` * pageSize를 하면, 원하는 주소가 있는 블록의 시작 위치를 알 수 있고, 여기서 displacement인 d를 더하면 우리가 찾길 원하는 실제 주소값 (r) 을 알 수 있다.
※ residence bit가 0인 경우, page fault가 일어나게 되고, swap device (Disk IO) 에서 해당 page를 메모리로 적재한다.
※ Page Fault 를 최대한 피해야하는 이유 : Page Fault라는 것은, 원하는 page가 실제로 존재하지 않고, Page Fault가 일어나게 되면, 디스크에서 해당 page를 메모리로 적재해야한다. 그런데, running 중인 thread가 추가적인 자원을 필요로 하게 될 때, 자원을 할당받을 때까지 작업을 block한 후, sleep 상태로 대기한다. 이 때, context switching이 일어나게 되고, 부하(overhead)가 높아지게 된다.
즉, Page Fault는 thread를 running에서 block으로 보내고, 이에따라 context swtiching을 야기시키며 overhead를 높이게 된다. (firecatlibrary.tistory.com/49 참조)
-> 가상 메모리 시스템에서는 최대한 Page Fault를 줄이는 것이 중요하다!
Direct Mapping의 문제점
- 메모리 접근 횟수가 2배가 된다. (main memory (kernel) 에 있는 PMT 에서 한번 찾고, 다시 main memory에 있는 실제 주소를 찾는다.)
-> Associative mapping (TLB)를 사용하여 메모리 접근 횟수를 줄인다.
- PMT를 위한 메모리 공간이 필요하다.
-> Dedicated register나 cache memory를 사용한다.
Associative Mapping
- TLB (Translation Look-aside Buffer)에 PMT 적재
ㆍTLB : PMT를 탐색하기 위한 전용 하드웨어
-> TLB에서는 page를 하나하나 탐색하는 것이 아니라 병렬로 페이지등을 동시에 탐색가능하다.
ㆍAssociative high-speed memory
- PMT를 병렬 탐색
- Low overhead, high speed : Memory Access에서 소모되는 시간을 단축할 수 있다.
- 매우 비싼 하드웨어이다. -> 용량이 제한됨 -> 큰 PMT를 다루기가 어렵다.
Hybrid Direct / Associative Mapping
- 두 기법을 혼합하여 사용한다.
- 작은 크기의 TLB 사용
ㆍPMT : 메모리 (커널 공간)에 저장한다.
ㆍTLB : PMT 중 일부 entry들을 적재 : 그렇다면 어떤 entry를 TLB에 적재할 것인가?
-> 최근에 사용된 page들에 대한 entry 저장
ㆍLocality (지역성) 활용
-> 프로그램의 수행과정에서 한번 접근한 영역을 다시 접근하거나 인접 영역을 다신 접근할 가능성이 높다.
- 프로세스의 PMT가 TLB에 적재되어 있는지 확인한다.
1) TLB에 적재되어 있는 경우 : Residence bit를 검사하고 page frame 번호 확인
2) TLB에 적재되어 있는 않는 경우 : Direct mapping으로 page frame 번호를 확인하고, 해당 PMT entry를 TLB에 적재한다.
Frame Table
- Page frame 당 하나의 entry
- 구성 :
ㆍAllocated / available field : 해당 entry가 할당되어 있는가?
ㆍPID field : 어떤 page가 올라와있는가? (PID : Process ID)
ㆍLink field : 할당받지 않은 entry를 묶어놓은 list (사용가능한 fp들을 연결) :
ㆍAV : Free list header (free list의 시작점)
Page Sharing
- 여러 프로세스가 특정 page 공유 가능하다.
- 공유 가능 page
1) Procedure pages
ㆍPure code (코드의 함수 등이 해당된다.)
2) Data page
ㆍRead-only data
ㆍRead-write data (Mutex나 Semaphore 등으로 병행성을 관리해줘야한다.)
그림 8은 한 Page를 여러 프로세스가 공유해서 사용하는 것의 예제이다.
각 프로세스는 ed라는 프로그램을 공유해서 사용하고 있고, ed는 ed1~3으로 나눠져있다. (단, 각 프로그램을 위한 데이터는 각각 다른 것이 보인다.) ed1~3는 page table에 올라와있는 번호가 같은데 이는 같은 memory의 주소를 참조하고 있기 때문이다. 이를 page sharing이라고 한다.
그림 9-1의 경우, page table에서의 page number는 다르지만 (k1과 k2) 같은 page frame (p`)를 참조하고 있다. P1을 참고하여 p`에 접근하려면, virtual address는 (k1, d)가 되고, P2를 참고하여 p`에 접근하려면 virtual address가 (k2, d)가 되버리는 문제가 일어난다.
이를 방지하기 위해, 다른 프로세스라도 같은 page frame을 참조하고 있으면, PMT에도 같은 page number를 부여한다.
Page Protection
여러 프로세스들이 page를 공유한다면, 보안적인 문제가 일어날 수 있다. (어떤 프로세스가 임의로 page frame에 있는 내용을 변질시켜 버릴 수 있다.) 이 때문에, 프로세스들에게 각각 다른 접근 권한을 부여함으로서 보안성을 향상할 수 있다.
'Pintos Project > 이론 공부' 카테고리의 다른 글
| [PintOS, Project 3] Virtual Memory Management - Cost Model / HW Components (0) | 2021.02.18 |
|---|---|
| [PintOS, Project3] Virtual Memory - Segmentation System (1) | 2021.02.18 |
| Lecture 5 : Process Scheduling (0) | 2021.01.30 |
| Lecture 4 : 스레드 관리 (Thread Management) (0) | 2021.01.29 |
| Lecture 3 : 프로세스 관리 (0) | 2021.01.29 |
댓글