操作系统考试复习——第二章 进程控制 同步与互斥
进程控制一般是由OS中的原语来实现的。
大多数OS内核都包含了两大方面的功能：
1.支撑功能：1)中断处理 2)时钟管理 3)原语操作(原语操作就是原子操作。所谓原子操作就是一个操作中所有动作要不全做要不全不做)
2.资源管理功能：1)进程管理 2)存储器管理 3)设备管理
同步与互斥的基本概念：
在多道程序环境下，进程是并发执行的，不同进程之间存在不同的相互制约关系。为了协调进程之间的相互制约关系，引入进程同步的概念。
临界资源：我们将一次只允许一个进程使用的资源称为临界资源。例如在单处理机上面CPU就是临界资源。
同步也称为直接制约关系，是指为了完成某种任务而建立的两个或多个进程。这些进程因为在某些位置上协调他们的工作次序而等待，传递信息所产生的制约关系。进程之间的制约取决于它们之间的相互合作。
互斥也成为间接制约关系，当一个进程进入临界区使用临界资源时另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许访问此临界资源。
临界区：人们把在每个进程中访问临界值资源的那段代码称为临界区。一般来说一个访问临界资源的循环进程描述为：
while(TRUE）
{
进入区
临界区
退出区
剩余区
}
同步机制应遵循的规则：
1.空闲让进：当无进程处于临界区，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
2.忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
3.有限等待：对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入"死等"状态。
4.让权等待(这里的权指的是cpu)：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入"忙等"状态。
硬件同步机制
1.关中断的方式来实现互斥：采用中断的方式来进行硬件同步机制。在锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。
2.利用Test-and-set指令实现互斥
借助TS指令：TS指令的一般性描述如下：*lock=FALSE时表示资源空闲反之表示资源正在被使用
boolean TS(boolean *lock){
boolean old;
old=*lock;
*lock=TRUE;
return old;
}
3.利用swap指令实现进程互斥
该指令称为对换指令
void swap(boolean *a,boolean *b) do{
{ key=True;
boolean temp; do{
temp=*a; swap(&lock,&key)
*a=*b; }while(key != FALSE)
*b=temp; 临界区操作；
} lock=FALSE;
}while(TRUE);
信号量机制
1.整型信号量：
除了初始化之外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问。很长时间以来，这俩操作之前一直被称为p,v操作。
wait(s){
while(s<=0)
s=s-1;
}
signal(s){
s=s+1;
}
2.AND型信号量
将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放；（类似于数据库中的事务）
对若干个临界资源的分配，采取原子操作方式要么全部分配到进程，要么一个也不分配；
为此，在wait操作中，增加了一个“AND”条件，故称为AND同步；
3.信号量集
信号量集是在AND型信号量的基础上实现的，一次可以申请多个单位。
几种特殊情况：
SP(S,d,d)此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不予分配。
SP(S,1,1)此时信号量集已蜕化为一般的记录型信号量(s>1)或互斥信号量(s=1)时。
SP(S,1,0)这是一种很特殊且很有用的信号量操作。当s>=1时，允许多个进程进入某特定区；当s变为0后，将阻止任何进程进入特定区。换言之，它相当于一个开关。
利用信号量机制实现进程互斥：
semaphore s=1;
P1(){
P(s);
进程P1的临界区；
V(s);
}