标签：管理 死锁 互斥 临界 线程 进程 第二章 资源

2.1.1 进程与线程的基本概念

^03dd71

进程的概念与特征

• 进程的概念
  进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
  进程是动态的，是程序的一次执行过程
  进程映像（进程实体）:
  1. 是静态的
  2. 由程序段、相关数据段和PCB组成
• 进程的特征
  1. 动态性（进程最基本的特征）
  2. 并发性
  3. 独立性
  4. 异步性
  5. 结构性
• 程序并发执行的特征
  1. 间断性
  2. 失去封闭性（并发进程共享变量，其执行结果与速度有关）
  3. 不可再现性

线程的基本概念

• 引入线程的目的是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性
• 线程是CPU基本的执行单元，也是程序执行流的最小单元
• 由线程ID、程序计数器、寄存器集合和堆栈组成
• 一个进程可以创建线程，线程之间可以并发执行
• 线程有阻塞、就绪和运行三种状态

2.1.2 进程/线程的状态与转换

进程/线程的状态与转换

进程的状态

1. 运行态：
   • 在单核处理机环境下，每个时刻最多只有一个进程处于运行态
2. 就绪态：
   • 进程获得了除了处理机外所需的一切资源，一旦得到处理机，便可立即运行
   • 处于就绪态的进程进程可能有多个，通常将它们排成一个就绪队列
3. 阻塞态/等待态
   • 等待某资源可用（不包括处理机）或等待输入/输出完成，即使处理机空闲，该进程也不能运行
4. 创建态
   • 进程正在被创建，尚未转到就绪态
   • 创建进程的步骤：
     1. 申请一个空白的PCB，并PCB填入一些控制和管理进程的信息
     2. 系统为该进程分配运行时所必须的
     3. 把进程转为就绪态
5. 结束态
   • 进程正在从系统中消失，可能是进程正常运行结束或其他原因中断退出运行

进程转换图

• 阻塞态 \(\to\) 就绪态是不受进程自身能控制的，是一种被动行为
• 运行态 \(\to\) 阻塞态是一种进程自身做出的主动行为
• 不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求）
  ![Pasted image 20241127151226.png]]

线程切换与进程切换的不同

• 当切换进程时，需要保存/恢复进程运行环境，还需要切换内存地址空间（更新快表、更新缓存）
• 同一进程内的各个线程间并发，不需要切换进程运行环境和内存地址空间，省时省力

2.1.3 线程的实现方式

用户级线程

• 用户级线程由应用程序通过线程库实现。
• 所有的线程管理工作都由应用程序负责（包括线程切换）
• 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。 ^6f98c6
• 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。（用户级线程对用户不透明，对操作系统透明）
• 缺点
  • 系统调用的阻塞：
    线程执行一个系统调用时，该进程的所有线程都会被阻塞(因为操作系统看不⻅用户级线程)
  • 多线程应用不能利用多处理机进行多重处理：
    内核给进程分配的只有一个cpu，进程中只有一个线程能执行
• 优点
  • 线程转换不需要切换到内核空间
  • 调度算法可以是进程专用的
  • 用户线程的实现与OS平台无关

内核级线程

• 内核级线程的管理工作由操作系统内核完成。
• 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。(多处理器中内核能同时调度同一进程中的多个线程并行执行)
• 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

2.1.4 进程与线程的组织与控制

2.3 同步与互斥

2.3.1 同步与互斥的基本概念

临界资源

• 临界资源是互斥共享资源，打印机、共享变量、共享缓冲区、公共队列都是临界资源
• 我们把一个时间段内只允许一个进程使用的资源称为临界资源。
  许多物理设备都属于临界资源，如打印机等。
  此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。
• 临界资源的访问过程分成4个部分：
  1. 进入区
     为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
  2. 临界区
     进程中访问临界资源的那段代码，又称临界段。
  3. 退出区
     将正在访问临界区的标志清除。
  4. 剩余区
     代码中的其余部分。
• 进入区和退出区是负责实现互斥的代码段。
  临界区也可称为“临界段”。

同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。
为了实现对临界资源的同步访问，需要遵循以下原则

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当进入临界区的进程数达到上限时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

互斥

为了实现对临界资源的互斥访问，需要遵循以下原则

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

2.3.2 实现临界区互斥的基本方法

软件实现方法

单标志法

• 算法思想：
  两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
  ![Pasted image 20241125165134.png]]

  turn 的初值为0，即刚开始只允许0 号进程进入临界区。若P1 先上处理机运行，则会一直卡在⑤。直到P1 的时间片用完，发生调度，切换P0 上处理机运行。代码①不会卡住P0，P0 可以正常访问临界区，在P0 访问临界区期间即时切换回P1，P1依然会卡在⑤。只有P0 在退出区将turn 改为1 后，P1才能进入临界区。

• 主要问题：
  违背“空闲让进”原则

双标先检查志法

• 算法思想
  设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区
  的意愿，比如“flag[0] = ture”意味着0 号进程P0 现在想要进入临界区。
  每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果
  没有，则把自身对应的标志flag[i] 设为true，之后开始访问临界区。
  ![Pasted image 20241125170047.png]]
• 优点
  不用交替进入，可以连续使用
• 主要问题
  违反“忙则等待”原则
  原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的
  “检查”后，“上锁”前可能发生进程切换
  导致双方检查都通过，两个进程同时进入临界区（按照 1-5-2-6 顺序）

双标志后检查法

• 算法思想
  双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
  ![Pasted image 20241125170325.png]]
• 主要问题
  两个进程争着要进入临界区，导致谁都进不了
  又违背了“空闲让进”和“有限等待”原则
  会因各进程都长期无法访问临界资源而产生“饥饿”现象。
  不是死锁

Peterson 算法

• 算法思想
  结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那
  可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
  ![Pasted image 20241125170715.png]]
• 主要问题
  未遵循让权等待的原则

硬件实现方法

中断屏蔽方法

• 原理：
  当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简单方法是关中断
  因为CPU只在发生中断时引起进程切换，通过禁止中断来暂时阻止操作系统进行进程切换
• 利用“开/关中断指令”实现
  ...
  关中断
  临界区
  开中断
  ...
• 优点：
  实现起来简单、高效
• 缺点：
  1. 不适用于多处理机
     关中断的机制只能影响当前进程或当前执行的CPU核，通常是对单核（单处理器）系统有效。对于多核（多处理器）系统，关中断方法并不能有效阻止其他处理器上的进程执行。
  2. 只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）
  3. 限制了CPU交替执行程序的能力，导致系统效率降低

硬件指令方法

• 用硬件指令方法实现互斥的优点：
  • ①简单、容易验证其正确性；
  • ②适用于任意数目的进程，支持多处理器系统；
  • ③支持系统中有多个临界区，只需为每个临界区设立一个布尔变量
• 用硬件指令方法实现互斥的缺点：
  • ①等待进入临界区的进程会占用CPU 执行 while 循环，不能实现“让权等待”;
  • ②从等待进中随机选择一个进程进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

TestAndSet指令

• 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令
• TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
• 指令的功能描述
  ![Pasted image 20241125173627.png]]
• 实现进程互斥
  ![Pasted image 20241125173801.png]]
  若刚开始 lock 是 false，则 TSL 返回的old 值为 false，while循环条件不满足，直接跳过循环，进入临界区。
  若刚开始 lock是 true，则执行 TLS 后old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问的临界区的进程在退出区进行“解锁”。
• 优点
  1. 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
  2. 适用于多处理机环境
• 缺点
  不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

Swap指令

• 有的地方也叫 Exchange 指令，或简称 XCHG 指令
• Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
• 指令的功能描述
  ![Pasted image 20241125174143.png]]
• 实现进程互斥
  ![Pasted image 20241125174227.png]] 逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old 变量上），再将上锁标记 lock 设置为 true，最后检查 old，如果old为 false 则说明之前没有别的进程则可跳出循环，进入临界区。
• 优点
  1. 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
  2. 适用于多处理机环境
• 缺点
  不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

2.3.3 互斥锁

![Pasted image 20241126161908.png]]

• 缺点：
  忙等待，进程时间片用完才能下处理机违反“让权等待”
• 优点：
  进程在等待锁期间，没有上下文切换，若上锁的时间较短，则等待代价不高。
• 常用于多处理器系统，一个线程可以在一个处理器上旋转，而不影响其他线程的执行。
• 不适用于单处理机系统，忙等过程中不可能解锁

2.3.4 信号量

• 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
• 信号量其实就是一个变量可以用信2号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1
• 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断
  原语是由关中断/开中断指令实现的
  软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题
• wait、signal 原语常简称为P、V操作。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)

整型信号量

• 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
• wait和signal的操作描述
  ![Pasted image 20241125191624.png]]
• 执行过程
  ![Pasted image 20241125191652.png]]
• 缺点
  违背“让权等待”原则，会发生“忙等”

记录型信号量

• “记录型信号量”，即用记录型数据结构表示的信号量
• 记录型信号量的定义
  ![Pasted image 20241125191843.png]]
• WAIT和SIGNAL操作（先改变,后检测）
  ![Pasted image 20241125192103.png]]
  对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减1，当 S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态→阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
  对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行 S.value++，表示资源数加1，若加1后仍是 S.value <=0，表示依然有进程在等待该类资源，因此应调用 wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）
• 注：若考试中出现 P(S)、V(S) 的操作，除非特别说明，否则默认 S 为记录型信号量
• 记录型信号量先改变,后检测
• 整型信号量 wait 操作先检测,后改变，signal直接改变没有检测

信号量机制实现进程互斥

• 对不同的临界资源需要设置不同的互斥信号量
• P、V操作必须成对出现。
  缺少 P(mutex) 就不能保证临界资源的互斥访问。缺少V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
  • ![Pasted image 20241125192907.png]]

信号量机制实现进程同步

• ![Pasted image 20241125193225.png]]
  若先执行到V(S) 操作，则 S++ 后 S=1。之后当执行到 P(S) 操作时，由于 S=1，表示有可用资源，会执行 S--，S 的值变回 0， P2 进程不会执行block 原语，而是继续往下执行代码4。
  若先执行到 P(S) 操作，由于 S=0，S-- 后 S=-1，表示此时没有可用资源，因此P操作中会执行block 原语，主动请求阻塞。之后当执行完代码2，继而执行V(S) 操作，S++，使 S 变回 0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V 操作中执行 wakeup 原语，唤醒 P2 进程。这样 P2 就可以继续执行代码4了，保证了代码4 一定是在代码2 之后执行
• 实现步骤
  • 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操（或两句代码）
  • 设置同步信号量 S, 初始为 0
  • 在“前操作”之后执行 V(S）
  • 在“后操作”之前执行 P(S)

信号量机制实现前驱关系

![Pasted image 20241125193947.png]]

2.3.5 经典同步问题

生产者消费者问题

• 问题描述
  • 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）生产者、消费者共享一个初始为空、大小为n的缓冲区。
  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（缓冲区没满→生产者生产）
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。(缓冲区没空→消费者消费)
  • 缓冲区是临界资源，各进程必须互斥地访问。(互斥关系)
    ![Pasted image 20241126165825.png]]
• PV操作题目分析步骤
  1. 关系分析:找出题目中描述的各个进程，分析它们之间的同步、互斥关系
  2. 整理思路:根据各进程的操作流程确定P、V操作的大致顺序
  3. 设置信号量:并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

  • 互斥：在临界区先 P 后 V

  • 同步: 在临界区先 V 后 P

  • 同步关系
    ![Pasted image 20241126170106.png]]

  • 互斥关系：缓冲区是临界资源，各进程必须互斥地访问。

• 具体算法

  semaphore mutex = 1; //互斥信号量，实现对缓冲区的互斥访问semaphore empty
  semaphore empty = n; //同步信号量，表示空闲缓冲区的数量
  semaphore full = 0; //同步信号量，表示产品的数量，也即非空缓冲区的数量
  producer (){
      while (1) {
          生产一个产品;
          P(empty);
          P(mutex);
          把产品放入缓冲区;
          V(mutex);
          V(full);
      }
  }
  consumer () {
      while (1) {
          P(full);
          P(mutex);
          从缓冲区取出一个产品;
          V(mutex);
          V(empty);
          使用产品;
      }
  }
  

• 能否改变P V的顺序？
  • 实现互斥的 P 操作一定要在实现同步的 P 操作之后![Pasted image 20241126175250.png]]

多生产者消费者问题

• 问题描述
  • 桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
• 分析
  • 互斥关系
    对缓冲区（盘子）的访问要互斥地进行(mutex=1)
  • 同步关系
    1. 父亲将苹果放入盘子后，女儿才能取苹果
    2. 母亲将橘子放入盘子后，儿子才能取橘子
    3. 只有盘子为空时，父亲或母亲才能放入水果
       ![Pasted image 20241126180412.png]]
• 具体算法
  ![Pasted image 20241126180816.png]]
  • 即使不设置专门的互斥变量mutex，也不问会出现可多个进程同时访互问盘号子量的现象
  • 原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…
  • 盘子容量为2则必须需要mutex

吸烟者问题

• 问题描述
  • 假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）
• 分析
  • 互斥关系
    桌子抽象为容量为1的缓冲区，要互斥访问
  • 同步关系
    组合一：纸+胶水
    组合二：烟草+胶水
    组合三：烟草
    桌上有组合一→第一个抽烟者取走东西
    桌上有组合二→第二个抽烟者取走东西
    桌上有组合三→第三个抽烟者取走东西
    发出完成信号→供应者将下一个组合放到桌上
    ![Pasted image 20241126181504.png]]
• 具体算法
  semaphore offer1 = 0; //桌上组合一的数量
  semaphore offer2 = 0; //桌上组合二的数量
  semaphore offer3 = 0; //桌上组合三的数量
  semaphore finish = 0; //抽烟是否完成
  int i = 0; //用于实现“三个抽烟者轮流抽烟”
  ![Pasted image 20241126182441.png]]

读者-写者问题

• 问题描述
  • 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
    ①允许多个读者可以同时对文件执行读操作；
    ②只允许一个写者往文件中写信息；
    ③任一写者在完成写操作之前不允许其他读者或写者工作；
    ④写者执行写操作前，应让已有的读者和写者全部退出。
• 分析
  两类进程：写进程, 读进程
  互斥关系：写进程-写进程，写进程-读进程。读进程与读进程不存在互斥问题。
• 算法
  • 在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的“写优先”，而是相对公平的先来先服务原则。有的书上把这种算法称为“读写公平法”。
  • 读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。其核心思想在于设置了一个计数器 count用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。最后，还要认真体会我们是如何解决“写进程饥饿”问题的。
    ![Pasted image 20241126191645.png]]
• 如何解决“写进程饥饿”问题
  若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和reader()函数中各增加一对 PV操作，就可以得到写进程优先的解决程序
  ![Pasted image 20241126192332.png]]

哲学家进餐问题

• 问题描述
  有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
  ①允许多个读者可以同时对文件执行读操作；
  ②只允许一个写者往文件中写信息；
  ③任一写者在完成写操作之前不允许其他读者或写者工作；
  ④写者执行写操作前，应让已有的读者和写者全部退出。

哲学家进餐问题的关键在于解决进程死锁。这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。如果在考试中遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想，分析题中给出的进程之间是否会发生循环等待，是否会发生死锁。可以参考哲学家就餐问题解决死锁的三种思路。

• 防止死锁的发生 ^5dfff3
  • ①可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

    semaphore chopstick[5] = {1,1,1,1,1};
    semaphore count = 4; // 设置一个count，最多有四个哲学家可以进来
    void philosopher(int i) {
        while (true) {
            think();
            wait(count); //请求进入房间进餐
    			         //当count为0时不能允许哲学家再进来了
            wait(chopstick[i]); //请求左手边的筷子
            wait(chopstick[(i + 1) % 5]); //请求右手边的筷子
            eat();
            signal(chopstick[i]); //释放左手边的筷子
            signal(chopstick[(i + 1) % 5]); //释放右手边的筷子
            signal(count); //离开饭桌释放信号量
        }
    }
    

  • ②要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。

    semaphore chopstick[5] = {1, 1, 1, 1, 1};
    void philosopher(int i) {
        while (true) {
            think();
            if (i % 2 == 0) {
                //偶数哲学家，先右后左。
                wait (chopstick[(i + 1) % 5]);
                wait (chopstick[i]);
                eat();
                signal (chopstick[(i + 1) % 5]);
                signal (chopstick[i]);
            } else {
                //奇数哲学家，先左后右。
                wait (chopstick[i]);
                wait (chopstick[(i + 1) % 5]);
                eat();
                signal (chopstick[i]);
                signal (chopstick[(i + 1) % 5]);
            }
        }
    }
    

  • ③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷
    本质:一次申请完所有资源,简单易行
    ![Pasted image 20241126194935.png]]

2.3.6 管程

管程的定义

• 为什么要引入管程？
  信号量机制存在的问题：编写程序困难、易出错
• 管程的定义和基本特征
  • 管程是一种特殊的软件模块，有这些部分组成
    1. 局部于管程的共享数据结构说明；
    2. 对该数据结构进行操作的一组过程（函数）；
    3. 对局部于管程的共享数据设置初始值的语句；
    4. 管程有一个名字。
  • 管程的基本特征：
    1. 局部于管程的数据只能被局部于管程的过程所访问；
    2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
    3. 每次仅允许一个进程在管程内执行某个内部过程。
• 用管程实现生产者和消费者问题
  ![Pasted image 20241126162412.png]]
  1. 需要在管程中定义共享数据（如生产者消费者问题的缓冲区）
  2. 需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）
  3. 只有通过这些特定的“入口”才能访问共享数据
  4. 管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心）
  5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。

条件变量

• 将阻塞原因定义为条件变量
• 对条件变量只有两种操作
  • x.wait
    当x对应的条件不再满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程
  • x.signal
    当x对应的条件发生变化时，调用x.signal,唤醒因为x条件而阻塞的进程
• 条件变量与信号量的比较
  • 条件变量的wait和signal类似于信号量的P/V操作，可以实现进程的阻塞和唤醒
  • 条件变量是没有值的，仅实现了排队等待的功能，在管程中剩余资源数用共享数据结构记录

2.4 死锁

• 死锁的处理策略
  1. 预防死锁
     破坏死锁产生的四个必要条件中的一个或几个。
  2. 避免死锁
     用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
  3. 死锁的检测和解除
     允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

2.4.1 死锁的概念

死锁的定义

• 在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。
• 死锁、饥饿、死循环的区别:
  • 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
  • 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF）算法
  • 死循环：某进程执行过程中一直跳不出某个循环的现象。
    有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。
    可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。
    死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。
    死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。

死锁产生的必要条件

1. 互斥条件
   只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
2. 不剥夺条件
   进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
3. 请求和保持条件
   进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
4. 循环等待条件
   存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
   发生死锁时一定有循环等待，但是发生循环等待时未必死锁

发生死锁的原因

1. 对系统资源的竞争
   各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的
2. 进程推进顺序非法
   请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2 分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
3. 信号量的使用不当也会造成死锁
   如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

2.4.2 死锁预防

限制申请资源的顺序

破坏互斥条件

• 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态,比如: SPOOLing技术
• 缺点:并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

破坏不剥夺条件

• 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
• 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
• 缺点:
  1. 实现起来比较复杂。
  2. 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。
  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

破坏请求和保持条件

• 可以采用静态分配方法
  即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
  • 缺点:
    有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。
    另外，该策略也有可能导致某些进程饥饿。
• 也可以对静态分配进行改进，允许一个进程只获得运行初期所需的资源后，便开始运行,这种方法改进了静态分配方法的缺点

破坏循环等待条件

• 可采用顺序资源分配法
  首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
• 缺点
  • 不方便增加新的设备，因为可能需要重新分配所有的编号
  • 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
  • 必须按规定次序申请资源，用户编程麻烦。

2.4.3死锁的避免

限制分配资源的顺序

系统安全状态

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。
当然，安全序列可能有多个。
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利的执行下去。
如果系统处于安全状态，就一定不会发生死锁
如果系统进入不安全状就未必就是发生了死锁，但发生死锁时一定是在不安全状态

银行家算法

• 核心思想
  在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
• 数据结构描述
  • 假设系统中有n 个进程，m 种资源
  • 每个进程在运行前先声明对各种资源的最大需求数，则可用一个n * m 的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i, j]=K 表示进程 Pi 最多需要K 个资源 Rj
  • 同理，系统可以用一个 n * m 的分配矩阵 Allocation表示对所有进程的资源分配情况。
  • Max – Allocation =Need 矩阵，表示各进程最多还需要多少各类资源。
  • 另外，还要用一个长度为m的一维数组 Available 表示当前系统中还有多少可用资源。
• 算法描述
  ![Pasted image 20241129210901.png]]
• 安全性算法
  ![Pasted image 20241129210827.png]]

2.4.4 死锁检测和解除

资源分配

不需要知道进程全部的资源需求
一般用矩形表示资源结点，矩形中的小圆代表该类资源的数量
从进程到资源的有向边为请求边
从资源到进程的有向边为分配边

死锁定理

• 简化方法
• 死锁定理
  如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

死锁的解除

1. 资源剥夺法
   挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
2. 撤销进程法（或称终止进程法）
   强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
3. 进程回退法
   让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

标签：管理,死锁,互斥,临界,线程,进程,第二章,资源
From： https://www.cnblogs.com/zhujio/p/18578328