[PintOS project] 1. Part 1: Threds - Alarm Clock

@developer/takealittle.time·2024년 11월 6일

KAIST PintOS Project

목록 보기

2/9

00. 들어가며

PintOS 프로젝트를 처음 받고 든 느낌은, 나는 이러했다.
무언가 거대한. 그 마저도 C언어로 작성된 프로젝트를 받았는데,
마치 어떤 거대한 무인도에 갑자기 툭 떨어진 기분이 들었다.
'나 뭐 해야되는거지?' 라는 생각이 들었다는 말이다.
앞으로의 PintOS 프로젝트를 헤쳐감에 있어, 어떠한 순서로 주차별 과제에 접근할 것인지 본인만의 루틴을 만드는 일도 중요할 것 같다.
나는 아래와 같이 나만의 문제 해결 순서를 잡았다.

KAIST에서 제공하는 강의와 강의 자료에 해당 과제에 대한 각 도전 과제에 대해 기술되어 있다.
https://oslab.kaist.ac.kr/pintosslides/

위 자료를 참고해서, 내가 당장 어떤 코드를 건드려야 하는지에 대해 확인한다.

해당 코드를 뜯어본다. (내가 작성한 코드가 아니라서 현재 구조가 잘 보이지 않으므로)
ex) timer.c와 thread.c를 수정해야 한다고 하면, 해당 코드들에 어떠한 변수들과 함수들이 있고, 이 변수들은 어떻게 생겼으며, 이 함수들은 각각 어떤 역할을 하는지에 대해서 이해하는 것이다.

코드를 어느 정도 뜯어보고 나면, 머릿속에 들어있는 CS 지식과 연결되면서 어느 정도 가닥이 잡히기 시작한다.

위의 자료를 다시 확인한다. 이제 구현해야 할 내용들에 대해 명세되어 있는 부분들을 확인하고 이해한다.

해당 내용들을 차근차근 구현한다.

수정해야 할 코드들을 뜯어보자!

00-1. timer.c

8254 타이머: 실제 Hardware. Intel 8254 Programmable Interval Timer

타이밍 기능: 세 개의 16-bit 카운터 → 각각 다른 mode 설정 가능 → tick 기반 시간 관리.

스케줄링: 운영체제 스케줄러 → 정해진 시간(Time Slice) 마다 인터럽트 발생 → 스케줄링

TIMER_FREQ: 타이머의 동작 주기 설정값. 초당 system tick의 빈도.
ex) TIMER_FREQ이 100 → 초당 100번의 system tick. (1초는 1000ms) → system tick의 주기는 10ms. → 이를 기준으로 interrupt를 주고 스레드를 종료한다면 → 10ms 마다 스레드 종료.
timer_init(): ① 8254 타이머 칩의 주기 설정.
② timer interrupt 핸들러 등록 → 주기적으로 timer interrupt 발생.
timer_calibrate(): 시스템 성능에 따라 loops_per_tick (1tick 동안 실행할 수 있는 loop 횟수) 값 보정.
busy_wait(): loops 변수 감소시키면서 0보다 클 때까지 루프 반복
(주어진 loops 수 만큼 빈 루프 돌면서 대기)
too_many_loops(): 운영체제 부팅 후 경과된 타이머 틱의 수 반환.
timer_sleep(): ticks 수를 인자로 받아, 해당 값 만큼 tick이 경과할 때까지 스레드를 대기 상태로 만듦.
real_time_sleep(): num,denom을 인자로 전달 받아 num/denom 초 만큼 대기

00-2. thread.c

struct thread { // 스레드 구조체
	tid_t tid; // 스레드 ID
    enum thread_status status; // 스레드 상태
    char name[16]; // 스레드 이름
    int priority; // 스레드 우선 순위 (나중에 실행 순서 결정) 
    struct list_elem elem; // 스레드를 하나의 연결 리스트로 연결
    struct intr_frame tf; // 스위칭 시 필요한 정보 저장
    unsigned magic; // 스택 끝에 있는 값 확인하는 매직 넘버 (stack overflow 확인)
}

thread_init(): 스레드 이용을 위한 총체적인 시스템의 초기화 (마치 부팅하듯)
인터럽트 비활성 상태를 확인하고, 커널 GDT 재로드. 스레드 id 할당. ready_list 초기화. destruction_req 초기화.
thread_start(): idle 쓰레드 생성. 인터럽트 활성화. (intr_enable();) → 총체적인 스레드 시스템의 시작
thread_tick(): 매 타이머 tick 마다 실행 → 현재 스레드의 실행 통계 업데이트.
thread_create(): 인자들(스레드 이름, 우선순위, 실행 함수, 실행 함수에 전달 할 인자) 입력 받아 스레드 생성. → run queue에 삽입
thread_block(): 현재 스레드 BLOCKED 상태로 변경하고 schedule() 호출 해 준비 큐의 다른 스레드 실행
thread_unblock(): block 된 스레드를 READY 상태로 변경. → ready_list에 추가.
thread_yield(): 현재 스레드가 CPU를 양보하도록 (현재 스레드가 idle이 아닐 경우, 준비 목록에 추가) → 다른 스레드가 실행될 수 있도록 한다.

* Thread의 상태 종류

Running: 실행 중. CPU에서 실행 중인 상태

Ready: CPU 사용 가능. but. CPU에 아직 할당 되지는 않은 상태. (다른 스레드가 사용 중)

BLOCKED: 특정 event를 기다리고 있는 상태 (ex. I/O 작업 신호 등)

IDLE: system이 아무 스레드도 실행하지 않고 있는 상태. (=ready_list에 아무것도 없는 상태.)

01. Alarm Clock

Main Goal

현재 제공 받은 코드에서 pintOS는 busy-waiting 방식으로 스레드를 관리하고 있다.
→ 이를 sleep-awake 방식으로 수정한다.

01-1. 제공 받은 busy-waiting의 문제점

현재 실행(running) 중인 thread가 CPU 동작만 수행하는 것이 아니라, I/O 동작을 수행한다고 해보자.
ex) Disk에 특정 파일을 꺼내러 간 경우 → Disk에서 (bus를 타고) 파일을 찾으러 가는 시간, (disk에서 특정 파일을) 찾는 동안 시간이 걸린다. → 문제는 이 녀석이 이렇게 CPU를 쓰고 있지 않는 동안에도 안 비키고 while문을 돌면서 기다린다는 것이다! (이것이 busy-waiting 방식이다.)

01-2. sleep-awake 방식으로의 수정

따라서, 우리는 위와 같이 sleep-awake 방식으로 스케줄러를 구현한다.
sleep-awake 방식이란 다음과 같다.
- running 중이던 스레드가 잠시 동안 CPU를 쓸 필요가 없을 때 (ex. I/O 동작 수행 등으로 인해서) 이 스레드를 sleep_list로 옮긴다.
  졸고 있는 놈들을 수면실로 옮긴다.
- sleep_list 안으로 옮긴 스레드들을 BLOCKED 상태로 전환한다. (sleep)
  수면실로 옮긴 놈들을 재운다. (sleep)
- 이 스레드들은 각각 정해진 tick이 지나면 다시 READY 상태로 전환 되어, ready_list로 들어간다. (awake)
  수면실에 재운 놈들을 시간이 다 되면 깨운다. (awake)
이렇게 구현하면, running 도중 잠깐 CPU를 사용하지 않는 스레드를 sleep_list로 치워놓고 ready_list에서 뒤에 대기하고 있던 스레드를 이 시간 동안 처리할 수 있다.

tip.

마치, 위 그림에서 running thread의 자리를 1개의 은행 창구라고 생각하고, CPU를 1명의 은행원이라 생각해보자. ready_list에는 각자의 용무를 가진 손님들(thread)이 줄을 서서 대기하고 있다고 생각하자.

지금은 손님A (threadA)의 용무를 처리하고 있는 상황이다.

제공 받은 코드의 busy-waiting 방식에서는 은행 창구에서 은행원(CPU)이 '이 용무는 잠깐 시간이 필요하니 대기 해 주세요~.' 라고 했을 때, 손님A가 내내 은행 창구에서 대기하는 꼴이다.

이렇게 되면 뒤에 있는 손님들(ready_list 속 thread)은 그저 대기해야 한다.

우리가 수정한 sleep_awake 방식에서는 위와 같은 상황일 때, 은행원이 다음과 같이 말한다. '이 용무는 잠깐 시간이 필요하니, 오른쪽 대기석에서 10분 대기하신 뒤에 다시 번호표를 뽑아 주세요~'

이렇게 하면, 뒤에 있는 손님들(ready_list 속 thread) 중 다음 순번분의 용무를 먼저 처리할 수 있을 것이다.

01-3. 구현

thread.c에 sleep-list를 작성한다.
(list 구조체가 이미 있기 때문에, 어렵지 않다.)

// THREAD_BLOCK 상태의 스레드를 할당할 리스트
struct list sleep_list;

thread.h에 가면 thread 구조체가 작성되어 있는데, 여기에 wake_tick (잠 든 스레드를 깨울 시간)을 추가한다.

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. */

   //******... 중략 ...******//

	/* Owned by thread.c. */
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;                     /* Detects stack overflow. */
	
	int64_t wake_tick; /* 스레드가 깨어날 시각*/
};

thread.c로 돌아가서, 위의 wake_tick과 sleep_list를 이용해 기능들을 구현한다.

thread_init()

void
thread_init (void) {
  ASSERT (intr_get_level () == INTR_OFF);

			/* .. 중략 ..*/
    
   /* Init the globla thread context */
   lock_init (&tid_lock);
   list_init (&ready_list);
   // sleep_list를 초기화 하는 함수 호출 추가
   list_init (&sleep_list);
   list_init (&destruction_req);

  /* 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 ();
  // wake_tick을 0으로 초기화 하는 코드 추가
  initial_thread->wake_tick = 0;
}

thread_sleep ()

// thread를 block 상태로 수정하고 sleep_list에 추가하는 함수
void
thread_sleep (int64_t wake_tick) {
  struct thread *curr = thread_current ();
  enum intr_level old_level;

  ASSERT (!intr_context ());

  old_level = intr_disable ();
  curr->wake_tick = wake_tick; // 스레드가 꺠어날 시각 저장
  // list_insert_ordered 함수를 통해 sleep_list의 정렬 상태를 유지하면서 삽입
  list_insert_ordered(&sleep_list, &curr->elem, thread_wake_tick_cmp, NULL);
  thread_block(); // 현재 스레드를 BLOCK 상태로 전환

  intr_set_level (old_level);
}

→ sleep_list에 thread를 추가할 때, wake_tick을 기준으로 오름차순 정렬의 순서를 지키며 삽입하도록 하였다.
이 때, list.h에 이미 list_insert_ordered() 라고 하는 함수가 존재하므로 이를 사용해주면 된다.
다음과 같이 wake_tick을 기준으로 대소 비교를 해주는 함수 하나를 작성해서 이에 전달해주면 된다.

thread_wake_tick_cmp()

  // sleep_list에 스레드 삽입 중 정렬 위해 wake_tick을 비교하는 함수
bool
thread_wake_tick_cmp(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
  struct thread *t_a = list_entry(a, struct thread, elem);
  struct thread *t_b = list_entry(b, struct thread, elem);
  return t_a->wake_tick < t_b->wake_tick;
}

thread_awake()

  // sleep_list에 있는 blocked 상태의 스레드를 unblock 하는 함수
void 
thread_awake(int64_t current_tick) {
  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->wake_tick <= current_tick) {
          e = list_remove(e);  // 요소를 제거하고 다음 요소로 이동
          thread_unblock(t);
      } else {
          e = list_next(e);  // 조건에 맞지 않으면 다음 요소로 이동
      }
  }
}

timer.c 로 들어가서, 다음과 같은 부분들을 추가/수정한다.

timer_interrupt()

  /* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
  ticks++;
  thread_tick ();
  // 매 timer_interrupt 마다 대기 중인 스레드 깨우기
  thread_awake(ticks);
}

timer_sleep()

  /* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
  int64_t start = timer_ticks ();
  int64_t wake_tick = start + ticks;

  ASSERT (intr_get_level () == INTR_ON);

  /*thread_sleep()을 호출*/
  thread_sleep(wake_tick);
}

01-4. 실행 결과

sleep-awake 방식을 사용하지 않았을 때는 0 idle ticks로 출력되던 것이 550 idle ticks로 바뀌었다!
→ 왜? idle ticks가 나올 수 있을까?
- 사실, 생각해보면 당연하다.
- 위처럼 running state와 ready_list만 존재할 때는 시스템이 시작할 때를 제외하고 ready_list가 비는 경우 (idle)가 발생할 수가 없다.
- 하지만, 위와 같이 sleep_list를 추가하면 어떠한 경우에 ready_list가 비는 경우가 생길 수 있게 되는 것이다.