19

I have been tasked in a class to create a user level thread library in C. I was wondering if anyone could give me a list of things to read up on to accomplish this. I have a good idea as to where to start, but any resources on user level threads and some applicable aspects of the C language that might help would be extremely valuable.

I am very unclear as to how I would implement a scheduler for such. Assume that I have a pretty good understanding of the C language and some of its more helpful library functions.

Improve this question
4
  • 4
    The assignment is a little bit difficult to satisfy because it can't be done "in C". You need at least a minimal amount of assembly or equivalent compiler extensions to facilitate the creation of new execution contexts and switching between them. Or you could write your own complete virtual machine and C implementation to run on the virtual machine, but I don't think this is what your instructor had in mind... Commented Feb 4, 2012 at 22:55
  • 1
    For cooperative multitasking/threading, you might find getcontext/makecontext/setcontext functions useful. Commented Feb 4, 2012 at 22:57
  • I can't see how this could be done without some assembler to implement the saving/restoring of register context and stack pointer. That's without even considering I/O and how to wait for it. Commented Feb 4, 2012 at 23:01
  • @MartinJames, if the contents of the jmp_buf are documented on your system, you can save & restore all the context you need by wrapping setjmp/longjmp. I’ve done it. (The code has gone to the great /dev/null in the sky, though, so I can’t point to it. ☹) Commented Feb 5, 2012 at 22:36

3 Answers 3

Reset to default
10

I’ve done this for a homework assignment without writing any assembler at all. The thread switch mechanism was setjmp/longjmp. What this involved was allocating memory for each thread’s stack, then very carefully massaging the values in the jmp_buff so execution jumps to the next thread’s stack.

See also Russ Cox’s pretty readable libtask.

Edit in response to OP’s comment: In deciding when to switch threads there are two main directions: preemptive & cooperative. In the preemptive model, you’ll have something like a timer signal that causes execution flow to jump to a central dispatcher thread, which chooses the next thread to run. In a cooperative model, threads “yield” to each other, either explicitly (e.g., by calling a yield() function you’ll provide) or implicitly (e.g., requesting a lock held by another thread).

Take a look at the API of libtask for an example of the cooperative model, particularly the description of the function taskyield(). That’s the explicit yield I mentioned. There are also the non-blocking I/O functions which include an implicit yield—the current “task” is put on hold until the I/O completes, but the other tasks get their chance to run.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This is how I imagined that I would do thread switching. I suppose my biggest blank of knowledge is how to determine when a thread should relinquish control so that another can run. i.e. how do threads determine that they have had enough time.
@SirensOfTitan, I’ve updated my answer to cover what you’ve just asked.
4

A simple cooperative scheduler can be done in C using swapcontext, look at the example in the swapcontext man page here, this is its output:

$ ./a.out
main: swapcontext(&uctx_main, &uctx_func2)
func2: started
func2: swapcontext(&uctx_func2, &uctx_func1)
func1: started
func1: swapcontext(&uctx_func1, &uctx_func2)
func2: returning
func1: returning
main: exiting

So as you can see it is quite doable.

Note: if you swap the context inside a timer signal handler, then you have yourself a pre-emptive scheduler, but I'm not sure if it's safe or possible to do this.

Edit: I found this in the man page of sigaction which suggests that it's possible to switch the context inside a signal handler:

If SA_SIGINFO is specified in sa_flags, then sa_sigaction (instead of sa_handler) specifies the signal-handling function for signum. This function receives the signal number as its first argument, a pointer to a siginfo_t as its second argument and a pointer to a ucontext_t (cast to void *) as its third argument.

Improve this answer

1 Comment

Given that this is a homework problem (and I’ve retagged it so), the OP should check if that would be acceptable. More likely, the instructor is looking for an implementation of swapcontext() functionality rather than simply using it.
2

You can look up Apple's open-source implementation. Note that the largest part of the code is actually assembly code, because it requires some specialized things that you can't do in C, like retrieving the stack frame's return address or jumping to an arbitrary address.

Userland threads (also commonly called "fibers") generally employ a cooperative model; that is, threads execute until they decide they've had enough time, then yield to another thread. Using a priority queue, you can implement a scheduler that executes the task that has run for the shortest amount of time. (The scheduler keeps a track of the running tasks, and the running task yields back when it decides it's had enough. The scheduler updates the amount of time the task has run, then yields to the one that has had the least execution time.)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.