操作系统-进程和线程 课件.ppt

第2章进程和线程 2 1进程概念2 2进程的状态和组成2 3进程管理2 4线程2 5进程的同步和通信2 6经典进程同步问题2 7管程2 8进程通信2 9Linux的进程管理 2 1进程概念 2 1 1程序的顺序执行和并发执行程序的执行有两种方式 顺序执行和并发执行 顺序执行是单道批处理系统的执行方式 也用于简单的单片机系统 现在的操作系统多为并发执行 具有许多新的特征 引入并发执行的目的是为了提高资源利用率 例 循环程序A和B 共享一个变量N A每执行一次 都要做N N 1操作 B每执行一次时 都要执行Print N 操作 然后再将N置成 0 程序A和B以不同的速度运行 A N N 1 B printf d N N 0 1 N N 1在Print N 和N 0之前 此时得到的N值分别为n 1 n 1 0 2 N N 1在Print N 和N 0之后 此时得到的N值分别为n 0 1 3 N N 1在Print N 和N 0之间 此时得到的N值分别为n n 1 0 2 1 1多道程序设计 顺序执行的特征顺序性 按照程序结构所指定的次序 可能有分支或循环 封闭性 独占全部资源 计算机的状态只由于该程序的控制逻辑所决定可再现性 初始条件相同则结果相同 如 可通过空指令控制时间关系 并发执行的特征间断 异步 性 走走停停 一个程序可能走到中途停下来 失去原有的时序关系 失去封闭性 共享资源 受其他程序的控制逻辑的影响 如 一个程序写到存储器中的数据可能被另一个程序修改 失去原有的不变特征 失去可再现性 失去封闭性 失去可再现性 外界环境在程序的两次执行期间发生变化 失去原有的可重复特征 2 1 2进程概念 它对应虚拟处理机 虚拟存储器和虚拟外设等资源的分配和回收 引入多进程 提高了对硬件资源的利用率 但又带来额外的空间和时间开销 增加了OS的复杂性 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程 2 1 2进程概念 较典型的进程定义还有 1 进程是程序的一次执行 2 进程是一个程序及其数据在处理机上顺序执行时所发生的活动 3 进程是程序在一个数据集合上运行的过程 它是系统进行资源分配和调度的一个独立单位 2 进程的特征 动态性 进程具有动态的地址空间 数量和内容 地址空间上包括 代码 指令执行和CPU状态的改变 数据 变量的生成和赋值 系统控制信息 进程控制块的生成和删除 独立性 各进程的地址空间相互独立 除非采用进程间通信手段 并发性 异步性 虚拟 结构化 代码段 数据段和核心段 在地址空间中 程序文件中通常也划分了代码段和数据段 而核心段通常就是OS核心 由各个进程共享 包括各进程的PCB 2 1 2进程概念 进程和程序的区别 进程是动态的 程序是静态的 程序是有序代码的集合 进程是程序的执行 通常进程不可在计算机之间迁移 而程序通常对应着文件 静态和可以复制 进程是暂时的 程序的永久的 进程是一个状态变化的过程 程序可长久保存 进程与程序的组成不同 进程的组成包括程序 数据和进程控制块 即进程状态信息 进程与程序的对应关系 通过多次执行 一个程序可对应多个进程 通过调用关系 一个进程可包括多个程序 2 2进程的状态和组成 2 2 1进程的状态及其转换1 进程的基本状态运行状态 Running 就绪状态 Ready 阻塞状态 Blocked 新建状态 New 终止状态 Terminated 进程的基本状态 1 进程的三种基本状态运行态 正在占用CPU运行程序阻塞态 等待外部事件发生 无法占用CPU就绪态 可运行 但其他进程正在占用CPU 所有被暂时挂起 进程状态 进程的基本状态 2 运行态 阻塞态 就绪态 进程就绪 可以运行 状态转换 进程等待外部事件 阻塞 OS决定由哪个进程占用CPU 进程调度 进程状态 进程的基本状态 3 运行态变为就绪态强制终止某进程的运行 系统原因 运行态变为阻塞态运行进程等待外部事件发生 自身原因 阻塞态变为就绪态外部事件已经发生 可准备运行就绪态变为运行态停止其他进程运行后 运行该进程占用CPU 进程状态 进程的基本状态 4 问题1 为什么不能从阻塞态变为运行态呢 问题2 为什么不能从就绪态变为阻塞态呢 答案 三种状态的变换体现了OS的资源管理作用进程的核心思想在于运行 CPU资源的分配 进程状态 2 五种进程状态的转换 图2 2进程的5种基本状态及其转换 图进程的五种基本状态及其转换 2 2 2进程描述 1 进程映像进程映像由它的 用户 地址空间内容 硬件寄存器内容和与该进程有关的核心数据结构组成 图2 3进程映像模型 2 2 2进程描述 2 进程控制块的组成进程控制块 PCB 有时也称进程描述块 ProcessDescriptor 它是进程组成中最关键的部分 其中含有进程的描述信息和控制信息 是进程动态特性的集中反映 是系统对进程施行识别和控制的依据 进程描述信息 进程标识符 processID 唯一 通常是一个整数 进程名 通常基于可执行文件名 不唯一 用户标识符 userID 进程组关系 processgroup 进程控制信息 当前状态 优先级 priority 代码执行入口地址 程序的外存地址 运行统计信息 执行时间 页面调度 进程间同步和通信 阻塞原因资源占用信息 虚拟地址空间的现状 打开文件列表CPU现场保护结构 寄存器值 通用 程序计数器PC 状态PSW 地址包括栈指针 进程控制块的内容 3 进程控制块的作用 OS是根据PCB来对并发进程进行控制和管理的 PCB是进程存在的唯一标志 PCB经常被系统访问 系统将所有的PCB组织成若干个链表 或队列 存放在内存PCB区内 进程控制块是进程实体的一部分 由OS维护 用来记录进程相关信息 2 2 3进程队列 1 线性方式 图2 4PCB线性队列示意图 2 2 3进程队列 2 链接方式 图2 5PCB链接队列示意图 图2 6PCB索引结构示意图 2 2 3进程队列 3 索引方式 2 3进程管理 2 3 1进程图进程图 ProcessGraph 是描述进程族系关系的有向树 图2 7进程创建的层次关系 2 3 2进程创建 引发创建进程的事件通常是调度新的批作业 交互式用户登录 操作系统提供服务和现有进程派生新进程 创建新进程时要执行创建进程的系统调用 如UNIX Linux系统中的fork 其主要操作过程有如下四步 1 申请一个空闲的PCB 2 为新进程分配资源 3 将新进程的PCB初始化 4 将新进程加到就绪队列中 下面这个C程序展示了UNIX系统中父进程创建子进程及各自分开活动的情况 includevoidmain intargc char argv intpid forkanotherprocess pid fork if pid 0 erroroccurred fprintf stderr ForkFailed exit 1 elseif pid 0 childprocess execlp bin ls ls NULL else parentprocess parentwillwaitforthechildtocomplete wait NULL printf ChildComplete exit 0 2 3 3进程终止 1 正常终止 2 异常结束 越界错误 保护错 非法指令 特权指令错 运行超时 等待超时 算术运算错 I O故障 3 外部干扰 操作员或操作系统干预 父进程请求 父进程终止 终止进程的主要操作过程如下 找到指定进程的PCB终止该进程的运行回收该进程所占用的全部资源终止其所有子孙进程 回收它们所占用的全部资源 将被终止进程的PCB从原来队列中摘走 2 3 4进程阻塞 1 引起进程阻塞和唤醒的事件 请求系统服务2 启动某种操作3 新数据尚未到达 4 无新工作可做 进程阻塞的过程如下 立即停止当前进程的执行现行进程的CPU现场保存现行状态由 运行 改为 阻塞 转到进程调度程序 2 3 5进程唤醒 唤醒原语执行过程如下 把阻塞进程从相应的阻塞队列中摘下 将现行状态改为就绪状态 然后把该进程插入就绪队列中 如果被唤醒的进程比当前运行进程的优先级更高 则设置重新调度标志 2 4线程 2 4 1线程概念1 线程的引入进程 资源分配单位 存储器 文件 和CPU调度 分派 单位 又称为 任务 task 以进程作为并发执行的单位 系统进程创建 撤消和切换中要付出较大的时空开销 这限制了并发程度的提高 线程 作为CPU调度单位 而进程只作为其他资源分配单位 只拥有必不可少的资源 如 线程状态 寄存器上下文和栈同样具有就绪 阻塞和执行三种基本状态 2 线程的组成 每个线程有一个thread结构 即线程控制块 用于保存自己私有的信息 主要由以下4个基本部分组成 图2 8thread结构示意图 线程必须在某个进程内执行一个进程可以包含一个线程或多个线程 图2 9单线程和多线程的进程模型 3 线程的状态运行状态就绪状态阻塞状态终止状态 4 线程和进程的关系 一个进程可以有多个线程 但至少要有一个线程 而一个线程只能在一个进程的地址空间内活动 资源分配给进程 同一进程的所有线程共享该进程的所有资源 处理机分配给线程 即真正在处理机上运行的是线程 线程在执行过程中需要协作同步 不同进程的线程间要利用消息通信的办法实现同步 5 引入线程的好处 易于调度 提高并发性 开销少 利于充分发挥多处理器的功能 2 4 2在用户空间实现线程 把线程库整个地放在用户空间 核心对线程一无所知 图2 10 a 在用户空间实现线程 1 在用户空间实现线程的优点 线程切换速度很快 调度算法可以是应用程序专用的 用户级线程可以运行在任何操作系统上 包括不支持线程机制的操作系统 2 用户级线程的主要缺点 系统调用的阻塞问题 在单纯用户级线程方式中 多线程应用程序不具有多处理器的优点 2 4 3在核心空间实现线程 核心知道线程存在 并对它们实施管理 在多处理器系统中 核心可以同时调度同一进程的多个线程 如果一个进程的某个线程阻塞了 核心可以调度同一个进程的另一个线程 优点是 核心线程本身也可以是多线程的 缺点 主要是控制转移开销大 图2 10 b 在核心空间实现线程 2 4 4组合方式 1 多对一模型 图2 11在核心级线程上有多个用户级线程 图2 12多对一模型 2 4 4组合方式 2 一对一模型 图2 13一对一多模型 2 4 4组合方式 3 多对多模型 图2 14多对一多模型 2 4 5线程池 好处 1 服务速度更快 2 可用于限定系统中线程的数量 思想 在进程建立时就创建若干线程 把它们放在一个池中 它们在那里等待工作 一旦服务器接收到一个请求 就唤醒池中的一个线程 并把请求传给它 由该线程进行服务 一旦它完成工作 便返回池中 等待进行下面的服务 如果池中没有可用的线程 那么 服务器就要等待 直至有一个线程被唤醒 2 5进程的同步和通信 硬件或软件 如外设 共享代码段 共享数据结构 多个进程在对其进行访问时 关键是进行写入或修改 必须互斥地进行 有些共享资源可以同时访问 如只读数据 多道程序环境 进程之间存在资源共享 进程的运行时间受影响 进程间的相互关系互斥 进行竞争 独占分配到的部分或全部共享资源 同步 进行协作 等待来自其他进程的信息 通信 2 5 1进程的同步和通信 1 同步所谓同步 就是并发进程在一些关键点上可能需要互相等待与互通消息 这种相互制约的等待与互通消息称为进程同步 同步意味着两个或多个进程之间根据它们一致协议进行相互作用 同步的实质是使各合作进程的行为保持某种一致性或不变关系 要实现同步 一定存在着遵循的同步规则 缓冲区B P1进程 P2进程 进程间同步问题示意图 2 互斥 指进程间因相互竞争使用独占型资源 而产生的制约关系 它主要由资源共享引起 这种关系表现形式为 进程 资源 进程 进程间资源访问冲突共享变量的修改冲突操作顺序冲突 共享变量的修改冲突 T1 Read x if x 1 x x 1 Write x T2 Read x if x 1 x x 1 Write x 5 x 4 5 4 考虑一个飞机订票系统 两个终端 运行T1 T2进程 操作顺序冲突 例 生产者 消费者问题 生产者指针in 消费者指针out n 1 in in 1 n out out 1 n 满 空 生产者和消费者两进程共享下面的变量 intn 缓冲区数目typeitem itembuffer n 产品缓冲区intin out 输入指针 输出指针intcounter 产品数量 Producer While 1 produceaniteminnextp while counter n buffer in nextp in in 1 n counter counter 1 consumer while 1 while counter n nextc buffer out out out 1 n counter counter 1 consumertheiteminnextc 对于Counter变量的操作 生产者和消费者执行如下 register1 counter register2 counter register1 register1 1 register2 register2 1 counter register1 counter register2 并发时可能产生错误 2 5 2临界资源和临界区 1 临界资源和临界区一次仅允许一个进程使用 我们把这类共享资源称为临界资源 CriticalResource 在每个进程中访问临界资源的那段程序叫做临界区 CriticalSection 简称CS区 2 5 2临界资源和临界区 2 进程的一般结构 图2 15典型进程的一般结构 2 5 2临界资源和临界区 3 临界区进入准则 如果若干进程要求进入空闲的临界区 一次仅允许一个进程进入 任何时候 处于临界区内的进程不可多于一个 进入临界区的进程要在有限时间内退出 如果进程不能进入自己的临界区 则应让出CPU 避免进程出现 忙等 现象 2 5 2临界资源和临界区 图2 16互斥使用临界区 2 5 3互斥实现方式 1 利用硬件方法解决进程互斥问题 1 禁止中断 2 专用机器指令 将内存单元上锁2 原语是机器指令的延伸 往往是为完成某些特定的功能而编制的一段系统程序 原语操作也称做 原子操作 atomicaction 即一个操作中的所有动作要么全做 要么全不做 执行原语操作时 要屏蔽中断 以保证其操作的不可分割性 2 5 3互斥实现方式 3 利用软件方法解决进程互斥问题可为每类临界区设置一把锁 该锁有打开和关闭两种状态 关锁原语lock W while W 1 W 1 开锁原语unlock W w 0 2 5 3互斥实现方式 进程A lock W 打印信息S CS区unlock W 进程B lock W 打印信息S CS区unlock W 2 5 4信号量 1 整型信号量P操作最初源于荷兰语proberen 表示测试 V操作源于荷兰语verhogen 表示增加 在有些书上将P操作称做wait或者DOWN操作 将V操作称做signal或者UP操作 P和V操作都是原语 P和V操作可描述为 P while S 0 S S 1 V S S 1 使用P V操作实现互斥的形式 do P mutex 临界区V mutex while 1 2 5 4信号量 2 结构型信号量结构型信号量一般是由两个成员组成的数据结构 其中一个成员是整型变量 表示该信号量的值 另一个是指向PCB的指针 typedefstruct intvalue structPCB list semaphore 2 5 4信号量 信号量的值与相应资源的使用情况有关 图2 17信号量的一般结构及PCB队列 2 5 4信号量 P操作的定义如下 voidP semaphoreS S value if S value 0 把这个进程加到S list队列 block 2 5 4信号量 V操作的定义如下 voidV semaphoreS S value if S value 0 从S list队列中移走进程Q wakeup Q 在具体实现时应注意 P V操作都应作为一个整体实施 不允许分割或相互穿插执行 S value的初值表示系统中某类资源的数目每次wait操作 意味着进程请求一个单位的该类资源当S value 0时 表示该类资源已分配完毕 因此进程应调用block原语 进行自我阻塞 放弃处理机 并插入到信号量链表S L中 此时S value的绝对值表示在该信号量链表中已阻塞进程的数目 每次signal操作 表示执行进程释放一个单位资源 故S value S value 1操作表示资源数目加1 若加1后仍是S value 0 则表示在该信号量链表中 仍有等待该资源的进程被阻塞 故还应调用wakeup原语 将S L链表中的第一个等待进程唤醒 如果S value的初值为1 表示只允许一个进程访问临界资源 此时的信号量转化为互斥信号量 3 AND型信号量 在两个进程中都要包含两个对Dmutex和Emutex的操作 即processA processB wait Dmutex wait Emutex wait Emutex wait Dmutex 若进程A和B按下述次序交替执行wait操作 processA wait Dmutex 于是Dmutex 0 processB wait Emutex 于是Emutex 0 processA wait Emutex 于是Emutex 1A阻塞 processB wait Dmutex 于是Dmutex 1B阻塞 AND同步机制的基本思想是 在一个原语中 将一段代码同时需要的多个临界资源 要么全部分配给它 要么一个都不分配 称为Swait SimultaneousWait 在Swait时 各个信号量的次序并不重要 虽然会影响进程归入哪个阻塞队列 但是由于是对资源全部分配或不分配 所以总有进程获得全部资源并在推进之后释放资源 因此不会死锁 为此 在wait操作中 增加了一个 AND 条件 故称为AND同步 或称为同时wait操作 即Swait Simultaneouswait 定义如下 Swait S1 S2 Sn P原语 while TRUE if S1 1 Ssignal S1 S2 Sn for i 1 i n i Si 释放占用的资源 for eachprocessPwaitinginSi queue 检查每种资源的等待队列的所有进程 从等待队列Si queue中取出进程P if 判断进程P是否通过Swait中的测试 注 与signal不同 这里要进行重新判断 通过检查 资源够用 时的处理 进程P进入就绪队列 else 未通过检查 资源不够用 时的处理 进程P进入某等待队列 2 5 5信号量的一般应用 1 用信号量实现进程互斥Pa Pb P mutex P mutex 分配打印机释放打印机 读写分配表 读写分配表 V mutex V mutex 2 5 5信号量的一般应用 利用信号量实现互斥的一般模型是 进程P1进程P2 进程Pn P mutex P mutex P mutex 临界区临界区临界区V mutex V mutex V mutex 2 5 5信号量的一般应用 使用P V操作实现互斥时应注意两点 在每个程序中用于实现互斥的P mutex 和V mutex 必须成对出现 即先做P 进入临界区 后做V 退出临界区 互斥信号量mutex的初值一般为1 2 5 5信号量的一般应用 2 用信号量实现进程简单同步 图2 18简单供者和用者对缓冲区的使用关系 2 5 5信号量的一般应用 供者和用者间要交换两个消息 缓冲区空和缓冲区满的状态 设置两个信号量 S1表示缓冲区是否空 0表示不空 1表示空 S2表示缓冲区是否满 0表示不满 1表示满 规定S1和S2的初值分别为1和0 2 5 5信号量的一般应用 供者进程用者进程L1 P S1 L2 启动读卡机P S2 从缓冲区取出信息收到输入结束中断V S1 V S2 加工并且存盘gotoL1 gotoL2 2 5 5信号量的一般应用 用P和V操作实现同步时应注意如下三点 分析进程间的制约关系 确定信号量种类 信号量的初值与相应资源的数量有关 也与P V操作在程序代码中出现的位置有关 同一信号量的P V操作要 成对 出现 但是 它们分别出现在不同的进程代码中 2 6经典进程同步问题 1 生产者 消费者问题如果一个进程能产生并释放资源 则该进程称做生产者 如果一个进程单纯使用 消耗 资源 则该进程称做消费者 问题可以表述如下 一组生产者进程和一组消费者进程 设每组有多个进程 通过缓冲区发生联系 生产者进程将生产的产品 数据 消息等统称为产品 送入缓冲区 消费者进程从中取出产品 假定缓冲区共有N个 不妨把它们设想成一个环形缓冲池 1 生产者 消费者问题 图2 19生产者 消费者问题环形缓冲池 它们应满足如下同步条件 任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量 N 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量 1 生产者 消费者问题 1 设缓冲区的编号为0 N 1 in和out分别是生产者进程和消费者进程使用的指针 指向下面可用的缓冲区 初值都是0 2 设置三个信号量 full 表示放有产品的缓冲区数 其初值为0 empty 表示可供使用的缓冲区数 其初值为N mutex 互斥信号量 初值为1 表示各进程互斥进入临界区 保证任何时候只有一个进程使用缓冲区 1 生产者 消费者问题 生产者进程Producer 消费者进程Consumer while TRUE while TRUE P empty P full P mutex P mutex 产品送往buffer in 从buffer out 中取出产品 in in 1 modN out out 1 modN 以N为模 以N为模 V mutex V mutex V full V empty 2 6经典进程同步问题 2 读者 写者问题读者 写者问题也是一个著名的进程互斥访问有限资源的同步问题 例如 一个航班预订系统有一个大型数据库 很多竞争进程要对它进行读 写 允许多个进程同时读该数据库 但是在任何时候如果有一个进程写 即修改 数据库 那么就不允许其他进程访问它 既不允许写 也不允许读 2 读者 写者问题 设置两个信号量 读互斥信号量rmutex和写互斥信号量wmutex 另外设立一个读计数器readcount 它是一个整型变量 初值为0 rmutex 用于读者互斥地访问readcount 初值为1 wmutex 用于保证一个写者与其他读者 写者互斥地访问共享资源 初值为1 2 读者 写者问题 读者Readers while TRUE P rmutex readcount readcount 1 if readcount 1 P wmutex V rmutex 执行读操作P rmutex readcount readcount 1 if readcount 0 V wmutex V rmutex 使用读取的数据 写者Writers while TRUE P wmutex 执行写操作V wmutex 这个算法隐含读者的优先级高于写者 2 6经典进程同步问题 3 哲学家进餐问题 图2 20哲学家进餐问题 五位哲学家围坐在一张圆桌旁进餐 每人面前有一只碗 各碗之间分别有一根筷子 每位哲学家在用两根筷子夹面条吃饭前独自进行思考 感到饥饿时便试图占用其左 右最靠近他的筷子 但他可能一根也拿不到 他不能强行从邻座手中拿过筷子 而且必须用两根筷子进餐 餐毕 要把筷子放回原处并继续思考问题 定义信号量集chopstick 5 初值为 1 1 1 1 1 voidphilosopher inti while 1 think P chopstick i 1 5 P chopstick i eat V chopstick i 1 5 V chopstick i 解法1 死锁 哲学家进餐问题 defineN5 defineLEFT i 1 N defineRIGHT i 1 N defineTHINKING0 defineHUNGRY1 defineEATING2typedefstruct 定义结构型信号量 intvalue structPCB list semaphore intstate N semaphoremutex 1 互斥进入临界区 semaphores N 每位哲学家一个信号量 解法2 哲学家进餐问题 voidphilosopher inti while TRUE think 哲学家在思考问题 take chopstick i 拿到两根筷子或者等待 eat 进餐 put chopstick i 把筷子放回原处 voidtake chopstick inti P mutex state i HUNGRY test i 试图拿两根筷子 V mutex P s i 解法2 哲学家进餐问题 voidput chopstick inti P mutex state i THINKING test LEFT 查看左邻 现在能否进餐 test RIGHT 查看右邻 现在能否进餐 V mutex voidtest inti if state i HUNGRY 解法2 定义信号量集chopsiick 5 初值为 1 1 1 1 1 voidphilosopher inti while 1 think SSwait chopstick i 1 5 chopstick i eat SSignal chopstick i 1 5 chopstick i 解法3 4 打瞌睡的理发师问题 理发店里有一位理发师和一把理发椅 还有N张座椅供等候的顾客休息 在没有顾客的时候 理发师就会躺在理发椅上睡觉 因此 当有顾客来到理发店时 他必须先叫醒理发师 如果理发师正在理发时又有顾客来到 此时 如果有空椅子可坐 他们就会坐下来等 如果没有空椅子 就会离开 问题 用信号量和P V原语写出理发师和顾客行为的程序描述 问题描述 睡着的理发师问题 本图摘自AndrewS Tanenbaum ModernOperatingSystems S1判断有多少人在等待 有多少把椅子 若椅子不够 转S5 S2如果是第一个顾客 就去叫醒理发师 S3走到一把空椅子处坐下等 等理发师叫自己 S4理发中 S5离开理发店 问题分析 顾客的做法 S1判断是否有人在等 若没有 就去睡觉 若有 转S2 S2去唤醒一个正在等待的顾客 S3理发中 S4转S1 理发师的做法 需要设置一个整型的waiting变量 来记录正在等待的顾客个数 对于理发师和各个顾客而言 waiting变量是一个临界资源 对它的访问必须互斥地进行 因此需要设置一个互斥信号量S mutex 顾客可能需要去唤醒理发师 理发师也需要去唤醒顾客 两者之间存在着同步关系 所以需要两个信号量S customer和S barber defineCHAIRS5 椅子的个数intwaiting 0 等待的顾客个数semaphoreS mutex 互斥信号量 初值为1semaphoreS customer 等待的顾客数 初值0semaphoreS barber 空闲的理发师个数 0 睡着的理发师问题 voidbarber void while TRUE P S customer 若无顾客 睡去P S mutex 申请对waiting的访问waiting waiting 1 等待的顾客数减1V S barber 理发师有空 唤醒顾客 V S mutex 结束对waiting的访问cut hair 给顾客理发 理发师进程 voidcustomer void P S mutex 申请对waiting的访问if waiting CHAIRS waiting waiting 1 等待的顾客数加1V S customer 新增一顾客 唤醒理发师 V S mutex 结束对waiting的访问P S barber 理发师有空否 get haircut 理发中 else V S mutex 理发店满员了 走先 顾客进程 2 7管程 管程 一个管程定义一个数据结构和能为并发进程在其上执行的一组操作 这组操作能使进程同步和改变管程中的数据 一个管程由管程名称 局部于管程的共享数据的说明 对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成 2 7管程 图2 22管程的结构 2 7管程 管程具有以下三个特性 管程内部的局部数据变量只能被管程内定义的过程所访问 不能被管程外面声明的过程直接访问 进程要想进入管程 必须调用管程内的某个过程 一次只能有一个进程在管程内执行 而其余调用该管程的进程都被挂起 等待该管程成为可用的 即管程能有效地实现互斥 2 7管程 实现互斥是由编译程序完成 为解决同步问题 引入两个条件变量x和y conditionx y 操作原语wait x 挂起等待条件x的调用进程 释放相应的管程 以便供其他进程使用 操作原语signal x 恢复执行先前因在条件x上执行wait而挂起的那个进程 管程的职责与信号量的职责不同 带条件变量的管程结构 利用管程解决生产者 消费者问题 建立一个命名为Producer Consumer管程 包括两个过程 1 put item 过程 生产者利用该过程将自己生产的产品投放到缓冲池中 并用整型变量count来表示在缓冲池中已有的产品数目 当count n时 表示缓冲池已满 生产者须等待 2 get item 过程 消费者利用该过程从缓冲池中取出一个产品 当count 0时 表示缓冲池中已无可取用的产品 消费者应等待 beginmonitorproducer consumer intcount conditionfull empty voidput intitem if count n p full 将产品放入缓冲区 count count 1 if count 1 v empty produce itemget if count 0 p empty item 取产品count count 1 if count N 1 v full count 0 endmonitor 在利用管程解决生产者 消费者问题时 其中的生产者和消费者可描述为 Producer while 1 produceanitemin PC put item consumer While 1 item PC get consumetheitem 2 8进程通信 进程通信是指进程间的信息交换 上述进程的互斥和同步机构因交换的信息量少 被归结为低级进程通信 高级进程通信方式有很多种 大致可归并为共享存储器 消息传递和管道文件三类 1 共享存储器方式共享存储器方式是在内存中分配一片空间作为共享存储区 需要进行通信的各个进程把共享存储区附加到自己的地址空间中 然后 就像正常操作一样对共享区中的数据进行读或写 2 8进程通信 2 消息传递方式消息传递方式以消息 Message 为单位在进程间进行数据交换 直接通信方式 间接通信方式 2 8进程通信 3 管道文件方式管道文件也称管道线 它是连接两个命令的一个打开文件 一个命令向该文件中写入数据 称做写者 另一个命令从该文件中读出数据 2 8进程通信 2 8 1消息传递系统send和receive的一般格式是 send destination message receive source message 2 8 1消息传递系统 表2 3消息传递系统设计要点 消息传递系统 用消息传递方式解决生产者 消费者问题 defineN100 缓冲区个数 voidproducer void intitem messagem 消息缓冲区 while TRUE item produce item 生成一些数据放入缓冲区 receive consumer 向消费者发送一个数据项 voidconsumer void intitem i messagem for i 0 i N i send producer 使用数据项进行操作 2 8 2客户 服务器系统中的通信 常用的进程通信方式有socket和远程过程调用 1 socketsocket好像一条通信线两端的接插口 只要通信双方都有插口 并且中间有通信线路相连 就可以互相通信了 一对进程通过网络进行通信要用一对socket 每个进程一个 一个socket在逻辑上有网络地址 连接类型和网络规程三个要素 2 8 2客户 服务器系统中的通信 网络地址表明一个socket用于哪种网络连接类型表明网络通信所遵循的模式 主要分为 有连接 和 无连接 模式 网络规程表明具体网络的规程 一般来说 网络地址和连接类型结合在一起就基本上确定了适用的规程 2 8 2客户 服务器系统中的通信 图2 25socket通信流程 2 8 2客户 服务器系统中的通信 2 远程过程调用远程过程调用 RemoteProcedureCall RPC 是远程服务的一种最常见的形式 2 9Linux的进程管理 2 9 1Linux进程概述2 9 2Linux进程控制2 9 3Linux进程通信 1 进程控制块及任务结构内核将进程放在叫作任务队列的双向循环链表中 链表中的每一项都是类型为task struct 称为进程描述符的结构 Task struct结构描述了一个正在执行的程序的所有信息 如 进程当前的状态调度信息进程标识进程通信信息进程的家族关系时间和定时信息文件系统信息存储管理信息CPU现场保留信息 进程描述符及任务队列 内核通过一个唯一的进程标识值PID来标识每个进程 PID的最大值默认为32768 进程描述符及内核栈 返回到本节 Linux内核通过进程task struct结构中的信息来进行进程的控制 首先通过其中的调度信息决定该进程是否运行 当进程被调度在CPU上运行时 要根据task struct结构中保留的处理机现场来恢复进程运行现场 再根据虚拟内存信息定位进程的正文和数据 并通过其中的通信信息和其他进程实现同步与通信 总之 对进程所有操作都要依赖task struct结构 task struct结构是进程实体的核心 是进程存在的惟一标志 2 9 1Linux进程概述 2 进程的状态进程是一个动态的概念 在其运行的整个生命周期中可根据具体情况不断改变其状态 Linux进程主要有如下几种状态 1 可运行状态 TASK RUNNING 2 可中断状态 TASK INTERRUPTIBLE 3 不可中断状态 TASK UNINTERRUPTIBLE 4 暂停状态 TASK STOPPED 5 僵死状态 TASK ZOMBLE 2 9 2Linux进程控制 1 进程创建调用fork 的进程称为父进程 通过fork 建立的新进程称为子进程 系统执行fork 时 将为新进程分配空闲的task struct结构和进程标识号 PID 为新进程堆栈分配物理页 fork 采用了一种称为写时拷贝的实现技术 即fork 并不复制整个进程的地址空间 而是让父进程和子进程共享同一个拷贝 只有在需要写入的时候 数据才会被复制 2 等待进程结束当父进程用fork 创建子进程后 子进程往往通过exec 转去执行新装载的程序映像 父进程可用系统调用wait 等待它的一个子进程的结束 wait 的参数指定了父进程等待的子进程 如果子进程尚未终止 未完成任务 则父进程挂起 一旦等到指定的子进程结束 父进程被唤醒 即可继续再做其他工作 2 9 2Linux进程控制 3 进程终止当需要一个进程结束或进程希望终止自己时 可通过系统调用exit 来实现 Exit 首先释放进程占用的大部分资源 进入 task zombie 状态 并返回一个状态参数 父进程执行wait 时 可取得该参数 使等待子进程结束的父进程恢复执行 处于TASK ZOMBIE状态的进程占用的所有资源就是 内核栈 thread info结构和task struct结构 此时进程存在的唯一目的就是向它的父进程提供信息 父进程检索到信息后 或通知内核那时无关的信息后 由进程所持的剩余内存被释放 归还给系统 如果父进程在子进程之前退出 则init进程将称为该孤儿进程的父进程 负责回收事宜 2 9 2Linux进程控制 返回到本节 图2 20shell执行流程 2 9 3Linux进程通信 1 信号机制信号是Linux最基本的进程通信机制 信号机制的一个主要特点是它的异步特性 这表现在进程在执行期间可随时接收到信号 甚至可能当进程正在执行系统调用时接收信号 1 信号类型 2 信号处理方式 3 信号的发送 4 信号的检测和处理 2 9 3Linux进程通信 2 管道机制管道是实现进程间大容量信息传送的机构 1 匿名管道匿名管道由pipe 系统调用创建 其原型为 intpipe intfd 2 2 命名管道 FIFO文件 Linux还支持另外一种管道形式 命名管道 命名管道操作方式是按先进先出方式传送信息也称为FIFO文件 FIFO文件和匿名管道的数据结构及操作极其相似 二者主要区别在于FIFO文件是按名存取文件 在使用之前就已经存在 用户可打开或关闭FIFO文件 而匿名管道只在操作时存在 是临时对象 另外 命名管道容许具有适当权限的进程利用标准的open 系统调用加以访问 即使是无关系的进程 而父进程不同的进程难以共享匿名管道 2 9 3Linux进程通信 2 9 3Linux进程通信 3 SystemV的进程通信机制为了与其他系统兼容 Linux支持三种SystemV进程通信