M. Ben-Ari

Principles of Concurrent and Distributed Programming uPDF eBook (eBook, PDF)

• Format: PDF

Produktbeschreibung

Principles of Concurrent and Distributed Programming provides an introduction to concurrent programming focusing on general principles and not on specific systems.

Software today is inherently concurrent or distributed - from event-based GUI designs to operating and real-time systems to Internet applications. This edition is an introduction to concurrency and examines the growing importance of concurrency constructs embedded in programming languages and of formal methods such as model checking.

The full text downloaded to your computer

With eBooks you can:

• search for key concepts, words and phrases
• make highlights and notes as you study
• share your notes with friends

eBooks are downloaded to your computer and accessible either offline through the Bookshelf (available as a free download), available online and also via the iPad and Android apps.

Upon purchase, you'll gain instant access to this eBook.

Time limit

The eBooks products do not have an expiry date. You will continue to access your digital ebook products whilst you have your Bookshelf installed.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Pearson HigherEducation
• Seitenzahl: 384
• Altersempfehlung: ab 18 Jahre
• Erscheinungstermin: 9. November 2015
• Englisch
• ISBN-13: 9781292122588
• Artikelnr.: 54936537

Autorenporträt

Mordechai (Moti) Ben-Ari is an Associate Professor in the Department of Science Teaching at the Weizmann Institute of Science in Rehovot, Israel. He is the author of texts on Ada, concurrent programming, programming languages, and mathematical logic, as well as Just a Theory: Exploring the Nature of Science. In 2004 he was honored with the ACM/SIGCSE Award for Outstanding Contribution to Computer Science Education.

Inhaltsangabe

Contents
 
Preface xi
 
1 What is Concurrent Programming? 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Concurrency as abstract parallelism . . . . . . . . . . . . . . . . 2
1.3 Multitasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 The terminology of concurrency . . . . . . . . . . . . . . . . . 4
1.5 Multiple computers . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 The challenge of concurrent programming . . . . . . . . . . . . 5
 
2 The Concurrent Programming Abstraction 7
2.1 The role of abstraction . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Concurrent execution as interleaving of atomic statements . . . . 8
2.3 Justification of the abstraction . . . . . . . . . . . . . . . . . . .
13
2.4 Arbitrary interleaving . . . . . . . . . . . . . . . . . . . . . . . 17
2.5 Atomic statements . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.6 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.8 Machine-code instructions . . . . . . . . . . . . . . . . . . . . . 24
2.9 Volatile and non-atomic variables . . . . . . . . . . . . . . . . . 28
2.10 The BACI concurrency simulator . . . . . . . . . . . . . . . . . 29
2.11 Concurrency in Ada . . . . . . . . . . . . . . . . . . . . . . . . 31
2.12 Concurrency in Java . . . . . . . . . . . . . . . . . . . . . . . . 34
2.13 Writing concurrent programs in Promela . . . . . . . . . . . . . 36
2.14 Supplement: the state diagram for the frog puzzle . . . . . . . . 37
 
3 The Critical Section Problem 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 The definition of the problem . . . . . . . . . . . . . . . . . . . 45
3.3 First attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.4 Proving correctness with state diagrams . . . . . . . . . . . . . . 49
3.5 Correctness of the first attempt . . . . . . . . . . . . . . . . . . 53
3.6 Second attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.7 Third attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.8 Fourth attempt . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.9 Dekker’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . 60
3.10 Complex atomic statements . . . . . . . . . . . . . . . . . . . . 61
 
4 Verification of Concurrent Programs 67
4.1 Logical specification of correctness properties . . . . . . . . . . 68
4.2 Inductive proofs of invariants . . . . . . . . . . . . . . . . . . . 69
4.3 Basic concepts of temporal logic . . . . . . . . . . . . . . . . . 72
4.4 Advanced concepts of temporal logic . . . . . . . . . . . . . . . 75
4.5 A deductive proof of Dekker’s algorithm . . . . . . . . . . . . . 79
4.6 Model checking . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.7 Spin and the Promela modeling language . . . . . . . . . . . . . 83
4.8 Correctness specifications in Spin . . . . . . . . . . . . . . . . . 86
4.9 Choosing a verification technique . . . . . . . . . . . . . . . . . 88
 
5 Advanced Algorithms for the Critical Section Problem 93
5.1 The bakery algorithm . . . . . . . . . . . . . . . . . . . . . . . 93
5.2 The bakery algorithm for N processes . . . . . . . . . . . . . . 95
5.3 Less restrictive models of concurrency . . . . . . . . . . . . . . 96
5.4 Fast algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
5.5 Implementations in Promela . . . . . . . . . . . . . . . . . . . . 104