Adding a new scheduling algorithm to Fiasco.OC
Hi, I'm planning to add a new scheduling algorithm to Fiasco.OC. I will implement EDF. First of all, is there some handout written by you main developers that copes with the issues of implementing EDF in Fiasco.OC? What I've achieved so far: I've created the files sched_context-edf.cpp and ready_queue_edf.cpp in ./kernel/fiasco/src/kern, using the corresponding source files for your fixed-priority scheduler as templates. I've named the config directive used in ./kernel/fiasco/src/Modules.* files analogous to yours, that is 'sched_edf' in my case. Now, I'm beginning to modify sched_context-edf.cpp and ready_queue_edf.cpp to fit the requirements of EDF, especially the en- and dequeuing as well as the 'dominates' method. Are there any other major source files that I do have to alter? Thanks in advance! Best regards, Valentin
Hi, On Thu Jun 12, 2014 at 16:29:43 +0200, Valentin Hauner wrote:
I'm planning to add a new scheduling algorithm to Fiasco.OC. I will implement EDF. First of all, is there some handout written by you main developers that copes with the issues of implementing EDF in Fiasco.OC?
No, there's no such memo.
What I've achieved so far: I've created the files sched_context-edf.cpp and ready_queue_edf.cpp in ./kernel/fiasco/src/kern, using the corresponding source files for your fixed-priority scheduler as templates. I've named the config directive used in ./kernel/fiasco/src/Modules.* files analogous to yours, that is 'sched_edf' in my case. Now, I'm beginning to modify sched_context-edf.cpp and ready_queue_edf.cpp to fit the requirements of EDF, especially the en- and dequeuing as well as the 'dominates' method.
Are there any other major source files that I do have to alter?
That looks good. You should look at the wfq files as those already implement an algorithm that is quite close to EDF. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, I've added a new config directive for 'sched_edf' to the Modules.* files in 'kernel/fiasco/src', that is: PREPROCESS_PARTS-$(CONFIG_SCHED_EDF) += sched_edf This enables the user to compile the kernel with EDF scheduling when setting this directive, right? I want to implement the preemptive EDF algorithm, i.e. any running task must be preempted if a new task with a shorter deadline arrives. dominates() from sched_context-edf.cpp and next_to_run() from ready_queue_edf.cpp are designed to choose the one with the shortest deadline, but how can I tell Fiasco to act preemptive? Thanks in advance! Best regards, Valentin On 06/13/2014 10:01 PM, Adam Lackorzynski wrote:
Hi,
On Thu Jun 12, 2014 at 16:29:43 +0200, Valentin Hauner wrote:
I'm planning to add a new scheduling algorithm to Fiasco.OC. I will implement EDF. First of all, is there some handout written by you main developers that copes with the issues of implementing EDF in Fiasco.OC?
No, there's no such memo.
What I've achieved so far: I've created the files sched_context-edf.cpp and ready_queue_edf.cpp in ./kernel/fiasco/src/kern, using the corresponding source files for your fixed-priority scheduler as templates. I've named the config directive used in ./kernel/fiasco/src/Modules.* files analogous to yours, that is 'sched_edf' in my case. Now, I'm beginning to modify sched_context-edf.cpp and ready_queue_edf.cpp to fit the requirements of EDF, especially the en- and dequeuing as well as the 'dominates' method.
Are there any other major source files that I do have to alter?
That looks good. You should look at the wfq files as those already implement an algorithm that is quite close to EDF.
Adam
On Mon Jun 30, 2014 at 12:08:00 +0200, Valentin Hauner wrote:
I've added a new config directive for 'sched_edf' to the Modules.* files in 'kernel/fiasco/src', that is: PREPROCESS_PARTS-$(CONFIG_SCHED_EDF) += sched_edf This enables the user to compile the kernel with EDF scheduling when setting this directive, right?
This adds the preprocess tag 'sched_edf' which are used in the expressions for the INTERFACE and IMPLEMENTATION blocks. With that you can chose whether a block of code is included in compilation or not.
I want to implement the preemptive EDF algorithm, i.e. any running task must be preempted if a new task with a shorter deadline arrives. dominates() from sched_context-edf.cpp and next_to_run() from ready_queue_edf.cpp are designed to choose the one with the shortest deadline, but how can I tell Fiasco to act preemptive?
So, on one CPU only one thread can be running at a time. Others might be ready to execute but not running. Regarding preemption, the timer interrupt drives scheduling (see Thread::handle_timer_interrupt) which calls schedule() whenever there's something to do, i.e. a timeout has expired. Of course schedule() might also be called for other reasons, for example when threads change their ready state. In the scheduler implementation you'll see whenever some new thread arrives or one leaves, so I think the preemption as you need it is already there. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi Adam, thank you, that makes things clearer to me, especially the information of the timer for managing preemption. In a previous mail, you stated that a thread has a Sched_context object embedded that stores scheduling-related information. However, I cannot find a 1:1 relation from a Thread to a Sched_context object. I've found various calls of the sched_context() method in 'thread.cpp', which is defined in 'context.cpp'. Furthermore, there are several calls of the current() method in 'thread.cpp' (returning the current context), which is defined in 'context_base.cpp'. So my main question is: What is the exact relation of a Thread object to all these classes? I assume that a Context object is cpu-specific, i.e. each Context object points to its home cpu. Is that right? This would make sense since there is a home_cpu attribute and a schedule() method in that class that handles the scheduling on a certain cpu. But what's the matter with Sched_context? It seems to me that there is no 1:1 relation from a Thread to a Sched_context since the sched_context() method called in 'thread.cpp' is defined in 'context.cpp'. So is a Sched_context cpu-specific, too? This would not make sense to me as a Sched_context object stores thread-specific information such as the priority and the remaining quantum of a thread. Thanks in advance! Best regards, Valentin On 07/02/2014 12:30 AM, Adam Lackorzynski wrote:
On Mon Jun 30, 2014 at 12:08:00 +0200, Valentin Hauner wrote:
I've added a new config directive for 'sched_edf' to the Modules.* files in 'kernel/fiasco/src', that is: PREPROCESS_PARTS-$(CONFIG_SCHED_EDF) += sched_edf This enables the user to compile the kernel with EDF scheduling when setting this directive, right?
This adds the preprocess tag 'sched_edf' which are used in the expressions for the INTERFACE and IMPLEMENTATION blocks. With that you can chose whether a block of code is included in compilation or not.
I want to implement the preemptive EDF algorithm, i.e. any running task must be preempted if a new task with a shorter deadline arrives. dominates() from sched_context-edf.cpp and next_to_run() from ready_queue_edf.cpp are designed to choose the one with the shortest deadline, but how can I tell Fiasco to act preemptive?
So, on one CPU only one thread can be running at a time. Others might be ready to execute but not running. Regarding preemption, the timer interrupt drives scheduling (see Thread::handle_timer_interrupt) which calls schedule() whenever there's something to do, i.e. a timeout has expired. Of course schedule() might also be called for other reasons, for example when threads change their ready state. In the scheduler implementation you'll see whenever some new thread arrives or one leaves, so I think the preemption as you need it is already there.
Adam
Hi, On Thu Jul 03, 2014 at 12:09:06 +0200, Valentin Hauner wrote:
In a previous mail, you stated that a thread has a Sched_context object embedded that stores scheduling-related information. However, I cannot find a 1:1 relation from a Thread to a Sched_context object. I've found various calls of the sched_context() method in 'thread.cpp', which is defined in 'context.cpp'. Furthermore, there are several calls of the current() method in 'thread.cpp' (returning the current context), which is defined in 'context_base.cpp'.
So my main question is: What is the exact relation of a Thread object to all these classes?
A Thread is derived from Context which in turn is derived from Context_base. So a Thread contains a Context and from a Thread everything in Context can be accessed (except 'private' things of course). A Sched_context is embedded in the Context class (_sched_context).
I assume that a Context object is cpu-specific, i.e. each Context object points to its home cpu. Is that right? This would make sense since there
A context 'lives' on a CPU but it can also change its CPU. The CPU info is stored in the Context so that the code knows on which CPU it is currently running.
is a home_cpu attribute and a schedule() method in that class that handles the scheduling on a certain cpu.
But what's the matter with Sched_context? It seems to me that there is no 1:1 relation from a Thread to a Sched_context since the sched_context() method called in 'thread.cpp' is defined in 'context.cpp'. So is a Sched_context cpu-specific, too? This would not make sense to me as a Sched_context object stores thread-specific information such as the priority and the remaining quantum of a thread.
Generally, scheduling configuration is CPU specific. However, in this case, the Sched_context is specific to the Context/Thread, i.e. in this case a Context and Thread is the same thing and each Thread has its Sched_context. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, On 06/13/2014 10:01 PM, Adam Lackorzynski wrote:
You should look at the wfq files as those already implement an algorithm that is quite close to EDF I've found out that Weighted Fair Queuing is used for scheduling network data packets. However, no source I've read through mentions a similarity to EDF.
I'm not sure what all those parameters in sched_context-wfq.cpp mean. Quantum and weight seem clear to me, but what's the semantic of qdw (quantum divided by weight) and dl? Does the latter one stand for deadline? What sense does it make to add quantum/left attributes to a EDF-simliar algorithm? Another problem was arising when I tried to compile Fiasco with my EDF scheduler: I've removed the attributes quantum and left from my sched_context-edf.cpp implementation and got this error:
context.cpp:1039:49: error: ‘class Sched_context’ has no member named ‘left’ Obviously, Sched_context needs these parameters, but why? They are used in context.cpp which should be independent of any concrete scheduling algorithm, shouldn't it? There is no quantum in deadline based algorithms.
Best regards, Valentin
On Fri Aug 01, 2014 at 16:28:12 +0200, Valentin Hauner wrote:
On 06/13/2014 10:01 PM, Adam Lackorzynski wrote:
You should look at the wfq files as those already implement an algorithm that is quite close to EDF I've found out that Weighted Fair Queuing is used for scheduling network data packets. However, no source I've read through mentions a similarity to EDF.
I'm not sure what all those parameters in sched_context-wfq.cpp mean. Quantum and weight seem clear to me, but what's the semantic of qdw (quantum divided by weight) and dl? Does the latter one stand for deadline? What sense does it make to add quantum/left attributes to a EDF-simliar algorithm?
I wanted to express that it is similar, goes into that direction. I did not want to say that it is there. Yes, dl is meant as a deadline there I think.
Another problem was arising when I tried to compile Fiasco with my EDF scheduler: I've removed the attributes quantum and left from my sched_context-edf.cpp implementation and got this error:
context.cpp:1039:49: error: ‘class Sched_context’ has no member named ‘left’ Obviously, Sched_context needs these parameters, but why? They are used in context.cpp which should be independent of any concrete scheduling algorithm, shouldn't it? There is no quantum in deadline based algorithms.
Being independent of any specific algorithm also means that the interface between the different algorithms and the generic code is so abstract that any algorithm can be plugged in. Maybe this is not the case, maybe it is. Anyway, left() tells the generic code how long a thread still has time to run. I think you'll also have a value to put in there, at least it should be known at which point in time a reevaluation of the situation should be done. The quantum value is not used in generic code so it seems ok to not supply it. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, On 08/05/2014 10:59 PM, Adam Lackorzynski wrote:
Anyway, left() tells the generic code how long a thread still has time to run. I think you'll also have a value to put in there, at least it should be known at which point in time a reevaluation of the situation should be done. OK, that makes sense. But there's still a problem: The scheduling mechanisms in Fiasco.OC (even those that are independent of any concrete scheduling algorithm) are timeslice-based, e.g. the method expired() in timeslice_timeout.cpp calls the requeue method of the ready queue: In the original fixed priority algorithm, the current context is requeued and rotated to the end (!) of the queue by the following line of code (in ready_queue_fp.cpp): prio_next[i->prio()].rotate_to(*++List::iter(i));
That makes sense in a timeslice based round robin scheduler, where the threads are executed by turns. But it does not make sense for EDF where the ready queue has to be sorted by deadlines in ascending order. Removing the line mentioned above from my EDF implementation stops the execution of the whole system: The last message I see on screen is
SIGMA0: Hello! Obviously, sigma0 is a regular, periodic task and is scheduled together with my example tasks. So no other task than sigma0 comes to execution, as no round robin mechanism takes place. What's your suggestion to fix this?
My second question is a short one: How can I pass individual arguments for my example tasks to the L4 system, e.g. individual deadlines? Each Sched_context object has a deadline attribute that is initialized to a default value at the moment. The following LUA script starts the two tasks hello1 and hello2:
-- Include L4 functionality require("L4");
-- Some shortcut for less typing local l = L4.default_loader;
l:start({ caps = { }, log = { "hello1", "blue" } }, "rom/hello1");
l:start({ caps = { }, log = { "hello2", "green" } }, "rom/hello2");
Where can I pass my deadlines here? Thanks again for your support! Best regards, Valentin Hauner
Hi, On Thu Aug 07, 2014 at 15:43:20 +0200, Valentin Hauner wrote:
On 08/05/2014 10:59 PM, Adam Lackorzynski wrote:
Anyway, left() tells the generic code how long a thread still has time to run. I think you'll also have a value to put in there, at least it should be known at which point in time a reevaluation of the situation should be done. OK, that makes sense. But there's still a problem: The scheduling mechanisms in Fiasco.OC (even those that are independent of any concrete scheduling algorithm) are timeslice-based, e.g. the method expired() in timeslice_timeout.cpp calls the requeue method of the ready queue: In the original fixed priority algorithm, the current context is requeued and rotated to the end (!) of the queue by the following line of code (in ready_queue_fp.cpp): prio_next[i->prio()].rotate_to(*++List::iter(i));
That makes sense in a timeslice based round robin scheduler, where the threads are executed by turns. But it does not make sense for EDF where the ready queue has to be sorted by deadlines in ascending order. Removing the line mentioned above from my EDF implementation stops the execution of the whole system: The last message I see on screen is
SIGMA0: Hello! Obviously, sigma0 is a regular, periodic task and is scheduled together with my example tasks. So no other task than sigma0 comes to execution, as no round robin mechanism takes place. What's your suggestion to fix this?
I'd assume that the ready queue also has moe because moe should be ready. Wouldn't, with a requeue, sigma0 moved behind moe now (next deadline of sigma0 is further away)? On the other side, sigma0 is not done with that single message, so it also should be continuing execution. Who's running when the output stops?
My second question is a short one: How can I pass individual arguments for my example tasks to the L4 system, e.g. individual deadlines? Each Sched_context object has a deadline attribute that is initialized to a default value at the moment. The following LUA script starts the two tasks hello1 and hello2:
-- Include L4 functionality require("L4");
-- Some shortcut for less typing local l = L4.default_loader;
l:start({ caps = { }, log = { "hello1", "blue" } }, "rom/hello1");
l:start({ caps = { }, log = { "hello2", "green" } }, "rom/hello2");
Where can I pass my deadlines here?
You add l:start({ ..., scheduler = L4.Env.user_factory:create(L4.Proto.Scheduler, ...), }, ...) statements. For the fixed-prio type, we add two numbers, giving upper limit and base (e.g. L4.Env.user_factory:create(L4.Proto.Scheduler, 10, 5). However, for using this in the lua scripting, you also need to adapt libkproxy. So for the start, I'd suggest you use the C/C++ interface and reconfig the main thread from the defaults just in your program. In your case, the numbers used have a different meaning of course. Passing them down to the kernel goes via Scheduler::run_thread. There's some support for different scheduling parameters in the kernel, you've probably seen 'union Sp'. You can probably squeeze it in there. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, On 08/11/2014 11:35 PM, Adam Lackorzynski wrote:
I'd assume that the ready queue also has moe because moe should be ready. Wouldn't, with a requeue, sigma0 moved behind moe now (next deadline of sigma0 is further away)? On the other side, sigma0 is not done with that single message, so it also should be continuing execution. Who's running when the output stops?
Are sigma0 and moe periodic tasks that are active as long as the whole system is up? Or are they just active during the init phase? In theory, the ready queue of a EDF scheduler isn't rotated, but contains all Sched_contexts sorted by their deadlines. Meanwhile, I have added a separate ready queue for my deadline based threads. So currently, there are two ready queues: One that contains all ordinary threads (sigma0, moe etc.) and one that contains my deadline based threads only. The ordinary ready queue is rotated with that method mentioned in my previous mail whenever a requeue request arrives. The deadline ready queue is not rotated. Adapted from your fp_wfq example, the thread to run next is determined as follows:
[...] Ready_queue_edf<E>::next_to_run() const { if (!deadlineRq.empty()) return deadlineRq.front();
return rq.front(); }
I.e. whenever there is a thread in my deadline ready queue, it is chosen for execution. However, the execution ends up with the following error:
[...] MOE: Hello world [...] MOE: loading 'rom/ned' [...] Ned: loading file: 'rom/hello.cfg' Inserted id:5 in ordinary rq! Inserted id:3 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:3 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:8 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:3 in ordinary rq!
Inserted id:9 with deadline=10 in deadlineRq (content of deadlineRq: 9->end)
Inserted id:8 in ordinary rq!
Got requeue call for id:9 - reinserted! ./kernel/fiasco/src/kern/thread-ipc.cpp:456: ASSERTION FAILED (!(state() & Thread_ipc_mask))
I'm assigning identification numbers to the threads in the order of their creation time. So my two threads launched in hello.cfg are those with id 9 and 11 (the latter does not appear in the example above). Consequently, Fiasco creates 8 kernel threads (?) before mine. Why does that assertion fail? Obviously, some of the kernel threads have to be executed before, but which? The ordinary ready queue will never become empty as it is a cyclic queue with rotation. Best regards, Valentin
On Tue Aug 12, 2014 at 10:05:46 +0200, Valentin Hauner wrote:
On 08/11/2014 11:35 PM, Adam Lackorzynski wrote:
I'd assume that the ready queue also has moe because moe should be ready. Wouldn't, with a requeue, sigma0 moved behind moe now (next deadline of sigma0 is further away)? On the other side, sigma0 is not done with that single message, so it also should be continuing execution. Who's running when the output stops?
Are sigma0 and moe periodic tasks that are active as long as the whole system is up? Or are they just active during the init phase?
Neither. They have an init phase and during run-time they handle client requests.
In theory, the ready queue of a EDF scheduler isn't rotated, but contains all Sched_contexts sorted by their deadlines. Meanwhile, I have added a separate ready queue for my deadline based threads. So currently, there are two ready queues: One that contains all ordinary threads (sigma0, moe etc.) and one that contains my deadline based threads only. The ordinary ready queue is rotated with that method mentioned in my previous mail whenever a requeue request arrives. The deadline ready queue is not rotated.
Adapted from your fp_wfq example, the thread to run next is determined as follows:
[...] Ready_queue_edf<E>::next_to_run() const { if (!deadlineRq.empty()) return deadlineRq.front();
return rq.front(); }
I.e. whenever there is a thread in my deadline ready queue, it is chosen for execution. However, the execution ends up with the following error:
Ok, good approach.
[...] MOE: Hello world [...] MOE: loading 'rom/ned' [...] Ned: loading file: 'rom/hello.cfg' Inserted id:5 in ordinary rq! Inserted id:3 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:3 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:8 in ordinary rq! Inserted id:4 in ordinary rq! Inserted id:3 in ordinary rq!
Inserted id:9 with deadline=10 in deadlineRq (content of deadlineRq: 9->end)
Inserted id:8 in ordinary rq!
Got requeue call for id:9 - reinserted! ./kernel/fiasco/src/kern/thread-ipc.cpp:456: ASSERTION FAILED (!(state() & Thread_ipc_mask))
I'm assigning identification numbers to the threads in the order of their creation time. So my two threads launched in hello.cfg are those with id 9 and 11 (the latter does not appear in the example above). Consequently, Fiasco creates 8 kernel threads (?) before mine. Why does that assertion fail?
The assertion says that when starting an IPC, none of the IPC-related thread state flags must be enabled. Print state() before the assertion to know which one and get some more info.
Obviously, some of the kernel threads have to be executed before, but which? The ordinary ready queue will never become empty as it is a cyclic queue with rotation.
When I boot pure hello, I get 4 + num_cpus threads (sigma0, moe, hello and hello's l4re_kernel, plus one idler per CPU). With ned it's two more. How many CPU's do you have? And look at 'lp' in the jdb to get an overview. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, thanks, that makes things much clearer to me. On 08/13/2014 10:23 PM, Adam Lackorzynski wrote:
The assertion says that when starting an IPC, none of the IPC-related thread state flags must be enabled. Print state() before the assertion to know which one and get some more info.
Before the assertion fails, bit #3 of the state flags is set (decimal: 8). Unfortunately, I cannot find any documentation of that state flags. Where do I have to look? Execution stops with thread with dbg_id 3a. 'lp' prints the information attached to this mail. 3a seems to wait for something, but what is '1s'? By the way, what are those threads with no name (i.e. containing dashes in the 'name' column)? Best regards, Valentin
On Thu Aug 14, 2014 at 00:30:59 +0200, Valentin Hauner wrote:
thanks, that makes things much clearer to me.
On 08/13/2014 10:23 PM, Adam Lackorzynski wrote:
The assertion says that when starting an IPC, none of the IPC-related thread state flags must be enabled. Print state() before the assertion to know which one and get some more info.
Before the assertion fails, bit #3 of the state flags is set (decimal: 8). Unfortunately, I cannot find any documentation of that state flags. Where do I have to look?
Thread states are defined in thread_state.cpp. Bit 3 is Thread_receive_wait, so it is waiting already.
Execution stops with thread with dbg_id 3a. 'lp' prints the information attached to this mail. 3a seems to wait for something, but what is '1s'?
3a is one of the hello threads. The thread waits for itself, with a one second timeout (that's the 1s), so basically it does a sleep(1).
By the way, what are those threads with no name (i.e. containing dashes in the 'name' column)?
That are those where nobody has set a name. In the 'sp' (space) column you see to which task they belong. When you trace a bit in do_ipc, does 3a enter do_ipc multiple times? Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
Hi, On 08/14/2014 11:22 PM, Adam Lackorzynski wrote:
3a is one of the hello threads. The thread waits for itself, with a one second timeout (that's the 1s), so basically it does a sleep(1).
You were right. My hello application was printing "Hello World" ten times, with a sleep after each output. I've removed this sleep call, and things are looking better now: 'hello' prints its message ten times, as it is supposed to. However, after it is finished, 'hello2' isn't executed, but nothing happens (see first attachment). I've added a call of enter_kdebug() to the main function of 'hello' just before it ends, the second attachment contains the output of the thread list at this point. As I have written in a previous mail, I'm starting 'hello' and 'hello2' in 'hello.cfg'. I've changed your fp_wfq example to an fp_edf implementation and both threads are set to my type 'Deadline' (analogous to your type 'Wfq'). At the moment, this happens statically, i.e. the assignment of types & deadlines is done in the constructor of the Sched_context class (I'm aware that this is not state of the art). All Sched_contexts with type 'Deadline' are added to my EDF ready queue, all others to the FP ready queue.
Sched_context::Sched_context(unsigned short no) { if (no == 9 || no == 11) { printf("Created Sched_context object with type:Deadline (no. %d)\n", no); _t = Deadline; if (no == 9) _sc.edf._dl = 10; if (no == 11) _sc.edf._dl = 20; } else { _t = Fixed_prio; [...] } }
'no' is just a counter, i.e. no. 9 means that it's the 9th Sched_context object created (it's just an auxiliary construction as I cannot access the dbg_id in the constructor). The dbg_id of thread with no. 9 respectively 11 are 3a respectively 41. Is it neccessary to enqueue the threads with dbg_id 34 (#hello) and 3e (#hello2) in the EDF ready queue, too? At the moment, they are ordinary FP threads. If I change their types to 'Deadline', the following happens:
[...] Enqueuing Sched_context object in edf_rq (cid:34) Trying to insert cid:34... - inserted, same deadline: 9 Enqueuing Sched_context object in edf_rq (cid:34) Trying to insert cid:34... - inserted, same deadline: 9 Thread_ipc_mask: 28 ; state flags: 0000000000001001 ./kernel/fiasco/src/kern/thread-ipc.cpp:464: ASSERTION FAILED (!(state() & Thread_ipc_mask))
Interesting is the thread list entry for #hello:
id cpu name pr sp wait to state [...] 34 0 #hello 0 33 a ready,rcv_wait
#hello seems to wait for moe, which does not come to execution because FP threads ain't be executed as long as my EDF ready queue contains elements. Sorry for this voluminous mail and thanks again for your support! Best regards, Valentin
Hi, I've solved the problem explained in my mail from August 15th. There was a bug in my implementation of 'Ready_queue_edf::dequeue' so that a thread which already finished didn't get removed properly from the queue. By the way, what's the exact meaning of the attribute named '_ready_link' in your fp_wfq implementation? As far as I got it, it's set to 0 if the Sched_context is idle and it's set to the address of the enqueued Sched_context if it is not idle. However, the second question in my mail from August 15th is still relevant: Shall I enqueue the threads with dbg_id 34 (#hello) and 3e (#hello2) in the EDF ready queue, too? At the moment, they are ordinary FP threads. On 08/11/2014 11:35 PM, Adam Lackorzynski wrote:
You add l:start({ ..., scheduler = L4.Env.user_factory:create(L4.Proto.Scheduler, ...), }, ...) statements. For the fixed-prio type, we add two numbers, giving upper limit and base (e.g. L4.Env.user_factory:create(L4.Proto.Scheduler, 10, 5). However, for using this in the lua scripting, you also need to adapt libkproxy. So for the start, I'd suggest you use the C/C++ interface and reconfig the main thread from the defaults just in your program.
In your case, the numbers used have a different meaning of course. Passing them down to the kernel goes via Scheduler::run_thread. There's some support for different scheduling parameters in the kernel, you've probably seen 'union Sp'. You can probably squeeze it in there.
OK, my goal is to define the type (Fixed_prio or Deadline) for each thread directly in my LUA script. Depending on the type, it should be possible to pass the priority respectively the deadline for the thread. I guess that './l4/pkg/libkproxy/include/scheduler_svr' contains the code snippet that extracts the information supplied in the LUA script (lines 92-102, 'case L4_SCHEDULER_RUN_THREAD_OP'). Is that right? Unfortunately, I cannot find the base priority you mentioned. Furthermore, the struct 'L4_sched_param_fixed_prio' does not have attributes for 'affinity.offset' and 'affinity.granularity' that are set in scheduler_svr. I've tried your example with an upper limit of 10 and a base priority of 5 for my two tasks created in my LUA script, but the 'pr' column in the thread list of JDB still shows 1 for #hello and #hello2. Best regards, Valentin
On Fri Aug 15, 2014 at 11:29:11 +0200, Valentin Hauner wrote:
Sched_context::Sched_context(unsigned short no) { if (no == 9 || no == 11) { printf("Created Sched_context object with type:Deadline (no. %d)\n", no); _t = Deadline; if (no == 9) _sc.edf._dl = 10; if (no == 11) _sc.edf._dl = 20; } else { _t = Fixed_prio; [...] } }
'no' is just a counter, i.e. no. 9 means that it's the 9th Sched_context object created (it's just an auxiliary construction as I cannot access the dbg_id in the constructor). The dbg_id of thread with no. 9 respectively 11 are 3a respectively 41.
Is it neccessary to enqueue the threads with dbg_id 34 (#hello) and 3e (#hello2) in the EDF ready queue, too? At the moment, they are ordinary FP threads. If I change their types to 'Deadline', the following happens:
[...] Enqueuing Sched_context object in edf_rq (cid:34) Trying to insert cid:34... - inserted, same deadline: 9 Enqueuing Sched_context object in edf_rq (cid:34) Trying to insert cid:34... - inserted, same deadline: 9 Thread_ipc_mask: 28 ; state flags: 0000000000001001 ./kernel/fiasco/src/kern/thread-ipc.cpp:464: ASSERTION FAILED (!(state() & Thread_ipc_mask))
Interesting is the thread list entry for #hello:
id cpu name pr sp wait to state [...] 34 0 #hello 0 33 a ready,rcv_wait
#hello seems to wait for moe, which does not come to execution because FP threads ain't be executed as long as my EDF ready queue contains elements.
For me this setup looks like 34 queries something from moe (likely a memory mapping) because 35(?) page faulted. Which thread is still ready in this situation? With both hellos sleeping for 1s there should rarely be someone ready. Putting the two also in the EDF queue can not be the solution I think because IPC dependencies exist (may exist) throughout the system so that every thread (down the dependency graph) would end up there. Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
On Sun Aug 17, 2014 at 20:51:40 +0200, Valentin Hauner wrote:
I've solved the problem explained in my mail from August 15th. There was a bug in my implementation of 'Ready_queue_edf::dequeue' so that a thread which already finished didn't get removed properly from the queue.
Ok, good.
By the way, what's the exact meaning of the attribute named '_ready_link' in your fp_wfq implementation? As far as I got it, it's set to 0 if the Sched_context is idle and it's set to the address of the enqueued Sched_context if it is not idle.
Looks like _ready_link is used for implementing the ready list.
However, the second question in my mail from August 15th is still relevant: Shall I enqueue the threads with dbg_id 34 (#hello) and 3e (#hello2) in the EDF ready queue, too? At the moment, they are ordinary FP threads.
I replied to that now.
On 08/11/2014 11:35 PM, Adam Lackorzynski wrote:
You add l:start({ ..., scheduler = L4.Env.user_factory:create(L4.Proto.Scheduler, ...), }, ...) statements. For the fixed-prio type, we add two numbers, giving upper limit and base (e.g. L4.Env.user_factory:create(L4.Proto.Scheduler, 10, 5). However, for using this in the lua scripting, you also need to adapt libkproxy. So for the start, I'd suggest you use the C/C++ interface and reconfig the main thread from the defaults just in your program.
In your case, the numbers used have a different meaning of course. Passing them down to the kernel goes via Scheduler::run_thread. There's some support for different scheduling parameters in the kernel, you've probably seen 'union Sp'. You can probably squeeze it in there.
OK, my goal is to define the type (Fixed_prio or Deadline) for each thread directly in my LUA script. Depending on the type, it should be possible to pass the priority respectively the deadline for the thread.
I guess that './l4/pkg/libkproxy/include/scheduler_svr' contains the code snippet that extracts the information supplied in the LUA script (lines 92-102, 'case L4_SCHEDULER_RUN_THREAD_OP'). Is that right?
Yes, this code snippet is used to take the parameters out of the IPC of a Scheduler::run_thread call.
Unfortunately, I cannot find the base priority you mentioned.
That is done by calling create() with Proto=Scheduler on an appropriate Factory that in turn creates a Scheduler object with the created config. Now this describes it a bit too abstract maybe. The kernel factory does not support creating additional scheduler objects, that is, this is a user-level object only. The allocator/factory in moe is in moe/server/src/alloc.cc where you'll also find the creation of a Scheduler (Proxy) Object. The base and max values are extracted there and stored in the Sched_proxy object. For any run_thread call that goes through this Sched_proxy, the base and max values will be used to adjust the given prio.
Furthermore, the struct 'L4_sched_param_fixed_prio' does not have attributes for 'affinity.offset' and 'affinity.granularity' that are set in scheduler_svr.
Indeed. They are handled separately in the kernel's scheduler.cpp sys_run method.
I've tried your example with an upper limit of 10 and a base priority of 5 for my two tasks created in my LUA script, but the 'pr' column in the thread list of JDB still shows 1 for #hello and #hello2.
When implementing a new scheduler you might also need to adapt the functionality in jdb to properly show all values. I'm not sure this might be the problem here. Otherwise the prios show ok? Adam -- Adam adam@os.inf.tu-dresden.de Lackorzynski http://os.inf.tu-dresden.de/~adam/
participants (2)
-
Adam Lackorzynski -
Valentin Hauner