Threads programmingCS380L: Mike DahlinSeptember 23, 2008But, the main reason for advocating the use of this pattern is to make your program more obiously,and more robustly, correct...[T]his programming convention allows you to verify correctness bylocal inspection, which is always preferable to global inspection.”Andrew Birrell “An introduction to programming with threads”One final warning: don’t emphasize efficiency at the expense of correctness. It is much easier tostart with a correct program and ...[make] it efficient, than to start with an efficient program and...[make] it correct.Andrew Birrell “An introduction to programming with threads””Debugging is twice as hard as writing the code in the first place. Therefore, if you write the codeas cleverly as possible, you are, by definition, not smart enough to debug it.”Brian W. Kernighan1 Preliminaries1.1 ReviewLast few weeks: OS structure• Origin of modern OSes: Multix, THE, Unix• Minimal abstractions: Scheduler activations, exokernel• Hypervisors: Disco, ESXWhat we didn’t cover:• Other classics: Plan9, OsKit/Flux, Alto/Pilot, microkernels, hydra, mach, Xen, ...• Security, information flow: Asbestos, Flume, HiStar1• Scalable support for multicore: K42, ...• Dependability: Singularity, Nooks (device driver isolation)• ...and many others...1.2 PreviewThis week: Correctness/Concurrency local/distributed• Today: Basic threads programming• Thursday: liveness properties of distributed systems1.3 Non-previewWanted to do a broader study of correctness of large systemsTouches on OS, distributed systems, formal methods, AIA sampling of cool papers:1.3.1 Other takes on threads• case against threads (for event-driven)– Event-driven Programming for Robust Software (Dabek et. al. 2002)• Binary rewriting for correct multithreading:– Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson, Eraser:A Dynamic Race Detector for Multi-Threaded Programs, ACM Transactions on Computer Systems,15(4): 391-411, November 1997.• transactional memory– Christopher J. Rossbach, Owen S. Hofmann, Donald E. Porter, Hany E. Ramadan, Aditya Bhandari,Emmett Witchel TxLinux: Using and Managing Transactional Memory in an Operating System• Stream programming– Lagniappe (Taylor Riche)21.3.2 Other cool papers on correctness/understanding systems• Debugging/performance black box systems– Performance Debugging for Distributed Systems of Black Boxes Marcos K. Aguilera, Jeffrey C.Mogul, Janet L. Wiener, Patrick Reynolds, Athicha Muthitacharoen SOSP 2003• AI to diagnose faults– Capturing, Indexing, Clustering, and Retrieving System History. Ira Cohen (HP Labs), MoisesGoldszmidt (HP Labs), Steve Zhang (Stanford University), Terence Kelly (HP Labs), ArmandoFox (Stanford), Julie Symons (HP Labs) SOSP 2005• Model checking/program analysis to find serious OS bugs– EXE: Automatically Generating Inputs of Death, (postscript) (PDF) Cristian Cadar, Vijay Ganesh,Peter M. Pawlowski, David L. Dill, Dawson R. Engler, 13th ACM Conference on Computer andCommunications Security, 2006.– eXplode: a Lightweight, General System for Finding Serious Storage System Errors, Junfeng Yang,Can Sar, and Dawson Engler, Proceedings of the 7th Symposium on Operating System Design andImplementation, 2006.• Data mining/AI to analyze code– From Uncertainty to Belief: Inferring the Specification Within, Ted Kremenek, Paul Twohey, God-mar Back, Andrew Ng, Dawson Engler, Proceedings of the 7th Symposium on Operating SystemDesign and Implementation, 2006. (PDF)– Shan Lu, Soyeon Park, Chongfeng Hu, Xiao Ma, Weihang Jiang, Zhenmin Li, Raluca A. Popa,Yuanyuan Zhou. MUVI: Automatically Inferring Multi-Variable Access Correlations and DetectingRelated Semantic and Concurrency Bugs. In the Proceedings of the 21st ACM Symposium onOperating Systems Principles (SOSP’07), October 2007– Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code DawsonEngler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf.– Checking System Rules Using System-Specific, Programmer-Written Compiler Extension DawsonEngler, Benjamin Chelf, Andy Chou, and Seth Hallem.– Shan Lu, Soyeon Park, Eunsoo Seo, Yuanyuan Zhou. Learning from Mistakes — A ComprehensiveStudy on Real World Concurrency Bug Characteristics. In the proceedings of the 13th InternationalConference on Architecture Support for Programming Languages and Operating Systems (ASP-LOS’08), March 2008– Lin Tan, Ding Yuan, Yuanyuan Zhou. /* iComment: Bugs or Bad Comments? */. In the Proceed-ings of the 21st ACM Symposium on Operating Systems Principles (SOSP’07), October 200731.4 OutlineBasic threads programming• background• tirade• deadlocks2 Rules to live byMostly from Lamspon and Redell “Experience with processors and monitors in Mesa” CACM v23 n2 1980.2.0.1 History• Mesa: programming language for Pilot personal computer at Xerox PARC– Personal computer for PARC Computer scientists: write software in one language (Mesa), eachuser has own machine → protection is to guard against bugs not malicious attacks; resource mgmtis minor concern• Extreme research: light weight threads– “Second system”∗ First system was Alto (pre-PC PC)∗ Second system: support muti-programming– Debate of concurrent programming model∗ Message passing, or∗ Shared memory∗ Debate settled on the ground of ease of programming– Debate of synchronization primitives∗ Non-preemptive scheduler, or∗ Semaphores, or∗ Monitors (locks + condition variables)· Hoare semantics, or· Hansen semantics∗ Debate settled on the ground of structures• Terminology and modern languages4– Lampson/Redell “process” = modern “thread”∗ Mesa: no HW protection – process == thread– LR “Monitor” v. “Monitored record”∗ LR Default “monitor” associates synchronization variables with code (e.g., class variables/staticvariables)∗ LR “Monitored record” associates synchronization variables with object (e.g., member vari-ables)∗ Modern: Member variables are default → when I say “monitor” I mean “montored record”∗ NB: many textbooks really broken (IMHO) – no OO programming; “critical section” focuseson code (not shared data) and uses global variables for synchronization. (See Lampsen andRedell p. 106 “(c) Creating monitors. A fixed number of monitors is also unacceptable...butmany of the details of existing