十字转门

Turnstile是一种数据抽象，封装休眠队列和优先级继承互斥锁和读/写锁相关的信息。Turnstiles在Solaris7大幅改变，但基本前提仍然是相同的。首先，我们要看着2.5.1/2.6机制，然后看看在Solaris7发生什么改变。

图1.tstile_mod的结构

tstile_mod的结构是这样展开的。它保持turnstiles的链接，以及实施所需的各个领域，如pool，活跃的数字行在tsm_chunk阵列的活跃入turnstiles，链接到pool中的turnstiles，一个数组的指针到pool中的turnstiles块(tsm_chunk[] -这些都是活跃的pool中的turnstiles)。turnstiles本身维护名单上的其他pool中的turnstiles，前向链路的结构与优先级继承信息(pirec)，数组有两个休眠队列，读/写锁，读操作和写操作都保存在单独的休眠队列，而只有其中之一是用于互斥锁。正如上个月我们所看到的，休眠队列点上的队列(sq_first)内核线程。其他环节结合在一起，包括内核线程链接turnstiles(KTHREAD阻塞时，对一个同步对象设置)，如果一个点从KTHREAD结构pirec的内核线程的优先级改变，由于优先级反转。由于继承是接收者(高优先级)，benef领域pirec点回的内核线程更好的优先级。

在开机时，当一个线程需要一个互斥或读/写锁阻止从pool中分配一个turnstile，内核创建一个pool中的turnstiles块。该pool是在图1关闭tsp_list挂入turnstiles列表。turnstiles返回到可用pool时，线程被唤醒。代码试图保持pool中的turnstiles来匹配在系统上寻找在pool中的turnstiles每一次的内部thread_create()函数被调用来创建一个新的内核线程的内核线程数。如果内核线程数大于turnstiles在pool中创建的内核线程的数量，代码将动态分配的pool中的turnstiles。

当一个执行内核线程都需要一个锁，它可以调用mutex_enter()或mutex_tryenter()，它试图获取互斥锁的地址通过两种功能。更频繁地调用mutex_enter(); mutex_tryenter()将立即返回，如果锁不能被获取，如果锁被保有，而mutex_enter()将导致典型的旋转或阻止行为。mutex_tryenter()例程存在的情况下，如果不能立即提供所需的互斥，调用代码不起旋转或阻塞。这样一个使用的mutex_tryenter()"功能运行"的旗帜，其中一个内核函数功能启动时，抓起一个互斥。另一个内核线程使得相同的函数调用，它使一个mutex_tryenter()进入呼叫，如果mutex_tryenter返回一个错误(持有锁)，我们知道另一个线程运行函数。让我们来看看一个mutex_enter()调用的流动，看到在turnstiles和优先级继承被终结了。

mutex_enter()函数检查锁定类型(自适应或自旋)锁创建并初始化时建立的。如果锁自锁旋转，它正被保有，代码进入一个的自旋循环，通过循环试图获取锁与每个通路。如果锁是自适应的，目前被保有，代码将检查持有锁的线程的状态。如果持有人运行，旋进入循环，如果没有，使的mutex_enter()调用的内核线程最初请求锁设置为阻止(休眠)。注意，输入的自适应锁的代码段是在处理器的系统信息结构mutex_adaptive_lock_enter场递增。自适应锁进入的数量反映在mpstat的的SMTX列(1M)。

当一个锁被锁住，而锁住者没有运行的时候，这时为了能够进行休眠应该使用一个turnstile来设置应答线程。Turnstile是从turnstile池中分配的，并且相关结构域会被初始化。turnstile的结构和可适应互斥结构都包含被内核用作整体实现的一部分的域。一个可适应互斥结构包含一个储存着turnstile所等待线程的ID的域。如果等待域是空(这意味着，没有线程在等待)，一个turnstile是从池中分配的，那互斥等待域设置为刚刚分配的turnstile的ID，并且turnstile的ts_sobj_priv_data(turnstile同步对象私有数据)域设置为指向可适应互斥结构的地址。否则，如果一个线程已经在为互斥等待，那已经为互斥而分配的turnstile的地址被检索。

在这两种情况下，我们现在有一个同步对象(可适应互斥)的turnstile，并且我们能通过关联turnstile继续改变线程状态以休眠和设置休眠序列。内核的t_block()函数就是以这个目的被调用的，同时CL_SLEEP宏也为此调用。从之前的列中应该记住，调度特定类的函数是通过宏调用的，这些宏用于实现正确的基于调度内核线程类的功能。在TS和IA类线程情况下，ts_sleep()函数被调用，并且线程的优先级设置为SYS优先级。这是一个优先级的提升--当他被唤醒是，他会得到优先于TS和IA而运行的优先级--同时线程的状态被设置为TS_SLEEP。内核线程的t_wchan域(等待渠道)设置为同步对象操作向量的地址--一个有可适应互斥对象特定功能的数组。回想从上个月一个到相似函数设定的连接为休眠序列完成了。在这种turnstile的情况下，不同的同步对象的turnstile被用以定义一个操作的向量，这向量是一种简单的包含对象种类，拥有者的地址，和未休眠的优先级修改独特对象函数的数据结构。一个同步对象的操作结构为了所有同步对象而被声明，这存在于Solaris内核中。

以下为结构的定义:

/usr/include/sys/sobject.h:

/*

* The following datastructure is used to map

* synchronization object typenumbers to the

* synchronization object'ssleep queue number

* or the synch. object'sowner function.

*/

typedef struct _sobj_ops {

char *sobj_class;

syncobj_t sobj_type;

qobj_t sobj_qnum;

kthread_t * (*sobj_owner)();

void (*sobj_unsleep)(kthread_t *);

void (*sobj_change_pri)(kthread_t *, pri_t, pri_t *);

} sobj_ops_t;

最终，线程的t_ts域设置为turnstile的地址，而线程被插入到turnstile的休眠序列中。上个月我们讨论的休眠序列函数被间接地通过在turnstile头文件(线程在休眠序列中的插入通过称作内核的sleep_insert()函数的TSTILE_INSERT宏完成)中定义的宏而调用。当全部完成后，内核线程驻留在休眠序列中和turnstile连接(如图1所示)，同时内核线程的t_ts鱼被设置，以参考turnstile的地址。一个内核线程只能被一个同步对象在任意时间点堵塞，决不能超过一个。所以，t_ts将会同时变为空指针或者一个指向单个turnstile的指针。

我们还没有全部完成--现在是时候进行优先级继承检查来决定是否锁住锁的线程在一个比线程回应锁(被放置在turnstile休眠序列中)更低(更差)的优先级中。内核的pi_willto()函数被调用，互斥拥有者的优先级和线程等待相检查。如果拥有者的优先级比等待线程优先级更高，那么我们不存在优先级调换的情况，而且代码被释放。如果等待者优先级比拥有者高，我们需要优先级调换，互斥拥有者的优先级被提高以超过等待者。内核线程的t_epri域被用来继承优先级，同时当轮到按序安排线程派遣序列(在唤醒后)时，一个在t_epri中的非空值会导致被占用线程优先级的继承。

此时，turnstile已被设置，同时等待线程也已存在于turnstile的休眠队列中、优先级反转的问题的潜力也已被检查，以及如果需要的话，优先级继承已被执行。内核现在进入调度动开关switch()函数，从调度队列中找到最好的可运行的线程并运行它，进而使得执行内核线程放弃处理器。

读/写锁本质上与此是相同的。当内核线程试图获得一个读/写锁，而这个锁目前正在由另一个线程持有，此时turnstile功能被调用来分配turnstile(或者如果这个锁已经被一个turnstile所拥有，则设置turnstile指针，这意味着至少有另外一个线程在等待)。然后内核线程被放在与turnstile关联的休眠队列中。正如我们前面提到的，一个关联读/写锁的turnstile会拥有两个独立的休眠队列链表，一个用来读一个用来写。

唤醒机制其实很简单。在内核中使用锁的约定中要求调用同步对象输入例程(例如mutex_enter()或rw_enter())，其次需要在适当的时间调用结束例程(例如mutex_exit()或rw_exit())，从而释放被持有的锁。对于自适应的互斥锁或读/写锁，释放功能需要检查同步对象中的等待域。如果有正在等待的内核线程，turnstile宏TSTILE_WAKEONE()会被引用，同时sleepq_wakeone()函数会被调用。Turnstile的休眠队列中最高优先级的线程将被调度类的特定唤醒程序唤醒，并根据其优先级放在适当的调度队列(记住，在这种情况下，如果该线程在被放入休眠队列时赋予了SYS优先级，则它会在任何TS和IA类线程之前被唤醒)。一旦执行，它会让抢占另一个被堵塞的同步对象。Turnstile现在可以返回到可用的turnstile池中了。

那么在Solaris7中有什么不同呢?

正如我们前面提到的，Solaris7中的turnstiles被重新改写:很多代码被删除，同时开发了一些新的、更高效的功能。Turnstiles被保留在一个全系统的哈希表turnstile_table[]中，这是一个turnstile_chain结构的数组。数组中的每一项都是turnstile_chain结构，同时也是一个turnstiles锁链表的开头。该数组利用同步对象(互斥锁或读/写锁)地址的散列函数来索引。Turnstile_table数组在引导时被初始化，如下面图2中所示。

图2.turnstile table的结构

链中的每个条目都具有其自己的锁，以允许链执行并发遍历。Turnstile本身具有不同的结构;对于每一个链，都有一个活动列表(ts_next)和一个空闲的列表(ts_free)，还有一个计算在同步对象(waiters)中等待的线程数、一个同步对象的(ts_sobj)指针、一个连接到内核线程的线程指针，这个内核线程的优先级是通过优先级继承得来的，以及多个休眠队列。在2.6的实现中，每个turnstile有两个休眠队列。注意，优先级继承的数据被集成到了turnstile中，所以不会再有pirec结构。

新开发的turnstile功能支持新的模型，并且集成了优先级继承功能。在之前的版本中，优先级继承代码是内核例程中的一组独立的函数(例如我们之前提到的pi_willto()函数)。一般事件的序列在所有的版本是一样的。

让我们继续看上一节中的例子，内核进程通过执行mutex_enter()或者rwlock_enter()调用来请求锁，而当前这个锁正被另一个线程控制。---看看在Solaris7系统下会发生什么。如上所述，在自适应互斥与控制者没有运行的情况下，调用方将会阻止(对于读/写锁，如果锁被线程拥有，调用方总是会阻止)。Solaris7结果中，在一个同步对象turnstile_table[]调用时，我们索引的数组通过散列的同步对象的地址，如果已经存在一个turnstile(即已经有等待者)，我们会得到正确的turnstile。否则，查找功能将简单的返回一个没有等待者的turnstile的地址。

现在已经完成了第一步。这意味着代码有了turnstile。接下来，内核线程需要被设置为休眠状态，并放在与turnstile休眠队列，若存在优先级反转条件，则需要测试和解决之。Solaris7的turnstile_block()函数处理安置到休眠队列中的请求锁的线程，任何线程优先级反转测试可能已经等待相同的锁，就像2.6例子中那样，放弃处理器进入调度的swtch()函数。

在turnstile_block()，指针设置根据从turnstile_lookup()中的返回。如果turnstile指针为null，我们连接起来在哪个内核线程的t_ts的的指针指向turnstile。(当初始化内核线程是在Solaris7，创建一个turnstile和链接到其t_ts指针)。如果从查询返回的指针不为空，那么至少一个KTHREAD等待锁作为一个结果，设置了适当的指针链接代码(见图2)。然后把线程进入休眠状态，如同前面的例子中，通过调度类特定的休眠习惯(ts_sleep())。插入同步对象使用sleepq_insert()接口描述上个月休眠队列。在检票口的等待者空间递增，代码执行优先级反转检查(现在的turnstile_block()例程的一部分)。同样的规则适用于:如果锁保持器的优先级是较低的(差)比请求的线程的优先级，所以请求线程的优先级被任性的支架;持有人的t_epri字段被设置到新的优先级，并继承者指针在检票口与内核线程。此时，调度员通过调用swtch()输入，猛拉关闭另一个内核线程调度队列。

唤醒机制启动如前面所述，如果有上的锁的线程阻塞，锁定出口例程的调用将导致一个turnstile_wakeup()。在Solaris 7的代码上的锁阻塞的所有线程被唤醒，而不是只是一个潜在的几个线程醒来2.5.1/2.6的情况下。熟悉周围操作系统设计的问题的读者可能已经看到惊群问题，这是一个丰富多彩的术语，用来描述一种情况，即多个线程正在等待相同的资源被唤醒，他们都取得了可运行，多处理器系统上，它们都使资源在同一时间被获取。

在Sun编码的Solaris 7中的一个足够通用的方式turnstile_wakeup()中，从而使一个单一的的线程唤醒可以无误地执行，而不是所有线程不可避免地一起醒来。不同的负载下的力竭性测试显示，在实践中，我们极少结束大量的线程阻塞链,因此几乎从不碰到惊群问题。"唤醒所有(wakeup-all)"的实施还解决了一些使唤醒一个场景变得棘手的位同步问题。

当内核线程需要阻塞一个请求锁时，互斥锁和RW锁会使用turnstile。休眠队列在处理其他资源等待时无法通过优先级继承处理优先级反转问题时的函数来解决，turnstiles的建立就是为了解决这个问题。