A社の佐伯さんがのらりくらりと

A社の佐伯さんがのらりくらりと。インターネットと少しだけ生活のこと。

うろ覚えだった知識をまとめてみたよ【ソフトウェア編①】

学習エントリ。 全体的な知識の底上げをすべく、復習も兼ねてまとめてみる。

OSとは

OS（オペレーティング・システム）はコンピュータに関わる様々な装置を管理するソフトウェア。高性能なCPU、大容量のメモリ、ネットワークカードなどを管理するにはしっかりとした管理が必要

OSを表す用語
  • シングルタスク：同時に複数のプログラムを実行することができない。1つだけ。
  • マルチタスク：同時に複数のプログラムを実行することができる。OSによるタスク管理のおかげ。
  • リアルタイムOS：定められた時間内に処理を完了させる機構をもつOS。
  • シングルユーザ：OSを一つのユーザだけが利用できること。
  • マルチユーザ：OSを複数のユーザが利用できること。
  • CUI：コマンドラインを使用する形態。
  • GUI：ウィンドウやメニューを使用する形態。

代表的なOSはUnix系OS、Windows、MacOS、Android、iOS

OSの3大機能
  • タスク管理：CPUを休まずに働かせる為のスケジュール管理を行う
  • 記憶管理：メモリを有効に活用するための管理を行う
  • ジョブ管理：ジョブの実行に必要な資源の予約や開放を行い、効率よくジョブを処理する為の管理を行う。
タスクとジョブの違い
  • タスク：コンピュータから見た仕事の単位。1プログラムが1タスク。
  • ジョブ：人間から見た仕事の単位。料金の計算し請求書を発行する、など。大体複数のタスクが一つのジョブを作る。
カーネルとシェル

カーネル：OSの中核の部分。 シェル：ユーザが入力したコマンドを解釈し、カーネルに伝えるもの

記憶管理

メモリ領域を管理する。実記憶管理と仮想記憶管理がある。

実記憶管理

コンピュータに実際に搭載されている主記憶の領域を実記憶空間という。 固定区画方式：実記憶空間を一定区間のサイズに区切り、区間単位で領域を割り当てる。区間ピッタリのサイズなんてほぼ無いので、どうしてもあまりができちゃう→内部フラグメンテーション 可変区画方式：データひとつひとつに合わせた区画を用意する。しかし区画と区画の間に細かい未使用領域が出来てしまう→外部フラグメンテーション しかし可変区画方式においては、ある程度未使用領域が増えてきたら、これらをまとめる操作を行う。これをメモリコンパクションという。

メモリオーバーレイ

家電製品などには主記憶が少量しか搭載されていないこともある。例えば64kbとか。このシステムで100kbのプログラムを動かす技術をメモリオーバーレイという。メモリオーバーレイではプログラムを機能単位で分けて、必要なセグメントだけメモリに読み込む。しかし←は自分でプログラムする必要があるので、まあ手間かかる。

仮想記憶装置

主記憶の要領以上に領域が使えるようになる。

ページング方式

実記憶空間と違って、OSがプログラムに見せているメモリ領域を仮想記憶空間という。実記憶空間よりも大きいサイズの仮想記憶空間をみせることで、プログラムでは主記憶以上の要領のメモリ領域を使える。まあ実際はOSが実記憶空間をうまいことやりくりして、サイズの大きな仮想記憶空間が実在するかのように振る舞ってるだけだけど。ページング方式はそのやり方の一つで、仮想記憶空間と実記憶空間をページという単位で管理する。プログラムはページを指定して実行する。実行する前にページが実記憶空間にあるかチェックする。実記憶空間にないことをページフォルトという。その場合実記憶に入れる必要がある。入れることをページインという。ページイン時に実記憶空間に空きがない場合、いらないものをハードディスク装置に対比させる（ページアウト）

ページ置き換えアルゴリズム

ページアウトの際に、いらないのはどれかを選ぶアルゴリズム LRU：最後にアクセスしてから最も長い時間を経過しているものを捨てる FIFO：最初にページインされたページを選ぶ

スラッシング

実記憶空間（＝主記憶の容量）が極端に小さい場合、ページインとページアウトを繰り返してしまう。これをスラッシングといい、システム全体の性能が極端に低下しちゃう。スラッシングが発生した時は、プログラムの同時起動数を減らしたり、主記憶の増設などが必要。

参考

Amazon CAPTCHA

うろ覚えだった知識をまとめてみたよ【コンピューターシステム編】

学習エントリ。 全体的な知識の底上げをすべく、復習も兼ねてまとめてみる。

システムの形態の分類

処理形態による分類
  • バッチ処理：データをある程度蓄積、指定した時点で一括処理。途中で人間による入力を行わない。大量のデータを一括で処理。月ごとの売上計算や、毎日の集計などで使う。
  • オンライントランザクション処理：データが発生するその都度処理を行う。処理すべきデータは通信回線で送る。電車の座席予約、銀行のATMなど。
  • リアルタイム処理：センサの信号に瞬時に反応する。ロボットなど。
分担形態による分類
  • 集中システム：コンピュータセンタに汎用機を設置して、すべての処理はそこで行う。拠点にはアクセス端末がある。センタのみ管理すればいいので、セキュリティ、運用、データ管理は比較的容易だが、障害発生時にシステム全体が停止する。
  • 分散システム：処理を行うコンピュータを各拠点に設置。拠点間を通信回線で接続。障害発生時に影響が局所化されるのはいいことだが、運用、データ管理、セキュリティ管理が比較的困難。
  • クライアント・サーバシステム：分散システムの一部。処理を行うサーバと処理の依頼を出すクライアント。
クライアント・サーバシステム

以下例 * ファイルサーバ：ファイル管理、共有 * データベースサーバ：DB管理とアクセス * プリントサーバ：プリンタの共有とか * Webサーバ：要求に応じて処理（HTML返すとか） * メールサーバ：メールの送信 * DNSサーバ：ホスト名に合わせたIPアドレスを送信

3層クライアント・サーバシステム

3層アーキテクチャとも言う。普通のウェブアプリケーションシステムはこれっぽい。MVCみたいなものかも。 * プレゼンテーション層：ユーザインターフェースに関わる部分。データの入力とか結果の出力とか * ファンクション層：業務ロジックやデータ加工 * データ層：データベースへのアクセス処理

システム性能を測る

MIPS

Million Instructions Per Second その名の通り一秒間に実行できる命令数を百万単位で表す指標。 たとえば一秒間に100,000,000回命令を実行できるCPUのMIPS値は100である。

FLOPS

FLoating point Operations Per Second 一秒間に実行できる浮動小数点演算の回数を表す。スパコンの性能などを測るために使う。

スループット

単位時間あたりに処理されるコンピュータの仕事の量

レスポンスタイムとターンアラウントタイム
  • レスポンスタイム（＝応答時間）はコンピュータに処理の指示を出してから、結果の表示が始まるまでにかかる時間。オンライントランザクション処理システム、クライアント・サーバシステム、リアルタイム処理システムの性能を測る用途で使われる。
  • ターンアラウンドタイムは、入力を開始して結果の出力が完了するまでにかかる時間。例えばデータをDVDに書き込み、郵送でコンピュータセンタに送るとすると、帰ってくるまでのその郵送時間（システムの要素とは無関係）もターンアラウンドタイムに含まれる。主にバッチ処理システムに使われる。
ベンチマークテスト

測定用のソフトウェアを使用し、システムの処理性能を相対的に数値化

システムの信頼性を測るもの

RASIS

R：Reliability（信頼性）：壊れにくいか A：Availability（可用性）：正常に利用できるか S：Serviceability（保守性）：保守・修理がしやすいか I：Integrity（安全性）：不整合は発生しにくいか S：Security（機密性）：情報の漏洩や改ざん、破壊の対する強さ

MTBF と MTTR

MTBF（Mean Time Between Failure）：信頼性を測る。システムが故障すること無く動作する時間の平均値。 MTTR（Mean Time To Repair）：保守性を測る。修理に要した時間の平均値。

ちなみに可用性は稼働率で表せる。 稼働率　＝　MTBF/MTBF + MTTR また、故障率は 1/MTBF

バスタブ曲線

当たり前だけど故障率は時間の経過に伴って変化する。それをグラフ化したもの。システム運用初期段階は初期トラブルで故障率は高い傾向にある（初期故障）。その後は安定化する。この時の故障は偶発故障。システムの終末期は劣化、いわゆる寿命による故障が多くなる（摩耗故障）

複数の装置から構成されるシステムの稼働率

全体のシステムの稼働率は、各装置の稼働率を掛け合わせる

直列システム

システムを構成する複数の装置が正常に動作しているど、全体が正常に動作できるシステム。稼働率は単純に各装置の稼働率をかければよい。

並列システム

直列と違い、何台かが動いていれば問題なく動作する。 パターン①：すべてが停止してなければ（少なくとも１台動いていれば）よい場合 稼働率　＝ 1 - （全体が停止している確率）

パターン②：上記以外 全てのパターンの確率を合計する。

高信頼化技術

信頼性の高いシステムはフォールト・トレランスやフォールト・アボイダンスという考え方にもとづいて構築する必要がある。 信頼性の高いシステム＝24時間365日動き続け、故障しにくいシステム

フォールト・トレランス

障害が発生してもシステム動作を継続できるよう対策しよう！という考え方。 同じ役割の装置を複数用意し一つが故障しても残りで代替できるもの。こんな感じの構成を冗長構成という。

冗長化いろいろ

デュプレックスシステム：本番系と待機系を用意。通常は本番系を稼働。本番系に障害が起きた場合、待機系に切り替える。 デュアルシステム：複数系統を同時に稼働させる。お互いを常にチェックしている。障害発生時には診断プログラムを走らせて障害部分を特定、それを切り離し動作を継続。デュプレックスシステムよりも信頼性は高い（=壊れにくい）。

デュプレックスシステムには3つの待機システムがある ホットスタンバイ：利用者が気づかんくらいの時間で待機系に切り替える。本番系と同じOSやアプリケーションを常に最新にしてるから。 コールドスタンバイ：切り替えに時間がかかる。本番系と同じOSやアプリケーションをまずインストールする必要がある。 ウォームスタンバイ：↑ふたつの中間

フォールト・アボイダンス

各装置の故障率を低くして、そもそも障害を無くそうよ、という考え方。結構コストが高くなる。

それ以外

フェールセーフ：故障時にシステムを出来るだけ安全な方向へ！（システム停止もやむをえない） フェールソフト：故障した部分は切り離す。機能を低下させてでも、システムの動作の継続を優先 フールプルーフ：人為的なミスが無いような設計をしよう！って考え方（もし利用者が誤っても、異常が起きないような作りにしよう） フォールトマスキング：故障しても、それを表面に出さず外部から分からないようにすること。

参考

https://www.amazon.co.jp/%E3%83%8B%E3%83%A5%E3%83%BC%E3%82%B9%E3%83%9A%E3%83%83%E3%82%AF%E3%83%86%E3%82%AD%E3%82%B9%E3%83%88-%E5%9F%BA%E6%9C%AC%E6%83%85%E5%A0%B1%E6%8A%80%E8%A1%93%E8%80%85-%E5%B9%B3%E6%88%9028%E5%B9%B4%E5%BA%A6-%E6%83%85%E5%A0%B1%E5%87%A6%E7%90%86%E6%8A%80%E8%A1%93%E8%80%85%E8%A9%A6%E9%A8%93-TAC%E6%83%85%E5%A0%B1%E5%87%A6%E7%90%86%E8%AC%9B%E5%BA%A7/dp/4813265545www.amazon.co.jp

うろ覚えだった知識をまとめてみたよ【ハードウェア編②】

学習エントリ。 全体的な知識の底上げをすべく、復習も兼ねてまとめてみる。

メモリ

主記憶装置。データを保存する部品。ROMとRAMにわかれる

ROM（Read Only Memory）
  • 原則として読み出し専用
  • コンピュータの基本設定やBIOSの記録に用いられる
  • 電源を切っても内容は消えない（不揮発性）
  • USBメモリやSDメモリに使われる
  • アクセス速度（読み出しや書き込みの速度）はRAMより遅い
    RAM（Random Access Memory）
  • 読み出し、書込み可能なメモリ
  • プログラム実行や作業領域として用いられる（コンピュータの主記憶）
  • 電源を切ると内容が消える（揮発性）
  • DRAM : コンデンサを集積して作っている。主記憶に用いられる。低速・大容量。内容の保持のため、適度にリフレッシュが必要。
  • SRAM：フリップフロップというトランジスタ回路で作っている。高速・小容量。主にキャッシュメモリに使われる。

※コンデンサ：電気を蓄えることが出来る粒子

誤り制御

メモリに記録したデータは、外界からの電気ノイズなどが原因で内容が変化してしまうことがある。その修正技術が2つ。 * パリティ：1ビットの誤りを発見する技術。発見だけ？みたい * ハミング符号：1ビットの誤りを検出して、正しい値に訂正できる。2ビットの誤りを検出できる。

メモリの高速アクセス

CPUはメモリの10倍以上早く動く。この差を埋めるために「CPUがメモリになるべく速くアクセスできるような仕組み」が必要。その仕組がキャッシュメモリとメモリインタリーブ。

キャッシュメモリ

SRAMを用いた高速メモリのこと。CPU「内部」に取り付けてある。大きな容量を保存できない。頻繁にアクセスする部分のコピーをキャッシュメモリに置いておく。キャッシュメモリを用いる場合CPUの手順は以下

  1. キャッシュメモリに必要とするデータが存在するのかをチェックする
  2. 存在すればキャッシュメモリから取得する
  3. 存在しなければ主記憶装置から入手。入手したデータのコピーをキャッシュメモリに置く。その際キャッシュメモリが一杯の場合、最も不要と思われるものを捨てた上で保存する。

必要なデータがキャッシュメモリに存在している確率をヒット率という。 データを書き込む際にキャッシュと主記憶どっちに書き込むかによって、2つの方式がある。 * ライトスルー方式：キャッシュメモリと主記憶の両方に書き込む。けどそれだとキャッシュメモリの効果ない * ライトバック方式：とりあえずキャッシュメモリだけに書き込んでおく。それが追い出される時に主記憶に反映させる

メモリインタリーブ

当たり前だが、キャッシュを導入しても主記憶そのもののアクセス時間は短縮されない。それを短くする仕組み。具体的には主記憶は区間に分けて各区間に交互にアクセスすることでアクセス時間を短縮している。

参考

www.amazon.co.jp

うろ覚えだった知識をまとめてみたよ【ハードウェア編①】

学習エントリ。 全体的な知識の底上げをすべく、復習も兼ねてまとめてみる。

ハードウェアとは

ハードウェアとは、コンピュータを構成する要素の総称。処理・記憶・入力・出力それぞれ４種類の機能を持つ装置のこと。

CPUとは
  • コンピュータの頭脳みたいな
  • メモリから命令やデータを取り出して、それを実行し、またメモリに結果を格納する
CPUの動作
  1. 命令フェッチ：メモリから命令を取得
  2. デコード：取得した命令を解読。CPUのどの回路に動作させるか決める
  3. オペランドフェッチ ：メモリから処理対象のデータを取得
  4. 実行
  5. 結果の書き込み：結果をメモリに書き込む

これらの流れを命令サイクルという。オペランドは処理の対象となるデータ。命令もデータもとりあえずはメモリに置いてある。

CPUの構成要素

中でも重要な3点 * レジスタ ：メモリから取得した命令やデータ、計算結果を格納する変数みたいなもの。まずはこのレジスタに入れて、演算を行い、結果をレジスタに戻す。命令レジスタ、凡庸レジスタ、アキュムレータ、インデックスレジスタ、ベースレジスタなど * ALU：四則演算や論理演算を行う機構。 * デコーダ：命令レジスタが保持している命令を解読し、CPU内部のどの部分を動作させるか決める機能

クロック周波数

CPUが全体として正しく動作するためには、レジスタ、デコーダがタイミングをあわせて正しく動作する必要があり、そのタイミングを合わせるための信号がクロック。クロックを一秒間にどれくらい発生させるかをクロック周波数という（単位はHz）。一般的にクロック周波数が高いとCPUの動作は早くなる。3GHzのCPUなら、一秒間に約30億回のクロック。

CPUの構造

  • CISC：複合命令セットコンピュータ。高性能な命令を豊富に用意したCPU。 便利だけど、すべてをハードウェアでコントロールすることが出来ず、一部はソフトウェア（マイクロプログラム）で管理されている。そのため速度は若干遅い。

  • RISC：基本的な命令のみに絞ったCPU。CISCと違い、CPU内部の回路は単純なため、全てをハードウェアで管理（ワイヤードロジック制御）。動作は早い。

パイプライン制御とハザード

命令サイクルをプロセッサ内で複数のステージに細分化し、複数の命令を並列に実行することで命令を高速で処理できる様になった。ベルトコンベアのようなイメージ。これをパイプライン制御という。パイプライン制御を阻害する様々な要因がハザード。主に以下の2つ。 * 制御ハザード：条件分岐命令、ジャンプ命令の実行 * データハザード：直前の命令の実行結果を利用する

マルチコアプロセッサ

CPU本体の回路をコアという。ひとつのCPUに複数のコアがあるのでマルチコアプロセッサ。消費電力を抑えつつ、処理性能を高められるのがいいとこ。

機械言語とその命令の種類

機械語（アセンブラ言語）はCPUが直接理解できる唯一の言語。 * 転送命令：メモリ〜レジスタ間のデータの転送 * 演算命令：算術、論理演算 * 比較演算命令：大小関係の比較 * シフト演算命令：レジスタに格納されている数値の桁を移動する * 分岐命令：プログラムの実行順序を変える

機械言語命令の構成

命令部 オペランド部：処理対象のデータを指定。データが何番地にあるのか？その指定の事をアドレッシングモードという。

アドレッシングモード
  • 直接アドレス指定：オペランド部に書いてある数値が格納場所の番地であるとする
  • 間接アドレス指定：オペランド部に書いてある数値が有効アドレスがある番地を指している（有効アドレス＝データが格納させれている番地）。２回メモリにアクセスせにゃならん。
  • インデックスアドレス指定：インデックスレジスタとオペランド部に書いてある数値を足した値が格納場所の番地であるとする。配列のアクセスなどに使う。
  • ベースアドレス指定：ベースレジスタとオペランド部に書いてある数値を足した値が格納場所の番地であるとする。
割込み

割込みが発生するとCPUは処理を停止し、割込みの対応を行う。それが終わると停止したプログラムを再開する。 内部割り込み：プログラムを実行した結果として発生する割込み 外部割り込み：CPUに接続される周辺装置が状況により発生させる割込み

参考

www.amazon.co.jp

【アルゴリズムの勉強】Pythonでユークリッドの互除法を書いてみた

学習エントリ。

Pythonでユークリッドの互除法を実装する。

ユークリッドの互除法ってなんぞ

ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである

ユークリッドの互除法 - Wikipedia

# coding: utf-8

x = 108
y = 648

def gcd(x,y): 
	while y != 0:
		x , y = y , x % y 
	return x

print(gcd(x,y)) ##108

【アルゴリズムの勉強】Pythonで二分探索を書いてみた

学習エントリ。

Pythonで二分探索を実装する。

二分探索ってなんぞ

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである（O記法）。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度（奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個）の要素を無視することができる。

二分探索 - Wikipedia

# coding: utf-8
import math

example_list = [1,3,4,5,6,7,9,10,13,16,18,22,24,25,26] 
target = 22

def binary_search(list,taget): 

	result = -1
	left = 0
	right = len(list) - 1

	while left <= right:
		center = (left + right)/2
		if list[center] == target:
			result = center
			break
		elif list[center] < target:
			left = center + 1
		elif list[center] > target:
			right = center - 1

	if result == -1:
		return str(target) + "は見つかりませんでした"
	else:
		return "要素の値が" + str(target) + "のインデックス=>" + str(result)

    
print binary_search(example_list,target) #要素の値が22のインデックス=>11
メモ

・left,rightというリストの両端のインデックスを用意する
・targetの判定によって、centerを用いてどちらかを狭めていく
・targetを見つけたら処理をwhile文を抜ける
・最大まで狭めると処理を終了する
・結果を判定するための変数(result)は-1にしておく。result = 0だとtargetが1(indexが0)の場合に失敗になってしまう。


この前のマージソートのように再帰的に求められるかと思ったが、挫折した。こちらの書き方の方がシンプルで分かりやすい。

【アルゴリズムの勉強】Pythonで線形探索を書いてみた

学習エントリ。

Pythonで線形探索を実装する。

線形探索ってなんぞ

線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
{\displaystyle n} n個のデータから {\displaystyle m} m個のデータを検索する場合、 時間計算量は {\displaystyle O(nm)} O(nm)、空間計算量は {\displaystyle O(1)} O(1)必要となる。

線型探索 - Wikipedia

# coding: utf-8

example_list = [5,2,10,1,18,3,7,4]
target = 18

def linear_search(list,taget): 
	result = 0
	index = 0
	for x in xrange(0,len(list)):
		if list[x] == target:
			result = 1
			index = x
			break
	if result == 1:
		return str(target) + "はリストの" + str(index) + "番目にあったよ"
	else:
		return str(target) + "はリストには無かったよ"
    
print(linear_search(example_list,target)) ##18はリストの4番目にあったよ

楽に書けた
targetが複数あった場合の処理は別途必要