秋季招生复习笔记 ：操作系统 主要复习要点
操作系统
操作系统主要是管理，分配，调用应用程序，同时能够在硬件接口和应用程序之间提供服务的应用程序
为什么需要操作系统 ？
操作系统本质上是一个能够和硬件沟通和调度的一个应用程序，而我们可以通过C语言等这类能够和硬件直接交互的语言来编写我们的软件。但是操作系统解决了一些我们常见的问题。
- 应用程序之间的内存管理和分配
- 应用程序之间的IO操作，包括但不限于磁盘IO，网络IO
- 应用程序的CPU资源调度和管理
- . . . . . .
虽然我们能够通过自己编写程序来完成这些操作甚至针对我们自己程序进行优化,但是当我们希望快速构建一个程序,亦或者我们的语言无法直接对硬件进行控制,那么我们就需要操作系统.
一般来说,操作系统主要分为两种 :
- 批处理系统 : 用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行。
- 分时系统 : 多个程序分时（分时间片）共享硬件和软件资源。
早期的大型机是典型的批处理系统,当时的系统设计就是为了计算大量的数据,因此,系统的高吞吐量才是设计的目标。而随着PC的普及，用户需要在操作系统中运行越来越多的程序，系统就需要对各个应用程序进行分时调度，这个阶段分时系统得到了蓬勃的发展。
内核态
什么是内核态 ？
内核态：控制计算机的硬件资源，并提供上层应用程序运行的环境。
我们能从图中看出，内核态是整个操作系统中最核心的位置，而设置内核态主要为了做一些安全性的保护。
在CPU的所有指令中，有一些指令是非常危险的，如果错用，将导致整个系统崩溃。所以，CPU将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统及其相关模块使用，普通的应用程序只能使用那些不会造成灾难的指令。
我们经常会听到一个概念——用户态内核态转换。用户态到内核态转化并不是随意发生的，一般来说分为三种情况。
- 系统调用 ：这是一种比较常见的操作，例如Java中获取Sync失败后阻塞，会被系统调用进入内核态
- 异常事件： 当CPU正在执行运行在用户态的程序时，突然发生某些预先不可知的异常事件，这个时候就会触发从当前用户态执行的进程转向内核态执行相关的异常事件，典型的如缺页异常
- 外围设备的中断：当外围设备完成用户的请求操作后，会像CPU发出中断信号，此时，CPU就会暂停执行下一条即将要执行的指令，转而去执行中断信号对应的处理程序，如果先前执行的指令是在用户态下，则自然就发生从用户态到内核态的转换。
系统调用的本质其实也是中断，相对于外围设备的硬中断，这种中断称为软中断。从触发方式和效果上来看，这三种切换方式是完全一样的，都相当于是执行了一个中断响应的过程。但是从触发的对象来看，系统调用是进程主动请求切换的，而异常和硬中断则是被动的。
Kernel四个特征
- 并发 : 在一段时间内能够有多个程序运行(并行指在一个时间点上多个程序运行,需要多个CPU)
- 共享 : 系统资源可以被多个程序共享，同时访问和互斥共享
- 异步 : 程序能够走走停停，不是一贯到底
- 虚拟 : 能够虚拟出其他的操作系统或者内存等内容
内存
内存(Memory)也被称为内存储器和主存储器，其作用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，操作系统就会把需要运算的数据从内存调到CPU中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也决定了计算机的稳定运行。
内存这部分内容是操作系统的重点部分，我们的程序基本都运行在内存之上，而随着CS的发展，又出现了虚拟内存等技术，因此这部分的学习需要有一个思路。
- 传统内存分配方式导致的碎片应该如何处理 ？
- 虚拟内存解决了什么 ？
- 什么是页帧页表 ？
- 常见的页面置换算法的进化过程
- 等等
这是我自己的一个学习思路，个人认为在学习一个东西的时候，虽然有很长的历史并且我们对于之前的版本并不需要投入很多精力，但是需要了解，因为想要构成一个体系，记忆清晰就需要归纳总结缺点和解决方式，就像页面置换算法中，从最开始的FIFO导致Belady现象，到后面的LRU，LFU导致的轮询消耗，最后通过时钟算法解决，后期又通过二次机会法对时钟算法进行了进一步优化。通过这种方式，能够有效提升一个人对于某个技术的理解和基因加深。
四个特点
- 抽象 : 应用程序访问到的地址空间应该是逻辑地址空间而非真实的地址空间
- 保护 : 应用程序不能访问到不属于自己的内存地址
- 共享 : 能够安全可靠让进程之间完成交互数据传递
- 虚拟化 : 能够虚拟化出更大的内存空间
虚拟化内存原理
当我们需要将一个应用程序加载到内存中的时候，发现内存空间不足，但是这个程序不会立即执行，可以先将他加载到磁盘上，然后需要时加载进入内存，再将不需要立即执行的任务加载到磁盘中，这样能够加载更多的程序，但是在执行效率上时不会改变的，因为真正的物理内存是不会发生变化。
虚拟内存空间可以为硬盘+内存的大小。
磁盘中主要防止访问较少，热度低，当前利用率不高的数据，而内存尽量防止利用率高的数据。
覆盖技术
把程序按照自身逻辑结构分为多个模块，每次不会将所有模块全部加载如系统(类似于类加载机制)，只有当使用到该模块和依赖模块时才会将其加载进入内存中。在Java中，虽然在编译期间会编译为.class文件，但是只有使用到的时候才会加载进入内存中，如果不需要也可以进行类卸载，但是实际中一般不会卸载类。
交换技术(Unix)
操作系统将一个完整的应用程序置换到外存中(整个地址空间),称之为sweep-out，当需要使用这部分内容是再导入内存中sweep-in，导出粒度一般大于页帧大小，性能消耗取决于内存中应用地址空间大小。
交换技术有以下几个问题 :
- 何时交换 : 只有当内存不足的时候才能够交换，换入换出需要进行读写，消耗性能很大
- 交换区大小 : 必须保证能够将内存中的数据全部写入交换区，需要维护一个足够大的交换区
- 程序
sweep-in重定位 : 当换出再换入后，可能程序在内存中位置已经改变，就需要重新定位，可以使用页表机制通过Table进行映射(动态地址映射)
虚存管理技术
覆盖技术需要手动完成，而交换技术需要交换整个应用的内存空间，所以希望能够有一种技术既能够像覆盖技术一样动态加载所需要的模块，又能像交换技术一样将暂时不适用的应用交换到磁盘中，虚存管理完成了这点。
执行流程
- 在装入程序时，并不会将程序完整装入，只需要装入当前执行程序和依赖程序，保证程序能够正常启动即可
- 程序在运行的过程中，发现访问的数据或者指令不存在，则触发缺页中断，将内容加载进入内存
- 操作系统会观察程序，当一些程序暂时不需要使用内存并不运行时，会将其换出到磁盘上以获得更多空间
程序局部性原理
- 时间局部性 : 一条指令的一次执行和下一次执行集中在一个短时期内
- 空间局部性 : 执行当前指令和附近指令，所访问的内存区域都在临近区域
当满足这两个局部性时，虚存管理才能够良好运行，因为当两个数据分布很远时，系统不得不将两个数据块导入内存以供使用，如果两个数据在一块内存块中，只需要加载一个即可。
虚存技术特点
- 具有大的用户空间 : 大小为硬盘+内存
- 部分交换 : 不交换整个应用程序，只交换页或者段
- 不连续 : 内存空间分配不连续，虚拟内存不连续
缺页中断
虚存管理将内存按照块划分存储进入磁盘，当读取数据时发现数据不在内存中而在磁盘上会触发缺页中断，系统会中断程序运行，将磁盘中数据读入内存，再次执行。当时间局部性和空间局部性满足度差时，会频繁触发缺页中断，效率会变得很低。
页表管理
局部页面置换算法
当缺页中断发生需要调入新的页面，但是内存已满则需要调出已有页，需要选择调出哪个。
页面置换算法目标在于尽量减少对于硬盘上的页面读写，减少换入换出次数，提高性能，并且需要锁定常驻内存，例如操作系统的内存地址，确保操作系统能够正常工作。
最优页面置换算法(评价标准)
当一个缺页产生时，对于保存在内存中的一个页面，计算下次访问该页的时间，还需要等待多长时间，选择等待时间最长的那个页面，作为置换页面。这只是一种理想情况，系统无从知道一个页面之后多长时间会被访问。
FIFO
将所有的页维护在一个队列中，每次替换存活时间最长的一个页，将换入的页放入队列末尾，这种方法性能较差，调出的可能是经常访问的页。
LRU
LRULeast Recently Used，当一个缺页产生，选择最久未被使用的一个页进行替换，LRU算法是通过过去的状态来决定对哪个页进行替换，替换效果很好，但是在实际中需要使用队列或者栈来维护每一个页帧的最近使用时间，而每一次访问都需要对链表进行完全遍历，找到对应页帧进行时间的更新，这个操作消耗非常大，通常不会被采用
时钟算法
ACCESS标记位
在页表中，会有映射标记，访问标记和物理页地址。
- 映射标记 : 该页是否在内存中有映射，没有的化使用会触发缺页中断
- 访问标记 : 该页是否被访问，被访问后会置为1
- 物理页地址 : 逻辑内存根据TABLE查找到的物理页地址
而时钟算法会利用访问标记来完成时间记录，在内部会维护一个环形链表，将这些页标签存入其中，每当时钟扫描到一个访问标记为0的页时会将其置换，遇到访问为1的页会将其置为0。指针循环访问这些页。
这样能够保证访问次数多的页能够比较容易被标记为1，存活的概率会更大，同生能够保证一个较少的消耗。
二次机会法
当程序对某个页进行了写操作，会将access和dirty都置为1，这两位的作用如下两种情况 :
- 程序对页只读 : 当程序将硬盘上的内容写入内存，但是只读，由于数据未发生变化，那么再次置换本页时只需要将内存中内容丢弃即可。
- 程序对页写入 : 当程序对页进行了写操作，表明内存中的数据和硬盘不一致，再次置换时，就需要将内容重新写入到硬盘中
在二次机会算法中，只有当access和dirty都是0时才会被置换，而每次指针扫过，都会将access或者dirty中某个1置为0。在这种算法下，只读页会优先换出，写入页会滞后换出，可以说是对时钟算法的一种增强。
LFU
LFULeast Frequently Used算法指当缺页中断发生时，选择访问次数最少的那个页面进行替换，在每个页内部维护一个计数器，当被访问时，计数器加一，每次替换时，都选择最小的页进行替换。
LRU和LFU一样，因为维护计数器，会消耗大量的资源。
Belady现象
采用FIFO算法时，给程序分配的页越多，反而出现缺页的情况越严重
由于FIFO算法不会根据页访问频率时间来决定替换，而是根据先后顺序，当分配越多时，链表中存储头部越多，更加容易被新的页替换掉，所以当分配的页越多，越容易初恋缺页。
因此，Belady主要出现原因是对内存动态划分的缺少。
全局页面替换算法
程序对于内存的使用时动态变化的，可能在开始时需要大量内存，但是后期是使用的很少，所以需要全局页面置换算法来完成。
工作集
一个进程当前正在使用的逻辑页面的集合。可以理解为一个滑动窗口，近期访问的页是否在这个滑动窗口中。如下图
常驻集
常驻集指当前时刻，实际驻留在物理内存中的页面的集合
我们希望工作集尽量能够和常驻集进行重叠，当二者不重叠时，则会触发缺页中断。
工作集页置换算法
在局部页面置换算法中，一般只有内存不够使用才进行页面置换，但是在全局算法中，一般一个页在之后一段时间内不会被使用，就需要被移出内存，如下图。
维护一个滑动窗口，这个滑动窗口内时应用程序所需要使用到的页，当其中有的页不在内存中，则需要从磁盘引入，如果执行过后，该页在滑动窗口内不存在，如A在滑动窗口中没有再次重复，则A这个页会被置换到磁盘中。
工作集窗口主要就是维护当前及之后一段时间内所需要的页，当之后没有某个页时，这个页会被置换到磁盘。
逻辑地址 & 物理地址
一般应用程序所使用的地址空间都是逻辑地址空间，类似于数组的线性结构，通过起始地址和偏移量来规定大小。
而在操作系统中会维护一个逻辑地址空间和物理地址空间的表来体现对应关系。
内存碎片问题
内存碎片有两种 : 内碎片和外碎片
- 内碎片 : 系统给应用程序分配的内存应用程序无法完全使用，内部浪费了一部分内存，属于内碎片
- 外碎片 : 某些未分配的内存太小，无法再分配给其他的应用使用，产生了外碎片
页表机制
大部分操作系统对于内存碎片解决办法是内存段+页表的模式，首先OS为每个应用程序分配一段内存，然后这段内存会被分为许多个很小的页帧(Frame)，同样创建一个逻辑内存，逻辑内存中的划分是连接有序的，然后维护一张页表，来连接逻辑内存和物理内存的地址关系。
页表机制带来的好处是能够最大程度减少内存碎片的存在，虽然再逻辑内存中，应用程序是按照一整块内存分配，但是在物理内存中，这些分配被打乱，分配在不同的页帧上frame，每个页帧一般都不会很大，即使页帧无法完全使用，所造成的浪费也是可以接受的。
但是页表机制也会带来一些问题，例如会消耗额外的内存，每次分配内存都需要多查找一次页表然后再通过页表查找物理内存，会消耗额外的时间。
一级页表和二级页表
如果页表中offset偏移量为8KB，那么我们寻址一个数据需要扫描这8KB内容，是比较浪费时间的，而二级页表中维护了这8KB内容的offset，例如我们希望找一个变量num，首先找到这个变量在一级页表中的173位置，然还再进入二级页表找到它的位置，整体结构类似于Map<Integer,Map<Integer,address>>，能够有效提升查询效率，当然也浪费了一定存储空间。
同理，可以在二级页表中维护更为详细的地址，这样就形成了树形的多级页表
一般分配方式
- 最优满足分配 : 将剩余内存中的地址选择一块最小的能够满足应用程序的内存，能够保留较大的整块内存，但是内存碎片较多
- 最差满足分配 : 每次都选择最大的内存地址分配内存，然还拆分，产生碎片更少，但是不会剩下大块的内存空间
为了清理内存碎片，有两种方法
- 内存压缩方法 : 将内存中的内存段迁移，将碎片压成一块完整内存，只有在程序不处于正在执行的状态才能移动，如果内存已经爆满，则无法压缩
- 置换方法 : 利用虚拟内存，将一些暂停的程序移动到磁盘上，然后移动内存完成碎片清理
进程和线程
线程
由于进程之间拥有各自的内存空间，当需要进程通讯时，就需要操作系统进行调度，提高了进程间访问数据的代价。而线程共享同一片内存区域，访问无阻碍，能有效提高并发的效率。
线程是进程的组成部分，是其中的一条执行流程。
- 一个进程中可以拥有多个线程
- 各个线程并发执行
- 各个线程之间可以访问共享地址的资源
进程
进程 : 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程，一个进程应该包括程序代码，程序数据，程序计数器，寄存器例如堆/栈，系统资源(内存，网络，文件系统)
程序是静态的代码，进程是程序执行的过程，所以程序是产生进程的基础，一个程序拥有多个进程。
进程在执行的过程中有核心态和用户态
- 核心态 : 执行一些操作系统的功能，例如文件读取，线程阻塞等情况
- 用户态 : 使用自身的功能，例如修改自身程序变量等
进程的特点 :
- 动态性 : 进程能够被动态的创建和销毁
- 并发性 : 进程能够被独立调度并占有处理器
- 独立性 : 多个进程相互不影响
- 制约性 : 因为访问共享数据或进程间同步而相互制约
进程的生命周期
进程创建
进程创建主要有三个情况
- 系统初始化时会创建
init进程 - 用户创建使用应用程序时创建新的进程
- 一个进程调用创建进程方法，例如
fork时，创建进程
进程就绪与运行
当进程创建完成后，进入ready状态，此时需要等待操作系统分配时间片，如果分配到则运行，如果没有分配到就进入阻塞(等待)
进程等待
一般如下情况会导致进程等待，在等待状态时不消耗CPU的资源，进入等待状态会让出CPU执行权
- 请求的系统服务无法立刻完成
- 启动某种操作，无法立刻完成
- 需要的数据还未到达
进程结束
- 正常退出(自愿)
- 错误退出(自愿,程序出现异常)
- 致命错误(强制杀死)
- 被其他进程杀死(强制性的)
进程挂起和进程阻塞
进程阻塞 : 进程阻塞指该进程所需要的条件无法立即获得，进入等待状态，让出CPU执行权，但是依旧占用内存
进程挂起 : 进程挂起指进程进入挂起状态，不在占用内存空间，该进程映像在磁盘之上
进程挂起有两种状态 :
- 阻塞挂起 : 此时进程在外存并等待某个事件
- 就绪挂起 : 进程在外存，但是一旦写入内存后就能够运行
挂起(Suspend)
把一个进程从内存转为外存的过程称为挂起
- 阻塞到阻塞挂起 : 但一个进程处于阻塞状态，挂起后依旧是阻塞状态
- 就绪到就绪挂起 : 当由高优先级就绪状态和低优先级就绪状态的进程，系统会挂起低优先级的就绪状态进程
- 运行到就绪挂起 : 对于抢占系统，可能根据优先级将运行状态的进程挂起为就绪状态
- 阻塞到就绪挂起 : 在外存中，某个阻塞挂起状态的线程所需的资源满足，系统会将阻塞挂起状态改为就绪挂起状态
进程创建函数
fork
当一个进程调用了fork函数后，会根据当前进程创建一个几乎一样的子进程，这两个进程可以做同样的事情，但是如果传参不同结果可能不同。
进程调用fork()后，系统会给新的进程分配资源，并将当前进程的数据复制到新的进程之中，相当于克隆了自己。
fork()函数调用后，会产生两个返回值 :
- 在父进程中返回子进程的进程id(pid)
- 在子进程中，fork返回0
- 如果出现错误，fork返回负值
而fork()可能出错有两种原因 :
- 当前进程数量已经到达系统规定上限
- 系统内存不足，无法再进行进程创建
exec
当进程调用了fork()后会将父进程的资源全部复制，但是大部分情况我们都希望子进程运行的是和父进程不同的内容，例如参数不同，处理的IO不同(Redis中的多路复用)，所以在子进程中调用exec()方法能够重新加载代码段，但是同样会带来一些问题。
- 每次都要复制父进程的内容但是不适用，消耗资源
- 子进程可能关闭打开的文件和连接
vfork
vfork函数是轻量级的fork()，vfork只创建一个进程的系统调用，而不会复制内存中的数据，并且创建后立刻调用exec()
常见进程调度算法
一个CPU核心只能在同一时间处理一个进程的请求，如何分配处理时间是操作系统需要关注的重点，一般有如下几种算法。
FCFS先到先服务算法
FCFSFirst Come First Service算法是最简单的调度算法，所有的进程就绪后都会进入队列排队，CPU资源分配过程严格按照队列顺序。
- 优点 : 实现简单，有利于长作业
- 缺点 : 效率低，容易造成任务积压
FCFS是典型适用于CPU繁忙场景，该模型能够减少多个任务之间的挂起切换等情况，能够提高CPU在一段时间之内的吞吐量。但是不利于I/O繁忙或者高响应模型，因为只有一个任务执行完成后才能执行另一个，这样会导致出现长任务阻塞后面任务执行，响应较慢。
时间片轮询算法
时间片轮询算法是一种分时系统所使用的算法，系统会为每个进程分配相同的时间片，当执行完当前事件后切换下一个进程，如果在时间内任务未完成，则会被添加到队列末尾等待下一次时间片的分配。
在时间片轮询算法中，时间片大小的选择是非常重要的，如果选择太大，则可能进程提早执行完成，CPU空耗，如果太小则会造成太多的切换损耗性能。
SJF短作业优先算法
短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。
短作业优先调度算法是一个非抢占策略，他的原则是下一次选择预计处理时间最短的进程，因此短进程将会越过长作业，跳至队列头。该算法即可用于作业调度，也可用于进程调度。但是他对长作业不利，不能保证紧迫性作业（进程）被及时处理，作业的长短只是被估算出来的。
缺点 :
- 该算法对长作业不利，SJF调度算法中长作业的周转时间会增加。更严重的是，如果有一长作业进入系统的后备队列，由于调度程序总是优先调度那些 (即使是后进来的）短作业，将导致长作业长期不被调度（“饥饿”现象，注意区分“死锁”。后者是系统环形等待，前者是调度策略问题）。
- 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。
- 由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
最短剩余时间算法
最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。
高响应比率算法
比率公式 R = (w+s)/s （R为响应比，w为等待处理的时间，s为预计的服务时间）
如果该进程被立即调用，则R值等于归一化周转时间（周转时间和服务时间的比率）。R最小值为1.0，只有第一个进入系统的进程才能达到该值。调度规则为：当前进程完成或被阻塞时，选择R值最大的就绪进程，它说明了进程的年龄。当偏向短作业时，长进程由于得不到服务，等待时间不断增加，从而增加比值，最终在竞争中赢了短进程。和最短进程优先、最短剩余时间优先一样，使用最高响应比策略需要估计预计服务时间。
高响应比优先调度算法主要用于作业调度，该算法是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
- 当作业的等待时间相同时，则要求服务时间越短，其响应比越高，有利于短作业。
- 当要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
- 对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。克服了饥饿状态，兼顾了长作业。
优先级调度算法
优先级调度算法又称优先权调度算法，该算法既可以用于作业调度，也可以用于进程调度，该算法中的优先级用于描述作业运行的紧迫程度。
在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。
根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为：
- 非剥夺式优先级调度算法。当某一个进程正在处理机上运行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在运行的进程继续运行，直到由于其自身的原因而主动让出处理机时（任务完成或等待事件），才把处理机分配给更为重要或紧迫的进程。
- 剥夺式优先级调度算法。当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。
而根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：
- 静态优先级。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。
- 动态优先级。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短。
多级反馈队列调度算法(重点)
多级反馈队列算法，不必事先知道各种进程所需要执行的时间，他是当前被公认的一种较好的进程调度算法。
多级反馈队列调度算法的实现思想如下：
- 应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。
- 赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。例如，第2级队列的时间片要比第1级队列的时间片长一倍， ……第i+1级队列的时间片要比第i级队列的时间片长一倍。
- 当一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样地按FCFS 原则等待调度执行；如果它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 n 级队列后，在第 n 级队列中便釆用时间片轮转的方式运行。
- 仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行；仅当第1 ~ (i-1)级队列均为空时，才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列（第 1 ~ (i-1)中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理机分配给新到的更高优先级的进程。
进程通信(IPC)
由于进程的特点是内存空间互不干扰，所以当进程之间需要通信的时候，不能够像线程一样直接读取对方的内容，所以操作系统必须实现进程间通讯的功能。
一般来说有管道，消息队列，信号量，共享内存,Socket和streams等方式来实现进程间的通讯。
匿名管道 & 命名管道
匿名管道是在内核中创建一块固定大小的缓冲区，程序具有读取和写入的权力，匿名管道有如下特点
- 只能在具有血缘关系的进程间使用，一般是在
fork中通讯 - 半双工，只能够单向通讯，而如果希望双向通讯，则需要维护两个管道
- 自带同步互斥机制
- 生命周期随内核
而命名管道可以理解为一种能够在所有线程之间通讯的匿名管道，没有了进程血缘限制。
消息队列
系统会在内存中创建一个队列链表，其中每个元素都是一个数据报，不同的线程可以访问队列获取他们需要的信息。
消息队列具有上限长度，当到达上限后，进程无法再写入消息数据报。
- 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
- 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
- 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
- 消息队列实现了双向通讯
信号量
在内核中创建一个信号量集合（本质是个数组），数组的元素（信号量）都是1，使用P操作进行-1，使用V操作+1，
-
P(sv)如果sv的值⼤大于零，就给它减1；如果它的值为零，就挂起该进程的执⾏ 。 -
V(sv)如果有其他进程因等待sv而被挂起，就让它恢复运⾏，如果没有进程因等待sv⽽挂起，就给它加1。
当PV操作作用于同一进程，实现了互斥，作用于不同进程，实现了同步
互斥指两个进程不能同时访问某个资源，同步则更进一步，指多个进程按照某个顺序访问某个资源
共享内存
将同一块物理内存一块映射到不同的进程的虚拟地址空间中，实现不同进程间对同一资源的共享，共享内存可以说是最有用的进程间通信方式，也是最快的IPC形式。
- 不用从用户态到内核态频繁切换和拷贝数据，直接内存读取
- 共享内存是临界资源，操作时必须保证原子性。一般使用信号量和互斥锁
- 生命周期随内核
Socket & Streams
其他四种通信方式是适用于本机进程，当进程在不同机器上，可以使用socket和strams来完成，使用IP地址和端口号来对指定机器中的某个线程进行通讯，严格来说这种通讯方式算TCP网络通讯。
IO
BIO 和 NIO
阻塞IO和非阻塞IO最大的区别是面向不同
- BIO面向流，只能保证单工通讯，需要有输入流和输出流
- NIO面向缓冲区，能双向通讯，需要使用channel技术
流类似于水管，所有信息都已byte的形式来发送，程序通过byte数组接收。
而通道本身如同铁路，自身并不具有信息承载的能力，缓冲区类似于火车，将信息填满缓冲区后，缓冲区在通道中传输。
在Java中可以通过allocate方法获取buffer。
public void getBuffer() {
ByteBuffer byteBuffer = ByteBuffer.allocate(1024);
}
缓冲区
缓冲区的核心属性
- capacity : 容量，缓冲区中最大存储数据容量 ，一旦声明，不能改变(缓冲区底层就是数组，数组长度不能改变)
- limit : 表示缓冲区中可以操作数据的大小(limit后数据不能进行读写)
- position : 缓冲区中正在操作的位置 (position < limit <capacity)
- mark : 标记当前position的位置，通过remark回到原来的位置
有两种缓冲区，直接缓冲与非直接缓冲
- 直接缓冲区 : 将缓冲区建立在OS的物理内存中(创建销毁消耗资源，不易控制)
- 非直接缓冲区 : 将缓冲区建立在JVM的内存模型中(效率低一点)
分散读取与聚集写入
- 分散读取 : 将通道中的数据读取到多个缓冲区中
- 聚集写入 : 将多个缓冲区数据聚集到一个通道中
阻塞与非阻塞
阻塞式 :
每次调用IO后，都会先访问应用进程内核，如果没有数据，则等待，有数据，内核开始向应用进程复制，复制完成后，应用进程恢复，整个过程中都是阻塞的，例如Socket，在accept过程中，无法调用其他操作。
好处 :
- 操作简单，实现方便
劣势 :
- 虽然可以使用多线程解决阻塞问题，但是仍然会有线程被阻塞，浪费线程资源
非阻塞 :
系统会通过轮询的方式来访问内核，查看是否准备完成，完成则进行复制。
好处 :
- 线程不被阻塞，在非复制过程中，能够执行其他任务
坏处 :
- 轮询会浪费CPU执行时间，降低吞吐量
- 轮询时间过长可能导致任务早已准备完，但是延后，时间过短消耗CPU资源过大
select/poll/epoll(重点)
阻塞IO复制过程
- 等待数据传输到内核空间(
kernel) - 内核空间中数据复制到用户空间(
user space)
在线程阻塞期间并不会浪费CPU资源,CPU只是不会再执行IO操作。
Select
应用线程申请IO后将有select处理，select监控多个IO。select会代替应用线程进行阻塞，当数据在内核空间中拷贝完毕时，将通知应用线程，然后应用线程阻塞复制。
缺点 :
- 根据
fd_size的定义，它的大小为32个整数大小，所以最多只能够监控1024个文件描述符 - 每次判断有哪些事件发生是一个成本很高的操作，因为采用轮询方式(对fd数组轮询)，CPU消耗
Poll
poll的原理与select非常相似，差别如下：
- 描述fd集合的方式不同，poll使用 pollfd 结构而不是select结构fd_set结构，所以poll是链式的，没有最大连接数的限制
- poll有一个特点是水平触发，也就是通知程序fd就绪后，这次没有被处理，那么下次poll的时候会再次通知同个fd已经就绪。
假设现实中，有1百万个客户端同时与一个服务器保持着tcp连接，而每一个时刻，通常只有几百上千个tcp连接是活跃的，这时候我们仍然使用select/poll机制，kernel必须在搜寻完100万个fd之后，才能找到其中状态是active的，这样资源消耗大而且效率低下。
Epoll
总结一下select/poll缺点，需要主动轮询，监控数量有限，需要将fd复制进入kernel。
在epoll中提供了如下三个函数
int epoll_create(int size) : 建立一个epoll对象，并传回id
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event) : 事件注册函数，将监听事件和需要监听的fd交给epoll的对象
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)等待注册的事件被触发或者timeout时发生
这三个函数解决了以上这些问题 :
- epoll使用监听对象来监听fd，没有上限，最大数量和机器内存有关(约1G = 10w个)
- epoll不需要每次都将fd_set复制进入内核空间，在注册时就已经完成复制
- epoll是被动触发方式，内部维护了一个就绪队列，当一个任务完成时将自己主动加入队列，epoll工作就是查看这个队列有没有就绪的fd。
- 虽然epoll。poll。epoll都需要查看是否有fd就绪，但是epoll之所以是被动触发，就在于它只要去查找就绪队列中有没有fd，就绪的fd是主动加到队列中，epoll不需要一个个轮询确认。 换一句话讲，就是select和poll只能通知有fd已经就绪了，但不能知道究竟是哪个fd就绪，所以select和poll就要去主动轮询一遍找到就绪的fd。而epoll则是不但可以知道有fd可以就绪，而且还具体可以知道就绪fd的编号，所以直接找到就可以，不用轮询。