2023年计算机操作系统第四版期末复习知识点归纳总结超详细知识汇总全面汇总归纳附习题.pdf

第一章 引论 为什么发明电脑系统：方便、有效、可扩充、开放 电脑系统作用：做接口、管理资源、资源的抽象 发展电脑系统的动力：提高利用率、更加方便、应用.体系.硬件更新都要跟上 电脑系统发展史 一、无操作系统 一人工操作：单用户、CPU.内存长期空闲 二脱机输入/输出OFF-LINE I/0：装好卡片再上机。节约 CPU 空闲时间、提高I/O 速度 二、单道批操作系统 描述：有个监督程序将磁带上的作业调入电脑 缺点：I/O 太慢，CPU 太快 三、多道批操作系统 描述：A 在 I/0，B 趁机 CPU 优点：肯定提高资源利用率、系统吞吐量变大 缺点：每个程序都要很久才处理完作业要排队、无交互能力 未解难题：内存、处理机争用、I/O 设备、文件的组织和管理、作业管理、用户和系统的接口 四、分时系统 描述：解决人机交互问题 优点：终于有人机交互、多用户共享主机 实际问题：由于多用户，所以要有“多路卡”、作业直接入内存、有个“时间片”调度作业 特征：多路、独立、及时用户可接受、交互 五、实时系统 描述：工业武器控制系统、信息查询系统、多媒体系统、嵌入式系统 类型 1：周期性实时：真的很周期；非周期性实时：有开始截止时间和完成截止时间 类型 2：硬实时：工业、武器系统；软实时：信息查询系统和多媒体系统 与分时系统比较：多路、独立、及时毫秒级、交互、可靠 六、微机时代 一单用户单任务：8 位机的 CP/M、16 位机的 MS-DOS 二单用户多任务：目前的 32 位系统，如 Windows 三多用户多任务：UNIX、Solaris、Linux 操作系统共同特性：一、并发 一并发和并行宏观上一样，并发：单处理机系统，微观上交替运行 并行：多处理机系统，微观上同时运行 二引入进程 进程：在系统中能独立运行并作为资源分配的基本单位，由机器指令、数据和堆栈等组成，能独立运行的活动实体 特点：用进程就可以并发执行了 二、共享 一互斥共享方式 例子：临界资源，打印机、磁带机 描述：你要先申请才能获得资源 二同时访问方式 描述：微观上还是并发 例子：多用户磁盘设备 条件：系统允许进程并发、系统能有效管理资源 三、虚拟 一时分复用技术利用空闲时间服务其他用户 虚拟处理机技术：分身之术 虚拟设备：又是分身之术，骗用户以为有专人服务 时分复用：速度：1/N 二空分复用技术 描述：将程序、线分成假设干部分，然后各部分分时进入内存运行 空分复用：空间：1/N 四、异步 描述：因为要并发，所以需要一个机制调度进程 操作系统主要功能 一、处理机管理功能 一进程控制 描述：要并发，就要进程、要进程，就要管理 二进程同步 进程互斥方式：临界资源要互斥 进程同步方式：合作完成共同任务，同步机构要协调先后次序信号量控制 三进程通信 描述：对合作进程而言，需要交换信息。当他们处于同一电脑系统时，通常采用直接通信的方式。例子：输入进程、计算进程、打印进程，需要信息交换 四调度 作业调度：选择作业、建立进程、分配资源、插入就绪队列 进程调度：从就绪队列中选出进程，分配 CPU 二、存储器管理功能 一内存分配 任务：分配空间、减少碎片、追加内存空间 方式：静态分配，装入内存时确定，不允许追加、不允许移动；动态分配，允许追加、允许移动 二内存保护 任务 1：每道程序只在自己的内存空间运行，互不干扰 任务 2：不允许用户程序访问操作系统程序和数据、也不允许用户程序转移到非共享的其他用户程序中执行 三地址映射 任务：存储器要负责地址映射，在硬件支持下完成 四内存扩充 描述：用虚拟存储技术，从逻辑上扩充内存容量 任务 1：请求-调入功能 任务 2：置换功能 三、设备管理功能 任务 1：完成用户进程的 I/O 请求：分配 I/O 设备，完成 I/O 操作 任务 2：提高 CPU 和 I/O 利用率：提高 I/O 速度，方便用户使用 I/O 设备 一缓冲管理 描述：在内存中设置缓冲区CPU 高速性和 I/O 低速性 例子：单缓冲机制、双向同时传送数据的双缓冲机制、多个设备共同使用的公用“缓冲池”机制 二设备分配 描述：在系统中设置“设备控制表”、“控制器控制表”等数据结构，用于记录设备和控制器等标识符和状态。根据表就知道指定设备当前是否可用、忙碌。分配时，针对不同设备要有不同“分配方式”，对独占设备还要考虑分配后是否安全 三设备处理 描述：CPU 向设备控制器发出 I/O 命令，要求完成 I/O 操作、反之，CPU 接收控制器发出的中断请求，并响应.处理 四、文件管理功能 描述：管理用户、系统文件，方便使用；保证安全性 一文件储存空间管理 背景：多用户环境下，用户自己管理文件存储，会困难和低效 任务 1：为每个文件分配外存空间、提高外存利用率、进而提高存取速度 任务 2：系统中设置数据结构，记录文件存储空间使用情况，以供分配时参考 任务 3：分配和回收 二目录管理 任务 1：为每个文件建立目录项，包括文件名、属性、物理位置等，以实现按名存取 任务 2：实现文件共享。任务 3：提供目录查询手段 三文件读/写管理和保护 文件读/写管理：根据用户请求，从外存中读取数据，或将数据写入外存 文件保护：防止未经核准的用户存取文件、防止冒名顶替存取文件、防止以不正确方式使用文件 五、操作系统与用户之间的接口 一用户接口 描述：方便用户直接.间接控制自己的作业 联机用户接口：等待用户键入命令 脱机用户接口：一开始就提供作业说明书，直到作业结束语句 图形用户接口：移动鼠标选择菜单项 二程序接口 描述：旧系统用汇编语言写，所以只有汇编语言的才能直接使用系统调用；如果是高级语言，就用一一对应的库函数 六、现代操作系统的新功能 一系统安全 描述：确保存储和传送数据的保密性、完整性和系统可用性，要用几种技术 技术：认证技术、密码技术、访问控制技术、反病毒技术 二网络的功能和服务 功能：网络通信、资源管理、应用互操作 三支持多媒体 功能：接纳控制功能、实时调度、多媒体文件的存储 OS 结构设计 一、传统操作系统结构 一无结构操作系统 又名：整体系统结构 二模块化结构 OS 基本概念：又名：模块-接口法 描述：有模块、子模块、接口 模块独立性：标准：内聚性越高，模块独立性越高、耦合度越低，模块独立性越高 优点：提高设计正确性.可理解性和可维护性、增强可适应性、加快加速过程 缺点：接口难以满足需求、无序 三分层式结构 OS 基本概念：有序分层，自底向上法铺设中间层 优点：易保证系统正确性、易扩充和易维护 缺点：系统效率降低 二、客户/服务器模式(Client/Server Model)简介 一客户/服务器模式的由来、组成和类型 组成：客户机、服务器、网络系统 二客户/服务器之间的交互 描述：客户发送请求消息、服务器接收消息、服务器回送消息、客户机接收消息 三客户/服务器模式的优点 描述：数据分布处理和存储、便于集中管理、灵活性和可扩充性、易于改编应用软件 三、面向对象的程序设计 一OOP 的基本概念 描述：抽象，具体事物为对象 对象：封装好 对象类：创建多个相似对象 继承：继承父类，增加部分 二OOP 的优点 描述：“重用”提高产品质量和生产率、使系统具有更好的易修改性和易扩展性、易于保证系统“正确性”和“可靠性”四、微内核 OS 结构 描述：支持多处理机 例子：卡内基梅隆的 Mach OS、Windows 2000/XP 一基本概念 描述：足够小的内核、基于 C/S 模式、应用“机制与策略别离”原理、采用 OOP 技术 二基本功能 描述：进程管理、低级存储器管理、中断和陷入处理 三优点 描述：提高可扩展性、增强可靠性、可移植性强、提供对分布式系统的支持、融入 OOP 四缺点 描述：效率降低 第二章 进程描述与控制 前趋图与程序执行 一、前趋图与程序执行 一前趋图 描述：前一个做完，才到后一个做、禁止循环 二、顺序执行 描述：一个跟一个 特征：顺序、封闭独占资源、可再现 三、并发执行 描述：互不依赖才能并发执行 特征：间断、失去封闭、不可再现 进程的描述 一、进程的定义和特征 进程实体：程序段、相关的数据段和 PCB 定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位 特征：动态、并发、独立、异步 二、进程的基本状态及转换 进程的三基态：就绪只欠 CPU、执行、阻塞因故无法继续执行 三态转换：如图 新增两态：创建状态、终止状态 五态转换：如图 三、挂起操作和进程状态的转换 挂起原因：终端用户需要、父进程请求、负荷调节、操作系统需要 引入挂起后的三态转换：如图 引入挂起后的五态转换：如图 四、进程管理中的数据结构 用于管理控制的数据结构：每个资源、进程都有一个数据结构用于表征实体资源信息表、进程信息表，包括：标识、描述、状态等和一批指针，通过指针能够链接成队列，便于查找 分类：内存表、设备表、文件表、进程表 PCB 的作用：作为独立运行基本单位的标识、能实现间断运行、提供进程管理所需的信息、实现与其他进程的同步与通信 PCB 的信息：进程标识符内外部、处理机状态、进程调度信息、进程控制信息 PCB 组织方式：线性方式、链接方式、索引方式 进程控制 一、操作系统内核 描述：常驻内存的模块 目的：保护软件、提高 OS 运行效率 系统态、管态、内核态：高特权、访问所有寄存器.存储区、传统 OS 都在系统态运行 用户态、目态：低特权、执行指定指令.访问指定寄存器和存储区 支撑功能：中断处理、时钟管理、原语操作 资源管理功能：进程管理、存储器管理、设备管理 二、进程的创建 层次结构：UNIX 有父子关系，Windows只有控制与被控制关系 进程图：描述家庭关系的图 引起创建进程的事件：用户登录、作业调度、提供服务譬如打印、应用请求 进程的创建：申请空白 PCB、分配物理.逻辑资源、初始化 PCB、如果能插入就绪，就插 三、进程的终止 引起进程终止的事件：正常结束、异常结束、外界干预 进程的终止过程：根据标识符、终止执行.立即调度、子孙终止、资源归还、移出队列 四、进程的阻塞与唤醒 引起进程阻塞和唤醒的事件：向系统请求共享资源失败、等待某操作完成、新数据尚未到达、等待新任务到达 进行阻塞过程：发生上述的某事件，就进入 block 过程，主动将状态改为阻塞，PCB 插入阻塞队列分类插入，处理机分配给另一就绪进程，切换，并保留被阻塞进程的处理机状态 进程唤醒过程：由释放资源的进程调用 wakeup原语，即移出阻塞队列，合作/相关的进程中安排 wakeup 五、进程的挂起与激活 进程的挂起：活动静止，suspend原语进程正在执行，就转向调度程序重新调度 进程的激活过程：从外存调入 active 原语到内存，检查进程现行状态，静止活动 抢占调度策略：静止就绪进程就绪队列，比较当前进程优先度，有时机立即剥夺当前进程运行 进程同步 描述：能够并发、改善利用率、提高吞吐量、但使系统复杂 一、进程同步的基本概念 制约关系：间接相互制约关系、直接相互制约关系 间接相互制约关系：互斥共享 直接相互制约关系：合作共享，异步性要做好 临界资源：生产者-消费者问题、临界区、：进入区、临界区、退出区、剩余区 同步机制应遵循的规则：空闲让进、忙则等待、有限等待、让权等待 二、硬件同步机制 关中断：缺点多：滥用关中断.造成严重后果、关中断时间过长、不适用于多 CPU 系统因为一个处理器关中断并不能防止进程在其他处理器上执行相同的临界段代码 Test-and-Set：不断测试 lock，如果是 FALSE，就进入临界区，并 lock=TRUE；否则测试到 TS(s)=TRUE Swap 指令：一直等，直到 key=TRUE 但以上都不符合“让权等待”原则 三、信号量机制 整形信号量：S0，就一直等，直到释放互斥资源 记录型信号量：整形信号量不符合“让权等待”原则。如果有资源，就分配，如果无，就插入阻塞队列；释放资源，如果有等待，就激活 AND 型信号量：一口气全分配 信号量集：有多个信号量S 信号量,至少要 t 个,每次分配 d 个 四、信号量的应用 利用信号量实现进程互斥：mutex=(-1,0,1=无，一临一阻队，一临一信队 利用信号量实现前趋关系：需要的信号量被占用了，就这样实现 五、管程机制 描述：为解决信号量机制分散、容易死锁的问题，发明新同步工具管程 定义：定义一个数据结构和能为并发进程所执行在该数据结构上的一组操作，这组操作能同步进程和改变管程中的数据 组成：管程名称、数据结构的说明、对数据结构进行操作的过程、初始化的语句 特性：模块化、抽象数据类型、信息掩蔽 管程与进程不同：都有数据结构，一个公.一个私、管程操作同步.初始化.进程顺序执行、管程为解决互斥资源.进程实现并发性、进程调用管程.进程主动.管程被动、管程不能并发.进程能并发、管程是 OS 的一个资源管理模块.进程有动态性 条件变量：增加一个条件变量，万一发生意外，在管程中被挂起或被阻塞，下一个进程都可以继续执行 经典进程的同步问题 一、生产者-消费者问题 记录型信号量解决：如果缓冲区空，而且能够获取信号量，就投放产品；如果缓冲区有产品，而且能够获取信号量，就消费 AND 信号量解决：一口气全分配 管程解决：利用管程只有一个进程能够使用的属性 二、哲学家进餐问题 记录型信号量解决：先拿左.后那右、先放左.后放右 解决死锁：最多 4 人取筷子、先检查.有左右筷子才能取、奇左右.偶右左 AND 信号量解决：一口气全分配 三、读者-写者问题 描述：可以多读一、一旦开始写.就不能读或写 记录型信号量解决：读操作：等 rmutex就是为了改 readcount无人读？看看是否在写.等wmutexreadcount+自增完成.rmutex还你读读读等 rmutex为了自减readcount无人读？可以写了.还你 wmutex 写操作：等 wmutex.即无读无写写完.还你 wmutex 利用信号量集机制：读：限制 reader个数如果 mx 是 1.就读最后释放一个 reader个数 写：如果 mx 是 1.并且读者数为 0.就写写完释放 mx 进程通信 一、进程通信类型 共享存储器系统：某些数据结构和共享存储区、管道通信系统、消息传递系统、C-S 系统 二、消息传递通信的实现方式 一直接消息传递系统 1.直接通信原语：对称寻址方式、非对称寻址方式 2.消息格式：较短的减少系统处理和存储的开销、较长可以方便 3.进程同步方式：发塞收塞进程间紧密同步.无缓冲、发通收塞平常状态、发通收通发生某事件无法继续运行、无发塞收通 4.通信链路：用“建立连接”原语建立通信链路.用完拆、用“发送命令”原语建立链路，还分单向和双向 二信箱通信间接 1.定义：是数据结构.分信箱头和信箱体 2.原语：创建和撤销.发送和接收 3.类型：私用、公用操作系统创建、共享进程创建 4.进程之间的关系：一对一、多对一、一对多、多对多 三、直接消息传递系统实例 消息缓冲队列通信机制中的数据结构：利用数据结构式消息缓冲区、在 PCB 增加有关通信的数据项 原语：设置发送区、申请 PCB(B)的缓冲区 i、复制到缓冲区、插入消息队列、移出消息队列、复制到接收区、释放缓冲区 线程的基本概念 描述：就是为了提高程序并发执行的程度 一、线程的引入 进程的两个基本属性：进程是一个可拥有资源的独立单位、进程同时是一个可独立调度和分派的基本单位 进程并发执行所需的时空开销：创建进程、撤销进程、进程切换 线程作为调度和分派的基本单位：线程轻装上阵 二、线程与进程比较 调度的基本单位：线程是调度和分派的基本单位、跨进程，会切换进程 并发性：线程的合作.能够并发 拥有资源：有 TCB.但只是必不可少、保证独立运行的资源 独立性：同一进程的不同线程共享进程的内存地址空间和资源 系统开销：因为轻装.所以减少开销、提升速度 支持多处理机系统：对多线程进程，多个线程可以分配到多个处理机上 三、线程的状态和线程控制块 线程运行的三个状态：和进程一样 线程控制块 TCB：标识符、一组寄存器、运行状态、优先级、线程专有存储区、信号屏蔽、堆栈指针 多线程 OS 中的进程属性：进程是可拥有资源的基本单位、多个线程可并发执行、进程已不是可执行的实体 线程的实现 一、线程的实现方式 内核支持线程 KLT：优点：内核调度同一进程多个线程并行执行、一个线程阻塞.其他线程占有处理机、支持小数据结构和堆栈.切换较快开销小、内核本身采用多线程技术.提高系统执行速度和效率 用户级线程 ULT：优点：无需内核.节省模式切换的开销、调度算法进程专用、与 OS 无关.甚至可以在操作系统平台实现 缺点：一个线程阻塞.同进程的其他线程都会塞、只有一个 CPU.只有一个线程能执行、按进程分配.不公平 组合方式：多对一模型：优点：开销小、缺点：一塞进程全塞、只有一线程访问内核、多线程不能同时在多个处理机上运行 一对一模型：一个用户级线程映射到一个内核支持线程 多对多模型：一对一和多对一的结合 二、线程的实现 内核支持线程的实现：创建线程、保存信息、调度和切换线程、撤销线程、回收资源 用户级线程的实现：运行时系统：用于管理和控制线程的函数的集合，这些函数驻留用户空间.并作为用户级线程与内核之间的接口 内核控制线程：连接到 LWP，连接到 LWP 的线程才能与内核通信 三、线程的创建和终止 线程的创建：初始化线程、创建后返回线程标识符 线程的终止：终止线程用函数或系统调用终止操作.但有些线程被建立就会一直执行。大多数 OS，线程被中止后并不立即释放所占资源，只有“其他线程”执行别离函数才会别离资源，才能被其他线程利用。虽然未释放的资源也可以被其他线程使用，但要有个“等待线程终止”的连接命令作保险.否则一直阻塞 第三章 处理机调度与死锁 处理机调度的层次和调度算法的目标 描述：作业可能要经历多级处理机调度 一、处理机调度层次 一高级调度长程调度/作业调度 对象是作业、决定将外存中处于后备队列的作业调入内存.创建进程和分配资源.并放入就绪队列、主要存在于多道批处理系统，分时和实时系统不设置高级调度 二低级调度进程调度/短程调度 对象是进程/内核级线程、决定就绪队列哪个进程获得处理机、多道批.分时和实时都要配置 三中级调度内存调度存储器的对换功能 对象是暂时不能运行的进程、把这些进程调到外存.设为挂起状态、一有条件.稍微有空就变为就绪状态 分级按运行频率划分 二、处理机调度算法的目标 一共同目标 提高资源利用率、公平、平衡、策略强制执行 二批处理系统目标 处理机利用率高、平均周转时间短、系统吞吐量高 三分时系统目标 响应时间快、均衡性 四实时系统目标 截止时间保证、可预测性 作业与作业调度 一、批处理系统中的作业 一作业和作业步 作业：包括程序.数据和作业说明书、在批处理系统.作业是基本单位从外存调入内存 作业步：独立步骤 二作业控制块JCB 包括作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等 流程：进入系统创建 JCB根据类型放到后备队列等待调度入内存根据 JCB 和作业说明书控制完成回收资源.撤销 JCB 三作业运行的三个阶段和三种状态 收容阶段-后备状态、运行阶段-运行状态、完成阶段-完成状态 二、作业调度的主要任务 也叫：接纳调度 考虑：接纳多少作业、接纳哪些作业 三、先来先服务 FCFS 和短作业优先 SJF 调度算法 一先来先服务 FCFS 就这样.完成或阻塞才分配到其他进程、实际中和其他算法结合使用 有利于长作业进程，不利于短作业进程 二短作业优先 SJF 实际用得多、要预知作业运行时间、长作业、紧迫作业不利、无人机交互 四、优先级调度算法和高响应比优先调度算法 一优先级调度算法 外部赋予作业优先级 二高响应比优先调度算法 集的优点.兼顾长作业、但要做相应比计算.增加系统开销Exp.做过类似 进程调度 一、进程调度的任务、机制和方式 一进程调度的任务 保存处理机的现场信息、按某种算法选取进程、把处理器分配给进程 二进程调度机制 排队器：插入就绪队列 分配器：从就绪队列取出.分配处理机 上下文切换器：保存、装入新的 CPU 现场信息等内容 三进程调度方式 非抢占方式：只有完成或因某事无法继续运行、I/O、执行了原语操作如 block，才会引起进程调度 优点：简单、开销小、适用大多数批处理系统 抢占方式：对分时系统而言.有人机交互、对实时系统而言.能满足任务需求 主要原则：优先权原则、短进程优先原则、时间片原则 二、轮转调度算法 一轮转法RR的基本原理 按 FCFS 策略排成就绪队列，每隔一定时间就产生一次中断 二进程切换时机 时间片未用完就完成：马上调度队首进程.启动新时间片 时间片完还没完成：中断.进程被调到就绪队列队尾 三时间片大小确实定 太短有利于短进程、太长退化为 FCFS 算法.要计算平均周转时间带权周转时间 三、优先级调度算法 一优先级调度算法的类型 非抢占式和抢占式 二优先级的类型 确定优先级的依据：静态优先级：进程类型系统进程优先权高于用户进程优先权、进程对资源的需求少则优先、用户需求紧迫程度、花费 动态优先级：先赋予优先级，随着进程推进或等待时间增加而改变 四、多队列调度算法 将一条就绪队列拆分成多条，各有各调度算法 五、多级反馈队列调度算法 一调度机制 多条就绪队列、队列内使用 FCFS 算法.一个时间片未完成就放到下一个队列的末尾.最后一个队列用 RR 方式、按队列优先级调度.前队列空才到本队列运行 二调度算法的性能 终端型用户、短批处理作业用户、长批处理作业用户 六、基于公平原则调度算法 一保证调度算法 保证处理机公平分配 功能：跟踪进程已经执行的处理时间、该时间除以 n、计算实际处理时间和应获得时间之比、比较比率、比率最低的获得处理机 二公平分享调度算法 考虑多用户 实时调度 描述：实时系统有两种实时任务HRT 和 SRT 一、实现实时调度的基本条件 一提供必要信息 就绪时间、开始截止和完成截止时间、处理时间、资源要求、优先级 二系统处理能力强 处理时间 i/周期时间 i总和 1.未考虑任务切换花费的时间还应该留有余地 提高系统处理能力的途径：单处理机系统增强处理能力.显著减少每个任务的处理时间、多处理机系统.就变成处理时间 i/周期时间 i总和 N 三采用抢占式调度机制 执行完关键程序和临界区后，能及时将自己阻塞起来，以释放处理机 四具有快速切换机制 对中断的快速响应能力、快速的任务分派能力 二、实时调度算法的分类 根据任务性质：H/S 根据调度方式：非抢占式/抢占式 一非抢占式调度算法 轮转、优先调度，不适合实时系统。进程自动放弃处理机，才进行调度。二抢占式调度算法 基于时钟中断的抢占式优先级调度算法：等待时钟中断发生才剥夺当前任务的执行 立即抢占优先调度算法：好快好快.只要任务未处于临界区.就立即剥夺当前任务执行 优先权原则、短作业进程优先原则、时间片原则。三、最早截止时间优先 EDF 算法 非抢占式调度方式用于非周期实时任务：开始截止时间早的排前 抢占式调度方式用于周期实时任务：最早截止时间优先算法 四、最低松弛度优先 LLF算法 紧急程度越高，优先级越高。五、优先级倒置 一优先级倒置的形成 二优先级倒置的解决方法 继承动态优先级的方法：P3 继承 P1 的优先级.一方面防止 P2 抢占处理机、另一方面释放mutex资源 死锁概述 一、资源问题 指互斥资源、不可被抢占的资源 一可重用性资源和消耗性资源 可重用性资源：一个只能分配给一个进程使用、顺序为请求.使用.释放、数目相对固定.运行期间不能创建或删除 可消耗性资源：在进程运行中数目不断变化.可为 0、可以不断创建.放入缓冲区、可以由进程创建.使用并不再返回资源类 二可抢占性资源和不可抢占性资源 可抢占性资源：可以被其他进程抢占.如 CPU 和主存 不可抢占性资源：一旦分配给进程就不能强制收回.要做到底 二、电脑系统中的死锁 一竞争不可抢占性资源引起死锁 我要你的，你要我的，形成环路，死锁 二竞争可消耗资源引起死锁 譬如消息通信机制.先读后写.就会死锁 三进程推进顺序不当引起死锁 竞争不可抢占性资源引起死锁的翻版.多画了一个图 三、死锁的定义、必要条件和处理方法 一死锁的定义 这组死锁进程都在等其他进程释放所占资源 二产生死锁的必要条件 互斥条件：一段时间只被一个进程占用 请求和保持条件：进程已经保持至少一个条件.但有提出新资源请求 不可抢占条件：只能在进程用完才能释放 循环等待条件：存在循环链 三处理死锁的方法 预防死锁：设置限制条件.破坏产生死锁四个必要条件来预防 防止死锁：在资源动态分配时.用防止系统进入不安全状态 检测死锁：通过检测机构及时检测死锁.采取适当措施以解脱 解除死锁：撤销进程.回收资源.分配给处于阻塞的进程 防范逐渐减弱.但资源利用率提高.进程因资源因素而阻塞的频度下降 预防死锁 一、破坏“请求和保持”条件 保证：进程请求 资源时，不持有不可抢占资源 第一种协议：一次性全部申请，从而破坏“请求条件”、缺点是资源被严重浪费.进程饥饿 第二种协议：先释放资源.再请求新资源 二、破坏“不可抢占”条件 当保持了某些不可抢占资源后.提出新资源请求不得满足.就必须释放已经保持的资源.等需要时再申请 缺点：增加周转时间、增加系统开销、降低系统吞吐量 三、破坏“循环等待”条件 总有一个进程占据了较高序号的资源.此后它继续申请的资源必然是空闲的 防止死锁 一、系统安全状态 一安全状态 计算一个资源分配的安全性.如果分配不会导致不安全状态.才可将资源分配给进程 二安全状态之例 三由安全状态向不安全状态的转换 二、利用银行家算法防止死锁 一银行家算法中的数据结构 Availalbe、Max、Allocation、Need 二银行家算法 睇 wiki“银行家算法”条目 声明：Request是请求向量 Request Need,否则出错 Request Available,否则P 等待 系统试探分配资源给 P,并执行 Availalbe-=Requeset;Allocation+=Request;Need-=Request 死锁的检测与解除 一、死锁的检测 一资源分配图 圆圈代表进程、方格代表一类资源、边代表资源分配 二死锁的定理 简化资源分配图.如果不能完全简化.就会死锁 三死锁检测中的数据结构 类似于银行家算法？二、死锁的解除 常用两种方法：抢占资源、终止/撤销进程 一终止进程的方法 终止所有死锁进程：会功亏一篑 逐个终止进程：找到代价最小.考虑优先级、已执行时间.还需的时间、已用资源、交互式还是批处理式 二付出代价最小的死锁解除算法 很不实际 第四章 存储器管理 存储器的层次结构 一、多层结构的存储器系统 CPU 寄存器；高速缓存 Cache、主存储器 RAM、磁盘缓存；固定磁盘、可移动存储介质 二、可执行存储器 就是 CPU 寄存器和主存.访问很快 二、主存储器与寄存器 一主存储器 又叫主存 or 内存.相比 CPU 执行速度.它还是很慢.所以引入寄存器和高速缓存 二寄存器 完全与 CPU 协同工作.但好贵 三、高速缓存和磁盘缓存 一高速缓存 备份主存中较常用的数据.以减少 CPU 对主存储器的访问次数 二磁盘缓存 因为磁盘 I/O 速度远低于主存访问速度.所以设置磁盘缓存来暂存频繁使用的一部分磁盘数据和信息 程序的装入和链接 用户程序要在 OS 中运行.要先装入内存.再转换为一个可执行程序：编译、链接、装入 一、程序的装入 一绝对装入方式 当 OS 很小.且仅能运行单道程序时.完全有可能知道程序驻留在内存的位置.那么就可以产生绝对地址的目标代码 二可重定位装入方式静态重定位 多道程序下.逻辑地址和物理地址不同.要加上起始地址.但只在进程装入时一次完成.故称为静态重定位.可装到内存任何允许位置 三动态运行时的装入方式 需要重定位寄存器，运行时允许移动 二、程序的链接 一静态链接方式 要解决：对相对地址进行修改子程序的相对地址、变换外部调用符号生成可执行文件后不再拆开.又叫静态链接方式 二装入时动态链接 便于修改和更新各模块分开存放、便于实现对目标模块的共享静态每个应用模块必有目标模块的拷贝.无法共享.但动态可以一个目标链接多个应用模块 三运行时动态链接 运行时发现没有.就由 OS 去找这个模块内功加快程序装入过程和节约大量内存空间 连续分配存储管理方式 一、单一连续分配 分系统区和用户区.单用户.单任务操作系统 二、固定分区分配 划分分区的方法：大小相等一台电脑控制多台相同冶炼炉和大小不等 内存分配：通常按大小排队.建立分区使用表.如果找不到大小足够的分区.就拒绝分配内存 三、动态分区分配 动态分区分配中的数据结构：空闲分区表、空闲分区链 动态分区分配算法：之后介绍 4 种分配算法和 3 中索引搜索算法 分区分配操作：分配内存、回收内存 四、基于顺序搜索的动态分区分配算法不太大系统 首次适应算法FF、循环首次适应算法(NF)、最正确适应算法(BF)、最坏适应算法(WF)五、基于索引搜索的动态分区分配算法(大、中型系统)快速适应算法以空间换时间、伙伴系统合并回收与均匀分配、哈希算法 六、动态可重定位分区分配 紧凑、动态重定位、动态重定位分区分配算法 对换 一、多道程序环境下的对换技术 一对换的引入 防止内存全部被阻塞.外存却有很多作业无法进入内存 二对换的类型 整体对换进程对换、页面对换部分对换支持虚拟存储系统 二、对换空间的管理 一对换空间管理的主要目标 文件区管理主要目标：先提高文件存储空间的利用率.离散分配 对换空间管理的主要目标：先提高换入换出的速度，连续分配方式 二对换区空闲盘块管理中的数据结构 与内存的相似 三对换空间的分配与回收 与内存分配和回收雷同 三、进程的换出与换入 一进程的换出 选择被换出的进程：阻塞或睡眠状态、优先级最低、内存驻留时间 进程换出过程 二进程的换入 如果发现许多进程运行时缺页且内存紧张.才启动对换程序.将部分进程调至外存 如果缺页率明显减少.系统吞吐量已下降.则可以暂停运行对换程序 分页存储管理方式 其实分三种：分页、分段、段页式 一、分页存储管理的基本方法 一页面和物理块 页面：页号 页面大小：太小.进程占用较多页面、太多.碎片多、适中.1kB8kB 二地址结构 页号：P 页内地址偏移量：d 两个都有公式计算 三页表 从页号到物理块号的映射 二、地址变换机构 一基本的地址变换机构 如果发现页号页表长度.就引发越界中断；否则页表始址+页号*页表项长度=物理块号 二具有快表的地址变换机构 有个快表在高速缓存 三、访问内存的有效时间 EAT=t+t=2t内存 EAT=a*+(t+)(1-a)+t=2t+-t*a快表 四、两级和多级页表 一两级页表 二多级页表 五、反置页表 一反置页表的引入 二地址变换 分段存储管理方式 一、分段存储管理的基本方法 一方便编程 逻辑地址是由段名段号和段内偏移量段内地址决定的 二信息共享 段是信息的逻辑单位.简化共享过程 三信息保护 就是可以加个标识.不允许读写 四动态增长 可以解决这个问题 五动态链接 二、分段系统的基本原理 一分段 每个段有一个段号，连续的分区 二段表 实现从逻辑段到物理内存区的映射，段长和基址 三地址变换机构 段表项数目比页表项数目少.其所需的联想存储器相对较少.减少存取数据的时间 四分页和分段的主要区别 页是信息的物理单位.分页是系统管理上的需要 while 段是存储管理方式中的逻辑单位.分段目的在于更好满足用户的需要 页大小固定.段大小不固定 分页的用户程序地址是一维的.分段是二维的 三、信息共享 一分页系统中对程序和数据的共享 每个进程都有页表.也都指向相同的物理块号 二分段系统中的程序和数据的共享 可重入代码是一种不允许任何进程对它进行修改的代码 配以局部数据区.把执行中可能改变的部分拷贝到该数据区.这样执行时只需对该数据区中的内容修改即可 四、段页式存储管理方式 分段分页.每段一个段名 段号.比较.加法算段表段号得到页号.(比较).加法算页表页号得到物理块号.加页内地址得物理地址 第五章 虚拟存储器 出现问题：作业很大、大量作业要求运行 虚拟存储器概述 一、常规存储管理方式的特征和局部性原理 一常规存储管理方式的特征 传统：一次性、驻留性 二局部性原理 绝大部分顺序执行、调用进度不超过 5、循环结构由少数指令构成.但多次执行、多对数据结构的处理.这些处理局限于很小的部分 时间、空间局限性 三虚拟存储器的基本工作情况 将少数页面或段先装入内存即可运行 二、虚拟存储器的定义和特征 一虚拟存储器的定义 有请求调入功能和置换功能.能逻辑上对内存内容加以扩充的一种存储器系统 二虚拟存储器的特征 多次性、对换性、虚拟性 三、虚拟存储器的实现方式 一分页请求系统 硬件支持：请求分页的页表机制、缺页中断机制、地址变换机制 实现请求分页的软件 二请求分段系统 硬件支持：请求分段的段表机制、缺段中断机构、地址变换机构 软件支持 请求分页存储管理方式 一、请求分页中的硬件支持 一请求页表机制 二缺页中断机构 三地址变换机构 二、请求分页中的内存分配 一最小物理块数确实定 二内存分配策略 策略：固定分配局部置换、可变分配全局置换、可变分配局部置换 三物理块分配算法 算法：平均分配算法、按比例分配算法、考虑优先权的分配算法 三、页面调入策略 一何时调入页面 预调页策略：手动指出哪些页要调入内存、成功率偏低 请求调页策略：一次调入一页.须较大系统开销 二从何处调入页面 系统拥有足够的对换区空间：进程进行前就把进程相关的文件拷贝到对换区 系统缺少足够的对换区空间：未修改过的不到对换区.以后要用再从文件区调入 UNIX 方式：从文件区入.出到对换区、允许页面共享 三页面调入过程？四缺页率？页面置换算法 抖动：一个进程在运行中把大部分时间都花费在页面置换工作上 一、最正确置换算法和先进先出置换算法 一最正确置换算法看未来 要知道未来需要哪页.实际上不可能 二先进先出页面置换算法 剔走最老的页 二、最近最久未使用和最少使用置换算法LRU 看过去 一最近最久未使用 看最近的 n 个，最老的踢走 二LRU 置换算法的硬件支持 寄存器：8 位寄存器值最小的页被踢出 栈：最新访问的是栈顶 三最少使用置换算法 现实使用这个多.一旦访问就在最高位置一 三、Clock 置换算法 一简单的 CLOCK 置换算法 也叫最近未使用算法.就是有个访问位，10换出 二改良型 CLOCK 置换算法 四类：A M=0 0 1 1 第一步：先找 0 0 第二步：再找 0 1，并置所有页 0 X 第三步：再找 0 0，最后找 0 1，一定找到 优点：减少 I/O 缺点：增加系统开销 四、页面缓冲算法 一影响页面换进换出效率的假设干因素 页面置换算法、写回磁盘的频率、读入内存的频率 二页面缓冲算法 PBA 显著降低页面换进、换出频率，减少页面换进换出的开销 换入换出的开销大幅减少，才能使用简单的置换策略，如 FIFO 要在内存中设置：空闲页面链表、修改页面链表 五、访问内存的有效时间 如果考虑快表的命中率和缺页率：EAT=.如果仅考虑缺页率：EAT=“抖动”与工作集 一、多道程序度与“抖动”一现象 先增后减 二原因 进程太多，物理块不够分 二、工作集 一工作集的基本概念 如果可以预知，就可以先调入内存，大大降低缺页率，从而显著提高处理机利用率 二工作集的定义 引用的集合，类似 FIFO 三、“抖动”的预防方法 一采取局部置换策略“抖动”影响较小 二把工作集算法融入到处理机调度中 每个进程在内存的驻留页面是否足够多，如果是就调入新作业、否则增加新物理块 三利用 L=S 准则调节缺页率 缺页之间的平均时间=平均缺页服务时间 四选择暂停的进程 先暂停优先级最低的进程、在选择并不重要，但较大的进程 请求分段存储管理方式 其实也类似于分页，要硬件和软件支持 一、请求分段中的硬件支持 一请求段表机制 段表项：段名、段长、段基址、存取方式、访问字段 A、修改位 M、存在位 P、增补位、外存始址 A、M：改良型 CLOCK 置换算法 P：本段是否调入