操作系统练习答案.doc

练习1、在下列调度算法中，对所有进程和作业都是公平合理的调度算法是（ D多级反馈队列 ），最有利于提高系统吞吐量的作业调度算法是（ B短作业优先 ），能兼顾作业等待时间和作业执行时间的调度算法是（ E高响应比优先 ），最有利于提高资源的利用率，使大部分用户比较满意的调度算法是（ C时间片轮转 ），为实现人机交互而采用的调度算法，能对紧急作业进行及时处理的调度算法是（ F可抢占式优先级 ）。A先来先服务B短作业优先C时间片轮转D多级反馈队列E高响应比优先F可抢占式优先级调度2、假设有一计算机系统中有4个进程，各进程的执行时间和到达就绪队列的时间如下：进程到达就绪队列时间总执行时间P108P214P329P435试用剥夺式短进程优先调度算法和时间片轮转调度（时间片为2个基本时间单位），分别给出每个进程的调度次序及平均周转时间。进程到达就绪队列时间总执行时间执行时间周转时间P1080-1 10-1717P2141-54P32917-2624P4355-107进程到达就绪队列时间总执行时间执行时间周转时间P1080-2 8-10 16-18 21-2323P2142-4 10-1211P3294-6 12-14 18-20 23-25 25-2624P4356-8 14-16 20-21183、有5个批处理作业1、2、3、4、5，分别在0、1、3、5、6时刻到达计算中心。假设它们的预计的运行时间是3、5、2、3、2，且在执行过程中不进行I/O处理和系统调用。它们的优先级分别为5、3、1、2、6（6为最高优先级，1为最低优先级）对于下面的四种调度算法，请写出每个进程的结束时间、周转时间和所有作业的平均周转时间。忽略进程转换所产生的系统开销，且后三种调度算法为非剥夺的调度算法。（1）时间片轮转调度算法，时间片长度为2；（2）优先级调度算法；（3）FCFS算法；（4）SJF算法。作业到达时间运行时间优先级开始时间结束时间周转时间平均10350336.2215338733211214114532912756267934、有5个批处理作业A、B、C、D、E，几乎同时到达计算机系统，其估计运行时间分别为10、6、2、4、8分，优先级数分别为3、5、2、1、4，其中5为最高优先级。假设它们都是纯计算型作业，系统开销时间忽略不记。若系统采用非剥夺式使用CPU，对于以下调度算法，描述执行过程并计算平均周转时间：（1）优先级调度；（2）先来先服务（按A、B、C、D、E顺序）；（3）短作业优先。5、有两个作业A和B，分别在7:00和8:30到达系统，它们估计的计算时间分别是0.8小时和0.1小时，系统在9:00开始以响应比高者优先算法进行调度，请问在单道执行时这两道作业被选中的次序以及被选中时的响应比。(2+0.8)/0.8=3.5(0.5+0.1)/0.1=6 9:00 B9:06 A (2.1+0.8)/0.8=3.6256、设有某系统有5个作业J1、J2、J3、J4、J5进入系统的时间、计算时间如下表所示。若作业在处理机上按单道方式运行，且作业按响应比高者优先调度算法。试写出作业的执行顺序，计算响应比、作业的周转时间和平均周转时间。作业进入系统时间计算时间开始时间结束时间周转时间平均周转时间J110:0642分10:0610:4842J210:1930分10:4811:1859J310:3024分11:3011:5484J410:3624分11:5412:18102J510:4212分11:1811:304810:48 J2 (29+30)/30=1.97J3 (18+24)/24=1.75J4 (12+24)/24=1.50J5 (6+12)/12=1.50 11:18J3 (48+24)/24=3J4 (42+24)/24=2.75J5 (36+12)/12=411:30J3 (60+24)/24=3.5J4 (54+24)/24=3.2511:54J4 1、在请求页式系统中，一程序的页面走向为2、3、4、5、2、3、6、2、3、4、5、6，设分配给该程序的存储块为m。试计算m=3和m=4时，FIFO和LRU两种替换算法的缺页中断次数，并对结果进行分析说明。答：FIFO算法：M=3时：页面踪迹234523623456FIFO算法222555666663332222244444333335置换标记M=4时：页面踪迹234523623456FIFO算法222222666655333333222264444443333555555444置换标记M=3时，缺页9次，M=4时，缺页10次。这说明FIFO算法出现了Belady异常现象。LRU算法：M=3时：页面踪迹234523623456LRU算法222555666444333222222264443333355置换标记M=4时：页面踪迹234523623456LRU算法222222222226333333333334444666655555555444置换标记M=3时，缺页10次，M=4时，缺页8次。2、在一个请求页式存储管理系统中，进程P的地址空间共有5页组成，访问页面序列为：3、2、1、0、3、2、4、3、2、1、0、4，试用FIFO置换算法和LRU置换算法，计算当分配给该进程的页框数分别为3和4时，访问过程中发生的缺页次数和缺页率，比较所得的结果，分析原因。答：FIFO算法：M=3时：页面踪迹321032432104FIFO算法333000444444222333331111112222200置换标记M=4时：页面踪迹321032432104FIFO算法333333444400222222333341111112222000000111置换标记M=3时，缺页9次，缺页率为75%；M=4时，缺页10次，缺页率为83.3%。这说明FIFO算法出现了Belady异常现象。LRU算法：M=3时：页面踪迹321032432104LRU算法333000444111222333333001112222224置换标记M=4时：页面踪迹321032432104LRU算法333333333334222222222221111444400000000111置换标记M=3时，缺页10次，缺页率为83.3%；M=4时，缺页8次，缺页率为66.7%。3、在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115、228、120、88、446、102、321、432、260、167。若该作业的第0页已经装入内存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题。（1）按FIFO调度算法将产生多少次缺页中断？缺页中断率为多少？（2）按LRU调度算法将产生多少次缺页中断？缺页中断率为多少？3.11答：定义数组buf0、buf1；bufempty0，bufempty1是PA的私有信号量；buffull0、buffull1是PB的私有信号量。初始时：bufempty0=bufempty1=n,(n为缓冲区队列的缓冲区个数)buffull0=buffull1=0send(i,m)beginlocal xP(bufemptyi)按FIFO方式选择一个空缓冲区bufi(x)bufi(x)=mbufi(x)置满标记V(buffulli)endreceive(i,m)beginlocal xP(buffulli)按FIFO方式选择一个装满数据的缓冲区bufi(x)m=bufi(x)bufi(x)置空标记V(bufemptyi)endPA调用send(0,m)和receive(1,m)PB调用send(1,m)和receive(0,m)练习2：有3个并发进程in, outA和outB共享一个缓冲区buf(容量为1)。规定：进程in负责将读入数据放到buf中。进程outA仅当在buf中有数据且数据为奇数时，outA才可从buf取数据打印,并使buf为空；进程outB仅当在buf中有数据且数据为偶数时，outB才可从buf取数据打印,并使buf为空；试用P，V操作实现三个进程可正确执行的并发程序。提示：这是一个同步问题，可以设3个私用信号量。答：根据题意，设三个同步信号量：SR是进程in的私用信号量，初值为1，表示开始时进程in可向缓冲区buf中送一整数；SW1是进程outA的私用信号量，初值为0，表示开始时缓冲区buf中无奇数可供进程outA取；SW2是进程outB的私用信号量，初值为0，表示开始时缓冲区buf中无偶数可供进程outA取。in()beginlocal x从输入设备上读一整数到xP(SR)buf=xif(buf=奇数)thenV(SW1)elseV(SW2)fiendoutA()beginlocal yP(SW1)y=bufV(SR)打印y中的数endoutB()beginlocal zP(SW2)z=bufV(SR)打印z中的数end练习3：桌上有一只盘子，只能容纳一个水果，每次只能放入或取出一个水果。现在有许多苹果和橘子。一家四口各行其职：父亲负责取苹果，然后将苹果放入盘中，并重复这两个动作；母亲负责取橘子，然后将橘子放入盘中，并重复这两个动作；一个儿子负责从盘中取橘子，然后吃掉橘子，并重复这两个动作；一个女儿负责从盘中取苹果，然后吃掉苹果。请用P，V操作实现父亲，母亲，儿子和女儿之间同步与互斥关系。答：根据题意，设三个同步信号量：sp是父亲进程（father）和母亲进程（mother）的私用信号量，表示盘子里可以放置的水果数量，初值为1；sg1是儿子进程（son）的私用信号量，表示盘子里橘子的数量，初值为0；sg2是女儿进程（daughter）的私用信号量，表示盘子里苹果的数量，初值为0。father()beginrepeat取一个苹果P(sp)把苹果放进盘子V(sg2)until 进程结束endmother()beginrepeat取一个橘子P(sp)把橘子放进盘子V(sg1)until 进程结束endson()beginrepeatP(sg1)从盘子里取橘子V(sp)吃橘子until 进程结束enddaughter()beginrepeatP(sg2)从盘子里取苹果V(sp)吃苹果until 进程结束end3.14答：（1）设信号量c0-c5，初始值均为1，分别表示i号筷子被拿（i=0,1,2,3,4）。send(i)：第i个哲学家要吃饭beginP(ci);P(ci+1 mod 5);eat;V(ci+1 mod 5);V(ci);end该过程能保证两邻座不同时吃饭，但会出现5个哲学家一人拿一支筷子，谁也吃不上饭的死锁情况。（2）解决的思路如下：让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。这样，任何一个哲学家拿到一支筷子以后，就已经阻止了他邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人会饿死。send(i)：beginif i mod 2=0thenP(ci);P(ci+1 mod 5);eat;V(ci);V(ci+1 mod 5);elseP(ci+1 mod 5); P(ci);eat;V(ci+1 mod 5);V(ci);end进程A1,A2,An通过一个缓冲区向进程B1,B2,Bm不断地发送消息。发送和接收工作遵循如下规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度；（2）对每一个消息，B1,B2,Bm都须各接收一次，读入各自的数据区；（3）缓冲区满时，发送进程等待；没有可读的消息时，接收进程等待。试用P,V操作组织正确的发送和接收工作。（说明信号量的意义）分析：本题是生产者-消费者问题的一个变形。在生产者-消费者问题中，生产者和消费者公用一组缓冲区，每一个缓冲区只需写一次、读一次；而这个问题中，每一个缓冲区只写一次，但需读m次。在解题的过程中，可以把一组缓冲区看做m组缓冲区。这样一来，每一个生产者需要同时写m个缓冲区组中相应的m个缓冲区，而每一个消费者只需读自己对应的那组缓冲区中对应的单元。生产者须在m个缓冲区都为空时方可写入。这样，就可以用m组信号量（avail,full）来实现这一流程。设公用信号量mutex保证生产者进程和消费者进程之间的互斥，设信号量avail1m为生产者进程的私用信号量，信号量full1m为消费者进程的私用信号量。信号量mutex表示可用有界缓冲区的个数，初值为1；信号量availi(1im)表示有界缓冲区组中的第i个缓冲区的空单元数，初值为m；信号量fulli(1im)表示有界缓冲区中的第i个缓冲区的非空单元数，初值为0。send(m):beginlocal ii1;repeatP(availi);until i=mP(mutex);把数据m送入缓冲区中某个单元;i1;repeatV(fulli);until i=mV(mutex);endreceive(m,i):beginP(fulli);P(mutex);取出缓冲区中某个单元的数据mV(availi);V(mutex);end练习1：假定系统有3个并发进程Read，Process，Print，他们共享缓冲区B1和B2。进程Read负责从输入设备读信息，每读一条记录，就把他放入缓冲区B1；进程Process从缓冲区B1取出记录，加工后存入缓冲区B2；进程Print则将B2中的记录打印输出。缓冲区B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出来的记录与读入记录的个数和次序完全一样，请使用P,V操作，写出他们的并发程序。本题中，三进程之间存在同步的关系。设4个私用信号量SR、SP1、SP2、ST。SR是进程Read的私用信号量，表示B1缓冲区中空缓冲单元的个数，初值为1；SP1和SP2是进程Process的私用信号量，SP1表示B1缓冲区中满缓冲单元的个数，初值为0，SP2表示B2缓冲区中空缓冲单元的个数，初值为1；ST是进程Print的私用信号量，表示B2缓冲区中满缓冲单元的个数，初值为0。Read():beginlocal xrepeat接收来自输入设备上的一个记录x接收的一个记录P(SR)B1xV(SP1)until 进程结束endProcess():beginlocal yrepeatP(SP1)y=B1V(SR)加工yP(SP2)B2=yV(ST)until 进程结束endPrint():beginlocal zrepeatP(ST)z=B2V(SP2)打印zuntil 进程结束end练习2：有3个并发进程in, outA和outB共享一个缓冲区buf(容量为1)。规定：进程in负责将读入数据放到buf中。进程outA仅当在buf中有数据且数据为奇数时，outA才可从buf取数据打印,并使buf为空；进程outB仅当在buf中有数据且数据为偶数时，outB才可从buf取数据打印,并使buf为空；试用P，V操作实现三个进程可正确执行的并发程序。提示：这是一个同步问题，可以设3个私用信号量。练习3：桌上有一只盘子，只能容纳一个水果，每次只能放入或取出一个水果。现在有许多苹果和橘子。一家四口各行其职：父亲负责取苹果，然后将苹果放入盘中，并重复这两个动作；母亲负责取橘子，然后将橘子放入盘中，并重复这两个动作；一个儿子负责从盘中取橘子，然后吃掉橘子，并重复这两个动作；一个女儿负责从盘中取苹果，然后吃掉苹果。请用P，V操作实现父亲，母亲，儿子和女儿之间同步与互斥关系。8.5答：设7个关键字为zhl,ouy,lwj,yks,lxz,suy,hls。h(n)=(676*l1+26*l2+l3) mod 11（1）线性散列 hi(k)=(h1(k)+2*i) mod 11h(zhl)=(676*26+26*8+12) mod 11=9h(ouy)=(676*15