0.等候行列
在Linux内核中等候行列有许多用处，可用于中止处理、进程同步及守时。咱们在这儿只说，进程常常有必要等候某些事情的产生。等候行列完结了在事情上的条件等候: 期望等候特定事情的进程把自己放进适宜的等候行列，并抛弃操控全。因而，等候行列表明一组睡觉的进程，当某一条件为真时，由内核唤醒它们。
等候行列由循环链表完结，由等候行列头（wait_queue_head_t）和等候行列项（wait_queue）组成，其元素（等候行列项）包括指向进程描述符的指针。每个等候行列都有一个等候行列头(wait queue head),等候行列头是一个类型为wait_queue_head_t的数据结构
界说等候行列头（相关内容能够在linux/include/wait.h中找到）
等候行列头结构体的界说：
struct wait_queue_head {
spinlock_t lock; //自旋锁变量，用于在对等候行列头
struct list_head task_list; // 指向等候行列的list_head
};
typedef struct __wait_queue_head wait_queue_head_t;
运用等候行列时首要需求界说一个wait_queue_head，这能够经过DECLARE_WAIT_QUEUE_HEAD宏来完结，这是静态界说的办法。该宏会界说一个wait_queue_head，而且初始化结构中的锁以及等候行列。
Linux中等候行列的完结思维如下图所示，当一个使命需求在某个wait_queue_head上睡觉时，将自己的进程操控块信息封装到wait_queue中，然后挂载到wait_queue的链表中，履行调度睡觉。当某些事情产生后，另一个使命（进程）会唤醒wait_queue_head上的某个或许一切使命，唤醒作业也便是将等候行列中的使命设置为可调度的状况，而且从行列中删去。
（2）等候行列中寄存的是在履行设备操作时不能取得资源而挂起的进程
界说等候对列：
struct wait_queue {
unsigned int flags; //prepare_to_wait()里有对flags的操作，检查以得出其意义
#define WQ_FLAG_EXCLUSIVE 0x01 //一个常数,在prepare_to_wait()用于修正flags的值
void * private //一般指向当时使命操控块
wait_queue_func_t func; //唤醒堵塞使命的函数 ，决议了唤醒的方法
struct list_head task_list; // 堵塞使命链表
};
typedef struct __wait_queue wait_queue_t;
poll完结剖析
1.select/poll缺陷
select/poll的缺陷在于：
1.每次调用时要重复地从用户态读入参数。
2.每次调用时要重复地扫描文件描述符。
3.每次在调用开始时，要把当时进程放入各个文件描述符的等候行列。在调用完毕后，又把进程从各个等候行列中删去。
2. 内核完结
2.1 首要数据结构：
(1) struct poll_table_entry {
struct file filp;
wait_queue_t wait;//内部有一个指针指向一个进程
wait_queue_head_t wait_address;//等候行列头部（等候行列有多个wait_queue_t组成，经过双链表衔接）
};
(2) struct poll_table_page {
struct poll_table_page next;
struct poll_table_entry entry;
struct poll_table_entry entries[0];
};
(3) struct poll_wqueues {
poll_table pt;//一个函数指针，一般指向__pollwait或null
struct poll_table_page * table;
int error;
};
(4) struct poll_list {
struct poll_list *next;//按内存页衔接，因为kmalloc有请求数据约束
int len;//用户空间传入fd的数量
struct pollfd entries[0];//寄存用户空间存入的数据
};
typedef void (*poll_queue_proc)(struct file *, wait_queue_head_t *, struct poll_table_struct *);
typedef struct poll_table struct {
poll_queue_proc qproc;
} poll_table;
2.2 poll体系调用函数联系总图
int poll(struct pollfd *fds, nfds_t nfds, int timeout);
3. 内核2.6.9 poll完结代码剖析
[fs/select.c –>sys_poll]
asmlinkage long sys_poll(struct pollfd __user * ufds, unsigned int nfds, long TImeout)
{
struct poll_wqueues table;
struct poll_list *head;
struct poll_list *walk;
……
poll_initwait(&table);
……
while(i!=0) {
struct poll_list *pp;
pp = kmalloc(sizeof(struct poll_list)+ sizeof(struct pollfd)
*(i>POLLFD_PER_PAGE?POLLFD_PER_PAGE:i), GFP_KERNEL));
if (head == NULL)
head = pp;
else
walk->next = pp;
walk = pp;
if (copy_from_user(pp->entries, ufds + nfds-i,
sizeof(struct pollfd)*pp->len)) {
err = -EFAULT;
goto out_fds;
}
i -= pp->len;
}
/*这一大堆代码便是树立一个链表，每个链表的节点是一个page巨细（一般是4k），这链表节点由一个指向struct poll_list的指针掌控每个poll_list的entrys成员指向一个struct pollfd。上面的循环便是把用户态的struct pollfd拷进这些entries里。一般用户程序的poll调用就监控几个fd，所以上面这个链表一般也就只需求一个节点，即操作体系的一页。可是，当用户传入的fd许多时，因为poll体系调用每次都要把一切struct pollfd拷进内核，所以参数传递和页分配此刻就成了poll体系调用的功能瓶颈。*/
fdcount = do_poll(nfds, head, &table, TImeout);
}
其间poll_initwait较为要害，从字面上看，应该是初始化变量table，留意此处table在整个履行poll的进程中是很要害的变量。而struct poll_table其实就只包括了一个函数指针。
现在咱们来看看poll_initwait到底在做些什么
void __pollwait(struct file *filp, wait_queue_head_t *wait_address, poll_table *p);
void poll_initwait(struct poll_wqueues *pwq)
{
&(pwq->pt)->qproc = __pollwait; /*设置回调函数*/
……
}
很明显，poll_initwait的首要动作便是把table变量的成员poll_table对应的回调函数置为__pollwait。这个__pollwait不仅是poll体系调用需求，select体系调用也相同是用这个__pollwait，说白了，这是个操作体系的异步操作的“御用”回调函数。当然了，epoll没有用这个，它其他新增了一个回调函数，以到达其高效工作的意图，这是后话，暂且不表。
最终一句do_poll，咱们跟进去：
staTIc int do_poll(unsigned int nfds, struct poll_list *list,struct poll_wqueues *wait,
long TImeout)
{
int count = 0;
poll_table* pt = &wait->pt;
for (;;) {
struct poll_list *walk;
set_current_state(TASK_INTERRUPTIBLE);
walk = list;
while(walk != NULL) {
do_pollfd( walk->len, walk->entries, &pt, &count);
walk = walk->next;
}
pt = NULL;
if (count || !timeout || signal_pending(current))
break;
count = wait->error;
if (count)
break;
timeout = schedule_timeout(timeout); /* 让current挂起，其他进程跑，timeout到了
今后再回来运转current*/
}
__set_current_state(TASK_RUNNING);
return count;
}
留意set_current_state和signal_pending，它们两句保证了当用户程序在调用poll后挂起时，发信号能够让程序敏捷推出poll调用，而一般的体系调用是不会被信号打断的。纵览do_poll函数，首要是在循环内等候，直到count大于0才跳出循环，而count首要是靠do_pollfd函数处理。留意标红的while循环，当用户传入的fd许多时（比方1000个），对do_pollfd就会调用许屡次，poll功率瓶颈的另一原因就在这儿。
do_pollfd便是针对每个传进来的fd，调用它们各自对应的poll函数，简化一下调用进程，如下：
[fs/select.c–>sys_poll()–>do_poll()]
static void do_pollfd(unsigned int num, struct pollfd * fdpage, poll_table ** pwait, int *count)
{
……
struct file* file = fget(fd);
file->f_op->poll（file, &(table->pt));
……
}
假如fd对应的是某个socket，do_pollfd调用的便是网络设备驱动完结的poll；假如fd对应的是某个ext3文件体系上的一个翻开文件，那do_pollfd调用的便是ext3文件体系驱动完结的poll。一句话，这个file->f_op->poll是设备驱动程序完结的，那设备驱动程序的poll完结一般又是什么姿态呢？其实，设备驱动程序的规范完结是：调用poll_wait，即以设备自己的等候行列为参数（一般设备都有自己的等候行列，否则一个不支持异步操作的设备会让人很抑郁）调用struct poll_table的回调函数。
作为驱动程序的代表，咱们看看socket在运用tcp时的代码：
[net/ipv4/tcp.c–>tcp_poll]
unsigned int tcp_poll(struct file *file, struct socket *sock, poll_table *wait)
{
……
poll_wait(file, sk->sk_sleep, wait);
tcp_poll的中心完结便是poll_wait，而poll_wait便是调用struct poll_table对应的回调函数，那poll体系调用对应的回调函数便是__poll_wait，所以这儿简直就能够把tcp_poll理解为一个句子：
__poll_wait(file, sk->sk_sleep, wait);
由此也能够看出，每个socket自己都带有一个等候行列sk_sleep，所以上面咱们所说的“设备的等候行列”,其实不止一个。
这时候咱们再看看__poll_wait的完结:
[fs/select.c–>__poll_wait()]
void __pollwait(struct file *filp, wait_queue_head_t *wait_address, poll_table *_p)
{
……
}
__poll_wait的效果便是创立了上图所示的数据结构（一次__poll_wait即一次设备poll调用只创立一个poll_table_entry），并经过struct poll_table_entry的wait成员，把current挂在了设备的等候行列上，此处的等候行列是wait_address，对应tcp_poll里的sk->sk_sleep。
现在咱们能够回忆一下poll体系调用的原理了：先注册回调函数__poll_wait，再初始化table变量（类型为struct poll_wqueues)，接着复制用户传入的struct pollfd（其实首要是fd）(瓶颈1)，然后轮番调用一切fd对应的poll（把current挂到各个fd对应的设备等候行列上）(瓶颈2)。在设备收到一条音讯（网络设备）或填写完文件数据（磁盘设备）后，会唤醒设备等候行列上的进程，这时current便被唤醒了。current醒来后脱离sys_poll的操作相对简略，这儿就不逐行剖析了。
