Concurrent regions

A house has a hall lamp and a porch lamp, each with its own button. With the states and superstates you know so far, one state machine would need a state for every combination: both off, hall on, porch on, both on. A third lamp makes eight states, a fourth sixteen. Real controllers do many things at once (watch sensors, count, drive outputs), and writing out every combination does not scale.

Regions solve this. A region is a state machine of its own, and a chart or a superstate can contain several regions side by side. Each region is in one of its states at any time, and all of them react in every tick. That is concurrency in SCCharts, and this chapter is about how regions run, how they communicate within a tick, and how they finish together.

Two machines side by side

TwoLampsSimulation

Open in the playground

Diagram

Code

scchart TwoLamps {
  input bool hallButton, porchButton
  output bool hall, porch

  region Hall {
    initial state Off
      if hallButton do hall = true go to On
    state On
      if hallButton do hall = false go to Off
  }

  region Porch {
    initial state Off
      if porchButton do porch = true go to On
    state On
      if porchButton do porch = false go to Off
  }
}

Step

Tick 0 of 5

Inputs for tick 1

hallButton Boolean input: true while on. It keeps its value until you change it. porchButton Boolean input: true while on. It keeps its value until you change it.

Timing diagram of TwoLamps

Tick	input bool hallButton	input bool porchButton	output bool hall	output bool porch	Active state of region Hall	Active state of region Porch

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 5 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 5 ticks:

1. hallButton = false, porchButton = falseTick 1 enters the initial state of each region: Off in Hall and Off in Porch. The chart is in two states at once.
2. hallButton = truehallButton: the Hall region moves to On. Porch reacts too, in the same tick, but none of its transitions is enabled, so it stays in Off.
3. hallButton = false, porchButton = trueporchButton: now Porch moves to On; Hall stays where it is.
4. hallButton = trueBoth buttons are pressed (porchButton is still true from the last tick). Both regions react in this one tick: both lamps go off.
5. hallButton = false, porchButton = falseNeither button: both regions stay in Off.

In tick 4 both buttons are pressed, and both regions react in that one tick.

Each region block is a complete state machine with its own initial state. Tick 1 enters the initial state of every region, so TwoLamps starts in two states at once: Off in the region Hall and Off in the region Porch. The two regions have an Off and an On each; the region a state belongs to keeps them apart.

From then on, every region reacts in every tick. Hall looks at hallButton, Porch at porchButton, and in tick 4, when both buttons are down, both lamps switch in the same tick. A region with nothing enabled stays where it is, as Porch does in tick 2.

How to write regions:

• A region is region Name { … }. The name is optional (region { … }), but named regions are easier to talk about, and KIELER shows the name in the diagram, where each region is a box of its own.
• KIELER also accepts the braces left out: region Name: followed by the region’s states. The region then runs to the next region line or to the end of the enclosing state. The KIELER wiki writes its examples this way, so you will meet it.
• Regions can sit at the top of a chart, as here, or inside a superstate. Entering a superstate enters the initial state of each of its regions, all in the same tick.
• A state with one region can write its states directly, as in Superstates. A state with several regions writes each of them as a region block. The two styles do not mix: states written next to a region block in the same state are a syntax error, such as mismatched input 'region' expecting '}'.

Talking within a tick

Regions often need each other’s results. In this burglar alarm the region Door notices the door opening and sets intruder; the region Siren sounds the siren as soon as intruder is true. intruder is declared at the top of the chart without input or output: it is a local of the chart, shared by both regions.

AlarmSimulation

Open in the playground

Diagram

Code

scchart Alarm {
  input bool door
  output bool siren
  bool intruder

  region Siren {
    initial state Quiet
      if intruder do siren = true go to Sounding
    state Sounding
  }

  region Door {
    initial state Watching
      if door do intruder = true go to Alarmed
    state Alarmed
  }
}

Step

Tick 0 of 4

Inputs for tick 1

door Boolean input: true while on. It keeps its value until you change it.

Timing diagram of Alarm

Tick	input bool door	output bool siren	Active state of region Siren	Active state of region Door

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks:

1. door = falseTick 1 enters Quiet and Watching. intruder is a local variable of the chart, shared by both regions; it starts false.
2. The door stays shut. Both regions react and nothing is enabled.
3. door = trueThe door opens. Door sets intruder to true, and Siren reads intruder in the same tick: it sees true and sounds the siren. The reader waited for the writer, although Siren is written first in the file.
4. door = falseThe door closes again, but both regions have moved on: siren stays true.

In tick 3 the door opens and the siren sounds in the same tick, although Siren is written before Door.

In tick 3 the door opens. Door sets intruder to true, and Siren reads intruder in the same tick and sees true: the siren sounds in the very tick the door opened. Nothing waits for the next tick.

How can that work when Siren is written first? Regions do not run in the order you write them. Within a tick, KIELER orders the regions’ actions by the data they share, and the basic rule is: every write of a variable comes before every read of it. Siren’s test of intruder waits until Door has done whatever it does with intruder in this tick. Swap the two regions and nothing changes:

Alarm and AlarmSwappedComparison

Diagrams

Alarm

AlarmSwapped

Code

Alarm

scchart Alarm {
  input bool door
  output bool siren
  bool intruder

  region Siren {
    initial state Quiet
      if intruder do siren = true go to Sounding
    state Sounding
  }

  region Door {
    initial state Watching
      if door do intruder = true go to Alarmed
    state Alarmed
  }
}

AlarmSwapped

scchart AlarmSwapped {
  input bool door
  output bool siren
  bool intruder

  region Door {
    initial state Watching
      if door do intruder = true go to Alarmed
    state Alarmed
  }

  region Siren {
    initial state Quiet
      if intruder do siren = true go to Sounding
    state Sounding
  }
}

Step

Tick 0 of 4

Inputs for tick 1, for both charts

door Boolean input: true while on. It keeps its value until you change it.

Timing diagram of Alarm and AlarmSwapped, no ticks yet

Tick	input bool door	Alarm: output bool siren	Alarm: Active state of region Siren	Alarm: Active state of region Door	AlarmSwapped: output bool siren	AlarmSwapped: Active state of region Door	AlarmSwapped: Active state of region Siren

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Both charts get the same inputs. Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks, the same inputs for both charts:

1. door = falseTick 1 enters Quiet and Watching in both charts. intruder is a local of each chart, shared by its two regions; it starts false.
2. The door stays shut. All four regions react, and nothing is enabled.
3. door = trueThe door opens. In both charts Door sets intruder, and Siren reads it in the same tick, sees true and sounds the siren. In Alarm Siren is written first, in AlarmSwapped second: the reader waits for the writer either way.
4. door = falseThe door closes again, but both regions have moved on: siren stays true in both charts.

The same alarm with its regions in the other order. The door opens in tick 3, and both charts sound the siren in that tick.

The same holds for signals (see Signals). Emitting a signal counts as a write (an update, to be exact, as the next section explains) and testing it as a read, so if any region emits a signal in a tick, every region that tests the signal in that tick sees it present.

Inside a single region nothing is reordered. A region’s transitions and effects run in the order you wrote them, like the statements of a sequential program, and a region never waits for itself: if a region reads a variable before it writes it, the read sees the old value. The order between regions is the compiler’s business; the order within a region is yours.

Several writers: initialise, update, read

Writes before reads is half of the rule. What happens when several regions write the same variable in the same tick? Here is a visitor counter for a shop with two doors. North and South each add one to inside when someone comes in, Clear resets the count, and Display reports a crowd from three visitors on.

VisitorsSimulation

Open in the playground

Diagram

Code

scchart Visitors {
  input bool clear, north, south
  output int inside
  output bool crowded

  region Display {
    initial state Calm
      if inside >= 3 do crowded = true go to Crowded
    state Crowded
      if inside < 3 do crowded = false go to Calm
  }

  region Clear {
    initial state Ready
      if clear do inside = 0 go to Ready
  }

  region North {
    initial state Counting
      if north do inside++ go to Counting
  }

  region South {
    initial state Counting
      if south do inside++ go to Counting
  }
}

Step

Tick 0 of 6

Inputs for tick 1

clear Boolean input: true while on. It keeps its value until you change it. north Boolean input: true while on. It keeps its value until you change it. south Boolean input: true while on. It keeps its value until you change it.

Timing diagram of Visitors

Tick	input bool clear	input bool north	input bool south	output int inside	output bool crowded	Active state of region Display	Active state of region Clear	Active state of region North	Active state of region South

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 6 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 6 ticks:

1. clear = false, north = false, south = falseTick 1 enters the initial state of all four regions. inside starts at 0.
2. north = trueSomeone comes in through the north door: North adds one, inside is 1.
3. north = false, south = trueSomeone comes in through the south door: 2.
4. north = trueBoth doors at once (south is still true). North and South both update inside in this tick, and both updates count: 2 + 1 + 1 = 4. Display reads inside only after both updates, sees 4 and reports a crowd, in the same tick.
5. clear = trueclear, north and south all at once. Clear sets inside = 0 first (an absolute write), then the two updates add 1 each, then Display reads the result: 2, so it goes back to Calm. The order of the regions in the file plays no part.
6. clear = false, north = false, south = falseQuiet again: inside stays 2.

Tick 5: inside is set to 0, then both doors add one, and Display sees only the result, 2.

In tick 4 both doors fire, and both updates count: inside goes from 2 to 4, and Display, which reads after both, reports a crowd in that same tick. In tick 5 clear arrives as well, and inside ends at 2: not 0, and not 1.

The precise rule behind this is the initialise–update–read protocol. Within a tick, KIELER orders the accesses to each variable in three phases:

1. Initialise: absolute writes, which set a value outright, such as inside = 0.
2. Update: relative writes, which change the current value, such as inside++ or inside += 2. Emitting a signal is an update too.
3. Read: everything that uses the value, such as the trigger inside >= 3.

Each region keeps its own order throughout. The protocol is the core of SCCharts’ sequentially constructive model of computation; Why the compiler says no tells the whole story.

Several updates of one variable in the same tick are only accepted if their order cannot matter: any mix of +=, -=, ++ and --, or several updates with the same operator, such as two *=. A += in one region and a *= in another would give different results in different orders, and KIELER rejects that combination.

Valued signals follow the same logic. With a combine function, such as combine +, every region’s emission counts. Without one, two regions may emit the signal in the same tick only in exactly the same way, V(1) in both: V(a) in one region and V(b) in the other are rejected even when a and b are equal, because the compiler compares what you wrote, not the values.

Write updates with ++, += and their relatives. An old-style inside = inside + 1 counts as an update too, but KIELER warns about it, for a good reason that Why the compiler says no explains.

Finishing together: ABRO

ABRO is the classic first example of synchronous programming. It comes from Esterel, the synchronous language whose ideas SCCharts inherits, and its specification fits in two sentences: wait for two inputs, A and B, in any order, and as soon as both have arrived, emit O. Whenever R arrives, start again from the beginning. Concurrency makes the first sentence easy. Here it is, step by step.

Wait for A

One region waits for A, then rests in a final state: done, nothing more to do. A is a signal, so if A asks whether A is present in this tick.

region HandleA {
  initial state WaitA
    if A go to DoneA
  final state DoneA
}

Wait for A and B

Put two such regions into one superstate, WaitAB, and they wait at the same time:

initial state WaitAB {
  region HandleA {
    initial state WaitA
      if A go to DoneA
    final state DoneA
  }
  region HandleB {
    initial state WaitB
      if B go to DoneB
    final state DoneB
  }
}

Whichever input arrives first, its region finishes and rests in its final state until the other one arrives. If both arrive in the same tick, both regions finish in that tick.

Then emit O

When has WaitAB finished? A superstate with several regions terminates when all of its regions are in final states at the same time. Its join to then fires in that same tick, exactly as with one region in Superstates:

ABOSimulation

Open in the playground

Diagram

Code

scchart ABO {
  input signal A, B
  output signal O

  initial state WaitAB {
    region HandleA {
      initial state WaitA
        if A go to DoneA
      final state DoneA
    }
    region HandleB {
      initial state WaitB
        if B go to DoneB
      final state DoneB
    }
  }
  do O join to Done

  state Done
}

Step

Tick 0 of 6

Inputs for tick 1

A Input signal: present while on. It keeps its value until you change it. B Input signal: present while on. It keeps its value until you change it.

Timing diagram of ABO

Tick	input signal A	input signal B	output signal O	Active state of the chart	Active state of region HandleA (in WaitAB)	Active state of region HandleB (in WaitAB)

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 6 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 6 ticks:

1. A = false, B = falseTick 1 enters WaitAB and both of its regions: WaitA and WaitB are active.
2. A = trueA is present: HandleA reaches its final state, DoneA. HandleB is still waiting, so WaitAB has not terminated.
3. A = falseNothing happens. HandleA stays in its final state; it does not need A any more.
4. B = trueB is present: HandleB reaches DoneB. Now both regions are in final states, so WaitAB terminates and its join to Done fires in this tick: O is present.
5. B = falseO was a one-tick event. The chart rests in Done.
6. A = true, B = trueDone has no transitions, so new As and Bs change nothing. To start again, ABRO needs its R.

A in tick 2, B in tick 4: O is present in tick 4, the tick in which the second region finishes.

“At the same time” is meant literally. Termination looks at where the regions are at the end of the tick, and a final state is a place, not a flag: a region that leaves its final state again (a final state can have outgoing transitions) no longer counts. If only some regions of a state have final states at all, a region without a final state never finishes, so its superstate never terminates, and KIELER warns:

All or none concurrent regions should have final states.

Start again on R

The second sentence of the specification, “whenever R arrives, start again”, needs a way out of everything at once. You know one from Superstates: a transition on a superstate leaves it from wherever it is inside. ABRO wraps the whole behaviour into a superstate, ABO, and gives it a transition back to itself:

ABROSimulation

Open in the playground

Diagram

Code

scchart ABRO {
  input signal A, B, R
  output signal O

  initial state ABO {
    initial state WaitAB {
      region HandleA {
        initial state WaitA
          if A go to DoneA
        final state DoneA
      }
      region HandleB {
        initial state WaitB
          if B go to DoneB
        final state DoneB
      }
    }
    do O join to Done

    state Done
  }
  if R abort to ABO
}

Step

Tick 0 of 9

Inputs for tick 1

A Input signal: present while on. It keeps its value until you change it. B Input signal: present while on. It keeps its value until you change it. R Input signal: present while on. It keeps its value until you change it.

Timing diagram of ABRO

Tick	input signal A	input signal B	input signal R	output signal O	Active state of the chart	Active state of the region of ABO	Active state of region HandleA (in ABO.WaitAB)	Active state of region HandleB (in ABO.WaitAB)

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 9 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 9 ticks:

1. A = false, B = false, R = falseTick 1 enters ABO, WaitAB, WaitA and WaitB: four states, two levels of nesting, two regions.
2. A = trueA: HandleA is done.
3. A = false, B = trueB: HandleB is done too, WaitAB terminates and its join emits O. ABO is now in Done.
4. B = falseWaiting in Done.
5. A = true, B = trueA and B again, but Done ignores them.
6. A = false, B = false, R = trueR: the transition if R abort to ABO leaves ABO and enters it again, so everything inside starts over in WaitA and WaitB.
7. R = false, A = trueA: HandleA is done.
8. A = false, B = trueB: both are done, O is present again.
9. B = falseBack in Done until the next R.

Tick 6: R leaves ABO and enters it again, and both regions are back in their waiting states.

The new keyword in the last line is abort to, a strong abort. For now read if R abort to ABO as “whenever R is present, leave ABO and enter it again”. Entering ABO enters WaitAB, and entering WaitAB puts both regions back into their initial states. Why ABRO uses abort to here, and not the go to you know, is a question for the next chapter, Aborts, which comes back to ABRO at its end.

Determinate, or rejected

In C, Java or Python, concurrency usually means threads, and threads can race: run the same program twice and you can get two different results. SCCharts regions are different. KIELER orders every tick by the data the regions share, not by the order in which you wrote them, so the same inputs always give the same outputs: an SCChart is determinate, as Thinking in ticks promised. (One hole remains: old-style updates such as x = x + 1 in two regions. Why the compiler says no shows it, and writing += and ++ avoids it.)

The price is that some charts have no good order at all, and KIELER rejects them rather than pick one. The most common case is two regions setting the same variable to different values:

ConflictChart

Open in the playground

Diagram

Code

scchart Conflict {
  input bool on, off
  output bool light

  region SwitchOn {
    initial state Waiting
      if on do light = true go to Waiting
  }

  region SwitchOff {
    initial state Waiting
      if off do light = false go to Waiting
  }
}

KIELER rejects this chart

• Line 7, column 16Two concurrent regions assign different values to lightKIELER says: The SCG is NOT asc-schedulable!KIELER does not check whether the two assignments can happen in the same tick: two regions that run side by side must not both assign light. Let one region own light, and let the other regions send it requests with signals.About this message

SwitchOn sets light and SwitchOff clears it. KIELER rejects the chart.

If on and off arrive in the same tick, which write should count? Neither order is better than the other, so KIELER refuses the chart with The SCG is NOT asc-schedulable!, after a list of Can't schedule from … lines that use the compiler’s own names.

The other kind of rejected chart has regions waiting for each other. Say region P sets x only if y is false, and region Q sets y only if x is false. P cannot read y before Q has decided whether to write it, and Q cannot decide that before it has read x, which in turn waits for P. Each region waits for the other, and KIELER rejects the chart with the same messages. Why the compiler says no explains these messages, and the ways to change a chart that KIELER refuses, starting with Conflict. When several regions really do need one thing, such as a printer, Sharing a resource shows how to let them take turns.

Try it

A third input

Extend ABO to ABCO: emit O once A, B and C have all arrived, in any order and in any combination of ticks.

Open the starter in the playground

Show the starter chart

scchart ABO {
  input signal A, B
  output signal O

  initial state WaitAB {
    region HandleA {
      initial state WaitA
        if A go to DoneA
      final state DoneA
    }
    region HandleB {
      initial state WaitB
        if B go to DoneB
      final state DoneB
    }
  }
  do O join to Done

  state Done
}

Show a solution

scchart ABCO {
  input signal A, B, C
  output signal O

  initial state WaitABC {
    region HandleA {
      initial state WaitA
        if A go to DoneA
      final state DoneA
    }
    region HandleB {
      initial state WaitB
        if B go to DoneB
      final state DoneB
    }
    region HandleC {
      initial state WaitC
        if C go to DoneC
      final state DoneC
    }
  }
  do O join to Done

  state Done
}

Open the solution in the playground

People leave too

The shop’s visitor counter only ever goes up. Add an input leaving and a region Exit that takes one off inside whenever someone leaves. Then simulate a tick in which one person comes in while another leaves: KIELER should accept the chart, and inside should not change in that tick.

Open the starter in the playground

Show the starter chart

scchart Visitors {
  input bool clear, north, south
  output int inside
  output bool crowded

  region Display {
    initial state Calm
      if inside >= 3 do crowded = true go to Crowded
    state Crowded
      if inside < 3 do crowded = false go to Calm
  }

  region Clear {
    initial state Ready
      if clear do inside = 0 go to Ready
  }

  region North {
    initial state Counting
      if north do inside++ go to Counting
  }

  region South {
    initial state Counting
      if south do inside++ go to Counting
  }
}

Show a solution

scchart VisitorsExit {
  input bool clear, north, south, leaving
  output int inside
  output bool crowded

  region Display {
    initial state Calm
      if inside >= 3 do crowded = true go to Crowded
    state Crowded
      if inside < 3 do crowded = false go to Calm
  }

  region Clear {
    initial state Ready
      if clear do inside = 0 go to Ready
  }

  region North {
    initial state Counting
      if north do inside++ go to Counting
  }

  region South {
    initial state Counting
      if south do inside++ go to Counting
  }

  region Exit {
    initial state Counting
      if leaving do inside-- go to Counting
  }
}

Open the solution in the playground

Check your understanding

A game starts when both players are ready at the same time. Player A can also leave the lobby again after getting ready.

LobbyPrediction

Diagram

Code

scchart Lobby {
  input bool readyA, readyB, leaveA
  output bool playing

  initial state Gathering {
    region PlayerA {
      initial state WaitingA
        if readyA go to ReadyA
      final state ReadyA
        if leaveA go to WaitingA
    }
    region PlayerB {
      initial state WaitingB
        if readyB go to ReadyB
      final state ReadyB
    }
  }
  do playing = true join to Game

  state Game
}

In tick 3, player A leaves while player B gets ready.

Inputs per tick. A value in grey was not set in that tick: it holds from an earlier one.

Tick	readyA	readyB	leaveA
1	false	false	false
2	true	false	false
3	false	true	true
4	true	true	false

1. After tick 3, what is playing? Choosetruefalse
2. After tick 4, what is playing? Choosetruefalse

Run and check Plays the scenario on the diagram, then marks each answer.

Explanation

playing is false after tick 3 and true after tick 4. In tick 3 player A leaves ReadyA while player B reaches ReadyB, so at the end of the tick only PlayerB is in a final state, and Gathering has not terminated. In tick 4 player A is ready again: now both regions are in final states at the same time, the join fires, and playing becomes true. Termination looks at where the regions are at the end of a tick.

Three regions react in the same tick: region P does x = 10, region Q does x += 1, and region R does y = x. Nothing else writes x or y. What is y after the tick?

A10B11CIt depends on the order of the regions in the fileDThe value x had in the previous tick

Show the answer

Answer B: 11

Initialise, update, read: the absolute write x = 10 comes first, then the update x += 1, and the read in R comes last and sees 11. The order of the regions in the file plays no part.

Two regions share a variable, and every update of it is written with += or ++. You move one region from the bottom of the chart’s source to the top. What can change in the chart’s behaviour?

AWhich region reacts first in each tick, and so the outputsBThe values the moved region readsCNothing

Show the answer

Answer C: Nothing

KIELER orders the actions of concurrent regions by the data they share, not by their order in the file. The two alarm charts above differ only in the order of their regions and behave identically. The question’s condition matters: with old-style updates such as x = x + 1 in two regions, the order in the file can decide the result, a trap shown in Why the compiler says no.

Key ideas

• A region is a state machine of its own. A chart or a superstate can have several, side by side; each is in one state at a time, and all of them react in every tick.
• Regions communicate within a tick. For each variable, absolute writes come first, then updates, then reads. The order of the regions in the file does not matter, as long as you write updates with += and ++.
• A superstate with regions terminates when all of them are in final states at the same time, and its join to fires in that tick.
• The same inputs always give the same outputs. A chart without a valid order, such as two regions setting one output to different values, is rejected.

Next, Aborts: leaving a superstate while its inside is still busy, and what the inside may still do in that tick.