操作系统导论复习要点张不同版.doc

操作系统导论复习要点课程内容 第一章 操作系统概述（3） 第二章 进程和处理机管理（2+9） 第三章 存储管理（6） 第四章 设备管理（4） 第五章 文件管理（2） 第六章 Windows操作系统 第七章 Unix操作系统第一章 操作系统概述本章要点 操作系统的地位：从计算机系统结构的角度 操作系统的定义：研究操作系统的四种视角 现代操作系统的特征、功能、类型 基本概念：批处理、多道程序设计、作业、任务、进程和线程、接口、虚拟存储、文件讲课顺序的一些调整 1.1 计算机系统概述 1.2 操作系统的概念 1.3 操作系统的功能 1.4 操作系统的用户接口 1.5 操作系统的发展史 1.6 操作系统的分类 1.7 研究操作系统的几种视角l 操作系统：管理物理设备。l 实用程序：支持其他软件编制和维护的软件。l 应用程序：特定应用领域的专用软件。操作系统在计算机系统中的地位1.1 操作系统的地位1.2 操作系统四种视角 用户接口 资源管理 虚拟机 作业组织 软件的视角1.2.1 操作系统-软件的视角 操作系统作为软件的外在特性和内在特性 外在特性：命令、调用、语法等等 内在特性：结构特点1.2.2 操作系统用户接口的视角 操作系统为用户提供不同的服务，不同的用户提供不同的接口。 最终用户 系统用户 （用户）命令：指计算机用户要求计算机为其工作的指示。 命令的表现形式： 字符形式：比较灵活，但是繁琐而难记 菜单形式 图形形式：直观易记，不够灵活 命令的使用方式：脱机使用方式（off-line） 联机使用方式（on-line）1.2.3 操作系统资源管理的视角 操作系统是计算机系统中各类资源的管理者，它负责分配、回收以及控制系统中的各种软硬件资源。 跟踪资源的使用状况，满足资源请求，提高资源利用率，以及协调各程序和用户对资源的使用冲突。 监视资源 分配/回收资源 保护资源1.2.4 操作系统虚拟机的视角 操作系统是建立在计算机硬件平台上的虚拟机器，它为应用软件提供了许多比计算机硬件功能更强或者计算机硬件所没有的功能。 操作系统在虚拟机种充当管理员和协调员的角色，管理计算机的软硬件资源，并协调多任务、多进程的运行。 扩充：功能、计算机的数量1.2.5 操作系统作业组织的视角 操作系统是计算机系统工作流程的组织者，它负责协调在系统中运行的各个软件的运行次序。 用于巨型机和大型机上，以批文件方式提交作业，请求主机逐个运行。 主机操作系统负责组织、协调各个作业的运行，并报告执行结果或者错误消息。 减少了人工干预，提高了系统的效率。 这种工作方式有利于有效利用造价高且性能强大的主机资源。操作系统的定义 操作系统是计算机系统中的一个系统软件，管理和控制计算机系统中的软件和硬件资源，合理地组织计算机的工作流程，以便有效利用这些资源为用户提供一个功能强大的、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。1.3 操作系统的形成和发展 操作系统简历 推动操作系统发展的因素 操作系统的发展历史 手工操作操作系统的史前文明 单道批处理（早期批处理）操作系统的雏形 多道批处理系统现代意义上的操作系统的出现 分时系统 实时系统 操作系统的进一步发展1.3.1 操作系统的简历 50年代中期，第一个简单批处理系统 60年代中期，多道程序批处理系统 不久，分时系统，实时系统 80年代，微机及网络操作系统 。 分布式操作系统，嵌入式操作系统 。1.3.2 操作系统发展的推动因素 计算机硬件的升级以及新的硬件的出现 新的服务，方便使用 提高计算机资源利用效率 更正软件错误 计算机体系结构的发展 1.3.3 操作系统的发展史手工操作 早期的计算机是由n多个晶体管组成的 操作和编程完全靠手工进行，直接和硬件打交道 独占资源，效率低下 手工操作，易出差错 串行作业，周期很长1.3.3 操作系统的发展史-单道批处理系统 批处理程序（监督程序）常驻内存 操作步骤： 1、收集一批作业卡，使用专用的I/O计算机将作业逐个读到磁带上保存起来； 2、批处理程序将磁带上的第一作业读入计算机，运算结束后将结果输出到输出磁带上； 3、自动读入下一个作业，依次循环； 4、当一批作业全部执行结束之后，取下输入磁带和输出磁带，输入磁带输入下一批作业，输出磁带送到专用输出计算机进行脱机打印。单道批处理系统评价 解决了作业间自动转接问题，减少了机器时间浪费 串行运行 独占资源，资源利用率低 对短作业不公平 交互性差1.3.3 操作系统的发展史多道批处理系统 单道批处理系统中，任意时刻任意时刻只允许一个作业在内存中运行，资源利用率低。 为了提高资源利用率和系统吞吐量，发展了多道批处理系统 多道批处理系统是真正现代意义的操作系统 多道：指允许多个程序同时存在于内存中，按照某种原则分派处理机，逐个执行这个程序。 批处理：用户提交的作业首先在外存中排成一个队列，然后由作业调度程序按照一定的算法从该队列中依次选取一个或者几个作业转入内存中执行。处理机自动切换 当某个程序占用处理机执行过程中遇到了输入/输出语句，可以启动专门负责输入/输出的系统服务程序完成输入/输出操作，而处理机切换到另外一个程序执行。 多道批处理多道程序设计技术（multiprogramming） 为了提高系统吞吐量和资源利用率，允许多个程序同时驻留内存，使处理机在这些程序之间进行切换，在一段时间内执行完多个程序的处理技术称为多道程序设计技术。 现代操作系统大都采用了多道程序处理技术。 资源利用率：指在给定时间内，系统中某一资源（如CPU、存储器、外部设备等）实际使用时间所占比率。 吞吐量(Throughput)：指单位时间内系统所处理的信息量。它通常是以每小时或每天所处理的作业个数来度量。一个例子的具体使用情况如下表所示： 假设一个计算机系统有256k主存(不包含操作系统)，一个磁盘、一个终端和一台打印机。 三个作业分别被命名为JOB1、JOB2、JOB3。各作业运行时间分别为5分钟、15分钟和10分钟。它们对资源的具体使用情况如下： 作业1主要使用CPU； 作业2主要使用终端（键盘和显示器）； 作业3主要使用磁盘和打印机。多道程序设计引发的问题 处理机的分配与回收 内存的分配与保护 I/O设备的共享与效率 文件的有效组织 作业的组织1.3.3 操作系统的发展史分时系统与实时系统 多道批处理系统的资源利用率和吞吐量提高了，但是交互性很差，作业周转时间比较长。 为了改进响应时间和性能，提供交互式工作环境，分时系统出现。 分时系统的实质是，在多道程序设计技术的基础上，为多个用户配置一个联机终端。 分时系统的工作方式：一台主机连接有若干个终端。用户交互式地向系统提出命令请求，系统接受命令，采用时间片轮转方式处理请求，并在终端上显示结果。 分时：是指多个用户分时使用CPU的时间。将CPU 的单位时间(比如5ms)划分成若干个时间段（时间片）。 批处理系统： 目标是提高机器的使用效率。 适用于比较成熟的大型作业。 用作业控制语言。 分时系统： 目标是对用户请求的快速响应，提供交互性工作环境。 适用于短小作业。 终端键入命令。实时系统 当对处理机操作或数据流动有严格时间要求时，就需要使用实时系统。 实时系统： 实时控制系统：工业生产中的自动控制，军事上的飞机运行、导弹发射等。 实时信息处理系统：民航机票的预订、查询，银行系统的借贷，情报信息检索等系统。实时操作系统的特点 （1）实时性。计算机对随机发生的外部事件能够及时地响应和处理。 （2）可靠性。实时系统控制和处理的对象往往是重要的经济和军事目标，而且又是现场直接控制处理。重要的实时控制系统，采用双工机制。 （3）可确定性。是指系统按照固定的、预先确定的时间或时间间隔执行指定的操作。其可确定性取决于系统响应中断的速度和处理能力。1.3.3 操作系统的发展史操作系统的进一步发展 个人计算机操作系统 网络操作系统 分布式操作系统 嵌入式操作系统网络操作系统 计算机网络环境中提供网络管理、通信、安全、资源共享和各种网络应用等功能的操作系统。 目标：为了实现网络中各个计算机之间的通信和网络资源共享，提高网络资源的利用率和网络的吞吐量。分布式操作系统 分布式系统是指多个处理机通过通信线路相互连接而成的系统，系统地处理和控制功能分布在各个处理机上。 配置在分布式系统上的操作系统成为分布式操作系统，它负责分布式系统中的任务分配、资源管理等功能服务。嵌入式系统 嵌入式系统在控制设备的计算机中运行。 电视机、微波炉、移动电话、汽车、仪器 嵌入式系统是以应用为中心，以计算机技术为基础，软件、硬件可裁剪，适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。1.4 操作系统的功能及特征 操作系统功能 处理机管理 存储器管理 设备管理（输入输出设备） 文件管理 提供接口服务 操作系统的特征 并发性 共享性 随机性 可重构性 虚拟性1.4.1 操作系统的功能1.4.2 操作系统的特征现代操作系统特征 随机性（randomicity） 可重构性（reconstruction） 虚拟性 物理实体转化为若干逻辑上的对应物1.5 一些基本概念 多道程序设计 进程与线程 作业 任务 接口 系统调用 虚拟存储 文件多道程序设计 系统中允许多道程序同时准备运行，当正在运行的那道程序因为某种原因（比如等待输入输出数据）暂时不能继续运行时，系统将自动地启动另一道程序运行；一旦原因消除（比如数据已经到达或者数据已经传输完毕），暂时停止运行的那道程序在将来的某个时候还可以被系统重新启动继续运行。问题 协调因争夺处理机或者输入输出设备而产生的冲突，解决同步、互斥和死锁问题。 防止各道程序之间的交叉和冲突，防止作业被有意无意地破坏。 必须有高效可靠和方便的文件系统，有效地管理和存取系统中的软件资源和辅存空间。进程与线程 进程是指，程序的一次执行，包括可执行的程序、程序所需的数据和相关状态信息。进程是拥有资源的最小实体，在传统os中，进程同时也是系统调度的最小单位。 线程是指，程序的一次相对独立的运行过程；在现代os中，线程是系统调度的最小单位。作业 作业是指，计算机用户在一次上机过程中要求计算机系统为其所做工作的集合；作业中的每项相对独立的工作称为作业步。通常，人们用一组命令来描述作业；其中，每个命令定义一个作业步。 作业的基本类型 脱机作业 联机作业任务 在经典的多任务操作系统环境下，任务与进程是等同的，都被认为是系统的最小工作单位 任务是从系统资源分配的角度描述程序在系统中的运行 进程则从处理器利用和工作流程控制的角度描述程序的执行 程序员习惯称呼进程，而工程师则习惯称呼为任务系统调用 系统调用是操作系统提供的最基本的一级服务，供用户程序调用。 系统调用只能在程序中作为程序语句使用，不能单独使用。接口 英文Interface在操作系统中具有接口和界面两种含义。 接口多用于描述系统硬件之间的连接关系，以及软件和程序模块之间的调用关系。如总线接口、打印机接口等。 界面多用于描述用户与系统之间的操作环境，以及人机之间的交互方式和过程，如字符界面、图形用户界面等。虚拟存储 定义：为了能在有限的内存空间中运行更大、更多的进程（程序），可以将一部分磁盘空间虚拟为逻辑内存，使用户感觉到一个比物理内存空间更大的逻辑内存空间， 即实际物理内存空间与虚拟的那部分逻辑内存空间的总和，统称为虚拟内存空间。文件 文件是若干相关数据的集合，有的操作系统将程序、数据以及各种外部设备统统称为文件。 唯一的文件名 对文件的操作：建立、修改、删除、重命名、设置访问权限等 概括地说，文件就是命名了的字节流，它是现代操作系统对计算机系统中种类繁多的外部设备进行高度抽象的结果。1.6 操作系统的分类1.6 操作系统分类重点总结第二章 用户接口与作业管理几个问题？主要内容 2.1 作业的基本概念 定义 作业步作业作业流 作业控制方式：批处理和交互式 2.2 批处理作业的管理 作业的组织I/O调度控制 2.3 交互式作业管理 常用操作使用接口 2.4 用户和操作系统之间的接口 程序一级接口（系统调用） 作业控制一级接口2.1作业的概念 作业步：每一个相对独立的加工步骤 作业：用户要求计算机处理的问题 作业流：若干作业按照次序合成一批2.1.2作业的控制方式2.2批处理作业的管理2.2批处理作业的管理：组织-I/O-调度-控制2.2批处理作业的管理：组织-I/O-调度-控制2.2批处理作业的管理：组织-I/O-调度-控制SPOOLing系统工作原理Simultaneous Peripheral Operations On-Line含义：同时的外围设备联机操作（假脱机技术）包括： 输入程序模块 输出程序模块 作业调度程序SPOOLing系统工作原理（续2） 作业执行前用慢速设备将作业预先输入到后援存储器（如磁盘、磁鼓，称为输入井）中，称为预输入 作业运行后，使用数据时，从输入井中取出 作业执行不必直接启动外设输出数据，只需将这些数据写入输出井中 作业全部运行完毕，再由外设输出全部数据和信息，称为缓输出 实现了对作业输入、组织调度和输出的统一管理 使外设在CPU直接控制下，与CPU并行工作 作业调度的主要功能 审查系统是否能满足用户作业的资源要求 按照一定的算法选取作业 设计调度算法应考虑的原则 选择调度算法考虑的因素 单道批处理系统的作业调度算法调度算法评价调度实质上是一个策略问题设定的目标往往是相互冲突的 目标： 单位时间内运行尽可能多的作业 使处理机尽可能保持忙碌 使各种I/O设备得以充分利用 对所有的作业都是公平合理的设计调度算法时应考虑的因素： 调度算法应与系统设计目标保持一致 注意系统资源均衡使用 保证提交的作业在截止时间内完成 设法缩短作业平均周转时间大多数操作系统都采用比较简单的调度算法作业平均周转时间=作业流中作业周转时间之和/作业流中作业的个数作业的周转时间=作业的结束时间-作业的提交时间 T（ ） 作业平均带权周转时间 调度算法 先来先服务算法（FCFS：First Come First Serve） 最短作业优先算法（SJF：Shortest Job First） 最高响应比优先算法（HRN：Highest Response Ratio Next） 响应比R = 作业周转时间 / 作业运行时间 =（作业运行时间+作业等待时间）/ 作业运行时间 = 1 +（作业等待时间 / 作业运行时间）单道批处理系统作业调度算法 先来先服务（FCFS）：按照作业提交的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业。 优点：实现简单、公平 缺点：没考虑资源利用率和作业的特殊性（短作业） 先来先服务算法已很少作主要的调度策略，常被结合在其它的调度策略中使用。调度算法 基于优先数调度算法 （HPF：Highest Priority First） （a）由用户规定优先数（外部优先数） 用户提交作业时，根据急迫程度规定适当的优先数 作业调度程序根据JCB优先数决定进入内存的次序 （b）由系统计算优先数（内部优先数） 均衡调度算法算例 假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间 应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间先来先服务调度算法最短作业优先作业算法最高响应比优先作业算法算例FCFS112.54.975SJF 953.25HRN87.54.075前情回顾：操作系统概述2.3.2菜单技术2.3.3窗口技术2.3.4操作命令的执行过程交互式系统实例分时系统分时系统中的用户控制作业的执行大致有四个阶段： 终端的连接 用户登录 控制作业执行 用户退出主要内容 2.1 作业的基本概念 定义 作业步作业作业流 作业控制方式：批处理和交互式 2.2 批处理作业的管理 作业的组织I/O控制（调度） 2.3 交互式作业管理 常用操作使用接口 2.4 用户和操作系统之间的接口 程序一级接口（系统调用） 作业控制一级接口2.4用户与操作系统之间的接口2.4用户与操作系统之间的接口主要内容 2.1 作业的基本概念 定义 作业步作业作业流 作业控制方式：批处理和交互式 2.2 批处理作业的管理 作业的组织I/O调度控制 2.3 交互式作业管理 常用操作使用接口 2.4 用户和操作系统之间的接口 程序一级接口（系统调用） 作业控制一级接口重点总结作业 P42 1.（1）（2）（3）（5）（7） 2.操作系统原理Principles of Operating System第三章 进程和处理机管理本章内容要点 进程的描述及控制 进程调度 互斥与同步 进程通信 死锁3.1进程的概念程序传统的程序是一组指令的集合，是静态概念，无法描述程序在内存中的执行情况，即我们无法从程序的字面上看出它何时执行，何时停顿，也无法看出它与其它执行程序的关系，因此，程序这个静态概念已不能如实反映程序并发执行过程的特征。为了深刻描述程序动态执行过程的性质，人们引入进程（Process）概念。 因此应该采取措施来制约、控制各并发程序段的执行速度 反映程序的运行过程 程序在执行过程中是不断申请资源 ，程序作为共享资源的基本单位是不合适的 所以需要引入一个概念，它能动态描述程序的执行过程而且可以作为拥有资源的基本单位，这个概念就是进程 。思考？ 为什么引入进程？ 1.为了开发同一作业中不同作业步之间的并发，作业机制已不能满足需要，引入了进程机制。 2.动态描述程序的执行过程，制约、控制各并发程序段的执行速度 3.作为拥有资源的基本单位 4.3.1 进程的概念和定义 1. 进程的定义 2. 进程和程序的主要区别 3. 进程的特征3.1.2进程的定义进程与程序的关系 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 进程是操作系统中最基本、重要的概念。是多道程序系统出现后，为了刻画系统内部出现的动态情况，描述系统内部各道程序的活动规律引进的一个概念,所有多道程序设计操作系统都建立在进程的基础上。进程的特征引入进程带来的问题 增加了空间开销：为进程建立数据结构 额外的时间开销：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场 更难控制：竞争和共享资源、协调 3.1 进程的概念和定义 3.2 进程的状态和进程控制块 3.2.1 进程的状态 3.2.2 进程的状态演变 3.2.3 进程控制块3.2进程的状态和进程控制块3.2.2进程的状态演变思考？ 1如果系统中有N个进程， 运行的进程最多几个，最少几个； 就绪进程最多几个最少几个； 等待进程最多几个，最少几个？ 2. 有没有这样的状态转换，为什么？ （1） 等待运行 （2） 就绪等待前情回顾 为什么引入进程？ 进程的定义 进程和程序的区别 同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。 进程的特征 动态性、并行性、独立性、异步性、结构特征 进程的状态及状态演变思考？ 为什么引入进程？ 1.为了开发同一作业中不同作业步之间的并发，作业机制已不能满足需要，引入了进程机制。 2.动态描述程序的执行过程，制约、控制各并发程序段的执行速度 3.作为拥有资源的基本单位 4.3.2.2进程的状态演变多个进程竞争内存资源 内存资源紧张 无就绪状态，处理机空闲：I/O速度比较慢，全部进程都处于阻塞状态 交换技术（swapping）：换出一部分 虚拟存储技术 挂起状态 阻塞：等待事件 挂起：换出内存 就绪状态 阻塞状态 就绪/挂起（静止就绪） 阻塞/挂起（静止阻塞）3.2.3进程控制块进程控制块的组成 3.1 进程的概念和定义 3.2 进程的状态和进程控制块 3.3 进程控制 3.3.1 进程家族及分类 补充 操作系统内核 3.3.2 进程控制的基本操作 3.3进程控制补充操作系统内核（kernel） 操作系统的核心，是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是OS的基础。 现代OS设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序、设备驱动程序等）、基本的、公共的、运行频率较高的模块（如时钟管理、进程调度等）以及关键性数据结构独立开来，使之常驻内存，并对他们进行特殊保护，通常把这一部份成为OS内核。补充操作系统内核（kernel） 用户通过系统调用访问操作系统的功能，这些功能都通过操作系统内核实现。 一般地，操作系统内核的功能可以概括地划分为资源管理功能和支撑功能。 资源管理：进程管理、存储管理、I/O设备管理 支撑功能：中断处理、统计、监测、时钟管理、原语操作等3.3.2进程控制的基本操作进程控制原语 进程创建与撤销 进程切换 进程的阻塞与唤醒 进程的挂起与激活进程控制的基本操作 3.1 进程的概念和定义 3.2 进程的状态和进程控制块 3.3 进程控制 3.4 进程的互斥与同步 3.4.1 临界区 3.4.2 进程互斥 3.4.3 进程同步 多道程序设计技术允许多个进程同时驻留内存并发执行。 问题 如何协调多个进程对系统资源（内存、外部设备等）的竞争和共享？ 如何解决多个进程因竞争资源而出现结果异常，甚至导致系统不稳定、失效等问题？ 多个进程同时申请文件打印，如何有效分配？例子 存折和银行卡 ATM和柜台存款（1000，2000元） 余额5000 两个进程同时读余额并进行修改 多个进程同时修改一数据，必须进行控制 在多道程序设计技术的OS中对诸多进程的并发控制是非常重要和必须的。3.4.1 临界区 进程竞争资源首先必须解决互斥问题。某些共享资源必须互斥使用，如打印机、共享变量、表格、文件等。 这类资源又称为临界资源，访问临界资源的那段代码称为临界区。 任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。 临界资源 输入机、打印机、磁盘机 变量、数据、表格、栈。进程互斥进入临界区 当进程需要使用临界资源时，通过获得临界区的使用权实现。 首先在进入区判断是否可以进入临界区，如果可以，则必须设置临界区使用标志，阻止其他后来的进程进入临界区。后来的进程通过查看临界区的使用标志，知道自己不能进入临界区，就进入阻塞队列，将自己阻塞。 当临界区内的进程使用完毕，退出临界区时，即在退出区修改临界区使用标志，并负责唤醒阻塞队列中的一个进程，让其进入临界区。临界区的使用原则（调度原则） 当无进程访问临界区时，允许一个进程立即访问其临界区。（空闲让进） 当某一进程已访问了它的临界区时，其他试图访问临界区的进程必须等待。（忙则等待） 当某一进程离开临界区时，若有等待访问临界区的进程，则允许其中的一个进程进入临界区访问。（空闲让进） 进程只能在临界区内等待有限时间，不能使其他进程在临界区外无限等待。（有限等待） 进入临界区的进程不能在临界区内长时间阻塞等待某事件，必须在一定期限内退出临界区。（让权等待）3.4.2 进程互斥实现方法 软件方法 硬件方法 信号量方法 管程方法 消息传递方法 软件的方法是指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互斥，无需专门的程序设计语言或者操作系统的支持 实践证明，该方法很那正确控制进程间的同步与互斥，而且可能会大大地增加系统的额外开销。 为了解决软件方法的不足，有人提出了硬件解决方法，通过屏蔽中断或采用专门的机器指令控制同步与互斥。 减少了系统额外开销 硬件约束条件太强，可能导致进程饥饿与死锁现象 一直没能成为通用的解决方法。3.4.2进程互斥-有如千军万马过独木桥。资源只能互斥地使用，而不能同步使用。n 利用加锁实现进程互斥p 当某个进程进入临界区后，为了阻止其他进程进入临界区，它将锁上临界区，直到退出临界区为止。p 并发进程在申请进入临界区时，首先测试该临界区是否是上锁，若是，则该进程要等到临界区开锁之后才能进入临界区。n 缺点：系统开销大、不公平。前情回顾 进程控制块（PCB） 操作系统内核 原语操作 临界资源与临界区 进程互斥实现方法 互斥的加锁实现信号量和P、V操作 红绿灯 阻塞，死锁 红灯阻塞等待 绿灯进入临界区基本原理 两个或者多个进程可以通过传递信号进行合作，可以迫使进程在某个位置暂时停止执行（阻塞等待），直到它收到一个可以向前推进的信号（被唤醒） 实现信号灯作用的变量称为信号量，常被定义为记录型变量s，其中一个域为整型，另一个域为队列，其元素为等待该信号量的阻塞进程。利用信号量实现进程互斥 信号量：表示资源的物理实体，是一个与队列有关的整数变量，OS系统利用它的状态对进程和资源进行管理。 原语操作：P操作和V操作 wait（s） signal（s） 公用信号量：联系着一组并行进程，初始值为1，每个进程都可以对它进行P和V操作，通常它为实现进程的互斥而设置。（互斥信号量） 私用信号量：联系着一组共行进程，初始值为0或者某个整数，仅允许拥有它的进程对他进行P和V操作，通常用来实现进程的同步。（资源信号量）Procedure P(S)Begin Lock out interrupts; 关中断 S:=S-1; 信号量的值减1 If S0 then begin 如果S0，说明已经没有此类资源 Status(q):=block; q的申请得不到满足，将其阻赛 Insert(Q,q); 将q插入到该资源的等待队列中 end Unlock interrupts; 开中断End; P原语-P（S）-申请一个单位的资源，执行一次P操作，信号量的值就减1。Procedure V(S)Begin Lock out interrupts; 关中断 S:=S+1; 信号量的值加1 If S=0 then begin 如果S=0，说明有等待该资源的进程 Remove(Q,r); 则将进程r从等待队列中移出 Status(r):=ready; 并将其状态改为就绪 Insert(RL,r); 插入到就绪队列 end; Unlock interrupts; 开中断End; V原语-V（S）-释放一个单位的资源，执行一次V操作，信号量的值就加1进程互斥进入临界区信号量的特征信号量的特征 信号量的值=信号量的初始值-P操作的次数+V操作的次数 执行V操作表示释放一个单位的资源。若S1 P(S) 多个读者共享的计数器rc 互斥使用！前情回顾 信号量表示资源的实体，变量 公用信号量、私用信号量 互斥信号量、资源信号量 P（s）、V（s） 信号量的特征 读者写者问题进程互斥进入临界区3.4.3进程的同步-不同进程之间的协作过程 进程同步的规则： 计算进程计算出数据后，打印进程才能执行 打印进程取走数据后，计算进程才能执行单缓冲区 两个私有信号量： Sc：是否有可供打印的结果 Sp：缓冲区的计算结果是否取走 初始值： Sc：=0； Sp：=0 同步和互斥 计算进程：结果输入缓冲区 计算进程：唤醒打印进程 计算进程：数据未取走，阻塞自己 打印进程：申请数据 打印进程：打印，唤醒计算进程Begin semaphore Sc,Sp; Sc:=0;Sp:=0;Cobegin CP:begin LA:computer next number; Add to buffer; V(Sc); P(Sp); Goto LA end 生产者和消费者问题 多缓冲区 同步规则： 生产者企图将一个消息放入一个已经满的缓冲区时要等消费者取走一个消息 消费者企图从空的缓冲区取走消息时，要等生产者放入一个消息之后 互斥：缓冲区生产者和消费者问题 多缓冲区 生产者进程：有空输入，满时等待- empty 消费者进程：有数消费，空时等待-full full：消息数量 empty：空缓冲区数量 初始值：empty：=n；full：=0 对缓冲区的互斥使用： mutex:=1互斥信号量生产者和消费者问题 生产者进程： 先看缓冲区是否有空，P(empty) 如果有空，申请互斥使用缓冲区P(mutex) 如果获得缓冲区使用权，将数据输入缓冲区 释放缓冲区使用权，V(mutex) 发送消息，有新的数据输入，V(full)生产者和消费者问题 消费者进程： 先看缓冲区是否有数据，P(full) 如果有数据，申请互斥使用缓冲区P(mutex) 如果获得缓冲区使用权，将数据消费 释放缓冲区使用权，V(mutex) 有新的空间，V(empty)begin semaphore mutex,empty,full; mutext:=1;empty:=n;full:=0;Cobegin producer:begin L1:produce next message; P(empty); P(mutext); add to buffer; V(mutex); V(full); goto L1; end利用信号量实现进程同步 分析： 司机和售票员要互通消息：是否启动车辆？能否开车门？分别用S1，S2表示。假设初始状态车停在始发站，车门关着，则S1=0,S2=1,售票员工作流程的起点是开车门。3.5 进程通信 进程通信互斥与同步 信号通信和信件通信 低级通信原语：开锁、关锁、P、V操作原语 高级通信原语：较高的传输效率传输大批量的信息 消息缓冲和信箱实例 幼儿园小朋友喂饭 喂饭方法设计的目标？原则？ 调度在一个队列中，按照某种方法或者算法，选择一个适合的个体的过程。 关键算法 如何设计一个好的算法？调度目标 公平性 处理机利用率 提高系统吞吐量 尽量减少响应时间3.6进程调度为什么引进进程调度？3.6.2引起进程调度的原因3.6.2引起进程调度的原因 在分时系统中，分配给该进程运行的时间片已经用完 在执行完系统调用，当系统程序返回用户进程时，可认为系统进程执行完毕，从而可以调度选择一个新的用户进程执行 在可剥夺方式下，就绪队列中的某进程的优先级变得高于当前执行进程的优先级时会引起进程调度进程调度的方式 长程调度作业调度 短程调度进程调度3.6.3 进程调度算法 先来先服务（FCFS） 按照作业来到的先后顺序排队，每次调度队首的作业（进程）。 非抢占（剥夺），实现简单，看似公平 对于后进入队列，运行时间较短的作业或I/O型的作业要长时间等待。 先来先服务（FCFS） 对短作业不公平。如果长作业排在队首，那么后边的短作业就会等待很长时间，增加了平均周转时间。 不利于I/O型作业 混合使用，例如加入优先级3.6.3 进程调度算法 短作业（进程）优先 通过计算判断就绪队列中哪个作业的预期执行时间最短，就调度谁。 非抢占（剥夺） 短作业（进程）优先 与FCFS算法相比，改善的系统性能，降低了平均等待时间，提高了系统的吞吐量。 也可能让长作业长时间等待 如何预测执行时间？ 最高优先级优先（HPF）调度算法 优先级调度算法（priority-scheduling algorithm）是指每个进程都有一个优先级与其相关联，具有最高优先级的就绪进程会被分派到CPU。具有相同优先级的进程按FCFS顺序调度。 作业调度、进程调度 抢占式和非抢占式优先级的确定考虑因素 进程的类型（性质） 系统进程、用户进程 I/O繁忙CPU繁忙：充分利用资源 交互性批量性：响应时间 进程要求的资源 短作业优先 外部优先级和作业到达时间 进程完成功能的重要性和急迫性优先级的确定方法 静态优先级 进程创建初给他一个优先级，不再改变。 调度方法简单，但是随着进程的推进，原来确定优先级的特性可能在改变。 那么为了改善调度性能动态优先级动态优先级 典型的动态优先级变化方式为： 优先级随着进程运行的剩余时间的减少而上升，使将要执行结束的进程尽快完成； 或者随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿。 具体实现方法，在每个时钟中断时，或者需要进程切换时，重新计算队列中各进程的优先级，并优先调度优先级高的进程。 剩余时间最短者优先，响应比高者优先3.6.3 进程调度算法 响应比高者优先 作业（进程）的响应时间=作业（进程）等待时间+运行时间 作业（进程）的响应比=作业的响应时间/运行时间 既考虑了等待时间，又考虑了运行时间 非抢占（剥夺） 作业虽然长，但是随着等待时间的增加，其响应比增加 运行时间越短，响应比越高 很难预估作业的运行时间 增加了系统开销前情回顾 进程同步 进程调度 调度目标 调度的原因 调度的方式：抢占式和非抢占式 调度算法：FCFS、短进程优先、最高优先级优先（动态优先级，响应比高者优先）轮转法 实例： 在一个分时联机系统中，同时有n个人通过各自的终端共享一台主机（服务器）。终端完成输入/输出操作，主机负责处理从终端发来的请求，为之建立进程并协调各进程的运行、调度各个进程等，并尽量满足每个终端用户对响应时间的要求。 在分时系统中，n个进程循环地获得时间片而执行。从系统中来看他们是交替执行的，但每个终端用户而言，都感觉是在独占主机，不受其他用户的影响，这是通过进程并发执行实现的。 如果用户数太多，进程急剧增加，进程的响应时间也可能增长，用户将明显感觉到主机的速度慢而不满意。 时间片的大小也会影响到进程的响应时间。1、简单轮转法 调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。 抢占式（剥夺式） 循环得为每个进程分配时间片，对每个进程都是公平的。 对于短进程和大量I/O操作的进程不利 交互对于时间要求紧迫的进程不能及时处理 时间片可变 优先级多队列2、可变时间片轮转法 时间片设置 响应时间 就绪队列中进程数目（最大用户数） 进程转换时间 系统效率等2、可变时间片轮转法 时间片 进程数 响应时间3、多队列轮转法 建立多个就绪队列 每个队列有不同的优先级 每个队列又分别采用时间片轮转法调度调度算法小结 先来先服务 短进程（作业）优先 最高优先级优先 剩余时间最短者优先 响应比高者优先 轮转调度法 简单轮转法 可变时间片轮转法 多队列轮转法 如何选择进程调度算法跟系统设计的目标有关 交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时根据进程性质设置不同的优先级 批处理系统往往以作业的平均周转时间来衡量调度性能，常选用基于优先级的短进程（作业）优先调度算法。3.7 死锁银行家算法假设某银行拟将一定数量的资金供给一定数量的顾客共享使用。规定：p 每个顾客必须预先 申请对资金的最大需求量，但不得超过银行共享资金的总和；p 每个顾客的借款方式是以一个资金单位为单位p 银行对顾客提出的每次交易，将根据当时的资金数量，依照一定的原则，或立即成交或推迟成交，但必须保证客户等待的时间是有限的，每个顾客的借款总额不得超过其最大申请量p 当且仅当每个顾客的借款总额达到最大申请量后，才能且必须在有限时间内归还其全部借款假设银行有10个资金单位，有甲、乙、丙三个顾客与银行进行交易，三个顾客的最大申请额分别为8、3、9个资金单位。死锁 并发控制中出现的问题 多个进程竞争系统资源 进程的并发控制不仅要控制若干进程的同步与互斥，确保进程之间的正常通信，还需要解决进程死锁的问题。 一旦出现进程死锁，相应的进程将无法向前推进。如果系统内的绝大多数进程或全部进程死锁，那么，整个系统将处于瘫痪状态，造成系统的死机。 交通中的死锁现象 进程竞争引起死锁 改进（推进顺序）死锁定义 当某进程提出资源申请后，使得若干进程在无外力作用下，永远不能再继续前进，称这种情况为系统发生了死锁或僵局。 竞争资源 推进顺序不当 相互通信而永久阻塞 Eg：两个进程都在等待着对方占有的而不不能为自己使用的资源，这时就发生了死锁。 若系统出现死锁，必须有相应的措施进行解除。 当然，如果能提前预防和避免死锁的出现，将能够提高系统的运行效率。引起死锁的原因 主要原因，竞争资源。而进程对资源的总需求量超过系统能提供的最大资源量。 永久性资源（可重用资源） 消耗型资源 永久性资源，某一时刻仅允许一个进程使用、不能被进程消耗的、释放以后还可以被其他进程使用的资源。 处理机、I/O通道和设备、存储器、文件、数据库、信号量之类的 竞争永久性资源可能引起死锁 消耗性资源，可以创造（生产）和撤销（消耗）的资源，其数量不限。 中断、信号、消息、Buffer中的数据 进程竞争消耗性资源也可能产生死锁。 程序设计引起 死锁：预防或者解除 什么情况造成出现死锁 死锁产生的条件产生死锁的条件 互斥：竞争的资源一次只能被一个进程使用 请求和保持：当一个进程占有一些资源，同时又申请新的资源。如果新资源申请失败，进程将占有资源且阻塞等待。 非剥夺：进程已经占有的资源不能被其他进程强行剥夺。 循环等待：在系统中存在一个由若干进程形成的循环请求链，其中的每一个进程均占有一些资源，同时又申请环形请求链中下一个进程所占有的资源。 四个条件-必要条件 第四个条件实际上是前三个条件的可能导致的结果，即只有存在互斥、请求和保持、非剥夺条件，就可能出现循环等待。 只要系统出现循环等待，一定出现死锁。解决死锁的方法 按照解决死锁的时机： 预防死锁 死锁检测（避免死锁） 死锁恢复（死锁检测与恢复）解决死锁的方法 预防死锁：进程申请资源时必须遵守某些预先制定的限制条件，以破坏产生死锁的四个必要条件中的一个或几个，防止死锁发生。 该方法严格限制了系统资源的分配和使用，会降低系统资源的利用率。 避免死锁：当进程申请资源时，需要首先判断（预测），如果满足这次资源的请求可能导致死锁，拒绝请求，阻塞进程，直到其所需的资源可分配为止。 类似于下棋 该方法并不严格限制产生死锁的四个必要条件，以提高系统资源利用率。 安全状态和不安全状态 指系统能按某种进程顺序，如，分别为这n个进程分配其所需的资源，直至最大需求，使每个进程都能顺利完成。 就称为安全序列 如果系统中不存在这样的安全序列，则称系统处于不安全状态，可能出现死锁。 若系统处于安全状态，且按照某个安全序列分配资源，可以保证系统不会出现死锁。 并非所有不安全状态都会出现死锁。 不安全状态可能进入死锁状态 避免死锁。避免系统进入不安全状态。银行家算法T0时刻系统是安全的，存在一个安全序列。 检测并解除死锁：进程申请资源不进行限制，定时的检测，发现了就解除死锁。 实践证明，该方法可进一步提高资源利用率。 解除死锁 资源剥夺 撤销进程银行家算法假设某银行拟将一定数量的资金供给一定数量的顾客共享使用。规定：p 每个顾客必须预先 申请对资金的最大需求量，但不得超过银行共享资金的总和；p 每个顾客的借款方式是以一个资金单位为单位p 银行对顾客提出的每次交易，将根据当时的资金数量，依照一定的原则，或立即成交或推迟成交，但必须保证客户等待的时间是有限的，每个顾客的借款总额不得超过其最大申请量p 当且仅当每个顾客的借款总额达到最大申请量后，才能且必须在有限时间内归还其全部借款银行家算法：分配资源的原则 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程 进程可以分期请求资源，但请求的总数不能超过最大需求量 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在优先的时