04-进程描述与控制

null第四讲 进程描述与控制第四讲 进程描述与控制多道程序 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 顺序程序 并发程序 多道程序设计 与时间有关的错误 线程的基本概念 线程的引入 线程的实现 机制 综治信访维稳工作机制反恐怖工作机制企业员工晋升机制公司员工晋升机制员工晋升机制图 Solaris进程线程模型进程的基本概念 进程的概念 进程的基本状态及其转换 进程控制块 进程映像 (进程要素) 进程控制 进程的特征 一、多道程序设计一、多道程序设计顺序程序 并发程序 多道程序设计 与时间有关的错误1.顺序程序（1/2）1.顺序程序（1/2）程序： 指令或语句序列，体现了某种算法。 所有程序是顺序的。 顺序环境： 计算机系统中，只有一个程序在运行； 该程序独占系统中所有资源； 其执行不受外界影响。顺序程序（2/2）特征： 程序执行的顺序性 一个执行结束，另一个开始执行。 程序执行的封闭性 独占资源，执行过程中不受外界影响。 程序执行结果的确定性 即：程序结果的可再现性 程序运行结果与程序执行速度无关，只要初始状态相同，结果应相同。顺序程序（2/2）2.并发程序（1/4）2.并发程序（1/4）并发环境： 一定时间内，物理机器上有两个或两个以上的程序同时处于开始运行但尚未结束的状态，并且次序不是事先确定的。引入并发的目的： 为了提高资源利用率，从而提高系统效率。在顺序环境下，A先执行，B再执行 CPU利用率= 40/80 = 50% DEV1利用率= 15/80 =19% DEV2利用率= 25/80 =31% 在顺序环境下，A先执行，B再执行 CPU利用率= 40/80 = 50% DEV1利用率= 15/80 =19% DEV2利用率= 25/80 =31% 并发程序（2/4） t(s) t(s)CPU DEV1 DEV2 CPU CPUA1015203040 DEV2CPUDEV 1 DEV2 CPUB1020304025并发程序（3/4）并发程序（3/4）ABCPUDEV1DEV2CPUCPU1015203040 t(s)25DEV1CPU3545DEV2CPUDEV2在并发环境下，A、B可同时执行 CPU利用率= 40/45 = 89% DEV1利用率= 15/45 =33% DEV2利用率= 25/45 =56% 并发程序（4/4）特征： （1）程序执行结果的不可再现性 并发程序执行的结果与其执行的相对速度有关，是不确定的。 （2）在并发环境下程序的执行是间断性的 执行——停——执行 （3）资源共享 系统中资源被多个程序使用。 （4）独立性和制约性 独立的相对速度、起始时间。 程序之间可相互作用（相互制约）， 可分为直接作用和间接作用。 （5）程序和计算不再一一对应 （计算：一个程序的执行）并发程序（4/4）3.多道程序设计（Multiprogramming）3.多道程序设计（Multiprogramming）多道程序设计：允许多个程序同时进入内存并运行，其目的是为了提高系统效率。考虑因素： 在多道程序环境下如何向用户提供服务 在并发程序之间如何正确传递消息（通信） 如何对CPU进行调度，保证每个用户相对公平地得到CPU （CPU是一个只可调度，不可分配的资源） 如何管理其他资源 当各用户对资源使用上发生冲突时，如何处理竞争。 对CPU只能通过调度来解决竞争问题，而对于其他资源通过申请—分配—使用—回收的办法进行管理，当且仅当占有CPU的时候才可以申请，否则要排队等候。4.与时间有关的错误（1/4）4.与时间有关的错误（1/4）一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: ... ... read(x); read(x); if x>=1 then if x>=1 then x:=x-1; x:=x-1; write(x); write(x); ... ...nullCobegin get; copy; put; Coend复制一个记录与时间有关的错误（2/4）null f s t g 初始状态 3,4,...,m 2 2 (1,2) g,c,p 4,5,...,m 3 3 (1,2,3)  g,p,c 4,5,...,m 3 3 (1,2,2) X c,g,p 4,5,...,m 3 2 (1,2,2) X c,p,g 4,5,...,m 3 2 (1,2,2) X p,c,g 4,5,...,m 3 2 (1,2,2) X p,g,c 4,5,...,m 3 3 (1,2,2) X 设信息长度为m，有多少种可能性？与时间有关的错误（3/4）null并发环境下程序间的制约关系与时间有关的错误（4/4）二、进程的基本概念二、进程的基本概念进程的概念 进程的状态及其转换 进程控制块（PCB） 进程映像 (进程要素) 进程控制 进程的特征1.进程的概念1.进程的概念定义：Process 进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。 又称任务（Task） 为了描述程序在并发执行时对系统资源的共享，所需的一个描述程序执行时动态特征的概念。进程何时创建?进程何时创建?用户登录 提交一个程序执行 由OS创建，以向用户提供服务( 如：打印文件) 由已存在的一进程创建 一个用户程序可创建成多个进程进程何时中止?进程何时中止?程序执行Halt指令 用户退出登录 进程执行一个中止服务请求 出错及失败因素进程中止的原因（1/2）进程中止的原因（1/2）正常结束 给定时限到 缺少内存 存储器出界 保护性出错 如，写只读文件 算术错 超出时间 进程等待超过对某事件的最大值进程中止的原因（2/2）进程中止的原因（2/2）I/O 失败 无效指令 如，试图执行数据 特权指令 操作系统干预 如，当死锁发生时 父进程请求中止某一子进程 父进程中止，所以子进程也中止程序与进程的区别程序与进程的区别进程能真实地描述并发(程序不能) 进程是由程序和数据两部分组成的 程序是静态的，进程是动态的 进程有生命周期，有诞生有消亡，短暂的；而程序是相对长久的 一个程序可对应多个进程 进程具有创建其他进程的功能进程分类进程分类进程的分类： 系统进程 用户进程 系统进程优先于用户进程2.进程的基本状态及其转换2.进程的基本状态及其转换进程的三种基本状态： 运行态、就绪态、等待态 进程在消亡前处于且仅处于三种基本状态之一。 不同系统设置的进程状态数目不同。进程的三种基本状态进程的三种基本状态运行态（Running）： 进程占有CPU，并在CPU上运行。 就绪态（Ready）： 一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态（当调度给其CPU时，立即可以运行）。 等待态（Blocked）： 阻塞态、封锁态、睡眠态。 指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。null进程状态转换进程状态转换状态转换： 在进程运行过程中，由于进程自身进展情况及外界环境的变化，这三种基本状态可以依据一定的条件相互转换。 就绪→运行 运行→就绪 运行→等待 等待→就绪进程状态转换的原因进程状态转换的原因就绪 --> 运行 调度程序选择一个新的进程运行。 运行 --> 就绪 运行进程用完了时间片。 一个高优先级进程处于就绪状态，中断正在运行的进程。 运行 --> 等待 当一个进程必须等待时： OS尚未完成服务； 对一资源的访问尚不能进行； 初始化I/O 且必须等待结果； 等待某一进程提供输入。 等待 --> 就绪 当所等待的事件发生时。进程的其他状态创建状态，终止状态 挂起（suspend）状态 进程没有占用内存空间 处在挂起状态的进程映像在磁盘上 （调节负载，对换）进程的其他状态已完成创建一进程所必要的工作 已构造了进程标识符 已创建了管理进程所需的表格 但还没有允许执行该进程 (尚未同意) 因为资源有限中止后，进程移入该状态 它不再有执行资格 表格和其它信息暂时由辅助程序保留 可完成一些数据统计工作 当数据不再需要后，进程(和它的表格)被删除五状态进程模型五状态进程模型William Stallings七状态进程模型（1/4）七状态进程模型（1/4）William Stallings七状态进程模型（2/4）七状态进程模型（2/4）就绪状态(Ready)： 进程在内存且可立即进入运行状态 阻塞状态(Blocked)： 进程在内存并等待某事件的出现 阻塞挂起状态（Blocked, suspend）： 进程在外存并等待某事件的出现 就绪挂起状态（Ready, suspend）： 进程在外存，但只要进入内存，即可运行七状态进程模型（3/4）挂起（Suspend）：把一个进程从内存转到外存；可能有以下几种情况： 阻塞→阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，发生这种转换，以提交新进程或运行就绪进程。 就绪→就绪挂起：当有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程时，系统会选择挂起低优先级就绪进程。 运行→就绪挂起：对抢占式系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态。七状态进程模型（3/4）七状态进程模型（4/4）激活（Activate）：把一个进程从外存转到内存；可能有以下几种情况： 就绪挂起→就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，发生转换。 阻塞挂起→阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程（调入内存）。七状态进程模型（4/4）Linux进程状态（1/3）Linux进程状态（1/3）Linux的进程状态有五种 TASK_RUNNING：表示进程具备运行的资格，正在运行或等待被调度执行。进程控制块中有一个run_list成员，所有处于TASK_RUNNING状态的进程都通过该成员链在一起，称之为可运行队列。 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE： 两种状态均表示进程处于等待状态。TASK_INTERRUPTIBLE除了资源满足时可以被唤醒外，还可以被信号唤醒，而TASK_UNINTERRUPTIBLE则不行。Linux进程状态（2/3）Linux进程状态（2/3）TASK_STOPPED：进程处于暂停状态，主要用于调试目的。如正在运行的进程收到SIGSTOP信号将进入TASK_STOPPED状态。 TASK_ZOMBIE：表示进程已经结束运行并释放了大部分占用的资源，但task_struct结构还未被释放。Linux进程状态(3/3)Linux进程状态(3/3)3.进程控制块 （Process Control Block，PCB）3.进程控制块 （Process Control Block，PCB）概念： 系统为了管理进程设置的一个专门的数据结构，用它来记录进程的外部特征，描述进程的运动变化过程（又称进程描述符、进程属性）。 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。 进程与PCB是一一对应的。PCB的内容（1/3）PCB的内容（1/3）进程描述信息： 进程标识符(process ID)，唯一，通常是一个整数 进程名，通常基于可执行文件名（不唯一） 用户标识符(user ID) 进程控制信息： 当前状态 优先级(priority) 代码执行入口地址 程序的外存地址 运行统计信息（执行时间、页面调度） 进程间同步和通信；阻塞原因PCB的内容（2/3）PCB的内容（2/3）进程的队列指针 进程的消息队列指针 所拥有的资源和使用情况： 虚拟地址空间的现状 打开文件列表 CPU现场保护信息： 寄存器值（通用、程序计数器PC、程序状态字PSW） 指向赋予该进程的段/页表的指针 PCB的内容（3/3）PCB的内容（3/3）A. S. TanenbaumPCB组织方式（1/5）PCB组织方式（1/5）PCB表： 系统把所有PCB组织在一起，并把它们放在内存的固定区域，就构成了PCB表。 PCB表的大小决定了系统中最多可同时存在的进程个数，称为系统的并发度。 （注：多道程序中的多道与系统并发度不同）PCB组织方式（2/5）PCB组织方式（2/5）链接结构： 同一状态进程的PCB组成一个链表，不同状态对应多个不同的链表。 就绪链表、阻塞链表。 索引结构： 对具有相同状态的进程，分别设置各自的PCB索引表，表明PCB在PCB表中的地址。 进程队列： 不同状态进程分别组成队列。 运行队列、就绪队列、等待队列。PCB组织方式（3/5）PCB组织方式（3/5）William StallingsPCB组织方式（4/5）PCB组织方式（4/5）PCB组织方式（5/5）PCB组织方式（5/5）William Stallings4.进程映像 (进程要素)4.进程映像 (进程要素)代码段（用户程序） 数据段（用户数据） 用户栈（堆栈） 用于过程调用和参数传递 与系统栈区分 进程控制块PCB (进程属性) 用户进程不能直接访问、修改自己的PCB进程虚拟地址空间进程虚拟地址空间进程上下文环境（context）进程上下文环境（context）对进程执行活动全过程的静态描述。 由进程的用户地址空间内容、硬件寄存器内容及与该进程相关的核心数据结构组成。 用户级上下文： 进程的用户地址空间（包括用户栈各层次），包括用户正文段、用户数据段和用户栈。 寄存器级上下文： 程序计数器、程序状态寄存器、栈指针、通用寄存器的值。 系统级上下文： 静态部分（PCB和资源表格） 动态部分：核心栈（核心过程的栈结构，不同进程在调用相同核心过程时有不同核心栈） 5.进程控制5.进程控制创建、撤消进程以及完成进程各状态之间的转换，由具有特定功能的原语完成。 进程创建原语 进程撤消原语 阻塞原语 唤醒原语 挂起原语 激活（解挂）原语 改变进程优先级(1)进程的创建(1)进程的创建创建一个PCB 赋予一个统一进程标识符 为进程映象分配空间 初始化进程控制块 许多默认值 (如: 状态为 New，无I/O设备或文件...) 设置相应的链接 如: 把新进程加到就绪队列的链表中(2)进程的撤消(2)进程的撤消收回进程所占有的资源 撤消该进程的PCB(3)进程阻塞和进程唤醒处于运行状态的进程，在其运行过程中期待某一事件发生，如等待键盘输入、等待磁盘数据传输完成、等待其它进程发送消息，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态。6.进程的特征（1/2） 6.进程的特征（1/2） 并发性 任何进程都可以同其他进程一起向前推进 动态性 进程对应程序的执行 进程是动态产生，动态消亡的 进程在其生命周期内，在三种基本状态之间转换 动态的地址空间 独立性 进程是资源分配的一个独立单位 例如：各进程的地址空间相互独立进程的特征（2/2）进程的特征（2/2）交互性 指进程在执行过程中 可能与其他进程产生直接或间接的关系 异步性 每个进程都以其相对独立的、不可预知的速度向前推进 结构性： 进程的组成：程序+数据+PCB 可再入程序（可重入）： 可被多个进程同时调用的程序，具有下列性质： 它是纯代码的，即在执行过程中自身不改变，调用它的进程应该提供数据区。【思考题】【思考题】如果一个单处理机系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个？ 有没有如下所示的状态转换，为什么？ 等待—运行； 就绪—等待 一个状态转换的发生，是否一定导致另一个转换发生，列出所有的可能？ 举3个日常生活中类似进程的例子？三、线程的基本概念三、线程的基本概念线程的引入 线程与进程的对比 线程的实现 实例：Solaris1.线程的引入(1/4)1.线程的引入(1/4)进程的两个基本属性： 资源的拥有者 给每个进程分配一虚拟地址空间，保存进程映像，控制一些资源（文件，I/O设备），有状态、优先级、调度。 调度单位 进程是一个执行轨迹。 以上两个属性构成进程并发执行的基础。线程的引入（2/4）线程的引入（2/4）系统必须完成的操作： 创建进程 撤消进程 进程通信 进程切换 → 时间空间开销大，限制并发度的提高。 在操作系统中，进程的引入提高了计算机资源的利用率。但在进一步提高进程的并发性时，人们发现进程切换开销占的比重越来越大，同时进程间通信的效率也受到限制。线程的引入正是为了简化线程间的通信，以小的开销来提高进程内的并发程度。线程的引入（3/4）线程的引入（3/4）线程：有时称轻量级进程。 进程中的一个运行实体， 是一个CPU调度单位， 资源的拥有者还是进程或称任务。 将原来进程的两个属性分开处理。线程的引入（4/4）线程的引入（4/4）线程： 有执行状态（状态转换） 不运行时保存上下文 有一个执行栈 有一些局部变量的静态存储 可存取所在进程的内存和其他资源 可以创建、撤消另一个线程nullnull引入线程的好处引入线程的好处创建一个新线程花费时间少（结束亦如此） 两个线程的切换花费时间少 （如果机器设有“存储[恢复]所有寄存器”指令，则整个切换过程用几条指令即可完成） 线程之间相互通信无须调用内核（同一进程内的线程共享内存和文件） 适合多处理机系统例子例子例子1： LAN中的一个文件服务器，在一段时间内需要处理几个文件请求 有效的方法是：为每一个请求创建一个线程 在一个SMP机器上：多个线程可以同时在不同的处理器上运行例子2： 一个线程显示菜单，并读入用户输入；另一个线程执行用户命令 考虑一个应用：由几个独立部分组成，这几个部分不需要顺序执行，则每个部分可以以线程方式实现；当一个线程因I/O阻塞时，可以切换到同一应用的另一个线程2.线程与进程的比较2.线程与进程的比较调度 线程是独立调度的基本单位，进程是资源拥有的基本单位。 并发性 线程可以在进程内并发。 拥有资源 线程基本不拥有资源，进程拥有资源。 系统开销 线程开销小。3.线程的实现机制3.线程的实现机制用户级线程 核心级线程 两者结合方法（1）用户级线程（User Level Thread）（1）用户级线程（User Level Thread）由应用程序完成所有线程的管理 通过线程库(用户空间) 一组管理线程的过程 核心不知道线程的存在 线程切换不需要核心态特权 调度是针对应用的，是特定的创建、撤消线程 在线程之间传递消息和数据 调度线程执行 保护和恢复线程上下文对用户级线程的核心活动对用户级线程的核心活动核心不知道线程的活动，只管理线程的进程的活动 当线程调用系统调用时，整个进程阻塞 对线程库来说，线程仍然是运行状态 即线程状态是与进程状态独立的用户级线程的优点和缺点用户级线程的优点和缺点优点： 线程切换不调用核心 调度是应用程序特定的：可以选择最好的算法 ULT可运行在任何操作系统上（只需要线程库） 缺点： 大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞 核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上(2)核心级线程(Kernel Level Thread)(2)核心级线程(Kernel Level Thread)所有线程管理由核心完成 没有线程库，但对核心线程工具提供API 核心维护进程和线程的上下文 线程之间的切换需要核心支持 以线程为基础进行调度 例子：Windows核心级线程的优点和缺点核心级线程的优点和缺点优点： 对多处理器，核心可以同时调度同一进程的多个线程 阻塞是在线程一级完成 核心例程是多线程的 缺点： 在同一进程内的线程切换调用内核，导致速度下降（3）ULT和KLT结合方法（3）ULT和KLT结合方法线程创建在用户空间完成 线程调度等在核心态完成 例子：Solaris4.Solaris 进程线程模型4.Solaris 进程线程模型Solaris的多线程模型中包括四种实体： 进程，内核线程，用户线程和轻量级进程（LWP） Solaris内核是多线程的 进程是资源分配和管理的单元 内核级线程是内核的调度单元 用户级线程是程序执行在用户态的抽象 LWP把用户线程和内核线程绑定到一起Solaris进程模型Solaris进程模型进程 对用户程序执行上下文环境的抽象 包括虚拟内存地址空间, 程序资源和至少一个执行线程 硬件上下文 进程执行过程中的处理机信息, 它与CPU结构相关 总体来说,就是硬件寄存器的状态 (普通寄存器, 特权寄存器)‏ 保存在LWP中 软件上下文 地址空间, 证书,打开文件, 资源限制等等 ——同一进程中可被其他线程共享的资源LWP轻量级进程LWP轻量级进程LWP把内核线程和用户线程绑定到一起 当程序从用户态陷入到内核态时，用户线程的硬件上下为保存在内核线程的栈中，保存的位置存放在LWP结构中 发生系统调用时，系统调用的参数存放在LWP中 如果进程中有多个LWP，则这个进程的多个用户线程可以同时访问内核的系统调用进程、内核线程和LWP的关系进程、内核线程和LWP的关系进程的概念视图进程的概念视图进程执行环境进程执行环境重要的数据结构重要的数据结构进程的数据结构——proc进程的数据结构——procproc数据结构定义在文件usr/src/uts/common/sys/proc.h中内核线程和用户线程内核线程和用户线程内核线程的控制结构为_kthread，保存了与内核线程相关的信息： 内核栈信息 各类锁 调度类信息 …… 用户线程的控制结构是ulwp，保存了： 用户栈信息 用户线程的统计信息 用户态线程库管理用的信息用户线程、内核线程、lwp三者之间的关系用户线程、内核线程、lwp三者之间的关系多线程模型的演化多线程模型的演化作业作业多道程序系统的特征是什么？ 进程是什么？进程与程序有什么区别？ 进程的三种基本状态是什么？进程状态转换有哪几种类型？引起进程状态转换的原因分别是什么？ 什么是PCB？PCB的作用是什么？ 进程有哪些基本特征？ 什么是线程？引入线程有什么好处？线程与进程相比各有什么特点？