1）进程的并发执行
a.进程的特征：
并发：进程的执行是间断性的；进程的相对执行速度是不可预测的
共享性：进程/线程之间的制约性
不确定性：进程执行的结果与其执行的相对速度有关，是不确定的
b.进程并发执行的问题：
两个进程的关键活动出现交叉
2）进程互斥
竞争条件：两个或多个进程在读写某些共享数据，而最后结果取决于进程运行的精确时序
进程互斥：由于各进程要求使用共享资源（变量、文件等），而这些资源的使用要排他性使用，
各进程之间竞争使用这些资源
临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源称为临界资源或互斥资源或共享变量
临界区：各进程中对某个临界资源（共享变量）实施操作的程序片段
临界区（互斥区）的使用原则：没有进程在临界区，想进入临界区的进程可进入
不允许两个进程同时处于临界区中
临界区外运行的进程不得阻塞其他进程进入临界区
不得使进程无限期等待进入临界区
a.进程互斥的软件解决方案
忙等待（busy waiting）：进程在得到临界区访问权之前，持续测试而不做其他事情
自旋锁Spin lock（多处理器）
优先级反转（倒置）
解法一：(当初值为false的P进程执行完while(free);后离开CPU，Q进程开始执行，当进入临界区后离开CPU
（时间片用完之类的），P进程继续往下执行，也进入临界区，不满足临界区的使用原则，是个错误的解法）
free:临界区空闲标志：true有进程在临界区，false无进程在临界区；初值：false
P:…… Q:……
while(free); while(free);
free = true; free = true;
临界区 临界区
free = false free = false
启示：把while(free);free = true;这两句封装成lock()函数，做成原子操作，就是正确的解法
free = false;封装成一个unlock()函数，原语操作
解法二：（P进程等待进入临界区，但Q一直不想进入临界区，P也不能进临界区，也就是Q进程阻止了P进程进临界区，
不满足临界区的使用原则，是不正确的）
turn：谁进临界区的标志：true：P进临界区，false：Q进程进临界区；初值任意
P: Q:
…… ……
while(not turn); while(turn);
临界区 临界区
turn = false; turn = true;
…… ……
解法三：（P进程执行pturn = ture;后，时间片用完，Q进程也想进临界区，执行qturn = ture;便一直循环在while(pturn);
Q的时间片用完后，P继续执行，也在不断循环while(qturn);【Alten you问题】,不满足临界区的使用原则）
pturn,qturn:初值为false
P进入临界区的条件：pturn ^ not qturn
Q进入临界区的条件：not pturn ^ qturn
P: Q:
…… ……
pturn = true; qturn = true;
while(qturn); while(pturn);
临界区 临界区
pturn = false; qturn = false;
…… ……
解法四——DEKKER算法：
在解法3的基础上引入turn变量，由turn决定在两个进程都想进临界区是让谁进
P: Q:
… … … …
pturn = true; qturn = true;
while(qturn){ while(pturn){
if(turn == 2){ if(turn == 1){
pturn = flase; qturn = false;
while(turn == 2); while(turn == 1): //忙等待
pturn = true; qturn = true;
} } } }
临界区 临界区
turn = 2; turn = 1;
pturn = false; qturn = false;
解法五——PETERSON算法(如果两个进程都想进临界区，先给turn赋值的先进临界区）
进程i:
……
enter_region(i);
临界区
leave_region(i);
……
#define FALSE 0
#define TRUE 1
#define N 2 //进程的个数
int turn; //轮到谁？
int interested[N]; //兴趣数组，初始值为FALSE
void enter_region(int process) // process = 0 or 1
{
int other; // 另外一个进程的进程号
other = 1 - process;
interested[process] = TRUE;
turn = process; // 设置标志位
while(turn == process && interested[other] == TRUE);
}
void leave_region(int process)
{
interested[process] = FALSE;
}
b.进程互斥的硬件解法
解法一——中断屏蔽方法（“开关中断”指令）：
执行“关中断”指令
l临界区操作
执行“开中断”指令
优缺点：
简单高效；代价高，限制CPU并发能力（临界区的大小）；不适用于多处理器；适用于操作系统本身，不适于用户进程
解法二——“测试并加锁”指令：（把总线锁住，先读后写后，打开总线）
TSL 指令：TEST AND SET LOCK
enter_region:
TSL REGISTER,LOCK | 复制锁到寄存器并将锁置1
CMP REGISTER,#0 | 判断寄存器内容是否为零
JNE enter_region | 若不是零，跳转到enter_region
RET | 返回调用者，进入了临界区
leave_region:
MOVE LOCK,#0 | 在锁中置0
RET | 返回调用者
解法三——“交换”指令：
XCHG指令：EXCHANGE（在一条指令结束的时候，把两个位置上的内容交换）
enter_region:
MOVE REGISTER，＃１ | 给寄存器中置1
XCHG REGISTER,LOCK | 交换寄存器与锁变量的内容
CMP REGISTER，＃０ ｜ 判断寄存器内容是否是零
JNE enter_region | 若不是零，跳转到enter_region
RET | 返回调用者，进入了临界区
leave_region:
MOVE LOCK,#0 | 在锁中置0
RET | 返回调用者
3）进程的同步
指系统中系统多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务
生产者/消费者问题（有界缓冲区问题）
问题描述：一个或多个生产者产生某种类型的数据放置在缓冲区中
有消费者从缓冲区中取数据，每次取一项
只能有一个生产者或消费者对缓冲区操作
#define N 100 void consumer(void) int count = 0; { int item; void producer(void) while(TRUE){ int item; if(count == 0) sleep(); while(TRUE) item = remove_item(); { count = count - 1; item = produce_item(); if(count == N-1) if(count == N) sleep(); wakeup(producer); insert_item(item); consume_item(item); count = count + 1; } if(count == 1) } wakeup(consumer); } }
4）信号量及PV 操作
a.信号量：一个特殊的变量；用于进程间传递信息的一个整数值
定义：stuc semaphore
{
int count;
queueType queue;
}
信号量说明：semaphore s;
对信号量可以实施的操作：初始化，P，V
P、V操作为原语操作
P、V操作定义：
P(s) V(s)
{ {
s.count --; s.count ++;
if(s.count < 0) if(s.count <= 0) // 小于零说明原来的队列上有进程在等
{ {
该进程状态设置为阻塞态； 唤醒相应等待队列s.queue中等待的一个进程；
将该进程插入相应的等待队列s.queue末尾； 改变其状态为就绪态，并将其插入就绪队列；
重新调度； }
} }
}
b.用P、V操作解决进程间互斥问题
分析并发进程的关键活动（涉及到共享变量的语句、代码），划定临界区
设置信号量mutex，初值为1
在临界区前实施P(mutex)
在临界区之后实施V(mutex)
c.用信号量解决生产者/消费者问题
#define N 100 // 缓冲区个数
typedef int semaphore; // 信号量是一种特殊的整数型数据
semaphore mutex = 1; // 互斥信号量：控制对临界区的访问
semaphore empty = N; // 空缓冲区的个数
semaphore full = 0; // 满缓冲区的个数
void producer(void) void consumer(void) { { int item; int item; while(TRUE) while(TRUE){ { item = produce_item(); P(&full); P(&empty); P(&mutex); //两个P操作的顺序一定不能改变 P(&mutex); item = remove_item(); insert_item(item); V(&mutex); V(&mutex); V(&empty); //两个V操作顺序可以改变 V(&full); consume_item(item); //不要放在V操作之前，那样会扩大临界区的范围 } } } }
d.用信号量解决读者/写者问题
问题描述：多个进程共享一个数据区，这些进程分两组：
读者进程：只读数据区中的数据；写者进程：只往数据区写数据
满足条件：允许多个读者同时执行读操作；不允许多个写者同时操作；不允许读者、写者同时操作
第一类读者写者问题：读者优先
如果读者执行：无其他读者、写者，该读者可以读
若已有写者再等，但有其他读者正在读，则该读者也可以读
若有写者正在写，该读者必须等
如果写者执行：无其他读者、写者，该写者可以写
若有读者正在读，该写者等待
若有其他写者正在写，该写者等待
void reader(void) { while(TRUE) { P(mutex); rc = rc + 1;//rc也是临界资源，所以需要P、V操作 if(rc == 1) P(W);//第一个读者 V(mutex); 读操作 P(mutex); rc = rc - 1; if(rc == 0) V(w);//最后一个读者 V(mutex) ; 其他操作 } } void writer(void) { while(TRUE) { …… P(w) ; 写操作 V(w) ; } }