Virtual Memory

• toc {:toc}

Background

• 코드가 실행되기 위해서는 메모리에 있어야 한다.
• 하지만, 모든 프로그램이 전체적으로 실행되는 경우는 많지 않다. ⇒ 사용되지 않는 부분은 낭비 ——→ 그러면 사용하는 부분만 올려서 사용하자!

Virtual Memory

Physical memory로 부터 logical memory 분리

• 실행에 필요한 부분만 사용하자. → 실제 메모리에 안올렸지만 올린 것처럼 작동시켜야 함.

• Logical memory > Physical memory

• 장점

  • Address spaces를 더 많은 프로세스가 concurrent하게 사용 가능하다.
    • 각 프로그램이 실행되는 동안 더 적은 메모리를 사용한다.
    • CPU utilization과 throughput 증가된다.
  • Process creation을 할 때도 부담이 줄어든다.
  • Swap을 적게 해도 된다.

Virtual Address Space

• 프로세스가 어떻게 저장되는가에 대한 logical view
• 주로 0에서 시작해서 끝까지 이어진다. MMU가 logical to physical mapping 한다.

Demand Paging

• 아이디어 : 필요할 때 Page를 메모리로 가져오기

• Page 필요 > Page 참조 >

  • invalid > abort
  • not-in-memory > memory로 가져오기

• Swapping하는 paging system과 유사하다.

  • Lazy swapper : 필요할 때만 swap한다. 아니면 하지 않는다.
  • page fault handler인 pager를 통해서 swap한다.

With Valid-Invalid Bit

• 각 page entry에 valid-invalid bit 탑재
• Valid : 메모리 위에 있다. Memory resident
• Invalid : 메모리 위에 없다. > page fault > Swap in

Handling Page Fault

Page Fault handling 과정

1. 만약 page에 대한 참조가 있다면(가정), 첫번째 참조는 Lazy swapper를 사용해 swap 되지 않은 상태이기 때문에 trap(Page Fault)을 발생시킨다.
2. 운영체제가 다른 table을 확인한다. (if invalid > abort(중단), if not in memory > 빈 frame 필요)
3. Free frame을 찾는다.
4. Scheduled disk operation을 통해 page를 frame으로 swap in 한다.
5. Page table을 갱신한다.
6. Instruction을 재실행한다.

• 사례
  • 배경 : Logical memory에 A~H 까지 8개의 page 존재
  • Page table에 0, 2, 5번만 valid, 나머지는 invalid한 상태

7. Page B에 접근하고 싶은 상황. B에 접근
8. Invalid ⇒ Page fault 발생
9. Backing store에서 swap in 해서 데이터를 메인 메모리로 이동
10. Page table 업데이트 및 valid-invalid bit 업데이트
11. Page B에 접근 ———> Lazy swapper를 사용하면 처음에 page 접근할 때 page fault가 발생해야 swap in해서 메모리에 올릴 수 있다.

Performance of Demand Paging

• Page fault rate : p
  • 0 < p < 1
  • p = 0 이면 Page fault 가 발생하지 않는다.
  • P = 1 이면 Page fault 가 반드시 발생한다.
• Effective Access Time (EAT)
  • EAT = (memory access) + {(page fault overhead), (swap page out), (swap page in)}
  • Page fault가 발생하지 않았을 때 ⇒ 메모리 접근 시간만 소요
  • Page fault가 발생했을 때 overhead, swap 시간 소요

Copy-on-Write (COW)

• 부모, 자식 프로세스 모두 메모리에서 같은 page들을 공유하도록 허락하는 것
• 예시
  • P1 : 부모, P2 : 자식 같은 page A, B, C를 공유
  • 같은 페이지를 가지고 있다가 P1이 C를 수정
  • A, B, C 메모리 그대로 차지하고 있고 다른 free frame에 C 복사해 수정

Free-Frame List

• Free frame들을 list로 저장하고 있는 리스트.
• Free frame에 전형적으로 0을 채워 넣는다.
• ---⇒ 0을 채워 넣지 않으면 이전 값이 남아있을 수 있기 때문.
• 시스템이 처음에 시작하면 모든 사용 가능한 free frame은 free frame list에 저장된다.

Page Replacement

• Background

  • Free frame을 사용해서 디스크에서 메모리로 데이터를 이동시키는데, free frame이 없다면?
  • 원래 있던 page를 종료시키고 다음 page를 해당 frame에 놓자!
  • 어떤 기준으로 원래 있던 page 종료 시킬 것인가?
  • 기준? → 성능! ---⇒ 최대한 page fault가 발생하지 않고 빠르게 동작할 수 있도록 하자!

• Basic Page Replacement

1. 디스크에서 필요로 하는 page의 위치를 찾는다.
2. Free frame을 찾는다.
   1. 있다면 사용한다.
   2. 없다면 교체 알고리즘을 활용해 victim frame을 정한다.
   3. victim frame에 있는 page table의 dirty bit값이 활성화된 경우 디스크에 frame을 쓴다(저장).
3. 필요로 하는 page를 free frame으로 가져온다.
4. trap이 발생했던 instruction을 재시작한다.

---⇒ Victim frame, desired page 2개의 page transform이 발생한다.

Page Replacement Algorithm

Frame-allocation algorithm

• 얼마나 많은 frame을 각 프로세스에 할당해야 할까?

Page-replacement algorithm

• 얼마나 많은 frame들이 교체되는가?
• 가장 적게 page fault가 발생해야 한다.

평가를 진행하는데 Page reference string을 사용한다.

• Page reference string
  • Page 참조 순서를 저장해놓은 string

FIFO Page Replacement

• 가장 먼저 온, 가장 오래 있던 page가 victim이 되자.

• Reference string : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

• Frame 개수 3개로 가정

• Belady’s anomaly : 일반적으로, free frame의 수를 늘릴 수록 겹치는 page가 많아져 page fault가 덜 발생해야 하나, 오히려 더 증가하는 현상을 의미한다.

Optimal Page Replacement

• 가장 긴 시간 동안 사용되지 않을 예정인 page가 victim이 되자.

• 미래까지 고려한 알고리즘 → 미래를 고려할 수 없다. → 때문에 말 그대로 ‘최적’

• 현실적이지 않고, 알고리즘의 비교를 위해 사용한다.

• Reference string : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

• Frame 개수 3개로 가정

LRU(Least Recently Used) Page Replacement

• 가장 사용되지 않았던 page가 victim이 되자.

• Optim에서는 미래에 집중해서 진행했으나, LRU에서는 과거에 대해 집중해서 사용되지 않은 것을 선택한다.

• FIFO보다는 좋지만 Optim보다는 좋지 않다.

• 일반적으로 좋은 알고리즘이고 자주 사용된다.

• Reference string : 7, 0, 1, 2, 0, 3, 0, 4, 2, 3

• Frame 개수 3개로 가정

• LRU를 어떻게 구현하는가

  • Counter implementation
  • Stack implementation

Counter implementation

• 모든 page entry에 counter가 존재한다. Page가 참조될 때마다 counter가 clock을 copy하고, time stemp가 가장 이전의 것이 victim이 된다.
• Page가 변경돼야 할 때, counter가 가장 작은 값을 가진 것을 찾는다.
  • Frame이 많으면 search overhead가 증가한다. Time stemp 값을 하나씩 비교 해야 하기 때문.

Stack implementation

• Double link로 연결된 page number stack을 유지한다.
• Page가 참조되면 맨 위로 보낸다.
  • 6개의 포인터를 조정해야 한다.
• 가장 밑에 있는 page를 교체하면 되기 때문에 search할 필요는 없지만 매 업데이트가 비싸다.

LRU Approximation Algorithms

• LRU 알고리즘 구현을 위해서는 counter, stack등 적절한 하드웨어의 지원이 필요하다.
• LRU는 Reference bit를 사용해 하드웨어 지원없이 LRU와 비슷한 알고리즘을 구현한다.
• Reference bit
  • 초기에 0으로 초기화된다.
  • Page가 참조되면 1로 바뀐다.
  • Reference bit = 0 인 것 중 하나를 랜덤으로 선택해서 변경한다.

Second-chance algorithm

• 일반적으로는 FIFO이나, reference bit를 사용한 알고리즘.
• 원형 큐로 구성되어 reference bit를 사용해 1일 때 봐주고 0이면 교체한다.
• 모든 reference bit가 1이면 FIFO를 따른다.

Global / Local Replacement

• Global Replacement : 프로세스가 컴퓨터 모든 frame의 집합으로부터 frame을 교체할 수 있다.
  • 다른 프로세스에 할당된 page frame을 빼앗을 수 있다.
  • 프로세스 실행 시간이 매우 다양할 수 있다.
  • Throughput이 더 크기 때문에 더 흔하게 사용된다.
• Local Replacement : 각 프로세스가 할당된 frame의 집합에서만 frame을 선택할 수 있다.
  • Local 마다 알고리즘을 다르게 설정할 수 있다.
  • 프로세스마다 성능이 더 일정하다.
  • 프로세스마다 사용할 양을 정확히 알지 못하기 때문에

Thrashing

• 정의 : 프로세스가 swapping하느라 바쁜 상태 swap위해 대기중 > 메인 메모리 부족 > 성능 하락
  • 프로세스가 충분한 페이지를 가지고 있지 않다면 page fault rate가 매우 커진다.
  • CPU 사용량이 줄어든다. → 사용량이 줄어드니 OS는 더 많은 프로세스를 투입해야겠다고 생각한다. → Thrashing 심화

1. 운영체제 → CPU 이용률 감시
2. 이용률이 너무 낮아지면 새로운 프로세스 시스템에 추가하여 다중 프로그래밍 정도를 높인다.
3. 이 때, global replacement를 사용해 어떤 프로세스의 페이지인지 고려하지 않고 교체한다.
4. 교체된 페이지들이 해당 프로세스에서 필요로 하는 것이라면 다시 page fault를 발생시킨다.
5. 또 다른 프로세스에서 frame을 가져온다.
6. Page swap in, out을 위해 paging을 사용해야 하는데, 이를 사용하기 위해 queueing이 진행되고 ready queue는 비게 된다.
7. 기다리는 동안 CPU 이용률이 떨어지고 OS는 새로운 프로세스를 추가한다.
8. 더 많은 page fault가 발생한다.

Global replacement를 사용하면 전체에 영향을 주게 된다. Local, priority page replacement를 사용해 영향을 제한할 수 있다.

• Locality model
  • 할당된 frame보다 프로세스의 크기가 더 클 때 thrashing 발생
  • size of locality > total memory size (Thrashing 발생 조건)
  • 프로세서가 처리될 때 메모리 접근 요청이 발생하는 데, 접근 요청 메모리 위치는 패턴을 가지고 있다. ⇒ 특정 영역에서 집중적으로 접근 요청이 된다.

Working-Set Model

• Locality를 어떻게 계산할까?
• 필요한 부분을 집중적으로 참조하는 것(메모리에 올리는 것).
• Delta = Window Size = 페이지 참조의 고정
• (프로세스 의 Working set size) = 가장 최근 Delta동안 접근한 총 페이지 수
  • Delta가 너무 작으면 전체 locality를 확인하기 어렵다.
  • Delta가 너무 크면 여러 locality들을 동반한다.
  • Delta가 infinite하면 전체 프로그램을 동반한다.
• = total demand frames = 요구되는 총 frame 수
  • Locality 근사
  • Delta에 따라서 WSS가 하나의 locality를 가지고 있다고 보장할 수 없다. 하지만 대략적으로 얼마나 locality를 가지고 있는지 확인할 수 있다는 점에서 근사한다 할 수 있다.
• 만약 D > m (m : 할당된 frame)이면 Thrashing

Page-Fault Frequency (PFF)

• 수용 가능한 최대의 page fault 빈도수를 설정해놓고 local replacement 정책을 사용하는 것
  • Page fault rate의 상한, 하한선을 정한다.
  • 상한선보다 높은 경우 page fault가 많이 발생하므로 더 많은 frame을 할당해준다.
  • 하한선보다 낮은 경우 page fault가 적게 발생하므로 frame 수를 줄인다.
• WSS는 직접적으로 page fault를 측정하지 않지만 PFF의 경우 page fault rate를 측정해 조절하기 때문에 더 직접적인 방식이다.

Allocating Kernel Memory

이전까지는 User memory에 대한 내용 User memory와는 다르게 대우한다. Free-memory pool에서 할당한다.

• User : malloc → paging → frames에 대응
• Kernel : kmalloc → 나누지 않고 contiguous하게 할당한다.
  • Paging을 하면 느려지기 때문에 contiguous하게 사용

Buddy System Allocator

• 고정된 크기의 segment를 할당해준다.
• 고정된 크기 = 2의 n승 (최소 4K 이상 가진다.)
  • 만약, 요청된 사이즈가 3K일지라도 올림하여 4K를 할당해준다.
  • 비어있는 메모리가 256K일 때 만약 21K를 할당하고 싶다면 (매우 작은 할당을 필요로 한다면) 현재 메모리를 2개씩 나눠가며 최소 크기를 찾는다.
• 장점 : 사용하지 않는 chunk들을 더 큰 chunck로 빠르게 합칠 수 있다.
• 단점 : 2의 n승으로 분할되기 때문에 internal framentation이 발생한다.

Slab Allocator

• Slab : 물리적으로 연속된 페이지들로 구성되어 있는 영역
• Cache : Slab에서 사용되는 임시 보관소 개념. 하나 이상의 slab으로 구성되어 있다.
• Slab은 미리 다양한 사이즈의 cache를 만들어 놓는 것이다. 각 cache는 빈 object(structure)로 채워진다.
• Structure를 미리 만들어 놓아 요청이 있을 때 바로바로 할당해주고 사용이 완료되면 회수한다.
• 처음 cache 생성 → free로 표시 / cache에 structure 저장 → used로 표시
• Slab state : Full (=all used) / Empty (=all free) / Partial (=mix of free and used)
• 빈 slab이 없다면 새로운 slab을 할당한다.
• Cache에서 각 크기마다의 Object를 가지고 있어 fragmentation을 발생시키지 않는다.
• 미리 만들어 놓았기 때문에 빠르게 메모리 요청을 만족시킨다.