Principles of concurrent and distributed programming

Principles of Concurrent and Distributed Programming
Visit the Principles of Concurrent and Distributed Programming, Second Edition Companion Website at www.pearsoned.co.uk/ben-ari to find valuable student learning material including: • Source code for all the algorithms in the book • Links to sites where software for studying concurrency may be downloaded.

We work with leading authors todevelop the strongest educational materials in computing, bringing cutting-edge thinking and best learning practice to a global market. Under a range of well-known imprints, including Addison-Wesley, we craft high quality print and electronic publications which help readers to understand and apply their content, whether studying or at work. To find out more about the complete range of our publishing,please visit us on the World Wide Web at: www.pearsoned.co.uk

Principles of Concurrent and Distributed Programming
Second Edition

M. Ben-Ari

Pearson Education Limited Edinburgh Gate Harlow Essex CM20 2JE England and Associated Companies throughout the world Visit us on the World Wide Web at: www.pearsoned.co.uk First published 1990 Second edition 2006 c Prentice Hall Europe, 1990 cMordechai Ben-Ari, 2006 The right of Mordechai Ben-Ari to be identified as author of this work has been asserted by him in accordance with the Copyright, Designs and Patents Act 1988. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without eitherthe prior written permission of the publisher or a licence permitting restricted copying in the united Kingdom issued by the Copyright Licensing Agency Ltd, 90 Tottenham Court Road, London W1T 4LP. All trademarks used herein are the property of their respective owners. The use of any trademark in this text does not vest in the author or publisher any trademark ownership rights in such trademarks,nor does the use of such trademarks imply any affiliation with or endorsement of this book by such owners. ISBN-13: 978-0-321-31283-9 ISBN-10: 0-321-31283-X British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library Library of Congress Cataloging-in-Publication Data A catalog record for this book is available from the Library of Congress 109 8 7 6 5 4 3 2 1 10 09 08 07 06 Printed and bound by Henry Ling Ltd, at the Dorset Press, Dorchester, Dorset The publisher’s policy is to use paper manufactured from sustainable forests.

Contents
Preface 1 What is Concurrent Programming? 1.1 1.2 1.3 1.4 1.5 1.6 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . Concurrency as abstract parallelism . . . . . . . . . . . . . .. . Multitasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . The terminology of concurrency . . . . . . . . . . . . . . . . . Multiple computers . . . . . . . . . . . . . . . . . . . . . . . . The challenge of concurrent programming . . . . . . . . . . . . xi 1 1 2 4 4 5 5 7 7 8 13 17 19 21 23 24 28 29 31

2 The Concurrent Programming Abstraction 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.92.10 2.11 The role of abstraction . . . . . . . . . . . . . . . . . . . . . . . Concurrent execution as interleaving of atomic statements . . . . Justification of the abstraction . . . . . . . . . . . . . . . . . . . Arbitrary interleaving . . . . . . . . . . . . . . . . . . . . . . . Atomic statements . . . . . . . . . . . . . . . . . . . . . . . . . Correctness . . . . . . . . . . . . . . . . . .. . . . . . . . . . Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Machine-code instructions . . . . . . . . . . . . . . . . . . . . . Volatile and non-atomic variables . . . . . . . . . . . . . . . . . The BACI concurrency simulator . . . . . . . . . . . . . . . . . Concurrency in Ada . . . . . . . . . . . . . . . . . . . . . . . . v

vi 2.12 2.13 2.14

Contents...