进程同步：多个相关进程在执行次序上进行协调，使并发执行的进程之间能按照一定的规则共享系统资源，并能很好的合作，从而使进程的执行具有可再现性。
进程之间可能存在互斥或者同步的关系。
互斥(间接相互制约关系)：访问临界资源。临界资源：一段时间内只允许一个进程访问的资源。
同步（直接相互制约关系）：进程合作。
临界区：临界资源必须互斥访问，访问临界资源的代码称为临界区。
进入区：每个进程在进入临界区钱，应先对临界资源进行检查，看是否正被访问。
退出区：在临界区后，用于将临界区正被访问的标志恢复为未被访问的标志。
while(TRUE){
进入区;
临界区;
退出区;
剩余区;
}同步机制应遵循的规则：
（1）空闲让进：临界区无进程访问，让请求进入的进程立即进入
（2）忙则等待：临界区有进程访问，请求进入的进程必须等待
（3）有限等待：要求请求访问临界资源的进程，在有限时间内进入临界区，以免陷入死等。
（4）让权等待：当进程不能进入自己的临界区，应立即释放处理机。
进程同步机制：
硬件实现：关中断
在进入锁测试之前关闭中断，直到完成锁测试并上锁后才打开中断。进程在临界区执行期间，计算机系统不响应中断，不会引发调度或进程切换。
优点：保证了对锁的测试和关锁的连续性和完整性，保证互斥。
缺点：（1）滥用关中断导致严重后果（2）关中断时间过程，影响系统效率,限制处理机交叉执行程序的能力（3）关中断不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程
（2）利用Test and Set指令
通过专门提供的TS指令(原语)
boolean TS(boolean *lock):
boolean old;
old=*lock;
*lock=TRUE;
return old;*lock是FALSE时，表示该资源空闲；
*lock是TRUE时，表示该资源正在被使用；
用 TS指令管理临界区时，为每个临界区设置一个布尔变量lock,由于变量lock代表资源的状态，所以可以把它看成一把锁。
do{
...
while TS(&lock);
critical sectiom;
lock=FALSE;
remainder section;
}while(TRUE);(3)利用swap指令实现进程互斥
该指令称为对换指令，在intel8086中又称XCHG指令，用于交换两个字的内容。
void swap(boolean *a,boolean *b){
boolean temp;
temp=*a;
*a=*b;
*b=temp;
}
为每个临界资源设置一个全局的布尔变量lock,,初值为false,在每个进程中再利用一个局部布尔变量key
do{
key=TRUE;
do{
swap(&lock,&key);
}while(key!=FALSE);
临界区操作
lock=FALSE;
}当lock为TRUE时，说明有进程在占用临界区，swap指令执行后key依然是TRUE。如果占用临界却的进程一直不释放临界区，那么lock一直为 TRUE，那么会一直在循环中等待。
利用上述硬件能够有效地实现进程互斥，但是临界资源忙碌时，其他访问进程必须不断地测试，处于忙等的状态。
信号量实现：
信号量机制：
进程同步工具。从整型信号量经记录型信号量，进而发展为“信号量集"机制。
(1)整型信号量：
表示资源数目的整型量S。除初始化外,仅能通过两个标准的原子操作wait(S）和signal(S)来访问。又称为PV操作。
P操作：
wait(S):
while s<=0;
S--;V操作：
signal(S):
S++(2)记录型信号量
在整型信号量机制中的wait操作,只要是信号量S<=0，就会不断的测试。
因此，该机制并未遵循让权等待的准则，而是使进程处于忙等的状态。
但在采取让权等待的策略后，又会出现多个进程等待访问同一临界资源的情况。
为此，在记录型信号量机制中，除了需要一个用于代表资源数目的整型变量value外,还应该增加应该进程链表指针List,用于链接所有的等待进程。
typedef struct{
int value;
struct process control *list;
}semaphore;
相应的wait(S)和signal(S)操作描述如下：
wait(semaphore *S){
S->value--
if(S->value<0)block(S->list);
}
signal(semaphore *S){
S->value++;
if(S->value<=0)wakeup(S->list);
}说明：
S：资源信号量。
S->value的初值：系统中某类资源的数目
wait操作： 进程请求一个单位资源。
S->value--： 使系统中可供分配的该类资源减1
S->value<0：表示该类资源已分配完毕，因此调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S->list中。
若加1后仍是S->value<=0，则表示在该信号量链表中仍有等待该资源的进程被阻塞，所以还应该调用wakeup原语，将S->list链表中的第一个等待进程唤醒。
S->value初值为1：只允许应该进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。
（3）AND型信号量：
将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。
要么把它所请求的资源全部分配到进程，要么一个也不分配。这样可以避免死锁的发生。
Swait(s1,s2,...,sn);
Ssignal(s1,s2,...,sn);(4)信号量集：
Swait(s1,t1,d1,...,sn,tn,dn);
Ssignal(s1,d1,...,sn,dn);Swait(si,ti,di):如果资源si个数小于t1，则不予分配。如果允许分配，进程对该资源的需求值为di,即进行si=si-d操作。
管程实现：
管程定义：
代表共享数据资源的【数据结构】以及由对该共享数据结构实施操作的【一组过程】组成的资源管理程序。
（1）进程对共享资源的申请、释放和其他操作必须通过这组过程，间接地对共享数据结构实现操作。
（2）每次只能由一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源所有访问的统一管理，有效地实现进程互斥。
管程构成：名称、共享数据结构、操作数据的一组过程、数据初始化
条件变量：
一个进程被阻塞或挂起的条件由多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。
每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供操作wait和signal。
(1)x.wait:调用管程的进程因条件x需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其他进程可以使用该管程。
(2)x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择其中一个，如果没有，继续执行原进程。（信号量singal执行s++，而管程不执行）
管程中包含面向对象的思想，将数据和操作都封装在一个对象的内部，隐藏了实现的细节。
管程内部数据只能通过管程的进程访问；管程的过程只能访问内部的数据。
【管程的特性】
模块化：管程是一个基本程序单位，可以单独编译
抽象数据类型：管程中不仅由数据，而且由对数据的操作
信息掩蔽：管程中的数据只能被管程的过程调用
进程和管程的不同
题目：
进程调度
进程调度的任务：
(1)保存处理机的现场信息：保存当前进程的处理机的现场信息，如程序计数器，多个通用寄存器的内容。
(2)按某种算法选取进程：按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。
(3)把处理器分配给进程：PCB现场信息装入处理器响应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。
进程调度方式：
(1)非抢占方式：一旦处理机分配给某进程后，一直让它运行下去，直至该进程完成。
(2)抢占方式：允许调度程序按某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。
优点：
(1)在批处理系统，可以防止一个长进程长时间占用处理机。
(2)在分时系统中使用抢占式可以实现人机交互。
(3)在实时系统中,抢占方式能满足实时任务的需求。
抢占的常见情况:
优先权高的进程抢占、短进程抢占、时间片抢占。各进程按时间片轮流运行，当一个时间片用完后，便停止了该进程的执行而重新进行调度。抢占的本质是进程还没运行完就被暂停运行，换其他进程运行
进程调度算法：
作业调度算法同样适用于进程调度：FCFS,SJF,HRRN
时间片轮转调度算法(RR)：分时系统，常用时间片轮转调度算法。
在RR调度算法中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔产生一次中断，激活系统中的进程调度程序，将CPU分配给队首进程。
如果时间片未用完，进程运行完，并从就绪队列删除，调度其他进程运行。如果时间片用完，进程未运行完，进程放入队尾。
采用公平的分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。
如果就绪队列上有n个进程，则每个进程每次大约都可获得1/n的处理机时间。
RR调度不会产生饥饿现象，因为就绪队列采用FCFS策略，每个进程都可以获得CPU时间片，只不过短进程可以在时间片内完成，而长进程在时间片内完不成就放到就绪队列末尾，等待下一轮调度。RR调度可以实现人机交互(抢占式调度)。
时间片大小的确定：略大于一次典型的交互所需要的时间
大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。
时间片小，有利于短作业，但是会频繁地执行进程调度和进程上下文的切换，会增加系统的开销。
时间片太长，RR算法退化为FCFS算法。所有进程都能在一个时间片内完成，无法满足短作业和交互式用户的需求。
时间片的引入：
如果进程阻塞或结束，需要进行切换，不会造成CPU资源浪费。但由于只有一个CPU一次只能处理程序要求的一部分，为了能够公平，一种方法就是引入时间片每个程序轮流执行。
优先级调度算法：
非抢占式优先级调度算法：
一旦把处理机分配给就绪队列中的优先级最高的进程后，该进程便一直执行下去直至完成。
抢占式优先级调度算法：
在执行期间，只要出现了另一个优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的程序。
优先权的类型：
静态优先权：在创建进程时确定，在进程的整个运行期间保持不变。
确定静态进程优先权的依据：
进程类型：系统进程优先权高于一般用户进程的优先权
进程对资源的需求：要求少的进程应赋予较高的优先权
用户要求：根据用户要求
动态优先权：在创建进程时所赋予的优先权，可以随进程的推进或随其等待时间的增加而改变。
例：在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。优先权初值低的进程可能升为最高，从而获得处理机。
例：当采用抢占式优先权调度算法时，如果再规定当前进程的优先权随运行时间的推移以速率b下降，可防止一个长作业长期垄断处理机。
多级反馈队列调度算法：使短作业和长作业都可以满意
设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之。优先级越高，时间片越小。每个队列都采用FCFS算法。
当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS等待调度。
当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，转入第二队列的末尾等待调度。否则，放入第三队列队尾....。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行.....
性能：
终端型作业用户：作业通常较小，系统只要使这些作业在第一队列所规定的时间片内，便可使终端型作业用户都感到满意。
短批处理作业用户：对于稍长的短作业，只需在第2-3队列各执行一时间片完成，其周转时间仍然较短。
长批处理作业用户：最后在第n个队列按轮转方式运行。用户不必担心长期作业得不到处理。
