aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim')
-rw-r--r--OpenSim/Framework/PriorityQueue.cs99
-rw-r--r--OpenSim/Region/Framework/Scenes/Prioritizer.cs34
2 files changed, 112 insertions, 21 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 {
diff --git a/OpenSim/Region/Framework/Scenes/Prioritizer.cs b/OpenSim/Region/Framework/Scenes/Prioritizer.cs
index 2e80156..a7637c0 100644
--- a/OpenSim/Region/Framework/Scenes/Prioritizer.cs
+++ b/OpenSim/Region/Framework/Scenes/Prioritizer.cs
@@ -88,7 +88,7 @@ namespace OpenSim.Region.Framework.Scenes
88 88
89 // If this is an update for our own avatar give it the highest priority 89 // If this is an update for our own avatar give it the highest priority
90 if (client.AgentId == entity.UUID) 90 if (client.AgentId == entity.UUID)
91 return PriorityQueue.ImmediateQueue; 91 return 0;
92 92
93 uint priority; 93 uint priority;
94 94
@@ -119,16 +119,40 @@ namespace OpenSim.Region.Framework.Scenes
119 119
120 private uint GetPriorityByTime(IClientAPI client, ISceneEntity entity) 120 private uint GetPriorityByTime(IClientAPI client, ISceneEntity entity)
121 { 121 {
122 return 1; 122 // And anything attached to this avatar gets top priority as well
123 if (entity is SceneObjectPart)
124 {
125 SceneObjectPart sop = (SceneObjectPart)entity;
126 if (sop.ParentGroup.RootPart.IsAttachment && client.AgentId == sop.ParentGroup.RootPart.AttachedAvatar)
127 return 1;
128 }
129
130 return PriorityQueue.NumberOfImmediateQueues; // first queue past the immediate queues
123 } 131 }
124 132
125 private uint GetPriorityByDistance(IClientAPI client, ISceneEntity entity) 133 private uint GetPriorityByDistance(IClientAPI client, ISceneEntity entity)
126 { 134 {
135 // And anything attached to this avatar gets top priority as well
136 if (entity is SceneObjectPart)
137 {
138 SceneObjectPart sop = (SceneObjectPart)entity;
139 if (sop.ParentGroup.RootPart.IsAttachment && client.AgentId == sop.ParentGroup.RootPart.AttachedAvatar)
140 return 1;
141 }
142
127 return ComputeDistancePriority(client,entity,false); 143 return ComputeDistancePriority(client,entity,false);
128 } 144 }
129 145
130 private uint GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity) 146 private uint GetPriorityByFrontBack(IClientAPI client, ISceneEntity entity)
131 { 147 {
148 // And anything attached to this avatar gets top priority as well
149 if (entity is SceneObjectPart)
150 {
151 SceneObjectPart sop = (SceneObjectPart)entity;
152 if (sop.ParentGroup.RootPart.IsAttachment && client.AgentId == sop.ParentGroup.RootPart.AttachedAvatar)
153 return 1;
154 }
155
132 return ComputeDistancePriority(client,entity,true); 156 return ComputeDistancePriority(client,entity,true);
133 } 157 }
134 158
@@ -197,8 +221,10 @@ namespace OpenSim.Region.Framework.Scenes
197 221
198 // And convert the distance to a priority queue, this computation gives queues 222 // And convert the distance to a priority queue, this computation gives queues
199 // at 10, 20, 40, 80, 160, 320, 640, and 1280m 223 // at 10, 20, 40, 80, 160, 320, 640, and 1280m
200 uint pqueue = 1; 224 uint pqueue = PriorityQueue.NumberOfImmediateQueues;
201 for (int i = 0; i < 8; i++) 225 uint queues = PriorityQueue.NumberOfQueues - PriorityQueue.NumberOfImmediateQueues;
226
227 for (int i = 0; i < queues - 1; i++)
202 { 228 {
203 if (distance < 10 * Math.Pow(2.0,i)) 229 if (distance < 10 * Math.Pow(2.0,i))
204 break; 230 break;