1、操作系统基础
操作系统提供的服务
作业管理、文件管理、存储管理、输入输出设备管理、进程及处理器管理
中断
所谓的中断就是在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类：
- 内部异常中断：由计算机硬件异常或故障引起的中断
- 软中断：由程序中执行了引起中断的指令而造成的中断
- 外部中断：由外部设备请求引起的中断，比如I/O请求
中断处理函数：操作系统内核中对中断进行处理的特定函数
中断优先级：机器错误 > 时钟 > 磁盘 > 网络设备 > 终端 > 软件中断
系统调用
程序的执行一般是在用户态下执行的，但当程序需要使用操作系统提供的服务时，比如说打开某一设备、创建文件、读写文件等，就需要向操作系统发出调用服务的请求，这就是系统调用。
2、进程管理
一些定义
进程定义：进程是指一个正在运行的程序的实例
进程与线程的区别：进程是操作系统资源分配的最小单位，线程是操作系统中调度的最小单位。
进程的基本状态：阻塞、就绪、运行
进程的组成
- 程序的代码
- 程序处理的数据
- 程序计数器的值、指示下一条将运行的指令
- 一组通用的寄存器的当前值，堆、栈
- 一组系统资源（如内存资源，文件系统，网络等一系列资源）
进程与程序的关系
- 程序是产生进程的基础
- 程序的每次运行构成不容的进程
- 进程是程序功能的体现
- 通过多次执行，一个程序可以对应多个进程；通过调用关系，一个进程可以包含多个程序
进程与程序的区别：
- 进程是 动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行，进程有核心态用户态
- 进程是 暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存
- 进程与程序的组成不同：进程的组成包括程序，数据和进程控制块(即进程状态信息)
进程控制结构（PCB）
- 进程控制块：操作系统管理控制进程运行所用的信息集合。
- 操作系统用PCB来描述进程的基本情况以及运行变化过程，PCB是进程存在的唯一标志。
- 进程的创建：为该进程生成一个PCB
- 进程终止：回收它的PCB
- 进程的组织管理：通过对PCB的组织管理来实现
PCB包含的信息
进程标识信息。如本进程的标识，本进程的产生者标识(父进程标识)；用户标识。
处理器（CPU）状态信息保存区。保存进程的运行现场信息：
- 用户可见寄存器，用户程序可以使用数据，地址等寄存器。
- 控制和状态寄存器，如程序计数器(PC)，程序状态字(PSW)。
- 栈指针，过程调用/系统调用/中断处理和返回时需要用到它。
进程控制信息
- 调度和状态信息，用于操作系统调度进程并占用处理机使用。
- 进程间通信信息，为支持进程间与通信相关的各种标识，信号，信件等，这些信息存放在接收方的进程控制块里面。
- 存储管理信息，包含有指向本进程影像存储空间的数据结构。
- 进程所用的资源，说明由进程打开，使用的系统资源，如打开的文件等。
- 有关数据结构连接信息，进程可以连接到一个进程队列中，或连接到相关的其他进程的PCB。
僵尸进程：进程已经“死亡”，但task_struct结构还保存在进程列表中，半死不活，故称为“僵尸进程”
孤儿进程：在回收僵尸进程之前，如果父进程退出了，则僵尸进程变为“孤儿进程”，进而被init进程接管、回收
进程调度
- 先来先服务调度算法FCFS：既可以作为作业调度算法也可以作为进程调度算法；按作业或者进程到达的先后顺序依次调度；因此对于长作业比较有利；
- 短作业优先调度算法SJF：作业调度算法，算法从就绪队列中选择估计时间最短的作业进行处理，直到得出结果或者无法继续执行；缺点：不利于长作业；未考虑作业的重要性；运行时间是预估的，并不靠谱 ；
- 高相应比算法HRN： 响应比=(等待时间+要求服务时间)/要求服务时间；
- 时间片轮转调度RR：按到达的先后对进程放入队列中，然后给队首进程分配CPU时间片，时间片用完之后计时器发出中断，暂停当前进程并将其放到队列尾部，循环 ;
- 多级反馈队列调度算法：目前公认较好的调度算法；设置多个就绪队列并为每个队列设置不同的优先级，第一个队列优先级最高，其余依次递减。优先级越高的队列分配的时间片越短，进程到达之后按FCFS放入第一个队列，如果调度执行后没有完成，那么放到第二个队列尾部等待调度，如果第二次调度仍然没有完成，放入第三队列尾部…。只有当前一个队列为空的时候才会去调度下一个队列的进程。
- 优先级：按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法。
死锁
死锁产生的四个必要条件：
- 互斥使用：指进程对所分配到的资源进行排它性使用
- 不可抢占：指进程已获得的资源，在未使用之前，不能被剥夺，只能在使用完成时由自己释放
- 请求和保持：指进程已经保持至少一个资源，但是又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放
- 循环等待：在发生死锁时，必然存在一个进程-资源的环形链
死锁处理
- 预防死锁：破坏产生死锁的4个必要条件中的一个或者多个；实现起来比较简单，但是如果限制过于严格会降低系统资源利用率以及吞吐量
- 避免死锁：在资源的动态分配中，防止系统进入不安全状态(可能产生死锁的状态)-如银行家算法
- 检测死锁：允许系统运行过程中产生死锁，在死锁发生之后，采用一定的算法进行检测，并确定与死锁相关的资源和进程，采取相关方法清除检测到的死锁。实现难度大
- 解除死锁：与死锁检测配合，将系统从死锁中解脱出来（撤销进程或者剥夺资源）。对检测到的和死锁相关的进程以及资源，通过撤销或者挂起的方式，释放一些资源并将其分配给处于阻塞状态的进程，使其转变为就绪态。实现难度大
破坏死锁产生的四个条件
破坏“互斥使用/资源独占”条件：把独占资源变成共享资源
破坏“占有且等待”条件：
- 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
- 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配
破坏“不可抢占”条件：适用于状态易于保存和恢复的资源（CPU、内存）
破坏“循环等待”条件：通过定义资源类型的线性顺序实现，把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配
进程间通信
本地进程间通信的方式有很多，可以总结为下面四类：
- 消息传递（管道、FIFO、消息队列）
- 同步（互斥量、条件变量、读写锁、文件和写记录锁、信号量）
- 共享内存（匿名的和具名的）
- 远程过程调用（Solaris门和Sun RPC）
3、内存管理
虚拟内存
虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
分页系统地址映射
内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。
一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。
物理地址和虚拟地址
现代操作系统中，进程是运行在虚拟地址空间上的。比如在32位机器上，进程可以认为自己有4GB的内存空间可以使用。
现代的硬件一般是以分页的方式管理内存的。一个虚拟页映射到一个物理页。
在虚拟地址中连续的地址，在物理上可能是碎片似的分散在内存条的各个地方，但是在一个页内，地址是连续地一一对应的。
要把一个虚拟地址转换成物理地址，其实就是要知道该虚拟地址所在的虚拟页对应的物理页。知道了物理页，再加上页内偏移量即可。
Linux为每一个进程都维护了一个页表，放在内存中。页表的每一项就是一个虚拟页号对应的物理页号。
如果能够访问到页表，那么就能够把虚拟地址转换成物理地址。然而，只有在内核态才有权限访问页表，用户态是无权访问的。
页面置换算法
- 最佳：所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。
- 最近最久未使用（LRU）：为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。
- 最近未使用：每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
- 先进先出：选择换出的页面是最先进入的页面
- 第二次机会算法：FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
- 时钟：第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。
分段
虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。
下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。
分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
段页式
程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。
分页与分段的比较
- 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
- 地址空间的维度：分页是一维地址空间，分段是二维的。
- 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
- 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护