多线程编程(二):互斥锁与死锁问题

2017-05-30 18:00 阅读 3,398 次 评论 2 条

二元信号量提供了一种很方便的方法来确保对共享变量的互斥访问,即将每个共享变量与一个信号量s(初始为1)联系起来,然后P(s)和V(S)操作将相应的临界区包围起来。互斥锁是以提供互斥为目的的二元信号量,二者均属于挂起等待锁。

互斥锁(针对于线程)

互斥锁用于确保同一时间只有一个线程能访问被互斥锁保护的资源(互斥锁是针对于线程的)。锁定互斥量的线程与解锁互斥量的线程必须是同一个线程。

互斥锁的引入必须对互斥量mutex有一个新的认识,多个线程同时访问共享数据时可能会发生冲突,这与信号的可重入性是同样的问题。比如两个线程都要把某个全局变量增加1,这个操作在Linux下需要三条指令完成:

① 从内存读变量到寄存器。

② 寄存器的值+1。

③ 将寄存器的值写回内存。

我们在读取变量的值和把变量的新值保存回去两步操作之间插入一个printf调用,它会执行write系统调用进内核,为内核调用别的线程执行提供一个很好的时机(线程与进程间切换最好的时机:从内核态切换到用户态)。我们在一个循环中重复上述操作几千次,就会出现访问冲突的现象。

上述程序的运行结果足以说明一切,正确结果应该是10000,程序在用户态与内核态之间不断的切换,两个线程对其进行访问(因为i++是非原子的),则必然导致不可预料的结果。

对于多线程的访问,访问冲突的问题是非常普遍的,解决的方法就是加入互斥锁,获得锁的线程可以完成"读-修改-写"的操作,然后释放锁给其他的线程,没有获得锁的线程只能等待而不能访问共享数据,这样"读-修改-写"三步操作组成了一个原子操作

如果mutex_enter不能设置锁(因为另外一个进程已经设置了),则阻塞动作将取决于互斥对象中保存的专用类型信息。与互斥锁相关联的操作如下所示:

① pthread_mutex_init:初始化互斥锁。

参数mutex:互斥锁地址,类型为 pthread_mutex_t。

参数attr:设置互斥量的属性,通常可采用默认属性设置为NULL。

如果mutex变量是静态分配的(全局变量或static变量),也可以用宏定义PTHREAD_MUTEX_INITIALIZER来初始化,相当于pthread_mutex_init初始化并且attr设置为NULL。

返回值:成功返回0,失败返回错误码。

② pthread_mutex_destroy:销毁互斥锁。

直接加互斥锁的地址进行销毁。

③ pthread_mutex_lock:加锁,挂起等待锁(与二元信号量一样)。

参数mutex:互斥锁的地址

返回值:成功返回0,失败返回错误码。

一个线程可以调用此函数来对mutex加锁,如果另外一个线程想获得mutex,则只能挂机等待,直到当前线程释放锁为止。

挂起等待在严格意义上是:每个mutex有一个等待队列,一个线程在mutex上挂起等待,首先要将自己,本质上是将PCB加入等待队列中。

④ pthread_mutex_unlock:解锁。

参数mutex:互斥锁的地址。

返回值:成功返回0,失败返回错误码。

使用此函数释放mutex,当前线程将被唤醒,才能获得该mutex并继续执行。

⑤ pthread_mutex_trylock:加锁,尝试失败立即返回,不等待的非阻塞式。

如果一个线程既想得到锁,又不想挂起等待,可以调用trylock,如果mutex已经被另外一个线程获得,这个函数会失败返回EBUSY,而不会使线程挂起等待。

互斥锁测试

注意:pthread不是Linux下的默认的库,也就是在链接的时候,无法找到phread库中各个函数的入口地址,于是链接会失败。在gcc编译(或者Makefile)的时候,附加要加-lpthread参数。

当我们对临界区加锁之后,程序运行结果符合预期,多个线程访问临界资源不会再发生冲突。

死锁的原理

信号量的引入了潜在的令人厌恶的运行时错误,称之为死锁(deadlock),它指的是一组线程被阻塞了,等待一个永久也不会为真的条件,它是一组相互竞争系统资源或进行通信的进程间的"永久"阻塞。

下图展示了一对用两个信号量来实现互斥的线程的进度图:

线程1申请到s,线程2申请到t,由于继续执行时,线程1阻塞在t上,而线程2阻塞在s上,因而形成了死锁。

▶使用PV操作顺序不当,以至于两个信号量的禁止区域重叠。如果某个执行轨迹线恰巧到达死锁区域d,则不可能继续发展。也验证了死锁是因为每个线程都在等待其他线程执行一个根本不可能发生的V操作。

▶重叠的禁止区域引入了一组称为死锁区域(deadlock region)的状态。轨迹线一旦进入死锁区域,那么死锁则必然发生。

互斥锁加锁顺序规则:如果对于程序中每队互斥锁(s,t),给出所有的锁分配一个铨叙,每个线程按照这个顺序来申请锁,并且按照逆序来释放,那么这个程序就是无死锁的。

死锁的条件

死锁的四个必要条件:

1)互斥。一次只有一个进程可以使用一个资源,其他进程不能访问已分配给其他进程的资源。

2)占有且等待。当一个进程等待其他进程时,继续占有已经分配的资源。

3)不可抢占。不能强行抢占进程已占有的资源。

4)循环等待。存在一个封闭的进程链,使得每个进程至少占有此链中下一个进程所需要的一个资源,如下图所示:

对上面四个条件可以总结为一下:

死锁预防

1)破坏互斥条件:一般来说,这个条件是不可能禁止的,如果需要对资源进行互斥访问,那么操作系统必须支持互斥。

2)资源一次性分配:可以要求进程一次性请求所有需要的资源,并且阻塞这个进程直到所有请求同时满足。但是存在三个问题:

①  一个进程可能被阻塞很长时间以等待所有资源,但此进程可能只需要一部分资源就可以运行。

② 分配给一个进程的资源可能有很长一段时间没有被使用,在此期间,也不会被其他进程使用。

③ 一个进程可能事先不知道他说需要的全部资源。

3)破坏不可抢占条件:但是这种只能是资源状态可以很容易保存和恢复的前提下才是实用的。

4)资源的有序分配:对资源按照序号进行申请锁,确保锁的分配顺序可以预防死锁。但是它可能是低效的,它会进程执行速度变慢,并且可能在没有必要的情况下拒绝资源访问。

死锁避免

解决死锁问题的另一个方法就是死锁避免(deadlock avoidance),它允许三个必要条件,因此死锁避免比死锁预防允许更多的并发。在死锁避免中,是否允许当前的资源分配请求是通过判断该请求是否可能导致死锁来决定的。

避免死锁的两个方法:

1)如果一个进程的请求会导致死锁,则不启动此进程。

2)如果一个进程增加的资源请求会导致死锁,则不允许此分配。

银行家算法:资源分配拒绝策略,又称为银行家算法,首次提出了安全状态,即至少有一个资源分配序列不会导致死锁(即所有进程都能运行直到结束)。

对于银行家算法在这里我不再阐述,在之前操作系统课设里面已经对银行家算法进行编写,这里我贴上链接C语言实现银行家算法,不足之处就是当时对链表不熟悉,采用的是数组静态开辟的空间。

讲到这里死锁问题也就阐述完结,不知道大家是否对死锁有了新的认识,感兴趣可以编写一下银行家算法,当然还有应该重要的哲学家就餐问题,这里也就不再阐述了。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:多线程编程(二):互斥锁与死锁问题 | 术与道的分享
分类:操作系统 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情

  1. 张国荣
    张国荣 【农民】 @回复

    二元信号量貌似没有同步机制吧