Lecture Operating systems: A concept-based approach (2/e): Chapter 16 - Dhamdhere

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. Chapter 16: Theoretical issues in Distributed Systems Dhamdhere: Operating Systems— A Concept­Based Approach , 2 ed Slide No: 1 Copyright © 2008 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 Chapter 16: Theoretical issues in Distributed Systems Dhamdhere: Operating Systems— A Concept­Based Approach , 2 ed Slide No: 2 Copyright © 2008 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 } Chapter 16: Theoretical issues in Distributed Systems Dhamdhere: Operating Systems— A Concept­Based Approach , 2 ed Slide No: 3 Copyright © 2008 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: < process state, old state, new state, event description, channel, message > • Event ei is < Pk, s, s’, send, c, m > Chapter 16: Theoretical issues in Distributed Systems Dhamdhere: Operating Systems— A Concept­Based Approach , 2 ed Slide No: 4 Copyright © 2008 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, i.e., occurred before it – Precedence of events in a process is known – A causal relationship is a cause-and-effect relationship * The event corresponding to a cause occurs before that corres-ponding to its effect, e.g., sending and receiving of a message * It is used to find precedence of events in different processes – Event precedence is transitive * If ei → ej and ej → ek, then ei → ek Chapter 16: Theoretical issues in Distributed Systems Dhamdhere: Operating Systems— A Concept­Based Approach , 2 ed Slide No: 5 Copyright © 2008 ... - tailieumienphi.vn