scheduler.hh revision 13209:aad30faa966b
12SN/A/* 29235Sandreas.hansson@arm.com * Copyright 2018 Google, Inc. 39235Sandreas.hansson@arm.com * 49235Sandreas.hansson@arm.com * Redistribution and use in source and binary forms, with or without 59235Sandreas.hansson@arm.com * modification, are permitted provided that the following conditions are 69235Sandreas.hansson@arm.com * met: redistributions of source code must retain the above copyright 79235Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer; 89235Sandreas.hansson@arm.com * redistributions in binary form must reproduce the above copyright 99235Sandreas.hansson@arm.com * notice, this list of conditions and the following disclaimer in the 109235Sandreas.hansson@arm.com * documentation and/or other materials provided with the distribution; 119235Sandreas.hansson@arm.com * neither the name of the copyright holders nor the names of its 129235Sandreas.hansson@arm.com * contributors may be used to endorse or promote products derived from 139235Sandreas.hansson@arm.com * this software without specific prior written permission. 141762SN/A * 152SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 162SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 172SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 182SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 192SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 202SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 212SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 222SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 232SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 242SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 252SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 262SN/A * 272SN/A * Authors: Gabe Black 282SN/A */ 292SN/A 302SN/A#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 312SN/A#define __SYSTEMC_CORE_SCHEDULER_HH__ 322SN/A 332SN/A#include <functional> 342SN/A#include <map> 352SN/A#include <set> 362SN/A#include <vector> 372SN/A 382SN/A#include "base/logging.hh" 392665SN/A#include "sim/core.hh" 402665SN/A#include "sim/eventq.hh" 412665SN/A#include "systemc/core/channel.hh" 429235Sandreas.hansson@arm.com#include "systemc/core/list.hh" 432SN/A#include "systemc/core/process.hh" 442SN/A#include "systemc/core/sched_event.hh" 459235Sandreas.hansson@arm.com 469235Sandreas.hansson@arm.comclass Fiber; 472SN/A 489411Sandreas.hansson@arm.comnamespace sc_gem5 499405Sandreas.hansson@arm.com{ 509411Sandreas.hansson@arm.com 519235Sandreas.hansson@arm.comtypedef NodeList<Process> ProcessList; 529235Sandreas.hansson@arm.comtypedef NodeList<Channel> ChannelList; 539235Sandreas.hansson@arm.com 542SN/A/* 552SN/A * The scheduler supports three different mechanisms, the initialization phase, 569405Sandreas.hansson@arm.com * delta cycles, and timed notifications. 579405Sandreas.hansson@arm.com * 589411Sandreas.hansson@arm.com * INITIALIZATION PHASE 599405Sandreas.hansson@arm.com * 609405Sandreas.hansson@arm.com * The initialization phase has three parts: 619405Sandreas.hansson@arm.com * 1. Run requested channel updates. 629411Sandreas.hansson@arm.com * 2. Make processes which need to initialize runnable (methods and threads 639411Sandreas.hansson@arm.com * which didn't have dont_initialize called on them). 649411Sandreas.hansson@arm.com * 3. Process delta notifications. 659411Sandreas.hansson@arm.com * 669411Sandreas.hansson@arm.com * First, the Kernel SimObject calls the update() method during its startup() 679411Sandreas.hansson@arm.com * callback which handles the requested channel updates. The Kernel also 689411Sandreas.hansson@arm.com * schedules an event to be run at time 0 with a slightly elevated priority 699411Sandreas.hansson@arm.com * so that it happens before any "normal" event. 709411Sandreas.hansson@arm.com * 719411Sandreas.hansson@arm.com * When that t0 event happens, it calls the schedulers prepareForInit method 729235Sandreas.hansson@arm.com * which performs step 2 above. That indirectly causes the scheduler's 732SN/A * readyEvent to be scheduled with slightly lowered priority, ensuring it 749235Sandreas.hansson@arm.com * happens after any "normal" event. 759411Sandreas.hansson@arm.com * 769411Sandreas.hansson@arm.com * Because delta notifications are scheduled at the standard priority, all 779411Sandreas.hansson@arm.com * of those events will happen next, performing step 3 above. Once they finish, 789411Sandreas.hansson@arm.com * if the readyEvent was scheduled above, there shouldn't be any higher 799411Sandreas.hansson@arm.com * priority events in front of it. When it runs, it will start the first 809411Sandreas.hansson@arm.com * evaluate phase of the first delta cycle. 819411Sandreas.hansson@arm.com * 829235Sandreas.hansson@arm.com * DELTA CYCLE 839235Sandreas.hansson@arm.com * 849235Sandreas.hansson@arm.com * A delta cycle has three phases within it. 859411Sandreas.hansson@arm.com * 1. The evaluate phase where runnable processes are allowed to run. 869411Sandreas.hansson@arm.com * 2. The update phase where requested channel updates hapen. 879235Sandreas.hansson@arm.com * 3. The delta notification phase where delta notifications happen. 889235Sandreas.hansson@arm.com * 899405Sandreas.hansson@arm.com * The readyEvent runs all three steps of the delta cycle. It first goes 909411Sandreas.hansson@arm.com * through the list of runnable processes and executes them until the set is 919411Sandreas.hansson@arm.com * empty, and then immediately runs the update phase. Since these are all part 929411Sandreas.hansson@arm.com * of the same event, there's no chance for other events to intervene and 939411Sandreas.hansson@arm.com * break the required order above. 949411Sandreas.hansson@arm.com * 959411Sandreas.hansson@arm.com * During the update phase above, the spec forbids any action which would make 969411Sandreas.hansson@arm.com * a process runnable. That means that once the update phase finishes, the set 979411Sandreas.hansson@arm.com * of runnable processes will be empty. There may, however, have been some 989411Sandreas.hansson@arm.com * delta notifications/timeouts which will have been scheduled during either 999411Sandreas.hansson@arm.com * the evaluate or update phase above. Those will have been accumulated in the 1009411Sandreas.hansson@arm.com * scheduler, and are now all executed. 1019411Sandreas.hansson@arm.com * 1029411Sandreas.hansson@arm.com * If any processes became runnable during the delta notification phase, the 1039411Sandreas.hansson@arm.com * readyEvent will have been scheduled and will be waiting and ready to run 1049411Sandreas.hansson@arm.com * again, effectively starting the next delta cycle. 1059411Sandreas.hansson@arm.com * 1069411Sandreas.hansson@arm.com * TIMED NOTIFICATION PHASE 1079411Sandreas.hansson@arm.com * 1089411Sandreas.hansson@arm.com * If no processes became runnable, the event queue will continue to process 1099411Sandreas.hansson@arm.com * events until it comes across an event which represents all the timed 1109411Sandreas.hansson@arm.com * notifications which are supposed to happen at a particular time. The object 1119411Sandreas.hansson@arm.com * which tracks them will execute all those notifications, and then destroy 1129405Sandreas.hansson@arm.com * itself. If the readyEvent is now ready to run, the next delta cycle will 1139411Sandreas.hansson@arm.com * start. 1149411Sandreas.hansson@arm.com * 1159405Sandreas.hansson@arm.com * PAUSE/STOP 1169411Sandreas.hansson@arm.com * 1179411Sandreas.hansson@arm.com * To inject a pause from sc_pause which should happen after the current delta 1189411Sandreas.hansson@arm.com * cycle's delta notification phase, an event is scheduled with a lower than 1199411Sandreas.hansson@arm.com * normal priority, but higher than the readyEvent. That ensures that any 120532SN/A * delta notifications which are scheduled with normal priority will happen 1219405Sandreas.hansson@arm.com * first, since those are part of the current delta cycle. Then the pause 1229405Sandreas.hansson@arm.com * event will happen before the next readyEvent which would start the next 1239405Sandreas.hansson@arm.com * delta cycle. All of these events are scheduled for the current time, and so 1249405Sandreas.hansson@arm.com * would happen before any timed notifications went off. 1259405Sandreas.hansson@arm.com * 1269405Sandreas.hansson@arm.com * To inject a stop from sc_stop, the delta cycles should stop before even the 1279405Sandreas.hansson@arm.com * delta notifications have happened, but after the evaluate and update phases. 1289405Sandreas.hansson@arm.com * For that, a stop event with slightly higher than normal priority will be 1299405Sandreas.hansson@arm.com * scheduled so that it happens before any of the delta notification events 1309405Sandreas.hansson@arm.com * which are at normal priority. 1319405Sandreas.hansson@arm.com * 1329405Sandreas.hansson@arm.com * MAX RUN TIME 1339405Sandreas.hansson@arm.com * 1349405Sandreas.hansson@arm.com * When sc_start is called, it's possible to pass in a maximum time the 1359405Sandreas.hansson@arm.com * simulation should run to, at which point sc_pause is implicitly called. The 1369405Sandreas.hansson@arm.com * simulation is supposed to run up to the latest timed notification phase 1379405Sandreas.hansson@arm.com * which is less than or equal to the maximum time. In other words it should 1389411Sandreas.hansson@arm.com * run timed notifications at the maximum time, but not the subsequent evaluate 1399411Sandreas.hansson@arm.com * phase. That's implemented by scheduling an event at the max time with a 1409411Sandreas.hansson@arm.com * priority which is lower than all the others except the ready event. Timed 1419411Sandreas.hansson@arm.com * notifications will happen before it fires, but it will override any ready 1429411Sandreas.hansson@arm.com * event and prevent the evaluate phase from starting. 1439411Sandreas.hansson@arm.com */ 1449411Sandreas.hansson@arm.com 1459411Sandreas.hansson@arm.comclass Scheduler 1469411Sandreas.hansson@arm.com{ 1479411Sandreas.hansson@arm.com public: 1489411Sandreas.hansson@arm.com typedef std::list<ScEvent *> ScEvents; 1499411Sandreas.hansson@arm.com 1509411Sandreas.hansson@arm.com class TimeSlot : public ::Event 1519411Sandreas.hansson@arm.com { 1529411Sandreas.hansson@arm.com public: 1539411Sandreas.hansson@arm.com TimeSlot() : ::Event(Default_Pri, AutoDelete) {} 1549411Sandreas.hansson@arm.com 1559411Sandreas.hansson@arm.com ScEvents events; 1569411Sandreas.hansson@arm.com void process(); 1579411Sandreas.hansson@arm.com }; 1589411Sandreas.hansson@arm.com 1599405Sandreas.hansson@arm.com typedef std::map<Tick, TimeSlot *> TimeSlots; 1609279Sandreas.hansson@arm.com 1619279Sandreas.hansson@arm.com Scheduler(); 1629279Sandreas.hansson@arm.com ~Scheduler(); 1639279Sandreas.hansson@arm.com 1649279Sandreas.hansson@arm.com void clear(); 1659279Sandreas.hansson@arm.com 1669279Sandreas.hansson@arm.com const std::string name() const { return "systemc_scheduler"; } 1679279Sandreas.hansson@arm.com 1689279Sandreas.hansson@arm.com uint64_t numCycles() { return _numCycles; } 1699279Sandreas.hansson@arm.com Process *current() { return _current; } 1709279Sandreas.hansson@arm.com 1719411Sandreas.hansson@arm.com void initPhase(); 1729411Sandreas.hansson@arm.com 1739411Sandreas.hansson@arm.com // Register a process with the scheduler. 1749411Sandreas.hansson@arm.com void reg(Process *p); 1759411Sandreas.hansson@arm.com 1769411Sandreas.hansson@arm.com // Run the next process, if there is one. 1779411Sandreas.hansson@arm.com void yield(); 1789411Sandreas.hansson@arm.com 1799411Sandreas.hansson@arm.com // Put a process on the ready list. 1809411Sandreas.hansson@arm.com void ready(Process *p); 1819411Sandreas.hansson@arm.com 1829411Sandreas.hansson@arm.com // Mark a process as ready if init is finished, or put it on the list of 1839411Sandreas.hansson@arm.com // processes to be initialized. 1849411Sandreas.hansson@arm.com void resume(Process *p); 1859411Sandreas.hansson@arm.com 1869411Sandreas.hansson@arm.com // Remove a process from the ready/init list if it was on one of them, and 1879411Sandreas.hansson@arm.com // return if it was. 1889411Sandreas.hansson@arm.com bool suspend(Process *p); 1899411Sandreas.hansson@arm.com 1909411Sandreas.hansson@arm.com // Schedule an update for a given channel. 1919279Sandreas.hansson@arm.com void requestUpdate(Channel *c); 1929279Sandreas.hansson@arm.com 1939279Sandreas.hansson@arm.com // Run the given process immediately, preempting whatever may be running. 1949279Sandreas.hansson@arm.com void 1959279Sandreas.hansson@arm.com runNow(Process *p) 1969279Sandreas.hansson@arm.com { 1979279Sandreas.hansson@arm.com // This function may put a process on the wrong list, ie a thread 1989279Sandreas.hansson@arm.com // the method list. That's fine since that's just a performance 1999279Sandreas.hansson@arm.com // optimization, and the important thing here is how the processes are 2009279Sandreas.hansson@arm.com // ordered. 2019279Sandreas.hansson@arm.com 2029279Sandreas.hansson@arm.com // If a process is running, schedule it/us to run again. 2039411Sandreas.hansson@arm.com if (_current) 2049411Sandreas.hansson@arm.com readyListMethods.pushFirst(_current); 2059405Sandreas.hansson@arm.com // Schedule p to run first. 2069279Sandreas.hansson@arm.com readyListMethods.pushFirst(p); 2079405Sandreas.hansson@arm.com yield(); 2089405Sandreas.hansson@arm.com } 2099405Sandreas.hansson@arm.com 2109405Sandreas.hansson@arm.com // Set an event queue for scheduling events. 2119405Sandreas.hansson@arm.com void setEventQueue(EventQueue *_eq) { eq = _eq; } 2129405Sandreas.hansson@arm.com 2139405Sandreas.hansson@arm.com // Get the current time according to gem5. 2149405Sandreas.hansson@arm.com Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 2159405Sandreas.hansson@arm.com 2169411Sandreas.hansson@arm.com Tick 2179411Sandreas.hansson@arm.com delayed(const ::sc_core::sc_time &delay) 2189411Sandreas.hansson@arm.com { 2199411Sandreas.hansson@arm.com //XXX We're assuming the systemc time resolution is in ps. 2209411Sandreas.hansson@arm.com return getCurTick() + delay.value() * SimClock::Int::ps; 2219411Sandreas.hansson@arm.com } 2229411Sandreas.hansson@arm.com 2239405Sandreas.hansson@arm.com // For scheduling delayed/timed notifications/timeouts. 2242SN/A void 225531SN/A schedule(ScEvent *event, const ::sc_core::sc_time &delay) 2269235Sandreas.hansson@arm.com { 227531SN/A Tick tick = delayed(delay); 2289235Sandreas.hansson@arm.com if (tick < getCurTick()) 2292SN/A tick = getCurTick(); 2309405Sandreas.hansson@arm.com 2319405Sandreas.hansson@arm.com // Delta notification/timeout. 2329405Sandreas.hansson@arm.com if (delay.value() == 0) { 2339405Sandreas.hansson@arm.com event->schedule(deltas, tick); 2349405Sandreas.hansson@arm.com scheduleReadyEvent(); 2359405Sandreas.hansson@arm.com return; 2369405Sandreas.hansson@arm.com } 2379405Sandreas.hansson@arm.com 2389405Sandreas.hansson@arm.com // Timed notification/timeout. 2399411Sandreas.hansson@arm.com TimeSlot *&ts = timeSlots[tick]; 2409411Sandreas.hansson@arm.com if (!ts) { 2419411Sandreas.hansson@arm.com ts = new TimeSlot; 2429411Sandreas.hansson@arm.com schedule(ts, tick); 2439411Sandreas.hansson@arm.com } 2449411Sandreas.hansson@arm.com event->schedule(ts->events, tick); 2459405Sandreas.hansson@arm.com } 246531SN/A 2479405Sandreas.hansson@arm.com // For descheduling delayed/timed notifications/timeouts. 2489405Sandreas.hansson@arm.com void 2492SN/A deschedule(ScEvent *event) 2509235Sandreas.hansson@arm.com { 2519235Sandreas.hansson@arm.com ScEvents *on = event->scheduledOn(); 2529405Sandreas.hansson@arm.com 2532SN/A if (on == &deltas) { 2549235Sandreas.hansson@arm.com event->deschedule(); 2559235Sandreas.hansson@arm.com return; 2569405Sandreas.hansson@arm.com } 2572SN/A 2589235Sandreas.hansson@arm.com // Timed notification/timeout. 2599235Sandreas.hansson@arm.com auto tsit = timeSlots.find(event->when()); 2609405Sandreas.hansson@arm.com panic_if(tsit == timeSlots.end(), 2612SN/A "Descheduling event at time with no events."); 2629235Sandreas.hansson@arm.com TimeSlot *ts = tsit->second; 263 ScEvents &events = ts->events; 264 assert(on == &events); 265 event->deschedule(); 266 267 // If no more events are happening at this time slot, get rid of it. 268 if (events.empty()) { 269 deschedule(ts); 270 timeSlots.erase(tsit); 271 } 272 } 273 274 void 275 completeTimeSlot(TimeSlot *ts) 276 { 277 _changeStamp++; 278 assert(ts == timeSlots.begin()->second); 279 timeSlots.erase(timeSlots.begin()); 280 if (!runToTime && starved()) 281 scheduleStarvationEvent(); 282 } 283 284 // Pending activity ignores gem5 activity, much like how a systemc 285 // simulation wouldn't know about asynchronous external events (socket IO 286 // for instance) that might happen before time advances in a pure 287 // systemc simulation. Also the spec lists what specific types of pending 288 // activity needs to be counted, which obviously doesn't include gem5 289 // events. 290 291 // Return whether there's pending systemc activity at this time. 292 bool 293 pendingCurr() 294 { 295 return !readyListMethods.empty() || !readyListThreads.empty() || 296 !updateList.empty() || !deltas.empty(); 297 } 298 299 // Return whether there are pending timed notifications or timeouts. 300 bool 301 pendingFuture() 302 { 303 return !timeSlots.empty(); 304 } 305 306 // Return how many ticks there are until the first pending event, if any. 307 Tick 308 timeToPending() 309 { 310 if (pendingCurr()) 311 return 0; 312 if (pendingFuture()) 313 return timeSlots.begin()->first - getCurTick(); 314 return MaxTick - getCurTick(); 315 } 316 317 // Run scheduled channel updates. 318 void runUpdate(); 319 320 // Run delta events. 321 void runDelta(); 322 323 void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 324 325 void start(Tick max_tick, bool run_to_time); 326 void oneCycle(); 327 328 void schedulePause(); 329 void scheduleStop(bool finish_delta); 330 331 enum Status 332 { 333 StatusOther = 0, 334 StatusDelta, 335 StatusUpdate, 336 StatusTiming, 337 StatusPaused, 338 StatusStopped 339 }; 340 341 bool elaborationDone() { return _elaborationDone; } 342 void elaborationDone(bool b) { _elaborationDone = b; } 343 344 bool paused() { return status() == StatusPaused; } 345 bool stopped() { return status() == StatusStopped; } 346 bool inDelta() { return status() == StatusDelta; } 347 bool inUpdate() { return status() == StatusUpdate; } 348 bool inTiming() { return status() == StatusTiming; } 349 350 uint64_t changeStamp() { return _changeStamp; } 351 352 void throwToScMain(const ::sc_core::sc_report *r=nullptr); 353 354 Status status() { return _status; } 355 void status(Status s) { _status = s; } 356 357 private: 358 typedef const EventBase::Priority Priority; 359 static Priority DefaultPriority = EventBase::Default_Pri; 360 361 static Priority StopPriority = DefaultPriority - 1; 362 static Priority PausePriority = DefaultPriority + 1; 363 static Priority MaxTickPriority = DefaultPriority + 2; 364 static Priority ReadyPriority = DefaultPriority + 3; 365 static Priority StarvationPriority = ReadyPriority; 366 367 EventQueue *eq; 368 369 // For gem5 style events. 370 void 371 schedule(::Event *event, Tick tick) 372 { 373 if (initDone) 374 eq->schedule(event, tick); 375 else 376 eventsToSchedule[event] = tick; 377 } 378 379 void schedule(::Event *event) { schedule(event, getCurTick()); } 380 381 void 382 deschedule(::Event *event) 383 { 384 if (initDone) 385 eq->deschedule(event); 386 else 387 eventsToSchedule.erase(event); 388 } 389 390 ScEvents deltas; 391 TimeSlots timeSlots; 392 393 Process * 394 getNextReady() 395 { 396 Process *p = readyListMethods.getNext(); 397 return p ? p : readyListThreads.getNext(); 398 } 399 400 void runReady(); 401 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 402 void scheduleReadyEvent(); 403 404 void pause(); 405 void stop(); 406 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 407 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 408 409 Fiber *scMain; 410 const ::sc_core::sc_report *_throwToScMain; 411 412 bool 413 starved() 414 { 415 return (readyListMethods.empty() && readyListThreads.empty() && 416 updateList.empty() && deltas.empty() && 417 (timeSlots.empty() || timeSlots.begin()->first > maxTick) && 418 initList.empty()); 419 } 420 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 421 void scheduleStarvationEvent(); 422 423 bool _elaborationDone; 424 bool _started; 425 bool _stopNow; 426 427 Status _status; 428 429 Tick maxTick; 430 Tick lastReadyTick; 431 void 432 maxTickFunc() 433 { 434 if (lastReadyTick != getCurTick()) 435 _changeStamp++; 436 pause(); 437 } 438 EventWrapper<Scheduler, &Scheduler::maxTickFunc> maxTickEvent; 439 440 uint64_t _numCycles; 441 uint64_t _changeStamp; 442 443 Process *_current; 444 445 bool initDone; 446 bool runToTime; 447 bool runOnce; 448 449 ProcessList initList; 450 451 ProcessList readyListMethods; 452 ProcessList readyListThreads; 453 454 ChannelList updateList; 455 456 std::map<::Event *, Tick> eventsToSchedule; 457}; 458 459extern Scheduler scheduler; 460 461inline void 462Scheduler::TimeSlot::process() 463{ 464 scheduler.status(StatusTiming); 465 466 try { 467 while (!events.empty()) 468 events.front()->run(); 469 } catch (...) { 470 if (events.empty()) 471 scheduler.completeTimeSlot(this); 472 else 473 scheduler.schedule(this); 474 scheduler.throwToScMain(); 475 } 476 477 scheduler.status(StatusOther); 478 scheduler.completeTimeSlot(this); 479} 480 481const ::sc_core::sc_report *reportifyException(); 482 483} // namespace sc_gem5 484 485#endif // __SYSTEMC_CORE_SCHEDULER_H__ 486