[OS] Paging

프로세서의 메인메모리 할당에 대해, 특정시점에 메인메모리의 빈 공간인 홀에 배치시키다 보니 외부단편화 문제가 발생했었다. 외부 단편화 문제를 해결하기 위한 방법으로 페이징이 있다.



페이징 (Paging)

페이징은 프로세서를 일정한 크기, 페이지 사이즈로 잘라서 메모리에 적재하는 기법이다.
프로세스는 페이지의 집합이고 메모리는 프레임의 집합이다.

cpu와 메인메모리 사이 address를 중재하는 MMU는 base, limit, relocation register로 구성되고, 위는 relocation register 여러개로 구성된 모습이다.
MMU가 여러개의 relocation register로 구성된 것을 page table이라 한다.

현재 여러 프로세서가 실행 및 종료를 반복해 메인메모리에 홀이 흩어져 있는 상태이다.
이 때 하드디스크에서 특정 프로세서를 메인 메모리에 적재하려 하려 하는데, 페이징 기법을 사용하려 한다.
프로세서를 page size로 일정하게 잘랐을 때 각 조각을 page이라 한다.
메인메모리 또한 page size의 page조각이 매핑되어야 하므로 page size로 잘랐을 때 각 조각을 frame이라 한다.

cpu는 주소를 내보내고, 주소가 연속된다 생각하는데, mmu의 relocation register값이 각각 다르므로 각 frame에 더해지는 값이 달라져 메인메모리에 흩어져서 매핑된다. 따라서 cpu가 보았을 땐 프로세서가 메인메모리에 연속적으로 배치되어 있는 것처럼 보이는 효과가 생긴다.
이 때 cpu가 보는 주소를 논리주소(Logical address), 메인메모리가 보는 주소를 물리주소(physical address)라 하며,
mmu = page table을 기준으로 주소의 종류가 달라진다.

page table의 갯수는 해당 프로세서가 몇 개의 page를 사용하는가에 따라 결정된다.
ex) page size = 1kbyte일 때
1k = 2^10이므로 n = 10
프로세서 크기가 8kbyte면 mmu relocation register = 8개



논리 주소 (Logical address)를 물리주소 (Physical address)로 변환하는 방법

논리주소는 cpu가 내보내는 2진수의 주소값이다.
전체 m비트 중 하위 n비트는 displacement(d)이고, 상위 (m-n)비트는 페이지 번호를 의미한다.

물리주소는 페이지 테이블 인덱스값을 의미하는 베이지 번호(p)와 displacement(d)로 구성된다.



논리주소가 50번지일 때 그 주소는 물리주소로 몇 번지인가?

논리주소를 물리주소로 변환하는 과정

1 page는 16바이트이므로 하위 4비트가displacement이다. 나머지 2비트는 page number이다.
1. 논리주소 50번지를 2진수로 변환하면 110010이다.

page number(p)	displacement(d)
(11)2 → (3)10	(0010)2 → (2)10

2. page table의 인덱스 p의 내용 = frame number → 8
메인메모리의 8번째 인덱스로 감

frame number(f)	displacement(d)
(8)10 → (1000)2	(2)10 → (0010)2

따라서 물리주소는 10000010이고 메인메모리의 8번째 인덱스에서 2만큼 떨어진 위치에 적재된다.
메인메모리의 8번째 번지는 128번지이고 2만큼 떨어진 위치는 128 + 2 = 130번지이다.

메인메모리 130번지에 cpu가 보낸 주소 50이 적재되는 것이다.

메인메모리는 page size로 조각조각 흩어져 있는 모습인데, cpu가 보기에는 연속적인 메모리공간에 위치했다고 속이는 것이다.





내부 단편화 (internal fragmentation)페이지 테이블

페이징 기법을 사용해서 외부단편화 현상은 막았지만 내부단편화 현상이 발생했다.
내부단편화 현상에 의한 메모리 낭비는 실제로는 외부단편화보다는 미미하다.

페이지 사이즈로 자른 프로세스 크기가 페이지 크기의 배수가 아니라서 한 조각이 페이지 사이즈보다 작다면, 그 한 조각은 한 프레임을 다 채울 수 없어, 메모리 낭비가 생기는 현상이다.

페이지 테이블

• 페이지 테이블이 cpu레지스터 안에 있다면 → cpu가 내보내는 주소는 페이지 테이블을 경유해 메인메모리로 가는데, 페이지 테이블이 cpu 안에 있다면 주소 변환속도는 매우 빠르다. 하지만 cpu안의 페이지 테이블은 용량이 작다.

• 페이지 테이블이 메인 메모리 안에 있다면 → 메인메모리는 용량이 크므로 페이지 테이블이 아무리 커도 메인메모리가 수용할 수 있다. 하지만 cpu가 주소를 보내면 os 안의 페이지 테이블을 읽어 frame number를 도출하고 frame number에 해당되는 메인메모리 주소로 가서 읽어야 하므로 실행속도는 2배로 느려지게 된다.

• TLB(Translation Look-aside Buffer)에 있다면

주소를 변환하는 목적으로 고속의 SRAM을 사용한다. 원리는 캐시메모리와 같다.
→ cpu에 페이지 테이블이 있을 때보다는 많은 용량을 담을 수 있지만 주소변환속도가 느리고, 메인메모리에 페이지 테이블이 있을 때보다는 적은 용량을 담지만 빠르게 주소변환을 할 수 있다.




보호(Prediction)와 공유(sharing)

보호

cpu에서 내보내진 주소는 페이지 테이블을 모두 경유하므로, 페이지 테이블에 r(read), w(write), x(execute)
3비트를 추가해 해당 페이지에 대한 접근을 제어한다.

r	w	e
1	1	1	read,write,execute가능하다
1	0	0	read만 가능.
0	0	1	execute만 가능

(r,w,e) = (1, 0, 0) 인 상황에서 다른 유저가 내용을 write하여 바꾸려 한다면 페이지 테이블에서 cpu로 인터럽트 신호를 보내게 되고, cpu는 하던일을 멈추고 os의 특정 루틴으로 가서 잘못된 시도를 하려는 프로세스를 강제종료해 프로세스 보호가 이루어진다.



공유

프로그램은 코드, 데이터, 스택으로 구성된다. 하드디스크 내부 pa,pb,pc의 코드가 모두 똑같다면 코드는 중복되고, 메모리는 낭비된다. 따라서 페이지 테이블에 코드영역은 항상 같게 고정시키고 데이터 영역만 달라지도록 하면 메모리를 낭비를 막을 수 있다.
중복되는, 프로세스의 페이지 테이블 코드영역이 같은 곳을 가리키는 코드를 non self modifying code = reentrant code = pure code라 한다.