X-Git-Url: http://git.buserror.net/cgi-bin/gitweb.cgi?p=polintos%2Fscott%2Fpriv.git;a=blobdiff_plain;f=kernel%2Finclude%2Fkern%2Fsched.h;fp=kernel%2Finclude%2Fkern%2Fsched.h;h=5592063c1fd39fdd7c3d01e3f078490cdd30b056;hp=0000000000000000000000000000000000000000;hb=db11b9a38323d994d42303c6149c9e06ff29b7d2;hpb=cbad341e097fc2e24079b0626146baff8d71c877

diff --git a/kernel/include/kern/sched.h b/kernel/include/kern/sched.h
new file mode 100644
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