Section 2.3 Data Sharing

Section 2.3 Data Sharing

2.3 Data Sharing

An important Multi-Pascal feature is called spinlocks, which are useful to help coordinate the sharing of data values and data structures by parallel processes.

An atomic operation performed by a process is defined as an operation that cannot be interrupted by other processes

2.3.1Concept of atomic operation

For the operation of reading and writing of an individual shared variable by parallel processes, there is a potential program error called timing-dependent error. For example, if a variable X contains the value 20 and two processes try to access the variable in parallel, as illustrated in the figure below:

Figure 2.14 Error with shared data.

Following is an another example of how this type of error could actually arise in real program, consider the following program segment to search an array for a given value and record the total number of occurrences of that value in the array:

PROGRAM Search;

VAR A: ARRAY [1..200] OF INTEGER:

i , val, n: INTEGER;

BEGIN

. . .

n:=0;

Readln(val);

FORALL i : =1 TO 200 GROUPING 10 DO

IF A[i] = val THEN n:=n+1;

Writeln(‘Total occurrences:’ , n);

To eliminate the problem a spinlock can be used. There are two simple operations-Lock or Unlock to modify the state of a spinlock. This provides a mechanism for one process to make other processes wait. Here is a new Parallel Search program that works correctly:

PROGRAM Search;

VAR A: ARRAY [1..200] OF INTEGER;

i : val, n: INTEGER;

L: SPINLOCK;

BEGIN

. . .

n :=0;

Readln(val);

FORALL i :=1 TO 200 GROUPING 10 DO

IF A[i ] = val THEN

BEGIN

Lock(L); (*Enter and lock the spinlock*)

n := n+1;

Unlock(L); (* Unlock the spinlock to allow another to enter*)

END;

Writeln('Total occurerences: ', n);

. . .

In the above program, each process must execute "Lock(L)" before performing the update of variable n. The "Lock(L)" and "Unlock(L)" operations create a kind of "fence" around the instruction "n := n+1", as shown in Figure below:

Figure 2.15 Effect of spinlocks.

This introduces an important concept in the field of parallel programming: the atomic operation. An atomic operation is performed by a single parallel process and cannot be interrupted by any other process.

The goal of the atomic operation is to allow one process to access and modify some shared data, while at the same time preventing other processes from reading or writing this data until the modification is finished. This requirement is sometimes called the classic mutual exclusion problem of parallel programming: the use of shared data by one process must "exclude" all other processes. This "exclusion" property guarantees that the operation performed is atomic.

2.3.2Spinlocks

2.3.2.1Implementation of Spinlocks

The spinlock itself is easily implemented as a program variable associated with an ordinary memory cell. By writing a 0 into the memory cell , the Unlock(L) operation is easily performed

Unlock(L): Write 0 into L;

The Lock(L)operation is slightly more complex as shown below. It requires the spinlock be examined and modified.

Lock(L):

Repeat

X:= TestandSet(L); (*Read old state and set to "locked"*)

Until X=0; (*Terminate loop if L was "unlocked"*)

All subsequent processes entering a "Lock(L)" operation will continue to busy-wait inside the loop. This is a form of process suspension, in which the process keeps computing, but is stuck inside a small loop that keeps on checking the state of spinlock.

2.3.2.2Spinlocks and Structured Types

"SPINLOCK" is a built-in data type in Multi-Pascal. Any variable name may be declared as having type "SPINLOCK in the declaration section of the main program or any procedure, ". Once a variable is declared in this way, it can be used in LOCK or UNLOCK operations in the program.

The SPINLOCK data type may be combined with the structured types- arrays and records.

For example, consider the following declarations:

VAR G: ARRAY [1..10] OF SPINLOCK;

H: ARRAY [1..10, 1..10] OF SPINLOCK;

The following are all valid operations for these arrays:

Lock(G[3]);

Unlock (H[1, 5]);

i := 2 ;

Lock(G[i ]);

Unlock (G[i +5]);

Similary, the SPINLOCK data type may also be used as a component of a Record type, as in the following declaration"

VAR item : RECORD

Data: INTEGER;

L: SPINLOCK;

END;

For this record declaration, the following are valid operations:

Lock(item. L);

Unlock(item. L);

Pointers can also be combined with spinlocks. It is possible to have a pointer to a spinlock type. The following is a valid Multi-Pascal declaration:

TYPE itempnt = ^itemtype;

Itemtype = RECORD

data: INTEGER;

L: SPINLOCK;

next: itempnt;

END;

VAR head: itempnt;

Spinlocks may also be used as procedure or function parameters, and behave in the same way as other Pascal parameters.

Using a spinlock as a VAR parameter will cause the parameter name to become an alias for the spinlock that is passed as an argument in the procedure call.

Using a spinlock as a value parameter will cause it to get a copy of the state of the spinlock argument in the procedure call.