[PintOS, Project1] Priority_Scheduling and Synchronization (semaphore 관련)

 지금까지 작업한 pintos에서 thread가 semaphore를 가져가는 순서는 FIFO순으로 되어있다. 이것은 priority가 높은 순으로 semaphore를 가져갈 수 있도록 할 것이다.

 

@/include/threads/synch.h


/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

 struct semaphore는 semaphore를 관리하기 위한 구조체로서 semaphore의 현재 상태인 value와 이 semaphore를 기다리는 waiters(list 구조체) 가 있다. 

 

 semaphore와 관련된 함수들을 보자. 처음은 sema_init이다.

@/threads/synch.c

/* Initializes semaphore SEMA to VALUE.  A semaphore is a
   nonnegative integer along with two atomic operators for
   manipulating it:

   - down or "P": wait for the value to become positive, then
   decrement it.

   - up or "V": increment the value (and wake up one waiting
   thread, if any). */
   
void sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL);

	sema->value = value;
	list_init (&sema->waiters);
}

  말 그대로 semaphore를 초기화하는 함수이다. value는 사용자 정의이지만, semaphore가 사용 가능이면 1 이상을 넣을 것이고 (현재는 1이 최대이다.) 아니라면 0을 넣을 것이다.

 

@/threads/synch.c

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
   to become positive and then atomically decrements it.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but if it sleeps then the next scheduled
   thread will probably turn interrupts back on. This is
   sema_down function. */
   
void sema_down (struct semaphore *sema) {
	enum intr_level old_level;

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

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_push_back (&sema->waiters, &thread_current ()->elem);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 sema_down은 thread(running 중)가 semaphore를 요청할 때 사용하는 함수이다. 이 함수는 semaphore가 가용이든 불가용이든 일단 실행된다. 만약 semaphore가 불가용이라면 (sema->value == 0) semaphore를 기다리는 리스트인 waiters에 들어가고 block상태로 들어간다. 

 

 여기서 중요한 것은 block되면서 thread는 thread_block()에서 멈추고, block상태로 들어간다(정지).

 

 그리고 sema_up()으로 일어날 때, thread는 thread_block(); 부터 시작한다. 그러나 이 때, (별일이 없다면) sema->value 는 1이기 때문에 semaphore를 획득할 수 있다. 

 

 

@/threads/synch.c

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	sema->value++;
	intr_set_level (old_level);
}

 이것은 semphore를 가진 thread가 더이상 semaphore가 필요없어졌을 때 발생하는 함수이다.

 

 이 semaphore를 위해 대기하는 thread가 있다면 (if (!list_empty (&sema->waiters))) 그 대기줄(waiters)에서 가장 앞에 있는 thread를 unblock한다.

 

 ※ sema_up()이 끝나고 나면, 그 thread는 위의 sema_down()에서 thread_block() 다음부터 실행할 것이다. 그리고 이 sema_up()에서 sema->value를 ++해줬으므로 아마 그 thread는 while (sema->value == 0) 를 탈출하고 semaphore를 획득할 것이다.

 

 

 

 이 semaphore를 관리하는 것에는 여러가지 방법이 있다. 이번 프로젝트에서는 lock과 condition_variable을 사용하여 관리할 것이다.

 

 

※ PintOS에서의 Monitor system은 하기의 링크를 참조하라.

[PintOS, Project1] Condition Variable을 이용한 Monitor System (tistory.com)

[PintOS, Project1] Condition Variable을 이용한 Monitor System

 

 

@/threads/synch.c

/* Initializes LOCK.  A lock can be held by at most a single
   thread at any given time.  Our locks are not "recursive", that
   is, it is an error for the thread currently holding a lock to
   try to acquire that lock.

   A lock is a specialization of a semaphore with an initial
   value of 1.  The difference between a lock and such a
   semaphore is twofold.  First, a semaphore can have a value
   greater than 1, but a lock can only be owned by a single
   thread at a time.  Second, a semaphore does not have an owner,
   meaning that one thread can "down" the semaphore and then
   another one "up" it, but with a lock the same thread must both
   acquire and release it.  When these restrictions prove
   onerous, it's a good sign that a semaphore should be used,
   instead of a lock. */
void
lock_init (struct lock *lock) {
	ASSERT (lock != NULL);

	lock->holder = NULL;
	sema_init (&lock->semaphore, 1);
}

 lock은 semaphore와 lock->holder를 가지고 있는 구조체이다. lock->holder 는 thread이며, semaphore는 어떤 thread가 lock을 가질 수 있는지(sema->value > 0), 가질 수 없다면 대기리스트(waiters)에 들어간다.

 

 

@/threads/synch.c

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
   
void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	sema_down (&lock->semaphore);
	lock->holder = thread_current ();
}

 running중인 thread가 어떤 임계 영역을 써야될 때, 해당 임계영역을 사용가능한가 (semaphore->value > 0) 를 확인한다. 이 thread가 lock을 얻는다면 lock->holer 를 thread_current()로 지정한다.

 

 

@/threads/synch.c

/* Releases LOCK, which must be owned by the current thread.
   This is lock_release function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock));

	lock->holder = NULL;
	sema_up (&lock->semaphore);
}

 lock의 semaphore를 다 사용하고 나면 lock을 반납한다. 

 

 

 

 

여기서부터는 condition_variable 로 semaphore를 다룬다. 

@/threads/synch.c

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

  conditional variable로 관리한다. 여기서는 signal로 관리하기때문에 대기 리스트(waiters)만 필요로 한다. 

 

@/threads/synch.c

/* Initializes condition variable COND.  A condition variable
   allows one piece of code to signal a condition and cooperating
   code to receive the signal and act upon it. */
void
cond_init (struct condition *cond) {
	ASSERT (cond != NULL);

	list_init (&cond->waiters);
}


/* Atomically releases LOCK and waits for COND to be signaled by
   some other piece of code.  After COND is signaled, LOCK is
   reacquired before returning.  LOCK must be held before calling
   this function.

   The monitor implemented by this function is "Mesa" style, not
   "Hoare" style, that is, sending and receiving a signal are not
   an atomic operation.  Thus, typically the caller must recheck
   the condition after the wait completes and, if necessary, wait
   again.

   A given condition variable is associated with only a single
   lock, but one lock may be associated with any number of
   condition variables.  That is, there is a one-to-many mapping
   from locks to condition variables.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
   
void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

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

	sema_init (&waiter.semaphore, 0);
	list_push_back (&cond->waiters, &waiter.elem);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}



/* If any threads are waiting on COND (protected by LOCK), then
   this function signals one of them to wake up from its wait.
   LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
   
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);
}



/* Wakes up all threads, if any, waiting on COND (protected by
   LOCK).  LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
   
void
cond_broadcast (struct condition *cond, struct lock *lock) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);

	while (!list_empty (&cond->waiters))
		cond_signal (cond, lock);
}

 위의 cond관련 함수들은 위의 Monitor관련 참조글에 설명되어있다.

 

 

 

우선 semaphore_elem을 받아와서 해당 semphore의 주인 thread의 priority를 비교할 수 있는 함수를 만든다. 이는 cmp_priority와 거의 유사하다. 

@/threads/thread.c

/*-------------------------- project.1-Priority Sync -----------------------------*/
bool cmp_sem_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
	struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);
	
	struct list_elem *sa_e = list_begin(&(sa->semaphore.waiters));
	struct list_elem *sb_e = list_begin(&(sb->semaphore.waiters));

	struct thread *sa_t = list_entry(sa_e, struct thread, elem);
	struct thread *sb_t = list_entry(sb_e, struct thread, elem);

	return (sa_t->priority) > (sb_t->priority);
}
/*-------------------------- project.1-Priority Sync -----------------------------*/

 

 

 

  위에서 만든 cmp_sem_priority()를 이용하여, priority순대로 삽입될 수 있도록 한다.

 

@threads/thread.c

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

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

	old_level = intr_disable ();
	while (sema->value == 0) {
		// list_push_back (&sema->waiters, &thread_current ()->elem);
		/*-------------------------- project.1-Priority Sync -----------------------------*/
		list_insert_ordered(&sema->waiters, &thread_current ()->elem, &cmp_priority, NULL);
		/*-------------------------- project.1-Priority Sync -----------------------------*/
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 

 

 

 

※ 우선순위로 정렬하는 것은 사실 이 챕터에선 필요없다. 왜냐하면 우선순위가 변경되는 것은 running_thread의외는 없기 때문이다. waiter_list에 있는 thread의 priority가 변경되는 일은 차후 단계의 donation에서 일어난다.

 

 thread_unblock으로 ready_list에 들어간 thread가 running중인 thread보다 더 우선순위가 높을 수 있으므로 priority prrmption()을 실행해준다. 

 

@threads/synch.c

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

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
		{
			/*-------------------------- project.1-Priority Sync -----------------------------*/
			list_sort(&sema->waiters, &cmp_priority, NULL);
			/*-------------------------- project.1-Priority Sync -----------------------------*/
			thread_unblock (list_entry (list_pop_front (&sema->waiters), struct thread, elem));
		}
	sema->value++;
	/*-------------------------- project.1-Priority Sync -----------------------------*/
	test_max_priority();
	/*-------------------------- project.1-Priority Sync -----------------------------*/
	intr_set_level (old_level);
}

 

 

 

 

 cond 관련 수정사항은 위의 sema와 같다. 마찬가지로 대기 중에 우선순위가 변경되는 것은 실제로는 차후의 donation에서 일어나는 일이다. 

 

@/threads/synch.c

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

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

	sema_init (&waiter.semaphore, 0);
	/*-------------------------- project.1-Priority Sync -----------------------------*/
	// list_push_back (&cond->waiters, &waiter.elem);
	list_insert_ordered(&cond->waiters, &waiter.elem, &cmp_sem_priority, NULL);
	/*-------------------------- project.1-Priority Sync -----------------------------*/


	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

 

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))
	{
    	/*-------------------------- project.1-Priority Sync -----------------------------*/
		list_sort(&cond->waiters, &cmp_sem_priority, NULL);
        /*-------------------------- project.1-Priority Sync -----------------------------*/
		sema_up (&list_entry (list_pop_front (&cond->waiters), struct semaphore_elem, elem)->semaphore);
	}
}

 

이로서 완성되었다.