レポート作成上の注意
- OSはレポートの比重が非常に高い(60%)ので、毎回提出しないと単位がかなり厳しくなります。
- 提出期限を越えた場合は点数が半減(切り捨て)となります。期限日の授業開始前にTAに提出してください。
- 解答を公開した後は、一切受け取りません(期限後約一週間後を予定)。
- 教え合い・結果の相互確認はかまいませんが、明らかに他人のものを丸写ししている場合は、両方とも無効(0点)となります。
- レポート用紙はA4サイズを使用し、レポートの左上をホッチキスで留めて提出してください。推奨の表紙:.doc,.pdf
- 課題内容等の質問はTA（森下）までお願いします。
- 諸事情により期限までに終える事ができない場合（就活・留学等）は早めにTAまで連絡をお願いします。
第4回レポート課題
注意:第3回レポートはこの下にあります。第3回レポートの〆切は1月14日です。
- 問 提出期限:2009/1/21 試験開始まで
- 提出先:計算機ソフトウェア研究室2B622(10:00~19:00),試験開始前にTAに提出
●課題
問 CTL
あるシステムの動作を示したクリプケ構造がある。
問1 CTLによるモデル検査
以下のCTLをこのシステムが満たすかどうかを示せ(各2点)
- (1)EFω
- (2)EGφ
- (3)AF(E[ψUω])
問2 システムで成り立つCTL
上のシステムで成り立つCTLを3つ示せ。ただし、問1,3のCTLは除く(各1点)
問3 CTLの意味
CTLでは様々な性質を示すことができる。たとえばこのCTL
- AFψ
は「すべての動作はいつかψに到達する」ことを示しており、システムが目的の動作を行った後の状態をψとすると、このシステムは必ず目的の動作を完了できるかどうか検証することになる。
これをふまえて、以下のCTLの意味を答え、さらにどのようなモデル検査に使えるか示せ。なおこの問のCTLは上のシステムとは関係がない。(各3点)
- (1)AG¬ψ
- (2)AG(AFω)
●問題に対する捕捉
CTLの説明は講義だけでは大変だと思うので、CTLの解説を用意しました→PPT、PDF
問1 CTLによるモデル検査
まず、システムの動作を木構造で示し、その木構造に対して満たす満たさないの説明を加えよ。
問2 システムで成り立つCTL
基本的に何でも良いが、CTLの定義をBNFに以下に示すので、これに従ったものにすること。（ただし、pはCTL、APは原始命題(φ、ψ、ωのこと)）
p ::= AP | ¬p | p ∧ p | p ∨ p | EX p | AX p | EF p | AF p | EG p | AG p | E[ p U p ] | A[ p U p ]
問3 CTLの意味
「目的の動作」を行うのか行わないのかに着目すると良い。
(2)は難しいかもしれません。
●解答・解説
問1 CTLによるモデル検査
(1),(2),(3)ともに満たす。(1),(2)に関してはほぼ全員正解につき省略。(3)はE[ΨUω]をa->bのbに貼り付け、それに対し初期状態aからAF(E[ΨUω])を調べるため、満たす。この、入れ子の場合の中身はまず各状態に貼り付けてから評価するという点が理解できていないため、満たさないと解答した者もいた。
問2 システムで成り立つCTL
ほぼ全員正解であるが、Aを用いたときに、a->b->a->b->...があるため満たされないCTLを書いている者もいた。Eを用いれば簡単に解答できたと思う。
問3 CTLの意味
(1)
- Ψを目的の動作を「行わない」動作とし、AF¬Ψをシステムが目的の動作をするか検証すると答える（０点）
- Ψに到達せずに「完了できるか」（０点）
- これを満たせば、システムは目的の動作を完了できないと答える（０点）
- 「全て」の動作で目的の動作を「行わない」と答える（１点）
- Ψをエラーなど危険な状態と述べる（３点満点）
Ψに到達しないからと言って、目的の動作をすることができる、と答えるのは誤り。検証の目的として、Ψをエラー状態であると答えるところまで進めれば満点。
(2)
- AFωとの違いが分からない（１点）
- 「全ての動作」はいつか到達する（１点）
- 満たせば無限ループに陥る（２点）
- その目的の状態を終えた後でもまたいつかは目的の状態を満たせる（３点満点）
ωに到達したとしても、その状態ですらAFωを満たさなければならないため、ωに到達したことがゴールではない。何度でもωに到達できることを言えば満点。さらに、応答性について述べている者もいた。
第3回レポート課題
- 問1 提出期限:2009/1/14 授業開始まで（12月末に出題し忘れたため、延長）
- 問2 提出期限:2009/1/21 試験開始まで（問1の提出日しか記載していなかったため、第4回レポートにあわせてありますが、1月14日に提出するのが望ましい）
- 提出先:計算機ソフトウェア研究室2B622(10:00~19:00),講義・試験開始前にTAに提出
●課題
問1 リアルタイムシステムのスケジューラビリティ解析
今、あるリアルタイム（組込み）システムを設計するにあたり、実際にコーディングする前にスケジューラビリティを解析したい。つまり、現在の設定のまま実装するとシステムに不具合が出るかどうか、実装前に確かめたいという状況である。
このシステムが行う処理は、タスク１〜３の３つの周期タスクで実現され、また現段階での各タスクの設計パラメータは以下となっている。
| タスク | 優先度（Rate Monotonicで決定） | 処理にかかる時間 | デッドライン | 周期 |
| タスク1 | 3 | 10[ms] | 50[ms] | 50[ms] |
| タスク2 | 2 | 20[ms] | 70[ms] | 70[ms] |
| タスク3 | 1 | X[ms] | 200[ms] | 200[ms] |
- CPUが1つしかないため、同時に実行できるタスクは1つだけ（シングルコア）。
- 全てのタスクは、まず最初に起動される（Critical Instantから開始）。その後は周期の時間が経過する度に起動する。
- 優先度が高いタスクが起動すると、割り込まれた優先度が低いタスクは高いものが処理を終えるまで待機する（プリエンティブシステム）。
- 優先度は既にRate Monotonic（周期が短いほど優先）で決定済みである。実行中に優先度が変わることはない。
- タスクはそれぞれ独立している。あるタスクを実行するにあたり、他のあるタスクが実行済みかどうかは条件とならない（※割り込みの影響は受ける）。
- デッドラインは周期と一致している。つまり、次の起動までに処理が終わればよい。
- ハードリアルタイムシステムである。つまり、いずれかのタスクがデッドラインまでに処理を終えられなければそれは致命傷となり、システム全体が停止する。
- タスク3の処理にかかる時間Xについては後述。
問1-1 タスク3の最悪応答時間（WCRT）を計算することで、スケジュール可能か否かを判定せよ（3点×2）
ただし、タスク3の処理時間Xは以下の2通りとし、それぞれの場合について確認すること
| case 1 | X=101+自分の名列番号の一の位 |
| case 2 | X=91+自分の名列番号の一の位 |
問1-2 動作をシュミレーションする図を描き、スケジュール可能か否かを判定せよ（2点×2）
ただし、タスク3の処理時間Xは以下の2通りとし、それぞれの場合について確認すること。
| case 1 | X=101+自分の名列番号の一の位 |
| case 2 | X=91+自分の名列番号の一の位 |
問2 講義関連調査（5点）
以下の4つの事項から1つ選び、その原理や動向を調査し、自由に述べよ。
- ソフトウェアを検証する手法『モデル検査（model checking）』
- 動的再構成可能組込みシステム
- 組込みシステムにおけるオペレーティングシステム
- 組込みシステムのソフトウェア
●問題に対する補足
問1-1
- 計算問題なので計算過程は必須
- 得られた結論（スケジュール可能or不可能）の記述も忘れずに。
- case1で名列番号が10,20,30なら101に,15,25,35なら106という具合です。表紙に書く名列番号と一致させてください
- 最悪応答時間（あるいは最大レスポンス時間）の計算方法については講義資料に説明がありますが、以下の説明の方がわかりやすいかもしれません。
（Tnはタスクnの周期、Cnはタスクnの処理にかかる時間）
問1-2
- 得られた結論（スケジュール可能or不可能）の記述も忘れずに。
- スケジュール可能ではない場合はいずれかのタスクがデッドラインを超えてしまうところまでの処理の流れを、スケジュール可能である場合はすべてのタスクがデッドラインを超えることなく処理を一回以上無事に終えるところまでを描画してください。（※）
- 図のサンプルはこちら↓
- タスクの移動と処理の完了はそれぞれ↑と↓で表してください。無いと減点されます。
- 処理が切り替わるところは時間を明記してください。
- 時間の単位はmsです。
- プログラムによる解答も可能とします。入力、出力、言語等は各自特異な形で設定してください。ただし、WS室で動作することが好ましい。なにかあれば早めにTAまでお願いします。
※システムがCritial Instantな状況から処理を開始した場合は、これで安全を保証できる。
問2
- 調査・報告能力を問う。情報は多い方がよいが、紙一枚を超える分量は要求しない。
- 必ず参照した文献あるいはURLを列挙すること（数が多い場合は、別ページにする）。これが欠けている場合、無条件で0点となる。
- 2chやgoo、wikipediaのような、真偽が曖昧な情報源のみを参考に文章を書いている場合、低評価になる（書き手の素性や所属等がはっきりしている者が望ましい）。
- ○○○社が○○○のシステムで実際に活用した、などの具体的な情報を示すと高評価とする。
- 情報源が幅広いほど高評価になる。
●解答・解説
問1
case1がスケジュール不可能であり、case2がスケジュール可能になる
計算については省略。良くできていた。
問2
良くできていた。
問3
- 単一文献から少し引用したのみで貧弱（１点）
- 同一文献からの引用（２点）
- 複数文献から引用だが内容が貧弱（２点）
- 複数文献からまとめるが全体的に列挙しただけにとどまっている（３点）
- 複数文献からの引用をまとめる（４点）
- 複数文献からまとめ自分なりの展望を述べる（５点）
第2回レポート課題
- 問3のみ提出期限を一週間延ばしています。できれば一緒に提出するのが望ましいですが、問3のみ別途11月26日までに提出しても構いません。
- 問1,問2 提出期限:2008/11/19 授業開始まで
- 問3 提出期限:2008/11/26 授業開始まで
- 提出先:計算機ソフトウェア研究室2B622(10:00~19:00),講義開始前にTAに提出
●課題
今回の課題は3題あります. 合計点は20点です。
問1 プロデューサ／コンシューマ問題(10点)
1スロットのバッファにおけるプロデューサ／コンシューマ問題を考える。プロセスの数は、プロデューサが２つ（プロセス１と２）、コンシューマが２つ（プロセス３と４）の計４つとする。
これらの関係を図で描くと以下のようになる。
プロデューサ／コンシューマ問題イメージ
プロデューサ／コンシューマの処理内容は以下である。
プロデューサ／コンシューマ問題プログラム
これを、以下のような図で表すとする。ただし、↑で処理の到着を、↓で処理の完了を表す。
プロデューサ／コンシューマの処理内容の図
この図の中の、各処理の処理時間と処理内容は以下の通り。
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
| プロデューサの処理 | コンシューマの処理 |
最後に、今回用いるセマフォアのそれぞれの役割と初期値を示す。
- セマフォアA:プロデューサ間の排他制御に用いる。初期値は1
- セマフォアB:コンシューマ間の排他制御を用いる。初期値は1
- セマフォアS:バッファの空きスロット数を数えるのに用いる。初期値は1
- セマフォアM:バッファに入っているメッセージ数を数えるのに用いる。初期値は0
ここで、下記のcase1、case2それぞれの設定における、次のプロセスの優先度と到着時刻の場合のスケジュール図を示せ。ただし、優先度に関しては、数字の若い順に優先度が高いとする。（つまり、case1の優先度はプロセス２＞プロセス１＞プロセス３とする）
|
|
||||||||||||||||||||||||||||||
| case1(5点) | case2(5点) |
注意
- スケジュラ（ディスパッチャ）は、プリエンティブな（プリエンプションが発生する）優先度順スケジュリング方式とすること。
- 各セマフォア変数の変化と完了時刻を記述すること
- プロセスが実行していない時間帯はready（実行可能状態）かwait（待ち状態）と記述すること
例
問2 プロデューサ／コンシューマ問題の解法比較(5点)
教科書には「セマフォアを用いた解法」「モニタを用いた解法」「ＣＳＰを用いた解法」が掲載されているが、この3つの手法を比較せよ
問3 モニタ、CSPによる記述(5点+α)
以下の4題から1題以上選び、その解法を指定された方法で記述せよ。また、1題を完璧に解答することで5点得られる。2題以上解答されていた場合は、そのどちらも何らかのミスがあったとしても、理解できていると判断できれば5点得られる。
- (a)モニタによるリーダ／ライタ問題のライタ優先解
- (b)モニタによるダイニング・フィロソファ問題
- (c)CSPによるリーダ／ライタ問題
- (d)CSPによるダイニング・フィロソファ問題
ただし、モニタのライタ優先解などをどのように実装するかは各自に任せるものとし、どのように実装したかを必ず説明を添えること。また、変数を用いる場合は各変数について説明を添えること。またモニタ・CSPの記述の各文に説明が添えてあると採点者としてはありがたい。
●問題に対する補足
- 問1は前回同様平行プロセスを理解するための作業の問題です。得点しやすいと思います。
- 問2は教科書、講義資料から理解すれば解ける問題なので必ず得点してください。
- 問3は一度全ての問題を理解し、自分の得意になれそうなものについて解答してもらえれば良いと思います。モニタのリーダ／ライタ問題のリーダ優先解は教科書に書かれているため、それを参考にライタ優先解を考えるのが最も早く済むと思われます。
- 問3の「+α」に当たる点数は、2題以上良解答した場合に加算されるが、レポートの最大点数60点は変わらない。なお、「+α」される最大点数は5点とし、3問以上解答した場合に限る。
問1 プロデューサ／コンシューマ問題 の補足
- case1、case2の両方に解答してください。
- 前回、見直しをしていなかったのか、ミスが多く見られる解答もありました。今回は必ず見直しをしてください。
- プログラムによって解答することも認めます。その際には、実行環境に関しては前回の課題と同様とし、入力はいかなる形でも良いので各自用意し、各プロセスの各処理の終了時間を全て出力してください。
問2 プロデューサ／コンシューマ問題の解法比較 の補足
- それぞれの特徴・利点・欠点を簡潔に（数行）お願いします。
- 教科書と講義資料から自分なりにまとめたもので最高点を付けます。(つまり、教科書と講義資料以上の内容は求めない)
- ただし、ただの複写では点数を付けられないので、教科書の表現に従うにしても自分の表現で記述してください。
問3 モニタ、CSPによる記述 の補足
- 利用する各変数には、その説明を別途書き添えてください。
- 所詮疑似言語なので文法は意味の分かる程度で適当でかまいません。ちょっとした新しい文法を用いる場合は（変数の代入など）説明を加えてあれば使って貰ってかまわないません。ただし、各モニタ、CSPの記述の特徴を無視した記述は採点されません。
- モニタ、CSPの書き方は教科書を参考にしてください。
●この課題について受けた質問
この課題について受けた質問をここに掲載します。質問はTA（森下）まで。
- 問1:最後にバッファにデータが残るが構わないか……構いません。
○解答
問1
case 1(5点)
case 2(5点)
問2
セマフォアによる解法
- プロセス間の共通変数を用意し、P命令・V命令によりその値を参照させることで排他制御を実現する方法
- セマフォアは整数型であり、リソースの残存数を数えるなど応用が利く
モニタによる解法
- モニタがバッファを管理し、それを操作するためのプロセデュアを用意する方法
- 個々のプロセスにおいてリソースアクセスをコーディングする必要がない
- 各プロセスはプロセデュアを利用し、同時に動作するプロセスを１個に制限する
- 複数のモニタを用いる場合、モニタが別のモニタのプロセデュアうを呼ぶ多重呼び出しを行う。しかし、多重呼び出しではデットロックが生じる可能性がある
CSPによる解法
- 入出力をプログラミングの基本要素と見なし、あるプロセスの出力コマンドの実行完了を、同期する別のプロセスの入力コマンドが実行されるまで待たせることで、直接情報のやりとりをさせる方法
- 多くの問題に対して簡潔な解を提供できる
- バッファが存在しないため、転送は同期的に行われる必要がある。また、センダ・レシーバを直接名前で指定するために、プロセス名が固定されてしまう。さらには、プロセス数の上限を宣言しなくてはならないなど、プログラムに制限がかかる
問3
(a)モニタによるリーダ／ライタ問題のライタ優先解:例
readers_and_writers : monitor begin readercount : INTEGER ; busy : BOOLEAN ; OKtoread, OKtoweite : CONDITION ; procedure startwrite ; begin if readercount /= 0 or busy then OKtoweite.wait ; end if ; -- リーダが動作中または他のライタが動作している場合、待つ busy : true ; end startwrite ; procedure endwrite ; begin if OKtowrite.queue then OKtowrite.signal ; else if OKtoread.queue then OKtoread.signal ; end if ; end if ; -- ライタの待ち行列があればライタを一つ起動し、なければリーダを一つ起動する end endwrite ; procedure startwread ; begin if budy then OKtoread.wait ; end if ; -- ライタが動作していれば待つ readcount := readcount+1 ; if OKtoread.queue then OKtoread.signal ; end if ; -- リーダは一度起動すれば全て起動させる end startread ; procedure endread ; begin readercount := readercount -1 ; if readercount = 0 then OKtowrite.signal ; end if ; -- リーダが全て終了したらライタを起動 end endread ; readercount := 0 ; busy := false ; end readers_and_writers ;
(b),(c)については省略
○採点基準
問1
case1、case2、各5点。減点式。
- 実行可能状態（ready）に対する記述がない -3
- 理に２度目がある -2
- ・P命令で待ち状態（wait）になり、実行可能状態になって実行した際、再度同じP命令を行っている -1
- 他プロセスのV命令があっても待ち状態（wait）から実行可能状態（ready）になっていない -1
- セマフォアの値の記述がない -1
- セマフォアの値が0にもかかわらずP命令後待ち状態になっていない -2
- 実行可能状態（ready）にすべきところが待ち状態（wait）になっている -1
- 処理が途中で終わっている -3
- 優先度が守られていない -2
- 待った後にP命令を行っている（順序のミス） -1
- V命令が実行されていないにもかかわらず、P命令のwaitから抜けて動作している -2
- セマフォアMとSの取り違い（各セマフォアの意味を理解できていないと見なす） -2
問2
各解法を
A(3p) ... 各解法の本質が記述されている
B(2p) ... 動作の範囲で記述されている or 本質に触れているが不十分
C(1p) ... 動作にしても本質にしても不十分な内容が記述されてる or だいたい良いが誤りがある
D(0p) ... その解法に対する解説がない
で評価し、
9p ... 5点
7~8p ... 4点
5~6p ... 3点
4p ...2点
3p ... 1点
0~2p ... 0点
で点数を付けた。
セマフォアのBである理由
- セマフォアは共通変数であるという点に触れられていない
- 動作についてのみ記述されている
モニタのBである理由
- モニタがリソースを持ち、オブジェクトのように隠蔽し、プロセスはそれを利用するだけという概念が言及不足
- モニタとは何か書かれていない、伺える箇所がない
- 動作においてのみ記述されている
CSPのBである理由
- 同期について言及不足
- 入出力を元にしていることが言及不足
- 動作においてのみ記述されている
問3
各問、SABCで評価
S ... 各記法の特性を理解し、適した方法で簡潔に書かれている
A ... 各記法の特性を理解し、解法に誤りなく書かれている
B ... 各記法の書き方に乗っ取っているが、解法に誤りがある
C ... 各記法の書き方に誤りがある
D ... その解法ではない
1問のみ解答してある場合
A,S ... 5点
B ... 3点
C ... 1点
2問以上解答してある場合、最高評点で、まず、問3の点数を決める
A,S ... 5点
B ... 3点
C ... 1点
D ... 0点
問3の各問で、Sを3p、Aを1pとし、
9p~ ... +5点
7~8p ... +4点
5~6p ... +3点
4p ... +2点
2~3p ... +1点
0~1p ... 加算点なし
とする。
(a)モニタによるリーダ／ライタ問題のライタ優先解
S ... 該当なし
A ... write優先解になっている
B ... writeが同時書き込みを行なわれてしまう、waitのままになることがある
C ... ↑だけではなく、read中にwriteが起動してしまう
教科書のリーダ優先解では、ローカルデータ'busy'は「リソースが試用中か否か」を示しており、write時にのみ'true'になる。これはこの解がreadでは同時にreadを可能としているが、write時は同時に可能としていない事を示す。write時に複数のwriteやreadが存在しないことを示すのがリーダ／ライタ問題につき、writeが複数同時に行われるものはB評価とした。
(b)モニタによるダイニング・フィロソファ問題
S ... 工夫がある
A ... ダイニング・フィロソファ問題として動作する
B ... 上手く他の哲学者にsignalが伝播していない
C ... 該当なし
(c)CSPによるリーダ／ライタ問題
S ... 非常に簡潔に書かれている
A ... readercount,writercountを用いて解答している。
B ... ライタが一部しか書き換えていない
C ... リーダ／ライタ問題の解ではない
(d)CSPによるダイニング・フィロソファ問題
S ... 該当なし
A ... 哲学者と、フォーク全てをオブジェクトとして解答している
B ... 確かにダイニング・フィロソファとして動作するが、フォークをオブジェクトとしていない。哲学者とフォークの状態を管理していない。メッセージ通信が一切無い。
C ... ダイニング・フィロソファ問題の解ではない
○採点感想
- 問1についてはよくできていた。readyとwaitを混同している解答が数人。
- 問2については動作のみ記述し、手法の比較になっていない解答が多かった。であるが、全体的によくできていた。
- 問3(a)について、リーダ／ライタ問題を理解せずに解答している解答が多数見られた（ライタが複数起動しているものが代表例）。各解法の特性を上手く用いた解答をできているものは少なかった。
第1回レポート課題
- 提出期限:2008/10/22 授業開始まで
- 提出先:計算機ソフトウェア研究室2B622(10:00~19:00),講義開始前にTAに提出
●課題
問1 教科書P,47問2.7改題
教科書とは一部数値を変えています。ご注意ください。
教科書P,43図2.14のように、CPUと入出力チャネルで構成されている2個のサーバからなるシステムを考える。そして次のようなジョブを仮定する。
| ジョブ | CPU処理時間 | 入出力時間 | |
| ジョブ1 | 1番目のサイクル | 20秒 | 10秒 |
| 2番目のサイクル | 20秒 | 10秒 | |
| 3番目のサイクル | 20秒 | 10秒 | |
| 4番目のサイクル | 20秒 | ||
| ジョブ2 | 1番目のサイクル | 20秒 | 20秒 |
| 2番目のサイクル | 20秒 | 20秒 | |
| 3番目のサイクル | 20秒 | 20秒 | |
| 4番目のサイクル | 20秒 | ||
| ジョブ3 | 1番目のサイクル | 5秒 | 25秒 |
| 2番目のサイクル | 5秒 | 25秒 | |
| 3番目のサイクル | 5秒 | 25秒 | |
| 4番目のサイクル | 5秒 | ||
| ジョブ4 | 1番目のサイクル | 200秒 | 10秒 |
| 2番目のサイクル | 5秒 | 200秒 | |
| 3番目のサイクル | 100秒 | 100秒 | |
| 4番目のサイクル | 5秒 | ||
四つのジョブは既にシステムに存在するが、その到着順は1,2,3,4の順であると仮定して、以下のCPUスケジュリング方式に対するCPUの利用効率と、ターンアラウンドタイムの平均値を計算せよ。
- (a)FCFS
- (b)SPT
- (c)SRPT
- (d)クオンタムの大きさ5秒のRR
- (e)優先度がジョブ3,2,1,4の順の優先度順スケジュリング
- (f)優先度がジョブ4,1,2,3の順の優先度順スケジュリング
- (g)クオンタムの大きさ5の2段FB
- (h)入出力ジョブ優先
なお、入出力スケジュリング方式は常にFCFSを仮定することとする。
●問題に対する補足
スケジュリングに対する基本的な考えは以下の通りとします。
- 優先度がある場合は、待ち行列の中で最も高い優先度のジョブを実行する。(SPT、SRPT、入出力ジョブ優先は、各スケジュリングの考えに基づいて優先度が決定される)
- 優先度が同じ場合には、待ち行列の先頭のジョブを実行する。つまり、優先度が同じジョブの中では、待ち行列に到着した順に実行される。(注意として、ここでいう到着順とは、ジョブがシステムに現れた順ではなく、スケジュリング内で待ち行列に到着した順である。)
- CPU使用率は、4つのジョブの処理が全て完了した経過時間と、その間にCPUを使用した時間の比で計算される
- ターンアラウンドタイムは、ジョブが到着してから結果を受け取るまでの経過時間のことである。従って、今回の場合は「処理開始時(0秒の時点)」から「各ジョブの4サイクル目のCPU処理が完了するまで」の時間となる。
教科書の前提だけでは解釈により答えが変わってしまうので、さらに以下の条件を追加します。
- 入出力スケジュリング方式は常にFCFSと仮定する。つまり、I/O段階では到着順に先頭から処理していく。
- 新しいジョブと未完了ジョブ、新サイクルのジョブの待ち行列に到着した場合の待ち行列の並びは次のようになると仮定する。
- 新しいジョブ
- 新サイクルのジョブ
- 未完了のジョブ
- SPT方式、優先度順方式、入出力ジョブ優先方式はプリエンティブな(プリエンプションのある)方式とノンプリエンティブな方式の両方が考えられる(OS依存)が、今回のレポートでは以下とする。(プリエンプションについては教科書P,38参照)
- SPT方式……プリエンプションなし
- 優先度順方式……プリエンプションあり
- 入出力ジョブ優先……プリエンプションあり
●課題に対する補足
オペレーティングシステムの講義で毎回出題されている課題です。CPU、メモリといった限られた資源を複数のプロセス（ジョブ）に対してどうやって効率的に割り振るか、このOSの働きにより性能評価は変わってきます。この課題で、各方式の動作を実際に体感し、それぞれの長所・短所を確かめてください。
手計算により解答する場合は、必ず途中計算も提出してください。計算結果だけ提出されたのでは評価することができません。途中計算の例として教科書P,34[例2.4]のP,35図2.9を挙げておきます。
プログラムを作成して解答する場合は、自然研２号館２階ワークステーション室のコンピュータのlinuxコンソール上で実行、コンパイル可能なプログラムのソースを提出してください（c,c++,java,perl,ruby,php,python,mathematica,matlabは確認）。それ以外の言語や環境（JavaScript,BASIC,VBA,ActionScript,HSP等）を用いて行いたい場合はTAまで相談してください。このファイル(input1)を入力とし、正しい出力を行えるかどうかで判断します。入力は、ジョブの表を数値（1~9999の整数）の羅列にしたものです。出力は作業効率をパーセントで小数点一桁まで（切り捨て）、ターンアラウンドタイムの平均値も小数点一桁まで（切り捨て）出力してください。なお、出力例として、教科書P,47問2.7の入力（このファイル(input1sample)）に対する(a)FCFSの出力（このファイル(output1sample)）を挙げておきます。プログラムは１つのスケジュリング方式につき一つのプログラムコードを用意してください。プログラムはソースコードをTA宛にメールで送信してください（到着を確認次第、受理通知のメールを返信します。その日中の返信をします。返信がない場合は直接相談してください）。なお念のため、プログラムのコンパイル、実行方法も簡単に記してください。全ての課題をプログラムによって解かなくても、選んだ課題のみプログラムで解き、あとは手計算でもかまいません。
途中計算や結果が一部誤っているがこの課題に対する理解が十分であることが伺える解答については、満点、もしくは部分点とします。なお、このポリシーについては提出締め切り後、解答状況より判断し、解答例とともに公開します。
この課題には例年それなりの時間がかかります。期限前日に行うのは危険です。ご注意ください。
●注意（ヒント）
- 教科書P,34[例2.4]が参考になる。
- 各ジョブは、CPU→I/O→CPU→I/O→CPU→I/O→CPUの順で処理を要求する(問題では、CPU→I/Oで1サイクルとしている)。したがって、(a)FCFS方式であれば、CPUはジョブ１のサイクル１、ジョブ２のサイクル１、ジョブ３のサイクル１、……の順で処理することになる。
- また、同ジョブは前の処理が完了するまで次の処理に移れない。つまり、初期状態からなら、最初のCPU処理が完了するまでI/O処理は実行できない。
- 各ジョブは独立しており、ジョブ間での処理に関する関係は存在しないとする。つまり、あるジョブが１番目のサイクルの処理を完了していなくても、他のジョブは２番目以降のサイクルの処理を実行できる。
- SPRTはプリエンプションを用いるSPTの変形であり、新しいジョブが到着するたびサービス中のものも含めて、待ち行列に並んでいる各ジョブの現サイクルの残っている処理時間に従いSPTでスケジュリングする。その際、残っている処理時間が同じ場合は、上に書いた待ち行列の並びになるが、残っている時間が最短なものにCPU処理を行っていたものがある場合は、プリエンプションされずそのままCPU処理を続ける。
- 入出力ジョブ優先方式は、CPU時間累積と入出力時間の累積の比で入出力ジョブを識別する。そのため、各サイクルごとではなく、各ジョブ単位ではじめに優先度を与えるとする。
下線部の補足：下線部は、つまり、新しくジョブが到着しスケジュリングされるとき、CPU処理を行っていたジョブのそのサイクルでの残り時間より、処理時間が短いものがあれば、プリエンプションされるが、他のジョブの処理時間が全て同じかそれ以上なら、そのまま処理を続けることを意味する。要約すると、SPRTにおいて残りの処理時間が最短のジョブが複数存在した場合、その中での実行順は以下の通りになる。
- たった今までCPUで実行中だったジョブ（まだ待ち行列に入っていない＝まだ未完了ジョブになっていない）
- 待ち行列の中の、新しいジョブ
- 待ち行列の中の、新サイクルのジョブ
- 待ち行列の中の、未完了のジョブ（今よりも前にプリエンプションされていたもの）
SPRTは新しいジョブが到着するたび、残っている処理時間に従いSPTでスケジュリングする。そのときCPUT処理を行っていたジョブは、まだプリエンプションされておらず、スケジュリングの結果、残り処理時間がより短いジョブがあった場合に、プリエンプションされ未完了ジョブとなる。
●この課題について受けた質問
この課題について受けた質問をここに掲載します。質問はTA（森下）まで。
- 「2段のFF」の2段とは？……待ち行列が２つ、つまり教科書P,37図2.10(d)で言えば、n=1ということになります。
- SPTは一度各ジョブの全サイクルを合計した処理時間を優先度の判断に使うのか？……違います。本問におけるSPTは待ち行列に入っている各ジョブのサイクルに対して、各サイクルの処理時間を優先度の判断に用いるものとします。
- 「CPU時間累積と入出力時間の累積の比で入出力ジョブを識別する」とあるが、時間が累積していない一番最初のサイクル時の優先度は考慮せず、そのままジョブ1から始めればよいのか？1サイクル目のI/O処理を終えジョブが帰ってきた際に、未処理のジョブがCPUに待ち行列にあったとき、優先度はどうなるのか？……今回の問題は、事前にCPU処理時間と入出力時間が分かっている例です。よってその分かっている時間を用いて、ジョブの開始時に比を計算して優先度を付け、その優先度で最後までスケジュリングを行ってください。また、累積を計算してやってみたい場合は、足りないポリシーを解答に添えてもらえれば、そのポリシーが入出力ジョブ優先方式の考えに外れていなければ、それで採点をします。（ポリシーの例：最初のサイクル時はCPU時間累積と入出力時間の累積の比を1と換算する、CPU時間累積と入出力時間の累積の比は各サイクルの最初に計算する、など）
- RRとFBが同じ結果にならないか……なりません。聞いてみると、RRにおいて、新サイクルのジョブ、未完了のジョブが待ち行列の最後に着くというのが理解されていなかったようでした。
- 間違った解答に対する返答→次のサイクルへ進むには入出力を完了しなければなりません。
- 入出力時間優先方式で、累積時間を計算してやってみる場合のポリシーとして「全サイクルの"残り"CPU処理時間、入出力処理時間を利用する」のは正しいか？……正しくないと思います。本来ならば入出力処理優先方式はCPU処理時間、入出力時間が分からないので、処理が進み次第処理時間を計測していって判断する、というものです。よって、なるべく多くの計測サンプルが欲しい中で、"既に処理を終えたから省く"というのは、概念としてあっていないと思います。ただし、「200秒より以前の測定は信用しない」等のポリシーはあるかもしれません。
○解答
| 問 | CPUの利用効率(％) | ターンアラウンドタイムの平均値(s) |
| (a)FCFS | 66.7 | 682.5 |
| (b)SPT | 66.7 | 512.5 |
| (c)SRPT | 61.3 | 327.5 |
| (d)クオンタムの大きさ5秒のRR | 61.3 | 376.3 |
| (e)優先度がジョブ3,2,1,4の順の優先度順スケジュリング | 61.3 | 328.8 |
| (f)優先度がジョブ4,1,2,3の順の優先度順スケジュリング | 67.1 | 692.5 |
| (g)クオンタムの大きさ5の2段FB | 61.3 | 363.8 |
| (h)入出力ジョブ優先 | 66.7 | 546.3 |
○採点基準
- 15点満点。減点式。
- 全問解答していない場合、量に合わせて-15~-5。
- プリエンプションの概念なし -5
- プリエンプションを反映すべき問で反映していない -3
- ジョブとサイクルの考え方誤り -5
- 新しいサイクルのジョブが待ち行列の一番後ろにいっていない 軽度-1,重度-3
- RRにて、現在実行中のジョブの残り時間と新サイクルのジョブの実行時間が等しいにもかかわらず、新サイクルのジョブをプリエンプションして実行している -3
- 新しいサイクルのジョブと未完了のジョブが同時に到着した場合、新しいサイクルのジョブが先に待ち行列に入る、が守られていない -2
- ターンアラウンドタイムの計算方法が誤っている 軽度-1,重度-3
- SPTの考え方を誤る -2
- FBの2段の考え方を誤る -2
- I/O処理がFCFSではない -3
- 明らかなミスの連発（CPU処理が終了していないにもかかわらず、I/O処理が開始する等） ３つ目から-1
○採点感想
- CPU処理が終わっていないにもかかわらず、I/O処理を始めてしまったミスが多数。またその逆もあり。それが数カ所であり、他では理解できているようであれば、とくに減点はしなかった。
- ターンアラウンドタイムの計算方法を、サイクル３が終了時点での時間を利用している者が多数見られた。
- RRについて、新サイクルのジョブが、待ち行列の一番後ろではなく、一番前に来ている例が見られた。FBの2段目の待ち行列でも同様。図の通り、待ち行列の一番後ろに来ます。通常、優先度が付けられないジョブに対して、RRやFBを行う場合が多い。
- 新サイクルのジョブと未完了のジョブが同時に到着した際の優先順を誤っている者がいた。今回の問題設定をよく見てください。
- プログラムによる解答は１人。
|
OS2008 講義資料 |
OS2008 |
OS2008 試験情報 |