操作系统之FCFS - 先来先服务算法
一、简述
先来先服务调度算法是最简单的调度方法。
基本原则：按照进程进入就绪队列的先后次序进行选择。对于进程调度来说，一旦一个进程得到处理机，它就一直运行下去，直到该进程完成任务或者因等待某事件而不能继续运行，才会让出处理机。先来先服务调度算法属于非剥夺方式
先来先服务的原则：
- 先到达的进程优先执行
- 一旦进程抢占到cpu的执行权，则需要待进程的任务全部执行完才会是否cpu的执行权给其它进程
二、例题
有4个进程p1、p2、p3、p4依次在8:00、8:50、9:00、9:50进入，它们的运行时间如下，求各个作业的开始时间、完成时间、周转时间、带权周转时间和总的平均周转时间、平均带权周转时间。
| 进程 | 提交时刻 | 运行时间 |
|---|---|---|
| p1 | 8:00 | 120 |
| p2 | 8:50 | 50 |
| p3 | 9:00 | 10 |
| p4 | 9:50 | 20 |
答：
| 进程 | 提交时刻 | 运行时间 | 开始时刻 | 完成时刻 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| p1 | 8:00 | 120 | (1) | (2) | (9) | (13) |
| p2 | 8:50 | 50 | (3) | (4) | (10) | (14) |
| p3 | 9:00 | 10 | (5) | (6) | (11) | (15) |
| p4 | 9:50 | 20 | (7) | (8) | (12) | (16) |
先来先服务的原则：
- 先到达的进程优先执行
- 一旦进程抢占到cpu的执行权，则需要待进程的任务全部执行完才会是否cpu的执行权给其它进程
答：
- 第（1）、（2）空填写：
- 8:00时刻只有p1进程到达了，所以p1先执行，p1的开始时刻是8:00，所以（1）填写8:00
- 由上述原则，p1会一直执行完才会释放，即p1执行120，到10:00，p1执行完成，所以p1的完成时刻是10:00，所以（2）填写10:00
- 第（3）、（8）空填写：
- 由上p1的完成时刻是10:00，在10:00的时候，p2、p3、p4都已经进入了，所以按照进入的次序依次执行，按进入由早到晚依次是：p2(8:50)、p3(9:00)、p4(9:50)
- 所以p2的开始时刻是10:00，第（3）空填写10:00，p2执行50，所以p2的完成时刻是10:50，第（4）空填下10:50
- 所以p3的开始时刻是10:50，第（5）空填写10:50，p3执行10，所以p3的完成时刻是11:00，第（6）空填下11:00
- 所以p4的开始时刻是11:00，第（7）空填写11:00，p4执行20，所以p4的完成时刻是11:20，第（8）空填下11:20
- 第（9）-（16）空填写：
- 周转时间 = 完成时间 - 到达时间（进入时间）
- 带权周转时间 = 周转时间 / 运行时间
- （9）- （12）空填写：120、120、120、90
- （13）- （16）空填写：1、2.4、12、4.5
- 平均周转时间 = （120+120+120+90）div 4 = 112.5
- 平均带权周转时间 = （1+2.4+12+4.5）div 4 = 4.975
对应表格为：
| 进程 | 提交时刻 | 运行时间 | 开始时刻 | 完成时刻 | 周转时间 | 带权周转时间 |
|---|---|---|---|---|---|---|
| p1 | 8:00 | 120 | 8:00 | 10:00 | 120 | 1 |
| p2 | 8:50 | 50 | 10:00 | 10:50 | 120 | 2.4 |
| p3 | 9:00 | 10 | 10:50 | 11:00 | 120 | 12 |
| p4 | 9:50 | 20 | 11:00 | 11:20 | 90 | 4.5 |
平均周转时间 = 112.5文章来源：https://www.toymoban.com/news/detail-717179.html
平均带权周转时间 = 4.975文章来源地址https://www.toymoban.com/news/detail-717179.html
三、公式
- 完成时刻 = 开始时刻 + 运行时间
- 周转时间 = 完成时间 - 到达时间（进入时间 / 提交时刻）
- 带权周转时间 = 周转时间 / 运行时间
到了这里，关于操作系统之FCFS - 先来先服务算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
