[컴퓨터구조] 1127

Virtual Memory

▷ CPU - virtual memory - main memory, disk

• 각각의 프로그램은 각자의 virtual memory를 가지고 있다.
• 실행하고자 하는 프로그램을 virtual memory에 store하여, main memory와 disk에서 찾을 수 있도록 한다.
  --> 실제 main memory 크기보다 더 큰 프로세스를 실행할 수 있게 된다.

- Virtual memory: "page"

- Main memory: "Frame"

virtual memory - main memory, disk

 

Address Translation

Address Translation

: virtual memory의 page와 main memory의 frame과 매핑되도록 한다.

• Virtual page number --> Physical page number
• Page offset --> Page offset (virtual address와 main address의 offset 값은 같다.)

 

Page Fault Penalty

▶ Page Fault

: 원하는 virtual memory의 page에 대한 main memory의 frame이 main memory에 존재하지 않을 때!

--> Disk까지 가서 찾아와야 한다. (the page must be fetched from disk)

 

▷ Page fault를 최소한으로 하기 위한 방법:

• Fully associative placement: associativity를 높인다!
• Smart replacement algorithms

Page fault를 해결하기 위해서는, disk로 가는 상황을 막아야 한다. 즉, 자주 쓰는 데이터를 main memory에 저장해 두어야 한다.Q. "Associativity를 높인다" == "main memory에서의 associativity를 높인다"A. 캐시에서 associativity를 높이면 miss rate를 줄일 수 있다. Associativity가 커질수록, 정해진 방을 차지하려고 하는 경쟁이 덜 일어나기 때문에 miss rate를 줄일 수 있다. Main memory에서도 sub-room의 개수를 늘리면, 데이터가 disk로 쫓겨날 확률이 줄어들기 때문에, miss rate를 줄일 수 있다. 즉, cache와 main memory의 관계 == main memory와 disk의 관계!

 

 

Page Tables

: virtual memory의 page와 main memory의 frame을 매핑한다.

Page Tables

1. Page table register: 원하는 프로그램에 대한 page table의 main memory 주소를 가리키는 레지스터
2. 원하는 virtual page number에 대한 physical frame number 또는 disk address를 찾기 위해 page table을 확인한다.
   - Valid == 1 --> 해당 page에 대한 physical frame number가 있다! Main memory로 가서 그 frame에 접근하면 된다.
   - Valid == 0 --> 해당 page에 대한 frame이 main memory에 없다. Disk로 가야 한다. (page fault)

 

---

Replacement and Writes

: Page fault rate을 줄이기 위해서는, 자주 쓰이는 데이터를 main memory에 잘 저장해 두어야 한다.

▶ LRU(Least Recently Used): 가장 덜 최근에 사용된 데이터를 main memory에서 swap-out한다.

• Reference bit: 최근에 사용됐는지 여부를 표시하여, 어떤 page를 쫓아낼 지 결정하도록 하는 비트
  - 1: "최근에 사용됐다."
  - 0: "최근에 사용되지 않았다." --> swap-out!

 

+ Disk에 접근하는 것은 굉장히 오랜 시간을 필요로 한다. 따라서 disk에는 최소한으로 접근하도록 하는 것이 좋다.

--> 메모리에 어떤 값이 sw되면:

• Write through: main memory, disk에 둘 다 쓰는 방법 --> IMPRACTICAL!
• Wirte-back: 일단 main memory에만 쓰고, dirty bit == 1로 설정한 후, main memory에서 swap-out할 때만 disk에 쓴다.

 

---

Fast Translation Using a TLB

• Problem: 원하는 프로그램에 대한 page table을 main memory에 저장하여 page table register가 이를 가리키도록 하면, main memory에의 접근이 2번 필요하게 된다.
  - 1st: page table을 찾기 위한 메모리 접근
  - 2nd. 해당 page에 대한 frame에 접근하기 위한 메모리 접근
• Solution: TLB

▶ TLB (Translation Look-aside Buffer)

: Page table에 대한 캐시 메모리 역할을 한다. TLB 안에 PTE(Page Table Entry)의 일부를 저장해둔다!

--> 원하는 프로그램에 대한 page table을 찾기 위한 메모리 접근이 필요 없어진다.

Fast Translation Using TLB

1. 원하는 프로그램에 대한 virtual page number가 있다.
2. 이 page number에 대한 physical frame number를 알기 위해, 우선 TLB에 접근한다.
   - TLB valid bit == 1: TLB에 그에 대한 frame number가 있다! 그 frame에 대한 main memory 주소로 접근한다.
   - TLB valid bit == 0: TLB에 그에 대한 frame number가 없다. Main memory에 가서 그 프로그램에 대한 page table을 찾는다.

즉, TLB hit이면 바로 main memory로 가고, TLB miss가 발생했을 때만 main memory의 page table에 접근한다.

 

TLB Misses

TLB miss가 발생하면, page table을 찾으러 main memory로 가야 한다. 이때, 두 가지 상황이 발생할 수 있다.

1. 일단 main memory에 가서 page table을 찾는다.

2. Page table을 찾고 보니:

• Case 1) 원하는 virtual page number에 대한 physical frame이 main memory에 있다.
  --> TLB에 PTE(Page Table Entry)를 load하고, 재시도한다.
• Case 2) 원하는 virtual page number에 대한 physical frame이 main memory에 없다. 즉, 데이터가 disk에 있는 것이다. (page fault)
  --> 운영체제가 disk에 접근하여 main memory의 page table을 업데이트하여, 해당 page에 대한 frame을 추가한다.

 

TLB Miss Handler

• Case 1) TLB에 해당 page에 대한 frame 정보가 없어서 TLB miss가 발생했지만, main memory에서 page table을 찾아보니, 그 page에 대한 frame이 있다.
  --> TLB miss handler가 PTE를 main memory에서 TLB에 복사하고, 재시도한다.
• Case 2) TLB miss가 발생해서 main memory에서 page table을 찾고 보니, 그 page에 대한 frame이 main memory에 없다. Disk에 가서 찾아와야 한다. 
  --> Page fault!

 

Page Fault Handler

1. virtual address를 이용하여 disk에서 원하는 데이터를 찾는다. 즉, disk에서 frame을 찾는다.
2. Disk에 있는 page에 대한 frame(PTE; Page Table Entry)를 page table에 적는다.
3. 이때, page table에 entry를 추가하기 위해서는 다른 entry를 쫓아내야 한다. 어떤 entry를 main memory에서 swap-out할 지 정한다.
   만약 swap-out할 entry가 dirty라면, 즉 main memory에서 변경된 적이 있다면, disk에 적은 후 swap-out해야 한다.
4. Page table 업데이트가 완료된다.

 

TLB and Cache Interaction

TLB and Cache Interaction

자, 이제 전체적인 흐름을 살펴보자.

1. CPU가 원하는 virtual address 즉, virtual page number가 있다.
2. TLB에 접근하여 그 virtual page number에 대한 physical frame number가 TLB에 저장되어 있는지 확인한다.
3. 만약 TLB에 physical frame number가 있다면(valid == 1), main memory로 가서 그 frame에 접근한다.
   만약 TLB에 physical frame number가 없다면(valid == 0), main memory로 가서 그 page number에 대한 page table을 찾아서, 다시 main memory에서 원하는 frame number를 찾는다.
4. 잠깐! 이때 TLB 또는 page table을 통해 frame number를 알았다고 해서 바로 main memory로 가는게 아니다. Disk보다는 아니지만, main memory로의 접근 또한 굉장히 오래걸린다. 우리는 cache로 간다!

그런데 여기서 또 다른 문제가 있다.

왜 virtual address를 physical address로 바꾼 후에만, cache로의 접근이 가능해야 할까? 그냥 virtual memory만을 가지고 바로 cache에 접근하면 main memory에 한 번도 접근하지 않고도 데이터를 얻을 수 있을 것이다.

• Alternative: Use virtual address tag. (다소 복잡하긴 함...)

 

---

Memory Protection

• Problem: 많은 프로세스들이 virtual address를 공유한다. But, need to protect against errant access.
• Solution: HW support for OS protection.

▶ Privileged supervisor mode (Kernel mode)

: Privileged instructions.

• Page tables and other state information only accessible in supervisor mode.
• System call exception. (예: syscall in MIPS)

 

---

The Memory Hierarchy

자, 5장에서 배운 내용을 정리해보자!

 

1) Block Placement

: Block placement는 associativity에 의해 결정된다.

• Direct mapped (1-way associative): One choice for a set.
• n-way set associative: n choices for a set.
• Fully associative: Any location.

• 장점: Associativity가 높아진다는 것은 sub-room이 많아진다는 것이다. 따라서 하나의 set에 대해 여러 tag(데이터)를 저장할 수 있다. 따라서 miss rate가 낮아진다.
• 단점: 하나의 set에 대한 sub-room이 많아지면, set을 검색한 후에, 다시 tag를 살펴보는 시간이 필요하다. --> Increase complexity, cost and access time.

 

2) Finding a Block

Finding a Block

▷ Associativity가 높아지면:

• Hardware caches: 하나의 set에 대해 여러 데이터를 저장할 수 있어 miss rate가 낮아지지만, comparison time이 늘어난다.
• Virtual memory: Fully associative table lookup makes full associativity feasible. Benefit in reduced miss rate.

 

3) Replacement on a Miss

• Hardware caches: LRU 또는 random
• Virtual memory: LRU

 

4) Write Policy

▶ Hardware caches:

• Wirte-through: 캐시와 메모리에 둘 다 쓰는 방식
• Wirte-back: 일단 캐시에만 쓰고, dirty bit = 1로 바꿨다가, 캐시에서 swap-out될 때 메모리에 쓰는 방식

▶ Virtual memory:

• Write-back: 일단 메모리에만 쓰고, dirty bit = 1로 바꿨다가, 메모리에서 swap-out될 때 디스크에 쓰는 방식

 

---

Sources of Misses

• Compulsory miss: cache와 page table 모두, 처음 접근하면 그에 대한 정보는 저장되어 있지 않기 때문에 miss가 발생한다.
• Capacity miss: cache와 page table의 크기가 한정되어 있기 때문에, cache와 PTE가 꽉 차버리면 LRU에 의거하여 어떤 것을 쫓아내야 한다. 이것은 용량의 한계때문에 발생하는 miss이므로, fully associative에서도 발생한다.
• Conflict miss: 하나의 set 당 저장될 수 있는 tag 개수가 한정되어 있기 때문에, 원하는 set에 할당된 sub-room이 꽉 차버리면, LRU에 의거하여 어떤 것을 쫓아내야 한다. 이것은 sub-room 개수의 한계때문에 발생하는 miss이므로, conflict miss의 가장 좋은 해결책은 fully associativity를 적용하는 것이다.

 

Cache Design Trade-offs

▷ Cache 크기를 늘리면:

• Decrease cache miss.
• Increase access time.

▷  Associativity를 늘리면:

• Decrease conflict miss.
• Increase access time (comparing time).

▷  Block 크기를 늘리면:

• Decrease compulsory misses. (Block 크기가 크면, 메모리에서 한번에 읽어들이는 데이터의 양이 많다. 따라서 한 번의 compulsory miss는 발생하겠지만, 그와 가까운 메모리를 필요로 하는 다른 것에 대해서는 compulsory miss가 방지될 것이다.)
• Increase miss penalty. For very large block size, may increase miss rate due to pollution.

 

 

 

 

 

출처: 이화여자대학교 이형준교수님 컴퓨터구조