[OS] 8. Virtual Memory

Demanding Page

Demanding Paging은 필요한 page만 memory에 올리는 메커니즘을 말한다.

 

구체적인 동작 방식은 아래와 같다.

 

https://hyelie.tistory.com/entry/OS-Demand-Paging-Thrashing

1. Physical Memory의 instruction을 바탕으로 접근해야하는 대상이 Page Table에 Valid한 Entry로 존재하는지 확인한다.

2. 만약 Valid한 Entry가 존재하지 않는다면, page fault trap이 발생한다.(MMU에 의해 발생)

3. Page fault trap 발생을 page fault handler가 받고, 해당 reference의 타당성을 검사한다. 예를 들어, 해당 접근이 valid 하지만 physical memory에 로드되어 있지만 않은 경우 disk로부터 데이터를 가져온 후, memory에 로드하지만 잘못된 접근인 경우 abort를 발생시킨다.

4. 만약 page table에 빈 자리가 존재하지 않는다면 일부 entry를 evict 시킨 후 빈 자리에 page를 할당한다.

5. physical memory와 page table에 load가 완료되면 fault가 발생하기 전에 실행되었던 instruction을 재실행한다.

 

 

TLB

Translation Lookaside Buffer의 약자로, 주소 변환을 빠르게 하는데 도움을 주는 하드웨어 cache에 해당한다.

 

CPU가 Virtual Address를 Physical Address로 변환할 때, 주소 변환 결과를 TLB에 저장하게 된다.

이후 Virtual Address를 통해 메모리에 접근할 때, TLB를 우선적으로 확인하고 TLB에 해당하는 entry가 존재하는 경우 해당 값을 이용해 Physical Address를 획득하는 방식으로 작동한다.

 

이 TLB는 Hardware에 의해 관리될 수도 있고, Software에 의해서도 관리될 수 있는데 두 케이스에서의 page fault 처리 과정이 조금 다르다.

 

Hardware에 의해 관리되는 경우 아래와 같이 처리된다.

 

1. TLB miss가 발생한다.

2. Page table에 valid한 entry가 존재하는지 확인한다.

3. Page table에 valid한 entry가 존재하지 않는 경우 page fault가 발생한다.

4. kernel trap이 작동한다.

5. Virtual address를 file + offset으로 변환한다.

6. physical memory에 page frame을 할당한다.

7. page frame에 disk block을 load한다.

8. 해당 page를 valid하게 표시한다.

9. 실패했던 instruction을 다시 수행한다.

10. TLB miss가 발생한다.

11. Page table에 valid한 entry가 존재하는지 확인한다.

12. instruction이 실행된다.

 

 

Software에 의해 관리되는 경우는 아래와 같다.

 

1. TLB miss가 발생한다.

2. kernel trap이 작동한다.

3. Page Table을 확인하고, page가 invalid함을 확인한다.

4. Virtual address를 file + offset으로 변환한다.

5. physical memory에 page frame을 할당한다.

6. disk block을 page frame으로 불러온다.

7. DMA(Direct Memory Access)가 종료되면  Disk Interrupt를 수행한다.

8. 해당 page를 valid하게 표시한다.

9. TLB entry를 load한다.

10. 실패했던 instruction을 재 수행한다.

11. TLB hit가 발생하고 instruction을 재수행한다.

 

거의 유사하게 동작하지만, Software(OS)가 관리하는 경우 TLB miss 발생 후 page table에 page frame을 로드하는 과정에서 곧바로 TLB에 업데이트가 진행되어 결과적으로 한 번의 TLB miss가 발생하지만, Hardware의 경우 2번의 miss가 발생하는 것을 확인할 수 있다.

 

Dirty Page(Modified Page)

Page 할당 과정에서 Physical memory의 여유 공간이 부족한 경우 이미 할당된 page를 evict하고 빈 공간에 할당하게 된다.

 

다만 page를 evict 할때 다른 처리 없이 진행할 수 없는데, 이는 page에서 발생한 변화가 storage에 반영되지 않은 상태이기 때문이다.

 

SSD, HDD와 같은 storage는 Read와 Write가 RAM과 같은 physical memory에 비해 매우 느리기 때문에 Page에 변화가 일어날 때마다 SSD, HDD에 반영하면 프로그램 실행 속도에 매우 큰 영향을 준다.

 

따라서 `Hardware`는 store instruction으로 인한 Page의 변화를 곧바로 Storage 공간에 반영하지 않고 Dirty Bit(Modified Bit)를 이용하여 해당 공간에서 Store 작업 등이 발생했음을 저장한다.

 

Page를 evict할 때는 이 dirty bit를 확인하여 storage에 변경사항을 반영할 지 결정해야한다.

 

dirty bit는 위와 같이 TLB와 Page Table에 저장되어 있으며, 해당 정보를 통해 해당 Page에 변화가 발생했는지 감지할 수 있다.

 

이러한 dirty bit를 page마다 설정하는 것은 추가적인 Cost에 해당한다.

 

이러한 Cost를 줄이기 위해 dirty bit를 따로 두지 않고, 이를 흉내내는 방식으로 동작하는 경우도 있다.

 

Hardware loaded TLB는 아래와 같이 Dirty Bit를 두지 않고, 이를 Emulating한다.

 

1. 모든 clean page(값이나 내용에서 변화가 일어나지 않는 page)들에 대하여 read-only로 설정한다.

2. page에 처음으로 wirte가 발생하면, kernel trap을 진행한다.

3. kernel이 modifed bit를 설정하면, page를 read-write로 설정한다.

 

Dirty bit외에, 해당 Page가 사용되었는지를 확인하기 위한 `use bit`도 존재하며, 이를 Emulating 하기 위한 메커니즘 또한 존재한다. 해당 메커니즘은 다음과 같다.

 

1. 모든 사용되지 않은 페이지를 invalid하게 설정한다.

2. 첫 번째로 read/write를 진행하면, kernel로 trap한다.

3. kernel이 used bit를 설정하면, 해당 페이지를 read 혹은 read-write로 설정한다.

 

Software loaded TLB는 아래와 같이 동작한다.

 

TLB miss 발생 시

1. page가 clean하다면 TLB에 read only 상태로 load한다. 만약 dirty page라면 read-write로 설정한다.

2. 해당 page를 recently used로 설정한다.

 

TLB write 시(hit)

1. kerenl이 page table의 page에 수정되었음을 알리기 위한 설정을 진행한다.

2. TLB element를 read-write로 설정한다.

3. page를 recentlry used로 설정한다.

 

TLB wirte 시(miss)

1. kernel이 page table에 page의 수정 여부를 표기한다.

2. TLB entry를 read-write로 load한다.

3. page를 recently used로 표기한다.

 

 

Memory Mapped File

File I/O를 처리하는 방법에는 `System Call`을 사용하는 방식과 `Memory Mapped File`을 사용하는 방식이 있다.

 

System Call을 사용할 경우 파일 I/O는 파일을 직접 읽고 쓰는 방식으로 동작한다.

파일을 읽을때는 read(), 쓸 때는 write()라는 함수를 활용해야 한다.

 

반면 Memory Mapped File의 경우 직접 파일의 데이터를 가상 메모리 주소 공간에 매핑하기 때문에, 파일에 대한 접근이 일반적인 메모리 접근과 동일하게 동작한다. 즉 파일에 대한 읽기와 쓰기 과정 또한 일반적으로 메모리에 접근하여 이루어지는 읽기, 쓰기와 동일하게 동작한다.

 

동작 과정을 간략하게 정리하면 다음과 같다.

 

System Call

 

- 파일 열기

System Call에서는 파일을 열 때 open() 함수를 사용하며, 이를 통해 File Descriptor를 리턴받는다.

 

- 데이터 읽기

System Call 방식에서는 파일의 내용을 읽기 위해 read() 함수를 사용하여 File Descriptor에서 데이터를 읽고, 읽은 데이터를 프로그램 버퍼나 변수에 저장한다.

 

- 데이터 쓰기

파일에 데이터를 쓰는 경우 write() 함수를 사용하며, File Descriptor로 데이터를 쓰며, 파일의 내용이 변경된다.

 

 

Memory Mapped File

 

- 파일 열기

open() 함수를 사용하여 파일을 열고, mmap() 함수를 사용하여 파일을 가상 메모리 주소 공간에 매핑한다.

 

- 데이터 읽기

파일의 데이터가 메모리에 매핑되어 있으므로, 해당 메모리 공간에 접근하여 파일의 내용을 읽고 쓸 수 있다. 따라서 파일을 연 이후부터는 별도의 I/O 함수 호출이 발생하지 않는다.

 

Memory Mapped File 방식에서는 파일의 내용을 메모리에 올리기 때문에, Demanding Page와 동일하게 사용할 부분만 메모리에 로드하는 메커니즘을 활용한다.

 

Replacement Policy

TLB에서의 cache miss, Page Table에서의 Page fault가 발생했을 때 이미 Physical memory 공간이 가득 차 있다면  할당된 대상을 상대로 evict를 진행해야한다. 이 때 어떤 대상을 evict할 것인지 결정하는 정책을 `Replacement Policy`라고 한다.

 

FIFO

First In First Out의 준말로, 제일 먼저 들어왔던 대상을 상대로 evict 하는 방식이다.

 

하지만 이는 seqeuntial flooding 형태의 입력이 존재하면 매우 비효율적이다.

 

예를 들어, cache에 4개의 데이터를 담을 수 있는 상황에서

A->B->C->D->E->A->B->C->D->E->A ..... 와 같이 5 종류의 데이터가 반복해서 입력된다고 가정하면 계속해서 evict가 발생한다.

 

MIN

가장 오랫동안 사용하지 않을 대상을 교체하는 방식으로, 이론적으로는 가장 좋은 방법이지만 어떤 대상에 가장 오래 접근하지 않을 것인지를 알기 위해서는 이를 예측하는 방법밖에 존재하지 않기때문에 실제 구현은 어렵다.

 

LRU

Least Recently Used의 준말로, 참조한지 가장 오래된 페이지를 evict하는 방식이다.

 

Linked List 형태로 페이지의 참조 시점을 관리하며 가장 오래된 page를 evict하기 때문에 O(1) Time에 victim page를 선정할 수 있다.

 

LFU

Least Fequently Used의 준말로, 가장 참조 횟수가 적은 page를 evict하는 방식이다.

 

heap을 통해 관리하기 때문에 logn time의 시간복잡도를 가진다.

 

Clock Algorithm

해당 알고리즘을 사용하는 이유는 실제 page eviction에 LFU나 LRU을 적용하는데 어려움이 존재하기 때문이다.

 

page table에 있는 entry가 valid한 경우, 가상메모리 주소를 translate하는 작업만 이루어지는데 이는 하드웨어에 의해 진행된다.

반면, page fault가 발생한 경우에는 disk I/O가 필요하기 때문에 커널로 제어권이 넘어가며 OS가 이를 처리한다.

 

만약 LFU나 LRU를 사용하려면 page들의 순서를 유지하면서 linked list형태로 들고 있어야하는데, 페이지에 대한 접근에 OS가 관련하지 않기 때문에 이러한 데이터구조를 실제로 유지하는 것은 어렵다. 

 

따라서 이에 대한 보완으로 clock algorithm을 사용한다.

 

Second Chance Algorithm이라고도 부르며, 다음과 같이 동작한다.

1. Page Fault가 발생하면 위와 같이 시계형태로 배치한 page frame들에 대해 순회를 시작한다.

2. use bit를 체크하고, use bit가 1이라면, 이를 0으로 변경한 후 다음 page frame을 검사한다.

3. 만약 use bit가 0이라면, 해당 페이지를 교체 대상으로 결정한다.

 

만약 use bit가 아니라 정수 값을 N을 통해 동일한 검사를 진행하면, 총 N번의 기회를 줄 수 있다.

따라서 이 경우는 N-th chance Algorithm이 된다.

 

Thrashing

page fault가 매우 빈번히 일어나는 상황을 Thrashing이라고 한다.

 

이는 프로세스가 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생한다.

 

Thrashing 발생 시 CPU의 utilization이 낮아지는데, CPU 사용률이 낮은 상황에서 OS는 CPU가 거의 사용되고 있지 않다는 사실을 바탕으로 Multiprogramming degree를 높여야한다고 판단하게 된다.

따라서 새로운 프로세스가 시스템에 추가되고, 프로세스 당 할당된 page frame 수는 더욱 감소하므로 상황이 악화되게 된다.

 

이를 막기 위해서는 multiprogramming degree, 즉 동시에 실행되는 프로세스의 수를 조절해주어야 하는데

 

이를 위한 방법이 Working-Set Model이다.

 

Working-Set Model

Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올려야 하는 page들의 집합을 working set이라고 정의한다.

 

해당 모델에서는 process의 working set 전체가 메모리에 올라와야하며, 이러한 조건을 충족하지 못하는 경우 모든 frame을 반납하고 디스크로 프로세스가 swap out된다.

 

Page Size

page size는 전통적으로는 4KB이지만, 메모리 주소 체계가 64bit로 확장되면서 페이지 사이즈도 그에 따라 커지고있다.

 

page size를 감소시키면 페이지 수가 증가하면서, 페이지 테이블의 크기가 증가하게된다.

또한 disk I/O 의 효율성이 감소한다는 단점이 있다.

Internal Fragmentation이 감소한다는 것은 장점으로 작용될 수 있으나, 앞서 언급한 단점의 overhead가 커서 page size가 커지는 방향으로 발전하고 있다.