오버뷰

크게 해야할 것

1. Ready_list를 우선순위 순으로 정렬하여서, running thread를 결정하는 기준이 각 스레드의 우선순위가 되도록.
2. synchronization의 구현 요소에 대한 Wait_list를 우선순위 순으로 정렬.
3. 우선순위가 높은 쓰레드가 낮은 쓰레드를 기다리고 있는 Priority Inversion을 예방하기 위해서 Priority Donation 구현

Priority Scheduling

해야할 것

• ready_list에서 run할 쓰레드를 고를때, 최고 우선순위를 가진 쓰레드를 pick
  - 만약 ready_list에 새로운 쓰레드가 들어오면, 현재 running 중인 쓰레드와 비교해서 preemption(선점) 진행.

사용 자료구조

• CPU를 기다리는 ready_list

실제 사용 함수

젤 중요한 test_max_priority()

readylist에서 제일 우선순위 큰 쓰레드의 우선순위 값과, 현재 running 쓰레드의 우선순위를 **비교하여서 CPU를 할당_**

cmp_priority()

정렬 혹은 삽입시에, 두 쓰레드의 우선순위를 비교하는 함수.

1. thread_create

• 새로이 생성된 쓰레드가 thread_unblock 을 통해서 run queue에 들어간 이후, 바로 test_max_priority
  를 통해서 running 쓰레드와 우선순위를 비교하여서 필요시 선점을 진행.

2. thread_unblock

• blocked(sleep 중이던) 쓰레드가 unblock되어서 ready_list에 들어갈때, 우선순위 순으로 삽입될 수 있게 해주면 됨.

3. thread_yield

• running 쓰레드가 CPU를 넘겨주고 다시 ready_list에 들어갈때(sleep하러 가는 것이 아님!), ready_list에 우선순위 순으로 삽입될 수 있게 해준다.

4. thread_set_priority

현재 쓰레드의 우선순위를 재지정할 때, test_max_priority 를 통하여서 running 쓰레드와 ready_list의 가장 큰 값을 비교하여 필요시 선점을 진행.

실제로 스레드의 삽입을 책임지는 do_schedule과 schedule 함수

do_schedule(int status)

1. 삭제 요청 큐에 있는 쓰레드들(이미 죽기로 확정돼 있는) 을 지움
2. 현재 쓰레드의 상태를 인자로 들어온 status로 바꾼다. -> 메모리 확보 위함
3. schedule() 호출

schedule()

• running 쓰레드를 그 다음 쓰레드(ready_list의 맨 앞)으로 변경한다.

Synchronization primitive

해야할 것

• synchronization 구현 요소(락..) 을 기다리는 쓰레드들 중 하나를 선택할때, 최고 우선순위를 가진 스레드를 선택.

사용 Primitive

• condition variable & lock
• semaphore

condition variable, lock, semaphore 이 셋이 무슨 관계인가요??

• condition variable은 특정 조건이 도달할때까지 스레드를 기다리게 합니다.

• 이때 lock을 사용해서 condition variable의 기다리는 리스트인 waiters배열에 접근이 가능

• 이때 waiters 배열 안의 쓰레드를 잠재우기 위해서 semaphore를 사용

• 이것이 cond_wait과 cond_signal이 하는 일

이를 도식화해서 나타내면 다음과 같다