지난 시간

물리적 메모리의 낮은 주소 영역에 운영체제가 상주하고 그 외 주소 높은 주소 영역단에 프로그램들이 들어와 프로세스가 된다.

연속할당법

• 프로그램을 구성하는 가상메모리 주소공간이 물리적 메모리에 통째로 올라가는 방법을 가정함.
• 메모리 주소 변환이 비교적 간단함. 각각의 프로그램마다 0번지부터 시작하는 가상 메모리 공간을 물리적 메모리의 시작위치만을 더해서 주소변환을 쉽게 할 수 있었음.

불연속할당

• 프로그램을 구성하는 주소공간이 분할되어 메모리 상에 다른 위치로 배분될 수 있는 방식.
• 잘려진 조각 조각이 어디에 존재하는지 어디로 올라가는지를 알아야한다. 그래서 MMU도 두 개의 레지스터만으로 구성될 수 없다.

페이징 기법을 통해 프로세스를 동일 크기의 페이지 단위로 쪼개어 각 페이지마다 주소 변환을 하게한다.

페이지 갯수가 워낙많아서 레지스터만으로는 처리가 어렵다. -> 페이지 테이블을 활용.

---

Paging

프로세스 각각의 메모리 주소공간을 페이지 단위로 잘라서 각각의 페이지가 서로다른 물리적 메모리 공간에 올라갈 수 있게한다. 당장 다 올리는 것도 아니고, 일부 사용할 것만 올리고 나머지는 배킹 스토리지에 일단 두게된다.

같은 크기로 나눈다. -> 프로세스를 구성하는 주소공간도 같은 크기 공간으로 나누는데, 물리적인 메모리도 페이지 하나가 들어갈 공간으로 나눠둔다. 물리적인 메모리의 페이지를 담기 위한 공간을 페이지 프레임이라고 한다. 물리적인 메모리 공간도 4키로바이트로 나눈다.

주소 변환은 페이지 테이블이라는 것을 통해 진행한다. 프로세스를 구성하는 주소공간이 백만개라면, 페이지 테이블에는 백만개의 페이지가 물리적인 메모리 어디에 있는가 주소 변환할 수 있는 기능을 함.

연속할당 기법은 프로그램의 크기가 제각각이어서 외부 조각들이 생성되었으나, 페이징기법은 프로그램을 동일한 크기의 페이지로 쪼갰기 때문에, 공간이 낭비되는 external fragmentation 문제가 발생하지 않는다. (내부조각은 발생 가능하다)

페이지 테이블에 적혀있는 메모리가 꼭 물리적 메모리에 존재하는 것은 아님.
-> 이를 확인하는 것으로 페이지 테이블에는 valid-invalid bit가 존재해서 true, false로 물리적 메모리에 존재하는지를 확인한다.

Implementation of Page table

• Page table의 크기 문제로, 테이블은 메인 메모리에 존재.
• 기존에 존재하던 base register, limit register는 이에 맞게 변화.
  Page table base register(PTBR): page table의 메모리 시작 위치를 가리킴.
  Page table length register(PTLR): 테이블의 크기를 보관
• 모든 메모리 접근 연산에는 페이지 테이블 접근 후 data/instruction메모리 위치 접근을 하기에 두 번의 메모리 access가 필요하다.
• 두 번 메모리에 접근한다는 건 그만큼 느려졌다는 것.
  -> translation look-aside buffer(TLB) 캐쉬메모리를 활용하여 빠르게 처리하도록 한다.

페이지 테이블로 주소 변환을 하지만 테이블의 일부를 TLB에 담아 더 빠르게 처리하도록 한다.

페이지 테이블에선 논리 메모리 주소가 곧 인덱스여서 페이지 테이블을 바로 참조하고 프레임 인덱스를 참조할 수 있었으나, TLB의 경우 페이지 테이블을 일부만을 조각조각 가지고 있기에 논리 메모리 주소를 인덱스를 가지고 접근할 수 없음. 따라서 캐쉬해온 페이지 번호에 상응하는 프레임 번호를 쌍으로 가지고 있어야 되겠다.

TLB에 필요한 주소값이 존재하는지를 확인하려면 일일히 주소값을 확인하는 방법밖에 없다. -> associative register라는 병렬적 확인이 가능한 하드웨어를 이용하여 TLB를 구성 및 탐색한다.

페이지 테이블은 프로세스마다 가지고 있음.
프로세스가 시스템 내 여러개 있다면 테이블 또한 여러개있게 됨.

Associative Register

: parallel search가 가능
-> TLB에는 page table 중 일부만 존재

• Address translation
  page table 중 일부가 associative register 에 보관되어 있음
  만약 해당 page # 가 associative register에 있는 경우 곧바로 frame # 를 얻게 됨.
  그렇지 않다면 메인 메모리에 있는 페이지 테이블로부터 frame # 얻음
  TLB는 context switch 시 flush. (Remove old entries).
  -> 문맥 전환에 큰 오버헤드가 존재한다.

Effective Access Time

• Associative register lookup time = e
• memory cycle time = 1
• Hit ratio = a (associative register에서 찾아지는 비율)

Effective Access Time (EAT)는,
EAT = (1 + e)a + (2 + e)(1-a) = 2 + e - a

캐쉬 적중(1항)의 경우와 캐쉬 미스(2항)의 경우를 합하여, EAT를 얻는다. 일반적으로 a같은 1에 가까운 값을 가진다.

Two-level page table

• 현대 컴퓨터는 address space가 매우 큰 프로그램들을 지원함.
  32비트 운영체제는 0x0 ~ 0xFFFFFFFF까지의 2^32 (4 GB)의 주소 공간이 존재할 수 있고, 페이지 사이즈는 4KB일 때 1M 개의 페이지 테이블 엔트리가 필요하다.

각 페이지 엔트리가 4바이트면 프로세스 당 4M의 페이지 테이블이 필요하나, 대부분의 프로그램은 주소 공간 중 지극히 일부만 사용하므로 페이지 테이블 공간이 심하게 낭비된다.

-> 페이지 테이블 자체를 페이지로 구성
-> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응하는 inner page table이 없음)

그래서 좀 더 효율적 사용을 위해 다단계 페이지 테이블이 나타난다.
-> 선형 페이지 테이블 구조를 트리 구조로 표현.

2단계 페이지 테이블의 경우 페이지 테이블이 두 단계로 구성되어있다.

단계를 거쳐 추가적인 접근을 해야하므로 시간이 늦어지나, 공간적으로 이득이 되어서 사용한다고 함.

계층적으로, 큰 범위 -> 작은 범위 -> 특정 찾고자하는 메모리 주소로 찾아가게끔 한다. 마치 서울시 관악구 @@빌딩 ##호 이런 식으로.

logical address (on 32-bit machine with 4K page size)의 구성.

• 20 bit의 페이지 번호
• 12 bit의 페이지 오프셋

페이지 테이블 자체가 페이지로 구성되기 때문에 페이지 번호는 다음과 같이 나뉜다. (각 페이지 테이블 엔트리가 4B)
-> 10 bit page number.
-> 10 bit page offset.

P1 은 outer page table의 인덱스이고, P2는 outer page table의 page 에서의 변위.

더욱 많은 단계의 페이지 테이블을 사용한다.
공간은 크게 절약할 수 있게 된다. 대신 시간이 오래 걸림. 주소 변환을 위해 단계별로 메모리 접근을 해야하기 때문

Memory Protection

• Page table 의 각 엔트리 마다 아래의 비트를 둔다.

Protection bit : page에 대한 접근 권한 (read/write/read-only)
Valid-invalid bit : 해당 주소의 프레임에 그 프로세스를 구성하는 유효한 내용이 있고 없고를 나타냄.

• 유효한 페이지를 찾아갈 수 있도록 비트를 활용하여 정보를 제공하는 것이다.