互斥锁的初步实现-阿里云开发者社区

引言

本章节我们将实现互斥锁，那么什么是互斥锁呢？什么情况下需要使用互斥锁呢？

初识互斥锁

互斥锁的作用就是让多个子进程争抢一个资源的同时，有序进行而不会同时使用，最好的比喻就是厕所坑位，一个坑位最多只能一个人使用，不能两个人同时使用一个坑位，A 发现坑位空闲，即门外标识为绿色的时候就可以直接进去使用，使用前就要把门关上，这时门外标识为红色，此时其他人就无法再使用这个坑位了，只能等 A 出来
于是我们把厕所坑位引入计算机系统，比打印机、硬盘等设备只能同时被一个任务使用，想要避免多个任务同时使用同一资源，那么就引入了互斥锁
互斥锁的本质其实就是变量的两种状态，可用和不可用，就像厕所坑位一样，绿色表示可用，红色表示不可用

思考一个问题

先来思考一个问题：互斥锁功能必须要在内核中实现吗？
貌似在用户程序中，我们也可以实现互斥锁的功能，无非就是任务在执行到临界区时判断一下该临界区（变量状态标志）是否可用，如果不可用，我们也可以用 while 等待直到满足可用条件，任务再继续向下执行
既然在用户态时我们也可以实现类似互斥锁的机制，那么我们又为什么非要把互斥锁实现在内核态中呢？
在内核态实现互斥锁我们有以下方面的考虑

进入内核态后所有任务均暂停执行，这时候就能直观的决定当前任务是否能够进入临界区，如果可以，则返回用户态，当前程序继续执行，如果不可用，则当前任务进入阻塞状态，调度下一个任务执行，如果在用户态利用 while 等待，那么 CPU 资源还一直被当前任务 while 霸占着，这显然不合理
拥有最高权限，能够决定任务的生死，如果一个任务不守规矩，想要强行获取临界资源，这时候内核能够阻止该任务，而在用户态实现互斥锁是无法做到这点的

互斥锁框架初步实现

本次代码实现见：mutex.c、mutex.h、u_syscall.c、u_syscall.h、syscall.c、app.c
关于互斥锁，首先我们能想到的就是要实现以下四个功能：创建、上锁、解锁、销毁。使用互斥锁的是用户程序，但是互斥锁的功能必须要在内核中实现，内核才有限制别人权限的资格。那么，本次实验代码我们就单纯调通互斥锁系统调用框架，参考：再论系统调用
首先在内核 “core” 文件夹下创建 “mutex.c”，修改其对应目录的 “BUILD.json” 配置文件，其中 "src" 项增加 "mutex.c", 在 “include” 文件夹下创建 “mutex.h” 头文件
在 “mutex.c” 文件中实现四个基本功能函数，当然目前是没有实现具体功能的，仅用打印替代

typedef void MUTEX; // 目前我们还不知道 MUTEX 的具体类型
// 创建互斥锁
MUTEX* SYS_MutexCreat(void)
{
    printk("SYS_MutexCreat\n");
    return (MUTEX*)0x1234;
}
// 上锁
E_RET SYS_MutexLock(MUTEX* mutex)
{
    printk("SYS_MutexLock\n");
    return E_OK;
}
// 解锁
E_RET SYS_MutexUnLock(MUTEX* mutex)
{
    printk("SYS_MutexUnLock\n");
    return E_OK;
}
// 销毁互斥锁
E_RET SYS_MutexDestory(MUTEX* mutex)
{
    printk("SYS_MutexDestory\n");
    return E_OK;
}

系统调用分两部分，一部分在内核中，这是功能的真正实现，还有一部分在 “user” 文件夹下的 “u_syscall.c”，仅是接口实现

// 创建互斥锁
MUTEX* MutexCreat(void)
{
    return (MUTEX*)_SYS_CALL0(_NR_MutexCreat);
}
// 上锁
E_RET MutexLock(MUTEX* mutex)
{
    return _SYS_CALL1(_NR_MutexLock, mutex);
}
// 解锁
E_RET MutexUnLock(MUTEX* mutex)
{
    return _SYS_CALL1(_NR_MutexUnLock, mutex);
}
// 销毁互斥锁
E_RET MutexDestory(MUTEX* mutex)
{
    return _SYS_CALL1(_NR_MutexDestory, mutex);
}

别忘了修改内核 “syscall.c” 中 syscall_table，这里要注意 SYS_xxx 函数在 syscall_table 数组中的位置要与接口层 user 中的 _SYS_CALLx 调用第一个参数要一致

SYSCALL_FUNC syscall_table[] = {
    ...
    (SYSCALL_FUNC)SYS_MutexCreat,
    (SYSCALL_FUNC)SYS_MutexLock,
    (SYSCALL_FUNC)SYS_MutexUnLock,
    (SYSCALL_FUNC)SYS_MutexDestory,
};

关于互斥锁的系统调用整个流程都已经实现了，现在我们在 app 中调用互斥锁相关接口函数测试一下

MUTEX* mutex = NULL;
void TaskAFunc(void)    // 任务执行函数
{
  ...
  mutex = MutexCreat();
  print("mutex = %x\n", mutex);
  MutexLock(mutex);
  MutexUnLock(mutex);
  MutexDestory(mutex);
  ...
}

成果展示

进一步完善互斥锁

上面我们已经打通了互斥锁从应用层到内核的系统调用，接下来自然就是在内核中具体实现互斥锁相关功能函数了
本次代码实现见：mutex.c、mutex.h
互斥锁的本质就是一个变量，其有两种状态（可用和不可用），为了管理这些变量，我们可以把所有的互斥锁变量以链表的形式进行管理
上面我们当时由于不确定 MUTEX 类型，所以暂时用 typedef void MUTEX; 替代。现在我们重新定义互斥锁 MUTEX 类型，其中 lock 变量表示可用状态（0：可用；1：不可用）；node 为链表节点，用于操作链表

typedef struct MUTEX
{
    LIST_NODE   node;
    U08         lock;
} MUTEX;

既然使用互斥锁使用链表来进行管理，那么在使用链表前，我们当然要创建一个链表并对其进行初始化啦（在 "main.c" 中调用初始化函数）

static LIST MUTEX_LIST;         // 互斥锁链表
void MutexInit(void)
{
    ListInit(&MUTEX_LIST);
}

准备工作都已经做好了，接下来就是实现前面四个互斥锁的相关功能函数，由于我们已经实现了动态内存分配，所以互斥锁链表节点我们就可以通过申请来获得内存空间啦

// 创建互斥锁
MUTEX* SYS_MutexCreat(void)
{
    MUTEX* mutex = (MUTEX *)Malloc(sizeof(MUTEX));
    if(NULL == mutex)
        return NULL;
    mutex->lock = 0;                              // 可用状态
    ListAddHead(&MUTEX_LIST, (LIST_NODE *)mutex); // 头插
    return mutex;
}
// 上锁
E_RET SYS_MutexLock(MUTEX* mutex)
{
    // 检查参数合法性
    if(NULL == mutex || !CheckMutex(mutex))
        return E_ERR;
    // 如果互斥锁处于空闲状态，则将其上锁，否则，将当前任务放到等待队列中并立即切换到下一个任务
    if(0 == mutex->lock)
        mutex->lock = 1;
    else
        printk("switch to next task, wait...\n");
    return E_OK;
}
// 解锁
E_RET SYS_MutexUnLock(MUTEX* mutex)
{
    // 检查参数合法性
    if(NULL == mutex || !CheckMutex(mutex))
        return E_ERR;
    // 将互斥锁设置为空闲可用状态
    mutex->lock = 0;
    return E_OK;
}
// 销毁
E_RET SYS_MutexDestory(MUTEX* mutex)
{
    // 检查参数合法性
    if(NULL == mutex || !CheckMutex(mutex))
        return E_ERR;
    // 删除链表节点并释放内存
    ListDelNode(&mutex->node);
    Free(mutex);
    return E_OK;
}

互斥锁关键设计与实现

思考一下当前我们已经实现的代码，目前我们已经打通了从用户态到内核态上锁和解锁的状态设置，然而，这就是互斥锁的全部了吗？
很显然，互斥锁的互斥属性我们并没有实现，现在我们还不能做到当一个任务对临界资源进行访问时，另一个任务就无法同时对这个临界资源进行访问
那么我们应该如何设计呢？
设计方案：当一个任务将要临界资源，且该临界资源已被上锁时，我们把该任务从任务就绪队列中取出，转移到一个等待队列中，然后从任务就绪队列中再取出一个任务并切换到该任务执行，这种我们也称之为阻塞。当临界资源互斥锁状态变为空闲状态时，即解锁，此时我们再把任务从等待队列中移到就绪队列，就绪队列中的任务即可以被调度执行
本次代码实现见：mutex.c、mutex.h、schedule.c、schedule.h、queue.c、queue.h、app.c
首先，我们在互斥锁 MUTEX 结构体类型中添加 QUEUE wait 元素，其作用是作为等待该互斥锁的任务链表头，即当同时有多个任务等待该互斥锁时，我们把这些任务从任务就绪队列中转移到 wait 队列中。

typedef struct MUTEX
{
    LIST_NODE   node;       // 互斥锁链表节点
    U08         lock;       // 锁状态
    QUEUE       wait;       // 等待该互斥锁的任务队列（每个互斥锁都有一个等待队列）
} MUTEX;

互斥锁中添加了等待队列，那么不要忘记给等待队列初始化，这里坑了我好几个小时

MUTEX* SYS_MutexCreat(void)
{
    ...
    QueueInit(&mutex->wait);                      // 初始化互斥锁中的等待队列
    ...
}

下面我们就来实现一个函数，其功能是将当前任务从就绪队列中移到互斥锁中的 wait 等待队列中，并从原就绪队列中重新取一个任务节点执行，可以参考以前实现过的 SYS_TaskDestory 函数，它们之间的区别就是将释放 Free(task) 改为 QueueAdd(&mutex->wait, nodeTmp)，因为跟调度相关，所以我们把代码写到 "schedule.c" 文件中好了

实现了互斥锁的等待机制，接下来就是当互斥锁释放时，将该互斥锁等待队列中的任务取一个出来放到就绪队列中

E_RET MutexResume(MUTEX* mutex)
{
    QUEUE_NODE* nodeTmp = NULL;
    // 从互斥锁的等待队列中取出一个任务，并将其添加到就绪队列中
    nodeTmp = QueueRemove(&mutex->wait);
    if(NULL == nodeTmp)
        return E_ERR;
    QueueHeadAdd(&TASK_READY_QUEUE, nodeTmp);
    return E_OK;
}

QueueHeadAdd() 函数之前我们并没有实现过，现在实现好了，主要是想将任务加到就绪队列头，下次调度能够较快执行

void QueueHeadAdd(QUEUE* queue, QUEUE_NODE* node)
{
    ListAddHead((LIST *)queue, node);
    queue->length++;
}

搞清楚 MutexSuspend 和 MutexResume 函数的调用位置

E_RET SYS_MutexLock(MUTEX* mutex)
{
    ...    
    // 如果互斥锁处于空闲状态，则将其上锁，否则，将当前任务放到等待队列中并立即切换到下一个任务
    if(0 == mutex->lock)
        mutex->lock = 1;
    else
        MutexSuspend(mutex);
    ...
}
E_RET SYS_MutexUnLock(MUTEX* mutex)
{
    ...
    // 将互斥锁设置为空闲可用状态，并将互斥锁等待队列中的任务放回到就绪队列中
    mutex->lock = 0;
    MutexResume(mutex);
}

最后我们修改 “app.c” 中的任务代码，测试一下互斥锁的功能吧

MUTEX* gMutex = NULL;
void TaskAFunc(void)    // 任务执行函数
{
    gMutex = MutexCreat();
    MutexLock(gMutex);
    for(int i = 0; i < 10; i++)
    {
        print("a"); 
        {volatile U32 cnt = 999999; while(cnt--);}
    }
    MutexUnLock(gMutex);
}
void TaskBFunc(void)    // 任务执行函数
{
    while(1)
    {
        MutexLock(gMutex);
        for(int i = 0; i < 4; i++)
        {
            print("b"); 
            {volatile U32 cnt = 999999; while(cnt--);}
        }
        MutexUnLock(gMutex);
    }
}

看一下我们努力的成果，任务 A 打印完 10 个字符 ‘a’ 后任务 B 才能开始打印，符合我们的互斥锁预期效果，自己可以测试一下把互斥锁代码注释掉，那么将会交叉打印字符 ‘a’ 和 ‘b’

发现问题一

经过不懈地努力，看起来我们已经有了一个能用的互斥锁了，深入思考一下，我们实现的互斥锁完善吗？
嗯~~，何止是不完善啊，简直是漏洞百出，不忍直视，为了直观的看问题，我们增加一些打印信息

E_RET SYS_MutexLock(MUTEX* mutex)
{
    ...
    // 如果互斥锁处于空闲状态，则将其上锁，否则，将当前任务放到等待队列中并立即切换到下一个任务
    if(0 == mutex->lock)
    {
        printk(" %s Lock\n", current_task->name);
        mutex->lock = 1;
    }
    else
    {
        printk(" %s enters the waiting queue\n", current_task->name);
        MutexSuspend(mutex);
    }
    ...
}
E_RET SYS_MutexUnLock(MUTEX* mutex)
{ 
    ...
    // 将互斥锁设置为空闲可用状态，并将互斥锁等待队列中的任务放回到就绪队列中
    mutex->lock = 0;
    printk(" %s Unlock\n", current_task->name);
    MutexResume(mutex);
    ...
}

运行程序，分析下面的打印信息，首先调度运行任务 A，任务 A 加锁，打印 ①，接着任务 A 向下执行，打印 ②，再往后任务 B 被调度执行，任务 B 发现已加锁，于是任务 B 从就绪队列中移到等待队列，打印 ③，于是系统重新调度任务 A 执行，直到任务 A 释放锁，打印 ④，锁释放之后，任务 B 就从等待队列中转移到就绪队列中并等待调度执行，打印 ⑤，再往后由于任务 A 已经执行完销毁，所以只有任务 B 执行。整个流程看起来没什么问题，但是仔细看 ④ 和 ⑤ 之间缺少了任务 B 的加锁打印信息，即当任务 A 释放锁之后，任务 B 在拿到锁之后并没有再次加锁就继续向下执行了

发现问题二

思考一下下面的几个情况：任务 A 创建锁后连续两次加锁，任务 B 不按套路出牌，先执行解锁操作，然后再尝试获取锁，任务 C 呢？明明不需要互斥锁，但是却使坏，把互斥锁给销毁了
就我们当前实现的互斥锁代码，如果任务 A 第一次拿到了互斥锁，第二次又加锁了一次，那么就会造成任务 A 自己把自己挂起，造成死锁，对于任务 B，先执行解锁操作，很显然，是可以解锁成功的，怎么能非法解锁其它任务的加锁呢？对于任务 C，即便是任务 A 或 B 已经将互斥锁加锁，然而任务 C 却依旧可以强行把这个互斥锁销毁，正常来讲只有在互斥锁解锁状态才能销毁

互斥锁的初步实现

引言

初识互斥锁

相关概念

思考一个问题

互斥锁框架初步实现

进一步完善互斥锁

互斥锁关键设计与实现

发现问题一

发现问题二

后续

热门文章

最新文章

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

互斥锁的初步实现

引言

初识互斥锁

相关概念

思考一个问题

互斥锁框架初步实现

进一步完善互斥锁

互斥锁关键设计与实现

发现问题一

发现问题二

后续

热门文章

最新文章

相关电子书