操作系统复习题答案

总复习题部分参考答案11、在设备管理中，数据传送控制方式有哪几种？试比较它们各自的优缺点。1、程序控制输入/输出方式。控制相对简单，不需要硬件支持，CPU和I/O设备串行工作，适用于CPU执行速度较慢且外设较少的设备。2、中断输人／输出方式。能实现CPU和I/O设备及I/O设备间的并行，中断次数过多，数据容易丢失，适用于中断次数少且外设较少的设备。3、直接存储器方式DMA方式。能实现CPU和I/O设备间的并行，设备和主存之间可以直接成批传送数据，大大减少了CPU干预，需要存储器硬件支持。4、通道控制方式。CPU权利下放，干预更少，提高了系统资源利用率，需要硬件支持。2、文件的物理组织结构常见的有几种？它们与文件的存取方式有什么关系？⑴、顺序结构（又称连续结构）：是顺序存取时速度较快；当文件是定长记录文件时，还可根据文件起始地址及记录长度进行随机访问。⑵、链接（又称串联）结构：链接文件只能按照文件的指针链顺序访问，因而查找效率较低。⑶、索引结构：是可以进行随机访问，也易于进行文件的增删。3、文件存储空间管理的方法有哪些？它们的优缺点？①、空闲文件目录：⑴、如果文件太大，那么在空白文件目录中将没有合适的空白文件能分配给它，尽管这些空白文件的总和能满足需求。⑵、经过多次分配和回收，空白文件目录中的小空白文件越来越多，很难分配出去，形成碎片。②、空闲块链：⑴、可实现不连续分配。⑵、由于每个空闲块的指针信息都是存放在上一空闲块中的，这样就不用占用额外的存储空间，与空白文件目录管理方法相比节省了存储开销。⑶、因为链接信息是存放在每个空闲块中的，每当在链上增加或删除空白块时需要很多输入／输出操作，系统开销大。⑷、对于大型文件系统，空闲链将会太长。③、位示图：采用位示图的方法管理辅存空间较为简单，并且由于位示图很小，可放在内存中，访问速度较快。4、系统中调度的层次分为几级，它们的主要任务各是什么？一般地，处理机的调度分为3级：⑴、作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。⑵、交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存总复习题部分参考答案2交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。⑶、进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。六、应用题（每题10分，共20分）1、2、生产者与消费者的问题(producer/consumer)满足条件：①、消费者想取走产品时，缓冲区中至少有一个单元是满的；②、生产者想发送产品时，缓冲区中至少有一个单元是空的；用P、V操作描述它。程序描述：beginintegermutex,empty,full;mutex=1,empty=n,full=0;producer：生产者进程BeginWhiletruedo总复习题部分参考答案3BeginProducenextproductP(empty);P(mutex);/*送产品入缓冲区某单元*/buffer(i)=producti=（i+1）modnV(mutex);V(full);EndEndconsumer：消费者进程BeginWhiletruedoBeginP(full);P(mutex);/*从缓冲区某单元取产品*/goods=buffer(j)j=（j+1）modnV(mutex);V(empty);EndEndEnd2、如何预防死锁。破坏互斥条件、破坏不可剥夺、破坏“请求与保持”、破坏“循环等待”3、在存储管理中，那一种存储方法解决了共享问题，画图并解释说明。段式、段页式存储方法解决了共享问题。图：略4、设备分配中常用的数据结构有哪几种？进程请求I/O设备时，它们在设备分配中的操作顺序是什么？设备控制表DCT、控制器控制表COCT、系统设备表SDT、通道控制表CHCT顺序：SDT—→DCT—→COCT—→CHCT六、应用题（每题10分，共20分）1、平均周转时间：72总复习题部分参考答案4调度顺序：ABDCE作业名装入时间开始时间结束时间周转时间带权周转时间A8:068:068:48421B8:188:489:18602D8:369:189:42662.75C9:189:4210:06964E9:1810:0610:189682、①、描述一个保证不会出现两个邻座同时要求吃饭的算法。设信号量C[i]表示i号筷子被拿起。且互斥的，则：intC[4]={1,1,1,1,1}第i个哲学家要吃饭则p(C[i]);p(C[i+1mod5]);吃饭;v(C[i+1mod5]);v(C[i]);②、描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。方法一：奇数先取左侧，偶数先取右侧（没有拿到就等待）ifImod2==0then{p(C[i]);p(C[i+1mod5]);吃饭;v(C[i+1mod5]);v(C[i]);}else{p(C[i+1mod5]);p(C[i]);吃饭;v(C[i]);v(C[i+1mod5]);}方法二：最多只允许n-1个哲学家同时吃饭。则：设S=4（设缓冲区有4个）p(s);总复习题部分参考答案5p(C[i]);p(C[i+1mod5]);吃饭;v(C[i+1mod5]);v(C[i]);v(s);③、在什么情况下，5个哲学家全部吃不上饭？每人拿到一只筷子，出现“死锁”现象1、简述作业、进程、程序它们之间的关系。作业是用户需要计算机完成某项任务时要求计算机所作工作的集合。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。而进程则是已提交完毕程序的执行过程的描述，是资源分配的基本单位。程序是一个在时间上按严格次序前后相继的操作序列，是一个静态的概念。进程和程序既有联系又有区别，进程是一个动态的概念。进程具有并行性，而程序没有。进程是竞争计算机系统资源的基本单位，从而其并行性受到系统自己的制约。不同的进程可以包含同一程序，只要该程序所对应的数据集不同。作业是用户向计算机提交任务的任务实体。一个作业可由多个进程组成。2、画图并举例说明段页式存储管理中的地址变换过程。3、计算机硬件发展分几个时代，各时期代表性的操作系统类型各是什么？第一代，电子管时间，无操作系统。第二代，晶体管时代，批处理系统。第三代，集成电路时代，多道程序设计。第四代，大规模集成电路时代，分时操作系统。4、系统中调度的层次分为几级，它们的主要任务各是什么？一般地，处理机的调度分为3级：⑴、作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。总复习题部分参考答案6⑵、交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。⑶、进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。六、应用题（每题10分，共20分）1、读者与写者问题分析：①、任一写者访问共享数据时，其他写者或读者都不能访问共享数据，此为互斥关系，设写者的互斥信号量为wrt。②、任一读者访问共享数据时，写者不能访问，设读者是否在访问状态，我们引入另一个读者数的变量readcount，对读者在线访问共享数据，每增加一个我们使readcount+1，读者下线后，我们在使readcount-1。变量readcount记录为当前正在访问该共享数据的读者个数。③、读者对readcount的修改是互斥的，设此互斥信号量为mutex。程序描述：beginmutex=1;wrt=1;readcount=0;cobeginreaderbeginp(mutex);readcount=readcount+1;ifreadcount0thenP(wrt);V(mutex);Readingisperforming;p(mutex);readcount=readcount-1;ifreadcount=0thenV(wrt);V(mutex);EndWriter;BeginP(wrt);writeringisperforming;总复习题部分参考答案7V(wrt);EndCoendEnd;2、先进先出走向432143543215块14444555511块2333344445块322223333块41111222缺页缺缺缺缺缺缺缺缺缺缺缺页率为：10/12。最近最久未使用：表（略）缺页率为：8/12。4、文件的物理组织结构常见的有几种？它们与文件的存取方式有什么关系？⑴、顺序结构（又称连续结构）：是顺序存取时速度较快；当文件是定长记录文件时，还可根据文件起始地址及记录长度进行随机访问。⑵、链接（又称串联）结构：链接文件只能按照文件的指针链顺序访问，因而查找效率较低。⑶、索引结构：是可以进行随机访问，也易于进行文件的增删。六、应用题（每题10分，共20分）1、先来先服务最短寻道时间优先扫描算法下一磁道移动磁道数237737635320517113273191136142190129398208293694251814总复习题部分参考答案8下一磁道移动磁道数下一磁道移动磁道数32321323219058190582051520515611443761714021398222911613372364021194291118123641419437637218139822414移动总长：700平均寻道长：58.3移动总长：692平均寻道长：57.72、分析：①、任一写者访问共享数据时，其他写者或读者都不能访问共享数据，此为互斥关系，设写者的互斥信号量为wrt。②、任一读者访问共享数据时，写者不能访问，设读者是否在访问状态，我们引入另一个读者数的变量readcount，对读者在线访问共享数据，每增加一个我们使readcount+1，读者下线后，我们在使readcount-1。变量readcount记录为当前正在访问该共享数据的读者个数。③、读者对readcount的修改是互斥的，设此互斥信号量为mutex。程序描述：beginmutex=1;wrt=1;readcount=0;cobeginreaderbeginp(mutex);readcount=readcount+1;ifreadcount=1thenP(wrt);V(mutex);4022移动总长：1596平均寻道长：133总复习题部分参考答案9Readingisperforming;p(mutex);readcount=readcount-1;ifreadcount=0thenV(wrt);V(mutex);EndWriter;BeginP(wrt);writeringisperforming;V(wrt);EndCoendEnd;