0623のHW

1.Imagine that the bitmap showing which disk blocks are free has become unreliable, so you decide to rebuild it by walking through all of the in-use inodes. Assume on-disk inodes are 128 bytes, and the file system was initialized to hold a maximum of one million files. Your disk has a transfer rate of 40 megabytes/second, and can execute a random operation in 10milliseconds. It holds 100GB.

A.If all of the inodes are stored in one contiguous chunk of disk, how long will it take to read them all?

128 * 1000000 = 128MByte
128 / 40 = 3.2 sec


B.If 100,000 of the files each use a single indirect block that is randomly placed on the disk, how long will it take to work through all of them?

100000 * 10
= 1000000 msec
= 1000 sec

C.Using the same type of disk, how long would it take to read every 4KB block on the disk in random order?
100GB / 4KB = 25000000
25000000 * 10 msec = 250000 sec

2. Do you back up the data on your computer? If so, how?
A. Execute a data backup. This backup may be of any type, using any tool, and may be just your user files or may be the entire system. You may back up to CD/DVD, external disk, tape, or over the network to a server.
scpを用いてネットワーク上のサーバへsystem()を使用して、backupを取る。
systemでscpを実行し0 byteのファイルを転送したときの時間は、10回平均で0.5936 sec
iperfで測定した通信速度は15.2Mbps

B.Report how long it took to perform your backup, and how much data was transferred.
1Gのファイルを転送する。
かかった時間は581.6871 - 0.5936 = 581.0945 sec

0616のHW

1. Report on your system configuration! What type of file system are you working on?
# df -hT
Filesystem Type サイズ 使用 残り 使用% マウント位置
/dev/sda5 ext3 29G 6.1G 22G 23% /
varrun tmpfs 994M 112K 993M 1% /var/run
varlock tmpfs 994M 0 994M 0% /var/lock
udev tmpfs 994M 48K 993M 1% /dev
devshm tmpfs 994M 12K 994M 1% /dev/shm
lrm tmpfs 994M 40M 954M 4% /lib/modules/2.6.24-24-generic/volatile

2. Determine how long a file name your system supports. First, create a temporary directory to work in. Try creating files with different length names and see what happens.
255文字のファイル名のときにSegmentation faultが起きる
これはファイル名をchar型で宣言しているため、char型のサイズを超過したためである。

3. Now see how many files you can practically put in this directory. Time the creation of new files. How long does it take to create files 1-10? 101-110? 1,001-1,010? 10,001-10,010? Keep going until performance is too bad to continue, then time the deletion of the files. Plot the performance.

1-10 time: 0.000474929809570312500000000000
101-110 time: 0.000506401062011718750000000000
1,001-1,010 time: 0.000512361526489257812500000000
10,001-10,010 time: 0.000587701797485351562500000000
100,001-100,010 time: 0.000705718994140625000000000000
1,000,001-1,000,010 time: 0.000760078430175781250000000000

4. Now do something similar for depth: what happens as you create deeper directory trees?
A.Do this problem once with relative path names. Each time you create a directory, chdir() into it before proceeding.
1-10 time: 0.000515460968017578125000000000
101-110 time: 0.000478267669677734375000000000
1,001-1,010 time: 0.000493764877319335937500000000
10,001-10,010 time: 0.000223875045776367187500000000
100,001-100,010 time: 0.000257015228271484375000000000
1,000,001-1,000,010 time: 0.000296592712402343750000000000

20090609のHW

1.Report on your progress on your project.
interrupt coalecsingの設定が出来ないでいます。
onboardのNICではないNICで試してみます。また直接プログラムからinterrupt coalescingを変更する関数を呼び出して設定してみます。
測定用のツールとしてiperfにCPU時間のユーザ時間とシステム時間を取得するコードを組み込んでいます。


2.A socket has parts both in the kernel and in the user library. Find the definition of both in an OS of your choice, and describe the differences in the information.

[linux-kernel]
1202 asmlinkage long sys_socket(int family, int type, int protocol)
1203 {
1204 int retval;
1205 struct socket *sock;
1206
1207 retval = sock_create(family, type, protocol, &sock);
1208 if (retval < retval =" sock_map_fd(sock);">nsproxy->net_ns, family, type, protocol, res, 0);
1195 }

1079 static int __sock_create(struct net *net, int family, int type, int protocol,
1080 struct socket **res, int kern)
1081 {
1082 int err;
1083 struct socket *sock;
1084 const struct net_proto_family *pf;
1085
1086 /*
1087 * Check protocol is in range
1088 */
1089 if (family <>= NPROTO)
1090 return -EAFNOSUPPORT;
1091 if (type <>= SOCK_MAX)
1092 return -EINVAL;
1093
1094 /* Compatibility.
1095
1096 This uglymoron is moved from INET layer to here to avoid
1097 deadlock in module load.
1098 */
1099 if (family == PF_INET && type == SOCK_PACKET) {
1100 static int warned;
1101 if (!warned) {
1102 warned = 1;
1103 printk(KERN_INFO "%s uses obsolete (PF_INET,SOCK_PACKET)\n",
1104 current->comm);
1105 }
1106 family = PF_PACKET;
1107 }
1108
1109 err = security_socket_create(family, type, protocol, kern);
1110 if (err)
1111 return err;
1112
1113 /*
1114 * Allocate the socket and allow the family to set things up. if
1115 * the protocol is 0, the family is instructed to select an appropriate
1116 * default.
1117 */
1118 sock = sock_alloc();
1119 if (!sock) {
1120 if (net_ratelimit())
1121 printk(KERN_WARNING "socket: no more sockets\n");
1122 return -ENFILE; /* Not exactly a match, but its the
1123 closest posix thing */
1124 }
1125
1126 sock->type = type;
1127
1128 #if defined(CONFIG_KMOD)
1129 /* Attempt to load a protocol module if the find failed.
1130 *
1131 * 12/09/1996 Marcin: But! this makes REALLY only sense, if the user
1132 * requested real, full-featured networking support upon configuration.
1133 * Otherwise module support will break!
1134 */
1135 if (net_families[family] == NULL)
1136 request_module("net-pf-%d", family);
1137 #endif
1138
1139 rcu_read_lock();
1140 pf = rcu_dereference(net_families[family]);
1141 err = -EAFNOSUPPORT;
1142 if (!pf)
1143 goto out_release;
1144
1145 /*
1146 * We will call the ->create function, that possibly is in a loadable
1147 * module, so we have to bump that loadable module refcnt first.
1148 */
1149 if (!try_module_get(pf->owner))
1150 goto out_release;
1151
1152 /* Now protected by module ref count */
1153 rcu_read_unlock();
1154
1155 err = pf->create(net, sock, protocol);
1156 if (err <>ops->owner))
1164 goto out_module_busy;
1165
1166 /*
1167 * Now that we're done with the ->create function, the [loadable]
1168 * module can have its refcnt decremented
1169 */
1170 module_put(pf->owner);
1171 err = security_socket_post_create(sock, family, type, protocol, kern);
1172 if (err)
1173 goto out_sock_release;
1174 *res = sock;
1175
1176 return 0;
1177
1178 out_module_busy:
1179 err = -EAFNOSUPPORT;
1180 out_module_put:
1181 sock->ops = NULL;
1182 module_put(pf->owner);
1183 out_sock_release:
1184 sock_release(sock);
1185 return err;
1186
1187 out_release:
1188 rcu_read_unlock();
1189 goto out_sock_release;
1190 }




3.Write a program that, when run, prints out its own source code.

char*a="char*a=%c%s%c;
main()
{
printf(a,34,a,34);
}
";
main()
{
printf(a,34,a,34);
}

20090602のHW

1.Report on your progress on your project.
2.Estimate how long it would take to swap out an entire process on your machine.
a.How fast is your disk in megabytes/second, roughly?
[実行結果]
$ sudo hdparm -t /dev/sda1

/dev/sda1:
Timing buffered disk reads: 140 MB in 3.03 seconds = 46.19 MB/sec

b.Pick a process on your system (say, Word or Firefox). How big is it, in MB of memory?
[実行結果]
$ ps aux | grep firefox
cream 6571 10.9 8.3 350620 170416 ? Sl 13:26 14:41 /usr/lib/firefox-3.0.11/firefox
cream 13600 0.0 0.0 2816 788 pts/0 S+ 15:40 0:00 grep firefox

使用仮想メモリ
350620 kバイト
使用物理メモリ
170416 kバイト

c.Divide. How long will it take to write out the whole process, assuming that it can be written linearly at full disk bandwidth?
170.416/46.19 = 3.689 sec

3.Go back and rerun your memory copy experiments for sizes up to 100MB or so, and produce a graph with error bars and a linear fit. What is your Y intercept (the fixed, overhead cost) and your slope (the per-unit cost)? Tell me why you believe the linear fit does or does not represent the actual cost of the operation






4.Now run up to sizes much larger than your physical memory. What happens? Graph the output. (Note: this may take a long time to run!)
物理メモリが2Gなので3Gを指定して実行しました。
その結果、処理が遅くなったあと動かなくなりました。
しかし、物理メモリ以下の要領である1Gの前に動かなくなったため、理由がよく分かりません。
途中まで取れていた結果のグラフです。

これを見ると途中から既存のアプリケーションのswapを行っているため、理論値よりもかなり遅くなっている。

0526のＨｏｍｅｗｏｒｋ

1.Experimentally construct a rough memory map for an application on your operating system.

1. Write a program that prints out (in hexadecimal) the addresses of the following:
   1. main()
   2. a variable on the outermost stack frame (main()'s stack frame)
   3. a variable on the stack frame of a recursively-called function called to a depth of five times
   4. a statically-defined but uninitialized variable
   5. a statically-defined, initialized variable
   6. several large chunks of malloc()ed memory
   7. a library routine, such as strcpy()
   8. a system call wrapper, such as the one for write()

[プログラム]
1 #include
2 #include
3 #include
4 #include
5
6 void recursive_function();
7
8 static cnt = 5;
9
10 int main(int argc, char **argv)
11 {
12 static uninitial;
13 static initial=0;
14 int *mem, a;
15 mem = (int *)malloc(16);
16 char *src = "hello";
17 char *dst;
18
19 printf(" main() : %p\n", main);
20 printf(" argc : %p\n a: %p\n", &argc, &a);
21 printf(" recursive_function : %p\n", recursive_function);
22 printf(" uninitial : %p\n", &uninitial);
23 printf(" initial : %p\n", &initial);
24 printf(" malloc : %p\n", &mem);
25 printf(" strcpy : %p\n", strcpy(dst, src));
26 printf("system call wrapper : %p\n", fork);
27
28 }
29
30 void
31 recursive_function()
32 {
33 if (cnt < 0) {
34 return ;
35 }
36 cnt--;
37 recursive_function();
38 }
[実行結果]
main() : 0x8048414
argc : 0xbff2e450
a : 0xbff2e428
recursive_function : 0x804850d
uninitial : 0x8049808
initial : 0x8049804
malloc : 0x804a020
strcpy : 0xb7f73ff4
system call wrapper : 0x8048378

B. Take that information and draw a memory map for your OS. It should indicate which direction the stack and the heap grow in. An ASCII picture is okay, or you can use a drawing program of some sort if you wish.

1. How big is the distance between your stack and your heap?
2. Was your program compiled with static libraries or shared libraries?

1.メモリ番地を計算すると0xbf829a26の距離が有ります

2.strcpyは共有ライブラリで、他の関数(main, recursive)は静的ライブラリ（？）


2.
A.デバイスドライバ内で記述されているinterrupt coalescing
/* Get the coalescing parameters, and put them in the cvals
* structure. */
static int gfar_gcoalesce(struct net_device *dev, struct ethtool_coalesce *cvals)
{
struct gfar_private *priv = netdev_priv(dev);

if (!(priv->einfo->device_flags & FSL_GIANFAR_DEV_HAS_COALESCE))
return -EOPNOTSUPP;

if (NULL == priv->phydev)
return -ENODEV;

cvals->rx_coalesce_usecs = gfar_ticks2usecs(priv, priv->rxtime);
cvals->rx_max_coalesced_frames = priv->rxcount;

cvals->tx_coalesce_usecs = gfar_ticks2usecs(priv, priv->txtime);
cvals->tx_max_coalesced_frames = priv->txcount;

cvals->use_adaptive_rx_coalesce = 0;
cvals->use_adaptive_tx_coalesce = 0;

cvals->pkt_rate_low = 0;
cvals->rx_coalesce_usecs_low = 0;
cvals->rx_max_coalesced_frames_low = 0;
cvals->tx_coalesce_usecs_low = 0;
cvals->tx_max_coalesced_frames_low = 0;

/* When the packet rate is below pkt_rate_high but above
* pkt_rate_low (both measured in packets per second) the
* normal {rx,tx}_* coalescing parameters are used.
*/

/* When the packet rate is (measured in packets per second)
* is above pkt_rate_high, the {rx,tx}_*_high parameters are
* used.
*/
cvals->pkt_rate_high = 0;
cvals->rx_coalesce_usecs_high = 0;
cvals->rx_max_coalesced_frames_high = 0;
cvals->tx_coalesce_usecs_high = 0;
cvals->tx_max_coalesced_frames_high = 0;

/* How often to do adaptive coalescing packet rate sampling,
* measured in seconds. Must not be zero.
*/
cvals->rate_sample_interval = 0;

return 0;
}

/* Change the coalescing values.
* Both cvals->*_usecs and cvals->*_frames have to be > 0
* in order for coalescing to be active
*/
static int gfar_scoalesce(struct net_device *dev, struct ethtool_coalesce *cvals)
{
struct gfar_private *priv = netdev_priv(dev);

if (!(priv->einfo->device_flags & FSL_GIANFAR_DEV_HAS_COALESCE))
return -EOPNOTSUPP;

/* Set up rx coalescing */
if ((cvals->rx_coalesce_usecs == 0) ||
(cvals->rx_max_coalesced_frames == 0))
priv->rxcoalescing = 0;
else
priv->rxcoalescing = 1;

if (NULL == priv->phydev)
return -ENODEV;

/* Check the bounds of the values */
if (cvals->rx_coalesce_usecs > GFAR_MAX_COAL_USECS) {
pr_info("Coalescing is limited to %d microseconds\n",
GFAR_MAX_COAL_USECS);
return -EINVAL;
}

if (cvals->rx_max_coalesced_frames > GFAR_MAX_COAL_FRAMES) {
pr_info("Coalescing is limited to %d frames\n",
GFAR_MAX_COAL_FRAMES);
return -EINVAL;
}

priv->rxtime = gfar_usecs2ticks(priv, cvals->rx_coalesce_usecs);
priv->rxcount = cvals->rx_max_coalesced_frames;

/* Set up tx coalescing */
if ((cvals->tx_coalesce_usecs == 0) ||
(cvals->tx_max_coalesced_frames == 0))
priv->txcoalescing = 0;
else
priv->txcoalescing = 1;

/* Check the bounds of the values */
if (cvals->tx_coalesce_usecs > GFAR_MAX_COAL_USECS) {
pr_info("Coalescing is limited to %d microseconds\n",
GFAR_MAX_COAL_USECS);
return -EINVAL;
}

if (cvals->tx_max_coalesced_frames > GFAR_MAX_COAL_FRAMES) {
pr_info("Coalescing is limited to %d frames\n",
GFAR_MAX_COAL_FRAMES);
return -EINVAL;
}

priv->txtime = gfar_usecs2ticks(priv, cvals->tx_coalesce_usecs);
priv->txcount = cvals->tx_max_coalesced_frames;

if (priv->rxcoalescing)
gfar_write(&priv->regs->rxic,
mk_ic_value(priv->rxcount, priv->rxtime));
else
gfar_write(&priv->regs->rxic, 0);

if (priv->txcoalescing)
gfar_write(&priv->regs->txic,
mk_ic_value(priv->txcount, priv->txtime));
else
gfar_write(&priv->regs->txic, 0);

return 0;
}

B. HPのマシン2台、GbitのNICを持っている。またethtool -C eth0を実行出来る
ただまだcoalescingの設定変更は出来ていない。
Packetモニター用のThinkpadのPCのNICもGbitのNICを持っている。

C. milestone & schedule
6/2 マシンの性能確認＆coalescingのデバイスドライバでの実装を見る
6/9 interrupt coalescingの設定方法を見つける＆実験環境を整える
6/16 iperfへのCPU時間取得コードの実装＆packet間の時間の測定
6/23 CPU時間の精度を求める＆測定開始
6/30 coalescingを変更したときのCPU時間の測定とpacketロスの測定の終了(CPUに制限を与えた場合)
7/7 考察


3.
4 hours

20090519のHomework

1. Take last week's memory copy program, and modify it to fork() to a certain depth, then have each one of the processes time the copy of a certain amount of memory. Your program should take three arguments, the depth, the amount of memory to copy, and the number of times to copy the memory. Ideally, the amount of memory to copy should be large enough to require several seconds, but that's not practical, so have it repeat the copy some number of times. For example, fork five processes, malloc() ten megabytes each, and have the processes copy that memory one hundred times.

A.Run the program with a depth of one, and report how long it takes. Repeat this program twenty-five times and report the average and the individual times.
[プログラム]
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7
8 double gettimeofday_sec();
9 void usage();
10 void exec_fork_and_copy(int, int, int);
11 void copy_mem(int *, int *, int, int);
12
13 int
14 main(int argc, char* argv[])
15 {
16 int size = 0;
17 int count = 0;
18 int depth = 0;
19 int i = 0;
20 int pid = 0;
21 char ch;
22 pid_t start_process_id, stop_process_id;
23 double start_time, stop_time;
24
25 //
26 // check the number of argument
27 //
28 if (argc != 7) {
29 usage();
30 }
31
32 //
33 // check the option
34 //
35 while ((ch = getopt(argc, argv, "d:b:t:")) != -1) {
36 switch (ch) {
37 case 'd': // set depth
38 depth = atoi(optarg);
39 break;
40 case 'b': // set the amount of memory to copy
41 size = atoi(optarg)*1000000; // M
42 break;
43 case 't': // set the number of times to copy the memory
44 count = atoi(optarg);
45 break;
46 default:
47 fprintf(stderr, "unknown option\n");
48 usage();
49 }
50 }
51 start_process_id = getpid();
52
53 fprintf(stderr, "process_id: %d\ndepth: %d\nmemory size: %d\ntimes: %d\n", start_process_id, depth, size, count);
54 // exit(0);
55
56 // get start time
57 start_time = gettimeofday_sec();
58
59 //
60 // execution
61 //
62 exec_fork_and_copy(depth, size, count);
63
64
65 stop_process_id = getpid();
66 // print result
67 if (start_process_id == stop_process_id) {
68 // get stop time
69 stop_time = gettimeofday_sec();
70
71 printf("時間：%10.30f\n", stop_time - start_time);
72 }
73 }
74
75 void
76 exec_fork_and_copy(int depth, int size, int count)
77 {
78 int i;
79 int status;
80 pid_t pid=0;
81 int *src;
82 int *dst;
83
84 for (i = 0; i < pid =" fork())" src =" (int" dst =" (int" i="0;" 107="" 108="" 109="" 110="" free="" 111="" 112="" 113="" 114="" 115="" double="" 116="" 117="" 118="" struct="" timeval="" 119="" 120="" return="" tv_sec="" 121="" 122="" 123="" void="" 124="" 125="" 126="" 127="" depth="" size="" n="" 128="" 129="" 130="" mempro="" d="" 1="" b="" 10="" t="" 100=""> 1 : 時間：0.674799919128417968750000000000
2 : 時間：0.697927951812744140625000000000
3 : 時間：0.734071969985961914062500000000
4 : 時間：0.722994804382324218750000000000
5 : 時間：0.702398061752319335937500000000
6 : 時間：0.687880992889404296875000000000
7 : 時間：0.769035100936889648437500000000
8 : 時間：0.713932037353515625000000000000
9 : 時間：0.675138950347900390625000000000
10: 時間：0.667946100234985351562500000000
11: 時間：0.682356834411621093750000000000
12: 時間：0.728009939193725585937500000000
13: 時間：0.769045829772949218750000000000
14: 時間：0.690872907638549804687500000000
15: 時間：0.703732013702392578125000000000
16: 時間：0.657273054122924804687500000000
17: 時間：0.692090988159179687500000000000
18: 時間：0.687263965606689453125000000000
19: 時間：0.678195953369140625000000000000
20: 時間：0.692916870117187500000000000000
21: 時間：0.701704025268554687500000000000
22: 時間：0.674097061157226562500000000000
23: 時間：0.679100990295410156250000000000
24: 時間：0.705204010009765625000000000000
25: 時間：0.666203975677490234375000000000

平均： 0.6977

B.Now run the program with a depth of five. Again, repeat at least five times and report the average. Is the average higher than five times the depth one case? Why?
[実行]
./mempro -d 5 -b 10 -t 100

[実行結果]
1: 時間：3.502972126007080078125000000000
2: 時間：3.525238990783691406250000000000
3: 時間：3.549910068511962890625000000000
4: 時間：3.512364149093627929687500000000
5: 時間：3.534419059753417968750000000000

平均 : 3.5244

Aの5回の平均：3.4886
Bの方が時間が長いのは子プロセスをコピーする時間が必要なためであると考えられる

C. Plot the density function for the execution time. (You should have twenty-five data points here for copying a gigabyte of memory each, for the depth one and depth five cases.) Is there more variability in the depth five case?





2.Run one copy of your program at the normal priority, and at the same time a second copy at lower priority, e.g. by using nice. Does the first one completely monopolize the CPU until it is finished?
[プログラム（変更箇所のみ）]
86 if(fork() == 0) {
87 cpid = getpid();
88 fprintf(stderr,"priority 20 cpid : %d process start!\n", cpid);
89 nice(20);
90 copy_mem(src, dst, size, count);
91 fprintf(stderr, "pid : %d i: %d\n", cpid, i);
92 } else if (fork() == 0) {
93 cpid = getpid();
94 fprintf(stderr,"priority 10 cpid : %d process start!\n\n", cpid);
95 nice(10);
96 copy_mem(src, dst, size, count);
97 fprintf(stderr, "pid : %d i: %d\n", cpid, i);
98 }

[実行]
./mempro_pri -d 1 -b 10 -t 10
[実行結果]
depth: 1
memory size: 10000000
times: 100
priority 20 pid : 11652 process start!
priority 10 pid : 11653 process start!

pid : 11653　priority 10 stop!
pid : 11652 priority 20 stop!

3.Find and report the time quantum for your particular system.
Linuxのカーネルは優先度を用いてプロセスを時分割で実行する「O（1）スケジューラ」を採用している。
またCPUが割り当てられてプロセスが実行できる時間をクォンタムという。


・O（1）スケジューラ以外のスケジューラを使う方法
プログラムのmain()関数で
policy = SCHED_FIFO;
と書いてポリシーを変更する

セットできる値としては
SCHED_FIFO：First Input First Output
SCHED_RR：ラウンドロビン
SCHED_OTHER：優先度付き時分割
SCHED_BATCH：バッチ

これによってスケジューリングを変えることが出来る

4.Schedule a meeting with me (voice or in person) to discuss your project by the end of next week.
有田、中村で話し合った結果、
5/28 午前〜16:00
5/29 一日中
に面談を行うことが可能です。
よろしくお願いします。

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