Skip to content
Software Architecture Guide

Deadlock in Process Models

Explanation

Section titled “Explanation”

A process model is a diagram of steps and decisions. Each running case is a process instance. Gateways are the diamond shapes that split or join the flow. Many models contain control-flow errors. Deadlock is one of them, and lack of synchronization is another (f1).

How a deadlock happens. A parallel (AND) join makes the instance wait until every incoming sequence flow has been taken (f7). If one incoming branch never delivers, the instance waits forever.

The usual trigger is a mismatch. An exclusive (XOR) gateway selects only one outgoing flow (f8). If a parallel join follows it, the other branches never fire. The join keeps waiting, and the work after it never runs.

The opposite mismatch. An exclusive join only passes flows through. It does not merge concurrent flows the way a parallel gateway does (f9). Merging a parallel split with an exclusive join therefore causes lack of synchronization, not a deadlock (f5). See the article “Lack of Synchronization”.

Other ways to get stuck. An exclusive gateway with no matching condition and no default flow creates an incident, and the instance gets stuck. A default flow avoids this (f10). An inclusive (OR) join completes only under defined conditions. Either all incoming flows were taken at least once, or no path from any active node can still deliver one (f11). Misusing it can also block the flow.

Link to soundness. Soundness is a quality check for process models. It has three parts: option to complete, proper completion, and no dead activities (f3). Option to complete guarantees that no deadlocks occur (f2). Proper completion means each token ends in a different end event (f4). A dead activity is one that no instance can ever execute (f3). See “Soundness of Process Models”.

Detection. Soundness comes from Petri nets and workflow nets, which are formal models of token flow. Translating BPMN into Petri nets is not always possible, so a dedicated open-source soundness checker exists (f6).

Example

Section titled “Example”

An order process starts with an exclusive gateway: “Pay by card” or “Pay by invoice”. Both paths lead into a parallel join before “Ship order”. Only one path ever runs. The join waits for a token from the other path, which never comes. The order never ships, and the process never reaches its end. The fix is to use an exclusive join where the two paths meet, so it passes on whichever token arrives.

Trade-offs

Section titled “Trade-offs”

Choosing a join type is a trade-off. A parallel join waits for every branch, which is right after a parallel split but blocks after an exclusive split. An exclusive join never blocks, but it does not synchronize concurrent branches. That leads to lack of synchronization (f5, f7, f9).

Deadlock: an exclusive split feeds a parallel join, which waits forever for the second token.

Diagram source 
<?xml version="1.0" encoding="UTF-8"?>
<definitions xmlns="http://www.omg.org/spec/BPMN/20100524/MODEL" xmlns:bpmndi="http://www.omg.org/spec/BPMN/20100524/DI" xmlns:dc="http://www.omg.org/spec/DD/20100524/DC" xmlns:di="http://www.omg.org/spec/DD/20100524/DI" targetNamespace="http://example.com/deadlock">
  <process id="p1" isExecutable="false">
    <startEvent id="s" name="Order received">
      <outgoing>f1</outgoing>
    </startEvent>
    <exclusiveGateway id="xor" name="Payment type?">
      <incoming>f1</incoming>
      <outgoing>f2</outgoing>
      <outgoing>f3</outgoing>
    </exclusiveGateway>
    <task id="card" name="Pay by card">
      <incoming>f2</incoming>
      <outgoing>f4</outgoing>
    </task>
    <task id="inv" name="Pay by invoice">
      <incoming>f3</incoming>
      <outgoing>f5</outgoing>
    </task>
    <parallelGateway id="and" name="Join (waits for both)">
      <incoming>f4</incoming>
      <incoming>f5</incoming>
      <outgoing>f6</outgoing>
    </parallelGateway>
    <task id="ship" name="Ship order">
      <incoming>f6</incoming>
      <outgoing>f7</outgoing>
    </task>
    <endEvent id="e" name="Order done">
      <incoming>f7</incoming>
    </endEvent>
    <sequenceFlow id="f1" sourceRef="s" targetRef="xor" />
    <sequenceFlow id="f2" sourceRef="xor" targetRef="card" />
    <sequenceFlow id="f3" sourceRef="xor" targetRef="inv" />
    <sequenceFlow id="f4" sourceRef="card" targetRef="and" />
    <sequenceFlow id="f5" sourceRef="inv" targetRef="and" />
    <sequenceFlow id="f6" sourceRef="and" targetRef="ship" />
    <sequenceFlow id="f7" sourceRef="ship" targetRef="e" />
  </process>
  <bpmndi:BPMNDiagram id="BPMNDiagram_p1">
    <bpmndi:BPMNPlane id="BPMNPlane_p1" bpmnElement="p1">
      <bpmndi:BPMNShape id="BPMNShape_s" bpmnElement="s">
        <dc:Bounds x="80" y="102" width="36" height="36" />
        <bpmndi:BPMNLabel>
          <dc:Bounds x="68" y="143" width="60" height="28" />
        </bpmndi:BPMNLabel>
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_xor" bpmnElement="xor" isMarkerVisible="true">
        <dc:Bounds x="216" y="95" width="50" height="50" />
        <bpmndi:BPMNLabel>
          <dc:Bounds x="212" y="62" width="58" height="28" />
        </bpmndi:BPMNLabel>
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_card" bpmnElement="card">
        <dc:Bounds x="366" y="80" width="100" height="80" />
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_inv" bpmnElement="inv">
        <dc:Bounds x="366" y="240" width="100" height="80" />
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_and" bpmnElement="and" isMarkerVisible="true">
        <dc:Bounds x="566" y="95" width="50" height="50" />
        <bpmndi:BPMNLabel>
          <dc:Bounds x="550" y="62" width="83" height="28" />
        </bpmndi:BPMNLabel>
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_ship" bpmnElement="ship">
        <dc:Bounds x="716" y="80" width="100" height="80" />
      </bpmndi:BPMNShape>
      <bpmndi:BPMNShape id="BPMNShape_e" bpmnElement="e">
        <dc:Bounds x="916" y="102" width="36" height="36" />
        <bpmndi:BPMNLabel>
          <dc:Bounds x="898" y="143" width="73" height="14" />
        </bpmndi:BPMNLabel>
      </bpmndi:BPMNShape>
      <bpmndi:BPMNEdge id="BPMNEdge_f1" bpmnElement="f1">
        <di:waypoint x="116" y="120" />
        <di:waypoint x="216" y="120" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f2" bpmnElement="f2">
        <di:waypoint x="266" y="120" />
        <di:waypoint x="366" y="120" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f4" bpmnElement="f4">
        <di:waypoint x="466" y="120" />
        <di:waypoint x="566" y="120" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f6" bpmnElement="f6">
        <di:waypoint x="616" y="120" />
        <di:waypoint x="716" y="120" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f7" bpmnElement="f7">
        <di:waypoint x="816" y="120" />
        <di:waypoint x="916" y="120" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f3" bpmnElement="f3">
        <di:waypoint x="241" y="145" />
        <di:waypoint x="241" y="280" />
        <di:waypoint x="366" y="280" />
      </bpmndi:BPMNEdge>
      <bpmndi:BPMNEdge id="BPMNEdge_f5" bpmnElement="f5">
        <di:waypoint x="466" y="280" />
        <di:waypoint x="591" y="280" />
        <di:waypoint x="591" y="145" />
      </bpmndi:BPMNEdge>
    </bpmndi:BPMNPlane>
  </bpmndi:BPMNDiagram>
</definitions>

Checks

Section titled “Checks”
  • Every parallel (AND) join in the process models is preceded by a parallel split, so no branch can fail to deliver a token.
  • Every exclusive gateway has a default flow or conditions that cover all cases.
  • Process models have been checked for soundness, including option to complete.
  • Inclusive (OR) joins are used only where their completion conditions are understood.
Section titled “Related”

Sources

Section titled “Sources”