In this lab, you will implement a simple user-space threading system, similar to the basic functionality we have used in POSIX threads. Unlike POSIX threads, this threading system will provide concurrency but not parallelism. The system will create the impression of multiple tasks running at once (it is thus concurrent) but only one will actually be active at any one time (there is no parallelism). While the system you implement could be used for general purpose parallel programs, you will be implementing it specifically to support the game Worm!, a clone of the classic game Snake.
This game implementation uses several threads:
Each thread runs in a loop that contains a blocking operation. Your task is to implement a threading system that will run these threads in round-robin fashion, switching between them as the currently-executing thread blocks. We will spend some time at the start of class looking through the provided code and discussing the thread implementation.
You can find the starter code for your lab at http://github.com/csc213/worm-USERS, where USERS is replaced by a dash-separated list of all groups members’ Grinnell usernames. Please work directly in this repository and not in a fork; you do not need to submit a pull request to turn in this lab.
Group information is no longer available for this course.
ERR, no input is available. First, you need to record why the thread is blocked (it’s waiting for input), and then call
scheduler()to choose a new thread to run. Later, when the scheduler is choosing a new thread to run (at some point in the future) there will be an input character. The scheduler can then
swapcontext()back to the thread we blocked.
You will be implementing what is known as cooperative multithreading. This is a simple technique for implementing threads where there is no preemption. Once a thread is started it will run until it issues a blocking operation or exits. In our case, threads will run until they exit, ask to join another thread, sleep, or wait for user input. When you hit one of these points you should invoke the scheduler function to select and start another thread to run. As part of this process, you will need to check to see if any previously-blocked threads can now unblock. This could happen because they are joining with threads that have now exited, their sleep timer has elapsed, or user input is now available. The thread API below should give a better sense of how this all works.
int, which is then used as an index into an array of thread information structures.
void mythread_create(mythread_t* handle, void (*fn)())
pthread_create, in that it starts a new thread and writes an identifying handle for this new thread to the first parameter. Unlike
pthread_create, there is no provision for passing attributes or a parameter to the new thread.
void mythread_join(mythread_t handle)
pthread_join, this should block the calling thread until the thread identified by
handlehas exited. Unlike POSIX threads, there is no provision for collecting a return value.
void mythread_sleep(size_t ms)
msmilliseconds. At this point, you should schedule another thread to run. You cannot simply call
sleep_msin this function, since that would block all threads, not just the caller.
getch()which will return
ERRif no input is available, or the character code if input was available.
The starter code includes a partial implementation of some global state for your thread library, and a partial implementation of the
thread_info_t struct is designed not to be shared with the user of the system, but to hold the internal state of a thread;
this includes its context—the state required to return to the running thread—and other information about what the thread is waiting for or whether it has exited.
There is an array of these
thread_info_t structures called
the value returned in a
mythread_t is an index into this array.
You are free to change this structure, but you should not need to unless you decide to do the optional challenge at the end of this lab.
mythread_create function shows how you can set up a
context_t to execute a function.
To do this, you first pre-populate the context with information from the current thread, set up a stack for the new thread, and then use the
makecontext function to point the context to a function with some number of parameters (zero in our case).
makecontext function sets up a context, but does not run it.
To do that, you will need to use the
You simply call
swapcontext(&context1, &context2), which will save the currently-executing thread to
context1, then load in and begin executing from
One peculiar feature of this function is that it sort of returns.
The processor will begin executing in
context2, but if you later swap back to
context it will resume by returning from this call to
Your scheduler code will need to use
swapcontext to jump from a newly-blocked or exited thread to the next thread you would like to execute.
You should implement a round-robin scheduler for this lab. That means if thread 3 blocks, the first candidate thread your scheduler should consider is thread 4; if thread 4 is blocked, move on to thread 5, thread 6, and so on. You do not need to reorder threads to track the order in which they unblocked; simply cycle through them in the order they were first created, starting with the next thread in the sequence after the previously executed one.
You may find it useful to test your thread implementation with a simpler program than the
This may be a good way to test thread scheduling and sleeping before you’ve implemented input or joining.
The easiest way to test your thread implementation would be to move worm.c out of the lab directory temporarily and write a new source file with a
main function that creates some threads using your thread API.
Make sure you call
mythread_init before calling any other mythreads functions.
One drawback of the implementation this lab starts with is that there is a hard upper limit on the number of threads any program can create.
That limit applies to both currently-executing threads and any threads created in the past.
If you would like an additional challenge, change your implementation so it supports an arbitrary number of threads.
That means you will not be able to use a fixed-size global array to track threads, and you should have some provision for freeing memory allocated to hold thread information once a thread has been joined.
This will almost certainly require that you change the underlying type of a
think carefully about what kind of type will best allow you to locate a thread’s information structure without imposing the upper limit in the original implementation.