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

Revised project proposals

テーマ： "interrupt coalescing"という最適化を行うことで、実際にどのくらいTCPに割り当てられるCPUの処理が減少するのかを測定する。

測定すること:CPUのパフォーマンスとCPUがパケット処理に割り当てられる時間

測定方法:topコマンドを用いてCPUのパフォーマンスを測る。また、10秒間TCPストリーム又はping pongパケットを送信し、受信側のパケット処理を行うプロセスで時間を計り、CPUが10秒間にどのくらいパケット受信処理に割り当てられたかを比較する。

このプロジェクトから学べること：Linuxカーネルにおけるパケット処理、割り込み処理

スケジュール:

• Final approval of projects, implementation begins: May 26
• Weekly reviews begin: June 2
• Implemention finishes: June 15
• Mid-term progress review, evaluation begins: June 16
• Final evaluation of projects (face-to-face): July 14-23

20090428のHomeWork

1. This week we have talked about processes. Write a program to call fork() repeatedly. Eventually, the call will fail in one of the children. When it does, print out the depth of the process tree: how many times have you succeeded in calling fork()? What was the reason for the failure (use perror())?

[実行結果]
fork error:: Resource temporarily unavailable
final i is 15986


2. Now modify that program to collect timing information for a given number of processes, giving the number of processes as an argument to the program (no argument should do the same as above, run until the fork fails). How long does it take to create and delete a thousand processes? Two thousand?

[1000の実行結果]
i is 1000
時間：0.154197931289672851562500000000

[2000の実行結果]
i is 2000
時間：0.278687000274658203125000000000


3.
a. Find the Linux kernel code for fork() and post it on your blog. If your machine is Linux, you may want to learn where the source code is stored on your machine (you may have to install it); if you are not using Linux, you may use one of the browsable Linux kernel source archives on the web (there are several; pick one).

[ソース]
long do_fork(unsigned long clone_flags,
unsigned long stack_start,
struct pt_regs *regs,
unsigned long stack_size,
int __user *parent_tidptr,
int __user *child_tidptr)
{
struct task_struct *p;
int trace = 0;
long nr;

if (unlikely(current->ptrace)) {
trace = fork_traceflag (clone_flags);
if (trace)
clone_flags |= CLONE_PTRACE;
}

p = copy_process(clone_flags, stack_start, regs, stack_size,
child_tidptr, NULL);
/*
* Do this prior waking up the new thread - the thread pointer
* might get invalid after that point, if the thread exits quickly.
*/
if (!IS_ERR(p)) {
struct completion vfork;

/*
* this is enough to call pid_nr_ns here, but this if
* improves optimisation of regular fork()
*/
nr = (clone_flags & CLONE_NEWPID) ?
task_pid_nr_ns(p, current->nsproxy->pid_ns) :
task_pid_vnr(p);
if (clone_flags & CLONE_PARENT_SETTID)
put_user(nr, parent_tidptr);

if (clone_flags & CLONE_VFORK) {
p->vfork_done = &vfork;
init_completion(&vfork);
}

if ((p->ptrace & PT_PTRACED) || (clone_flags & CLONE_STOPPED)) {
/*
* We'll start up with an immediate SIGSTOP.
*/
sigaddset(&p->pending.signal, SIGSTOP);
set_tsk_thread_flag(p, TIF_SIGPENDING);
}

if (!(clone_flags & CLONE_STOPPED))
wake_up_new_task(p, clone_flags);
else
p->state = TASK_STOPPED;

if (unlikely (trace)) {
current->ptrace_message = nr;
ptrace_notify ((trace << 8) | SIGTRAP);
}

if (clone_flags & CLONE_VFORK) {
freezer_do_not_count();
wait_for_completion(&vfork);
freezer_count();
if (unlikely (current->ptrace & PT_TRACE_VFORK_DONE)) {
current->ptrace_message = nr;
ptrace_notify ((PTRACE_EVENT_VFORK_DONE << 8) | SIGTRAP);
}
}
} else {
nr = PTR_ERR(p);
}
return nr;
}


b. Find the definition of the process or task structure from another operating system, either in a book or online. Post it on your blog. Over the next few weeks, we will compare this structure to Linux. You can find the definition for BSD, Windows, Symbian, NACHOS, Minix, or any other OS of your choice.

[FreeBSD 8-CURRENT]

/sys/proc.h

  /*
   * Process structure.
   */
  struct proc {
          LIST_ENTRY(proc) p_list;        /* (d) List of all processes. */
          TAILQ_HEAD(, thread) p_threads; /* (c) all threads. */
          struct mtx      p_slock;        /* process spin lock */
          struct ucred    *p_ucred;       /* (c) Process owner's identity. */
          struct filedesc *p_fd;          /* (b) Open files. */
          struct filedesc_to_leader *p_fdtol; /* (b) Tracking node */
          struct pstats   *p_stats;       /* (b) Accounting/statistics (CPU). */
          struct plimit   *p_limit;       /* (c) Process limits. */
          struct callout  p_limco;        /* (c) Limit callout handle */
          struct sigacts  *p_sigacts;     /* (x) Signal actions, state (CPU). */
 
          /*
           * The following don't make too much sense.
           * See the td_ or ke_ versions of the same flags.
           */
          int             p_flag;         /* (c) P_* flags. */
          enum {
                  PRS_NEW = 0,            /* In creation */
                  PRS_NORMAL,             /* threads can be run. */
                  PRS_ZOMBIE
          } p_state;                      /* (j/c) S* process status. */
          pid_t           p_pid;          /* (b) Process identifier. */
          LIST_ENTRY(proc) p_hash;        /* (d) Hash chain. */
          LIST_ENTRY(proc) p_pglist;      /* (g + e) List of processes in pgrp. */
          struct proc     *p_pptr;        /* (c + e) Pointer to parent process. */
          LIST_ENTRY(proc) p_sibling;     /* (e) List of sibling processes. */
          LIST_HEAD(, proc) p_children;   /* (e) Pointer to list of children. */
          struct mtx      p_mtx;          /* (n) Lock for this struct. */
          struct ksiginfo *p_ksi; /* Locked by parent proc lock */
          sigqueue_t      p_sigqueue;     /* (c) Sigs not delivered to a td. */
  #define p_siglist       p_sigqueue.sq_signals
 
  /* The following fields are all zeroed upon creation in fork. */
  #define p_startzero     p_oppid
          pid_t           p_oppid;        /* (c + e) Save ppid in ptrace. XXX */
          struct vmspace  *p_vmspace;     /* (b) Address space. */
          u_int           p_swtick;       /* (c) Tick when swapped in or out. */
          struct itimerval p_realtimer;   /* (c) Alarm timer. */
          struct rusage   p_ru;           /* (a) Exit information. */
          struct rusage_ext p_rux;        /* (cj) Internal resource usage. */
          struct rusage_ext p_crux;       /* (c) Internal child resource usage. */
          int             p_profthreads;  /* (c) Num threads in addupc_task. */
          volatile int    p_exitthreads;  /* (j) Number of threads exiting */
          int             p_traceflag;    /* (o) Kernel trace points. */
          struct vnode    *p_tracevp;     /* (c + o) Trace to vnode. */
          struct ucred    *p_tracecred;   /* (o) Credentials to trace with. */
          struct vnode    *p_textvp;      /* (b) Vnode of executable. */
          u_int           p_lock;         /* (c) Proclock (prevent swap) count. */
          struct sigiolst p_sigiolst;     /* (c) List of sigio sources. */
          int             p_sigparent;    /* (c) Signal to parent on exit. */
          int             p_sig;          /* (n) For core dump/debugger XXX. */
          u_long          p_code;         /* (n) For core dump/debugger XXX. */
          u_int           p_stops;        /* (c) Stop event bitmask. */
          u_int           p_stype;        /* (c) Stop event type. */
          char            p_step;         /* (c) Process is stopped. */
          u_char          p_pfsflags;     /* (c) Procfs flags. */
          struct nlminfo  *p_nlminfo;     /* (?) Only used by/for lockd. */
          struct kaioinfo *p_aioinfo;     /* (c) ASYNC I/O info. */
          struct thread   *p_singlethread;/* (c + j) If single threading this is it */
          int             p_suspcount;    /* (j) Num threads in suspended mode. */
          struct thread   *p_xthread;     /* (c) Trap thread */
          int             p_boundary_count;/* (c) Num threads at user boundary */
          int             p_pendingcnt;   /* how many signals are pending */
          struct itimers  *p_itimers;     /* (c) POSIX interval timers. */
  /* End area that is zeroed on creation. */
  #define p_endzero       p_magic
 
  /* The following fields are all copied upon creation in fork. */
  #define p_startcopy     p_endzero
          u_int           p_magic;        /* (b) Magic number. */
          int             p_osrel;        /* (x) osreldate for the
                                                 binary (from ELF note, if any) */
          char            p_comm[MAXCOMLEN + 1];  /* (b) Process name. */
          struct pgrp     *p_pgrp;        /* (c + e) Pointer to process group. */
          struct sysentvec *p_sysent;     /* (b) Syscall dispatch info. */
          struct pargs    *p_args;        /* (c) Process arguments. */
          rlim_t          p_cpulimit;     /* (c) Current CPU limit in seconds. */
          signed char     p_nice;         /* (c) Process "nice" value. */
          int             p_fibnum;       /* in this routing domain XXX MRT */
  /* End area that is copied on creation. */
  #define p_endcopy       p_xstat
 
          u_short         p_xstat;        /* (c) Exit status; also stop sig. */
          struct knlist   p_klist;        /* (c) Knotes attached to this proc. */
          int             p_numthreads;   /* (c) Number of threads. */
          struct mdproc   p_md;           /* Any machine-dependent fields. */
          struct callout  p_itcallout;    /* (h + c) Interval timer callout. */
          u_short         p_acflag;       /* (c) Accounting flags. */
          struct proc     *p_peers;       /* (r) */
          struct proc     *p_leader;      /* (b) */
          void            *p_emuldata;    /* (c) Emulator state data. */
          struct label    *p_label;       /* (*) Proc (not subject) MAC label. */
          struct p_sched  *p_sched;       /* (*) Scheduler-specific data. */
          STAILQ_HEAD(, ktr_request)      p_ktr;  /* (o) KTR event queue. */
          LIST_HEAD(, mqueue_notifier)    p_mqnotifier; /* (c) mqueue notifiers.*/
          struct kdtrace_proc     *p_dtrace; /* (*) DTrace-specific data. */
          struct cv       p_pwait;        /* (*) wait cv for exit/exec */
  };
 
  #define p_session       p_pgrp->pg_session
  #define p_pgid          p_pgrp->pg_id
 
  #define NOCPU   0xff            /* For when we aren't on a CPU. */
 
  #define PROC_SLOCK(p)   mtx_lock_spin(&(p)->p_slock)
  #define PROC_SUNLOCK(p) mtx_unlock_spin(&(p)->p_slock)
  #define PROC_SLOCK_ASSERT(p, type)      mtx_assert(&(p)->p_slock, (type))

4. Determine how many processes have been created on your computer
since the last time it was booted.  Describe any caveats on your knowledge.

26531

Term Project Proposal

テーマ：TCPネットワークパフォーマンスの比較と考察
・OS毎のTCPネットワーキングのパフォーマンスを測定する
・TCPの入力から出力までの時間を測定を行う
・Linuxのいくつかのディストリビューションと、FreeBSDなどを比較測定する

チームでやります。

team:有田、中村

20090421のhomework

1. This week we have talked about system calls. Take your "Hello, world" program from last week and produce the assembler output from the compiler. Post the assembler file on your blog.
・the assembler file
1 .file "hello.c"
2 .section .rodata
3 .LC0:
4 .string "Hello, World!\n"
5 .text
6 .p2align 2,,3
7 .globl main
8 .type main, @function
9 main:
10 pushl %ebp
11 movl %esp, %ebp
12 subl $8, %esp
13 andl $-16, %esp
14 movl $0, %eax
15 addl $15, %eax
16 addl $15, %eax
17 shrl $4, %eax
18 sall $4, %eax
19 subl %eax, %esp
20 subl $12, %esp
21 pushl $.LC0
22 call printf
23 addl $16, %esp
24 movl $0, %eax
25 leave
26 ret
27 .size main, .-main
28 .ident "GCC: (GNU) 3.4.6 [FreeBSD] 20060305"

a. "printf" is the instruction that calls the string output function.
it is a library function.
printf はソフト割り込みをかけていないため
b. pushl $.LC0. 1個

c. "call printf"

2.Unfortunately, even "Hello, world" is a little bit complicated. Take the following even shorter program and repeat the above exercise.

1 .file "123.c"
2 .section .rodata
3 .LC0:
4 .string "123"
5 .text
6 .p2align 2,,3
7 .globl main
8 .type main, @function
9 main:
10 pushl %ebp
11 movl %esp, %ebp
12 subl $8, %esp
13 andl $-16, %esp
14 movl $0, %eax
15 addl $15, %eax
16 addl $15, %eax
17 shrl $4, %eax
18 sall $4, %eax
19 subl %eax, %esp
20 movl $.LC0, -4(%ebp)
21 subl $4, %esp
22 pushl $3
23 pushl -4(%ebp)
24 pushl $1
25 call write
26 addl $16, %esp
27 movl $0, %eax
28 leave
29 ret
30 .size main, .-main
31 .ident "GCC: (GNU) 3.4.6 [FreeBSD] 20060305"

a. "write". it is a system call.
b. 3個

3.Find a list of all of the system calls on the OS of your choice, and post it (or a link) on your blog. How many are there?

319個
http://d.hatena.ne.jp/toshi_hirasawa/20081105/1225885030

4.How long did it take you to complete this homework?

for 1 hour.

System Software Home work

20090414の宿題

1. 送りました。

2.Demonstrate that you have a working compiler setup where you will be able to write programs for class. Capture the output of the compilation and execution of a simple program (such as "Hello, world") and post it on your blog. Include the amount of time it took you to complete this exercise.

> vi 20090414.c

1 #include
2
3 int main()
4 {
5 printf("Hello, World!\n");
6 return 0;
7 }

> gcc 20090414.c -o 20090414
> ./20090414
Hello, World!

3.Read the paper above (Levin) and post your notes about the papers on your blog. (It is not necessary to write up notes about the readings from the textbook.)　

「An Evaluation of the Ninth SOSP Submissions -or- How (and How not) to Write a Good Systems Paper」

　僕の卒論は、実際に運用されることを想定したシステムであり、この分の中ではリアルシステムにあたるものであるという認識をもって読みました。

　論文の評価基準をおさっぱに箇条書きすると
・新しいアイデアか
・新しいアイデアが簡潔に述べられているか
・解決した問題は何か
・既存研究との違い
・関連研究
・実際に実装した論文か
・論文から学んだことは何か
・論文を読むことで学べることは何か
・前提は何か
・文法・語彙は正しいか
という事を評価基準として意識するようにと書いてありました。

　新しいアイデアであるか、解決した問題点は何か、既存研究との違いは何か、は論文を書く上で非常に重要なものであるという認識は誰もが持っていると思います。しかし、関連研究については軽く考えてしまっている場合もあると思います。おそらく著者は限られたページ数の中で自分の研究を出来るだけ詳しく書きたいでしょう。そのため、関連研究などは短めに書いてしまうことも多いと思います。しかし、読み手は関連研究という比較対象がなければ、論文で述べられている研究の位置づけがはっきり見えてこなくなります。関連研究を詳しく述べることではなく、自分の研究との違いを述べることが重要だと思います。

　また、論文を書くときには、読み手がその論文から何かを学べるものでなければならないというのも、重要なことだと思います。事実、僕は卒業研究に手をつける前に、自分の研究に近い分野の論文を読むことで、必要な知識を得ていました。論文を書く際には、自分が陥ってしまったミスや、重要になる基本的な事項、将来それがどのように発展していくのかをはっきりと書くことが重要であり、論文を書いた自分自身や論文の読み手が学ぶものが多かったと感じることができる論文を書くという意識が大切だと思いました。


4.Start reading the Lampson paper; for non-native English speakers, it is apparently a long paper, so I will give you two weeks.
Lampson

5.If you have additional thoughts about the above discussion of programming experience, please email me or post them on your blog.

6.What are the following hexadecimal numbers, in binary二進法 and in decimal?

1. 0x64 = 0b1100100 : 100
   
2. 0x1000= 0b1000000000000 : 4096
   
3. 0x100　= 0b100000000 : 256
   
4. 0x400 = 0b10000000000 : 1024
   
5. 0x1049 = 0b1000000001101 : 4109
   

7.Define the words "pointer" and "memory address".
・"pointer":ある関数や変数がなんらかの論理的位置情報でｱｸｾｽできるとき､その位置を表現する変数
・"memory address"：コンピュータにおいてCPUやそのほかのハードウェアがデータの書き込み、読みだす時のメモリ上の位置を表す識別子