第五章 并发性、互斥和同步

并发性出现的上下文环境：

• 多个应用程序
• 结构化应用程序
• 操作系统结构

一些相关概念：

• 临界区：一个代码，在这段代码中进程将访问共享资源11，当另一个进程已在这段代码中运行时，这个进程就不能在这段代码中执行。
• 死锁：两个或两个以上的进程因每个进程都在等待其他进程做完某件事情而不能继续执行的情形。
• 互斥：当一个进程为临界区访问共享资源时，其他进程不能进入临界区访问任何共享资源的情形。

5.1并发的原理

5.1.1并发执行的难点

• 全局资源的共享

• 操作系统很难对分配资源进行最优化管理

• 定位程序设计是非常苦难的

5.1.2进程的交互

• 进程之间的通信（分为三种类型）

  • 进程间相互不知道对方的存在（例如两个无关的应用程序都可能想去访问同一个磁盘）
  • 进程间间接知道对方的存在（不知道对方程序的ID但是通过共享某些对象，间接了解对方的状态）
  • 进程间直接知道对方的存在（通过对方的ID直接了解到）

• 进程间的资源竞争

  进程面临三个控制问题：互斥、死锁、饥饿

• 进程间通过共享合作

• 进程间通过通信合作

5.1.3互斥的要求

1. 在某一时刻，只能有一个进程允许进入临界区
2. 一个在非临界区停止的进程必须不干涉其他进程
3. 临界区不允许多个进程出现死锁或饿死
4. 当没有进程在临界区中时，任何需要进入临界区的进程必须够立即加入
5. 对相关进程的速度和处理器的数目没有任何要求和限制
6. 一个进程驻留在临界区中的事件必须是有限制的

5.2互斥的实现方法

硬件方法：

1. 中断禁止：

   • 单处理器系统有效

   • 一个进程将一直运行，直到它调用了一个操作系统服务或被中断

   • 禁止中断可以保证互斥

   • 处理器被限制了在多个程序之间交互执行

   • 多处理器系统这种方法就失效了。

     屏蔽中断法

1. 专用机器指令

​ 在硬件级别上，对处理器单元的访问与其他访问内存的指令相互排斥，将判别和加锁由一条指令完成，中间不会被其他指令打断。

//Test and Set Instruction
	boolean testset(int i){
		if(i == 0){
      	i = 1;
      	return true;
    }
    else{
      	return false;
    }
	}

注意：testset是一个指令（执行不被打断）

i = 0代表没有上锁，1代表已经上锁。

返回值代表能否可用

// program mutualexclusion
const int n ;// number of processs
int bolt;
void p(int 1)
{
	while (True)
  {
    while (!testset(bolt))
      //do nothing
    critical section
    bolt = 0
    remainder
  }
}
void main()
{
  bolt = 0;
  parbegin(p(1),p(2),p(3)....,p(n))
}

**机器指令方法的特点：**

• 优点
  • 适合与在单处理器或共享内存的多处理器上的任何数目的进程
  • 非常简单且易于证明
  • 可用于支持多个临界区，每个临界区可以用它自己的变量定义
• 缺点：
  • 使用忙等待消耗处理器时间
  • 可能饥饿
    • 当一个进程离开临界区，且多个进程正在等待时，选择哪一个等待进程是随意的。因此，某些进程坑无限期地被拒绝进入
  • 可能死锁
    • 若P1进入临界区，但被P2中断，而P2具有更高优先级，P2试图使用P1的资源，可能死锁

5.3信号量技术

两个或多个进程可以通过简单的信号进行合作，为了发信号需要使用一个特殊变量称为信号量。

⚠️一个进程若等待某一个信号量，则它被阻塞，知道收到指定的信号，进入就绪状态。

5.3.1信号量的三个操作

1. 初始化：可以初始化为一个非负数
2. Wait操作：将信号量值减1，若结果小于0，则执行Wait操作的进程进入等待状态；
3. Signal操作：将信号量值加1。

5.3.2信号量类型及同步原语

一般称Wait和Singal为信号量的同步原语

按照用途，信号量可以分为：

1. 二元信号量：其值仅取0或1，主要用于互斥问题，初值为1；
2. 一般信号量：其初值为0或n，一般用于进程同步问题。

信号量原语：

struct semaphora{
  int count;
  queueType queue;
};

void semWait(semaphore s)
{
  s.count--;
  if(s.count < 0)
  {
    place this process in s.queue;
    block this process
  }
}

void semSignal(semaphore s)
{
  s.count++;
  if(s.count <=  0)
  {
    remove a process p from s.queue;
    place process p on ready list;
  }
}

二元信号量原语：

struct binary_semaphora{
  enum{zero, one} value;
  queueType queue;
};
void semWaitB(binary_semaphora s)
{
  if(s.value == 1)
    	s.value = 0;
  else
  {
    place this process in s.queue;
    block this process;
  }
}
void semSignalB(semaphore s)
{
	if(s.queue.is_empty())
    s.value = 1;
  else:
  {
    remove a process p from s.queue;
    place process p on ready list;
  } 	
}

wait之后的等待方式分为阻塞等待和忙等待两种。

1. 阻塞等待方式

信号量数据结构化，为了方便对进程的管理，此时，把信号量的数据结构从整形扩充到记录类型

struct binary_semaphora{ enum{zero, one} value; queueType queue; };

1. 忙等待方式

   • 此时信号量的数据结构就是整形。
   • 一般的信号量的同步语言：

   

   • 二元信号量的同步原语：

​

同步原语的不可分割性：几乎所有的OS都规定：同步原语是不可分割的，以保证进程互斥地使用，且不被中断。

同步原语不可分割性的保证方法：利用testset实现原语。

而且一般采用忙等待的方法，因为一般来说忙等待对于短代码来说效率会更高一些。

//semWait原语的实现
semWait(S):
{
  while(!testset(s.flag))
    do nothing;
  s.count--;
  if(s.count<0)
  {
  	place this process in s.queue;
    block this process (must also set flag to 0);
  }
  s.flag = 0;
}
//semSignal原语的实现
semSignal(S):
{
  while(!testset(s.flag))
    do nothing;
  s.count--;
  if(s.count<0)
  {
    remove a process p from s.queue;
    place process p on ready list;
  }
  s.flag = 0;
}
/* 对于信号量原语的实现，相当于用testset指令为信号量原语的互斥增加了相应的锁
因此信号量的原语之间的执行是互斥的，实现了"原语"应有的功能。*/

**semWait和semSignal互斥含义（也就是不可分割呗）**：

• 对于同一个信号量，多个进程执行的semWait需要互斥
• 对于同一个信号量，多个进程执行的semSignal需要互斥
• 对于同一个信号量，多个进程执行的semWait和semSignal需要互斥

5.3.3信号量的物理意义

1. S>0,表示可用资源的数量；
2. S小于等于0，S的绝对值表示因申请资源而被阻塞的进程个数（也就是阻塞队伍的长度）
3. Wait操作，相当于申请了一个单位的相关资源；S = S - 1，若S < 0则阻塞申请者。
4. Singal操作，相对于释放一个单位的相关资源；S = S + 1，若S小于等于0则从阻塞队列中唤醒一个进程就绪。（回忆进程的状态相关的知识）

5.3.4信号量实现互斥和同步

互斥和同步问题本质一致：

一方面：信号量本身用到了testset等，实现的互斥算法。可见互斥可以实现同步。

另外一方面：自身的同步就实现了互斥，当s=1时，相当于将资源数目初始化为1时，就可以作为互斥使用。

/*program mutualexlusion*/
sonst int n = /* number of processes*/;
semaphore s = 1;
woid p(int i)
{
	while (Ture)
	{
		semWait(s);
		critical section;
		semSignal(s);
		remainder;
	}
	void main()
	{
		parbegin(p(1),p(2)...p(n));
	}
}

同步示意图：

同步问题中的”生产者/消费者”问题：（无限缓冲区）

​ n负责同步操作、s负责互斥操作

课堂测试；

第一个问题，交换完位置之后，可行但是会影响效率，将produce加入到互斥部分中去了。

第二个问题，将semSignal(s)和semSignal(n)交换位置之后呢，在semSignal(n)处执行完毕之后右边就进入到semWait(s)的忙等待中，还需要回头进入到semSignal(s)中增加了一个semSignal 的时间，影响了效率。

第三个问题，将semWait(n)和semWait(s)调换位置后，两个程序并行，右边直接将s变为0后导致，左边卡在semWait(s)处忙等待，右边卡在semWait(n)处忙等待（因为此时s和n都是0）

第四个问题：同第一个问题一个道理。