Handout 15 1Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 — Principles of Computer SystemsHandout 15 March 5, 1997____________________________________________________________________________Programming with ThreadsThe attached paper by Andrew Birrell, Introduction to Programming with Threads, appeared asreport 35 of the Systems Research Center, Digital Equipment Corp., Jan. 1989. A somewhatrevised version appears as chapter 4 of Systems Programming with Modula-3, Greg Nelson ed.,Prentice-Hall, 1991, pp 88-118.Read it as an adjunct to the lecture on practical concurrency. It explains how to program withthreads, mutexes, and condition variables, and it contains a lot of good advice and examples.d i g i t a lSystems Research Center130 Lytton AvenuePalo Alto, California 9430135An Introduction to Programmingwith Threadsby Andrew D. BirrellJanuary 6, 1989An Introduction to Programming with ThreadsAndrew D. BirrellThis paper provides an introduction to writing concurrent programs with “threads”. A threadsfacility allows you to write programs with multiple simultaneous points of execution,synchronizing through shared memory. The paper describes the basic thread andsynchronization primitives, then for each primitive provides a tutorial on how to use it. Thetutorial sections provide advice on the best ways to use the primitives, give warnings aboutwhat can go wrong and offer hints about how to avoid these pitfalls. The paper is aimed atexperienced programmers who want to acquire practical expertise in writing concurrentprograms.CR categories and Subject Descriptors: D.1.4 [Programming Techniques]: ConcurrentProgramming; D.3.3 [Programming Languages]: Language Constructs—Concurrentprogramming structures; D.4.1 [Operating Systems]: Process ManagementGeneral Terms: Design, Languages, PerformanceAdditional Key Words and Phrases: Threads, Concurrency, Multi-processing, SynchronizationCONTENTSIntroduction...................................................................................................... 1Why use concurrency?........................................................................................ 2The design of a thread facility .............................................................................. 3Using a Mutex: accessing shared data .................................................................... 7Using a Condition variable: scheduling shared resources.......................................... 14Using Fork: working in parallel......................................................................... 22Using Alert: diverting the flow of control ............................................................ 27Additional techniques ....................................................................................... 28Building your program ..................................................................................... 30Concluding remarks......................................................................................... 31References...................................................................................................... 31Appendix: other thread designs........................................................................... 33 Digital Equipment Corporation 1989This work may not be copied or reproduced in whole or in part for any commercialpurpose. Permission to copy in whole or in part without payment of fee is granted fornon-profit educational and research purposes provided that all such whole or partial copiesinclude the following: a notice that such copying is by permission of the SystemsResearch Center of Digital Equipment Corporation in Palo Alto, California; anacknowledgement of the authors and individual contributors to the work; and allapplicable portions of the copyright notice. Copying, reproducing, or republishing forany other purpose shall require a license with payment of fee to the Systems ResearchCenter. All rights reserved.An Introduction to Programming with Threads.1INTRODUCTIONMany experimental operating systems, and some commercial ones, have recently includedsupport for concurrent programming. The most popular mechanism for this is someprovision for allowing multiple lightweight “threads” within a single address space, usedfrom within a single program.1Programming with threads introduces new difficulties even for experiencedprogrammers. Concurrent programming has techniques and pitfalls that do not occur insequential programming. Many of the techniques are obvious, but some are obvious onlywith hindsight. Some of the pitfalls are comfortable (for example, deadlock is a pleasantsort of bug—your program stops with all the evidence intact), but some take the form ofinsidious performance penalties.The purpose of this paper is to give you an introduction to the programmingtechniques that work well with threads, and to warn you about techniques or interactionsthat work out badly. It should provide the experienced sequential programmer with enoughhints to be able to build a substantial multi-threaded program that works—correctly,efficiently, and with a minimum of surprises.A “thread” is a straightforward concept: a single sequential flow of control. In a high-level language you normally program a thread using procedures, where the procedure callsfollow the traditional stack discipline. Within a single thread, there is at any instant asingle point of execution. The programmer need learn nothing new to use a single thread.Having “multiple threads” in a program means that at any instant the program hasmultiple points of execution, one in each of its threads. The programmer can mostly viewthe threads as executing simultaneously, as if the computer were endowed with as manyprocessors as there are threads. The programmer is required to decide when and where tocreate multiple threads, or to accept such decisions made for him by implementers ofexisting library packages or runtime systems. Additionally, the programmer mustoccasionally be aware that the computer might not in fact execute all his threadssimultaneously.Having the threads execute within a “single address space” means that the computer’saddressing hardware is configured so as to permit the threads to read and write the samememory locations. In a high-level language, this usually corresponds to the fact that theoff-stack (global) variables are shared