Communicating Sequential Processes

Communicating Sequential Processes

Communicating Sequential Processes (CSP) CS5204 Operating Systems 1 CSP Communicating Sequential Processes (CSP) sequential process single thread of control autonomous encapsulated named static

communication channel CS 5204 Operating Systems synchronous reliable unidirectional pointtopoint fixed topology 2 CSP Operators operators: ! (send)

? (receive) usage: Send to Receive from B!x A?y message buffer A B B!x A?y x

y CS 5204 Operating Systems 3 CSP Semantics and Type Matching rendezvous semantics: senders (receivers) remain blocked at send (receive) operation until a matching receive (send) operation is made. typed messages: the type of the message sent by the sender and the type of the message expected by the receiver must match (otherwise abort). A!vec(x,y) B?vec(s,t) OK

A!count(x) B?index(y) NO CS 5204 Operating Systems 4 CSP Guarded Commands Guarded Commands boolean expression Examples at most one ? , must be at end of guard, considered true iff message pending n < 10 A!index(n); n := n + 1;

n < 10; A?index(n) next = MyArray(n); CS 5204 Operating Systems 5 CSP Alternative/Repetitive Commands Alternative Command [ G1 S1 [] G2 S2 [] ... [] Gn Sn ] 1. evaluate all guards 2. if more than on guard is true, nondeterministically select one. 3. if no guard is true, terminate. Note: if all true guards end with an input command for which there is no pending message, then delay the evaluation until a message arrives. If all senders have terminated, then the alternative command terminates.

Repetitive Command * [ G1 S1 [] G2 S2 [] ... [] Gn Sn ] repeatedly execute the alternative command until it terminates CS 5204 Operating Systems 6 CSP Examples Examples: [x >= y > m := x [] y >= x > m := y ] assign x to m if x is greater than or equal to y assign y to m if y is greater than or equal to x assign either x or y to m if x equals y

* [ c: character; west?c > east!c ] Transmit to the process named east a character received from the process named west until the process named west terminates. CS 5204 Operating Systems 7 CSP Examples SEARCH i := 0; * [ i < size; content(i) != n > i := i + 1 ] Scan the array context until the value n is found or until the end of the array of length size is reached LISTMAN:: *[ n : integer; X?insert(n) > INSERT [] n : integer; X?has(n) > SEARCH; X!(i < size) ] LISTMAN has a simple protocol defined by two messages - an insert message and a has message. The types insert and has are used to

disambiguate the integer value passed on each communication with X. INSERT is code (not shown) that adds the value of n to the array content. SEARCH is the code shown above. LISTMAN replies with a boolean value to each has message. CS 5204 Operating Systems 8 CSP Signals between Processes A message bearing a type but no data may be used to convey a signal between processes. For example: Semaphore:: val:integer; val = 0; *[ X?V()--> val = val + 1 [] val > 0; Y?P()--> val = val - 1 ] CS 5204 Operating Systems

9 CSP Bounded Buffer Example BoundedBuffer:: buffer: (0..9) portion; in, out : integer; in := 0; out := 0; * [ in < out + 10; producer?buffer(in mod 10) > in := in + 1; [] out < in; consumer?more() > consumer!buffer(out mod 10); out := out + 1; ] Implements a bounded buffer process using the array buffer to hold up to a maximum of 10 values of type portion. Note how the guarded commands do not accept producer messages when the buffer is full and do not accept consumer messages when the buffer is empty. CS 5204 Operating Systems

10 CSP Example lineimage:(1..125) character; i: integer; i:=1; * [ c:character; X?c --> lineimage(i);+ c; [ i <= 124 --> i := i+1; [] i = 125 --> lineprinter!lineimage; i:=1; ] ] [ I = 1 --> skip [] i>1 --> *[i <= 125 --> lineimage(i):= space; i:= i+1;] lineprinter!lineimage ] Read a stream of characters from X and print them in lines of 125 characters on a lineprinter completing thelast line with spaces if necessary. CS 5204 Operating Systems

11 CSP Arrays of Processes X(i: 1..100):: [process definition] declares an array of processes all with the same code but with different names (e.g., X(1), X(2),, X(100)) Communication among processes in the array is facilitated by the use of input/output commands as illustrated in this code fragment: *[ (i:1..100)X(i)?(params) --> ; X(i)!(result) ] where the bound variable i is used to identify the communicating partner process CS 5204 Operating Systems 12 CSP CSP - Comparison with Monitors Guarded Commands

Monitor: begin executing every call as soon as possible, waiting if the object is not in a proper state and signaling when the state is proper CSP: the called object establishes conditions under which the call is accepted; calls not satisfying these conditions are held pending (no need for programmed wait/signal operations). Rendezvous Monitor: the monitor is passive (has no independent task/thread/activity) CSP: synchronization between peer, autonomous activities. CS 5204 Operating Systems 13 CSP Comparison Distribution:

Monitor: inherently nondistributed in outlook and implementation CSP: possibility for distributed programming using synchronous message passing send receive call message reply message CS 5204 Operating Systems receive send 14

Recently Viewed Presentations

  • Equilibrium of Rigid Bodies in Two Dimensions

    Equilibrium of Rigid Bodies in Two Dimensions

    EQUILIBRIUM OF RIGID BODIES IN TWO DIMENSIONS When a rigid body is in equilibrium, both the resultant force and the resultant couple must be zero. Forces and moments acting on a rigid body could be external forces/moments or internal forces/moments.
  • Lesson 7.2.2  Teacher Notes Standard: 8.EE.B.6 Use similar

    Lesson 7.2.2 Teacher Notes Standard: 8.EE.B.6 Use similar

    Lesson 7.2.2 - Teacher Notes. Standard: 8.EE.B. 6 . Use similar triangles to explain why the slope m is the same between any two distinct points on a non-vertical line in the coordinate plane; derive the equation y = mx...
  • Grants for the arts funding seminar - City of Winchester

    Grants for the arts funding seminar - City of Winchester

    Arts Council England. Arts Council England champions, develops and invests in artistic and cultural experiences that enrich people's lives. We support a range of activities across the arts, museums and libraries - from theatre to digital art, reading to dance,...
  • Highline Class, BI 348

    Highline Class, BI 348

    "Primary Key", "Unique List of Elements", "List of Unique Identifiers", "Distinct List" are all synonyms. The "Primary Key" assure that data collected for a give element is stored in one and only one place. Observation or Record. A set of...
  • Causal Comparative

    Causal Comparative

    Some other variables (time available to study, relevance of the material to their job, etc.) probably explain the relationship. And in order to interpret the results of the analysis we need to know the context. Correlation only tells us that...
  • Warm-Up

    Warm-Up

    You have two cows. You keep half of the milk to sell or drink and give the other half to the king. If you complain, you can be fined, have your cows taken, or go to jail. ... Unlike a...
  • CHAPTER 10, SOCIAL STRATIFICATION - Cengage

    CHAPTER 10, SOCIAL STRATIFICATION - Cengage

    caste system Rigid hierarchy of classes, often preserved through formal law and cultural practices that present free association and movement between classes. class system Status is partially achieved and there is some potential for movement from one class to another.
  • Radiation Safety

    Radiation Safety

    Variability in annual background radiation is caused primarily by two factors. Increasing altitude increases exposure to cosmic radiation. Soil composition can include variable amounts of radioactive metals. **Distance from the equator does not significantly affect background radiation exposure.