操作系统

发表于 2019-09-26 更新于 2024-07-28 阅读次数：本文字数： 77k 阅读时长 ≈ 1:10

1. 操作系统的基本概念

操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
操作系统本质上是一个运行在计算机上的软件程序，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

操作系统的内核（Kernel）

维基百科对于内核的解释：

内核（英语：Kernel，又称核心）在计算机科学中是一个用来管理软件发出的数据 I/O（输入与输出）要求的电脑程序，将这些要求转译为数据处理的指令并交由中央处理器（CPU）及电脑中其他电子组件进行处理，是现代操作系统中最基本的部分。它是为众多应用程序提供对计算机硬件的安全访问的一部分软件，这种访问是有限的，并由内核决定一个程序在什么时候对某部分硬件操作多长时间。直接对硬件操作是非常复杂的。所以内核通常提供一种硬件抽象的方法，来完成这些操作。有了这个，通过进程间通信机制及系统调用，应用进程可间接控制所需的硬件资源（特别是处理器及 IO 设备）。

早期计算机系统的设计中，还没有操作系统的内核这个概念。随着计算机系统的发展，操作系统内核的概念才渐渐明晰起来了!

简单概括两点：

操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。
操作系统的内核是连接应用程序和硬件的桥梁，决定着操作系统的性能和稳定性。

中央处理器（CPU，Central Processing Unit）

关于 CPU 简单概括三点：

CPU 是一台计算机的运算核心（Core）+控制核心（ Control Unit），可以称得上是计算机的大脑。
CPU 主要包括两个部分：控制器+运算器。
CPU 的根本任务就是执行指令，对计算机来说最终都是一串由“0”和“1”组成的序列。

CPU vs Kernel(内核)

可以简单从下面两点来区别：

操作系统的内核（Kernel）属于操作系统层面，而 CPU 属于硬件。
CPU 主要提供运算，处理各种指令的能力。内核（Kernel）主要负责系统管理比如内存管理，它屏蔽了对硬件的操作。

操作系统的基本概念

2. 操作系统的基本特性

操作系统的基本特性是并发性、共享性、虚拟性、异步性。

并发性

并行性和并发性(Concurrence)是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。（宏观并发微观串行）

并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统

操作系统通过引入进程和线程，使得程序能够并发运行。

共享性

指系统中的资源可供内存中多个并发执行的进程(线程)共同使用，相应地，把这种资源共同使用称为资源共享，或称为资源复用。目前主要实现资源共享的方式有：

互斥共享方式
同时访问方式

互斥共享方式

当一个进程 A 要访问某资源时，必须先提出请求。如果此时该资源空闲，系统便可将之分配给请求进程 A 使用。此后若再有其它进程也要访问该资源时(只要 A 未用完)，则必须等待。仅当 A 进程访问完并释放该资源后，才允许另一进程对该资源进行访问。我们把这种资源共享方式称为互斥式共享，而把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源，例如打印机。

同时访问方式

系统中还有另一类资源，允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”，在单处理机环境下往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问。典型的可供多个进程“同时”访问的资源是磁盘设备，一些用重入码编写的文件也可以被“同时”共享，即若干个用户同时访问该文件。

虚拟性

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

异步性

在多道程序环境下允许多个进程并发执行，但只有进程在获得所需的资源后方能执行。在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。进程是以人们不可预知的速度向前推进，此即进程的异步性。

3. 操作系统的基本功能

操作系统的基本功能包括进程管理、内存管理、文件管理、设备管理。

进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等
内存管理：内存分配、地址映射、内存保护与共享、虚拟内存等
文件管理：文件存储空间的管理、目录管理、文件读写管理和保护等
设备管理：完成用户I/O请求，方便用户使用各种设备，并提高设备的利用率，主要包括缓冲管理、设备管理、设备处理、虚拟设备等。

4. 什么是系统调用/用户态和系统态是？

根据进程访问资源的特点，可以把进程在系统上的运行分为两个级别：

用户态(user mode) : 用户态运行的进程或程序可以直接读取用户程序的数据。
系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

我们运行的程序基本都是运行在用户态，如果要调用操作系统提供的系统态级别的子功能，那就需要系统调用了！

也就是说在运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

这些系统调用按功能大致可分为如下几类：

设备管理。完成设备的请求或释放，以及设备启动等功能。
文件管理。完成文件的读、写、创建及删除等功能。
进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
进程通信。完成进程之间的消息传递或信号传递等功能。
内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。

用户程序、系统调用、内核和硬件之间的关系

为什么要有用户态与内核态?

在 cpu 的所有指令中，有些指令是非常危险的，如果使用不当，将会造成系统崩溃等后果。为了避免这种情况发生，cpu 将指令划分为特权级(内核态)指令和非特权级(用户态)指令。

对于那些危险的指令只允许内核及其相关模块调用，对于那些不会造成危险的指令，就允许用户应用程序调用。

内核态(核心态,特权态): 内核态是操作系统内核运行的模式。 内核态控制计算机的硬件资源，如硬件设备，文件系统等等，并为上层应用程序提供执行环境。
用户态: 用户态是用户应用程序运行的状态。 应用程序必须依托于内核态运行,因此用户态的操作权限比内核态是要低的，如磁盘，文件等，访问操作都是受限的。
系统调用: 系统调用是操作系统为应用程序提供能够访问到内核态的资源的接口。

用户态切换到内核态的几种方式

系统调用: 系统调用是用户态主动要求切换到内核态的一种方式，用户应用程序通过操作系统调用内核为上层应用程序开放的接口来执行程序。
异常: 当 cpu 在执行用户态的应用程序时，发生了某些不可知的异常。于是当前用户态的应用进程切换到处理此异常的内核的程序中去。
硬件设备的中断: 当硬件设备完成用户请求后，会向 cpu 发出相应的中断信号，这时 cpu 会暂停执行下一条即将要执行的指令，转而去执行与中断信号对应的应用程序，如果先前执行的指令是用户态下程序的指令，那么这个转换过程也是用户态到内核台的转换。

5. 程序、进程与线程和协程

程序

程序是含有指令和数据的文件，被存在磁盘或其他的数据存储设备中，也就是说程序是静态的代码。

进程

为使程序能并发执行，且为了对并发执行的程序加以描述和控制，人们引入了“进程”的概念。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程是程序的一次执行过程，是系统运行程序的基本单位，因此进程是动态的。系统运行一个程序即是一个进程从创建，运行到消亡的过程。简单来说，一个进程就是一个执行中的程序，它在计算机中一个指令接着一个指令地执行着，同时，每个进程还占有某些系统资源如 CPU 时间，内存空间，文件，输入输出设备的使用权等等。换句话说，当程序在执行时，将会被操作系统载入内存中。

结构特征：通常程序是不能并发执行的。为使程序(含数据)能独立运行，应为之配置一进程控制块，即PCB(Process Control Block)（动态特征的集中反映）；而由程序段（描述要完成的功能）、相关的数据段（操作对象及工作区）和 PCB 三部分便构成了进程实体。

PCB一般在内存中，而程序段和数据段有可能是外存调入。所谓进程的创建和撤销，都是指对PCB的操作

线程

在操作系统中引入线程，是为了减少程序在并发执行时所付出的时空开销，使 OS 具有更好的并发性。适用于多CPU和网络操作系统。

线程与进程相似。但是线程是一个比进程更小的执行单位。一个进程在其执行的过程中可以产生多个线程。与线程不同的的是同类的多个线程共享同一块内存空间和一组系统资源（共享进程的堆和方法区资源），但是每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间切换工作时，负担要比进程小。

线程是进程划分成的更小的运行单位。线程和进程最大的不同在于基本上各进程是独立的，而各线程则不一定，因为同一进程中的线程极有可能会相互影响。从另一角度来说，进程属于操作系统的范畴，主要是同一段时间内，可以同时执行一个以上的程序，而线程则是在同一程序内几乎同时执行一个以上的程序段。线程执行开销小，但不利于资源的管理和保护；而进程正相反。

进程是可拥有资源的独立单位和可独立调度和分派的基本单位，在创建、撤销消和切换中，系统必须为之付出较大的时空开销。

线程具有许多传统进程所具有的特征，所以又称为轻型进程(Light-Weight Process)或进程元，相应地把传统进程称为重型进程(Heavy-Weight Process)，传统进程相当于只有一个线程的任务。

线程的属性

轻型实体，线程中的实体基本上不拥有系统资源
独立调度和分派的基本单位，线程的切换非常迅速，开销小
可并发执行（指一个进程内可以有多个线程，一个进程的线程可以与其他进程内的线程并发）
线程可以共享进程资源

区别

拥有资源：进程是资源分配的基本单位，但是线程不拥有资源，可以访问隶属进程的资源
调度：线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
通信方面：线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC

在 Java 中，一个进程中可以有多个线程，多个线程共享进程的堆和方法区资源（JDK1.8之后使用元空间），但是每个线程有自己的程序计数器，虚拟机栈和本地方法栈。

堆和方法区是所有线程共享的资源，其中堆是进程中最大的一块内存，主要用于存放新创建的对象 (所有对象都在这里分配内存)，方法区主要用于存放已被加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。

线程是进程划分成更小的运行单位。线程和进程最大的不同在于基本上各个进程都是独立的，而线程则不一定。同一进程中的不同线程极有可能相互影响。线程执行开销小，但不利于资源的管理和保护；进程则相反。

协程

协程本质上是一种用户态的轻量级线程，协程的调度完全由用户控制。

传统意思上来说，线程分为内核态线程和用户态线程，用户态线程需要绑定内核态线程，CPU并不能感知用户态线程的存在，它只知道它在运行1个线程，这个线程实际是内核态线程。用户态线程实际有个名字就叫协程（co-routine），为了容易区分，使用协程指用户态线程，使用线程指内核态线程。

协程跟线程是有区别的，线程由 CPU 调度是抢占式的，协程由用户态调度是协作式的，一个协程让出CPU后，才执行下一个协程。

协程和线程有3种映射关系：

N:1，N个协程绑定1个线程，优点就是协程在用户态线程即完成切换，不会陷入到内核态，这种切换非常的轻量快速。但也有很大的缺点，1个进程的所有协程都绑定在1个线程上，一是某个程序用不了硬件的多核加速能力，二是一旦某协程阻塞，造成线程阻塞，本进程的其他协程都无法执行了，根本就没有并发的能力了。
1:1，1个协程绑定1个线程，这种最容易实现。协程的调度都由CPU完成了，不存在N:1缺点，但有一个缺点是协程的创建、删除和切换的代价都由CPU完成，有点略显昂贵了。
M:N，M个协程绑定1个线程，是N:1和1:1类型的结合，克服了以上2种模型的缺点，但实现起来最为复杂。

协程是个好东西，不少语言支持了协程，比如：Lua、Erlang、Java（C++即将支持），就算语言不支持，也有库支持协程，比如C语言的coroutine（风云大牛作品）、Kotlin的kotlinx.coroutines、Python的gevent。

协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

协程是属于线程的。协程程序是在线程里面跑的，因此协程又称微线程和纤程等
协程没有线程的上下文切换消耗。协程的调度切换是用户(程序员)手动切换的，因此更加灵活,因此又叫用户空间线程.
原子操作性。由于协程是用户调度的，所以不会出现执行一半的代码片段被强制中断了，因此无需原子操作锁

协程的优点：

跨平台
跨体系架构
无需线程上下文切换的开销
无需原子操作锁定及同步的开销
方便切换控制流，简化编程模型
高并发+高扩展性+低成本：一个 CPU 支持上万的协程都不是问题。所以很适合用于高并发处理。

缺点：

无法利用多核资源：协程的本质是个单线程，它不能同时将单个 CPU 的多个核用上，协程需要和进程配合才能运行在多 CPU 上。当然我们日常所编写的绝大部分应用都没有这个必要，除非是 cpu 密集型应用。
进行阻塞（Blocking）操作（如IO时）会阻塞掉整个程序：这一点和事件驱动一样，可以使用异步IO操作来解决

6. 进程状态的切换

进程的三种基本状态

就绪状态：当进程已分配到除 CPU 以外的所有必要资源后，只要再获得 CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
执行状态：进程已获得 CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。
阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求 I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。

进程状态切换

只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

7. 进程同步

进程/线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。

临界资源

一次仅允许一个进程使用的共享资源，如打印机、磁带机、表格等

临界区

在每个进程中访问临界资源的那段程序（指的是软件），进程必须互斥进入临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查，看它是否正被访问。如果此刻该临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。进程中除上述进入区、临界区及退出区之外的其它部分的代码，在这里都称为剩余区。

repeat 
       entry section  # 检查临界资源是否能访问
       critical section； 
       exit section 
       remainder section； # 把临界区标志设为未访问
until false；

同步和互斥

在多道程序环境下，当程序并发执行时，由于资源共享和进程合作，使同处于一个系统中的诸进程之间可能存在着以下两种形式的制约关系。

间接相互制约：同处于一个系统中的进程，通常都共享着某种系统资源，而形成的相互制约。这种关系又叫互斥关系。

互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系
直接相互制约：这种制约主要源于进程间的合作。这种关系又叫同步关系

同步是进程间共同完成一项任务时直接发生相互作用的关系

信号量机制

信号量是一种数据结构，用于控制进程停止或执行。信号量的值表示相应资源的使用情况，它的值由P、V操作决定。

整形信号量

整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) (原语）wait(S)和 signal(S) 来访问。很长时间以来，这两个操作一直被分别称为 P、V操作。

# Wait(S)原语：
wait(S)： 
    while S<=0 do no-op；
    S:=S-1；

# Signal(S)原语：
signal(S)： S:=S+1；

wait(S)和 signal(S)是两个原子操作，因此，它们在执行时是不可中断的。亦即，当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在 wait 操作中，对 S 值的测试和做 S:=S-1 操作时都不可中断。

缺点：在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。

记录型信号量

记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针 L，用于链接上述的所有等待进程。

记录型信号量采用了记录型的数据结构，包含两个数据项，如下：

typedef struct {
      int value;//资源信号量，表示某类资源可用数目
      struct process_control_block *list; //pcb链表，阻塞队列
}semaphore;

S.value大于0时，表示资源的可用数目；S.value小于0时，代表等待使用资源的进程个数（阻塞的进程数量）

此时wait(S)和signal(S)操作如下：

//申请一个单位资源
wait(semaphore *S){
      S->value--;
      if(S->value<0) block(S->list);
}

//释放一个单位资源
signal(semaphore *S){
      S->value++;
      if(S->value<=0) wakeup(S->list); //表示还有等待该资源的进程被阻塞，将阻塞的进程进入就绪状态
}

如果 S.value 的初值为 1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

缺点：当一个进程需要获得两个或更多个共享资源后才能完成其任务，此时有两个进程A和B，都需要访问共享资源D和E（都设置了互斥信号量），其中A访问了D，B访问了E，此时A进入阻塞等待E，而B进入阻塞等待D，两者都还没有释放资源，又相互等待，就进入死锁状态

AND型信号量

其基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。

因此，AND型信号量在wait操作中增加了一个“AND”条件，称为AND同步，或者称为同时wait操作，即Swait(Simultaneous wait)。

Swait(S1,S2,...,Sn)
{
      while(TRUE){
          if(Si>1 && ... && Sn>=1){
              for(i=1;i<=n;i++)Si--;
              break;
          }
          else{
               //将进程放在与Si<1的第一个Si相关联的等待队列中，并将此进程的程序计数设置为Swait操作的开头
          }
      }
}

Ssignal(S1,S2,...,Sn){
      while(TRUE){
          for(i=1;i<=n;i++){
              Si++;
              //将与Si关联的队列中等待的所有进程移动到就绪队列中
          }
      }
}

使用信号量实现生产者——消费者问题

生产者—消费者问题是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，计算进程是生产者，而打印进程是消费者。

一组生产者进程生产产品给一组消费者进程消费。为使它们并发执行，设一个有n个缓冲区的缓冲池，生产者一次向一个缓冲区中投入消息；消费者从一个缓冲区中取得消息。生产者-消费者问题实际上是相互合作进程关系的一种抽象。
制约关系：

不允许消费者进程到一个空缓冲区中取产品
不允许生产者进程到一个已满且还没被取走的缓冲区中投放产品

假定在生产者和消费者之间的公用缓冲池中，具有 n 个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的个数。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

int in=0;//放入数据的地址（buffer数组的下标）
int out=0;//取出数据的地址
item buffer[n];//缓冲区，用于存放由生产者生产的数据信息
semaphore mutex=1;//互斥信号量
semaphore empty=n;//信号量：空缓冲区的数量，初始时都是空，所以n个
semaphore full=0;//信号量：满缓冲区的数量，初始时没有满的，所以0个

//生产者
void proceducer(){
      do{
            生产一个数据;
         	...;
            wait(empty);//申请一个缓冲区，空缓冲区减一
            wait(mutex);//判断有没有其他进程正在使用
            
            //临界区
            buffer[in]=nextp;//将产品放入缓冲区
            in:=(in+1)%n;//n+1
            
            signal(mutex);
            signal(full);//满缓冲区个数加一
      }while(TRUE);
}

//消费者
void consumer(){
      do{
          wait(full);//判断是否有满缓冲区
          wait(mutex);//判断是否有其他进程在使用
          
          //临界区
          nextc=buffer[out];
          out=(out+1)%n;//out+1
          
          signal(mutex);
          signal(empty);
          
          剩余区消费过程;
      }while(TRUE);
}

每个程序中互斥的wait(mutex)和signal(mutex)必须成对出现，而empty和full的P，V操作也是成对出现，但是处于在不同的程序中。同时注意P操作的顺序不能颠倒,不能先执行wait(mutex)再执行wait(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行wait(empty)操作，发现empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行singnal(empty)操作，empty永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

8. 管程

代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块称为管程。

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了条件变量以及相关的操作:wait()和signal()来实现同步操作。对条件变量执行wait()操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal()操作用于唤醒被阻塞的进程。

monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

9. 经典同步问题

读者——写者问题

一个数据文件或记录，可被多个进程共享，我们把只要求读该文件的进程称为Reader进程，其他进程则称为Writer进程。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象，因为这种访问将会引起混乱。所谓“读者—写者问题(Reader-Writer Problem)”是指保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。读者—写者问题常被用来测试新同步原语。共享对象不是临界资源

为实现 Reader 与 Writer 进程间在读或写时的互斥而设置了一个互斥信号量 Wmutex，再设置一个整型变量Readcount表示正在读的进程数目。Readcount是一个可被多个Reader进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。
仅当Readcount=0，表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若Wait(Wmutex)操作成功,Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcount减 1 操作后其值为 0 时，才须执行signal(Wmutex)操作，以便让Writer进程写。

sempaphore rmutex=1,wmutex=1;
int readcount=0;
void reader(){
      do{
      	  wait(rmutex);
          if(readcount==0) wait(wmutex);
          readcount++;
          signal(rmutex);
          ...
          wait(rmutex);
          readcount--;
          if(readcount==0) signal(wmutex);
          signal(rmutex);
      }while(TRUE);
}

void writer(){
      do{
      	  wait(wmutex);
          ...
          signal(wmutex);
      }while(TRUE);
}

哲学家进餐问题

该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组，所有信号量均被初始化为1

semaphore chopstick[5]={1,1,1,1,1};

//第i位哲学家的活动
do{
      wait(chopstick[i]);//先拿起左边的筷子
      wait(chopstick[(i+1)%5]);//再拿右边的筷子
      ...
      //eat
      ...
      signal(chopstick[i]);
      signal(chopstick[(i+1)%5]);
      ...
      //think
      ...
}while[TRUE];

上面的代码存在死锁的情况：假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为 0,当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。解决方法有：

至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是 1、2 号哲学家竞争 1 号筷子；3、4 号哲学家竞争 3 号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

利用AND型信号量解决哲学家进餐问题

semaphore chopstick[5]={1,1,1,1,1};

do{
      ...;
      //think;
      ...
      Sswait(chopstick[(i+1)%5],chopstick[i]);
      ...
      //eat
      ...
      Ssignal(chopstick[(i+1)%5],chopstick[i]);
}while[TRUE];

10. 进程通信

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication)

进程间通信模型

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

进程通信是指进程之间的信息交换。根据进程交换信息量的多少，可以分为低级通信和高级通信。

低级通信：进程的互斥和同步
高级通信：指用户可直接利用OS提供的一组通信命令，高效地传送大量数据的一种通信方式，对用户透明。

进程通信的分类

共享存储器系统
管道通信系统
消息传递系统
客户机-服务器系统

共享存储器系统

相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。

共享数据结构的通信方式：进程之间通过某种数据结构，如缓冲池进行通信，这种方式仅适用于传递相对少量的数据，通信效率低下，属于低级通信方式。
共享存储区通信方式：为了传递大量信息，在存储器中划出一块共享存储区，进程可通过对共享存储区进行读或写来实现通信，属于高级通信方式。

使得多个进程可以可以直接读写同一块内存空间，是最快的形式。是针对其他通信机制运行效率较低而设计的。

为了在多个进程间交换信息，内核专门留出了一块内存区，可以由需要访问的进程将其映射到自己的私有地址空间。进程就可以直接读写这一块内存而不需要进行数据的拷贝，从而大大提高效率。

由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。

共享内存原理

消息传递系统

进程间的数据交换以格式化的消息(message)为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令（原语），在进程间进行消息传递；在计算机网络中，又把 message 称为报文。属于高级通信方式，根据实现方式不同，可分为以下两种：

直接通信方式

发送进程利用OS所提供的发送原语（Send,Receive)(如 Linux 系统中的信号（signal）),直接把消息发送给目标进程。发送进程和接收进程都以显式方式分别提供对方的标识符。

Send(Receiver,message);
Receive(Sender,message);

信号（signal）
信号是 Linux 系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。

如果该进程当前并未处于执行状态，则该信号就由内核保存起来，直到该进程回复执行并传递给它为止。
如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消是才被传递给进程。

Linux系统中常用信号：

SIGHUP：用户从终端注销，所有已启动进程都将收到该进程。系统缺省状态下对该信号的处理是终止进程。
SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。
SIGQUIT：程序退出信号。程序运行过程中，按Ctrl+\键将产生该信号。
SIGBUS和SIGSEGV：进程访问非法地址。
SIGFPE：运算中出现致命错误，如除零操作、数据溢出等。
SIGKILL：用户终止进程执行信号。shell下执行kill -9发送该信号。
SIGTERM：结束进程信号。shell下执行kill 进程pid发送该信号。
SIGALRM：定时器信号。
SIGCLD：子进程退出信号。如果其父进程没有忽略该信号也没有处理该信号，则子进程退出后将形成僵尸进程。

信号来源

信号是软件层次上对中断机制的一种模拟，是一种异步通信方式，信号可以在用户空间进程和内核之间直接交互，内核可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：

硬件来源：用户按键输入Ctrl+C退出、硬件异常如无效的存储访问等。
软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号。

信号生命周期和处理流程

信号被某个进程产生，并设置此信号传递的对象（一般为对应进程的pid），然后传递给操作系统；
操作系统根据接收进程的设置（是否阻塞）而选择性的发送给接收者，如果接收者阻塞该信号（且该信号是可以阻塞的），操作系统将暂时保留该信号，而不传递，直到该进程解除了对此信号的阻塞（如果对应进程已经退出，则丢弃此信号），如果对应进程没有阻塞，操作系统将传递此信号。
目的进程接收到此信号后，将根据当前进程对此信号设置的预处理方式，暂时终止当前代码的执行，保护上下文（主要包括临时寄存器数据，当前程序位置以及当前CPU的状态）、转而执行中断服务程序，执行完成后在回复到中断的位置。当然，对于抢占式内核，在中断返回时还将引发新的调度。

信号的生命周期

间接通信方式

进程之间的通信需要通过某种中间实体（称为邮箱），也就是消息队列，该实体用来暂存发送进程发送给目标进程的消息；接收进程从该实体中取出对方发送给自己的消息。这种方式可以实现非实时通信。

Send(mailbox,message);
Receive(mailbox,message);

消息队列是存放在内核中的消息链表，每个消息队列由消息队列标识符表示。

与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。

另外与管道不同的是，消息队列在某个进程往一个队列写入消息之前，并不需要另外某个进程在该队列上等待消息的到达。

消息队列特点总结：

消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识.
消息队列允许一个或多个进程向它写入与读取消息.
管道和消息队列的通信数据都是先进先出的原则。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。比FIFO更有优势。
消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。
目前主要有两种类型的消息队列：POSIX消息队列以及System V消息队列，系统V消息队列目前被大量使用。系统V消息队列是随内核持续的，只有在内核重起或者人工删除时，该消息队列才会被删除。

根据邮箱的属性权限，可以分为私用邮箱，公用邮箱和共享邮箱。

私用邮箱:用户进程建立，作为该进程的一部分，拥有者有权读消息，其他用户只能发送。采用单向通信链路，进程结束时邮箱也消失。
公用邮箱:由OS创建，提供给系统中的所有核进程使用，进程既可以发送，也可以取出，采用双向通信链路的邮箱来实现，系统运行期间始终存在。
共享邮箱：由某进程创建，创建时提供共享进程（用户）的名字。邮箱的拥有者和共享者，都有权从邮箱中取走发送给自己的消息。

邮箱通信时发送进程和接收进程的关系：

一对一关系:建立一条专用的通信链路
多对一关系:服务进程与多个用户进程之间进行交互，又称客户/服务器交互。
一对多关系:一个发送进程与多个进程进程交互，使发送进程可用广播形式，向接收者发送消息。
多对多关系：建立一个公用邮箱，多个进程投递并取走自己的消息。

管道通信系统（匿名管道）

管道通信方式建立在文件系统的基础上，利用共享文件来连接两个相互通信的进程，此共享文件称为管道（Pipe）。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。

管道通信必须的协调能力：

互斥，即当一个进程正在对 pipe 执行读/写操作时，其它(另一)进程必须等待。
同步，指当写(输入)进程把一定数量(如 4 KB)的数据写入 pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把它唤醒。当读进程读一空 pipe 时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
确定对方是否存在，只有确定了对方已存在时，才能进行通信。

管道是通过调用pipe函数创建的，fd[0]用于读，fd[1]用于写。

#include <unistd.h>
int pipe(int fd[2]);

它具有以下特点：

只支持半双工通信，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。（单向交替传输）；
只能用于父子进程或者兄弟进程之间(具有亲缘关系的进程);
单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在与内存中。
数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

进程间管道通信的模型

管道的实质：

管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据，管道一端的进程顺序的将数据写入缓冲区，另一端的进程则顺序的读出数据。

该缓冲区可以看做是一个循环队列，读和写的位置都是自动增长的，不能随意改变，一个数据只能被读一次，读出来以后在缓冲区就不复存在了。

当缓冲区读空或者写满时，有一定的规则控制相应的读进程或者写进程进入等待队列，当空的缓冲区有新数据写入或者满的缓冲区有数据读出来时，就唤醒等待队列中的进程继续读写。

管道的局限：

管道的主要局限性正体现在它的特点上：

只支持单向数据流；
只能用于具有亲缘关系的进程之间；
没有名字；
管道的缓冲区是有限的（管道制存在于内存中，在管道创建时，为缓冲区分配一个页面大小）；
管道所传送的是无格式字节流，这就要求管道的读出方和写入方必须事先约定好数据的格式，比如多少字节算作一个消息（或命令、或记录）等等；

有名管道(FIFO)

匿名管道，由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道(Names Pipes)。

有名管道不同于匿名管道之处在于它提供了一个路径名与之关联，以有名管道的文件形式存在于文件系统中，这样，即使与有名管道的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过有名管道相互通信，因此，通过有名管道不相关的进程也能交换数据。值的注意的是，有名管道严格遵循先进先出(first in first out),对匿名管道及有名管道的读总是从开始处返回数据，对它们的写则把数据添加到末尾。有名管道的名字存在于文件系统中，内容存放在内存中。

匿名管道和有名管道对比：

管道是特殊类型的文件，在满足先入先出的原则条件下可以进行读写，但不能进行定位读写。
匿名管道是单向的，只能在有亲缘关系的进程间通信；有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
无名管道阻塞问题：无名管道无需显示打开，创建时直接返回文件描述符，在读写时需要确定对方的存在，否则将退出。如果当前进程向无名管道的一端写数据，必须确定另一端有某一进程。如果写入无名管道的数据超过其最大值，写操作将阻塞，如果管道中没有数据，读操作将阻塞，如果管道发现另一端断开，将自动退出。
有名管道阻塞问题：有名管道在打开时需要确实对方的存在，否则将阻塞。即以读方式打开某管道，在此之前必须一个进程以写方式打开管道，否则阻塞。此外，可以以读写（O_RDWR）模式打开有名管道，即当前进程读，当前进程写，不会阻塞。

客户机——服务器系统（套接字(socket)）

套接字是一种通信机制，凭借这种机制，客户/服务器（即要进行通信的进程）系统的开发工作既可以在本地单机上进行，也可以跨网络进行。也就是说它可以让不在同一台计算机但通过网络连接计算机上的进程进行通信。

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 协议的数据。因此，如果要访问其他协议发送数据必须使用原始套接字。

套接字通信的建立

Socket通信基本流程

服务器端：

首先服务器应用程序用系统调用socket来创建一个套接字，它是系统分配给该服务器进程的类似文件描述符的资源，它不能与其他的进程共享。
然后，服务器进程会给套接字起个名字，我们使用系统调用bind来给套接字命名。然后服务器进程就开始等待客户连接到这个套接字。
接下来，系统调用listen来创建一个队列并将其用于存放来自客户的进入连接。
最后，服务器通过系统调用accept来接受客户的连接。它会创建一个与原有的命名套接不同的新套接字，这个套接字只用于与这个特定客户端进行通信，而命名套接字（即原先的套接字）则被保留下来继续处理来自其他客户的连接（建立客户端和服务端的用于通信的流，进行通信）。

客户端：

客户应用程序首先调用socket来创建一个未命名的套接字，然后将服务器的命名套接字作为一个地址来调用connect与服务器建立连接。
一旦连接建立，我们就可以像使用底层的文件描述符那样用套接字来实现双向数据的通信（通过流进行数据传输）。

11. 进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法的目的是保证吞吐量和周转时间（从提交到终止的时间）

先来先服务调度算法（FCFS）

对于作业调度，每次调度从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列；对于进程调度，每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。

FCFS算法对长作业有利，不利于短作业。
有利于CPU繁忙型作业，不利于I/O繁忙型作业。

短作业（进程）优先调度算法（SJF）

短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。

SJ(P)F 调度算法能有效地降低作业的平均等待时间，提高系统吞吐量。
该算法对长作业不利
该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。

最短剩余时间优先（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

时间片轮转

在分时系统中，为保证能及时响应用户的请求，必须采用基于时间片的轮转式进程调度算法。系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。

时间片轮转算法的效率和时间片的大小有很大关系，因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。

优先级调度

为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

多级反馈队列调度算法

是目前公认的一种较好的进程调度算法。具体过程如下：

设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。
当一个新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按 FCFS 原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第 n 队列后，在第 n 队列中便采取按时间片轮转的方式运行。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第 1～(i-1)队列均空时，才会调度第 i 队列中的进程运行。如果处理机正在第 i 队列中为某进程服务时，又有新进程进入优先权较高的队列(第 1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第 i 队列的末尾，把处理机分配给新到的高优先权进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

12. 死锁产生的必要条件

互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，…，Pn}中的 P0正在等待一个 P1占用的资源； P1正在等待 P2占用的资源，……，Pn正在等待已被P0占用的资源。

13. 处理死锁的基本方法

主要有以下五种方法：

鸵鸟策略
预防死锁：该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而可能会导致系统资源利用率和系统吞吐量降低。
避免死锁：是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但实现难度较高。
检测死锁：是允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，采取适当措施，从系统中将已发生的死锁清除掉。
解除死锁：与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

预防死锁

预防死锁的方法是使四个必要条件中的第 2、3、4 个条件之一不能成立，来避免发生死锁。至于必要条件 1，因为它是由设备的固有特性所决定的，不仅不能改变，还应加以保证。

摒弃“请求和保持”条件

在采用这种方法时，系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。

优点：简单、易于实现且很安全
缺点：资源严重浪费，恶化了系统资源的利用率；造成使进程延迟运行

摒弃不剥夺条件

在采用这种方法时系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不剥夺”条件。

缺点：实现起来比较复杂且要付出很大的代价。一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。此外，这种策略还可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

摒弃“环路等待”条件

这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。

缺点：是为系统中各类资源所分配(确定)的序号必须相对稳定，这就限制了新类型设备的增加；作业(进程)使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费；这种按规定次序申请的方法，必然会限制用户简单、自主地编程。

避免死锁

所谓安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序列为安全序列)，来为每个进程 Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。
并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。

安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

预防死锁和避免死锁这两种方法实质上都是通过施加某些限制条件，来预防发生死锁。两者的主要差别在于：为预防死锁所施加的限制条件较严格，这往往会影响进程的并发执行；而为避免死锁所施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。

利用银行家算法避免死锁

银行家算法中的数据结构

可利用资源向量Available：是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j]=K，则表示系统中现有Rj类资源K个。
最大需求矩阵Max：是一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果 Max[i,j]=K，则表示进程 i 需要Rj类资源的最大数目为 K。
分配矩阵Allocation：是一个 n×m 的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,j]=K，则表示进程 i 当前已分得Rj类资源的数目为 K。
需求矩阵Need：是一个 n×m 的矩阵，用以表示每一个进程尚需的各类资源数。如果 Need[i,j]=K，则表示进程 i 还需要Rj类资源 K 个，方能完成其任务。

Need[i, j]=Max[i, j]-Allocation[i, j]

银行家算法

设Request i是进程 Pi 的请求向量，如果Request i[j]=K，表示进程Pi需要 K 个 R j类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

如果Request i[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
系统试探着把资源分配给进程 P i，并修改下面数据结构中的数值：

Available[j]= Available[j]-Request i[j];
Allocation[i,j] = Allocation[i,j]+Request i[j];
Need[i,j] = Need[i,j]-Request i[j];

系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi等待。

安全性算法

系统所执行的安全性算法可描述如下：

设置两个向量：

工作向量work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available。
Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。

从进程集合中找到一个能满足下述条件的进程：

Finish[i]=false;
Need[i,j]≤Work[j];若找到，执行步骤3，否则，执行步骤4。

当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j] = Work[j]+Allocation[i,j];
Finish[i] = true;
go to step 2;

如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

检测死锁

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

每种类型一个资源的死锁检测

资源分配图

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

每种类型多个资源的死锁检测

多个资源的死锁检测

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
如果没有这样一个进程，算法终止。

死锁解除

当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是：

剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。

14. 什么是虚拟内存

维基百科中有几句话是这样介绍虚拟内存的：

虚拟内存 使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如 RAM）的使用也更有效率。目前，大多数操作系统都使用了虚拟内存，如 Windows 家族的“虚拟内存”；Linux 的“交换空间”等。

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

通过虚拟内存可以让程序可以拥有超过系统物理内存大小的可用内存空间。另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。

虚拟内存是计算机系统内存管理的一种技术，我们可以手动设置自己电脑的虚拟内存。不要单纯认为虚拟内存只是“使用硬盘空间来扩展内存“的技术。虚拟内存的重要意义是它定义了一个连续的虚拟地址空间，并且把内存扩展到硬盘空间。

虚拟内存主要提供了如下三个重要的能力：

它把主存看作为一个存储在硬盘上的虚拟地址空间的高速缓存，并且只在主存中缓存活动区域（按需缓存）。
它为每个进程提供了一个一致的地址空间，从而降低了程序员对内存管理的复杂性。
它还保护了每个进程的地址空间不会被其他进程破坏。

虚拟（逻辑）地址和逻辑地址

编程一般只有可能和逻辑地址打交道，比如在 C 语言中，指针里面存储的数值就可以理解成为内存里的一个地址，这个地址也就是我们说的逻辑地址，逻辑地址由操作系统决定。物理地址指的是真实物理内存中地址，更具体一点来说就是内存地址寄存器中的地址。物理地址是内存单元真正的地址。

进程可用的虚拟地址范围称为该进程的虚拟地址空间。每个用户模式进程都有其自己的专用虚拟地址空间。对于32位进程，虚拟地址空间通常为2 GB范围 0x00000000 至 0x7FFFFFFF。对于64位 Windows 上的 64 位进程，虚拟地址空间为128 TB范围 0x000'00000000 到 0x7FFF'FFFFFFFF。

该图说明了虚拟地址空间的一些关键功能。

两个进程的虚拟地址空间图

该图显示了两个64位进程的虚拟地址空间：Notepad.exe 和 MyApp.exe。每个进程都有自己的虚拟地址空间，该地址空间从 0x000'0000000 到 0x7FF'FFFFFFFF。每个阴影块代表一页（4 KB大小）的虚拟或物理内存。请注意，记事本进程使用三个连续的虚拟地址页面，从 0x7F7'93950000 开始。但是，虚拟地址的这三个连续页面被映射到物理内存中的非连续页面。还要注意，两个进程都使用从 0x7F7'93950000 开始的虚拟内存页面，但是这些虚拟页面被映射到物理内存的不同页面。

为什么要有虚拟地址空间呢？

先从没有虚拟地址空间的时候说起吧！没有虚拟地址空间的时候，程序都是直接访问和操作的都是物理内存 。但是这样有什么问题呢？

用户程序可以访问任意内存，寻址内存的每个字节，这样就很容易（有意或者无意）破坏操作系统，造成操作系统崩溃。
想要同时运行多个程序特别困难，比如你想同时运行一个微信和一个 QQ 音乐都不行。为什么呢？举个简单的例子：微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就造成了微信这个程序就会崩溃。

总结来说：如果直接把物理地址暴露出来的话会带来严重问题，比如可能对操作系统造成伤害以及给同时运行多个程序造成困难。

通过虚拟地址访问内存有以下优势：

程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动。
不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

15. 虚拟内存技术的实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。 虚拟内存的实现有以下三种方式：

请求分页存储管理 ：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
请求分段存储管理 ：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。请求分段储存管理方式就如同请求分页储存管理方式一样，在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
请求段页式存储管理

请求分页与分页存储管理，两者有何不同呢？

请求分页存储管理建立在分页管理之上。他们的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因，我们在上面已经分析过了。

它们之间的根本区别在于是否将一作业的全部地址空间同时装入主存。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

不管是上面那种实现方式，我们一般都需要：

一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；
缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；
虚拟地址空间 ：逻辑地址到物理地址的变换。

16. 常见的几种内存管理机制

简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间，常见的如块式管理 。同样地，非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理和段式管理。

块式管理

远古时代的计算机操系统的内存管理方式。将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

分页系统地址映射

分段存储管理

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

分段1

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

分段2

段页式存储管理

段页式存储管理方式是程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段区别

共同点：

分页机制和分段机制都是为了提高内存利用率，较少内存碎片。
页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。

区别：

页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户的需要。
对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

17. CPU 寻址

内存通常被组织为一个由 M 个连续的字节大小的单元组成的数组，每个字节都有一个唯一的物理地址（Physical Address PA），作为到数组的索引。CPU 访问内存最简单直接的方法就是使用物理地址，这种寻址方式被称为物理寻址。

现代处理器使用的是一种称为 虚拟寻址(Virtual Addressing) 的寻址方式。使用虚拟寻址，CPU 需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。 实际上完成虚拟地址转换为物理地址转换的硬件是 CPU 中含有一个被称为 内存管理单元（Memory Management Unit, MMU） 的硬件。如下图所示：

CPU内存管理单元

虚拟寻址需要硬件与操作系统之间互相合作。CPU中含有一个被称为内存管理单元（Memory Management Unit, MMU）的硬件，它的功能是将虚拟地址转换为物理地址。MMU需要借助存放在内存中的页表来动态翻译虚拟地址，该页表由操作系统管理。

地址翻译过程

从形式上来说，地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素之间的映射。

下图为MMU利用页表进行寻址的过程：

地址翻译过程

页表基址寄存器（PTBR）指向当前页表。一个n位的虚拟地址包含两个部分，一个p位的虚拟页面偏移量（Virtual Page Offset, VPO）和一个（n - p）位的虚拟页号（Virtual Page Number, VPN）。

MMU根据VPN来选择对应的PTE，例如VPN 0代表PTE 0、VPN 1代表PTE 1….因为物理页与虚拟页的大小是一致的，所以物理页面偏移量（Physical Page Offset, PPO）与VPO是相同的。那么之后只要将PTE中的物理页号（Physical Page Number, PPN）与虚拟地址中的VPO串联起来，就能得到相应的物理地址。

多级页表的地址翻译也是如此，只不过因为有多个层次，所以VPN需要分成多段。假设有一个k级页表，虚拟地址会被分割成k个VPN和1个VPO，每个VPN i都是一个到第i级页表的索引。为了构造物理地址，MMU需要访问k个PTE才能拿到对应的PPN。

地址翻译过程2

TLB

页表是被缓存在内存中的，尽管内存的速度相对于硬盘来说已经非常快了，但与CPU还是有所差距。为了防止每次地址翻译操作都需要去访问内存，CPU使用了高速缓存与TLB来缓存PTE。

在最糟糕的情况下（不包括缺页），MMU需要访问内存取得相应的PTE，这个代价大约为几十到几百个周期，如果PTE凑巧缓存在L1高速缓存中（如果L1没有还会从L2中查找，不过我们忽略多级缓冲区的细节），那么性能开销就会下降到1个或2个周期。然而，许多系统甚至需要消除即使这样微小的开销，TLB由此而生。

TLB

TLB（Translation Lookaside Buffer, TLB）被称为翻译后备缓冲器或翻译旁路缓冲器，它是MMU中的一个缓冲区，其中每一行都保存着一个由单个PTE组成的块。用于组选择和行匹配的索引与标记字段是从VPN中提取出来的，如果TLB中有T = 2^t个组，那么TLB索引（TLBI）是由VPN的t个最低位组成的，而TLB标记（TLBT）是由VPN中剩余的位组成的。

下图为地址翻译的流程（TLB命中的情况下）：

TLB命中情况下地址翻译过程

第一步，CPU将一个虚拟地址交给MMU进行地址翻译。
第二步和第三步，MMU通过TLB取得相应的PTE。
第四步，MMU通过PTE翻译出物理地址并将它发送给高速缓存/内存。
第五步，高速缓存返回数据到CPU（如果缓存命中的话，否则还需要访问内存）。

当TLB未命中时，MMU必须从高速缓存/内存中取出相应的PTE，并将新取得的PTE存放到TLB（如果TLB已满会覆盖一个已经存在的PTE）。

TLB未命中

18. 页表，快表和多级页表

页表

虚拟内存空间被组织为一个存放在硬盘上的M个连续的字节大小的单元组成的数组，每个字节都有一个唯一的虚拟地址，作为到数组的索引（这点其实与物理内存是一样的）。

操作系统通过将虚拟内存分割为大小固定的块来作为硬盘和内存之间的传输单位，这个块被称为虚拟页（Virtual Page, VP），每个虚拟页的大小为P=2^p字节。物理内存也会按照这种方法分割为物理页（Physical Page, PP），大小也为P字节。

CPU在获得虚拟地址之后，需要通过MMU将虚拟地址翻译为物理地址。而在翻译的过程中还需要借助页表，所谓页表就是一个存放在物理内存中的数据结构，它记录了虚拟页与物理页的映射关系。

页表是一个元素为页表条目（Page Table Entry, PTE）的集合，每个虚拟页在页表中一个固定偏移量的位置上都有一个PTE。下面是PTE仅含有一个有效位标记的页表结构，该有效位代表这个虚拟页是否被缓存在物理内存中。

页表结构

虚拟页VP 0、VP 4、VP 6、VP 7被缓存在物理内存中，虚拟页VP 2和VP 5被分配在页表中，但并没有缓存在物理内存，虚拟页VP 1和VP 3还没有被分配。

在进行动态内存分配时，例如malloc()函数或者其他高级语言中的new关键字，操作系统会在硬盘中创建或申请一段虚拟内存空间，并更新到页表（分配一个PTE，使该PTE指向硬盘上这个新创建的虚拟页）。

由于CPU每次进行地址翻译的时候都需要经过PTE，所以如果想控制内存系统的访问，可以在PTE上添加一些额外的许可位（例如读写权限、内核权限等），这样只要有指令违反了这些许可条件，CPU就会触发一个一般保护故障，将控制权传递给内核中的异常处理程序。一般这种异常被称为“段错误（Segmentation Fault）”。

页命中

如上图所示，MMU根据虚拟地址在页表中寻址到了PTE 4，该PTE的有效位为1，代表该虚拟页已经被缓存在物理内存中了，最终MMU得到了PTE中的物理内存地址（指向PP 1）。

缺页

如上图所示，MMU根据虚拟地址在页表中寻址到了PTE 2，该PTE的有效位为0，代表该虚拟页并没有被缓存在物理内存中。虚拟页没有被缓存在物理内存中（缓存未命中）被称为缺页。

当CPU遇见缺页时会触发一个缺页异常，缺页异常将控制权转向操作系统内核，然后调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，如果牺牲页已被修改过，内核会先将它复制回硬盘（采用写回机制而不是直写也是为了尽量减少对硬盘的访问次数），然后再把该虚拟页覆盖到牺牲页的位置，并且更新PTE。

当缺页异常处理程序返回时，它会重新启动导致缺页的指令，该指令会把导致缺页的虚拟地址重新发送给MMU。由于现在已经成功处理了缺页异常，所以最终结果是页命中，并得到物理地址。

这种在硬盘和内存之间传送页的行为称为页面调度（paging）：页从硬盘换入内存和从内存换出到硬盘。当缺页异常发生时，才将页面换入到内存的策略称为按需页面调度（demand paging），所有现代操作系统基本都使用的是按需页面调度的策略。

虚拟内存跟CPU高速缓存（或其他使用缓存的技术）一样依赖于局部性原则。虽然处理缺页消耗的性能很多（毕竟还是要从硬盘中读取），而且程序在运行过程中引用的不同虚拟页的总数可能会超出物理内存的大小，但是局部性原则保证了在任意时刻，程序将趋向于在一个较小的活动页面（active page）集合上工作，这个集合被称为工作集（working set）。根据空间局部性原则（一个被访问过的内存地址以及其周边的内存地址都会有很大几率被再次访问）与时间局部性原则（一个被访问过的内存地址在之后会有很大几率被再次访问），只要将工作集缓存在物理内存中，接下来的地址翻译请求很大几率都在其中，从而减少了额外的硬盘流量。

如果一个程序没有良好的局部性，将会使工作集的大小不断膨胀，直至超过物理内存的大小，这时程序会产生一种叫做抖动（thrashing）的状态，页面会不断地换入换出，如此多次的读写硬盘开销，性能自然会十分“恐怖”。所以，想要编写出性能高效的程序，首先要保证程序的时间局部性与空间局部性。

快表

在分页内存管理中，很重要的两点是：

虚拟地址到物理地址的转换要快。
解决虚拟地址空间大，页表也会很大的问题。

为了解决虚拟地址到物理地址的转换速度，操作系统在页表方案基础之上引入了快表，来加速虚拟地址到物理地址的转换。我们可以把快表理解为一种特殊的高速缓冲存储器（Cache），其中的内容是页表的一部分或者全部内容。作为页表的Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

使用快表之后的地址转换流程是这样的：

根据虚拟地址中的页号查快表；
如果该页在快表中，直接从快表中读取相应的物理地址；
如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

看完了之后会发现快表和我们平时经常在我们开发的系统使用的缓存（比如 Redis）很像，的确是这样的，操作系统中的很多思想、很多经典的算法，都可以在我们日常开发使用的各种工具或者框架中找到它们的影子。

多级页表

现代的大多数计算机系统，都支持非常大的逻辑地址空间(232～264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有 32 位逻辑地址空间的分页系统，规定页面大小为 4 KB 即 2 的 12 次方，则在每个进程页表中的页表项可达 1 兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用 1 MB 的内存空间，而且还要求是连续的。显然这是不现实的，可以采用下述两个方法来解决这一问题：

采用离散分配方式来解决难以找到一块连续的大内存空间的问题；
只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

两级页表

对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。

两级页表结构

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景。

假设我们的环境为一个32位的虚拟地址空间，它有如下形式：

虚拟地址空间被分为4KB的页，每个PTE都是4字节。
内存的前2K个页面分配给了代码和数据。
之后的6K个页面还未被分配。
再接下来的1023个页面也未分配，其后的1个页面分配给了用户栈。

下图是为该虚拟地址空间构造的二级页表层次结构（真实情况中多为四级或更多），一级页表（1024个PTE正好覆盖4GB的虚拟地址空间，同时每个PTE只有4字节，这样一级页表与二级页表的大小也正好与一个页面的大小一致都为4KB）的每个PTE负责映射虚拟地址空间中一个4MB的片（chunk），每一片都由1024个连续的页面组成。二级页表中的每个PTE负责映射一个4KB的虚拟内存页面。

多级页表示例

这个结构看起来很像是一个B-Tree，这种层次结构有效的减缓了内存要求：

如果一个一级页表的一个PTE是空的，那么相应的二级页表也不会存在。这代表一种巨大的潜在节约（对于一个普通的程序来说，虚拟地址空间的大部分都会是未分配的）。
只有一级页表才总是需要缓存在内存中的，这样虚拟内存系统就可以在需要时创建、页面调入或调出二级页表（只有经常使用的二级页表才会被缓存在内存中），这就减少了内存的压力。

为了提高内存的空间性能，提出了多级页表的概念；但是提到空间性能是以浪费时间性能为基础的，因此为了补充损失的时间性能，提出了快表（即TLB）的概念。不论是快表还是多级页表实际上都利用到了程序的局部性原理。

19. 虚拟存储器

基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其他部分留在外存，就可以启动程序执行。由于外存往往比内存大很多，所以我们运行的软件的内存大小实际上是可以比计算机系统实际的内存大小大的。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换到外存上，从而腾出空间存放将要调入内存的信息。这样，计算机好像为用户提供了一个比实际内存大的多的存储器——虚拟存储器。

实际上，我觉得虚拟内存同样是一种时间换空间的策略，你用 CPU 的计算时间，页的调入调出花费的时间，换来了一个虚拟的更大的空间来支持程序的运行。不得不感叹，程序世界几乎不是时间换空间就是空间换时间。

20. 页面置换算法

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。

一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再访问的页面调出。

抖动：刚被换出的页很快又被访问，需重新调入，又需再选一页调出，如此频繁地更换页面的现象。抖动导致进程在运行中，把大部分时间花费在页面置换中。

地址映射过程中，若在页面中发现所要访问的页面不在内存中，则发生缺页中断。

缺页中断 就是要访问的页不在主存，需要操作系统将其调入主存后再进行访问。在这个时候，被内存映射的文件实际上成了一个分页交换文件。

当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。用来选择淘汰哪一页的规则叫做页面置换算法，我们可以把页面置换算法看成是淘汰页面的规则。

最佳置换算法

OPT, Optimal replacement algorithm

其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。
采用最佳置换算法，通常可保证获得最低的缺页率。但由于无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

最近最久未使用置换算法

LRU, Least Recently Used

根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。

先进先出页面置换算法

FIFO, First In First Out

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

Clock置换算法/最近未使用算法

Clock / NUR Not Recently Used

当采用简单 Clock 算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，则再返回到队首去检查第一个页面。由于该算法是循环地检查各页面的使用情况，故称为 Clock 算法。但因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法 NRU(Not Recently Used)。

最少使用（LFU）置换算法

在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。

21. 磁盘存储器的结构

磁盘设备可包括一或多个物理盘片，每个磁盘片分一个或两个存储面(surface)，每个磁盘面被组织成若干个同心环，这种环称为磁道(track)，各磁道之间留有必要的间隙。为使处理简单起见，在每条磁道上可存储相同数目的二进制位。这样，磁盘密度即每英寸中所存储的位数，显然是内层磁道的密度较外层磁道的密度高。每条磁道又被逻辑上划分成若干个扇区(sectors)，软盘大约为 8～32 个扇区，硬盘则可多达数百个。一个扇区称为一个盘块(或数据块)，常常叫做磁盘扇区。各扇区之间保留一定的间隙。

盘面（Platter）：一个磁盘有多个盘面；
磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
制动手臂（Actuator arm）：用于在磁道之间移动磁头；
主轴（Spindle）：使整个盘面转动。

磁盘结构

22. 磁盘调度算法

磁盘设备在工作时以恒定速率旋转。为了读或写，磁头必须能移动到所要求的磁道上，并等待所要求的扇区的开始位置旋转到磁头下，然后再开始读或写数据。读写一个磁盘块的时间的影响因素有：

寻道时间Ts:指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间 s 与磁头移动 n 条磁道所花费的时间之和。

// m是一个常数，与磁盘驱动器的速度有关
Ts = m x n + s

旋转延迟时间Tr：这是指定扇区移动到磁头下面所经历的时间。不同的磁盘类型中，旋转速度至少相差一个数量级，如软盘为 300 r/min，硬盘一般为7200～15 000 r/min，甚至更高。

平均旋转延迟时间Tr = 1/2r（r为磁盘每秒的转数）

传输时间Tt。这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt 的大小与每次所读/写的字节数 b 和旋转速度有关:

// r为磁盘每秒的转数
// N为一条磁道上的字节数，当一次读/写的字节数相当于半条磁道上的字节数时，Tt与 Tr相同。
Tt = b / (r x N)

综上，访问时间 Ta 可以表示为：

Ta = Ts + 1/2r + b/(rN)

磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。

先来先服务

FCFS, First Come First Served

根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

最短寻道时间优先

SSTF, Shortest Seek Time First

其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。

SSTF 算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的 I/O 请求必然优先满足。

扫描算法

SCAN

该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN 算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。这时，同样也是每次选择这样的进程来调度，即要访问的磁道在当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现象。由于在这种算法中磁头移动的规律颇似电梯的运行，因而又常称之为电梯调度算法。

23. 程序在系统中运行过程

用户程序要在系统中运行，必须先将它装入内存，然后在将其转变为一个可以执行的程序，通常都要经过以下几个步骤：

编译：由编译程序对用户源程序进行编译，形成若干个目标模块；
链接：由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块
装入：由装入程序将装入模块装入内存

编译

以下是一个 hello.c 程序：

#include <stdio.h>

int main()
{
    printf("hello, world\n");
    return 0;
}

在 Unix 系统上，由编译器把源文件转换为目标文件。

gcc -o hello hello.c

这个过程大致如下：

编译过程

预处理阶段：处理以 # 开头的预处理命令；
编译阶段：翻译成汇编文件；
汇编阶段：将汇编文件翻译成可重定位目标文件；
链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

目标文件

可执行目标文件：可以直接在内存中执行
可重定位目标文件：可与其他可重定位目标文件在链接阶段合并，创建一个可执行目标文件
共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接

链接

源程序经过编译后，可得到一组目标模块，再利用链接程序将这组目标模块链接，形成装入模块。根据链接时间的不同，可把链接分成如下三种：

静态链接
装入时动态链接
运行时动态链接

静态链接方式

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。在将几个目标模块装配成一个装入模块时，须解决以下两个问题：

静态链接方式

对相对地址进行修改。如图4-4，在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为 0，每个模块中的地址都是相对于起始地址计算的。在链接成一个装入模块后，原模块 B 和 C 在装入模块的起始地址不再是 0，而分别是 L 和 L+M，所以此时须修改模块 B 和 C 中的相对地址，即把原 B 中的所有相对地址都加上 L，把原 C 中的所有相对地址都加上 L+M。
变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如把B的起始地址变换为 L，把 C 的起始地址变换为 L+M。这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

动态链接

静态库有以下两个问题：

当静态库更新时那么整个程序都要重新进行链接；
对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：

在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。

装入时动态装入

用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照图 4-4 所示的方式来修改目标模块中的相对地址。

运行时动态装入

这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

24. 孤儿进程和僵尸进程

孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程。孤儿进程将被init进程（进程号为 1）所收养，并由init进程对它们完成状态收集工作。由于孤儿进程会被init进程收养，所以孤儿进程不会对系统造成危害。
僵尸进程：一个子进程的进程描述符在子进程退出时不会释放，只有当父进程通过wait()或waitpid()获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用wait()或waitpid()，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。僵尸进程通过 ps 命令显示出来的状态为Z（zombie）。系统所能使用的进程号是有限的，如果产生大量僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。要消灭系统中大量的僵尸进程，只需要将其父进程杀死，此时僵尸进程就会变成孤儿进程，从而被init进程所收养，这样init进程就会释放所有的僵尸进程所占有的资源，从而结束僵尸进程。

父子进程传递：

当一个子进程改变了它的状态时（停止运行，继续运行或者退出），有两件事会发生在父进程中：

得到SIGCHLD信号
waitpid()或者wait()调用会返回

其中子进程发送的 SIGCHLD 信号包含了子进程的信息，比如进程 ID、进程状态、进程使用 CPU 的时间等。

在子进程退出时，它的进程描述符不会立即释放，这是为了让父进程得到子进程信息，父进程通过wait()和waitpid()来获得一个已经退出的子进程的信息。

wait

父进程调用wait()会一直阻塞，直到收到一个子进程退出的SIGCHLD信号，之后wait()函数会销毁子进程并返回。

pid_t wait(int *status)

如果成功，返回被收集的子进程的进程 ID；如果调用进程没有子进程，调用就会失败，此时返回 -1，同时errno被置为ECHILD。

参数status用来保存被收集的子进程退出时的一些状态，如果对这个子进程是如何死掉的毫不在意，只想把这个子进程消灭掉，可以设置这个参数为NULL。

waitpid

作用和 wait() 完全相同，但是多了两个可由用户控制的参数pid和options。

pid_t waitpid(pid_t pid, int *status, int options)

pid参数指示一个子进程的 ID，表示只关心这个子进程退出的SIGCHLD信号。如果pid=-1时，那么和wait()作用相同，都是关心所有子进程退出的SIGCHLD信号。

options参数主要有WNOHANG和WUNTRACED两个选项，WNOHANG可以使waitpid()调用变成非阻塞的，也就是说它会立即返回，父进程可以继续执行其它任务。

25. 程序局部性原理

程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。

时间局部性：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

对于以下代码：

//求数组元素之和，v为数组名，n为数组大小，
int sum(int *v, int n)
{
    int i = 0;
    int sum = 0;

    for (i=0; i<n; ++i)
    {
        sum+=v[i];
    }	

    return sum;
}

由于数组的特点是在内存中是连续存放的，根据代码以及局部性定义可知：

对于循环中的 sum 变量：有良好的时间局部性。因为在 for 循环结束之前，每次执行循环体都有对 sum 的访问。而 sum 没有空间局部性。因为 sum 是标量（也就是说通过 sum 这个地址只能得到一个值）

对于循环体中的 v 变量：有良好的空间局部性。因为数组 v 是按顺序存放在内存中，每次访问 v[i] 总是在 v[i-1] 的下一个位置。而 v 没有时间局部性，因为在循环体中，每个元素 v[i] 只会被访问一次。

对于二维数组，如果有以下两种访问方式：

int a[500][500];

//先访问行
void fun_1()
{    
    int i,j;    
   
    for(i=0; i<500; i++)    
    {
    for(j=0; j<500; j++)
    {
        a[i][j]=i;
    }    
    }
}

//先访问列
void fun_2()
{    
    int i,j;  
    
    for(j=0; j<500; j++)    
    {
    for(i=0; i<500; i++)
    {
        a[i][j]=i;
    }    
    }
}

fun_1 和 fun_2 都是对一个二维数组进行遍历赋值。在 fun_1 函数的 for 循环体中，是以行序为主序对元素进行遍历。也就是说内层循环先访问第一行的元素，然后第二行……，而二维数组在存储器中也是按照行序为主序来进行存储的。也就是说先存储第一行，然后第二行……，本例中存储顺序和访问顺序一致，所以可以该程序对 a[][] 的引用有良好的空间局部性。

而 fun_2 函数只是在 fun_1 的基础上将求和函数中的双重循环的索引 i 和 j 调换一下位置，也就是说在对 a[][] 进行遍历的时候，以列序为主序。即先访问第一列，在访问第二列……，而前面讲了二维数组在存储器中也是按照行序为主序来进行存储；意味着每访问一个元素，就要跳过 N 个元素才能访问下一个。这种情况下没有良好的空间局部性。

对于同一个数组，具有空间局部性的 fun_1 函数运行的效率几乎是没有局部性的 fun_2 函数的提高了一倍，至于为什么有良好局部性的程序有更好的性能，这个和计算机的缓存是息息相关。

良好局部性程序有更好性能的原因

首先看一看计算机的存储结构：

计算机存储级结构

各类存储器的大小和访问耗时

寄存器，既是CPU的工作台，也是存放计算数据的地方。

CPU要工作，它需要数据或者地址，先从一级缓存里面找，找不到就从二级缓存里面找，依次类推。假如 CPU 到磁盘才有，那么这个数据就会存入内存，再存入三级缓存、二级缓存、一级缓存，最后存入寄存器，CPU 用它来计算了。所以说，可以这么看， L1是寄存器的缓存，L1是L2的缓存，依次这样下去，上面一层是下面一层的缓存。

从最快的 L1 Cache 到最慢的 HDD，其两者的访存时间差距达到了 6 个数量级，即便是和内存比较，也有几百倍的差距。举个例子，如果 CPU 在运算是直接从内存中读取指令和数据，执行一条指令 0.3ns，然后从内存读下一条指令，等 120ns，这样 CPU 99% 计算时间都会被浪费掉。

CPU 的工作要高速，希望 CPU 需要的数据更多的就在 L1 里面，一找就找着。不希望更多的跑到下面内存乃至磁盘里面去找，这样会花更多的时间。所以当 CPU 用了一个数据，计算机会遇见性的存入其他等会儿 CPU 可能会用到的数据到 L123 内存，用到的可能性越大，就能存到越接近寄存器的层次。这也才是缓存的真正意义。

那么，计算机怎样才能判断一个数据接下来可能被用到？

时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。正在使用的这个数据地址旁边的数据，比如数组。

26. fork 操作原理

由 fork 创建的新进程被称为子进程（child process）。该函数被调用一次，但返回两次。两次返回的区别是子进程的返回值是 0，而父进程的返回值则是新进程（子进程）的进程 id。将子进程 id 返回给父进程的理由是：因为一个进程的子进程可以多于一个，没有一个函数使一个进程可以获得其所有子进程的进程 id 。对子进程来说，之所以 fork 返回 0 给它，是因为它随时可以调用 getpid() 来获取自己的 pid；也可以调用 getppid() 来获取父进程的id。(进程 id 0总是由交换进程使用，所以一个子进程的进程 id 不可能为 0 )。

fork 之后，操作系统会复制一个与父进程完全相同的子进程，虽说是父子关系，但是在操作系统看来，他们更像兄弟关系，这 2 个进程共享代码空间，但是数据空间是互相独立的，子进程数据空间中的内容是父进程的完整拷贝，指令指针也完全相同，子进程拥有父进程当前运行到的位置（两进程的程序计数器 pc 值相同，也就是说，子进程是从 fork 返回处开始执行的），但有一点不同，如果 fork 成功，子进程中 fork 的返回值是 0，父进程中 fork 的返回值是子进程的进程号，如果 fork 不成功，父进程会返回错误。

可以这样想象，2 个进程一直同时运行，而且步调一致，在 fork 之后，他们分别作不同的工作，也就是分岔了。

27. 什么是上下文切换

多线程编程中一般线程的个数都大于CPU核心的个数，而一个CPU核心在任一时只能被一个线程使用，为了让这些线程都能得到有效执行，CPU采取的策略是为每个线程分配时间片并轮转的形式。当一个线程的时间片用完的时候，就会重新处于就绪状态让其他线程使用，这个过程就是一次上下文切换

也就是说，当前任务在执行完CPU时间片切换到另一个任务之前，会先保存自己的状态，以便下次再切换回这个任务时，可以再加载这个任务的状态。任务从保存到再次加载的过程就是一次上下文切换。

上下文切换通常是计算密集型的。也就是说，它需要相当可观的处理器时间，在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间。所以，上下文切换对系统来说意味着消耗大量的CPU时间，事实上，可能是操作系统中时间消耗最大的操作。

Linux 相比与其他操作系统（包括其他类 Unix 系统）有很多的优点，其中有一项就是，其上下文切换和模式切换的时间消耗非常少。

28. 如何让运行时 CPU 占用率为50%

在 Linux 下，CPU 利用率分为用户态，系统态和空闲态，分别表示 CPU 处于用户态执行的时间，系统内核执行的时间，和空闲系统进程执行的时间，三者之和就是 CPU 的总时间，当没有用户进程、系统进程等需要执行的时候，CPU 就执行系统缺省的空闲进程。从平常的思维方式理解的话，CPU 的利用率就是非空闲进程占用时间的比例，即 CPU 执行非空闲进程的时间 / CPU 总的执行时间。

那么问题就很简单了，只要保持让 cpu 运行 50，休息 50 就可以保证 cpu 的利用保持在 50% 了。

import java.lang.Thread;
import java.text.SimpleDateFormat;
public class cpu50 {
    public static void main(String[] args) {
        long time_start;
        int fulltime = 100;//总时间
        int runtime = 50;//运行时间
        while(true){
            time_start = System.currentTimeMillis();//获取当前时间
            while((System.currentTimeMillis()-time_start)<runtime){}
             try {
                Thread.sleep(fulltime-runtime); 
                } catch (InterruptedException e) {
                return;
            }
        }
    }
}

29. 什么是惊群效应？如何避免？

惊群效应（thundering herd）是指多进程（多线程）在同时阻塞等待同一个事件的时候（休眠状态），如果等待的这个事件发生，那么他就会唤醒等待的所有进程（或者线程），但是最终却只能有一个进程（线程）获得这个时间的“控制权”，对该事件进行处理，而其他进程（线程）获取“控制权”失败，只能重新进入休眠状态，这种现象和性能浪费就叫做惊群效应。

惊群效应消耗了什么？

Linux 内核对用户进程（线程）频繁地做无效的调度、上下文切换等使系统性能大打折扣。上下文切换（context switch）过高会导致 CPU 像个搬运工，频繁地在寄存器和运行队列之间奔波，更多的时间花在了进程（线程）切换，而不是在真正工作的进程（线程）上面。直接的消耗包括 CPU 寄存器要保存和加载（例如程序计数器）、系统调度器的代码需要执行。间接的消耗在于多核 cache 之间的共享数据。为了确保只有一个进程（线程）得到资源，需要对资源操作进行加锁保护，加大了系统的开销。目前一些常见的服务器软件有的是通过锁机制解决的，比如 Nginx（它的锁机制是默认开启的，可以关闭）；还有些认为惊群对系统性能影响不大，没有去处理，比如 Lighttpd。

解决方案

Linux 解决方案之 Accept

Linux 2.6 版本之前，监听同一个 socket 的进程会挂在同一个等待队列上，当请求到来时，会唤醒所有等待的进程。

Linux 2.6 版本之后，通过引入一个标记位 WQ_FLAG_EXCLUSIVE，保证一次只会唤醒一个进程，解决掉了 accept 惊群效应。

Nginx 锁实现方案

nginx master 进程监听端口号（例如80），所有的 nginx worker 进程开始用 epoll_wait 来处理新事件（linux下），如果不加任何保护，一个新连接来临时，会有多个 worker 进程在 epoll_wait 后被唤醒，然后发现自己 accept 失败。现在，我们可以看看 nginx 是怎么处理这个惊群问题了。

其具体思路是：不让多个进程在同一时间监听接受连接的 socket，而是让每个进程轮流监听，这样当有连接过来的时候，就只有一个进程在监听那肯定就没有惊群的问题。

Nginx 提供了一个 accept_mutex 这个东西，这是一个加在 accept 上的一把共享锁。即每个 worker 进程在执行 accept 之前都需要先获取锁，获取不到就放弃执行 accept()。有了这把锁之后，同一时刻，就只会有一个进程去 accpet()，这样就不会有惊群问题了。accept_mutex 是一个可控选项，我们可以显示地关掉，默认是打开的

具体做法是：利用一把进程间锁，每个进程中都尝试获得这把锁，如果获取成功将监听 socket 加入 wait 集合中，并设置超时等待连接到来，没有获得锁的进程则将监听 socket 从 wait 集合去除。这里只是简单讨论 nginx 在处理惊群问题基本做法，实际其代码还处理了很多细节问题，例如简单的连接的负载均衡、定时事件处理等等。

30. 中断和中断处理流程

中断概念

中断是指由于接收到来自外围硬件（相对于中央处理器和内存）的异步信号或来自软件的同步信号，而进行相应的硬件／软件处理。发出这样的信号称为进行中断请求（interrupt request，IRQ）。硬件中断导致处理器通过一个上下文切换（context switch）来保存执行状态（以程序计数器和程序状态字等寄存器信息为主）；软件中断则通常作为CPU指令集中的一个指令，以可编程的方式直接指示这种上下文切换，并将处理导向一段中断处理代码。中断在计算机多任务处理，尤其是实时系统中尤为有用。这样的系统，包括运行于其上的操作系统，也被称为“中断驱动的”（interrupt-driven）。

中断是一种使CPU中止正在执行的程序而转去处理特殊事件的操作，这些引起中断的事件称为中断源，它们可能是来自外设的输入输出请求，也可能是计算机的一些异常事故或其它内部原因。

中断的作用

并行操作
硬件故障报警与处理
支持多道程序并发运行，提高计算机系统的运行效率
支持实时处理功能

中断的分类

按中断源进行分类

发出中断请求的设备称为中断源。按中断源的不同，中断可分为

内中断：即程序运行错误引起的中断
外中断：即由外部设备、接口卡引起的中断
软件中断：由写在程序中的语句引起的中断程序的执行，称为软件中断

按CPU接不接受中断请求进行分类

CPU 通过指令限制某些设备发出中断请求，称为屏蔽中断。从 CPU 要不要接收中断即能不能限制某些中断发生的角度，中断可分为

可屏蔽中断：可被 CPU 通过指令限制某些设备发出中断请求的中断
不可屏蔽中断：不允许屏蔽的中断，如电源掉电

中断允许触发器：在 CPU 内部设置一个中断允许触发器，只有该触发器置“1”，才允许中断；置“0”，不允许中断。

指令系统中，开中断指令，使中断触发器置“1”，关中断指令，使中断触发器置“0”

中断优先级和中断嵌套

中断优先级：为了管理众多的中断请求，需要按每个（类）中断处理的急迫程度，对中断进行分级管理，称其为中断优先级。在有多个中断请求时，总是响应与处理优先级高的设备的中断请求。
中断嵌套：当 CPU 正在处理优先级较低的一个中断，又来了优先级更高的一个中断请求，则 CPU 先停止低优先级的中断处理过程，去响应优先级更高的中断请求，在优先级更高的中断处理完成之后，再继续处理低优先级的中断，这种情况称为中断嵌套。

中断和异常理解为两种中断当前程序执行的不同机制。这是中断和异常的共同点。不同点在于：

中断(interrupt)是异步的事件，典型的比如由I/O设备触发；异常(exception)是同步的事件，典型的比如处理器执行某条指令时发现出错了等等。
中断又可以分为可屏蔽中断和非可屏蔽中断，异常又分为故障、陷阱和异常中止3种
平常所说的屏蔽中断是不包括异常的，即异常不会因为CPU的IF位被清（关中断，指令：cli）而受影响，比如缺页异常，即使关了中断也会触发CPU的处理。

中断（异常）处理流程

中断处理流程

需要明确的一点是 CPU 对于中断和异常的具体处理机制本质上是完全一致的，即：当 CPU 收到中断或者异常的信号时，它会暂停执行当前的程序或任务，通过一定的机制跳转到负责处理这个信号的相关处理程序中，在完成对这个信号的处理后再跳回到刚才被打断的程序或任务中。

具体的处理过程如下：

中断响应的事前准备：

系统要想能够应对各种不同的中断信号，总的来看就是需要知道每种信号应该由哪个中断服务程序负责以及这些中断服务程序具体是如何工作的。系统只有事前对这两件事都知道得很清楚，才能正确地响应各种中断信号和异常。

系统将所有的中断信号统一进行了编号（一共256个：0～255），这个号称为中断向量，具体哪个中断向量表示哪种中断有的是规定好的，也有的是在给定范围内自行设定的。

中断向量和中断服务程序的对应关系主要是由IDT（中断向量表）负责。操作系统在 IDT 中设置好各种中断向量对应的中断描述符（一共有三类中断门描述符：任务门、中断门和陷阱门），留待 CPU 查询使用。而 IDT 本身的位置是由 idtr 保存的，当然这个地址也是由 OS 填充的。

中断服务程序具体负责处理中断（异常）的代码是由软件，也就是操作系统实现的，这部分代码属于操作系统内核代码。也就是说从 CPU 检测中断信号到加载中断服务程序以及从中断服务程序中恢复执行被暂停的程序，这个流程基本上是硬件确定下来的，而具体的中断向量和服务程序的对应关系设置和中断服务程序的内容是由操作系统确定的。

CPU检查是否有中断/异常信号

CPU 在执行完当前程序的每一条指令后，都会去确认在执行刚才的指令过程中中断控制器（如：8259A）是否发送中断请求过来，如果有那么CPU就会在相应的时钟脉冲到来时从总线上读取中断请求对应的中断向量。

对于异常和系统调用那样的软中断，因为中断向量是直接给出的，所以和通过 IRQ （中断请求）线发送的硬件中断请求不同，不会再专门去取其对应的中断向量。

根据中断向量到 IDT 表中取得处理这个向量的中断程序的段选择符

CPU 根据得到的中断向量到 IDT 表里找到该向量对应的中断描述符，中断描述符里保存着中断服务程序的段选择符。

根据取得的段选择符到 GDT 中找相应的段描述符

CPU 使用 IDT 查到的中断服务程序的段选择符从 GDT 中取得相应的段描述符，段描述符里保存了中断服务程序的段基址和属性信息，此时 CPU 就得到了中断服务程序的起始地址。这里，CPU 会根据当前 cs 寄存器里的 CPL 和 GDT 的段描述符的DPL，以确保中断服务程序是高于当前程序的，如果这次中断是编程异常（如：int 80h系统调用），那么还要检查 CPL 和 IDT 表中中断描述符的 DPL，以保证当前程序有权限使用中断服务程序，这可以避免用户应用程序访问特殊的陷阱门和中断门。

CPU根据特权级的判断设定即将运行的中断服务程序要使用的栈的地址

CPU 会根据 CPL 和中断服务程序段描述符的 DPL 信息确认是否发生了特权级的转换，比如当前程序正运行在用户态，而中断程序是运行在内核态的，则意味着发生了特权级的转换，这时 CPU 会从当前程序的 TSS信息（该信息在内存中的首地址存在 TR 寄存器中）里取得该程序的内核栈地址，即包括 ss 和 esp 的值，并立即将系统当前使用的栈切换成新的栈。这个栈就是即将运行的中断服务程序要使用的栈。紧接着就将当前程序使用的 ss,esp 压到新栈中保存起来。也就说比如当前在某个函数中，使用的栈，在中断发生时，需要切换新的栈。

保护当前程序的现场

CPU开始利用栈保护被暂停执行的程序的现场：依次压入当前程序使用的 eflags，cs，eip，errorCode（如果是有错误码的异常）信息。

跳转到中断服务程序的第一条指令开始执行

CPU 利用中断服务程序的段描述符将其第一条指令的地址加载到 cs 和 eip 寄存器中，开始执行中断服务程序。这意味着先前的程序被暂停执行，中断服务程序正式开始工作。

中断服务程序处理完毕，恢复执行先前中断的程序

在每个中断服务程序的最后，必须有中断完成返回先前程序的指令，这就是iret（或iretd）。程序执行这条返回指令时，会从栈里弹出先前保存的被暂停程序的现场信息，即 eflags,cs,eip 重新开始执行。

31. Linux 的目录结构和文件类型

在 Linux 操作系统中，所有被操作系统管理的资源，例如网络接口卡、磁盘驱动器、打印机、输入输出设备、普通文件或是目录都被看作是一个文件。 也就是说在 Linux 系统中有一个重要的概念：一切都是文件。

其实这是 UNIX 哲学的一个体现，在 UNIX 系统中，把一切资源都看作是文件，Linux 的文件系统也是借鉴 UNIX 文件系统而来。

目录结构

Linux文件目录

目录	说明
bin	存放二进制可执行文件(ls,cat,mkdir等)，常用命令一般都在这里
boot	存放用于系统引导时使用的各种文件
dev	用于存放设备文件
etc	存放系统管理和配置文件
home	存放所有用户文件的根目录，是用户主目录的基点，比如用户 user 的主目录就是/home/user，可以用~user 表示
lib	存放跟文件系统中的程序运行所需要的共享库及内核模块
mnt	系统管理员安装临时文件系统的安装点，系统提供这个目录是让用户临时挂载其他的文件系统
opt	额外安装的可选应用程序包所放置的位置。一般情况下，我们可以把 tomcat 等都安装到这里
proc	虚拟文件系统，存放当前内存的映射，可直接访问这个目录来获取系统信息
root	超级用户目录
sbin	存放二进制可执行文件，只有root才能访问，这里存放的是系统管理员使用的系统级别的管理命令和程序。如 ifconfig 等
tmp	用于存放各种临时文件，是公用的临时文件存储点
usr	用于存放系统应用程序，比较重要的目录/usr/local 本地管理员软件安装目录
var	用于存放运行时需要改变数据的文件，也是某些大文件的溢出区，比方说各种服务的日志文件（系统启动日志等。）等
lost/found	这个目录平时是空的，系统非正常关机而留下“无家可归”的文件（windows 下叫什么.chk）就在这里

文件分类

Linux一切皆文件，文件一共分为7类分别是 - b c d s p l。

普通文件（regular file：-）

普通文件又分成文本文件和纯二进制文件。文本文件存放的都是文字编码，文本编辑器打开后，会将这些文字编码翻译为文字图形，以供人识别。（白色）纯二进制文件（机器码），比如经过编译后得到的可执行文件，里面放的是 cpu 执行的纯二进制机器码，不能被文本编辑器识别，用文本编辑器打开后，显示的内容是错乱的，无法辨识。（绿色）

块设备文件（block special file：b）

以块（1024字节）为单位来操作数据。块设备存储的数据量往往非常大，比如：电脑硬盘、移动硬盘、u盘等。

字符设备文件（character special file：c）

以字节为单位来操作数据。比如：键盘、鼠标、显示器都等是字符设备。Linux 将所有的外设当做文件来看待，都存放在 /dev 中。

目录文件（director file：d）

目录是一种特殊的文件，专门用于管理其它文件，将文件的名称和它的索引节点号结合在一起的一张表。（蓝色）

套接字文件（socket：s）

专门用于网络通信的文件。

管道文件（fifo：p）

用于实现不同进程（程序）之间的通信，管道是OS提供的一种纯代码层面的通信机制，主要用于进程间的传递数据，管道是进程间传递数据的媒介。例如 A 进程将数据存入管道文件中，B 进程从管道文件中获取数据。

符号连接文件（symbolic link：l）

其实就是一种快捷图标，背后指向了另外一个文件，提供了共享文件的一种方法。使用链接文件可以访问普通文件、目录文件和其他文件。（浅蓝色）

32. Linux常用命令

目录切换

cd ~:表示切换到用户主目录
cd -:表示切换到上一个操作所在目录

目录的操作命令

mkdir 目录名称：增加目录
ls/ll：查看目录信息（ll是ls -l的别名，ll命令可以看到该目录下的所有目录和文件的详细信息）
find 目录参数:寻找目录，示例：

列出当前目录及子目录下所有文件和文件夹: find .
在/home目录下查找以.txt结尾的文件名:find /home -name "*.txt"
同上，但忽略大小写: find /home -iname "*.txt"
当前目录及子目录下查找所有以.txt和.pdf结尾的文件:find . \( -name "*.txt" -o -name "*.pdf" \)或find . -name "*.txt" -o -name "*.pdf"

mv 目录名称新目录名称:修改目录的名称，mv的语法不仅可以对目录进行重命名而且也可以对各种文件，压缩包等进行重命名的操作。mv命令用来对文件或目录重新命名，或者将文件从一个目录移到另一个目录中。
mv 目录名称目录的新位置：移动目录的位置—剪切（改）,mv语法不仅可以对目录进行剪切操作，对文件和压缩包等都可执行剪切操作。另外mv与cp的结果不同，mv好像文件“搬家”，文件个数并未增加。而cp对文件进行复制，文件个数增加了。
cp -r 目录名称目录拷贝的目标位置：拷贝目录（改），-r代表递归拷贝,cp命令不仅可以拷贝目录还可以拷贝文件，压缩包等，拷贝文件和压缩包时不用写-r递归
rm [-rf] 目录: 删除目录（删）,rm不仅可以删除目录，也可以删除其他文件或压缩包，无论删除任何目录或文件，都直接使用rm -rf 目录/文件/压缩包

文件的操作命令

touch 文件名称：文件的创建
cat/tac/more/less/head/tail 文件名称:文件的查看

cat：查看显示文件内容
tac: 是 cat 的反向操作，从最后一行开始打印
more：可以显示百分比，回车可以向下一行，空格可以向下一页，q可以退出查看
less：可以使用键盘上的PgUp和PgDn向上和向下翻页，q结束查看
head：去文件前几行
tail-10：查看文件的后10行，Ctrl+C结束

注意：命令tail -f文件可以对某个文件进行动态监控，例如tomcat的日志文件，会随着程序的运行，日志会变化，可以使用tail -f catalina-2016-11-11.log监控文件的变化

vim 文件
rm -rf 文件:删除文件

文件搜索命令

which：指令搜索

which [-a] command
-a：将所有指令列出，而不是只列第一个

whereis：文件搜索，速度比较快，因为它只搜索几个特定的目录

whereis [-bmus] [BMS] dirname/filename
-b  定位可执行文件
-m  定位帮助文件
-s  定位源代码文件
-u  搜索出上面三个外的其他文件
-B  指定搜索可执行文件的路径
-M  指定搜索帮助文件的路径
-S  指定搜索源代码文件的路径

locate:文件搜索。可以用关键字或者正则表达式进行搜索。
locate使用/var/lib/mlocate/这个数据库来进行搜索，它存储在内存中，并且每天更新一次，所以无法用 locate 搜索新建的文件。可以使用updatedb来立即更新数据库。

# locate [-ir] keyword
-r：正则表达式

grep 要搜索的字符串要搜索的文件 --color：搜索命令，--color代表高亮显示

搜索文件里某一个单词或字符出现的次数：

grep -o objStr  filename|wc -l

压缩解压缩

Linux中的打包文件一般是以.tar结尾的，压缩的命令一般是以.gz结尾的。

而一般情况下打包和压缩是一起进行的，打包并压缩后的文件的后缀名一般.tar.gz。命令：tar -zcvf 打包压缩后的文件名要打包压缩的文件其中：

z：调用gzip压缩命令进行压缩
c：打包文件
v：显示运行过程
f：指定文件名

比如：假如test目录下有三个文件分别是：aaa.txt bbb.txt ccc.txt，如果我们要打包test目录并指定压缩后的压缩包名称为test.tar.gz可以使用命令:tar -zcvf test.tar.gz aaa.txt bbb.txt ccc.txt或tar -zcvf test.tar.gz /test/

解压压缩包命令：tar [-xvf] 压缩文件

其中x：代表解压

示例：

将/test下的test.tar.gz解压到当前目录下可以使用命令：tar -xvf test.tar.gz
将/test下的test.tar.gz解压到根目录/usr下:tar -xvf test.tar.gz -C /usr（- C代表指定解压的位置）

用于压缩的指令有：

gzip：gzip 是 Linux 使用最广的压缩指令，可以解开 compress、zip 与 gzip 所压缩的文件。经过 gzip 压缩过，源文件就不存在了。有 9 个不同的压缩等级可以使用。可以使用zcat、zmore、zless来读取压缩文件的内容。

$ gzip [-cdtv#] filename
-c ：将压缩的数据输出到屏幕上
-d ：解压缩
-t ：检验压缩文件是否出错
-v ：显示压缩比等信息
-# ： # 为数字的意思，代表压缩等级，数字越大压缩比越高，默认为 6

bzip2:提供比gzip更高的压缩比。查看命令：bzcat、bzmore、bzless、bzgrep。

 $ bzip2 [-cdkzv#] filename
-k ：保留源文件

xz：提供比 bzip2 更佳的压缩比。可以看到，gzip、bzip2、xz的压缩比不断优化。不过要注意的是，压缩比越高，压缩的时间也越长。查看命令：xzcat、xzmore、xzless、xzgrep。

$ xz [-dtlkc#] filename

权限命令

操作系统中每个文件都拥有特定的权限、所属用户和所属组。权限是操作系统用来限制资源访问的机制，在Linux中权限一般分为读(readable)、写(writable)和执行(excutable)，分为三组。分别对应文件的属主(owner)，属组(group)和其他用户(other)，通过这样的机制来限制哪些用户、哪些组可以对特定的文件进行什么样的操作。通过ls -l命令我们可以查看某个目录下的文件或目录的权限

示例：在随意某个目录下 ls -l

权限2

文件的类型

d：代表目录
-：代表文件
l：代表链接

Linux权限分为一下几种

r：代表权限是可读的，r也可以用数字4表示
w：代表权限是可写的，w也可以用数字2表示
x：代表权限是可执行，x也可以用数字1表示

文件权限和目录权限的区别

对于文件：

权限名称	可执行操作
r	可以使用cat查看文件的内容
w	可以修改文件的内容
x	可以将其运行为二进制文件

对于目录：

权限名称	可执行操作
r	可以查看目录下列表
w	可以创建和删除目录下的文件
x	可以使用cd进入目录

需要注意的是超级用户可以无视普通用户的权限，即使文件目录权限是000，依旧可以访问。在linux中的每个用户必须属于一个组，不能独立于组外。在linux中每个文件有所有者、所在组、其它组的概念。

所有者：一般为文件的创建者，谁创建了该文件，就天然的成为该文件的所有者，用ls ‐ahl命令可以看到文件的所有者也可以使用chown 用户名文件名来修改文件的所有者。
文件所在组：当某个用户创建了一个文件后，这个文件的所在组就是该用户所在的组，用ls ‐ahl命令可以看到文件的所有组也可以使用chgrp 组名文件名来修改文件所在的组。
其它组：除开文件的所有者和所在组的用户外，系统的其它用户都是文件的其它组

修改文件/目录的权限。

修改文件/目录的权限的命令：chmod

示例：修改/test下的aaa.txt的权限为属主有全部权限，属主所在的组有读写权限，其他用户只有读的权限

chmod u=rwx,g=rw,o=r aaa.txt
chmod 764 aaa.txt

用户管理

Linux系统是一个多用户多任务的分时操作系统，任何一个要使用系统资源的用户，都必须首先向系统管理员申请一个账号，然后以这个账号的身份进入系统。

用户的账号一方面可以帮助系统管理员对使用系统的用户进行跟踪，并控制他们对系统资源的访问；另一方面也可以帮助用户组织文件，并为用户提供安全性保护。

Linux用户管理相关命令:

useradd 选项用户名:添加用户账号
userdel 选项用户名:删除用户帐号
usermod 选项用户名:修改帐号
passwd 用户名:更改或创建用户的密码
passwd -S 用户名 :显示用户账号密码信息
passwd -d 用户名: 清除用户密码

useradd命令用于Linux中创建的新的系统用户。useradd可用来建立用户帐号。帐号建好之后，再用passwd设定帐号的密码．而可用userdel删除帐号。使用useradd指令所建立的帐号，实际上是保存在/etc/passwd文本文件中。

passwd命令用于设置用户的认证信息，包括用户密码、密码过期时间等。系统管理者则能用它管理系统用户的密码。只有管理者可以指定用户名称，一般用户只能变更自己的密码。

用户组管理

每个用户都有一个用户组，系统可以对一个用户组中的所有用户进行集中管理。不同Linux系统对用户组的规定有所不同，如Linux下的用户属于与它同名的用户组，这个用户组在创建用户时同时创建。

用户组的管理涉及用户组的添加、删除和修改。组的增加、删除和修改实际上就是对/etc/group文件的更新。

Linux系统用户组的管理相关命令:

groupadd 选项用户组:增加一个新的用户组
groupdel 用户组:要删除一个已有的用户组
groupmod 选项用户组: 修改用户组的属性

其他常用命令

pwd：显示当前所在位置
grep 要搜索的字符串要搜索的文件 --color：搜索命令，--color代表高亮显示

网络通信命令：

查看当前系统的网卡信息：ifconfig
查看与某台机器的连接情况：ping
查看当前系统的端口使用：netstat -an
net-tools和iproute2：net-tools起源于BSD的TCP/IP工具箱，后来成为老版本Linux内核中配置网络功能的工具。但自2001年起，Linux社区已经对其停止维护。同时，一些Linux发行版比如Arch Linux和CentOS/RHEL 7则已经完全抛弃了net-tools，只支持iproute2。linux ip命令类似于ifconfig，但功能更强大，旨在替代它。
shutdown:shutdown -h now：指定现在立即关机；shutdown +5 "System will shutdown after 5 minutes"：指定5分钟后关机，同时送出警告信息给登入用户。
reboot：重开机。reboot -w：做个重开机的模拟（只有纪录并不会真的重开机）。

进程管理命令

ps：查看进程

ps -l  # 查看自己的进程
ps aux # 查看系统所有进程
ps aux | grep threadx # 查看特定的进程

pstree：查看进程树
top：实时显示进程信息

top -d 2 # 每两秒钟刷新一次

netstat：查看占用端口的进程

netstat -anp | grep port # 查看特定端口的进程

ps -ef / ps -aux：这两个命令都是查看当前系统正在运行进程，两者的区别是展示格式不同。如果想要查看特定的进程可以使用这样的格式：ps aux|grep redis（查看包括redis字符串的进程），也可使用pgrep redis -a。
注意：如果直接用ps（Process Status）命令，会显示所有进程的状态，通常结合grep命令查看某进程的状态。
kill -9 进程的pid：杀死进程（-9表示强制终止。）
先用ps查找进程，然后用kill杀掉

进程状态

状态	说明
R	`running or runnable(on run queue)` 正在执行或者可执行，此时进程位于执行队列中。
D	`uninterruptible sleep (usually I/O)` 不可中断阻塞，通常为 IO 阻塞。
S	`interruptible sleep (waiting for an event to complete)` 可中断阻塞，此时进程正在等待某个事件完成。
Z	`zombie (terminated but not reaped by its parent)` 僵死，进程已经终止但是尚未被其父进程获取信息。
T	`stopped (either by a job control signal or because it is being traced)` 结束，进程既可以被作业控制信号结束，也可能是正在被追踪。

用一行指令找出指定的进程并将其全部Kill

ps -efww|grep -w 'helloworld'|grep -v grep|cut -c 9-15|xargs kill -9

说明：管道符|用来隔开两个命令，管道符左边命令的输出会作为管道符右边命令的输入。

ps　-efww是查看所有进程的命令。这时检索出的进程将作为下一条命令 grep 的输入，注意要结束其它程序时，请将上面命令中的 helloworld 替换成其它程序名，-w 'helloworld' 强制 PATTERN 仅完全匹配字词。
grep -v grep 是在列出的进程中去除含有关键字 grep 的进程。
cut -c 9-15 是截取输入行的第 9 个字符到第 15 个字符，而这正好是进程号 PID。
xargs kill -9 中的 xargs 命令是用来把前面命令的输出结果（PID）作为 kill -9 命令的参数，并执行该命令。
kill -9 会强行杀掉指定进程，这样就成功清除了同名进程。

Linux下查找大于1G的文件，并删除

find /APP/istester/ -type f -size +1G | xargs rm

列出当前目录文件的数量

$ ls -l | grep "^-" | wc -l

$ ls -lR| grep "^-" | wc -l

查看某目录下文件夹(目录)的个数（包括子目录）:

$ ls -lR | grep "^d" | wc -l

ls -l：长列表输出该目录下文件信息(注意这里的文件是指目录、链接、设备文件等)，每一行对应一个文件或目录，ls -lR是列出所有文件，包括子目录。
grep "^-"：过滤 ls 的输出信息，**只保留一般文件，只保留目录是 grep "^d"**。
wc -l：统计输出信息的行数，统计结果就是输出信息的行数，一行信息对应一个文件，所以就是文件的个数。

tcp抓包命令

简介

tcpdump 是一款强大的网络抓包工具，运行在 Linux 平台上。tcpdump 的使用能够帮助我们分析、调试网络数据。但是要想很好地掌握 tcpdump，就必须对网络报文（TCP/IP协议）有一定的了解。不过对于简单的使用来说，只要有网络基础概念就行了。

作为互联网上经典的的系统管理员必备工具，tcpdump以其强大的功能，灵活的截取策略，成为每个高级的系统管理员分析网络，排查问题等所必备的工具之一。在实际工作中，需要以 root 权限去执行该命令。

常见选项：

-s number：tcpdump 默认只会截取前96字节的内容，要想截取所有的报文内容，就需要使用这个选项，其中number是需要截取的报文字节数，如果是0的话，表示截取报文全部内容；
-nn：表示不解析域名，直接显示IP，在 netstat 命令中，也有这个选项；
-X：同时使用 hex 和 ascii 显示报文内容；
-S：显示绝对的序列号（sequence number），而不是相对编号；
-i：指定监听的网卡，如果为-i any则表示监听所有的网卡；
-v，-vv，-vvv：显示更多的详细信息；
-c number：表示截取 number 个报文，然后结束；
-w：将监听到的数据包写入文件中保存，而并不分析和打印出来；
-A：只使用 ascii 打印报文的全部数据，不要和 -X 选项一起使用。截取HTTP请求的时候可以用sudo tcpdump -nSA port 80

在服务器上的网络报文是异常的多，很多时候我们只关注和具体问题有关的数据报文，而这些有用的报文只占到很小的一部分，为了不让我们在报文的海洋里迷失自己，就需要使用 tcpdump 提供的灵活而且功能强大的过滤器。

过滤器也可以简单地分为三类：type，dir 和 proto。

type：主要用来区分过滤报文源类型，主要由 host 主机报文，net 网段报文和 port 指定端口的报文组成；
dir：只过滤报文的源地址和目的地址，主要包括 src 源地址和 dst 目的地址；
proto：只过滤报文的协议类型，支持 tcp，udp和 icmp 等；使用的时候可以省略proto关键字：

tcpdump -i eth1 arp
tcpdump -i eth1 ip
tcpdump -i eth1 tcp
tcpdump -i eth1 udp
tcpdump -i eth1 icmp

在进行抓包时，可以使用“与”（and、&&）、“或”（or、||）和“非”（not、!）来将多个条件组合起来

常用功能

写入文件：-w filename 监听内容写入文件
监听端口设置：

port 80 / tcp port 80 / udp port 80 / src port 80 / dst port 80 
监听80端口 / tcp80端口 / udp80端口 / 来源端口80 / 发往端口80

监听IP设置：

host 192.168.0.1 / src 192.168.0.1 / dst 192.168.0.1 
监听与主机192.168.0.1通信内容 / 监听来源自主机内容 / 监听发往主机内容

监听指定网络接口：-i eth0 监听eth0接口(执行 tcpdump -D 可以查看支持的接口有哪些）

常用样例

命令：tcpdump -i eth1
说明：监视指定网络接口的数据包
命令：tcpdump host 210.27.48.3
说明：截获210.27.48.3主机收到的和发出的所有数据包
命令：tcpdump host 210.27.48.4 and (210.27.48.5 or 210.27.48.6)
说明：截获 210.27.48.3 主机和 210.27.48.5 或者 210.27.48.6 主机进行通信的所有数据包
命令：tcpdump net 192.168.1.0/24
说明：截获 192.168.1.0/24 整个网络的数据包
命令：tcpdump -i eth0 src host 210.27.48.3
说明：监视 eth0 网卡上源地址是 210.27.48.3 的所有网络包
命令：tcpdump -i eth0 dst host 210.27.48.3
说明：监视 eth0 网卡上目的地址是 210.27.48.3 的所有网络包
命令：tcpdump tcp port 23 and host 210.27.48.3
说明：获取主机 210.27.48.3 上端口为23的应用发出和接收的所有TCP协议包
命令：tcpdump udp port 123
说明：获取本机 123 端口发出和接收的所有 UDP 协议包
命令：tcpdump src host 10.126.1.222 and dst net 10.126.1.0/24
说明：截获源主地址为 10.126.1.222，目的地址是 10.126.1.0/24 整个网络
命令：tcpdump -i eth0 -s0 -G 60 -Z root -w %Y_%m%d_%H%M_%S.pcap
说明：抓取报文后按照指定时间间隔保存；-G选项后面接时间，单位为秒；上述命令就是每隔60秒生存一个文件
命令：tcpdump -i eth0 -s0 -C 1 -Z root -w eth0Packet.pcap
说明：抓取报文后按照指定报文大小保存；-C选项后接文件大小，单位为MB；上述命令就是每抓包文件达到1MB时就使用一个新的文件保存新抓的报文

输出信息说明

输出示例如下：

/ 时间/ ID号 / IP 是表明该分组是IP分组 /  >表示从主机发送到另一主机的端口（< 表示接收） / FLAFGS是TCP报文中的标志信息 / win表示当前窗口大小 / length表示包的长度
22:04:38.306530 IP 183.232.231.172.https > 192.168.0.100.61572: Flags [P.], seq 578:723, ack 3611, win 1212, length 145

内存命令

top：用于实时显示 process 的动态

PID：进程的ID　　
USER：进程所有者
PR：进程的优先级别，越小越优先被执行
VIRT：进程占用的虚拟内存
RES：进程占用的物理内存
SHR：进程使用的共享内存
S：进程的状态,S表示休眠，R表示正在运行，Z表示僵死状态，N表示该进程优先值为负
%CPU：进程占用CPU的使用
%MEM：进程使用的物理内存和总内存的百分
TIME+：该进程启动后占用的总的CPU时间，即占用CPU使用时间的累加值
COMMAND：进程启动命令名称

free：查看系统内存使用情况

total:总计物理内存的大小
used:已使用多大
free:可用有多少
shared:多个进程共享的内存总额
buff/cached:磁盘缓存的大小
available:可用多少

m: 查看 RAM 使用情况最简单的方法是通过 /proc/meminfo

这个动态更新的虚拟文件实际上是许多其他内存相关工具(如：free / ps / top)等的组合显示。

/proc/meminfo 列出了所有你想了解的内存的使用情况。

进程的内存使用信息也可以通过/proc/<pid>/statm 和 /proc/<pid>/status 来查看。

查看磁盘命令

df [选项] [文件]:显示指定磁盘的可用空间，没指定则显示当前目录

-a  显示全部文件系统
-h  文件大小友好显示
-l  显示本地文件系统
-i  显示inode信息
-T  显示文件系统类型

du [选项] [文件]：显示每个文件和目录的磁盘使用空间

-h  方便阅读的方式
-s  只显示总和的大小

查看 IO 命令

用 top 命令中的 cpu 信息观察：其中 wa 的百分比可以大致的体现出当前的磁盘io请求是否频繁。如果 wa 的数量比较大，说明等待输入输出的的 io 比较多。
vmstat：vmstat 命令报告关于线程、虚拟内存、磁盘、陷阱和 CPU 活动的统计信息。由 vmstat 命令生成的报告可以用于平衡系统负载活动。系统范围内的这些统计信息(所有的处理器中)都计算出以百分比表示的平均值，或者计算其总和。
用iostat，Iostat 是 sysstat 工具集的一个工具，需要安装。r/s 和 w/s 分别是每秒的读操作和写操作，而 rKB/s 和 wKB/s 列以每秒千字节为单位显示了读和写的数据量

iostat -dx 显示磁盘扩展信息

防火墙命令

iptables 是一个基于命令行的防火墙工具，它使用规则链来允许/阻止网络流量。当一条网络连接试图在你的系统中建立时，iptables 会查找其对应的匹配规则。如果找不到，iptables 将对其采取默认操作。

iptables 的规则链分为三种：输入、转发和输出。

输入：这条链用来过滤目的地址是本机的连接。例如，如果一个用户试图使用 SSH 登陆到你的 PC/服务器，iptables 会首先匹配其 IP 地址和端口到 iptables 的输入链规则。
转发：这条链用来过滤目的地址和源地址都不是本机的连接。例如，路由器收到的绝大数数据均需要转发给其它主机。如果你的系统没有开启类似于路由器的功能，如 NATing，你就不需要使用这条链。
输出：这条链用来过滤源地址是本机的连接。例如，当你尝试 ping howtogeek.com 时，iptables 会检查输出链中与 ping 和 howtogeek.com 相关的规则，然后决定允许还是拒绝你的连接请求。

查看防火墙状态：

service iptables status

开启防火墙：

service iptables start

关闭防火墙：

service iptables stop

sed 命令

Linux sed 命令是利用脚本来处理文本文件。

sed 可依照脚本的指令来处理、编辑文本文件。

Sed 主要用来自动编辑一个或多个文件、简化对文件的反复操作、编写转换程序等。

sed [-hnV][-e<script>][-f<script文件>][文本文件]

参数说明：

-e<script> 或 --expression=<script>，以选项中指定的 script 来处理输入的文本文件。
-f<script文件> 或 --file=<script文件>，以选项中指定的 script 文件来处理输入的文本文件。
-h 或 --help 显示帮助。
-n 或 --quiet 或 --silent 仅显示 script 处理后的结果。
-V 或 --version 显示版本信息。

动作说明：

a ：新增， a 的后面可以接字串，而这些字串会在新的一行出现(目前的下一行)～
c ：取代， c 的后面可以接字串，这些字串可以取代 n1,n2 之间的行！
d ：删除，因为是删除啊，所以 d 后面通常不接任何咚咚；
i ：插入， i 的后面可以接字串，而这些字串会在新的一行出现(目前的上一行)；
s ：取代，可以直接进行取代的工作,通常这个 s 的动作可以搭配正规表示法！例如 1,20s/old/new/g 就是啦！

sed 后面接的动作，请务必以 '' 两个单引号括住，示例：

# 在testfile文件的第四行后添加一行，并将结果输出到标准输出
sed -e 4a\newLine testfile 

# 将 /etc/passwd 的内容列出并且列印行号，同时，请将第 2~5 行删除
nl /etc/passwd | sed '2,5d'

33. Linux的五种IO模型

在Linux（UNIX）操作系统中，共有五种IO模型：阻塞IO模型，非阻塞IO模型，IO复用模型，信号驱动IO模型以及异步IO模型。

阻塞和非阻塞

阻塞: 一个线程调用一个方法计算 1 - 100 的和，如果该方法没有返回结果，那么调用方法的线程就一直等待直到该方法执行完毕。
非阻塞: 一个线程调用一个方法计算 1 - 100 的和，该方法立刻返回，如果方法返回没有结果，调用者线程也无需一直等待该方法的结果，可以执行其他任务，但是在方法返回结果之前， 线程仍然需要轮询的检查方法是否已经有结果。

结论: 阻塞与非阻塞针对调用者的立场而言。

同步与异步

同步: 一个线程调用一个方法计算 1 - 100 的和，如果方法没有计算完，就不返回。
异步: 一个线程调用一个方法计算 1 - 100 的和，该方法立刻返回，但是由于方法没有返回结果，所以就需要被调用的这个方法来通知调用线程 1 - 100 的结果，或者线程在调用方法的时候指定一个回调函数来告诉被调用的方法执行完后就执行回调函数。

结论:同步和异步是针对被调用者的立场而言的。

IO

我们常说的IO，指的是文件的输入和输出，但是在操作系统中，一次完整的IO操作，是文件从硬盘中拷贝到用户空间的过程。

阻塞IO模型

这种模型是最简单的IO模型，一般表现为进程或线程等待某个条件，如果条件不满足，则一直等待下去。条件满足，则进行下一步操作。

阻塞IO模型

应用进程通过系统调用通过recvfrom接受数据，但由于内核还未准备好数据报，应用进程就会阻塞住，直到内核准备好数据报，recvfrom完成数据报复制工作，应用进程才能结束阻塞状态。

这种方式实现简单，但是比较耗费时间，比较适合那种并发低，时效性要求低的场景。

阻塞 IO 是同步阻塞的。

阻塞 IO 的同步体现在: 内核只有准备好数据并把数据复制到用户应用进程才会返回。
阻塞 IO 的阻塞体现在:用户应用进程等待内核准备数据和把数据从用户态拷贝到内核态的这整个过程，用户应用进程都必须一直等待。 当然,如果是本地磁盘 IO,内核准备数据的时间可能会很短。但网络 IO 就不一样了，因为服务端不知道客户端何时发送数据，内核就仍需要等待 socket 数据，时间就可能会很长。

阻塞 IO 的优点是对于数据是能够保证无延时的，因为应用程序进程会一直阻塞直到 IO 完成。但应用程序的阻塞就意味着应用程序进程无法执行其他任务，这会大大降低程序性能。一个不太可行的办法是为每个客户端 socket 都分配一个线程，这样就会提升 server 处理请求的能力。不过操作系统的线程资源是有限的，如果请求过多，可能造成线程资源耗尽，系统卡死等后果。

非阻塞IO模型

应用进程与内核交互，目的未达到之前，不再一味的等待，而是直接返回。然后通过轮询的方式，不停的去问内核数据准备有没有准备好。如果某一次轮询发现数据已经准备好了，那就把数据拷贝到用户空间。

非阻塞IO模型

应用进程通过recvfrom调用不停的去和内核交互，直到内核准备好数据。如果没有准备好，内核会返回error,应用进程在得到error后，过一段时间再发送recvfrom请求。在两次请求的时间段，进程可以先做别的事情。

非阻塞 IO 的非阻塞体现在: 用户应用进程不用阻塞在对内核的系统调用上

非阻塞 IO 的优点在于用户应用进程在轮询阶段可以执行其它任务。但这也是它的缺点，轮询就代表着用户应用进程不是时刻都会发起系统调用。 可能数据准备好了，而用户应用进程可能等待其它任务执行完毕才会发起系统调用，这就意味着数据可能会被延时获取。

信号驱动的IO模型

应用程序在读取文件时通知内核，如果某个socket的某个事件发生时，就向应用程序发一个信号。在收到信号后，信号对应的处理函数会进行后续处理。

用户应用进程发起 sigaction 系统调用,内核收到并立即返回。用户应用进程可以继续执行其他任务，不会阻塞。当内核准备好数据后向用户应用进程发送 SIGIO 信号，应用进程收到信号后，发起系统调用，将数据从内核拷贝到用户进程，然后进行数据处理。

信号驱动的IO模型

应用程序预先向内核注册一个信号处理函数，然后用户进程返回，并不阻塞，当内核数据准备就绪时就会发送一个信号给进程，用户便在信号处理函数中开始把数据拷贝到用户空间中。

IO复用模型

多个进程的IO可以注册到同一个管道上，这个管道会统一和内核进行交互。当管道中的某一个请求需要的数据准备好之后，进程再把对应的数据拷贝到用户空间中。

IO复用模型

IO多路转接是多了一个select函数，多个进程的IO可以注册到同一个select上，当用户进程调用该select,select会监听所有注册好的IO，如果所有被监听的IO需要的数据都没有好时，select调用进程会阻塞。当任意一个IO所需的数据准备好之后，select调用就会返回，然后进程在通过recvfrom来进行数据拷贝。

这里的IO复用模型，并没有向内核注册信号处理函数，所以，它并不是非阻塞的。进程在发出select后，要等到select监听的所有IO操作中至少有一个需要的数据准备好，才会有返回，并且也需要再次发送请求去进行文件的拷贝。

IO 多路复用模型是同步阻塞的

IO 多路复用模型的同步体现在: select 函数只有监听到某个 socket 有事件才会返回。
IO 多路复用模型的阻塞体现在: 用户应用进程会阻塞在对 select 函数上的调用上。

IO 多路复用的优点在于内核可以处理多个 socket，相当于一个用户进程(线程)就可以处理多个 socket 连接。

这样不仅降低了系统的开销，并且对于需要高并发的应用是非常有利的。而非阻塞 IO 和阻塞 IO 的一个用户应用进程只能处理一个 socket，要想处理多 socket，只能新开进程或线程，但这样很消耗系统资源。

PS: 在 IO 多路复用模型中, socket 一般应该为非阻塞的，这就是 Java 中 NIO 被称为非阻塞 IO 的原因。但实际上 NIO 属于 IO 多路复用，它是同步阻塞的 IO。

实现（Select/Poll/Epoll 区别）

select/poll/epoll都是I/O多路复用的具体实现，select出现的最早，之后是poll，再然后是epoll。

select，poll，epoll 都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步 I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

文件描述符：文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。
文件描述符在形式上是一个非负整数。实际上，它是一个索引值，指向内核为每一个进程所维护的该进程打开文件的记录表。当程序打开一个现有文件或者创建一个新文件时，内核向进程返回一个文件描述符。在程序设计中，一些涉及底层的程序编写往往会围绕着文件描述符展开。但是文件描述符这一概念往往只适用于UNIX、Linux这样的操作系统。

select

// 数据结构 (bitmap)
typedef struct {
    unsigned long fds_bits[__FDSET_LONGS];
} fd_set;

int select(int n, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

FD_ZERO(int fd, fd_set* fds)   // 清空集合
FD_SET(int fd, fd_set* fds)    // 将给定的描述符加入集合
FD_ISSET(int fd, fd_set* fds)  // 判断指定描述符是否在集合中 
FD_CLR(int fd, fd_set* fds)    // 将给定的描述符从文件中删除

select允许应用程序监视一组文件描述符，等待一个或者多个描述符成为就绪状态，从而完成I/O操作。select()的机制中提供一种 fd_set 的数据结构，实际上是一个 long 类型的数组，每一个数组元素都能与一打开的文件句柄（不管是 Socket 句柄,还是其他文件或命名管道或设备句柄）建立联系，建立联系的工作由程序员完成，当调用 select() 时，由内核根据 IO 状态修改 fd_set 的内容，由此来通知执行了 select() 的进程哪一 Socket 或文件可读。

从流程上来看，使用select函数进行IO请求和同步阻塞模型没有太大的区别，甚至还多了添加监视socket，以及调用select函数的额外操作，效率更差。但是，使用select以后最大的优势是用户可以在一个线程内同时处理多个socket的IO请求。用户可以注册多个socket，然后不断地调用select读取被激活的socket，即可达到在同一个线程内同时处理多个IO请求的目的。而在同步阻塞模型中，必须通过多线程的方式才能达到这个目的。

fd_set使用数组实现，数组大小使用FD_SETSIZE定义，所以只能监听少于FD_SETSIZE数量的描述符。有三种类型的描述符类型：readset,writeset,exceptset，分别对应读、写、异常条件的描述符集合。
timeout为超时参数，调用select会一直阻塞直到有描述符的事件到达或者等待的时间超过timeout。
成功调用返回结果大于0，出错返回结果为-1，超时返回结果为0

select的调用过程如下：

使用copy_from_user从用户空间拷贝fd_set到内核空间
注册回调函数__pollwait
遍历所有fd，调用其对应的poll方法（对于socket，这个poll方法是sock_poll，sock_poll根据情况会调用到tcp_poll,udp_poll或者datagram_poll）
以 tcp_poll 为例，其核心实现就是__pollwait，也就是上面注册的回调函数。
__pollwait 的主要工作就是把 current （当前进程）挂到设备的等待队列中，不同的设备有不同的等待队列，对于tcp_poll来说，其等待队列是 sk->sk_sleep （注意把进程挂到等待队列中并不代表进程已经睡眠了）。在设备收到一条消息（网络设备）或填写完文件数据（磁盘设备）后，会唤醒设备等待队列上睡眠的进程，这时 current 便被唤醒了。
poll方法返回时会返回一个描述读写操作是否就绪的mask掩码，根据这个mask掩码给fd_set赋值。
如果遍历完所有的fd，还没有返回一个可读写的mask掩码，则会调用 schedule_timeout 使调用select的进程（也就是current）进入睡眠。当设备驱动发现自身资源可读写后，会唤醒其等待队列上睡眠的进程。如果超过一定的超时时间（schedule_timeout指定），还是没人唤醒，则调用 select 的进程会重新被唤醒获得CPU，进而重新遍历 fd，判断有没有就绪的 fd。
把 fd_set 从内核空间拷贝到用户空间。

select 的缺点：

每次调用select，都需要把 fd 集合从用户态拷贝到内核态，这个开销在 fd 很多时会很大
同时每次调用 select 都需要在内核遍历传递进来的所有 fd，这个开销在 fd 很多时也很大
select 支持的文件描述符数量太小了，默认是1024

poll

int poll(struct pollfd *fds,unsigned int timeout)

poll功能与select类似，也是等待一组描述符中的一个成为就绪状态。
poll中描述符是pollfd类型的数组，pollfd定义如下：

struct pollfd {
    int fd;           /* file descriptor */
    short events;     /* requested events */
    short revents;    /* returned events */
}

比较

功能：select和poll的功能基本相同，不过在一些实现细节上有所不同。

select会修改描述符，而poll不会；
select的描述符类型使用数组实现，FD_SETSIZE大小默认为 1024，因此默认只能监听 1024 个描述符。如果要监听更多描述符的话，需要修改FD_SETSIZE之后重新编译；而poll没有描述符数量的限制；
poll提供了更多的事件类型，并且对描述符的重复利用上比select高。
如果一个线程对某个描述符调用了 select 或者 poll，另一个线程关闭了该描述符，会导致调用结果不确定。

速度：select和poll速度都比较慢，每次调用都需要将全部描述符从应用进程缓冲区复制到内核缓冲区。
可移植性：几乎所有的系统都支持 select，但是只有比较新的系统支持 poll。

epoll

epoll 是对 select 和 poll 的改进，epoll提供了三个函数: epoll_create,epoll_ctl 和 epoll_wait。

int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event)；
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);

// epoll_wait检查是否有事件发生时，只需要检查 eventpoll 对象中的 rdlist 双链表中是否有 epitem 元素即可
struct eventpoll {
    /*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/
    struct rb_root  rbr;
    /*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/
    struct list_head rdlist;
};

epoll_create 是创建一个 epoll句柄，也就是负责创建一个监控和管理句柄 fd 的池子；
epoll_ctl是注册要监听的事件类型,用于向内核注册新的描述符或者是改变某个文件描述符的状态，也就是负责管理这个池子里的 fd 增、删、改；
epoll_wait则是等待事件的产生,已注册的描述符在内核中会被维护在一棵红黑树上，通过回调函数内核会将 I/O 准备好的描述符加入到一个链表中管理，进程调用epoll_wait()便可以得到事件完成的描述符，让出 CPU 调度，但是只要有“事”，立马会从这里唤醒。

epoll 高效的原因

一：通过红黑树实现句柄快速，稳定的查找

首先，epoll 的第一步是创建一个池子。这个使用 epoll_create 来做：

原型：

int epoll_create(int size);

示例：

epollfd = epoll_create(1024);
if (epollfd == -1) {
    perror("epoll_create");
    exit(EXIT_FAILURE);
}

这个池子对我们来说是黑盒，这个黑盒是用来装 fd 的。当拿到了一个 epollfd ，这个 epollfd 就能唯一代表这个 epoll 池。注意，这里又有一个细节：用户可以创建多个 epoll 池。

然后，就要往这个 epoll 池里放 fd 了，这就要用到 epoll_ctl 了。

示例：

if (epoll_ctl(epollfd, EPOLL_CTL_ADD, 11, &ev) == -1) {
    perror("epoll_ctl: listen_sock");
    exit(EXIT_FAILURE);
}

上面，我们就把句柄 11 放到这个池子里了，op（EPOLL_CTL_ADD）表明操作是增加、修改、删除，event 结构体可以指定监听事件类型，可读、可写。

Linux 内核对于 epoll 池的内部实现就是用红黑树的结构体来管理这些注册进程来的句柄 fd。红黑树是一种平衡二叉树，时间复杂度为 O(log n)，就算这个池子就算不断的增删改，也能保持非常稳定的查找性能。这也是epoll 高效的第一个原因。

二：通过回调实现数据的快速感知

epoll_ctl 的内部实现中，除了把句柄结构用红黑树管理，另一个核心步骤就是设置 poll 回调。

思考来了：poll 回调是什么？怎么设置？

先说说 file_operations->poll 是什么？

Linux 设计成一切皆是文件的架构，这个不是说说而已，而是随处可见。实现一个文件系统的时候，就要实现这个文件调用，这个结构体用 struct file_operations 来表示。这个结构体有非常多的函数，精简了一些，如下：

struct file_operations {
    ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
    __poll_t (*poll) (struct file *, struct poll_table_struct *);
    int (*open) (struct inode *, struct file *);
    int (*fsync) (struct file *, loff_t, loff_t, int datasync);
    // ....
};

看到了 read，write，open，fsync，poll 等等，这些都是对文件的定制处理操作，对于文件的操作其实都是在这个框架内实现逻辑而已，比如 ext2 如果有对 read/write 做定制化，那么就会是 ext2_read，ext2_write，ext4 就会是 ext4_read，ext4_write。在 open 具体“文件”的时候会赋值对应文件系统的 file_operations 给到 file 结构体。

那很容易知道 read 是文件系统定制 fd 读的行为调用，write 是文件系统定制 fd 写的行为调用，file_operations->poll 呢？

这个是定制监听事件的机制实现。通过 poll 机制让上层能直接告诉底层，我这个 fd 一旦读写就绪了，请底层硬件（比如网卡）回调的时候自动把这个 fd 相关的结构体放到指定队列中，并且唤醒操作系统。

举个例子：网卡收发包其实走的异步流程，操作系统把数据丢到一个指定地点，网卡不断的从这个指定地点掏数据处理。请求响应通过中断回调来处理，中断一般拆分成两部分：硬中断和软中断。poll 函数就是把这个软中断回来的路上再加点料，只要读写事件触发的时候，就会立马通知到上层，采用这种事件通知的形式就能把浪费的时间窗就完全消失了。

这个 poll 事件回调机制则是 epoll 池高效最核心原理。epoll 池管理的句柄只能是支持了 file_operations->poll 的文件 fd。换句话说，如果一个“文件”所在的文件系统没有实现 poll 接口，那么就用不了 epoll 机制。在 epoll_ctl 的实现中，有一步是调用 vfs_poll ,这个里面就会有个判断，如果 fd 所在的文件系统的 file_operations 实现了 poll ，那么就会直接调用，如果没有，那么就会报告响应的错误码。

static inline __poll_t vfs_poll(struct file *file, struct poll_table_struct *pt)
{
    if (unlikely(!file->f_op->poll))
        return DEFAULT_POLLMASK;
    return file->f_op->poll(file, pt);
}

poll 调用里面究竟是实现了什么？

总结概括来说：挂了个钩子，设置了唤醒的回调路径。epoll 跟底层对接的回调函数是：ep_poll_callback，这个函数其实很简单，做两件事情：

把事件就绪的 fd 对应的结构体放到一个特定的队列（就绪队列，ready list）；
唤醒 epoll ，活来啦！

当 fd 满足可读可写的时候就会经过层层回调，最终调用到这个回调函数，把对应 fd 的结构体放入就绪队列中，从而把 epoll 从 epoll_wait 出唤醒。**这个对应结构体叫做 epitem **，每个注册到 epoll 池的 fd 都会对应一个。

那么就绪队列需要用很高级的数据结构吗？就绪队列就简单了，因为没有查找的需求了呀，只要是在就绪队列中的 epitem ，都是事件就绪的，必须处理的。所以就绪队列就是一个最简单的双指针链表。

总结来说，epoll 之所以做到了高效，最关键的三点：

内部管理 fd 使用了高效的红黑树结构管理，做到了增删改之后性能的优化和平衡；
epoll 池添加 fd 的时候，调用 file_operations->poll ，把这个 fd 就绪之后的回调路径安排好。通过事件通知的形式，做到最高效的运行；

epoll 池核心的两个数据结构：红黑树和就绪列表。红黑树是为了应对用户的增删改需求，就绪列表是 fd 事件就绪之后放置的特殊地点，epoll 池只需要遍历这个就绪链表，就能给用户返回所有已经就绪的 fd 数组；

对于 select 第一个缺点（每次调用select，都需要把 fd 集合从用户态拷贝到内核态），epoll的解决方案在 epoll_ctl 函数中。每次注册新的事件到 epoll 句柄中时（在 epoll_ctl 中指定 EPOLL_CTL_ADD），会把所有的 fd 拷贝进内核，而不是在 epoll_wait 的时候重复拷贝。epoll 保证了每个 fd 在整个过程中只会拷贝一次。

对于第二个缺点（每次调用 select 都需要在内核遍历传递进来的所有 fd），epoll 的解决方案不像 select 或 poll 一样每次都把 current 轮流加入 fd 对应的设备等待队列中，而只在 epoll_ctl 时把 current 挂一遍（这一遍必不可少）并为每个 fd 指定一个回调函数，当设备就绪，唤醒等待队列上的等待者时，就会调用这个回调函数，而这个回调函数会把就绪的 fd 加入一个就绪链表。epoll_wait 的工作实际上就是在这个就绪链表中查看有没有就绪的 fd（利用 schedule_timeout() 实现睡一会，判断一会的效果，和 select 实现中的第7步是类似的）。

对于第三个缺点，epoll 没有这个限制，它所支持的 FD 上限是最大可以打开文件的数目，这个数字一般远大于 2048,举个例子,在1GB 内存的机器上大约是10万左右，具体数目可以 cat /proc/sys/fs/file-max 察看,一般来说这个数目和系统内存关系很大。

从上面的描述可以看出,epoll只需要将描述符从进程缓冲区向内核缓冲区拷贝一次，并且进程不需要通过轮询来获得事件完成的描述符。

epoll仅适用于 Linux OS。

epoll比select和poll更加灵活而且没有描述符数量限制。

epoll对多线程编程更有友好，一个线程调用了epoll_wait()另一个线程关闭了同一个描述符也不会产生像select和poll的不确定情况。

哪些 fd 可以用 epoll 来管理？

再来思考另外一个问题：由于并不是所有的 fd 对应的文件系统都实现了 poll 接口，所以自然并不是所有的 fd 都可以放进 epoll 池，那么有哪些文件系统的 file_operations 实现了 poll 接口？

首先说，类似 ext2，ext4，xfs 这种常规的文件系统是没有实现的，换句话说，这些最常见的、真的是文件的文件系统反倒是用不了 epoll 机制的。

那谁支持呢？

最常见的就是网络套接字：socket 。网络也是 epoll 池最常见的应用地点。Linux 下万物皆文件，socket 实现了一套 socket_file_operations 的逻辑（ net/socket.c ）：

static const struct file_operations socket_file_ops = {
    .read_iter =    sock_read_iter,
    .write_iter =   sock_write_iter,
    .poll =     sock_poll,
    // ...
};

我们看到 socket 实现了 poll 调用，所以 socket fd 是天然可以放到 epoll 池管理的。

还有支持的吗？

有的，很多。其实 Linux 下还有两个很典型的 fd ，常常也会放到 epoll 池里。

eventfd：eventfd 实现非常简单，故名思义就是专门用来做事件通知用的。使用系统调用 eventfd 创建，这种文件 fd 无法传输数据，只用来传输事件，常常用于生产消费者模式的事件实现；
timerfd：这是一种定时器 fd，使用 timerfd_create 创建，到时间点触发可读事件；

工作模式

epoll的描述符事件有两种触发模式：LT（level trigger）和ET（edge trigger）。

LT 模式:当epoll_wait()检测到描述符事件到达时，将此事件通知进程，进程可以不立即处理该事件，下次调用epoll_wait()会再次通知进程。是默认的一种模式，并且同时支持Blocking和No-Blocking。
ET 模式:和 LT 模式不同的是，通知之后进程必须立即处理事件，下次再调用epoll_wait()时不会再得到事件到达的通知。很大程度上减少了epoll事件被重复触发的次数，因此效率要比 LT 模式高。只支持 No-Blocking，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

应用场景

很容易产生一种错觉认为只要用epoll就可以了，select和poll都已经过时了，其实它们都有各自的使用场景。

select应用场景

select的timeout参数精度为微秒，而poll和epoll为毫秒，因此select更加适用于实时性要求比较高的场景，比如核反应堆的控制。
select可移植性更好，几乎被所有主流平台所支持。

poll应用场景
poll没有最大描述符数量的限制，如果平台支持并且对实时性要求不高，应该使用poll而不是select。
epoll应用场景

只需要运行在 Linux 平台上，有大量的描述符需要同时轮询，并且这些连接最好是长连接。
需要同时监控小于 1000 个描述符，就没有必要使用epoll，因为这个应用场景下并不能体现epoll的优势。
需要监控的描述符状态变化多，而且都是非常短暂的，也没有必要使用epoll。因为epoll中的所有描述符都存储在内核中，造成每次需要对描述符的状态改变都需要通过epoll_ctl() 进行系统调用，频繁系统调用降低效率。并且epoll 的描述符存储在内核，不容易调试。

上面的四种IO模型，都是同步的IO模型，因为无论以上哪种模型，真正的数据拷贝过程，都是同步进行的。对于信号驱动模型，内核是在数据准备好之后通知进程，然后进程再通过recvfrom操作进行数据拷贝。可以认为数据准备阶段是异步的，但是，数据拷贝操作是同步的，所以整个IO过程也不能认为是异步的。

异步IO模型

应用进程把IO请求传给内核后，完全由内核去操作文件拷贝。内核完成相关操作后，会发信号告诉应用进程本次IO已经完成。

异步IO模型

用户进程发起aio_read操作后，给内核传递描述符、缓冲区指针、缓冲区大小等，告诉内核当整个操作系统操作完成时，如何通知进程，然后就立刻去做其他事情了。当内核收到aio_read后，会立刻返回，然后内核开始等待数据准备，数据准备好以后，直接把数据拷贝到用户控件，然后在通知进程本次IO已经完成。

异步 IO 的异步体现在:内核不用等待数据准备好就立刻返回，所以内核肯定需要在 IO 完成后通知用户应用进程。

34. Linux中的虚拟内存系统

Linux为每个进程维护了一个单独的虚拟地址空间。虚拟地址空间分为内核空间与用户空间，用户空间包括代码、数据、堆、共享库以及栈，内核空间包括内核中的代码和数据结构，内核空间的某些区域被映射到所有进程共享的物理页面。Linux也将一组连续的虚拟页面（大小等于内存总量）映射到相应的一组连续的物理页面，这种做法为内核提供了一种便利的方法来访问物理内存中任何特定的位置。

Linux中的虚拟内存系统

Linux将虚拟内存组织成一些区域（也称为段）的集合，区域的概念允许虚拟地址空间有间隙。一个区域就是已经存在着的已分配的虚拟内存的连续片（chunk）。例如，代码段、数据段、堆、共享库段，以及用户栈都属于不同的区域，每个存在的虚拟页都保存在某个区域中，而不属于任何区域的虚拟页是不存在的，也不能被进程所引用。

内核为系统中的每个进程维护一个单独的任务结构（task_struct）。任务结构中的元素包含或者指向内核运行该进程所需的所有信息（PID、指向用户栈的指针、可执行目标文件的名字、程序计数器等）。

Linux中的虚拟内存系统2

mm_struct：描述了虚拟内存的当前状态。pgd指向一级页表的基址（当内核运行这个进程时，pgd会被存放在CR3控制寄存器，也就是页表基址寄存器中），mmap指向一个vm_area_structs的链表，其中每个vm_area_structs都描述了当前虚拟地址空间的一个区域。
vm_starts：指向这个区域的起始处。
vm_end：指向这个区域的结束处。
vm_prot：描述这个区域内包含的所有页的读写许可权限。
vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的以及一些其他信息。
vm_next：指向链表的下一个区域结构。

内存映射

Linux通过将一个虚拟内存区域与一个硬盘上的文件关联起来，以初始化这个虚拟内存区域的内容，这个过程称为内存映射（memory mapping）。这种将虚拟内存系统集成到文件系统的方法可以简单而高效地把程序和数据加载到内存中。

一个区域可以映射到一个普通硬盘文件的连续部分，例如一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页的初始内容。由于按需页面调度的策略，这些虚拟页面没有实际交换进入物理内存，直到CPU引用的虚拟地址在该区域的范围内。如果区域比文件区要大，那么就用零来填充这个区域的余下部分。

一个区域也可以映射到一个匿名文件，匿名文件是由内核创建的，包含的全是二进制零。当CPU第一次引用这样一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就先将它写回到硬盘，之后用二进制零覆盖牺牲页并更新页表，将这个页面标记为已缓存在内存中的。

简单的来说：普通文件映射就是将一个文件与一块内存建立起映射关系，对该文件进行IO操作可以绕过内核直接在用户态完成（用户态在该虚拟地址区域读写就相当于读写这个文件）。匿名文件映射一般在用户空间需要分配一段内存来存放数据时，由内核创建匿名文件并与内存进行映射，之后用户态就可以通过操作这段虚拟地址来操作内存了。匿名文件映射最熟悉的应用场景就是动态内存分配（malloc()函数）。

Linux很多地方都采用了“懒加载”机制，自然也包括内存映射。不管是普通文件映射还是匿名映射，Linux只会先划分虚拟内存地址。只有当CPU第一次访问该区域内的虚拟地址时，才会真正的与物理内存建立映射关系。

只要虚拟页被初始化了，它就在一个由内核维护的交换文件（swap file）之间换来换去。交换文件又称为交换空间（swap space）或交换区域（swap area）。swap区域不止用于页交换，在物理内存不够的情况下，还会将部分内存数据交换到swap区域（使用硬盘来扩展内存）。

共享对象

虚拟内存系统为每个进程提供了私有的虚拟地址空间，这样可以保证进程之间不会发生错误的读写。但多个进程之间也含有相同的部分，例如每个C程序都使用到了C标准库，如果每个进程都在物理内存中保持这些代码的副本，那会造成很大的内存资源浪费。

内存映射提供了共享对象的机制，来避免内存资源的浪费。一个对象被映射到虚拟内存的一个区域，要么是作为共享对象，要么是作为私有对象的。

如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。相对的，对一个映射到私有对象的区域的任何写操作，对于其他进程来说是不可见的。一个映射到共享对象的虚拟内存区域叫做共享区域，类似地，也有私有区域。

为了节约内存，私有对象开始的生命周期与共享对象基本上是一致的（在物理内存中只保存私有对象的一份副本），并使用写时复制的技术来应对多个进程的写冲突。

Linux共享对象

只要没有进程试图写它自己的私有区域，那么多个进程就可以继续共享物理内存中私有对象的一个单独副本。然而，只要有一个进程试图对私有区域的某一页面进行写操作，就会触发一个保护异常。在上图中，进程B试图对私有区域的一个页面进行写操作，该操作触发了保护异常。异常处理程序会在物理内存中创建这个页面的一个新副本，并更新PTE指向这个新的副本，然后恢复这个页的可写权限。

还有一个典型的例子就是fork()函数，该函数用于创建子进程。当fork()函数被当前进程调用时，内核会为新进程创建各种必要的数据结构，并分配给它一个唯一的PID。为了给新进程创建虚拟内存，它复制了当前进程的mm_struct、vm_area_struct和页表的原样副本。并将两个进程的每个页面都标为只读，两个进程中的每个区域都标记为私有区域（写时复制）。

这样，父进程和子进程的虚拟内存空间完全一致，只有当这两个进程中的任一个进行写操作时，再使用写时复制来保证每个进程的虚拟地址空间私有的抽象概念。

35. 零拷贝

传统上，网络服务器通过网络将文件中存储的数据提供给客户端的过程是：

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

这里其实经历了四次上下文切换：

四次上下文切换

数据从磁盘读取到内核 read buffer，具体为：读取系统调用导致上下文从用户模式切换到内核模式。第一个副本由DMA引擎执行，该引擎从磁盘读取文件内容并将其存储到内核地址空间缓冲区中。
数据从内核缓冲区拷贝到用户缓冲区，然后读取系统调用返回，调用返回导致上下文从内核切换回用户模式。
数据从用户缓冲区拷贝到内核的 socket buffer，写系统调用导致上下文从用户模式又切换到内核模式。
数据从内核的 socket buffer 拷贝到网卡接口（硬件）的缓冲区，这一步也是通过 DMA 来传输。

从上面的步骤来说，第2、3步是不必要的。在此过程中，没有对文件内容做任何修改，那么在内核空间和用户空间来回拷贝数据无疑就是一种浪费，另外多次上下文的切换也影响性能。而零拷贝主要就是为了解决这种低效性。

零拷贝主要的任务就是避免 CPU 将数据从一块存储拷贝到另外一块存储，主要就是利用各种零拷贝技术，避免让CPU做大量的数据拷贝任务，减少不必要的拷贝，或者让别的组件来做这一类简单的数据传输任务，让CPU解脱出来专注于别的任务。这样就可以让系统资源的利用更加有效。这里主要有几个方法：

mmap

应用程序调用mmap()，磁盘上的数据会通过DMA被拷贝的内核缓冲区，接着操作系统会把这段内核缓冲区与应用程序共享，这样就不需要把内核缓冲区的内容往用户空间拷贝。应用程序再调用write(),操作系统直接将内核缓冲区的内容拷贝到socket缓冲区中，这一切都发生在内核态，最后，socket缓冲区再把数据发到网卡去。

tmp_buf = mmap(file, len);
write(socket, tmp_buf, len);

mmap

使用 mmap 替代 read 很明显减少了一次拷贝，当拷贝数据量很大时，无疑提升了效率。但是使用 mmap 是有代价的。当使用 mmap 时，可能会遇到一些隐藏的陷阱。例如，当程序 map 了一个文件，但是当这个文件被另一个进程截断(truncate)时, write 系统调用会因为访问非法地址而被 SIGBUS 信号终止。SIGBUS 信号默认会杀死你的进程并产生一个 coredump,如果服务器这样被中止了，那会产生一笔损失。

通常使用以下解决方案避免这种问题：

为SIGBUS信号建立信号处理程序
当遇到SIGBUS信号时，信号处理程序简单地返回，write系统调用在被中断之前会返回已经写入的字节数，并且errno会被设置成success,但是这是一种糟糕的处理办法，因为并没有解决问题的实质核心。这是一个治标不治本的解决方案。因为收到 SIGBUS 信号表示程序发生了严重的错误，不推荐使用它作为解决方案。
使用文件租借锁
通常使用这种方法，在文件描述符上使用租借锁，为文件向内核申请一个租借锁，当其它进程想要截断这个文件时，内核会向我们发送一个实时的RT_SIGNAL_LEASE信号，告诉我们内核正在破坏你加持在文件上的读写锁。这样在程序访问非法内存并且被SIGBUS杀死之前，你的write系统调用会被中断。write会返回已经写入的字节数，并且置errno为success。

sendfile

从2.1版内核开始，Linux引入了sendfile来简化操作:

#include<sys/sendfile.h>
ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);

系统调用 sendfile() 在代表输入文件的描述符 in_fd 和代表输出文件的描述符 out_fd 之间传送文件内容（字节）。描述符 out_fd 必须指向一个套接字，而 in_fd 指向的文件必须是可以 mmap 的。这些局限限制了 sendfile 的使用，使 sendfile 只能将数据从文件传递到套接字上，反之则不行。

使用 sendfile 不仅减少了数据拷贝的次数，还减少了上下文切换，数据传送始终只发生在 kernel space。

sendfile

在调用sendfile时，如果有其它进程截断了文件，假设没有设置任何信号处理程序，sendfile 调用仅仅返回它在被中断之前已经传输的字节数，errno 会被置为success。如果在调用 sendfile 之前给文件加了锁，sendfile 的行为仍然和之前相同，还会收到 RT_SIGNAL_LEASE 的信号。

目前为止，仍然存在一次拷贝，就是页缓存到socket缓存的拷贝。

借助于硬件上的帮助，可以将这一次的拷贝也省略。之前是把页缓存的数据拷贝到 socket 缓存中，实际上，我们仅仅需要把缓冲区描述符传到 socket 缓冲区，再把数据长度传过去，这样 DMA 控制器直接将页缓存中的数据打包发送到网络中就可以了。

sendfile2

总结一下，sendfile 系统调用利用 DMA 引擎将文件内容拷贝到内核缓冲区去，然后将带有文件位置和长度信息的缓冲区描述符添加 socket 缓冲区去，这一步不会将内核中的数据拷贝到 socket 缓冲区中，DMA 引擎会将内核缓冲区的数据拷贝到协议引擎中去，避免了最后一次拷贝。不过这一种收集拷贝功能是需要硬件以及驱动程序支持的。

使用splice

sendfile 只适用于将数据从文件拷贝到套接字上，限定了它的使用范围。Linux在2.6.17版本引入splice系统调用，用于在两个文件描述符中移动数据：

#define _GNU_SOURCE         /* See feature_test_macros(7) */
#include <fcntl.h>
ssize_t splice(int fd_in, loff_t *off_in, int fd_out, loff_t *off_out, size_t len, unsigned int flags);

splice 调用在两个文件描述符之间移动数据，而不需要数据在内核空间和用户空间来回拷贝。他从 fd_in 拷贝 len 长度的数据到 fd_out，但是有一方必须是管道设备，这也是目前 splice 的一些局限性。flags 参数有以下几种取值：

SPLICE_F_MOVE ：尝试去移动数据而不是拷贝数据。这仅仅是对内核的一个小提示：如果内核不能从pipe移动数据或者pipe的缓存不是一个整页面，仍然需要拷贝数据。Linux最初的实现有些问题，所以从2.6.21开始这个选项不起作用，后面的Linux版本应该会实现。
SPLICE_F_NONBLOCK ：splice 操作不会被阻塞。然而，如果文件描述符没有被设置为不可被阻塞方式的 I/O ，那么调用 splice 有可能仍然被阻塞。
SPLICE_F_MORE：后面的 splice 调用会有更多的数据。

splice 调用利用了 Linux 提出的管道缓冲区机制，所以至少一个描述符要为管道。

参考内容

主要参考以来两篇博客以及相关博客推荐，因找的博客比较多，没注意记录，最后好多忘了在哪2333，如果有侵权，请及时联系我，非常抱歉。

https://github.com/Snailclimb/JavaGuide

https://github.com/CyC2018/CS-Notes

Linux的目录结构和文件分类

Linux 防火墙 iptables 初学者教程

Linux sed 命令

linux查看磁盘io的三种方式

什么是协程？

进程和线程、协程的区别

进程、线程和协程的概念

Linux 统计某个字符串出现的次数

进程间通信IPC (InterProcess Communication)

什么是惊群，如何有效避免惊群?

nginx怎么避免惊群？

nginx实现高并发的原理

中断和中断处理流程

彻底理解 IO多路复用

浅析Linux中的零拷贝技术

Zero Copy I: User-Mode Perspective

什么是 “零拷贝” ？

彻底理解Netty，这一篇文章就够了

Virtual address spaces

虚拟内存的那点事儿

Go语言高阶：调度器系列（1）起源

深入理解 Linux 的 epoll 机制

1. 操作系统的基本概念

操作系统的内核（Kernel）

中央处理器（CPU，Central Processing Unit）

CPU vs Kernel(内核)

2. 操作系统的基本特性

并发性

共享性

互斥共享方式

同时访问方式

虚拟性

异步性

3. 操作系统的基本功能

4. 什么是系统调用/用户态和系统态是？

为什么要有用户态与内核态?

用户态切换到内核态的几种方式

5. 程序、进程与线程和协程

程序

进程

线程

线程的属性

区别

协程

6. 进程状态的切换

进程的三种基本状态

7. 进程同步

临界资源

临界区

同步和互斥

信号量机制

整形信号量

记录型信号量

AND型信号量

使用信号量实现生产者——消费者问题

8. 管程

9. 经典同步问题

读者——写者问题

哲学家进餐问题

10. 进程通信

进程通信的分类

共享存储器系统

共享内存(share memory)

消息传递系统

直接通信方式

间接通信方式

管道通信系统（匿名管道）

管道的实质：

管道的局限：

有名管道(FIFO)

匿名管道和有名管道对比：

客户机——服务器系统（套接字(socket)）

套接字特性

套接字通信的建立

11. 进程调度算法

批处理系统

先来先服务调度算法（FCFS）

短作业（进程）优先调度算法（SJF）

最短剩余时间优先（SRTN）

交互式系统

时间片轮转

优先级调度

多级反馈队列调度算法

实时系统

12. 死锁产生的必要条件

13. 处理死锁的基本方法

鸵鸟策略

预防死锁

摒弃“请求和保持”条件

摒弃不剥夺条件

摒弃“环路等待”条件

避免死锁

利用银行家算法避免死锁

银行家算法中的数据结构

银行家算法

安全性算法

检测死锁

每种类型一个资源的死锁检测

每种类型多个资源的死锁检测

死锁解除

14. 什么是虚拟内存

虚拟（逻辑）地址和逻辑地址