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