멀티코어 시스템에서 운영체제의 성능을 높이기 위해서는 커널 내 자원에 대한 락 경합(Lock Contention)을 최소화해야 합니다. XV6의 기본 구현은 공유 자원에 대해 단일 전역 락을 사용하는 경우가 많아, 여러 CPU가 동시에 접근할 때 병목 현상이 발생합니다. 이 글에서는 메모리 할당기(kalloc)와 디스크 버퍼 캐시(bcache)의 구조를 변경하여 락 경합을 줄이는 방법을 다룹니다.

1. 물리 메모리 할당기(kalloc.c) 개선

기본 kalloc은 모든 CPU가 하나의 프리리스트(freelist)와 단일 락을 공유합니다. 이를 개선하기 위해 각 CPU마다 독립적인 프리리스트를 가지도록 구조를 변경합니다.

먼저 kmem 구조체를 CPU 개수만큼 배열로 선언합니다.

// kernel/kalloc.c

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem_pool[NCPU]; // 각 CPU별로 관리되는 메모리 풀

그다음 초기화 루틴인 kinit에서 각 풀의 락을 초기화합니다.

void
kinit()
{
  for(int i = 0; i < NCPU; i++) {
    initlock(&kmem_pool[i].lock, "kmem_pool");
  }
  freerange(end, (void*)PHYSTOP);
}

kfree 함수는 현재 작업을 수행 중인 CPU의 전용 풀에 메모리를 반환하도록 수정합니다.

void
kfree(void *pa)
{
  struct run *r;
  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  memset(pa, 1, PGSIZE);
  r = (struct run*)pa;

  push_off(); // 인터럽트 비활성화
  int id = cpuid();
  acquire(&kmem_pool[id].lock);
  r->next = kmem_pool[id].freelist;
  kmem_pool[id].freelist = r;
  release(&kmem_pool[id].lock);
  pop_off();
}

kalloc에서는 먼저 현재 CPU의 풀에서 메모리를 할당받으려 시도하고, 만약 부족하다면 다른 CPU의 풀에서 메모리를 가져오는(Stealing) 로직을 구현합니다.

void *
kalloc(void)
{
  struct run *r = 0;
  push_off();
  int start_id = cpuid();

  // 현재 CPU부터 시작하여 순환하며 빈 메모리 탐색
  for(int i = 0; i < NCPU; i++) {
    int target_id = (start_id + i) % NCPU;
    acquire(&kmem_pool[target_id].lock);
    r = kmem_pool[target_id].freelist;
    if(r) {
      kmem_pool[target_id].freelist = r->next;
    }
    release(&kmem_pool[target_id].lock);
    
    if(r) break;
  }
  pop_off();

  if(r)
    memset((char*)r, 5, PGSIZE);
  return (void*)r;
}

2. 디스크 버퍼 캐시(bio.c) 개선

버퍼 캐시 역시 단일 락으로 보호되는 LRU 리스트 구조에서 해시 테이블 기반의 다중 버킷 구조로 변경합니다. 각 버킷은 개별 락을 가져 병렬성을 높입니다.

먼저 buf.h 구조체에 접근 시간을 기록할 타임스탬프 필드를 추가합니다.

// kernel/buf.h
struct buf {
  int valid;
  int disk;
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  // struct buf *prev; // 기존 리스트 필드 삭제 가능
  // struct buf *next;
  uint last_access;   // LRU 대체를 위한 타임스탬프
  uchar data[BSIZE];
};

bio.c에서 해시 버킷 구조를 정의하고 전역 타임스탬프 변수를 선언합니다.

// kernel/bio.c
#define BUCKET_SIZE 13

struct {
  struct spinlock lock;
  struct buf buffers[NBUF];
} bcache_pool;

struct bucket {
  struct spinlock lock;
  struct buf head; // 버킷 내 버퍼 관리를 위한 더미 헤드
} hash_table[BUCKET_SIZE];

uint ticks_counter; // 전역 시간 카운터

uint
get_hash(uint blockno) {
  return blockno % BUCKET_SIZE;
}

binit 함수에서 버킷별 락과 버퍼들을 초기화합니다.

void
binit(void)
{
  for(int i = 0; i < BUCKET_SIZE; i++) {
    initlock(&hash_table[i].lock, "bcache_bucket");
  }

  for(int i = 0; i < NBUF; i++) {
    struct buf *b = &bcache_pool.buffers[i];
    initsleeplock(&b->lock, "buffer_sleep");
    b->refcnt = 0;
    b->last_access = 0;
  }
}

버퍼를 해제하거나 참조 횟수를 조정하는 함수들은 해당 버킷의 락만 획득하도록 수정합니다.

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  uint h = get_hash(b->blockno);
  acquire(&hash_table[h].lock);
  b->refcnt--;
  if(b->refcnt == 0) {
    b->last_access = __sync_fetch_and_add(&ticks_counter, 1);
  }
  release(&hash_table[h].lock);
  releasesleep(&b->lock);
}

void
bpin(struct buf *b) {
  uint h = get_hash(b->blockno);
  acquire(&hash_table[h].lock);
  b->refcnt++;
  release(&hash_table[h].lock);
}

void
bunpin(struct buf *b) {
  uint h = get_hash(b->blockno);
  acquire(&hash_table[h].lock);
  b->refcnt--;
  release(&hash_table[h].lock);
}

가장 핵심인 bget 함수는 요청된 블록이 이미 버킷에 있는지 확인하고, 없다면 참조되지 않은(refcnt=0) 버퍼 중 가장 오래된 것을 찾아 교체합니다.

static struct buf*
bget(uint dev, uint blockno)
{
  uint h = get_hash(blockno);
  acquire(&hash_table[h].lock);

  // 1. 해당 버킷에 이미 캐싱되어 있는지 확인
  for(int i = 0; i < NBUF; i++) {
    struct buf *b = &bcache_pool.buffers[i];
    if(b->dev == dev && b->blockno == blockno) {
      b->refcnt++;
      release(&hash_table[h].lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // 2. 캐시 미스 시 교체 대상 탐색 (전체 버퍼 중 refcnt 0이고 가장 오래된 것)
  struct buf *victim = 0;
  uint oldest_time = 0xffffffff;

  // 단순화를 위해 전체 풀에서 탐색 (실제 구현 시 버킷별 탐색이 효율적일 수 있음)
  for(int i = 0; i < NBUF; i++) {
    struct buf *b = &bcache_pool.buffers[i];
    if(b->refcnt == 0 && b->last_access < oldest_time) {
      oldest_time = b->last_access;
      victim = b;
    }
  }

  if(victim) {
    victim->dev = dev;
    victim->blockno = blockno;
    victim->valid = 0;
    victim->refcnt = 1;
    release(&hash_table[h].lock);
    acquiresleep(&victim->lock);
    return victim;
  }

  panic("bget: no buffers available");
}

마지막으로 필요한 유틸리티 함수와 전역 변수 증가 로직을 defs.h에 추가하여 외부에서 참조할 수 있도록 설정하면 최적화가 마무리됩니다. 이러한 구조 변경을 통해 멀티코어 환경에서 커널의 동시성 성능이 크게 향상됩니다.