[week09] KOCW 운영체제(반효경교수님) - Memory Management 2

Memory Management 2

Paging

paging

프로세스의 virtual memory를 동일한 사이즈의 page 단위로 나눔

virtual memory의 내용이 page 단위로 noncontiguous(불연속)하게 저장됨

일부는 backing storage에, 일부는 physical memory에 저장

Basic Method

physical memory를 동일한 크기의 frame으로 나눔

logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)

모든 가용 frame들을 관리

page table을 사용하여 logical address → physical address로 변환

External fragmentation 발생 안함, Internal fragmentation 발생 가능

Address Translation Architecture

CPU가 logical memory를 주면 physical memory로 변경해야 한다.

주소에서 앞부분이 page 번호(p), 뒷부분이 page에서 얼만큼 떨어진지 나타냄(d)

상대적인 위치 d는 바뀌지 않고 p가 f로 바뀐다.

Implementation of page table

page table의 용량이 굉장히 크다(register에 들어갈 수 없음). 이걸 어디에 저장할 것인가?

page table은 main memory에 상주한다.

page table은 각각의 프로세스별로 존재한다.

사용되는 registers

• Page-table base register(PTBR)가 page table을 가리킴
• Page-table length register(PTLR)가 table 크기를 보관

모든 메모리 접근 연산에는 2번의 memory access가 필요하다.

• page table 접근 1번(주소변환을 위해), 실제 data/instruction 접근 1번

두번 접근하면 속도가 느리고, 속도 향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용

Paging Hardware with TLB

TLB라는 별도의 hardware를 사용한다(main memory보다 접근속도 빠름).

주소변환을 위한 별도의 cache이다.

page table에서 빈번히 참조되는 entry를 caching하고 있다(page table 중 몇개만 가지고있음).

CPU가 logical memory를 주게 되면 main memory 상의 page table을 접근하기 전에 TLB를 먼저 검색한다.

TLB는 page table과 달리 전체를 다 검색해야 하므로 속도가 느려질 수 있다. → parallel search가 가능하게 함(associative registers)

TLB의 정보는 context switch가 발생할 때 flush(모든 entry를 비움)

• 프로세스마다 page table이 다르고, TLB도 다르기 때문

Two-level page table

32bit address 사용시 2^32(4GB)의 주소공간(logical memory)을 가짐

( 2^10 = KB, 2^20 = MB, 2^30 = GB )

하나의 page size가 4KB라고 하면, logical address는 (4GB / 4KB)이므로 1M개의 page로 나뉘어 진다. 그렇기 때문에 logical address를 physical address로 주소변환하는 page table의 entry 개수도 1M개가 되어야 한다. page table은 index를 가지고 mapping하기 때문에 중간에 빼먹을 수 없기 때문이다.

각 page entry가 4B일 때 page table entry 개수인 1M개를 곱하면 page table은 4MB의 크기를 가지게 된다.

그러나, 대부분의 프로그램은 4G의 주소공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비되는 문제가 발생한다.

해결책

page table 자체를 page로 구성

사용되지 않는 주소 공간에 대한 outer page table의 entry 값은 NULL(대응하는 inner page table 없음)

Two-level page table Example

Address-Translation scheme

d는 위에서부터 몇 번째 주소인지 구분하는 숫자이다(byte단위).

하나의 page의 크기는 (4KB) 2^12 byte 이다.

byte 단위에서 주소 구분을 하려면 몇bit가 필요할까?

page offset bit는 12개가 필요하다.

P2는 page table에서 위에서부터 몇 번째 entry인지 구분하는 숫자이다.

안쪽 page table의 크기는 page table과 같은 4KB이다.

page table의 entry 하나 크기는 4Byte이다.

따라서 안쪽 page table에 들어가는 entry의 개수는 1K개이다.

따라서 1K의 위치를 구분하기 위해서 P2는 10bit가 필요하다.

32bit에서 12bit, 10bit를 뺀 나머지인 10bit가 P1에 할당된다.

2단계 page table을 사용하는 이유

2단계 page table을 사용하는 이유는 시간은 더 걸리더라도 page table을 위한 공간을 줄여주기 위함이다.

그런데 뭔가 이상하지 않는가?

여전히 안쪽 table page는 1M개가 필요하다. 오히려 바깥쪽 page table이 하나 더 만들어지기 때문에 1단계 page table을 쓰는 것 보다 공간적으로도 손해이다...!

그럼 시간도 손해, 공간도 손해 그럼 이거 왜 쓰지?

프로그램을 구성하는 공간 중에서 상당 부분은 사용되지 않는다. 그런데 page table로 만들 때는 사용되지 않는 공간에 대한 entry도 모두 만들어야 한다. k번째 page을 주소변환하려면 위에서부터 접근해서 몇 번째인지 찾아야 하는데 entry가 없으면 못찾으니까. 결국 maximum logical memory의 크기만큼 page table이 만들어져야 한다.

2단계 page table을 쓰면 이걸 해소할 수 있다.

바깥쪽 page table은 전체 logical memory 크기만큼 만들어 지지만 실제로 사용되지 않는 부분의 안쪽 page table은 만들어지지 않고 포인터가 NULL 상태로 되어있다.

사용되지 않는 부분이 정말 많기 때문에 2단계 page table을 사용하는 것이 효과적이다.