Chapter 8-2. Virtual Memory

Translation Lookaside Buffer

Relocation 을 위해서 Page Table 을 이용한다. Page Table 에는 두가지 종류가 있다.

• hierarchical page table
• inverted page table

hierarchical page table 을 사용할 때는 Page Table 자체가 크기 때문에 이게 2, 3, 4, ... 단계 page table 이 될 수 있다.

2단계 페이지 테이블의 경우
데이터 읽기 → Root Page Table → 2nd Page Table → 정확한 Physical Address 주소 획득 → memory
⇒ 데이터를 읽을 때, memory 에 3번 access

ex) 보통 프로그램을 실행할 때 
코드 → 데이터 → 코드 → 데이터 → ... 을 반복하는데 
각각 3번씩 접근하므로 프로그램의 속도가 3배가 느려진다.

3단계 페이지 테이블까지 존재하는 경우에는 4번 메모리에 접근해야 한다.

⇒ TLB (Translation Lookaside Buffer) : Cache 이용

페이지 크기 2^10, 2^12 → 너무 큰 숫자
⇒ 만약, 명령 1000개라고 치면, 한 페이지 안에 명령 1000개가 들어있다는 뜻인데 이건 매우 많은 양이다.

처음에 코드를 읽어올 때 이 코드가 몇번 프레임에 있는지 페이지 테이블을 통해 찾고, Locality 덕분에 그 뒤 같은 테이블을 계속 읽는다.
어떤 페이지를 한 번 읽었을 때 몇 번 프레임에 있었다는 정보를 TLB에다 최근에 내가 읽은 페이지에 대한 정보를 적어 놓게 되면 다시 페이지 테이블을 찾으러 갈 필요가 없다.
⇒ Cache 역할을 한다.

TLB 에서 access 하면 된다. 최근에 내가 access 한 페이지의 정보 O
⇒ 속도 저하 방지 가능

Each virtual memory reference can cause two physical memory accesses

• one to fetch the page table
• one to fetch the data

To overcome this problem a high-speed cache is set up for page table entries

• called the TLB - Translation Lookaside Buffer
• Contains page table entries that have been most recently
  used
• Functions same way as a memory cache

주소를 변환하는 과정

1. 페이지 번호를 TLB 에 주고 프레임 번호를 얻어온다.
2. 만약 데이터가 있다면, 이걸 TLB hit 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 있는 경우
3. 만약 데이터가 없다면, TLB miss 라고 한다.
   = TLB 에 내가 원하는 페이지에 대한 정보가 없는 경우
   → 페이지 테이블로 접근
   ↳ 페이지 테이블을 2단계, 3단계 거쳐서 내가 원하는 프레임 정보를 얻어내면 이걸 다시 TLB 에 쓴다 .
   → 그 후 , 주소 변환
4. 페이지가 메모리에 없는 경우 (= 페이지 테이블에 페이지가 없는 경우) 는 Page fault 라고 한다.
   → 하드디스크에 가서 페이지를 메모리에 올려 놓는다.
   당연히 올려 놓는 과정에서 페이지 테이블을 업데이트 하고, TLB 도 업데이트 한다.

이렇게 한 번 작업하고 나면, 나중에 TLB에서 내가 원하는 정보를 얻을 수 있기 때문에 주소 변환이 즉시 즉시 이루어지게 된다.

왼편은 일반적인 메모리에 TLB 가 저장되어 있는 것
어떤 프로세스의 연속된 정보가 들어 있는 것이 아니라 최근 정보가 들어 있는 것이기 때문에 sequential 하게 5번 페이지가 37 번 프레임에 있다 하면, 5번 페이지를 꼭 찾아야 한다.

른편은 페이지 번호가 원소의 일부로 사용되는 association 타입을 이용한다. 하나의 엔트리 안에 페이지 번호와 프레임 번호가 들어 있어있다.
⇒ 한번에 내가 원하는 프레임 번호를 찾아낼 수 있다.

associative 메모리를 사용하기 때문에 TLB 는 한번에 access 하면 프레임 번호가 딱 튀어 나온다.

---

거의 모든 시스템이 Virtual Memory 와 TLB 를 사용한다.

하지만, Page size 에는 의견이 다양하다.

Page Size (페이지 크기는 작아서는 안된다!)

• Smaller page size, more pages required per process
• More pages per process means larger page tables
• Larger page tables means large portion of page tables in virtual memory

페이지의 크기가 작다면, 같은 크기의 프로그램 내에 더 많은 페이지 수가 많아지게 되므로 페이지 테이블의 Entry 개수가 많아지게 된다.
⇒ Page Table 수가 증가한다.
↳ 메모리에 페이지 테이블이 없을 확률이 높아진다.
⇒ 시간 소요가 증가한다. ⇒ 페이지 크기는 작아서는 안된다!

Page Size2 (페이지 크기는 커서는 안된다!)

• Small page size, large number of pages will be found in main memory
• As time goes on during execution, the pages in memory will all contain portions of the process near recent references. Page faults low.
• Increased page size causes pages to contain locations further from any recent reference. Page faults rise.

Virtual Memory System 에서는 여러 프로그램들이 메모리에 들어와 있어야 한다. 대부분의 경우 프로세스 하나하나 마다 일정한 크기의 공간을 나누어 준다.

만약 내가 할당받은 공간이 이만할 때, 우연히 내 페이지 크기가 딱 그만큼이라서 이 공간에 딱 한페이지만 들어갈 수 있다고 하자.
↳ 즉, 페이지 크기가 상당히 큰 것이다.

프로그램을 실행하려고 하면, 코드와 데이터가 있어야 한다. 코드 한줄, 데이터 한줄 계속 실행하는데, 각각의 코드와 데이터가 들어 있는 페이지는 하드디스크로 계속 Swap-In, Swap-Out 하게 된다.

그럼 계속 코드가 들어 있는 페이지와 코드가 들어 있는 페이지가 왔다갔다 실행되며 Thrasing 이 발생할 것이다.

만약 페이지의 크기가 작아서 내 프로그램이 더 작은 단위로 나뉘어져 있다면, 코드 한쪽 데이터 한쪽 스택 한쪽, ... 필요한 애들을 한쪽씩 갖다 놓고 작업을 할 수 있기 때문에 Page fault 가 일어나지 않는다.

Thrasing이 발생할 것이다

data ↔ code 왔다갔다 많이할 것

페이지를 작게하면 필요한 애들을 적게 적게 갖다 놔서 Page Fault 가 적어질 것이다.
↔ 페이지 크기를 크게 하면 Page Fault 가 많아질 것이다.

⇒ 결론적으로는 페이지는 너무 커도 안되고, 너무 작아도 안된다.

---

Segmentation

Segmentation을 이용한 Virtual momory system 은 굉장히 비효율적이기 때문에 사용하지 않는다.

• May be unequal, dynamic size
• Lends itself to sharing data among processes
• Lends itself to protection

sharing 하는 단위가 분명하다.

의미 있는 단위로 나뉠 것이다. → 한 segment 안에 data 또는 code 만 존재할 것이다.

Protect 하는 단위가 분명하다.

• PCB → OS 가 사용
• Code → User 가 사용

---

Segment Table Entries

Segment 을 이용한 시스템에서는 Dynamic Partitioning 을 사용하기 때문에 Segment 의 정확한 시작 주소를 알아야 한다.

길이가 제각각이기 때문에 Offset > Length 인지 계속 확인해 주어야 한다.

---

Segment Tables

• Each entry contains the length of the segment
• A bit is needed to determine if segment is already in
  main memory
• Another bit is needed to determine if the segment has been modified since it was loaded in main memory

---

Address Translation in Segmentation

주소변환과정

---

Combined Paging and Segmentation

두 시스템의 장점을 결합하여 사용

• Paging System → External Fragmentation X
• Segmenation System → Protection, Sharing 👍

1. 페이지 크기로 나누기 전에 Segmentation 4가지 영역으로 먼저 나눔
2. 동일한 크기의 page frame 크기로 나눔 ⇒ page 크기로 나눔
   ⇒ 한 페이지 안에 code 와 data, pcb 등등 서로 섞인 페이지가 존재하지 않게 된다.
3. 각 Segment 로 나눈 단위마다 Internal Fragmentation 존재 가능 (공간 낭비 조금 존재, but Protection 과 Sharing 이 더 중요)