東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年2月実施 問題4

Author

kainoj

Description

In this problem, we consider mutual exclusion of concurrent processes running on a multiprocessor system. Assume that the execution of the code x = x + 1 consists of the following three operations:

• (i) load the initial value of x to a register R from a memory address A,
• (ii) add 1 to R, and
• (iii) store the value of R to A.

Answer the following questions.

(1) Consider the case where two processes share a variable x and execute x = x + 1 concurrently on this multiprocessor system without mutual exclusion. Assuming that the initial value of x is \(0\), answer all the possible values of x after both the processes complete the executions of x = x + 1.

(2) A standard way to achieve mutual exclusion of the executions of x = x + 1 is to use the TestAndSet instruction as in the following C code:

while (TestAndSet(&lock));
x = x + 1;
lock = 0;

Here, x and lock are shared variables, whose initial values are \(0\). The TestAndSet instruction, with hardware support, atomically executes the functionality that is described by the following C code. Answer appropriate expressions that fill the blanks from (A) to (E).

int TestAndSet(int *a) {
    int b;
    (A) = (B);
    (C) = (D);
    return (E);
}

(3) An alternative way to achieve mutual exclusion is to use another atomic instruction Swap, whose functionality is described by the following C code:

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

Using the Swap instruction, mutual exclusion of the executions of x = x + 1 can be achieved as follows:

int key = (F);
while ((G) == 1)
    Swap((H), (I));
x = x + 1;
lock = 0;

Here, x and lock are shared variables whose initial values are \(0\), and key is a local variable. Answer appropriate expressions that fill the blanks from (F) to (I).

Kai

(1)

Its \(1\) and \(2\). On a sequential execution we get \(2\). We can get \(1\) when one process loads a value before another process stores it.

(2)

Test-and-set writes \(1\) to memory and returns previously stored value.

int TestAndSet(int *a) {
    int b;
    b = *a;
    *a = 1;
    return b;
}

(3)

Swap:

void Swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

Answer:

int key = 1;
while (key == 1)
    Swap(&key, &lock);
x = x + 1;
lock = 0;