[운영체제] 시험 대비 - 8강 ~ 10강 (Locality and Caching, Paging Scheme Design, Memory Management Policy)

1. Locality and Caching

• TLB : 주소 변환 시 메모리에 접근하는 일을 줄여줌
  • CPU의 cache에 위치 → VPN과 PFN 쌍으로 존재
  • TLB miss → memory에 존재하는 page table 따라가서 PFN 주소 확인
• 누가 TLB miss 처리?
  • OS
    • TLB miss → 현재 명령 중지 → kernal mode로 변환 → trap
    • page table 조회 → TLB update → 다시 명령 실행
    • 없으면? TLB miss handler
  • HW
    • page table 메모리 위치, page table 존재하는 정보 알아야
• TLB
  • VPN, PFN, 다른 비트들로 entry 구성
  • fully-associative(캐시 내 아무 장소에 mapping 가능)
• 문제
  • 서로 다른 process에 대해 같은 VA 정보가 TLB에 있다. 이 경우 VA로 mapping 정보 확인해야 하는데 같은 번호에 대한 서로 다른 PFN이 존재한다면 어떤 PFN을 선택해야할지 모른다. 이떄 해결할 수 잇는 장치는? → process id를 TLB에 저장 ! ASID(Address space Identifier)
• TLB 교체 정책 : LRU → 구현하기 어려우니 clock algorithm도 뒤이어 나옴
  • LRU는 시험 문제 또 나올 수 있으니 함 풀어보자
  • 진짜 풀다보면 어라라? 싶을 수도 있을 듯

---

1. Paging Scheme Design
   • page size를 늘리자 → internal fragmentation
   • hybrid approach: segment마다 base와 bound값 저장 (segment의 개념 차용)
     • 이 말인 즉슨, code, stack, heap 영역의 각각의 page들을 묶어 segment로 보겠다는 의미. (각 segment의 base, bound 값)
     • segment마다 page table을 두어 이것에 따른 mapping을 진행하겠다.
     • BUT, 여전히 heap의 경우는 page table 크게 잡아야 하고 다시 external fragmentation issue가 붉어질 수밖에 없음
   • Multi-level page table
     • page table 낭비를 줄이고자 multi-level page table을 구성
     • page table을 page 단위로 자른다 → 하나라도 유효한 entry가 없다면 해당 page table을 유지하지 않는다
     • page directory : page table의 page가 어디에 위치해 있는지, 해당 page table에 유효한 page가 있는지(valid) 알려주는 데 사용된다.
       • page table size 줄여주고
       • page 단위로 나눠서 관리하므로 잘 구현한다면 메모리 관리가 쉬워짐
       • page table의 일부를 가리키는 page directory를 사용 → 실제 메모리의 원하는 곳에 page table page를 배치할 수 있음
       • 단점: TLB Miss : 메모리에서 PT에 접근하기 위해 Page directory에도 접근해야 함
   • 예제 드가자
     • Page 크기 64Byte, PTE 크기가 4byte인 16KB 주소공간을 갖는 시스템에서, 가상주소의 offset과 VPN이 각각 몇 bit인지 구하라.
       • 16kb = 2^14 → VA : 14비트로 구성, page 크기→offset: 2^6 : 6bit, VPN: 8bit
     • page table의 크기는?
       • (vpn)2^8 = 256, (1PTE) 4byte, 256* 4b = 1KB
     • page directory entry의 개수
       • page table을 page size로 나누면 → 1kb / 64byte = 16 → page directory를 위해 4개의 bit : vpn의 상위 4bit를 사용
     • pte 정보로 사용하는 bit
       • vpn의 나머지 bit
     • 각각의 page table에 존재하는 entry 개수?
       • 16개
     • VA 100에서 PFN 주소를 찾아라
       • 100 = 0x64 = 00 00 / 00 01 / 10 0100
       • PDI 0번 접근
       • 1번 index로 접근해서 해당 PFN get
       • page size * PFN + offset (36) : 실제 physical address !
   • Second 예시
     • page 크기 512byte, pte size 4byte; 30 bit 가상 주소 공간
       • offset? VPN? → offset: 9bit, VPN: 21bit
       • page table 크기: 4*2^21 = 2^23
       • page entry 개수: 512 / 4 = 128 = 7 bit,,
       • page directory entry의 개수: (page table size) / (page size) = 2^23 / (2^9) = 2^14
       • 문제 → page directory에 220개 항목이 있으면 하나의 page로 나타낼 수 없게 됨
       • 따라서 page 단위(page에서 커버 가능한 page entry 수)로 page directory entry를 쪼갬
   • Inverted Page Tables
     • 모든 프로세스가 하나의 page table을 사용해버려
2. Page Table 크기가 너무 크다는 문제점 해결

---

1. Memory Management Policy

• 만약 더 큰 주소 공간을 위한 프로세스를 위해서는 OS는 어떤 작업을 취해야 할까?
  • page table 자체를 disk에 둬버리는 거야
• Swap space : disk 내 page가 저장되어 있는 공간
  • OS는 swap 공간을 페이지 단위로 읽고 쓰기 위해 disk에서 page 주소를 알아야 함
  • swap 공간의 크기: 특정 시점에 사용될 수 있는 최대 page 수
• Present bit : memory에 있나? disk에 있나?
  • page가 memory에 없다면 page fault 실행하고 page fault handler가 이를 도와야 함
• page fault vs seg fault
  • page fault는 정상 접근으로, page가 memory에 없을 때 나타나는 현상. page를 disk에서 가져와 다시 실행
  • seg fault는 비정상 접근, 접근할 수 없는 주소에 접근하여 생기는 것. 발생 시 프로세스 종료
• page fault 처리
  • OS는 disk 주소에 대한 정보를 page table의 PTE에서 알아낼 수 있음.
  • 이렇게 알아낸 주소로 page 가져오면 **(physical 메모리)**에 할당,
  • page table의 present bit 업데이트 하여 page가 메모리에 존재한다는 것 기억
  • TLB에 해당 정보 업데이트
• memory full?
  • page evict → page 교체 정책
• 실제로는 이렇게까지 안하고, daemon으로 실행 (low watermark : background에서 swap out, high watermark: swap in)
• page 교체 정책
  • metric: average memory access time
  • → (hit시 걸리는 시간)+(miss시 걸리는 시간) = (p_hitt_m) + (p_misst_D)
  • oracle policy: 미래 예측
  • fifo: first in -first out
    • BELADY’S ANOMALY:cache 높일 떄 일시적으로 성능 더 안좋아짐
  • random
  • lru
  • random → 성능 다 똑같음
  • 파레토 분포 → lru가 성능 oracle과 유사
  • looping sequence: RAND가 제일 좋음 (fifo ,lru 성능 그지)
• LRU 최적화
  • use bit → page내에서 참조될 때마다 1f로 update
  • dirty bit → 수정된 page들은 후순위로 evict되도록
• prefetching : OS가 page가 사용될 것이라 예측하고 가져오는 거
• delayed write(pending write) : 쓰기 작업을 미뤘다 swap out 한번에 진행
• Thrashing : 프로세스들이 요구하는 메모리의 크기가 실제 메모리보다 큰 경우
  • memory is oversubscribed and the memory demands of the set of running processes exceeds the available physical memory