1. 进程的定义
在引入多道程序技术之后,为了方便对各个任务进行管理,引入了进程和进程实体的概念.
进程只是一种概念,是一个程序在处理机上运行是发生的所有活动(动态性).是系统进行资源分配的一个独立单位.
而我们通常所讲的进程是指进程实体.之前的进程是进程实体的运行过程.
每一个进程实体都有==其进程控制块PCB,程序段==(所要执行的程序代码)和==数据段==(执行任务需要的变量,运算数据).
(1). PCB
- 进程描述信息
- 进程标识符PID
- 用户标识符UID
- 进程控制和管理信息
- 进程当前状态
- 进程优先级
- 资源分配清单
- 程序段指针
- 数据段指针
- 分配的各种硬件资源
- 处理机相关信息
- 各种寄存器的值
(2). 进程的组织
1). 链接方式
操作系统按照进程的状态将PCB分为多个队列,操作系统持有指向各个队列的指针.
执行指针,就绪队列指针,阻塞队列指针
2). 索引方式
根据进程状态的不同,建立几张索引表,操作系统持有指向各个索引表的指针.
索引表中的表项指向PCB
执行指针,就绪表指针,阻塞表指针
(3). 进程的特性
- 动态性:进程是动态的产生,变化和消亡的,只是一次执行过程.
- 并发性:内存中有多个进行实体,可并发执行
- 独立性:进程是能独立运行,独立获得资源,独立接受调度的基本单位
- 异步性:各个进程之间的执行不需要等待
- 结构性:每个进程的结构都是一致的,都是PCB+程序段+数据段
2. 进程状态和转换
(1). 进程的三种基本状态:
- 运行态:当前得到CPU资源的进程(多核处理机可以同时有多个进程处于运行态,被称为并行运行)
- 就绪态:得到了所需的所有资源,但是还没有被分配CPU运行时间,所以没有运行的进程
- 阻塞态:在等待某一时间(分配资源,等待硬盘操作等等)而没有运行的进程
(2). 另外两种状态:
- 创建态:进程刚刚被创建的状态
- 终止态:进程被撤销时的状态
(3). 状态的转换
进程在创建时是创建态,一经创建立即进入就绪态.当就绪态的线程被分配到了CPU执行时间时,进入运行态,运行态的进程使用完被分配的时间或者CPU被强占后重新变成就绪态.运行态的进程当使用==系统调用==申请系统资源或者等待某个事件发生时,进入阻塞态,阻塞态的进程在得到资源或者响应的事件发生后会进入就绪态等待分配CPU运行时间.
3. 进程控制
进程控制就是实现进程状态的转换.
进程控制是通过PCB在就绪队列和阻塞队列中的出队和入队实现的.其中使用==原语保证进程控制的原子性==.而==原语则是采用关中断和开中断两个指令实现的==.
进程控制相关的原语都做了3件事情:
- 更新PCB中的信息
- 修改进程状态标志
- 保存运行环境或者从PCB恢复运行环境
- 将PCB插入到相应的状态队列
- 分配/回收资源
4. 进程通信
进程通信就是进程时间的信息交换.但进程之间的内存空间是相互独立的.进程间通信保证了进程间的安全通信.
(1). 共享存储
操作系统为两个进程分配一片可以共享访问的内存空间,两个进程可以使用这个共享空间进行信息交换.
两个进程对共享空间的访问必须是互斥的.
1). 基于数据结构的共享
速度较慢,是一种低级的通信方式
2). 基于存储区的共享
由两个进程决定共享空间中的数据格式,相比之下这种方式速度更快,是一种更高级的通信方式.
(2). 管道通信
在两个进程中开辟一个管道,用于信息的传输.
管道只能由一个进程填满,再由一个进程全部取出.一个管道不能双向通信.(半双工)
各个进程对管道的访问互斥.
(3). 消息传递
进程之间以格式化消息传递信息,进程使用==消息的发送和接收原语==进行数据交换
1). 直接通信方式
发送进程直接将消息挂到接收进程的消息缓冲队列上
2). 间接通信方式
消息先发送到中间实体中,消息头中包含了消息的接收进程等等信息.
接收进程会主动在中间实体中查阅信息.
5. 线程
(1). 线程的概念
线程是一个基本的CPU执行单元,也是程序执行流的最小单位.
线程间的并发不需要切换进程环境,系统开销小.
线程的特性:
- 线程是处理机调度的单位
- 多核CPU可以同时运行不同的多个线程
- 线程有线程ID,线程控制块TCB
- 线程也有就绪,阻塞,运行三态
- 线程不占有系统资源
- 同一个进程的线程共享进程的内存空间
(2). 线程的实现方式
用户级线程:由应用程序通过线程库实现.用户级线程的线程切换可以再用户态下完成,无需操作系统的干预.
内核级线程:线程的管理工作由操作系统内核完成,所以线程的切换都需要在核心态下完成.
(3). 多线程模型
- 多对一模型:一个进程的多个用户级线程映射到一个内核级线程
- 优点:用户级线程的切换不需要CPU切换到核心态
- 缺点:用户级线程一旦被阻塞,整个进程都会被阻塞
- 一对一模型:每一个用户级线程都对应一个内核级线程
- 优点:一个线程被阻塞后,别的线程还可以继续执行,并发能力强
- 缺点:管理成本高
- 多对多模型:n个用户级线程映射到m和内核级线程(n >= m)
- 克服了多对一模型并发度不高的确定,也克服了一对一模型中进程管理开销太大的缺点
6. 处理机调度
(1). 高级调度
也叫作业调度,将作业从外存(磁盘,硬盘,U盘等等)调入内存(内存条)中,显示的应用于早起的批处理程序.
准确的讲:高级调度按照一定原则从后备队列的作业中挑选出一个,为它们分配内存等必要资源,并建立响应的进程(建立PCB),并使它们获得竞争处理机的权利.
作业调入时会建立相应的PCB,作业调出时才会撤销PCB.
(2). 中级调度
虚拟存储技术:将一部分磁盘空间划为交换区,内存中暂时不会用到的数据会移动到这里进行存储,以节省内存空间.
暂时被调到外存中等待的进程状态被称为挂起状态.
中级调度就是决定要将那个处于挂起状态的进程重新==调入==内存.
(3). 线程状态的七状态模型
(4). 低级调度
低级调度也叫进程调度,是按照某一种策略从就绪队列中选取一个进程,将处理机分配给它.
(5). 联系和对比
7. 进程调度
(1). 进程调度的时机
当前运行的进程==主动==放弃处理机:进程正常终止,发生异常,主动请求阻塞(等待I/O)
当前运行的进程==被动==放弃处理机:分配的时间片用完,有更紧急的事情处理(中断),被强占CPU资源
不能进行进程调度的情况:
- 处理中断的过程中
- 处于内核程序临界区中(普通临界区可以被调度)
- 原子操作过程中(原语)
(2). 进程调度的方式
- 抢占式
- 只允许进程主动放弃处理机
- 实现简单,系统开销小
- 无法及时处理紧急任务,适合早期的批处理程序
- 非抢占式
- 当一个进程在处理机上运行时,出现了另一个更紧急的进程需要使用处理机,那么此时运行的进程会让出CPU权限.
- 可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能
- 适用于分时操作系统,实时操作系统
(3). 调度算法的评价指标
- CPU利用率 = 忙碌时间/总时间
- 系统吞吐量 = 完成的作业数量/花费时间
- 周转时间 = 作业完成时间-作业提交时间
- 平均周转时间 = 各作业周转时间之和/作业数
- 带权周转时间 = 作业周转时间/作业实际运行时间(永远大于1)
- 平均带权周转时间 = 各作业带权周转时间之和/作业数
(4). 调度算法
1). 先来先服务(FCFS)
按照作业到达后背队列的顺序进行执行,不可抢占,不会发生饥饿
优点:公平,实现简单
缺点:对长作业有利,对短作业不利
2). 短作业优先(SJF)
每次选择作业时,选择当前所有作业中最短的作业执行.当作业时间一致时,先执行早到达的.会导致饥饿
优点:平均等待时间和平均周转时间短
缺点:对短作业有利,对长作业不利,会产生饥饿现象
3). 高响应比优先(HRRN)
每次选择作业是计算响应比((等待时间+要求服务时间)/要求服务时间).(响应比<=1)
综合考虑等待时间和运行时间,无明显缺点.不会导致饥饿.
4). 时间片轮转(RR)
时间片是将CPU每次分配的时间设置为一样的,公平地为每个进程轮流(根据作业到达的顺序)分配时间片.
根据时钟装置发出的时钟中断来进行抢占,所以是抢占式的.
不会导致饥饿.
优点:公平,响应快,适用与分时操作系统
缺点:不区分任务的紧急程度,由于高频度的进程切换会有一定开销.
时间片过短会导致开销过大,时间片过长会导致退化成先来先服务.
5). 优先级调度算法
按照优先级进行选择
优点:区分任务的紧急成都,适用于实时操作系统
缺点:可能导致饥饿.
6). 多级反馈队列
设置多级队列,优先级从高到低,时间片从小到大.
新进程直接进入一级队列
分配完时间片进入下一级队列,被处理机抢占的进程重新回到自己所在的队列尾.
当前一级队列为空时,才会为下一级队列中的进程分配时间片.
到最后一级的队列就不会再向下降级了.
优点:公平,可以灵活调整对进程的偏好程度(不降级的设置)
缺点:会造成饥饿
8. 实现进程互斥
(1). 软件实现
1). 单标志法
在一个进程访问完临界区后将权限给另一个进程.
当一个进程一直不访问临界区,那么另一个进程也无法访问.违背空闲让进
2). 双标志先检查法
两个进程都有一个标志位
进入临界区前会先进行标志位检查,然后将另一个进程的标志位改为等待
退出临界区将另一个进程的标志位改为可以访问
进入临界区和对其他进程上锁不是原子操作,所以可能造成多个进程同时进入临界区.违反忙则等待
3). 双标志后检查法
对标志的自旋检查放在了更改另一个进程标志位之后.
可能两个进程都更改了彼此的标志位,违反了空闲让进和有限等待.
4). Peterson算法
设置一个变量表示那个进程优先进入临界区,在标志位检查之前更改为对方
- 主动争取
- 主动谦让
- 检查自己是不是最后谦让的那个进程,如果是则让出机会.
(2). 硬件实现
1). 中断屏蔽
原语的实现方式
简单高效,但不适合用户进程,内核态不可随意暴露给用户
2). TestAndSet指令
原子性的进行上锁和检查操作
3). Swap指令
原子性的交换两个值
逻辑上与TAS指令一样
8. 信号量机制
信号量其实就是一个变量,可以用来表示系统中的某种资源的数量.
使用wait(S)原语减少一个信号量(相当于获取锁),使用signal(S)原语增加一个信号量(解锁).
通常也简称为P(S),V(S)操作
(1). 整型信号量
信号量为整型变量
wait(S)操作自旋等待信号量大于0时,信号量-1,退出
signal(S)操作给信号量+1
(2). 记录型信号量
信号量中除了定义整型信号量值,还定义了等待队列.
wait(S)先设置信号量的值减一,然后判断当前信号量的状态,如果小于零,将当前进程添加到等待队列
signal(S)先设置信号量的值加一,然后判断信号量的值小于等于0,从等待队列中唤醒第一个进程
可以解决让权等待
(3). 信号量实现互斥
在临界区前面加上P操作,后面加上V操作.
(4). 信号量实现同步
初始信号量为0,先进行的操作后面进行V操作,后进行的操作之前进行P操作.
9. 进程同步问题
(1). 生产者消费者问题
出现空闲位和生产者放入商品是同步关系 ===> 同步信号量 semaphore empty = n
缓冲区中出现商品与消费者拿出商品是同步关系 ===> 同步信号量 semaphore full = 0
所有进程之间都是互斥关系 ===> 互斥信号量 semaphore mutex = 1
==互斥信号量的P操作要在同步信号量的P操作之后进行==,防止已经获得了同步锁,但是缓冲区已满或者空,就死锁了.
(2). 多生产者多消费者问题
父亲放苹果和女儿吃苹果是同步关系 ===> 同步信号量 semaphore apple = 0
母亲放橘子和儿子吃橘子是同步关系 ===> 同步信号量 semaphore orange = 0
盘子为空和父亲母亲放入水果是同步关系 ===> 同步信号量 semaphore plate = 1(盘子中可以放入的水果数)
(3). 吸烟者问题
还是生产者消费者的问题
组合一的数量 ===> 同步信号量 semaphore offer1 = 0
组合二的数量 ===> 同步信号量 semaphore offer2 = 0
组合三的数量 ===> 同步信号量 semaphore offer3 = 0
抽烟是否完成 ===> 同步信号量 semaphore finish = 0
(4). 哲学家进餐问题
思路一:只能有4个哲学家同时用餐,总有一个哲学家可以拿到两只筷子
思路二:奇数哲学家先拿左边筷子,偶数哲学家先拿右边筷子,会有一哲学家没有筷子被阻塞
思路三:加锁,同时拿两双筷子
10. 死锁
(1). 什么是死锁
线程之间持有资源并且循环等待其他资源而相互阻塞的情况.
(2). 死锁产生的必要条件
- 互斥条件:资源只能被一个进程使用,不能共享
- 不可剥夺条件:资源被一个进程占有之后不能被其他进程剥夺
- 请求和保持条件:进程得到一个资源之后提出了新的获取资源的请求,但同时不放弃自己已经拥有的资源
- 循环等待条件:存在资源的循环等待链
(3). 避免死锁
1). 安全序列,安全状态和死锁
系统按照这种序列分配资源,每个进程都能顺利完成.
只要能找出一个安全序列,系统就是安全状态,安全序列可能有多个
安全状态可以转化为不安全状态(分配资源给进程,空闲资源减少),不安全状态也可以转化为安全状态(进程归还资源).
2). 银行家算法
在资源分配之前,预先判断这次分配是否会导致系统进入不安全的状态,从而决定是否答应本次资源分配请求.
安全性检查:
- 循环检查某一进程最多需要的资源是否能被满足,如果可以就分配给它,换取已经分配给这个进程的所有资源(进程归还资源),如果不行就跳过.
- 如果若干轮循环之后,所有的进程都能被满足分配资源的请求,那么认为当前状态是安全的,上一步进程的顺序就是安全序列
银行家算法中,会有一个进程向系统申请一定的资源,要做的就是系统减去这些资源之后(那么肯定要先判断本次申请能否满足),进行安全性检查,判断分配资源之后是否会不安全.
