若可blog

一个有趣的地方

操作系统笔记 – 进程

by · Published · Updated

2.1 进程的概念

2.1.1 程序顺序执行的特征

在早期的单道程序工作环境中，内存中只有一个作业的程序。一个作业完成了，后一个作业才进入内容，并得以执行。各个作业的程序都是一个语句一个语句地按顺序构成的。如果系统中只有一个作业，那么其程序执行时就从前到后一步一步地计算下去。前面的工作完成了，才做后面的事情，就像工厂生产中流水线加工方式一样。这种程序设计方式叫做顺序程序设计。这种顺序程序活动具有顺序性、封闭性和可再现性三个主要特点。

  • 顺序性是指程序所规定的每个动作都在上一个动作结束后才开始
  • 封闭性是指只有程序本身的动作才能改变程序的运行环境
  • 可再现性是指程序的执行结果与程序的运行速度无关

2.1.2 程序并发执行及其特征

2.1.2.1 概念

单道程序系统具有资源浪费、效率低、作业周转时间长等明显缺点，所以在现代计算机系统中几乎不再采用这种技术，而广泛采用多道程序设计技术。多道程序设计是指两个或更多各程序同时在系统中存在并得到运行。在此情况下，系统中各部分的工作方式不再是单纯串行，而是并发执行。

多道程序设计具有提高系统资源利用率和增加作业吞吐量的优点。
作业吞吐量是指在给定时间间隔内所完成作业的数量，如每小时20个作业。举一个极端化的例子：假设有两道作业A和B都在执行，每个作业都是执行一秒钟，然后等待一秒钟，进行数据输入，随后再执行，再等待，如此循环，一直重复60次。如果按照单道方式，先执行A，再执行B，两个作业都执行完共需要4分钟，CPU利用率为50%。如果采用多道程序技术来执行A和B，可以在CPU上交替执行A和B，理想情况下CPU利用率为100%，执行完共需2分钟。

2.1.2.2 特征

  1. 失去封闭性
    • 并发执行的多个程序共享系统中的资源，因而这些资源的使用状态不再仅由某个程序所决定，而是收到并发程序的共同影响。多个程序并发执行时的相对速度时不确定的，每个程序都会经历“走走停停”的过程。但何时发生控制转换并非完全由程序本身决定，而是与整个操作系统当时所处的环境有关，因此具有一定随机性。
  2. 程序与计算不再一一对应
    • 程序是指令的有序集合，是静态概念；而计算式指令序列在处理机上的执行过程，是动态概念。在并发执行过程中，一个共享程序可被多个用户作业调用，从而形成多个计算。
  3. 并发程序在执行期间相互制约
    • 并发程序的执行过程具有“执行-暂停-执行”的活动规律，各程序活动的工作状态与所处的系统环境密切相关。系统中很多资源具有独占性质，即一次只让一个程序使用，如打印机等。这就使裸机上彼此独立的程序由于共用这类独占资源而形成相互制约的关系——在顺序执行时可连续执行的程序，在并发执行时却不得不暂停下来，等待其他程序释放自己所需的资源。

2.1.3 进程概念的引入和定义

2.1.3.1 进程概念的引入

所有现代计算机可以同时做很多事情，当运行一个用户程序时，计算机可以从磁盘上为另一个用户程序读取数据，并且可以在终端或打印机上显示第三个用户程序的结果。

由于多道程序并发时共享系统资源，共同决定这些资源的状态，因此系统中各程序在执行过程中就出现了相互制约的新关系，程序的执行出现“走走停停”的新状态。而程序本身时机器能够翻译或者执行的一组动作或指令，或者写在纸面上，或者存放在磁盘等介质上的，是静止的。

用程序这个静态概念已经不能如实反映程序并发执行过程中的这些特征，因此引入进程（Process）这一概念来描述程序动态执行过程的性质。

2.1.3.2 进程的定义

进程（或任务）是操作系统的最基本、最重要的概念之一，是对正在运行程序的抽象。

进程最根本的属性是动态性和并发性。将进程定义为程序在并发环境中的执行过程。

进程和程序有着密切的关系，但又是两个完全不同的概念。

  1. 程序是静态、被动的概念，本身可以作为一种软件资源长期保存
    • 进程是程序的一次执行过程，是动态、主动的概念，有一定的生命期，会动态地产生和消亡
  2. 传统的进程是一个独立运行的单位，能与其他进程并发执行。进程是作为资源申请和调度单位存在的
    • 通常的程序时不能作为一个独立运行的单位而并发执行的
  3. 程序和进程无一一对应关系。一个程序可被多个进程共用，一个进程在其活动中又可顺序地执行若干程序。
  4. 各个进程在并发执行过程中会产生相互制约关系，造成各自前进速度的不可预测性
    • 程序本身时静态的，不存在这种异步特征

2.1.3.3 进程的特征

  1. 动态性
    • 进程是程序的执行过程，有产生和消亡，有活动和停顿，可以处于不同的状态
  2. 并发性
    • 多个进程的实体能存在于同一内存中，在一段时间内都得到运行，这样就使得一个进程的程序与其他进程的程序并发执行了
  3. 调度性
    • 进程是系统中申请资源的单位，也是被调度的单位。操作系统中有很多调度程序，他们根据各自的策略调度合适的进程为其运行提供条件
  4. 异步性
    • 各进程向前推进的速度是不可预知的，即以异步方式运行，这造成进程之间相互制约，使程序执行失去再现性。为保证个程序的协调运行，需要采取必要的措施。
  5. 结构性
    • 进程有一定的的结构，它由程序段、数据段和控制结构（如进程控制块）等组成。程序规定了该进程所要执行的任务，数据是程序操作的对象，而控制结构中含有进程的描述信息和控制信息，是进程中最关键的组成部分

2.2 进程状态描述及组织方式

2.2.1 进程的状态及其转换

2.2.1.1 进程的状态

通常在操作系统中，进程至少要有三种基本状态。这些状态是处理机挑选进程运行的主要因素，所以又称为进程控制状态。这三种基本状态是：运行态、就绪态和阻塞态（或等待态）。

  1. 运行态（Running）
    • 运行态是指当前进程已经分配到CPU，它的程序正在处理机上执行时的状态。处于这种状态的进程的个数不能大于CPU的数目。
  2. 就绪态（Ready）
    • 就绪态是指进程已具备运行条件，但因为其他进程正占用CPU，所以暂时不能运行而等待分配CPU的状态。一旦把CPU分配给它，它立即就可以允许。在操作系统中，处于就绪态的进程数目可以是多个。
  3. 阻塞态（Blocked）
    • 阻塞态是指进程音等待某种事件发生而暂时不能运行的状态。处于阻塞态的进程尚不具备运行条件，即使CPU空闲，也无法运行。系统中处于这种状态的进程可以有多个。

在很多系统中又增加了两种基本的进程状态，即新建态和终止态。

  1. 新建态（New）
    • 新建态是指进程刚被创建，尚未放入就绪队列时的状态。处于这种状态的进程时不完全的。当创建新进程的所有工作完成后，操作系统就把该进程送入就绪队列中。
  2. 终止态（Terminated）
    • 终止态是指进程完成自己的任务而正常终止或在运行期间由于出现某些错误和故障而被迫中止（非正常中止）时所处的状态。处于终止态的进程不能再被调度执行，下一步必然会被系统撤销，进而从系统中永久消失。

2.2.1.2 进程状态的转换

进程在其生存期间不断发生状态转换——从一种状态变为另一种状态。一个进程可以多次处于就绪态和运行态，也可以多次处于阻塞态，但可能排在不同的阻塞队列上。

  1. 就绪->运行
    • 处于就绪态的进程被调度程序选中，分配到CPU后，该进程的状态就由就绪态变为运行态。
  2. 运行->阻塞
    • 正在进行的进程因为某种条件未满足而放弃对CPU的占用，例如，该进程要求读入文件中的数据，在数据读入内存之前，该进程无法继续执行下去，它只好放弃CPU，等待读文件这一事件的完成。这个进程的状态就由运行态变为阻塞态。
  3. 阻塞->就绪
    • 处于阻塞态的进程所期待的事件发生了，此时该进程就从阻塞队列中出来，进入到就绪队列中，然后和就绪队列中的其他进程竞争CPU。
  4. 运行->就绪
    • 正在运行的进程如果用完了本次分配给它的CPU时间片，他就得从CPU上退下来，暂停运行。该进程的状态由运行态变为就绪态，以后进程调度程序选中它，它就又可以继续运行了。

2.2.2 进程的组成

2.2.2.1 进程映像

进程的活动是通过在CPU上执行一系列程序和对相应数据进行操作来体现的，因此，程序和数据是组成进程的实体。但二者仅是静态的文本，没有反映其动态特性。因此，还需要一个数据结构来描述进程当前的状态、本身的特性、对资源的占用及调度信息等，这种数据结构被称为进程控制块（Process Control Block，PCB）。此外，程序执行过程必须包含一个或多个栈，用来保存过程调用和相互传送参数的踪迹。栈按照后进先出（LIFO）的方式操作。

2.2.2.2 进程控制块的组成

进程控制块有时也被称为进程描述块（Process Descriptor），它是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，是系统识别和控制进程的依据。

一般来说，进程控制块应包括以下内容：

  1. 进程名
    • 它是唯一的标志对应进程的一个标识符或数字。
  2. 特征信息
    • 包括是系统进程还是用户进程，进程实体是否常驻内存等。
  3. 进程状态信息
    • 表明该进程的执行状态，是运行态、就绪态还是阻塞态等。
  4. 调度优先权
    • 表示进程获取CPU的优先级别。当多个就绪进程竞争CPU时，系统一般让优先权高的进程先占CPU。
  5. 通信信息
    • 反映该进程与哪些进程有什么样的通信关系。
  6. 现场保护区
    • 当对应进程由于某种原因放弃使用CPU时，需要把他的一部分与运行环境有关的信息保存起来，以便在重新获得CPU后能回复正常运行。
  7. 资源需求
    • 分配和控制方面的信息，如进程所需要或占有的I/O设备、磁盘空间、数据区等。
  8. 进程实体信息
    • 指出该进程的程序和数据存储情况，在内存或外存中的地址、大小等。
  9. 族系关系
    • 反映父子进程的隶属关系。
  10. 其他信息
    • 如文件信息、工作单元等。

2.2.2.3 进程控制块的作用

进程控制块是进程中最关键的组成部分。每个进程都有唯一的进程控制块。操作系统根据PCB对进程实施控制和管理。在进程的整个生命期中，系统对进程的控制和管理是通过PCB实现的。

进程的动态、并发等特征是通过PCB表现出来的。如果没有进程控制块，则多道程序环境中的程序和数据是无法实现并发的。

2.2.3 进程组织方式

2.2.3.1 线性方式

线性方式最简单，最容易实现。操作系统预先确定整个系统中同时存在的进程的最大数目，如n，然后静态分配空间，把所有进程的PCB都放在这个表中。这种方式存在的主要问题是：限定了系统中同时存在的进程的最大数目。当很多用户同时上机是，会造成无法为用户创建新进程的情况。更严重的缺点是：在执行CPU调度时，为选择合理的进程投入运行，经常要对整个表进行扫描，降低了调度效率。

2.2.3.2 链接方式

链接方式是经常采用的方式，其原理是：按照进程的不同状态分别放在不同的队列中。在单CPU情况下，处于运行态的进程只有一个，可以用一个指针指向它的PCB。处于就绪态的进程可以是若干个，他们排成一个（或多个）队列，对PCB结构内部的拉链指针把同一队列的PCB连接起来。就绪队列指针指向该队列的第一个PCB，最后一个PCB的拉链指针置为0，表示结尾。CPU调度程序把第一个PCB从该队列中摘下，令其投入运行。新加入就绪队列的PCB连在队列尾部，按照先进先出的策略。阻塞队列可以有多个，各对应不同的阻塞原因。当满足某个等待条件时，则可以把对应阻塞队列上的PCB送到就绪队列中，正在运行的进行如出现缺少某些资源而未能满足的情况，就变为阻塞态。

2.2.3.3 索引方式

索引方式是利用索引表记载相应状态进程的PCB地址，也就是说，系统建立几张索引表，各对应进程的不同状态，如就绪索引表、阻塞索引表等。状态相同的进程的PCB组织在同一索引表中，每个索引表的表目中存放该PCB的地址。各索引表在内存的起始地址放在专用的指针单元中。

2.3 进程管理和有关命令

2.3.1 进程图和进程管理

2.3.1.1 进程图（Process Graph）

同人类的族系一样，系统中众多的进程也存在族系关系：由父进程创建子进程、子进程在创建子进程，如此进行下去，从而构成一棵树形的进程族系图。

开机后，首先引导操作系统，把它装入内存。之后生成第一个进程，（在UNIX中称作0^#^进程），由它创建1^#^进程以及其他核心进程；然后1^#^进程又为每个终端创建命令解释进程（Shell进程）；用户输入命令后又创建了若干进程。这样便形成了一棵进程树。

树的根节点（即0^#^）是所有节点的祖先。上一层节点对应的进程是与其直接相连的下一层节点对应进程的父进程。

2.3.1.2 进程创建

一个进程可以动态地创建新进程，前者称作父进程，后者称作子进程。引发创建进程的事件通常是调度新的批作业、交互式用户登录、操作系统提供服务和现有进程派生新进程。

创建新进程时要执行创建进程的系统调用（如UNIX/Linux系统中的fork），操作过程有如下四步：

  1. 申请一个空的PCB。从系统的PCB表中找出一个空闲的PCB项，并指定唯一的进程标识符PID。
  2. 为新进程分配资源。根据调用者提供的所需内存大小，为新进程分配必要的内存空间，存放其程序和数据及工作区。
  3. 初始化新进程的PCB。根据调用者提供的参数，初始化新进程的PCB。这些参数包括新进程名（外部标识符）、父进程标识符、处理机初始状态、进程优先级、本进程开始地址等。一般将新进程状态设置为就绪态。
  4. 将新进程加到就绪队列中。一个进程派生新进程后，有两种可能的执行方式：
    1. 父进程和子进程同时（并发）执行。
    2. 父进程等待它的某个或者全部子进程终止
      • 建立子进程的地址空间也有两种可能的方式
    3. 子进程复制父进程的地址空间
    4. 把程序装入子进程的地址空间

2.3.1.3 进程终止

一旦系统中出现要求终止进程的事件后，便调用进程终止原语。终止进程的主要操作过程：

  1. 从系统的PCB表找到指定进程的PCB。若它正处于运行态，则立即终止该进程的运行。
  2. 回收该进程所占用的全部资源。
  3. 若该进程还有子孙进程，则还要终止其所有子孙进程，回收它们所占用的全部资源。
  4. 释放被终止进程的PCB，并从原来队列中摘走。

2.3.1.4 进程阻塞

正在运行的进程同故宫调用阻塞原语（如UNIX/Linux系统的sleep），主动地阻塞自己。进程阻塞的过程如下：

  1. 立即停止当前进程的执行。
  2. 将现行进程的CPU现成送到该进程的PCB现场保护区中保存起来，以便将来重新运行时恢复此时的现场。
  3. 把该进程PCB中的现行状态由运行改为阻塞，把它插入具有相同事件的阻塞队列中。
  4. 转到进程调度程序，重新从就绪队列中挑选一个合适的进程投入运行。

2.3.1.5 进程唤醒

当阻塞进程所气态的事件出现时，与阻塞进程相关的进程调用唤醒原语（如UNIX/Linux系统的wakeup），将等待该事件的进程唤醒。可见，阻塞进程不能唤醒自己。唤醒原语的执行过程是：

  1. 首先把被阻塞进程从相应的阻塞队列中摘下
  2. 将现行状态改为就绪态，然后把该进程插入到就绪队列中。
  3. 如果被唤醒进程比运行进程的优先级更高，则设置重新调度标志

阻塞原语和唤醒原语恰好是一对相反的原语，调用前者是自己去睡眠，调用后者是把“别人”唤醒。使用时也要承兑，前面有睡眠的，后面就要有唤醒的，否则，前者就要“长眠”了。

2.3.1.6 进程映像的更换

子进程被创建后，通常处于就绪态。在有些系统（如UNIX/Linux）中，由于创建子进程时是把父进程的映像赋值给子进程，所以父、子进程的映像基本相同。如果子进程不改变自己的映像，就必然重复父进程的过程，这不是我们希望的。

改变进程映像的工作很复杂，主要过程是：

  1. 释放子进程原理啊的程序和数据所占用的内存空间
  2. 从磁盘上找到子进程所要执行的程序和数据
  3. 分配内存空间，装入新的程序和数据
  4. 为子进程创建初始的运行环境——主要是对各个寄存器初始化，返回到用户态，运行该进程的程序

2.3.2 Linux进程管理

2.3.2.1 Linux进程状态

在Linux系统中，进程有以下五种状态：

  1. 运行态（TASK_RUNNING）。此时，进程正在运行，或准备运行（就绪态）。当前进程由运行指针所指向。
  2. 可中断等待态（TASK_INTERRUPTIBLE）。此时进程在“浅度”睡眠——等待一个事件的发生或某种系统资源，他能够被信号或中断唤醒。
  3. 不可中断等待态（TASK_UNINTERRUPTIBLE）。进程处于“深度”睡眠的等待队列，不能被信号或中断唤醒，只有所等待的资源得到满足时，才能被唤醒。
  4. 停止态（TASK_STOPPED）。通常由于接收一个信号导致进程停止。正在被调试的进程可能处于停止态。
  5. 僵死态（TASK_ZOMBIE）。由于某些原因，进程被终止了，但是该进程的控制结构仍然保留着。

2.3.2.2 进程的模式和类型

在Linux系统中，进程的执行模式分为用户模式和内核模式。在内核模式下运行的进程可以执行及其的特权指令，而且此时该进程的运行不受用户干预，即使是root用户也不能干预内核模式下进程的运行。

2.3.2.3 Linux进程结构

  1. task_struct结构
    • 它相当于进程控制块。系统中有一个进程向量数组task，长度默认值是512B，该数组的元素是指向task_struct结构的指针。在创建新进程时，Linux就从系统内存中分配一个task_struct结构，并把它的首地址加入task数组。task_struct结构包含下列信息：
      1. 进程状态
      2. 调度信息
      3. 标识符
      4. 内部进程通信
      5. 链接信息
      6. 时间和计时器
      7. 文件系统
      8. 虚拟内存
      9. 处理器信息
  2. 进程系统堆栈
    • 在linux系统中，每个进程都有一个系统堆栈，用来保存中断现场和进程进入内核模式后执行子程序嵌套调用的返回现场信息。每个进程的系统堆栈和task_struct数据结构之间存在紧密联系。
    • 另外，系统空间堆栈的大小是静态确定的，而用户空间堆栈可以在运行时动态扩展。

2.3.3 有关进程操作的命令

  1. ps命令
    • ps [option]
    • ps -aux
  2. kill命令
    • 一般来说，对于前台进程可以使用Ctrl+C终止。但是对于一个后台进程就必须使用kill命令来终止
    • kill [-s|-p] [-a] 进程号
  3. sleep命令
    • sleep命令的功能是使进程暂停执行一段时间
    • sleep 时间值

2.4 进程间的同步与互斥

进程具有动态性和并发性。如果对进程的活动不加约束，就会使系统出现混乱。例如数据处理的结果不唯一。为保证系统中所有进程都能正常活动，使程序的执行具有可再现性，就必须提供进程同步机制。

进程间的相互关系主要表现为三种形式：互斥、同步和通信。

2.4.1 进程间的关系

2.4.1.1 同步

同步进程通过共享资源来协调活动，在执行时间的次序上有一定的约束。虽然进程彼此不直接知道对方的名字，但知道对方的存在的作用。在协调动作的情况下，多个进程可以共同完成一项任务。

2.4.1.2 互斥

在计算机系统中，进程间的关系通常也是与此类似的互斥关系，这是由于进程共享某些资源而引起的。在逻辑上，进程间本来完全独立，毫无关系，只是由于竞争同一个资源而相互制约。这种互斥关系不同于前面讲的同步关系，他们的运行不具有时间次序的特征，谁先向系统提出申请，谁就先执行。

2.4.2 竞争条件和临界区

两个或多个进程同时访问和操纵同样数据时，最后的执行结果取决于进程运行的精确时序，这种情况称作竞争条件。要避免这种情况，关键是要找到某种途径来阻止一个以上的进程同时使用这种资源。也就是说，多个进程共享这种资源时，必须互斥执行。我们把这类共享资源称为临界资源（Critical Recourse）。在每个进程中访问临界资源的那段程序叫做临界区（Critical Section），简称CS区。

进程互斥进入临界区都要遵循一种通用模式：进入前要申请，获准后方可进入；执行后要退出，然后才可以执行其他代码。

要进入临界区的若干进程要遵循以下准则：

  1. 任何两个进程不能同时处于其临界区。
  2. 进程运行的速度具有不确定性。
  3. 应保证进入临界区的进程能不受干扰地运行。
  4. 不得使进程无限期地等到进入临界区。

2.4.3 进程同步机制

2.4.3.1 实现互斥方式

从实现机制方面来说，分为硬件方法和软件方法

  1. 利用硬件方法解决进程互斥问题
    • 有禁止中断和专用机器指令两种常见方式。
    • 禁止中断是使每个进程在进入临界区之后立即关闭所有的中断，在它离开临界区之前才重新开放中断。由于禁止中断，时钟中断也被禁止，就不会把CPU切换到另外的进程。弊端是：一旦某个进程关闭中断后，如果它不再开放中断，那么系统可能会因此而终止。
    • 设置专用机器指令是另一种方法，很多计算机都有一条名为TSL（Test and Set Lock，测试并上锁）的指令。它把内存字LOCK的内容读到寄存器RX中，然后在该地址单元中存入一个非零值。在这条指令完成之前，其他进程不能访问该单元。利用TSL可能会出现“忙式等待”——如果前面已有一个进程进入临界区，后者就不断利用TSL指令进行测试并等待前者开锁。
  2. 原语操作
    • 操作系统在完成某些基本操作时，往往利用原语操作来实现。所谓原语（primitive）就是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。在许多机器中规定，执行原语操作时要屏蔽中断，以保证其操作的不可分割性。原语操作也被称作“原子操作”。
  3. 利用软件方法解决进程互斥问题
    • 为解决进程互斥进入临界区的问题，可为每类临界区设置一把锁，该锁有打开和关闭两种状态。进程执行临界区程序的操作按照以下步骤执行：
      1. 关锁。先检查锁的状态，如果为关闭状态，则等待其打开；如果以及打开，则将其关闭，继续执行以下操作。
      2. 执行临界区程序。
      3. 开锁。将锁打开，退出临界区。

2.4.3.2 信号量及P、V操作原语

信号量及信号量上的P操作和V操作时E.W.Dijkstra在1965年提出的一种解决同步、互斥问题的更通用方法。
结构型信号量（又称计数信号量，简称信号量）一般是由两个成员组成的数据结构，其中一个成员是整型变量，表示该信号量的值，另一个是指向PCB的指针。当多个进程都等待同一信号量时，他们就排成一个队列，由信号量的指针项指向该队列的头，而PCB队列时通过PCB本身包含的指针项进行链接的，队尾为0。
信号量的值与相应资源的使用情况有关。当它的值大于0时，则表示当前可用资源的数量；当他的值小于0时，其绝对值表示等待使用该资源的进程个数。
对信号量的操作由如下严格限制：

  1. 信号量可以赋初值，且初值非负数。
  2. 在使用过程中，信号量的值可以修改，但只能通过P操作和V操作来访问，不允许通过其他方式查看和操纵信号量。

P操作最初源于荷兰语proberen，表示测试；V操作源于荷兰语verhogen，表示增加。

2.4.4 信号量的一般应用

利用信号量机制可以解决并发进程的互斥和同步问题。

2.4.4.1 用信号量实现进程互斥

我们可以用P、V操作实现对分配表的互斥操作。
使用P、V操作时要注意两点

  1. 每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区，后做V，退出临界区。
  2. 互斥信号量mutex的初值一般为1。

2.4.4.2 用信号量实现进程简单同步

  1. 分析进程间的制约关系，确定信号量种类。在保持进程间有正确的同步关系的情况下，确定哪个进程应先执行，哪些进程后执行，彼此间通过什么资源（信号量）进行协调，从而明确要设置哪些信号量。
  2. 信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。
  3. 同一信号量的P、V操作要“成对”出现，但它们分别出现在不同的进程代码中。

2.4.4.3 生产者-消费者问题

生产者-消费者问题是其中一个有代表性的进程同步问题。它是同步问题的一种抽象，是进程同步、互斥关系方面的一个典型。这个问题可以表述为：一组生产者进程和一组消费者进程（假设每组有多个进程）通过缓冲区发生联系。生产者进程将生产的产品（数据、信息等抽象为产品）送入缓冲区，消费者们从中取出产品。假设缓冲区有N个，不妨设想成一个环形缓冲池。缓冲区放有产品，否则为空。

为使这两类进程协调工作，防止盲目的生产和消费，它们应该满足如下同步条件：

  1. 任一时刻所有生产者存放产品的单元数不能超过缓冲区的总容量（N）
  2. 所有消费者取出产品的总量不能超过所有生产者当前生产产品的总量。

假设缓冲区的编号是0至N-1，in和out分别是生产者进程和消费者进程使用的指针，指向下面可用的缓冲区，初值都是0。
为使得两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。

  • full：表示存有产品的缓冲区数，其初值为0
  • empty：表示可供使用的缓冲区数，其初值为N
  • mutex：互斥信号量，初始值为1，表示各进程互斥进入临界区，保证任何时候都只有一个进程使用缓冲区。

生产者进程Producer

while (True):
    P(empty)
    P(mutex)
    # 产品送往buffer(in)
    in = mod(in + 1, N)
    V(mutex)
    V(full)

消费者进程Consumer

while (True):
    P(full)
    P(mutex)
    # 从buffer(out)中取出产品
    out = mod(out + 1, N)
    V(mutex)
    V(empty)

在生产者-消费者问题中应该注意以下三点：

  1. 在每个程序中必须先做P(mutex)，后做V(mutex)，两者要成对出现。夹在两者中间的代码段就是该进程的临界区。
  2. 对同步信号量full和empty的P、V操作同样必须成对出现，但他们分别位于不同的程序中
  3. 无论在生产者进程中，还是在消费者进程中，两个P的操作次序不能颠倒：应先执行同步信号量的P操作，然后执行互斥信号量的P操作，否则可能造成进程死锁。

2.5 进程通信

信号量上的P、V具有很强的功能，一个进程对某信号量的操作可使其他相关进程获得一些信息，从而决定了它们能否进入临界区执行下去。但是信号量能传达的信息量是非常有限的，通信的效率低。为了解决进程间消息通信问题，人们研究和设计了高级的通信机构。

进程通信是指进程间的信息交换。各进程在执行过程中为合作完成一个共同的任务，需要协调步伐、交流信息。进程间交换的信息量可多可少，可以少到仅是一个状态或数值，也可以多到可交换成千上万个字节的数据。

高级进程的通信方式有很多种，大致分为三类：共享存储器、管道文件和消息传递。

2.5.1 共享存储器方式

共享存储器方式是在内存中分配一片空间作为共享存储去。需要进行通信的各个进程把共享存储区附加到自己的地址空间中，然后像进行正常的操作一样对共享区中的数据进程进行读或写操作。如果用户不需要某个共享存储区，则可以把它取消。通过对共享存储区的访问，相关进程间就可以传出大量数据。

2.5.2 管道文件方式

管道文件也称作管道线，它是连接两个命令的一个打开文件。一个命令用于向该文件中写入数据，称作写者（Writer），另一个命令用于从该文件中读出数据，称作读者（Reader）。例如，在Linux系统中，下述命令行可以实现两个命令间的通信

who | wc -1

写者和读者按先入先出（FIFO）的方式传输数据，由管道通信机制协调两者的动作，提供同步、互斥等功能。

在UNIX系统中，命令是通过进程实现的，所以读者和写着又分别称作读进程和写进程。

2.5.3 消息传递方式

消息传递方式是以消息（message）为单位在进程间进行数据交换。它有两种实现方式：

  1. 直接通信方式。发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。
  2. 间接通信方式。发送进程将消息送到称作信箱的中间设施中，接收进程从信箱中取得消息。这种通信方式也称做信箱通信方式。

2.5.3.1 直接通信方式

消息缓冲通信的设计思想是：由系统管理一组缓冲区，其中每个缓冲区可以存放一个消息（即一组信息）。当进程要发送消息时，先要向系统申请一个缓冲区，然后把消息写进去，接着把该缓冲区连到接收进程的一个消息队列中，并用V操作通知接收者，接收进程可以在适当的时候从消息队列中取出信息，并释放该缓冲区。

消息缓冲区一般包含下列几种信息：

  1. name：发送消息的进程名或标识号
  2. size：消息长度
  3. text：消息正文
  4. next：下个缓冲区的地址

在采用消息通信机构的系统中，进程PCB中一般包含下列项目：

  1. mutex：消息队列操作互斥信号灯。消息队列是临界资源，不允许两个或两个以上的进程同时对它进行访问
  2. S~m~：表示接收消息计数和同步的信号灯，用于接收消息进程与发送信息进程进行同步，其值表示消息队列中的消息数目。
  3. P~m~：指向进程的消息队列中第一个缓冲区的指针。

2.5.3.2 信箱通信

信箱是实现进程通信的中间实体，可以存放一定数量的消息。发送进程将消息送入信箱，接收进程从信箱中取出发给自己的消息。
信箱是一种数据结构，在逻辑上可分为两个部分：信箱头——包括信箱名字、信箱属性（公用、私用或者共享）、信箱格状态等；信箱体——用来存放消息的多个信箱格。
消息在信箱中存放受到安全保护，得到核准的用户（进程）可以随时读取信息，而其他用户被拒绝访问信箱。
信箱可以动态创建和撤销。进程可以利用信箱创建原语来创建一个新信箱，创建时应给出信箱名字及其属性等，以及谁可以共享此信箱。不再使用信箱时，可用信箱撤销原语删除它。

发送进程要发送信息时，先判断该信箱的信箱格是否为空。若为空，则将消息送入，并置信箱格状态状态为满；否则重复测试。当信箱全满时，发送者挂起，直至有消息从信箱中取走。
接收进程要接受一个消息时，先判断信箱状态是否为满。若为满，表示有消息，则从中取走消息；否则若为空，则接收者挂起。

信箱可分为三类：

  1. 公用信箱：它由操作系统创建，系统中所有核准进程都可使用它——既可把消息送到该信箱，又可以从中取出发给自己的消息
  2. 共享信箱：它由某个进程创建，对它要指明共享属性以及共享进程的名字。信箱的创建者和共享这都可以从中取走发给自己的消息。
  3. 私有信箱：用户进程为自己创建的信箱。创建者有权从中读取消息，而其他进程（用户）只能把消息发送到该信箱。

2.6 管程

管程（Monitor）的定义是：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。

一个管程由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句4部分组成。

管程具有以下三个特性：

  1. 管程内部的局部数据变量只能被管程内定义的过程访问，不能被管程外面声明的过程直接访问。
  2. 进程要向进入管程，必须调用管程内的某个过程。
  3. 一次只能有一个进程在管程内执行，而其他调用该管程的进程都被挂起，等待该管程称为可用的，即管程能有效地实现互斥。

2.7 经典进程同步问题

2.7.1 读者-写者问题

读者-写者问题是一个著名的进程互斥访问有限资源的同步问题。例如，一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写操作。允许多个进程同时读该数据库，但是在任何时候如果有一个进程写（即修改）数据库，那么就不允许其他进程访问它——既不允许写，也不允许读。
显然，系统中的读者（进程）和写者（进程）各有多个，各个读者的执行过程基本相同。同样，各个写者的执行过程也基本相同。

以下是解决这个问题的一种算法：

读者

while True:
    P(rmutex)
    readcount += 1
    if readcount == 1:
        P(wmutex)
    V(rmutex)
    # 执行读操作
    P(rmutex)
    readcount -= 1
    if readcount == 0:
        V(wmutex)
    V(rmutex)
    # 使用读取的数据

写者

while True:
    P(wmutex)
    # 执行写操作
    V(wmutex)

2.7.2 哲学家进餐问题

哲学家进餐问题（The Dining Philosophers Problem）的同步问题，描述如下：
五位哲学家围坐在一张圆桌旁进餐，每个人面前有一只碗，各碗之间分别由一只筷子。每个哲学家都在用两根筷子吃饭前肚子进行思考，感到饥饿时遍试图用其左、右最靠近它的筷子，但他可能一根也拿不到。他不能强行从邻座手中拿过筷子，而且必须用两根筷子进餐；餐毕，要把筷子放回原处并继续思考问题。

以下是一种算法。设立一个整数型数组state，用来保存各位哲学家的状态：进餐（EATING）、思考（THINKING）或者饥饿（HUNGRY）。每位哲学家仅当其左右邻座都不进餐时，他才能进餐。第i位哲学家的两位邻座由宏LEAF和RIGHT定义：如果i时2，LEAF是1，RIGHT是3。
程序中使用一个信号量数组S，每个哲学家对应其中一个元素。如果感到饥饿的哲学家所用的筷子正被别人占用着，他就等待（阻塞）。

#define N 5
#define LEFT (i+N-1)%N
#define RIGHT (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2

typedef struct{
    int value;
    struct PCB *list;
}semaphore;

int state[N];
semaphore mutex = 1;
semaphore s[N];

void philosopher(int i){
    while (TRUE){
        think();
        take_chopstick(i);
        eat();
        put_chopstick(i);
    }
}

void take_chopstick(int i){
    P(mutex);
    state[i]=HUNGRY;
    test(i);
    V(mutex);
    P(s[i]);
}

void put_chopstick(int i){
    P(mutex);
    state[i]=THINKING;
    test(LEFT);
    test(RIGHT);
    V(mutex);
}

void test(int i){
    if (state[i]==HUNGRY && state[LEFT]!=EATING && state[RIGHT]!=EATING){
        state[i]=EATING;
        V(s[i]);
    }
}

2.7.3 打瞌睡的理发师问题

理发师问题是另一个经典的IPC（进程间通信）问题。故事是这一的：理发店里有一名理发师，还有一把理发椅和几把座椅，等待理发者可坐在上面。如果没有顾客来到，理发师就坐在理发椅上打盹。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在立法，该顾客就坐在椅子上排队；如果满座了，他就离开这个理发店。

理发师和每位顾客都分别是一个进程。理发师开始工作时，先看一看店内有无顾客：如果没有，他就在理发椅上打瞌睡；如果有顾客，他就为等待时间最久的顾客服务，且等待人数减一。

每位顾客进程开始执行时，先看看店内有无空位：如果没有空位，就不等了，离开理发店；如果有空位，则排队，等待人数加一；如果理发师在睡眠，则唤醒他工作。

以下是一种算法

#define CHAIRS 5
typedef struct{
    int value;
    struct PCB *list
}semaphore;

semaphore customers=0;
semaphore barbers=0;
semaphore mutex=1;
int waiting=0;

void barber(void){
    while (TRUE){
        P(customers);
        P(mutex);
        waiting--;
        V(barbers);
        V(mutex);
        cut_hair();
    }
}

void customer(void){
    P(mutex);
    if (waiting CHAIRS){
        waiting++;
        V(customers);
        V(mutex);
        P(barbers);
        get_haircut();
    } else {
        V(mutex);
    }
}

Tags:

You may also like...

发表回复

您的电子邮箱地址不会被公开。