aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/lib/queue.h17
-rw-r--r--include/util/mutex.h2
-rw-r--r--kernel/lib/queue.c43
-rw-r--r--kernel/sys/schedule.c96
-rw-r--r--kernel/util/mutex.c14
-rw-r--r--usr/test.c2
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
@@ -2,54 +2,23 @@
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)
generated by cgit v1.2.1 (git 2.18.0) at 2024-12-25 06:05:52 +0000