09-VirtualMemoryManagement

1.     Swapping

-       전체 프로세스를 메모리에서 임시로 백업 저장소(swap 장치 – HDD) 로 내보내고 (메모리 부족을 해결하기 위해), 이후 실행을 계속하기 위해 다시 메모리로 가져오는 과정

-       Context switching time이 높아진다. (swap-in, swap-out)

-       많은 시간을 소요해서 최신 OS는 swapping을 피하려고 한다. Physical memory가 매우 작을 때만 활성화 한다.

-       Better => Demand Paging : 프로세스의 일부만 스왑하는 방법

 

2.     Background

-       코드가 실행되기 위해서는 메모리에 있어야하지만, 전체 프로그램이 항상 사용되는것은 아님.

-       Partially-loaded program : 부분적으로 로드된 프로그램을 실행할 수 있는 능력

 

3.     Demand Paging : 프로세스가 필요로 하는 페이지를 미리 메모리에 로드하지 않고 실제로 필요할 때 (demand가 있을때) 메모리에 로드하는 메모리 관리 기법

-       Sequence 한 pages를 볼 수 있다. 

-       필요한 page만 load 해서 사용한다

-       메모리에 전체 프로그램을 load하지 않고, 필요한 page만 memory에 load한다

-       Why?

1)     필요한 I/O가 줄어든다 => 프로그램 응답 속도가 빨라짐

2)     필요한 메모리가 줄어든다 => 더 큰 프로그램을 실행할수있다

-       Pager : 페이지 관리자. Demand paging을 수행한다. / swapper : 전체 프로세스를 swap in swap out 한다. 

 

4.     Demand paging usage : Heap/Stack

-       Heap : 동적 메모리 할당에 사용되며, 메모리 아래->위로 성장

-       Stack : 함수 호출을 통해, 메모리 위->아래로 성장

-       Lage blank space : 가상 주소 공간의 일부이지만, 힙과 스택이 성장할 경우에만 실제 물리적 페이지가 필요하다

-       Sparse Address space : 실행 중에 demand paging을 통해 힙이나 스택이 성장 할때 채워질 수 있는 빈공간

 

5.     Dynamically linked libraries (DLL) : 프로그램 실행 시점에서 라이브러리를 메모리에 로드하고 연결합니다. 정적링크와 달리 컴파일 시간에 모든 라이브러리 코드를 포함하지 않아도 된다. 일부 페이지는 메모리에 있지만 일부는 여전히 디스크에 있다. 

-       필요한 부분만 메모리에서 로드해서 사용.

-       구분하는 방법 : HardWare지원으로 Valid-Invalid Bit 를 사용한다. 

 

6.     Valid-Invalid Bit

-       Memory 에 존재하면 : v

-       Memory 에 없으면 : i

-       0과1로도 나타낼수있다

-       맨처음에는 모두 i로 초기화된다. 

-       Page fault : 주소를 변환하는 도중, page에서 i로 되어있으면 프로세스가 참조하려는 페이지가 현재 메모리에 존재하지 않아 발생하는 예외상황이다.

 

7.     Page fault

-       Invalid page를 참조하려 할때 나타나는 현상 -> 소프트웨어 trap을 발생시킴

-       OS가 해결하는 방법 : 유효비트가 i인 경우(단순히 메모리에 없는것) physical memory에서 빈 프레임을 가져온다. Disk에서 페이지를 물리적 메모리 프레임으로 swap 한다. 유효비트는 v 로 변경한다. 

 

8.     Aspects of demand paging

-       Hardware support가 필요하다 : valid-invalid bit 가 있는 page table

-       Secondary storage : swap 장치 (disk)

-       Swap = RAM과 Disk 사이에서 page나 process를 교환하는 것

 

9.     Performing of Demand Paging

-       Page fault Rate : 0<= p <= 1

P = 0 no page faults 성공하는것!

P = 1 every reference is a fault 실패하는 것!

-       Effective Access Time (EAT) 

EAT = (1-p) x memory access + p x page fault time

Page fault time = page fault overhead + swap page out + swap page in + restart overhead

-       Page-fault rate가 최대한 낮도록 유지를 해야한다. Demand-paging system에서

 

10.  Free-frame 이 없을 경우?

-       모든 메모리가 사용중인경우. -> Multiprogramming

-       Free-frame list 가 꽉찬 경우 -> physical memory가 꽉찼다는 것

 

11.  Page replacement (페이지교체) : Page replacement

-       현재 메모리에는 있지만 적극적으로 사용되지 않는 페이지를 찾아 새로운 페이지를 위해 공간을 만듦. 페이지 fault 수를 최소화 하는 알고리즘 사용

1)     FIFO (선입선출) : 메모리에서 가장 오래된 페이지를 먼저 교체

2)     LRU (최근에 사용하지 않은 페이지) : 가장 오랫동안 사용되지 않은 페이지를 교체

 

12.  Basic Page Replacement

-       디스크에서 원하는 페이지의 위치를 찾는다 -> 빈 프레임이 있는 경우 사용하고, 없는 경우는 page replacement algorithm 을 사용하여 victim frame을 선택한다. -> victim frame에 원하는 페이지를 디스크에서 메모리로 읽어온다. -> process 재시작

 

13.  Modify Bit (=Dirty Bit)

-       상황 : free-frame이 없는경우 두 번의 페이지 전송이 필요함

-       Page-out 의 수를 줄일 수 있을까요? (페이지 아웃 – 변경된 내용은 disk에 다시 한번 update 하는 느낌)

ð  Dirty bit 을 사용해 초기상태를 0으로 설정하고, 페이지의 바이트가 수정(쓰기)될때마다 비트를 1로 설정한다. 

ð  수정된 페이지만 디스크에 기록되고, 수정되지 않은 페이지(읽기만 한 페이지)는 디스크에 기록하지 않고 삭제할 수 있음(기록하지 않는 다는 것 = page-out이 필요 없다는 것)

ð  페이지 전송 overhead를 줄일 수 있다.

 

14.  Benefits of Virtual Memory (using Demand Paging) 가상메모리의 이점

-       Protection (보호) : 각 프로세스는 가상 주소에만 접근할 수 있다, 한 프로세스의 버그로 다른 프로세스에게 영향을 끼치지 않음

-       Transparency (투명성) : 특정 물리적 메모를 요구하지 않고, 연속적인 가상 메모리 공간을 볼 수 있음

-       Resource exhaustion (자원 고갈 방지) : 모든 프로세스의 크기 합계가 물리적 메모리보다 클 수 있음.

ð  Demand paging : 한 프로세스가 20페이지를 필요하는 경우, 10개의 프레임과 나머지 스왑 공간(디스크)에서 실행할 수있음. 수요페이징과 페이지 교체 사용.

 

15.  Page Replacement algorithms 

-       가장 낮은 page-fault 비율을 원함

-       Page-fault 수는 프레임의 수가 증가함에 따라 감소한다.

1)     FIFO page replacement

2)     Optimal page replacement

3)     LRU(Least-Recently-Used) algorithm : clock, stack, reference-bit

 

16.  First-In-First-Out (FIFO) Algorithm

-       Page가 교체되어야 할 때, 가장 오래된 (오래있었던) 페이지를 선택한다.

= 페이지가 메모리에 불러와진 시간을 기준으로 교체

-       하지만, frame수가 늘어남에 따라 page fault 가 줄어들지 않을 수도 있다.

n  Belady의 이상현상 : 가장 오래된 페이지를 교체하는 것이 마냥 좋은 방법은 아니다. 오래된 페이지에 자주 사용되는 변수가 포함 될 수 있기 때문. 

n  할당된 프레임 수가 증가함에 따라 페이지 폴드가 증가할 수있다.

 

17.  Optimal Algorithm

-       Lowest page-fault rate 

-       가장 오랫동안 사용되지 않을 페이지를 교체

= 페이지가 사용될 시간을 기준으로 교체

-       Future knowledge (미래의 메모리) 참조를 예측해야 하므로 실제로 구현하기는 어려움. But, 알고리즘의 성능을 평가하는데 중요

 

18.  Least Recently Used (LRU) Algorithm

-       과거를 통해 미래 예측

-       과거의 정보를 사용하여 가장 오랫동안 사용되지 않은 페이지를 교체

-       일반적으로 좋은 알고리즘이며, 자주 사용된다.

-       Counter 또는 Stack 을 사용함

-       LRU 구현은 속도가 느리기때문에 (각 캐시 항목에 접근해야해서) hardware 지원이 필요하다

1)     Counter 구현 : 각 페이지 항목에 카운터가 있고, 페이지가 참조 될 때마다 타이머를 카운터에 복사한다. -> 페이지를 교체해야할 때, 카운터를 확인하여 가장 작은 타이머 값을 가진 페이지를 교체한다.

n  단점 : 페이지를 교체하기 위해 검색이 필요하고, 각 메모리 참조마다 타이머를 업데이트 해야한다. 

2)     Stack 구현 : 페이지가 참조 될 때 해당 페이지를 스택의 맨 위로 이동시킨다. (이중 연결리스트 사용) 

n  배열을 사용하지 않는 이유? 

교체시 최악의경우 ex. 6개의 포인터를 변경해야한다. 교체를 위한 검색이 필요없다

-       Clock fields 나 stack은 모든 메모리 참조에 업데이트 되어야 한다 

= 많은 시간이 걸리고 느려서 hardware support가 필요하다.

 

19.  LRU Approximation: Reference bit

-       각 페이지에 비트를 하나씩 할당하고 초기값을 0으로 설정한다

-       페이지가 참조 될 때 비트를 1로 설정

-       참조 비트가 0인 페이지를 교체

-       페이지 참조 순서를 알수는 없지만 페이지가 참조된 여부는 알수있다.