I/O Completion Ports

Content

1. Introduction
2. Creating an I/O Completion Port
3. Associating a Device with an I/O Completion Port
4. How the I/O Completion Port Manages the Thread Pool
5. Simulating Completed I/O Requests

Introduction

Service application architecture can be one of the following models:

• Serial model A single thread waits for a client to make a request (usually over the network). When the request comes in, the thread wakes and handles the client’s request.

• Concurrent model A single thread waits for a client request and then creates a new thread to handle the request. While the new thread is handling the client’s request, the original thread loops back around and waits for another client request. When the thread that is handling the client’s request is completely processed, the thread dies.

The problem with the serial model is that it does not handle multiple, simultaneous requests well. If two clients make requests at the same time, only one can be processed at a time; the second request must wait for the first request to finish processing. A service that is designed using the serial approach cannot take advantage of multiprocessor machines. Obviously, the serial model is good only for the simplest of server applications, in which few client requests are made and requests can be handled very quickly. A Ping server is a good example of a serial server.

Because of the limitations in the serial model, the concurrent model is extremely popular. In the concurrent model, a thread is created to handle each client request. The advantage is that the thread waiting for incoming requests has very little work to do. Most of the time, this thread is sleeping. When a client request comes in, the thread wakes, creates a new thread to handle the request, and then waits for another client request. This means that incoming client requests are handled expediently. Also, because each client request gets its own thread, the server application scales well and can easily take advantage of multiprocessor machines.

Service applications using the concurrent model were implemented using Windows. The Windows team noticed that application performance was not as high as desired. In particular, the team noticed that handling many simultaneous client requests meant that many threads were running in the system concurrently. Because all these threads were runnable (not suspended and waiting for something to happen), Microsoft realized that the Windows kernel spent too much time context switching between the running threads, and the threads were not getting as much CPU time to do their work. To make Windows an awesome server environment, Microsoft needed to address this problem. The result is the I/O completion port kernel object.

Creating an I/O Completion Port

The theory behind I/O Completion Ports states the following:

1. The number of threads running concurrently must have an upper bound, i.e 500 simultaneous client requests cannot allow 500 runnable threads to exist, it makes sense to set the upper bound equals number of CPUs.
2. I/O completion ports were designed to work with a pool of threads. A pool of threads is created when the application initializes, and these threads hang around for the duration of the application. What is the number of threads in the pool? As a rule of thumb take the number of CPUs on the host machine and multiply it by 2. So on a dual-processor machine, you should create a pool of four threads.

HANDLE CreateNewCompletionPort(DWORD dwNumberOfConcurrentThreads) {

   return(CreateIoCompletionPort(INVALID_HANDLE_VALUE, NULL, 0,
      dwNumberOfConcurrentThreads));
}

Associating a Device with an I/O Completion Port

BOOL AssociateDeviceWithCompletionPort(
   HANDLE hCompletionPort, HANDLE hDevice, DWORD dwCompletionKey) {

   HANDLE h = CreateIoCompletionPort(hDevice, hCompletionPort, dwCompletionKey, 0);
   return(h == hCompletionPort);
}

I/O Completion Ports Internal Data structures

Device List: contains a set of device handles associated with the completion port.

I/O Completion Queue (FIFO): When an asynchronous I/O request for a device completes, the system checks to see whether the device is associated with a completion port and, if it is, the system appends the completed I/O request entry to the end of the completion port’s I/O completion queue.

Waiting Thread Stack (LIFO): As each thread in the thread pool calls GetQueuedCompletionStatus, the ID of the calling thread is placed in this waiting thread queue, enabling the I/O completion port kernel object to always know which threads are currently waiting to handle completed I/O requests. When an entry appears in the port’s I/O completion queue, the completion port wakes one of the threads in the waiting thread queue. This thread gets the pieces of information that make up a completed I/O entry.

Release Thread List and Paused Thread List: When a completion port wakes a thread, the completion port places the thread’s ID in the released thread list. This allows the completion port to remember which threads it awakened and to monitor the execution of these threads. If a released thread calls any function that places the thread in a wait state, the completion port detects this and updates its internal data structures by moving the thread’s ID from the released thread list to the paused thread list

All the threads in the pool should execute the same function. Typically, this thread function performs some sort of initialization and then enters a loop that should terminate when the service process is instructed to stop. Inside the loop, the thread puts itself to sleep waiting for device I/O requests to complete to the completion port.

How the I/O Completion Port Manages the Thread Pool

The goal of the completion port is to keep as many entries in the released thread list as are specified by the concurrent number of threads value used when creating the completion port. If a released thread enters a wait state for any reason, the released thread list shrinks and the completion port releases another waiting thread. If a paused thread wakes, it leaves the paused thread list and reenters the released thread list. This means that the released thread list can now have more entries in it than are allowed by the maximum concurrency value.

Once a thread calls GetQueuedCompletionStatus, the thread is "assigned" to the specified completion port. The system assumes that all assigned threads are doing work on behalf of the completion port. The completion port wakes threads from the pool only if the number of running assigned threads is less than the completion port’s maximum concurrency value.

You can break the thread/completion port assignment in one of three ways:

1. Have the thread exit.
2. Have the thread call GetQueuedCompletionStatus, passing the handle of a different I/O completion port.
3. Destroy the I/O completion port that the thread is currently assigned to.

Let’s tie all of this together now. Say that we are again running on a machine with two CPUs. We create a completion port that allows no more than two threads to wake concurrently, and we create four threads that are waiting for completed I/O requests. If three completed I/O requests get queued to the port, only two threads are awakened to process the requests, reducing the number of runnable threads and saving context-switching time. Now if one of the running threads calls Sleep, WaitForSingleObject, WaitForMultipleObjects, SignalObjectAndWait, a synchronous I/O call, or any function that would cause the thread not to be runnable, the I/O completion port would detect this and wake a third thread immediately. The goal of the completion port is to keep the CPUs saturated with work.

Eventually, the first thread will become runnable again. When this happens, the number of runnable threads will be higher than the number of CPUs in the system. However, the completion port again is aware of this and will not allow any additional threads to wake up until the number of threads drops below the number of CPUs. The I/O completion port architecture presumes that the number of runnable threads will stay above the maximum for only a short time and will die down quickly as the threads loop around and again call GetQueuedCompletionStatus. This explains why the thread pool should contain more threads than the concurrent thread count set in the completion port.

Simulating Completed I/O Requests

I/O completion ports do not have to be used with device I/O at all. it can be used for inter-thread communication.

The PostQueuedCompletionStatus function is incredibly useful—it gives you a way to communicate with all the threads in your pool. For example, when the user terminates a service application, you want all the threads to exit cleanly. But if the threads are waiting on the completion port and no I/O requests are coming in, the threads can’t wake up. By calling PostQueuedCompletionStatus once for each thread in the pool, each thread can wake up, examine the values returned from GetQueuedCompletionStatus, see that the application is terminating, and clean up and exit appropriately.

You must be careful when using a thread termination technique like the one I just described. My example works because the threads in the pool are dying and not calling GetQueuedCompletionStatus again. However, if you want to notify each of the pool’s threads of something and have them loop back around to call GetQueuedCompletionStatus again, you will have a problem because the threads wake up in a LIFO order. So you will have to employ some additional thread synchronization in your application to ensure that each pool thread gets the opportunity to see its simulated I/O entry. Without this additional thread synchronization, one thread might see the same notification several times.

API Table

HANDLE CreateIoCompletionPort(    HANDLE    hFile,    HANDLE    hExistingCompletionPort,    ULONG_PTR CompletionKey,    DWORD     dwNumberOfConcurrentThreads);	This function performs two different tasks: it creates an I/O completion port, and it associates a device with an I/O completion port. The dwNumberOfConcurrentThreads parameter tells the I/O completion port the maximum number of threads that should be runnable at the same time. If you pass 0 for the dwNumberOfConcurrentThreads parameter, the completion port defaults to allowing as many concurrent threads as there are CPUs on the host machine.
BOOL GetQueuedCompletionStatus(    HANDLE       hCompletionPort,    PDWORD       pdwNumberOfBytesTransferred,    PULONG_PTR   pCompletionKey,    OVERLAPPED** ppOverlapped,    DWORD        dwMilliseconds);	The thread puts itself to sleep waiting for device I/O requests to complete to the completion port
BOOL GetQueuedCompletionStatusEx(   HANDLE hCompletionPort,   LPOVERLAPPED_ENTRY pCompletionPortEntries,   ULONG ulCount,   PULONG pulNumEntriesRemoved,   DWORD dwMilliseconds,   BOOL bAlertable);	In Windows Vista, if you expect a large number of I/O requests to be constantly submitted, instead of multiplying the number of threads to wait on the completion port and incurring the increasing cost of the corresponding context switches, you can retrieve the result of several I/O requests at the same time.
BOOL PostQueuedCompletionStatus(    HANDLE      hCompletionPort,    DWORD       dwNumBytes,    ULONG_PTR   CompletionKey,    OVERLAPPED* pOverlapped);	This function appends a completed I/O notification to an I/O completion port’s queue. The first parameter, hCompletionPort, identifies the completion port that you want to queue the entry for. The remaining three parameters—dwNumBytes, CompletionKey, and pOverlapped—indicate the values that should be returned by a thread’s call to GetQueuedCompletionStatus. When a thread pulls a simulated entry from the I/O completion queue, GetQueuedCompletionStatus returns TRUE, indicating a successfully executed I/O request.

References

Windows® via C/C++, Fifth Edition

Advertisement