4 #include <kern/types.h>
6 #include <kern/spinlock.h>
8 #include <arch/thread.h>
10 #include <util/list.h>
12 extern "C" void schedule();
13 extern "C" void sched_new_thread();
16 extern int need_resched;
22 // This is a reasonably simple O(1) scheduler that provides both
23 // real-time and timeshared scheduling, with (non-rt) priority boosts
24 // for interactive tasks.
26 // At some point, it'd be nice to extend/replace this with something
27 // that gives more options to how to schedule tasks. Priority
28 // inheritance would be nice, as would the ability to schedule groups
29 // of threads as one prior to scheduling within the group. The latter
30 // would help avoid giving more CPU time to certain apps simply
31 // because they divided their work among more threads (or to certain
32 // users simply because they're running more programs).
34 // At some sooner point, SMP support will need to be added.
39 // The default timeslice of 10 ms applies to priority 8
42 default_timeslice = 10000000,
46 // This must not exceed 32 without increasing the size
53 ulong bitmap[rt_prios / sizeof(ulong)];
54 Util::List rt_runqueue[rt_prios];
56 u32 ts_bitmap, ts_depleted_bitmap;
59 Util::List ts_runqueue[ts_prios];
60 Util::List ts_depleted[ts_prios];
62 Lock::SpinLock runqueue_lock;
64 void schedule_nolock();
65 Thread *best_rt(int prio);
68 void replenish_prio(int prio);
71 static u32 prio_to_slice(int prio);
72 static int slice_to_prio(u32 slice);
74 Time::KTimerEntry resched_timer;
77 Util::List threadlist;
79 // FIXME: use sleeping lock once implemented
80 Lock::SpinLock threadlist_lock;
82 typedef void (*thread_func)(void *arg1, void *arg2);
84 Thread *new_thread(thread_func func, void *arg1, void *arg2 = NULL,
85 const char *name = NULL);
87 void sched_new_thread();
92 friend class WaitQueue;
101 // Besides the obvious use by ThreadBlocker, this is used in
102 // CascadeBlocker by WaitQueue both for prioritization of wakeups
103 // and for calling wake_nolock().
116 virtual void wake() = 0;
118 // Like wake, but doesn't wake the thread -- used by WaitQueue
119 // which calls thread->wake_nolock itself.
121 virtual void unblock() = 0;
124 // This is a basic one-thread blocker; all blocked threads must
127 struct ThreadBlocker : public Blocker {
132 ThreadBlocker(Thread *THREAD)
141 // A thread that needs to block on more than one blocker can create
142 // multiple CascadeBlockers all pointing to the same ThreadBlocker.
143 // The thread wakes when any of the cascades has been woken.
145 struct CascadeBlocker : public Blocker {
150 CascadeBlocker(Blocker *BLOCKER)
153 thread = blocker->thread;
161 // Waitqueues are queues of Blockers that can be woken up either one
162 // at a time in priority order or all at once, at the waker's option.
163 // Unlike Blockers, waitqueues do not have a blocked field; blocking
164 // threads must check for completion after adding themselves to the
165 // wait queue. When a blocker is woken, it is removed from the waitqueue.
171 Blocker *unblock_one_nolock();
174 void block(Blocker *blocker);
175 void unblock(Blocker *blocker);
179 // Returns true if a task was successfully woken
182 // Returns the number of tasks successfully woken
185 // Like wake_one, but return the thread instead of waking it.
186 Blocker *unblock_one();