Untangle header file interdependencies.

[polintos/scott/priv.git] / kernel / include / kern / sched.h

diff --git a/kernel/include/kern/sched.h b/kernel/include/kern/sched.h
new file mode 100644 (file)
index 0000000..5592063
--- /dev/null
+++ b/kernel/include/kern/sched.h
@@ -0,0 +1,189 @@
+#ifndef _KERN_SCHED_H
+#define _KERN_SCHED_H
+
+#include <kern/types.h>
+#include <kern/time.h>
+#include <kern/spinlock.h>
+
+#include <arch/thread.h>
+
+#include <util/list.h>
+
+extern "C" void schedule();
+extern "C" void sched_new_thread();
+
+// FIXME: per-CPU
+extern int need_resched;
+
+namespace Threads {
+       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();
+       };
+}
+
+#endif