跳至主要内容

【转】Select函数实现原理分析

select需要驱动程序的支持，驱动程序实现fops内的poll函数。select通过每个设备文件对应的poll函数提供的信息判断当前是否有资源可用(如可读或写)，如果有的话则返回可用资源的文件描述符个数，没有的话则睡眠，等待有资源变为可用时再被唤醒继续执行。

 

下面我们分两个过程来分析select：

 

1. select的睡眠过程

 

支持阻塞操作的设备驱动通常会实现一组自身的等待队列如读/写等待队列用于支持上层(用户层)所需的BLOCK或NONBLOCK操作。当应用程序通过设备驱动访问该设备时(默认为BLOCK操作)，若该设备当前没有数据可读或写，则将该用户进程插入到该设备驱动对应的读/写等待队列让其睡眠一段时间，等到有数据可读/写时再将该进程唤醒。

 

select就是巧妙的利用等待队列机制让用户进程适当在没有资源可读/写时睡眠，有资源可读/写时唤醒。下面我们看看select睡眠的详细过程。

 

select会循环遍历它所监测的fd_set内的所有文件描述符对应的驱动程序的poll函数。驱动程序提供的poll函数首先会将调用select的用户进程插入到该设备驱动对应资源的等待队列(如读/写等待队列)，然后返回一个bitmask告诉select当前资源哪些可用。当select循环遍历完所有fd_set内指定的文件描述符对应的poll函数后，如果没有一个资源可用(即没有一个文件可供操作)，则select让该进程睡眠，一直等到有资源可用为止，进程被唤醒(或者timeout)继续往下执行。

 

下面分析一下代码是如何实现的。

select的调用path如下：sys_select -> core_sys_select -> do_select

其中最重要的函数是do_select, 最主要的工作是在这里, 前面两个函数主要做一些准备工作。do_select定义如下：

int do_select(int n, fd_set_bits *fds, s64 *timeout)

{

         struct poll_wqueues table;

         poll_table *wait;

         int retval, i;

 

         rcu_read_lock();

         retval = max_select_fd(n, fds);

         rcu_read_unlock();

 

         if (retval < 0)

                   return retval;

         n = retval;

 

         poll_initwait(&table);

         wait = &table.pt;

         if (!*timeout)

                   wait = NULL;

         retval = 0;        //retval用于保存已经准备好的描述符数，初始为0

         for (;;) {

                   unsigned long *rinp, *routp, *rexp, *inp, *outp, *exp;

                   long __timeout;

 

                   set_current_state(TASK_INTERRUPTIBLE);    //将当前进程状态改为TASK_INTERRUPTIBLE

 

                   inp = fds->in; outp = fds->out; exp = fds->ex;

                   rinp = fds->res_in; routp = fds->res_out; rexp = fds->res_ex;

 

                   for (i = 0; i < n; ++rinp, ++routp, ++rexp) { //遍历每个描述符

                            unsigned long in, out, ex, all_bits, bit = 1, mask, j;

                            unsigned long res_in = 0, res_out = 0, res_ex = 0;

                            const struct file_operations *f_op = NULL;

                            struct file *file = NULL;

 

                            in = *inp++; out = *outp++; ex = *exp++;

                            all_bits = in | out | ex;

                            if (all_bits == 0) {

                                     i += __NFDBITS;       // //如果这个字没有待查找的描述符, 跳过这个长字(32位)

                                     continue;

                            }

 

                            for (j = 0; j < __NFDBITS; ++j, ++i, bit <<= 1) {     //遍历每个长字里的每个位

                                     int fput_needed;

                                     if (i >= n)

                                               break;

                                     if (!(bit & all_bits))

                                               continue;

                                     file = fget_light(i, &fput_needed);

                                     if (file) {

                                               f_op = file->f_op;

                                               MARK(fs_select, "%d %lld",

                                                                 i, (long long)*timeout);

                                               mask = DEFAULT_POLLMASK;

                                               if (f_op && f_op->poll)

/* 在这里循环调用所监测的fd_set内的所有文件描述符对应的驱动程序的poll函数 */

                                                        mask = (*f_op->poll)(file, retval ? NULL : wait);

                                               fput_light(file, fput_needed);

                                               if ((mask & POLLIN_SET) && (in & bit)) {

                                                        res_in |= bit; //如果是这个描述符可读, 将这个位置位

                                                        retval++;  //返回描述符个数加1

                                               }

                                               if ((mask & POLLOUT_SET) && (out & bit)) {

                                                        res_out |= bit;

                                                        retval++;

                                               }

                                               if ((mask & POLLEX_SET) && (ex & bit)) {

                                                        res_ex |= bit;

                                                        retval++;

                                               }

                                     }

                                     cond_resched();

                            }

//返回结果

                            if (res_in)

                                     *rinp = res_in;

                            if (res_out)

                                     *routp = res_out;

                            if (res_ex)

                                     *rexp = res_ex;

                   }

                   wait = NULL;

/* 到这里遍历结束。retval保存了检测到的可操作的文件描述符的个数。如果有文件可操作，则跳出for(;;)循环，直接返回。若没有文件可操作且timeout时间未到同时没有收到signal,则执行schedule_timeout睡眠。睡眠时间长短由__timeout决定，一直等到该进程被唤醒。

那该进程是如何被唤醒的？被谁唤醒的呢？

我们看下面的select唤醒过程*/

                   if (retval || !*timeout || signal_pending(current))

                            break;

                  if(table.error) {

                            retval = table.error;

                            break;

                   }

 

                   if (*timeout < 0) {

                            /* Wait indefinitely */

                            __timeout = MAX_SCHEDULE_TIMEOUT;

                   } else if (unlikely(*timeout >= (s64)MAX_SCHEDULE_TIMEOUT - 1)) {

                            /* Wait for longer than MAX_SCHEDULE_TIMEOUT. Do it in a loop */

                            __timeout = MAX_SCHEDULE_TIMEOUT - 1;

                            *timeout -= __timeout;

                   } else {

                            __timeout = *timeout;

                            *timeout = 0;

                   }

                   __timeout = schedule_timeout(__timeout);

                   if (*timeout >= 0)

                            *timeout += __timeout;

         }

         __set_current_state(TASK_RUNNING);

 

         poll_freewait(&table);

 

         return retval;

}

 

2.  select的唤醒过程

前面介绍了select会循环遍历它所监测的fd_set内的所有文件描述符对应的驱动程序的poll函数。驱动程序提供的poll函数首先会将调用select的用户进程插入到该设备驱动对应资源的等待队列(如读/写等待队列)，然后返回一个bitmask告诉select当前资源哪些可用。

一个典型的驱动程序poll函数实现如下：

(摘自《Linux Device Drivers � ThirdEdition》Page 165)

static unsigned int scull_p_poll(struct file *filp, poll_table *wait)

{

    struct scull_pipe *dev = filp->private_data;

    unsigned int mask = 0;

    /*

     * The buffer is circular; it is considered full

     * if "wp" is right behind "rp" and empty if the

     * two are equal.

     */

    down(&dev->sem);

    poll_wait(filp, &dev->inq,  wait);

    poll_wait(filp, &dev->outq, wait);

    if (dev->rp != dev->wp)

        mask |= POLLIN | POLLRDNORM;    /* readable */

    if (spacefree(dev))

        mask |= POLLOUT | POLLWRNORM;   /* writable */

    up(&dev->sem);

    return mask;

}

将用户进程插入驱动的等待队列是通过poll_wait做的。

Poll_wait定义如下：

static inline void poll_wait(struct file * filp, wait_queue_head_t * wait_address, poll_table *p)

{

         if (p && wait_address)

                   p->qproc(filp, wait_address, p);

}

这里的p->qproc在do_select内poll_initwait(&table)被初始化为__pollwait，如下：

void poll_initwait(struct poll_wqueues *pwq)

{

         init_poll_funcptr(&pwq->pt, __pollwait);

         pwq->error = 0;

         pwq->table = NULL;

         pwq->inline_index = 0;

}

__pollwait定义如下：

/* Add a new entry */

static void __pollwait(struct file *filp, wait_queue_head_t *wait_address,

                                     poll_table *p)

{

         struct poll_table_entry *entry = poll_get_entry(p);

         if (!entry)

                   return;

         get_file(filp);

         entry->filp = filp;

         entry->wait_address = wait_address;

         init_waitqueue_entry(&entry->wait, current);

         add_wait_queue(wait_address,&entry->wait);

}

通过init_waitqueue_entry初始化一个等待队列项，这个等待队列项关联的进程即当前调用select的进程。然后将这个等待队列项插入等待队列wait_address。Wait_address即在驱动poll函数内调用poll_wait(filp, &dev->inq,  wait);时传入的该驱动的&dev->inq或者&dev->outq等待队列。

 

注: 关于等待队列的工作原理可以参考下面这篇文档:

http://blog.chinaunix.net/u2/60011/showart_1334657.html

 

到这里我们明白了select如何当前进程插入所有所监测的fd_set关联的驱动内的等待队列，那进程究竟是何时让出CPU进入睡眠状态的呢？

进入睡眠状态是在do_select内调用schedule_timeout(__timeout)实现的。当select遍历完fd_set内的所有设备文件，发现没有文件可操作时(即retval=0),则调用schedule_timeout(__timeout)进入睡眠状态。

 

唤醒该进程的过程通常是在所监测文件的设备驱动内实现的，驱动程序维护了针对自身资源读写的等待队列。当设备驱动发现自身资源变为可读写并且有进程睡眠在该资源的等待队列上时，就会唤醒这个资源等待队列上的进程。

举个例子，比如内核的8250 uart driver:

Uart是使用的Tty层维护的两个等待队列, 分别对应于读和写: (uart是tty设备的一种)

struct tty_struct {

         ……

         wait_queue_head_t write_wait;

         wait_queue_head_t read_wait;

         ……

}

当uart设备接收到数据，会调用tty_flip_buffer_push(tty);将收到的数据push到tty层的buffer。

然后查看是否有进程睡眠的读等待队列上，如果有则唤醒该等待会列。

过程如下：

serial8250_interrupt -> serial8250_handle_port -> receive_chars -> tty_flip_buffer_push ->

flush_to_ldisc -> disc->receive_buf

在disc->receive_buf函数内：

if (waitqueue_active(&tty->read_wait)) //若有进程阻塞在read_wait上则唤醒

wake_up_interruptible(&tty->read_wait);

 

到这里明白了select进程被唤醒的过程。由于该进程是阻塞在所有监测的文件对应的设备等待队列上的，因此在timeout时间内，只要任意个设备变为可操作，都会立即唤醒该进程，从而继续往下执行。这就实现了select的当有一个文件描述符可操作时就立即唤醒执行的基本原理。

 

Referece:

1.       Linux Device Drivers � ThirdEdition

2.       内核等待队列机制原理分析

http://blog.chinaunix.net/u2/60011/showart_1334657.html

3.       Kernel code : Linux 2.6.18_pro500 - Montavista


本文来自: (www.91linux.com) 详细出处参考：http://www.91linux.com/html/article/kernel/20081027/13698.html

评论

发表评论

此博客中的热门博文

【转】AMBA、AHB、APB总线简介

AMBA 简介 随着深亚微米工艺技术日益成熟，集成电路芯片的规模越来越大。数字IC从基于时序驱动的设计方法，发展到基于IP复用的设计方法，并在SOC设计中得到了广泛应用。在基于IP复用的SoC设计中，片上总线设计是最关键的问题。为此，业界出现了很多片上总线标准。其中，由ARM公司推出的AMBA片上总线受到了广大IP开发商和SoC系统集成者的青睐，已成为一种流行的工业标准片上结构。AMBA规范主要包括了AHB(Advanced High performance Bus)系统总线和APB(Advanced Peripheral Bus)外围总线。   AMBA 片上总线        AMBA 2.0 规范包括四个部分：AHB、ASB、APB和Test Methodology。AHB的相互连接采用了传统的带有主模块和从模块的共享总线，接口与互连功能分离，这对芯片上模块之间的互连具有重要意义。AMBA已不仅是一种总线，更是一种带有接口模块的互连体系。下面将简要介绍比较重要的AHB和APB总线。 基于 AMBA 的片上系统        一个典型的基于AMBA总线的系统框图如图３所示。        大多数挂在总线上的模块(包括处理器)只是单一属性的功能模块：主模块或者从模块。主模块是向从模块发出读写操作的模块，如CPU，DSP等；从模块是接受命令并做出反应的模块，如片上的RAM，AHB／APB 桥等。另外，还有一些模块同时具有两种属性，例如直接存储器存取(DMA)在被编程时是从模块，但在系统读传输数据时必须是主模块。如果总线上存在多个主模块，就需要仲裁器来决定如何控制各种主模块对总线的访问。虽然仲裁规范是AMBA总线规范中的一部分，但具体使用的算法由RTL设计工程师决定，其中两个最常用的算法是固定优先级算法和循环制算法。AHB总线上最多可以有16个主模块和任意多个从模块，如果主模块数目大于16，则需再加一层结构(具体参阅ARM公司推出的Multi-layer AHB规范)。APB 桥既是APB总线上唯一的主模块，也是AHB系统总线上的从模块。其主要功能是锁存来自AHB系统总...
发表评论
阅读全文

【转】C++/CLI程序进程之间的通讯

　现在，把大型软件项目分解为一些相交互的小程序似乎变得越来越普遍，程序各部分之间的通讯可使用某种类型的通讯协议，这些程序可能运行在不同的机器上、不同的操作系统中、以不同的语言编写，但也有可能只在同一台机器上，实际上，这些程序可看成是同一程序中的不同线程。而本文主要讨论C++/CLI程序间的通讯，当然，在此是讨论进程间通讯，而不是网络通讯。 　　 简介 　　试想一个包含数据库查询功能的应用，通常有一个被称为服务端的程序，等待另一个被称为客户端程序发送请求，当接收到请求时，服务端执行相应功能，并把结果（或者错误信息）返回给客户端。在许多情况中，有着多个客户端，所有的请求都会在同一时间发送到同一服务端，这就要求服务端程序要更加高级、完善。 　　在某些针对此任务的环境中，服务端程序可能只是众多程序中的一个程序，其他可能也是服务端或者客户端程序，实际上，如果我们的数据库服务端需要访问不存在于本机的文件，那么它就可能成为其他某个文件服务器的一个客户端。一个程序中可能会有一个服务线程及一个或多个客户线程，因此，我们需小心使用客户端及服务端这个术语，虽然它们表达了近似的抽象含义，但在具体实现上却大不相同。从一般的观点来看，客户端即为服务端所提供服务的"消费者"，而服务端也能成为其他某些服务的客户端。 　　 服务端套接字 　　让我们从一个具体有代表性的服务端程序开始（请看例1）,此程序等待客户端发送一对整数，把它们相加之后返回结果给客户端。 　　例1： using namespace System; using namespace System::IO; using namespace System::Net; using namespace System::Net::Sockets; int main(array<String^>^ argv) { if (argv->Length != 1) { Console::WriteLine("Usage: Server port"); Environment::Exit(1); } int port = 0; try { port = Int32::Parse(argv[0]); } catch (FormatException^ e) { Console::Wri...
1 条评论
阅读全文

【转】VxWorks入门

1．VxWorks开发方式：交叉开发，即将开发分为主机（host）和目标机（target）两部分。 类似于dos下C语言程序的开发。 合并开发的优点：简单 缺点：资源消耗量大，CPU支持，非标准体系的支持 host (Tornado) target(vxWork) 小程序模块 vxWorks实际采用开发模式 Tornado提供：编辑，编译，调试，性能分析工具，是vxWorks的开发工具 vxWorks：面向对象可以剪裁的实际运行操作系统 2.vxWorks启动方式 <1>Rom方式 (vxWork_rom) vxWorks直接烧入rom <2>Rom引导方式（bootrom+vxWorks） 其中bootrom烧入rom，vxWorks可以通过从串口，网口，硬盘，flash等下载！这里的bootrom不是开发环境中的bootable，在开发环境里bootable指的是vxWorks，downloadable指application 3.调试 <1>attachs/20060907_164540_564.rar 用来在多任务调试时将调试对象绑定到某个任务 <2>任务级调试（attachs/20060907_164540_564.rar taskName） 单个任务的调试不会影响到其他任务的运行，主要用来调用户的应用程序。 全局断点：在调另一任务或本任务时，系统运行本任务断点，则停下。各任务要配合使用。 任务断点：调本任务时，系统运行到本任务断点，则停下。如果没有attachs/20060907_164540_564.rar到本任务，不起作用。 一次性断点：跑到一次之后自动删除。 <3>系统级调试(attachs/20060907_164540_564.rar system) 把所有task和系统core、中断看成一个整体，可用于调试系统和中断。对中断调试，如果不是系统级调试，无论是那种断点都不起作用 ！wdbAgent不在调试范围内，当任务级调试时工作在中断方式，系统级调试工作在轮询方式。 ！可是使用命令行方式的调试，参看crossWind教程。 4.调度 优先级调度（无条件） 时间片：同优先级，如果时间片没有打开，任务采取先到先运行，运行完毕在交出cpu，如果打开，则轮流使用cpu。 ！死循环使比它...
发表评论
阅读全文