操作系统 2.进程管理

进程管理涉及到进程调度、CPU分配等问题，是操作系统中最重要的部分之一

进程管理

进程的基本概念

程序的并发执行。程序的执行有两种方式：顺序执行和并发执行。

• 顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；
• 现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。

首先引入前驱图，再用前趋图表示程序的运行流程：前趋图是一个有向无循环图DAG(Directed Acyclic Graph)。

• 顺序执行：是指一个程序运行时独占整个系统资源, 处理机严格按照程序所规定的顺序进行操作。在一个程序段中，只有前面的一个操作执行完，才能进行后面一个操作。

  

  • 顺序性
  • 封闭性
  • 结果可再现性

• 并发执行：是指在一个时间段内，多个程序段在计算机系统中“一起”执行，若干程序段在执行时间上有重叠, 即一个程序段的执行过程中插入了其它程序的操作，称为并发执行。例如，在一个时间段内，一个CPU在为多道程序工作，而在某一个瞬间，一个CPU只能运行一道程序，它只是在多道程序中快速切换，给人以CPU“同时”运行几道程序的感觉。每个程序内部仍是按顺序执行，但是多个程序的执行过程是可以交叉的，这是一种伪并行，称之为并发执行。

  

  • 间断(异步)性
  • 失去封闭性
  • 失去可再现性
  • 相互作用和制约性

为了强调进程并发性和动态性的特点，将其定义为：进程是程序的一次执行，该程序可以与其它程序并发执行。

• 结构性：由程序+数据+进程控制块PCB组成了进程实体，其中PCB是进程存在的标志。
• 动态性：进程是进程实体的执行过程, 它由创建而产生, 由调度而执行,因某事件而暂停, 由撤销而消亡。
• 并发性：多个进程同时存于内存中,一起向前推进,并发执行。
• 独立性：进程是独立获得资源和独立调度的基本单位。
• 异步性：各进程都各自独立的不可预知的速度向前推进。

进程与程序的区别

• 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。

• 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。

• 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

• 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块PCB（即进程状态信息）。

• 进程的表示：程序 + 数据 + 进程控制块PCB

  • 程序：描述了进程所要完成的功能，是进程执行时不可修改的部分。
  • 数据集合：程序执行时所需要的数据和工作区，为一个进程专用，可修改。
  • 进程控制块PCB(Process Control Block)：包含了进程的描述信息和控制信息，是进程的动态特性的集中反映。

进程控制块PCB：为了对进程进行有效的控制和管理，系统为每一进程设置一个进程控制块，PCB是进程存在的唯一标志。PCB表常驻内存，属于系统空间，只有操作系统程序才能够访问，用户程序不得访问。通常PCB包含以下几类信息：

• 进程描述信息：进程标识名(Process ID)、进程名
• 进程控制信息：当前状态、优先级、程序和数据的地址、队列指针或链接字
• 资源占用信息：进程执行时除CPU外的资源的需求、分配和控制信息。
• CPU现场保护结构：它由处理机各种寄存器的内容所组成，该类信息使进程被中断后重新执行时能恢复现场从断点处继续运行。

PCB表的组织形式：PCB是一个线性表结构，系统中的PCB个数是有限的。常驻内存的。操作系统在内存专门开辟一个PCB表区，每个PCB是一片连续的存储单元。常用的组织方式有2种

• 链接方式：用PCB表中的队列指针项将具有相同状态的进程的PCB表链接起来，这样PCB表就形成就绪队列、空闲队列及阻塞队列等。其中，空闲队列是一个，而就绪队列与阻塞队列可以是多个。也可以将不同优先级的进程的PCB表排入不同的就绪队列中。

  

• 索引方式：根据进程的状态，在内存中建立相应的索引表，系统中的某些固定单元保存各索引表的首地址。各索引表的表目中记录相应状态的PCB表的首地址。

  

进程的三种基本状态及其转换

• 运行态（Running）：当一个进程在处理机上运行时，则称该进程处于运行状态。

• 就绪态（Ready）：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。

• 阻塞态（Blocked）：当一个进程正在等待某一事件发生（例如请求I／O而等待I／O完成等）而暂时停止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。注意与就绪状态的不同在于即使处理机处于空闲状态也无法运行。

• ① 就绪→运行：调度程序选择一个新的进程运行

• ② 运行→就绪：运行进程用完时间片被中断或在抢占调度方式中,因为一高优先级进程进入就绪状态

• ③ 运行→阻塞：进程发生I/O请求或等待某事件时

• ④ 阻塞→就绪：当I/O完成或所等待的事件发生时

• 转化如图

  

  

• 细分的进程调度状态——挂起状态：由于终端用户及操作系统的需要(排除故障或为系统减负)，为了能够将指定进程暂时静止下来，增加了静止阻塞 (阻塞挂起) 和静止就绪 (就绪挂起)态，原阻塞和就绪改称为活动阻塞和活动就绪状态。

  • ①运行或活动就绪→静止就绪，活动阻塞→静止阻塞 通过挂起操作(suspend)。

  • ②静止就绪→活动就绪, 静止阻塞→活动阻塞 通过激活操作(activate)。

  • ③静止阻塞→静止就绪 当等待的事件发生时。

  • 如图

    

    

进程的控制

• 处理机的执行状态
  • 系统态(核心态、管态)：有特权，能执行所有指令，能访问所有寄存器和存储区。
  • 用户态(目态、算态)：无特权，只能执行规定指令，只能访问指定的寄存器和存储区。
  • 用户程序运行在用户态，它不能执行OS指令不能访问OS区域，防止对OS的破坏。OS内核运行在系统态。进程控制包含在OS的内核（Kernel）中，它常驻内存，执行效率高。
  • 操作系统内核是系统硬件的首次延伸，通过执行各种原语操作来实现对进程的控制功能（创建、调度、通讯、撤销等）。

原语(Primitive)

由若干条机器指令构成的并用以完成特定功能的一段程序，而且这段程序在执行期间不允许中断。原语又称为“原子操作(Atomic Operation)”过程，作为一个整体而不可分割——要么全都完成，要么全都不做。

1）进程创建原语

• 引起创建进程的事件：用户登录、作业调度、提供服务、应用请求四类

• 进程图：允许进程创建子进程，子进程还可以创建自己的子进程，从而形成树型的进程家族。进程图是用于描述进程家族关系的有向图，子进程可以继承父进程所拥有的资源。

  

• 树型结构系统的优点：

  • 资源分配严格。祖先拥有进程家族的所有资源，子进程可在祖先进程所拥有的资源中进行分配、使用与归还。
  • 进程控制灵活。可根据需要给予进程不同的控制权力，而且可根据需要创建多个子进程并行工作，协同完成任务。
  • 进程层次清晰，关系明确。

• 进程的建立有两种方式：

  • 系统生成时就建立起一些系统进程。主要用于创建常驻内存的系统进程；
  • 经创建原语产生进程。主要用于创建非常驻的系统进程和用户进程。

• 进程的创建过程：一旦发现了要求创建新进程的事件，OS便调用创建原语, 按以下过程创建新进程。

  • 分配一个唯一的进程标识符,索取一个空白PCB；
  • 为新进程的程序和数据分配内存空间
  • 初始化进程控制块：初始化标识符信息(填入)、处理机的状态信息(指令指针,栈指针)和控制信息(状态,优先级…)
  • 设置相应的链接。如:把新进程加到就绪队列的链表中

2）进程撤消原语

• 进程何时中止

  • 正常结束：批处理系统中,进程已运行完成遇到 Halt 指令；分时系统中, 用户退出登录
  • 异常结束：本进程发生出错和故障事件；存储区越界、保护性错(如:写只读文件)、特权，指令错、非法指令(如:程序错转到数据区)、算术运算错、运行超时、等待超过时、I/O 失败、
  • 外界干预：操作系统干预、父进程请求、父进程终止

• 进程的终止过程：一旦发生终止进程的事件，OS便调用撤消原语，按以下过程终止该进程。

  • 从PCB中读取进程的状态；
  • 若进程处于执行态,应立即终止该进程的执行，并置调度标志为真（以便该进程终止后系统重新进行调度,将处理机分配给新选择的进程）
  • 若有子孙进程则将其全部终止，以防它们失控
  • 将该进程所占有的全部资源还给父进程或系统
  • 将该进程的PCB从所在队列中移出。

• 创建与撤销流程图

  

3）阻塞原语、唤醒原语

• 进程的阻塞

  • 处于运行状态的进程，在其运行过程中期待某一事件发生（如：请求系统服务、等待键盘输入、等待数据传输完成、等待其它进程发送消息）当被等待的事件未发生时, 由进程调用阻塞原语(block),将自己阻塞。
  • 阻塞原语使处于运行态的进程停止运行，将运行现场保存在其PCB的CPU现场保护区，然后将 PCB中的现行状态由运行态变为阻塞态，并将该进程插入到相应事件的阻塞队列中。最后，转进程调度程序重新调度，将处理机分配给一个就绪进程，按新进程PCB中的处理机状态设置CPU环境，使它投入运行。

• 进程的唤醒

  • 当被阻塞进程期待的事件到来时,由中断处理进程或其它产生该事件的进程调用唤醒原语(Wakeup),将期待该事件的进程唤醒。
  • 唤醒原语执行时, 将被阻塞进程从相应等队列中移出, 并将其 PCB中的现行状态由阻塞改为就绪态, 然后将该进程插入就绪队列中。
  • 若事件是等待 I/O 完成, 则由硬件提出中断请求, CPU响应中断, 暂停当前进程的执行, 转去中断处理。检查有无等待该 I/O完成的进程。若有, 则将它唤醒。然后结束中断处理。返回被中断进程或重新调度。
  • 若事件是等待某进程发一个信息, 则由发送进程把该等待进程唤醒。

• 阻塞与唤醒流程图

  

4）挂起原语、激活(解挂)原语

• 进程的挂起
  • 当进程请求将自己挂起或父进程请求将子进程挂起时, 调用挂起原语(suspend),将指定进程挂起。
  • 执行过程: 检查要挂起进程的状态，若处于活动就绪态就将其改为静止就绪态，对于活动阻塞态的进程则将其改为静止阻塞态。如果被挂起的进程正在执行则还要转到调度程序重新调度。
• 进程的激活：
  • 要激活指定进程，调用激活原语(active)将它激活。
  • 执行过程：将要激活的进程调入内存, 并检查它的状态, 若是静止就绪态则将其改为活动就绪态,若为静止阻塞态就将其改为活动阻塞态。如果采用的是抢占调度策略,被激活的进程优先级高则引起重新调度。

进程同步与互斥

并发的问题

• 并发进程之间的关系

  • 合作关系：一组进程协同完成一个任务，它们之间是合作关系（直接制约关系）。例如，一个计算进程和一个打印进程共同完成一个任务。
  • 竞争关系：多个进程因为使用共享资源而产生竞争关系（间接制约关系）。例如，多个进程共同使用一台打印机。

• 进程并发执行相互间的影响

  • 同步：多个进程在执行过程中，为了共享资源与相互合作而在执行次序上的协调，称为同步，即共享同一资源的进程和相互关联进程以通信手段来保障完成任务时所必须保持一种固定的时间关系。
  • 互斥：当某一进程访问某一资源时，不允许别的进程同时访问，这种限制称为互斥，即多个进程在访问某些资源（如临界资源）时，也要有一种执行次序上的协调，当一个进程访问完毕，另一个进程才能访问。所以就其本质来讲，互斥仍是一种同步。

• 临界资源

  • 限定进程只能互斥地访问的资源叫临界资源（指一次仅允许一个进程使用的资源 ）
    • 临界资源限定了使用者只能互斥地使用它,操作系统也不能中途从抢先者手中把临界资源抢来给其他进程用。因此，临界资源也是不可剥夺性资源。
  • 临界区：进程中访问临界资源的那段程序代码称为临界区或临界段。
  • 使用同一临界资源的不同进程中的临界区称为同类临界区或相关临界区。
  • 临界区的使用原则，即“空则让进，忙则等待，等则有限，等则让权”。

临界区的互斥进入方法

• (1)采用询问方式，当其他进程不用时，则自己进入。此法实现复杂。
• (2)采用加锁方式，加锁是一种最简单的进程互斥方法，它使用一个锁变量W来表示某种临界资源的状态，
  • W=0表示资源空闲可用
  • W=1表示资源正被使用
• (3)信号灯机制。
• (4)管程机制等。

互斥的加锁实现

• 1）为临界区加锁——每当进程想要进入临界区，就要测试锁的状态，若W＝0，就马上将其设置为1，以防止其它进程进入临界区。若W＝1，则进程就进入等待状态。这时临界区的控制描述如下：（若同时有进程检测到W=0，控制机制就会导致失败！）

  

• 2）由硬件提供相应指令

• 3）加锁实现互斥访问

  • 如图

    

• 4）加锁原语

  • 如图

    

• 5）用上锁和开锁原语

  • 用上锁用上锁原语和开锁原语来实现进程的互斥的确很简单，但处理机效率不高，因为上锁原语中的条件测试操作可能引起CPU“忙等”。

    

信号量机制

• 信号量的思想：两个或多个进程可以利用彼此间收发的简单的信号来实现“正确的”并发执行，一个进程在收到一个指定信号前，会被迫在一个确定的或者需要的地方停下来，从而保持同步或互斥。

• 信号量类型

  • P（Passeren/proberen ）、 V（Vrijgeren/verhogen ）是荷兰语，分别代表 “通过/测试或等待”及 “释放/增加或发信号”。

    

  • 整型信号量定义：

    

  • 记录型信号量：信号量的数据结构。C语言为例——struct结构体

    

• 信号量S的值含义（S的值只能由P、V操作来改变）

  • 当S≥0时，表示某类可用资源的数目，或者说表示可以执行P操作而不会被阻塞的进程的数目；
  • 当S＜0时，其绝对值表示信号量S的阻塞队列中的进程数，即系统中因请求该类资源而被阻塞的进程的数目，亦即被信号灯挡住的进程数目，这些进程需要别的进程发出相应的信号灯来唤醒。

• P(S)、V(S)操作含义

  • P(S)操作表示“等信号”，即测试一个要等的信号是否到达；
  • V(S)操作表示“发信号”。这个信号在实现同步时就是“合作者的伙伴进程已完成前趋任务”，在实现互斥时就是“临界资源可用”。
  • 另外，在互斥问题中，每执行一次P(S)操作的含义，也可理解为进程请求一个单位的S类资源；每执行一次V(S)操作的含义，也可理解为进程释放一个单位的S类资源。

• 信号量集

  • 假如进程一次需要共享多种临界资源，且每种资源个数不限于一个时，则P、V操作就显得效率不高，这种情况下我们可以用信号量集来解决。在信号量集机制中，进程一次可以申请多个不同种类的临界资源，当可用资源个数低于系统规定的某一下限值时，不予分配。

  • AND型信号量：进程同时请求若干类资源，每类资源请求一个

    

  • 信号量集SP(s1,t1,d1；s2,t2,d2；…；sn,tn,dn)

    • si：系统i类资源可用的个数（信号量）；

    • di：进程当前需要的i类资源个数（需求数）；

    • ti：系统保留的i类资源数目，或者说是分配下限（下限值）；

    • 若si≥ti且si≥di时，作si=si- di，表示资源申请成功；否则，资源申请失败,则将申请资源的进程放入第一个不满足条件的si的等待队列，转进程调度程序入口。

      

    • 操作说明：进程使用信号量操作申请资源时，即使有一个资源申请不到，也将此次申请作废，程序计数器拨回到进程执行信号量时的初始位置。下次进程运行时再重新申请所有资源。

    • 特例：

      • 1)SP(s,d,d)表示只有一个信号量：此时在信号量集中只有一个信号量 S，但允许它每次申请 d 个资源，当现有资源数少于 d 时，不予分配。
      • 2)SP(s,1,1)：相当于P(s)，；此时的信号量集已蜕化为一般的记录型信号量(S>1 时)或互斥信号量(S=1 时)。
      • 3. SP(s,1,0)：相当于一个可控开关。即当s≥1时，允许多个进程进入某特定区；当s<1时，禁止任何进程进入某特定区。
      • 4. 将SP(s，1，0)作一引伸，如SP(s，n，0)，则表示当s≥n时，允许多个进程进入某特定区；当s<n时，禁止任何进程进入某特定区。

信号量应用

P、V操作(信号量)实现进程的互斥

• 即保证进程互斥地进入各自的临界区。

• 为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量 mutex，并设其初始值为 1，然后将各进程访问该资源的临界区 CS 置于 wait(mutex)和 signal(mutex)操作之间即可。（注：wait(mutex)和 signal(mutex)必须成对地出现。）

• 用P、V操作原语实现进程互斥的效率更高一些，因为P操作中引入了阻塞机制，所以消除了CPU忙等现象。

• 三个进程互斥进入临界区

  

P、V操作(信号量)实现前趋关系

• 先确定前驱关系；再设信号量值

  

  • 设有两个并发执行的进程P 1 和P 2 。P 1 中有语句 S 1 ；P 2 中有语句 S 2 。我们希望在 S 1 执行后再执行 S 2 。为实现这种前趋关系，
  • 我们只须使进程 P 1 和 P 2 共享一个公用信号量 S，并赋予其初值为 0，将 signal(S)操作放在语句 S 1 后面；而在 S 2 语句前面插入 wait(S)操作，即在进程 P 1 中，用 S 1 ；signal(S)；在进程 P 2 中，用 wait(S)；S 2 ；
  • 由于 S 被初始化为 0，这样，若 P 2 先执行必定阻塞，只有在进程 P 1 执行完 S 1 ；signal(S)；操作后使 S 增为 1 时，P 2 进程方能执行语句 S 2 成功。

• 更复杂的示例：

  

  

管程机制

• 自行使用PV操作可能的问题：P、V操作没有成对出现——只有P，而没有V，或者只有V，而没有P；P、V操作颠倒；两个P操作颠倒等。

管程定义

一个管程指定义了一个数据结构和能为并发程序在该数据结构上执行的一组操作，这组操作能同步进程和改变管程中的数据（将对临界资源的控制与管理集中起来，用户只要提出使用要求，其它诸如互斥、同步等问题则不需要用户自己解决，而由系统统一解决。）

组成

• (1) 管程标识符；
• (2) 局部于管程的共享变量说明（局部于管程内部的数据结构，仅能被局部于管程内部的过程所访问，任何管程外的过程都不能访问它）；
• (3) 对该数据结构进行操作的一组过程；
• (4) 对局部于管程内部的共享数据的初始化过程。

条件变量

• 在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语 wait 和 signal。
• 考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间地等待。为了解决这个问题，引入了条件变量condition。其形式为：Var x，y：condition。
• ① x.wait：正在调用管程的进程因 x 条件需要被阻塞或挂起，则调用 x.wait 将自己插入到 x 条件的等待队列上，并释放管程，直到 x 条件变化。此时其它进程可以使用该管程。
• ② x.signal：正在调用管程的进程发现 x 条件发生了变化，则调用 x.signal，重新启动一个因 x 条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。

进程同步定义

指的是两个或多个进程为了合作完成同一个任务，在执行速度或某些个确定的时序点上必须相互协调，即一个进程的执行依赖于另一个进程——其合作伙伴的消息，当一个进程到达了某一确定点而没有得到合作伙伴发来的“已完成某些操作”的消息时必须等待，直到该消息到达被唤醒后，才能继续向前推进。

进程同步和互斥间的关系

• 相似处：进程的互斥实际上是进程同步的一种特殊情况； 进程的互斥和同步统称为进程同步。
• 差别：进程互斥是进程间共享资源的使用权，这种竞争没有固定的必然联系，哪个进程竞争到使用权就归那个进程使用，直到不需要使用时再归还；而进程同步则涉及共享资源的并发进程间有一种必然的联系，当进程必须同步时，即使无进程在使用共享资源时，那么尚未得到同步消息的进程也不能去使用这个资源。

PV操作实现进程同步

• P、V操作也都是配对出现，但对同一个信号量的P、V操作却不是同时出现在每一个进程的程序里，而是分别出现在一个进程和它的合作伙伴的代码中。
• 解答这类进程同步问题的主要步骤也是有三步：
  • (1)分析清楚题目涉及的进程间的制约关系
  • (2)设置信号量（包括信号量的个数和初值及其物理含义），合作进程间需要收发几条消息相应就设置几个信号量。同步信号量的初值一般为0，表示得到合作进程的消息后才能向前推进。
  • (3)给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序的适当处。

经典进程同步问题

生产者—消费者问题

• 生产者—消费者问题是相互合作进程关系的一种抽象

问题分析

• ①生产者—消费者之间的同步关系表现为：一旦缓冲池中所有缓冲区均装满产品时，生产者必须等待消费者提供空缓冲区；一旦缓冲池中所有缓冲区全为空时，消费者必须等待生产者提供满缓冲区。
• ②生产者—消费者之间还有互斥关系：由于缓冲池是临界资源，所以任何进程在对缓冲区进行存取操作时都必须和其他进程互斥进行。

问题解答

• ①所用信号量设置如下：

  • Ⅰ）同步信号量empty，初值为n，表示消费者已把缓冲池中全部产品取走，有n个空缓冲区可用。
  • Ⅱ）同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池，有0个满缓冲区可用。
  • Ⅲ）互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问缓冲池。
• 

读者—写者问题

• 读者—写者问题是共享数据对象的非合作进程关系的一种抽象

问题描述

• 一组读者与一组写者循环访问共享的同一个数据对象。
• 读者：指能对共享数据对象读的进程，写者：指对共享数据对象只要求写的进程。
• 规定：多个读者可以同时读这个数据对象，但决不允许多个写者同时对这个数据对象进行写操作，也不允许读者、写者同时访问这个数据对象。

问题分析

• ①读者—写者之间的互斥关系：
  • 写者与写者的互斥、写者与读者的互斥。设一个公用的初值为1的互斥信号量 RW_mutex ？但是实现了读者与读者的互斥。引入一个读者计数器变量RC。
• ②读者—读者之间又有了互斥关系：
  • 再设一个读者公用的初值为1的互斥信号量R_mutex实现各个读者间互斥的访问RC

问题解答

• ①所用信号量和其他变量设置如下：

  • Ⅰ）互斥信号量RW_mutex，初值为1，用于实现写者与其他写者或读者互斥地访问共享的数据对象。
  • Ⅱ）互斥信号量R_mutex，初值为1，用于实现诸读者互斥地访问读者计数器变量。
  • Ⅲ）整型变量RC，初值为0，用于对读者进行记数。

• 算法描述&伪代码

  

哲学家进餐问题

问题描述

• 有5个哲学家，围坐在圆桌旁，他们的生活方式是交替地进行思考和进餐；圆桌上间隔地摆放着5把叉子和1个装有通心粉的盘子，规定第i号哲学家固定坐在第i把椅子上（i=0,1,2,3,4），且每个哲学家必须两手分别拿起他左右两旁的那两把叉子，才能吃通心粉；假定通心粉的数量足够5个哲学家用的。

  

解决策略

• 策略一：饥饿时总是先拿左边的筷子，再拿右边的。（当5个哲学家同时饥饿时都拿左边的筷子，就会进入无限等待右边筷子而死锁）

  

• 改进策略一：通过发放令牌，至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。

  

• 改进策略二：规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。

  

• 改进策略三：采用Hoare管程实现，算法思想是将哲学家的状态分为思考、饥饿、进餐；并且仅当哲学家左右两边的筷子都可用才允许他拿筷子，否则一只筷子也不拿。

  

信号量机制解题步骤

• （1）分析进程间的制约关系
• （2）设置信号量
• （3）实施P、V操作。
• 第一步是基础、关键，第三步是核心。
• 掌握实现进程互斥与进程同步的第三步在形式上差异：即P、V操作总是配对出现的。
• 但P,V在互斥问题中总是出现在同一个进程的代码中，且紧紧夹着临界区；而在同步问题中，却是分别出现在两个合作进程的代码中，需要等消息的一方用P操作，相应的对同一信号量的V操作则在发出此消息的另一方中。

进程通信

• 进程之间的信息交换称为进程通信。

• 按通信交换的数据量多少划分为:

  • 低级通信：进程间交换的数据量很少，一般只传送一个和几个字节的信息，如信号量机制。缺点是：u效率低。v通信对用户不透明。

  • 高级通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。优点是：效率高和使用方便

    
    • 共享存储器系统
      • (1)基于共享数据结构的通信方式：通信进程公用某些数据结构，如生产者与消费者问题中的公共缓冲区；
      • (2)基于共享存储区的通信方式：多个进程可以通过对共享内存储区中数据的读操作与写操作完成进程之间的通信。
    • 消息机制
      • 直接通信方式：发送进程将消息直接发给接收进程，挂在接收进程的消息队列上，由接收进程从自己的消息队列上取下消息，完成一次消息的通信过程。
      • 间接通信方式：通信时指明一个中间媒介，即信箱。发送者执行发送命令，将消息发到指明的信箱，接收者执行接收命令时，从指定的信箱中接收消息。
    • 管道
      • 无名管道：是操作系统提供的资源，可以被所有的进程使用。但是无名管道在使用上的限制是：它仅能用于连接具有共同祖先的进程。
      • 有名管道：克服了无名管道使用上的限制，所有进程都可以共享对管道的操作，相互之间通过管道通信。

进程同步方式

• ⑴ 阻塞发送、阻塞接收：用于进程间双向通信，发送进程和接收进程之间无缓冲。即通信双方联系非常紧密,得到对方的应答才能推进。
• ⑵ 不阻塞发送、阻塞接收：适合于那些不等待消息的到来就无法继续工作的进程。如服务器上的服务进程，平时总是处于阻塞状态，只有在请求服务的消息到达时，它们才会被唤醒以便提供服务。
• ⑶ 既不阻塞发送也不阻塞接收：常用于分布式系统中，因为采用阻塞方式进行通信时，一旦传递的数据丢失，将会使阻塞进程无限期地等待下去。而采用非阻塞、接收的方式就可以避免这种情况。接收进程有消息时就处理消息，无消息时继续执行

消息通信机制

• 信箱通信(间接通信)

  • 在信箱通信中，发送者创建一个消息，然后调用发送命令将消息发送到一个共享的数据结构——信箱中去，接收者调用接收命令从信箱中取出消息。

• 消息缓冲通信(直接通信方式)

  • 消息缓冲通信过程中，一个进程将一个消息直接发送给接收进程，而接收进程执行时接收这个消息。
  • 消息缓冲通信的通信过程如下：发送进程首先在自己地址空间的消息发送区制造一个始地址为a的消息，然后调用发送命令send(B，a)发送消息；
  • 发送原语（send（接收者进程名，发送区首地址））；接收原语（receive（接收区首地址））是系统提供给用户实现进程通信的最基本的原语，也是构成一种具体的通信系统的主要内容，用户直接使用这些通信原语一次就能发送成千上万字节的信息。
• 

线程管理

• 作为并发执行的进程具有二个基本的属性：
  • （1）进程既是一个拥有资源的独立单位。
  • （2）进程又是一个可独立调度和分派的基本单位。
• 进程的缺点
  • (1)进程管理开销大
  • (2)进程的局限性
• 线程定义
  • 进程内一个执行单元或一个可调度实体。线程只拥有一点在运行中必不可省的资源（程序计数器、一组寄存器和栈），但它可与同属一个进程的其它线程共享进程拥有的全部资源。

线程与进程的比较

• (1)调度:在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。现在分离了。
• (2)并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。
• (3)拥有资源：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源的一个独立单位，它可以拥有自己的资源。
• (4)系统开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。

线程与进程的关系

• 线程是进程的一个组成部分。每个进程创建时通常只有一个线程，需要时可创建其他线程。
• 进程的多线程都在进程的地址空间活动。
• 资源是分给进程的，不是分给线程的。线程在执行中需要资源时，可从进程资源中划分。
• 处理机调度的基本单位是线程，线程之间竞争处理机。真正在CPU上运行的是线程。
• 线程在执行时，需要同步。

线程的控制

1.线程的状态及其转换

• 线程由创建而产生，由撤消而消亡，在生命期间，线程可以处于就绪状态、执行状态和阻塞状态三个基本状态中。也有状态变迁，如就绪状态→执行状态，执行状态→阻塞状态，阻塞状态→就绪状态等
• 但是线程没有挂起状态，这是因为线程不拥有资源，因而没有权利将整个进程或自己挂起，所以线程没有挂起状态。
• 多线程机制中的进程，其状态可以简单地被划分为活动状态与非活动状态。挂起属于非活动状态，即不可运行状态；活动状态是指进程中某个线程正在执行。
• 对进程的操作等效于对进程下的所有线程，比如挂起某进程，即将该进程中的所有线程挂起。

2.线程控制块

• 每一个线程是一个动态对象，它表示进程中的一条控制线索，执行一系列指令操作，是一个相对独立的、可被调度运行的基本单位。
• 在进程的地址空间中可以有多个线程，它们可以并发执行，这就需要一张单独的表来记录线程控制与管理等信息，这张表称为线程控制表。
• 为了管理系统中的进程和线程，不但要有进程控制块，还要为每个线程设置一个线程控制块TCB。线程控制块由一个线程标识符和一张线程描述表组成，线程描述表记录了线程的属性和调度所需的数据。如线程状态、寄存器组（用于存放现场信息）、堆栈、以及有关调度和I/O活动的信息。

3.线程控制

• 系统为了对线程进行管理，也提供了相应的线程控制原语，如线程的创建与撤销、阻塞与唤醒等。当应用程序启动执行时，首先被执行的线程称之为初始化线程，也叫做主线程。它可以根据需要再去创建若干线程。
• 一个线程可以通过调用创建原语来创建线程，线程创建原语要申请一个线程控制块，并初始化线程ID、线程描述表等其它有关项，排入就绪队列，最后返回一个线程标识符供以后使用。
• 当线程正常结束时会请求撤离，如果线程运行过程中出现错误或由于某种原因而被其它线程终止，线程也就随之消亡。撤销线程原语收回该线程的数据结构及线程控制块。
• 同样当线程请求某一事件时可以调用阻塞原语将自己置入阻塞态，当阻塞的事件发生，会被线程唤醒原语唤醒。

4.线程间的同步与通信

（常用的有互斥锁和信号量机制等）

互斥锁

• 互斥锁是一种比较简单的同步机制，它有两种状态，即开锁和关锁状态。对互斥锁的操作命令有两条，即关锁命令（lock（L））和开锁命令（unlock（L））。由于操作互斥锁的时间和空间的开销都较少，因而它适合于频繁使用的共享数据和程序段。为共享数据设一把互斥锁L。每当线程去访问共享数据时，都先调用关锁命令lock（L），当它操作完共享数据时，再调用开锁命令。
• 为了减少线程被阻塞的机会，有的系统也提供互斥锁的测试操作trylock，该命令返回互斥锁的状态值。即若为开锁状态，返回一个成功码；若为关锁状态，则返回一个失败码，但并不阻塞线程。
• 为避免出现死锁现象，特设条件变量与一个互斥锁一起使用。
• 互斥锁用于短期锁定，保证对临界区互斥进入，而条件变量则用于线程的长期等待，直至所等待的资源成为可用的。

信号量机制

• 私用信号量用于同一进程下诸线程之间的同步。它可由请求同步的线程来创建，属于进程所有，存于进程的地址空间中，操作系统并不知道它的存在。
• 而公用信号量是为不同进程间或不同进程的线程之间的同步而设置的，其数据结构是存放在受保护的系统存储区中，由操作系统对它进行管理，故也称之为系统信号量。

线程的实现

线程类型：用户级线程、内核级线程以及混合型线程

• 用户级线程：是指由用户应用程序建立起来的线程，并且由用户应用程序负责所有这些用户级线程的调度执行和管理工作。而操作系统的内核完全不知道线程的存在，因而也不会参与线程的管理。用户级线程的切换发生在同一个进程的诸多线程之间，因为线程管理操作不需要内核介入，因而远比进程调度与切换好得多，切换速度也特别快。与常规的过程调用的代价是在同一量级上的。用户级线程还表现出很好的适应性。它们可以在不用修改内核的前提下，根据语言或用户的需要进行定制。
• 用户程序怎样才能搭建一个支持线程的运行环境呢？通常是由操作系统或某种语言如Java为用户提供一个基于多线程的用户应用程序开发环境和运行环境,称之为线程库（ThreadsLibrary），它可以支持所有用户线程的创建、调度和管理工作。操作系统首先为进入系统的程序创建一个由内核管理的进程，当该进程在线程库的环境下开始运行时，只有一个初始线程。随着主线程的执行，它可以调用线程库中的创建函数来生成新的线程。线程库按照一定的调度算法挑选就绪线程执行，并完成线程之间的切换、控制工作。
• 系统仍然是以进程为单位进行调度的。故容易发生线程当前状态与实际状态不相吻合的情况，如某线程运行过程中请求I/O，于是系统将该线程所在的进程置入阻塞状态。同一进程下的线程即使具备运行条件，也不会被调度；而当前线程理应是阻塞状态，但实际上仍是运行状态，因为系统不对线程进行操作。
• 内核级线程：是指线程是在操作系统的支持下运行的，当应用程序进入内存时，内核首先为它创建一个进程和一个线程，线程运行过程中通过调用内核创建原语可以创建其它的线程。这种方式下，系统对线程的管理与传统操作系统下的进程管理是一样的。和用户级线程相比，内核支持级线程更为灵活，内核本身也可以采用线程实现。当进程中的一个线程被阻塞后，同一进程中的其它线程仍可以被调度执行。另外内核可以调度同一个进程中的若干线程到多个处理器上运行，从而提高程序执行速度和效率。但是它也有不足之处，因为线程的一切活动均由内核管理，因此即使是同一个进程下的线程之间的切换也要进行两次模式转换，所以其开销比较大。

比较两种线程的优缺点

• 1．线程的调度与切换速度：内核支持线程的调度和切换与进程的调度和切换十分相似。
• 2．系统功能调用：当传统的用户进程调用一个系统功能调用时，要由用户态进入核心态，用户进程将被阻塞。当内核完成系统调用而返回时，才将该进程唤醒，继续执行。
• 3．线程执行时间 ：对于只设置了用户级线程的系统，调度是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，这对诸进程而言似乎是公平的。

混合线程

• ⑴进程仍然是资源分配的基本单位，拥有用户地址空间、堆栈和PCB等。
• ⑵用户级线程是由线程库来管理的，其数目可以很多，每个仅需一个栈和程序计数器。内核并不知道它的存在，故不受内核调度程序的调度，因此切换很快。
• ⑶内核级线程完成内核的所有工作，是被调度并分派到一个处理机上执行的实体。
• ⑷轻型进程（LightWeight Process－LWP）是用户级线程和内核级线程之间的接口，可以看成是被内核创建的用户级线程。