Shutting down a windows service that has threads

From the MSDN link you provided:

A thread is either a background thread or a foreground thread. Background threads are identical to foreground threads, except that background threads do not prevent a process from terminating. Once all foreground threads belonging to a process have terminated, the common language runtime ends the process. Any remaining background threads are stopped and do not complete.

Setting a thread's IsBackground property to true will allow your Windows service to terminate immediately once the OnStop() callback is finished executing and all foreground threads (if any) have exited. The background threads will be stopped wherever they happen to be in their execution state, so if these threads need to terminate gracefully, you'll need to use a different mechanism.

One way to do this would be to use foreground threads that check a ManualResetEvent object that signals the threads to shutdown. In your OnStop() callback, set the ManualResetEvent and then wait for the threads to exit using Join(). If they don't exit in a reasonable time, you can forcefully terminate them since the process is exiting.