4 #include <kern/types.h>
6 #include <arch/thread.h>
9 #include <kern/spinlock.h>
12 extern "C" void schedule();
13 extern "C" void sched_new_thread();
16 extern int need_resched;
26 // This is a reasonably simple O(1) scheduler that provides both
27 // real-time and timeshared scheduling, with (non-rt) priority boosts
28 // for interactive tasks.
30 // At some point, it'd be nice to extend/replace this with something
31 // that gives more options to how to schedule tasks. Priority
32 // inheritance would be nice, as would the ability to schedule groups
33 // of threads as one prior to scheduling within the group. The latter
34 // would help avoid giving more CPU time to certain apps simply
35 // because they divided their work among more threads (or to certain
36 // users simply because they're running more programs).
38 // At some sooner point, SMP support will need to be added.
43 // The default timeslice of 10 ms applies to priority 8
46 default_timeslice = 10000000,
50 // This must not exceed 32 without increasing the size
57 ulong bitmap[rt_prios / sizeof(ulong)];
58 Util::List rt_runqueue[rt_prios];
60 u32 ts_bitmap, ts_depleted_bitmap;
63 Util::List ts_runqueue[ts_prios];
64 Util::List ts_depleted[ts_prios];
66 Lock::SpinLock runqueue_lock;
68 void schedule_nolock();
69 Thread *best_rt(int prio);
72 void replenish_prio(int prio);
75 static u32 prio_to_slice(int prio);
76 static int slice_to_prio(u32 slice);
78 Time::KTimerEntry resched_timer;
81 Util::List threadlist;
83 // FIXME: use sleeping lock once implemented
84 Lock::SpinLock threadlist_lock;
86 typedef void (*thread_func)(void *arg);
88 Thread *new_thread(thread_func func, void *arg, char *name = NULL);
90 void sched_new_thread();
95 friend class WaitQueue;
101 Util::List list_node;
104 // Besides the obvious use by ThreadBlocker, this is used in
105 // CascadeBlocker by WaitQueue both for prioritization of wakeups
106 // and for calling wake_nolock().
119 virtual void wake() = 0;
121 // Like wake, but doesn't wake the thread -- used by WaitQueue
122 // which calls thread->wake_nolock itself.
124 virtual void unblock() = 0;
127 // This is a basic one-thread blocker; all blocked threads must
130 struct ThreadBlocker : public Blocker {
135 ThreadBlocker(Thread *THREAD)
144 // A thread that needs to block on more than one blocker can create
145 // multiple CascadeBlockers all pointing to the same ThreadBlocker.
146 // The thread wakes when any of the cascades has been woken.
148 struct CascadeBlocker : public Blocker {
153 CascadeBlocker(Blocker *BLOCKER)
156 thread = blocker->thread;
164 // Waitqueues are queues of Blockers that can be woken up either one
165 // at a time in priority order or all at once, at the waker's option.
166 // Unlike Blockers, waitqueues do not have a blocked field; blocking
167 // threads must check for completion after adding themselves to the
168 // wait queue. When a blocker is woken, it is removed from the waitqueue.
174 Blocker *unblock_one_nolock();
177 void block(Blocker *blocker);
178 void unblock(Blocker *blocker);
182 // Returns true if a task was successfully woken
185 // Returns the number of tasks successfully woken
188 // Like wake_one, but return the thread instead of waking it.
189 Blocker *unblock_one();
193 // This must be first.
194 Arch::ArchThread arch;
196 // If the thread is currently running, this contains the time of
197 // the context switch when the thread most recently started
200 Time::Time last_time;
202 // This contains the time in ns that the thread has remaining in
203 // its current timeslice.
207 // The current timeslice length in ns. For timeshared tasks, this
208 // is simply the priority scaled linearly.
212 // Real-time and timeshared priorities
214 // Real-time priorities go from 0 to 255, with 0 indicating a
217 // Static timeshared priorities go from 1 to 16; they determine the
218 // timeslice of a task (not including interactivity bonuses). The
219 // default is 8. The dynamic timeshared priority is the priority
220 // associated with time_left as of the last global timeslice
221 // replenishment or wake-up, and ranges from 1 to 31. If the
222 // static priority is x, the dynamic priority is within the range
225 int rt_prio, ts_static_prio, ts_prio, last_replenish;
233 ThreadBlocker *blocked_on;
234 Util::List runqueue_node;
243 void charge(Time::Time &now);
248 Util::List threadlist_node;
249 Mem::AddrSpace *addr_space, *active_addr_space;
258 internal_orbstack_frames = 8
261 ORB::CallStackHeader orbstack;
262 ORB::CallFrame orbstackframes[internal_orbstack_frames];
264 // The header and frame of the method invocation at the top of
265 // the stack. FIXME: add a lock aronud these if other threads
266 // can read these to do a traceback/traceforward.
268 ORB::CallStackHeader *orbstack_top_hdr;
269 int orbstack_top; // Index into orbstack_top_hdr->frames[]
273 void block(ThreadBlocker *blocker);
277 friend class WaitQueue;
279 friend void Arch::switch_thread(Thread *dest, Thread *src);
281 // FIXME: temp hack; use a Process later
283 void set_aspace(Mem::AddrSpace *aspace);
287 thread_size = sizeof(Thread) + 7 / 8
291 #include <arch/current.h>
292 #define curthread (::Arch::get_current_thread())