Module-5

Discrete Time and Other

Modelling Tools
[Link] Renold, SCOPE,VIT
Contents
Discrete
Event
Models
● Discrete event models are a type of simulation model
used to represent systems where changes occur at
distinct points in time, rather than continuously. In these
models, the system state changes only at specific events,
which can be triggered by various factors such as the
arrival of a customer, the completion of a service, or the
occurrence of a failure.
• The key components of discrete event simulation include:

• Events: Specific occurrences that change the state of the system.

• Event List: A schedule of upcoming events that need to be
processed.
• State Variables: Variables that define the current state of the
system.
2. Hard Firm Soft Real time Control
Systems
● Hard Real-Time Systems
• Hard real-time systems have extremely strict timing constraints. In these
systems, failing to meet a deadline can lead to catastrophic consequences,
such as loss of life or significant damage to equipment.
• Characteristics:
• Deterministic Behavior: These systems must guarantee that critical tasks
will be completed within a specified time frame.
• Examples: Applications include medical devices (like pacemakers),
industrial automation systems, and safety-critical systems such as airbag
deployment in vehicles. In these cases, missing a deadline is considered
a system failure
● Firm Real-Time Systems
• Firm real-time systems are somewhat less stringent than hard real-time
systems. While they still have deadlines, missing a deadline does not result
in catastrophic failure; however, it may lead to a loss of value or utility.
• Characteristics:
• Deadline Importance: Responses that miss their deadlines are
considered useless, but the system can still function without them.
• Examples: An example might be a video streaming service where frames
must be delivered on time for smooth playback. If a frame is late, it may
not be displayed, but the overall system continues to operate
effectively.
● Soft Real-Time Systems
• Soft real-time systems have the most relaxed timing constraints. In these
systems, meeting deadlines is important but not critical. Delays may
degrade the quality of service but do not cause system failure.
• Characteristics:
• Graceful Degradation: The system can tolerate missed deadlines, and
the performance may degrade gracefully.
• Examples: Examples include multimedia applications, such as video
conferencing or online gaming, where occasional delays may affect user
experience but do not stop the system from functioning
● Hard Real-Time System:
• The QoR (Quality of Result) is fixed, meaning there is a strict requirement to meet a
specific quality threshold.
• The task must be completed exactly by the deadline, and there is no flexibility if the
deadline is missed. If it does, the result is considered unacceptable.
• The graph shows that as time approaches the deadline, the QoR remains stable, but
after the deadline, QoR drastically drops to zero, meaning the system fails.
● Soft Real-Time System:
• The QoR has an acceptable range, meaning the result quality can vary.
• The system allows some flexibility after the deadline. If the task is completed slightly
late, the QoR gradually decreases but does not immediately become unacceptable.
• The graph shows that QoR peaks around the deadline, but even if it slightly exceeds
the deadline, some QoR is maintained, although less optimal than within the deadline.
•DiscreteClock: Periodic event signals.
•PoissonClock: Random error event signals.
3. Petrinet
Petri net modeling is a mathematical and graphical tool used to describe and
analyze the behavior of concurrent systems. Developed by Carl Adam Petri
in the early 1960s, Petri nets provide a way to model systems where multiple
events can occur simultaneously and where the state of the system is
determined by conditions and transitions.
Places: Represent conditions or states in the system.
Graphically, places are depicted as circles.
Transitions: Represent events that can change the
state of the system. Transitions are shown as
rectangles or bars.
Tokens: Represent the presence of a certain condition
or resource. Tokens reside in places and are depicted
as dots or small circles within the places.
Arcs: Connect places to transitions (input arcs) and
transitions to places (output arcs), indicating the flow
of the system. Arcs are shown as arrows.
 Example: EFTPOS System

(EFTPOS= Electronic Fund Transfer Point of Sale)

1 digit 1 digit 1 digit 1 digit

Initial d1 d2 d3 d4

OK
OK OK
OK
OK OK
pressed

Rejected Reject

Initial state
Approved
Final state
Example: EFTPOS System (A Petri net)

1 digit 1 digit 1 digit 1 digit d4

Initial d1 d2 d3

OK
OK OK OK
OK

OK
pressed
Rejected!
Reject approve

approved
A vending machine starts in the ‘0 Rs’ state. Users
can deposit rupees (5 Rs, 10 Rs, or 15 Rs) and select
snack bars. If a user deposits 20 Rs, they can take a
snack bar and return to the initial state. What are
the possible transitions and states for this vending
machine?
 Example: Vending Machine (FSM)

Deposit 15 Rs

Deposit 10 Rs
5 Rs 15 Rs

0 Rs

Deposit 10 Rs
10 Rs 20 Rs

Take 20 Rs snack bar

 Example: Vending Machine (A Petri net)

Deposit 15 Rs
Deposit 10 Rs
15 Rs
5c
Deposit 5 Rs

Deposit Deposit
Deposit 5 Rs
0 rs 5 Rs 5 Rs

Deposit 10 Rs
10c 20 Rs
Deposit 10 Rs
Take 20 Rs bar
Timed Automata
● Timed automata are a formal modeling framework used to represent
systems that operate under timing constraints.
● They extend the concept of finite automata by incorporating real-valued
clocks, allowing for the modeling of time-dependent behaviors in systems.
● This makes timed automata particularly useful for analyzing and
verifying real-time systems, such as embedded systems, communication
protocols, and control systems.
 Structure of Timed Automata
A timed automaton consists of the following key components:
1. States: These represent the various conditions or configurations of the
system at any given time.
2. Transitions: These are the rules that dictate how the system moves from
one state to another. Transitions can be triggered by events or can occur
after certain time conditions are met.
3. Clocks: Real-valued variables that measure the passage of time. Clocks can
be used in guards (conditions) on transitions, allowing for precise control
over when transitions can occur based on the current values of the clocks.
4. Clock Constraints: These are conditions that involve the clocks and
determine when transitions can be taken. For example, a transition might
only be allowed if a certain clock is less than a specified value.
● Operational Semantics
● The operational semantics of timed automata define how the
system evolves over time.
● The state of a timed automaton is described not only by its current
state but also by the values of its clocks.
● As time progresses, the values of the clocks increase, and the
automaton can transition to new states when the clock constraints
are satisfied.
Simple Light Control

● States and Transitions:

1. Off:
1. The light is initially off.
2. Press once: Moves to the "Light" state,
turning the light on at a normal brightness.
2. Light (Normal brightness):
1. Press once: Moves to the "Bright" state,
making the light brighter.
2. Press again: Returns to the "Off" state,
turning the light off.
3. Bright (Maximum brightness):
1. Press once: Returns to the "Off" state,
turning the light off.
● A timed automaton is needed for the light control system described in the
image because the behavior of the system depends not just on the sequence of
events (pressing the button) but also on the timing between these events.
● Why Use Timed Automata?
Quick Double Press Detection:
1. The system specifies that when in the "Off" state, a quick double press should

result in the light transitioning directly to the "Bright" state.

2. To differentiate between a quick double press (which should make the light go

straight to "Bright") and two separate presses with a longer delay (which follow
the normal sequence from "Off" to "Light" to "Bright"), the system needs to
measure the time between button presses.
● Consider a printer system modeled using timed automata, consisting of two processes:
USER and PRINTER.
● The USER process transitions from an initial state (Idle) to a state where it submits print
requests (order!) and increments a global counter to track the number of jobs in the
queue.
● The PRINTER process listens for this print request, and if counter ≥ 1, it moves from its
Start state to the Queue state, eventually transitioning to the Printing and Print
Completed states.
● Design a traffic light control system at an intersection using timed
automata. The intersection has three states for the traffic lights: Red, Green,
and Yellow. The light transitions between these states with the following
rules:
1. Green lasts for 60 seconds.
2. Yellow lasts for 5 seconds, as a warning before turning red.
3. Red lasts for 55 seconds, allowing traffic from the perpendicular direction to
move.
4. The system should immediately transition back to the Green state after the
Red light period, repeating the cycle continuously.
28

Explain the following●1. Train States: far, near, in

Controller States:
● s0: Initial state, waiting for an approach
signal.
● s1: The controller is processing the
approach signal and preparing to lower the
gate.
● s2: The gate is fully lowered, blocking
traffic.
● s3: The controller is preparing to raise the
gate after receiving an exit signal.
1. Gate States:
● up: The gate is open.
● coming down: The gate is in the process of
closing.
● down: The gate is closed.
● going up: The gate is in the process of
opening.