操系计网离数复试课件操作系统习题课

1西安电子科技大学计算机学院2习题讲解第一章～第六章第一章3ch1－3操作系统形成标志－多道程序系统的出现ch1－11客户机/服务器模型可以用于单机系统，同时它也适用于分布式系统。理解时注意以下几点：1）客户机、服务器是一个抽象的概念，并不一定要和实际的物理机器对应；2）把握其核心思想第一章下图展示的是一个客户机/服务器模型在这里内核的全部工作就是处理客户机和服务器间的通信，如果是单机则消息直接由本机操作系统内核传递，如果是分布式系统则消息需要通过网络在不同机器的操作系统内核间传递，但是无论采用何种方式，都是符合上述客户机/服务器模型的。4第一章下图是一个分布式系统中的客户机/服务器模型5第二章作业的执行顺序为1->2->4->3->1作业提交时间执行时间（分钟）开始时刻完成时刻周转时间（分钟）18：00608：0010：0512528：20358：208：553538：30259：009：255548：3558：559：0025平均周转时间T＝60分钟2406第二章7ch2－10本题不严密，两处有歧义：“作业在时刻0以1,2,3,4,5的顺序到达”：时刻是一个瞬时概念，如果作业都是在这个时刻到达则不应当有先后顺序；优先数代表的优先级高低未交代清楚，因为有的机器可能是高优先数代表高优先级，但有的机器却相反。为此对这两处作如下规定：改为“作业从时刻0开始在很短的时间（可以忽略）内以1,2,3,4,5的顺序到达”；规定低优先数代表高优先级第二章8FCFS：作业的执行顺序为1->2->3->4->5作业提交时间执行时间开始时刻完成时刻周转时间带权周转时间1010010101201101111113021113136.5401131414145051419193.8平均周转时间T＝13.4，平均带权周转时间＝7.266736.3第二章9SJF：作业的执行顺序为1->2->4->3->5作业提交时间执行时间开始时刻完成时刻周转时间带权周转时间1010010101201101111113021214147401111212125051419193.8平均周转时间T＝13.2，平均带权周转时间＝6.966634.8第二章10非剥夺式优先级算法：作业的执行顺序为1->2->5->3->4作业提交时间执行时间开始时刻完成时刻周转时间带权周转时间1010010101201101111113021618189401181919195051116163.2平均周转时间T＝14.8，平均带权周转时间＝8.647443.2第二章11讨论作业的平均周转时间和平均带权周转时间是衡量作业调度算法的两个重要指标，通常，使用前者来衡量不同调度算法对同一作业流的调度性能；使用后者来衡量同一调度算法对不同作业流的调度性能。作业的平均周转时间和平均带权周转时间越短越好。注：带权周转时间＝周转时间/执行时间；带权周转时间即为周转系数，平均带权周转时间即为平均周转系数。第三章12ch3-24(教材73,74,75,77画线部分）初值为1，范围1,0,-1,…,-(n-1)初值为m，范围m,m-1,…,1,0,…,-(n-m)第三章13ch3-26设置信号量mutex1,mutex2，初值为1，用于counti的互斥；tunnel初值为1；计数器count1，count2，初值为0。北方：P(mutex1);count1:=count1+1;if

count1=1

thenP(tunnel);V(mutex1);过隧道；P(mutex1);count1:=count1-1;if

count1=0

then

V(tunnel);V(mutex1);南方：P(mutex2);count2:=count2+1;if

count2=1

thenP(tunnel);V(mutex2);过隧道；P(mutex2);count2:=count2-1;if

count2=0

then

V(tunnel);V(mutex2);第三章14ch3-27（1）设：私有信号量C表示货位的容量，初值为1（也可不用，直接用S就可以）；公有信号量S用于货位的互斥操作，初值为

1；私有信号量Icebox表示冰箱，初值为0；私有信号量Car表示汽车，初值为0A:While(true){B:While(true){甲:While(true){乙While(true){P(C)；P(S)；P(C)；P(S)；P(Car)；P(S)；P(Icebox)；P(S)；放汽车；放冰箱；取汽车；取冰箱；V(S);V(Car);}V(S);V(Icebox);}V(S);V(C);}V(S);V(C);}第三章15ch3-27（2）设：私有信号量C表示货位的容量，初值为N，其它同前。第三章16ch3－29可看作四对生产者／消费者问题。mutexi(i＝0，1，2，3)控制四个信箱的互斥使用，初值均为1；emptyi(i＝0，1，2，3)表示各信箱中空单元的个数，初值分别为1，3，2，2；fulli(i＝0，1，2，3)表示各箱中信息个数，初值分别为2，0，0，0。第三章17P0：BeginL1：P(full0)；P(mutex0)；从M0中取一个消息;V(mutex0)；V(empty0)；加工消息；P(emptyl);P(mutex1)；送消息进入M1；V(mutex1)；V(fulll)；GotoL1;End；P1：BeginL2：P(full1)；P(mutex1)；从M1中取一个消息;V(mutex1)；V(empty1)；加工消息；P(empty2);P(mutex2)；送消息进入M2；V(mutex2)；V(full2)；GotoL2;End；第三章18P2：BeginL3：P(full2)；P(mutex2)；从M2中取一个消息;V(mutex2)；V(empty2)；加工消息；P(empty3);P(mutex3)；送消息进入M3；V(mutex3)；V(full3)；GotoL3;End；P3：BeginL4：P(full3)；P(mutex3)；从M3中取一个消息;V(mutex3)；V(empty3)；加工消息；P(empty0);P(mutex0)；送消息进入M0；V(mutex0)；V(full0)；GotoL4;End；第三章补充19桌上有一空盘，允许放一个水果。爸爸可向盘中放苹果和桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用PV原语实现爸爸、儿子、女儿三个并发进程的同步。桌子上有一只盘子，最多可容纳两个水果，每次只能放人或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘于中放桔子(orange)，两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。请用PV操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。第四章20ch4－9不安全，因为找不到一个安全序列。不可以，否则会死锁。ch4－10死锁。死锁，因为图中最右边的资源无进程生产。第四章ch4－11T121T2T3T4S1•

R1

•S2R2

•

•第四章ch4－11T1T2T4S1•

R1

•S2R2

•

•22第四章ch4－11T2T4•

R1

•S2R2

•

•23T2T4•

R1

•S2第四章ch4－11死锁24第四章25ch4－12判断是否为安全状态，关键在于能否找到一个安全序列。进程剩余需求量系统剩余资源P13,4,72,3,3P21,3,4P30,0,6P42,2,1P51,1,0至少可以找到一个安全序列<P4P2P3P5Pl>，答案不唯一。不能，因为系统剩余资源不够。可以分配。因为至少可以找到一个安全序列<P4P5P1P2P3>。不能分配，因为找不到一个安全序列。第四章26ch4－13为永久性资源（a）会死锁（b)不会死锁第四章27ch4－9不安全，因为找不到一个安全序列。不可以，否则会死锁。ch4－10死锁。死锁，因为图中最右边的资源无进程生产。第四章ch4－11T128T2T3T4S1•

R1

•S2R2

•

•第四章ch4－11T1T2T4S1•

R1

•S2R2

•

•29第四章ch4－11T2T4•

R1

•S2R2

•

•30T2T4•

R1

•S2第四章ch4－11死锁31第四章32ch4－12判断是否为安全状态，关键在于能否找到一个安全序列。进程剩余需求量系统剩余资源P13,4,72,3,3P21,3,4P30,0,6P42,2,1P51,1,0至少可以找到一个安全序列<P4P2P3P5Pl>，答案不唯一。不能，因为系统剩余资源不够。可以分配。因为至少可以找到一个安全序列<P4P5P1P2P3>。不能分配，因为找不到一个安全序列。第四章33ch4－13为永久性资源（a）会死锁（b)不会死锁第五章3415（1）当M＝3时，采用LRU替换算法：时刻123456789101112P432143543215M4+3+2+1+4+3+5+432+1+5+432143543214-3-2-1-4-3-5-4-3-2-F++++++++++算出缺页中断次数F=10，缺页率f

=10／12=83％。第五章3515（2）当M＝4时，采用LRU替换算法：时刻123456789101112P432143543215M4+3+2+1+435+432+1+5+4321435432143214354324-3-2-1-1-1-5-4-3-F++++++++由表可以算出缺页中断次数F=8，而缺页率：8／12=67%。第五章3615（3）如果采用FIFO替换算法，当M＝3时时刻123456789101112P432143543215M4+3+2+1+4+3+5+552+1+1432143335224-3-2-1-4-4-4-3-5-5-F+++++++++由表可以算出缺页中断次数F=9，而缺页率：9／12=75%。第五章3715（4）采用FIFO替换算法，当M＝4时时刻123456789101112P432143543215M4+3+2+1+115+4+3+2+1+5+4322215432143332154324-4-4-3-2-1-5-4-3-F++++++++++由表可以算出缺页中断次数F=10，而缺页率：10／12=83%。第五章3815（5）采用OPT淘汰算法，当M＝3时时刻123456789101112P432143543215M4+3+2+-1+-1-1-5+-55555-43333333-2+-1+-1444444-4444F+++++++由表可以算出缺页中断次数F=7，而缺页率：7／12=58%。第五章3915（6）采用OPT淘汰算法，当M＝4时时刻123456789101112P432143543215M4+3+2+1+-1-1-5+-55555-432222222-1+-14333333-33344444-4444F++++++由表可以算出缺页中断次数F=6，而缺页率：6／12=50%。第五章4015通过以上缺页次数和缺页率的分析计算，可以看

出，对于LRU、OPT算法，增加物理块数，不会增加

缺页次数。对于FIFO算法，增加物理块数，不一定能减少缺页次数。但这里，OPT算法仅是一种理论算法，因为它根据未来页面走向决定淘汰哪一页，而在实际执行时无法准确的知道未来行为。所以，该算法不作为实用算法，仅用于算法的比较和评价。讨论：计算缺页次数和缺页率时，要注意初始时刻所有物理块为空。调入页面时，不需要页面替换，但是需要引起缺页中断。第五章4116(1)为了实现从逻辑地址到物理地址的变换，在系统中需要设置段表寄存器，存放段表起始地址和段表长度

STL。在进行地址变换时，系统将逻辑地址中的段号S与段表长度STL进行比较。若S≥STL，则表示段号太大，访问越界(段号越界)，产生越界中断。若未越界，则根据段表的起始地址和段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始位置和段长SL，再检查段内地址D是否超过该段的段长SL。若超过，即D≥SL，则同样发出越界中断信号(段内地址越界)；若未越界，则将该段的起始地址与段内地址D相加，即得要访问的内存物理地址。第五章4216(2)

[0,340]------------------219+340

=

559[1,10]-------------------3300+10

=

3310[2,500]-----------------段内地址越界（500>100），不合法[3,400]-----------------1237+400

=

1637第五章4316(3)存取主存中的一条指令或数据至少要访问2次主存。一次是访问段表，另一次是访问需要的指令或数据。讨论

在分段存储管理的地址变换过程中，要点是由段号查段表得段起始地址。然后与段内地址相加得物理地址。但要注意，段地址是二维地址，段号和段内地址都有可能越界。如因5＞4，所以[5，l00]越界(段号越界)第五章17(1)(2)操作系统作业1（60KB）空闲区A（60KB）作业2（40KB）空闲区B（20KB）作业3（30KB）空闲区C（26KB）0K20K80K140K180K200K230K255K操作系统空闲区A（120KB）作业2（40KB）空闲区B（76KB）0K20K140K180K255K44第五章17(3)首次适应算法操作系统空闲区A（120KB）作业2（40KB）空闲区B（76KB）0K20K140K180K255K0K20K90K140K180K45255K操作系统作业4（70KB）空闲区A（50KB）作业2（40KB）空闲区B（76KB）第五章17(3)最佳适应算法操作系统空闲区A（120KB）作业2（40KB）空闲区B（76KB）0K20K140K180K255K0K20K46140K180K250K255K操作系统空闲区A（120KB）作业2（40KB）作业4（70KB）空闲区B（6KB）第五章18（1）J2页面映像表47页号块号03142638第五章4818（2）页面大小为1024字节，逻辑地址2100页号为2（2100/1024

＝

2.05），对应块号为6，页内位移为52（1024×2＋52

＝

2100），所以物理地址为1024×6＋52＝6196。逻辑地址3100页号为3

（

3100/1024

＝

3.02

），对应块号为8，页内位移为28（1024×3＋28

＝

3100），所以物理地址为1024×8＋28＝8220。第五章18（2）2100转换过程如下图所示：S4页表控制寄存器页表起始地址 页表长度252逻辑地址2100页号 页内偏移量65203142638+S

虚页号实页号地址寄存器49第五章5019NRU：0号页（因为R＝0）FIFO：2号页（需回写，因为修改位M＝0）LRU：1号页第二次机会算法：0号页第五章5120（1）每一块为4k=4*1024=4096，所以9016/4096=2.2，在2号页中（页号从0开始），对应32号块。页内偏移量为9016-4096*2=824。根据页表映射关系，其物理地址为：32*4k+824=131896；（2）

12300属于第12300/4096=3.002,所以其页号为3，此时该页不在内存，引起缺页中断，待3号页面装入内存后（假设3号页面对应的内存块号为x，由内存页表得出块x

的物理地址为y），则逻辑地址12300

的物理地址为=y+12（12

是页内偏移量=12300-4096*3）第六章1(1)(2)(3)52第六章353第六章546、由于每个逻辑记录的大小与磁盘块大小相等，均为512字节，所以，从要存取的文件逻辑字节地址1569＝512x3+33可知，我们要访问是第四个磁盘块(逻辑记录号为3)的第33字节相对地址，即要访问第80号磁盘块第六章5512在UNIX操作系统中，一个文件应属于某个用户所有，

我们将这个用户称为该文件的文件主。一般情况下，文件主就是建立文件的用户。在系统中，使用用户标识符(uid)来记录文件主。UNIX将使用文件的用户分成三类，即文件主、同组用户和其他用户。同组用户是相互之间有某种关系的用户、如同一课题组的人，用户所在的用户组用组标识符(gid)来表示。其他用户一般是和文件主无关的用户，但他们也是系统中的用户。第六章5612每一类用户对文件的操作都有三种不同的存取权限，即读、写和执行。由于有三类用户，每类用户有三种存取权限，故每个文件都有9种存取权限。在系统内部，文件的存取权限用9位二进制数描述，文件主权限对应最高三位，同组用户权限对应中间三位，其他用户权限对应低三位。例如，111101001(也可以用八进制数表示，如0751)，表示文件主可以对该文件进行读、写、执行操作；同组用户可以对该文件进行读和执行操作；其他用户只能对该文件进行执行操作。第六章5712当系统用ls命令列目录时，文件权限以标准的符号形式表示。这种表示法使用9个字符，分为3组，每组3个字符。第一组表示文件主的权限，第二组表示同组用户的权限，第三组表示其他用户的权限。在每组的三个字符中，如果允许这类用户读，则第一个字符置为

“r”，如果允许进行写，则第二个字符置为“w”，如果允许执行，则第三个字符置为“x”。如果不允许某个权限，则相应的字符置为“-”。第六章5812由上述介绍可知，文件F的存取权限rwxr-x---表示文件主可以对F进行读、写及执行操作，同组用户可以对F进行读及执行操作，其他用户不能对F进行操作。因为另一用户与文件主的组标识符相同(gid均为1)，由此可知他们是同组用户，所以允许该用户执行文件F。第六章5916、能。如果允许使用任意长的名字，则可以模拟多级目录结构。例如，可用符号

“.”指明子目录的结束。这样，名字

h.lisp.F1指明F1是子目录lisp的文件，而

lisp是根目录h的文件。第六章6018空白文件目录是管理磁盘空间的一种方法，该方法将文件存储设备上的每个连续空闲区看作一个空白文件。系统为所有空白文件单独建立一个目录，每个空白文件在这个目录中占一个表目。表目的内容至少包括第一个空白块的地址(物