进程同步和通信

发表于 | 分类于
字数统计: 2,121

信号量与管程

互斥只是进程间关系的一个方面，很多时候，进程间还需要进行同步和通信，因此就需要更高级的同步互斥方法。

信号量(抽象数据类型)

  • 一个整型sem , 两个原子操作
  • P() : sem - 1 , 若 sem < 0 等待，否则继续
  • V()：sem + 1, 若 sem <= 0 , 唤醒一个等待的P
  • 互斥：二进制信号量 mutex = new Semaphore(1);
  • 条件同步：计数信号量 fullBuffers = new Semaphore(0); emptyBuffers = new Semaphore(n);

相比于锁机制，可以实现进程的并行。

实现细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSemaphore{
  int sem;
  WaitQueue q;
}

Semaphore::P(){
  sem--;
  if(sem < 0){
    Add this thread t to q;
    block(p);
  }
}
Semaphore::V(){
  sem++;
  if(sem <= 0){  // 由于先释放一个资源，所以要判断=
    Remove a thread t from q;
    wakeup(t);
  }
}

存在问题

  1. 开发代码时容易出错：使用的信号量已经被占用；忘记释放信号量
  2. 不能处理死锁

管程(模块)

最初是从编程语言的层面提出的，而不是os层面。通过在高级语言中设计管程机制，简化开发中对同步互斥的操作，实现语言的并发机制。

可以把管程理解成一个特殊的空间。

  • 一个Lock ：指定临界区, 还没有拿到锁的进程挂在entry queue上，等待进入管程
  • 0或n个条件变量：已进入管程的进程在并发访问临界区时所受到的约束，等待进程挂在对应条件变量的等待队列(queues associated with x,y….conditions)上
  • wait()：释放锁进入睡眠
  • signal()

实现细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Condition{
  int num Waiting = 0;
  WaitQueue q;
}

Condition::Wait(lock){
  numWaiting++;
  Add this thread t to q;
  release(lock); //释放锁，允许其他进程进入管程执行(要是先睡眠就没有办法释放了)
  schedule(); // 当前进程睡眠，调度一个就绪进程继续执行
  require(lock); // 再次获得锁才能再次进行wait循环
}
Condition::Signal(){
  if(numWaiting > 0){
    Remove a thread t from q;
    wakeup(t); // 将一个睡眠进程置为就绪状态
    numWaiting--;
  }
}

区别于信号量的V操作，signal不一定会做减法。

例：生产者消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
classBoundedBuffer{
	Lock lock；// 拿到锁才能进入管程访问临界区，同一时刻只有一个进程可以进入,不管是生产者还是消费者
    int count = 0；// 缓存区占用空间
    Condition notFull,notEmpty;
}

BoundedBuffer::Deposite(c){
  lock -> Acquire();
  while(count == n) notFull.Wait(&lock); // 区满等待
  Add c to the buffer;
  count++;
  notEmpty.Signal(); // 唤醒一个消费者
  lock -> Release();
}
BoundedBuffer::Remove(c){
  lock -> Acquire();
  while(count == 0) notEmpty.Wait(&lock);
  Remove c from buffer;
  count--;
  notFull.Signal();
  lock -> Release();
}

存在的问题

当一个正在执行的进程A发出signal操作后，将会调度一个就绪的进程B，那么这个时候到底要执行那一个进程呢？

  • Hansen方法：让进程A继续执行，完成release操作，这个时候可能存在多个就绪进程去抢占lock
  • Hoare方法：让进程B继续执行，此时不会有抢占问题。用if代替while

经典同步问题的实现

读者写者问题

读者优先

已经有读者时，下一个读者也可以进入，只是需要用原子操作来改变count变量。可能造成写者一直等待

写者

1
2
3
sem_wait(WriteMutex);
write;
sem_post(WriteMutex);

读者

1
2
3
4
5
6
7
8
9
10
11
sem_wait(CountMutex);
if(Rcount == 0) 
    sem_wait(WriteMutex);
++Rcount;
sem_post(CountMutex);
read;
sem_wait(CountMutex);
--Rcount;
if(Rcount == 0)
    sem_post(WriteMutex);
sem_post(CountMutex);
写者优先

同理，写者之间不互斥

哲学家就餐问题

思路一：先拿左再拿右。可能同时拿左，造成死锁

思路二：右边不在把左边放回，随机等待一会再重复。可能造成饥饿

思路三：将就餐的的动作视为互斥。每次允许一人吃饭，效率降低，有三个叉子浪费了

思路四：要么不拿要么拿两把，把状态当临界资源，改变状态是一个互斥操作。

我正学到这，老爸走进来，我跟他说了这个问题，他说这还不好办，把筷子从中间一砍啊！ 真妙啊…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void philosopher(int i)
{
    while(true)
    {
        think();
        take_forks(i);
        eat();
        put_forks(i);        
    }
}


void take_forks(int i)
{
    P(mutex);
    state[i] = hungry;
    test_take_left_right_forks(i);
    V(mutex);
    P(s[i]);   // 没拿到叉子就阻塞
}

void test_take_left_right_forks(int i){
    if(state[i] == hungry && state[left] != eating && state[right] != eating){ // 判断可否同时拿到两把叉子
        state[i] = eating;
        v(s[i]);
    }
}

void put_fork(int i){
   P(mutex);
    state[i] = thinking;
    test_take_left_right_forks(left); // 奥妙之处，帮助邻居判断，满足条件把叉子给邻居并其唤醒
    test_take_left_right_forks(right);
    V(mutex);
}

进程通信(IPC)

为了解决进程间竞争关系（间接制约关系）而引入进程互斥；为了解决进程间松散的协作关系( 直接制约关系)而引入进程同步；

为了解决进程间紧密的协作关系而引入进程通信。互斥是一种特殊的同步，进程同步是一种进程通信。

进程之间互相交换信息的工作称之为进程通信IPC （InterProcess Communication）（主要是指大量数据的交换）。进程同步往往只有传递信号的作用，不能传递数据。

详见：进程的同步、互斥、通信的区别

从发送路径上看，可分为：直接通信和间接通信(通过一个消息队列发送和接收消息)

从对是否正确发送消息的处理方式来看，可分为：同步阻塞(直到正确发送才进行下一步)和异步非阻塞

进程间的通信可以分为两种模型，分别为：

  • 共享内存(Shared Memory): 直接通信。开辟一段新的贡献资源段，然后两个进程之间进行数据信息等的交互，该过程不受CPU的控制。
  • 消息传递(Message Passing)：间接通信。将相关的信息传给内核，然后内核将其转发

信号

类似于一种异步打断机制，用软件中断通知事件处理。

具体实现：需要接受信息的应用程序会在OS中注册一个handler函数，在收到传来的信号时，OS从内核态返回用户态，并把应用程序的堆栈指针设置为handler函数的入口地址

信号与信号量的区别：

信号(signal)：是一种处理异步事件的方式。信号是比较复杂的通信方式，用于通知接受进程有某种事件发生，除了用于进程外，还可以发送信号给进程本身。linux除了支持unix早期的信号语义函数，还支持语义符合posix.1标准的信号函数sigaction。

信号量(Semaphore)：进程间通信处理同步互斥的机制。在多线程环境下使用，它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。

信号比较高效但不能传数据。

管道|

可以进行数据交换。一个进程的输出作为另一个的输入，完成重定向。

管道是一种虚文件，实际上是内核的一块缓存区，之所以称之为虚文件，因为对于左边进程而言它就像一个接收文件，对右边进程而言它就像一个数据发送文件。

具体实现：创建管道，创建两个新的进程，由于子进程继承父进程的文件描述符，这时把管道当做一种文件来处理，并分别设置两个子进程的管道写端和管道读端

消息队列

管道的建立依赖于进程间的父子关系，而且传输的数据是字节流，没有结构化关系。消息队列可以解决这两个问题，将消息作为字节序列存储在消息数组中

共享内存

管道和消息队列都是间接通信。共享内存实现的是直接通信，可以快速大量地传输数据，但是会有一致性问题。

SOCKET

更多用在网络进程通信。相关内容以前已经写过。