#操作系统
进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。操作系统要提供“进程同步机制”来解决异步问题。
以管道通信为例： 写进程和读进程并发进行，由于并发必然导致异步性，二者不可预知。所以“写数据”和“读数据”两个操作执行的先后顺序是不确定的，而实际应用中，又必须按照“写数据 -> 读数据”的顺序来执行。
同步又称之为直接制约关系，指为完成某种任务而建立的两个或者多个进程，这些进程因为需要在某些位置协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是来源于他们之间的相互合作。
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源（比如内存，又比如打印机、摄像头这样的I/O设备）。
- 互斥共享 系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
- 同时共享方式 系统中的某些资源，允许一个时间段内由多个进程“同时”对它们进行访问。
临界资源（Critical Section）： 我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。 对临界资源的互斥访问，可以在逻辑上分为如下四个部分：
do {
entry section; // 进入区
critical section; // 临界区
exit section; // 退出区
remainder section; // 剩余区
}
while(true);- 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志（可理解为“上 锁”），以阻止其他进程同时进入临界区。
- 临界区：访问临界资源的那段代码。
- 退出区：负责解除正在访问临界资源的标志（可理解为“解锁”）。
- 剩余区：做其他处理。
★注意：
临界区是进程中访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。临界区也可称为“临界段”。
★为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
- 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
- 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
加入进程
因此有必要实现进程间的互斥。
算法思想： 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。
int turn = 0; // turn 表示当前允许进入临界区的进程号
// turn = 0, 表示当前 0 号进程被允许进入临界区
// P_0 进程：
while(turn != 0); // 1
critical section; // 2
turn = 1; // 3
remainder section; // 4
// P_1 进程
while(turn != 1); // 5
critical section; // 6
turn = 0; // 7
remainder section; // 8算法解释：
- turn 的初值为 0，即刚开始只允许 0 号进程进入临界区。
- 若
$P_1$ 先上处理机运行，则会一直卡在代码5。直到$P_1$ 的时间片用完，发生调度，切换$P_0$ 上处理机运行。 -
代码 1不会卡住$P_0$ ，$P_0$ 可以正常访问临界区，在$P_0$ 访问临界区期间即时切换回$P_1$ ，$P_1$ 依然会卡在代码5。 - 只有
$P_0$ 在退出区将 turn 改为 1 后，$P_1$ 才能进入临界区。 因此，该算法可以实现 “同一时刻最多只允许一个进程访问临界区”。
turn变量背后的逻辑：表达谦让.
单标志法存在的主要问题是：违背“空闲让进”原则。(例如，当处理机是空闲状态的时候，如此时某进程，进程1表示当前我需要使用处理机，而处理机此前刚刚被进程1执行完毕，那么由于此前会做出谦让动作，所以导致目前处理机无法直接使用。)
算法思想：
设置一个布尔型数组 flag[ ]，数组中各个元素用来标记各进程想进入临界区的意愿。
比如“flag[0] = ture” 意味着 0 号进程 flag[i] 设为 true，之后开始访问临界区。
bool flag [2]; // 表达进入临界区意愿的数组
flag[0] = false; // 初始化：两者都不想进入临界区
flag[1] = false;
// P_0 进程
while (flag [1]); // 1 如果此时P_1 想进入临界区，P0 就需要循环等待
flag[0] = true; // 2 标记为P0 进程想要进入临界区
critical section; // 3 访问临界区
flag[0] = false; // 4 访问完临界区，修改标记为 P0 不想使用临界区
remainder section;
// P_1 进程
while (flag [0]); // 5
flag[1] = true; // 6
critical section; // 7
flag[1] = false; // 8
remainder section;问题：若两个程序并发执行，即按照 1、5、2、6、3、7...... 的顺序执行，
flag[i]背后的逻辑含义： “表达意愿”
因此，双标志先检查法的主要问题是：违反“忙则等待”原则。 原因在于，进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。
算法思想： 双标志先检查法的改版。前一个算法的问题是 先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。 因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
bool flag [2]; // 表达进入临界区意愿的数组
flag[0] = false;
flag[1] = false; // 刚开始的时候设置为两个进程都不想进去临界区
// P0 进程
flag[0] = true; // 1 标记为 P0 进程想要进入临界区
while (flag [1]); // 2 如果此时 P1 想进入临界区，P0 就需要循环等待
critical section; // 3 访问临界区
flag[0] = false; // 4 访问完临界区，修改标记为 P0 不想使用临界区
remainder section;
// P1 进程
flag[1] = true; // 5
while (flag [0]); // 6
critical section; // 7
flag[1] = false; // 8
remainder section;若按照 1、5、2、6….的顺序执行，
flag[i]背后的逻辑含义： “表达意愿”
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。 两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。
算法思想： 结合双标志法、单标志法的思想。 如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。
bool flag [2]; // 表达进入临界区意愿的数组，初始值都是 false
// 背后的含义：“表达意愿”
int turn; // turn 表示有限让哪个进程进入临界区
// 背后的含义：“谦让”
// P0 进程
flag[0] = true; // 1 表达 P0 进程有有意愿进入临界区
turn = 1; // 2 优先让 P1 进程使用临界区
while (flag [1] && turn == 1); // 3 如果对方有意愿 并且
// 最后一次是自己谦让，则需要继续等待
critical section; // 4
flag[0] = false; // 5 访问完表示自己不想再访问了
remainder section;
// P1 进程
flag[1] = true; // 6
turn = 0; // 7
while (flag [0] && turn == 0); // 8
critical section; // 9
flag[1] = false; // 10
remainder section;算法的进入区完成以下几件事:
- 主动争取（把flag 置成true）；
- 主动谦让（把turn 设置成对方）；
- 检查对方是否也想使用临界资源， 且最后一次是不是自己说了“客气话”。
Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然未遵循让权等待的原则。Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。
利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）。
关中断
-----临界区访问-----
开中断- 优点：简单、高效
- 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）。
TestAndSet 简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令，
TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
以下是用C语言描述的逻辑：
// 布尔型共享变量 lock 表示当前临界区是否被加锁
// true 表示已经枷锁， false 表示未加锁
bool TestAndSet(bool *lock)
{
bool old;
old = *lock; // 用于存放lock 原来的值
*lock = true; // 无论之前是否已经加锁，都将lock值设为true
return old; // 返回lock原来的值
}以下是使用TSL指令，实现互斥的算法逻辑：
while (TestAndSet(&lock)); // “上锁”并“检查”
临界区代码段...
lock = false; // “解锁”
剩余区代码段...代码说明：
若刚开始 lock 是 false，则 TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。
若刚开始 lock 是 true，则执行 TLS 后 old 返回的值为 true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
- 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
- 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行
TSL指令，从而导致“忙等”。
有的地方也叫 Exchange 指令，或简称 XCHG 指令。
Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
以下是用C语言描述的逻辑:
// swap指令的作用是交换两个变量的值
void Swap (bool *a, bool *b)
{
bool temp;
temp = *a;
*a = *b;
*b = temp;
}以下是使用Swap指令 实现互斥的算法逻辑，
lock表示当前临界区是否被加锁
bool old = true;
while (old == true)
{
Swap (&lock, &old);
}
临界区代码段...
lock = false;
剩余区代码段...逻辑上来看 Swap 和 TSL 并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old 变量上），再将上锁标记 lock 设置为 true，最后检查 old.
如果 old 为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。
- 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
- 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法） 进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）
- 在双标志先检查法中，进入区的“检查”、“上锁” 操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；
- 所有的解决方案都无法实现“让权等待”。
1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法 —— 信号量机制。
用户进程可以通过使用操作系统提供的一对原语来对信号量（Semaphore）进行操作，从而很方便的实现了进程互斥、进程同步。
- 信号量其实就是一个变量，可以用一个信号量（可以是一个整数，也可以是更复杂的记录型变量）来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。
- 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语：wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。
wait、signal原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。
因此常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)。
用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。
与普通整数变量的区别：对信号量的操作只有三种，即
初始化、P操作、V操作。
int S = 1; // 初始型整型信号量s，表示当前系统中可用的打印机资源数
void wait (int S) // wait 原语，相当于“进入区”
{
while (S <= 0); // 循环检查，是否当前资源已经不够了
S--; // 如果资源数够，则占用一个资源
}
void signal (int S) // signal 原语，相当于“退出区”
{
S++; // 使用完资源后，在退出区释放资源
}进程
// ...
wait (S); // 进入区，申请资源
// 使用打印机资源... // 临界区，访问资源
signal(S); // 退出区，释放资源
// ...进程
// ...
wait (S); // 进入区，申请资源
// 使用打印机资源... // 临界区，访问资源
signal(S); // 退出区，释放资源
// ......
进程
// ...
wait (S); // 进入区，申请资源
// 使用打印机资源... // 临界区，访问资源
signal(S); // 退出区，释放资源
// ...在任何一个进程开始执行的时候，进入程序内部执行检查操作，检查信号量资源是否被完全占据，如果被占据，就一直忙等待，等有空闲信号量资源的时候，再占据这个信号量。“检查”和“上锁”一气呵成，避免了并发、异步导致的问题。 存在的问题：不满足“让权等待”原则，会发生“忙等”（忙等，busy wait，当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环，陷入忙等状态，连续测试一个变量直到某个值出现为止）。
整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。
/* 记录型信号量的定义 */
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} Semaphore;
/* 某进程需要使用资源时，通过wait原语申请 */
void wait(Semaphore S)
{
S.value--;
if (S.value < 0) {
block (S.L);
}
}如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，并把挂到信号量 S 的等待队列（即阻塞队列）中。
/*进程使用完资源后，通过signal 原语释放*/
void signal (Semaphore S)
{
s.value++;
if (S.value <= 0) {
wakeup(S.L);
}
}释放资源后， 若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态。
注意理解信号量背后的含义，一个信号量对应一种资源。 信号量的值 = 这种资源的剩余数量（信号量的值如果小于0，说明此时有进程在等待这种资源）
P( S )—— 申请一个资源S，如果资源不够就阻塞等待；V( S )—— 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。
对信号量 S 的一次 P 操作意味着进程请求一个单位的该类资源，因此需要执行 S.value--，表示资源数减1，当S.value < 0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞（当前运行的进程从运行态 -> 阻塞态），主动放弃处理机，并插入该类资源的等待队列 S.L 中。
可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。
对信号量 S 的一次 V 操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是 S.value <= 0，表示依然有进程在等待该类资源，因此应调用wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态 -> 就绪态）。
- 实现方法
- 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）
- 设置互斥信号量
mutex，初值为 1 - 在进入区
P(mutex)—— 申请资源 - 在退出区
V(mutex)—— 释放资源
信号量
mutex表示“进入临界区的名额”。
/*记录型信号量的定义*/
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} Semaphore;
/* 信号量机制实现互斥 */
Semaphore mutex = 1;
P1()
{
// ...
P(mutex); // 使用临界区前加锁
// 临界区代码段
V(mutex); // 使用临界区后解锁
// ...
}
P2()
{
// ...
P(mutex);
// 临界区代码段
V(mutex);
// ...
}
★注意：
对不同的临界资源需要设置不同的互斥信号量。
P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒。
进程同步：要让各并发进程按要求有序地推进。
P1()
{
代码 1;
代码 2;
代码 3;
}
P2()
{
代码 4;
代码 5;
代码 6;
}比如:
若
- 用信号量实现进程同步：
- 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）；
- 设置同步信号量 S, 初始为 0；
- 在“前操作”之后执行 V(S)；
- 在“后操作”之前执行 P(S)；
/* 信号量机制实现同步 */
Semaphore S = 0;
P1()
{
代码 1;
代码 2;
V(S);
代码 3;
}
P2() // P2 的执行需要依赖一种信号量资源S，而这种资源只能由P1 释放，因此保证必须 P1 后再 P2
{
P(S);
代码 4;
代码 5;
代码 6;
}- 若先执行到
V(S)操作，则S++后S = 1。之后当执行到P(S)操作时，由于S = 1，表示有可用资源，会执行S--，S 的值变回 0，P2 进程不会执行block原语，而是继续往下执行代码4。
执行顺序 1、2、4、5、6。保证代码4在代码2之后执行
- 若先执行到
P(S)操作，由于S = 0，S--后S = -1，表示此时没有可用资源，因此P操作中会执行 block 原语，主动请求阻塞。 - 之后当处理机交还处理进程P1，执行完代码2，继而执行
V(S)操作，S++，使 S 变回 0，由于此时有进程在该信号量对应的阻塞队列中，因此会在 V 操作中执行wakeup原语，唤醒 P2 进程。这样 P2 就可以继续执行 代码4 了。
前V后P
信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源。
有如下几个进程，必须满足如图的程序执行顺序：其中进程 P1 中有句代码 S1，P2 中有句代码 S2 ，P3中有句代码S3 …… P6 中有句代码 S6。这些代码要求按如下前驱图所示的顺序来执行：
其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）因此：
- 要为每一对前驱关系各设置一个同步信号量；
- 在“前操作”之后对相应的同步信号量执行 V 操作；
- 在“后操作”之前对相应的同步信号量执行 P 操作；
代码实现：
// 为每一个前驱关系各设置一个同步信号量，途中一共是7对前驱关系
// 分配7个相应的同步信号量：a、b、c、d、e、f、g
// P1 会导致P2 和 P3程序，所以需要先使用 V操作释放a、b
P1()
{
...
S1;
V(a);
V(b);
...
}
// 由于P1 对a的释放，才可以使得P2 执行，因此在这里执行 P操作，占用a
P2()
{
...
P(a);
S2;
V(c); // 释放c、d资源
V(d);
...
}
P3()
{
...
P(b); // 占用b 资源
S3;
V(g); // 释放g 资源
...
}
P4()
{
...
P(c); // 占用c 资源
S4;
V(e); // 释放e 资源
...
}
P5()
{
...
P(d); // 占用d 资源
S5;
V(f); // 释放f 资源
...
}
P6()
{
...
P(e); // 占用e 资源
P(f); // 占用f 资源
P(g); // 占用g 资源
S6;
...
}