Welcome!

Download your copy of the Light-weight Thread Library (LWT), lwt-0.2.tar.gz, for Linux by, John Haskins, Jr. today!


What is the LWT library and where did it come from?

This first distribution of the light-weight thread library (LWT) is a user-level thread library that functions atop Linux' own kernel-level thread scheduling and dispatching mechanisms. It was developed on an Intel system running Linux kernel version 2.0.0 and appears to compile and run stably on 2.0.34, as well. (I have not yet tested it with kernel version 2.2.0. Volunteers?)

[Note: LWT was developed on the Slackware '96 Linux distribution whose jump buffer (jmp_buf) data structures are layed out remarkably differently from those in Red Hat and perhaps other distributions. Since LWT works by trampling several layers of abstraction to manipulate jump buffers directly, it may be necessary to download the Slackware suite of header files (i.e., the contents of /usr/include) in order to get LWT to work with your Linux distribution. A more elegant solution is in the works and will be made availible as quickly as possible. --JHJr. 9 July 1999]

The initial version of LWT was the result of a VERY slow evening. Bored out of my mind, sitting in my apartment one Tuesday evening, I decided to play around with the idea of developing a user-level thread library for use with another of my wild ideas. I booted to my Linux partition and about five hours later, LWT was born. Not exactly feature-rich, LWT sported mutex lock functions and very crude mechanisms for thread creation, destruction, scheduling and dispatching. In the week following, I coded two, more sophisticated synchronization devices: condition variables and semaphores. Though still crude and unrefined, LWT worked and was --- at least in my initial experiments --- surprisingly stable.

Further work on LWT inspired by my gradute-level operating systems professor who posted assignments for which LWT was a perfect foundation. (Assignments, which --- I might add --- account for a non-trivial portion of our final grade.)

What is lwt-0.2.tar.gz and how do I use it?

lwt-0.2.tar.gz is a tar-ed, gzip-ed archive, containing the source files for building and installing the LWT library (liblwt.a) and several sample programs which utilize the library.

To unpack the archive, gunzip and un-tar as in the example below:

All files should be deployed into a directory named lwt-0.2. If you are able to run as root, you may perform a full installation of the library file (liblwt.a) and the header files (lwt.h and lwt_atomic.h) as follows:

You may then link the LWT library to your programs as usual. For example, if you were going to compile the thread.c program from the lwt-0.2/Examples/ directory, your command-line would look like:

Users who are not root, may still compile with LWT; you, however, will not be able to fully install the library and header files, only build them:

Furthermore, you must explicitly specify the location of the header files and explicitly give the path and name of the LWT library file (lwtlib.a). To compile the thread.c program from the lwt-0.2/Examples/ directory, your command-line would look like:

The Makefile bundled with this distribution uses the latter method.

Voila! LWT is ready to go. For an overview of the sample programs and a brief summary of LWT's primary functions, read on. A complete explaination of all functions in the LWT API, is provided in the README.lwt-0.2 file supplied with the archive. (Manual pages are forthcoming and shall appear in a later distribution.)

Tell me about the sample programs.

The sample programs showcase the capabilities of LWT's thread-handling functions and synchronization mechanisms. For your convenience, links to the source-code for each are listed below:

The first demonstrates LWT's mutex lock and condition variable functions; the second demonstrates semaphores; the last demonstrates locking exclusively implemented with mutex locks.

Briefly, what are the basics of the LWT API?

lwt_create() and lwt_kill() create and destroy LWT threads. lwt_dispatcher() configures the session to be either time-slicing (RR_TS) or first-in, first-out (FIFO) and sets up the quantum (in milliseconds) between context switches. lwt_schedule() forces a context switch and can be called from any session, whether time-sliced or first-in, first-out. lwt_mutexinit(), lwt_mutexlock() and lwt_mutexunlock() are the interface functions to LWT's mutex locking mechanisms; each takes as its parameter, a pointer to the mutex lock which is to be initialized, locked or unlocked, respectively. A failed attempt to acquire a lock (i.e., the lock is already held by another thread) will cause a context switch to occur.

lwt_conditionwait(), lwt_conditionsignal(), lwt_conditionbroadcast() and lwt_conditioninit() are the interface functions to LWT's condition variable mechanisms. lwt_conditionwait() takes as its parameter, pointers to a condition variable and a mutex lock. When called, lwt_conditionwait() atomically unlocks the specified mutex lock and removes the calling thread from the run queue; then a context switch invoked. lwt_conditionsignal() takes as its parameter, a pointer to a condition variable. lwt_conditionsignal() searches through the queue of waiting threads, placing back onto the run queue, one thread which waited on the specified condition variable. lwt_conditionbroadcast() functions similarly to lwt_conditionsignal(), but returns to the run queue, all threads that were waiting on the specified condition variable. lwt_conditioninit() initializes the specified condition variable.

Finally, lwt_semainit(), lwt_semap() and lwt_semav(), are the interface functions to LWT's semaphore mechanisms; each takes as its parameter, a pointer to the semaphore which is to be initialized, waited or signaled, respectively. Since the semaphores are built using condition variables, a call to lwt_semap() calls lwt_conditionwait() which causes a context switch and removal from the run queue in the event of a failed lock attempt. lwt_semav() calls lwt_conditionsignal(), causing only one thread to be placed back onto the run queue.

What happens when a thread returns?

It all starts when a thread is created. Immediately after pushing the parameter onto the new thread's stack, lwt_create() pushes a return address. Whether the function running in the thread explicitly calls return or simply reaches its last instruction, this value is popped off the stack by the CPU into the program counter where execution continues. lwt_create() automatically sets this value to the address of the lwt_return() function. (In LWT versions 0.0 and 0.1, the programmer had to manually place lwt_return() calls at the end of thread functions and anywhere return would have been used, ordinarily.)

LWT threads (as with most other thread packages, e.g., Solaris Threads, LinuxThreads) cannot return a value.

What are the known glitches in LWT?

LWT's thread creation and elimination methods are very crude. lwt_kill(), in fact, while it does delete a thread's entry from LWT's internal structures, does not return the killed thread's space to LWT for reuse. When a thread return()s, its runnable status is permanently removed (similarly to lwt_kill()), and its stack space deallocated; its other resources, however, are not immediately deallocated nor deleted from LWT's internal structures; this is done with lwt_kill(). This is remedied in the new version of LWT, to debut in March, 1999.

Finally, because LWT uses a time-slicing non-priority-based scheduling algorithm, the programmer has very limited control over the behavior of the threads once the program is running. A vivid example of this manifests itself in the execution of the count.c program. One might expect that the four threads' counter variables, shielded by a common mutex lock, would get equal amounts of CPU cycles resulting in all four threads' counter variables having similar values. Actual test runs, however, can yield vastly different values for each thread's counter variable. The lack of an appropriate priority mechanism which is responsible for this behavior will be rectified in the next LWT distribution.

What are the author's plans for the future of LWT?

LWT is a prime example of the kind of productive work that gets accomplished on slow Tuesday nights. Given enough slow Tuesday nights, then, who knows? LWT may blossom into a rich, full-featured, multithreaded, mutliuser operating system.

Seriously, though, I hope to continue to refine and --- where necessary --- reconstruct LWT. Particularly, I would like to redo the entire thread allocation-deallocation strategy. Anyone who knows anything about operating systems knows that my method heavily deviates from the usual, more effecient methods more commonly used. Such is the price we pay for rapid prototyping, I suppose. When I sat down to develop LWT, my mind was so abuzz with ideas that in the rush to get them implemented, I neglected efficiency. The allocation-deallocation strategy I used is a real no-brainer.

LWT can automatically switch threads, interrupting the currently running thread at the end of its assigned quantum. The term preemptive, as it is normally used, implies not only that threads be periodically interrupted, but that the threads may be interrupted, because a thread of higher priority arrives, preempting the currently running thread. LWT's threads have no priorities (or, depending on how one views it, they therefore all have the same priority). The next version of LWT will feature threads with priorities and a true preemptive scheduling algorithm.

Hopefully, I will someday get control of an SMP system running Linux (if only for a few short hours). I think that LWT shows promise as a thread library that can function atop a more sophisticated kernel-level thread library such as Xavier Leroy's LinuxThreads which is an implementation of the POSIX 1003.1c thread API.

Software development, it seems, is a never-ending cycle of makes and remakes, bug finds and bug fixes. To that end, I intend to brainstorm and come up with new, innovative ideas for LWT's implementation and features while keeping a constant vigil for subtle errors that I missed in earlier versions.

How do I contact the author?

I can be contacted via e-mail at predator@virginia.edu. Please note that I am a full-time graduate student and that not all my nights are as slow as the one which prompted me to build a thread library (of all things). Therefore, I will not be able to provide support for LWT, the sample programs or any other part of the distributions. I will attempt to respond to all e-mails, bug reports, et cetera in a timely fashion, but offer no promises.

Notes and final comments...

LWT is not intended to replace anyone's thread library. LWT was originally intended for my own use in the development of another project idea. Developing it taught me an awful lot (and helped to assure me that the whopping amount of money spent paying for my undergraduate education was money well-spent). LWT, in my opinion, has pedagogical value. I would be very interested, in fact, in receiving any feedback from educators about LWT's effectiveness as a teaching tool. (CS4441, Introduction to Thread Library Implementation, anyone? I'd gladly teach such a course... for a modest salary.)

Legalese...

Neither I, the author nor the University of Virginia guarantee the suitability of the Light-weight Thread library (LWT) for any purpose, that it be stable, correct or bug-free. LWT is free software, offered to the Linux community in the hope that others will find it elucidating, offering some insight into the implementation of user-level thread libraries. Use at your own risk.

Latest version: 17 February 1999.


Light-weight Thread Library for Linux. Copyright (C) 1998,1999 John Haskins, Jr.