Project 2

Introduction

In the previous project, we studied the effect of a user level scheduler with some high performance, non-I/O code. For project we are going to address a common I/O bound application, the Web Server. Suggested reading for this project is the Scheduler Activation Paper (from the optional readings section).
User level thread libraries have many advantages over conventional threading functionality provided by the OS. Switching cost for user level threading code is very low and hence it makes sense to have a much finer quantum, allowing for reduced thread latency. Furthermore the cost of maintaining user level threads is paid in user space, as opposed to kernel threads which require portions of the kernel address space. User level threads are more easily scheduled according to need, thus allowing an application to work more smartly. For example, a smart application can add a low priority idle thread to work as a pre-fetching/caching thread, so that i/o requests are fulfilled with lower latency.

Goals

The goal of this project is to more completely understand the user level thread functionality. We will build on the previous project. If your project 1 code was not complete, please contact me by email and I'll provide a working project 1. While most of you already have a working multiprocessor scheduler, for the purpose of simplification, we will only concern ourselves with the single processor case.

Step 1

In the first step we will add a priority based scheduling policy to the current scheduler. Define each thread with a certain priority (priority classes are up to you, but I suggest atleast 3 classes). To further optimize your library add support for stack reuse (so that you don't have to perform a memory allocation each time you create a thread). Assume that your thread will exit with a proper exit call. However stack reuse doesn't work if you use up too much memory. So implement a stack garbage collector in your idle thread. Garbage collector policy is very important to the peformance.

Step 2

One major problem in user level thread libraries is that I/O involved blocking for the entire application. This is because I/O usually involved a system call into kernel mode. However this problem can be fixed by allocating multiple kernel threads at the start. You want to design your thread library so that when an I/O request is made, a waiting kernel thread is made active so that the other user level threads can be scheduled. To simplify the problem, you are allowed to add I/O replacement calls to your library (gtopen, gtread, gtwrite, gtseek, etc). You can also use the control you have over the I/O functionality to add features that are missing in conventional I/O calls.

Step 3

Combine the above two improvements to the scheduler and write a small i/o intensive application for it. For ease of measurement I would like to see an implementation of a threaded webserver. (Yes I know network polling webservers can be faster but this is to test your library not the webserver). Implement this webserver first using pthreads in linux. This will be your base case. Next replace the pthread functionality with gtthread functionality. Next add gtIO to the webserver.
Compare the performance of the pthread, gthread and gtthread/gtio servers. The performance metrics that you should look at are response time, total throughput, maximum latency, scheduling overhead, number of clients and size of files being served.

Step 4

The final step is to take full advantage of the functionality of your libraries. You should add support for prefetching based on history, thread reuse, stack reuse and multiple priority threads. Compare the performance of each optimization with the base design.

Submission

Submit a full report of the project including design and implementation of webserver, design and implementation of scheduling classes, non-blocking I/O design and implementation and prefetching design and implementation. Provide complete performance comparisons between the different designs. Please provide analysis of performance results instead of just a graph/table. The grade is more based on analysis and justification rather than actual numbers. You must also submit your tar.gz source code. Since we aren't sure about the directories, submit by email to habbasi@cc.
Mohammed Hasan Abbasi
Last modified: Sat Sep 23 23:25:02 EDT 2006