일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Project 1
- 끝
- PINTOS
- 제발흰박
- 글리치
- 황금 장미
- 바빠지나?
- 자 이제 시작이야
- 일지 시작한 지 얼마나 됐다고
- 셋업
- 핀토스 프로젝트 2
- 핀토스 프로젝트 4
- 핀토스 프로젝트
- multi-oom
- 아직도 실험 중
- alarm clock
- 핀토스 프로젝트 1
- 내일부터
- 파란 장미
- 마일섬
- 가테
- 글루민
- 핀토스 프로젝트 3
- 노가다
- botw
- Today
- Total
거북이의 쉼터
(2022.05.27) Caching & Demand Page 본문
이번 파트에서는 파일의 데이터를 메모리에 Caching하는 것과 demand paging을 배우면서 Physical Memory Management를 하는 방식에 대해 배울 것이다.
메모리는 디스크 정보에 대한 cache로서 활용될 수 있다. 따라서 cache의 동작에 대해 알 필요가 있다. 특정 주소에 대해 읽기를 할 때, 요청하는 address가 cache 내에 있다면 그 값을 반환하고, 아니라면 해당 주소에서 값을 읽어오면 된다. 쓰기 요청을 할 때는 아키텍쳐상으로 잠시 쓰려는 값이 write buffer에 저장되었다가 cache로 주소값과 함께 요청되는데, 이 때 cache 내에 해당 주소가 존재한다면 cache의 값을 update하고, 존재하지 않는다면 read와 마찬가지로 해당 주소에서 값을 cache로 불러와 update해주면 된다. 이 때 문제는 주소에 위치한 실제값과 cache 내의 값이 일치하지 않게 되는 synchronization 문제가 발생한다는 것이다. 만약 이를 메모리 - 스토리지 관계로 생각한다면 메모리 상에서 바뀐 파일 내용이 스토리지에 반영이 되지 않는 근본적인 문제가 발생하는 것이다.
이를 해결하기 위해서는 cache의 데이터를 단순히 원래 저장소에 write하는 루틴이 있기만 하면 된다. 이는 cache의 데이터가 더 up-to-date된 데이터이기 때문이다. write를 하는 방식에는 두 가지 방식이 제안되었는데, 하나는 cache의 정보가 변화되는 순간순간에 원래 저장소에도 해당 변화를 반영하도록 하는 write through이며, 다른 하나는 cache block이 교체될 때까지 원래 저장소에 write 하는 것을 미루다가 교체가 일어나면 변화를 반영하는 write back이다. write through는 언제나 write back에 비해 느리다. cache에서 write through가 그럼에도 사용되는 이유는 read가 write에 비해 dominant하게 일어나기 때문에 write에서 생기는 손해를 cache가 read에서 매꿀 수 있기 때문이다. write back은 실제로는 asynchronous하게도 일어나기 때문에 생각할 거리가 더 많다. 또한 write back이 일어나기 이전에 shutdown 등으로 consistency가 훼손되는 경우가 있기 때문에 이러한 점을 어떻게 고칠 수 있는지는 나중에 파일 시스템을 다룰 때 또 볼 것이다.
현대 컴퓨터 아키텍쳐는 3단계의 cache와 2단계의 TLB를 가진다. 메모리 계층 구조상 코어(core)에서 가장 가까운 것은 1st level cache / 1st level TLB이며, 가까울 수록 hit cost가 적고, 데이터를 빠르게 구할 수 있다는 것을 알 수 있다. 혹시 모르니 수업 때 언급한 cache 종류에 따른 hit cost도 수록은 해놓겠다.
- 1 Lv Cache / 1 Lv TLB : 1ns
- 2 Lv Cache / 2 Lv TLB : 4ns
- 3 Lv Cache : 12ns
- Memory (DRAM) : 100ns
- Local Non-volatile Memory : 100us (microsecond)
- Local Disk : 10ms
- Remote data center disk : 200ms
계층구조에서 아래로 내려갈수록 저장 용량도 증가한다.
이제 본격적으로 어떻게 OS가 제한된 물리 메모리를 활용해 프로세스에게 무한에 가까운, 적어도 스토리지 용량에는 버금가는 메모리가 있다는 착각을 심어줄 수 있을까? 바로 Demand-paged virtual memory를 이용해서이다. 주어진 예시에서 page B에 접근하려고 할 때, 해당 페이지 정보는 디스크에 있고, DRAM에는 존재하지 않기 때문에 Access는 invalid를 나타낸다. 때문에 trap이 일어날 것이며, 커널에서는 해당 페이지 내용을 디스크에서 메모리로 읽어와서 페이지 테이블을 세팅하고 프로세스로 다시 동작을 넘긴다. 이 때, 필요한 페이지를 담을 메모리 공간이 충분하지 않다면 기존에 존재하던 페이지(들)을 디스크로 쫓아내는 eviction 과정이 수반된다.
file-mapped memory의 demand paing 과정을 좀 더 세밀하게 살펴보자.
1. TLB miss (cold) : TLB에는 요청하는 주소에 대한 매핑이 없을 것이기에 당연히 miss가 난다.
2. Page Table Walk : HW(CPU)는 TLB에서 miss가 났기에 페이지 테이블을 순회하며 매핑이 있는지를 본다.
3. Page fault (page invalid in page table)
4. Trap to kernel : 이제부턴 커널에서 단계가 진행된다.
5. 커널은 가상주소를 파일 + 오프셋 (디스크내에서 필요한 페이지의 주소)으로 변환한다.
6. 커널은 페이지 프레임을 할당한다. 필요하다면 eviction이 일어난다.
7. 페이지 내용이 담긴 디스크 block에서 페이지 프레임으로 내용을 읽어오는 과정을 시작한다. 디스크가 DMA를 수행할 동안 CPU는 다른 작업을 수행할 수 있다.
8. 디스크가 DMA를 마친 뒤에 디스크 인터럽트를 보내 알린다. (HW에서 일어나는 단계)
9. 페이지 테이블 내에서 요청한 페이지가 valid하다고 표기한다. (다시 커널에서 진행되는 단계)
10. Resume process at faulting instruction (지금까지 요청한 어플리케이션이 멈춰있었고, 요구한 페이지가 준비됐다는 신호를 주는 것이다)
11. TLB miss가 다시 난다. (TLB에는 매핑 정보가 채워지지 않았기 때문)
12. Page Table Walk 후 valid한 매핑을 TLB로 fetch한다. (이젠 TLB까지 매핑이 올라갔다)
13. Execute Instruction
해당 과정을 잘 기억하길 바란다고 한다. 페이지 테이블은 커널에 의해 채워지지만, TLB는 HW가 페이지 테이블을 참조하면서 채워지는 것이기에 TLB를 채우는 주체는 HW이다. 몇몇 OS에서는 TLB에 직접 접근하는 명령어가 있긴 하지만, 적어도 x86에 한해서는 TLB 엔트리는 HW에게 같은 주소가 다시 요청됨으로서 HW가 채우게 된다. 또 한가지 주요한 것은 프로세스(어플리케이션)는 이 과정이 일어나는 것을 전혀 몰라야 한다는 것이다. (transparent to app)
부가적으로 virtual memory abstraction을 활용할 수 있는 방안을 살펴보자. file IO에 virtual memory abstraction을 활용할 수 있는데, 바로 Memory Mapped IO이다. mmap과 munmap을 활용하는 코드는 익숙할 것이다. mmap은 fd와 연동된 파일을 메모리 상에 위치한 것처럼 입출력 할 수 있도록 해 준다. 해당 방식으로 생성한 가상 메모리는 file-backed memory가 된다. 만약 mmap의 인자 중 하나인 flags에 MAP_ANONYMOUS를 설정하고, fd로 -1을 설정했다면 OS는 해당 영역을 anonymous memory로 인식하게 된다.
mmap의 semantic은 virtual address space를 생성하는 것이다. 그럼 단순히 mmap을 호출하면 반환되는 그 순간에 OS가 물리 메모리도 같이 할당할까? 그렇지 않다. 반환되는 순간에 물리 메모리까지 할당받으려면 MAP_POPULATE 플래그까지 설정해주어야 한다. 플래그를 설정하지 않은 일반적인 호출에 대해서는 가상 주소만 할당받기 때문에, 첫 번째 접근을 할 때 page fault가 나고, 이를 핸들링하는 과정에서 물리 메모리를 할당받게 된다. 만약 비정상적인 영역에 접근하려고 한다면 일반적인 page fault가 일어나서 어플리케이션이 죽게 될 것이다. page fault가 일어날 때, 해당 영역이 mmap에 의해 생성된 정상적인 가상 주소 범위 안에 있는지를 검사하는 것은 OS가 해줘야 하는 일이다.
File IO에는 두 가지 방안이 있을 수 있다. 첫 번째는 일반적인 read/write system call을 사용하는 것으로서, 과정은 user process buffer에서 커널로 데이터가 복사된 뒤, 커널이 IO를 처리하고, 그 결과물이 어플리케이션으로 복사된다. 이와 비교해 Memory Mapped File 방식에서는 파일이 가상 공간의 세그먼트 중 하나로 취급되기 때문에, 프로그램은 load/store와 같은 메모리 연산 명령을 수행해 파일의 내용을 읽거나 쓸 수 있다. 구체적으로 리눅스에서 Memory Mapping Segment가 위치하는 지점은 Stack과 Heap의 중간 지점 어딘가에 있다고 한다. 수업에서는 Memory Mapped Area가 어플리케이션의 Heap Region에 위치해있다고 이해하라고 하였다. 프로그램에서 요청한 Memory Mapped 주소가 아직 메모리에 들어있지 않을때는 page fault가 일어나고, 커널이 빠진 block을 스토리지에서 메모리로 불러와서 프로세스를 다시 실행시킨다. 이러한 특징 때문에 file backed page의 첫 page fault 때에는 file IO가 내부적으로 이루어지며, 이 때문에 page fault time이 anonymous page보다 길어질 것이라 예상할 수 있다.
Memory Mapped IO를 사용함으로 얻을 수 있는 이점을 살펴보자.
- 파일을 메모리 내부의 영역으로 추상화하므로 프로그래밍이 간단해진다.
- 단순 File IO에서처럼 데이터를 app에서 커널로, 커널에서 app으로 복사하는 과정이 필요하지 않다. (Zero-copy IO)
- Pipelining : 모든 페이지가 물리 메모리에 올라가지 않더라도 프로세스가 시작하는 것이 가능하다.
- IPC에도 유용하다. 같은 파일 페이지를 공유하게 할 수 있기 때문이다.
마지막으로 한 프로세스가 실행될 때 존재할 수 있는 각 영역을 anonymous memory와 file-backed memory로 분류하여 살펴보면서 끝내도록 하자. code와 data는 모두 실행 파일에서 load된 세그먼트이므로 file-backed memory이다. shared library도 마찬가지이며, 그 내부에는 일반 프로세스와 마찬가지로 code와 data 영역이 있을 것이다. Memory mapped file은 위에서 살펴봤듯이 원본 파일의 내용을 불러온 것이므로 file-backed memory이다. 질문은 이러한 file-backed memory 영역이 evict될 때 메모리에 있던 내용은 항상 원본 파일로 write back되는가이다. 스토리지에 있는 실행 파일을 실행해 메모리 상에 불러와졌다고 하자. code와 data 영역이 메모리로 load될 것이며, code는 read only이므로 evict될 때 discard될 것이다. 그럼 수정이 가능한 data는 evict될 때 원본 파일로 write back되어야 할까? 말도 안되는 소리이다. 이러한 특징 때문에 data 영역은 evict가 될 때 temporal한 파일에 저장이 되었다가 필요할 때 다시 해당 파일에서 메모리로 불러오는 방식으로 운용된다. Shared library 또한 code file과 temp data file로 나뉘므로 비슷하게 운용되며, memory mapped file의 경우 evict될 시 원본 파일에 문제없이 write back된다. 프로세스 종료시에 임시 파일은 모두 삭제된다.
file-backed memory와 대비되게 anonymous memory는 기반 파일이 없는 영역으로 stack, heap segment가 여기에 속한다. 이들은 evict될 때, swap disk/file이라고 알려진 no-mapping file에 그 내용이 저장되며, 필요할 경우 해당 위치에서 메모리로 내용이 올려진다. 헛갈리지 않아야 할 것은 anon memory가 evict될 때 저장되는 swap file과 data 영역이 evict될 때 저장되는 temp file은 서로 다른 객체라는 것이다.
이제 남은 것은 디자인 문제를 해결하는 것이다.
- fault 이후에 어떻게 프로세스로 복귀할 것인가? (mechanism 관련)
- 어떤 것을 evict할 것인가? (policy 관련)
각 질문을 좀 더 세밀하게 살펴본다.
이제 페이지 폴트 핸들링을 좀 더 심도있게 살펴볼 것이다. 페이지 폴트 핸들러는 OS의 메모리 관리 부분에 있어 심장과도 같은 부분이다. 메모리 관리의 거의 모든 동작은 페이지 테이블의 invalid한 엔트리에 접근하여 페이지 폴트가 발생하면서 시작된다. 페이지 폴트가 발생하면 어플리케이션이 멈추고, 페이지 폴트 핸들러가 동작한다. 페이지 폴트 핸들러는 페이지를 할당하기 위에 Free page list (Linux에서는 Buddy Memory Allocator, 핀토스에서는 Linked List로 관리)에서 페이지를 가져온다. free page를 받은 뒤에는 해당 페이지를 초기화하고 페이지 테이블에 매핑을 설정한 뒤, 어플리케이션으로 주도권을 반환한다. 이 때 중요한 것은 어플리케이션이 재시작하는 텀을 얼마나 최적화할 수 있는가이다. 페이지 폴트 핸들러를 수정하는 것은 전체적인 성능에 영향을 많이 줄 수 있기 때문에 Linux와 여러 OS에서는 해당 핸들러를 섣불리 고치는 것을 피하는 편이다.
또 하나 중요한 것은 페이지를 초기화하는 것이다. 페이지에는 크게 Anonymous page와 File-backed page로 분류할 수 있으며, 이들 각각을 초기화하는 방법도 분리되어 있다. Anon page를 초기화하는 방법은 이전에 배웠던 zero-on-reference이며, file-backed page는 file에서 읽어옴으로서 초기화한다. 위의 demand paging의 단계들 중 5~8단계에 해당하는 것이 초기화 단계라고 할 수 있다.
다음으로 새로운 페이지 프레임을 할당받는 부분을 뜯어보자. 만약 모든 물리 메모리가 사용중이어서 가득 차 있다면, 이전 페이지 중 하나를 골라 evict해야 한다. 어떤 페이지를 evict할지 결정했다면 해당 물리 페이지를 매핑하고 있는 모든 페이지 테이블을 찾아 각 엔트리를 invalid로 수정해주도록 한다. 모든 페이지 테이블 엔트리라고 표기한 이유는 evict하려는 프레임이 shared 되고 있을 상황을 고려한 것이다. 또한 TLB 엔트리 중 해당 프레임을 가리키는 매핑이 있다면 제거해주어야 한다. TLB에 있는 매핑은 해당 프레임이 evict된 이후에는 엉뚱한 내용을 가리키게 될 것이기 때문에 반드시 없애줄 필요가 있으며, 이를 위해 OS에서 마련한 것은 TLB flushing이다. 만약 evict하려는 페이지가 file-backed page이며, 디스크에서와 내용이 달라져 변화된 내용을 디스크에 반영할 필요가 있다면 디스크에 write하도록 한다. 변화가 없었다면 디스크에 해당 내용이 들어있기 때문에 그냥 discard한다.
문제는 어떻게 변화가 있었는지 알 수 있을까? 모든 페이지 테이블 엔트리에는 해당 페이지에 대한 정보가 수록된다. 그 중에는 페이지가 수정되었는지를 나타내는 dirty bit과, 페이지가 최근에 사용되었는지를 나타내는 use bit (access bit)이란 것이 있다. dirty bit은 페이지에 write 명령이 있었을 때 HW에 의해 세팅되며, TLB와 페이지 테이블 엔트리 모두에 존재한다. 정확한 명칭은 TLB에서는 modified bit, 페이지 테이블에서는 dirty bit으로 불린다. 이를 사용하여 evict될 때 discard할지 write back할지를 결정할 수 있다. access bit의 경우, 추후에 eviction policy를 다룰 때 중요하게 볼 것이며, 어떤 페이지를 evict할 때의 주요한 평가 기준이 될 것이다. 해당 비트는 페이지 테이블의 각 엔트리에 위치하며, TLB miss가 날 때마다 HW에 의해 세팅된다.
해당 정보 비트들은 OS 커널에 의해 초기화될 수도 있다. dirty bit의 경우, write back이 일어났으면 dirty bit은 초기화되어야 하는 것이 옳다. 이 외에도 TLB flush가 일어나거나 디스크와 메모리의 정보가 일치하게 된 시점에서는 dirty bit은 clear되어야 한다. 일례로 메모리 내의 변형된 내용을 디스크에 쓰는 system call인 fsync가 있다. fsync가 호출된 시점에서 OS 커널은 해당 cache data를 discard할지 write back할지 dirty bit를 보고 결정하고, fsync가 반환되고 프로세스로 실행이 돌아가기 이전에 OS는 dirty bit을 clear한다. fsync의 사용과 관련해서는 나중에 다시 살펴볼 것이다. 이외에도 OS는 정기적으로 메모리 내의 데이터를 디스크와 synchronize하기 위해 write back을 하면서 dirty bit을 정리한다. 부가적으로 OS가 dirty bit을 초기화했다면 TLB flushing도 일어난다. access bit의 경우에는 어떤 페이지를 최근에 사용했는지 추적하기 위해 초기화할 때도 있다. 물리 페이지를 매핑하고 있는 아무 페이지 테이블 중에서 하나라도 modified라고 표기하고 있으면 해당 페이지는 modified된 것이며, 하나라도 recently used라고 표기되어 있으면 최근에 접근된 적이 있는 페이지인 것이다.
실제로 x86에서 구현된 페이지 테이블 엔트리 내에서 dirty와 accessed bit가 위치하는 것을 확인할 수 있다. 퍼미션은 Read/Write 비트로 관리된다.
이제 중요한 주제로 넘어간다. 어떤 프레임을 evict할 것인지 결정하는 방법을 배울 것이다. eviction policy, 또는 eviction algorithm을 공부하기 위해 처음으로 알아야 할 것은 Locality에 관한 것이다. Locality는 크게 temporal locality와 spatial locality로 구분할 수 있다. Temporal Locality는 최근에 참조된 영역이 다시 참조될 가능성이 높다는 것을 의미하며, Spatial Locality는 최근의 참조된 영역 근처의 영역이 곧 참조될 가능성이 높다는 것을 의미한다.
실제로 80/20 rule이라는 용어가 있다고 한다. 20%의 메모리에 80%의 메모리 접근이 발생한다는 뜻으로, 효율적으로 메모리를 활용하기 위해서는 20%의 "뜨거운" 부분을 메모리에, 80%의 "차가운" 부분을 디스크에 넣어놓는 것이 효율적일 것이다. 가상 공간의 주소별로 접근하는 횟수를 표현한 위의 그래프를 살펴보자. 어플리케이션이 자주 접근하는 부분이 다른 부분들에 비해 눈에 띄게 접근이 빈번한 것은 Temporal Locality를, 그러한 부분이 좁은 영역에 뭉쳐서 분포하는 것은 Spatial Locality의 존재를 나타낸다. 어플리케이션에서 이러한 Locality가 관측되는 이유는 무엇일까? 순차적 프로그램에서 루프가 있을 때, 해당 루프는 접근 횟수가 다른 코드 부분에 비해 빈번할 것이며, 보통 루프를 돌면서 하는 행동은 Array같은 연속된 공간에 순차적으로 접근하는 것이기 때문이다. 때문에 루프와 Array operation을 하는 프로그램에서는 locality가 특징적으로 나타난다.
자주 쓰는 가상 주소와 연결된 프레임을 메모리에 남겨놓고 그렇지 않은 것은 디스크에 돌려놓기 위해서 이제 우리는 cache replacement policy를 배울 것이다. 페이지 폴트가 발생하면 OS는 프레임을 할당해 해당 프레임에 적절한 내용을 채워 넣어 반환한다. 어느 순간에는 사용할 수 있는 프레임이 모두 할당되어 새로운 프레임을 할당할 수 없는 상황이 온다. 이때 OS는 기존의 프레임 중 하나를 선택해 요청된 페이지의 내용으로 교체할 필요가 있으며 이를 page cache replacement라고 한다. 우리는 이제 어떤 프레임을 교체할지를 선택하는 알고리즘인 page replacement algorithm을 배울 것이다. 해당 policy의 목적은 cache miss를 줄이는 것이다. 메모리는 스토리지의 cache라고도 볼 수 있으므로, cache miss가 줄어들었다는 것은 대부분의 필요한 내용을 메모리에서 찾을 수 있다는 것이다. 스케줄러를 떠올리면 특정 평가 기준에 따라 각 policy의 성능을 측정했었는데 여기서도 비슷하게 진행될 것이다. 이를 위해서는 expected case performance를 향상시키고, poor performance가 발생할 확률을 감소시켜야 한다. OS는 여러 어플리케이션을 돌리는 만큼 일반화된 policy를 제공해야 한다. RR이 Best policy가 아닌 generally good policy였다는 것을 상기하자.
Random
그냥 임의로 프레임을 선택해 교체한다.
FIFO
가장 직관적인 policy. 제일 처음 메모리에 들어와서 가장 오랫동안 있었던 엔트리를 교체한다. 해당 policy를 선택할 경우 문제가 되는 access patern이 있다. 바로 Loop Iteration, Sequential Scan Pattern이다.
현존하는 프레임이 4개, 접근하려는 페이지가 5개 있는 극단적인 경우를 생각해보자. ABCDE 순서대로 루프를 돈다면 모든 경우에서 cache miss (fault)가 뜨면서 최악의 성능을 보여주게 된다. (Program strides through memory that is larger than cache)
MIN (Belady's Algorithm)
해당 policy는 그저 이론의 영역이지만, replacement policy가 추구해야할 궁극적인 목표에 대해 생각하게 한다. 우선 미래의 모든 access patern을 알 수 있다고 가정하자. 그러면 eviction이 일어나야 할 때, 그 때를 기점으로 가장 오랫동안 사용되지 않을 프레임(cache 엔트리)를 선택하는 것이 가능하다. 해당 방식은 최적이라는 것이 증명되어있으며, 만약 더 일찍 사용될 엔트리를 교체하게 된다면 더 빠른 cache miss를 초래할 것이다. MIN policy는 실용성이 없다. 미래의 일을 알 수 없기 때문이다. 다만 다른 policy의 성능을 비교하기 위한 용도로서 활용될 수 있다.
LRU (Least Recently Used)
MIN에서 사용하는 미래를 모르기 때문에 이를 근사화하기 위해 과거의 정보에 의존하는 방식을 채택한다. LRU는 용어 그대로 과거에 가장 오랫동안 사용되지 않은 엔트리를 교체한다. 교체되는 시점에 가장 오랫동안 사용되지 않은 엔트리가 이후로도 많이 사용되지 않을 것이라는 추론에 의거한 방식이다. 이는 Temporal Locality를 생각한다면 근거가 있는 방식이다.
지금까지 살펴본 3가지 방식을 하나의 access patern으로 비교해보면 위와 같다. LRU가 FIFO보다 더 많은 hit을 보여주는 것을 볼 수 있으며 LRU와 MIN이 비슷한 성능을 내는 것을 확인할 수 있다. 그럼 이제 FIFO에 쥐약이었던 Sequential Scan을 LRU와 MIN에서도 살펴보자.
LRU에서도 나아진 것이 없는 것 같다. MIN은 미래를 볼 수 있기 때문에 A가 아닌 D를 교체함으로서 hit을 늘릴 수 있다. LRU는 FIFO와 마찬가지로 과거를 보기 때문에 생기는 제약이다.
이와 별개의 문제로 LRU는 구현도 까다롭다. 어떤 방식으로 무수한 페이지 중 가장 오랫동안 접근되지 않은 페이지를 정확히 골라낼 수 있을까? 한 가지 방법은 모든 access마타 PTE time stamp를 찍어놓고, 해당 값을 보며 가장 오랫동안 접근되지 않은 페이지를 골라내는 것이다. 물론 해당 방식은 탐색 시간에 엄청난 시간이 소모될테니 말이 안된다. 그럼 다른 방법을 생각해보자. 전체 페이지를 doubly linked list로 관리하면서 head에서 tail로 갈수록 access한지 오래된 페이지를 둔다. 만약 특정 페이지가 access됐다면 해당 페이지를 head쪽으로 옮긴다. 해당 방식이 LRU를 구현함에 있어서 가장 그럴듯한 방식이긴 하나, 어플리케이션 단에서 일어나는 access도 OS가 모두 관리한다는 것은 불가능하다. 이를 가능하게 하려면 모든 메모리 access가 page fault를 일으켜야 하는데, 이 또한 만만찮은 비용이다. 만약 read, write 명령이 정해져있는 서버 클라이언트 통신 체제 방식이었다면 해당 방식이 쓸만할지 모르겠으나, OS에서 사용하기에는 너무 고비용이다. 정리하면 LRU는 간단한 방식으로는 구현하기에는 너무 현실적인 문제가 많기 때문에, OS 디자이너들은 LRU의 근사를 사용하게 되었다.
Clock
특정 메모리에 접근할 때마다 HW가 PTE의 access bit을 켜는 것을 활용하여 LRU를 근사한 알고리즘이다. 모든 cache 엔트리는 access bit을 가지고 있고 OS는 이를 원형으로 순회할 수 있다고 하자. OS는 페이지를 순회하면서 access bit가 1일 경우, access bit를 0으로 초기화하고, 0인 경우에 해당 엔트리를 victim으로 선택한다. (reclaim)
해당 과정은 페이지 폴트시 실행될 수도 있고 (synchronously), 주기적으로 실행될 수도 있다 (asynchronously). 주기적으로 실행될 경우에는 최근 사용되지 않으면서 내용 변화가 없는 페이지의 pool을 형성하기 위해 사용된다. 만약 reclaim할 페이지의 dirty bit가 켜져있다면 디스크에 변경 내용을 write back해주고, dirty bit가 켜지지 않아 clean한 페이지일 경우 invalid라고 우선 표기한 뒤 pool로 해당 페이지를 옮겨놓는다. 후에 페이지 폴트가 일어나면 요청하는 페이지가 pool에 있는지를 확인하고, pool에 있는 것이 요청한 페이지가 아닐 경우 해당 페이지를 evict하여 사용한다. 참고로 리눅스에서는 asynchronous한 write back은 file backed page에만 일어난다고 한다.
Nth Chance
Used Bit은 오직 0 또는 1만을 나타낼 수 있었다. 이를 확장하여 좀 더 큰 정수(counter)를 각 엔트리(프레임)마다 저장할 수 있도록 만들면 정확성을 개선할 수 있을 것이란 점에서 착안된 방식이 Nth Chance 방식, 또는 Not Recently Used 방식이다. 만약 해당 페이지가 사용됐다면, counter와 used bit을 모두 0으로 초기화한다. 사용되지 않은 페이지들에 대해서는 counter 값을 1 증가시키고, used bit을 0으로 돌린다. 이런 식으로 해서 counter 값이 가장 높은 페이지 중 하나를 선택하면 될 것이다. 말로 설명해서는 감이 잘 안오니 그림을 보자.
파랑으로 표시된 것이 access된 페이지라는 것을 의미하며 unused 페이지에 대해서는 카운터 값이 증가하는 것을 볼 수 있다, 최종적으로 evict 시점에서 가장 높은 카운터 값을 가진 페이지가 evict될 후보가 된다. 한 번 eviction이 일어나기 이전에 2번의 전체 스캔 과정을 거치는 2nd Chance가 기존 Clock보다 성능, 또는 eviction 해야 될 페이지의 정확성이 좋다. 이는 각 프레임마다 우연히, 또는 순차 진행을 하면서 1번은 접근할 수 있지만 2번 이상 접근했다는 것은 미래에도 해당 프레임에 다시 접근할 여지가 있기 때문이다. 2번 이상부터는 그렇게 큰 차이를 보이지 않는다. 때문에 부가적인 스캔을 요구하는 3rd Chance 부터는 그렇게 유명하지 않다. 2nd Chance가 보편적으로 사용되며, 리눅스 또한 해당 policy에 약간 변경을 가해 사용하고 있다. Nth Chance도 Clock처럼 synchronous, asynchronous한 방식 모두 사용 가능하다.
LFU (Least Frequently Used)
LFU를 이해하기 위해서는 "recently"와 "frequently"의 차이를 알아야 한다. recently는 얼마나 "최근에" 사용되었는지를 보는 반면에 "frequently"는 얼마나 "자주" 사용되었는지를 보기 때문이다. 이를 위해 LFU는 각 엔트리에 카운터를 두고, 각 access마다 카운터 값을 증가시킨다. 다만 과거에 너무 많이 접속되었던 페이지가 최근에는 접속되지 않아도 카운터 수 때문에 evict되지 않는 현상을 방지하기 위해 해당 카운터에는 decay가 적용된다. LFU가 LRU보다 더 잘 작동할 수 있는 경우는 전체 working set에 대하여 활발한 접근이 일어나고, 그러한 영역이 DRAM보다 큰 경우이다. 해당 경우에 recency가 잘 작동하지 않는 이유는 모두 활발하게 접근되기 때문에 recency에 따른 hot/cold 개념이 잘 반영되지 않기 때문이다. 이 경우 활발한 접근 중에서도 어느 접근이 더 활발하게 일어나는지를 평가할 수 있는 frequency가 더 높은 hit ratio를 달성할 가능성이 있다.
MFU (Most Frequently Used)
가장 적게 사용된 엔트리는 가장 최근에 들여와서 빈도가 적은 것일 수 있으므로, 역으로 가장 접근 횟수가 많은 엔트리를 쫓아낸다. 가장 많이 접근된 엔트리는 사용이 끝났을 가능성이 있기 때문에 나름 타당한 접근법이다. 그러나 많은 어플리케이션에서 적용되는 방식은 아니기에 보편성은 부족하다.
Frequency를 사용하는 방식들의 단점은 각 엔트리마다 접근 카운터를 유지해야 하기 때문에 현실적으로 구현이 어렵다는 것이다. 이 때문에 흔하게 사용되지 않는다.
Belady's Anomaly
흔히 cache 내의 담을 수 있는 엔트리 수가 증가하면 cache hit ratio가 늘어날 것이라고 생각하지만 실제로는 그렇지 않은 경우가 있다. 이런 비직관적인 현상을 Belady's Anomaly라고 한다. FIFO로 다음의 access patern을 가지는 프로세스를 실행한다고 생각해보자.
Refernce가 늘어나면서 hit 횟수도 증가했어야 할 것 같지만 실제로는 3에서 2로 줄은 것을 확인할 수 있다. 해당 현상은 FIFO뿐만 아니라 stack algorithm을 충족하지 않는 다른 policy에서도 나타나며, 왜 나타나는지 증명되지 않았기에 Anomaly라고 부른다. 여기서 중요한 점은 큰 메모리가 언제나 높은 hit rate를 보장하지 않는다는 사실이다.
주제를 환기해서 각 프로세스에 어느 정도의 물리 메모리를 할당할 것인가를 생각해보자. 두 가지 해결법이 있을 수 있는데, 고정된 크기의 물리 메모리를 할당하는 fixed space와, 각각의 경우마다 다르게 물리 메모리를 할당할 수 있도록 하는 variable space 방식이다.
fixed space의 경우 각 프로세스는 사용할 수 있는 물리 메모리 공간에 한계가 있으며, 그 한계를 넘어서 사용하려고 할 경우 해당 프로세스는 본인이 차지하고 있는 물리 메모리의 프레임 중 하나를 골라 교체한다. 즉, process local replacement가 일어난다고 볼 수 있다. Docker (container)에서는 고정된 사이즈의 메모리가 할당되고 메모리가 부족하면 스스로의 메모리 한계 안에서 교체가 일어나게 된다.
이와 대비되게 variable space의 경우, 프로세스가 차지할 수 있는 물리 메모리에는 한계가 없으며, 사용할 메모리가 많으면 전체 물리 메모리 공간에서 차지하는 페이지 수가 늘어나고, 적으면 줄어든다. OS는 물리 메모리를 따로 분할하지 않고 전체 물리 메모리를 pool로서 활용한다. 이러한 방식을 global replacement라고 한다. variable space에서는 한 프로세스가 메모리를 독식해 다른 프로세스의 실행을 방해할 수 있다. 그러나 이러한 단점에도 불구하고 리눅스는 variable space 방식을 채택하는데, fixed space에서는 메모리 공간의 internal fragmentation이 발생할 수 있기 때문이다. 핀토스는 variable space 방식으로 운용된다.
이제 policy에 의해 선택된 페이지가 어떻게 되는지를 살펴보자. 선택한 페이지가 어떤 종류의 페이지인지에 따라 그 행동이 달라진다. (mechanism for file-backed page & anonymous page are different) file-backed page에 대해서는 직금까지 배운 것이 있으니 anon page에 대해 조금만 더 알아보자. evict되는 anon 페이지에 대해서는 swap file에 그 내용이 저장된다. OS는 하나 또는 복수의 swap file 또는 swap partition을 디스크에 유지한다. 파티션인지 파일인지는 layer of abstraction에 의해 크게 영향을 주지 않는다. swap file에 저장이 되는 구체적인 포맷이 있긴 하지만 다루지는 않을 것이다.
Unmodified Anonymous Page에 대해서는 만약 해당 페이지의 내용을 저장하고 있는 swap disk의 공간이 있다면 그냥 메모리에서 제거하기만 해도 된다. 수정이 되지 않았기 때문에 필요할때는 해당 swap disk에서 불러오기만 하면 되기 때문이다. 만약 해당 페이지가 한 번도 swap disk에 들어가지 않았다면 새로운 swap space를 할당하고 해당 공간에 페이지 내용을 write해준다. 여기에는 한 가지 예외가 있는데, 페이지의 전체 내용이 0으로 가득 차있는 zero page가 unmodified된 페이지일 경우, swap 공간을 할당할 필요가 없다. 추후에 할당할 때 다시 0으로 채워넣어주기만 하면 되기 때문이다. (zero page가 필요한 이유는 효율성 때문이다. 프로세스가 처음 시작할 때 대부분의 페이지의 내용은 0으로 가득차 있을 것이다. 현대 OS에서는 이런 중복된 zero page를 각각 할당하는 것이 아닌 하나의 zero page를 물리 공간에 생성해 매핑을 해당 페이지로 가게끔 연결시켜 놓는다. 해당 페이지는 read only이므로 쓰려고 하면 COW와 유사한 과정이 일어난다.)
Modified Anonymous Page의 경우, 해당 페이지의 내용이 swap disk에 있다면, 해당 swap space에 기록된 내용을 변경된 내용으로 수정해준다. 만약 한 번도 swapped out되지 않아 swap disk에 해당 내용이 없다면 새로운 swap space를 할당해 페이지의 내용을 write한다.
다음으로 Working Set에 대해 알아보자. 수업을 너무 못해서 다른 블로그와 교재에서 설명을 참조해서 정리하였다. Working Set이란 현재부터 일정 구간의 과거까지 프로그램이 참조한 메모리 영역의 집합을 의미한다. Working Set의 크기는 시간 구간 (t-w, t) 사이에 참조한 unique한 페이지의 수로 결정되기 때문에 시간에 따라 변할 수 있으며, Poor Locality를 가진다는 뜻은 Working Set의 크기가 크다는 것을 의미한다. 일정 크기의 시간을 나타내는 w는 윈도 크기 (Window Size)라고 불린다. 워킹셋을 이해하기 위해 아래의 상황을 예로 들어보자.
t1의 시점에서는 워킹셋이 1, 2, 5, 6, 7이며, 워킹셋 크기는 5이다. t2에서는 워킹셋 사이즈가 2이다. 해당 워킹셋을 이용해 메모리 관리를 하는 방법을 생각해보자. 만약 프로세스들의 워킹셋 크기의 합이 페이지 프레임의 수보다 큰 경우 일부 프로세스를 swap out시켜 남은 프로세스의 워킹셋을 우선적으로 충족시킨다. 시간이 지나 워킹셋을 다 할당하고도 페이지 프레임이 남을 경우 swap out된 프로세스에게 워킹셋을 할당하도록 한다.
워킹셋의 문제는 프로세스마다 phase change behavior가 있다는 것이다. 프로세스가 실행됨에 따라 워킹셋이 역동적으로 변하기도 하기 때문에 이 또한 예측 범주에 넣어야 한다. 윈도 크기를 정하는 것도 문제이다. 윈도 크기 내에 워킹셋에 속한 페이지는 메모리에 유지, 그렇지 않는 것은 버리는 방식이기 때문에 너무 작으면 프로세스가 요구하는 locality set을 모두 수용하지 못할 수 있으며, 너무 크게 잡으면 메모리 낭비와 함께 적정한 다중 프로그래밍을 유지하기 힘들다. 그래서 이와 관련된 많은 연구가 있으며, page replacement algorithm으로서는 실전상 많이 활용되지는 않는다. 그러나 워킹셋은 그 개념 자체는 유용하기에, abstracted terminology로 활용되는 편이다.
Proactive한 방법은 제한 사항이 많다. 따라서 Reactive한 방식을 사용하기로 하자. OS가 프로세스의 동작을 보고 정보를 얻어 메모리를 더 할당할지를 결정하는 것이다. 해당 정보는 "페이지 폴트"이며 이 정보를 활용한 알고리즘을 Page Fault Frequency (PFF) 라고 부른다. 해당 알고리즘은 각 프로세스의 폴트 rate를 지켜보면서 폴트 rate가 일정 상한선을 초과한다면 할당된 메모리가 부족해 폴트가 빈번하게 일어난다고 판단하여 메모리를 더 할당해준다. 물론 Belady's Anomaly 때문에 항상 예상대로 되지는 않는다. 이와 반대로 폴트 rate가 일정 하한선 아래라면 메모리를 회수해 폴트 rate를 높이려고 한다. 물론 이 또한 Belady's Anomaly 때문에 항상 작동하지는 않으며, 이것이 해당 approach가 ad-hoc인 이유이다. 그러나 실전에서는 estimated working set보다 잘 동작하는 방식이다. PFF도 locality 변동으로 인한 phase change를 감지하기 어려워하기 때문에 이를 감안해야한다.
마지막으로 스레싱에 대해 알아보고 강의를 끝내자. 스레싱(Thrashing)이란 OS가 페이지 데이터를 디스크와 메모리 사이에서 옮기느라 대부분의 시간을 보내는 현상을 의미한다. 스레싱은 요구되는 물리 메모리의 양보다 너무 작은 크기의 물리 메모리만이 주어졌을 때 발생하는 현상으로 메모리가 overcommited 되었다는 것을 의미한다. 스레싱이 발생하면 대부분의 작업을 페이지 폴트에 소모하기 때문에 실제로 유용한 작업을 하는 시간은 줄어들게 된다. 스레싱이 발생했는지를 판단하는 기준은 CPU utilization을 살펴보면 된다. 스레싱이 발생하기 전에는 프로세스 숫자가 증가함에 따라 CPU utilization이 증가한다. 그러나 스레싱이 발생한 이후에는 디스크와 메모리 사이에서 데이터가 오가는 IO bound 작업이 계속 발생하기 때문에 CPU utilization이 급락한다. 좋은 Page Replacement Algorithm은 스레싱을 방지할 수 있으며, 더 간단한 해결책은 물리 메모리를 좀 더 공급하는 것이다.
'코딩 삽질 > OS 요약 정리' 카테고리의 다른 글
(2022.05.31) File System (2) (0) | 2022.05.31 |
---|---|
(2022.05.30) File System (1) (0) | 2022.05.30 |
(2022.05.27) Address Translation (2) (0) | 2022.05.27 |
(2022.05.27) Address Translation (1) (0) | 2022.05.27 |
(22.04.11 ~ 04.13) Concurrency Bugs (0) | 2022.04.13 |