操作系统入门（二）进程
一学期的可也算是基本上完了，不知道大家学的怎样。 应朋友之约，我来总结一下这学期学的操作系统课程，方便大家复习。
进程与进程管理
进程的引入
前驱图
前趋图（Procedence Graph）是一个有向无循环图（DAG）。图中的每个结点可用于表示一条语句、一个程序段或进程；结点间的有向边则表示在两结点之间存在的偏序或前趋关系“→”，
→={(Pi，Pj)| Pi必须在Pj开始前完成 }。
程序顺序执行
程序执行的顺序性
处理机的操作严格按程序规定的顺序执行，即只有前一操作结束后才能执行后继操作。
程序执行的封闭性
程序一旦开始运行，其执行结果不受外界因素的影响。
程序执行结果的确定性
程序执行的结果与它的执行速度、时间无关。
程序结果的可再现性
程序执行时的环境和初始条件相同，当程序多次重复执行时，都将获得相同的结果。
程序并发执行
程序执行的间断性
程序执行的相互制约将导致并发程序具有“执行—暂停执行—执行”这种间断性的活动规律。
程序执行失去封闭性
因多个程序共享系统中的资源，所以某程序在执行时必然会受到其他程序的影响。
程序执行结果的不可再现性
由于失去了封闭性，也将导致失去其可再现性。
资源共享
系统中的硬件资源和软件资源不再被单个用户或程序独占，而为多个用户或作业共同使用。
程序和计算不再一一对应
程序和计算是两个不同的概念，在程序并发执行中一个共享程序可对应多个“计算”，程序与“计算”已不再一一对应。
多道程序设计
在采用多道程序设计的计算机系统中，允许多个程序同时进入一个计算机系统的内存储器并运行，这种让多个程序同时进入计算机计算的方法称为多道程序设计。
提高处理器的效率，从而提高整个系统的效率。
进程
为什么要进程
为了使程序在多道程序环境下能够并发执行，并对并发执行的程序加以控制和描述，引入进程的概念。 程序段、数据段及进程控制块三部分构成了一个进程的实体。
进程的概念
进程是具有独立功能的可并发执行的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的独立单位。或者说，“进程”是进程实体的运行过程。
程序与进程的区别与联系
（1）进程是程序的一次执行，是一个动态的概念，程序是完成某个特定功能的指令的有序序列，是一个静态的概念 （2）一个进程可以执行一个或几个程序，同一程序也可能由多个进程同时执行 （3）进程是系统进行资源分配和调度的一个独立单位，程序则不是 （4）程序可以作为一种软件资源长期保存，而进程是程序的一次执行过程，它是临时的，有生命期的 进程是具有结构的
联系:进程是程序的运行
进程的特征
动态性：进程的基本特性。进程是进程实体的执行过程； 并发性:进程的主要特征。多个进程实体同存于内存中，能在一段时间内同时运行； 独立性：进程实体是一个能独立运行的基本单位，同时也是系统中独立获得资源和独立调度的基本单位。 异步性：进程按各自独立的、不可预知的速度向前推进；或者说，进程按异步方式运行。 结构特征：从结构上看，进程实体是由程序段、数据段及进程控制块三部分组成，有人把这三部分统称为“进程映像”。
进程的基本状态及其转换
进程的三种基本状态
- 就绪状态 当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机便可立即执行，这时的状态称为就绪状态
- 执行状态 指进程已获得处理机，其程序正在执行
- 阻塞状态 进程因发生某种事件（如I/O请求、申请缓冲空间等）而暂停执行时的状态，亦即进程的执行受到阻塞，故称这种状态为阻塞状态，有时也称为“等待”状态或“睡眠”状态。
进程状态的转换
－ 就绪→执行状态 处于就绪状态的进程，当进程调度为之分配了处理机后 － 执行→阻塞状态 正在执行的进程因发生某种事件而无法执行 － 执行→就绪状态 正在执行的进程如因时间片用完或一个优先权高的进程到来而被暂停执行 － 阻塞→就绪状态 处于阻塞状态的进程，其等待的事件已经发生
思考:其他状态转换可以存在吗? 这个问题自己想想。、，碧如阻塞到执行的飞跃。
进程的挂起状态
挂起状态的引入
- 终端用户的需要 当终端用户在自己的程序运行期间发现有可疑问题时，往往希望暂时使自己的进程静止下来。
- 父进程的需要 父进程常常希望考察和修改子进程或者当要协调各子进程间的活动
- 操作系统的需要 操作系统有时需要挂起某些进程，检查运行中资源的使用情况及进行记账，以便改善系统运行的性能。
- 对换的需要 为了缓解内存紧张的情况，即将内存中处于阻塞状态的进程换至辅存上，使进程又处于一种有别于阻塞状态的新状态。
- 负荷调节的需要
进程状态的转换
在引入挂起状态后，又将增加从挂起状态（又称静止状态）到非挂起状态（又称活动状态）的转换 － 活动就绪→静止就绪 － 活动阻塞→静止阻塞 － 静止就绪→活动就绪 － 静止阻塞→活动阻塞
进程控制块（PCB）
进程控制块的作用
－进程控制块记录进程信息 －操作系统是根据进程控制块PCB来对并发执行的进程进行控制和管理的 －PCB是进程存在的唯一标志
进程控制块中的信息
－进程标识符信息 进程标识符用于唯一地标识一个进程，通常有外部标识符和内部标识符 ①外部标识符。由创建者提供，通常由字母、数字所组成，往往是由用户（进程）在访问该进程时使用。 ②内部标识符。这是为了方便系统使用而设置的。在所有操作系统中都为每一个进程赋予一个惟一的整数作为内部标识符，它通常就是一个进程的序号。
－处理机状态信息 处理机状态信息主要是由处理机各种寄存器中的内容所组成 ：通用寄存器、指令计数器、程序状态字PSW、用户栈指针。
－进程调度信息 存放了一些与进程调度和进程对换有关的信息：进程状态、进程优先级、进程调度所需的其他信息、事件。
进程控制
进程控制的主要任务是创建和撤消进程以及实现进程的状态转换，进程控制一般由操作系统的内核来实现。操作系统内核通常是运行在系统态的。
操作系统内核
通常，将一些与硬件紧密相关的模块诸如中断处理程序、各种常用设备的驱动程序以及运行频率较高的模块都安排在紧靠硬件的软件层次中并使它们常驻内存，以便提高操作系统的运行效率，并对它们加以特殊的保护，把这一部分称为操作系统的内核
操作系统内核的功能
中断处理：中断处理功能在操作系统中，既是内核的最基本功能，也是整个操作系统赖以活动的基础，即操作系统的重要活动最终都将依赖于中断。 进程管理：进程创建、撤消、进程状态的转换 、进程调度等。 资源管理中的基本操作：包括对时钟、I/O设备和文件系统进行控制和管理的基本操作。
原子操作
所谓原子操作是指：一个操作中的所有动作，要么全做，要么全不做。换言之，原子操作是一个不可分割的操作。 内核在执行上述操作时，往往是通过执行各种原语操作来实现的。
进程阻塞过程
进程便通过调用阻塞原语block（）把自己阻塞 －立即停止当前进程的执行 －把进程控制块中的现行状态由“执行”改为“阻塞”，并把它插入到阻塞队列
进程唤醒过程
调用唤醒原语wakeup( )将等待该事件的进程唤醒 －把被阻塞进程从等待该事件的阻塞队列中移出 －将其PCB中的现行状态由“阻塞”改为“就绪” －然后再将该进程插入到就绪队列中
进程的挂起过程
当出现了引起进程挂起的事件时，系统就利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起 －检查被挂起进程的状态，若正处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将其改为静止阻塞 －进程保存于外存对换区 －如被挂起的进程正在执行，则转调度程序重新调度
进程的激活过程
当发生激活进程的事件时系统将利用激活原语active( )将指定进程激活
－将进程从外存调入内存，检查该进程的现行状态：若是静止就绪，便将其改为活动就绪；若为静止阻塞，便将其改为活动阻塞 －假如采用的是抢占调度策略 ，检查是否要进行重新调度
进程的调度
调度的基本概念
一个程序从提交开始直到完成，往往要经历三级调度： 高级调度又称为作业调度，它决定将哪些在外存上处于后备状态的作业（程序加数据）调入主机内存，准备执行。 低级调度又称为进程调度。它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给该进程的操作。 在有的系统中，可能增加一中级调度，主要作用是在内存和外存对换区之间进行进程对换，以解决内存紧张问题 。
进程的调度功能
进程调度就是系统按照某种算法把CPU动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。 进程调度程序的主要功能： －选择进程占有CPU －进行进程上下文的切换
调度方式
非剥夺方式
分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件（如提出I/O请求）而阻塞时才把处理机分配给另一进程 －优点：简单，系统开销小， －缺点：貌似公正,可能导致系统性能的恶化
剥夺方式
该方式规定，当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程 剥夺原则：优先权原则、短进程优先原则、时间片原则
进程调度算法
先进先出（FIFO）
－算法：把处理机分配给最先进入就绪队列的进程 －优点：易于实现 －缺点：表面上公平，服务质量不佳 、对短进程不利
最短处理机运行期优先调度算法
－算法：从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机使之执行 －优点：可获得较好的调度性能 －缺点： 进程的CPU执行期难以准确得到、对长进程不利
最高响应比优先调度算法
－算法：响应比=（等待时间+要求的服务时间）/要求的服务时间 ，每次选取响应比最高的进程调度 －优点：所以对短进程有利，并且考虑了等待时间 －缺点：计算响应比有一定的系统开销
优先级调度算法
－算法：将CPU分配给就绪队列中优先级最高的进程 －静态优先级 在进程创建时确立，确定后运行期间保持不变。确立依据有：进程的类型、进程对资源的需求、用户申请的优先级 优点：简单 缺点：不能动态反映进程特点，系统调度性能差
动态优先级
进程在开始创建时，根据某种原则确定一个优先级后，随着进程执行时间的变化，其优先级不断地进行动态调整 确定依据：根据进程占有的CPU时间的长短来决定，占有时间越长优先级越低；根据进程等待CPU的时间来决定，时间越长优先级越高
时间片轮转调度算法
算法：通常用在分时系统，它轮流地调度系统中所有就绪进程，使就绪进程依次获得一个时间片的运行时间
- 时间片长短确定遵循原则 既要保证系统各个用户进程及时地得到响应，又不要由于时间片太短而增加调度的开销，降低系统的效率
前后台调度算法
－算法：该方法用在批处理和分时相结合的系统中。将分时用户作业放在前台，把批处理作业放在后台。系统对前台作业按照时间片轮转法进行调度，仅当前台无作业时，才把处理机分配给后台作业的进程。后台进程通常按先来先服务方式运行 －优点：使分时用户进程得到及时响应，又提高了系统资源的利用率
多级反馈队列轮转算法
－系统设置多个不同优先级的就绪队列，每次调度总是先调度优先级高的队列，仅当该队列空时，才调度次高优先级队列。 －通常刚创建的进程和因请求I/O未用完时间片的进程排在最高优先级队列，在这个队列中运行2-3个时间片未完成的进程排列下一个较低优先级队列。 －不论什么时候，只要较高优先级队列有进程进入，立即转进程调度，及时调度较高优先级队列进程。 －优点：能较好地满足各类作业的用户要求，既能使分时用户作业得到满意的响应，又能使批处理用户的作业获得较合理的周转时间
进程依次执行时可能发生的三种情况
－进程未用完一个时间片便结束，这时系统应提前进行调度 －进程在执行过程中提出I/O请求而阻塞，系统应将它放入相应的阻塞队列并引起调度 －进程用完一个时间片后尚未完成。系统应将它重新放到就绪队列的末尾，等待下次执行
进程调度的时机和过程
进程调度的时机
－正在执行的进程运行完毕 －正在执行的进程调用阻塞原语将自己阻塞起来进入等待状态 －在采用抢占式优先级调度时，有优先级高于正在运行进程的进程进入就绪队列 －在分时系统中时间片已经用完 －CPU方式是可剥夺时，就绪队列中的某个进程 优先级变得高于当前运行进程的优先级
进程调度的过程
－进程调度所依赖的数据结构通常是调度队列，由于调度的原因不同，在单处理器系统中设置了多种等待队列 －只有就绪队列中的进程能够获得处理器而最终运行，其他队列中的进程从队列中出来后，必须进入就绪队列才能分配处理器 －队列数据结构的建立结构与调度算法密切相关 －进程调度算法只是决定哪一个进程将获得处理机，而将处理机分配给该进程的具体操作是由分派程序完成的
线程的基本概念
线程的引入
在操作系统中引入进程的目的是为了使多个程序并发执行以改善资源利用率及提高系统的吞吐量； 在操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性