操作系统复习

《操作系统》重点知识总结第一章引论•操作系统定义•操作系统的目标•推动操作系统发展的主要动力•在OS中引入多道程序设计技术的好处•多道批处理系统的特征及优缺点•分时系统与实时系统特征的比较•操作系统的基本特征•操作系统的主要功能•存储器管理的主要功能•OS的用户接口包括什么？第二章进程管理1.程序顺序执行时的特征2.程序并发执行的特征3.进程及其特征4.进程的基本状态及其转换5.引入挂起状态的原因6.具有挂起状态的进程状态及其转换7.进程控制块及其作用8.引起创建进程的事件9.引起进程阻塞和唤醒的事件10.进程之间的两种制约关系11.临界资源12.临界区13.同步机构应遵循的规则14.经典同步算法第三章处理机调度与死锁•高级调度•低级调度•进程调度的两种方式•抢占的原则•操作系统选择调度方式和调度算法的若干准则•周转时间•针对各种调度算法计算周转时间、带权周转时间•吞吐量•多级反馈队列调度算法的原理、性能•死锁、产生原因、必要条件•处理死锁的基本方法•预防死锁的方法•安全状态•银行家算法第四章存储器管理•用户源程序变为一个可在内存中执行的程序需经过哪些步骤？•程序装入的方式•重定位、静态重定位、动态重定位•内存的连续分配方式有哪些？•对换•基本分页管理原理、地址变换过程•分段系统的基本原理、地址变换过程•分页与分段的主要区别•段页式存储管理的基本原理、地址变换过程•虚拟存储器、特征•页面置换算法计算缺页率、置换率第五章设备管理•按设备的共享属性可将设备分为什么？•通道•引入通道的原因•I/O控制方式及发展宗旨•缓冲引入的原因•设备分配时应考虑的因素•设备独立性•SPOOLING、组成、特点•共享打印机原理•设备驱动程序的功能、特点•磁盘访问时间包括什么？•磁盘调度算法：计算平均寻道长度第六章文件管理•文件•文件的逻辑结构及分类•文件的物理结构及分类•文件目录•目录管理的要求•文件控制块•索引节点•文件存储空间的管理方法•成组链接法的空闲盘快的组织、分配回收过程第七章操作系统接口•系统调用桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的句子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。VARs,so,sa:semaphore:=1,0,0;//s表示盘空，so表示橘子，sa表示苹果。parbeginFather:beginrepeatwait(s);putapple();signal(sa);untilfalseendMother:beginrepeatwait(s);putorange();signal(so);untilfalseend桌上有一个盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放橘子，儿子专等吃盘里的句子，女儿专等吃盘里的苹果。只要盘子空，爸爸妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出他们四人之间的同步关系程序。Son:beginrepaetwait(so);eatorange();signal(s);untilfalseenddaughter:beginrepeatwait(sa);eatapple();signal(s);untilfalseendparend有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一个座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试用wait,signal原语描述各个进程之间的同步互斥关系。Vars,mutax:semaphore:=100,1;Reader：BeginRepeatWait(s);Wait(mutex);登记；Signal(mutex);阅览图书；Wait(mutex);取消登记；Signal(mutex);Signal(s);Untilfasleend有两个用户进程A和B，在运行过程中都要使用系统中的一台打印机输出计算结果。(1)试说明A、B两进程之间存在什么样的制约关系？答：A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用(2)为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。此题答案为：答：mutex：用于互斥的信号量，因为只有一台打印机，所以初值为1进程A进程B......P(mutex)；P(mutex)；申请打印机；申请打印机；使用打印机；使用打印机；V(mutex)；V(mutex)；设input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问：（1）这两个进程有何相互制约关系？答：这两个进程的相互制约关系为同步关系；（2）试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。此题答案为：答：设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是否有信息，初值为0，表示Q中无信息。两进程的代码段如下：input进程output进程…………While信息未处理完毕While信息未处理完毕{加工一个信息；{P（S2）；P（S1）；从Q中读出一个信息；将信息放入Q中；V（S1）；}V（S2）；}……根据如下的前趋图写出可并发执行的程序：解：vara,b,c,d,e,f,g,h,i:semaphore:=0,0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);endbeginwait(a);S2;signal(c);signal(d);endbeginwait(c);S3;signal(e);signal(f);endbeginwait(b);S4;signal(g);endbeginwait(d);wait(e)S5;signal(h);endbeginwait(f);wait(g);S6;signal(i);endbeginwait(h);wait(i);S7;endparendendS1S2S5S3S4S6S7假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。表1进程到达和需要服务时间进程到达时间服务时间A03B26C44D65E82此题答案为：表2进程的完成时间和周转时间进程ABCDE平均FCFS完成时间39131820周转时间37912128.6带权周转时间1.001.172.252.406.002.56SPF(非抢占)ABCDE平均完成时间39152011周转时间37111437.6带权周转时间1.001.171.752.801.501.84SPF(抢占)ABCDE平均完成时间31582010周转时间31341427.2带权周转时间1.002.161.002.801.001.59系统中有3种类型的资源（A,B,C,）和5个进程P1,P2,P3,P4,P5,A资源总数为10，B为8，C为8，在T0时刻系统状态如下表。系统采用银行家算法实施死锁避免策略。试问：最大资源需求量已分配资源数量ABCABCP1773020P2334210P3912302P4233212P5434012a:T0时刻此系统是否安全，若是，给出一个安全序列。b:此时若进程P2请求资源（1，1，0），是否能实施资源分配，为什么？c:在此基础上，若进程P1请求资源（2，0，1），能否实施资源分配，为什么？NEEDABC753124610021422解：依题意可得Available（3，3，2）a:T0时刻是安全的，安全序列为（P4,p2,p3,p5,p1）。（过程略）b:若进程P2请求资源Req（1，1，0），按银行家算法判断如下：1）判断Req(1，1，0)=Need2(1,2,4),表示Req为合法请求；2）判断Req(1，1，0)=Available（3，3，2），表示Req为可满足的请求；3）试探性分配Available-=Req;变为（2，2，2）Alloc2+=Req;变为（3，2，0）Need2-=Req;变为（0，1，4）4）判断新状态的安全性新状态是安全的，可找到安全序列（P4,p2,p3,p5,p1）（具体过程在此略去）,因此可分配资源，Available变为（2,2,2）,c:若进程P1请求资源Req（2，0，1），按银行家算法判断如下：1）判断Req(2,0,1)=Need1(7,5,3),表示Req为合法请求；2）判断Req(2,0,1)=Available（2，2，2），表示Req为可满足的请求；3）试探性分配Available-=Req;变为（0，2，1）Alloc1+=Req;变为（2，2，1）Need1-=Req;变为（5，5，2）4）判断新状态的安全性新状态是不安全的，因为可利用资源只能满足P4后就不能满足任何进程的全部资源需求了，即找不到安全序列，此时系统进入不安全状态。因此，不能满足进程P1的资源请求Req（2，0，1）。对访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大小分别为3，4时，使用FIFO和LRU替换算法的缺页次数。结果说明了什么？此题答案为：答：首先采用FIFO，当m=3时，缺页次数＝9，当m=4时，缺页次数＝10。采用LRU算法，当m=3时，缺页次数＝10；当m=4时，缺页次数＝8。结果说明：FIFO有Belady奇异现象，即不满足驻留集增大，缺页次数一定减小的规律；另外在m=3时，LRU的缺页次数比FIFO要多，所以LRU算法并不总优于FIFO，还要看当前访问串的特点。若干个等待访问磁盘者依次要访问的磁道为20，44，40，4，80，12，76，假设每移动一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并计算为完成上述各次访问总共花费的寻道时间。（1）先来先服务算法；（2）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）解：（1）磁道访问顺序为：20，44，40，4，80，12，76寻道时间=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道访问顺序为：40，44，20，12，4，76，80寻道时间=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道访问顺序为：40，44，76，80，20，12，4寻道时间=（0+4+32+4+60+8+8）*3=116*3=348