0
0

【10. 信号量和管程】

在这里插入图片描述

🎉作者简介:👓

      博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢
     
     
      c
     
     
      +
     
     
      +
     
     
      ,
     
     
      g
     
     
      o
     
     
      ,
     
     
      p
     
     
      y
     
     
      t
     
     
      h
     
     
      o
     
     
      n
     
     
      ,
     
     
      目前熟悉
     
     
      c
     
     
      +
     
     
      +
     
     
      ，
     
     
      g
     
     
      o
     
     
      语言，数据库，网络编程，了解分布式等相关内容
     
    
   
   
    \textcolor{orange}{博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容}
   
  
 博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容

📃

      个人主页：
     
    
   
   
    \textcolor{gray}{个人主页：}
   
  
 个人主页： 小呆鸟_coding

🔎

      支持
     
     
      :
     
    
   
   
    \textcolor{gray}{支持:}
   
  
 支持:
 
  
   
    
     
      如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦
     
    
   
   
    \textcolor{green}{如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦}
   
  
 如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦👍
 
  
   
    
     
      就是给予我最大的支持！
     
    
   
   
    \textcolor{green}{就是给予我最大的支持！}
   
  
 就是给予我最大的支持！🎁

💛本文摘要💛
本专栏主要是讲解操作系统的相关知识 本文主要讲解 信号量和管程

文章目录

**

清华操作系统系列文章：可面试可复习

**

  1. 操作系统—概述

  2. 操作系统—中断、异常、系统调用

  3. 操作系统—物理内存管理

  4. 操作系统—非连续内存分配

  5. 虚拟内存管理

  6. 操作系统—虚拟内存管理技术页面置换算法

  7. 进程管理

  8. 调度算法

  9. 同步与互斥

  10. 信号量和管程

  11. 死锁和进程通信

  12. 文件系统管理

🎶信号量和管程

  • 背景
  • 信号量
  • 信号量实现
  • 管程
  • 经典同步问题

用信号量和管程解决同步互斥的问题

❓0. 上次概念

  • 并发问题：竞争条件（竞态条件）- 多程序并发存在大的问题
  • 同步- 多线程共享公共数据的协调执行- 包括互斥与条件同步- 互斥：在同一时间只有一个线程可以执行临界区
  • 确保同步正确很难？- 需要高层的编程抽象（如：锁）- 从底层硬件支持编译

在这里插入图片描述

  • 同步：一种合作关系，为完成某个任务而建立的多个进程或者线程之间的协调调用，次序等待，传递消息告知资源（进程切换，互相前进）
  • 互斥：制约关系，当一个进程或多个进程进入临界区后会进行加锁操作，此时其他进程（线程）无法进入临界区，只有当该进程（线程）使用后进行解锁，其他人才可以进入临界区。

❓1. 信号量

  • 进入临界区后，不一定做一些操作，还需要做读操作，读操作可以有多个进程一起进入临界区执行（不需要限制一个进程）。

在这里插入图片描述

  • P() < 0，执行P操作的进程需要睡眠，当P >= 0,可以继续执行，进入临界区（类似于lock锁操作）
  • V() 就是把信号量的值加1，如果sem <= 0,当前一些进程等待着P操作。他就会唤醒等待的P（执行位操作的进程，会唤醒挂载信号量上的等待的进程，一般可以唤醒一个或者多个）

❓2. 信号量的使用

一般最开始把信号量设置为整数，而且是大于0的整数，这样在进程进入临界区的时候才不会阻塞
  • 信号量是整数
  • 信号量是被保护的变量- 初始化完成后,唯一改变一个信号量的值的办法是通过P()和V()- 操作必须是原子
  • P()能够阻塞,V()不会阻塞
  • 我们假定信号量是公平的- 没有线程被阻塞在P()仍然堵塞如果V()被无限频繁调用(在同一个信号量)- 在实践中,FIFO经常被使用

问题：信号量可以通过FIFO队列实现唤醒进程，而锁在进行忙等待时能否通过FIFO队列实现唤醒进程吗

信号量的设置

  • 两个类型信号量- 二进制信号量: 可以是0或1（模拟锁lock）- 计数信号量: 可以取任何非负数（设置为大于0的整数，可以使得多个进程一起进入临界区执行。而lock锁是临界区只有一个进程，这就是区别）- 两者相互表现(给定一个可以实现另一个)
  • 信号量可以用在2个方面- 互斥- 条件同步(调度约束——一个线程等待另一个线程的事情发生)

二进制信号量可以实现互斥操作
在这里插入图片描述
二进制信号量可以实现同步操作

  • 同步操作信号量赋值为0。
  • 线程A必须等待线程B执行完之后才执行。

先执行进程A，当进程A执行后O操作会减1，此时信号量变为-1，进程A挂起，然后执行进程B，当执行完进程B，V操作会+1，此时信号量为0，唤醒进程A

在这里插入图片描述

计数信号量

  • 单纯使用二进制信号量，可能对于复杂的进程没办法解决，此时需要条件同步机制完成
  • 一个线程等待另一个线程处理事情- 比如生产东西或消费东西(生产者消费者模式),- 互斥(锁机制)是不够的
  • 例如有界缓冲区的生产者-消费者问题- 一个或者多个生产者产生数据将数据放在一个缓冲区里- 单个消费者每次从缓冲区取出数据- 在任何一个时间只有一个生产者或消费者可以访问该缓冲区

在这里插入图片描述

  • 正确性要求- 在任何一个时间只能有一个线程操作缓冲区(互斥)- 当缓冲区为空时,消费者必须等待生产者(调度,同步约束)- 当缓存区满,生产者必须等待消费者(调度,同步约束)
  • 每个约束用一个单独的信号量- 二进制信号量互斥（二进制信号量用于互斥）- 一般信号量 fullBuffers（计数信号量用于同步）- 一般信号了 emptyBuffers

❗️2.1 生产者与消费者模型（第一个经典问题）

  • 需要满足使得buffer互斥，使用mutex->P()和mutex->V()(使用信号量的P,V操作使得往缓冲区添加数据时为互斥操作，使得对buffer操作是只有一个进程对其操作)
  • 生产者：- buffer没有满，可以执行，用emptyBuffer判断buffer有没有满，而且emptybuffer初始值设置为n，也就是可以执行n次操作（也就是可以用有n个生产者进程进入buffer中）- fullbuffer->V操作,可以通知消费者，buffer缓冲区有数据，你可以来取（一开始消费者想取数据，取不到因为初始值为0，只有在生产者执行fullbuffer->V才可以）
  • 消费者- 如果一开始生产者先执行，那么fullbuffer为1，此时消费者执行fullbuffer->P()操作时，可以从缓冲区取数据- 如果一开始消费者先执行，由于fullbufferW为空，则会阻塞，消费者会睡眠，同时会唤醒生产者，知道缓冲区有数据。
如果生产者很快，把buffer塞满了，此时执行emptybuffer->P(),操作是阻塞，此时需要消费者执行emptybuffer->V()操作，使得buffer的值+1，当buffer不满时，通知睡眠的生产者

class BoundedBuffer{
        mutex = new Semaphore(1);//互斥操作，初始值设置为1（当第一个执行时，值-1，为0.此时第二个需要等待第一个锁释放）
        fullBuffers = new Semaphore(0);//说明缓冲区初始为空
         emptyBuffers = new Semaphore(n);//生产者可以往缓冲区填充n个数据};

BoundedBuffer::Deposit(c){
        emptyBuffers->P();
        mutex->P();
        Add c to the buffer;
        mutex->V();
        fullBuffers->V();}

BoundedBuffer::Remove(c){
        fullBuffers->P();
        mutex->P();
        Remove c from buffer;
        mutex->V();
        emptyBuffers->V();}

P、V操作的顺序有影响吗？

  • 对于互换生生产者最后的V操作，对程序没有影响- 不会影响，因为V操作只会加1，和通知机制（唤醒），本身不会阻塞
  • 对于互换生生产者开头的P操作，对程序有影响- 当buffer满时，此时生产者会进入mutex->P(),在执行到emptybuffer->P()操作会阻塞（因为buffer已满，在执行就变成-1，需要睡眠），此时需要唤醒消费者。- 对于消费者，buffer已满，此时fullbuffer->P();可以执行，但是执行到mutex->P()就会产生错误，因为生产者虽然buffer满无法执行但是它占用mutex信号量。使得消费者执行mutex失败——死锁

❓3. 信号量的实现

  • 做P操作可能有信号处于等待状态，等操作就是等待队列（进程当得不到相应的资源，就会睡眠），也就是执行P操作时，这个值<0，此时进程会睡眠，需要等待队列。等待信号量执行V操作后会唤醒
  • P操作执行–，当信号量<0,此时会将信号量放到等待队列中去，并且自身睡眠
  • V操作执行++，判断是否等待队列中有睡眠的信号量，将它从等待队列移除，并将其唤醒（FIFO取出唤醒等待队列中的信号量）在这里插入图片描述
  • 信号量的双用途- 互斥和条件同步- 但等待条件是独立的互斥
  • 读,开发代码比较困难- 程序员必须非常精通信号量
  • 容易出错- 使用的信号量已经被另一个线程占用- 忘记释放信号量
  • 不能够处理死锁问题

与lock区别：

  • lock有俩种等待：忙等和等待队列（可以做sleep操作）
  • 信号量全部都是使用等待队列实现sleep，在通过v操作唤醒

❓4. 管程

管程最开始是用于语言，来完成同步互斥的操作（针对语言的并发操作），后来用于操作系统上

  • 目的: 分离互斥和条件同步的关注
  • 什么是管程- 一个锁: 指定临界区（所有要访问管程管理的函数只能有一个线程，需要确保互斥性）- 0或者多个条件变量: 等待,通知信号量用于管程并发访问共享数据（访问大量共享资源，在访问中可能得不到满足，需要把等待的，得不到资源的线程挂起，挂在条件变量上面）- 管程管理着一系列函数。可以供线程访问
  • 一般方法- 收集在对象,模块中的相关共享数据- 定义方法来访问共享数据

图例

  1. entry queue进入管程是互斥的，首先要去的lock，获得lock才能进入管程，取不到lock就要在这个队列中
  2. 进入lock管理的临界区后，线程可以执行管程维护的一系列函数，操作函数，这些函数有许多共享变量，可以对共享变量操作，针可能对某个共享资源的共享变量得不到满足，则需要等待，需要把自身挂载到条件变量上，同时把lock释放掉，让等待在lock上的其他线程执行
  3. 自身挂到条件变量上，条件变量的等待队列挂载所有线程，有条件x和y，当条件满足就会唤相应进程
wait

:线程等在条件变量中

signal

:唤醒条件变量使得，使得挂载到条件变量上的线程可以继续执行
在这里插入图片描述

  • Lock- Lock::Acquire() 等待直到锁可用,然后抢占锁- Lock::Release() 释放锁,唤醒等待者如果有
  • Condition Variable- 允许等待状态进入临界区- 允许处于等待(睡眠)的线程进入临界区- 某个时刻原子释放锁进入睡眠- Wait() operation- 释放锁,睡眠,重新获得锁放回- Signal() operation(or broadcast() operation)- 唤醒等待者(或者所有等待者),如果有

实现

  • 需要维持每个条件队列
  • 线程等待的条件等待signal()
class Condition{int numWaiting =0;
        WaitQueue q;};

Condition::Wait(lock){
        numWaiting++;//执行wait操作就是睡眠了，表明多了一个睡在条件变量上的进程。
        Add this thread t to q;release(lock);//让生产者释放锁，让其他的进程进入管程执行schedule();//need mutex,选择下一个线程执行，本身这个进程已经属于睡眠状态了require(lock);}

Condition::Signal(){if(numWaiting >0){//说明有进程处于等待状态，如果有的活从等待队列唤醒进程
                Remove a thread t from q;wakeup(t);//need mutex
                numWaiting--;}}
wake up与 schedule对应，schedule是进程睡眠了，他会取一个就绪态进程继续执行，完成线程切换，wake up 将睡眠进程重新置成就绪态

值得注意，如果这个等待队列里没有进程，则这个操作什么也不做
信号里面是信号量的个数为0，（他的P和V操作一定会进行加和减操作的）而这里是num waiting等待进程的数量为0（在Wait会做加操作，而signal不一定会减操作）.

管程解决生产者—消费者问题

  • 管程最重要的俩个：lock(锁)和条件变量
  • 对于之前的生产者和消费者问题，条件变量有俩种：buffer满和buffer空
  • 管程的生产者和消费者模型，不仅需要设置buffer空和buffer满，还要设置count(记录buffer当前的空闲情况，count =0,buffer空，count=n,buffer满)

注意：与信号量互斥不一样，信号量的互斥是仅仅靠近这个buffer,而管程的互斥是放到程序的头和尾（由管程的定义决定，线程进入到管程的时候，只有一个线程能进去，才能使用管程管理的所有函数，所以一进入管程的时候就需要互斥）

class BoundedBuffer{
        Lock lock;int count =0;//buffer 为空
        Condition notFull, notEmpty;};

BoundedBuffer::Deposit(c){
        lock->Acquire();//管程的定义:只有一个线程能够进入管程while(count == n)
                notFull.Wait(&lock);//与信号量不一样，notfull是条件变量，不需要初始化，表示当前已经满了，需要睡眠，释放前面的锁（释放管程的lock，因为睡眠了，释放锁后，可以让其他的进程进入管程执行，睡眠之前一定要释放锁， 不然会导致所有后面等待的进程都无法进入管程）
        Add c to the buffer;
        count++;
        notEmpty.Signal();//buffer空与buffer满是一样的
        lock->Release();}

BoundedBuffer::Remove(c){
        lock->Acquire();while(count ==0)
                notEmpty.Wait(&lock);
        Remove c from buffer;
        count--;
        notFull.Signal();//对应生产者的notfull Wait，notfull.Signal是唤醒机制，如果notfill Signal中有等待的线程，那么就会唤醒（首先count --, buffer满，经过-- 后，会不满，此时可以使用notfull Signal操作唤醒，它里面等待的进程）
        lock->Release();}

问题：

  • 当线程在管程里面执行的时候，如果某个线程，执行某个条件变量的> Signal（唤醒）操作时，是不是马上唤醒等待在条件变量上的线程。 - 执行Signal操作时，管程里面是有俩个线程，signal之后，就是要把等>待的进程唤醒（唤醒进程的本身也可以执行），这就会产生冲突。

俩种解决办法

  1. 一旦发出signal操作后，让等待的线程执行，它自身去睡眠，直到等待的线程执行完release之后，发出signal的线程才能继续执行。
  2. 当发出signal操作是，不是立刻放弃CPU，让等待的线程执行，而是等到发出signal的线程执行完release后，才把控制权交给等待的线程执行。

在这里插入图片描述
在这里插入图片描述

  • 开发,调试并行程序很难- 非确定性的交叉指令
  • 同步结构- 锁: 互斥- 条件变量: 有条件的同步- 其他原语: 信号量
  • 怎么样有效地使用这些结构 制定并遵循严格的程序设计风格,策略

❓5. 经典同步问题

❗️5.1 读者-写者问题（第二个经典问题）

  • 动机：- 共享数据的访问
  • 两种类型的使用者：- 读者 — 不修改数据（读者优先）- 写者 — 读取和修改数据
  • 问题的约束：- 允许同一时间有多个读者,但在任何时候只有一个写者- 当没有写者时,读者才能访问数据- 当没有读者和写者时,写者才能访问数据- 在任何时候只能有一个线程可以操作共享变量

当读者读的过程中，有写者进入，那么等待读者读完，同样当写者执行时，不管读者和写者都要等待。等待当前写者写完。

  • 多个并发进程的数据集共享 - 读者 — 只读数据集;他们不执行任何更新- 写者 — 可以读取和写入
  • 共享数据 - 数据集- 信号量CountMutex初始化为1（读Rcounter保证读是互斥的）- 信号量WriteMutex初始化为1（写也要互斥）- 整数Rcount初始化为0(当前读者个数,写者就一个，读者有很多)

在这里插入图片描述

  • WriteMutex确保写者的互斥性，以及只有一个读者的互斥性
  • 通过Rcounter实现对读者个数的记录,使得多个读者可以同时数据里面进行读操作
  • Rcounter通过CounterMutex来进行保护（互斥），使得Rcounter可以互斥的+，-

读者优先与写者优先
在这里插入图片描述

💤5.1.1 利用管程实现写者优先的，读者—写者问题（前面使用信号量方式实现读者优先的，读者—写者问题）

  • 读者需要等待的写者的有俩类： 1. 当前正在做写操作的写者2. 当前正在等待做写操作的写者
⭐️5.1.1.1 代码

在这里插入图片描述

初始化
在这里插入图片描述
读者代码

在这里插入图片描述
写者代码
在这里插入图片描述
总代码

//writer
Database::Write(){
        Wait until readers/writers;
        write database;
        check out - wake up waiting readers/writers;}//reader
Database::Read(){
        Wait until no writers;
        read database;
        check out - wake up waiting writers;}//管程实现
AR =0;// # of active readers
AW =0;// # of active writers
WR =0;// # of waiting readers
WW =0;// # of waiting writers
Condition okToRead;
Condition okToWrite;
Lock lock;//writer
Public Database::Write(){//Wait until no readers/writers;StartWrite();
        write database;//check out - wake up waiting readers/writers;DoneWrite();}

Private Database::StartWrite(){
        lock.Acquire();while((AW + AR)>0){//如果临界区里面的读者或者写者正在进行操作，那么写者等待(体现写者优先)
                WW++;
                okToWrite.wait(&lock);
                WW--;}
        AW++;
        lock.Release();}

Private Database::DoneWrite(){
        lock.Acquire();
        AW--;if(WW >0){
                okToWrite.signal();}elseif(WR >0){
                okToRead.broadcast();//唤醒所有reader,可能等待的没有写者，只有读者，就把读者全部唤醒，提高效率}
        lock.Release();}//reader
Public Database::Read(){//Wait until no writers;StartRead();
        read database;//check out - wake up waiting writers;DoneRead();}

Private Database::StartRead(){
        lock.Acquire();while(AW + WW >0){//关注等待的writer,体现出写者优先
                WR++;
                okToRead.wait(&lock);
                WR--;}
        AR++;
        lock.Release();}

private Database::DoneRead(){
        lock.Acquire();
        AR--;if(AR ==0&& WW >0){//只有读者全部没有了,才需要唤醒
                okToWrite.signal();}
        lock.Release();}

❗️5.2 哲学家就餐问题（第三个经典问题）

思路1：
在这里插入图片描述

思路2：
在这里插入图片描述
思路3：
在这里插入图片描述

💤5.2.1 代码（信号量实现,也可以用管程+条件变量实现）

  • V(s[i])操作一般是通知其他进程（唤醒其他进程）
  • 状态都属于互斥，需要保护起来
'用数据结构，来描述每个哲学家的当前状态'#defineN5//哲学家个数#defineLEFT(i + N -1)% N //第i个哲学家的左邻居#defineRIGHT(i +1)% N    //第i个哲学家的右邻居#defineTHINKING0//思考状态#defineHUNGRY1//饥饿状态#defineEATING2//进餐状态typedefint semaphore;int state[N];// 跟踪每个哲学家的状态'该状态是一个临界资源，对它的访问应该互斥地进行'
semaphore mutex =1;// 临界区的互斥，临界区是 state 数组，对其修改需要互斥'一个哲学家吃饱后，唤醒临界，存在同步关系'
semaphore s[N];// 每个哲学家一个信号量(哲学家进行通信，看是否阻塞还是运行)voidphilosopher(int i){//i的取指：0到N-1while(TRUE){think(i);//S1take_forks(i);//S2-S4（拿到俩把叉子或被阻塞）eat(i);//S5（吃面条）put_forks(i);//S6-S7（把俩把叉子放回到原处）}}'要么拿到俩把叉子，要么被阻塞起来'voidtake_forks(int i){P(mutex);//hunger是需要保护的，这是写操作
    state[i]= HUNGRY;//第i个哲学家，饿了！test_take_left_right_forks(i);//试图拿俩把叉子V(mutex);P(s[i]);// 只有收到通知之后才可以开始吃，否则会一直等下去（没有叉子便阻塞）}'把俩把叉子放回原处，并在需要的时候，去唤醒左邻右舍'voidput_forks(i){P(mutex);//进入临界区
    state[i]= THINKING;//思考状态，意味着把俩把叉子放回去test_take_left_right_forks(LEFT);// 尝试通知左右邻居，自己吃完了，你们可以开始吃了——看左邻居能否进餐test_take_left_right_forks(RIGHT);//看右邻居能否进餐（之前参数i是指的自身，看自身能不能进餐）V(mutex);//与take_forks的P[s[i]]是一对的，当这里执行了V操作后，P操作才不会阻塞（我先判断左/右邻居能不能拿到俩把叉子进餐，如果可以的话，执行V操作，在执行P操作就不会阻塞，如果不执行V操作，说明它拿不到叉子此时P操作需要一直等等待）}voidthink(int i){P(&mutex);
    state[i]= THINKING;V(&mutex);}voideat(int i){P(&mutex);
    state[i]= EATING;V(&mutex);}// 检查两个邻居是否都没有用餐，如果是的话，就 V(s[i])，使得 P(s[i]) 能够得到通知并继续执行voidtest_take_left_right_forks(int i){if(state[i]== HUNGRY && state[LEFT]!= EATING && state[RIGHT]!=EATING){
        state[i]= EATING;//俩把叉子到手(只要处于eat状态，证明俩把叉子到手)'拿到俩把叉子，且通知自己可以吃饭了'V(s[i]);//通知第i人可以吃饭了,s[i]的初值为0（V操作后s[i]的值变为1），我自己可以吃饭（对自身状态做了设置），使得后面做P操作的时候不会阻塞。}}

**总结**：
  • 读者—写者问题（细分读者优先和写者优先，使用了管程的方法）
  • 哲学家问题（使用了了信号量，也可以使用管程+条件变量）
标签： 大数据 开发语言
本文转载自: https://blog.csdn.net/weixin_45043334/article/details/126533681
版权归原作者 小呆鸟_coding 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【10. 信号量和管程】”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

ManageEngine连续荣登Gartner 2024年安全信息和事件管理魔力象限

iPhone/Mac 之间跨设备拷贝/粘贴失效解决方案汇总

如何在mac电脑安装 Android SDK

一个开源的AT命令解析模块

IDEA开发Spark应用实战(Scala)

大数据相关招聘岗位可视化分析-毕业设计

第一个SpringBoot项目

文章导航