2008年秋季操作系统答案及评分标准a.doc

操作系统（A卷）答案及评分标准一、术语解释（共20 分 每题2分）进程；进程是程序在一个数据集合上运行的过程， 它是系统进行资源分配和调度的一个独立单位;(2分)中断；CPU暂停当前程序的执行，转去处理计算机内部或外部发生的突发事件，完成突发事件处理后回到原来程序执行的过程；(2分)重定位；从程序的逻辑地址映射到物理地址的过程；(2分)页面抖动；刚调进内存的页面不久又被调出，而调出后不久又被调入，CPU大量的时间花费的页面调入调出的现象；(2分)文件的物理组织；文件在存储设备上的组织结构；(2分)分时；将CPU的运行时间划分成若干个时间段（称为时间片），循环轮流分配给各个程序（用户）使用; (2分)死锁；在一个进程集合中的每个进程， 都在等待仅由该集合中的另一进程才能引发的事件， 而无限期地僵持下去的局面; (2分)吞吐量；单位时间内完成的作业数; (2分)进程同步；一个进程执行到某一点后要等到另一进程执行到某点才能继续往下执行的一种进程间关系；(2分)虚拟存储器；只进程分配部分所需内存，剩下内存需求等到进程真正需要访问这些存储器时才被调入，但在用户看来却分配到了所有所需内存，这种内存管理方式成为虚拟存取器。(2分)二、简答题（共30分 每题5分）1. 处理机的工作状态主要有哪两种？ 为什么要设置这两种状态？处理器有用户态和和心态等2中工作状态， 设置2种工作状态的原因是为了对操作系统内核进行保护。2. 什么时候会发生缺页？ 说明缺页出现时操作系统所做的事情。当CPU要访问的页面不在内存中时，就发生缺页中断；发生缺页中断时，CPU转缺页中断处理程序执行，将待访问页面从外存调入内存，返回被中断程序，重新启动引起缺页的指令。3. 死锁产生的4个必要条件是什么？死锁产生的4个必要条件是：互斥条件、保持和等待条件、循环等待条件、不可抢占条件。4. 高级调度与低级调度的主要功能是什么? 两者是什么关系?高级调度是作业调度，为作业分配资源，将作业调入内存，并为之创建进程；低级调度为进程调度，为进程分配处理器；作业调度为进程调度做准备。5. 什么是操作系统？操作系统的主要功能是什么？操作系统是一种系统软件，是若干程序模块所的集合，它负责管理和控制计算机系统的硬件、软件资源的分配、调度和管理，使系统高效、安全地运行；为用户提供简单、直观、灵活的用户接口和使用环境；操作系统的主要功能是实现对计算机系统软硬件资源的管理。6. 为什么要引进高级通信机构? 请列举常见进程间通信机制的实例。引进高级通信机构的目的是为了在进程间实现大量数据的交换；进程间通信机制的实例有：管道、消息通信、共享内存等。三、理解题（共20分 每题5分）1. 列出5项设备管理的功能。设备分配；设备回收；设备启动;I/O操作;中断处理;缓冲区管理；2. 列出5种进程调度时机。进程正常结束；进程出错终止；运行时间片用完；等待I/O操作；优先级更高度进程就绪；3.考虑以下页表：页号物理块号021328假定页面大小是每页1024字节，有效地址的格式为(页号,页内偏移量)，请计算有效地址 (1,500)、(2,3000)、(3,100)的物理地址。答；有效地址 (1,500)的物理地址为：10243+500=3572; (3分)有效地址 (2,3000)不合法；(1分)有效地址(3,100)的页号超出页表范围，出现地址越界；(1分)4.下列程序设计技术和结构对于请求分页环境来说， 哪些是“好的”？ 哪些是“不好的”？（1）数组；（2）双向链表；（3）跳转；(4)循环；（5）二叉树4. （1）数组好；（2）双向链表不好；（3）跳转不好；(4)循环好；（5）二叉树不好；(评分标准：每项1分，最多5分)四、综合题（共30分）1. (10分)设有一台计算机， 有两条IO通道， 分别接一台卡片输入机和一台打印机。 卡片机把一叠卡片逐一输入到缓冲区B1中， 加工处理后再搬到缓冲区B2中， 并在打印机上印出， 问： (1) 系统要设几个进程来完成这个任务? 各自的工作是什么?(2) 这些进程间有什么样的相互制约关系?(3) 用P、 V操作写出这些进程的同步算法。答：(1) 可用3个进程完成：Pa：从卡片机读信息，并逐一输入到缓冲区B1中（1分)Pb：从缓冲区B1读信息， 加工处理后再搬到缓冲区B2中（1分)P3：从缓冲区B2读信息， 并在打印机上印出 (1分)(2) 这些进程间为同步关系 (2分)(3) 同步算法：初值：empty1=empty2=1; full1=full2=0; (2分)Empty1和Empty2的初值为1，Full1和Full2的初值为0Pa：(1分)While(1) 从卡片机读数据；P(Empty1);将数据写入缓冲区B1；V(Full1);Pb：(1分)While (1) P(Full1);从缓冲区B1读数据；V(Empty1)加工数据P(Empty2);将加工后的数据写缓冲区B2；V(Full2);Pc：(1分)While(1) P(Full2);从缓冲区2读数据；V(Empty2);打印信息；2. (7分)考虑下面存储访问序列， 该程序有460字： 10， 11， 104， 170， 73， 309， 185， 245， 246， 434， 458， 364设页面大小是100字，请给出访问顺序。又设该程序基本可用内存是200字，请写出采用LRU页面置换算法是页面替换顺序，计算缺页率。答：页面走向为：0，1，0，3，1，2，4，3 (1分)采用LRU算法的页面替换顺序为：页面走向01031243内存页000332231111144是否命中XXXXXX页面替换顺序0312 （2分）页面替换顺序为：0，3，1，2 (2分)缺页率为：68= 75% (2分)3.(3分) 一个操作系统支持分页虚存，所用处理机的周期时间是1s，页面大小是1000字，分页设备是磁鼓，它每分钟转3000圈，传输速率是每秒1000000字。 由系统测得下述统计结果：（1） 所执行的全部指令中有0.1%存取的页面不是当前的页面。（2） 存取另外页面的指令，它们所存取的页面有80%已在内存。（3） 当请求一个新页面时，所置换页面有50%在此期间修改过。设系统中只运行这一个程序，当磁鼓进行传送时，处理机空转等待。在上述条件下计算这个系统的有效指令时间（执行一条指令所需的平均时间）答：1个页面从外存传到内存的时间：100010-610-3 s 1 ms存取当前页面中内存单元的时间：1 us 99.9%10-6 s (1分)存取不在当前页面中内存单元（但单元已在内存）的时间：1 us 0.1% 80% 10-9 s存取不在当前页面中内存单元（但单元不在内存，被置换页面不需写回）的时间：1 ms 0.1% 20%50% =10-7 s存取不在当前页面中内存单元（但单元不在内存，被置换页面需写回）的时间：2 ms 0.1% 20%50% =210-7 s (1分)有效存取时间为: 10-6 s + 10-9 s +10-7 s + 210-7 s 1.3 us (1分)4.(10分)假定在单CPU条件下有下列要执行的作业:作业运行时间优先级1103211323414552作业到来的时间是按作业编号顺序进行的(即后面作业依次比前一个作业迟到一个时间单位)。（1）用一个执行时间图描述采用时间片轮转算法RR（时间片=1）时执行这些作业的情况；（2）并计算各个作业的周转时间是多少和平均周转时间。答： (1) RR算法执行时间图：(4分)2018516 14 1210 8 6 40 24321（2）各作业周转时间：(4分)作业12345平均周转时间周转时间19151107.2（3）平均周转时间 (2分) (19+1+5+1+10) 5=7.23操作系统（B卷）答案及评分标准一、术语解释（共20 分 每题2分）并发；两个或更多个程序同时在系统中存在并且运行， 即一个程序段执行尚未结束，另一个程序段已经开始执行实时；能够及时响应外部事件的请求，在规定的时间内完成对事件的处理;死锁预防；破坏死锁的四个必要条件之一，使死锁不可能发生；存储器碎片；经过多次内存分配与回收后产生的一些尺寸太小得不到利用存储器块；多道程序设计；同时在内存中让多个程序并发执行；线程；一种轻量级进程，位于进程内部，是处理器调度的基本单位；快表；用于保存最近需要使用的页表项的高速存储器；程序地址；程序中使用的存储器地址；系统调用；应用程序调用操作系统服务的唯一方式，采用中断机制实现；文件逻辑组织；用户看到的文件结构；二、简答题1. 操作系统主要有哪几种基本类型？ 分时系统和实时系统各有何特点？答：操作系统有3种基本类型：批处理系统，分式系统，实时系统；在分式系统中，每个用户有一个操作终端，将运行时间分成很多时间片，分给各个用户使用，但用户看来，每个都感觉在独占计算机；实时系统可对外部发生的时间在规定的时间内作出相应2. 什么是重定位？ 它分为哪几类？ 它们之间的差别是什么？答： 重定位是程序地址变换为物理地址的过程；它分为静态重定位和动态重定位2种；静态重定位在程序加载到内存时通过把程序地址修改成物理地址完成重定位；动静态重定位在程序执行中、内存访问前有硬件执行重定位。3. 文件管理的主要功能是什么？答：文件管理的主要功能：文件存储空间管理，文件目录管理，文件操作，文件保护，文件按名存取。4. 处理机调度一般可分为哪三级? 其中哪一级调度必不可少? 为什么?答：处理机调度一般可分为作业调度、交换调度和进程调度三级；其中进程调度必不可少；因为只有进程调度才能将处理器分配给进程使用。5. 在操作系统中为什么要引入进程概念? 它与程序的差别和关系是怎样的?答：在操作系统中引入进程概念是为了更好地描述程序执行过程中动态特性,这些特性是“程序”这个概念无法描述清楚的；它与程序的差别和关系是：进程是程序的执行过程，程序是进程的静态形式。6. 什么是原语？操作系统为何要引入原语的概念。答：原语是执行过程中不可被打断的一段代码（3分），操作系统引入原语的原因是为了保护一些系统状态、数据结构的一致性和完整性(2分)。三、理解题（共20分 每题5分）1. 列出文件控制块中任意5项内容。答： 文件名、文件大小、文件数据块指针、文件创建时间、文件访问权限、文件所属用户等2. 列出5项进程控制块的内容。答：进程号、进程名、进程状态、父进程指针、堆栈地址等3. 考虑如下段表写出下述逻辑地址的物理地址。（1） 0， 430；（2） 1， 10；（3） 1， 11；（4） 2， 500；（5） 3， 400；答：(1) 219+430=649(2) 2300+10=2310(3) 2300+11=2311(4) 500100， 发生地址越界(5) 132740017274. 下列程序设计技术和结构对于请求分页环境来说， 哪些是“好的”？ 哪些是“不好的”？（1）堆栈；（2） 散列符号表；（3） 顺序查找；（4） 二分查找；（5） 纯码；答：（1）好；（2） 不好；（3） 好；（4） 不好；（5） 好四、综合题（共30分）1. (10分)设系统中只有一台打印机， 有三个用户的程序在执行过程中都要使用打印机输出计算结果。 设每个用户程序对应一个进程。 问： 这三个进程间有什么样的制约关系？ 试用P、 V操作写出这些进程使用打印机的算法。答： (1)三个进程间的关系是互斥关系。(2分)(2) 进程间同步算法如下：设置一个互斥信号量mutex来协调各进程对打印机的使用，初值为1。(2分)用户进程1：(2分)P(mutex);打印计算结果1；V(mutex);用户进程2：(2分)P(mutex);打印计算结果2；V(mutex);用户进程3：(2分)P(mutex);打印计算结果3；V(mutex);2.（7分）假定分页存储系统中有快表， 多数活动页表项都可收在其中。 如果页表还是放在内存中， 内存访问时间是1s， 若快表的命中率是85%， 则有效存取时间是多少？ 若命中率降为50%， 那么有效存取时间为多少？答：（1） 有效存取时间为：(1-0.85)1 us + 1 us = 1.15 us (4分)（2） (1-0.5) 1 1 1.5 us (3分)姓名: 学号: 系别: 年级专业: ( 密 封 线 内 不 答 题 )密封线线3.(3分)假定文件A采用串连文件结构，其文件结构表示如下图所示，试计算该文件第3个数据块的内容保存在哪个物理快中。(注意：