Lab: Worm!

Assigned:
Tuesday, Mar 6, 2018
Due:
Friday, Mar 16, 2018 by 10:30pm
Collaboration:
Work with your assigned partner for this lab. You can use online resources for your lab, provided they do not provide complete answers and you cite them in your code. If you do not know whether it is acceptable use a specific resource you can always ask me.

Overview

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:

  1. A main thread that starts up the game
  2. A thread to update the worm state in the game board
  3. A thread that redraws the board periodically
  4. A thread that reads input from the user and processes controls
  5. A thread that generates “apples” at random locations on the board
  6. A thread that updates existing “apples” by spinning them and removing them after some time

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.

Groups

Group information is no longer available for this course.

Questions & Answers

How should mythread_readchar work?
If there’s already a character to read, we could return it to the thread immediately. However, if getch() returns 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.

Threading System Details

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.

API

mythread_t
This is a type that users of the mythread library use to uniquely identify threads. In the starter code, this is just an int, which is then used as an index into an array of thread information structures.
void mythread_init()
Programs should call this function before invoking any other mythread functions. This gives you an opportunity to set up any bookkeeping data you need. Odds are you’ll have to set things up to keep track of the program’s main thread.
void mythread_create(mythread_t* handle, void (*fn)())
This function mirrors 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)
As with pthread_join, this should block the calling thread until the thread identified by handle has exited. Unlike POSIX threads, there is no provision for collecting a return value.
void mythread_sleep(size_t ms)
The calling thread should block for ms milliseconds. At this point, you should schedule another thread to run. You cannot simply call sleep_ms in this function, since that would block all threads, not just the caller.
int mythread_readchar()
The calling thread should block until user input is available. You can check for input by calling getch() which will return ERR if no input is available, or the character code if input was available.

Internals

The starter code includes a partial implementation of some global state for your thread library, and a partial implementation of the mythread_create function. 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 threads; 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.

The 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).

The makecontext function sets up a context, but does not run it. To do that, you will need to use the swapcontext function. You simply call swapcontext(&context1, &context2), which will save the currently-executing thread to context1, then load in and begin executing from context2. 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 swapcontext. 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.

Scheduler Requirements

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.

Testing

You may find it useful to test your thread implementation with a simpler program than the worm game. 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.

Optional Challenge: Unlimited Threads

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 mythread_t; 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.