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:有田、中村