Paging
: 프로그램을 구성하는 논리적인 메모리를 동일한 크기의 페이지로 잘라서 각각의 페이지 별로 물리적인 메모리에 어디든지 비어있는 위치에 올라갈 수 있게 하는 방법
Paging기법에서 주소 변환을 위해서 page table이 사용된다. 각각의 논리적인 페이지들이 물리적인 메모리에 어디에 올라와있는가 논리적인 페이지도 페이지 번호를 매기고
물리적인 메모리에서 페이지가 들어갈 수 있는 공간을 페이지 프레임이라고 한다.
Address Translation Architecture
CPU가 논리적인 주소를 주게 되면 물리적인 메모리상에 주소로 바꿔야 한다.
Implementation of Page Table
-
Page table은 main memory에 상주
-
Page-table base register(PTBR)가 page table을 가리킴
-
Page-table length register(PTLR)가 테이블 크기를 보관
-
모든 메모리 접근 연산에는 2번의 memory access 필요
-
page table 접근 1번, 실제 data/instruction 접근 1번
-
속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용
Two-Level Page Table
-
현대의 컴퓨터는 address space가 매우 큰 프로그램 지원
*32bit address사용시 232(4G)의 주소 공간
- page size가 4K시 1M개의 page table entry 필요
- 각 pahe entry가 4B시 프로세스 당 4M의 page table 필요
- 그러나, 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table공간이 심하게 낭비됨
-> page table 자체를 page로 구성
-> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL(대응하는 inner page table이 없음)
page Table을 두단계 거쳐서 주소변환을 하고 실제로 메모리 접근을 하게 된다.
왜 이런 방식을 사용하는가?
1. 속도를 빠르게 하던지
2. 공간을 줄이던지
(속도는 줄어들지 않는다. 두 번 접근하니 시간은 더 걸림 속도는 줄어들지 않는데 페이지테이블을 위한 공간이 줄어드므로 2단계 페이지 테이블을 사용한다.)
Multilevel paging and Performance
- Address space가 더 커지면 다단계 페이지 테이블 필요
- 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
- TLB를 통해 메모리 접근 시간을 줄일 수 있음
- 4단계 페이지 테이블을 사용하는 경우
- 메모리 접근 시간이 100ns, TLB 접근 시간이 20ns이고 TLB hit ratio 가 98%인 경우 effective memory access time = 0.98 x 120 + 0.02 x 520 =128nanoseconds 결과적으로 주소변환을 위해 28ns만 소요
Memory Protection
- Page table 의 각 entry 마다 아래의 bit을 둔다.
*Protection bit
page에 대한 접근 권한]
*Valid-invalid bit
"valid"는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함(접근 허용)
"invalid"는 해당 주소의 frame에 유효한 내용이 없음을 뜻함(접근 불허)
Inverted Page Table
-
page table이 매우 큰 이유
- 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
- 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재 -
Inverted page table
Page frame 하나당 page table에 하나의 entry를 둔 것(system-wide)
각 page table entry는 각각의 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address)
단점 : 테이블 전체를 탐색해야 함
조치 : associative register 사용(expensive)
Shared Page
-
Shared code
- Re-entry Code(=Pure code)
- read only로 하여 프로세스 간에 하나의 code만 메모리에 올림(eg, text editors, compilers, window systems)
- Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함 -
Private code and data
- 각 프로세스들은 독자적으로 메모리에 올림
- Private data는 logical address space의 아무곳에 와도 무방
공유할 수 있는 코드는 같은 코드로 매핑을 시켜서 메모리에 한 카피만 올린다.
Segmentation
: 프로세스를 구성하는 주소 공간을 의미 단위로 쪼갬
-
프로그램은 의미 단위인 여러 개의 segment로 구성
작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
* 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨 -
Segment는 다음과 같은 logical unit들임
main(), function, global variables, stack, symbol table, arrays -
Logical address는 다음의 두 가지로 구성
<segment-number, offset> -
Segment table
* each table entry has:
- base : starting physical address of the segment
- limit : length of the segment -
Segment-table base register(STBR)
* 물리적 메모리에서의 segment table의 위치 -
Segment-table length register(STLR)
* 프로그램이 사용하는 segment의 수
segment number s i legal fi s < STLR
Segmentation Architecture(Cont.)
-
Protection
- 각 세그먼트 별로 Protection bit가 있음
- Each entry:
valid : bit = 0 => illegal segment
Read/Write/Execution 권한 bit -
Sharing
shared segment
same segment number
** segment는 의미 단위이기 때문에 공유(sharing)와 보안(protection)에 있어 paging보다 훨씬 효과 적이다. -
Allocation
first fit / best fit
external fragmentation 발생
** segment의 길이가 동일하지 않으므로 가변분할 방식에서와 동일한 문제점들이 발생
Allocation of Physical Memory
-
메모리는 일반적으로 두 영역으로 나뉘어 사용
OS 상주영역
interrupt vector와 함께 낮은 주소 영역 사용
사용자 프로세스 영역
높은 주소 영역 사용 -
사용자 프로세스 영역의 할당 방법
Contiguous allocation
: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것
#Fixed partition allocation
#Variable partition allocation
Noncontiguous allocation
: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음
#Paging
#Segmentation
#Paged Segmentation
Segmentation with Paging
세그먼트 하나가 여러 개의 페이지로 이루어져 있다.
