kernel/include/kern/sched.h

   1 #ifndef _KERN_SCHED_H
   2 #define _KERN_SCHED_H
   3
   4 #include <kern/types.h>
   5 #include <kern/time.h>
   6 #include <kern/spinlock.h>
   7
   8 #include <arch/thread.h>
   9
  10 #include <util/list.h>
  11
  12 extern "C" void schedule();
  13 extern "C" void sched_new_thread();
  14
  15 // FIXME: per-CPU
  16 extern int need_resched;
  17
  18 namespace Threads {
  19         class Thread;
  20         class WaitQueue;
  21
  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.
  25         //
  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).
  33         //
  34         // At some sooner point, SMP support will need to be added.
  35
  36         class Sched {
  37         public:
  38                 enum {
  39                         // The default timeslice of 10 ms applies to priority 8
  40                         // timeshared tasks.
  41
  42                         default_timeslice = 10000000,
  43                         rt_prios = 256,
  44                         ts_static_prios = 16,
  45
  46                         // This must not exceed 32 without increasing the size
  47                         // of ts_bitmap.
  48
  49                         ts_prios = 32
  50                 };
  51
  52         private:
  53                 ulong bitmap[rt_prios / sizeof(ulong)];
  54                 Util::List rt_runqueue[rt_prios];
  55
  56                 u32 ts_bitmap, ts_depleted_bitmap;
  57                 int last_replenish;
  58
  59                 Util::List ts_runqueue[ts_prios];
  60                 Util::List ts_depleted[ts_prios];
  61
  62                 Lock::SpinLock runqueue_lock;
  63
  64                 void schedule_nolock();
  65                 Thread *best_rt(int prio);
  66                 Thread *best_ts();
  67
  68                 void replenish_prio(int prio);
  69                 void replenish_all();
  70
  71                 static u32 prio_to_slice(int prio);
  72                 static int slice_to_prio(u32 slice);
  73
  74                 Time::KTimerEntry resched_timer;
  75
  76         public:
  77                 Util::List threadlist;
  78
  79                 // FIXME: use sleeping lock once implemented
  80                 Lock::SpinLock threadlist_lock;
  81
  82                 typedef void (*thread_func)(void *arg1, void *arg2);
  83
  84                 Thread *new_thread(thread_func func, void *arg1, void *arg2 = NULL,
  85                                    char *name = NULL);
  86                 void schedule();
  87                 void sched_new_thread();
  88
  89                 void init();
  90
  91                 friend class Thread;
  92                 friend class WaitQueue;
  93         };
  94
  95         extern Sched sched;
  96
  97         struct Blocker {
  98                 Util::List list_node;
  99                 bool blocked;
 100
 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().
 104
 105                 Thread *thread;
 106
 107                 Blocker()
 108                 {
 109                         blocked = true;
 110                 }
 111
 112                 virtual ~Blocker()
 113                 {
 114                 }
 115
 116                 virtual void wake() = 0;
 117
 118                 // Like wake, but doesn't wake the thread -- used by WaitQueue
 119                 // which calls thread->wake_nolock itself.
 120
 121                 virtual void unblock() = 0;
 122         };
 123
 124         // This is a basic one-thread blocker; all blocked threads must
 125         // use one of these.
 126
 127         struct ThreadBlocker : public Blocker {
 128                 ThreadBlocker()
 129                 {
 130                 }
 131
 132                 ThreadBlocker(Thread *THREAD)
 133                 {
 134                         thread = THREAD;
 135                 }
 136
 137                 void wake();
 138                 void unblock();
 139         };
 140
 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.
 144
 145         struct CascadeBlocker : public Blocker {
 146                 CascadeBlocker()
 147                 {
 148                 }
 149
 150                 CascadeBlocker(Blocker *BLOCKER)
 151                 {
 152                         blocker = BLOCKER;
 153                         thread = blocker->thread;
 154                 }
 155
 156                 Blocker *blocker;
 157                 void wake();
 158                 void unblock();
 159         };
 160
 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.
 166
 167         class WaitQueue {
 168                 Util::List blockers;
 169                 Lock::SpinLock lock;
 170
 171                 Blocker *unblock_one_nolock();
 172
 173         public:
 174                 void block(Blocker *blocker);
 175                 void unblock(Blocker *blocker);
 176
 177                 bool empty();
 178
 179                 // Returns true if a task was successfully woken
 180                 bool wake_one();
 181
 182                 // Returns the number of tasks successfully woken
 183                 int wake_all();
 184
 185                 // Like wake_one, but return the thread instead of waking it.
 186                 Blocker *unblock_one();
 187         };
 188 }
 189
 190 #endif