深入浅出 Linux 惊群：现象、原因和解决方案

"惊群"简单地来讲，就是多个进程(线程)阻塞睡眠在某个系统调用上，在等待某个 fd(socket)的事件的到来。当这个 fd(socket)的事件发生的时候，这些睡眠的进程(线程)就会被同时唤醒，多个进程(线程)从阻塞的系统调用上返回，这就是"惊群"现象。"惊群"被人诟病的是效率低下，大量的 CPU 时间浪费在被唤醒发现无事可做，然后又继续睡眠的反复切换上。本文谈谈 linux socket 中的一些"惊群"现象、原因以及解决方案。

1. Accept"惊群"现象

我们知道，在网络分组通信中，网络数据包的接收是异步进行的，因为你不知道什么时候会有数据包到来。因此，网络收包大体分为两个过程：

[1] 数据包到来后的事件通知[2] 收到事件通知的Task执行流，响应事件并从队列中取出数据包

数据包到来的通知分为两部分：

(1)网卡通知数据包到来，中断协议栈收包；

(2)协议栈将数据包填充 socket 的接收队列，通知应用程序有数据可读，这里仅讨论数据到达协议栈之后的事情。

应用程序是通过 socket 和协议栈交互的，socket 隔离了应用程序和协议栈，socket 是两者之间的接口，对于应用程序，它代表协议栈；而对于协议栈，它又代表应用程序，当数据包到达协议栈的时候，发生下面两个过程：

[1] 协议栈将数据包放入socket的接收缓冲区队列，并通知持有该socket的应用程序；[2] 持有该socket的应用程序响应通知事件，将数据包从socket的接收缓冲区队列中取出

对于高性能的服务器而言，为了利用多 CPU 核的优势，大多采用多个进程(线程)同时在一个 listen socket 上进行 accept 请求。多个进程阻塞在 Accept 调用上，那么在协议栈将 Client 的请求 socket 放入 listen socket 的 accept 队列的时候，是要唤醒一个进程还是全部进程来处理呢？

linux 内核通过睡眠队列来组织所有等待某个事件的 task，而 wakeup 机制则可以异步唤醒整个睡眠队列上的 task，wakeup 逻辑在唤醒睡眠队列时，会遍历该队列链表上的每一个节点，调用每一个节点的 callback，从而唤醒睡眠队列上的每个 task。这样，在一个 connect 到达这个 lisent socket 的时候，内核会唤醒所有睡眠在 accept 队列上的 task。N 个 task 进程(线程)同时从 accept 返回，但是，只有一个 task 返回这个 connect 的 fd，其他 task 都返回-1(EAGAIN)。这是典型的 accept"惊群"现象。这个是 linux 上困扰了大家很长时间的一个经典问题，在 linux2.6(似乎在 2.4.1 以后就已经解决，有兴趣的同学可以去验证一下)以后的内核中得到彻底的解决，通过添加了一个 WQ_FLAG_EXCLUSIVE 标记告诉内核进行排他性的唤醒，即唤醒一个进程后即退出唤醒的过程，具体如下：

/* * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve * number) then we wake all the non-exclusive tasks and one exclusive task. * * There are circumstances in which we can try to wake a task which has already * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns * zero in this (rare) case, and we handle it by continuing to scan the queue. */static void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int wake_flags, void *key){ wait_queue_t *curr, *next; list_for_each_entry_safe(curr, next, &q->task_list, task_list) { unsigned flags = curr->flags; if (curr->func(curr, mode, wake_flags, key) && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive) break; }}

这样，在 linux 2.6 以后的内核，用户进程 task 对 listen socket 进行 accept 操作，如果这个时候如果没有新的 connect 请求过来，用户进程 task 会阻塞睡眠在 listent fd 的睡眠队列上。这个时候，用户进程 Task 会被设置 WQ_FLAG_EXCLUSIVE 标志位，并加入到 listen socket 的睡眠队列尾部(这里要确保所有不带 WQ_FLAG_EXCLUSIVE 标志位的 non-exclusive waiters 排在带 WQ_FLAG_EXCLUSIVE 标志位的 exclusive waiters 前面)。根据前面的唤醒逻辑，一个新的 connect 到来，内核只会唤醒一个用户进程 task 就会退出唤醒过程，从而不存在了"惊群"现象。

2. select/poll/Epoll "惊群"现象

尽管 accept 系统调用已经不再存在"惊群"现象，但是我们的"惊群"场景还没结束。通常一个 server 有很多其他网络 IO 事件要处理，我们并不希望 server 阻塞在 accept 调用上，为提高服务器的并发处理能力，我们一般会使用 select/poll/epoll I/O 多路复用技术，同时为了充分利用多核 CPU，服务器上会起多个进程(线程)同时提供服务。于是，在某一时刻多个进程(线程)阻塞在 select/poll/epoll_wait 系统调用上，当一个请求上来的时候，多个进程都会被 select/poll/epoll_wait 唤醒去 accept，然而只有一个进程(线程 accept 成功，其他进程(线程 accept 失败，然后重新阻塞在 select/poll/epoll_wait 系统调用上。可见，尽管 accept 不存在"惊群"，但是我们还是没能摆脱"惊群"的命运。难道真的没办法了么？我只让一个进程去监听 listen socket 的可读事件，这样不就可以避免"惊群"了么？

没错，就是这个思路，我们来看看 Nginx 是怎么避免由于 listen fd 可读造成的 epoll_wait"惊群"。这里简单说下具体流程，不进行具体的源码分析。

2.1 Nginx 的 epoll"惊群"避免

Nginx 中有个标志 ngx_use_accept_mutex，当 ngx_use_accept_mutex 为 1 的时候（当 nginx worker 进程数>1 时且配置文件中打开 accept_mutex 时，这个标志置为 1），表示要进行 listen fdt"惊群"避免。

Nginx 的 worker 进程在进行 event 模块的初始化的时候，在 core event 模块的 process_init 函数中(ngx_event_process_init)将 listen fd 加入到 epoll 中并监听其 READ 事件。Nginx 在进行相关初始化完成后，进入事件循环(ngx_process_events_and_timers 函数)，在 ngx_process_events_and_timers 中判断，如果 ngx_use_accept_mutex 为 0，那就直接进入 ngx_process_events(ngx_epoll_process_events)，在 ngx_epoll_process_events 将调用 epoll_wait 等待相关事件到来或超时，epoll_wait 返回的时候该干嘛就干嘛。这里不讲 ngx_use_accept_mutex 为 0 的流程，下面讲下 ngx_use_accept_mutex 为 1 的流程。

[1] 进入ngx_trylock_accept_mutex，加锁抢夺accept权限（ngx_shmtx_trylock(&ngx_accept_mutex)），加锁成功，则调用ngx_enable_accept_events(cycle) 来将一个或多个listen fd加入epoll监听READ事件(设置事件的回调函数ngx_event_accept)，并设置ngx_accept_mutex_held = 1;标识自己持有锁。[2] 如果ngx_shmtx_trylock(&ngx_accept_mutex)失败，则调用ngx_disable_accept_events(cycle, 0)来将listen fd从epoll中delete掉。[3] 如果ngx_accept_mutex_held = 1(也就是抢到accept权)，则设置延迟处理事件标志位flags |= NGX_POST_EVENTS; 如果ngx_accept_mutex_held = 0(没抢到accept权)，则调整一下自己的epoll_wait超时，让自己下次能早点去抢夺accept权。[4] 进入ngx_process_events(ngx_epoll_process_events)，在ngx_epoll_process_events将调用epoll_wait等待相关事件到来或超时。[5] epoll_wait返回，循环遍历返回的事件，如果标志位flags被设置了NGX_POST_EVENTS，则将事件挂载到相应的队列中(Nginx有两个延迟处理队列，(1)ngx_posted_accept_events：listen fd返回的事件被挂载到的队列。(2)ngx_posted_events：其他socket fd返回的事件挂载到的队列)，延迟处理事件，否则直接调用事件的回调函数。[6] ngx_epoll_process_events返回后，则开始处理ngx_posted_accept_events队列上的事件，于是进入的回调函数是ngx_event_accept，在ngx_event_accept中accept客户端的请求，进行一些初始化工作，将accept到的socket fd放入epoll中。[7] ngx_epoll_process_events处理完成后，如果本进程持有accept锁ngx_accept_mutex_held = 1，那么就将锁释放。[8] 接着开始处理ngx_posted_events队列上的事件。

Nginx 通过一次仅允许一个进程将 listen fd 放入自己的 epoll 来监听其 READ 事件的方式来达到 listen fd"惊群"避免。然而做好这一点并不容易，作为一个高性能 web 服务器，需要尽量避免阻塞，并且要很好平衡各个工作 worker 的请求，避免饿死情况，下面有几个点需要大家留意：

[1] 避免新请求不能及时得到处理的饿死现象 工作worker在抢夺到accept权限，加锁成功的时候，要将事件的处理delay到释放锁后在处理(为什么ngx_posted_accept_events队列上的事件处理不需要延迟呢？ 因为ngx_posted_accept_events上的事件就是listen fd的可读事件，本来就是我抢到的accept权限，我还没accept就释放锁，这个时候被别人抢走了怎么办呢？)。否则，获得锁的工作worker由于在处理一个耗时事件，这个时候大量请求过来，其他工作worker空闲，然而没有处理权限在干着急。[2] 避免总是某个worker进程抢到锁，大量请求被同一个进程抢到，而其他worker进程却很清闲。 Nginx有个简单的负载均衡，ngx_accept_disabled表示此时满负荷程度，没必要再处理新连接了，我们在nginxnf曾经配置了每一个nginx worker进程能够处理的最大连接数，当达到最大数的7/8时，ngx_accept_disabled为正，说明本nginx worker进程非常繁忙，将不再去处理新连接。每次要进行抢夺accept权限的时候，如果ngx_accept_disabled大于0，则递减1，不进行抢夺逻辑。

Nginx 采用在同一时刻仅允许一个 worker 进程监听 listen fd 的可读事件的方式，来避免 listen fd 的"惊群"现象。然而这种方式编程实现起来比较难，难道不能像 accept 一样解决 epoll 的"惊群"问题么？答案是可以的。要说明 epoll 的"惊群"问题以及解决方案，不能不从 epoll 的两种触发模式说起。

相关视频推荐

“惊群”原理、锁的设计方案及绕不开的“死锁”问题

6种epoll的设计，让你吊打面试官【linux服务器开发】

学习地址：C/C++Linux服务器开发/后台架构师【零声教育】-学习视频教程-腾讯课堂

需要C/C++ Linux服务器架构师学习资料加qun812855908获取（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享

3 Epoll"惊群"之 LT(水平触发模式)、ET(边沿触发模式)

我们先来看下 LT、ET 的语意：

[1] LT 水平触发模式只要仍然有未处理的事件，epoll就会通知你，调用epoll_wait就会立即返回。[2] ET 边沿触发模式只有事件列表发生变化了，epoll才会通知你。也就是，epoll_wait返回通知你去处理事件，如果没处理完，epoll不会再通知你了，调用epoll_wait会睡眠等待，直到下一个事件到来或者超时。

LT(水平触发模式)、ET(边沿触发模式)在"惊群"问题上，有什么不一样的表现么？要说明这个，就不能不来谈谈 Linux 内核的 sleep/wakeup 机制以及 epoll 的实现核心机制了。

3.1 epoll 的核心机制

在了解 epoll 的核心机制前，先了解一下内核 sleep/wakeup 机制的几个核心概念：

[1] 等待队列 waitqueue队列头(wait_queue_head_t)往往是资源生产者队列成员(wait_queue_t)往往是资源消费者当头的资源ready后, 会逐个执行每个成员指定的回调函数，来通知它们资源已经ready了[2] 内核的poll机制被Poll的fd, 必须在实现上支持内核的Poll技术，比如fd是某个字符设备,或者是个socket, 它必须实现file_operations中的poll操作, 给自己分配有一个等待队列头wait_queue_head_t，主动poll fd的某个进程task必须分配一个等待队列成员, 添加到fd的等待队列里面去, 并指定资源ready时的回调函数，用socket做例子, 它必须有实现一个poll操作, 这个Poll是发起轮询的代码必须主动调用的, 该函数中必须调用poll_wait(),poll_wait会将发起者作为等待队列成员加入到socket的等待队列中去，这样socket发生事件时可以通过队列头逐个通知所有关心它的进程。[3] epollfd本身也是个fd, 所以它本身也可以被epoll

epoll 作为中间层，为多个进程 task，监听多个 fd 的多个事件提供了一个便利的高效机制，我们来看下 epoll 的机制图：

从图中，可以看到 epoll 可以监控多个 fd 的事件，它通过一颗红黑树来组织所有被 epoll_ctl 加入到 epoll 监听列表中的 fd，每个被监听的 fd 在 epoll 用一个 epoll item(epi)来标识。

根据内核的 poll 机制，epoll 需要为每个监听的 fd 构造一个 epoll entry(设置关心的事件以及注册回调函数)作为等待队列成员睡眠在每个 fd 的等待队列，以便 fd 上的事件 ready 了，可以通过 epoll 注册的回调函数通知到 epoll。

epoll 作为进程 task 的中间层，它需要有一个等待队列 wq 给 task 在没事件来 epoll_wait 的时候来睡眠等待(epoll fd 本身也是一个 fd，它和其他 fd 一样还有另外一个等待队列 poll_wait，作为 poll 机制被 poll 的时候睡眠等待的地方)。

epoll 可能同时监听成千上万的 fd，这样在少量 fd 有事件 ready 的时候，它需要一个 ready list 队列来组织所有已经 ready 的就绪 fd，以便能够高效通知给进程 task，而不需要遍历所有监听的 fd。图中的一个 epoll 的 sleep/wakeup 流程如下：

无事件的时候，多个进程task调用epoll_wait睡眠在epoll的wq睡眠队列上。[1] 这个时候一个请求RQ_1上来，listen fd这个时候ready了，开始唤醒其睡眠队列上的epoll entry，并执行之前epoll注册的回调函数ep_poll_callback。[2] ep_poll_callback主要做两件事情，(1)发生的event事件是epoll entry关心的，则将epi挂载到epoll的就绪队列ready list并进入(2)，否则结束。(2)如果当前wq不为空，则唤醒睡眠在epoll等待队列上睡眠的task(这里唤醒一个还是多个，是区分epoll的ET模式还是LT模式，下面在细讲)。[3] epoll_wait被唤醒继续前行，在ep_poll中调用ep_send_events将fd相关的event事件和数据copy到用户空间，这个时候就需要遍历epoll的ready list以便收集task需要监控的多个fd的event事件和数据上报给用户进程task，这个在ep_scan_ready_list中完成，这里会将ready list清空。

通过上图的 epoll 事件通知机制，epoll 的 LT 模式、ET 模式在事件通知行为上的差别，也只能是在[2]上 task 唤醒逻辑上的差别了。我们先来看下，在 epoll_wait 中调用的导致用户进程 task 睡眠的 ep_poll 函数的核心逻辑：

static int ep_poll(struct eventpoll *ep, struct epoll_event __user *events, int maxevents, long timeout){int res = 0, eavail, timed_out = 0;bool waiter = false;...eavail = ep_events_available(ep);//是否有fd就绪if (eavail)goto send_events;//有fd就绪，则直接跳过去上报事件给用户if (!waiter) { waiter = true; init_waitqueue_entry(&wait, current);//为当前进程task构造一个睡眠entry spin_lock_irq(&ep->wq.lock); //插入到epoll的wq后面，注意这里是排他插入的，就是带WQ_FLAG_EXCLUSIVE flag __add_wait_queue_exclusive(&ep->wq, &wait); spin_unlock_irq(&ep->wq.lock); }for (;;) { //将当前进程设置位睡眠, 但是可以被信号唤醒的状态, 注意这个设置是"将来时", 我们此刻还没睡 set_current_state(TASK_INTERRUPTIBLE); // 检查是否真的要睡了 if (fatal_signal_pending(current)) { res = -EINTR; break; } eavail = ep_events_available(ep); if (eavail) break; if (signal_pending(current)) { res = -EINTR; break; } // 检查是否真的要睡了 end //使得当前进程休眠指定的时间范围， if (!schedule_hrtimeout_range(to, slack, HRTIMER_MODE_ABS)) { timed_out = 1; break; }}__set_current_state(TASK_RUNNING);send_events: /* * Try to transfer events to user space. In case we get 0 events and * there's still timeout left over, we go trying again in search of * more luck. */ // ep_send_events往用户态上报事件，即那些epoll_wait返回后能获取的事件 if (!res && eavail && !(res = ep_send_events(ep, events, maxevents)) && !timed_out) goto fetch_events; if (waiter) { spin_lock_irq(&ep->wq.lock); __remove_wait_queue(&ep->wq, &wait); spin_unlock_irq(&ep->wq.lock); } return res;}

接着，我们看下监控的 fd 有事件发生的回调函数 ep_poll_callback 的核心逻辑：

#define wake_up(x)__wake_up(x, TASK_NORMAL, 1, NULL)static int ep_poll_callback(wait_queue_entry_t *wait, unsigned mode, int sync, void *key){ int pwake = 0; struct epitem *epi = ep_item_from_wait(wait); struct eventpoll *ep = epi->ep; __poll_t pollflags = key_to_poll(key); unsigned long flags; int ewake = 0; .... //判断是否有我们关心的event if (pollflags && !(pollflags & epi->event.events)) goto out_unlock; //将当前的epitem放入epoll的ready list if (!ep_is_linked(epi) && list_add_tail_lockless(&epi->rdllink, &ep->rdllist)) { ep_pm_stay_awake_rcu(epi); } //如果有task睡眠在epoll的等待队列，唤醒它 if (waitqueue_active(&ep->wq)) { .... wake_up(&ep->wq);// } ....}

wake_up 函数最终会调用到 wake_up_common，通过前面的 wake_up_common 我们知道，唤醒过程在唤醒一个带 WQ_FLAG_EXCLUSIVE 标记的 task 后，即退出唤醒过程。通过上面的 ep_poll，task 是排他(带 WQ_FLAG_EXCLUSIVE 标记)加入到 epoll 的等待队列 wq 的。也就是，在 ep_poll_callback 回调中，只会唤醒一个 task。这就有问题，根据 LT 的语义：只要仍然有未处理的事件，epoll 就会通知你。例如有两个进程 A、B 睡眠在 epoll 的睡眠队列，fd 的可读事件到来唤醒进程 A，但是 A 可能很久才会去处理 fd 的事件，或者它根本就不去处理。根据 LT 的语义，应该要唤醒进程 B 的。

我们来看下 epoll 怎么在 ep_send_events 中实现满足 LT 语义的：

static int ep_send_events(struct eventpoll *ep, struct epoll_event __user *events, int maxevents) { struct ep_send_events_data esed; esed.maxevents = maxevents; esed.events = events; ep_scan_ready_list(ep, ep_send_events_proc, &esed, 0, false); return esed.res; } static __poll_t ep_scan_ready_list(struct eventpoll *ep, __poll_t (*sproc)(struct eventpoll *, struct list_head *, void *), void *priv, int depth, bool ep_locked) { ... // 所有的epitem都转移到了txlist上, 而rdllist被清空了 list_splice_init(&ep->rdllist, &txlist); ... //sproc 就是 ep_send_events_proc res = (*sproc)(ep, &txlist, priv); ... //没有处理完的epitem, 重新插入到ready list list_splice(&txlist, &ep->rdllist); /* ready list不为空, 直接唤醒... */ // 保证(2) if (!list_empty(&ep->rdllist)) { if (waitqueue_active(&ep->wq)) wake_up(&ep->wq); ... } } static __poll_t ep_send_events_proc(struct eventpoll *ep, struct list_head *head, void *priv) { ... //遍历就绪fd列表 list_for_each_entry_safe(epi, tmp, head, rdllink) { ... //然后从链表里面移除当前就绪的epi list_del_init(&epi->rdllink); //读取当前epi的事件 revents = ep_item_poll(epi, &pt, 1); if (!revents) continue; //将当前的事件和用户传入的数据都copy给用户空间 if (__put_user(revents, &uevent->events) || __put_user(epi->event.data, &uevent->data)) { //如果发生错误了， 则终止遍历过程，将当前epi重新返回就绪队列，剩下的也会在ep_scan_ready_list中重新放回就绪队列 list_add(&epi->rdllink, head); ep_pm_stay_awake(epi); if (!esed->res) esed->res = -EFAULT; return 0; } } if (epi->event.events & EPOLLONESHOT) epi->event.events &= EP_PRIVATE_BITS; else if (!(epi->event.events & EPOLLET)) { // 保证(1) //如果是非ET模式(即LT模式)，当前epi会被重新放到epoll的ready list。 list_add_tail(&epi->rdllink, &ep->rdllist); ep_pm_stay_awake(epi); } }

上面处理逻辑的核心流程就 2 点：

[1] 遍历并清空epoll的ready list，遍历过程中，对于每个epi收集其返回的events，如果没收集到event，则continue去处理其他epi，否则将当前epi的事件和用户传入的数据都copy给用户空间，并判断，如果是在LT模式下，则将当前epi重新放回epoll的ready list[2] 遍历epoll的ready list完成后，如果ready list不为空，则继续唤醒epoll睡眠队列wq上的其他task B。task B从epoll_wait醒来继续前行，重复上面的流程，继续唤醒wq上的其他task C，这样链式唤醒下去。

通过上面的流程，在一个 epoll 上睡眠的多个 task，如果在一个 LT 模式下的 fd 的事件上来，会唤醒 epoll 睡眠队列上的所有 task，而 ET 模式下，仅仅唤醒一个 task，这是 epoll"惊群"的根源。等等，这样在 LT 模式下就必然"惊群"，epoll 在 LT 模式下的"惊群"没办法解决么？

3.2 epoll_create& fork

相信大家在多进程服务中使用 epoll 的时候，都会有这样一个疑问，是先 epoll_create 得到 epoll fd 后在 fork 子进程，还是先 fork 子进程，然后每个子进程在 epoll_create 自己独立的 epoll fd 呢？有什么异同？

3.2.1 先 epoll_create 后 fork

这样，多个进程公用一个 epoll 实例(父子进程的 epoll fd 指向同一个内核 epoll 对象)，上面介绍的 epoll 核心机制流程，都是在同一个 epoll 对象上的，这种情况下，epoll 有以下这些特性：

[1] epoll在ET模式下不存在“惊群”现象，LT模式是epoll“惊群”的根源，并且LT模式下的“惊群”没办法避免。[2] LT的“惊群”是链式唤醒的，唤醒过程直到当前epi的事件被处理了，无法获得到新的事件才会终止唤醒过程。例如有A、B、C、D...等多个进程task睡眠在epoll的睡眠队列上，并且都监控同一个listen fd的可读事件。一个请求上来，会首先唤醒A进程，A在epoll_wait的处理过程中会唤醒进程B，这样进程B在epoll_wait的处理过程中会唤醒C，这个时候A的epoll_wait处理完成返回，进程A调用accept读取了当前这个请求，进程C在自己的epoll_wait处理过程中，从epi中获取不到事件了，于是终止了整个链式唤醒过程。[3] 多个进程的epoll fd由于指向同一个epoll内核对象，他们对epoll fd的相关epoll_ctl操作会相互影响。一不小心可能会出现一些比较诡异的行为。想象这样一个场景(实际上应该不是这样用)，有一个服务在1234，1235，1236这3个端口上提供服务，于是它epoll_create得到epoll fd后，fork出3个工作的子进程A、B、C，它们分别在这3个端口创建listen fd，然后加入到epoll中监听其可读事件。这个时候端口1234上来一个请求，A、B、C同时被唤醒，A在epoll_wait返回后，在进行accept前由于种种原因卡住了，没能及时accept。B、C在epoll_wait返回后去accept又不能accept到请求，这样B、C重新回到epoll_wait，这个时候又被唤醒，这样只要A没有去处理这个请求之前，B、C就一直被唤醒，然而B、C又无法处理该请求。[4] ET模式下，一个fd上的同事多个事件上来，只会唤醒一个睡眠在epoll上的task，如果该task没有处理完这些事件，在没有新的事件上来前，epoll不会在通知task去处理。

由于 ET 的事件通知模式，通常在 ET 模式下的 epoll_wait 返回，我们会循环 accept 来处理所有未处理的请求，直到 accept 返回 EAGAIN 才退出 accept 流程。否则，没处理遗留下来的请求，这个时候如果没有新的请求过来触发 epoll_wait 返回，这样遗留下来的请求就得不到及时处理。这种处理模式，会带来一种类"惊群"现象。考虑，下面的一个处理过程：

A、B、C三个进程在监听listen fd的EPOLLIN事件，都睡眠在epoll_wait上，都是ET模式。[1] listen fd上一个请求C_1上来，该请求唤醒了A进程，A进程从epoll_wait返回准备去accept该请求来处理。[2] 这个时候，第二个请求C_2上来，由于睡眠队列上是B、C，于是epoll唤醒B进程，B进程从epoll_wait返回准备去accept该请求来处理。[3] A进程在自己的accept循环中，首选accept得到C_1，接着A进程在第二个循环继续accept，继续得到C_2。[4] B进程在自己的accept循环中，调用accept，由于C_2已经被A拿走了，于是B进程accept返回EAGAIN错误，于是B进程退出accept流程重新睡眠在epoll_wait上。[5] A进程继续第三个循环，这个时候已经没有请求了， accept返回EAGAIN错误，于是A进程也退出accept处理流程，进入请求的处理流程。

可以看到，B 进程被唤醒了，但是并没有事情可以做，同时，epoll 的 ET 这样的处理模式，负载容易出现不均衡。

3.2.2 先 fork 后 epoll_create

用法上，通常是在父进程创建了 listen fd 后，fork 多个 worker 子进程来共同处理同一个 listen fd 上的请求。这个时候，A、B、C...等多个子进程分别创建自己独立的 epoll fd，然后将同一个 listen fd 加入到 epoll 中，监听其可读事件。这种情况下，epoll 有以下这些特性：

[1] 由于相对同一个listen fd而言， 多个进程之间的epoll是平等的，于是，listen fd上的一个请求上来，会唤醒所有睡眠在listen fd睡眠队列上的epoll，epoll又唤醒对应的进程task，从而唤醒所有的进程(这里不管listen fd是以LT还是ET模式加入到epoll)。[2] 多个进程间的epoll是独立的，对epoll fd的相关epoll_ctl操作相互独立不影响。

可以看出，在使用友好度方面，多进程独立 epoll 实例要比共用 epoll 实例的模式要好很多。独立 epoll 模式要解决 fd 的排他唤醒 epoll 即可。

4.EPOLLEXCLUSIVE 排他唤醒 Epoll

linux4.5 以后的内核版本中，增加了 EPOLLEXCLUSIVE， 该选项只能通过 EPOLL_CTL_ADD 对需要监控的 fd(例如 listen fd)设置 EPOLLEXCLUSIVE 标记。这样 epoll entry 是通过排他方式挂载到 listen fd 等待队列的尾部的，睡眠在 listen fd 的等待队列上的 epoll entry 会加上 WQ_FLAG_EXCLUSIVE 标记。根据前面介绍的内核 wake up 机制，listen fd 上的事件上来，在遍历并唤醒等待队列上的 entry 的时候，遇到并唤醒第一个带 WQ_FLAG_EXCLUSIVE 标记的 entry 后，就结束遍历唤醒过程。于是，多进程独立 epoll 的"惊群"问题得到解决。

5."惊群"之 SO_REUSEPORT

"惊群"浪费资源的本质在于很多处理进程在别惊醒后，发现根本无事可做，造成白白被唤醒，做了无用功。但是，简单的避免"惊群"会造成同时并发上来的请求得不到及时处理(降低了效率)，为了避免这种情况，NGINX 允许配置成获得 Accept 权限的进程一次性循环 Accept 所有同时到达的全部请求，但是，这会造成短时间 worker 进程的负载不均衡。为此，我们希望的是均衡唤醒，也就是，假设有 4 个 worker 进程睡眠在 epoll_wait 上，那么此时同时并发过来 3 个请求，我们希望 3 个 worker 进程被唤醒去处理，而不是仅仅唤醒一个进程或全部唤醒。

然而要实现这样不是件容易的事情，其根本原因在于，对于大多采用 MPM 机制(multi processing module)TCP 服务而言，基本上都是多个进程或者线程同时在一个 Listen socket 上进行监听请求。根据前面介绍的 Linux 睡眠队列的唤醒方式，基本睡眠在这个 listen socket 上的 Task 只能要么全部被唤醒，要么被唤醒一个。

于是，基本的解决方案是起多个 listen socket，好在我们有 SO_REUSEPORT(linux 3.9 以上内核支持)，它支持多个进程或线程 bind 相同的 ip 和端口，支持以下特性：

[1] 允许多个socket bind/listen在相同的IP，相同的TCP/UDP端口[2] 目的是同一个IP、PORT的请求在多个listen socket间负载均衡[3] 安全上，监听相同IP、PORT的socket只能位于同一个用户下

于是，在一个多核 CPU 的服务器上，我们通过 SO_REUSEPORT 来创建多个监听相同 IP、PORT 的 listen socket，每个进程监听不同的 listen socket。这样，在只有 1 个新请求到达监听的端口的时候，内核只会唤醒一个进程去 accept，而在同时并发多个请求来到的时候，内核会唤醒多个进程去 accept，并且在一定程度上保证唤醒的均衡性。SO_REUSEPORT 在一定程度上解决了"惊群"问题，但是，由于 SO_REUSEPORT 根据数据包的四元组和当前服务器上绑定同一个 IP、PORT 的 listen socket 数量，根据固定的 hash 算法来路由数据包的，其存在如下问题：

[1] Listen Socket数量发生变化的时候，会造成握手数据包的前一个数据包路由到A listen socket，而后一个握手数据包路由到B listen socket，这样会造成client的连接请求失败。[2] 短时间内各个listen socket间的负载不均衡6.惊不"惊群"其实是个问题

很多时候，我们并不是害怕"惊群"，我们怕的"惊群"之后，做了很多无用功。相反在一个异常繁忙，并发请求很多的服务器上，为了能够及时处理到来的请求，我们希望能有多"惊群"就多"惊群"，因为根本做不了无用功，请求多到都来不及处理。于是出现下面的情形：

从上可以看到各个 CPU 都很忙，但是实际有用的 CPU 时间却很少，大部分的 CPU 消耗在_spin_lock 自旋锁上了，并且服务器并发吞吐量并没有随着 CPU 核数增加呈现线性增长，相反出现下降的情况。这是为什么呢？怎么解决？

6.1 问题原因

我们知道，一般一个 TCP 服务只有一个 listen socket、一个 accept 队列，而一个 TCP 服务一般有多个服务进程(一个核一个)来处理请求。于是并发请求到达 listen socket 处，那么多个服务进程势必存在竞争，竞争一存在，那么就需要用排队来解决竞态问题，于是似乎锁就无法避免了。在这里，有两类竞争主体，一类是内核协议栈(不可睡眠类)、一类是用户进程(可睡眠类)，这两类主体对 listen socket 发生三种类型的竞争：

[1] 协议栈内部之间的竞争[2] 用户进程内部之间的竞争[3] 协议栈和用户之间的竞争

由于内核协议栈是不可睡眠的，为此 linux 中采用两层锁定的 lock 结构，一把 listen_socket.lock 自旋锁，一把 listen_socket.own 排他标记锁。其中，listen_socket.lock 用于协议栈内部之间的竞争、协议栈和用户之间的竞争，而 listen_socket.own 用于用户进程内部之间的竞争，listen_socket.lock 作为 listen_socket.own 的排他保护(要获取 listen_socket.own 首先要获取到 listen_socket.lock)。对于处理 TCP 请求而言，一个 SYN 包 syn_skb 到来，这个时候内核 Lock(RCU 锁)住全局的 listeners Table，查找 syn_skb 对应的 listen_socket，没找到则返回错误。否则，就需要进入三次握手处理，首先内核协议栈需要自旋获得 listen_socket.lock 锁，初始化一些数据结构，回复 syn_ack，然后释放 listen_socket.lock 锁。

接着，client 端的 ack 包到来，协议栈这个时候，需要自旋获得 listen_socket.lock 锁，构造 client 端的 socket 等数据结构，如果 accept 队列没有被用户进程占用，那么就将连接排入 accept 队列等待用户进程来 accept，否则就排入 backlog 队列(职责转移，连接排入 accept 队列的事情交给占有 accept 队列的用户进程)。可见，处理一个请求，协议栈需要竞争两次 listen_socket 的自旋锁。由于内核协议栈不能睡眠，于是它只能自旋不断地去尝试获取 listen_socket.lock 自旋锁，直到获取到自旋锁成功为止，中间不能停下来。自旋锁这种暴力、打架的抢锁方式，在一个高并发请求到来的服务器上，就有可能出现上面这种 80%多的 CPU 时间被内核占用，应用程序只能够分配到较少的 CPU 时钟周期的资源的情况。

6.2 问题的解决

解决这个问题无非两个方向：(1) 多队列化，减少竞争者 (2) listen_socket 无锁化 。

6.2.1 多队列化 - SO_REUSEPORT

通过上面的介绍，在 Linux kernel 3.9 以上，可以通过 SO_REUSEPORT 来创建多个 bind 相同 IP、PORT 的 listen_socket。我们可以每一个 CPU 核创建一个 listen_socket 来监听处理请求，这样就是每个 CPU 一个处理进程、一个 listen_socket、一个 accept 队列，多个进程同时并发处理请求，进程之间不再相互竞争 listen_socket。SO_REUSEPORT 可以做到多个 listen_socket 间的负载均衡，然而其负载均衡效果是取决于 hash 算法，可能会出现短时间内的负载极端不均衡。

SO_REUSEPORT 是在将一对多的问题变成多对多的问题，将 Listen Socket 无序暴力争抢 CPU 的现状变成更为有序的争抢。多队列化的优化必须要面对和解决的四个问题是：队列比 CPU 多，队列与 CPU 相等，队列比 CPU 少，根本就没有队列，于是，他们要解决队列发生变化的情况。

如果仅仅把 TCP 的 Listener 看作一个被协议栈处理的 Socket，它和 Client Socket 一起都在相互拼命抢 CPU 资源，那么就可能出现上面的，短时间大量并发请求过来的时候，大量的 CPU 时间被消耗在自旋锁的争抢上了。我们可以换个角度，如果把 TCP Listener 看作一个基础设施服务呢？Listener 为新来的连接请求提供连接服务，并产生 Client Socket 给用户进程，它可以通过一个或多个两类 Accept 队列提供一个服务窗口给用户进程来 accept Client Socket 来处理。仅仅在 Client Socket 需要排入 Accept 队列的是，细粒度锁住队列即可，多个有多个 Accept 队列(每 CPU 一个，那么连锁队列的操作都可以省了)。这样 Listener 就与用户进程无关了，用户进程的产生、退出、CPU 间跳跃、绑定，解除绑定等等都不会影响 TCP Listener 基础设施服务，受影响的是仅仅他们自己该从那个 Accept 队列获取 Client Socket 来处理。于是一个解决思路是连接处理无锁化。

6.2.2 listen socket 无锁化- 旁门左道之 SYN Cookie

SYN Cookie 原理由 D.J. Bernstain 和 Eric Schenk 提出，专门用来防范 SYN Flood 攻击的一种手段。它的原理是，在 TCP 服务器接收到 SYN 包并返回 SYN ACK 包时，不分配一个专门的数据结构(避免浪费服务器资源)，而是根据这个 SYN 包计算出一个 cookie 值。这个 cookie 作为 SYN ACK 包的初始序列号。当客户端返回一个 ACK 包时，根据包头信息计算 cookie，与返回的确认序列号(初始序列号 + 1)进行对比，如果相同，则是一个正常连接，然后，分配资源，创建 Client Socket 排入 Accept 队列等等用户进程取出处理。于是，整个 TCP 连接处理过程实现了无状态的三次握手。SYN Cookie 机制实现了一定程度上的 listen socket 无锁化，但是它有以下几个缺点。

（1）丢失 TCP 选项信息在建立连接的过程中，不在服务器端保存任何信息，它会丢失很多选项协商信息，这些信息对 TCP 的性能至关重要，比如超时重传等。但是，如果使用时间戳选项，则会把 TCP 选项信息保存在 SYN ACK 段中 tsval 的低 6 位。（2）cookie 不能随地开启Linux 采用动态资源分配机制，当分配了一定的资源后再采用 cookie 技术。同时为了避免另一种拒绝服务攻击方式，攻击者发送大量的 ACK 报文，服务器忙于计算验证 SYN Cookie。服务器对收到的 ACK 进行 Cookie 合法性验证前，需要确定最近确实发生了半连接队列溢出，不然攻击者只要随便发送一些 ACK，服务器便要忙于计算了。6.2.3 listen socket 无锁化- Linux 4.4 内核给出的 Lockless TCP listener

SYN cookie 给出了 Lockless TCP listener 的一些思路，但是我们不想是无状态的三次握手，又不想请求的处理和 Listener 强相关，避免每次进行握手处理都需要 lock 住 listen socket，带来性能瓶颈。4.4 内核前的握手处理是以 listen socket 为主体，listen socket 管理着所有属于它的请求，于是进行三次握手的每个数据包的处理都需要操作这个 listener 本身，而一般情况下，一个 TCP 服务器只有一个 listener，于是在多核环境下，就需要加锁 listen socket 来安全处理握手过程了。我们可以换个角度，握手的处理不再以 listen socket 为主体，而是以连接本身为主体，需要记住的是该连接所属的 listen socket 即可。4.4 内核握手处理流程如下：

[1] TCP 数据包 skb 到达本机，内核协议栈从全局 socket 表中查找 skb 的目的 socket(sk)，如果是 SYN 包，当然查找到的是 listen_socket 了，于是，协议栈根据 skb 构造出一个新的 socket(tmp_sk)，并将 tmp_sk 的 listener 标记为 listen_socket，并将 tmp_sk 的状态设置为 SYNRECV，同时将构造好的 tmp_sk 排入全局 socket 表中，并回复 syn_ack 给 client。

[2] 如果到达本机的 skb 是 syn_ack 的 ack 数据包，那么查找到的将是 tmp_sk，并且 tmp_sk 的 state 是 SYNRECV，于是内核知道该数据包 skb 是 syn_ack 的 ack 包了，于是在 new_sk 中拿出连接所属的 listen_socket，并且根据 tmp_sk 和到来的 skb 构造出 client_socket，然后将 tmp_sk 从全局 socket 表中删除(它的使命结束了)，最后根据所属的 listen_socket 将 client_socket 排如 listen_socket 的 accept 队列中，整个握手过程结束。

4.4 内核一改之前的以 listener 为主体，listener 管理所有 request 的方式，在 SYN 包到来的时候，进行控制反转，以 Request 为主体，构造出一个临时的 tmp_sk 并标记好其所属的 listener，然后平行插入到所有 socket 公共的 socket 哈希表中，从而解放掉 listener，实现 Lockless TCP listener。

原文地址：https://mp.weixin.qq/s/dQWKBujtPcazzw7zacP1lg

学会这11个主要元知识概念，妈妈再也不用担心我的代码编写啦

全文共3226字，预计学习时长10分钟

图源：Pexels

在小芯认识的程序员之中，大部分人都更注重实操实践，对于知识点的学习没有那么在意，虽然那些基础知识常常在编码中发挥不可取代的作用，但还是难以逃脱被人们看轻或忽视的命运。

当然现在也出了很多知识学习，指南指导类的文章或者课程，成为大家“投机取巧”、短时间掌握大量核心知识的“捷径”。

并不是说这种“捷径”不好。

在大多数情况下，有很多指南都是可以参考的，它们能够指导读者学习那些最热门的语言以及最热门的知识，从而使读者成为行业的佼佼者。

尽管这些指南可能有用，但它们仅引导读者获得表面价值。这些指南提供了浅层次的学习路线，如果想要往更深层次发展，还是需要自己去慢慢实践和探索。

因此，小芯今天帮大家整理了能“获得成为一个真正有效的开发人员所需的深度知识“。

但是这些生僻的编程“元”知识，仍需要读者自己去主动潜心钻研。

编程元知识是计算机科学专业毕业生必学的东西，而自学者经常会漏掉这些知识点。编程元知识是查看和编写代码的基础。

Aphinya Dechalert拍摄-这些都是“元”

本文提供一份清单式的指南，好让读者在这些新鲜好奇的知识行囊里进行浏览和挑选。

综合指南（绝大部分与语言无关）

全局图—：Aphinya Dechalert撰写

1. 数组！因为一切都是数据

几乎在每个教程中，都会遇到一个非常简单的数组版本。比如熟知的扁平的一维数组，包含少许元素。但是在现实生活中，还有更多的种类，形状和具有奇异性的数据可以以数组形式呈现。

当涉及到生产级数据集时，多维数组和交错数组是经常使用的类型。如何优化这些数组的结构以供创建和使用，决定着开发人员是否能高效地执行任务。

2. 谈谈算法

每个人都在谈论“算法”，仿佛它是一个被AI唤醒的神秘物体，会给所有人带来厄运。 或许这只是广大民众的一种看法。

在开发人员踏入编程的潮流前，算法只是编程中一系列实现特定结果的可重复规则。

当涉及到算法时，了解排序算法的机制可以帮助开发人员在处理大量数据时保持清醒。

有些时候，面临的是数据和数据处理问题。如果熟悉为特定类型的数据进行设计和测试的方法，那么就能减少对列表的sort（）等方法的依赖。

这是因为sort（）倾向于运行自己的算法，而该算法可能因绘制引擎而异。当编写自己的算法时，就可以更好地控制通过代码处理的数据的质量和速度。

3. SOLID设计原则

SOLID是编程中五项设计原则的集合。这五项原则是可以实现面向对象编程的模式。

SOLID原则的有用之处在于提升代码灵活性、长期可维护性，以及加强对开发人员间工作完成方式的全面理解。

除了创立健壮的代码之外，SOLID还形成了敏捷软件开发的核心理念。

4. 测试

不要仅仅学习如何测试，更要学会研究测试背后的理论。当进行测试时，开发人员倾向于仅仅关注单元测试，而不去弄清楚整体意识形态的机制，以及它们为什么是代码稳健的基础。

测试分为基于功能的测试和非功能性测试，如性能、安全性、可用性和兼容性测试。这些测试通常具有较低优先级，或者根本未被考虑。

重要的是，测试还能让开发人员运行假设的场景并预先确定数据的形态，以及在开始编码之前预测潜在的问题。

图源：Pexels

5. 树

有些时候会听到关于“树”的内容。这里的“树”不是指通常生长在泥土中并提供氧气的植物，而是基于关系基础结构——通过节点、叶节点、子节点、父节点和兄弟节点访问，从而构建数据。

如果使用过HTML，就会听说过DOM树。那是一种树的类型。二叉树是每个节点都有两个子节点连接的树，它创建了一个可以追溯到最顶端的金字塔样式图。

但是，树的意义远不止这些，它还与性能、处理数据以及如何快速检索数据有关。

6. 动态编程

动态编程是一种通过递归方式，将复杂问题分解为可能的最小子问题，来解决复杂问题的方法。这是一种编程技术，可用于多个学科，而不仅限于代码。

动态编程的关键点在于，它对递归的使用意味着一个问题只会被解决一次，并且可以优化工作负载，而不是根据特定的重复算法来组合事物。

最初，因为很像算法，动态编程的概念可能会让人困惑。但是动态编程和算法有着显著的不同，有着不同的机制原理，从长远来看，学习动态编程可以帮助开发人员成为一个更好的程序员。

7. 散列表 (Hash Table)?(与土豆煎饼 (Hashbrowns) 无关)

程序以一种易于访问和理解的方式组织大量数据。散列表是存储和检索数据的另一种方法。

当涉及大型数据集（有数百万个的数据点）并且需要快速检索数据时，散列表是常见的选择。但同时散列表也能对本地应用程序存储中较小的数据集进行设计，以提高效率并对特定集进行分类。

8. 二分搜索法

又回到了另一个与数据相关的话题。二分搜索是一个值得探索的重要话题，因为它与性能有关。

为了使二分搜索工作正常进行，必须要对需搜索的数据集进行预排序，以使算法能够快速遍历每个数据点并确定是否匹配。

关于二分搜索，有多种方法能够实现它，通常是算法和递归的混合。二分搜索的思想可以应用于不同的语言，它更多的是一种基于数学推理的技巧，而不是实际的代码。

9. 认真对待进程、线程和并发

当开始关注进程、线程和并发时，这意味着已经开始深入编程了。

然而，因为进程、线程和并发主要面向后端开发人员，但作为一个前端开发人员，可能从未遇到过这些问题，但对它们的工作原理有所了解仍然是一件好事。因为这有助于全面了解计算机的工作原理，以及代码是如何作为人类、绘制引擎/解释引擎和机器之间的通信桥梁进行工作的。

了解这些概念还能帮助你了解储存系统的工作方式以及编写的代码对性能的影响。

图源：Pexels

10. 链表

除非使用C ++或Python，否则不太可能会运用到链表。虽然链表看起来与数组十分相似，但是链表有着不同于数组的特定优点和缺点。

如果开始深入研究数据是如何以链表的形式显示的，就会发现它非常适用于大型数据集工作，因为它的容量是无限的。

如果数据过于庞大，最终需要调整数组的大小。而链表可以保持数据之间的“链接”。

11. 设计模式的艺术

一切都可以归结为一个模式。后退一步，着眼全局，并确定以前是否遇到相同问题，然后设计模式就得以实现了。

如果可能的话，则推荐使用设计模式来节省时间，防止潜在的问题进一步发展，并为代码编写过程创建标准。

虽然设计模式看起来是一个需要学习的大领域，但它也会带来良好的投资回报，因为实际上减少了将来由于结构缺乏或结构较弱而可能从代码中出现的百搭码文的数量。

在某种意义上，设计模式就好比一个预先设计的蓝图，有助于在不断的实践应用中保持代码的可读性和可理解性。

结语

编程不仅仅是学习一门语言的工作原理。语言、框架、库背后还隐藏着机制和技巧。

希望这份元知识指南能让大家对编码有更为全面的了解，并且不局限于……嗯，代码本身。

If else 语句会使很多刚入门的程序员感到困惑，但掌握if else 语句也是证明知识积累与应用达到新高度的标志。

不必完全理解所有的内容，但这些知识点可以有助于未来的程序编写。

知道或至少了解上述主题如何发挥作用并融入全局，将有助于加快编码过程，并提高所创建代码的潜在健壮性，以防出现残缺和衰退。

加油，各位机智的天才程序员们！

留言点赞关注

我们一起分享AI学习与发展的干货

如转载，请后台留言，遵守转载规范

22计算机考研，一定要收藏的408大纲

大家好呀，我是小芝

研芝士，是一个服务于广大计算机考生的

专业&贴心的服务团队

坚持数据驱动教育

持续研发高性价比的题库、图书、课程

陪伴你上岸各种计算机考试

时间已经来到了6月中旬

已经有75%的同学已经进入

到22考研计算机专业课的复习中

其中有47%的同学选择

计算机统考408的备考

每年都有大量的学校选择改考408（戳此了解22考研改408的院校>>>）。考408的学校越来越多，而且只接受408调剂的学校越来越多。导致备考408已经成为了大多数同学的第一选择。

大多数同学已经进入到了408的第一轮的复习中。在复习的时候先了解一下408考试大纲，明确考纲范围，并且能够了解到要备考的知识点体系，是非常重要的，会对接下来的备考起到一定的指导作用。

研芝士22新版《精深解读》，对408考试大纲进行了分析，对历年考试考点分布、分值分布都做了统计，进行了知识点的梳理和讲解，划出了常考重难点，预估22考研的考察方向，并精选了408真题、各院校真题和模拟习题专项练习。

每年最新版的考试大纲都会在9月份进行公布，所以22考研的同学可以先参照21的408考试大纲进行复习。

特别地，21考试大纲较20考试大纲有14处改动，也是这么多年以来唯一一次的变动，可以预见的是，22考试大纲不会再有太多的变动，可以按照21考试大纲进行复习备考。

接下来的全文为《2021计算机学科专业基础综合考试大纲》，建议添加到微信“我的收藏”，经常翻看！

408考试大纲

1考试性质

计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目。其目的是、科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机学科与计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

2考察目标

计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目。其目的是、科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机学科与计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

3试卷满分及试卷结构

1、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟。

2、答题方式

答题方式为闭卷、笔试。

3、试卷内容结构

数据结构 45分

计算机组成原理 45分

操作系统 35分

计算机网络 25分

4、分试卷题型结构

单项选择题 80分（40小题，每小题2分）

综合应用题 70分

4数据结构 考查内容

[考察目标]

1、掌握数据结构的基本概念、基本原理和基本方法。

2、掌握数据结构的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

一、线性表

（一）线性表的基本概念

（二）线性表的实现

1.顺序存储

2.链式存储

（三）线性表的应用

二、栈、队列和数组

（一）栈和队列的基本概念

（二）栈和队列的顺序存储结构

（三）栈和队列的链式存储结构

（四）多维数组的存储

（五）特殊矩阵的压缩存储

（六）栈、队列和数组的应用

三、树和二叉树

（一）树的基本概念

（二）二叉树

1.二叉树的定义及其主要特性

2.二叉树的顺序存储结构和链式存储结构

3.二叉树的遍历

4.线索二叉树的基本概念和构造

（三）树、森林

1.树的存储结构

2.森林与二叉树的转换

3.树和森林的遍历

（四）树和二叉树的应用

1.二叉搜索树

2.平衡二叉树

3.哈夫曼（Huffman）树和哈夫曼编码

四、图

（一）图的基本概念

（二）图的存储及基本操作

1.邻接矩阵法

2.邻接表法

3.邻接多重表、十字链表

（四）图的基本应用

1.最小（代价）生成树

2.最短路径

3.拓扑排序

4.关键路径

五、查找

（一）查找的基本概念

（二）顺序查找法

（三）分块查找法

（四）折半查找法

（五）B树及其基本操作、B+树的基本概念

（六）散列（Hash）表

（七）字符串模式匹配

（八）查找算法到的分析及应用

六、排序

（一）排序的基本概念

（二）插入排序

1.直接插入排序

2.折半插入排序

（三）起泡排序（Bubble Sort）

（四）简单选择排序

（五）希尔排序（Shell Sort）

（六）快速排序

（七）堆排序

（八）二路归并排序（Merge Sort）

（九）基数排序

（十）外部排序

（十一）各种排序算法到的比较

5计算机组成原理 考查内容

[考察目标]

1、理解单处理器计算机系统中各部件的内部工作原理、组成结果以及相互连接方式，具有完整的计算机系统的整机概念。

2、理解计算机系统层次化结构概念，熟悉硬件与软件之间的界面，掌握指令集体系结构的基本知识和基本实现方法。

3、能够综合运用计算机组成的基本原理和基本方法，对有关计算机硬件系统中的理论和实际问题进行计算、分析，对一些基本部件进行简单设计；并能对高级程序设计语言（如C语言）中的相关问题进行分析。

一、计算机系统概述

（一）计算机系统层次结构

1.计算机系统的基本组成

2.计算机硬件的基本组成

3.计算机软件和硬件的关系

4.计算机系统的工作过程

（二）计算机性能指标

吞吐量、响应时间、CPU时钟周期、主频、CPI、CPU执行时间、MIPS、MFLOPS、GFLOPS、TFLOPS、PFLOPS、EFLOPS、ZFLOPS。

二、数据的表示和运算

（一）数制与编码

1.进位计数制及其相互转换

2.真值和机器数

3.字符和字符串

（二）定点数的表示和运算

1.定点数的表示

无符号数的表示，带符号整数的表示

2.定点数的运算

定点数的移位运算，原码定点数的加/减运算，补码定点数的加/减运算，定点数的乘/除运算，溢出概念和判别方法。

（三）浮点数的表示和运算

1.浮点数的表示

IEEE 754标准

2.浮点数的加/减运算

（四）算术逻辑单元ALU

1.串行加法器和并行加法器

2.算术逻辑单元ALU的功能和结构

三、存储器层次结构

（一）存储器的分类

（二）存储器的层次化结构

（三）半导体随机存取存储器

1.SRAM存储器

2.DRAM存储器

3.只读存储器

4.Flash存储器

（四）主存储器与CPU的连接

（五）双口RAM和多模块存储器

（六）高速缓冲存储器（Cache）

1.Cache的基本工作原理

2.Cache和主存之间的映射方式

3.Cache中主存块的替换算法

4.Cache写策略

（七）虚拟存储器

1.虚拟存储器的基本概念

2.页式虚拟存储器

3.段式虚拟存储器

4.段页式虚拟存储器

5.TLB（快表）

四、指令系统

（一）指令格式

1.指令的基本格式

2.定长操作码指令格式

3.扩展操作码指令格式

（二）指令的寻址方式

1.有效地址的概念

2.数据寻址和指令寻址

3.常见寻址方式

（三）CISC和RISC的基本结构

五、中央处理器（CPU）

（一）CPU的功能和基本结构

（二）指令执行过程

（三）数据通路的功能和基本结构

（四）控制器的功能和工作原理

1.硬布线控制器

2.微程序控制器

微程序、微指令和微命令、微指令格式、微命令的编码方式、微地址的形成方式。

（五）指令流水线

1.指令流水线的基本概念

2.指令流水线的基本实现

3.超标量和动态流水线的基本概念

六、总线

（一）总线概述

1.总线的基本概念

2.总线的分类

3.总线的组成及性能指标

（二）总线操作和定时

1.同步定时方式

2.异步定时方式

（三）总线标准

七、输入输出（I/O）系统

（一）I/O系统基本概念

（二）外部设备

1.输入设备：键盘、鼠标

2.输出设备：显示器、打印机

3.外存储器：硬盘存储器、磁盘阵列

（三）I/O接口（I/O控制器）

1.I/O接口的功能和基本结构

2.I/O端口及其编址

（四）I/O方式

1.程序查询方式

2.程序中断方式

中断的基本概念，中断的响应过程，中断处理过程，多重中断和中断屏蔽的概念。

3.DMA方式

DMA控制器的组成，DMA传送过程。

6操作系统 考查内容

[考察目标]

1.掌握操作系统的基本概念、基本原理和基本功能、理解操作系统的整体运行过程。

2.掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。

3.能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。

一、操作系统概述

（一）操作系统的概念、特征、功能和提供的服务

（二）操作系统的发展与分类

（三）操作系统的运行环境

1.内核态与用户态

2.中断、异常

3.系统调用

（四）操作系统体系结构

二、进程管理

（一）进程与线程

1.进程概念

2.进程的状态与转换

3.进程控制

4.进程组织

5.进程通信

共享存储系统，消息传递系统，管道通信。

6.线程概念与多线程模型

（二）处理机调度

1.调度的基本概念

2.调度时机、切换与过程

3.调度的基本准则

4.调度方式

5.典型调度算法

先来先服务调度算法，短作业（短进程、短线程）优先调度算法，时间片轮转调度算法，优先级调度算法，高响应比优先调度算法，多级反馈队列调度算法；

（三）同步与互斥

1.进程同步的基本概念

2.实现临界区互斥的基本方法

软件实现方法，硬件实现方法。

3.信号量

4.管程

5.经典同步问题

生产者-消费者问题，读者-写者问题，哲学家进餐问题。

（四）死锁

1.死锁概念

2.死锁处理策略

3.死锁预防

4.死锁避免

系统安全状态，银行家算法。

5.死锁检测和解除

三、内存管理

（一）内存管理基础

1.内存管理概念

程序装入与链接，逻辑地址与物理地址空间，内存保护。

2.连续分配管理方式

3.非连续分配管理方式

分页管理方式，分段管理方式，段页式管理方式。

（二）虚拟内存管理

1.虚拟内存基本概念

2.请求分页管理方式

3.页面置换算法

最佳置换算法（OPT），先进先出置换算法（FIFO），最近最少使用置换算法（LRU），时钟置换算法（CLOCK）。

4.页面分配策略

5.工作集

6.抖动

四、文件管理

（一）文件系统基础

1.文件概念

2.文件的逻辑结构

顺序文件，索引文件，索引顺序文件。

3.目录结构

文件控制块和索引节点，单级目录结构和两级目录结构，树形目录结构，图形目录结构。

4.文件共享

5.文件保护

访问类型，访问控制。

（二）文件系统实现

1.文件系统层次结构

2.目录实现

3.文件实现

（三）磁盘组织与管理

1.磁盘的结构

2.磁盘调度算法

3.磁盘的管理

五、输入/输出（I/O）管理

（一）I/O管理概述

1.I/O控制方式

2.I/O软件层次结构

（二）I/O核心子系统

1.I/O调度概念

2.高速缓存与缓冲区

3.设备分配与回收

4.假脱机技术（SPOOLing）

7操作系统 考查内容

[考察目标]

1.掌握计算机网络的基本概念、基本原理和基本方法。

2.掌握计算机网络的体系结构和典型网络协议，了解典型网络的组成特点，理解典型网络设备的工作原理。

3.能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。

一、计算机网络体系结构

（一）计算机网络概述

1.计算机网络的概念、组成与功能

2.计算机网络的分类

3.计算机网络主要性能指标

（二）计算机网络体系结构与参考模型

1.计算机网络分层结构

2.计算机网络协议、接口、服务等概念

3.ISO/OSI参考模型和TCP/IP模型

二、物理层

（一）通信基础

1.信道、信号、带宽、码元、波特、速率、信源与信宿等基本概念

2.奈奎斯特定理与香农定理

3.编码与调制

4.电路交换、报文交换与分组交换

5.数据报与虚电路

（二）传输介质

1.双绞线、同轴电缆、光纤与无线传输介质

2.物理层接口的特性

（三）物理层设备

1.中继器

2.集线器

三、数据链路层

（一）数据链路层的功能

（二）组帧

（三）差错控制

1.检错编码

2.纠错编码

（四）流量控制与可靠传输机制

1.流量控制、可靠传输与滑动窗口机制

2.停止-等待协议

3.后退N帧协议（GBN）

4.选择重传协议（SR）

（五）介质访问控制

1.信道划分

频分多路复用，时分多路复用，波分多路复用，码分多路复用的概念和基本原理。

2.随机访问

ALOHA协议，CA协议，CA/CD协议，CA/CA协议。

3.轮询访问

令牌传递协议。

（六）局域网

1.局域网的基本概念与体系结构

2.以太网与IEEE 802.3

3.IEEE 802.11

4.令牌环网的基本原理

（七）广域网

1.广域网的基本概念

2.PPP协议

3.HDLC协议

（八）数据链路层设备

1.网桥的概念及其基本原理

2.局域网交换机及其工作原理

四、网络层

（一）网络层的功能

1.异构网络互连

2.路由与转发

3.拥塞控制

（二）路由算法

1.静态路由与动态路由

2.距离-向量路由算法

3.链路状态路由算法

4.层次路由

（三）IPv4

1.IPv4分组

2.IPv4地址与NAT

3.子网划分、路由聚集、子网掩码与CIDR

4.ARP协议、DHCP协议、ICMP协议

（四）IPv6

1.IPv6的主要特点

2.IPv6地址

（五）路由协议

1.自治系统

2.域内路由与域间路由

3.RIP路由协议

4.OSPF路由协议

5.BGP路由协议

（六）IP组播

1.组播的概念

2.IP组播地址

（七）移动IP

1IP的概念

2IP通信过程

（八）网络层设备

1.路由器的组成和功能

2.路由表与路由转发

五、传输层

（一）传输层提供的服务

1.传输层的功能

2.传输层寻址与端口

3.无连接服务与面向连接服务

（二）UDP协议

1.UDP数据段

2.UDP校验

（三）TCP协议

1.TCP段

2.TCP连接管理

3.TCP可靠传输

4.TCP流量控制与拥塞控制

六、应用层

（一）网络应用模型

1.客户/服务器模型

2.P2P模型

（二）DNS系统

1.层次域名空间

2.域名服务器

3.域名解析过程

（三）FTP

1.FTP协议的工作原理

2.控制连接与数据连接

（四）电子邮件

1.电子邮件系统的组成结构

2.电子邮件格式与MIME

3.TP协议与POP3协议

（五）WWW

1.WWW的概念与组成结构

2.HTTP协议