シグナル

シグナル

「シグナル」はプロセスとプロセスの間で通信を行う際に使用される“信号”のことで、シグナルを受け取ったプロセスは“何らかの動作”を行う。その動作は、例えば「再起動」であったり、「終了」であったりする。シグナルが送信された際、OSは宛先プロセスの正常な処理の流れに割り込む。kill -lコマンドを使用すると、使用可能なシグナルの一覧が表示される。

 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP
 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1
11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM
16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP
21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ
26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR
31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3
38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8
43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13
48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12
53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7
58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2
63) SIGRTMAX-1  64) SIGRTMAX



シグナルを送出するには、 kill コマンドに送出先プロセスのプロセス ID と、送出するシグナルを指定して実行する。シグナルの指定には、各シグナルに定義されているシグナル番号かシグナル名のどちらかを使用する。送出先プロセスの プロセス ID (PID) は、ps コマンドや pgrep コマンドで確認することができる。

シグナル番号 シグナル名 通知内容
1 HUP プロセスに再起動を通知する。
2 INT プロセスに割り込みを通知する。(Ctrl+c)
3 QUIT プロセスに終了を通知する。(coreを作成する)
9 KILL プロセスに強制終了を通知する。
15 TERM プロセスに終了を通知する。(デフォルト)
18 CONT プロセスに再開を通知する。
19 STOP プロセスに中断を通知する。
20 TSTP プロセスにサスペンドを通知する。(Ctrl+Z)


trapコマンド

trap コマンドは送出されたシグナルを捕捉し、あらかじめ指定されていた処理を実行するコマンドである。シェルスクリプトに対して送出されたシグナルは trap コマンドで捕捉できる。実行中のシェルスクリプトに対して送出されたシグナルは、trap コマンドを使用することで捕捉することが可能である。

kill コマンドなどによりシグナルリストに指定されたシグナルが送出されると、trap コマンドはそれを捕捉し、指定したコマンドを実行する。trap コマンドを使用することにより、各シグナルの規定の動作を置き換えることができる。ただし、強制終了のシグナルである9番は trap することはできないので注意が必要だ。

マージソートを実装

use strict;
use warnings;
use utf8;
use Data::Dumper;
use Time::HiRes qw(gettimeofday tv_interval);
binmode(STDOUT, ":utf8");

&main;

sub main {
    my $t0 = [gettimeofday];

    my $arr_size = 10;
    my @arr_elements = (8, 5, 9, 2, 6, 3, 7, 1, 10, 4);
    &merge_sort(\@arr_elements, $arr_size, 0, $arr_size);

    $\="\n";
    print @arr_elements;
    my $timer = tv_interval($t0) * 1000;
    print "$timer ms";
}

sub merge_sort {
    my ($arr_elements, $arr_size, $left, $right) = @_;
    
    if ($left + 1 < $right ) {
        my $mid = ($left + $right) / 2;
        &merge_sort($arr_elements, $arr_size, $left, $mid);
        &merge_sort($arr_elements, $arr_size, $mid, $right);
        
        $left = int $left;
        $right = int $right;
        $mid = int $mid;

        &merge($arr_elements, $arr_size, $left, $mid, $right);
    }
}    


sub merge {
    my ($arr_elements, $arr_size, $left, $mid, $right) = @_;
    
    my $n1 = $mid - $left;
    my $n2 = $right - $mid;
    
    my @left_arr;
    my @right_arr;

    for (my $i = 0; $i < $n1; $i++) {
        $left_arr[$i] = $arr_elements->[$left + $i]; 
    }
    for (my $i = 0; $i < $n2; $i++) {
        $right_arr[$i] = $arr_elements->[$mid + $i]; 
    }
    
    my $i = 0;
    my $j = 0;
    
    $left_arr[$n1] = 10000;
    $right_arr[$n2] = 10000;
    
    for (my $k = $left; $k < $right; $k++) {
        
        if ($left_arr[$i] <= $right_arr[$j]) {
            $arr_elements->[$k] = $left_arr[$i++];
        } else {
            $arr_elements->[$k] = $right_arr[$j++];
        }
    }
}

素数3の配列をどう処理するかでかなりの時間を労した。いきなり要素数10の配列で試すのではなく、初めは要素数3の配列で試したりすることで問題を細かく切り分けて考えるのが大事だという教訓を得た。

「初めに配列を要素が1になるように分割して...」っていう解説がよくされているけど実際は添字足したり割ったりしているだけで要素1の配列を実際に作っているわけではない。

Linuxのファイルシステム

ファイルシステム

ファイルシステムとは、記憶装置に保存されたデータを管理し、操作するために必要な機能のことである。OSが提供する機能の一つで、ほとんどのOSはファイルシステムでファイルを管理している。

ファイル

ファイルとは、記憶装置に保存された情報のことである。ソフトウェアやユーザーが作成したデータ、HDDレコーダーに録画したテレビ番組や、DVDに焼かれた映画などもファイルに含まれる。普段、HDDレコーダーにテレビ番組を録画したり、再生したりするとき、気付かないうちにファイルシステムを使っているということになる。

ファイルシステムは、ファイルを操作するためのインターフェイスも提供している。ファイルを階層構造に格納してラベルをつけ、必要なときにファイルを使えるようにする。ファイルシステムがないと、データを正しく保存できなかったり、保存した位置がわからなくなる。

フォーマット(初期化)

ファイルシステムの機能のひとつにフォーマット(初期化)がある。フォーマット(論理フォーマット)とは、使用しているOSのファイルシステムに合わせて記憶領域を区切り、番号を設定することであり、データを消すことではない。フォーマットすることでその記憶装置が認識され、使用できるようになる。

クラスタ

フォーマットで作成する区切りをクラスタと呼ぶ。クラスタは、ファイルを保存するための最小単位で、クラスタのサイズが小さいほどディスクを無駄なく使うことができる。

Linuxファイルシステム

Linuxでは複数のファイルシステムが開発されており、 利用者は好きなファイルシステムを利用することができる。 ファイルシステムはモジュール化して提供されているため、 新しいファイルシステムを利用したい場合は、動的に組み込むことが可能である。

Linuxがサポートしているファイルシステムは /proc/filesystems という 仮想ファイルに一覧化されている。この仮想ファイルはテキストファイルなので、 vi や cat などで内容を確認することができる。

$ cat /etc/filesystems
ext4
ext3
ext2
nodev proc
nodev devpts
iso9660
vfat
hfs
hfsplus


ファイルシステムの構造

ファイルシステム内で領域を割り当てる基本単位を論理ブロックという。ディスクデバイスの連続する物理ブロックから構成される。

i-node

i-nodeはファイルシステムにおけるデータ構造である。1ファイル、ディレクトリごとにi-node tableの1エントリが使用される。i-node内には以下の情報が保存される。

ファイルの種類
オーナ(UID)
グループ(GID)
パーミッション
タイムスタンプ(ファイルに最後にアクセスした時刻/ファイルを最後に変更した時刻/ファイルの属性を最後に変更したした時刻)
ハードリンクカウント
バイト単位のファイルサイズ
ファイルに割り当てたブロック数
ファイルデータを保存したデータブロックへのポインタ

i-nodeでは、i-node内に保持しているデータブロックへのポインタによって、ファイルデータを持つデータブロックを特定する。この構造によってファイルは連続したブロックを保持する必要がなく、ディスクを効率良く使用することができる。同時にi-nodeサイズの固定化、複数のデータブロックにまたがる巨大ファイルサイズのファイルの格納が可能、小さなサイズファイルのファイルに対して低レイテンシでアクセス可能になった。

レイテンシー

レイテンシーとは、データの転送要求などのリクエストを発してから、リクエストの結果が返ってくるまでにかかる遅延時間のことである。例えばメモリやハードディスクなどの記憶装置からデータを読み出す場合には、命令を送ってから記憶装置におけるデータが記録された箇所までアクセスする時間と、記憶装置から読み出されたデータが命令の結果として返ってくるまで、わずかながら遅延時間が生じる。

仮想ファイルシステム

仮想ファイルシステム(Virtual File System)は、実際のファイルシステムの上位に位置する抽象化層である。VFSの目的はクライアントアプリケーションが様々なファイルシステムに同じ方法でアクセスできるようにすることである。例えば VFS を使うと、クライアントアプリケーションはローカルな記憶装置にもネットワーク上の記憶装置にも透過的にアクセスできるため、その違いを意識する必要がない。あるいは、WindowsMac OSUNIXといったオペレーティングシステム (OS) の違いを超えてファイルシステムの違いを意識することなくアクセスすることが可能となる。

VFSは、カーネルと実際のファイルシステムとのインタフェースあるいは規約を定義している。従って、その規約に従うことで簡単に新たなファイルシステムカーネルに追加することができる。規約の条件はリリースの度に非互換な変更を加えられる可能性があり、ファイルシステムは新たなリリースに対応するために修正を施したり、再コンパイルする必要がある。

ジャーナリングシステム

ジャーナリングファイルシステムとは、ファイルシステムの種類の一つで、管理領域を変更する際にジャーナルあるいはログと呼ばれる更新履歴を残すことで管理領域の破損を防ぐ機能を持ったものである。

通常のファイルシステムでは、ファイルを書き込んだり書き換えたりする際、ファイルシステムの管理領域(メタデータ)の内容を変更している最中に不意の電源断などのトラブルが生じると、管理領域の内容に矛盾が生じ、データへの参照が失われたり、復旧に膨大な時間がかかる場合がある。

ジャーナリングファイルシステムではいきなり管理情報(メタデータ)を書き換えるのではなく、一旦これから行う変更をジャーナルと呼ばれる特殊な領域に時系列で保存し、それから管理情報の書き換えを行う。操作中に障害が発生しても、ジャーナルの内容を参照すれば即座に変更の破棄あるいは復旧を行うことができ、管理領域の一貫性を保ちつづけることができる。

データベース管理システム(DBMS)のトランザクション処理などに類似しているが、あくまで管理領域のみを保護する機構であり、ファイルの内容(データ本体)の保全は行わないため、データの喪失を防ぐには他の仕組みを併用する必要がある。ジャーナリング機能を持つファイルシステムとしてはext3ext4、XFS、ZFS、ReiserFS、NTFSなどがよく知られ、高い信頼性が求められるサーバ用途などで利用される。

fsck

fsck(file system checkあるいはfile system consistency check)とはUNIXオペレーティングシステム (OS)でファイルシステムの一貫性を調査するためのツールである。sckは、OSがクラッシュするなどで正常にシャットダウンしなかった後に再起動すると自動的に実行される。 fsckには多くの場合、対話的に対応方法を聞きながら発見した問題を修復する機能も備わっている。

また、fsckは問題があるファイルシステムに対して管理者が手動で実行することもできる。 ただし,ファイルを破壊してしまう危険性もあるため、障害が発生した場合(特に論理障害である場合)は、可能な限りデータのバックアップを実施した上で行うことが重要である。

マウント

Unixでは全てのディスクやネットワーク上の記憶資源は一つのツリー構造の 中に展開される。ツリー構造は / を頂点として、枝分かれしており、 それぞれのディスク上のファイルシステムは全てこのツリー構造の中のどこかの 枝の中に組み込まれるようになっている。逆に、ディスク資源を利用可能に するためには、ツリー構造への組み込み作業が必要であり、これをマウント と言う。マウントすることで、OSがファイルシステムを介してストレージデバイス上のファイルやディレクトリを利用できるようになる。

パーティション

コンピュータのハードディスクのパーティション (Partition) とは、ハードディスクの記憶領域を論理的に分割すること、あるいは分割された個々の領域を指す。パーティションを作成することをパーティショニング (Partitioning) とも言う。パーティショニングは、ひとつのハードディスク上に複数のファイルシステムを持つことを可能にする。

物理ディスクとは別に、ハードウェアにリンクした管理単位を定義し、その管理単位でのアセスを制御することで、とあるパーティションで障害が発生しても、他パーティション及びハードディスク全体に被害が及ばないように、障害の局所化が可能となる。

固有パーティションにおいて、ディスクの空きが枯渇しても、全データ区分に影響が及ばないように局所化する事ができる。ただし、システム使用パーティションの一部においては、そのパーティションの残量が枯渇した場合、システム自体の動作が停止してしまうことがある。

用途によってパーティション分割する場合もある。例えば、ほとんど書き込まれることがないパーティションがあれば、それを読み込みのみを許可する状態で使用する(マウントする)ことも考えられる。小さなファイルを多数格納するファイルシステムは、パーティションとして独立させてiノードを多数にするような設定をすることもできる。


参考:ファイルシステムとは?今さら聞けない基礎知識とOSごとの種類|発注成功のための知識が身に付く【発注ラウンジ】

トランザクションのコミットとロールバック

トランザクション

トランザクション (transaction)とは「商品を渡して、代金を受け取る」のように「ここからここまでワンセット」な処理単位のことである。

コミット

トランザクションが成功すること、つまり整合性を保って資源を更新することを、トランザクションのコミットという。トランザクションをコミットするかどうか最終的に決定するトランザクション処理の区切りを、同期点という。資源は、同期点で更新する。

ロールバック

トランザクションが失敗して、トランザクションで更新するはずの資源の状態を、トランザクション開始直前の状態に戻すことを、トランザクションロールバックという。トランザクションをコミットできなかった場合や、処理の不整合を検出した場合には,これまでの処理をロールバックで取り消して、データの整合性を保つ。

トランザクションロールバックした要因はログに取得できる。ロールバック要因をログに取得するかどうか,トランザクション関連定義のtrn_rollback_information_putオペランドで指定する。

ローカルトランザクション

単一のリソース(コンピュータとかデータベースとか)が関わっているトランザクション)のみが関わっているトランザクションのことを指す。

グローバルトランザクション

「複数のリソース(コンピュータとかデータベースとか)が関わっているトランザクション」が「グローバルトランザクション」である。「分散トランザクション」とも言う。「ワンセットなトランザクションが複数のデータベース(とか)に分散される」のがグローバルトランザクションである。

グローバルトランザクションは複数プロセスで構成される。グローバルトランザクションを構成する各プロセスを、トランザクションブランチといいます。特に、トランザクションの開始を宣言したプロセスをルートトランザクションブランチという。

ヒューリスティックハザード

ルートトランザクションブランチがトランザクションブランチにコミットの準備を指示したあとで通信障害が発生して、ルートトランザクションブランチでの決着(結果)がトランザクションブランチに届かなくなることを、ヒューリスティックハザードという。

ヒューリスティック決着

ヒューリスティックハザードが起こった場合には、コマンドを使って、トランザクションブランチごとにトランザクションを強制的に決着できます。ルートトランザクションブランチの同期点処理を待たないで、コマンドでトランザクションブランチのトランザクションを強制的に決着することを、ヒューリスティック決着という。

コンパイラの内部処理

コンパイラの内部処理

コンパイラでは、字句解析、構文解析、意味解析、コード最適化、コード生成といったフェーズに分かれて順に処理が進む。

字句解析

字句解析とは、広義の構文解析の前半の処理で、自然言語の文やプログラミング言語ソースコードなどの文字列を解析して、後半の狭義の構文解析で最小単位(終端記号)となっている「トークン」(字句)の並びを得る手続きである。

例えば、ソースコード中の「let x := 100」という記述において「let」というキーワードや「100」という数字列は、それでひとつの意味を持つカタマリであり、それ以上細かく意味を持たない。このようなカタマリのことを「トークン」という。また let と x の間にある空白など一般に空白類は、意味があるとしても、それがないと繋がってしまう場合に切り離す以上の意味は普通は無く、構文規則には通常そういったものは含めない。

構文解析

構文解析とは、字句解析でできたトークンをもとに、意味のわかる形式(e.g. AST(Abstract Syntax Tree)) に変換することである。構文解析では、字句を意味がわかる木の形(構文木)にする。構文解析を行なうプログラムのことを パーサ(parser)と呼ぶ。

意味解析

意味解析は、ソースコード内に記述された変数の型や文(ステートメント)が言語の記述仕様に沿っているかどうかをチェックする。その後、コード生成、最適化の手順を経て目的プログラムが作成される。ここで得た情報は記号表として、ソースコードに使われる記号の意味を記録される。

コード最適化

実行時により早く実行できるように無駄をなくしたり、オブジェクトのコードのサイズをできるだけ小さくするように無駄をなくす処理をする。

コード生成

オブジェクトコードを生成する。

全探索アルゴリズムの実装

use strict;
use warnings;
use utf8;
use Data::Dumper;
use Time::HiRes qw(gettimeofday tv_interval);
binmode(STDOUT, ":utf8");

&main;

sub main {
    my $t0 = [gettimeofday];
    $\="\n";

    my $input_n = 5;
    my @n_nums_arr = (1, 5, 7, 10, 21);
    my $input_q = 4;
    my @q_nums_arr = (2, 4, 17, 8);

    my $result;
    for my $q_num (@q_nums_arr) {
        $result = &exhaustive_search_algorithm(0, $input_n, \@n_nums_arr, $input_q, $q_num);

        if ($result == 1) {
            print 'yes';
        } else {
            print 'no';
        }
    }
    my $timer = tv_interval($t0)."\n";
    print "$timer ms\n";
}

sub exhaustive_search_algorithm {
    my ($i, $input_n, $n_nums_arr, $input_q, $q_num) = @_;

    return 1 if ($q_num == 0);
    return 0 if ($i >= $input_n);

    my $num_diff = $q_num - $n_nums_arr->[$i];
    my $res = &exhaustive_search_algorithm($i + 1, $input_n, $n_nums_arr, $input_q, $q_num) ||
              &exhaustive_search_algorithm($i + 1, $input_n, $n_nums_arr, $input_q, $num_diff);
    return $res;
}

gdbを利用したデバッグの手法(c++)

gdbを使ってできること

デバッグされるプログラムを開発者の設定したブレークポイントで止めることができる。
プログラムが停止した時、この時のプログラムで発生している事柄を検査することができる。
動的に現在のプログラムの実行環境を変更することができる。


「-g」オプションを付けてビルドを行うことで、「gdb」でデバッグ可能状態にする。

$ g++ -g ソースコード名

gdbを立ち上げる。

$ gdb 実行ファイル名

ブレークポイントを指定する。

(gdb) b 行番号
(gdb) b 関数名
(gdb) b ファイル名:行番号

よく使うコマンド

(gdb) i b ブレイクポイントを表示
(gdb) d no 番号に対応するブレークポイントを削除
(gdb) l ソースコードを10行単位で表示
(gdb) info locals 現在実行しているプログラムの変数の値を表示
(gdb) p 変数またはその他の情報を表示
(gdb) whatis 現在の変数の型を表示
(gdb) c 現在のブレークポイントから離脱
(gdb) delete 全てのブレークポイントを削除

実行する

run

参考:
https://astaxie.gitbooks.io/build-web-application-with-golang/ja/11.2.html
GDB