scheduler.hh revision 13133
17008Snate@binkert.org/* 27008Snate@binkert.org * Copyright 2018 Google, Inc. 37008Snate@binkert.org * 47008Snate@binkert.org * Redistribution and use in source and binary forms, with or without 57008Snate@binkert.org * modification, are permitted provided that the following conditions are 67008Snate@binkert.org * met: redistributions of source code must retain the above copyright 77008Snate@binkert.org * notice, this list of conditions and the following disclaimer; 87008Snate@binkert.org * redistributions in binary form must reproduce the above copyright 97008Snate@binkert.org * notice, this list of conditions and the following disclaimer in the 107008Snate@binkert.org * documentation and/or other materials provided with the distribution; 117008Snate@binkert.org * neither the name of the copyright holders nor the names of its 127008Snate@binkert.org * contributors may be used to endorse or promote products derived from 137008Snate@binkert.org * this software without specific prior written permission. 147008Snate@binkert.org * 157008Snate@binkert.org * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 167008Snate@binkert.org * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 177008Snate@binkert.org * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 187008Snate@binkert.org * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 197008Snate@binkert.org * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 207008Snate@binkert.org * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 217008Snate@binkert.org * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 227008Snate@binkert.org * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 237008Snate@binkert.org * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 247008Snate@binkert.org * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 257008Snate@binkert.org * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 267008Snate@binkert.org * 277008Snate@binkert.org * Authors: Gabe Black 286285Snate@binkert.org */ 297039Snate@binkert.org 307039Snate@binkert.org#ifndef __SYSTEMC_CORE_SCHEDULER_HH__ 316285Snate@binkert.org#define __SYSTEMC_CORE_SCHEDULER_HH__ 3210706Spower.jg@gmail.com 336285Snate@binkert.org#include <functional> 347039Snate@binkert.org#include <map> 359104Shestness@cs.utexas.edu#include <set> 366285Snate@binkert.org#include <vector> 3711339SMichael.Lebeane@amd.com 386876Ssteve.reinhardt@amd.com#include "base/logging.hh" 396876Ssteve.reinhardt@amd.com#include "sim/core.hh" 407039Snate@binkert.org#include "sim/eventq.hh" 417039Snate@binkert.org#include "systemc/core/channel.hh" 427039Snate@binkert.org#include "systemc/core/list.hh" 437039Snate@binkert.org#include "systemc/core/process.hh" 447039Snate@binkert.org#include "systemc/core/sched_event.hh" 457039Snate@binkert.org 467039Snate@binkert.orgclass Fiber; 479208Snilay@cs.wisc.edu 487039Snate@binkert.orgnamespace sc_gem5 496285Snate@binkert.org{ 506285Snate@binkert.org 5111339SMichael.Lebeane@amd.comtypedef NodeList<Process> ProcessList; 527039Snate@binkert.orgtypedef NodeList<Channel> ChannelList; 537039Snate@binkert.org 546876Ssteve.reinhardt@amd.com/* 557039Snate@binkert.org * The scheduler supports three different mechanisms, the initialization phase, 5611169Sandreas.hansson@arm.com * delta cycles, and timed notifications. 5710518Snilay@cs.wisc.edu * 587039Snate@binkert.org * INITIALIZATION PHASE 598615Snilay@cs.wisc.edu * 607039Snate@binkert.org * The initialization phase has three parts: 618688Snilay@cs.wisc.edu * 1. Run requested channel updates. 628688Snilay@cs.wisc.edu * 2. Make processes which need to initialize runnable (methods and threads 638688Snilay@cs.wisc.edu * which didn't have dont_initialize called on them). 646285Snate@binkert.org * 3. Process delta notifications. 657039Snate@binkert.org * 667039Snate@binkert.org * First, the Kernel SimObject calls the update() method during its startup() 677039Snate@binkert.org * callback which handles the requested channel updates. The Kernel also 686285Snate@binkert.org * schedules an event to be run at time 0 with a slightly elevated priority 699104Shestness@cs.utexas.edu * so that it happens before any "normal" event. 709104Shestness@cs.utexas.edu * 717039Snate@binkert.org * When that t0 event happens, it calls the schedulers prepareForInit method 727039Snate@binkert.org * which performs step 2 above. That indirectly causes the scheduler's 7310518Snilay@cs.wisc.edu * readyEvent to be scheduled with slightly lowered priority, ensuring it 747039Snate@binkert.org * happens after any "normal" event. 757039Snate@binkert.org * 767039Snate@binkert.org * Because delta notifications are scheduled at the standard priority, all 776285Snate@binkert.org * of those events will happen next, performing step 3 above. Once they finish, 786285Snate@binkert.org * if the readyEvent was scheduled above, there shouldn't be any higher 797039Snate@binkert.org * priority events in front of it. When it runs, it will start the first 80 * evaluate phase of the first delta cycle. 81 * 82 * DELTA CYCLE 83 * 84 * A delta cycle has three phases within it. 85 * 1. The evaluate phase where runnable processes are allowed to run. 86 * 2. The update phase where requested channel updates hapen. 87 * 3. The delta notification phase where delta notifications happen. 88 * 89 * The readyEvent runs all three steps of the delta cycle. It first goes 90 * through the list of runnable processes and executes them until the set is 91 * empty, and then immediately runs the update phase. Since these are all part 92 * of the same event, there's no chance for other events to intervene and 93 * break the required order above. 94 * 95 * During the update phase above, the spec forbids any action which would make 96 * a process runnable. That means that once the update phase finishes, the set 97 * of runnable processes will be empty. There may, however, have been some 98 * delta notifications/timeouts which will have been scheduled during either 99 * the evaluate or update phase above. Those will have been accumulated in the 100 * scheduler, and are now all executed. 101 * 102 * If any processes became runnable during the delta notification phase, the 103 * readyEvent will have been scheduled and will be waiting and ready to run 104 * again, effectively starting the next delta cycle. 105 * 106 * TIMED NOTIFICATION PHASE 107 * 108 * If no processes became runnable, the event queue will continue to process 109 * events until it comes across an event which represents all the timed 110 * notifications which are supposed to happen at a particular time. The object 111 * which tracks them will execute all those notifications, and then destroy 112 * itself. If the readyEvent is now ready to run, the next delta cycle will 113 * start. 114 * 115 * PAUSE/STOP 116 * 117 * To inject a pause from sc_pause which should happen after the current delta 118 * cycle's delta notification phase, an event is scheduled with a lower than 119 * normal priority, but higher than the readyEvent. That ensures that any 120 * delta notifications which are scheduled with normal priority will happen 121 * first, since those are part of the current delta cycle. Then the pause 122 * event will happen before the next readyEvent which would start the next 123 * delta cycle. All of these events are scheduled for the current time, and so 124 * would happen before any timed notifications went off. 125 * 126 * To inject a stop from sc_stop, the delta cycles should stop before even the 127 * delta notifications have happened, but after the evaluate and update phases. 128 * For that, a stop event with slightly higher than normal priority will be 129 * scheduled so that it happens before any of the delta notification events 130 * which are at normal priority. 131 * 132 * MAX RUN TIME 133 * 134 * When sc_start is called, it's possible to pass in a maximum time the 135 * simulation should run to, at which point sc_pause is implicitly called. The 136 * simulation is supposed to run up to the latest timed notification phase 137 * which is less than or equal to the maximum time. In other words it should 138 * run timed notifications at the maximum time, but not the subsequent evaluate 139 * phase. That's implemented by scheduling an event at the max time with a 140 * priority which is lower than all the others except the ready event. Timed 141 * notifications will happen before it fires, but it will override any ready 142 * event and prevent the evaluate phase from starting. 143 */ 144 145class Scheduler 146{ 147 public: 148 typedef std::set<ScEvent *> ScEvents; 149 150 class TimeSlot : public ::Event 151 { 152 public: 153 TimeSlot() : ::Event(Default_Pri, AutoDelete) {} 154 155 ScEvents events; 156 void process(); 157 }; 158 159 typedef std::map<Tick, TimeSlot *> TimeSlots; 160 161 Scheduler(); 162 ~Scheduler(); 163 164 void clear(); 165 166 const std::string name() const { return "systemc_scheduler"; } 167 168 uint64_t numCycles() { return _numCycles; } 169 Process *current() { return _current; } 170 171 void initPhase(); 172 173 // Register a process with the scheduler. 174 void reg(Process *p); 175 176 // Tell the scheduler not to initialize a process. 177 void dontInitialize(Process *p); 178 179 // Run the next process, if there is one. 180 void yield(); 181 182 // Put a process on the ready list. 183 void ready(Process *p); 184 185 // Mark a process as ready if init is finished, or put it on the list of 186 // processes to be initialized. 187 void resume(Process *p); 188 189 // Remove a process from the ready/init list if it was on one of them, and 190 // return if it was. 191 bool suspend(Process *p); 192 193 // Schedule an update for a given channel. 194 void requestUpdate(Channel *c); 195 196 // Run the given process immediately, preempting whatever may be running. 197 void 198 runNow(Process *p) 199 { 200 // If a process is running, schedule it/us to run again. 201 if (_current) 202 readyList.pushFirst(_current); 203 // Schedule p to run first. 204 readyList.pushFirst(p); 205 yield(); 206 } 207 208 // Set an event queue for scheduling events. 209 void setEventQueue(EventQueue *_eq) { eq = _eq; } 210 211 // Get the current time according to gem5. 212 Tick getCurTick() { return eq ? eq->getCurTick() : 0; } 213 214 Tick 215 delayed(const ::sc_core::sc_time &delay) 216 { 217 //XXX We're assuming the systemc time resolution is in ps. 218 return getCurTick() + delay.value() * SimClock::Int::ps; 219 } 220 221 // For scheduling delayed/timed notifications/timeouts. 222 void 223 schedule(ScEvent *event, const ::sc_core::sc_time &delay) 224 { 225 Tick tick = delayed(delay); 226 if (tick < getCurTick()) 227 tick = getCurTick(); 228 229 event->schedule(tick); 230 231 // Delta notification/timeout. 232 if (delay.value() == 0) { 233 deltas.insert(event); 234 scheduleReadyEvent(); 235 return; 236 } 237 238 // Timed notification/timeout. 239 TimeSlot *&ts = timeSlots[tick]; 240 if (!ts) { 241 ts = new TimeSlot; 242 schedule(ts, tick); 243 } 244 ts->events.insert(event); 245 } 246 247 // For descheduling delayed/timed notifications/timeouts. 248 void 249 deschedule(ScEvent *event) 250 { 251 if (event->when() == getCurTick()) { 252 // Attempt to remove from delta notifications. 253 if (deltas.erase(event) == 1) { 254 event->deschedule(); 255 return; 256 } 257 } 258 259 // Timed notification/timeout. 260 auto tsit = timeSlots.find(event->when()); 261 panic_if(tsit == timeSlots.end(), 262 "Descheduling event at time with no events."); 263 TimeSlot *ts = tsit->second; 264 ScEvents &events = ts->events; 265 assert(events.erase(event)); 266 event->deschedule(); 267 268 // If no more events are happening at this time slot, get rid of it. 269 if (events.empty()) { 270 deschedule(ts); 271 timeSlots.erase(tsit); 272 } 273 } 274 275 void 276 completeTimeSlot(TimeSlot *ts) 277 { 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 !readyList.empty() || !updateList.empty() || !deltas.empty(); 296 } 297 298 // Return whether there are pending timed notifications or timeouts. 299 bool 300 pendingFuture() 301 { 302 return !timeSlots.empty(); 303 } 304 305 // Return how many ticks there are until the first pending event, if any. 306 Tick 307 timeToPending() 308 { 309 if (pendingCurr()) 310 return 0; 311 if (pendingFuture()) 312 return timeSlots.begin()->first - getCurTick(); 313 return MaxTick - getCurTick(); 314 } 315 316 // Run scheduled channel updates. 317 void update(); 318 319 void setScMainFiber(Fiber *sc_main) { scMain = sc_main; } 320 321 void start(Tick max_tick, bool run_to_time); 322 void oneCycle(); 323 324 void schedulePause(); 325 void scheduleStop(bool finish_delta); 326 327 bool paused() { return _paused; } 328 bool stopped() { return _stopped; } 329 330 private: 331 typedef const EventBase::Priority Priority; 332 static Priority DefaultPriority = EventBase::Default_Pri; 333 334 static Priority StopPriority = DefaultPriority - 1; 335 static Priority PausePriority = DefaultPriority + 1; 336 static Priority MaxTickPriority = DefaultPriority + 2; 337 static Priority ReadyPriority = DefaultPriority + 3; 338 static Priority StarvationPriority = ReadyPriority; 339 340 EventQueue *eq; 341 342 // For gem5 style events. 343 void 344 schedule(::Event *event, Tick tick) 345 { 346 if (initDone) 347 eq->schedule(event, tick); 348 else 349 eventsToSchedule[event] = tick; 350 } 351 352 void schedule(::Event *event) { schedule(event, getCurTick()); } 353 354 void 355 deschedule(::Event *event) 356 { 357 if (initDone) 358 eq->deschedule(event); 359 else 360 eventsToSchedule.erase(event); 361 } 362 363 ScEvents deltas; 364 TimeSlots timeSlots; 365 366 void runReady(); 367 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent; 368 void scheduleReadyEvent(); 369 370 void pause(); 371 void stop(); 372 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent; 373 EventWrapper<Scheduler, &Scheduler::stop> stopEvent; 374 Fiber *scMain; 375 376 bool 377 starved() 378 { 379 return (readyList.empty() && updateList.empty() && deltas.empty() && 380 (timeSlots.empty() || timeSlots.begin()->first > maxTick) && 381 initList.empty()); 382 } 383 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent; 384 void scheduleStarvationEvent(); 385 386 bool _started; 387 bool _paused; 388 bool _stopped; 389 390 Tick maxTick; 391 EventWrapper<Scheduler, &Scheduler::pause> maxTickEvent; 392 393 uint64_t _numCycles; 394 395 Process *_current; 396 397 bool initDone; 398 bool runToTime; 399 bool runOnce; 400 401 ProcessList initList; 402 ProcessList toFinalize; 403 ProcessList readyList; 404 405 ChannelList updateList; 406 407 std::map<::Event *, Tick> eventsToSchedule; 408}; 409 410extern Scheduler scheduler; 411 412inline void 413Scheduler::TimeSlot::process() 414{ 415 for (auto &e: events) 416 e->run(); 417 scheduler.completeTimeSlot(this); 418} 419 420} // namespace sc_gem5 421 422#endif // __SYSTEMC_CORE_SCHEDULER_H__ 423