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 --- include/lib/queue.h | 17 ++------- include/util/mutex.h | 2 ++ kernel/lib/queue.c | 43 ++++------------------- kernel/sys/schedule.c | 96 +++++++++++++++------------------------------------ kernel/util/mutex.c | 14 ++++---- usr/test.c | 2 ++ 6 files changed, 45 insertions(+), 129 deletions(-) diff --git a/include/lib/queue.h b/include/lib/queue.h index 1d4899a..c6da6ed 100644 --- a/include/lib/queue.h +++ b/include/lib/queue.h @@ -1,33 +1,20 @@ #ifndef LIB_QUEUE_H #define LIB_QUEUE_H -enum EntryType { - VALUE_ENTRY = 0, - START_ENTRY = 1, - END_ENTRY = 2, -}; - struct Entry { void* value; struct Entry* next; - unsigned long entry_type; }; struct Queue { struct Entry start; - struct Entry end; }; -// Add to end of queue -void push_to_queue(struct Entry* e, struct Queue* q); // Add to beginning of queue -void prepend_to_queue(struct Entry* e, struct Queue* q); +void push_to_queue(struct Entry* e, struct Queue* q); // Remove from beginning of queue struct Entry* pop_from_queue(struct Queue* q); -// Remove the entry after this one from its queue +// Remove the next entry struct Entry* remove_next_from_queue(struct Entry* e); -// Find an entry in a queue -// Returns the entry before the target entry -struct Entry* find_value(void* value, struct Queue* q); #endif diff --git a/include/util/mutex.h b/include/util/mutex.h index cef4c60..da71146 100644 --- a/include/util/mutex.h +++ b/include/util/mutex.h @@ -16,6 +16,8 @@ struct Mutex { unsigned long pid; void* addr; + struct Entry* locking_thread; + struct Entry* waiting_threads; } __attribute__((packed, aligned(4))); struct MutexManager { diff --git a/kernel/lib/queue.c b/kernel/lib/queue.c index 1fc35f6..38ef8cf 100644 --- a/kernel/lib/queue.c +++ b/kernel/lib/queue.c @@ -1,55 +1,24 @@ #include void push_to_queue(struct Entry* e, struct Queue* q) -{ - q->end.next->next = e; - q->end.next = e; - e->next = &q->end; -} - -void prepend_to_queue(struct Entry* e, struct Queue* q) { e->next = q->start.next; q->start.next = e; - if (e->next->entry_type == END_ENTRY) - q->end.next = e; } struct Entry* pop_from_queue(struct Queue* q) { - if (q->start.next->entry_type == END_ENTRY) + if (q->start.next == 0) return 0; struct Entry* e = q->start.next; q->start.next = e->next; - if (e->next->entry_type == END_ENTRY) - q->end.next = &q->start; return e; } -struct Entry* remove_next_from_queue(struct Entry* e) -{ - struct Entry* prev = e; - struct Entry* remove = e->next; - struct Entry* next = remove->next; - if (remove->entry_type != VALUE_ENTRY) +struct Entry* remove_next_from_queue(struct Entry* e) { + if (e->next == 0) return 0; - prev->next = next; - if (next->entry_type == END_ENTRY) - next->next = prev; - return remove; -} - -struct Entry* find_value(void* value, struct Queue* q) -{ - struct Entry* prev; - struct Entry* entry; - prev = &q->start; - entry = prev->next; - while (entry->entry_type != END_ENTRY) { - if (entry->value == value) - return prev; - prev = entry; - entry = prev->next; - } - return 0; + struct Entry* next = e->next; + e->next = next->next; + return next; } 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; } diff --git a/kernel/util/mutex.c b/kernel/util/mutex.c index 997d85d..b05aee3 100644 --- a/kernel/util/mutex.c +++ b/kernel/util/mutex.c @@ -9,18 +9,14 @@ void mutex_init(void) for (unsigned long m = 0; m < MAX_MUTEXS; m++) { mutexs[m].pid = 0; mutexs[m].addr = 0; + mutexs[m].locking_thread = 0; + mutexs[m].waiting_threads = 0; mutex_entries[m].value = &mutexs[m]; - mutex_entries[m].entry_type = VALUE_ENTRY; mutex_entries[m].next = &mutex_entries[m+1]; } // Initialize Free Mutexs - mutex_manager.free.start.value = 0; mutex_manager.free.start.next = &mutex_entries[0]; - mutex_manager.free.start.entry_type = START_ENTRY; - mutex_manager.free.end.value = 0; - mutex_manager.free.end.next = &mutex_entries[MAX_MUTEXS-1]; - mutex_entries[MAX_MUTEXS-1].next = &mutex_manager.free.end; - mutex_manager.free.end.entry_type = END_ENTRY; + mutex_entries[MAX_MUTEXS-1].next = 0; } struct Mutex* create_mutex(void* addr) @@ -44,7 +40,8 @@ unsigned char delete_mutex(struct Mutex* m) return 1; struct Entry* entry = &mutex_entries[index]; // Add it to the free queue - prepend_to_queue(entry, &mutex_manager.free); + push_to_queue(entry, &mutex_manager.free); + mutex_manager.used_mutexes--; return 0; } @@ -67,6 +64,7 @@ unsigned char lock_mutex(struct Mutex* m) if ((unsigned char) index > rthread->highest_mutex) return 2; sys1(SYS_LOCK, m); + m->locking_thread = &mutex_entries[index]; return 0; } return 3; diff --git a/usr/test.c b/usr/test.c index b30fbba..3885113 100644 --- a/usr/test.c +++ b/usr/test.c @@ -193,6 +193,7 @@ void test_super(void) draw_string((8%TEST_PER_LINE)*15, 11+5*(8/TEST_PER_LINE), "Mutex Unlock"); add_thread(test_results,(void*) 8, 0);idx = 0; + /* static unsigned long semp = 0; for (unsigned long i = 0; i < MAX_ITER; i++) { semp = 1; @@ -212,6 +213,7 @@ void test_super(void) } draw_string((11%TEST_PER_LINE)*15, 11+5*(11/TEST_PER_LINE), "Semaphore V"); add_thread(test_results,(void*) 11, 0);idx = 0; + */ } void delaytest(void) -- cgit v1.2.1