> This does not solve the problem of avoiding queue reordering in
I completely agree with this. The bit map needs to be modified for
dynamic priority changes. However, atomic operations (like
Compare-And-Swap) can be used to modify the bitmap. Barring any
(highly unlikely but bounded) contention scenarios from other
processors, this implementation would still continue to be efficient
than maintaining a priority-ordered queue.
We can still maintain the O(1) instruction-suspend/unsuspend, if we
maintain a counter for each priority level.
(a) When a task suspends on a lock, we can do an atomic increment of
the counter for its priority level and set the bit on the priority map
of tasks waiting for the lock. Attaching the task to a
per-priority-level linked list queue should take O(1) assuming that
there is a tail pointer.
(b) When the lock is released, find the highest priority bit set on
the lock's priority map, index into the appropriate per-priority-level
linked list, and wake up the task at the head of the queue (delete
operation with O(1)). Do an atomic decrement of the counter, if it
reaches zero unset the bit on the priority map.
While there are still contention issues that arise with updating the
linked list and counters, these are restricted to tasks within the
same priority level (highly unlikely that multiple tasks from the same
priority level decide to acquire the same lock within a window of a
couple of instructions), and should be much less than the contention
arising from all the tasks in the system.
Yes. I did not think about EDF based schedulers when I proposed the
implementation mechanism. I believe we can work on the SRP idea to get
a corresponding version for EDF.
I agree that there needs to be more work to generalize the idea to EDF
based schedulers on SMP, however, the idea still applies to
fixed-priority scheduling in the SMP context. Many SMP processors
support atomic instructions (for example:
http://software.intel.com/en-us/articles/implementing-scalable-atomic-locks-for-multi-...).
We can utilize these instructions to efficiently implement such locks
at least in fixed-priority schedulers (like Deadline Monotonic
Schedulers) for SMP systems.
Thanks
- Karthik
--
