同步机制

发表于 | 分类于
字数统计: 7.2k

一.进程的并发执行

问题的提出：这一讲的问题都是由于并发所引起的.并发是所有问题产生的基础，并发也是操作系统设计的一个基础。

1.进程特征所带来的问题

(1).并发

  • 进程的执行是间断性的。

每个进程在它的生命周期期间一会儿上CPU执行，一会儿由于某种原因暂停执行，所以每个进程的执行是间断性的

  • 进程的相对执行速度是不可预测

进程执行的间断性使得进程的相对执行速度是不可预测的。由于有进程调度，有其他事件的发生，每个进程上CPU执行可能执行一段时间停止，然后再接着执行，所以整个执行的时间是不可预测的。

(2).共享

  • 进程/线程之间的制约性

在一个并发环境下多个进程或者线程之间会共享某些资源，在这些资源的使用过程中会产生进程之间的一种制约性。比如当一个进程享用打印机这个资源，另外一个进程在第一个进程没有释放这个资源的前提之下就得不到这个资源，那就得等待。因此在一个并发环境下多个进程的执行会带来一种制约。

(3).不确定性

  • 进程执行的结果与其执行的相对速度有关，是不确定的

进程执行的结果和它的相对执行速度是有关系的，因此在不同的执行顺序的情况下，进程的执行结果也是不确定的。

2.与时间相关的错误例子

场景是 get、copy和put 三个进程并发执行：

(1).并发执行过程的分析

假设 g,c,p 分别为 get,copy 和 put 的一次循环过程。因此从当前状态出发能得到正确的结果。

所以如果不满足进程的制约关系，调度的顺序不正确，那就会带来这些错误的结果。

(2).进程前趋图

三个进程的制约关系如下：

  • 当get执行完第一个循环之后，只能够copy执行它的第一个循环。

  • 当copy执行完第一个循环之后可以 是put执行第一个循环，也可以是get执行第二个循环。

  • 以上两个都执行完了，才能够去执行copy的第二个循环。

因此这三个进程之间的制约关系应该满足这样一个前趋图才能保证不出错误。

二.进程互斥

1.竞争条件

竞争条件定义：两个或多个进程读写某些共享数据， 而最后的结果取决于进程运行的精确时序。

和时间是相关的 这就是带来了竞争条件。

竞争条件是由于有一个共享的资源，而多个进程都对这个数据进行相应的操作，所以会带来竞争条件这个概念，比如打印机。

2.进程互斥的概念

进程互斥的概念:由于各进程要求使用共享资源(变量、文件等)， 而这些资源需要排他性使用，各进程之间竞争使用这些资源，这一关系称为进程互斥。

临界资源 (critical resource)：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。

进程互斥所使用的共享资源是一个核心，这个共享资源就是临界资源。

临界区(互斥区) [critical section(region)]： 各个进程中对某个临界资源(共享变量)实施操作的程序片段。

当多个进程都要使用同一个共享资源时，它的代码里就会有相应的操作。而这些代码就是临界区。

这些程序片段，分散在不同的进程里，它们的共同的特点是对同一个共享变量进行一些操作。这一段代码，和另外一个进程的这一段代码互为临界区，互为互斥区。

3.临界区的使用原则

如下图所示，A进程在临界区里还没有出临界区，如果B进程上CPU之后也想进临界区，应该不能够让它进去，如果B进程也进临界区，就会出现关键活动的交叉，带来前面所介绍的各种各样的错误。因此当B进程想要进临界区时，由于A进程还在临界区里，所以 B 进程只能够被阻塞。

回顾上一章优先级反转问题。 有一个低优先级的进程进入了临界区，因为它优先级比较低，有更高优先级进程就绪时就会抢占它的CPU ，可低优先级进程已经在临界区里，所以更高优先级的进程也上不了CPU运行，因为上CPU运行也进不了临界区。所以就被阻塞。

而在高优先级和低优先级之间又会有中级优先级且非常耗时的一些进程在执行，使得低优先级的进程上不了CPU ，也就不能够让高优先级的进程尽快上 CPU。

给出临界区的使用原则：

  • 没有进程在临界区时，想进入临界区的进程可进入
  • 不允许两个进程同时处于其临界区中
  • 临界区外运行的进程不得阻塞其他进程进入临界区
  • 不得使进程无限期等待进入临界区

4.实现进程互斥的方案

(1).软件方案

软件解法1

假设 P先上的CPU，free的初值是 false ，所以循环结束。

如果这时进程P被切换下CPU，而上CPU的正好又是进程 Q，那么进程Q也要判断free是不是false，由于进程P还没有来得及改变它的值，因此Q检测的结果free也等于false ，继续往下执行把 free 变成 true ，然后进入了临界区。 如果Q进入临界区之后又一次被切换下去了。假设正好又是P上CPU了，把 free 变成 true ，然后进入临界区。结果在临界区里两个进程，不满足原则。这就是一个错误的解法。

解决方案：

把两条语句写成一个lock函数，如果把lock函数设计成一个原语，在执行过程中不容许被中断，那么这个操作就是正确的了。

软件解法2

如果P进程想进临界区，而turn等于false ，所以它一直在等待进入临界区。可是如果Q进程始终没有进过临界区，也不想进临界区，那么 P进程就进不了临界区，尽管临界区里没有进程。也就是说，在临界区外的进程Q阻止了P进程进临界区。这也是不允许的。

软件解法3

如果当pturn设置为true之后，紧跟着qturn也是true，这就会导致两个进程都进不了临界区，都在”谦让”。而这，就是After you问题。

软件解法4——DEKKER算法

在解法三的基础上引入turn，让turn值来决定是哪一个进程进入临界区，但是这个算法会出现忙等待 busy waiting问题，浪费了时间。

软件解法5——PETERSON算法

当任何一个进程想进临界区时，它只需要调用enter_region函数，查看能发安全地进入临界区，如果能安全地进入临界区，那么就是相当于这个函数执行结束，可以进临界区。如果不能够安全地进入临界区，就会在这个函数当中去等待进入临界区。

调用这个函数是用进程号，当进程使用完临界区的相关资源之后，出临界区时就调用leave_region函数，就可以让其他的进程进入临界区。

(2).硬件方案

硬件解法1——中断屏蔽法

利用开关中断指令，是一条允许中断或禁止中断的指令。

操作就是在进临界区之前先把中断关闭，然后进入临界区做相应的操作，出临界区时再把中断打开，允许中断。这实际上就是原语操作。

特点：

  • 简单，高效
  • 代价高，限制CPU并发能力(临界区大小)
  • 不适用于多处理器
  • 适用于操作系统本身，不适于用户进程

硬件解法2——“测试并加锁”指令

用测试并加锁这条指令去操作， 这一条指令做了两个事情，一是先读内存单元内容，读到寄存器，然后再去写，把内存单元的内容写上某个值。

TSL指令：TEST AND SET LOCK

硬件解法3——“交换”指令

交换指令的作用是把两个位置，可能是寄存器或内存单元，在一条指令结束的时把两个位置的内容进行一个交换。

XCHG指令：EXCHANGE

三.进程同步

进程互斥指进程之间具有一种竞争关系，而进程同步指多个进程之间的协作关系 。

进程同步 (synchronization)：指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同 完成一项任务。具体地说，一个进程运行到某一点时， 要求另一伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态， 获得消息后被唤醒进入就绪态。

1.生产者与消费者问题

来看一个场景 ：

消费者判断count是否等于 0，如果在它判断count = 0还没有去调用sleep之前消费者被切换下CPU。那么这个时候count是0，假设生产者又生产了一个数据上CPU，可以看到就不断地去生产放到缓冲区，count也不等于 N ，刚才是0，现在生产者生产了一个数据加完 1 之后count就等于1。这时生产者知道count 等于 1，所以会做一个wakeup。但是由于刚才的消费者还没有sleep，所以做的这个wakeup实际上做了一个空操作，因为没有进程在睡眠，所以就继续接着执行，生产者继续生产。如果生产者被切换下CPU，消费者一上来肯定首先要做sleep，但是这个sleep的进程刚才wakeup已经做完了，所以就不会再被唤醒了。所以没有做到完全解决生产者/消费者问题。

四.信号量及PV操作

之所以叫同步机制是因为通常把进程的互斥看成是一种特殊的同步。它既解决同步的问题，也能解决互斥的问题。这种典型的进程同步机制就称为信号量及PV 操作。

1.基本概念

(1).信号量

信号量：是一个特殊变量，用于进程间传递信息的一个整数值。

定义如下:

1
2
3
4
struc semaphore {
  int count;
  queueType queue; 
}

由一个值和一个队列组成，int值传递信息的整数值，队列允许进程挂到上面。

  • 声明一个信号量：semaphore s;

  • 对信号量可以实施的操作: 初始化、P和V (P、V分别 是荷兰语的test(proberen)和increment(verhogen))

(2).PV操作定义

  • P、V操作为原语操作 (primitive or atomic action)

  • 在信号量上定义了三个操作: 初始化(非负数)、P操作、V操作

  • 最初提出的是二元信号量(解决互斥)

    之后，推广到一般信号量(多值)或计数信号量(解决同步)

2.用PV操作解决进程间互斥问题

(1).基本步骤

  • 分析并发进程的关键活动，划定临界区
  • 设置信号量 mutex，初值为1
  • 在临界区前实施 P(mutex)
  • 在临界区之后实施 V(mutex)

(2).例子

假定有三个进程 P1、 P2、 P3，它们都对同一个临界资源进行相应的操作，设定了一个信号量 mutex ，初值是 1。在临界区的前和后把 P、V操作加上。

  • 假设P1先上CPU，它在做P操作时把 mutex减1，mutex=0 。0不小于0，所以P1进程就可以进入临界区。
  • 如果P1进程在临界区的期间被中断了，那么P2进程正好上CPU。它也想进临界区，也做 P(mutex)，而mutex-1 = -1。 因此P2进程就等在mutex队列上。

  • 让出 CPU 之后，假设 P3进程又上CPU。它也要进临界区。mutex -1 = 2。因此P3 进程也等在这个信号量上，等在P2后面，让出CPU。

  • 假设P1又上CPU， 然后它在临界区里完成了工作后出临界区。，接着会执行一个 V(mutex) ，mutex + 1 = -1，这个时候信号量的值还是小于等于 0，因此V操作就会到队列里找到进程P2并把它送到就绪队列，然后P1接着做别的事情。

  • 如果P2上CPU了，它就下一个就进入临界区。P操作执行完后，它接着就进临界区，当它出临界区又做一次 V 操作，mutex +1 = 0，还是小于等于 0 ，所以V操作就会把队列里等的P3进入就绪，就是这样一个过程。

3.用信号量解决生产者/消费者问题

如果把消费者的P(&full)和P(&mutex)互换，当出现缓冲区个数为0的时候，执行P(&mutex)和P(&full)之后，mutex=-1，此时如果生产者执行P(&emputy)和P(&mutex)会出现死锁。

两个V 操作的顺序可以颠倒，因为V操作只是把信号量的值加一。然后查看有无进程等在队列里，如果有就把它释放。 因此V操作不会使得调用V操作的这个进程进入等待状态，所以这两个的顺序是可以颠倒的。 颠倒的结果可能会带来其他的一些问题，比如说，临界区里头会多一点点指令，其他的进程想进临界区可能会稍微晚一点。但是代码中的是最理想的。

4.用信号量解决读者/写者问题

问题描述:

多个进程共享一个数据区，这些进程分为两组:

  • 读者进程:只读数据区中的数据
  • 写者进程:只往数据区写数据

要求满足条件:

  • 允许多个读者同时执行读操作
  • 不允许多个写者同时操作
  • 不允许读者、写者同时操作

(1).第一类读者写者问题：读者优先

问题

如果读者执行:

  • 无其他读者、写者，该读者可以读
  • 若已有写者等，但有其他读者正在读，则该读者也可以读
  • 若有写者正在写，该读者必须等

如果写者执行:

  • 无其他读者、写者，该写者可以写
  • 若有读者正在读，该写者等待
  • 若有其他写者正在写，该写者等待

写者是和其他写者是互斥的，和读者也是互斥的。 所以读者写者问题本质上是一个互斥的问题。

解法

第一类读者写者问题实际上是要解决的是多个读者可以同时读，因此不需要每个读者都去做P(w)或做V(w) 操作。

经过分析发现第一个读者 到来时如果没有其他的读者和写者，他可以去读。它在读之前首先要把临界区保护起来，所以第一个读者做P(w)。只要前面有读者在读，那么后续来的读者都可以去读。 当所有的读者都读完就会把临界区还回来，所以最后一个读者去做V(w)操作。

在代码中的读者里引入一个计数器rc，它用来记录现在有几个读者。进来一个读者之后通过 rc ＋ 1 判断是不是第一个读者，如果rc = 1，表示是第一个读者，那就去做P(w)的工作。每个读者离开都要去 rc- 1 ，当最后一个读者做完 rc - 1， rc就等于0了,最后一个读者去做V(w)操作。

因为多个读者都对rc进行相应的操作，所以rc就成为了一个新的临界资源。rc = rc + 1 判断 rc，或者 rc = rc - 1 判断 rc 都是一个临界区。 因此还要针对这样一个临界区再增加一个互斥的信号量，对rc这段代码进行保护。

(2).Linux提供的读写锁

应用场景:

如果每个执行实体对临界区的访问或者是读或者是写共享变量，但是它们都不会既读又写时，读写锁是最好的选择。

实例:

Linux的IPX路由代码中使用了读-写锁，用 ipx_routes_lock的读-写锁保护IPX路由表的并发访问

要通过查找路由表实现包转发的程序需要请求读锁；需要添加和删除路由表中入口的程序必须获取写锁(由于通过读路由表的情况比更新路由表的情况多得 多，使用读-写锁提高了性能)

五.管程 MONITOR

1.管程的基本概念

(1).为什么引入管程

信号量机制具有一些缺点，比如用信号量及PV操作解决问题的时程序编写需要很高的技巧。 如果没有合理地安排PV操作的位置，就会导致一些出错的结果比如说出现死锁等问题。 所以有人提出一种新的同步机制就是管程。 它实际上是在程序设计语言中引入的一个成分，称之为高级同步机制。

(2).管程的定义

管程是一种特殊的模块，每个管程都有一个名字。管程主要是管理共享资源所对应的数据结构，所以管程在管理共享资源的同时也提供了在这个共享资源之上需要的各种各样的操作，也就是由一组操作的过程来组成。

示例:

进程与管程的关系:

作为进程，它只能通过调用管程给提供的各种过程来间接地来使用管程当中的数据结构。

(3).管程的要求

作为一种同步机制，管程要解决两个问题：

互斥

  • 管程是互斥进入的。
  • 互斥是为了保证管程中数据结构的数据完整性
  • 管程的互斥性是由编译器负责保证的

同步

  • 管程中设置条件变量及等待/唤醒操作以解决同步问题

  • 作用可以让一个进程或线程在条件变量上等待(此时，应先释放管程的使用权)，也可以通过发送信号将等待在条件变量上的进程或线程唤醒

(4).遇到的问题

场景：

当一个进入管程的进程 执行等待操作时，它应当释放管程的互斥权。当后面进入管程的进程执行唤醒操作时(例如后进的P唤醒前面的Q)，管程中便存在两个同时处于活动状态的进程。

解决方法：

  • P等待Q执行
  • Q等待P继续执行
  • 规定唤醒操作为管程中最后一个可执行 的操作

2.HOARE管程

(1).基本概念

  • 因为管程是互斥进入的，所以当一个进程试图进入 一个已被占用的管程时，应当在管程的入口处等待
    • 为此，管程的入口处设置一个进程等待队列，称作入口等待队列
  • 如果进程P唤醒进程Q，则P等待Q执行;如果进程Q执行中又唤醒进程R，则Q等待R执行;……，如此，在管程内部可能会出现多个等待进程
    • 在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列 的优先级

(2).条件变量的实现

因为管程的互斥是由编译器保证的，是语言机制。 所以这里头只考虑怎么样解决同步问题，同步问题是通过条件变量和条件变量上实施的wait和signal这两个操作来完成的。

条件变量——在管程内部说明和使用的一种特殊类型的变量。对于条件变量，可以执行wait和signal操作

wait(c):

如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入 c(条件变量) 链末尾。

signal(c):

如果 c 链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾。

3.管程的应用

(1).管程的实现

管程实现的两个主要途径:

  • 直接构造——效率高

    因为它是语言机制，所以可以在某个语言当中加入这样一个管程成分，然后去编写相应的编译器

  • 间接构造——用某种已经实现的同步机制去构造

    比如可以用信号量及 PV 操作来构造一个管程

(2).用管程解决生产者消费者问题

4.MESA管程

引入MESA的原因：

  • Hoare管程的一个缺点：两次额外的进程切换

  • 解决方式：解决:

    • 把 signal 改成 notify
    • notify：当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到通知，发信号的进程继续执行

(1).使用NOTIFY要注意的问题

  • notify的结果：位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行

  • 由于不能保证在它之前没有其他进程进入管程， 因而这个进程必须重新检查条件

    用while循环取代if语句

  • 导致对条件变量至少多一次额外的检测(但不再有额外的进程切换)，并且对等待进程在notify 之后何时运行没有任何限制

(2).MEAS管程：生产者—消费者问题

(3).改进NOTIFY

  • 对notify的一个很有用的改进

    • 给每个条件原语关联一个监视计时器，不论是否被通知，一个等待时间超时的进程将被设为就绪态
    • 当该进程被调度执行时，会再次检查相关条件， 如果条件满足则继续执行

  • 超时可以防止如下情况的发生:

    • 当某些进程在产生相关条件的信号之前失败时，等待该条件的进程就会被无限制地推迟执行而处于饥饿状态

(4).引入BROADCAST

broadcast：使所有在该条件上等待的进程都被释放并进入就绪队列

应用场景：

  • 当一个进程不知道有多少进程将被激活时，这种方式是非常方便的

例子:生产者/消费者问题中，假设insert和remove 函数都适用于可变长度的字符块，此时，如果一个 生产者往缓冲区中添加了一批字符，它不需要知道 每个正在等待的消费者准备消耗多少字符，而仅仅 执行一个broadcast，所有正在等待的进程都得到通 知并再次尝试运行

  • 当一个进程难以准确判定将激活哪个进程时，也可使用广播

5.HOARE管程与MESA管程的比较

  • Mesa管程优于Hoare管程之处在于Mesa管程错误比较少

  • 在Mesa管程中，由于每个过程在收到信号后都重新检查管程变量，并且由于使用了while结构，一个进程不正确的broadcast广播或发信号notify，不会导致收到信号的程序出错

    收到信号的程序将检查相关的变量，如果期望的条件没有满足，它会重新继续等待

6.管程小结

管程：抽象数据类型 有一个明确定义的操作集合，通过它且只有通过它才能操纵该数据类型的实例

实现管程结构必须保证下面几点：

  • 只能通过管程的某个过程才能访问资源;
  • 管程是互斥的，某个时刻只能有一个进程或线程调用管程中的过程

条件变量:为提供进程与其他进程通信或同步而引入

wait/signal 或 wait/notify 或 wait/broadcast

六.PTHREAD中的同步机制

Pthread解决互斥的问题：在Pthread 中使用一个互斥量，通过对互斥量提供相应的操作来保护临界区。

Pthread解决同步问题：在Pthread 中使用条件变量，以及在条件变量上的各种操作

1.用PTHREAD解决生产者消费者问题

2.讨论：PTHREAD_COND_WAIT

pthread_cond_wait的执行分解为三个主要动作:

1、解锁

2、等待

当收到一个解除等待的信号 (pthread_cond_signal或者 pthread_cond_broad_cast)之后， pthread_cond_wait马上需要做的动作是:

3、上锁

七.进程间通信机制

1.为什么需要通信机制

  • 信号量和管程只能传递很简单的信息，不能传递大量的信息

    比如要把一个大的数组传送给另外一 进程，那么信号量和管程在这一方面是做不到的。

  • 管程不适合于用于多处理器的情况

因此在传递大量信息的时候需要引入新的通信机制，这个通信机制就是进程间通信机制。

非常典型的形式就是消息传递 ，实际上就是由send和receive提供这样的原语操作。当一个进程要把消息发送给另外一个进程时就去调用send； 当另外一个进程想接收消息时就去调用receive操作。

使用情况：分布式系统、基于共享内存的多处理机系统、单处理机系统。可以解决进程间的同步 问题、通信问题

2.基本通信方式

(1).消息传递

发送消息：发送进程只是把消息准备好，调用send 操作，然后操作系统做相应的复制消息的内容，挂接的内容。

接收消息：接收进程接收消息时把请求提交给操作系统，操作系统完成把消息复制到接收进程空间的工作。

所以操作系统要提供这样一个通信机制，来完成进程之间的信息传送。

用PV操作实现SEND操作

2.共享内存

该通信模式需要解决两个问题：

第一个问题：需要在物理内存里建一个大家能够共享的一块内存空间。通过相应的映射能把这个物理内存空间映射到了两个进程相应的地址空间里。

第二个问题：其实就是读者写者问题，因为共享内存不能同时去写，可以同时去读。 所以可以利用控制读写者问题的这个方法来解决互斥问题。

3.管道通信方式 PIPE

利用一个缓冲传输介质——内存或文件连接两个相互通信的进程。

  • 用字符流方式写入读出
  • 先进先出顺序
  • 管道通信机制必须提供的协调能力
    • 互斥、同步、判断对方进程是否存在

八.典型操作系统中的IPC机制

1.进程同步/通信实例

2.LINUX的进程通信机制

Linux提供了很多种工具，根据需要挑选合适的一种。

3.原子操作

原子操作是不可分割，在执行完之前不会被其他任务或事件中断。它常用于实现资源的引用计数。

例子：

1
2
3
4
5
6
atomic_t v = atomic_init(0);
atomic_set(&v, 4); 
atomic_add(2, &v); 
atomic_inc(&v);
printk(“%d\n”, atomic_read(&v);
int atomic_dec_and_test(atomic_t *v)

4.屏障

屏障主要是用于对一组线程进行协调的。

应用场景：

一组线程协同完成一项任务，需要所有线程都到达一个汇合点后再一起向前推进。

0%