Virtual Memory

Virtual Memory

 Virtual Memory(논리적 메모리. OS 관여)

 - Separation of user logical memory from physical memory.

  How can we implement Virtual memory?

 - 90-10 rule : programs spend 90% of their time in 10% of their code

 - Wasteful to require all of user's code to be in memory

 -> only part of the program needs to be in memory for execution

 -> need to allow pages to be swapped in and out

 -> demand paging

 Demand Paging

 - 실제로 필요할 때 page를 메모리에 올리는 것 : I/O 양의 감소, Memory 사용량 감소(물리적으로.), 빠른 응답 시간(하나의 프로세스가 아니라 전체를 봤을때), 더 많은 사용자 수용.(더 많은 프로세스를 올릴 수 있다.)

 - Valid/Invalid bit의 사용 : Invalid의 의미 - 사용되지 않는 주소 영역인 경우.  페이지가 물리적 메모리에 없는 경우.

                                   처음에는 모든 page entry가 invalid로 초기화.

                                   address translation 시에 invalid bit이 set되어 있으면 => "page fault"

  Page Fault

 - invalid page를 접근하면 MMU가 trap을 발생시킴.(page fault trap)

 - Kernel mode로 들어가서 page fault handler가 invoke 됨.

 - page fault 처리 순서

   1. Invalid reference? (eg. bad address, protection violation)

   2. Get an empty page frame. (없으면 뺏어온다 : replace) 공간확보

   3. 해당 페이지를 disk에서 memory로 읽어온다.

       1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)

       2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"

       3. ready queue에 process를 insert -> dispatch later

       4. 이 프로세스가 CPU를 잡고 다시 running

       5. 아까 중단되었던 instruction을 재개

  Free frame이 없는 경우

 - Page replacement : 어떤 frame을 빼앗아올지 결정해야 함.  곧바로 사용되지 않을 page를 쫓아내는 것이 좋음. (쫓아낸 page가 바로 사용되야하면 overhead).  동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음.

 - Replacement Algorithm : page-fault rate를 최소화하는 것이 목표.

  Optimal Algorithm

 - MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace

 - 미래의 참조를 어떻게 아는가? : Offline algorithm

 - 다른 알고리즘 성능에 대한 upper bound를 제공한다. (다른 알고리즘의 기준점이 되기 때문.)

   Belady's optimal algorithm, MIN, OPT 등으로 불림.

  FIFO(First in First Out) Algorithm

 - FIFO : 먼저 들어온 것을 먼저 내쫓음.

   frame 늘어날때마다 page fault를 줄여야 상식인데, 오히려 늘어나는 오류 발생이 가능하다.

  LRU(Least Recently Used) Algorithm

 - LRU : 가장 오래 전에 참조된 것을 지움.

  LFU(Least Frequently Used) Algorithm

 - LFU : 참조 횟수(reference count)가 가장 적은 객체를 지운다.

           Counting algorithm

           최저 참조 횟수인 page가 여럿 있는 경우 : LFU 알고리즘 자체에서는 여러 page중 임의로 선정한다. 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다.

           장단점 : LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있다. but 참조 시점의 최근성을 반영하지 못한다. LRU보다 구현이 복잡하다.

  * OS는 참조횟수 같은 것을 알 수 없다.(HW에서 처리)  아는건 단지 1번, 2번 사용했다라는 것.(page fault만 안다.) 중간 단계를 모르기 때문에, LFU와 LRU를 사용하지 못한다.(virtual에서, cache는 가능) ==> Clock Algorithm

  Clock Algorithm(=Second Chance Algorithm)

 - LRU의 근사(approximation) 알고리즘

 - Reference bit을 사용해서 교체 대상 페이지 선정(circular list) : Reference bit=0 -> never reference, Reference bit=1 -> yes, referenced.(HW에서 참조됨.)

 - reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동.

 - 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈.

 - 한 바퀴 되돌아와서도(=second chance) 0 이면 그때에는 replace 당함.

 - 자주 사용되는 페이지라면 second chance가 올 때 1.

  Clock Algorithm의 개선

 - Enhanced Second Chance (=NUR : Not Used Recently) : reference bit와 modified bit(dirty bit)를 함께 사용.  reference bit = 1 : 최근에 참조된 페이지 빈번사용?  ,  modified bit=1 -> 최근에 변경된 페이지 : I/O 유발하는가?

  Page Frame의 Allocation

 - Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?

 - Allocation의 필요성 : 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지 동시 참조 -> 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음. 

                               Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함 -> 최소한의 allocation이 없으면 매 loop 마다 page fault.

  Global vs Local Replacement

 - Global replacement : Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다.  Process별 할당량을 조절하는 또 다른 방법임.  FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당.  Working set, PFF 알고리즘 사용.

 - Local replacement :  자신에게 할당된 frame 내에서만 replacement.  FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영 시.

  Thrashing

 - 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우에 발생.  Page fault rate가 매우 높아지고 CPU utilization이 낮아진다.

 - OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단.

 - 또 다른 프로세스가 시스템에 추가됨(higher MPD)

 - 프로세스 당 할당된 frame의 수가 더욱 감소

 - 프로세스는 page의 swap in/out 으로 매우 바쁨

 - 대부분의 시간에 CPU는 한가함.  low throughput

  Working-Set Model

 

 - Locality of reference : 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조. 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함.

 - Working-set Model : Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함.   Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend).   Thrashing을 방지하고 Multiprogramming degree를 결정한다.

  Working-Set Algorithm

 - Working set의 결정 : Working set window를 통해 알아낸다. window size에 따라, Working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버린다. 참조된 후 size 시간 동안 해당 page를 메모리에 유지한 후 버린다.

 - Process들의 working set size의 합이 page frame의 수보다 큰 경우 : 일부 process를 swap out시켜 남은 process의 working set을 우선적으로 충족시켜 준다.(MPD를 줄임)   

   Working set을 다 할당하고도 page frame이 남는 경우 :  Swap out 되었던 프로세스에게 working set을 할당(MPD를 키움)

 - Window size : Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 한다. 값이 너무 작으면 locality set을 모두 수용하지 못할 우려가 있다.(for문 돌릴때 비효율)  값이 너무 크면 여러 규모의 locality set 수용.(필요없는 데이터들도 올라올 수 있다. -> 많은 프로세스가 올라올 수 없다.)  값이 무한대이면 전체 프로그램을 구성하는 page를 working set으로 간주한다.

 * 1 2 3 4 에서 window size가 3인데, 만약 가지고 있는 frame이 2개라면? -> 아예 할당을 해주지 않는다 -> (abort) 지금 실행하지 않고 나중에 한다 -> PFF

  PFF(Page-Fault Frequency) Scheme

 - page-fault rate의 상한 값과 하한 값을 둔다.  :  Page falut rate가 상한 값을 넘으면 frame을 더 할당한다.  Page fault rate가 하한 값 이하이면 할당 frame 수를 줄인다.

 - 빈 frame이 없으면 일부 프로세스를 swap out.

  Page size의 결정

 - Page size를 감소시키면  :  페이지의 수 증가, 페이지 테이블 크기의 증가, Internal fragmentation 감소, Disk transfer의 효율성 감소, 필요한 정보만 메모리에 올라와 메모리 이용이 효율적.(Locality 활용 측면에서는 좋지 않다.)

 - Trend : Larger page size.  32 bit 4KB에서 대용량 page로의 추세.