Concurrent Systems (CS) - Questions and Answers

Introduction

What is the difference between strict and sequential consistency?

Strict consistency requires that a read operation from a memory location always returns the value of the most recent write operation to the same location. This requirement holds for every processor of a shared-memory multiprocessor system, particularly multi-/many core systems. A consequence from this definition is the existance of absolute global time for the whole multiprocessor system in order to uniquely determine the most recent write and, thus, to make all processors see the write operations exactly in the order in which they were issued.

Sequential consistency is weaker than strict consistency. It requires that the read/write operations issued are seen by every processor in the order as specified by the non-sequential program being executed by the processors. This model allows the order of read/write operations in terms of "real time" or observed from outside the system, respectively, to be different from the order noticed by the processors inside the system.

Critical Sections

What is the use of volatile in the declaration of the external variable i local to function twofold()?

The purpose of the function is to exemplify non-repeatable read (i.e., read-write conflict), that is a data race pattern were the same read operation on shared data is consecutively performed by a process and may result in different output. Thereto, not only the source code but also the generated assembly-level code both have to contain multiple read operations as to the same variable in main memory. With volatile the compiler is forced to generate the desired assembly-level program.

Reconsider the example presented in the lecture:

int twofold() {
        extern volatile int i;

        return i + i;
}

Compilation by means of gcc -O3 -m32 -static -fomit-frame-pointer -S creates the following assembly program:

_twofold:
        movl    _i, %eax
        addl    _i, %eax
        retl

Here, two read operations take place, (1) explictly by movl and (2) implicitly by addl. These two operations correspond to the two reads that are part of the expression i + i at C level. The assembly-level representation of the C program shows vulnerability to non-repeatable read in the presence of two simultaneous processes, whereby one acts as reader and the other one acts as writer.

Now, compile the same source module as above but by adding -Dvolatile="" to remove the volatile type qualifier from the compilation unit. This results in the following assembly-level code:

_twofold:
        movl    _i, %eax
        addl    %eax, %eax
        retl

This time, only a single read operation as to the shared variable takes place. Although the C level program shows potential for non-repeatable read, the semantically equivalent assembly-level program does not. Devoid of volatile, the compiler enabled to optimise code generation in this particular case. The compiler realises the semantics of the function twofold(), namely to return the doubled value of the actual parameter, and, using register addressing mode, doubles the value just read from main memory into the (standard) value-returning register eax.