操作系统总复习题纲(整理版)

考试题型：选择题（20分），20个选择，每个选择1分填空题（20分），20个空，每空1分简答题（25分），5道题，每题5分综合题（35分），3道题，第二章：用信号量解决进程同步、互斥问题（生产者消费者问题）第三章：处理机调度（通用/实时）/银行家算法第四章：分页系统地址变换/页面置换算法/动态分区分配算法总分：100分（闭卷，考试允许带计算器，所有计算结果精确至小数点后2位）考试范围第一章操作系统引论第二章进程管理第三章处理机调度与死锁第四章存储器管理第五章设备管理第六章文件管理第一章操作系统引论1、操作系统的作用：1)OS作为用户与计算机硬件系统之间接口(用户观点)：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统；2)OS作为计算机系统资源的管理者(资源管理者观点)；3)OS实现了对计算机资源的抽象(虚拟机观点)。2、操作系统的发展过程1)批处理系统是如何提高资源的利用率用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。2)多道与单道的周转时间计算1单道：顺序执行的总时间2多道——抢占式/非抢占式3)分时系统（为什么引入，实现中的关键问题）1引入目的：为了改进响应时间和性能，提供交互式操作环境，导致了分时系统的出现。2实现中的关键问题：·及时接收——多路卡：使主机能同时接收各用户从终端上输入的数据。——缓冲区：暂存用户键入的命令。·及时处理——作业直接进入内存——不允许一个作业长时间占用处理机4)实时系统（为什么引入，更注重什么特征）1引入原因：为了满足实时控制和实时信息处理的应用需求2更注重什么特征：多路性、独立性、及时性、交互性、可靠性3、操作系统四大特征——并发性、共享性、虚拟性、异步性1)并发：在一段时间内宏观上有多个程序在同时运行；共享：系统中的资源可供内存中多个并发执行的进程(线程)共同使用；虚拟：通过某种技术把一个物理实体变为若干个逻辑上的对应物；异步：进程以人们不可预知的速度向前推进2)并发与并行概念1并行性是指两个或多个事件在同一时刻发生；2并发性是指两个或多个事件在同一时间间隔内发生。4、五大功能——处理机管理、存储器管理、设备管理、文件管理、提供接口1五大功能：1)处理机管理：创建和撤销进程(线程)，撤销已结束的进程，以及控制进程在运行过程中的状态转换；2)存储器管理：为多道程序的运行提供良好的环境，方便用户使用存储器；3)设备管理：完成用户进程提出的I/O请求；为用户进程分配其所需的I/O设备；提高CPU和I/O设备的利用率；提高I/O速度；方便用户使用I/O设备。4)文件管理：对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安全性；5)提供接口：操作系统向用户提供用户与操作系统的接口--用户接口：是提供给用户使用的接口,用户可通过接口取得操作系统的服务。--程序接口：以系统调用的形式供用户编程时使用。几乎各种操作系统都提供了系统调用，供程序设计。2接口类型：1)用户接口（CLI、GUI）·CLI(CommandLineInterface)：命令行接口·GUI(GraphicsUserInterface)：图形用户接口2)程序员接口（API,ApplicationProgrammingInterface,应用程序接口）5、OS结构：——微内核结构1)所采用的技术：采用面向对象技术，基于“抽象”和“隐蔽”原则控制系统的复杂性，再进一步利用“对象”、“封装”和“继承”等概念来确保操作系统地“正确性”、“可靠性”。2)微内核中包括的内容：1基本概念：·足够小的内核；·基于客户/服务器模式；·应用“机制与策略分离”原理；·采用面向对象技术。2基本功能：·进程(线程)管理；·低级存储器管理；·中断和陷入处理；3优点：·提供了系统的可扩展性；·增强了系统的可靠性；·可移植性；·提供了分布式系统地支持；·融入了面向对象技术。4存在的问题：·运行效率有所降低；·引起更多的上下文切换。第二章进程管理1、前趋图（要求会画，会用相应的程序来描述）概念：是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。2、程序并发执行时的特征——（间断、失去封闭、不可再现）1)间断性：程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约的关系。相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。2)失去封闭性：程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。(封闭性：程序运行时独占全机资源，资源的状态[除初始状态外]只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响)。3)不可再现性：只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，将获得不同的结果。进程相关的概念3、为什么要引入进程：为了使程序能并发执行，且为了对并发执行的程序加以描述和控制。4、进程由什么组成的（程序段+数据段+PCB）5、进程的三种基本状态——就绪、执行、阻塞它们之间如何进行转换：处于就绪状态的进程，在调度程序为之分配了处理机之后，该进程便可执行，相应地，它就由就绪状态转变为执行状态。正在执行的程序也称为当前进程，如果因分配给它的时间片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某事件而使进程的执行受阻(例如，进程请求访问某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，该进程将由执行状态转变为阻塞状态。6、进程的同步与互斥1)临界资源的概念：在一段时间内只允许一个进程访问的资源。临界资源的访问要求互斥的访问。2)临界区的概念：每个进程中访问临界资源的代码3)原语的概念：系统提供的一组通信命令4)如何写原语——具体情况具体分析5)记录型信号量的物理含义：1wait(S)：当S.value0时，表示目前系统中这类资源还有可用的。执行一次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源减少一个，因此描述为S.value:=S.value-1；当S.value0时，表示该类资源已分配完毕，进程应调用block原语自我阻塞，放弃处理机，并插入到信号量链表S.L中。2signal(S)：执行一次signal操作，意味着释放一个单位的可用资源，使系统中可供分配的该类资源数增加一个，故执行S.value:=S.value+1操作。若加1后S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，因此应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。6)如何解决忙等问题(？？？有待进一步解答)7)应用信号量机制解决进程的同步与互斥问题（生产者与消费者(可能会出综合题)、哲学家进餐、读者-写者）7、管程——代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了的操作系统地资源管理模块1)管程的组成(4部分)———管程的名称；局部于管程内部的共享数据结构说明；对该数据结构进行操作的一组过程；对局部于管程内部的共享数据设置初始值的语句。2)为什么引入条件变量：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其他进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量。8、进程的通信1)高级通信的类型（共享存储器系统、消息传递系统、管道通信）1共享存储器系统：相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。2消息传递系统：进程间的数据交换以格式化的消息为单位。程序员直接利用操作系统提供的一组通信命令(原语)，不仅实现大量数据的传递，还隐藏了通信的实现细节，使通信过程对用户是透明的，从而大大减化了通信程序编制的复杂性。3管道通信：发送进程和接受进程利用管道(用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件)进行通信。2)消息传递通信1直接通信方式：发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显示方式提供对方的标识符。2间接通信方式：进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发送给目标进程的消息；接收进程则从该实体中取出对方发送给自己的消息。通常把这种中间实体称为信箱。9、线程——轻量级的(线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证其独立运行的资源)。第三章处理机调度与死锁1、处理机调度算法1)SJF(ShortestJobFirst)，短作业(进程)优先调度算法：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。(抢占和非抢占)2)高响应比优先调度(非抢占)等待时间+要求服务时间响应时间pR(响应比)=要求服务时间=要求服务时间=13)时间片轮转(RR)(抢占)4)要求会计算周转时间与带权周转时间1周转时间=完成时间—到达时间；2带权周转时间=周转时间/服务时间2、实时调度算法1)系统处理能力与可调度性：假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为iC，周期时间表示为iP，则在单处理机情况下，必须满足下面的限制条件：11miiiPC系统才是可调度的；同理，多处理机情况下，则NPCmiii12)最早截止时间优先算法(EDF，EarliestDeadlineFirtst)：根据任务的开始截止时间来确定任务的优先级。(抢占和非抢占)3)最低松弛度优先算法(LLD，LeastLaxityFirst)：根据任务紧急(或松弛)的程度，来确定任务的优先级。(抢占)松弛度=必须完成时间—其本身的运行时间—当前时间3、掌握各种算法的调度方式(见上述算法括号中内容)4、死锁的相关概念1)死锁的定义：多个进程同时竞争多个临界资源所产生的僵持状态(多个进程竞争一个资源不会产生死锁)；进程推进次序不等当。(？？？有待进一步更正)2)产生死锁的原因：1竞争资源引起进程死锁·可剥夺和非剥夺性资源·竞争非剥夺性资源·竞争临时性资源2进程推进顺序不当引起死锁·进程推进顺序合法·进程推进顺序非法3)产生死锁的必要条件:1互斥条件：指进程对所分配到的资源进行排它性使用，即要求在一段时间内某资源仅被一进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。3不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时自行释放。4环路等待条件：在发生死锁时，必然存在一个进程——资源的环行链。即进程集合｛P0，P1，…Pn｝对资源的请求成环状：P0→P1→P2→…Pn→P0(P0正在等待一个P1占用的资源；P1正在等待P2占用的资源......)5、预防死锁的方法：1)摒弃“请求和保持”条件(静态资源分配法)：系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。2)摒弃“不剥夺”条件(资源剥夺法)：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。3)摒弃“环路等待”条件(有序资源使用法)：系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出。6、避免死锁1)银行家算法(可能会出综合题)1银行家算法中的数据结构·系统中进程总数n·资源类总数m·可利