[Pintos Project] Alarm Clock and Priority Scheduling

Alarm Clock - Timer Interrupt

 

Alarm

Alarm은 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수이다. Pintos에서는 알람 기능이 Busy waiting 방식으로 구현되어 있다. 해당 알람 기능을 sleep/wake up 방식으로 수정하여 다시 구현한다.

 

 

Alarm Clock 기능을 구현할 때, ticks에 대한 이해가 미흡했기 때문에 어려움을 겪었었다. 아래 코드는 next_tick_to_awake가 제대로 갱신되지 않고, thread_awake의 argument가 잘못된 경우이다.

 

/* 최소 틱을 가진 스레드 저장 */
void update_next_tick_to_awake(int64_t ticks)
{
	// 만약 ticks가 next_tick_to_awake보다 작으면 해당 변수 update
	if (ticks < next_tick_to_awake)
	{
		next_tick_to_awake = ticks;
	}
}

void thread_awake(int64_t ticks)
{
	struct list_elem *e = list_begin(&sleep_list);

	while (e != list_tail(&sleep_list))
	{
		struct thread *f = list_entry(e, struct thread, elem);

		if (ticks >= f->wakeup_tick)
		{
			e = list_remove(&f->elem);
			thread_unblock(f);
		}
		else
		{
			update_next_tick_to_awake(f->wakeup_tick);
			e = e->next;
		}
	}
}

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	int64_t temp = get_next_tick_to_awake();
	if(ticks>=temp)
	{
		thread_awake(temp);

	}
}

 

현재 next_tick_to_awake는 갱신이 이루어지지 않으므로, 처음으로 thread_awake 함수가 호출되면서 깨운 스레드의 wakeup_tick이 저장되어 있다. tick은 timer_interrupt에 의해 계속해서 증가하므로, thread_awake 함수 안에서 update_next_tick_to_awake함수가 호출된다 하더라도 이 값은 영원히 갱신되지 않는다. 따라서 이후 timer_interrupt 함수가 호출되어도 깨울 수 있는 스레드는 존재하지 않게 된다.

 

 

처음에는 next_tick_to_awake가 제대로 갱신된다고 생각했고, ticks가 temp보다 큰 경우를 고려하지 않았다고 생각하여 timer_interrupt 함수 내 thread_awake 함수의 argument를 ticks로 바꾸어 해당 문제를 해결했다고 생각했다. 그러나 이는 next_tick_to_awake가 갱신되지 않으므로 매 틱마다 thread_awake 함수를 호출하기 때문에 busy waiting 방식과 다를 것이 없었다.

 

 

next_tick_to_awake가 한 번 갱신

 

thread_sleep 의 경우 update_next_tick_to_awake함수가 제대로 동작하여 next_tick_to_awake가 제대로 갱신되었지만 문제는 thread_awake였다. 이미 깨운 스레드의 최소 wakeup_tick이 저장되어 있으므로, 나머지 스레드들을 순회하며 update_next_tick 함수를 실행하여도 갱신될 수 없었기 때문이다. 따라서 thread_awake 함수가 호출될 때마다 next_tick_to_awake를 초기화하였다. 또한, timer_interrupt 내 thread_awake 함수의 실행 조건과 argument를 수정하였다.

 

void thread_awake(int64_t ticks)
{
	struct list_elem *e = list_begin(&sleep_list);
	next_tick_to_awake = INT64_MAX;

	while (e != list_tail(&sleep_list))
	{
		struct thread *f = list_entry(e, struct thread, elem);

		if (ticks >= f->wakeup_tick)
		{
			e = list_remove(&f->elem);
			// ASSERT (is_interior(e));
			thread_unblock(f);
		}
		else
		{
			update_next_tick_to_awake(f->wakeup_tick);
			e = e->next;
		}
	}
}

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	int64_t temp = get_next_tick_to_awake();
	if(ticks==temp)
	{
		thread_awake(ticks);

	}
}

next_tick_to_awake가 계속해서 갱신

 

Timer Interrupt

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();

	int64_t temp = get_next_tick_to_awake();
	if(ticks==temp)
	{
		thread_awake(ticks);

	}
}

 

CPU에 내장된 타이머가 자동으로 해당 인터럽트를 일으켜준다. ticks는 OS가 부팅된 이후로 흐른 시간으로 볼 수 있다. Pintos Project에서 1tick은 10ms를 의미한다.

 

 

timer_interrupt는 인터럽트 핸들러로써 매 틱(tick) 실행된다. 따라서 ticks는 timer_interrupt가 실행된 횟수로도 볼 수 있다. 매 틱 마다 해당 함수가 실행되므로 다음에 깨워야 할 스레드의 wakeup_tick을 매 틱마다 확인할 수 있다. 따라서 thread_awake 함수의 실행 조건을 ticks가 temp와 같을 때로 명시할 수 있다.

 

 

Priority Scheduling

 

라운드 로빈으로 구현되어 있는 Pintos의 scheduler를 우선순위를 고려하여 scheduling할 수 있도록 수정한다. 현재 실행 중인 스레드보다 priority가 높은 스레드가 ready list에 추가되면 현재 스레드는 즉시 프로세서를 새 스레드에게 양보해야 한다. 마찬가지로 스레드가 lock, semaphore, condition variable을 기다리고 있을 때, priority가 가장 높은 대기 스레드가 먼저 깨어나야 한다.

 

 

스레드가 공유자원에 접근할 때 실행 순서와 자원의 일관성을 보장해야 하기에 반드시 동기화(Synchronization)되어야 한다. 아래는 lock과 semaphore, condition variable을 이용하여 동기화를 구현하고 Pintos의 test_priority_condvar에 따른 실행 과정을 나타낸 것이다.

 

 

test function의 실행 결과

Test function은 각각의 스레드들을 시작하고 시그널을 통해 하나씩 깨우는 순서로 진행한다.

 

void
test_priority_condvar (void) 
{
  int i;
  
  /* This test does not work with the MLFQS. */
  ASSERT (!thread_mlfqs);

  lock_init (&lock);
  cond_init (&condition);

  thread_set_priority (PRI_MIN);
  for (i = 0; i < 10; i++) 
    {
      int priority = PRI_DEFAULT - (i + 7) % 10 - 1;
      char name[16];
      snprintf (name, sizeof name, "priority %d", priority);
      thread_create (name, priority, priority_condvar_thread, NULL);
    }

  for (i = 0; i < 10; i++) 
    {
      lock_acquire (&lock);
      msg ("Signaling...");
      cond_signal (&condition, &lock);
      lock_release (&lock);
    }
}

static void
priority_condvar_thread (void *aux UNUSED) 
{
  msg ("Thread %s starting.", thread_name ());
  lock_acquire (&lock);
  cond_wait (&condition, &lock);
  msg ("Thread %s woke up.", thread_name ());
  lock_release (&lock);
}

Thread 1이 lock을 획득하고 연산을 수행하다가 선행 조건이 성립되지 않아, condition waiters list에 우선순위 순으로 들어가게 된다.

 

 

이 때 waiter라는 semaphore elem을 생성하고 해당 구조체 안의 semaphore waiters list에 thread 1의 elem이 들어가면서 자신의 상태를 Block으로 전환한다. 편의 상 하나의 waiter를 그렸으나 다수의 waiter가 cond waiter에 삽입될 수 있다.

 

 

이후 소유하고 있던 lock을 반환하고 조건을 만족시켜줄 thread 2가 lock을 획득하게 된다. Thread 2가 Thread 1에게 signal을 보내준다고 가정한다. 

 

 

Signaling…이라는 메시지와 함께 thread2는 cond_signal 함수를 호출해 condition waiters list에서 가장 우선순위가 높은 waiter.elem을 빼내면서 이에 대응되는 semaphore를 인수로 sema_up 함수를 호출한다. 따라서 Thread 1은 unblock 상태가 되고 Value가 1이 되므로 while loop를 나와 다시 value를 0으로 낮추며 sema_down 함수가 종료된다. 이후 thread_yield를 통해 ready list에 삽입된다.

 

 

최종적으로 Thread 2는 lock을 반환하고 thread 1이 cond_wait 함수를 리턴하면서 lock을 재획득하게 된다.