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

Contents:

우선 순위 스케줄링 구현
1. 구조체 만지기
2. synch.c
  1. sema
  2. lock

우선 순위 스케줄링 구현

오늘은 우선순위 스케줄링 할거다

일단 구조체부터 만져야 한다

구조체 만지기

우선순위 할거니까

int base_priority;
int priority;

이 두 개를 스레드 구조체에 넣어줬다

base_priority는 걍 초기 배정값

priority가 현재 상태라 보면된다

그리고 추가로 lock관련도 넣어줘야 한다

우선순위 이거 챙기는 이유가 lock 때문이니까

struct lock * waiting_lock;
struct list locks;

락 구조체에서 기다리는 락 떼오고

리스트로 locks만들어줬다

리스트는 걍 냅두면 되고

struct lock은 지금 만들어주면 된다

struct lock
{
	struct thread *holder;
	struct semaphore semaphore;
	struct list_elem elem; // holder->locks에 연결용
};

lock관련해서 필요한 애들만 담았다
현재 lock 잡고 있는 스레드
lock을 담당하는 세마포어
그리고 스레드의 락 리스트 연결을 위한 노드까지

이거 다하니 벌써 오후 3시다

구조체만 했는데 시간 ㄹㅈㄷ

synch.c

그 다음엔 synch.c에 존재하는 함수들 손봐야 한다

sema_down(), sema_up()

lock_acquire(), lock_release()

cond_wait(), cond_signal(), cond_broadcast()

이 이와 관련 있는 이들이다…

sema

세마포어와 연관 있는, 즉, 사실살 락하는 거라 보면 된다

sema_down 할 때에 waiter 리스트에 뒤 쪽에 그냥 붙이는데

이를 정렬 삽입으로 수정해줬다

별 거 없고 list_push_back을 list_insert_ordered로 바꿔준 뒤
prio_greater라는 비교 함수 하나 추가 하고 sema_down은 마무리

sema_up도 손봐줘야 한다

중간에 기부 일어나거나 하면 순서 바뀔 수 있으니

언블록 전에 정렬도 한번 하고 언블록하고 현재 실행중 스레드하고 우선순위 비교도 하고
다 해줘야 한다

그렇다, 사실 sema_down에 삽입정렬도 딱히 필요없다

속도 좀 높아진다는 것 정도 말고 말이다…

down만 하면 정렬 필요 없는 줄 알았는데 이럴거면 up 먼저 손볼걸..
하며 아쉽지만 좋은게 좋은거라 넘어가자

왜냐하면 이보다 중요한게 있으니

기존 sema_up은 단순히 waiter 리스트에서 뽑아 언블록하고 세마포어 값 올리는게 끝이었다

이를 수정해서 뽑은 뒤 현재 일어난 스레드랑 실행 중 스레드 우선순위 비교해

바로 기부 받을지 말지 등 정해줘야 한다

일단 현재랑 깨어난 거 구분 위해 선언해준다

struct thread * cur   = thread_current();
struct thread * woken = NULL;

이렇게 선언해 준 뒤

원래 함수의

if (!list_empty (&sema->waiters))
	thread_unblock (list_entry (list_pop_front (&sema->waiters),
				struct thread, elem));

이걸 살짝 수정해준다

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);
}

바로 언블록 하는대신 중간에 대기 리스트 바뀌었을 것 까지 고려해

sort 한번 해준다

그리고 pop 해준다 (sort 했으니 맨 앞의 스레드의 우선순위가 대기 중 최고 우선순위)

이렇게 깨어난 애를 woken 에 지정해주고 언블록한다

사실 여기까지도 전야제였다

이제 현재 깨어난 애랑 원래 실행중인 스레드의 우선순위를 비교해줘야 한다

bool preempt = (woken && woken->priority > cur->priority);

if (intr_context()) {
	if (preempt) intr_yield_on_return();
	intr_set_level(old_level);
} else {
	intr_set_level (old_level);
	if (preempt) thread_yield();
}

선점 관련해서 플래그 하나 만들어준다

woken이 존재하며 그 우선순위가 현재 실행중 보다 놓은지 확인

그리고 저 아래 intr_context는 안넣으면 낭패 볼 수 있다

인터럽트 핸들러 내부에서 실행된지 확인하는 건데

인터럽트 핸들러 내부일 경우에는 thread_yield()가 안되어 양보가 안된다;;

인터럽트 핸들러 안에서 안되는 것들 목록
- 블록 금지
  thread_block(), sema_down() 같이 잠들 수 있는 함수 호출 금지
- 즉시 스케줄 전환 금지
  thread_yield()로 곧장 컨텍스트 스위치 X
- 락 획득 주의
  블록될 수 있는 락/세마 획득 시도 금지

이럴 경우 핸들러 복귀 직후 양보하라고 intr_yield_on_return()을 써주면 해결! emoji

이제 cond 애들 건드려야 하는데

다행히도 cond_signal만 건드리면 될 거 같다

FIFO 방식에서 우선순위 먼저 뽑는걸로

참고로 cond 애들은 동기화 관련이다

lock

lock_acquire랑 lock_release 나오는데

lock_acquire 부터 보자

얜 뭐 안한다
lock 획득하고 그 lock의 holder를 현재 스레드로 바꿔주는게 끝이다

얘를 기부(연속 포함)랑 대기락 설정/해제 이런거 하게 해줘야 한다

겨우 2줄만 갖고 있는 놈에게 이것저것 해주려니 할게 많다

holder가 존재할때에 기부 이뤄지니

if (lock->holder != NULL)

조건문 걸어주자

그리고 인트럽트 비활성화랑 깊이 제한 걸어서
대기자 있고 정해놓은 깊이 이하일시 돌리는 while문 만든다

현재 우선순위가 대기자 우선순위보다 놓으면 대기자 우선순위 높여주는 거 넣어준뒤
대기자 없어지면 break
대기자 다음으로 넘겨주면 끝~

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;		// 대기자 우선순위 높여준다
		}
		if (hold->waiting_lock == NULL) break;  // 대기자 없으면 break!
		hold = hold->waiting_lock->holder; 		// 다음으로 대기자 재지정
	}

	intr_set_level (old);						// 인터럽트 활성화 및 복구
}

이거 해주고 난 뒤 마무리 작업 해주면 된다

생각보다 상당히 쉽지 않은? 쉬운? 애매한 작업이다

// 2) 실제 획득
sema_down(&lock->semaphore);

// 3) 보유자/상태 갱신
cur->waiting_lock = NULL;
lock->holder = cur;
list_push_back(&cur->locks, &lock->elem);

이거까지 해주고 나면 이제 다음으로 넘어가야 한다

lock_release 얘도 지금은 뭐 안한다

그러니 추가해줘야 한다

주요한 추가접은 일단 lock리스트에서 스스로 제거하기랑
다른 애들한테 받은 우선순위 영향 초기화하는거다

스스로 제거하는 건 걍
list_remov(&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)) {

    /* holder가 들고 있는 개별 lock 객체로 복원 */
    struct lock *L = list_entry(lock_ele, struct lock, elem);

    /* 이 락을 기다리는 스레드가 있으면, 그 중 최고 우선순위를 반영 */
    if (!list_empty(&L->semaphore.waiters)) {
      /* waiters에서 최고 우선순위 스레드를 하나 고른다.
         - 정책 1) waiters가 내림차순 정렬 유지: list_front() 사용 가능
         - 정책 2) 정렬 보장은 sema_up()에서: 여기서는 list_max()로 조회 */
      struct thread *top =
        list_entry(list_max(&L->semaphore.waiters, prio_greater, NULL),
                   struct thread, elem);

      /* base ← max(base, top->priority) : 실효 우선순위 후보 갱신 */
      base = max(base, top->priority);
    }
  }
cur->priority = base;							// 갱신한 거 반영

락 리스트 쓰기가 거지 같아서 어려웠고

semaphore.waiters 등 쓰는게 어려웠다

list_max는 기존에 만들어둔 조건문인

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;
}

사용해서 괜찮았다

정렬 삽입하려 만든건데 재사용 ㄱㅇㄷ

cond의 경우에는 cond_signal하나만 수정해주면 된다

숩다수어 ㅋ

…

이거하는데 3~4시간 걸린 거 같다 ㅅㅂ

총체적으로 난국인 과정이었다

별 거 아닌 거 같았는데

포인터 장난이 어지러웠다

설명은 대충 하고 넘어가겠다 너무 힘들다

/* 이 waiter를 깨우면 깨어날 스레드의 우선순위'로 비교하는 함수 */
static bool greater_waiter(const struct list_elem *a, const struct list_elem *b, void *aux) {
    const struct semaphore_elem *wa = list_entry(a, struct semaphore_elem, elem);
    const struct semaphore_elem *wb = list_entry(b, struct semaphore_elem, elem);

    /* 최고 우선순위 스레드의 priority 추출 */
    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에 대기자가 있으면, '가장 높은 우선순위를 깨어나게 할 waiter'를 골라 깨운다 */
void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
    ASSERT (cond != NULL);
    ASSERT (lock != NULL);
    ASSERT (!intr_context ());
    ASSERT (lock_held_by_current_thread (lock));

    if (!list_empty (&cond->waiters)) {
        /* 최고 우선순위 waiter(elem) 선택 */
        struct list_elem *best_elem = list_max(&cond->waiters, greater_waiter, NULL);
        /* elem → semaphore_elem 복원 */
        struct semaphore_elem *best = list_entry(best_elem, struct semaphore_elem, elem);
        /* cond 대기열에서 제거 후, 해당 waiter의 전용 세마포어를 up */
        list_remove(best_elem);
        sema_up (&best->semaphore);
    }
}

주석 적당히 적었다

너무 많은 일이 있었다…

힘들다 진짜…