Add new Edit Delete History Source Add new post
Prose.io: Add new Edit Add new post

Contents:

변경사항

중간 정리 안하고 TIL쓰려 했더니 망했다

뭘 어떻게 했는지 잘 기억안날뿐더라

전부 문제였어서 트러블 슈팅하기도 쉽지 않다

그치만 완성했으니 어떤 변경으로 구현했는지 적겠다

~~힘들때 카카시해라~~

변경사항

우선순위 선점과 도네이션 구현했다

핵심 변화

ready-list 정렬:
우선순위 내림차순 유지
삽입 시 list_insert_ordered(..., prio_greater) 사용
즉시 선점:
더 높은 우선순위 스레드가 READY일 때 바로 스레드 선점
(thread_create, sema_up)
Priority Donation:
- waiting_lock로 내가 기다리는 lock 추적
- locks(락 리스트)로 누가 나에게 기부 중인지 계산
- base_priority(원래값) + “내가 ‘보유 중인 락들’의 waiters 중 최대 우선순위”로 실효 우선순위 (priority) 산출
Nested Donation:
최대 깊이 8단계로 체인 전파
락 해제 시 복원:
해당 락 관련 기부 걷어내고 재계산
세마포어/조건변수 웨이터 정렬:
항상 가장 높은 우선순위가 먼저 깨어남

구조체 변경 사항

`struct thread` - `thread.h`에 있는 거

int base_priority; — 원래 우선순위(사용자가 설정한 값)
int priority; — 실효 우선순위(기부 반영된 현재 값)
struct lock *waiting_lock; — 현재 대기 중인 락(없으면 NULL)
struct list locks; — 내가 보유한 락들(여기 대기자들의 우선순위가 나에게 기부됨)

`struct lock` - `synch.h`에 있는 거

struct list_elem elem; — 락을 보유 스레드의 locks 리스트에 연결하기 위한 엘리먼트(새로 추가)

전역/보조 로직

내림차순 정렬 유지: 우선순위 높으면 리스트 앞
공통 비교자:
- prio_greater(a,b)— A.priority > B.priority (내림차순 정렬용)
- prio_less(a,b)— A.priority < B.priority (list_max에 사용)

파일별 상세 정리

1) `thread.h` 변경/추가

struct thread에 필드 추가
프로토타입 추가

2) `thread.c` 변경/추가

ready_list: 정렬 큐로 사용
비교자: prio_greater, prio_less
init_thread()
- base_priority = priority;
- waiting_lock = NULL;
- list_init(&t->locks);
- wakeup_tick = 0;
thread_unblock(t)
- 상태를 THREAD_READY로 바꾸고
- list_insert_ordered(&ready_list, &t->elem, prio_greater, NULL);로 우선순위 정렬 삽입
thread_yield()
- idle이 아니면 자신을 정렬 삽입 후 do_schedule(THREAD_READY)
thread_create() 새 스레드 thread_unblock()후, 새 스레드의 priority가 현재 스레드보다 높으면 즉시 선점 처리
(인터럽트 문맥이면 intr_yield_on_return 그게 아니라면 thread_yield)
우선순위 재정렬 유틸: resort_ready_if_ready(t)
- base_priority를 시작값으로, t가 보유한 모든락의 waiters중 최댓값을 반영해 t->priority 갱신
- t가 READY면 resort_ready_if_ready(t)
도네이션 체인 전파: donate_chain_from(struct thread *donor)
- donor->waiting_lock 체인을 따라 holder들에게 donor의 priority를 전파(최대 깊이 8)
- 중간에서 refresh_priority(holder) 호출로 holder의 실효 우선순위 최신화
thread_set_priority(int new_prio)
- new_prio를 [PRI_MIN, PRI_MAX]로 클램핑 후 base_priority 갱신
- refresh_priority(cur)로 현재 스레드의 실효 우선순위 재계산
- 현재 스레드가 어떤 락을 기다리는 중이면 donate_chain_from(cur)로 체인 갱신
- ready_list 맨 앞과 비교해 자신보다 높은 priority가 있으면 즉시 선점

`synch.h` 변경/추가

struct lock에 elem 추가(스레드의 locks 리스트에 넣으려고)

`synch.c` 변경/추가

세마포어

sema_down()
- sema->value == 0이면, sema->waiter에 현재 스레드를 우선순위 정렬 삽입
  (list_insert_ordered(..., prio_greater)), 그리고 thread_block()
sema_up()
- sema->value++후, sema->waiter 비었지 않으면 가장 높은 우선순위 웨이터를 꺼내(list_sort 후 pop_front) thread_unblock
- 깨어난 스레드의 priority > 현재 스레드 priority면 즉시 선점
  (인터럽트 컨텍스트면 intr_yield_on_return, 아니면 thread_yield)

락

lock_acquire(lock)
- 이미 누가 보유 중일 시:
  - cur->waiting_lock = lock; 설정
  - 도네이션 체인: holder를 따라 최대 8단계까지, cur->priority가 더 크면 holder의 priority를 올리고 resort_ready_if_ready(holder)로 위치 재정렬
    holder가 또 다른 락을 기다리는 중이면 계속 상위로 전파
- sema_down(&lock->semaphore)로 잠자고, 깨어나서 획득시
  - cur->waiting_lock = NULL;
  - lock->holder = cur;
  - list_push_back(&cur->locks, &lock->elem); (내가 가진 락 목록에 추가)
lock_release(lock)
- 내 locks에서 lock 제거 → 이제 이 락을 통해 들어오던 도네는 제거되어야 함
- 나머지 보유 락들의 대기자 최댓값을 반영해 cur->priority 재계산
  (= base_priority와 보유 락들 waiters의 최대치 중 큰 값)
- resort_ready_if_ready(cur)로 READY 재정렬
- lock->holder = NULL; 후 sema_up(&lock->semaphore)로 가장 높은 웨이터를 즉시 깨움(그리고 필요시 선점 발생)

조건 변수

cond_wait(cond, lock)
- semaphore_elem waiter를 만들고, cond->waiters에 우선순위 정렬 삽입
  (각 semaphore_elem의 내부 semaphore.waiters의 선두 priority 기준 비교)
- lock_release(lock) → sema_down(&waiter.semaphore)로 블록 → 깨어나면 lock_acquire(lock)

실제 코드

thread.h

`struct thread`에 추가된 필드들

/* struct thread 내부 - 추가된 필드들 */

/* 우선순위 */
int base_priority;                 /* 원래 우선순위 (사용자 설정값) */
int priority;                      /* 실효 우선순위 (기부 반영; 기존 priority 의미 확장) */
struct lock * waiting_lock;        /* 지금 대기 중인 락 (도네이션 체인용) */
struct list locks;                 /* 내가 보유 중인 락들 (도네이션 재계산용) */

락/세마포어/조건변수 전방 선언 추가

/* 전방 선언 추가 */
struct lock;
struct semaphore;
struct condition;

thread.c

1) ready-list를 우선순위 정렬 큐로 운영

대응: 스케줄링 핵심 → priority-fifo / priority-preempt

static bool prio_greater(const struct list_elem *a, const struct list_elem *b, void *aux) {
  const struct thread *ta = list_entry(a, struct thread, elem);
  const struct thread *tb = list_entry(b, struct thread, elem);
  return ta->priority > tb->priority;
}
static bool prio_less (const struct list_elem *a,
                       const struct list_elem *b,
                       void *aux UNUSED) {
  const struct thread *ta = list_entry (a, struct thread, elem);
  const struct thread *tb = list_entry (b, struct thread, elem);
  return ta->priority < tb->priority;
}

/* thread_unblock(): READY로 전환 시 정렬 삽입 */
void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t));
// --------------- 추가한 곳 -----------------
	old_level = intr_disable ();
	t->status = THREAD_READY;
	list_insert_ordered (&ready_list, &t->elem, prio_greater, NULL);
	intr_set_level (old_level);
// -------------------------------------------
}

/* thread_yield(): 자신을 정렬 삽입 후 양보 */
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());
// --------------- 추가한 곳 -----------------
	old_level = intr_disable ();
	if (curr != idle_thread)
		list_insert_ordered(&ready_list, &curr->elem, prio_greater, NULL);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
// -------------------------------------------
}

2) 스레드 생성 직후 더 높은 우선순위면 즉시 선점

대응: priority-preempt / priority-fifo

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;

	ASSERT (function != NULL);

// ...

	thread_unblock (t);

/* -------- thread_create() 끝부분 -------- */
	enum intr_level old = intr_disable ();
	if (t->priority > thread_current ()->priority) {
		if (intr_context ()) intr_yield_on_return ();
		else                 thread_yield ();
	}
	intr_set_level (old);
/* ---------------------------------------- */
	return tid;
}

3) init_thread: 도네이션을 위한 필드 초기화

대응: 도네이션/알람클록 인프라

/* init_thread에 추가 */
t->priority     = priority;
t->base_priority= priority;
t->waiting_lock = NULL;
list_init(&t->locks);
t->wakeup_tick  = 0;

4) READY인 경우 우선순위 바뀌면 재정렬 유틸

대응: 어디서든 priority 바뀔 때 큐 정렬 유지

// 상당히 자주 사용
void resort_ready_if_ready (struct thread *t) {
  if (t->status == THREAD_READY) {
    list_remove (&t->elem);
    list_insert_ordered (&ready_list, &t->elem, prio_greater, NULL);
  }
}

5) 실효 우선순위 재계산(보유 락 waiters 최대 반영)

대응: donate-, donate-lower 전반

/* 보유 중인 모든 락의 waiters를 고려해 t의 실효 우선순위를 다시 계산 */
static void refresh_priority(struct thread *t) {
  int base = t->base_priority;
  struct list_elem *lock_ele;
  for (lock_ele = list_begin(&t->locks);
       lock_ele != list_end(&t->locks);
       lock_ele = list_next(lock_ele)) {
    struct lock *L = list_entry(lock_ele, struct lock, elem);
    if (!list_empty(&L->semaphore.waiters)) {
      struct thread *top = list_entry(list_max(&L->semaphore.waiters, prio_less, NULL),
                                      struct thread, elem);
      if (base < top->priority) base = top->priority;
    }
  }
  t->priority = base;
  resort_ready_if_ready(t);
}

6) 도네이션 체인 전파

최대 깊이: 8

대응: donate-chain / donate-nest

static void donate_chain_from (struct thread *donor) {
  int prio = donor->priority;
  struct lock *lock = donor->waiting_lock;
  int depth = 0;

  while (lock != NULL && lock->holder != NULL && depth++ < 8) {
    struct thread *holder = lock->holder;

    refresh_priority(holder);         // holder의 실효값 최신화
    if (holder->priority < prio)
      holder->priority = prio;

    if (holder->waiting_lock == NULL) break;
    lock = holder->waiting_lock;
  }
}

7) thread_set_priority: base 변경 → 재계산 → 필요 시 체인 갱신/선점

대응: priority-change / donate-… 케이스 안정화

void thread_set_priority (int new_priority) {
  enum intr_level old = intr_disable();
  struct thread *cur = thread_current();

  if (new_priority < PRI_MIN) new_priority = PRI_MIN;
  if (new_priority > PRI_MAX) new_priority = PRI_MAX;
  cur->base_priority = new_priority;

  refresh_priority(cur);                  // 보유 락 고려해 실효 재계산

  bool preempt = false;
  if (cur->waiting_lock != NULL)
    donate_chain_from(cur);               // 대기 중이면 체인 갱신

  if (!list_empty(&ready_list)) {
    struct thread *top = list_entry(list_front(&ready_list), struct thread, elem);
    preempt = (top->priority > cur->priority);
  }
  intr_set_level(old);

  if (preempt) thread_yield();
}

synch.h

`struct lock`에 리스트 엘리먼트 추가

/* struct lock 내부 - 추가된 필드 */
struct list_elem elem;    /* holder->locks 에 연결하기 위한 엘리먼트 */

synch.c

1) 세마포어 waiters 우선순위 정렬 삽입

대응: sema_down 대기자 정렬 → priority-sema / priority-preempt

static bool prio_greater(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
  const struct thread *ta = list_entry(a, struct thread, elem);
  const struct thread *tb = list_entry(b, struct thread, elem);
  return ta->priority > tb->priority;
}
static bool prio_less (const struct list_elem *a,
                       const struct list_elem *b,
                       void *aux UNUSED) {
  const struct thread *ta = list_entry (a, struct thread, elem);
  const struct thread *tb = list_entry (b, struct thread, elem);
  return ta->priority < tb->priority;
}

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
/* --- sema_down(): waiters에 우선순위 정렬 삽입 --- */
	while (sema->value == 0) {
		list_insert_ordered (
			&sema->waiters,
			&thread_current ()->elem,
			prio_greater,
			NULL
		);
		thread_block ();
/* ------------------------------------------------ */
	}
	sema->value--;
	intr_set_level (old_level);
}

2) 세마포어 up 시 최고 우선순위 먼저 깨우고 즉시 선점

대응: sema_up 선점 보장 → priority-preempt / priority-sema / donate-sema

/* --------- 사실상 다 바뀜 ㅇㅇ --------- */
void sema_up (struct semaphore *sema) {
  enum intr_level old_level;
  struct thread *cur   = thread_current();
  struct thread *woken = NULL;

  old_level = intr_disable ();
  sema->value++;
  if (!list_empty (&sema->waiters)) {
    list_sort (&sema->waiters, prio_greater, NULL);
    struct list_elem *e = list_pop_front (&sema->waiters);
    woken = list_entry (e, struct thread, elem);
    thread_unblock (woken);
  }
  intr_set_level (old_level);

  if (woken && woken->priority > cur->priority) {
    if (intr_context()) intr_yield_on_return();
    else                thread_yield();
  }
}

3) lock_acquire: waiting_lock 설정 + 도네이션 체인 전파

대응: donate-one / donate-multiple / donate-chain / donate-nest

void lock_acquire (struct lock *lock) {
  ...
  struct thread *cur = thread_current();

  if (lock->holder != NULL) {
    enum intr_level old = intr_disable();
    cur->waiting_lock = lock;

    struct thread *hold = lock->holder;
    int depth = 0;
    while (hold && depth++ < 8) {
      if (cur->priority > hold->priority) {
        hold->priority = cur->priority;
        resort_ready_if_ready (hold);
      }
      if (hold->waiting_lock == NULL) break;
      hold = hold->waiting_lock->holder;
    }
    intr_set_level (old);
  }

  sema_down (&lock->semaphore);

  cur->waiting_lock = NULL;
  lock->holder = cur;
  list_push_back(&cur->locks, &lock->elem);
}

4) lock_release: 보유 락 목록 기반 실효 우선순위 재계산 + 재정렬

대응: donate-lower / donate-multiple2 / donate-sema (복원)

void lock_release (struct lock *lock) {
  ...
  enum intr_level old = intr_disable();
  struct thread *cur = thread_current();
  list_remove(&lock->elem);

  int base = cur->base_priority;
  struct list_elem *lock_ele;
  for (lock_ele = list_begin(&cur->locks);
       lock_ele != list_end(&cur->locks);
       lock_ele = list_next(lock_ele)) {
    struct lock *L = list_entry(lock_ele, struct lock, elem);
    if (!list_empty(&L->semaphore.waiters)) {
      struct thread *top = list_entry(list_max(&L->semaphore.waiters, prio_less, NULL),
                                      struct thread, elem);
      if (base < top->priority) base = top->priority;
    }
  }
  cur->priority = base;
  resort_ready_if_ready(cur);
  lock->holder = NULL;
  intr_set_level(old);

  sema_up (&lock->semaphore);
}

5) 조건변수: 웨이터 우선순위 기준 signal

대응: priority-cond / priority-sema (CV 대기자도 우선순위 반영)

/* cond_wait을 위한 선물 */
static bool greater_waiter (const struct list_elem *a,
                            const struct list_elem *b,
                            void *aux UNUSED) {
  struct semaphore_elem *wa = list_entry(a, struct semaphore_elem, elem);
  struct semaphore_elem *wb = list_entry(b, struct semaphore_elem, elem);
  int pa = list_empty(&wa->semaphore.waiters) ? -1
         : list_entry(list_front(&wa->semaphore.waiters), struct thread, elem)->priority;
  int pb = list_empty(&wb->semaphore.waiters) ? -1
         : list_entry(list_front(&wb->semaphore.waiters), struct thread, elem)->priority;
  return pa > pb;
}

/* cond_wait(): cond->waiters에 우선순위 정렬 삽입 */
void cond_wait (struct condition *cond, struct lock *lock) {
  struct semaphore_elem waiter;
  sema_init (&waiter.semaphore, 0);
  list_insert_ordered (&cond->waiters, &waiter.elem, greater_waiter, NULL);
  lock_release (lock);
  sema_down (&waiter.semaphore);
  lock_acquire (lock);
}

/* cond_signal을 위한 선물 */
static bool waiter_less (const struct list_elem *a,
                         const struct list_elem *b,
                         void *aux UNUSED) {
  const struct semaphore_elem *wa = list_entry (a, struct semaphore_elem, elem);
  const struct semaphore_elem *wb = list_entry (b, struct semaphore_elem, elem);
  int pa = list_empty(&wa->semaphore.waiters) ? PRI_MIN - 1
           : list_entry(list_front(&wa->semaphore.waiters), struct thread, elem)->priority;
  int pb = list_empty(&wb->semaphore.waiters) ? PRI_MIN - 1
           : list_entry(list_front(&wb->semaphore.waiters), struct thread, elem)->priority;
  return pa < pb;
}

/* cond_signal(): 가장 높은 우선순위 waiter 선택 */
void cond_signal (struct condition *cond, struct lock *lock UNUSED) {
  if (!list_empty (&cond->waiters)) {
    struct list_elem *best_elem = list_max(&cond->waiters, waiter_less, NULL);
    struct semaphore_elem *best = list_entry(best_elem, struct semaphore_elem, elem);
    list_remove(best_elem);
    sema_up (&best->semaphore);
  }
}

여담

가장 골때렸던 건
로직 고려해 다 완성해놓고
thread_create에 언블록 까지만 넣고
우선순위 높으면 바로 선점하는 거 안넣어 개같이 굴렀던 경험이다

그리고 return a > b; 같은 비교함수 쓸때 좀 헷갈렸다
초반에 정확히 안짚고 넘어가
내림차 순 정리할때랑 최댓값 정할때 똑같이 써버려
무한 츠쿠요미에 빠졌고
원인 찾느라 하루는 쓴거 같다