Virtual Memory

Virtual Memory

1.   Back Ground

·       프로세스 전체를 메모리에 올리지 않고도 실행이 되도록 한다. -> 메모리 크기보다 큰 프로그램 수행 가능해 진다.

·       프로세스 실행 시, 전체 프로세스가 항상 메모리에 있어야 하는 것은 아니다.(ex) 발생 빈도 낮은 예외 처리 루틴 등)

·       실제의 물리 메모리와 논리 메모리 개념을 분리하여 사용한다.

·       Page 단위로 swap in & swap out이 이루어 진다.(by pager)

2.   Demand Paging

·       그때그때 필요한 page를 메모리로 올리자.

·       Pager(Lazy swapper) : 해당 page가 필요하기 전까지는 올리지 않는다.( cf - swap은 프로세스를 대상으로 이루어짐.)

·       I/O 감소, 메모리 사용량 감소, 빠른 반응속도, throughput, utilization 증가.

·       이를 위해 어느 페이지가 메모리에 있는지 알아야 한다 -> Valid-Invalid Bit를 사용.

o   Valid : in memory

o   Invalid : not in memory or not legal (메모리에 없거나, 디스크 값이 갱신되었음 ex) 공항 예약 시스템)

·       기존 paging에서는 protection을 위해 사용되었음.

o   처음에는 전부 Invalid로 초기화.(안 올라와 있으므로)

o   접근하고자 하는 page table의 항목이 Invalid라면, page fault trap 발생.

·       Pure demand paging : 필요하기 전까지는 swap in x, 메모리에 page를 올리지 않고 프로세스를 시작하는 방법.

·       Page fault

·       Invalid page 접근 시 MMU trap(page fault trap) 발생. -> page fault handler 수행.

o   Page fault 발생시, OS는 PCB와 page table을 보고, invalid reference인지 검사.(protection 침해 여부 등.)

1-1) invalid reference 라면 프로세스 중단.

1-2) not in memory 라면, 빈 frame을 찾는다.(없다면 replace) + process를 wait 상태로 만든다.(I/O 해야하니까)

 2)  디스크로부터 page를 읽어와 해당 frame에 넣는다. I/O 종료 후 process는 ready 큐로 이동하여, dispatch를 기다린다.

 3)  page table의 값을 갱신한다.(invalid -> valid, frame number 등)

 4)  해당 process가 다시 CPU를 받으면, Page fault trap이 종료된다.

 5)  page fault를 발생시켰던 instruction부터 다시 수행한다.

·       Page fault : instruction fetch 중 발생했다면, page 올린 후 다시 수행하면 돼.

                operand(피연산자) fetch 중 발생, page 올린 후, 해당 instruction 다시 fetch 하면 돼.(restart)

                많은 메모리 공간에 변화를 가져오는 instruction 수행 중 발생. -> undo(이전 상태 기록 임시저장공간 필요)

                -> consistency 위해서 atomic 하게 수행되어야 한다.

·       Performance of demand paging

·       Page fault rate p, [0,1] ( p = 0  page fault x, p =1 모든 접근이 page fault 발생)

·       EAT = (1-p)*memory access time + p*{page fault 오버헤드(disk I/O, 필요 시 replace, swap in, restart overhead)} 

  -  p를 줄이는 것이 아주 중요하다.(Locality 때문에 그렇게 자주 발생하지 않음.)

  -  또한, 메모리의 크기가 커질수록 page fault 빈도가 낮아진다.

·       Process Creation

·       Virtual memory 사용시의 장점.

o   메모리 사이즈 보다 큰 프로세스를 실행 할 수 있다.

o   응답 시간, 쓰루풋 등 지표 개선.

o   Process creation에 걸리는 시간 대폭 감소

o   메모리 공유 율 상승

·       Copy-on-Write(COW) : 프로세스 생성시, fork를 쓰면 부모의 주소공간을 그대로 복사해서 자식의 주소공간을 만들었다.

COW 방식에서는 자식이 부모의 page를 함께 사용하도록 한다. (Page table을 공유하도록 한다.)

만약, 한 프로세스가 shared page를 변형한다면, 그때 해당 page를 복사한다.( 프로세스 생성 시간 대폭 감소)

+) 단순한 page sharing과 다르다. Code 부분 등의 read-only 부분만 공유하는 것이 아니라, 주소 공간 전체를 공유(data까지 공유)하다가, COW를 통해 공유되지 않을 페이지만 새로 만드는 것이므로 공유 율이 훨씬 높다.

·       Page replacement

·       궁극적 목표 : page fault 를 최소화 하는 것.

·       Dirty bit(modify bit) : 해당 페이지가 메모리 위에서 update 되었는지에 대한 정보를 갖고 있어야, DISK I/O 횟수를 줄일 수 있음. 다른 조건이 모두 동일하다면, update가 되지 않은 페이지를 선택하는 것이 유리.

     1) 디스크에서 페이지의 위치를 찾는다.

     2) 빈 frame을 찾는다.

2-1) 빈 frame이 없다면, 페이지 교체 알고리즘을 수행하여, victim frame을 선정한다. 

     3) victim frame을 디스크에 기록하고, 관련 테이블 변경한다.(invalid, frame..)

     4) 페이지를 frame에 기록하고, 관련 테이블 변경한다.

     -> 이와 같은 page fault service routine 수행 후, CPU 스케줄링 재개.

·       1] FIFO : 일반적으로, Frame 수가 늘어나면, page fault 가 감소해야 하지만 FIFO 사용시 오히려 증가하는 현상 발생.

            (벨러디의 모순)

·       2] OPTIMAL : 앞으로 가장 오랫동안 사용되지 않을 페이지를 선택. (미래 정보를 알 수 없다. 근사하기 위해 LRU 사용)

·       3] LRU : 가장 오랫동안 사용되지 않은 페이지를 선택.(최근 선택된 페이지 남긴다. - Locality)

o   각 페이지 별로 시간정보 저장 필요, victim 선정 시 page list 탐색 필요. -> 시간, 공간 오버헤드 발생.

·       Counter : CPU가 메모리 접근 시마다 counter 값 증가시켜서, 해당 페이지에 기록. 가장 적은 counter 값 가진                                        

              page 선택 -> 시간, 공간 오버헤드 너무 크다.

·       Stack     : page number의 스택을 이중연결리스트로 구현. 사용되는 페이지 번호는 스택의 top, 가장 오랫동안   

             사용되지 않은 페이지 번호는 스택의 가장 밑에 위치. (victim selection O(1))

   -> 공간 오버헤드 발생, 연결리스트에서 찾는 오버헤드 발생, 연결리스트 구조 변화에 오버헤드 발생.

·       4] LRU 근사 알고리즘.

o   Reference bit : 초기 값 0, 페이지가 참조되면 1로 바꾼다. 이 bit가 0인 페이지 선택.

-> bit가 0인 page간에 순서를 알 수 없음.

·       additional reference bit  : reference bit + 추가 8bit 를 사용. 가장 작은 값을 갖는 페이지 선택.

·       일정 주기마다 비트 값을 오른쪽으로 shift 한다.(reference bit -> 8bit)

·       계속 참조 되었다면 all 1, 계속 안 되었다면 all 0.

·       Frequency, 누가 더 최근에 참조 되었는지도 알 수 있음.

·       Second chance(clock) : reference bit + page 원형 큐 사용. 이 비트가 0인 페이지 선택.

·       순환하면서 1 -> 0, 포인터가 한 바퀴 돌 동안 참조되었다면 교체되지 않는다.

-> 최악의 경우(전부다 1인 경우) FIFO가 된다. BUT, locality 때문에 이런 일은 없을 것이다.

·       Enhanced second chance  : reference bit + page 원형 큐 + dirty bit 사용.

·       참조도 안되었고, 변경도 안된 페이지 우선 선택, 참조도 되고 변경도 된 페이지는 가장 후 순위.

·       5] 참조 횟수 count 알고리즘

o   LFU : count 수가 가장 작은 페이지 선택. But, locality의 변화에 대처 어려움.

o   MFU : count 수가 가장 큰 페이지 선택. 말도 안됨.

·       Allocation of frames

·       프로세스에게 프레임을 어떻게 할당할 것인가?(총 몇 개의 frame을 사용할 수 있도록 할 것인가?)

·       Minimum number of frames

o   한 명령어가 참조하는 모든 페이지는 동시에 메모리에 올라와야 instruction 수행 가능.

o   loop내의 page 는 동시에 올라와 있는 것이 유리(매 loop마다 페이지 폴트 발생 -> disk I/O,,,)

·       Fixed allocation : 프로세스에게 한번 할당한 공간의 크기는 끝까지 바뀌지 않는다.

o   Equal allocation : 모든 프로세스에게 동일한 크기 할당.

o   Proportional allocation : 프로세스의 크기에 비례하여 할당.

·       Priority allocation : 우선순위에 비례하여 할당.

o   높은 우선순위를 갖는 프로세스는 더 많은 메모리를 가지므로 페이지 폴트 수 감소, I/O 감소, 더 빨리 끝난다.

o   I/O가 줄어드니까 waiting state에서 보내는 시간이 줄어들고, 일찍 끝난다.

o   페이지 폴트가 발생 했다면

·       Victim을 해당 프로세스에 할당된 frame 내에서 선택 -> local replacement

·       Victim은 어떤 프로세스에서도 선택 가능(낮은 우선순위 프로세스의 frame 뺏기 가능) -> global replacement

-> 지역 교체에서는, 잘 안 쓰이는 페이지 프레임이 있어도 계속 낭비하게 됨. 전역 교체가 더 좋다.

·       Thrashing

·        페이지 폴트가 너무나도 빈번히 발생하여 예기치 못하게 성능이 급격히 하락하는 현상.

·        페이지 폴트 많이 발생 -> handler 호출 -> disk I/O 자주 발생 -> I/O 대기시간이 대부분의 시간을 차지하게 된다.

 -> CPU가 유의미한 일을 하지 못함. -> long term scheduler는 CPU 이용률을 높이기 위해 새로운 프로세스 올린다.

 -> 페이지 폴트 증가 -> CPU 이용 률 감소….     +) degree of multiprogramming : 메모리에 있는 프로세스의 수

·       Thrashing은 순식간에 발생. Frame 수 1개 차이로 발생할 수 있다.

·        paging은 왜 동작할까?

o   Locality 때문, CPU의 메모리 접근에는 지역성이 존재하기 때문.

·       Thrashing은 왜 생길까?

o   어떤 프로세스가 새로운 지역을 진입할 때, 충분한 frame을 제공해 준다면, 그 지역의 모든 페이지가 올라올 때 까지는 페이지 폴트가 발생하지만, 그 이후 그 지역을 떠나기 전까지는 발생하지 않는다. But, 그 지역의 페이지 수 보다 적은 프레임을 할당하면, 이 지역을 수행하는 동안 계속해서 페이지 폴트를 발생 시킨다. -> 쓰레싱.

o   Total size of locality > total allocated memory size 일 때, thrashing 발생.

o   +) virtual memory 쓰지 않는다면, 실행중인 프로세스의 페이지는 모두 메모리 위에 있으므로, 페이지 폴트, 쓰레싱 x.

  8-1. Locality

·       프로그램의 메모리 참조는 고도의 지역성을 가진다.

o   시간 지역성(temporal locality) : 현재 참조된 메모리가 가까운 미래에도 참조될 가능성이 높다. (ex - loop)

o   공간 지역성(spatial locality) : 현재 참조된 메모리의 주변 메모리가 계속 참조될 가능성이 높다. (ex - array traversal)

  8-2. Working set model

·       Locality를 토대로 한 모델, allocation, replacement등에 사용할 수 있다.

·       Δ = working set window, 시간간격을 의미(Δ 동안 참조된 page를 보겠다)

·       WS(ti) = ti의 working set, [ti, ti-Δ] 동안 접근한 페이지의 집합.

o   Δ가 너무 작으면, locality를 제대로 반영하지 못함.

o   Δ가 너무 크다면, 여러 지역성을 과도하게 수용.

o   Δ가 무한대라면, 이제껏 참조한 전체 페이지의 집합.

-> 잘 정하는 것이 중요하다, 이게 안 되서 못쓴다.

·       WSSi = Pi의 working set size, D = ∑WSSi (전체 프레임 요구량), m = 사용가능한 전체 프레임의 수

o   D > m  -> thrashing 발생. 

o   OS는 각 프로세스의 Working set을 보면서, 각 프로세스의 working set size에 맞는 프레임 들을 할당한다. 프레임이 남는다면 새로운 프로세스를 시작시킨다.(d.o.m 증가) but, D가 m보다 커진다면 OS는 프로세스를 하나 선택해서, suspend 시킨다.

o   WS(ti)가 모두 보장되어야만 run, 아니면 suspend.

·       실제 구현

o   매 reference 마다 각 page의 최근 접근시간이 Δ안에 들어가는지 검사해야 한다. -> 너무 오버헤드 크다, 근사하자.

o   Reference bit + interval timer + additional 2 bits

·       Δ가 10k라면, 매 5k마다 timer interrupt 발생하여 비트를 left shift, reference bit를 0으로 만든다.

·       3 비트 중 1개라도 1이라면 10k내에 참조가 되었다는 것을 의미.(working set 내에 속한다.)

·       오차가 존재한다.(맨 왼쪽 비트는 10001~14999 의미 가능, working set size보다 커진다.)

·       비트 수를 눌리고 interval을 줄이면 (ex - 10개, 1k) 오차 줄일 수 있음.

-> 매 참조시마다 값을 계속 변경시켜야 하므로 오버헤드가 너무 크다.

8.3. page fault frequency scheme

·       실제 페이지 폴트 발생 비율을 보고 프레임 할당을 조정하자.

·       Upper bound보다 높으면, 프레임을 더 할당한다.(free frame이 없으면 프로세스를 선택하고 suspend)

·       Lower bound보다 낮으면, 프레임을 감소시킨다.

-> PFF는 페이지 폴트시에만 페이지 집합을 수정하므로 오버헤드가 훨씬 적다.

·       Memory mapped files

·       Virtual memory의 side benefits 1) process creation 오버헤드 대폭 감소. 2) file I/O 오버헤드 대폭 감소.

·       일반적인 File I/O는 file system을 거치는 과정에서 수많은 system call들을 거쳐야 한다.

·       Memory mapped file에서는 file을 address space에 mapping 시킨다. CPU는 파일이 메모리에 올라와 있다고 여기므로, Logical address를 발생시켜서 접근하려고 한다.(load, store를 쓴다, read, write x, file system을 거치지 않는다.)

·       CPU가 요구하면, 실제로는 메모리에 없으니까 page fault가 발생하고, 실제로 파일을 메모리에 올린다. 최악의 경우 전체 file이 메모리에 올라오게 된다. (# of page fault = entire file size / page size)

·       파일을 메모리에 올릴 때, page 단위로 올리므로 Disk I/O가 줄어든다.(접근 단위가 1 BYTE라도 페이지 폴트 수는 불변)

 -> 장점 : Disk I/O가 줄어든다(한번 페이지 단위로 올라오고 난 이후의 접근은 memory access이다)

             여러 프로세스가 파일을 공유할 수 있다.

 -> 단점 : 파일 값 변경 시, 디스크가 아닌 메모리에 반영한다.(메모리에서 쫒겨날 때 or 의도적으로 동기화 할 때 반영)

·       Other issue

1.   Prepaging : 프로세스의 시작 때 발생하는 과한 page fault를 줄이자!

·       미리 필요한 page 들을 메모리에 올려둔다. 만약 쓰이지 않는 다면 불필요한 I/O, 메모리 사용 발생하므로 잘 정해야 한다.

2.   Page Size

·       Page size가 커지면

o   Page table 크기 감소

o   Page 개수 감소

o   TLB 감소

o   Disk I/O 효율 상승(한번에 많은 데이터를 가져오므로)

  BUT, internal fragmentation 증가.

·       TLB reach : TBL를 통해 접근할 수 있는 메모리의 크기. TLB reach = TLB size(entry 수) * Page size

·       Working set 이 TLB내에 모두 저장될 수 있으면 이상적. 그렇지 않으면 TLB miss, 메모리 접근 필요.

·       Page size를 증가시키면, internal fragmentation 커진다. TLB size 증가는 너무 비싸다.

·       대안 ) 다양한 page size를 사용.

·       Program structure : P.L이 row major 인지 column major인지에 따라 코드에 따른 페이지 폴트 수가 급증할 수 있다.

·       I/O interlock : 곧 I/O의 대상이 될 페이지는 교체 대상으로 보지 않아야 한다.