实验目的

        通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。

实验内容

先来先服务调度算法（FCFS）

        先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用 FCFS 算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。

短作业优先调度算法（SJF）

        短作业优先（SJF）调度算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。短作业优先调度算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存运行，为它们分配资源、创建进程，然后放入就绪队列。在进程调度在采用SJF算法时，从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使之投入运行，或发生某事件而被阻塞放弃处理机时再重新调度。

最高响应比优先调度算法（HRRN）

        最高响应比优先（HRRN）调度算法是一种对FCFS调度算法和SJF调度算法综合平衡的算法，它不仅考虑作业的执行时间，还考虑作业的等待时间，在进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业，将其调入内存，为它们分配资源、创建进程，然后放入就绪队列。响应比Rp =（等待时间+要求服务时间）/ 要求服务时间 = 1 +（等待时间 / 要求服务时间）

        由上式可以看出：①如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而类似于SJF算法，有利于短作业。②当要求服务的时间相同时，作业的优先权又决定于其等待时间，因而该算法又类似于FCFS算法。③对于长作业的优先级，可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机。因此该算法实现了较好的折中。在利用该算法时，每次要进行调度之前，都需要先做响应比的计算，显然会增加系统开销。

时间片轮转调度算法（RR）

        在时间片轮转(RR)调度算法中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔，即产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行。当该进程的时间片耗尽或运行完毕时，系统再次将CPU分配给新的队首进程(或新到达的紧迫进程)。由此，可保证就绪队列中的所有进程在一个确定的时间段内，都能够获得一次CPU执行。

        在时间片轮转调度算法中，应在何时进行进程的切换，可分为两种情况：①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

实验设计

先来先服务调度算法（FCFS）

class Process:
   def __init__(self, name, arrival_time, service_time):
       self.name = name
       self.arrival_time = arrival_time
       self.service_time = service_time
       self.start_time = None
       self.end_time = None
       self.turnaround_time = None
       self.weighted_turnaround_time = None


def fcfs(processes):
   num_processes = len(processes)
   current_time = 0
   turnaround_time = 0
   weighted_turnaround_time = 0

   for process in processes:
       # 如果进程尚未到达，则等待
       if process.arrival_time > current_time:
           current_time = process.arrival_time

       # 计算进程的开始时间、完成时间、周转时间和平均周转时间
       process.start_time = current_time
       current_time += process.service_time
       process.end_time = current_time
       process.turnaround_time = process.end_time - process.arrival_time
       process.weighted_turnaround_time = process.turnaround_time / process.service_time

   # 输出每个进程的开始时间、完成时间、周转时间和带权周转时间
   print("进程\t\t提交时间\t\t运行时间\t\t开始时间\t\t完成时间\t\t周转时间\t\t带权周转时间")
   for process in processes:
       turnaround_time += process.turnaround_time  # 更新周转时间总和
       weighted_turnaround_time += process.weighted_turnaround_time  # 更新带权周转时间总和
       print("{}\t\t{:4}\t\t{:4}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}".format(process.name, process.arrival_time,
                                                                                 process.service_time,
                                                                                 process.start_time, process.end_time,
                                                                                 process.turnaround_time,
                                                                                 process.weighted_turnaround_time))
   # 计算平均周转时间和平均带权周转时间
   average_turnaround_time = turnaround_time / num_processes
   average_weighted_turnaround_time = weighted_turnaround_time / num_processes
   # 输出平均周转时间和带权周转时间
   print("平均周转时间:{:.3f} ".format(average_turnaround_time))
   print("平均带权周转时间: {:.3f}".format(average_weighted_turnaround_time))


if __name__ == '__main__':
   num_processes = int(input("请输入进程个数: "))
   processes = []

   for i in range(num_processes):
       name = input("请输入第{}个进程名称: ".format(i + 1))
       arrival_time = float(input("请输入第{}个提交时间: ".format(i + 1)))
       service_time = float(input("请输入第{}个服务时间: ".format(i + 1)))
       process = Process(name, arrival_time, service_time)
       processes.append(process)

   # 按照提交时间排序进程
   processes.sort(key=lambda x: x.arrival_time)
   fcfs(processes)

短作业优先调度算法（SJF）

class Process:
   def __init__(self, name, arrival_time, service_time):
       self.name = name
       self.arrival_time = arrival_time
       self.service_time = service_time
       self.start_time = None
       self.end_time = None
       self.turnaround_time = None
       self.weighted_turnaround_time = None


def sjf(processes, current_time):
   ready_queue = []
   waiting_queue = []

   # 按提交时间将进程分为就绪队列和等待就绪队列
   for process in processes:
       if process.arrival_time <= current_time:
           ready_queue.append(process)
       else:
           waiting_queue.append(process)

   # 如果就绪队列为空，执行等待就绪队列的第一个进程
   if not ready_queue:
       current_time = waiting_queue[0].arrival_time
       ready_queue.append(waiting_queue.pop(0))

   # 按服务时间对就绪队列进行排序
   ready_queue.sort(key=lambda x: x.service_time)

   # 计算就绪队列中每个进程的开始时间、完成时间、周转时间和平均周转时间
   for process in ready_queue:
       process.start_time = current_time
       current_time += process.service_time
       process.end_time = current_time
       process.turnaround_time = process.end_time - process.arrival_time
       process.weighted_turnaround_time = process.turnaround_time / process.service_time

   # 将等待就绪队列作为新的进程列表递归执行，直到等待就绪队列为空
   if waiting_queue:
       sjf(waiting_queue, current_time)


if __name__ == '__main__':
   num_processes = int(input("请输入进程个数: "))
   turnaround_time = 0
   weighted_turnaround_time = 0
   processes = []

   for i in range(num_processes):
       name = input("请输入第{}个进程名称: ".format(i + 1))
       arrival_time = float(input("请输入第{}个提交时间: ".format(i + 1)))
       service_time = float(input("请输入第{}个服务时间: ".format(i + 1)))
       process = Process(name, arrival_time, service_time)
       processes.append(process)

   # 按照提交时间和服务时间排序进程
   processes.sort(key=lambda p: (p.arrival_time, p.service_time))
   sjf(processes, 0)

   # 输出每个进程的开始时间、完成时间、周转时间和带权周转时间
   print("进程\t\t提交时间\t\t运行时间\t\t开始时间\t\t完成时间\t\t周转时间\t\t带权周转时间")
   for process in processes:
       turnaround_time += process.turnaround_time  # 更新周转时间总和
       weighted_turnaround_time += process.weighted_turnaround_time  # 更新带权周转时间总和
       print("{}\t\t{:4}\t\t{:4}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}".format(process.name, process.arrival_time,
                                                                                 process.service_time,
                                                                                 process.start_time, process.end_time,
                                                                                 process.turnaround_time,
                                                                                 process.weighted_turnaround_time))
   # 计算平均周转时间和平均带权周转时间
   average_turnaround_time = turnaround_time / num_processes
   average_weighted_turnaround_time = weighted_turnaround_time / num_processes
   # 输出平均周转时间和带权周转时间
   print("平均周转时间:{:.3f} ".format(average_turnaround_time))
   print("平均带权周转时间: {:.3f}".format(average_weighted_turnaround_time))

最高响应比优先调度算法（HRRN）

class Process:
   def __init__(self, name, arrival_time, service_time):
       self.name = name
       self.arrival_time = arrival_time
       self.service_time = service_time
       self.start_time = None
       self.end_time = None
       self.turnaround_time = None
       self.weighted_turnaround_time = None
       self.response_ratio = None


def hrrn(processes, current_time):
   ready_queue = []
   waiting_queue = []

   # 按提交时间将进程分为就绪队列和等待就绪队列
   for process in processes:
       if process.arrival_time <= current_time:
           ready_queue.append(process)
       else:
           waiting_queue.append(process)

   # 如果就绪队列为空，执行等待就绪队列的第一个进程
   if not ready_queue:
       current_time = waiting_queue[0].arrival_time
       waiting_queue[0].response_ratio = 1
       ready_queue.append(waiting_queue.pop(0))

   # 计算就绪队列中每个进程的响应比
   for process in ready_queue:
       wait_time = current_time - process.arrival_time
       response_ratio = (wait_time + process.service_time) / process.service_time
       process.response_ratio = response_ratio

   # 按响应比进行排序
   ready_queue.sort(key=lambda x: x.response_ratio, reverse=True)

   # 计算就绪队列中每个进程的开始时间、完成时间、周转时间和平均周转时间
   for process in ready_queue:
       process.start_time = current_time
       current_time += process.service_time
       process.end_time = current_time
       process.turnaround_time = process.end_time - process.arrival_time
       process.weighted_turnaround_time = process.turnaround_time / process.service_time

   # 将等待就绪队列作为新的进程列表递归执行，直到等待就绪队列为空
   if waiting_queue:
       hrrn(waiting_queue, current_time)

       
if __name__ == '__main__':
   num_processes = int(input("请输入进程个数: "))
   turnaround_time = 0
   weighted_turnaround_time = 0
   processes = []

   for i in range(num_processes):
       name = input("请输入第{}个进程名称: ".format(i + 1))
       arrival_time = float(input("请输入第{}个提交时间: ".format(i + 1)))
       service_time = float(input("请输入第{}个服务时间: ".format(i + 1)))
       process = Process(name, arrival_time, service_time)
       processes.append(process)

   # 按照提交时间排序进程
   processes.sort(key=lambda x: x.arrival_time)
   hrrn(processes, 0)

   # 输出每个进程的开始时间、完成时间、周转时间和带权周转时间
   print("进程\t\t提交时间\t\t运行时间\t\t开始时间\t\t完成时间\t\t周转时间\t\t带权周转时间")
   for process in processes:
       turnaround_time += process.turnaround_time  # 更新周转时间总和
       weighted_turnaround_time += process.weighted_turnaround_time  # 更新带权周转时间总和
       print("{}\t\t{:4}\t\t{:4}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}".format(process.name, process.arrival_time,
                                                                                 process.service_time,
                                                                                 process.start_time, process.end_time,
                                                                                 process.turnaround_time,
                                                                                 process.weighted_turnaround_time))
   # 计算平均周转时间和平均带权周转时间
   average_turnaround_time = turnaround_time / num_processes
   average_weighted_turnaround_time = weighted_turnaround_time / num_processes
   # 输出平均周转时间和带权周转时间
   print("平均周转时间:{:.3f} ".format(average_turnaround_time))
   print("平均带权周转时间: {:.3f}".format(average_weighted_turnaround_time))

时间片轮转调度算法（RR）

import copy
from queue import Queue


class Process:
   def __init__(self, name, arrival_time, service_time):
       self.name = name
       self.arrival_time = arrival_time
       self.service_time = service_time
       self.start_time = None
       self.end_time = None
       self.turnaround_time = None
       self.weighted_turnaround_time = None


def rr(processes, time_quantum):
   num_processes = len(processes)
   current_time = 0
   turnaround_time = 0
   weighted_turnaround_time = 0
   temp = copy.deepcopy(processes)  # 深拷贝，建立按到达顺序排序的临时对象
   q = Queue()  # 建立队列
   sign = True  # 循环标记
   flag = num_processes    # 记录未完成进程数量
   i = 0    # 进程索引

   while sign:
       # 未完成进程都在队列
       # 依次出队运行，判断是否运行完成，未完成重新入队
       if Queue.qsize(q) == flag:
           now_p = q.get()
           index = temp.index(now_p)  # 获得该进程的索引

           # 如果第一次执行(原始运行时间等于剩余运行时间)
           if processes[index].service_time == now_p.service_time:
               processes[index].start_time = current_time

           if now_p.service_time > time_quantum:
               now_p.service_time -= time_quantum
               current_time += time_quantum
           else:
               servicetime = processes[index].service_time
               now_p.end_time = now_p.service_time + current_time
               now_p.turnaround_time = now_p.end_time - now_p.arrival_time
               now_p.weighted_turnaround_time = now_p.turnaround_time / servicetime
               current_time = now_p.end_time
               now_p.service_time = 0
               flag -= 1

           if now_p.service_time > 0:
               q.put(now_p)

       else:
           # 队列非空
           if not q.empty():
               now_p = q.get()  # 调度当前队头进程
               ind = temp.index(now_p)  # 获得该进程的索引

               # 如果第一次执行(原始运行时间等于剩余运行时间)
               if processes[ind].service_time == now_p.service_time:
                   processes[ind].start_time = current_time

               if now_p.service_time > time_quantum:
                   now_p.service_time -= time_quantum
                   current_time += time_quantum
               else:
                   servicetime = processes[ind].service_time
                   now_p.end_time = now_p.service_time + current_time
                   now_p.turnaround_time = now_p.end_time - now_p.arrival_time
                   now_p.weighted_turnaround_time = now_p.turnaround_time / servicetime
                   current_time = now_p.end_time
                   now_p.service_time = 0
                   flag -= 1

               wait = 0  # 等待进程数量
               for n in range(i, num_processes, 1):
                   if temp[n].arrival_time == current_time:
                       wait += 1

               # 如果有等待进程，等待进程入队
               if wait > 0:
                   for m in range(wait):
                       wait_p = temp[i]
                       q.put(wait_p)
                       i += 1  # 进程索引加一

               if now_p.service_time > 0:
                   q.put(now_p)

           else:
               now_p = temp[i]
               current_time = now_p.arrival_time
               q.put(now_p)
               i += 1  # 进程索引加一

       # 结束循环判断
       for j in range(num_processes):
           if temp[j].service_time == 0:
               sign = False  # 全部进程执行完成
           else:
               sign = True  # 还有未服务结束的进程
               break

   for l in range(num_processes):
       processes[l].end_time = temp[l].end_time
       processes[l].turnaround_time = temp[l].turnaround_time
       processes[l].weighted_turnaround_time = temp[l].weighted_turnaround_time

   # 输出每个进程的完成时间、周转时间和带权周转时间
   print("进程\t\t提交时间\t\t运行时间\t\t开始时间\t\t完成时间\t\t周转时间\t\t带权周转时间")
   for process in processes:
       turnaround_time += process.turnaround_time  # 更新周转时间总和
       weighted_turnaround_time += process.weighted_turnaround_time  # 更新带权周转时间总和
       print("{}\t\t{:4}\t\t{:4}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}\t\t{:.2f}".format(process.name, process.arrival_time,
                                                                                 process.service_time,
                                                                                 process.start_time, process.end_time,
                                                                                 process.turnaround_time,
                                                                                 process.weighted_turnaround_time))

   # 计算平均周转时间和平均带权周转时间
   average_turnaround_time = turnaround_time / num_processes
   average_weighted_turnaround_time = weighted_turnaround_time / num_processes
   # 输出平均周转时间和带权周转时间
   print("平均周转时间:{:.3f} ".format(average_turnaround_time))
   print("平均带权周转时间: {:.3f}".format(average_weighted_turnaround_time))


if __name__ == '__main__':
   num_processes = int(input("请输入进程个数: "))
   time_quantum = float(input("请输入时间片大小: "))
   processes = []

   for i in range(num_processes):
       name = input("请输入第{}个进程名称: ".format(i + 1))
       arrival_time = float(input("请输入第{}个提交时间: ".format(i + 1)))
       service_time = float(input("请输入第{}个服务时间: ".format(i + 1)))
       process = Process(name, arrival_time, service_time)
       processes.append(process)

   processes.sort(key=lambda x: x.arrival_time)
   rr(processes, time_quantum)

实验结果

图中时间片大小为1