scheduler.hh revision 13287:fa657c66fc83
112600Sodanrc@yahoo.com.br/* 212600Sodanrc@yahoo.com.br * Copyright 2018 Google, Inc. 312600Sodanrc@yahoo.com.br * 412600Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 512600Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 612600Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 712600Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 812600Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 912600Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1012600Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1112600Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1212600Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1312600Sodanrc@yahoo.com.br * this software without specific prior written permission. 1412600Sodanrc@yahoo.com.br * 1512600Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1612600Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1712600Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1812600Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1912600Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2012600Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2112600Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2212600Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2312600Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2412600Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2512600Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2612600Sodanrc@yahoo.com.br * 2712600Sodanrc@yahoo.com.br * Authors: Gabe Black 2812600Sodanrc@yahoo.com.br */ 2912600Sodanrc@yahoo.com.br 3012600Sodanrc@yahoo.com.br#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 3112600Sodanrc@yahoo.com.br#define __SYSTEMC_CORE_SCHEDULER_HH__ 3212600Sodanrc@yahoo.com.br 3312600Sodanrc@yahoo.com.br#include <functional> 3412600Sodanrc@yahoo.com.br#include <map> 3512600Sodanrc@yahoo.com.br#include <set> 3612600Sodanrc@yahoo.com.br#include <vector> 3712600Sodanrc@yahoo.com.br 3812607Sodanrc@yahoo.com.br#include "base/logging.hh" 3912607Sodanrc@yahoo.com.br#include "sim/core.hh" 4012607Sodanrc@yahoo.com.br#include "sim/eventq.hh" 4112607Sodanrc@yahoo.com.br#include "systemc/core/channel.hh" 4212607Sodanrc@yahoo.com.br#include "systemc/core/list.hh" 4312628Sodanrc@yahoo.com.br#include "systemc/core/process.hh" 4412628Sodanrc@yahoo.com.br#include "systemc/core/sched_event.hh" 4512628Sodanrc@yahoo.com.br 4612628Sodanrc@yahoo.com.brclass Fiber; 4712628Sodanrc@yahoo.com.br 4812600Sodanrc@yahoo.com.brnamespace sc_gem5 4912600Sodanrc@yahoo.com.br{ 5012600Sodanrc@yahoo.com.br 5112600Sodanrc@yahoo.com.brclass TraceFile; 5212600Sodanrc@yahoo.com.br 5312634Sodanrc@yahoo.com.brtypedef NodeList<Process> ProcessList; 5412634Sodanrc@yahoo.com.brtypedef NodeList<Channel> ChannelList; 5512634Sodanrc@yahoo.com.br 5612634Sodanrc@yahoo.com.br/* 5712634Sodanrc@yahoo.com.br * The scheduler supports three different mechanisms, the initialization phase, 5812634Sodanrc@yahoo.com.br * delta cycles, and timed notifications. 5912635Sodanrc@yahoo.com.br * 6012635Sodanrc@yahoo.com.br * INITIALIZATION PHASE 6112635Sodanrc@yahoo.com.br * 6212601Sodanrc@yahoo.com.br * The initialization phase has three parts: 6312601Sodanrc@yahoo.com.br * 1. Run requested channel updates. 6412601Sodanrc@yahoo.com.br * 2. Make processes which need to initialize runnable (methods and threads 6512601Sodanrc@yahoo.com.br * which didn't have dont_initialize called on them). 6612601Sodanrc@yahoo.com.br * 3. Process delta notifications. 6712600Sodanrc@yahoo.com.br * 6812600Sodanrc@yahoo.com.br * First, the Kernel SimObject calls the update() method during its startup() 6912600Sodanrc@yahoo.com.br * callback which handles the requested channel updates. The Kernel also 7012600Sodanrc@yahoo.com.br * schedules an event to be run at time 0 with a slightly elevated priority 7112626Sodanrc@yahoo.com.br * so that it happens before any "normal" event. 7212626Sodanrc@yahoo.com.br * 7312626Sodanrc@yahoo.com.br * When that t0 event happens, it calls the schedulers prepareForInit method 7412626Sodanrc@yahoo.com.br * which performs step 2 above. That indirectly causes the scheduler's 7512626Sodanrc@yahoo.com.br * readyEvent to be scheduled with slightly lowered priority, ensuring it 7612626Sodanrc@yahoo.com.br * happens after any "normal" event. 7712626Sodanrc@yahoo.com.br * 7812626Sodanrc@yahoo.com.br * Because delta notifications are scheduled at the standard priority, all 7912626Sodanrc@yahoo.com.br * of those events will happen next, performing step 3 above. Once they finish, 8012626Sodanrc@yahoo.com.br * if the readyEvent was scheduled above, there shouldn't be any higher 8112627Sodanrc@yahoo.com.br * priority events in front of it. When it runs, it will start the first 8212627Sodanrc@yahoo.com.br * evaluate phase of the first delta cycle. 8312627Sodanrc@yahoo.com.br * 84 * DELTA CYCLE 85 * 86 * A delta cycle has three phases within it. 87 * 1. The evaluate phase where runnable processes are allowed to run. 88 * 2. The update phase where requested channel updates hapen. 89 * 3. The delta notification phase where delta notifications happen. 90 * 91 * The readyEvent runs all three steps of the delta cycle. It first goes 92 * through the list of runnable processes and executes them until the set is 93 * empty, and then immediately runs the update phase. Since these are all part 94 * of the same event, there's no chance for other events to intervene and 95 * break the required order above. 96 * 97 * During the update phase above, the spec forbids any action which would make 98 * a process runnable. That means that once the update phase finishes, the set 99 * of runnable processes will be empty. There may, however, have been some 100 * delta notifications/timeouts which will have been scheduled during either 101 * the evaluate or update phase above. Those will have been accumulated in the 102 * scheduler, and are now all executed. 103 * 104 * If any processes became runnable during the delta notification phase, the 105 * readyEvent will have been scheduled and will be waiting and ready to run 106 * again, effectively starting the next delta cycle. 107 * 108 * TIMED NOTIFICATION PHASE 109 * 110 * If no processes became runnable, the event queue will continue to process 111 * events until it comes across an event which represents all the timed 112 * notifications which are supposed to happen at a particular time. The object 113 * which tracks them will execute all those notifications, and then destroy 114 * itself. If the readyEvent is now ready to run, the next delta cycle will 115 * start. 116 * 117 * PAUSE/STOP 118 * 119 * To inject a pause from sc_pause which should happen after the current delta 120 * cycle's delta notification phase, an event is scheduled with a lower than 121 * normal priority, but higher than the readyEvent. That ensures that any 122 * delta notifications which are scheduled with normal priority will happen 123 * first, since those are part of the current delta cycle. Then the pause 124 * event will happen before the next readyEvent which would start the next 125 * delta cycle. All of these events are scheduled for the current time, and so 126 * would happen before any timed notifications went off. 127 * 128 * To inject a stop from sc_stop, the delta cycles should stop before even the 129 * delta notifications have happened, but after the evaluate and update phases. 130 * For that, a stop event with slightly higher than normal priority will be 131 * scheduled so that it happens before any of the delta notification events 132 * which are at normal priority. 133 * 134 * MAX RUN TIME 135 * 136 * When sc_start is called, it's possible to pass in a maximum time the 137 * simulation should run to, at which point sc_pause is implicitly called. The 138 * simulation is supposed to run up to the latest timed notification phase 139 * which is less than or equal to the maximum time. In other words it should 140 * run timed notifications at the maximum time, but not the subsequent evaluate 141 * phase. That's implemented by scheduling an event at the max time with a 142 * priority which is lower than all the others except the ready event. Timed 143 * notifications will happen before it fires, but it will override any ready 144 * event and prevent the evaluate phase from starting. 145 */ 146 147class Scheduler 148{ 149 public: 150 typedef std::list<ScEvent *> ScEvents; 151 152 class TimeSlot : public ::Event 153 { 154 public: 155 TimeSlot() : ::Event(Default_Pri, AutoDelete) {} 156 157 ScEvents events; 158 void process(); 159 }; 160 161 typedef std::map<Tick, TimeSlot *> TimeSlots; 162 163 Scheduler(); 164 ~Scheduler(); 165 166 void clear(); 167 168 const std::string name() const { return "systemc_scheduler"; } 169 170 uint64_t numCycles() { return _numCycles; } 171 Process *current() { return _current; } 172 173 void initPhase(); 174 175 // Register a process with the scheduler. 176 void reg(Process *p); 177 178 // Run the next process, if there is one. 179 void yield(); 180 181 // Put a process on the ready list. 182 void ready(Process *p); 183 184 // Mark a process as ready if init is finished, or put it on the list of 185 // processes to be initialized. 186 void resume(Process *p); 187 188 // Remove a process from the ready/init list if it was on one of them, and 189 // return if it was. 190 bool suspend(Process *p); 191 192 // Schedule an update for a given channel. 193 void requestUpdate(Channel *c); 194 195 // Run the given process immediately, preempting whatever may be running. 196 void 197 runNow(Process *p) 198 { 199 // This function may put a process on the wrong list, ie a thread 200 // the method list. That's fine since that's just a performance 201 // optimization, and the important thing here is how the processes are 202 // ordered. 203 204 // If a process is running, schedule it/us to run again. 205 if (_current) 206 readyListMethods.pushFirst(_current); 207 // Schedule p to run first. 208 readyListMethods.pushFirst(p); 209 yield(); 210 } 211 212 // Run this process at the next opportunity. 213 void 214 runNext(Process *p) 215 { 216 // Like above, it's ok if this isn't a method. Putting it on this list 217 // just gives it priority. 218 readyListMethods.pushFirst(p); 219 if (!inEvaluate()) 220 scheduleReadyEvent(); 221 } 222 223 // Set an event queue for scheduling events. 224 void setEventQueue(EventQueue *_eq) { eq = _eq; } 225 226 // Get the current time according to gem5. 227 Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 228 229 Tick 230 delayed(const ::sc_core::sc_time &delay) 231 { 232 return getCurTick() + delay.value(); 233 } 234 235 // For scheduling delayed/timed notifications/timeouts. 236 void 237 schedule(ScEvent *event, const ::sc_core::sc_time &delay) 238 { 239 Tick tick = delayed(delay); 240 if (tick < getCurTick()) 241 tick = getCurTick(); 242 243 // Delta notification/timeout. 244 if (delay.value() == 0) { 245 event->schedule(deltas, tick); 246 if (!inEvaluate() && !inUpdate()) 247 scheduleReadyEvent(); 248 return; 249 } 250 251 // Timed notification/timeout. 252 TimeSlot *&ts = timeSlots[tick]; 253 if (!ts) { 254 ts = new TimeSlot; 255 schedule(ts, tick); 256 } 257 event->schedule(ts->events, tick); 258 } 259 260 // For descheduling delayed/timed notifications/timeouts. 261 void 262 deschedule(ScEvent *event) 263 { 264 ScEvents *on = event->scheduledOn(); 265 266 if (on == &deltas) { 267 event->deschedule(); 268 return; 269 } 270 271 // Timed notification/timeout. 272 auto tsit = timeSlots.find(event->when()); 273 panic_if(tsit == timeSlots.end(), 274 "Descheduling event at time with no events."); 275 TimeSlot *ts = tsit->second; 276 ScEvents &events = ts->events; 277 assert(on == &events); 278 event->deschedule(); 279 280 // If no more events are happening at this time slot, get rid of it. 281 if (events.empty()) { 282 deschedule(ts); 283 timeSlots.erase(tsit); 284 } 285 } 286 287 void 288 completeTimeSlot(TimeSlot *ts) 289 { 290 assert(ts == timeSlots.begin()->second); 291 timeSlots.erase(timeSlots.begin()); 292 if (!runToTime && starved()) 293 scheduleStarvationEvent(); 294 scheduleTimeAdvancesEvent(); 295 } 296 297 // Pending activity ignores gem5 activity, much like how a systemc 298 // simulation wouldn't know about asynchronous external events (socket IO 299 // for instance) that might happen before time advances in a pure 300 // systemc simulation. Also the spec lists what specific types of pending 301 // activity needs to be counted, which obviously doesn't include gem5 302 // events. 303 304 // Return whether there's pending systemc activity at this time. 305 bool 306 pendingCurr() 307 { 308 return !readyListMethods.empty() || !readyListThreads.empty() || 309 !updateList.empty() || !deltas.empty(); 310 } 311 312 // Return whether there are pending timed notifications or timeouts. 313 bool 314 pendingFuture() 315 { 316 return !timeSlots.empty(); 317 } 318 319 // Return how many ticks there are until the first pending event, if any. 320 Tick 321 timeToPending() 322 { 323 if (pendingCurr()) 324 return 0; 325 if (pendingFuture()) 326 return timeSlots.begin()->first - getCurTick(); 327 return MaxTick - getCurTick(); 328 } 329 330 // Run scheduled channel updates. 331 void runUpdate(); 332 333 // Run delta events. 334 void runDelta(); 335 336 void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 337 338 void start(Tick max_tick, bool run_to_time); 339 void oneCycle(); 340 341 void schedulePause(); 342 void scheduleStop(bool finish_delta); 343 344 enum Status 345 { 346 StatusOther = 0, 347 StatusEvaluate, 348 StatusUpdate, 349 StatusDelta, 350 StatusTiming, 351 StatusPaused, 352 StatusStopped 353 }; 354 355 bool elaborationDone() { return _elaborationDone; } 356 void elaborationDone(bool b) { _elaborationDone = b; } 357 358 bool paused() { return status() == StatusPaused; } 359 bool stopped() { return status() == StatusStopped; } 360 bool inEvaluate() { return status() == StatusEvaluate; } 361 bool inUpdate() { return status() == StatusUpdate; } 362 bool inDelta() { return status() == StatusDelta; } 363 bool inTiming() { return status() == StatusTiming; } 364 365 uint64_t changeStamp() { return _changeStamp; } 366 void stepChangeStamp() { _changeStamp++; } 367 368 void throwToScMain(); 369 370 Status status() { return _status; } 371 void status(Status s) { _status = s; } 372 373 void registerTraceFile(TraceFile *tf) { traceFiles.insert(tf); } 374 void unregisterTraceFile(TraceFile *tf) { traceFiles.erase(tf); } 375 376 private: 377 typedef const EventBase::Priority Priority; 378 static Priority DefaultPriority = EventBase::Default_Pri; 379 380 static Priority StopPriority = DefaultPriority - 1; 381 static Priority PausePriority = DefaultPriority + 1; 382 static Priority MaxTickPriority = DefaultPriority + 2; 383 static Priority ReadyPriority = DefaultPriority + 3; 384 static Priority StarvationPriority = ReadyPriority; 385 static Priority TimeAdvancesPriority = EventBase::Maximum_Pri; 386 387 EventQueue *eq; 388 389 // For gem5 style events. 390 void 391 schedule(::Event *event, Tick tick) 392 { 393 if (initDone) 394 eq->schedule(event, tick); 395 else 396 eventsToSchedule[event] = tick; 397 } 398 399 void schedule(::Event *event) { schedule(event, getCurTick()); } 400 401 void 402 deschedule(::Event *event) 403 { 404 if (initDone) 405 eq->deschedule(event); 406 else 407 eventsToSchedule.erase(event); 408 } 409 410 ScEvents deltas; 411 TimeSlots timeSlots; 412 413 Process * 414 getNextReady() 415 { 416 Process *p = readyListMethods.getNext(); 417 return p ? p : readyListThreads.getNext(); 418 } 419 420 void runReady(); 421 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 422 void scheduleReadyEvent(); 423 424 void pause(); 425 void stop(); 426 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 427 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 428 429 Fiber *scMain; 430 const ::sc_core::sc_report *_throwToScMain; 431 432 bool 433 starved() 434 { 435 return (readyListMethods.empty() && readyListThreads.empty() && 436 updateList.empty() && deltas.empty() && 437 (timeSlots.empty() || timeSlots.begin()->first > maxTick) && 438 initList.empty()); 439 } 440 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 441 void scheduleStarvationEvent(); 442 443 bool _elaborationDone; 444 bool _started; 445 bool _stopNow; 446 447 Status _status; 448 449 Tick maxTick; 450 Tick lastReadyTick; 451 void 452 maxTickFunc() 453 { 454 if (lastReadyTick != getCurTick()) 455 _changeStamp++; 456 pause(); 457 } 458 EventWrapper<Scheduler, &Scheduler::maxTickFunc> maxTickEvent; 459 460 void timeAdvances() { trace(false); } 461 EventWrapper<Scheduler, &Scheduler::timeAdvances> timeAdvancesEvent; 462 void 463 scheduleTimeAdvancesEvent() 464 { 465 if (!traceFiles.empty() && !timeAdvancesEvent.scheduled()) 466 schedule(&timeAdvancesEvent); 467 } 468 469 uint64_t _numCycles; 470 uint64_t _changeStamp; 471 472 Process *_current; 473 474 bool initDone; 475 bool runToTime; 476 bool runOnce; 477 478 ProcessList initList; 479 480 ProcessList readyListMethods; 481 ProcessList readyListThreads; 482 483 ChannelList updateList; 484 485 std::map<::Event *, Tick> eventsToSchedule; 486 487 std::set<TraceFile *> traceFiles; 488 489 void trace(bool delta); 490}; 491 492extern Scheduler scheduler; 493 494inline void 495Scheduler::TimeSlot::process() 496{ 497 scheduler.stepChangeStamp(); 498 scheduler.status(StatusTiming); 499 500 try { 501 while (!events.empty()) 502 events.front()->run(); 503 } catch (...) { 504 if (events.empty()) 505 scheduler.completeTimeSlot(this); 506 else 507 scheduler.schedule(this); 508 scheduler.throwToScMain(); 509 } 510 511 scheduler.status(StatusOther); 512 scheduler.completeTimeSlot(this); 513} 514 515const ::sc_core::sc_report reportifyException(); 516 517} // namespace sc_gem5 518 519#endif // __SYSTEMC_CORE_SCHEDULER_H__ 520