From 41a7818b552aef9e6e0bf788089f6ae16ae1e421 Mon Sep 17 00:00:00 2001 From: Christian Cunningham Date: Fri, 26 Aug 2022 23:27:46 -0700 Subject: Mutex wait queues --- kernel/sys/schedule.c | 96 +++++++++++++++------------------------------------ 1 file changed, 27 insertions(+), 69 deletions(-) (limited to 'kernel/sys/schedule.c') 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; } -- cgit v1.2.1