Virtual Memory?

메모리를 가상화하는 기법.
사용자 입장에서는 주소 0x0 ~ 0xFFFFF... 까지의 엄청 큰 공간으로 인식한다.
-> 프로그래밍 상에서의 제약 조건이 사라짐.
필요한 부분만

Demand Paging

프로세스의 모든 메모리를 physical memory에 올려놓는 것이 아닌, 프로세스의 해당 메모리 page가 필요할 때 그 page를 physical memory에 올려놓는 것.
사용되지 않는 메모리는 애초에 로드되지 않으므로 메모리 효율이 증가한다.

Basic Concepts

• Demand Paging을 사용하게 된다면, 프로세스의 일부 page만 load되므로, 이를 구별하는 방법이 필요. -> page table의 valid-invalid bit이 사용될 수 있다.
• 기존의 valid-invalid는 해당 page를 프로세스가 사용하냐 / 안하냐의 문제였지만, demand paging의 관점에서는 좀 달라짐.
  • valid : 해당 page를 프로세스가 사용하며, 동시에 memory에 load되어 있다.
  • invalid : 해당 page를 프로세스가 사용하지 않거나, memory에 load되어 있지 않다.
• page fault : load되지 않은 page에 프로세스가 접근하려고 하는 경우 발생. -> OS에 trap을 전달함.
  page fault handling
  1. internal table 확인(보통 PCB에 있음)
  2. 접근이 invalid -> 프로세스 terminate. 접근이 valid -> page in한다.
  3. free frame을 찾는다.
  4. secondary storage operation을 스케줄한다.
  5. 해당 page를 memory에 load시키고, page table과 프로세스의 internal table을 업데이트 한다.
  6. interrupt 되었던 instruction을 재시작한다.
• pure demand paging : required되기 전까지 아예 page를 memory에 가져오지 않는 방법.
• locality of reference : 메모리 참조에는 locality가 있다는 것. 나중에 설명할 예정.

Demand paging을 위한 Hardware Support -> paging and swapping과 동일. (page table, secondary memory)

Free-Frame List

• page fault를 해결하기 위한 방법.
• free-frame list를 만들어서 frame들을 관리한다.
• Zero-fill-on-demand : frame이 할당되기 전에 모두 0으로 채우는 것. (보안상의 이유 - 이전 데이터를 남겨놓지 않기 위함)

Performance of Demand Paging

demand-paged memory에 대한 effective access time을 구해보자.

• ma : memory-access time
• p : probability of a page fault $(0 \le p \le 1)$

==> effective access time = $(1-p) \times ma + p \times$page fault time

• 그래서 page fault time은 어떻게 구함?
  page fault시에 동작 과정

  1. OS에 trap을 넣음
  2. register와 process 상태를 저장
  3. interrupt가 page fault라는 것을 확인
  4. page reference가 legal하다는 것을 확인, 그리고 secondary storage에서의 page의 위치 확인
  5. storage에서 free frame으로의 read를 발생시킴.
     a. read request가 service될 때 까지 queue에서 대기
     b. device seek / latency time동안 기다림
     c. page를 free frame으로 옮김
  6. 기다리는 동안, CPU를 다른 프로세스에게 넘겨줌 (DMA가 있기에 가능)
  7. storage I/O subsystem에서 interrupt 수신
  8. 6이 실행되었다면, 현재 실행중이던 다른 프로세스의 상태를 저장
  9. interrupt가 secondary storage device로 부터 왔다는 것을 확인
  10. page table을 비롯한 다른 테이블들을 고친다. (메모리에 존재한다는 사실로)
  11. 다시 프로세스로 CPU가 할당되기를 기다린다.
  12. register, process state, new page table을 복원, interrupted instruction을 다시 수행.

  핵심 task 3가지

  1. Service the page-fault interrupt
  2. Read in the page
  3. Restart the process

대충 page fault time을 8ms, ma = 200ns 라고 한다면,
effective access time = $200+7,999,800\times p$가 된다. -> p에 비례함.

Copy-on-Write

• fork() 시스템 콜
  부모 프로세스의 모든 메모리를 복사해야 하므로 굉장히 overhead가 크다. 그것을 해결하기 위한 방법으로 copy-on-write가 나옴.
• copy-on-write
  말 뜻 그대로다. write할 때 copy한다는 뜻으로, fork()를 실행했을 때 메모리 복사가 이루어 지지 않고, 그냥 shared page 상태로 존재한다. 그러다가 수정이 되는 순간 해당 page가 복사가 이루어지게 된다. 물론, copy-on-write 상태라는 것을 mark 해 두어야 한다. (어딘지는 잘 모르겠음)
• vfork() 시스템 콜
  중요한 건 아니지만, 이런 시스템 콜이 있다는 것 정도..?
  fork()랑 똑같은데, 메모리 복사가 아예 일어나지 않는다. -> 자식 프로세스에서 바로 execve를 호출하는 경우를 위해 만들어짐. 만약 복사된 메모리의 수정을 한다면 주의해야 한다.

Page Replacement

만약 메모리가 할당되어야 하는데 free frame이 없다? -> 전체 프로세스를 swap out하는 것이 아닌, 사용되지 않는 일부 page만 swap out한다. -> 효율성 증대.
하지만 이 경우에도 단점이 존재 : page replacement가 일어날 때에는 swap out, swap in의 2가지가 다 실행되어야 한다.

해결 방안

modify bit (혹은 dirty bit)를 설정하여 0이면 바뀌지 않음, 1이면 바뀜으로 생각해서 바뀌었을 때에만 page out을 하고, 그렇지 않다면 page out을 하지 않고 page in만 수행한다. 물론 page table들의 valid / invalid bit은 설정을 해야겠지만.

장점

실제로 virtual memory가 이름값을 하게 한다. demand paging과 함께 page replacement가 이루어진다면, physical memory의 크기에 구애받지 않고 동작할 수 있다.

replacement 효율 계산 방법

메모리 참조 예시를 통해 page fault 횟수를 계산한다. 다음 2 가지 사실을 이용하여 계산함:

• page number단위로 계산함. (주소단위로 계산 x)
• p라는 page를 사용한 바로 다음 p라는 page를 사용한다면, page fault는 일어나지 않는다.

FIFO Page Replacement

• 가장 먼저 들어온 page를 교체하는 알고리즘.
• 되게 자주 사용되는 page도 오래되면 교체되어 버린다는 단점이 있음.
• Belady's anomaly
  무조건 frame이 많다고 page fault가 적게 일어나는 것이 아니다. 오히려 page fault가 많아지는 반례도 존재함.

Optimal Page Replacement

이론상 제일 적은 page-fault를 발생시키고, Belady's anomaly를 발생시키지 않는다.

• 알고리즘
  제일 오래 사용되지 않을 page를 교체하는 방법.
• 단점
  page 사용에 대한 미래 정보를 다 알고 있어야 한다. -> page-fault 효율을 측정하기 위한 척도로 사용됨.

LRU Page Replacement

과거 정보를 통해 미래를 예측한다.

• 알고리즘
  가장 이전에 사용되었던 page를 교체하는 방법. (least recently used)

• 구현 방법

  • Counter 사용
    각 page-table entry마다 time-of-use field를 놓고 사용될 때 마다 counter의 값을 time-of-use field에 써넣는다. (counter는 점점 증가함)
    제일 이전에 사용된 page의 경우, time-of-use값이 제일 작으므로, 그 page를 선택 -> replacement 수행.
  • Stack 사용
    스택에 쌓으면서 사용될 때 마다 스택의 위로 다시 올린다.
    제일 이전에 사용된 page의 경우, 스택의 제일 아래에 존재할 것이므로, 그 page를 선택 -> replacement 수행.

• Belady's anomaly가 존재하지 않는다.

• LRU의 경우, frame이 n개인 경우에 현재 시점에 들어있는 page들은 모두 frame이 n + 1개인 경우에 현재 시점에 들어있는 page에 포함된다.
  알고리즘에 의해 가장 최근 n개의 page가 frame에 존재 -> n + 1의 경우 가장 최근 n + 1개가 존재, 당연히 가장 최근 n개는 n + 1개에 포함됨.

• 매 memory reference마다 LRU 정보에 대한 업데이트가 진행되어야 함, TLB 레지스터의 도움을 필요로 한다.

LRU-Approximation Page-Replacement

LRU를 위한 hardware support가 없는경우?

• reference bit이 존재. -> page가 referenced 될 때 set된다. -> referenced된 page인지 아닌지 구분 가능.

Additional-Reference-Bits Algorithm

각 page마다 8비트짜리를 놓고 매 count 마다 해당 page가 사용되었는지 업데이트함. 업데이트 할 때, >>로 1번 shift 후에, 최상위 비트에 사용되었으면 1, 아니면 0으로 값을 바꾼다.
unsigned int 관점에서, 제일 적은 숫자를 가진 page가 바뀔 대상이 된다.

Second-Chance Algorithm

• reference bit이 하나만 있는 경우에 해당.
• circular queue를 이용해서, reference가 이루어진 page에 대해서는 reference bit을 0으로 만들고, 이미 reference bit이 0인 경우에는 그 page를 replace한 후, 그 자리에 새 page를 집어넣는 방식으로 동작함. (clock algorithm)
• 모든 bit이 set되면(? 내 생각에는 unset인듯) FIFO replacement와 동일하게 된다.

Enhanced Second-Chance Algorithm

reference bit에 더해 modify bit도 같이 사용한다.
똑같이 clock algorithm을 사용, 대신 victim을 선택할 때 reference bit과 modify bit 모두 0인 page를 replace한다.

Counting-Based Page Replacement

• least frequently used(LFU)
  • 사용된 횟수가 가장 적은 것을 대상으로 함.
  • 장점 : active한 page일수록 참조횟수가 많다.
  • 단점 : 초반에 active하다가 후반에 아예 안 사용될 수도 있음. -> 시간 지날수록 bit shift -> 일종의 aging 개념 도입.
• most frequently used(MFU)
  • 오히려 사용횟수가 적은 page의 경우 앞으로 사용될 가능성이 많으므로 고르지 않는다.

얘네들은 너무 구리다.

Page-Buffering Algorithms

victim 선택 알고리즘은 아니고, 병행하면 좋은 알고리즘.
swap out -> swap in -> 프로세스 실행은 오래 걸리니까, 순서를 swap in -> 프로세스 실행으로 바꾸고, swap out은 보류한다. (특히 modified page의 경우)

• free frame pool이 있다고 생각.

방법

• paging device가 idle상태가 되었을 때 second storage에다가 기록한다.
• 어느 page가 어느 frame에 할당되었는지에 대한 정보를 가진 채 free frame pool에 들어감. replacement가 일어날 때, 이 frame pool에 해당 page에 대한 정보가 있는 frame이 있다면 swap in 하지말고 그냥 바로 가져온다.

Applications and Page Replacement

특정 application의 경우 자기 자신이 메모리 사용 방식에 대해 더 잘 알기 때문에 운영체제보다 더 잘 관리할 수도 있음.

Allocation of Frames

프로세스 별로 할당되는 frame 수는 어떻게 조절할까?

Minimum Number of Frames

아키텍쳐마다 다름.
만약 한 instruction이 최소 3 개의 frame을 필요로 한다면, 이 아키텍쳐의 프로세스는 적어도 3개의 frame을 갖고 있어야 한다. 만약 2 이하라면, 연산 수행 -> page fault -> page replacement -> 다시 연산 수행 -> 2개밖에 없으니까 또 page fault -> ... 무한반복

Allocation Algorithms

전체 m frames, n processes라고 하자.

• equal allocation
  제일 쉬운 방법.
  각자에게 m / n만큼 나눠주기
  프로세스마다 필요한 메모리 양이 다르기 때문에 굉장히 비효율적이다.
• proportional allocation
  프로세스의 크기에 비례해서 메모리 할당해줌
  각 프로세스 $p_i$가 사용하는 메모리를 $s_i$라고 했을 때,
  $S=\Sigma s_i$ 라고 정의하자.
  그러면 $p_i$에게 할당하는 frame 수 = $a_i$라고 하면,
  $a_i=s_i/S\times m$이 된다.

이 외에도 단순 프로세스의 크기 뿐만 아니라 우선순위에 따라 분배해주는 방식 등 여러 방법이 있다.

Global versus Local Allocation

• global replacement
  모든 frame을 대상으로 replacement를 수행하는 것.
  성능이 좋다. -> 일반적으로 이 방법이 쓰임
  But 같은 프로세스일지라도 실행 순간마다 시간이 다르게 걸릴 수 있다.
• local replacement
  각 프로세스는 자신의 frame 내부에서만 replacement를 수행한다.
  성능이 떨어짐.
  항상 같은 결과를 낸다.
• Major & Minor fault -> 그냥 간단하게만.
  • major : page가 memory에 없는 경우. backing store로부터 가져와야 함.
  • minor : page로의 logical mapping이 없다. page는 메모리에 존재. ex) shared memory 인데 아직 mapping만 안됨.

• minimum threshold를 정해놓고, 그것보다 free memory가 내려가면 page reclaim을 수행하기 시작 (reapers)
• maximum threshold를 정해놓고, 그것보다 free memory가 올라가면 reaper routine이 중단된다.

만약 minimum threshold를 유지하지 못하고 그 아래로 떨어진다면?

• aggressively reclaim pages.

엄청 아래로 떨어진다면?

• out-of-memory(OOM) killer routine이 실행됨. -> process를 골라서 terminate 시킨다.
• OOM 기준? -> 프로세스가 사용하는 퍼센티지가 클수록 높은 OOM score -> 얘가 먼저 terminate 된다.

Non-Uniform Memory Access (넘어감)

Thrashing

Thrashing : executing보다 더 많은 시간을 paging에 보내는 경우.

Cause of Thrashing

• 전제: CPU utilization이 떨어지면 scheduler는 Degree of Multiprogramming을 높이려고 한다. & global replacement algorithm (얘가 일반적임)

어느 한 프로세스가 많은 page를 필요로 함 -> page fault 발생 -> global replacement algorithm으로 다른 프로세스들의 메모리를 뺏음 -> 뺏은 메모리는 굉장히 active한 녀석이었다. -> 뺏긴 프로세스가 다시 page fault 발생 (다른 프로세스의 메모리를 또 뺏어옴) -> page fault가 너무 많이 발생 -> Paging device의 queue에 너무 많은 프로세스가 쌓임 -> CPU utilization이 줄어들음 -> 더 많은 프로세스를 메모리에 넣음 -> 반복...

• 줄이는 법
  • local replacement algorithm
    프로세스는 자신으로부터만 replacement를 수행
    만약 thrashing이 발생하더라도 다른 프로세스에 영향을 끼치지 않음.
  • locality model 이용
    대부분의 프로세스는 locality를 따라서 메모리를 사용한다. 즉, 예를들면 1~2 page를 많이 쓰다가 옮겨가서 7~8 page를 많이쓰다가 옮겨가서 ... 이런식으로.
    이 locality마다 요구하는 page를 할당하고, 이를 다음 locality로 가기 전까지 사용하는 방식으로 page fault를 줄일 수 있다.

Working-Set Model

$\Delta$ : working-set window
가장 최근 $\Delta$ page reference를 알기 위함이다. -> working set이라고 부름.
$WSS_i$ : working-set size,
total demand for frames $D=\Sigma WSS_i$
만약 $(D > m)$이라면 thrashing이 발생함.

• 사용 방법
  OS가 각 프로세스의 working set을 알고 있으면, 전체 frame에 대해 여유가 있다면 추가 프로세스를 들어오게 할 수 있고, 꽉 찰 것 같으면 프로세스를 suspend 시킬 수 있다.

Page-Fault Frequency (PFF)

PFF에 upper bound, lower bound를 설정해서 upperbound를 넘어서면 frame 할당량을 늘리고, lowerbound 아래로 내려가면 frame 할당량을 줄이는 방법이다.

Memory Compression

7 free-frame에다가 modified frame 15, 3, 35를 compressed해서 집어넣고, 15, 3, 35는 free frame list로 들어간다. (swap out되지 않게)
만약에 15로의 page 접근이 생긴다면, page fault 발생 후 압축되어 있던 15, 3, 35는 다시 frame에 할당된다.

Allocating Kernel Memory

커널의 경우, 아키텍쳐 의존으로 설계되지 않음 -> page 단위로 메모리 할당을 하기에는 fragmentation과 같은 메모리 낭비의 가능성이 높다.

또한, hardware device들은 직접 physical memory에 접근하므로, 연속적으로 커널 메모리가 할당되는 것이 좋다.

-> kernel만의 고유한 메모리 관리 기법이 필요.

• Buddy System
  2의 제곱수를 기준으로 하여 메모리를 할당함. 예를 들면, 11KB의 경우, 11KB보다 크지만 가장 작은 2의 제곱수인 16KB가 할당된다.
  전체 256KB의 segment가 존재할 때 21KB를 요청한다면,
  256 -> 128 2
  128 -> 64 2
  64 -> 32 * 2
  즉, 256 -> 128 + 64 + 32 + 32의 형태로 쪼개져서 32KB가 할당되게 된다.

  • coalescing
    인접한 사용되지 않는 buddy들은 하나로 합쳐질 수 있다.
  • 단점
    2의 제곱수가 기준이므로 fragmentation이 발생 가능.

• Slab Allocation
  

  • slab : 하나 이상의 page로 구성됨.
    • full : slab의 모든 object가 used 상태임
    • empty : slab의 모든 object가 free 상태임
    • Partial : slab은 used와 free 상태의 object를 모두 가지고 있음
  • cache : 하나 이상의 slab로 구성됨.
    cache 하나는 자료구조 하나에 해당하는 메모리 할당을 수행한다.
    cache는 미리 해당 자료구조 여러 개로 할당되어 있다.
    예를 들면, task_struct 할당 요청이 들어옴
    • 먼저 partial slab에서 object를 할당해 준다.
    • partial slab이 없음 -> empty slab에서 새로 free object를 할당 -> 나눠줌
    • empty slab도 없다 -> contiguous physical page에서 새로 slab이 할당됨.
  • 장점
    • 해당 자료구조의 크기에 알맞게 할당하므로 fragmentation이 발생하지 않는다.
    • 미리 free 상태로 할당해놓고 필요할 때 꺼내 쓰므로 속도가 빠르다.

Other Consideration

Prepaging

• pure demand paging의 경우, 처음 locality를 만들기 위해서 page fault가 많이 발생함. -> 이를 고려해서 page fault를 발생시키지 않고, 한꺼번에 미리 locality를 만족하는 page들을 메모리로 가져온다.

• cost of prepaging (prepaging으로 가져왔지만 사용되지 않음) vs cost of servicing page faults

  • s : # of prepaged pages
  • $\alpha$ : fraction of s pages actually used

  당연히 $\alpha$가 0에 가까울 수록 prepaging이 안 좋고, 1에 가까울 수록 prepaging이 좋다.

Page Size

Page size 결정하는 법?

• page size와 page table의 크기는 반비례함.
• page size와 internal fragmentation은 비례함.
• I/O time과 page size는 반비례함.
  데이터 전송 자체는 오래 걸리지 않는다. (ex : 0.01ms)
  대신, latency time, seek time이 더 오래 걸림. (ex : 3ms, 5ms)
  I/O는 page 단위로 이루어져야 하므로, page size가 2배인 아키텍쳐의 경우 사실상 2배 더 적은 I/O 시간이 걸린다.
• Page size가 큼 -> 필요없는 부분도 메모리에 올라갈 수 있다.
  -> small page has better resolution
• Page size가 큼 -> page fault가 덜 발생함.

어쨌든 결론 : 굉장히 다양한 요인들이 있다.

TLB Reach

TLB Reach = TLB entries * page size
즉, 메모리 상에서 TLB를 통해 직접적으로 접근할 수 있는 메모리 용량.

• 당연히 page의 크기가 클 수록 TLB reach가 커지겠지만, 그에 따른 fragmentation도 커진다.

Inverted Page Tables

Page table의 사이즈를 줄여주는 이점은 확실히 있음.
But demand paging에서는 해당 page가 memory에 있는지 없는지에 대한 정보는 표시되지 않는다. -> 결국 프로세스별로 external page table이 필요함.
...

뒤에는 한 번씩 읽어보기만 해야지.

참고 자료

• Operating System Concepts, 10th edition