Building Thread-Safe Applications
`
`mmaf00OfDi
`
`m
`
`0
`
`REILLY
`
`Aaron Cohen éMi/ee Woodrmg
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`

`

`
`
`Win32 Multithreaded
`
`Programming
`
`Aaron Cohen and Mike Woodring
`
`Cambridge
`
`- K6171
`
`-
`
`Pam’s
`
`- Sebastopol
`
`- Toleyo
`
`O’REILLY'”
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`

`

`Win32 Multithreaded Programming
`by Aaron Cohen and Mike Woodring
`
`Copyright © 1998 O’Reilly 8; Associates, Inc. All rights reserved.
`Printed in the United States of America.
`
`Published by O’Reilly 8: 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 Handbook logo are registered trademarks, and The
`JavaTM Series is a trademark of O’Reilly 8: Associates, Inc. The association between the image
`of a Portuguese man—o’—war and the topic of Win32 multithreaded programming is a trademark
`of O’Reilly & Associates, Inc.
`
`Microsoft, Visual C++, Win52, Windows, and Windows NT are registered trademarks of
`Microsoft Corporation.
`
`Many of the designations used by manufacturers and sellers to distinguish their products are
`claimed as trademarks. Where those designations appear in this book, and O’Reilly 8:
`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 preparation of this book, the publisher assumes
`no responsibility for errors or omissions, or for damages resulting from the use of the
`information contained herein.
`
`(E
`3&9
`
`This book is printed on acid—free paper with 85% recycled content, 15% post—consumer waste.
`O’Reilly 8; 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
`Multithreaded
`
`Programming?
`- Why Write a
`Multithreaded
`
`Program (Why Use
`Threads)?
`. Igzzdjyotto Use
`- Making the
`Transition to
`Multithreaded
`
`Programming
`
`Introduction
`
`If there he no great love in the beginning, yet
`heaven may decrease it upon hetter acquaintance,
`when we are married and have more occasion to
`lenow one another: I hope, upon familiarity will
`grow more contempt.
`
`—William Shakespeare
`The Merry Wives of Windsor
`
`it
`While multithreading has long been available on mainframes and workstations,
`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 “good citizens” and share the CPU with
`other programs to enable the user to run more than one program at the same
`time. 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 52—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
`ensures that all 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.
`
`Microsoft Corp. Exhibit 1056
`
`1
`
`Microsoft Corp. Exhibit 1056
`
`

`

`
`
`2 Chapter I: 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 Maltithreaa’ed Programming?
`
`So what is multithreaded programming? Basically, multithreaded programming is
`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.
`
`Gooa’ 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 systems 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 programs trying to run at the same time is 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 Maltithreaa’ed Program
`(Why Use Threaas)?
`
`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 Maltithreaded 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:
`
`0
`
`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 independent activities, 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 requiredfor three tasles in a single threaded application
`
`0
`
`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
`
`0 Maximum parallelization. For most multithreaded applications, where each
`thread spends a large faction of its 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.
`
`0
`
`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 purposes of this discussion,
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`

`

`
`
`4 Chapter I: Introduction
`
`
`
`start
`
`
`
`Activity
`
`Activity
`
`II
`
`
`
`Figure 1-2. Time requiredfor three tasles in a multitbreaaed 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 audio to 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 Pee/eMessage or devise some other method of
`
`0
`
`-
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`

`

`
`When Not to Use Threads
`. 5
`
`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.
`
`0 Better use of tbe 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—ROM drive, 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 CPU to 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 down into 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:
`
`0 You don’t have a really good reason. This should be the first yardstick against
`which you measure the need to incorporate a thread in any program. Very
`often, the novice multithreaded programmer will 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 answer is “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 I: 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.
`
`0
`
`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 when it runs. Having a thread that runs very infrequently, and
`that does a little 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 thread is not justified.
`
`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 Maltitbreaded
`Programming
`
`As you make the transition from a single threaded programming environment to 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...tbat 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
`unequal battle.
`—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 want to 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:
`
`0
`
`- 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
`a new thread to start executing. When the thread is “done,” it returns to the
`pool, where it 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
`
`Orr-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:
`
`0
`
`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.
`
`0 Application performance scales wit/9 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
`consume lots of system resources, or that don’t have a very complex internal archi—
`tecture. Using an optimistic approach like this one assumes it’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 disadvantages to this approach:
`
`0 Adds an element of run-time failure to your design that can be awkward to
`overcome.
`
`-
`
`Can allow the system to be bogged down if the creation of threads in the pro— K
`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,
`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.
`
`Tbread 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
`
`

`

`
`
`336 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 of this kind:
`
`0
`
`0
`
`0
`
`0
`
`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 of time.
`
`System resource use is bounded. Prevents the user’s system from becoming
`bogged down by the runaway creation of threads on the fly.
`
`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 same time. If this is a popular server,
`it might be normal for the
`server to be fully utilized most of the time. If on—demand threads were used, the
`
`Microsoft Corp. Exhibit 1056
`
`wMk.V
`
`Microsoft Corp. Exhibit 1056
`
`

`

`Windows Programming
`
`O’REILLY'"
`
`
`Win32 Multithreaded Programming
`
` g
`
`'_
`
`! Win52’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 examples to illustrate the principles of
`
`multithreaded programming. Some of the topics covered include:
`
`0 How the Windows operating systems handle threads
`
`0 Multithreading primitives in the Win52 API
`
`0
`
`Techniques for generating thread—safe dynamic link libraries
`
`0 Advanced techniques for thread synchronization
`
`0
`
`Basic scenarios for synchronizing threads
`
`- Common designs 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, Mcl4Mfc, is included
`
`for MFC compatibility.
`
`Win32 Multithreaded Programming is an essential resource for any developer interested in
`
`learning about Win52 multithreaded programming in order to create high—performance, effective
`
`applications.
`
`Illllllllllllllllll
`
`lllllllllllll ll
`
`XOO16G2FRT
`
`
`
`Win32 Multithreaded Programming
`Used, Very Good
`
`{A9
`Printed on Recycled Paper
`
`Microsoft Corp. Exhibit 1056
`
`Microsoft Corp. Exhibit 1056
`
`