操作系统计算题.doc

计算题：一、 生产消费者问题为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值为。由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。P：i = 0;while (1) 生产产品; P(S1); P(mutex); 往Buffer i放产品; i = (i+1) % n; V(mutex); V(S2); ;Q： j = 0; while (1) P(S2); P(mutex); 从Bufferj取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品; ;二、 地址转换例1：若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址。页号 块号0 21 32 13 6解：本题中，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，页面大小为L，则： p=int(A/L)w=A mod L对于逻辑地址1011 p=int(1011/1024)=0 w=1011 mod 1024=1011查页表第0页在第二块，所以物理地址为3059。对于逻辑地址2148 p=int(2148/1024)=2 w=2148 mod 1024=100 查页表第2页在第1块，所以物理地址为1124。对于逻辑地址3000 p=int(3000/1024)=2 w=3000 mod 1024=928 查页表第2页在第1块, 所以物理地址为1796。对于逻辑地址4000 p=int(4000/1024)=3 w=4000mod 1024=928 查页表第3页在第6块, 所以物理地址为7072。对于逻辑地址5012 p=int(5012/1024)=4 w=5012mod1024=916因页号超过页表长度，该逻辑地址非法。例2：在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节,现有一逻辑地址为2F6AH,且第0, 1, 2页依次存放在物理块5, 10 ,11中,问相应的物理地址为多少?解:由题目所给给条件可知,本页式系统的逻辑地址结构为:逻辑地址2F6AH的二进制表示如下:由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中,用十六进制表示志号为B,所以物理地址为BF6AH.三、 求文件最大长度例：设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和盘块大小均为256字节，则可表示的单个文件的最大长度是多少？解答：本题的文件结构属混合索引分配方式。每个地址项大小为4字节，索引块和盘块大小为256字节，每个索引块中的项目数=256B/4B=64个。4个地址项为直接地址索引，对应的文件大小为4256B=1KB。2个地址项是一级间接地址索引，对应的文件大小是264256B=32KB，一个地址项是二级间接地址索引，对应的文件大小为16464256B=1024KB。所以单个文件的最大长度=1KB+32KB+1024KB=1057KB。四、 磁盘调度算法：1. 先来先服务FCFS 2. 最短寻道时间优先SSTF 3. SCAN算法4. 循环扫描(CSCAN)算法例：假设一个活动头磁盘有200道, 编号从0-199. 当前磁头正在143道上服务, 并且刚刚完成了125道的请求. 现有如下访盘请求序列(磁道号): 86, 147, 91, 177, 94, 150, 102, 175, 130 试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数). (1). 先来先服务(FCFS)磁盘调度算法. (2). 最短寻道时间优先(SSTF)磁盘调度算法.(3). 扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动.)答案：三、（1）86，147，91，177，94，150，102，175，130 （2）当前磁头在143道上： 147，150，130，102，94，91，86，175，177 （3）当前磁头在143道上，并且刚刚完成125道的请求 147，150，175，177，130，102，94，91，86五、 调度算法（求周转时间，加权周转时间）1先来先服务调度算法FCFS：该算法按照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之投入运行。例2优先级调度算法：总是选择具有最高优先级的进程首先使用处理机。在这种算法中，首先考虑的问题是如何确定进程的优先数。 分为： 静态优先权：在创建进程的时候便确定的，且在进程的运行期间保持不变。（简单易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期不被调度的情况。所以，只在要求不太高的系统中，才使用静态优先数（权）动态优先权：在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能 例：3.最短作业/进程优先法（SJF/SPF）：SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。4.最高响应比作业优先算法（HRN）：是对FCFS方式和SJF方式的一种综合平衡响应比。R(作业等待时间需运行时间)/ 需运行时间 1已等待时间 / 需运行时间 1W/T例：六：页面置换算法先进先出页面淘汰算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之理想淘汰算法最佳页面算法（OPT） 淘汰以后不再需要的或最远的将来才会用到的页面最近最久未使用页面淘汰算法（LRU） 选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页1 已知页面走向为1、2、1、3、1、2、4、2、1、3、4，且开始执行时主存中没有页面。若只给该作业分配2个物理块，当采用FIFO页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，缺页率又为多少？分析及相关知识 在进行内存访问时，若所访问的页已在主存，则称此次访问成功；若所访问的页不在主存，则称此次访问失败，并产生缺页中断。若程序P在运行过程中访问页面的总次数为S,其中产生缺页中断的访问次数为F,则其缺页率为：F/s. 解：根据所给页面走向，采用FIFO淘汰算法的页面置换情况如下：页面走向 1 2 1 3 1 2 4 2 1 3 4物理块1 1 1 3 3 2 2 1 1 4物理块2 2 2 1 1 4 4 3 3缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 从上述页面置换图可以看出：页面引用次数为11次，缺页次数为9次，所以缺页率为9/11。若采用后一种页面淘汰策略，其页面置换情况如下：页面走向 1 2 1 3 1 2 4 2 1 3 4物理块1 1 1 3 1 1 1 3 4物理块2 2 2 2 4 2 2 2缺页 缺 缺 缺 缺 缺 缺 缺 缺 在一个请求分页存储管理系统中，一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，当分配给该作业的物理块数分别为3，4时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。（1） 最佳置换淘汰算法（2） 先进先出淘汰算法（3） 最近最久未使用淘汰算法解：（1）根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 4 4 2 2块2 3 3 3 3 3 1块3 2 1 5 5 5缺页 缺 缺 缺 缺 缺 缺 缺缺页率为：7/12走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 4 4 1块2 3 3 3 3 3块3 2 2 2 2块4 1 5 5缺页 缺 缺 缺 缺 缺 缺 缺缺页率为：6/12由上述结果可以看出，增加分配 给作业 的内存块数可以降低缺页率（2）根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 1 1 1 5 5 5块2 3 3 3 4 4 4 3 2块3 2 2 2 3 3 2 1缺页 缺 缺 缺 缺 缺 缺 缺缺页率为：9/12走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 4 5 5 5 5 1 1块2 3 3 3 3 4 4 4 4 5块3 2 2 2 2 3 3 3 3块4 1 1 1 1 2 2 2缺页 缺 缺 缺 缺 缺 缺 缺缺页率为：10/12由上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为Belady 现象 。(3) 根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下：走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 1 1 1 5 2 2 2块2 3 2 4 4 4 4 1 1块3 2 3 2 3 3 3 3 5缺页 缺 缺 缺 缺 缺 缺 缺缺页率为：10/12走向 4 3 2 1 4 3 5 4 3 2 1 5 块1 4 4 4 4 4 4 4 5块2 3 3 3 3 3 3 3块3 2 2 5 5 1 1块4 1 1 2 2 2缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为:8/12 由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率.