티스토리 뷰
Fragmentation (단편화)
- External fragmentation (외부 단편화)
- 프로세스를 실행하기 위한 메모리 공간이 physical 메모리 내에 존재하지만, 연속적이지 않아서 할당할 수 없는 상황
- Internal fragmentation (내부 단편화)
- 프로세스를 실행하기 위해 메모리가 할당됐지만, 프로세스가 필요한 양보다 더 많이 할당되어 프로세스에게 할당된 메모리가 낭비되는 상황
- 50-percent rule
- First-fit을 통계적으로 분석해보면, 만약 메모리 내에서 N개의 블록이 할당되었을 때, 0.5N개의 블록이 internal fragmentation으로 손실될 수 있다. 즉, 1.5N개의 블록 중 0.5N개가 손실되므로, 메모리의 1/3을 쓸 수 없게 될 수 있다는 것을 의미한다. 이러한 현상을 50-percent rule이라고 한다.
Solutions to External Fragmentation (외부 단편화의 해결방법)
Compaction (압축)
- 외부 단편화로 분산되어 있는 메모리 공간들을 재배치하여, 하나의 큰 메모리 공간으로 확보한다.
Paging (페이징)
가상 메모리를 사용하여 프로세스를 크기가 같은 블록인 페이지로 나누고, 물리 메모리도 페이지의 크기와 동일한 프레임으로 나눈다. 페이지와 프레임을 대응하여 연속적인 물리 메모리가 아니더라도 프로세스가 필요한 만큼의 프레임을 사용할 수 있도록 하는 기법. 연속적이지 않은 메모리 공간을 활용하기 때문에 외부 단편화를 해결한다. 하지만 고정된 크기의 프레임을 할당하기 때문에 내부 단편화가 발생한다.
작은 크기의 페이지를 사용하면 내부 단편화를 줄일 수 있지만, 페이지 테이블 내의 엔트리가 증가하고, 이는 더 큰 오버헤드를 유발한다.
- Page (페이지)
- 논리 메모리를 일정한 크기로 나눈 블록
- Frame (프레임)
- 물리 메모리를 일정한 크기로 나눈 블록
CPU는 논리적 주소인 p와 d를 생성하는데, p는 page number, d는 page offset을 의미한다. 페이지의 크기는 하드웨어에 의해서 결정되는데, 주로 2의 지수형태이다. 페이지는 페이지 테이블을 통해 실제 물리 메모리의 주소로 매핑된다.
Hardware Support for Paging
페이지 테이블을 만드는 대표적인 방법으로 다음과 같이 2가지가 있다.
- CPU 내에 페이지 테이블을 만들기
- 메모리 내에 페이지 테이블을 만들기
첫 번째는 CPU 내부에 레지스터로 페이지 테이블을 만드는 것이다. 이는 주소변환을 빠르게 할 수 있지만, CPU가 사용할 수 있는 레지스터는 한정되어 있으므로 페이지 테이블의 크기가 매우 제한된다는 단점이 있다.
두 번째는 메모리 내부에 페이지 테이블을 만드는 것이다. 이는 첫 번째와 반대로 페이지 테이블의 크기에 제한이 없지만, 주소 변환 속도가 느리다는 단점이 있다. CPU는 프로세스에 접근하기 위해서 물리 메모리 내에 있는 페이지 테이블에 접근하고, 이 페이지 테이블을 다시 참조하여 물리 메모리 내의 실제 프로세스 주소로 접근하는데, 이는 2번의 메모리 접근을 하는 것이므로 매우 느리다.
위 두 가지 방법은 장단점이 너무 상반되기 때문에, 이를 해결하기 위해 페이지 테이블을 위한 캐시를 만들었다. 즉, 별도의 하드웨어를 둔 것이다. 이 하드웨어를 TLB(Translation look-aside buffer)라고 부른다. TLB는 CPU 내에 페이지 테이블을 두는 것보다 크기가 더 크고, 메모리 내에 페이지 테이블을 두는 것보다 주소 변환 속도가 더 빠르다는 장점이 있다.
Page Protection
프로세스의 모든 주소는 페이지 테이블을 경유하므로, 페이지 테이블을 이용해서 보호 기능을 수행할 수 있다. 대표적으로 valid-invalid bit를 두고, 해당 비트가 유효할 때만 프레임에 접근하도록 하는 것이다.
Page Sharing
프로세스는 code + data + stack + heap의 구조를 가지고 있다. 하나의 프로그램에서 여러 프로세스가 동일한 code를 사용한다면, 하나의 code 영역을 공유함으로써 메모리의 낭비를 줄일 수 있다. 하지만 이때 조건은, code는 reentrant(= read only) 해야 한다.
Page Table Structure
32비트 시스템은 2^32(= 4GB)만큼의 주소 공간을 가진다. 여기서 페이지의 크기가 4KB(= 2^12)라고 가정하면, 페이지 테이블이 가질 수 있는 페이지의 개수는 1MB(= 2^20, 약 100만 개)이다. 32비트 시스템에서 페이지를 나타내는 주소는 32비트(= 4B)이므로, 프로세스당 페이지 테이블의 크기는 4B * 1MB = 4MB (= 2^22)이다.
이렇게 생성된 페이지 테이블들은 프로그램이 메모리에 적재될 때 함께 적재된다. 하지만 페이지 테이블은 4MB로써 매우 큰 크기를 가진다. 이때 페이지 테이블은 연속적으로 메모리에 적재되므로 단편화로 인해 메모리 공간을 낭비하게 된다. 이를 해결하기 위해 다음과 같은 구조를 제시한다.
- Hierarchical Paging (계층적 페이징)
- Hashed Page Table (해쉬 페이지 테이블)
- Inverted Page Table (역 페이지 테이블)
Hierarchical Paging (계층적 페이징)
4MB의 연속된 메모리 공간은 생각보다 크다. 심지어 프로세스 또한 그 주소 공간 중 아주 일부분만 사용하므로, 페이지 테이블의 아주 일부분에만 접근할 것이다. 우리가 메모리 내에서 낭비되는 주소 공간을 페이징으로 해결한 것처럼, 페이지 테이블 내에서 낭비되는 공간 또한 페이징으로 해결할 수 있다.
계층적 페이징은 기존의 페이지 테이블 내의 페이지를 참조하는 또 다른 페이지 테이블(=outer page table)을 두어, 페이지 테이블을 비연속적으로 만드는 것이다.
32비트 주소체계에서, 기존의 4MB(= 2^22) 페이지 테이블은 1M(= 2^20)개의 엔트리를 가진다. Page of page table의 크기는 기존의 페이지와 동일하게 4KB(= 2^12)이므로, 1K(= 2^10)개의 엔트리를 가진다. 따라서, 기존의 페이지 테이블 내에 존재하는 page of page table은 1K(= 2^10)개가 존재한다.
Page of page table이 1K(= 2^10)개가 존재하므로 outer page table의 엔트리는 이와 동일하게 1K(= 2^10)개가 필요하고, 엔트리 한 개는 page of page table의 주소를 가리키므로 크기는 4KB(= 2^12)가 된다. 이는 페이지 1개의 크기와 동일하므로 더 이상 페이징으로 나눌 필요가 없게 된다.
위의 그림은 2번의 페이징을 통해 메모리 내의 프레임을 찾는 과정을 나타낸다.
32비트 주소 체계에서, 첫 10비트는 어떤 page of page table을 사용할지 찾는 데 사용된다. 두 번째 10비트는 우리가 메모리 내에서 어떤 프레임을 사용할지 찾는 데 사용된다. 남은 12비트는 프레임 내의 오프셋으로 사용된다.
Hashed Page Table (해쉬 페이지 테이블)
해쉬 페이지 테이블은 32비트 시스템에서 32비트보다 큰 주소를 처리할 때 사용한다. 해시 테이블의 각 항목들은 연결 리스트를 가지고 있다. 가상의 페이지 번호는 해싱되어 테이블에 저장된다. 각 연결 리스트의 항목들은 <가상 페이지 번호, 프레임 번호, 다음 항목을 향한 포인터>로 이루어져 있다. 해시 테이블로부터 물리 주소를 찾을 때 연결 리스트의 항목들로부터 가상 페이지 번호와 프레임 번호를 비교하여, 일치한다면 해당 주소를 반환한다.
Inverted Page Table (역 페이지 테이블)
기존의 페이지 테이블은 한 개의 프로세스당 한 개의 페이지 테이블을 가지고 있었다. 만약 프로세스가 많이 존재한다면, 페이지 테이블 또한 메모리에 저장되어 메모리 공간이 그만큼 필요하게 된다. 역 페이지 테이블은 시스템 내에 한 개의 전역 페이지 테이블을 두어 물리 메모리 내의 프레임에 대응하는 항목을 가진다. 이는 물리 메모리에서 실제로 사용되는 프레임만을 항목으로 가지므로 메모리의 낭비를 줄일 수 있지만, 각 프레임들이 어떤 프로세스에 의해서 사용되고 있는지 알기 위해 프로세스 ID가 필요하고, 해당 프레임이 몇 번째 페이지에 해당하는지 알기 위해 페이지 번호 또한 필요하다. 따라서 역 페이지 테이블은 <프로세스 ID, 페이지 번호>를 저장한다.
실제 물리 주소를 얻기 위해 <프로세스 ID, 페이지 번호>가 일치하는 항목을 찾고, 이때의 인덱스가 실제 메모리의 프레임 번호가 된다.
역 페이지 테이블은 메모리 공간을 많이 절약할 수 있지만, 프레임을 찾기 위해 테이블 전체를 검색해야 하므로 Linear search에 대한 오버헤드가 있다.
Solutions to Internal fragmentation (내부 단편화의 해결방법)
Segmentation (세그멘테이션)
가상 메모리를 사용하여 프로세스를 크기가 서로 다른 논리적 단위인 세그먼트로 분할하고 메모리를 할당하여 내부 단편화를 해결하는 기법. 프로세스를 메모리에 적재시키고 해제함을 반복함으로써 외부 단편화가 발생한다.
- Segment (세그먼트)
- 가상 메모리 내에서 서로 크기가 다른 논리적 단위
- 각 세그먼트는 이름(또는 숫자)과 길이를 가지고 있다.
- Segment table (세그먼트 테이블)
- 세그먼트들의 정보를 가지고 있는 테이블 <Base address, Limit>
- 테이블 내의 논리 메모리 주소를 1차원 물리 메모리 주소로 매핑한다.
CPU는 논리적 주소인 s와 d를 생성하는데, s는 segment id, d는 offset을 의미한다. 세그먼트는 세그먼트 테이블을 통해 실제 물리 메모리의 주소로 매핑된다.
'컴퓨터공학 > 운영체제' 카테고리의 다른 글
| [운영체제] 가상 메모리 관리 (2) | 2020.02.02 |
|---|---|
| [운영체제] 메모리 관리 (1) (0) | 2020.01.21 |
| [운영체제] 동기화 (2) (0) | 2020.01.14 |
| [운영체제] 동기화 (1) (0) | 2020.01.10 |
| [운영체제] 데드락 (0) | 2019.10.30 |
- Total
- Today
- Yesterday