search

littlekernel / lk

LK embedded kernel
MIT License
3.15k stars 621 forks source link

[wait-queue] fix wake all to remove threads from tail #161

Open mahavirj opened 8 years ago

mahavirj commented 8 years ago

While waking up all threads from wait-queue, order should start from tail to maintain correct scheduling sequence.

Signed-off-by: Mahavir Jain mahavirpj@gmail.com

travisg commented 8 years ago

No so sure about that, since it takes the items off the queue and then shoves them in the head of the run queue, if you pop from the tail it'll have the effect of putting the thread that's been waiting the longest deeper in the queue, and the thread that's been waiting the least longest at the head. With it popping from the head, it inverts the order and puts the oldest thread at the head, which i think is slightly more fair.

mahavirj commented 8 years ago

Let us consider a scenario, where resource is acquired, and thread1 blocks on it at time t1. And later thread2 blocks at time t2 (t2 > t1). Now if there is call to wake all threads, thread2 will get chance to run earlier than thread1, which seems incorrect (thread2 being at head of run queue). Correct me if I am wrong here.

zeusk commented 8 years ago

EDIT: I think, you're right.

After removing a thread from head of wait queue on line 1220, it is inserted to run queue's head on line 1227.

So the tail of wait queue will end up as head of run queue instead of our desired behavior (first come, first serve).

mahavirj commented 8 years ago

Ping...