본문 바로가기
Review/SW Jungle

[WEEK08] Pintos _ Project1 THREADS

by jamiehun 2022. 11. 17.

1. 프로젝트 관련 공부

Keywords

: Context Switching, Process, Threads, Scheduler, Timer Interrupt, Synchronization

Context

"프로세스는 실행중인 프로그램이다.(Process is a program in execution)"
프로그램의 문맥이란 현재 시점에서 CPU의 수행상태를 나타내줌
즉 프로세스의 현재 상태라고 볼 수 있음
프로세스는 사람으로 치면 키는 몇이고, 몸무게는 얼마나 되고, 지식은 얼마나 있나로 볼 수 있음

컴퓨터에서는 Context를 위해 필요한 것이 총 3가지인데
1. 하드웨어 문맥 : Program Counter, Register
2. 프로세스의 주소공간 (Code, Data, Stack 영역에 무엇이 있는지)
3. 프로세스 관련 커널 자료구조 : PCB, Kernel Stack
=> 이를 통해 CPU가 어느 상태에 있는지 알 수 있다.

Process의 상태

프로세스는 상태(state)가 변경되며 수행됨
Running : CPU를 잡고 Instruction을 수행 중인 상태
Ready : 메모리 등 다른 조건을 모두 만족하고 CPU를 기다리는 상태
Blocked(Wait, Sleep) : CPU를 주어도 당장 Instruction을 수행할 수 없는 상태 (event가 먼저 일어나야 함)
New : 프로세스가 생성 중인 상태
Terminated : 수행(Execution)이 끝난 상태

프로세스의 상태


CPU는 하나의 프로세스만 동작시키며 Running, Ready Queue가 있음

예를 들어 CPU가 프로세스를 동작시키다가 Disk나 Keyboard에 필요한 것이 있으면 해당 Queue에 줄을 세우고,
해당 Queue가 CPU에 전송이 되면 CPU는 잠시 하던 일을 멈추고 OS에게로 가서 해당 데이터를 CPU의 Ready Queue에 세우고
추후 CPU를 진행시킬 수 있는 자격이 생기게 됨

커널주소영역의 데이터 영역에는 PCB(프로세스 제어블록)이 존재하고
PCB는 프로세스와 관련된 정보를 저장하는 자료구조로서 프로세스 ID, 레지스터 값, 프로세스 상태, CPU 스케쥴링정보, 메모리관리정보, 사용한 파일과 입출력 장치 목록 등이 포함되어 있음

 

Context Switching

CPU를 한 프로세스에서 다른 프로세스로 넘겨주는 과정으로
운영체제(OS)는 CPU가 다른 프로세스에게 넘어갈 때 다음과 같은 과정을 수행한다.
1. CPU를 내어주는 프로세스의 상태를 그 프로세스의 PCB에 저장함
2. CPU를 새롭게 얻는 프로세스의 상태를 PCB에서 읽어옴

=> 이러한 Context Switching은 System Call이나 Interrupt 발생시 일어남
=> 실질적으로 Context Switching은 프로세스-> 운영체제 커널 혹은 사용자 프로세스 -> 커널모드를 의미하는 것이 아님
=> 프로세스 -> 다른 프로세스로 넘겨주는 과정을 의미함

Timer Interrupt

타이머 인터럽트의 경우 clock 신호를 발생시키는 장치에 의해 주기적으로 발생하는 하드웨어 인터럽트로 (=timeout interrupt)
기본적인 interrupt의 경우
1. 현재 상태를 멈추고, 현재 상태를 보관
2. interrupt 종류 분석
3. 특정 interrupt 수행
4. 보관된 상태를 원상복귀하고 멈춘 작업을 재개
추가 정보 : https://raisonde.tistory.com/entry/인터럽트Interrupt의-개념과-종류

Threads

스레드는 실행의 단위로서 프로세스를 구성하는 실행의 흐름단위
하나의 프로세스에 여러 개의 스레드를 가질 수 있음 (동시성 thread)
thread는 context의 크기가 process보다 작기 때문에 문맥전환이 빠르고 부모-자식간의 관계가 아닌 peer들의 pool을 구성함
thread는 thread ID, 스택, 스택포인터, 프로그램카운터, 조건코드, 범용 레지스터 값을 개별로 가지고, 코드, 읽기/쓰기 데이터, 힙, 공유 라이브러리 코드, 데이터 영역으로 공유자원을 다른 thread들과 공유함

Scheduler

/* 인자로 주어진 ticks 동안 스레드를 block */
void timer_sleep (int64_t ticks)

/* Thread를 blocked 상태로 만들고 sleep queue에 삽입하여 대기 */
void thread_sleep(int64_t ticks)

/* Sleep queue에서 깨워야 할 thread를 찾아서 wake */
void thread_awake(int64_t ticks)


전체적으로 봤을 때 위의 thread나 process들은 CPU를 필요로 하고 사용을 원하지만 OS는 공정하고 합리적으로 CPU할당을 하기 위해 어떤 프로세스 혹은 스레드에 CPU를 할당할지, 기다리게 할지 결정을 해야함
따라서, CPU scheduling이란 복수의 CPU 자원을 배분하는 것을 의미함
- 비선점형 스케쥴링 : 실행중인 프로세스/스레드보다 높은 우선순위를 가지는 프로세스가 실행된다 해도 실행대상을 바로 변경 x
- 선점형 스케쥴링 : 프로세스보다 높은 우선순위의 프로세스가 실행되면 스케쥴러에 의해 실행순서가 적극 조정되는 OS를 의미함
=> 스케쥴링을 통해서 CPU 사용 효율을 높임

Synchronization

프로세스나 스레드는 공유된 변수를 사용하는 경우가 있는데 이러한 변수들을 프로세스별로 독립적으로 수행하면 문제가 없음
반면 이들이 순서 병행으로 수행되면 실행되는 순서에 따라 올바르게 작동하지 않을 수 있음 => 프로세스 동기화가 필요함
이러한 프로세스 동기화에는 세마포어, 모니터 등의 방식을 활용할 수 있음

2. 과제 구현

과제 1 (Alarm Clock)

- 호출한 프로세스를 정해진 시간 후 다시 시작하는 커널 함수인 Alarm을 Busy waiting 방식 -> sleep/wake 방식으로 구현함
- 위에서 말한 CPU 스케쥴링을 기존 방식에서 좀 더 효율적인 방법 (Round Robin)을 활용한 Code 구현을 진행함

솔루션

- Sleep된 thread를 저장하는 자료구조
- timer_sleep()을 호출한 thread를 저장
- loop 기반 wait() -> sleep/wakeup 으로 변경

주요 수정 및 추가함수

/* 인자로 주어진 ticks 동안 스레드를 block */
void timer_sleep (int64_t ticks)

/* Thread를 blocked 상태로 만들고 sleep queue에 삽입하여 대기 */
void thread_sleep(int64_t ticks)

/* Sleep queue에서 깨워야 할 thread를 찾아서 wake */
void thread_awake(int64_t ticks)

/* Thread들이 가진 tick 값에서 최소 값을 저장 */
void update_next_tick_to_awake(int64_t ticks)

/* 최소 tick값을 반환 */
int64_t get_next_tick_to_awake(void)

 

/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks (); // start: 시작 시 시간(tick)

	ASSERT (intr_get_level () == INTR_ON); // 현재 인터럽트 상태가 enable
	
	/* 기존의 busy writing을 유발하는 코드를 삭제 */
	// while (timer_elapsed (start) < ticks)
	// thread_yield ();

	/* 새로 구현한 thread를 sleep queue에 삽입하는 함수를 호출 */
	if(timer_elapsed(start) < ticks) 
		thread_sleep(start + ticks); // ticks의 시간만큼 재움

}

 

/* 실행 중인 스레드를 슬립으로 만듦 */
void thread_sleep(int64_t ticks){
	/* 현재 스레드가 idle 스레드가 아닐 경우 
	   thread의 상태를 BLOCKED로 바꾸고 깨어나야 할 ticks를 저장 */
	struct thread *cur = thread_current();
	enum intr_level old_level;

	ASSERT (!intr_context ()); // 외부 인터럽트가 안들어왔을 때만 통과

	old_level = intr_disable(); 
	if (cur != idle_thread){
		// cur->status = THREAD_BLOCKED; // running -> sleep이라 yield랑은 다르게 BLOCKED으로 설정
		cur->wakeup_tick = ticks; 	  // 깨어나야할 ticks를 저장 (tick만큼 잠들어 있어 !)
		update_next_tick_to_awake(cur->wakeup_tick);
		list_push_back(&sleep_list, &cur->elem);
	}
	do_schedule(THREAD_BLOCKED); // next를 running으로 만
	
	/* schedule() 함수의 목적은 ready_list에서 뽑아내서 다음의 running list로 바꾸는 것
		=> 필요없을 것으로 보임 */
	// schedule();
	intr_set_level(old_level);

 

/* wakeup_tick 값이 ticks보다 작거나 같은 스레드를 깨움 
 * 현재 대기중인 스레드들의 wakeup_tick 변수 중 가장 작은 값을 
 * next_tick_to_awake 전역 변수에 저장
 */
void thread_awake(int64_t ticks)
{
	struct list_elem *e = list_begin(&sleep_list);
	next_tick_to_awake = INT64_MAX;

	while (e != list_tail(&sleep_list)) {
		struct thread *f = list_entry(e, struct thread, elem);
		
		if (ticks >= f->wakeup_tick){
			e = list_remove(&f->elem);
			// ASSERT (is_interior(e));
			thread_unblock(f);

		}

		else{
			update_next_tick_to_awake(f->wakeup_tick);
			e = e->next;
		}
	}


}

 

/* 최소 틱을 가진 스레드 저장 */
void update_next_tick_to_awake(int64_t ticks)
{	
	// next_tick_to_awake = INT64_MAX;
	/* 다음에 일어나야할 tick 저장 */
	// static int64_t next_tick_to_awake;
	// if (next_tick_to_awake == NULL){
	// 	next_tick_to_awake = ticks;
	// }
		
	// 만약 ticks가 next_tick_to_awake보다 작으면 해당 변수 update
	if (ticks < next_tick_to_awake){
		next_tick_to_awake = ticks;
		printf("========================\n");
		printf("%lld\n", next_tick_to_awake);
	}
}

 

/* thread.c의 next_tick_to_awake를 반환 */
int64_t get_next_tick_to_awake(void){
	return next_tick_to_awake;
}

 

과제 2-1 (Priority Scheduling)

- 과제 1에서 수행한 Pintos Scheduler를 Priority 기준으로 CPU를 점유하도록 수정
- 여러 thread들이 CPU 수행을 기다리고 있을 경우 우선순위가 높은 thread가 CPU를 먼저 점유

솔루션

- 추가된 thread가 실행중인 thread보다 우선순위가 높은 경우 CPU를 선점하도록 하기 위해 thread_create() 함수 수정
- ready_list를 우선순위로 정렬하기 위해 thread_unblock(), thread_yield() 함수들을 수정
- list_insert_ordered() 함수에 사용되는 cmp_priority() 함수를 추가
- 새로운 thread가 생성되거나 block되었던 thread가 unblock 되었을 때 (thread_unblock()) ready_list에 thread 추가

주요 수정 및 추가함수

/* 현재 수행중인 스레드와 가장 높은 우선순위의 스레드의 우선순위를 비교하여 스케줄링 */
void test_max_priority (void)

/* 인자로 주어진 스레드들의 우선순위를 비교 */
bool cmp_priority (const struct list_elem *a, const struct list_elem *b,void *aux UNUSED)

/* 새로운 스레드를 생성 */
tid_t thread_create (const char *name, int priority, thread_func *function, void *aux)

/* block된 스레드를 unblock */
void thread_unblock (struct thread *t)

/* 현재 수행중인 스레드가 사용중인 CPU를 양보 */
void thread_yield (void)

/* 현재 수행중인 스레드의 우선순위를 변경 */
void thread_set_priority (int new_priority)

 

/* 현재 수행중인 스레드의 우선순위와 ready_list의 가장 높은 우선순위를 비교하여 스케줄링(preempted) */

void test_max_priority(void)
{
	int cur_priority = thread_get_priority();				   // 현재 쓰레드 우선순위 저장
	// ASSERT(!list_empty(&ready_list));					   // error 체크용
	if (list_empty(&ready_list)) return;
	struct list_elem *e = list_begin(&ready_list);			   // ready_list의 첫번째 elem 반환
	struct thread *max_t = list_entry(e, struct thread, elem); // e에 해당하는 thread 저장

	if ((!list_empty(&ready_list)) && (cur_priority < max_t->priority)) // ready_list의 첫번째 thread 우선순위가 더 높으면
	{
		thread_yield(); // running thread가 CPU양보
	}
}

 

/* 첫번째 인자의 우선순위가 높으면 1을 반환,두 번째 인자의 우선순위가 높으면 0을 반환 */
/* elem을 기준으로 priority를 비교하여 설정함 */

bool cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{ // NULL일때 예외처리할것
	
	struct thread *temp1 = list_entry(a, struct thread, elem);	//list_elem *a 에 해당하는 thread 반환
	struct thread *temp2 = list_entry(b, struct thread, elem);	//list_elem *b 에 해당하는 thread 반환

	return temp1->priority > temp2->priority;
}

 

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();

	/* Call the kernel_thread if it scheduled.
	 * Note) rdi is 1st argument, and rsi is 2nd argument. */
	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;

	/* Add to run queue. */
	struct thread *curr = thread_current();
	thread_unblock(t); // ready list에 순서에 맞게 넣어줌

	/* 생성된 스레드의 우선순위가 현재실행중인 스레드의 우선순위보다 높다면 CPU를 양보한다. */
	/* 첫번째 인자의 우선순위가 높으면 1을반환,두 번째 인자의 우선순위가 높으면 0을반환 */
	if (cmp_priority(&t->elem, &curr->elem, NULL)) // aux=NULL로 전달
	{
		thread_yield();
	}
	return tid;
}

 

void thread_unblock(struct thread *t)
{
	enum intr_level old_level;
	ASSERT(is_thread(t));
	old_level = intr_disable();
	ASSERT(t->status == THREAD_BLOCKED);
	/* Thread가 unblock될 때 우선순위 순으로 정렬되어 ready_list에 삽입되도록 수정 */
	list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL); //list_less_func* less는 cmp_priority함수포인터로 전달 ,aux=NULL로 전달

	t->status = THREAD_READY;
	intr_set_level(old_level);
}

 

/* 현재 running 중인 스레드를 비활성화 시키고 ready_list에 삽입 */

void thread_yield(void)
{
	struct thread *curr = thread_current(); //현재 실행 중인 스레드
	enum intr_level old_level;				//인터럽트 level: on/off

	ASSERT(!intr_context()); 	// 외부 인터럽트가 들어왔으면 True / 아니면 False => 외부인터럽트가 False여야 밑으로 진행됨

	old_level = intr_disable(); // 인터럽트를 비활성하고 이전 인터럽트 상태(old_level)를 받아온다.

	if (curr != idle_thread)    // 현재 스레드가 idle 스레드와 같지 않다면

	{   //현재 thread가 CPU를 양보하여 ready_list에 삽입될 때 우선순위 순서로 정렬되어 삽입
		list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL); 
	}

	do_schedule(THREAD_READY); // context switch 작업 수행 - running인 스레드를 ready로 전환.
	intr_set_level(old_level); // 인자로 전달된 인터럽트 상태로 인터럽트 설정하고 이전 인터럽트 상태 반환
}

 

/* 스레드의 우선순위가 변경되었을 때 우선순위에 따라 ready_list의 우선순위와 비교하여 스케줄링(preempted) */
/* donation을 고려하여 thread_set_priority() 함수를 수정 */

void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	thread_current()->init_priority = new_priority;

	/* refresh_priority() 함수를 사용하여 우선순위를 변경으로 인한 donation 관련 정보를 갱신
       donation_priority(), test_max_pariority() 함수를 사용하여 priority donation 을 수행하고 스케줄링 */

	if (!list_empty(&thread_current()->donations)){
		refresh_priority();
		donate_priority();
	}
	test_max_priority();
}

 

과제 2-2 (Priority Scheduling)

- 과제 2-1에서 수행한 Pintos Scheduler의 Priority 기준으로 FIFO로 구현이 되어있으나,
- 여러 thread들이 CPU 수행을 기다리고 있을 경우 우선순위가 높은 thread가 CPU를 먼저 점유

솔루션

 

priority scheduling 

주요 수정 및 추가 함수

/* semaphore를 반환하고 value를 1 높임 */
void sema_down (struct semaphore *sema)

/* semaphore를 요청하고 획득했을 때 value를 1 낮춤 */
void sema_up (struct semaphore *sema)

/* condition variable을 통해 signal이 오는지 기림 */
void cond_wait (struct condition *cond, struct lock *lock)

/* condition variable에서 기다리는 가장높은 우선순위의 스레드에 signal을 보냄 */
void cond_signal (struct condition *cond, struct lock *lock UNUSED)

/* 첫번째 인자로 주어진 세마포어를 위해 대기 중인 가장 높은 우선순위의 스레드와 
   두번째 인자로 주어진 세마포어를 위해 대기 중인 가장 높은 우선순위의 스레드와 비교 */
bool cmp_sem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)

 

/* semapore를 요청하고 획득했을 때 value를 1 낮춤  */
/* (자원획득). SEMA 값이 양수가 되기를 기다리고 양수가되면 감소시킴. */

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);
	ASSERT (!intr_context ());
	
	old_level = intr_disable ();
	//sema값이 0인동안(자원이 없는동안) 현재thread를 waiters에 넣고 상태를 block으로 바꿈 
	//그리고 while문 반복되는 동안 계속해서 ready_list에서 하나 꺼내서 running
	while (sema->value == 0) {	 
		list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_priority, NULL); // ***
		thread_block ();	//자원이 없으면 block으로 상태바꾸고 schedule(), ???
	}						// block인 상태로 대기(?)
	sema->value--;
	intr_set_level (old_level);
}

 

/* semaphore를 반환하고 value를 1 높임 */
/* (자원반납). SEMA의 값을 증가시키고 SEMA를 기다리는 쓰레드 중(있는 경우) 하나의 스레드를 깨운다. */

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters)){
		//waiters_list에 (block된) thread가 있으면
		/* 스레드가 waiters list에 있는 동안 우선순위가 변경 되었을 경우를 고려 하여 waiters list 를 우선순위로 정렬 한다. */
		list_sort(&sema->waiters, cmp_priority, NULL);	// aux ???
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}	
	sema->value++;

	/* priority preemption 코드 추가*/
	thread_yield();	// ***

	intr_set_level (old_level);
}

 

/* condition variable을 통해 signal이 오는지 기다림 */

void
cond_wait (struct condition *cond, struct lock *lock) {
	struct semaphore_elem waiter;

	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	sema_init (&waiter.semaphore, 0);
	list_insert_ordered(&cond->waiters, &waiter.elem, cmp_sem_priority, NULL);	// ***
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

 

/* condition variable에서 기다리는 가장 높은 우선순위의 스레드에 signal을 보냄(즉, sema_up으로 깨우기) */
/* condition variable의 waiters list를 우선순위로 재정렬 */

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	ASSERT (cond != NULL);
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (lock_held_by_current_thread (lock));

	if (!list_empty (&cond->waiters)) {
		list_sort(&cond->waiters, cmp_sem_priority, NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

 

/* 첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 높으면 1을 반환 낮으면 0을 반환 */

bool cmp_sem_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
	struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
	struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);

	struct list* la = &sa->semaphore.waiters;
	struct list* lb = &sb->semaphore.waiters;
	struct list_elem *begin_a=list_begin(la);
	struct list_elem *begin_b=list_begin(lb);

	struct thread *ta = list_entry(begin_a, struct thread, elem);
	struct thread *tb = list_entry(begin_b, struct thread, elem);

	return ta->priority > tb->priority;
}

 

 

과제 2-3 (Priority Inversion Problem)

- 우선순위가 높은 스레드가 우선순위가 낮은 스레드를 기다리는 현상

priority inversion

솔루션

- Priority Donation : 낮은 우선순위의 thread에게 자신의 우선순위를 기부
- Multiple Donation : thread가 두개 이상의 lock을 보유시, 각 lock에 의해 donation을 발생시킴
- Nested Donation : lock을 점유하고 있지만 우선순위가 낮은 thread 들에게 높은 thread가 자신의 우선순위를 donation

priority donation

 

multiple donation _ 팀원 자료

 

nested donation _ 팀원자료

주요 수정 및 추가 함수

/* lock을 점유하고 있는 스레드와 요청 하는 스레드의 우선순위를 비교하여 priority donation을 수행하도록 수정 */
void lock_acquire (struct lock *lock)

/* donation list 에서 스레드를 제거하고 우선순위를 다시 계산하도록 remove_with_lock(), refresh_prioriy() 함수를 호출 */
void lock_release (struct lock *lock)

/* 스레드 우선순위 변경시 donation의 발생을 확인 하고 우선순위 변경을 위해 donation_priority()함수 추가 */
void thread_set_priority (int new_priority)

/* priority donation을 수행 */
void donate_priority(void)

/* donation list에서 스레드 엔트리를 제거 */
void remove_with_lock(struct lock *lock)

/* 우선순위를 다시 계산 */
void refresh_priority(void)

 

/* lock을 요청 */

void
lock_acquire (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (!intr_context ());
	ASSERT (!lock_held_by_current_thread (lock));

	if (lock->holder){  // 해당 lock의 holder가 존재한다면 아래 작업을 수행

		/* 현재 thread의 wait_on_lock 변수에 획득하기를 기다리는 lock 주소를 저장 */
		/* lock holder의 donations에 현재 running 중인 thread의 donation_elem을 삽입 */
		/* priority donation을 수행하기 위해 donate_priority() 함수를 호출 */
		thread_current()->wait_on_lock = lock;
		list_insert_ordered(&lock->holder->donations, &thread_current()->donation_elem, cmp_dom_priority, NULL);
		donate_priority();
	}

	sema_down (&lock->semaphore);
	thread_current()->wait_on_lock = NULL;

	/* Lock을 획득한 후 lock holder를 갱신함 */
	lock->holder = thread_current ();
}

 

/* lock을 반환 */

void
lock_release (struct lock *lock) {
	ASSERT (lock != NULL);
	ASSERT (lock_held_by_current_thread (lock)); // current_thread가 lock이어야 통과

	lock->holder = NULL;

	remove_with_lock(lock);
	refresh_priority();


	sema_up (&lock->semaphore);
}

 

/* 스레드의 우선순위가 변경되었을 때 우선순위에 따라 ready_list의 우선순위와 비교하여 스케줄링(preempted) */
/* donation을 고려하여 thread_set_priority() 함수를 수정 */

void thread_set_priority(int new_priority)
{
	thread_current()->priority = new_priority;
	thread_current()->init_priority = new_priority;

	/* refresh_priority() 함수를 사용하여 우선순위를 변경으로 인한 donation 관련 정보를 갱신
       donation_priority(), test_max_pariority() 함수를 사용하여 priority donation 을 수행하고 스케줄링 */

	if (!list_empty(&thread_current()->donations)){
		refresh_priority();
		donate_priority();
	}
	test_max_priority();
}

 

/* priority donation을 수행하는 함수를 구현 */

void donate_priority(void)
{
	/* 현재 스레드가 기다리고 있는 lock과 연결된 모든 스레드들을 순회하며, 
	   현재 스레드의 우선순위를 lock을 보유하고 있는 스레드에게 기부 
	   (Nested donation 그림 참고, nested depth 는 8로 제한) */
	struct thread *cur = thread_current();
	struct lock *cur_lock = cur->wait_on_lock;

	for (int i=0; i < 8; i++){
		if (cur_lock == NULL){ // cur->wait_on_lock이 없을시 break
			break;
		}
		else {
			if(cur->priority > cur_lock->holder->priority)
			{
				cur_lock->holder->priority = cur->priority;
			}
		cur = cur_lock->holder;
		cur_lock = cur->wait_on_lock;
		}

	}
}

 

/* lock을 해지 했을때 donations 리스트에서 해당 엔트리를 삭제 하기 위한 함수를 구현 */

void remove_with_lock(struct lock *lock){
	/* 현재 스레드의 donations 리스트를 확인하여 해지 할 lock 을 보유하고 있는 엔트리(그룹)를 삭제 */
	struct thread *cur = thread_current(); 		
	struct list *cur_don = &cur->donations;
	struct list_elem *e; 

	if (!list_empty(cur_don)){
		for (e = list_begin(cur_don); e != list_end(cur_don); e = list_next(e)){ // 순회
			struct thread *e_cur = list_entry(e, struct thread, donation_elem);
			if (lock == e_cur->wait_on_lock){ // 해당 Lock과 연관되어 있는 모든 thread를 donation에서 삭제함
				list_remove(&e_cur->donation_elem); 
			}
		}
	}
}

 

/* 스레드의 우선순위가 변경 되었을때 donation을 고려하여 우선순위를 다시 결정하는 함수를 작성 */

void refresh_priority(void){
	/* 현재 스레드의 우선순위를 기부받기 전의 우선순위로 변경 */
	struct thread *cur = thread_current();
	cur->priority = cur->init_priority;

	/* 가장 우선순위가 높은 donation List의 thread와
	   현재 thread의 우선순위를 비교하여 높은 값을 현재 thread의 우선순위로 설정 */
	if (list_empty(&cur->donations)) return;
	struct list_elem *first_don = list_begin(&cur->donations);
	struct thread *first_thread = list_entry(first_don, struct thread, donation_elem);

	if (first_thread->priority > cur->priority){
		cur->priority = first_thread->priority;
	}
}

 

3. 느꼈던 것


3번 (Advanced)까지 구현하고 싶었고 계획대로 진행되고 있었으나
생각지못한 버그를 만나 3을 제대로 구현해보지 못한 점이 아쉬웠다.
코치님 말씀대로 공부로 빠졌으면 제시간에 구현 못했을 것 같다.

팀원들과 함께여서 어려운 과정임에도 많이 배우고 공부해나가며 코드 구현을 해볼 수 있었다.
모르는 개념을 그리고 토론하고 코드로 구현해보는 과정을 거치며 길고도 짧은 1주일을 보낸 것 같다.
그리고 코드를 직접 구현하면서 Pintos는 하드웨어를 모르면 제대로 이해할 수 없다는 것이 몸소 이해가 되었다.

1주일동안 새로운 지식을 습득하고 코드를 구현한다고 밤도 새고 머리를 꽤나 썼지만 또 그만큼 성장한 것이 아닐까라는 생각이 든다.
특히 이번주차에는 디버깅을 조금 더 많이 해보고 싶었는데 버그를 찾아내느라 C 언어 디버깅 툴을 도움이 될만큼 사용해본 것 같아
소기의 목적을 달성해낸 것 같다.

다가올 Pintos 2주차도 팀원들과 협력해서 좋은 결과를 만들어 내야겠다 😊

4. 참고자료

- Georgia Tech OS 강의
- CSAPP : 3장, 8장, 12장
- Operating Systems : Three Easy Pieces - Lock, Semaphore, Condition Variable
- KOCW 이화여대 반효경 교수님 강의
- 혼자공부하는 컴퓨터 구조 + 운영체제
- 각종 블로그 등

팀원들의 블로그 자료 공유
https://sappire-9.tistory.com/7

'Review > SW Jungle' 카테고리의 다른 글

[WEEK10] Pintos _ Project2 User Program (2) System Calls  (0) 2022.11.29
[WEEK09] Pintos _ Project2 User Program (1) Argument Passing  (0) 2022.11.29
[WEEK05~07] 복기와 공부한 것들  (0) 2022.11.14
[WEEK04] 다이나믹 프로그래밍 & 4주차 복기  (4) 2022.10.30
[WEEK03] 서로소 집합 자료구조  (1) 2022.10.13

관련글

티스토리툴바