20090511のホームワーク

1. Ignoring the deadlock for a moment, what happens at the philosophers' table when one philosopher dies while hold a fork?

一人の哲学者がフォークを持ったまま死ぬと隣の哲学者は最大で一つのフォークしか持てなくなるなるため、死ぬ。これが繰り返し起こり、最終的には全哲学者が死ぬことになる

2. One possible solution to the dining philosophers problem is to number the forks, and require the philophers to always pick up an even-numbered fork first.

・Does this scheme work?
2人の哲学者が同時に同じフォークを掴もうとするとコンフリクトする．

・What happens when there are an odd number of forks?
5ほんのフォークがあるとすると１と５のフォークに挟まれる哲学者がいる。彼が餓死してしまう

・Can this scheme be extended to work when you need three forks to eat?
4人に対して4つのフォークしかない＝人数とフォークの数が同じであることが条件ならば
できません。
A→A以外→A→A以外の順でフォークを取るため、Aが3つのフォークを取ることはできない。



3. Another possible solution, since all forks are identical, is to pile all of the forks in the middle of the table, and have the philosophers grab any two when they want to eat. Does this work better?

・Analyze the probability of deadlock, treating time as discrete, based on the number of philosophers, probability of a philospher wanting to eat, and number of forks


デッドロックが起こる確率：全員が同時に1本ずつフォークを取る確率なので変わらない．

同時に食事できる哲学者の人数が増える。これはフォークが哲学者の隣にある場合は2つのフォークしか選べないが、テーブルの中央にある場合は最後の1本がなくなるまで選ぶことが出来るためである。

フォークの数、哲学者の数：n
現在食事している哲学者の数：m (＜n/2)

・フォークが哲学者の両隣にある場合
食事を開始できる最高人数：
(n - 1) / 2 - m（nが奇数）
n / 2 - m（nが偶数）

・フォークがテーブルの中央にある場合
食事を開始できる最高人数：
(n - 1) - m（nが奇数）
n - m（nが偶数）


4. I give you a red disk that you can use as a marker. How would create a protocol that guarantees deadlock avoidance? Is it robust against the death of one of the philosophers?


1.red diskを任意の哲学者の横に置く
2. フォークを取るときに，その哲学者はred diskをフォークの位置に置く
3. 食事をする
4. 食事が終わったら，フォークを戻し、red diskを回収する

もし別の哲学者がフォークの代わりに置かれたred diskを取ったら，その哲学者は自分の持ってるフォークとred diskを元に戻して，しばらく待つ。

これでデッドロックが起きない


5. Describe how the original Ethernet CSMA/CD scheme is like the dining philosophers problem

CSMA/CD scheme
1. まずケーブルの利用状況を調べる
2. ケーブルが空いていたら，機器がデータを送信。もし，他の機器が同時に データを送信しようとした場合，送信をやめる。
3. ランダムな時間待機した後再び1に戻る。



6. Find the synchronization primitive used in an Intel Core Duo dual-processor or an AMD on-chip multiprocessor

同期プリミティブには、セマフォ,モニタなどがある。
http://www.tokumaru.org/techterm/semaphore.html
http://www.tokumaru.org/techterm/monitor.html


7. Write a program that copies one chunk of memory to another (your OS certainly provides some memory copy library routine). Measure its performance. (We will use this information in later exercises in the course.)

#include
#include
#include
#include
#include
#include

double gettimeofday_sec();


int main(int argc, char* argv[])
{
int i = 0;
int size = 1000;
if (argc == 2) {
size = atoi(argv[1]);
}

int src[size],dst[size];
int cnt=1;
int status;
double start_time, stop_time;

for (i=0; i
src[i] = i;
}

start_time = gettimeofday_sec();
memcpy(dst, src, sizeof(int)*size);
stop_time = gettimeofday_sec();

printf("時間：%10.30f\n", stop_time - start_time);
}

double gettimeofday_sec()
{
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

[実行]
./memcpy 1000
./memcpy 1000000
[実行結果]
1000個のコピー
時間：0.000009059906005859375000000000
時間：9.06 μsec
1000000個のコピー
時間：0.009626150131225585937500000000
時間：9.63 msec