CPU Scheduling
CPU 자원을 최대한 효율적으로 사용하여 최대한의 퍼포먼스를 내기위해 사용하는 방법을 말합니다. 단위 시간 당 많은 일을 하고 완료시키고, CPU 이용률을 높이는 노력을 합니다.
시간 관련 척도(응답시간, 대기시간, 소요시간)를 기준으로 사용합니다.
Priority Scheduling
CPU 점유를 하는 방법에는 Preemptive(선점형) / Non-Preemptive(비선점형)로 나뉘어집니다.
선점형은 우선순위가 더 높은 프로세스가 들어오면 CPU를 뺏어서 주는 방식
비선점형은 아무리 높은 우선순위를 갖는 CPU가 들어와도 완료하기 전까지는 CPU를 넘겨주지 않는 방식 입니다.
기존 Pintos에 구현된 스케쥴링 방식은 라운드 로빈이지만
더 높은 우선순위를 갖는 스레드가 들어와도 cpu를 빼앗기지 않는 비선점형으로 구현되어 있습니다.
더 높은 우선순위를 갖는 스레드가 생성된다면 CPU를 점유할 수 있도록 하고
기존에 실행중인 우선순위가 낮은 스레드는 ready_list에 다시 넣어줍니다.
Synchronization
Pintos에서 위의 문제를 해결하면 추가적으로 해야될 것이 발생하게 됩니다.
공유자원 사용을 위해 Semaphore를 대기 하고 있는 스레드들의 list인 waiters가 FIFO로 구현되어 있습니다.
그래서 waiters에 들어온 순서대로 Lock을 획득하게 되어 우선순위에 따른 Lock을 획득하지 않습니다.
Semaphore를 요청 할때 waiters를 위의 그림과 같이 우선순위 순서로 정렬 해야합니다.
여러 스레드가 lock, semaphore, condition variable 을 얻기 위해 기다릴 경우
우선순위가 가장 높은 thread가 CPU를 점유 하도록 구현해야 됩니다.
Priority inversion Problem
Pintos에서 위의 문제를 해결하면 추가적으로 해야될 것이 발생하게 됩니다.
우선순위가 T3,T2,T1(숫자가 높을 수록 우선순위가 높다고 가정)인 스레드가 있다고 가정할때
우선순위가 가장 낮은 스레드인 T1이 실행하다가 우선순위가 가장 높은 스레드 T3 생성되었습니다.
T3는 T1의 실행이 완료되어야 실행 될 수 있다고 할 때 기다려야 합니다.
실행중인 T1보다 우선순위가 높은 스레드 T2가 생성되면 실행중인 스레드 T1은 CPU를 반납하는 현상이 생깁니다. 우선순위가 가장 높은 T3는 T1에 의존적이기에 실행하지 못하지만 T2는 의존적이지 않기 때문에
T3보다 먼저 실행되는 Priority inversion Problem 발생하게 됩니다.
Priority Donation
이 문제를 해결하기 위해서 우선순위가 낮은 스레드 T1에게 T3의 우선순위를 부여하는 Priority Donation 을 해주어서 T2가 먼저 실행되지 않도록 이 문제를 해결합니다.
