[[講義日程-2008年度夏学期]]
** 計算システム論第二 [#l207d376]
- 担当：中村 宏 准教授
- 1.5単位
-- 数理：限定選択C
-- システム：限定選択B
- 10:15-11:45 工学部六号館 62講義室
-成績評価
--試験による。持ち込み不可~
出席は救済のみ
**試験関係 [#r560fa0d]
//-だれか過去問の答え作ってくれないかなぁ。
-不完全ですがversion2うp。授業を受けていない人も、一通りの感じは掴めると思います。誤植を指摘してくれる方を引き続き募集中(by sen)
--''第二問の(1)(ア)は、講義の定義からいくと、CPI＝(必ずキャッシュヒットする理想状態の)CPI＋キャッシュミスによるCPIの増加、なので、CPI＝1＋0.4×0.1×100＝5だと思うのですが、いかがですか？''
--''↑俺もそう思った。あと、第一問の(1)は空欄１が「PC <- PC+1」で、空欄２が「ACC <- ACC + IR[5:0]」であってる？''
--↑多分それであっています。それから、残りの答えはしばしお待ちを。(sen)
--''↑最初のを書いた人間です。ですよねー。第二問の(1)(ア)は５ですよね。そしたら、(1)(イ)は2.6になるんですよね＞＜ あと、第一問の(1)は、僕もそうだと思いました''
--↑を補足すると(1)(イ)はcycle time=1.25[nsec],miss penaltyは100/1.25=80サイクルだから
CPI=1+0.4×0.05×80＝2.6,実行時間は(2.6×1.25)/(5×1)＝0.65（35％削減）
//あと(2)(ｳ)で実行時間長くなったんですけど・・
-自分の計算だと4.96って正解の5に近い値になったのは偶然?(sen)
-第2問（ア）について。ミスペナルティ100nsだけど、実際には101nsかかって（理想状態で1命令1ns）、総クロック数は60/100*n+36/100*n+4/100*n*101=5*nだと思うの。
-(イ)については、ペナルティ100nsはかわらないままプロセッサクロックが変化したため、損をする計算時間は減る(100回から80回になる)ことに注意する。(tako)
-(ウ)では各々求めたCPI値(a,bとしよう)から以下の計算をすればOK。1GHzのsec/instructionが、1/1G * a sec/clk * clk/instで求められる。また、800MHzも1/800MHz * bとなる。これで、1命令あたり何秒かかったかが出ているので、(d,eとしよう) (d-e)/d とすることによって、そうすると、上の35%削減という結果の人と同じ式になるのでは。(tako)
-みんな名乗ろうよ(by sen)
**参考文献とその他役に立ちそうなもの [#qb7c25e0]
参考書。いわゆるパタヘネ本。
--Conmputer Organization & Design: The Hardware/Software Interface 3rd Edition
--[[コンピュータの構成と設計>"http://www.amazon.co.jp/コンピュータの構成と設計~ハードウエアとソフトウエアのインタフェース-第3版-上-デイビッド・-パターソン/dp/482228266X/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1208136403&sr=8-1/"]]
-[[MIPSシミュレータ>http://pages.cs.wisc.edu/~larus/spim.html]]
-[[講義ページ>http://www.hal.rcast.u-tokyo.ac.jp/~nakamura/keisan2/]]~
パスワードはお友達に聞いてね。
-[[九大の講義ノート>http://ocw.kyushu-u.ac.jp/0009/0006/lecture.html]]
-[[論理合成を忘れてしまった人はこちら>http://www.ssc.pe.titech.ac.jp/lectures/ComputerLogicDesign/CLD_matsu_051027.pdf]]
**内容 [#t7f6cf42]
物理的制約のもとで複数のシステムを有機的に組み合わせ，計測，認識，制御，知能などを実現する最適化されたインタラクティブな計算システムの構成理論と手法を学ぶ。
+計算システムのモデリング
+命令セットアーキテクチャ
+データパスと制御論理
+メモリシステム：キャッシュメモリ、仮想記憶
+入出力制御
+プロセスの管理
+フォールトトレラントシステム
**授業ノート [#ra620884]
Presented by sen. tzik all blame reserved.~
誤植は見つけた人が直すものです
+計算システムとは
--目的に応じて
--ハードウェアとソフトウェアを組みあわせて構成~
目的によってさまざまな構成がありうるが、基本は同じ。
++ハードウェア構成(p2,3)
--CPU(Central Processing Unit) ,Processing Unit(PU) + 主記憶
--出入力装置
--補助記憶装置(HDDとか)
--プロセッサの速度はムーアの法則に従って増加するのに対し、記憶装置や入出力の速度は相対的に遅く、そこがボトルネックになっている。それを解決するための手法が最近のプロセッサには取りいれられている。(キャッシュとか)。たとえば、HDDの読み込み速度はCPUの100万倍くらい遅い。~
でも、基本的な部分は変わってないよ。
+システム設計の階層
-プログラムの構成
--高級言語(C,C++) → コンパイル → a.out(バイナリ)
--高級言語による設計の時には、下位レベル(ハードウェアのこと)を考える必要はない
++概念レベル(仕様書、頭の中)
++高級言語レベル(C,C++) ハードウェアに非依存
++機械命令レベル(PU依存)
++レジスタトランスファレベル
++ゲートレベル
++スイッチレベル
iii.までがソフト屋さんの仕事。ここが変わるとソフト、ハード両面に影響が出るので設計はとても重要。~
ivはレジスタ間の転送をハードウェアで実現する手法を規定~
VHDL,Verilogとかのハードウェア記述言語を使う。~
データパスと制御論理~
~
v.は第一でやったところ~
vi.はトランジスタの話。基本的にはこのあたりを気にする必要はあんまりない。
+階層設計に関する検討
1つのシステムがとても複雑になってきている。~
→設計の見通しの良さ~
設計が階層化されていれば、バグが生じたときに1つだけ上の階層に戻ってやり直しができる。~
→最終的な品質(製品としての性能と設計期間)
+セマンティックギャップ(semantic gap)~
高級言語の機能と、ハードウェアで実現されている機能(アセンブラ)のレベルのギャップが大きい。~
高級言語マシンというものが、今から20年くらい前にはさかんに研究されていた。~
RISC(Reduced insttuction set computer)~
→ハードウェアで実現する機能、命令は簡単なものでも良い。~
''プログラムの実行時間=(プログラムあたりの命令数)*(1命令あたりの実行時間)''~
高級言語マシンでは、1↓ 2↑~
RISCでは1↑2↓~
RISCでは単純な命令だけにして命令セットの数を減らすのが目的→複雑な動作をするためには命令数が増えるが、一つ一つの命令を早くすることで解決する
'(1命令あたりの実行時間) = (1命令あたりの所要サイクル数)*(サイクル時間)'~
単純な命令を繰り返すもののほうが、流れ作業に向いている。面倒なのでウィキペとか参考書とかを参照([[パイプライン処理>http://ja.wikipedia.org/wiki/パイプライン処理/]])
//中村先生… とても、ノートが取りにくいです…
//番号付きリストがうまく表示されないので、あとで書きなおす
//とても、眠いです…
+ハードウェア/ソフトウェア協調設計
例えば、組み込みとか、ちょっと凝った処理をしたいときにプロセッサを設計することはよくある。(携帯電話であればコストダウン、数値計算だけに特化したスパコンを作るetc.)一般的に、ハードウェアでやることを増やすと性能はあがるが、コストも増える。ハード/ソフトの協調設計ではこのトレードオフになる。どうするのがいいかはお金と時間による~
{ハードウェア|ソフトウェア}で実現する機能の決定。
//ハニョンハニョン
2.命令セットアーキテクチャ
2.1命令(instruction)
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
0.25 * 0.5 = 1.25(%)
PUが処理すべき動作を指示
命令セットアーキテクチャ(instruction set architecture)~
→命令の体系、ハードウェアとソフトウェアのインターフェイス、計算機構成の重要な抽象化レベル
命令の種類
-算術演算命令(加算、減算etc.)
-論理演算命令(and,or)
-データ転送命令(メモリなどとの間でデータを転送)
-分岐命令(if文のようなもの)
命令語(instruction words)~
命令を表現するword(バイナリ)
//MIPSの命令一覧を探したけど、見やすいのが無かった…
MIPSの命令については、これが分かりやすいかも~
http://ocw.kyushu-u.ac.jp/0009/0006/lecture/10.pdf
2.2 主記憶のアドレシング~
PUのレジスタは数十個(MIPSの場合は32ないし64個)なので、メモリからデータを読みこむ必要がある。図はめどいので教科書とかを参考。
アドレス付けの単位
-バイトアドレシング → 1つの番地で、1バイト管理
-ワードアドレシング → 1つの番地で、1ワード(4bit)管理
主記憶のサイズ~
プリント2^32=2^32バイト(32bitアドレス空間) →4GB~
最近はこれじゃ足りないので、64bitアドレス空間を使っているもの増えてきた。
命令セットアーキテクチャ
プロセッサAからプロセッサBへ。~
今までのソフトウェアが動くか？~
そもそも同じなら、完全互換。命令を追加した場合は上位互換。Intelのx86は、上位互換を維持するために、複雑怪奇な命令セットになっているのだとか…~
エンディアン(Endian)
-big endian
-litte endian
数値データを置く場所がどちらへ進んでいくか？ ~
数値データのMSD(most significant digit)をアドレス番号の小さい方に対応させるのがbig endianで、LSD(least significant digit)をアドレス番号の小さい方に対応させるのがlitte endian。互いにデータのやりとりをしなければ何も問題はない。 mipsはどちらにも対応していた(はず)
命令セットの違いはソフトウェア側でなんとかなる。でも、アドレスづけの単位やらエンディアンの違いは、どうにもならないこともある。
2.3命令セットアーキテクチャの分類
用意されているオペレーション(操作)の種類による分類ではなく、利用できるオペランド(操作対象)に大きく依存
+PU内部のオペランド指定方式
+主記憶のオペランド指定方式
2.3.1 PU内部の記憶部
-スタック(stack)
-アキュムレータ(accumurator) ←レジスタが一つしかないと思えば良い。
-レジスタ(register) ←最近の汎用プロセッサはこれ
詳細はググれカス(by 中村先生)
4/28
2.3.2 汎用レジスタ方式における記憶部の指定方法~
(1)regiaster addressing~
レジスタを指定する~
add r1,r2,r3 # r1 <= r2 + r3
(2)immediate addressing(直値) ~
オペランドの値を指定する
add r1,r2,1000 # r1 <= r2 +1000
(3)direct addressing~
主記憶のアドレスを直接指定
(3-1) register~
load r1,(r2) # r1 <= mem[r2]
主記憶のアドレスを保持するレジスタを指定する
(3-2) immediate~
load r1,(1000) # r1 <= mem[1000]
主記憶のアドレスを直接指定する
(3-3)index~
load r1,24(r2) # r1 <= mem[r2+24]
レジスタとオフセットで指定
(4)indirect addressing(間接参照)
-主記憶のアドレスを間接的に指定
-主記憶のアドレスを保持する別の主記憶のアドレスを指定する
(4-1)register~
load r1,@(r2) # r1 <= mem[mem[r2]]
(4-2) immediate~
load r1,@(1000) # r1 <= mem[mem[1000]]
(4-3) index
load r1,@24(r2) # r1 <= mem[mem[r2+24]]
2.4 RISC(reduced instruction set computer)~
命令セットアーキテクチャの1カテゴリ。明確な定義はないが、一般的に次のような特徴を有するものがRISCと呼ばれる。
-命令長が一定
-論理、算術命令のオペランドはレジスタのみ
-ロードストアアーキテクチャ~
主記憶のデータはロード命令、ストア命令のみで操作
lw $1,4($2)
add $1,$1,1
sw $1,4($2)
などという形で書かなければいけない。
-単純なメモリアドレシング(indirect addressingはない)
RISCの方針~
命令を単純化して、命令数は増加しても命令当りの処理時間を短くすることで、全体jの処理を高速化する。(また、命令形式が単純であることはパイプライン処理のし易さにも影響する)
処理時間 = (命令数)*(命令あたりの処理時間)~
このあたりは、後でパイプラインやらないと分からないかも
3.データパスと制御論理~
データパス(data path)~
所望の処理を実現するためのデータが流れる経路
//http://urasoku.blog106.fc2.com/blog-entry-368.html
//てらえろす
-レジスタ等の記憶装置
-算術論理演算回路
-その間の相互接続
//たぶん、図が多くなって書けなくなるとおもうのでぐぐってくれ。もしくは教科書を勝ってくれ
制御論理~
所望の処理を実現するために、データパス上のデータ転送を制御する論理。データパス上のタイミング制御も含む~
有限状態機械(Finite State Machine)で表現することが多い
実現方法:wired logic(有線論理)→FFと組合せ回路
3.1データパス~
(1)構成要素~
演算器、マルチプレクサ、レジスタ、メモリ~
(1-1)演算器:複数の入力に対し、制御信号で指定される演算を行う。
(1-2)マルチプレクサ~
複数の入力に対して、制御信号で指定された入力を選択して出力(selecter)
(1-3)レジスタ:記憶部
機能的にはD-FFと類似だが、N-bitデータを扱う。制御信号(write enable)がある。MIPSの場合は32bit
(1-4)レジスタファイル
M個のレジスタを扱う。入力出力をどれだけ許すか？~
最低、2入力1出力(そうじゃなきゃ演算ができないから)
3.2制御論理~
所望の動作をデータパス上で実現するための論理
(1)wired logic(布線論理)による方法。ハードウェア(FFと組み合わせ回路)で実現~
高速だが設計は大変~
(2)マイクロプログラムによる方法。命令より一段下のレベルのマイクロ命令によってプログラム的に記述。~
設計変更は容易だが、低速
3.3データパスと制御論理の設計~
「全ての命令の動作を実現するハードウェア」~
(1)各命令の実行ステージの分割~
いくつ？ 各ステージの動作は？~
ステージ：1サイクルに対応
(2)前項を満たすデータパスの構築~
該当するデータパス上で、各ステージの動作を実現する制御論理の仕様を、状態遷移図で表す。
(3)データパスはゲートレベルスイッチで対応~
制御論理は状態遷移図で与えられているので、前述の二つの方法を用いて落としこむ。
1,2レジスタトランスファレベル設計
6/2
4.メモリシステム~
4.1 キャッシュメモリ~
4.1.1 概念~
キャッシュ：大切なものを隠しておく場所~
方針：高速かつ大容量な記憶装置が手に入ればいいのだが、一般的に高速な記憶装置ほど高価で、容量も少なくなる。そのため、プロセッサに"近い"場所に高速だが容量の小さいメモリを配置することで処理の高速化を図る。~
根拠：局所性(locality)~
時間的局所性~
ある情報が参照されると、すぐ後にまた参照される傾向がある。
空間的局所性~
ある情報が参照されると、近くの情報も参照される傾向がある。
-用語
キャッシュヒット~
参照される情報がキャッシュにあること~
キャッシュミス~
参照される情報がキャッシュにないこと~
ヒット率~
参照時にヒットである割合~
メモリアクセス時間~
= (ヒット率) * (キャッシュアクセス時間) + (ミス率) * (主記憶アクセス時間)
高速化~
キャッシュをどう構成させるか？~
-ヒット率を上げる
-キャッシュアクセス時間を短縮する
4.1.2 主記憶とキャッシュのアドレスマッピング~
メモリからキャッシュへ持ってきたデータをどう配置するか？
(1)direct mapping(ダイレクトマップ方式)~
主記憶のコピーの格納場所は、キャッシュ上で一意に定まる。~
(2)fully associative(フルアソシアティブ)
主記憶のコピーの格納場所はキャッシュ上の任意の場所~
(3)N-way set associative(n-ウェイセットアソシアティブ)
主記憶のコピーの格納場所は、キャッシュ上でN通りある。~
キャッシュ上でデータを探す時間とキャッシュの使い易さのトレードオフ
4.1.3 キャッシュの構成と制御(p21)~
(1) ダイレクトマップの例~
ブロックサイズ4B,容量4KB~
(1-1)キャッシュの構成~
ブロック数：1024~
ブロックのデータ部：4B~
index：キャッシュブロック番号
V:当該ブロックが有効かどうか？
tag：当該ブロックに格納されているデータのアドレス~
data:当該ブロックに格納されているデータの本体~
(1-2)メモリ参照時のアドレスビットの意味~
32bitのアドレス空間~
offset部：アドレスの下位2bit[1:0]
→ブロック内のオフセットを定める
index部：アドレスの次の下位10bit[11:2]
→参照すべきcache indexを定める
tag部：上位20bit[31:12]
→tag部と比較される
(1-3)読み出しと参照の動作~
(1)参照すべきアドレスのindex部からcache index を決定し、tagを参照~
(2)キャッシュ内のtag部と、参照すべきアドレスのtag部が一致するかを比較
-不一致 → キャッシュミス
-一致
--有効ビット →キャッシュヒット
--無効ビット →キャッシュミス
(3)キャッシュヒット時~
キャッシュのデータ部から所望のデータを読みだす
キャッシュミス時~
主記憶にデータを読みにいく
-参照されるデータを含む1ブロック分のデータを主記憶へ持ってくる
-現在のキャッシュの当該ブロックを破棄して、新しいデータをキャッシュのデータ部へ格納、キャッシュのタグを更新
//6月16日 遅刻した
4.2.仮想記憶(virtual memory)~
4.2.1 概要~
物理的には小容量しかないメモリを仮想的に大容量のメモリとして提供する方法~
OSの管理下で、ハードウェア機能のサポートにより限られた容量の主記憶と、大容量の2次記憶からなるメモリ階層構成において、大容量の主記憶を仮想的に(論理的に)実現
-キャッシュと仮想記憶の対比
○ キャッシュ 仮想記憶~
制御単位 ブロック(固定、32Bから256B) ページ(固定:4KBから) セグメント(可変)~
入れ替え制御 ハード ソフト~
(1)原理~
主記憶の記憶領域が不足したら不要な主記憶の一部を2次記憶へ追い出し、主記憶上に新しい領域を確保する。~
swap in : 2次記憶から主記憶へ~
swap out: 主記憶から2次記憶へ~
(2)アドレス空間~
論理アドレス空間(logical address space)~
ユーザプログラムが実行されているアドレス空間(仮想アドレス空間とも言う)
物理アドレス空間(physical address space)~
主記憶上で実際に提供されているアドレス空間(実アドレス空間とも)
(3)制御の概略~
1.PU上でメモリアクセス実行~
2.論理アドレス→物理アドレスの変換(DAT:dynamic address translation)を変換表を用いて行なう。~
3.変換可能→物理アドレスを用いて主記憶アクセス~
変換不可→該当論理アドレスは主記憶にない。~
→割り込み発生(ページフォールト)~
→OSに制御が渡る→OSがswap in/out を行なう。
4.2.2 アドレス変換方式~
アドレス変換の単位:ページ(固定) / セグメント(可変)
(1)ページング(paging)~
1953(英マンチェスター大)
プリント22p
-変換方式~
論理アドレス~
ページ番号とページのオプトからなる。~
論理アドレスのページ番号を物理アドレスページ番号へ変換
(2)セグメンテーション~
1961(米Burroughs社)
主記憶に置く単位をプログラムの論理的に独立した単位(セグメント)とする方式。セグフォの名前はここから来ている。
ページングとの違いは多きさが可変であること
-長所 セグメントは属性が明確。記憶保護に最適~
-短所 外部フラグメンテーションが生じる~
→ページ化セグメント(paged segment)などがある
//前回senは休んでいました
// 6/30
5.入出力制御~
5.1 入出力制御方式~
1.特別なI/O方式~
アドレスとは別
2.address mapping I/O~
あるアドレスへの読み書きを入出力として扱う。
5.1.2 入出力装置からの通知検出方法
1.ポーリング方式~
CPUが定期的にI/Oデバイスを監視する。頻度が高ければ応答性も良くなるが、監視のオーバーヘッドも増加
2.割り込み方式(次でまたやる)
デバイス手動で、終了を割り込みで通知する。
割り込みを(ハードウェアが)検出すると、OSへ制御を渡して割り込み処理を行う。~
ポーリングとは逆に、監視のオーバーヘッドは無いが、プロセスの切り替えに時間が必要
。
5.1.3 データ転送を行う主体による分類~
(1) プログラム制御方式~
CPUがプログラムモードの入出力命令によって、入出力装置を起動。~
入出力命令実行中はCPU動作が中断するため、大量のデータ転送時はシステムの効率低下。(それゆえ、あまり使われない)
(2) DMA制御方式(direct memory access)~
CPUとは独立に、主記憶と入出力装置のデータ転送を行う機構。CPUは入出力処理からは解放される。
(step1) CPUは入出力装置のID、実行すべき処理、転送先/元の開始アドレス、転送量をDMAに通知。DMAの起動(DMA kick)~
(step2) DMAはバスの調停と入出力装置における処理を開始~
(step3) DMA転送が終了したら割り込みで通知~
例題. ポーリングと割り込み
一回のポーリングに400サイクル、CPU 500MHz
4words(16B毎)転送が行われ転送性能 4MB/sec のディスク
データが失われないようにポーリングで検出する場合のポーリングのオーバヘッドは？
解.
(1) 必要なポーリングの頻度
4MB/16B = 250k(回/sec)
1秒あたりのオーバヘッドは
400 * 250k = 100Mサイクル
100M/500M = 20% のオーバーヘッド
(2) 割り込みの場合
一回の割り込み処理に、500サイクル要する場合
オーバーヘッドは？
割り込み頻度はポーリングと同じく250k
オーバーヘッドは (250k * 500サイクル)/500Mサイクル = 25%
(3) ディスクの入出力処理は全体の5%だけである場合
(3.1)ポーリング
変わらず 20%
(3.2)割り込み
// 0.25 * 0.5 = 1.25(%)
25 * 0.05 = 1.25(%)
(4)DMA転送のオーバーヘッド
同じディスク
DMA転送のsetupに1000サイクル
DMA転送の終了の割り込みに5000サイクル
平均転送サイズ 8KB
このときのオーバーヘッド
ディスクは100%active
4MB/8KB = 0.5k(回/sec)
1回のDMA転送のオーバーヘッド
6000サイクル
(6000 * 0.5)/500M = 0.6%
5.2 割り込み~
不定期に起こる事象に対して、プログラムの実行を中断してしかるべき処理をすること。
5.2.1 割り込みの種類
-入出力割り込み~
キーボード、マウス
-システムコール割り込み
システムコールの発行(標準出力へ表示など)
-プログラム割り込み(ページフォールト、異常実行(0割り))
-外部割り込み(リセット)
precise/imprecise
正確な割り込み(復帰再開可能)
不正確な割り込み(復帰再開不可能)
-precise~
割り込みを発生させた命令以前の命令は終了し、割り込み処理後の再開で正しい結果が得られる。~
→ページフォールトはpreciseであるべき~
~
0除算：impreciseでも良い~
preciseの割り込みは思いの他大変
5.2.2 // 6/30
5.2.2 割り込み処理方式~
割り込みの受付は命令単位
+割り込みを受け付けるかを判断(優先度がある場合)
+CPUは実行中のプロセスを中断し、再開に必要な情報(PC、レジスタの値など)を退避する。
+割り込みベクタを参照し、指定されている値をPCに設定~
=割り込み処理ルーチン 割り込みハンドラに移行 OSに制御が移行
+処理が終了したら、退避情報を復元して処理を再開
6.オペレーティングシステム(Operating system)
ユーザとハードウェアシステムのインターフェイス~
=ハードウェアの仮想化
6.1 役割~
+資源管理
--ハードウェア資源
---PU,主記憶,ディスク等の資源
--ソフトウェア資源
---プログラム,データ等の資源
---パーミッションの管理なども
+利用者インターフェイス
ハードウェア資源の特性を抽象化して、ユーザに提供~
特性に応じて最適化をすることができない
+運転管理とRAS~
RAS~
R:reliability
A:availability
S:serviceability
→高信頼性が要求されるシステム(銀行のオンラインシステム)では重要
6.2 プロセス管理とスケジューリング~
6.2.1 プロセス(process)~
OSからハードウェア資源の割り当てを受けて処理を実行しているプログラム。~
(Linuxだとpsコマンド、Windowsではタスクマネージャで見られる)~
6.2.2 プロセスの状態と遷移~
(1)プロセスの状態
-実行状態：プロセスにCPU資源が割り当てられている
-実行可能状態：CPU資源は割り当てられていないが、割り当てられれば実行可能
-待ち状態：何らかのイベントを待っている状態
図が書けねー
・遷移状態~
1.初期状態：新しいプロセスが生成されると実行可能状態に~
2.実行可能状態→実行状態~
CPU資源が空いた時にスケジューリングアルゴリズムに従って、1つのプロセスが選択され、CPU資源を割り当てる。~
3.実行状態→実行可能状態~
特定のプロセスがCPU資源を占有するのを避けるために、あらかじめ決められた時間(タイムスライス)を実行状態プロセスに割り当てタイムスライス終了時に実行可能状態に遷移(タイマ割り込み)
・プロセスの管理と切り替え~
OS内では、
-親プロセス/子プロセスへのポインタ
-プログラムのコード領域とデータ領域へのポインタ
-プログラムカウンタ、レジスタの退避領域
-メモリ管理状態(ページテーブルへのポインタ)
などを管理
プロセス切り替え時に必要な処理~
再開に必要な処理の退避~
CPU資源内にあるプロセスの情報、プログラムカウンタ、レジスタの値は必須
6.2.3 スケジューリングアルゴリズム~
スケジューリング~
今回はCPUスケジューリング
スケジューラの評価基準
-CPU利用率
-ターンアラウンド時間 プロセスの実行要求から、実行までの時間
-待ち時間 プロセス完了までに、実行可能状態のキュー(待ち行列)で待つ時間
-応答時間
//senの遅刻によりぐぐれかす
7.フォールトトレラントシステム
障害に対して強いシステム
-故障(fault)
-fault avoidance と fault torerance
-fail safe ,fail stop
ユーザの期待するサービスを提供できないときシステムが機能を失うか安全な状態で停止する。
-fail soft
ユーザが期待するサービスが提供できないとき、性能を落としたサービスを提供する
7.2 評価尺度~
応用分野によって必要となる信頼性は異なる。趣味の自宅鯖だったらいくら落ちても問題ないし、生命に関わるシステムだったら高い信頼性が必要。
-信頼性
どれだけの時間障害を発生させずにサービスを提供できるか
-可用性
使いたいときにサービスが提供される確率
-保守性
修理のしやすさ、迅速さ
例えば、何十年も宇宙にあって簡単に修理のできない人工衛星だったら信頼性を高め、保守性は少し無視してもいい。飛行機だったら、最低限飛行中の20時間ほどの間に故障を起こさなければよく、修理をすれば良いとか。
7.2.1 フォールトカバレッジ(fault coverage)~
対象とするフォールト集合が現実に起こりうるフォールト全体のどの程度を包含するか。
計算システムにおけるフォールトの分類
-accidental fault(偶発的)
-physical fault(物理的)
--内部要因
--外部要因
-human fault(人為的：うっかり)
-malicious fault(人為的：故意)
-故障検出~
信頼度は故障検出能力に大きく依存
評価モデル~
どういう故障が起こるかの抽象モデル~ 良いモデルは、カバレッジ大、検出に必要な時間やコストが低い
7.2.2 信頼度(rliability)~
障害発生を統計的分析を持つ確率事象として扱う。
f(t) 障害が生じる確率密度関数~
時刻tからt+dtの間に障害が生じる確率はf(t)dt
0からtの間のtauで障害が発生する確率F(t)
#mimetex(F(t) = \int^t_0 f(\tau)d \tau)
逆に時刻tまで障害が発生しない確率は
#mimetex(R(t) = 1 - F(t))
-障害率 lambda(t)~
時刻tまで無障害という条件の元で、tからt+dtに障害が起きる確率 lambda(t)
#mimetex(f(t) = R(t)\lambda(t))
#mimetex(R(t) = 1 - F(t))
#mimetex(\frac{dR(t)}{dt} = -\frac{dF(t)}{dt} = -f(t))
変数分離で積分すると
#mimetex(R(t) = \exp(-\int^t_0 \lambda(f)dt))
平均寿命 MTTF(mean time to failure)
#mimetex(MTTF = \int^\inf_0R(t)dt)
lambda(t)はどんな関数？~
システムのハードウェア バスタブ曲線(経験則)~
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
