计算机操作系统第四版期末复习知识点汇总附习题(共81页).docx

《计算机操作系统第四版期末复习知识点汇总附习题(共81页).docx》由会员分享，可在线阅读，更多相关《计算机操作系统第四版期末复习知识点汇总附习题(共81页).docx（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上第一章 引论为什么发明计算机系统：方便、有效、可扩充、开放计算机系统作用：做接口、管理资源、资源的抽象发展计算机系统的动力：提高利用率、更加方便、应用.体系.硬件更新都要跟上计算机系统发展史一、无操作系统（一）人工操作：单用户、CPU. 内存长期空闲（二）脱机输入/输出（OFF-LINE I/0）：装好卡片再上机。节约CPU空闲时间、提高I/O速度二、单道批操作系统描述：有个监督程序将磁带上的作业调入计算机缺点：I/O太慢，CPU太快三、多道批操作系统描述：A在I/0，B趁机CPU优点：肯定提高资源利用率、系统吞吐量变大缺点：每个程序都要很久才处理完（作业要排队）、无

2、交互能力未解难题：内存、处理机争用、I/O设备、文件的组织和管理、作业管理、用户和系统的接口四、分时系统描述：解决人机交互问题优点：终于有人机交互、多用户共享主机实际问题：由于多用户，所以要有“多路卡”、作业直接入内存、有个“时间片”调度作业特征：多路、独立、及时（用户可接受）、交互五、实时系统描述：工业（武器）控制系统、信息查询系统、多媒体系统、嵌入式系统类型1：周期性实时：真的很周期；非周期性实时：有开始截止时间和完成截止时间类型2：硬实时：工业、武器系统；软实时：信息查询系统和多媒体系统与分时系统比较： 多路、独立、及时（毫秒级）、交互、可靠六、微机时代（一）单用户单任务：8位机的CP/

3、M、16位机的MS-DOS（二）单用户多任务：目前的32位系统，如Windows（三）多用户多任务：UNIX、Solaris、Linux操作系统共同特性：一、并发（一）并发和并行宏观上一样，并发：单处理机系统，微观上交替运行并行：多处理机系统，微观上同时运行（二）引入进程进程：在系统中能独立运行并作为资源分配的基本单位，由机器指令、数据和堆栈等组成，能独立运行的活动实体特点：用进程就可以并发执行了二、共享（一）互斥共享方式例子：临界资源，打印机、磁带机描述：你要先申请才能获得资源（二）同时访问方式描述：微观上还是并发例子：多用户磁盘设备条件：系统允许进程并发、系统能有效管理资源三、虚拟（一）时

4、分复用技术（利用空闲时间服务其他用户）虚拟处理机技术：分身之术虚拟设备：又是分身之术，骗用户以为有专人服务时分复用：速度：1/N（二）空分复用技术描述：将程序、电话线分成若干部分，然后各部分分时进入内存运行空分复用：空间：1/N四、异步描述：因为要并发，所以需要一个机制调度进程操作系统主要功能一、处理机管理功能（一）进程控制描述：要并发，就要进程、要进程，就要管理（二）进程同步进程互斥方式：临界资源要互斥进程同步方式：合作完成共同任务，同步机构要协调先后次序（信号量控制）（三）进程通信描述：对合作进程而言，需要交换信息。当他们处于同一计算机系统时，通常采用直接通信的方式。例子：输入进程、计算进

5、程、打印进程，需要信息交换（四）调度作业调度：选择作业、建立进程、分配资源、插入就绪队列进程调度：从就绪队列中选出进程，分配CPU二、存储器管理功能（一）内存分配任务：分配空间、减少碎片、追加内存空间方式：静态分配，装入内存时确定，不允许追加、不允许移动；动态分配，允许追加、允许移动（二）内存保护任务1：每道程序只在自己的内存空间运行，互不干扰任务2：不允许用户程序访问操作系统程序和数据、也不允许用户程序转移到非共享的其他用户程序中执行（三）地址映射任务：存储器要负责地址映射，在硬件支持下完成（四）内存扩充描述：用虚拟存储技术，从逻辑上扩充内存容量任务1：请求-调入功能任务2：置换功能三、设备

6、管理功能任务1：完成用户进程的I/O请求：分配I/O设备，完成I/O操作任务2：提高CPU和I/O利用率：提高I/O速度，方便用户使用I/O设备（一）缓冲管理描述：在内存中设置缓冲区（CPU高速性和I/O低速性）例子：单缓冲机制、双向同时传送数据的双缓冲机制、多个设备共同使用的公用“缓冲池”机制（二）设备分配描述：在系统中设置“设备控制表”、“控制器控制表”等数据结构，用于记录设备和控制器等标识符和状态。根据表就知道指定设备当前是否可用、忙碌。分配时，针对不同设备要有不同“分配方式”，对独占设备还要考虑分配后是否安全（三）设备处理描述：CPU向设备控制器发出I/O命令，要求完成I/O操作、反之

7、，CPU接收控制器发出的中断请求，并响应.处理四、文件管理功能描述：管理用户、系统文件，方便使用；保证安全性（一）文件储存空间管理背景：多用户环境下，用户自己管理文件存储，会困难和低效任务1：为每个文件分配外存空间、提高外存利用率、进而提高存取速度任务2：系统中设置数据结构，记录文件存储空间使用情况，以供分配时参考任务3：分配和回收（二）目录管理任务1：为每个文件建立目录项，包括文件名、属性、物理位置等，以实现按名存取任务2：实现文件共享。任务3：提供目录查询手段（三）文件读/写管理和保护文件读/写管理：根据用户请求，从外存中读取数据，或将数据写入外存文件保护：防止未经核准的用户存取文件、防止

8、冒名顶替存取文件、防止以不正确方式使用文件五、操作系统与用户之间的接口（一）用户接口描述：方便用户直接.间接控制自己的作业联机用户接口：等待用户键入命令脱机用户接口：一开始就提供作业说明书，直到作业结束语句图形用户接口：移动鼠标选择菜单项（二）程序接口描述：旧系统用汇编语言写，所以只有汇编语言的才能直接使用系统调用；如果是高级语言，就用一一对应的库函数六、现代操作系统的新功能（一）系统安全描述：确保存储和传送数据的保密性、完整性和系统可用性，要用几种技术技术：认证技术、密码技术、访问控制技术、反病毒技术（二）网络的功能和服务功能：网络通信、资源管理、应用互操作（三）支持多媒体功能：接纳控制功能

9、、实时调度、多媒体文件的存储OS结构设计一、传统操作系统结构（一）无结构操作系统又名：整体系统结构（二）模块化结构OS基本概念：又名：模块-接口法描述：有模块、子模块、接口模块独立性：标准：内聚性越高，模块独立性越高、耦合度越低，模块独立性越高优点：提高设计正确性.可理解性和可维护性、增强可适应性、加快加速过程缺点：接口难以满足需求、无序（三）分层式结构OS基本概念：有序分层，自底向上法铺设中间层优点：易保证系统正确性、易扩充和易维护缺点：系统效率降低二、客户/服务器模式(Client/Server Model)简介（一）客户/服务器模式的由来、组成和类型组成：客户机、服务器、网络系统（二）客

10、户/服务器之间的交互描述：客户发送请求消息、服务器接收消息、服务器回送消息、客户机接收消息（三）客户/服务器模式的优点描述：数据分布处理和存储、便于集中管理、灵活性和可扩充性、易于改编应用软件三、面向对象的程序设计（一）OOP的基本概念描述：抽象，具体事物为对象对象：封装好对象类：创建多个相似对象继承：继承父类，增加部分（二）OOP的优点描述：“重用”提高产品质量和生产率、使系统具有更好的易修改性和易扩展性、易于保证系统“正确性”和“可靠性”四、微内核OS结构描述：支持多处理机例子：卡内基梅隆的Mach OS、Windows 2000/XP（一）基本概念描述：足够小的内核、基于C/S模式、应用

11、“机制与策略分离”原理、采用OOP技术（二）基本功能描述：进程管理、低级存储器管理、中断和陷入处理（三）优点描述：提高可扩展性、增强可靠性、可移植性强、提供对分布式系统的支持、融入OOP（四）缺点描述：效率降低第二章 进程描述与控制前趋图与程序执行一、前趋图与程序执行（一）前趋图描述：前一个做完，才到后一个做、禁止循环二、顺序执行描述：一个跟一个特征：顺序、封闭（独占资源）、可再现三、并发执行描述：互不依赖才能并发执行特征：间断、失去封闭、不可再现进程的描述一、进程的定义和特征进程实体：程序段、相关的数据段和PCB定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位特征：动态

12、、并发、独立、异步二、进程的基本状态及转换进程的三基态：就绪（只欠CPU）、执行、阻塞（因故无法继续执行）三态转换：如图新增两态：创建状态、终止状态五态转换：如图三、挂起操作和进程状态的转换挂起原因：终端用户需要、父进程请求、负荷调节、操作系统需要引入挂起后的三态转换：如图引入挂起后的五态转换：如图四、进程管理中的数据结构用于管理控制的数据结构：每个资源、进程都有一个数据结构用于表征实体资源信息表、进程信息表，包括：标识、描述、状态等和一批指针，通过指针能够链接成队列，便于查找分类：内存表、设备表、文件表、进程表PCB的作用：作为独立运行基本单位的标识、能实现间断运行、提供进程管理所需的信息、

13、实现与其他进程的同步与通信PCB的信息：进程标识符（内外部）、处理机状态、进程调度信息、进程控制信息PCB组织方式：线性方式、链接方式、索引方式进程控制一、操作系统内核描述：常驻内存的模块目的：保护软件、提高OS运行效率系统态、管态、内核态：高特权、访问所有寄存器.存储区、传统OS都在系统态运行用户态、目态：低特权、执行指定指令.访问指定寄存器和存储区支撑功能：中断处理、时钟管理、原语操作资源管理功能：进程管理、存储器管理、设备管理二、进程的创建层次结构：UNIX有父子关系，Windows只有控制与被控制关系进程图：描述家庭关系的图引起创建进程的事件：用户登录、作业调度、提供服务（譬如打印）、

14、应用请求进程的创建：申请空白PCB、分配物理.逻辑资源、初始化PCB、如果能插入就绪，就插三、进程的终止引起进程终止的事件：正常结束、异常结束、外界干预进程的终止过程：根据标识符、终止执行.立即调度、子孙终止、资源归还、移出队列四、进程的阻塞与唤醒引起进程阻塞和唤醒的事件：向系统请求共享资源失败、等待某操作完成、新数据尚未到达、等待新任务到达进行阻塞过程：发生上述的某事件，就进入block过程，主动将状态改为阻塞，PCB插入阻塞队列（分类插入），处理机分配给另一就绪进程，切换，并保留被阻塞进程的处理机状态进程唤醒过程：由释放资源的进程调用wakeup原语，即移出阻塞队列，合作/相关的进程中安排

15、wakeup五、进程的挂起与激活进程的挂起：活动静止，suspend原语进程正在执行，就转向调度程序重新调度进程的激活过程：从外存调入active原语到内存，检查进程现行状态，静止活动抢占调度策略：静止就绪进程就绪队列，比较当前进程优先度，有机会立即剥夺当前进程运行进程同步描述：能够并发、改善利用率、提高吞吐量、但使系统复杂一、进程同步的基本概念制约关系：间接相互制约关系、直接相互制约关系间接相互制约关系：互斥共享直接相互制约关系：合作共享，异步性要做好临界资源：生产者-消费者问题、临界区、：进入区、临界区、退出区、剩余区同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待二、硬件同步

16、机制关中断：缺点多：滥用关中断.造成严重后果、关中断时间过长、不适用于多CPU系统（因为一个处理器关中断并不能防止进程在其他处理器上执行相同的临界段代码）Test-and-Set：不断测试lock，如果是FALSE，就进入临界区，并lock = TRUE；否则测试到TS(s) = TRUESwap指令：一直等，直到key = TRUE但以上都不符合“让权等待”原则三、信号量机制整形信号量：S0，就一直等，直到释放互斥资源记录型信号量：整形信号量不符合“让权等待”原则。如果有资源，就分配，如果无，就插入阻塞队列；释放资源，如果有等待，就激活AND型信号量：一口气全分配信号量集：有多个信号量（S信

17、号量,至少要t个,每次分配d个）四、信号量的应用利用信号量实现进程互斥：mutex = ( -1, 0, 1）= （无，一临一阻队， 一临一信队）利用信号量实现前趋关系：需要的信号量被占用了，就这样实现五、管程机制描述：为解决信号量机制分散、容易死锁的问题，发明新同步工具管程定义：定义一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据组成：管程名称、数据结构的说明、对数据结构进行操作的过程、初始化的语句特性：模块化、抽象数据类型、信息掩蔽管程与进程不同：都有数据结构，一个公.一个私、管程操作同步.初始化.进程顺序执行、管程为解决互斥资源.进程实现

18、并发性、进程调用管程.进程主动.管程被动、管程不能并发.进程能并发、管程是OS的一个资源管理模块.进程有动态性条件变量：增加一个条件变量，万一发生意外，在管程中被挂起或被阻塞，下一个进程都可以继续执行经典进程的同步问题一、生产者-消费者问题记录型信号量解决：如果缓冲区空，而且能够获取信号量，就投放产品；如果缓冲区有产品，而且能够获取信号量，就消费AND信号量解决：一口气全分配管程解决：利用管程只有一个进程能够使用的属性二、哲学家进餐问题记录型信号量解决：先拿左.后那右、先放左.后放右解决死锁：最多4人取筷子、先检查.有左右筷子才能取、奇左右.偶右左AND信号量解决：一口气全分配三、读者-写者问

19、题描述：可以多读一、一旦开始写.就不能读或写记录型信号量解决：读操作：等rmutex就是为了改readcount无人读？看看是否在写.等wmutexreadcount+自增完成.rmutex还你读读读等rmutex为了自减readcount无人读？可以写了.还你wmutex写操作：等wmutex.即无读无写写完.还你wmutex利用信号量集机制：读：限制reader个数如果mx是1.就读最后释放一个reader个数写：如果mx是1.并且读者数为0.就写写完释放mx进程通信一、进程通信类型共享存储器系统：某些数据结构和共享存储区、管道通信系统、消息传递系统、C-S系统二、消息传递通信的实现方式（

20、一）直接消息传递系统1.直接通信原语：对称寻址方式、非对称寻址方式2.消息格式：较短的减少系统处理和存储的开销、较长可以方便3.进程同步方式：发塞收塞（进程间紧密同步.无缓冲）、发通收塞（平常状态）、发通收通（发生某事件无法继续运行）、（无发塞收通）4.通信链路：用“建立连接”原语建立通信链路.用完拆、用“发送命令”原语建立链路，还分单向和双向（二）信箱通信（间接）1.定义：是数据结构.分信箱头和信箱体2.原语：创建和撤销. 发送和接收3.类型：私用、公用（操作系统创建）、共享（进程创建）4.进程之间的关系：一对一、多对一、一对多、多对多三、直接消息传递系统实例消息缓冲队列通信机制中的数据结构

21、：利用数据结构式消息缓冲区、在PCB增加有关通信的数据项原语：设置发送区、申请PCB(B)的缓冲区i、复制到缓冲区、插入消息队列、移出消息队列、复制到接收区、释放缓冲区线程的基本概念描述：就是为了提高程序并发执行的程度一、线程的引入进程的两个基本属性：进程是一个可拥有资源的独立单位、进程同时是一个可独立调度和分派的基本单位进程并发执行所需的时空开销：创建进程、撤销进程、进程切换线程作为调度和分派的基本单位：线程轻装上阵二、线程与进程比较调度的基本单位：线程是调度和分派的基本单位、跨进程，会切换进程并发性：线程的合作.能够并发拥有资源：有TCB.但只是必不可少、保证独立运行的资源独立性：同一进程

22、的不同线程共享进程的内存地址空间和资源系统开销：因为轻装.所以减少开销、提升速度支持多处理机系统：对多线程进程，多个线程可以分配到多个处理机上三、线程的状态和线程控制块线程运行的三个状态：和进程一样线程控制块TCB：标识符、一组寄存器、运行状态、优先级、线程专有存储区、信号屏蔽、堆栈指针多线程OS中的进程属性：进程是可拥有资源的基本单位、多个线程可并发执行、进程已不是可执行的实体线程的实现一、线程的实现方式内核支持线程KLT：优点：内核调度同一进程多个线程并行执行、一个线程阻塞.其他线程占有处理机、支持小数据结构和堆栈.切换较快开销小、内核本身采用多线程技术.提高系统执行速度和效率用户级线程U

23、LT：优点：无需内核.节省模式切换的开销、调度算法进程专用、与OS无关.甚至可以在操作系统平台实现 缺点：一个线程阻塞.同进程的其他线程都会塞、只有一个CPU.只有一个线程能执行、按进程分配.不公平组合方式：多对一模型：优点：开销小、缺点：一塞进程全塞、只有一线程访问内核、多线程不能同时在多个处理机上运行一对一模型：一个用户级线程映射到一个内核支持线程多对多模型：一对一和多对一的结合二、线程的实现内核支持线程的实现：创建线程、保存信息、调度和切换线程、撤销线程、回收资源用户级线程的实现：运行时系统：用于管理和控制线程的函数的集合，这些函数驻留用户空间.并作为用户级线程与内核之间的接口内核控制线

24、程：连接到LWP，连接到LWP的线程才能与内核通信三、线程的创建和终止线程的创建：初始化线程、创建后返回线程标识符线程的终止：终止线程用函数或系统调用终止操作.但有些线程被建立就会一直执行。大多数OS，线程被中止后并不立即释放所占资源，只有“其他线程”执行分离函数才会分离资源，才能被其他线程利用。虽然未释放的资源也可以被其他线程使用，但要有个“等待线程终止”的连接命令作保险.否则一直阻塞第三章 处理机调度与死锁处理机调度的层次和调度算法的目标描述：作业可能要经历多级处理机调度一、处理机调度层次（一）高级调度（长程调度/作业调度）对象是作业、决定将外存中处于后备队列的作业调入内存.创建进程和分配

25、资源.并放入就绪队列、主要存在于多道批处理系统，分时和实时系统不设置高级调度（二）低级调度（进程调度/短程调度）对象是进程（/内核级线程）、决定就绪队列哪个进程获得处理机、多道批.分时和实时都要配置（三）中级调度（内存调度）（存储器的对换功能）对象是暂时不能运行的进程、把这些进程调到外存.设为挂起状态、一有条件.稍微有空就变为就绪状态分级按运行频率划分二、处理机调度算法的目标（一）共同目标提高资源利用率、公平、平衡、策略强制执行（二）批处理系统目标处理机利用率高、平均周转时间短、系统吞吐量高（三）分时系统目标响应时间快、均衡性（四）实时系统目标截止时间保证、可预测性作业与作业调度一、批处理系统

26、中的作业（一）作业和作业步作业：包括程序.数据和作业说明书、在批处理系统.作业是基本单位从外存调入内存作业步：独立步骤（二）作业控制块（JCB）包括作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等流程：进入系统创建JCB根据类型放到后备队列等待调度入内存根据JCB和作业说明书控制完成回收资源.撤销JCB（三）作业运行的三个阶段和三种状态收容阶段-后备状态、运行阶段-运行状态、完成阶段-完成状态二、作业调度的主要任务也叫：接纳调度考虑：接纳多少作业、接纳哪些作业三、先来先服务FCFS和短作业优先SJF调度算法（一）先来先服务FCFS就这样.完成或阻塞才分配到其

27、他进程、实际中和其他算法结合使用有利于长作业（进程），不利于短作业（进程）（二）短作业优先SJF实际用得多、要预知作业运行时间、长作业、紧迫作业不利、无人机交互四、优先级调度算法和高响应比优先调度算法（一）优先级调度算法外部赋予作业优先级（二）高响应比优先调度算法集SJF.FCFS的优点.兼顾长作业、但要做相应比计算.增加系统开销（Exp.做过类似）进程调度一、进程调度的任务、机制和方式（一）进程调度的任务保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程（二）进程调度机制排队器：插入就绪队列分配器：从就绪队列取出.分配处理机上下文切换器：保存、装入新的CPU现场信息等内容（三）进程

28、调度方式非抢占方式：只有完成或因某事无法继续运行、I/O、执行了原语操作如block，才会引起进程调度优点：简单、开销小、适用大多数批处理系统抢占方式：对分时系统而言.有人机交互、对实时系统而言.能满足任务需求主要原则：优先权原则、短进程优先原则、时间片原则二、轮转调度算法（一）轮转法（RR）的基本原理按FCFS策略排成就绪队列，每隔一定时间就产生一次中断（二）进程切换时机时间片未用完就完成：马上调度队首进程.启动新时间片时间片完还没完成：中断.进程被调到就绪队列队尾（三）时间片大小的确定太短有利于短进程、太长退化为FCFS算法.要计算平均周转时间（带权周转时间）三、优先级调度算法（一）优先级

29、调度算法的类型非抢占式和抢占式（二）优先级的类型确定优先级的依据：静态优先级：进程类型（系统进程优先权高于用户进程优先权）、进程对资源的需求（少则优先）、用户需求（紧迫程度、花费）动态优先级：先赋予优先级，随着进程推进或等待时间增加而改变四、多队列调度算法将一条就绪队列拆分成多条，各有各调度算法五、多级反馈队列调度算法（一）调度机制多条就绪队列、队列内使用FCFS算法.一个时间片未完成就放到下一个队列的末尾.最后一个队列用RR方式、按队列优先级调度.前队列空才到本队列运行（二）调度算法的性能终端型用户、短批处理作业用户、长批处理作业用户六、基于公平原则调度算法（一）保证调度算法保证处理机公平分

30、配功能：跟踪进程已经执行的处理时间、该时间除以n、计算实际处理时间和应获得时间之比、比较比率、比率最低的获得处理机（二）公平分享调度算法考虑多用户实时调度描述：实时系统有两种实时任务HRT和SRT一、实现实时调度的基本条件（一）提供必要信息就绪时间、开始截止和完成截止时间、处理时间、资源要求、优先级（二）系统处理能力强（处理时间i/周期时间i）总和 1. 未考虑任务切换花费的时间还应该留有余地提高系统处理能力的途径：单处理机系统增强处理能力.显著减少每个任务的处理时间、多处理机系统.就变成（处理时间i/周期时间i）总和 N（三）采用抢占式调度机制执行完关键程序和临界区后，能及时将自己阻塞起来，

31、以释放处理机（四）具有快速切换机制对中断的快速响应能力、快速的任务分派能力二、实时调度算法的分类根据任务性质：H/S根据调度方式：非抢占式/抢占式（一）非抢占式调度算法轮转、优先调度，不适合实时系统。进程自动放弃处理机，才进行调度。（二）抢占式调度算法基于时钟中断的抢占式优先级调度算法：等待时钟中断发生才剥夺当前任务的执行立即抢占优先调度算法：好快好快.只要任务未处于临界区.就立即剥夺当前任务执行优先权原则、短作业（进程）优先原则、时间片原则。三、最早截止时间优先EDF算法非抢占式调度方式用于非周期实时任务：开始截止时间早的排前抢占式调度方式用于周期实时任务：最早截止时间优先算法四、最低松弛度

32、优先LLF算法 紧急程度越高，优先级越高。五、优先级倒置（一）优先级倒置的形成（二）优先级倒置的解决方法继承动态优先级的方法：P3继承P1的优先级.一方面避免P2抢占处理机、另一方面释放mutex资源死锁概述一、资源问题指互斥资源、不可被抢占的资源（一）可重用性资源和消耗性资源可重用性资源：一个只能分配给一个进程使用、顺序为请求.使用.释放、数目相对固定.运行期间不能创建或删除可消耗性资源：在进程运行中数目不断变化.可为0、可以不断创建.放入缓冲区、可以由进程创建.使用并不再返回资源类（二）可抢占性资源和不可抢占性资源可抢占性资源：可以被其他进程抢占.如CPU和主存不可抢占性资源：一旦分配给进

33、程就不能强制收回.要做到底二、计算机系统中的死锁（一）竞争不可抢占性资源引起死锁我要你的，你要我的，形成环路，死锁（二）竞争可消耗资源引起死锁譬如消息通信机制.先读后写.就会死锁（三）进程推进顺序不当引起死锁竞争不可抢占性资源引起死锁的翻版.多画了一个图三、死锁的定义、必要条件和处理方法（一）死锁的定义这组死锁进程都在等其他进程释放所占资源（二）产生死锁的必要条件互斥条件：一段时间只被一个进程占用请求和保持条件：进程已经保持至少一个条件.但有提出新资源请求不可抢占条件：只能在进程用完才能释放循环等待条件：存在循环链（三）处理死锁的方法预防死锁：设置限制条件.破坏产生死锁四个必要条件来预防避免死

34、锁：在资源动态分配时.用防止系统进入不安全状态检测死锁：通过检测机构及时检测死锁.采取适当措施以解脱解除死锁：撤销进程.回收资源.分配给处于阻塞的进程防范逐渐减弱.但资源利用率提高.进程因资源因素而阻塞的频度下降预防死锁一、破坏“请求和保持”条件保证：进程请求资源时，不持有不可抢占资源第一种协议：一次性全部申请，从而破坏“请求条件”、缺点是资源被严重浪费.进程饥饿第二种协议：先释放资源.再请求新资源二、破坏“不可抢占”条件当保持了某些不可抢占资源后.提出新资源请求不得满足.就必须释放已经保持的资源.等需要时再申请缺点：增加周转时间、增加系统开销、降低系统吞吐量三、破坏“循环等待”条件总有一个进

35、程占据了较高序号的资源.此后它继续申请的资源必然是空闲的避免死锁一、系统安全状态（一）安全状态计算一个资源分配的安全性.如果分配不会导致不安全状态.才可将资源分配给进程（二）安全状态之例（三）由安全状态向不安全状态的转换二、利用银行家算法避免死锁（一）银行家算法中的数据结构Availalbe、Max、Allocation、Need（二）银行家算法睇wiki“银行家算法”条目声明：Request是请求向量Request Need, 否则出错Request Available, 否则P等待系统试探分配资源给P, 并执行Availalbe -= Requeset; Allocation+= Requ

36、est; Need -= Request死锁的检测与解除一、死锁的检测（一）资源分配图圆圈代表进程、方格代表一类资源、边代表资源分配（二）死锁的定理简化资源分配图.如果不能完全简化.就会死锁（三）死锁检测中的数据结构类似于银行家算法？二、死锁的解除常用两种方法：抢占资源、终止/撤销进程（一）终止进程的方法终止所有死锁进程：会功亏一篑逐个终止进程：找到代价最小.考虑优先级、已执行时间.还需的时间、已用资源、交互式还是批处理式（二）付出代价最小的死锁解除算法很不实际第四章 存储器管理存储器的层次结构一、多层结构的存储器系统CPU寄存器；高速缓存Cache、主存储器RAM、磁盘缓存；固定磁盘、可移动

37、存储介质二、可执行存储器就是CPU寄存器和主存.访问很快二、主存储器与寄存器（一）主存储器又叫主存or内存.相比CPU执行速度.它还是很慢.所以引入寄存器和高速缓存（二）寄存器完全与CPU协同工作.但好贵三、高速缓存和磁盘缓存（一）高速缓存备份主存中较常用的数据.以减少CPU对主存储器的访问次数（二）磁盘缓存因为磁盘I/O速度远低于主存访问速度.所以设置磁盘缓存来暂存频繁使用的一部分磁盘数据和信息程序的装入和链接用户程序要在OS中运行.要先装入内存.再转换为一个可执行程序：编译、链接、装入一、程序的装入（一）绝对装入方式当OS很小.且仅能运行单道程序时.完全有可能知道程序驻留在内存的位置.那么

38、就可以产生绝对地址的目标代码（二）可重定位装入方式（静态重定位）多道程序下.逻辑地址和物理地址不同.要加上起始地址.但只在进程装入时一次完成.故称为静态重定位.可装到内存任何允许位置（三）动态运行时的装入方式需要重定位寄存器，运行时允许移动二、程序的链接（一）静态链接方式要解决：对相对地址进行修改（子程序的相对地址）、变换外部调用符号（生成可执行文件后不再拆开.又叫静态链接方式）（二）装入时动态链接便于修改和更新（各模块分开存放）、便于实现对目标模块的共享（静态每个应用模块必有目标模块的拷贝.无法共享.但动态可以一个目标链接多个应用模块）（三）运行时动态链接运行时发现没有.就由OS去找这个模块

39、内功加快程序装入过程和节约大量内存空间连续分配存储管理方式一、单一连续分配分系统区和用户区.单用户.单任务操作系统二、固定分区分配划分分区的方法：大小相等（一台计算机控制多台相同冶炼炉）和大小不等内存分配：通常按大小排队.建立分区使用表.如果找不到大小足够的分区.就拒绝分配内存三、动态分区分配动态分区分配中的数据结构：空闲分区表、空闲分区链动态分区分配算法：之后介绍4种分配算法和3中索引搜索算法分区分配操作：分配内存、回收内存四、基于顺序搜索的动态分区分配算法（不太大系统）首次适应算法（FF）、循环首次适应算法(NF)、最佳适应算法(BF)、最坏适应算法(WF)五、基于索引搜索的动态分区分配算

40、法(大、中型系统)快速适应算法（以空间换时间）、伙伴系统（合并回收与均匀分配）、哈希算法六、动态可重定位分区分配紧凑、动态重定位、动态重定位分区分配算法对换一、多道程序环境下的对换技术（一）对换的引入避免内存全部被阻塞.外存却有很多作业无法进入内存（二）对换的类型整体对换（进程对换）、页面对换（部分对换）支持虚拟存储系统二、对换空间的管理（一）对换空间管理的主要目标文件区管理主要目标：先提高文件存储空间的利用率.离散分配对换空间管理的主要目标：先提高换入换出的速度，连续分配方式（二）对换区空闲盘块管理中的数据结构与内存的相似（三）对换空间的分配与回收与内存分配和回收雷同三、进程的换出与换入（一

41、）进程的换出选择被换出的进程：阻塞或睡眠状态、优先级最低、内存驻留时间进程换出过程（二）进程的换入如果发现许多进程运行时缺页且内存紧张.才启动对换程序.将部分进程调至外存如果缺页率明显减少.系统吞吐量已下降.则可以暂停运行对换程序分页存储管理方式其实分三种：分页、分段、段页式一、分页存储管理的基本方法（一）页面和物理块页面：页号页面大小：太小.进程占用较多页面、太多.碎片多、适中.1kB8kB（二）地址结构页号：P页内地址（偏移量）：d两个都有公式计算（三）页表从页号到物理块号的映射二、地址变换机构（一）基本的地址变换机构如果发现页号页表长度.就引发越界中断；否则页表始址+页号*页表项长度=物

42、理块号（二）具有快表的地址变换机构有个快表在高速缓存三、访问内存的有效时间EAT = t +t = 2t（内存）EAT = a*+(t+)(1-a)+t = 2t+ - t* a（快表）四、两级和多级页表（一）两级页表（二）多级页表五、反置页表（一）反置页表的引入（二）地址变换分段存储管理方式一、分段存储管理的基本方法（一）方便编程逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的（二）信息共享段是信息的逻辑单位.简化共享过程（三）信息保护就是可以加个标识.不允许读写（四）动态增长可以解决这个问题（五）动态链接4.2.2二、分段系统的基本原理（一）分段每个段有一个段号，连续的分区（二）段表

43、实现从逻辑段到物理内存区的映射，段长和基址（三）地址变换机构段表项数目比页表项数目少.其所需的联想存储器相对较少.减少存取数据的时间（四）分页和分段的主要区别页是信息的物理单位.分页是系统管理上的需要while 段是存储管理方式中的逻辑单位.分段目的在于更好满足用户的需要页大小固定.段大小不固定分页的用户程序地址是一维的.分段是二维的三、信息共享（一）分页系统中对程序和数据的共享每个进程都有页表.也都指向相同的物理块号（二）分段系统中的程序和数据的共享可重入代码是一种不允许任何进程对它进行修改的代码配以局部数据区.把执行中可能改变的部分拷贝到该数据区.这样执行时只需对该数据区中的内容修改即可四

44、、段页式存储管理方式分段分页.每段一个段名段号.比较.加法算段表段号得到页号.(比较).加法算页表页号得到物理块号.加页内地址得物理地址第五章 虚拟存储器出现问题：作业很大、大量作业要求运行虚拟存储器概述一、常规存储管理方式的特征和局部性原理（一）常规存储管理方式的特征传统：一次性、驻留性（二）局部性原理绝大部分顺序执行、调用进度不超过5、循环结构由少数指令构成.但多次执行、多对数据结构的处理.这些处理局限于很小的部分时间、空间局限性（三）虚拟存储器的基本工作情况将少数页面或段先装入内存即可运行二、虚拟存储器的定义和特征（一）虚拟存储器的定义有请求调入功能和置换功能.能逻辑上对内存内容加以扩充的一种存储器系统（二）虚拟存储器的特征多次性、对换性、虚拟性三、虚拟存储器的实现方式（一）分页请求系统硬件支持：请求分页的页表机制、缺页中断机制、地址变换机制实现请求分页的软件（二）请求分段系