Re: Why Completely Fair Scheduler(CFS) using Red-Black tree instead of Min-heap?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 





On Sat, Oct 17, 2015 at 11:25 AM, venu gangireddy <venu.gangireddy@xxxxxxxxx> wrote:
Hi,

Currently, I am learning about CFS scheduler in linux, and I want to know reason about the data structure chooses in CFS implementation.

Nice. 
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?

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.


Thanks in advance.

--
Regards,
Venugopal Reddy.

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@xxxxxxxxxxxxxxxxx
http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies


_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@xxxxxxxxxxxxxxxxx
http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

[Index of Archives]     [Newbies FAQ]     [Linux Kernel Mentors]     [Linux Kernel Development]     [IETF Annouce]     [Git]     [Networking]     [Security]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux RAID]     [Linux SCSI]     [Linux ACPI]
  Powered by Linux