搜索
操作系统期末复习MadebyTzh第一部分：大题•本部分为课上老师所讲的几道大题，作为大题而言命中率应该蛮高的吧，它们包括：•资源分配图•硬盘调度•页面置换算法•PB操作•物理地址替换1.资源分配图•会看、会画•会判断死锁P1P2r1r2会看、会画P1P23个资源2个资源P1进程P1进程请求资源进程拥有资源P1拥有2个r1资源并请求1个r2P2拥有1个r1资源和1个r2资源并请求1个r1r1r2判断死锁P1P2P1需要1个r2P2需要1个r1R1剩余0个资源R2剩余1个资源P2的需求无法满足，但P1可以得到满足P1P2P2需要1个r1R1剩余2个资源R2剩余1个资源P1顺利执行，释放占用所有资源P2需求得到满足，顺利执行P1P2R1剩余3个资源R2剩余2个资源在这种情况下不会死锁那么，什么情况下会产生死锁呢P1P2P1需要2个r2P2需要1个r1R1剩余0个资源R2剩余1个资源此时，P1、P2的需求都无法得到满足，死锁2.磁盘调度想象，从磁盘圆心处向外画一条直线作为我们下图的X轴，把磁盘的磁道序号标在上面。题目是这样出的•条件：•欲访问的磁道号：100、55、58、39、18、90、160、150•磁头当前位置：100•问题：•磁头移动磁道数和平均寻道长度1.先来先服务算法•100、55、58、39、18、90、160、150•我们从起始位置开始，按顺序扫描，设磁头移动磁道数为m，初始为0•100、55、58、39、18、90、160、150•磁头移动到55，m+=(100-55),m=45•100、55、58、39、18、90、160、150•磁头移动到58，m+=(58-55),m=48•100、55、58、39、18、90、160、150•磁头移动到39，m+=(58-39),m=67•注意：磁头移动的是距离•而不是位移，所以不可能•为负数，因此一定是大减小以此类推，直到全部扫描完•当然，如果是答题，我们直接列式子即可•m=(100-55)+(58-55)+(58-39)+…..=结果•平均寻道长度=m/nn为磁道号个数2.最短寻道时间优先算法•为了节约时间，这次我们不再按照顺序来扫描磁盘了•18、39、55、58、90、100、150、160•还是那些磁道，不过这次我们提前排好序，起始位置依然100•接着我们看，在需要跑的磁道中，离100最近的磁道是哪个•这也是我们之所以要排序的原因，在这种情况下只有100相邻的两个磁道可能是我们的选择•我们发现，相比150,磁道90离100更近，所以我们先去90•18、39、55、58、90、100、150、160•m+=(100-90)m=10•同样，相比于100,58距离90更近，我们选择58•18、39、55、58、90、100、150、160•m+=(90-58)m=42•以此类推，知道将所有磁道跑完当然，跑过的磁道我们不会跑第二遍我猜你可能会问:这真的是最短的寻道时间吗？当然，答案肯定是不一定，计算机只能看到下一步的情况，但它不可能像围棋高手一样总览全局，至于真正的最短，那就是我们程序员写的算法才能够实现了，在操作系统中不会这么复杂3.扫描算法（电梯算法）•没错，就像是电梯一样，直上直下，一条道走到黑，撞了南墙再回头•18、39、55、58、90、100、150、160•同样的，我们把磁道号排好序，初始位置100•然后，我们按照序号增加的方向依次寻道•18、39、55、58、90、100、150、160•18、39、55、58、90、100、150、160•咚！撞墙了，这时可以回头了，但注意寻过道的磁道不需要再走一遍•18、39、55、58、90、100、150、160•所以我们直接跳到90•18、39、55、58、90、100、150、160•18、39、55、58、90、100、150、160分页存储求物理地址•指令：Load1,2500•指令的逻辑地址是100，页长1k，求指令的物理地址•1.求页号逻辑地址/页长，商为页号，余数为偏移量2.查表3.物理地址=物理块号*页长+偏移量页号物理块号041827取了两次地址，第一次根据逻辑地址找到物理地址，第二次取物理地址页面置换算法•如果给的是逻辑地址需要求出页号•页号=逻辑地址/页长（要的是商）先进先出（FIFO）将页号依次排好方法一开始是依次装入物理块，全都有缺页中断方法如果物理块满了，判断哪个页面存在时间最长就替换方法是向左划线判断哪条最长，同时缺页中断方法如果下一个页面物理块已经有了，就不用写了，也没有缺页中断最近最久未使用（LRU）方法往前数第三个来替换（有几个物理块找几个），但不算重复的，有重复的还要往前找要计算的东西•缺页次数：每一次页面替换和页面装入（画的对勾数）•被置换的页号顺序：被替换走的页号按顺序排列•缺页率=缺页次数/页面总数生产者—消费者问题他们又是互斥关系，又是相互协作关系，也是同步关系解法P操作，也可以是wait操作是--，只有参数大于0才可以顺利执行V操作，也可以是signal操作是++，相当于是恢复例题2.假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）；（2）指出算法中所用信号量的名称、作用及初值。解S1:阅览室可供使用的空座位，其初值为50S:是否可通过阅览室，其初值为1ProcessREAD_in（i=1„50）{到达阅览室入口处;P(S1);P(S);在入口处登记座位号;V(s);进入座位并阅读;}ProcessREAD_out（j=1„50）{结束阅读到达阅览室入口处;P(S);在入口处注销座位号;V(S1);V(S)离开入口处;}例题请用信号量实现下图所示的前趋关系调度算法运算方法•完成时间：就是目前的完成时间加上下一个要运行的进程的服务时间•周转时间：各进程的完成时间减去其到达的时间•带权周转时间：周转时间/服务时间•高响应比优先调度算法•先算出优先权再进行比较，先运行大的再运行小的•优先权=（等待时间+要求服务时间）/要求服务时间•等待时间：该进程要开始进行的时候总共经过的时间概念题•本部分为课上老师在书中所划的概念操作系统的目标•有效性提高系统资源利用率提高系统的吞吐量吞吐量是每秒的数据处理量吞吐量是在给定时间段内系统完成的交换数量.即系统的吞吐量越大,说明系统在单位时间内完成的用户或系统请求越多,系统的资源得到充分利用。•方便性•可扩充性•开放性操作系统的作用•用户接口：OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统•操作系统接口包括：•1.命令方式•2.系统调用方式•3.图形、窗口方式•计算机系统资源的管理者：OS•推动操作系统发展主要动力：•1.提高计算机资源的利用率•2.方便用户•3.器件升级操作系统的发展过程•人工操作方式•缺点：•1.用户独占全机•2.CPU等待人工操作•脱机输入/输出方式•优点：•1.减少了CPU的空闲时间•2.提高了I/O速度批处理系统（无交互能力）•单道批处理系统•多道批处理系统(宏观并行，微观串行)•优点：•1.资源利用率高•2.系统吞吐量大•缺点：•1.平均周转时间长•2.无交互能力•面临问题：•1.处理机管理问题•2.内存管理问题•3.I/O设备管理问题•4.文件管理问题•5.作业管理问题分时系统•定义：它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。•用户的需求具体表现在：•1.人-机交互•2.共享主机•3.便于用户上机•关键问题：•1.用户是否能及时接收命令•2.用户是否能及时处理命令•特点：•多路性•独立性•及时性•交互性实时系统•硬实时与软实时的区别•硬实时系统有一个刚性的、不可改变的时间限制，它不允许任何超出时限的错误。超时错误会带来损害甚至导致系统失败、或者导致系统不能实现它的预期目标。软实时系统的时限是一个柔性灵活的，它可以容忍偶然的超时错误。失败造成的后果并不严重，例如在网络中仅仅是轻微地降低了系统的吞吐量。分时系统与实时系统的比较•1.多路性：分时系统的多路性与用户情况有关，时多时少。实时控制系统的多路性则主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制•2.独立性：都是服务请求彼此互不干扰•3.及时性:实时系统及时性要求更强•4.交互性：实时系统的人与系统的交互仅限于访问系统中某些特定的专用服务程序，交互性分时系统更强•5.可靠性：实时系统要求更可靠操作系统基本特性•并发性：并行性和并发性是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。•共享性：是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用•虚拟性：是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。物理实体(前者)是实的，即实际存在的，而后者是虚的，是用户感觉上的东西。•异步性：每次只允许一个进程执行，其余进程只能等待。操作系统的主要功能•处理机管理功能•1.进程控制：为作业创建进程，撤销已结束的进程，控制进程在运行过程中的状态转化•2.进程同步：互斥与同步方式来协调多个进程（含线程）•3.进程通信方式：采用直接通信方式，由源进程利用发送命令将信息挂到目标进程的消息队列，之后由目标进程接收。•4.调度：•作业调度（高级调度）：从后备队列中通过一定算法找出若干个作业并为它们分配内存，建立进程，插入就绪队列。•进程调度（低级调度）：从就绪队列中选出一个进程，使该进程投入执行操作系统的主要功能•存储器管理功能•1.内存分配：为每道程序分配内存空间（静态、动态）•2.内存保护：使各程序执行时彼此互不干扰•3.地址映射：逻辑地址到物理地址之间的转换•4.内存扩充：借助虚拟存储•（1）：请求调入功能：在装入部分用户程序和数据的情况下就执行，中途向OS请求从磁盘将所需调入内存•（2）：将内存中一些暂时不用的数据调入硬盘腾出空间操作系统的主要功能•设备管理功能•1.缓冲管理：CPU与I/O之间甚至缓冲区，解决速度不匹配的问题•单缓冲机制、可双向传送的双缓冲机制、提供多个设备同时使用的公用缓冲池机制•2.设备分配：根据用户的I/O请求，为其分配所需设备•3.设备处理：CPU与I/O之间的通信操作系统的主要功能•文件管理功能•1.文件存储空间的管理•2.目录管理：系统为每个文件建立一个目录项，包括：•文件名、文件属性、文件在磁盘上的物理位置•3.文件的读/写管理：根据用户给出的文件名检索文件目录，从中获得文件在外存中的位置。•4.文件保护：操作系统给应用的接口程序接口也称为系统调用库函数属于用户程序而非系统调用，是系统调用的上层，有些库函数与系统调用是无关的（math.h）所谓原语，是操作系统内核中，由若干条指令构成、用于完成一个特定的功能的一个过程，该过程在执行时是不可中断的。微内核系统（不含LINUX）•优点•1.提高系统可扩展性•2.提高系统可靠性•3.可移植性•4.提供了对分布式系统的支持•5.融入了面向对象技术•缺点：运行效率低•硬中断：由与系统相连的外设(比如网卡、硬盘)自动产生的。主要是用来通知操作系统系统外设状态的变化•微内核中断和陷入处理（软中断）•将与硬件紧密相关的一小部分放在微内核中处理，微内核所做的就只是前期处理，将消息发给服务器由服务器再进行后期处理，因此微内核可以做的很小。进程的顺序执行•顺序执行（适合直接访问）：例如输入与打印，必须按顺序•前趋图：有向无环图进程由创建而产生，由调度而执行，由撤销而消亡进程的并发执行•程序的并发执行：多道程序可同时进行，但对于每一道程序而言是顺序执行。•程序并发执行的特征：•1.间断性：一个任务可能需要等待它的前驱任务完成才能继续执行，产生等待。•2.失去封闭性：多个程序共享系统中资源，这些资源将由多个程序来改变。•3.不可再现性：由于失去封闭性，输入的结果与