操作系统第四章 并发处理

《操作系统第四章 并发处理》由会员分享，可在线阅读，更多相关《操作系统第四章 并发处理（91页珍藏版）》请在金锄头文库上搜索。

1、第四章 并发处理 4.1并发活动进程的引入 假设某个作业job由输入I，计算C，打印P三 个操作组成。 1. 单道批处理系统中，作业序列的处理过程 如下：C1I1I2P2P1C2tjob1job2为了提高资源利用率和系统吞吐量，引入 多道批处理系统。2、多道批处理系统中，作业序列的 处理过程如下：I1C1P1I2C3P2I3C2P3t从图中可以看出： 有的程序段的执行是有先后次序的，如C1，I2先于C2； 有的程序段可以并发执行，如P1，C2，I3；可以用伪代码描述并发执行 的程序段，由Dijkstra提出， Cobegin（Concomitant begin）S1;S2; ;Sn; Coen

2、d 表示S1，S2，Sn可以并发执 行。例如：S0; CobeginS1;S2; ;Sn; Coend Sn+1;表示先执行S0，再并 发执行S1，S2，Sn； 当S1，S2，Sn全部执 行 完毕后，再执行Sn+1。S0S1S2SnSn+1也可以用先后次序图（以后也称 进程流图）表示，它是一个有向 无环图。4.1.5并发执行程序的特点1.间断性如果Ci-1完成后，若Ii未完成，则Ci也无法处理， 导致计算程序段暂停。 2.失去程序的封闭性程序在并发执行时，是多个程序共享系统中的各 种资源，因而这些资源的状态将由多个程序来改变， 致使程序的运行失去封闭性。 3.不可再现性当初始条件相同时，程序多

3、次执行，其结果必 然重复出现，称为可再现性。例如：有一公共变量x，r1，r2为2个 寄存器。假设CPU分时执行p1,p2。有两个程序段： P1:r1=x;r1+;x=r1; P2:r2=x;r2+;x=r2;方式一执行： P1:r1=x;r1+;x=r1; P2:r2=x;r2+;x=r2;结果：x=x+2例如：有一公共变量x，r1，r2为2个 寄存器。假设CPU分时执行p1,p2。 有两个程序段： P1:r1=x;r1+;x=r1; P2:r2=x;r2+;x=r2;方式二执行： P1:r1=x; P2:r2=x;r2+;x=r2; P1:r1+;x=r1;结果：x=x+1可见，并发执行的程

4、序可 能发生不可再现性。为了描述并发执行程序的活动规 律因而引进新的概念进程。4.2进程的概念 进程20世纪60年代初期提出，可翻译为 process，task，action等。 定义1：进程时一个具有独立功能的程序关 于某个数据集合的一次运行活动。 定义2：从核心看来，进程是分了类的，根 据一组规则操纵的数据结构。进程与程序的关系：1. 进程与程序的联系 进程=程序（程序 段、数据段、栈段） +进程控制块（PCB） 程序是构成进程的组 成部分之一，一个进 程存在的目的就是执 行其所对应的程序。进程和程序的区别 程序是静止的，进程 是动态的（有生命周 期的） 进程是能独立运行的 单位，能与其它

5、进程 并发执行。 进程是资源分配的基 本单位，也是CPU调 度的基本单位。4.2.2进程的类型1.系统进程它们运行OS的程序，也称守护进程 （Daemon进程）。系统启动时创建，运行时 CPU处于核心态。 2.用户进程这类进程运行用户程序，直接为用户服务。进程的特征： 并发性：可以与其它进程在宏观上同时先 前推进。 动态性：进程是执行中的程序。 独立性：进行是资源分配和调度的基本单 位。 交互性：进程在运行时可能会与其它进程 发生直接或间接的相互作业。 异步性：每个进程都可以相对独立，不可 预知的速度向前推进。 结构性：每个进程都对应1个进程控制 块。4.2.3进程的状态进程的基本状态 就绪状

6、态（Ready）：获得了除CPU以外的所有资 源，一旦获得CPU控制权，就可以立即运行。 运行状态（Running）：当就绪进程由OS的进程 调度程序调度，得到CPU控制权，占用CPU运行的 状态。 等待状态（Wait）：若某一进程正在等待某一事 件的发生而暂时停止，这时，即使获得CPU控制 权也无法执行。或阻塞状态（Block）、睡眠状态 （Sleep）。二、进程状态变迁图 1、进程的三态模型：运行等待就绪 时间片到 被抢占进程调度I/O请求 中断请求服务等I/O请求完成等进程队列模型：CPU创建就绪队列OS调度时间片用完等待事件1等待事件2等待事件n 事件1发生事件n发生事件2发生因等待的

7、原因不同可以分为若干个等待队列，这样发现和唤醒等待的进程 较为方便。二、进程状态变迁图 2、进程的五态模型：运行等待就绪 时间片到 被抢占进程调度I/O请求 中断请求服务等I/O请求完成等终止创建结束接纳创建态(Create)：进程刚刚建立（如建立PCB），完成初始化，但未分配内存等资源。 终止态(Terminated)：正常结束或异常结束。13.在进程基本状态转换图中，增加换出（将进程换出至辅存）和换入（ 将进程从辅存换入至主存）两个操作，试画出进程状态转换图。二、进程状态变迁图 3、UNIX系统进程状态变迁图（p106）4.2.4进程的描述进程控制块（ Process Contral Bl

8、ock） 进程的活动除包括CPU执行的程序及对相关 数据的操作，还需要用一个数据结构来刻 画进程的动态特征，描述进程的状态、占 用资源、调度信息等，这个数据结构即PCB 。 每个进程包括4个要素：程序段、数据段、 栈段、进程控制块（PCB）。进程的组成：指针针1指针2指针3其它信息程序段数据段堆栈段进程控制块PCB进程控制块PCB的其它信息包括一下 主要内容： 进程标识符（Pid）：由OS创建进程时给出 ，要求唯一 进程的状态（Status） :作为进程调度时分 配处理机的主要依据。为了便于对进程实 施管理，通常把具有相同状态的进程链接 在一起，组成各种队列。如就绪队列、各 种等待队进程控制块

9、PCB的其它信息包括一下 主要内容：当前队列指针（next）：指向相同状态的下 一个PCB 。nextnextnextnextnextnextnextRun-startReady-q-startWait-pt-startPCBiPCB2PCB1PCBn进程控制块PCB的其它信息包括一下 主要内容：总链指针（all_q_next）：就系统中所有进 程的PCB勾链起来。nextAll-q- nextnextAll-q- nextnextAll-q- nextnextAll-q- nextNext=All-q- nextnextAll-q- nextNext=All-q- nextRun-start

10、Ready-q-startWait-pt-startPCBiPCB2PCB1PCBnAll-start进程控制块PCB的其它信息包括一下 主要内容：程序开始地址（start_addr）：表示进程的 程序从此开始执行。 进程优先级（priority）： CPU现场保护区（cpu_status）:进程控制块PCB的其它信息包括一下 主要内容：通信信息（communication information）:如 ：记录消息缓冲队列指针htprhptrPCB消息缓冲区1消息缓冲区2 消息缓冲区n进程控制块PCB的其它信息包括一下 主要内容：家族信息（process_family）：如父进程的 标识符pp

11、id 占有资源清单（own_resource）P103 unix系统的进程控制块4.3进程控制 进程控制是对系统中的全部进程实施有效 的管理。这些管理功能是由一些具有特定 功能的程序段原语实现的。原语是一 种特殊的系统调用命令，它可以完成一个 特定的功能，其特定是执行时不可中断。 思考：如何实现原语执行时不可中断？ 执行原语之前关中断，执行完之后开中 断。进程控制原语有：创建原语、撤销原语、阻 塞原语、唤醒原语、延迟原语。执行终止就绪等待延迟创建创建原语撤销原语阻塞原语唤醒原语延迟原语4.3.2进程创建进程的创建可来源以下事件： 1. 用户向系统提交作业或程序； 2. OS创建服务进程 3.

12、已存在的进程创建新的进程，如父进程创建 子进程。 一般来说进程的创建过程如下： 申请一个空闲的PCB； 初始化PCB，如进程号，优先级，状态等 为新的进程分配资源，如内存等 将新进程插入就绪队列。4.3.3进程的撤销引起进程终止的事件： 正常结束，如程序执行完毕 异常结束，如溢出 外界干预，如程序执行时用户ctrl+break算法：由运行指针得到当前进程的pid;释放本进程所占用的资源给父进程；该进程从总链队列中摘除；释放此pcb结构；转OS进程调度； 4.3.4进程阻塞（block,supend,wait）引起进程阻塞的事件 请求OS服务 请求中断处理 新的数据还未到达 无新工作可做算法：w

13、ait(chan) Chan进程等待的原因 p104 int p_wchan保护当前进程的CPU现场到PCB结构中；置该进程为“等待”状态； 将该进程的PCB插入到等待chan的等待队列； 转OS进程调度； 4.3.4进程唤醒 当进程等待的事件发生后，唤醒等待该事件的所有进 程。 Wakeup（chan） 找到该阻塞原因chan的队列指针； For（等待该事件的进程） 将进程移出此等待队列； 置进程状态为“就绪”； 将进程插入“就绪队列”； 可以看出：当前进程执行Wakeup（chan）原语之后继 续执行。4.3.6进程延迟 将需要延迟的进程的PCB按其延迟时间加入 到延迟队列的适当位置。 D

14、elay(seconds) Seconds:需延迟的秒数 Clock_ticks=secondsclock_rate /需延迟的 机内时间 Clock_rate:为时钟速率，即时钟中断信号/ 秒（如50次/秒）算法： 保护调用延迟原语的进程的CPU现场； 计算clock_ticks; 封锁延迟队列； 以clock_ticks值检索延迟队列并插入合适位置； 置该进程为延迟状态； 解锁延迟队列； 转OS进程调度； 注意: 延迟队列是临界资源，使用之前需上锁，使用完毕要解 锁。延迟队列的结构： PCB中有deltatime项，其值为进程所需延迟的clock_ticks与延迟队列中的前一个 进程的cl

15、ock_ticks数之差。 例如：有进程A,B,C的clock_ticks分别为2，5，10，则延迟队列为：Pid=AnextDeltatime=2Pid=BnextDeltatime=3Pid=CNext=Deltatime=5Delay-q-start假设进程D的clock_ticks=8 ，则应该插入延迟队列的什 么位置呢？插入延迟队列过程如下： Deltatimenew=clock_ticksD; i=1; Time= Deltatimenew deltatimei If time0 则 Deltatimenew=time； i+；goto If time0 则插入相比较进程的前 面， 该进程的deltatime=deltatimenew;后一个进程的deltatime=time ;思考：画出插入进程D后的延迟队列 ？插入进程D后的延迟队列:Pid=AnextDeltatime=2Pid=BnextDeltatime=3Pid=CNext=Deltatime=2Delay-q-startPid=DnextDeltatime=3分析这样处理延迟队列有什么好处？二、延迟唤醒进程 它是一个系统进程，系统初始化时被创建，由时钟中断激活，直到系统关 闭。 当时钟中断信号到来时执行以下算法： 封锁延迟队列； 取延迟队列的首元素； 将deltatime- -; If (d