throbber
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
`
`

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket