<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Oct 17, 2015 at 11:25 AM, venu gangireddy <span dir="ltr"><<a href="mailto:venu.gangireddy@gmail.com" target="_blank">venu.gangireddy@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>Hi,<br><br>Currently, I am learning about CFS scheduler in linux, and I want to know reason about the data structure chooses in CFS implementation.<br><br></div></div></blockquote><div>Nice. </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>CFS scheduler picks next process based on minimum virtual time and to get
this value efficiently its using Red-Black tree(rbtree), using rbtree
we will get minimum O(h) here h is height of rbtree. But, using min-heap
we can get min virtual time process in O(1) time only. I just want to
know why min-heap is not consider in CFS implementation and is there any
difficulties using min-heap in kernel level? </div></div></blockquote><div><br></div><div><span style="font-family:'Helvetica Neue',Helvetica,Arial,sans-serif;font-size:13px;line-height:16.9px">I am not an expert in algorithms, but it seems that after o(1) peek you should perform heapify (which is o(log n)) to restore heap property. So give the reference to the implementation you talking about if I am wrong.</span></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div> <br><br>Thanks in advance.
</div><span class=""><font color="#888888"><div><br><div>-- <br><div><div dir="ltr"><div><b>Regards,<br></b></div><b>Venugopal Reddy.</b><br></div></div>
</div></div></font></span></div>
<br>_______________________________________________<br>
Kernelnewbies mailing list<br>
<a href="mailto:Kernelnewbies@kernelnewbies.org">Kernelnewbies@kernelnewbies.org</a><br>
<a href="http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies" rel="noreferrer" target="_blank">http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies</a><br>
<br></blockquote></div><br></div></div>