先着順予約とは何ですか？学習者の今日は、先着順CPUスケジューリングというオペレーティングシステムで非常に重要なトピックについて、理論的な概念とコードの実装を理解するつもりです。
コードの実装に入る前に、まず先着順の意味について理解しましょう。
先着順の紹介
First Come First Serve (FCFS) は、オペレーティングシステムにおける最も簡単で単純なCPUスケジューリングアルゴリズムで、プロセスが到着した順に自動的に実行されます。
このタイプのアルゴリズムでは、最初にCPUを要求したプロセスが、最初に完全な実行のためのCPUを取得します。
この方法は性能が低く、一般的な待ち時間はかなり長くなります。
実際の例を見てみましょう。
-
- アミューズメント・パーツのチケットを買うために行列している人たち
- バス停でバスを待つ人
さて、CPUスケジューリングでは、以下のような時間値の計算が必要となる。
- 1.終了時間：プロセスが完全に実行された後、いつCPUから離れたか。
- 2.ターンアラウンドタイム：プロセスの到着時間と終了時間の差。
-
- 待機時間：プロセスのバースト/実行時間とターンアラウンドタイムとの差。
これらに加えて、プロセスの平均待ち時間も計算できる。
先着順の図解
到着時刻と実行時刻が異なる4つのプロセスがある場合を考えてみましょう。
データは下表のように表示されます。
| プロセスID｜到着時間｜バースト/実行時間｜P1｜0｜4｜1 | ||
| P1 | 0 | 4 |
| P2 | 1 | 5 |
| P3 | 2 | 5 |
| P4 | 3 | 3 |
4種類のプロセスの到着時間とバースト時間ここで、終了時間、ターンアラウンドタイム、待ち時間など、異なる時間値を計算する必要があります。
以下のタイムチャートを見て、様々な時間値を分析・計算することができる。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
print("FIRST COME FIRST SERVE SCHEDULLING")
n= int(input("Enter number of processes : "))
d = dict()
for i in range(n):
key = "P"+str(i+1)
a = int(input("Enter arrival time of process"+str(i+1)+": "))
b = int(input("Enter burst time of process"+str(i+1)+": "))
l = []
l.append(a)
l.append(b)
d[key] = l
d = sorted(d.items(), key=lambda item: item[1][0])
ET = []
for i in range(len(d)):
# first process
if(i==0):
ET.append(d[i][1][1])
# get prevET + newBT
else:
ET.append(ET[i-1] + d[i][1][1])
TAT = []
for i in range(len(d)):
TAT.append(ET[i] - d[i][1][0])
WT = []
for i in range(len(d)):
WT.append(TAT[i] - d[i][1][1])
avg_WT = 0
for i in WT:
avg_WT +=i
avg_WT = (avg_WT/n)
print("Process | Arrival | Burst | Exit | Turn Around | Wait |")
for i in range(n):
print(" ",d[i][0]," | ",d[i][1][0]," | ",d[i][1][1]," | ",ET[i]," | ",TAT[i]," | ",WT[i]," | ")
print("Average Waiting Time: ",avg_WT)
|
ここで、プロセスの終了時間はそれぞれ4,9,14,17です。
プロセスのターンアラウンドタイムは、それぞれ4,8,12,14です。
そして同様に、プロセスの待ち時間はそれぞれ0,3,7,11です。
最後に平均待ち時間を計算すると、5.25 となる。
それでは、FCFSプロセスの実装に移りましょう。
この記事もチェック：Pythonによるグラフ理論の実装|頂点や辺の表示や追加のやり方を解説
PythonでFCFSを実装する
FIRST COME FIRST SERVE SCHEDULLINGEnter number of processes : 4
Enter arrival time of process1: 1
Enter burst time of process1: 5
Enter arrival time of process2: 0
Enter burst time of process2: 4
Enter arrival time of process3: 3
Enter burst time of process3: 3
Enter arrival time of process4: 2
Enter burst time of process4: 5
Process | Arrival | Burst | Exit | Turn Around | Wait | P2 | 0 | 4 | 4 | 4 | 0 |
P1 | 1 | 5 | 9 | 8 | 3 |
P4 | 2 | 5 | 14 | 12 | 7 |
P3 | 3 | 3 | 17 | 14 | 11 |
Average Waiting Time: 5.25
|
サンプル出力
FCFSの長所と短所
では、そのメリットについて見ていきましょう。
先着順のメリット
- プログラミングが容易
- CPUスケジューリングアルゴリズムの最も単純な形
先着順のデメリット
- 平均待ち時間が長い
- タイムシェアリングシステムには不向きな手法
- FCFSはあまり効率的ではない
まとめ
FCFS CPU スケジューリングとは何か、そして python プログラミング言語を使って同じものをどのように実装できるかがお分かりいただけたと思います。
このチュートリアルを気に入っていただけたでしょうか？読んでくれてありがとうございます。