信号量的主要操作包括：

1. 创建信号量（Create Semaphore）：用于创建一个信号量对象，并为其分配资源。

2. 增加信号量（Increment Semaphore）：用于增加信号量的计数器。当一个进程或线程请求访问共享资源时，需要先增加信号量。如果信号量的计数器已经达到最大值，则请求访问的进程或线程将被阻塞，直到其他进程或线程释放资源。

3. 减少信号量（Decrement Semaphore）：用于减少信号量的计数器。当一个进程或线程释放共享资源时，需要先减少信号量。如果信号量的计数器已经减少到零，则阻塞在信号量上的进程或线程将被唤醒，并尝试访问共享资源。

4. 获取信号量（Acquire Semaphore）：用于获取访问共享资源的权限。当一个进程或线程请求访问共享资源时，需要先获取信号量。如果信号量的计数器已经达到零，则请求访问的进程或线程将被阻塞，直到其他进程或线程释放资源。

5. 释放信号量（Release Semaphore）：用于释放访问共享资源的权限。当一个进程或线程释放共享资源时，需要先释放信号量。释放信号量可以唤醒阻塞在信号量上的进程或线程，并允许它们访问共享资源。

常见的信号量类型包括二元信号量（Binary Semaphore）和计数信号量（Counting Semaphore）。二元信号量只允许一个进程或线程访问共享资源，而计数信号量允许多个进程或线程同时访问共享资源。

2.3.1进程同步与互斥的基本概念

进程同步

进程同步（Process Synchronization）是一种在多任务操作系统中协调多个进程之间执行顺序的技术。在多任务操作系统中，CPU 可以同时处理多个进程。为了确保数据的一致性和避免死锁，需要对进程间的执行顺序进行同步。

进程具有异步性，我们必须保证进程推进的次序是按照我们想要的那种方式来推进的

某些进程必须按照一定的工作次序(例如，写数据必须在读数据之前)保证这些次序就是进程同步要做的

例如：

//进程1
P1(){
代码1；
代码2：
代码3；
}
//进程2
P2(){
代码4；
代码5；
代码6；
}

P1、P2并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

进程互斥

临界资源：同一时间段内只能一个进程访问的资源(摄像头、打印机)

进程互斥是一种在多任务操作系统中常见的现象，当多个进程试图同时访问临界资源（如内存或打印机）时，可能会导致数据不一致或系统崩溃。为了避免这种情况，操作系统会使用一种称为互斥的机制来确保每次只有一个进程能够访问共享资源。也就是说，当一个进程访问临界资源时，另一个想要访问临界资源的进程必须等待，这种现象叫做进程互斥

应遵循的规则：

• 空闲让进：没有进程在临界区时，任何进程可进入

• 忙则等待：有进程在临界区时，其他进程均不能进入临界区

• 有限等待：等待进入临界区的进程不能无限期等待

• 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

2.3.2进程互斥的软件实现方法

• 单标志法：个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

  • 实现方式：现有两个进程 p0、p1

  
  int turn=0//表示当前允许进入临界区的进程号
  //p0进程：
  while (turn !=0);//进入区
  critical section;//临界区
  turn =1;    //退出区
  remainder section;//剩余区

//p1进程
while (turn !=1);//进入区
critical section;//临界区
turn =0; //退出区
remainder section;//剩余区

  - 该代码中 turn的初始值是0，则进程p1先上处理机，这时候，turn==1，所以会一直while循环，直到分给该进程的时间片用完，p1下处理机，p0上处理机，然后执行

  - 缺点：如果此时允许p0进入临界区，但是p0迟迟不进临界区，这时候临界区会空闲，但是p1也无法访问，违背"空闲让进原则"

- **双标志先检查法**：：设置一个布尔型数组lag,数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[设为true,之后开始访问临界区。

  ```C++
bool flag [2];
flag[0]=false;
flag[1]=false;
//P0进程：
while (flag[1]);
flag[0]=true;
critical section;
flag[0]=false;
remainder section;

//p1进程
while (flag[0]);
flag[1]=true;
critical section;
flag[1]=false;
remainder section;

• 该算法的中心思想是检查另一个进程是否要访问临界区，如果要，则不会访问。

• 缺点：有一个bug，如果进程0先上处理机，执行到while，然后进入下一步，还没来及把flag[0]变为true,这时候他下处理机了，换到p1进程 ，p1进程就会进入临界区，紧接着当换回p0时，接着执行，也会进入临界区，违背互斥性

• 双标志后检查法：与双标志先检查法不同的是，后检查法会先先上锁后检查，即：

  
  bool flag [2];
  flag[0]=false;
  flag[1]=false;
  //P0进程：
  flag[0]=true;
  while (flag[1]);
  critical section;
  flag[0]=false;
  remainder section;

//p1进程
flag[1]=true;
while (flag[0]);
critical section;
flag[1]=false;
remainder section;

  - 缺点:会造成进程无限等待的情况。

- **Peterson算法**:结合双标志法和单标志法的思想

  ```C++
bool flag[2];
//表示进入临界区意愿的数组，初始值都是fa1se
int turn 0;
//turn表示优先让哪个进程进入临界区
//P0进程：
flag[0]=true;//表示自己想进入临界区
turn=1;//可以优先让对方进入临界区
while (flag[1]&turn==1);//对方想进，且最后一次是自己谦让，那自己就循环等待
critical section;
flag[0]=false;//解锁
remainder section;

//P1进程：
flag[1]=true;//表示自己想进入临界区
turn=0;//可以优先让对方进入临界☒
while (flag[0]&turn==0);//对方想进，且最后一次是自己“让梨”，那自己就循环等待
critical section;
flag[1]=false;//访问完临界区，表示自己已经不想访问临界区了
remainder section;

• 缺点：未遵循让权等待的原则，当进入不了临界区，也会卡在循环，卡在临界区

2.3.3进程互斥的硬件实现方法

• 中断屏蔽方法 ：利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

  • 优点:简单高效

  • 缺点：不适用与多处理机，只适合操作系统内核进程，不适用于用户进程(该指令运行在内核态)

• 互斥锁：

  • 锁是一个抽象的数据结构，一个二进制变量（锁定/解锁），使用锁来控制临界区访问。
    一共有两个操作：
    Lock::Acquire()锁被释放前一直等待，然后得到锁。
    Lock::Release()释放锁，唤醒任何等待的进程。
    使用锁机制的临界区访的逻辑代码如下：

  
  lock.acquire();// 一直等待并尝试获取锁
  critical_section;//临界区
  lock.release();// 释放

//其中:
lock::acquire(){
while (!available);//忙等待
available false;//获得锁
}
lock::release(){
available true;
}

  - 特性：

    - 需忙等，进程时间片用完才下处理机，违反“让权等待”

    - 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低

    - 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区

    - 不太适用于单处理机系统，忙等的过程中不可能解锁

- **TestAndSet指令**：简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令，TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。

  用C语言描述该指令的逻辑：

  ```C++
//布尔型共享变量L0ck表示当前临界区是否被加锁
//true表示已加锁，false表示未加锁
bool TestAndSet (bool *lock){
bool old;
oLd=*lock;//old用来存放1ock原来的值
*lock=true;//无论之前是否已加锁，都将Lock设为true
return old;
//返回1ock原来的值
}

//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));//"上锁"并"检查" 这里就相当于lock.acquire();的实现
critical_section;//临界区代码段，，
lock=false;//解锁 相当于 lock.release();
//剩余区代码段，，

• 以上只是逻辑实现，它实际上是通过硬件实现的

• 优点：实现简单，适用于多处理机环境

• 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

• Swap指令

  • 用C语言描述该指令的逻辑：

  ```C++
  //以下是用Swap指令实现互斥的算法逻辑
  //Lock表示当前临界区是否被加锁
  bool old=true;
  while (old ==true)//相当于lock.acquire();
  Swap (&lock,&old);//交换两个变量
  critical_section;//临界区代码段，，
  lock=false;//lock.release();
  //剩余区代码段.·。

  
  
  - 逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否己经被上锁（记录在old变量上)，再将上锁标记lock设置为true,最后检查old,如果old为false则说明之前没有别的进程
  对临界区上锁，则可跳出循环，进入临界区。
  
  - 以上只是逻辑实现，它实际上是通过硬件实现的

• 自旋锁：当一个进程不能得到锁资源时，并不会放弃CPU而进入阻塞状态，而是不断地在那里进行循环检测，因此称它为自旋锁。自旋锁是对于互斥锁而言的

• TestAndSet和Swap都属于自旋锁

2.3.4信号量机制

概念

信号量（Semaphore）是一种用于同步多个进程或线程的同步原语。它允许多个进程或线程在同一时刻访问有限的共享资源，从而避免了资源竞争和死锁等问题。信号量通常被用于实现线程同步、进程同步和进程间通信（IPC）等功能。

我的理解：所谓信号量，就是表示某一种一种资源，而信号量的值表示该资源的剩余可用的数量

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

一对原语：

• wait(s) 申请

• signal(s) 释放

• s为信号量

• 这两段原语简称为P、V操作，即：ait(s)=P(s) signal(s)=V(s)

  整数型信号量

  当s为整型，来表示系统中某种资源的数量：

  缺点:不能遵循让权等待的原则存在忙等的问题

  
  int S=1;//初始化整型信号量s,表示当前系统中可用的打印机资源数
  void wait (int S){//wait原语，相当于“进入区”
  while (S <0);//如果资源数不够，就一直循环等待
  S=S-1://如果资源数够，则占用一个资源
  }
  void signal(intS){//signal原语，相当于“退出区"
  S=S+1;//使用完资源后，在退出区释放资源
  }

//进程P0:
wait(S);//进入区，申清资源
//使用打印机资源.，，//临界区，访问资源
signal(S);//退出区，释放资源

  ### 记录型信号量

  优点：遵循让权等待的原则，不会出现忙等

  ```C++
/*记录型信号量的定义*/
typedef struct{
int value;//剩余资源数
struct process *L;//等待队列
}semaphore;

/*某进程震要使用资源时，通过wait原语申请*/
void wait (semaphore s){
    S.value--;
    if (S.value<0)block (S.L);//把当前进程主动阻塞起来，并挂入等待队列
}

/*进程使用完资源后，通过signal原语释放*/
void signal (semaphore s){
    s.value++;
    if (S.value <=0)wakeup(S.L);//从等待队列中唤醒，从阻塞态变为就绪态
)
}

信号量的应用

1.实现进程互斥

给每个临界区设置一个初始信号值为1的信号量，并在进入区设置V操作，退出区设置P操作。

typedef struct{
int value;//剩余资源数
struct process *L;//等待队列
}semaphore;

semaphore mutex
mutex.value=1//初始化信号量为1
//p、v操作
wait(mutex)
临界区代码
signal(mutex)

2.实现进程同步

这个图是画的很清楚了，总的原则就是"先V后P"(先做的后面放V操作，后做的前面放P操作)，例：s2之前得做s1，那么就是s1的后边放v操作，s2的前面放p操作

需要注意的是：信号量必须成对地出现在两个不同的进程中，并且其位置也要相互匹配。

2.3.5经典进程的同步问题

生产者消费者问题

问题描述：

需要考虑的：

• 能否互斥访问共享资源(不能同时访问共享数据)；

• 当公共容器满时，生产者能否继续生产(生产者应阻塞并唤醒消费者消费)；

• 当公共容器为空时，消费者能否继续消费(消费者应阻塞并唤醒生产者生产)。

• 生产者和消费者对缓冲区互斥访问是互斥关系(异步的)，

• 生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。

  前驱图：

  

  伪代码实现：

  ```C++
  //信号量：
  semaphore mutex=1;//互斥信号量，实现对缓冲区的互斥访问
  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)//增加一个空闲缓冲区的数量
使用产品;
}
}

### 吸烟者问题(一对多)

问题描述：可以生产多个产品的单生产者

 ![20230714140359](https://img.xlonglong.cn/img/20230714140359.png)

**解决思路**：

- 桌子上同一时刻能放两种材料：

  - 1:纸+胶水

  - 2:烟草+胶水

  - 3:烟草+纸

- 同步关系：

  - 桌上有组合一→第一个抽烟者取走东西

  - 桌上有组合二→第二个抽烟者取走东西

  - 桌上有组合三→第三个抽烟者取走东西

  - 发出完成信号→供应者将下一个组合放到桌上

![20230714140415](https://img.xlonglong.cn/img/20230714140415.png)

**伪代码实现**：

```C++
semaphore offerl=0;//桌上组合一的数量
semaphore offer20;//桌上组合二的数量
semaphore offer3=0;//桌上组合三的数量
semaphore finish=0;//抽烟是否完成
int i=0;//用于实现三个抽烟者轮流抽烟

provider (){
while(1){
    if(i==0){
      将组合一放桌上;
     V(offerl);
    }
    else if(i==1){
      将组合二放桌上;
        V(offer2);
    }
    else if(i==2){
     将组合三放桌上：
        V(offer3);
    }
    i=(1+1)%3;
    P(finish);
    }
}

smoker1 (){
while(1){
    P(offerl);
    从桌上拿走组合
    一;卷烟;抽掉;
    V(finish);
    }
}
smoker2 (){
while (1){
    P(offer2);
    从桌上拿走组合;
    二;卷烟;抽掉;
    V(finish);
    }
}

smoker3 (){
while(1){
    P(offer3);
    从桌上拿走组合
    三;卷烟;抽掉;
    V(finish);
    }
}

读者-写者问题

问题描述：

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

总的来说就是：

• 读者：只读取数据，不修改

• 写者：读取和修改数据

• 要求：“读 – 读”允许，“读 – 写”互斥， “写- 写”互斥

思路：

• 两类进程：写进程、读进程

• 互斥关系：写进程一写进程、写进程一读进程。读进程与读进程不存在互斥问题。

伪代码实现：

semaphore rw=1;//用于实现对共享文件的互斥访问
int count =0;//记录当前有几个读进程在访问文件
semaphore mutex=1;//用于保证对count变量的互斥访问
//writer
writer(){
 p(rw);//写之前上锁
  写文件;
  V(rw);

}

reader(){
  while(1){

    p(mutex);//对访问count变量上锁
     if(count==0) p(rw),//如果读者为0，则读之前上锁
    count++;
    v(mutex)//解锁count变量
      读文件;
     p(mutex)
       count--;
    if(count==0) v(rw);//当前没有正在读的了，解锁
    v(mutex);
  }  
}

该操作是读者优先策略：只要有读者正在读状态，后来的读者都能直接进入，如读者持续不断进入，则写者就处于饥饿。

如果要实现读写公平,也就是先来先服务， 需要加一个信号量。实现的伪代码是：

semaphore rw=1;//用于实现对共享文件的互斥访问
int count =0;//记录当前有几个读进程在访问文件
semaphore mutex=1;//用于保证对count变量的互斥访问
semaphore w=1; //用于避免读者优先
//writer
writer(){
  p(w);//
 p(rw);
  写文件;
  V(rw);
  v(w)

}

reader(){
  while(1){
   p(w)
    p(mutex);
     if(count==0) p(rw),
    count++;
    v(mutex);
    v(w)
      读文件;
     p(mutex)
       count--;
    if(count==0) v(rw);
    v(mutex);
  }  
}

哲学家进餐问题

问题描述：

问题分析：

• 关系分析：系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系

• 一个哲学家必须持有两个临界资源才能开始吃饭，要避免临界资源分配不当的问题

• 信号量设置：semaphore chopstick[5]={1,1,1,1,1};

• 一共五个人，所以最多可以有四个人进入临界区，可以保证至少有一个哲学家是可以拿到左右两只筷子的，避免了死锁、

解决的两种死锁方法

1.仅当两边筷子都能拿起来的时候才会拿筷子

伪代码实现：

//信号量
semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;//互斥的取筷子
p(int i) { //i号哲学家的进程
  while(1){
    P(mutex）;
    P(chopstick[i]);    //拿左
    P(chopstick[(i+1)%5])；//拿右
    V(mutex);
     吃饭;
    V(chopstick[i]);//放左
    V(chopstick[(i+1)号5])；//放右
    思考…;
}  
}

2、仅当两边筷子都能拿起来的时候才会拿筷子

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

semaphore fork[5];         // 信号量初值为1
p(int i) {  // 哲学家编号：0 － 4
    while (1) {

        if (i % 2 == 0) {
            P(chopstick[i]);            // 去拿左边的筷子
            P(chopstick[(i+1)%5]);  // 去拿右边的筷子
        } else {
            P(chopstick[(i+1)%5]);  // 去拿右边的筷子
            P(chopstick[i]);            // 去拿左边的筷子
        }
        吃饭;                  
      V(chopstick[i]);            // 放下左边的筷子
       V(chopstick[(i+1)%5]);  // 放下右边的筷子
    }
}

2.3.6 管程

信号量机制存在的问题：编写程序困难、易出错

管程是一种高级语言同步机制，也是为了实现多进程的同步和互斥的

定义

6. 局部于管程的共享数据结构说明

7. 对该数据结构进行操作的一组过程（也就是函数）：

8. 对局部于管程的共享数据设置初始值的语句：

9. 管程有一个名字。

特征:

10. 局部于管程的数据只能被局部于管程的过程所访问：

11. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据：

12. 每次仅允许一个进程在管程内执行某个内部过程。

条件变量

• 条件变量是管程内的等待机制：进入管程的进程因资源被占用而进入等待状态
  每个条件变量表示一种等待原因，对应一个等待队列

• 等待(Wait())操作 ：将自己阻塞在等待队列中，唤醒一个等待者或释放管程的互斥访问

• 唤醒(Signal())操作：将等待队列中的一个进程唤醒，等待队列为空，则等同空操作

实现：

用管程解决生产者消费者问题

class ProducerConsumer
{
    condition full,empty;//条件变量用来实现同步（排队）
    int count0;//缓冲区中的产品数
    void insert(Itemitem){//把产品item放入缓冲区
        if (count ==N) wait (full);
        count++;
        insert item (item);
        if (count==1)signal(empty);
    }
    Item remove（){//从缓冲区中取出一个产品
        if (count ==0) wait (empty);
        count--;
        if (count ==N-1)signal(full);
        return remove_item();
    }
}

//生产者进程
producer (){
    while(1){
        item=生产一个产品；
        ProdecerConsumer.insert (item);
    }
}
//消费者进程
consumer (){
    while(1){
    item=ProdecerConsumer.remove ()
    消费产品item;
    }
}

我的理解：所谓管程，可以看作一个类，具有一些共享数据和函数以供进程使用，进程在访问共享数据时，是需要调用这些函数接口的。在信号量中要考虑到互斥的特性，但是在管程中，互斥的特性是由编译器实现的,可以保证一个时间段内最多有一个进程在访问缓冲区。而在解决同步问题时，是可以设置条件变量和通过等待唤醒操作解决的，

管程是封装的思想

2.3.7死锁的概念

概念：

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各、进程都限塞，都无法向煎推进的现象。

所以发生死锁的发生是至少有两个或两个以上的进程同时发生死锁。发生死锁的进程是处于阻塞态的

出现死锁的条件：

• 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待
  这种资源)。

• 不可剥夺条件：不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

• 请求和保持条件：进程保持至少一个资源，并正在等待获取其他进程持有的资源,且对自己已有的资源不放

• 循环等待条件：循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程己获得的资源同时被下一个进程所请求 注：循环等待是死锁的必要不充分条件

什么时候会发生死锁：

• 1.对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。

• 2.进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2,之后进程P1又紧接着申请资源R2,而进程P2又申请资源R1,
  两者会因为申请的资源被对方占有而阻塞，从而发生死锁。

• 3.信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系资源)
  总之，对不可剥夺资源的不合理分配，可能导致死锁。

2.3.8死锁的处理策略

1.预防死锁

• 破坏互斥条件：封装成可同时访问

  • 缺点：该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

• 破坏不剥夺条件

  • 方案一：当某个进程清求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

  • 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用

  • 缺点：、

  1. 实现起来比较复杂

  2. 释放己获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。

  3. 反复地申请和释放资源会增加系统开销，降低系统吞吐量。

  4. 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

• 破坏请求条件和保持条件

  • 静态分配方法：即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，
    不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

  • 缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

• 破坏循环等待条件

  • 顺序资源分配法:首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，
    同类资源（即编号相同的资源）一次申请完。

  • 原理分析：一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，己持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

  • 缺点：

  1. 不方便增加新的设备，因为可能
     需要重新分配所有的编号：

  2. 进程实际使用资源的顺序可能和
     编号递增顺序不一致，会导致资源
     浪费：

  3. 必须按规定次序申请资源，用户
     编程麻烦

2.避免死锁

建立安全序列：所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

• 如果能找不到安全序列，那就进入了不安全状态，如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

• 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

银行家算法

• 定义：银行家算法是荷兰学者Dijkstra(这个哥真的牛)为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁

• 核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进
  入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

• 代码实现

  • 数据结构：

  • n = 进程数量, **m** = 资源类型数量

  • Max（总需求量）: n×m矩阵
    进程Pi最多请求类型Rj的资源 Max[i,j] 个实例

  • Available（剩余空闲量）：长度为m的向量
    当前有 Available[j] 个类型Rj的资源实例可用

  • Allocation（已分配量）：n×m矩阵
    进程Pi 当前分配了 Allocation[i, j] 个Rj的实例

  • Need（未来需要量）：n×m矩阵
    进程Pi未来需要 Need[i, j] 个Rj资源实例

  • Need[i,j] = Max[i,j] – Allocation[i,j]

  • 初始化:
    Request[i]表示进程Pi的资源请求向量
    Request[i][j]表示进程Pi请求资源Rj的实例个数

  • 循环：

  1. 如果 Request[i][j] <= Need[i][j], 转到步骤2。否则, 拒绝资源申请, 因为进程已经超过了其最大要求

  2. 如果 Request[i][j] <= Available[j], 转到步骤3。否则表示尚无可用的资源, Pi 必须等待,。

  3. 系统试探着把资源分配给进程P,并修改相应的数据（并非真的分配，修改数值只是为了做预判）(预分配)

Available[j] = Available[j] - Request[i][j] ;
Allocation[i][j]= Allocation[i][j] + Request[i][j] ;
Need[i][j]= Need[i][j] – Request[i][j] ;

4. 调用安全状态判断如果返回结果是安全，将资源分配给Pi (实施本次分配）如果返回结果是不安全，系统会拒绝Pi的资源请求 (撤销预分配）

3.死锁的检测和解除

死锁的检测

为了能对系统是否已发生了死锁进行检测，必须

13. 用某种数据结构来保存资源的请求和分配信息：

14. 提供一种算法，利用上述信息来检测系统是否己进入死锁状态。
    

    

• 定期调用死锁检测算法来，搜索图中是否存在死锁，出现死锁时，用死锁恢复机制进行恢复

• 依次消除与不阻塞进程相连的边，直到无边可消

• 死锁定理：若资源分配图是不可完全简化的，说明发生了死锁

死锁的解除

15. 资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给
    其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。

16. 撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能己经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。

17. 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程
    的历史信息，设置还原点。