scheduler.hh revision 13061:9b868a2ab73c
110259SAndrew.Bardsley@arm.com/* 210259SAndrew.Bardsley@arm.com * Copyright 2018 Google, Inc. 310259SAndrew.Bardsley@arm.com * 410259SAndrew.Bardsley@arm.com * Redistribution and use in source and binary forms, with or without 510259SAndrew.Bardsley@arm.com * modification, are permitted provided that the following conditions are 610259SAndrew.Bardsley@arm.com * met: redistributions of source code must retain the above copyright 710259SAndrew.Bardsley@arm.com * notice, this list of conditions and the following disclaimer; 810259SAndrew.Bardsley@arm.com * redistributions in binary form must reproduce the above copyright 910259SAndrew.Bardsley@arm.com * notice, this list of conditions and the following disclaimer in the 1010259SAndrew.Bardsley@arm.com * documentation and/or other materials provided with the distribution; 1110259SAndrew.Bardsley@arm.com * neither the name of the copyright holders nor the names of its 1210259SAndrew.Bardsley@arm.com * contributors may be used to endorse or promote products derived from 1310259SAndrew.Bardsley@arm.com * this software without specific prior written permission. 1410259SAndrew.Bardsley@arm.com * 1510259SAndrew.Bardsley@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1610259SAndrew.Bardsley@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1710259SAndrew.Bardsley@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1810259SAndrew.Bardsley@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 1910259SAndrew.Bardsley@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2010259SAndrew.Bardsley@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2110259SAndrew.Bardsley@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2210259SAndrew.Bardsley@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2310259SAndrew.Bardsley@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2410259SAndrew.Bardsley@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2510259SAndrew.Bardsley@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2610259SAndrew.Bardsley@arm.com * 2710259SAndrew.Bardsley@arm.com * Authors: Gabe Black 2810259SAndrew.Bardsley@arm.com */ 2910259SAndrew.Bardsley@arm.com 3010259SAndrew.Bardsley@arm.com#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 3110259SAndrew.Bardsley@arm.com#define __SYSTEMC_CORE_SCHEDULER_HH__ 3210259SAndrew.Bardsley@arm.com 3310259SAndrew.Bardsley@arm.com#include <vector> 3410259SAndrew.Bardsley@arm.com 3510259SAndrew.Bardsley@arm.com#include "base/logging.hh" 3610259SAndrew.Bardsley@arm.com#include "sim/eventq.hh" 3710259SAndrew.Bardsley@arm.com#include "systemc/core/channel.hh" 3810259SAndrew.Bardsley@arm.com#include "systemc/core/list.hh" 3910259SAndrew.Bardsley@arm.com#include "systemc/core/process.hh" 4010259SAndrew.Bardsley@arm.com 4110259SAndrew.Bardsley@arm.comclass Fiber; 4210259SAndrew.Bardsley@arm.com 4310259SAndrew.Bardsley@arm.comnamespace sc_gem5 4410259SAndrew.Bardsley@arm.com{ 4510259SAndrew.Bardsley@arm.com 4610259SAndrew.Bardsley@arm.comtypedef NodeList<Process> ProcessList; 4710259SAndrew.Bardsley@arm.comtypedef NodeList<Channel> ChannelList; 4810259SAndrew.Bardsley@arm.com 4910259SAndrew.Bardsley@arm.com/* 5010259SAndrew.Bardsley@arm.com * The scheduler supports three different mechanisms, the initialization phase, 5110259SAndrew.Bardsley@arm.com * delta cycles, and timed notifications. 5210259SAndrew.Bardsley@arm.com * 5310259SAndrew.Bardsley@arm.com * INITIALIZATION PHASE 5410259SAndrew.Bardsley@arm.com * 5510259SAndrew.Bardsley@arm.com * The initialization phase has three parts: 5610259SAndrew.Bardsley@arm.com * 1. Run requested channel updates. 5710259SAndrew.Bardsley@arm.com * 2. Make processes which need to initialize runnable (methods and threads 5810259SAndrew.Bardsley@arm.com * which didn't have dont_initialize called on them). 5910259SAndrew.Bardsley@arm.com * 3. Process delta notifications. 6010259SAndrew.Bardsley@arm.com * 6110259SAndrew.Bardsley@arm.com * First, the Kernel SimObject calls the update() method during its startup() 6210259SAndrew.Bardsley@arm.com * callback which handles the requested channel updates. The Kernel also 6310259SAndrew.Bardsley@arm.com * schedules an event to be run at time 0 with a slightly elevated priority 6410259SAndrew.Bardsley@arm.com * so that it happens before any "normal" event. 6510259SAndrew.Bardsley@arm.com * 6610259SAndrew.Bardsley@arm.com * When that t0 event happens, it calls the schedulers prepareForInit method 6710259SAndrew.Bardsley@arm.com * which performs step 2 above. That indirectly causes the scheduler's 6810259SAndrew.Bardsley@arm.com * readyEvent to be scheduled with slightly lowered priority, ensuring it 6910259SAndrew.Bardsley@arm.com * happens after any "normal" event. 7010259SAndrew.Bardsley@arm.com * 7110259SAndrew.Bardsley@arm.com * Because delta notifications are scheduled at the standard priority, all 7210259SAndrew.Bardsley@arm.com * of those events will happen next, performing step 3 above. Once they finish, 7310259SAndrew.Bardsley@arm.com * if the readyEvent was scheduled above, there shouldn't be any higher 7410259SAndrew.Bardsley@arm.com * priority events in front of it. When it runs, it will start the first 7510259SAndrew.Bardsley@arm.com * evaluate phase of the first delta cycle. 7610259SAndrew.Bardsley@arm.com * 7710259SAndrew.Bardsley@arm.com * DELTA CYCLE 7810259SAndrew.Bardsley@arm.com * 7910464SAndreas.Sandberg@ARM.com * A delta cycle has three phases within it. 8010259SAndrew.Bardsley@arm.com * 1. The evaluate phase where runnable processes are allowed to run. 8110259SAndrew.Bardsley@arm.com * 2. The update phase where requested channel updates hapen. 8210259SAndrew.Bardsley@arm.com * 3. The delta notification phase where delta notifications happen. 8310259SAndrew.Bardsley@arm.com * 8410259SAndrew.Bardsley@arm.com * The readyEvent runs the first two steps of the delta cycle. It first goes 8510259SAndrew.Bardsley@arm.com * through the list of runnable processes and executes them until the set is 8610259SAndrew.Bardsley@arm.com * empty, and then immediately runs the update phase. Since these are all part 8710259SAndrew.Bardsley@arm.com * of the same event, there's no chance for other events to intervene and 8810259SAndrew.Bardsley@arm.com * break the required order above. 8910259SAndrew.Bardsley@arm.com * 9010259SAndrew.Bardsley@arm.com * During the update phase above, the spec forbids any action which would make 9110259SAndrew.Bardsley@arm.com * a process runnable. That means that once the update phase finishes, the set 9210259SAndrew.Bardsley@arm.com * of runnable processes will be empty. There may, however, have been some 9310259SAndrew.Bardsley@arm.com * delta notifications/timeouts which will have been scheduled during either 9410259SAndrew.Bardsley@arm.com * the evaluate or update phase above. Because those are scheduled at the 9510259SAndrew.Bardsley@arm.com * normal priority, they will now happen together until there aren't any 9610259SAndrew.Bardsley@arm.com * delta events left. 9710259SAndrew.Bardsley@arm.com * 9810259SAndrew.Bardsley@arm.com * If any processes became runnable during the delta notification phase, the 9910259SAndrew.Bardsley@arm.com * readyEvent will have been scheduled and will have been waiting patiently 10010259SAndrew.Bardsley@arm.com * behind the delta notification events. That will now run, effectively 10110259SAndrew.Bardsley@arm.com * starting the next delta cycle. 10210259SAndrew.Bardsley@arm.com * 10310259SAndrew.Bardsley@arm.com * TIMED NOTIFICATION PHASE 10410259SAndrew.Bardsley@arm.com * 10510259SAndrew.Bardsley@arm.com * If no processes became runnable, the event queue will continue to process 10610259SAndrew.Bardsley@arm.com * events until it comes across a timed notification, aka a notification 10710259SAndrew.Bardsley@arm.com * scheduled to happen in the future. Like delta notification events, those 10810259SAndrew.Bardsley@arm.com * will all happen together since the readyEvent priority is lower, 10910259SAndrew.Bardsley@arm.com * potentially marking new processes as ready. Once these events finish, the 11010259SAndrew.Bardsley@arm.com * readyEvent may run, starting the next delta cycle. 11110259SAndrew.Bardsley@arm.com * 11210259SAndrew.Bardsley@arm.com * PAUSE/STOP 11310259SAndrew.Bardsley@arm.com * 11410259SAndrew.Bardsley@arm.com * To inject a pause from sc_pause which should happen after the current delta 11510259SAndrew.Bardsley@arm.com * cycle's delta notification phase, an event is scheduled with a lower than 11610259SAndrew.Bardsley@arm.com * normal priority, but higher than the readyEvent. That ensures that any 11710259SAndrew.Bardsley@arm.com * delta notifications which are scheduled with normal priority will happen 11810259SAndrew.Bardsley@arm.com * first, since those are part of the current delta cycle. Then the pause 11910259SAndrew.Bardsley@arm.com * event will happen before the next readyEvent which would start the next 12010259SAndrew.Bardsley@arm.com * delta cycle. All of these events are scheduled for the current time, and so 12110259SAndrew.Bardsley@arm.com * would happen before any timed notifications went off. 12210259SAndrew.Bardsley@arm.com * 12310259SAndrew.Bardsley@arm.com * To inject a stop from sc_stop, the delta cycles should stop before even the 12410259SAndrew.Bardsley@arm.com * delta notifications have happened, but after the evaluate and update phases. 12510259SAndrew.Bardsley@arm.com * For that, a stop event with slightly higher than normal priority will be 12610259SAndrew.Bardsley@arm.com * scheduled so that it happens before any of the delta notification events 12710259SAndrew.Bardsley@arm.com * which are at normal priority. 12810259SAndrew.Bardsley@arm.com * 12910259SAndrew.Bardsley@arm.com * MAX RUN TIME 13010259SAndrew.Bardsley@arm.com * 13110259SAndrew.Bardsley@arm.com * When sc_start is called, it's possible to pass in a maximum time the 13210259SAndrew.Bardsley@arm.com * simulation should run to, at which point sc_pause is implicitly called. The 13310259SAndrew.Bardsley@arm.com * simulation is supposed to run up to the latest timed notification phase 13410259SAndrew.Bardsley@arm.com * which is less than or equal to the maximum time. In other words it should 13510259SAndrew.Bardsley@arm.com * run timed notifications at the maximum time, but not the subsequent evaluate 13610464SAndreas.Sandberg@ARM.com * phase. That's implemented by scheduling an event at the max time with a 13710259SAndrew.Bardsley@arm.com * priority which is lower than all the others except the ready event. Timed 13810259SAndrew.Bardsley@arm.com * notifications will happen before it fires, but it will override any ready 13910259SAndrew.Bardsley@arm.com * event and prevent the evaluate phase from starting. 14010259SAndrew.Bardsley@arm.com */ 14110259SAndrew.Bardsley@arm.com 14210259SAndrew.Bardsley@arm.comclass Scheduler 14310259SAndrew.Bardsley@arm.com{ 14410259SAndrew.Bardsley@arm.com public: 14510259SAndrew.Bardsley@arm.com Scheduler(); 14610259SAndrew.Bardsley@arm.com 14710259SAndrew.Bardsley@arm.com const std::string name() const { return "systemc_scheduler"; } 14810259SAndrew.Bardsley@arm.com 14910259SAndrew.Bardsley@arm.com uint64_t numCycles() { return _numCycles; } 15010259SAndrew.Bardsley@arm.com Process *current() { return _current; } 15110259SAndrew.Bardsley@arm.com 15210259SAndrew.Bardsley@arm.com // Prepare for initialization. 15310259SAndrew.Bardsley@arm.com void prepareForInit(); 15410259SAndrew.Bardsley@arm.com 15510259SAndrew.Bardsley@arm.com // Register a process with the scheduler. 15610259SAndrew.Bardsley@arm.com void reg(Process *p); 15710259SAndrew.Bardsley@arm.com 15810259SAndrew.Bardsley@arm.com // Tell the scheduler not to initialize a process. 15910259SAndrew.Bardsley@arm.com void dontInitialize(Process *p); 16010259SAndrew.Bardsley@arm.com 16110259SAndrew.Bardsley@arm.com // Run the next process, if there is one. 16210259SAndrew.Bardsley@arm.com void yield(); 16310259SAndrew.Bardsley@arm.com 16410259SAndrew.Bardsley@arm.com // Put a process on the ready list. 16510259SAndrew.Bardsley@arm.com void ready(Process *p); 16610259SAndrew.Bardsley@arm.com 16710259SAndrew.Bardsley@arm.com // Schedule an update for a given channel. 16810259SAndrew.Bardsley@arm.com void requestUpdate(Channel *c); 16910259SAndrew.Bardsley@arm.com 17010259SAndrew.Bardsley@arm.com // Run the given process immediately, preempting whatever may be running. 17110259SAndrew.Bardsley@arm.com void 17210464SAndreas.Sandberg@ARM.com runNow(Process *p) 17310464SAndreas.Sandberg@ARM.com { 17410464SAndreas.Sandberg@ARM.com // If a process is running, schedule it/us to run again. 17510464SAndreas.Sandberg@ARM.com if (_current) 17610464SAndreas.Sandberg@ARM.com readyList.pushFirst(_current); 17710464SAndreas.Sandberg@ARM.com // Schedule p to run first. 17810464SAndreas.Sandberg@ARM.com readyList.pushFirst(p); 17910464SAndreas.Sandberg@ARM.com yield(); 18010464SAndreas.Sandberg@ARM.com } 18110464SAndreas.Sandberg@ARM.com 18210464SAndreas.Sandberg@ARM.com // Set an event queue for scheduling events. 18310464SAndreas.Sandberg@ARM.com void setEventQueue(EventQueue *_eq) { eq = _eq; } 18410464SAndreas.Sandberg@ARM.com 18510259SAndrew.Bardsley@arm.com // Get the current time according to gem5. 18610259SAndrew.Bardsley@arm.com Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 18710259SAndrew.Bardsley@arm.com 18810259SAndrew.Bardsley@arm.com // For scheduling delayed/timed notifications/timeouts. 18910259SAndrew.Bardsley@arm.com void 19010259SAndrew.Bardsley@arm.com schedule(::Event *event, Tick tick) 19110259SAndrew.Bardsley@arm.com { 19210259SAndrew.Bardsley@arm.com pendingTicks[tick]++; 19310259SAndrew.Bardsley@arm.com 19410259SAndrew.Bardsley@arm.com if (initReady) 19510259SAndrew.Bardsley@arm.com eq->schedule(event, tick); 19610259SAndrew.Bardsley@arm.com else 19710259SAndrew.Bardsley@arm.com eventsToSchedule[event] = tick; 19810259SAndrew.Bardsley@arm.com } 19910259SAndrew.Bardsley@arm.com 20010259SAndrew.Bardsley@arm.com // For descheduling delayed/timed notifications/timeouts. 20110259SAndrew.Bardsley@arm.com void 20210259SAndrew.Bardsley@arm.com deschedule(::Event *event) 20310259SAndrew.Bardsley@arm.com { 20410259SAndrew.Bardsley@arm.com auto it = pendingTicks.find(event->when()); 20510259SAndrew.Bardsley@arm.com if (--it->second == 0) 20610259SAndrew.Bardsley@arm.com 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 void oneCycle(); 273 274 void schedulePause(); 275 void scheduleStop(bool finish_delta); 276 277 bool paused() { return _paused; } 278 bool stopped() { return _stopped; } 279 280 private: 281 typedef const EventBase::Priority Priority; 282 static Priority DefaultPriority = EventBase::Default_Pri; 283 284 static Priority StopPriority = DefaultPriority - 1; 285 static Priority PausePriority = DefaultPriority + 1; 286 static Priority MaxTickPriority = DefaultPriority + 2; 287 static Priority ReadyPriority = DefaultPriority + 3; 288 static Priority StarvationPriority = ReadyPriority; 289 290 EventQueue *eq; 291 std::map<Tick, int> pendingTicks; 292 293 void runReady(); 294 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 295 void scheduleReadyEvent(); 296 297 void pause(); 298 void stop(); 299 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 300 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 301 Fiber *scMain; 302 303 bool 304 starved() 305 { 306 return (readyList.empty() && updateList.empty() && 307 (pendingTicks.empty() || 308 pendingTicks.begin()->first > maxTick) && 309 initList.empty()); 310 } 311 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 312 void scheduleStarvationEvent(); 313 314 bool _started; 315 bool _paused; 316 bool _stopped; 317 318 Tick maxTick; 319 EventWrapper<Scheduler, &Scheduler::pause> maxTickEvent; 320 321 uint64_t _numCycles; 322 323 Process *_current; 324 325 bool initReady; 326 bool runToTime; 327 bool runOnce; 328 329 ProcessList initList; 330 ProcessList toFinalize; 331 ProcessList readyList; 332 333 ChannelList updateList; 334 335 std::map<::Event *, Tick> eventsToSchedule; 336}; 337 338extern Scheduler scheduler; 339 340} // namespace sc_gem5 341 342#endif // __SYSTEMC_CORE_SCHEDULER_H__ 343