[pintOS] Project1-3. Priority Scheduling and Synchronization

📅 기간 : 2021.02.06(토) ~ 2021.02.08(월)

1. 과제 목표

여러 스레드가 lock, semaphore, condition variable 을 얻기 위해 기다릴 경우, 우선순위가 가장 높은 thread가 CPU를 점유 하도록 구현하자!
현재 pintos는 semaphore를 대기 하고 있는 스레드들의 list인 waiters가 FIFO로 구현되어있다. 이를 수정해주자.

현재 상황

목표

2. 배경지식

💡 세마포어, 락

여러 스레드가 자원을 공유할 때, 서로 겹치는 일이 없어야한다. 이런 일을 관리하기 위해 우리는 세마포어, 락 이라는 도구를 이용한다.

* 세마포어

struct semaphore {
	unsigned value;
	struct list waiters;
};

• value : 자원을 점유하고 있는 스레드가 있는지 알려주는 값 (0이면 점유 중, 1이면 사용가능)

• waiters : 해당 자원을 점유하기위해 대기하고 있는 스레드들의 목록
  (현재 핀토스에서는 이 waiter에 FIFO로 들어가는데, 이를 우선순위순으로 들어가도록 바꿔줘야함)

* Lock

struct lock {
	struct thread *holder;
	struct semaphore semaphore;
};

락은 세마포어인데, 현재 자신을 쥐고 있는 스레드가 누구인지 알고있는 세마포어!
이름표가 달린 세마포어다.
구현 시 주의할 점은, lock은 자신의 holder스레드를 알지만, 스레드 자신은 자신이 어떤 lock을 가지고 있는지 모른다. lock으로부터 스레드로의 접근은 바로 가능하지만, 스레드로부터 lock으로의 접근은 쉽지 않다.

3. 구현

3-1. sema_down, sema_up 함수

• sema_down : 세마포어를 관리하는 함수들에서 waiter에 스레드를 넣어줄때, 우선순위 순으로 넣어주도록 수정한다.
• sema_up : 스레드가 waiter에 있는 동안 우선순위가 변경 되었을 경우를 고려 하여 waiter를 우선순위로 정렬 한다.

3-2. cmp_sem_priority 함수

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

해당 lock을 기다리는 세마포어 리스트를 가장 높은 우선순위를 가지는 스레드의 우선순위 순으로 정렬하도록 구현한다.
첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 높으면 1 반환, 낮으면 0 반환하는 bool 함수로 구현한다.

4. 회고

이때부터 슬슬 어려워지기 시작했다.
세마포어와 lock의 개념이 본격적으로 등장하면서 누가 누굴 가리키고, 누가 누굴 소유하고 마구 헷갈리기 시작했다. 하지만 이건 맛보기에 불과했지..
다음 단계인 Priority donation은 정말.. Lock, 세마포어의 끝판왕이다..

(사진출처 : 핀토스 강의자료)