1 实验目的

分析处理器实施进程调度的前提条件，理解并掌握各类处理器调度算法设计原理和实现机制。

2 实验内容

分析和探索处理器实施进程调度的前提条件，理解并掌握处理器调度算法的设计原理和实现机制，随机发生和模拟进程创建及相关事件，编程实现基于特定处理器调度算法(三种以上，譬如先来先服务调度算法、短进程优先算法、高优先权优先调度算法、高响应比优先调度算法、时间片轮转调度算法、多级反馈队列调度算法、等等)的系统调度处理过程并加以测试验证。

3 实验要求

本实验课题主要功能设计要求包括:
1)选取和设计实现三种以上的处理器调度算法；
2)针对特定的处理器调度算法，分析处理器实施进程调度的前提条件和要求（譬如进程创建时刻、运 行时间长短、各集中计算运行/输入输出操作时间段长短、优先级），并随机发生和模拟处理对应的进 程创建及相关时间；
3)编程实现处理器调度机制，针对特定的处理器调度算法和随机事件序列，给出相应的调度处理过 程，主要涵盖进程相关时间、处理器调度操作或处理措施以及各状态进程列表；
4)测试验证处理器调度机制的有效性及有关处理器调度算法设计方案的正确性。

4 实验设计

4.1 随机生成模拟进程

该实验调度算法都采用python进行模拟，使用函数processList(num)生成模拟进程列表。主要使用python random模块随机生成进程到达时间，进程相对结束时间这两个数值。生成各进程参数如图注释所示。
OS: 处理器调度算法模拟实现与比较 - 图1
使用processShow(process)函数显示当前生成的进程列表，显示结果如图所示。
OS: 处理器调度算法模拟实现与比较 - 图2
OS: 处理器调度算法模拟实现与比较 - 图3

4.2 先来先服务调度算法

先来先服务调度算法是最基本的调度算法，核心是采用队列来实现。它根据进程到达时间决定先运行哪一个进程。这里我们使用list来实现。如下图所示，fcfs对模拟进程列表按时间到达先后进行排序。
OS: 处理器调度算法模拟实现与比较 - 图4
算法主体使用while循环来模拟，cputime模拟时间，代码大体梗概如图所示，需要注意的是，status函数用来输出当前进程列表状态，conclusion函数用于模拟结束后输出统计结果。
OS: 处理器调度算法模拟实现与比较 - 图5
Status函数:
OS: 处理器调度算法模拟实现与比较 - 图6
Conclusion函数:
OS: 处理器调度算法模拟实现与比较 - 图7
程序的main函数如图所示，通过传参将模拟方法与模拟进程数目传入。
OS: 处理器调度算法模拟实现与比较 - 图8
Fcfs调度算法模拟结果如图所示:
OS: 处理器调度算法模拟实现与比较 - 图9
OS: 处理器调度算法模拟实现与比较 - 图10

4.3 短进程优先调度算法

短进程优先调度算法是在先来先服务调度算法的基础上，对就绪进程所需要处理时间进行排序，优先服务短进程。所以模拟该调度算法也是在fcfs算法的基础上进行的，sjf算法新增加了对就绪队列排序的功能，使用sjfSort(process,current)函数实现，函数如图所示,使用选择排序对就绪进程队列按处理时间长短进行排序。
OS: 处理器调度算法模拟实现与比较 - 图11
模拟结果如图所示:
OS: 处理器调度算法模拟实现与比较 - 图12
OS: 处理器调度算法模拟实现与比较 - 图13

4.4 时间片轮转调度算法

时间片轮转调度算法的系统其进程就绪队列按照先来先服务调度原则，但是占用处理机只要一个时间片，在完成一个时间片后如果还没有完成就必须释放给下一个就绪的进程，而被剥夺的进程排到队尾。该算法最核心的便是时间片，在模拟程序中，我们将时间片长度设置为2s,while循环主体如图所示，与上两种算法有些不同，fcfs和sjf实现机制是普通队列，而rr调度算法实现机制是循环队列。
OS: 处理器调度算法模拟实现与比较 - 图14
RR调度算法运行结果如图所示:
OS: 处理器调度算法模拟实现与比较 - 图15
OS: 处理器调度算法模拟实现与比较 - 图16

4.5 高响应比优先调度算法

高响应比优先调度算法的基本思想是把CPU分配给就绪队列中响应比最高的进程。既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。所以该代码大体也与sjf算法相似，不同的是排序的依据，hrrn算法通过计算响应比来对就绪进程排序。排序算法如图所示:
OS: 处理器调度算法模拟实现与比较 - 图17
HRRN算法运行结果如图所示:
OS: 处理器调度算法模拟实现与比较 - 图18
OS: 处理器调度算法模拟实现与比较 - 图19

4.6 调度算法简单比较

为了更好的体现各调度算法的特点，将模拟进程数设置为100.
FCFS算法:
OS: 处理器调度算法模拟实现与比较 - 图20
SJF算法:
OS: 处理器调度算法模拟实现与比较 - 图21
HRRN算法:
OS: 处理器调度算法模拟实现与比较 - 图22
RR算法:
OS: 处理器调度算法模拟实现与比较 - 图23
由于模拟生成的进程每一次程序运行都不一样，所以这里只简单分析各个算法点。
对于FCFS算法，100个模拟进程的带权周转时间，如果计算它们的方差，一定是特别大的。稳定性较差。
对于SJF算法和HRRN算法，各进程的带权周转时间在这里没有体现较大的差异，呈现出随到达时间增长进程的带权周转时间也增长的特点。猜测是random函数设置区间范围太小的原因。
最后对于RR算法，大体上各进程带权周转时间相近似，所以有比较好的稳定性。但是平均带权周转时间会有所增加。

5 实验总结

经过此次试验，对于操作系统的一些调度算法有了较为深刻的理解。对各调度算法的优点和缺点都有所了解，从而意识到了操作系统调度算法对于操作系统的重要性。

  1. import random,sys
  3. # 生成进程列表
  4. def processList(num):
  5.     process=[]
  6.     for i in range(num):
  7.         dic={}
  8.         dic['id']=i  #模拟进程号
  9.         dic['start']=random.randint(0,20)  #进程到达时间
  10.         dic['end']=dic['start']+random.randint(1,20)  #进程相对结束时间
  11.         dic['runtime']=dic['end']-dic['start']  #进程所需运行时间
  12.         dic['status']=""  #进程当前状态
  13.         dic['left']=dic['runtime']  #进程运行剩余时间
  14.         dic['wait_time']=0 #进程等待时间
  15.         dic['tr_time']=0 #进程周转时间
  16.         process.append(dic)
  17.     return process
  19. # 展示进程列表
  20. def processShow(process):
  21.     for p in process:
  22.         print(p)
  23.     print()
  25. # 展示当前状态
  26. def status(process):
  27.     print("-----status table-------")
  28.     for p in process:
  29.         print("process id:%d status:%s"%(p['id'],p['status']))
  30.     print()
  32. # 计算进程状态时间
  33. def conclusion(process):
  34.     print("-------------conclusion table--------------")
  35.     print("进程ID  等待时间   周转时间   带权周转时间|")
  36.     sum1=0
  37.     sum2=0
  38.     sum3=0.0
  39.     for p in process:
  40.         wait_time=p['wait_time']
  41.         sum1+=wait_time
  42.         tr_time=p['tr_time']
  43.         sum2+=tr_time
  44.         wtr_time=float(p['tr_time'])/(p['end']-p['start'])
  45.         sum3+=wtr_time
  46.         print("%3d      %3ds        %3ds       %5.2f     |"%(p['id'],p['wait_time'],p['tr_time'],wtr_time))
  47.     print("-------------------------------------------")
  48.     print("平均等待时间: %ds\n平均周转时间: %ds\n平均带权周转时间:%.2fs"%(sum1/len(process),sum2/len(process),sum3/len(process)))
  49.     print("-------------------------------------------")
  51. # 非抢占式就绪排序
  52. def sjfSort(process,current):
  53.     for i in range(current,len(process)):
  54.         min=i
  55.         for j in range(current+1,len(process)):
  56.             if process[i]['status'] =='就绪' and process[j]['status']=='就绪':
  57.                 if process[min]['runtime']>process[j]['runtime']:
  58.                     min=j
  59.         process[min],process[i]=process[i],process[min]
  60.     return process
  62. # 高响应比排序
  63. def hrrnSort(process,current,cputime):
  64.     for i in range(current,len(process)):
  65.         min=i
  66.         for j in range(current+1,len(process)):
  67.             if process[i]['status'] =='就绪' and process[j]['status']=='就绪':
  68.                 scale_j=float(cputime-process[j]['start']+process[j]['runtime'])/process[j]['runtime']
  69.                 scale_min=float(cputime-process[min]['start']+process[min]['runtime'])/process[min]['runtime']
  70.                 if scale_j>scale_min:
  71.                     min=j
  72.         process[min],process[i]=process[i],process[min]
  73.     return process
  75. # 先来先服务算法
  76. def FCFS(process):
  77.     print("-------------------------------FCFS-----------------------------")
  78.     process=sorted(process,key=lambda x:x['start'])
  79.     processShow(process)
  80.     cputime=0
  81.     current=0
  82.     while True:
  83.         flag=False
  84.         if process[0]['start']==cputime:
  85.             process[current]['runtime']+=cputime
  86.             process[current]['status']="运行"
  87.             process[current]['wait_time']=cputime-process[current]['start']
  88.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  89.             flag=True
  90.         #当前进程结束
  91.         if current<=len(process) and process[current]['runtime']==cputime and process[current]['status']=='运行':
  92.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"结束!")
  93.             process[current]['status']='Die'
  94.             process[current]['tr_time']=cputime-process[current]['start']
  95.             flag=True
  96.         #所有进程结束
  97.         if process[current]['status']=='Die' and current==len(process)-1:
  98.             print("所有进程执行完毕，总计耗时"+str(cputime)+"s")
  99.             conclusion(process)
  100.             break;
  101.         #新进程开始
  102.         if process[current]['status']=='Die' and process[current+1]['start']<=cputime:
  103.             current+=1
  104.             process[current]['runtime']+=cputime
  105.             process[current]['status']="运行"
  106.             process[current]['wait_time']=cputime-process[current]['start']
  107.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  108.             flag=True
  109.         #检查是否有新进程到达
  110.         for i in range(current+1,len(process)):
  111.             if process[i]['start'] == cputime:
  112.                 process[i]['status'] = "就绪"
  113.         if flag:
  114.             status(process)
  115.         cputime+=1
  117. # 非抢占式短作业优先算法
  118. def SJF(process):
  119.     print("-------------------SJF------------------------------------")
  120.     process=sorted(process,key=lambda x:x['start'])
  121.     processShow(process)
  122.     cputime=0
  123.     current=0
  124.     while True:
  125.         flag=False
  126.         if process[0]['start']==cputime:
  127.             process[current]['runtime']+=cputime
  128.             process[current]['status']="运行"
  129.             process[current]['wait_time']=cputime-process[current]['start']
  130.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  131.             flag=True
  132.         if current<=len(process) and process[current]['runtime']==cputime:
  133.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"结束!")
  134.             process[current]['status']='Die'
  135.             process[current]['tr_time']=cputime-process[current]['start']
  136.             flag=True
  138.         if process[current]['status']=='Die' and current==len(process)-1:
  139.             print("所有进程执行完毕，总计耗时"+str(cputime)+"s")
  140.             conclusion(process)
  141.             break;
  142.         if process[current]['status']=='Die' and process[current+1]['start']<=cputime:
  143.             current+=1
  144.             process[current]['runtime']+=cputime
  145.             process[current]['status']="运行"
  146.             process[current]['wait_time']=cputime-process[current]['start']
  147.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  148.             flag=True
  150.         for i in range(current+1,len(process)):
  151.             if process[i]['start'] == cputime:
  152.                 process[i]['status'] = "就绪"
  153.         process=sjfSort(process,current+1)
  154.         if flag:
  155.             status(process)
  156.         cputime+=1
  158. # 时间片轮询调度算法
  159. def RR(process):
  160.     print("-------------------RR------------------------------------")
  161.     process=sorted(process,key=lambda x:x['start'])
  162.     processShow(process)
  163.     cputime=0
  164.     time_slice=2
  165.     current=0
  166.     start=True
  167.     while True:
  168.         flag=False
  169.         if start:
  170.             if time_slice==0:
  171.                 time_slice==2
  172.             if process[0]['start']==cputime:
  173.                 process[0]['status']='运行'
  174.                 print("第"+str(cputime)+ "s"+"进程"+str(process[0]['id'])+"开始!")
  175.                 flag=True
  176.                 start=False
  177.         #当前进程运行结束
  178.         if process[current]['status']=='运行' and process[current]['left']==0:
  179.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"结束!")
  180.             process[current]['status']='Die'
  181.             process[current]['tr_time']=cputime-process[current]['start']
  184.             process[current]['wait_time']=process[current]['tr_time']-process[current]['runtime']
  185.             flag=True
  186.         sig=True    
  187.         #启用新进程或所有进程结束
  188.         if process[current]['status']=='Die':
  189.             for i in range(current+1,current+len(process)):
  190.                 if process[i%len(process)]['status']=='就绪':
  191.                     process[i%len(process)]['status']='运行'
  192.                     current=i%len(process)
  193.                     print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  194.                     sig=False
  195.                     flag=True
  196.                     break
  197.             if sig:
  198.                 sig=True
  199.                 for i in range(len(process)):
  200.                     if process[i]['status']!='Die':
  201.                         sig=False
  202.                         break
  203.                 if sig:
  204.                     status(process)
  205.                     print("所有进程执行完毕，总计耗时"+str(cputime)+"s")
  206.                     conclusion(process)
  207.                     break
  208.             if time_slice==0:
  209.                 time_slice=2    
  210.         #时间片结束，切换进程执行    
  211.         if (not start) and time_slice==0:
  212.             process[current]['status']='就绪'
  213.             time_slice=2
  214.             for i in range((current+1)%len(process),(current+len(process))+1):
  215.                 if process[i%len(process)]['status']=='就绪':
  216.                     process[i%len(process)]['status']='运行'
  217.                     current=i%len(process)
  218.                     print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  219.                     flag=True
  220.                     break
  221.         for i in range(current+1,len(process)):
  222.             if process[i]['start'] == cputime:
  223.                 process[i]['status'] = "就绪"
  224.         if flag:
  225.             status(process)
  226.         cputime+=1
  227.         if not start:
  228.             process[current]['left']-=1
  229.         time_slice-=1
  231. # 高响应比优先算法
  232. def HRRN(process):
  233.     print("-------------------HRRN------------------------------------")
  234.     process=sorted(process,key=lambda x:x['start'])
  235.     processShow(process)
  236.     cputime=0
  237.     current=0
  238.     while True:
  239.         flag=False
  240.         if process[0]['start']==cputime:
  241.             process[current]['runtime']+=cputime
  242.             process[current]['status']="运行"
  243.             process[current]['wait_time']=cputime-process[current]['start']
  244.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  245.             flag=True
  246.         if current<=len(process) and process[current]['runtime']==cputime:
  247.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"结束!")
  248.             process[current]['status']='Die'
  249.             process[current]['tr_time']=cputime-process[current]['start']
  250.             flag=True
  252.         if process[current]['status']=='Die' and current==len(process)-1:
  253.             print("所有进程执行完毕，总计耗时"+str(cputime)+"s")
  254.             conclusion(process)
  255.             break;
  256.         if process[current]['status']=='Die' and process[current+1]['start']<=cputime:
  257.             current+=1
  258.             process[current]['runtime']+=cputime
  259.             process[current]['status']="运行"
  260.             process[current]['wait_time']=cputime-process[current]['start']
  261.             print("第"+str(cputime)+ "s"+"进程"+str(process[current]['id'])+"开始!")
  262.             flag=True
  264.         for i in range(current+1,len(process)):
  265.             if process[i]['start'] == cputime:
  266.                 process[i]['status'] = "就绪"
  267.         process=hrrnSort(process,current+1,cputime)
  268.         if flag:
  269.             status(process)
  270.         cputime+=1
  272. if __name__=="__main__":
  274.     if len(sys.argv)<3:
  275.         print("need more parameter!")
  276.         exit()
  277.     process=processList(int(sys.argv[2]))
  278.     cmd=sys.argv[1].upper()
  279.     if cmd=="FCFS":
  280.         FCFS(process)
  281.     elif cmd=="SJF":
  282.         SJF(process)
  283.     elif cmd=="RR":
  284.         RR(process)
  285.     elif cmd=="HRRN":
  286.         HRRN(process)
  287.     else:
  288.         print("unknown command!")