kernel/include/kern/thread.h

   1 #ifndef _KERN_THREAD_H
   2 #define _KERN_THREAD_H
   3
   4 #include <kern/types.h>
   5 #include <kern/time.h>
   6 #include <arch/thread.h>
   7 #include <util/list.h>
   8 #include <kern/irq.h>
   9 #include <kern/spinlock.h>
  10 #include <kern/orb.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 Mem {
  19         class ProcAddrSpace;
  20 }
  21
  22 namespace Threads {
  23         class Thread;
  24         class WaitQueue;
  25
  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.
  29         //
  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).
  37         //
  38         // At some sooner point, SMP support will need to be added.
  39
  40         class Sched {
  41         public:
  42                 enum {
  43                         // The default timeslice of 10 ms applies to priority 8
  44                         // timeshared tasks.
  45
  46                         default_timeslice = 10000000,
  47                         rt_prios = 256,
  48                         ts_static_prios = 16,
  49
  50                         // This must not exceed 32 without increasing the size
  51                         // of ts_bitmap.
  52
  53                         ts_prios = 32
  54                 };
  55
  56         private:
  57                 ulong bitmap[rt_prios / sizeof(ulong)];
  58                 Util::List rt_runqueue[rt_prios];
  59
  60                 u32 ts_bitmap, ts_depleted_bitmap;
  61                 int last_replenish;
  62
  63                 Util::List ts_runqueue[ts_prios];
  64                 Util::List ts_depleted[ts_prios];
  65
  66                 Lock::SpinLock runqueue_lock;
  67
  68                 void schedule_nolock();
  69                 Thread *best_rt(int prio);
  70                 Thread *best_ts();
  71
  72                 void replenish_prio(int prio);
  73                 void replenish_all();
  74
  75                 static u32 prio_to_slice(int prio);
  76                 static int slice_to_prio(u32 slice);
  77
  78                 Time::KTimerEntry resched_timer;
  79
  80         public:
  81                 Util::List threadlist;
  82
  83                 // FIXME: use sleeping lock once implemented
  84                 Lock::SpinLock threadlist_lock;
  85
  86                 typedef void (*thread_func)(void *arg);
  87
  88                 Thread *new_thread(thread_func func, void *arg, char *name = NULL);
  89                 void schedule();
  90                 void sched_new_thread();
  91
  92                 void init();
  93
  94                 friend class Thread;
  95                 friend class WaitQueue;
  96         };
  97
  98         extern Sched sched;
  99
 100         struct Blocker {
 101                 Util::List list_node;
 102                 bool blocked;
 103
 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().
 107
 108                 Thread *thread;
 109
 110                 Blocker()
 111                 {
 112                         blocked = true;
 113                 }
 114
 115                 virtual ~Blocker()
 116                 {
 117                 }
 118
 119                 virtual void wake() = 0;
 120
 121                 // Like wake, but doesn't wake the thread -- used by WaitQueue
 122                 // which calls thread->wake_nolock itself.
 123
 124                 virtual void unblock() = 0;
 125         };
 126
 127         // This is a basic one-thread blocker; all blocked threads must
 128         // use one of these.
 129
 130         struct ThreadBlocker : public Blocker {
 131                 ThreadBlocker()
 132                 {
 133                 }
 134
 135                 ThreadBlocker(Thread *THREAD)
 136                 {
 137                         thread = THREAD;
 138                 }
 139
 140                 void wake();
 141                 void unblock();
 142         };
 143
 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.
 147
 148         struct CascadeBlocker : public Blocker {
 149                 CascadeBlocker()
 150                 {
 151                 }
 152
 153                 CascadeBlocker(Blocker *BLOCKER)
 154                 {
 155                         blocker = BLOCKER;
 156                         thread = blocker->thread;
 157                 }
 158
 159                 Blocker *blocker;
 160                 void wake();
 161                 void unblock();
 162         };
 163
 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.
 169
 170         class WaitQueue {
 171                 Util::List blockers;
 172                 Lock::SpinLock lock;
 173
 174                 Blocker *unblock_one_nolock();
 175
 176         public:
 177                 void block(Blocker *blocker);
 178                 void unblock(Blocker *blocker);
 179
 180                 bool empty();
 181
 182                 // Returns true if a task was successfully woken
 183                 bool wake_one();
 184
 185                 // Returns the number of tasks successfully woken
 186                 int wake_all();
 187
 188                 // Like wake_one, but return the thread instead of waking it.
 189                 Blocker *unblock_one();
 190         };
 191
 192         class Thread {
 193                 // This must be first.
 194                 Arch::ArchThread arch;
 195
 196                 // If the thread is currently running, this contains the time of
 197                 // the context switch when the thread most recently started
 198                 // running.
 199
 200                 Time::Time last_time;
 201
 202                 // This contains the time in ns that the thread has remaining in
 203                 // its current timeslice.
 204
 205                 s32 time_left;
 206
 207                 // The current timeslice length in ns.  For timeshared tasks, this
 208                 // is simply the priority scaled linearly.
 209
 210                 u32 time_slice;
 211
 212                 // Real-time and timeshared priorities
 213                 //
 214                 // Real-time priorities go from 0 to 255, with 0 indicating a
 215                 // timeshared task.
 216                 //
 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
 223                 // [x,2x-1].
 224
 225                 int rt_prio, ts_static_prio, ts_prio, last_replenish;
 226
 227                 enum Policy {
 228                         TimeShared,
 229                         FIFO,
 230                         RoundRobin
 231                 } policy;
 232
 233                 ThreadBlocker *blocked_on;
 234                 Util::List runqueue_node;
 235
 236                 void ts_add();
 237                 void ts_del();
 238                 void ts_deplete();
 239
 240                 void add();
 241                 void del();
 242                 void replenish();
 243                 void charge(Time::Time &now);
 244                 void prio_adjust();
 245                 void wake_nolock();
 246
 247         public:
 248                 Util::List threadlist_node;
 249                 Mem::ProcAddrSpace *addr_space, *active_addr_space;
 250
 251                 enum {
 252                         name_len = 32
 253                 };
 254
 255                 char name[name_len];
 256
 257                 enum {
 258                         internal_orbstack_frames = 8
 259                 };
 260
 261                 ORB::CallStackHeader orbstack;
 262                 ORB::CallFrame orbstackframes[internal_orbstack_frames];
 263
 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.
 267
 268                 ORB::CallStackHeader *orbstack_top_hdr;
 269                 int orbstack_top; // Index into orbstack_top_hdr->frames[]
 270
 271                 ~Thread();
 272                 void exit();
 273                 void block(ThreadBlocker *blocker);
 274                 void wake();
 275
 276                 friend class Sched;
 277                 friend class WaitQueue;
 278
 279                 friend void Arch::switch_thread(Thread *dest, Thread *src);
 280
 281                 // FIXME: temp hack; use a Process later
 282
 283                 void set_aspace(Mem::ProcAddrSpace *aspace);
 284         };
 285
 286         enum {
 287                 thread_size = sizeof(Thread) + 7 / 8
 288         };
 289 }
 290
 291 #include <arch/current.h>
 292 #define curthread (::Arch::get_current_thread())
 293
 294 #endif