操作系统复习题纲2014肖老师

复习题纲操作系统（2014）掌握计算机软件的分类、操作系统的概念、微程序、命令解释器、操作系统的工作状态、用户软件的工作状态、操作系统的作用、进程、文件、虚拟机、系统调用以及系统结构等基本概念；并在掌握操作系统概念的基础上能够区分哪些指令是特权指令、哪些指令是非特权指令；CPU状态：管理状态与用户状态。第一部分引言第二部分进程掌握进程的基本概念、进程的特点、进程的状态以及状态之间的转化关系、线程的概念、线程实现的两种方式以及相应的特点；掌握进程通信中的基本概念内容包括竞争条件、临界区、互斥、临界区的求解原则、信号量、进程调度所需要考虑的因素、具体的各种进程调度算法（先来先服务、时间片轮转、优先级调度、多重队列、最短作业优先算法）等；能够运用所学的进程通信的知识，分析软件算法中所存在的问题，并能够在分析问题的基础上能运用相应的知识解决实际应用中的相应问题；第三部分输入/输出系统掌握：I/O设备的硬件软件原理，能够区分相关的I/O操作具体是在拿一软件层次上完成。了解死锁的定义、死锁发生的必要条件以及处理死锁的策略，针对于这些处理策略有哪些相应的算法来解决；磁盘软件以及磁盘臂调度算法、磁盘出错的处理等，掌握时钟软件所完成的任务运用：根据系统给出的资源分配图能够分析判断系统的状态；根据实际的情况能够对I/O设备的处理进行优化设置；第四部分存储器管理存储器的重定位和保护；固定分区与可变分区的概念；可变分区的内存管理以及使用链表的内存管理中的分配算法；分页的虚拟存储器的实现过程，虚拟地址到物理地址的转化过程；页面的替换算法；分页系统中的设计问题；第五部分文件系统文件系统的基本概念：文件命名、文件结构、文件类型、文件存储、文件属性、文件操作、层次目录系统、路径名称、目录操作；掌握文件系统的实现（文件的实现、目录实现）、磁盘空间的管理、文件系统的可靠性、文件系统的性能；安全性一、考试题型１．简答题5个（30分）２．５个大题（7０分）１．算法应用２．应用理论３．编程应用二、复习纲要１．作业调度２．进程调度＞FCFS.SJF.RR(RoundRobin)时间片轮转3.内外存交换调度（页面置换）OPT（clockpolicy）FIFO、LRUSecond—chance变强型（NUR）4.磁盘空白块管理算法①位图②链表FF.NF.BF.WF.③伙伴５．磁盘读写臂调度算法FCFS、SSTF、SCAN、LOOK.６．地址映射与转换虚地址与实地址，地址转换图７．UNIX文件系统结构与i结点。８．P.V操作、读写者问题（读者优先）？9．资源管理，死锁分析与研究1、什么是操作系统，它与系统软件之间的关系是什么？操作系统的主要功能是什么？答：操作系统是控制计算机的所有系统资源并提供开发应用程序的基础。操作系统是最基本的系统软件。操作系统的主要功能是虚拟机和资源管理器。2、资源（设备）可以分为那几类？打印机和磁盘属于什么类资源（设备）？答：从资源的可否剥夺的角度看，可以把资源分为可剥夺资源和不可剥夺资源。从设备的占有角度看，资源分为独占设备、共享设备和虚拟设备。3、读盘操作过程中所涉及到的时间开销按照时间开销从大到小依次为那些？有什么好的方法减少读盘操作的时间？答：从大到小依次为：寻道时间、旋转延迟时间、实际的数据传输时间。选择好的读写臂调度算法，减少寻道时间，有效减少读盘操作整的时间。4、若某单处理机系统中有M个进程，则处于就绪状态、运行状态、阻塞状态中的进程个数分别最多为多少？答：就绪状态进程最多为M个、运行状态进程最多为1个、阻塞状态进程最多为M个。5、什么是死锁，死锁发生的必要条件是什么？处理死锁常用的策略有那些？答：若一个进程集合中的每一个进程都在等待只能由本集合中的另一进程才能引发的事件，则这种情况被视为死锁。死锁发生的必要条件是互斥、非剥夺、部分分配和循环等待条件。处理死锁常用的策略主要（1）有忽略该问题；（2）检测死锁并恢复；（3）死锁避免；（4）死锁预防。6、在分页技术中由虚拟地址变换为物理地址的过程有那几步？答：（1）利用CPU所提供的虚拟地址计算出页号和页内偏移；页号=虚拟地址DIV页大小页内偏移=虚拟地址MOD页大小（2）根据页号查找页表，得到页架号（块号）；（3）计算物理地址物理地址=页架号*页大小+页内偏移三、例题讲解例１．假设系统由相同类型的m个资源组成，系统有n个进程，每个进程至少请求一个资源，证明：当n个进程最多需要的资源之和小于m+n时，该系统无死锁。解：证明：假设当n个进程最多需要的资源之和小于m+n，系统死锁。niinm1max最多需求nininiiiiLoanNeed111max还需求已占有因为系统死锁mLoaninmnmNeedi)(至少在一个Pi其Needi=0，此时Pi不死锁，与假设题意矛盾，所以系统不死锁。2.某系统中有六台打印机，N个进程共享打印机资源，每个进程要求两台，试问N取哪些值时，系统才不会发生死锁？解：由上可知证：n个进程最多需要的资源之和小于6+n时，该系统无死锁，即2n6+n，n6。n取值为1，2，3，4，5另证：如下图所示：当n=6时，最糟情况有：P1P2P3P4P5P6每一进程已占有一个资源，还申请一个资源，此时死锁。同理n6时系统也会出现死锁。而n=5时，最糟情况下也会有P1P5……此时可化简为完全可化简图，不死锁。同理1n5时也不死锁，n取值为1，2，3，4，5。例题2.设某系统有一256k的空白区，现有以下作业序列和对内存的要求：作业1要140k，作业2要求16k，作业3要求80k，作业1完成，作业3完成，作业4要求70k，作业5要求128k。试用首次适应和最佳适应算法对上述作业进行可变分区存贮分配(绘图)并讨论。解：job1(140k)job2(16k)job3(80k)140k156k236k256kjob5(128k)job2(16k)128k140k156kjob4(70k)226k256kjob4(70k)70k86k214kjob2(16k)job5(128k)256k浮动FFBFjob4(70k)job2(16k)70k140k156kjob5无法分配256k例3某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见下表，此刻系统的可用资源向量为（2，1，2），问题：（1）将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；（2）如果此时P1和P2均发出资源请求向量Request（1，0，1），为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因；（3）如果（2）中两个请求立刻得到满足后，系统此刻是否处于死锁状态？进程最大需求占有量R1R2R3R1R2R3P1322100P2613411P3314211P4422002解答（1）系统资源总数为（9，3，6）。各进程对资源需求矩阵为：222202103420（2）采用银行家算法进行计算得：系统不可以将资源分配给进程P1，虽然剩余资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各个进程能够正常运行下去。因此进程P1进人等待状态。系统可以满足P2的请求，因为分配完成后，至少还可以找到一个安全序列，如P2P1P3P4使各进程可以运行至结束。（3）系统满足进程P1和P2的请求后，没有立即进入死锁状态，因为此时所有进程还处于运行状态，没有被阻塞；只有等到进程继续申请资源并因得不到满足而全部进人阻塞状态，死锁才真正发生了。例题4.在一个请求页式存储系统中，一程序的页面走向为4.3.2.1.4.3.5.4.3.2.1.5采取LRU页面置换算法，设分配给该程序的存储块数M分别为3和4时，请求出在访问过程中发生的缺页次数和缺页率，并比较所得结果，从中可得到什么启发？解：当M＝3时432143543215432143543215432143543214321435432++++++++++初值缺页10次，缺页中断率为%3.83%1001210当M＝4时缺页7次，缺页中断率为%6.66%100128在LRU算法下，当M增大时，缺页次数减少，缺页中断率也减少。432143543215432143543215432143543214321435432+++++++432111543初值+例题5.假定五个作业A～E提交时间相同，且实际需要运行的时间分别是10、6、2、4和8分钟，外部分配的优先级数分别是3、5、2、1和4，(设数值大的优先数高)。忽略CPU的切换时间，分别就下列几种调度算法计算作业的平均周转时间。a.轮转法；b.优先级调度；c.SJF解：运行t优先级10624835214(a)轮转法：(时间片以及CPU切换时间都较小可忽略)C完成：2×5=10分钟D完成：10+(4–2)×4=18分钟调度次序：CDBEAE完成：24+(8–6)×2=28分钟A完成：28+(10–8)×1=30分钟)(2253028241810分钟TB完成：18+(6–4)×3=24分钟(b)优先级调度5)421086()21086()1086()86(6T5302624146)(20分钟调度次序：BEACD(c)SJF5)108642()8642()642()42(2T530201262)(14分钟调度次序：CDBEA例题6.设有一个数据区，有若干进程要去读或写它，遵循下列原则：写是互斥的，当一进程正在写时，其它进程既不能写，也不能读；读可同时进行，只要没有进程正在写，则任何进程都可以读，请用P，V操作写出读写过程的同步算法(要给出信号量物理意义以及初值)答：varmutex,wrt:Semaphore;readcount:integer;mutex:=wrt:=1;readcount:=0;parbeginReaderi:beginWait(mutex);readcount:=readcount+1;ifreadcount=1thenWait(wrt);Signal(mutex);读数据集；Wait(mutex);readcount:=readcount–1;ifreadcount=0thenSignal(wrt);Signal(mutex);endWriteri:beginWait(wrt);写数据集;Signal(wrt);endcoend例题7.有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：(1)为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？(2)用类Pascal语言和Wait,Signal操作写出这些进程间的同步算法。答：(1)应编写1个程序；设置2个进程；进程与程序间的对应关系是：多对1。(2)beginS1:=100(有100个座位)S2:=0(有没阅读者)mutex:=1cobeginP1:repeatP(S1);P(mutex);登记信息;V(muetx);V(S2)就座，阅读；untilfalsecoendendP2:repeatP(S2)P(mutex);消掉信息;V(muetx);V(S1);离开阅览室;untilfalse课程结束！祝学习快乐！