Python 中的先来先服务调度 [FCFS]

作者

什么是先到先服务调度？嘿，学习者！今天我们将了解操作系统中一个非常重要的主题的理论概念和代码实现，该主题称为先来先服务 CPU 调度。

在跳转到代码实现之前，让我们首先了解先来先服务的含义。

先到先得简介

先来先服务（FCFS） 是操作系统中最简单的CPU调度算法，它按照进程到达的顺序自动执行进程。

在这种类型的算法中，首先请求CPU的进程首先获得CPU来完成它们的执行。这种方法性能较差，一般等待时间相当长。

让我们看一些现实生活中的例子：

  1. 人们排队等候购买游乐部分门票
  2. 人们在公交车站等车

现在在CPU调度中，我们需要计算一些时间值，如下所示：

  1. 退出时间：进程执行完毕后何时离开CPU。
  2. 周转时间：流程的到达和退出时间之间的差异。
  3. 等待时间：突发/执行时间与进程周转时间之间的差异。

除此之外，我们还可以计算进程的平均等待时间。

先来先服务的插图

让我们考虑这样一种情况：我们有 4 个具有不同到达时间和执行时间的进程。数据如下表所示：

进程号 到达时间 突发/执行时间
P1 0 4
P2 1 5
P3 2 5
P4 3 3
4个不同进程的到达时间和突发时间

现在我们需要计算不同的时间值，例如退出时间、周转时间和等待时间。您可以看看下面提到的时间图表并分析和计算各种时间值。

FCFS时间表

这里进程的退出时间分别是 4、9、14 和 17。流程的周转时间分别为 4、8、12 和 14。

同样，进程的等待时间分别为0、3、7、11。最后我们必须计算平均等待时间，结果为 5.25。

现在让我们转向 FCFS 进程的代码实现。

在 Python 中实现 FCFS

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)

样本输出

FIRST COME FIRST SERVE SCHEDULLING
 
Enter 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的优点和缺点

让我们看看一些优点

先到先得的优点

  1. 易于编程
  2. CPU 调度算法的最简单形式

先到先服务的缺点

  1. 平均等待时间较长
  2. 对于分时系统来说不是一种理想的技术
  3. FCFS效率不是很高

结论

我希望您现在清楚什么是 FCFS CPU 调度以及如何借助 python 编程语言来实现它。

希望您喜欢本教程！感谢您的阅读！快乐学习！😇