lkml.org 
[lkml]   [2009]   [Jul]   [16]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: RFC for a new Scheduling policy/class in the Linux-kernel
From
> I still conceptually prefer the idea of granting locks to
> contending tasks in priority order, of course.  It is just a
> question of whether you want to have to agree (1) that all
> scheduling is based on priority, and (2) pay the price for either
> (2a) dynamically re-ordering all those queues every time a task
> gains or loses priority (due to inheritance, or whatever), or (2b)
> pay the O(n) price of scanning the queue for the currently
> highest-priority task when you grant the lock.  If you go this
> way, I would favor the latter.  In any system that does not
> already have poor performance due to excessive lock contention,
> the queues should rarely have more than one member.  Assuming
> integrity of the queue is maintained by the corresponding lock
> itself, it is much easier to do this scanning at the point the
> lock is released than to support (asynchronous) queue reordering
> for every potential priority change.
>
Just chiming in that from an implementation perspective, we could use
a priority bitmap of active tasks contending for the lock. An
implementation similar to the one used by the O(1) scheduler can be of
great use here. Hardware support like "find_first_bit" can drastically
reduce the time taken to search for the highest-priority task pending
on the lock. Given realistic values for the number of distinct
priority values required by most practical systems, such an
implementation could prove effective.

Thanks,
Karthik
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2009-07-17 00:37    [W:0.401 / U:1.024 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site