非抢占式多级反馈队列算法
第二个，非抢占式多级反馈队列如何计算呢？
辛苦帮忙给个详细的过程，对于这部分内容都不太理解和明白，太感谢了！
烦请解答，谢谢！
（1）采用最短进程优先算法（Shortest Job First, SJF）：
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 平均周转时间 |
| --- | --- | --- | --- | --- | --- |
| P1 | 0 | 30 | 30 | 30 | 30 |
| P2 | 10 | 60 | 90 | 80 | 40 |
| P3 | 20 | 40 | 130 | 110 | 36.7 |
| P4 | 30 | 50 | 180 | 150 | 37.5 |
| P5 | 50 | 30 | 210 | 180 | 36 |
平均周转时间 = (30 + 80 + 110 + 150 + 180) / 5 = 110
采用非抢占式多级反馈队列调度算法（Non-Preemptive Multilevel Feedback Queue Scheduling, MFQS）：
设置3个队列，第1级队列的时间片为10，第2级队列的时间片为20，第3级队列的时间片为30。根据到达时间进行排序，若到达时间相同，则根据进程编号排序。按照排序结果进行进程调度。
| 进程 | 到达时间 | 服务时间 | 完成时间 | 周转时间 | 平均周转时间 |
| --- | --- | --- | --- | --- | --- |
| P1 | 0 | 30 | 30 | 30 | 30 |
| P2 | 10 | 60 | 80 | 70 | 35 |
| P3 | 20 | 40 | 60 | 40 | 13.3 |
| P4 | 30 | 50 | 100 | 70 | 17.5 |
| P5 | 50 | 30 | 130 | 80 | 16 |
平均周转时间 = (30 + 70 + 40 + 70 + 80) / 5 = 58
（2）非抢占式多级反馈队列调度算法中，每个进程被分配到一个初始级别，而进程在当前级别没有用完时间片之前，都不会被抢占。如果进程在当前级别没有完成执行，则将进程移动到更高一级别的队列，继续执行。
在非抢占式多级反馈队列调度算法中，每个队列都有一个时间片，第 i 级队列的时间片为 10 * i。当一个进程进入第 i 级队列时，其剩余服务时间为 t。如果进程在第 i 级队列中用完了时间片，且其服务时间仍然大于 0，则将该进程移到第 i+1 级队列中。如果该进程已经在最高级别队列中执行，那么它会继续在该队列中执行，直到完成或被抢占为止。
具体步骤：
（1）将所有进程按照到达时间从小到大排序，作为就绪队列中的初始状态。
（2）创建多个就绪队列，每个队列代表不同级别，初始状态都为空。
（3）设置时间片大小，不同级别的队列时间片大小不同，第一级队列的时间片为10，第二级队列的时间片为20，第三级队列的时间片为30，以此类推。
（4）当前时刻t初始化为0，从第一级队列开始执行，每次执行一个时间片。
（5）如果当前队列不为空，从队首取出一个进程，执行它，并将t加上该进程执行的时间片。如果执行完后该进程已经完成，则计算出它的完成时间和周转时间，并将其从队列中删除。
（6）如果执行完后该进程还未完成，则将它加入到下一个级别的队列中等待调度。如果已经是最后一级队列了，则将其加入到当前队列末尾等待下一个时间片调度。
（7）如果当前队列为空，则跳转到下一个级别队列继续执行，直到所有队列都为空。
（8）当所有进程都执行完毕后，计算平均周转时间。
需要注意的是，在实现过程中需要考虑队列之间的转移关系和进程的插入和删除操作。同时，由于非抢占式算法不会强制剥夺进程的CPU时间，因此可能会出现某个进程长时间占用CPU的情况，导致其他进程无法得到调度，这需要在实现时进行一定的调控和限制。
非抢占式多级反馈队列是一种进程调度算法，它的基本思想是：
1、设置多个就绪队列，每个队列有不同的优先级和时间片大小，优先级越高的队列，时间片越小。
2、新到达的进程先放 入第一级队列，按照先来先服务的原则排队等待调度。
3、当轮到某个进程执行时，如果它能在一个时间片内完成，就结束运行；如果它在一个时间片结束时还没有完成，就被转移到下一级队列的末尾，等待下一次调度。
4、只有当高优先级的队列为空时，才会调度低优先级的队列中的进程执行。
为了计算非抢占式多级反馈队列的调度结果，您需要知道以下信息：
5、进程的到达时间、服务时间和名称
6、队列的数量、优先级和时间片大小
7、当前的系统时间和就绪队列的状态
您可以参考以下步骤来计算非抢占式多级反馈队列的调度结果：
【1】将所有进程按照到达时间从小到大排序，并初始化系统时间为0。
【2】从排序后的进程列表中找出所有在系统时间之前或等于系统时间到达的进程，并将它们放入第一级队列的末尾。
【3 】如果所有就绪队列都为空，则将系统时间更新为下一个到达的进程的到达时间，并重复步骤2。
【4】如果第一级队列不为空，则从队头取出一个进程，并记录它的开始运行时间和结束运行时间（开始运行时间等于系统时间，结束运行时间等于系统时间加上该进程剩余的服务时间和第一级队列的时间片中较小的一个）。
【5】如果该进程在一个时间片内完成，则输出该进程的名称、开始运行时间和结束运行时间，并将系统时间更新为结束运行时间。
【6】如果该进程在一个时间片内没有完成，则输出该进程的名称、开始运行时间和结束运行时间，并将该进程剩余的服务时间减去一个时间片，然后将该进程放入第二级队列的末尾，并将系统时间更新为结束运行时间。
【7】重复步骤2至步骤6，直到所有进程都完成运行。
您可以参考以下链接来了解更多关于非抢占式多级反馈队列的原理和示例：
https://blog.csdn.net/zzdxls/article/details/117885624
https://blog.csdn.net/yrx420909/article/details/104363553
https://wenku.baidu.com/view/96ac7cf3b24e852458fb770bf78a6529647d35f4.html
https://zhuanlan.zhihu.com/p/367636084
以下答案由GPT-3.5大模型与博主波罗歌共同编写：
非抢占式多级反馈队列 (Nonpreemptive Multilevel Feedback Queue, NMLFQ) 是一种调度算法，解决了抢占式多级反馈队列的问题。在 NMLFQ 中，进程无法被抢占，它只有在当前时间片结束后才能被替换。这个算法使用多个队列，每个队列有一个不同的时间片大小。当进程进入系统时，进程被放入第一个队列。如果进程在当前队列中完全执行完毕，那么它会被移动到下一个队列中，这个队列有更长的时间片。如果一个进程在队列中等待很长时间，那么它会被移动回上一个队列，这个队列有更短的时间片，使这个进程有机会在更短的时间内完成执行。下面是如何计算 NMLFQ 的过程：
1.创建多个队列，确定每个队列的时间片大小和优先级。
2.按照优先级顺序，将进程放入第一个队列。
3.如果进程运行时间小于队列的时间片大小，那么它将在队列中等待下一个时间片，直到完成。
4.如果进程在队列中完成执行，而没有使用完整个时间片，那么它将被移动到下一个队列，这个队列有更长的时间片。
5.如果进程等待了很长时间，还没有完成执行，那么它将被移动回上一个队列，这个队列有更短的时间片。
6.重复步骤3至5，直到进程完成执行。
下面是一个示例代码，演示了如何实现一个三级反馈队列调度算法：
class Process:
def __init__(self, pid, burst_time, arrival_time):
self.pid = pid
self.burst_time = burst_time
self.arrival_time = arrival_time
self.remaining_time = burst_time
q1 = []
q2 = []
q3 = []
quantum1 = 2 # 时间片大小
quantum2 = 4
quantum3 = 8
procs = [
Process(1, 24, 0),
Process(2, 3, 0),
Process(3, 3, 1),
Process(4, 7, 2),
Process(5, 4, 3)
]
current_time = 0
while True:
# 将到达时间小于等于当前时间的进程加入队列 1
while len(procs) > 0 and procs[0].arrival_time <= current_time:
q1.append(procs.pop(0))
if len(q1) == 0 and len(q2) == 0 and len(q3) == 0 and len(procs) == 0:
break # 所有进程都已经完成执行
if len(q1) > 0:
current_process = q1.pop(0)
current_process.remaining_time -= quantum1
current_time += quantum1
if current_process.remaining_time <= 0:
print(f'Process {current_process.pid} completed at time {current_time}')
else:
q2.append(current_process)
elif len(q2) > 0:
current_process = q2.pop(0)
current_process.remaining_time -= quantum2
current_time += quantum2
if current_process.remaining_time <= 0:
print(f'Process {current_process.pid} completed at time {current_time}')
else:
q3.append(current_process)
elif len(q3) > 0:
current_process = q3.pop(0)
current_process.remaining_time -= quantum3
current_time += quantum3
if current_process.remaining_time <= 0:
print(f'Process {current_process.pid} completed at time {current_time}')
else:
q3.append(current_process)
else:
current_time += 1 # 没有进程在等待，系统空转
print(f'Simulation ended at time {current_time}')
如果我的回答解决了您的问题，请采纳！