diff options
author | Mic Bowman | 2011-04-22 14:55:23 -0700 |
---|---|---|
committer | Mic Bowman | 2011-04-22 14:55:23 -0700 |
commit | a3bd769cb33ee59b883998205454bb340d44cb9e (patch) | |
tree | a224dbf2e1ec69a6258773496eb49f0b60f3edee /OpenSim/Framework/PriorityQueue.cs | |
parent | Set the initial rate for the adaptive throttle to 160Kpbs (diff) | |
download | opensim-SC_OLD-a3bd769cb33ee59b883998205454bb340d44cb9e.zip opensim-SC_OLD-a3bd769cb33ee59b883998205454bb340d44cb9e.tar.gz opensim-SC_OLD-a3bd769cb33ee59b883998205454bb340d44cb9e.tar.bz2 opensim-SC_OLD-a3bd769cb33ee59b883998205454bb340d44cb9e.tar.xz |
Added a second immediate queue to be used for the BestAvatar policy
and currently used for all of an avatars attachments by the other
policies. Also changed the way items are pulled from the update queues
to bias close objects even more.
Diffstat (limited to 'OpenSim/Framework/PriorityQueue.cs')
-rw-r--r-- | OpenSim/Framework/PriorityQueue.cs | 99 |
1 files changed, 82 insertions, 17 deletions
diff --git a/OpenSim/Framework/PriorityQueue.cs b/OpenSim/Framework/PriorityQueue.cs index ea718c4..8eeafd1 100644 --- a/OpenSim/Framework/PriorityQueue.cs +++ b/OpenSim/Framework/PriorityQueue.cs | |||
@@ -42,22 +42,40 @@ namespace OpenSim.Framework | |||
42 | 42 | ||
43 | public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); | 43 | public delegate bool UpdatePriorityHandler(ref uint priority, ISceneEntity entity); |
44 | 44 | ||
45 | // Heap[0] for self updates | 45 | /// <summary> |
46 | // Heap[1..12] for entity updates | 46 | /// Total number of queues (priorities) available |
47 | 47 | /// </summary> | |
48 | public const uint NumberOfQueues = 12; | 48 | public const uint NumberOfQueues = 12; |
49 | public const uint ImmediateQueue = 0; | 49 | |
50 | /// <summary> | ||
51 | /// Number of queuest (priorities) that are processed immediately | ||
52 | /// </summary. | ||
53 | public const uint NumberOfImmediateQueues = 2; | ||
50 | 54 | ||
51 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues]; | 55 | private MinHeap<MinHeapItem>[] m_heaps = new MinHeap<MinHeapItem>[NumberOfQueues]; |
52 | private Dictionary<uint, LookupItem> m_lookupTable; | 56 | private Dictionary<uint, LookupItem> m_lookupTable; |
57 | |||
58 | // internal state used to ensure the deqeues are spread across the priority | ||
59 | // queues "fairly". queuecounts is the amount to pull from each queue in | ||
60 | // each pass. weighted towards the higher priority queues | ||
53 | private uint m_nextQueue = 0; | 61 | private uint m_nextQueue = 0; |
62 | private uint m_countFromQueue = 0; | ||
63 | private uint[] m_queueCounts = { 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1 }; | ||
64 | |||
65 | // next request is a counter of the number of updates queued, it provides | ||
66 | // a total ordering on the updates coming through the queue and is more | ||
67 | // lightweight (and more discriminating) than tick count | ||
54 | private UInt64 m_nextRequest = 0; | 68 | private UInt64 m_nextRequest = 0; |
55 | 69 | ||
70 | /// <summary> | ||
71 | /// Lock for enqueue and dequeue operations on the priority queue | ||
72 | /// </summary> | ||
56 | private object m_syncRoot = new object(); | 73 | private object m_syncRoot = new object(); |
57 | public object SyncRoot { | 74 | public object SyncRoot { |
58 | get { return this.m_syncRoot; } | 75 | get { return this.m_syncRoot; } |
59 | } | 76 | } |
60 | 77 | ||
78 | #region constructor | ||
61 | public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } | 79 | public PriorityQueue() : this(MinHeap<MinHeapItem>.DEFAULT_CAPACITY) { } |
62 | 80 | ||
63 | public PriorityQueue(int capacity) | 81 | public PriorityQueue(int capacity) |
@@ -66,8 +84,16 @@ namespace OpenSim.Framework | |||
66 | 84 | ||
67 | for (int i = 0; i < m_heaps.Length; ++i) | 85 | for (int i = 0; i < m_heaps.Length; ++i) |
68 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); | 86 | m_heaps[i] = new MinHeap<MinHeapItem>(capacity); |
87 | |||
88 | m_nextQueue = NumberOfImmediateQueues; | ||
89 | m_countFromQueue = m_queueCounts[m_nextQueue]; | ||
69 | } | 90 | } |
91 | #endregion Constructor | ||
70 | 92 | ||
93 | #region PublicMethods | ||
94 | /// <summary> | ||
95 | /// Return the number of items in the queues | ||
96 | /// </summary> | ||
71 | public int Count | 97 | public int Count |
72 | { | 98 | { |
73 | get | 99 | get |
@@ -79,6 +105,9 @@ namespace OpenSim.Framework | |||
79 | } | 105 | } |
80 | } | 106 | } |
81 | 107 | ||
108 | /// <summary> | ||
109 | /// Enqueue an item into the specified priority queue | ||
110 | /// </summary> | ||
82 | public bool Enqueue(uint pqueue, IEntityUpdate value) | 111 | public bool Enqueue(uint pqueue, IEntityUpdate value) |
83 | { | 112 | { |
84 | LookupItem lookup; | 113 | LookupItem lookup; |
@@ -100,32 +129,62 @@ namespace OpenSim.Framework | |||
100 | return true; | 129 | return true; |
101 | } | 130 | } |
102 | 131 | ||
132 | /// <summary> | ||
133 | /// Remove an item from one of the queues. Specifically, it removes the | ||
134 | /// oldest item from the next queue in order to provide fair access to | ||
135 | /// all of the queues | ||
136 | /// </summary> | ||
103 | public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) | 137 | public bool TryDequeue(out IEntityUpdate value, out Int32 timeinqueue) |
104 | { | 138 | { |
105 | // If there is anything in priority queue 0, return it first no | 139 | // If there is anything in priority queue 0, return it first no |
106 | // matter what else. Breaks fairness. But very useful. | 140 | // matter what else. Breaks fairness. But very useful. |
107 | if (m_heaps[ImmediateQueue].Count > 0) | 141 | for (int iq = 0; iq < NumberOfImmediateQueues; iq++) |
142 | { | ||
143 | if (m_heaps[iq].Count > 0) | ||
144 | { | ||
145 | MinHeapItem item = m_heaps[iq].RemoveMin(); | ||
146 | m_lookupTable.Remove(item.Value.Entity.LocalId); | ||
147 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | ||
148 | value = item.Value; | ||
149 | |||
150 | return true; | ||
151 | } | ||
152 | } | ||
153 | |||
154 | // To get the fair queing, we cycle through each of the | ||
155 | // queues when finding an element to dequeue. | ||
156 | // We pull (NumberOfQueues - QueueIndex) items from each queue in order | ||
157 | // to give lower numbered queues a higher priority and higher percentage | ||
158 | // of the bandwidth. | ||
159 | |||
160 | // Check for more items to be pulled from the current queue | ||
161 | if (m_heaps[m_nextQueue].Count > 0 && m_countFromQueue > 0) | ||
108 | { | 162 | { |
109 | MinHeapItem item = m_heaps[ImmediateQueue].RemoveMin(); | 163 | m_countFromQueue--; |
164 | |||
165 | MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); | ||
110 | m_lookupTable.Remove(item.Value.Entity.LocalId); | 166 | m_lookupTable.Remove(item.Value.Entity.LocalId); |
111 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | 167 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); |
112 | value = item.Value; | 168 | value = item.Value; |
113 | 169 | ||
114 | return true; | 170 | return true; |
115 | } | 171 | } |
116 | 172 | ||
117 | for (int i = 0; i < NumberOfQueues; ++i) | 173 | // Find the next non-immediate queue with updates in it |
174 | for (int i = 1; i < NumberOfQueues; ++i) | ||
118 | { | 175 | { |
119 | // To get the fair queing, we cycle through each of the | 176 | m_nextQueue = (uint)((m_nextQueue + i) % NumberOfQueues); |
120 | // queues when finding an element to dequeue, this code | 177 | m_countFromQueue = m_queueCounts[m_nextQueue]; |
121 | // assumes that the distribution of updates in the queues | 178 | |
122 | // is polynomial, probably quadractic (eg distance of PI * R^2) | 179 | // if this is one of the immediate queues, just skip it |
123 | uint h = (uint)((m_nextQueue + i) % NumberOfQueues); | 180 | if (m_nextQueue < NumberOfImmediateQueues) |
124 | if (m_heaps[h].Count > 0) | 181 | continue; |
182 | |||
183 | if (m_heaps[m_nextQueue].Count > 0) | ||
125 | { | 184 | { |
126 | m_nextQueue = (uint)((h + 1) % NumberOfQueues); | 185 | m_countFromQueue--; |
127 | 186 | ||
128 | MinHeapItem item = m_heaps[h].RemoveMin(); | 187 | MinHeapItem item = m_heaps[m_nextQueue].RemoveMin(); |
129 | m_lookupTable.Remove(item.Value.Entity.LocalId); | 188 | m_lookupTable.Remove(item.Value.Entity.LocalId); |
130 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); | 189 | timeinqueue = Util.EnvironmentTickCountSubtract(item.EntryTime); |
131 | value = item.Value; | 190 | value = item.Value; |
@@ -139,6 +198,10 @@ namespace OpenSim.Framework | |||
139 | return false; | 198 | return false; |
140 | } | 199 | } |
141 | 200 | ||
201 | /// <summary> | ||
202 | /// Reapply the prioritization function to each of the updates currently | ||
203 | /// stored in the priority queues. | ||
204 | /// </summary | ||
142 | public void Reprioritize(UpdatePriorityHandler handler) | 205 | public void Reprioritize(UpdatePriorityHandler handler) |
143 | { | 206 | { |
144 | MinHeapItem item; | 207 | MinHeapItem item; |
@@ -184,6 +247,8 @@ namespace OpenSim.Framework | |||
184 | return s; | 247 | return s; |
185 | } | 248 | } |
186 | 249 | ||
250 | #endregion PublicMethods | ||
251 | |||
187 | #region MinHeapItem | 252 | #region MinHeapItem |
188 | private struct MinHeapItem : IComparable<MinHeapItem> | 253 | private struct MinHeapItem : IComparable<MinHeapItem> |
189 | { | 254 | { |