锁的实现.old

简单的说,互斥锁保护了一个临界区,在这个临界区中,一次最多只能进入一个线程。如果有多个进程在同一个临界区内活动,就有可能产生竞态条件(race condition)导致错误。

读写锁从广义的逻辑上讲,也可以认为是一种共享版的互斥锁。如果对一个临界区大部分是读操作而只有少量的写操作,读写锁在一定程度上能够降低线程互斥产生的代价。

条 件变量允许线程以一种无竞争的方式等待某个条件的发生。当该条件没有发生时,线程会一直处于休眠状态。当被其它线程通知条件已经发生时,线程才会被唤醒从 而继续向下执行。条件变量是比较底层的同步原语,直接使用的情况不多,往往用于实现高层之间的线程同步。使用条件变量的一个经典的例子就是线程池(Thread Pool)了。 当我们在谈论常见的锁名词时,最基础的即是信号量(Semaphore)与互斥锁(Mutex)。互斥锁的作用就是互斥,用来保护临界区(critical section)的。所谓临界区就是代码的一个区间,如果两个线程同时执行就有可能出问题,所以需要互斥锁来保护。信号量(Semaphore)是一种更高级的同步机制,Mutex 可以说是 Semaphore 在仅取值 0/1 时的特例。Semaphore 可以有更多的取值空间,可以为非负整数,用来实现更加复杂的同步,一个互斥量只能用于一个资源的互斥访问,它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是,也可以完成一个资源的互斥访问。 自旋锁是一种互斥锁的实现方式而已,相比一般的互斥锁会在等待期间放弃 cpu,自旋锁(SpinLock)则是不断循环并测试锁的状态,这样就一直占着 CPU。

保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区,那么在有一个线程进 入后其他所有试图访问此临界区的线程将被挂起,并一直持续到进入临界区的线程离开。临界区在被释放后,其他线程可以继续抢占,并以此达到用原子方式操作共 享资源的目的。

在使用临界区时,一般不允许其运行时间过长,只要进入临界区的线程还没有离开,其他所有试图进入此临界区的线程都会被挂起而进入到等待状态,并会在一定程 度上影响。程序的运行性能。尤其需要注意的是不要将等待用户输入或是其他一些外界干预的操作包含到临界区。如果进入了临界区却一直没有释放,同样也会引起 其他线程的长时间等待。虽然临界区同步速度很快,但却只能用来同步本进程内的线程,而不可用来同步多个进程中的线程。

自旋锁对信号量

需求 建议的加锁方法

低开销加锁 优先使用自旋锁 短期锁定 优先使用自旋锁 长期加锁 优先使用信号量 中断上下文中加锁 使用自旋锁 持有锁是需要睡眠、调度 使用信号量

Semaphore:信号量

信号量(Semaphore),有时被称为信号灯,是在多线程环境下使用的一种设施, 它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。

信号量可以分为几类: ² 二进制信号量(binary semaphore):只允许信号量取 0 或 1 值,其同时只能被一个线程获取。

² 整型信号量(integer semaphore):信号量取值是整数,它可以被多个线程同时获得,直到信号量的值变为 0。

² 记录型信号量(record semaphore):每个信号量 s 除一个整数值 value(计数)外,还有一个等待队列 List,其中是阻塞在该信号量的各个线程的标识。当信号量被释放一个,值被加一后,系统自动从等待队列中唤醒一个等待中的线程,让其获得信号量,同时信号量再减一。

信号量通过一个计数器控制对共享资源的访问,信号量的值是一个非负整数,所有通过它的线程都会将该整数减一。如果计数器大于 0,则访问被允许,计数器减 1;如果为 0,则访问被禁止,所有试图通过它的线程都将处于等待状态。

计数器计算的结果是允许访问共享资源的通行证。因此,为了访问共享资源,线程必须从信号量得到通行证, 如果该信号量的计数大于 0,则此线程获得一个通行证,这将导致信号量的计数递减,否则,此线程将阻塞直到获得一个通行证为止。当此线程不再需要访问共享资源时,它释放该通行证,这导致信号量的计数递增,如果另一个线程等待通行证,则那个线程将在那时获得通行证。

信 号灯与互斥锁和条件变量的主要不同在于”灯”的概念,灯亮则意味着资源可用,灯灭则意味着不可用。如果说后两中同步方式侧重于”等待”操作,即资源不可用 的话,信号灯机制则侧重于点灯,即告知资源可用;没有等待线程的解锁或激发条件都是没有意义的,而没有等待灯亮的线程的点灯操作则有效,且能保持灯亮状 态。当然,这样的操作原语也意味着更多的开销。

信号灯的应用除了灯亮/灯灭这种二元灯以外,也可以采用大于 1 的灯数,以表示资源数大于 1,这时可以称之为多元灯。

1. 创建和 注销

POSIX 信号灯标准定义了有名信号灯和无名信号灯两种,但 LinuxThreads 的实现仅有无名灯,同时有名灯除了总是可用于多进程之间以外,在使用上与无名灯并没有很大的区别,因此下面仅就无名灯进行讨论。

int sem_init(sem_t *sem, int pshared, unsigned int value) 这 是创建信号灯的 API,其中 value 为信号灯的初值,pshared 表示是否为多进程共享而不仅仅是用于一个进程。LinuxThreads 没有实现多 进程共享信号灯,因此所有非 0 值的 pshared 输入都将使 sem_init()返回-1,且置 errno 为 ENOSYS。初始化好的信号灯由 sem 变量 表征,用于以下点灯、灭灯操作。

int sem_destroy(sem_t * sem) 被注销的信号灯 sem 要求已没有线程在等待该信号灯,否则返回-1,且置 errno 为 EBUSY。除此之外,LinuxThreads 的信号灯 注销函数不做其他动作。

2. 点灯和灭灯

int sem_post(sem_t * sem)

点灯操作将信号灯值原子地加 1,表示增加一个可访问的资源。

int semwait(sem_t sem) int semtrywait(sem_t sem)

sem_wait()为等待灯亮操作,等待灯亮(信号灯值大于 0),然后将信号灯原子地减 1,并返回。sem_trywait()为 sem_wait()的非阻塞版,如果信号灯计数大于 0,则原子地减 1 并返回 0,否则立即返回-1,errno 置为 EAGAIN。

3. 获取灯值

int semgetvalue(sem_t sem, int _ sval)

读取 sem 中的灯计数,存于*sval 中,并返回 0。

4. 其他

sem_wait()被实现为取消点,而且在支持原子”比较且交换”指令的体系结构上,sem_post()是唯一能用于异步信号处理函数的 POSIX 异步信号 安全的 API。

Semaphore 可以被抽象为五个操作:

  • 创建 Create

  • 等待 Wait:

线程等待信号量,如果值大于 0,则获得,值减一;如果只等于 0,则一直线程进入睡眠状态,知道信号量值大于 0 或者超时。

-释放 Post

执行释放信号量,则值加一;如果此时有正在等待的线程,则唤醒该线程。

-试图等待 TryWait

如果调用 TryWait,线程并不真正的去获得信号量,还是检查信号量是否能够被获得,如果信号量值大于 0,则 TryWait 返回成功;否则返回失败。

-销毁 Destroy

信号量,是可以用来保护两个或多个关键代码段,这些关键代码段不能并发调用。在进入一个关键代码段之前,线程必须获取一个信号量。如果关键代码段中没有任何线程,那么线程会立即进入该框图中的那个部分。一旦该关键代码段完成了,那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。为了完成这个过程,需要创建一个信号量,然后将 Acquire Semaphore VI 以及 Release Semaphore VI 分别放置在每个关键代码段的首末端。确认这些信号量 VI 引用的是初始创建的信号量。

信号量对象对线程的同步方式与前面几种方法不同,信号允许多个线程同时使用共享资源,这与操作系统中的 PV 操作相同。它指出了同时访问共享资源的线程最大 数目。它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。在用 CreateSemaphore()创建信号量时即 要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数,每增加一个线程对共享资源的访问,当前可用资源计数就会 减 1,只要当前可用资源计数是大于 0 的,就可以发出信号量信号。但是当前可用计数减小到 0 时则说明当前占用资源的线程数已经达到了所允许的最大数目,不能 在允许其他线程的进入,此时的信号量信号将无法发出。线程在处理完共享资源后,应在离开的同时通过 ReleaseSemaphore()函数将当前可用资 源计数加 1。在任何时候当前可用资源计数决不可能大于最大资源计数。信号量是通过计数来对线程访问资源进行控制的,而实际上信号量确实也被称作 Dijkstra 计数器。

PV 操作及信号量的概念都是由荷兰科学家 E.W.Dijkstra 提出的。信号量 S 是一个整数,S 大于等于零时代表可供并发进程使用的资源实体数,但 S 小于零时则表示正在等待使用共享资源的进程数。

P 操作申请资源: (1)S 减 1; (2)若 S 减 1 后仍大于等于零,则进程继续执行; (3)若 S 减 1 后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转入进程调度。

V 操作 释放资源: (1)S 加 1; (2)若相加结果大于零,则进程继续执行; (3)若相加结果小于等于零,则从该信号的等待队列中唤醒一个等待进程,然后再返回原进程继续执行或转入进程调度。

信号量的使用特点使其更适用于对 Socket(套接字)程序中线程的同步。例如,网络上的 HTTP 服务器要对同一时间内访问同一页面的用户数加以限 制,这时可以为没一个用户对服务器的页面请求设置一个线程,而页面则是待保护的共享资源,通过使用信号量对线程的同步作用可以确保在任一时刻无论有多少用 户对某一页面进行访问,只有不大于设定的最大用户数目的线程能够进行访问,而其他的访问企图则被挂起,只有在有用户退出对此页面的访问后才有可能进入。

Mutex:互斥锁

互斥(Mutex)是一种用途非常广泛的内核对象。能够保证多个线程对同一共享资源的互斥访问。同临界区有些类似,只有拥有互斥对象的线程才具有访问资源 的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交 出,以便其他线程在获得后得以访问资源。与其他几种内核对象不同,互斥对象在操作系统中拥有特殊代码,并由操作系统来管理,操作系统甚至还允许其进行一些 其他内核对象所不能进行的非常规操作。互斥量跟临界区很相似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况 下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。互斥量比临界区 复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。

互斥量表现互斥现象的数据结构,也被当作二元信号灯。一个互斥基本上是一个多任务敏感的二元信号,它能用作同步多任务的行为,它常用作保护从中断来的临界段代码并且在共享同步使用的资源。 Mutex 本质上说就是一把锁,提供对资源的独占访问,所以 Mutex 主要的作用是用于互斥。Mutex 对象的值,只有 0 和 1 两个值。这两个值也分别代表了 Mutex 的两种状态。值为 0, 表示锁定状态,当前对象被锁定,用户进程/线程如果试图 Lock 临界资源,则进入排队等待;值为 1,表示空闲状态,当前对象为空闲,用户进程/线程可以 Lock 临界资源,之后 Mutex 值减 1 变为 0。

Mutex 可以被抽象为四个操作:

  • 创建 Create

  • 加锁 Lock

  • 解锁 Unlock

  • 销毁 Destroy

Mutex 被创建时可以有初始值,表示 Mutex 被创建后,是锁定状态还是空闲状态。在同一个线程中,为了防止死锁,系统不允许连续两次对 Mutex 加锁(系统一般会在第二次调用立刻返回)。也就是说,加锁和解锁这两个对应的操作,需要在同一个线程中完成。

不同操作系统中提供的 Mutex 函数: 动作\系统 Win32 Linyx Solaris

创建 CreateMutex pthread_mutex_init mutex_init

加锁 WaitForSingleObject pthread_mutex_lock mutex_lock

解锁 ReleaseMutex pthread_mutex_unlock mutex_unlock

销毁 CloseHandle pthread_mutex_destroy mutex_destroy

可递归锁与非递归锁

在所有的线程同步方法中,恐怕互斥锁(mutex)的出场率远远高于其它方法。互斥锁的理解和基本使用方法都很容易,这里不做更多介绍了。 Mutex 可以分为递归锁(recursive mutex)和非递归锁(non-recursive mutex)。可递归锁也可称为可重入锁(reentrant mutex),非递归锁又叫不可重入锁(non-reentrant mutex)。 二者唯一的区别是,同一个线程可以多次获取同一个递归锁,不会产生死锁。而如果一个线程多次获取同一个非递归锁,则会产生死锁。 Windows 下的 Mutex 和 Critical Section 是可递归的。Linux 下的 pthread_mutex_t 锁默认是非递归的。可以显示的设置 PTHREAD_MUTEX_RECURSIVE 属性,将 pthread_mutex_t 设为递归锁。

MutexLock mutex;
void foo()
{
mutex.lock();
// do something
mutex.unlock();
}
void bar()
{
mutex.lock();
// do something
foo();
mutex.unlock();
}

foo 函数和 bar 函数都获取了同一个锁,而 bar 函数又会调用 foo 函数。如果 MutexLock 锁是个非递归锁,则这个程序会立即死锁。因此在为一段程序加锁时要格外小心,否则很容易因为这种调用关系而造成死锁。 不要存在侥幸心理,觉得这种情况是很少出现的。当代码复杂到一定程度,被多个人维护,调用关系错综复杂时,程序中很容易犯这样的错误。庆幸的是,这种原因造成的死锁很容易被排除。 但 是这并不意味着应该用递归锁去代替非递归锁。递归锁用起来固然简单,但往往会隐藏某些代码问题。比如调用函数和被调用函数以为自己拿到了锁,都在修改同一 个对象,这时就很容易出现问题。因此在能使用非递归锁的情况下,应该尽量使用非递归锁,因为死锁相对来说,更容易通过调试发现。程序设计如果有问题,应该 暴露的越早越好。 为了避免上述情况造成的死锁,AUPE v2 一书在第 12 章提出了一种设计方法。即如果一个函数既有可能在已加锁的情况下使用,也有可能在未加锁的情况下使用,往往将这个函数拆成两个版本---加锁版本和不加锁版本(添加 nolock 后缀)。 例如将 foo()函数拆成两个函数。

// 不加锁版本
void foo_nolock()
{
// do something
}
// 加锁版本
void fun()
{
mutex.lock();
foo_nolock();
mutex.unlock();
}

为了接口的将来的扩展性,可以将 bar()函数用同样方法拆成 bar_withou_lock()函数和 bar()函数。 在 Douglas C. Schmidt(ACE 框架的主要编写者)的“Strategized Locking, Thread-safe Interface, and Scoped Locking”论文中,提出了一个基于 C++的线程安全接口模式(Thread-safe interface pattern),与 AUPE 的方法有异曲同工之妙。即在设计接口的时候,每个函数也被拆成两个函数,没有使用锁的函数是 private 或者 protected 类型,使用锁的的函数是 public 类型。接口如下:

class T
{
public:
foo(); //加锁
bar(); //加锁
private:
foo_nolock();
bar_nolock();
}

自旋锁

自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环查看是否该自旋锁的保持者已经释放了锁,"自旋"就是"在原地打转"。而信号量则引起调用者睡眠,它把进程从运行队列上拖出去,除非获得锁。这就是它们的"不类"。

互斥锁的起始原始开销要高于自旋锁,但是基本是一劳永逸,临界区持锁时间的大小并不会对互斥锁的开销造成影响,而自旋锁是死循环检测,加锁全程消耗 cpu,起始开销虽然低于互斥锁,但是随着持锁时间,加锁的开销是线性增长。

互斥锁用于临界区持锁时间比较长的操作,比如下面这些情况都可以考虑 1 临界区有 IO 操作 2 临界区代码复杂或者循环量大 3 临界区竞争非常激烈 4 单核处理器 至于自旋锁就主要用在临界区持锁时间非常短且 CPU 资源不紧张的情况下。

自旋锁是专为防止多处理器并发而引入的一种锁,它在内核中大量应用于中断处理等部分(对于单处理器来说,防止中断处理中的并发可简单采用关闭中断的方式,不需要自旋锁)。 自旋锁最多只能被一个内核任务持有,如果一个内核任务试图请求一个已被争用(已经被持有)的自旋锁,那么这个任务就会一直进行忙循环——旋转——等待锁重 新可用。要是锁未被争用,请求它的内核任务便能立刻得到它并且继续进行。自旋锁可以在任何时刻防止多于一个的内核任务同时进入临界区,因此这种锁可有效地 避免多处理器上并发运行的内核任务竞争共享资源。 事实上,自旋锁的初衷就是:在短期间内进行轻量级的锁定。一个被争用的自旋锁使得请求它的线程在等待锁重新可用的期间进行自旋(特别浪费处理器时间),所以自旋锁不应该被持有时间过长。如果需要长时间锁定的话, 最好使用信号量。 自旋锁的基本形式如下: spin_lock(&mr_lock); //临界区 spin_unlock(&mr_lock);

因为自旋锁在同一时刻只能被最多一个内核任务持有,所以一个时刻只有一个线程允许存在于临界区中。这点很好地满足了对称多处理机器需要的锁定服务。在单处理器上,自旋锁仅仅当作一个设置内核抢占的开关。如果内核抢占也不存在,那么自旋锁会在编译时被完全剔除出内核。 简单的说,自旋锁在内核中主要用来防止多处理器中并发访问临界区,防止内核抢占造成的竞争。另外自旋锁不允许任务睡眠(持有自旋锁的任务睡眠会造成自死锁——因为睡眠有可能造成持有锁的内核任务被重新调度,而再次申请自己已持有的锁),它能够在中断上下文中使用。 死锁:假设有一个或多个内核任务和一个或多个资源,每个内核都在等待其中的一个资源,但所有的资源都已经被占用了。这便会发生所有内核任务都在相互等待, 但它们永远不会释放已经占有的资源,于是任何内核任务都无法获得所需要的资源,无法继续运行,这便意味着死锁发生了。自死琐是说自己占有了某个资源,然后 自己又申请自己已占有的资源,显然不可能再获得该资源,因此就自缚手脚了。

自旋锁与互斥锁有点类似,只是自旋锁不会引起调用者睡眠,如果自旋锁已经被别的执行单元保持,调用者就一直循环在那里看是 否该自旋锁的保持者已经释放了锁,"自旋"一词就是因此而得名。其作用是为了解决某项资源的互斥使用。因为自旋锁不会引起调用者睡眠,所以自旋锁的效率远 高于互斥锁。虽然它的效率比互斥锁高,但是它也有些不足之处: 1、自旋锁一直占用 CPU,他在未获得锁的情况下,一直运行--自旋,所以占用着 CPU,如果不能在很短的时 间内获得锁,这无疑会使 CPU 效率降低。 2、在用自旋锁时有可能造成死锁,当递归调用时有可能造成死锁,调用有些其他函数也可能造成死锁,如 copy_to_user()、copy_from_user()、kmalloc()等。 因此我们要慎重使用自旋锁,自旋锁只有在内核可抢占式或 SMP 的情况下才真正需要,在单 CPU 且不可抢占式的内核下,自旋锁的操作为空操作。自旋锁适用于锁使用者保持锁时间比较短的情况下。 自旋锁的用法如下: 首先定义:spinlock_t x; 然后初始化:spin_lock_init(spinlock_t *x); //自旋锁在真正使用前必须先初始化 在 2.6.11 内核中将定义和初始化合并为一个宏:DEFINE_SPINLOCK(x)

获得自旋锁:spin_lock(x); //只有在获得锁的情况下才返回,否则一直“自旋” spin_trylock(x); //如立即获得锁则返回真,否则立即返回假 释放锁:spin_unlock(x);

结合以上有以下代码段:

spinlock_t lock; //定义一个自旋锁
spin_lock_init(&lock);
spin_lock(&lock);
....... //临界区
spin_unlock(&lock); //释放锁
还有一些其他用法:

spin_is_locked(x) // 该宏用于判断自旋锁 x 是否已经被某执行单元保持(即被锁),如果是, 返回真,否则返回假。 spin_unlock_wait(x) // 该宏用于等待自旋锁 x 变得没有被任何执行单元保持,如果没有任何执行单元保持该自旋锁,该宏立即返回,否 //将循环 在那里,直到该自旋锁被保持者释放。

spin_lock_irqsave(lock, flags) // 该宏获得自旋锁的同时把标志寄存器的值保存到变量 flags 中并失效本地中//断。相当于:spin_lock()+local_irq_save() spin_unlock_irqrestore(lock, flags) // 该宏释放自旋锁 lock 的同时,也恢复标志寄存器的值为变量 flags 保存的//值。它与 spin_lock_irqsave 配对使用。 //相当于:spin_unlock()+local_irq_restore()

spin_lock_irq(lock) //该宏类似于 spin_lock_irqsave,只是该宏不保存标志寄存器的值。相当 //于:spin_lock()+local_irq_disable() spin_unlock_irq(lock) //该宏释放自旋锁 lock 的同时,也使能本地中断。它与 spin_lock_irq 配对应用。相当于: spin_unlock()+local_irq+enable()

spin_lock_bh(lock) // 该宏在得到自旋锁的同时失效本地软中断。相当于: //spin_lock()+local_bh_disable() spin_unlock_bh(lock) //该宏释放自旋锁 lock 的同时,也使能本地的软中断。它与 spin_lock_bh 配对//使用。相当于:spin_unlock()+local_bh_enable()

spin_trylock_irqsave(lock, flags) //该宏如果获得自旋锁 lock,它也将保存标志寄存器的值到变量 flags 中,并且失//效本地中断,如果没有获得锁,它什么也不做。因此如果能够立即 获得锁,它等//同于 spin_lock_irqsave,如果不能获得锁,它等同于 spin_trylock。如果该宏//获得自旋锁 lock,那需要 使用 spin_unlock_irqrestore 来释放。

spin_trylock_irq(lock) //该宏类似于 spin_trylock_irqsave,只是该宏不保存标志寄存器。如果该宏获得自旋锁 lock,需要使用 spin_unlock_irq 来释放。 spin_trylock_bh(lock) // 该宏如果获得了自旋锁,它也将失效本地软中断。如果得不到锁,它什么//也不做。因此,如果得到了锁,它等同于 spin_lock_bh,如果得 不到锁,它等同//于 spin_trylock。如果该宏得到了自旋锁,需要使用 spin_unlock_bh 来释放。 spin_can_lock(lock) // 该宏用于判断自旋锁 lock 是否能够被锁,它实际是 spin_is_locked 取反。//如果 lock 没有被锁,它返回真,否则,返回 假。该宏在 2.6.11 中第一次被定义,在//先前的内核中并没有该宏。