문제 상황

xv6의 파일 시스템은 디스크 블록을 bget 함수를 통해 버퍼 캐시(bcache)에서 가져옵니다.

기본 구현에서는 모든 캐시 블록을 하나의 연결 리스트에 저장하며, 리스트 접근 시 하나의 전역 락으로 동기화합니다.

그렇기 때문에 다수의 스레드가 동시에 bget을 호출할 경우, 락 경합(lock contention)이 심해져 성능 효율이 저하됩니다.

해결 방법

bcache를 해시 테이블 구조로 변경하고 각 버킷 별로 별도의 lock을 가지도록 하여, 락 경합을 줄이고 병렬성을 높였습니다.

코드

implement block cache using hash table. · plming/xv6-labs-2022@5139910

고민한 부분

해시 함수 고르기

초기에는 FNV-1a 해시 함수를 사용하여 디스크 블록 번호(blockno)를 해싱하였습니다.

하지만 blockno는 0부터 2000까지의 연속된 정수로 구성되어 있어, FNV-1a가 이와 같은 단순한 입력에 대해 기대만큼 분산되지 않았고, 일부 버킷에 충돌이 집중되는 현상이 발생했습니다.

이를 해결하기 위해, 단순한 모듈로 해시 함수(blockno % N)를 적용하였고, 충돌을 줄이기 위해 N은 소수로 선택하였습니다.

위 과정을 통해, 해시 함수의 적절성은 그 자체의 복잡도보다는 입력 데이터의 분포에 따라 결정돼야 한다는 점을 깨달았습니다.

우선순위에 기반한 교착상태 피하기

캐시된 블록을 찾지 못한 경우, 다른 버킷에서 free 블록을 가져와 현재 버킷에 추가해야 합니다.

이 과정에서는 두 개의 버킷 락을 동시에 획득하게 되며, 잘못 처리할 경우 교착상태(deadlock)가 발생할 수 있습니다.

초기 구현에서는 락 획득 순서를 고려하지 않아, 실제 테스트 중 교착 상태가 발생했습니다.

이를 해결하기 위해, 항상 버킷 번호가 작은 순서대로 락을 획득하는 우선순위 기반 방식을 도입하였습니다.