操作系统作业题（含答案）作业一：作业管理1、有三道程序A、B、C在一个系统中运行，该系统有输入、输出设备各1台。三道程序A、B、C构成如下：A:输入32秒，计算8秒，输出5秒B:输入21秒，计算14秒，输出35秒C:输入12秒，计算32秒，输出15秒问：（1）三道程序顺序执行的总时间是多少？（2）充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间（不计系统开销）？并给出相应的示意图。作业一解答过程：1、（1）三道程序顺序执行的总时间是：32+8+5+21+14+35+12+32+15=174秒。（2）充分发挥各设备的效能，并行执行上述三道程序，最短需90秒（按BCA顺序执行），示意图如下：输入_计算—II一输出输入计算.输出输入计算—输出■iiI6789时间（秒）注：按ABC执行需1仃s按ACB执行需126s,按BAC执行需112s,按BCA执行需90s,按CAB执行114s,按CBA执行需99s作业二：进程管理1、有以下5条语句，请画出这5条语句的前趋图。（PPT第3章）S1y=x+1R(x)W(y)S2c=f-wR(f,w)W(c)S3d=r-yR(r,y)W(d)S4x=a+bR(a,b)W(x)S5r=c+yR(c,y)W(r)2、设有k个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用P，V操作写出有关互斥算法。（1）一次只允许一个进程进入临界区；（2）一次允许m（m
V（s）信号量s的变化范围为［-（k-1）,…,-1,0,1］。其中，s=1表示有1个空闲且可用的临界资源，且没有进程进入类名为s的临界区；s=0表示有1个进程在临界区中（该临界资源已被某进程占用），但无等待使用该临界资源的进程；s=-n（1V（s）信号量s的变化范围为[-（k-m）,…,-1,0,1,…,m]。其中，s=m表示有m个空闲且可用的临界资源，且没有进程进入类名为s的临界区；s=j（1
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。2、某超市市场科容纳100人同时购物，入口处备有篮子，每个购物者可取1只篮子入内购物，出口处结账并归还篮子（出、入口仅容1人通过）。请试用P，V操作及信号量写出如下情况的购物同步算法：（1）1个出入口，且一次只允许1人通过；（2）1个入口，n个出口（n》1且为整数）。3、设有无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息。试问：（1）两个进程间的制约关系；用P,V操作写出两个进程的同步算法,并给出信号量的初值；指出信号量的值的变化范围及取值的含义。作业三解答过程:1、(1)何时会发生死锁?(2)请提出一种可预防死锁发生的简单方法设4个路口为4个资源，其信号量分别设为S1，S2,S3和S4,初值均为1,代表资源空闲可用，下面用P，V操作预防死锁问题：方向①进方向②进方向③进方向④进程：程：程：程：P（S1,S2）<通过S1、S2路口>P（S2,S4）<通过S2、S4路口>P（S3,S4）<通过S3、S4路口>P（S1,S3）<通过S1、S3路口>V（S1,S2）V（S2,S4）V（S3,S4）V（S1,S3）信号量S1,S2,S3和S4的变化范围均为[-m,…,-1,0,1]（m为正整数）。2、（1）1个出入口，且一次只允许1人通过：设超市容量信号量为S,初值为100;购物进程为Pi，购物信号量为mutex，初值为1。购物进程Pi同步描述：P（苛、、P（mutex）\＜进入超市并丿取1只篮子＞/一―（mutex）＜选购商品＞P（mutex）＜结账并归还篮子＞（mutex）V（S）信号量S的变化范围为[-m,…,-1,0,1,…,100]（m为正整数）；信号量mutex的变化范围为[-99，…,-1,0,1]。（2）1个入口，n个出口（n＞1且为整数）设购物进程为Pi,;超市容量信号量为S,初值为100;入口互斥信号量为mutexl，初值为1;出口互斥信号量为mutex2，初值为1。购物进程Pi同步描述：P（S）fP（mutexl）\＜进入超市并J取1只篮子＞/（mutex1）＜选购商品＞P（mutex2）＜结账并归还篮子＞（mutex2）V（S）信号量S的变化范围为［-m,…,-1,0,1,…,100］（m为正整数）；信号量mutex1和mutex2的变化范围均为［-99,…,-1,0,1］。3、（1）两个进程间的制约关系：乙进程不能先于甲进程执行，而甲进程不受乙进程约束。（2）设置1个信号量S,S表示甲进程写满的缓冲区的个数，S初值为0,表示缓冲区为空，则甲、乙两进程的同步算法描述为甲进程：乙进程:i=0j=0i=i+1-j=j+1＜写入第i个P（S）缓冲区＞＜读出第jV（S）个缓冲区＞（3）信号量S的变化范围为［-1,+x］中的整数，当S=-1时表示缓冲区从未被写入信息或缓冲区信息被乙进程读空，且乙进程要求进一步读缓冲区中的信息，即乙进程超前甲进程欲读取缓冲区的信息而受阻作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？（1）先来先服务（2）轮转法（3）短作业优先（4）优先级高者优先（5）长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。下表给出了3种简单的作业调度算法：调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先最高相应比优先（1）请指出每种算法主要是体现了上述哪种原则。（在对应的行列上打上记号V）（2）如果在实际系统中只采用上述3种简单算法的任一种，都只能体现其中一种原则而其它原则得不到反映。为此，给出下列能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R（优先数）=（作业等待时间）2+1/（作业要求运行时间）请问这种算法反映了上述原则中的哪些原则？并简述理由。3、假设有4道作业，它们的提交时刻及运行时间由下表给出：作业号提交时刻/小时执行时间/小时110.002210.201310.400.5410.500.3计算在单道程序环境下，米用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。作业四解答过程:1、适用于作业调度用的算法：(1)(3)(4)(5),适用于进程调度用的算法：(1)(2)(4)2、(1)调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先最高相应比优先v该算法体现了先来先服务原则和最短作业优先原则。理由如下：体现先来先服务原则：假若两作业运行时间相同，但到达时间不同，早到达的作业等待时间长，根据公式计算，它的优先数大，则优先调度。体现最短作业优先原则：假若两道作业同时到达，但运行时间不等，根据公式计算，运行时间短的作业其优先数高，因而优先调度。3、(1)先来先服务(FCFS)调度：调度顺序为作业号到达时间结束时间周转时间带权周转时间110.0012.0021.00210.2013.002.82.80310.4013.503.16.20410.5013.803.311.00平均周转时间T=(2+2.8+3.1+3.3)/4=2.8小时平均带权周转时间W=(1+2.8+6.2+11)/4=5.25小时(2)最短作业优先(SJF)调度：调度顺序为1f31。作业号到达时间结束时间周转时间带权周转时间110.0012.0021410.5012.301.806310.4012.802.404.8210.2013.803.603.6平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时最高响应比优先(HRN)调度：调度顺序为1宀4t3宀2。响应比=（作业执行时间+作业等待时间”作业执行时间从下表可见，在作业1完成时刻（12.00）,作业2、3、4的响应比最高的为4;在作业4完成时刻（12.30），作业2、3的响应比最高的为3。作业等待执行响应号时间时间比21.8012.831.600.54.241.500.3冋22.113.131.90.5S3作业号到达时间结束时间周转时间带权周转时间110.0012.0021410.5012.301.806310.4012.802.404.8210.2013.803.603.6平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时作业五：存储管理1、假定某页式虚拟系统中，页面大小为100个单元，某作业占有实页面数为M=3，它的访问地址（走向）序列为75,175，66，267，32,102，333，166，22，255，256（数字为虚存的逻辑地址）。（1）请指出这些单元对应的页面访问顺序序列；（2）按先来先服务（FIFO）页面淘汰算法求出缺页率f,并画出图表表示之；（3）按最近最久未使用（LRU）页面置换算法求出缺页率f，并画出图表表示之。2、有系统其主存容量为1024K（字节），有6个作业同时到达，各作业要求主存量和运行时间如下表所示。假定系统初启时，将主存1024K按作业的编号顺序分给各道作业，并假定是多CPU下，分配到主存的作业都可以立即运行。请问：（1）1秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（2）2秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（3）在（2）后，此时有一个作业7要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情作业需主存运行时编号量（K）间（s）1200221201310034501580363202作业五解答过程:1、(1)访问序列为0,1,0,2,0,1,3,1,0,2,2。(2)FIFO:页面0102013102210112223300020011122333300011222缺页XXVXVVXVXVV缺页率f=5/11=45.45%。(3)LRU:页面0102013102210102013102220102013100311200311缺页XXVXVVXVVXV缺页率f=5/11=45.45%。2、（1）1秒后，主存空白区按首次适应和最佳适应算法的链接方式：首次适应算法：最佳适应算法：120—50—15420—320—474最佳适应算法：50—120—1542秒后，主存空白区的链接方式：首次适应算法：320—50—474最佳适应算法：50—320—4742秒后，作业7要求进入主存：首次适应算法：290—50—474作业六：文件管理1、在UNIX系统中，为使文件的索引表较小又能允许组织大文件，采用直接索引与多次间接索引（多级索引）方式，给出一个文件的所有磁盘的块号，如下图。假设每个磁盘块大小为1024字节，并且每个间接块容纳256个块号，试问：（1）如某进程要读取某文件的字节偏移量为9000处的数据，应如何找到它所在的磁盘块及块内位移量？（2）如想要存取350000处，又将如何？直接04096直接1228直接245423直接3401/直接4702直接511111直接610直101接7-9T0^33-/一次一次/数据直接8367直接990/间接428间接9156间接8242、磁道（0-90道）的存取正在处理第55道的服务请求，对于磁盘访问序列（磁道号）：22、77、35、90、40、83、66,试问对以下的磁盘I/O请求调度算法而言，满足以上请求序列，磁头将如何移动，移动距离为多少？若每移动一个柱面需3ms，计算总共花费的寻道时间。（1）先来先服务算法（FCFS）（2）最短查找时间优先调度（SSTF）（3）扫描调度（SCAN）（电梯调度算法）（4）循环扫描（C-SCAN）算法3、如果磁道范围0-99,刚结束第50道的服务请求，对于磁道序列70，25，40，85，90，55,分别按第2题（1）-（4）四种磁道扫描方法，磁头将如何移动？作业六解答过程:1、（1）根据9000/1024=8.8,故该字节在文件索引8（从0开始计）直接块中，于是可从表目项中读出内容为367,即该字节在磁盘块号为367的盘块中；再根据9000mod1024=808,查表在367号磁盘块的808字节即为文件的900
0字
个人自传范文3000字为中华之崛起而读书的故事100字新时代好少年事迹1500字绑架的故事5000字个人自传范文2000字
节。（2）350000/1024=341.8,则该字节在文件的逻辑块号为341的块中，故可知它必在二次间接寻址中（因为直接+1次间接可寻256+10=266块）。根据（341-266）/256=75/256=0.29（整数部分为0），可知其在二次间接块中0的表目上，又因为75mod256=75,可知在一次间接75表目处，从题表中可分别读出表目项内容为331和3333,可知在磁盘块3333中。由350000mod1024=816,得出文件的350000字节是3333磁盘块的816字节。2、（1）先来先服务算法（FCFS）:访问序列55f22f77f35f90^40^83^66总移动柱面距离为：33+55+42+55+50+43+17=295,总寻道时间为3ms*295=885ms。（2）最短查找时间优先调度（SSTF）:根据各个I/O请求的不同，总是为接近当前磁头位置的请求提供优先服务，也就是先执行查找时间最小的那个请求。由于查找时间正比于两个请求的柱面差值，所以磁头移动总是移到距当前最近的柱面上去。很明显，它比FCFS改善了磁盘的服务。从本质上讲，它是SJF短作业优先调度的形式。同样，可能导致某些请求长期得不到服务（被饿死）（当不断有I/O请求时）。访问序列55—66—77宀83—90宀40~35—22总移动柱面距离为：11+11+6+7+50+5+13=103，总寻道时间为3ms*103=309ms。（3）扫描调度（SCAN）:由于I/O请求具有动态性质，所以可以采取扫描法。磁头从磁盘的一端出发，向另一端移动，扫过所有柱面，遇到请求就服务。直到移到另一端后，移动方向反过来，继续做下面的服务。访问序列55—66—77—83—90—40—35—22总移动柱面距离为：11+11+6+7+50+5+13=103，总寻道时间为3ms*103=309ms。（4）循环扫描（C-SCAN）算法：它是SCAN扫描算法的变种，这是为了适应极大量存取请求而设计的。磁头臂总是从0号柱面至最大号柱面顺序扫描，到头后直接返回0号柱面重复进行，就像是循环至0号柱面一样（也可视为单向扫描）。在一个柱面上，磁头臂往往停留，待磁盘旋转一定圈数之后，再移向另一个柱面。为了在磁盘移动每一周时间内执行更多的存取，必须考虑旋转优化（考虑等待时间与传送时间）。访问序列55—66—77—83—90—0—22—35—40总移动柱面距离为：11+11+6+7+90+22+13+5=165,总寻道时间为3ms*165=495ms。
浙公网安备 33021202002483