[工学]计算机操作系统课件.ppt

计算机操作系统 南京工业大学信息学院计算机系 2 总目录 第1章操作系统引论第2章进程管理第3章处理机调度与死锁第4章存储器管理第5章设备管理第6章文件管理第7章操作系统接口 3 课内上机实验 进程的创建线程的创建进程同步进程通信进程调度银行家算法页面置换算法的模拟磁盘I O命令解释程序 说明 以上9个上机实验 共计22学时 包括2个进阶要求的4学时 可以选择其中的4次实验 共8学时 作为课内上机实验任务 第1次实验 进程管理 第4次实验 操作系统接口 第3次实验 存储器管理 设备管理 4选1 2选1 2选1 4 第1章操作系统引论 1 1OS的目标和作用1 2OS的发展过程1 3操作系统的基本特征1 4操作系统的主要功能1 5操作系统的结构设计第1章复习题 5 1 1 1OS的目标 有效性方便性可扩展性开放性 操作系统 OperatingSystem OS 是计算机硬件上的第一层软件 是计算机必须配置的最基本 最重要的系统软件 1 1OS的目标和作用 6 1 有效性 早期OS的主要目标 有效提高CPU和I O设备利用率提高的方法 合理地组织计算机的工作流程2 方便性 现在OS越来越重视方便性 可使计算机系统更容易使用 解释之 方便性和有效性是设计OS的两个最重要的目标 7 3 可扩展性 计算机硬件和体系结构的发展 对OS提出了更高的功能和性能要求计算机网络 特别是Internet的发展 也对OS提出了一系列更高的要求 为什么要有可扩充性 因为 OS为了能适应发展的要求 须具有良好的可扩充性 如何才有可扩充性 应采用新的OS结构 如微内核结构和客户服务器模式 8 4 开放性为什么要有开放性 计算机网络 特别是LAN的迅速发展 使OS的应用环境由单机转向网络环境 为使不同厂家的计算机和设备能通过网络加以集成化 并能正确 有效地协同工作 实现应用的可移植性和互操作性 必须具有统一的开放环境 进而要求OS具有开放性 什么是开放性 开放性是指系统能遵循世界标准规范 特别是遵循开放系统互连 OSI 国际标准 9 从用户观点看 OS是用户和计算机硬件系统之间的接口从资源管理观点看 OS是计算机系统资源 软 硬 的管理者 1 1 2OS的作用 1 OS作为用户和计算机硬件系统的接口2 OS作为计算机资源的管理者3 OS实现了对计算机资源的抽象 操作系统的作用 10 1 OS作为用户和计算机硬件系统的接口 用户接口 用户可以通过三种方式使用计算机 命令方式 键盘命令 图标 窗口方式 GUI 系统调用方式 程序接口 操作接口 1 1 2OS的作用 11 计算机系统资源可归结为四类 处理器 存储器 I O设备 信息 数据和程序 OS的主要功能也正是针对这四类资源进行有效管理 2 OS作为计算机资源的管理者 处理机管理 分配和控制处理机存储器管理 主要是内存分配和回收I O设备管理 I O设备的分配与操纵文件管理 文件的存取 共享和保护 12 完全无软件的计算机 裸机 裸机 难于使用 裸机覆盖了一层I O设备管理软件如图1 2所示 由它来实现对I O设备操作的细节 并向上提供一组I O操作命令 如Read和Write命令 用户可以利用它进行数据输入 输出 而无需关心I O实现的细节 此时用户所看到的是一台功能显著增强 使用极为方便的的机器 它向上提供了一组抽象的I O设备 称为扩充机或虚拟机 3 OS实现了对计算机资源的抽象 虚拟性是OS的基本特征之一 第一层软件 第二层软件 13 为了方便用户使用文件系统 又在第一层软件上再覆盖一层用于文件的管理软件 用它来实现对文件操作的细节 并向上提供一组对文件进行存取操作的命令 第二个层次的抽象 又在文件管理软件上再覆盖一层面向用户的窗口软件 用户便可在窗口环境下方便地使用计算机 形成一台功能更强的虚拟机 由此可知 操作系统是铺设在硬件上的多层系统软件 它们不仅增强了系统功能 而且还隐藏了对硬件操作的细节 由它们实现对计算机硬件的多个层次的抽象 14 1 1 3推动OS发展的主要动力 1 不断提高计算机资源利用率 2 方便用户 继续发展的因素分时系统 或称多用户系统 3 器件的不断更新换代 4 计算机体系结构的不断发展 最初发展的动力 批处理系统 8位机 16位机 32位机 64位机 8位OS 16位OS 单机系统 多处理机系统 单机OS 多处理机OS计算机网络 网络OS 15 1 2OS的发展过程 20世纪50年代中期 第一个简单的批处理系统60年代中期 多道程序批处理系统 随后出现分时系统上世纪80年代开始至21世纪初 微型机 多处理机 计算机网络大发展年代 微机OS 多处理机OS和网络OS的形成和大发展年代 16 1 2 1无OS的计算机系统 人工操作方式脱机输入 输出 Off LineI O 方式 20世纪50年代末 这一时期有两种操作方式 17 1 人工操作方式 程序员将事先已穿孔 对应于程序和数据 的纸带 或卡片 装入纸带输入机 或卡片输入机 再启动输入机将程序和数据输入计算机 然后启动计算机运行 当程序运行完毕并取走计算结果后 才让下一个用户上机 缺点 用户独占全机 CPU等待人工操作 18 2 脱机输入 输出方式 优点 1 减少了CPU的空闲时间 2 提高了I O速度 19 1 2 2单道批处理系统 把一批作业以脱机方式输入到磁带上 在监督程序 Monitor 控制下使这批作业一个接一个地连续处理 参看下页的图1 3 它是OS的前身 而非现在人们理解的OS 1 单道批处理系统的处理过程 20 开始 还有下一个作业 停止 把下一个作业的源程序转换为目标程序 源程序有错吗 装配目标程序 目标程序运行直到结束 否 是 是 否 图1 3单道批处理系统的处理流程 21 2 单道批处理系统的特征 1 自动性 在磁带上的作业能自动地逐个地依次运行 而无需人工干预 2 顺序性 3 单道性 磁带上的各道作业是顺序地进入内存 各道作业的完成顺序与它们进入内存的顺序相同 即先调入内存的作业先完成 在内存中仅有一道程序运行 即监督程序每次从磁带上只调入一道程序进入内存 当该程序完成或发生异常情况时 才换入其后继程序进入内存运行 22 1 2 3多道批处理系统 多道程序设计的基本概念 20世纪60年代中期 用户提交的作业事先存放在外存上 形成 后备队列 作业调度程序按一定算法从后备队列中选择若干作业调入内存 使它们共享CPU和系统中的各种资源 好处 1 提高CPU利用率 2 提高内存和I O设备利用率 3 增加系统吞吐量 23 多道批处理系统的特征 1 多道性 多道程序在内存中并发执行 提高了资源利用率和系统吞吐量 2 无序性 先进入内存的作业可能后完成 后进入内存的作业可能先完成 3 调度性 作业从提交到完成 需经过两种调度 作业调度和进程调度 24 多道批处理系统的优缺点 1 资源利用率高 CPU 内存 I O设备利用率 2 系统吞吐量大 3 周转时间长 4 无交互能力 系统吞吐量是指系统在单位时间内所完成的总工作量 作业周转时间是指从作业进入系统 提交 开始 直至它完成并退出系统为止所经历的时间 对修改和调试程序极不方便 25 多道批处理系统需要解决的问题 1 处理机管理问题 处理机分配 提高利用率 2 内存管理问题 分配 保护等 3 I O设备管理问题 方便用户 提高利用率 4 文件管理问题 方便用户 数据安全一致 5 作业管理问题 计算型 I O型不同处理 26 1 2 4分时系统 分时系统 是指在一台主机上连接多个带有显示器和键盘的终端 同时允许多个用户通过自己的终端 以交互方式使用计算机 共享主机中的资源 27 1 分时系统的产生 是为了满足用户的以下需求而产生的 1 人 机交互 2 共享主机 3 便于用户上机 28 2 分时系统实现中的关键问题 1 及时接收 2 及时处理 用户作业不能先进入磁盘 然后再调入内存不允许一个作业长期占用处理机 直至它运行结束或出现I O请求后 方才调度其它作业运行应该规定每个作业只运行一个很短的时间 称为时间片 要做到上述两条 必须彻底改变批处理系统的运行方式 即 29 3 分时系统的特征 1 多路性 允许一台主机上同时联接多个联机终端 2 独立性 每个用户各占一个终端 彼此独立操作 互不干扰 3 及时性 用户的请求能在很短时间内获得响应 4 交互性 用户可通过终端与系统进行广泛的对话 30 1 2 5实时系统 实时系统 Real TimeSystem 是指系统能及时响应外部事件的请求 在规定时间内完成该事件的处理 并控制所有实时任务协调一致地运行 定义 31 1 应用需求 1 实时控制 飞机或火车的订票系统 情报检索系统等 2 实时信息处理 实时数据采集处理 执行机构 自动控制 32 2 实时任务 在实时系统中必然存在着若干个实时任务 这些实时任务通常与某个 某些 外部设备相关 能反映或控制相应的外部设备 因而带有某种程度的紧迫性 周期性实时任务 按指定周期循环执行 以便周期性地控制某外部设备 非周期性实时任务 外部设备发出的激励信号无明显周期性 但都必须联系着一个截止时间 开始截止时间 任务在某时间以前必须开始执行 完成截止时间 任务在某时间以前必须完成 分类 按执行是否周期性划分 33 分类 实时任务按对截止时间要求划分 硬实时任务 软实时任务 系统必须满足任务对截止时间的要求 否则可能出现难于预测的结果 它也联系着一个截止时间 但并不严格 若偶尔错过了任务的截止时间 对系统产生的影响也不会太大 34 3 实时系统与分时系统特征的比较 1 多路性 实时系统的多路性主要表现在 系统经常对多路的现场信息进行采集 以及对多个对象或多个执行机构进行控制 2 独立性 实时系统中对信息的采集和对对象的控制 也都是彼此互不干扰 3 及时性 实时系统的及时性 是以控制对象所要求的开始截止时间或完成截止时间来确定的 一般为秒级 百毫秒级直至毫秒级 甚至有的要低于100微秒 4 交互性 实时系统的交互性仅限于访问系统中某些特定的专用服务程序 不象分时系统那样能向终端用户提供数据处理服务 资源共享等服务 5 可靠性 实时系统要求系统高度可靠 往往采用多级容错措施来保证系统的安全性及数据的安全性 35 1 2 6微机操作系统的发展 1 单用户单任务操作系统 CP M上世纪70年代 8位机 MS DOS上世纪80年代 16位机 32位机 2 单用户多任务操作系统 Windows95Windows98WindowsXPWindowsNT 兼容16位应用程序的32位操作系统 36 3 多用户多任务操作系统 UNIXOS AT T的Bell实验室 SolarisOS SUN公司 LinuxOS UNIX重要变种 芬兰学生 集体开发 37 操作系统的定义 操作系统是一组控制和管理计算机硬件和软件资源 合理地对各类作业进行调度 以及方便用户使用的程序的集合 无统一的定义 38 1 3操作系统的基本特征 1 3 1并发 Concurrence OS最重要的特征 其它三个特征都以并发为前提的 并行与并发 并行性 两个或多个事件在同一时刻发生 并发性 两个或多个事件在同一时间间隔内发生 在多道程序环境下 并发性是指在一段时间内 宏观上有多个程序在同时运行 但在单处理机系统中 每一时刻却只能有一道程序执行 故微观上这些程序只能是分时地交替执行 若计算机系统中有多个处理机 则这些可以并发执行的程序可被分配到多个处理机上 实现并行执行 39 与并发紧密相连的概念 进程 通常的程序是静态实体 它是不能并发执行的 为了使程序能并发执行 系统必须分别为每个程序建立进程 Process 进程是指在系统中能独立运行并作为资源分配的基本单位 它是由一组机器指令 数据和堆栈等组成的 是一个活动实体 多个进程之间可以并发执行和交换信息 40 在OS中引入进程的目的 是使多个程序能并发执行 进程和并发是现代OS中最重要的基本概念 也是OS运行的基础 直到80年代中期 人们才提出了比进程更小的单位 线程 Threads 一个进程通常包含若干线程 近年来推出的OS都引入了线程 关于进程 线程的初步概念 41 1 3 2共享 sharing 共享是指系统中的资源可供内存中多个并发执行的进程 线程 共同使用 目前主要有以下两种资源共享方式 1 互斥共享方式 对于临界资源 要求被互斥地共享 什么叫临界资源 临界资源例子 2 同时访问方式 对于共享资源 允许在一段时间内由多个进程 同时 对它进行访问 这里所说的 同时 往往是宏观上的 而微观上 这些进程可能是交替地对该资源进行访问 共享资源 42 资源的共享是以进程的并发执行为条件的 若系统不允许程序并发执行 自然不存在资源共享问题 若系统不能对资源共享实施有效管理 协调好诸进程对共享资源的访问 也必然影响到程序并发执行的程度 甚至根本无法并发执行 并发和共享是操作系统的两个最基本的特征 它们是互为存在条件的 43 1 3 3 虚拟 Virtual 虚拟 是指通过某种技术把一个物理实体变为若干个逻辑上的对应物 OS中利用了两种方式实现虚拟技术 即时分复用技术和空分复用技术 分别用来实现虚拟处理机 虚拟内存 虚拟外部设备和虚拟信道等 44 1 时分复用技术 时分复用技术最早用于电信行业 它将一条物理信道虚拟为多条逻辑信道 将每条逻辑信道供一对用户通话 操作系统中利用时分复用技术来实现虚拟处理机 虚拟设备等 以提高资源利用率 1 虚拟处理机技术利用多道程序设计技术 为每道程序建立一个进程 让多道程序并发地执行 以此来分时使用一台处理机 此时 虽然系统中只有一台处理机 但它能同时为多个用户服务 使每个终端用户都认为有一台处理机在专门为他服务 亦即把一台物理上的CPU虚拟为多台逻辑上的CPU 也称为虚拟处理机 45 通过虚拟设备技术 将一台物理I O设备虚拟为多台逻辑上的I O设备 允许每个用户占用一台逻辑上的I O设备 这样便可使原来在一段时间仅允许一个用户访问的设备 即临界资源 变为在一段时间内允许多个用户同时访问的共享设备 例如 虚拟打印机 2 虚拟设备技术 46 2 空分复用技术 上世纪初 电信业中就利用频分复用技术来提高信道的利用率 计算机中使用空分复用技术来提高存储空间的利用率 1 虚拟磁盘技术 通过虚拟磁盘技术 将一台硬盘虚拟成多台虚拟磁盘 这样使用起来方便 安全 虚拟磁盘技术采用了空分复用技术 它将硬盘划分成几个卷 再通过安装程序将它们分别安装在C D E 逻辑驱动器上 磁盘分区 47 2 虚拟存储器技术 在单道程序环境下 内存会有很多空闲空间 空分复用则是利用存储器的空闲空间来存放其它程序 以提高内存利用率 单纯的空分复用存储器只能提高内存的利用率 不能实现在逻辑上扩大存储器容量的功能 必须引入虚拟存储技术才能达到此目的 虚拟存储器技术在本质上就是使内存时分复用和空分复用 该技术将一道程序划分成若干部分 物理内存也划分成多个部分 通过 请求调入功能 和 置换功能 每次只把用户程序的一部分调入内存运行 这样便实现了用户程序各个部分分时进入内存运行的功能 从而在逻辑上扩充存储器的容量 48 4异步性 Asynchronism 由于资源等因素的限制 使进程的执行通常不是 一气呵成 而是以 停停等等 的方式运行 内存中的每个进程在何时能获得处理机运行 何时又因提出某种资源请求而暂停 以及进程以怎样的速度向前推进 每道程序总共需要多少时间才能完成等等 都是不可预知的 很可能是先进入内存的作业后完成 而后进入内存的作业先完成 或者说 进程是以人们不可预知的速度向前推进 此即进程的异步性 49 1 4操作系统的主要功能 处理机管理功能存储器管理功能设备管理功能文件管理功能用户接口 50 处理机管理功能 在传统的多道程序设计系统中 处理机的分配和运行 都是以进为基本单位的 因而对处理机的管理 可以归结为对进程的管理 在引入线程的OS中 还包含对线程的管理 也可称为进程管理 51 处理机管理的主要功能是 创建和撤消进程 线程 对诸进程 线程 的运行进行协调 实现进程 线程 之间的信息交换 按照一定的算法把处理机分配给进程 线程 进程控制 进程同步 进程通信 进程调度 处理机调度 52 存储器管理 存储器管理应具有以下功能 内存分配 静态 动态分配方式 内存保护 硬件检查越界 软件处理 地址映射 逻辑 物理地址 硬件支持 内存扩充 虚拟存储技术 53 主要任务 l完成进程提出的I O请求 l为用户进程分配其所需的I O设备 l提高CPU和I O设备的利用率 l提高I O速度 l方便用户使用I O设备 设备管理功能 54 设备管理应具有以下功能 缓冲管理 在设备和CPU之间引入缓冲 可有效地缓和CPU和I O设备速度不匹配的矛盾 提高CPU的利用率 进而提高系统的吞吐量 设备分配 按某种策略将设备分配给用户进程 需设备控制表等数据结构 设备处理 设备处理程序又称为设备驱动程序 基本任务是实现CPU与设备控制器通信 CPU发I O命令 设备控制器发中断请求 55 主要任务 对用户文件和系统文件进行管理 以方便用户使用 并保证文件的安全性 文件管理应具有以下功能 1 文件存储空间的管理2 目录管理3 文件的读 写管理和保护 4 文件管理 56 命令接口 联机命令 脱机命令 程序接口 系统调用 图形接口 GUI 5 用户接口 57 1 5操作系统的结构设计 OS的结构经历了四代变革 第一代的OS是无结构的第二代OS采用了模块式结构第三代OS是层次式结构 传统的操作系统结构 第四代OS采用微内核结构 20世纪80年代后期 58 微内核OS结构 现代OS结构 微内核结构能有效地支持多处理机运行 故非常使用于分布式系统环境 WindowsNT采用微内核结构 在与微内核技术发展的同时 客户 服务器技术 面向对象技术也在迅速发展 把它们应用到基于微内核结构的OS中 便具有了以微内核为OS核心 以客户 服务器为基础 并且采用了面向对象的程序设计方法的特征 59 微内核技术 微内核技术 是指精心设计的 能实现现代OS核心功能的小型内核 OS的变庞大 使对OS的开发 维护和移植变得十分困难 为了减少OS的复杂性 增加OS的可扩展性和可维护性而产生了微内核技术 产生背景 60 1 微内核操作系统的基本概念 1 足够小的内核 微内核是指精心设计的 能实现现代OS最基本的核心功能的部分 2 基于客户 服务器模式 把OS的最基本部分放在内核中 把OS的绝大部分功能放在内核外面的一组服务器 进程 中实现 61 62 3 应用 机制与策略分离 原理 所谓机制 是指实现某一功能的具体执行机构 策略是在机制基础上 借助于某些参数和算法来实现该功能的优化 或达到不同的功能目标 机制处于系统的低层 而策略处于系统的高层 传统OS将机制放在内核低层 策略放在内核高层 微内核OS将机制放在微内核中 策略放在微内核外 4 采用面向对象技术 63 2 微内核的基本功能 1 进程 线程 管理 进程队列属于调度功能的机制部分 放在微内核中 确定 修改优先级 属于策略问题 放在进程管理服务器中 进程 线程 通信 进程切换 线程调度 多处理机之间的同步等功能也放在微内核中 2 低级存储管理 页表机制和地址变换机制在微内核中 实现虚存的策略 包括页面置换算法 内存分配回收策略等放在存储器服务器中 64 3 中断和陷入处理 大多数微内核操作系统都将与硬件紧密相关的一小部分放入问内核中处理 此时 微内核的主要功能 是捕获所发生的中断和陷入事件 并进行相应的前期处理 如进行中断现场保护 识别中断或陷入类型 然后将有关事件的信息转换成消息后 发送给相应的服务器作中断后期处理 65 3 微内核的优点 1 提高了系统的可扩展性 2 增强了系统的可靠性 3 可移植性 4 提供了对分布式系统的支持 5 融入了面向对象技术 66 4 微内核操作系统存在的问题 微内核OS的运行效率有所降低 原因是 在完成一次客户对OS提出的服务请求时 需要利用消息实现多次交互和进行用户 内核模式及上下文的多次切换 解决的办法 重新将一些常用的操作系统基本功能 有服务器移入微内核中 67 第1章复习题 1 计算机操作系统的功能是 A 把源程序代码转换为目标代码B 实现计算机用户之间的相互交流C 完成计算机硬件与软件之间的转换D 控制 管理计算机系统的资源和程序的执行2 不是分时系统的特点 A 多个用户是经过网络连接 同时使用计算机系统B 各用户可同时请求系统服务C 各用户的请求彼此独立 互不干扰D 用户以会话方式控制自己的程序运行 D A 68 3 分时操作系统的主要目的是 A 计算机系统的交互性B 计算机系统的实时性C 计算机系统的可靠性D 提高软件的运行速度4 以下描述与操作系统无关的是 A 方便用户的程序集合B 控制和管理计算机系统的硬件和软件资源C 计算机系统的硬件和软件资源的集合D 合理地组织计算机工作流程 A C 69 5 分时操作系统的特点是 交互性 同时性 独立性 及时性可靠性 交互性 独立性 及时性C 可靠性 实时性 独立性 及时性D 交互性 同时性 独立性 实时性6 下列各项中 不是现代操作系统的主要特征 并发性B 共享性C 确定性D 虚拟性7 在下列操作系统中 对响应时间要求最高的是 A 批处理系统B 分时系统C 实时系统D 网络操作系统 A C C 70 8 对出现的中断事件是由进行处理的 A 硬件B 操作系统C 用户程序D 解释程序9 多道批处理系统的主要缺点是 A CPU利用率低B 不能并发执行C 缺少交互性D 以上都不是10 操作系统是对进行管理的软件 A 系统软件B 系统硬件C 计算机资源D 计算机程序 71 11 设计实时操作系统时 首先要考虑系统的 A 实时性和可靠性B 实时性和灵活性C 灵活性和可靠性D 灵活性和可移植性12 UNIX操作系统是一种多用户的 人机交互的 A 多道批处理系统B 实时系统C 分时系统D 分布式系统13 操作系统在计算机系统中处于之间的位置 A 计算机硬件和软件B 计算机硬件和用户C 处理机和用户D 外部设备和处理机 72 14 操作系统提供给用户程序的接口是 A 命令解释程序B 系统调用C P V操作D 对话框15 分时系统响应时间与有关 A 每个应用进程分配的时间片长度B 进程大小C 就绪进程数目D 就绪进程数目和时间片长度16 在操作系统中 部分属于微内核 A 作业调度软件B 用户命令解释程序C 磁盘文件目录管理软件D 进程通信服务例程 返回总目录 73 第2章进程管理 2 1进程的基本概念2 2进程控制2 3进程同步2 4经典进程同步问题2 5管程机制实现互斥的软件机制和硬件机制 补充 2 6进程通信2 7线程第一次课内上机实验 74 2 1进程的基本概念 程序的顺序执行及其特征程序的并发执行及其特征进程的特征与状态进程控制块 75 2 1 1程序的顺序执行及其特征 顺序执行包含两层含义 对于多个用户程序来说 所有程序是依次执行的 外部顺序性 对于一个程序来说 它的所有指令是按序执行的 内部顺序性 76 程序顺序执行的特征 1 顺序性 处理机的操作严格按照程序所规定的顺序执行 即每一操作必须在下一操作开始之前结束 或者说下一操作必须在当前操作结束后才能开始 2 封闭性 程序是在封闭的环境下执行的 即 程序运行时独占全机资源 资源的状态 除初始态外 只有本程序才能改变它 程序一旦开始执行 其执行结果不受外界影响 3 可再现性 只要程序执行时的环境和初始条件相同 当程序重复执行时 都将获得相同的结果 77 程序的并发执行包括两层含义 对于一个程序来说 它的所有指令是按序执行的 内部顺序性 对于多个程序 进程 来说 所有进程是交叉执行的 外部并发性 2 1 3程序的并发执行及其特征 78 1 间断性 程序在并发执行时 由于它们共享系统资源 以及为完成同一任务而相互合作 致使这些并发执行的程序之间形成了相互制约的关系 互斥关系 同步关系 相互制约导致并发执行的程序具有 执行 暂停 执行 这种间断性活动规律 2 失去封闭性 程序在并发执行时 由于多个程序共享系统资源 因而这些资源的状态将由多个程序来改变 致使程序的运行已失去了封闭性 某程序的执行时 会受到其他程序的影响 79 3 不可再现性 与时间有关的错误 程序在并发执行时 由于失去了封闭性 也将导致其失去可再现性 例如 有两个循环程序A和B 它们共享一个变量N L1 N N 1 gotoL1 L2 print N N 0 gotoL2 程序A 程序B 程序A和B并发执行时 可能出现下述三种情况 设N的值为10 1 N N 1在print N 和N 0之前 此时得到的N值分别为11 11 0 2 N N 1在print N 和N 0之后 此时得到的N值分别为10 0 1 3 N N 1在print N 和N 0之间 此时得到的N值分别为10 11 0 上述三种情况中 1 2 结果正确 3 结果出错 可见计算结果已与并发程序的执行速度 推进速度 有关 从而使程序执行失去了可再现性 80 2 1 4进程的特征与状态 1 进程的定义和特征 进程是程序在一个数据集上的运行过程 是系统进行资源分配和调度的一个独立单位 传统OS的定义 定义 1 结构特征 程序段 相关的数据段 PCB三部分构成了进程实体 2 动态性 进程的实质是进程实体的一次执行过程 故动态性是进程的最基本特征 进程的特征 81 4 独立性 在传统的OS中 独立性是指进程实体是一个能独立运行 独立分配资源和独立接受调度的基本单位 5 异步性 是指进程按各自独立的 不可预知的速度向前推进 或说进程实体按异步方式运行 3 并发性 这是指多个进程实体同存于内存中 且能在一段时间内同时运行 82 进程的三种基本状态 1 就绪 Ready 状态 当进程已分配到除CPU以外的所有资源后 只要再获得CPU 便可立即执行 进程这时的状态称为就绪状态 2 执行 Running 状态 进程已获得CPU 其程序正在执行 3 阻塞 Blocked 状态 正在执行的进程由于发生某事件而暂时无法继续执行时 便放弃处理机而处于暂停状态 亦即进程的执行受到阻塞 把这种暂停状态称为阻塞状态 或等待状态 83 进程的三种基本状态的转换 进程调度 就绪态 执行态时间片完 执行态 就绪态请求I O 执行态 阻塞态I O完成 阻塞态 就绪态 引起进程状态转换的典型事件 84 挂起状态 有些系统除了进程的三种基本状态外 还有挂起状态 1 引入挂起状态的原因 1 终端用户的请求 2 父进程请求 3 负荷调节的需要 4 操作系统的需要 当终端用户在自己的程序运行期间发现有可疑问题时 希望暂停执行 希望考察和修改子进程 或协调各子进程间的活动时 实时系统中工作负荷较重时 系统可把一些不重要的进程挂起 操作系统有时希望挂起某些进程 以便检查运行中的资源使用情况或进行记账 85 2 具有挂起状态系统的进程状态的转换 活动就绪 静止就绪 活动阻塞 静止阻塞 静止就绪 活动就绪 静止阻塞 活动阻塞 挂起原语Suspend 激活原语Active 86 为了描述和控制进程的运行 系统为每个进程定义了一个数据结构 进程控制块 进程控制块是进程实体的一部分 是操作系统中最重要的记录型数据结构 1 PCB作用 使一个在多道程序环境下不能独立运行的程序 含数据 成为一个能独立运行的基本单位 一个能与其它进程并发执行的进程 或者说 OS是根据PCB来对并发进程进行控制和管理的 例如 进程调度 现场保护和恢复 进程同步和通信 PCB是进程存在的唯一标志 2 1 5进程控制块 PCB 87 2 进程控制块中的信息 PCB中记录了操作系统所需的 用于描述进程当前情况以及控制进程运行的全部信息 具体包括下述四方面的信息 1 进程标识符 内部标识符 进程号 外部标识符 名 父进程标识及子进程标识 用户标识 2 处理机状态 处理机状态信息主要由处理机的各种寄存器中的内容组成的 寄存器包括 通用寄存器 指令计数器 程序状态字 PSW 寄存器 用户栈指针 保护 恢复现场 当处理机被中断时 这些信息都必须保存到PCB中 以便该进程重新执行时 能从断点继续执行 88 3 进程调度信息 在PCB中还存放一些与进程调度和进程对换有关的信息 包括 进程状态 作为调度和对换时的依据 进程优先级 由于描述进程使用处理机的优先级别的一个整数 优先级高的进程优先获得处理机 进程调度所需的其它信息 它们与所采用的进程调度算法有关 事件 即阻塞原因 89 4 进程控制信息 程序和数据的地址 指程序和数据所在的内存或外存首地址 进程同步和通信机制 如信号量 消息队列指针等 它们可能全部或部分地存放在PCB中 资源清单 是一张列出了除CPU外的 进程所需的全部资源及已经分配到该进程的资源的清单 链接指针 它给出本进程 PCB 所在队列中下一个进程的PCB的首址 90 3 进程控制块的组织方式 常用的组织方式有两种 链接方式和索引方式 1 链接方式 把具有同一状态的PCB 用其中的链接字链接成一个队列 形成 就绪队列 阻塞队列 空白队列等 91 2 索引方式 系统根据所有进程的状态建立几张索引表 如 就绪索引表 阻塞索引表等 索引表的首址记录在专用单元中 每个索引表的表目中 记录具有相应状态的某个PCB的首址 92 2 2进程控制 进程控制是进程管理中最基本的功能 进程控制包括 创建进程 终止进程 进程状态转换 进程控制是由OS的内核完成的 93 2 2 1进程的创建 1 引起创建进程的事件 用户登录 作业调度 提供服务 当用户进程提出某种请求后 系统将专门创建一个进程来提供用户所需的服务 如 文件打印 上述三种情况 都是由系统内核为它创建一个新进程 应用请求 是基于应用进程的需求 由应用进程自己创建一个新进程 以便新进程以并发运行方式完成特定任务 94 2 进程的创建 调用进程创建原语Create 按下述步骤创建一个进程 1 申请空白PCB 2 为新进程分配资源 主要是内存空间 3 初始化PCB 包括 初始化标识信息初始化处理机状态信息 程序计数器 堆栈指针等 进程状态 就绪或静止就绪 优先级等 初始化处理机控制信息 4 将新进程插入就绪队列 95 1 引起进程终止的事件 正常结束 外界干预 越界错误保护错 试图访问不允许访问的资源或文件 或者以不适当方式访问非法指令特权指令错 用户程序试图执行只允许OS执行的指令运行超时等待超时算术运算错 被0除I O故障 操作员或操作系统干预 如发生死锁 父进程请求 父进程终止 2 2 2进程的终止 异常结束常见的异常结束事件 96 2 进程的终止过程 OS调用终止原语 按下述过程终止进程 根据被终止进程的标识 从PCB集合中找除该进程的PCB 读出该进程状态 若被终止进程正处于执行状态 应立即终止其执行 并置调度标志为真 用于指示该进程被终止后应重新进行调度 若该进程还有子孙进程 应将其所有子孙进程终止 以防止它们成为不可控进程 将被终止进程的所有资源 或者归还给其父进程 或者归还给系统 将被终止进程 它的PCB 从所在队列中移出 等待其他进程来搜索信息 97 2 2 2进程的阻塞和唤醒 1 引起进程阻塞和唤醒的事件 请求系统服务 无新工作可做 当执行进程请求OS服务时 由于某种原因 OS并不立即满足该进程的请求时 该进程只能转变为阻塞状态来等待 如 进程请求打印机 系统往往设置一些具有特定功能的系统进程 每当这种进程完成任务后 便把自己阻塞起来以等待新任务到来 如 系统中发送数据的进程 启动某种操作 当进程启动某种操作后 如果该进程必须在该操作完成后才能继续执行 则必须先使该进程阻塞 以等待操作完成 如 启动了某I O设备 新数据尚未到达 对于相互合作的进程 如果其中一个进程需要获得另一个 合作 进程提供的数据才能运行以对数据进行处理 则只要其所需数据尚未到达 该进程只有阻塞 等待 如 98 2 进程阻塞过程 调用阻塞原语block把自己阻塞 主动行为 阻塞 block 过程 立即停止执行 把PCB中进程状态由 执行 改为 阻塞 将PCB插入具有相同事件的阻塞队列 转进程调度程序 将处理机分配给某个就绪进程 并进行进程切换 保留被阻塞进程的处理机状态 在PCB中 再按新进程的PCB中处理机状态设置CPU的环境 99 3 进程唤醒过程 调用唤醒原语wakeup 将等待事件的进程唤醒 唤醒原语执行过程 将被唤醒进程的PCB从阻塞队列移出 将其PCB中进程状态由 阻塞 改为 就绪 将改PCB插入到就绪队列中 block 和wakeup 是成对的 100 1 进程的挂起 当出现了引起进程挂起的事件时 用户进程请求将自己挂起 或父进程请求将子进程挂起 系统将用挂起原语suspend 将指定进程或处于阻塞状态的进程挂起 挂起原语的执行过程 检查被挂起进程的状态 若处于活动就绪或执行状态 则将其转为静止就绪 若处于活动阻塞 则将其转为静止阻塞 把该进程的PCB复制到某指定内存区域 为方便用户或父进程考查该进程的运行状态 若该进程正在执行 则转进程调度程序重新调度 2 2 4进程的挂起和激活 101 2 进程的激活 当发生激活进程的事件时 如父进程或用户请求激活指定进程 而内存中已有足够空间时 系统利用激活原语active 将指定进程激活 激活过程是 将进程从外存调入内存 若是静止就绪 则改为活动就绪 若是静止阻塞 则改为活动阻塞 若采用的是抢占式调度策略 则应检查被激活就绪进程的优先级 若其优先级比先行执行进程高 则应将处理机分配给被激活进程 检查该进程现行状态 102 2 3进程同步 由于进程的异步性 尤其是它们竞争临界资源时 可能会给系统造成混乱 进程同步的主要任务 是使并发执行的进程之间能有效地共享资源和相互合作 从而使程序的执行具有可再现性 2 3 1进程同步的基本概念2 3 2信号量机制2 3 3信号量的应用 103 2 3 1进程同步的基本概念 1 两种形式的制约关系 1 间接制约关系 间接制约关系源于资源共享 如 共享打印机 进程互斥 2 直接制约关系 源于进程间的合作 如 进程同步 2 临界资源 在一段时间内只允许一个进程访问的资源 即仅当一个进程访问完并释放该资源后 才允许另一个进程访问的资源 称为临界资源或独占资源 如 打印机 磁带机 共享变量 队列 104 生产者 消费者问题 例 生产者 消费者问题 著名的进程同步问题 共享变量 临界资源 循环缓冲区 生产者投放一个产品后 输入指针in加1 in in 1 n n是缓冲区个数 整型常量 in初值为0 消费者每取出一个产品 输出指针out加1 out out 1 n out初值为0 引入一个共享变量counter 初值为0 生产者投放一个产品 counter加1 counter n时不能再投放产品 消费者每取一个产品 counter减1 counter 0时不能再取出产品 前面交通观察站例子亦然 以下是软件临界资源的例子 105 processproducer while condition produceaniteminnextp while counter n no op no op表示空操作buffer in nextp in in 1 n counter counter 1 生产者进程算法如下 106 processconsumer structitemnextc while condition while counter 0 no op nextc buffer out out out 1 n counter counter 1 consumetheiteminnextc 消费者进程算法如下 107 上面的生产者程序和消费者程序 在顺序执行时其结果是正确的 但若并发执行时 可能会出现差错 问题在于这两个进程共享变量counter 生产者做counter counter 1操作 消费者做counter counter 1操作 这两个操作在机器语言实现时 常可用下面的形式描述 生产者执行的操作 register1 counter register1 register1 1 counter register1 消费者执行的操作 register2 counter register2 register2 1 counter register2 108 假设某一时刻counter的值为5 生产者和消费者同时对counter操作 按下述顺序执行 register1 counter 生产者取得counter的当前值为5 register1 register1 1 生产者将该值增1变为6 register2 counter 消费者取得counter的当前值为5 register2 register2 1 消费者将该值减1变为4 counter register2 消费者保存counter的新值4 counter register1 生产者保存counter的新值6 最终counter的值为6 正确的值应是5 出现了差错 学生考虑 什么情况会出现counter最终值为4的情况 解决此问题的关键 是应将变量counter作为临界资源处理 亦即让生产者进程和消费者进程互斥地访问变量counter 109 2 3 1进程同步的基本概念 3 临界区 criticalsection 每个进程中访问临界资源的那段代码称为临界区 不论是硬件临界资源 还是软件临界资源 多个进程必须互斥地对它们访问 显然 若能保证诸进程互斥地进入自己的临界区 便可实现诸进程对临界区的互斥访问 为此 每个进程在进入临界区之前 应先对欲访问的临界资源进行检查 看是否正被访问 如果此刻该资源未被访问 便可进入临界区对该临界资源进行访问 并设置它正被访问的标志 如果此刻它正被访问 则本进程不能进入临界区 定义 进程互斥的定义 进程互斥 不允许两个或两个以上进程同时访问同一个临界资源 进程互斥 不允许两个或两个以上进程同时进入相关临界区 110 因此必须在临界区前增加一段用于上述检查的代码 把这段代码称为进入区 entrysection 相应地 在临界区后面也要加上一段称为退出区 exitsection 的代码 用于将临界区正被访问的标志恢复为未被访问的标志 repeat非临界区进入区临界区退出区非临界区untilfalse 一般结构 进入区 和 退出区 的不同构成方法 形成了各种不同的同步机制 111 4 同步机制应遵循的原则 为了实现各进程互斥地进入自己的临界区 一般是在系统中设置专门的同步机制来协调各进程间的运行 所有同步机制都应遵循如下四条准则 空闲让进 当无进程处于临界区时 表明临界资源处于空闲状态 应允许一个请求进入临界区的进程立即进入自己的临界区 以便有效地利用临界资源 空闲让进 忙则等待 有限等待 让权等待 112 有限等待 让权等待 对要求访问临界资源的进程 应保证在有限的时间内能进入自己的临界区 以免陷入 死锁 状态 不死等 不互相阻塞 当进程不能进入自己的临界区时 应立即释放处理机 以免进程陷入 忙等 不忙碌等待 忙则等待 当已有进程进入临界区时 表明临界资源正在被访问 因而其他试图进入临界区的进程必须等待 以保证对临界资源的互斥访问 113 2 3 2信号量机制 信号量 Semaphores 机制是一种卓有成效的进程同步工具 信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中 信号量机制的发展 整型信号量 记录型信号量 AND型信号量 信号量集 忙等 未遵循 让权等待 准则 略 后边重点介绍 不作基本要求 后面只做简单介绍 114 2 记录型信号量 需要一个用于代表临界资源数目的整型变量value 还要一个在该资源上阻塞的队列 链表 指针L 故信号量应采用记录型 C语言中为结构型 的结构 structsemaphore intvalue structsemphore L 记录型信号量的结构定义 信号量除初始化外 只能通过两个原子操作 称为原语 wait S 和signal S 来访问 它们以前被称为P V操作 下页介绍wait和signal操作 115 wait和signal操作可用C C 语言描述如下 voidwait semaphoreS S value S value 1 if S value 0 block S L 让权等待 voidsignal semaphoreS S value S value 1 if S value 0 wakeup S L 唤醒第一个等待的进程 P S V S S value的初值表示系统中某类资源的数目 116 wait和signal操作的物理意义 对信号量S的每次wait操作 意味着进程请求一个该类临界资源 因此描述为S value S value 1 当S value 0时 表示该类资源已分配完 因此进程应调用block原语进行自我阻塞 放弃处理机 并插入到信号量链表S L 阻塞队列 中 可见该机制遵循了 让权等待 准则 类似地 可以解释signal操作 S value的初值表示系统中某类资源的数目 资源信号量 S value的初值为1 表示只允许一个进程访问 此时信号量转化为互斥信号量 117 作业1 进程同步 1 2011全国试题 有两个并发进程P1和P2 共享初值为1的变量x P1对x加1 P2对x减1 加1和减1操作的指令序列分别如下所示 加1操作loadR1 x 取x到寄存器R1中incR1storex R1 将R1的内容存入x 减1操作loadR2 xdecR2storex R2 两个操作完成后 x的值 A 可能为 1或3B 只能为1C 可能为0 1或2D 可能为 1 0 1或2 作业中部分题目讲解 C 118 3 S queue S value是信号灯S的两个组成部分 当S queue为空时 S value的值是 A S value 0B S value 0C S value 1D Svalue 04 如果信号量的当前值为 3 则表示系统中在该信号量上有个等待进程 7 设与某资源关联的信号量初值为3 当前值为1 若M表示该资源的可用个数 N表示等待该资源的进程数 则M N分别是 2010年全国考研试题 A 0 1B 1 0C 1 2D 2 0 B D 3 119 设有n个进程使用同一个共享变量 如果最多允许m m n 个进程同时进入相关临界区 则信号量的变化范围是 n n 1 n mm m 1 1 0 1 m nm m 1 1 0 1 m n 1m m 1 1 0 1 m n 1 B 120 3 AND型信号量 不作基本要求 Swait S1 S2 Sn ifS1 1从所有Si等待队列中移出进程并置入就绪队列 以便下次重新执行Swait操作 121 4 信号量集 不作基本要求 Swait S1 t1 d1 S2 Sn tn dn ifS1 t1从所有Si等待队列中移出进程并置入就绪队列 122 2 3 3信号量的应用 1 利用信号量实现进程互斥 方法要点 为每个临界资源设置一个互斥信号量mutex 其初值为1 各进程访问该资源前执行wait mutex 操作 离开临界区时执行signal mutex 操作 请看下页的例子 非临界区wait mutex 进入区临界区signal mu