* 뇌피셜이 난무할 수 있습니다.
* 개인 공부 용도로 작성하였습니다.

참고자료

• Assignment
• 한양대 PPT
  • 한양대 PPT는 32비트 핀토스이기에 다른 것이 종종 존재한다.
    • 한양대 PPT에서는 all_list가 존재하지만 카이스트 핀토스에는 all_list가 존재하지 않는다.
• 여러 정글 선배님 노션 및 블로그들을 참고하였습니다.

---

Pintos

• 여타 다른 핀토스와는 수정된 점이 조금씩 있기에(스탠포드 핀토스는 32비트인 반면, 카이스트 핀토스는 64비트로 변경되어 있다. 이러한 점으로 인해, 레지스터 명칭이 바뀌어 있기도 하고 컨텍스트 스위칭 방식이 조금 다르기도 하다고 한다) 꼭 해당 Assignment을 따라야 올바르게 과제를 수행할 수 있다.
• x86-64 아키텍처를 위한, 간단한 운영체제 시스템 프레임워크이다.
• 핀토스에서 쓰레드와 프로세스의 관계는 모호하다. 1개의 쓰레드를 1개의 프로세스라고 봐도 될 듯 싶다.

---

Project 1: Threads

• 핀토스는 최소한의 쓰레드 시스템이 구현되어져 있다. 이번 과제에서는 이 쓰레드 체계를 확장시키고(기능을 추가하는 등) 동기화 문제를 해결하는 것이 주된 업무이다.
  • sleep/awake
  • Synchronization
  • Priority
• 대부분 devices(timer.c), threads(thread.c, synch.c 등) 폴더에서 주로 작업하게 된다.

Introduction

Understanding Threads

• 핀토스는 이미 쓰레드 시스템(생성, 쓰레드들끼리의 스케줄링, 동기화)을 구현해놓았다.
• thread_create(... function ...) 함수를 통해서 쓰레드를 만들고 해당 쓰레드가 스케줄 될 때 function을 실행하게 된다.
  • 이 function이 return 값을 반환하면 쓰레드는 종료된다.
  • 각 쓰레드는 핀토스 내에서 마치 하나의 프로그램처럼 동작하게 되며, function은 그 쓰레드에서 마치 C언어에서의 main함수처럼 동작하게 된다.
• 주어진 시간 내에(예를 들면 TIME_SLICE, 즉 4틱 만큼) 쓰레드는 정확히 1개만 run할 수 있다.(CPU가 1개이기 때문) 나머지는 비활성화된다.
  • CPU에 쓰레드가 1개 올라간다고 생각하자.
  • scheduler는 다음에 실행할 쓰레드를 결정한다.
  • 만약 실행할 쓰레드가 없다면, idle_thread가 run하게 된다.
• Synchronization primitives는 한 쓰레드가 다른 쓰레드의 작업을 대기해야 할 때, 컨텍스트 스위칭을 강제할 수 있다.
  • Synchronization primitives : 동기화를 위한 소프트웨어 메커니즘
    • mutex, conditional variables, semaphore 등이 primitives에 해당된다.
      • 출처 : https://velog.io/@24siefil/Philosophers-Synchronization#4-synchronization-primitive
  • synch.c의 sema_down을 보면, 만약 A라는 쓰레드가 CPU에 올라간 상태이고, S라는 공유자원(세마포어)을 얻어 작업을 수행하려고 할 때 이미 B라는 쓰레드가 S를 점유하고 있어 접근할 수 없다면 while문을 만족하여 thread_block()이 수행되고, 이는 do_schedule과 schedule 함수를 실행시켜, CPU에 ready_list에 있는 다른 쓰레드를 올리게 된다.(즉 A에서 다른 쓰레드로 바뀌므로 컨텍스트 스위칭이 일어난다고 볼 수 있다.
• 컨텍스트 스위칭은 thread.c의 thread_launch 함수에 의해 발생한다.
  • 현재 실행 중인 쓰레드가 어디까지 실행했는지 저장하고, 앞으로 실행시킬 쓰레드가 어디서부터 실행하면 될지 복구시켜 실행시킨다.
  • 전에 CPU에 올라갔을 때 어디까지 실행했었는지는, 즉 CPU에 올라가게 되면 어디서부터 실행해야 되는지에 대해서는 각 쓰레드 TCB(struct thread)의 interrupt frame에 저장되어 있다.
• do_iret 함수의 iret 명령어를 통해 다른 쓰레드가 실행을 시작하게 된다.

Synchronization

• 동기화 문제는 사실 인터럽트를 끄면서 쉽게 해결이 가능하다.
  • CPU가 인터럽트에 대해 반응할 수 없게 된다.
  • 하지만 아예 무시되는 것이므로 어떤 쓰레드가 공유된 자원을 가지기 위해 대기할 수 없게 된다.
  • 따라서 이러한 문제를 해결하기 위해 condition variables, semaphore, lock을 사용해야 한다.

---

Alarm Clock

• 현재 핀토스는 Alarm 기능이 Busy Waiting으로 구현되어 있다.
  • Busy Waiting : 원하는 자원을 얻기 위해 기다리는 것이 아니라, 권한을 얻을 때까지 계속해서 확인하는 방식이다.
    • 자원의 권한을 얻는데 많은 시간이 소요되지 않는 상황일 때는 효율적일 수 있다.
  • 어떤 쓰레드가 실행되고 있을 때 timer_sleep을 당하면, 해당 쓰레드는 할당 받은 시간(CPU를 점유할 수 있는)이 남아 있다면 해당 시간 동안 계속해서 while문에 갇혀 있게 된다. 곧바로 조건문을 만족하여 thread_yield를 수행하게 된다. 말 그대로 자신의 CPU 점유권을 양보하는 것이다.
  • busy waiting을 진행 중인 쓰레드는 계속해서 CPU에 올라갈 때 while문을 만족하여 thread_yield가 수행된다.(ready_list로 내려가고 ready_list의 다른 쓰레드를 CPU에 올린다)
• busy waiting을 진행 중인 쓰레드는 CPU에 올라갈 필요가 없다. 잠들어 있다가 깨어나서 실행되면 된다.
  • timer_sleep이 일어나면 깨어나야 할 시간인 wakeup_tick까지 sleep_list에 잠들어 있다가(block이 된다) wakeup_tick이 지나면 깨어나서 ready_list로 올리면 된다. 그러면 ready_list에서 자신의 차례가 되었을 때 CPU에 올라가서 원래 본인의 일을 수행할 것이다.

수정한 것들

thread.c

• 함수 선언

// PJ1, 함수 추가
void thread_sleep (int64_t ticks);
void thread_awake (int64_t ticks);
void update_next_tick_to_awake (int64_t ticks);
int64_t get_next_tick_to_awake (void);

---

• 전역 변수 추가

static struct list sleep_list;									// PJ1, busy waiting을 sleep/wakeup 방식으로 바꾸기 위해 sleep될 쓰레드를 담을 sleep_list 형성
int64_t next_tick_to_awake = INT64_MAX;							// PJ1, 다음 깨어나야 할 쓰레드의 wakeup_tick를 저장해두고 있는다. 즉 sleep_list에서 가장 먼저 깨어나야 할 쓰레드의 wakeup_tick를 저장하고 있다. sleep_list의 쓰레드들의 wakeup_tick들 중 가장 작은 wakeup_tick일 것이다.

---

• thread_init

list_init (&sleep_list);				// PJ1, sleep_list 초기화

---

• thread_sleep

// PJ1, timer_sleep의 연장선으로 thread_sleep을 시킨다.
// 인터럽트로 인해 방해 받지 않은 상태에서
// 쓰레드를 block 상태로 만들고 sleep_list에 넣는다.
// 이 쓰레드가 가장 빨리 깨어나야 할 쓰레드일 수도 있으니 update_next_tick_to_awake를 통해 갱신한다.
void thread_sleep (int64_t ticks) {							
	struct thread *current_thread = thread_current();		
	enum intr_level old_level;
	
	old_level = intr_disable();
	if (current_thread != idle_thread) {
		current_thread->wakeup_tick = ticks;
		list_push_back(&sleep_list, &current_thread->elem);
		update_next_tick_to_awake(current_thread->wakeup_tick);
	}
	
	do_schedule(THREAD_BLOCKED);
	intr_set_level(old_level);
}

---

• thread_awake

// PJ1, sleep_list를 순회하며 현재 ticks보다 낮거나 같아서 깨워야할 쓰레드가 있는지 확인하고 꺠운다.
void thread_awake (int64_t ticks) {
	struct list_elem *search_elem;
	
	for (search_elem = list_begin(&sleep_list); search_elem != list_end(&sleep_list);) {
		struct thread *search_thread = list_entry(search_elem, struct thread, elem);
		
		if (search_thread->wakeup_tick <= ticks) {  // PJ1, 지금 시간인 ticks보다 작다면 깨우는 과정이다.
			search_elem = list_remove(search_elem);	// 알아서 search_elem은 search_elem->next가 된다. search_elem을 sleep_list에서 삭제하고 다음 노드를 반환한다.
			thread_unblock(search_thread);			// status를 block에서 ready로 바꾸고 ready_list로 올린다.
		} else {
			// PJ1, 만약 sleep_list에 wakeup_tick이 다음과 같은 쓰레드들이 들어있다고 가정하면
			// 2, 8, 5, 7
			// next_tick_to_awake = 2이다. 그 다음 ticks가 6으로 들어왔다면
			// 2는 제거되고, 다음 방문한 쓰레드가 8일 때 next_tick_to_awake가 8로 변경되어야 한다.
			// 5는 제거되고, 마찬가지로 7일 때 next_tick_to_awake가 7로 변경되어야 한다.
			search_elem = list_next(search_elem);
			update_next_tick_to_awake(search_thread->wakeup_tick);	
		}
	}
}

---

• update_next_tick_to_awake

// PJ1, next_tick_to_awake를 갱신한다.
void update_next_tick_to_awake (int64_t ticks) {
	next_tick_to_awake = (ticks < next_tick_to_awake) ? ticks : next_tick_to_awake; 
}

---

• get_next_tick_to_awake

// PJ1, next_tick_to_awake를 반환한다.
int64_t get_next_tick_to_awake (void) {
	return next_tick_to_awake;
}

timer.c

• timer_sleep

void
timer_sleep (int64_t ticks) {				// PJ1, 현재로부터 ticks만큼의 뒤의 시간까지 잠들라는 함수이다. 즉 start + ticks까지 BLOCK되라는 함수이다.
	int64_t start = timer_ticks ();

	// <Busy Waiting 방식>
	// while (timer_elapsed (start) < ticks)				
	// 	thread_yield ();
	
	// PJ1, Sleep/Awake 방식
	ASSERT (intr_get_level () == INTR_ON);
	if (timer_elapsed(start) < ticks) {
		thread_sleep(start + ticks);			
	}
}

---

• timer_interrupt

static void
timer_interrupt (struct intr_frame *args UNUSED) {
	ticks++;
	thread_tick ();
	
	if (get_next_tick_to_awake() <= ticks) {				// PJ1, sleep_list의 최소값, 즉 다음으로 깨어나야 할 쓰레드의 wakeup_tick이 현재 ticks보다 작거나 같다면 꺠운다.
		thread_awake(ticks);								// sleep_list에서 제거하고 ready_list로 넣는다
	}
}

thread.h

• 함수 선언

// PJ1, 함수 선언
void thread_sleep (int64_t ticks);				// PJ1, 실행 중인 쓰레드를 sleep 상태로 만든다.
void thread_awake (int64_t ticks);				// PJ1, sleep_list에서 깨워야 할 쓰레드를 깨운다.
void update_next_tick_to_awake (int64_t ticks); // PJ1, next_tick_to_awake를 갱신한다.
int64_t get_next_tick_to_awake (void);			// PJ1, next_tick_to_awake 값을 반환한다.

---

• struct thread에 wakeup_tick 추가

int64_t wakeup_tick;				// PJ1, 해당 쓰레드가, ticks까지 잠들라고 하는 timer_sleep을 당했을 때, 언제 깨어나면 될지 저장하고 있는 변수.

• 완료 화면
  

---

Priority Scheduling

Implement priority scheduling and priority donation in Pintos

• 만약 현재 running 중인 쓰레드보다 더 높은 우선순위를 가진 쓰레드가 ready_list에 들어온다면,
  • running 중인 쓰레드는 곧바로 CPU 점유권을 그 더 높은 우선순위를 가진 쓰레드한테 양보해야 한다.
• 쓰레드의 우선순위 범위는 0 ~ 63까지이다. 낮을수록 우선순위가 낮음을 뜻한다.
  • 쓰레드가 처음 만들어지면 중간 값인 31을 부여 받는다.

Priority Scheduling

• 현재 핀토스의 스케줄러는 그저 라운드 로빈으로 구현되어 있다.
  • 이 때 현재 핀토스의 Time Quantum은 40msec이다.
    • 핀토스에서 1틱은 10msec이다.
      • timer.h에 보면

      /* Number of timer interrupts per second. */
      #define TIMER_FREQ 100

      으로 정의되어 있다. 1초에 100번의 주파수이므로 1번의 주파수를 일으키기 위해서는 0.01초, 즉 10msec가 필요해진다. 따라서 1틱은 10msec가 필요하다.
      • Time Quantum이 40msec라는 것은 4틱이라는 것과 같다.
• 우선순위 개념이 아직은 없다.
  • ready_list에 새로 추가된 쓰레드의 우선 순위가, CPU를 점유 중인(running) 쓰레드의 우선순위보다 높다면, 기존 쓰레드를 밀어내고 CPU를 점유하도록 한다.
  • 여러 쓰레드가 락 혹은 세마포어를 얻기 위해 기다릴 경우 우선순위가 가장 높은 쓰레드가 CPU를 점유하도록 한다.

수정한 것들

thread.h

• 함수 선언

// PJ1
void test_max_priority (void);					// 현재 running 중인 쓰레드와, ready_list의 가장 높은 우선순위의 쓰레드의 우선순위를 비교하여 스케줄링한다.
bool cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);		// 인자로 주어진 쓰레드들의 우선순위를 비교한다.

thread.c

• thread_create

/* Add to run queue. */
	thread_unblock (t);
	
	test_max_priority();		// PJ1, 새로 만들어진 쓰레드(thread_unblock에 의해 ready_list로 들어갔을 것이다)의 우선순위가,
								// CPU를 점유하고 있는 쓰레드보다 높다면, 전자가 CPU를 선점하도록 한다.

	return tid;

---

• thread_unblock

void
thread_unblock (struct thread *t) {
	// list_push_back (&ready_list, &t->elem);
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);		// PJ1, ready_list에 우선순위가 높은 순서대로 담기도록 설정한다.(우선순위가 높은 쓰레드가 ready_list의 맨 처음에 오도록)
}

---

• thread_yield

void
thread_yield (void) {
	if (curr != idle_thread)
		// list_push_back (&ready_list, &curr->elem);
		list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);		// PJ1, 현재 쓰레드가 CPU를 양보하고 ready_list로 들어가게 되는데, 이 때 우선순위대로 정렬되도록 삽입한다.		
	do_schedule (THREAD_READY);													// 양보하고 난 후, ready_list의 맨 처음 쓰레드(next_thread_to_run)가 CPU를 차지(schedule)할 수 있게 만든다.
}

---

• thread_set_priority

void
thread_set_priority (int new_priority) {
	thread_current ()->priority = new_priority;
	
	test_max_priority();		// PJ1, 현재 쓰레드의 우선순위가 바뀐다면, ready_list의 쓰레드들이 더 우선순위가 높을 수도 있다. 그럴 때는 그 쓰레드가 CPU를 점유해야 한다.
}

• test_max_priority

// PJ1, 만약 현재 쓰레드보다 ready_list의 첫 번째 쓰레드(가장 우선순위가 높은)가 더 높은 우선순위를 가지고 있다면, 현재 쓰레드는 CPU를 양보하고 ready_list의 가장 우선순위가 높은 쓰레드가 CPU를 점유하도록 만든다.
void test_max_priority (void) {
	if (list_empty(&ready_list)) {
		return;
	}
	
	struct list_elem *highest_priority_e = list_begin(&ready_list);
	struct thread *highest_priority_t = list_entry(highest_priority_e, struct thread, elem);
		
	if (thread_current()->priority < highest_priority_t->priority) {
		thread_yield();
	}
}

• cmp_priority

// PJ1, a의 우선순위가 더 높다면 true를 반환한다. list_insert_ordered 함수에 인자로 사용된다.
bool cmp_priority (const struct list_elem* a_elem, const struct list_elem *b_elem, void* aux UNUSED) {
	struct thread* thread_a = list_entry(a_elem, struct thread, elem);
	struct thread* thread_b = list_entry(b_elem, struct thread, elem);
	
	if (thread_a->priority > thread_b->priority) {
		return true;
	} else {
		return false;
	}
}

• 완료 화면
  

---

Priority Scheduling - Synchronization

• 여러 쓰레드가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 쓰레드가 CPU를 점유하도록 구현한다.

기타 함수들

• idle_thread
  init.c의 main함수의 thread_start로부터 만들어진다. 맨 처음 1번 만들어지는 쓰레드로, CPU가 비어있으면 idle_thread가 올라가게 된다.(schedule 함수의 next 변수의 next_thread_to_run에 의해)

• next_thread_to_run
  ready_list를 확인해서 다음 CPU에 올릴 쓰레드를 반환한다. ready_list가 비어있으면 idle_thread를 반환한다.

thread_create, thread_start, idle_thread + next_thread_to_run, init.c, TCB, sema_down, thread_block, thread_launch, do_iret, struct thread, interrupt frame, thread_current,

timer_sleep, thread_yield, list_entry