From 8122c7760b4dba8c3b4f0f538eb6fa48d7026092 Mon Sep 17 00:00:00 2001 From: Brian Norris Date: Thu, 8 Mar 2012 23:36:48 -0800 Subject: [PATCH] schedule: add scheduler, thread_yield(), etc. Could use some cleanup still... --- Makefile | 4 +-- libthreads.c | 70 +++++++++++++++++++++++++++++++++++++++++++--------- libthreads.h | 1 + schedule.c | 56 +++++++++++++++++++++++++++++++++++++++++ schedule.h | 9 +++++++ 5 files changed, 127 insertions(+), 13 deletions(-) create mode 100644 schedule.c create mode 100644 schedule.h diff --git a/Makefile b/Makefile index becb998..49994ac 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ BIN=libthreads -SOURCE=libthreads.c -HEADERS=libthreads.h +SOURCE=libthreads.c schedule.c +HEADERS=libthreads.h schedule.h FLAGS= all: ${BIN} diff --git a/libthreads.c b/libthreads.c index 2326f3b..c69e45a 100644 --- a/libthreads.c +++ b/libthreads.c @@ -7,7 +7,7 @@ #define STACK_SIZE (1024 * 1024) -static struct thread *current; +static struct thread *current, *main_thread; static void *stack_allocate(size_t size) { @@ -32,7 +32,7 @@ static int create_context(struct thread *t) t->context.uc_stack.ss_sp = t->stack; t->context.uc_stack.ss_size = STACK_SIZE; t->context.uc_stack.ss_flags = 0; - t->context.uc_link = ¤t->context; + t->context.uc_link = &main_thread->context; makecontext(&t->context, t->start_routine, 1, t->arg); return 0; @@ -44,6 +44,45 @@ static int create_initial_thread(struct thread *t) return create_context(t); } +static int thread_swap(struct thread *old, struct thread *new) +{ + return swapcontext(&old->context, &new->context); +} + +static int thread_yield() +{ + struct thread *old, *next; + + DBG(); + if (current) { + old = current; + schedule_add_thread(old); + } else { + old = main_thread; + } + schedule_choose_next(&next); + current = next; + return thread_swap(old, next); +} + +static int master_thread_yield() +{ + struct thread *next; + + DBG(); + + if (current) { + DEBUG("completed thread %d\n", current->index); + current->completed = 1; + } + schedule_choose_next(&next); + if (next && !next->completed) { + current = next; + return thread_swap(main_thread, next); + } + return 1; +} + int thread_create(struct thread *t, void (*start_routine), void *arg) { static int created = 1; @@ -63,21 +102,26 @@ int thread_create(struct thread *t, void (*start_routine), void *arg) void thread_start(struct thread *t) { - struct thread *old = current; DBG(); - current = t; - swapcontext(&old->context, ¤t->context); + schedule_add_thread(t); +} - DBG(); +void thread_join(struct thread *t) +{ + while (!t->completed) + thread_yield(); } void a(int *idx) { int i; - for (i = 0; i < 10; i++) + for (i = 0; i < 10; i++) { printf("Thread %d, loop %d\n", *idx, i); + if (i % 2) + thread_yield(); + } } void user_main() @@ -91,20 +135,24 @@ void user_main() printf("%s() is going to start 1 thread\n", __func__); thread_start(&t1); thread_start(&t2); + + thread_join(&t1); + thread_join(&t2); printf("%s() is finished\n", __func__); } int main() { - struct thread main_thread, user_thread; + struct thread user_thread; - create_initial_thread(&main_thread); - current = &main_thread; + main_thread = malloc(sizeof(struct thread)); + create_initial_thread(main_thread); thread_create(&user_thread, &user_main, NULL); thread_start(&user_thread); - DBG(); + /* Wait for all threads to complete */ + while (master_thread_yield() == 0); DEBUG("Exiting\n"); return 0; diff --git a/libthreads.h b/libthreads.h index 1323cef..ff6d5aa 100644 --- a/libthreads.h +++ b/libthreads.h @@ -18,6 +18,7 @@ struct thread { ucontext_t context; void *stack; int index; + int completed; }; int thread_create(struct thread *t, void (*start_routine), void *arg); diff --git a/schedule.c b/schedule.c new file mode 100644 index 0000000..e940f5a --- /dev/null +++ b/schedule.c @@ -0,0 +1,56 @@ +//#define CONFIG_DEBUG + +#include "schedule.h" + +struct thread_list_node { + struct thread *this; + struct thread_list_node *next; + int live; +}; + +#define NUM_LIST_NODES 32 + +struct thread_list_node *head, *tail; +struct thread_list_node nodes[NUM_LIST_NODES]; + +static void enqueue_thread(struct thread *t) +{ + int i; + struct thread_list_node *node; + + for (node = nodes, i = 0; node->live && i < NUM_LIST_NODES; i++, node++); + if (i >= NUM_LIST_NODES) + printf("ran out of nodes\n"); + node->this = t; + node->next = NULL; + node->live = 1; + + if (tail) + tail->next = node; + else + head = node; + tail = node; +} + +static int dequeue_thread(struct thread **t) +{ + if (!head) + return -1; + *t = head->this; + head->live = 0; + if (head == tail) + tail = NULL; + head = head->next; + return 0; +} + +void schedule_add_thread(struct thread *t) +{ + DEBUG("%s: thread %d\n", __func__, t->index); + enqueue_thread(t); +} + +int schedule_choose_next(struct thread **t) +{ + return dequeue_thread(t); +} diff --git a/schedule.h b/schedule.h new file mode 100644 index 0000000..801af0d --- /dev/null +++ b/schedule.h @@ -0,0 +1,9 @@ +#ifndef __SCHEDULE_H__ +#define __SCHEDULE_H__ + +#include "libthreads.h" + +void schedule_add_thread(struct thread *t); +int schedule_choose_next(struct thread **t); + +#endif /* __SCHEDULE_H__ */ -- 2.34.1