Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
The JR Programming Language Concurrent Programming In an Extended
Nội dung xem thử
Mô tả chi tiết
THE JR
PROGRAMMING LANGUAGE
Concurrent Programming in an
Extended Java
THE KLUWER INTERNATIONAL SERIES IN
ENGINEERING AND COMPUTER SCIENCE
THE JR
PROGRAMMING LANGUAGE
Concurrent Programming in an
Extended Java
by
Ronald A. Olsson
University of California, Davis
U.S.A.
Aaron W. Keen
California Polytechnic State University
U.S.A.
KLUWER ACADEMIC PUBLISHERS
NEW YORK, BOSTON, DORDRECHT, LONDON, MOSCOW
eBook ISBN: 1-4020-8086-7
Print ISBN: 1-4020-8085-9
Print ©2004 Kluwer Academic Publishers
All rights reserved
No part of this eBook may be reproduced or transmitted in any form or by any means, electronic,
mechanical, recording, or otherwise, without written consent from the Publisher
Created in the United States of America
Boston
©2004 Springer Science + Business Media, Inc.
Visit Springer's eBookstore at: http://www.ebooks.kluweronline.com
and the Springer Global Website Online at: http://www.springeronline.com
To the memory of my parents, Dorothy and Ronald RAO
To all who have touched my life AWK
This page intentionally left blank
Contents
Dedication
List of Figures
List of Tables
Preface
Acknowledgments
xv
xvii
xix
xxv
Op-methods
Operation and Method Declarations
Operation Capabilities
17
17
19
21
21
22
22
1. INTRODUCTION
1.1
1.2
1.3
1.4
1.5
1.6
1.7
Key JR Components
Two Simple Examples
Matrix Multiplication
Concurrent File Search
Critical Section Simulation
Translating and Executing JR Programs
Vocabulary and Notation
Exercises
Part I Extensions for Concurrency
2. OVERVIEW OF EXTENSIONS
2.1
2.2
Process Interactions via Operations
Distributing JR Programs
3. OP-METHODS, OPERATIONS, AND CAPABILITIES
3.1
3.2
3.3
v
1
3
4
6
8
10
12
13
13
viii
Exercises 25
27
27
31
34
35
36
38
43
43
45
46
47
49
50
53
53
56
58
61
65
65
68
70
74
77
79
80
83
84
91
91
93
4. CONCURRENT EXECUTION
4.1
4.2
4.3
4.4
4.5
Process Declarations
The Unabbreviated Form of Processes
Static and Non-static Processes
Process Scheduling and Priorities
Automatic Termination Detection
Exercises
5. SYNCHRONIZATION USING SHARED VARIABLES
5.1
5.2
5.3
5.4
5.5
The Critical Section Problem
An Incorrect Solution
An Alternating Solution
The Bakery Algorithm for Two Processes
The Bakery Algorithm for N Processes
Exercises
6. SEMAPHORES
6.1
6.2
6.3
Semaphore Declarations and Operations
The Dining Philosophers Problem
Barrier Synchronization
Exercises
7. ASYNCHRONOUS MESSAGE PASSING
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
Operations as Message Queues
Invoking and Servicing via Capabilities
Simple Client-Server Models
Resource Allocation
Semaphores Revisited
Data-Containing Semaphores
Shared Operations
Parameter Passing Details
Exercises
8. REMOTE PROCEDURE CALL
8.1
8.2
Mechanisms for Remote Procedure Call
Equivalence to Send/Receive Pairs
Contents ix
8.3 Return, Reply, and Forward Statements
Exercises
9. RENDEZVOUS
9.1 The Input Statement
9.1.1
9.1.2
General Form and Semantics
Simple Input Statements
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
Receive Statement Revisited
Synchronization Expressions
Scheduling Expressions
More Precise Semantics
Break And Continue Statements
Conditional Input
Arrays of Operations
Dynamic Operations
9.10 Return, Reply, and Forward Statements
Exercises
10. VIRTUAL MACHINES
10.1
10.2
10.3
10.4
10.5
10.6
10.7
10.8
Program Start-Up and Execution Overview
Creating Virtual Machines
Creating Remote Objects
Examples of Multiple Machine Programs
Predefined Fields
Parameterized Virtual Machines
Parameter Passing Details
Other Aspects of Virtual Machines
Exercises
11. THE DINING PHILOSOPHERS
11.1
11.2
11.3
Centralized Solution
Distributed Solution
Decentralized Solution
Exercises
96
103
107
108
108
109
112
115
118
119
120
121
122
123
124
128
139
140
141
143
144
146
149
151
152
153
159
160
162
165
169
x
12. EXCEPTIONS
12.1
12.2
12.3
Operations and Capabilities
Input Statements
Asynchronous Invocation
12.3.1
12.3.2
Handler Objects
Send
12.4 Additional Sources of Asynchrony
12.4.1
12.4.2
Exceptions After Reply
Exceptions After Forward
12.5 Exceptions and Operations
Exercises
13. INHERITANCE OF OPERATIONS
13.1
13.2
13.3
13.4
Operation Inheritance
Example: Distributing Operation Servicing
Example: Filtering Operation Servicing
Redefinition Considerations
Exercises
14. INTER-OPERATION INVOCATION SELECTION MECHANISM
14.1
14.2
Selection Method Expression
View Statement
14.2.1
14.2.2
General Form and Semantics
Simple View Statement
14.3 Selection Method Support Classes
14.3.1
14.3.2
14.3.3
14.3.4
ArmEnumeration Methods
InvocationEnumeration Methods
Invocation Methods
Timestamp Methods
14.4 Examples
14.4.1
14.4.2
14.4.3
Priority Scheduling
Random Scheduling
Median Scheduling
Exercises
173
173
174
174
175
176
177
177
178
179
180
185
186
187
188
190
191
193
194
197
197
198
198
199
199
199
199
200
200
201
203
204
Contents xi
Part II Applications
15. PARALLEL MATRIX MULTIPLICATION
15.1
15.2
15.3
15.4
Prescheduled Strips
Dynamic Scheduling: A Bag of Tasks
A Distributed Broadcast Algorithm
A Distributed Heartbeat Algorithm
Exercises
16. SOLVING PDEs: GRID COMPUTATIONS
16.1
16.2
16.3
16.4
A Data Parallel Algorithm
Prescheduled Strips
A Distributed Heartbeat Algorithm
Using Multiple Virtual Machines
Exercises
17. THE TRAVELING SALESMAN PROBLEM
17.1
17.2
17.3
Sequential Solution
Replicated Workers and a Bag of Tasks
Manager and Workers
Exercises
18. A DISTRIBUTED FILE SYSTEM
18.1
18.2
18.3
System Structure
Directory and File Servers
User Interface
Exercises
19. DISCRETE EVENT SIMULATION
19.1
19.2
A Simulation Problem
A Solution
19.2.1
19.2.2
19.2.3
19.2.4
Main Class
Processor Class
Bus Controller Class
Scheduler Class
19.3 Observations
Exercises
211
212
215
217
220
223
227
228
232
236
240
241
247
248
251
254
258
263
264
266
272
280
283
283
285
285
285
286
288
290
291
xii
20. INTERFACING JR AND GUIs
20.1
20.2
BnB Game Overview
BnB Code Overview
20.2.1 Main Class
20.2.2 Window Class
20.2.3 Button Class
20.2.4 Board Class
20.2.5 Toy Classes
20.2.6 Input Classes
20.3 Miscellany
Exercises
21. PREPROCESSORS FOR OTHER CONCURRENCY NOTATIONS
21.1
21.2
21.3
Conditional Critical Regions (CCRs)
Monitors
Communicating Sequential Processes (CSP)
Exercises
Appendices
A
B
C
D
Synopsis of JR Extensions
Invocation and Enumeration Classes
Program Development and Execution
Implementation and Performance
D.1
D.2
D.3
D.4
D.5
D.6
D.7
JR Virtual Machines
Remote Objects
D.2.1 Remote Class Loading
Operations and Operation Capabilities
Invocation Statements
D.4.1 Inheritance
Input Statements
Quiescence Detection
Performance Results
E History of JR
293
293
294
296
297
299
300
305
307
308
310
313
313
316
320
325
331
331
337
341
343
343
344
344
345
345
346
346
346
347
351
Contents
References
Index 359
xiii
355
This page intentionally left blank