第六章

进程互斥：指并发的进程之间因相互争夺独占型资源而产生的一种竞争制约关系

进程同步：并发进程之间为完成共同任务基于某个条件来协调执行现后关系而产生的协作制约关系

临界区：并发进程中与互斥共享变量有关的程序段被称为”临界区“

互斥共享变量：所代表的资源称为”临界资源“，即依次仅能共给一个进程使用的资源

临界区管理实现的硬件方式：

1. 关中断：关中断 -> 临界区 -> 开中断
2. 测试并设置指令:循环请求锁 -> 临界区 -> 解锁
3. Swap指令：循环请求锁（swap）-> 临界区 -> 解锁

PV操作

1
2
3
4

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

设s为一个记录型信号量，关于s的PV操作原语描述如下：

1. P(s)：将信号s的value值减1，若结果小于0，则执行P操作的进程被阻塞，进入信号量s的list所指队列中，若结果大于0，则执行P操作的进程继续执行
2. V(s)：将信号量s的value值加1，若结果不大于0，则执行V操作的进程从信号量s的list所指的队列中释放一个进程，使其转换为就绪态，自己则继续执行；如结果大于0，则执行V操作的进程继续执行

PV操作与进程同步：

基本思路：定义一个记录型信号量，用于表示可用的资源数，同步信号量与互斥信号量的区别在于，同一个同步信号量的P操作和V操作不在一个进程里

管程

基本思路：将分散在各进程中的临界区集中管理，并将共享资源用数据结构抽象的表示

管程是由若干个局部公共变量及其声明和所有访问这些公共变量的过程所组成的软件模块

管程的问题：wait()操作延迟进程的执行，signal()使得被延迟的进程恢复执行。当某进程在管程中执行signal()之后，另一个被延迟的进程可恢复执行并进入管程。此时会有两个进程同时调用一个管程中的两个过程，造成管程中由两个进程同时进行

霍尔管程：为解决上一问题，假设Q进程在等待，P进程执行signal后，进程Q被释放，此时进程P等待直至进程Q退出管程，或者进程Q等待另一个条件

进程通信

进程通信：交往进程通过信号量实现进程的互斥和同步，这是⼀种低级的通信⽅式。 进程有时需要交换更多的信息（例如：传送数据），这时可以引进IPC（进程通信 机制），进程间用信件来交换信息

1. 基于信件
   1. 直接通信
      1. send(P, 信件)：将信件发送给进程P
      2. receive(Q, 信件)：从进程Q接受信件
   2. 间接通信：进程间发送或接受信件通过一个共享的数据结构——信箱来进行，每个信箱有个唯一的标识符
      1. 发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则，发送信件者被置等待信箱状态
      2. 接受信件：如果指定信箱中有信，则取出信件，并释放信箱的等待者；否则接受信件者被置为等待信箱信件状态
2. 基于字节流的通信
   1. 高级进程通信机制：多个进程可以使用一个共享的消息缓冲区，这个缓冲区将被组织成一个字节流，操作系统有很多类似的机制，如下
      1. 管道
      2. 共享内存
      3. 套接字通信
      4. 信号

死锁

定义：如果在一个进程集合中，每个进程都在等待只能由该集合中的另一个进程才能引发的事件

1. 死锁的防止

产生死锁的必要条件：

1. 互斥
2. 占有和等待
3. 不剥夺
4. 循环等待

静态分配策略：进程必须在执行前就申请它需要的全部资源，并且直到它需要的资源都得到满足后才开始执行

层次分配策略：旨在组织循环等待条件出现；

1. 资源被分成多个层次，一个进程得到某一层的一个资源后，它只能再申请较高一层的资源；
2. 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源；
3. 当另一个进程获得某一层的一个资源后，它想再申请该层的另一个资源，必须先释放该层已占资源

死锁的避免：

银行家算法：检查申请者对各类资源的最大申请量，如果系统现存的各类资源可以满足它的最大需求量，就满足当前需求。

安全序列：姑且这样做，找所有进程中need最少的,然后看available是否满足,满足后此进程排第一；接着在找第二个need最少的,然后依次…..；如果过程中发现不能满足need<available,则换一条路；这样就能快速找出一条序列；如果找不到就代表不安全