操作系统
一、概述
1、基本特征
（1）并发：并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。操作系统通过引入进程和线程使得程序能够并发运行；
（2）共享：共享是指系统中的资源可以被多个并发进程共同使用。共享的方式有两种：互斥共享和同时共享；其中互斥共享的资源成为临界资源，例如打印机等，在同一时间只允许一个进程访问，需要用同步机制来实现对临界资源的访问；
（3）虚拟：虚拟是指把一个物理实体转换为多个逻辑实体。主要的虚拟技术有两种：时分复用技术和空分复用技术；多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换；空分复用技术是指将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间和物理内存使用页进行交换，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法， 将该页置换到内存中；
（4）异步：异步只进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进；
2、基本功能
（1）进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度等；
（2）内存管理：内存分配、地址映射、内存保护与共享、虚拟内存等；
（3）文件管理：文件存储空间的管理、目录管理、文件读写管理和保护等；
（4）设备管理：完成用户的IO请求，方便用户使用各种设备，并提高设备的利用率。主要包括缓冲管理、设备分配、设备处理、虚拟设备等；
3、中断分类
（1）外中断：由CPU执行指令以外的时间引起，如IO完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等；
（2）异常：由CPU执行指令的内部时间引起，如非法操作码、地址越界、算术溢出等；
（3）陷入：在用户程序中使用系统调用；
二、进程管理
1、进程与线程
（1）进程：进程是资源分配的基本单位，进程控制块PCB描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对PCB的操作；每个进程都有独立的代码和数据空间（进程上下文），进程间的切换会有较大的开销，一个进程包含至少一个线程；
（2）线程：线程是CPU调度的基本单位，一个进程中可以有多个线程，它们共享进程资源；每个线程有独立的运行栈和程序计数器PC，线程切换开销小；
区别：
a.拥有资源：进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源；
b.调度：线程时独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换；
c.系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前进程CPU环境的保存及新调度进程CPU环境的设置，而线程切换时只需保存和设置少量寄存机内容，开销很小；
d.通信：线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助IPC；
2、线程状态切换
（1）新建状态（New）：新创建了一个线程对象；
（2）就绪状态（Runnable）：线程位于可运行线程池中，等待获取CPU的使用权；
（3）运行状态（Running）：就绪状态的线程获取了CPU，执行程序代码；
（4）阻塞状态（Blocked）：因为某种原因放弃CPU使用权，暂时停止运行。其原因主要有：等待阻塞（wait()）、同步阻塞（synchronized）、其他阻塞（sleep()、join()、I/O输入）；
（5）死亡状态（Dead）：线程执行完成了或因一场退出了run()方法；
3、进程同步
临界区：对临界资源进行访问的那段代码称为临界区；为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查；
同步：多个进程按一定顺序执行；
互斥：多个进程在同一时刻只有一个进程能进入临界区；
信号量：信号量是一个整型变量，可以对其执行down和up操作，也就是常见的P和V操作。
down：如果信号量大于0，执行-1操作；如果信号量等于0，进程睡眠，等待信号量大于0；
up：对信号量执行+1操作，唤醒睡眠的进程让其完成down操作；
down和up操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断；如果信号量的取值只能为0或者1，那么就成为了互斥量，0表示临界区已经加锁，1表示临界区解锁；
typedef int semaphore;
semaphore mutex = 1;void P1() {
down(&mutex);
// 临界区
up(&mutex);
}
void P2() {
down(&mutex);
// 临界区
up(&mutex);
}
经典同步问题：
生产者-消费者问题、读者-写者问题、哲学家进餐问题、理发师问题、烟鬼问题
4、进程通信
进程同步是控制多个进程按一定顺序执行，进程通信是进程间传输信息；进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息；
（1）管道：通常指无名管道，它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端，且只能在父子进程中使用，它不是普通的文件，并不属于其他任何文件，并且只存在于内存中；
（2）FIFO：也称命名管道，它是一种文件类型，可以在无关的进程之间交换数据，与无名管道不同，它由路径名与之相关联，以一种特殊设备文件形式存在于文件系统中。它的通信方式类似于在进程中使用文件来传输数据，只不过FIFO类型文件同时具有管道的特性，在数据读出时，FIFO管道中同时清除数据，并且“先进先出”；
（3）消息队列：是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识，它是面向记录的，其中的消息具有特定的格式以及特定的优先级。相比于FIFO，消息队列可以独立于读写进程存在，从而避免了FIFO中同步管道的打开和关闭时可能产生的困难；避免了FIFO的同步阻塞问题，不需要进程自己提供同步方法；读进程可以根据消息类型有选择地接收消息，而不像FIFO那样只能默认地接收；进程在终止时，消息队列及其内容并不会被删除，它可以实现消息的随机查询；
（4）信号量：它是一个计数器，用于为多个进程提供对共享数据对象的访问。它基于操作系统的PV操作，程序对信号量的操作都是原子操作，每次对信号量的操作不仅限于对信号量值的+1或-1，可以加减任意正整数，支持信号量组；
（5）共享内存：允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种IPC；需要使用信号量用来同步对共享内存的访问，多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外XSI共享内存不是使用文件，而是使用内存的匿名段；
（6）套接字：与其它通信机制不同的是，它可以用于不同机器间的进程通信；
5、进程调度
（1）先来先服务调度算法（FCFS）：按作业或者进程到达的先后顺序依次调度；有利于长作业，不利于短作业；
（2）短作业优先调度算法（SJF）：从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行。不利于长作业，未考虑作业的重要性，运行时间是预估的，并不靠谱；
（3）高响应比调度算法（HRN）：响应比=（等待时间+要求服务时间）/要求服务时间；
（4）时间片轮转调度算法（RR）：将所有就绪进程按FCFS的原则排成一个队列，每次调度时，把CPU时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把CPU时间分配给队首的进程；时间片轮转算法的效率和时间片的大小有很大关系，因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多的时间；但另一方面，如果时间片过长，那么实时性就不能得到保证；
（5）优先级调度算法：为每个进程分配一个优先级，按优先级进行调度；为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级；
（6）多级反馈队列调度算法：一个进程需要执行100个时间片，如果采用时间片轮转调度算法，那么需要交换100次；多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如1,2,4,8,…，进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换7次；每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程；可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合；
三、死锁
1、必要条件
（1）互斥：每个资源要么已经分配给了一个进程，要么就是可用的；
（2）请求和保持：进程被阻塞的时候并不释放锁请求到的资源；
（3）不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放；
（4）环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源；
2、处理方法
（1）鸵鸟策略：把头埋在沙子里，假装根本没有发生问题；因为解决死锁问题的代价很高，因此不采取任何措施的方案会获得更高的性能；当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略；
（2）死锁检测；每种类型一个资源的死锁检测、每种类型多个资源的死锁检测；
（3）死锁恢复：利用抢占恢复、利用回滚恢复、通过杀死进程恢复；
（4）死锁预防：破坏必要条件任意一条即可；
（5）死锁避免：银行家算法；
四、内存管理
虚拟内存：从逻辑的角度扩充内存容量，基于局部性原理，在程序装入的时候，可以将程序的一部分装入内存，而将其余部分留在外存就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入的内存的信息。这样，系统就好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器；
页面置换算法：在程序运行过程中，如果访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换去中来腾出空间；页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据；
（1）最佳置换算法：只具有理论意义的算法，用来评价其他页面置换算法；置换策略是将当前页面中在未来最长时间内不会被访问的页置换出去；
（2）先进先出置换算法：每次淘汰最早调入的页面，没有考虑页面的访问频率细信息。会使缺页率升高；
（3）最近最久未使用算法（LRU）：将最近最久未使用的页面换出；实现的时候需要在内存中维护一个所有页面的链表，当一个页面被访问时，将这个页面移到链表表头。这样每次只要找链表表尾的页面就是最近最久未访问的。因为每次访问都需要更新链表，因此这种方式实现的LRU代价很高；
（4）最近未使用算法（NRU）：每个页面都有两个状态位R与M，当页面被访问时设置页面的R=1，当页面被修改时设置页面的M=1。其中R位会定时被清零；当发生缺页中断时，NRU算法随机地从类编号最小的非空类中挑选一个页面将它换出；注意，NRU优先换出已经被修改的脏页面（R=0,M=1），而不是被频繁使用的干净页面（R=1,M=0）；
分页与分段的比较：
（1）对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段；
（2）地址空间的维度：分页是一维地址空间，分段是二维的；
（3）大小是否可以改变：页的大小不可变，段的大小可以动态改变；
（4）出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护；