doc/互斥锁的初步实现.md · 稀风/KOS

引言

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

初识互斥锁

互斥锁的作用就是让多个子进程争抢一个资源的同时，有序进行而不会同时使用，最好的比喻就是厕所坑位，一个坑位最多只能一个人使用，不能两个人同时使用一个坑位，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 MutexSuspend(MUTEX* mutex)
{
    QUEUE_NODE* nodeTmp = NULL;

    // 把当前任务节点从就绪任务队列中取出，当前任务节点在队列尾，取出后添加到 wait 队列中
    nodeTmp = QueueTailRemove(&TASK_READY_QUEUE);
    if(NULL == nodeTmp)
        return E_ERR;
    QueueAdd(&mutex->wait, nodeTmp);  // 这是该函数与 SYS_TaskDestory 函数的唯一区别

    // 从就绪任务队列中取出一个任务节点并执行该任务，再将该任务节点重新添加到就绪任务队列中
    nodeTmp = QueueRemove(&TASK_READY_QUEUE);
    if(NULL == nodeTmp)
        return E_ERR;
    current_task = (volatile TASK *)QUEUE_NODE(nodeTmp, TASK, node);
    QueueAdd(&TASK_READY_QUEUE, nodeTmp);

    TSS* tss = (TSS*)(*(U32*)TSS_ENTRY_ADDR);                             // 找到 TSS
    tss->esp0 = (U32)(&current_task->reg) + sizeof(current_task->reg);    // TSS.esp0 指向任务上下文数据结构 reg 的末尾
    current_reg = (U32)(&current_task->reg);                              // current_reg 指向任务上下文数据结构 reg 的起始位置
    SWITCH_TO(current_task);
  
    return E_OK;
}

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

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 却依旧可以强行把这个互斥锁销毁，正常来讲只有在互斥锁解锁状态才能销毁

稀风 / KOS

引言

初识互斥锁

相关概念

思考一个问题

互斥锁框架初步实现

进一步完善互斥锁

互斥锁关键设计与实现

发现问题一

发现问题二

后续

简介

发行版

贡献者

近期动态

稀风 / KOS .gitee-modal { width: 500px !important; }

引言

初识互斥锁

相关概念

思考一个问题

互斥锁框架初步实现

进一步完善互斥锁

互斥锁关键设计与实现

发现问题一

发现问题二

后续

简介

发行版

贡献者

近期动态

搜索帮助

稀风 / KOS