aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Framework
diff options
context:
space:
mode:
authorMic Bowman2011-04-22 14:55:23 -0700
committerMic Bowman2011-04-22 14:55:23 -0700
commita3bd769cb33ee59b883998205454bb340d44cb9e (patch)
treea224dbf2e1ec69a6258773496eb49f0b60f3edee /OpenSim/Framework
parentSet the initial rate for the adaptive throttle to 160Kpbs (diff)
downloadopensim-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')
-rw-r--r--OpenSim/Framework/PriorityQueue.cs99
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 {