Dear
Now I am tracing the source code of cpu reservation server in l4/pkg/cpu_reserve directory. And I got several questions...
1. The bottom of cpu reservation server is implemented by l4_rt_add_timeslice(), l4_rt_set_period(), l4_rt_begin_strictly_periodic() functions. And these functions are defined in l4/pkg/l4sys/include/ARCH-x86/rt_sched-impl.h which calls l4_rt_generic() function.
Function l4_rt_generic() is implemented by inline assembly, and it seems to call the system call "thread_schedule". Because these functions only appears in ARCH-x86 directory, do they support on ARM architecture? If not, how can I implement similar behaviors of these functions? Where can I find the document about the L4 system call API ? I can't really understand the behavior of these functions.
2. When system contains three user threads, I want to control Fiasco scheduler not to schedule one thread in these three threads during one time interval. How can I implement it? The simplest way seems to control this thread into un-running state. How can I achieve this by a supervisal server?
I'm sorry for my poor English and lengthy question. I'm glad if you give me some hints or corrections.
Thanks a lot!
Best Regards, Sean
On Mon, 1 Jun 2009 01:57:46 +0800 Sean (S) wrote:
S> Function l4_rt_generic() is implemented by inline assembly, and it seems S> to call the system call "thread_schedule".
Indeed.
S> Because these functions only appears in ARCH-x86 directory, do they S> support on ARM architecture?
Currently these functions are available on x86 only.
S> If not, how can I implement similar behaviors of these functions? S> Where can I find the document about the L4 system call API ? I can't S> really understand the behavior of these functions.
The API is described in my diploma thesis, see http://os.inf.tu-dresden.de/papers_ps/steinberg-diplom.pdf
You would have to extend the kernel ABI (e.g., which parameters are passed in which registers) for ARM to be able to use these extensions. Note that the real-time scheduling code in Fiasco is quite dated. No one has used or maintained it in the last 5 years.
S> 2. When system contains three user threads, I want to control Fiasco S> scheduler not to schedule one thread in these three threads during one S> time interval. How can I implement it? S> The simplest way seems to control this thread into un-running state. S> How can I achieve this by a supervisal server?
I suggest you read the aforementioned PDF document first. It describes how you can control thread execution with periods, deadlines and release times.
Cheers,
- Udo
*Dear Udo
Thanks for your reply. *
On Mon, Jun 1, 2009 at 2:32 AM, Udo A. Steinberg udo@hypervisor.org wrote:
On Mon, 1 Jun 2009 01:57:46 +0800 Sean (S) wrote:
S> Function l4_rt_generic() is implemented by inline assembly, and it seems S> to call the system call "thread_schedule".
Indeed.
S> Because these functions only appears in ARCH-x86 directory, do they S> support on ARM architecture?
Currently these functions are available on x86 only.
S> If not, how can I implement similar behaviors of these functions? S> Where can I find the document about the L4 system call API ? I can't S> really understand the behavior of these functions.
The API is described in my diploma thesis, see http://os.inf.tu-dresden.de/papers_ps/steinberg-diplom.pdf
You would have to extend the kernel ABI (e.g., which parameters are passed in which registers) for ARM to be able to use these extensions. Note that the real-time scheduling code in Fiasco is quite dated. No one has used or maintained it in the last 5 years.
S> 2. When system contains three user threads, I want to control Fiasco S> scheduler not to schedule one thread in these three threads during one S> time interval. How can I implement it? S> The simplest way seems to control this thread into un-running state. S> How can I achieve this by a supervisal server?
I suggest you read the aforementioned PDF document first. It describes how you can control thread execution with periods, deadlines and release times.
* I got confused here. I already go through your diploma thesis. This thesis describes the design issues and implementation detail of the Periodic Mode support for Fiasco. If I don't want to control thread execution with periods, deadlines and etc. , how can I implement the functionality I mentioned?
My goal is that
In the system, there are several user threads. During a time interval, some particular user threads will not be scheduled even though these threads are in ready state.
How can I implement it? Does any exist function/API support it? I already have several directions below. I hope anyone give me some suggestions. 1. Directly change the state of these threads to non-ready by system call thread_ex_regs_sc. But there are some problems because the thread_ex_regs_sc can be called by the thread in same address space. And I'm not sure the thread states maintained by Fiasco and whether I can change the state directly.
2. Modify the Fiasco scheduler. Before choosing the thread to schedule, the Fiasco scheduler checks a list contained un-scheduled threads IDs. But the maintenance of this list is a problem. Maybe I need to add a new system call for this.
Thanks a lot for your reading!
Best Regards, Sean*
Cheers,
- Udo
l4-hackers mailing list l4-hackers@os.inf.tu-dresden.de http://os.inf.tu-dresden.de/mailman/listinfo/l4-hackers
On Mon, 1 Jun 2009 20:03:49 +0800 Sean (S) wrote:
S> I already go through your diploma thesis. This thesis describes the design S> issues and implementation detail of the Periodic Mode support for Fiasco. S> If I don't want to control thread execution with periods, deadlines and S> etc. , how can I implement the functionality I mentioned? S> S> My goal is that S> S> In the system, there are several user threads. During a time interval, S> some particular user threads will not be scheduled even though these S> threads are in ready state.
In Fiasco all threads in the ready state are eligible for execution. In fact, the ready state means that the thread is only waiting to be dispatched by the scheduler. So if you don't want a thread to be scheduled, it must not be in the ready state.
S> How can I implement it? Does any exist function/API support it?
Before we can give you a definite answer, we need to know why you don't want a particular thread to be scheduled. Here are some questions:
1) What is the event that makes an otherwise ready thread ineligible to execute (according to your use case)?
2) What is the event that makes it eligible for scheduling again?
Without answers to these questions we cannot tell you what API you might be able to use or how you would have to implement such a mechanism yourself.
Cheers,
- Udo
Dear
Thanks for your reply!
On Mon, Jun 1, 2009 at 8:46 PM, Udo A. Steinberg udo@hypervisor.org wrote:
On Mon, 1 Jun 2009 20:03:49 +0800 Sean (S) wrote:
S> I already go through your diploma thesis. This thesis describes the design S> issues and implementation detail of the Periodic Mode support for Fiasco. S> If I don't want to control thread execution with periods, deadlines and S> etc. , how can I implement the functionality I mentioned? S> S> My goal is that S> S> In the system, there are several user threads. During a time interval, S> some particular user threads will not be scheduled even though these S> threads are in ready state.
In Fiasco all threads in the ready state are eligible for execution. In fact, the ready state means that the thread is only waiting to be dispatched by the scheduler. So if you don't want a thread to be scheduled, it must not be in the ready state.
S> How can I implement it? Does any exist function/API support it?
Before we can give you a definite answer, we need to know why you don't want a particular thread to be scheduled. Here are some questions:
- What is the event that makes an otherwise ready thread ineligible to
execute (according to your use case)?
- What is the event that makes it eligible for scheduling again?
I want to build another scheduling framework in Fiasco. I will design a control server (scheduler) here, and it will plan a time schedule for all user threads to determine in which time, which user threads can be scheduled.
For example, there are 7 user threads in the system. I group them into three group. Group A : user thread 1, 2, 3 Group B : user thread 4, 5 Group C : user thread 6, 7
If Group A is eligible in the time interval {0~3 }, Group B is {3~4}, and Group C is {5~8}.
At time 0, the user thread 4, 5, 6, 7 might be in the ready state but the system scheduler can't schedule them to execute. In other word, the user thread 1, 2, 3 are eligible and the user thread 4, 5, 6, 7 are ineligible during time 0 to time 3. So at time 3, the user thread 1, 2, 3, 6, 7 will change to be ineligible and user thread 4, 5 will be eligible.
I also need to consider how to implement a precise time interval and other issues about the control server design. But in first, I want to find some way to implement the behavior of marking the user threads ineligible.
Without answers to these questions we cannot tell you what API you might be able to use or how you would have to implement such a mechanism yourself.
Cheers,
Sorry for my poor English and lengthy question. Very thanks for your kindness!
- Udo
l4-hackers mailing list l4-hackers@os.inf.tu-dresden.de http://os.inf.tu-dresden.de/mailman/listinfo/l4-hackers
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:
1) ready+eligible 2) ready+ineligible 3) blocked+eligible 4) 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.
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
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
On Wed, 3 Jun 2009 02:25:15 +0800 Sean (S) wrote:
S> I got confused in several points S> S> Currently, I don't trace how to implement timeout in Fiasco. I assume when S> it expired, the timeout handler will execute.
There exists a timeout base class and 3 derived classes for specific timeouts, namely IPC timeouts, timeslice timeouts and deadline timeouts. When a timeout expires, the virtual method ::expired is called; all derived classes overwrite this method such that code specific to the timeout type is executed.
S> 1. If timeout handler is executed inside Fiasco S> => Fiasco needs to determine which group of threads needs to change S> state and the information about time interval. So I need to port all S> control rules of control server into Fiasco? S> => Or I need to maintain a list in Fiasco and update this list from the S> control server on top of Fiasco. But how to do it?
Have a look at how the current real-time scheduling framework controls deadlines, period etc. from user space. You would have to design a similar interface that downloads interval start/end times and affected threads into the kernel.
S> 2. If timeout handler is executed as a user thread on top of Fiasco. How S> the control server on top of Fiasco changes the other user thread's state? S> => I need to provide the system call interface or other issues to S> change the user thread's state. S> => Can I implement it by fixing the existent system call thread_ex_regs S> or I need to add a new system call?
The simplest thing here is to add a new system call that allows setting and clearing the Thread_ineligible flag of threads from user mode. I do not recommend overloading the ex_regs system call because that only complicates things.
S> If I use the system call thread_ex_regs, I think it will have the problem: S> If there are a lot of threads needed to change the state, I need to S> call the system call many times for every thread. it seems to be a huge S> overhead here.
Correct. But you can design your system call such that you change the state of multiple (all?) affected threads at once. However, note that the more threads change state on interval boundaries, the more latency you will add in the kernel even if you can do it with just a single system call invocation.
If this is a problem, you could take an alternate approach to the whole problem: You could maintain a run queue for each time interval and when one interval ends and another starts, you could just switch run queues. While this removes the need to track eligible/ineligible state of threads, you now have to decide into which run queue a particular threads should go when it is ready. This approach requires less thread state changes, but requires much more memory.
Cheers,
- Udo
Dear
Now I start to write my own scheduling framework. But I got some questions here...
Because the policy to decide the time interval in control server is dependent on the execution time of the threads in each group. I need to get the information about the execution time after last context switch. I had traced the source code about the variable *_consumed_time* in class Context. This variable will be updated in * Thread::handle_timer_interrupt()* function. My question is 1. Can I use this variable directly? What's the accuracy of this variable?
2. *Thread::handle_timer_interrupt()* function will be called in * irq_handler()* function in ARM platform. I can't find any information about this function. When will this function be called? Where is the related source code of calling/registering this function?
Thanks for your kindness.
Best Regards, Sean
On Wed, Jun 3, 2009 at 3:20 AM, Udo A. Steinberg udo@hypervisor.org wrote:
On Wed, 3 Jun 2009 02:25:15 +0800 Sean (S) wrote:
S> I got confused in several points S> S> Currently, I don't trace how to implement timeout in Fiasco. I assume when S> it expired, the timeout handler will execute.
There exists a timeout base class and 3 derived classes for specific timeouts, namely IPC timeouts, timeslice timeouts and deadline timeouts. When a timeout expires, the virtual method ::expired is called; all derived classes overwrite this method such that code specific to the timeout type is executed.
S> 1. If timeout handler is executed inside Fiasco S> => Fiasco needs to determine which group of threads needs to change S> state and the information about time interval. So I need to port all S> control rules of control server into Fiasco? S> => Or I need to maintain a list in Fiasco and update this list from the S> control server on top of Fiasco. But how to do it?
Have a look at how the current real-time scheduling framework controls deadlines, period etc. from user space. You would have to design a similar interface that downloads interval start/end times and affected threads into the kernel.
S> 2. If timeout handler is executed as a user thread on top of Fiasco. How S> the control server on top of Fiasco changes the other user thread's state? S> => I need to provide the system call interface or other issues to S> change the user thread's state. S> => Can I implement it by fixing the existent system call thread_ex_regs S> or I need to add a new system call?
The simplest thing here is to add a new system call that allows setting and clearing the Thread_ineligible flag of threads from user mode. I do not recommend overloading the ex_regs system call because that only complicates things.
S> If I use the system call thread_ex_regs, I think it will have the problem: S> If there are a lot of threads needed to change the state, I need to S> call the system call many times for every thread. it seems to be a huge S> overhead here.
Correct. But you can design your system call such that you change the state of multiple (all?) affected threads at once. However, note that the more threads change state on interval boundaries, the more latency you will add in the kernel even if you can do it with just a single system call invocation.
If this is a problem, you could take an alternate approach to the whole problem: You could maintain a run queue for each time interval and when one interval ends and another starts, you could just switch run queues. While this removes the need to track eligible/ineligible state of threads, you now have to decide into which run queue a particular threads should go when it is ready. This approach requires less thread state changes, but requires much more memory.
Cheers,
- Udo
l4-hackers mailing list l4-hackers@os.inf.tu-dresden.de http://os.inf.tu-dresden.de/mailman/listinfo/l4-hackers
l4-hackers@os.inf.tu-dresden.de
-
Sean -
Udo A. Steinberg