ホーム » 2024 (ページ 6)

年別アーカイブ: 2024

2025年5月
 123
45678910
11121314151617
18192021222324
25262728293031

検索・リンク

スタックと待ち行列

前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。

計算処理中に一時的なデータの保存として、スタック(stack)待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。

スタック

配列を用いたスタック

一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。

import java.util.*;

public class Main {
    static final int STACK_SIZE = 10 ;
    static int[] stack = new int[ STACK_SIZE ] ;
    static int   sp    = 0 ;
    static void push( int x ) {
        stack[ sp++ ] = x ;
    }
    static int pop() {
        return stack[ --sp ] ;
    }
    public static void main(String[] args) throws Exception {
        push( 11 ) ;
        push( 22 ) ;
        push( 33 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}

配列を使った Stack をオブジェクト指向で記述するなら、以下のように書ける。

import java.util.*;

class Stack {
    static final int STACK_SIZE = 10 ;
    int[] array ;
    int   sp ;
    Stack() {
        this.array = new int[ STACK_SIZE ] ;
        this.sp    = 0 ;
    }
    void push( int x ) {
        array[ sp++ ] = x ;
    }
    int pop() {
        return array[ --sp ] ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        Stack stack = new Stack() ;
        stack.push( 11 ) ;
        stack.push( 22 ) ;
        stack.push( 33 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

C言語で書いた場合

#define STACK_SIZE 32
int stack[ STACK_SIZE ] ;
int sp = 0 ;

void push( int x ) { // データをスタックの一番上に積む
    stack[ sp++ ] = x ;
}
int pop() { // スタックの一番うえのデータを取り出す
    return stack[ --sp ] ;
}
void main() {
    push( 1 ) ; push( 2 ) ; push( 3 ) ;
    printf( "%d\n" , pop() ) ; // 3
    printf( "%d\n" , pop() ) ; // 2
    printf( "%d\n" , pop() ) ; // 1
}

++,–の前置型と後置型の違い

// 後置インクリメント演算子
int i = 100 ;
printf( "%d" , i++ ) ;
// これは、
printf( "%d" , i ) ;
i++ ;
// と同じ。100が表示された後、101になる。

// 前置インクリメント演算子
int i = 100 ;
printf( "%d" , ++i ) ;
//   これは、
i++ ;
printf( "%d" , i ) ;
// と同じ。101になった後、101を表示。

リスト構造を用いたスタック

しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
}

public class Main {
    static ListNode stack = null ;
    static void push( int x ) {
        stack = new ListNode( x , stack ) ;
    }
    static int pop() {
        int ans = stack.data ;
        stack = stack.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        push( 1 ) ;
        push( 2 ) ;
        push( 3 ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
        System.out.println( pop() ) ;
    }
}
struct List* stack = NULL ;

void push( int x ) { // リスト先頭に挿入
    stack = cons( x , stack ) ;
}
int pop() { // リスト先頭を取り出す
    int ans = stack->data ;
    struct List* d = stack ;
    stack = stack->next ;      // データ 0 件で pop() した場合のエラー対策は省略
    free( d ) ;
    return ans ;
}

オブジェクト指向っぽく書くならば、下記のようになるだろう。初期状態で stack = null にしておくと、stack.push() ができないので、stack の先頭には、ダミーデータを入れるようにプログラムを書くと以下のようになるだろう。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    ListNode() {   // stack初期化用のコンストラクタ
        this.data = -1 ;
        this.next = null ;
    }
    void push( int x ) {
        this.next = new ListNode( x , this.next ) ;
    }
    int pop() {
        int ans = this.next.data ;
        this.next = this.next.next ;
        return ans ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode stack = new ListNode() ; // stack初期化用のコンストラクタを使う
        stack.push( 1 ) ;
        stack.push( 2 ) ;
        System.out.println( stack.pop() ) ;
        System.out.println( stack.pop() ) ;
    }
}

キュー(QUEUE)

2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。

配列を用いたQUEUE / リングバッファ

配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。

import java.util.*;

public class Main {
    static final int QUEUE_SIZE = 32 ;
    static int[] queue = new int[ QUEUE_SIZE ] ;
    static int wp = 0 ;
    static int rp = 0 ;
    static void put( int x ) {
        queue[ wp++ ] = x ;
        if ( wp >= QUEUE_SIZE ) // wp = wp % QUEUE_SIZE ; or wp = wp & (QUEUE_SIZE - 1) ;
            wp = 0 ;
    }
    static int get() {
        int ans = queue[ rp++ ] ;
        if ( rp >= QUEUE_SIZE ) // rp = rp % QUEUE_SIZE ; or rp = rp & (QUEUE_SIZE - 1) ;
            rp = 0 ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        // Your code here!
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}
#define QUEUE_SIZE 32
int queue[ QUEUE_SIZE ] ;
int wp = 0 ; // write pointer(書き込み用)
int rp = 0 ; // read  pointer(読み出し用)

void put( int x ) { // 書き込んで後ろ(次)に移動
    queue[ wp++ ] = x ;
    if ( wp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        wp = 0 ;
}
int get() { // 読み出して後ろ(次)に移動
    int ans = queue[ rp++ ] ;
    if ( rp >= QUEUE_SIZE )  // 末尾なら先頭に戻る
        rp = 0 ;
    return ans ;
}
void main() {
    put( 1 ) ; put( 2 ) ; put( 3 ) ;
    printf( "%d\n" , get() ) ; // 1
    printf( "%d\n" , get() ) ; // 2
    printf( "%d\n" , get() ) ; // 3
}

このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか?

 

リスト構造を用いたQUEUE

前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。

この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。

import java.util.*;

class ListNode {
   int      data ;
   ListNode next ;
   ListNode( int d , ListNode n ) {
       this.data = d ;
       this.next = n ;
   }
} ;

public class Main {
    static ListNode top = new ListNode( -1 , null ) ;
    static ListNode tail = top ;
    static void put( int x ) {
        tail.next = new ListNode( x , null ) ;
        tail = tail.next ;
    }
    static int get() {
        int ans = top.next.data ;
        top.next = top.next.next ;
        return ans ;
    }
    public static void main(String[] args) throws Exception {
        put( 1 ) ;
        put( 2 ) ;
        put( 3 ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
        System.out.println( get() ) ;
    }
}

Javaで書かれた ListNode を用いた待ち行列のイメージ図は下記のように示される。

struct List* queue = NULL ;
struct List** tail = &queue ;

void put( int x ) { // リスト末尾に追加
    *tail = cons( x , NULL ) ;
    tail = &( (*tail)->next ) ;
}
int get() { // リスト先頭から取り出す
    int ans = queue->data ;
    struct List* d = queue ;
    queue = queue->next ;
    free( d ) ;
    return ans ;
}

ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。

理解確認

  • 配列を用いたスタック・待ち行列は、どのような処理か?図などを用いて説明せよ。
  • リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
  • スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか?欠点があるか説明せよ。
  • 配列を用いたリングバッファが用いられている身近な例にはどのようなものがあるか?
  • 配列を用いたリングバッファを実装する場合配列サイズには 2n 個を用いることが多いのはなぜだろうか?

UMLと構造図

UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。

クラス図

クラス図は、構造図の中の基本的な図で、 枠の中に、上段:クラス名、中段:属性(要素)、下段:メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、”-“:private、”+”:public、”#”:protected 可視性に応じて、”+-#”などを記載する。

関連

クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連(association):単純に関係がある場合、
(b)集約(aggregation):部品として持つが、弱い結びつき。関係先が消滅しても別に存在可能。(has-a)
(c)コンポジション(composition):部品として持つが強い結びつき。関係先と一緒に消滅。(has-a)
(d)依存(dependency):依存関係にあるだけ
(e)派生(generalization):派生・継承した関係(is-a)
(f)実現(realization): Javaでのinterfaceによる多重継承

上図の例では、乗り物クラスVehicleから自動車Carが派生し(CarからVehicleへの三角矢印―▷)、 自動車は、エンジン(Engine)を部品として持つ(EngineからCarへのひし形矢印―◆)。エンジンは車体と一緒に廃棄なら、コンポジション(C++であれば部品の実体を持つ)で実装する。

自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約(部品への参照を持つ)で実装する(WheelからCarへのひし形矢印―◇)。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。

Javaなどのプログラム言語では、オブジェクトはデータの実体へのポインタで扱われるため、コンポジションと集約を区別して表現することは少ない。

is-a 、has-a の関係

前の課題でのカモノハシクラスで、羽や足の情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、“is-a”の関係“has-a”の関係で考えると、部品なのか継承なのか判断しやすい。

たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、”Car is-a Vehicle” といえるので、is-a の関係。 “Car is-a Engine”と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、”Car has-a Engine”といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。

ER図

UMLではないが、オブジェクト図に近いものとしてER図がある。これはリレーショナルデータベースの設計が正しいか確認しながら設計するための図で、Entity(実体)とRelation(関連)を相互に線で結んだもので、最近のER図の書き方は、かなりクラス図の書き方に似ている。

オブジェクト図

クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き中段の属性の所には具体的な値を書き込んで示す。

その他の構造図

パッケージ図

パッケージ図は、クラス図をパッケージ毎に分類して記載する図。 パッケージのグループを、フォルダのような図で記載する。


IT専科から引用

コンポーネント図とコンポジット構造図

コンポジット構造図は、クラスやコンポーネントの内部構造を示すもので、コンポーネント図は、複数のクラスで構成される処理に、 インタフェースを用意し、あたかも1つのクラスのように扱ったもの。 接続するインタフェースを飴玉と飴玉を受けるクチのイメージで、提供側を◯───で表し、要求側を⊃──で表す。


IT専科から引用

配置図

配置図は、システムのハードウェア構成や通信経路などを表現するための図。 ハードウェアは直方体の絵で表現し、 デバイスの説明は、”≪device≫”などを示し、実行環境には、”≪executionEnvironment≫” などの目印で表現する。


IT専科から引用

プロセス管理とシェルスクリプト

ジョブ管理

プログラムを実行している時、それがすごくメモリも使い計算時間もかかる処理の場合、条件を変化させながら結果が欲しい時、どのように実行すべきだろうか?1つの処理が1時間かかるとして、画面を見ながら1時間後に処理が終わったことを確認してプログラムを実行するのか?

簡単な方法としては、1つ目の処理(仮にプログラムAとする)を実行させたままで、新しくウィンドウを開いてそこで新しい条件でプログラムを並行処理すればいい(プログラムBとする)と考えるかもしれない。しかし、メモリを大量に使用する処理をいくつも並行処理させると、仮想メモリが使われるようになる。結果的にスワッピングが発生する分、プログラムAを実行させた後にプログラムBを実行するための時間以上に、時間がかかることになる。

ここで、プログラムを並行処理させるか、逐次処理させるといった、JOB(ジョブ)管理について説明を行う。
以下の説明で、複雑で時間のかかる処理を実行するとサーバの負担が高くなるので指定時間の処理待ちを行うための sleep 命令を使う。

逐次実行と並行実行

プログラムを連続して実行(処理Aの後に処理Bを実行する)場合には、セミコロン”;” で区切って A ; B のように処理を起動する。

guest00@nitfcei:~$ echo A
A
guest00@nitfcei:~$ echo A ; echo B
A
B

プログラムを並行して実行(処理Aと処理Bを並行処理)する場合には、アンド”&”で区切って A & B のように処理を起動する。

guest00@nitfcei:~$ sleep 5 &
[1] 55
guest00@nitfcei:~$ echo A
A
[1]+ 終了  sleep 5
guest00@nitfcei:~$ sleep 2 & sleep 3
[1] 56
[1]+ 終了  sleep 2
guest00@nitfcei:~$ time ( sleep 1 ; sleep 1 )   # time コマンドは、コマンドの実行時間を測ってくれる。
real    0m2.007s
user    0m0.005s
sys     0m0.002s
guest00@nitfcei:~$ time ( sleep 1 & sleep 1 )
real    0m1.002s
user    0m0.003s
sys     0m0.000s

fg, bg, jobs コマンド

プログラムを実行中に、処理(ジョブ)を一時停止したり、一時停止している処理を復帰させたりするときには、fg, bg, jobs コマンドを使う。

  • 処理をしている時に、Ctrl-C を入力すると前面処理のプログラムは強制停止となる。
  • 処理をしている時に、Ctrl-Z を入力すると前面処理のプログラムは一時停止状態になる。
  • fg (フォアグラウンド) は、指定した処理を前面処理(キー入力を受け付ける処理)に変更する。
  • bg (バックグラウンド) は、指定した処理を後面処理(キー入力が必要になったら待たされる処理)に変更する。
  • jobs (ジョブ一覧) は、実行中や一時停止している処理(ジョブ)の一覧を表示する。
guest00@nitfcei:~$ sleep 10   # 途中で Ctrl-Z を入力する
^Z
[1]+ 停止  sleep 10
guest00@nitfcei:~$ fg
sleep 10                      # 一時停止していた sleep 10 を実行再開
guest00@nitfcei:~$ sleep 3
^Z
[1]+  停止  sleep 3
guest00@nitfcei:~$ sleep 4
^Z
[2]+  停止  sleep 4
guest00@nitfcei:~$ jobs
[1]-  停止  sleep 3           # [1],[2]というのはjob番号
[2]+  停止  sleep 4
guest00@nitfcei:~$ fg %1      # ジョブ番号1 を前面処理にする
sleep 3
guest00@nitfcei:~$ fg %2      # ジョブ番号2 を前面処理にする
sleep 4

ps, kill コマンド

OS では、プログラムの処理単位は プロセス(process) と呼ぶ。OS はプロセスごとにメモリの実行範囲などの管理を行う。一連のプロセスを組み合わせて実行する単位を ジョブ(job) と呼ぶ。

複数のプロセスは間違ったメモリアクセスで他のプロセスが誤動作するようでは、安心して処理が実行できない。そこで、OS は、プロセスが他のプロセスのメモリをアクセスすると強制停止させるなどの保護をしてくれる。しかし、プロセスと他のプロセスが協調して処理を行うための情報交換のためにメモリを使うことは困難である。プロセス間で情報交換が必要であれば、パイプ機能やプロセス間共有メモリ機能を使う必要がある

最近のOSでは、共通のメモリ空間で動き 並行動作する個々の処理は スレッド(thread) と呼び、その複数のスレッドをまとめたものがプロセスとなる。OS では、プロセスごとに番号が割り振られ、その番号を プロセスID(PID) と呼ぶ。実行中のプロセスを表示するには、ps コマンドを使う。

実行中のプロセスを停止する場合には、kill コマンドを用いる。停止するプログラムは、ジョブ番号(%1など) か プロセスID を指定する。

guest00@nitfcei:~$ sleep 3
^Z
[1]+  停止  sleep 3
guest00@nitfcei:~$ sleep 4
^Z
[2]+ 停止 sleep 4
guest00@nitfcei:~$ jobs
[1]- 停止 sleep 3                 # [1],[2]というのはjob番号
[2]+ 停止 sleep 4
guest00@nitfcei:~$ ps w          # プロセスの一覧(wを付けるとコマンドの引数も確認できる)
 PID TTY   STAT TIME     CMD
  13 pts/0 Ss   00:00:00 -bash
  84 pts/0 T    00:00:00 sleep 3
  85 pts/0 T    00:00:00 sleep 4
  86 pts/0 R    00:00:00 ps w
guest00@nitfcei:~$ kill %1 
[1]- Terminated  sleep 3
guest00@nitfcei:~$ kill -KILL 85
[2]+ 強制終了     sleep 4
guest00@nitfcei:~$ ps ax          # 他人を含めた全プロセスの一覧表示 
 PID TTY STAT TIME COMMAND
   1 ?   Ss   0:52 /sbin/init
   2 ?   S    0:00 [kthreadd]
   3 ?   I<   0:00 [rcu_gp]
   :

ここまでの授業では、OSでのリダイレクト・パイプの概念とプロセスの概念について説明を行ってきた。これによりプログラムの実行結果を他のプログラムに渡すことができる。これらの機能を使うと、いくつかのプログラムを次々と実行させるなどの自動化をしたくなってくる。そこで、これ以降では、OSとプログラムの間の情報を伝え合う基本機能の説明や、プログラムの起動をスクリプトとしてプログラム化するためのシェルスクリプト(shell script)について説明する。

環境変数

OSを利用していると、その利用者に応じた設定などを行いたい場合が多い。このような情報を管理する場合には、環境変数が使われる。環境変数はプロセス毎に管理され、プロセスが新しく子供のプロセス(子プロセス)を生成すると、環境変数は子プロセスに自動的に引き渡される。代表的な環境変数を以下に示す。

  • HOME – ユーザがログインした際の起点となるディレクトリであり、/home/ユーザ名 となっているのが一般的。
    シェルの中では”~” で代用できる。( “cd ~” で、最初のディレクトリに戻る )
  • LC_ALL, LANG – ユーザが使う言語。OSからのメッセージなどを日本語で表示したい場合には、ja_JP.UTF-8 などを指定。
  • TZ – ユーザの時差の情報(Time Zone) 日本であれば、”JST-9″ を設定するのが一般的。
    日本標準時 “JST” で、グリニッジ標準時(GMT)との時差を表す “-9” の組み合わせ。
  • PATH – ユーザがよく使うコマンドの保存されているディレクトリの一覧。/bin:/usr/bin の様にディレクトリ名を”:”区切りで書き並べる。
  • LD_LIBRARY_PATH – 共有ライブラリの保存されているディレクトリの一覧。

環境変数と同じように、シェルの中で使われるものはシェル変数と呼ぶ。この変数は、子プロセスに引き渡されない。

環境変数を表示するには、env コマンド(環境変数を表示)や、set コマンド(環境変数やシェル変数を表示)を用いる。シェルの中で特定の環境変数を参照する場合には、$変数名 とする。echo コマンドで PATH を表示するなら、”echo $PATH” とすればいい。

guest00@nitfcei:~$ env
SHELL=/bin/bash
:
guest00@nitfcei:~$ echo $PATH
/bin:/usr/bin:/usr/local/bin

変数に値を設定する場合には、“変数名=値” の様に設定する。この変数を環境変数に反映させるには、export コマンドを用いるか、“export 変数名=値” を用いる。

環境変数の中で PATH は、コマンドを実行する際にコマンドの保存先を探すための変数であり、例えば PATH=/bin:/usr/bin:/usr/local/bin であったばあい、shell は、最初に /bin の中からコマンドを探し、次に /usr/bin を探し、さらに /usr/local/bin の中からコマンドを探す。PATH の設定の注意点

((( 環境変数の設定 )))
guest00@nitfcei:~$ PATH=/bin:/usr/bin
guest00@nitfcei:~$ echo $PATH
guest00@nitfcei:~$ export PATH
guest00@nitfcei:~$ export PATH=/bin:/usr/bin:/usr/local/bin

((( PATHの確認 )))
guest00@nitfcei:~$ which zsh       # which はコマンドの場所を探してくれる
/bin/zsh
guest00@nitfcei:~$ export PATH=/usr/local/bin:/usr/bin:/bin
guest00@nitfcei:~$ which zsh
/usr/bin/zsh

((( LC_ALL,LANG の確認 )))
guest00@nitfcei:~$ export LC_ALL=C
guest00@nitfcei:~$ man man
(英語でマニュアルが表示される)
guest00@nitfcei:~$ export LC_ALL=ja_JP.UTF-8
guest00@nitfcei:~$ man man
(日本語でマニュアルが表示される)

((( TZタイムゾーンの確認 )))
guest00@nitfcei:~$ export TZ=GMT-0
guest00@nitfcei:~$ date
2022年 7月 4日 月曜日 05:23:23 GMT       # イギリスの時間(GMT=グリニッジ標準時間)が表示された
guest00@nitfcei:~$ export TZ=JST-9
guest00@nitfcei:~$ date                 # 日本時間(JST=日本標準時間)で表示された
2022年 7月 4日 月曜日 14:23:32 JST
guest00@nitfcei:~$ TZ=GMT-0 date ; date # 環境変数を一時的に変更して date を実行
2022年 7月 4日 月曜日 05:23:23 GMT
2022年 7月 4日 月曜日 14:23:32 JST

環境変数 PATH の考え方は、Windows でも同じように存在し、PATH を変更する場合には、「設定 – システムのプロパティ – 詳細設定 – 環境変数」により編集可能となる。

プログラムとコマンドライン引数と環境変数

この後に説明するシェルスクリプトなどの機能を用いる場合は、自分のプログラムとのデータのやり取りにコマンドライン引数と環境変数を使う。また、プログラムの実行に失敗した時に別の処理を実行するためには、main関数の返り値を使うことができる。

コマンドライン引数

コマンドライン引数は、プログラムを起動する時の引数として書かれている情報であり、C言語でこの情報を用いる時には、main関数の引数”int main( int argc , char** argv ) …” により値をもらうことができ、以下のようなプログラムを記述することで受け取ることができる。
# 参考として Java の場合のコマンドライン引数の取得方法も示す。

((( argv.c )))
#include <stdio.h>

int main( int argc , char** argv ) {
    for( int i = 0 ; i < argc ; i++ ) {
        printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
    }
    return 0 ;
}
((( argv.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argv.c .
guest00@nitfcei:~$ gcc argv.c
guest00@nitfcei:~$ ./a.out 111 aaa 234 bcdef
argv[0] = ./a.out
argv[1] = 111
argv[2] = aaa
argv[3] = 234
argv[4] = bcdef

((( Argv.java )))
import java.util.* ;

public class Argv {
        public static void main( String[]  args ) throws Exception {
                for( int i = 0 ; i < args.length ; i++ )
                        System.out.println( "args["+i+"] = "+args[i] ) ;
        }
}
((( Argv.java を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/Argv.java .
guest00@nitfcei:~$ javac Argv.java
guest00@nitfcei:~$ java Argv 111 aaa 234 bcdef
args[0] = 111            # Java では コマンド名argv[0]は引数に含まれない
args[1] = aaa
args[2] = 234
args[3] = bcdef

注意点:コマンドライン引数の0番目には、プロセスを起動した時のプロセス名が入る。

環境変数の参照

C言語のmain関数は、コマンドライン引数のほかに環境変数も参照することができる。envpの情報は、getenv関数でも参照できる。

((( argvenvp.c )))
#include <stdio.h>
int main( int argc , char** argv , char** envp ) {
    // コマンドライン引数argc,argvの処理
    for( int i = 0 ; i < argc ; i++ ) {
        printf( "argv[%d] = %s\n" , i , argv[ i ] ) ;
    }
    // 環境変数envpの処理
    for( int i = 0 ; envp[i] != NULL ; i++ ) {
        printf( "envp[%d] = %s\n" , i , envp[ i ] ) ;
    }
    return 0 ;
}
((( argvenvp.c を実行してみる )))
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argvenvp.c .
guest00@nitfcei:~$ gcc argvenvp.c
guest00@nitfcei:~$ ./a.out
argv[0] = ./a.out
envp[0] = SHELL=/bin/bash
:

プロセスの返す値

プログラムによっては、処理が上手くいかなかったことを検知して、別の処理を実行したいかもしれない。
こういう場合には、C言語であれば main の返り値に 0 以外の値で return させる。( exit関数を使ってもいい )
以下の例では、入力値の平均を出力するが、データ件数が0件であれば平均値を出力できない。こういう時に、”return 1 ;” のように値を返せば、シェル変数 $? (直前のコマンドの返り値) に return で返された値を参照できる。

((( average.c )))
#include <stdio.h>
int main() {
    int count = 0 ;
    int sum = 0 ;
    char buff[ 1024 ] ;
    while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
        int value ;
        if ( sscanf( buff , "%d" , &value ) == 1 ) {
            sum += value ;
            count++ ;
        }
    }
    if ( count == 0 ) {
        // データ件数が0の場合は平均が計算できない。
        fprintf( stderr , "No data\n" ) ;
        // プログラムが失敗したことを返すには 0 以外の値を return する。
        return 1 ;      // exit( 1 ) ;
    } else {
            printf( "%lf\n" , (double)sum / (double)count ) ;
    }
    return 0 ;
}

((( average.c を動かしてみる )))
guest00@nitfcei:~$ gcc average.c
guest00@nitfcei:~$ ./a.out
12
14
^D        # Ctrl-D で入力を終わらせる
13.00000
guest00@nitfcei:~$ echo $?       # プロセスの実行結果の値を参照するためのシェル変数 $?
0
guest00@nitfcei:~$ ./a.out
^D        # データを入力せずにすぐに終了させる。
No data
guest00@nitfcei:~$ echo $?
1

シェルスクリプト

今まで、コマンドラインで命令の入力をしてきたが、こういったキーボードと対話的処理を行うプログラムは shell (シェル) と呼ばれ、今回の演習では、/bin/bash を用いている。 shell は、キーボードとの対話的処理だけでなく、shell で入力するような処理をファイルに記録しておき、そのファイルに記載されている順に処理を実行することができる。

guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/helloworld.sh .
guest00@nitfcei:~$ cat helloworld.sh
#!/bin/bash

echo "Hello World"

message="こんにちは"                       # シェル変数への代入
echo "Hello World = $message"             # シェル変数の参照

guest00@nitfcei:~$ bash helloworld.sh     # bash で helloworld.sh を実行する
Hello World
Hello World = こんにちは

シェルスクリプトの基本は、キー入力で実行するようなコマンドを書き並べればいい。

しかし、プログラムを実行する度に、bash ファイル名 と入力するのは面倒。こういう時には以下の2つの設定を行う。

  1. シェルスクリプトの先頭行に 実行させる shell の名前の前に “#!” をつける。
    この行は、通称”シバン shebang (シェバン)“と呼ばれ、bashで実行させたいのなら”#!/bin/bash“、プログラミング言語 Perl で実行させたいのなら “#!/usr/bin/perl” とか、Python で実行させたいのなら、”#!/usr/bin/python” のようにすればいい。(今回のサンプルはすでに記入済み)
  2. 保存したスクリプトに対して、実行権限を与える。
    “ls -al “で “rw-r–r–” のようなファイルの書き込みパーミッションが表示されるが、通常ファイルの場合は、“x”の表示があると、プログラムとして実行可能となる。(フォルダであれば、rwxr-xr-x のように”x”の表示があると、フォルダの中に入ることができる)
((( 実効権限の設定 )))
guest00@nitfcei:~$ chmod 755 helloworld.sh
guest00@nitfcei:~$ ./helloworld.sh
Hello World
Hello World = こんにちは

$HOME/.bashrc

シェルスクリプトは、Linux の環境設定を行うためのプログラム言語として使われている。

例えば、ユーザがログインする際には、そのユーザがどういった言語を使うのか(LC_LANG,LANG)や、どういったプログラムをよく使うのか(PATH,LD_LIBRARY_PATH)などは、そのユーザの好みの設定を行いたい。こういう時に、shell に bash を使っているのであれば、$HOME/.bashrc に、shell を使う際の自分好みの設定を記載すればいい。

((( $HOME/.bashrc の例 )))
#!/bin/bash

# PATHの設定
export PATH=/usr/local/bin:/usr/bin:/bin

# MacOS でインストールされているソフトで PATH を切り替える
if [ -d /opt/homebrew/bin ]; then  # /opt/homebrew/bin のディレクトリがあるならば...
        # HomeBrew
        export PATH=/opt/homebrew/bin:$PATH
elif [ -d /opt/local/bin ]; then   # /opt/local/bin のディレクトリがあるならば...
        # MacPorts
        export PATH="/opt/local/bin:$PATH"
fi

ユーザ固有の設定以外にも、OSが起動する時に、起動しておくべきプログラムの初期化作業などにもシェルスクリプトが使われている。
例えば、/etc/init.d/ フォルダには、Webサーバ(apache2)やsshサーバ(ssh) といったサーバを起動や停止をするための処理が、シェルスクリプトで記載してあり、OS 起動時に必要に応じてこれらのシェルスクリプトを使ってサーバソフトを起動する。(ただし最近は systemd が使われるようになってきた)

理解度確認

D/A・A/D変換回路と誤差

小型コンピュータを使った制御では、外部回路に指定した電圧を出力(D/A変換)したり、外部の電圧を入力(A/D変換)したりすることが多い。以下にその為の回路と動作について説明する。

D/A変換回路

ラダー抵抗回路によるD/A変換の仕組みを引用

このような回路で、D0,D1,D2 は、デジタル値の0=0[V] , 1=5[V] であった場合、Output 部分の電圧は、(D0,D1,D2)の値が、(0,0,0),(0,0,1),…(1,1,1)と変化するにつれ、5/8[V]づつ増え、(1,1,1)で 5*(7/8)=4.4[V]に近づいていく。最後に、Output が出力によって電圧が変化しないように、アンプ回路を通す。

DCモータをアナログ量で制御しないこと

このように、電圧をコンピュータから制御するようになると、ロボットで模型用の直流モータの回転速度をこれで制御したい…と考えるかもしれない。
しかし、直流モータは、ブラシとコイル(電磁石)を組み合わせたものだが、モーターが回転しだす瞬間でみれば、コイルは単なる導線である。このため、小さい電流でゆっくりモータを回転させようとすると、たとえ小さい電圧でも導線(抵抗はほぼ0[Ω])には大量の電流が流れ、モータをスイッチングする回路は焼き切れるかもしれない。



PWM変調

こういう場合には、PWM変調(Pulse Width Modulation) を行う。電圧の高さは一定で、高速回転させるときは長時間電圧をONにするが、低速回転させるときはONとOFFを繰り返し信号でONの時間を短くする。

このような波形であれば、低速度でも電流が流れる時間が短く、大量の電流消費は避けられ、モーターをまわす力も安定する。

A/D変換回路

D/A変換とは逆に、アナログ量をデジタル値に変換するには、どのようにするか?

このような場合には、A/D変換回路を用いる。一般的な回路では、以下のような逐次比較型A/D変換を用いる。

この回路では、変換開始と共に入力値をサンプル保持回路でアナログ量を保存する。
その後、Registerの中のデジタル値を、D/A 変換回路でアナログ量に変換した結果を、比較器(Comparator)でどちらが大きいか判断し、その結果に応じて2分探索法とかハイアンドローの方式のように、比較を繰り返しながらデジタル値を入力値に近づけていく。

ハイアンドロー(数あてゲーム)

数あてゲームで、デタラメな0〜127までの整数を決めて、ヒントを元にその数字を当てる。回答者は、数字を伝えると、決めた数よりHighかLowのヒントをもらえる。
最も速い回答方法は…

例えば決めた数が55だとすると

・初期状態    ???????  0..127
・64 - Low   0??????  0..63
・32 - High  01????? 32..63
・48 - High  011???? 48..63
・56 - Low   0110??? 48..55
・52 - High  01101?? 52..55
・54 - High  011011? 54..55
・55 - Bingo 0110111 55確定

どんな値でも、7回(27=127)までで当てることができる。

量子化と量子化誤差

アナログデータ(連続量)デジタルデータなどの離散的な値で近似的に表すことを、量子化という。

量子化誤差とは、信号をアナログからデジタルに変換する際に生じる誤差のことをいう。

アナログ信号からデジタル信号への変換を行う際、誤差は避けられない。アナログ信号は連続的で無限の正確さを伴うが、デジタル信号の正確さは量子化の解像度やアナログ-デジタル変換回路のビット数に依存する。

偶然誤差

アナログ信号がA/D変換回路に入るまでに、アナログ部品の電気的変動(ノイズ)が原因で値が変動することもある。ノイズが時間的に不規則に発生し、値が増えてしまったり減ってしまったり偶然に発生するものは偶然誤差という。偶然誤差を加えると相殺されてほぼ0になるのであれば、統計的な手法で誤差の影響を減らすことができる

系統誤差

ある特定の原因によって測定値が偏る誤差は、系統誤差と呼ぶ。例として、測定機器が持つ精度である器差によるもの、温度や湿度、気圧などが影響して発生するもの、測定方法の癖で値が偏るものなどがある。系統誤差は、誤差の要因が解ればその偏ったズレの量を調べて、測定した値からズレを引き算すれば補正することができる。

なぜデジタル信号を使うのか

コンピュータが信号処理でなぜ使われるのか?例えば、下の信号のように、電圧の低い/高いで0/1を表現したとする。

ノイズが混入しづらい

このデータ”01011100″を通信相手に送る場合、通信の途中でノイズ(図中の赤)のような信号が加わった場合、アナログ信号では、どれがノイズなのか判別することはできない。しかしデジタル信号であれば、真ん中青線より上/下か?で判別すれば、小さいノイズの影響は無視して、元どおりの”01011100″を取り出せる。この0か1かを判別するための区切り(図中青線)は、しきい値と呼ばれる。

ノイズを見つける・治す

また、”01011100″のデータを送る通信の途中で、しきい値を越えるような大きなノイズが混ざって、受信したとする。この場合、単純に受け取るだけであれば、”01010100″で間違った値を受け取っても判別できない。しかし、データを送る際にパリティビット(偶数パリティであれば全データの1の数が偶数になるように)1ビットのデータを加える。このデータを受け取った際に、ノイズで1ビット反転した場合、1の数が奇数(3個)なので、ノイズでビット反転が発生したことがわかる。これをパリティチェックと言う。

このように、デジタル信号を使えば、しきい値を越えない程度のノイズならノイズの影響を無視できるし、たとえ大きなノイズでデータに間違いがあっても、パリティチェックのような方法を使えば間違って伝わったことを判別できる。

パリティチェックは、元のデータに1bitの信号を追加することで誤り検出ができるが、2bit同時に変化してしまうと誤りを見つけられない。そこで、元データにさらに多くのbit情報を追加すると、1bitの間違いを元に戻すようにもできる。誤り検出・訂正

電子回路で制御するかコンピュータで制御するか

これ以外にも、デジタル信号にする理由がある。

アナログ回路(電子回路)で制御しようとすると、抵抗やコイルやコンデンサといった受動素子が必要となるが、その中でもコイルは小型化がしづらい部品で、制御回路全体の小型化が難しい。大量生産ができるような回路なら小型化ができるかもしれないが、多品種少量の生産物では小型化のための開発費用の元がとれない。しかし、大量生産された安価な小型コンピュータで制御すれば、制御回路全体の小型化も可能となる。

また、電子回路の特性を調整するには、抵抗などの部品をはんだ付けをしながら部品を交換することになるかもしれない。しかしながら、アナログ信号をデジタル信号にしてしまえば、ノイズを減らすための平均化処理などは計算で実現できるし、特性を変化させるための調整もプログラムの数値を変更するだけで可能となる。

UMLの概要

巨大なプロジェクトでプログラムを作成する場合、設計の考え方を図で示すことは、直感的な理解となるため重要であり、このために UML がある。以下にその考え方と記述方法を説明していく。

プログラムの考え方の説明

今まで、プログラムを人に説明する場合には、初心者向けの方式としてフローチャートを使うのが一般的であろう。しかし、フローチャートは四角の枠の中に説明を書ききれないことがあり、使い勝手が悪い。他には、PAD と呼ばれる記述法もある。この方法は、一連の処理を表す縦棒の横に、処理を表す旗を並べるようなイメージで記載する。

しかし、これらの記法は、手順を記載するためのものであり、オブジェクト指向のようなデータ構造を説明するための図が必要となってきた。

個人的な経験では、企業にてプログラムを作っていた頃(1990年頃)、UML などの考え方は普及していなかった。処理を説明するためのフローチャートでも、通信関係のプログラムでは、送信側と受信側の相互関係を説明する場合、フローチャートでは相互のタイミングなどの説明は困難であった。また、通信では、リトライ・タイムアウトといった状態も発生するが、その場合だと状態遷移図なども併記する必要があり、フローチャートの限界を感じていた。

また、データ構造については、オブジェクト指向も普及前であればデータ要素の一覧表が中心であった。プログラム書式(コーディングスタイル)などの統一もされていないので、同じチーム内で誤解などを解消するための意思統一が重要であった。

プログラムのドキュメント

学生のみなさんは、プログラムの説明の文書はどのように残しているだろうか?

私が仕事をしていた頃は、プログラムと別にドキュメントをワープロで残そうとすると、プログラム変更に合わせて編集することが難しく、プログラムとドキュメントの乖離が発生する。このため、プログラムの中にコメントの形で残すことが重要であった。特にデータ構造の説明は、ヘッダファイルの中に大量のコメントで残すことが多かった。

TeX(LaTeX)を改発した Knuth は、文芸的プログラミングとして、プログラム中にドキュメントを併記するための WEB を同時に開発している。このシステムでは、プログラムとドキュメントを併記したソースプログラムから、ドキュメントを取り出すプログラムと、ソースコードを取り出すプログラムがあり、情報の一体性を高めている。

最近では、プログラムのエディタで Markdown という、マークアップ言語でドキュメントを残す場合も多いだろう。これであれば、プレーンテキストで書いたドキュメントを、HTMLLaTeXといったWeb形式・論文形式といったドキュメントに変換も容易である。

このような方法で、ドキュメントとプログラムの乖離を防ぐことが重要となる。


UML記法が生まれるまで

巨大なプロジェクトでプログラムを作る場合、対象となるシステムを表現する場合、オブジェクト指向分析(Object Oriented Analysis)オブジェクト指向設計(Object Oriented Design)とよばれるソフトウェア開発方法が重要となる。(総称して OOAD – Object Oriented Analysis and Design)

これらの開発方法をとる場合、(1)自分自身で考えを整理したり(2)グループで設計を検討したり(3)ユーザに仕様を説明したりといった作業が行われる。この時に、自分自身あるいはチームメンバーあるいはクライアントに直感的に図を用いて説明する。この時の図の書き方を標準化したものが UML であり、(a)処理の流れを説明するための振る舞い図(フローチャートやPAD)と、(b)データ構造を説明するための構造図を用いる。

UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA(Object Oriented Anarisys)中心)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE/Object Oriented Software Engineering)を元に1990年頃に 発生し、ブーチのBooch法(どちらかというとOOD(Object Oriented Design)中心)の考えをまとめ、 UML(Unified Modeling Language)としてでてきた。

UMLでよく使われる図を列記すると、以下の物が挙げられる。

  • 構造図
    • クラス図
    • コンポーネント図
    • 配置図
    • オブジェクト図
    • パッケージ図
  • 振る舞い図
    • アクティビティ図
    • ユースケース図
    • ステートチャート図(状態遷移図)
    • 相互作用図
    • シーケンス図
    • コミュニケーション図(コラボレーション図)

その他の関連雑談のためのリンク

 

フィルタとプロセス管理

フィルタプログラム

パイプを使うと、標準入力からデータをもらい・標準出力に結果を出力するような簡単なプログラムを組み合わせて、様々な処理が簡単にできる。こういったプログラムは、フィルタと呼ぶ。

簡単な例として、入力をすべて大文字に変換するプログラム(toupper)、入力文字をすべて小文字に変換するプログラム(tolower)が、下記の例のように保存してあるので動作を確かめよ。

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/toupper.c .
guest00@nitfcei:~$ gcc -o toupper toupper.c .
guest00@nitfcei:~$ cat toupper.c | ./toupper
#INCLUDE <STDIO.H>
#INCLUDE <CTYPE.H>
INT MAIN() {
    INT     C ;
    WHILE( (C = GETCHAR()) != EOF )
        PUTCHAR( TOUPPER( C ) ) ;
    RETURN 0 ;
}

guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/tolower.c .
guest00@nitfcei:~$ gcc -o tolower tolower.c
guest00@nitfcei:~$ cat tolower.c | ./tolower
(((何が出力されるか答えよ)))

よく使われるフィルタのまとめ

 

文字パターンを含む行だけ出力 grep 文字パターン
文字パターンを含まない行を出力
文字パターンを正規表現でマッチングし該当を出力
大文字小文字を区別しない
grep -v 文字パターン
grep -e 正規表現
grep -i 文字パターン
入力文字数・単語数・行数をカウント(word counter) wc
入力行数をカウント wc -l
データを昇順に並べる sort
データを降順に並べる
先頭を数字と見なしてソート
sort -r
sort -g
同じ行データが連続したら1つにまとめる uniq
同じ行が連続したら1つにまとめ、連続した数を出力 uniq -c
空白区切りで指定した場所(1番目)を抽出 awk ‘{print$1;}’
入力の先頭複数行を表示(10行) head
入力の末尾複数行を表示(10行) tail
指定した行数だけ、先頭/末尾を表示 head -行数
tail -行数
入力したデータを1画面分表示した所で一時停止する(ページャ)
more は、最も単純なページャで、SPACE で1画面送り、ENTER で1行送り、”q”で終了。
lv は前後に移動できるページャで、カーソルキー↑(b)↓(f) で行を前後に移動できる。
more
lv

LOG解析

Linux は利用者に様々なサービスを提供するサーバで広く利用されている。しかし、幅広いサービス提供となると、中にはウィルス拡散や個人情報収集のための悪意のあるアクセスも増えてくる。

このためサーバでは、アクセスを受けた時の状況を記録し保存する。このような情報はアクセス履歴ログと呼ぶ。

ログの中には、以下のような情報が混在することになるが、大量の 1. や 2. 目的のアクセスの中に、3. や 4. といったアクセスが混ざることになるが、これを見逃すとシステムに不正侵入を受ける可能性もある。

  1. 本来の利用者からのアクセス
  2. 検索システムの情報収集(クローラーからのアクセス)
  3. 不正な情報収集のためのアクセス
  4. システムの不備を探して不正侵入などを試みるアクセス

今回の演習では、電子情報の web サーバのとある1日のアクセス履歴ファイルを用い、パイプ機能を使い様々なフィルタを使い LOG解析の練習を行う。

アクセス履歴の解析

Webサーバのアクセス履歴が、/home0/Challenge/2.2-LOG.d/access.log に置いてある。このファイルで簡単な確認をしてみよう。

(( ファイルの場所に移動 ))
$ cd /home0/Challenge/2.2-LOG.d/

(( .asp という文字を含む行を表示 ))
$ grep .asp access.log

電子情報のWebサーバには、.asp (WindowsのWebサーバで動かすプログラムの拡張子) など存在しない。明らかに設定不備を探すための攻撃である。

これを見ると、grep で .asp を含む行が抜粋され、.asp の部分が強調されていることで、攻撃を簡単に確認できる。しかしこれは画面行数で10件程度が確認できるが、本当は何回攻撃を受けたのだろうか?この場合は、行数をカウントする”wc -l” を使えばいい。

(( アクセス回数を数える ))
$ grep .asp access.log | wc -l
37

access.log の各項目の意味

電子情報のWebサーバの access.log に記録されている各項目の意味は以下の通り。

 

項目 log項目 内容
1 %h リモートホスト。WebサーバにアクセスしてきたクライアントのIPアドレス
2 %l リモートログ名。説明略。通常は “-“
3 %u ログインして操作するページでのユーザ名。通常は “-“
4 %t アクセスを受けた時刻
5 %r 読み込むページ。アクセス方法(GET/POSTなど)と、アクセスした場所
6 %>s ステータスコード。(200成功,403閲覧禁止,404Not Found)
7 %b 通信したデータのバイト数
8 %{Referer}i Referer どのページからアクセスが発生したのか
9 %{User-Agent}i User-Agent ブラウザ種別(どういったブラウザからアクセスされたのか)

以下に、フィルタプログラムを活用して、色々な情報を探す例を示す。実際にコマンドを打って何が表示されるか確認しながら、フィルタプログラムの意味を調べながら、何をしているか考えよう。

.asp を使った攻撃を探す

(( .asp を試す最初の履歴を探す ))
$ grep "\.asp" access.log | head -1
49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)"

(( 49.89.249.9 がどんなアクセスを試みているのか探す ))
$ grep ^49.89.249.9 access.log | head
49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /Include/md5.asp HTTP/1.1" 404 64344 "https://www.ei.fukui-nct.ac.jp/Include/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)"
49.89.249.9 - - [20/Dec/2019:09:19:06 +0900] "POST /inc/md5.asp HTTP/1.1" 404 61056 "https://www.ei.fukui-nct.ac.jp/inc/md5.asp" "Mozilla/4.0 (compatible; MSIE 9.0; Windows NT 6.1)"
  • ステータスコードが404は”Not Found”なので、読み出しに失敗している。
  • IPアドレス検索で、49.89.249.9 がどこのコンピュータか調べよう。

攻撃の時間を確認

(( 49.89.249.9 がどんな時間にアクセスを試みているのか探す ))
$ grep ^49.89.249.9 access.log | awk '{print $4;}'
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:06
[20/Dec/2019:09:19:07
:
  • 不正アクセスを試みている時間を調べると、そのアクセス元の09:00~17:00に攻撃していることがわかる場合がある。どういうこと?

ページの閲覧頻度を確認

(( /~t-saitoh/ 見たIPアドレスと頻度 ))
$ grep "/~t-saitoh/" access.log | awk '{print $1;}' | sort | uniq -c | sort -g -r | head
     38 151.80.39.78
     35 151.80.39.209
     32 203.104.143.206
     31 5.196.87.138
        :
  • grep – “/~t-saitoh/”のページをアクセスしているデータを抽出
  • awk – 項目の先頭(IPアドレス)だけ抽出
  • sort – IPアドレス順に並べる(同じIPアドレスならその数だけ重複した行になる)
  • uniq – 重複している行数を数える
  • sort -g -r – 先頭の重複数で大きい順にソート
  • head – 先頭10行だけ抽出
(( /~t-saitoh/ 見たIPアドレスと頻度 ))
(( t-saitoh のテスト問題のページを誰が見ているのか? ))
$ grep "/~t-saitoh/exam/" access.log
5.196.87.156 - - [20/Dec/2019:06:36:02 +0900] "GET /~t-saitoh/exam/db2009/ex2009-5-1.pdf HTTP/1.1" 200 20152 "-" "Mozilla/5.0 (compatible; AhrefsBot/6.1; +http://ahrefs.com/robot/)"
 :
(( クローラーのアクセスが多くてよくわからないので bot を含まない行を抽出 ))
$ grep "/~t-saitoh/exam/" access.log | grep -v -i bot | lv
213.242.6.61 - - [20/Dec/2019:06:33:12 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.87 Safari/537.36 OPR/54.0.2952.64 (Edition Yx)"
188.163.109.153 - - [20/Dec/2019:06:43:04 +0900] "GET /%7Et-saitoh/exam/ HTTP/1.0" 200 19117 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99"
188.163.109.153 - - [20/Dec/2019:06:43:05 +0900] "POST /cgi-bin/movabletype/mt-comments.cgi HTTP/1.0" 404 432 "http://www.ei.fukui-nct.ac.jp/%7Et-saitoh/exam/" "Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.170 Safari/537.36 OPR/53.0.2907.99"
45.32.193.50 - - [20/Dec/2019:07:06:15 +0900] "GET /~t-saitoh/exam/apply-prog.html HTTP/1.0" 200 5317 "http://www.ei.fukui-nct.ac.jp/" "Mozilla/5.0 (Windows NT 5.2) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/63.0.3239.132 Safari/537.36"
  • この結果を見ると mt-comments.cgi というアクセスが見つかる。どうも コメントスパム(ブログのコメント欄に広告を勝手に書き込む迷惑行為)をしようとしている。

ネットワーク攻撃への対処

今回の access.log のアクセス履歴解析は、Webサーバへのアクセスへの基本的な対処となる。しかし、もっと違うネットワーク接続ではどのような対処を行うべきであろうか?

一般的には、

  • サーバにネットワークアクセスの記録ソフトを使う(例ネットワークプロトコルアナライザーWireShark)
  • ファイアウォールのアクセス履歴を解析

授業内レポート

  • ここまでのLOG解析の例の1つについて、どういう考え方でフィルタを使っているのか、自分の言葉で説明せよ。
  • LOG 解析のためのコマンドを考え、その実行結果を示し、それから何が判るか説明せよ。
    (例) コメントスパムを何度も試す危ないアクセス元は〇〇である。

ジョブ管理

プログラムを実行している時、それがすごくメモリも使い計算時間もかかる処理の場合、条件を変化させながら結果が欲しい時、どのように実行すべきだろうか?1つの処理が1時間かかるとして、画面を見ながら1時間後に処理が終わったことを確認してプログラムを実行するのか?

簡単な方法としては、1つ目の処理(仮にプログラムAとする)を実行させたままで、新しくウィンドウを開いてそこで新しい条件でプログラムを並行処理すればいい(プログラムBとする)と考えるかもしれない。しかし、メモリを大量に使用する処理をいくつも並行処理させると、仮想メモリが使われるようになる。結果的にスワッピングが発生する分、プログラムAを実行させた後にプログラムBを実行するための時間以上に、時間がかかることになる。

ここで、プログラムを並行処理させるか、逐次処理させるといった、JOB(ジョブ)管理について説明を行う。
以下の説明で、複雑で時間のかかる処理を実行するとサーバの負担が高くなるので指定時間の処理待ちを行うための sleep 命令を使う。

逐次実行と並行実行

プログラムを連続して実行(処理Aの後に処理Bを実行する)場合には、セミコロン”;” で区切って A ; B のように処理を起動する。

guest00@nitfcei:~$ echo A
A
guest00@nitfcei:~$ echo A ; echo B
A
B

プログラムを並行して実行(処理Aと処理Bを並行処理)する場合には、アンド”&”で区切って A & B のように処理を起動する。

guest00@nitfcei:~$ sleep 5 &
[1] 55
guest00@nitfcei:~$ echo A
A
[1]+ 終了  sleep 5
guest00@nitfcei:~$ sleep 2 & sleep 3
[1] 56
[1]+ 終了  sleep 2
guest00@nitfcei:~$ time ( sleep 1 ; sleep 1 )   # time コマンドは、コマンドの実行時間を測ってくれる。
real    0m2.007s
user    0m0.005s
sys     0m0.002s
guest00@nitfcei:~$ time ( sleep 1 & sleep 1 )
real    0m1.002s
user    0m0.003s
sys     0m0.000s

fg, bg, jobs コマンド

プログラムを実行中に、処理(ジョブ)を一時停止したり、一時停止している処理を復帰させたりするときには、fg, bg, jobs コマンドを使う。

  • 処理をしている時に、Ctrl-C を入力すると前面処理のプログラムは強制停止となる。
  • 処理をしている時に、Ctrl-Z を入力すると前面処理のプログラムは一時停止状態になる。
  • fg (フォアグラウンド) は、指定した処理を前面処理(キー入力を受け付ける処理)に変更する。
  • bg (バックグラウンド) は、指定した処理を後面処理(キー入力が必要になったら待たされる処理)に変更する。
  • jobs (ジョブ一覧) は、実行中や一時停止している処理(ジョブ)の一覧を表示する。
guest00@nitfcei:~$ sleep 10   # 途中で Ctrl-Z を入力する
^Z
[1]+ 停止  sleep 10
guest00@nitfcei:~$ fg
sleep 10                      # 一時停止していた sleep 10 を実行再開
guest00@nitfcei:~$ sleep 3
^Z
[1]+  停止  sleep 3
guest00@nitfcei:~$ sleep 4
^Z
[2]+  停止  sleep 4
guest00@nitfcei:~$ jobs
[1]-  停止  sleep 3           # [1],[2]というのはjob番号
[2]+  停止  sleep 4
guest00@nitfcei:~$ fg %1      # ジョブ番号1 を前面処理にする
sleep 3
guest00@nitfcei:~$ fg %2      # ジョブ番号2 を前面処理にする
sleep 4

ps, kill コマンド

OS では、プログラムの処理単位は プロセス(process) と呼ぶ。OS はプロセスごとにメモリの実行範囲などの管理を行う。一連のプロセスを組み合わせて実行する単位を ジョブ(job) と呼ぶ。

複数のプロセスは間違ったメモリアクセスで他のプロセスが誤動作するようでは、安心して処理が実行できない。そこで、OS は、プロセスが他のプロセスのメモリをアクセスすると強制停止させるなどの保護をしてくれる。しかし、プロセスと他のプロセスが協調して処理を行うための情報交換のためにメモリを使うことは困難である。プロセス間で情報交換が必要であれば、パイプ機能やプロセス間共有メモリ機能を使う必要がある

最近のOSでは、共通のメモリ空間で動き 並行動作する個々の処理は スレッド(thread) と呼び、その複数のスレッドをまとめたものがプロセスとなる。OS では、プロセスごとに番号が割り振られ、その番号を プロセスID(PID) と呼ぶ。実行中のプロセスを表示するには、ps コマンドを使う。

実行中のプロセスを停止する場合には、kill コマンドを用いる。停止するプログラムは、ジョブ番号(%1など) か プロセスID を指定する。

guest00@nitfcei:~$ sleep 3
^Z
[1]+  停止  sleep 3
guest00@nitfcei:~$ sleep 4
^Z
[2]+ 停止 sleep 4
guest00@nitfcei:~$ jobs
[1]- 停止 sleep 3                 # [1],[2]というのはjob番号
[2]+ 停止 sleep 4
guest00@nitfcei:~$ ps w          # プロセスの一覧(wを付けるとコマンドの引数も確認できる)
 PID TTY   STAT TIME     CMD
  13 pts/0 Ss   00:00:00 -bash
  84 pts/0 T    00:00:00 sleep 3
  85 pts/0 T    00:00:00 sleep 4
  86 pts/0 R    00:00:00 ps w
guest00@nitfcei:~$ kill %1 
[1]- Terminated  sleep 3
guest00@nitfcei:~$ kill -KILL 85
[2]+ 強制終了     sleep 4
guest00@nitfcei:~$ ps ax          # 他人を含めた全プロセスの一覧表示 
 PID TTY STAT TIME COMMAND
   1 ?   Ss   0:52 /sbin/init
   2 ?   S    0:00 [kthreadd]
   3 ?   I<   0:00 [rcu_gp]
   :

理解度確認

Javaでリスト構造

6/24(月)の大雨による休講で7/1(月)に説明

テスト前のリスト導入の復習

前回のリスト構造の導入では、配列のデータに次のデータの入っている番号を添えることで途中にデータを挿入できるデータ構造の説明をした。

また、それをクラスを用いたプログラムを示した。

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存する方法を、next の部分を次のデータへの参照を用いるように、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;   // データ部分
    ListNode next ;   // 次のデータへの参照
    // コンストラクタ
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
        // 途中にデータを入れる
        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

リスト操作

リスト構造に慣れるために簡単な練習をしてみよう。リスト構造のデータに対するメソッドをいくつか作ってみよう。print() や sum() を参考に、データ数を求める count() , 最大値を求める max() , データを検索する find() を完成させてみよう。

class ListNode {
    (略)
} ;

public class Main {
    static void print( ListNode p ) {   // リストを表示
        for( ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }

    static int sum( ListNode p ) {      // リストの合計を求める
        int s = 0 ;
        for( ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }

    static int count( ListNode p ) {    // データ件数を数える

    }

    static int max( ListNode p ) {      // データの最大値を求める

    }

    static boolean find( ListNode p , int key ) { // データ列の中から特定のデータを探す
                                                  //   見つかったら true , 見つからなければ false
    }
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        print( top ) ;
        System.out.println( "合計:" + sum( top ) ) ;
        System.out.println( "件数:" + count( top ) ) ;
        System.out.println( "最大:" + max( top ) ) ;
        System.out.println( "検索:" + (find( top , 22 )
                                       ? "みつかった" : "みつからない" ) ) ;
    }
}

オブジェクト指向っぽく書いてみる

前述のプログラムでは、print( top ) のように使う static な関数としてプログラムを書いていた。しかし、オブジェクト指向であれば、オブジェクトに対するメソッドだと top.print() のように書きたい。この場合だと、以下のように書くかもしれない。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
    int sum() {    // リストの合計を求める
        int  s = 0 ;
        for( ListNode p = this ; p != null ; p = p.next )
            s += p.data ;
        return s ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = null ;
        list_empty.print() ;  // 実行時エラー java.lang.NullPointerException ぬるぽ!
    }
}

しかし、データ件数 0件 に対してメソッドを呼び出せない。

ListNode と List というクラスで書いてみる

ひとつの方法として、リストの先頭だけのデータ構造を宣言する方法もある。

class ListNode {
    int   data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

class List {
    ListNode top ;
    List( ListNode p ) {
        this.top = p ;
    }
    void print() {
        for( ListNode p = top ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        List list = new List( new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ) ;
        list.print() ;
        
        List list_empty = new List( null ) ;
        list_empty.print() ;
    }
}

しかし、List と ListNode の2つのデータの型でプログラムを書くのは面倒くさい。

授業ではシンプルに説明したいので、今後はこの方法は極力避けていく。

先頭にダミーデータを入れる

複数のクラス宣言するぐらいなら、リストデータの先頭は必ずダミーにしておく方法もあるだろう。

import java.util.*;

class ListNode {
    int data ;
    ListNode next ;
    ListNode( int d , ListNode n ) {
        this.data = d ;
        this.next = n ;
    }
    void print() {   // リストの全データを表示
        for( ListNode p = this.next ; p != null ; p = p.next )
            System.out.print( p.data + " " ) ;
        System.out.println() ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode list = new ListNode( -1 , null ) ;
        list.next = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;
        top.print() ;
        System.out.println( "合計: " + top.sum() ) ;

        ListNode list_empty = new ListNode( -1 , null ) ;
        list_empty.print() ;
    }
}

以降、必要に応じて、先頭にダミーを入れる手法も取り混ぜながらプログラムを書くこととする。

入力データをリストに追加

入力しながらデータをリストに格納する処理を考えてみる。

リストでデータを追加保存するのであれば、一番簡単なプログラムは、以下のように先頭にデータを入れていく方法だろう。

class ListNode {
    (略)
    void print() {
        for( ListNode p = this ; p != null ; p = p.next )
            System.out.print( p.data ) ;
        System.out.println() ;
    }
} ;
    
public class Main {
    public static void main(String[] args) throws Exception {
        int[] inputs = { 11 , 22 , 33 } ;
        ListNode top = null ;

        for( int datum : inputs )
            top = new ListNode( datum , top ) ;
        top.print() ;
    }
}

でもこの方法だと、先頭にデータを入れていくため、保存されたデータは逆順になってしまう。

末尾にデータを入れる

逆順になるのを避けるのであれば、データを末尾に追加する方法があるだろう。ただし初期状態でデータが0件だと処理が書きづらいので、先頭にダミーを入れておく方法で書いてみる。

public class Main {
    public static void main(String[] args) throws Exception {
        int[] test_data = { 11 , 22 , 33 } ;

        ListNode top = new ListNode( -1 , null ) ; // ダミー
        ListNode tail = top ;
        for( int x : test_data ) {
            tail.next = new ListNode( x , null ) ;
            tail = tail.next ;
        }
        top.print() ; // -1   11  22  33
    }                 // ダミー
}

表計算ソフトの使い方(絶対参照・相対参照)

今日の表計算ソフトを使った演習では、下記のサンプルファイルを練習に使うので、Teamsで参照してください。

前回課題の答え合わせ

前回のレポートでは、sin(83度)(例)といった数値の有効数字を考えるというものを考えてもらったので、この有効数字をどう記載すべきか考えてみる。

課題を示す Excel ファイルでは、75度~89度あたりの角度で出題をするようにしてあった。注意しないといけない点は、sinは90度に近づくほど、1に近づく。このため、0.99…といった数値が求まるが、角度がちょっと変化しても、0.99といった部分はほぼ変化しない。だから、83が有効数字2桁ということで、0.99 といった有効数字2桁の書き方では、ちょっと不十分かもしれない。

そこで、83度(有効数字2桁)が小数点以下を丸められた数値と仮定する。この場合、元の数値は 82.5度~83.5度 の可能性がある。これらの値のsinを計算すると、0.9914から0.9935の間であり、小数点以下3桁目は、1~3 の値であり、結果を 0.992 (有効数字3桁) と記載しても良いかもしれない。

 sin(82.5°) = 0.991444861
 sin(83.0°) = 0.992546152
 sin(83.5°) = 0.993571856

表計算ソフトの使い方

情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。

セルの場所と簡単な式

簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。

Excel では、表のには左から、A,B,C,D… , 表のには上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に¥80、C5に4 が入っている。

例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、

=B2*C2

を書き込めば、その場所には360が表示される。

先頭の”=”を入力した後、該当する”B2″の場所をクリックするなりカーソルを操作すると、カーソルのセルの場所”B2″が自動的に入力される。さらに”*”を入力した後、”C2″の場所をクリックすれば”C2″が入力される。

Excelでは、入力する文字列の先頭が”=”の場合は、残り部分は計算式として扱われる。

D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。

この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。

ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)

関数式

例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー&ペーストし、A3,B3 を A4~A6にペーストすればいい。

B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。

また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。

絶対参照と相対参照

最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。

この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。

ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。

こういった場合には、絶対参照を用いる。D3 に記入する式を

=B3*C3*(1+$B$2)

とし、この D3 の式を D4 にコピー&ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。

このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。

絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時に[F4ボタン]を押す度に、B2$B$2B$2$B2B2 と変化する

$B2 は、式をコピーすると列部分はBのまま行部分は場所に合わせて変化する。

B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。

レポート課題(第5回)

Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。A列は角度・B列はsin(x)・C列はsin(x+y)の値とし、yの値は”C1″に保存されているものとする。

この時、計算式の入力をどのように行なったのか(相対参照や絶対参照をどのように使ったのか)説明を、グラフの下に入力欄を設け記入せよ。

なお、Excel の sin() 関数は、引数がラジアンで入力する必要があるので、計算式には注意せよ。

そして出来上がった Excel のファイルを、Teams のこちらのフォルダに提出せよ。

 

派生や集約と多重継承

派生や継承について、一通りの説明が終わったので、データ構造(クラスの構造)の定義の方法にも様々な考え方があり、どのように実装すべきかの問題点を考えるための説明を行う。その中で特殊な継承の問題についても解説する。

動物・鳥類・哺乳類クラス

派生継承を使うと、親子関係のあるデータ構造をうまく表現できることを、ここまでの授業で示してきた。

しかしながら、以下に述べるような例では、問題が発生する。

// 動物クラス
class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
  virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public Animal {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s fry.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

// 哺乳類クラス
class Mammal : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay baby.\n" , get_name() ) ;
  }
} ;

int main() {
  Bird chiken( "piyo" ) ;
  chiken.move() ;
  chiken.birth() ;
  Mammal cat( "tama" ) ;
  cat.move() ;
  cat.birth() ;
  return 0 ;
}

ここで、カモノハシを作るのであれば、どうすれば良いだろうか?

鳥類・哺乳類とは別にカモノハシを作る(いちばん無難な方法)

class SeaBream : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

この例では、簡単な処理だが、move() の中身が複雑であれば、改めて move() を宣言するのではなく、継承するだけの書き方ができないだろうか?

多重継承を使う方法(ダイヤモンド型継承が発生する)

C++ には、複数のクラスから、派生する多重継承という機能がある。であれば、鳥類と哺乳類から進化したのだから、以下のように書きたい。

// 多重継承 鳥(Bird)と哺乳類(Mammal) から SeaBeam を作る
class SeaBream : public Bird , public Mammal {
   //
} ;

しかし、カモノハシに move() を呼び出すと、鳥類の move() と哺乳類の move() のどちらを動かすか曖昧になる。

また「派生」は、基底クラスと派生クラスの両方のデータを持つデータ構造を作る。このため、単純に多重継承を行うと、カモノハシのクラスでは、派生クラスは親クラスのデータ領域と、派生クラスのデータ領域を持つため、鳥類の name[] と、哺乳類の name[] を二つ持つことになる。多重継承による”ダイヤモンド型継承”の問題

足と羽のクラスを作る場合(本来は多重継承で実装すべきではない)

以下に、足と羽のクラスを作ったうえで、多重継承を行うプログラム例を示す。

しかし、この例では、相変わらずカモノハシのクラスを多重継承で実装すると、ダイヤモンド型継承の問題が残る。

class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
} ;
// 羽
class Wing {
public:
   const char* move_method() { return "fly" ; }
} ;
// 
class Leg {
public:
   const char* move_method() { return "walk" ; }
} ;
class Bird : public Animal , public Wind {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;
class Mammal : public Animal , public Leg {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;

継承を使うべきか、部品として持つべきか

ただし、ここで述べた方式は、UML による設計の際に改めて説明を行うが、is-a , has-a の関係でいうなら、

  • Bird is a Animal. – 鳥は動物である。
    • “Bird has a Animal” はおかしい。
    • 鳥は、動物から派生させるのが正しい。
  • Bird has a Wing. – 鳥は羽をもつ。
    • “Bird is a Wing” はおかしい。
    • 鳥は、羽を部品として持つべき。

であることから、Wing は 継承で実装するのではなく、集約もしくはコンポジションのような部品として実装すべきである。

このカモノハシ問題をどうしても多重継承で実装したいのなら、C++では、以下のような方法で、ダイヤモンド型の継承問題を解決できる。

class Animal {
private:
   char name[ 10 ] ;
public:
   Animal( const char s[] ) {
      strcpy( name , s ) ;
   }
   const char* get_name() const { return name ; }
   virtual void move() = 0 ;
   virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public virtual Animal {
public:
   Bird( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s fry.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay egg.\n" , get_name() ) ;
   }
} ;

// 哺乳類クラス
class Mammal : public virtual Animal {
public:
   Mammal( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s walk.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay baby.\n" , get_name() ) ;
   }
} ;

class SeaBream : public virtual Bird , virtual Mammal {
public:
   SeaBream( const char s[] ) : Animal( s ) {}
   void move() {
      Mammal::move() ;
   }
   void birth() {
      Bird::birth() ;
   }
} ;

ただし、多重継承は親クラスの情報と、メソッドを継承する。この場合、通常だと name[] を二つ持つことになるので、問題が発生する。そこで、親クラスの継承に virtual を指定することで、ダイヤモンド型継承の 2つの属性をうまく処理してくれるようになる。

しかし、多重継承は処理の曖昧さや効率の悪さもあることから、採用されていないオブジェクト指向言語も多い。特に Java は、多重継承を使えない。その代わりに interface という機能が使えるようになっている。

多重継承を使える CLOS や Python では、適用するメソッドやインスタンス変数の曖昧さについては親クラスへの優先度を明確にできる機能がある。曖昧さの問題を避けるのであればクラス限定子”::”を使うべきである。

Unix演習で ./a.out の理由

今日の演習の後で “コマンドを実行する時に ./a.out とか先頭に ./ をつけるのはなぜ?” との質問があった。

環境変数 PATH とは

通常、フォルダ一覧を表示するために “ls” とか入力しているけど、ls という命令はどこにあるのだろうか?

実は、unix や Windows では「よく使うコマンドの保存場所」を 環境変数 PATH にて管理している。環境変数は “echo $PATH” といった命令で確認ができる。unix では PATH は “:” 区切りで「よく使うコマンドの場所(ディレクトリ)」が列記してある。通常は /usr/local/bin:/usr/bin:/bin といった値になっているはず。

コマンドを実行する時にディレクトリが明記されていない場合は、PATH のディレクトリから探して実行することになっている。
(Windows の PATH は “;” 区切りなので要注意。cmd.exe を起動し echo %PATH% を実行すれば PATHが確認できる)

$ ls
helloworld.c
$ which ls
/usr/bin/ls
$ echo $PATH
/usr/local/bin:/usr/bin/:/bin

このため、a.out のプログラムを実行する時には、”a.out” とだけ入力しても PATH に記載がないため「どこにある a.out を実行するの?」という状態になる。このため、カレントディレクトリにある a.out を実行する時には、”./” をつけて ./a.out と明示が必要となっている。

カレントディレクトリを PATH に加えればいいじゃん

コマンド実行で、いちいち“./”をつけるのはめんどくさい…と思う人もいるだろう。であれば、PATH を変更すればいい。

$ echo $PATH
/usr/local/bin:/usr/bin/:/bin
$ a.out
a.out: コマンドが見つかりません。
$ PATH=.:/usr/local/bin:/usr/bin/:/bin
$ a.out
HelloWorld

しかし、この設定はセキュリティ的にも危険なのでやってはいけない設定の代表例です。
# Windows は、カレントディレクトリのプログラム実行で PATH 指定が不要なので要注意。

PATH=.:/usr/bin:/bin が危険な理由

もし、誰にでも書き込みができるフォルダがあって、そのフォルダに “ls” という名前のファイルを置き逃げした人がいたとしよう。

別の人はそのフォルダに入って、どんなファイルがあるのかな?ということで “ls” とタイプするかもしれない。そうすると何が起こるだろうか?

どういったことが発生するか、体験するためのフォルダが作ってあるので何が起こるか試してみよう。

$ cat /home0/Challenge/1-CTF.d/Task5/Bomb/ls
#!/bin/bash
killall -KILL bash 2> /dev/null           # ← bash プロセスを殺すshell script(結果として強制ログアウトされる)
 
$ PATH=.:/usr/bin:/bin                    # 危険なPATHの指定

$ cd /home0/Challenge/1-CTF.d/Task5/Bomb
$ ls                                      # ← どんなファイルがあるかな? ls
Connection to nitfcei.mydns.jp closed.

この例では、強制ログアウトする命令となっているが、ls の処理として「login: … password: …」といった入力を行うようなプログラムが置いてあったら、「ls ってタイプしたらなぜかログイン画面にもどっちゃった。よくわからんけど再ログインするか…」と、ID とパスワードを入力する人もいるかもしれない。でも、この ID と パスワードを特定の人にメールするようにしてあれば、アカウント乗っ取りが可能となる。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー