Pintos에는 페이지 단위로 메모리를 할당하는 할당자와 임의 크기의 블록을 할당할 수 있는 할당자, 두 가지 메모리 할당자가 있습니다.

페이지 할당자

include/threads/palloc.h에 선언된 페이지 할당자는 페이지 단위로 메모리를 할당합니다. 대부분 한 번에 한 페이지씩 메모리를 할당하는 데 사용되지만, 한 번에 여러 개의 연속된 페이지를 할당할 수도 있습니다. 페이지 할당자는 할당하는 메모리를 커널 풀과 사용자 풀이라는 두 개의 풀로 나눕니다. 기본적으로 각 풀은 1MB 이상의 시스템 메모리의 절반을 가지지만, ul 커널 명령행 옵션으로 분할을 변경할 수 있습니다. 할당 요청은 한 풀 또는 다른 풀에서 가져옵니다. 한 풀이 비어도 다른 풀에는 여전히 사용 가능한 페이지가 있을 수 있습니다. 사용자 풀은 사용자 프로세스를 위한 메모리 할당에 사용되어야 하고, 커널 풀은 다른 모든 할당에 사용되어야 합니다. 이는 프로젝트 3부터 중요해질 것입니다. 그때까지는 모든 할당이 커널 풀에서 이루어져야 합니다.

각 풀의 사용량은 풀의 페이지당 한 비트씩 비트맵으로 추적됩니다. n 페이지를 할당하는 요청은 해당 페이지가 사용 가능함을 나타내는 false로 설정된 n개의 연속 비트를 비트맵에서 검색한 다음, 해당 비트를 true로 설정하여 사용 중임을 표시합니다. 이는 "최초 적합" 할당 전략입니다.

페이지 할당자는 단편화될 수 있습니다. 즉, n개 이상의 페이지가 사용 가능한 경우에도 사용 가능한 페이지가 사용 중인 페이지로 분리되어 있기 때문에 n개의 연속 페이지를 할당하지 못할 수 있습니다. 실제로 병리학적인 경우에는 풀의 페이지 절반이 사용 가능함에도 불구하고 2개의 연속 페이지를 할당하지 못할 수 있습니다. 단일 페이지 요청은 단편화로 인해 실패할 수 없으므로, 여러 연속 페이지에 대한 요청은 가능한 한 제한해야 합니다. 페이지는 인터럽트 컨텍스트에서 할당될 수 없지만, 해제될 수는 있습니다.

페이지가 해제되면 디버깅 지원을 위해 모든 바이트가0xcc로 지워집니다(Debugging Tips 참조).

페이지 할당자 유형과 함수는 아래에 설명되어 있습니다.

void *palloc_get_page (enum palloc_flags flags)
void *palloc_get_multiple (enum palloc_flags flags, size_t page_cnt)

각각 하나의 페이지 또는 page_cnt 개의 연속 페이지를 얻어 반환합니다. 페이지를 할당할 수 없는 경우 널 포인터를 반환합니다. flags 인수는 다음 플래그의 조합일 수 있습니다:

PAL_ASSERT 페이지를 할당할 수 없는 경우 커널을 패닉 상태로 만듭니다. 이는 커널 초기화 중에만 적절합니다. 사용자 프로세스는 절대 커널을 패닉 상태로 만들어서는 안 됩니다. PAL_ZERO 할당된 페이지를 반환하기 전에 모든 바이트를 0으로 만듭니다. 설정되지 않은 경우 새로 할당된 페이지의 내용은 예측할 수 없습니다. PAL_USER 사용자 풀에서 페이지를 가져옵니다. 설정되지 않은 경우 커널 풀에서 페이지가 할당됩니다.

void palloc_free_page (void *page)
void palloc_free_multiple (void *pages, size_t page_cnt)

각각 pages에서 시작하는 하나의 페이지 또는 page_cnt 개의 연속 페이지를 해제합니다. 모든 페이지는 palloc_get_page() 또는 palloc_get_multiple()을 사용하여 얻어야 합니다.

블록 할당자

threads/malloc.h에 선언된 블록 할당자는 임의의 크기로 블록을 할당할 수 있습니다. 이는 이전 섹션에서 설명한 페이지 할당자 위에 계층화되어 있습니다. 블록 할당자가 반환하는 블록은 커널 풀에서 얻어옵니다.

블록 할당자는 메모리를 할당하기 위해 두 가지 다른 전략을 사용합니다. 첫 번째 전략은 1kB 이하의 블록(페이지 크기의 1/4)에 적용됩니다. 이러한 할당은 가장 가까운 2의 거듭제곱 또는 16바이트 중 더 큰 값으로 반올림됩니다. 그런 다음 해당 크기의 할당에만 사용되는 페이지로 그룹화됩니다.

두 번째 전략은 1kB보다 큰 블록에 적용됩니다. 이러한 할당(약간의 오버헤드 포함)은 크기 면에서 가장 가까운 페이지로 반올림된 다음, 블록 할당자는 페이지 할당자에게 해당 수의 연속 페이지를 요청합니다.

어느 경우든 요청된 할당 크기와 실제 블록 크기의 차이는 낭비됩니다. 실제 운영 체제는 이러한 낭비를 최소화하기 위해 할당자를 신중하게 조정하겠지만, 이는 Pintos와 같은 교육용 시스템에서는 중요하지 않습니다.