Memory system

간단하게 CS:APP의 연습문제 9.4번을 풀면서 메모리, 캐시, 가상 메모리에 대해 정리해보려 한다.

문제 가정

작은 메모리 시스템에 대한 TLB, 페이지 테이블, 캐시

문제에서 주어진 것 처럼 Virtual address가 0x03d7일 때 시스템이 어떻게 가상 주소를 물리 주소로 번역하고, 캐시를 접근하는지를 보겠다.

주어진 가상 주소를 bit 형태로 써보면 00 0011 1101 0111 이고, 여기서 TLB에 접근하기 위해 태그와 인덱스를 구해보면, 주어진 문제에서 4개의 집합을 가지니, VPN(0x0F)의 2개 하위 비트들이 집합 인덱스(TLBI)(0x03)로 사용되고, 나머지 6개의 상위 비트들은 태그(TLBT)(0x03)로 사용된다. 여기서 VPO(0x17)는 페이지의 크기가 2^6 =64바이트 이기 때문에, 하위 6비트에 해당하고 PPO 또한 물리 메모리에서 하위 6비트를 가리킨다. 이에 따라 VPN은 상위 (14-6) =8 비트이고, PPN은 상위 (12-6)=6비트가 된다. 캐시는 직접 매핑을 가정한다. 가정에서 블록 사이즈를 2^2 =4byte로 설정했으므로 물리 주소 하위 2비트는 블록 오프셋(CO)으로 사용됨. 16개의 집합이 있다 하였으니 2^4 이므로 4비트는 집합 인덱스(CI)로 사용된다. 나머지 상위 6비트는 태그로 사용한다.

---

주어진 문제로 다시 돌아와서 주소 번역 흐름을 알아보자. CPU가 가상 주소 0x03d7을 읽는다. 먼저 MMU는 VPN(0x0 F)을 가상 주소에서 뽑아내고, TLB와 비교해서 이전의 메모리 참조로부터 PTE 0x0F의 사본을 캐싱한 적이 있는지 알아본다. TLB는 TLB인덱스(0x03)와 TLB tag(0x3)를 VPN으로부터 추출해서 집합 0x3의 두 번째 엔트리에서 유효한 매칭을 찾고 캐시 된 PPN(0x0 D)를 MMU로 보낸다.

만일 TLB가 미스했다면 MMU는 PTE를 메인 메모리에서 가져올 필요가 있었을 것이다. MMU는 이제 물리 주소를 구성하는 데 필요한 모든 것을 얻었다.  물리 주소는 가상 주소의 VPO(0x14) 와 PTE로부터 PPN(0x0 D)를 연결해서 얻으며, 그 결과 물리 주소(0x357)를 구성한다. 다음으로 MMU는 물리 주소를 캐시로 보내고, 캐시는 오프셋 CO(0x3), 캐시 집합 엔덱스 CI(0x5), 캐시 태그 CT(0x0 D)를 물리 주소에서 추출한다. 5번째 idx의 태그가 일치하여 캐시는 hit 되고 데이터 바이트 0x1D를 오프셋에서 읽어서 이걸 MMU로 리턴하고 MMU는 다시 이걸 CPU로 전달한다.

위와 같은 경우는 번역 과정 모든 곳에서 hit가 났지만, 다음과 같은 예외가 있을 수 있다.

• 방금 같은 경우에 TLB에서 miss 나지 않아도 cache에서 miss가 나서 메인 메모리로 가져 올 수 있다.
• 최악의 경우에는  TLB에서 miss가 나서 page table에서 새로운 매핑 정보를 가져오려 했는데, valid 가 0이라서 page fault가 난 경우. 디스크에서 가져와야 한다.

위에서 말한 page fault가 일어난 경우 디스크에서 해당 데이터를 읽어 메모리를 업데이트하고, 그 메인 메모리에 대한 매핑 정보를 page table에 업데이트해준다. 그리고 그 정보를 TLB에 써주고 다시 접근 시도를 해준다.

 

여기까지가 간단한 메모리 시스템의 주소 번역 과정이다.

---

 

페이지 폴트 관련하여 생각난 것을 적어 보려 한다.

쓰레싱이라는 개념이 있는데, 멀티프로그래밍 degree를 높이기 위해서  CPU이용률이 떨어질 때 새로운 프로세스를 추가할 때 생길 수 있는 문제이다.

프로세스가 실제로 사용하는 프레임 수  만큼 프레임을 갖지 못하면 page fault가 계속 일어나게 되고, CPU이용률은 프로세스의 page가 계속 교체되어서 I/O 작업이 계속 일어나게 되어서 줄어들게 된다.  이 상태에서 CPU이용률은 또 떨어지니 새로운 프로세스를 다시 시작한다. 이렇게 페이지 부재 증가와 CPU이용률 감소가 악순환이 된다.

쓰레싱을 해결하기 위해서는 크게 두 가지 접근이 있는데, 하나는 프로세스가 필요로 하는 최소한의 프레임 개수를 보장해야 합니다. 

또 다른 하나는 다중 프로그래밍 정도를 낮춰서 CPU이용률을 유지해야 합니다. 구체적인 방법으로는 주 기억장치의  Working-set을 제대로 유지하게 합니다. working set은 임의의 시점에서 집중적으로 참조되는 페이지들을 모두 주 기억장치에 적재시켜 프로세스로 하여금 부재를 거의 발생시키지 않게 하는 set입니다. working set은 작으면 작을수록 좋다. temporal locality가 좋은 프로그램은 작은 수의 virtual page만 집중적으로 참고하고 새롭게 페이지를 만들 필요가 없다. 반대로 working set의 사이즈가 커지게 되면 위에서 말한 page fault가 발생하면서 안 쓰는 page와 쓰는 페이지 간에 swapping이 발생할 것이고, 자주 발생하면 Thrashing이 발생하게 된다. 

여기서 working set이란  Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page 들의 집합을 Working Set이라고 한다