The implementation of CPU reservation server

Udo A. Steinberg udo at
Mon Jun 1 20:31:42 CEST 2009

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> 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> If Group A is eligible in the time interval {0~3 }, Group B is {3~4}, and
S> Group C is {5~8}.
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

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.


	- Udo
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: not available
URL: <>

More information about the l4-hackers mailing list