Chapter 17 - Distributed control algorithms. This chapter describes the notions of correctness of a distributed control algorithm, and presents algorithms for performing five control functions in a distributed OS - mutual exclusion, deadlock handling, leader election, scheduling, and termination detection. | PROPRIETARY MATERIAL. © 2007 The McGraw-Hill Companies, Inc. All rights reserved. No part of this PowerPoint slide may be displayed, reproduced or distributed in any form or by any means, without the prior written permission of the publisher, or used beyond the limited distribution to teachers and educators permitted by McGraw-Hill for their individual course preparation. If you are a student using this PowerPoint slide, you are using it without permission. Theoretical issues in distributed systems An OS uses two key notions to organize its operation Time and state Time is used to keep track of when an event occurred, or the order in which events occurred State of processes and resources are used in scheduling and resource allocation These notions are hard to use in a distributed system Computers have their own clocks, which might show different times Hence time is not uniquely known Computers have memories So states of entities might be spread throughout the system We need to develop | PROPRIETARY MATERIAL. © 2007 The McGraw-Hill Companies, Inc. All rights reserved. No part of this PowerPoint slide may be displayed, reproduced or distributed in any form or by any means, without the prior written permission of the publisher, or used beyond the limited distribution to teachers and educators permitted by McGraw-Hill for their individual course preparation. If you are a student using this PowerPoint slide, you are using it without permission. Theoretical issues in distributed systems An OS uses two key notions to organize its operation Time and state Time is used to keep track of when an event occurred, or the order in which events occurred State of processes and resources are used in scheduling and resource allocation These notions are hard to use in a distributed system Computers have their own clocks, which might show different times Hence time is not uniquely known Computers have memories So states of entities might be spread throughout the system We need to develop practical substitutes to these notions Local and global states Definitions Local state State of an entity, such as a process, CPU, or resource Global state Global state of a system at time t is the collection of local states of all entities in it at time instant t We depict local and global states as follows: Local state of a process Pk at time t: skt Global state of the system at time t: St If a system contains n processes, its state is represented as { s1t, s2t, , snt } Change of state • The state changes as a result of an event – An event could be the sending or receiving of a message – We represent an event as follows: Event ei is Event Precedence Event precedence indicates which event occurred before or after another event Precedence is used to know the order in which events occurred It is called event ordering ei → ej indicates that event ei precedes ej, ., occurred before
