pintOS - project1(Thread) thread.c

thread.c

< macro >

// advanced scheduling 용도
//17.14 형식의 고정소수점 표현 
#define P 17
#define Q 14
#define F (1 << (Q))

#define FIXED_POINT(x) (x) * (F)
#define REAL_NUMBER(x) (x) / (F)

#define ROUND_TO_INT(x) (x >= 0 ? ((x + F/2)/F) : ((x - F/2)/F))

//고정소수점 기본 연산
#define ADD_FIXED(x,y) (x) + (y)
#define SUB_FIXED(x,y) (x) - (y)
#define MUL_FIXED(x,y) ((int64_t)(x)) * (y) / (F)
#define DIV_FIXED(x,y) ((int64_t)(x)) * (F) / (y)

#define ADD_INT(x, n) (x) + (n) * (F)
#define SUB_INT(x, n) (x) - (n) * (F)
#define MUL_INT(x, n) (x) * (n)
#define DIV_INT(x, n) (x) / (n)

#define THREAD_MAGIC 0xcd6abf4b
#define THREAD_BASIC 0xd42df210

/* 스케줄링 */
#define TIME_SLICE 4            /* 스레드 실행 시간 지정 */

#define is_thread(t) ((t) != NULL && (t)->magic == THREAD_MAGIC)
#define running_thread() ((struct thread *) (pg_round_down (rrsp ())))

< thread_init >

// 시스템이 부팅될 때 한번 호출되는 전체 스레드 초기화
void
thread_init (void) {
	// 인터럽트가 켜져있으면 종료
	ASSERT (intr_get_level () == INTR_OFF);
	
	// 커널에 대한 임시 gdt를 다시 로드
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	// 전역 스레드 변수 초기화
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);
	list_init (&sleep_list);
	list_init (&all_list);
	load_avg = 0;
	
	// 실행중인 스레드의 구조를 설정
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();
}

< thread_start >

// 인터럽트를 활성화하여 스레드 스케줄링 시작
void
thread_start (void) {
	// 유휴 스레드를 생성하고 세마포어를 초기화
	struct semaphore idle_started;
	sema_init (&idle_started, 0);
	
	load_avg = 0; // 평균 부하를 0으로 초기화
	thread_create ("idle", PRI_MIN, idle, &idle_started); // 스레드 생성

	intr_enable (); // 인터럽트를 활성화해 선점형 스케줄링 가능
	sema_down (&idle_started); // 유휴 스레드를 매개변수로 세마포어 감소
}

< thread_tick >

// 각 스레드 틱 수
void
thread_tick (void) {
	struct thread *t = thread_current (); // 현재 스레드를 포인터 t에 저장

	// t가 유휴 스레드면 유휴 틱수 증가
	if (t == idle_thread)
		idle_ticks++;
        
// 이 부분은 아직 사용 x
#ifdef USERPROG
	else if (t->pml4 != NULL)
		user_ticks++;
#endif

	// t가 커널 스레드면 커널 틱수 증가
	else
		kernel_ticks++;

	// 선점 강제 실행
	// 현재 스레드 틱수가 타임슬라이스를 넘었다면 스레드 제어 교체
	if (++thread_ticks >= TIME_SLICE)
		intr_yield_on_return ();
}

< thread_create >

// 스레드 생성
tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	tid_t tid;
	
	// 인자로 받아온 함수가 없으면 종료
	ASSERT (function != NULL);

	// 스레드 할당
	t = palloc_get_page (PAL_ZERO);
	if (t == NULL)
		return TID_ERROR;

	// 스레드 초기화
	init_thread (t, name, priority);
	tid = t->tid = allocate_tid ();

	// 만약 mlfqs가 실행중이라면
	if (thread_mlfqs == true){
		// 스레드의 우선도를 PRI_MAX값으로 지정
		t->priority = calculate_advanced_priority(t);
		// 원래 우선도에 지정한 우선도를 저장
		t->original_priority = t->priority;
	}

	// 예약된 경우 커널 스레드를 호출(rdi, rsi)
	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;

	// 스레드를 다시 언블락
	thread_unblock (t);

	// 가져온 스레드의 우선도가 실행 중인 스레드보다 작으면 교체한다.
	if (thread_get_priority() < priority){
		thread_yield();		
	}

	// 스레드 id 반환
	return tid;
}

< thread_block >

// 스레드를 블락시키며, 언블락 때까지 다시 실행되지 않는다.
void
thread_block (void) {
	// 인터럽트가 처리중이면 종료
	ASSERT (!intr_context ());
	// 인터럽트가 켜져있으면 종료
	ASSERT (intr_get_level () == INTR_OFF);
	// 조건을 다 통과하고 현재 스레드를 블럭시킨다.
	thread_current ()->status = THREAD_BLOCKED;
	// 다음 스레드를 선택해 제어를 넘긴다.
	schedule ();
}

< thread_unblock >

// 블락해논 스레드를 언블락시킨다.
void
thread_unblock (struct thread *t) {
	enum intr_level old_level;
	
	ASSERT (is_thread (t)); // 스레드가 존재하지 않으면 종료
	old_level = intr_disable (); // old_level에 현재 상태를 저장하고 인터럽트를 비활성화
	ASSERT (t->status == THREAD_BLOCKED); // 스레드의 상태가 블락상태가 아니면 종료

	// ready_list에 스레드의 elem을 삽입
	list_insert_ordered(&ready_list, &t->elem, priority_scheduling, NULL);
	t->status = THREAD_READY;
	intr_set_level (old_level); // 인터럽트를 다시 원래상태로 되돌린다.
}

< thread_yield >

// 실행중인 스레드를 중단하고 다른 스레드에게 양보한다.
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){
		// ready_list에 현재 스레드의 elem을 넣는다.
		list_insert_ordered(&ready_list, &curr->elem, priority_scheduling, NULL);
	}
	
	do_schedule (THREAD_READY); // 스레드 상태를 준비중인 스레드로 변경
	intr_set_level (old_level); // 인터럽트 상태를 원래대로 되돌리기
}

< thread_set_priority >

// 스레드의 우선도를 new_priority로 설정
void
thread_set_priority (int new_priority) {
	// 현재 스레드의 우선도가 현재 스레드의 원래 우선도와 같으면
	// 즉, 아직 우선도를 올려받지 못했다면 새 우선도로 변경한다.
	if (thread_current()->priority == thread_current()->original_priority){
		thread_current ()->priority = new_priority;
	} 

	// mlfqs로 함수를 실행했다면 현재 스레드의 우선도를 새 우선도로 변경한다.
	if (thread_mlfqs == true){
		thread_current()->priority = new_priority;
	}
	
	/* 이 줄의 추가로 priority-sema가 pass한다. 왜why?*/
	/* 이 줄의 추가로 priority-fifo가 pass한다. 왜why?*/
	// 현재 스레드의 원래 우선도에 새 우선도를 추가한다. 왜 될까
	thread_current()->original_priority = new_priority;

	//새 priority가 더 낮은지 확인하고 Ready List에 더 높은 우선순위가 있다면 양보
	struct list_elem *max_elem = list_max(&ready_list, priority_scheduling, NULL);
	struct thread *next = list_entry(max_elem, struct thread, elem);
	if (thread_get_priority() < next->priority){
		thread_yield();	
	}
}

< thread_get_priority >

// 현재 스레드의 우선도를 가져온다.
int
thread_get_priority (void) {
	// 현재 스레드의 우선도를 반환한다.
	int current_priority = thread_current()->priority;
	return current_priority;
}

< idle >

// 실행 준비된 스레드가 없을 때 cpu가 대기 상태로 들어간다.
static void
idle (void *idle_started_ UNUSED) {
	struct semaphore *idle_started = idle_started_;

	idle_thread = thread_current ();
	// idle_started 세마포어 값을 증가
	sema_up (idle_started);
	
	// 무한루프로 인터럽트를 비활성화하고 스레드를 블락한다.
	for (;;) {
		intr_disable ();
		thread_block ();

		// sti : 인터럽트를 다시 활성화, hlt : cpu를 대기 상태로 전환
		asm volatile ("sti; hlt" : : : "memory");
	}
}

< init_thread >

// 개별 스레드 초기화
static void
init_thread (struct thread *t, const char *name, int priority) {
	// 스레드가 없으며, 우선도가 최소보다 작거나 최대보다 크고, 이름이 없으면 종료
	ASSERT (t != NULL);
	ASSERT (PRI_MIN <= priority && priority <= PRI_MAX);
	ASSERT (name != NULL);
	
	memset (t, 0, sizeof *t);	// 스레드의 메모리를 0으로 초기화
	t->status = THREAD_BLOCKED; // 스레드 상태를 블락으로 변경
	strlcpy (t->name, name, sizeof t->name); // name을 복사
	// 스레드의 각 부분을 지정
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = priority;
	t->original_priority = priority;
	t->magic = THREAD_MAGIC;
	t->has_lock = 0;
	t->wait_on_lock = NULL;
	list_init(&t->donors); // 스레드의 기부자 리스트를 초기화
	list_push_back(&all_list, &t->all_elem); // 스레드의 all_elem을 리스트의 끝에 추가

	// milfqs로 실행했을 경우 nice_value와 recent_cpu를 초기화
	if (thread_mlfqs == true){
		t->nice_value = 0;
		t->recent_cpu = 0;
	} 
}

< next_thread_to_run >

// 다음 실행할 스레드를 선택하고 반환
static struct thread *
next_thread_to_run (void) {
	// ready_list가 비어있으면 유휴 스레드를 반환
	if (list_empty (&ready_list))
		return idle_thread;
	// ready_list에 스레드가 있으면 맨 앞의 스레드를 pop하고 반환
	else
		return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

< do_schedule >

// 스레드의 상태를 변경 후 전환
static void
do_schedule(int status) {
	// 인터럽트가 켜있거나, 현재 스레드 상태가 대기중이면 종료
	ASSERT (intr_get_level () == INTR_OFF);
	ASSERT (thread_current()->status == THREAD_RUNNING);
	
	// 파괴를 요청한 리스트가 빌 때까지 반복
	while (!list_empty (&destruction_req)) {
		// 파괴 리스트의 맨 앞 스레드를 pop하고 victim 스레드에 넣는다
		struct thread *victim =
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
		// victim에 할당된 메모리 페이지를 해제한다.
		palloc_free_page(victim);
	}
	
	// 현재 스레드 상태를 인자로 받은 status로 저장하고 schedule() 실행
	thread_current ()->status = status;
	schedule ();
}

< schedule >

// 현재 실행 중인 스레드에서 다음 실행 스레드로 변경하는 과정
static void
schedule (void) {
	// curr에 실행중인 스레드를 넣고, next에 다음에 실행할 스레드를 넣는다.
	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));

	// 다음 스레드의 상태를 실행 중으로 변경
	next->status = THREAD_RUNNING;

	// 새 타임 슬라이스 시작
	thread_ticks = 0;

// 이 부분은 잘 모르겠다
#ifdef USERPROG
	/* Activate the new address space. */
	process_activate (next);
#endif

	// 실행 중인 스레드와 다음 스레드가 다를 경우
	if (curr != next) {
		// 현재 스레드가 존재하고 상태가 죽어가는 스레드이며, 초기 스레드가 아닌 경우
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			// 어차피 if에서 걸리기 때문에 ASSERT 필요없어도 되지 않을까 싶다
			ASSERT (curr != next);
			// 파괴 요청 리스트에 현재 elem을 넣는다
			list_push_back (&destruction_req, &curr->elem);
		}
		// 현재 스레드에서 다음 스레드로 컨텍스트 스위칭을 수행
		// 현재 실행 중인 스레드의 상태를 저장하고, 다음 스레드의 상태를 복원한다.
		thread_launch (next);
	}
}

< thread_sleep >

// 스레드 재우기
void thread_sleep(int64_t ticks){
	struct thread *t = thread_current(); // t에 현재 스레드 저장
	enum intr_level old_level; // 인터럽트를 복원할 변수 지정
	t->sleep_ticks = ticks; // 스레드를 재울 ticks에 인자 ticks 저장

	old_level = intr_disable(); // 인터럽트를 저장하고 비활성화
	list_insert_ordered(&sleep_list, &t->elem, sleep_list_order, NULL); // sleep_list에 t의 elem을 삽입
	thread_block(); // 스레드를 블락시킨다.
	intr_set_level(old_level); // 다시 인터럽트를 복원
}

< thread_wakeup >

// 자고 있는 스레드 깨우기
void thread_wakeup(int64_t ticks) {
  enum intr_level old_level;
  old_level = intr_disable();

	// sleep_list가 빌 때까지 반복
  while (!list_empty(&sleep_list)) {
	  // waking_up에 sleep_lsit 맨 앞 스레드를 저장
    struct list_elem *waking_up = list_front(&sleep_list);
    // checker에 waking_up의 구조체에 대한 포인터 저장
    struct thread *checker = list_entry(waking_up, struct thread, elem);

		// checker의 sleep_ticks가 인자로 가져온 ticks보다 작거나 같으면
    if (checker->sleep_ticks <= (ticks)) {
	    // waking_up에 sleep_list의 맨 앞 요소를 pop해 저장한다.
      waking_up = list_pop_front(&sleep_list);
      // ready_list에 waking_up을 우선도 스케줄링을 적용하여 삽입한다
      list_insert_ordered(&ready_list, waking_up, priority_scheduling, NULL);
    } else {
      break;
    }
  }
  
  intr_set_level(old_level);
}

< sleep_list_order >

// sleep_list 정렬
static bool sleep_list_order(const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED){
  // 스레드 a와 b를 가져와 sleep_ticks를 비교해 a가 작으면 true 반환 크면 false 반환
  const struct thread *a = list_entry (a_, struct thread, elem);
  const struct thread *b = list_entry (b_, struct thread, elem);

  return a->sleep_ticks < b->sleep_ticks;
}

< priority_scheduling >

// 우선도 스케줄링 정렬
bool priority_scheduling(const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED){
  // 스레드 a와 b를 가져와 비교해서 a가 작으면 true 반환 크면 false 반환
	const struct thread *a = list_entry (a_, struct thread, elem);
	const struct thread *b = list_entry (b_, struct thread, elem);

	return a->priority > b->priority;
}