Virtual Memory

Basic Concepts Physical Memory의 용량보다 큰 Memory 용량을 주소 지정할 수 있게 함 동적 주소 바인딩 기법을 사용함 Physical Address는 컴파일 시점이 아니라 실행 시 결정됨

Basic Concepts(Cont’d) Virtual address와 Physical address 간의 매핑관계를 정의한 맵(Ψ)을 사용함 맵(Ψ)은 프로그램이 실행되는 동안 변함 Virtual Address Space PhysicalAddress Space Ψ

Paging 메모리를 일정한 공간으로 나누어 관리 프레임 내에 있는 페이지는 물리메모리에 위치 프레임(Frame) 물리 메모리를 고정된 크기로 나누었을 때, 하나의 블럭 페이지(Page) 가상 메모리를 고정된 크기로 나누었을 때, 하나의 블록 프레임 내에 있는 페이지는 물리메모리에 위치 프레임을 할당 받지 못한 페이지는 외부저장장치에 저장 외부저장장치에도 페이지 단위는 같다 한 프로세스가 실행되기 위해서는 메모리에 올라와야한다. 메모리에 일부만 올라오고 나머지는 저장장치에 있다. “메모리에 올라온다”라는 의미는 메모리를 할당 받는다는 얘기이다. 페이지를 할당 받지 못한 것들은 디스크에 남아있다. Main memory인 것처럼 사용하는 공간을 Virtual 공간이라고 한다.

가상 메모리 주요 부분 Frame allocation policy Static paging algorithm : 처음 프로세스에게 프레임을 할당하면 그 프레임 수는 변하지 않는 정책 Dynamic paging algorithm : 프로세스의 상태에 따라 할당된 프레임의 수가 동적으로 변하는 정책 Fetch policy - 하나의 페이지를 메모리에 적재할 때를 결정하는 기법 Demand paging fetch policy Prefetch policy Replacement Policy - 새로운 페이지를 위한 메모리를 확보하기 위해replacement 할 페이지를 결정하는 기법 Random , Belady , LRU , LFU , FIFO , Stack algorithm 등등 Frame : 실제 physical memory임. Frame allocation : physical memory를 할당해주는 것 Fetch : virtual memory에 있던 것이 main memory로 올라가는 것 한 프로세스가 사용할 수 있는 메모리가 가변적인데 한 프로세스가 5개의 프레임을 사용하고 있는데 다른 프로세스가 프레임을 필요로 하면 5개의 프레임 중 한 개 이상 반납해야되는데 이를 결정하는 방법을 : replacement policy라고 한다.

Demand Paging Demand Paging 프로세스 실행을 위해 모든 page를 물리 메모리에 위치시키지 않고, 필요한 page의 요청이 있을 시 메모리에 올리는 기법 프로세스가 page를 참조 할 때 가능한 상황 참조하려는 page가 물리메모리에 위치(valid) 정상적인 참조가 일어남 참조하려는 page가 물리메모리에 없음(invalid) 물리 메모리에 페이지가 존재하지 않음으로 메모리로 가져와야 됨  Page fault 발생 필요한 page만 요청이 있을 때 메모리에 올려준다.

Demand Paging (Cont’d) 장점 실행을 위한 물리 메모리 구성의 시간이 줄어듦 프로세스 전체의 이미지를 메모리에 올리지 않기 때문에 전체 물리 메모리의 양을 절약 할 수 있음 단점 Page fault 가 자주 일어날 시에는 Page 를 교체하는데 너무 많은 시간을 소비하여 프로세스 실행시간이 줄어듦 Page fault 발생시 교체할 page에 대한 알고리즘이 필요 필요에 의해 올라오기 때문에 X = x + y; 이런 식을 수행한다면 X,y page가 따로 있다. X,y가 메모리에 없으면 디스크에서 가져와야함.  demand paging

Page Replacement(page fault 처리 순서) victim Physical memory i v Page table 1 Swap out victim page 3 Swap desired page in frame No. valid-invalid bit 4 Reset page table for new page 2 Change to invalid

Page Replacement 메모리 과다 할당 상태(Over-allocating of memory) 해결방법 모든 유저 프로세스가 사용하는 페이지 수보다 물리 메모리의 프레임 수가 작은 상황 해결방법 Page Replacement : 물리 메모리에 위치한 페이지를 디스크에 저장하고 요구된 페이지가 해당 프레임을 할당 받도록 함 프로세스에 할당된 메모리보다 물리 메모리가 작아서 프로세스가 사용할 수 있는 페이지가 없다. 부족한 부분을 해결하기 위해서 메모리에 있던 페이지를 디스크에 저장하고 요구한 프로세스의 페이지가 메모리를 할당 받을 수 있게 한다.

Random Replacement 교체될 Page를 random하게 선택하는 방법 구현이 간단하나 효율성이 떨어짐 Page Replacement Algorithms Random Replacement 교체될 Page를 random하게 선택하는 방법 Primary memory에 있는 모든 Page들은 교체될 가능성이 모두 동등함 구현이 간단하나 효율성이 떨어짐 최악의 경우 바로 뒤에 호출될 Page도 교체될 수 있음  잘 사용되지 않음

Page Replacement Algorithms Random Replacement  : page reference stream  = 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7이고 3 Frame인 경우  14 page faults 가 발생(가변적임) Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 2 2 2 3 3 3 0 0 0 0 4 4 7 1 0 0 1 1 1 1 1 1 1 3 3 6 6 5 5 2 3 3 3 0 0 0 2 2 2 1 1 1 1 1 한 프로세스당 3개의 프레임을 할당함. 한 프로세스가 페이지를 요구했을 때 여분의 페이지가 없어서 할당 할 수 없을 때 Random으로 디스크에 옮겨주고 할당을 할 수 있게 한다. (random replacement)

Belady’s Optimal Algorithm Page Replacement Algorithms Belady’s Optimal Algorithm 가장 오랫동안 참조되지 않을 Page를 교체하는 방법 미래에 대한 지식을 필요로 함  현실적으로 불가능하므로 실제로 구현된 시스템은 존재하지 않음 교체 알고리즘으로 제안된 다른 알고리즘을 평가하기 위한 하나의 척도로서 사용됨 교체할 대상을 택할 때 앞으로 사용되지 않을 페이지를 고르게 된다. 앞으로 어떤 페이지를 선택할지 모르기 때문에 현실적으로 불가능.

Belady’s Optimal Algorithm Page Replacement Algorithms Belady’s Optimal Algorithm  = 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 이고 3 Frame 인 경우  10 page faults 가 발생함 비어있는 frame이 없으므로 앞으로 사용되지 않을 3(뒤에 바로 이어서 2,0이 있음) 빼고 그 프레임을 사용한다. Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 2 2 2 2 2 2 2 2 2 0 0 0 0 4 4 4 1 0 0 0 0 0 3 3 3 3 3 3 6 6 6 7 2 3 1 1 1 1 1 1 1 1 1 1 1 5 5 처음이므로 페이지fault 발생

Least Recently Used(LRU) Page Replacement Algorithms Least Recently Used(LRU) 가장 오랫동안 사용되지 않은 Page를 교체하는 방법 현시점에서 가까운 시점에 사용했던 Page 군은 가까운 장래에 다시 참조될 것이라는 가정에 근거를 둠 – 지역성(Locality) 특정 조건하에서는 효율이 떨어지나 비교적 좋은 효율성을 보임  오늘날 가장 널리 사용되고 있음 구현 방법 Counter 사용 : 참조된 시간을 기록 Stack 사용 : 한번 사용된 페이지는 Stack의 가장상위에 위치 가장 위의 페이지 : 가장 최근에 사용된 페이지 가장 아래의 페이지 : 가장 오래전에 사용된 페이지 오랫동안 사용되지 않은 page를 교체한다. 현시점에서 최근에 사용되었던 page는 다시 금방 사용된다. 특정적일 때는 비효율적일 수 있다(goto문이 사용되었을 때, 비지역성일 때)

Least Recently Used(LRU) Page Replacement Algorithms Least Recently Used(LRU)  = 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 이고 3 page frame인 경우  16 page faults 가 발생함 Frame 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 1 1 1 3 3 3 0 0 0 6 6 6 7 1 0 0 0 2 2 2 1 1 1 3 3 3 4 4 4 2 3 3 3 0 0 0 2 2 2 1 1 1 5 5

Least Recently Used(LRU) Page Replacement Algorithms Least Recently Used(LRU)  = 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 이고 4 page frame인 경우  8 page faults 가 발생함 2 0 3 1 2 0 3 1 2 0 3 1 6 4 5 7 0 2 2 2 2 2 2 2 3 2 2 2 2 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 3 3 3 3 3 3 3 3 3 3 3 3 5 5 1 1 1 1 1 1 1 1 1 1 1 1 7 2 3 1 Frame

LRU의 구현 LRU의 구현 Counter 사용 : 참조된 시간을 기록 Stack 사용 : 한번 사용된 페이지는 Stack의 가장상위에 위치 가장 위의 페이지 : 가장 최근에 사용된 페이지 가장 아래의 페이지 : 가장 오래 전에 사용된 페이지 참조비트(reference bit) 주기적으로 0으로 설정 참조된 page의 bit를 1 page fault시 0인 page 가 대상 dirty bit 0 이면 복사가 필요하지 않음 17

Clock Policy 교체 후보 프레임들로 구성된 환영 버퍼의 첫 프레임 18

Clock page replace algorithm 환영 버퍼의 첫 프레임 최근에 교체된 페이지 다음부터 조사하기 시작한다. (0,0)을 찾아!! (0,0)이 없으면 다시 돌아와서 (0,1)을 조사한다. (reference,modify) 모르겠다!!!!!! 찾아봐야지!!! 역시 이창훈!!! 최근에 교체된 페이지 이번에 교체될 페이지 1. (0, 0)을 scan 2. (0, 1)을 scan u를 0으로 3. 실패 시 다시 시작 19

FIFO (First In First Out) Page Replacement Algorithms FIFO (First In First Out) 가장 먼저 들어온 Page를 교체하는 방법 자주 참조되는 Page가 먼저 적재된 경우 빈번한 Page fault가 발생하여 효율성이 떨어짐 Page frame의 수가 증가함에도 불구하고 Page fault가 더 발생할 수 있음  Belady’s anomaly

Page Replacement Algorithms Belady’s Anomaly  = 0 1 2 3 0 1 4 0 1 2 3 4 인 경우 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 3 3 3 4 4 4 4 4 4 1 1 1 1 0 0 0 0 0 2 2 2 2 2 2 1 1 1 1 1 3 3 2  9 faults Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 0 4 4 4 4 3 3 1 1 1 1 1 1 1 0 0 0 0 4 2 2 2 2 2 2 1 1 1 1 3 3 3 3 3 3 2 2 2 2 3  10 faults

Stack Algorithms Page가 참조될 때마다, Page 번호가 stack에 입력됨 Page Replacement Algorithms Stack Algorithms Page가 참조될 때마다, Page 번호가 stack에 입력됨 스택의 맨 위는 가장 최근에 사용된 Page, 맨 아래는 가장 오랫동안 사용되지 않은 Page를 의미함 Inclusion Property : m개의 Page Frame을 가진 실행에서 존재했던 Page들이 m+1개의 Page Frame에서의 실행에서도 존재함  Inclusion Property를 만족하는 것은 Stack Algorithm과 동일한 동작을 가짐(예:LRU)  Belady’s anormaly를 해결함

Page Replacement Algorithms Stack Algorithms  = 0 1 2 3 0 1 4 0 1 2 3 4 인 경우 Stack 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 0 1 4 0 1 2 3 0 1 2 3 0 1 4 0 1 2 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 3 3 3 4 4 4 2 2 2 1 1 1 1 0 0 0 0 0 0 3 3 2 2 2 1 1 1 1 1 1 4 2  10 faults

Page Replacement Algorithms Stack Algorithms Stack 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 0 1 4 0 1 2 3 0 1 2 3 0 1 4 0 1 2 0 1 2 3 3 3 4 0 1 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 4 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 4 4 4 4 3 3 3 3 3 3 3 3 2 2 2 1 3 2  8 faults  Inclusion Property를 만족

Inclusion Property Inclusion Property  = 0 1 2 3 0 1 4 0 1 2 3 4 인 경우 [ FIFO기법 ] Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 3 3 3 4 4 4 4 4 4 1 1 1 0 0 0 0 0 2 2 2 2 2 2 1 1 1 1 1 3 3 1 2 Frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 0 4 4 4 4 3 3 1 1 1 1 1 1 0 0 0 0 4 2 2 2 2 2 2 1 1 1 1 3 3 3 3 3 3 2 2 2 2 3 1 Inclusion Property를 불만족  Stack Algorithms이 아님

Dynamic Paging Algorithms Page Replacement Algorithms Dynamic Paging Algorithms 프로세스가 수행되는 동안 갖는 Page Frame의 수가 변함 프로세스는 어느 실행단계 동안 상대적으로 특정 Page들만을 집중적으로 참조하는 Locality를 가짐 Locality가 변함에 따라 할당되는 Page Frame의 수가 변함  Working Set Algorithm

Page Replacement Algorithms Working Set Working set이란 일정한 시간 간격 동안 하나의 프로세스가 참조하는 Page들의 집합  = … 0 1 2 1 0 1 2 …  = 3 Working Set = {0,1} Working set의 크기가 너무 작으면 Page fault가 빈번하고(Thrashing 발생), 너무 크면 필요 이상의 Page Frame을 가지게 됨 Thrashing : 너무 빈번한 Page 교환이 일어나는 현상으로, 프로세스가 프로그램 수행에 보내는 시간보다 Page 교환에 보내는 시간이 더 많음

Page Replacement Algorithms Working Set  = 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7, Working Set with  = 3인 경우 Allocation 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 Frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0 0 3 3 3 2 2 2 1 1 1 4 4 4 7 1 1 1 0 0 0 3 3 3 2 2 2 5 5 5 2 2 2 1 1 1 0 0 0 3 3 3 6 6 2 1  16 Page faults 발생

2-단계 페이징 시스템에서의 주소변환 + + 프로그램 페이징 기법 주 기억 장치 가상 주소 Root page table ptr 페이지크기 페이지의 offeset 가상 주소 10 bits 10 bits 12 bits Frame # Offset 페이지 번호 Root page table ptr 페이지 테이블의 개수는 2^20 크기는 2^20*4byte 페이지 프레임 + Contiguous에서의 문제점을 막기 위해서 2단계페이징을 함. 메모리 활용이 좋음 하지만 메모리 access 증가의 문제가 발생한다. 메모리 공간의 문제, 페이지의 시작 주소를 알기 위해서는 루트페이지 테이블, 4-k 바이트 페이지 테이블을 읽어야한다. 메모리 access를 3번해야함. 멀티 레벨일 수 록 메모리 access가 증가한다. + 페이지의 시작주소 (32bit) 루트 페이지 테이블 4-k바이트 페이지 테이블 (1024개의 PTE 포함) (1024개의 PTE 포함) 프로그램 페이징 기법 주 기억 장치 29

2단계 페이징 시스템 각각의 테이블 페이지 테이블

TLB의 사용  TLB ( Translation Lookaside Buffer ) 보조 기억 장치 주 기억 장치 TLB 31 Offset page # Frame # 페이지 적재 보조 기억 장치 주 기억 장치 offset TLB TLB 적중 페이지 테이블 TLB 부재 페이지 폴트 실 주소 Page 번호와 offset으로 구분함. TLB : 메모리 레지스터와 같다. Cache 레지스터는 content를 이용하여 찾아간다. 메모리 access time을 줄이기 위해서 사용!!!!!!!!!!!!!!!!!!!!!!!!!!! (CPU 레지스터는 레지스터 번호로 찾아가는 것과 같음.) 페이지 번호와 프레임 번호를 가지고 찾아간다. TLB에는 자주 사용되는 페이지의 번호가 들어있다. TLB를 이용하면 page table을 access할 필요가 없기 때문에 memory access time이 감소한다. 페이지 10000을 찾일 때는 TLB에 가서 10000번 페이지가 있는지 확인한다. 페이지 번호가 있다면 실주소와 연결되어 있어 이를 따라가게 된다. TLB에 페이지 번호가 없다면 페이지 테이블로 가서 찾아 실제주소를 가리키는 곳을 따라 이동하여 찾아간다. 페이지 폴트는 페이지 테이블에도 페이지 번호가 없다는 것! Disk에서 메모리에 올라오지 않은것이기때문에 보조기억장치(disk)에서 읽어와야한다. 페이지 폴트중 worst case는 1. 비어있는 페이지가 없을 경우이다. 이럴 경우 희생자를 찾아서 디스크로 옮기고 그 페이지에 디스크에서 읽어와 올린다. 2. Dirty bit를 검사하여 내용이 변경되었다면 디스크에 써야하지만 dirty bit의 변화가 없을 경우는 굳이 디스크에 저장할 필요가 없다. 왜냐하면 변경된 내용이 없기 때문이다. 3. 마지막 경우는 비어있는 페이지가 있어 그곳에 디스크에서 읽어와 올리는 것! TLB를 사용했을 때 context switching이 일어났을 때 변경되어야 할 것은 페이지 테이블, TLB 를 변경해야한다. Cpu의 정보만 바꾸는 것이 아니라 메모리 부분의 내용도 변경해야한다. 31

역 페이지 테이블 구조 (Inverted page table) 가상 주소 Page # Offset 제어비트 Process n bits page# ID Chain(frame) m bits 해시 함수 i Inverted page table Page 번호와 offset이 있다. Page 번호를 우선 해시 함수에 넣는다. 해시 함수를 왜 써? Search 하는 방법 중 해시 함수를 사용하는 방법을 direct search라고 함. 바로 찾아가는 방법….. 역 페이지 테이블을 프레임 번호 순으로 sort되어 있다. 역 페이지 테이블의 장점을 프로세스의 수와 상관없이 이것 한 개만 있으면 된다. 부과적인 메모리가 필요 없기 때문에 메모리 공간 효율성이 좋다. 가상 주소인 페이지 번호를 물리 주소로 변경해줘야하는데 이때 방법은 예를 들어 해시 함수에 100이라는 값을 넣으면 H(100) = 78 이렇게 나온다고 하면 78의 의미는 페이지가 100번인 모든 프로세스는 하나의 chain을 이루고 있고 그 chain의 시작이 78번이다. 연결된 chain에는 페이지 번호(해시함수 거치기전의 번호)와 프로세스 번호등이 들어있다. 프로세스의 번호를 확인하여 찾고자 하는 번호와 같은 chain (frame)의 frame 번호를 가지고 실주소를 찾아간다. Chain 끝까지 검색하였는데 찾고자 하는 프로세스가 없다면 page fault이다. j 2m – 1 역 페이지 테이블 Frame # Offset (물리 메모리 프레임 당 한 항목) m bits 실 주소 32

Page Replacement Algorithms Working Set  = 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7, Working Set with  = 4인 경우 Allocation 1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 Frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 5 5 5 2 2 2 2 2 2 2 2 2 2 2 2 6 6 3 3 3 3 3 3 3 3 3 3 3 3 7 2 1 3  8 Page faults 발생

Address Translation based on 80x86 Example Address Translation based on 80x86 Segmentation with Paging 방식 Segment의 최대크기는 4GB이고, Page의 크기는 4KB임 주소 변환 과정 Logical Address Linear Address Physical Address Segmentation Unit Paging Unit Segment와 Offset 으로 이루어짐 Segmentation을 가지고 메모리 access를 하다가 멀티 태스킹!!!!!을 하기에는 불편함을 느끼고(contiguous하기 때문에) Exteral ~~오류 발생 4G를 contiguous하기 놓기에는 힘들어….그래서 paging unit을 사용해서 4KB로 페이지를 놔둬! 4GB(232)까지의 주소를 지정할 수 있음 Primary memory의 주소

Address Translation based on 80x86 Example Address Translation based on 80x86 Logical address Segment register offset Descriptor table Segment descriptor + Page frame Linear address directory page offset Physical address Page directory Page table Directory entry page table entry 페이지프레임의시작주소 CR3 (Control register) 페이지 테이블의 시작주소

Descriptor Table Base Register Example Logical Address의 변환과정 Segment의 특징을 기술한 테이블로 프로세스의 각 Segment에 대한 정보를 가짐 + Linear Address Descriptor Table 프로세스가 가지고 있음 Context switching 시 변경해야함 + Descriptor Table Base Register : Descriptor Table 의 시작주소를 가짐 Segment Register Offset 컴파일러 Logical Address 프로그램 소스

Windows Virtual Memory Example Windows Virtual Memory Page Directory/Table은 Primary Memory에 존재하며 프로세스마다 할당됨 2단계 페이징 기법 사용 + Directory Table Offset : Linear Address Page Directory (1024개의 Table Entry를 가짐) Page Table (1024개의 Page Entry를 가짐) Primary Memory Page 31 22 21 12 11 Page Directory의 물리적주소 Page Table의 물리적주소 Page의 물리적주소 CR3 (Control Register)

Linux Virtual Memory + Directory Table Offset Example Linux Virtual Memory 3단계 페이징 기법 사용 - 페이지 디렉토리(Page Directory) - 페이지 중간 디렉토리(Page Middle Directory) : i386 마이크로프로세서에서는 하나의 Entry만 가지며 실제 구현되진 않음 - 페이지 테이블(Page Table) + Directory Table Offset : Linear Address Page Directory (1024개의 Table Entry를 가짐) Page Table (1024개의 Page Entry를 가짐) Primary Memory Page 31 22 21 12 11 Page Directory의 물리적주소 Page Table의 물리적주소 Page의 물리적주소 CR3 (Control Register)