表-进程同步 |
进程同步目的 | 对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资源（互斥）和相互合作（同步），使程序的执行具有可再现性 |
两种制约关系 | 1) 间接制约关系—互斥：用于资源共享（共享的资源为间接的制约因素） 2) 直接制约关系—同步：用于相互合作 互斥也是一种同步。 |
临界资源访问 | 临界资源 | 各个进程应采用互斥方式实现对临界资源的共享 |
访问临界资源的进程的代码 | 临界区 | 进程中访问临界资源的那段代码称为临界区。若能保证各个进程互斥地进入自己的临界区，便可以实现各个进程对临界资源的互斥访问。 |
进入区 | 进程进入临界区前用于检查欲访问的临界资源是否正被访问，若未被访问，设置临界资源正被访问的标志的那段代码。 |
退出区 | 将临界资源正被访问的标志恢复为未被访问的那段代码。 |
剩余区 | 除进入区、临界区及退出区外的代码。 |
原语 | 由若干条指令组成，用于完成一定功能，作为原子操作不可分割（要么全做，要么全不做）的过程。 |
进程同步机制 | 同步机制遵循的四条准则 | 1) 闲则让进 无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区。 2) 忙则等待 有进程处于临界区时，其他请求进入临界区的进程必须等待。 3) 有限等待（防死等） 对要求访问临界区的进程，应保证在有限时间内能进入自己的临界区。 4) 让权等待（防忙等） 当进程不能进入自己的临界区时，应立即释放处理机。 |
信号量机制 （每个要访问临界资源的进程都必须自备同步操作wait(S)和signal(S)） | 整型信号量 （用于各进程之间只共享一类临界资源，且同类型的临界资源一次仅申请一个） | 基本思想 | 整型信号量为表示资源数目的整型变量S。信号量除初始化外，只能通过两个原子操作wait和signal来访问，称为P、V操作（P—阻塞，V—唤醒）。 当信号量小于等于0时，wait原子操作便会一直测试，不符合“让权等待”的原则（因是原子操作，不能被中断，会一直占用CPU）。 |
原语 | wait(S) : while S<=0 do no-op; S≔S-1;（先判断，后申请） signal(S) : S≔S+1; |
记录型信号量 （用于各进程之间只共享一类临界资源，且且同类型的临界资源一次仅申请一个） | 基本思想 | 记录型信号量为含有代表资源数目的整型变量和链接所有等待进程的链表指针两个成员变量的记录型结构体。（因含有等待进程链表，故可满足“让权等待”） type semaphore = record value:integer; L:list of process; end |
原语 | procedure wait(S) var S:semaphore begin /* 先提出申请 */ S.value≔S.value – 1; /* 后判断申请能否满足（自我阻塞）*/ if S.value<0 then block(S.L); end procedure signal(S) var S:semaphore begin /* 先释放资源 */ S.value≔S.value + 1; /* 后判断有无等待进程，在S.value 加1后，仍小于等于0说明加1之前S.value 小于0，即存在等待资源的进程 */ if S.value<=0 then wakeup(S.L); end 当S.value初值为1时，该信号量变为互斥信号量。 |
AND型信号量 （用于各进程之间共享两类或更多类临界资源，且同类型的临界资源一次仅申请一个） | 基本思想 | 将进程在整个运行过程中所需要的所有资源，一次性（原子操作）分配给进程，使用完后一次性（原子操作）释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它，可以避免死锁。（Simultaneous—同时） |
原语 | Swait(S1, S2, …, Sn) if S1>=1 and … and Sn>=1 then for i≔1 to n do Si:= Si -1; endfor else place the process in the waiting queue associated with the first Si found with Si <1, and set the program count of this process to the beginning of Swait opetion. /* Swait为原子操作，若不成功则回到起点 */ endif Ssignal(S1, S2, …, Sn) for i≔1 to n do Si:= Si+1; endfor remove all the process waiting in the queue associated with Si into the ready queue. /* 因为只要尚有一类资源未能分配给进程，其他所有可能为之分配的资源也不分配给它，所以释放后n类资源必定同时可得 */ endfor |
信号量集 （用于各进程之间共享两类或更多类临界资源，且同类型的临界资源一次可申请多个） | 基本思想 | 1) 可一次申请多个某一类型的临界资源； 2) 当临界资源数低于某一下限值时，便不予以分配。 |
原语 | S为信号量，t为下限值，d为需求值 Swait(S1, t1, d1, …, Sn, tn, dn) if S1>= t1 and … and Sn>= tn then for i≔1 to n do Si:= Si - di; endfor else place the process in the waiting queue associated with the first Si found with Si <ti, and set the program count of this process to the beginning of Swait opetion. /* Swait为原子操作，若不成功则回到起点 */ endif Ssignal(S1, d2, …, Sn, dn) for i≔1 to n do Si:= Si+ di; endfor remove all the process waiting in the queue associated with Si into the ready queue. /* 因为只要尚有一类资源数少于下限值，其他所有可能为之分配的资源也不分配给它，所以释放后n类资源数必定同时大于各自的下限值 */ endfor |
信号量集的特殊应用 | Swait(S,d,d) | 信号量集中只有一个信号量； 下限值为需求值 |
Swait(S,1,1) | 信号量集中只有一个信号量； 当S初始值大于1时为一般的记录型信号量； 当S初始值等于1时变为互斥信号量。 |
Swait(S,1,0) | 信号量集中只有一个信号量； 当S当前值大于等于1时，允许多个进程进入某特定区，当S当前值变为0后，将阻止任何进程进入特定区，相当于一个可控开关。 |
信号量的应用 | 1) 进程互斥：互斥/间接相互制约，用于资源共享。 实现方式：信号量初始值设为1，且对同一信号量的原子操作wait(S)和signal(S)同时成对出现在共享资源的每个进程中。 2) 前驱关系：同步/直接相互制约，用于相互合作。 实现方式：信号量初始值设为0，且对同一信号量的原子操作wait(S)和signal(S)分别单独出现在相互合作的两个进程中。 当需要同时操作同步信号量和互斥信号量时，为避免死锁，应先执行同步信号量的wait操作，后执行互斥信号量的wait操作，互斥信号量和同步信号量的wait和signal操作不能交叉，即先执行wait操作的信号量后执行其signal操作（类似栈操作先进后出）。 |
管程机制 （管程作为独立模块，用于同步进程，供共享资源的各个进程调用） | 管程定义 | 代表共享资源的数据结构（信号量），以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序（操作原语），共同构成了一个操作系统的资源管理模块，称之为管程。 |
管程组成 | 1) 管程名称； 2) 局限于管程内部的共享数据结构（仅能被局限于管程内部的过程所访问，任何管程外的过程都不能访问它）； 3) 对该数据结构进行操作的一组过程（仅能访问管程内部的数据结构，可调用管程外的过程或被管程外的过程调用）； 4) 对局限于管程内部的共享数据结构的初始化语句； |
条件变量 | 1) 引入目的： 解决忙等问题 2) 每个条件变量的组成： a) 链表：记录因该条件变量而阻塞的所有进程； b) 两个操作：wait和signal 对条件变量的操作仅仅是wait和signal，其含义： x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件发生变化。此时其他进程可以使用该管程。 x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程。 （关于“如果进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时两个进程P和Q哪个先执行”的问题，可以规定管程中的过程所执行的signal操作是过程体的最后一个操作，于是，过程P执行signal操作后立即退出管程，因而进程Q马上被恢复执行） |
