[Chapter 10]
I. 가상 메모리
A. 가상 메모리 종류
1. Logical Memory를 통해서 메모리 영역 전체를 사용가능하다고 가정하고 사용하는 방식. 2. 디스크의 일정 부분을 메모리처럼 사용할 수 있는 방법. 일정 부분이란 것은
물리적으로 메모리처럼 사용할 수 있는 공간이 지정되어있다는 뜻은 아니다.
Physical memory와 secondary storage사이의 swap을 통해서 구현한다.
free frame이 없으면 디스크를 메모리처럼 사용해서 특정 프로세스를 디스크로 내리고 새로운 프로세스를 physical memory에 할당한다.
B. Demand Paging
1. 개념: logical memory에서는 프로그램이 실행되려면 메모리로 프로그램이 전부다 올라온다고 가정하지만, 실제로 virtual memory를 적용하면 처음 수행할때는 아무것도 피지컬 메모리에 올리지 않고 수행한다. CPU가 TLB혹은 메모리에 존재하는 페이지 테이블을 통해 특정 메모리 영역을 접근했는데 플래그가 invalid 상태이면 그때 피지컬 메모리에 올린다. 처음 프로세스가 실행되면 페이지 테이블이 생성되고 전부 invalid 인 상태로 시작한다. 특정 페이지 참조했는데 invalid이면 exception으로 인해서 인터럽트를 발생시키고 운 영체제를 호출하고 인터럽트 핸들러가 protection문제로 인한 invalid상태인지(not in memory) secondary storage에 존재하는것인지(page fault) 판단하고 page fault라면 디스크에서 페이지를 가져와서 메모리에 올 린다. Protection 이슈라면 운영체제가 kill한다.
context switching이후 최초 한번은 반드시 page fault가 발생한다.
요청이 있을때 필요한 부분만 피지컬 메모리에 올리기 때문에 Demand Paging이라고 부른다. 만약 피지컬 메모리에 free frame이 없으면 피지컬 메모리에 있는 특정 페이지를 디스크로 내려야한다. 디스크의 어느 공간에 프로그램이 존재하는지는 PCB에 base주소가 기록되어있다. Invalid일 경우 PCB를 참 조해서 디스크에서 가져와서 로드한다. 따라서 특정 디스크 영역이 정해진 것이 아니라 디스크 영역 전체가 가상메모리처럼 사용되는것이다. 하지만 용량의 한계는 정해져있어야 한다.
2. Locality: Swap in, out이 굉장히 빈번하게 발생하면 디스크 IO가 많이 일어나므로 성능이 크게 하락하겠지만 Locality 특성으로 인해 좋은 성능으로 동작한다. temporal locality = 시간적인 측면의 locality. 최근에 사용된 데이터가 앞으로 사용될 가능성이 높다. Spatial locality - 공간상의 locality. 근접한 데이터가 사용될 확률이 높다. 디스크에 있는 페이지를 피지컬 메모리에 캐싱한다는 개념으로도 생각할 수 있다.
C. Memory Reference
1. 과정: CPU에서 메모리 엑세스하려고 하면 TLB를 참조하고 Cache hit이 난다면 바로 메모리를 엑세스하고 Miss가 나면 페이지 테이블을 참조하여 Valid비트라면 메모리를 엑세스하고 invalid비트이면 운영체제가 개 입해서 Protection문제인지 Page fault인지 판단하고 Page fault라면 PCB참조해서 디스크에 접근해서 실제 메모리에 로드하고 페이지 테이블과 TLB를 업데이트한다.
D. Copy-on-Write
1. Fork()로 인해서 프로세스가 2개가 됐다. 포크 된 순간은 모든 섹션이 똑같고, Demand Paging에 의해서 메모 리를 새로 할당해줄 필요 없이 똑같은 영역을 공유해서 사용한다.
2. 한 프로세스가 데이터값을 업데이트하는 경우 같이 사용하면 데이터가 일치하지 않는다. 그 프로세스만의 고유한 영역이 필요하면 그 부분만 복사해서 새로 페이지를 할당해준다.
II. Page Replacement
A. 필요성
1. Free Frame이 없는 경우: Physical memory가 가득 차 있는 상황에서 새로운 페이지를 메모리에 올리는 경 우 메모리 공간이 없으므로 Victim을 선정하고 디스크로 swap out하고 새로운 페이지를 swap in 해야한 다. 이 과정을 page replacement라고 한다. 어떤 페이지를 Victim으로 선정하냐가 중요하다. 자주 사용되 는 페이지를 swap out한다면 IO가 계속 발생해서 성능이 떨어진다.
B. Page Replacement Algorithm 개요
1. page fault가 많이 일어나지 않는 최적의 victim을 선정하기 위한 알고리즘. Belady’s Proof: 가장 오랜시간 사용되지 않은 페이지를 victim으로 선정하는것이 page fault를 최소화한다.
2. 프로세스 전체를 올려놓으면 page fault가 일어나지 않고 할당받은 프레임이 많을수록 replacement가 줄 어든다. 하지만 프레임 수가 5,6개 이상이면 page-fault rate가 거의 비슷해진다. 따라서 5,6개 이상의 프 레임을 할당하는것은 큰 의미가 없다.
C. Page Replacement Algorithms
1. FIFO: 가장 먼저 들어온 페이지를 가장 빨리 swap out한다. 공평하긴 하지만 성능이 잘 나오지 않는다. 프 로세스에 할당하는 프레임수를 늘려도 page fault가 줄어들지 않는 문제가 있다. locality를 고려하지 않기 때문이다.
2. Optimal Algorithm: 가장 오래 사용되지 않은 페이지를 replace한다. 시간을 고려해서 엑세스 시점을 저장 하고 시간을 계산해야하므로 오버헤드가 크다는 문제점이 있다.
3. LRU(Least Recently Used): Optimal 알고리즘 최적화를 위해서 시간을 1bit로 초기화한다. 이 비트를 Reference bit라고 하며 참조된 경우 1 아닌경우 0으로 하나의 비트만으로 시간을 approximation해서 관 리한다. Stack으로 관리하는 방법도 존재하지만 Stack을 유지해야하는 오버헤드가 있어서 사용하지 않는 다. 타이머 인터럽트가 발생하면 전부 0으로 초기화된다. 메모리 참조가 발생하면 1로 설정하고 아직 reference bit가 0인 것에서 하나를 빼서 replace한다. 이 방식의 문제점은 1bit로 시간을 관리하니 타이머 인터럽트 발생 적전에 1이 된 페이지도 있을 수 있고 0인 페이지가 여러개 있는 경우 한번도 replace되 지 않는 경우도 발생한다는 점에서 optimal하지 않다
4. LRU Clock: reference bit가 1인 페이지가 얼마나 오래됐는지 판단할 수 없는 문제가 있었으므로 1로 되어 있으면 다음에 replace하는것으로 next victim 포인터 위치를 한칸씩 내리며 0으로 초기화한다. 0인 페이 지를 만나면 replacement대상이 된다. 시간정보를 더 고려할 수 있는 장점이 있지만 계속해서 reference bit탐색을 해야하고 오버헤드가 크다.
5. NRU: 리눅스에서 실제로 사용되고 있는 방식. Reference bit와 함께 modify bit를 사용해서 4가지 상태를 가지는 상태처리도를 기반으로 동작한다. 인터럽트가 발생하면 전부 0으로 초기화하고 Read가 발생하면 R(Reference bit)를 1로 바꾼다. Write가 발생하면 M(Modify bit)를 1로 바꾼다. Class 0은 접근이 이루어지 지 않은 가장 우선순위가 낮은 페이지이고 Class 1은 Write만 이루어진 페이지이다. Write작업보다 Read 작업이 계속되는 경우가 많으므로 Write보다 우선순위가 높다.Class2는 Read만 이루어진 페이지이고 Class3은 둘다 이루어진 페이지이다. 3이 가장 replace될 가능성이 낮다.
PTE를 보면 Valid비트와 함께 Reference bit와 Modify bit를 함께 관리하고 있는 것을 알 수 있다.
6. LFU(Least Frequently Used): 제일 많이 쓰인 페이지를 두고 제일 적게 레퍼런싱 된 페이지를 내리는 방법. 레퍼런싱 된 횟수를 가지고 victim을 선정한다. 횟수를 관리하는 오버헤드가 크고 오버헤드를 줄이기 위 해서 카운터를 1bit로 만들면 LRU의 approximation과 동일하다.
D. 프레임 할당
1. 프로세스마다 몇개의 프레임을 할당할것인지, 즉 valid로 체크된 페이지를 몇개로 유지할것인지, 프로세스 마다 동일한 개수를 줄 것인지를 고려해야한다. 동일한 개수의 프레임을 할당하는것을 Equal Allocation이 라고 한다.
2. Proportional Allocation: 사이즈가 큰 프로세스에 더 많은 프레임을 할당하는 방식. 하지만 사이즈가 크다 고 해서 반드시 프레임이 많이 필요한것은 아니다. 반대로 사이즈가 작아도 page fault가 적게 일어나야 하는 성능이 중요한 경우도 있다.
3. Priority based Allocation: 우선순위가 높은 프로세스에 더 많은 프레임을 할당한다. 현재 운영체제에서는 Proportion과 Priority를 둘 다 고려한다.
E. Page-Fault Frequency Scheme: 프로세스 시작할때 프레임을 상수로 정해주는 것은 적합하지 않을 수 있다. bottleneck이 걸릴 때의 성능을 고려하지 못한다. 따라서 동적으로 프레임을 할당할 필요가 있다. 처음에는 우선순위와 Proportion을 보고 프레임을 할당하고, Page fault가 한번도 나지 않으면 프레임을 과하게 할당했 다고 판단하고 할당해준 프레임을 하나씩 줄인다. Page fault가 너무 많이 일어나는 경우 프레임이 너무 적 다고 판단하고 프레임을 더 할당한다. upper bound와 lower bound 내에서 동적으로 프레임 수를 조절한다.
F. Global/Local Replacement
1. Global replacement: Physical memory전체에서 replace할 페이지를 찾는 방식
2. Local Replacement: 동작하고 있는 특정 프로세스에서 페이지를 선정해서 내리는 방식. Local Replacement 방식이 사용된다. 프레임이 더 필요해서 다른 프로세스의 페이지를 내리고 가져간다면 fairness가 깨지고 다른 곳에서 성능이 더 떨어질 가능성이 있따.
G. Thrashing
1. Thrashing: 프로세스 수가 증가할수록 CPU Utilization이 계속해서 증가하다가 어느 순간 급격히 감소하는 현상. locality특성을 가지고 있는 페이지들의 총량이 physical memory보다 커지는 순간 page replacement 가 급격히 증가하고 IO작업만 계속하면서 성능이 떨어진다. Locality를 가지는 페이지들의 총량이 피지컬 메모리의 양을 넘어서서 IO만 계속해서 발생하는 상황이다.
H. Working Set Model
1. Locality 총량을 계산하기 위해서 만든 모델. 특정 시간단위(델타) 안에서 페이지 레퍼런스가 몇번 이루어 졌는지 집합으로 만든다. 집합이 크면 Locality가 낮다. Set에 몇개의 페이지 레퍼런스밖에 없으면 Locality 가 좋다. 총량을 계산해서 Physical memory를 넘어서면 Thrashing이 일어난다고 판단한다.
III. 기타 이슈들
A. PrePaging
1. 프로세스를 처음 실행시키면 전부 invalid상태이고 Demand Paging으로 디스크에서 메모리로 올리는 상 황에서 Spatial locality를 고려하면 순차적으로 근처의 코드가 실행될 확률이 높으므로 엑세스되지 않은 페이지도 미리 가지고 오는 방법이다. 최조에 프로그램을 실행할때 많이 사용한다.
B. Page Size Selection
1. 페이지 사이즈가 커지면 페이지 테이블의 엔트리 수가 적어지지만 internal fragmentation의 사이즈가 커 지고 페이지 사이즈가 작아지면 페이지 테이블 엔트리 수가 증가하는 tradeoff관계가 존재한다. 적절한 협의점이 4kbyte이다. 모든 페이지를 4kbyte로 사용하지는 않고 여러개의 페이지 사이즈를 같이 관리한 다.
C. TLB Reach
1. TLB는 캐시이므로 캐싱되어있는 정보들로 hit이 나서 접근할 수 있는 메모리의 양이 존재하는데 그걸 TBL Reach라고 한다. TLB Reach가 크면 좋지만 하드웨어가 커져야 하므로 비용이 증가한다. 엔트리를 캐 싱하는 것이므로 페이지의 크기가 커진다면 TLB리치가 커진다. 즉 miss가 잘 안난다. TLB 자체의 사이즈 를 키우는것은 어려우니 페이지 사이즈를 증가시키고 multiple size page를 적용해서 internal
fragmentation을 최소화한다.
D. 프로그램 구조
1. 프로그램을 어떻게 짜느냐에 따라서 Page fault의 수가 크게 달라질 수 있다. 아래 예제에서 1024개의 int형 배열의 크기는 4kbyte이므로 page의 크기와 일치한다. 따라서 i, j의 순서가 바뀌는 것만으로 연속 해서 데이터에 접근하는것이 아니라 계속해서 page fault가 발생할 수 있다.
E. IO interlock
1. DMA를 사용하면 디스크가 CPU를 거치지 않고 메모리에 로드할 수 있다. 디스크는 계속해서 로드하고 CPU는 DMA로 새로 올라오는 페이지들은 아직 레퍼런싱 된 적 없으니 디스크로 내리는 상황이 발생할 수 있다. 따라서 DMA를 수행할때는 피지컬 메모리의 특정 영역을 버퍼로 지정하고 IO interlock을 걸어 서 victim으로 선정되지 않도록 한다.