导图社区 进程管理
- 270
- 20
- 2
- 举报
进程管理
进程与线程，处理机调度，进程同步，死锁
编辑于2019-08-20 09:01:30
- 相似推荐
- 大纲
进程管理
进程与线程
进程的概念
定义
是程序的一次执行过程
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位
特征
动态性
最基本的特征
并发性
独立性
异步性
结构性
了解即可
进程的状态与转换
状态
运行态
进程正在处理及上运行没在单处理机环境下，每个时刻最多只能有一个进程处于运行态
就绪态
进程已处于准备运行的状态，及进程获得了出处理机外的一起所需资源，一旦得到处理机即可运行
阻塞态
即等待态，进程正在等待某一时间二展厅运行，如等待某资源为可用（不包括处理机）有或者等待输入/输出完成，即使处理及空闲，该进程也不能运行
创建态
进程正在被创建，尚未转到就绪态
结束态
进程正从系统中小时，可能是进程正常结束或其他原因中断退出运行
转换
就绪态--运行态
处于就绪态的进程被调用后，获得处理及资源，（分派处理机时间片）于是进程有就绪态转换为运行态
运行态--就绪态
处于运行态的进程在时间片用完后，不得不让处理及，从而进程由运行态转换为就绪态，此外，在可剥夺的操作系统中，当有更高优先级的进程就绪时，调正程序将政治性的程序转换为就绪态，让更高优先级的进程执行
运行态--阻塞态
进程请求某一资源的使用和分配或等待某一时间发生时，他就从运行态转换为阻塞态。进程以系统调用的形式请求操作系统提供服务，这是一种页数的，由运行用户态程序调用操作系统内核过程的形式
阻塞态--就绪态
进程等待的时间到来时，如I/O操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞态转换为就绪态
进程的控制
进程的创建
定义
一个进程创建另一个的进程，此时创建者曾为父进程被创建的进程称为子进程。子进程给可以集成父进程所拥有的资源。当子进程被测小时，应将其从父进程哪里获得的资源归还给父进程，在撤销父进程时，必须同时撤销所有的子进程
过程
为新进程分配一个唯一的进程标识号，并申请一个空白的PCD(PCD是有限的)。若PCD申请失败，则创建失败
为进程分配资源，为新进程的程序和数据及用户栈分配必要的内存空间（在PCD中体现）注意，若资源不住（如内存空间），则并不是创建失败，而是处于“等待态”等待这个资源
初始化PCB，主要包括初始化标志信息、初始化处理及状态信息和初始化处理机控制信息，以及设置进程的优化级等
若进程就绪队列能接纳新进程，则将新进程插入就绪队列，等待被调度运行
进程的终止
过程
根据被终止的进程的标识符，检索PCB，从中读出该进程的状态
若被终止进程处于执行状态，理机终止该进程的执行，将处理机资源分配给其他进程
若该进程还有子进程，则应将其所有子进程终止
将该进程所拥有的全部资源归还给其父进程，或归还给操作系统
将该PCB从所在队列（链表）中删除
进程的阻塞和唤醒
阻塞过程
找到将要被阻塞进程的标识号对应的PCB
若该进程为一年形态，则保护其现场，将其状态转为阻塞态，停止运行
把该PCB插入相应时间的等待队列
唤醒过程
在该时间的等待队列中找到相应的进程PC
将其从等待队列溢出，并置其状态为就绪态
把改PCD插入就绪队列，等待调度程序调度
进程的切换
过程
保存处理机上下文，包括程序计数器和其他寄存器
更新PCB信息
把进程的PCB一如相应的队列，如就绪、在某事件柱塞等队列
选择另一个进程程序，并更新其PCD
更新内存管理的数据结构
恢复处理机上下文
注意
调度
决定资源分配给那个进程的行为，是一种决策行为
切换
指实际分配的行为，是执行行为
进程组织
进程控制块（PCB）
定义
操作系统核心的一种数据结构，主要用来表示进程的状态
各部分主要说明
进程描述信息
进程标识符
标志各个进程，每个进程都有一个唯一的标识号。
用户标识符
进程归属的用户，用户标识符主要为共享和保护服务
进程控制和管理信息
进程当前状态
描述进程的状态信息，作为处理机分配调度的依据
进程优先级
描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机
资源分配清单
用于说明有关内存地址空间或虚拟空间的状况，所打开文件的列表和所使用的输入/输出设备信息
处理及相关信息
主要指处理机中各寄存器的值，当进程被切换时，处理及状态信息都必须保存在相应的PCB中，以便在该程序进程重新执行时，能从断电继续执行
程序段
能被进程调度程序调度到CPU执行的程序代码段
数据段
一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以时程序执行时产生的中间或最终结果
进程通信
共享存储系统
定义
在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享给空间进行写/读操作实现进程之间的信息交换
注意
用户的进程空间一般是独立的，进程运行期间一般不能访问其他进程的空间，想要让用户进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的
分类
低级方式的共享
基于数据结构的共享
高级方式的共享
基于存储区的共享
消息传递系统
直接通信方式
发送进程直接把消息发送给接受进程，并将他挂在接受线程的消息缓冲队列上，接受进程从消息缓冲队列中取得信息
间接通信方式
发送进程把消息发送到某个中间实体，接受进程从中间实体取得消息
中间实体一般称为心想，这种通信方式又称信箱通信方式
例如电子邮件
管道通信
管道
指用于连接一个读进程和一个写进程以实现他们之间的通信的一个共享文件，又名pipe文件
定义
向管道提供一个输入的发送进程（即写进程），以字符流形式将大量的数据写入管道；而接受管道输出的接受进程（即读进程）则从管道中接受数据
注意
管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放空间以便写更多的数据。管道只能采用半双工通信，即某一时刻只能单向传输，要实现父子进程双方互动通信，需要定义两个管道
线程概念与多线程模型
引入目的
为了实现更好的使多道程序并发执行，以提高资源利用率和系统吞吐量，增加程序的并发性
线程与进程的比较
调度
在传统的操作系统中，拥有资源和独立调度的基本单位都是进程
拥有资源
不论是传统操作系统还是设有线程的操作系统，进程都是拥有资源的基本单位，而线程不拥有系统资源，但线程可以访问其隶属进程的系统资源
并发性
在引入线程的操作系统中，不仅进程之间可以并发执行，而且多个线程之间也可以并发执行，从而使操作系统具有更好的并发性，提高了系统的吞吐量
系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，因此操作系统所付出的开销远大于创建或撤销线程时的开销
地址空间和其他资源
进程的地址空间之间相互独立，统一进程的各线程间共享进程的资源，某进程内的线程对于其他进程不可见
通信方面
进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以直接读/写进程数据段（如全局变量）来进行通信
线程的属性
线程是一个情形实体，它不拥有资源，但每个线程都有唯一的标识符，和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态
不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把他们创建成不同的线路
同一进程中的各个线程共享该进程所拥有的资源
线程是处理机的独立调度单位，多个线程时可以并发执行的
一个线程被创建后，便开始了他的生命周期，直至终止，线程在生命周期内会经历阻塞态、就绪态、运行态等各种状态变化
线程的实现方式
用户级线程
有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在
内核级线程
又称内核支持的线程，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口
多线程模型
多对一模型
概念
将多个用户级线程映射到一个内核级线程，，线程管理在用户空间完成，这个模式中，用户级线程对操作系统不可见
优点
线程管理时在用户空间进行的，因此效率比较高
缺点
一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行的运行在多处理机上
一对一模型
概念
将每个用户级线程映射到一个内核级线程
优点
当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强
缺点
每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能
多对多模型
概念
将n个用户级线程映射到m各内核级线程上，要求m小于等于n
特点
多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点
处理机的调度
调度的基本概念
处理机调度
对处理机进行分配，即从就绪队列中按照一定算法选择一个进程将处理机分配给它运行
处理机调度时多道程序操作系统的基础，是操作系统设计的核心问题
调度的层次
作业调度
即高级调度，主要任务是按照一定的原则从外村上处于后备状态的作业中挑选作业，对其分配内存、输入/输出设备等必要资源，并建立相应的进程，使其获得竞争处理机的权利
多道批处理系统中大多有作业调度，而其它系统中通常不需要配置作业调度
中级调度
即内存调度，作用是提高内存利用率和系统吞吐量
进程调度
即低级调度，作用使按照某种方法和策略从就绪队列中选取一个进程，将处理及分配给它
三级调度的联系
作业调度为进程活动做准备，进程调度使系统正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间
作业调度次数最少，中级调度次数略多，进程调度频率最高
进程调度使最基本的，不可或缺
调度实际、切换与过程
不能进行进程的调度与切换的情况
在处理中断过程中
进程在操作系统给内核程序临界区中
其他需要完全屏蔽中断的原子操作过程中
应该进行进程调度与切换的情况如下
发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换，若操作系统旨在这种情况下进行进程调度，则是非剥夺调度
中断处理结束后或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度
调度的基本准则
调度的基本准则
CPU利用率
系统吞吐量
周转时间
等待时间
响应时间
调度方式
非剥夺调度方式，又称非抢占方式
剥夺调度方式，又称抢占方式
典型调度算法
先来先服务调度算法（FCFS）
概念
在作业调度中，算法每次从后背作业队列中选择最先进入该队列的一个或几个作业，将它们调度内存，分配必要的资源，创建进程并放入就绪队列
特点
算法简单，但效率低
对长作业比较有利，但对短作业不利
有利于CPU繁忙型作业，而不利于I/O繁忙型作业
短作业（短进程、短线程）有限调度算法（SJF）
概念
从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，知道完成或发生某时间阻塞时，才释放处理机
缺点
对长作业不利
该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理
由于作业的长短只是根据用户所提供的估计时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度
时间片轮转调度算法
概念
主要用于分时系统。系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个程序执行
时间片长短的决定因素
系统响应时间
就绪队列中的进程数目
系统的处理能力
优先级调度算法
概念
每次从后备作业队列中选择优先级最高的一个或几个作业将它调度内存，分配必要的资源，创建进程并放入就绪队列
根据更高优先级进程能否抢占正在执行的进程分类
非剥夺式优先级调度算法
剥夺式优先级调度算法
根据进程创建后其优先级是否可以改变分类
静态优先级
动态优先级
高响应比有限调度算法
概念
主要用于作业调度，是对FCFS和SJF的一种综合平衡，同时考虑了每个作业的等待时间和估计运行时间，在每次进行作业调度是，先计算后备队列中每个作业的相应比，从中选出相应比最高的作业投入运行
相应比的变化规律
相应比=（等待时间+要求服务时间）/要求服务时间
三种情况
作业等待时间相同时，要求服务时间越短，相应占比越高，有利于短作业
要求服务时间同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的时先来先服务
对于长作业，作业的响应比可以随着等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机
多级反馈队列调度算法
主要思想
设置多个就绪队列，并为各个队列赋予不同的优先级，第一队列优先级最高，优先级逐次降低
赋予各个队列中进程执行时间片的大小各不相同
一个新进程进入内存后，首先将他放入第一级队列的末尾，按FCFS原则排队等待宽度。当轮到该进程执行时，入它能在该事件片内完成，便可准备撤离系统；若它在一个时间片结束未完成，调度程序便将该进程转入第二级队列的末尾，重复上面操作
当上一级队列为空时，调度程序才调度下级队列中的进程运行
优点
终端型作业用户
短作业优先
短批处理作业用户
周期时间较短
长批处理作业用户
经过前面几个队列得到部分执行，不会长期得不到处理
同步与互斥
进程同步的基本概念
作用
为了协调进程之间相互制约关系
临界资源
定义
一次仅允许一个进程使用的资源
许多变量、数据等都可以被若干进程共享的资源
访问过程
进入区
为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区
临界区
进程中访问临界资源的那段代码，又称临界段
退出区
将正在访问临界区的标志清楚
剩余区
代码中剩余的部分
同步
概念
亦称直接制约关系，指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的制约关系源于他们之间的相互合作
互斥
概念
也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当詹咏琳姐资源的进程退出临界区后，另一进程才允许区访问此临界资源
准则
空闲让进
临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待
当已有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待
对请求访问的进程，应保证在有限时间内进入临界区
让权等待
当进程不能进入临界区时，应立即释放处理器，防止进程忙等待
实现临界区互斥的基本方法
软件实现方法
单标志法
违背“空闲让进”原则
双标志法先检查
违背“忙则等待”原则
双标志发后检查
会导致“饥饿”现象
皮特森算法
单标志法和双标志法后检查的结合
硬件实现方法
中断屏蔽法
进区关中断，出区开中断
硬件指令法
设置原子操作指令
信号量
利用PV操作解决互斥与同步问题
管程
定义
系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和资源所执行的操作来表征该资源，而忽略他们的内部结构和实现细节
由一组数据及定义在这组数据置上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程
组成
局部管程的共享结构数据说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句
基本特性
局部于管程的数据只能被局部于管程内的过程所访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次仅允许一个进程在管程内执行某个内部过程
经典同步问题
生产者-消费者问题
问题描述
一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能吧消息放入缓冲区，否则不许等待；只有缓冲区不空时，消费者才能从中取出信息，否者必须等待。由于缓冲区时临界资源他只允许一个生产者放入消息，或者一个消费者从这取出消息
问题分析
关系分析
生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作关系，只有生产者生产之后，消费者才能消费，他们也是同步关系
整理思路
只有生产者和消费者两个进程，正好是这连个进程存在着互斥关系和同步关系，那么需要解决的是互斥和同步PV操作的位置
信号量设置
信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1；信号量full用于记录当前缓冲池中的“满”缓冲区域，处置为0，信号量empty用于记录当前缓冲池中的“空”缓冲区数，初值为n
读者-写者问题
问题描述
由读者和写者两组并发进程，共享一个文件，当两个或以上的都进程同时访问贡献数据时不会产生副作用，单若某个写进程和其他进程同时访问共享数据时，则可能导致数据不一致的作物
允许多个读者可以同时对文件执行读操作
只允许一个写者往文件中写信息
任一写着在完成写操作之前不允许其他读者或写者工作
写者执行写操作前，应让已有的读者和写者全部退出
问题分析
关系分析
读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题
整理思路
两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决问题。读者必须实现与写者互斥的同时，实现与其他读者的铜鼓，因此简单的一对P操作、V操作是无法解决问题的。这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，此时读者会一直占用文件，当没有读者时，写者才可以写文件。同时这里不同读者对计数器的访问应该也是互斥的
信号量设置
首先设置信号量count为计数器，用于记录当前读者的数量，初值为0；设置mutex为互斥信号量，用于保护更新count变量时的互斥；设置互斥信号量rw用于保证读者和写者的互斥访问
哲学家进餐问题
问题描述
一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间时一碗米饭，哲学家们倾注毕生精力用于思考和金禅，哲学家在思考时，并不影响他人。只有当哲学家饥饿时才试图拿起左、右两根筷子。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考
问题分析
关系分析
5名哲学家与左右邻居对其中间的筷子访问时互斥关系
整理思路
显然，这里有5个进程，本问题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法有两个，一是让他们同时拿两根筷子；二是对每名哲学家的动作指定跪着，避免饥饿或死锁现象的发生
信号量设置
定义互斥信号量数组chopstick[5]={1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号为0~4，哲学家i左边的筷子编号为i，哲学家右边的筷子编号为(i+1)%5
死锁
产生原因
非剥夺资源的竞争和进程的不恰当推进顺序
定义
多个进程因竞争资源二造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进
解决方案
预防死锁
破坏互斥条件
有些资源必须互斥使用，无法破坏互斥条件
破坏不剥夺条件
增加系统开销，降低吞吐量
破坏请求和保持条件
严重浪费系统资源，还可能造成饥饿现象
破坏循环等待条件
浪费系统资源，并造成编程不便
避免死锁
安全状态
能找到一个分配资源的序列能让所有进程都顺利完成
应行家算法
采用预分配策略检查分配完成时系统是否处在安全状态
解除死锁
资源剥夺法
挂起某些死锁进程并抢夺他的资源，以便让其他进程继续推进
撤销进程法
强者撤销部分、甚至全部死锁进程并剥夺这些进程的资源
进程回退法
让一个或多个进程回退到足以回避死锁的地步