这个部分这个部分用来介绍操作系统，目前这一块知识是我的盲区，需要掌握这些基础知识，不仅仅是应付面试，为以后全栈学习打好基础。
1. 进程与线程
前言
本章主要介绍进程与线程的区别与联系相关知识点，也是我们面试过程中，经常会问到的一个问题。希望通过这篇文章，能让大家理解相关知识点~
涉及面试题：
- 1.进程与线程之间有什么区别？
- 2.进程、线程都各有什么特点？
- 3.进程之间的是怎么进行交互的呢？
- 4.什么是缓冲区溢出？
- 5.进程之间如何进行交互？
- 6.线程之间如何进行交互？
上面的面试题可以看出，其实都是一回事，只是换了一种提问方式，只要我们能掌握核心要点，随便面试官怎么提问，我们都能轻松应对！
1.1 小例子：
我们生活中有许许多多关于进程与线程的小例子，比如：1.我们使用打开一个微信软件，这个时候就开启了一个进程，
当我们在微信里面进行各种操作（查看朋友圈，扫一扫…），这么多的操作就是线程。
所以我们可以说“进程”是包含“线程”的，“线程”是“进程”的一个子集。
来源百度百科：
进程（Process） 是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。 在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。程序是指令、数据及其组织形式的描述，进程是程序的实体。
线程（thread） 是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。
我们简单总结下：
进程：指在系统中正在运行的一个应用程序；程序一旦运行就是进程；进程——资源分配的最小单位。
线程：系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元执行流。线程——程序执行的最小单位。
1.2 深入理解：
1.2.1 进程(线程+内存+文件/网络句柄)
我们通过上面的图片进行进一步理解：
“内存”： 我们通常所理解的内存是我们所见到的(2G/4G/8G/16G)物理内存,它为什么会在进程之中呢？ 实际上，这里的内存是逻辑内存。指的是内存的寻址空间。每个进程的内存是相互独立的。 否则的话会出现一个问题：我们把指针的值改一改就指向其他进程的内存了，通过这样我们岂不是就可以看到其他进程中”微信”或者是”网上银行”的信息， 这样的话，那我们的微信聊天记录或者是银行账户的信息就都被别人找到了，这是一个很危险的信号！显然这样是不可能的。
“文件/网络句柄”： 它们是所有的进程所共有的，例如打开同一个文件，去抢同一个网络的端口这样的操作是被允许的。
“线程”： 接下来，我们就要介绍一下我们的“线程”有关知识
1.2.2 线程(栈+PC+TLS)
1.2.2.1 栈:
我们通常都是说调用堆栈，其实这里的堆是没有含义的，调用堆栈就是调用栈的意思。 那么我们的栈里面有什么呢？ 我们从主线程的入口main函数，会不断的进行函数调用， 每次调用的时候，会把所有的参数和返回地址压入到栈中。
1.2.2.2 PC：
Program Counter 程序计数器，操作系统真正运行的是一个个的线程， 而我们的进程只是它的一个容器。PC就是指向当前的指令，而这个指令是放在内存中。 每个线程都有一串自己的指针，去指向自己当前所在内存的指针。 计算机绝大部分是存储程序性的，说的就是我们的数据和程序是存储在同一片内存里的 这个内存中既有我们的数据变量又有我们的程序。所以我们的PC指针就是指向我们的内存的。
1.2.2.2.1 缓冲区溢出
例如我们经常听到一个漏洞：缓冲区溢出 这是什么意思呢？ 例如：我们有个地方要输入用户名，本来是用来存数据的地方。 然后黑客把数据输入的特别长。这个长度超出了我们给数据存储的内存区，这时候跑到了 我们给程序分配的一部分内存中。黑客就可以通过这种办法将他所要运行的代码 写入到用户名框中，来植入进来。我们的解决方法就是，用用户名的长度来限制不要超过 用户名的缓冲区的大小来解决。
1.2.3 TLS:
全称：thread local storage 之前我们看到每个进程都有自己独立的内存，这时候我们想，我们的线程有没有一块独立的内存呢?答案是有的，就是TLS。 可以用来存储我们线程所独有的数据。 可以看到：线程才是我们操作系统所真正去运行的，而进程呢，则是像容器一样他把需要的一些东西放在了一起，而把不需要的东西做了一层隔离，进行隔离开来。
1.3 小结：
1.进程要分配一大部分的内存，而线程只需要分配一部分栈就可以了。
2.一个程序至少有一个进程,一个进程至少有一个线程。
3.进程是资源分配的最小单位，线程是程序执行的最小单位。
4.一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行。
2.进程间通信
2.1 进程间通信的概念
每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication）
2.2 进程间通信的7种方式
2.2.1 管道/匿名管道(pipe)
管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。
只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程);
单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。
数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。
![进程间管道通信模型]()
管道的实质：
管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，管道一端的进程顺序的将数据写入缓冲区，另一端的进程则顺序的读出数据。
该缓冲区可以看做是一个循环队列，读和写的位置都是自动增长的，不能随意改变，一个数据只能被读一次，读出来以后在缓冲区就不复存在了。
当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写。
管道的局限：
管道的主要局限性正体现在它的特点上：
只支持单向数据流；
只能用于具有亲缘关系的进程之间；
没有名字；
管道的缓冲区是有限的（管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小）；
管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等；
2.2.2 有名管道(FIFO)
匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道(FIFO)。
有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。值的注意的是，有名管道严格遵循先进先出(first in first out),对匿名管道及有名管道的读总是从开始处返回数据，对它们的写则把数据添加到末尾。它们不支持诸如lseek()等文件定位操作。有名管道的名字存在于文件系统中，内容存放在内存中。
匿名管道和有名管道总结：
（1）管道是特殊类型的文件，在满足先入先出的原则条件下可以进行读写，但不能进行定位读写。
（2）匿名管道是单向的，只能在有亲缘关系的进程间通信；有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
（3）无名管道阻塞问题：无名管道无需显示打开，创建时直接返回文件描述符，在读写时需要确定对方的存在，否则将退出。如果当前进程向无名管道的一端写数据，必须确定另一端有某一进程。如果写入无名管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞，如果管道发现另一端断开，将自动退出。
（4）有名管道阻塞问题：有名管道在打开时需要确实对方的存在，否则将阻塞。即以读方式打开某管道，在此之前必须一个进程以写方式打开管道，否则阻塞。此外，可以以读写（O_RDWR）模式打开有名管道，即当前进程读，当前进程写，不会阻塞。
2.2.3 信号(Signal)
信号是Linux系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。
如果该进程当前并未处于执行状态，则该信号就有内核保存起来，知道该进程回复执行并传递给它为止。
如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消是才被传递给进程。
Linux系统中常用信号：
（1）SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
（2）SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。
（3）SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\\键将产生该信号。
（4）SIGBUS和SIGSEGV：进程访问非法地址。
（5）SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。
（6）SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。
（7）SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。
（8）SIGALRM：定时器信号。
（9）SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。
信号来源
信号是软件层次上对中断机制的一种模拟，是一种异步通信方式，，信号可以在用户空间进程和内核之间直接交互，内核可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：
- 硬件来源：用户按键输入
Ctrl+C退出、硬件异常如无效的存储访问等。 - 软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号。
信号生命周期和处理流程
（1）信号被某个进程产生，并设置此信号传递的对象（一般为对应进程的pid），然后传递给操作系统；
（2）操作系统根据接收进程的设置（是否阻塞）而选择性的发送给接收者，如果接收者阻塞该信号（且该信号是可以阻塞的），操作系统将暂时保留该信号，而不传递，直到该进程解除了对此信号的阻塞（如果对应进程已经退出，则丢弃此信号），如果对应进程没有阻塞，操作系统将传递此信号。
（3）目的进程接收到此信号后，将根据当前进程对此信号设置的预处理方式，暂时终止当前代码的执行，保护上下文（主要包括临时寄存器数据，当前程序位置以及当前CPU的状态）、转而执行中断服务程序，执行完成后在回复到中断的位置。当然，对于抢占式内核，在中断返回时还将引发新的调度。
2.2.4 消息(Message)队列
消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。
与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。
另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达。延伸阅读：消息队列C语言的实践
消息队列特点总结：
（1）消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识.
（2）消息队列允许一个或多个进程向它写入与读取消息.
（3）管道和消息队列的通信数据都是先进先出的原则。
（4）消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比FIFO更有优势。
（5）消息队列克服了信号承载信息量少，管道只能承载无格式字 节流以及缓冲区大小受限等缺。
（6）目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，系统V消息队列目前被大量使用。系统V消息队列是随内核持续的，只有在内核重起或者人工删除时，该消息队列才会被删除。2.2.5 共享内存(share memory)
使得多个进程可以可以直接读写同一块内存空间，是最快的可用IPC形式。是针对其他通信机制运行效率较低而设计的。
为了在多个进程间交换信息，内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。
由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。
延伸阅读：Linux支持的主要三种共享内存方式：mmap()系统调用、Posix共享内存，以及System V共享内存实践
![共享内存原理图]()
2.2.6 信号量(semaphore)
信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。
为了获得共享资源，进程需要执行下列操作：
（1）创建一个信号量：这要求调用者指定初始值，对于二值信号量来说，它通常是1，也可是0。
（2）等待一个信号量：该操作会测试这个信号量的值，如果小于0，就阻塞。也称为P操作。
（3）挂出一个信号量：该操作将信号量的值加1，也称为V操作。为了正确地实现信号量，信号量值的测试及减1操作应当是原子操作。为此，信号量通常是在内核中实现的。Linux环境中，有三种类型：Posix（可移植性操作系统接口）有名信号量（使用Posix IPC名字标识）、Posix基于内存的信号量（存放在共享内存区中）、System V信号量（在内核中维护）。这三种信号量都可用于进程间或线程间的同步。
![两个进程使用一个二值信号量]()
![一个进程两个线程共享基于内存的信号量]()
![两个进程所以用一个Posix有名二值信号量]()
信号量与普通整型变量的区别：
（1）信号量是非负整型变量，除了初始化之外，它只能通过两个标准原子操作：wait(semap) , signal(semap) ; 来进行访问；
（2）操作也被成为PV原语（P来源于荷兰语proberen”测试”，V来源于荷兰语verhogen”增加”，P表示通过的意思，V表示释放的意思），而普通整型变量则可以在任何语句块中被访问；
信号量与互斥量之间的区别：
（1）互斥量用于线程的互斥，信号量用于线程的同步。这是互斥量和信号量的根本区别，也就是互斥和同步之间的区别。
互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。
同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。
在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源
（2）互斥量值只能为0/1，信号量值可以为非负整数。
也就是说，一个互斥量只能用于一个资源的互斥访问，它不能实现多个资源的多线程互斥问题。信号量可以实现多个同类资源的多线程互斥和同步。当信号量为单值信号量是，也可以完成一个资源的互斥访问。
（3）互斥量的加锁和解锁必须由同一线程分别对应使用，信号量可以由一个线程释放，另一个线程得到。
2.2.7 套接字(socket)
套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。
套接字是支持TCP/IP的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。
套接字特性
套接字的特性由3个属性确定，它们分别是：域、端口号、协议类型。
（1）套接字的域
它指定套接字通信中使用的网络介质，最常见的套接字域有两种：
一是AF_INET，它指的是Internet网络。当客户使用套接字进行跨网络的连接时，它就需要用到服务器计算机的IP地址和端口来指定一台联网机器上的某个特定服务，所以在使用socket作为通信的终点，服务器应用程序必须在开始通信之前绑定一个端口，服务器在指定的端口等待客户的连接。
另一个域AF_UNIX，表示UNIX文件系统，它就是文件输入/输出，而它的地址就是文件名。
（2）套接字的端口号
每一个基于TCP/IP网络通讯的程序(进程)都被赋予了唯一的端口和端口号，端口是一个信息缓冲区，用于保留Socket中的输入/输出信息，端口号是一个16位无符号整数，范围是0-65535，以区别主机上的每一个程序（端口号就像房屋中的房间号），低于256的端口号保留给标准应用程序，比如pop3的端口号就是110，每一个套接字都组合进了IP地址、端口，这样形成的整体就可以区别每一个套接字。
（3）套接字协议类型
因特网提供三种通信机制，
一是流套接字，流套接字在域中通过TCP/IP连接实现，同时也是AF_UNIX中常用的套接字类型。流套接字提供的是一个有序、可靠、双向字节流的连接，因此发送的数据可以确保不会丢失、重复或乱序到达，而且它还有一定的出错后重新发送的机制。
二个是数据报套接字，它不需要建立连接和维持一个连接，它们在域中通常是通过UDP/IP协议实现的。它对可以发送的数据的长度有限制，数据报作为一个单独的网络消息被传输,它可能会丢失、复制或错乱到达，UDP不是一个可靠的协议，但是它的速度比较高，因为它并一需要总是要建立和维持一个连接。
三是原始套接字，原始套接字允许对较低层次的协议直接访问，比如IP、 ICMP协议，它常用于检验新的协议实现，或者访问现有服务中配置的新设备，因为RAW SOCKET可以自如地控制Windows下的多种协议，能够对网络底层的传输机制进行控制，所以可以应用原始套接字来操纵网络层和传输层应用。比如，我们可以通过RAW SOCKET来接收发向本机的ICMP、IGMP协议包，或者接收TCP/IP栈不能够处理的IP包，也可以用来发送一些自定包头或自定协议的IP包。网络监听技术很大程度上依赖于SOCKET_RAW。
原始套接字与标准套接字的区别在于：
原始套接字可以读写内核没有处理的IP数据包，而流套接字只能读取TCP协议的数据，数据报套接字只能读取UDP协议的数据。因此，如果要访问其他协议发送数据必须使用原始套接字。
套接字通信的建立
服务器端
（1）首先服务器应用程序用系统调用socket来创建一个套接字，它是系统分配给该服务器进程的类似文件描述符的资源，它不能与其他的进程共享。
（2）然后，服务器进程会给套接字起个名字，我们使用系统调用bind来给套接字命名。然后服务器进程就开始等待客户连接到这个套接字。
（3）接下来，系统调用listen来创建一个队列并将其用于存放来自客户的进入连接。
（4）最后，服务器通过系统调用accept来接受客户的连接。它会创建一个与原有的命名套接不同的新套接字，这个套接字只用于与这个特定客户端进行通信，而命名套接字（即原先的套接字）则被保留下来继续处理来自其他客户的连接（建立客户端和服务端的用于通信的流，进行通信）。
客户端
（1）客户应用程序首先调用socket来创建一个未命名的套接字，然后将服务器的命名套接字作为一个地址来调用connect与服务器建立连接。
（2）一旦连接建立，我们就可以像使用底层的文件描述符那样用套接字来实现双向数据的通信（通过流进行数据传输）。
延伸阅读 ：Java socket编程
2.3 参考引用
1. 进程间通信–管道
2. Linux进程间通信——使用共享内存
3. 进程间通信—共享内存
4. 信号量与互斥锁
5. 信号量
3.进程调度策略
3.1 先来先服务调度算法：
先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
3.2 短作业(进程)优先调度算法：
短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。
3.3 高优先权优先调度算法：
为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。
3.3.1 非抢占式优先权算法：
在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。
3.3.2 抢占式优先权调度算法：
在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i 时，就将其优先权Pi与正在执行的进程j 的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i 进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。
3.3.3 容易出现优先级倒置现象：
优先级反转是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。
3.3.4 优先级反转案例解释：
不同优先级线程对共享资源的访问的同步机制。优先级为高和低的线程tall和线程low需要访问共享资源，优先级为中等的线程mid不访问该共享资源。当low正在访问共享资源时，tall等待该共享资源的互斥锁，但是此时low被mid抢先了，导致mid运行tall阻塞。即优先级低的线程mid运行，优先级高的tall被阻塞。
3.3.5 优先级倒置解决方案：
3.3.5.1 设置优先级上限
给临界区一个高优先级，进入临界区的进程都将获得这个高优先级，如果其他试图进入临界区的进程的优先级都低于这个高优先级，那么优先级反转就不会发生。
3.3.5.2 优先级继承
当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。
这里还有一个八卦，1997年的美国的火星探测器（使用的就是vxworks)就遇到一个优先级反转问题引起的故障。简单说下，火星探测器有一个信息总线，有一个高优先级的总线任务负责总线数据的存取，访问总线都需要通过一个互斥锁（共享资源出现了）；还有一个低优先级的，运行不是很频繁的气象搜集任务，它需要对总线写数据，也就同样需要访问互斥锁；最后还有一个中优先级的通信任务，它的运行时间比较长。平常这个系统运行毫无问题，但是有一天，在气象任务获得互斥锁往总线写数据的时候，一个中断发生导致通信任务被调度就绪，通信任务抢占了低优先级的气象任务，而无巧不成书的是，此时高优先级的总线任务正在等待气象任务写完数据归还互斥锁，但是由于通信任务抢占了CPU并且运行时间比较长，导致气象任务得不到CPU时间也无法释放互斥锁，本来是高优先级的总线任务也无法执行，总线任务无法及时执行的后果被探路者认为是一个严重错误，最后就是整个系统被重启。Vxworks允许优先级继承，然而遗憾的工程师们将这个选项关闭了。
3.3.5.3 临界区禁止中断
第三种方法就是，通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。火星探路者正是由于在临界区中运行的气象任务被中断发生的通信任务所抢占才导致故障，如果有临界区的禁止中断保护，此一问题也不会发生。
3.4 高响应比优先调度算法：
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为：
在利用该算法时，每要进行调度之前，都须先做响应比的计算，这会增加系统开销。
3.5 时间片轮转法：
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。
3.6 多级反馈队列调度算法：
前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。
(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
(2)当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。
批处理系统、分时系统和实时系统中，各采用哪几种进程（作业）调度算法？
批处理系统常用调度算法：
①、先来先服务：FCFS
②、最短作业优先
③、最短剩余时间优先
④、响应比最高者优先
分时系统调度算法：
①、轮转调度
②、优先级调度
③、多级队列调度
④、彩票调度
实时系统调度算法：
①、单比率调度
②、限期调度
③、最少裕度法
4.死锁
死锁是什么，以及在并发程序中如何避免死锁一直是面试官偏爱的一个问题。
4.1 死锁
当线程A持有独占锁a，并尝试去获取独占锁b的同时，线程B持有独占锁b，并尝试获取独占锁a的情况下，就会发生AB两个线程由于互相持有对方需要的锁，而发生的阻塞现象，我们称为死锁。
下面用一个非常简单的死锁示例来帮助你理解死锁的定义。
1 | public class DeadLockDemo { |
4.2 如何避免死锁？
教科书般的回答应该是，结合“哲学家就餐”模型，分析并总结出以下死锁的原因，最后得出“避免死锁就是破坏造成死锁的，若干条件中的任意一个”的结论。
造成死锁必须达成的4个条件（原因）：
互斥条件：一个资源每次只能被一个线程使用。
请求与保持条件：一个线程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：线程已获得的资源，在未使用完之前，不能强行剥夺。
循环等待条件：若干线程之间形成一种头尾相接的循环等待资源关系。
但是，“哲学家就餐”光看名字就很讨厌，然后以上这4个条件看起来也很绕口，再加上笔者又是个懒人，所以要让我在面试时把这些“背诵”出来实在是太难了！必须要想办法把这4个条件简化一下！
于是，通过对4个造成死锁的条件进行逐条分析，我们可以得出以下4个结论。互斥条件 —> 独占锁的特点之一。
请求与保持条件 —> 独占锁的特点之一，尝试获取锁时并不会释放已经持有的锁
不剥夺条件 —> 独占锁的特点之一。
循环等待条件 —> 唯一需要记忆的造成死锁的条件。
不错！复杂的死锁条件经过简化，现在需要记忆的仅只有独占锁与第四个条件而已。
- 所以，面对如何避免死锁这个问题，我们只需要这样回答！
- 在并发程序中，避免了逻辑中出现复数个线程互相持有对方线程所需要的独占锁的的情况，就可以避免死锁。
下面我们通过“破坏”第四个死锁条件，来解决第一个小节中的死锁示例并证明我们的结论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57public class DeadLockDemo2 {
public static void main(String[] args) {
// 线程a
Thread td1 = new Thread(new Runnable() {
public void run() {
DeadLockDemo2.method1();
}
});
// 线程b
Thread td2 = new Thread(new Runnable() {
public void run() {
DeadLockDemo2.method2();
}
});
td1.start();
td2.start();
}
public static void method1() {
synchronized (String.class) {
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程a尝试获取integer.class");
synchronized (Integer.class) {
System.out.println("线程a获取到integer.class");
}
}
}
public static void method2() {
// 不再获取线程a需要的Integer.class锁。
synchronized (String.class) {
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("线程b尝试获取Integer.class");
synchronized (Integer.class) {
System.out.println("线程b获取到Integer.class");
}
}
}
}
-----------------
线程a尝试获取integer.class
线程a获取到integer.class
线程b尝试获取Integer.class
线程b获取到Integer.class在上面的例子中，由于已经不存在线程a持有线程b需要的锁，而线程b持有线程a需要的锁的逻辑了，所以Demo顺利执行完毕。
4.3 总结
是否能够简单明了的在面试中阐述清楚死锁产生的原因，并给出解决死锁的方案，可以体现程序员在面对对并发问题时思路是否清晰，对并发的基础掌握是否牢固等等。
而且在实际项目中并发模块的逻辑往往比本文的示例复杂许多，所以写并发应用之前一定要充分理解本文所总结的要点，并切记，并发程序编程在不显著影响程序性能的情况下，一定要尽可能的保守。
5.I/O 多路复用，select / poll / epoll 详解
5.1 从阻塞 I/O 到 I/O 多路复用
阻塞 I/O，是指进程发起调用后，会被挂起（阻塞），直到收到数据再返回。如果调用一直不返回，进程就会一直被挂起。因此，当使用阻塞 I/O 时，需要使用多线程来处理多个文件描述符。
多线程切换有一定的开销，因此引入非阻塞 I/O。非阻塞 I/O 不会将进程挂起，调用时会立即返回成功或错误，因此可以在一个线程里轮询多个文件描述符是否就绪。
但是非阻塞 I/O 的缺点是：每次发起系统调用，只能检查一个文件描述符是否就绪。当文件描述符很多时，系统调用的成本很高。
因此引入了 I/O 多路复用，可以通过一次系统调用，检查多个文件描述符的状态。这是 I/O 多路复用的主要优点，相比于非阻塞 I/O，在文件描述符较多的场景下，避免了频繁的用户态和内核态的切换，减少了系统调用的开销。
I/O 多路复用相当于将「遍历所有文件描述符、通过非阻塞 I/O 查看其是否就绪」的过程从用户线程移到了内核中，由内核来负责轮询。
进程可以通过 select、poll、epoll 发起 I/O 多路复用的系统调用，这些系统调用都是同步阻塞的：如果传入的多个文件描述符中，有描述符就绪，则返回就绪的描述符；否则如果所有文件描述符都未就绪，就阻塞调用进程，直到某个描述符就绪，或者阻塞时长超过设置的 timeout 后，再返回。使用非阻塞 I/O 检查每个描述符的就绪状态。
如果 timeout 参数设为 NULL，会无限阻塞直到某个描述符就绪；如果 timeout 参数设为 0，会立即返回，不阻塞。
I/O 多路复用引入了一些额外的操作和开销，性能更差。但是好处是用户可以在一个线程内同时处理多个 I/O 请求。如果不采用 I/O 多路复用，则必须通过多线程的方式，每个线程处理一个 I/O 请求。后者线程切换也是有一定的开销的。这部分内容可以查看最下文 Redis 的线程模型。
5.2 为什么 I/O 多路复用内部需要使用非阻塞 I/O
I/O 多路复用内部会遍历集合中的每个文件描述符，判断其是否就绪：
1 | for fd in read_set |
这里的 readable(fd) 就是一个非阻塞 I/O 调用。试想，如果这里使用阻塞 I/O，那么 fd 未就绪时，select 会阻塞在这个文件描述符上，无法检查下个文件描述符。
注意：这里说的是 I/O 多路复用的内部实现，而不是说，使用 I/O 多路复用就必须使用非阻塞 I/O，见下文为什么边缘触发必须使用非阻塞 I/O。
5.3 select
5.3.1 函数签名与参数
1 | int select(int nfds, |
readfds、writefds、errorfds 是三个文件描述符集合。select 会遍历每个集合的前 nfds 个描述符，分别找到可以读取、可以写入、发生错误的描述符，统称为“就绪”的描述符。然后用找到的子集替换参数中的对应集合，返回所有就绪描述符的总数。
timeout 参数表示调用 select 时的阻塞时长。如果所有文件描述符都未就绪，就阻塞调用进程，直到某个描述符就绪，或者阻塞超过设置的 timeout 后，返回。如果 timeout 参数设为 NULL，会无限阻塞直到某个描述符就绪；如果 timeout 参数设为 0，会立即返回，不阻塞。
5.3.2 什么是文件描述符 fd
文件描述符（file descriptor）是一个非负整数，从 0 开始。进程使用文件描述符来标识一个打开的文件。
系统为每一个进程维护了一个文件描述符表，表示该进程打开文件的记录表，而文件描述符实际上就是这张表的索引。当进程打开（open）或者新建（create）文件时，内核会在该进程的文件列表中新增一个表项，同时返回一个文件描述符 —— 也就是新增表项的下标。
一般来说，每个进程最多可以打开 64 个文件，fd ∈ 0~63。在不同系统上，最多允许打开的文件个数不同，Linux 2.4.22 强制规定最多不能超过 1,048,576。
这篇文章以图示的方式对文件描述符作了深入地讲解，可以进一步阅读。
5.3.3 socket 与 fd 的关系
socket 是 Unix 中的术语。socket 可以用于同一台主机的不同进程间的通信，也可以用于不同主机间的通信。一个 socket 包含地址、类型和通信协议等信息，通过 socket() 函数创建：
1 | int socket(int domain, int type, int protocol) |
返回的就是这个 socket 对应的文件描述符 fd。
可以这样理解：socket 是进程间通信规则的高层抽象，而 fd 提供的是底层的具体实现。socket 与 fd 是一一对应的。通过 socket 通信，实际上就是通过文件描述符 fd 读写文件。这也符合 Unix“一切皆文件”的哲学。
后面可以将 socket 和 fd 视为同义词。
5.3.4 fd_set 文件描述符集合
参数中的 fd_set 类型表示文件描述符的集合。
由于文件描述符 fd 是一个从 0 开始的无符号整数，所以可以使用 fd_set 的二进制每一位来表示一个文件描述符。某一位为 1，表示对应的文件描述符已就绪。比如比如设 fd_set 长度为 1 字节，则一个 fd_set 变量最大可以表示 8 个文件描述符。当 select 返回 fd_set = 00010011 时，表示文件描述符 1、2、5 已经就绪。
fd_set 的使用涉及以下几个 API：
1 |
|
5.3.5 select 使用示例
下图的代码说明：
先声明一个
fd_set类型的变量readFDs调用
FD_ZERO，将readFDs所有位置 0调用
FD_SET，将readFDs感兴趣的位置 1，表示要监听这几个文件描述符将
readFDs传给select，调用selectselect会将readFDs中就绪的位置 1，未就绪的位置 0，返回就绪的文件描述符的数量当
select返回后，调用FD_ISSET检测给定位是否为 1，表示对应文件描述符是否就绪比如进程想监听 1、2、5 这三个文件描述符，就将
readFDs设置为00010011，然后调用select。如果
fd=1、fd=2就绪，而fd=5未就绪，select会将readFDs设置为00000011并返回 2。如果每个文件描述符都未就绪，
select会阻塞timeout时长，再返回。这期间，如果readFDs监听的某个文件描述符上发生可读事件，则select会将对应位置 1，并立即返回。![15732186159520]()
5.3.6 select 的缺点
性能开销大
- 调用
select时会陷入内核，这时需要将参数中的fd_set从用户空间拷贝到内核空间 - 内核需要遍历传递进来的所有
fd_set的每一位，不管它们是否就绪
- 调用
同时能够监听的文件描述符数量太少。受限于
sizeof(fd_set)的大小，在编译内核时就确定了且无法更改。一般是 1024，不同的操作系统不相同5.4 poll
poll 和 select 几乎没有区别。poll 采用链表的方式存储文件描述符，没有最大存储数量的限制。
从性能开销上看，poll 和 select 的差别不大。
5.5 epoll
epoll 是对 select 和 poll 的改进，避免了“性能开销大”和“文件描述符数量少”两个缺点。
简而言之，epoll 有以下几个特点：
使用红黑树存储文件描述符集合
使用队列存储就绪的文件描述符
每个文件描述符只需在添加时传入一次；通过事件更改文件描述符状态
select、poll 模型都只使用一个函数，而 epoll 模型使用三个函数：
epoll_create、epoll_ctl和epoll_wait。5.5.1 epoll_create
1
int epoll_create(int size);
epoll_create会创建一个epoll实例，同时返回一个引用该实例的文件描述符。返回的文件描述符仅仅指向对应的
epoll实例，并不表示真实的磁盘文件节点。其他 API 如epoll_ctl、epoll_wait会使用这个文件描述符来操作相应的epoll实例。当创建好 epoll 句柄后，它会占用一个 fd 值，在 linux 下查看
/proc/进程id/fd/，就能够看到这个 fd。所以在使用完 epoll 后，必须调用close(epfd)关闭对应的文件描述符，否则可能导致 fd 被耗尽。当指向同一个epoll实例的所有文件描述符都被关闭后，操作系统会销毁这个epoll实例。epoll实例内部存储：监听列表：所有要监听的文件描述符，使用红黑树
就绪列表：所有就绪的文件描述符，使用链表
5.5.2 epoll_ctl
1
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
epoll_ctl会监听文件描述符fd上发生的event事件。参数说明：
epfd即epoll_create返回的文件描述符，指向一个epoll实例fd表示要监听的目标文件描述符event表示要监听的事件（可读、可写、发送错误…）op表示要对fd执行的操作，有以下几种：EPOLL_CTL_ADD：为fd添加一个监听事件eventEPOLL_CTL_MOD：Change the event event associated with the target file descriptor fd（event是一个结构体变量，这相当于变量event本身没变，但是更改了其内部字段的值）
EPOLL_CTL_DEL：删除fd的所有监听事件，这种情况下event参数没用返回值 0 或 -1，表示上述操作成功与否。
epoll_ctl会将文件描述符fd添加到epoll实例的监听列表里，同时为fd设置一个回调函数，并监听事件event。当fd上发生相应事件时，会调用回调函数，将fd添加到epoll实例的就绪队列上。5.5.3 epoll_wait
1
2int epoll_wait(int epfd, struct epoll_event *events,
int maxevents, int timeout);这是 epoll 模型的主要函数，功能相当于
select。参数说明：
epfd即epoll_create返回的文件描述符，指向一个epoll实例events是一个数组，保存就绪状态的文件描述符，其空间由调用者负责申请maxevents指定events的大小timeout类似于select中的 timeout。如果没有文件描述符就绪，即就绪队列为空，则epoll_wait会阻塞 timeout 毫秒。如果 timeout 设为 -1，则epoll_wait会一直阻塞，直到有文件描述符就绪；如果 timeout 设为 0，则epoll_wait会立即返回返回值表示
events中存储的就绪描述符个数，最大不超过maxevents。5.5.4 epoll 的优点
一开始说，epoll 是对 select 和 poll 的改进，避免了“性能开销大”和“文件描述符数量少”两个缺点。
对于“文件描述符数量少”，select 使用整型数组存储文件描述符集合，而 epoll 使用红黑树存储，数量较大。
对于“性能开销大”，
epoll_ctl中为每个文件描述符指定了回调函数，并在就绪时将其加入到就绪列表，因此 epoll 不需要像select那样遍历检测每个文件描述符，只需要判断就绪列表是否为空即可。这样，在没有描述符就绪时，epoll 能更早地让出系统资源。相当于时间复杂度从 O(n) 降为 O(1)
此外，每次调用
select时都需要向内核拷贝所有要监听的描述符集合，而 epoll 对于每个描述符，只需要在epoll_ctl传递一次，之后epoll_wait不需要再次传递。这也大大提高了效率。5.5.5 水平触发、边缘触发
select只支持水平触发，epoll支持水平触发和边缘触发。水平触发（LT，Level Trigger）：当文件描述符就绪时，会触发通知，如果用户程序没有一次性把数据读/写完，下次还会发出可读/可写信号进行通知。
边缘触发（ET，Edge Trigger）：仅当描述符从未就绪变为就绪时，通知一次，之后不会再通知。
区别：边缘触发效率更高，减少了事件被重复触发的次数，函数不会返回大量用户程序可能不需要的文件描述符。
水平触发、边缘触发的名称来源：数字电路当中的电位水平，高低电平切换瞬间的触发动作叫边缘触发，而处于高电平的触发动作叫做水平触发。
5.5.6 为什么边缘触发必须使用非阻塞 I/O？
关于这个问题的解答，强烈建议阅读这篇文章。下面是一些关键摘要：
每次通过
read系统调用读取数据时，最多只能读取缓冲区大小的字节数；如果某个文件描述符一次性收到的数据超过了缓冲区的大小，那么需要对其read多次才能全部读取完毕select可以使用阻塞 I/O通过select获取到所有可读的文件描述符后，遍历每个文件描述符，read一次数据（见上文 select 示例）这些文件描述符都是可读的，因此即使
read是阻塞 I/O，也一定可以读到数据，不会一直阻塞下去select采用水平触发模式，因此如果第一次read没有读取完全部数据，那么下次调用select时依然会返回这个文件描述符，可以再次read
select也可以使用非阻塞 I/O。当遍历某个可读文件描述符时，使用for循环调用read多次，直到读取完所有数据为止（返回EWOULDBLOCK）。这样做会多一次read调用，但可以减少调用select的次数在epoll的边缘触发模式下，只会在文件描述符的可读/可写状态发生切换时，才会收到操作系统的通知
- 因此，如果使用
epoll的边缘触发模式，在收到通知时，必须使用非阻塞 I/O，并且必须循环调用read或write多次，直到返回EWOULDBLOCK为止，然后再调用epoll_wait等待操作系统的下一次通知
- 因此，如果使用
如果没有一次性读/写完所有数据，那么在操作系统看来这个文件描述符的状态没有发生改变，将不会再发起通知，调用
epoll_wait会使得该文件描述符一直等待下去，服务端也会一直等待客户端的响应，业务流程无法走完- 这样做的好处是每次调用
epoll_wait都是有效的——保证数据全部读写完毕了，等待下次通知。在水平触发模式下，如果调用epoll_wait时数据没有读/写完毕，会直接返回，再次通知。因此边缘触发能显著减少事件被触发的次数 - 为什么
epoll的边缘触发模式不能使用阻塞 I/O？很显然，边缘触发模式需要循环读/写一个文件描述符的所有数据。如果使用阻塞 I/O，那么一定会在最后一次调用（没有数据可读/写）时阻塞，导致无法正常结束
5.6 三者对比
- 这样做的好处是每次调用
select：调用开销大（需要复制集合）；集合大小有限制；需要遍历整个集合找到就绪的描述符poll：poll 采用链表的方式存储文件描述符，没有最大存储数量的限制，其他方面和 select 没有区别epoll：调用开销小（不需要复制）；集合大小无限制；采用回调机制，不需要遍历整个集合select、poll都是在用户态维护文件描述符集合，因此每次需要将完整集合传给内核；epoll由操作系统在内核中维护文件描述符集合，因此只需要在创建的时候传入文件描述符。此外
select只支持水平触发，epoll支持边缘触发。5.7 适用场景
当连接数较多并且有很多的不活跃连接时，epoll 的效率比其它两者高很多。当连接数较少并且都十分活跃的情况下，由于 epoll 需要很多回调，因此性能可能低于其它两者。
5.8 Redis 的线程模型
Redis 是一个单线程的工作模型，使用 I/O 多路复用来处理客户端的多个连接。为什么 Redis 选择单线程也能效率这么高？
I/O 设备（如磁盘、网络）等速度远远慢于 CPU，因此引入了多线程技术。当一个线程发起 I/O 请求时，先将它挂起，切换到别的线程；当 I/O 设备就绪时，再切换回该线程。总之，多线程技术是为了充分利用 CPU 的计算资源，适用于下层存储慢速的场景。
而 redis 是纯内存操作，读写速度非常快。所有的操作都会在内存中完成，不涉及任何 I/O 操作，因此多线程频繁的上下文切换反而是一种负优化。Redis 选择基于非阻塞 I/O 的 I/O 多路复用机制，在单线程里并发处理客户端的多个连接，减少多线程带来的系统开销，同时也有更好的可维护性，方便开发和调试。
不过 redis 在最新的几个版本中也引入了多线程，目的是：