[Pintos] Priority Scheduling

implement priority scheduling and priority donation in Pintos.

When a thread is added to the ready list that has a higher priority than the currently running thread, the current thread should immediately yield the processor to the new thread.

Similarly, when threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be awakened first. A thread may raise or lower its own priority at any time, but lowering its priority such that it no longer has the highest priority must cause it to immediately yield the CPU.

<aside> 🔥 현재 실행중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 ready list에 추가되면 현재 쓰레드는 즉시 프로세서를 새 쓰레드에게 양보해야합니다.

마찬가지로 쓰레드가 락, 세마포어 또는 조건변수(참고)를 대기할 때, 우선순위가 가장 높은 대기 스레드를 먼저 깨워야합니다. 쓰레드는 언제든지 자신의 우선순위를 올리거나 내릴 수 있지만, 우선순위를 내렸을 때 해당 쓰레드의 우선순위가 가장 높은 우선순위가 아니게 된다면 CPU를 즉시 양보해야 합니다.

</aside>

Thread priorities range from PRI_MIN (0) to PRI_MAX (63). Lower numbers correspond to lower priorities, so that priority 0 is the lowest priority and priority 63 is the highest. The initial thread priority is passed as an argument to thread_create(). If there's no reason to choose another priority, use PRI_DEFAULT (31). The PRI_ macros are defined in threads/thread.h, and you should not change their values.

<aside> 🔥 쓰레드 우선순위의 범위는 PRI_MIN (0) 부터 PRI_MAX (63) 까지입니다. 숫자가 작을수록 우선순위가 낮으므로 우선순위 0이 가장 우선순위가 낮고, 우선순위 63이 가장 우선순위가 높습니다. 초기 쓰레드의 우선순위는 thread_create() 에 대한 인수로 전달됩니다. 이때 다른 우선순위를 선택할 이유가 없으면 PRI_DEFAULT (31) 를 사용하세요. PRI_매크로는 threads/thread.h 에 정의되있고, 이 값들을 변경하면 안됩니다.

</aside>

One issue with priority scheduling is "priority inversion". Consider high, medium, and low priority threads H, M, and L, respectively. If H needs to wait for L (for instance, for a lock held by L), and M is on the ready list, then H will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is for H to "donate" its priority to L while L is holding the lock, then recall the donation once L releases (and thus H acquires) the lock.

<aside> 🔥 우선순위 스케줄링에서 중요한 사항은 “우선순위 역전(priority inversion)”입니다.

우선순위가 높은 쓰레드 H, 중간 M 그리고 낮은 L가 있다고 생각해보세요. 만약 L이 락을 갖고있어서 H가 L을 기다려야하고 M이 ready list에 있다면, H는 절대로 CPU를 사용하지 못할 것입니다. 왜냐면 낮은 우선순위의 스레드가 CPU시간을 얻지 못할 것이기 때문입니다. 이 문제에 대한 부분적으로 해결하는 방법은 L이 락을 갖는 동안 H가 L에게 우선순위를 기부(donate)한 다음, L이 잠금을 해제하면 (따라서 H가 획득) 이 기부를 회수하는 것입니다.

</aside>

Implement priority donation. You will need to account for all different situations in which priority donation is required. Be sure to handle multiple donations, in which multiple priorities are donated to a single thread. You must also handle nested donation: if H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H's priority. If necessary, you may impose a reasonable limit on depth of nested priority donation, such as 8 levels.

<aside> 🔥 우선순위 기부를 구현해봅시다. 우선 우선순위의 기부가 필요한 모든 상황을 고려해야합니다. 하나의 쓰레드에 여러 우선순위가 기부되는 multiple donation 상황을 처리할 수 있어야 합니다. 또한 nested donation 즉 H가 M이 가진 락에서 대기하고있고, M은 L이 가진 락에서 대기하고 있다면 M과 L이 모두 H의 우선순위로 상승해야합니다. 필요하다면 8 단계와 같이 nested priority donation의 깊이에 대해 적당한 제한을 둘 수도 있습니다.

</aside>

You must implement priority donation for locks. You need not implement priority donation for the other Pintos synchronization constructs. You do need to implement priority scheduling in all cases.

Finally, implement the following functions that allow a thread to examine and modify its own priority. Skeletons for these functions are provided in threads/thread.c.

<aside> 🔥 락에 대한 우선순위 기부(priority donation)를 구현해야 합니다. 다른 Pintos 동기화 생성자에 대한 우선순위 기부를 구현할 필요는 없습니다. 모든 경우에서 우선 순위 스케쥴링을 구현해야 합니다. 마지막으로 다음의 함수들을 구현하세요. 이 함수들은 쓰레드가 자신의 우선순위를 검사하고 수정하도록 합니다. 이러한 함수에 대한 골격은 threads/thread.c 에 제공되어 있습니다.

</aside>

void thread_set_priority(int new_priority)

Sets the current thread's priority to new priority. If the current thread no longer has the highest priority, yields.

<aside> 🔥 현재 스레드의 우선순위를 새 우선순위로 설정합니다. 만약 현재 스레드의 우선순위가 더 이상 높지 않으면 우선순위를 양보합니다.

</aside>

void thread_get_priority(int new_priority)

Returns the current thread's priority. In the presence of priority donation, returns the higher (donated) priority.

<aside> 🔥 현재 스레드의 우선순위를 반환합니다. 우선 순위 기부가 있는 경우 더 높은 (기부된) 우선순위를 반환합니다.

</aside>

You need not provide any interface to allow a thread to directly modify other threads' priorities. The priority scheduler is not used in any later project.

<aside> 🔥

스레드가 다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다. 우선순위 스케줄러는 이후 프로젝트에 사용되지 않습니다.

</aside>

 

 

 

 

Scheduler

스레드 스케쥴링 하기 전에는 무조건 인터럽트를 꺼야 함

• 현재는 FCFS = FIFO 방식으로 구현되어있다.

ready_list queue의 맨 앞 만을 뽑아내고 있다

average-waiting time이 매우 길어질 수 있다는 단점이 있다.

convoy effect를 해결하지 못하는 방식이다.

따라서 우선순위 큐 기반 스케쥴링을 진행할 것이다.

• ready_list에 스레드 삽입할 때 우선순위 기반 정렬 삽입.

 

우선순위 기반 선점 스케쥴링

우선순위를 기반으로, ready_list의 맨 앞 스레드의 우선순위가 현재 실행중인 스레드보다 우선순위가 높다면, 선점할 수 있도록 함수를 만든다.

 

정확히는, 우선순위 기반 선점가능한 상태이면

현재 스레드를 방출시킨 후 ready_list에 우선순위 기반 내림차순 순서로 삽입한 뒤

이미 정렬된 ready_list의 맨 앞 요소를 READY에서 RUNNING 상태로 변경하는 것이다.

thread_yield 함수에서 스케쥴링함수를 호출한다

 

 

 

 

기존 thread_yield()에서, 현재 스레드를 ready_list로 방출할 때의 코드

 

 

변경한 코드, 방출 후 ready_list로 삽입할 때, 우선순위를 기반으로 한 내림차순 순서를 지켜 삽입할 수 있도록 한다

compare_thread_prioirty는 스레드의 priority를 비교하는 함수다

 

 

 

임의의 스레드가 ready_list로 옮겨갈 때 선점 가능해질 수 있으므로,

이 때 preemption_by_prioirty() 함수의 호출을 고려할 수 있다.

스레드는 어떤 상황에서, 언제 ready_list에 삽입되는가

• blocked_list 에서 unblock 시켰을 때
  • unblock()
• 스레드 생성 직후
  • thread_create()

 

위와 같은 상황에서 preemption을 고려해야한다.

 

또한

현재 실행중인 스레드의 우선순위를 동적으로 바꿀 때

에도 preemption을 고려해야 한다.

(동적으로 바꾼다? => pintos에서 테스트 할 때 현재 스레드의 우선순위를 동적으로 바꾼다.)

이런 느낌으로 바꾼다.

 

 

따라서 thread_set_priority를 하는 상황에도 preemption을 고려해야 합니다.

 

• unblock()
• thread_create()
• thread_set_priority()

이렇게 총 세 번의 상황에서 선점 스케쥴링을 진행해주면 됩니다.

 

 

헷갈렸던 것

 

timer interrupt가 발생할 때마다 스레드의 라이프사이클이 영향을 받고 스케줄링이 발생할 수 있습니다. 이 과정에서 스케줄러가 현재 실행 중인 스레드를 교체하거나 유지할지 결정하게 됩니다.

 

구체적으로:

1. Tick 주기: 타이머가 일정한 주기(tick)마다 인터럽트를 발생시키며, 이 주기는 일반적으로 시스템에서 설정한 타이머의 속도에 따라 결정됩니다.
2. 스케줄링: 매 tick이 발생할 때마다, 타이머 인터럽트 핸들러가 호출됩니다. 이 핸들러에서는 실행 중인 스레드의 타임 슬라이스(time slice)가 끝났는지 확인합니다. 타임 슬라이스가 끝났다면, 스레드를 선점하고 다른 스레드를 실행할지 여부를 결정하는 스케줄러가 동작하게 됩니다.

 

그러면 타이머 인터럽트 말고, 다른 인터럽트도 결국에는 처리할 수 있는 기간이 타이머 인터럽트의 주기마다 처리할 수 있는건가? 라는 의문이 들었습니다.

 

구체적으로

blocked thread가, 기다리던 이벤트가 처리되어서 unblocked 되면 ready thread로 다시 스케쥴링되는 거 아닌가요?

이거는 그러면 i/o 완료 interrupt를 받은 blocked thread가 timer interrupt가 발생할 때까지 처리를 기다리는거 아닌가요?

 

 

처음 의문에 대해서는,

다른 인터럽트도 타이머 인터럽트와 독립적으로 발생하며, 타이머 인터럽트 주기와 관계없이 즉시 처리될 수 있습니다. 인터럽트는 하드웨어나 소프트웨어에 의해 발생하며, CPU는 인터럽트를 감지하면 현재 작업을 중단하고 해당 인터럽트의 핸들러로 제어를 넘깁니다.

 

 

그렇기 때문에,

Blocked 상태에 있는 스레드가 기다리던 이벤트(예: I/O 작업 완료)가 발생하면, 해당 스레드는 unblocked 상태가 되어 Ready 리스트에 추가됩니다. 여기 까지가 unblock 과정에 대한 interrupt handler가 처리하는 일입니다.

 

따라서 Ready 상태가 되었다고 해서 즉시 실행되는 것은 아니며, 실행 여부는 다음 timer_interrupt 때 스케줄러가 실행될 때까지 기다리게 됩니다.

 

이를 조금 더 구체적으로 설명하자면:

1. Blocked 스레드는 I/O 작업과 같은 이벤트를 기다리며 CPU를 양보하고 대기합니다.
2. I/O 인터럽트가 발생하면, I/O 작업이 완료되었다는 것을 알리는 인터럽트 핸들러가 실행됩니다. 핸들러는 해당 스레드를 Unblocked 상태로 바꾸고 Ready 리스트에 추가합니다. 이 과정에서 스레드는 아직 CPU를 점유하지는 않습니다.
3. 스케줄러가 실행될 기회는 보통 타이머 인터럽트에 의해 발생합니다. 즉, 스케줄링 주기가 타이머 인터럽트에 따라 결정되기 때문에, 타이머 인터럽트가 발생할 때까지 Ready 상태의 스레드는 실행되지 않고 대기합니다.
4. 타이머 인터럽트가 발생하면 스케줄러가 실행되며, Ready 상태인 스레드 중 하나가 선택되어 CPU에서 실행됩니다.

따라서 unblocked된 스레드는 다음 타이머 인터럽트가 발생할 때까지 실행되지 않고, Ready 리스트에서 대기하는 것이 일반적입니다.

 

 

timer tick을 기준으로 스레드 스케쥴링을 진행하는데,

싱글 스레드인 pintos에서

그럼 blocked된 스레드에 대한 i/o 완료 interrupt가 tick 주기와 동일한 순간이 아닌

한 tick 사이에 들어오면

"그걸 그 순간에 처리하는가" 아니면 "다음 tick이 시작할 때 처리하는가"가 궁금했습니다.

 

결과적으로는, CPU는 단일 tick 동안 여러 개의 인터럽트를 처리할 수 있습니다.

tick은 타이머 기반 스레드 스케쥴링을 위해 우리가 구현한 임의의 기준이기 때문입니다.

 

이해를 돕기 위해 단계별로 설명하자면:

1. 인터럽트 처리 우선순위: CPU는 타이머 인터럽트 외에도 I/O 장치 등 다양한 소스에서 발생하는 인터럽트를 처리합니다. 인터럽트가 발생하면, CPU는 현재 실행 중인 작업을 잠시 중단하고 인터럽트 핸들러를 실행합니다.
2. 인터럽트의 중첩 처리: 인터럽트가 처리되는 도중에도 새로운 인터럽트가 발생할 수 있습니다. 일반적으로 인터럽트는 중첩될 수 있으며, 우선순위가 더 높은 인터럽트는 기존 인터럽트 처리를 중단시키고 우선 처리될 수 있습니다.
3. 타이머 인터럽트: 주기적으로 발생하는 타이머 인터럽트는 스케줄러를 호출하여 스레드를 교체할 기회를 제공하지만, 그 외에도 I/O 완료 인터럽트 등 다양한 종류의 인터럽트가 발생할 수 있습니다.
4. 동일한 tick 동안 여러 인터럽트 처리: CPU는 하나의 tick 동안도 여러 인터럽트를 처리할 수 있으며, 각 인터럽트는 해당 인터럽트 핸들러에서 적절하게 처리됩니다. 그 후 스케줄러가 실행되어 어떤 스레드가 실행될지 결정됩니다.

결론적으로, 하나의 tick 내에서도 CPU는 여러 종류의 인터럽트를 처리하고, 상황에 따라 다양한 스레드의 상태를 변경할 수 있습니다

 

추가적으로,

이렇게 인터럽트의 중첩 구조를 가질 수 있기 때문에,

특정 함수는 다른 인터럽트로 인해 방해받지 않도록 구현해야할 필요가 있기도 합니다.

thread_yield() 같은 함수가 대표적입니다.

 

왜 그럴까요?

바로 context switching과 데이터 무결성 보장을 위해서입니다.

 

인터럽트의 중첩 구조 때문에, thread_yield() 같은 함수가 다른 인터럽트로 인해 방해받지 않도록 구현해야 할 필요가 있는 이유는 컨텍스트 스위칭과 데이터 무결성을 보장하기 위해서입니다. 그 이유를 자세히 설명하자면:

1. 컨텍스트 스위칭 중 일관성 보장

• thread_yield() 함수는 CPU에서 현재 실행 중인 스레드의 상태를 저장하고, 새로운 스레드를 선택해 실행하는 컨텍스트 스위칭을 담당하는 함수입니다.
• 이 과정에서 현재 스레드의 레지스터 상태, 스택, 그리고 프로세스 제어 블록(PCB) 등이 저장되고, 새로운 스레드의 상태를 복원하여 실행하게 됩니다.
• 컨텍스트 스위칭은 매우 복잡한 과정이기 때문에, 만약 이 도중에 또 다른 인터럽트가 발생하여 thread_yield() 함수의 실행이 중단된다면, 스레드 상태가 일관성 없이 저장될 가능성이 생깁니다. 즉, 스레드가 제대로 저장되지 않거나 복원되지 않는 경우가 발생할 수 있습니다.

2. 데이터 무결성 문제

• **thread_yield()**는 스레드 큐와 같은 공유 자원을 조작할 가능성이 높습니다. 스레드를 CPU에서 제거하고 다른 스레드를 실행하기 위한 과정에서 스레드 큐나 스케줄러가 관리하는 자료구조가 변경됩니다.
• 이때, 인터럽트가 발생하여 다른 코드가 실행되면 공유 자원의 일관성이 깨질 수 있습니다. 이를 방지하기 위해, 스레드의 상태를 저장하거나 스케줄링을 처리할 때는 인터럽트를 비활성화하여 다른 인터럽트가 중간에 개입하지 않도록 해야 합니다.

3. 중첩된 인터럽트로 인한 교착 상태 또는 오류

• 만약 **thread_yield()**가 인터럽트 도중 호출되거나, 다른 인터럽트에 의해 중단되었다가 다시 호출되면, 중첩된 인터럽트로 인해 교착 상태 또는 예기치 않은 오류가 발생할 수 있습니다.
• 예를 들어, CPU가 스레드 A의 상태를 저장하는 도중 다른 인터럽트가 발생해 스레드 B로 전환이 시작되었는데, 또 다른 인터럽트가 스레드 A나 B의 상태를 다시 저장하려 한다면, 이 과정이 엉망이 될 수 있습니다.

결론: 왜 **thread_yield()**는 보호가 필요할까?

• **thread_yield()**는 스레드의 상태 저장, 복원, 스케줄러 호출 등 중요한 작업을 수행하므로, 이 함수가 중간에 인터럽트로 인해 중단되면 컨텍스트 스위칭 과정이 불완전해질 수 있습니다.
• 따라서, 이런 중요한 함수는 인터럽트를 비활성화한 상태에서 실행되며, 다른 인터럽트로 인해 방해받지 않도록 보호해야 합니다. 이는 스레드 상태의 일관성을 유지하고 데이터 무결성을 보장하기 위해서입니다.

**thread_yield()**는 CPU 자원을 관리하고 스케줄링하는 핵심적인 함수이기 때문에, 반드시 방해받지 않도록 구현할 필요가 있습니다.

 

 

어쨋든

이거때문에 너무 헷갈렸던게,

block중인 스레드가 현재 시스템의 모든 스레드 중에서 우선순위가 가장 높다면,

얘가 thread_unblock 되면 직후에 선점 스케쥴링이 가능하도록 구현해야하는 것 아닌가?

싶어

thread_unblock 함수의 마지막에 preemption_by_priority() 함수를 넣었으나 자꾸 timeout이 뜨고,

그렇다면 unblock을 호출하는 함수의 unblock 호출 이후 부분에 preemption_by_priority() 를 넣었으나

kernel panic이 나는 것 아니겠는가!!

 

kernel panic의 이유는 interrupt 처리 중에 preemption_by_priority() 함수가 호출하는 thread_yield() 함수를 호출하면 안되었기 때문이다.

(ASSERT함수에 걸려서 그랬음)

 

왜 이렇게 구현된걸까?

 

thread_unblock 함수의 주석을 다시 살펴보면,

unblock 함수는 현재 running thread를 preemption 하지 않는다고 써져 있다.

이게 중요하다고 하는데,

그 이유는 다음과 같다.

 

이 함수는 인터럽트가 비활성화된 상태에서 실행중일 수 있기 때문에,

caller가 스레드를 원자적으로 unblock하고 다른 데이터를 안전하게 업데이트할 수 있음을 기대할 수 있다고 설명합니다. 즉, 인터럽트가 비활성화된 동안에도 안전하게 처리될 수 있도록 설계되어 있다.

 

unblock 이후 즉시 선점 스케쥴링이 되도록 구현되어있는 것은 아니다.

즉시성보다는 안정성을 택한 것 같다.

unblock 되어 ready_list로 들어간 스레드는 다음 tick에서 timer_interrupt 때 스케쥴링될 것이다.

 

 

 

혹시 몰라서 한 번 구현해봣는데

위처럼 kernel panic이 나온다.

 

스레드 스케쥴링을 하려면

현재 THREAD_RUNNING state에 있는 스레드는 없어야 한다.

다시 말해, running 중인 스레드 없이 ready_list에 있는 스레드 끼리 스케쥴링을 해줘야 한다.

 

schedule 함수는 그런 상황을 상정하기 때문에,

현재 unblock 함수에서 schedule을 호출하면 schdule의 ASSERT(curr->status != THREAD_RUNNING)에 걸리는 것이다.

 

이렇게 schedule이 요구하는 상황을 맞춰주기 위해 do_schedule이 존재한다.

 

do_schedule(thread_state) 를 호출하면

현재 RUNNING STATE에 있는 스레드를 thread_state로 변화시킨 채로 schedule을 호출해주기 때문이다.

 

조금 더 위에서 바라보자면,

thread_yield 함수는 현재 RUNNING state의 스레드를 ready list로 방출한다.

do_schedule(THREAD_RUNNING)을 호출하기 때문이다.

그런데 위 함수는 다른 외부 인터럽트 처리중에는 작동 못하도록 ASSERT가 걸려있다.

 

따라서 timer_sleep과 같이 외부 인터럽트를 기다리며 block된 스레드들은

timer_interrupt 혹은 다른 외부 인터럽트에 의해 unblock 되는데, 이때 즉각적으로 선점 스케쥴링을 하기 위해

thread_yield를 무조건 호출해야 하는데, 그게 pintos의 구조 상 막혀 있다.

 

결과적으로,

외부 인터럽트를 기다리며 block된 스레드가 unblock되는 상황에서는 즉각적인 스케쥴링을 할 필요가 없다(할 수가 없다).

 

 

 

리눅스도 이렇게 unblock을 구현했을까

리눅스도 이렇게 unblock되는 상황에서, 즉시 선점 스케쥴링하는게 아니라

다음 tick에 스케쥴링 되도록 구현했을까?