scheduler.hh revision 12987
112953Sgabeblack@google.com/* 212953Sgabeblack@google.com * Copyright 2018 Google, Inc. 312953Sgabeblack@google.com * 412953Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 512953Sgabeblack@google.com * modification, are permitted provided that the following conditions are 612953Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 712953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 812953Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 912953Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1012953Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1112953Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1212953Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1312953Sgabeblack@google.com * this software without specific prior written permission. 1412953Sgabeblack@google.com * 1512953Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1612953Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1712953Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1812953Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1912953Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2012953Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2112953Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2212953Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2312953Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2412953Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2512953Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2612953Sgabeblack@google.com * 2712953Sgabeblack@google.com * Authors: Gabe Black 2812953Sgabeblack@google.com */ 2912953Sgabeblack@google.com 3012953Sgabeblack@google.com#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 3112953Sgabeblack@google.com#define __SYSTEMC_CORE_SCHEDULER_HH__ 3212953Sgabeblack@google.com 3312957Sgabeblack@google.com#include <vector> 3412957Sgabeblack@google.com 3512961Sgabeblack@google.com#include "base/logging.hh" 3612954Sgabeblack@google.com#include "sim/eventq.hh" 3712954Sgabeblack@google.com#include "systemc/core/channel.hh" 3812953Sgabeblack@google.com#include "systemc/core/list.hh" 3912953Sgabeblack@google.com#include "systemc/core/process.hh" 4012953Sgabeblack@google.com 4112961Sgabeblack@google.comclass Fiber; 4212961Sgabeblack@google.com 4312953Sgabeblack@google.comnamespace sc_gem5 4412953Sgabeblack@google.com{ 4512953Sgabeblack@google.com 4612953Sgabeblack@google.comtypedef NodeList<Process> ProcessList; 4712954Sgabeblack@google.comtypedef NodeList<Channel> ChannelList; 4812954Sgabeblack@google.com 4912954Sgabeblack@google.com/* 5012954Sgabeblack@google.com * The scheduler supports three different mechanisms, the initialization phase, 5112954Sgabeblack@google.com * delta cycles, and timed notifications. 5212954Sgabeblack@google.com * 5312954Sgabeblack@google.com * INITIALIZATION PHASE 5412954Sgabeblack@google.com * 5512954Sgabeblack@google.com * The initialization phase has three parts: 5612954Sgabeblack@google.com * 1. Run requested channel updates. 5712954Sgabeblack@google.com * 2. Make processes which need to initialize runnable (methods and threads 5812954Sgabeblack@google.com * which didn't have dont_initialize called on them). 5912954Sgabeblack@google.com * 3. Process delta notifications. 6012954Sgabeblack@google.com * 6112954Sgabeblack@google.com * First, the Kernel SimObject calls the update() method during its startup() 6212954Sgabeblack@google.com * callback which handles the requested channel updates. The Kernel also 6312954Sgabeblack@google.com * schedules an event to be run at time 0 with a slightly elevated priority 6412954Sgabeblack@google.com * so that it happens before any "normal" event. 6512954Sgabeblack@google.com * 6612957Sgabeblack@google.com * When that t0 event happens, it calls the schedulers prepareForInit method 6712954Sgabeblack@google.com * which performs step 2 above. That indirectly causes the scheduler's 6812954Sgabeblack@google.com * readyEvent to be scheduled with slightly lowered priority, ensuring it 6912954Sgabeblack@google.com * happens after any "normal" event. 7012954Sgabeblack@google.com * 7112954Sgabeblack@google.com * Because delta notifications are scheduled at the standard priority, all 7212954Sgabeblack@google.com * of those events will happen next, performing step 3 above. Once they finish, 7312954Sgabeblack@google.com * if the readyEvent was scheduled above, there shouldn't be any higher 7412954Sgabeblack@google.com * priority events in front of it. When it runs, it will start the first 7512954Sgabeblack@google.com * evaluate phase of the first delta cycle. 7612954Sgabeblack@google.com * 7712954Sgabeblack@google.com * DELTA CYCLE 7812954Sgabeblack@google.com * 7912954Sgabeblack@google.com * A delta cycle has three phases within it. 8012954Sgabeblack@google.com * 1. The evaluate phase where runnable processes are allowed to run. 8112954Sgabeblack@google.com * 2. The update phase where requested channel updates hapen. 8212954Sgabeblack@google.com * 3. The delta notification phase where delta notifications happen. 8312954Sgabeblack@google.com * 8412954Sgabeblack@google.com * The readyEvent runs the first two steps of the delta cycle. It first goes 8512954Sgabeblack@google.com * through the list of runnable processes and executes them until the set is 8612954Sgabeblack@google.com * empty, and then immediately runs the update phase. Since these are all part 8712954Sgabeblack@google.com * of the same event, there's no chance for other events to intervene and 8812954Sgabeblack@google.com * break the required order above. 8912954Sgabeblack@google.com * 9012954Sgabeblack@google.com * During the update phase above, the spec forbids any action which would make 9112954Sgabeblack@google.com * a process runnable. That means that once the update phase finishes, the set 9212954Sgabeblack@google.com * of runnable processes will be empty. There may, however, have been some 9312954Sgabeblack@google.com * delta notifications/timeouts which will have been scheduled during either 9412954Sgabeblack@google.com * the evaluate or update phase above. Because those are scheduled at the 9512954Sgabeblack@google.com * normal priority, they will now happen together until there aren't any 9612954Sgabeblack@google.com * delta events left. 9712954Sgabeblack@google.com * 9812954Sgabeblack@google.com * If any processes became runnable during the delta notification phase, the 9912954Sgabeblack@google.com * readyEvent will have been scheduled and will have been waiting patiently 10012954Sgabeblack@google.com * behind the delta notification events. That will now run, effectively 10112954Sgabeblack@google.com * starting the next delta cycle. 10212954Sgabeblack@google.com * 10312954Sgabeblack@google.com * TIMED NOTIFICATION PHASE 10412954Sgabeblack@google.com * 10512954Sgabeblack@google.com * If no processes became runnable, the event queue will continue to process 10612954Sgabeblack@google.com * events until it comes across a timed notification, aka a notification 10712954Sgabeblack@google.com * scheduled to happen in the future. Like delta notification events, those 10812954Sgabeblack@google.com * will all happen together since the readyEvent priority is lower, 10912954Sgabeblack@google.com * potentially marking new processes as ready. Once these events finish, the 11012954Sgabeblack@google.com * readyEvent may run, starting the next delta cycle. 11112961Sgabeblack@google.com * 11212961Sgabeblack@google.com * PAUSE/STOP 11312961Sgabeblack@google.com * 11412961Sgabeblack@google.com * To inject a pause from sc_pause which should happen after the current delta 11512961Sgabeblack@google.com * cycle's delta notification phase, an event is scheduled with a lower than 11612961Sgabeblack@google.com * normal priority, but higher than the readyEvent. That ensures that any 11712961Sgabeblack@google.com * delta notifications which are scheduled with normal priority will happen 11812961Sgabeblack@google.com * first, since those are part of the current delta cycle. Then the pause 11912961Sgabeblack@google.com * event will happen before the next readyEvent which would start the next 12012961Sgabeblack@google.com * delta cycle. All of these events are scheduled for the current time, and so 12112961Sgabeblack@google.com * would happen before any timed notifications went off. 12212961Sgabeblack@google.com * 12312961Sgabeblack@google.com * To inject a stop from sc_stop, the delta cycles should stop before even the 12412961Sgabeblack@google.com * delta notifications have happened, but after the evaluate and update phases. 12512961Sgabeblack@google.com * For that, a stop event with slightly higher than normal priority will be 12612961Sgabeblack@google.com * scheduled so that it happens before any of the delta notification events 12712961Sgabeblack@google.com * which are at normal priority. 12812961Sgabeblack@google.com * 12912961Sgabeblack@google.com * MAX RUN TIME 13012961Sgabeblack@google.com * 13112961Sgabeblack@google.com * When sc_start is called, it's possible to pass in a maximum time the 13212961Sgabeblack@google.com * simulation should run to, at which point sc_pause is implicitly called. 13312961Sgabeblack@google.com * That's implemented by scheduling an event at the max time with a priority 13412961Sgabeblack@google.com * which is lower than all the others so that it happens only if time would 13512961Sgabeblack@google.com * advance. When that event triggers, it calls the same function as the pause 13612961Sgabeblack@google.com * event. 13712954Sgabeblack@google.com */ 13812953Sgabeblack@google.com 13912953Sgabeblack@google.comclass Scheduler 14012953Sgabeblack@google.com{ 14112953Sgabeblack@google.com public: 14212953Sgabeblack@google.com Scheduler(); 14312953Sgabeblack@google.com 14412954Sgabeblack@google.com const std::string name() const { return "systemc_scheduler"; } 14512954Sgabeblack@google.com 14612953Sgabeblack@google.com uint64_t numCycles() { return _numCycles; } 14712953Sgabeblack@google.com Process *current() { return _current; } 14812953Sgabeblack@google.com 14912957Sgabeblack@google.com // Prepare for initialization. 15012957Sgabeblack@google.com void prepareForInit(); 15112953Sgabeblack@google.com 15212957Sgabeblack@google.com // Register a process with the scheduler. 15312957Sgabeblack@google.com void reg(Process *p); 15412957Sgabeblack@google.com 15512957Sgabeblack@google.com // Tell the scheduler not to initialize a process. 15612957Sgabeblack@google.com void dontInitialize(Process *p); 15712953Sgabeblack@google.com 15812953Sgabeblack@google.com // Run the next process, if there is one. 15912953Sgabeblack@google.com void yield(); 16012953Sgabeblack@google.com 16112953Sgabeblack@google.com // Put a process on the ready list. 16212954Sgabeblack@google.com void ready(Process *p); 16312954Sgabeblack@google.com 16412954Sgabeblack@google.com // Schedule an update for a given channel. 16512954Sgabeblack@google.com void requestUpdate(Channel *c); 16612953Sgabeblack@google.com 16712953Sgabeblack@google.com // Run the given process immediately, preempting whatever may be running. 16812953Sgabeblack@google.com void 16912953Sgabeblack@google.com runNow(Process *p) 17012953Sgabeblack@google.com { 17112953Sgabeblack@google.com // If a process is running, schedule it/us to run again. 17212953Sgabeblack@google.com if (_current) 17312953Sgabeblack@google.com readyList.pushFirst(_current); 17412953Sgabeblack@google.com // Schedule p to run first. 17512953Sgabeblack@google.com readyList.pushFirst(p); 17612953Sgabeblack@google.com yield(); 17712953Sgabeblack@google.com } 17812953Sgabeblack@google.com 17912954Sgabeblack@google.com // Set an event queue for scheduling events. 18012954Sgabeblack@google.com void setEventQueue(EventQueue *_eq) { eq = _eq; } 18112954Sgabeblack@google.com 18212962Sgabeblack@google.com // Get the current time according to gem5. 18312962Sgabeblack@google.com Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 18412962Sgabeblack@google.com 18512962Sgabeblack@google.com // For scheduling delayed/timed notifications/timeouts. 18612962Sgabeblack@google.com void 18712962Sgabeblack@google.com schedule(::Event *event, Tick tick) 18812962Sgabeblack@google.com { 18912962Sgabeblack@google.com pendingTicks[tick]++; 19012985Sgabeblack@google.com 19112985Sgabeblack@google.com if (initReady) 19212985Sgabeblack@google.com eq->schedule(event, tick); 19312985Sgabeblack@google.com else 19412985Sgabeblack@google.com eventsToSchedule[event] = tick; 19512962Sgabeblack@google.com } 19612962Sgabeblack@google.com 19712962Sgabeblack@google.com // For descheduling delayed/timed notifications/timeouts. 19812962Sgabeblack@google.com void 19912962Sgabeblack@google.com deschedule(::Event *event) 20012962Sgabeblack@google.com { 20112962Sgabeblack@google.com auto it = pendingTicks.find(event->when()); 20212962Sgabeblack@google.com if (--it->second == 0) 20312962Sgabeblack@google.com pendingTicks.erase(it); 20412985Sgabeblack@google.com 20512985Sgabeblack@google.com if (initReady) 20612985Sgabeblack@google.com eq->deschedule(event); 20712985Sgabeblack@google.com else 20812985Sgabeblack@google.com eventsToSchedule.erase(event); 20912962Sgabeblack@google.com } 21012962Sgabeblack@google.com 21112962Sgabeblack@google.com // Tell the scheduler than an event fired for bookkeeping purposes. 21212962Sgabeblack@google.com void 21312962Sgabeblack@google.com eventHappened() 21412962Sgabeblack@google.com { 21512962Sgabeblack@google.com auto it = pendingTicks.begin(); 21612962Sgabeblack@google.com if (--it->second == 0) 21712962Sgabeblack@google.com pendingTicks.erase(it); 21812987Sgabeblack@google.com 21912987Sgabeblack@google.com if (starved() && !runToTime) 22012987Sgabeblack@google.com scheduleStarvationEvent(); 22112962Sgabeblack@google.com } 22212962Sgabeblack@google.com 22312962Sgabeblack@google.com // Pending activity ignores gem5 activity, much like how a systemc 22412962Sgabeblack@google.com // simulation wouldn't know about asynchronous external events (socket IO 22512962Sgabeblack@google.com // for instance) that might happen before time advances in a pure 22612962Sgabeblack@google.com // systemc simulation. Also the spec lists what specific types of pending 22712962Sgabeblack@google.com // activity needs to be counted, which obviously doesn't include gem5 22812962Sgabeblack@google.com // events. 22912962Sgabeblack@google.com 23012962Sgabeblack@google.com // Return whether there's pending systemc activity at this time. 23112962Sgabeblack@google.com bool 23212962Sgabeblack@google.com pendingCurr() 23312962Sgabeblack@google.com { 23412962Sgabeblack@google.com if (!readyList.empty() || !updateList.empty()) 23512962Sgabeblack@google.com return true; 23612962Sgabeblack@google.com return pendingTicks.size() && 23712962Sgabeblack@google.com pendingTicks.begin()->first == getCurTick(); 23812962Sgabeblack@google.com } 23912962Sgabeblack@google.com 24012962Sgabeblack@google.com // Return whether there are pending timed notifications or timeouts. 24112962Sgabeblack@google.com bool 24212962Sgabeblack@google.com pendingFuture() 24312962Sgabeblack@google.com { 24412962Sgabeblack@google.com switch (pendingTicks.size()) { 24512962Sgabeblack@google.com case 0: return false; 24612962Sgabeblack@google.com case 1: return pendingTicks.begin()->first > getCurTick(); 24712962Sgabeblack@google.com default: return true; 24812962Sgabeblack@google.com } 24912962Sgabeblack@google.com } 25012962Sgabeblack@google.com 25112962Sgabeblack@google.com // Return how many ticks there are until the first pending event, if any. 25212962Sgabeblack@google.com Tick 25312962Sgabeblack@google.com timeToPending() 25412962Sgabeblack@google.com { 25512962Sgabeblack@google.com if (!readyList.empty() || !updateList.empty()) 25612962Sgabeblack@google.com return 0; 25712962Sgabeblack@google.com else if (pendingTicks.size()) 25812962Sgabeblack@google.com return pendingTicks.begin()->first - getCurTick(); 25912962Sgabeblack@google.com else 26012962Sgabeblack@google.com return MaxTick - getCurTick(); 26112962Sgabeblack@google.com } 26212954Sgabeblack@google.com 26312954Sgabeblack@google.com // Run scheduled channel updates. 26412954Sgabeblack@google.com void update(); 26512954Sgabeblack@google.com 26612961Sgabeblack@google.com void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 26712961Sgabeblack@google.com 26812961Sgabeblack@google.com void start(Tick max_tick, bool run_to_time); 26912961Sgabeblack@google.com 27012961Sgabeblack@google.com void schedulePause(); 27112961Sgabeblack@google.com void scheduleStop(bool finish_delta); 27212961Sgabeblack@google.com 27312961Sgabeblack@google.com bool paused() { return _paused; } 27412961Sgabeblack@google.com bool stopped() { return _stopped; } 27512961Sgabeblack@google.com 27612953Sgabeblack@google.com private: 27712961Sgabeblack@google.com typedef const EventBase::Priority Priority; 27812961Sgabeblack@google.com static Priority DefaultPriority = EventBase::Default_Pri; 27912961Sgabeblack@google.com 28012961Sgabeblack@google.com static Priority StopPriority = DefaultPriority - 1; 28112961Sgabeblack@google.com static Priority PausePriority = DefaultPriority + 1; 28212961Sgabeblack@google.com static Priority ReadyPriority = DefaultPriority + 2; 28312987Sgabeblack@google.com static Priority StarvationPriority = ReadyPriority; 28412961Sgabeblack@google.com static Priority MaxTickPriority = DefaultPriority + 3; 28512961Sgabeblack@google.com 28612954Sgabeblack@google.com EventQueue *eq; 28712962Sgabeblack@google.com std::map<Tick, int> pendingTicks; 28812954Sgabeblack@google.com 28912954Sgabeblack@google.com void runReady(); 29012954Sgabeblack@google.com EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 29112954Sgabeblack@google.com void scheduleReadyEvent(); 29212954Sgabeblack@google.com 29312961Sgabeblack@google.com void pause(); 29412961Sgabeblack@google.com void stop(); 29512961Sgabeblack@google.com EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 29612961Sgabeblack@google.com EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 29712961Sgabeblack@google.com Fiber *scMain; 29812961Sgabeblack@google.com 29912987Sgabeblack@google.com bool 30012987Sgabeblack@google.com starved() 30112987Sgabeblack@google.com { 30212987Sgabeblack@google.com return (readyList.empty() && updateList.empty() && 30312987Sgabeblack@google.com (pendingTicks.empty() || 30412987Sgabeblack@google.com pendingTicks.begin()->first > maxTick) && 30512987Sgabeblack@google.com initList.empty()); 30612987Sgabeblack@google.com } 30712987Sgabeblack@google.com EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 30812987Sgabeblack@google.com void scheduleStarvationEvent(); 30912987Sgabeblack@google.com 31012961Sgabeblack@google.com bool _started; 31112961Sgabeblack@google.com bool _paused; 31212961Sgabeblack@google.com bool _stopped; 31312961Sgabeblack@google.com 31412961Sgabeblack@google.com Tick maxTick; 31512961Sgabeblack@google.com EventWrapper<Scheduler, &Scheduler::pause> maxTickEvent; 31612961Sgabeblack@google.com 31712953Sgabeblack@google.com uint64_t _numCycles; 31812953Sgabeblack@google.com 31912953Sgabeblack@google.com Process *_current; 32012953Sgabeblack@google.com 32112957Sgabeblack@google.com bool initReady; 32212987Sgabeblack@google.com bool runToTime; 32312957Sgabeblack@google.com 32412953Sgabeblack@google.com ProcessList initList; 32512957Sgabeblack@google.com ProcessList toFinalize; 32612953Sgabeblack@google.com ProcessList readyList; 32712953Sgabeblack@google.com 32812954Sgabeblack@google.com ChannelList updateList; 32912985Sgabeblack@google.com 33012985Sgabeblack@google.com std::map<::Event *, Tick> eventsToSchedule; 33112953Sgabeblack@google.com}; 33212953Sgabeblack@google.com 33312953Sgabeblack@google.comextern Scheduler scheduler; 33412953Sgabeblack@google.com 33512953Sgabeblack@google.com} // namespace sc_gem5 33612953Sgabeblack@google.com 33712953Sgabeblack@google.com#endif // __SYSTEMC_CORE_SCHEDULER_H__ 338