Priority Scheduling
목표
- 현재 pintos의 스케줄러는 라운드 로빈으로 구현되어 있다. 이를 우선순위를 고려하여 스케줄링 하도록 수정한다.
- Ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인 thread의 우
선순위보다 높으면, 기존 thread를 밀어내고 CPU를 점유하도록 한다 - 여러 thread가 lock, semaphore 를 얻기 위해 기다릴 경우 우선순위가 가장 높은
thread가 CPU를 점유 한다
라운드 로빈이란?
라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘 이다. 시간 할당량(time_quantum) 또는 시간 조각(time slice)라고 하는 작은 단위의 시간을 정의한다. 시간 할당량은 일반적으로 10 ~ 100ms 이다.
준비 완료 큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 완료 큐를 돌면서 한 번에 한 프로세스에게 한 번의 시간 할당량 동안 CPU를 할당한다.
핀토스에서의 우선순위
PRI_MIN(=0) 부터 PRI_MAX(=63)까지의 범위를 가지며 숫자가 클수록 우선순위가 높음.
thread_create() 함수로 thread를 생성할 때 인자로 초기 우선순위를 전달(기본 값으로 PRI_DEFAULT(=31))
💻 구현하기
1. 구현할 함수 선언
2. thread_create() 함수 수정
- Thread의 ready_list 삽입 시 현재 실행중인 thread와 우선순위를 비교하여, 새로 생성된 thread의 우선순위가 높다면 thread_yield()를 통해 CPU를 양보.
3. thread_unblock() 함수 수정
- Thread가 unblock 될때 우선순위 순으로 정렬 되어 ready_list에 삽입되도록 수정
4. thread_yield() 함수 수정
- 현재 thread가 CPU를 양보하여 ready_list에 삽입 될 때 우선순위 순서로 정렬되어
삽입 되도록 수정
5. thread_set_priority()함수 수정
6. test_max_priority()함수 추가
7. cmp_priority() 함수 추가
- 첫 번째 인자의 우선순위가 높으면 1을 반환, 두 번째 인자의 우선순위가 높으면 0을 반환
- list_insert_ordered() 함수에서 사용
결과
Priority Scheduling and Synchronization
목표
- 여러 스레드가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유 하도록 구현
- 현재 pintos는 semaphore를 대기 하고 있는 스레드들의 list인 waiters가 FIFO로 구현되어 있다.
현재 상황
- 우선순위를 무시하고 waiters list에 삽입되는 순서대로 lock을 획득
해결책
- Semaphore를 요청 할때 대기 리스트를 우선순위로 정렬
- sema_down()에서 waiters list를 우선순위로 정렬 하도록 수정
💻 구현하기
1. sema_down() 함수 수정
- Semaphore를 얻고 waiters 리스트 삽입 시, 우선순위대로 삽입되도록 수정
2. sema_up() 함수 수정
3. 구현할 함수 선언
4. cmp_sem_priority() 함수 추가
- 첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 높으면 1을 반환 낮으면 0을
반환
5. cond_wait() 함수 수정
- condition variable의 waiters list에 우선순위 순서로 삽입되도록 수정
6. cond_signal() 함수 수정
- condition variable의 waiters list를 우선순위로 재 정열
- 대기 중에 우선순위가 변경되었을 가능성이 있음
결과
