본 시리즈은 비전공자가 공부한 computer science, 그중에서도 컴퓨터구조를 정리한 글입니다. 틀린내용이 있다면 댓글로 알려주시면 정말정말 감사하겠습니다. 참고한 책은 Computer Organization and Design MIPS Edition입니다
진짜진짜 컴퓨터구조의 마지막 포스팅으로 돌아온 킴스캐슬입니다
(운영체제로 다시 돌아올 예정입니다 ㅎㅎ)
이번 포스팅은 하나의 예제를 분석해보는 포스팅입니다
뭔가 길거같지는 않은데 표를 따라오는 과정에서 머리가 조금 지끈거릴수는있을거같긴합니다...
(눈알도 좀 빠질거같기도 하네요...)
컴퓨터구조를 마무리하는 소감은 맨 아래쪽에서 푸는걸로 하고 마지막 포스팅도 힘차게 출발해보겠습니다
Example of Cache and Memory
아주 간단한 예시입니다 아래와같은 메모리에 있는 data에 연속적으로 접근하는 예시입니다
Virtual address에서 TLB와 page table을 거쳐 cache까지 가는 회로는 아래과 같다고 하겠습니다
검은색 네모박스를 보면 page offset이 12bit니까 (2의12제곱)byte니까 page의 크기가 4KB라는걸 알수있습니다
빨간색 네모박스를 보면 byte offset이 2bit, block offset이 4bit이므로 16words/block이라는걸 알 수 있습니다. cache index가 8bit니까 cache의 index는 0부터 255까지겠네요
파란색 네모박스를 보면 tag를 여러군데에있는걸 비교하는게 아니라 하나의 tag만 비교해서 hit여부를 판별하므로 direct mapped cache라는걸 알 수 있습니다(1way)
Initial States of TLB, cache, page table and Main memory
초기 상태는 아래와 같은 표에서 시작한다고 해보겠습니다
첫번째 메모리주소에 access해보겠습니다
우선 0x00004000은 TLB에가서 physical memory address를 얻어야하는데 TLB가 비어있으므로 TLB miss입니다 그리고 page table도 비어있어서 page fault가 발생합니다
그래서 어쩔수없이 main memory에서 데이터를 읽어와야하는데 여기도 데이터가 없습니다
그렇다는말은 address translation이 불가능하다는 뜻이 됩니다
결국 secondary storage에서 0x0004를 포함하는 4KB만큼의 데이터를 메모리에 넣어줍니다 이때 main memory는 fully associate이기때문에 비어잇는 첫 page에 넣어줍니다
그러면 page table과 TLB가 업데이트됩니다
이런상황이겠네요
State of TLB, cache, page table and Main memory(1)
여기서 이제 physical address를 알았습니다. 0x01000000입니다(page+pageoffset)
그럼 이제 이 32bit에서 데이터에 access하기위해서 tag와 cache index로 분리를 했는데
index가 0인쪽에 가서 봤는데 cache의 valid가 0이라 cache miss가 되게 됩니다
그렇게 되면 main 메모리에서 해당 주소에있는 16word(64byte)만큼의 데이터를 가져와서 cache에 넣게됩니다
State of TLB, cache, page table and Main memory(2)
0x00004008이라는 메모리에 data에 access해보겠습니다
근데 page offset을 제외한 bit와 같은 tag를 TLB에서 찾을 수 있습니다 이 경우에 TLB hit이 되고 바로 physical address를 얻을 수 있습니다
그러면 physical address는 0x01000008이 됩니다
tag는 0x01000이 되고 index는 0x00이 됩니다
data에 access하기 위해서 cache의 index와 tag를 비교해보니 같은 곳에 valid가 1이라서 cache hit이 됩니다
State of TLB, cache, page table and Main memory(3)
이번에는 0x000041000을 보겠습니다
block offset을 제외한값을 TLB tag에서 찾을 수 있기 때문에 TLB hit입니다
그렇게되면 physical address로 0x01000100을 얻을 수 있는데
tag가 0x01000이고 index가 0x04가됩니다
cache로 가보니 해당 index에 valid가 0이라서 cache miss가 됩니다
그렇게되면 main memory에서 해당 address가 포함되어있는 64byte값을 cache에 copy하게됩니다
그림에서 보면 main memory 0x01000page에 찾으려는 데이터가 있어서 64byte만큼 copy해옵니다
State of TLB, cache, page table and Main memory(4)
0x00002010입니다
block offset을 제외한 bit를 TLB에서 tag로 찾을수없기때문에 TLB miss이고
page에서도 index로 찾을수가없어서 page fault입니다
address translation이 불가능해서 해당 주소의 data를 포함하고 있는 4KB를 main memory에 copy해줍니다
TLB와 page table을 채우고 physical address를 구해서 cache로 갔는데 index에 valid가 0이어서 main memory에서 해당 address를 포함하는 범위의 data를 64byte만큼 copy해줍니다
이때는 cache miss가 발생합니다
State of TLB, cache, page table and Main memory(5)
0xFFFFF000을 볼까요?
이경우도 마찬가지로 TLB miss, page fault인데 main memory에도 해당 address가 포함된 데이터가 없어서 secondary storage에서 데이터를 4KB만큼 copy해오고 physical address를 구해서 cache index로 갔는데 valid가 0이기때문에 cache miss가 발생해 main memory에서 해당 address가 포함된 64byte를 cache로 copy해옵니다
State of TLB, cache, page table and Main memory(6)
0x00001000도 위의 메모리와 마찬가지입니다
TLB miss와 page fault인데 main memory에도 해당 address가 포함된 데이터가 없어 secondary storage에서 copy해오고 TLB와 page table을 채운뒤 physical address를 구해서 cache index로 갔는데 valid가 0이라서 main memory에서 해당 address가 포함된 64byte데이터를 copy해옵니다
State of TLB, cache, page table and Main memory(7)
0x00005000을 볼까요 이 경우도 TLB miss page fault cache miss가 일어나는데 이미 TLB가 꽉차서 가장 오래된 TLB 데이터를 지우고 그 자리에 데이터를 넣습니다
cache miss인데 index가 0x00이고 tag가 0x01004 입니다
cache에 같은 index가 valid라서 tag를 비교했는데 달라서 해당 데이터를 replace합니다
State of TLB, cache, page table and Main memory(8)
0x00004000을 보겠습니다(거의 다 왔습니다!)
TLB에 갔는데 tag와 동일한게 없으니까 TLB miss입니다
page table에 가니까 0x0004라는 index의 valid가 1입니다
이를 통해 physical address를 구할 수 있고 cache에 가니까 index는 같은데 tag가 달라서 address가 포함된 data를 maim memory에서 64byte만큼 copy해서 replace해줍니다
마지막입니다!
0x00002000을 보겠습니다!
TLB에 갔더니 tag에 맞는게 없어서 TLB miss가 발생합니다 하지만 page table에는 일치하는 index가 있고 valid가 1이라서 physical address를 구할 수 있습니다
index는 0x40이고 tag는 0x01000인데 cache에 가니까 index와 tag가 동일하고 valid가 1인게 있어서 해당 data에 바로 access할 수있습니다 이 경우엔 TLB는 miss였지만 cache hit이 발생하는 경우입니다
Cache, TLB, and VM
지금까지 봐온걸 바탕으로 cache와 TLB VM의 관계를 정리해보겠습니다
보시면 page table miss가 발생한 경우엔 TLB와 Cache hit이 일어날 수는 없습니다 하지만
TLB가 hit이고 page table이가 hit일때 cache는 miss가 될수도있고
TLB가 miss지만 page table과 cache가 hit일수도있고
TLB가 miss지만 page table이 hit이고 cache가 miss일수있습니다
마지막으로 전부다 miss일수도있습니다 이런경우엔 secondary storage에서 4kb만큼의 data를 copy해와야하겟지만요...
이번포스팅에서 본 예제들을 다시한번 복습하면 위의 표에서 볼수있는 경우들을 확인할수있으리라 생각됩니다!
드디어 끝!
