[LITMUS^RT] Questions on data struct bheap and rt_domain_t

[Christopher Kenna]

Hi Hang,

Regarding your first question, the bheap you are seeing is actually a
binomial heap, not a binary heap. More information can be found in one
of Bjoern's papers [1].

I think I will let someone with more expertise than myself answer your
second question. I just wanted to give you a fast response and
hopefully unblock you a bit.

 -- Chris

[1] B. Brandenburg and J. Anderson, “On the Implementation of Global
Real-Time Schedulers”, Proceedings of the 30th IEEE Real-Time Systems
Symposium (RTSS 2009), pp. 214-224. IEEE, December 2009.
http://www.mpi-sws.org/~bbb/papers/pdf/rtss09.pdf

On Tue, Mar 6, 2012 at 4:42 PM, Hang Su <hsu at cs.utsa.edu> wrote:
> Hi all:
>
> I have a couple of questions as described as followings:
>
> 1. struct bheap is binary heap and struct bheap_node represents each heap
> node in a heap, right ? A traditionally binary heap node could have up to
> two children, left one and right one. In struct bheap_node, I see its has
> next and child. Which is the corresponding left child and right child ? Or,
> child and sibling representation is used, so that a bheap_node only maintain
> its left child and its sibling. And degree represents how many children it
> has or what ?  In struct bheap, there are head and min. If it was a minimum
> heap, head and min should points to the same bheap_node, which is the heap
> root, after each bheap operation like insertion and deletion. When does they
> differs ?
>
> 2. In rt_domian.h, there is a struct rt_domain_t. What is the difference
> between release_queue and tobe_released. From the comments, they are all
> related to release queue. But i am a little bit confused about them. Inside
> requeue function in sched_gsn_edf.c, a task is linked in tobe_released
> instead of release_queue through calling add_release(&gsnedf,task), if it
> has not been released . If an example could be shown, it is pretty much
> clear for me. For example, we have a task set with two tasks, T1(c1,p1) =
> (3,5)  and T2(c2,p2)=(2,6). This task set will be scheduled on one processor
> by EDF. At time 0, both of their jobs are released. And the
> release_queue.slot[5] ,  release_queue.slot[10], ..., release_queue.slot[
> min( 5*i, RELEASE_QUEUE_SLOTS) ], maintain jobs from T1, which will be
> released within window-sized RELEASE_QUEUE_SLOTS.  is that right ?
>
>
> Thanks.
>
>
>
>
> _______________________________________________
> litmus-dev mailing list
> litmus-dev at lists.litmus-rt.org
> https://lists.litmus-rt.org/listinfo/litmus-dev
>