操作系统复习试题.doc

1. 操作系统是系统软件中的一种，在进行系统安装时可以先安装其它软件，然后再装操作系统。答: 操作系统是系统软件中的一种，在进行系统安装时必须先安装其它软件，然后再装操作系统。2. 在虚拟存储系统中，操作系统为用户提供了巨大的存储空间。因此，用户地址空间的大小可以不受任何限制。答：在虚拟存储系统中，操作系统为用户提供了巨大的存储空间。但是，用户地址空间的大小依然不受任何限制。3. 在请求式分页系统中，增加内存帧一定可以降低缺页中断率。4.答：在请求式分页系统中，增加内存帧不一定可以降低缺页中断率。5. 若系统处于不安全状态，则一定发生了死锁。答：若系统处于不安全状态，则不一定发生了死锁。OPT页面替换算法是堆栈型算法？证明如下：因为LRU算法满足，n=Lt时，Bt(n)=Bt(n+1)n表示分配给程序的实页数，Bt(n)表示t时刻在n个实页中的虚页集合，Lt为t时刻不同虚页的页面数。由于在主存中保留的是最近使用过的页面。如果先给某一个程序分配n个主存页面，那么在t时刻，这n个主存页面都是最近使用过的页面。如果再给这个程序多分配一个主存页面，那么在t时刻，这n1个主存页面也都是最近使用过的页面。因此，在这n1个主存页面中必然包含了前面的n个主存页面。所以，opt算法是堆栈型算法。1. 读着优先、写者优先（代码）。读者优先如果有读者来时，无读者和写者，新读者可以读；如有写者等待，但有其他读者正在读，则新读者可以读；有写者写，新读者则等待Var wsem:semaphore; (initial value: 1)Writer： while(1) P(wsem); V(wsem); int readCount = 0;semaphore wsem = 1;semaphore mutex = 1;reader()： while(1) P(mutex); readCount = readCount+1; if (readCount = 1) P(wsem); V(mutex); P(mutex); readCount = readCount-1; if (readCount = 0) V(wsem); V(mutex); 写者优先如果有写者来时，无读者，新写者可以写；如有读者正在读，则新读者等待；有其他写者正在写，新写者则等待。int writeCount = 0;semaphore wsem,rsem = 1;semaphore mutexY = 1;writer()： while(1) P(mutexY); writeCount = writeCount+1; if (writeCount = 1) P(rsem); V(mutexY); P(wsem); V(wsem); P(mutexY); writeCount = writeCount-1; if (writeCount = 0) V(rsem); V(mutex); int readCount = 0;semaphore wsem,rsem = 1;semaphore mutexX,mutex = 1;reader()： while(1) P(mutex); P(rsem); P(mutexX); readCount = readCount+1; if (readCount = 1) P(wsem); V(mutexX); V(rsem); V(mutex); P(mutexX); readCount = readCount-1; if (readCount = 0) V(wsem); V(mutexX); 变量wsem用来保证读者与写者之间的互斥，以及写者与写者之间的互斥；变量writeCount用来记录写者的数目；变量mutexY用来实现读者对于变量writeCount访问的互斥；变量readCount用来记录读者的数目；变量mutexX用来实现读者对于变量readCount访问的互斥;mutex用来实现rsem上不要有长的排队等待。2. 资源分配图的化简。可以通过对资源分配图的约简，来判断系统是否处于死锁状态资源分配图中的约简方法如下：(1)寻找一个非孤立且没有请求边的进程结点pi,若无算法结束；(2)去除所有pi的分配边使pi成为一个孤立结点；(3)寻找所有请求边均可满足的进程pj,将pj的请求边全部改为分配边；(4)转步骤(1) 若算法结束时，所有结点均为孤点，则称资源分配图是可以完全约简的，否则称为不可完全约简的文献已经证明，系统处于死锁状态的充分必要条件是资源分配图不可完全约简这一结论称为死锁定理定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简 对于问题1，假设进程p3申请资源类r2中的一个实例，由于没有空闲的资源实例，将增加一条申请边(p3,r2)，形成图 52. 此时, 出现了两个环路: p1 r1 p2 r3 p3 r2 p1 和p2 r3 p3 r2 p2. 进一步分析可以验证，此时系统已经发生死锁，且进程p1、p2和p3都参与了死锁. 对于问题2，此图中亦有一个环路: p1r2p4r1p1 然而并不存在死锁. 注意观察p2可能会释放资源类r1中的一个资源实例, 该资源实例可分配给进程p3, 从而使环路断开. 综合上述分析可以看出, 如果资源分配图中不存在环路, 则系统中不存在死锁; 反之, 如果资源分配图中存在环路, 则系统中可能存在死锁, 也可能不存在死锁.3. 扔球问题。（1）有一个充分大的池子，两个人分别向池中扔球，甲扔红球，乙扔蓝球，一次扔一个，开始时池中有红、蓝球各一个，要求池中球满足条件：1红球数蓝球数2，用P V操作描述两个进程信号量初值：r=1；b=0扔红 扔蓝 P(r) P(b)扔一个红 扔一个蓝V(b) V(r) V(r)（2）一个充分大的池子，甲乙丙三人扔球，甲扔红，乙扔蓝，丙扔绿。开始时池子中又红绿蓝球各一个。要求：池中球满足要求：1=红/蓝=2 ，且蓝=绿=红+蓝信号量初值：r，b1，g=1；b2=0 扔红 扔蓝 扔绿P(r) P(b1) P(g)扔一个红 P(b2) 扔一个绿V(b1) 扔一个蓝 V(b2)V(g) V(r) V(r) V(g)4. 最佳页面尺寸算法例：在一个分页系统中，设计算机的内存大小为M，作业平均尺寸为J，一个页表项占x个存储单位，问最佳页面尺寸P是多少？每个进程需要的页数：J/P占用 xJ/P 个存储单位每个进程的内部碎片平均为： P/2由页表和内部碎片带来的总开销： xJ/P+P/2=M对P求导，令其等于0，得到方程：-x(J/P2)+1/2=0由此得到最佳页面尺寸公式 P = 2xJ(1/2)5. 安全性检测算法（已知流程图，写代码）。数据结构： Available: array1.mof integer; /系统可用资源 Claim: array1.n,1.mof integer; /进程最大需求 Allocation: array1.n,1.mof integer; /当前分配 Need: array1.n,1.mof integer; /尚需资源 Request: array1.n,1.mof integer; /当前请求int Workm; 工作变量, 记录可用资源.int Finishn; 工作变量, 记录进程是否可进行完.1. Work = Available；Finish = false；2. 寻找满足如下条件的i: (1) Finishi=false；(2) NeediWorki； 如果不存在, 则转步骤4；3. Work = Work + Allocationi；Finishi = true； 转步骤24. 如果对于所有i, Finishi = true, 则系统处于安全状态, 否则处于不安全状态.FWork:=Available;Finish:=false; 有满足条件的j:Finishj=falseNeedjWorkFinishj=true;Work:=Work+AllocationjTj ,finishj=trueTF安全不安全6. 进程的状态及其转移。运行：进程当前处于运行状态。 就绪；进程已准备好运行。 阻塞；进程等待某些事件发生（如I/O操作）后才能运行。 创建：进程刚产生，但还未被操作系统提交到可运行进程池中。 消失：进程被操作系统从可运行进程池中释放。 带有挂起状态的进程状态图：(a) 带有一个挂起状态的进程转换图(b)