Mutex wait queuesno-search

1 files changed, 27 insertions, 69 deletions

diff --git a/kernel/sys/schedule.c b/kernel/sys/schedule.c
index 142ffaf..c8dc581 100644
--- a/kernel/sys/schedule.c
+++ b/kernel/sys/schedule.c
@@ -8,6 +8,7 @@
 
 extern void kernel_usr_task_loop(void);
 
+/// Initialize the scheduler
 void init_scheduler(void)
 {
 	// Set rthread to usrloopthread - an infinitely running thread so that the pointer will never be null
@@ -27,26 +28,11 @@ void init_scheduler(void)
 	// Initialize Scheduling Queues
 	for (unsigned long p = 0; p < PRIORITIES; p++) {
 		// Ready Init
-		scheduler.ready[p].start.value = 0;
-		scheduler.ready[p].start.next = &scheduler.ready[p].end;
-		scheduler.ready[p].start.entry_type = START_ENTRY;
-		scheduler.ready[p].end.value = 0;
-		scheduler.ready[p].end.next = &scheduler.ready[p].start;
-		scheduler.ready[p].end.entry_type = END_ENTRY;
+		scheduler.ready[p].start.next = 0;
 		// Mutex Wait Init
-		scheduler.mwait[p].start.value = 0;
-		scheduler.mwait[p].start.next = &scheduler.mwait[p].end;
-		scheduler.mwait[p].start.entry_type = START_ENTRY;
-		scheduler.mwait[p].end.value = 0;
-		scheduler.mwait[p].end.next = &scheduler.mwait[p].start;
-		scheduler.mwait[p].end.entry_type = END_ENTRY;
+		scheduler.mwait[p].start.next = 0;
 		// Signal Wait Init
-		scheduler.swait[p].start.value = 0;
-		scheduler.swait[p].start.next = &scheduler.swait[p].end;
-		scheduler.swait[p].start.entry_type = START_ENTRY;
-		scheduler.swait[p].end.value = 0;
-		scheduler.swait[p].end.next = &scheduler.swait[p].start;
-		scheduler.swait[p].end.entry_type = END_ENTRY;
+		scheduler.swait[p].start.next = 0;
 	}
 
 	// Initialize nextpid
@@ -60,18 +46,13 @@ void init_scheduler(void)
 		t->highest_mutex = 0;
 		thread_entries[i].value = t;
 		thread_entries[i].next = &thread_entries[(i+1)];
-		thread_entries[i].entry_type = VALUE_ENTRY;
 	}
 	// Initialize the free queue
-	scheduler.free_threads.start.value = 0;
-	scheduler.free_threads.start.entry_type = START_ENTRY;
-	scheduler.free_threads.end.value = 0;
-	scheduler.free_threads.end.entry_type = END_ENTRY;
 	scheduler.free_threads.start.next = &thread_entries[0];
-	scheduler.free_threads.end.next = &thread_entries[MAX_THREADS-1];
-	thread_entries[MAX_THREADS-1].next = &scheduler.free_threads.end;
+	thread_entries[MAX_THREADS-1].next = 0;
 }
 
+/// Push the given thread to a given priority queue
 void push_thread_to_queue(struct Thread* t, unsigned char type, unsigned char priority)
 {
 	struct Entry* entry = &thread_entries[t->offset];
@@ -86,27 +67,9 @@ void push_thread_to_queue(struct Thread* t, unsigned char type, unsigned char pr
 		return;
 	}
 	push_to_queue(entry, queue);
-	//queue->end.next->next = entry;
-	//queue->end.next = entry;
-	//entry->next = &queue->end;
-}
-
-void prepend_thread_to_queue(struct Thread* t, unsigned char type, unsigned char priority)
-{
-	struct Entry* entry = &thread_entries[t->offset];
-	struct Queue* queue;
-	if (type == THREAD_READY) {
-		queue = &scheduler.ready[priority];
-	} else if (type == THREAD_MWAIT) {
-		queue = &scheduler.mwait[priority];
-	} else if (type == THREAD_SWAIT) {
-		queue = &scheduler.swait[priority];
-	} else {
-		return;
-	}
-	prepend_to_queue(entry, queue);
 }
 
+/// Get a thread from a queue
 struct Entry* pop_thread_from_queue(unsigned char type, unsigned char priority)
 {
 	struct Entry* entry = 0;
@@ -123,6 +86,7 @@ struct Entry* pop_thread_from_queue(unsigned char type, unsigned char priority)
 	return pop_from_queue(queue);
 }
 
+/// Find thread with pid
 struct Entry* find_pid(unsigned long pid)
 {
 	for (unsigned char p = 0; p < PRIORITIES; p++) {
@@ -133,7 +97,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.ready[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -143,7 +107,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.mwait[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -153,7 +117,7 @@ struct Entry* find_pid(unsigned long pid)
 		queue = &scheduler.swait[p];
 		prev = &queue->start;
 		entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pid == pid)
 				return prev;
 			prev = entry;
@@ -163,20 +127,14 @@ struct Entry* find_pid(unsigned long pid)
 	return 0;
 }
 
+/// Find the next thread waiting on this mutex
 struct Entry* find_mutex_wait_next(void* m)
 {
-	for (unsigned char p = 0; p < PRIORITIES; p++) {
-		struct Queue* queue = &scheduler.mwait[p];
-		struct Entry* prev = &queue->start;
-		struct Entry* entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
-			if (((struct Thread*)entry->value)->mptr == m)
-				return prev;
-			prev = entry;
-			entry = entry->next;
-		}
-	}
-	return 0;
+	unsigned long spacing = (unsigned long)&mutexs[1] - (unsigned long)&mutexs[0];
+	unsigned long difference = (unsigned long)m - (unsigned long)&mutexs[0];
+	unsigned long index = difference/spacing;
+	struct Entry* entry = mutexs[index].waiting_threads;
+	return entry;
 }
 
 struct Entry* find_signal_wait_next(void* s)
@@ -185,7 +143,7 @@ struct Entry* find_signal_wait_next(void* s)
 		struct Queue* queue = &scheduler.swait[p];
 		struct Entry* prev = &queue->start;
 		struct Entry* entry = prev->next;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->mptr == s)
 				return prev;
 			prev = entry;
@@ -200,7 +158,7 @@ struct Entry* get_unused_thread(void)
 	struct Queue* q = &scheduler.free_threads;
 	// If we have no available free threads
 	//  return null pointer
-	if (q->start.next->entry_type == END_ENTRY)
+	if (q->start.next == 0)
 		return 0;
 	// Otherwise, get the next thread
 	return pop_from_queue(q);
@@ -211,7 +169,7 @@ unsigned char find_duplicate(void* pc)
 	for (unsigned char p = 0; p < PRIORITIES; p++) {
 		struct Queue* queue = &scheduler.ready[p];
 		struct Entry* entry = queue->start.next;
-		while (entry->entry_type == VALUE_ENTRY) {
+		while (entry != 0) {
 			if (((struct Thread*)entry->value)->pc == pc) {
 				return 1;
 			}
@@ -282,7 +240,7 @@ void uart_scheduler(void)
 		uart_string("Ready Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -295,7 +253,7 @@ void uart_scheduler(void)
 		uart_string("Mutex Wait Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -308,7 +266,7 @@ void uart_scheduler(void)
 		uart_string("Signal Wait Queue\n");
 		entry = queue->start.next;
 		length = 0;
-		while (entry->entry_type != END_ENTRY) {
+		while (entry != 0) {
 			uart_hex((unsigned long)entry->value);
 			uart_char(' ');
 			kmemshow32((void*)entry->value, 9);
@@ -320,7 +278,7 @@ void uart_scheduler(void)
 	// Count number of free threads
 	struct Queue* queue = &scheduler.free_threads;
 	struct Entry* entry = queue->start.next;
-	while (entry->entry_type != END_ENTRY) {
+	while (entry != 0) {
 		entry = entry->next;
 		length++;
 	}
@@ -333,7 +291,7 @@ struct Thread* next_thread(void)
 	// Recurse through all priorities to try to find a ready thread
 	for (int p = 0; p < PRIORITIES; p++) {
 		struct Queue* rq = &scheduler.ready[p];
-		if (rq->start.next->entry_type == END_ENTRY)
+		if (rq->start.next == 0)
 			continue;
 		return rq->start.next->value;
 	}
@@ -384,7 +342,7 @@ void sched_mutex_yield(void* m)
 		push_thread_to_queue(rt->value, THREAD_MWAIT, priority);
 	// Find the thread that has the mutex locked
 	struct Mutex* mtex = m;
-	struct Entry* mutex_next = find_pid(mtex->pid);
+	struct Entry* mutex_next = mtex->locking_thread;
 	if (mutex_next == 0)
 		return;
 	// The next thread is the one with the lock
@@ -445,7 +403,7 @@ unsigned long sched_mutex_resurrect(void* m)
 		struct Entry* tentry = pop_thread_from_queue(THREAD_READY, p);
 		((struct Thread*)tentry->value)->priority = op;
 		((struct Thread*)tentry->value)->old_priority = 0xFF;
-		prepend_thread_to_queue(tentry->value, THREAD_READY, op);
+		push_thread_to_queue(tentry->value, THREAD_READY, op);
 	}
 	return 1;
 }