scheduler.hh revision 13058:da3ffd935b29
15222Sksewell@umich.edu/* 25254Sksewell@umich.edu * Copyright 2018 Google, Inc. 35254Sksewell@umich.edu * 45254Sksewell@umich.edu * Redistribution and use in source and binary forms, with or without 55222Sksewell@umich.edu * modification, are permitted provided that the following conditions are 65254Sksewell@umich.edu * met: redistributions of source code must retain the above copyright 75254Sksewell@umich.edu * notice, this list of conditions and the following disclaimer; 85254Sksewell@umich.edu * redistributions in binary form must reproduce the above copyright 95254Sksewell@umich.edu * notice, this list of conditions and the following disclaimer in the 105254Sksewell@umich.edu * documentation and/or other materials provided with the distribution; 115254Sksewell@umich.edu * neither the name of the copyright holders nor the names of its 125254Sksewell@umich.edu * contributors may be used to endorse or promote products derived from 135254Sksewell@umich.edu * this software without specific prior written permission. 145254Sksewell@umich.edu * 155254Sksewell@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 165222Sksewell@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 175254Sksewell@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 185254Sksewell@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 195254Sksewell@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 205254Sksewell@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 215254Sksewell@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 225254Sksewell@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 235254Sksewell@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 245254Sksewell@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 255254Sksewell@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 265254Sksewell@umich.edu * 275254Sksewell@umich.edu * Authors: Gabe Black 285222Sksewell@umich.edu */ 295254Sksewell@umich.edu 305254Sksewell@umich.edu#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 315254Sksewell@umich.edu#define __SYSTEMC_CORE_SCHEDULER_HH__ 325222Sksewell@umich.edu 335222Sksewell@umich.edu#include <vector> 346379Sgblack@eecs.umich.edu 356379Sgblack@eecs.umich.edu#include "base/logging.hh" 365222Sksewell@umich.edu#include "sim/eventq.hh" 376379Sgblack@eecs.umich.edu#include "systemc/core/channel.hh" 385222Sksewell@umich.edu#include "systemc/core/list.hh" 398745Sgblack@eecs.umich.edu#include "systemc/core/process.hh" 405222Sksewell@umich.edu 415222Sksewell@umich.educlass Fiber; 425222Sksewell@umich.edu 436378Sgblack@eecs.umich.edunamespace sc_gem5 446378Sgblack@eecs.umich.edu{ 456378Sgblack@eecs.umich.edu 466383Sgblack@eecs.umich.edutypedef NodeList<Process> ProcessList; 476379Sgblack@eecs.umich.edutypedef NodeList<Channel> ChannelList; 485222Sksewell@umich.edu 495222Sksewell@umich.edu/* 506378Sgblack@eecs.umich.edu * The scheduler supports three different mechanisms, the initialization phase, 516379Sgblack@eecs.umich.edu * delta cycles, and timed notifications. 526383Sgblack@eecs.umich.edu * 536379Sgblack@eecs.umich.edu * INITIALIZATION PHASE 546383Sgblack@eecs.umich.edu * 555222Sksewell@umich.edu * The initialization phase has three parts: 565222Sksewell@umich.edu * 1. Run requested channel updates. 576378Sgblack@eecs.umich.edu * 2. Make processes which need to initialize runnable (methods and threads 586378Sgblack@eecs.umich.edu * which didn't have dont_initialize called on them). 595222Sksewell@umich.edu * 3. Process delta notifications. 605222Sksewell@umich.edu * 615222Sksewell@umich.edu * First, the Kernel SimObject calls the update() method during its startup() 625222Sksewell@umich.edu * callback which handles the requested channel updates. The Kernel also 635222Sksewell@umich.edu * schedules an event to be run at time 0 with a slightly elevated priority 646378Sgblack@eecs.umich.edu * so that it happens before any "normal" event. 655222Sksewell@umich.edu * 666378Sgblack@eecs.umich.edu * When that t0 event happens, it calls the schedulers prepareForInit method 675222Sksewell@umich.edu * which performs step 2 above. That indirectly causes the scheduler's 685222Sksewell@umich.edu * readyEvent to be scheduled with slightly lowered priority, ensuring it 696378Sgblack@eecs.umich.edu * happens after any "normal" event. 706378Sgblack@eecs.umich.edu * 715222Sksewell@umich.edu * Because delta notifications are scheduled at the standard priority, all 726378Sgblack@eecs.umich.edu * of those events will happen next, performing step 3 above. Once they finish, 735222Sksewell@umich.edu * if the readyEvent was scheduled above, there shouldn't be any higher 745222Sksewell@umich.edu * priority events in front of it. When it runs, it will start the first 756378Sgblack@eecs.umich.edu * evaluate phase of the first delta cycle. 766378Sgblack@eecs.umich.edu * 775222Sksewell@umich.edu * DELTA CYCLE 785222Sksewell@umich.edu * 795222Sksewell@umich.edu * A delta cycle has three phases within it. 805222Sksewell@umich.edu * 1. The evaluate phase where runnable processes are allowed to run. 815222Sksewell@umich.edu * 2. The update phase where requested channel updates hapen. 826378Sgblack@eecs.umich.edu * 3. The delta notification phase where delta notifications happen. 835222Sksewell@umich.edu * 846378Sgblack@eecs.umich.edu * The readyEvent runs the first two steps of the delta cycle. It first goes 855222Sksewell@umich.edu * through the list of runnable processes and executes them until the set is 865222Sksewell@umich.edu * empty, and then immediately runs the update phase. Since these are all part 876378Sgblack@eecs.umich.edu * of the same event, there's no chance for other events to intervene and 886378Sgblack@eecs.umich.edu * break the required order above. 895222Sksewell@umich.edu * 906378Sgblack@eecs.umich.edu * During the update phase above, the spec forbids any action which would make 915222Sksewell@umich.edu * a process runnable. That means that once the update phase finishes, the set 925222Sksewell@umich.edu * of runnable processes will be empty. There may, however, have been some 936378Sgblack@eecs.umich.edu * delta notifications/timeouts which will have been scheduled during either 946378Sgblack@eecs.umich.edu * the evaluate or update phase above. Because those are scheduled at the 955222Sksewell@umich.edu * normal priority, they will now happen together until there aren't any 965222Sksewell@umich.edu * delta events left. 975222Sksewell@umich.edu * 986378Sgblack@eecs.umich.edu * If any processes became runnable during the delta notification phase, the 995222Sksewell@umich.edu * readyEvent will have been scheduled and will have been waiting patiently 1005222Sksewell@umich.edu * behind the delta notification events. That will now run, effectively 1016378Sgblack@eecs.umich.edu * starting the next delta cycle. 1026378Sgblack@eecs.umich.edu * 1035222Sksewell@umich.edu * TIMED NOTIFICATION PHASE 1046378Sgblack@eecs.umich.edu * 1055222Sksewell@umich.edu * If no processes became runnable, the event queue will continue to process 1065222Sksewell@umich.edu * events until it comes across a timed notification, aka a notification 1075222Sksewell@umich.edu * scheduled to happen in the future. Like delta notification events, those 10811566Smitch.hayenga@arm.com * will all happen together since the readyEvent priority is lower, 10911566Smitch.hayenga@arm.com * potentially marking new processes as ready. Once these events finish, the 1105222Sksewell@umich.edu * readyEvent may run, starting the next delta cycle. 11111566Smitch.hayenga@arm.com * 11211566Smitch.hayenga@arm.com * PAUSE/STOP 1135222Sksewell@umich.edu * 1145222Sksewell@umich.edu * To inject a pause from sc_pause which should happen after the current delta 1156383Sgblack@eecs.umich.edu * cycle's delta notification phase, an event is scheduled with a lower than 1166378Sgblack@eecs.umich.edu * normal priority, but higher than the readyEvent. That ensures that any 1176378Sgblack@eecs.umich.edu * delta notifications which are scheduled with normal priority will happen 1186379Sgblack@eecs.umich.edu * first, since those are part of the current delta cycle. Then the pause 1195222Sksewell@umich.edu * event will happen before the next readyEvent which would start the next 1205222Sksewell@umich.edu * delta cycle. All of these events are scheduled for the current time, and so 1215222Sksewell@umich.edu * would happen before any timed notifications went off. 1226383Sgblack@eecs.umich.edu * 12311566Smitch.hayenga@arm.com * To inject a stop from sc_stop, the delta cycles should stop before even the 12411566Smitch.hayenga@arm.com * delta notifications have happened, but after the evaluate and update phases. 12511566Smitch.hayenga@arm.com * For that, a stop event with slightly higher than normal priority will be 1265222Sksewell@umich.edu * scheduled so that it happens before any of the delta notification events 1275222Sksewell@umich.edu * which are at normal priority. 12811566Smitch.hayenga@arm.com * 12911566Smitch.hayenga@arm.com * MAX RUN TIME 13011566Smitch.hayenga@arm.com * 13111566Smitch.hayenga@arm.com * When sc_start is called, it's possible to pass in a maximum time the 13211566Smitch.hayenga@arm.com * simulation should run to, at which point sc_pause is implicitly called. The 13311566Smitch.hayenga@arm.com * simulation is supposed to run up to the latest timed notification phase 13411566Smitch.hayenga@arm.com * which is less than or equal to the maximum time. In other words it should 13511566Smitch.hayenga@arm.com * run timed notifications at the maximum time, but not the subsequent evaluate 13611566Smitch.hayenga@arm.com * phase. That's implemented by scheduling an event at the max time with a 13711566Smitch.hayenga@arm.com * priority which is lower than all the others except the ready event. Timed 13811566Smitch.hayenga@arm.com * notifications will happen before it fires, but it will override any ready 13911566Smitch.hayenga@arm.com * event and prevent the evaluate phase from starting. 14011566Smitch.hayenga@arm.com */ 14111566Smitch.hayenga@arm.com 1426378Sgblack@eecs.umich.educlass Scheduler 1435222Sksewell@umich.edu{ 1446378Sgblack@eecs.umich.edu public: 1456378Sgblack@eecs.umich.edu Scheduler(); 1465222Sksewell@umich.edu 1476383Sgblack@eecs.umich.edu const std::string name() const { return "systemc_scheduler"; } 1486383Sgblack@eecs.umich.edu 1495222Sksewell@umich.edu uint64_t numCycles() { return _numCycles; } 1505222Sksewell@umich.edu Process *current() { return _current; } 1515222Sksewell@umich.edu 1525222Sksewell@umich.edu // Prepare for initialization. 1536378Sgblack@eecs.umich.edu void prepareForInit(); 1546378Sgblack@eecs.umich.edu 1556378Sgblack@eecs.umich.edu // Register a process with the scheduler. 1565222Sksewell@umich.edu void reg(Process *p); 1575222Sksewell@umich.edu 1585222Sksewell@umich.edu // Tell the scheduler not to initialize a process. 1595222Sksewell@umich.edu void dontInitialize(Process *p); 1606378Sgblack@eecs.umich.edu 1616378Sgblack@eecs.umich.edu // Run the next process, if there is one. 1625222Sksewell@umich.edu void yield(); 1635222Sksewell@umich.edu 1645222Sksewell@umich.edu // Put a process on the ready list. 1656378Sgblack@eecs.umich.edu void ready(Process *p); 1666378Sgblack@eecs.umich.edu 1675222Sksewell@umich.edu // Schedule an update for a given channel. 1686383Sgblack@eecs.umich.edu void requestUpdate(Channel *c); 1696379Sgblack@eecs.umich.edu 1706379Sgblack@eecs.umich.edu // Run the given process immediately, preempting whatever may be running. 1716379Sgblack@eecs.umich.edu void 1725222Sksewell@umich.edu runNow(Process *p) 1735222Sksewell@umich.edu { 1746378Sgblack@eecs.umich.edu // If a process is running, schedule it/us to run again. 1755222Sksewell@umich.edu if (_current) 1765222Sksewell@umich.edu readyList.pushFirst(_current); 1775222Sksewell@umich.edu // Schedule p to run first. 1785222Sksewell@umich.edu readyList.pushFirst(p); 1796379Sgblack@eecs.umich.edu yield(); 1806379Sgblack@eecs.umich.edu } 1816379Sgblack@eecs.umich.edu 1826379Sgblack@eecs.umich.edu // Set an event queue for scheduling events. 1836379Sgblack@eecs.umich.edu void setEventQueue(EventQueue *_eq) { eq = _eq; } 1846379Sgblack@eecs.umich.edu 185 // Get the current time according to gem5. 186 Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 187 188 // For scheduling delayed/timed notifications/timeouts. 189 void 190 schedule(::Event *event, Tick tick) 191 { 192 pendingTicks[tick]++; 193 194 if (initReady) 195 eq->schedule(event, tick); 196 else 197 eventsToSchedule[event] = tick; 198 } 199 200 // For descheduling delayed/timed notifications/timeouts. 201 void 202 deschedule(::Event *event) 203 { 204 auto it = pendingTicks.find(event->when()); 205 if (--it->second == 0) 206 pendingTicks.erase(it); 207 208 if (initReady) 209 eq->deschedule(event); 210 else 211 eventsToSchedule.erase(event); 212 } 213 214 // Tell the scheduler than an event fired for bookkeeping purposes. 215 void 216 eventHappened() 217 { 218 auto it = pendingTicks.begin(); 219 if (--it->second == 0) 220 pendingTicks.erase(it); 221 222 if (starved() && !runToTime) 223 scheduleStarvationEvent(); 224 } 225 226 // Pending activity ignores gem5 activity, much like how a systemc 227 // simulation wouldn't know about asynchronous external events (socket IO 228 // for instance) that might happen before time advances in a pure 229 // systemc simulation. Also the spec lists what specific types of pending 230 // activity needs to be counted, which obviously doesn't include gem5 231 // events. 232 233 // Return whether there's pending systemc activity at this time. 234 bool 235 pendingCurr() 236 { 237 if (!readyList.empty() || !updateList.empty()) 238 return true; 239 return pendingTicks.size() && 240 pendingTicks.begin()->first == getCurTick(); 241 } 242 243 // Return whether there are pending timed notifications or timeouts. 244 bool 245 pendingFuture() 246 { 247 switch (pendingTicks.size()) { 248 case 0: return false; 249 case 1: return pendingTicks.begin()->first > getCurTick(); 250 default: return true; 251 } 252 } 253 254 // Return how many ticks there are until the first pending event, if any. 255 Tick 256 timeToPending() 257 { 258 if (!readyList.empty() || !updateList.empty()) 259 return 0; 260 else if (pendingTicks.size()) 261 return pendingTicks.begin()->first - getCurTick(); 262 else 263 return MaxTick - getCurTick(); 264 } 265 266 // Run scheduled channel updates. 267 void update(); 268 269 void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 270 271 void start(Tick max_tick, bool run_to_time); 272 273 void schedulePause(); 274 void scheduleStop(bool finish_delta); 275 276 bool paused() { return _paused; } 277 bool stopped() { return _stopped; } 278 279 private: 280 typedef const EventBase::Priority Priority; 281 static Priority DefaultPriority = EventBase::Default_Pri; 282 283 static Priority StopPriority = DefaultPriority - 1; 284 static Priority PausePriority = DefaultPriority + 1; 285 static Priority MaxTickPriority = DefaultPriority + 2; 286 static Priority ReadyPriority = DefaultPriority + 3; 287 static Priority StarvationPriority = ReadyPriority; 288 289 EventQueue *eq; 290 std::map<Tick, int> pendingTicks; 291 292 void runReady(); 293 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 294 void scheduleReadyEvent(); 295 296 void pause(); 297 void stop(); 298 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 299 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 300 Fiber *scMain; 301 302 bool 303 starved() 304 { 305 return (readyList.empty() && updateList.empty() && 306 (pendingTicks.empty() || 307 pendingTicks.begin()->first > maxTick) && 308 initList.empty()); 309 } 310 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 311 void scheduleStarvationEvent(); 312 313 bool _started; 314 bool _paused; 315 bool _stopped; 316 317 Tick maxTick; 318 EventWrapper<Scheduler, &Scheduler::pause> maxTickEvent; 319 320 uint64_t _numCycles; 321 322 Process *_current; 323 324 bool initReady; 325 bool runToTime; 326 327 ProcessList initList; 328 ProcessList toFinalize; 329 ProcessList readyList; 330 331 ChannelList updateList; 332 333 std::map<::Event *, Tick> eventsToSchedule; 334}; 335 336extern Scheduler scheduler; 337 338} // namespace sc_gem5 339 340#endif // __SYSTEMC_CORE_SCHEDULER_H__ 341