# Windows Thread Pool with an Intrusive Priority Queue

A C++ systems-programming project built around five reusable Visual Studio projects: a custom Windows thread pool, a priority-queue DLL, an intrusive doubly linked list, a diagnostic library, and a client that demonstrates and tests their integration.

The implementation uses Win32 threads, critical sections, a semaphore, and thread handles rather than the Windows thread-pool API or `std::async`. Scheduling policy is supplied through callbacks, keeping the thread pool independent of the priority queue.

## Design documents

- [HLD.md — high-level design](HLD.md): a friendly overview of the projects, architecture, job lifecycle and ownership rules.
- [LLD.md — low-level design](LLD.md): function-by-function thread-pool flows, queue/list integration, synchronization, monitoring and safe shutdown.

## Interactive presentation and native measurements

Open [`index.html`](index.html) directly or publish the repository as a static site. It includes a sectioned technical write-up, a configurable **educational scheduler simulation**, and a **separate real native benchmark capture**. The browser model is not a native trace, and its logical ticks are not timings.

The performance harness is **C17 only**, in `ThreadPool/PerformanceTests1/ThreadPoolNativeBenchmarks.c`, compiled with `/TC /std:c17`. It uses the real DLL APIs, QPC, two discarded warmups and seven measured repetitions for thread lifecycle baselines, 1/4/8-worker throughput, three priority mixes, and 16-producer stress. Each complete capture validates 182 measured rows and 2,523,584 tasks (1,008,000 in many-producer stress). All observed slowdowns and variation are retained, not hidden.

- [Measurement boundaries, actual results, instrumentation and reproduction](docs/BENCHMARKS.md).
- [Static-site walkthrough, accessibility and model tests](docs/PRESENTATION.md).
- [Raw QPC samples](assets/native-runs.csv) and [sanitized environment/results JSON](assets/benchmarks.json).

Run `powershell -File Build/Benchmark.ps1 -Platform x64 -Publish` from the repository root to rebuild and replace the capture. This runs a standalone C executable, with no C++ test framework, using isolated `NativeBenchmark=true` outputs. Trace/info call sites are disabled consistently in every module only for this opt-in measurement build; ordinary diagnostics and safe shutdown behavior remain unchanged. The C artifact is version 2 and has freshly measured results; the previous C++ artifact/capture is archived as inactive text under `docs/history/cpp-harness/`. No scheduler optimization or language-conversion speedup is claimed.

## Projects and dependencies

| Project | Output | Responsibility |
| --- | --- | --- |
| `Intrusive_LinkedList` | Static library | Caller-owned intrusive nodes; head/tail insertion, removal, and pointer-based search |
| `Debugger` | Static library | Log levels, source-location macros, assertions, and elapsed-time logging |
| `PriorityQueue` | DLL | Three priority levels backed by intrusive FIFO lists; depends on the list and debugger libraries |
| `ThreadPool` | DLL | Worker management, submission, diagnostics, completion reporting, and safe shutdown; links the debugger library and uses the list's node type |
| `ClientApp` | Console executable | Queue adapters, explicit priority-queue DLL loading, stress demonstration, and regression tests |

The client links ThreadPool through its import library. It loads `PriorityQueue.dll` with `LoadLibraryExW` and resolves its six exported operations with `GetProcAddress`. Its direct list tests link `Intrusive_LinkedList.lib`.

### Repository layout

- `ThreadPool/ThreadPool.slnx` — solution containing the five runtime projects plus an additional native measurement host.
- `<Project>/Source/` — active implementations and public headers.
- `<Project>/Resources/` — preserved design documents, earlier code iterations, and historical output where available.
- `Build/ProjectSettings.props` — relative include paths and shared output settings.
- `Build/Test.ps1` — repeatable rebuild and executable-test matrix.
- `ThreadPool/PerformanceTests1/` — additional C17 console measurement project, exercising the real DLLs.
- `Build/Benchmark.ps1` — isolated native Release measurements and sanitized static-site export.
- `index.html`, `assets/`, `docs/` — no-package presentation, simulation, native results and methodology.
- `artifacts/bin/<Platform>/<Configuration>/` — generated executable, DLLs, and libraries.
- `artifacts/TestResults/` — generated build and test logs.

Project references control build order. Neither building nor running requires the original internship directory.

## Why an intrusive linked list?

An intrusive list embeds its links directly in the object being stored. Here, `NODE` contains `pPrev` and `pNext`; `LIST_HEAD` contains head/tail pointers and a critical section. `CONTAINING_RECORD` recovers the enclosing object from its embedded node.

This avoids a separate container-node allocation for every insertion and allows the same list implementation to hold different payload types. Head/tail insertion and removal are O(1); pointer-based search is O(n). The list is linear, doubly linked, and not circular.

The tradeoff is explicit ownership discipline:

- The caller allocates and owns each enclosing object.
- A particular embedded node must not belong to multiple lists at once or be inserted twice without removal.
- Objects must remain alive while linked; removal clears the detached node's links.
- Search does not extend an object's lifetime after the operation unlocks.
- List operations synchronize access, but initialization and destruction require exclusive lifecycle ownership.

Direct queue tests embed a node in client work data. The thread pool instead allocates an internal `WORK_ITEM` containing a callback, context, scheduling key, completion callback, and embedded node. The pool frees that internal wrapper; the caller remains responsible for the context.

## Priority-queue design

`PRIORITY_QUEUE` holds three intrusive lists:

1. `PRIORITY_HIGH` (0)
2. `PRIORITY_MEDIUM` (1)
3. `PRIORITY_LOW` (2)

Enqueue appends to the selected list. Dequeue scans from HIGH to LOW and removes the first available head. This gives FIFO order within a priority and highest-priority-first selection among queued jobs. It is not a heap: insertion is O(1), and dequeue is O(P), where P is the fixed three-level count.

A queue-wide critical section serializes priority selection, list mutation, and count publication. Individual lists retain their own locks for standalone use. Cleanup detaches nodes but does not free caller-owned payloads; all users must stop accessing the queue before cleanup.

Priority is a dequeue policy, not preemption. An already-running low-priority job is not interrupted by a new high-priority job, and execution/completion order across multiple workers can differ from dequeue order. Continuous high-priority traffic can starve lower priorities; aging and fairness are not implemented.

## Thread-pool design and execution flow

1. ClientApp initializes a priority queue and passes enqueue/dequeue adapters to `InitializeThreadPool`.
2. `SubmitWork` creates a work wrapper and enqueues it with an opaque `ULONG` scheduling key. The adapters interpret that key as a priority.
3. The pool publishes the queued job and pending count under its lock, then releases a semaphore permit.
4. A worker wakes, checks shutdown state, dequeues a job, and records its diagnostic slot under the pool lock.
5. The worker invokes the callback outside the lock and reports the outcome through the optional completion callback.

The pool starts with a configurable core worker count and grows when pending work exceeds idle capacity. Surplus healthy workers retire after five seconds idle. The demonstration uses 3 core workers and a healthy-worker limit of 12. A hard cap of 16 bounds all live workers, including overdue workers and their replacements.

### Diagnostics and overdue work

Tracking slots record thread ID, start time, scheduling key, context, and completion callback. `DumpThreadPoolState` reports a synchronized snapshot. Periodic calls to `ReapStuckWorkers` mark jobs exceeding the configured threshold and may create replacement capacity. There is no internal monitoring thread: ClientApp supplies one.

Completion statuses are:

- `WORK_STATUS_SUCCEEDED` — the work callback returned normally.
- `WORK_STATUS_FAILED_STUCK` — the monitor flagged the callback as overdue; it may still be running.
- `WORK_STATUS_CANCELLED` — shutdown removed the job before execution.

Worker completion and stuck reporting share the pool lock so only one outcome is selected. Completion callbacks execute outside that lock. An overdue callback is **not terminated** and is not automatically retried. Retrying it is a caller decision and requires work that is safe to repeat.

### Shutdown and lifetime contract

`ShutdownThreadPool` rejects new submissions, cancels queued jobs, and joins every worker before releasing handles and synchronization objects. Joining actual thread handles ensures no worker is still logging or returning through pool code when shutdown completes.

- Stop and join external producer and monitor threads before shutdown.
- Keep the pool, queue, callback code, completion code, and contexts alive until shutdown returns. A `FAILED_STUCK` notification alone does not make its context safe to free.
- Running callbacks must eventually return. Shutdown may wait indefinitely for a permanently hung callback; it does not forcibly terminate threads.
- Do not call shutdown from a work or completion callback. Do not concurrently destroy or reinitialize the pool.
- Callbacks must not let exceptions escape across the worker boundary.
- After shutdown, do not call pool APIs until it has been reinitialized.

After shutdown returns, ClientApp can safely clean up its queue and unload the priority-queue DLL.

## Where the debugger library fits

`LOG_TRACE`, `LOG_INFO`, `LOG_WARN`, `LOG_ERROR`, and `LOG_CRITICAL` capture file, line, and function information. Messages include timestamps, process IDs, and thread IDs, and go to the console and `OutputDebugString`. An initialized file sink additionally receives messages. `DBG_ASSERT` breaks into the debugger on failure; scope timers report elapsed milliseconds.

A statically initialized SRW lock protects each linked logger instance, including calls before file logging is initialized. Redirected output does not assume console attributes are available.

Because Debugger is a **static** library, ClientApp and each DLL have separate logger state. ClientApp's `clientapp.log` contains its own logger instance's messages; it is not a combined file sink for every DLL. The test runner captures process stdout to collect messages from all components.

## Build and run

### Prerequisites

- Windows and Visual Studio 2026 with **Desktop development with C++**.
- MSVC toolset **v145** and **Windows SDK 10.0.26100.0**.
- C++20 support; PowerShell is used by the test runner.
- C17 support for the performance executable; no C++ test-framework dependency. Node is optional for browser-model tests only.

The SDK version is pinned for reproducibility. On the validation machine, the floating `10.0` selection chose SDK 10.0.28000.0, whose manifest tool failed to start with `0xC0000135`, causing `LNK1327`. SDK 10.0.26100.0 worked; manifest generation remains enabled.

### Visual Studio

1. Open `ThreadPool/ThreadPool.slnx`.
2. Set **ClientApp** as the startup project.
3. Select Debug or Release and x64 or x86 (the project platform for x86 is `Win32`).
4. Build the solution, then run with **Ctrl+F5**.

Keep `ClientApp.exe`, `ThreadPool.dll`, and `PriorityQueue.dll` together in the generated output directory. Queue DLL lookup uses the application's directory, not an arbitrary current working directory.

### Command line

From the repository root, in a Visual Studio Developer PowerShell:

```powershell
msbuild .\ClientApp\ClientApp.vcxproj /t:Build /p:Configuration=Debug /p:Platform=x64
.\artifacts\bin\x64\Debug\ClientApp.exe --self-test
.\artifacts\bin\x64\Debug\ClientApp.exe
```

With no arguments, the client runs the full demonstration and writes `clientapp.log` in its working directory. `--self-test` runs regression checks. Failed checks return a nonzero exit code.

## Tests and verified results

Run all Debug/Release and x64/Win32 rebuilds and tests from a regular PowerShell:

```powershell
.\Build\Test.ps1 -Stress
```

For a shorter single-configuration check:

```powershell
.\Build\Test.ps1 -Platform x64 -Configuration Debug
```

The runner locates Visual Studio through `vswhere`, uses a timeout for each executable run, captures stdout/stderr, checks exit codes and pass markers, and rejects failure diagnostics. These are executable-based tests rather than tests registered in Visual Studio Test Explorer.

Regression coverage includes empty-list operations, list links/search/removal, invalid queue arguments, FIFO priority ordering, count updates, concurrent producer/consumer delivery, exactly-once completion, repeated stuck reporting, shutdown waiting for running work, cancellation of pending work, and submission rejection during shutdown. Normal and stuck shutdown scenarios each run ten times.

The full client uses a fixed stress-plan seed and exercises:

1. Direct priority-queue ordering and argument checks.
2. 200 jobs submitted by concurrent producers, with multiple workers and a monitor; selected jobs deliberately exceed the stuck threshold.
3. Immediate shutdown of a fresh pool with 40 jobs, checking queued cancellation and complete worker exit.

Verified on the development machine:

| Platform | Configuration | Rebuild | Regression suite | 200-job stress + shutdown |
| --- | --- | --- | --- | --- |
| x64 | Debug | Passed | Passed | Passed — 200/200 completed |
| x64 | Release | Passed | Passed | Passed — 200/200 completed |
| Win32 | Debug | Passed | Passed | Passed — 200/200 completed |
| Win32 | Release | Passed | Passed | Passed — 200/200 completed |

All four rebuild logs contained no compiler warnings or errors; all eight executable runs passed with zero failed checks and empty stderr logs. This validates the exercised scenarios, not every possible thread interleaving or resource-exhaustion condition. Deliberate invalid-input tests produce expected error-level log messages; overdue-job tests produce expected warnings.

## Preserved design and iteration resources

The implementation originated in the corresponding internship projects. Active code was adapted to local project references and corrected during validation; historical resources remain unchanged.

- [Debugger resources](Debugger/Resources/) — early logging/debug macro examples from Assignment_1; the original empty `log_macro_code.txt` is preserved.
- [Intrusive linked-list resources](Intrusive_LinkedList/Resources/) — six stages from singly linked lists through intrusive-library integration, from Assignment_3.
- [Priority-queue design](PriorityQueue/Resources/PriorityQueue_Design.md).
- [Thread-pool design](ThreadPool/Resources/ThreadPool_Design.md).
- [Client resources](ClientApp/Resources/) — Assignment_6 design, output walkthrough, code iterations, stress examples, starvation planning, a kernel-mode discussion, and historical output.

All 19 imported resource files were checked against their originals and matched byte-for-byte. Historical documents may refer to old project names, paths, or bounded/leaking shutdown behavior. This README and the active `Source` files describe the current implementation; kernel-mode thread pools and starvation mitigation are reference material, not implemented features.