操作系统进程同步与信号量---08

如果需要多个进程合作来完成某个任务，那个可能会存在资源争用或者其他一些意想不到的问题，这个时候，就需要通过实现进程同步来防止问题的产生。

实现两个进程之间的同步，最常见的思路就是通过信号机制，就像售票员和司机一样，只有售票员发出关门的信号，司机才能启动车辆。

而只有司机发出停车信号，售票员才能开门。

对于生产者和消费者模型而言，通过counter变量就可以控制进程的同步:

当存在多个消费者或者生产者的时候，信号就无法具备足够的语义，来表明当前存在多少个需要被唤醒的生产者或者消费者。

因此，需要给信号增添新的语义，增添新语义后的信号，被称为信号量。

(1) 缓冲区满，P1执行，P1 sleep，记录下1个进程等待

(2) P2执行， P2 sleep，记录下2个进程等待

(3) C执行1次循环，发现2个进程等待，wakeup 1个

(4) C再执行1次循环，发现?个进程等待，再?

(5) C再执行1次循环，怎么办? 此时再来P3怎么办?

什么是信号量?

信号量会记录额外的信息,然后通过这个额外的信息来决定是发出睡眠信号，还是唤醒信号。

对于上面那个例子而言，我们只需要给counter增添一些语义，就变成了信号量sem，例如: sem

而sem>0则表示有多少资源空闲中，可以被使用,下面sem=1就表示有一个缓冲区空闲等待使用。

信号量有什么组成？

同时，由于该value的值是所有进程都可以看到和访问的共享变量，所以必须在内核中定义；同样，这个名字的信号量也是可供所有进程访问的，必须在内核中定义；同时，又要操作内核中的数据结构：进程控制块PCB，所以信号量一定要在内核中定义，而且必须是全局变量。由于信号量要定义在内核中，所以和信号量相关的操作函数也必须做成系统调用，还是那句话：系统调用是应用程序访问内核的唯一方法。

<code class="javascript">V(semaphore s){    s.value++;    if(s.value<=0)      wakeup(s.queue);}</code>

<code class="javascript">int fd = open(“buffer.txt”);write(fd, 0, sizeof(int)); //写inwrite(fd, 0, sizeof(int)); //写out</code>

<code class="javascript">semaphore full = 0; semaphore empty = BUFFER_SIZE;semaphore mutex = 1;</code>

需要mutex这个信号量充当互斥锁的角色，因为对同一个文件，只能同时有一个进程进行读写工作。

使用信号量还需要注意一个问题，这个问题是由多进程的调度引起的。

当一个进程正在修改信号量的值时，由于时间片耗完，引发调度，该修改信号量的进程被切换出去，而得到CPU使用权的新进程也开始修改此信号量，那么该信号量的值就很有可能发生错误，如果信号量的值出错了，那么进程的同步也会出错。

所以在执行修改信号量的代码时，必须加以保护，保证在修改过程中其他进程不能修改同一个信号量的值。也就是说，当一个进程在修改信号量时，由于某种原因引发调度，该进程被切换出去，新的进程如果也想修改该信号量，是不能操作的，必须等待，直到原来修改该信号量的进程完成修改，其他进程才能修改此信号量。

修改信号量的代码一次只允许一个进程执行，这样的代码称为临界区，所以信号量的保护，又称临界区保护。

实现临界区的保护有几种不同的方法，在Linux 0.11上比较简单的方法是通过开、关中断来阻止时钟中断，从而避免因时间片耗完引发的调度，来实现信号量的保护。但是开关中断的方法，只适合单CPU的情况，对于多CPU的情况，不适用。Linux 0.11就是单CPU，可以使用这种方法。

我们期望得到的empty=-3，但是由于指令调度顺序问题，导致最终empty的值为-2，与期望不符，那么为什么会产生指令调度顺序问题呢？

就是因为时间片或者阻塞等原因，会导致信号量的修改出现问题

产生竞争条件的主要原因是因为时间片到期导致的进程切换，从而让指令调度顺序变化。

解决竞争最简单的方法就是加锁，具体如下:

但是，加锁又引出来一个问题，那就是加锁和加锁之间的范围多大合适，这段范围也被叫做临界区。

以买牛奶为例子，我们可以借此找到些许灵感。

如果丈夫或者妻子谁要去买牛奶了，就先留一个便条，这样对方看到的时候，就知道有人去买了，我就不买了。

这样的标记法会导致死锁的发生，即双方都等待对象先释放锁。

那么如果让一方不太勤劳，看到有人去买牛奶了后，就直接离开。而另一个勤劳的人看到有人去买牛奶了后，会不停的等待，直到对方买回来。

面包店算法由分布式系统大佬lamport提出的，用来解决多线程抢占资源的锁控制问题

当我们去商场的餐馆吃饭的时候。由于用餐的人太多，所以需要排队。但是商场不可能真的让顾客排成一队，不仅可能会影响通道畅通，而且也不方便顾客。万一顾客还想去买点东西或者是上个厕所，都不方便。所以为了解决这个问题，商场有了叫号的机制。每个排队的顾客都会拿一个号码，当商场里有了空位之后，会让号码最小的顾客进去用餐。这个过程就是面包店算法了，只不过Lamport大神当时可能还没有叫号机，所以他想的场景是面包店买面包，买什么不重要，原理大同小异。

我们对叫号的原理进行一点变形，我们假设这个餐厅只有一个位置，一次只能允许一个客人进去用餐。并且我们假设所有的顾客都会一直排队，不会中途走开。做完了这两个假设之后，我们将问题的场景做一个映射。我们把餐厅当成是内存里的一块抢占资源，排队的客人映射成等待资源的线程，用餐的过程映射成线程读写资源。那么，只要线程像是顾客一样会取号排队，不就可以保证线程之间不会出现抢占以及同时读写的问题了吗？

这也就是Lamport面包店算法解决的问题。下面是对Lamport面包店算法的细节讲解

这里补充几点：

1.( a , b )

2.choosing是一个数组，i表示进程，含义是进程是否在选取排队号码 number也是各一个数组，i表示进程，含义是进程的排队号码

<code class="javascript">do{//进程i正要选取进入临界区的排队号码    choosing[i]=true; //进程i正在选取序号，进入排队序列中    number[i]=max(number[0],number[1]...number[n-1])+1; //进程i选取序号完毕    choosing[i]=false; //这个for循环有尽头，也是有空让进的一种粗浅体现    for(j=0;j<n;j++){ //判断此时这个进程是否在选取信号        while(choosing[j]); /*判断进程j是否在队列中，这个条件等价于只有当j进程在排队且j进程的优先级高于i进程，i进程自旋等待，等待j进程申请完临界区后退出临界区。*/        while((number[j]!=0)&&(number[j],j)<(number[i],i));     }    ...//临界区代码 //进程i执行完毕退出临界区了，再申请，就重新排队    number[i]=0; }while(true);</code>

整个情况就类似于你排队去面包房买面包，首先排队，当轮到你了，买面包（也就是执行代码），买完后。如果想要再买就重新排队。

总体来说如果不考虑硬件层面对临界区的实现，Lamport面包店算法已经可以了。

面包店算法的优缺点如下:

优点:

这里的原子和数据库事务原则里的原子性是一个意思，指的是某个指令或者是某些指令要么不做，要么全做，不允许出现中间状态。我们先来看最简单的单CPU的情况，对于单CPU，一次只能执行一个线程，单条指令的执行天然就是原子的。因为同一时刻只会有一个线程在执行，不会存在抢占的情况。我们只需要保证指令的执行顺序，就可以保证原子操作的正确性。

总线锁

对于多CPU的场景而言，就无法保证了，因为可能会出现多个线程或进程同时读写同一块内存的情况。这种情况下显然没有办法保证操作的正确性。为了解决这个问题，一个解决方案是加上硬件锁。所谓的硬件锁就是当某个线程读写内存的时候，将总线的电平拉低，从而锁住系统总线，防止其他线程读写内存。

这种方式显然太简单粗暴了，并且极端情况下会丧失大量性能，我们想要通过多线程或多进程来提升系统并发能力的初衷就达不到了。

缓存锁

针对这种情况，又提出了缓存锁。

因为在CPU当中除了内存之外，还会好几块缓存。我们可以将CPU的原子操作挪到CPU中的某一块缓存当中执行，这样我们就只需要锁住某一块缓存就行了，就可以不用锁住整块内存了。

当然由于缓存和内存存在数据交互，所以实际的操作要复杂得多，我们不需要探究那么深入，只需要在原理上了解即可。

上面说的总线索和缓存锁都需要CPU硬件角度提供支持才行，硬件支持的锁相比之下使用起来要复杂一些，而且限制较多，并不是所有系统都能够支持。因此，通过软件实现的锁更加普遍，下面再介绍一种通过软件实现的多线程锁——自旋锁。

自旋锁

微信 WeLM

WeLM不是一个直接的对话机器人，而是一个补全用户输入信息的生成模型。

33

查看详情

自旋锁看着名字新奇，但是含义很简单。意思是在多线程的场景当中，当一个线程无法获取到临界区资源的时候，不是挂起等待，而是会一直保持执行，反复查询锁变量是否可用。也就是说是一种忙等待。

这样做的好处是线程不需要被挂起，可以减少操作系统执行过程当中的上下文切换带来的开销。

在Java当中，自旋锁有一个非常著名的实现算法，叫做CAS(compare and swap)。翻译过来的意思是比较和替换，在Java很多并发场景当中都用到了CAS的技术，也是Java程序员经常问的问题之一。

CAS的原理很简单，我们会对于每一个操作的对象设置一个期望值，当我们从内存中读取到的结果和期望值不一致的时候，我们会自旋再次读取。如果和期望值一致，说明此时其他线程没有造成干扰，那么就进行修改。

缺点:

我们可以采用软硬件结合的方式来完成对临界区的保护，为什么临界区中的一段指令不能够原子执行，是因为有时钟中断的产生，那么我们如果在进入临界区前关中断，不就能够保证临界区内的代码能够原子执行吗？

然后在退出临界区后，再开中断即可。

但是开关中断这个方法只适合与单CPU，如果是多CPU的话，则会失效，因为对于CPU来说，每个CPU对应一个INTR寄存器，来标记当前发生了什么中断请求:

那么，如果存在多个CPU的话，每个CPU都有自己的INTR寄存器，那么不就不好使了。

首先来看看TestAndSet函数的逻辑有没有问题:

又因为TestAndSet函数的执行可以通过硬件确保原子性，所以上面这段程序的逻辑就不会存在问题

至于硬件层面如何实现原子操作，大家可以看一下下面这篇文章的入门介绍:

处理器如何实现原子操作

计算机体系结构——指令系统——原子指令

操作系统内部其实涉及到很多同步相关的事情，例如: 磁盘读写时，需要判断磁盘是否被其他进程占用，如果被其他进程占用了，那么当前进程就需要进入睡眠状态，而当前磁盘占用结束时，对应的进程还需要通过中断还唤醒等待磁盘读写的进程。

信号量在这个过程中的应用，就是用来判断当前磁盘是否被占用，以及等待读写磁盘的进程有多少个。

对于信号量本身来说，因为需要提供多进程可见性，因此需要放在内核态中。

因此，在用户区想要使用信号量，需要通过对应的系统调用来创建信号量。

首先需要给出信号量这个结构体的模样：

<code class="javascript">sem.c //进入内核typedef struct{    //当前信号量的名字    char name[20];    //资源数    int value;    //任务队列    task_struct * queue;} semtable[20];</code>

定义了20个信号量，每个信号量都有自己的名字，自己的资源数，和自己的任务队列。

创建信号量的系统调用伪代码如下:

<code class="javascript">sys_sem_open(char * name){    在semtable中寻找name对上的;    没找到则创建;    返回对应的下标;}</code>

假设此时有一个磁盘读写请求，需要信号量的保护，那么具体过程如下:

<code class="javascript">main(){//创建一个名为"empty"的信号量,表示只有在磁盘为空闲状态时,才能去读写,因此value使用默认值0即可sd=sem_open("empty")//需要向文件写入5个字符for(i=1 to 5)//每次写入前,需要通过信号量判断文件此刻是否空闲,如果其他进程占用,则进行等待sem_wait(sd)write(fd,&i,4)</code>

syy_sem_wait系统调用伪代码如下:

<code class="javascript">sys_sem_wait(int sd){   //关中断   cli();   //满足条件,说明此时资源被占用了,需要进入等待状态   if(semtable[sd].value-- <0 ){     设置当前进程为阻塞状态;     将自己加入当前信号量的等待队列中: semtable[sd].queue;     进行进程调度: schedule();  } //开中断 sti(); }</code>

我们以Linux 0.11读磁盘为例，来看看Linux 0.11中是如何实现对信号量的使用和保护的:

读取磁盘块的伪代码如下:

<code class="javascript">//读取磁盘块的系统调用函数bread(int dev,int bolck){   //内存中申请一块缓冲区   struct buffer_head *bh;  //启动读命令,然后就不管了,继续往下执行---读取过程由DMA自动完成  ll_rw_blocj(READ,bh);   //在bh缓冲区上阻塞等待  wait_on_bufer(bh);}</code>

启动磁盘读以后睡眠，等待磁盘读完由磁盘中断将其唤醒， 也是一种同步:

读之前,现需要判断对应的内存缓冲区对应的信号量状态,决定是等待,还是直接使用:

<code class="javascript">lock_buffer(buffer_head * bh){   //关中断   cli();   //如果当前资源被锁住了,也就是被被人占用了   while(bh->b_lock)   //那么就进入睡眠状态   sleep_on(&bh->b_wait);   //否则自己锁住当前资源   bh->b_lock=1;   //开中断   sti();}</code>

这里的b_lock就是信号量，用来控制当前内存缓冲区是否被占用，但是这里并没有使用对信号量使用正负机制，而仅仅是通过0,1来表示，那么就有两个问题出现了:

下面就来看看sleep_on函数的实现:

<code class="javascript">void sleep_on(struct task_struct **p){struct task_struct *tmp;//将当前进程加入阻塞队列中tmp = *p;*p = current;//设置当前进程状态为阻塞态current->state = TASK_UNINTERRUPTIBLE;//进程切换schedule();//当前进程被唤醒后,从此处开始执行//判断阻塞队列中下一个进程是否阻塞if (tmp)//如果是处于阻塞中,就唤醒他,设置他的PCB=0,表示当前进程进入就绪态tmp->state=0;}</code>

问题：这个世界上最隐蔽的队列长什么样子?

<code class="javascript">//将当前进程加入阻塞队列中tmp = *p;*p = current;</code>

sleep_on(struct task_struct **p)---->p是一个指向task_struct结构体的指针的指针

指针的指针是什么? ====> 一个存放task_struct地址的数组,p指向的是这个数组的首元素，而* p ==* (p+0)拿到的就是数组的首元素。

<code class="javascript">struct task_struct *tmp;tmp = *p;*p = current;</code>

上面三句代码，就完成了当前进程加入阻塞队列的任务，但是好像看不出来阻塞队列在哪里体现，因为这个队列非常滴隐蔽:

tmp指向了当前信号量bh关联的阻塞队列队首元素，然后p指向了当前进程PCB，相当于将阻塞队列队首元素完成了切换，而此时的tmp可以理解为保存了阻塞队列中下一个进程的PCB。

而因为tmp局部变量是存放在当前进程的内核栈中，而当前sleep_on函数还没有执行结束，因此tmp函数会一直保存在内核栈中，并且tmp指向的是阻塞队列中下一个进程的PCB，因此通过信号量关联的阻塞队列，可以拿到当前队首阻塞进程的PCB，然后再通过当前sleep_on函数内的局部变量tmp就获取到了下一个进程的PCB，这样就完成了阻塞队列的串联。

当发生磁盘中断时，表示之前被占用的内存缓冲区资源得到释放,下一步可以去唤醒阻塞队列中的进程，让他们来使用这个资源了:

<code class="javascript">static void read_intr(void){...//结束磁盘读请求end_request(1);</code>

<code class="javascript">end_request(int uptodate){...//对缓冲区占用资源的释放unlock_buffer(CURRENT->bh);</code>

<code class="javascript">unlock_buffer(struct buffer_head * bh){//信号量置为0,表示释放资源bh->b_lock=0;//唤醒wake_up(&bh->b_wait);}</code>

<code class="javascript">wake_up(struct task_struct **p){   if (p && *p){   //取出队首元素,将对应的PCB状态设置为0,表示当前进程进入就绪态      (**p).state=0; *p=NULL;  }}</code>

当队首的进程被唤醒进入就绪态后，当下一次切换到该进程执行时,会从之前sleep_on函数阻塞处继续向下执行:

<code class="javascript">schedule();//tmp指向的是阻塞队列中下一个元素if (tmp)//唤醒下一个进程---将下一个进程PCB状态设置为0,下一个进程进入了就绪态tmp->state=0; </code>

当磁盘读结束后,发出对应的中断信号，然后会唤醒阻塞队列中的首元素对应的进程，该进程拿到CPU控制权后，又会先去唤醒其指向的下一个进程，下一个进程再去唤醒下一个进程，就这样挨个唤醒,直到全部唤醒完毕。

假设每次只去唤醒首元素，那么会导致排在阻塞队列前面的进程优先得到执行，又因为后来的进程是排在阻塞队列的头部的，这样就导致后来的优先级越高，先到的反而优先级很低，这显然不符合逻辑。

这里先去唤醒队首元素，然后队首元素再唤醒阻塞队列中下一个元素，接着下一个元素被调度时,再去唤醒阻塞队列中下一个元素，直到全部唤醒。

这样只要执行一次wake_up()操作，就可以依次将所有等待在信号量sem处的睡眠进程唤醒。

因此这里全部唤醒之后，阻塞队列中的进程就都处于就绪态了，然后由schedule函数来决定优先让那个进程去获得CPU控制权。

联系之前进程切换时讲过的进程调度算法可知，因为IO阻塞时间越长的进程，优先级会动态升高。

核心思想：唤醒所有被阻塞的进程,让他们按照优先级去竞争锁，而优先级的判断交给schedule函数来决定

<code class="javascript">lock_buffer(buffer_head*bh){  cli();  //被唤醒后会再次进入while循环,判断当前资源是否占用了,如果被占用了,那么继续去睡  while(bh->b_lock)  sleep_on(&bh->b_wait);  //如果没有,就占用资源,然后就可以去使用资源了  bh->b_lock = 1;  sti(); }</code>

如果将下面这段代码改一下:

<code class="javascript">  while(bh->b_lock)  sleep_on(&bh->b_wait);</code>

改为，下面这样写,还对吗?

<code class="javascript">  if (bh->b_lock)  sleep_on(&bh->b_wait);</code>

考虑到sleep_on()会形成一个隐式的等待队列，而wake_up()只要唤醒了等待队列的头结点，就可以依靠sleep_on()内部的判断语句，实现依次唤醒全部的等待进程。所以，sem_wait()的代码实现，必须考虑到这个情况。

参考linux 0.11内部的代码，对于进程是否需要等待的判断，不能用简单的if语句，而应该用while()语句，假设现在sem=-1，生产者往缓冲区写入了一个数，sem=0

没看懂的，可以再去看看下面这篇文章的讲解:

Linux 0.11下信号量的实现和应用（李治军操作系统实验6）

以上就是操作系统进程同步与信号量---08的详细内容，更多请关注php中文网其它相关文章！