앞서
사용자 프로세스 영역의 할당 방법
- Contiguous allocation
- 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
- Fixed partition allocation, Variable partition allocation
- Noncontiguous allocation
- 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
- Paging, Segmentation, Paged Segmentation
이번 포스팅은 불연속 할당 기법 내용을 다룰 예정이다.
Paging
- Process의 virtual(logical) memory를 동일한 사이즈의 page 단위로 나눈다.
- Virtual memory의 내용이 page 단위로 noncontiguous하게 저장된다.
- 일부는 Backing store에, 일부는 Physical memory에 저장된다.
- External fragmentation이 발생하지 않는다.
- Internal fragmentation 발생 가능하다. (But loss가 그렇게 크지 않다)
필요 조건
논리 주소 공간과 물리 주소 공간의 분리 : 주소의 동적 재배치를 허용한다.
전용 하드웨어 (MMU) : 논리 주소와 물리 주소의 변환
Basic Method
- Physical memory를 동일한 크기의 frame으로 나눈다.
- Logical memory를 동일한 크기의 page로 나눈다. (== frame과 같은 크기)
- 모든 가용 frame 등을 관리한다. (비어있는 frame의 리스트 위치 등)
- page table을 사용하여 logical address를 physical address로 변환한다.
- page table은 main memory에 상주한다.
프로세스를 나눈 조각을 page 라 하고, 메모리를 나눈 조각을 frame 이라 한다.
프로세스는 페이지의 집합이고, 메모리는 프레임의 집합이다. 프로세스를 정상적으로 사용하기 위해 MMU의 재배치 레지스터를 여러개 사용해서 위의 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이러한 여러 개의 재배치 레지스터를 페이지 테이블(Page Table) 이라 한다.
주소 변환 Schema
CPU는 2가지로 구성된 virtual address를 사용한다.
- Page Number (p)
- page table의 index로 사용한다.
- 해당 index에는 그 페이지의 물리적 메모리 상의 base address가 저장된다.
- Page Offset (d)
- base address와 더해져서 physical address가 구해진다.
CPU는 Page Number와 Page Offset만 알면 된다. (Base Address 알 필요 X)
페이지 테이블의 페이지 번호 p 위치에 있는 f 값이 물리 메모리 페이지 번호이다.
또한 f는 실제 메모리의 페이지 기준 주소로 메인 메모리의 프레임 번호이다.
기준 주소 (f)에 페이지 offset(d)가 더해져서 실제 메모리 주소가 결정된다.
- Page Table은 메인 메모리에 상주한다.
- Page-Table Base Register(PTBR)가 page table을 가리킨다.
- Page-Table Length Register(PTLR)가 테이블 크기를 보관한다.
- 모든 메모리 접근 연산에는 2번의 memory access가 필요하다.
- page table 접근 1번, 실제 data/instruction 접근 1번
- 속도 향상을 위해 TLB라고 불리는 고속의 lookup hardware cache 사용한다.
TLB
- Associative registers (TLB) : parallel search가 가능하다.
- TLB에는 page table 중 일부만 존재한다.
- Address Translation
- page table 중 일부가 TLB에 보관되어 있다.
- 만약 해당 page number가 TLB에 있는 경우 곧바로 frame number를 얻는다.
- 그렇지 않은 경우 메인 메모리에 있는 page table로부터 frame number를 얻는다.
- TLB는 context switch 때 flush 한다. (remove old entries)
- Effective Access Time (EAT)
- (e + 1) * a + (e + 2)(1 - a) = 2 + e - a
- a : Hit ratio
- e : TLB lookup time
- 1 : memory access(cycle) time
- 2 : page table access time + memory access time
Two-Level Page Table
페이지 테이블 자체가 다시 페이징이 되는 것이다.
현대의 컴퓨터는 기본적으로 32 or 64 bit address를 사용하므로 주소 공간이 매우 큰 프로그램을 지원한다.
- 32 bit address 사용 시 : 2^32 = 4GB (GB = 1024^3 바이트에 해당)
이를 size가 4K인 page로 나누면 약 1M개의 페이지로 나뉘어진다. 그러면 logical -> physical address로 주소 변환하는 매핑 정보를 담고 있는 page table entry 개수는 100만 개가 되어야 한다. (가상 주소 공간에서의 하나의 페이지는 하나의 PTE(Page Table Entry)를 가진다.)
32bit 컴퓨터 이므로 page entry 하나당 32bit 주소 체계를 가지게 되어 4B가 할당되므로 프로세스당 4B X 1M = 4MB 크기의 page table을 가지게 된다. 그런데 이 page table은 프로그램이 메모리에 올라갈 때 physical memory에 할당된다. 그래서 physical memory의 주소 공간 낭비가 발생한다.
이러한 낭비 문제를 해결하기 위해 page table entry 정보를 가지고 있는 page table을 하나 더 만드는 기법인 Two-Levl Page Table이 나왔다.
inner page table(page of page table)이 원래 page table(outer page table)의 entry 1개를 각각 다시 page로 나눈 page table들을 가지고 있는 table이다.
즉, inner page table 1개는 outer table의 page 크기인 4KB의 크기를 갖게 된다. 또한 inner page table 역시 entry의 크기는 4B일 것이므로 table 당 1K(1000(2^10과 비슷))개의 entry를 가지게 된다.
2개의 page table을 사용할 때 속도는 줄어들지 않는다. 2번의 접근으로 속도가 늘어날 수 있다. 하지만 프로그램의 메모리는 상용하지 않는 공간이 많은데, 이 공간들에 대해 outer page table이 가리키는 inner page table 값을 NULL로 설정할 수 있다.
그 결과 많은 메모리 공간 값들이 NULL을 가리키게 되어 page table을 사용하는 공간이 줄어들게 된다. (낭비 문제 해결)
Multilevel Paging
Address space가 더 커진다면 다단계 페이지 테이블이 필요하다.
문제는 주소 변환 시 더 많은 메모리 접근이 필요하게 되어 소요 시간이 길어질 수 있는데 이는 캐시 메모리(TLB)를 통해 메모리 접근 시간을 줄일 수 있다.
Memory Protection
Page table의 각 entry마다 아래의 bit를 둔다
Page table entry
logical -> physical address로 주소 변환하는 매핑 정보를 담고 있다.
- Protection bit
page에 대한 접근 권한 (read / write / read-only) - Valid-invalid bit
- valid : 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있다 (접근 허용)
- invalid : 해당 주소의 frame에 유효한 내용이 없음 (접근 불허)
- 프로세스가 그 주소 부분을 사용하지 않는 경우
- 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우
쓰지 않는 page는 0으로 표시 & invalid flag
Inverted Page Table
- Page table이 매우 큰 이유
- 모든 프로세스 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재한다.
- 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재한다.
Page table의 가장 큰 문제는 모든 프로세스가 크기만큼 page table을 가져야 하고, 그 page table은 메모리 영역에 저장되어 공간이 낭비된다.
이를 해결하기 위한 기법이 Inverted Page Table이다.
이 방법은 시스템 안에 page table이 딱 1개만 존재하고, entry가 프로세스 기준이 아닌 물리적 메모리의 frame 개수만큼 존재한다.
- Page frame 하나당 page table에 하나의 entry를 둔 것 (system-wide)
- 각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용을 표시한다. (PID, process의 logical address), 반대로 물리 메모리의 어느 위치에 저장되어야 하는지는 frame의 index 정보로 알 수 있다.
- 주소 변환을 해야 할 경우, CPU는 논리 주소의 pid와 p와 맞는 entry를 찾아내기 위해 page table을 모두 탐색하고, 찾으면 찾은 index 정보를 가지고 frame 번호를 알아내어 pid와 p를 i로 바꿔준다. (d(offset)는 그대로)
- 단점 : 테이블의 모든 entry를 탐색해야 한다.
- 해결 : Associative Register (Cache) 사용 (but 비쌈)
Shared Page
- 몇몇의 프로세스들이 Shared code( = Re-entrant code = Pure code ) 를 가질 경우 하나의 code 부분 page만 메모리에 올려 공유하는 방법이다. (ex. text editors, compilers, window systems)
- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 한다.
- cf) 각 프로세스들은 독자적으로 메모리에 올리고, private data는 logical adress space의 아무 곳에 와도 무방하다.
Segmentation
프로그램은 의미 단위(code, data, stack)인 여러 개의 segment로 구성
페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하였다. 여기서 물리적인 것은 말 그대로 프로세스를 일정한 크기로 자른 것이다. 반면에 세그먼테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하는 것을 말한다.
- 작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
- 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
- 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의된다.
- Logical Address 구성 : segment-number, offset
- Segment table
사용자가 정의한 주소를 실제 주소로 매핑하는 정보를 저장하고 있고, 각 세그먼트 항목별 Base(세그먼트 시작 주소)/Limit(세그먼트 길이)의 정보를 가지고 있다.- base : 세그먼트 시작하는 physical address
- limit : 세그먼트 길이
- STBR(Segment-table base register) : 물리적 메모리에서의 segment table 위치
- STLR(Segment-table length register) : 프로그램이 사용하는 segment의 수
- segment number s is legal if s < STLR
각각의 세그먼트들은 비슷한 성질의 데이터이기 때문에 이들이 가지는 속성에 대해 테이블을 마련해줌으로써 서로 다른 세그먼트 참조 시에 그들에 대한 권한을 통제할 수 있다.
- segment number s is legal if s < STLR
- Protection
- 각 세그먼트별로 protection bit가 있다.
- Each entry : Valid/Invalid bit, Read/Write/Execution 권한 bit
- Sharing : shared segment, same segment number
- segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과적이다.
- Allocation : first fit/best fit, external fragmentation 발생
- segment 길이가 동일하지 않아서 가변분할 방식에서와 동일한 문제점 발생
