Lightweight Tasks in C

While most modern operating systems allow multiple threads within a process, earlier-generation systems do not. Jonathan presents a multithreading package that allows for cooperatively multitasked threads within a single process for operating systems that do not explicitly support threads.

May 01, 1995
URL:http://www.drdobbs.com/cpp/lightweight-tasks-in-c/184409552

Figure 1

MAY95: Lightweight Tasks in C

Lightweight Tasks in C

A robust implementation in a few lines of code

Jonathan Finger

Jonathan is a Boston-area consultant with many years of experience programming in C and Mumps. He can be reached at [email protected].

Modern operating systems allow multiple processes to exist at the same time, and each process can contain more than one thread of execution. For operating systems that do not explicitly support threads, you can build a multithreading package in a high-level language such as C, which allows for cooperatively multitasked threads within a single process.

One good commercial implementation of this is the Multi-C package from MIX Software, which provides process scheduling, process synchronization, and message passing. However, for a variety of reasons, you may want to roll your own lightweight tasker in C. For instance, one project I was involved in required porting a multiuser mailing-list management system from its original minicomputer platform to a PC/DOS system. I decided to implement a multitasking system in C to work in place of the original minicomputer operating system. My system serves as the foundation for the multiuser application, which consists of thousands of lines of production code. In this article, I'll present a simplified version of my multithreading code. This code is not a toy--the original version has been used extensively in a commercial environment for several years. The code runs over DOS and can be compiled with either the Watcom 10.0 32-bit compiler using the Tenberry Software (formerly Rational Systems) DOS extender or the Microsoft C7.0 16-bit compiler.

Processes and Tasks

Conceptually, a process is a program in execution, plus its associated environment. The operating system isolates processes so they don't interfere with each other; often, processes can communicate with each other using primitives provided by the operating system. Because of this, you can completely define the state of a process by specifying the values of its variables (global and local) and a unique point in the executing code.

In a multithreading system, each thread is effectively a copy of its original process, but, unlike heavyweight processes, threads share resources and global variables (and can therefore interfere with each other). On a multiprocessor machine, different processors can run threads simultaneously.

Switching between threads can be either cooperative or preemptive. In cooperative task switching, a thread runs until it makes an explicit call to swap_thread(), which allows other threads to run, eventually returning to its caller. From the point of view of the calling thread, there is no perceptible effect, except for the passage of time.

In preemptive task switching, a thread runs until some external event (such as a timer interrupt or a device interrupt) causes the thread to be suspended and another thread resumed.

Implementing Cooperative Task Switching

The trick to cooperative task switching in C is that for most machines and compilers, only three things need to be set properly: the instruction pointer, C stack, and machine registers.

The instruction pointer or program counter marks the current place in the running code. The C functions setjmp() and longjmp() take care of the instruction pointer and the registers, but they unwind the stack. To handle the stack properly, our code must explicitly copy it to a "save" region for each thread. In my version, these routines assume that the C stack is in contiguous memory and that it grows from the bottom; see Listing One .

As you can see in the listing, the threads struct contains information about individual threads. The start_new_thread (*program) function creates a new thread and stores a pointer to the program in the threadp>function element of the threads struct.

For this code to work, the compiler must implement local variables on a stack, the stack must be contiguous, and the stack must grow down. Fortunately, these conditions are satisfied on most machines and C compilers, but they are not part of the C specification. It is pretty straightforward to modify my implementation to account for stacks that grow up; your code can also test the direction of stack growth and act accordingly.

The routines start_new_thread() and queue_thread() can be called from an interrupt service routine as long as mutual exclusion is ensured. (For example, if an interrupt occurs during execution of queue_thread and you call queue_thread, the queues may get corrupted.) In MS-DOS, you can accomplish simple mutual exclusion by masking out interrupts during critical sections of code.

Implementing Preemptive Task Switching

Preemptive task switching is implemented by simply switching tasks at predefined intervals. Usually, the process receives periodic interrupts from a timer, and the multitasker arranges things so that the interrupt returns to the next task. There are several ways of implementing this:

Under 16-bit MS-DOS, you can use assembly language to directly manipulate the stack.

Under 32-bit MS-DOS, such stack manipulation may or may not be possible, depending on the DOS extender you use.

On systems with C compilers that implement signal(SIGALRM,_), the signal is usually implemented as a call, meaning that you can use the setjmp()/longjmp() stack-copy tricks in Listing One.

Context Switch Walkthrough

To clarify the implementation, I'll walk through a context switch. For simplicity, I'll assume two threads (A and B) are running and that all task-switches occur with calls to swap_thread(). You should also assume that thread A is running and thread B is waiting to run. The run-time stack is shown in Figure 1.

The part of the run-time stack colored light pink contains thread A's local variables and function return address. If thread B were running, B's local variables and function return addresses would occupy the area colored light or dark pink, but this area of memory has been copied to thread B's thread[B].c_stack. (For this example, assume thread B is currently using more stack than thread A.)

Thread A calls swap_thread() to allow other threads to run. swap_thread() returns if there is no other runable thread. Finding thread B as the next thread in the run queue, thread A gets moved from the head of the run queue to the tail.

Next, swap_out_thread() is called. It saves any thread globals and copies the area of the run-time stack colored light pink in Figure 1 to thread A's stack save-area (thread[A].c_stack). Next, setjmp() sets the point where thread A will resume execution. setjmp returns 0, so the return value from swap_out_thread() is 0 and swap_in_thread() is then called.

The swap_in_thread() function sets up any global variables for thread B and then copies the saved run-time-stack data to the run-time stack, so that the area in Figure 1 colored light or dark pink now contains thread B's stack info. This is why swap_in_thread() has a local variable called UCHARbuffer[thread_SWAP_STACK _SIZE]. This guarantees that the locals used by setup_thread_globals() are in a portion of the stack not overwritten by the memcpy(). This area is a breeding ground for potential bugs, since an optimizing compiler may realize that buffer[] is not used and leave the stack pointer unchanged. If the compiler inlines setup_thread_globals() into swap_in _thread(), it becomes apparent that buffer[] is not used.

The swap_in_thread() function now executes longjmp(). The cpr-->swap _thread_buff structure element was previously set for thread B by the setjmp() call in swap_in_thread(), so control is transferred to the setjmp() in swap _out_thread(). The setjmp() returns a nonzero value, so swap_out_thread() returns to swap_thread() with a nonzero value. Since the run-time stack now returns thread B's stack, swap_thread() returns to thread B.

Conclusion

The setjmp() and longjmp() functions in C allow implementing a bare-bones multitasker in only a few lines of code. This straightforward code can serve as the basis for more full-featured implementations.

Figure 1 Diagram of the run-time stack when two threads are created.

Listing One


/* Lightweight Multitasker in C -- by Jonathan Finger, 1995   (reformatted) */

#include <setjmp.h>
#include <conio.h>
#include <stdio.h>
#include <time.h>
#include <string.h>
#include <dos.h>
#include <setjmp.h>

#define MAX_THREAD              10
#define THREAD_SWAP_STACK_SIZE  10000
typedef short    int            THREAD_NUM;
typedef unsigned char           UCHAR;
typedef unsigned long           ULONG;
typedef unsigned int            UINT;
typedef unsigned short int      USHORT;
typedef unsigned char *         STR;

/*----------------------the threads structure-------------------------------*/
struct threads 
{
        THREAD_NUM thread_number;
        jmp_buf    swap_thread_buff;
        UCHAR      c_stack[THREAD_SWAP_STACK_SIZE];/* save area for c stack */
        size_t     c_stack_size;                   /* save state info       */

        THREAD_NUM volatile next_thread;   /* forward chain for queues      */
        THREAD_NUM volatile prev_thread;   /* backward chain for some queues*/
        UCHAR      volatile queue;         /* current queue that thread is  */
                                           /* on: 'R'means RUN, 'F'is Free  */
        void (*function)(void);
        /* other info can be added here as needed */
};
typedef struct threads thrd;
thrd thread[MAX_THREAD];
thrd *cpr; /* pointer to the current running thread */
/*------------------------------------------------------------------------*/
jmp_buf   new_thread_start_buff;
#define NO_THREAD           (MAX_THREAD+100)
THREAD_NUM  current_thread = NO_THREAD;
STR  stack_swap_start;
/* note that the following variables have been declared volatile, since 
 * they may be altered by an interrupt service routine  */
static THREAD_NUM volatile run_queue_head;
static THREAD_NUM volatile run_queue_tail;
/*------------------------Function prototypes-------------------------*/
void     init_thread_table     (void);
int      start_new_thread      (void (*program)(void));
void     free_current_thread   (void);
void     setup_thread_globals  (THREAD_NUM thread_no, STR buff);
void     save_thread_globals   (void);
int      swap_out_thread       (void);
void     swap_in_thread        (void);
void     swap_thread           (void);
void     swap_thread_block     (void); /*put curr thread to sleep on event*/
void     queue_thread          (THREAD_NUM thread_number);
void     unqueue_thread        (UCHAR new_queue);
void thread1(void)
{       while (1)
        {       printf("\n\rthread 1");
                swap_thread();
        }
}
void thread2(void)
{       while (1)
        {       printf("\n\rthread 2");
                swap_thread();
        }
}
void thread3(void)
{       while (1)
        {       if (kbhit()) exit(0);

                printf("\n\rthread 3");
                swap_thread();
        }
}
main()
{       int i = 0;
        init_thread_table();
        run_queue_head = run_queue_tail = NO_THREAD;
        stack_swap_start = (STR) &i;
        if (!setjmp(new_thread_start_buff))
        {       
                /* starts three threads */
            start_new_thread(thread1);/*should error-check return value*/
                start_new_thread(thread2);
                start_new_thread(thread3);
                swap_thread_block();
        }
        (*(cpr->function))();
        free_current_thread();
}
void init_thread_table()
{       int i = 0;
        while (i < MAX_THREAD)
        {       thread[i].thread_number = i;
                thread[i].queue         = 'F';
                thread[i].next_thread   = i + 1;
                thread[i].prev_thread   = i - 1;
                i++;
        };
        thread[MAX_THREAD].next_thread = NO_THREAD;
}
int start_new_thread(void *(program)(void))
{
        THREAD_NUM thread_num;
        thrd *threadp;
        thread_num = get_free_thread_id();
        if (thread_num == NO_THREAD) return(NO_THREAD);
        threadp = &thread[thread_num];
        threadp->c_stack_size = 0;
        threadp->next_thread  = NO_THREAD;
        threadp->function     = program;
        memcpy(threadp->swap_thread_buff,
                new_thread_start_buff, sizeof(jmp_buf));
        /* the memcpy copies the contents of new_thread_start_buff 
        * to the thread's swap buff so that when swap_in_thread() 
        * calls longjmp(), control returns from the setjmp in main()  */
        queue_thread(thread_num);
        return(thread_num);
}
static int get_free_thread_id()

{       int i = 0;
        do 
    {       while ((i < MAX_THREAD) && (thread[i].queue != 'F')) 
                    i++;
                if (i < MAX_THREAD) return(i);
        } while (i < MAX_THREAD);
        return(NO_THREAD);
}
void setup_thread_globals(THREAD_NUM thread_num, STR buff)
{       /*STR buff; needed to defeat optimizer */
        cpr = &thread[thread_num];
}
void save_thread_globals()
{
}
int swap_out_thread()
{       long int i;
        if (current_thread == NO_THREAD) return(0);
        save_thread_globals();     
        i = stack_swap_start - ((STR)&i);
        cpr->c_stack_size = (size_t) i;
        memcpy(cpr->c_stack, ((STR)&i)+1, (size_t) i);
        return(setjmp(cpr->swap_thread_buff));
        /* the setjmp sets the return point where the thread will 
     * resume execution when longjmp() in swap_in_thread()  */
}
void swap_in_thread()
{       UCHAR buffer[thread_SWAP_STACK_SIZE];
        /* make sure we are above (below) the swap stack */
        current_thread = run_queue_head;
        setup_thread_globals(current_thread, &buffer[0]);
        memcpy(stack_swap_start - cpr->c_stack_size + 1,
                cpr->c_stack, cpr->c_stack_size);
        longjmp(cpr->swap_thread_buff, 1);
        /* lonjmp() transfers control back to setjmp() in swap_out_thread */

}
void swap_thread()
{       int next_thread;
        next_thread = thread[run_queue_head].next_thread;
        if (next_thread != NO_THREAD)
        {       run_queue_head = next_thread;
                thread[run_queue_tail].next_thread = current_thread;
                run_queue_tail = current_thread;
                thread[current_thread].next_thread = NO_THREAD;
                if (!swap_out_thread()) swap_in_thread();
                /* if swap_out_thread() returns 0, this is a return from the
                 * call to swap_out_thread and we call swap_in_thread. If it 
                 * returns !0 then swap_out_thread is returning from longjmp()
                 * in swap_in_thread and task switch has already occurred */
        }
}
void swap_thread_block() /*put current thread to sleep on event*/
{       while (run_queue_head == NO_THREAD) 
                continue;
        /* if this loop is encountered and run queue is empty, process idles
         * until a process is queue either in an interrupt service routine or 
         * signal handler */
        if (current_thread != run_queue_head
                && !swap_out_thread()) 
        {
                swap_in_thread();
        }
}
void queue_thread(THREAD_NUM thread_number)
{
        /* If run queue can be modified by an interrupt service routine or
     * signal handler then code must be added to assure mutual exclusion */
        if (run_queue_tail != NO_THREAD) 
    {
                thread[run_queue_tail].next_thread = thread_number;
        }
        else 
    {
            run_queue_head = thread_number;
    }
        run_queue_tail = thread_number;
        thread[thread_number].next_thread = NO_THREAD;
        thread[thread_number].queue = 'R';
}
void unqueue_thread(UCHAR new_queue)
{       THREAD_NUM thread_num;
        thread_num = run_queue_head;
        if ((run_queue_head =  thread[thread_num].next_thread) == NO_THREAD)
                run_queue_tail = NO_THREAD;
        thread[thread_num].queue = new_queue;
}
void free_current_thread()
{       free_thread(current_thread);                    
        unqueue_thread('F');
        swap_thread_block(); /* this will never return */
}
int free_thread(THREAD_NUM thread_num)

{       thrd *threadp = &thread[thread_num];
        if (threadp->queue == 'F') return(0);
        if (current_thread == thread_num) current_thread = NO_THREAD;
        return(1);
}