[PINTOS_PROJECT1] THREAD1

1. thread 구조체

thread.h

struct thread {
	/* Owned by thread.c. */
	tid_t tid;                          /* Thread identifier. */
	enum thread_status status;          /* Thread state. */
	//스레드의 상태는 thread_running, thread_ready, thread_blocked, thread_dying 중 하나

	char name[16];                      /* Name (for debugging purposes). */
	int priority;                       /* Priority. 스레드 우선순위(0이 가장 낮은 우선순위) */

	int64_t wakeup_tick;                // pintos project - alarm clock
	int init_priority;		    // pintos project - priority donation

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */
	// pintos project - priority donation
	struct lock *wait_on_lock; 		// 스레드가 현재 얻기 위해 기다리고 있는 lock
	struct list donations; 			// 자신에게 priority를 나눠준 스레드 리스트
	struct list_elem donation_elem; 	// donations 리스트를 관리하기 위한 element


	// 스레드를 이중연결 리스트에 넣기 위해 사용
	// 이중연결리스트란, ready_list(run을 위해 ready 중인 스레드의 리스트),
	// sema_down()에서 세마포어에서 waiting 중인 스레드 리스트를 말함
	// 세마포어에 있는 스레드는 ready 상태가 될 수 없고, ready 상태인 스레드는 세마포어일 수 없으므로 
	// 두 리스트에 대해 같은 list_elem을 사용할 수 있음
  	···
 }

2. thread_start()

// 스케줄러를 시작하기 위해 호출
// ready 상태의 스레드가 없을 때, 스케줄 되는 idle thread 생성
// (idle은 어떤 프로그램에 의해서도 사용되지 않는 유휴 상태를 의미)
// main()이나 intr_yield_on_return()을 사용하는 인터럽트를 가능하게 만든다
  
void
thread_start (void) {
	/* Create the idle thread. */
	struct semaphore idle_started; 
	//semaphore 구조체 (멤버 : current value, list waiters(waiting threads 리스트))

	sema_init (&idle_started, 0); // 초기값 0으로 만들어줘서 create 하는동안에 보호해주는것 

	thread_create ("idle", PRI_MIN, idle, &idle_started); //idle thread 생성
	// idle() 호출해서, &idle_started를 인자로 넣음
	// idle()에서 sema_up() 실행해줌 -> 그러고 나서, sema_down이 가능해짐!

	/* Start preemptive thread scheduling. */
	intr_enable (); //interrupt on 

	/* Wait for the idle thread to initialize idle_thread. */
	sema_down (&idle_started); //sema_init (&idle_started, 0) 으로 보호상태(0인 상태)이기 때문에
	// idle_started 세마포어가 1이 될때까지 실행되지 않음. 
	// thread_create()가 실행하면 idle 함수에서 sema_up을 할 때까지!

}

3. thread_create()

//인자 name으로 스레드를 만들고 시작
//만들어진 스레드의 tid 반환하고, 해당 스레드는 function 함수를 실행, aux는 function의 인자를 나타냄
//thread_create()는 스레드의 페이지를 할당하고, 스레드 구조체를 초기화하며 스레드 스택을 할당함
//스레드는 blocked 상태에서 초기화 되며, 반환 직전에 unblocked 됨 --> 스레드를 스케줄하기 위해!

tid_t
thread_create (const char *name, int priority,
		thread_func *function, void *aux) {
	struct thread *t;
	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 (); //tid 할당

	/* Call the kernel_thread if it scheduled. // 스케줄 되었을 때, 실행할 첫 명령어가 kernel_thread
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	t->tf.rip = (uintptr_t) kernel_thread; // 현재 영역의 위치를 가리키는 포인터
	t->tf.R.rdi = (uint64_t) function; // kernel_thread에 넣을 1번째 인자
	t->tf.R.rsi = (uint64_t) aux; // kernel_thread에 넣을 2번째 인자
	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); //unblock 해서 ready queue에 넣기

	// pintos project - priority
	// 생성된 스레드 t의 우선순위(t->priority)와 current 스레드의 우선순위(thread_current()-> priority) 비교하여, 
	// t의 우선순위가 더 클 경우, thread_yield() 호출하여 cpu 선점
	if (t->priority > thread_current()-> priority)
		thread_yield();

	test_max_priority();

	return tid;
}

4. init_thread()

// 커널 스레드에 들어가야 하는 정보를 가지고 있는 struct thread의 값을
// 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);

	// pintos project - priority donation
	t->init_priority = priority;
	t->wait_on_lock = NULL;
	list_init(&t->donations);

	t->status = THREAD_BLOCKED;
	strlcpy (t->name, name, sizeof t->name);
	t->tf.rsp = (uint64_t) t + PGSIZE - sizeof (void *);
	t->priority = priority;
	t->magic = THREAD_MAGIC;
}

5. thread_unblock()

// 인자로 받은 스레드를 다시 스케줄 되도록 함
// (block 상태인 스레드를 unblock(ready to run)상태로 변경)
void
thread_unblock (struct thread *t) {
	enum intr_level old_level;

	ASSERT (is_thread (t)); 

	old_level = intr_disable (); //intrerupt off
	ASSERT (t->status == THREAD_BLOCKED); //해당 스레드의 상태가 block 상태인지 확인

	// pintos project - priority
	// list_push_back (&ready_list, &t->elem); // 해당 스레드를 ready_list 끝에 추가
	// priority에 따라 정렬하여 ready_list에 삽입
	list_insert_ordered(&ready_list, &t->elem, cmp_thread_priority, NULL);

	t->status = THREAD_READY; // 스레드 상태를 ready로 변경
	intr_set_level (old_level);
}

6. thread_yield()

// 현재 running 중인 스레드를 비활성화 시키고, ready_list에 삽입
// 해당 과정을 수행하는 동안 들어오는 interrupt를 모두 무시하고,
// 작업이 끝나면 thread_yield()하기 직전의 인터럽트 상태로 되돌림
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ()); 
	// intr_context() : 외부(하드웨어) 인터럽트 수행 중에는 해당 값이 true로 설정되며, 이 외에는 false를 반환

	old_level = intr_disable (); //old level은 interrupt off로 설정

	// pintos project - priority
	if (curr != idle_thread) //curr가 idle_thread가 아니면, ready_list의 맨 끝에 삽입
		list_insert_ordered(&ready_list, &curr->elem, cmp_thread_priority, NULL);// 우선순위에 따라 정렬되어 삽입
		// cmp_thread_priority() : ready_list의 우선순위가 높으면 1, curr->elem의 우선순위가 높으면 0을 반환
	
	do_schedule (THREAD_READY); //do_schedule로 스레드 상태를 running에서 ready로 변경
	intr_set_level (old_level); // 인자로 부여한 level이 interrupt ON 상태이면 intr_enable ()/ interrupt off 상태이면 intr_disable ()
}

7. do_schedule()

// 현재 running 중인 스레드 status를 바꾸고, 새로운 스레드를 실행

static void
do_schedule(int status) {
	ASSERT (intr_get_level () == INTR_OFF); //interrupt off 상태인지 확인
	ASSERT (thread_current()->status == THREAD_RUNNING); //current 스레드 상태가 running인지 확인
	while (!list_empty (&destruction_req)) {  
		// destruction_req가 있는 리스트의 맨 앞을 victim으로 지정
		// 즉, 삭제 리스트 안의 첫번째 리스트를 victim으로 지정
		struct thread *victim =
			list_entry (list_pop_front (&destruction_req), struct thread, elem);
		palloc_free_page(victim); // victim 페이지 할당 해제
	}
	thread_current ()->status = status; //현재 스레드의 상태를 인자로 받은 상태(ready)로 갱신
	schedule ();
}

8. schedule()

// running 스레드(current)를 빼내고, next 스레드를 running으로 만들어 줌
// curr = running 상태의 스레드
// next = ready_list가 있으면, ready_list의 첫번째 스레드를 가져오고, ready_list가 빈 경우, idle thread

static void
schedule (void) {
	struct thread *curr = running_thread (); 
	struct thread *next = next_thread_to_run (); 

	ASSERT (intr_get_level () == INTR_OFF); // interrupt off 상태 확인
	ASSERT (curr->status != THREAD_RUNNING); // current 스레드 상태가 running인지 확인
	ASSERT (is_thread (next)); 
    
	/* Mark us as running. */
	next->status = THREAD_RUNNING; //next 스레드 running으로 변경

	/* Start new time slice. */
	thread_ticks = 0; //thread_ticks를 0으로 변경(새로운 스레드가 시작했으므로)

#ifdef USERPROG
	process_activate (next);
#endif

	if (curr != next) { 
		if (curr && curr->status == THREAD_DYING && curr != initial_thread) {
			// curr가 존재하면서 dying 상태이고, curr는 initial_thread가 아니라면
			// curr를 삭제 리스트의 마지막에 넣기
			ASSERT (curr != next);
			list_push_back (&destruction_req, &curr->elem);
		}
		thread_launch (next); // next를 thread_launch()함(context switching 수행)
	}
}

9. thread_launch();

// 새로운 스레드가 running함에 따라, context switching 수행
static void
thread_launch (struct thread *th) {
	uint64_t tf_cur = (uint64_t) &running_thread ()->tf; 
	uint64_t tf = (uint64_t) &th->tf;
	ASSERT (intr_get_level () == INTR_OFF); //interrupt off 

	/* The main switching logic.
	 * We first restore the whole execution context into the intr_frame
	 * and then switching to the next thread by calling do_iret.
	 * Note that, we SHOULD NOT use any stack from here
	 * until switching is done. */
	__asm __volatile (
			/* Store registers that will be used. */
			// rax : 누산기(accumulator) 레지스터 -> 사칙연산 명령어에서 자동으로 사용, 리턴 레지스터/ 시스템콜의 실질적인 번호를 가리키는 포인터
			// rbx : 베이스 레지스터 -> 메모리 주소 저장
			// rcx : 카운터 레지스터 -> ECX(Extended Counter Register)로, 반복적으로 수행되는 연산에 사용되는 카운터 값 저장
			// rdx : 데이터 레지스터 -> EAX(Extended Accumulator Register)와 같이 사용되며, 산술 연산 또는 함수의 리턴 값 저장
			"push %%rax\n"
			"push %%rbx\n"
			"push %%rcx\n"
			/* Fetch input once */
			// rsp : 스택 포인터 레지스터 / rbp : 베이스 포인터 레지스터(스택 복귀 주소)/ rsi : 근원지(source) 레지스터/ rid : 목적지(destination) 레지스터
			// rsp, rbp, rsi, rdi 레지스터의 경우 포인터나 인덱스라 부르기도 함
			"movq %0, %%rax\n"
			"movq %1, %%rcx\n"
			"movq %%r15, 0(%%rax)\n"
			"movq %%r14, 8(%%rax)\n"
			"movq %%r13, 16(%%rax)\n"
			"movq %%r12, 24(%%rax)\n"
			"movq %%r11, 32(%%rax)\n"
			"movq %%r10, 40(%%rax)\n"
			"movq %%r9, 48(%%rax)\n"
			"movq %%r8, 56(%%rax)\n"
			"movq %%rsi, 64(%%rax)\n"
			"movq %%rdi, 72(%%rax)\n"
			"movq %%rbp, 80(%%rax)\n"
			"movq %%rdx, 88(%%rax)\n"
			"pop %%rbx\n"              // Saved rcx
			"movq %%rbx, 96(%%rax)\n"
			"pop %%rbx\n"              // Saved rbx
			"movq %%rbx, 104(%%rax)\n"
			"pop %%rbx\n"              // Saved rax
			"movq %%rbx, 112(%%rax)\n"
			"addq $120, %%rax\n"
			"movw %%es, (%%rax)\n"
			"movw %%ds, 8(%%rax)\n"
			"addq $32, %%rax\n"
			"call __next\n"         // read the current rip.
			"__next:\n"
			"pop %%rbx\n"
			"addq $(out_iret -  __next), %%rbx\n"
			"movq %%rbx, 0(%%rax)\n" // rip
			"movw %%cs, 8(%%rax)\n"  // cs
			"pushfq\n"
			"popq %%rbx\n"
			"mov %%rbx, 16(%%rax)\n" // eflags
			"mov %%rsp, 24(%%rax)\n" // rsp
			"movw %%ss, 32(%%rax)\n"
			"mov %%rcx, %%rdi\n"
			"call do_iret\n"
			"out_iret:\n"
			: : "g"(tf_cur), "g" (tf) : "memory"
			);
}