The implementation of CPU reservation server

Sean sean0920 at
Tue Jun 2 20:25:15 CEST 2009


Thanks very much for your useful suggestion!!

On Tue, Jun 2, 2009 at 2:31 AM, Udo A. Steinberg <udo at> 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:
> 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.

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

Can you give me any idea about it?
I'm sorry if I got into wrong direction or got wrong understanding of

Thanks very much!!

Best Regards,

> 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 at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the l4-hackers mailing list