- class Thread;
- class WaitQueue;
-
- // This is a reasonably simple O(1) scheduler that provides both
- // real-time and timeshared scheduling, with (non-rt) priority boosts
- // for interactive tasks.
- //
- // At some point, it'd be nice to extend/replace this with something
- // that gives more options to how to schedule tasks. Priority
- // inheritance would be nice, as would the ability to schedule groups
- // of threads as one prior to scheduling within the group. The latter
- // would help avoid giving more CPU time to certain apps simply
- // because they divided their work among more threads (or to certain
- // users simply because they're running more programs).
- //
- // At some sooner point, SMP support will need to be added.
-
- class Sched {
- public:
- enum {
- // The default timeslice of 10 ms applies to priority 8
- // timeshared tasks.
-
- default_timeslice = 10000000,
- rt_prios = 256,
- ts_static_prios = 16,
-
- // This must not exceed 32 without increasing the size
- // of ts_bitmap.
-
- ts_prios = 32
- };
-
- private:
- ulong bitmap[rt_prios / sizeof(ulong)];
- Util::List rt_runqueue[rt_prios];
-
- u32 ts_bitmap, ts_depleted_bitmap;
- int last_replenish;
-
- Util::List ts_runqueue[ts_prios];
- Util::List ts_depleted[ts_prios];
-
- Lock::SpinLock runqueue_lock;
-
- void schedule_nolock();
- Thread *best_rt(int prio);
- Thread *best_ts();
-
- void replenish_prio(int prio);
- void replenish_all();
-
- static u32 prio_to_slice(int prio);
- static int slice_to_prio(u32 slice);
-
- Time::KTimerEntry resched_timer;
-
- public:
- Util::List threadlist;
-
- // FIXME: use sleeping lock once implemented
- Lock::SpinLock threadlist_lock;
-
- typedef void (*thread_func)(void *arg);
-
- Thread *new_thread(thread_func func, void *arg, char *name = NULL);
- void schedule();
- void sched_new_thread();
-
- void init();
-
- friend class Thread;
- friend class WaitQueue;
- };
-
- extern Sched sched;
-
- struct Blocker {
- Util::List list_node;
- bool blocked;
-
- // Besides the obvious use by ThreadBlocker, this is used in
- // CascadeBlocker by WaitQueue both for prioritization of wakeups
- // and for calling wake_nolock().
-
- Thread *thread;
-
- Blocker()
- {
- blocked = true;
- }
-
- virtual ~Blocker()
- {
- }
-
- virtual void wake() = 0;
-
- // Like wake, but doesn't wake the thread -- used by WaitQueue
- // which calls thread->wake_nolock itself.
-
- virtual void unblock() = 0;
- };
-
- // This is a basic one-thread blocker; all blocked threads must
- // use one of these.
-
- struct ThreadBlocker : public Blocker {
- ThreadBlocker()
- {
- }
-
- ThreadBlocker(Thread *THREAD)
- {
- thread = THREAD;
- }
-
- void wake();
- void unblock();
- };
-
- // A thread that needs to block on more than one blocker can create
- // multiple CascadeBlockers all pointing to the same ThreadBlocker.
- // The thread wakes when any of the cascades has been woken.
-
- struct CascadeBlocker : public Blocker {
- CascadeBlocker()
- {
- }
-
- CascadeBlocker(Blocker *BLOCKER)
- {
- blocker = BLOCKER;
- thread = blocker->thread;
- }
-
- Blocker *blocker;
- void wake();
- void unblock();
- };
-
- // Waitqueues are queues of Blockers that can be woken up either one
- // at a time in priority order or all at once, at the waker's option.
- // Unlike Blockers, waitqueues do not have a blocked field; blocking
- // threads must check for completion after adding themselves to the
- // wait queue. When a blocker is woken, it is removed from the waitqueue.
-
- class WaitQueue {
- Util::List blockers;
- Lock::SpinLock lock;
-
- Blocker *unblock_one_nolock();
-
- public:
- void block(Blocker *blocker);
- void unblock(Blocker *blocker);
-
- bool empty();
-
- // Returns true if a task was successfully woken
- bool wake_one();
-
- // Returns the number of tasks successfully woken
- int wake_all();
-
- // Like wake_one, but return the thread instead of waking it.
- Blocker *unblock_one();
- };
-