10/17~10/23 学習記録

10/17~10/23 学習記録

気づき、自分なりの新たな発見があった部分のみまとめてみます。
ある程度の分量を読んでから自分の言葉に直して書いているので間違いのある可能性があります。
もしお読みいただける場合はそちらにお気をつけください。

「コンピュータ、どうやってつくったんですか？　はじめて学ぶコンピュータの歴史としくみ」

コンピュータにとって表現しやすく、区別しやすい状態の数が2つ
→0と1に対応
電気：流れているかいないか
電圧：高いか低いか（どれぐらいで分けるかは場合による）
磁力：磁力の向きが変わるか変わらないか（垂直方式と水平方式があるらしい、詳しくは不明）
光（CDやDVD）：光を当てる強さと時間によって、原子が規則的に並ぶところと不規則なところを作れる。
　　　　　　　　　→光をよく反射するか光が散ってしまうか

電気信号で記憶されるメモリは電源を切ると失われる（揮発性）が、
磁力の向きや光の反射などで記憶される補助記憶装置は電源を切っても失われない（不揮発性）
ディスクのデータを使うときは一度電気信号に変えメモリーに転送し、プログラムカウンタでメモリーのアドレスを指定しないといけないためメモリーより処理速度が落ちる

コンピュータは二進法の数字で全てを表す。文字、画像、音など
フルカラーは3バイト、24桁→2の24乗で1677万7216色
音は波を一定時間（CDなら44000分の1秒）ごとに分けて値を読み取り、16ビットに収まるようにキリのいい数値に変える（量子化）
→元の波を完全には再現できない（デジタルの性質）
アナログ回線の電話では音を電気の波に変えるため、アナログをアナログのまま表現できるので情報が抜け落ちない。
自然界にはアナログ（連続的）な量が多く、それを数字で表現するのがデジタル（離散的になる）

バビロニア数字は60の累乗で桁上がり、空位を表す方法がある（アラビア数字の0と全く同じではない）

コンピュータ内部で計算はどうやって行なっている？
二進法の足し算はAND回路とXOR回路を組み合わせた半加算器（一桁）や半加算器2つとOR回路を組み合わせた全加算器（二桁以上）で行う。
全加算器を繋げればつなげるほど計算できる桁が増えていく

19世紀　ブールが推論の過程を計算で表す（and,or,not,xor）（命題の真偽を0と1に対応させた）
20世紀前半　リレーという部品が使われるようになる
リレー：電磁石によってスイッチを直接触らず操作できるもの
リレーが計算を表現できるということが重要（スイッチの入れる入れないを0と1に対応）

リレーから真空管、半導体へ
真空管では電流そのものをコントロール
→イギリスのColossus、アメリカのENIAC
コンピュータの計算の仕組みはあまり変わっていないが、性能とサイズは格段に違ってきている

リレーを使った計算機では人が穴あきカードでプログラムを機械に読み込ませながら計算するのでも大した速度の違いはなかったが、
真空管を使うようになって速度の差が無視できないほど大きくなった
→メインメモリにデータだけでなく命令も入れる（プログラム内蔵方式）によって速度が一気に変わった

万能チューリングマシン

「プログラムはなぜ動くのか」

CPUの内部は数百万から数億個のトランジスタで構成されている
トランジスタとはスイッチング機能と増幅機能を持つ電子部品

メモリーの格納場所はアドレスで区別するが、レジスタは名前で区別
プログラム内に条件分岐や繰り返しがある場合は、プログラムカウンタの値を任意のアドレスに設定して実現している
フラグレジスタは演算結果のアキュムレータや汎用レジスタの値が負、ゼロ、正のいずれかを記憶（オーバーフロー、パリティチェックの結果なども記憶）
プログラム中の比較命令はCPU内部では減算として処理されている

関数呼び出しはコール命令とリターン命令（スタックでやる）
マシン語命令はシンプル（データ転送、演算、ジャンプ、コール/リターン）

コンピュータにできる演算は論理演算（各桁を個別に扱う、not,and,or,xor)と算術演算（四則演算）の2種
論理演算はグラフィックスパターンなど
シフト演算
論理左シフト
空いた下位桁に0を入れる
算術左シフト
同様、値は2の（シフトする桁数）乗倍される

論理右シフト
空いた上位桁に0を入れる
算術右シフト
符号がある数値として扱う場合は、空いた上位桁に符号ビットを入れる
値は2のマイナス（シフトする桁数）乗倍される

コンピュータは少数の計算を間違える可能性がある（例：0.1を100回加える）
なぜなら10進数の少数の中に2進数で正確に表せないものがあるから
10進数で1/3が0.333…となるのと同様（循環小数）
→金銭の計算など正確さが求められる場合でなければ無視してよい？

コンピュータ内部での少数点数の表し方
倍精度浮動小数点数(64ビット)と単精度浮動小数点数(32ビット)
±m*n^e（m:仮数,n:基数,e:指数)
仮数部では小数点以上の値を1に固定する正規表現、指数部では中央の値を0としマイナスも表現できるようにするイクセス表現が使われる

複数バイトからなるデータをアドレスの上位から格納するか、下位から格納するかでビッグエンディアン、リトルエンディアンと呼ばれている

配列：同じデータ型の複数のデータがメモリー内に連続して並んだもの
先頭から通し番号を振り、それをインデックス（添字）とよぶ
インデックスとメモリーアドレスを変換する処理はコンパイラがやってくれる

1バイト型の配列なら、論理的な構造と物理的な構造が一致する
→メモリーの使い方の基本

スタック：LIFO(後入れ先出し）、一旦置いておく（Push,Pop)
キュー：FIFO(先入れ先出し）、待ち行列、同時に送られてくるデータを順番に処理など(EnQueue,DeQueue)
リスト：次の要素のインデックスも組み合わせて一つの要素とした配列、配列と比較して後から要素を追加、削除が楽
2分探索木：前の要素と次の要素のインデックスも組み合わせて一つの要素とした配列、データの探索が楽（2分探索）

キャッシュ：低速な装置のデータを高速な装置に保存しておいて、同じデータが必要な場合には高速な装置から読み出す
ちなみにキャッシュ（cache)は隠し場所という意味、現金(cash)ではない
キャッシュはブラウザなど様々なところで活用されている

仮想記憶：ディスクをメモリーの一部として使う、ページング方式とセグメント方式
ページング方式では実行されるプログラムを一定のサイズのページに分割し、
実行されるページをメモリーに読み出すページインと、実行されないページをディスクに書き込むページアウトする
セグメント方式では処理やデータの集合など意味のある単位で分割

ディスクの物理構造
ディスクを固定長の領域に分けるセクター方式と可変長の領域に分けるバリアブル方式がある
セクターがディスクを物理的に読み書きする最小単位となり、1セクター512KBが一般的(Windows)
Windowsが論理的に読み書きする最小単位はセクターの整数倍のクラスタ
同一のクラスタに複数のファイルは格納できない、できてしまうとどちらかだけの処理ができなくなるから
クラスタのサイズを小さくするとディスク全体の記憶容量が減る代わりに処理速度が向上する、大きくするとその逆

ファイルにデータが記憶される最小単位はバイト
さまざまな圧縮の方法
ランレングス法：データ*繰り返し回数で表す。繰り返しの多い画像データなどで効果を発揮、FAXの画像圧縮など。

モールス符号：1837年モールス考案、トンツーの短点と長点の組み合わせで表現。出現頻度の高いEは1ビット、Aは4ビット、低いCは9ビットなどで表す。

ハフマン符号化：圧縮対象ファイルごとに最適な符号体系を作り、それをもとに圧縮。ハフマン木を使う。

文書ファイルは完全に元に戻せる可逆圧縮が求められるが、画像ファイルは人間の目で見る分には良ければ完全に元に戻せなくても良い（非可逆圧縮）。
圧縮率や圧縮時間など必要に応じてさまざまな圧縮方法を選択する。

CPUは、そのCPU固有のマシン語しか解釈できない、種類が異なれば解釈できるマシン語の種類も異なる。
コンピュータの本体はCPUやメモリ、I/Oを介した周辺装置など機種ごとの違いがあるが、その違いを吸収してくれるのがOSである。

かつてはアプリケーションの機能の中に直接ハードウェアを操作する部分があったため、機種ごとに違うアプリケーションを買う必要があった。
現在ではアプリケーションはOSの違いに、OSはハードウェアの違いに対応すればよくなった。

BIOS（Basic Input/Output System)：ROMに記憶され、あらかじめコンピュータに内蔵されているプログラム
キーボードやディスク装置などの基本制御プログラムに加えブートストラップローダーを起動する機能を持つ
ブートストラップローダー：起動ドライブの先端領域に記憶されたプログラム、ディスクに記録されたOSをメモリーにロードして実行する。OSはOS自身を起動できないため。

コンパイラはソースコードとマシン語の対応表を持ってる感じ。ただし字句解析、構文解析、意味解析などを経てネイティブコードを生成する（詳しくは突っ込まない）
プログラミング言語の種類だけでなく、CPUの種類ごとに対応したコンパイラが必要

コンパイル後には拡張子.objのオブジェクトファイルができる。呼び出す関数など（外部シンボル）の処理内容が格納されたオブジェクトファイルとリンクさせて、EXEファイルができる。
スタートアップ：すべてのプログラムの先頭に結合する統一的な処理の書かれたオブジェクトファイル
ライブラリファイル：複数のオブジェクトファイルを一つのファイルにまとめたもの
標準関数：ライブラリファイルの形でコンパイラと共に提供される関数
スタティックリンクライブラリ：オブジェクトファイルの実体をライブラリファイルに格納
インポートライブラリ（ダイナミック）：実体がどこどこのファイルにあるという情報と、そのファイルが格納されているフォルダを参照する情報だけが記憶されているライブラリファイル

プログラム内の変数や関数のメモリーアドレスは実行するたび変わるが、それはどうやって示す？
EXEファイル内に変数や関数の仮のメモリーアドレスが与えられており、実行時に変換
EXEファイルの先頭に変換が必要な部分を示す情報を付加しておき、この情報を再配置情報という。

プログラムの実行時には一つのプログラムに対し、変数、関数、スタック、ヒープのためのメモリ領域が確保される。
プログラムは一般にデータと処理からなるが変数がデータを、関数が処理を表している。
スタックはコンパイラによって自動的に生成される。
ヒープは言語によるがガベージコレクションを自動で行なってくれない言語の場合はプログラムで明示的にヒープを解放しないと、処理の終了後もメモリ領域が確保されたままになってしまう（メモリーリーク）。

OSが存在していなかった時代はプログラマがハードウェアに対してあらゆる処理を行うプログラムを書いていた。
次に、OSの原型となるプログラムをロードする機能と実行する機能だけを備えたモニタープログラムが開発された。
モニタープログラムを利用しているうちに、キーボードから文字を入力したりディスプレイに文字データを出力などの複数のプログラム間で共通した部分があったため、基本的な入出力を行う機能を持ったプログラムがモニタープログラムに追加された。これが初期のOSとなった。
さらなるハードウェア制御プログラムや言語プロセッサなどが追加されていき、現在の形に近いOSが生まれていった。

OSがハードウェアを抽象化しているためアプリケーションを作るプログラマはハードウェアを意識しなくてよくなったが、トラブルに遭遇したとき解決できるくらいの知識は必要である。
システムコール：OSがハードウェアを制御するための関数やそれを呼び出す行為のこと

プログラミング言語の方では独自の関数名を使い、コンパイルする際にOSごとの違いに対して合わせる。
言語で直接システムコールを呼び出す場合は、OSごとに違うプログラムを書く必要が出てくる（移植性が悪い）

Windowsではかつてディスプレイの表示とプリンタの印刷のため別々のプログラムを書く必要があったが、WYSIWYGというディスプレイとプリンタをグラフィックスを出力する同等の装置として取り扱う機能によってそれがほとんどなくなった。

高水準言語ではバラバラにかかれた命令やデータは、アセンブリ言語ではそれぞれのセクションに分けて記述される
アセンブリ言語の特徴
ネイティブコードとは一対一に対応
構文にはAT＆T記法とインテル記法がある
ソースコードはネイティブコードに変換される通常の命令と、擬似命令というアセンブラに対する命令で表される
一行で「オペコード　オペランド」という構成でCPUに対する一つの命令を表す

関数を呼び出す際コンパイラが必要なスタックのサイズを決め、スタックに引数を格納し、またスタックに戻り先のアドレスを格納することで呼び出される前の状態に戻る
関数の中で宣言された変数は呼び出されている間だけ有効（ローカル変数）
関数の外で宣言→グローバル変数　変数のセクションに記述される
条件分岐や反復は比較命令とジャンプ命令によって書かれる
アセンブリ言語では条件が真ならジャンプするという表現しかできないため高水準言語に戻すとまぎらわしい表現になる

I/Oコントローラ（I/O)：コンピュータ本体と周辺装置の電気的特性を相互に変換するIC
I/Oの中にメモリと周辺装置の入出力のためのデータを一時的に保存できるメモリーがあり、それをポートもしくはレジスタと呼ぶ
それぞれの周辺装置に対しポートが必要で、ポート番号（I/Oアドレス）で識別される

IRQ(Interrupt Request)：現在実行中のプログラムをいったん脇に置き、他のプログラムを実行するための割り込み要求。どの周辺装置が行なったかは割り込み番号でわかる
複数の周辺装置から同時に割り込み要求が来る可能性があるため、I/OとCPUの間に割り込みコントローラと呼ばれるICがワンクッション入る
割り込み要求を受けると、まず現在のCPUのレジスタの値をメモリー上のスタック領域に退避させ、割り込まれた処理が終わると元の状態に戻される

DMA(Direct Memory Access)：CPUを仲介させずに周辺装置がメモリーと入出力を行う方法
DMAコントローラと呼ばれるICが周辺装置をDMAチャネルと呼ばれる番号で識別し、実行している
CPUを仲介する場合はPIO(Programmed I/O)と呼ばれる

VRAM(Video RAM)：ディスプレイに表示する文字やグラフィックスの情報を記憶するメモリー
MS-DOS時代はメインメモリーの一部がVRAMになっていた
現在では、グラフィックスボードと呼ばれる専用のハードウェアにメインメモリーとは独立したVRAMとGPU（Graphics Processing Unit)という画像表示専用のプロセッサが装備されている