1 #include <assert.h> 2 #include <limits.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <time.h> 6 7 #include <tchar.h> 8 #include <windows.h> 9 10 #ifndef InitializeListHead 11 #define InitializeListHead(PLH__) ((PLH__)->Flink = (PLH__)->Blink = (PLH__)) 12 #endif 13 14 #ifndef IsListEmpty 15 #define IsListEmpty(PLH__) ((PLH__)->Flink == (PVOID)(PLH__)) 16 #endif 17 18 #ifndef RemoveEntryList 19 20 #define RemoveEntryList(PLE__) \ 21 { \ 22 PLIST_ENTRY pleBack__ = (PLIST_ENTRY)((PLE__)->Blink); \ 23 PLIST_ENTRY pleForward__ = (PLIST_ENTRY)((PLE__)->Flink); \ 24 \ 25 pleBack__->Flink = pleForward__; \ 26 pleForward__->Blink = pleBack__; \ 27 } 28 29 #endif 30 31 #ifndef InsertTailList 32 33 #define InsertTailList(PLH__, PLE__) \ 34 { \ 35 PLIST_ENTRY pleListHead__ = (PLH__); \ 36 PLIST_ENTRY pleBlink__ = (PLIST_ENTRY)((PLH__)->Blink); \ 37 \ 38 (PLE__)->Flink = pleListHead__; \ 39 (PLE__)->Blink = pleBlink__; \ 40 pleBlink__->Flink = (PLE__); \ 41 pleListHead__->Blink = (PLE__); \ 42 } 43 44 #endif 45 46 #ifndef RemoveHeadList 47 48 #define RemoveHeadList(PLH__) \ 49 (PLIST_ENTRY)((PLH__)->Flink); \ 50 RemoveEntryList((PLIST_ENTRY)((PLH__)->Flink)); 51 52 #endif 53 54 #define FIBERTEST_COUNT 500 55 56 struct FiberData 57 { 58 unsigned nMagic; 59 unsigned nId; 60 unsigned nPrio; 61 unsigned nRealPrio; 62 PVOID pFiber; 63 LIST_ENTRY leQueue; 64 int nQuantumQueued; 65 int nBoost; 66 struct FiberData * pfdPrev; 67 int bExitPrev; 68 }; 69 70 static LIST_ENTRY a_leQueues[32]; 71 static unsigned nQuantum = 0; 72 static struct FiberData * pfdLastStarveScan = NULL; 73 74 void Fbt_Create(int); 75 void Fbt_Exit(void); 76 void Fbt_Yield(void); 77 78 struct FiberData * Fbt_GetCurrent(void); 79 unsigned Fbt_GetCurrentId(void); 80 VOID CALLBACK Fbt_Startup(PVOID); 81 void Fbt_Dispatch(struct FiberData *, int); 82 void Fbt_AfterSwitch(struct FiberData *); 83 84 void DoStuff(void); 85 86 struct FiberData * Fbt_GetCurrent(VOID) 87 { 88 return GetFiberData(); 89 } 90 91 unsigned Fbt_GetCurrentId(VOID) 92 { 93 return Fbt_GetCurrent()->nId; 94 } 95 96 void Fbt_Yield(VOID) 97 { 98 struct FiberData * pfdCur; 99 100 pfdCur = Fbt_GetCurrent(); 101 102 if(pfdCur->nBoost) 103 { 104 -- pfdCur->nBoost; 105 106 if(!pfdCur->nBoost) 107 pfdCur->nPrio = pfdCur->nRealPrio; 108 } 109 else if((rand() % 100) > 50 - (45 * pfdCur->nPrio) / 32) 110 Fbt_Dispatch(pfdCur, 0); 111 } 112 113 void Fbt_AfterSwitch(struct FiberData * pfdCur) 114 { 115 struct FiberData * pfdPrev; 116 117 pfdPrev = pfdCur->pfdPrev; 118 119 /* The previous fiber left some homework for us */ 120 if(pfdPrev) 121 { 122 /* Kill the predecessor */ 123 if(pfdCur->bExitPrev) 124 { 125 if(pfdLastStarveScan == pfdPrev) 126 pfdLastStarveScan = 0; 127 128 DeleteFiber(pfdPrev->pFiber); 129 free(pfdPrev); 130 } 131 /* Enqueue the previous fiber in the correct ready queue */ 132 else 133 { 134 /* Remember the quantum in which the previous fiber was queued */ 135 pfdPrev->nQuantumQueued = nQuantum; 136 137 /* Disable the anti-starvation boost */ 138 if(pfdPrev->nBoost) 139 { 140 pfdPrev->nBoost = 0; 141 pfdPrev->nPrio = pfdPrev->nRealPrio; 142 } 143 144 /* Enqueue the previous fiber */ 145 InsertTailList 146 ( 147 &a_leQueues[pfdPrev->nPrio], 148 &pfdPrev->leQueue 149 ); 150 } 151 } 152 } 153 154 VOID CALLBACK Fbt_Startup(PVOID pParam) 155 { 156 assert(pParam == GetFiberData()); 157 Fbt_AfterSwitch(pParam); 158 DoStuff(); 159 Fbt_Exit(); 160 } 161 162 void Fbt_Dispatch(struct FiberData * pfdCur, int bExit) 163 { 164 UCHAR i; 165 UCHAR n; 166 struct FiberData * pfdNext; 167 168 assert(pfdCur == GetFiberData()); 169 170 ++ nQuantum; 171 172 /* Every ten quantums check for starving threads */ 173 /* FIXME: this implementation of starvation prevention isn't that great */ 174 if(nQuantum % 10 == 0) 175 { 176 int j; 177 int k; 178 int b; 179 int bResume; 180 PLIST_ENTRY ple = NULL; 181 182 bResume = 0; 183 i = 0; 184 185 /* Pick up from where we left last time */ 186 if(pfdLastStarveScan) 187 { 188 unsigned nPrio; 189 190 nPrio = pfdLastStarveScan->nPrio; 191 192 /* The last fiber we scanned for starvation isn't queued anymore */ 193 if(IsListEmpty(&pfdLastStarveScan->leQueue)) 194 /* Scan the ready queue for its priority */ 195 i = nPrio; 196 /* Last fiber for its priority level */ 197 else if(pfdLastStarveScan->leQueue.Flink == &a_leQueues[nPrio]) 198 /* Scan the ready queue for the next priority level */ 199 i = nPrio + 1; 200 /* Scan the next fiber in the ready queue */ 201 else 202 { 203 i = nPrio; 204 ple = pfdLastStarveScan->leQueue.Flink; 205 bResume = 1; 206 } 207 208 /* Priority levels 15-31 are never checked for starvation */ 209 if(i >= 15) 210 { 211 if(bResume) 212 bResume = 0; 213 214 i = 0; 215 } 216 } 217 218 /* 219 Scan at most 16 threads, in the priority range 0-14, applying in total at 220 most 10 boosts. This loop scales O(1) 221 */ 222 for(j = 0, k = 0, b = 0; j < 16 && k < 15 && b < 10; ++ j) 223 { 224 unsigned nDiff; 225 226 /* No previous state to resume from */ 227 if(!bResume) 228 { 229 int nQueue; 230 231 /* Get the first element in the current queue */ 232 nQueue = (k + i) % 15; 233 234 if(IsListEmpty(&a_leQueues[nQueue])) 235 { 236 ++ k; 237 continue; 238 } 239 240 ple = (PLIST_ENTRY)a_leQueues[nQueue].Flink; 241 } 242 else 243 bResume = 0; 244 245 /* Get the current fiber */ 246 pfdLastStarveScan = CONTAINING_RECORD(ple, struct FiberData, leQueue); 247 assert(pfdLastStarveScan->nMagic == 0x12345678); 248 assert(pfdLastStarveScan != pfdCur); 249 250 /* Calculate the number of quantums the fiber has been in the queue */ 251 if(nQuantum > pfdLastStarveScan->nQuantumQueued) 252 nDiff = nQuantum - pfdLastStarveScan->nQuantumQueued; 253 else 254 nDiff = UINT_MAX - pfdLastStarveScan->nQuantumQueued + nQuantum; 255 256 /* The fiber has been ready for more than 30 quantums: it's starving */ 257 if(nDiff > 30) 258 { 259 /* Plus one boost applied */ 260 ++ b; 261 262 /* Apply the boost */ 263 pfdLastStarveScan->nBoost = 1; 264 pfdLastStarveScan->nRealPrio = pfdLastStarveScan->nPrio; 265 pfdLastStarveScan->nPrio = 15; 266 267 /* Re-enqueue the fiber in the correct priority queue */ 268 RemoveEntryList(&pfdLastStarveScan->leQueue); 269 InsertTailList(&a_leQueues[15], &pfdLastStarveScan->leQueue); 270 } 271 } 272 } 273 274 pfdNext = NULL; 275 276 /* This fiber is going to die: scan all ready queues */ 277 if(bExit) 278 n = 1; 279 /* 280 Scan only ready queues for priorities greater than or equal to the priority of 281 the current thread (round-robin) 282 */ 283 else 284 n = pfdCur->nPrio + 1; 285 286 /* This loop scales O(1) */ 287 for(i = 32; i >= n; -- i) 288 { 289 PLIST_ENTRY pleNext; 290 291 /* No fiber ready for this priority level */ 292 if(IsListEmpty(&a_leQueues[i - 1])) 293 continue; 294 295 /* Get the next ready fiber */ 296 pleNext = RemoveHeadList(&a_leQueues[i - 1]); 297 InitializeListHead(pleNext); 298 pfdNext = CONTAINING_RECORD(pleNext, struct FiberData, leQueue); 299 assert(pfdNext->pFiber != GetCurrentFiber()); 300 assert(pfdNext->nMagic == 0x12345678); 301 break; 302 } 303 304 /* Next fiber chosen */ 305 if(pfdNext) 306 { 307 /* Give some homework to the next fiber */ 308 pfdNext->pfdPrev = pfdCur; 309 pfdNext->bExitPrev = bExit; 310 311 /* Switch to the next fiber */ 312 SwitchToFiber(pfdNext->pFiber); 313 314 /* Complete the switch back to this fiber */ 315 Fbt_AfterSwitch(pfdCur); 316 } 317 /* No next fiber, and current fiber exiting */ 318 else if(bExit) 319 { 320 PVOID pCurFiber; 321 322 /* Delete the current fiber. This kills the thread and stops the simulation */ 323 if(pfdLastStarveScan == pfdCur) 324 pfdLastStarveScan = NULL; 325 326 pCurFiber = pfdCur->pFiber; 327 free(pfdCur); 328 DeleteFiber(pCurFiber); 329 } 330 /* No next fiber: continue running the current one */ 331 } 332 333 void Fbt_Exit(VOID) 334 { 335 Fbt_Dispatch(GetFiberData(), 1); 336 } 337 338 void Fbt_CreateFiber(int bInitial) 339 { 340 PVOID pFiber; 341 struct FiberData * pData; 342 static int s_bFiberPrioSeeded = 0; 343 static LONG s_nFiberIdSeed = 0; 344 345 pData = malloc(sizeof(struct FiberData)); 346 347 assert(pData); 348 349 if(bInitial) 350 pFiber = ConvertThreadToFiber(pData); 351 else 352 pFiber = CreateFiber(0, Fbt_Startup, pData); 353 354 if(!s_bFiberPrioSeeded) 355 { 356 unsigned nFiberPrioSeed; 357 time_t tCurTime; 358 359 tCurTime = time(NULL); 360 memcpy(&nFiberPrioSeed, &tCurTime, sizeof(nFiberPrioSeed)); 361 srand(nFiberPrioSeed); 362 s_bFiberPrioSeeded = 1; 363 } 364 365 assert(pFiber); 366 367 pData->nMagic = 0x12345678; 368 pData->nId = InterlockedIncrement(&s_nFiberIdSeed); 369 pData->nPrio = rand() % 32; 370 pData->pFiber = pFiber; 371 pData->nQuantumQueued = 0; 372 pData->nBoost = 0; 373 pData->nRealPrio = pData->nPrio; 374 pData->pfdPrev = NULL; 375 pData->bExitPrev = 0; 376 377 if(bInitial) 378 { 379 InitializeListHead(&pData->leQueue); 380 } 381 else 382 { 383 InsertTailList 384 ( 385 &a_leQueues[pData->nPrio], 386 &pData->leQueue 387 ); 388 } 389 } 390 391 void DoStuff(void) 392 { 393 unsigned i; 394 unsigned n; 395 unsigned nId; 396 397 n = rand() % 1000; 398 nId = Fbt_GetCurrentId(); 399 400 _ftprintf(stderr, _T("[%u] BEGIN\n"), nId); 401 402 for(i = 0; i < n; ++ i) 403 { 404 unsigned j; 405 unsigned m; 406 407 _ftprintf(stderr, _T("[%u] [%u/%u]\n"), nId, i + 1, n); 408 409 m = rand() % 1000; 410 411 for(j = 0; j < m; ++ j) 412 Sleep(0); 413 414 Fbt_Yield(); 415 } 416 417 _ftprintf(stderr, _T("[%u] END\n"), nId); 418 } 419 420 int _tmain(int argc, _TCHAR const * const * argv) 421 { 422 unsigned i; 423 unsigned nFibers; 424 425 if(argc > 1) 426 nFibers = _tcstoul(argv[1], NULL, 0); 427 else 428 nFibers = FIBERTEST_COUNT; 429 430 for(i = 0; i < 32; ++ i) 431 { 432 InitializeListHead(&a_leQueues[i]); 433 } 434 435 for(i = 0; i < nFibers; ++ i) 436 Fbt_CreateFiber(i == 0); 437 438 Fbt_Startup(GetFiberData()); 439 440 return 0; 441 } 442 443 /* EOF */ 444