東京大学 情報理工学系研究科 コンピュータ科学専攻 2018年2月実施 問題4
Author
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 registerR
from a memory addressA
, - (ii) add 1 to
R
, and - (iii) store the value of
R
toA
.
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 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 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 key
is a local variable.
Answer appropriate expressions that fill the blanks from (F) to (I).
Kai
(1)
Its
(2)
Test-and-set writes
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;