[haiku-commits] BRANCH pdziepak-github.scheduler [da3a48f] headers/private/kernel/util src/system/kernel/scheduler
- From: pdziepak-github.scheduler <community@xxxxxxxxxxxx>
- To: haiku-commits@xxxxxxxxxxxxx
- Date: Thu, 17 Oct 2013 19:30:37 +0200 (CEST)
added 3 changesets to branch 'refs/remotes/pdziepak-github/scheduler'
old head: 3ec1d8da429b162235dc0f5e4023cc71cdc0533f
new head: da3a48f4a8a723322ad53f06fddf945a7c38ea3d
overview: https://github.com/pdziepak/Haiku/compare/3ec1d8d...da3a48f
----------------------------------------------------------------------------
278c978: scheduler_affine: Use global core heap and per-core CPU heaps
There is a global heap of cores, where the key is the highest priority
of threads running on that core. Moreover, for each core there is
a heap of logical processors on this core where the key is the priority
of currently running thread.
The per-core heap is used for load balancing among logical processors
on that core. The global heap is used in initial decision where to put
the thread (note that the algorithm that makes this decision is not
complete yet).
18c0d16: kernel/util: Add MinMaxHeap implementation
da3a48f: scheduler_affine: Use min-max heap as per-core CPU heap
[ Pawel Dziepak <pdziepak@xxxxxxxxxxx> ]
----------------------------------------------------------------------------
3 files changed, 663 insertions(+), 82 deletions(-)
headers/private/kernel/util/Heap.h | 14 +-
headers/private/kernel/util/MinMaxHeap.h | 478 +++++++++++++++++++
src/system/kernel/scheduler/scheduler_affine.cpp | 253 +++++++---
############################################################################
Commit: 278c9784a13e80068e7ab97ffd9feb27b98e17d6
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Wed Oct 16 23:50:14 2013 UTC
scheduler_affine: Use global core heap and per-core CPU heaps
There is a global heap of cores, where the key is the highest priority
of threads running on that core. Moreover, for each core there is
a heap of logical processors on this core where the key is the priority
of currently running thread.
The per-core heap is used for load balancing among logical processors
on that core. The global heap is used in initial decision where to put
the thread (note that the algorithm that makes this decision is not
complete yet).
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/Heap.h
b/headers/private/kernel/util/Heap.h
index cca75c7..653e4b0 100644
--- a/headers/private/kernel/util/Heap.h
+++ b/headers/private/kernel/util/Heap.h
@@ -79,7 +79,7 @@ public:
inline Element* PeekRoot();
- inline const Key& GetKey(Element* element) const;
+ static const Key& GetKey(Element* element);
inline void ModifyKey(Element* element, Key newKey);
@@ -96,9 +96,8 @@ private:
int fLastElement;
int fSize;
- Compare sCompare;
- GetLink sGetLink;
-
+ static Compare sCompare;
+ static GetLink sGetLink;
};
@@ -187,12 +186,9 @@ HEAP_CLASS_NAME::PeekRoot()
HEAP_TEMPLATE_LIST
const Key&
-HEAP_CLASS_NAME::GetKey(Element* element) const
+HEAP_CLASS_NAME::GetKey(Element* element)
{
- HeapLink<Element, Key>* link = sGetLink(element);
-
- ASSERT(link->fIndex >= 0 && link->fIndex < fLastElement);
- return link->fKey;
+ return sGetLink(element)->fKey;
}
diff --git a/src/system/kernel/scheduler/scheduler_affine.cpp
b/src/system/kernel/scheduler/scheduler_affine.cpp
index d370847..b1667bf 100644
--- a/src/system/kernel/scheduler/scheduler_affine.cpp
+++ b/src/system/kernel/scheduler/scheduler_affine.cpp
@@ -49,20 +49,35 @@ const bigtime_t kMaxThreadQuantum = 10000;
struct CPUHeapEntry : public HeapLinkImpl<CPUHeapEntry, int32> {
+ HeapLink<CPUHeapEntry, int32> fMaxHeap;
int32 fCPUNumber;
};
-static CPUHeapEntry* sCPUEntries;
+static CPUHeapEntry* sCPUPriorityEntries;
typedef Heap<CPUHeapEntry, int32> AffineCPUHeap;
-static AffineCPUHeap* sCPUHeap;
+typedef Heap<CPUHeapEntry, int32, HeapGreaterCompare<int32>,
+ HeapMemberGetLink<CPUHeapEntry, int32, &CPUHeapEntry::fMaxHeap>
>
+ AffineCPUMaxHeap;
+
+// TODO: Use one min-max heap per-core
+static AffineCPUHeap* sCPUPriorityHeaps;
+static AffineCPUMaxHeap* sCPUMaxPriorityHeaps;
+
+struct CoreHeapEntry : public HeapLinkImpl<CoreHeapEntry, int32> {
+ int32 fCoreID;
+};
+
+static CoreHeapEntry* sCorePriorityEntries;
+typedef Heap<CoreHeapEntry, int32> AffineCoreHeap;
+static AffineCoreHeap* sCorePriorityHeap;
// The run queues. Holds the threads ready to run ordered by priority.
// One queue per schedulable target per core. Additionally, each
-// logical processor has its sCPURunQueues used for scheduling
+// logical processor has its sPinnedRunQueues used for scheduling
// pinned threads.
typedef RunQueue<Thread, THREAD_MAX_SET_PRIORITY> AffineRunQueue;
static AffineRunQueue* sRunQueues;
-static AffineRunQueue* sCPURunQueues;
+static AffineRunQueue* sPinnedRunQueues;
static int32 sRunQueueCount;
static int32* sCPUToCore;
@@ -181,7 +196,7 @@ dump_run_queue(int argc, char **argv)
}
for (int32 i = 0; i < cpuCount; i++) {
- iterator = sCPURunQueues[i].GetConstIterator();
+ iterator = sPinnedRunQueues[i].GetConstIterator();
if (iterator.HasNext()) {
kprintf("\nCPU %" B_PRId32 " run queue:\n", i);
@@ -193,25 +208,64 @@ dump_run_queue(int argc, char **argv)
}
-static int
-dump_cpu_heap(int argc, char** argv)
+static void
+dump_heap(AffineCPUHeap* heap)
{
+ AffineCPUHeap temp;
+
kprintf("cpu priority actual priority\n");
- CPUHeapEntry* entry = sCPUHeap->PeekRoot();
+ CPUHeapEntry* entry = heap->PeekRoot();
while (entry) {
int32 cpu = entry->fCPUNumber;
- kprintf("%3" B_PRId32 " %8" B_PRId32 " %15" B_PRId32 "\n", cpu,
- sCPUHeap->GetKey(entry),
+ int32 key = AffineCPUHeap::GetKey(entry);
+ kprintf("%3" B_PRId32 " %8" B_PRId32 " %15" B_PRId32 "\n", cpu,
key,
affine_get_effective_priority(gCPU[cpu].running_thread));
- sCPUHeap->RemoveRoot();
- entry = sCPUHeap->PeekRoot();
+ heap->RemoveRoot();
+ temp.Insert(entry, key);
+
+ entry = heap->PeekRoot();
}
- int32 cpuCount = smp_get_num_cpus();
- for (int i = 0; i < cpuCount; i++) {
- sCPUHeap->Insert(&sCPUEntries[i],
- affine_get_effective_priority(gCPU[i].running_thread));
+ entry = temp.PeekRoot();
+ while (entry) {
+ int32 key = AffineCPUHeap::GetKey(entry);
+ temp.RemoveRoot();
+ heap->Insert(entry, key);
+ entry = temp.PeekRoot();
+ }
+}
+
+
+static int
+dump_cpu_heap(int argc, char** argv)
+{
+ AffineCoreHeap temp;
+
+ kprintf("core priority\n");
+ CoreHeapEntry* entry = sCorePriorityHeap->PeekRoot();
+ while (entry) {
+ int32 core = entry->fCoreID;
+ int32 key = AffineCoreHeap::GetKey(entry);
+ kprintf("%4" B_PRId32 " %8" B_PRId32 "\n", core, key);
+
+ sCorePriorityHeap->RemoveRoot();
+ temp.Insert(entry, key);
+
+ entry = sCorePriorityHeap->PeekRoot();
+ }
+
+ entry = temp.PeekRoot();
+ while (entry) {
+ int32 key = AffineCoreHeap::GetKey(entry);
+ temp.RemoveRoot();
+ sCorePriorityHeap->Insert(entry, key);
+ entry = temp.PeekRoot();
+ }
+
+ for (int32 i = 0; i < sRunQueueCount; i++) {
+ kprintf("\nCore %" B_PRId32 " heap:\n", i);
+ dump_heap(&sCPUPriorityHeaps[i]);
}
return 0;
@@ -295,6 +349,41 @@ affine_get_most_idle_cpu()
#endif
+static inline void
+affine_update_priority_heaps(int32 cpu, int32 priority)
+{
+ int32 core = sCPUToCore[cpu];
+
+ sCPUPriorityHeaps[core].ModifyKey(&sCPUPriorityEntries[cpu], priority);
+ sCPUMaxPriorityHeaps[core].ModifyKey(&sCPUPriorityEntries[cpu],
priority);
+
+ int32 maxPriority
+ =
AffineCPUMaxHeap::GetKey(sCPUMaxPriorityHeaps[core].PeekRoot());
+ int32 corePriority =
AffineCoreHeap::GetKey(&sCorePriorityEntries[core]);
+
+ if (corePriority != maxPriority)
+ sCorePriorityHeap->ModifyKey(&sCorePriorityEntries[core],
maxPriority);
+}
+
+
+static inline int32
+affine_choose_core(void)
+{
+ CoreHeapEntry* entry = sCorePriorityHeap->PeekRoot();
+ ASSERT(entry != NULL);
+ return entry->fCoreID;
+}
+
+
+static inline int32
+affine_choose_cpu(int32 core)
+{
+ CPUHeapEntry* entry = sCPUPriorityHeaps[core].PeekRoot();
+ ASSERT(entry != NULL);
+ return entry->fCPUNumber;
+}
+
+
static void
affine_enqueue(Thread* thread, bool newOne)
{
@@ -323,23 +412,19 @@ affine_enqueue(Thread* thread, bool newOne)
targetCPU = idleThreads++;
targetCore = sCPUToCore[targetCPU];
} else {
- CPUHeapEntry* cpuEntry = sCPUHeap->PeekRoot();
- ASSERT(cpuEntry != NULL);
-
- targetCPU = cpuEntry->fCPUNumber;
- targetCore = sCPUToCore[targetCPU];
+ targetCore = affine_choose_core();
+ targetCPU = affine_choose_cpu(targetCore);
}
schedulerThreadData->previous_core = targetCore;
} else {
- targetCPU = thread->previous_cpu->cpu_num;
- targetCore = sCPUToCore[targetCPU];
- ASSERT(targetCore == schedulerThreadData->previous_core);
+ targetCore = schedulerThreadData->previous_core;
+ targetCPU = affine_choose_cpu(targetCore);
}
TRACE("enqueueing thread %ld with priority %ld %ld\n", thread->id,
threadPriority, targetCore);
if (pinned)
- sCPURunQueues[targetCPU].PushBack(thread, threadPriority);
+ sPinnedRunQueues[targetCPU].PushBack(thread, threadPriority);
else
sRunQueues[targetCore].PushBack(thread, threadPriority);
@@ -363,7 +448,7 @@ affine_enqueue(Thread* thread, bool newOne)
// It is possible that another CPU schedules the thread before
the
// target CPU. However, since the target CPU is sent an ICI it
will
// reschedule anyway and update its heap key to the correct
value.
- sCPUHeap->ModifyKey(&sCPUEntries[targetCPU], threadPriority);
+ affine_update_priority_heaps(targetCPU, threadPriority);
if (targetCPU == smp_get_current_cpu()) {
gCPU[targetCPU].invoke_scheduler = true;
@@ -391,11 +476,11 @@ affine_enqueue_in_run_queue(Thread *thread)
static inline void
affine_put_back(Thread* thread)
{
- bool pinned = sCPURunQueues != NULL && thread->pinned_to_cpu > 0;
+ bool pinned = sPinnedRunQueues != NULL && thread->pinned_to_cpu > 0;
if (pinned) {
int32 pinnedCPU = thread->previous_cpu->cpu_num;
- sCPURunQueues[pinnedCPU].PushFront(thread,
+ sPinnedRunQueues[pinnedCPU].PushFront(thread,
affine_get_effective_priority(thread));
} else {
int32 previousCore = thread->scheduler_data->previous_core;
@@ -492,7 +577,7 @@ affine_set_thread_priority(Thread *thread, int32 priority)
affine_get_effective_priority(thread));
if (thread->state == B_THREAD_RUNNING)
- sCPUHeap->ModifyKey(&sCPUEntries[thread->cpu->cpu_num],
priority);
+ affine_update_priority_heaps(thread->cpu->cpu_num, priority);
if (thread->state != B_THREAD_READY) {
affine_cancel_penalty(thread);
@@ -637,8 +722,8 @@ affine_dequeue_thread(int32 thisCPU)
Thread* sharedThread = sRunQueues[thisCore].PeekMaximum();
Thread* pinnedThread = NULL;
- if (sCPURunQueues != NULL)
- pinnedThread = sCPURunQueues[thisCPU].PeekMaximum();
+ if (sPinnedRunQueues != NULL)
+ pinnedThread = sPinnedRunQueues[thisCPU].PeekMaximum();
if (sharedThread == NULL && pinnedThread == NULL)
return NULL;
@@ -656,7 +741,7 @@ affine_dequeue_thread(int32 thisCPU)
return sharedThread;
}
- sCPURunQueues[thisCPU].Remove(pinnedThread);
+ sPinnedRunQueues[thisCPU].Remove(pinnedThread);
return pinnedThread;
}
@@ -692,7 +777,7 @@ affine_reschedule(void)
// update CPU heap so that old thread would have CPU properly chosen
Thread* nextThread = sRunQueues[thisCore].PeekMaximum();
if (nextThread != NULL) {
- sCPUHeap->ModifyKey(&sCPUEntries[thisCPU],
+ affine_update_priority_heaps(thisCPU,
affine_get_effective_priority(nextThread));
}
@@ -735,10 +820,10 @@ affine_reschedule(void)
// select thread with the biggest priority
if (oldThread->cpu->disabled) {
- ASSERT(sCPURunQueues != NULL);
- nextThread = sCPURunQueues[thisCPU].PeekMaximum();
+ ASSERT(sPinnedRunQueues != NULL);
+ nextThread = sPinnedRunQueues[thisCPU].PeekMaximum();
if (nextThread != NULL)
- sCPURunQueues[thisCPU].Remove(nextThread);
+ sPinnedRunQueues[thisCPU].Remove(nextThread);
else {
nextThread =
sRunQueues[thisCore].GetHead(B_IDLE_PRIORITY);
if (nextThread != NULL)
@@ -759,7 +844,7 @@ affine_reschedule(void)
oldThread, nextThread);
// update CPU heap
- sCPUHeap->ModifyKey(&sCPUEntries[thisCPU],
+ affine_update_priority_heaps(thisCPU,
affine_get_effective_priority(nextThread));
nextThread->state = B_THREAD_RUNNING;
@@ -857,41 +942,12 @@ scheduler_affine_init()
{
int32 cpuCount = smp_get_num_cpus();
- sCPUHeap = new AffineCPUHeap;
- if (sCPUHeap == NULL)
- return B_NO_MEMORY;
- ObjectDeleter<AffineCPUHeap> cpuHeapDeleter(sCPUHeap);
-
- sCPUEntries = new CPUHeapEntry[cpuCount];
- if (sCPUEntries == NULL)
- return B_NO_MEMORY;
- ArrayDeleter<CPUHeapEntry> cpuEntriesDeleter(sCPUEntries);
-
- for (int i = 0; i < cpuCount; i++) {
- sCPUEntries[i].fCPUNumber = i;
- status_t result = sCPUHeap->Insert(&sCPUEntries[i],
B_IDLE_PRIORITY);
- if (result != B_OK)
- return result;
- }
-
- TRACE("scheduler_affine_init(): creating %" B_PRId32 " per-cpu
queue%s\n",
- cpuCount, cpuCount != 1 ? "s" : "");
-
+ // create logical processor to core mapping
sCPUToCore = new(std::nothrow) int32[cpuCount];
if (sCPUToCore == NULL)
return B_NO_MEMORY;
ArrayDeleter<int32> cpuToCoreDeleter(sCPUToCore);
- sCPURunQueues = new(std::nothrow) AffineRunQueue[cpuCount];
- if (sCPURunQueues == NULL)
- return B_NO_MEMORY;
- ArrayDeleter<AffineRunQueue> cpuRunQueuesDeleter(sCPURunQueues);
- for (int i = 0; i < cpuCount; i++) {
- status_t result = sCPURunQueues[i].GetInitStatus();
- if (result != B_OK)
- return result;
- }
-
int32 coreCount = 0;
for (int32 i = 0; i < cpuCount; i++) {
if (gCPU[i].topology_id[CPU_TOPOLOGY_SMT] == 0)
@@ -926,6 +982,73 @@ scheduler_affine_init()
}
}
+ // create logical processor and core heaps
+ sCPUPriorityEntries = new CPUHeapEntry[cpuCount];
+ if (sCPUPriorityEntries == NULL)
+ return B_NO_MEMORY;
+ ArrayDeleter<CPUHeapEntry>
cpuPriorityEntriesDeleter(sCPUPriorityEntries);
+
+ sCorePriorityEntries = new CoreHeapEntry[coreCount];
+ if (sCorePriorityEntries == NULL)
+ return B_NO_MEMORY;
+ ArrayDeleter<CoreHeapEntry> corePriorityEntriesDeleter(
+ sCorePriorityEntries);
+
+ sCPUPriorityHeaps = new AffineCPUHeap[coreCount];
+ if (sCPUPriorityHeaps == NULL)
+ return B_NO_MEMORY;
+ ArrayDeleter<AffineCPUHeap> cpuPriorityHeapDeleter(sCPUPriorityHeaps);
+
+ sCPUMaxPriorityHeaps = new AffineCPUMaxHeap[coreCount];
+ if (sCPUMaxPriorityHeaps == NULL)
+ return B_NO_MEMORY;
+ ArrayDeleter<AffineCPUMaxHeap> cpuMaxPriorityHeapDeleter(
+ sCPUMaxPriorityHeaps);
+
+ for (int32 i = 0; i < cpuCount; i++) {
+ sCPUPriorityEntries[i].fCPUNumber = i;
+ int32 core = sCPUToCore[i];
+
+ status_t result
+ =
sCPUPriorityHeaps[core].Insert(&sCPUPriorityEntries[i],
+ B_IDLE_PRIORITY);
+ if (result != B_OK)
+ return result;
+
+ result =
sCPUMaxPriorityHeaps[core].Insert(&sCPUPriorityEntries[i],
+ B_IDLE_PRIORITY);
+ if (result != B_OK)
+ return result;
+ }
+
+ sCorePriorityHeap = new AffineCoreHeap;
+ if (sCorePriorityHeap == NULL)
+ return B_NO_MEMORY;
+ ObjectDeleter<AffineCoreHeap>
corePriorityHeapDeleter(sCorePriorityHeap);
+
+ for (int32 i = 0; i < coreCount; i++) {
+ sCorePriorityEntries[i].fCoreID = i;
+ status_t result =
sCorePriorityHeap->Insert(&sCorePriorityEntries[i],
+ B_IDLE_PRIORITY);
+ if (result != B_OK)
+ return result;
+ }
+
+ // create per-logical processor run queues for pinned threads
+ TRACE("scheduler_affine_init(): creating %" B_PRId32 " per-cpu
queue%s\n",
+ cpuCount, cpuCount != 1 ? "s" : "");
+
+ sPinnedRunQueues = new(std::nothrow) AffineRunQueue[cpuCount];
+ if (sPinnedRunQueues == NULL)
+ return B_NO_MEMORY;
+ ArrayDeleter<AffineRunQueue> pinnedRunQueuesDeleter(sPinnedRunQueues);
+ for (int i = 0; i < cpuCount; i++) {
+ status_t result = sPinnedRunQueues[i].GetInitStatus();
+ if (result != B_OK)
+ return result;
+ }
+
+ // create per-core run queues
TRACE("scheduler_affine_init(): creating %" B_PRId32 " per-core
queue%s\n",
coreCount, coreCount != 1 ? "s" : "");
@@ -947,10 +1070,13 @@ scheduler_affine_init()
"List CPUs in CPU priority heap", "\nList CPUs in CPU priority
heap",
0);
- cpuHeapDeleter.Detach();
- cpuEntriesDeleter.Detach();
- cpuToCoreDeleter.Detach();
- cpuRunQueuesDeleter.Detach();
runQueuesDeleter.Detach();
+ pinnedRunQueuesDeleter.Detach();
+ corePriorityHeapDeleter.Detach();
+ cpuMaxPriorityHeapDeleter.Detach();
+ cpuPriorityHeapDeleter.Detach();
+ corePriorityEntriesDeleter.Detach();
+ cpuPriorityEntriesDeleter.Detach();
+ cpuToCoreDeleter.Detach();
return B_OK;
}
############################################################################
Commit: 18c0d163ede074f15215e2c9caec15ae4cbd0f26
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Thu Oct 17 17:22:29 2013 UTC
kernel/util: Add MinMaxHeap implementation
----------------------------------------------------------------------------
diff --git a/headers/private/kernel/util/MinMaxHeap.h
b/headers/private/kernel/util/MinMaxHeap.h
new file mode 100644
index 0000000..0727a85
--- /dev/null
+++ b/headers/private/kernel/util/MinMaxHeap.h
@@ -0,0 +1,478 @@
+/*
+ * Copyright 2013 Haiku, Inc. All rights reserved.
+ * Distributed under the terms of the MIT License.
+ *
+ * Authors:
+ * Paweł Dziepak, pdziepak@xxxxxxxxxxx
+ */
+#ifndef KERNEL_UTIL_MIN_MAX_HEAP_H
+#define KERNEL_UTIL_MIN_MAX_HEAP_H
+
+
+#include <debug.h>
+
+#include <SupportDefs.h>
+
+
+template<typename Element, typename Key>
+struct MinMaxHeapLink {
+ MinMaxHeapLink();
+
+ bool fMinTree;
+ int fIndex;
+ Key fKey;
+};
+
+template<typename Element, typename Key>
+class MinMaxHeapLinkImpl {
+private:
+ typedef MinMaxHeapLink<Element, Key> Link;
+
+public:
+ inline Link* GetMinMaxHeapLink();
+
+private:
+ Link fMinMaxHeapLink;
+};
+
+template<typename Element, typename Key>
+class MinMaxHeapStandardGetLink {
+private:
+ typedef MinMaxHeapLink<Element, Key> Link;
+
+public:
+ inline Link* operator()(Element* element) const;
+};
+
+template<typename Element, typename Key,
+ MinMaxHeapLink<Element, Key> Element::*LinkMember>
+class MinMaxHeapMemberGetLink {
+private:
+ typedef MinMaxHeapLink<Element, Key> Link;
+
+public:
+ inline Link* operator()(Element* element) const;
+};
+
+template<typename Key>
+class MinMaxHeapCompare {
+public:
+ inline bool operator()(Key a, Key b);
+};
+
+#define MIN_MAX_HEAP_TEMPLATE_LIST \
+ template<typename Element, typename Key, typename Compare, typename
GetLink>
+#define MIN_MAX_HEAP_CLASS_NAME MinMaxHeap<Element, Key, Compare,
GetLink>
+
+template<typename Element, typename Key,
+ typename Compare = MinMaxHeapCompare<Key>,
+ typename GetLink = MinMaxHeapStandardGetLink<Element, Key> >
+class MinMaxHeap {
+public:
+ MinMaxHeap();
+ ~MinMaxHeap();
+
+ inline Element* PeekMinimum();
+ inline Element* PeekMaximum();
+
+ static const Key& GetKey(Element* element);
+
+ inline void ModifyKey(Element* element, Key newKey);
+
+ inline void RemoveMinimum();
+ inline void RemoveMaximum();
+
+ inline status_t Insert(Element* element, Key key);
+
+private:
+ status_t _GrowHeap();
+
+ void _MoveUp(MinMaxHeapLink<Element, Key>*
link);
+ void _MoveDown(MinMaxHeapLink<Element, Key>*
link);
+ bool _ChangeTree(MinMaxHeapLink<Element,
Key>* link);
+
+ void _RemoveLast(bool minTree);
+
+ Element** fMinElements;
+ int fMinLastElement;
+
+ Element** fMaxElements;
+ int fMaxLastElement;
+
+ int fSize;
+
+ static Compare sCompare;
+ static GetLink sGetLink;
+};
+
+
+#if KDEBUG
+template<typename Element, typename Key>
+MinMaxHeapLink<Element, Key>::MinMaxHeapLink()
+ :
+ fIndex(-1)
+{
+}
+#else
+template<typename Element, typename Key>
+MinMaxHeapLink<Element, Key>::MinMaxHeapLink()
+{
+}
+#endif
+
+
+template<typename Element, typename Key>
+MinMaxHeapLink<Element, Key>*
+MinMaxHeapLinkImpl<Element, Key>::GetMinMaxHeapLink()
+{
+ return &fMinMaxHeapLink;
+}
+
+
+template<typename Element, typename Key>
+MinMaxHeapLink<Element, Key>*
+MinMaxHeapStandardGetLink<Element, Key>::operator()(Element* element) const
+{
+ return element->GetMinMaxHeapLink();
+}
+
+
+template<typename Element, typename Key,
+ MinMaxHeapLink<Element, Key> Element::*LinkMember>
+MinMaxHeapLink<Element, Key>*
+MinMaxHeapMemberGetLink<Element, Key, LinkMember>::operator()(
+ Element* element) const
+{
+ return &(element->*LinkMember);
+}
+
+
+template<typename Key>
+bool
+MinMaxHeapCompare<Key>::operator()(Key a, Key b)
+{
+ return a < b;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+MIN_MAX_HEAP_CLASS_NAME::MinMaxHeap()
+ :
+ fMinElements(NULL),
+ fMinLastElement(0),
+ fMaxElements(NULL),
+ fMaxLastElement(0),
+ fSize(0)
+{
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+MIN_MAX_HEAP_CLASS_NAME::~MinMaxHeap()
+{
+ free(fMinElements);
+ free(fMaxElements);
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+Element*
+MIN_MAX_HEAP_CLASS_NAME::PeekMinimum()
+{
+ if (fMinLastElement > 0)
+ return fMinElements[0];
+ else if (fMaxLastElement > 0) {
+ ASSERT(fMaxLastElement == 1);
+ return fMaxElements[0];
+ }
+
+ return NULL;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+Element*
+MIN_MAX_HEAP_CLASS_NAME::PeekMaximum()
+{
+ if (fMaxLastElement > 0)
+ return fMaxElements[0];
+ else if (fMinLastElement > 0) {
+ ASSERT(fMinLastElement == 1);
+ return fMinElements[0];
+ }
+
+ return NULL;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+const Key&
+MIN_MAX_HEAP_CLASS_NAME::GetKey(Element* element)
+{
+ return sGetLink(element)->fKey;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::ModifyKey(Element* element, Key newKey)
+{
+ MinMaxHeapLink<Element, Key>* link = sGetLink(element);
+
+ Key oldKey = link->fKey;
+ link->fKey = newKey;
+
+ if (sCompare(newKey, oldKey) && link->fMinTree)
+ _MoveUp(link);
+ else
+ _MoveDown(link);
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::RemoveMinimum()
+{
+ if (fMinLastElement == 0) {
+ ASSERT(fMaxLastElement == 1);
+ RemoveMaximum();
+ return;
+ }
+
+#if KDEBUG
+ Element* element = PeekMinimum();
+ MinMaxHeapLink<Element, Key>* link = sGetLink(element);
+ link->fIndex = -1;
+#endif
+
+ _RemoveLast(true);
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::RemoveMaximum()
+{
+ if (fMaxLastElement == 0) {
+ ASSERT(fMinLastElement == 1);
+ RemoveMinimum();
+ return;
+ }
+
+#if KDEBUG
+ Element* element = PeekMaximum();
+ MinMaxHeapLink<Element, Key>* link = sGetLink(element);
+ link->fIndex = -1;
+#endif
+
+ _RemoveLast(false);
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+status_t
+MIN_MAX_HEAP_CLASS_NAME::Insert(Element* element, Key key)
+{
+
+ if (min_c(fMinLastElement, fMaxLastElement) == fSize) {
+ ASSERT(max_c(fMinLastElement, fMaxLastElement) == fSize);
+ status_t result = _GrowHeap();
+ if (result != B_OK)
+ return result;
+ }
+
+ ASSERT(fMinLastElement != fSize || fMaxLastElement != fSize);
+
+ MinMaxHeapLink<Element, Key>* link = sGetLink(element);
+
+ link->fMinTree = fMinLastElement < fMaxLastElement;
+
+ int& lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement;
+ Element** tree = link->fMinTree ? fMinElements : fMaxElements;
+
+ tree[lastElement] = element;
+ link->fIndex = lastElement++;
+ link->fKey = key;
+
+ if (!_ChangeTree(link))
+ _MoveUp(link);
+
+ return B_OK;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+status_t
+MIN_MAX_HEAP_CLASS_NAME::_GrowHeap()
+{
+ int newSize = max_c(fSize * 2, 4);
+
+ size_t arraySize = newSize * sizeof(Element*);
+ Element** newBuffer
+ = reinterpret_cast<Element**>(realloc(fMinElements, arraySize));
+ if (newBuffer == NULL)
+ return B_NO_MEMORY;
+ fMinElements = newBuffer;
+
+ newBuffer
+ = reinterpret_cast<Element**>(realloc(fMaxElements, arraySize));
+ if (newBuffer == NULL)
+ return B_NO_MEMORY;
+ fMaxElements = newBuffer;
+
+ fSize = newSize;
+ return B_OK;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::_MoveUp(MinMaxHeapLink<Element, Key>* link)
+{
+ Element** tree = link->fMinTree ? fMinElements : fMaxElements;
+ while (true) {
+ if (link->fIndex <= 0)
+ break;
+
+ int parent = (link->fIndex - 1) / 2;
+ bool isSmaller = sCompare(link->fKey,
sGetLink(tree[parent])->fKey);
+ if (isSmaller ^ !link->fMinTree) {
+ ASSERT(sGetLink(tree[parent])->fIndex == parent);
+ sGetLink(tree[parent])->fIndex = link->fIndex;
+
+ Element* element = tree[link->fIndex];
+ tree[link->fIndex] = tree[parent];
+ tree[parent] = element;
+
+ link->fIndex = parent;
+ } else
+ break;
+ }
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::_MoveDown(MinMaxHeapLink<Element, Key>* link)
+{
+ int current;
+
+ int lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement;
+ Element** tree = link->fMinTree ? fMinElements : fMaxElements;
+ while (true) {
+ current = link->fIndex;
+
+ int child = 2 * link->fIndex + 1;
+ if (child < lastElement) {
+ bool isSmaller = sCompare(sGetLink(tree[child])->fKey,
link->fKey);
+ if (isSmaller ^ !link->fMinTree)
+ current = child;
+ }
+
+ child = 2 * link->fIndex + 2;
+ if (child < lastElement) {
+ bool isSmaller = sCompare(sGetLink(tree[child])->fKey,
+ sGetLink(tree[current])->fKey);
+ if (isSmaller ^ !link->fMinTree)
+ current = child;
+ }
+
+ if (link->fIndex == current)
+ break;
+
+ ASSERT(sGetLink(tree[current])->fIndex == current);
+ sGetLink(tree[current])->fIndex = link->fIndex;
+
+ Element* element = tree[link->fIndex];
+ tree[link->fIndex] = tree[current];
+ tree[current] = element;
+
+ link->fIndex = current;
+ }
+
+ if (2 * link->fIndex + 1 >= lastElement)
+ _ChangeTree(link);
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+bool
+MIN_MAX_HEAP_CLASS_NAME::_ChangeTree(MinMaxHeapLink<Element, Key>* link)
+{
+ int currentLastElement = link->fMinTree ? fMinLastElement :
fMaxLastElement;
+ int otherLastElement = link->fMinTree ? fMaxLastElement :
fMinLastElement;
+
+ Element** currentTree = link->fMinTree ? fMinElements : fMaxElements;
+ Element** otherTree = link->fMinTree ? fMaxElements : fMinElements;
+
+ if (otherLastElement <= 0) {
+ ASSERT(currentLastElement == 1);
+ return true;
+ }
+
+ ASSERT((link->fIndex - 1) / 2 < otherLastElement);
+
+ Element* predecessor;
+ if (2 * link->fIndex + 1 < otherLastElement) {
+ predecessor = otherTree[2 * link->fIndex + 1];
+ ASSERT(sGetLink(predecessor)->fIndex == 2 * link->fIndex + 1);
+ } else if (link->fIndex < otherLastElement) {
+ predecessor = otherTree[link->fIndex];
+ ASSERT(sGetLink(predecessor)->fIndex == link->fIndex);
+ } else {
+ predecessor = otherTree[(link->fIndex - 1) / 2];
+ ASSERT(sGetLink(predecessor)->fIndex == (link->fIndex - 1) / 2);
+ }
+ MinMaxHeapLink<Element, Key>* predecessorLink = sGetLink(predecessor);
+
+ bool isSmaller = sCompare(predecessorLink->fKey, link->fKey);
+ if (isSmaller ^ !link->fMinTree) {
+ Element* element = currentTree[link->fIndex];
+ currentTree[link->fIndex] = otherTree[predecessorLink->fIndex];
+ otherTree[predecessorLink->fIndex] = element;
+
+ int index = link->fIndex;
+ link->fIndex = predecessorLink->fIndex;
+ predecessorLink->fIndex = index;
+
+ predecessorLink->fMinTree = !predecessorLink->fMinTree;
+ link->fMinTree = !link->fMinTree;
+
+ _MoveUp(link);
+ return true;
+ }
+
+ return false;
+}
+
+
+MIN_MAX_HEAP_TEMPLATE_LIST
+void
+MIN_MAX_HEAP_CLASS_NAME::_RemoveLast(bool minTree)
+{
+ bool deleteMin = fMaxLastElement < fMinLastElement;
+
+ Element** tree = deleteMin ? fMinElements : fMaxElements;
+ int& lastElement = deleteMin ? fMinLastElement : fMaxLastElement;
+
+ ASSERT(lastElement > 0);
+ lastElement--;
+ if (lastElement == 0 && deleteMin == minTree)
+ return;
+
+ Element* element = tree[lastElement];
+
+ if (minTree)
+ fMinElements[0] = element;
+ else
+ fMaxElements[0] = element;
+
+ MinMaxHeapLink<Element, Key>* link = sGetLink(element);
+ link->fIndex = 0;
+ link->fMinTree = minTree;
+ _MoveDown(link);
+}
+
+
+#endif // KERNEL_UTIL_MIN_MAX_HEAP_H
+
############################################################################
Commit: da3a48f4a8a723322ad53f06fddf945a7c38ea3d
Author: Pawel Dziepak <pdziepak@xxxxxxxxxxx>
Date: Thu Oct 17 17:23:27 2013 UTC
scheduler_affine: Use min-max heap as per-core CPU heap
----------------------------------------------------------------------------
diff --git a/src/system/kernel/scheduler/scheduler_affine.cpp
b/src/system/kernel/scheduler/scheduler_affine.cpp
index b1667bf..1dbcc6f 100644
--- a/src/system/kernel/scheduler/scheduler_affine.cpp
+++ b/src/system/kernel/scheduler/scheduler_affine.cpp
@@ -28,6 +28,7 @@
#include <thread.h>
#include <timer.h>
#include <util/Heap.h>
+#include <util/MinMaxHeap.h>
#include <util/Random.h>
#include "RunQueue.h"
@@ -48,20 +49,13 @@ const bigtime_t kMinThreadQuantum = 3000;
const bigtime_t kMaxThreadQuantum = 10000;
-struct CPUHeapEntry : public HeapLinkImpl<CPUHeapEntry, int32> {
- HeapLink<CPUHeapEntry, int32> fMaxHeap;
+struct CPUHeapEntry : public MinMaxHeapLinkImpl<CPUHeapEntry, int32> {
int32 fCPUNumber;
};
static CPUHeapEntry* sCPUPriorityEntries;
-typedef Heap<CPUHeapEntry, int32> AffineCPUHeap;
-typedef Heap<CPUHeapEntry, int32, HeapGreaterCompare<int32>,
- HeapMemberGetLink<CPUHeapEntry, int32, &CPUHeapEntry::fMaxHeap>
>
- AffineCPUMaxHeap;
-
-// TODO: Use one min-max heap per-core
+typedef MinMaxHeap<CPUHeapEntry, int32> AffineCPUHeap;
static AffineCPUHeap* sCPUPriorityHeaps;
-static AffineCPUMaxHeap* sCPUMaxPriorityHeaps;
struct CoreHeapEntry : public HeapLinkImpl<CoreHeapEntry, int32> {
int32 fCoreID;
@@ -214,25 +208,25 @@ dump_heap(AffineCPUHeap* heap)
AffineCPUHeap temp;
kprintf("cpu priority actual priority\n");
- CPUHeapEntry* entry = heap->PeekRoot();
+ CPUHeapEntry* entry = heap->PeekMinimum();
while (entry) {
int32 cpu = entry->fCPUNumber;
int32 key = AffineCPUHeap::GetKey(entry);
kprintf("%3" B_PRId32 " %8" B_PRId32 " %15" B_PRId32 "\n", cpu,
key,
affine_get_effective_priority(gCPU[cpu].running_thread));
- heap->RemoveRoot();
+ heap->RemoveMinimum();
temp.Insert(entry, key);
- entry = heap->PeekRoot();
+ entry = heap->PeekMinimum();
}
- entry = temp.PeekRoot();
+ entry = temp.PeekMinimum();
while (entry) {
int32 key = AffineCPUHeap::GetKey(entry);
- temp.RemoveRoot();
+ temp.RemoveMinimum();
heap->Insert(entry, key);
- entry = temp.PeekRoot();
+ entry = temp.PeekMinimum();
}
}
@@ -355,10 +349,9 @@ affine_update_priority_heaps(int32 cpu, int32 priority)
int32 core = sCPUToCore[cpu];
sCPUPriorityHeaps[core].ModifyKey(&sCPUPriorityEntries[cpu], priority);
- sCPUMaxPriorityHeaps[core].ModifyKey(&sCPUPriorityEntries[cpu],
priority);
int32 maxPriority
- =
AffineCPUMaxHeap::GetKey(sCPUMaxPriorityHeaps[core].PeekRoot());
+ = AffineCPUHeap::GetKey(sCPUPriorityHeaps[core].PeekMaximum());
int32 corePriority =
AffineCoreHeap::GetKey(&sCorePriorityEntries[core]);
if (corePriority != maxPriority)
@@ -378,7 +371,7 @@ affine_choose_core(void)
static inline int32
affine_choose_cpu(int32 core)
{
- CPUHeapEntry* entry = sCPUPriorityHeaps[core].PeekRoot();
+ CPUHeapEntry* entry = sCPUPriorityHeaps[core].PeekMinimum();
ASSERT(entry != NULL);
return entry->fCPUNumber;
}
@@ -999,12 +992,6 @@ scheduler_affine_init()
return B_NO_MEMORY;
ArrayDeleter<AffineCPUHeap> cpuPriorityHeapDeleter(sCPUPriorityHeaps);
- sCPUMaxPriorityHeaps = new AffineCPUMaxHeap[coreCount];
- if (sCPUMaxPriorityHeaps == NULL)
- return B_NO_MEMORY;
- ArrayDeleter<AffineCPUMaxHeap> cpuMaxPriorityHeapDeleter(
- sCPUMaxPriorityHeaps);
-
for (int32 i = 0; i < cpuCount; i++) {
sCPUPriorityEntries[i].fCPUNumber = i;
int32 core = sCPUToCore[i];
@@ -1014,11 +1001,6 @@ scheduler_affine_init()
B_IDLE_PRIORITY);
if (result != B_OK)
return result;
-
- result =
sCPUMaxPriorityHeaps[core].Insert(&sCPUPriorityEntries[i],
- B_IDLE_PRIORITY);
- if (result != B_OK)
- return result;
}
sCorePriorityHeap = new AffineCoreHeap;
@@ -1073,7 +1055,6 @@ scheduler_affine_init()
runQueuesDeleter.Detach();
pinnedRunQueuesDeleter.Detach();
corePriorityHeapDeleter.Detach();
- cpuMaxPriorityHeapDeleter.Detach();
cpuPriorityHeapDeleter.Detach();
corePriorityEntriesDeleter.Detach();
cpuPriorityEntriesDeleter.Detach();
Other related posts:
- » [haiku-commits] BRANCH pdziepak-github.scheduler [da3a48f] headers/private/kernel/util src/system/kernel/scheduler - pdziepak-github . scheduler
