投稿
  1. 首页
  2. 服务器知识

linux下信号量和互斥锁的区别

小夏•2023-3-13•服务器知识•阅读52

linux下信号量和互斥锁的区别,第1张

信号量用在多线程多任务同步的，一个线程完成了某一个动作就通过信号量告诉别的线程，别的线程再进行某些动作（大家都在semtake的时候，就阻塞在哪里）。

而互斥锁是用在多线程多任务互斥的，一个线程占用了某一个资源，那么别的线程就无法访问，直到这个线程unlock，其他的线程才开始可以利用这个资源。比如对全局变量的访问，有时要加锁，操作完了，在解锁。

有的时候锁和信号量会同时使用的。我记得以前做的一个项目就是既有semtake，又有lock。

信号量的数值仅能由P，V原语操作改变。采用P，V原语，可以把类名为S的临界区描述为When S do P(sem)临界区V(sem)od。

这里，sem是与临界区内所使用的公用资源有关的信号量。一次P原语操作使得信号量sem减1，而一次V原语操作使得信号量sem加1。必须强调的一点是，当某个进程正在临界区内执行时，其他进程如果执行了P原语操作，则该进程并不像调用lock时那样因进不了临界区而返回到lock的起点，等以后重新执行测试，而是在等待队列中等待有其他进程做V原语操作释放资源后，进入临界区，这时，P原语的执行才算真正结束。另外，当有好几个进程执行P原语操作未通过而进入等待状态之后，如有某进程作了V原语操作，则等待进程中的一个可以进入临界区，但其他进程必须等待。

P原语操作的主要动作是：

（a）sem减1；

（b）若sem减1后仍大于或等于零，则进程继续执行；

（c）若sem减1后小于零，则该进程被阻塞后与该信号相对应的队列中，然后转进程调度。

V原语操作的主要动作是：

（a）sem加1；

（b）若相加结果大于或等于零，则进程继续执行；

（c）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。

通用有序平衡二叉树接口描述

这套代码对用户屏蔽了复杂的二叉树的旋转操作，不区分用户的数据类型，任何数

据都可以用有序平衡二叉树来存放。我还对平衡二叉树进行了一点点扩展，在树结构里

面增加了保持线行递增（或递减）顺序的双向链表，方便使用者能够快速按序遍历所有

树节点。

这套代码需要用户直接参与的部分都用注册函数来实现，让使用者完全不需要了解

有序平衡二叉树的添加、删除或查找的过程，能够做到傻瓜式的使用。至于性能，我添

加过300万个树节点之后，树高只有22层，查找任意一个节点最多只需要22次匹配操作。

比HASH表快了很多。

这套代码还针对vxworks操作系统做了一点点扩展，其实就是判断一下当前操作系统

是否是vxworks，如果是的话就创建一个二进制信号量，如果不是就什么信号量也不创建。

目前此版本提供了如下通用接口：

1、数据结构定义

1.1、树的结构定义

typedef struct _AVL_TREE_HEADER

{

TREE_NODE *pTreeHeader

#ifdef ORDER_LIST_WANTED

TREE_NODE *pListHeader

TREE_NODE *pListTail

#endif

unsigned int count/*AVL树里的节点总数*/

int (*keyCompare)(TREE_NODE * , TREE_NODE *)

int (*free)(TREE_NODE *)

#if OS==3||OS==4 /*#if OS == VXWORKS || OS == VXWORKS_M*/

SEM_ID sem

#endif

} tAVLTree

1.2、树节点的结构定义

typedef struct _AVL_TREE_NODE

{

#ifdef ORDER_LIST_WANTED

struct _AVL_TREE_NODE *prev

struct _AVL_TREE_NODE *next

#endif

struct _AVL_TREE_NODE *tree_root

struct _AVL_TREE_NODE *left_child

struct _AVL_TREE_NODE *right_child

int bf /*平衡因子；当平衡因子的绝对值大于或等于2的时候就表示树不平衡(balance_factor)*/

}TREE_NODE

2、通用函数接口定义

2.1、avlTreeCreate

函数原型：tAVLTree *avlTreeCreate(int *keyCompareFunc,int *freeFunc)

参数描述：keyCompareFunc - 节点大小比较函数的指针，此函数需要用户自己提供，

比较函数的返回值应该是-1、0、1，(*keyCompareFunc)函数有两个参数，

分别是两个树节点，如果第二个参数所指向的树节点的值比第一个的小，

那么比较函数就应该返回-1，如果相等就是返回0，否则就是1。具体的比

较规则由用户根据所存储的数据里面的关键字来指定（当然，关键字有可

能有多个）。

freeFunc - (*freeFunc)只有一个参数，就是需要释放内存的节点的指

针，填写这个注册函数的目的是为了实现avlTreeDestroy和avlTreeFlush

这两个函数。

返回值 ：成功 - 返回指向一个树的指针

失败 - NULL

函数描述：创建一棵空的平衡二叉树，如果是vxworks操作系统的话还创建一个跟树

相关的一个二进制信号量。初始化所有指针为空指针。

2.2、avlTreeDestroy

函数原型：int avlTreeDestroy(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 1

失败 - 0

函数描述：摧毁一颗平衡二叉树，释放所有树节点的内存，并且释放信号量（如果是

vxworks操作系统的话），释放pTree所指向的二叉树所占用的内存。

2.3、avlTreeFlush

函数原型：int avlTreeFlush(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 1

失败 - 0

函数描述：清空一颗平衡二叉树，释放所有树节点的内存，但是并不删除平衡二叉树

2.4、avlTreeAdd

函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pInsertNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pInsertNode - 待插入的节点的指针

返回值 ：成功 - 1

失败 - 0

函数描述：往平衡二叉树中添加一个成员节点

2.5、avlTreeDel

函数原型：int avlTreeAdd(tAVLTree *pTree , TREE_NODE *pDelNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pDelNode - 待插入的节点的指针

返回值 ：成功 - 1

失败 - 0

函数描述：从平衡二叉树中删除一个树节点

2.6、avlTreeFind

函数原型：TREE_NODE *avlTreeFind(tAVLTree *pTree,TREE_NODE *pKeyNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pKeyNode - 待查找的节点的关键字

返回值 ：成功 - 查找到的节点指针

失败 - NULL

函数描述：查找一个节点

2.7、avlTreeCount

函数原型：int avlTreeCount(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里的节点总数

失败 - 0

函数描述：获取当前树里面的所有成员节点总数

2.8、avlTreeFirst

函数原型：TREE_NODE *avlTreeFirst(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里面的最小的成员节点的指针

失败 - NULL，只有树是空的时候才会返回NULL

函数描述：获取当前平衡二叉树里面第一个成员节点，即最小的成员节点

2.9、avlTreeLast

函数原型：TREE_NODE *avlTreeLast(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 当前平衡二叉树里面的最大的成员节点的指针

失败 - NULL，只有树是空的时候才会返回NULL

函数描述：获取当前平衡二叉树里面最后一个成员节点，即最大的成员节点

2.10、avlTreeNext

函数原型：TREE_NODE *avlTreeNext(TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 下一个成员节点的指针

失败 - NULL

函数描述：获取当前节点的下一个节点

2.11、avlTreePrev

函数原型：TREE_NODE *avlTreePrev(TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：成功 - 前一个成员节点的指针

失败 - NULL

函数描述：获取当前节点的前一个节点

2.12、AVL_TREE_LOCK

函数原型：void AVL_TREE_LOCK(tAVLTree *pTree,int timeout)

参数描述：pTree - 指向一棵平衡二叉树的指针

timeout - 等待时间

返回值 ：N/A

函数描述：此函数只有是vxworks系统才有效，目的是对树进行互斥操作，防止

多任务同时操作链表。

2.13、AVL_TREE_UNLOCK

函数原型：void AVL_TREE_UNLOCK(tAVLTree *pTree)

参数描述：pTree - 指向一棵平衡二叉树的指针

返回值 ：N/A

函数描述：此函数只有是vxworks系统才有效，目的是对树进行解除互斥操作

2.13、AVL_TREENODE_FREE

函数原型：void AVL_TREENODE_FREE(tAVLTree *pTree,TREE_NODE *pNode)

参数描述：pTree - 指向一棵平衡二叉树的指针

pNode - 需要释放的节点的指针

返回值 ：N/A

函数描述：此函数释放内存的过程采用的是注册的释放函数，释放不仅仅

只有free函数，对于一些复杂的结构设计，可能需要释放多个

不同的内存。

3、应用举例

> typedef struct _testStruct{

> TREE_NODE node /*树节点的结构一定要放在用户自定义结构的最前面，注意!*/

> int keyA /*关键字A*/

> int keyB /*关键字B*/

> int keyC /*关键字C，比方说此结构有3个关键字*/

> int userData[200]/*用户的实际数据区*/

> }tTestStruct

>

> int keyCompareFunc(TREE_NODE *p , TREE_NODE *p1)

> {

> tTestStruct *T1=NULL,*T2=NULL

>

> T1=(tTestStruct *)p

> T2=(tTestStruct *)p1

>

> if(T1->keyA <T2->keyA) return 1

> if(T1->keyA >T2->keyA) return -1

>

> if(T1->keyB <T2->keyB) return 1

> if(T1->keyB >T2->keyB) return -1

>

> if(T1->keyC <T2->keyC) return 1

> if(T1->keyC >T2->keyC) return -1

>

> return 0

> }

>

> int freeFunc(TREE_NODE *pNode)

> {

> free((void *)pNode)

> return 1

> }

>

> tAVLTree *pTree = NULL

> int main()

> {

> tTestStruct *pTest = NULL

> tTestStruct key

> int count = 0

> pTree = (tAVLTree *)avlTreeCreate

> (

> (void*)keyCompareFunc ,

> (void *)freeFunc

> )

> if(!pTree)

> {

> printf("\r\n 创建平衡二叉树失败")

> return 0

> }

>

> /*添加一个节点*/

> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))

> if(!pTest)

> {

> printf("\r\n 创建树节点失败")

> return 0

> }

>

> pTest->keyA = 1

> pTest->keyB = 2

> pTest->keyC = 3

> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))

> {

> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")

> return 1

> }

>

> /*再添加一个节点*/

> pTest = (tTestStruct *)malloc(sizeof(tTestStruct))

> if(!pTest)

> {

> printf("\r\n 创建树节点又失败")

> return 0

> }

>

> pTest->keyA = 1

> pTest->keyB = 1

> pTest->keyC = 3 /*第二次添加的节点的关键字比较大家可以算一算*/

> if(!avlTreeAdd(pTree , (TREE_NODE *)pTest))

> {

> printf("\r\n 已经存在相同节点，添加失败!关键字完全匹配就表示节点完全相同")

> return 1

> }

>

> /*遍历有序平衡二叉树 -- 从小到大*/

> pTest = (tTestStruct *)avlTreeFirst(pTree)

> while(pTest)

> {

> /**************************

> *这里你想干嘛干嘛

> *处理pTest->userData?

> ***************************/

> pTest = (tTestStruct *)avlTreeNext(pTree)

> }

>

> /*遍历有序平衡二叉树 -- 从大到小*/

> pTest = (tTestStruct *)avlTreeLast(pTree)

> while(pTest)

> {

> /**************************

> *这里你想干嘛干嘛

> *处理pTest->userData?

> ***************************/

> pTest = (tTestStruct *)avlTreePrev(pTree)

> }

>

> /*查找某个节点*/

> key->keyA = 1

> key->keyB = 1

> key->keyC = 3

> pTest = (tTestStruct *)avlTreeFind(pTree , (TREE_NODE *)&key)

> if(pTest)

> printf("\r\n 这里应该可以查找到一条记录，就是第二个插入的节点")

>

> /*删除一个节点，我们就将上面查找到的节点删除*/

> if(!avlTreeCount(pTree , (TREE_NODE *)pTest))

> {

> printf("\r\n 如果删除失败，只能说明一个问题，树里面不存在这个节点")

> return 0

> }

>

> /*获取树的总的节点数*/

> count = avlTreeCount(pTree)

> printf("\r\n 我想现在count应该等于1，刚才我们删掉了一个节点")

>

> /*清空整棵树*/

> avlTreeFlush(pTree)

>

> /*删除整棵树，其实现在只有一颗裸树了，因为树节点都被flush掉了*/

> avlTreeDestroy(pTree)

> pTree = NULL

>

> return 1

> }

欢迎分享，转载请注明来源：夏雨云

原文地址:https://www.xiayuyun.com/zonghe/118801.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
小夏小夏管理员组
00
上一篇 2023-03-13
下一篇2023-03-13

发表评论

登录后才能评论

评论列表（0条）

    保存