From b7590870cfd909baca7b5dc1d954e233ec92092e Mon Sep 17 00:00:00 2001 From: Christian Cunningham Date: Wed, 16 Mar 2022 12:46:30 -0700 Subject: List Schedule --- include/globals.h | 1 + include/sys/schedule.h | 17 +-- linker.ld | 10 +- src/cpu/irq.c | 1 + src/globals.c | 1 + src/sys/schedule.c | 283 +++++++++++++++++++++++++------------------------ 6 files changed, 164 insertions(+), 149 deletions(-) diff --git a/include/globals.h b/include/globals.h index 249ffe7..ce98c97 100644 --- a/include/globals.h +++ b/include/globals.h @@ -17,6 +17,7 @@ extern struct Thread usrloopthread; extern unsigned int gwidth, gheight, gpitch, gisrgb; extern unsigned char thread_table[MAX_THREADS]; extern struct Thread threads[MAX_THREADS]; +extern struct ThreadEntry thread_entries[MAX_THREADS]; extern unsigned long mutex_table[MAX_MUTEXS]; extern struct Mutex mutexs[MAX_MUTEXS]; #endif diff --git a/include/sys/schedule.h b/include/sys/schedule.h index 3015e98..a6e03a9 100644 --- a/include/sys/schedule.h +++ b/include/sys/schedule.h @@ -13,6 +13,12 @@ enum ThreadStatus { THREAD_SWAIT = 2, }; +enum EntryTypes { + THREAD_ENTRY = 0, + START_ENTRY = 1, + END_ENTRY = 2, +}; + struct Thread { void* pc; void* sp; // Store r0-r12,lr on stack @@ -31,18 +37,13 @@ struct Thread { struct ThreadEntry { struct Thread* thread; - struct ThreadEntry* prev; struct ThreadEntry* next; -}; - -struct ThreadEntryIterator { - struct ThreadEntry* entry; + unsigned long entry_type; }; struct ThreadQueue { - struct ThreadEntry entry[TQUEUE_MAX]; - struct ThreadEntryIterator read; - struct ThreadEntryIterator write; + struct ThreadEntry start; + struct ThreadEntry end; }; struct Scheduler { diff --git a/linker.ld b/linker.ld index e12ab5c..8e6bcc4 100644 --- a/linker.ld +++ b/linker.ld @@ -34,13 +34,15 @@ SECTIONS . = ALIGN(4096); KEEP(*(.bss.kmem)) . = ALIGN(4096); - KEEP(*(.bss.threadl")) + KEEP(*(.bss.threadl)) . = ALIGN(4096); - KEEP(*(.bss.threads")) + KEEP(*(.bss.threads)) . = ALIGN(4096); - KEEP(*(.bss.mutexl")) + KEEP(*(.bss.threade)) . = ALIGN(4096); - KEEP(*(.bss.mutexs")) + KEEP(*(.bss.mutexl)) + . = ALIGN(4096); + KEEP(*(.bss.mutexs)) . = ALIGN(4096); *(.bss) *(.bss.*) diff --git a/src/cpu/irq.c b/src/cpu/irq.c index 4947844..80ca7dd 100644 --- a/src/cpu/irq.c +++ b/src/cpu/irq.c @@ -33,6 +33,7 @@ void c_irq_handler(void) // Handle the recieved data // Ctrl+T to toggle timer if(data == 0x14) { + uart_scheduler(); unsigned long timer_status; asm volatile("mrc p15, 0, %0, c14, c3, 1" : "=r"(timer_status)); if(timer_status == 0) { diff --git a/src/globals.c b/src/globals.c index c704cb4..37853cd 100644 --- a/src/globals.c +++ b/src/globals.c @@ -26,3 +26,4 @@ __attribute__((section(".bss.mutexs"))) struct Mutex mutexs[MAX_MUTEXS]; // 4+ - Reserved __attribute__((section(".bss.threadl"))) unsigned char thread_table[MAX_THREADS]; __attribute__((section(".bss.threads"))) struct Thread threads[MAX_THREADS]; +__attribute__((section(".bss.threade"))) struct ThreadEntry thread_entries[MAX_THREADS]; diff --git a/src/sys/schedule.c b/src/sys/schedule.c index fe919e6..4366b1a 100644 --- a/src/sys/schedule.c +++ b/src/sys/schedule.c @@ -25,38 +25,27 @@ void init_scheduler(void) // Initialize Scheduling Queues for (unsigned long p = 0; p < PRIORITIES; p++) { - for (unsigned long t = 0; t < TQUEUE_MAX; t++) { - /// Ready Queue - scheduler.ready[p].entry[t].thread = 0; - if (t == 0) - scheduler.ready[p].entry[t].prev = &scheduler.ready[p].entry[TQUEUE_MAX-1]; - else - scheduler.ready[p].entry[t].prev = &scheduler.ready[p].entry[(t-1)%TQUEUE_MAX]; - scheduler.ready[p].entry[t].next = &scheduler.ready[p].entry[(t+1)%TQUEUE_MAX]; - /// Mutex Wait Queue - scheduler.mwait[p].entry[t].thread = 0; - if (t == 0) - scheduler.mwait[p].entry[t].prev = &scheduler.mwait[p].entry[TQUEUE_MAX-1]; - else - scheduler.mwait[p].entry[t].prev = &scheduler.mwait[p].entry[(t-1)%TQUEUE_MAX]; - scheduler.mwait[p].entry[t].next = &scheduler.mwait[p].entry[(t+1)%TQUEUE_MAX]; - /// Signal Wait Queue - scheduler.swait[p].entry[t].thread = 0; - if (t == 0) - scheduler.swait[p].entry[t].prev = &scheduler.swait[p].entry[TQUEUE_MAX-1]; - else - scheduler.swait[p].entry[t].prev = &scheduler.swait[p].entry[(t-1)%TQUEUE_MAX]; - scheduler.swait[p].entry[t].next = &scheduler.swait[p].entry[(t+1)%TQUEUE_MAX]; - } - // Ready Queue - scheduler.ready[p].read.entry = &scheduler.ready[p].entry[0]; - scheduler.ready[p].write.entry = &scheduler.ready[p].entry[0]; - // Mutex Wait Queue - scheduler.mwait[p].read.entry = &scheduler.mwait[p].entry[0]; - scheduler.mwait[p].write.entry = &scheduler.mwait[p].entry[0]; - // Signal Wait Queue - scheduler.swait[p].read.entry = &scheduler.swait[p].entry[0]; - scheduler.swait[p].write.entry = &scheduler.swait[p].entry[0]; + // Ready Init + scheduler.ready[p].start.thread = 0; + scheduler.ready[p].start.next = &scheduler.ready[p].end; + scheduler.ready[p].start.entry_type = START_ENTRY; + scheduler.ready[p].end.thread = 0; + scheduler.ready[p].end.next = &scheduler.ready[p].start; + scheduler.ready[p].end.entry_type = END_ENTRY; + // Mutex Wait Init + scheduler.mwait[p].start.thread = 0; + scheduler.mwait[p].start.next = &scheduler.mwait[p].end; + scheduler.mwait[p].start.entry_type = START_ENTRY; + scheduler.mwait[p].end.thread = 0; + scheduler.mwait[p].end.next = &scheduler.mwait[p].start; + scheduler.mwait[p].end.entry_type = END_ENTRY; + // Signal Wait Init + scheduler.swait[p].start.thread = 0; + scheduler.swait[p].start.next = &scheduler.swait[p].end; + scheduler.swait[p].start.entry_type = START_ENTRY; + scheduler.swait[p].end.thread = 0; + scheduler.swait[p].end.next = &scheduler.swait[p].start; + scheduler.swait[p].end.entry_type = END_ENTRY; } // Initialize nextpid @@ -67,7 +56,13 @@ void init_scheduler(void) struct Thread* t = &threads[i]; t->offset = i; t->sp_base = 0x20000000 - STACK_SIZE*i; + // Clear the stack use thread_table[i] = 0; + struct ThreadEntry* te = &thread_entries[i]; + te->thread = t; + // Initialize To No Next Entry Initially + te->next = 0; + te->entry_type = THREAD_ENTRY; } } @@ -83,7 +78,12 @@ struct Thread* get_unused_thread(void) unsigned char add_thread(void* pc, void* arg, unsigned char priority) { struct Thread* thread = get_unused_thread(); + // The only point-of-failure is not having a thread available + if (thread == 0) + return 1; + /// Mark the Stack Space as In-Use thread_table[thread->offset] = 1; + /// Thread Setup thread->pc = pc; unsigned long* argp = (void*)thread->sp_base; argp -= 13; @@ -107,21 +107,16 @@ unsigned char add_thread(void* pc, void* arg, unsigned char priority) thread->old_priority = -1; // Reserved for non-preemptible tasking thread->preempt = 0; + /// Add Thread to Scheduler // Get the Ready Queue struct ThreadQueue* ready_queue = &scheduler.ready[thread->priority]; - // Get the write pointer - struct ThreadEntryIterator* ready_write = &ready_queue->write; - if (ready_write->entry->thread == 0) { - // Add the thread to the write pointer - ready_write->entry->thread = thread; - // Move the write pointer to the next entry - ready_write->entry = ready_write->entry->next; - } else { - // Cannot add, mark the stack space as available - // so that it can be used on a subsequent add thread - thread_table[thread->offset] = 0; - return 1; - } + // Get thread's entry + struct ThreadEntry* new_t_entry = &thread_entries[thread->offset]; + // Append to the end of the thread + ready_queue->end.next->next = new_t_entry; + ready_queue->end.next = new_t_entry; + // Link thread's next entry to end of queue + new_t_entry->next = &ready_queue->end; // Schedule if this was called in usermode unsigned long mode = getmode() & 0x1F; if (mode == 0x10) { @@ -140,36 +135,37 @@ void uart_scheduler(void) uart_string("Priority "); uart_10(p); uart_char('\n'); - struct ThreadEntryIterator iter; + struct ThreadQueue* queue; + struct ThreadEntry* entry; - struct ThreadQueue* rq = &scheduler.ready[p]; + queue = &scheduler.ready[p]; uart_string("Ready Queue\n"); - iter.entry = rq->read.entry; - while (iter.entry != rq->write.entry) { - uart_hex((unsigned long)iter.entry->thread); + entry = queue->start.next; + while (entry->entry_type != END_ENTRY) { + uart_hex((unsigned long)entry->thread); uart_char(' '); - kmemshow32((void*)iter.entry->thread, 9); - iter.entry = iter.entry->next; + kmemshow32((void*)entry->thread, 9); + entry = entry->next; } - struct ThreadQueue* mq = &scheduler.mwait[p]; + queue = &scheduler.mwait[p]; uart_string("Mutex Wait Queue\n"); - iter.entry = mq->read.entry; - while (iter.entry != mq->write.entry) { - uart_hex((unsigned long)iter.entry->thread); + entry = queue->start.next; + while (entry->entry_type != END_ENTRY) { + uart_hex((unsigned long)entry->thread); uart_char(' '); - kmemshow32((void*)iter.entry->thread, 9); - iter.entry = iter.entry->next; + kmemshow32((void*)entry->thread, 9); + entry = entry->next; } - struct ThreadQueue* sq = &scheduler.swait[p]; + queue = &scheduler.swait[p]; uart_string("Signal Wait Queue\n"); - iter.entry = sq->read.entry; - while (iter.entry != sq->write.entry) { - uart_hex((unsigned long)iter.entry->thread); + entry = queue->start.next; + while (entry->entry_type != END_ENTRY) { + uart_hex((unsigned long)entry->thread); uart_char(' '); - kmemshow32((void*)iter.entry->thread, 9); - iter.entry = iter.entry->next; + kmemshow32((void*)entry->thread, 9); + entry = entry->next; } } uart_string("==============\n"); @@ -180,9 +176,9 @@ struct Thread* next_thread(void) // Recurse through all priorities to try to find a ready thread for (int p = 0; p < PRIORITIES; p++) { struct ThreadQueue* rq = &scheduler.ready[p]; - if (rq->read.entry == rq->write.entry) + if (rq->start.next->entry_type == END_ENTRY) continue; - return rq->read.entry->thread; + return rq->start.next->thread; } // No thread found, use basic usrloopthread while waiting for new thread return &usrloopthread; @@ -191,11 +187,14 @@ struct Thread* next_thread(void) void c_cleanup(void) { struct Thread* rt = scheduler.rthread; - struct ThreadEntryIterator* read = &scheduler.ready[rt->priority].read; - // Clear the thread pointer - read->entry->thread = 0; - // Move read pointer forward - read->entry = read->entry->next; + struct ThreadEntry* rte = &thread_entries[rt->offset]; + struct ThreadQueue* queue = &scheduler.ready[rt->priority]; + // Move head forward + queue->start.next = rte->next; + if (rte->next->entry_type == END_ENTRY) + rte->next->next = &queue->start; + // Clear thread entry's next + rte->next = 0; // Mark Thread Unused thread_table[rt->offset] = 0; } @@ -210,14 +209,22 @@ void yield(void) // thus any threads of the same priority can be run first unsigned char priority = rthread->priority; struct ThreadQueue* trq = &scheduler.ready[priority]; - trq->read.entry = trq->read.entry->next; - trq->write.entry->thread = rthread; - trq->write.entry = trq->write.entry->next; + struct ThreadEntry* te = &thread_entries[rthread->offset]; + // Move head forward + trq->start.next = te->next; + if (te->next->entry_type == END_ENTRY) + te->next->next = &trq->start; + // Add to tail + trq->end.next->next = te; + trq->end.next = te; + te->next = &trq->end; } +// TODO: Figure out why two things are appearing in the wait queue by the end of this void sched_mutex_yield(void* m) { struct Thread* rthread = scheduler.rthread; + struct ThreadEntry* rthread_e = &thread_entries[rthread->offset]; // usrloopthread should not be yielded if (rthread == &usrloopthread) return; @@ -227,49 +234,48 @@ void sched_mutex_yield(void* m) struct ThreadQueue* trq = &scheduler.ready[priority]; struct ThreadQueue* tmq = &scheduler.mwait[priority]; // Move to next thread in the current thread priority's ready queue - trq->read.entry = trq->read.entry->next; + trq->start.next = trq->start.next->next; + if (trq->start.next->next->entry_type == END_ENTRY) + trq->end.next = &trq->start; // Add thread to waiting queue - tmq->write.entry->thread = rthread; - tmq->write.entry = tmq->write.entry->next; - // Find the thread with the mutex - struct ThreadEntryIterator iter; + tmq->end.next->next = rthread_e; + tmq->end.next = rthread_e; + rthread_e->next = &tmq->end; + /// Find the thread with the mutex // Search through each priority for (unsigned long p = 0; p < PRIORITIES; p++) { - struct ThreadQueue* rq = &scheduler.ready[p]; - iter = rq->read; - while (iter.entry != rq->write.entry) { + struct ThreadQueue* queue = &scheduler.ready[p]; + // Keep track of the previous entry + struct ThreadEntry* prev = &queue->start; + struct ThreadEntry* entry = prev->next; + while (entry->entry_type != END_ENTRY) { // Check if it is the Mutex's thread - if (iter.entry->thread->pid == ((struct Mutex*)m)->pid) { + if (entry->thread->pid == ((struct Mutex*)m)->pid) { + uart_scheduler(); // Promote the thread's priority - if (iter.entry->thread->priority > priority) { + if (entry->thread->priority > priority) { + struct ThreadQueue* new_queue = &scheduler.ready[priority]; // Add it to the higher priority queue - scheduler.ready[priority].write.entry->thread = iter.entry->thread; - // Move the Write Iterator Forward - scheduler.ready[priority].write.entry = scheduler.ready[priority].write.entry->next; + new_queue->end.next->next = entry; + new_queue->end.next = entry; // Set the old priority if not set - if (iter.entry->thread->old_priority == 0xFF) - iter.entry->thread->old_priority = p; - + if (entry->thread->old_priority == 0xFF) + entry->thread->old_priority = p; // Set the new priority - iter.entry->thread->priority = priority; - - // Prune the old priority entry - struct ThreadEntry* prev = iter.entry->prev; - struct ThreadEntry* next = iter.entry->next; - prev->next = next; - next->prev = prev; - // Put the newly freed entry at end of write queue - //iter.entry->prev = rq->write.entry; - //iter.entry->next = rq->write.entry->next; - if (iter.entry == rq->read.entry) - rq->read.entry = rq->read.entry->next; - rq->write.entry->next->prev = iter.entry; - rq->write.entry->next = iter.entry; - iter.entry->thread = 0; + entry->thread->priority = priority; + // Remove it from the lower priority queue + prev->next = entry->next; + if (entry->next->entry_type == END_ENTRY) { + entry->next->next = prev; + } + // Set the entry's next entry + entry->next = &new_queue->end; } return; } - iter.entry = iter.entry->next; + // Continue forward + prev = entry; + entry = entry->next; } } } @@ -278,44 +284,47 @@ void sched_mutex_resurrect(void* m) { // Look through each priority for (int p = 0; p < PRIORITIES; p++) { - struct ThreadQueue* tmq = &scheduler.mwait[p]; - struct ThreadEntryIterator iter; - iter = tmq->read; + struct ThreadQueue* wait_queue = &scheduler.mwait[p]; + struct ThreadEntry* prev = &wait_queue->start; + struct ThreadEntry* entry = prev->next; // Look through the lock wait queue - while (iter.entry != tmq->write.entry) { - // Check if the thread is waiting for the released mutex - if (iter.entry->thread->mptr == m) { - // Ressurect the thread - iter.entry->thread->mptr = 0; - scheduler.ready[iter.entry->thread->priority].write.entry->thread = iter.entry->thread; - scheduler.ready[iter.entry->thread->priority].write.entry = scheduler.ready[iter.entry->thread->priority].write.entry->next; - // Move the read pointer ahead - if (iter.entry == tmq->read.entry) - tmq->read.entry = tmq->read.entry->next; - iter.entry->prev->next = iter.entry->next; - iter.entry->next->prev = iter.entry->prev; - tmq->write.entry->next->prev = iter.entry; - tmq->write.entry->next = iter.entry; + while (entry->entry_type != END_ENTRY) { + // Check if the thread is waiting for the release mutex + if (entry->thread->mptr == m) { + // Resurrect the thread + entry->thread->mptr = 0; + struct ThreadEntry* end = &scheduler.ready[entry->thread->priority].end; + // Remove from old list + prev->next = entry->next; + if (entry->next->entry_type == END_ENTRY) { + prev->next->next = prev; + } + // Add to new list + end->next->next = entry; + end->next = entry; + entry->next = end; struct Thread* rthread = scheduler.rthread; - // Move the current thread to its old priority if it was promoted earlier + struct ThreadEntry* rthread_e = &thread_entries[rthread->offset]; + // Move current thread to old thread if applicable if (rthread->old_priority != 0xFF) { - struct ThreadQueue* cur_trq = &scheduler.ready[rthread->priority]; - struct ThreadQueue* old_trq = &scheduler.ready[rthread->old_priority]; - // Prune from the current ready queue - cur_trq->read.entry->thread = 0; - cur_trq->read.entry = cur_trq->read.entry->next; - // Prepend to original ready queue - old_trq->read.entry = old_trq->read.entry->prev; - old_trq->read.entry->thread = rthread; - // Reset Priority + struct ThreadQueue* cqueue = &scheduler.ready[rthread->priority]; + struct ThreadQueue* oqueue = &scheduler.ready[rthread->old_priority]; + // Move current queue up + cqueue->start.next = cqueue->start.next->next; + if (cqueue->start.next->next->entry_type == END_ENTRY) + cqueue->end.next = &cqueue->start; + // Add to old queue + oqueue->end.next->next = rthread_e; + oqueue->end.next = rthread_e; + rthread_e->next = &oqueue->end; + // Reset priority rthread->priority = rthread->old_priority; - rthread->old_priority = -1; + rthread->old_priority = 0xFF; } return; } - iter.entry = iter.entry->next; + prev = entry; + entry = entry->next; } } } - -// TODO: Check offsets -- cgit v1.2.1