1 #include <minix/mthread.h> 2 #include "global.h" 3 #include "proto.h" 4 5 /*===========================================================================* 6 * mthread_queue_add * 7 *===========================================================================*/ mthread_queue_add(queue,thread)8 void mthread_queue_add(queue, thread) 9 mthread_queue_t *queue; /* Queue we want thread to append to */ 10 mthread_thread_t thread; 11 { 12 /* Append a thread to the tail of the queue. As a process can be present on 13 * only one queue at the same time, we can use the threads array's 'next' 14 * pointer to point to the next thread on the queue. 15 */ 16 mthread_tcb_t *last; 17 18 if (!isokthreadid(thread)) 19 mthread_panic("Can't append invalid thread ID to a queue"); 20 21 last = mthread_find_tcb(thread); 22 23 if (mthread_queue_isempty(queue)) { 24 queue->mq_head = queue->mq_tail = last; 25 } else { 26 queue->mq_tail->m_next = last; 27 queue->mq_tail = last; /* 'last' is the new last in line */ 28 } 29 } 30 31 32 /*===========================================================================* 33 * mthread_queue_init * 34 *===========================================================================*/ mthread_queue_init(queue)35 void mthread_queue_init(queue) 36 mthread_queue_t *queue; /* Queue that has to be initialized */ 37 { 38 /* Initialize queue to a known state */ 39 40 queue->mq_head = queue->mq_tail = NULL; 41 } 42 43 44 /*===========================================================================* 45 * mthread_queue_isempty * 46 *===========================================================================*/ mthread_queue_isempty(queue)47 int mthread_queue_isempty(queue) 48 mthread_queue_t *queue; 49 { 50 return(queue->mq_head == NULL); 51 } 52 53 54 /*===========================================================================* 55 * mthread_dump_queue * 56 *===========================================================================*/ 57 #ifdef MDEBUG mthread_dump_queue(queue)58 void mthread_dump_queue(queue) 59 mthread_queue_t *queue; 60 { 61 int threshold, count = 0; 62 mthread_tcb_t *t; 63 mthread_thread_t tid; 64 threshold = no_threads; 65 printf("Dumping queue: "); 66 67 if(queue->mq_head != NULL) { 68 t = queue->mq_head; 69 if (t == &mainthread) tid = MAIN_THREAD; 70 else tid = t->m_tid; 71 printf("%d ", tid); 72 count++; 73 t = t->m_next; 74 while (t != NULL) { 75 if (t == &mainthread) tid = MAIN_THREAD; 76 else tid = t->m_tid; 77 printf("%d ", tid); 78 t = t->m_next; 79 count++; 80 if (count > threshold) break; 81 } 82 } else { 83 printf("[empty]"); 84 } 85 86 printf("\n"); 87 } 88 #endif 89 90 /*===========================================================================* 91 * mthread_queue_remove * 92 *===========================================================================*/ mthread_queue_remove(queue)93 mthread_thread_t mthread_queue_remove(queue) 94 mthread_queue_t *queue; /* Queue we want a thread from */ 95 { 96 /* Get the first thread in this queue, if there is one. */ 97 mthread_thread_t thread; 98 mthread_tcb_t *tcb, *random_tcb, *prev; 99 int count = 0, offset_id = 0, picked_random = 0; 100 101 tcb = queue->mq_head; 102 103 if (MTHREAD_RND_SCHED) { 104 /* Count items on queue */ 105 random_tcb = queue->mq_head; 106 if (random_tcb != NULL) { 107 do { 108 count++; 109 random_tcb = random_tcb->m_next; 110 } while (random_tcb != NULL); 111 } 112 113 if (count > 1) { 114 picked_random = 1; 115 116 /* Get random offset */ 117 offset_id = random() % count; 118 119 /* Find offset in queue */ 120 random_tcb = queue->mq_head; 121 prev = random_tcb; 122 while (--offset_id > 0) { 123 prev = random_tcb; 124 random_tcb = random_tcb->m_next; 125 } 126 127 /* Stitch head and tail together */ 128 prev->m_next = random_tcb->m_next; 129 130 /* Fix head and tail */ 131 if (queue->mq_head == random_tcb) 132 queue->mq_head = random_tcb->m_next; 133 if (queue->mq_tail == random_tcb) 134 queue->mq_tail = prev; 135 136 tcb = random_tcb; 137 } 138 } 139 140 /* Retrieve thread id from tcb */ 141 if (tcb == NULL) thread = NO_THREAD; 142 else if (tcb == &mainthread) thread = MAIN_THREAD; 143 else thread = (tcb->m_tid); 144 145 /* If we didn't pick a random thread and queue is not empty... */ 146 if (!picked_random && thread != NO_THREAD) { 147 tcb = queue->mq_head; 148 if (queue->mq_head == queue->mq_tail) { 149 /* Queue holds only one thread */ 150 queue->mq_head = queue->mq_tail = NULL; /* So mark thread empty */ 151 } else { 152 /* Second thread in line is the new first */ 153 queue->mq_head = queue->mq_head->m_next; 154 } 155 } 156 157 if (tcb != NULL) 158 tcb->m_next = NULL; /* This thread is no longer part of a queue */ 159 160 return(thread); 161 } 162 163