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

标签：

• Tokyo-University
• Atomic-Operations
• Test-and-Set-and-Swap-Spinlocks
• Process-Synchronization

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).

题目描述

考虑多处理器系统上并发进程的互斥。假定语句 x = x + 1 分为三步：

1. 从内存地址 $A$ 将 x 的初值装入寄存器 R；
2. 将 R 加 $1$；
3. 把 R 的值存回地址 $A$。

回答下列问题。

（1）两个进程共享变量 x，且不使用互斥而并发执行 x = x + 1。若 x 初值为 $0$，列出两个进程都执行完成后 x 的所有可能值。

（2）题中代码用硬件支持的原子指令 TestAndSet 实现对 x = x + 1 的互斥，其中共享变量 x 和 lock 初值均为 $0$。 TestAndSet 原子地完成所给 C 函数的功能。填写函数中的空白（A）至（E），使外层自旋锁代码正确工作。

（3）另一原子指令 Swap 原子交换两个地址中的值。题中给出使用 Swap 实现互斥的代码，其中 x、lock 是初值为 $0$ 的共享变量， key 是局部变量。填写空白（F）至（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;