scheduler.hh revision 12987
1/* 2 * Copyright 2018 Google, Inc. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: redistributions of source code must retain the above copyright 7 * notice, this list of conditions and the following disclaimer; 8 * redistributions in binary form must reproduce the above copyright 9 * notice, this list of conditions and the following disclaimer in the 10 * documentation and/or other materials provided with the distribution; 11 * neither the name of the copyright holders nor the names of its 12 * contributors may be used to endorse or promote products derived from 13 * this software without specific prior written permission. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 18 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 19 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 20 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 21 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 22 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 23 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 * 27 * Authors: Gabe Black 28 */ 29 30#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 31#define __SYSTEMC_CORE_SCHEDULER_HH__ 32 33#include <vector> 34 35#include "base/logging.hh" 36#include "sim/eventq.hh" 37#include "systemc/core/channel.hh" 38#include "systemc/core/list.hh" 39#include "systemc/core/process.hh" 40 41class Fiber; 42 43namespace sc_gem5 44{ 45 46typedef NodeList<Process> ProcessList; 47typedef NodeList<Channel> ChannelList; 48 49/* 50 * The scheduler supports three different mechanisms, the initialization phase, 51 * delta cycles, and timed notifications. 52 * 53 * INITIALIZATION PHASE 54 * 55 * The initialization phase has three parts: 56 * 1. Run requested channel updates. 57 * 2. Make processes which need to initialize runnable (methods and threads 58 * which didn't have dont_initialize called on them). 59 * 3. Process delta notifications. 60 * 61 * First, the Kernel SimObject calls the update() method during its startup() 62 * callback which handles the requested channel updates. The Kernel also 63 * schedules an event to be run at time 0 with a slightly elevated priority 64 * so that it happens before any "normal" event. 65 * 66 * When that t0 event happens, it calls the schedulers prepareForInit method 67 * which performs step 2 above. That indirectly causes the scheduler's 68 * readyEvent to be scheduled with slightly lowered priority, ensuring it 69 * happens after any "normal" event. 70 * 71 * Because delta notifications are scheduled at the standard priority, all 72 * of those events will happen next, performing step 3 above. Once they finish, 73 * if the readyEvent was scheduled above, there shouldn't be any higher 74 * priority events in front of it. When it runs, it will start the first 75 * evaluate phase of the first delta cycle. 76 * 77 * DELTA CYCLE 78 * 79 * A delta cycle has three phases within it. 80 * 1. The evaluate phase where runnable processes are allowed to run. 81 * 2. The update phase where requested channel updates hapen. 82 * 3. The delta notification phase where delta notifications happen. 83 * 84 * The readyEvent runs the first two steps of the delta cycle. It first goes 85 * through the list of runnable processes and executes them until the set is 86 * empty, and then immediately runs the update phase. Since these are all part 87 * of the same event, there's no chance for other events to intervene and 88 * break the required order above. 89 * 90 * During the update phase above, the spec forbids any action which would make 91 * a process runnable. That means that once the update phase finishes, the set 92 * of runnable processes will be empty. There may, however, have been some 93 * delta notifications/timeouts which will have been scheduled during either 94 * the evaluate or update phase above. Because those are scheduled at the 95 * normal priority, they will now happen together until there aren't any 96 * delta events left. 97 * 98 * If any processes became runnable during the delta notification phase, the 99 * readyEvent will have been scheduled and will have been waiting patiently 100 * behind the delta notification events. That will now run, effectively 101 * starting the next delta cycle. 102 * 103 * TIMED NOTIFICATION PHASE 104 * 105 * If no processes became runnable, the event queue will continue to process 106 * events until it comes across a timed notification, aka a notification 107 * scheduled to happen in the future. Like delta notification events, those 108 * will all happen together since the readyEvent priority is lower, 109 * potentially marking new processes as ready. Once these events finish, the 110 * readyEvent may run, starting the next delta cycle. 111 * 112 * PAUSE/STOP 113 * 114 * To inject a pause from sc_pause which should happen after the current delta 115 * cycle's delta notification phase, an event is scheduled with a lower than 116 * normal priority, but higher than the readyEvent. That ensures that any 117 * delta notifications which are scheduled with normal priority will happen 118 * first, since those are part of the current delta cycle. Then the pause 119 * event will happen before the next readyEvent which would start the next 120 * delta cycle. All of these events are scheduled for the current time, and so 121 * would happen before any timed notifications went off. 122 * 123 * To inject a stop from sc_stop, the delta cycles should stop before even the 124 * delta notifications have happened, but after the evaluate and update phases. 125 * For that, a stop event with slightly higher than normal priority will be 126 * scheduled so that it happens before any of the delta notification events 127 * which are at normal priority. 128 * 129 * MAX RUN TIME 130 * 131 * When sc_start is called, it's possible to pass in a maximum time the 132 * simulation should run to, at which point sc_pause is implicitly called. 133 * That's implemented by scheduling an event at the max time with a priority 134 * which is lower than all the others so that it happens only if time would 135 * advance. When that event triggers, it calls the same function as the pause 136 * event. 137 */ 138 139class Scheduler 140{ 141 public: 142 Scheduler(); 143 144 const std::string name() const { return "systemc_scheduler"; } 145 146 uint64_t numCycles() { return _numCycles; } 147 Process *current() { return _current; } 148 149 // Prepare for initialization. 150 void prepareForInit(); 151 152 // Register a process with the scheduler. 153 void reg(Process *p); 154 155 // Tell the scheduler not to initialize a process. 156 void dontInitialize(Process *p); 157 158 // Run the next process, if there is one. 159 void yield(); 160 161 // Put a process on the ready list. 162 void ready(Process *p); 163 164 // Schedule an update for a given channel. 165 void requestUpdate(Channel *c); 166 167 // Run the given process immediately, preempting whatever may be running. 168 void 169 runNow(Process *p) 170 { 171 // If a process is running, schedule it/us to run again. 172 if (_current) 173 readyList.pushFirst(_current); 174 // Schedule p to run first. 175 readyList.pushFirst(p); 176 yield(); 177 } 178 179 // Set an event queue for scheduling events. 180 void setEventQueue(EventQueue *_eq) { eq = _eq; } 181 182 // Get the current time according to gem5. 183 Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 184 185 // For scheduling delayed/timed notifications/timeouts. 186 void 187 schedule(::Event *event, Tick tick) 188 { 189 pendingTicks[tick]++; 190 191 if (initReady) 192 eq->schedule(event, tick); 193 else 194 eventsToSchedule[event] = tick; 195 } 196 197 // For descheduling delayed/timed notifications/timeouts. 198 void 199 deschedule(::Event *event) 200 { 201 auto it = pendingTicks.find(event->when()); 202 if (--it->second == 0) 203 pendingTicks.erase(it); 204 205 if (initReady) 206 eq->deschedule(event); 207 else 208 eventsToSchedule.erase(event); 209 } 210 211 // Tell the scheduler than an event fired for bookkeeping purposes. 212 void 213 eventHappened() 214 { 215 auto it = pendingTicks.begin(); 216 if (--it->second == 0) 217 pendingTicks.erase(it); 218 219 if (starved() && !runToTime) 220 scheduleStarvationEvent(); 221 } 222 223 // Pending activity ignores gem5 activity, much like how a systemc 224 // simulation wouldn't know about asynchronous external events (socket IO 225 // for instance) that might happen before time advances in a pure 226 // systemc simulation. Also the spec lists what specific types of pending 227 // activity needs to be counted, which obviously doesn't include gem5 228 // events. 229 230 // Return whether there's pending systemc activity at this time. 231 bool 232 pendingCurr() 233 { 234 if (!readyList.empty() || !updateList.empty()) 235 return true; 236 return pendingTicks.size() && 237 pendingTicks.begin()->first == getCurTick(); 238 } 239 240 // Return whether there are pending timed notifications or timeouts. 241 bool 242 pendingFuture() 243 { 244 switch (pendingTicks.size()) { 245 case 0: return false; 246 case 1: return pendingTicks.begin()->first > getCurTick(); 247 default: return true; 248 } 249 } 250 251 // Return how many ticks there are until the first pending event, if any. 252 Tick 253 timeToPending() 254 { 255 if (!readyList.empty() || !updateList.empty()) 256 return 0; 257 else if (pendingTicks.size()) 258 return pendingTicks.begin()->first - getCurTick(); 259 else 260 return MaxTick - getCurTick(); 261 } 262 263 // Run scheduled channel updates. 264 void update(); 265 266 void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 267 268 void start(Tick max_tick, bool run_to_time); 269 270 void schedulePause(); 271 void scheduleStop(bool finish_delta); 272 273 bool paused() { return _paused; } 274 bool stopped() { return _stopped; } 275 276 private: 277 typedef const EventBase::Priority Priority; 278 static Priority DefaultPriority = EventBase::Default_Pri; 279 280 static Priority StopPriority = DefaultPriority - 1; 281 static Priority PausePriority = DefaultPriority + 1; 282 static Priority ReadyPriority = DefaultPriority + 2; 283 static Priority StarvationPriority = ReadyPriority; 284 static Priority MaxTickPriority = DefaultPriority + 3; 285 286 EventQueue *eq; 287 std::map<Tick, int> pendingTicks; 288 289 void runReady(); 290 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 291 void scheduleReadyEvent(); 292 293 void pause(); 294 void stop(); 295 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 296 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 297 Fiber *scMain; 298 299 bool 300 starved() 301 { 302 return (readyList.empty() && updateList.empty() && 303 (pendingTicks.empty() || 304 pendingTicks.begin()->first > maxTick) && 305 initList.empty()); 306 } 307 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 308 void scheduleStarvationEvent(); 309 310 bool _started; 311 bool _paused; 312 bool _stopped; 313 314 Tick maxTick; 315 EventWrapper<Scheduler, &Scheduler::pause> maxTickEvent; 316 317 uint64_t _numCycles; 318 319 Process *_current; 320 321 bool initReady; 322 bool runToTime; 323 324 ProcessList initList; 325 ProcessList toFinalize; 326 ProcessList readyList; 327 328 ChannelList updateList; 329 330 std::map<::Event *, Tick> eventsToSchedule; 331}; 332 333extern Scheduler scheduler; 334 335} // namespace sc_gem5 336 337#endif // __SYSTEMC_CORE_SCHEDULER_H__ 338