Bitmap 사용 방법 - Week12-13-GOAT/pintos-vm GitHub Wiki

• 비트맵은 각 비트를 0 또는 1로 설정하여 어떤 자원이 사용 중인지 아닌지를 추적하는 구조야.
• 예: 페이지 프레임, 스왑 슬롯 등.
• 장점: 공간이 매우 작고 빠르게 상태 추적 가능.

struct bitmap {
    size_t bit_cnt;     // 전체 비트 수
    elem_type *bits;    // 실제 비트를 저장하는 배열 (unsigned long *)
};

• bit_cnt개의 비트를 가진 비트맵을 동적으로 생성.

• 모든 비트를 0(false)으로 초기화.

• 사용 예시:

  struct bitmap *bm = bitmap_create(1024);  // 1024개의 비트 생성
  

• 외부에서 준비된 메모리 버퍼 위에 비트맵을 생성.
• 커널이나 디스크에서 저장공간을 고정적으로 할당할 때 사용.

• malloc()으로 만든 비트맵을 메모리에서 해제.

• idx번째 비트를 value(true or false)로 설정.

• 각각 해당 비트를 1로 설정, 0으로 초기화, 0<->1 전환.
• 이 함수들은 원자적(atomic) 연산으로, 동시성 환경에서 안전함.

• idx번째 비트가 1인지 확인.

• 전체 비트를 1 또는 0으로 초기화.

• start부터 cnt개 비트를 value로 설정.

• 지정된 범위 내에서 value(0 or 1)인 비트의 개수 반환.

• 범위 내에 특정 값의 비트가 있는지 여부를 반환.

• any: 하나라도 true면 true
• none: 모두 false면 true
• all: 모두 true면 true

• start부터 cnt개 연속된 비트가 모두 value인 첫 인덱스를 반환.
• 없으면 BITMAP_ERROR 반환.
• 주로 빈 슬롯 찾을 때 사용.

size_t idx = bitmap_scan(b, 0, 1, false);  // 빈 비트 하나 찾기

• 위에서 찾은 연속된 비트를 한꺼번에 반전시킴 (0→1 또는 1→0)
• 보통 할당하면서 동시에 비트를 예약할 때 사용

size_t slot = bitmap_scan_and_flip(b, 0, 1, false);  // 사용 가능한 비트를 찾아서 할당

• 파일에서 비트맵 상태를 읽어옴

• 비트맵을 파일에 저장

이건 파일 시스템이나 스왑 디스크 상태를 복원/저장할 때 사용

• 비트맵 상태를 16진수로 출력. 디버깅할 때 유용

• 유저 프로세스에 할당된 물리 페이지 관리

struct bitmap *frame_bitmap = bitmap_create(NUM_FRAMES);
size_t f = bitmap_scan_and_flip(frame_bitmap, 0, 1, false);
void *frame = paddr_to_vaddr(f * PGSIZE);  // 물리 주소로 변환

• 디스크에 있는 스왑 슬롯 관리

struct bitmap *swap_bitmap = bitmap_create(SWAP_SLOT_COUNT);
// 스왑 아웃할 때
size_t slot = bitmap_scan_and_flip(swap_bitmap, 0, 1, false);
// 스왑 해제할 때
bitmap_reset(swap_bitmap, slot);