Project1. Alarm clock

alarm : 호출한 프로세스를 정확한 시간 후에 다시 시작하는 커널 내부 함수

핀토스에서는 알람 기능이 busy waiting을 이용하여 구현 → sleep / wake up 다시 구현

busy waiting : thread가 CPU를 점유하면서 대기하고 있는 상태, CPU자원이 낭비되고, 소모 전력이 불필요하게 낭비될 수 있다.

 

💡 컨셉!

깨어날 시간이 아니면 양보, 애초에 양보할 일을 안만들면 되지 않을까? → 별도의 리스트를 마련해서 CPU가 잠자고 있는 애들 모아놓기!

 

✅ 수정해야 할 주요 파일 :

include/threads/thread.h, threads/thread.c, devices/timer.c

 

✅ 수정 및 추가해야할 함수

void timer_sleep (int64_t ticks) /* 인자로 주어진 ticks 동안 스레드를 block */
void thread_sleep (int64_t ticks) /* Thread를 blocked 상태로 만들고 sleep queue에 삽입하여 대기 */
void threae_awake (int64_t ticks) /* Sleep queue에서 깨워야 할 thread를 찾아서 wake */

• Ready_list : CPU를 기다리는 쓰레드들의 배열
  • 새로운 쓰레드는 리스트 맨뒤에 추가(list_push_back())
• timer_sleep()
  • 현재 busy waiting으로 구현되어 있음
  • thread_yiedld()를 통해 CPU를 양도
  • 주어진 tick 경과 후 Ready_list에 삽입된다.
• 전달된 tick의 만큼 loop 기반 waiting

void timer_sleep (int64_t ticks) { //ticks : 자고싶어하는 duration 
	int64_t start = timer_ticks ();
	ASSERT (intr_get_level () == INTR_ON);
	while (timer_elapsed (start) < ticks) // <- busy waiting 유발 깨워야할 시간이 안되었으면 계속 양보를 하고 
	thread_yield (); //자기가 점유하고 있던 CPU에 대한 권한을 양보 하는 과정 
	thread_sleep(start + ticks);
}

• • thread_yield() : CPU를 양보하고, thread를 ready_list에 삽입
  • timer_ticks() : 현재 진행되고 있는 tick의 값을 반환
  • timer_elased() : 인자로 전달된 tick이후 몇 tick이 지났는지 반환
• CPU를 양보하고, thread를 ready_list에 삽입

void thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

• thread_current() : 현재 실행 되고 있는 thread를 반환
• intr_set_level(old_level) : 인자로 전달된 인터럽트 상태로 인터럽트를 설정하고 이전 인터럽트 상태를 반환
• do_schedule() : 컨텍스트 스위치 작업을 수행
• list_push_back(&ready_list, &cur→elem) : 주어진 entry를 list의 마지막에 삽입
• intr_disable() : 인터럽트를 비활성하고 이전 인터럽트의 상태를 반환

 

 😎 Alarm clock 솔루션!

• Sleep/wake up기반의 alarm clock 구현
• Sleep queue의 도입
  • Sleep된 thread를 저장하는 자료구조
  • timer_sleep()을 호출한 thread를 저장

• 수정
  • loop 기반 wait() → sleep/wakeup으로 변경
  • timer_sleep()호출시 thread를 ready_list에서 제거, sleep queue에 추가
  • wake up 수행
    • timer interrupt가 발생시 tick 체크
    • 시간이 다 된 thread는 sleep queue에서 삭제하고, ready_list에 추가

😎  Alarm clock 구현

• 쓰레드 디스크립터 필드 추가
  • 해당 쓰레드가 깨어나야할 tick을 저장할 필드(wakeup)

  /* /include/threads/thread.h */
  
  struct thread {
  	/* Owned by thread.c. */
  	tid_t tid;                          /* Thread identifier. */
  	enum thread_status status;          /* Thread state. */
  	char name[16];                      /* Name (for debugging purposes). */
  	int priority;                       /* Priority. */
  
  	/* Shared between thread.c and synch.c. */
  	struct list_elem elem;              /* List element. */
      
      /* PROJECT1: THREADS - Alarm Clock */
  	int64_t	wakeup;						/* time to wake up */
  

• 전역변수 추가
  • Sleep queue 자료구조 추가
    • BLOCKED된 스레드들을 담기위한 sleep_list를 만들고 thread_init()함수에 추가한다.

    /* /threads/thread.c */
    
    /* PROJECT1: THREADS - Alarm Clock */
    static struct list sleep_list;
    
    void thread_init (void) {
    	ASSERT (intr_get_level () == INTR_OFF);
    
    	/* Reload the temporal gdt for the kernel
    	 * This gdt does not include the user context.
    	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
    	struct desc_ptr gdt_ds = {
    		.size = sizeof (gdt) - 1,
    		.address = (uint64_t) gdt
    	};
    	lgdt (&gdt_ds);
    
    	/* Init the globla thread context */
    	lock_init (&tid_lock);
    	list_init (&ready_list);
    	list_init (&destruction_req);
    
    	/* PROJECT1: THREADS - Alarm Clock */
    	list_init (&sleep_list);
    
    	/* Set up a thread structure for the running thread. */
    	initial_thread = running_thread ();
    	init_thread (initial_thread, "main", PRI_DEFAULT);
    	initial_thread->status = THREAD_RUNNING;
    	initial_thread->tid = allocate_tid ();
    }
    

• 구현할 함수 선언

pintos/src/threads/thread.h

void thread_sleep (int64_t ticks); /* 실행 중인 스레드를 슬립으로 만듬 */
void thread_awake (int64_t ticks); /* 슬립큐에서 깨워야할 스레들를 깨움 */

• thread_init() 함수 수정
  • main() 함수에서 호출되는 쓰레드 관련 초기화 함수
  • Sleep queue 자료구조 초기화 코드 추가
• timer_sleep()함수 수정
  • 기존의 busy waiting을 유발하는 코드 삭제
  • Sleep queue를 이용하도록 함수 수정
    • 구현하게 될 함수인 thread_sleep()함수 사용

  /* /devices/timer.c */
  
  /* PROJECT1: THREADS - Alarm Clock */
  void timer_sleep (int64_t ticks) {
  	int64_t start = timer_ticks ();
  
  	ASSERT (intr_get_level () == INTR_ON);
  	
  	thread_sleep(start + ticks);
  }
  

• thread_sleep() 함수 구현
  • thread를 sleep queue에 삽입하고 blocked 상태로 만들어 대기
  • 해당 과정중에는 인터럽트를 받아들이지 않는다.
  • devices/timer.c : timer_sleep() 함수에 의해 호출

  /* /threads/thread.c */
  
  /* PROJECT1: THREADS - Alarm Clock */
  /* Make the running thread sleep. */
  void thread_sleep(int64_t ticks) {
  	struct thread *cur;
  	enum intr_level old_level;
  
  	old_level = intr_disable(); 				/* turn off interupt */
  	cur = thread_current();
  	
  	ASSERT(cur != idle_thread);
  
  	cur -> wakeup = ticks;						/* set time to wake up */
  	list_push_back(&sleep_list, &cur->elem);	/* push to sleep_list */
  	thread_block();								/* make thread blocked */
  
  	intr_set_level(old_level);					/* turn on interupt */
  }
  

• timer_interrupt() 함수 수정
  • 매 tick마다 timer 인터럽트 시 호출되는 함수
  • sleep queue에서 깨어날 thread가 있는지 확인
    • sleep queue에서 가장 빨리 깨어날 쓰레드의 tick값 확인
    • 있다면, sleep queue를 순회하며 쓰레드 깨움
      • 구현하게 될 함수인 thread_awake()함수 사용

    /* devices/timer.c */
    
    /* Timer interrupt handler. */
    static void timer_interrupt (struct intr_frame *args UNUSED) {
    	ticks++;
    	thread_tick ();
    	thread_awake(ticks); /* PROJECT1: THREADS - Alarm Clock */
    }
    

• thread_awake() 함수 구현
  • wakeup_tick 값이 인자로 받은 ticks 보다 크거나 같은 스레드를 깨움
  • 현재 대기중인 스레드들의 wakeup_tick 변수 중 가장 작은 값을 next_tick_to_awake 전역변수에 저장

  /* /threads/thread.c */
  
  /* PROJECT1: THREADS - Alarm Clock */
  /* Makes the sleeping thread wake up. */
  void thread_awake(int64_t ticks) {
  	struct list_elem *e = list_begin(&sleep_list);
  	while (e != list_end (&sleep_list)) {
  		struct thread *t = list_entry(e, struct thread, elem);
  		if (t -> wakeup <= ticks) {
  			e = list_remove(e);
  			thread_unblock(t);
  		}
  		else 
  			e = list_next(e);
  	}
  }
  

🔑  터미널 입력!

아래와 같이 Thread: 550 idle ticks로 변했다면 그만큼 CPU가 놀았다는것! 성공!

 

 

🤫  참고 자료 : 

한양대 Pintos PPT자료, https://always-be-wise.tistory.com/151