2 * Copyright 2018 Google, Inc.
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.
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.
28 #ifndef __SYSTEMC_CORE_SCHEDULER_HH__
29 #define __SYSTEMC_CORE_SCHEDULER_HH__
37 #include "base/logging.hh"
38 #include "sim/core.hh"
39 #include "sim/eventq.hh"
40 #include "systemc/core/channel.hh"
41 #include "systemc/core/list.hh"
42 #include "systemc/core/process.hh"
43 #include "systemc/core/sched_event.hh"
52 typedef NodeList<Process> ProcessList;
53 typedef NodeList<Channel> ChannelList;
56 * The scheduler supports three different mechanisms, the initialization phase,
57 * delta cycles, and timed notifications.
59 * INITIALIZATION PHASE
61 * The initialization phase has three parts:
62 * 1. Run requested channel updates.
63 * 2. Make processes which need to initialize runnable (methods and threads
64 * which didn't have dont_initialize called on them).
65 * 3. Process delta notifications.
67 * First, the Kernel SimObject calls the update() method during its startup()
68 * callback which handles the requested channel updates. The Kernel also
69 * schedules an event to be run at time 0 with a slightly elevated priority
70 * so that it happens before any "normal" event.
72 * When that t0 event happens, it calls the schedulers prepareForInit method
73 * which performs step 2 above. That indirectly causes the scheduler's
74 * readyEvent to be scheduled with slightly lowered priority, ensuring it
75 * happens after any "normal" event.
77 * Because delta notifications are scheduled at the standard priority, all
78 * of those events will happen next, performing step 3 above. Once they finish,
79 * if the readyEvent was scheduled above, there shouldn't be any higher
80 * priority events in front of it. When it runs, it will start the first
81 * evaluate phase of the first delta cycle.
85 * A delta cycle has three phases within it.
86 * 1. The evaluate phase where runnable processes are allowed to run.
87 * 2. The update phase where requested channel updates hapen.
88 * 3. The delta notification phase where delta notifications happen.
90 * The readyEvent runs all three steps of the delta cycle. It first goes
91 * through the list of runnable processes and executes them until the set is
92 * empty, and then immediately runs the update phase. Since these are all part
93 * of the same event, there's no chance for other events to intervene and
94 * break the required order above.
96 * During the update phase above, the spec forbids any action which would make
97 * a process runnable. That means that once the update phase finishes, the set
98 * of runnable processes will be empty. There may, however, have been some
99 * delta notifications/timeouts which will have been scheduled during either
100 * the evaluate or update phase above. Those will have been accumulated in the
101 * scheduler, and are now all executed.
103 * If any processes became runnable during the delta notification phase, the
104 * readyEvent will have been scheduled and will be waiting and ready to run
105 * again, effectively starting the next delta cycle.
107 * TIMED NOTIFICATION PHASE
109 * If no processes became runnable, the event queue will continue to process
110 * events until it comes across an event which represents all the timed
111 * notifications which are supposed to happen at a particular time. The object
112 * which tracks them will execute all those notifications, and then destroy
113 * itself. If the readyEvent is now ready to run, the next delta cycle will
118 * To inject a pause from sc_pause which should happen after the current delta
119 * cycle's delta notification phase, an event is scheduled with a lower than
120 * normal priority, but higher than the readyEvent. That ensures that any
121 * delta notifications which are scheduled with normal priority will happen
122 * first, since those are part of the current delta cycle. Then the pause
123 * event will happen before the next readyEvent which would start the next
124 * delta cycle. All of these events are scheduled for the current time, and so
125 * would happen before any timed notifications went off.
127 * To inject a stop from sc_stop, the delta cycles should stop before even the
128 * delta notifications have happened, but after the evaluate and update phases.
129 * For that, a stop event with slightly higher than normal priority will be
130 * scheduled so that it happens before any of the delta notification events
131 * which are at normal priority.
135 * When sc_start is called, it's possible to pass in a maximum time the
136 * simulation should run to, at which point sc_pause is implicitly called. The
137 * simulation is supposed to run up to the latest timed notification phase
138 * which is less than or equal to the maximum time. In other words it should
139 * run timed notifications at the maximum time, but not the subsequent evaluate
140 * phase. That's implemented by scheduling an event at the max time with a
141 * priority which is lower than all the others except the ready event. Timed
142 * notifications will happen before it fires, but it will override any ready
143 * event and prevent the evaluate phase from starting.
149 typedef std::list<ScEvent *> ScEvents;
151 class TimeSlot : public ::Event
154 TimeSlot() : ::Event(Default_Pri, AutoDelete) {}
160 typedef std::map<Tick, TimeSlot *> TimeSlots;
167 const std::string name() const { return "systemc_scheduler"; }
169 uint64_t numCycles() { return _numCycles; }
170 Process *current() { return _current; }
174 // Register a process with the scheduler.
175 void reg(Process *p);
177 // Run the next process, if there is one.
180 // Put a process on the ready list.
181 void ready(Process *p);
183 // Mark a process as ready if init is finished, or put it on the list of
184 // processes to be initialized.
185 void resume(Process *p);
187 // Remove a process from the ready/init list if it was on one of them, and
189 bool suspend(Process *p);
191 // Schedule an update for a given channel.
192 void requestUpdate(Channel *c);
193 // Same as above, but may be called from a different thread.
194 void asyncRequestUpdate(Channel *c);
196 // Run the given process immediately, preempting whatever may be running.
200 // This function may put a process on the wrong list, ie a thread
201 // the method list. That's fine since that's just a performance
202 // optimization, and the important thing here is how the processes are
205 // If a process is running, schedule it/us to run again.
207 readyListMethods.pushFirst(_current);
208 // Schedule p to run first.
209 readyListMethods.pushFirst(p);
213 // Run this process at the next opportunity.
217 // Like above, it's ok if this isn't a method. Putting it on this list
218 // just gives it priority.
219 readyListMethods.pushFirst(p);
221 scheduleReadyEvent();
224 // Set an event queue for scheduling events.
225 void setEventQueue(EventQueue *_eq) { eq = _eq; }
227 // Get the current time according to gem5.
228 Tick getCurTick() { return eq ? eq->getCurTick() : 0; }
231 delayed(const ::sc_core::sc_time &delay)
233 return getCurTick() + delay.value();
236 // For scheduling delayed/timed notifications/timeouts.
238 schedule(ScEvent *event, const ::sc_core::sc_time &delay)
240 Tick tick = delayed(delay);
241 if (tick < getCurTick())
244 // Delta notification/timeout.
245 if (delay.value() == 0) {
246 event->schedule(deltas, tick);
247 if (!inEvaluate() && !inUpdate())
248 scheduleReadyEvent();
252 // Timed notification/timeout.
253 TimeSlot *&ts = timeSlots[tick];
258 event->schedule(ts->events, tick);
261 // For descheduling delayed/timed notifications/timeouts.
263 deschedule(ScEvent *event)
265 ScEvents *on = event->scheduledOn();
272 // Timed notification/timeout.
273 auto tsit = timeSlots.find(event->when());
274 panic_if(tsit == timeSlots.end(),
275 "Descheduling event at time with no events.");
276 TimeSlot *ts = tsit->second;
277 ScEvents &events = ts->events;
278 assert(on == &events);
281 // If no more events are happening at this time slot, get rid of it.
282 if (events.empty()) {
284 timeSlots.erase(tsit);
289 completeTimeSlot(TimeSlot *ts)
291 assert(ts == timeSlots.begin()->second);
292 timeSlots.erase(timeSlots.begin());
293 if (!runToTime && starved())
294 scheduleStarvationEvent();
295 scheduleTimeAdvancesEvent();
298 // Pending activity ignores gem5 activity, much like how a systemc
299 // simulation wouldn't know about asynchronous external events (socket IO
300 // for instance) that might happen before time advances in a pure
301 // systemc simulation. Also the spec lists what specific types of pending
302 // activity needs to be counted, which obviously doesn't include gem5
305 // Return whether there's pending systemc activity at this time.
309 return !readyListMethods.empty() || !readyListThreads.empty() ||
310 !updateList.empty() || !deltas.empty();
313 // Return whether there are pending timed notifications or timeouts.
317 return !timeSlots.empty();
320 // Return how many ticks there are until the first pending event, if any.
327 return timeSlots.begin()->first - getCurTick();
328 return MaxTick - getCurTick();
331 // Run scheduled channel updates.
337 void start(Tick max_tick, bool run_to_time);
340 void schedulePause();
341 void scheduleStop(bool finish_delta);
354 bool elaborationDone() { return _elaborationDone; }
355 void elaborationDone(bool b) { _elaborationDone = b; }
357 bool paused() { return status() == StatusPaused; }
358 bool stopped() { return status() == StatusStopped; }
359 bool inEvaluate() { return status() == StatusEvaluate; }
360 bool inUpdate() { return status() == StatusUpdate; }
361 bool inDelta() { return status() == StatusDelta; }
362 bool inTiming() { return status() == StatusTiming; }
364 uint64_t changeStamp() { return _changeStamp; }
365 void stepChangeStamp() { _changeStamp++; }
367 // Throw upwards, either to sc_main or to the report handler if sc_main
371 Status status() { return _status; }
372 void status(Status s) { _status = s; }
374 void registerTraceFile(TraceFile *tf) { traceFiles.insert(tf); }
375 void unregisterTraceFile(TraceFile *tf) { traceFiles.erase(tf); }
378 typedef const EventBase::Priority Priority;
379 static Priority DefaultPriority = EventBase::Default_Pri;
381 static Priority StopPriority = DefaultPriority - 1;
382 static Priority PausePriority = DefaultPriority + 1;
383 static Priority MaxTickPriority = DefaultPriority + 2;
384 static Priority ReadyPriority = DefaultPriority + 3;
385 static Priority StarvationPriority = ReadyPriority;
386 static Priority TimeAdvancesPriority = EventBase::Maximum_Pri;
390 // For gem5 style events.
392 schedule(::Event *event, Tick tick)
395 eq->schedule(event, tick);
397 eventsToSchedule[event] = tick;
400 void schedule(::Event *event) { schedule(event, getCurTick()); }
403 deschedule(::Event *event)
406 eq->deschedule(event);
408 eventsToSchedule.erase(event);
417 Process *p = readyListMethods.getNext();
418 return p ? p : readyListThreads.getNext();
422 EventWrapper<Scheduler, &Scheduler::runReady> readyEvent;
423 void scheduleReadyEvent();
427 EventWrapper<Scheduler, &Scheduler::pause> pauseEvent;
428 EventWrapper<Scheduler, &Scheduler::stop> stopEvent;
430 const ::sc_core::sc_report *_throwUp;
435 return (readyListMethods.empty() && readyListThreads.empty() &&
436 updateList.empty() && deltas.empty() &&
437 (timeSlots.empty() || timeSlots.begin()->first > maxTick) &&
440 EventWrapper<Scheduler, &Scheduler::pause> starvationEvent;
441 void scheduleStarvationEvent();
443 bool _elaborationDone;
454 if (lastReadyTick != getCurTick())
458 EventWrapper<Scheduler, &Scheduler::maxTickFunc> maxTickEvent;
460 void timeAdvances() { trace(false); }
461 EventWrapper<Scheduler, &Scheduler::timeAdvances> timeAdvancesEvent;
463 scheduleTimeAdvancesEvent()
465 if (!traceFiles.empty() && !timeAdvancesEvent.scheduled())
466 schedule(&timeAdvancesEvent);
470 uint64_t _changeStamp;
478 ProcessList initList;
480 ProcessList readyListMethods;
481 ProcessList readyListThreads;
483 ChannelList updateList;
485 ChannelList asyncUpdateList;
486 std::mutex asyncListMutex;
488 std::map<::Event *, Tick> eventsToSchedule;
490 std::set<TraceFile *> traceFiles;
492 void trace(bool delta);
495 extern Scheduler scheduler;
497 // A proxy function to avoid having to expose the scheduler in header files.
498 Process *getCurrentProcess();
501 Scheduler::TimeSlot::process()
503 scheduler.stepChangeStamp();
504 scheduler.status(StatusTiming);
507 while (!events.empty())
508 events.front()->run();
511 scheduler.completeTimeSlot(this);
513 scheduler.schedule(this);
517 scheduler.status(StatusOther);
518 scheduler.completeTimeSlot(this);
521 const ::sc_core::sc_report reportifyException();
523 } // namespace sc_gem5
525 #endif // __SYSTEMC_CORE_SCHEDULER_H__