Transcript C i-1

Formal Model for Simulations
Instructor: DR. Lê Anh Ngọc
Presented by – Group 6:
1. Nguyễn Sơn Hùng
2. Lê Văn Hùng
3. Nguyễn Xuân Hậu
4. Nguyễn Xuân Tùng
AGENDA

1. Introduction and Problem Specifications

2. Communication Systems

3. Modeling Process

4. Admissibility

5. Simulations
2/33
1. Introduction
There are so many way to be solved
specifying a problem in DS that we
approach about system simulations
and algorithms instead of looking
inside an algorithm.
 It is focused on the interface between
the device's algorithm or processor
with the outside world.

3/33
Introduction
4/33
Techniques applied


Layering is the technique that allows
system designers to control the
complexity of building large-scale
systems
Specification sub-system P as a set of
inputs in(P), a set of outputs out(P), and
a set of allowable sequences seq(P) of
inputs and outputs:
5/33
Problem Specifications
Problem
specification when
put conditions
(sequence, time,...)
on processor
states as they
relate to each
other and to initial
states.
6/33
Problem Specifications
Mutual Exclusion Example

inputs:
◦ T0, …, Tn-1
 Ti indicates pi wants to try to enter the critical section
◦ E0,…, En-1
 Ei indicates pi wants to exit the critical section

outputs:
◦ C0,…,Cn-1
 Ci indicates pi may now enter the critical section
◦ Ri,…,Rn-1
 Ri indicates pi may now enter the remainder section
7/33
Problem Specifications

Mutual Exclusion Example
a sequence  of inputs and outputs
is allowable iff, for each i,
◦  | i cycles through Ti, Ci, Ei, Ri
 each proc cycles through trying, critical, exit,
and remainder sections in that order
◦ whenever Ci occurs, most recent preceding
input or output for any j ≠ i is not Cj
 only one process is in the critical section at a
time
8/33
Problem Specifications
Mutual Exclusion Example: allowable
p1
T1
p0
T0
C0
E0
R1
T2
Mutual
Exclusion
C2
E2
p2
R2
T0 T1 C0 T2 E0 C2 R1 E2 R2 …
9/33
Problem Specifications
Mutual Exclusion Example: not allowable
p1
T1
p0
T0
C0
E0
T2
Mutual
Exclusion
C2
p2
T0 T1 C0 T2 C2 … E0 C2 …
10/33
2. Communication Systems So Far

So far, we have explicitly modeled the
communication system
◦ inbuf and outbuf state components and
deliver events for message passing,
◦ explicit shared variables as part of
configurations for shared memory

Not so convenient when we want to
study how to provide one kind of
communication in software, given
another kind.
11/33
Different Kinds of Communication
Systems

Message passing vs. shared memory
◦ different interfaces (sends/receives vs.
invocations/responses)

Within message passing:
◦ different levels of reliability, ordering
◦ different guarantees on content (when
malicious failures are possible)

Within shared memory:
◦ different shared variable semantics
12/33
What Kinds of Simulations?





How to provide broadcast (with different
reliability and ordering guarantees) on top of
point-to-point message passing
How to provide shared objects on top of
message passing
How to provide one kind of shared objects on
top of another kind
How to provide stronger synchrony on top of
an asynchronous system
How to provide better-behaved faulty
processors on top of worse-behaved ones
13/33
New Way to Model Communication
Systems
Interpose a communication system
between the processors
 A particular type of communication system
is specified using the approach just
described

◦ focus on the desired behavior of the
communication system, as observed at its
interface, instead of the details of how that
behavior is provided
14/33
Asynchronous Point-to-Point Message
Passing Example
Interface is:
 inputs: sendi(M)
◦ models pi sending set of msgs M
◦ each msg indicates sender and recipient
(must be consistent with assumed topology)

outputs: recvi(M)
◦ models pi receiving set of msgs M
◦ each msg in M must have pi as its recipient
15/33
Asynch MP Example (cont…)

For a sequence of inputs and outputs (sends
and receives) to be allowable, there must exist
a mapping  from the msgs in recv events to
msgs in send events s.t.
◦ each msg in a recv event is mapped to a msg in a
preceding send event
◦  is well-defined: every msg received was previously
sent (no corruption or spurious msgs)
◦  is one-to-one: no duplicates
◦  is onto: every msg sent is received
16/33
Asynchronous Broadcast Example

Inputs: bc-sendi(m)
◦ an input to the broadcast service
◦ pi wants to use the broadcast service to send
m to all the procs

Outputs: bc-recvi(m,j)
◦ an output of the broadcast service
◦ broadcast service is delivering msg m, sent by
pj, to pi
17/33
Asynch Bcast Example (cont…)

A sequence of inputs and outputs (bc-sends
and bc-recvs) is allowable iff there exists a
mapping  from each bc-recvi(m,j) event to an
earlier bc-sendj(m) event s.t.
◦  is well-defined: every msg bc-recv'ed was
previously bc-sent
◦  restricted to bc-recvi events, for each i, is one-toone: no msg is bc-recv'ed more than once at any
single proc.
◦  restricted to bc-recvi events, for each i, is onto:
every msg bc-sent is received at every proc.
18/33
3. Modeling Process
Proposed facility


May be several algorithms (processes) runs on
each processor to simulate the desired
communication system.
For example, a processor run two algorithms
(processes) at the same time
◦ one process (algorithm) that uses the broadcast
service
◦ another process (algorithm) that implements the
asynchronous broadcast system on top of the
asynchronous point-to-point message-passing
system
19/33
Modeling Process (Cont.)
Algorithm (process) composition

Ordering of process, forming a “Stack of
protocols”
◦ Environment communicates with the top layer
◦ Each process uses communication primitives to
interact with the layer beneath it
◦ The bottom layer communicates with the
Communication System
20/33
Simulation for Modeling Process
environment
layer 1
modeled
as state
machines
layer 2
modeled as a problem
spec (interface &
allowable sequences)
communicate via
appropriate primitives:
shared events
layer 3
communication system
Layered model
modeled as a problem
spec (interface &
allowable sequences)
21/33
Simulation for Modeling Process
(Cont…)
environment
Send
layer 1
Send
layer 2
Send
layer 3
Send
communication system
Propagation of events
22/33
Modeling Process Specifications
(Cont…)

A system consists of
◦ A collection of n processors (or nodes), p0 through pn-1
◦ A communication system C linking the nodes
◦ Environment E

Notes
◦ Environment E and Communication system C are given as
problem specifications
◦ Node is a hardware notion
◦ Running on each node are one or more processes
 Processes are organized into a single stack of layers
 The same number of layers on each node
23/33
Modeling Process Specifications
(Cont…)

Each process is state machine (modeled as an
automaton)
◦ Has a set of states, including a subset of initial states
◦ Has hour kinds of events
 Inputs coming in from the layer above (or the environment, if
this is the top layer)
 Outputs going out to the layer above
 Inputs coming in from the layer below (or the communication
system, if this is the bottom layer)
 Outputs going out to the layer below
◦ Events of type 1 and 2 form the top interface of the process
◦ Events of type 3 and 4 form the bottom interface of the
process
24/33
layer i - 1
1
2
Top interface of layer i
layer i
4
3
Bottom interface of layer i
layer i + 1
Propagation of events
25/33
Modeling Process Specifications
(Cont…)

Events
◦ Concepts
 An event is said to be enabled in a state of a
process if there is a transition from that state
labeled with that event
 Inputs from the environment and from the
communication system are called node inputs

A configuration of the system specifies a
state for every process on every node
◦ A configuration does not include the state of
the communication system
◦ An initial configuration contains all initial
states
26/33
Modeling Process Specifications
(Cont…)

An execution of the system is a sequence C0 e1 C1 e2 C2 … of alternating
configurations Ci and events ei
◦ If it is finite, ending with a configuration
◦ Satisfies the following conditions
 C0 is an initial configuration
 event ei is enabled in Ci-1 (there is a transition from the state(s) of the
relevant process(es) in Ci-1 labeled ei)
 state components of processes change according to the transition functions
for ei
 can chop the execution into pieces so that
 each piece starts with a node input
 all events in each piece occur at the same node
 the next node input does not occur until no events (other than node
inputs) are enabled

Schedule of an execution is the sequence of events in execution , without the
configurations.
◦
top()/bot() are schedule only including the events of the top/bottom
27/33
4. Admissibility
Definition of Admissible Execution

We only require an algorithm to be correct
if
◦ each process is given enough opportunities to
take steps (called fairness)
◦ the communication system behaves "properly"
and
◦ the environment behaves "properly"

Executions satisfying these conditions are
admissible.
28/33
Proper Behavior of Communication
System
The restriction of the execution to the
events of the interface at the "bottom of
the stack" is an allowable sequence for
the problem specification corresponding
to the underlying communication system
 Example: message passing, every
message sent is eventually received

29/33
Proper Behavior of Environment
The environment (user) interacts
"properly" with the top layer of the stack
(through the interface events) as long as
the top layer is also behaving properly.
 Mutex example: the user only requests to
leave the critical section if it is currently in
the critical section.

30/33
5. Simulations
System C1 simulates system C2 if there is a set of
processes, one per node, called Sim s.t.
1. top interface of Sim is the interface of C2
2. bottom interface of Sim is the interface of C1
3. For every admissible execution  of Sim, the
restriction of  to the interface of C2 is
allowable for C2 (according to its problem
spec).
31/33
Simulations
C2 inputs
C2 outputs
Sim
…
Sim0
C1 inputs
C2 inputs
C1 outputs
C2
C2 outputs
Simn-1
C1 inputs
C1 outputs
C1
If user of C2 behaves properly and if C1 behaves properl
then Sim ensures that user of C2 thinks it is really using
C2 (and not C1 plus a simulation layer)
32/33
Thank you for listening
33/33