引言
- 本章节我们将实现互斥锁，那么什么是互斥锁呢？什么情况下需要使用互斥锁呢？
初识互斥锁
- 互斥锁的作用就是让多个子进程争抢一个资源的同时，有序进行而不会同时使用，最好的比喻就是厕所坑位，一个坑位最多只能一个人使用，不能两个人同时使用一个坑位，A 发现坑位空闲，即门外标识为绿色的时候就可以直接进去使用，使用前就要把门关上，这时门外标识为红色，此时其他人就无法再使用这个坑位了，只能等 A 出来
- 于是我们把厕所坑位引入计算机系统，比打印机、硬盘等设备只能同时被一个任务使用，想要避免多个任务同时使用同一资源，那么就引入了互斥锁
- 互斥锁的本质其实就是变量的两种状态，可用和不可用，就像厕所坑位一样，绿色表示可用，红色表示不可用
相关概念
- 临界资源（Critical Resource）：每次只允许一个任务进行访问（读/写）的资源
- 临界区（Critical Section）：每次只允许一个任务执行的代码片段
- 任务间的同步：在一些情况下，控制多个任务的执行顺序，即不允许多个任务同时执行
- 任务间的互斥：多个任务同一时刻都需要访问同一个临界资源，此时只能有一个任务访问临界资源，其它任务必须等待
- 互斥锁：互斥锁是一种特殊的状态变量（空闲状态和占用状态），当互斥锁处于空闲状态时，任务可成功获取锁，访问临界资源，锁被任务获取后，自动转为占用状态；当互斥锁处于占用状态时，试图获取锁的任务会被阻塞，直到锁再次转化为空闲状态
思考一个问题
- 先来思考一个问题：互斥锁功能必须要在内核中实现吗？
- 貌似在用户程序中，我们也可以实现互斥锁的功能，无非就是任务在执行到临界区时判断一下该临界区（变量状态标志）是否可用，如果不可用，我们也可以用 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 却依旧可以强行把这个互斥锁销毁，正常来讲只有在互斥锁解锁状态才能销毁
后续
- 以上问题我们将放在下一章节解决
