paging, TLB - 운영체제

Segmentation의 문제: Fragmentation

• 메모리 할당에 사용할 수 없는 빈 공간
• external fragmentation:
  • 외부 단편화
  • memory allocator(= OS) 입장에서 확인할 수 있음
  • 세그멘트가 연속적으로 할당되기 때문에 이보다 작은 공간에는 할당할 수 없음
• internal fragmentation:
  • 내부 단편화
  • requester 입장에서 확인할 수 있음
  • 내부적으로 공간이 있으나 사용되지 않음

Paging

• 메모리 주소가 연속적이어야 한다는 문제를 해결
• 외부 단편화 제거
• 필요시에 세그먼트를 늘이거나 줄일 수 있음
• 메모리 공간을 fixed-sized page (e.g. 4kb)로 나눔
• physical page: page frame

Translation of Page Address

• logical address가 physical address 어디를 가리키는가?
  • high-order bits는 page number를 가리킴
  • low-order bits는 page offset을 가리킴
• 매핑 테이블이 있다고 생각하자
• page offset은 그대로 사용
• 예시에서 page offset이 12 bits인 이유는 페이지 크기가 2의 12승 = 4kb이기 때문
  

  

  
  

  

  
  

  

• virt page 표현 개수는 2의 high bits 승

Virtual page number => Physical Page Number

• OS 혹은 MMU
• 메모리에 접근해서 실제 페이지 넘버를 가져와야 한다
• segmentation에서는 phys addr = virt_offset + base_reg으로 해결했었다
• paging에서는 OS는 더 일반적인 매핑 매커니즘이 필요
  

  

• Array에 매핑되기 된다

페이지 테이블이 저장하는 정보

• 32비트 주소 공간
• 4KB 페이지
• 4B 페이지 엔트리
• 1M 엔트리 개수
• 한 프로세스 당 페이지 테이블 크기가 4MB
• 각 페이지 테이블은 메모리에 저장된다
  • 메모리 낭비가 너무 심함!
• 컨텍스트 스위치
  • 페이지 테이블 시작 주소 값을 가지는 베이스 레지스터를 새로운 값으로 바꿔야 함
  • 기존 페이지 테이블 베이스 레지스터 값은 PCB에 포함되어 저장

Other PT Info

• valid bit: is valid
• protection bits: rwx
• present bit: in memory?
• reference bit: LRU
• dirty bit: write back

Memory Access with Pages

 

• 명령 자체도 페이지 테이블 통해서 접근
  • 페이지 테이블 접근
  • 물리 메모리 주소에서 명령어 fetch
  • 코드 실행
• 메모리 접근하는 명령
  • 페이지 테이블에 접근
  • physical address 갖고 다시 메모리에 접근
• 총 3개 명령어, 2개 movl이 메모리에 접근
  • 각 2번씩 메모리 접근(= 총 10번 접근)

페이징의 이점

• 외부 단편화가 없음
  • 페이지는 메모리 어디에든 위치 가능
• 빠른 할당 및 해제
  • alloc: free space를 찾을 필요 없음, free space list로 관리 => pop
  • free: free 공간을 만들기 위해 garbage collection 할 필요가 없음
  • bitmap을 사용하여 free/allocate
• 메모리의 일부분을 디스크에서 읽어오기 쉬움
  • 페이지 사이즈는 디스크 블록 사이즈와 같음
  • 프로세스가 디스크에서 읽어오기 가능
  • present bit을 통해 달성

페이징의 단점

• 내부 단편화: 4kb를 다 사용하지 않는 경우
• 추가적인 메모리 접근으로 느림
  • 페이지 테이블은 메모리에 저장된다
  • MMU가 페이지 테이블의 base address를 저장한다
  • 메모리 내 페이지 테이블 접근
  • 다시 메모리 접근
  • TLB를 추가하여 해결한다
• 페이지 테이블을 위한 저장공간이 필요
  • 심플한 페이지 테이블
    • 모든 페이지에 대해 PTE를 가져야한다
    • 페이지가 할당되지 않아도 엔트리 있어야 함
    • 메모리 낭비가 생김
  • 다이나믹 스택과 힙의 경우 문제가 생김
  • 페이지 테이블이 연속적으로 할당됨
  • 페이징과 세그멘테이션을 혼합하여 사용한다

Example

• (p2) load 0x0000 => load 0x0800 (PTE) => load 0x6000 (phys addr)
• (p2) load 0x1444 => load 0x0808 (PTE) => load 0x2444 (phys addr)
  • 1 => PTE index: 1, PTE size = 8 bytes
  • 444 => page offset
• (p1) load 0x1444 => load 0x0008 (PTE) => load 0x5444 (phys addr)

Translation Step

• H/W: 각 메모리 접근 시
  1. VA(virtual addr)로부터 VPN(virtual page number) 뽑기
  2. PTE(page table entry) 계산하기
  3. 메모리에서 PTE 값 읽기
  4. PFN(page frame number) 뽑기
  5. page offset과 합쳐 PA(physical address) 구성
  6. 메모리의 PA 주소에서 값을 읽어 레지스터에 저장
• 3, 6 스텝이 오래 걸림

Array Iterator Example

• 0x3000, 0x3004, 0x3008, ... 순차적으로 접근
• 데이터가 같은 페이지 안에 존재한다면 메모리에서 PFN을 계속 받아오는 건 비효율적
  

  

• PFN을 위한 캐시와 같은 공간을 만들자 => TLB(Translation Look-aside Buffer)

TLB(Translation Look-aside Buffer)

• VPN을 이용하여 먼저 TLB에서 parallel search
• TLB에 PFN(Physical Frame Number)가 존재한다면 TLB Hit
  • 해당 값을 이용하여 physical address 구성하여 메모리 접근
• TLB Miss일 경우에만 메모리 내의 페이지 테이블 접근

TLB Associativity Trade-off

• higher associativity
  • Hit Rate 증가, Collision 적음
  • 느리다
  • 더많은 하드웨어가 필요
• lower associativity
  • 빠르다
  • 간단하고 적은 하드웨어
  • collision 발생할 확률 높음
• 보통 fully associative로 사용한다

Array Iterator Example with TLB

 

• 같은 페이지에 접근하는 virtual address는 TLB Hit으로 인해 메모리 접근을 한 번만 수행한다