Skip to content

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

Author

kainoj

Description

Consider the following task pool problem on a shared-memory system. Several worker processes concurrently execute the following program written in the C language:

1
2
3
4
5
6
7
8
while (1) {
    k = queue_head++;
    if (k < N) {
        process(buffer[k]);
    } else {
        break;
    }
}

Among the processes, only the variable queue_head, the array buffer, and the constant N (the size of the array buffer) are shared. The value of queue_head is initially \(0\). The buffer is filled with data before execution, and each data must be processed exactly once.

Answer the following questions.

(1) The above processes may fail to work properly in an actual runtime environment, because mutual exclusion is not implemented. Show an example situation in which the above processes fail.

(2) Name at least two approaches to attain mutual exclusion.

(3) Choose one approach from your answers for Question (2). Explain its basic mechanism. Then explain how to solve the above task pool problem with it.

Kai

(1)

Suppose that there are two processes. One of them may load value of queue_head before the other stores back incremented value. Then, both processes will access the same buffer element, although they must not.

(2)

Semaphores (binary, counting), locks (test&set, swap), monitors.

(3)

A semaphore is a shared variable with two defined operations executing atomically: wait and signal. wait() decrements semaphore value, and if the value becomes less than zero, then process calling wait() is made to sleep and is pushed to a queue. signal() increments semaphore value and, if the value is still negative, wakes up process at the beginning of the queue.

Note, that we only need to assure that every process is assigned different value of queue_head. Initial setting:

1
Semaphore mutex = Semaphore(1);

Code:

1
2
3
4
5
while(1) {
    wait(mutex);
    k = queue_head++;
    signal(mutex);
    ...