专业的医疗行业网站模板,服务周到的网站建站,北京网站建设天下公司,公司怎么制作网站第二章 进程的描述与控制 文章目录 第二章 进程的描述与控制2.1 前趋图和程序执行2.1.1 前趋图2.1.2 程序顺序执行2.1.3 程序并发执行 2.2 进程的描述2.2.1 进程的定义和特征2.2.2 进程的基本状态及转换2.2.3 挂起操作和进程状态的转换2.2.4 进程管理中的数据结构 2.3 进程控制…第二章 进程的描述与控制 文章目录 第二章 进程的描述与控制2.1 前趋图和程序执行2.1.1 前趋图2.1.2 程序顺序执行2.1.3 程序并发执行 2.2 进程的描述2.2.1 进程的定义和特征2.2.2 进程的基本状态及转换2.2.3 挂起操作和进程状态的转换2.2.4 进程管理中的数据结构 2.3 进程控制2.3.1 操作系统内核2.3.2 进程的创建2.3.3 进程的终止2.3.4 进程的阻塞与唤醒2.3.5 进程的挂起与激活 2.4 进程同步2.4.1 进程同步的基本概念2.4.2 硬件同步机制2.4.3 信号量机制2.4.4 信号量的应用2.4.5 管程(Monitors)机制 2.5 经典进程的同步问题2.5.1 生产者-消费者问题Producer-Consumer Problem2.5.2 哲学家进餐问题Dining Philosophers Problem2.5.3 读者-写者问题Reader-Writer Problem2.5.4 可生产单种产品的多生产者-多消费者问题2.5.5 吸烟者问题 - 可生产多种产品的单生产者-多消费者问题 2.6 进程通信2.6.1 进程通信的类型2.6.2 消息传递通信的实现方式2.6.3 直接消息传递系统实例 2.7 线程(Threads)的基本概念2.7.1 线程的引入2.7.2 线程与进程的比较2.7.3 线程的状态和线程控制块 2.8 线程的实现2.8.1 线程的实现方式2.8.2 线程的实现2.8.3 线程的创建和终止2.8.4 线程的状态与转换 组织与控制 2.1 前趋图和程序执行
2.1.1 前趋图
前趋图(Precedence Graph)是指一个有向无循环图,可记为 DAG(DirectedAcyclic Graph)用于描述进程之间执行的先后顺序。 图中的每个结点可用来表示一个进程或程序段乃至一条语句, 结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)。 Pi - Pj 或 Pi, Pj) ∈ - 表示在Pj开始执行之前Pi必须完成。Pi是Pj的直接前趋Pj是Pi的直接后继。 把没有前趋的结点称为初始结点(Initial Node) 把没有后继的结点称为终止结点(Final Node) 每个结点还具有一个重量(Weight)用于表示该结点所含有的程序量或程序的执行时间。
2.1.2 程序顺序执行
通常一个应用程序由若干个程序段组成每一个程序段完成特定的功能它们在执行时都需要按照某种先后次序顺序执行仅当前一程序段执行完后才运行后一程序段。 程序顺序执行时的特征
顺序性:指处理机严格地按照程序所规定的顺序执行,即每一操作必须在下一个操作开始之前结束封闭性:指程序在封闭的环境下运行即程序运行时独占全机资源资源的状态(除初始状态外)只有本程序才能改变它程序一旦开始执行其执行结果不受外界因素影响可再现性:指只要程序执行时的环境和初始条件相同当程序重复执行时可获得相同的结果。
2.1.3 程序并发执行
只有在不存在前趋关系的程序之间才有可能并发执行否则无法并发执行。 程序并发执行时的特征 间断性。程序在并发执行时由于它们共享系统资源以及为完成同一项任务而相互合作致使在这些并发执行的程序之间形成了相互制约的关系。 例如I、C和P是三个相互合作的程序当计算程序完成 Ci-1 的计算后如果输入程序 Ii 尚未完成数据的输入则计算程序 Ci 就无法进行数据处理必须暂停运行。只有当使程序暂停的因素消失后(如Ii已完成数据输入)计算程序便可恢复执行。 相互制约将导致并发程序具有“执行–暂停–执行”这种间断性的活动规律。 失去封闭性。其中任一程序在运行时其环境都必然会受到其它程序的影响。 不可再现性。计算结果必将与并发程序的执行速度有关。 例如有两个循环程序A和B它们共享一个变量N。 程序A每执行一次时都要做NN1操作; 程序B每执行一次时都要执行Print(N)操作然后再将N置成“0”。 假定某时刻变量N的值为n ① NN1在 Print(N)和N0之前此时得到的N值分别为n1,n1,0。② NN1在 Print(N)和N0之后此时得到的N值分别为n,01。③ NN1在 Print(N)和N0之间此时得到的N值分别为nn10。
2.2 进程的描述
2.2.1 进程的定义和特征
定义
进程控制块(Process Control BlockPCB)系统利用 PCB 来描述进程的基本情况和活动过程进而**控制和管理进程**。
进程实体(又称进程映像)简称为进程。由程序段【程序的代码(指令序列)】、相关的数据段【运行过程中产生的各种数据(如:程序中定义的变量)】和 PCB【进程描述信息 进程控制和管理信息 资源分配清单 处理机相关信息】 三部分便构成。
PCB 是给操作系统用的程序段、数据段是给进程自己用的与进程自身的运行逻辑有关
创建进程实质上是创建进程实体中的PCB;撤消进程实质上是撤消进程实体中的PCB。
进程 进程是进程实体的运行过程。 进程是程序的一次执行。 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。 进程是具有独立功能的程序在一个数据集合上的运行过程是系统进行资源分配和调度的一个独立单位。
进程是动态的进程实体(进程映像)是静态的。
特征 动态性。由创建而产生由调度而执行由撤消而消亡。—— 进程实体有一定的生命期。 程序则只是一组有序指令的集合并存放于某种介质上其本身并不具有活动的含义因而是静态的。 程序: 是静态的。 进程(Process): 是动态的。 当进程被创建时操作系统会为该进程分配一个唯一的、不重复的“身份证号”-- PID(Process lD进程ID) 并发性。是指多个进程实体同存于内存中且能在一段时间内同时运行。而程序(没有建立PCB)是不能参与并发执行的。 独立性。在传统的OS中独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。 异步性。是指进程是按异步方式运行的即按各自独立的、不可预知的速度向前推进。
2.2.2 进程的基本状态及转换
三个基本状态
就绪(Ready)状态
就绪状态指进程已处于准备好运行的状态即进程已分配到除 CPU以外的所有必要资源后只要再获得CPU便可立即执行。
就绪队列系统中有许多处于就绪状态的进程它们按一定的策略(如优先级策略)排成的一个队列
执行(Running)状态
执行状态进程已获得 CPU其程序正在执行的状态。
对任何一个时刻而言在单处理机系统中只有一个进程处于执行状态 而在多处理机系统中则有多个进程处于执行状态。
阻塞(Block)状态
阻塞状态 / 等待状态 / 封锁状态正在执行的进程由于发生某事件(如等待某种系统资源的分配或者等待其他进程的响应等)暂时无法继续执行时的状态即进程的执行受到阻塞。此时引起进程调度OS把处理机分配给另一个就绪进程而让受阻进程处于阻塞状态。
阻塞队列将处于阻塞状态的进程排成一个队列。【根据阻塞原因的不同会设置多个阻塞队列。】
两个常见状态
创建状态
进程的创建通常包括以下步骤
申请空白 PCB操作系统为进程分配一个空白 进程控制块PCB用于存储进程的管理和控制信息。填写 PCB向 PCB 中填写进程的基本信息如进程 ID、优先级、状态、程序计数器、寄存器状态等。分配资源为该进程分配运行所需的资源如内存空间、文件描述符、设备等。转入就绪状态如果资源分配成功将进程状态设置为 就绪状态并将其插入就绪队列等待调度执行。
创建状态在资源分配过程中系统无法满足进程的资源需求例如内存不足则进程的创建无法完成的状态。【创建状态是为了确保进程的调度只能在创建工作完成后进行从而保证对 PCB 操作的完整性。】
终止状态
进程的终止可以通过以下几种方式触发【触发之后就进入终止状态进程不再执行】
自然结束进程完成其任务达到程序中的结束点如 main 函数的返回。无法克服的错误进程在执行过程中遇到致命错误如访问非法内存、除以零等无法继续运行。操作系统终止操作系统主动终止进程例如因为系统资源不足或进程违反系统规则。其他进程终止具有终止权的进程如父进程或特权进程主动终止目标进程。
进程终止通常分为两个步骤
善后处理进程不再执行但是操作系统会保留一个记录其中保存状态码和一些计时统计数据供其他进程收集。删除进程将进程的 进程控制块PCB 清零并将空白PCB归还给系统以便复用。
状态转换 NULL → 创建一个新进程产生时该进程处于创建状态创建状态 → 就绪状态当其获得了所需的资源以及对其 PCB 的初始化工作完成后由创建转变为就绪就绪状态 → 执行状态在调度程序为处于就绪状态的进程分配了处理机之后便可执行由就绪转变为执行执行状态 → 终止状态进程主动结束或被动结束无法克服的错误操作系统/其他进程终止由执行转变为终止执行状态 → 就绪状态正在执行的进程(当前进程)因分配的时间片已用完而被剥夺处理机暂停执行时由执行转为就绪执行状态 → 阻塞状态正在执行的进程由于发生某事件暂时无法继续执行时由执行状态转变为阻塞状态。阻塞状态 → 就绪状态阻塞的进程所等待的事件已经发生即进程已分配到除 CPU以外的所有必要资源由阻塞转变为就绪 进程的组织链式方式 和 索引方式 2.2.3 挂起操作和进程状态的转换
挂起(Suspend)操作当该操作作用于某个进程时该进程将被挂起意味着此时该进程处于静止状态。
如果进程正在执行它将暂停执行。如果进程正在就绪则该进程此时暂不接受调度。与挂起操作对应的操作是激活(Active)操作。
引入挂起操作的原因
终端用户的需要。终端用户在自己的程序运行期间可以暂停自己的程序的运行以便研究其执行情况或对程序进行修改。父进程请求。父进程希望挂起自己的某个子进程以便考查和修改该子进程或者协调各子进程间的活动。负荷调节的需要。当实时系统中的工作负荷较重已可能影响到对实时任务的控制时可由系统把一些不重要的进程挂起以保证系统能正常运行。操作系统的需要。操作系统有时希望挂起某些进程以便检查运行中的资源使用情况或进行记账。
状态转换进阶版
当进程处于未被挂起的就绪状态时称此为活动就绪状态 —— 可以接收调度该进程表示为 Readya。
当进程处于已被 Suspend挂起的就绪状态时称此为静止就绪状态 —— 不可以被调度该进程表示为 Readys。
当进程处于未被挂起的阻塞状态时称它此为活动阻塞状态 —— 该进程表示为 Blockeda。
当进程处于已被 Suspend挂起的阻塞状态时称此为静止阻塞状态—— 该进程表示为 Blockeds。 创建状态 → 活动就绪状态在当前系统性能和内存容量均允许的情况下已完成对进程创建的必要操作由创建转变为活动就绪。创建状态 → 静止就绪状态考虑到系统当前资源状况和性能的要求不分配给新建进程所需资源【主要是主存】而被安置在外存不参与调度此时进程创建工作尚未完成由创建转变为静止就绪。活动就绪 → 静止就绪。活动就绪的进程被Suspend挂起由活动就绪转变为静止就绪。静止就绪 → 活动就绪。处于静止就绪状态的进程被激活原语 Active 激活后由静止就绪转变为活动就绪。活动阻塞 → 静止阻塞。活动阻塞的进程被Suspend挂起由活动阻塞转变为静止阻塞。静止阻塞 → 活动阻塞。处于静止阻塞状态的进程被激活原语 Active 激活后由静止阻塞转变为活动阻塞。静止阻塞 → 静止就绪。处于静止阻塞状态的进程在其所期待的事件出现后由静止阻塞变为静止就绪。活动阻塞 → 活动就绪。处于活动阻塞状态的进程在其所期待的事件出现后由活动阻塞变为活动就绪。
2.2.4 进程管理中的数据结构
操作系统中用于管理控制的数据结构
资源信息表或进程信息表在计算机系统中对于每个资源和每个进程都设置了一个数据结构其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针可以将同类资源或进程的信息表或者同一进程所占用的资源信息表分类链接成不同的队列便于操作系统进行查找。
一般分为以下四类:内存表、设备表、文件表 和 用于进程管理的进程表进程控制块 PCB
进程控制块 PCB(Process Control Block)
系统是通过 PCB感知进程的存在的。PCB已成为进程存在于系统中的唯一标志。【当系统创建一个新进程时就为它建立了一个PCB。进程结束时又回收其PCB进程于是也随之消亡。】用于描述进程的当前情况以及管理进程运行的全部信息。
PCB 的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位一个能与其他进程并发执行的进程。PCB作用的具体阐述:
作为独立运行基本单位的标志。当一个程序(含数据)配置了 PCB 后就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位也具有取得 OS服务的权利。能实现间断性运行方式。 当进程因阻塞而暂停运行时它必须保留自己运行时的CPU现场信息再次被调度运行时还需要恢复其 CPU 现场信息。在有了PCB 后系统就可将 CPU 现场信息保存在被中断进程的 PCB 中供该进程再次被调度执行时恢复 CPU 现场时使用。 提供进程管理所需要的信息。 调度程序调度到某进程运行时只能根据该进程PCB中记录的程序和数据在内存或外存中的始址指针找到相应的程序和数据;在进程运行过程中当需要访问文件系统中的文件或 I/O 设备时也都需要借助于 PCB 中的信息。可根据 PCB中的资源清单了解到该进程所需的全部资源等。 提供进程调度所需要的信息。 在 PCB中就提供了进程处于何种状态的信息。其他信息如进程的优先级、进程的等待时间和已执行的时间等。 实现与其它进程的同步与通信。 进程同步机制是用于实现诸进程的协调运行的在采用信号量机制时它要求在每个进程中都设置有相应的用于同步的信号量。在PCB中还具有用于实现进程通信的区域或通信队列指针等。
进程控制块中的信息
进程标识符进程标识符用于唯一地标识一个进程。PID 外部标识符。为了方便用户(进程)对进程的访问。它是由创建者提供的通常由字母、数字组成。内部标识符。为了方便系统对进程的使用每一个进程拥有一个唯一的数字标识符通常是一个进程的序号。 处理机状态 - 处理机的上下文主要是由处理机的各种寄存器中的内容组成的 ①通用寄存器又称为用户可视寄存器用户程序可以访问的用于暂存信息②指令计数器其中存放了要访问的下一条指令的地址③ 程序状态字 PSW其中含有状态信息如条件码、执行方式、中断屏蔽标志等④ 用户栈指针指每个用户进程都有一个或若干个与之相关的系统栈用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。 进程调度信息 ①进程状态指明进程的当前状态②进程优先级是用于描述进程使用处理机的优先级别的一个整数优先级高的进程应优先获得处理机③进程调度所需的其它信息与所采用的进程调度算法有关比如进程已等待CPU的时间总和、进程已执行的时间总和等④事件是指进程由执行状态转变为阻塞状态所等待发生的事件即阻塞原因。 进程控制信息 - 用于进程控制所必须的信息 ①程序和数据的地址进程实体中的程序和数据的内存或外存地(首)址②进程同步和通信机制实现进程同步和进程通信时必需的机制如消息队列指针、信号量等③资源清单在该清单中列出了进程在运行期间所需的全部资源(除CPU 以外), 另外还有一张已分配到该进程的资源的清单④链接指针本进程(PCB)所在队列中的下一个进程的 PCB 的首地址。
PCB组织方式 线性方式即将系统中所有的PCB都组织在一张线性表中将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小但每次查找时都需要扫描整张表因此适合进程数目不多的系统。链接方式即把具有相同状态进程的 PCB 分别通过 PCB 中的链接字链接成一个队列。可以形成就绪队列、若干个阻塞队列和空白队列等。 就绪队列往往按进程的优先级将PCB从高到低进行排列将优先级高的进程PCB排在队列的前面。阻塞队列阻塞状态进程的 PCB 根据其阻塞原因的不同排成多个。 索引方式即系统根据所有进程状态的不同建立几张索引表。把各索引表在内存的首地址记录在内存的一些专用单元中在每个索引表的表目中记录具有相应状态的某个 PCB 在 PCB 表中的地址。
2.3 进程控制
进程控制就是要实现进程状态转换
2.3.1 操作系统内核
OS内核功能模块安排在紧靠硬件的软件层次中且常驻内存【一般将OS划分为若干层次,再将OS的不同功能分别设置在不同的层次中】
与硬件紧密相关的模块(如中断处理程序等)各种常用设备的驱动程序运行频率较高的模块(如时钟管理、进程调度和许多模块所公用的一些基本操作)
如此安排目的
便于对这些软件进行保护防止遭受其他应用程序的破坏可以提高 OS 的运行效率。
处理机的执行状态分类: 【将应用程序与 操作系统内核 隔离防止 OS本身及关键数据(如PCB等)遭受到应用程序有意或无意的破坏。】
① 系统态: 又称为管态也称为内核态。它具有较高的特权能执行一切指令访问所有寄存器和存储区传统的OS都在系统态运行。② 用户态: 又称为目态。具有较低特权的执行状态仅能执行规定的指令访问指定的寄存器和存储区。一般情况下应用程序只能在用户态运行不能去执行 OS 指令及访问 OS区域就可以防止应用程序对OS的破坏。 系统态与内核的关系 系统态是内核的执行环境 当 CPU 运行在系统态时操作系统内核可以访问和控制所有硬件资源执行所有指令包括特权指令。内核代码运行在系统态负责管理整个系统的运行。 内核是系统态的主体 操作系统内核是唯一能够在系统态下运行的软件组件。用户程序无法直接运行在系统态必须通过内核提供的接口如系统调用请求服务。 用户态与应用程序的关系 用户态是应用程序的执行环境 当 CPU 运行在用户态时应用程序只能执行非特权指令无法直接访问硬件资源或执行特权操作。应用程序代码运行在用户态依赖于操作系统提供的服务。 应用程序是用户态的主体 应用程序是运行在用户态的主要软件组件。操作系统内核无法直接运行在用户态但提供了接口如系统调用、库函数供应用程序访问系统资源和服务。 OS内核包含的两个功能 支撑功能 中断处理 各种类型的系统调用键盘命令的输入进程调度设备驱动等 时钟管理 在时间片轮转调度中每当时间片用完时便由时钟管理产生一个中断信号促使调度程序重新进行调度在实时系统中的截止时间控制批处理系统中的最长运行时间控制等 原语操作 原语(Primitive)就是由若干条指令组成的用于完成一定功能的一个过程。是“原子操作”。原语在执行过程中不允许被中断。 原子操作(Action Operation)一个操作中的所有动作是一个不可分割的基本单位要么全做要么全不做。原子操作在系统态下执行常驻内存。 原子性实现 用“关中断指令”和“开中断指令”这两个特权指令实现原子性 正常情况每执行完一条指令就需要判断是否有外部中断信号 原子性实现CPU执行了关中断指令之后就不再例行检查中断信号直到执行开中断指令之后才会恢复检查。即关中断、开中断 之间的这些指令序列就是不可被中断的这就实现了“原子性”。 资源管理功能 进程管理。 由于各个功能模块的运行频率较高进程的调度与分派、进程的创建与撤消等由于被多种功能模块所需要用于实现进程同步的原语、常用的进程通信原语等 存储器管理。 用于实现将用户空间的逻辑地址变换为内存空间的物理地址的地址转换机构内存分配与回收的功能模块实现内存保护和对换功能的模块等。 设备管理。由于设备管理与硬件(设备)紧密相关因此其中很大部分也都设置在内核中 各类设备的驱动程序用于缓和CPU与I/O速度不匹配矛盾的缓冲管理用于实现设备分配和设备独立性功能的模块等
2.3.2 进程的创建
进程的层次结构 UNIX 父进程(Parent Process)创建进程的进程 子进程(Progeny Process)被创建的进程 孙进程子进程继续创建的进程 进程家族(组)进程与其子孙进程共同组成的 在PCB中设置了家族关系表项【标识进程之间的家族关系】标明自己的父进程及所有的子进程。 子进程可以继承父进程所拥有的资源。进程不能拒绝其子进程的继承权。当子进程被撤消时应将其从父进程那里获得的资源归还给父进程。在撤消父进程时也必须同时撤消其所有的子进程。 Windows不存在任何进程层次结构的概念所有的进程都具有相同的地位。 进程之间的关系不是层次关系而是获得句柄与否、控制与被控制的简单关系 一个进程创建另外的进程时创建进程获得了一个句柄其作用相当于一个令牌可以用来控制被创建的进程。这个句柄是可以进行传递的获得了句柄的进程就拥有控制对应进程的权力。
进程图Process Graph用于描述进程之间关系的一棵有向树
结点代表进程有向边代表进程之间的父子关系树的根节点进程家族的祖先Ancestor
例子在进程Pi 创建了进程Pj之后,称Pi是Pj的父进程Pj是Pi的子进程。
触发进程创建(Creation of Process)的事件: 系统内核为用户创建一个新进程: 用户登录。在分时系统中用户在终端键入登录命令后若登录成功系统将为该用户建立一个进程并把它插入就绪队列中。 作业调度。在多道批处理系统中当作业调度程序按一定的算法调度到某个(些)作业时便将它(们)装入内存为它(们)创建进程并把它(们)插入就绪队列中。 提供服务。当运行中的用户程序提出某种请求后系统将专门创建一个进程来提供用户所需要的服务 由用户进程自己创建新进程 应用请求。使新进程以和其创建者进程并发运行的方式完成特定任务
进程创建过程
系统中在出现了创建新进程的请求后OS就调用进程创建原语 Creat创建一个新进程:
申请空白PC。为新进程申请获得唯一的数字标识符并从PCB 集合中索取一个空白 PCB。为新进程分配其运行所需的资源包括各种物理和逻辑资源。这些资源或从操作系统或仅从其父进程获得。 例如为新进程的程序和数据以及用户栈分配必要的内存空间时操作系统必须知道新进程所需内存的大小: 批处理作业其大小可在用户提出创建进程要求时提供;应用进程创建子进程也应是在该进程提出创建进程的请求中给出所需内存的大小;交互型作业用户可以不给出内存要求而由系统分配一定的空间如果新进程要共享某个已在内存的地址空间(即已装入内存的共享段)则必须建立相应的链接。 初始化进程控制块(PCB)。PCB的初始化包括: 初始化标识信息将系统分配的标识符和父进程标识符填入新PCB中;初始化处理机状态信息使程序计数器指向程序的入口地址使栈指针指向栈顶;初始化处理机控制信息将进程的状态设置为就绪状态或静止就绪状态 对于优先级通常是将它设置为最低优先级除非用户以显式方式提出高优先级要求。 如果进程就绪队列能够接纳新进程便将新进程插入就绪队列。
2.3.3 进程的终止
触发进程终止(Termination of Process)的事件
正常结束表示进程的任务已经完成准备退出运行。 在批处理系统中, 可利用Holt指令。在分时系统中可利用Logs off指令。 异常结束是指进程在运行时发生了某种异常事件使程序无法继续运行。常见的异常事件有: 越界错这是指程序所访问的存储区已越出该进程的区域;保护错指进程试图去访问一个不允许访问的资源或文件或者以不适当的方式进行访问例如进程试图去写一个只读文件非法指令指程序试图去执行一条不存在的指令。出现该错误的原因可能是程序错误地转移到数据区把数据当成了指令特权指令错指用户进程试图去执行一条只允许 OS执行的指令运行超时指进程的执行时间超过了指定的最大值;等待超时指进程等待某事件的时间超过了规定的最大值;算术运算错指进程试图去执行一个被禁止的运算例如被0除I/O 故障这是指在 I/O过程中发生了错误等。 外界干预是指进程应外界的请求而终止运行。这些干预有: 操作员或操作系统干预指如果系统中发生了某事件例如发生了系统死锁进程请求指当子进程已完成父进程所要求的任务时父进程可以提出请求结束该子进程;因父进程终止指当父进程终止时它的所有子进程也都应当结束。因此OS在终止父进程的同时也将它的所有子孙进程终止
进程终止过程
根据被终止进程的标识符从PCB集合中检索出该进程的PCB从中读出该进程的状态;若被终止进程正处于执行状态应立即终止该进程的执行(立即剥夺CPU将CPU分配给其他进程)并置调度标志为真用于指示该进程被终止后应重新进行调度;若该进程还有子孙进程还应将其所有子孙进程也都予以终止以防它们成为不可控的进程;将被终止进程所拥有的全部资源或者归还给其父进程或者归还给系统;将被终止进程(PCB)从所在队列(或链表)中移出等待其它程序来搜集信息。
2.3.4 进程的阻塞与唤醒
触发进程的阻塞与唤醒的事件 向系统请求共享资源失败。进程在向系统请求共享资源时由于系统已无足够的资源分配给它此时进程因不能继续运行而转变为阻塞状态。 例如一进程请求使用打印机由于系统已将打印机分配给其它进程已无可以再可分配的打印机这时请求者进程只能被阻塞仅在其它进程释放出打印机时请求进程才被唤醒。 等待某种操作的完成。当进程启动某种操作后如果该进程必须在该操作完成之后才能继续执行则应先将该进程阻塞起来以等待操作完成。 例如进程启动了某 I/O设备如果只有在 I/O 设备完成了指定的 I/O 操作任务后进程才能继续执行则该进程在启动了 I/O设备后便应自动进入阻塞状态去等待。在I/O操作完成后再由中断处理程序将该进程唤醒。 新数据尚未到达。对于相互合作的进程如果一个进程需要先获得另一进程提供的数据后才能对该数据进行处理只要其所需数据尚未到达进程便只有阻塞。 例如有两个进程进程 A用于输入数据进程B对输入数据进行加工。假如A尚未将数据输入完毕则进程 B将因没有所需处理的数据而阻塞;一旦进程A把数据输入完毕便可去唤醒进程 B。 等待新任务的到达。在某些系统中(特别是在网络环境下的OS)往往设置一些特定的系统进程每当这种进程完成任务后便把自己阻塞起来等待新任务的到来。 例如在网络环境中的发送进程其主要任务是发送数据包若已有的数据包已全部发送完成而又无新的数据包发送这时发送进程将把自己阻塞起来;仅当有新的数据包到达时才将发送进程唤醒。
进程阻塞过程 正在执行的进程如果发生了触发阻塞事件进程便通过调用阻塞原语block将自己阻塞。【阻塞是进程自身的一种主动行为。】 进入block过程后由于该进程还处于执行状态所以应先立即停止执行把进程控制块中的现行状态由“执行”改为“阻塞”并将 PCB插入阻塞队列。【如果系统中设置了因不同事件而阻塞的多个阻塞队列则应将本进程插入到具有相同事件的阻塞队列。】 进程上下文切换Context Switching- 运行环境信息保留被阻塞进程的处理机状态按新进程的PCB中的处理机状态设置CPU 的环境。 保存被阻塞进程的处理机状态操作系统保存该进程的 执行上下文包括程序计数器PC、寄存器状态、程序状态字PSW等关键信息并将其存储到该进程的 进程控制块PCB中以便后续恢复执行。加载新进程的 PCB 设置 CPU 环境操作系统从就绪队列中选择一个进程进行调度并将其 PCB 中存储的上下文信息如程序计数器、寄存器值等加载到 CPU 中从而为这个新调度的进程设置执行环境使其能够继续或开始执行。 步骤 找到要阻塞的进程对应的PCB保护进程运行现场将PCB状态信息设置为“阻塞态暂时停止进程运行将PCB插入相应事件的等待队列
进程唤醒过程
当被阻塞进程所期待的事件发生时由有关进程(比如提供数据的进程)调用唤醒原语wakeup将等待该事件的进程唤醒
首先把被阻塞的进程从等待该事件的阻塞队列中找到并移出将其PCB中的现行状态由阻塞改为就绪再将该PCB插入到就绪队列中等待被调度。
block 原语和wakeup 原语是一对作用刚好相反的原语。在使用它们时必须成对使用。
2.3.5 进程的挂起与激活
进程挂起过程
OS将利用挂起原语suspend 将指定进程或处于阻塞状态的进程挂起
首先检查被挂起进程的状态 处于活动就绪状态的进程将其改为静止就绪处于活动阻塞状态的进程将其改为静止阻塞; 然后为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后若被挂起的进程正在执行则转向调度程序从就绪队列中选择另一个合适的进程开始执行
进程激活过程
OS将利用激活原语active将指定进程激活。
激活原语先将进程从外存调入内存检查该进程的现行状态 若是静止就绪便将之改为活动就绪;若为静止阻塞便将之改为活动阻塞。 假如采用的是抢占调度策略则每当有静止就绪进程被激活而插入就绪队列时将由调度程序将被激活的进程与当前进程两者的优先级进行比较 如果被激活进程的优先级低就不必重新调度;如果被激活进程的优先级高就需要立即剥夺当前进程的运行把处理机分配给刚刚被激活的进程。
2.4 进程同步
2.4.1 进程同步的基本概念 进程同步机制的主要任务是对多个相关进程在执行次序上进行协调使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源并能很好地相互合作从而使程序的执行具有可再现性。 【多个相互关联的进程同时运行时需要对它们的执行顺序进行安排和管理让它们按照一定的规矩或时间顺序来使用系统的资源比如内存、CPU、缓冲区等并能够很好地配合工作。这样一来不管程序运行多少次结果都能保持一致不会出现混乱或者错误。】 1. 两种形式的制约关系
间接相互制约关系 - 临界资源的互斥访问
定义多个并发执行的程序因**共享系统资源如CPU、打印机、磁带机等**而产生的相互制约关系。特点 需要对临界资源进行互斥访问即同一时间只能有一个进程使用。资源的分配由系统统一管理进程需先申请资源不能直接使用。
直接相互制约关系 - 进程间的协作与同步
定义某些应用程序创建多个进程这些**进程为完成同一任务而合作因共享特定资源如缓冲区**而产生的相互制约关系。特点 进程间存在协作关系如输入进程A向计算进程B提供数据。当共享资源如缓冲区为空或满时进程会被阻塞等待对方唤醒。
进程的异步性
定义进程在运行过程中是否能获得CPU以及运行速度无法由自身控制受系统调度和制约关系影响。问题 可能导致对共享变量或数据结构的访问顺序错误。引发与时间相关的错误导致进程每次执行结果不一致。 解决方法 使用进程同步机制如信号量、互斥锁协调进程执行顺序。确保进程对资源的访问有序进行。
2. 临界资源(Critical Resouce)
生产者-消费者(producer-consumer) 问题 生产者进程与消费者进程能并发执行在两者之间设置了一个具有n个缓冲区的缓冲池生产者进程将其所生产的产品放入一个缓冲区中消费者进程可从一个缓冲区中取走产品去消费。 所有的生产者进程和消费者进程都是以异步方式运行的但它们之间必须保持同步既不允许消费者进程到一个空缓冲区去取产品也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。 一个数组 buffer来表示上述的具有n个缓冲区的缓冲池 - 循环缓冲。一个整型变量 counter其初始值为 0
生产者每投入一个产品时, 缓冲池 buffer 中暂存产品的数组单元指针 in加1【in(in1)%n - 循环缓冲】counter 加1。
消费者每取出一个产品时, 缓冲池 buffer 中已取走产品的空闲单元的数组单元指针 out加1【out(out1)%n - 循环缓冲】counter 减1。
当(in1)%nout 时表示缓冲池满而inout 则表示缓冲池空。
生产者和消费者两进程共享下面的变量:
int in0, out0, count0;
item buffer[n];生产者
void producer() {//在生产者进程中使用一局部变量nextp用于暂时存放每次刚刚生产出来的产品;while(1){produce an item in nextp;...while (countern);buffer [in] nextp;in (in1) % n;counter;}
};消费者
void consumer()
{//在消费者进程中则使用一个局部变量 nextc,用于存放每次要消费的产品。while(1){while (counter0);nextcbuffer[out];out (out1)% n;counter--;consumer the item in nextc;}
};生产者程序和消费者程序在分别看时都是正确的而且两者在顺序执行时其结果也会是正确的但若并发执行时就会出现差错问题就在于这两个进程共享变量counter。 用机器语言实现时形式描述 生产者 register1counter
register1register11;
counterregister1;消费者 register2counter
register2register2-1;
counterregister2;假设:counter的当前值是5。 存在情况一 register1counter(register15)
register1register11; (register16)
counterregister1; (counter6)
register2counter(register26)
register2register2-1; (register25)
counterregister2; (counter5)存在情况二 register1counter(register15)
register1register11; (register16)
register2counter(register25)
register2register2-1; (register24)
counterregister1; (counter6)
counterregister2; (counter4)解决此问题的关键是应把变量counter 作为临界资源处理令生产者进程和消费者进程互斥地访问变量counter。 3. 临界区(critical section)
临界区(critical section)在每个进程中访问临界资源的那段代码
进入区(entry section)在临界区前面增加一段用于进行检查的代码 检查欲访问的临界资源是否正被访问 如果此刻临界资源未被访问进程便可进入临界区对该资源进行访问并设置它正被访问的标志 如果此刻该临界资源正被某进程访问则本进程不能进入临界区。
退出区(exit section)将临界区正被访问的标志恢复为未被访问的标志在临界区后面加上的一段代码
剩余区除上述进入区、临界区及退出区之外的其它部分的代码
4.同步机制应遵循的规则
实现进程互斥地进入自己的临界区可用软件方法更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述准则:
空闲让进。当无进程处于临界区时表明临界资源处于空闲状态应允许一个请求进入临界区的进程立即进入临界区可有效地利用临界资源。忙则等待。当已有进程进入临界区时表明临界资源正在被访问因而其它试图进入临界区的进程必须等待以保证对临界资源的互斥访问。有限等待。对要求访问临界资源的进程应保证在有限时间内能进入自己的临界区以免陷入“死等”状态。让权等待。当进程不能进入自己的临界区时应立即释放处理机以免进程陷入“忙等”状态。
2.4.2 硬件同步机制
在对临界区进行管理时可以将标志看做一个锁。
初始时锁是打开的。每个要进入临界区的进程必须先对锁进行测试 当锁是未打开的时候则必须等待直至锁被打开。当锁是打开的时候则应立即把其锁上以阻止其它进程进入临界区。
为防止多个进程同时测试到锁为打开的情况测试和关锁操作必须是连续的不允许分开进行。
1. 关中断
关中断是为了在临界区代码执行期间不会被中断打断从而确保临界区代码的原子性。关中断的具体作用包括
避免进程切换中断可能导致进程切换如时钟中断触发调度关中断可以防止这种情况。防止其他中断干扰硬件中断如磁盘IO完成可能影响临界区代码的执行关中断可以屏蔽这些中断。
关中断的时机在进入锁测试之前关闭中断直到完成锁测试并上锁之后才能打开中断。
关中断的缺点:
滥用关中断权力可能导致严重后果关中断时间过长会影响系统效率限制了处理器交叉执行程序的能力关中断方法也不适用于多CPU 系统因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。
2. 利用 Test-and-Set 指令实现互斥
借助一条硬件指令“测试并建立”指令 TS(Test-and-Set)该指令是一条原语。
为每个临界资源设置一个全局的布尔变量lock——代表该资源的状态可把它看成一把锁
lock初值为FALSE表示该临界资源空闲。进程在进入临界区之前先用TS指令测试lock 如果其值为 FALSE则表示没有进程在临界区内可以进入。并将lock赋值 TRUE关闭了临界资源使任何进程都不能进入临界区如果其值为 TRUE则表示该资源正在被使用。
伪代码
bool lock false; // 全局锁变量bool TestAndSet(bool *lock) {bool original_value *lock; // 1. 测试 lock 的原始值*lock true; // 2. 设置 lock 为 truereturn original_value; // 3. 返回原始值
}void enter_critical_section() {while (TestAndSet(lock)) { // 忙等待// 如果 lock 为 true等待}// 进入临界区
}void leave_critical_section() {lock false; // 释放锁
}
3. 利用 Swap 指令实现进程互斥
Swap指令称为对换指令在Intel 80x86 中又称为XCHG指令。
为每个临界资源设置一个全局的布尔变量lock用于表示临界区是否被占用。初始时为 FALSE表示临界区空闲。每个进程在进入临界区前使用 Swap 指令将局部布尔变量key key TRUE与 lock 交换。根据交换后的 lock 值判断能否进入临界区。 如果交换后 lock FALSE说明临界区空闲进程可以进入。如果交换后 lock TRUE说明临界区已被占用进程需要等待。
伪代码
bool lock false; // 全局锁变量void Swap(bool *a, bool *b) {bool temp *a;*a *b;*b temp;
}void enter_critical_section() {bool key true; // 局部变量do {Swap(key, lock); // 原子交换 key 和 lock 的值} while (key true); // 如果 key 为 true忙等待// 进入临界区
}void leave_critical_section() {lock false; // 释放锁
}
2.4.3 信号量机制
信号量其实就是一个变量(可以是一个整数,也可以是更复杂的记录型变量)可以用一个信号量来表示系统中某种资源的数量比如:系统中只有一台打印机就可以设置一个初值为1的信号量
1. 整型信号量 —— P、V操作
整型信号量一个用于表示资源数目的整型量S(整数)。除初始化外仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问。
P 操作荷兰语 Proberen意为“测试”在英文中常被称为 wait
wait(S) {while (S 0) {// 阻塞或忙等待}S--; // 申请资源信号量减 1
}V 操作荷兰语 Verhogen意为“增加”在英文中常被称为 signal。
signal(S) {S; // 释放资源信号量加 1// 唤醒等待该资源的进程
}wait(S)和 signal(S)是两个原子操作即它们在执行时是不可中断的。【在一个进程对信号量进行操作的过程中其他进程不能同时对该信号量进行任何操作。】 存在的问题:不满足“让权等待”原则会发生“忙等” 忙等Busy Waiting线程/进程在等待某个条件如锁、资源、信号量时持续占用 CPU 资源通过循环反复检查条件是否满足 让权等待Yield Waiting / Blocking Wait线程/进程在等待时主动释放 CPU进入阻塞状态如睡眠、挂起让其他线程/进程运行直到条件满足后再被唤醒。 2. 记录型信号量
整型信号量在整型信号量机制中的wait 操作只要是信号量S≤0就会不断地测试。使进程处于“忙等”的状态。
记录型信号量采取了“让权等待”策略
增加一个用于代表资源数目的整型变量 value还增加一个进程链表指针 list队列用于存放因信号量不可用而被阻塞的进程。
typedef struct {int value, //资源数目struct process_control block *list; //链接等待的进程
}semaphore;S-value 的初值表示系统中某类资源的数目因而又称为资源信号量
对它的每次 wait 操作表示进程请求一个单位的该类资源使系统中可供分配的该类资源数减少一个因此描述为S-value–;对它的每次 signal 操作表示执行进程释放一个单位资源使系统中可供分配的该类资源数增加一个因此描述为S-value。
【“让权等待”准则】
当 S-value 0时表示该类资源已分配完毕因此进程应调用 block 原语进行自我阻塞放弃处理机并插入到信号量链表S-list 中。此时 S-value 的绝对值表示在该信号量链表中已阻塞进程的数目。
若signal 操作加1后仍是S- value ≤ 0则表示在该信号量链表中仍有等待该资源的进程被阻塞还应调用wakeup 原语将S-list 链表中的第一个等待进程唤醒。
如果S-value 的初值为1表示只允许一个进程访问临界资源此时的信号量转化为互斥信号量用于进程互斥。
// 定义信号量的 wait 操作
void wait(semaphore *S) {// 将信号量的值减 1表示占用一个资源S-value--; // 如果信号量的值小于 0表示没有可用资源if (S-value 0) { // 将当前进程阻塞并将其加入到信号量的等待队列中 - block 原语进行自我阻塞(进程从运行态→阻塞态)主动放弃处理机block(S-list); }
}// 定义信号量的 signal 操作
void signal(semaphore *S) {// 将信号量的值加 1表示释放一个资源S-value; // 如果信号量的值小于等于 0表示有进程在等待资源if (S-value 0) { // 从信号量的等待队列中唤醒一个进程 - wakeup 原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)wakeup(S-list); }
}若考试中出现 P(S)、V(S)的操作除非特别说明否则默认s为记录型信号量。 3. AND型信号量
一个进程往往需要获得多个共享资源后方能执行其任务
AND同步机制的基本思想是: 将进程在整个运行过程中需要的所有资源一次性全部地分配给进程待进程使用完后再一起释放。【对若干个临界资源的分配采取原子操作方式:要么把它所请求的资源全部分配到进程要么一个也不分配。】从而避免了死锁情况的发生。 死锁 两个进程A和B它们都要求访问共享数据临界资源D和E为这两个数据分别设置用于互斥的信号量 Dmutex 和 Emutex并令它们的初值都是1。相应地在两个进程中都要包含两个对Dmutex和Emutex的操作 process A: wait(Dmutex);
wait(Emutex);process B: wait(Emutex);
wait(Dmutex);若进程A和B按下述次序交替执行wait操作: process A:wait(Dmutex); 于是Dmutex0
process B:wait(Emutex); 于是Emutex0
process A: wait(Emutex); 于是Emutex-1A阻塞
process B:wait(Dmutex); 于是Dmutex-1 B阻塞最后进程A和B就将处于僵持状态。在无外力作用下两者都将无法从僵持状态中解脱出来。此时的进程A和B已进入死锁状态 Swait(S1, S2, ..., Sn)
{while (TRUE){if (S1 1 S2 1 ... Sn 1){// 所有资源都可用分配资源for(i 1; i n; i) Si--;break; // 退出循环任务继续执行}else{// 有资源不可用阻塞任务// 将任务加入等待队列并释放 CPUblock();}}
}Ssignal(S1, S2, ..., Sn)
{for(i 1; i n; i){Si; // 释放资源}// 唤醒等待这些资源的所有任务wakeup_all();
}4. 信号量集
信号量集核心思想当进程申请某类临界资源时在每次分配之前都必须测试资源的数量判断是否大于可分配的下限值决定是否予以分配。 信号量Si的资源分配下限 ti ; 进程对该资源的需求值为di即表示资源占用量 记录型信号量机制每次只能对某类临界资源进行一个单位的申请或释放。分配下限ti 1 需求值为di 1进行SiSi - 1操作。 信号量集资源分配下限ti要求Si ≥ ti否则不予分配。进程对该资源的需求值为di进行SiSi - di操作。 信号量对应的Swait 和 Ssignal 格式为: Swait(Si, ti, di, …, Sn, tn, dn); Ssignal(Si, di, …, Sn, dn);
一般“信号量集”还有下面几种特殊情况:
Swait(S,d,d)。此时在信号量集中只有一个信号量S但允许它每次申请d个资源, 当现有资源数少于d时不予分配。Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S 1 时)。Swait(S,1,0)。当S≥1时允许多个进程进入某特定区当S0后将阻止任何进程进入特定区。
2.4.4 信号量的应用
利用信号量实现进程互斥 - 互斥问题信号量初值为1
互斥信号量mutex - 进入临界区的名额设其初始值为1。取值范围为(-1,0,1)。
当mutex1时表示两个进程皆未进入需要互斥的临界区;当mutex0时,表示有一个进程进入临界区运行,另外一个必须等待挂入阻塞队列;当mutex-1时表示有一个进程正在临界区运行另外一个进程因等待而阻塞在信号量队列中需要被当前已在临界区运行的进程退出时唤醒。
注意wait(mutex)和signal(mutex)必须成对地出现
缺少wait(mutex)将会导致系统混乱不能保证对临界资源的互斥访问缺少signal(mutex)将会使临界资源永远不被释放从而使因等待该资源而阻塞的进程不能被唤醒
注意对不同的临界资源需要设置不同的互斥信号量。
利用信号量实现前趋关系 - 本质是多级同步问题信号量初值为0
设有两个并发执行的进程P1和P2。P1中有语句S1;P2中有语句S2。希望在S1执行后再执行S2。为实现这种前趋关系只需使进程P1和 P2共享一个公用信号量S并赋予其初值为0将 signal(S)操作放在语句S1后面而在S2语句前面插入 wait(S)操作即
在进程P1中用S1; signal(S);在进程P2中wait(S); 用 S2;
由于S被初始化为0,这样,若P2先执行必定阻塞,只有在进程P1执行完S1;signal(S); 操作后使S增为1时P2进程方能成功执行语句S2。 S1→S2S1→S3 的前趋关系, 应分别设置信号量a和bS2→S4S2→S5S3→S6S4→S6和S5→S6设置信号量cdefg。 p1() { S1; signal(a); signal(b);}
p2() { wait(a); S2; signal(c); signal(d); }
p3() { wait(b); S3; signal(e);}
p4() { wait(c); S4; signal(f);}
p5() { wait(d); S5; signal(g);}
p6() { wait(e); wait(f); wait(g); S6;}在“前操作”之后执行 V(S)在“后操作”之前执行 P(S)
2.4.5 管程(Monitors)机制
1. 管程
管程定义 代表共享资源的数据结构 以及 由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块
【将某个资源的所有信息数据结构以及对资源的操作比如读、写、修改等都打包在一起并且提供了统一的访问方式。】
管程由四部分组成:
管程的组成部分类的组成部分详细描述①管程的名称类名标识这个管程是做什么的②局部于管程的共享数据结构说明属性变量管程内部的共享变量类似于类的属性用来描述管程管理的资源状态。③对数据结构进行操作的一组过程方法管程提供的操作接口类似于类的方法/函数用来对共享资源进行操作。④对共享数据设置初始值的语句构造函数或初始化块管程创建时对共享数据进行初始化类似于类的构造函数或初始化块。
管程的基本特征:
局部于管程的数据只能被局部于管程的过程所访问一个进程只有通过调用管程内的过程(管程提供的特定入口)才能进入管程访问共享数据 - 通过管程的过程间接修改管程的数据结构每次仅允许一个进程在管程内执行某个内部过程。- 互斥特性是由编译器负责实现
管程主要有以下特性:
模块化即管程是一个基本程序单位可以单独编译;抽象数据类型指管程中不仅有数据而且有对数据的操作;信息掩蔽指管程中的数据结构只能被管程中的过程访问这些过程也是在管程内部定义的供管程外的进程调用而管程中的数据结构以及过程(函数)的具体实现外部不可见。 封装 管程将共享资源的数据结构及其操作逻辑封装在内部外部只能通过管程提供的接口间接访问资源。这种机制隐藏了实现细节实现了资源的集中管理和安全性。 互斥访问 管程通过同步机制确保同一时间只有一个进程进入管程并操作资源。如果有多个进程想操作资源管程会让他们排队。进程请求访问时管程检查资源状态若资源被占用则进程等待若资源空闲则进程进入。这避免了竞争条件保证了资源的互斥访问。 管程和进程不同:
区别点进程管程数据结构定义私有数据结构如 PCB定义公共数据结构如消息队列操作方式通过顺序程序执行操作数据结构主要进行同步操作和初始化操作数据结构目的实现系统的并发性解决共享资源的互斥使用问题工作方式主动工作方式通过调用管程中的过程操作共享数据结构被动工作方式由进程调用其内部过程并发性进程之间能并发执行管程不能与其调用者并发生命周期动态性由创建而诞生由撤销而消亡静态性作为操作系统的资源管理模块供进程调用
2. 条件变量
条件变量主要用于处理在管程内被阻塞或挂起的进程。一个进程被阻塞或挂起的条件(原因)可有多个因此在管程中设置了多个条件变量对这些条件变量的访问只能在管程中进行。 管程中对每个条件变量都须予以说明其形式为: condition x,y; 对条件变量的操作仅仅是 wait 和 signal可表示为 x.wait 和 x.signal x.wait: 正在调用管程的进程因x条件需要被阻塞或挂起则调用 x.wait , 将自己插入到x条件的等待队列上并释放管程直到x条件变化。此时其它进程可以使用该管程。x.signal: 正在调用管程的进程发现x条件发生了变化则调用 x.signal重新启动一个因x条件而阻塞或挂起的进程如果存在多个这样的进程则选择其中的一个如果没有继续执行原进程而不产生任何结果。 每个条件变量保存了一个链表, 用于记录因该条件变量而阻塞的所有进程。 假设有两个进程 P 和 Q 进程 Q 因为某个条件 x 不满足而被阻塞了。进程 P 运行在管程中执行了 x.signal() 操作唤醒了等待条件 x 的进程 Q。 问题是进程 P 和进程 Q 都被激活了该让谁先执行谁等待 方式一P 等待Q 先执行 P 执行 x.signal() 后立即把自己挂起进入等待状态。Q 被唤醒后继续执行直到 Q 离开管程或因为其他条件再次被阻塞。然后P 才能继续执行。Hoare 管程采用这种方式。 方式二P 先执行Q 等待 P 执行 x.signal() 后继续执行直到 P 离开管程或因为其他条件被阻塞。然后Q 才能被重新启动并执行。MESA 管程采用这种方式。 方式三折中 - 规定 signal 操作必须是管程中过程的最后一个操作。 P 执行 x.signal() 后必须立即退出管程没有其他操作了。Q 被唤醒后可以立即执行而不需要和 P 竞争。Hansan 管程采用这种方式。 2.5 经典进程的同步问题
2.5.1 生产者-消费者问题Producer-Consumer Problem 1. 利用记录型信号量解决生产者-消费者问题
// 全局变量定义
int in 0, out 0; // in 和 out 是缓冲区的索引in 指向下一个空位out 指向下一个待消费的位置
item buffer[n]; // 缓冲区大小为 n
semaphore mutex 1; // 互斥信号量实现对缓冲区的互斥访问
semaphore empty n; // 空槽位信号量初始值为缓冲区的大小 n - 同步信号量表示空闲缓冲区的数量
semaphore full 0; // 满槽位信号量初始值为 0 - 同步信号量表示产品的数量也即非空缓冲区的数量// 生产者函数
void producer() {do {// 生产一个 itemitem nextp produce_item(); // 假设 produce_item() 是一个生产 item 的函数wait(empty); // 消耗一个空闲缓冲区wait(mutex); // 进入临界区实现对缓冲区的互斥访问 - ***实现互斥的P操作一定要在实现同步的P操作之后***buffer[in] nextp; // 将生产的 item 放入缓冲区in (in 1) % n; // 更新 in 索引循环使用缓冲区signal(mutex); // 离开临界区释放互斥锁signal(full); // 增加满槽位信号量通知消费者有新的 item 可用 - 增加一个产品} while (TRUE); // 无限循环
}// 消费者函数
void consumer() {do {wait(full); // 消耗一个产品(非空缓冲区)wait(mutex); // 进入临界区实现对缓冲区的互斥访问item nextc buffer[out]; // 从缓冲区中取出一个 itemout (out 1) % n; // 更新 out 索引循环使用缓冲区signal(mutex); // 离开临界区释放互斥锁signal(empty); // 增加空槽位信号量通知生产者有空槽位可用 - 增加一个空闲缓冲区consume_item(nextc); // 消费 item假设 consume_item() 是一个消费 item 的函数} while (TRUE); // 无限循环
}// 主函数
void main() {// 并发执行生产者和消费者cobeginproducer(); // 启动生产者consumer(); // 启动消费者coend
}
1. empty n
表示初始时缓冲区中有 n 个空槽位即 n 个资源未被使用。生产者生产一个 item 时会占用一个空槽位因此需要先 wait(empty)检查是否有空槽位可用。如果 empty 0生产者可以继续生产如果 empty 0表示缓冲区已满生产者需要等待。
2. full 0
表示初始时缓冲区中没有已生产的 item即没有资源被操作。消费者消费一个 item 时会释放一个空槽位因此需要先 wait(full)检查是否有已生产的 item 可以消费。如果 full 0消费者可以继续消费如果 full 0表示缓冲区为空消费者需要等待。
实现互斥的P操作一定要在实现同步的P操作之后
2. 利用 AND 信号量解决生产者-消费者问题
// 定义共享变量和信号量
int in 0, out 0; // 生产者和消费者的索引
item buffer[n]; // 容量为 n 的缓冲区
semaphore mutex 1, empty n, full 0; // 互斥信号量 mutex空槽位信号量 empty已生产项信号量 full// 生产者函数
void producer() {do {// 生产一个 itemitem nextp produce_item(); // 假设 produce_item() 是一个生产 item 的函数// 等待空槽位和互斥锁Swait(empty, mutex); // 等待空槽位empty--同时获取互斥锁mutex--// 将 item 放入缓冲区buffer[in] nextp;in (in 1) % n; // 更新生产者索引// 释放互斥锁和增加已生产项Ssignal(mutex, full); // 释放互斥锁mutex并增加已生产项full} while (TRUE); // 无限循环持续生产
}// 消费者函数
void consumer() {do {// 等待已生产项和互斥锁Swait(full, mutex); // 等待已生产项full--同时获取互斥锁mutex--// 从缓冲区取出 itemitem nextc buffer[out];out (out 1) % n; // 更新消费者索引// 释放互斥锁和增加空槽位Ssignal(mutex, empty); // 释放互斥锁mutex并增加空槽位empty// 消费 itemconsume_the_item(nextc); // 模拟消费 item} while (TRUE); // 无限循环持续消费
} 用 Swait(emptymutex)来代替 wait(empty)和 wait(mutex); 用 Ssignal(mutex, full)来代替 signal(mutex)和 signal(full); 用 Swait(full,mutex)代替 wait(full)和 wait(mutex) 用 Ssignal(mutexempty)代替Signal(mutex)和 Signal(empty)。
3. 利用管程解决生产者-消费者问题
// 定义生产者消费者问题的 Monitor —— Monitor 内部的所有方法是互斥执行的即同一时刻只能有一个线程执行 Monitor 中的方法。
Monitor ProducerConsumer {item buffer[N]; // 容量为 N 的缓冲区int in, out; // 共享变量缓冲区的读写索引condition notfull; // 条件变量缓冲区未满condition notempty; // 条件变量缓冲区不为空int count; // 缓冲区中当前的 item 数量 - 由于 Monitor 互斥性count 的修改和访问不会发生竞争条件即使它在多个线程之间共享。public:// 向缓冲区中放入 itemvoid put(item x) {// 如果缓冲区已满则等待 未满 条件if (count N) {cwait(notfull); // 阻塞当前线程等待缓冲区未满}// 将 item 放入缓冲区buffer[in] x;in (in 1) % N; // 更新生产者索引实现循环缓冲区count; // 增加缓冲区中的 item 数量// 通知消费者缓冲区不为空csignal(notempty); // 唤醒等待 不为空 条件的线程}// 从缓冲区中取出 itemvoid get(item x) {// 如果缓冲区为空则等待 不为空 条件if (count 0) {cwait(notempty); // 阻塞当前线程等待缓冲区不为空}// 从缓冲区中取出 itemx buffer[out];out (out 1) % N; // 更新消费者索引实现循环缓冲区count--; // 减少缓冲区中的 item 数量// 通知生产者缓冲区未满csignal(notfull); // 唤醒等待 未满 条件的线程}// 初始化缓冲区和条件变量ProducerConsumer() {in 0;out 0;count 0;}
} PC; // 定义 Monitor 实例 PC// 生产者线程函数
void producer() {item x; // 定义 item 变量 x用于存储生产的 itemwhile (TRUE) { // 无限循环持续生产 itemproduce an item in x; // 生产一个 item 并存入 xPC.put(x); // 将 item x 放入缓冲区}
}// 消费者线程函数
void consumer() {item x; // 定义 item 变量 x用于存储从缓冲区中取出的 itemwhile (TRUE) { // 无限循环持续消费 itemPC.get(x); // 从缓冲区中取出一个 item 并存入 xconsume the item in x; // 消费 item x}
}// 主函数
void main() {cobegin // 启动并发执行producer(); // 启动生产者线程consumer(); // 启动消费者线程coend // 并发执行结束
} 生产者线程 (producer) 生产者不断生产 item并将其放入缓冲区。使用 PC.put(x) 方法将生产出的 item x 放入缓冲区。 消费者线程 (consumer) 消费者不断从缓冲区中取出 item并消费它。使用 PC.get(x) 方法从缓冲区中取出 item x。 通过 Monitor PC 保证了缓冲区的线程安全访问。 条件变量的使用 使用 cwait 阻塞线程等待条件满足。使用 csignal 唤醒等待条件的线程。
2.5.2 哲学家进餐问题Dining Philosophers Problem
问题设定
场景5 位哲学家围坐在一张圆桌旁桌上摆放 5 根筷子每两位哲学家之间共享一根。哲学家行为 思考Thinking哲学家长时间思考不占用任何筷子。饥饿Hungry哲学家感到饥饿试图拿起 左右两边最靠近他的筷子 准备进餐。进餐Eating如果成功拿到两根筷子哲学家开始进餐进餐结束后放下筷子继续思考。【只有在拿到两只筷子时才能进餐】 每个哲学家进程需要同时持有两个临界资源才能开始吃饭。需要避免临界资源分配不当造成的死锁现象 1. 利用记录型信号量解决哲学家进餐问题
//--------------------有死锁风险------------------
// 定义5个信号量分别表示5根筷子初始值均为1表示筷子可用
semaphore chopstick[5] {1, 1, 1, 1, 1};// 哲学家i的行为
do {// 尝试获取左边的筷子i号筷子wait(chopstick[i]);// 尝试获取右边的筷子(i1)%5号筷子wait(chopstick[(i 1) % 5]);// 哲学家成功拿到两根筷子开始进餐eat();// 进餐结束后释放左边的筷子i号筷子signal(chopstick[i]);// 进餐结束后释放右边的筷子(i1)%5号筷子signal(chopstick[(i 1) % 5]);// 哲学家开始思考think();
} while (TRUE); // 无限循环
假如五位哲学家同时饥饿而各自拿起左边的筷子时就会使五个信号量chopstick均为0;当他们再试图去拿右边的筷子时都将因无筷子可拿而无限期地等待。对于这样的死锁问题可采取以下几种解决方法: 至多只允许有四位哲学家同时去拿左边的筷子 Semaphore philospher4;
Semaphore chopsticks[5]{1,1,1,1,1};
Philospher i(){while(1){P(philospher);P(chopsticks[i];P(chopsticks[(i1)%5];开始进餐;V(chopsticks[i]);V(chopsticks[(i1)%5]);V(philospher);
}一次仅有一位哲学家可以访问临界资源筷子 - 一个哲学家在拿筷子拿到一半时被阻塞也不会有别的哲学家会继续尝试拿筷子。 semaphore chopsticks[5]{1,1,1,1,1};//五个哲学家进程
semaphore mutex1; //互斥资源设置的互斥信号量
philosopher i(){while(1){//用p v操作框起来保证了左右两边都有筷子P(mutex);P(chopsticks[i]);//去左边的筷子P(chopsticks[(i1)%5]);//取右边的筷子 开始进餐V(mutex); //先释放互斥锁可以保证其他哲学家取用筷子不会被阻碍V(chopsticks[i]);v(chopsticks[(i1)%5]);思考
}规定奇数号哲学家先拿他左边的筷子然后再去拿右边的筷子;而偶数号哲学家则相反。 semaphore chopsticks[5]{1,1,1,1,1};//五个哲学家进程
void process(int i){while(1){if(i%20)//偶数号先拿右边的筷子{P(chopsticks[(i1)%5]);//取右边的筷子P(chopsticks[i]);//去左边的筷子开始进餐V(chopsticks[(i1)%5]);V(chopsticks[i]);}else //奇数号先拿左边的筷子{P(chopsticks[i]);//去左边的筷子P(chopsticks[(i1)%5]);//取右边的筷子开始进餐V(chopsticks[i]);V(chopsticks[(i1)%5]); } }
}2. 利用 AND 信号量解决哲学家进餐问题
// 声明并初始化5个信号量表示5根筷子初始状态均为可用1
semaphore chopstick[5] {1, 1, 1, 1, 1};// 哲学家i的循环行为
do {// 思考阶段think();// 同步请求两根筷子防止死锁的关键点// Sswait(chopstick[(i1)%5], chopstick[i]) 是一个原子操作// 1. 先尝试获取右边的筷子(i1)%5号// 2. 再尝试获取左边的筷子i号// 如果任一筷子不可用则阻塞避免循环等待Sswait(chopstick[(i 1) % 5], chopstick[i]);// 成功获取两根筷子后开始进餐eat();// 原子性地同时释放两根筷子// Ssignal会按请求顺序的逆序释放资源// 1. 先释放左边的筷子i号// 2. 再释放右边的筷子(i1)%5号Ssignal(chopstick[(i 1) % 5], chopstick[i]);} while (TRUE); // 无限循环
2.5.3 读者-写者问题Reader-Writer Problem
问题描述 与消费者进程不同,读者进程在读数据后并不会将数据清空并不会改变数据因此多个读者可同时访问共享数据 读进程与写进程同时共享数据可能导致读出的数据不一致的问题 两个写进程同时共享数据可能导致数据错误覆盖的问题 多个 读者Readers 和多个 写者Writers 共享同一个数据对象如文件、数据库、共享内存等。 读者只读取数据不会修改数据可并发执行。 写者会写入数据必须独占访问互斥访问。 关键约束条件 读写互斥一个写者不能和任何读者或其他写者同时访问数据。 优先级 读者优先只要存在读者写者会被阻塞。 ✅ 读者不会等待多个读者可以并发读无需互斥。 ❌ 可能导致写者饥饿如果一直有新的读者到来写者可能永远无法执行。 适用场景读操作远多于写操作且要求高读取并发性如数据库查询。 写者优先当有写者在等待时新来的读者必须等待正在执行的读者完成旧读者完成后写者先执行之后才允许新读者进入。 ✅ 写者不会被饿死只要有写者在等待新读者就不能进入临界区。 ❌ 读者可能等待较久但不会完全饿死。 适用场景写操作频率较高且要求数据一致性如日志系统、内存缓存。 公平策略通过FIFO调度读者和写者——即读者和写者按到达顺序执行确保公平性。 适用场景读写比例均衡的系统
1. 利用记录型信号量解决读者-写者问题
//------------------------------读者优先--------------------------
semaphore rmutex 1; // 保护 readcount 的互斥锁读者间互斥
semaphore wmutex 1; // 读写互斥锁保证写者独占
int readcount 0; // 当前正在读取的读者数量//--------------------- 读者线程 ---------------------//
void reader() {do {// 1. 进入临界区保护 readcountwait(rmutex); if (readcount 0) // 如果是第一个读者需要占用写锁wait(wmutex); // 阻止写者进入readcount; // 增加读者计数signal(rmutex); // 释放 readcount 锁// 2. 执行读操作此时允许多个读者并发读/* perform read operation */ // 3. 离开临界区更新 readcountwait(rmutex); readcount--; if (readcount 0) // 如果是最后一个读者释放写锁signal(wmutex); // 允许写者进入signal(rmutex); } while (TRUE); // 循环执行
}//--------------------- 写者线程 ---------------------//
void writer() {do {wait(wmutex); // 获取写锁独占访问/* perform write operation */ // 执行写操作signal(wmutex); // 释放写锁} while (TRUE); // 循环执行
}//--------------------- 主程序 ---------------------//
void main() {cobegin // 并发执行读者和写者reader();writer();coend
}信号量作用 rmutex保护 readcount 变量防止多个读者同时修改导致竞争。 互斥修改 readcount 通过 wait(rmutex)/signal(rmutex) 确保同一时间只有一个线程能修改 readcount。 避免重复获取 wmutex 第一个读者readcount 0会获取 wmutex后续读者跳过这一步。最后一个读者readcount 0会释放 wmutex。rmutex 保证这一判断和操作的原子性防止多个读者竞争 wmutex。 wmutex实现读写互斥保证写者独占访问 读者逻辑 进入时第一个读者获取 wmutex后续读者只需递增 readcount。退出时最后一个读者释放 wmutex允许写者执行。 写者逻辑 必须独占 wmutex因此会等待所有读者完成readcount 0
2. 利用信号量集解决读者-写者问题
增加了一个限制即最多只允许RN个读者同时读
//------------------------------写者优先--------------------------
int RN; // 最大支持的读者数量
semaphore L RN; // 控制读者并发数初始值为RN
semaphore mx 1; // 写锁保证写操作的互斥性// 读者线程
void reader() {do {// Swait(L,1,1): 申请一个L信号量若L≥1则减1否则阻塞Swait(L, 1, 1); // 占用一个读者名额// Swait(mx,1,0): 检查mx是否为0不阻塞仅测试Swait(mx, 1, 0); // 检查是否有写者正在写/* 执行读操作多个读者可并发读 */// Ssignal(L,1): 释放一个L信号量读者退出Ssignal(L, 1); // 释放读者名额} while (TRUE);
}// 写者线程
void writer() {do {// Swait(mx,1,1; L,RN,0): 同时申请mx锁并检查无读者LRNSwait(mx, 1, 1; L, RN, 0); // 1. 独占mx锁2. 确保无活跃读者LRN/* 执行写操作写者独占访问 */// Ssignal(mx,1): 释放mx锁Ssignal(mx, 1); // 允许其他写者或读者进入} while (TRUE);
}// 主程序
void main() {cobeginreader(); // 启动读者线程writer(); // 启动写者线程coend
}RN 表示系统允许的 最大读者并发数初始化时 L RN 表示所有读者名额可用。 Swait(L,1,1)读者线程 申请一个读者名额若 L ≥ 1 则减少 L否则阻塞。保证当前活跃读者数 不超过 RN。 Swait(mx,1,0)读者线程 非阻塞检查写锁仅测试 mx 是否为 0无写者不影响信号量值。确保 无写者正在写 时才允许读。 Swait(mx,1,1; L,RN,0)写者线程 同时满足两个条件 mx 1获取写锁保证互斥。L RN确保 所有读者名额均未被占用即无活跃读者。 写者优先于新读者防止读者饥饿。 写者通过 Swait(mx,1,1; L,RN,0) 严格抢占资源 写者在进入临界区时必须同时满足两个条件 (1) 获得写锁 mx保证互斥。(2) 检查读者信号量 L RN即当前没有活跃的读者。 这意味着 只要有读者在读写者必须等待L RN 时写者会被阻塞。但在写者竞争时新的读者无法抢占资源因为 L 已经被占用。 Ssignal 操作 读者退出时释放 L允许新读者进入。写者退出时释放 mx允许其他写者或读者竞争。
2.5.4 可生产单种产品的多生产者-多消费者问题 2.5.5 吸烟者问题 - 可生产多种产品的单生产者-多消费者问题 2.6 进程通信
进程通信(Inter-Process Communication, IPC)是指进程之间的信息交换。
2.6.1 进程通信的类型
高级通信机制可归结为四大类: 共享存储器系统、管道通信系统、消息传递系统以及客户机-服务器系统。
1、共享存储器系统 (Shared-Memory System)
相互通信的进程共享某些数据结构或共享存储区进程之间能够通过这些空间进行通信。可分成以下两种类型:
低级通信基于共享数据结构的通信方式。【如在生产者-消费者问题中的有界缓冲区】 操作系统仅提供共享存储器由程序员负责对公用数据结构的设置及对进程间同步的处理。仅适于传递相对少量的数据通信效率低下。高级通信基于共享存储区的通信方式。 需要通信的进程在通信前先向系统申请获得【共享存储区域在内存中划出的且所有进程都可进行读或写交换信息的且访问是互斥的】共享存储区域中的一个分区并将其附加到自己的地址空间中便可对其中的数据进行正常读、写交换信息实现通信读写完成或不再需要时将其归还给共享存储区。数据的形式和位置甚至访问控制都是由进程负责而不是OS。可传输大量数据。 2、管道(pipe)通信系统
“管道”是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件又名 pipe 文件。可有效地传送大量数据。 本质是在内存中开辟一个大小固定的内存缓冲区读写数据先进先出。管道是循环队列
输入的发送进程(即写进程)以字符流形式将大量的数据送入管道;输出的接收进程(即读进程)从管道中接收(读)数据。
管道机制必须提供以下三方面的协调能力:
①互斥即当一个进程正在对 pipe 执行读/写操作时其它(另一)进程必须等待。【各进程要互斥地访问管道(由操作系统实现)】②同步 指当写(输入)进程把一定数量的数据写入 pipe便去睡眠等待直到读(输出)进程取走数据后再把它唤醒。 写进程往管道里写数据如果管道满了写进程会阻塞睡眠等待等读进程取走数据后(管道未满)就可 “叫醒”唤醒继续写。当读进程读一空 pipe 时也应睡眠等待直至写进程将数据写入管道后才将之唤醒。 读进程从管道里读数据如果管道是 空的读进程会 “阻塞”睡眠等待等写进程往里写了新数据后(管道未空)就可 “叫醒”唤醒继续读。 ③确定对方是否存在只有确定了对方已存在时才能进行通信。
管道只能采用华双工通信某一时间段内只能实现单向的传输。如果要实现双向同时通信则需要设置两个管道。
管道中的数据一旦被读出就彻底消失。因此当多个进程读同一个管道时可能会错乱。对此通常有两种解决方案:①一个管道允许多个写进程一个读进程(2014年408真题高教社官方答案);②允许有多个写进程多个读进程但系统会让各个读进程轮流从管道中读数据(Linux的方案)。
3、消息传递系统 (Message passing system)
进程不借助任何共享存储区或数据结构是以格式化的消息(message)为单位将通信的数据封装在消息中并利用操作系统提供的一组通信命令(原语)在进程间进行消息传递完成进程间的数据交换。
基于消息传递系统的通信方式属于高级通信方式可分成两类:
直接通信方式是指发送进程利用OS所提供的发送原语直接把消息发送给目标进程:间接通信方式是指发送和接收进程都通过共享中间实体(称为邮箱)的方式进行消息的发送和接收完成进程间的通信。
4、客户机-服务器系统 (Client-Server system)
主要的实现方法分为三类:套接字、远程过程调用和远程方法调用 套接字 概念 一个套接字就是一个通信标识类型的数据结构包含了通信目的的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址以及针对客户或服务器程序提供的不同系统调用(或 API函数)等。是进程通信【同一台计算机内部的进程通信】和网络通信【网络环境中不同计算机间的进程通信】的基本构件。每个套接字拥有唯一的套接字号(也称套接字标识符)系统中所有的连接都持有唯一的一对套接字及端口连接能区分来自不同应用程序进程或网络连接的通信 套接字是为客户/服务器模型而设计的通常套接字包括两类: 基于文件型: 通信进程都运行在同一台机器的环境中套接字是基于本地文件系统支持的一个套接字关联到一个特殊的文件通信双方通过对这个特殊文件的读写实现通信其原理类似于前面所讲的管道。 基于网络型: 该类型通常采用的是非对称方式通信即发送者需要提供接收者命名。 通信双方的进程运行在不同主机的网络环境下被分配了一对套接字一个属于接收进程(或服务器端)一个属于发送进程(或客户端)。 发送进程(或客户端)发出连接请求时随机申请一个套接字主机为之分配一个端口与该套接字绑定不再分配给其它进程。 接收进程(或服务器端) 拥有全局公认的套接字和指定的端口(如ftp 服务器监听端口为 21http服务器监听端口为 80)并通过监听端口等待客户请求。任何进程都可以向接收进程发出连接请求和信息请求。 接收进程(或服务器端)一旦收到请求就接受来自发送进程(或客户端)的连接完成连接即在主机间传输的数据可以准确地发送到通信进程实现进程间的通信;当通信结束时系统通过关闭接收进程(或服务器端)的套接字撤销连接。 远程过程调用和远程方法调用 概念 远程过程(函数)调用 RPC(Remote Procedure Call)是一个通信协议用于通过网络连接的系统。该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程。如果涉及的软件采用面向对象编程那么远程过程调用亦可称做远程方法调用。 角色 进程有两个本地客户进程 ➕ 远程服务器进程这两个进程通常也被称为网络守护进程主要负责在网络间的消息传递 一般情况下这两个进程都是处于阻塞状态等待消息。 存根(stub)有两个一般也是处于阻塞状态等待消息。 在本地客户端每个能够独立运行的远程过程都拥有一个客户存根(Client Stub) 客户存根(Client Stub): 伪装成远程服务让本地代码以为在调用本地方法其实是将本地调用转为网络请求。 ✔️ 核心职责 伪装成远程服务 在代码中客户端存根会暴露和远程服务完全相同的接口方法例如GetUser(id)。开发者调用client.GetUser(123)时并不知道该方法实际会触发网络通信仿佛在调用本地代码。 本地调用 → 网络请求的转换 接收本地参数存根获取方法名GetUser和参数id123。序列化参数将参数转换为网络传输格式如Protobuf / JSON。协议封装按协议如HTTP/gRPC构造协议头并打包请求数据。 隐藏网络细节 开发者无需处理Socket连接、数据分包、超时重试、负载均衡等底层问题。 在每个远程进程所在的服务器端其所对应的实际可执行进程也存在一个服务器存根(Server Stub)。 服务器存根(Server Stub) 接收、解析客户端请求并驱动真实业务逻辑执行最终封装结果返回给客户端 ✔️ 核心职责 接收网络请求 监听特定协议如 HTTP/gRPC的端口接收客户端发来的二进制数据流。 反序列化请求 解析协议头如 gRPC 的 Content-Type提取方法名和参数。将二进制数据还原为编程语言对象如 Protobuf → Go 结构体。 调用真实服务 根据方法名如 GetUser找到服务端注册的业务实现类如 UserService。传入反序列化后的参数执行实际逻辑如查询数据库。 封装响应 将业务结果或异常序列化为网络格式如 Protobuf/JSON。按协议组装响应头如 HTTP 状态码、gRPC 的 grpc-status。 步骤 本地过程调用者以一般方式调用远程过程在本地关联的客户存根传递相应的参数然后将控制权转移给客户存根;客户存根执行完成包括过程名和调用参数等信息的消息建立将控制权转移给本地客户进程;本地客户进程完成与服务器的消息传递将消息发送到远程服务器进程:远程服务器进程接收消息后转入执行并根据其中的远程过程名找到对应的服务器存根将消息转给该存根;服务器存根接到消息后由阻塞状态转入执行状态拆开消息从中取出过程调用的参数然后以一般方式调用服务器上关联的过程;在服务器端的远程过程(真实服务-业务逻辑的代码)运行完毕后将结果返回给与之关联的服务器存根:该服务器存根获得控制权运行将结果打包为消息并将控制权转移给远程服务器进程;远程服务器进程将消息发送回客户端;本地客户进程接收到消息后根据其中的过程名将消息存入关联的客户存根再将控制权转移给客户存根;客户存根从消息中取出结果返回给本地调用者进程并完成控制权的转移。 #mermaid-svg-mcu1muUSyIdWg6OX {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-mcu1muUSyIdWg6OX .error-icon{fill:#552222;}#mermaid-svg-mcu1muUSyIdWg6OX .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-mcu1muUSyIdWg6OX .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-mcu1muUSyIdWg6OX .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-mcu1muUSyIdWg6OX .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-mcu1muUSyIdWg6OX .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-mcu1muUSyIdWg6OX .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-mcu1muUSyIdWg6OX .marker{fill:#333333;stroke:#333333;}#mermaid-svg-mcu1muUSyIdWg6OX .marker.cross{stroke:#333333;}#mermaid-svg-mcu1muUSyIdWg6OX svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-mcu1muUSyIdWg6OX .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-mcu1muUSyIdWg6OX text.actortspan{fill:black;stroke:none;}#mermaid-svg-mcu1muUSyIdWg6OX .actor-line{stroke:grey;}#mermaid-svg-mcu1muUSyIdWg6OX .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-mcu1muUSyIdWg6OX .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-mcu1muUSyIdWg6OX #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-mcu1muUSyIdWg6OX .sequenceNumber{fill:white;}#mermaid-svg-mcu1muUSyIdWg6OX #sequencenumber{fill:#333;}#mermaid-svg-mcu1muUSyIdWg6OX #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-mcu1muUSyIdWg6OX .messageText{fill:#333;stroke:#333;}#mermaid-svg-mcu1muUSyIdWg6OX .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-mcu1muUSyIdWg6OX .labelText,#mermaid-svg-mcu1muUSyIdWg6OX .labelTexttspan{fill:black;stroke:none;}#mermaid-svg-mcu1muUSyIdWg6OX .loopText,#mermaid-svg-mcu1muUSyIdWg6OX .loopTexttspan{fill:black;stroke:none;}#mermaid-svg-mcu1muUSyIdWg6OX .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-mcu1muUSyIdWg6OX .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-mcu1muUSyIdWg6OX .noteText,#mermaid-svg-mcu1muUSyIdWg6OX .noteTexttspan{fill:black;stroke:none;}#mermaid-svg-mcu1muUSyIdWg6OX .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-mcu1muUSyIdWg6OX .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-mcu1muUSyIdWg6OX .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-mcu1muUSyIdWg6OX .actorPopupMenu{position:absolute;}#mermaid-svg-mcu1muUSyIdWg6OX .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-mcu1muUSyIdWg6OX .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-mcu1muUSyIdWg6OX .actor-man circle,#mermaid-svg-mcu1muUSyIdWg6OX line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-mcu1muUSyIdWg6OX :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 客户端代码-本地调用者 客户端存根 本地客户进程(网络库) 远程服务器进程 服务器存根 真实服务-业务逻辑的代码 调用远程过程像调用本地方法传递相应的参数 序列化参数 添加 gRPC 头部方法路径、超时等 序列化参数 等信息的消息建立 发送网络请求消息传递传输二进制数据 将消息路由到对应的服务器存根 反序列化参数 调用服务器端的真实服务 返回 结果 序列化结果 打包结果为消息 传回二进制数据 将消息路由到对应的客户存根 反序列化结果 取出结果并返回 客户端代码-本地调用者 客户端存根 本地客户进程(网络库) 远程服务器进程 服务器存根 真实服务-业务逻辑的代码
2.6.2 消息传递通信的实现方式
进程通信分为直接和间接两种通信方式
1、直接消息传递系统 - 直接通信
发送进程利用OS所提供的发送命令(原语)直接把消息发送给目标进程。
直接通信原语 对称寻址方式要求发送进程和接收进程都必须以显式方式提供对方的标识符。 发送一个消息给接收进程 send(receiver, message); - 将消息message发送给接收进程receiver 接收 Sender 发来的消息 receive(sender,message); - 接收由sender发来的消息message。 缺点一旦改变进程的名称则可能需要检查所有其它进程的定义有关对该进程旧名称的所有引用都必须查找到修改为新名称【不利于实现进程定义的模块化】 非对称寻址方式在接收进程的原语中不需要命名发送进程只填写表示源进程的参数发送进程仍需要命名接收进程。 发送一个消息给进程P send(P,message); 接收来自任何进程的消息 receive (id,message); id变量可为发送方进程 id 或名字。
消息的格式 : 可采用变长的消息格式即进程所发送消息的长度是可变的。
进程的同步方式 - 协调通信 三种情况:
①发送进程阻塞接收进程阻塞。这种情况主要用于进程之间紧密同步发送进程和接收进程之间无缓冲时。②发送进程不阻塞、接收进程阻塞。应用最广。 发送进程平时不阻塞可以尽快地把一个或多个消息发送给多个目标;接收进程平时则处于阻塞状态直到发送进程发来消息时才被唤醒。 ③发送进程和接收进程均不阻塞。较常见的。平时发送进程和接收进程都在忙于自己的事情仅当发生某事件使它无法继续运行时才把自己阻塞起来等待。
通信链路 发送进程和接收进程之间建立一条通信链路进行通信。
建立通信链路有两种方式 由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路在链路使用完后拆除链路。这种方式主要用于计算机网络中。发送进程无须明确提出建立链路的请求只须利用系统提供的发送命令(原语)系统会自动地建立一条链路。这种方式主要用于单机系统中。 链路分成两种: 单向通信链路只允许发送进程向接收进程发送消息或者相反;双向通信链路既允许由进程A向进程B发送消息也允许进程 B同时向进程A发送消息。 2、信箱通信 - 间接通信
进程之间的通信需要通过某种中间实体(如共享数据结构等)来完成。该实体建立在随机存储器的公用缓冲区上用来暂存发送进程发送给目标进程的消息;接收进程可以从该实体中取出发送进程发送给自己的消息通常把这种中间实体称为邮箱(或信箱);每个邮箱都有一个唯一的标识符。实现实时通信又可实现非实时通信。
信箱结构
在逻辑上可以将其分为两个部分: 消息的传递可以单向传递也可以是双向的
信箱头用以存放有关信箱的描述信息如信标识符、信的拥有者、信箱口信箱的空格数等;信箱体由若干个可以存放消息(或消息头)的信箱格组成信箱格的数目以及每格的大小是在创建信箱时确定的。 信箱通信原语
邮箱的创建和撤消。 进程可利用邮箱创建原语来建立一个新邮箱创建者进程应给出邮箱名字、邮箱属性(公用、私用或共享); 对于共享邮箱还应给出共享者的名字。当进程不再需要读邮箱时可用邮箱撤消原语将之撤消。 消息的发送和接收。当进程之间要利用邮箱进行通信时必须使用共享邮箱并利用系统提供的下述通信原语进行通信。 将一个消息发送到指定邮箱 Send(mailboxmessage);从指定邮箱中接收一个消息 Receive(mailbox,message); 信箱的类型 邮箱可由操作系统创建也可由用户进程创建创建者是邮箱的拥有者。据此可把邮箱分为以下三类:
私用邮箱。 用户进程可为自己建立一个新邮箱并作为该进程的一部分。邮箱的拥有者有权从邮箱中读取消息其他用户则只能将自己构成的消息发送到该邮箱中。采用单向通信链路的邮箱来实现。当拥有该邮箱的进程结束时,邮箱也随之消失。 公用邮箱。 由操作系统创建并提供给系统中的所有使用。 核准进程Authorized Process是指经过系统安全机制验证具备特定权限或资源访问资格的进程。其核心目的是防止未授权的代码或用户执行特权操作核准进程既可把消息发送到该邮箱中也可从邮箱中读取发送给自己的消息。采用双向通信链路的邮箱来实现。公用邮箱在系统运行期间始终存在。 共享邮箱。 由某进程创建在创建时或创建后指明它是可共享的同时须指出共享进程(用户)的名字。邮箱的拥有者和共享者都有权从邮箱中取走发送给自己的消息。
在利用邮箱通信时,在发送进程和接收进程之间, 存在以下四种关系:
一对一关系。发送进程和接收进程可以建立一条两者专用的通信链路使两者之间的交互不受其他进程的干扰。多对一关系。允许一个服务(接收)进程与多个用户(发送)进程之间进行交互也称为客户/服务器交互(client/server interaction)。一对多关系。允许一个发送进程与多个接收进程进行交互使发送进程可用广播方式向接收者(多个)发送消息。多对多关系。允许建立一个公用邮箱让多个进程都能向邮箱中投递消息; 也可从邮箱中取走属于自己的消息。
2.6.3 直接消息传递系统实例
消息缓冲队列通信机制被广泛应用于本地进程之间的通信中。
发送进程利用Send 原语将消息直接发送给接收进程接收进程则利用 Receive 原语接收消息。
1、消息缓冲队列通信机制中的数据结构
消息缓冲区
type struct message_buffer {int sender; // 发送者进程标识符int size; // 消息长度char *text; // 消息正文struct message_buffer *next; // 指向下一个消息缓冲区的指针
}PCB中有关通信的数据项。 消息队列队首指针用于对消息队列进行操作用于实现同步的互斥信号量mutex资源信号量sm
type struct processcontrol_block {...struct message_buffer *mq; // 消息队列队首指针semaphore mutex; // 消息队列互斥信号量semaphore sm; // 消息队列资源信号量...
}PCB ;2、发送原语
发送进程在利用发送原语发送消息之前应先在自己的内存空间设置一发送区a把待发送的消息正文、发送进程标识符、消息长度等信息填入发送区a中调用发送原语把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度来申请一缓冲区接着把发送区a中的信息复制到缓冲区中将缓冲区挂在接收进程的消息队列(临界资源)上。 void send(receiver, a) // receiver为接收进程标识符a为发送区首址
{// 根据 a.size 申请缓冲区;getbuf(a.size, i); // 将发送区a中的信息复制到消息缓冲区i中;copy(i.sender, a.sender); i.size a.size;copy(i.text, a.text);i.next 0;// 获得接收进程内部的标识符j;getid(PCBset, receiver.j);wait(j.mutex);// 将消息缓冲区插入消息队列;insert(j.mq, i);signal(j.mutex);signal(j.sm);
}3、接收原语
接收进程调用接收原语receive(b)从自己的消息缓冲队列中摘下第一个消息缓冲区并将其中的数据复制到以b为首址的指定消息接收区内释放消息缓冲区。
void receive(b){// j为接收进程内部的标识符;j internal name;wait(j.sm);wait(j.mutex);// 将消息队列中第一个消息移出;remove(j.mq, i);signal(j.mutex);// 将消息缓冲区i中的信息复制到接收区 b;copy(b.sender, i.sender);b.size i.size;copy(b.text, i.text);// 释放消息缓冲区;releasebuf(i);
}2.7 线程(Threads)的基本概念
引入进程的目的是为了使多个程序能并发执行以提高资源利用率和系统吞吐量。
引入线程的目的是为了减少程序在并发执行时所付出的时空开销使OS具有更好的并发性。
2.7.1 线程的引入
1、进程的两个基本属性 进程是一个可拥有资源的独立单位一个进程要能独立运行它必须拥有一定的资源包括用于存放程序正文、数据的磁盘和内存地址空间以及它在运行时所需要的 I/O 设备、已打开的文件、信号量等; 进程同时又是一个可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB系统可根据其PCB感知进程的存在也可以根据其 PCB 中的信息对进程进行调度还可将断点信息保存在其PCB中。反之再利用进程 PCB 中的信息来恢复进程运行的现场。 调度Scheduling决定哪个就绪进程将来获得CPU决策过程。 分派Dispatching执行调度的决策实际将CPU分配给该进程动作过程使其从就绪态转为运行态的过程。
2、程序并发执行所需付出的时空开销
为使程序能并发执行系统必须进行以下的一系列操作:
创建进程系统在创建一个进程时必须为它分配其所必需的、除处理机以外的所有资源如内存空间、I/O设备以及建立相应的PCB撤消进程系统在撤消进程时又必须先对其所占有的资源执行回收操作然后再撤消PCB进程切换对进程进行上下文切换时需要保留当前进程的CPU环境设置新选中进程的 CPU 环境因而须花费不少的处理机时间。
2.7.2 线程与进程的比较
由于线程具有许多传统进程所具有的特征所以又称之为轻型进程(Light-Weight Process)或进程元
把传统进程称为重型进程(Heavy-Weight Process)相当于只有一个线程的任务。
1、调度的基本单位 进程作为独立调度和分派的基本单位——进程是能独立运行的基本单位。在每次被调度时都需要进行上下文切换开销较大。 线程作为调度和分派的基本单位——线程是能独立运行的基本单位。当线程切换时仅需保存和设置少量寄存器内容切换代价远低于进程。 在同一进程中线程的切换不会引起进程的切换但从一个进程中的线程切换到另一个进程中的线程时必然就会引起进程的切换。 传统进程机制中进程是资源分配、调度的基本单位 引入线程后进程是资源分配的基本单位线程是调度的基本单位
2、并发性
进程之间可以并发执行在一个进程中的多个线程之间甚至所有线程可并发执行不同进程中的线程也能并发执行 例子在文字处理器中可以设置三个线程 第一个线程用于显示文字和图形第二个线程从键盘读入数据第三个线程在后台进行拼写和语法检查 3、拥有资源
进程可以拥有资源并作为系统中拥有资源的一个基本单位。线程拥有少量资源【一组寄存器和堆】, 以保证独立运行。 在每个线程中都应具有一个用于控制线程运行的线程控制块 TCB用于指示被执行指令序列的程序计数器保留局部变量少数状态参数返回地址。 允许多个线程共享该进程所拥有的资源: 属于同一进程的所有线程都具有相同的地址空间——线程可以访问该地址空间中的每一个虚地址可以访问进程所拥有的资源如已打开的文件、定时器、信号量机构等的内存空间和它所申请到的I/O设备等。
4、独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。
【为防止进程之间彼此干扰和破坏】每个进程都拥有一个独立的地址空间和其它资源除了共享全局变量外不允许其它进程的访问。同一进程中的不同线程之间可以相互合作它们共享进程的内存地址空间和资源。
5、系统开销
进程创建或撤消时大于线程所付出的开销:
在创建或撤消进程时系统都要为之分配和回收进程控制块、分配或回收其它资源如内存空间和 I/O 设备等。在进程切换时涉及到进程上下文的切换系统开销大; 线程间并发如果是同一进程内的线程切换则不需切换进程环境系统开销小。在一些OS中线程的切换、同步和通信都无需操作系统内核的干预。
6、支持多处理机系统
在多处理机系统中对于传统的进程即单线程进程不管有多少处理机该进程只能运行在一个处理机上。在多处理机系统中对于多线程进程可以将一个进程中的多个线程分配到多个处理机上使它们并行执行。
2.7.3 线程的状态和线程控制块
1、线程运行的三个状态
执行状态表示线程已获得处理机而正在运行;就绪状态指线程已具备了各种执行条件只须再获得CPU便可立即执行;阻塞状态指线程在执行中因某事件受阻而处于暂停状态。
2、线程控制块 TCB
每个线程配置了一个线程控制块TCB,将所有用于控制和管理线程的信息记录在线程控制块中。
线程控制块通常有这样几项:
① 线程标识符为每个线程赋予一个唯一的线程标识符;② 一组寄存器包括程序计数器PC、状态寄存器和通用寄存器的内容;③ 线程运行状态用于描述线程正处于何种运行状态;④ 优先级描述线程执行的优先程度;⑤ 线程专有存储区用于线程切换时存放现场保护信息和与该线程相关的统计信息等;⑥ 信号屏蔽即对某些信号加以屏蔽⑦ 堆栈指针每个线程需设置一个堆栈用它来保存局部变量和返回地址【在线程运行时经常会进行过程调用而过程的调用通常会出现多重嵌套的情况就必须将每次过程调用中所使用的局部变量以及返回地址保存起来。】。在TCB中须设置两个指向堆栈的指针: 指向用户自己堆栈的指针当线程运行在用户态时使用用户自己的用户栈来保存局部变量和返回地址指向核心栈的指针当线程运行在核心态时使用系统的核心栈。
3、多线程 OS 中的进程属性
进程是一个可拥有资源的基本单位。在多线程OS中进程仍是作为系统资源分配的基本单位任一进程所拥有的资源都包括: 用户的地址空间实现进程(线程)间同步和通信的机制已打开的文件已申请到的I/O 设备一张由核心进程维护的地址映射表该表用于实现用户程序的逻辑地址到其内存物理地址的映射。 多个线程可并发执行。通常一个进程都含有若干个相对独立的线程(至少要有一个线程)。 把传统进程的执行方法称为单线程方法。将每个进程支持多个线程执行的方法称为多线程方法。 进程已不是可执行的实体。在多线程OS中是把线程作为独立运行(或称调度)的基本单位。 进程仍具有与执行相关的状态——所谓进程处于“执行”状态实际上是指该进程中的某线程正在执行。对进程所施加的与进程状态有关的操作也对其线程起作用。 例如在把某个进程挂起时该进程中的所有线程也都将被挂起又如在把某进程激活时属于该进程的所有线程也都将被激活、
2.8 线程的实现
2.8.1 线程的实现方式
1、内核支持线程 KST(Kernel Supported Threads) - 内核空间 特点 在内核空间中实现的在OS中的所有进程【无论是系统进程还是用户进程】都是在操作系统内核的支持下运行的。内核支持线程KST同样也是在内核的支持下运行的它们的创建、阻塞、撤消和切换等也都是在内核空间实现的。在内核空间也为每一个内核线程设置了一个线程控制块内核根据该控制块感知某线程的存在并对其加以控制和管理。调度是以线程为单位进行的 优点 在多处理器系统中内核能够同时调度同一进程中的多个线程并行执行;并发能力强如果进程中的一个线程被阻塞了内核可以调度该进程中的其它线程占有处理器运行也可以运行其它进程中的线程;内核支持线程具有很小的数据结构和堆栈线程的切换比较快切换开销小;内核本身也可以采用多线程技术可以提高系统的执行速度和效率。 缺点 对于用户的线程切换而言其模式切换的(CPU 需要变态)开销较大在同一个进程中从一个线程切换到另一个线程时需要从用户态转到核心态进行这是因为用户进程的线程在用户态运行而线程调度和管理是在内核实现的系统开销较大。
2、用户级线程 ULT(User Level Threads) - 用户空间 特点 用户级线程是与内核无关对线程的创建、撤消、同步与通信等功能都无需内核的支持内核完全不知道用户级线程的存在。是在用户空间中实现的线程的任务控制块都是设置在用户空间线程所执行的操作也无需内核的帮助 - 不需要CPU变态。是应用程序通过线程库实现的。调度是以进程为单位进行的。 优点 线程切换不需要转换到内核空间开销小。 所有线程管理数据结构TCB 存放在进程的用户空间切换时 不涉及内核模式避免用户态→内核态切换开销。线程切换由用户级线程库直接管理不依赖操作系统内核。 调度算法可以是进程专用的。在不干扰 OS 调度的情况下每个进程可定制独立的线程调度策略。用户级线程的实现与OS平台无关。对于线程管理的代码是属于用户程序的一部分所有的应用程序都可以对之进行共享。线程机制不依赖 OS 内核支持。即使 OS 本身不支持线程如早期 Unix用户程序仍可模拟多线程基于协程、状态机。 用户级线程ULT和 内核级线程KLT对比
优点用户级线程ULT内核级线程KLT切换速度快无内核介入慢需切换至内核态调度控制进程可自定义调度策略由 OS 统一调度多核并行不真正并行OS 仅调度单进程可多核并行跨平台性强不依赖内核支持依赖 OS 线程机制如 Windows CreateThread
缺点用户级线程ULT内核级线程KLT系统调用阻塞整个进程/某一个线程阻塞所有线程暂停仅阻塞当前线程其他线程可运行多核并行多个线程不可在多核处理机上并行运行单进程单CPU分配线程可分配到不同核心并行执行
3、组合
把用户级线程和内核支持线程两种方式进行组合提供了组合方式ULT/KST线程。在组合方式线程系统中
内核支持多个内核支持线程的建立、调度和管理;也允许用户应用程序建立、调度和管理用户级线程。
组合方式线程中同一个进程内的多个线程可以同时在多处理器上并行执行而且在阻塞一个线程时并不需要将整个进程阻塞。
由于用户级线程和内核支持线程连接方式的不同从而形成了三种不同的模型:
多对一模型即将用户线程映射到一个内核控制线程。 这些用户线程一般属于一个进程运行在该进程的用户空间对这些线程的调度和管理也是在该进程的用户空间中完成。 仅当用户线程需要访问内核时才将其映射到一个内核控制线程上但每次只允许一个线程进行映射。优点线程管理的开销小效率高缺点如果一个线程在访问内核时发生阻塞则整个进程都会被阻塞; 此外在任一时刻只有一个线程能够访问内核多个线程不能同时在多个处理机上运行。 一对一模型即将每一个用户级线程映射到一个内核支持线程。 为每一个用户线程都设置一个内核控制线程与之连接。优点当一个线程阻塞时允许调度另一个线程运行所以它提供了比多对一型更好的并发功能。此外在多处理机系统中它允许多个线程并行地运行在多处理机系统上。缺点每创建一个用户线程相应地就需要创建一个内核线程开销较大因此需要限制整个系统的线程数。 多对多模型即将许多用户线程映射到同样数量或更少数量的内核线程上。 内核控制线程的数目可以根据应用进程和系统的不同而变化可以比用户线程少也可以与之相同。该模型结合上述两种模型的优点 可以像一对一模型那样使个进程的多个线程并行地运行在多处理机系统上也可像多对一模型那样减少线程的管理开销和提高效率。
2.8.2 线程的实现
不论是进程还是线程都必须直接或间接地取得内核的支持。
1、内核支持线程的实现
系统在创建一个新进程时便在内核空间为它分配一个任务数据区 PTDA(Per Task Data Area)其中包括若干个线程控制块 TCB 空间。在每一个TCB中可保存线程标识符、优先级、线程运行的 CPU状态等信息。每当进程要创建一个线程时便为新线程分配个TCB将有关信息填入该TCB中并为之分配必要的资源。当PTDA中的所有TCB 空间已用完而进程又要创建新的线程时只要其所创建的线程数目未超过系统的允许值(通常为数十至数百个)系统可再为之分配新的 TCB 空间。在撤消一个线程时也应回收该线程的所有资源和 TCB。 有的系统中为了减少在创建和撤消一个线程时的开销在撤消一个线程时并不立即回收该线程的资源和 TCB——当以后再要创建一个新线程时便可直接利用已被撤消但仍保持有资源的 TCB作为新线程的TCB。内核支持线程的调度和切换与进程的调度和切换十分相似也分抢占式方式和非抢占方式两种。在线程的调度算法上同样可采用时间片轮转法、优先权算法等。
2、用户级线程的实现 用户级线程是在用户空间实现的。 所有的用户级线程都具有相同的结构它们都运行在一个中间系统上。当前有两种方式实现中间系统即运行时系统和内核控制线程。 运行时系统Runtime System 本质一组用于管理和控制线程的函数过程的集合包含 线程生命周期管理创建、撤销线程同步与通信互斥锁、信号量、条件变量线程调度选择合适的就绪线程执行 作用 使用户级线程无需依赖内核纯用户空间实现。充当用户级线程与内核之间的接口但本身不进入内核。 线程切换机制 传统进程切换必须进入内核态user → kernel由 OS 完成上下文切换。用户级线程切换 完全在用户空间完成由运行时系统的线程切换函数处理 保存当前线程状态CPU 寄存器、栈指针到线程的私有堆栈。选择新线程根据调度算法从就绪队列中选取。加载新线程状态从堆栈恢复寄存器、更新栈指针和程序计数器。 优势线程的切换无须进入内核切换操作简单且速度极快。 系统资源 进程是利用OS提供的系统调用来请求系统资源的系统调用通过软中断(如tap)机制进入OS内核由内核来完成相应资源的分配。用户级线程是不能利用系统调用的。当线程需要系统资源时是将该要求传送给运行时系统由后者通过相应的系统调用来获得系统资源。 内核控制线程, 又称为轻型进程 LWP(Light Weight Process) 本质介于 用户级线程ULT 和 内核级线程KLT 之间的桥梁用于赋予 ULT 部分内核支持线程的能力。 特点 每个 LWP 拥有独立的 TCB栈、寄存器状态、优先级但共享进程资源如内存、文件描述符。通过系统调用访问内核与内核级线程类似但由用户线程运行时系统动态绑定。通过 LWPULT 获得与内核通信的能力如 I/O 请求。 LWP 的核心机制: LWP 线程池缓冲池 背景用户级线程可能数量庞大如协程池而内核无法直接管理 ULT。 解决方案进程维护一个 LWP 池数量远少于 ULT动态分配给 ULT 使用。 工作方式 当一个 ULT 需要访问内核如系统调用它必须绑定到一个 空闲的 LWP。如果 LWP 池耗尽例5 个 ULT 请求 I/O但仅有 4 个 LWP则超出的 ULT 必须等待。 LWP 与内核线程的关系 LWP一对一绑定到内核级线程KLT 内核只能看到 LWP即 KLT无法感知 ULT 的存在。调度单位是 LWP内核按 LWP 分配 CPU 时间片。 ULT 通过 LWP 间接访问内核当 ULT 执行系统调用时需绑定到 LWP由 LWP 代理请求内核。 阻塞 在内核级线程执行操作时如果内核级线程发生阻塞则与之相连接的多个LWP也将随之阻塞进而使连接到 LWP 上的用户级线程也被阻塞。如果进程中只包含了一个LWP该进程实际上也应阻塞。如果在一个进程中含有多个LWP则当一个LWP阻塞时进程中的另一个LWP可继续执行。即使进程中的所有LWP全部阻塞进程中的线程也仍然能继续执行只是不能再去访问内核。
2.8.3 线程的创建和终止
1、线程的创建
应用程序在启动时通常仅有一个线程在执行人们把线程称为“初始化线程”主要功能是用于创建新线程。在创建新线程时需要利用一个线程创建函数(或系统调用)并提供相应的参数——如指向线程主程序的入口指针、堆栈的大小以及用于调度的优先级等。在线程的创建函数执行完后将返回一个线程标识符供以后使用。
2、线程的终止
线程终止的两种情况
正常终止 线程主动完成任务后调用终止函数如 pthread_exit退出。 强制终止 线程因异常如段错误、未捕获信号或被其他线程终止如 pthread_cancel。
线程终止后的资源处理
资源不会立即释放 线程终止后其占用的资源如栈、寄存器状态、线程描述符可能被保留。需其他线程显式调用分离函数如 pthread_detach才能释放资源。 未分离的线程可被复用 其他线程可通过连接join操作获取已终止线程的状态并回收资源。若线程未被分离其资源会一直保留直到被连接pthread_join。
系统线程的特殊性
长期运行的线程
某些系统线程如内核守护线程一旦启动会持续运行不被显式终止。通常由操作系统管理用户无法直接干预其生命周期。
线程连接Join机制
作用允许一个线程等待另一个线程终止并获取其退出状态。阻塞与非阻塞 若目标线程仍在运行调用 pthread_join 的线程会阻塞直到目标线程终止。若目标线程已终止调用线程立即继续执行并回收资源。 连接后资源释放成功连接后目标线程的资源会被系统回收。✅ pthread_join 是唯一获取线程返回值的方式如果不关心返回值可以传 NULL。只有 非分离non-detached线程 才能被 join
分离Detach机制
作用显式声明线程终止后自动释放资源无需其他线程连接。使用场景如果 不关心线程的返回值并且 希望线程结束后自动释放资源可调用 pthread_detach 避免资源泄露。不可逆性线程一旦**被分离**不能再通过 join 连接。
关键函数对比
操作函数POSIX线程效果终止线程pthread_exit线程主动退出资源保留到被连接或分离。强制终止线程pthread_cancel请求终止目标线程终止行为取决于线程的取消状态延迟或异步。等待线程终止并回收pthread_join阻塞调用者直到目标线程终止回收资源。分离线程pthread_detach线程终止后自动释放资源无需连接。
2.8.4 线程的状态与转换 组织与控制 参考
教材 计算机操作系统第四版 (汤小丹) (Z-Library).pdf
视频 王道计算机考研 操作系统
博客 哲学家进餐
