第三章_B调度算法

3.3调度算法进程调度算法类型算法类型简单的调度算法先来先服务算法短作业（进程）优先最高响应比优先优先权法抢占式优先权非抢占式优先权静态优先权动态优先权多级反馈队列算法时间片轮转法1.先来先服务First-Come-First-Served（FCFS）（作业／进程）调度算法FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。FCFS算法易于实现，表面上很公平。CPU就绪队列123后备队列内存例题:在单道环境下，某批处理有四道作业，已知他们的进入系统的时刻、估计运算时间如下：作业进入时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间8.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间T＝平均带权周转时间T’＝作业进入时刻运行时间开始时刻完成时刻周转时间12348.008.509.009.502.000.500.100.20带权周转用FCFS算法:计算作业的运行情况、平均周转时间和平均带权周转时间完成时间=开始时间+运行时间周转时间=完成时间—进入时间带权周转时间=周转时间/运行时间6.875（h）1.725（h）FCFS算法调度例2作业名进入时间运行时间（分）需内存量KBA8:064215B8:183060C8:302450D8:362410E8:421220有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法名装入内存时间开始时间结束时间周转时间带权周转时间A8:068:068:484242/42B8:188:489:186060/30D8:369:189:426666/24C9:189:4210:069696/24E9:1810:0610:189696/12有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法作业名进入时间运行时间（分）需内存量KBA8:064215B8:183060C8:302450D8:362410E8:421220100K15K60K10K15KFCFS总结：FCFS根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。2.短作业／进程优先(SJF/ShortestProcessNext)调度算法这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用SJF有利于系统减少平均周转时间和平均带权周转时间。作业进入时刻(h)运行时间(h)12348.008.509.009.502.000.500.100.20例题：用SJF算法计算作业的运行情况、平均周转时间和平均带权周转时间该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.0028.500.5039.000.1049.500.20平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0028.500.5039.000.1049.500.20平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5039.000.1049.500.20平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5039.000.1010.0049.500.20平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5039.000.1010.0010.1049.500.20平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5039.000.1010.0010.1049.500.2010.10平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5039.000.1010.0010.1049.500.2010.1010.30平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5010.3039.000.1010.0010.1049.500.2010.1010.30平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5010.3010.8039.000.1010.0010.1049.500.2010.1010.30平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.0028.500.5010.3010.8039.000.1010.0010.1049.500.2010.1010.30平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.0028.500.5010.3010.802.3039.000.1010.0010.101.1049.500.2010.1010.300.80平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周转时间T＝平均带权周转时间T’＝最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周转时间T＝1.55h平均带权周转时间T’＝5.15h最短作业优先法（SJF）该算法总是优先调度要求运行时间最短的作业作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00平均周转时间T＝1.55h平均带权周转时间T’＝5.15h最短作业优先法（SJF）运行顺序1342作业进入时刻运行时间开始时刻完成时刻周转时间带权周转18.002.008.0010.002.001.0028.500.5010.3010.802.304.6039.000.1010.0010.101.1011.0049.500.2010.1010.300.804.00作业进入时刻运行时间开始时刻完成时刻周转时间12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50带权周转缺点：1有利于短作业，不利于长作业；2未考虑作业紧迫程度;图3-4FCFS和SJF调度算法的性能SJF算法例作业名进入时间运行时间（分）需内存量KBA8:064215B8:183060C8:302450D8:362410E8:421220有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用SJf算法名装入内存时间开始时间结束时间周转时间带权周转时间A8:068:068:484242/42D8:368:489:123636/24B8:189:129:428484/30E9:129:429:544242/12C9:429:5410:183636/24作业名进入时间运行时间（分）需内存量KBA8:064215B8:183060C8:302450D8:362410E8:421220100K15K60K10K15K例：A请求系统服务时间5s，B请求系统服务时间为100s，设第0到第5秒前，CPU运行C进程。第1秒时B进入系统内存，第2秒时A进入内存当CPU空闲，需要调度进程时根据不同的算法选择A或B问：分别计算FCFS算法下和SJF算法下，A和B的周转时间，带权周转时间和系统平均周转时间BA调度算法比较例题FCFS算法－－先来先服务B：周转时间为4＋100＝104s带权周转时间为104/100＝1.04A：周转时间为3+100+5＝108s带权周转时间为108/5＝21.6平均带权周转时间为(21.6+1.04)÷2＝11.32SJF算法－－短进程优先A：周转时间为3+5＝8s带权周转时间为8/5＝1.6B：周转时间为4+5+100＝109s带权周转时间为109/100＝1.09平均带权周转时间为(1.6+1.09)÷2＝1.345调度算法比较例先调度B后调度A先调度A后调度B调度顺序调度顺序短作业（进程）优先算法SJ（P）F不一定能真正做到短作业优先调度未考虑作业的紧迫程度，因而不能保证紧迫性作业被及时处理不利于长作业，当不断有短进程到达时，不保证长进程响应的及时性，甚至可能得不到调度3.高响应比优先HighestResponseRatioNext(HRRN)(作业)调度算法按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比RP，然后选择其值最大的作业投入运行。RP值定义为：RP＝（已等待时间＋要求运行时间）／要求运行时间＝1＋已等待时间／要求运行时间HRN算法实际上是FCFS算法和SJF算法的折衷。