[Pintos] Project 1 - Alarm-Clock

문제 상황:

• Alarm clock은 호출한 프로세스를 정해진 시간 이후에 다시 시작하도록 하는 함수이다.
• 하지만 Pintos에서는 해당 기능이 Busy Waiting 방식으로 구현되어 있다.

void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

• timer.c의 timer_sleep이라는 함수를 통해 tick동안 시간이 경과되지 않은 스레드는 CPU를 점유할 수 없도록 구현되어 있다.
• 하지만 현재시간을 확인하고 충분한 시간이 경과할 때 까지 계속해서 thread_yield()를 호출하는 루프에서 회전한다.
• 이로 인해 스레드가 CPU를 점유하면서 대기하게 되는 상태가 반복되면서 CPU 자원이 낭비 되고, 소모 전력이 불필요하게 낭비될 수 있다. - Busy Waiting

## 개선 사항:

🔖 Pintos의 thread의 cycle은 다음과 같이 이루어져있다. 각 스레드는 정해진 시간 동안 sleep 이후 running 상태가 되어 CPU를 점유할 수 있다.
하지만 ready_list에서 아직 running 할 수 있는 상태가 될 수 없더라도 스케쥴러에 의해 선택된다. 그리고 timer_sleep 함수로 인해 다시 ready_list로 보내진다 - **thread_yield

scedule에 의해 running상태로 cpu를 점유함 → 그런데 아직 sleep할 tick이 남아있음 → 다시 대기 상태로 되돌아감.

이러한 문제를 해결하기 위해 timer_sleep의 디자인을 다음과 같이 개선하였다.

🔖 처음 스레드가 생성되면서 ready_list안에 들어가게 되고 sceduling하면서 ready_list의 가장 앞에 있는 스레드와 running 스레드를 switching하게 된다.
하지만 이 경우 아직 sleep을 해야할 경우 해당 스레드를 block상태로 변동시켜서 별도에 리스트에 이동시킨다.
이후 해당 스레드가 sleep해야할 tick만큼 경과 되었을 때에 스레드를 unblock시켜 ready_list에 삽입한다.

thread_create() - thread.c

 tid_t thread_create(const char *name, int priority,
 					thread_func *function, void *aux)
 {
 	struct thread *t;
 	struct thread *curr;
 	tid_t tid;
 
 	ASSERT(function != NULL);
 
 	/* Allocate thread. */
 	t = palloc_get_page(PAL_ZERO);
 	if (t == NULL)
 		return TID_ERROR;
 
 	/* Initialize thread. */
 	init_thread(t, name, priority);
 	tid = t->tid = allocate_tid();
 
 	/* Call the kernel_thread if it scheduled.
 	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
 	t->tf.rip = (uintptr_t)kernel_thread;
 	t->tf.R.rdi = (uint64_t)function;
 	t->tf.R.rsi = (uint64_t)aux;
 	t->tf.ds = SEL_KDSEG;
 	t->tf.es = SEL_KDSEG;
 	t->tf.ss = SEL_KDSEG;
 	t->tf.cs = SEL_KCSEG;
 	t->tf.eflags = FLAG_IF;
 
 	/* Add to run queue. */
 	// thread_unblock(t);
 	curr = thread_current();
 	thread_unblock(t);
 	if (t->priority > curr->priority)
 		thread_yield();
         
 	return tid;
 }

schedule() - thread.c

  static void
  schedule(void)
  {
  	struct thread *curr = running_thread();
  	struct thread *next = next_thread_to_run();
  
  	ASSERT(intr_get_level() == INTR_OFF);
  	ASSERT(curr->status != THREAD_RUNNING);
  	ASSERT(is_thread(next));
  	/* Mark us as running. */
  	next->status = THREAD_RUNNING;
  
  	/* Start new time slice. */
  	thread_ticks = 0;
  
  #ifdef USERPROG
  	/* Activate the new address space. */
  	process_activate(next);
  #endif
  
  	if (curr != next)
  	{
  		/* If the thread we switched from is dying, destroy its struct
  		   thread. This must happen late so that thread_exit() doesn't
  		   pull out the rug under itself.
  		   We just queuing the page free reqeust here because the page is
  		   currently used bye the stack.
  		   The real destruction logic will be called at the beginning of the
  		   schedule(). */
  		if (curr && curr->status == THREAD_DYING && curr != initial_thread)
  		{
  			ASSERT(curr != next);
  			list_push_back(&destruction_req, &curr->elem);
  		}
  
  		/* Before switching the thread, we first save the information
  		 * of current running. */
  		thread_launch(next);
  	}
  }

🔖 sleep - wake 방식은 다음과 같다. timer_sleep에서 더 자야할 스레드들은 block시켜서 list안에 넣어두었고, 일어날 스레드는 ready_list로 들어가는 방식이다.
이를 통해 busy-waiting의 문제를 해결하였다.