先来先服务调度CPU进程调度

在本教程中，我们将学习CPU进程调度算法中的一个重要概念。重要的概念名称是首次到达先服务。这是每个学生必须学习的基本算法，以了解CPU进程调度算法的所有基础知识。

首次到达先服务为理解其他算法铺平了道路。这个算法可能有很多缺点。但是这些缺点创造了非常新颖和高效的算法。因此，我们有责任学习关于首次到达先服务的CPU进程调度算法。

重要缩写

1. CPU – – – > 中央处理器
2. FCFS – – – > 首次到达先服务
3. AT – – – > 到达时间
4. BT – – – > 执行时间
5. WT – – – > 等待时间
6. TAT – – – > 周转时间
7. CT – – – > 完成时间
8. FIFO – – – > 先进先出

首次到达先服务

首次到达先服务的CPU调度算法简称FCFS是CPU进程调度算法的第一个算法。在首次到达先服务算法中，我们所做的是允许进程按线性方式执行。

这意味着无论哪个进程先进入就绪队列，都会首先执行。这表明首次到达先服务算法遵循先进先出（FIFO）原则。

首次到达先服务算法可以以抢占和非抢占方式执行。在进入示例之前，让我们了解一下CPU进程调度中的抢占和非抢占方法。

抢占方法

在抢占式进程调度的情况下，操作系统将资源分配给进程一段预定的时间。在资源分配过程中，进程从运行状态转换到就绪状态或从等待状态转换到就绪状态。这种切换是因为CPU可能会赋予其他进程优先级并用优先级更高的进程替换当前活动的进程。

非抢占方法

在非抢占式进程调度的情况下，不能在进程完成运行之前从进程中撤回资源。当运行的进程完成并转换到等待状态时，资源被切换。

首次到达先服务中的护航效应

护航效应是发生在名为首次到达先服务（FCFS）调度算法中的调度算法的一种现象。首次到达先服务调度算法以非抢占的方式进行。

非抢占的方式意味着如果一个进程或作业开始执行，那么操作系统必须完成其进程或作业。直到进程或作业为零，新的进程或作业才开始执行。在操作系统的术语中，非抢占调度的定义意味着中央处理器（CPU）将完全专用于首先启动的进程或作业的结束，并且只有在旧进程或作业完成之后才执行新的进程或作业。

可能会有一些情况导致中央处理器（CPU）分配太多时间。这是因为在首次到达先服务调度算法的非抢占方式中，进程或作业按序选择。因此，较短的作业或进程在较大的作业或进程后面花费了太多时间来完成执行。因此，等待时间，周转时间，完成时间非常长。

所以，如果第一个进程很大或完成时间太长，那么在先来先服务算法中会发生这种车队效应。

让我们假设较长的作业需要无限的时间来完成。那么，剩下的进程必须等待同样无限的时间。由于较长作业所创建的车队效应，等待进程的饥饿度会非常迅速地增加。这是FCFS CPU进程调度的最大缺点。

FCFS CPU进程调度的特点

FCFS CPU进程调度的特点是：

1. 实现简单。
2. 使用时不会引起任何因果关系。
3. 采用非抢占和抢占策略。
4. 按照接收到的顺序运行每个程序。
5. 到达时间被用作程序的选择标准。

FCFS CPU进程调度的优势

FCFS CPU进程调度的优势是：

1. 为了分配进程，它使用先进先出队列。
2. FCFS CPU调度过程简单直接，易于实现。
3. 在FCFS情况下的抢占调度中，没有进程饥饿的机会。
4. 由于没有考虑进程优先级，它是一种公平的算法。

FCFS CPU进程调度的缺点

FCFS CPU进程调度的缺点是：

• FCFS CPU调度算法具有较长的等待时间。
• FCFS CPU调度偏向于CPU而不是输入或输出操作。
• 在FCFS中存在发生车队效应的机会。
• 因为FCFS如此直接，它通常没有很高的效率。长时间的等待与此同时。如果CPU正在处理一个耗时较长的订单，所有其他订单都将闲置不做任何操作。

先来先服务CPU调度算法中的问题

例子

S. No      Process ID      Process Name      Arrival Time      Burst Time        
_ _ _     _ _ _ _ _ _     _ _ _ _ _ _ _     _ _ _ _ _ _ _     _ _ _ _ _ _ _
1           P 1            A                  0                 9
2           P 2            B                  1                 3
3           P 3            C                  1                 2
4           P 4            D                  1                 4
5           P 5            E                  2                 3
6           P 6            F                  3                 2

非抢占式方法

现在，让我们使用非抢占式方法中的先来先服务调度算法来解决这个问题。

上述示例1的甘特图如下：

转化时间= 完成时间 – 到达时间

等待时间= 转化时间 – 爆发时间

上述问题例子1的解决方案

S. No	Process ID	Arrival Time	Burst Time	Completion Time	Turn Around Time	Waiting Time
1	P 1	A	0	9	9	9 | 0
2	P 2	B	1	3	12	11 | 8
3	P 3	C	1	2	14	13 | 11
4	P 4	D	1	4	18	17 | 13
5	P 5	E	2	3	21	19 | 16
6	P 6	F	3	2	23	20 | 18

平均完成时间为：

平均CT = (9 + 12 + 14 + 18 + 21 + 23) / 6

平均CT = 97 / 6

平均CT = 16.16667

平均等待时间为：

平均WT = (0 + 8 + 11 + 13 + 16 + 18) /6

平均WT = 66 / 6

平均WT = 11

平均周转时间为：

平均TAT = (9 + 11 + 13 + 17 + 19 +20) / 6

平均TAT = 89 / 6

平均TAT = 14.83334

这是非抢占式FCFS的解法。

现在，让我们了解一下如何使用抢占式方法解决这个问题。

抢占式方法

现在，让我们用抢占式方法中名为先来先服务的调度算法来解决这个问题。

在抢占式方法中，我们寻找可用的最佳进程。

上述示例1的甘特图如下：

S. No	Process ID	Arrival Time	Burst Time	Completion Time	Turn Around Time	Waiting Time
1	P 1	A	0	9	23	23	14
2	P 2	B	1	3	8	7	4
3	P 3	C	1	2	3	2	0
4	P 4	D	1	4	15	14	10
5	P 5	E	2	3	11	9	7
6	P 6	F	3	2	5	2	0

操作系统中的信号量

为了解决浪费唤醒信号的问题，Dijkstra 提出了一种方法，即将所有的唤醒调用存储起来。Dijkstra 表示，生产者可以将唤醒调用存储在一个变量中，而不是直接将其提供给消费者，任何一个消费者都可以在需要时读取它。

信号量是变量，它存储了从生产者传输到消费者的所有唤醒调用。它是一个在内核模式下自动进行读取、修改和更新的变量。

信号量不能在用户模式下实现，因为当两个或多个进程同时尝试访问变量时，可能会产生竞态条件。它始终需要操作系统的支持来实现。

根据情况的需求，信号量可以分为两类。

1. 计数信号量
2. 二进制信号量或互斥锁

我们将详细讨论每一种信号量。