schedule.cc

   1 #include <string.h>
   2 #include <stdlib.h>
   3
   4 #include "threads-model.h"
   5 #include "schedule.h"
   6 #include "common.h"
   7 #include "model.h"
   8 #include "nodestack.h"
   9 #include "execution.h"
  10
  11 /**
  12  * Format an "enabled_type_t" for printing
  13  * @param e The type to format
  14  * @param str The output character array
  15  */
  16 void enabled_type_to_string(enabled_type_t e, char *str)
  17 {
  18         const char *res;
  19         switch (e) {
  20         case THREAD_DISABLED:
  21                 res = "disabled";
  22                 break;
  23         case THREAD_ENABLED:
  24                 res = "enabled";
  25                 break;
  26         case THREAD_SLEEP_SET:
  27                 res = "sleep";
  28                 break;
  29         default:
  30                 ASSERT(0);
  31                 res = NULL;
  32                 break;
  33         }
  34         strcpy(str, res);
  35 }
  36
  37 /** Constructor */
  38 Scheduler::Scheduler() :
  39         execution(NULL),
  40         enabled(NULL),
  41         enabled_len(0),
  42         curr_thread_index(0),
  43         current(NULL)
  44 {
  45 }
  46
  47 /**
  48  * @brief Register the ModelExecution engine
  49  * @param execution The ModelExecution which is controlling execution
  50  */
  51 void Scheduler::register_engine(ModelExecution *execution)
  52 {
  53         this->execution = execution;
  54 }
  55
  56 void Scheduler::set_enabled(Thread *t, enabled_type_t enabled_status) {
  57         int threadid = id_to_int(t->get_id());
  58         if (threadid >= enabled_len) {
  59                 enabled_type_t *new_enabled = (enabled_type_t *)snapshot_malloc(sizeof(enabled_type_t) * (threadid + 1));
  60                 memset(&new_enabled[enabled_len], 0, (threadid + 1 - enabled_len) * sizeof(enabled_type_t));
  61                 if (enabled != NULL) {
  62                         memcpy(new_enabled, enabled, enabled_len * sizeof(enabled_type_t));
  63                         snapshot_free(enabled);
  64                 }
  65                 enabled = new_enabled;
  66                 enabled_len = threadid + 1;
  67         }
  68         enabled[threadid] = enabled_status;
  69 }
  70
  71 /**
  72  * @brief Check if a Thread is currently enabled
  73  *
  74  * Check if a Thread is currently enabled. "Enabled" includes both
  75  * THREAD_ENABLED and THREAD_SLEEP_SET.
  76  * @param t The Thread to check
  77  * @return True if the Thread is currently enabled
  78  */
  79 bool Scheduler::is_enabled(const Thread *t) const
  80 {
  81         return is_enabled(t->get_id());
  82 }
  83
  84 /**
  85  * @brief Check if a Thread is currently enabled
  86  *
  87  * Check if a Thread is currently enabled. "Enabled" includes both
  88  * THREAD_ENABLED and THREAD_SLEEP_SET.
  89  * @param tid The ID of the Thread to check
  90  * @return True if the Thread is currently enabled
  91  */
  92 bool Scheduler::is_enabled(thread_id_t tid) const
  93 {
  94         int i = id_to_int(tid);
  95         return (i >= enabled_len) ? false : (enabled[i] != THREAD_DISABLED);
  96 }
  97
  98 /**
  99  * @brief Check if a Thread is currently in the sleep set
 100  * @param t The Thread to check
 101  * @return True if the Thread is currently enabled
 102  */
 103 bool Scheduler::is_sleep_set(const Thread *t) const
 104 {
 105         return get_enabled(t) == THREAD_SLEEP_SET;
 106 }
 107
 108 /**
 109  * @brief Check if execution is stuck with no enabled threads and some sleeping
 110  * thread
 111  * @return True if no threads are enabled an some thread is in the sleep set;
 112  * false otherwise
 113  */
 114 bool Scheduler::all_threads_sleeping() const
 115 {
 116         bool sleeping = false;
 117         for (int i = 0; i < enabled_len; i++)
 118                 if (enabled[i] == THREAD_ENABLED)
 119                         return false;
 120                 else if (enabled[i] == THREAD_SLEEP_SET)
 121                         sleeping = true;
 122         return sleeping;
 123 }
 124
 125 enabled_type_t Scheduler::get_enabled(const Thread *t) const
 126 {
 127         int id = id_to_int(t->get_id());
 128         ASSERT(id < enabled_len);
 129         return enabled[id];
 130 }
 131
 132 void Scheduler::update_sleep_set(Node *n) {
 133         enabled_type_t *enabled_array = n->get_enabled_array();
 134         for (int i = 0; i < enabled_len; i++) {
 135                 if (enabled_array[i] == THREAD_SLEEP_SET) {
 136                         enabled[i] = THREAD_SLEEP_SET;
 137                 }
 138         }
 139 }
 140
 141 /**
 142  * Add a Thread to the sleep set.
 143  * @param t The Thread to add
 144  */
 145 void Scheduler::add_sleep(Thread *t)
 146 {
 147         DEBUG("thread %d\n", id_to_int(t->get_id()));
 148         set_enabled(t, THREAD_SLEEP_SET);
 149 }
 150
 151 /**
 152  * Remove a Thread from the sleep set.
 153  * @param t The Thread to remove
 154  */
 155 void Scheduler::remove_sleep(Thread *t)
 156 {
 157         DEBUG("thread %d\n", id_to_int(t->get_id()));
 158         set_enabled(t, THREAD_ENABLED);
 159 }
 160
 161 /**
 162  * Add a Thread to the scheduler's ready list.
 163  * @param t The Thread to add
 164  */
 165 void Scheduler::add_thread(Thread *t)
 166 {
 167         DEBUG("thread %d\n", id_to_int(t->get_id()));
 168         ASSERT(!t->is_model_thread());
 169         set_enabled(t, THREAD_ENABLED);
 170 }
 171
 172 /**
 173  * Remove a given Thread from the scheduler.
 174  * @param t The Thread to remove
 175  */
 176 void Scheduler::remove_thread(Thread *t)
 177 {
 178         if (current == t)
 179                 current = NULL;
 180         set_enabled(t, THREAD_DISABLED);
 181 }
 182
 183 /**
 184  * Prevent a Thread from being scheduled. The sleeping Thread should be
 185  * re-awoken via Scheduler::wake.
 186  * @param thread The Thread that should sleep
 187  */
 188 void Scheduler::sleep(Thread *t)
 189 {
 190         set_enabled(t, THREAD_DISABLED);
 191         t->set_state(THREAD_BLOCKED);
 192 }
 193
 194 /**
 195  * Wake a Thread up that was previously waiting (see Scheduler::wait)
 196  * @param t The Thread to wake up
 197  */
 198 void Scheduler::wake(Thread *t)
 199 {
 200         ASSERT(!t->is_model_thread());
 201         set_enabled(t, THREAD_ENABLED);
 202         t->set_state(THREAD_READY);
 203 }
 204
 205 /**
 206  * @brief Select a Thread to run via round-robin
 207  *
 208  * @param n The current Node, holding priority information for the next thread
 209  * selection
 210  *
 211  * @return The next Thread to run
 212  */
 213 Thread * Scheduler::select_next_thread(Node *n)
 214 {
 215         bool have_enabled_thread_with_priority = false;
 216         if (model->params.fairwindow != 0) {
 217                 for (int i = 0; i < enabled_len; i++) {
 218                         thread_id_t tid = int_to_id(i);
 219                         if (n->has_priority(tid)) {
 220                                 DEBUG("Node (tid %d) has priority\n", i);
 221                                 if (enabled[i] != THREAD_DISABLED)
 222                                         have_enabled_thread_with_priority = true;
 223                         }
 224                 }
 225         }
 226
 227         int avail_threads = enabled_len;        // number of available threads
 228         int thread_list[enabled_len];   // keep a list of threads to select from
 229         for (int i = 0; i< enabled_len; i++){
 230                 thread_list[i] = i;
 231         }
 232
 233         while (avail_threads > 0) {
 234                 int random_index = rand() % avail_threads;
 235                 curr_thread_index = thread_list[random_index];  // randomly select a thread from available threads
 236
 237                 // curr_thread_index = (curr_thread_index + i + 1) % enabled_len;
 238                 thread_id_t curr_tid = int_to_id(curr_thread_index);
 239                 if (model->params.yieldon) {
 240                         bool bad_thread = false;
 241                         for (int j = 0; j < enabled_len; j++) {
 242                                 thread_id_t tother = int_to_id(j);
 243                                 if ((enabled[j] != THREAD_DISABLED) && n->has_priority_over(curr_tid, tother)) {
 244                                         bad_thread=true;
 245                                         break;
 246                                 }
 247                         }
 248                         if (bad_thread) {
 249                                 thread_list[random_index] = thread_list[avail_threads - 1]; // remove this threads from available threads
 250                                 avail_threads--;
 251
 252                                 continue;
 253                         }
 254                 }
 255
 256                 if (enabled[curr_thread_index] == THREAD_ENABLED &&
 257                                 (!have_enabled_thread_with_priority || n->has_priority(curr_tid))) {
 258                         return model->get_thread(curr_tid);
 259                 } else {        // remove this threads from available threads
 260                         thread_list[random_index] = thread_list[avail_threads - 1];
 261                         avail_threads--;
 262                 }
 263         }
 264
 265         /* No thread was enabled */
 266         return NULL;
 267 }
 268
 269 void Scheduler::set_scheduler_thread(thread_id_t tid) {
 270         curr_thread_index=id_to_int(tid);
 271 }
 272
 273 /**
 274  * @brief Set the current "running" Thread
 275  * @param t Thread to run
 276  */
 277 void Scheduler::set_current_thread(Thread *t)
 278 {
 279         ASSERT(!t || !t->is_model_thread());
 280
 281         current = t;
 282         if (DBG_ENABLED())
 283                 print();
 284 }
 285
 286 /**
 287  * @return The currently-running Thread
 288  */
 289 Thread * Scheduler::get_current_thread() const
 290 {
 291         ASSERT(!current || !current->is_model_thread());
 292         return current;
 293 }
 294
 295 /**
 296  * Print debugging information about the current state of the scheduler. Only
 297  * prints something if debugging is enabled.
 298  */
 299 void Scheduler::print() const
 300 {
 301         int curr_id = current ? id_to_int(current->get_id()) : -1;
 302
 303         model_print("Scheduler: ");
 304         for (int i = 0; i < enabled_len; i++) {
 305                 char str[20];
 306                 enabled_type_to_string(enabled[i], str);
 307                 model_print("[%i: %s%s]", i, i == curr_id ? "current, " : "", str);
 308         }
 309         model_print("\n");
 310 }