基本概念

原子操作：一个函数（原语）或动作的指令序列不可分割，要么作为一个整体执行（不可中断），要么都不执行。
临界资源：一次仅允许一个进程独自占有使用的不可剥夺资源。
临界区：进程访问临界资源的那一段代码。
互斥：当一个进程正在临界区中访问临界资源时，其他进程不能进入临界区。
同步：合作的并发进程需要按先后次序执行。例如：一个进程的执行依赖于合作进程的消息或信号。当一个进程没有得到来自合作进程的消息或信号时需阻塞等待，直到消息或信号到达才唤醒。
死锁：多个进程全部阻塞，形成等待资源的循环链。
饥饿：一个就绪进程被调度程序长期忽视、不被调度执行。
信号量：用于进程间传递信号的一个整数。在信号两上只可以进行三种操作，即初始化，递增，递减。这三种操作分别都是原子操作。递减作用于阻塞一个进程，递增作用于解除一个进程的阻塞。信号量也称为计数信号量或一般信号量。

并发原理

进程交互

进程之间相互不知道对方的存在：独立的进程，不会在一起工作，这种情况的最好的例子是多个独立进程的多道程序设计，相当于批处理作业，也可以是交互式会话或者混合。尽管这些进程不会一起工作，但操作系统需要知道他们对资源的竞争情况。例如两个无关的应用程序可能都想访问同一个磁盘，文件或者打印机。
进程间接知道对方的存在：这些进程不需要知道对方进程的ID，但他们共享某些对象，比如同一个I/O缓存区。这类进程在共享同一个对象时表现出合作行为。
进程直接知道对方的存在：进程通过ID互相通信，用于合作完成某些活动，同样，这类进程也表现出合作行为。

互斥的要求

强制互斥（忙则等待）：一次只允许一个进程进入临界区。有进程正在临界区执行时，其他请求进程等待；等待进程退出后，从多个请求进程中选择一个进入临界区。
有限等待：请求进程应在有限的等待时间内进入临界区，不能造成进程死锁或饥饿。
有空让进：当临界区空闲时，请求进程可立即进入。
让权等待：进程不能进入临界区时，应释放处理器，避免忙等。

进程互斥

进程互斥是进程之间的间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待。只有当使用临界资源的进程退出临界区后，这个进程才会解除阻塞状态。

比如进程B需要访问打印机，但此时进程A占有了打印机，进程B会被阻塞，直到进程A释放了打印机资源,进程B才可以继续执行。概念如图所示

互斥：硬件的支持

中断禁用

在单处理机器中，并发进程不能重叠，只能交替。此外，一个进程将一直运行，直到它调用了系统服务或者被中断。因此为保证互斥，只需要保证一个进程不被中断就可以了

下列代码为对一个进程实施互斥

while(true){
    /*禁用中断*/
    /*临界区*/
    /*启用中断*/
    /*其余部分*/
}

临界区不能被中断，所以可以保证互斥。

专用机器指令

多处理配置中，几个处理器共享内存，这种情况下，处理器间的行为是无关的，表现为一种对等关系，处理器之间没有支持互斥的中断机制。

两种最常见的指令：比较和交换指令

信号量

信号量：不要求忙等的同步互斥工具。
一种信号量表示一种资源。信号量的值表示可用资源的个数。
当资源不可用时，进程将阻塞（避免忙等）（加入阻塞队列），直到另一进程释放资源时才被唤醒。
信号量s只能被下面的两个原语访问：
- semWait(s) 也称作P(s)操作，wait(s) ——本进程请求分配一个资源
- semSignal(s) 也称作V(s)操作，signal(s) ——本进程释放一个资源

普遍规则

1.**semWaits(s)、semSignal(s)操作必须成对出现。**

2.**用于互斥时，位于同一进程**内，临界区前后。

3.**用于同步时，交错出现于两个合作进程**内。

4.**多个semWait()的次数不能颠倒，否则可能导致死锁。用于同步的semWait(s1)应出现在用于互斥的semWait(s2)之前**。

**5.**多个semSignal()操作的次序可任意。

struct	semaphore {
	
	int count;
	queueType queue;
};
 
void semWait(semaphore s){
	s.count--;
	if(s.count < 0){
		/*把当前进程插入队列*/
		/*阻塞当前进程*/
	}
}
 
void semSignal(semaphore s){
	s.count++;
	if(s.count <= 0){
		/*把进程p从队列中移除*/
		/*把进程p插入就绪队列*/
	}
	
}

互斥

用于互斥时，s的初值为1，取指为1~-(n-1)。

s=1时：有一个临界资源可用，一个进程可进入临界区。
s=0时：临界资源已分配，一个进程已进入临界区。
s<0时：临界区已被占用，**|s|个阻塞进程**正在等待进入。

用于同步时，s初值将>=0

s>=0：可用资源个数（或可进入临界区的进程个数）。
s<0 : 该资源的等待队列长度（阻塞进程个数）。

强信号量：唤醒一个阻塞进程并移出阻塞队列时，采用FIFO移出策略的信号量。

弱信号量：唤醒一个阻塞进程并移出阻塞队列时，采用随机选择移出策略的信号量。

用信号量实现互斥：

const int n = /*进程数 */
semaphore s =1;/*s的初值=1*/
void P(int i){	/*进程Pi*/
	while(true){
		semWait(s);
		/*临界区*/
		semSignal(s);
		/*其他部分*/

	}
}

void main(){/*n个进程并发*/

	parbegin(P(1),P(2),...,P(n));

}

在下列图中，三个进程（A，B，C）访问一个信号量lock保护的共享资源。进程A执行semWait（lock）；由于信号量在本次semWait操作时值为1，因而A可以立即进入临界区，并把信号量的值置为0；当A在临界区时，B和C都执行一个semWait操作并被阻塞；当A退出临界区并执行semWait（lock）时，队列中的第一个进程B现在可以进入临界区。

生产者/消费者问题

通常可描述如下：有一个或多个生产者生产某种类型的数据，并放置在缓冲区中；有一个消费者从缓冲区中取数据，每次取一项；系统保证避免对缓冲区的重复操作，也就是说，在任何时候只有一个主题（生产者或消费者）可以访问缓冲区。

一组生产者进程和一组消费者进程共用一个有sizeofbuffer个缓冲区的缓冲池来交换数据（有限缓冲）。
资源，约束条件及信号量的设置
缓冲池一次只能让一个进程访问。（互斥）

设一信号量s，初值为1。
生产者需要空缓冲来发送数据。（同步）

设一信号量empty，初值为sizeofbuffer。
消费者需要满缓冲来获取数据。（同步）

设一信号量full，初值为0。

void producter(){
	while(true){
		semWait(empty);
		semWait(s);
		/*把数据送到缓冲区*/
		semSignal(s);
		semSignal(full);
	}
}
 
void consumer(){
	while(true){
		semWait(full);
		semWait(s);
		/*从缓冲区取出数据*/
		semSignal(s);
		semSignal(empty);
	}
}

我们给生产者/消费者问题增加一个新的实际约束，即缓冲区是有限的。缓冲区被看作是一个循环寄存器。

生产者和消费者函数可以表示成如下形式（变量in和out初始化为0，n代表缓冲区大小）

下图为用信号量解决有限缓冲区生产者/消费者问题的方法。

管程

基本概念

管程是由一个或多个过程、一个初始过程、一个初始化序列和局部数据组成的软件模块。主要特点如下：

局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
一个进程通过调用管程的一个过程进入管程。
在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。

（个人理解：管程就是将semWait()和semSignal()和共享数据封装起来，使得只能通过调用管程里的相应函数才能实现其功能。这样子做好处在于避免了进程有意/无意的互斥/同步错误。）

条件变量（condition variable）

#表示进程正在等待的资源或原因。只用于维护等待队列，但没有相关联的值。

有两个函数可以操作条件变量：

#cwait(c):条件不满足时，调用cwait(c)的进程被放在条件变量c的等待队列中阻塞。

#csignal(c):唤醒一个条件变量为c的阻塞进程。

管程实现互斥/同步

消息

消息格式

进程通信采用消息传递方式时，进程间的数据交换会以格式化的信息 (Message) 为单位。进程通过操作系统提供的”发送消息/接受消息”两个原语进行数据交换。
在这里插入图片描述
拓展：计算机网络中发送的“报文”其实就是一种格式化的消息。

其实，消息传递方式也分为两种，分别是直接通信方式和间接通信方式。下面对这两种方式进行介绍。

直接通信方式

进程通信采用消息传递的直接通信方式时，消息会直接挂到接收进程的消息缓冲队列上。
举个例子：假如，进程1给进程2发送了两个消息。那进程2的消息缓冲队列如下。
在这里插入图片描述
这种方式类似于寄快递，你写明收件人后，快递公司会把快递送达收件人的手中。在这里，快递就是消息，收件人就是接收进程，快递公司就是操作系统。

间接通信方式

进程通信采用消息传递的直接通信方式时，发送进程会把消息发送到一个中间实体(信箱)中，而接收进程通过某些方法可以取得属于自己的消息，因此，这种方式也被称为”信箱通信方式”。
在这里插入图片描述这种方式类似于电子邮件系统，用户A给用户B发送的邮件会暂存于服务器的信箱中，该邮件会等待用户B的取出。

总结

在这里插入图片描述

读者写者问题

有一个共享的数据对象：

要求：

1、允许多个读者可以同时对文件执行读操作。

2、只允许一个写者往文件中写信息。

3、任一写者在完成写操作之前不允许其他读者或写者工作。

4、写者执行写操作前，应让已有的读者和写者全部退出。

读者优先

当至少已有一个读者正在读时，随后的读者直接进入，开始读数据对象，但写者将等待。
但一个写者正在写时，随后到来的读者和写者都等待。
信号量的设置：

一次只能让一个写者或一顿读者访问数据。

设一互斥信号量wsem，初值为1。

正在读数据的读者数目由全局变量readcount表示（初值=0），它被多个读者互斥访问。

（第1个读者需对数据加锁，最后1个读者对数据解锁）

为readcount设一互斥信号量x，初值为1。

void reader(){
	while(true){
		semWait(x);
		readcount++;
		if(readcount == 1)
			semWait(wsem);
		semSignal(x);
		/*读数据对象*/
		semWait(x);
		readcount--;
		if(readcount == 0)
			semSignal(wsem);
		semSignal(x);
	}
}

void  writer(){
	while(true){
		semWait(wsem);
		/*写数据对象*/
		semSignal(wsem);
	}
}