From: anish198519851985@gmail.com (anish singh)
To: kernelnewbies@lists.kernelnewbies.org
Subject: Why Completely Fair Scheduler(CFS) using Red-Black tree instead of Min-heap?
Date: Sun, 18 Oct 2015 00:35:32 -0700 [thread overview]
Message-ID: <CAK7N6vobYrbRh6daV5hF9bBEV02W=8Xuj4aQZgn=2MXyXbncsw@mail.gmail.com> (raw)
In-Reply-To: <CAHmFiJDD7HTvYfNzd55s7hXgNbE1xTvKCT6Vf7B9zOVT8x-1PA@mail.gmail.com>
On Sat, Oct 17, 2015 at 11:25 AM, venu gangireddy <venu.gangireddy@gmail.com
> 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 at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20151018/1696f7c1/attachment.html
prev parent reply other threads:[~2015-10-18 7:35 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-10-17 18:25 Why Completely Fair Scheduler(CFS) using Red-Black tree instead of Min-heap? venu gangireddy
2015-10-18 6:55 ` Nicholas Mc Guire
2015-10-18 7:35 ` anish singh [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAK7N6vobYrbRh6daV5hF9bBEV02W=8Xuj4aQZgn=2MXyXbncsw@mail.gmail.com' \
--to=anish198519851985@gmail.com \
--cc=kernelnewbies@lists.kernelnewbies.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).