12

I'm not quite sure as to what this term means. I saw it during a course where we are learning about concurrency. I've seen a lot of definitions for data interleaving, but I could find anything about process interleaving.

When looking at the term my instincts tell me it is the use of threads to run more than one process simultaneously, is that correct?

mdw7326
  • 163
  • 1
  • 1
  • 9
  • 1
    Could you tell me why you down voted my question? I thought it was valid.. if I'm doing something wrong please let me know – mdw7326 Apr 13 '14 at 21:29

3 Answers3

6

If you imagine a process as a (possibly infinite) sequence/trace of statements (e.g. obtained by loop unfolding), then the set of possible interleavings of several processes consists of all possible sequences of statements of any of those process.

Consider for example the processes

int i;

proctype A() {
  i = 1;
}

proctype B() {
  i = 2;
}

Then the possible interleavings are i = 1; i = 2 and i = 2; i = 1, i.e. the possible final values for i are 1 and 2. This can be of course more complex, for instance in the presence of guarded statements: Then the next possible statements in an interleaving sequence are not necessarily those at the position of the next program counter, but only those that are allowed by the guard; consider for example the proctype

proctype B() {
  if
    :: i == 0 -> i = 2
    :: else   -> skip
  fi
}

Then the possible interleavings (given A() as before) are i = 1; skip and i = 2; i = 1, so there is only one possible final value for i.

Indeed the notion of interleavings is crucial for Spin's view of concurrency. In a trace semantics, the set of possible traces of concurrent processes is the set of possible interleavings of the traces of the individual processes.

dsteinhoefel
  • 688
  • 4
  • 13
5

It simply means performing (data access or execution or ... ) in an arbitrary order**(see the note). In the case of concurrency, it usually refers to action interleaving. If the process P and Q are in parallel composition (P||Q) then the actions of these will be interleaved. Consider following processes:

PLAYING = (play_music -> stop_music -> STOP).
PERFORMING = (dance -> STOP).

||PLAY_PERFORM = (PLAYING || PERFORMING).

So each primitive process can be shown as: (generated by LTSA model-cheking tool) enter image description hereenter image description here

Then the possible traces as the result of action interleaving will be:

dance -> play_music -> stop_music
play_music -> dance -> stop_music
play_music -> stop_music -> dance

Here is the LTSA tool generated output of this example. enter image description here

**note: "arbitrary" here means arbitrary choice of process execution not their inner sequence of codes. The code execution in each process will be always followed sequentially.

If it is still something that you're not comfortable with you can take a look at: https://www.doc.ic.ac.uk/~jnm/book/firstbook/pdf/ch3.pdf

Hope it helps! :)

Kasra
  • 891
  • 1
  • 10
  • 17
0

Operating Systems support Tasks (or Processes). But for now let's think of "Actitivities".

Activities can be executed in parallel. Here are two activities, P and Q:

    P:      abc
    Q:      def

a, b, c, d, e, f, are operations. *

Each operation has always the same effect independent of what other operations may be executing at the same time (atomicity).

What is the effect of executing the two activities concurrently? We do not know for sure, but we know that it will be the same as obtained by executing sequentially an INTERLEAVING of the two activities [interleavings are also called SCHEDULES]. Here are the possible interleavings of these two activities:

    abcdef
    abdcef
    abdecf
    abdefc
    adbcef
    ......
    defabc

That is, the operations of the two activities are sequenced in all possible ways that preserve the order in which the operations appeared in the two activities. A serial interleaving [serial schedule] of two activities is one where all the operations of one activity precede all the operations of the other activity. The importance of the concept of interleaving is that it allows us to express the meaning of concurrent programs: The parallel execution of activities is equivalent to the sequential execution of one of the interleavings of these activities.

For detailed information: https://cis.temple.edu/~ingargio/cis307/readings/interleave.html

Eldar Mahmudov
  • 27
  • 8