이번 주차에 필요한 대부분의 개념들(가상메모리, 페이징, 동적 메모리 할당, 메모리 단편화 등)을 정리했다.
Virtual Memory
시스템의 프로세스들은 CPU와 메인 메모리를 다른 프로세스들과 공유한다. 그렇기 때문에 프로세스들이 CPU에 대한 요구가 많아질 때마다 프로세스들은 점점 느려지고, 너무 많은 메모리를 요구하면 프로세스를 실행할 수조차 없다. 실제 메모리의 크기는 한정되어있기 때문에 모든 프로세서에 다 할당할 수 없는 상황이 오는 것이다. 이전에는 메인 메모리의 물리적인 주소에 접근해서 저장하는 물리 주소 방식을 사용했었으나, 현대의 프로세스들은 가상 메모리 시스템을 이용한 가상 주소 방식을 사용한다.
가상 메모리라는 것은 내가 사용할 수 있는 물리적인 메모리의 크기와 상관없이 작업할 수 있는 커다란 공간이다. 가상메모리의 중요 기능은 다음과 같다.
- 메인메모리를 캐시로 취급해서 디스크와 메모리 간에 필요에 따라 전송하여 효율적으로 사용
- 프로세스에 통일된 주소공간을 제공해서 메모리 단순화(메모리 용량 다운)
- 프로세스 주소공간을 다른 프로세스들에게 침범받지 않게끔 보호
이론적으로 가상 메모리는 무한대의 공간을 가지고 있지만, 실질적으로 가상 메모리의 최대 크기는 컴퓨터가 가지고 있는 물리적인 메모리의 크기이다.
그렇다면 어떻게 무한대로 사용할 수 있는 것처럼 보이는 것일까?
평소에는 프로세스가 가상 주소를 사용하는데, 데이터를 읽고 쓸 때만 물리주소로 바꿔주는 형태이기 때문이다. CPU가 어떤 특정 프로세스를 참조할 때 가상 주소를 먼저 참조하고 그 다음 물리 주소를 참조한다. 가상 주소 참조 >> 물리 주소 참조라는 과정을 짧게 하기 위해 MMU(Memory Management Unit)라는 하드웨어 칩의 지원을 받는다.
Processor >> Virtual Memory >> MMU >> Physical Memory >> Main Memory
페이징(Paging)이란?
가상메모리가 메모리를 더 효율적으로 관리하기 위한 기법이다. 가상 메모리애서 메인 메모리 사이에 페이지를 전송하는 동작을 페이징이라고 한다. 쉽게 말해 페이지 단위로 메모리를 관리하겠다는 것이다. 그래서 페이지는 가상 메모리를 일정한 크기로 나눈 블록이고 이러한 페이지를 모아서 보관하는 곳이 페이지 테이블(Page Table)이다. 각각의 PTE(Page Table Entry, 페이지 테이블에 포함되어 있는 각각의 블록을 이렇게 칭한다)에는 한 개의 유효비트(Valid)와 주소가 담겨있다.
유효비트는 0 혹은 1로 표시하며 0이라면 가상페이지가 아직 할당되지 않음을 뜻하고 1은 할당되었음을 뜻한다. 아래 그림을 보면 지금 VP 1, 2, 4, 7은 메인 메모리에 캐시되어있으며(Cached) VP 0, 5는 아직 할당되지 않았다(Unallocated). VP 3, 6은 할당되었으나 아직 캐시되지 않은 상태(Uncached)이다.
Page Hit(페이지 적중)
메모리에 있는 어떤 페이지를 불러오고 싶을 때, 메모리에 해당 페이지가 있다면 페이지 적중이다.
VP 2를 읽어온다고 가정하자. 주소 번역 하드웨어가 PTE 2를 찾기 위해서 가상 주소를 사용해 메모리로부터 읽어올 것이다. 유효비트가 1로 설정되어 있기 때문에 VP 2가 메모리에 캐시되었다는 것을 확인하고 PTE 내에 물리메모리를 사용해서(PP 1 가르키는 부분) 물리 주소를 구성한다.
Page Fault(페이지 부재)
메모리에서 어떠한 페이지를 불러오려고 시도했으나 해당 페이지가 없을 때 페이지 오류가 발생한다. 오류가 발생하면 희생자 페이지를 선택해서 해당 페이지를 메모리에서 제거한 후 우리가 불러오려고 했던 페이지를 메모리에 넣는다.
VP 3을 읽어온다고 가정하자. 주소 번역 하드웨어가 PTE 3을 읽어왔지만 유효비트가 0으로 설정되어 있기 때문에 캐시되어 있지 않음을 확인하고 페이지 오류 예외를 발생시킨다.
페이지 오류 예외 핸들러는 희생자 페이지를 선택하게 된다(이 그림에서는 PP 3에 저장된 VP 4를 선택했다). VP 4가 수정되었다면 커널이 VP 4를 디스크에 복사하고 PTE를 수정해서 VP 4가 메인 메모리에 캐시되지 않았음을 반영한다. 그리고 VP 3을 디스크에서 PP 3으로 복사하고 PTE 3을 갱신한다.
이러한 방식으로 요구하는 페이지들만 메모리에 올리고 필요하지 않은 메모리들은 디스크에 저장하는 것을 요구 페이징(Demand Paging)이라고 한다.
주소 번역 과정(Address Translation)
아까 가상메모리 쪽에서 설명했던 과정과 비슷하지만 페이지 적중과 오류를 적용한 것이다. 페이지 적중만 간단히 설명 후 넘어가겠다.
- 프로세서가 가상 주소 생성 후 MMU로 전달한다
- MMU가 PTEA(PTE 주소)를 생성하고 메모리에 요청한다
- 메모리는 PTE를 MMU에 전달한다
- MMU는 물리 주소를 구성하고 메모리로 보낸다
- 메모리는 요청한 데이터를 다시 프로세서로 보낸다
페이지 부재시에는 밑 그림처럼 처리된다.
TLB(Translation Lookaside Buffer)
위 과정을 실행했을 때 MMU가 물리 주소를 구성하고 메모리에 접근하는 시간이 꽤나 오래 걸리기 때문에, 이를 해결하기 위해 TLB라는 최근 페이지 정보의 캐시를 저장하는 장치의 도움을 받는다.
TLB의 도움을 받게 되면 한 번 변환되었던 물리 주소는 TLB에 저장되어 MMU가 페이지 테이블에 다녀오지 않아도 TLB에서 해당하는 물리주소를 찾을 수 있다. 메모리에 반복적으로 접근하지 않아도 되기 때문에 시간 단축이 가능한 것이다.
다중 단계 페이징
만드는 프로그램의 용량이 메모리에 용량보다 적을 때, 쓰이지 않는 남은 용량들을 모두 페이지 테이블에 올리게 되면 많은 공간을 낭비하게 된다. 이를 방지하기 위해 페이지 정보를 나누어 생성하는 것을 다중 단계 페이징이라고 부른다.
데이터가 없으면(NULL이면) 페이지를 생성하지 않고, 데이터가 있는 영역에 한해서 페이지 디렉토리별로 페이지를 생성한다.
동적 메모리 할당
동적 프로그래밍이란 프로그램이 실행되는 도중에 사용자가 원하는 크기의 메모리를 할당받고 싶을 때 사용하는 방법이다. 동적 할당된 메모리는 힙(heap)영역에 저장되고 malloc과 free를 호출하여 메모리를 할당하고 해제한다.
명시적 할당기- 애플리케이션이 명확하게 할당된 블록을 반환해줄 것을 요구한다.
e.g. malloc 호출해서 함수 할당 후 free해서 메모리 반환
묵시적 할당기 - 반환 요구를 하지 않아도 프로그램에 의해 사용되고 있지 않은 블록이 있다면 할당기가 검출해서 반환한다.
e.g. java에 garbage collector- 사용하지 않는 할당된 블록을 자동적으로 반환
메모리 단편화(Fragmentation)
메모리 단편화란 메모리가 할당되고 해제되는 과정에서 메모리 공간이 작은 조각으로 나뉘어져 사용 가능한 메모리가 충분히 남았음에도 불구하고 할당이 불가능한 상태를 의미한다.
내부 단편화 - 할당된 블록의 크기가 데이터보다 더 클 때 나타난다.
예를 들어, 10KB만큼을 할당했으나 6KB밖에 사용하지 않았을 때, 4KB가 낭비되고 있는 것이 내부 단편화이다.
외부 단편화 - 아래 그림과 같이 빈칸을 모두 합치면 6칸을 할당할 수 있으나 6칸이 이어져있지 않아 할당이 불가한 경우를 외부 단편화라고 한다. 메모리에 공간은 남아있으나 공간이 이어져있지 않아서 커널에 추가적인 가상 메모리를 요청할 수밖에 없다.
묵시적 가용 리스트
추가예정
명시적 가용 리스트
할당한 블록 배치
First Fit - 가용 free list를 처음부터 검색해서 크기가 맞는 첫번째 가용블록을 선택한다. First fit의 장점은 리스트 마지막에 가장 큰 가용블록들을 남겨둔다는 것이다. 하지만 그만큼 리스트 앞부분에 작은 블록들을 남겨둬서 큰 블록들을 찾는 경우에는 검색 시간이 증가한다.
Next Fit- 이전에 검색이 종료된 시점에서 검색을 시작해서 크기가 맞는 가용블록을 선택한다. Next fit은 First fit의 대안으로 고안되었기 때문에 First fit에 비해 빠른 탐색 시간을 갖는다. 특히 앞부분이 작은 크기의 조각들로 구성되어 있으면 더 빠르다. 하지만 메모리 사용량이 크다.
Best Fit- 모든 가용 블록을 검사해서 크기가 맞는 가장 작은 블록을 선택한다. Best fit은 위 둘 방법과 비교했을 때 더 좋은 메모리 사용량을 가지고 있으나, 단순한 가용 리스트를 탐색할 때의 단점은 힙을 완전히 다 검색해야한다는 것이다.
출처 및 참고 자료
CSAPP 책
https://velog.io/@gndan4/OS-%EA%B0%80%EC%83%81-%EB%A9%94%EB%AA%A8%EB%A6%AC#%ED%8E%98%EC%9D%B4%EC%A7%95-%EA%B0%9C%EB%85%90
https://velog.io/@supssson/%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%8B%A8%ED%8E%B8%ED%99%94
