pintOS - project1(Thread) synch.c

synch.c

< sema_init >

// 세마포어 초기화
void
sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL); // 세마포어가 없으면 종료

	sema->value = value; // 해당 세마포어의 value값을 인자의 value로 저장
	list_init (&sema->waiters); // 해당 세마포어의 대기자를 매개로 list 초기화
}

< sema_down >

// 세마 감소(스레드 잠금 획득)
void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;
	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable (); // 인터럽트를 비활성화
	// 세마포어의 값이 0이 아닐 때까지 반복
	while (sema->value == 0) {
		// 세마포어의 대기자에 우선도 위주로 정렬해 현재 스레드의 elem을 삽입
		list_insert_ordered(&sema->waiters, &thread_current()->elem, sema_priority, NULL);
		// 스레드를 블럭(언블락될 때까지 대기)
		thread_block ();
	}
	
	thread_current()->has_lock += 1; // 현재 스레드의 lock을 1증가
	sema->value--; // 세마포어 값을 감소
	intr_set_level (old_level); // 인터럽트를 다시 복원
}

< sema_up >

// 세마 증가(스레드 잠금 해제)
void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;
	struct thread *sema_top_priority; 
	ASSERT (sema != NULL);

	old_level = intr_disable (); // 인터럽트를 비활성화
	
	// 세마포어의 대기자가 있다면
	if (!list_empty (&sema->waiters))
	{
		// 대기자를 우선도로 정렬
		list_sort(&sema->waiters, sema_priority, NULL);
		// 세마포어 대기자의 맨 앞 스레드를 저장(우선도가 가장 높음)
		sema_top_priority = list_entry(list_pop_front(&sema->waiters),
					struct thread, elem);
		// 스레드를 언블락
		thread_unblock (sema_top_priority);
	}
	
	thread_current()->has_lock -= 1; // 현재 스레드의 lock을 1감소
	sema->value++; // 세마포어 값을 증가
	intr_set_level (old_level); // 인터럽트를 다시 복원

	thread_yield(); // 실행중인 스레드와 대기자 스레드 교체
	
}

< lock_init >

// lock 초기화
void
lock_init (struct lock *lock) {
	ASSERT (lock != NULL); // lock이 없으면 종료
	lock->holder = NULL; // lock의 홀더를 NULL로 초기화
	sema_init (&lock->semaphore, 1); // lock의 세마포어에 1로 초기화
}

< lock_acquire >

// lock을 획득
void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL); // lock이 없으면 종료
	ASSERT (!intr_context ()); // 인터럽트가 실행중이면 종료
	ASSERT (!lock_held_by_current_thread (lock)); // 현재 스레드가 lock을 보유중이면 종료

	struct thread *lock_holder;
	struct thread *now = thread_current();

	if (lock->holder != NULL) // lock 홀더가 존재하면
	{
		lock_holder = lock->holder; // lock_holder에 lock의 홀더 저장
		now->wait_on_lock = lock; // 현재 스레드의 대기 중인 lock에 lock을 저장

		 // 현재 스레드의 우선도가 lock_holder의 우선도보다 크면
		if (now->priority> lock_holder->priority)
		{
			// lock_holder의 기부자에 삽입 후 현재 스레드부터 재귀
			list_insert_ordered(&lock_holder->donors, &now->donor_elem, lock_priority, NULL);
			donate_recursion(now);
		}
	}

	sema_down (&lock->semaphore); // lock의 세마포어를 매개변수로 세마를 감소
	thread_current()->wait_on_lock = NULL; // 현재 스레드의 대기중인 lock을 초기화
	lock->holder = thread_current (); // lock의 홀더에 현재 스레드 저장
}

< lock_release >

// lock을 해제
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL); // lock이 없으면 종료
	ASSERT (lock_held_by_current_thread (lock)); // 현재 스레드가 lock이 없으면 종료

	if (!list_empty(&lock->holder->donors)){ // 기부자 리스트에 스레드가 존재하면
		struct list_elem *element;
		element = list_front(&lock->holder->donors);
		
		// 요소가 빌 때까지 반복
		while(element != NULL){
			struct thread *t = list_entry(element, struct thread, donor_elem);
			// 스레드가 기다리고 있는 lock이 인자 lock과 같다면 리스트에서 제거
			if (t->wait_on_lock == lock){
				list_remove(element);
			}

			element = element->next; // 요소를 다음으로 변경
			if (element->next == NULL){ // 다음 요소가 없다면 탈출
				break;
			}
		}
	} 
	
	// 현재 스레드의 기부자 리스트에 스레드가 있다면
	if (!list_empty(&thread_current()->donors))
	{
		// 기부자 리스트의 맨 앞 스레드를 가져와서 그 스레드의 우선도를 현재 스레드 우선도에 저장
		struct thread* foremost_thread = list_entry(list_front(&thread_current()->donors), struct thread, donor_elem);
		thread_current()->priority = foremost_thread->priority;
	}
	// 기부자 리스트가 없으면
	else {
		// 현재 스레드의 원래 우선도를 우선도에 저장
		thread_current()->priority = thread_current()->original_priority;
	}

	// lock을 소유중인 스레드와 현재 스레드가 기다리고 있는 lock을 초기화한다.
	lock->holder = NULL;
	thread_current()->wait_on_lock = NULL;
	// lock의 세마포어를 증가시킨다.
	sema_up (&lock->semaphore);
}

< lock_held_by_current_thread >

// 현재 스레드가 lock을 보유하고 있는지 확인
bool
lock_held_by_current_thread (const struct lock *lock) {
	ASSERT (lock != NULL); // lock이 없으면 종료
	
	// lock을 가진 스레드가 현재 스레드면 true 아니면 false
	return lock->holder == thread_current (); 
}

< donate_recursion >

// nest나 chain에 쓰일 기부 함수 재귀 적용
void donate_recursion(struct thread *t){
	// t의 우선도가 t의 wait_on_lock의 holder의 우선도보다 크면
	if(t->priority > t->wait_on_lock->holder->priority)
		// t의 wait_on_lock의 holder의 우선도에 t의 우선도를 넣는다.
		t->wait_on_lock->holder->priority = t->priority;
	
	// // t의 wait_on_lock의 holder의 wait_on_lock이 존재하면
	if(t->wait_on_lock->holder->wait_on_lock != NULL){
		// holder를 스레드 매개변수로 재귀
		donate_recursion(t->wait_on_lock->holder);
	}
}

< cond_wait >

// 특정 조건이 충족될 때까지 대기
void
cond_wait (struct condition *cond, struct lock *lock) {
	// 특정 조건을 기다리는 스레드
	struct semaphore_elem waiter;
	// 특정 조건을 기다리는 스레드의 우선도
	waiter.sema_priority = NULL;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0); // 기다리는 스레드의 세마포어 초기화
	
	// 스레드의 우선도를 현재 스레드의 우선도로 넣기
	waiter.sema_priority = thread_current()->priority;
	
	// 특정조건을 기다리는 스레드 리스트에 우선도로 정렬하여 스레드 삽입
	list_insert_ordered (&cond->waiters, &waiter.elem, sema_elem_priority, NULL);
	lock_release (lock); // lock을 해제
	sema_down (&waiter.semaphore); // 세마포어 감소
	lock_acquire (lock); // lock을 획득
}

< cond_signal >

// 조건 변수를 기다리는 스레드를 깨워 실행
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))
		// 리스트의 맨 앞 스레드의 세마포어를 증가시킨다.
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
}

< cond_broadcast >

// 조건 변수를 기다리는 모든 스레드를 깨운다.
void
cond_broadcast (struct condition *cond, struct lock *lock) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);

	// 조건 변수를 기다리는 리스트가 빌 때까지
	while (!list_empty (&cond->waiters))
		// 스레드를 깨워 실행시킨다.
		cond_signal (cond, lock);
}