`Building Thread-Safe Applications
`
`iae
`
`le PSettaiabinteAmpCVSS
`RETRLTTE,
`sma
`Pinsnca:
`
`f Ai
`
`O’REILLY’
`
`Aaron Cohen & Mike Woodring
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`Win32 Multithreaded
`Programming
`
`Aaron Cohen and Mike Woodring
`
`Cambridge
`
`+ K6éln
`
`+ Paris
`
`O’REILLY*
`+ Sebastopol
`+
`Ttokyo
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`Win32 Multithreaded Programming
`by Aaron Cohen and Mike Woodring
`
`Copyright © 1998 O'Reilly & Associates, Inc. All rights reserved.
`Printed in the United States of America.
`
`Published by O’Reilly & Associates, Inc., 101 Morris Street, Sebastopol, CA 95472.
`
`Editor: Ron Petrusha
`
`Production Editors: Jane Ellin and Nancy Crumpton
`
`Printing History:
`
`January 1998:
`
`First Edition
`
`Nutshell Handbook and the Nutshell Handbooklogo are registered trademarks, and The
`Java™ Series is a trademark of O’Reilly & Associates, Inc. The association between the image
`of a Portuguese man-o’-warand the topic of Win32 multithreaded programmingis a trademark
`of O'Reilly & Associates, Inc.
`
`Microsoft, Visual C++, Win32, Windows, and WindowsNT are registered trademarks of
`Microsoft Corporation.
`
`Manyof the designations used by manufacturers andsellers to distinguish their products are
`claimed as trademarks. Where those designations appear in this book, and O'Reilly &
`Associates, Inc. was aware of a trademark claim, the designations have been printed in caps
`or initial caps.
`.
`
`While every precaution has been taken in the preparationof this book, the publisher assumes
`no responsibility for errors or omissions, or for damages resulting from the use of the
`information contained herein.
`
`eS
`
`
`
`This bookis printed on acid-free paper with 85% recycled content, 15% post-consumerwaste.
`O’Reilly & Associates is committed to using paper with the highest recycled content available
`consistent with high quality.
`
`ISBN: 1-56592-296-4
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`In this chapter:
`¢ What Is
`Mutltitbreaded
`Programming?
`* Why Write a
`Multithreaded
`Program (Why Use
`Threads)?
`
`WebsNetto Use
`* Making the
`Transition to
`Multithreaded
`Programming
`
`Introduction
`
`If there be no great love in the beginning, yet
`heaven may decrease it upon better acquaintance,
`when we are married and have more occasion to
`know one another: I hope, upon familiarity will
`grow more contempt.
`—William Shakespeare
`The Merry Wives of Windsor
`
`While multithreading has long been available on mainframes and workstations,it
`is a new capability for personal computers. Prior to the first release of Windows
`NT, 16-bit versions of the Microsoft Windows operating system provided only a
`crude form of multitasking known as cooperative multitasking. With cooperative
`multitasking, all programs needed to be “goodcitizens” and share the CPU with
`other programs to enable the user to run more than one program at the same
`ume. Unfortunately, most software was not always so well behaved, and the
`result was that running more than one program at a time was often more trouble
`than it was worth. All this changed for the better with the 32-bit Windows oper-
`ating systems, Windows NT and Windows 95, which support preemptive
`multitasking and multithreading. Applications can now be written pretty much as
`if they are the only program running on the system, and the operating system
`ensuresthatall of the programs share the CPU and behave themselves.
`
`With the new multithreading capabilities came new challenges for programmers.
`Most PC programmers were raised on DOS and other simple operating systems.
`Making the transition to Win32 programming and taking full advantage of the
`advanced features of the 32-bit operating systems can be difficult. Programmers
`who have not had experience with more advanced systems may not have been
`exposed to even the basic concepts of multitasking and multithreading,
`
`1
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`2 Chapter 1: Introduction
`
`In order to provide good grounding for the reader, this chapter will explain what
`multithreading is, and why you would want to use it. Because multithreading is
`not a solution to every problem, we will then discuss situations in which you
`would not want to use multithreading. The chapter ends with an introduction to
`the basic mindset you must have in order to write correct multithreaded programs.
`
`What Is Multithreaded Programming?
`So what is multithreaded programming? Basically, multithreaded programmingis
`implementing software so that two or more activities can be performed in parallel
`within the same application. This
`is accomplished by having each activity
`performed by its own thread. A thread is a path of execution through the soft-
`ware that has its own call stack and CPU state. Threads run within the context of
`a process, which defines an address space within which code and data exist, and
`threads execute. This is what most people think of when they refer to “multi-
`threaded programming,” but
`there really is a lot more to programming in a
`multithreaded environment.
`
`Good multithreaded programming involves more than simply creating additional
`threads. We can loosely divide the issues into two categories. The first
`issue
`involves writing your software to use multiple threads in a useful and efficient
`manner. Carefully written multithreaded programs should be superior to single
`threaded designs in terms of execution time, user responsiveness, architecture, or
`all three.
`
`The second issue is awareness of the operating system’s rules that govern the
`behavior of your program while it’s running, as well as understanding how your
`program interacts—directly or indirectly—with other programs running at
`the
`same time. You need to understand not just how the operating system will treat
`your program, but how it will
`treat your program when other programs are
`running at the same time. Likewise, understanding the impact your program has
`on other programstrying to run at the same timeis just as important.
`
`Becoming knowledgeable and adept at both aspects of multithreaded program-
`ming will be crucial
`to your success as a programmer on Windows 95 and
`Windows NT. This book will cover both aspects of writing good multithreaded
`programs.
`
`Why Write a Multithreaded Program
`(Why Use Threads)?
`So why would you want to add extra threads to your programs? After all, you’ve
`been getting by just
`fine without support
`from Windows for
`incorporating
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`Why Write a Multithreaded Program (Why Use Threads)? 3
`
`multiple threads into your programs. Why start now? It turns out that there are
`some distinct advantages to using multiple threads in your programs. Some of
`those advantages include:
`
`e
`
`Increased parallelization. Very often, programs need to accomplish more
`than one task as a result of some initial event (like a user pressing a button,
`or a service request coming in from another machine in the network). If these
`tasks are essentially independentactivities, the performance of an application
`can be improved by having a separate thread take care of performing each
`activity. In a single threaded application, the total length of time required to
`accomplish three tasks is the sum of the times that it takes to accomplish each
`task serially, as shown in Figure 1-1.
`
`
`
`Figure 1-1. Time requiredforthree tasks in a single threaded application
`
`e
`
`time
`length of
`the total
`In a multithreaded program,
`Faster processing.
`required to accomplish all three tasks is just the time it takes to complete the
`longest of the individual tasks.” This is illustrated in Figure 1-2.
`
`¢ Maximum parallelization. For most multithreaded applications, where each
`thread spends a large faction ofits time waiting for an I/O operation to com-
`plete, or a kernel object to become signaled, maximum parallelization of the
`kind illustrated by this diagram can be achieved. In other words, if the thread
`performing Activity A spends a significant portion of the time waiting for
`some I/O operation to complete, the thread performing Activity B can accom-
`plish useful work while thread A is blocked. And on multiprocessor
`machines, the operating system will be able to execute threads truly concur-
`rently to one another by allowing one thread to run on each CPU.
`
`e
`
`Simplified design. A well-designed multithreaded program can use threads to
`actually simplify the design of the program by dedicating a unique thread to
`
`* There is some additional system overhead when the CPU switches between threads. For most applica-
`tions, it is a small fraction of the total CPU load and will be ignored for the purposesofthis discussion.
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`4 Chapter 1: Introduction
`
`
`
`Start
`
`Finish
`
`
`
`Activity
`
`Activity
`
`|"
`
`
`
`Figure 1-2. Time requiredfor three tasks in a multithreaded application
`
`each well-defined, independent job. For example, an audio playback program
`can be designed to use one thread for reading compressed audio from a disk
`file, a separate thread for decompressing the audio stream, and a third thread
`for playing back the audio data to the speakers. This design allows the file-
`reading thread, which will spend a large portion of its time blocked waiting
`for disk I/O operations to complete, to read ahead from the input file while
`the second thread is decompressing audio data that was previously read from
`disk. Likewise, the playback thread can be playing the uncompressed audio
`stream to the speaker smoothly without concern for the other two activities. A
`single threaded application would have to interleave small portions of disk
`reads, decompression, and playback in an unnecessarily complicated manner
`in order to present equally smooth-sounding audioto the user.
`Increased robustness. By using multiple threads within a program,it’s possible
`to increase the robustness of an application by isolating critical subsystems
`into their own thread (or threads) of control. For example, you might want to
`ensure that even if subsystem A fails as a result of invalid user input, sub-
`system B (the thermonuclear device temperature monitoring thread) can con-
`tinue to run unabated.
`
`Increased responsiveness to the user. By using multiple threads to separate the
`user interface portions of your program from the rest of your program, you
`can increase the responsiveness to the user, even if the program is “busy”
`doing something. For example, a single threaded Internet browser application
`that wants to allow the user to cancel bringing in data from a large web page
`would have to periodically call PeekMessage or devise some other method of
`
`¢
`
`°
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`When Not to Use Threads 35
`
`interrupting the data transfer. By performing network data transfers on a back- =
`ground thread,
`the user interface thread running at a higher priority can
`instantly react to the user’s desire to cancel the lengthy operation.
`Better use of the CPU. A lot of the work done by Windows programs happens
`in short bursts in between long waits for something to occur. Waiting for a
`block of data to be read from the CD-ROMdrive, or for a buffer of data to be
`written to a COM port, are both examples of activities that include plenty of
`built-in waits for devices operating at speeds much slower than the CPUto fin-
`ish a particular job. By performing these activities on individual threads, the
`operating system can do a better job of keeping the CPU busy doing useful
`work while I/O bound threads are waiting for these slow devices to finish
`doing something useful.
`
`There are other good reasons to incorporate the use of multiple threads in your
`applications, but these are the most fundamental.
`
`When Not to Use Threads
`
`Just because an operating system supports the use of multiple threads in a
`program doesn’t necessarily mean you should have multiple threads in your
`program. In fact, at
`times there are disadvantages to using multiple threads in
`order to accomplish a job. When most programmers discover multithreaded
`programming for the first
`time,
`they’re almost giddy with excitement. Every
`problem solved by their programs is broken downinto its own thread. And who
`can blame them?It’s just plain fun to watch your program work on more than one
`chore at a time,
`like so many little automated robots running around a factory
`floor busily doing their assigned job without regard for other activities going on in
`the plant. While there are many advantages to using multiple threads in your
`programs, adding additional threads also introduces complexity and the possibility
`of encountering new classes of errors (deadlock, starvation, etc.) that are not part
`of the landscape of single threaded programming. Here are some guidelines to
`help you decide when not to incorporate the use of multiple threads in your
`application:
`
`You don’t have a really good reason. This should be thefirst yardstick against
`which you measure the need to incorporate a thread in any program. Very
`often, the novice multithreaded programmerwill not have a good reason to
`be adding a new thread into a program—it
`just happens to be fun. And
`what's the harm? The answeris “potentially,
`lots.” The inclusion of just one
`extra thread in an otherwise single threaded application brings with it a
`whole nest of design, implementation, and debugging problems that need to
`be considered.
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`Chapter 1: Introduction
`
`For example, you shouldn’t divide a job between two threads when each
`thread could not otherwise stand on its own. In other words, if two threads
`are involved in doing job X, and the absence of one thread or the other
`would preclude job X from being done, you probably don’t have a good rea-
`son to involve two separate threads.
`
`¢
`
`The operating system overhead involved with scheduling and otherwise deal-
`ing with a thread, when taken together with the frequency with which the
`thread does its job, outweighs the amount of work actually performed by that
`thread. In other words, if a thread does only a little bit of work, but does it
`very often, the overhead incurred by the operating system as it tries to sched-
`ule your thread to run many times per second can outweigh the other bene-
`fits you might have sought
`to gain by introducing the thread into your
`program. Keep in mind that this does not mean that each thread has to do
`lots of work whenit runs. Having a thread that runs very infrequently, and
`
`that doesalittle bit of work when it does run, is not going to cause system
`performance to drop.
`It’s threads that wake up and run very often, and that
`do only a little bit of work when they do run, that will degrade the perfor-
`mance of not only your application, but the machine as a whole.
`
`threads will outweigh the actual
`the overhead of additional
`For example,
`work performed when threads are used in an essentially serial manner. If the
`threads in your application always run synchronously with respect to one
`another, the overhead involved with scheduling each thread to run and com-
`municating information between each threadis notjustified.
`
`There are some other more subtle reasons why including multiple threads in the
`design of a program might not be the best for the success of your application.
`Because a multithreaded program involves a new class of problems, the skill sets
`of the developers actually implementing the software play into the decision to
`incorporate multiple threads in an application. Just because the Win32 API docu-
`ments all the functions needed to write multithreaded software doesn’t mean that
`a programming team has everything they need to successfully develop a good
`multithreaded application.
`
`Making the Transition to Multithreaded
`Programming
`As you makethe transition from a single threaded programming environmentto a
`multithreaded one, you'll need to increase the scope with which you look at a
`problem.It will no longer be enough to know how to manipulate data structures
`or to correctly pass parameters in order to accomplish some useful
`task. For
`example, when you’re looking at a function’s implementation, you need to under-
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`In this chapter:
`* On-Demand Threads
`¢ Thread Pools
`
`Advanced Thread
`Management
`Techniques
`
`It is quite clear...that you are not experienced in
`this matter ofadventures. They are giants, and if
`you are afraid, go away and say yourprayers,
`whilst I advance and engage them infierce and
`unequalbattle.
`—Don Quixote
`Up to this point in the book, we've illustrated various ways to apply and control
`the use of threads in your programs. In each of our examples, we have focused
`on either the mechanics of protecting resources in the presence of multiple
`threads, or ways to apply the use of threads to a particular class of problem. As
`you start to develop multithreaded applications, you'll find that a thread itself is
`really a resource just like any other. In other words, you might wantto limit the
`number of threads in your application at any one time, or pre-allocate your
`threads at the start of your program to ensure that when you need a thread, you
`won't run the risk of failing to create a thread on the fly. When viewed as a
`resource like any other, there are two common approaches to managing multiple
`threads in your applications:
`© On-demand. Threads are created on an as-needed basis during the lifetime of
`a program, and deleted when they're no longer required.
`Thread pools. The threads needed by the program are created in a batch (or
`batches) early on, and stay idle until needed. To “start” a thread just involves
`resuming the execution of an idle thread in the pool at the location you want
`4 new thread to start executing. When the thread is “done,” it returns to the
`pool, whereit remains idle until needed again.
`There are advantages and disadvantages to each approach, as we'll see shortly,
`and the decision to use one. or the other will depend on the requirements of the
`application being developed.
`
`*
`
`334
`
`.
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`Thread Pools 335
`
`On-Demand Threads
`
`This is the most simplistic approach to thread resource management. All of the
`examples presented so far in this book have used this technique. The basic idea
`is pretty straightforward: create a thread when you need one, and delete it when
`you're done. This includes the direct creation of a thread for a specific purpose,
`as well as the creation of threads internal to active objects. Here are some of the
`advantages to this approach:
`
`¢
`
`Simple. You can’t get much simpler than this. In fact, by using a library like
`Mcl, creating a thread is as easy as declaring a local variable.
`¢ Application performance scales with processor speed and processor count. In
`other words, if your application creates threads as needed, and might at one
`point have lots of threads active,
`the performance of the application can
`improve by running on a faster machine, or a machine with more processors
`that is running Windows NT.
`
`The simplicity of this approach fits well with small applications that don’t
`consumelots of system resources, or that don’t have a very complex internal archi-
`tecture. Using an optimistic approach like this one assumesit’s unlikely that you'll
`ever fail to create a thread at run-time. There is a price to pay for this simplicity,
`however. Here are some of the disadvantagesto this approach:
`
`e Adds an element of run-time failure to your design that can be awkward to
`overcome.
`
`*
`
`Can allow the system to be bogged downif the creation of threads in the pro- =
`gram isn’t capped somehow.
`
`When you design your program so that it creates threads on the fly, unrelated
`activities on the host system may affect
`its ability to create a new thread. This
`means that even though your program might never fail
`to create a thread the
`whole time you’re developing and testing it,
`it might fail in strange ways, or at
`seemingly random places, on a user's system that is particularly burdened with
`other applications that make extensive use of large numbers of threads. Likewise, or
`if your program doesn’t voluntarily cap the creation of new threads at some arbi-
`trary limit, your program could get carried away and create so many threads that
`the user’s system becomes saturated with scheduling activities and doesn’t have
`any cycles left over to actually do anything useful.
`
`Thread Pools
`
`The basic idea behind a thread pool is to define an object that represents a batch
`of threads that have been reserved for use sometime in the future. This is similar
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`
`
`
`
`3306 Chapter 10: Advanced Thread Management Techniques
`
`to the idea of creating buffer pools (or heaps) that contain pre-allocated buffers
`that can be used and returned to the pool over the lifetime of your program
`without having to deal with the element of failure that is introduced by dynami-
`cally allocating buffers on an as-needed basis. A thread pool is an object that you
`can initialize to have a pre-created set of threads that are idle and that can be
`dispatched to arbitrary places in your program to handle a job, and then be
`returned to the pool when they’re no longer needed. Here are some of the advan-
`tages to thread pools ofthis kind:
`
`e
`
`~~ey
`
`Microsoft Corp. Exhibit 1056
`
`e
`
`e
`
`*
`
`Confines the element of failure to create a thread to an initialization activity
`and allows the thread resources needed by the application to be reserved
`ahead oftime.
`System resource use is bounded. Prevents the user’s system from becoming
`bogged down by the runawaycreation of threads on thefly.
`Fast thread dispatching. Dispatching an existing thread to a perform a new
`job in the program can be done very quickly and without the cost normally
`associated with creating a brand new thread.
`Idle threads in the pool do not consume CPU cycles until they are dispatched
`to do a job.
`For mission-critical applications that need to be able to reserve all the resources
`they'll ever need up front when the program is initializing, the first advantage to
`thread pools is an important one. By using a pool of preallocated threads, such
`an application is better able to consistently perform its function independently of
`how the user’s system is being used by other applications. The second advantage
`to the use of a thread pool protects the user’s system from being attacked by a
`program that tries to create lots and lots of threads, perhaps unintentionally. The
`third advantage to using a thread pool—fast dispatching—comes into play with
`applications that need to start new threads up very often in order to do a very
`short job. If dynamic thread creation were used, the overhead involved in creating
`a thread and terminating a thread might far outweigh the actual work done by the
`thread while it was alive. By using a thread pool, you can start up a “new”thread
`very quickly simply by resuming its execution at a particular place in the code.
`The last advantage worth noting is that the threads in a thread pool that are not
`being used actually remain suspended so that they consume no CPU cycles if they
`are not doing anything useful at the moment.
`One example of a multithreaded application that could leverage a thread pool of
`this kind might be an Internet FTP server application. Such an application might
`want to allow a finite number of users (250, for example) to connect to the
`machine at the sametime. If this is a popularserver, it might be normal for the
`server to befully utilized most of the time. If on-demand threads were used, the
`
`Microsoft Corp. Exhibit 1056
`
`
`
`Windows Programming
`
`
`
`O’REILLY
`
` #
`
`Win32 Multithreaded Programming
`Many Windowsdevelopersstill write code as if their application is a single entity
`that, while it is running, has complete control of all system resources. This legacy
`from the days of DOS meansthat developers frequently fail to take advantage of
`7
`i | Win32’s support of multiple threads of execution to enhance their application’s
`:
`responsiveness and performance. But multithreaded programming means more than adding threads
`to perform some processing in the background;it also requires that the code be thread-safe.
`
`Win32 Multithreaded Programming explores the concepts of multithreaded programming to
`provide the developer with the knowledge necessary to skillfully construct efficient and complex
`applications. From basic thread synchronization using mutexes and semaphores to advanced topics
`like creating reusable thread pools or implementing a deferred processing queue, the book uses
`real-world applications and carefully constructed examplesto illustrate the principles of
`multithreaded programming. Some of the topics covered include:
`
`¢ How the Windows operating systems handle threads
`
`® Multithreading primitives in the Win32 API
`
`*
`
`Techniques for generating thread-safe dynamic link libraries
`
`* Advanced techniques for thread synchronization
`
`e
`
`*
`
`Basic scenarios for synchronizing threads
`
`Commondesigns for building multithreaded user interfaces
`
`¢ Debugging multithreaded applications
`
`The CD-ROM accompanying this book features Mcl, the authors’ C++ class library for multithreaded
`programming, which both wraps multithreaded API functions and easily supports more complex
`multithreaded scenarios. For programmers using MFC, an additional library, Mcl4Mfe, is included
`for MFC compatibility.
`
`Win32 Multithreaded Programming is an essential resource for any developer interested in
`learning about Win32 multithreaded programming in order to create high-performance, effective
`applications.
`
`X0016G2FRT
`
`Win32 Multithreaded Programming
`Used, Very Good
`
`
`
`EY
`
`Printed on Recycled Paper
`Microgoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`