进程间通信--Inter Process Communication

三个问题

  1. 一个进程如何把信息传递给另一个 pass information among processes
  2. 确保两个或者更多的进程在Critical Region中不会出现交叉 get into each other's way
  3. 存在依赖关系时的正确排序（如果该顺序是有关联的话）

第一个问题：共享一个地址空间

竞争条件--Race Conditions

  • 两个或多个进程读写某些共享数据，而最后的结果取决于操作的顺序
  • 随着内核数量的增加导致并行性的增加，竞争条件变得越来越普遍。

临界区--Critical Region

  • 避免竞争条件的关键：禁止超过一个进程同时对共享数据进行读取和写入，即互斥

  • 临界区：对共享内存进行访问的程序片段

  • 满足4个条件的一个解决方案：

    1. 任何两个进程不能同时(simultaneously)处于其临界区
    2. 不应对CPU的速度和数量做任何假设
    3. 临界区外运行的进程不得阻塞其他进程
    4. 不得使进程无限期等待进入临界区

忙等待的互斥--Mutual Exclusion Solution

mutux：互斥量

实现互斥的几种方案

  • 屏蔽中断--Disabling Interrupts

    • 使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断
    • 屏蔽中断后，时钟中断也被屏蔽
    • CPU只有发生时钟中断或其他中断后才会进行进程切换，屏蔽中断后，CPU将不会被切换到其他进程
    • 缺点
      • 一个线程可能一直不会打开中断
      • 多处理器系统中，屏蔽了一个CPU，其他CPU仍然能继续运行，可以访问共享内存

  • 锁变量--Lock Variable

    • 设置一个共享锁变量，其初始值为0
    • 当一个进程想进入其临界区时，首先测试这把锁
      • 当锁值为0，则该进程将其设置为1并进入临界区
      • 当锁值为1，则进程等待直到其值变为0
    • 疏漏
      • 一个进程发现锁值为0，恰好将值设置为1之前，另一个进程被调度运行，将锁值变为1，当第一个进程再次运行，同样也将该锁设置为1，此时同时有两个进程进入临界区

  • 严格轮换法--Strict Alternation

    • 整形变量turn，初始值为0，用于记录哪个进程进入临界区，检查或更新共享内存
    • 开始时，进程0检查turn，发现其值为0，进入临界区
    • 进程1也发现其值为0，在一个等待循环中不断地测试turn，看其值何时变为1

    连续测试一个变量直到某个值出现为止，称为忙等待（busy waiting）

    • 浪费CPU时间。应避免

    • 用于忙等待的锁，称为自旋锁（spin lock）

    • 一个进程比另一个慢了许多的情况下，轮流进入临界区不是一个好办法

  • Peterson解法

    • 将锁变量与警告变量的思想结合，提出一个不需要严格轮换的软件互斥算法

  • TSL指令

    • 需要硬件支持

    • 复制内存中的一个值（flag）到CPU的寄存器中，将这个值设为1

  • Mutual Exclusion with Busy Waiting

    • Busy-Waiting: 执行代码的进程将处于紧密循环中，占用 CPU 周期，一遍又一遍地测试某些条件，直到它变成真的。
    • 忙等待可能导致优先级倒置问题

睡眠与唤醒

优先级反转问题--priority inversion problem,忙等待问题会导致这个问题

  • 设置了两个参数：sleep、wakeup
    • sleep:一个将引起调用进程阻塞的系统调用，即被挂起
    • wakeup:有一个参数，指定要被唤醒的进程

Producer-Consumer Problem

生产者-消费者问题

  • 考虑一个可以容纳N个项目的循环缓冲区。
  • 生产者将项目添加到缓冲区，消费者从缓冲区中删除项目
  • 生产者消费者问题是限制对缓冲区的访问

Semaphores 信号量

首先要知道，信号量有两种

  • 一种用于互斥，防止同时访问一些变量
    • 一般初始化为1，表示只有一个进程可以进入
  • 一种用于同步，用于通知其他的进程。
    • 一般初始化为0，有人释放，增加1，就可以被其他的进程检测知道

举一个简单例子：放水果给孩子吃，有两种水果：苹果和梨子，一次只能放一个

  • 放水果这个行为限定了次数，因此用互斥的信号量，防止放多个
  • 孩子吃到水果，则使用同步的信号量，我放了一个苹果，通知他可以吃了

信号量是一种结构，包含两个部分

  1. COUNT，一个用于计数的整数
  2. Q，阻塞的进程的pid的队列
1
2
3
4
5
6
struct sem_struct {
    int count;
    queue Q;
} semaphore;

semaphore S;

信号量的操作

  1. UP
  2. DOWN

这些操作必须原子性地执行(即互斥)。

假设P是进行系统调用的进程，操作定义为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
DOWN(S):
	if (S.count > 0)
		S.count = S.count - 1;
	else
		block(P); /*that is,
        (a) enqueue the pid of P in S.Q,
        (b) block process P (remove the pid from the ready queue)
        (c) pass control to the scheduler*/

UP(S):
	if (S.Q is nonempty)
		wakeup(P) /*for some process P in S.Q; that is,
			(a) remove a pid from S.Q (the pid of P),
			(b) put the pid in the ready queue, and
			(c) pass control to the scheduler.*/
	else
		S.count = S.count + 1

Semaphores do not require busy-waiting, instead they involve BLOCKING

1
2
3
4
semaphore mutex = 1; // set mutex.count = 1
DOWN(mutex);
	- critical section -
UP(mutex);

Mutexes 互斥量

A mutex is a semaphore that can be in one of two states: unlocked (0) or locked (1)

  • 互斥量是一种信号量，有两种状态：unlocked (0) （临界区可用）和 locked (1)

信号量解决生产者消费者问题

使用信号量

进程同步(Synchronization)

同步时的信号量初始化为0，当优先级高的进程执行完毕后，便会释放，即增加1。

例题

Check Points

  1. What is Race Condition?
  2. What is Critical Region?
  3. What is Busy Waiting?
  4. What is Semaphore?
  5. What is Mutex

Solution

  1. Two or more processes access shared resourse and the final result depend on the order of the process
  2. The program that access the shared resourse
  3. The process is running the program over and over again until some condition become true, the CPU is keep running
  • a process executing the entry code will sit in a tight loop using up CPU cycles, testing some condition over and over, until it becomes true
  1. A SEMAPHORE, S, is a structure consisting of two parts: (a) an integer counter, COUNT (b) a queue of pids of blocked processes, Q
  2. A kind of semaphore that has two status: locked and unlocked