5. 운영체제 paging

→메모리 관리 접근법 두 가지

1) Segmentation
- 이전 파트에서 공부함
- 다양한 크기의 segment로 나눔
- fragmentation, free list management 등의 문제점

2) Paging
- 고정된 크기의 "page"로 virtual address를 나눔
- physical memory는 고정된 크기의 page frame 배열이 되고, 그것은 각각 virtual page에 연결됨

 

Page-Based Memory Mangement의 이점

• Flexibility : 프로세스가 메모리를 어떻게 사용하든지 (스택이든 힙이든 상관없이) 유연함
• Simplicity : 모든 페이지의 크기가 같으므로 free list를 관리하기도 쉽고 free page 찾아서 쓰기도 쉬움

 

Virtual Page to Physical Frame Translation

16KB의 virtual address space를 표현한다면, 14bit가 필요하다. 이 중 12bit는 4KB 크기의 page안에서의 주소를 가리킨다.

 

Page Table

• OS는 virtual page를 physical frame에 매핑해주는 page table이라는 자료구조를 가짐
• 이 page table은 프로세스마다 생성됨
• virtual page number(VPN)이 physical frame number(PFN)에 매핑됨
• 문제점 : page table은 프로세스 마다 생성돼서 크기가 매우 큼 → 레지스터나 캐시가 아닌 메모리에 저장!

 

Page Table Entry (PTE)

• VPN으로 PFN을 찾기 위해 PTE를 검색
• PFN과 control bits로 구성
  

  

• PTE를 이용한 메모리 엑세스 순서

1. fetch PTE
2. extract PFN
3. PFN에 offset 결합
4. physical memory 접근

 

Page-based Memory Mangement의 문제점

• 두 번의 메모리 엑세스가 필요 - PTE 한 번, actual data 한 번
• 이 두개가 serialized 되면 좋을텐데... → Translation Lookaside Buffer (TLB)

 

Translation Lookaside Buffer (TLB)

•  자주 사용되는 address를 TLB(cache)에 저장해둠
• 사실 상 TLB가 있어 paging이 가능한거임!

 

Address Transloation using TLB

• TLB hit / miss : VPN-PFN 매핑이 TLB에 있음 / 없음
• 과정
  1) VPN 추출
  2) TLB 존재 여부 검사
  3-1) hit : PFN 추출 후 메모리에 엑세스
  3-2) miss : page table 통해 PTE 추출, PFN으로 메모리 엑세스, 현재 VPN-PFN pair를 TLB에 삽입
• 참고로, TLB는 cache에 존재해서 TLB에서 존재 여부 검사할 때 메모리 엑세스로 인한 오버헤드 X

 

Local Principles 

• Temporal Locality
• Spatial Locality

Page Size와 Performance의 관계

	Large	Small
TLB miss	↓	↑
# of pages	↑	↓
internal fragment	↑	↓

일반적으로 4KB 크기를 사용

 

TLB Contents

• Set-Associative Cache
• 문제점 : TLB는 cuttently running process 정보만 갖고 있어서 context switching 발생시 처리가 힘들다.
• 각 프로세스마다 VPN이 존재해서 서로 다른 프로세스인데 VPN이 같은 TLB가 존재한다. 이러면 어떤 PFN이 맞는건지 알 수 없다.
  

  

• 그래서 Address Space ID (ASID)가 필요
  

  

 

Shared Pages

• 서로 다른 프로세스가 같은 physical address를 공유하는 것도 가능
• ex) fork() 사용할 때

 

Cache Organizations

1. Direct-Mapped Cache
   1-to-1 mapping, 한 번만 체크함
   

   

2. Fully-Associative Cache
   전체 entry에 대해 모두 체크
   

   

3. Set-Associative Cache
   1과 2의 절충안. N개의 cache block만 체크
   

   

 

Page Table의 크기가 문제라고 했는데, 이걸 줄이려면?

• Long Pages : 페이지 크기가 크면 개수는 줄어드므로 Page Table의 크기가 작아짐. 하지만 internal fragmentation 문제 발생
• Paging + Segmentation : Segmentation 마다 Page를 두는 것. 스택과 힙 사이의 빈 공간 낭비를 방지해줌

 

Multi-Level Page Tables

• Paging + Segmentation은 여전히 internal fragmentation, variable-sized page table 등의 문제가 있음
• Multi-Level Page Tables는 page table을 page의 크기의 단위로 나눔
• 만약 page table 안의 page가 전부 사용되지 않으면 그 page table은 메모리에 할당되지 않음
• page directory라는 자료구조를 이용해 각 page의 할당여부와 위치를 파악
• 트리구조

Multi-Level Page Tables 장점

• 메모리 관리가 용이함
• TLB miss 발생시 두 번의 메모리 엑세스가 필요함 : page directory와 PTE

 

Deeper Multi-Level Page Tables 라는 것도 있음

Inverted Page Table이라는 것도 있음

• VPN → PFN이 아니라, single page table을 두고 PFN → VPN을 탐색하는 방식

 

---

Beyond Physical Memory

지금까지 우리는 모든 page들이 Physical Memory에 존재한다고 가정했는데 Physical Memory 크기보다 더 커보이게 할 수 는 없을까?
→ 자주 엑세스 되지 않는 page들을 하드디스크의 swap space에 보낸다.
→ 그러니까 메모리를 캐시처럼 사용한다는 거지.

 

Swap Space

• 디스크 공간의 일부는 page-sized memory data 저장을 위해 사용된다.
• 아래 그림에서 자주 사용되지 않는 Proc 3는 swap space에 계속 남는다.
  

  

Page Fault 

• Swap Space 때문에 발생
• PTE에 present bit라는게 해당 page가 memory에 있는지 swap space에 있는지를 알려줌
• page fault handler를 통해 메모리로 page를 다시 가져오는 swap out을 함
  

  

• page를 가져와서 PTE를 업뎃하고, 다시 시도해서 page를 불러올 수 있음
• 근데 swap out하는 동안 context switching으로 다른 프로세스 실행할 수 있음

 

Page Replacement 교체 정책

• 메모리가 가득차면 OS는 page 일부를 제거함
• 이 때 제거하는 page 교체 정책에 따라 컴퓨터 성능이 달라짐. 근데 일단 중요한건 page fault를 최소화하는 것
• Average Memory Access Time(AMAT)
  

  

 

1. Optional Replacement Policy
   - 가장 나중에 엑세스될 페이지를 제거
   - 당연히 예측 불가이므로 쓸 수 없음
2. FIFO 정책
   - 심플하지만, page의 중요도를 안따짐
3. Random Replacement Policy
   - 심플하지만, 결과도 랜덤
4. Least-Recently-Used Replacement Policy (LRU 정책)
   - 과거 정보를 이용해 최근에 적게 엑세스된 페이지를 삭제
   - temporal locality를 고려한 것
5. Others
   - Least-Frequently-Used(LFU) : 모든 시간 통틀어서 적게 엑세스된 페이지를 삭제
   - Most-Frequently-Used(MFU) : 최근에 가장 많이 사용된 페이지를 삭제

 

Replacement Speeding Up

• Dirty bit : 페이지가 변경된 기록이 있는지 여부 (변경된 내용을 기록하는 비용이 발생하므로 교체 X)
• write clustering : 그룹 단위로 제거
• prefetching : spatial locality 기반으로 다음에 올 page를 예측
• 메모리가 가득차기 전부터 크기를 조정
  - free page수가 low watermark(LW) 보다 작으면 그 free page를 제거
  - free page수가 high watermark(HW) 보다 커질 때까지 다른 메모리 free

 

Thrashing

• 메모리가 이미 활동중이 페이지들로 가득차서 어떤 페이지가 교체되어도 바로 다시 교체가 필요한 상황
• 지역교환 알고리즘이나 우선순위 교환 알고리즘을 사용해 제한할 수 있음. 또는 admission control을 통해 몇개의 프로세스만 완벽히 처리하거나, 메모리를 많이 사용하는 프로세스를 kill하는 등의 방법이 있음. (
  후자는 그래픽 서버같이 중요한 프로세스 죽일 위험이 있음 ㅠㅠ)