操作系统

大部分互联网公司的软件开发职位面试可能不会直接涉及这一层面的知识，但并不意味着这部分知识不重要。对于计算机底层实现的深入理解，能帮助你了解计算机的运行原理，能够更好地设计高效的架构，并且有助于调试、判断错误。特别地，对于多线程的理解尤为重要：现今的程序架构都需要并发处理，如何协调不同线程之间的分工协作，避免死锁、同步出错等等问题，是程序员应当具备的技能。对于后端工程师而言，良好的操作系统知识基础更是深刻理解并实现复杂分布式系统的前提条件。

进程vs.线程

进程(process)与线程(thread)最大的区别是进程拥有自己的地址空间，某进程内的线程对于其他进程不可见，即进程A不能通过传地址的方式直接读写进程B的存储区域。进程之间的通信需要通过进程间通信(Inter-process communication，IPC)。与之相对的，同一进程的各线程间之间可以直接通过传递地址或全局变量的方式传递信息。

此外，进程作为操作系统中拥有资源和独立调度的基本单位，可以拥有多个线程。通常操作系统中运行的一个程序就对应一个进程。在同一进程中，线程的切换不会引起进程切换。在不同进程中进行线程切换，如从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。相比进程切换，线程切换的开销要小很多。线程于进程相互结合能够提高系统的运行效率。

线程可以分为两类：

一类是用户级线程(user level thread)。对于这类线程，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。在应用程序启动后，操作系统分配给该程序一个进程号，以及其对应的内存空间等资源。应用程序通常先在一个线程中运行，该线程被成为主线“程。在其运行的某个时刻，可以通过调用线程库中的函数创建一个在相同进程中运行的新线程。用户级线程的好处是非常高效，不需要进入内核空间，但并发效率不高。

另一类是内核级线程(kernel level thread)。对于这类线程，有关线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只能调用内核线程的接口。内核维护进程及其内部的每个线程，调度也由内核基于线程架构完成。内核级线程的好处是，内核可以将不同线程更好地分配到不同的CPU，以实现真正的并行计算。

事实上，在现代操作系统中，往往使用组合方式实现多线程，即线程创建完全在用户空间中完成，并且一个应用程序中的多个用户级线程被映射到一些内核级线程上，相当于是一种折中方案。

上下文切换

对于单核单线程CPU而言，在某一时刻只能执行一条CPU指令。上下文切换(Context Switch)是一种将CPU资源从一个进程分配给另一个进程的机制。从用户角度看，计算机能够并行运行多个进程，这恰恰是操作系统通过快速上下文切换造成的结果。在切换的过程中，操作系统需要先存储当前进程的状态(包括内存空间的指针，当前执行完的指令等等)，再读入下一个进程的状态，然后执行此进程。

系统调用

系统调用(System call)是程序向系统内核请求服务的方式。可以包括硬件相关的服务(例如，访问硬盘等)，或者创建新进程，调度其他进程等。系统调用是程序和操作系统之间的重要接口。

Semaphore/Mutex

当用户创立多个线程／进程时，如果不同线程／进程同时读写相同的内容，则可能造成读写错误，或者数据不一致。此时，需要通过加锁的方式，控制核心区域(critical section)的访问权限。对于semaphore而言，在初始化变量的时候可以控制允许多少个线程／进程同时访问一个critical section，其他的线程／进程会被堵塞，直到有人解锁。

Mutex相当于只允许一个线程／进程访问的semaphore。此外，根据实际需要，人们还实现了一种读写锁(read-write lock)，它允许同时存在多个阅读者(reader)，但任何时候至多只有一个写者(writer)，且不能于读者共存。

死锁

在引入锁的同时，我们遇到了一个新的问题：死锁(Deadlock)。死锁是指两个或多个线程／进程之间相互阻塞，以至于任何一个都不能继续运行，因此也不能解锁其他线程／进程。例如，线程A占有lock A，并且尝试获取lock B；而线程2占有lock B，尝试获取lock A。此时，两者相互阻塞，都无法继续运行。

总结产生死锁的四个条件(只有当四个条件同时满足时才会产生死锁)：

Mutual Exclusion – Only one process may use a resource at a time
Hold-and-Wait – Process holds resource while waiting for another
No Preemption – Can’t take a resource away from a process
Circular Wait – The waiting processes form a cycle

生产者消费者

生产者消费者模型是一种常见的通信模型：生产者和消费者共享一个数据管道，生产者将数据写入buffer，消费者从另一头读取数据。对于数据管道，需要考虑为空和溢出的情况。同时，通常还需要将这部分共享内存用mutex加锁。在只有一个生产者一个消费者的情况下，可以设计无锁队列(lockless queue)，线程安全地直接读写数据。

进程间通信

在介绍进程的时候，我们提起过一个进程不能直接读写另一个进程的数据，两者之间的通信需要通过进程间通信(inter-process communication, IPC)进行。进程通信的方式通常遵从生产者消费者模型，需要实现数据交换和同步两大功能。

1) Shared-memory + semaphore

不同进程通过读写操作系统中特殊的共享内存进行数据交换，进程之间用semaphore实现同步。

2) Message passing

进程在操作系统内部注册一个port，并且监测有没有数据，其他进程直接写数据到该port。该通信方式更加接近于网络通信方式。事实上，网络通信也是一种IPC，只是进程分布在不同机器上而已。

逻辑地址/物理地址/虚拟内存

所谓的逻辑地址，是指计算机用户(例如程序开发者)，看到的地址。例如，当创建一个长度为100的整型数组时，操作系统返回一个逻辑上的连续空间：指针指向数组第一个元素的内存地址。由于整型元素的大小为4个字节，故第二个元素的地址时起始地址加4，以此类推。事实上，逻辑地址并不一定是元素存储的真实地址，即数组元素的物理地址(在内存条中所处的位置)，并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的，这样更符合人们的直观思维。

另一个重要概念是虚拟内存。操作系统读写内存的速度可以比读写磁盘的速度快几个量级。但是，内存价格也相对较高，不能大规模扩展。于是，操作系统可以通过将部分不太常用的数据移出内存，“存放到价格相对较低的磁盘缓存，以实现内存扩展。操作系统还可以通过算法预测哪部分存储到磁盘缓存的数据需要进行读写，提前把这部分数据读回内存。虚拟内存空间相对磁盘而言要小很多，因此，即使搜索虚拟内存空间也比直接搜索磁盘要快。唯一慢于磁盘的可能是，内存、虚拟内存中都没有所需要的数据，最终还需要从硬盘中直接读取。这就是为什么内存和虚拟内存中需要存储会被重复读写的数据，否则就失去了缓存的意义。

现代计算机中有一个专门的转译缓冲区(Translation Lookaside Buffer，TLB)，用来实现虚拟地址到物理地址的快速转换。

与内存／虚拟内存相关的还有如下两个概念：

1) Resident Set

当一个进程在运行的时候，操作系统不会一次性加载进程的所有数据到内存，只会加载一部分正在用，以及预期要用的数据。其他数据可能存储在虚拟内存，交换区和硬盘文件系统上。被加载到内存的部分就是resident set。

2) Thrashing

由于resident set包含预期要用的数据，理想情况下，进程运行过程中用到的数据都会逐步加载进resident set。但事实往往并非如此：每当需要的内存页面(page)不在resident set中时，操作系统必须从虚拟内存或硬盘中读数据，这个过程被称为内存页面错误(page faults)。当操作系统需要花费大量时间去处理页面错误的情况就是thrashing。

文件系统

Unix风格的文件系统利用树形结构管理文件。每个节点有多个指针，指向下一层节点或者文件的磁盘存储位置。文件节点还附有文件的操作信息(metadata)，包括修改时间，访问权限等等。

用户的访问权限通过访问控制表(Access Control List)和能力表(Capability List)实现。前者从文件角度出发，标注了每个用户可以对该文件进行何种操作。后者从用户角度出发，标注了某用户可以以什么权限操作哪些文件。

Unix的文件权限分为读、写和执行，用户组分为文件拥有者，组和所有用户。可以通过命令对三组用户分别设置权限。

实时 vs.分时操作系统

操作系统可以分为实时操作系统(Real-time system)，和分时操作系统(Sharing time system)。通常计算机采用的是sharing time，即多个进程／用户之间共享CPU，从形势上实现多任务。各个用户／进程之间的调度并非精准度特别高，如果一个进程被锁住，可以给它分配更多的时间。而实时操作系统则不同，软件和硬件必须遵从严格的deadline，超过时限的进程可能直接被终止。在这样的操作系统中，每次加锁都需要仔细考虑。

编译器

对于高级语言来说，代码需要通过编译才能够运行。编译通过编译器(compiler)实现，是一个将程序源代码转换成二进制机器码的过程。计算机可以直接执行二进制代码。在编译的过程中，编译器需要进行词法分析(lexical analysis)，解析(parsing)和过渡代码生成(intermediate code generation)。编译器的好坏可以直接影响最终代码的执行效率。

请问死锁的条件是什么？以及如何处理死锁问题？

解答：互斥条件(Mutual exclusion)：

资源不能被共享，只能由一个进程使用。
请求与保持条件(Hold and wait)：已经得到资源的进程可以再次申请新的资源。
非剥夺条件(No pre-emption)：已经分配的资源不能从相应的进程中被强制地剥夺。
循环等待条件(Circular wait)：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。

如何处理死锁问题：

忽略该问题。例如鸵鸟算法，该算法可以应用在极少发生死锁的的情况下。为什么叫鸵鸟算法呢，因为传说中鸵鸟看到危险就把头埋在地底下，可能鸵鸟觉得看不到危险也就没危险了吧。跟掩耳盗铃有点像。
检测死锁并且恢复。
仔细地对资源进行动态分配，以避免死锁。
通过破除死锁四个必要条件之一，来防止死锁产生。

请阐述动态链接库与静态链接库的区别。

解答：静态链接库是.lib格式的文件，一般在工程的设置界面加入工程中，程序编译时会把lib文件的代码加入你的程序中因此会增加代码大小，你的程序一运行lib代码强制被装入你程序的运行空间，不能手动移除lib代码。

动态链接库是程序运行时动态装入内存的模块，格式*.dll，在程序运行时可以随意加载和移除，节省内存空间。

在大型的软件项目中一般要实现很多功能，如果把所有单独的功能写成一个个lib文件的话，程序运行的时候要占用很大的内存空间，导致运行缓慢；但是如果将功能写成dll文件，就可以在用到该功能的时候调用功能对应的dll文件，不用这个功能时将dll文件移除内存，这样可以节省内存空间。

请阐述进程与线程的区别。

解答：

从概念上：
- 进程：一个程序对一个数据集的动态执行过程，是分配资源的基本单位。
- 线程：一个进程内的基本调度单位。线程的划分尺度小于进程，一个进程包含一个或者更多的线程。
从执行过程中来看：
- 进程：拥有独立的内存单元，而多个线程共享内存，从而提高了应用程序的运行效率。
- 线程：每一个独立的线程，都有一个程序运行的入口、顺序执行序列、和程序的出口。但是线程不能够独立的执行，必须依存在应用程序中，由应用程序提供多个线程执行控制。
从逻辑角度来看（重要区别）：
- 多线程的意义在于一个应用程序中，有多个执行部分可以同时执行。但是，操作系统并没有将多个线程看做多个独立的应用，来实现进程的调度和管理及资源分配。

用户进程间通信主要哪几种方式？

解答：主要有以下6种：

管道：管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的道端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样地，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞。
- 无名管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系（通常是指父子进程关系）的进程间使用。
- 命名管道：命名管道也是半双工的通信方式，在文件系统中作为一个特殊的设备文件而存在，但是它允许无亲缘关系进程间的通信。当共享管道的进程执行完所有的I/O操作以后，命名管道将继续保存在文件系统中以便以后使用。
信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
消息队列：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
信号：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
共享内存：共享内存就是映射一段能被其它进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量）配合使用，来实现进程间的同步和通信。
套接字：套接字也是一种进程间通信机制，与其它通信机制不同的是，它可用于不同机器间的进程通信。

操作系统的五大功能，分别为：作业管理、文件管理、存储管理、输入输出设备管理、进程及处理机管理

中断与系统调用

中断

所谓的中断就是在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类：

由计算机硬件异常或故障引起的中断，称为内部异常中断；
由程序中执行了引起中断的指令而造成的中断，称为软中断（这也是和我们将要说明的系统调用相关的中断）；
由外部设备请求引起的中断，称为外部中断。简单来说，对中断的理解就是对一些特殊事情的处理。

与中断紧密相连的一个概念就是中断处理程序了。当中断发生的时候，系统需要去对中断进行处理，对这些中断的处理是由操作系统内核中的特定函数进行的，这些处理中断的特定的函数就是我们所说的中断处理程序了。

另一个与中断紧密相连的概念就是中断的优先级。中断的优先级说明的是当一个中断正在被处理的时候，处理器能接受的中断的级别。中断的优先级也表明了中断需要被处理的紧急程度。每个中断都有一个对应的优先级，当处理器在处理某一中断的时候，只有比这个中断优先级高的中断可以被处理器接受并且被处理。优先级比这个当前正在被处理的中断优先级要低的中断将会被忽略。

典型的中断优先级如下所示：

机器错误 > 时钟 > 磁盘 > 网络设备 >  终端 > 软件中断

当发生软件中断时，其他所有的中断都可能发生并被处理；但当发生磁盘中断时，就只有时钟中断和机器错误中断能被处理了。

系统调用

在讲系统调用之前，先说下进程的执行在系统上的两个级别：用户级和核心级，也称为用户态和系统态(user mode and kernel mode)。

程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，比如说打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，这就是系统调用。

Linux系统有专门的函数库来提供这些请求操作系统服务的入口，这个函数库中包含了操作系统所提供的对外服务的接口。当进程发出系统调用之后，它所处的运行状态就会由用户态变成核心态。但这个时候，进程本身其实并没有做什么事情，这个时候是由内核在做相应的操作，去完成进程所提出的这些请求。

系统调用和中断的关系就在于，当进程发出系统调用申请的时候，会产生一个软件中断。产生这个软件中断以后，系统会去对这个软中断进行处理，这个时候进程就处于核心态了。

那么用户态和核心态之间的区别是什么呢？（以下区别摘至《UNIX操作系统设计》）

用户态的进程能存取它们自己的指令和数据，但不能存取内核指令和数据（或其他进程的指令和数据）。然而，核心态下的进程能够存取内核和用户地址
某些机器指令是特权指令，在用户态下执行特权指令会引起错误

对此要理解的一个是，在系统中内核并不是作为一个与用户进程平行的估计的进程的集合，内核是为用户进程运行的。

并发技术

进程

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。它可以申请和拥有系统资源，是一个动态的概念，是一个活动的实体。它不只是程序的代码，还包括当前的活动，通过程序计数器的值和处理寄存器的内容来表示。

进程的概念主要有两点：第一，进程是一个实体。每一个进程都有它自己的地址空间，一般情况下，包括文本区域（text region）、数据区域（data region）和堆栈（stack region）。文本区域存储处理器执行的代码；数据区域存储变量和进程执行期间使用的动态分配的内存；堆栈区域存储着活动过程调用的指令和本地变量。第二，进程是一个“执行中的程序”。程序是一个没有生命的实体，只有处理器赋予程序生命时，它才能成为一个活动的实体，我们称其为进程。

进程的基本状态

等待态：等待某个事件的完成；
就绪态：等待系统分配处理器以便运行；
运行态：占有处理器正在运行。
运行态→等待态往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。

等待态→就绪态则是等待的条件已满足，只需分配到处理器后就能运行。

运行态→就绪态不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。

就绪态→运行态系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态

进程调度

调度种类

高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度：

高级调度：(High-Level Scheduling)又称为作业调度，它决定把后备作业调入内存运行；
低级调度：(Low-Level Scheduling)又称为进程调度，它决定把就绪队列的某进程获得CPU；
中级调度：(Intermediate-Level Scheduling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。

非抢占式调度与抢占式调度

非抢占式
- 分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生进程调度进程调度某事件而阻塞时，才把处理机分配给另一个进程。
抢占式
- 操作系统将正在运行的进程强行暂停，由调度程序将CPU分配给其他就绪进程的调度方式。

调度策略的设计

响应时间: 从用户输入到产生反应的时间

周转时间: 从任务开始到任务结束的时间

CPU任务可以分为交互式任务和批处理任务，调度最终的目标是合理的使用CPU，使得交互式任务的响应时间尽可能短，用户不至于感到延迟，同时使得批处理任务的周转时间尽可能短，减少用户等待的时间。

调度算法

FIFO或First Come, First Served (FCFS)
- 调度的顺序就是任务到达就绪队列的顺序。
- 公平、简单(FIFO队列)、非抢占、不适合交互式。未考虑任务特性，平均等待时间可以缩短
Shortest Job First (SJF)
- 最短的作业(CPU区间长度最小)最先调度。
- 可以证明，SJF可以保证最小的平均等待时间。
- Shortest Remaining Job First (SRJF)
- SJF的可抢占版本，比SJF更有优势。
- SJF(SRJF): 如何知道下一CPU区间大小？根据历史进行预测: 指数平均法。
优先权调度
- 每个任务关联一个优先权，调度优先权最高的任务。
- 注意：优先权太低的任务一直就绪，得不到运行，出现“饥饿”现象。
- FCFS是RR的特例，SJF是优先权调度的特例。这些调度算法都不适合于交互式系统。
Round-Robin(RR)
- 设置一个时间片，按时间片来轮转调度（“轮叫”算法）
- 优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；
- 如何确定时间片？
- 时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。
多级队列调度
- 按照一定的规则建立多个进程队列
- 不同的队列有固定的优先级（高优先级有抢占权）
- 不同的队列可以给不同的时间片和采用不同的调度方法
- 存在问题1：没法区分I/O bound和CPU bound；
- 存在问题2：也存在一定程度的“饥饿”现象；
多级反馈队列
- 在多级队列的基础上，任务可以在队列之间移动，更细致的区分任务。
- 可以根据“享用”CPU时间多少来移动队列，阻止“饥饿”。
- 最通用的调度算法，多数OS都使用该方法或其变形，如UNIX、Windows等。

进程同步

临界资源与临界区

在操作系统中，进程是占有资源的最小单位（线程可以访问其所在进程内的所有资源，但线程本身并不占有资源或仅仅占有一点必须资源）。但对于某些资源来说，其在同一时间只能被一个进程所占用。这些一次只能被一个进程所占用的资源就是所谓的临界资源。典型的临界资源比如物理上的打印机，或是存在硬盘或内存中被多个进程所共享的一些变量和数据等(如果这类资源不被看成临界资源加以保护，那么很有可能造成丢数据的问题)。

对于临界资源的访问，必须是互斥进行。也就是当临界资源被占用时，另一个申请临界资源的进程会被阻塞，直到其所申请的临界资源被释放。而进程内访问临界资源的代码被成为临界区。

对于临界区的访问过程分为四个部分：

进入区:查看临界区是否可访问，如果可以访问，则转到步骤二，否则进程会被阻塞
临界区:在临界区做操作
退出区:清除临界区被占用的标志
剩余区：进程与临界区不相关部分的代码

解决临界区问题可能的方法：

一般软件方法
关中断方法
硬件原子指令方法
信号量方法

信号量

信号量是一个确定的二元组（s，q），其中s是一个具有非负初值的整形变量，q是一个初始状态为空的队列，整形变量s表示系统中某类资源的数目：

当其值 ≥ 0 时，表示系统中当前可用资源的数目
当其值＜ 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目

除信号量的初值外，信号量的值仅能由P操作和V操作更改，操作系统利用它的状态对进程和资源进行管理

P操作

P 操作记为P(s)，其中s为一信号量，它执行时主要完成以下动作：

s.value = s.value - 1；  /*可理解为占用1个资源，若原来就没有则记帐“欠”1个*/

若s.value ≥ 0，则进程继续执行，否则（即s.value < 0），则进程被阻塞，并将该进程插入到信号量s的等待队列s.queue中

说明：实际上，P操作可以理解为分配资源的计数器，或是使进程处于等待状态的控制指令

V操作

V 操作记为V(s)，其中s为一信号量，它执行时，主要完成以下动作：

s.value = s.value + 1；/*可理解为归还1个资源，若原来就没有则意义是用此资源还1个欠帐*/

若s.value > 0，则进程继续执行，否则（即s.value ≤ 0）,则从信号量s的等待队s.queue中移出第一个进程，使其变为就绪状态，然后返回原进程继续执行

说明：实际上，V操作可以理解为归还资源的计数器，或是唤醒进程使其处于就绪状态的控制指令

信号量方法实现：生产者 − 消费者互斥与同步控制

semaphore fullBuffers = 0; /*仓库中已填满的货架个数*/
semaphore emptyBuffers = BUFFER_SIZE;/*仓库货架空闲个数*/
semaphore mutex = 1; /*生产-消费互斥信号*/

Producer()
{
    while(True)
    {
       /*生产产品item*/
       emptyBuffers.P();
       mutex.P();
       /*item存入仓库buffer*/
       mutex.V();
       fullBuffers.V();
    }
}

Consumer()
{
    while(True)
    {
        fullBuffers.P();
        mutex.P();
        /*从仓库buffer中取产品item*/
        mutex.V();
        emptyBuffers.V();
        /*消费产品item*/
    }
}

使用pthread实现的生产者－消费者模型：

#include <pthread.h>
#include <stdio.h>

#include <stdlib.h>
#define BUFFER_SIZE 10

static int buffer[BUFFER_SIZE] = { 0 };
static int count = 0;

pthread_t consumer, producer;
pthread_cond_t cond_producer, cond_consumer;
pthread_mutex_t mutex;

void* consume(void* _){
  while(1){
    pthread_mutex_lock(&mutex);
    while(count == 0){
      printf("empty buffer, wait producer\n");
      pthread_cond_wait(&cond_consumer, &mutex);
    }

    count--;
    printf("consume a item\n");
    pthread_mutex_unlock(&mutex);
    pthread_cond_signal(&cond_producer);
    //pthread_mutex_unlock(&mutex);
  }
  pthread_exit(0);
}

void* produce(void* _){
  while(1){
    pthread_mutex_lock(&mutex);
    while(count == BUFFER_SIZE){
      printf("full buffer, wait consumer\n");
      pthread_cond_wait(&cond_producer, &mutex);
    }

    count++;
    printf("produce a item.\n");
    pthread_mutex_unlock(&mutex);
    pthread_cond_signal(&cond_consumer);
    //pthread_mutex_unlock(&mutex);
  }
  pthread_exit(0);
}

int main() {

  pthread_mutex_init(&mutex, NULL);
  pthread_cond_init(&cond_consumer, NULL);
  pthread_cond_init(&cond_producer, NULL);

  int err = pthread_create(&consumer, NULL, consume, (void*)NULL);
  if(err != 0){
    printf("consumer thread created failed\n");
    exit(1);
  }

  err = pthread_create(&producer, NULL, produce, (void*)NULL);
  if(err != 0){
    printf("producer thread created failed\n");
    exit(1);
  }

  pthread_join(producer, NULL);
  pthread_join(consumer, NULL);

  //sleep(1000);

  pthread_cond_destroy(&cond_consumer);
  pthread_cond_destroy(&cond_producer);
  pthread_mutex_destroy(&mutex);


  return 0;
}

死锁

死锁: 多个进程因循环等待资源而造成无法执行的现象。

死锁会造成进程无法执行，同时会造成系统资源的极大浪费(资源无法释放)。

死锁产生的4个必要条件：

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

死锁避免——银行家算法

思想: 判断此次请求是否造成死锁若会造成死锁，则拒绝该请求

进程间通信

本地进程间通信的方式有很多，可以总结为下面四类：

消息传递（管道、FIFO、消息队列）
同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
共享内存（匿名的和具名的）
远程过程调用（Solaris门和Sun RPC）

线程

线程，有时被称为轻量级进程(Lightweight Process，LWP），是程序执行流的最小单元。一个标准的线程由线程ID，当前指令指针(PC），寄存器集合和堆栈组成。

线程具有以下属性：

轻型实体线程中的实体基本上不拥有系统资源，只是有一点必不可少的、能保证独立运行的资源。线程的实体包括程序、数据和TCB。线程是动态概念，它的动态特性由线程控制块TCB（Thread Control Block）描述。TCB包括以下信息：
- 线程状态。
- 当线程不运行时，被保存的现场资源。
- 一组执行堆栈。
- 存放每个线程的局部变量主存区。
- 访问同一个进程中的主存和其它资源。
- 用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。
独立调度和分派的基本单位。
- 在多线程OS中，线程是能独立运行的基本单位，因而也是独立调度和分派的基本单位。由于线程很“轻”，故线程的切换非常迅速且开销小（在同一进程中的）。
可并发执行。在一个进程中的多个线程之间，可以并发执行，甚至允许在一个进程中所有线程都能并发执行；同样，不同进程中的线程也能并发执行，充分利用和发挥了处理机与外围设备并行工作的能力。
共享进程资源。在同一进程中的各个线程，都可以共享该进程所拥有的资源，这首先表现在：所有线程都具有相同的地址空间（进程的地址空间），这意味着，线程可以访问该地址空间的每一个虚地址；此外，还可以访问进程所拥有的已打开文件、定时器、信号量机构等。由于同一个进程内的线程共享内存和文件，所以线程之间互相通信不必调用内核。线程共享的环境包括：进程代码段、进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯)、进程打开的文件描述符、信号的处理器、进程的当前目录和进程用户ID与进程组ID。

协程

协程，又称微线程，纤程。英文名Coroutine。

协程可以理解为用户级线程，协程和线程的区别是：线程是抢占式的调度，而协程是协同式的调度，协程避免了无意义的调度，由此可以提高性能，但也因此，程序员必须自己承担调度的责任，同时，协程也失去了标准线程使用多CPU的能力。

使用协程改写生产者-消费者问题：

import time

def consumer():
    r = ''
    while True:
        n = yield r
        if not n:
            return
        print('[CONSUMER] Consuming %s...' % n)
        time.sleep(1)
        r = '200 OK'

def produce(c):
    c.next()
    n = 0
    while n < 5:
        n = n + 1
        print('[PRODUCER] Producing %s...' % n)
        r = c.send(n)
        print('[PRODUCER] Consumer return: %s' % r)
    c.close()

if __name__=='__main__':
    c = consumer()
    produce(c)

可以看到，使用协程不再需要显式地对锁进行操作

IO多路复用

基本概念

IO多路复用是指内核一旦发现进程指定的一个或者多个IO条件准备读取，它就通知该进程。IO多路复用适用如下场合：

当客户处理多个描述字时（一般是交互式输入和网络套接口），必须使用I/O复用。
当一个客户同时处理多个套接口时，而这种情况是可能的，但很少出现。
如果一个TCP服务器既要处理监听套接口，又要处理已连接套接口，一般也要用到I/O复用。
如果一个服务器即要处理TCP，又要处理UDP，一般要使用I/O复用。
如果一个服务器要处理多个服务或多个协议，一般要使用I/O复用。

与多进程和多线程技术相比，I/O多路复用技术的最大优势是系统开销小，系统不必创建进程/线程，也不必维护这些进程/线程，从而大大减小了系统的开销。

常见的IO复用实现

select(Linux/Windows/BSD Unix), epoll(Linux)，kqueue(BSD/Mac OS X)

内存分配

虚拟地址：用户编程时将代码（或数据）分成若干个段，每条代码或每个数据的地址由段名称 + 段内相对地址构成，这样的程序地址称为虚拟地址
逻辑地址：虚拟地址中，段内相对地址部分称为逻辑地址
物理地址：实际物理内存中所看到的存储地址称为物理地址
逻辑地址空间：在实际应用中，将虚拟地址和逻辑地址经常不加区分，通称为逻辑地址。逻辑地址的集合称为逻辑地址空间
线性地址空间：CPU地址总线可以访问的所有地址集合称为线性地址空间
物理地址空间：实际存在的可访问的物理内存地址集合称为物理地址空间
MMU(Memery Management Unit内存管理单元)：实现将用户程序的虚拟地址（逻辑地址） → 物理地址映射的CPU中的硬件电路
基地址：在进行地址映射时，经常以段或页为单位并以其最小地址（即起始地址）为基值来进行计算
偏移量：在以段或页为单位进行地址映射时，相对于基地址的地址值

虚拟地址先经过分段机制映射到线性地址，然后线性地址通过分页机制映射到物理地址。

虚拟内存

请求调页，也称按需调页，即对不在内存中的“页”，当进程执行时要用时才调入，否则有可能到程序结束时也不会调入

页面置换算法

FIFO算法
- 先入先出，即淘汰最早调入的页面。
OPT(MIN)算法
- 选未来最远将使用的页淘汰，是一种最优的方案，可以证明缺页数最小。
- 可惜，MIN需要知道将来发生的事，只能在理论中存在，实际不可应用。
LRU(Least-Recently-Used)算法
- 用过去的历史预测将来，选最近最长时间没有使用的页淘汰(也称最近最少使用)。
- LRU准确实现：计数器法，页码栈法。
- 由于代价较高，通常不使用准确实现，而是采用近似实现，例如Clock算法。

内存抖动现象：页面的频繁更换，导致整个系统效率急剧下降，这个现象称为内存抖动（或颠簸）。抖动一般是内存分配算法不好，内存太小引或者程序的算法不佳引起的。

Belady现象：对有的页面置换算法，页错误率可能会随着分配帧数增加而增加。

FIFO会产生Belady异常。

栈式算法无Belady异常，LRU，LFU（最不经常使用），OPT都属于栈式算法。

磁盘调度

磁盘访问延迟 = 队列时间 + 控制器时间 + 寻道时间 + 旋转时间 + 传输时间

磁盘调度的目的是减小延迟，其中前两项可以忽略，寻道时间是主要矛盾。

磁盘调度算法

FCFS
- 先进先出的调度策略，这个策略具有公平的优点，因为每个请求都会得到处理，并且是按照接收到的顺序进行处理。
SSTF(Shortest-seek-time First 最短寻道时间优先)
- 选择使磁头从当前位置开始移动最少的磁盘I/O请求，所以 SSTF 总是选择导致最小寻道时间的请求。
- 总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比 FCFS 算法更好的性能，会存在饥饿现象。
SCAN
- SSTF+中途不回折，每个请求都有处理机会。
- SCAN 要求磁头仅仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向上的最后一个磁道，或者在这个方向上没有其他请求为止。
- 由于磁头移动规律与电梯运行相似，SCAN 也被称为电梯算法。
- SCAN 算法对最近扫描过的区域不公平，因此，它在访问局部性方面不如 FCFS 算法和 SSTF 算法好。
C-SCAN
- SCAN+直接移到另一端，两端请求都能很快处理。
- 把扫描限定在一个方向，当访问到某个方向的最后一个磁道时，磁道返回磁盘相反方向磁道的末端，并再次开始扫描。
- 其中“C”是Circular（环）的意思。
LOOK 和 C-LOOK
- 釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK和C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求。

文件系统

分区表

MBR：支持最大卷为2 TB（Terabytes）并且每个磁盘最多有4个主分区（或3个主分区，1个扩展分区和无限制的逻辑驱动器）
GPT：支持最大卷为18EB（Exabytes）并且每磁盘的分区数没有上限，只受到操作系统限制（由于分区表本身需要占用一定空间，最初规划硬盘分区时，留给分区表的空间决定了最多可以有多少个分区，IA-64版Windows限制最多有128个分区，这也是EFI标准规定的分区表的最小尺寸。另外，GPT分区磁盘有备份分区表来提高分区数据结构的完整性。

RAID 技术

磁盘阵列（Redundant Arrays of Independent Disks，RAID），独立冗余磁盘阵列之。原理是利用数组方式来作磁盘组，配合数据分散排列的设计，提升数据的安全性。

RAID 0
- RAID 0是最早出现的RAID模式，需要2块以上的硬盘，可以提高整个磁盘的性能和吞吐量。
- RAID 0没有提供冗余或错误修复能力，其中一块硬盘损坏，所有数据将遗失。
RAID 1
- RAID 1就是镜像，其原理为在主硬盘上存放数据的同时也在镜像硬盘上写一样的数据。
- 当主硬盘（物理）损坏时，镜像硬盘则代替主硬盘的工作。因为有镜像硬盘做数据备份，所以RAID 1的数据安全性在所有的RAID级别上来说是最好的。
- 但无论用多少磁盘做RAID 1，仅算一个磁盘的容量，是所有RAID中磁盘利用率最低的。
RAID 2
- 这是RAID 0的改良版，以汉明码（Hamming Code）的方式将数据进行编码后分区为独立的比特，并将数据分别写入硬盘中。因为在数据中加入了错误修正码（ECC，Error Correction Code），所以数据整体的容量会比原始数据大一些，RAID2最少要三台磁盘驱动器方能运作。
RAID 3
- 采用Bit－interleaving（数据交错存储）技术，它需要通过编码再将数据比特分割后分别存在硬盘中，而将同比特检查后单独存在一个硬盘中，但由于数据内的比特分散在不同的硬盘上，因此就算要读取一小段数据资料都可能需要所有的硬盘进行工作，所以这种规格比较适于读取大量数据时使用。
RAID 4
- 它与RAID 3不同的是它在分区时是以区块为单位分别存在硬盘中，但每次的数据访问都必须从同比特检查的那个硬盘中取出对应的同比特数据进行核对，由于过于频繁的使用，所以对硬盘的损耗可能会提高。（块交织技术，Block interleaving）

RAID 2/3/4 在实际应用中很少使用

RAID 5
- RAID Level 5是一种储存性能、数据安全和存储成本兼顾的存储解决方案。它使用的是Disk Striping（硬盘分区）技术。
- RAID 5至少需要三块硬盘，RAID 5不是对存储的数据进行备份，而是把数据和相对应的奇偶校验信息存储到组成RAID5的各个磁盘上，并且奇偶校验信息和相对应的数据分别存储于不同的磁盘上。
- RAID 5 允许一块硬盘损坏。
- 实际容量 Size = (N-1) * min(S1, S2, S3 ... SN)
RAID 6
- 与RAID 5相比，RAID 6增加第二个独立的奇偶校验信息块。两个独立的奇偶系统使用不同的算法，数据的可靠性非常高，即使两块磁盘同时失效也不会影响数据的使用。
- RAID 6 至少需要4块硬盘。
- 实际容量 Size = (N-2) * min(S1, S2, S3 ... SN)
RAID 10/01（RAID 1+0，RAID 0+1）
- RAID 10是先镜射再分区数据，再将所有硬盘分为两组，视为是RAID 0的最低组合，然后将这两组各自视为RAID 1运作。
- RAID 01则是跟RAID 10的程序相反，是先分区再将数据镜射到两组硬盘。它将所有的硬盘分为两组，变成RAID 1的最低组合，而将两组硬盘各自视为RAID 0运作。
- 当RAID 10有一个硬盘受损，其余硬盘会继续运作。RAID 01只要有一个硬盘受损，同组RAID 0的所有硬盘都会停止运作，只剩下其他组的硬盘运作，可靠性较低。如果以六个硬盘建RAID 01，镜射再用三个建RAID 0，那么坏一个硬盘便会有三个硬盘脱机。因此，RAID 10远较RAID 01常用，零售主板绝大部份支持RAID 0/1/5/10，但不支持RAID 01。
- RAID 10 至少需要4块硬盘，且硬盘数量必须为偶数。

常见文件系统

Windows: FAT, FAT16, FAT32, NTFS
Linux: ext2/3/4, btrfs, ZFS
Mac OS X: HFS+

Linux文件权限

Linux文件采用10个标志位来表示文件权限，如下所示：

-rw-r--r--  1 skyline  staff    20B  1 27 10:34 1.txt
drwxr-xr-x   5 skyline  staff   170B 12 23 19:01 ABTableViewCell

第一个字符一般用来区分文件和目录，其中：

d：表示是一个目录，事实上在ext2fs中，目录是一个特殊的文件。
－：表示这是一个普通的文件。
l: 表示这是一个符号链接文件，实际上它指向另一个文件。
b、c：分别表示区块设备和其他的外围设备，是特殊类型的文件。
s、p：这些文件关系到系统的数据结构和管道，通常很少见到。

第2～10个字符当中的每3个为一组，左边三个字符表示所有者权限，中间3个字符表示与所有者同一组的用户的权限，右边3个字符是其他用户的权限。

这三个一组共9个字符，代表的意义如下：

r(Read，读取)：对文件而言，具有读取文件内容的权限；对目录来说，具有浏览目录的权限
w(Write,写入)：对文件而言，具有新增、修改文件内容的权限；对目录来说，具有删除、移动目录内文件的权限。
x(eXecute，执行)：对文件而言，具有执行文件的权限；对目录来说该用户具有进入目录的权限。

权限的掩码可以使用十进制数字表示：

如果可读，权限是二进制的100，十进制是4；
如果可写，权限是二进制的010，十进制是2；
如果可运行，权限是二进制的001，十进制是1；

具备多个权限，就把相应的 4、2、1 相加就可以了：

若要 rwx 则 4+2+1=7 若要 rw- 则 4+2=6 若要 r-x 则 4+1=5 若要 r-- 则 =4 若要 -wx 则 2+1=3 若要 -w- 则 =2 若要 --x 则 =1 若要 --- 则 =0

默认的权限可用umask命令修改，用法非常简单，只需执行umask 777命令，便代表屏蔽所有的权限，因而之后建立的文件或目录，其权限都变成000，

依次类推。通常root帐号搭配umask命令的数值为022、027和 077，普通用户则是采用002，这样所产生的权限依次为755、750、700、775。

chmod命令

chmod命令非常重要，用于改变文件或目录的访问权限。用户用它控制文件或目录的访问权限。

该命令有两种用法。一种是包含字母和操作符表达式的文字设定法；另一种是包含数字的数字设定法。

文字设定法
- chmod ［who］［+ | - | =］［mode］文件名
- 命令中各选项的含义为：
- 操作对象who可是下述字母中的任一个或者它们的组合：
  - u 表示“用户（user）”，即文件或目录的所有者。
  - g 表示“同组（group）用户”，即与文件属主有相同组ID的所有用户。
  - o 表示“其他（others）用户”。
  - a 表示“所有（all）用户”。它是系统默认值。
- 操作符号可以是：
  - 添加某个权限。
  - 取消某个权限。
  - = 赋予给定权限并取消其他所有权限（如果有的话）。
- 设置mode所表示的权限可用下述字母的任意组合：
  - r 可读。
  - w 可写。
  - x 可执行。
  - X 只有目标文件对某些用户是可执行的或该目标文件是目录时才追加x 属性。
  - s 在文件执行时把进程的属主或组ID置为该文件的文件属主。方式“u＋s”设置文件的用户ID位，“g＋s”设置组ID位。
  - t 保存程序的文本到交换设备上。
  - u 与文件属主拥有一样的权限。
  - g 与和文件属主同组的用户拥有一样的权限。
  - o 与其他用户拥有一样的权限。
- 文件名：以空格分开的要改变权限的文件列表，支持通配符。
- 在一个命令行中可给出多个权限方式，其间用逗号隔开。例如：chmod g+r，o+r example 使同组和其他用户对文件example 有读权限。
数字设定法
- 直接使用数字表示的权限来更改：
- 例： $ chmod 644 mm.txt

chgrp命令

功能：改变文件或目录所属的组。
语法：chgrp ［选项］ group filename
例：$ chgrp - R book /opt/local /book
改变/opt/local /book/及其子目录下的所有文件的属组为book。

chown命令

功能：更改某个文件或目录的属主和属组。这个命令也很常用。例如root用户把自己的一个文件拷贝给用户xu，为了让用户xu能够存取这个文件，root用户应该把这个文件的属主设为xu，否则，用户xu无法存取这个文件。
语法：chown ［选项］用户或组文件
说明：chown将指定文件的拥有者改为指定的用户或组。用户可以是用户名或用户ID。组可以是组名或组ID。文件是以空格分开的要改变权限的文件列表，支持通配符。
例：把文件shiyan.c的所有者改为wang。
chown wang shiyan.c