1、操作系统期末复习Made by Tzh1第一部分：大题 本部分为课上老师所讲的几道大题，作为大题而言命中率应该蛮高的吧，它们包括：资源分配图 硬盘调度 页面置换算法 PB操作 物理地址替换21.资源分配图 会看、会画 会判断死锁P1P2r1r23会看、会画P1P23个资源2个资源P1进程P1进程请求资源进程拥有资源P1拥有2个r1资源并请求1个r2P2拥有1个r1资源和1个r2资源并请求1个r1r1r24判断死锁P1P2P1需要1个r2P2需要1个r1R1剩余0个资源R2剩余1个资源5P2的需求无法满足，但P1可以得到满足P1P2P2需要1个r1R1剩余2个资源R2剩余1个资源P1顺利执行，释
2、放占用所有资源6P2需求得到满足，顺利执行P1P2R1剩余3个资源R2剩余2个资源在这种情况下不会死锁7那么，什么情况下会产生死锁呢P1P2P1需要2个r2P2需要1个r1R1剩余0个资源R2剩余1个资源此时，P1、P2的需求都无法得到满足，死锁82.磁盘调度想象，从磁盘圆心处向外画一条直线作为我们下图的X轴，把磁盘的磁道序号标在上面。9题目是这样出的 条件：欲访问的磁道号：100、55、58、39、18、90、160、150 磁头当前位置：100 问题：磁头移动磁道数和平均寻道长度101.先来先服务算法100、55、58、39、18、90、160、150我们从起始位置开始，按顺序扫描，设磁头
3、移动磁道数为m，初始为0100、55、58、39、18、90、160、150磁头移动到55，m+=(100-55),m=45100、55、58、39、18、90、160、150磁头移动到58，m+=(58-55),m=48100、55、58、39、18、90、160、150磁头移动到39，m+=(58-39),m=67注意：磁头移动的是距离而不是位移，所以不可能为负数，因此一定是大减小11以此类推，直到全部扫描完当然，如果是答题，我们直接列式子即可m=(100-55)+(58-55)+(58-39)+.=结果平均寻道长度=m/n n为磁道号个数122.最短寻道时间优先算法为了节约时间，这次我们
4、不再按照顺序来扫描磁盘了18、39、55、58、90、100、150、160还是那些磁道，不过这次我们提前排好序，起始位置依然100接着我们看，在需要跑的磁道中，离100最近的磁道是哪个这也是我们之所以要排序的原因，在这种情况下只有100相邻的两个磁道可能是我们的选择我们发现，相比150,磁道90离100更近，所以我们先去9018、39、55、58、90、100、150、160m+=(100-90)m=10同样，相比于100,58距离90更近，我们选择5818、39、55、58、90、100、150、160m+=(90-58)m=42以此类推，知道将所有磁道跑完当然，跑过的磁道我们不会跑第二遍
5、我猜你可能会问:这真的是最短的寻道时间吗？当然，答案肯定是不一定，计算机只能看到下一步的情况，但它不可能像围棋高手一样总览全局，至于真正的最短，那就是我们程序员写的算法才能够实现了，在操作系统中不会这么复杂133.扫描算法（电梯算法）没错，就像是电梯一样，直上直下，一条道走到黑，撞了南墙再回头18、39、55、58、90、100、150、160同样的，我们把磁道号排好序，初始位置100然后，我们按照序号增加的方向依次寻道18、39、55、58、90、100、150、16018、39、55、58、90、100、150、160咚！撞墙了，这时可以回头了，但注意寻过道的磁道不需要再走一遍18、39、
6、55、58、90、100、150、160所以我们直接跳到9018、39、55、58、90、100、150、16018、39、55、58、90、100、150、16014分页存储求物理地址指令：Load 1,2500指令的逻辑地址是100，页长1k，求指令的物理地址1.求页号 逻辑地址/页长，商为页号，余数为偏移量 2.查表 3.物理地址=物理块号*页长+偏移量页号页号物理物理块号块号041827取了两次地址，第一次根据逻辑地址找到物理地址，第二次取物理地址15页面置换算法如果给的是逻辑地址需要求出页号页号=逻辑地址/页长（要的是商）16先进先出（FIFO）将页号依次排好17方法一开始是依次装入
7、物理块，全都有缺页中断18方法如果物理块满了，判断哪个页面存在时间最长就替换方法是向左划线判断哪条最长，同时缺页中断19方法如果下一个页面物理块已经有了，就不用写了，也没有缺页中断20最近最久未使用（LRU）21方法往前数第三个来替换（有几个物理块找几个），但不算重复的，有重复的还要往前找22要计算的东西缺页次数：每一次页面替换和页面装入（画的对勾数）被置换的页号顺序：被替换走的页号按顺序排列缺页率=缺页次数/页面总数23生产者消费者问题他们又是互斥关系，又是相互协作关系，也是同步关系24解法P操作，也可以是wait操作是-，只有参数大于0才可以顺利执行V操作，也可以是signal操作是+，相
8、当于是恢复25例题2.假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）；（2）指出算法中所用信号量的名称、作用及初值。解 S1:阅览室可供使用的空座位，其初值为50 S:是否可通过阅览室，其初值为1 Process READ_in（i=150）到达阅览室入口处;P(S1);P(S);在入口处登记座位号;V(s);进入座位并阅读;Process READ_out（j=150）结束阅读到达阅览室入口处;P
9、(S);在入口处注销座位号;V(S1);V(S)离开入口处;26例题请用信号量实现下图所示的前趋关系27调度算法28运算方法完成时间：就是目前的完成时间加上下一个要运行的进程的服务时间周转时间：各进程的完成时间减去其到达的时间带权周转时间：周转时间/服务时间高响应比优先调度算法先算出优先权再进行比较，先运行大的再运行小的优先权=（等待时间+要求服务时间）/要求服务时间等待时间：该进程要开始进行的时候总共经过的时间29概念题本部分为课上老师在书中所划的概念30操作系统的目标有效性 提高系统资源利用率 提高系统的吞吐量 吞吐量是 每秒的数据处理量 吞吐量是在给定时间段内系统完成的交换数量.即系统的
10、吞吐量越大,说明系统在单位时间内完成的用户或系统请求越多,系统的资源得到充分利用。方便性可扩充性开放性31操作系统的作用用户接口：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统操作系统接口包括：1.命令方式2.系统调用方式3.图形、窗口方式计算机系统资源的管理者：OS推动操作系统发展主要动力：1.提高计算机资源的利用率2.方便用户3.器件升级32操作系统的发展过程人工操作方式缺点：1.用户独占全机2.CPU等待人工操作脱机输入/输出方式优点：1.减少了CPU的空闲时间2.提高了I/O速度33批处理系统（无交互能力）单道批处理系统多道批处理系统(宏观并行，微观串行)优点：1.资源
11、利用率高2.系统吞吐量大缺点：1.平均周转时间长2.无交互能力面临问题：1.处理机管理问题2.内存管理问题3.I/O设备管理问题4.文件管理问题5.作业管理问题34分时系统定义：它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。用户的需求具体表现在：1.人-机交互2.共享主机3.便于用户上机关键问题：1.用户是否能及时接收命令2.用户是否能及时处理命令特点：多路性独立性及时性交互性35实时系统硬实时与软实时的区别硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统 不能实现它的预期目标。软实时系统的时限是一个柔
12、性灵活的，它可以容忍偶然的超时错误。失败造成的后果并不严重，例如在网络中仅仅是轻微地降低了系统的吞 吐量。36分时系统与实时系统的比较1.多路性：分时系统的多路性与用户情况有关，时多时少。实时控制系统的多路性则主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制2.独立性：都是服务请求彼此互不干扰3.及时性:实时系统及时性要求更强4.交互性：实时系统的人与系统的交互仅限于访问系统中某些特定的专用服务程序，交互性分时系统更强5.可靠性：实时系统要求更可靠37操作系统基本特性并发性：并行性和并发性是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并
13、发性是指两个或多个事件在同一时间间隔内发生。共享性：是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用虚拟性：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。物理实体(前者)是实的，即实际存在的，而后者是虚的，是用户感觉上的东西。异步性：每次只允许一个进程执行，其余进程只能等待。38操作系统的主要功能处理机管理功能1.进程控制：为作业创建进程，撤销已结束的进程，控制进程在运行过程中的状态转化2.进程同步：互斥与同步方式来协调多个进程（含线程）3.进程通信方式：采用直接通信方式，由源进程利用发送命令将信息挂到目标进程的消息队列，之后由目标进程接收。4.调度：作业调度（高级调度）
14、：从后备队列中通过一定算法找出若干个作业并为它们分配内存，建立进程，插入就绪队列。进程调度（低级调度）：从就绪队列中选出一个进程，使该进程投入执行39操作系统的主要功能存储器管理功能1.内存分配：为每道程序分配内存空间（静态、动态）2.内存保护：使各程序执行时彼此互不干扰3.地址映射：逻辑地址到物理地址之间的转换4.内存扩充：借助虚拟存储（1）：请求调入功能：在装入部分用户程序和数据的情况下就执行，中途向OS请求从磁盘将所需调入内存（2）：将内存中一些暂时不用的数据调入硬盘腾出空间40操作系统的主要功能设备管理功能1.缓冲管理：CPU与I/O之间甚至缓冲区，解决速度不匹配的问题单缓冲机制、可双
15、向传送的双缓冲机制、提供多个设备同时使用的公用缓冲池机制2.设备分配：根据用户的I/O请求，为其分配所需设备3.设备处理：CPU与I/O之间的通信41操作系统的主要功能文件管理功能1.文件存储空间的管理2.目录管理：系统为每个文件建立一个目录项，包括：文件名、文件属性、文件在磁盘上的物理位置3.文件的读/写管理：根据用户给出的文件名检索文件目录，从中获得文件在外存中的位置。4.文件保护：42操作系统给应用的接口程序接口也称为系统调用库函数属于用户程序而非系统调用，是系统调用的上层，有些库函数与系统调用是无关的（math.h）所谓原语，是操作系统内核中，由若干条指令构成、用于完成一个特定的功能的
16、一个过程，该过程在执行时是不可中断的。43微内核系统（不含LINUX）优点1.提高系统可扩展性2.提高系统可靠性3.可移植性4.提供了对分布式系统的支持5.融入了面向对象技术缺点：运行效率低硬中断：由与系统相连的外设(比如网卡、硬盘)自动产生的。主要是用来通知操作系统系统外设状态的变化微内核中断和陷入处理（软中断）将与硬件紧密相关的一小部分放在微内核中处理，微内核所做的就只是前期处理，将消息发给服务器由服务器再进行后期处理，因此微内核可以做的很小。44进程的顺序执行顺序执行（适合直接访问）：例如输入与打印，必须按顺序前趋图：有向无环图进程由创建而产生，由调度而执行，由撤销而消亡45进程的并发执
17、行程序的并发执行：多道程序可同时进行，但对于每一道程序而言是顺序执行。程序并发执行的特征：1.间断性：一个任务可能需要等待它的前驱任务完成才能继续执行，产生等待。2.失去封闭性：多个程序共享系统中资源，这些资源将由多个程序来改变。3.不可再现性：由于失去封闭性，输入的结果与并发程序的速度有关，每一次的输出结果不同。46进程特征和状态1.结构特征：进程实体（在UNIX中称为“进程映像”）程序段相关数据段PCB：作用寄存器有什么，进程的唯一标识动态性：进程是程序的一次执行过程，它有一定的生命期并发性：多个进程同时进行独立性：进程实体独立异步性：进程各自独立，速度不一2.进程的状态许可释放47进程控
18、制块（PCB）进程控制块组织方式：1.链接方式按进程优先级高低排列隐式链接最不适合 直接访问执行指针就一个链接字482.索引表方式49进程控制进程的创建：1.申请空白PCB2.为新进程分配资源3.初始化进程控制块（PCB）4.将新进程插入就绪队列终止过程：1.通过该进程PCB读出该进程的状态2.结束该进程的执行3.结束该进程的子孙进程4.释放该进程占有的资源5.将被终止进程从所在队列移出50进程阻塞与唤醒进程的阻塞：进程由于某些原因无法继续进行，进程调用阻塞源语自己把自己阻塞，从执行状态变为阻塞状态。阻塞原因：1.请求系统服务未得到响应。2.启动某种操作（操作完成才可继续执行）。3.新数据尚未
19、到达。4.无新工作可做进程的唤醒（与阻塞互逆）：当进程所期望的事件出现，便自己调用唤醒源语，将自己从阻塞队列移出，到就绪队列。挂起：由用户或父进程引起激活（与挂起互逆）：由用户或父进程引起51进程同步互斥临界区：每个进程访问临界资源的那段代码称为临界区临界资源（硬件资源如打印机等）：在一段时间内只允许一个进程访问的资源，临界资源的访问要求互斥的访问进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。进程同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是
20、所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源52同步机制规则1.空闲让进2.忙则等待3.有限等待：不能让进程一直等，得一段时间内能得到临界资源4.让权等待：进程如果不能进入临界区，就别等了信号量1.整型信号量：wait（S），signal（S）S为整型信号量，初值为1，当前为2代表有两个资源，当前为0代表被占用，当前为-1代表已经有一个等待2.记录型信号量除了对信号量加减之外，还有判断，不行就阻塞去3.AND型信号量：一个进程可能需要多个资源才能进行，中途可能有其它资源争夺，所以为了解决死锁的问题，我们在wait语句中增加and条件，只有判断它每一个要求的资源都存
21、在，才占用，否则阻塞信号量集：设置需求值和下限值，判断条件不再是1，而是下限值53信号量的应用1.利用信号量实现进程互斥：设置一互斥信号量，初值为1，标记该资源是否可以被使用，从而使进程对该资源互斥访问2.利用信号量（初值为0）实现前趋关系：对于有前置的等待进程，只有它的前趋进程执行完才执行该进程，前趋进程是否执行结束我们通过信号量来控制。54经典进程同步问题生产者消费者读者写者哲学家进餐问题55进程通信进程间的信息交换直接通信方式：直接把消息发送给目标进程，发送进程和接收进程都是显示方式提供对方标识符间接通信方式：有一个实体（信箱）暂存发送的消息，接受消息的一方也从信箱中获取消息消息缓冲队列
22、通信机制：在缓冲区暂存信息，以队列的形式逐条存储56线程（只是调度单位）进程使资源分配单位+调度单位属性：1.轻型实体：基本不拥有系统资源，只有TCB2.独立调度和分派的基本单位：不可再分，切换迅速开销小3.可并发执行4.共享进程资源内核支持线程：进程的创建撤销都是利用系统调用进入内核，线程也是如此用户级线程：只存在于用户空间中，无需系统调用57调度作业调度（高级调度、长程调度）：从后备队列中通过一定算法找出若干个作业并为它们分配内存，建立进程，插入就绪队列。进程调度（低级调度、短程调度）：从就绪队列中选出一个进程，使该进程投入执行1.保存现场信息，存入PCB2.按某种算法选取进程3.把处理器
23、分配给进程基本机制：1.排队器：将就绪进程排队，提高效率2.分派器：从就绪队列提出选中的要执行进程3.上下文切换：第一队上下文：将当前运行进程的信息保存给分派程序第二队上下文：将新进程的现场信息装进来58调度方式非抢占方式：一个进程一直运行到完才运行下一个抢占方式：通过以下原则暂停某个正在运行的进程原则：1.优先权原则：紧急任务具有较高优先权2短作业优先原则：先执行耗时短的进程3.时间片原则：按时间片流转，公平。时间片大了小了都不好，应该在0.01s0.1s之间（大部分如此）59调度队列模型仅有进程调度：完全按照用户键入的命令顺序执行程序作业调度：根据不同原则的不同算法选择插入就绪队列的进程，
24、不一定按顺序。中级调度：把进程就绪分为内存就绪（进程在内存中就绪）和外存就绪（进程在外存中就绪），阻塞状态也分成外存内存调度准则面向用户：周转时间短、响应时间快、截止时间保证、优先权准则面向系统：系统吞吐量高、处理机利用率好、各类资源平衡利用60实时调度最早截止时间优先（EDF）算法：任务的开始截止时间越早，优先级越高最低松弛度优先（LLF）算法：根据任务紧急或松弛的程度来确定优先级61死锁定义：多个进程抢夺资源而形成的僵局原因：1.竞争资源：因为诸进程对资源的竞争引起2.进程间推进顺序非法：请求和释放资源的顺序不当，也同样会导致产生进程的死锁。产生死锁的必要条件1.互斥条件：该资源要求访问的
25、进程互斥访问2.请求和保持条件：该进程已占有资源但还请求其他资源，但资源又被其他进程占用，则该进程请求进程阻塞，又对已获得资源不放3.不剥夺条件：进程已获得的资源在该进程执行完毕之前不释放4.环路等待条件：发生死锁时，必然存在一个进程资源的环形链P0，P1，P2,.Pn，P0等待P1资源，P1等待P2资源。Pn等待P0资源62处理死锁方法1.预防死锁：通过破坏产生死锁的四个必要条件中的某些来避免死锁2.安全状态：在资源分配之前先检测资源分配安全性，若不安全，则另进程等待银行家算法63银行家算法的步骤64死锁检测与解除检测方法：利用资源分配图（大题第一个）死锁解除：1.剥夺资源：从其它进程剥夺足够量的资源给死锁进程解除死锁状态2.撤销进程：撤销死锁进程温柔一点的方法是按某种顺序逐个撤销死锁进程，在此过程中可以释放资源，使得某些死锁进程得以解除死锁状态65
