前趋图和程序执行
-
前趋图
- 定义:
前趋图是指一个有向无循环图,可记为 DAG,它用于描述进程之间执行的先后顺序 - 图形表示:
- 定义:
-
程序的执行
程序顺序执行时,系统资源的利用率很低- 程序顺序执行时的特征
- 顺序性
- 封闭性
- 可再现性
只有在不存在前趋关系的程序之间才有可能并发执行
- 程序并发执行时的特征
- 间断性
- 失去封闭性
- 不可再现性
- 程序顺序执行时的特征
进程的描述
为了能使程序并发执行,并且可以对并发执行的程序加以描述和控制,引入了进程概念
-
进程的定义和特征
- 进程的定义
对于进程的定义,从不同的角度可以有不同的定义,其中较典型的定义有:- 进程是程序的一次执行
- 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
- 进程是具有独立功能的程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位
- 进程的特征
- 动态性:动态性是进程的最基本的特征
- 并发性
- 独立性
- 异步性:进程是按异步方式运行的,即按各自独立的,不可预知的速度向前推进
- 进程实体
通常,进程实体由程序控制块(PCB)、程序段、数据段三部分组成
- 进程的定义
-
进程的状态及转换
-
进程有三种基本状态:
- 就绪状态:进程已处于准备好运行的状态,已分配到除CPU以外的所有必要资源
- 执行状态:进程已获得CPU,其程序正在执行的状态
- 阻塞(等待)状态:正在执行的进程由于某事件暂时无法继续执行的状态
-
引入进程的创建状态和终止状态
- 创建状态:
- 由进程申请一个空白PCB
- 向PCB中填写用于控制和管理进程的信息
- 为该进程分配运行时所必须的资源
- 终止状态:当一个进程到达了自然结束点,或出现了无法克服的错误
- 删除该进程,将其PCB清零
- 将空白PCB返回系统
- 创建状态:
-
-
挂起操作和进程状态的转换
当挂起操作作用于某个进程时,该进程将被挂起,意味着此时该进程处于静止状态。如果进程正在执行,它将暂停执行。若原本处于就绪状态,则该进程此时暂不接受调度与挂起搡作对应的操作是激活操作- 引入挂起原语操作后三个进程状态的转换
- 活动就绪→静止就绪
- 活动阻塞→静止阻塞
- 静止就绪一活动就绪
- 静止阻塞一活动阻塞
- 引入挂起操作的原因
- 终端用户的需要:暂停自己程序的运行
- 父进程请求:挂起自己的某个子进程
- 负荷调节的需要
- 操作系统的需要
- 引入挂起操作后五个进程状态的转换
- 引入挂起原语操作后三个进程状态的转换
-
进程控制块(PCB)
- 概念:
PCB 是一记录型数据结构,它作为进程实体的一部分,记录了操作系统所需的、用于描述进程 的当前情况以及管理进程运行的全部信息 - PCB的作用
- 作为独立运行基本单位的标志
- 能实现间断性运行方式
- 提供进程管理所需要的信息
- 提供进程调度所需要的信息
- 实现与其他进程的同步与通信
- 进程控制块中的信息
- 概念:
处理机状态 | 进程调度信息 | 进程控制信息 |
---|---|---|
通用寄存器 | 进程状态 | 程序和数据的地址 |
指令计数器 | 进程优先级 | 进程同步和通信机制 |
程序状态字 | 进程调度所需的其他信息 | 资源清单 |
用户栈指针 | 事件 | 链接指针 |
- 进程控制块的组织方式
- 线性方式:系统中所有的PCB都组织在一张线性表中,首址存放在内存的专用区域中
- 链接方式:把具有相同状态进程的PCB通过PCB中的链接字链接成一个队列
- 索引方式:
根据所有进程状态的不同,建立几张索引表,各索引表的首址存放在内存的一些专用单元中
进程控制
进程控制是进程管理中最基本的功能,主要包括
- 创建新进程
- 终止已完成的进程
- 将因发生异常情况而无法继续运行的进程置于阻塞状态
- 负责进程运行中的状态转换
等功能
进程的创建
- 引起创建进程的事件
- 用户登录
- 作业调度
- 提供服务
- 应用请求
- 进程的创建
- 申请空白PCB,从PCB集合中索取一个空白PCB
- 为新进程分配其运行所需的资源,包括物理和逻辑资源
- 初始化进程控制块PCB
- 初始化标识信息
- 初始化处理机状态信息
- 初始化处理机控制信息
- 如果进程就绪队列能够接纳新进程,将新进程插入就绪队列
进程的终止
- 引起进程终止的事件
- 正常结束
- 异常结束
- 外界干预
- 进程的终止过程
- 根据被终止进程的标识符PID,检索出该进程的PCB,读出该进程的状态
- 立即终止该进程的执行
- 将其所有子孙进程终止
- 将该进程所拥有的全部资源归还给其父进程或系统
- 将PCB从所在队列中移出
进程的阻塞与唤醒
- 引起进程阻塞和唤醒的事件
- 向系统请求共享资源失败
- 等待某种操作完成
- 新数据尚未到达
- 等待新任务到达
进程同步
- 进程同步的基本概念
- 进程同步机制的主要任务
对多个相关进程在执行次序上进行协调,使并发执行的诸进程之间能按照一定的规则(或时 序)共享系统资源,并能很好地相互合作,从而使程序的执行具有可再现性 - 两种形式的制约关系
- 间接相互制约关系:由于临界资源,必须保证多个进程对之只能互斥地访问
- 直接相互制约关系:源于进程之间的相互合作
- 临界资源
一次仅允许一个进程使用的资源称为临界资源 - 临界区
将在每个进程中访问临界资源的那段代码称为临界区 - 同步机制应遵循的规则
- 空闲让进:临界资源处于空闲状态,允许一个进程立即进入临界区
- 忙则等待:临界资源正在被访问,其他试图进入的进程必须等待
- 有限等待:保证访问临界资源的进程在有限时间内能进入自己的临界区
- 让权等待:进程不能进入临界区时,立即释放处理机
- 进程同步机制的主要任务
- 硬件同步机制
- 关中断
- 利用 Test-and-Set 指令实现互斥
- 利用 Swap 指令实现进程互斥
- 管程机制
- 定义
一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据 - 组成
- 管程的名称
- 局部于管程的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 对局部于管程的共享数据设置初始值的语句
- 定义
进程通信
- 进程通信的概念
- 进程通信的定义
进程通信是指进程之间的信息交换 - 进程通信的分类
进程通信可分为高级进程通信和低级进程通信两种
- 进程通信的定义
- 高级进程通信的类型
- 共享存储器系统
- 基于共享数据结构的通信方式
- 基于共享存储区的通信方式
- 管道通信系统
- 消息传递系统
- 直接通信方式
- 问接通信方式
- 客户机-服务器系统
- 共享存储器系统
线程的基本概念
线程——比进程更小的基本单位,用来提高程序并发执行的程度,进一步改善系统的服务质量
-
线程的引入
- 进程的两个基本属性
- 进程是一个可拥有资源的独立单位
- 进程同时又是一个可独立调度和分派的基本单位
- 线程引入原因
- 减少程序并发执行所需付出的时空开销,使操作系统具有更好的并发性
- 进程的两个基本属性
-
线程与进程的比较
- 调度的基本单位
- 在传统的OS中,进程是作为独立调度和分派的基本单位,因而进程是能独立运行的基本单位
- 而在引入线程的OS中,已把线程作为调度和分派的基本单位,因而线程是能独立运行的基本单位
- 并发性
不同进程之间、在一个进程中的多个线程之间或者不同进程中的线程之间都能并发执行 - 拥有资源
- 进程是系统中拥有资源的一个基本单位
- 线程本身并不拥有系统资源,而是仅有一点必不可少的、能保证独立运行的资源
- 多个线程共享该进程所拥有的资源,还可以访问进程所拥有的资源
- 独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多 - 系统开销
- 创建或撤消进程时所付出的开销明显大于线程创建或撤消时所付出的开销
- 线程的切换代价也远低于进程的切换代价
- 调度的基本单位
-
线程的状态和线程控制块
- 线程运行的三个状态
- 执行状态
- 就绪状态
- 阻塞状态
- 线程控制块TCB
线程控制块通常有这样几项信息
- 线程标识符
- 一组寄存器
- 线程运行状态
- 优先级
- 线程专有存储区
- 信号屏蔽
- 堆栈指针
在多线程OS中,线程作为独立运行(或称调度)的基本单位;而进程仍是资源分配的基本单位
- 线程运行的三个状态
线程的实现方式
- 内核支持线程KST
- 用户级线程ULT
- 组合方式
组合方式下包括三种不同的模型