2008-06-24

Process programming

2008/06/24



プロセスとは?

・プログラムの実行形

・独立したアドレス空間とPC, SP, レジスタのセット

・現在使用中のNWソケットや読み書き中のファイルなどのI/Oデバイスの利用状況のセット。

・シグナルにより別プロセスにメッセージを送ることが可能



↑中のプログラム自体は単純な動作の集合に過ぎない。

単純な動作の集合から、複雑な動作になっている。







------------ exec ----------------

execlでプロセスが変わる。

このため、execlのあとにプログラムを書いても意味がない。



p = path

execle = 環境変数を指定して呼び出す。



signal

interupt



signal

required #inlude



sigaction(SICINT, &act, 0);

// just registerd



act.sa_flags = 0;



important!

act.sa_handler = ouch(function);



while(1){

printf("Hello World!\n");

sleep(1);

// once output per sec



if you press Ctrl+c, the function ouch is called.



----------------------------



(ここから突如日本語が打てなくなった笑)

pipeline is 8 bit
register 16bit
cache 32 or 16 it


"ls > aaa"

output ls data into aaa
std output change dup2


opposite cat

"cat < aaa" exchange 0 of dup2 why dup2 is important? [understand fork and exec] know system call getpid, getppid getued, geteuid,...,and so on. ps command >confirm process information running

UID = process is appeared by who

The Who is the UID

each process have unique ID

PID = unique ID of each process


[flow of program]
1, init is called by OS(root)
forced to allocate memory space
almost Linux has this init program
In config file, there are a lot of programs about init.

2, init calls login program (UID = 0)
then user should input ID and password
ex tatsuo has 515 UID

3, seeing inputed ID, shell command is called
this UID is 515

if sshd has bug, root has possibility to be stolen.
*private address has more safety than global IP.


*the programs under init are supporting init program

GID is represented by 16bit integer.


getpid, getppid, getuid, getgid have no parameter.
you can fetch each ID using functions above.


fork
implement multi process eniviroment.
copy process image when it is called.
file descriptor is also copied.

usage
pid_t fork(void);
including sys/types.h and unistd.h is required!

recognize program itself is parent or child

ex
pid_t new_pid;
new_pie = fork(); // stack is already copied,

if(new_pid) == -1){
// error
}else if(new_pid == 0){
// execution as a child process
}else{
// execution as a general process
}

* if fork return -1, it shows error.
* which is occurred earlier depends on then environment.
* this above means debug work is very hard!

copy on right makes cost less

wait call
how do we synchronize child process and parent process?
while shell command is running, is shell sequential?

wait = wait for finishing of whose process.
waitpid = wait for finishing of certain process.

required #include

wait function has 3 parameters.

ex
waitpid(child, &stat_val, 0);p
// child contains child process.
// if child process is not finished yet, wait for finishing it!
// if you forget to command "&", you get 0 instead of &stat_val, then you hold or system down.
// so, it is difficult to find out where is bug.
// c++ has exception function, but c does not such a exception.
// if using language has the exception function, you should use it!
// if possible, you should not call system call, because it makes bugs lower.
* OS is still a little weak, so you pay careful attention to write arguments!
*


wait: wait for the status of child is available by family
exit: By child, configure status code, and then notice what parent has finished!


-----------------------------------------
kill
kill -kill 1234
you have killed process having PID of 1234
signal; waiting for pressing any of keyboard and something like that.

alarm(5)
signal is occurred per 5 seconds.

act.sa_handler = ding;

clock_t times(struct tms *buf)
examine how much time program spends.

int system(const char *command)
forced to call command.
In homework, you must not use the system command!

putenv, getenv
reconfigure your envinment variables.


inter communication between processes
pipe, socket


pipe
In shell command

ps -Af|grep hoge
you can move result anywhere.

int pipe(int file_descriptor[2]);
[0];for reading
[1];for writing

return
0: successful
-1; failure


Case1
Parent <----> child

parent --- file_pipes[1] | file_pipes[0] --- child
parent --- file_pipes[0] | file_pipes[1] --- child

some source codes
int file_pipes[2];

if(pipe(file_pipes) == 0){
fork_result = fork()l
...
}

close(file_pipes[1]); = pipe
data_o = read(file_pipes[0], buffer, BUFSIZ); = file_pipes[0] yu child
// reading data put into buffer

you do not have to close pipe, but it has possibility to occur bugs!
so, you should close it ASAP.


let's consider PS -As | grep hoge (== 1 | 0)
grep is fetching data from 2nd parameter to end parameter.
Using dup2,

dup2(1, p[1])
// fetching pipeline[1]

dup2(0, p[0]);
// fetching pipeline[0]

kind of
ls > aaa
cat < aaa ex program close(0); dup(p_id[0]); // equals to "dup2(0,p_id[0]);" close(p_fd[0] close(p_fd[1] pipe added name(FIFO) who call pipe system call? you should clarify that who and who inter communicate. From Command Line mkfifo < filename>

From System Call
int mkfifo(const char * filename, mode_t mode);

* this pipe is hardly used.

pipe system can be call if only two programs are related to family-child.


setjump/longjump
#include // required

jump_buf ma; // required and should be put in global

longjmp(ma, -1) // return value is -1


key = setjmp(ma) // key == -1




EX
func()
{
longjmp
}

main(){
sigaction
setjmp
printf("prompt = ")
read(ls, -1)
fork
wait
exec
}

important!
ls > a
cat <= a ls|grep - , cntl.c

fork| | | sigaction
exec| dup2 | pipe | setjmp/longjmp
wait| | |

/bin
/usr/bin


ex. ls -l
search files from upper to bottom in directory.
if you find out it, execute it,

2008-06-17

memo@file system, device driver etc.




2008/06/17
・ファイル名
ファイルを識別するためのString名からID名へ変換する
/a/b/c→101020



・ファイル内のポインタ
論理アドレスから物理アドレスへの変換

↑上記の二つをどうやって実現するのか?


・フ
ァイルシステム概要
ファイルの詰め込み方には異論の方法がある

例:
1. 頭からファイルを詰め込んでいく方法
→deflagmentationが起こるのであまり使われない。

2. 固定長のブロックに分けてファイルを詰め込んでいく方法、各ブロックは次のブロックを指すポインタを持っている
→しかしsequencialにしかアクセスできない!

3. 自分のファイルがどこに保存されているかを格納しているところがあり、それを参照して、ファイルの格納場所を知る(←これをディレクトリという。)
→これが最も一般的なやり方
cf.ページテーブル

☆directoryをどうやってストレージデバイスにおいていくか、が実現上大きな問題にある。よって、それぞれのファイルとdirectoryをどうやって実現していくかがこれから説明する。



・Unix file system
API概要(OSが実現するAPI)
fd = open((file,mode)
read/write(fd, buf, size)
…とか色々



・全体の概要
スーパーブロック→inode list→ファイルブロック:固定長に分けたブロック

i-node table:
i-node:各ファイルごとに一対一対応するデータ構造。
スーパーブロック:ファイル全体を管理するデータ構造
i-node list全体の数とかを管理する

ファイルへのアクセスはメモリへのアクセスと比べると時間がかかる。
一度オープンしたファイルに関しては一旦メモリ上にコピーされる。
ファイルデータ構造というのは、readすると順番にブロックが呼び出されていく。どこから呼び出されていくかはOSが知っている。

プロセスデータ構造:プロセスごとに存在し、ファイルデータ構造にある内容をファイルディスクリプタ内の情報に変換する?

つまり、ファイルディスクリプタの番号はプロセスごとに閉じている。

ストレージは非常に大きい。よって、メモリ上に持っていくことは出来ない。
しかし、一部のファイルに関してはメモリにコピーしていることがある。
ストレージデバイスの良く使うごく一部の部分がメモリ上にコピーする。



・i-nodeとブロックの関係
i-node内部構造:内部構造は固定長で、
"所有者、アクセス権、アクセスタイム、変更時間、10個のエントリ、3個のエントリ"
が含まれている
ファイルシステムは何年も使われて、安全が保障されてから人に使われる。
よって、開発から実用まで10年ぐらいのスパンがある。

10個のエントリ:それぞれが独立に10個のブロックを指している。
3個のエントリ:それぞれが独立に3個の間接ブロック(=中身はエントリ)を指していて、そのブロックはそれぞれまた別なブロックを指している。

一つのブロックには256個のエントリが入る。よって、
10K + 256*1K + 256*256*1K + 256*256*256*1K
よって、ファイルのサイズが大きくなればなるほど深い層までもぐりこまなければならないのでperformanceは低下する。

i-nodeの数だけ、ファイルが作られるので、
ファイルの上限はi-nodeの数に制限される。



・Unix filesystem(4)
ファイルデータ構造は、複数のプロセスから共有されることがある。

例:プロセスAがオープンしたファイルデータ構造はプロセスBからも共有される

forkしたときに、現在オープンしたファイルディスクリプタは共有される。
オフセット:現在書き込みしているところの次はどこに書き込むのか、という情報が格納されている。



・スーパーブロック
スーパーブロックはファイルシステム全体を管理するデータ構造。
一番最初に読み込まれる。
-ブロックサイズをどうするか?4K?1K?
-どのブロックが現在使われているか?

新しくブロックを割り当てる場合、空いているところをビットマップから判断し、割り当てる。

名前をどうやってi-nodeに変換するか?
i-nodeが分かったとき、その後どうやってファイルにアクセスするか。



・read/write
ファイルをオープンすると、今アクセスしようとしているi-nodeを認識する。
それをi-node tableのコピーする。
ファイルデータ構造にallocationして、
プロセスデータ構造からファイルデータ構造に書き込む。
ファイルデータ構造のoffsetを見て、i-nodeテーブルを見て、i-nodeの何バイト目を見るかを決める。
10Kより小さかった場合は、ブロックを発見。
10Kより大きかった場合は、間接ブロックを辿っていく


rooter i-node
i-node:3,5,7,19,17と書いてあるとする。

頭は"/"から始まる
"/" "usr"=3
. =自分
..=親のディレクトリ

"vmunix" = 10
→ファイルを直接アクセスしている。
ファイルのブロックが順番にアクセスされる。

usr = 3
usrと認識すると i-node 3を見る。
3は"."を指しているので、親のディレクトリに行く。

例:/usr/readmeをopenする
ディスクからi-node tableの必要なブロックを全部呼び出す。
readmeを探し、7が見つかったので、
i-node 7の指すファイルを全部呼び出して、
前から順々にアクセスしていく。

よって、
ファイル名から、
i-nodeの指すファイルを探して、
ファイルをopenする。



・ハードディスクが複数合った場合はどうするのか?
ディレクトリ+ブロックが入っている。
あるハードディスクのあるディレクトリを、他のハードディスクをマウントするようにする。
mount table
mntはディスクテーブルにある。
mntを見つけたら、ディスクBをアクセスし始める。
mnt=mount

ディレクトリ自体は一つのtree構造であることには変わらない。



・物理的なディスクの構造
ハードディスク上にファイルシステムを作る
ディスクは複数ある。
ディスクは同心円の円がたくさん入っていて、そこにデータがたくさん入っている。
その輪の中にデータを入れていく。
それぞれの輪の部分をトラックという。
トラックを固定長に分割した部分をセクタという。
各ディスクのことをシリンダという。

シリンダ->トラック->セクタ

アームで読み込む。アームは前後に動く。
ディスクが回っていて、アームと接触した部分を読み込む。
よって、読み込むまでの時間は、アームのところに読み込みたいセクタまでディスクを回してあげて、完了するまでの時間。
→読み込み時間はアームの前後に動く時間と、セクタを指定した位置に持っていくまでの時間に左右される。

よって、ハードディスクの読み込みは遅くなる。


・バッファキャッシュ
キャッシングとプロフェッチ。
prefetch:次に読み込むものが分かっている場合は、事前にフェッチしていくこと。
ファイル全体をメモリにコピーしていくことが多い。

使用例:ファイルは頭から順番にアクセスしていくことが多いことを利用する。
具体例:Unixは次のブロックを指していたら、その次のブロックがアクセスされる場合が多いので、事前にメモリ上に呼び出しておく。

タイムスタンプ:いつアクセスされていたか。
キャッシュの管理アルゴリズムは、タイムスタンプをつけてLRUで管理している。



・ディスクの書き出し
バッファキャッシュで変更する場合、30秒から1分待つ。これにより、同じバッファブロックに対して何度も何度も書き出すことを制限することが出来る。

30秒に一回変更されているブロックをディスクに書き出す。
ディレクトリやスーパーブロック, i-nodeの変更はすぐにディスクに書き出す。
→システムがファイルへ書き出す前にクラッシュしたとき、ファイルシステム全体が壊れる可能性がある。
→ファイルのデータ構造をいじくるときは、常にファイルシステムの一貫性を保てるようにする。



・ディスクスケジューリング
FIFOスケジューリングは行ったり来たりする。
メカニカル動く。
アームの動く速度は遅いので、アームの動く量を最小にしたい。
→C-SCANというアルゴリズムがある。

C-SCAN:
いくつかのタスクを溜めておいて、ソートして
頭から尾に向かって順番にアクセスしていく。
その後、アームを頭の位置に戻す。

他のもディスクスケジューリングアルゴリズムがある。
今は、もうちょっと頭のいいアルゴリズムも存在する。

☆ハードディスクのアクセスには物理メモリと違って、
トラックがどこにあるかによってアクセス時間が大幅に違う。

自分のアクセスしたいデータがトラックのどこにあるのかを認識して、
最小限のアームの動きでアクセスする必要がある。



・分散ファイルシステム
リモートにあるマシンに対して同じプログラムを使いたいときは
アクセス透過性と位置透過性を考える必要がある。

アクセス透過性:リモートファイルもローカルファイルも同一のAPIを用いてアクセス可能
位置透過性:ファイル名にマシン名が含まれていない。
→どこのマシンにあるかを気にせずアクセスできる。



・NFS
network file systemの略称。しかしnetwork file systemとは滅多に言わない。

☆プログラマーから見て、あたかも普通にディレクトリをアクセスできるかのようにすることが大切。
→OS空見れば、ネットワーク上の複雑な処理を隠蔽することが大事!



・I/Oの種類
プログラム⇔デバイスドライバ⇔デバイス

デバイスの種類はたくさんある!
デバイスドライバが出来るだけ隠蔽してあげることが大切。



・バスの種類
PCI
ISA
SCSI
…たくさん!



・デバイスドライバ
デバイス独自のプロトコルの使用にあわせて作り、出来るだけ簡略化し、隠蔽する・

デバイスドライバは、各デバイスのアクセスプロトコル(デバイスの制御手順)を実装する。

デバイスドライバはデバイスを自動的に発見し、どのようにアクセスするかを自動的にけっている。
cf:USBの挿入
USBを差し込む→OSが認識→
デバイスドライバがない場合:デバイスドライバをインストールする。
デバイスドライバがある場合:USBを読み込む

昔は数百行だったが、今は数千行必要になる。
→デバイスドライバを作る人はこれから増えるかもしれない。

☆重要なこと
デバイスとデバイスドライバのやり取りをどうするかを決めること。



・デバイスアクセスの方法
I/Oイベントの通知
-error通知、利用可能データ通知、状態通知
-ポーリング:CPUからデバイスに対して使用可能か調べる?
-割り込み



・データの転送
デバイスとCPUのデータ転送方法を決定する。
-read/write
-programmable I/O
-DMA:direct memory access:ある程度の長さのデータを一括して転送する



・I/O port
-メモリ空間と異なるI/O空間
-各デバイスはI/O空間上にポートを割り当てられる
-ポートをアクセスすることによりデバイスとメモリ間のデータ転送が行われる
-I/Oポートをアクセスするための特注名命令が必要
→x86の場合、in, out命令



・Memory mapped I/O
-デバイスの一部をメモリとしてみることが出来る。
-メモリアクセスとして実現されるが、アクセスコストが異なる。



・ポーリング
CPUからデバイスに対して以下のことを確認する。
-データの入力が可能となる
-データの出力が可能となる
-処理の終了
あるデータの書き出すが起きているときには、それが終わるまでは次の書き出しを禁止する。
ポーリングを使って、毎回毎回処理終わったかどうかを聞く。
例:
while(flagPort != READY);
mem = dataPort;

dataPort:どっかのレジスタ

イベントの発生などをポーリングで待つことはCPUの無駄遣い
他の処理の合間にポーリングをすることが可能だが、システム全体の構造がクリアではなくなる

よって、ポーリングを使用するときは、結果が分かるまでの時間が短い場合のみ。
20μsならよいが20nsでは無駄。



・割り込み interrupt
CPU→要求(I/O port, memory)→デバイス
CPU← 割り込み  ←デバイス
↑ポーリングによるCPUの無駄遣いを防ぐことが出来る

割り込みは、デバイスからCPUに対して何かを呼び出したいとき、
今実行しているプログラムを中断して割り込んだデバイスの処理をさせるときに使う。



・割り込みハンドラ
以下のような処理が割り込み処理に当たる
-新しく入力された
-エラー処理
-デバイスからの通知処理

番号ごとに違う番号を登録する

例:割り込みベクタ↓
IRQ0 = clock handler
IRQ1 = disk handler
IRQ2 = network handler
IRQ3 = trap handler: page fault, system call, bus error etc.

各デバイスはIRQの何番を用いるか知っている。

場合によっては、割り込みベクタを複数のデバイスで共有することが出来る。
→割り込み処理で貰ってきた値を評価して、どのデバイスの割り込みかを認識する。



・多重割り込み
割り込みが複数個ある。
割り込み処理が実行されたときに、違う割り込みが来た場合はどうするのか?

割り込みには優先度が付いている。
例:level2, level3, level4,...,level7
levelの値が高い方が優先して処理する。

デバイスによっては、あまり長い時間放置されると破綻するものもある。
例:network driverは連続的にパケットが送信されるので、
データが来たときにすぐ処理しなければならない。

・時間制約によって勝手に割り込んでくる処理がある。
割り込みの数が多いと、今実行されているプログラムは実行できなくなる。

☆未だに解決できていない課題
時間を測定する関数を使った場合、割り込み処理によって正確な値が測定できない。


割り込みハンドラを実行後レジスタを回復する必要がある。
例:
handler(){
save_register();
process_interrupt();
restore_register();
}

割り込みは割り込みようのスタックを用いる。
これにより、スタックがオーバーフローすることを避けている。



・割り込みのオーバーヘッド
割り込み処理のコストは結構大きい。ポーリングより大きいので、ポーリングを使った方が良いときも多い。

例:
web serverはデータが来る毎に割り込みが発生する。
昔は10MB/bpsだったので、そんなにCPUが早くなくても取りこぼさない。
今は10GB/bpsなので、パケット量が圧倒的に増えて、割り込みが毎回発生する。
最悪の場合、web serverが実行できずに割り込み処理しか実行されない。
→割り込みハンドラの呼ばれる頻度が高い。
10GB/bpsだと、CPUは有意義な計算を行うことが出来ない。

対処例:割り込みハンドラの呼ばれる頻度が高くなったら、ポーリングに切り替える。



・割り込みの禁止
システムコールの処理と割り込みハンドラ間の排他制御
cf.複数のスレッドを実行するときは排他制御する必要がある。

例:readやwriteがデータ構造をいじっているときは割り込みを禁止する。

例:
syscall()
{
割り込み禁止
排他リソースのアクセス
割り込み可能
}
注意:割り込みを禁止している時間はなるべく短くするように心がける。

・Direct Memory Access
各デバイスはメモリから直接データをやり取りする。
bufPort: buffer size
sizePort:送るべきデータのサイズ
cmdPort: WRITEスタート

CPUとは関係なく実行される



・サイクルスティーリングとは?
メモリとCPUを繋ぐバスがある
DMAデバイスはバスを使う。
→バスは共有されている。同時には使えない。
→DMAが動いているときはパイプラインが使えない
DMAはCPU上で動いているプログラムのパフォーマンスを低下させる可能性を持っている。
かつ、CPUとは無関係に動いているので、どのくらい低下するのか予想するのが難しい。


デバイスからDMAを使ってデータを物理メモリの呼び出されたとき、
キャッシュの中をクリアする必要がある。
→DMAをたくさん使うとパフォーマンスが低下する。



・物理空間か仮想空間か
デバイスがMMUを解さずメモリをアクセスする場合は、デバイスにバッファのアドレスを教えるときは物理メモリアドレスを教える必要がある。


CPUから見えるアドレスとデバイスから見えるアドレスは違うので、マッピングする必要がある。



・TLB管理
ページテーブルによる仮想アドレスと物理アドレスの変換オーバーヘッドを減少するためTLBが導入された。
☆割り込みを考えるとTLBもパフォーマンスを低下させる可能性を持っている。

TLBはコンテキストスイッチが起こるたびにクリアする必要がある。
ページテーブルの変更はTLBに影響を及ぼさない。

TLBの負ラッシュする必要があるときは以下の場合。
-I/Oデバイスが新しくマップかアンマップされたとき
-新しい仮想エリアが新しくマップされたか案マップされたとき
-プロセスのコンテキストスイッチが発生したとき



・ユーザから見たI/Oインターフェース
/dev/device0 10 1
↑このファイルをオープンするとメジャー番号(10)とマイナー番号(1)に変換する。
よって、オープンするときは、

fd = open("/dev/device", mode);
close(fd);
read/write(fd, buf, size);
ioctl(fd, cmd, arg);

何でもかんでもI/Oコマンドを定義していくと移植性が低下するので、I/Oコマンドの定義は最小限にした方が好ましい。



・/proc
特別なデバイス。各プロセスの色んな情報を取り出すことが出来る。

例:
/proc/1/fd/3 プロセス1のfd3の情報を取る。
/proc/1/mem プロセス1のメモリ
/proc/pci PCIに関する情報
/proc/modules カーネル内にロードされたモジュールの情報



・非同期I/O
readシステムコールはデータが来るまで待っている。
signalを使って非同期化する?

例:
{
signal(SIGIO,..&input_handler)..
fcntl(0, F_SETWON,..getpid());
oflag = fcntl(0, F_GETFL);
fcntl(0, f_SETFL, oflag | FASYNC);
}



・付録
PDFの"付録"にデバイスドライバのサンプルソースコードがあるので目を通しておく。

2008-06-14

Mini-research project "Revised"

It's soooooooooooooooooooo difficult for me to grasp the theory of analog modulation, but what I have studied at analog modulation is just about amplitude modulation, not including frequency modulation :(  gee. the next experiment is that. hahaha I have had enough!



----- Mini-research project "Revised?" -----
Mini-Research Title and Introduction

Investigating what program makes full use of CPU for improving programming skill of non-major computer science programmer [Revised]

Introduction
In 2008, we can easily make a program using computer because plenty of computer scientists have helped an improvement about computer. However, at the birth of the computer called ENIAC in 1945[1], no one was able to use computer without a computer scientist because the way of programming of it was only to wire by hand. This means that a programmer was not able to program without knowledge of computer architecture in those days. However, from 1960s to 1970s, plenty of programming language which were designed to be easier for human to understand were revised or born, which is called 3rd generation programming language[2]. Following that, from 1980s to 1990s, the ability of programming language had improved rapidly, which are 4th or 5th generation programming language[3][4]. For this reason, now even a person who does not know about computer architecture was able to program if the person knows just some programming language. As a result, in 2000s, the number of programmer has been increased, and in 2008, there are numerous programmers in the world.



However, in some business society, the number of programmer is fewer than the number of what most companies need, so the companies decide to hire a person who is not computer scientist as a programmer. As a result of this decision, the companies can produce a lot of big softwares. On the other hand, the execution speeds of software can sluggish even if using high-performance CPU, in other words, big software can run smoothly on only high-spec computer. This kind of problem is caused when programmers code the program by not thinking about CPU. Therefore, we need to improve all of programmers’ skill totally, so we should summarize and list up how to make full use of CPU for non-major computer science programmers.



In this paper, we will suggest ten commandments about how to code by making full use of CPU in each case of programming for the programmers. In particular, we will look at clock per cycle of CPU from running program to finish, and find out the good performance code with comparing each code. We hope programmers understand these commandments, and then urge to totally improve the quality of software in business society.

References
1. http://en.wikipedia.org/wiki/Computer
2. http://en.wikipedia.org/wiki/Third-generation_programming_language
3. http://en.wikipedia.org/wiki/Fourth-generation_programming_language
4. http://en.wikipedia.org/wiki/Fifth-generation_programming_language

2008-06-09

Mini-research project

I guessed a project and wrote this introduction below of the project, for understanding what good structure in introduction is, but..., well..., what a terrible project this is lol. this may have good structure, but this will not be logical.

------------------------------------
Mini-Research Title and Introduction

What program is kind?: Investigating the kind programming for computer architecture, using Internet website resources for making full use of CPU


Introduction

In 2008, we can easily program using computer because plenty of computer scientists have helped an improvement about computer. However, at the birth of the computer called ENIAC in 1946[1], no one was able to use computer without a computer scientist because the way of programming of it was only to wire by hand. This means that programmer was not able to program without knowledge of computer architecture in those days. However, from 1990s to 2008, the number of programming language had increased, and the capability of the personal computer also had been improved[2]. For this reason, even a person who does not know about computer architecture was able to program if the person knows just some programming language. As a result, in 2000s, the number of programmer has been increased, and in 2008, there numerous programmers in the world.

In Japan business society, the number of programmer is fewer than the number of what most companies need, so the companies decide to hire a person who is not computer scientist as a programmer. As a result of this decision, the companies can produce a lot of big software. On the other hand, the execution speeds of software can sluggish even if using high-performance CPU. This kind of problem is caused when programmers code the program by not thinking about CPU. Therefore, we need to clarify the role of the programmer in making full use of CPU, and summarizing and listing up it for non-major computer science programmers.

In this paper, we will suggest ten commandments about how to code by making full use of CPU in each case for the programmers. In particular, we will look at clock per cycle of CPU from running program to finish, and find out the good performance code with comparing each code. We hope programmers understand these commandments, and then urge to totally improve the quality of software in business society.

References
1. http://en.wikipedia.org/wiki/Computer
2. http://en.wikipedia.org/wiki/Software_engineer

2008-06-07

enumerater using PROgram in LOGic

That's close on two points!
First, I have handed in this report below, in time!
because this midnight is deadline.

Second, Tomorrow, I will participate in the party held by WRESS, where there will be gathered 300 people who can speak English for discussing! I heard team tables were already dicided, and the table I'm in gatherd good English speakers. How fun it seems! I will make full use of it!

----------
1. 問題設定
2. 考え方
3. 作成したプログラム
4. 実行結果
5. 考察
6. 感想



1. 問題設定
  三つの自然数の足し算の全ての場合を列挙する。

2. 考え方
  配布資料で示されている関数addは、第3引数が既に分かっているとき、バックトラックによって様々な解を捜し求めてくれる。しかしながら、第3引数が未知のときは、関数add内の再帰ループの結果が真となり、第1引数と第3引数のインクリメントが永遠と行われてしまう。
このような関数addの性質を踏まえつつ、関数addを用いて3項の加算演算を行う関数add3を使う。その後、関数add3を用いて三つの自然数の足し算の全ての場合を列挙する関数enum3を作成する。
このとき、関数addと同様の理由で、全ての変数を未知の状態で関数add3を呼び出してしまうと、再帰関数addでtrueの永久ループにはまってしまい、バックトラックが発生しなくなる。よって、常にバックトラックを発生させるため、まずは3項加算式の解である第4引数の値を決定させる。その後、関数add3を呼び出すことでバックトラックが起こり、三つの自然数の足し算の全ての場合を列挙する関数enum3が完成する。

3. 作成したプログラム
/* X + Y = Z */
add(0, Y, Y).
add(s(X), Y, s(Z)) :- add(X, Y, Z).

/* A + B + C = D */
add3(0, 0, Z, Z).
add3(0, s(X), Y, s(Z)):-
add3(0, X, Y, Z).
add3(s(A), B, C, s(D)):-
add3(A, B, C, D).

/* 3項加算演算で起こりうる全ての場合を列挙する */
enum3(A,B,C,D) :-
add(D,0,D), % 先にDの値を評価行う。
add3(A,B,C,D). % その後、AとBとCの評価を行う。

4. 実行結果
?- enum3(A,B,C,D).
A = 0,
B = 0,
C = 0,
D = 0 ;

A = 0,
B = 0,
C = s(0),
D = s(0) ;

A = 0,
B = s(0),
C = 0,
D = s(0) ;

A = s(0),
B = 0,
C = 0,
D = s(0) ;

A = 0,
B = 0,
C = s(s(0)),
D = s(s(0)) ;

A = 0,
B = s(0),
C = s(0),
D = s(s(0)) ;

A = 0,
B = s(s(0)),
C = 0,
D = s(s(0)) ;

A = s(0),
B = 0,
C = s(0),
D = s(s(0)) ;

A = s(0),
B = s(0),
C = 0,
D = s(s(0)) ;

A = s(s(0)),
B = 0,
C = 0,
D = s(s(0)) ;

5. 考察
  本項目では、バックトラックの理解を深めるため、prologで関数enum3を呼び出したとき、処理系の内部ではどのような振る舞いが行われているのかを考察したい。
  関数enum3が呼び出されたとき、最初に評価される式はadd(D,0,D)である。ここで、関数addの持つデータベースを見るとadd(0, Y, Y)と書かれていることがわかる。よって、このとき関数add3から関数addに渡される第2引数の値が0であることが分かっているので、add(0, Y, Y)より第3引数は0と判断する。結果、enum3の第4引数Dは0であると判断された。
その後、関数enum3の関数add3が呼び出される。このとき、これまでの結果から既にDの値は分かっているので、実際に関数add3に渡される引数はadd3(A, B, C, 0)となる。
  次に、関数add3の内部の振る舞いについて考える。関数add3ではデータベースとしてadd3(0, 0, Z, Z)を持っている。関数addのときと同じように、第4引数が0であることからD=C=0である判断される。
その後、add3(0, s(X), Y, s(Z)):- add(X,Y,Z).の評価を行う。関数addで使う引数のYとZは共に0であることが分かっているため、実際に渡される引数はadd(X, 0, 0)となり、X+0=0よりX=0という結果を得る。つまり関数enum3の第二引数Bが0である判断される。
最後に、add3(s(A), B, C, s(D)):- add3(A, B, C, D).の評価を行う。これまでの結果から、再帰的に呼び出す関数add3に渡される引数は、add3(A, 0, 0, 0)となる。そして、再び関数add3の先頭の式から評価が開始される。つまり、データベースadd3(0, 0, Z, Z)と、引き渡された引数(A, 0, 0, 0)の照合が行われる。このとき、4つの引数のうち3つがデータベースと一致していることから、Aに入る引数は0であると判断される。結果、関数enum3の出力する値は、”A=0, B=0, C=0. D=0”となる。
一巡目の解求まると、バックトラックによって、今まで通ってきた解を順々に戻っていく。結果、関数enum3で一番初めのadd(D,0,D)を呼び出したところまで戻る。そして、他の解を探すため、分岐点の違う分岐ルートを選ぶ。つまり、関数add内の分岐、

add(0, Y, Y).  (最初に通ったルート)
 add(s(X), Y, s(Z)) :- add(X, Y, Z). (←違う分岐ルート:今度はこっちを通る)

である。コレによりs(D)が行われる。つまりs(0)となり、再び関数addが引数(s(0), 0, s(0))を伴って呼び出される。addが呼び出されると、本考察冒頭と同様に、データベースとの照合が行われる。そして、バックトラックにより関数enum3に戻り、関数add3が引数(A, B, C, s(0))を伴って渡されて呼び出される。
その後、関数add3のデータベースより、第3引数=第4引数と判断され、D=C=s(0)と判断される。そして、この後も1順目と同様に、式を評価していく。
このようにして、関数enum3では自明の解を得るまで式を次々と評価していく。このため、”2.考え方”の部分でも述べたが、式を評価していく途中で自明の解が得られない再帰ループに入ってしまった場合、思ったとおりの振る舞いをしてくれなくなる。
これらのことから、今回の問題のような列挙を目的とした探索をして欲しい場合は、処理系が一つずつ解を導いてくれるようにprogrammingする必要があるといえる。本プログラムでは、これらのことを意識し、バックトラックが常に発生する仕組みを構築した。結果、本プログラムは仕様に沿う振る舞いをしてくれた。

6. 感想
PrologがどのようなStepで走っているのかを理解するのが難しく、理解するのにかなりの時間を使ってしまった。そのため、課題2の問題例で示されている他の問題や、オリジナルの問題を解くことが出来なかった。なので、今回解けなかった問題に対しては、自由課題として後日提出したい。

2008-06-05

Calculator with LP 2

I have finish the report! so next time, I'll study a backend of language processor!

but, now for a computational intelligence programming, namely "prolog"!
because its deadline is coming soon! lol



目次
1. 入力文字列の構文規則
2. 電卓を設計した過程
3. ソースプログラムの説明
3.1 字句解析
3.2 構文解析
3.3 意味解析
3.4 誤り処理
3.5 main関数
4. 実行例
5. 設計した電卓のソースプログラム



(!!CAUTAION!!:some indents were omitted)
1. 入力文字列の構文規則
以下に、今回設計した電卓プログラム(以下、本プログラム)の構文規則を示す。

expression = [ '-' | '+' ] term { ( '+' | '-' ) term }
term = primary { ( '*' | '/' | '%' ) primary }
primary = character | figure | '(' expression ')' | '[' expression ']'
character = ID [ '=' expression ]
figure = {number} [ '.' {number}]
number = 0|1|2|3|4|5|6|7|8|9
ID = 英文字(大文字、小文字含む)

ただし、ID = expression1 * expression2のような入力文字列が与えられた場合、ID = (expression1 * expression2)としてIDへの代入処理が行われる。
ID にexpression1だけを代入して、その結果とexpression2を計算させたい場合は、
( ID = expression1 ) * expression2 のように、括弧を使って明示的に示す必要がある。



2. 電卓を設計した過程
電卓を設計する上でまず始めに考えたことは、与えられた仕様を満たすように入力文字列の構文規則を設計することである。このとき構文規則は、後の具現化の作業が容易になるように、再帰降下法が適用できる形にした。こうして出来上がった構文規則が1.で示した構文規則である。
次に、具体的な字句解析の方法を考えると同時に、具現化の作業を行った。このとき、WL言語や教材ページの簡易電卓で使われている字句解析を参考にして、設計を行った。
その後、変数の登録・代入の設計方針と誤り処理の設計方針についてはひとまず置いておき、まずはここまでの仕様を具現化した。しかしながら、誤りが起こったときの処理で関数errorを呼び出して扱うことは明白だったので、誤りが構文規則以外の文字を読み取ったときには、ひとまず関数errorを呼び出して置くようにした。
代入と誤り処理以外の仕様をすべて満たす電卓が完成したら、次に代入の設計方針を固める作業を行った。代入の設計方針としては、英字列を読み取ったとき、代入文とともに呼び出される場合と、そうでない場合の2通りがあることに留意しながら設計を行った。このとき、代入文とともに呼び出される場合は、英字列と値の同期付けを行い、その結果をなんらかの方法で表に登録する必要がある。今回設計した電卓では、登録、または登録された英字列を読み出す方法として、ハッシュ法を採用した。そして、これらの設計方針を基にして、代入の具現化を行った。

最後に、誤り処理の設計を行った。しかしながら、誤り処理については具体的な設計アルゴリズムが思いつかなかったので、出来るだけjavaやCコンパイラの誤り処理に近づけるようにして設計する、という方針を採用した。具体的な設計方針としては、入力文字列のどこの部分がどのように間違えているのかを出来るだけ明確にして出力する、また、誤りが複数ある場合は、その誤りの数だけ指摘できる誤り処理がする、という設計方針を立てた。これらの設計方針に基づき、誤り処理の具現を行い、今回設計した電卓が完成した。



3. ソースプログラムの説明
本項では本プログラムのソースプログラムを解説する。具体的には、ソースプログラムを字句解析部、構文解析部、代入の処理部、誤りの処理部、そしてmain関数部の5つの部分に分けて、各部分について一つずつ解説を行っていく。

3.1 字句解析
本プログラムは、WL言語と同様に1次先読みの字句解析を行うようにしている。以下は、本プログラムで使用する1次先読みの字句解析プログラムの解説である。
字句解析を行うにあたり、まずは入力文字列を読み込む必要があるので、入力文字列を読み込み、読み込んだ文字列を配列charsに格納する関数get_line()を作成した。この関数では、入力文字列を関数getchar()を用いて、’\n’が押されるまでの間、入力文字を読み取り続けている。関数get_char()が’\n’を読み取ったとき、入力文字列が空行であればFalseを、一文字以上存在していればTrueを返している。これにより、与えられた仕様の”からの行を入力すると終了する”という部分の具現が容易になる。
次に、配列charsに格納された入力文字列を、呼び出される度に一字読み取っていく関数get_token()を作成した。具体的には、変数cpを入力文字列のポインタとして扱い、字句を読み取った後、変数cpをインクリメントしていき、一字ずつ入力文字列を読み取っている。
ただし、読み取った文字が以下のケースに該当し場合は、例外的に以下に示す処理を行う。

(条件:処理)
・ 空白スペース:空白スペース以外の文字が出現するまで次の文字を読み取り続ける。
・ 英字:英字以外の文字が出現するまで次の文字を読み取り続ける。また、読み取った文字列を一つの単語として配列strに格納する。

また、関数get_token()では、配列charsから一字読み取ると同時に、読み取った文字をカテゴリ別に分類する作業も行うようにしている。分類した結果は変数tokenに反映させている。このときの分類作業は、以下の仕様に則って行われる。

(カテゴリ名:カテゴライズされる文字)
1. Value:0から9の数字
2. Character:aからz、またはAからZ
3. Decimal:’.’
4. Lbracket:’{‘
5. Lpar:’(‘
6. Plus:’+’
7. Minus:’-’
8. Times:’*’
9. Divide:’/’
10. Modulo:’%’
11. Rpar:’)’
12. Rbracket:’}’
13. Equal:’=’
14. EOL:’\n’
15. Error:上記以外の文字、または記号

上記に示した各カテゴリは、enum宣言で列挙した。列挙する順番は、カテゴリ名の左に書かれている番号に準拠している。
本プログラムの字句解析では、読み取った英字列に対しての名前の同定は行わず、その英字列を配列strに一時的に保存するだけにとどめている。これは、次に読み取る字句によって、読み取った英字列に対して行う処理が変わるためである。よって、読み取った英字列に対しての名前の同定処理は、構文解析の部分で行うことにしている。
本プログラムの字句解析部は、これらの関数を用いて具現化されている。


3.2 構文解析
次に、字句解析で得た情報を基に構文解析をするプログラムについて解説する。構文解析プログラムは、1.で示した構文規則に再帰降下法を適用したプログラムとなっている。よって、構文規則より、関数expression(), term(), primary(), figure(), character()を生成し、これらの関数を再帰的に用いて構文解析を行っている。
関数expression(), term, primary()については、特にこだわった点は無く、構文規則に従い単純に再帰降下法を適用しただけである。一方で、関数figure(), character()については、読み取った文字列の数値化や名前の同定作業、変数の登録作業を行っている。
まずは、関数figure()について解説を行う。関数figure()が呼び出されるとき、構文規則より、変数tokenには必ずValueが入っていることになる。つまり、これから読み取る文字が、1つ以上の連続した数字列であることが保証されていることになる。よって、文字列の数値化を具現化する方法として、while文を使って読み取った文字が数字である限り、以下の関数を呼び出す方法を使った。

value= value*10+(chars[cp-1]-'0');
get_token();

一行目に書かれている文は、変数valueに10をかけて1の位を0にしたあと、読み取った文字番号から’0’の文字番号を引いた値をvalueに加算する、という文である。その後、関数get_token()を用いて次の文字を読み取る。これらの式により、入力された数字の文字列を十進整数定数化することが可能になる。
しかしながら、構文規則では数字列の直後に小数点が来ることを許している。つまり、入力された文字列が小数点を含んだ十進定数であっても、数値化できなくてはいけない。この仕様を具現化する手段としては、小数点後に続く数字の数をカウントし、文字列の数値化が終了した時点でカウントした数だけ変数valueを10で除算する、という方法を用いている。このとき、文字列を数値化する方法は十進整数定数を具現化する方法と同じ方法を用いている。また、十進整数定数化後に読み取った文字列が小数点でなければ、この処理は行われない。
これらの動作により、関数figure()は文字列の数値化を具現化している。


3.3 意味解析
次に、関数character()について解説する。関数characterには、大きく分けて二つの処理方法があり、条件文によって必ずどちらか一方の処理が実行される。一つ目の処理方法は、英字列の後に’=’が付属した場合に実行される。この処理では、英字列を一つの変数として扱い、’=’後に続く式の結果をその変数に格納している。その後、その変数をハッシュ法で撒布させ、該当するハッシュ表に関数registerKeyword()を用いて登録する。このとき、撒布後の衝突を防ぐため、ハッシュ表の各要素はリスト構造を持たせている。これにより、ハッシュ法による衝突が生じた場合でもリストを用いて変数を登録することが出来る。
もう一つの処理方法は、英字列の後に’=’が付属していない場合の処理方法である。この処理では、読み取った英字列を既にハッシュ表に登録されている変数として扱う。よって、まずはその英字列を関数FindKeyWord()を用いてハッシュ表から検索する。検索に失敗した場合は関数error()を呼び出し、成功した場合は関数popKeyValue()を用いてその英字列の持っている数値を取り出す。
これらの動作により、関数character()は、名前の同定と変数の登録を具現化している。

3.4 誤り処理
本項では、本プログラムの構文解析において、予期せぬ字句を読み取ってしまった場合の対処方法について解説する。
本プログラムでは、構文解析時に構文規則を満たさない字句を読み取ってしまった場合、関数error()を呼び出すことにしている。関数error()は3つの引数をもっており、それぞれ以下のような特徴を持っている。

(引数名:役割)
Char message[]:コンソール画面にmessageに格納されている文字列を出力する。
Int procedure:変数procedureより優先度の低い字句を読み飛ばす。
Int position:構文規則を満たしていない文字の場所を変数positionで示す。

上記に示したように各引数はそれぞれ、誤りを是正するために必要な情報を出来るだけ詳細に示す役割を持っている。以下に、各引数が関数error()のどのような振る舞いと関係があるのかを具体的に解説する。
配列messageでは、エラーの内容を出来るだけ詳細に教えてくれる役割を持っている。例えば、左括弧’(‘を事前に入力文字列から読み取っていたが、それらに対応する’)’が入力文字列に含まれていなかった場合は、引数の配列messageに”missing ‘(‘”を入れることで、画面にエラーの原因が出力することが出来る。

変数procedureは、入力文字列に誤りが複数あったとき、その誤りを出来る限り多く検出する役割を持っている。3.1の字句解析で、分類されるカテゴリはEnum宣言で列挙されることを示した。これを利用して、Enum宣言で列挙するカテゴリの順番を、出現する頻度や演算子同士の優先度を考慮して配置することで、次に来るべき字句を特定することが出来る。これにより、’+’や’*’などの演算子を使うべき部分で何らかの誤りがあった場合でも、Valueや括弧が出てくるまで入力文字列を読み飛ばして再び構文解析を開始することが出来る。つまり、変数procedureで適宜読み飛ばす字句を指定してあげることで、複数のerrorを一度に検出することが出来ることになる。
変数positionは、入力文字列のどこの文字がerrorの原因になったかを特定する役割を持っている。文字の場所を特定する方法として、入力文字列ポインタ用の変数cpを使っている。なぜなら、関数error()は構文解析中に呼び出され、かつ変数cpは常に次の文字を指しているので、chars[cp-1]の場所にある文字がerrorの発生した文字と一致するからである。しかしながら、3.1字句解析の解説で示したように、英字を読み取った場合は例外的な処理を行っているため、errorの発生する場所が常にcp-1になるとは限らない。よって、この場合に限っては、現在cpの指している位置によって変数positionの値を変更し、変数positionの値が常に英字列の最後尾を指すように設計した。
この関数error()を用いて、本プログラムでは誤りの原因の特定を行っている。


3.5 main関数
最後に、本プログラムのmain関数について解説する。main関数では、まず入力文字列を格納する配列charsの初期化を行い、その後、関数get_line()を呼び出している。3.1の字句解析で解説したように、関数get_line()は空行が入力されたかどうかの結果を返すことにしている。これを利用して、while文の条件式を”while(get_line() != FALSE)”とすることで、空行が入力されたときに終了するプログラムにすることできる。
次に、while文の内側で実行される処理を解説する。関数get_line()で何らかの入力文字列を読み取ったら、関数get_token()を呼び出して字句解析を一度だけ行う。これは一字先読みのルールを遵守するためである。その後、構文解析プログラムを用いて入力文字列の計算を行い、その結果を変数resultに格納する。その後、構文解析中にerrorが発生していなければresultの内容を出力し、errorが1個以上発生していればerror発生したことを画面に出力している。しかしながら、誤り処理の関数error()も完璧に隙が無いわけではない。このため、誤りを検知出来なかった場合の例外も想定して、誤り検出に失敗したときは”unexpected error”を画面に出力するようにしている。その後、配列charsを再度初期化して、再びwhile文の先頭に戻る。
While文を抜けたら、ハッシュ法を使用する際に確保したメモリを解放し、プログラムを終了させる。



4. 実行例
yohei@YOHEI-note ~/wl/calc
$ gcc calc.c -o calc
yohei@YOHEI-note ~/wl/calc
$ ./calc

----- 小数点、各演算子、括弧、代入、終了の確認 -----
# +2-1
>> 1.000000

# -2-1
>> -3.000000

# 2+5*10
>> 52.000000

# 2*5+10
>> 20.000000

# 2*(5+10)
>> 30.000000

# 3/2
>> 1.500000

# 5.5/2.2
>> 2.500000

# [5.5/2.2]
>> 2.000000

# [5/(1+1)]
>> 2.000000

# 2/1+6%3
>> 2.000000

# 4.9%0.3
>> 0.100000

# two=2
two holds 2.000000
>> 2.000000

# five=5
five holds 5.000000
>> 5.000000

# ten=10
ten holds 10.000000
>> 10.000000

# hundred=100
hundred holds 100.000000
>> 100.000000

# -(ten+five/two)*two*hundred
>> -2500.000000

#
shut down this program...
yohei@YOHEI-note ~/wl/calc
$


----- 誤り処理 -----
# 1+ 2++ 4
error: incorrect position of symbol.
1+ 2++ 4
^
1 error was found.

# (1+3*4
error: missing ')'
(1+3*4
^
1 error was found.

# 1++[2*3**1
error: incorrect position of symbol.
1++[2*3**1
^
error: incorrect position of symbol.
1++[2*3**1
^
error: missing ']'
1++[2*3**1
^
3 errors were found.

# two+five*second+ten
error: not registered word is used.
two+five*second+ten
^
1 error was found.

# 1.3.4.5.6
unexpected error



5. 設計した電卓のソースプログラム
* see the following page.
https://github.com/yasulab/calculator-with-lp

2008-06-03

calculator with LP

I finally have seen the goal of this programming!, namely making a calculator program using knowledge of language processor I have studied.
However, this program has still a lot of errors, so I will brush up tomorrow.
This program is a calculator which can run along this specification below.

1. can use operands: +, -, *, /, %
2. can use Gauss's integer using branckets
3. can change priority of operation using parenthsis
4. can assign value to a valuable structured by alphabets


The specification is implemented by this syntax rule below.

expression = ['-'] term {('+'|'-') term }
term = primary {('*'|'/'|'%') primary }
primary = character | figure | '(' expression ')' | '[' expression ']'
character = ID | ID '=' expression
figure = {number} ['.' {number}]
number = 0|1|2|3|4|5|6|7|8|9
ID = a|b|...|y|z|A|B|...|Y|Z


Finally, I have implemented it so far, as this draft program below.
I feel I will be able to finish it including report!

* To see the source of "calculator.c", please visit the following page.
https://github.com/yasulab/calculator-with-lp