This past March I was a judge for a regional science fair. Having entered a regional science fair six times, travelled to the Canada-Wide Science Fair twice, and having won a gold medal at a Canada-Wide Science Fair, I think that I bought a unique perspective to judging. Having said that, there were some standout issues that I noted with the projects that I saw, and I'd like to put them up here in case anybody (perhaps an adviser to a science fair student) finds them useful.

1. Wikipedia is not an acceptable bibliography entry.
   
   I don't think that I saw a single project without a Wikipedia reference in the bibliography (I was rather startled to see this, but much has changed in the decade since my peak at the science fair). Why is this a problem? Let's start with the obvious: Anybody can edit Wikipedia. I know that there has been plenty of debate about whether Wikipedia is better than any other encyclopedia, but lets face it: its content is in a constant state of flux and is not always subjected to the same scrutiny as more authoritative sources -- such uncertainty is not welcome in a scientific endeavour. Furthermore, encyclopedias alone do not go into enough depth on a subject to provide sufficient research. Few projects had rich bibliographies containing credible books or papers related to their subjects. Especially at the high school level, I really think that the creator of a winning project needs to spend some time at a post-secondary library. I used to spend plenty of time at our local college library and, since I mostly did computer science projects, at computer book stores. Don't get me wrong: I'm not saying that the internet isn't a useful resource. I am saying that the internet resources need to be credible, and I am tremendously disappointed that the students' advisers did not point out these problems.



2. Science Fair projects need to show some science.
   
   This entry really applies more to students in the upper years whose projects might be considered for the Canada-Wide Science Fair. I witnessed this problem with engineering projects in particular, but it really applies to every category: It's great if the student is able to build something and explain how it works. On the other hand, why it works is just as (if not more) important than the how. I want to illustrate this in terms of a hypothetical project involving a mechanical device. Suppose that this mechanical device shoots a projectile. Doing trials to prove that it does (or does not) work is insufficient. For this project to really shine, it needs some scientific polish. The applicable kinematics equations are easily understandable by a ninth grade student. If the device is storing potential energy, spring constants are also easy to grasp. If the exhibitor were to combine the physics equations with the actual tests of the device, it would improve the project immensely. For example, the student could do some math to predict the results of the trials, and then attempt to confirm these predictions in the experiment.
   
   I was not immune from this issue. For my first science fair project in seventh grade, I built trusses out of match sticks. The purpose of the project was to determine if the strength of the trusses increased proportionally to the number of triangles in the design. In order to test the bridges, I placed lead weights on the trusses, increasing the mass until the truss broke. Unfortunately I did not answer some very important questions related to my work:
   
   
   • Why was lead a useful material for weights?
   • What kinds of forces were involved?
   • Mathematical formulas and calculations
   • Other issues (this list is not comprehensive)
   
   
   I guess that the point that I am trying to make is this:
   
   
   • If there are mathematical formulae related to the subject matter, learn them and use them (biology projects are not immune to this, no pun intended).
   • If your experiment behaves a certain way, explain why, even (or especially) if it doesn't work as expected.
   • If you make a decision, explain why you made it.
   • If you choose certain materials, explain why.
   • If you can measure something more precisely, do so. If you are unable to do so (perhaps it is too expensive), then mention that as an improvement in your future work.
     
   • If you have a feeling that a judge might catch you on something, fix the problem (the judges will notice it).



3. Watch those constants.
   
   Group projects, remember that it's not always a good idea to split everything 50/50. For example, let's suppose that Partner A and Partner B agree to do 20 repetitions of their experiment, but to keep it fair, each partner will do half of them at his/her respective house and then combine the results later. Hold on! Unless the location of the test is the manipulated variable, the experiment will be flawed. The location of the experiment isn't being held constant! I know it sounds like nitpicking, but it weakens an experiment when a "close enough" attitude is taken toward constants! It calls the results into question when more than one variable is being manipulated at a time.
   

After I wrote my original post about the fibrous thread pool, I recalled an additional issue that I needed to address during implementation.

Suppose I'm executing a function on a fiber that has been scheduled by the fibrous thread pool. If I call ReadFile, I need to perform a suspend operation because the I/O completion port will generate a completion packet corresponding to the read operation. What if ReadFile returns TRUE? We already know that the operation has completed successfully, so why should we bother suspending? In older versions of Windows, the completion event fires no matter what. This leads to some extra activity in the fibrous thread pool that is merely housekeeping to ensure that our completion events are in sync. Unfortunately this housekeeping is effectively redundant. What we really need is a way to suppress I/O completion callbacks when a file I/O operation returns TRUE without ERROR_IO_PENDING being set.

The Windows 6.x (i.e. Vista and Server 2008) versions provide the solution via a new API: SetFileCompletionNotificationModes. This function allows us to disable I/O completion notifications in instances where an I/O operation meets the above criteria.

For all the criticism that Vista has received, I've got to say that I'm actually quite pleased with many of the additions to the Win32 API. I only wish that they had been made available sooner!

"I'm the fiber king, Dave. I'm the fiber king."
- Horatio Caine

Every so often I get an idea in my head that nags at me constantly until I try it out. This idea is a questionable but nonetheless interesting experiment that I was compelled to try over one weekend. Unless you're doing something like writing a DBMS using fibers, don't do this. This was an intellectual exercise. Caveat emptor.

I've been working on quite a bit of server-side Windows code as of late. One technique to maximize scalability on Windows NT systems is to use asynchronous I/O. While working on my I/O implementation, an idea crossed my mind: what if fibers were integrated into a thread pool? What would that look like? How would such a thread pool behave? Is it even a good idea?

Why Fibers?

Remember that a fiber is a user-mode construct that provides a safe mechanism for cooperative context switching. Though fibers can be used to implement user-level threads (such as those found in many UNIX environments), they can (in theory) have a much wider range of applications. Fibers run on top of OS threads, and since fibers are a user-mode concept the NT kernel doesn't recognize them. Fiber context switches are cheaper to execute than thread context switches and if used wisely they can maximize the utilization of the OS threads that they are running on top of. Fibers are sometimes used in databases to maximize performance; Microsoft SQL Server and Sybase SQL Anywhere both have fiber modes.

I was thinking that fibers could be used as a means to implement coroutines. I was interested in coroutines because they could be effective in eliminating the need to code state machines inside I/O completion callbacks. Instead a coroutine's context maintains the required state. As a corollary to this property, coroutines could potentially allow code that expects synchronous I/O to be integrated into an asynchronous model. Let us examine this latter idea in more detail.

Suppose I have a parser that can read in data from an arbitrary source. The parser accepts a pointer to a callback function that copies the data in from the source to a buffer. The parser is expecting the callback to be synchronous, i.e. when that callback returns, it is assumed to have completed the read request. Obviously this doesn't mesh well with asynchronous I/O, where we initiate a request and check back on it later. Using coroutines we could suspend the parser callback function, go and do something else, and then resume the callback once the I/O request has completed. This would allow us to leverage existing code that uses a synchronous I/O model without having to modify it too much (at least in theory).

The Fibrous Thread Pool

What I implemented was a thread pool that schedules fibers. I started off with a bunch of threads that wait on an I/O completion port (see this blog post by Larry Osterman for a rough idea of how this part would work). The difference is that each worker thread has been converted to a fiber. This "main fiber" is responsible for scheduling the "worker fibers." The fibers are scheduled via the pool's I/O completion port. Each completion packet that is queued to the port includes a pointer to a fiber that has been initialized to execute a work item. The main fiber then switches to the worker fiber to run it. Since fibers are cooperative, the thread will continue to execute the worker fiber until it explicitly switches back to the main fiber. This is accomplished via a suspend function that the pool provides that allows worker fibers to switch back to the main fiber for that thread. Each thread has its own dedicated main fiber, but the worker fibers do not have any particular thread affinity; they are scheduled and executed by whichever thread retrieves the completion packet.

The I/O completion port is also leveraged for asynchronous I/O purposes. If a worker fiber wants to initiate asynchronous I/O, it can bind itself to the completion port. Once the fiber initiates an asynchronous I/O request, it can suspend itself. When the I/O request completes, the fiber will be posted back to the completion port and will be scheduled as soon as a thread dequeues its packet.

Of course there are several minutiae that I have not gone into here. There are numerous conditions that must be handled correctly in order to ensure robustness and correctness.


Pitfalls

Perhaps this section should be called, "The Sarlacc Pit." There are many reasons that the uses of the fibrous thread pool (and fibers in general) are limited:

• Until Windows Server 2003, FPU context could not be saved. I can't see this as being a big deal, but if you do any floating-point arithmetic then you're out of luck.
• In general, code that uses TLS will break. The code would need to be modified use fiber local storage (FLS), which requires Windows Server 2003. Considering one of the applications of this exercise was to avoid extensively modifying synchronous code, we kind of blew it with this one.
• Corollary: The C runtime library uses TLS unless you compiled using Visual C++ 2003 (or newer) and are running on an FLS enabled OS. The CRT and C++ exceptions will give you problems unless the version requirements are met.
• Third party libraries are not likely to be fiber-safe. COM is not fiber-safe.
  
• CRITICAL_SECTIONs, mutex objects, or any other synchronization / mutual exclusion mechanism that tracks the owning thread, will not work correctly. To a critical section, two different fibers running on top of the same thread will appear to be the same unit of execution. Since critical sections allow recursive entry, they can allow multiple fibers to be inside. The mechanisms above would also experience difficulties if the holding fiber were rescheduled to a different thread. Other mechanisms that don't track the owning thread might work, but remember that they will block the fiber's underlying thread. If there is only one thread in the pool, the other fibers will not be able to execute.
  
• Code that depends on thread handles or thread IDs to be unique for different contexts will not work because multiple fibers will be sharing the same thread.
• This one goes without saying, but I'll say it anyway: GUI code will not like fibers. Mind you, GUI code doesn't like multithreading either; windows have thread affinity. If you're doing GUI stuff with a thread pool (WTF?), adding fibers would be the least of your worries.

Part II of this topic is available here.