Modelling Parallel Systems - Complete
Study Notes
1. CORE CONCEPTS & INTERACTIONS
Parallel Program Interactions
Parallel programs interact and influence each other in several ways:
Types of Interactions:
• Causal relationships - One event causes another
• Communication - Direct data exchange between processes
• Coordination - Synchronization to avoid conflicts
• Competition - Competing for shared resources
Interaction Categories:
• On purpose: Direct data exchange (intended)
• Not desired: Delays caused by resource competition
Properties of Parallel Systems
Essential Properties to Maintain:
1. Determinism: Same conditions → same results
2. Free of disturbances: Predefined execution order doesn't change results
3. Mutual exclusion: At most one process uses exclusive resource at any time
4. Free of deadlocks: No cyclic waiting between processes
5. No starvation: No process postponed forever (even without deadlock)
2. PARALLEL ACTIVITIES - ABSTRACTION LEVELS
Three Abstraction Levels:
1. Model Level (Focus of this lecture)
• Action trees: Focus on actions and dependencies
• State machines: Focus on states and transitions
• Petri Nets: Combined approach
2. Programming Language Level
• Parallel sections: POSIX threads, C++, Java threads, Ada tasks
• Process hierarchies: fork, join operations
• Communications: send, recv operations
• Synchronization: lock, unlock operations
3. OS Level
• Processes: Programs in execution with own address space
• Threads: Lightweight processes with shared address space
• Communication: Shared memory, files, messages
• Synchronization: Locks, interrupts
3. ACTION TREES
Formal Definition
An action tree is a triple p = (E, ≤, α) where:
• E: Set of events (E ⊆ E*)
• ≤: Partial order over E (causality relation)
• α: Transformation α: E → A (action marking)
Key Properties
• Unique events: Each event occurs only once within a process
• Reusable actions: Different events can have same action
• Parallel/Concurrent events: Events e₁, e₂ are parallel if ¬(e₁ ≤ e₂ ∨ e₂ ≤ e₁)
• Sequential process: Causality relation ≤ is a linear order
• Finite process: Finite set of events
Causal Dependencies (Important!)
Three types of causal dependencies:
1. Real causal relations: Event e is causal for event d if d can never occur without e
2. Temporal relations: Event e ends before event d starts (Lamport's "happened before"
relation)
3. System restrictions: Mutual exclusion - events cannot occur concurrently
Graphical Representation
• Nodes: Events (marked by actions)
• Directed edges: Causal relationships
• Cycle-free: Events occur only once, actions can repeat
4. STATE MACHINES
Nondeterministic Finite Automaton (NFA)
An NFA consists of:
• S: Set of states (state space)
• A: Set of actions
• S₀: Set of possible initial states
• R ⊆ S × A × S: State transition relation
Transition Notation
• s₀ →ᵃ s₁: In state s₀, action a can be executed to reach state s₁
• Condition: (s₀, a, s₁) ∈ R
Nondeterminism
• Multiple transitions possible from same state
• Selecting different transitions leads to different follow-up states
• Conflicts: Actions and state changes can conflict (e.g., parallel assignments to same
variable)
Conflict Example
e₁: x = x + 1;
e₂: x = 2 * x;
If executed in parallel, final state cannot be uniquely determined - OS must prevent such
interference!
5. PETRI NETS
Basic Definition
A Petri Net is a triple (P, T, F) where:
• P: Finite set of places (circles) - model passive elements
• T: Finite set of transitions (rectangles) - model active elements
• F: Flow relation F ⊆ (P × T) ∪ (T × P) - directed arcs
• Constraint: P ∩ T = ∅
Notation
For node x ∈ (P ∪ T):
• Preset: •x = {y | y F x} (inputs)
• Postset: x• = {z | x F z} (outputs)
Dynamic Behavior
Capacity and Weight:
• c: P → ℕ ∪ {∞}: Place capacity (default: infinite)
• w: F → ℕ ∪ {0}: Arc weight (default: 1)
Marking:
• M: P → ℕ: Current state (tokens in places)
• Constraint: ∀p ∈ P: M(p) ≤ c(p)
Firing Rules (CRITICAL!)
A transition t ∈ T is ready to fire if:
1. Enough tokens: ∀p ∈ •t: M(p) ≥ w((p,t))
2. Capacity check: ∀p ∈ t•: M(p) ≤ c(p) - w((t,p))
Firing creates new marking M':
• Remove from input: ∀p ∈ •t ∖ t•: M'(p) = M(p) - w((p,t))
• Add to output: ∀p' ∈ t• ∖ •t: M'(p') = M(p') + w((t,p'))
• Both input and output: ∀p'' ∈ •t ∩ t•: M'(p'') = M(p'')
