跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 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:

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

题目描述​

考虑共享内存系统中的任务池问题。若干工作进程并发执行题中给出的 C 程序：每次通过 k = queue_head++ 取得一个任务下标；若 k<Nk<N，则处理 buffer[k]，否则退出循环。进程之间仅共享变量 queue_head、数组 buffer 和表示数组大小的常量 NN。queue_head 初值为 00，buffer 在执行前已装入数据，并要求每份数据恰好处理一次。

回答下列问题。

（1）上述程序没有实现互斥，因此在实际运行环境中可能不能正确工作。给出一个会导致程序失败的具体执行情形。

（2）列举至少两种实现互斥的方法。

（3）从第（2）问的答案中选择一种方法，说明其基本机制，并说明如何用它解决上述任务池问题。

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:

Semaphore mutex = Semaphore(1);

Code:

while(1) {
    wait(mutex);
    k = queue_head++;
    signal(mutex);
    ...
本页目录