搜索
关于调度算法【例1】下表给出作业l，2，3的提交时间和运行时间。采用先来先服务调度算法和短作业优先调度算法，试问作业调度次序和平均周转时间各为多少？（时间单位：小时，以十进制进行计算。）作业号提交时间运行时间1230.00.41.08.04.01.0分析解这样的题关键是要根据系统采用的调度算法，弄清系统中各道作业随时间的推进情况。我们用一个作业执行时间图来形象地表示作业的执行情况，帮助我们理解此题。采用先来先服务调度算法，是按照作业提交的先后次序挑选作业，先进入的作业优先被挑选。然后按照“排队买票”的办法，依次选择作业。其作业执行时间图如下：采用短作业优先调度算法，作业调度时根据作业的运行时间，优先选择计算时间短且资源能得满足的作业。其作业执行时间图如下：由于作业1，2，3是依次到来的，所以当开始时系统中只有作业1，于是作业1先被选中。在8.0时刻，作业1运行完成，这时系统中有两道作业在等待调度，作业2和作业3，按照短作业优先调度算法，作业3只要运行1个时间单位，而作业2要运行4个时间单位，于是作业3被优先选中，所以作业3先运行。待作业3运行完毕，最后运行作业2。作业调度的次序是1，3，2。另外，要记住以下公式：作业i的周转时间Ti＝作业完成时间－作业提交时间系统中个作业的平均周转时间，其中Ti为作业i的周转时间。解：采用先来先服务调度策略，则调度次序为l、2、3。作业号提交时间运行时间开始时间完成时间周转时间10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周转时间T＝（8＋11.6＋12）/3＝10.53采用短作业优先调度策略，则调度次序为l、3、2。作业号提交时间运行时间开始时间完成时间周转时间10.08.00.08.08.031.01.08.09.08.020.44.09.013.012.6平均周转时间T＝（8＋8＋12.6）/3＝9.53思考题1请同学们判断这句话：作业一旦被作业调度程序选中，即占有了CPU。（）提示：需要清楚作业调度和进程调度的区别。【例2】考虑下述页面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当内存块数量分别为3时，试问FIFO、LRU、OPT这三种置换算法的缺页次数各是多少?答：缺页定义为所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。当内存块数量为3时：发生缺页中断的次数为16。在FIFO算法中，先进入内存的页面被先换出。当页6要调入时，内存的状态为4、1、5，考查页6之前调入的页面，分别为5、1、2、4，可见4为最先进入内存的，本次应换出，然后把页6调入内存。发生缺页中断的次数为15。在LRU算法中，最近最少使用的页面被先换出。当页6要调入时，内存的状态为5、2、1，考查页6之前调入的页面，分别为5、1、2，可见2为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。发生缺页中断的次数为11。在OPT算法中，在最远的将来才被访问的页面被先换出。当页6要调入时，内存的状态为1、2、5，考查页6后面要调入的页面，分别为2、1、2、…，可见5为最近一段时间内使用最少的，本次应换出，然后把页6调入内存。【例3】在一个单道的程序设计系统中，有3个作业J1、J2、J3，它们到达输入井的时间分别为8：50、9：00、9：30，它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在10：00按响应比高者优先算法对它们进行调度，请回答：（1）作业被选中执行的次序是什么？（2）三个作业被选中时的响应比分别是多少？分析响应比＝作业周转时间/作业运行时间＋作业等待时间/作业运行时间系统在10：00，计算作业的响应比：以J1为例，它的作业计算时间是1.5小时，即90分钟；J1从8：50到达输入井，在10：00时刻，J1的等待时间为70分钟，因此作业J1的响应比为：1＋70分钟/90分钟=1.77同理，J2：1＋60分钟/24分钟=3.5J3：1＋30分钟/60分钟=1.5因此按照响应比高者优先算法，优先调度J2。在10：24，J2完成。这时计算J1、J3的响应比：J1：1＋（70＋24）分钟/90分钟=2.04J3：1＋（30＋24）分钟/60分钟=1.9按照响应比高者优先算法，优先调度J1。在11：54，J1完成，系统调度J3，J3的响应比为1＋（30＋24＋90）分钟/60分钟=3.4因此，作业被选中执行的次序是J2、J1、J3。三个作业被选中时的响应比分别是：J1，2.04；J2，3.5；J3，3.4。解：（1）作业被选中执行的次序是J2、J1、J3。（2）三个作业被选中时的响应比分别是：J1，1.04；J2，2.5；J3，2.4。思考题2某作业的提交时间为10：30，需要运行的时间为1小时，假设11：00开始调度，它的响应比是。【例4】设有进程A、B、C、D依次进入就绪队列（相隔一个时间单位），它们的优先级（优先数大的优先级较高）如下表所示：进程CPU时间优先数A203B151C84D103试问采用“先来先服务”、“静态优先数法”调度算法（注：优先数大的优先级高），选中进程的执行次序。解：采用先来先服务调度算法，按照进程进入就绪队列的先后次序占有CPU，其执行次序是A-B-C-D。采用静态优先数法，进程A最先就绪，在0时刻先占有CPU运行，随后1时刻进程B进入就绪队列，2时刻进程C进入就绪队列，3时刻进程D进入就绪队列。由于采用静态优先数法，不容许随时间的推移改变进程的优先级，所以当进程A运行结束时，系统的就绪队列中有B、C、D三个进程，而进程C优先级最高，于是选中C；这样分析下去，进程的执行次序是A-C-D-B。思考题3时间片轮转调度算法是为了（）。A．多个终端都能得到系统的及时响应B．先来先服务C．优先级高的进程先使用CPUD．紧急事件优先处理参考解答思考题1：错误。作业被作业调度程序选中，说明作业处于运行状态，即该作业进入内存并以进程的形式存在于系统中，但属于该作业的进程可能处于运行、就绪和等待状态，只有处于运行状态的进程才能占有处理机，而其余两种状态的进程并不占有处理机。作业调度和进程调度的区别：一个作业从进入系统到最后完成，一般至少要经历两级调度：作业调度和进程调度。作业调度是宏观上的高级调度，它的主要功能是根据一定的算法，从输入井中选中若干个作业，分配必要的资源，如主存、外设等，为它们建立初始状态为就绪的作业进程。进程调度是微观上的低级调度，它的主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。一般的操作系统都必须有进程调度。可见在多道系统中，作业调度与进程调度是相互配合来实现多道作业的并行执行的。两者的关系可用下图表示。思考题2：1.5（注：作业等待0.5小时，运行1小时，响应比=1＋0.5/1=1.5）思考题3：A【例5】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址需要多少二进制位表示？（2）物理地址需要多少二进制位表示？分析在分页存储管理中，逻辑地址结构如下图所示。它由两个部分组成：前一部分表示该地址所在页面的页号p；后一部分表示页内地址（页内位移）d。页号的地址位数决定了页的多少，假设页号有20位，则地址空间中最多可容纳的页面数为220，即1MB个页面。页内地址位数确定了每页的大小，若页内地址为12位，则每页大小为212，即2KB。同理，物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。解因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。【例6】若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，4000，5012转化为相应的物理地址。\000Bã页号块号01232316分析页式存储管理的地址结构是一维的，即逻辑地址（或物理地址）只用一个数值即可表示。若给定逻辑地址A，页面的大小为L，则页号p和页内地址d可按照下式求得：p=int[A/L]d=AmodL其中，int是取整函数（取数值的整数部分），mod是取余函数（取数值的余数部分）。页表的作用是实现从页号到物理块号的地址映射。以逻辑地址的页号检索页表，得到该页的物理块号；同时将页内地址d直接送入物理地址寄存器的块内地址字段中。这样物理块号和块内地址拼接成了实际访问内存的地址，从而完成了从逻辑地址到物理地址的转换。所以物理地址的计算公式为：物理地址＝块的大小（即页的大小L）´块号f＋页内地址d解:本题中，为了描述方便，设页号为p，页内位移为d，则：（1）对于逻辑地址1011，p＝int（1011/1024）＝0，d＝1011mod1024＝1011。查页表第0页在第2块，所以物理地址为1024´2＋1011＝3059。（2）对于逻辑地址2148，p＝int（2148/1024）＝2，d＝2148mod1024＝100。查页表第2页在第1块，所以物理地址为1024＋100＝1124。（3）对于逻辑地址4000，p＝int（4000/1024）＝3，d＝4000mod1024＝928。查页表第3页在第6块，所以物理地址为1024´6＋928＝7072。（4）对于逻辑地址5012，p＝int（5012/1024）＝4，d＝5012mod1024＝916。因页号超过页表长度，该逻辑地址非法。【例7】某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址是什么？分析在分页存储管理方式中，逻辑地址结构为：如果给定的逻辑地址是A，页面大小为L，则页号p和页内地址d可按下式求得：p=int[A/L]d=[A]modL其中，int表示取结果的整数部分，mod表示取结果的余数部分。页号的位数表示地址空间中最多可容纳的页面个数，页内地址位数表示第页的大小，页表的作用是实现从页号到物理块号的地址映射。在页式存储管理中，逻辑空间页的大小与主存地址空间中块的大小相同。一般：物理地址与页号、块号和页内地址之间存在如下关系物理地址=块的大小（页的大小L）*块号+页内地址d解：页式存储管理的逻辑地址分为两部分：页号和页内地址。由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=210，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。逻辑地址0A5C（H）所对应的二进制表示形式是：000101001011100，根据上面的分析，下划线部分为页内地址，编码“00010”为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：0100，拼接块内地址1001011100，得01001001011100，即125C（H）。逻辑地址0A5C（H）所对应的物理地址是125C（H）。【例8】某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K一逻辑地址为（2，154）的实际物理地址为多少？答：逻辑地址（2，154）表示段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。【例9】下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：96K、20K、200K。若采用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业的请求，为什么？分区号大小起始地址1234532K10K5K