[OS] Pintos - BusyWaiting 해제

Pintos를 처음 설치하게 되면 현재 스레드가 devices/timer.c의 timer_sleep() 함수를 호출하면 지정 Tick동안 While문이 계속해서 thread_yield()를 호출하면서 CPU를 점유하지 않는 모습을 보여준다.

/pintos/src/device/timer.c

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

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

이정도의 소스는 다들 이해 할수 있다고 생각하기때문에 더욱 자세한 설명은 생략하도록 하겠다.

현재 스레드가 CPU를 점유 하지 않기 위해서 CPU를 점유해야하는 모순된 모습을 보여준다.

이런 문제를 "Busy Waiting" 이라고 부르는데 Busy Waiting에 관한 정보는 https://blog.system32.kr/80 여기를 참고하도록 하자.

Busy Waiting 정의

이번주 과제는 디렉토리중 /device/timer.c 에 대한 구조를 알아오는 것이다.

수정 ) Busy Waiting 의 정의, 구현 방식, 해결 방법을 알아오는 것이다.

결국 Busy Waiting 을 제거하는 것이다. Busy Waiting 을 제거하기 위해서는 다양한 구현 방법이 존재한다고 알려져 있다. (Pintos Menual 참조)

필자가 생각을 잘못했다. /device/timer.c 소스를 다시 봐보자.

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

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

현재 start 에는 현재 시간을 입력하도록 되어있다. timer_elapsed() 함수를 통해서 start 부터 Ticks 까지 지금까지 지난 시간을 표시 하기 위한 함수이다.

결론은 받아온 ticks 변수의 값 만큼 시간이 지날때 까지 thread_yield()를 해야한다.

그럼 thread_yield() 함수는 무엇일까? -> 나중에 알아보도록 하자.

 

그럼 이제 Busy Waiting 에서 Sleep 되어 있는 시간 동안 반족적으로 thread_yield() 함수를 호출하는 걸로 알게 되었다.

그럼 thread_yiled()를 호출하게 되면 동작하지 않도록 재우게 되는 것이다. 비효율적이다.

 

그래서 alarm 기능을 만들고 시간이 되면 wake_up을 통해서 잠자고 있는 thread를 깨우도록 해야한다.

thread를 깨우기 위해서는 자고 있는 thread들의 대기 목록을 가지고 있어야 한다.

static struct list waiting_list;

위 구문을 /pintos/src/device/timer.c 에 추가하도록 하자. 어디에 추가 해햐 하는지는 당연히 알고 있을거라 생각한다.

timer_init (void) 
{
  pit_configure_channel (0, 2, TIMER_FREQ);
  intr_register_ext (0x20, timer_interrupt, "8254 Timer");
  list_init(&waiting_list)
}

항상 waiting_list를 초기화 해야 하기 때문에 timer_init 부분을 위와 같이 수정해 준다.

이제 리스트의 내용을 작성해야 하는데 먼저 sleep-wake의 구조를 잘 잡아야 한다.

Call Sleep -> Sleep(Save Information & Sleep Threads) -> timer interrupt() -> sleep time manage alarm time check -> if reach alarm time then wake

sleep을 호출하고, sleep 를 처리해야 한다. 그다음으로 timer interrupt()를 시키고, sleep time을 관리하여 알람시간을 체크 후 도달 하면 깨우는 동작 방식을 가져야 한다.

그리고 sleep에 들어온 Thread는 당연히 Block 상태가 되어야 한다. (+ Sleep Time 을 기억하고 있어야 한다.)

필수적으로 필요한 정보는 다음과 같다. Blocked Thread Information , Each Thread Sleep Time 이 필요하다.

 

구현단계 )

몇가지 방법으로 구현해보려고 한다. 2020.01.21 포스팅에서는 하나만 다루고, 계속해서 추가할 예정이다.

• All Time Save to Array
• Save to List (Sorted Time)
• Save The First Wake-up Thread of time(will) and Wake-up Specific Thread

먼저 필자는 time순으로 thread를 sorting 해서 넣을거며, 가장 일찍 깨어날 time을 저장후, time비교, time에 도달하면 wake_up을 실시할것이다.

참고 )

[ https://m.blog.naver.com/PostView.nhn?blogId=kangjin13&logNo=220138495555&proxyReferer=https%3A%2F%2Fwww.google.com%2F ]

이러한 방법을 쓰는 이유는 timer_interrupt안에서 너무 많은 동작이 일어나면 안되기 때문

sleep에서 sorting과정을 거치지 않으면 sorting또는 검색이 필요하기에  

검색만큼의 overhead가 timer_interrupt에 부과되고 이로 인해 실행에 문제가 발생할 수 있게 된다.

 

/pintos/src/threads/thread.h 에 변수를 추가해줘야한다.

/pintos/src/threads/thread.h

#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint32_t *pagedir;                  /* Page directory. */
#endif
    int32_t alarm_time;

마지막에 int32_t alarm_time 변수를 추가해 줘야한다. timer_sleep()에 구현해야한다.

/pintos/src/device/timer.c

위와 같이 소스를 변경해준다.

    bool
    min_time(struct list_elem *elem, struct list_elem *e, void *aux)
    {
        struct thread *cur = list_entry(elem, struct thread, elem);
        struct thread *list = list_entry(e, struct thread, elem);
        if(cur->alarm_time <= list->alarm_time)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

뭔가 잘못됐다. 추후 수정하겠다.