/* * minithread.c * * Sung-Eun Choi (sungeun@cs.washington.edu) * Autumn 1996 * */ #include #include #include "my_malloc.h" #include "minithread.h" #include "minithread_md.h" #include "clock.h" #include "queue.h" #include "panic.h" /* * A minithread should be defined either in this file or in a private * header file. Minithreads have a stack pointer with to make procedure * calls, a stackbase which points to the bottom of the procedure * call stack, the ability to be enqueueed and dequeued, and any other state * that you feel they must have. */ struct minithread { stack_pointer_t sp; stack_pointer_t stackbase; minithread_t next; }; /* important threads */ static minithread_t Idle_minithread = (minithread_t) NULL; static minithread_t Active_minithread = (minithread_t) NULL; static minithread_t Main_minithread = (minithread_t) NULL; static minithread_t Reaper_minithread = (minithread_t) NULL; /* Approximately the max number of free threads that can be sitting around in the free list -- I just picked this number out of thin air. I probably should run a few experiments and adjust it. */ #define FREE_THREAD_LIMIT 10 /* In an ideal world, I'd be using my queue package for this, but since C allows me to, I'll use a mechanism that I think is more effiecnt. */ static minithread_t Free_minithreads = (minithread_t) NULL; static minithread_t Moribund_minithreads = (minithread_t) NULL; /* the ready queue (FIFO) */ static queue_t ReadyQ; /* forward references */ static void scheduler_loop(int); static void minithread_reaper(int); static void minithread_destroy_internal(minithread_t); static void minithread_exit(int); #define minithread_panic panic /* * minithread_t * minithread_fork(proc_t proc, arg_t arg) * Create and schedule a new thread of control so * that it starts executing inside proc_t with * initial argument arg. */ minithread_t minithread_fork(proc_t proc, arg_t arg) { minithread_t t; t = minithread_create(proc, arg); /* create a thread */ minithread_start(t); /* and start it */ return t; } #ifndef STACKALIGN #define STACKALIGN 03 #endif /* * minithread_t * minithread_create(proc_t proc, arg_t arg) * Like minithread_fork, only returned thread is not scheduled * for execution. */ minithread_t minithread_create(proc_t proc, arg_t arg) { minithread_t t; disable_interrupts(); /* allocate the thread */ if (Free_minithreads != NULL) { /* check the list of freed threads */ t = Free_minithreads; Free_minithreads = t->next; /* reset the stack pointer */ /* copied from minithread_allocate_stack() */ if (STACK_GROWS_DOWN) { /* Stacks grow down, but malloc grows up. Compensate and word align. */ t->sp = (stack_pointer_t) (( ADDR_TO_INT(t->stackbase) + STACKSIZE - 1)&~STACKALIGN); } else { /* Word align (turn off low 2 bits by anding with ~3) */ t->sp = (stack_pointer_t)(( ADDR_TO_INT(t->stackbase) + 3)&~STACKALIGN); } } else { /* oh well, create a new thread */ t = (minithread_t) my_malloc(sizeof(struct minithread)); if (t == NULL) { minithread_panic("Out of memory."); } /* allocate stack */ minithread_allocate_stack(&t->stackbase, &t->sp); if ((t->stackbase == NULL) || (t->sp == NULL)) { minithread_panic("Out of memory."); } } t->next = NULL; /* initialize stack */ minithread_initialize_stack(&t->sp, /* (proc_t) enable_interrupts, (arg_t) NULL, */ (proc_t) NULL, (arg_t) NULL, proc, arg, (proc_t) minithread_destroy_internal, (arg_t) t); enable_interrupts(); return t; } /* * minithread_t minithread_self(): * Return identity (minithread_t) of caller thread. */ minithread_t minithread_self() { return Active_minithread; } /* * minithread_stop() * Block the calling thread. */ void minithread_stop() { minithread_t t; t = minithread_self(); /* get my context */ disable_interrupts(); Active_minithread = Idle_minithread; /* Run the idle thread */ minithread_switch(&t->sp, &Idle_minithread->sp); enable_interrupts(); } /* * minithread_unlock_and_stop(tas_lock_t* lock) * Atomically release the specified test-and-set lock and * block the calling thread. */ void minithread_unlock_and_stop(tas_lock_t *lock) { disable_interrupts(); atomic_clear(lock); minithread_stop(); enable_interrupts(); } /* * minithread_start(minithread_t t) * Make t runnable. */ void minithread_start(minithread_t t) { /* put the thread on the ready queue */ disable_interrupts(); queue_append(ReadyQ, (any_t) t); enable_interrupts(); } /* * minithread_yield() * Forces the caller to relinquish the processor and be put to the end of * the ready queue. Allows another thread to run. */ void minithread_yield() { minithread_t t; disable_interrupts(); if ((Active_minithread != NULL) && /* if we've started AND */ (Active_minithread != Idle_minithread)) {/* I'm not the idle thread */ t = minithread_self(); /* get my context */ queue_append(ReadyQ, (any_t) t); /* put it on the ready queue */ minithread_stop(); /* stop running */ } enable_interrupts(); } /* * Initialization. * * minithread_system_initialize: * This procedure should be called from your C main procedure * to turn a single threaded UNIX process into a multithreaded * program. * * Initialize any private data structures. * Create the idle thread. * Fork the thread which should call mainproc(mainarg) * Start scheduling. * */ void minithread_system_initialize(proc_t mainproc, arg_t mainarg) { stack_pointer_t dummy_stack; /* initialize the ready queue */ #ifdef DEBUG_MT printf("Initializing ready queue...\n"); fflush(stdout); #endif ReadyQ = queue_new(); /* fork the main thread */ #ifdef DEBUG_MT printf("Forking the first thread...\n"); fflush(stdout); #endif minithread_fork(mainproc, mainarg); /* create the idle thread */ #ifdef DEBUG_MT printf("Creating the idle thread...\n"); fflush(stdout); #endif Idle_minithread = minithread_create((proc_t) scheduler_loop, (arg_t) NULL); /* create the reaper thread */ #ifdef DEBUG_MT printf("Creating the reaper thread...\n"); fflush(stdout); #endif Reaper_minithread = minithread_create((proc_t) minithread_reaper, (arg_t) NULL); /* initialize the clock */ #ifdef DEBUG_MT printf("Initializing the clock...\n"); fflush(stdout); #endif #ifndef NON_PREEMPTIVE minithread_clock_init((ClockHandler) minithread_yield); #endif /* switch to the idle thread */ #ifdef DEBUG_MT printf("Begin scheduling...\n\n"); fflush(stdout); #endif minithread_switch(&dummy_stack, &Idle_minithread->sp); /* Alternatively, you could have (1) created a dummy thread to do the bootstrap, or (2) just started the scheduler loop */ } /* * minithread_reaper(int dummy) * Spare thread context which cleans up the contexts of terminated threads. */ static void minithread_reaper(int dummy) { minithread_t t, prev_t; int i; /* clean up after terminated threads */ while (1) { disable_interrupts(); #ifdef DEBUG_MT { int i; i = 0; while (t = Moribund_minithreads) { Moribund_minithreads = t->next; i++; } printf("minithread_reaper: cleaning up after %d threads\n", i); fflush(stdout); } #endif /* put the moribund thread contexts on the free list */ if (Free_minithreads == NULL) { Free_minithreads = Moribund_minithreads; } else { /* first, make sure the free list isn't too long */ for (i = 1, prev_t = Free_minithreads, t = prev_t->next; i < FREE_THREAD_LIMIT && t != NULL; prev_t = t,t = t->next) { /* count the number of free threads */ i++; } if (i > FREE_THREAD_LIMIT) { /* free the moribund threads */ while (t = Moribund_minithreads) { Moribund_minithreads = t->next; minithread_free_stack(t->stackbase); my_free((char*)t); } } else { /* add the moribund threads to the end of the list */ prev_t->next = Moribund_minithreads; } } Moribund_minithreads = NULL; minithread_stop(); /* no threads, so stay off the ready queue */ } } /* * minithread_destroy_internal() * Never returns. * Normally called when a thread returns from its topmost stack frame. * */ static void minithread_destroy_internal(minithread_t t) { disable_interrupts(); if (Moribund_minithreads == NULL) { /* if there are no moribund threads */ /* the reaper thread is not in ther ready queue, so put it there */ #ifdef DEBUG_MT printf ("minithread_destroy_internal: scheduling the reaper\n"); fflush(stdout); #endif queue_append(ReadyQ, (any_t) Reaper_minithread); } t->next = Moribund_minithreads; Moribund_minithreads = t; minithread_stop(); } /* exported version that does not stop */ void minithread_destroy(minithread_t t) { disable_interrupts(); if (Moribund_minithreads == NULL) { /* if there are no moribund threads */ /* the reaper thread is not in ther ready queue, so put it there */ #ifdef DEBUG_MT printf ("minithread_destroy: scheduling the reaper\n"); fflush(stdout); #endif queue_append(ReadyQ, (any_t) Reaper_minithread); } t->next = Moribund_minithreads; Moribund_minithreads = t; enable_interrupts(); } /* Exit gracefully */ static void minithread_exit(int ret_code) { exit(ret_code); } /* * Scheduler loop. The idle thread runs this loop. */ static void scheduler_loop(int dummy) { minithread_t t; Active_minithread = Idle_minithread; while (1) { disable_interrupts(); if (queue_dequeue(ReadyQ, (any_t *) &t) == 0) { if (t != NULL) { /* run this thread */ Active_minithread = t; minithread_switch(&Idle_minithread->sp, &t->sp); /* I'm running now */ Active_minithread = Idle_minithread; } else{ /* no more threads */ minithread_exit(0); } enable_interrupts(); } else { minithread_panic("Error accessing ready queue."); } } }