Dear
Thanks very much for your useful suggestion!!
On Tue, Jun 2, 2009 at 2:31 AM, Udo A. Steinberg udo@hypervisor.org wrote:
On Tue, 2 Jun 2009 01:54:49 +0800 Sean (S) wrote:
S> I want to build another scheduling framework in Fiasco. S> I will design a control server (scheduler) here, and it will plan a time S> schedule for all user threads to determine in which time, which user S> threads can be scheduled. S> S> For example, there are 7 user threads in the system. I group them into S> three group. S> Group A : user thread 1, 2, 3 S> Group B : user thread 4, 5 S> Group C : user thread 6, 7 S> S> If Group A is eligible in the time interval {0~3 }, Group B is {3~4}, and S> Group C is {5~8}. S> S> At time 0, the user thread 4, 5, 6, 7 might be in the ready state but the S> system scheduler can't schedule them to execute. In other word, the user S> thread 1, 2, 3 are eligible and the user thread 4, 5, 6, 7 are ineligible S> during time 0 to time 3. So at time 3, the user thread 1, 2, 3, 6, 7 will S> change to be ineligible and user thread 4, 5 will be eligible.
So basically you can have any of your threads in one of 4 different states:
- ready+eligible
- ready+ineligible
- blocked+eligible
- blocked+ineligible
The ready list in Fiasco only distinguishes ready and blocked threads. If a thread is ready, it is in the ready list and can be picked by the scheduler, if it's blocked it's not in the ready list and thus cannot be dispatched.
One way you can achieve your desired behavior is by adding a new Thread_ineligible flag to the thread state. When a new time interval begins, you:
a) set Thread_ineligible on all threads that were previously eligible and are now ineligible. Furthermore, if any of these threads is ready (Thread_ready is set), you ready_dequeue() the thread.
b) clear Thread_ineligible on all threads that were previously ineligible and are now eligible. Furthermore, if any of these threads is ready (Thread_ready is set), you ready_enqueue() the thread.
That way the ready queue will only contain threads in state 1) and threads in state 2) will be kicked out according to rule a). The scheduler will handle the rest correctly.
I'm sorry for my poor understanding.
Now I have read the document from the lecture "Microkernel Construction". And I traced the source code of Context::schedule(), Context::state_change() ... etc.
I got confused in several points
Currently, I don't trace how to implement timeout in Fiasco. I assume when it expired, the timeout handler will execute.
1. If timeout handler is executed inside Fiasco => Fiasco needs to determine which group of threads needs to change state and the information about time interval. So I need to port all control rules of control server into Fiasco? => Or I need to maintain a list in Fiasco and update this list from the control server on top of Fiasco. But how to do it?
2. If timeout handler is executed as a user thread on top of Fiasco. How the control server on top of Fiasco changes the other user thread's state? => I need to provide the system call interface or other issues to change the user thread's state. => Can I implement it by fixing the existent system call thread_ex_regs or I need to add a new system call?
If I use the system call thread_ex_regs, I think it will have the problem: If there are a lot of threads needed to change the state, I need to call the system call many times for every thread. it seems to be a huge overhead here.
Can you give me any idea about it? I'm sorry if I got into wrong direction or got wrong understanding of Fiasco.
Thanks very much!!
Best Regards, Sean
S> I also need to consider how to implement a precise time interval and other S> issues about the control server design. But in first, I want to find some S> way to implement the behavior of marking the user threads ineligible.
You can check how Fiasco handles timeouts. You can implement a new timeout type that sets/clears the Thread_eligible flag when it expires.
Cheers,
- Udo
l4-hackers mailing list l4-hackers@os.inf.tu-dresden.de http://os.inf.tu-dresden.de/mailman/listinfo/l4-hackers