13 #ifndef InitializeListHead
14 #define InitializeListHead(PLH__) ((PLH__)->Flink = (PLH__)->Blink = (PLH__))
18 #define IsListEmpty(PLH__) ((PLH__)->Flink == (PVOID)(PLH__))
21 #ifndef RemoveEntryList
23 #define RemoveEntryList(PLE__) \
25 PLIST_ENTRY pleBack__ = (PLIST_ENTRY)((PLE__)->Blink); \
26 PLIST_ENTRY pleForward__ = (PLIST_ENTRY)((PLE__)->Flink); \
28 pleBack__->Flink = pleForward__; \
29 pleForward__->Blink = pleBack__; \
34 #ifndef InsertTailList
36 #define InsertTailList(PLH__, PLE__) \
38 PLIST_ENTRY pleListHead__ = (PLH__); \
39 PLIST_ENTRY pleBlink__ = (PLIST_ENTRY)((PLH__)->Blink); \
41 (PLE__)->Flink = pleListHead__; \
42 (PLE__)->Blink = pleBlink__; \
43 pleBlink__->Flink = (PLE__); \
44 pleListHead__->Blink = (PLE__); \
49 #ifndef RemoveHeadList
51 #define RemoveHeadList(PLH__) \
52 (PLIST_ENTRY)((PLH__)->Flink); \
53 RemoveEntryList((PLIST_ENTRY)((PLH__)->Flink));
57 #define FIBERTEST_COUNT 500
69 struct FiberData
* pfdPrev
;
73 static LIST_ENTRY a_leQueues
[32];
74 static unsigned nQuantum
= 0;
75 static struct FiberData
* pfdLastStarveScan
= NULL
;
81 struct FiberData
* Fbt_GetCurrent(void);
82 unsigned Fbt_GetCurrentId(void);
83 VOID CALLBACK
Fbt_Startup(PVOID
);
84 void Fbt_Dispatch(struct FiberData
*, int);
85 void Fbt_AfterSwitch(struct FiberData
*);
89 struct FiberData
* Fbt_GetCurrent(VOID
)
91 return GetFiberData();
94 unsigned Fbt_GetCurrentId(VOID
)
96 return Fbt_GetCurrent()->nId
;
101 struct FiberData
* pfdCur
;
103 pfdCur
= Fbt_GetCurrent();
110 pfdCur
->nPrio
= pfdCur
->nRealPrio
;
112 else if((rand() % 100) > 50 - (45 * pfdCur
->nPrio
) / 32)
113 Fbt_Dispatch(pfdCur
, 0);
116 void Fbt_AfterSwitch(struct FiberData
* pfdCur
)
118 struct FiberData
* pfdPrev
;
120 pfdPrev
= pfdCur
->pfdPrev
;
122 /* The previous fiber left some homework for us */
125 /* Kill the predecessor */
126 if(pfdCur
->bExitPrev
)
128 if(pfdLastStarveScan
== pfdPrev
)
129 pfdLastStarveScan
= 0;
131 DeleteFiber(pfdPrev
->pFiber
);
134 /* Enqueue the previous fiber in the correct ready queue */
137 /* Remember the quantum in which the previous fiber was queued */
138 pfdPrev
->nQuantumQueued
= nQuantum
;
140 /* Disable the anti-starvation boost */
144 pfdPrev
->nPrio
= pfdPrev
->nRealPrio
;
147 /* Enqueue the previous fiber */
150 &a_leQueues
[pfdPrev
->nPrio
],
157 VOID CALLBACK
Fbt_Startup(PVOID pParam
)
159 assert(pParam
== GetFiberData());
160 Fbt_AfterSwitch(pParam
);
165 void Fbt_Dispatch(struct FiberData
* pfdCur
, int bExit
)
169 struct FiberData
* pfdNext
;
171 assert(pfdCur
== GetFiberData());
175 /* Every ten quantums check for starving threads */
176 /* FIXME: this implementation of starvation prevention isn't that great */
177 if(nQuantum
% 10 == 0)
183 PLIST_ENTRY ple
= NULL
;
188 /* Pick up from where we left last time */
189 if(pfdLastStarveScan
)
193 nPrio
= pfdLastStarveScan
->nPrio
;
195 /* The last fiber we scanned for starvation isn't queued anymore */
196 if(IsListEmpty(&pfdLastStarveScan
->leQueue
))
197 /* Scan the ready queue for its priority */
199 /* Last fiber for its priority level */
200 else if(pfdLastStarveScan
->leQueue
.Flink
== &a_leQueues
[nPrio
])
201 /* Scan the ready queue for the next priority level */
203 /* Scan the next fiber in the ready queue */
207 ple
= pfdLastStarveScan
->leQueue
.Flink
;
211 /* Priority levels 15-31 are never checked for starvation */
222 Scan at most 16 threads, in the priority range 0-14, applying in total at
223 most 10 boosts. This loop scales O(1)
225 for(j
= 0, k
= 0, b
= 0; j
< 16 && k
< 15 && b
< 10; ++ j
)
229 /* No previous state to resume from */
234 /* Get the first element in the current queue */
235 nQueue
= (k
+ i
) % 15;
237 if(IsListEmpty(&a_leQueues
[nQueue
]))
243 ple
= (PLIST_ENTRY
)a_leQueues
[nQueue
].Flink
;
248 /* Get the current fiber */
249 pfdLastStarveScan
= CONTAINING_RECORD(ple
, struct FiberData
, leQueue
);
250 assert(pfdLastStarveScan
->nMagic
== 0x12345678);
251 assert(pfdLastStarveScan
!= pfdCur
);
253 /* Calculate the number of quantums the fiber has been in the queue */
254 if(nQuantum
> pfdLastStarveScan
->nQuantumQueued
)
255 nDiff
= nQuantum
- pfdLastStarveScan
->nQuantumQueued
;
257 nDiff
= UINT_MAX
- pfdLastStarveScan
->nQuantumQueued
+ nQuantum
;
259 /* The fiber has been ready for more than 30 quantums: it's starving */
262 /* Plus one boost applied */
265 /* Apply the boost */
266 pfdLastStarveScan
->nBoost
= 1;
267 pfdLastStarveScan
->nRealPrio
= pfdLastStarveScan
->nPrio
;
268 pfdLastStarveScan
->nPrio
= 15;
270 /* Re-enqueue the fiber in the correct priority queue */
271 RemoveEntryList(&pfdLastStarveScan
->leQueue
);
272 InsertTailList(&a_leQueues
[15], &pfdLastStarveScan
->leQueue
);
279 /* This fiber is going to die: scan all ready queues */
283 Scan only ready queues for priorities greater than or equal to the priority of
284 the current thread (round-robin)
287 n
= pfdCur
->nPrio
+ 1;
289 /* This loop scales O(1) */
290 for(i
= 32; i
>= n
; -- i
)
294 /* No fiber ready for this priority level */
295 if(IsListEmpty(&a_leQueues
[i
- 1]))
298 /* Get the next ready fiber */
299 pleNext
= RemoveHeadList(&a_leQueues
[i
- 1]);
300 InitializeListHead(pleNext
);
301 pfdNext
= CONTAINING_RECORD(pleNext
, struct FiberData
, leQueue
);
302 assert(pfdNext
->pFiber
!= GetCurrentFiber());
303 assert(pfdNext
->nMagic
== 0x12345678);
307 /* Next fiber chosen */
310 /* Give some homework to the next fiber */
311 pfdNext
->pfdPrev
= pfdCur
;
312 pfdNext
->bExitPrev
= bExit
;
314 /* Switch to the next fiber */
315 SwitchToFiber(pfdNext
->pFiber
);
317 /* Complete the switch back to this fiber */
318 Fbt_AfterSwitch(pfdCur
);
320 /* No next fiber, and current fiber exiting */
325 /* Delete the current fiber. This kills the thread and stops the simulation */
326 if(pfdLastStarveScan
== pfdCur
)
327 pfdLastStarveScan
= NULL
;
329 pCurFiber
= pfdCur
->pFiber
;
331 DeleteFiber(pCurFiber
);
333 /* No next fiber: continue running the current one */
338 Fbt_Dispatch(GetFiberData(), 1);
341 void Fbt_CreateFiber(int bInitial
)
344 struct FiberData
* pData
;
345 static int s_bFiberPrioSeeded
= 0;
346 static LONG s_nFiberIdSeed
= 0;
348 pData
= malloc(sizeof(struct FiberData
));
353 pFiber
= ConvertThreadToFiber(pData
);
355 pFiber
= CreateFiber(0, Fbt_Startup
, pData
);
357 if(!s_bFiberPrioSeeded
)
359 unsigned nFiberPrioSeed
;
362 tCurTime
= time(NULL
);
363 memcpy(&nFiberPrioSeed
, &tCurTime
, sizeof(nFiberPrioSeed
));
364 srand(nFiberPrioSeed
);
365 s_bFiberPrioSeeded
= 1;
370 pData
->nMagic
= 0x12345678;
371 pData
->nId
= InterlockedIncrement(&s_nFiberIdSeed
);
372 pData
->nPrio
= rand() % 32;
373 pData
->pFiber
= pFiber
;
374 pData
->nQuantumQueued
= 0;
376 pData
->nRealPrio
= pData
->nPrio
;
377 pData
->pfdPrev
= NULL
;
378 pData
->bExitPrev
= 0;
382 InitializeListHead(&pData
->leQueue
);
388 &a_leQueues
[pData
->nPrio
],
401 nId
= Fbt_GetCurrentId();
403 _ftprintf(stderr
, _T("[%u] BEGIN\n"), nId
);
405 for(i
= 0; i
< n
; ++ i
)
410 _ftprintf(stderr
, _T("[%u] [%u/%u]\n"), nId
, i
+ 1, n
);
414 for(j
= 0; j
< m
; ++ j
)
420 _ftprintf(stderr
, _T("[%u] END\n"), nId
);
423 int _tmain(int argc
, _TCHAR
const * const * argv
)
429 nFibers
= _tcstoul(argv
[1], NULL
, 0);
431 nFibers
= FIBERTEST_COUNT
;
433 for(i
= 0; i
< 32; ++ i
)
435 InitializeListHead(&a_leQueues
[i
]);
438 for(i
= 0; i
< nFibers
; ++ i
)
439 Fbt_CreateFiber(i
== 0);
441 Fbt_Startup(GetFiberData());