[PintOS] 1-2 Priority Scheduler, Priority Donation

GIT

[thread.c, thread.h, synch.c, synch.h]

 

이론 영상 출처 : https://www.youtube.com/watch?v=myO2bs5LMak

---

1. Priority scheduler

Why Priority Scheduler ?

- Alarm Clock에서는 tick 단위로 실행 thread 관리, sleep & wake 상태로 thread 실행 관리
- FIFO 방식이므로 thread의 중요도를 고려하지 않는 한계

=> thread에 priority 요소를 추가하여, 우선순위를 고려한 scheduling을 하고자 함

- 우선순위를 고려한다는 것은, priority라는 요소를 struct thread에 추가한다는 것
 - 기존의 ready_list에 thread를 insert 할 때, priority로 정렬해서 넣어야 할 것
  - 현재 running thread에 비해, ready_list에 더 높은 우선순위인 thread가 있다면 CPU 점유를 양보해야 함

 

- ready list를 우선순위 정렬할 것
- wait list를 동기화 인자로 정렬할 것 (semaphore, condition variable)
- preemption 구현할 것 (강제적 선점 : yield()와 다르게, 강제적으로 다른 프로세스에게 CPU 할당)
- preemption은 timer interrupt가 호출될 때마다 동작하는 게 아니고, ready list에 삽입 시 동작)

- PintOS 우선순위 범위는 0 ~ 63 (높을수록 우선순위 높은 것)
- 쓰레드가 생성될 때 priority를 부여하며, 기본 할당 priority = 31

- thread_create() : 쓰레드 생성 함수, 이 때 기본 우선순위 부여
- thread_set_priority(int new priority) : 현재 실행 중인 쓰레드의 우선순위 변경
- thread_get_priority() : 현재 쓰레드의 우선순위 반환

 

thread_create() 구현 시 주의사항

 

* tid_t thread_create(const char *name, int priority, thread_func *function, void *aux)

- 쓰레드를 생성하고 ready_list에 넣을 때, list 내부의 쓰레드들과 우선순위 비교하여 배치해야 함
  -> 이 과정은 cost가 많이 드는 동작
  
- ready_list에 쓰레드를 넣으면, 현재 CPU를 사용 중인 쓰레드와 우선순위 비교
- 만약 새로 ready_list에 넣은 쓰레드가 현재 CPU를 사용 중인 쓰레드보다 우선순위가 높다면, 
  schedule() 사용하여 context switching 발생시킴

 

수정해야 하는 함수

1. void thread_unblock(struct thread *t)

   0) 쓰레드가 생성되면 block 상태 (실행 불가능 상태, ready_list에도 못들어감)
   1) 쓰레드의 상태를 준비 상태로 변경하고, 우선순위를 고려하여 ready_list에 삽입

2. void thread_yield(void)
	 
if 현재 CPU를 사용하는 쓰레드(current thread) 의 우선순위 < ready_list에 삽입된 새로운 쓰레드 :
   current thread는 yield() 호출
   -> ready_list에서 우선순위가 더 높은 thread가 실행되고, current thread는 ready_list 삽입
	 
3. void thread_set_priority(int new_priority)
	
   current thread의 우선순위 변경
   -> ready_list에서, 변경된 current thread의 우선순위보다 높은 게 있는지 탐색
   --> 혹시나 존재한다면, context switching

 

Hint : thread_unblock()

 

- thread_unblock()
  unblock() 함수를 사용할 때, list_push_back 사용 대신 list_insert_ordered 사용해라
	
- 기존 함수에서는, block 상태의 쓰레드를 (우선순위 고려 없이) ready_list의 맨 뒤로 넣었다
- block 상태의 쓰레드를, 우선순위 고려하여 ready_list에 삽입하는 동작으로 수정하라

 

 

---

2. Priority donation

 

Why Priority donation ?

- Thread가 공유자원에 접근한다면, race condition이 발생할 가능성이 있음
 - 지금까지 구현한 priority scheduler는 이를 방지할 수단이 없는 상태
  - 같은 공유자원에 접근하고자 하는 thread가 존재한다는 가정 하에, 동기화를 통해 문제를 방지할 수 있음

 

Priority Inversion

** Priority Inversion

   낮은 우선순위의 쓰레드가 Lock을 획득한 상태에서, 높은 우선순위의 쓰레드가 동일한 lock을 요청하면
   높은 우선순위 쓰레드는 낮은 우선순위 쓰레드가 lock을 해제할 때까지 기다려야 함
	 
   중간 우선순위 쓰레드가 CPU를 할당받아 실행되면서 낮은 우선순위 쓰레드를 간섭하게 되면
   높은 우선순위 쓰레드가 계속 대기하는 '우선순위 역전' 현상이 발생
	 
   -> 중간 우선순위 쓰레드가 올바르지 않은 CPU 스케줄링에 의해 실행되어버린 상태
	 
   -> 우선순위 상속 프로토콜 등의 기법으로 해결 가능 (Priority Donation)

 

Priority Donation

** Priority Donation

   낮은 우선순위 쓰레드가 Lock을 획득한 상태에서, 높은 우선순위의 쓰레드가 동일한 lock을 요청하면
   높은 우선순위 쓰레드는 낮은 우선순위 쓰레드가 lock을 해제할 때까지 기다려야 함
	 
   중간 우선순위 쓰레드가 CPU를 할당받아 실행되면서 낮은 우선순위 쓰레드를 간섭할 수 있을 때,
   낮은 우선순위 쓰레드의 우선순위를 높은 우선순위 쓰레드의 우선순위로 일시적 상향 조정 한다.
	 
   낮은 우선순위 쓰레드의 lock이 해제되면, 낮은 우선순위 쓰레드의 우선순위는 기존으로 돌아간다.

 

---

** Lock

Definition :

	Multithread 환경에서 공유 자원에 대한 접근을 제어하기 위해 사용되는 동기화 메커니즘
	한 번에 하나의 쓰레드만 공유 자원에 접근할 수 있도록 보장
	=> race condition 방지

Function :

	Lock은 2개의 상태로 분류 (Locked, Unlocked)
	쓰레드는 공유 자원에 접근하기 전에 Lock을 획득(Acquire) 해야 함
	Lock이 Unlocked 상태 : 쓰레드가 Lock을 획득할 수 있는 상태
	
	쓰레드가 공유 자원에 대한 작업을 완료하면 락을 해제(Release)해야함
	Lock이 다른 쓰레드에 의해 획득된 상태라면, Lock을 요청한 쓰레드는 대기
	
Type :
	
    Mutex : 상호 배제를 보장하는 Lock
            한 번에 하나의 쓰레드만 뮤텍스 획득 가능
            뮤텍스 소유한 쓰레드만 공유 자원에 접근 가능
					
   Semaphore : 
		
        1) Binary Semaphore : 뮤텍스와 유사하게, 공유 자원에 대한 접근 제어
        2) Counting Semaphore : 공유 자원에 대한 여러 쓰레드의 접근을 관리
		
   Reader-Writer Lock : 읽기, 쓰기 작업을 구분하여 쓰레드 관리
                        읽는 쓰레드는 동시에 진행 가능
                        쓰기 쓰레드는 배타적으로 진행토록 관리
											 
Caution :

    Deadlock : 두 개 이상의 쓰레드가 서로 lock을 획득하기 위해 무한히 대기하는 상황
               -> lock 획득 순서를 일관되게 유지, 불필요한 lock 획득 방지해야 함
						 
    Livelock : 쓰레드들이 lock을 획득하기 위해 계속 시도하지만, 서로 양보하는 상황
               -> lock 획득 시도 횟수를 제한하여 방지
						 
    Overhead : Lock 획득과 해제가 잦아질 경우 성능 저하가 발생

 

우선순위를 고려하지 않은 lock/release 흐름도

우선순위를 고려한 lock/release 흐름도

 

Semaphore in pintOS

 

1. void sema_init(struct semaphore *sema, unsigned value)
	 
	 semaphore 초기화하는 함수
	 sema : 초기화할 세마포어 구조체의 포인터
	 value : 세마포어의 초기 값, 세마포어가 가질 수 있는 리소스의 개수
	 
	 세마포어의 초기 값 설정, 대기열 초기화
	 
2. void sema_down(struct semaphore *sema)
	 
	 세마포어에서 리소스를 획득하는 함수
	 세마포어의 값이 0보다 클 때 :
		 세마포어의 값을 1 감소시키고 함수 반환 -> 리소스 성공적으로 획득한 것
	 세마포어의 값이 0일 때 :
		 현재 쓰레드는 세마포어의 대기열에 추가되고 block 상태가 됨
	 대기 중인 쓰레드 : 세마포어의 값이 증가할 때 깨어나서 리소스 획득
	 
3. void sema_up(struct semaphore *sema)

	 세마포어에서 리소스를 해제하는 함수
	 세마포어의 값을 1 증가시키고 함수 반환 -> 리소스 성공적으로 해제한 것
	 세마포어 대기열에 대기 중인 쓰레드가 있다면, 해당 쓰레드를 실행 가능 상태로 변경

4. cond_wait(struct condition *cond, struct lock *lock)

	 조건 변수를 사용하여 쓰레드를 대기시키는 함수
	 cond : 대기할 조건 변수 구조체의 포인터
	 lock : 조건 변수와 연관된 락 구조체의 포인터

	 현재 쓰레드는 조건 변수의 대기열에 추가됨 (block 상태)
	 다른 쓰레드에서 조건 변수를 시그널링 하면, 대기 중인 쓰레드는 깨어나서 실행 재개
	 

** 여기서 sema_down(), sema_up() 수정해야 함

 

 

1. struct lock
	
	1) struct thread *holder
		 현재 lock을 소유하고 있는 쓰레드를 가리키는 포인터
	2) struct semaphore semaphore
		 lock의 동작을 제어하는 데 사용되는 binary semaphore
		 binary semaphore 방식으로 락의 획득과 해제 관리

2. void lock_init(struct lock *lock)

	 lock 구조체 초기화, 세마포어 초기화
	 
3. void lock_acquire(struct lock *lock)

	 lock 획득하는 함수
	 세마포어를 사용하여 락을 요청하고, 락이 해제될 때까지 쓰레드 block으로 유지
	 lock 획득한 쓰레드는 임계영역에 진입 (공유 자원에 접근)

4. void lock_release(struct lock *lock)

	 lock 해제하는 함수
	 세마포어를 사용하여 lock을 해제하고, 대기 중인 다른 쓰레드가 lock을 획득할 수 있게 함

 

 

1. void cond_init(struct condition *cond)
	 
	 주어진 condition 변수를 초기화
	 condition 변수의 대기 중인 쓰레드 리스트 초기화
	 
2. void cond_wait(struct condition *cond, struct lock *lock)

	 현재 쓰레드를 condition 변수에 연결된 대기 중인 쓰레드 리스트에 추가, 시그널 대기
	 a) 현재 쓰레드를 condition 변수의 대기 중인 쓰레드 리스트에 추가
	 b) lock을 해제하여 다른 쓰레드가 공유 자원에 접근할 수 있도록 함
	 c) 시그널을 받을 때까지 현재 쓰레드를 대기 상태로 만듬
	 d) 시그널을 받으면 lock을 다시 획득한 후 함수에서 반환
	 
3. void cond_signal(struct condition *cond, struct lock *lock UNUSED)

	 condition 변수에서 대기 중인 쓰레드 중 가장 높은 우선순위를 가진 쓰레드에게 시그널 송출
	 a) condition 변수의 대기 중인 쓰레드 중 가장 높은 우선순위를 가진 쓰레드 선택
	 b) 선택된 쓰레드에게 시그널 송출 -> 대기 상태에서 wake up 시킴
	 c) 시그널을 받은 쓰레드는 lock 획득 -> 실행 재개
	 
4. void cond_broadcast(struct condition *cond, struct lock *lock)

	 condition 변수에서 대기 중인 모든 쓰레드에게 시그널 송출
	 a) condition 변수의 대기 중인 쓰레드 리스트에 있는 모든 쓰레드에게 시그널 송출
	 b) 시그널을 받은 모든 쓰레드는 대기 상태에서 wake up
	 c) 각 쓰레드는 lock을 획득하고 실행 재개

 

** condition variable

Definition :

	쓰레드 간의 통신과 동기화를 위해 사용되는 동기화 도구
	특정 조건이 만족될 때까지 쓰레드를 대기시키고, 조건이 충족되면 대기 중인 쓰레드에게 시그널 송출

Reason :

	1. 쓰레드 간의 통신
		 한 쓰레드에서 다른 쓰레드로 특정 조건이 만족되었음을 알릴 수 있다
		 condition 변수를 통해 쓰레드 간 통신 가능

	2. 자원 공유
		 여러 쓰레드가 공유 자원에 접근할 때, condition 변수를 통해 쓰레드 간 race condition 방지
		 공유 자원 사용이 가능함을 판단할 수 있게 해주는 변수가 condition 변수
		 
	3. 효율적 대기
	
		 쓰레드가 비효율적인 busy-waiting 상태에 진입하지 않게 할 수 있다
		 쓰레드는 조건이 만족될 때까지 대기 상태를 유지하고, 조건이 만족해서 시그널을 받으면 실행 재개

 

Need to Modify

- 쓰레드를 wait_list에 삽입하는 동작

1. void sema_down(struct semaphord *sema)
2. void cond_wait(struct condition *cond, struct lock *lock)

- wait_list를 정렬 하는 동작

1. void sema_up(struct semaphore *sema)
2. void cond_signal(struct condition *cond, struct lock *lock UNUSED)


==> wait_list에 삽입할 때도 우선순위를 고려하여 리스트에 넣기
    wait_list를 정렬할 때도 우선순위를 고려하여 정렬하기

 

+ Nested donation, Multiple donation은 따로 정리 X !

 

- Nested donation

  * donation 시, wait_on_lock <-> holder priority 비교 및 연쇄 donation이 잘 이루어지는가 ?
  
- Multiple donation

  * donation 시, thread->donations list 삽입 및 제거 과정이 잘 이루어지는가 ?

---

3. 마주한 문제

 

1) original_priority

lock_release 이후, donation 받은 thread는 본래 자신의 priority로 돌아가야 함
해당 동작을 위해 struct thread에, original_priority라는 필드를 추가함

thread_set_priority() 함수에서, original_priority도 new_priority로 변경해줘야 함
-> 해당 함수는 테스트 코드에서 호출하는 함수로, 특정 thread의 priority를 설정하는 동작이기 때문에
--> 또한 priority 변경 이후, preemption() 호출을 통해 update된 priority의 비교 및 후속 동작을 준비


2) multiple donation -> struct thread *donations !!!!!!!!!!

donations list를 평가하는 multiple 테스트에서, 자꾸 실패함
처음에는 'lock_release() 함수에서 donations list에서 제거를 제대로 못하나?' 생각
printf로 확인을 해보니, donations list에 삽입이 아예 안되는 것을 확인함

'donations list에 삽입' 동작이 포함된 다른 함수들이 잘못된 줄 알고 이리저리 고치다 보니, 성공한 테스트들도 실패함

문제는 thread.h 파일 내의 struct thread 정의하는 부분에서, donations list 선언 부분이였음
배열인 donations 앞에 *를 붙이는 바람에, 지금까지 donations list에 삽입하는 게 아닌 donations 배열의 
주소값에 thread->d_elem을 넣고 있었다고 생각함 ...

-> struct thread의 donations 앞에 *를 제거하니까, 문제 해결


3) sema_up()

sema_up() 안의 thread_unblock() 이전에 &sema->waiters list를 sort 해줘야 함