オペレーティングシステムスケジューリングアルゴリズム解析
4939 ワード
先着順サービススケジューリングアルゴリズム
先行サービス(First Come First Serviced,FCFS)は、ジョブスケジューリングにもプロセススケジューリングにも適用される簡単なスケジューリングアルゴリズムです.先行サービスアルゴリズムは、ジョブまたはプロセス
先着順サービススケジューリングアルゴリズム
プロセス名
到着時間(開始時間)
じっこうじかん
終了時間
かいてんじかん
P1
0
9
9
20
P2
0.4
4
13
5
P3
1
1
14
1
P4
5.5
4
18
6
P5
7
2
20
2
先来先サービススケジューリングアルゴリズム分析
時間/s
0
P 1が到着し、P 1が実行される(期間実行9 s)
0.4
P 2到着、P 2未実行、P 1実行中(残り8.6 s)
1
P 3到着、P 2未実行、P 3未実行、P 1(残り7.6 s)
5.5
P 4到着、P 2未実行、P 3未実行、P 1(残り3.5 s)
7
P 5到着、P 5未実行、P 4未実行、P 2未実行、P 3未実行、P 1(残り2 s)
9
P 1が終了し、P 2が運転を開始する(期間実行4 s)
13
P 2が終了し、P 3が運転を開始する(期間実行1 s)
14
P 3が終了し、P 4が運転を開始する(期間4 s実行)
18
P 4が終了し、P 5が運転を開始する(期間実行2 s)
20
P 4終了
提案する必要がある点は、このスケジューリングアルゴリズムのスケジューリングプロセスは、まずジョブを探したり、プロセスの中で最初に来たりするものであり、つまり、これは`到着時間`を見て、到着時間が早ければ早いほど、最初にスケジューリングを行い、注意すべきは、このスケジューリングアルゴリズムは`サービス`が1つのジョブやプロセスを完了した後、`サービス`次のジョブやプロセスである.
ショートジョブ優先スケジューリングアルゴリズム
ショートジョブ優先スケジューリングアルゴリズム(Shortest Job First,SJF)またはショートプロセススケジューリングアルゴリズム(Shortest Process First,SPF)は、ショートジョブまたはショートプロセス優先スケジューリングのアルゴリズムである.ここで、ジョブまたはプロセスの長さは、ジョブまたはプロセス要求
ショートジョブ優先スケジューリングアルゴリズム
プロセス名
到着時間(開始時間)
じっこうじかん
終了時間
かいてんじかん
P1
0
9
20
20
P2
0.4
4
5.4
5
P3
1
1
2
1
P4
5.5
4
11.5
6
P5
7
2
9
2
ショートジョブ優先スケジューリングアルゴリズム解析
時間/s
0
P 1到着、P 1実行
0.4
P 2到着、P 2実行、P 1ストップ(残り8.6 s)
1
P 3到着、P 2ストップ(残り3.4 s)、P 3実行
2
P 3終了、P 2実行
5.4
P 2が終了し、P 1が実行される
5.5
P 4到着、P 1ストップ(残り8.5 s)、P 4運転
7
P 5到着、P 5運転、P 4停止(残り2.5 s)
9
P 5終了、P 4運転
11.5
P 4終了、P 1運転
20
P 1終了
注意すべき時、短いジョブ(プロセス)優先スケジューリングアルゴリズムは確かに`実行時間の長さ`によって測定される.つまり、実行時間が短い人は、まずどの`ジョブ`または`プロセス`をスケジューリングします.しかし、これは、最初にスケジューリングされた`ジョブ`または`プロセス`を実行した後に他の`ジョブ`または`プロセス`をスケジューリングすることを意味するものではなく、本当のスケジューリングプロセスは交差して行われる.全体の順序はやはり到着した時間から最初に到着したジョブやプロセスからスケジューリングを開始し、例えば本例では、P 1が到着した後、直ちに実行し、P 1のスケジューリングが完了する前に、P 2が到着し、直ちに実行し(このとき、P 1が停止)、順次類推する.上記の表-**短いジョブ(プロセス)優先スケジューリングアルゴリズム分析**は、十分に明確であると信じています.
優先度スケジューリングアルゴリズム
優先度スケジューリングアルゴリズムでは、優先度は、ジョブまたはプロセスが享受するスケジューリング優先度を表すために使用されます.このアルゴリズムの鍵は、プロセスまたはジョブの優先度を決定することです.優先度は、静的優先度と動的優先度の2つに分類されます.
静的優先度
静的メソッドは、ジョブまたはプロセスの静的特性に基づいて、ジョブまたはプロセスの実行が開始される前に優先度を決定し、実行が開始されると変更できません.次の表の優先順位の高いものが最優先です
プロセス名
到着時間(開始時間)
じっこうじかん
ゆうせんど
終了時間
かいてんじかん
P1
0
10
3
24
24
P2
0
6
5
6
6
P3
0
2
2
26
26
P4
0
4
1
30
30
P5
0
8
4
14
14
プロセスの実行:
このアルゴリズムでは,単純な計算のために5つのジョブが同時にコミットされたと仮定し,いずれも0時点でコミットする.全体の過程は`先来先サービスアルゴリズム`とよく似ており、1つのジョブを先に実行した後、別のジョブのスケジューリングを行う.ただスケジューリング順測定の基準が`優先数`に変わりました.優先数の大きさについては,問題によって与えられる基準が異なり,最小優先数で優先するものもあれば,最大優先であるものもあり,ここでは議論しない.
タイムスライスローテーション
タイムスライスローテーション法(Round−Robin,RRアルゴリズム)は主に時間分割システムにおける
以下の表では、タイムスライス長が2 msである.
プロセス名
到着時間
じっこうじかん
開始時間
終了時間
かいてんじかん
A
0
10
0
30
30
B
0
6
2
22
20
C
0
2
4
6
2
D
0
4
6
16
10
E
0
8
8
28
20
このアルゴリズムでは,タイムスライス回転法を1つのキューと見なし,キューの前の先でスケジューリングを行うことができるが,先来先サービスアルゴリズムとは異なり,各プロセスは交差して行われる.従来のサービスアルゴリズムでは、**はジョブ(プロセス)**全体をスケジューリングした後、他のジョブまたはプロセスをスケジューリングします.上の時間軸から分かるように、いずれも`1タイムスライスサイズの時間(ここでは2 ms)`にスケジューリングを行い、1つのプロセススケジューリングが完了するまで、上の時間軸から明らかなように、各プロセスの到着時間と開始時間も異なる.この点は前のいくつかのアルゴリズムとも少し違います.
説明
文章が終わらないうちに、後続のアルゴリズムが更新され続けます.
先行サービス(First Come First Serviced,FCFS)は、ジョブスケジューリングにもプロセススケジューリングにも適用される簡単なスケジューリングアルゴリズムです.先行サービスアルゴリズムは、ジョブまたはプロセス
に従ってスケジューリングされる.ジョブ・スケジュールでこのアルゴリズムを使用すると、スケジュールのたびにバックアップ・キューから最初にキューに入るジョブを選択し、メモリに呼び出し、プロセスを作成し、対応するリソースを割り当て、ジョブのプロセスを準備キューに入れます.プロセススケジューリングでこのアルゴリズムを使用する場合、各スケジューリングは、準備キューから最新のキューに入るプロセスを選択し、プロセッサを割り当てます.先着順サービススケジューリングアルゴリズム
プロセス名
到着時間(開始時間)
じっこうじかん
終了時間
かいてんじかん
P1
0
9
9
20
P2
0.4
4
13
5
P3
1
1
14
1
P4
5.5
4
18
6
P5
7
2
20
2
先来先サービススケジューリングアルゴリズム分析
時間/s
0
P 1が到着し、P 1が実行される(期間実行9 s)
0.4
P 2到着、P 2未実行、P 1実行中(残り8.6 s)
1
P 3到着、P 2未実行、P 3未実行、P 1(残り7.6 s)
5.5
P 4到着、P 2未実行、P 3未実行、P 1(残り3.5 s)
7
P 5到着、P 5未実行、P 4未実行、P 2未実行、P 3未実行、P 1(残り2 s)
9
P 1が終了し、P 2が運転を開始する(期間実行4 s)
13
P 2が終了し、P 3が運転を開始する(期間実行1 s)
14
P 3が終了し、P 4が運転を開始する(期間4 s実行)
18
P 4が終了し、P 5が運転を開始する(期間実行2 s)
20
P 4終了
提案する必要がある点は、このスケジューリングアルゴリズムのスケジューリングプロセスは、まずジョブを探したり、プロセスの中で最初に来たりするものであり、つまり、これは`到着時間`を見て、到着時間が早ければ早いほど、最初にスケジューリングを行い、注意すべきは、このスケジューリングアルゴリズムは`サービス`が1つのジョブやプロセスを完了した後、`サービス`次のジョブやプロセスである.
ショートジョブ優先スケジューリングアルゴリズム
ショートジョブ優先スケジューリングアルゴリズム(Shortest Job First,SJF)またはショートプロセススケジューリングアルゴリズム(Shortest Process First,SPF)は、ショートジョブまたはショートプロセス優先スケジューリングのアルゴリズムである.ここで、ジョブまたはプロセスの長さは、ジョブまたはプロセス要求
によって測定される.ショートジョブ優先スケジューリングアルゴリズム
プロセス名
到着時間(開始時間)
じっこうじかん
終了時間
かいてんじかん
P1
0
9
20
20
P2
0.4
4
5.4
5
P3
1
1
2
1
P4
5.5
4
11.5
6
P5
7
2
9
2
ショートジョブ優先スケジューリングアルゴリズム解析
時間/s
0
P 1到着、P 1実行
0.4
P 2到着、P 2実行、P 1ストップ(残り8.6 s)
1
P 3到着、P 2ストップ(残り3.4 s)、P 3実行
2
P 3終了、P 2実行
5.4
P 2が終了し、P 1が実行される
5.5
P 4到着、P 1ストップ(残り8.5 s)、P 4運転
7
P 5到着、P 5運転、P 4停止(残り2.5 s)
9
P 5終了、P 4運転
11.5
P 4終了、P 1運転
20
P 1終了
注意すべき時、短いジョブ(プロセス)優先スケジューリングアルゴリズムは確かに`実行時間の長さ`によって測定される.つまり、実行時間が短い人は、まずどの`ジョブ`または`プロセス`をスケジューリングします.しかし、これは、最初にスケジューリングされた`ジョブ`または`プロセス`を実行した後に他の`ジョブ`または`プロセス`をスケジューリングすることを意味するものではなく、本当のスケジューリングプロセスは交差して行われる.全体の順序はやはり到着した時間から最初に到着したジョブやプロセスからスケジューリングを開始し、例えば本例では、P 1が到着した後、直ちに実行し、P 1のスケジューリングが完了する前に、P 2が到着し、直ちに実行し(このとき、P 1が停止)、順次類推する.上記の表-**短いジョブ(プロセス)優先スケジューリングアルゴリズム分析**は、十分に明確であると信じています.
優先度スケジューリングアルゴリズム
優先度スケジューリングアルゴリズムでは、優先度は、ジョブまたはプロセスが享受するスケジューリング優先度を表すために使用されます.このアルゴリズムの鍵は、プロセスまたはジョブの優先度を決定することです.優先度は、静的優先度と動的優先度の2つに分類されます.
静的優先度
静的メソッドは、ジョブまたはプロセスの静的特性に基づいて、ジョブまたはプロセスの実行が開始される前に優先度を決定し、実行が開始されると変更できません.次の表の優先順位の高いものが最優先です
プロセス名
到着時間(開始時間)
じっこうじかん
ゆうせんど
終了時間
かいてんじかん
P1
0
10
3
24
24
P2
0
6
5
6
6
P3
0
2
2
26
26
P4
0
4
1
30
30
P5
0
8
4
14
14
プロセスの実行:
P2 P5 P1 P3 P4
|—————————|——————————————|———————————————————|———|——————————|————>
0 6 14 24 26 30
このアルゴリズムでは,単純な計算のために5つのジョブが同時にコミットされたと仮定し,いずれも0時点でコミットする.全体の過程は`先来先サービスアルゴリズム`とよく似ており、1つのジョブを先に実行した後、別のジョブのスケジューリングを行う.ただスケジューリング順測定の基準が`優先数`に変わりました.優先数の大きさについては,問題によって与えられる基準が異なり,最小優先数で優先するものもあれば,最大優先であるものもあり,ここでは議論しない.
タイムスライスローテーション
タイムスライスローテーション法(Round−Robin,RRアルゴリズム)は主に時間分割システムにおける
スケジューリングに用いられる.ローテーションスケジューリングの実現原理はシステムがすべての準備プロセスを先入先出の原則に従って1つのキューに並べて、新しく来たプロセス準備キューの末尾、プロセススケジューリングを実行するたびに、準備キューのキューのキューの最初のプロセスはいつも先にスケジューリングプログラムに選択されて、CPUの上で を実行した後、システムのタイマーはクロックを出して中断して、スケジューリングプログラムはスケジューリングを行って、プロセスの実行を停止し、準備キューの最後に挿入します.その後、プロセスの切り替えを行い、CPUを準備キューの先頭プロセスに分けて、同じようにタイムスライスを実行させ、このように往復させる.回転法の原理図は以下の通りである.以下の表では、タイムスライス長が2 msである.
プロセス名
到着時間
じっこうじかん
開始時間
終了時間
かいてんじかん
A
0
10
0
30
30
B
0
6
2
22
20
C
0
2
4
6
2
D
0
4
6
16
10
E
0
8
8
28
20
A B C D E A B D E A B E A E A
|————|————|————|————|————|————|————|————|————|————|————|————|————|————|————|————>
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30このアルゴリズムでは,タイムスライス回転法を1つのキューと見なし,キューの前の先でスケジューリングを行うことができるが,先来先サービスアルゴリズムとは異なり,各プロセスは交差して行われる.従来のサービスアルゴリズムでは、**はジョブ(プロセス)**全体をスケジューリングした後、他のジョブまたはプロセスをスケジューリングします.上の時間軸から分かるように、いずれも`1タイムスライスサイズの時間(ここでは2 ms)`にスケジューリングを行い、1つのプロセススケジューリングが完了するまで、上の時間軸から明らかなように、各プロセスの到着時間と開始時間も異なる.この点は前のいくつかのアルゴリズムとも少し違います.
説明
文章が終わらないうちに、後続のアルゴリズムが更新され続けます.