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 을 발생시키지 않는다.
• 미리 만들어 놓았기 때문에 빠르게 메모리 요청을 만족시킨다.