Home > Error Max > Promela Spin

Promela Spin

Contents

The return value can be passed back to the calling process via a global variable, or via a message. proc 1 (transfer) line 15, Recv ack,12 <- queue 1 (chin) proc 2 (channel) line 29, Recv ack,99 <- queue 2 (in) proc 3 (transfer) line 15, Recv ack,99 <- queue The semantics of the selection and cycling statements in Promela is also rather different from other guarded command languages: the statements are not aborted when all guards are false but they Try to find this sequence and understand how it violates the liveness property.

acceptance cycles - (not selected) The minus indicates that the search did not check for the presence of acceptance or non-progress cycles. Initially, in the Promela model, just one process will be executed: a process of type init, that must be declared explicitly in every Promela specification. mtype = { ack, nak, err, next, accept }; proctype transfer(chan in,out,chin,chout) { byte o, i; in?next(o); do :: chin?nak(i) -> out!accept(i); chout!ack(o) :: chin?ack(i) -> out!accept(i); in?next(o); chout!ack(o) :: chin?err(i) Consider the following example.

Promela Spin

The first option in the selection structure of the process of type C is executable if the channel contains a message a, where a is a constant with value 1, defined For a hint of their purpose, see ``Digging Deeper'' at the end of this manual. The smallest possible Promela specification, therefore, is: init { skip } where skip is a dummy, null statement.

By using the mtype keyword in channel declarations, the corresponding message field will always be interpreted symbolically, instead of numerically. The value of MAX is not really too interesting, as long as it is larger than the range of the sequence numbers in the protocol: in this case 2. COLLAPSE a state vector compression mode; collapses state vector sizes by up to 80% to 90% (see Spin97 workshop paper) variations: add -DSEPQS or -DJOINPROCS (off by default) MA=N use a Spin Examples It grants two processes mutually exclusion access to an arbitrary critical section in their code, by manipulation three additional global variables.

The relevant behavior is modeled in Promela and verified. Promela Tutorial As indicated, all collissions are resolved in full search mode, since all states are placed in a linked list. Hoare's language was based exclusively on synchronous communication. The normal way to terminate the repetition structure is with a break statement.

That means that the verification of Spin take into account all possible relative timings of the three processes. Spin Painter For instance, use 23 if you expect 8 million reachable states and can use 8 million bits of memory (i.e., 223 bits is 8 million bits, which requires 2 20 or The assertions can formalize invariant relations about the values of variables or about allowable sequences of events in the model. Options The executable analyzer that is generated comes with a modest number of options that can be checked as follows $ ./pan -- -cN stop at Nth error (default=1) -l find

Promela Tutorial

In this case the output is: $ run -c0 assertion violated (i == (last_i + 1)) vector 64 byte, depth reached 60, errors: 5 165 states, stored 5 states, linked 26 chout!ack,99 2 . . Promela Spin In this case a dummy statement skip is useful: it is a place holder that is always executable and has no effect. Promela Examples HC a state vector compression mode; collapses state vector sizes down to 32+16 bits and stores them in conventional hash-table (a version of Wolper's hash-compact method -- new in version 3.2.2.)

Generated Sun, 20 Nov 2016 22:12:46 GMT by s_hp90 (squid/3.5.20) Again, nothing bad will happen if a statement happens to be non-executable. If more than one value is to be transferred per message, they are specified in a comma separated list qname!expr1,expr2,expr3 qname?var1,var2,var3 If more parameters are sent per message then the message It provides a vehicle for making abstractions of protocols (or distributed systems in general) that suppress details that are unrelated to process interaction. Promela Syntax

Please try the request again. chout!ack,10 2 . . The option is explained in the section on ``More Advanced Usage.'' The executable analyzer has two other options. init { run A(); run B() } run is used as a unary operator that takes the name of a process type (e.g.

Advanced Usage The modeling language has a few features that specifically address the verification aspects. To see how many non-progress cycles there are, we can use the -c flag. when the state vector is 1 byte longer than a multiple of 4 the memory allocator ends up adding 3 dummy bytes to secure memory alignment.

The last option -w N can only affect the run time, not the scope, of an analysis with a full state space.

It is unexecutable if this cannot be done, for instance if too many processes are already running. Set the search depth to 50 and run the verification. Communication via message channels can be defined to be synchronous (i.e., rendezvous), or asynchronous (i.e., buffered). The verification produces: $ spin -a hyman2 $ gcc -o pan pan.c $ ./pan assertion violated ((cnt==0)||(cnt==1)) pan: aborted (at depth 15) pan: wrote pan.trail full statespace search for: assertion violations

In a full verification, the assertion therefore can be evaluated at any time during the lifetime of the other two processes. Using a zero as an argument to the first option forces the state space search to continue, even if errors are found. Promela also allows for message type definitions that look as follows: mtype = { ack, nak, err, next, accept } This is a preferred way of specifying the message types since The timeout condition becomes true only when no other statements within the distributed system is executable.

As the hash factor approaches 1 the coverage approaches 0%. it slows down the search, but can save memory. In the example, process declaration B contains a single statement that decrements the value of the state variable by one. To force termination we could modify the program as follows.

Since this is a full statespace search that ran to completion this means that these transitions are effectively unreachable (dead code). In particular, if a Promela is checked for the presence of deadlocks, the verifier must be able to distinguish a normal end state from an abnormal one. It does not necessarily prevent the monopolization of the access to the critical section by one of the processes. The trail can be inspected in detail by invoking Spin with the -t option.

byte count; proctype counter() { do :: count = count + 1 :: count = count - 1 :: (count == 0) -> break od } Only one option can be In the dijkstra example, for instance, we can label the successful passing of a semaphore test as ``progress'' and ask a verifier to make sure that there is no cycle in The reduction in complexity can be dramatic. chin?ack,11 1 . . .

Curious to find out more, we can repeat the run with more verbose output, e.g. In the first case another process can send a message to channel qname just after this process determined that the channel was not full.