[WIL] 크래프톤 정글 11~12주차 - PintOS 키워드 정리

Virtual Memory

(관련 정리 링크 : https://jeokyong-development.tistory.com/29)

 

- 메모리를 실제 메모리보다 많아 보이게 하는 기술로, 어떤 프로세스가 실행될 때 메모리에 해당 프로세스 전체가 올라가지 않아도 실행이 가능하다는 점에 착안하여 고안된 메모리 기법이다.

장점

- 메인 메모리를 하드 디스크의 캐시로 처리하여 더 넓은 메모리 공간을 제공한다. 임시 데이터를 하드 디스크 드라이브에 저장하고, 필요에 따라 기본 메모리로 가져올 수도 있고, 기본 메모리에 있는 것을 하드 디스크 드라이브에 옮길 수도 있다.

 

- 각 프로세스의 주소 공간을 다른 프로세스에 의한 손상으로부터 보호할 수 있다.

 

- page sharing을 통해 두 개 이상의 프로세스가 파일과 메모리를 공유할 수 있다.

 

- 각 프로세스에 통일된 주소 공간을 제공함으로써 메모리 관리를 단순화한다.

Page Table

(Page 정리 링크 : https://jeokyong-development.tistory.com/32)

Paging

- 페이징은 프로세스의 물리 주소 공간이 연속적이지 않게 하는 메모리 관리 계획법으로, 프로세스를 일정 크기로 자르고 이를 메모리에 불연속적으로 할당하여 외부 단편화를 해결할 수 있다.

 

- 가상 메모리를 일정한 크기의 page들로 나누고, 물리 메모리를 일정한 크기의 frame들로 나눈 뒤, 둘을 매핑하는 형식으로 이루어진다.

 

- 가상 주소는 page number와 page offset이라는 두 부분으로 나뉘게 된다.

 

이 때, page number는 page table에 대한 index로 사용되고, page offset은 page table에 나와있는 frame의 시작 주소에 더해 실제 물리 메모리 주소를 만들 수 있다.

물리 메모리의 실제 주소를 찾는 과정은 MMU(Memory Management Unit)가 수행한다.

Translation Lookaside Buffer(TLB)

- TLB는 Page를 이용했을 때 일어나는 메모리 접근 횟수를 줄이기 위해 만든 것으로, 하드웨어적으로 지원하여 page table에 대한 cache 역할을 한다.

 

- TLB는 cache처럼 사용되기 때문에 적은 page table entry들만 저장할 수 있다.

 

· 만약 찾고 있는 page number가 TLB 안에 있다면 바로 해당 page entry가 갖고 있는 frame number가 나오게 되고, 이를 이용해 물리 메모리에 접근할 수 있다.(TLB hit)

 

· 만약 찾고 있는 page number가 TLB 안에 없다면 page table로 접근하여 해당 page number가 가리키는 entry를 찾는다.(TLB miss)

 

- TLB가 꽉 차게 되면 TLB에서 삭제할 entry를 골라야하는데, 고르는 방법으로는 LRU(Least Recently Used), RR(Round Robin), Random 방식 등이 있다.

 

- 몇몇 TLB는 특정 entry가 삭제되는 것을 허용하지 않는다.

Page Fault

- page fault란, 물리적 메모리에 올라와있지 않은 page에 접근하는 것을 말한다.(valid/invalid page의 개념을 알고 있다면 invalid한 page에 접근하는 것이라고 봐도 된다.)

 

- page fault의 과정들은 다음과 같다.

 

① 현재 프로세스가 page table에 접근할 때, 해당 페이지가 valid한지 invalid한지 확인한다.

 

② invalid하다면, MMU가 trap을 발생하여 운영체제에 알리고, 이 프로세스를 멈춘다.

 

③ 찾는 page가 backing store(disk)에 있는 것을 확인한다.

 

④ 메인 메모리(물리 메모리)에서 free frame(빈 공간)을 찾아 해당 frame에 넣는다.

 

⑤ page table에서 해당 page entry를 valid로 초기화한다.(최신화한다)

 

⑥ 멈춘 프로세스의 멈춘 부분부터 시작한다.(실제로는 바로 시작하는 것이 아니라 ready queue에 들어가게 된다.)

Page Replacement Policy

- Demand paging(프로그램 실행에 필요한 페이지들을 물리 메모리에 옮겨 놓는 것)을 할 때, 메모리가 꽉 차있는 경우 메모리에 있는 페이지를 디스크로 옮겨줘야 하는데(이를 page out이라 한다), 그 페이지를 고르는 것이 page replacement policy이다.

 

- 이 때, evict할 page(victim page)를 잘 골라서 최대한 page fault가 일어나지 않도록 해야 메모리 효율이 좋아진다.(그렇다고 알고리즘이 복잡하면 알고리즘 실행이 오래걸리므로 trade off 관계가 있다.)

FIFO Page Replacement

- 가장 간단한 page replacement 알고리즘으로, 가장 오래된(가장 먼저 온) page를 골라 page-out 시켜주는 알고리즘이다.

 

- Belady's anomaly : 할당된 frame들이 많을 수록 page fault rate가 증가한다.

Optimal Page Replacement

- 실제로 구현이 불가능한 알고리즘으로, 가장 먼 미래에 사용될 page를 page out하는 알고리즘이다.(미래의 정보를 알 수가 없음)

 

- 수학적으로 가장 page fault rate가 낮은 알고리즘이다.

 

LRU(Least-Recently-Used) Page Replacement

- optimal 알고리즘를 근사한 알고리즘으로, 가장 오랫동안 사용되지 않은 page를 victim으로 선택하는 알고리즘이다.

 

- 각 page의 마지막으로 사용한 시간을 알아야한다.(이를 counter 혹은 stack으로 구현한다)

 

· Counters : 각 page table entry를 time-of-use라는 값과 연계시킨다. page가 사용될 때마다 해당 값을 1씩 증가시켜주고, 만약 victim page를 요구한다면, time-of-use 값이 가장 작은 page entry를 page out 시킨다.

 

· Stack : 정확하게 stack을 사용하는 방법은 아니지만, stack과 유사한 자료구조를 사용하는 방법이다.

page가 사용되면, 해당 page를 top으로 옮긴다. 만약 victim page를 요구한다면, stack의 bottom에 위치한 page를 page out 시킨다.

Second-Chance Algorithm(Clock Algorithm)

- LRU는 비용이 크기 때문에 비슷한 성능(살짝 안좋음)을 가지지만 비용이 더 작은 second-chance 알고리즘을 사용할 수 있다.

 

- 기본적으로 FIFO 알고리즘으로 비슷한데, page에 reference bit를 추가하여 사용하는 알고리즘이다.

 

- 만약 이번에 확인하는 page의 reference bit이 0이라면 바로 해당 page를 victim page로 고르고 page out 시킨다.

 

- 만약 어떤 page가 victim page로 골라졌는데 reference bit이 1이라면 기회를 한 번 더 주어(second chance) 다음 FIFO page를 고르게 된다. 이 때, 먼저 골라졌던 page의 reference bit은 0이 된다.

 

- 만약 시계 바늘(victim page를 고르는 것)이 오기 전에 어떤 page가 참조되면, 해당 page의 reference bit를 1로 바꾼다.

 

- circular queue로 구현이 가능하다.

 

- 이외에도 Enhanced Second-Chance Algorithm, Counting-Based Page Replacement, Page-Buffer Algorithm 등이 존재한다.

Swap Disk

Swap

- 시스템에 실제 물리 메모리가 부족할 경우, 디스크 공간을 이용하여 부족한 메모리를 대체할 수 있는 공간을 말한다.

 

- 하드웨어에서 대신 사용하게 되는 일종의 가상 메모리 개념으로, 실제 메모리가 아닌 하드 디스크를 이용하는 것이기 때문에 메모리 속도는 떨어진다.

Swapping

- 실제 메모리가 가득 차면 swap 공간이 사용되는데, 물리 메모리의 비활성 페이지가 swap 공간으로 이동하게 되면서 사용하게 된다.

 

- 프로세스가 일시적으로 메모리에서 나와 backing storage(disk)에 들어갔다가 다시 memory에 들어가는 방식이다.

 

- swap의 장점으로는 시스템이 실제 담을 수 있는 수보다 더 많은 프로세스들을 메모리에 담을 수 있다는 것이다.

 

· Idle process는 swap out하기 좋은 후보가 될 수 있다.

 

· 만약 비활성화된 swap out된 프로세스가 다시 활성화되면 swap in 되어야 한다.

 

- page를 메모리에서 backing store로 옮기는 것을 page out, 그 반대를 page in 이라고 한다.

Swap 역의 종류

- swap은 filesystem 형태로 생성할 수 있고, partition volume 형태로도 사용할 수 있다.

(filesystem 형태 : 이미 생성된 공간에 특정 사이즈를 가진 파일 형태로 존재)

 

- 대부분 linux 배포 판에서는 swap 공간을 Filesystem 형태 보다는 partition volume 형태로 생성하여 사용하는 것을 권고하고 있다.

Anonymous page(익명 페이지)

- Anonymous page는 어떤 파일과 데이터 소스와도 연결되지 않은 페이지를 의미한다.

 

- Anonymous page는 커널로부터 직접 메모리 영역을 할당받은 메모리 페이지로, 스택과 힙 영역에서 사용된다.

 

- 프로그램이 실행되는 동안 필요한 메모리 공간을 동적으로 할당하여 프로그램의 요구에 맞게 메모리를 사용할 수 있다.

ex) malloc과 같은 메모리 할당 함수를 사용했을 때, 이 페이지를 할당한다.

 

- 가상 메모리 공간에서 실제 메모리로 데이터를 옮기거나 실제 메모리에서 가상 메모리로 데이터를 가져오는 데 사용된다.

 

- 0으로 초기화된 메모리 공간으로 할당받는다.

작동 원리

1. 메모리 할당 : 프로세스가 동적 메모리 할당을 요청하면, 운영 체제는 anonymous page를 할당하여 이 요청을 충족시킨다.

 

2. 페이지 폴트 처리 : 프로세스가 처음으로 anonymous page에 접근하면 페이지 폴트가 발생한다. 이 때, 운영체제는 해당 페이지를 물리적 메모리에 매핑하고, 필요에 따라 초기화한다.

 

3. 스왑 아웃 : 시스템 메모리가 부족할 때, 운영체제는 anonymous page를 스왑 공간으로 이동시킬 수 있다. 이는 물리적 메모리를 확보하기 위한 조치이다.

특징

· 비지속성 : anonymous page는 디스크에 있는 파일과 연결되지 않으므로 시스템이 종료되면 이 페이지에 올라와있는 데이터는 사라진다.

 

· 동적 할당 : 동적 메모리 할당 요청에 대응하여 생성되며, 프로세스의 런타임 동안만 존재한다.

 

· 스왑 가능성 : 메모리 부족 상황에서 스왑 영역으로 이동될 수 있으며, 이는 성능에 영향을 줄 수 있다.

File-backed Page(파일-백업 페이지)

- 파일 시스템에 있는 특정 파일에 직접 매핑되는 메모리 페이지를 말한다.

 

- 프로세스가 파일의 내용을 메모리에 매핑할 때 생성되며, 이는 메모리 매핑된 입출력(I / O)에서 사용된다.

작동 원리

1. 메모리 매핑 : 프로세스가 파일을 메모리에 매핑하면, 운영 체제는 파일의 내용을 메모리 페이지에 매핑한다. 이 페이지들은 파일의 실제 데이터를 반영한다.

 

2. 페이지 폴트 처리 : 프로세스가 처음으로 file-backed page에 접근하면 페이지 폴트가 발생할 수 있다. 이 경우, 운영 체제는 해당 파일의 적절한 부분을 읽어 메모리에 로드한다.

 

3. 데이터 동기화 : 프로세스가 이 페이지들을 변경하면, 변경 사항은 나중에 파일 시스템에 다시 쓰여질 수 있다. 이를 통해 파일과 메모리 간의 데이터 동기화가 이루어진다.

특징

· 지속성 : file-backed page는 디스크에 저장된 파일과 직접 연결되어 있으므로 데이터가 지속성을 가지게 된다.(디스크에 저장되므로)

 

· 효율적인 파일 접근 : 파일 입출력을 위한 시스템 호출의 오버헤드 없이 파일 데이터에 접근하고 수정할 수 있다.

 

· 동기화 옵션 : 자동 또는 수동으로 파일과 메모리 간의 동기화를 관리할 수 있다.

Lazy Loading

- OS 관점에서의 lazy loading은 프로그램이 실제로 해당 데이터를 필요로 할 때까지 데이터의 로딩을 지연시키는 기법이다.(프로그램이 시작할 때 모든 데이터를 로딩시키는 것이 아닌, 당장 필요한 것만 로딩을 시키는 방법)

 

- 이를 통해 메모리 사용의 효율을 높일 수 있고, 시스템의 전반적인 성능을 개선할 수 있다.(메모리는 한정된 자원이므로, 모든 데이터를 미리 로드하면 메모리를 불필요하게 많이 사용하게 되는 것이므로)

동작 방식

1. 디맨드 페이징(demand paging) : 프로세스가 페이지에 접근하려 할 때, 해당 페이지가 메모리에 없으면 페이지 폴트가 발생한다. 이후 운영체제는 필요한 페이지를 디스크에서 메모리로 옮긴다.

 

2. 리소스 사용 최적화 : 프로세스가 실제로 사용하지 않는 페이지는 메모리에 로드되지 않는다. 이는 시스템 리소스의 낭비를 줄이고, 사용 가능한 메모리를 더 효율적으로 사용할 수 있게 한다.

장단점

장점

· 메모리 사용을 최적화할 수 있다.

 

· 초기 로딩 시간이 감소된다.

 

·  시스템 자원을 효율적으로 사용할 수 있다. 

단점

· 페이지 폴트 발생 시 성능 저하가 일어날 수 있다.

 

· 관리가 복잡해질 수 있다.

Direct Memory Access

(관련 정리 링크 : https://jeokyong-development.tistory.com/31)

 

- DMA란 주변 장치들(I/O device)이 CPU와 독립적으로 메모리에 바로 접근하는 방식이다.

 

- DMA와 대조되는 방식으로는 Programmed I/O, Interrupt Initiated I/O가 있는데, 이 방식 모두 CPU의 개입이 필요하다.

 

- DMA는 I/O address, Memory address, Interrupt request numbers(IRQ), DMA channels 라는 4가지 리소스를 필요로 한다.

 

실제로 CPU가 control 하는 것은 DMAC(DMA Controller) 뿐이다.

Burst Mode

- Burst mode는 모든 데이터가 전송될 때까지 read, write를 반복하는 것으로, DMA mode 중 가장 빠른 방법이다.

 

- 단점 : Burst mode 동안에는 CPU가 system bus를 이용할 수 없다. 만약 데이터의 크기가 크다면 CPU는 모든 데이터가 전송될 때까지 system bus를 이용할 수 없으므로 오랜 시간동안 CPU가 제대로 작동되지 않는다.

Cycle-stealing-Mode

- Cycle-stealing-mode는 데이터 전송을 1 word씩 하게 된다.

 

- 지속적으로 입출력을 하는 장치에서 burst mode를 사용하게 되면 bus 독점 시간이 길어져 문제가 발생하게 되는데, 이 때 cycle-stealing mode를 사용하게 되면 문제가 해결된다.

 

- CPU가 system bus를 사용하다가 1 word 전송이 준비되면 system bus의 사용 권한을 DMAC에게 되돌려 준다.