中财网在贝加尔湖的草原上:进程管理
来源：百度文库 编辑：中财网 时间：2024/05/05 06:28:39
基础：进程描述及控制
策略：进程调度
实现：互斥与同步
避免：死锁与饥饿
解决：几个经典问题
关于：进程通信
2.1进程的引入
程序：源代码程序、目标程序和可执行程序
程序执行：编辑、编译、链接、执行
程序的结构：顺序结构、分支结构和循环结构
程序顺序执行的特征：顺序性、封闭性、可再现性
多道程序设计技术：多个程序并发执行
程序并发执行时的特征间断性、非封闭性、不可再现性。
协调各程序的执行顺序
例如，当输入的数据还未全部输入内存时，计算必须等待
多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果
选择哪些、多少个程序进入内存执行？
内存中的执行程序谁先执行
内存如何有效分配？
定义：可并发执行的程序，在一个数据集合上的运行过程。
申请/拥有资源
程序：静态概念，是指令和数据的集合，可长期存储
进程与程序对应关系
一个程序可以对应一个进程或多个进程
一个进程可以对应一个程序，或者一段程序
动态性
并发性
独立性
异步性
引入进程带来的问题
增加了空间开销：为进程建立数据结构
额外的时间开销：管理和协调、跟踪、填写和更新有关数据结构、切换进程、保护现场
更难控制：
协调多个进程竞争和共享资源如何预防
解决多个进程因为竞争资源而出现故障
处理机的竞争尤为突出
组成（进程映像）：程序、数据集合、进程控制块PCB（Process Control Block）
PCB是进程存在的唯一标志。创建进程时，创建PCB；进程结束时，系统将撤销PCB
进程标识信息：进程的内部和外部标识符
处理机状态信息：通用寄存器值、指令寄存器值、程序状态字值、用户栈指针值
进程调度信息：进程状态、进程优先权、进程调度的其他信息
其他信息：程序及数据地址、进程同步和通讯机制、资源清单、链接指针
所有进程的PCB通过链表组织成为一个单一队列。适用于进程数目不多的系统。（过多导致查找过于频繁）如，Windows操作系统
PCB按进程状态不同，组织成不同的表格：就绪进程表、执行进程表（多级系统中）及阻塞进程表
系统分别记载各PCB表的起始地址。
PCB按进程状态不同用链接指针组成不同队列：就绪进程队列、阻塞进程队列（可按阻塞原因不同，分别组织）
系统分别记载各PCB链表的起始地址
2.2 进程的状态
进程执行轨迹
进程的轨迹：进程执行的指令序列，用以观察处理机的执行过程
注:并非所有进程只要“未执行”就处于就绪，有的需要阻塞等待I/O完成
执行状态（Running）
就绪状态（Ready）
阻塞状态（Blocked）
新状态（NEW）
终止状态（Terminated）
1新状态：进程已经创建，但未被OS接纳为可执行进程
2就绪状态：准备执行
3执行状态：占用处理机(单处理机环境中，某一时刻仅一个进程占用处理机)
4阻塞状态：等待某事件发生才能执行，如等待i/0完成等
5终止状态：因停止或取消，被OS从执行状态释放。
空->新状态新创建的进程首先处于新状态
新状态
就绪状态
执行状态终止状态
执行状态
执行状态阻塞状态
阻塞状态
注：某些系统允许父进程在任何情况下终止其子进程。
如果一个父进程被终止，其子孙进程都必须终止。
新状态
就绪状态
阻塞状态终止
内存资源紧张
无就绪进程，处理机空闲：i/0的速度比处理机的速度慢得多，可能出现全部进程阻塞等待i/0
采用交换技术：换出一部分进程到外村，以腾出内存空间。
采用虚拟存储技术：每个进程只能装入一部分程序和数据（存储管理部分）
将内存中暂时不能运行的进程，或暂时不用的数据和程序，换出到外村，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的数据和程序，换入内存。
进程被交换到外存，状态变为挂起状态
进程全部阻塞，处理机空闲。
系统负荷过重，内存空间紧张。
操作系统的需要。操作系统可能需要挂起后台进程或一些服务进程，或者某些可能导致系统故障的进程。
终端用户的请求
父进程的需求
不能立即执行
可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行。
使之挂起的进程为；自身、其父进程、OS
只有挂起它的进程才能使之由挂起状态转换为其他状态。
挂起于阻塞
问题1.是否只能挂起阻塞进程？
2.如何激活一个挂起进程？
区分两个概念
进程是否等待事件，阻塞与否
进程是否被换出内存，挂起与否
4种状态组合
就绪：进程在内存，准备执行
阻塞：进程在内存，等待事件
就绪/挂起：进程在外存，只要调入内存即可执行
阻塞/挂起：进程在外存，等待事件
注：处理机可调度执行的进程有两种：
新创建的进程
或换入一个以前挂起的进程
通常为避免增加系统负载，系统会换入一个以前挂起的进程执行。
具有挂起状态额进程状态转换图
系统模式（又称为系统态）、控制模式或内核模式
1具有较高的特权
2运行系统特定的指令，包括读.写控制寄存器的指令、基本i/0指令以及与存储器管理有关的指令，及一些特定的内存区
3内核模式下的处理机机器指令、寄存器和内存都受到完全控制和保护
用户模式(或用户态)
1具有较低的特权
2用户程序一般运行在用户模式
用户模式->系统模式：用户程序执行到一条系统调用，进入操作系统内核执行
系统模式->用户模式：执行完系统调用的功能，返回到用户程序。
特殊情况：程序执行到结束语句时，切换到系统模式，不再返回到用户程序。
操作系统的核心，是基于硬件的第一层软件扩充，提供操作系统最基本的功能，是操作系统工作的基础
现代操作系统设计中，为减少系统本身的开销，往往将一些与硬件紧密相关的（如中断处理程序、设备驱动程序等）、基本的、公共的、运行频率较高的模块（如时钟管理、进程调度等）以及关键性数据结构独立开来，使之常驻内存，并对它们进行特殊保护。通常把这一部分称为操作系统的内核。
3.用户通过系统调用访问操作系统的功能，这些功能最终都通过操作系统内核实现。
4不同的操作系统对内核的定义和功能范围的设定是不同的
5一般地，操作系统内核的功能可以概括地分为资源管理功能和支撑功能。
资源管理;进程管理、存储管理和i/0设备管理
支撑功能：中断处理、统计、检测、时钟、管理、原语操作等
1进程管理：进程创建和终止、调度、状态转换、同步和通信、管理PCB
2存储管理：为进程分配地址空间、兑换、段/页管理
i/0设备管理：缓存管理、为进程分配i/0通道和设备
中断处理
时钟管理
原语（Primitive）：原子操作
统计
监测
进程切换
创建与终止
阻塞与唤醒
挂起与激活
提交新的批处理作业
交互式用户注册
操作系统提供服务
父进程创建子进程
进程创建：步骤
1.
2.
3.
4.
5.
进程终止：原因
批处理作业执行到“结束”语句
交互式用户“注销”
停止进程（应用程序）的执行
遇到错误或故障
正常结束
超时终止，执行时间超过预计时间
内存不足，无法为进程分配所需的内存空间
越界访问
企图使用未允许用的数据，或操作方式错
计算错，如除零，或企图存储硬件允许的最大数
超时等待某事件发生
i/0失败，如找不到文件或多次重试仍无法读写文件，或无效操作
无效指令，企图执行不存在的指令
特权指令，企图执行特权指令
数据类型不符，或未初始化
操作员或OS干预，如发生死锁的时候
父进程终止
父进程请求
1.根据被终止进程的标识符ID，找到其PCB，读出该进程的状态
2.若该进程为执行状态，则终止其执行，调度新进程执行。
3.若该进程有子孙进程，则立即终止其所有子孙进程
4.将该进程的全部资源，或归还给其父进程，或归还给系统
5.将被终止进程的PCB从所在的队列中移出，等待其它程序来所及信息。
阻塞原因：请求系统服务；启动某种操作，如i/0；新数据尚未到达；暂时无新工作可做等
当出现阻塞事件，进程调用阻塞原语将自己阻塞。并将其状态变为“阻塞状态”，并进入相应事件的阻塞队列。
当阻塞进程期待的事件发生，有关进程调用唤醒原语，将等待该事件的进程唤醒。并将其状态变为“就绪状态”，插入就绪队列
一般，进程可以自己阻塞自己；而唤醒操作则由操作系统，或其它相关进程来完成，进程无法自己唤醒自己
当出现挂起事件，系统利用挂起原语将指定进程或一个阻塞进程挂起。进程从内存换出到外存，其状态转换：就绪-》就绪/挂起
当激活事件发生，系统利用激活原语将指定进程激活。将相应进程从外存换入到内存，可能的状态转换：就绪/挂起-》就绪，或
时钟中断
进程执行完一个时间片
虚拟存储中，需要的指令或数据不在内存
执行遇到错误
可能使进程转换到终止状态
进程切换，作用于进程之间的一种操作。当分派程序收回当前进程的CPU并准备把它分派给某个就绪进程时，该操作将被引用。
模式切换，是进程内部所引用的一种操作。当用户程序转入系统调用，或相反时，该操作将被引用。
进程切换一定引发模式切换，反之则不然
什么是调度
调度是指，在一个队列中，按照某种方法（算法），选择一个合适的个体的过程。
调度的关键是需要某种方法或算法，好的调度算法有利于选择到合适的个体
如何判断、设计一个号的地阿杜算法呢？
公平性，防止进程长期不能获得调度而饥饿；
处理机利用率，尽量提高处理机的利用率；
提高系统吞吐量；
尽量减少进程的响应时间
满足用户的要求；相应时间、周转时间、截止时间
满足系统的需求：系统吞吐量、处理机利用率、各类资源的平衡使用、公平性及优先级
是指，从用户通过键盘提交一个请求开始、直到系统首次产生响应为止的时间。
输入的请求传送到处理机的时间
处理机对请求信息进行处理的时间
将响应结果发送到输出终端的时间
调度算法则应考虑尽可能使绝大多数用户的请求能在响应时间内完成。
常用于评价分时系统的性能
指从作业提交给系统开始，到作业完成为止的这段时间间隔
作业在外存排队等待调度的时间
进程在就绪队列中等待调度的时间
进程被处理机执行的时间
等待I/O操作完成的时间
周转时间
常用于评价批处理系统的性能
作业从外存调度到内存（作业调度）
进入内存还需在就绪队列中排队，等待进程调度
甚至，可能会挂起进程，在外存等待被激活（中程调度）
面向用户的原则：截止时间
指实时系统中，某任务必须开始执行的最迟时间，或必须完成的最迟时间
常用于评价实时系统的性能。
大、中型多用户系统，由于处理机价格昂贵，处理机利用率是衡量系统性能的一个重要指标
单用户微机或某些实时系统，则并非很重要。
多道程序系统的目标之一就是为了提高系统资源的利用率，因此，调度算法有责任使系统中的各种资源都尽量处于忙碌状态。
该原则同时适用于长程调度和中程调度，因为他们可以决定哪些作业（进程）可以进入内存，可以考虑系统资源的均衡使用。
优先权高的进程应优先调度
可以根据进程的优先权不同，组织不同的就绪队列。进程调度时首先选择高优先权队列中的进程，直到该队列空，再调度较低优先权队列中的进程，
几乎所有操作系统的调度算法都可考虑优先权原则。
当然，仅考虑优先权，可能会出现饥饿，对低优先权的进程不公平。
可以将进程排队的等待时间等因素纳入优先权的计算，随着进程等待时间的增长，其优先权也不断提高，进程也会在不久的将来得到调度。
根据执行进程的处理机是由进程自己释放，还是被强行剥夺，可以将进程调度方式分为非剥夺方式和剥夺方式两种。
执行进程只有在执行完毕，或因申请i/0阻塞自己时，才中断其执行，释放处理机，调度新的进程执行、
这种方式不利于“即时性要求较高的分时和实时系统。主要用于批处理系统。
剥夺方式
操作系统可以在新进程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，活在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。
这种方式会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。
调度的类型
批处理调度、分时调度、实时调度和多处理机调度
长程调度、中程调度、短程调度
i/0调度
又称为高级调度，或作业调度，它为被调度作业或用户程序创建进程，分配必要的系统资源，并将新进程插入就绪队列，等待短程调度。
某些采用交换技术的系统将新创建的进程插入到就绪/挂起队列，等待中程调度。
在批处理系统中，作业进入系统后，先驻留在磁盘上，组织成批处理队列，称为后备队列。长程调度从该队列中选择一个或多个作业，为之创建进程。
1.
取决于多道程序的度，即允许同时在内存中运行的进程数。
2.
取决于长程调度算法。
也称进程调度，或低级调度，决定就绪队列中的哪个进程将获得处理机。
短程调度运行频率最高。
现代操作系统几乎都具有段程调度工程。
又称为中级调度。它是对换功能的一部分
当内存空间非常紧张时，或处理机找不到一个可执行的就绪进程时，需要选择一个进程（阻塞或就绪状态）换出到外存，释放出内存空间给别的进程使用；当内存空间较充裕时，从外存选择一个挂起状态的进程调度到内存（换入）。
阻塞/挂起到就绪/挂起不需要调度，只需等待事件结束
先来先服务（FCFS）
该方法按照进程到达的先后顺序排队，每次调度队首的进程。
FCFS算法属于非剥夺调度方式，实现简单，看似公平。
但，对于那些后进入队列而运行时间较短的进程，或i/0型的进程而言，可能需要长时间等待。
对短进程不公平
由于长进程可能排在队列前面，必将增加队列后部进程的等待时间，从而将增加平均周转时间。
不利于i/0型进程，未有效利用系统资源。
一般地，FCFS与其他调度算法混合使用。例如，系统可以按照不同的优先级维护多个就绪队列，每个队列内部按照FCFS算法调度。
FCFS算法同时适合于长城、中程和短程调度三种调度类型。
当需要调度进程（或作业）时，通过计算判断就绪进程队列中哪个进程的预期执行时间最短，或后备作业队列中哪一个或几个作业的预期时间最短，就调度谁
属于非剥夺调度算法。当某进程获得处理机，直到其执行完成，或需要等待某事件而阻塞时，才自动释放处理机。系统又调度新的进程（或作业）
短进程优先
与FCFS算法比较，短进程优先调度算法改善了系统的性能，降低了系统的平均等待时间，提高了系统的吞吐量。但是，该算法也存在一些问题：
1很难准确预测进程的执行时间。
2可能导致长进程饥饿，这对长进程不公平；
3采用非剥夺调度方式，未考虑进程的紧迫程度，不适合于分时系统和事物处理系统。
1在分时联机系统中，n个进程循环地获得时间片儿执行。从系统中来看他们是交替执行的，但就每个终端用户而言，都感觉到自己独占了一台主机，不受其他用户的影响。这是通过进程并发执行实现的。
2如果用户数太多，主机处理的进程将会剧增加，进程排队等待的时间也会很长，进程的响应时间也可能增长，用户将明显感觉到主机的速度变慢而不满意。
3另外，时间片的大小也会影响进程的响应时间。
1进程切换将会增加系统的额外开销。
2时间片设定得太短，进程切换会非常频繁，而降低处理机的效率；时间片设定的太长，将无法满足交互式用户对响应时间的要求。
3因此，时间片大小的确定应综合考虑系统的最大用户数、响应时间、系统效率等多种因素。
为了简单，图中忽略了进程切换时的系统开销，而实际操作系统中，这类额外开销是客观存在的。
可见，采用基于时间片轮转调度法，进程的周转时间和平均周转时间并不比采用FCFS和短进程优先调度算法小。
加上进程切换所需的系统开销时间，该算法的平均周转时间还会增长。
常用于分时系统及事务处理系统，合理的时间片大小将带来满意的响应时间。
通常，合理的时间片指，能让80%左右的进程在一个时间片内完成。
对于短的、计算型的进程较有利。
不适合于批处理系统的进程调度。
不利于批处理系统的进程调度。
不利于i/0型的进程。
改进的方法之一，可以将i/0阻塞事件完成的进程单独组织一个就绪队列，该队列进程的时间片可以设置的小一些，且优先调度。
基于时间片轮转调度法循环式地为每个被调度的进程分配一个时间片，对每个进程都是公平的。
然而，实际应用中，进程的性质可能是不同的。例如，一个与用户进行交互的前台进程击破地需要对用户的输入做出响应，而一个后台打印进程的迫切性也许就不那么重要。
因此，可以为每个进程定义一个优先级，优先级越高的进程将优先获得处理机的调度。
进程完成功能的重要性
进程完成功能的急迫性
为均衡系统资源的使用，指定进程（作业）优先级
进程对资源的占用程度例如，可以为短进程（或作业）赋予较高的优先级。
静态优先级：一旦确定，则进程运行期间优先级一直不改变。
动态优先级：系统首先赋予进程一个初始优先级，该优先级将随着进程的运行而改变。
典型的动态优先级变化方式为：
优先级随着进程运行的剩余时间的减少而上升，使简要执行结束的进程尽快完成；
或随着进程排队等待时间的增长而上升，使等待时间越长的进程优先得到调度，不至于长时间饥饿。
具体实现方法，可以在每个时钟中断时，或需要进程切换时，重新计算就绪队列中各进程的优先级，并优先调度高优先级的进程。
采用动态优先级的两种调度算法：剩余时间最短者优先和响应比高者优先。
为了使将要结束的进程尽早结束，释放系统资源，让别的进程执行。可以在每个时钟中断时，根据就绪队列中各进的剩余执行时间动态调整其优先级，剩余时间最短的进程优先级最高。
显然，该算法是剥夺型的短进程优先调度算法，调度程序总是选择剩余执行时间最短的进程调度执行。
与短进程优先调度算法一样，该调度算法很难准确估计进程的剩余执行时间
由于长进程在未执行时，或刚开始执行的一段时间内，其剩余执行时间都不会最短，所以该算法对长进程不公平。
但是，它不像FCFS算法偏袒长进程，也不像轮转调度算法会产生很多中断而增加系统负担。
由于短进程提前完成，故采用剩余时间最短者优先的调度算法获得的平均周转时间比采用短进程优先算法短。
将进程的等待时间和进程的预期执行时间纳入优先级的计算，进程（预期执行时间）越长优先级越低，而随着进程的等待时间增长优先级上升，即进程的优先级与等待时间成正比，与进程执行那个时间成反比。令w表示等待时间，s表示预期执行执行时间，则响应比：R=w/s +1
调度方法：若当前执行进程执行完毕，或需要阻塞等待某事件而释放处理机，调度程序选择就绪队列中响应比最大的进程执行。
若等待时间相同，短进程因为s较小，R较大而优先调度。若进程的预期执行时间相同，则等待时间长的进程优先调度，相当于FCFS。
随着等待时间的增加，长进程的响应比不断增大，在某个时刻，也必然被调度。
同短进程优先和剩余时间最短者优先调度算法一样，很难准确估计进程的预期执行时间。
每次调度之前都需要计算响应比，增加了系统开销。
前面介绍的几种调度算法都存在各自不同的问题，尤其是短进程优先、剩余时间最短者优先以及响应比高者优先调度算法都需要估计进程的预期执行时间，如果估计不准确，将影响调度结果和系统性能。
如果根据进程执行历史，而非未来，进行调度，将解决这个问题。
反馈调度法就是一种根据进程执行历史调整调度方式的调度方法，它结合了优先级和时间片轮转调度思想。
该方法有利于交互型短进程或短批处理作业，因为他们一般只需要一个或很少的几个时间片即可完成，
但可能使长进程的周转时间急剧增加。
如果不断地有新进程到来，还可能出现长进程长期饥饿现象。
为此，可以为各队列设置不同的时间片，优先级越低时间片越长。
若队列中只有一个进程执行完是否会中断？
中断前提是有新进程到来或处理机空闲，
若有新进程到来，按时间片原则到时间片到则中断
若就绪队列1中正在执行，有新进程进入就绪队列0，进程怎么执行
注意是单处理机，时间片到会中断，若没有执行完进入下一就绪队列，而调度高优先级的进程进入就绪队列0，然后执行。
1如何选择进程调度算法与系统设计的目标有关.
2交互式多任务系统，主要考虑联机用户对响应时间的要求，一般采用基于时间片轮转调度算法，同时，根据进程的性质设置不同的优先级；
批处理系统往往以作业的平均周转时间按来衡量调度性能，常选用基于优先级的短进程（或作业）优先调度算法。
指，能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行的计算机系统。
分为实时控制系统和实时信息处理系统。
指要进行实时控制的系统
主要用于生产过程的控制，实时采集现场数据，并对所采集的数据进行及时处理，进而自动地控制相应的执行机构，使某些参数（如温度、压力、方位等）能按预定的规律变化，以保证产品的质量和提高产量。
也可用于武器的控制，如火炮的自动控制系统，飞机的自动驾驶系统，以及导弹的制导系统等。
实时信息处理系统
指能对信息进行实时处理的系统
该系统由一台或多台主机通过通信线路连接成百上千个远程终端，计算机接收从远程终端发来的服务请求，根据用户提出的问题，对信息进行检索和处理，并在很短额时间内位用户做出正确的回答。
典型的实时信息处理系统有：飞机订票系统、情报检索系统等。
指，具有及时性要求的，常常被重复执行的特定进程，在实时系统中习惯称为任务。
按任务执行时是否呈现周期性来分类：
（1）
（2）
截止时间包括：开始截止时间（任务在某时间以前，必须开始执行）和完成截止时间（任务在某时间以前必须完成）。
根据对截止时间的要求将实时任务划分为：
（1）
（2）
实时调度的目标
主要考虑如何使硬实时任务在其规定的截止时间内完成，同时，尽可能使软实时任务也能在规定的截止时间内完成。
而公平性和最短平均响应时间等要求已不再重要。
但是，大多数现代实时操作系统无法直接处理任务的截止时间，它们只能尽量提高响应速度，以尽快的调度任务。
实时性要求不太高的实时系统可用的调度算法：
基于时间片轮转调度算法
基于优先级的调度算法
最早截止时间优先调度算法，即优先调度截止时间最近的实时任务。
根据任务的周期大小赋予优先级，最短周期的任务具有最高优先级。其中，
任务周期，指一个任务到达至下一任务到达之间的时间范围。
任务速度（rate），即周期（以秒记）的倒数，以赫兹为单位。
任务周期的结束，表示任务的硬截止时间。任务的执行时间不应超过任务周期。
在RMS调度算法中，如果以任务速度为参数，则优先级函数是一个单调递增的函数，故称为速度单调算法。
该调度算法广泛用于工业实时系统的周期性任务调度。