スケジューリング班OJL_実装課題

課題内容

• ex_prioritization.pyの27行目にノードの実行順序を記述する
  
• makespan（全てのノードが実行完了するまでに時間）が一定値以下になったら、実行時にSucceed!表示がされる
  
• 課題用DAG1, 2両方で、それぞれSucceed!が出る実行順序を求める
  
  • 課題用DAG1のクリア基準makespan: 14
  • 課題用DAG2のクリア基準makespan: 13
  • 課題用DAG2はやや難です

課題が終わったら…（発展内容）

• Succeed!が出る実行順序の法則性を見つける
  • 法則性に則って自動で実行順序を決定するアルゴリズムを作る（これができたら研究レベル）
• make_random_dag()関数を使って適当なDAGを生成、実行順序を調べてみる
  • 法則性が正しいかを調べてみる（法則<適当になるか？）
• コードを読んでみる

課題プログラム実行方法

実行準備

// git clone またはzipをダウンロード、解凍
$ cd OJL_team_scheduling
$ bash setup.bash

また、python環境が必須です。

実行時

$ python3 ex_prioritization.py

課題プログラム出力

order:          [0, 1, 2, 3, 4, 5, 6, 7] # 入力実行順序
makespan:       16 # 全てのノードの実行完了までの時間
result:         Succeed!/Failed...
output:         output/scheduling_result_03251752.html # 実行結果の出力ファイル

output/scheduling_result_MMDDYYSS.htmlには、実際にスケジューラがどのようにノードを処理したかが描画されます。
隙間なく埋まっているほど、短いmakespanを示します。

課題用DAG

課題用DAG1

• G = make_template_dag() で呼び出し
• デフォルトの状態（実行順序[0, 1, 2, 3, 4, 5, 6, 7]）で実行するとmakespan: 16
  
• 目標のmakespan: 14
  

課題用DAG2

• G = make_template_dag2() で呼び出し
• デフォルトの状態（実行順序[0, 1, 2, 3, 4, 5, 6, 7, 8]）で実行するとmakespan: 14
  
• 目標のmakespan: 13
  

なお、どちらの課題も2つのコアを持つマルチコアプロセッサで実行するものとします。

ディレクトリ構成

.
├── README.md #このファイルです
├── ex_prioritization.py # 実行ファイルです
├── fig # README内の画像が格納されています
├── output # 結果ファイルの出力先です
├── requirements.txt
├── setup.bash # 環境設定のbashファイルです
└── src # ソースコードです（興味があったら読んでみてください）
   ├── lib # sched_sim.pyの依存ファイルです
   ├── make_dag.py # サンプルのDAGを生成するコードです
   ├── sched_sim.py # スケジューリングの実行を行うコードです
   └── scheduling_viewer.py # スケジューリング結果の可視化を行うコードです

ブランチ構成

• main # 出題用のブランチです
• additional # 発展課題のアルゴリズム実装のヒントが書かれています
• answer # 課題の答えと発展課題のアルゴリズムの実装が書かれています

FAQ

• raise AlgorithmErrorが出る
  • 実行順序が、ノードの順序制約を守っていない可能性が高いです

raise AlgorithmError(f'node {node_i} does not allocated.')
src.lib.exceptions.AlgorithmError: node 0 does not allocated.

• bash setup.bashが失敗する
  • 環境依存の関係があります。代わりに以下のコマンドを実行してください
  • $ pip3 install networkx
• 出力ファイルにグラフがない
  • スクロールバーでHTMLファイルの右側を探してみてください