Mercurial > flash_v2
annotate packages/kernel/current/src/sched/lottery.cxx @ 68:f74b2666b30d ecos-sw-2000-02-04
Merge from eCos master repository on 2000-02-04-07:47:04-GMT
| author | jlarmour |
|---|---|
| date | Fri, 04 Feb 2000 15:01:01 +0000 |
| parents | bf00f99aec69 |
| children | e0c0827131d1 |
| rev | line source |
|---|---|
| 0 | 1 //========================================================================== |
| 2 // | |
| 2 | 3 // sched/lottery.cxx |
| 0 | 4 // |
| 2 | 5 // Lottery scheduler class implementation |
| 0 | 6 // |
| 7 //========================================================================== | |
| 8 //####COPYRIGHTBEGIN#### | |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
9 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
10 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
11 // The contents of this file are subject to the Red Hat eCos Public License |
|
66
bf00f99aec69
Merge from eCos master repository on 2000-02-02-19:16:44-GMT
jlarmour
parents:
64
diff
changeset
|
12 // Version 1.1 (the "License"); you may not use this file except in |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
13 // compliance with the License. You may obtain a copy of the License at |
|
66
bf00f99aec69
Merge from eCos master repository on 2000-02-02-19:16:44-GMT
jlarmour
parents:
64
diff
changeset
|
14 // http://www.redhat.com/ |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
15 // |
|
66
bf00f99aec69
Merge from eCos master repository on 2000-02-02-19:16:44-GMT
jlarmour
parents:
64
diff
changeset
|
16 // Software distributed under the License is distributed on an "AS IS" |
|
64
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
17 // basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
18 // License for the specific language governing rights and limitations under |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
19 // the License. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
20 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
21 // The Original Code is eCos - Embedded Configurable Operating System, |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
22 // released September 30, 1998. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
23 // |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
24 // The Initial Developer of the Original Code is Red Hat. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
25 // Portions created by Red Hat are |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
26 // Copyright (C) 1998, 1999, 2000 Red Hat, Inc. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
27 // All Rights Reserved. |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
28 // ------------------------------------------- |
|
c38311975d4f
Merge from eCos master repository on 2000-01-28-04:28:11-GMT
jlarmour
parents:
2
diff
changeset
|
29 // |
| 0 | 30 //####COPYRIGHTEND#### |
| 31 //========================================================================== | |
| 32 //#####DESCRIPTIONBEGIN#### | |
| 33 // | |
| 2 | 34 // Author(s): nickg |
| 35 // Contributors: nickg | |
| 36 // Date: 1997-09-16 | |
| 37 // Purpose: Lottery scheduler class implementation | |
| 38 // Description: This file contains the implementations of | |
| 0 | 39 // Cyg_Scheduler_Implementation and |
| 40 // Cyg_SchedThread_Implementation. | |
| 41 // | |
| 42 // | |
| 43 //####DESCRIPTIONEND#### | |
| 44 // | |
| 45 //========================================================================== | |
| 46 | |
| 47 #include <pkgconf/kernel.h> | |
| 48 | |
| 49 #include <cyg/kernel/ktypes.h> // base kernel types | |
| 50 #include <cyg/infra/cyg_trac.h> // tracing macros | |
| 51 #include <cyg/infra/cyg_ass.h> // assertion macros | |
| 52 | |
| 53 #include <cyg/kernel/sched.hxx> // our header | |
| 54 #include <cyg/kernel/intr.hxx> // interrupt defines, for Cyg_HAL_Clock | |
| 55 | |
| 56 #include <cyg/hal/hal_arch.h> // Architecture specific definitions | |
| 57 | |
| 58 | |
| 59 #include <cyg/kernel/thread.inl> // thread inlines | |
| 60 #include <cyg/kernel/sched.inl> // scheduler inlines | |
| 61 | |
| 62 #ifdef CYGSEM_KERNEL_SCHED_LOTTERY | |
| 63 | |
| 64 #define CYG_ENABLE_TRACE 1 | |
| 65 | |
| 66 //========================================================================== | |
| 67 // Cyg_Scheduler_Implementation class static members | |
| 68 | |
| 69 #ifdef CYGSEM_KERNEL_SCHED_TIMESLICE | |
| 70 | |
| 71 cyg_count32 Cyg_Scheduler_Implementation::timeslice_count = | |
| 72 CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS; | |
| 73 | |
| 74 #endif | |
| 75 | |
| 76 //========================================================================== | |
| 77 // Cyg_Scheduler_Implementation class members | |
| 78 | |
| 79 // ------------------------------------------------------------------------- | |
| 80 // Constructor. | |
| 81 | |
| 82 Cyg_Scheduler_Implementation::Cyg_Scheduler_Implementation() | |
| 83 { | |
| 84 CYG_REPORT_FUNCTION(); | |
| 85 | |
| 86 total_tickets = 0; | |
| 87 rand_seed = 1; | |
| 88 } | |
| 89 | |
| 90 // ------------------------------------------------------------------------- | |
| 91 // Choose the best thread to run next | |
| 92 | |
| 93 Cyg_Thread *Cyg_Scheduler_Implementation::schedule() | |
| 94 { | |
| 95 CYG_REPORT_FUNCTION(); | |
| 96 | |
|
68
f74b2666b30d
Merge from eCos master repository on 2000-02-04-07:47:04-GMT
jlarmour
parents:
66
diff
changeset
|
97 #ifdef CYGPKG_HAL_POWERPC |
| 0 | 98 |
| 99 // PowerPc specific version of random number generator. | |
| 100 register cyg_int32 r1 asm("r4"); | |
| 101 r1 = rand_seed; | |
| 102 asm( | |
| 103 "li 7,0;" | |
| 104 "ori 7,7,33614;" | |
| 105 "mulhwu 5,7,%0;" | |
| 106 "mullw 6,7,%0;" | |
| 107 "srawi 6,6,1;" | |
| 108 "add %0,5,6;" | |
| 109 "cmpwi %0,0;" | |
| 110 "bge 1f;" | |
| 111 "slwi %0,%0,1;" | |
| 112 "srwi %0,%0,1;" | |
| 113 "addi %0,%0,1;" | |
| 114 "1:;" | |
| 115 : "=r"(r1) | |
| 116 : "0"(r1) | |
| 117 : "r5", "r6", "r7" | |
| 118 ); | |
| 119 rand_seed = r1; | |
| 120 | |
| 121 #else | |
| 122 #if 1 | |
| 123 rand_seed = (rand_seed * 1103515245) + 1234; | |
| 124 cyg_int32 r1 = rand_seed & 0x7FFFFFFF; | |
| 125 #else | |
| 126 // Generic implementation of RNG. | |
| 127 #if( CYG_BYTEORDER == CYG_MSBFIRST ) | |
| 128 #define _LO 1 | |
| 129 #define _HI 0 | |
| 130 #else | |
| 131 #define _LO 0 | |
| 132 #define _HI 1 | |
| 133 #endif | |
| 134 union { cyg_int64 r64; cyg_int32 r32[2]; } u; | |
| 135 u.r64 = (cyg_int64)rand_seed * 33614LL; | |
| 136 cyg_int32 r1 = u.r32[_HI] + (u.r32[_LO]>>1); | |
| 137 if( r1 < 0 ) | |
| 138 r1 = (r1 & 0x7FFFFFFF) + 1; | |
| 139 rand_seed = r1; | |
| 140 #undef _LO | |
| 141 #undef _HI | |
| 142 #endif | |
| 143 #endif | |
| 144 | |
| 145 cyg_int32 ticket = r1 % total_tickets; | |
| 146 cyg_int32 tick = ticket; | |
| 147 Cyg_Thread *thread = run_queue.highpri(); | |
| 148 | |
| 149 // Search the run queue for the thread with the | |
| 150 // given ticket. | |
| 151 while( ticket > 0 ) | |
| 152 { | |
| 153 ticket -= thread->priority; | |
| 154 if( ticket <= 0 ) break; | |
| 155 thread = thread->next; | |
| 156 | |
| 157 CYG_ASSERT( thread != run_queue.highpri(), "Looping in scheduler"); | |
| 158 } | |
| 159 | |
| 160 CYG_TRACE3( CYG_ENABLE_TRACE, | |
| 2 | 161 "seed %08x ticket %d thread %08x", |
| 0 | 162 rand_seed, tick, thread); |
| 163 | |
| 164 // If the thread has any compensation tickets, take them away since | |
| 165 // it has just won. | |
| 166 | |
| 167 if( thread->compensation_tickets > 0 ) | |
| 168 { | |
| 169 thread->priority -= thread->compensation_tickets; | |
| 170 total_tickets -= thread->compensation_tickets; | |
| 171 thread->compensation_tickets = 0; | |
| 172 } | |
| 173 | |
| 174 // Re-insert thread at head of list. This reduces runtime by | |
| 175 // putting the large ticket holders at the front of the list. | |
| 176 | |
| 177 // run_queue.remove(thread); | |
| 178 // run_queue.enqueue(thread); | |
| 179 | |
| 180 CYG_CHECK_DATA_PTR( thread, "Invalid next thread pointer"); | |
| 181 CYG_ASSERTCLASS( thread, "Bad next thread" ); | |
| 182 | |
| 183 return thread; | |
| 184 } | |
| 185 | |
| 186 // ------------------------------------------------------------------------- | |
| 187 | |
| 188 void Cyg_Scheduler_Implementation::add_thread(Cyg_Thread *thread) | |
| 189 { | |
| 190 CYG_REPORT_FUNCTION(); | |
| 191 | |
| 192 // If the thread is on some other queue, remove it | |
| 193 // here. | |
| 194 if( thread->queue != NULL ) | |
| 195 { | |
| 196 thread->queue->remove(thread); | |
| 197 thread->queue = NULL; | |
| 198 } | |
| 199 | |
| 200 total_tickets += thread->priority; | |
| 201 | |
| 202 run_queue.enqueue(thread); | |
| 203 } | |
| 204 | |
| 205 // ------------------------------------------------------------------------- | |
| 206 | |
| 207 void Cyg_Scheduler_Implementation::rem_thread(Cyg_Thread *thread) | |
| 208 { | |
| 209 CYG_REPORT_FUNCTION(); | |
| 210 | |
| 211 run_queue.remove(thread); | |
| 212 | |
| 213 total_tickets -= thread->priority; | |
| 214 | |
| 215 // Compensate the thread for the segment of the quantum that | |
| 216 // it used. This makes it more likely to win the lottery next time | |
| 217 // it is scheduled. We only do this for threads that have voluntarily | |
| 218 // given up the CPU. | |
| 219 | |
| 220 // if( thread->get_state() != Cyg_Thread::RUNNING ) | |
| 221 { | |
| 222 #if 0 | |
| 223 cyg_uint32 hal_ticks; | |
| 224 HAL_CLOCK_READ( &hal_ticks ); | |
| 225 thread->compensation_tickets = thread->priority * | |
| 226 CYGNUM_KERNEL_COUNTERS_RTC_PERIOD / hal_ticks; | |
| 227 #else | |
| 228 thread->compensation_tickets = (thread->priority * | |
| 229 CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS) / timeslice_count; | |
| 230 | |
| 231 #endif | |
| 232 thread->priority += thread->compensation_tickets; | |
| 233 } | |
| 234 } | |
| 235 | |
| 236 // ------------------------------------------------------------------------- | |
| 237 // register thread with scheduler | |
| 238 | |
| 239 void Cyg_Scheduler_Implementation::register_thread(Cyg_Thread *thread) | |
| 240 { | |
| 241 CYG_REPORT_FUNCTION(); | |
| 242 | |
| 243 // No registration necessary in this scheduler | |
| 244 } | |
| 245 | |
| 246 // ------------------------------------------------------------------------- | |
| 247 | |
| 248 // deregister thread | |
| 249 void Cyg_Scheduler_Implementation::deregister_thread(Cyg_Thread *thread) | |
| 250 { | |
| 251 CYG_REPORT_FUNCTION(); | |
| 252 | |
| 253 // No registration necessary in this scheduler | |
| 254 } | |
| 255 | |
| 256 // ------------------------------------------------------------------------- | |
| 257 // Test the given priority for uniqueness | |
| 258 | |
| 259 cyg_bool Cyg_Scheduler_Implementation::unique( cyg_priority priority) | |
| 260 { | |
| 261 CYG_REPORT_FUNCTION(); | |
| 262 | |
| 263 // Priorities are not unique | |
| 264 return true; | |
| 265 } | |
| 266 | |
| 267 //========================================================================== | |
| 268 // Support for timeslicing option | |
| 269 | |
| 270 #ifdef CYGSEM_KERNEL_SCHED_TIMESLICE | |
| 271 | |
| 272 void Cyg_Scheduler_Implementation::timeslice() | |
| 273 { | |
| 274 CYG_REPORT_FUNCTION(); | |
| 275 | |
| 276 if( --timeslice_count <= 0 ) | |
| 277 { | |
| 278 CYG_INSTRUMENT_SCHED(TIMESLICE,0,0); | |
| 279 | |
| 280 // Force a reschedule on each timeslice | |
| 281 need_reschedule = true; | |
| 282 timeslice_count = CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS; | |
| 283 } | |
| 284 } | |
| 285 | |
| 286 #endif | |
| 287 | |
| 288 //========================================================================== | |
| 289 // Cyg_Cyg_SchedThread_Implementation class members | |
| 290 | |
| 291 Cyg_SchedThread_Implementation::Cyg_SchedThread_Implementation | |
| 292 ( | |
| 293 CYG_ADDRWORD sched_info | |
| 294 ) | |
| 295 { | |
| 296 CYG_REPORT_FUNCTION(); | |
| 297 | |
| 298 priority = cyg_priority(sched_info); | |
| 299 | |
| 300 // point the next and prev field at this thread. | |
| 301 | |
| 302 next = prev = CYG_CLASSFROMBASE(Cyg_Thread, | |
| 303 Cyg_SchedThread_Implementation, | |
| 304 this); | |
| 305 } | |
| 306 | |
| 307 // ------------------------------------------------------------------------- | |
| 308 // Insert thread in front of this | |
| 309 | |
| 310 void Cyg_SchedThread_Implementation::insert( Cyg_Thread *thread) | |
| 311 { | |
| 312 CYG_REPORT_FUNCTION(); | |
| 313 | |
| 314 thread->next = CYG_CLASSFROMBASE(Cyg_Thread, | |
| 315 Cyg_SchedThread_Implementation, | |
| 316 this); | |
| 317 thread->prev = prev; | |
| 318 prev->next = thread; | |
| 319 prev = thread; | |
| 320 } | |
| 321 | |
| 322 // ------------------------------------------------------------------------- | |
| 323 // remove this from queue | |
| 324 | |
| 325 void Cyg_SchedThread_Implementation::remove() | |
| 326 { | |
| 327 CYG_REPORT_FUNCTION(); | |
| 328 | |
| 329 next->prev = prev; | |
| 330 prev->next = next; | |
| 331 next = prev = CYG_CLASSFROMBASE(Cyg_Thread, | |
| 332 Cyg_SchedThread_Implementation, | |
| 333 this); | |
| 334 } | |
| 335 | |
| 336 // ------------------------------------------------------------------------- | |
| 337 // Yield the processor to another thread | |
| 338 | |
| 339 void Cyg_SchedThread_Implementation::yield() | |
| 340 { | |
| 341 CYG_REPORT_FUNCTION(); | |
| 342 | |
| 343 | |
| 344 } | |
| 345 | |
| 346 //========================================================================== | |
| 347 // Cyg_ThreadQueue_Implementation class members | |
| 348 | |
| 349 void Cyg_ThreadQueue_Implementation::enqueue(Cyg_Thread *thread) | |
| 350 { | |
| 351 CYG_REPORT_FUNCTION(); | |
| 352 | |
| 353 // Always put thread at head of queue | |
| 354 if( queue == NULL ) queue = thread; | |
| 355 else | |
| 356 { | |
| 357 queue->insert(thread); | |
| 358 // queue->next->insert(thread); | |
| 359 // queue = thread; | |
| 360 } | |
| 361 | |
| 362 thread->queue = CYG_CLASSFROMBASE(Cyg_ThreadQueue, | |
| 363 Cyg_ThreadQueue_Implementation, | |
| 364 this); | |
| 365 } | |
| 366 | |
| 367 // ------------------------------------------------------------------------- | |
| 368 | |
| 369 Cyg_Thread *Cyg_ThreadQueue_Implementation::dequeue() | |
| 370 { | |
| 371 CYG_REPORT_FUNCTION(); | |
| 372 | |
| 373 if( queue == NULL ) return NULL; | |
| 374 | |
| 375 Cyg_Thread *thread = queue; | |
| 376 | |
| 377 if( thread->next == thread ) | |
| 378 { | |
| 379 // sole thread on list, NULL out ptr | |
| 380 queue = NULL; | |
| 381 } | |
| 382 else | |
| 383 { | |
| 384 // advance to next and remove thread | |
| 385 queue = thread->next; | |
| 386 thread->remove(); | |
| 387 } | |
| 388 | |
| 389 thread->queue = NULL; | |
| 390 | |
| 391 return thread; | |
| 392 } | |
| 393 | |
| 394 // ------------------------------------------------------------------------- | |
| 395 | |
| 396 Cyg_Thread *Cyg_ThreadQueue_Implementation::highpri() | |
| 397 { | |
| 398 CYG_REPORT_FUNCTION(); | |
| 399 | |
| 400 return queue; | |
| 401 } | |
| 402 | |
| 403 // ------------------------------------------------------------------------- | |
| 404 | |
| 405 void Cyg_ThreadQueue_Implementation::remove(Cyg_Thread *thread) | |
| 406 { | |
| 407 CYG_REPORT_FUNCTION(); | |
| 408 | |
| 409 // If the thread we want is the at the head | |
| 410 // of the list, and is on its own, clear the | |
| 411 // list and return. Otherwise advance to the | |
| 412 // next thread and remove ours. If the thread | |
| 413 // is not at the head of the list, just dequeue | |
| 414 // it. | |
| 415 | |
| 416 thread->queue = NULL; | |
| 417 | |
| 418 if( queue == thread ) | |
| 419 { | |
| 420 if( thread->next == thread ) | |
| 421 { | |
| 422 queue = NULL; | |
| 423 return; | |
| 424 } | |
| 425 else queue = thread->next; | |
| 426 } | |
| 427 | |
| 428 thread->Cyg_SchedThread_Implementation::remove(); | |
| 429 | |
| 430 } | |
| 431 | |
| 432 // ------------------------------------------------------------------------- | |
| 433 // Rotate the front thread on the queue to the back. | |
| 434 | |
| 435 void Cyg_ThreadQueue_Implementation::rotate() | |
| 436 { | |
| 437 CYG_REPORT_FUNCTION(); | |
| 438 | |
| 439 queue = queue->next; | |
| 440 } | |
| 441 | |
| 442 // ------------------------------------------------------------------------- | |
| 443 | |
| 444 #endif | |
| 445 | |
| 446 // ------------------------------------------------------------------------- | |
| 447 // EOF sched/lottery.cxx |