5/1分の宿題

すっかり遅れてしまったが，5/1出題分の宿題について．

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

->死んだ時にフォークを手放すかどうかによる．フォークを手放さない場合，当然全ての哲学者は飢え死ぬことになるだろう．
死んだ際に左手に持っていたフォークを手放す場合，その死んだ哲学者の両隣の哲学者LとRは，それぞれLなら右側，Rなら左側のフォークを独占できる．
この場合，左のフォークを先に確保するアルゴリズムのため，Rは相変わらず右のフォークを獲得できないでロックする事があるが，Lは左のフォークを確保した地点で右のフォークを確実に確保できる．そのため，Lから順々にデッドロックの輪が解放されていき，結果としてRのロックは解放される．
しかし，このケースでは，生き残った哲学者全ては平等な立場では無くなる．すなわち，Lが最も有利であり，Rが最も不利な立場になる．

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?
• What happens when there are an odd number of forks?
• Can this scheme be extended to work when you need three forks to eat?

このアルゴリズムは哲学者の人数が偶数の場合，正常に動作する．
人数が奇数の場合，正常に動作しない．なぜならば1番のフォークとMAX_COUNTのフォークに囲まれている哲学者はフォークを一生取ることができない(1からナンバリングした場合，両方奇数となる)か，0番のフォークとMAX_COUNTのフォークに囲まれている哲学者はどちらのフォークを取れば良いか分からない(0からナンバリングした場合，両方偶数となる)からである．
3つのフォークをどの位置から取ってくるのかがよく分からないが，恐らくうまく動かないのではないかと思う．3つ目のフォークを確保する際に最大2つのフォークを確保済みで無ければならず，それがロックの原因になるのではないかと思う．

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.

うまく動作しない．哲学者の数とフォークの数が同じ以上，全員が一つのフォークを持って立ち往生するという本質は変わらないからである．
以下に哲学者が4人(A,B,C,D)の場合を例示する．

1. A,B,C,Dが同時にフォークを一つ取る
2. テーブルの上にフォークは一つも残らない(デッドロック)

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?

• 二つめのフォークが取れなかった場合に，マークされた哲学者であれば一度食べることをあきらめてフォークを机に戻す．
• フォークを机に戻した後，左の哲学者にマークを渡す

これで不平等さはほとんど無いのではないかと思う．

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

フォークを確保する際，取りたいフォークが机の上に無ければ手に持ったフォークを全て机に置き(Reset)，ランダムな時間空腹を我慢する．その後またフォークを取りに行けば良い．

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

Core2 DuoではLOCK命令が該当する命令だと思われる．
参照元: Intel® 64 and IA-32 Architectures Software Developer's Manuals: http://www.intel.com/products/processor/manuals/index.htm
　Volume 2A: Instruction Set Reference, A-MにLOCK命令の詳細が記述されている．

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

source:

$ cat memorycopy.c
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#define SIZE 1024000

double cputime();

int main(){
unsigned char buff[SIZE] = "homework no.7";
unsigned char buff2[SIZE];
double stime, etime;
stime = cputime();
memcpy(buff2, buff, SIZE);
etime = cputime();
printf("%d Bytes memcpy() time: %10.6f ms.\n", SIZE, etime - stime);
}

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

output:
$ ./a.out
1024000 Bytes memcpy() time: 0.003304 ms.