C# – Multi-threading in C# .NET Windows Service

You should have a look at the thread pool pattern in Wikipedia, I think this is what you are looking for. The trick is to create n threads once when your service starts, avoiding the overhead of thread creation (see this question on SO) during runtime.

As for your workflow, you may want to consider switching the first two steps:
First check if there are records to process, and if there are, see if your thread pool has a free thread. This is an optimisation problem, you want to reach the decision no processing (because there is no data, or no resources for it) with as little effort as possible. If you reach this decision more often because there is no data to process, check for this first.

Some will argue that this is premature optimisation, but I personally prefer to err a little more on the premature side.

One of the main reasons for using threads even in a completely CPU-bound process is to allow interaction or update progress output via a UI of some sort. While running the calculation in the foreground without allowing interaction would be more efficient, the slight cost of task switching and handling UI events usually outweighs the penalty of forcing a user to wait indefinitely for a process.

Another case where running multiple threads on a single core would be more efficient is when a multi-stage process involves one stage that produces a lot of temporary results that are processed by a later stage. Running these stages in series might exhaust available memory. Running them in parallel allows the second stage to free up memory as it processes results.

Finally, as we add more caches to our architectures, threads can often become idle when a cache miss occurs while accessing memory. This gives some time for another thread to activate and do some work.

The main benefits of multi-threading over multi-processing include

• shared memory
• less overhead for context-switching
• easier abstraction

Most modern operating systems provide some method of sharing memory across processes, too. Even still, allowing the OS or virtual machine to shift threads across multiple processors when available is very appealing. For example, when you move a multi-threaded Java program from a single-core machine to one with multiple cores, the JVM will automatically make use of those other cores.