1、第 5 章处理机调度5.1 调度的层次5.2 作业状态和作业调度5.3 进程调度5.4 进程调度实现举例习题第 5 章处理机调度在多道程序系统中，可能在磁盘上存在一批作业等待处理，那么，如何从这众多的作业中选择一个或几个进入系统，进入系统后创建的若干进程如何去争夺CPU的控制权呢？这正是将要讨论的处理机调度问题。一般来说，一个作业从提交到运行完成，要经过作业调度和进程调度。5.1 调调度度的的层层次次第 5 章处理机调度(1)作业调度，又称为高级调度、宏观调度。其主要功能是按照某种原则从后备作业队列中进行挑选，给选中的作业分配内存等资源，并建立相应的进程，使其投入运行。(2)进程调度，又称为低
2、级调度、微观调度。其主要功能是按照给定的原则从就绪队列中选取一个进程，并为其分配处理机。从上述的描述中可以发现，作业调度和进程调度的功能各不相同，但又有一定的联系。作业调度选择作业进入内存，并为其建立进程，使其具有获得处理机的资格，但不一定能占用处理机并在其上运行。而进程调度就可以决定哪个进程占用处理机，从而为其分配处理机。第 5 章处理机调度5.2.1 作业状态作业状态在批处理系统中，用户向系统提交作业到最后得到结果，一般要经历提交、后备、运行和完成四个状态。作业状态间的转换如图5-1所示。5.2 作业状态和作业调度作业状态和作业调度第 5 章处理机调度图5-1 作业状态第 5 章处理机调度
3、1提交状态提交状态作业的程序、数据及操作说明书交到机房，准备由输入设备输入，此时作业处于提交状态。2后备状态后备状态当作业通过输入设备进入计算机系统后，将作业存在辅存上，为这个作业建立作业控制块，并把它插入到后备作业队列中等待调度。在后备作业队列中的作业处于后备状态。第 5 章处理机调度3运行状态运行状态当一个作业被调度程序选中，并为它分配了必要的资源，建立相应的进程后，作业开始运行，直到完成计算任务为止，作业处于运行状态。4完成状态完成状态当作业正常运行结束或因发生错误而终止执行时，作业处于完成状态。此时，由操作系统将作业控制块(JCB)从当前作业队列中删去，并收回其所占用的资源，将作业运行
4、结果编入输出文件并调用有关设备处理进程输出。第 5 章处理机调度5.2.2 作业调度的功能作业调度的功能作业调度的主要任务是完成作业从后备状态到运行状态和从运行状态到完成状态的转变。为了完成这一任务，作业调度应包含如下功能。1记录已进入系统的各作业的情况记录已进入系统的各作业的情况在外存中有许多作业存在，为了管理和调度这些作业，就必须记录已进入系统中的各作业的情况，并随时记录该作业在各运行阶段的变化。如同前面讲过的进程管理中的PCB一样，系统为每个作业设置一个作业控制块JCB，其中记录了作业的有关信息。对于不同的系统，JCB所包含的信息有所不同，第 5 章处理机调度通常作业控制块中包含的主要内
5、容如下：(1)资源要求。其中包括：估计的运行时间、最迟完成时间、需要的内存容量、外设的类型及数量等。(2)资源使用情况。其中包括：作业进入系统的时间、开始运行时间、已运行时间、内存地址、外设号等。(3)作业名、作业状态。(4)作业类型、作业控制方式和优先权等。作业控制块作为作业存在的唯一标志，使系统可以感知作业的存在。当作业运行完成后，系统撤销JCB，释放有关的资源，并撤销该作业。第 5 章处理机调度2.根据某一调度算法，从后备作业中挑选一个或多个作根据某一调度算法，从后备作业中挑选一个或多个作业运行业运行一般来说，系统中处于后备状态的作业较多，但处于运行状态的作业只是有限的几个。因此，作业调
6、度程序就要按照一定的原则从后备作业中挑选出若干个作业投入运行。第 5 章处理机调度3.为被选中的作业分配运行时所需要的资源为被选中的作业分配运行时所需要的资源作业调度程序挑选作业后，要为该作业建立相应的进程，并为这些进程分配资源，如内存和外部设备等。至于CPU这一资源，作业调度程序只能保证作业有获得CPU的资格，处理机的分配是由进程调度程序来完成的。4.作业结束后作善后处理工作作业结束后作善后处理工作在一个作业运行结束时，作业调度程序要把相应的一些信息进行输出，然后收回该作业所占有的全部资源，撤销与该作业有关的全部进程和该作业的控制块。第 5 章处理机调度5.2.3 调度性能的衡量调度性能的衡
7、量1.调度算法应达到的目标调度算法应达到的目标调度算法即系统所采取的调度策略，规定了从后备作业中选择作业去运行的原则。确定这些原则时，要考虑许多因素，而且这些目标还要和主观上的目标一致，这些目标如下：(1)处理尽可能多的作业。(2)使处理机保持忙碌状态。(3)使输入/输出设备充分使用。(4)对所有的作业公平合理。第 5 章处理机调度这些目标之间也是相互冲突的，任何一个算法要同时满足上述目标是不可能的。要选择一个理想的算法是很困难的，因此，实际采用的调度算法是根据需要而兼顾某些目标。第 5 章处理机调度2.确定调度算法应考虑的因素确定调度算法应考虑的因素(1)调度算法应与系统设计目标一致。例如，
8、批处理操作系统应提高系统的吞吐量；分时操作系统应保证响应时间等。(2)保证系统资源的充分利用，既能兼顾I/O量大的作业，又能兼顾计算量大的作业，使CPU与I/O设备得到均衡使用。(3)尽量缩短作业在系统中的平均周转时间，使用户可以尽快地得到运行结果。对于一个系统而言，考虑的因素越多，就会导致算法越复杂，从而增加系统开销，影响对资源的利用率。因此，大多数系统往往采用比较简单的调度算法。第 5 章处理机调度3调度性能的衡量标准调度性能的衡量标准一个调度算法性能的好坏，通常采用平均周转时间和平均带权周转时间来衡量。(1)周转时间。作业i的周转时间Ti为Ti=Tei-Tsi 其中，Tei为作业的完成时
9、间，Tsi为作业的提交时间。第 5 章处理机调度对于进入系统的n个作业而言，平均周转时间T为T=n1n1iiT 一个作业的周转时间说明了该作业在系统内停留的时间，它包含两个部分，一个是等待时间Tw，另一个是运行时间Tr，即Ti=Tw+Tr第 5 章处理机调度为了保证系统吞吐量大，系统资源利用率高，应使Ti越小越好，所以平均周转时间越小调度性能越好。(2)带权周转时间。一个作业的周转时间等于它的运行时间和等待时间之和，如果有两个作业，它们的运行时间不等，但进入系统后等待的时间相等，这时，这两个作业的周转时间仍不相等。但从调度的角度来看，系统让它们等待的时间一样，所以，为了更好地说明调度性能，应去
10、掉作业运行时间的因素，于是提出了带权周转时间的概念，作业i的带权周转时间Wi为Wi=riTT 第 5 章处理机调度作业的带权周转时间等于它的周转时间除以运行时间，它可以说明作业的相对等待时间。每个用户都希望在提交作业后能立即投入运行并一直运行到完成，使作业的周转时间最短。但是，从系统运行的角度来说，不可能满足每个用户的这种要求。因此系统尽量选择作业的平均周转时间或平均带权周转时间短的某种算法，来提高资源的利用率，使大多数用户感到满意。第 5 章处理机调度5.2.4 作业调度算法作业调度算法1.先来先服务调度算法先来先服务调度算法这种调度算法按作业到达系统的先后次序进行调度。该算法优先考虑在系统
11、中等待时间最长的作业，而不考虑作业运行时间的长短。这种算法简单，容易实现，但效率较低。由于该算法没有考虑各个作业运行特征和资源要求的差异，所以影响了系统效率的发挥。假定有4个作业，它们的提交、运行、完成的情况如表5-1所示。按先来先服务的调度算法进行调度，并求出平均周转时间和平均带权周转时间(时间单位：小时，以十进制进行计算)。第 5 章处理机调度表表5-1 先来先服务调度算法先来先服务调度算法作业 提交时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 1 8:00 2.00 8:00 10:00 2.00 1 2 8:50 0.50 10:00 10:50 2.00 4 3 9:0
12、0 0.10 10:50 10:60 1.60 16 4 9:50 0.20 10:60 10:80 1.30 6.5 第 5 章处理机调度平均周转时间T=1.725小时，平均带权周转时间W=6.875小时。2短作业优先调度算法短作业优先调度算法这种调度算法总是从作业的后备队列中挑选运行时间最短的作业作为下一个调度运行的对象。这种算法效率比较高，也比较容易。但该算法只考虑了作业的运行时间，而忽略了作业的等待时间。如果系统不断接收新的短作业，就会使长作业长时间等待而不能运行。如果对上例的作业采用短作业优先调度算法，则算出的平均周转时间和平均带权周转时间如表5-2所示(时间单位：小时，以十进制进行
13、计算)。第 5 章处理机调度表表5-2 短作业优先调度算法短作业优先调度算法第 5 章处理机调度平均周转时间T=1.55小时，平均带权周转时间W=5.15小时。调度过程如下：在8.00时，因为只有作业1到达，系统将作业1投入运行。作业1运行2小时完成。即作业1的完成时间是10.00，在该时间，作业2，3，4均已到达系统。由于采用短作业优先调度算法，这样在作业1执行完后，要比较剩下三个作业的运行时间，作业运行时间最短为0.10，因此选择作业3运行，然后按运行时间排序依次为作业4、作业2。第 5 章处理机调度3响应比高者优先调度算法响应比高者优先调度算法这种调度算法在每次调度作业运行时，先计算后备
14、作业队列中每个作业的响应比，然后挑选响应比最高者投入运行。响应比的计算公式如下：响应比=作业运行时间作业运行时间作业等待时间 第 5 章处理机调度从公式中可以看出，一个作业的响应比随着等待时间的增加而提高。如果系统中某一作业等待足够长的时间，它就会成为响应比最高者而获得运行的机会。在相同等待时间的情况下，短作业优先，对于相同运行时间的作业，等待时间长的作业优先运行。假定有4个作业，它们的提交、运行、完成的情况如表5-3所示。按响应比高者优先调度算法进行调度，并求出平均周转时间和平均带权周转时间(时间单位：小时，以十进制进行计算)。第 5 章处理机调度表表5-3 响应比高者优先调度算法响应比高者
15、优先调度算法第 5 章处理机调度平均周转时间T=1.975，平均带权周转时间W=6.65。调度过程如下：在8.00时，因为只有作业1到达，系统将作业1投入运行。作业1运行2小时完成。由于采用响应比高者优先调度算法，这样在作业1执行完后，要计算剩下三个作业的响应比，然后选响应比高者去运行。三个作业的响应比计算如下：r2=1+(10.0-8.3)/0.5=4.4r3=1+(10.0-8.5)/0.1=16r4=1+(10.0-9.0)/0.4=3.5第 5 章处理机调度从计算结果看，作业3的响应比高，所以让作业3先运行。作业3运行0.1小时完成，此时，要计算剩余的作业2和作业4的响应比：r2=1+
16、(10.1-8.3)/0.5=4.6r4=1+(10.1-9.0)/0.4=3.75从计算结果看，作业2的响应比高，所以让作业2先运行，然后作业4运行。第 5 章处理机调度4.优先数调度算法这种调度算法综合考虑有关因素，例如作业的缓急程度、等待时间的多少、外部设备的使用情况等，根据系统设计目标来考虑各种因素对优先数的影响比例，然后按比例确定各作业的优先数，系统按优先数的高低将作业排序，优先数高的首先调度。第 5 章处理机调度下面给出一个例子来综合说明作业调度算法。【例例5-1】设有一组作业，它们的提交时间及运行时间如表5-4所示，试求采用先来先服务调度算法、短作业优先调度算法和响应比高者调度算
17、法的平均周转时间和平均带权周转时间，并指出它们的调度顺序。第 5 章处理机调度表表5-4 作业的提交时间和运行时间情况作业的提交时间和运行时间情况第 5 章处理机调度解解(1)采用先来先服务调度算法，其调度情况如表5-5所示。平均周转时间T=58.75分钟，平均带权周转时间W=4.5。其调度顺序为1、2、3、4。(2)采用短作业优先调度算法，其调度情况如表5-6所示。第 5 章处理机调度表表5-5 采用先来先服务调度算法的作业调度情况采用先来先服务调度算法的作业调度情况作业号 提交时间 运行时间/分钟 开始时间 完成时间 周转时间/分钟 带权周转时间 1 8:00 70 8:00 9:10 7
18、0 1 2 8:40 30 9:10 9:40 60 2 3 8:50 10 9:40 9:50 60 6 4 9:10 5 9:50 9:55 45 9 第 5 章处理机调度表表5-6 采用短作业优先调度算法的作业调度情况采用短作业优先调度算法的作业调度情况第 5 章处理机调度平均周转时间T=46.25分钟，平均带权周转时间W=2分钟。其调度顺序为1、4、3、2。(3)采用响应比高者优先调度算法，其调度情况如表5-7所示。第 5 章处理机调度表表5-7 采用响应比高者优先调度算法的作业调度情况采用响应比高者优先调度算法的作业调度情况第 5 章处理机调度平均周转时间T=47.5分钟，平均带权周
19、转时间W=2.38分钟。其调度顺序为1、3、4、2。第 5 章处理机调度5.3.1 进程调度的功能进程调度的功能1记录和保持系统中所有进程的有关情况和状态特征记录和保持系统中所有进程的有关情况和状态特征进程在活动期间的状态是在不断改变的，如由就绪转为运行，由运行转为等待，由等待转为就绪。要改变进程的状态，可以通过进程的PCB在运行队列、各种等待队列和就绪队列之间的转换来实现，在状态改变同时，还要对进程控制块PCB的内容作相应的登记和修改，来记录进程的有关情况。例如，将进程由等待状态转为就绪状态，是通过将该进程的PCB从等待队列中删除，然后插入到就绪队列中实现的，同时将该进程PCB中记录其状态的
20、信息由“等待”改为“就绪”。5.3 进进 程程 调调 度度第 5 章处理机调度2决定分配策略决定分配策略在处理机空闲时，根据一定的原则选择一个进程去运行，同时确定获得处理机的时间。分配策略实际上是由就绪队列排序原则体现的。3实施处理机的分配和回收实施处理机的分配和回收当正在运行的进程由于某种原因让出处理机时，应将该进程的状态改为“阻塞”，并插入相应队列中，还须保留该进程的CPU现场。第 5 章处理机调度处理机调度的时机有以下几种可能：(1)进程完成其任务。(2)执行中的进程自己调用阻塞原语将自己阻塞起来进入等待状态。(3)执行中的进程调用了P原语操作，从而因资源不足而被阻塞。(4)在分时系统中
21、，当进程使用完规定的时间片后，该进程让出处理机。(5)执行中的进程提出I/O请求后被阻塞。第 5 章处理机调度5.3.2 进程调度的算法进程调度的算法常用的进程调度算法有先来先服务、优先数、时间片轮转和分级调度等算法。1.先来先服务调度算法先来先服务调度算法这种调度算法是按照进程进入就绪队列的先后次序选择可以占用处理机的进程的。当有新进程就绪时，把该进程排入就绪队列的末尾，进程调度程序总是把处理机分配给就绪队列中的第一个进程。一旦一个进程占用了处理机，它就一直运行直到因等待某事件或进程完成任务才让出处理机。第 5 章处理机调度该算法实现起来很简单，但由于进程进入就绪队列的随机性，可能会导致进程
22、等待处理机的平均时间较长。例如，就绪队列中依次有三个进程P1，P2，P3，进程P1和进程P2需要5毫秒可以完成任务，而进程P3需要20毫秒完成。按照先来先服务算法，执行的顺序为P1P2P3，它们的平均等待时间为(0+5+10)/3=5毫秒。如果进程是按P3，P2，P1的次序排入队列，这三个进程的平均等待时间为(25+20+0)/3=15毫秒。可见当运行时间长的进程先就绪的话，系统效率会受到影响。第 5 章处理机调度2优先数调度算法优先数调度算法对每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理机。如果进程具有相同的优先数，则按先来先服务的次序分配处理机。在就绪队列中的进程是
23、按优先数从大到小排列的，当有新进程就绪时，就根据它的优先数插入到就绪队列的适当位置。进程调度也总是把处理机分配给就绪队列中的第一个进程。第 5 章处理机调度如何为进程确定优先数呢？进程被创建时系统为其确定一个优先数，进程的优先数可以是固定的，即不随进程的执行而改变。以这种方式指派给进程的优先数称为静态优先数。采用静态优先数的调度算法比较简单，但不够精确。因为在进程执行的整个过程中，原来优先数所依赖的特征都在不断地改变，所以，静态优先数并不能自始至终反映出这些特性。如果能在进程运行中，不断地随着特性的改变而修改优先数，就可以更精确地调度，获得更好的调度性能，这种能不断被改变的优先数称为动态优先数
24、。第 5 章处理机调度一个高优先数的进程占用处理机后，系统可以用两种方式来对待它。第一种方式是“非抢占式”的，一旦某个高优先级的进程占用了处理机，就一直运行下去直到该进程由于自身的原因主动让出处理机或进程执行结束让出处理机。另一种方式是“可抢占”的，这种方式可以保证总是让更高优先级的进程占用处理机。即当某一进程在处理机上运行时，一旦有一个更高优先数的进程就绪，就会剥夺正在处理机上运行的进程使用处理机的权力，把处理机分配给更高优先级的进程。第 5 章处理机调度3时间片轮转调度算法时间片轮转调度算法把规定进程一次使用处理机的最长时间称为“时间片”。时间片轮转调度算法让就绪进程按就绪的先后次序排成队
25、列，每次总是选择就绪队列中的第一个进程占用处理机，但规定只能使用一个“时间片”。如果一个时间片用完，进程的工作尚未结束，则它也必须让出处理机给其他进程使用，自己被重新排到就绪队列的末尾，等待再次运行。如果在一个时间片的时间内进程发生了等待事件，也要把处理机让给下一个就绪的进程使用，自己被排入等待队列。等待事件结束后，仍需排入就绪队列的末尾，当再次轮到运行时，重新开始使用一个新的时间片。第 5 章处理机调度这样，就绪队列中进程就依次轮流地占用处理机运行，一次运行未完成工作的进程可作第二次、第三次或更多的轮转，直至进程完成工作。时间片轮转调度算法经常用在分时系统中。在一个分时系统中，多个用户通过终
26、端设备同时与计算机系统进行交互，计算机系统应及时地对每一个用户的要求做出应答。采用时间片轮转的办法可使每一个用户都感到计算机系统对自己有求必应，好像自己在单独使用计算机系统。第 5 章处理机调度时间片取值的大小关系到计算机系统的效率和用户的满意度，所以，时间片的值应根据进程要求系统给出应答的时间和进入系统的进程数来决定。如果要求系统快速应答则时间片小一些，这样使轮转一遍的总时间减少而可对进程尽快应答。如果进程数少，则时间片可以大一些，这样可减少进程调度的次数，提高系统效率。对每个进程可规定相同的时间片，也可对不同的进程规定不同的时间片。例如，对很少使用外部设备而运算时间长的进程，给一个大一些的
27、时间片，以达到减少调度次数、加快进程执行速度的目的。第 5 章处理机调度4分级调度算法分级调度算法这种调度算法由系统设置多个就绪队列，每个就绪队列中的进程按时间片轮转法占用处理机。具体的调度原则是：(1)当有进程就绪时，排入第一级就绪队列的末尾；(2)当某就绪队列的一个进程获得处理机并用完规定的时间片后，它的工作尚未结束，则排入下一级就绪队列的末尾；(3)当最后一级中的进程占用处理机运行一个规定的时间片后，它的工作尚未结束，则仍排入本队列末尾；第 5 章处理机调度(4)当占用处理机的进程在规定的时间片内运行时出现等待事件，则排入等待队列，等待结束后成为就绪状态排入第一级就绪队列；(5)第一级就
28、绪队列的优先级高，每次总是先选择第一级就绪队列中的进程，仅当该队列为空时，才从第二级就绪队列中选进程，若仍为空，则再从下一级就绪队列中选，依次类推。如图5-2所示。第 5 章处理机调度图5-2 分级调度算法 第 5 章处理机调度对不同就绪队列中的进程，可规定使用不同长度的时间片。一般来说，第一级就绪队列的时间片短一些，以后各级就绪队列的时间片逐级增长，最后一级就绪队列的时间片最长。这样，运行时间短的进程只需经过前面几级队列就能得到结果，且它们被优先调度，有利于提高系统的吞吐量。而对运行时间长的进程在进入了低级就绪队列后可得到较长的时间片，以减少调度次数来保证系统效率。第 5 章处理机调度例如，
29、对经常使用外围设备的进程来说，每次等待外围设备传输结束后总是排入第一级就绪队列，它们会被优先调度，有利于处理机与外围设备传输以及外围设备之间的并行工作，从而提高资源的使用效率。但也会存在问题，需运行时间长的进程进入低级就绪队列后，有可能会长时间得不到处理机，需要确定一种原则将低级就绪队列中的进程移到高一级的就绪队列中，使其能及时被运行。第 5 章处理机调度下面给出一个例子来综合说明进程调度算法。【例例5-2】某系统的进程状态如图5-3所示。1.请说明一个进程发生变迁3的原因。发生变迁2、变迁4的原因又是什么？2.下述因果变迁是否会发生？如果有可能的话，在什么情况下发生？21 35 42 31
30、3.请根据此状态变迁图叙述该系统的调度策略、调度效果。第 5 章处理机调度图5-3 进程状态图第 5 章处理机调度解：解：(1)发生变迁的原因变迁3：一个运行进程因请求I/O这一操作系统服务功能时由运行状态变为等待状态，从而发生变迁3。变迁2：该系统采用的是按时间片轮转的调度算法，当时间片到时，运行进程由运行状态转变为就绪状态，从而发生变迁2。变迁4：当I/O完成时，一个进程由等待状态转变为就绪状态，从而发生变迁4。第 5 章处理机调度(2)所谓因果变迁，指的是有两个变迁，一个变迁的发生会引起另一个变迁的发生，前一个为因，后一个为果。21 这两个变迁是因果变迁。即当运行进程因时间片到由运行状态
31、变为就绪状态时，CPU空闲，必然引起进程调度，使一个处于就绪状态的进程由就绪状态变为运行状态，可能发生变迁1。发生此因果变迁的条件：当时间片到时，高优先队列为空。第 5 章处理机调度35 这两个变迁是因果变迁。即当运行进程因需要I/O设备而由运行状态变为等待状态时，CPU空闲，必然引起进程调度，使一个处于就绪状态的进程由就绪状态变为运行状态，就可能发生变迁5。发生此因果变迁的条件：当时间片到时，高优先队列不为空。第 5 章处理机调度42 这两个变迁不是因果变迁，因为当一个进程由等待状态变为就绪状态时，不会使运行进程放弃CPU，而变迁2却使CPU空闲。31 这两个变迁是因果变迁。即当运行进程因需
32、要I/O设备而由运行状态变为等待状态时，CPU空闲，必然引起进程调度，使一个处于就绪状态的进程由就绪状态变为运行状态，可能发生变迁1。发生此因果变迁的条件：当时间片到时，高优先队列为空。第 5 章处理机调度(3)调度策略：系统采用时间片轮转调度和优先数调度相结合的一种调度策略。分两个就绪队列，从高优先就绪队列中选择进程。当高优先就绪队列为空时，则从低优先就绪队列中选择进程去运行。调度效果：优先照顾了I/O量大的进程，这样的进程处于高优先就绪队列中，当CPU空闲时，首先从该队列中选择进程去运行，所以I/O量大的进程被调度的机会多。而且由于它计算量相对小，所以每次赋予较小的时间片也就够了。而计算量
33、大的进程处于低优先就绪队列，不容易被调度上，但一旦选中，就可以给较大的时间片，对这类进程作了适当的照顾。该调度策略使系统设备的利用率较高，因为优先照顾了I/O量大的进程，系统开销也不大，且由于对计算量大的进程给予的时间量大，减少了这类进程的调度开销。第 5 章处理机调度1.实验内容实验内容进程调度模拟实验。2.实验目的实验目的通过模拟进程调度算法，了解进程调度的过程并比较不同的调度算法的区别。3.实验题目实验题目设计一段程序来模拟优先级调度算法和时间片轮转算法。要求可以指定进程的数量、各进程需要CPU的时间和各进程的优先级。5.4 进程调度实现举例进程调度实现举例第 5 章处理机调度4.实验提
34、示实验提示(1)进程调度算法是指处理机的分配策略。优先数调度算法是指对每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理机。如果进程具有相同的优先数，则按先来先服务的次序分配处理机。在本实例中采用动态优先数算法。时间片轮转算法是指就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占用处理机，但规定只能使用一个“时间片”。(2)系统中的进程可以用进程控制块PCB来表示，PCB的结构定义如表5-8所示：第 5 章处理机调度表表5-8 PCB结构结构第 5 章处理机调度(3)在进程调度时进程会交替地出现在运行、就绪和完成三种状态。可以定义三个链表来存放三种状态的进
35、程。当进程运行时就把进程放入到运行链表中；当进程处于就绪状态时就将进程放入到就绪链表中；当进程运行完毕时就将进程放入到完成链表中。由于同一时刻运行的进程只能有一个，所以运行链表只能有一个结点。在实例程序中为了使程序更简洁，忽略了进程的等待状态，仅运行了优先数调度算法，由于篇幅有限，仅显示部分结果，对于时间片轮转调度算法，请读者自行运行。(4)主要变量及函数说明如表5-9所示。第 5 章处理机调度表表5-9 主要变量及函数说明主要变量及函数说明第 5 章处理机调度5.实例代码实例代码/进程调度算法proc.c/运行环境Redhad9.0 gcc 4.0#include#include typed
36、ef struct pcb/定义PCB结构第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调
37、度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度第 5 章处理机调度1.作业调度与进程调度的功能分别是什么？它们之间有什么区别与联系？2.作业调度的性能评价标准有哪些？这些性能评价标准在任何情况下都能反映调度策略的优劣吗？3.进程调度的时机有哪些？4.若在后备作业队列中等待运行的作业同时有三个，即1、2、3，已知它们各自的运行时间分别为a、b、c，且满足关系abc，试证明采用短作业优先调度算法能获得最小平均周转时间。习习 题题第 5 章处理机调度5.作业1，2，3的提交时间和运行时间如表5-10所示。采用短作业优先调度算法和先来先服务调度算法，试问平均周转时间各为多少？是否还有更
38、好的调度策略存在？第 5 章处理机调度表表5-10 作业的提交时间与运行时间作业的提交时间与运行时间第 5 章处理机调度6.有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法。如表5-11所示的作业序列，作业优先数即为进程优先数，优先数越小优先级越高。(1)列出所有作业进入内存的时间及结束时间。(2)计算平均周转时间。第 5 章处理机调度表表5-11 作业序列情况作业序列情况 第 5 章处理机调度7.在一个单处理器的多道程序设计系统中，现有两道作业同时执行，其中一道以计算为主，另一道以输入输出为主，你将怎样赋予作业进程占有处理机的优先级？为什么？8.当进程调度选中一个进程后，怎样才能让它占用处理器？9.在分级调度算法中，为什么对不同就绪队列中的进程规定使用不同长度的时间？10.有5个进程P1，P2，P3，P4，P5它们同时依次进入就绪队列，它们的优先数和需要的处理器时间如表5-12所示。如果忽略进程调度等所花费的时间，请回答下列问题：第 5 章处理机调度表表5-12 进进 程程 情情 况况第 5 章处理机调度(1)写出分别采用“先来先服务”和“非抢占式的优先数”调度算法选中进程执行的次序。(2)分别使用上述两种算法计算出各进程在就绪队列中的等待时间以及两种算法下的平均等待时间。
