操作系统（3）

• 平等竞争：不能假设各并发进程的相对执行速度。即各并发进程享有平等地、独立地竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任意指令结束时，其他并发进程可以进入临界区。
• 不可独占：并发进程中的某个进程不在临界区时，它不能阻止其他进程进入临界区。
• 互斥使用：并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。
• 有限等待：并发进程中的某个进程从申请进入临界区时开始，应在有限时间内得以进入临界区。

• 屏蔽中断：进程进入临界区后立即屏蔽所有中断，离开后打开中断。缺点是多核系统无效，并且用户程序控制中断很危险（试想一下，一个进程屏蔽中断后不再打开中断，那你的系统就GG了）。

• 互斥加锁：对临界区加锁以实现互斥。当某个进程进入临界区后，它将锁上临界区，直到它退出临界区为止。加锁的缺点：1、有可能出现其中一个进程的执行，导致另一个进程长期得不到处理机资源，而处于永久饥饿状态（starvation）。2、如果一个进程进入临界区，但是在它把锁变量置1之前被中断，另一个进程进入临界区后将0置1，这样，当前一个进程再次运行时它也将锁变量置1，这样临界区内依然存在两个进程。如何解决？我们可以为临界区设置一个管理员，由这个管理员来管理相应临界区的公有资源，这个管理员就是信号量。

• 信号量：信号量sem是一个整数，信号量的数值仅能由P、V原语操作改变。原语操作都是原子性的。

设置信号量初始值sem=1;

P操作（down）：申请进入临界区

sem=sem-1

判断sem≥0

TRUE：继续（执行临界区命令）

FALSE：阻塞进入队列挂起

V操作（up）：退出临界区

sem=sem+1

判断sem＞0

TRUE：继续（执行退出临界区之后的命令）

FALSE：唤醒队列上阻塞的进程，再执行退出临界区之后的命令

被唤醒的进程直接进入临界区，要退出的时候再执行V操作。

实例：

• 初始sem=1，有进程A\B\C。
• A进来P操作，sem=0，进入临界区。B进来P操作,sem=-1，挂起；C进来P操作sem=-2，挂起。
• A出临界区V操作，sem=-1，唤醒挂起的进程，比如B。B被唤醒了直接进入临界区，退出时V操作，sem=0，唤醒挂起的进程C。C被唤醒了直接进入临界区，退出时V操作,sem=1。回到初始状态

操作系统层面上的线程同步

• 锁：锁有两个基本操作，闭锁和开锁。而闭锁有两个步骤：一是等待锁达到打开状态，二是获得锁并锁上。显然，闭锁的两个操作应该是原子操作，不能分开。当对方持有锁时，你就不需要等待锁变为打开状态，而是去睡觉，锁打开后对方再来把你叫醒。

• 信号量：和进程间同步一个概念，sem、P、V原语。

• 管程（Monitor）即监视器的意思：

a. 它监视的就是进程或线程的同步操作。具体来说，管程就是一组子程序、变量和数据结构的组合。言下之意，把需要同步的代码用一个管程的构造框起来，即将需要保护的代码置于begin monitor和end monitor之间，即可获得同步保护，也就是任何时候只能有一个线程活跃在管程里面。

b. 在管程中使用两种同步机制：锁用来进行互斥，条件变量用来控制执行顺序。从某种意义上来说，管程就是锁+条件变量。

c. 条件变量就是线程可以在上面等待的东西，而另外一个线程则可以通过发送信号将在条件变量上的线程叫醒。因此，条件变量有点像信号量，但又不是信号量，因为不能对其进行up和down操作。

d. 管程只能在单台计算机上发挥作用，如果想在多计算机环境下进行同步，那就需要其他机制了，而这种其他机制就是消息传递。

• 消息传递：

a. 消息传递是通过同步双方经过互相收发消息来实现，它有两个基本操作：发送send和接收receive。他们均是操作系统的系统调用，而且既可以是阻塞调用，也可以是非阻塞调用。而同步需要的是阻塞调用，即如果一个线程执行receive操作，就必须等待受到消息后才能返回。也就是说，如果调用receive，则该线程将挂起，在收到消息后，才能转入就绪。

b. 消息传递最大的问题就是消息丢失和身份识别。由于网络的不可靠性，消息在网络间传输时丢失的可能性较大。

c. 消息丢失可以通过使用TCP协议减少丢失，但也不是100%可靠。身份识别问题则可以使用诸如数字签名和加密技术来弥补。

• 栅栏：栅栏顾名思义就是一个障碍，到达栅栏的线程必须停止下来，知道出去栅栏后才能往前推进。该院与主要用来对一组线程进行协调，因为有时候一组线程协同完成一个问题，所以需要所有线程都到同一个地方汇合之后一起再向前推进。例如，在并行计算时就会遇到这种需求，如下图所示：

同步、异步

• 同步：进程执行一个操作之后，进程等待IO操作完成(也就是我们说的阻塞)或者轮询的去查看IO操作(也就是我们说的非阻塞)是否完成，等待结果，然后才继续执行后续的操作。
• 异步：进程执行一个操作后，可以去执行其他的操作，然后等待通知再回来执行刚才没执行完的操作。

阻塞、非阻塞

• 阻塞：进程给CPU传达一个任务之后，一直等待CPU处理完成，然后才执行后面的操作。
• 非阻塞：进程给CPU传达任务之后，继续处理后续的操作，隔断时间再来询问之前的操作是否完成。这样的过程其实也叫轮询。

TIPS：

1. 同步有阻塞和非阻塞之分，异步没有，它一定是非阻塞的。

2. 阻塞、非阻塞、多路IO复用，都是同步IO，异步必定是非阻塞的。

BIO、NIO、AIO

• 同步阻塞IO（BIO）：

我们熟知的Socket编程就是BIO，一个socket连接一个处理线程，典型的一请求一应答，缺点是缺乏弹性伸缩能力，线程可是很宝贵的资源。（这个线程负责这个Socket连接的一系列数据传输操作）。阻塞的原因在于：操作系统允许的线程数量是有限的，多个socket申请与服务端建立连接时，服务端不能提供相应数量的处理线程，没有分配到处理线程的连接就会阻塞等待或被拒绝。

• 同步非阻塞IO（NIO）：NIO的底层实现原理

一个socket连接只有在特点时候才会发生数据传输IO操作，大部分时间这个“数据通道”是空闲的，但还是占用着线程。NIO作出的改进就是“一个请求一个线程”，在连接到服务端的众多socket中，只有需要进行IO操作的才能获取服务端的处理线程进行IO。这样就不会因为线程不够用而限制了socket的接入。epoll是NIO的具体实现。

• 异步非阻塞IO（AIO）：

AIO是发出IO请求后，由操作系统自己去获取IO权限并进行IO操作，线程可以去做别的事情了，所以是异步的。NIO则是发出IO请求后，由线程不断尝试获取IO权限。

为什么NIO比BIO高效？

因为NIO一个请求一个线程，这样就不会因为线程不够用而限制了socket的接入。

NIO的底层实现原理

Java NIO的实现是这样的，NIO包中主要有Channel、Buffer、Selector这几种对象。

• Channel：NIO把它支持的I/O对象抽象为Channel，模拟了通信连接，用户可以通过它读取和写入数据。
• Buffer：Buffer是一块连续的内存区域，一般作为Channel收发数据的载体出现。所有数据都通过Buffer对象来处理。
• Selector：Selector类提供了监控一个和多个通道当前状态的机制。只要Channel向Selector注册了某种特定的事件，Selector就会监听这些事件是否会发生，一旦发生某个事件，便会通知对应的Channel。使用选择器，借助单一线程，就可对数量庞大的活动I/O通道实施监控和维护。

流程：

• 向Selector对象注册感兴趣的事件
• 从Selector中获取感兴趣的事件
• 根据不同的事件进行相应的处理

举个例子：

• 服务端的selector上注册了读事件，某时刻客户端给服务端发送了一些数据，阻塞I/O这时会调用read()方法阻塞地读取数据，而NIO的服务端会在selector中添加一个读事件。服务端的处理线程会轮询地访问selector，如果访问selector时发现有感兴趣的事件到达，则处理这些事件，如果没有感兴趣的事件到达，则处理线程会一直阻塞直到感兴趣的事件到达为止。

I/O多路复用

一句话解释：单个线程，通过记录跟踪每个I/O流(socket)的状态，来同时管理多个I/O流

• select, poll, epoll 都是I/O多路复用的具体的实现。
• 这些函数也会使进程阻塞，select先阻塞，有活动套接字才返回，但是和阻塞I/O不同的是，这两个函数可以同时阻塞多个I/O操作，而且可以同时对多个读操作，多个写操作的I/O函数进行检测，直到有数据可读或可写（就是监听多个socket）。
• 正因为阻塞I/O只能阻塞一个I/O操作，而I/O复用模型能够阻塞多个I/O操作，所以才叫做多路复用。

select\poll\epoll

• select, poll, epoll 都是I/O多路复用的具体的实现，epoll是NIO的具体实现

Nginx的高并发得益于其采用了epoll模型，Apache就没采用

• 因为一个线程只能处理一个套接字的I/O事件，如果想同时处理多个，可以利用非阻塞忙轮询的方式。
• 我们只要把所有流从头到尾查询一遍，就可以处理多个流了，但这样做很不好，因为如果所有的流都没有I/O事件，白白浪费CPU时间片。
• 正如有一位科学家所说，计算机所有的问题都可以增加一个中间层来解决，同样，为了避免这里cpu的空转，我们不让这个线程亲自去检查流中是否有事件，而是引进了一个代理(一开始是select,后来是poll，select只能监听1024个连接，而且会修改传入的参数数组，poll去掉了连接限制，而且不再修改传入的参数数组)，这个代理很牛，它可以同时观察许多流的I/O事件，如果没有事件，代理就阻塞，线程就不会挨个挨个去轮询了。
• 但是依然有个问题，我们从select\poll那里仅仅知道了，有I/O事件发生了，却并不知道是哪那几个流（可能有一个，多个，甚至全部），我们只能无差别轮询所有流。所以select具有O(n)的无差别轮询复杂度，同时处理的流越多，无差别轮询时间就越长。
• 因此有了epoll，epoll会把哪个流发生了怎样的I/O事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd）的，此时我们对这些流的操作都是有意义的。复杂度降低到了O(1)。不能不说epoll跟select相比，是质的飞跃。

epoll概述

设想一下如下场景：有100万个客户端同时与一个服务器进程保持着TCP连接。而每一时刻，通常只有几百上千个TCP连接是活跃的(事实上大部分场景都是这种情况)。如何实现这样的高并发？

在select/poll时代，服务器进程每次都把这100万个连接告诉操作系统(从用户态复制句柄数据结构到内核态)，让操作系统内核去查询这些套接字上是否有事件发生，轮询完后，再将句柄数据复制到用户态，让服务器应用程序轮询处理已发生的网络事件，这一过程资源消耗较大，因此，select/poll一般只能处理几千的并发连接。

epoll的设计和实现与select完全不同。epoll通过在Linux内核中申请一个简易的文件系统，把原先的select/poll调用分成了3个部分：
调用epoll_create()建立一个epoll对象(在epoll文件系统中为这个句柄对象分配资源)
调用epoll_ctl向epoll对象中添加这100万个连接的套接字
调用epoll_wait收集发生的事件的连接 
如此一来，要实现上面说的场景，只需要在进程启动时建立一个epoll对象，然后在需要的时候向这个epoll对象中添加或者删除连接。同时，epoll_wait的效率也非常高，因为调用epoll_wait时，并没有一股脑的向操作系统复制这100万个连接的句柄数据，内核也不需要去遍历全部的连接

应用：Nginx的高并发得益于其采用了epoll模型，Apache就没采用，传统Apache都是多进程或者多线程来工作

epoll底层实现原理

一句话描述就是：三步曲。

第一步：epoll_create()系统调用。此调用返回一个句柄，之后所有的使用都依靠这个句柄来标识。
第二步：epoll_ctl()系统调用。通过此调用向epoll对象中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。
第三部：epoll_wait()系统调用。通过此调用收集收集在epoll监控中已经发生的事件。

流程概述：
epoll_create()创建一个eventpoll结构体，里面包含红黑树和双链表。epoll_ctl()将所有连接句柄数据放入红黑树，如果连接有动作，就把连接放入双链表。epoll_wait()检查双链表，有连接就返回给用户。

流程详解：

当某一进程调用epoll_create方法时，Linux内核会创建一个eventpoll结构体，这个结构体中有两个成员与epoll的使用方式密切相关。eventpoll结构体如下所示

每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间效率是lgn，其中n为树的高度)。

 而所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中。

在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：

当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。

从上面的讲解可知：通过红黑树和双链表数据结构，并结合回调机制，造就了epoll的高效。

epoll的水平触发和边缘触发

一句话解释：水平触发会一直通知，边缘触发只会通知一次。select(),poll()模型都是水平触发模式，信号驱动IO是边缘触发模式，epoll()模型即支持水平触发，也支持边缘触发，默认是水平触发。

Level_triggered(水平触发)：当被监控的文件描述符上有可读写事件发生时，epoll_wait()会通知处理程序去读写。如果这次没有把数据一次性全部读写完(如读写缓冲区太小)，那么下次调用 epoll_wait()时，它还会通知你在上没读写完的文件描述符上继续读写，当然如果你一直不去读写，它会一直通知你！！！如果系统中有大量你不需要读写的就绪文件描述符，而它们每次都会返回，这样会大大降低处理程序检索自己关心的就绪文件描述符的效率！！！

Edge_triggered(边缘触发)：当被监控的文件描述符上有可读写事件发生时，epoll_wait()会通知处理程序去读写。如果这次没有把数据全部读写完(如读写缓冲区太小)，那么下次调用epoll_wait()时，它不会通知你，也就是它只会通知你一次，直到该文件描述符上出现第二次可读写事件才会通知你！！！这种模式比水平触发效率高，系统不会充斥大量你不关心的就绪文件描述符！！！

阻塞IO：当你去读一个阻塞的文件描述符时，如果在该文件描述符上没有数据可读，那么它会一直阻塞(通俗一点就是一直卡在调用函数那里)，直到有数据可读。当你去写一个阻塞的文件描述符时，如果在该文件描述符上没有空间(通常是缓冲区)可写，那么它会一直阻塞，直到有空间可写。以上的读和写我们统一指在某个文件描述符进行的操作，不单单指真正的读数据，写数据，还包括接收连接accept()，发起连接connect()等操作...

非阻塞IO：当你去读写一个非阻塞的文件描述符时，不管可不可以读写，它都会立即返回，返回成功说明读写操作完成了，返回失败会设置相应errno状态码，根据这个errno可以进一步执行其他处理。它不会像阻塞IO那样，卡在那里不动！！！
应用场景：
监听的socket文件描述符我们用sockfd，对于即要读写的文件描述符用connfd代替
对于监听的sockfd，最好使用水平触发模式，边缘触发模式会导致高并发情况下，有的客户端会连接不上。如果非要使用边缘触发，网上有的方案是用while来循环accept()。

对于读写的connfd，水平触发模式下，阻塞和非阻塞效果都一样，不过为了防止特殊情况，还是建议设置非阻塞。

对于读写的connfd，边缘触发模式下，必须使用非阻塞IO，并要一次性全部读写完数据。

用户态和内核态

如上图所示，从宏观上来看，Linux操作系统的体系架构分为用户态和内核态（或者用户空间和内核）。内核从本质上看是一种软件——控制计算机的硬件资源，并提供上层应用程序运行的环境。用户态即上层应用程序的活动空间，应用程序的执行必须依托于内核提供的资源，包括CPU资源、存储资源、I/O资源等。为了使上层应用能够访问到这些资源，内核必须为上层应用提供访问的接口：即系统调用。、

系统调用是操作系统的最小功能单位，这些系统调用根据不同的应用场景可以进行扩展和裁剪，现在各种版本的Unix实现都提供了不同数量的系统调用，如Linux的不同版本提供了240-260个系统调用，FreeBSD大约提供了320个（reference：UNIX环境高级编程）。我们可以把系统调用看成是一种不能再化简的操作（类似于原子操作，但是不同概念），有人把它比作一个汉字的一个“笔画”，而一个“汉字”就代表一个上层应用，我觉得这个比喻非常贴切。因此，有时候如果要实现一个完整的汉字（给某个变量分配内存空间），就必须调用很多的系统调用。如果从实现者（程序员）的角度来看，这势必会加重程序员的负担，良好的程序设计方法是：重视上层的业务逻辑操作，而尽可能避免底层复杂的实现细节。库函数正是为了将程序员从复杂的细节中解脱出来而提出的一种有效方法。它实现对系统调用的封装，将简单的业务逻辑接口呈现给用户，方便用户调用，从这个角度上看，库函数就像是组成汉字的“偏旁”。这样的一种组成方式极大增强了程序设计的灵活性，对于简单的操作，我们可以直接调用系统调用来访问资源，如“人”，对于复杂操作，我们借助于库函数来实现，如“仁”。显然，这样的库函数依据不同的标准也可以有不同的实现版本，如ISO C 标准库，POSIX标准库等。

Shell是一个特殊的应用程序，俗称命令行，本质上是一个命令解释器，它下通系统调用，上通各种应用，通常充当着一种“胶水”的角色，来连接各个小功能程序，让不同程序能够以一个清晰的接口协同工作，从而增强各个程序的功能。同时，Shell是可编程的，它可以执行符合Shell语法的文本，这样的文本称为Shell脚本，通常短短的几行Shell脚本就可以实现一个非常大的功能，原因就是这些Shell语句通常都对系统调用做了一层封装。为了方便用户和系统交互，一般，一个Shell对应一个终端，终端是一个硬件设备，呈现给用户的是一个图形化窗口。我们可以通过这个窗口输入或者输出文本。这个文本直接传递给shell进行分析解释，然后执行。