信号量（Semaphores）机制

信号量实现互斥的基本原理

为实现实现进程的互斥与同步，多个进程通过相互传递信号进行合作，迫使某个进程收到信号自动的暂停执行（阻塞等待），直到他收到唤醒信号。
类比：一堆人排队看病。第一个来的人看见亮绿灯，直接进去，第二个看到里面亮红灯，睡觉休息。看好病的认出来灯变成绿灯，但是都睡着了，要去叫醒下一个病人。

信号量定义

• Value：资源数，目类比为——诊所一次性可以接待的人

  • 若value为1，表示访问临界资源，则是处理互斥情况
  • 若value大于1，表示访问非临界资源，处理的是进程同步问题

• L：list of process，进程链表，链接所有的等待的进行进程。就是上图的排队看病的病人。

定义信号量的两个原子操作（Atomic Operation）——每个病人必须都会的能力

1. wait（S）/P（S），整型信号量——判断诊所有没有人和睡觉的能力

• 使信号量的值减一（申请一个单位的资源）
• 判定条件（根据信号量决定自己的具体执行）
  • 如果信号量的值为负数，其绝对值代表正在排队等待，陷入阻塞的进程。同时系统资源已经分配完毕，进程自己阻塞在S的队列上，等待阻塞；
  • 如果信号量的值为正数，其意义为诊所还可以再治疗一个人；资源尚有剩余，可以直接仅需占用资源无需等待

s = s - 1;
//申请占用一个资源 
if s < 0
//占用之后小于零，说明已经没有资源使用
then begin 
  进程阻塞
  进程进入S.L队列等待
end

2. signal（S）/V(S)，整型变量——叫醒下一个人

• 使信号量的值减一（归还一个单位的资源）
• 判定条件 （根据信号量决定自己的具体执行）
  • 如果信号量的值为负数，说明仍旧有病人再睡觉等待，则要去叫醒下一个病人。即唤醒仍旧在排队等待的进程
  • 如果信号量的值为正数，说明没有病人在等待，无需叫醒别人，走就行了。

s = s + 1;
//结束占用，归还资源 
if s <=0
//s为零，说明仅仅只有一个一个进行排队，要叫醒它
//s为负数，说明有不止一个在排队，
then begin 
  唤醒队首进程；
  将进程从S.L阻塞队列中移除；
end

3. S.value的初值标识系统中某种资源的数目，称之为资源信号量，执行wait（S）|P(S)操作是申请占用资源，但不是分配资源，分配资源是在执行时进行的；signal（S）|V(S)每一次操作，是释放一个单位的资源

信号量机制的通用模式

wait，signal的注意事项

1. wait和signal的执行时机：
   • wait：是在进入临界区的前的进入区，并不涉及到分配资源，分配资源，就意味着执行。
   • signal：是在退出临界区的退出区

2. 注意两个语句的判定条件是不一样的，都是先对临界资源数目进行操作。
   wait判定条件是小于零，已经申请了一个资源，若此时还为0，说明就只有一个资源，刚好你取了，所以要去执行。所以判定条件是小于零。
   
   signal（S）判定条件是小于等于0。signal是否唤醒的条件是有唤醒的对象，资源符号量的正数表示有资源，非正数表示有人在排队。

信号量的类型

1. 信号量分为：互斥信号量和资源信号量

• 互斥信号量的初始化为1，主要用于使用共享资源的约束关系。
• 资源信号量的初始化为大于1的整数，主要用于进程之间存在一定的逻辑关系，需要再执行次序上进行协调。

2. wait（S）操作用于申请资源，执行者会主动陷入阻塞状态
3. signal（S）操作用于释放资源，执行者会主动唤醒处于阻塞状态的其他进程，其他进程被动唤醒。

注意

在一个多道程序系统之间，进程之间存在着不同关系，可以大致划分为两大类：其中同步指的是进程之间存在一定的逻辑关系，需要在执行次序上协调：互斥是指进程间在使用共享资源方面上的约束关系。解决上述两个问题常用的方法是信号量机制。

1. 背景

前段时间老师上课讲到了uC/OS中的信号量机制，所以我想要结合《μC/OS-III源码分析笔记》和中国大学MOOC-电子科技大学《嵌入式系统及应用》PPT写一篇笔记对这部分的内容进行总结。

2. 概述

2.1. 主要机制及应用

$$\text{Figure 1. 模型}$$

• 在单处理器平台上，嵌入式操作系统内核提供的同步、互斥与通信机制
  主要包括：
  • 信号量（semaphore），用于互斥与同步。
  • 事件（组）（event group），用于同步。
  • 邮箱（mailbox）、消息队列（message queue），用于消息通信。
  • 异步信号（asynchronous signal），用于同步。
  • 管道（pipe），提供非结构化数据交换（通信）和实现同步。
• 单处理器或多处理器系统中，还有其它一些机制也可用于同步与通信：
  • 全局变量
  • 共享内存
  • Sockets
  • 远程过程调用（Remote Procedure Call）

2.2. 同步或通信的基本方式

$$\text{Figure 2. 同步或通信的基本方式}$$

3. 信号量

3.1. 主要机制及应用

• 在单处理器平台上，嵌入式操作系统内核提供的同步、互斥与通信机制 主要包括:
  • 信号量(semaphore)，用于互斥与同步。
  • 事件(组)(event group)，用于同步。
  • 邮箱(mailbox)、消息队列(message queue)，用于消息通信。
  • 异步信号(asynchronous signal)，用于同步。
  • 管道(pipe)，提供非结构化数据交换(通信)和实现同步。
• 单处理器或多处理器系统中，还有其它一些机制也可用于同步与通信: 全局变量、共享内存、Sockets、远程过程调用(Remote Procedure Call)。

3.2. 分类

信号量用于实现任务与任务之间、任务与中断处理程序之间的同步与 互斥。信号量一般分为三种:

• 互斥信号量:用于解决互斥问题，可能会引起优先级反转问题。
• 二值信号量:用于解决同步问题
• 计数信号量:用于解决资源计数问题

3.3. 互斥信号量

• 用互斥信号量保护的代码区称作临界区，临界区代码通常用 于对共享资源的访问。
• 共享资源可能是一段存储器空间、一个数据结构或I/O设备，也 可能是被两个或多个并发任务共享的任何内容。
• 使用互斥信号量可以实现对共享资源的串行访问，保证只有成功 地获取互斥信号量的任务才能够释放它。
• 互斥信号量基本特点:互斥信号量的值被初始化成1，最多只有 一个任务可以进入临界区。

$$\text{Figure 3. 互斥信号量状态图}$$

• 互斥信号量是一种特殊的二值信号量，一般它支持所有权、递归访 问、任务删除安全和一些避免优先级反转、饥饿、死锁等互斥所固 有问题的协议。
• 所有权:当一个任务通过获取互斥信号量而将其锁定时，得到该互 斥信号量的所有权。相反，当一个任务释放信号量时，失去对其的 所有权。

3.3.1. 嵌套(递归)资源访问

• 嵌套(递归)资源访问:如果Task1调用RoutineA，而RoutineA 又调用RoutineB，并且三者访问相同的共享资源，就发生了递归共 享资源的访问同步问题。
• 一个递归的互斥信号量允许嵌套锁定互斥信号量，而不引起死锁。
• 每个获取信号量的调用必须与释放信号量的调用相匹配。
• 用于同步的信号量不支持嵌套访问，否则任务会被永久阻塞。

3.3.2. 删除安全

• 删除安全:在一个受信号量保护的临界区，经常需要保护在临界区执行的任务不会被意外地删除。
• 删除一个在临界区执行的任务可能引起意想不到的后果，造成信号量不可用或资源破坏。
• 解决方法:提供任务保护和解除任务保护原语对。

3.4. 各种互斥机制的比较

$$\text{Figure 4. 各种互斥机制的比较}$$

3.5. 二值信号量

二值信号量主要用于任务与任务之间、任务与中断服务程序之间的 同步。二值信号量的初始值为0，表示同步事件尚未产生。

$$\text{Figure 5. 二值信号量状态图}$$

用二值信号量实现任务间双向同步时，申请者和释放者不是同一个任务，与互斥信号量不同。互斥信号量必须谁申请，谁释放。

$$\text{Figure 6. 用二值信号量实现任务间双向同步}$$

3.6. 计数信号量

• 计数信号量用于控制系统中共享资源的多个实例的使用，允许多个 任务同时访问同一种资源的多个实例。
• 计数信号量被初始化为一个非负整数n，即该种共享资源的数目。

$$\text{Figure 7. 计数信号量状态图}$$

$$\text{Figure 8. 有界缓冲问题1}$$

$$\text{Figure 9. 有界缓冲问题}$$

4. uC/OS-II中实现

4.1. 创建信号量

OS_EVENT* OSSemCreate(INT16U cnt)
{
    OS_EVENT* pevent;
    pevent = OSEventFreeList; //从空闲事件控制块链中取得一个ECB
    if (OSEventFreeList != (OS_EVENT*)0) {
        OSEventFreeList = (OS_EVENT*) { OSEventFreeList->OSEventPtr; }
        if (pevent != (OS_EVENT*)0) { //初始化ECB的各个域
            pevent->OSEventType = OS_EVENT_TYPE_SEM; //事件类型为信号量
            //信号量的初始计数值
            pevent->OSEventCnt = cnt;
            pevent->OSEventPtr = (void*)0;
            OS_EventWaitListInit(pevent); //初始化等待任务列表
        }
    }
    return (pevent); //调用者需检查返回值，如果为NULL则表示建立失败
}

说明：这是针对计数信号量和二值信号量的实现。 μC/OS-II中互斥 信号量的实现参见源码os_mutex.c文件。

$$\text{Figure 10. 基本流程}$$

4.2. 获取(申请)信号量

void OSSemPend(OS_EVENT* pevent, INT16U timeout, INT8U* err)
{
    //信号量值大于0，成功获得信号量并返回
    if (pevent->OSEventCnt > 0) {
        pevent->OSEventCnt--;
        *err = OS_NO_ERR;
        return;
    }
    //设置任务状态为等待信号量
    OSTCBCur->OSTCBStat |= OS_STAT_SEM;
    //设置等待时限
    OSTCBCur->OSTCBDly = timeout;
    //将任务放置到信号量的等待列表中
    OS_EventTaskWait(pevent);
    //内核实施任务调度，系统切换到另一就绪任务执行
    OS_Sched();
    //判断任务恢复执行的原因，如果等待时限超时但仍然未获得信号量，则返回超时信息
    if (OSTCBCur->OSTCBStat & OS_STAT_SEM) {
        OSEventTO(pevent);
        *err = OS_TIMEOUT;
        return;
    }
    OSTCBCur->OSTCBEventPtr = (OS_EVENT*)0;
    *err = OS_NO_ERR; //任务由于获得信号量而恢复执行，本调用成功返回
}

说明：这里同样是针对计数信号量和二值信号量的实现。

---

OSSemAccept也可以实现获取(申请)信号量的功能。

INT16U OSSemAccept(OS_EVENT* pevent)
{
    INT16U cnt;
    cnt = pevent->OSEventCnt;
    if (cnt > 0) {
        pevent->OSEventCnt--;
        }
    return (cnt);
}

• 功能：无等待的获取或申请一个信号量。
• 注意：即使不能成功获得信号量(返回值为0)，调用者也不 会被阻塞。此函数可以在中断处理程序中使用。

4.3. 释放信号量

$$\text{Figure 12. 释放信号量}$$

INT8U OSSemPost(OS_EVENT* pevent)
{

    if (pevent->OSEventGrp != 0x00) { //如果有任务在等待该信号量
        OS_EventTaskRdy(pevent, (void*)0, OS_STAT_SEM); //使等待列表中优先级最高的任务就绪
        OS_Sched(); //内核实施任务调度
        return (OS_NO_ERR); //成功返回
    }
    if (pevent->OSEventCnt < 65535) { //如果没有任务等待该信号量，并且信号量的值未溢出
        pevent->OSEventCnt++; //信号量的值加1
        return (OS_NO_ERR); //成功返回
    }
    return (OS_SEM_OVF); //信号量溢出
}

4.4. 删除信号量

$$\text{Figure 13. 删除信号量}$$

OS_EVENT* OSSemDel(OS_EVENT* pevent, INT8U opt, INT8U* err)
{
    BOOLEAN tasks_waiting;
    if(pevent->OSEventGrp!=0x00{//根据是否有任务在等待信号量设置等待标志
            tasks_waiting = TRUE;
    }else{
            tasks_waiting = FALSE;
    }
    switch(opt){
        case OS_DEL_NO_PEND: //如果有任务等待信号量则不删除信号量
            if(task_waiting==FALSE{ //没有任务等待，释放ECB回空闲链
                pevent->OSEventType = OS_EVENT_TYPE_UNUSED;
                pevent->OSEventPtr = OSEventFreeList;
                OSEventFreeList = pevent; //调整空闲ECB链头指针
                *err = OS_NO_ERR;
                return ((OS_EVENT)0);
            }else{
                *err = OS_ERR_TASK_WAITING; //有任务等待，删除信号量失败
                return (pevent);
            }
        case OS_DEL_ALWAYS: //无论有无任务等待都删除信号量
                //将等待列表中的每个任务都设置成就绪
                while (pevent->OSEventGrp != 0x00) {
                OS_EventTaskRdy(pevent, (void*)0, OS_STAT_SEM);
                }
                pevent->OSEventType = OS_EVENT_TYPE_UNUSED;
                pevent->OSEventFreeList;
                OSEventFreeList = pevent; //释放该信号量的ECB回空闲控制块链
                if (tasks_waiting == TRUE) {
                OS_Sched();
                } //如果之前有任务等待信号量，内核实施任务调度
                *err = OS_NO_ERR;
                return ((OS_EVENT*)0);
        default:
                *err = OS_ERR_INVALID_OPT;
                return (pevent);
        }
}

---

联系邮箱：curren_wong@163.com

CSDN：https://me.csdn.net/qq_41729780

知乎：https://zhuanlan.zhihu.com/c_1225417532351741952

公众号：复杂网络与机器学习

欢迎关注/转载，有问题欢迎通过邮箱交流。

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

 

 

 

信号量其实就是一个变量（可以是一个整数，也可以是一个更复杂的变量），可以用信号量来表示系统中某种资源的数量。比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

P、V操作：

P表示通过，V表示释放

 

 

 1.整型信号量：

整型信号量与普通的信号量的区别：

对信号量的操作只有：初始化、P操作、V操作 

 

缺点：不满足“让权等待”原则，会发生“忙等”

 2.记录型信号量：

 

在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应该增加一个进程链表指针L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。

例题： 

 

 用P、V操作进行进程的通过和释放，再加入原语来实现进程的“上锁”和“解锁”，等资源使用完毕，再利用block原语进行阻塞（主动让出处理机），该机制遵循了“让权等待”的原则。

 

 

 

 

 

 3.AND型信号量：

AND型信号量在一些应用场合，是一个进程需要先获得两个或者更多的共享资源后方能执行其任务。

 

 AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配给进程，要么一个也不分配。由死锁理论可知，这样就可以避免上述死锁情况发生。为此，在wait操作中，增加一个“AND”条件，故称为AND同步，或称为同时wait操作。

 

 缺点：AND型信号量满足了 “多种资源，数量为1”的使用情景，但是实际上还会有多种资源数量不固定的情景，AND型信号量显然处理不了这种情况的进程调度。

 

 死锁的概念：

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去；此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

 

 

 4.信号量集：

信号量集由两部分组成：标识组和等待任务列表；

标识组由三部分组成：1.OSFlagType——识别是否为信号量集的标志

                                    2.OSFlagWaitList——指向等待任务列表的指针

                                    3.OSFlagFlags——信号量表

注意：信号量集的标识组只是保存了各输入信号量的值，而至于如何对这些任务进行处理则是等待任务的事情。

等待任务必须完成以下两个操作：1.在多个信号量输入中挑选等待任务感兴趣的输入。

                                                      2.把挑选出来的输入按照等待任务所期待的方式运算，以得到输出。

1. 信号量集的标志组

UCOS不是使用事件控制块的结构描述信号量集，而是使用一个标志组的机构来描述信号量集OS_FLG_GRP

2. 等待任务链表

与其他事件不同，信号量集采用一个双向链表来组织等待任务。标志组OS_FLG_GRP的成员OSFlagWaitList指向信号量集的这个等待任务链表。

等待任务链表中的节点OS_FLAG_NODE中的成员OSFlagNodeFlags相当于一个过滤器，它可以将请求任务需要的信号筛选出来，不需要的信号屏蔽掉。

对等待任务链表的操作：添加节点和删除节点。

“信号量集”的三种特殊情况：

​ (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量S， 但允许它每次申请d个资源，当现有资源数少于d时，不予分配。

​ (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。

​ (3) Swait(S, 1, 0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。
 

信号量的应用：

• 利用信号量实现进程互斥关系
• 利用信号量实现进程同步关系
• 利用信号量实现进程前趋关系

小结：

 

 

 

 

 

 5.信号量实现进程的互斥：

 

 

解释一下互斥原理：

           先设置一个互斥信号量mutex（可自己定义），再初始化信号量，使mutex=1，然后进行P操作（申请资源使用），这时候mutex-1，即mutex=0，对这个资源进行“加锁”，别人无法再使用这个资源，也就是相当于（C语言中for循环的条件判断，满足条件就进行，不满足就跳出），等程序使用资源完毕时，就会进行V操作（释放资源），对资源进行“解锁”，这时候mutex+1，重新使mutex=1，使资源解放出来，等待下一个程序的使用。

 6.信号量机制实现进程同步：

 

进程同步：要让各进程按要求有序地进行推进。

 

 

解释一下进程同步的原理：

         让各进程按要求有序地进行推进，先将初始化同步信号量的初始值设置为0。我们让代码4在代码2之后进行执行，这时候因为异步性，不知道是P1进程先进行还是P2进程先进行，我们先在代码2后面设置一个V（S）操作，在代码4后面设置一个P(S)操作。【可能有以下两种情况】

1.当先进行P1进程时，进程会按照代码1，代码2的顺序进行，当执行完代码2时，到达了V（S）操作，这时候将资源释放了出来，这时候初始值增加（S+1），接着进行P2进程，由于P2中进行了P(S)[申请资源]的操作，所以进程会按照代码4，代码5，代码6进行下去。

2.当先进行P2进程时，会遇到P(S)，但这时候的初始值为0，无法提供资源，P2进程进入自我阻塞状态。然后就进行P1进程的执行。这样就实现了让各进程按要求有序地进行推进。也就是实现了进程同步。

 

 

 

 7.信号量机制实现前驱关系：

 

前驱关系本质上就是更复杂的同步问题。

在这一个进程实现之后执行V操作

在下一个进程实现之前执行P操作

 

 

 总结：

 

 

 

         这篇文章写了三个半小时，先进行看视频学习，两个视频反复看了两三遍，等自己理解之后，再写，进行整理和写上了自己对内容的理解，感觉虽然时间花费的比较多，但这些内容自己都理解了，还拓展了一部分，感觉自己棒棒，哈哈 。