CPUスケジューリング
|
|
|
- しげじろう しどり
- 6 years ago
- Views:
Transcription
1 10-12 並行プロセス 1
2 順序グラフ 今まで, プログラムの逐次的実行 これから, プログラム内の並行実行 a:=x+y; b:=z+1; c:=a-b; w:=c+1; 上記の文を平行に実行したい! 1 と 2 は, 並列に実行できる. 3 は,1 の後 4 は,3 の後 2
3 順序グラフの定義 S1 循環のあるグラフは考えない. S2 S3 S1 S4 S2 S5 S6 S3 S7 図 9.2 循環のある順序グラフ 図 9.1 順序グラフ 3
4 並行に実行できるための条件 記号の定義 R(Si): 文 Si で読み出される変数の集合 W(Si): 文 Si で書きこまれる変数の集合 例 a:=x+y; b:=z+1; c:=a-b; w:=c+1; R(3)={a,b},W(3)={c} 2 つの連続する文 S1,S2 が並行実行可能であるための必要十分条件 以下の 3 つが成立すること (Bernstein の条件 (1966)) 1)R(S1) W(S2)={} 2)W(S1) R(S2)={} 3)W(S1) W(S2)={} 4
5 仕様 プログラミング言語で用いる並列命令 1)Fork と Join 構造体 2)parbegin と parend の構造体 5
6 Fork と Join 構造体 (1/3) Conway(1963), Dennis and Van Horn(1966) が提案 S1 S1 S2 Fork join S2 S3 S3 図 9.3 fork 構造体のための順序グラフ 図 9.4 join 構造体のための順序グラフ 6
7 Fork と Join 構造体 (2/3) S2 Fork join S3 count:=2; fork L1; S3; go to L2; L1: S2; L2: join count; Join 命令 ; Count:= count -1; If count!= 0; then quit; 7
8 Fork と Join 構造体 (3/3) ー図 9.1 のプログラムー S5 S2 S4 S1 S6 S3 S7 S1; Count:=3; Fork L1; S2; S4; Fork L2; S5; Go to L3 L2: S6; Go to L3; L1: S3; L3: join count; S7; 図 9.1 順序グラフ 8
9 並行文 :parbegin と parend の構造体 (1/2) より高級な構造体 Dijkstra(1965) により提案 形式 Parbegin S1; S2;, Sn parend; S0 S1 S2 Sn-1 Sn Sn+1 図 9.5 並行文のための順序グラフ 9
10 並行文 :parbegin と parend の構造体 (2/2) parbegn a:= x+y; b:= z+1; parend c:= a-b; w:= c+1; a:=x+y; b:=z+1; c:=a-b; w:=c+1; S5 S2 S4 S1 S6 S3 S7 S1; parbegin S3; begin S2; S4; parbegin S5; S6; parend; end parend S7; 図 9.1 順序グラフ 10
11 比較 (fork/join と parbegin/parend)(1/2) 任意の順序グラフを表現できるか? ( 例 ) 図 9.6 を例にとると, 並行文 (parbegin/parend) では表現できない. Fork/join では, 表現できる. 使いやすさ Fork/join < parbegin/parend 任意の順序グラフを表現できる必要があるか? 多くの問題にできようできるだけで十分では? S1; count1:= 2; fork L1; S2; S4; count 2:=2; fork L2; S5; go to L3; L1: S3; L2: join count1; S6; L3: join count2; S7; S5 S2 S4 S7 S1 S6 S3 図 9.6 対応する並行文のない順序グラフ 11
12 比較 (fork/join と parbegin/parend)(2/2) Parbegin/parend 構造は,fork/join で記述できる. count:=n; fork L2; fork L3; fork Ln; S1; go to Lj; L2: S2; go to Lj; L3: S3; go to Lj; Ln: Sn; Lj; join count;
13 プロセスの概念 プロセスとは? ( 厳密な概念はない! 定義は困難.) 1) 実行しているプログラム 2) 疑似プロセッサ プログラムを実行するための器 OSが管理するための単位 プロセスのことをタスクとも言う. 図 9.6 対応する並行文のない順序グラフ 13
14 プロセスの状態 実行中 (running) 命令をプロセッサで実行している状態 実行待ち (ready) プロセッサの割り当てを待っている状態 待機中 ( 封鎖,blocked, suspended) ある事象が起こるのを待っている状態 入出力の完了,... デッドロック (deadlocked) 図 9.7 プロセス状態推移図 ( 準備中 ) 14
15 プロセスグラフ プロセスの階層構成 プロセスの依存関係を表すグラフ 図 9.8 プロセスグラフ ( 準備中 ) 15
16 危険区域 ( クリティカルセクション,critical section) 問題 危険区域 ( クリティカルセクション,critical section) 際どい区域 ( 際どい領域 ) とも言う. 例として, 生産者 / 消費者問題 (Producer/consumer problem) を考える. 16
17 生産者 / 消費者問題 (Producer/consumer problem)(1/3) 生産者 : 消費者によって消費されるものを生産する. 消費者 : 生産者がつくったものを消費する. ( 例 ) 実社会 : どら息子,... 計算機の世界 プリンタ, コンパイラ, アセンブラ, デバイスドライバ,.. 17
18 生産者 / 消費者問題 (Producer/consumer problem)(2/3) 注意すべきこと : 生産者 : まだ消費していないところに, 上書きしてはいけない. 消費者 : 生産されていないところから読んではいけない. 格納する場所が必要 バッファ バッファの大きさ 無限長 : 制約なしバッファ (unbounded-buffer) 有限長 : 制約バッファ (bounded-buffer) 18
19 生産者 / 消費者問題 : 制約バッファでの実現 (3/3) 使用する変数 n: バッファの大きさ in: 次の空きバッファを指すポインタ ( 生産者は in で指されたバッファに格納する ) Out: 詰まっている最初のバッファを指すポインタ ( 消費者は out で指されたバッファから取り出す ) 注意事項 バッファが一杯, 空をどうやって判断するか? in==out のとき, バッファは空 (in+1 mod n) == out のとき, バッファは一杯 in out 19
20 処理概要 生産者 : バッファが一杯でなければ, バッファに格納. ポインタ in を +1 消費者 : バッファが空でなければ, バッファから取り出す. ポインタ out を +1 parbegin producer: begin repeat 項目を生産して nextp に入れる while in+1 mod n = out do skip; /* バッファが一杯か?*/ buffer[in] := nextp ; in := in + 1 mod n ; /* ポインタを +1*/ until false end; consumer: begin repeat while in = out do skip; /* バッファが空か?*/ nextc := buffer[out] ; out := out + 1 mod n ; /* ポインタを +1*/ nextc の項目を消費する until false ; end ; 同時に一杯にできるバッファ数最大 : バッファ容量 (n) -1 20
21 修正アルゴリズム バッファ容量数 (n) だけ使えるようにしたい. 方針 一杯であるバッファ数を記憶しておく. counter : 一杯であるバッファ数 counter == 0; バッファが空 counter == n( バッファ数 ); バッファが満杯 処理概要 生産者 バッファが満杯かどうかチェック 満杯でなければ, バッファに格納 ポインタ in を +1 消費者 バッファが空かどうかチェック 空でなければ, バッファから取り出す ポインタ out を +1 21
22 修正した処理 ( プログラム ) の概要 生産者 repeat 項目を生産してnextpに入れる while counter = n do skip; /* バッファが一杯か?*/ buffer[in] := nextp ; in := in + 1 mod n ; /* ポインタを+1*/ counter := counter + 1 ; until false 消費者 repeat while counter = 0 do skip; /* バッファが空か?*/ nextc := buffer[out] ; out := out + 1 mod n ; /* ポインタを +1*/ counter := counter - 1 ; nextc の項目を消費する until false ; 22
23 前記のプログラムは正しく動作するか? 生産者と消費者で共有している ( 共有変数 )counter がくせもの! Counter 操作の実現コード ( 例 ) counter := counter +1 ; 1register1 := counter ; 2register1 := register1 + 1 ; 3counter := register1 ; counter := counter -1 ; 4register2 := counter ; 5register2 := register2-1 ; 6counter := register2 ; 正しく動作しない系列の系 いま,counter = 0 とする. 左記の 2 つの文がまじりあって実行されると, ( 論理的には,+-1 で,counter = 0 のはず ) 1) 生産者が 1 を実行 (r1 =0, c=0) 2) 生産者が 2 を実行 (r1 = 1, c=0) ここで, 何らかの理由で生産者の実行が中断し, 消費者に実行が移る. ( 理由の例 : ラウンドスケジューリングでタイムスライスを使い切って, たまたま消費者プログラムが実行対象に選択された ) 3) 消費者が 4 を実行 (r2=0, c=0) 4) 消費者が 5 を実行 (r2 = -1, c=0) 5) 消費者が 6 を実行 (r2= -1, c= -1) ( この後, 何らかの理由で, 生産者に実行が移った ) 6) 生産者が 3 を実行 (r1=1, c=1) 上記の実行結果 : counter = 1 論理的に正しくない. 23
24 クリティカルセクション問題の定義 クリティカルセクションとは (critical section, 危険領域, 際どい領域 ) とは? まじあって実行されてはいけない区域, 領域, 操作のこと. 操作が不可分に実行されなくてはいけない. 複数のプログラムが共有オブジェクトへの読書きを行うと, 必ず生じる. 有限バッファの例 Counter への操作 (+1, -1) プログラム 1 プログラム n 読書き 読書き 共有オブジェクト 24
25 クリティカルセクション問題の例 リストの管理 ( ダブルポインタ ) 25
26 クリティカルセクション問題を解決する解に要請する ( 満たすべき ) 条件 今から, 考える解は, 次の 3 つの条件を満たす必要あり. 1) 相互排除 (Mutual exclusion) クリティカルセクションに同時に入れるプロセスは高々 1 つ 2) 前進 (Progress) クリティカルセクション内にプロセスがない場合, 入口で待っているプロセスの内, 尐なくとも 1 つは有限時間でクリティカルセクションに入れる.( 必ずどれかは入れる.) 3) 有限待機 (Bounded waiting) クリティカルセクションへ入ろうとして待たされる時間は, 有限時間でなければならない.( 待っているプロセスからみれば, 有限時間待てば, 必ずクリティカルセクションに入れる. 永久に待たされることはない.) 26
27 仮定と解について 仮定 プロセスの実行速度は任意 ( でも,!= 0) 機械命令は不可分に実行される. Load, store, test,. クリティカルセクションを実現する解 歴史をみる. ソフトウェアによる解 基本的な機械命令を用いる ( 特殊な機械命令はない ). 1) プロセス数が 2 つの場合 ( 最も単純な場合 ) 2) プロセス数が一般 (n) の場合 ハードウェアによる解 特殊な機械命令を用いた解 27
28 ソフトウェアによる解ープロセス数が 2 の場合ー プロセス プロセス 0: P0 プロセス 1: P1 変数 ( 整数 ) i = 0, 1 j = 1 i i = 0, j = 1 I = 1, j = 0 28
29 ソフトウェアによる解ープロセス数が 2 の場合ーアルゴリズム 1 考え方 : クリティカルセクションに入れるプロセスを指定する共有変数を設ける. Repeat while turn i do skip ; turn = j ; 残り区域 until false; 危険区域 ( クリティカルセクション ) 考察 相互排除の要請は満足 前進, 有限待機の要請は満足していない. プロセスは交互にしかクリティカルセクションに入れない. 29
30 PO アルゴリズム 1 P1 自分の番か? No Read Read 自分の番か? No Yes Yes CS 実行 変 数 CS 実行 お前の番だ! Write Write お前の番だ! CS: クリティカルセクション 30
31 ソフトウェアによる解ープロセス数が 2 の場合ーアルゴリズム 2(1/3) 考え方 : クリティカルセクションに入っているかどうかを識別する. 識別する変数 : flag[i] 論理変数 Flag[i] = true( クリティカルセクションに入っている ) Flag[i] = false( に入っていない ) Repeat while flag[j] do skip ; flag[i] := true ; 危険区域 ( クリティカルセクション ) flag[i]:= false ; 残り区域 until false; 31
32 プロセス PO アルゴリズム 2(2/3) プロセス P1 Yes Yes 相手が入っているか? 相手が入っているか? No No 自分が入っているぞ! 自分が入っているぞ! CS 実行 CS 実行 出たぞ! CS: クリティカルセクション 出たぞ! 32
33 ソフトウェアによる解ープロセス数が 2 の場合ーアルゴリズム 3(1/3) アルゴリズム 2 がうまくいかなかった理由 : 自分がクリティカルセクションに入ったことを告げる前に, 誰かクリティカルセクションに入っているかどうかを判断している. 誰か入っていないか? while flag[j] do skip ; クリティカルセクションに自分が入ったことを告げる. flag[i] := true ; 33
34 ソフトウェアによる解ープロセス数が 2 の場合ーアルゴリズム 3(2/3) 改良点 : クリティカルセクションに入りたいことをつげる. 誰か入りたがっていないか? Repeat flag[i] := true ; while flag[j] do skip ; 危険区域 ( クリティカルセクション ) flag[i]:= false ; 残り区域 until false; 34
35 プロセス PO アルゴリズム 3(3/3) プロセス P1 入りたいよう! 入りたいよう! Yes 相手が入りたがっているか? No 相手が入りたがっているか? No Yes CS 実行 CS 実行 出たぞ! CS: クリティカルセクション 出たぞ!
36 アルゴリズム 3 はクリティカルセクション問題を正しく解決するか? 1) 相互排除の要請は満たされているか? OK 2) 前進の要請は満たされているか? 満たされていない. どの待ちプロセスも入れないことが起こり得る. 例 : 36
37 ソフトウェアによる解ープロセス数が 2 の場合ーアルゴリズム 4(1/3) 正しいアルゴリズム Perterson[1981] による Repeat flag[i] := true ; turn := j ; while( flag[j] and turn = j ) do skip ; 危険区域 ( クリティカルセクション ) fkag[i]:= false ; 残り区域 until false; 37
38 プロセス PO アルゴリズム 4(2/3) プロセス P1 入りたいよう! 入りたいよう! カルタに手を付ける カルタ カルタに手を付ける No 相手が入りたがっているか? No 相手が入りたがっているか? パス A Yes パス B パス A Yes パス B 自分が先に手を付けたか? ( 相手の手が上にあるか?) No 自分が先に手を付けたか? ( 相手の手が上にあるか?) No Yes Yes CS 実行 CS 実行 出たぞ! CS: クリティカルセクション 出たぞ!
39 アルゴリズム 4 が 3 つの要請を満たしていることの証明概要 アルゴリズム 4 Simplified Dekker s Algorithm(Perterson が提案 ) とも言う. Dekker: 最初に提案した学者 Dekker が提案したアルゴリズムは複雑だったので, Perterson が簡単にしたアルゴリズムが, このアルゴリズム 4 3 つの要請 1) 相互排除 2) 前進 3) 有限待機 39
40 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (1/ 6) 相互排除 クリティカルセクション (CS) に同時に入れるプロセスは高々 1 つ. 証明のやり方 背理法を用いる. 2 つのプロセスが CS に入れるとする. 矛盾を導く. だから,2 つのプロセスが CS には入れない. だから, 同時に CS に入っているプロセスは高々 1 つ. プロセス P0 の CS への入り方 1) パス A 2) パス B 40
41 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (2/ 6) 1) パス A 経由で CS に入った場合 P0 がパス A 経由で入った時,P1 は, 入りたいよう! 以前を実行していた. この後,P1 は, 入りたいよう!, カルタに手付 を実行 従って,P1 は, パス B 経由でしか入れない. ( 理由 :P0 がすでに CS に入っているので ) P1 がパス B 経由で入ったならば,P0 の手が上になければならない. これはありえない.( 理由 :P0 が先に入ったのだから, 当然,P1 の手は P0 の手の下にあるはず.) No パス A 入りたいよう! カルタに手を付ける 相手が入りたがっているか? Yes 自分が先に手を付けたか? ( 相手の手が上にあるか?) Yes パス B No 矛盾 従って,CS にいる P0 は,CS にはパス A 経由で入っていない. CS 実行 出たぞ! 41
42 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (3/ 6) 2) パスB 経由でCS に入った場合 P1のCSへの入り方 : 2-1) パスA 2-2) パスB の2 種類上記, 各々の場合を考える. No 入りたいよう! カルタに手を付ける 相手が入りたがっているか? パス A Yes パス B 自分が先に手を付けたか? ( 相手の手が上にあるか?) No CS 実行 Yes 出たぞ! 42
43 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (4/ 6) 2-1) パス A 経由の場合 状況を整理すると,P0: パス B,P1: パス A P0: P1 が入りたがっているので, パス B 経由で入った. P1: P0 が入りたがっていないので, パス A 経由で入った. 入りたいよう! カルタに手を付ける P1 が入った時は,P0 は, 入りたいよう! 以前を実行 (P1 は, カルタの手付 を終了している ) P0 は, パス B 経由で入れない.( 理由 :P1 の手が P 0 の上にあることはない. というのは,P1 の方が早く カルタの手付 を実行しているから ) No 相手が入りたがっているか? パスA Yes パスB 矛盾 従って,CS にいる P0 が, パス B 経由で入った場合, P1 はパス A 経由では入っていない. 自分が先に手を付けたか? ( 相手の手が上にあるか?) CS 実行 Yes No 出たぞ! 43
44 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (5/ 6) 2-2) パス B 経由の場合 状況を整理すると,P0: パス B,P1: パス B P0: P1 が入りたがっているので, パス B 経由で入った. P1: P0 が 同時にパス B 経由で入ったことはあり得ない!( 理由 :P0,P1 もパス B 経由で入ったということは, 相手の手が上にあるのを確認してから入ったことになる ) これは, あり得ない. というのは, カルタの手付き は 1 回だけなので, 必ずどちらかの手が上になるので. 入りたいよう! カルタに手を付ける No 相手が入りたがっているか? パスA Yes パスB 矛盾 従って,CS にいる P0 が, パス B 経由で入った場合, P1 はパス B 経由では入っていない. 自分が先に手を付けたか? ( 相手の手が上にあるか?) CS 実行 Yes No 出たぞ! 44
45 アルゴリズム 4 が 相互排除 の要請を満たしていることの証明概要 (6/ 6) まとめ P0,P1 が同時に CS に入っているとすると, 矛盾が生じる. だから,P0,P1 が同時に入っていることは, あり得ない. 従って, 同時に CS に入っているプロセスの数は, 高々 1 つのみ. 入りたいよう! カルタに手を付ける No 相手が入りたがっているか? パスA Yes パスB 自分が先に手を付けたか? ( 相手の手が上にあるか?) No CS 実行 Yes 出たぞ! 45
46 アルゴリズム 4 が 前進 の要請を満たしていることの証明概要 (1/4) 前進 CS に入っていない時, 待ちプロセスのどれか ( この場合は, もう 1 つのプロセス ) が必ず CS には入れるか? 場合分け : 1)P0 のみが CS に入ることを要求,P1 は要求しない 2)P0,P1 の両方が要求 上記の各々の場合を考える. No パス A 入りたいよう! カルタに手を付ける 相手が入りたがっているか? Yes 自分が先に手を付けたか? ( 相手の手が上にあるか?) CS 実行 Yes パス B No 出たぞ! 46
47 アルゴリズム 4 が 前進 の要請を満たしていることの証明概要 (2/4) 1)P0 のみが CS に入ることを要求,P1 は要求しない の場合 P0 は CS に入れる ( 自明 ) No 入りたいよう! カルタに手を付ける 相手が入りたがっているか? パス A Yes パス B 自分が先に手を付けたか? ( 相手の手が上にあるか?) No CS 実行 Yes 出たぞ! 47
48 アルゴリズム 4 が 前進 の要請を満たしていることの証明概要 (3/4) 2)P0,P1 の両方が要求 の場合 両方とも CS に入れない状態 ループで回っている状態 相手が入りたがっている, かつ, 相手の手が下にある. 上記の状態はあり得ない. というのは, カルタの手付は 1 回のみなので. 矛盾 従って,P0,P1 が CS に入ることを要求した時, どちらかが CS に入れる. No パス A 入りたいよう! カルタに手を付ける 相手が入りたがっているか? Yes 自分が先に手を付けたか? ( 相手の手が上にあるか?) CS 実行 Yes パス B No 出たぞ! 48
49 アルゴリズム 4 が 前進 の要請を満たしていることの証明概要 (4/4) まとめ CS に誰も入っていない時,CS に入りたいと要求したプロセスは,CS に入ることができる. 入りたいよう! カルタに手を付ける No 相手が入りたがっているか? パス A Yes パス B 自分が先に手を付けたか? ( 相手の手が上にあるか?) No CS 実行 Yes 出たぞ! 49
50 アルゴリズム 4 が 有限待機 の要請を満たしていることの証明概要 (1/2) 有限待機 CS に入りたがった後, 有限時間で CS に入れるか?( 永久に待たされることはない. 飢餓状態 (starvation) は生じない ) 入りたいよう! カルタに手を付ける No 相手が入りたがっているか? パス A Yes パス B 自分が先に手を付けたか? ( 相手の手が上にあるか?) No CS 実行 Yes 出たぞ! 50
51 アルゴリズム 4 が 有限待機 の要請を満たしていることの証明概要 (2/2) P0 が有限時間で入れないとする. これは,P1 が何回も入る状態 P1 が入れるということは,P1 の手の上に,P0 の手がある, ということ. これはあり得ない.(P0 の カルタの手付 は 1 回のみなので ) 矛盾 従って,CS に誰も入っていない時,CS に入りたいプロセスは有限時間で入れる. No パス A 入りたいよう! カルタに手を付ける 相手が入りたがっているか? Yes 自分が先に手を付けたか? ( 相手の手が上にあるか?) CS 実行 Yes パス B No 出たぞ! 51
52 アルゴリズム 4 が 3 つの要請を満たしていることの証明概要 まとめ アルゴリズム 4 は, 以下の 3 つの要請を満足することが証明? できた. 3つの要請 1) 相互排除 2) 前進 3) 有限待機 52
53 プロセス数が一般,n, の場合 アルゴリズム 6 Lamport[1974] による パン屋アルゴリズム (bakery algorithm) Repeat choosing[i] := true ; number[i] := max ( number[0], number[1],, numbr[n-1] + 1 ); choosing [i] := false ; for j := 0 to n-1 do begin while choosing[j] do skip ; while (number[j] 0 and (number[j], j ) < ( number[i], i ) ) do skip ; end ; 危険区域 ( クリティカルセクション ) number[i]:= 0 ; 残り区域 until false; 53
54 ハードウェアによる解 ハードウェアが提供する不可分 (atomic) 命令 (1) テスト アンド セット (Test-and-Set) 命令 function Test-and-Set ( var target: boolean ) : boolean ; begin Test-and-Set := target ; target := true ; end ; 1read 変数 target 2write true 54
55 ハードウェアによる解 テスト アンド セット (Test-and-Set) 命令を用いたクリティカルセクション問題を解決する方法 repeat 初期値 lock := false while Test-and-Set(lock) do skip ; 危険区域 ( クリティカルセクション ) lock := false ; 残り区域 until false; 但し, 上記のアルゴリズムは, 有限待機の要請を満足していない. 55
56 ハードウェアによる解 テスト アンド セット (Test-and-Set) 命令を用いたクリティカルセクション問題を解決する方法 有限待機の要請も満足させるアルゴリズム var j : 0 n-1 ; key : boolean ; repeat waiting[i] := true ; key := true ; while waiting[i] and key do key := Test-and-Set(lock) ; waiting[i] := false ; 危険区域 ( クリティカルセクション ) j := j + 1 mod n ; while ( j i ) and ( not waiting[j] ) do j := j + 1 mod n ; if j = i then lock := false else waiting[j] := false ; 残り区域 until false; 56
57 ハードウェアによる解 (2) スワップ (Swapp) 命令 Procedure Swap ( var a, b: boolean ) ; var temp : boolean ; begin temp := a ; a := b ; b := temp ; end ; 交換 変数 a 変数 b 57
58 ハードウェアによる解 スワップ命令を用いたクリティカルセクション問題を解決する方法 初期値 lock := false repeat key := true ; repeat Swapp ( lock, key) ; until key = false ; 危険区域 ( クリティカルセクション ) lock := false ; 残り区域 until false; 変数 key 1true 2 交換 変数 lock 但し, 上記のアルゴリズムは, 有限待機の要請を満足していない. 58
59 セマフォ (Semaphore) プロセス間同期のための構造体 Dijkstra[1965] により提案 命令の種類 : 次の 2 つ. P 命令 V 命令 P, V 命令の定義 ( 古典的定義 ) P(S): while S 0 do skip ; S := S 1 ; V(S): S := S + 1 ; S: セマフォ ( あるいは, セマフォ変数 ) と呼ぶ P(S), V(S) ともに不可分に実行されなければならない. P(S), V(S): クリティカルセクション として実行されることが重要. 大きなクリティカルセクション ( 還元 ) 小さなクリティカルセクション 59
60 セマフォ (Semaphore) の使用方法ークリティカルセクション問題の解決方法としてー 初期値 mutex := 1 repeat P(mutex) ; V(mutex) 残り区域 until false; 危険区域 ( クリティカルセクション ) 60
61 セマフォ (Semaphore) の使用方法ー順序グラフの実行ー S1 S5 S2 S4 S7 S6 S3 var a, b, c, d, e, f, g : semaphores ; (* すべてのセマフォの初期値は 0 である.*) begin parbegin begin S1; V(a); V(b); end ; begin P(a); S2; S4; V(c); V(d); end ; begin P(b); S3; V(e); end ; begin P(c); S5; V(f); end ; begin P(d); P(e); S6; V(g); end ; begin P(f); V(g); S7; end ; parend ; until false; 図 9.6 対応する並行文のない順序グラフ 61 61
62 セマフォの新しい定義 古典的定義の問題点 繁忙待機 (busy-waiting) が生じる. プロセッサを浪費 待つ場合は, プロセッサを解放する ( プロセスをサスペンドさせる ) した方がよい.. セマフォの新しい定義 プロセスが待たなければならない場合は,( 古典的定義のように繁忙待機で待つのではなく ) そのプロセスをサスペンドさせて, プロセッサを解放させる ( 他プロセスに明け渡す ) P, Vの新しい定義 P(S): S := S 1; if S < 0 then begin そのプロセスをサスペンドして,(Sに対応した) キューにつなぐ. end ; V(S): S := S + 1; if S 0 then begin キューの先頭にあるプロセスを起こす. end ; S 0のとき, S が待ちプロセス数を表す. 62
63 セマフォの実現 P(S), V(S) が不可分に実行されなければならない. 本来のクリティカルセクション 小さなクリティカルセクションに還元 (P(S), V(S) 操作 ) P(S), V(S) のクリティカルセクション問題 ( 新しい定義の ) 実現 P(S), V(S) は通常システムコールとして提供 システムモードで実行 1) シングルプロセッサの場合 割込み禁止にして実行, またはハードウェア提供の不可分命令 ( 例 : テストアンドセット命令など ) 2) マルチプロセッサの場合 割込み禁止にしてもだめ. ソフトウェアによる実現, またはハードが提供する不可分命令 ( 例 : テストアンドセット命令など ) を用いて実現 63
64 古典的プロセス協調問題 代表的なプロセス協調問題 有限バッファ問題 (bounded buffer problem)( 制約バッファ問題 )( 生産者 / 消費者問題 ) 読書き問題 (Reader/Writer problem) 食事をする哲学者問題, 哲学者の食事問題 (Dining philosophers problem) 64
65 有限バッファ問題 (Bounded buffer problem) 同期命令 : セマフォ セマフォ ( 変数 ) full: 一杯のバッファ数 empty: 空のバッファ数 mutex: バッファへのアクセスを相互排除するために使用 65
66 有限バッファ問題 begin full := 0 ; empty := n ; mutex := 1 ; parbegin producer : repeat nextpへ1つの項目を生産して入れる. P(empty) ; P(mutex) ; nextpをbufferに追加する. V(mutex) ; V(full) ; until false ; consumer : repeat P(full) ; P(mutex) ; bufferから1つの項目を取出してnextcへ置く. V(mutex) ; V(empty) ; nextcの中の項目を消費する. until false ; parend ; end 66
67 読書き問題 (Readers/Writers problem) データファイルへのアクセス データを読み出すだけのプロセス ( リーダ,Reader) データを読書きするプロセス ( ライタ,Writer) 注意点 リーダとライタが同時に 1 つのデータファイルにアクセスすると, データの一貫性が保てなくなる可能性あり. ライタは相互排除でデータにアクセスする必要あり. ファイルアクセスの優先度 待ちプロセスの中に, リーダとライタが混在していたら, どちらのプロセスを優先して中に入れるか? 第一読書き問題 ( 第一種の読書き問題 ) リーダが優先される. 第二読書き問題 ( 第二種の読書き問題 ) ライタが優先される. 飢餓状態 (starvation, スタベーション ) 飢餓状態になる可能性のあるのは, どのプロセスか? 第一読書き問題 ( 第一種の読書き問題 ) ライタ 第二読書き問題 ( 第二種の読書き問題 ) リーダ 67
68 読書き問題 (Readers/Writers problem) リーダ ライタ 待ちプロセス リーダ データファイル ライタ
69 第一種の読書き問題 ( リーダ優先 ) 初期値セマフォ mutex=1, wrt =1, integer readcount = 0 読取り系プロセス ( リーダ ) の一般的な構造 P(mutex) ; readcount := readcount + 1 ; if readcount >= 1 then p(wrt ) ; V(mutex) ; 読取りが実行される. P(mutex) ; readcount := readcount 1 ; if readcount = 0 then V(wrt ) ; V(mutex) ; ライタを待たせる 待ちライタを起動 書込み系プロセス ( ライタ ) の一般的な構造 P(wrt) ; 書込みが実行される. V(wrt) ; 69
70 食事をする哲学者問題, 哲学者の食事問題 (1/4) (Dining Philosophers problem) 問題の説明 5 人の哲学者がテーブルに座っている. 哲学者と哲学者の間に,1 本 ( 一対ではない ) の箸がおいてある. 哲学者の動作 : 下記の食事と思索の 2 つの動作を繰り返す. 食事 : 左右の 2 本の箸をとりあげて食事する. 思索にふける : 食事の後, 持っていた箸をおいて, 思索にふける. 哲学者 箸 (1 本, 一対ではない ) 70
71 食事をする哲学者問題, 哲学者の食事問題 (2/4) (Dining Philosophers problem) やりたいこと : 哲学者の動作を記述したい. 哲学者の動作 両方の箸を取り上げて, 食事をする. 食事がすんだら, 持っている箸を元の場所において, 思索にふける. 上記の動作を繰り返す. 要請 デッドロックになってはいけない. 食事をしたい哲学者が餓死してはいけない.( 飢餓状態が発生してはいけない ) 箸の取り上げは, 排他制御で行わなくてはならない. 哲学者 箸 (1 本, 一対ではない ) 71
72 食事をする哲学者問題, 哲学者の食事問題 (3/4) (Dining Philosophers problem) 1 つの例 : どの哲学者も食事をするときは, 同じ動作をする ( 対称動作 ) まず, 左の箸をとって, 次に右の箸をとる. 箸 1 本の取り上げは, 排他制御で行う 排他制御 : セマフォを用いる.. 初期値セマフォ chopstick[i] = 1 repeat P(chopstick[i]) ; P(chopstick[I + 1 mod 5]) ; 食べる ( 食事 ) V(chopstick[i]) ; V(chopstick[I + 1 mod 5]) ; 考える ( 思索にふける ) until false デッドロックが生じる可能性あり! みんなが同時に, 左の箸を取り上げた場合 72
73 食事をする哲学者問題, 哲学者の食事問題 (4/4) (Dining Philosophers problem) デッドロックを生じさせない方法 1)4 人しかテーブルにつけないようにする. 2) 左右の箸を同時に取り上げる. この動作をクリティカルセクションにする. 3) 非対称な解を用いる. 偶数番目 : 右の箸から. 奇数番目 : 左の箸から 飢餓状態の回避はどうするか? 73
74 以上 74
Microsoft PowerPoint - OS04.pptx
この資料は 情報工学レクチャーシリーズオペレーティングシステム松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために 名古屋工業大学松尾啓志 津邑公暁が作成しました オペレーティングシステム #4 並行プロセス : 排他制御基礎 パワーポイント 2007 で最終版として保存しているため 変更はできませんが 授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ
Microsoft PowerPoint - OS06.pptx
この資料は 情報工学レクチャーシリーズ松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために 名古屋工業大学松尾啓志 津邑公暁が作成しました 並行プロセス モニタ パワーポイント 2007 で最終版として保存しているため 変更はできませんが 授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ 編集可能なバージョンをお渡しする事も可能です 排他制御の枠組み
POSIXスレッド
POSIX スレッド (3) システムプログラミング 2011 年 11 月 7 日 建部修見 同期の戦略 単一大域ロック スレッドセーフ関数 構造的コードロッキング 構造的データロッキング ロックとモジュラリティ デッドロック 単一大域ロック (single global lock) 単一のアプリケーションワイドの mutex スレッドが実行するときに獲得, ブロックする前にリリース どのタイミングでも一つのスレッドが共有データをアクセスする
コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n
コンピュータ工学講義プリント (7 月 17 日 ) 今回の講義では フローチャートについて学ぶ フローチャートとはフローチャートは コンピュータプログラムの処理の流れを視覚的に表し 処理の全体像を把握しやすくするために書く図である 日本語では流れ図という 図 1 は ユーザーに 0 以上の整数 n を入力してもらい その後 1 から n までの全ての整数の合計 sum を計算し 最後にその sum
05-scheduling.ppt
オペレーティングシステム ~ スケジューリング ~ 山田浩史 hiroshiy @ cc.tuat.ac.jp 2014/06/01 復習 : プロセス 実行状態にあるプログラムのこと プログラムの実行に必要なものをひっくるめて指す テキスト領域 データ領域 スタック領域 CPU のレジスタ値 プログラムカウンタ など OS はプロセス単位で管理する メモリ Hard Disk CPU プロセス execute
Microsoft PowerPoint - 5_2-3IPC.pptx
2.3.1 競合状態 (race condition) オペレーティングシステム 5 2.3 プロセス間通信 Example Process A Process B i=0 i=0 while(i-10){ i++ i-- print A finished print B finished プロセス A スプーラディレクトリ ( ファイル印刷の待ち配列 ) ここまで印刷した
PowerPoint Presentation
コンピュータ科学 II 担当 : 武田敦志 http://takeda.cs.tohoku gakuin.ac.jp/ 今日の話 オペレーティングシステム コンピュータを利用するための基本ソフト オペレーティングシステムの役割 プロセスの管理主記憶の管理出入力の管理ファイルの管理 タイムシェアリングシステム仮想記憶排他制御ディレクトリ構造
NUMAの構成
共有メモリを使ったデータ交換と同期 慶應義塾大学理工学部 天野英晴 hunga@am.ics.keio.ac.jp 同期の必要性 あるプロセッサが共有メモリに書いても 別のプロセッサにはそのことが分からない 同時に同じ共有変数に書き込みすると 結果がどうなるか分からない そもそも共有メモリって結構危険な代物 多くのプロセッサが並列に動くには何かの制御機構が要る 不可分命令 同期用メモリ バリア同期機構
VelilogHDL 回路を「言語」で記述する
2. ソースを書く 数値表現 数値表現形式 : ss'fnn...n ss は, 定数のビット幅を 10 進数で表します f は, 基数を表します b が 2 進,o が 8 進,d が 10 進,h が 16 進 nn...n は, 定数値を表します 各基数で許される値を書くこ Verilog ビット幅 基数 2 進表現 1'b0 1 2 進 0 4'b0100 4 2 進 0100 4'd4 4
プログラミングA
プログラミング A 第 5 回 場合に応じた処理 繰り返し 2019 年 5 月 13 日 東邦大学金岡晃 場合に応じた処理 1 こういうプログラムを作りたい 5 教科のテスト 100 点以上各科目の点数の合計が 100 点未満 おめでとう! これで 100 点越えのプレゼントを獲得! というメッセージを出力 残念!100 点越えのプレゼントまであと ** 点! というメッセージを出力 5 教科の点数の合計が
Microsoft Word - VBA基礎(3).docx
上に中和滴定のフローチャートを示しました この中で溶液の色を判断する部分があります このような判断はプログラムではどのように行うのでしょうか 判断に使う命令は IF 文を使います IF は英語で もし何々なら という意味になります 条件判断条件判断には次の命令を使います If 条件式 1 Then ElseIf 条件式 2 Then ElseIf 条件式 3 Then 実行文群 1 実行文群 2 実行文群
CPUスケジューリング
5-6 プロセス管理と CPU スケジューリング 1 多重プログラミングの概念 CPU を無駄なく使いたい ジョブ A ジョブ B 開始遊休状態 : 入力 開始遊休状態 : 入力 遊休状態 : 入力 遊休状態 : 入力 停止 停止 図 4.1 二つの上部 A,B の実行 2 多重プログラミングの概念 ジョブ A 開始遊休状態 : 入力 遊休状態 : 入力 停止 ジョブ B 待ち 開始遊休状態 : 入力
プログラミングA
プログラミング A 第 5 回 場合に応じた処理 繰り返し 2017 年 5 月 15 日 東邦大学金岡晃 前回の復習 (1) このプログラムを作成し実行してください 1 前回の復習 (2) このプログラムを作成し実行してください 2 前回の復習 (3) 3 前回の復習 演算子 代入演算子 インクリメント シフト演算子 型変換 4 場合に応じた処理 5 こういうプログラムを作りたい 5 教科のテスト
オペレーティングシステム
1.PFLab( 加藤研 ) のウェブサイトからダウンロードできます http://www.pf.is.s.u-tokyo.ac.jp/ja/classes/ 2. 紙資料も配布します オペレーティングシステム 加藤真平東京大学大学院情報理工学系研究科 shinpei@is.s.u-tokyo.ac.jp 2018/5/14 第 5 回オペレーティングシステム 1 講義概要 受講生に求める基礎知識
2006年10月5日（木）実施
2010 年 7 月 2 日 ( 金 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,
ex04_2012.ppt
2012 年度計算機システム演習第 4 回 2012.05.07 第 2 回課題の補足 } TSUBAMEへのログイン } TSUBAMEは学内からのログインはパスワードで可能 } } } } しかし 演習室ではパスワードでログインできない設定 } 公開鍵認証でログイン 公開鍵, 秘密鍵の生成 } ターミナルを開く } $ ssh-keygen } Enter file in which to save
Microsoft PowerPoint - algo ppt [互換モード]
![Microsoft PowerPoint - algo ppt [互換モード]](/thumbs/65/53901879.jpg "Microsoft PowerPoint - algo ppt [互換モード]")
( 復習 ) アルゴリズムとは アルゴリズム概論 - 探索 () - アルゴリズム 問題を解くための曖昧さのない手順 与えられた問題を解くための機械的操作からなる有限の手続き 機械的操作 : 単純な演算, 代入, 比較など 安本慶一 yasumoto[at]is.naist.jp プログラムとの違い プログラムはアルゴリズムをプログラミング言語で表現したもの アルゴリズムは自然言語でも, プログラミング言語でも表現できる
Microsoft PowerPoint - os ppt [互換モード]
![Microsoft PowerPoint - os ppt [互換モード]](/thumbs/74/69816971.jpg "Microsoft PowerPoint - os ppt [互換モード]")
5. メモリ管理 (2) 概要ページ管理 式ページ置換アルゴリズム 28/5/23 メモリ管理 (2) 1 ページング ( 復習 ) 仮想アドレス空間, 主記憶 ( 実アドレス空間 ) を固定サイズのページに分割 仮想アドレス空間のページを主記憶 ( メモリ ) のページに対応させる ページテーブル ( 変換表 ) を実メモリ上に保持 ページを単位としたアドレス変換 ( 仮想ページ番号, オフセット
始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル
![始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル](/thumbs/89/99127345.jpg "始めに, 最下位共通先祖を求めるための関数 LcaDFS( int v ) の処理を記述する. この関数は値を返さない再帰的な void 関数で, 点 v を根とする木 T の部分木を深さ優先探索する. 整数の引数 v は, 木 T の点を示す点番号で, 配列 NodeSpace[ ] へのカーソル")
概略設計書 作成者築山修治作成日 2012 年 10 月 1 日 概要 ( どのような入力に対して, どのような出力をするかの概要説明 ) * 木 T および質問点対の集合 P が与えられたとき, 各質問点対 p = (v,w) P の最下位共通先祖 ( すなわち木 T において点 v と w の共通の先祖 a で,a の真の子孫には v と w の共通の先祖が無いような点 ) を見出す関数である.
Microsoft PowerPoint - Lec ppt [互換モード]
![Microsoft PowerPoint - Lec ppt [互換モード]](/thumbs/91/106557353.jpg "Microsoft PowerPoint - Lec ppt [互換モード]")
0 年後学期 アウトオブオーダ実行プロセッサの構成 計算機アーキテクチャ第二 (O) アウトオブオーダ実行プロセッサとバックエンド フロントエンド 命令ウィンドウ : 命令を格納するバッファ 命令ウィンドウ ALU レジスタファイル ALU スケジューラ等 Register Dispatch 命令フェッチ, デコード, リネーミング バックエンド アウトオブオーダ実行プロセッサの構成 ディスパッチ
プログラミング入門１
プログラミング入門 1 第 5 回 繰り返し (while ループ ) 授業開始前に ログオン後 不要なファイルを削除し て待機してください Java 1 第 5 回 2 参考書について 参考書は自分にあったものをぜひ手元において自習してください 授業の WEB 教材は勉強の入り口へみなさんを案内するのが目的でつくられている これで十分という訳ではない 第 1 回に紹介した本以外にも良書がたくさんある
Microsoft PowerPoint - 06.pptx
アルゴリズムとデータ構造第 6 回 : 探索問題に対応するデータ構造 (2) 担当 : 上原隆平 (uehara) 2015/04/22 内容 スタック (stack): 最後に追加されたデータが最初に取り出される 待ち行列 / キュー (queue): 最初に追加されたデータが最初に取り出される ヒープ (heap): 蓄えられたデータのうち小さいものから順に取り出される 配列による実装 連結リストによる実装
PowerPoint プレゼンテーション
プログラミング応用演習 第 4 回再帰的構造体 前回の出席確認演習 #include int main() { FILE *fp; int c, linecount, length, maxlength; fp=fopen("/usr/share/dict/words","r"); if (fp == NULL) return 1; linecount=0; length=0;
Prog1_12th
2013 年 7 月 4 日 ( 木 ) 実施 ファイル処理ファイルとはファイル (file) は日常用語では紙などを綴じたものを表すが, コンピュータ用語ではデータの集合体を指す言葉である ファイルは例えば, 文書ファイルやプログラムファイルのように, 用途によって分類されることもあれば, また, テキストファイルやバイナリファイルのように, ファイルの作り方によって分類されることもある なお,
Microsoft PowerPoint - 05.pptx
アルゴリズムとデータ構造第 5 回 : データ構造 (1) 探索問題に対応するデータ構造 担当 : 上原隆平 (uehara) 2015/04/17 アルゴリズムとデータ構造 アルゴリズム : 問題を解く手順を記述 データ構造 : データや計算の途中結果を蓄える形式 計算の効率に大きく影響を与える 例 : 配列 連結リスト スタック キュー 優先順位付きキュー 木構造 今回と次回で探索問題を例に説明
PowerPoint プレゼンテーション
プログラミング応用演習 第 4 回再帰的構造体 プログラミングを 余談 : 教えることの難しさ 丁寧に説明しないと分かってもらえない 説明すると 小難しくなる学生が目指すべきところプログラム例を説明されて理解できる違うやり方でも良いので自力で解決できる おっけー 動けば良い という意識でプログラミング 正しく動くことのチェックは必要 解答例と自分のやり方との比較が勉強になる 今日のお題 再帰的構造体
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ
C プログラミング演習 1( 再 ) 2 講義では C プログラミングの基本を学び 演習では やや実践的なプログラミングを通して学ぶ 今回のプログラミングの課題 次のステップによって 徐々に難易度の高いプログラムを作成する ( 参照用の番号は よくわかる C 言語 のページ番号 ) 1. キーボード入力された整数 10 個の中から最大のものを答える 2. 整数を要素とする配列 (p.57-59) に初期値を与えておき
オートマトン 形式言語及び演習 1. 有限オートマトンとは 酒井正彦 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110,
オートマトン 形式言語及び演習 1 有限オートマトンとは 酒井正彦 wwwtrscssinagoya-uacjp/~sakai/lecture/automata/ 形式言語 言語とは : 文字列の集合例 : 偶数個の 1 の後に 0 を持つ列からなる集合 {0, 110, 11110, } 形式言語 : 数学モデルに基づいて定義された言語 認識機械 : 文字列が該当言語に属するか? 文字列 機械 受理
スライド 1
Dispatch 0 年後学期 計算機アーキテクチャ第二 (O) アウトオブオーダ実行プロセッサとバックエンド フロントエンド 命令ウィンドウ : 命令を格納するバッファ ALU Dispatch 命令フェッチ, デコード, リネーミング バックエンド ディスパッチ (dispatch) : 命令ウィンドウに命令を格納する動作 発行 (issue, fire) : 命令ウィンドウから, データ依存が解消された命令を機能ユニットに送り出す動作
Microsoft PowerPoint - ca ppt [互換モード]
![Microsoft PowerPoint - ca ppt [互換モード]](/thumbs/91/107496045.jpg "Microsoft PowerPoint - ca ppt [互換モード]")
大阪電気通信大学情報通信工学部光システム工学科 2 年次配当科目 コンピュータアルゴリズム 良いアルゴリズムとは 第 2 講 : 平成 20 年 10 月 10 日 ( 金 ) 4 限 E252 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ 第 1 講の復習
cmpsys15w07_os.ppt
情報システム論 第 7 週ソフトウェアシステム Operating System (part I) 根來 均 ソフトウェア (Software) とは プログラムと同義もしくは各種プログラムの総称 ソフトウェアは 記憶装置上などに 電子的にのみ (0/1 で記録された情報として ) 存在する ソフトウェアに対して 物理的に存在する CPU 等の各種装置をハードウェア Hardware と呼ぶ 例えば
PowerPoint Presentation
最適化手法 第 回 工学部計数工学科 定兼邦彦 http://researchmap.jp/sada/resources/ 前回の補足 グラフのある点の隣接点をリストで表現すると説明したが, 単に隣接点の集合を持っていると思ってよい. 互いに素な集合のデータ構造でも, 単なる集合と思ってよい. 8 3 4 3 3 4 3 4 E v 重み 3 8 3 4 4 3 {{,},{3,8}} {{3,},{4,}}
Microsoft PowerPoint - DA2_2017.pptx
1// 小テスト内容 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I) 1 1 第 章の構成. 単一始点最短路問題 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 1 1 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ
Microsoft PowerPoint - DA2_2018.pptx
1//1 データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (I). 単一始点最短路問題 第 章の構成 単一始点最短路問題とは 単一始点最短路問題の考え方 単一始点最短路問題を解くつのアルゴリズム ベルマン フォードのアルゴリズム トポロジカル ソートによる解法 ダイクストラのアルゴリズム 単一始点最短路問題とは 単一始点最短路問題とは 前提 : 重み付き有向グラフ 特定の開始頂点 から任意の頂点
PowerPoint プレゼンテーション
多分岐選択 条件式 If Then Else IIF Select Switch 今日の目的 Dim n As Long n = 10 If n = 10 Then 条件式 Debug.Print ゆっくりしていってね! End If 比較演算子 その他 よく使用する演算子 文字列型にたいする条件式 条件式 オブジェクト型 バリアント型に対する条件式 比較演算子 = 等しい 等しくない >=
Microsoft Word - 3new.doc
プログラミング演習 II 講義資料 3 ポインタ I - ポインタの基礎 1 ポインタとは ポインタとはポインタは, アドレス ( データが格納されている場所 ) を扱うデータ型です つまり, アドレスを通してデータを間接的に処理します ポインタを使用する場合の, 処理の手順は以下のようになります 1 ポインタ変数を宣言する 2 ポインタ変数へアドレスを割り当てる 3 ポインタ変数を用いて処理 (
Microsoft PowerPoint - while.ppt
本日の内容 繰り返し計算 while 文, for 文 例題 1. 自然数の和例題 2. 最大公約数の計算例題 3. ベクトルの長さ while 文例題 4. 九九の表 for 文と繰り返しの入れ子例題 5. ド モアブルの公式計算誤差の累積 今日の到達目標 繰り返し (while 文, for 文 ) を使って, 繰り返し計算を行えるようになること ループカウンタとして, 整数の変数を使うこと 今回も,
メソッドのまとめ
メソッド (4) 擬似コードテスト技法 http://java.cis.k.hosei.ac.jp/ 授業の前に自己点検以下のことがらを友達に説明できますか? メソッドの宣言とは 起動とは何ですか メソッドの宣言はどのように書きますか メソッドの宣言はどこに置きますか メソッドの起動はどのようにしますか メソッドの仮引数 実引数 戻り値とは何ですか メソッドの起動にあたって実引数はどのようにして仮引数に渡されますか
Microsoft PowerPoint - 13approx.pptx
I482F 実践的アルゴリズム特論 13,14 回目 : 近似アルゴリズム 上原隆平 (uehara@jaist.ac.jp) ソートの下界の話 比較に基づく任意のソートアルゴリズムはΩ(n log n) 時間の計算時間が必要である 証明 ( 概略 ) k 回の比較で区別できる場合の数は高々 2 k 種類しかない n 個の要素の異なる並べ方は n! 通りある したがって少なくとも k n 2 n!
本サンプル問題の著作権は日本商工会議所に帰属します また 本サンプル問題の無断転載 無断営利利用を厳禁します 本サンプル問題の内容や解答等に関するお問 い合わせは 受け付けておりませんので ご了承ください 日商プログラミング検定 STANDARD(VBA) サンプル問題 知識科目 第 1 問 ( 知
本サンプル問題の著作権は日本商工会議所に帰属します また 本サンプル問題の無断転載 無断営利利用を厳禁します 本サンプル問題の内容や解答等に関するお問 い合わせは 受け付けておりませんので ご了承ください 日商プログラミング検定 STANDARD(VBA) サンプル問題 知識科目 第 1 問 ( 知識 4 択 :20 問 ) 1. ユーザが行った操作を記録して同じ操作を自動で行うことができる機能を何というか
program7app.ppt
プログラム理論と言語第 7 回 ポインタと配列, 高階関数, まとめ 有村博紀 吉岡真治 公開スライド PDF( 情報知識ネットワーク研 HP/ 授業 ) http://www-ikn.ist.hokudai.ac.jp/~arim/pub/proriron/ 本スライドは,2015 北海道大学吉岡真治 プログラム理論と言語, に基づいて, 現著者の承諾のもとに, 改訂者 ( 有村 ) が加筆修正しています.
計算機アーキテクチャ
計算機アーキテクチャ 第 11 回命令実行の流れ 2014 年 6 月 20 日 電気情報工学科 田島孝治 1 授業スケジュール ( 前期 ) 2 回日付タイトル 1 4/7 コンピュータ技術の歴史と コンピュータアーキテクチャ 2 4/14 ノイマン型コンピュータ 3 4/21 コンピュータのハードウェア 4 4/28 数と文字の表現 5 5/12 固定小数点数と浮動小数点表現 6 5/19 計算アーキテクチャ
オペレーティングシステム 2014
オペレーティングシステム 2019/6/13 海谷治彦 1 目次 安全性 生存性 干渉 デッドロック 2 互いに邪魔しない点からの性質 安全性 (safety): 好ましくない状態にならない 干渉 (interfere) がおきない. デッドロック (dead lock) が無い. 生存性 (liveness): やろうとしたことは, いつかは処理される. 永遠に待たされることは無い 例えば高層ビルに多数のエレベータがあるが,
RH850の割り込み/例外実現方法 CC-RHアプリケーションガイド
RH850の割り込み / 例外実現方法 CC-RH アプリケーションガイド R20UT3546JJ0101 2018.10.12 ソフトウェア開発統括部 ソフトウェア技術部ルネサスエレクトロニクス株式会社 アジェンダ 概要ページ 03 割り込み / 例外発生時に実行する関数の定義ページ 10 直接ベクタ方式のベクタの定義ページ 17 テーブル参照方式のベクタの定義ページ 25 その他 割り込み制御ページ
書式に示すように表示したい文字列をダブルクォーテーション (") の間に書けば良い ダブルクォーテーションで囲まれた文字列は 文字列リテラル と呼ばれる プログラム中では以下のように用いる プログラム例 1 printf(" 情報処理基礎 "); printf("c 言語の練習 "); printf
情報処理基礎 C 言語についてプログラミング言語は 1950 年以前の機械語 アセンブリ言語 ( アセンブラ ) の開発を始めとして 現在までに非常に多くの言語が開発 発表された 情報処理基礎で習う C 言語は 1972 年にアメリカの AT&T ベル研究所でオペレーションシステムである UNIX を作成するために開発された C 言語は現在使われている多数のプログラミング言語に大きな影響を与えている
マニュアル訂正連絡票
< マニュアル訂正連絡票 > FUJITSU Software ASP システムコマンド集 V29 [J2K0592001A] 2018 年 12 月 25 日発行 修正箇所 ( 章節項 ): STRRDAT コマンドの CAPCNV のオペランド説明 CAPCNV( 整数型 ): 英小文字変換モードを指定する. @YES: 英小文字を英大文字に変換する. @NO: 英小文字をエラーにする. CAPCNV(
Taro-スタック（公開版）.jtd
0. 目次 1. 1. 1 配列によるの実現 1. 2 再帰的なデータ構造によるの実現 1. 3 地図情報処理 1. 4 問題 問題 1 グラフ探索問題 - 1 - 1. は データの出し入れが一カ所で行われ 操作は追加と削除ができるデータ構造をいう 出入口 追加 削除 操作 最初 111 追加 111 222 追加 111 222 333 追加 111 222 333 444 追加 111 222
POSIXプログラミング Pthreads編
POSIXプログラミング Pthreads 編 デジタルビジョンソリューション 中山一弘佐藤史明 参考図書 Pthreads プログラミング, Bradford Nichols, Dick Buttlar, Jacqeline Proulx Farrell, ISBN4-900900-66-4 Pthreads POSIX スレッド標準を実装したライブラリを Pthreads と呼ぶ C 言語のデータ型
フローチャートの書き方
アルゴリズム ( 算法 ) 入門 1 プログラムの作成 機械工学専攻泉聡志 http://masudahp.web.fc2.com/flowchart/index.html 参照 1 何をどのように処理させたいのか どのようなデータを入力し どのような結果を出力させるのか問題を明確にする 2 問題の内容どおりに処理させるための手順を考える ( フローチャートの作成 )~アルゴリズム( 算法 ) の作成
Microsoft PowerPoint - DA2_2019.pptx
Johnon のアルゴリズム データ構造とアルゴリズム IⅠ 第 回最大フロー 疎なグラフ, 例えば E O( V lg V ) が仮定できる場合に向いている 隣接リスト表現を仮定する. 実行時間は O( V lg V + V E ). 上記の仮定の下で,Floyd-Warhall アルゴリズムよりも漸近的に高速 Johnon のアルゴリズム : アイデア (I) 辺重みが全部非負なら,Dikra
第10回 コーディングと統合（WWW用）.PDF
10 January 8, 2004 algorithm algorithm algorithm (unit testing) (integrated testing) (acceptance testing) Big-Bang (incremental development) (goto goto DO 50 I=1,COUNT IF (ERROR1) GO TO 60 IF (ERROR2)
2015_collabo_04
Cortex-M にも広がってきたマルチコアプログラミング ~ARM コア搭載東芝汎用マイコン無料コラボセミナー 2015~ 株式会社エーアイコーポレーション TOPPERS グループ はじめに ~ARM コア搭載東芝汎用マイコン無料コラボセミナー 2015~ 2015/2/9 A. I. Corporation 2 講演内容 Cortex-A だけでなく Cortex-M においてもマルチコアを搭載した汎用マイコンが登場してきています
※ ポイント ※
4S-RO ロボティクス実験 参考資料 ファイル入出力 : ファイルの読み込み 1 周目に計測した生体情報データを読み込み プログラムにより信号処理を行うが その際にファイルの 入出力が必要となる 実験前半ですでに学習しているが必要に応じて本資料を参考にすること 以下のようにすると指定したファイルを読み込むことができる ( 詳細は後から記述 ) int i; double --------; char
Microsoft PowerPoint - pc11.ppt
本日の内容 コンピュータのしくみ ( 第 11 回 ) 9 章 オペレーティングシステム (OS) 中田明夫 ( 情報科学研究科 ) ( コンピュータのしくみ H17 第 11 回 ) 1 ( コンピュータのしくみ H17 第 11 回 ) 2 復習 : コンピュータの構成 ソフトウェアとハードウェア 復習 : ハードウェアの構成 複数の構成要素からなる コンピュータ ハードウェア ソフトウェア ハードウェア
PowerPoint Presentation
様相論理と時相論理 Kripke 構造 K = S, R, L S: 状態の集合 ( 無限かもしれない ) R: 状態間の遷移関係 R S S L: 状態から命題記号の集合への写像 L(s) は 状態 s S において成り立つ命題記号の集合を与える Kripke 構造 K = S, R, L G = S, R 有向グラフ Kripke 構造 K = S, R, L L : S 2 Atom Atom
プログラミング基礎
C プログラミング Ⅰ 条件分岐 : if 文, if~else 文 条件分岐 条件分岐とは ある条件が成立したときとしないときで処理の内容を変更する場合に応じた, 複雑な処理を行うことができる 条件分岐 yes 成績が良かったか? no ご褒美に何か買ってもらう お小遣いが減らされる C 言語では,if 文,if~else 文,if~else if~else 文,switch 文で条件分岐の処理を実現できる
Microsoft PowerPoint - sp ppt [互換モード]
![Microsoft PowerPoint - sp ppt [互換モード]](/thumbs/74/69816956.jpg "Microsoft PowerPoint - sp ppt [互換モード]")
// システムプログラム概論 メモリ管理 () 今日の講義概要 ページ管理方式 ページ置換アルゴリズム 第 5 講 : 平成 年 月 日 ( 月 ) 限 S 教室 中村嘉隆 ( なかむらよしたか ) 奈良先端科学技術大学院大学助教 y-nakamr@is.naist.jp http://narayama.naist.jp/~y-nakamr/ // 第 5 講メモリ管理 () ページング ( 復習
プレポスト【解説】
コース名 : シェルの機能とプログラミング ~UNIX/Linux の効率的使用を目指して ~ 1 UNIX および Linux の主な構成要素は シェル コマンド カーネルです プロセスとは コマンドやプログラムを実行する単位のことなので プロセスに関する記述は誤りです UNIX および Linux のユーザーインターフェースは シェル です コマンドを解釈するという機能から コマンドインタープリタであるともいえます
3 PAD p.2/88
3 PAD 20050023 faculty@soi.wide.ad.jp Δ N205 2005 3 PAD p.1/88 http://www.soi.wide.ad.jp/ 3 PAD p.2/88 1: 2: PAD (Problem Analysis Diagram) 3: PAD 3 PAD p.3/88 TIPS? 3 PAD p.4/88 Cricket 1 (+ ) 1 (+ )
PowerPoint プレゼンテーション
ループ ループとは? ある条件を満たすまで 指定の命令を繰り返す Do... Loop For Next For Each Next While WEnd ループの種類 Do Loop Do While 条件 ステートメント Loop Do ステートメント Loop While 条件 Do Until 条件 ステートメント Loop Do ステートメント Until Loop 条件 Do Loop
第２回
第 4 回基本データ構造 1 明星大学情報学科 2 3 年前期 アルゴリズムとデータ構造 Ⅰ 第 4 回 Page 1 配列 スタック キューとその操作 4-1. 配列とその操作 配列型 同じ型の変数を並べたもの 配列にする型は 基本型 配列型 構造体 ポインタいずれでもよい 要素の並べ方を 次元 という 1 次元配列 ( 直線状 ) 2 次元配列 ( 平面状 ) 3 次元配列 ( 立体状 ) a[5]
Microsoft PowerPoint - mp11-06.pptx
数理計画法第 6 回 塩浦昭義情報科学研究科准教授 shioura@dais.is.tohoku.ac.jp http://www.dais.is.tohoku.ac.jp/~shioura/teaching 第 5 章組合せ計画 5.2 分枝限定法 組合せ計画問題 組合せ計画問題とは : 有限個の もの の組合せの中から, 目的関数を最小または最大にする組合せを見つける問題 例 1: 整数計画問題全般
Microsoft Word - VBA基礎(6).docx
あるクラスの算数の平均点と理科の平均点を読み込み 総点を計算するプログラムを考えてみましょう 一クラスだけ読み込む場合は test50 のようなプログラムになります プログラムの流れとしては非常に簡単です Sub test50() a = InputBox(" バナナ組の算数の平均点を入力してください ") b = InputBox(" バナナ組の理科の平均点を入力してください ") MsgBox
Microsoft PowerPoint - OS07.pptx
この資料は 情報工学レクチャーシリーズ松尾啓志著 ( 森北出版株式会社 ) を用いて授業を行うために 名古屋工業大学松尾啓志 津邑公暁が作成しました 主記憶管理 主記憶管理基礎 パワーポイント 27 で最終版として保存しているため 変更はできませんが 授業でお使いなる場合は松尾 (matsuo@nitech.ac.jp) まで連絡いただければ 編集可能なバージョンをお渡しする事も可能です 復習 OS
4 分岐処理と繰返し処理 ( 教科書 P.32) プログラムの基本的処理は三つある. (1) 順次処理 : 上から下に順番に処理する ぶんきそろ (2) 分岐処理 : 条件が揃えば, 処理する はんぷく (3) 反復処理 : 条件が揃うまで処理を繰り返す 全てのプログラムは (1) から (3) の
4 分岐処理と繰返し処理 ( 教科書 P.32) プログラムの基本的処理は三つある. (1) 順次処理 : 上から下に順番に処理する ぶんきそろ (2) 分岐処理 : 条件が揃えば, 処理する はんぷく (3) 反復処理 : 条件が揃うまで処理を繰り返す 全てのプログラムは (1) から (3) の組み合わせで作れる. ここでは (2) と (3) について扱う. 4.1 分岐処理 4.1.1 if
xl 1 program Othello6; 2 {$APPTYPE CONSOLE} 3 uses SysUtils; 4 5 type 6 TMasuNo = 0..99; // 7 TYouso = (Soto,Kara,Kuro,Siro); // 8 TBan = array [TMasu
xl 1 program Othello6; 2 {$APPTYPE CONSOLE 3 uses SysUtils; 4 5 type 6 TMasuNo = 0..99; // 7 TYouso = (Soto,Kara,Kuro,Siro); // 8 TBan = array [TMasuNo] of TYouso; // 10 10 9 TPlayer = Kuro..Siro; // 10
Microsoft PowerPoint - 11.pptx
ポインタと配列 ポインタと配列 配列を関数に渡す 法 課題 : 配列によるスタックの実現 ポインタと配列 (1/2) a が配列であるとき, 変数の場合と同様に, &a[0] [] の値は配列要素 a[0] のアドレス. C 言語では, 配列は主記憶上の連続領域に割り当てられるようになっていて, 配列名 a はその配列に割り当てられた領域の先頭番地となる. したがって,&a[0] と a は同じ値.
Microsoft PowerPoint - 03_What is OpenMP 4.0 other_Jan18
OpenMP* 4.x における拡張 OpenMP 4.0 と 4.5 の機能拡張 内容 OpenMP* 3.1 から 4.0 への拡張 OpenMP* 4.0 から 4.5 への拡張 2 追加された機能 (3.1 -> 4.0) C/C++ 配列シンタックスの拡張 SIMD と SIMD 対応関数 デバイスオフロード task 構 の依存性 taskgroup 構 cancel 句と cancellation
gengo1-8
問題提起その 1 一文字ずつ文字 ( 数字 ) を読み込み それぞれの文字が何回入力されたかを数えて出力するプログラム int code, count_0=0, count_1=0, count_2=0, count_3=0,..., count_9=0; while( (code=getchar())!= EOF ){ } switch(code){ case 0 : count_0++; break;
TopSE並行システム はじめに
はじめに 平成 23 年 9 月 1 日 トップエスイープロジェクト 磯部祥尚 ( 産業技術総合研究所 ) 2 本講座の背景と目標 背景 : マルチコア CPU やクラウドコンピューティング等 並列 / 分散処理環境が身近なものになっている 複数のプロセス ( プログラム ) を同時に実行可能 通信等により複数のプロセスが協調可能 並行システムの構築 並行システム 通信 Proc2 プロセス ( プログラム
文法と言語
一昨年の CPU (ARM の一種 ) Nvidia 社製 Tegra 3 の省電力技術 4-PLUS-1 メインである 4 つのコアに加え 低性能 低消費電力のコンパニオンコアを状況に応じて活用する技術 端末のパフォーマンスが必要なときは 4 つのコアから必要な数のコアを使い 不要なときは低消費電力のコンパニオンコアだけで動作して全体の消費電力を削減する ビデオ再生時では最大 61% Web 閲覧では最大
PowerPoint プレゼンテーション
コンピュータアーキテクチャ 第 13 週 割込みアーキテクチャ 2013 年 12 月 18 日 金岡晃 授業計画 第 1 週 (9/25) 第 2 週 (10/2) 第 3 週 (10/9) 第 4 週 (10/16) 第 5 週 (10/23) 第 6 週 (10/30) 第 7 週 (11/6) 授業概要 2 進数表現 論理回路の復習 2 進演算 ( 数の表現 ) 演算アーキテクチャ ( 演算アルゴリズムと回路
メモリ管理
メモリ管理 (2) 思い出そ ~~ う 物理アドレスと論理アドレス 論理アドレス空間 アドレス変換 メモリ管理ユニット (MMU) ページ ページテーブル,TLB 保護違反, ページフォルト ページング APP CPU OS OS が提供するメモリ関連 API (1) 1. 論理アドレス空間生成 = プロセスの生成 プロセスの作成 ( プログラムの起動 ) 2. 論理的なメモリ ( 仮想メモリ )
arduino プログラミング課題集 ( Ver /06/01 ) arduino と各種ボードを組み合わせ 制御するためのプログラミングを学 ぼう! 1 入出力ポートの設定と利用方法 (1) 制御( コントロール ) する とは 外部装置( ペリフェラル ) が必要とする信号をマイ
arduino プログラミング課題集 ( Ver.5.0 2017/06/01 ) arduino と各種ボードを組み合わせ 制御するためのプログラミングを学 ぼう! 1 入出力ポートの設定と利用方法 (1) 制御( コントロール ) する とは 外部装置( ペリフェラル ) が必要とする信号をマイコンから伝える 外部装置の状態をマイコンで確認する 信号の授受は 入出力ポート 経由で行う (2) 入出力ポートとは?
10-vm1.ppt
オペレーティングシステム ~ 仮想記憶 (1) ~ 山田浩史 hiroshiy @ cc.tuat.ac.jp 2015/06/19 OS の目的 裸のコンピュータを抽象化 (abstraction) し より使いやすく安全なコンピュータとして見せること OS はハードウェアを制御し アプリケーションの効率的な動作や容易な開発を支援する OS がないと メモリをアプリケーション自身が管理しなければならない
ソフトウェア基礎技術研修
算術論理演算ユニットの設計 ( 教科書 4.5 節 ) yi = fi (x, x2, x3,..., xm) (for i n) 基本的な組合せ論理回路 : インバータ,AND ゲート,OR ゲート, y n 組合せ論理回路 ( 復習 ) 組合せ論理回路 : 出力値が入力値のみの関数となっている論理回路. 論理関数 f: {, } m {, } n を実現.( フィードバック ループや記憶回路を含まない
Microsoft PowerPoint - DA2_2017.pptx
// データ構造とアルゴリズム IⅠ 第 回単一始点最短路 (II)/ 全点対最短路 トポロジカル ソート順による緩和 トポロジカル ソート順に緩和 閉路のない有向グラフ限定 閉路がないならトポロジカル ソート順に緩和するのがベルマン フォードより速い Θ(V + E) 方針 グラフをトポロジカル ソートして頂点に線形順序を与える ソート順に頂点を選び, その頂点の出辺を緩和する 各頂点は一回だけ選択される
1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 5 3. 4. 5. A0 (1) A, B A B f K K A ϕ 1, ϕ 2 f ϕ 1 = f ϕ 2 ϕ 1 = ϕ 2 (2) N A 1, A 2, A 3,... N A n X N n X N, A n N n=1 1 A1 d (d 2) A (, k A k = O), A O. f
データ構造
アルゴリズム及び実習 3 馬青 1 バブルソート 考え方 : 隣接する二つのデータを比較し データの大小関係が逆のとき 二つのデータの入れ替えを行って整列を行う方法である 2 バブルソートの手順 配列 a[0],a[1],,a[n-1] をソートする場合 ステップ 1: 配列 a[0] と a[1],a[1] と a[2],,a[n-2] と a[n-1] と となり同士を比較 ( 大小が逆であれば
問題1 以下に示すプログラムは、次の処理をするプログラムである
問題 1 次のプログラムの出力結果を a~d の中から選べ public class Problem1 { int i=2; int j=3; System.out.println("i"+j); a) 23,b) 5,c) i3,d) ij 問題 2 次のプログラムの出力結果を a~d の中から選べ public class Problem2 { int a=6; if((a>=2)&&(a
次に示す数値の並びを昇順にソートするものとする このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 次に末尾側から 2 番目と 3 番目の 1
4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる
COMET II のプログラミング ここでは機械語レベルプログラミングを学びます 1
COMET II のプログラミング ここでは機械語レベルプログラミングを学びます 1 ここでは機械命令レベルプログラミングを学びます 機械命令の形式は学びましたね機械命令を並べたプログラムを作ります 2 その前に プログラミング言語について 4 プログラミング言語について 高級言語 (Java とか C とか ) と機械命令レベルの言語 ( アセンブリ言語 ) があります 5 プログラミング言語について
Microsoft PowerPoint - 説柔5_間勊＋C_guide5ï¼›2015ã•’2015æŒ°æŁŽæš’å¯¾å¿œç¢ºèª“æ¸‹ã†¿ã•‚.pptx
情報ネットワーク導入ユニット Ⅰ C 言語 配列 5 章 : 配列同じ型 (int, double など ) の変数の集まりを 番号 ( 添字 ) で管理する変数 int vc[5]; // 要素数が 5 の配列 vc[0] = 1; vc[1] = 2; vc[2] = 3; vc[3] = 4; vc[4] = 5; printf("vc[0] = %d n", vc[0] ); printf("vc[1]
人工知能入門
藤田悟 黄潤和 探索とは 探索問題 探索解の性質 探索空間の構造 探索木 探索グラフ 探索順序 深さ優先探索 幅優先探索 探索プログラムの作成 バックトラック 深さ優先探索 幅優先探索 n 個の ueen を n n のマスの中に 縦横斜めに重ならないように配置する 簡単化のために 4-ueen を考える 正解 全状態の探索プログラム 全ての最終状態を生成した後に 最終状態が解であるかどうかを判定する
ただし 無作為にスレッドを複数実行すると 結果不正やデッドロックが起きる可能性がある 複数のスレッド ( マルチスレッド ) を安全に実行する ( スレッドセーフにする ) ためには 同期処理を用いるこ とが必要になる 同期処理は 予約語 synchronized で行うことができる ここでは sy
オブジェクト指向プログラミング演習 2010/10/27 演習課題 スレッド ( その 2) 同期処理 結果不正 デッドロック 前回のスレッドの演習では 複数のスレッドを実行し 一つのプログラムの中の違う処理を同時に実行し た ただし 無作為にスレッドを複数実行すると 結果不正やデッドロックが起きる可能性がある 複数のスレッド ( マルチスレッド ) を安全に実行する ( スレッドセーフにする )
Microsoft PowerPoint - os ppt [互換モード]
![Microsoft PowerPoint - os ppt [互換モード]](/thumbs/95/126317907.jpg "Microsoft PowerPoint - os ppt [互換モード]")
2. プロセス 概要 マルチプログラミング プロセスの管理 スケジューリング方式 2008/5/13 プロセス 1 複数の仕事を処理する つの 法 論 執筆メール処理データ整理会議 論 執筆論 執筆論 執筆論 執筆 時間 メール処理メール処理メール処理メール処理 仕事が捗るのはどちらの方法か 人を待たせないのはどちらか データ整理 データ整理 データ整理 データ整理 会議 会議 会議 2008/5/13
情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤
情報工学実験 C コンパイラ第 2 回説明資料 (2017 年度 ) 担当 : 笹倉 佐藤 2017.12.7 前回の演習問題の解答例 1. 四則演算のできる計算機のプログラム ( 括弧も使える ) 2. 実数の扱える四則演算の計算機のプログラム ( 実数 も というより実数 が が正しかったです ) 3. 変数も扱える四則演算の計算機のプログラム ( 変数と実数が扱える ) 演習問題 1 で行うべきこと
Microsoft PowerPoint - No3.ppt
OS を支援するプロセッサ機能 プロセッサの動作モード 割込み (Interrupt)/ 例外 (Exception) 入出力装置との並列動作 マルチプログラミング (multi-programming) OS の機能 : ユーザプログラムの実行制御の管理 コンピュータ資源の管理 管理するためには 特権 が必要 プロセッサの動作モード 特権モード = OS の実行モード ( カーネルモード, スーハ
Developer Camp
2F Delphi/C++ チュートリアルセッション Delphi でキカイを制御する アプリケーションの設計とテクニック 株式会社イマジオム代表取締役 高木太郎 1 はじめに この講演の内容 制御プログラムというもの 制御プログラム設計のポイント 制御プログラム実装のテクニック 3 どんなものを考えているのか? 例 :3 次元プリンタ ここに入っている PC がシステム全体を制御 3 次元プリンタ原理
演算増幅器
ファイルこれまでにデータの入力方法として キーボードからの入力を用いてきた 構造体を習った際に実感してもらえたと思うが 入力データ量が多いときにはその作業は大変なものとなり 入力するデータを間違えた場合には最初からやり直しになる そこで今回はこれらの問題を解決するため あらかじめ入力データをテキストエディタなどで編集し ファイルとして保存したものを入力データとして用いる方法を習っていく さらにプログラムで作成したデータをファイルに出力する方法も併せて習っていく
1. A0 A B A0 A : A1,...,A5 B : B1,...,B
1. A0 A B A0 A : A1,...,A5 B : B1,...,B12 2. 3. 4. 5. A0 A B f : A B 4 (i) f (ii) f (iii) C 2 g, h: C A f g = f h g = h (iv) C 2 g, h: B C g f = h f g = h 4 (1) (i) (iii) (2) (iii) (i) (3) (ii) (iv) (4)
プログラミング基礎
C プログラミング Ⅰ 授業ガイダンス C 言語の概要プログラム作成 実行方法 授業内容について 授業目的 C 言語によるプログラミングの基礎を学ぶこと 学習内容 C 言語の基礎的な文法 入出力, 変数, 演算, 条件分岐, 繰り返し, 配列,( 関数 ) C 言語による簡単な計算処理プログラムの開発 到達目標 C 言語の基礎的な文法を理解する 簡単な計算処理プログラムを作成できるようにする 授業ガイダンス
Taro-リストⅠ（公開版）.jtd
0. 目次 1. 再帰的なデータ構造によるリストの表現 1. 1 リストの作成と表示 1. 1. 1 リストの先頭に追加する方法 1. 1. 2 リストの末尾に追加する方法 1. 1. 3 昇順を保存してリストに追加する方法 1. 2 問題 問題 1 問題 2-1 - 1. 再帰的なデータ構造によるリストの表現 リストは データの一部に次のデータの記憶場所を示す情報 ( ポインタという ) を持つ構造をいう
sinfI2005_VBA.doc
sinfi2005_vba.doc MS-ExcelVBA 基礎 (Visual Basic for Application). 主な仕様一覧 () データ型 主なもの 型 型名 型宣言文字 長さ 内容 整数型 Integer % 2 バイト -32,768 32,767 長整数型 Long & 4 バイト -2,47,483,648 2,47,483,647 単精度浮動小数点数 Single 型!
PowerPoint Presentation
算法数理工学 第 2 回 定兼邦彦 クイックソート n 個の数に対して最悪実行時間 (n 2 ) のソーティングアルゴリズム 平均実行時間は (n log n) 記法に隠された定数も小さい in-place ( 一時的な配列が必要ない ) 2 クイックソートの記述 分割統治法に基づく 部分配列 A[p..r] のソーティング. 部分問題への分割 : 配列 A[p..r] を 2 つの部分配列 A[p..q]
本文ＡＬＬ.indd
Intel Xeon プロセッサにおける Cache Coherency 時間の性能測定方法河辺峻田口成美古谷英祐 Intel Xeon プロセッサにおける Cache Coherency 時間の性能測定方法 Performance Measurement Method of Cache Coherency Effects on an Intel Xeon Processor System 河辺峻田口成美古谷英祐
040402．ユニットテスト
2. ユニットテスト ユニットテスト ( 単体テスト ) ユニットテストとはユニットテストはプログラムの最小単位であるモジュールの品質をテストすることであり その目的は結合テスト前にモジュール内のエラーを発見することである テストは機能テストと構造テストの2つの観点から行う モジュールはプログラムを構成する要素であるから 単体では動作しない ドライバとスタブというテスト支援ツールを使用してテストを行う
Microsoft Word - 実験4_FPGA実験2_2015
FPGA の実験 Ⅱ 1. 目的 (1)FPGA を用いて組合せ回路や順序回路を設計する方法を理解する (2) スイッチや表示器の動作を理解し 入出力信号を正しく扱う 2. スケジュール項目 FPGAの実験 Ⅱ( その1) FPGAの実験 Ⅱ( その2) FPGAの実験 Ⅱ( その3) FPGAの実験 Ⅱ( その4) FPGAの実験 Ⅱ( その5) FPGAの実験 Ⅱ( その6) FPGAの実験 Ⅱ(
nlp1-04a.key
自然言語処理論 I. 文法 ( 構文解析 ) その 構文解析 sytctic lysis, prsig 文の構文的な構造を決定すること句構造文法が使われることが多い文法による構文木は一般に複数ある 構文木の違い = 解釈の違い 構文解析の目的 句構造文法の規則を使って, 文を生成できる構文木を全て見つけだすこと 文法が入力文を生成できるかどうかを調べるだけではない pro I 構文解析とは 構文木の違い