进程与线程
进程
进程是一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。进程一般由程序、数据集合和进程控制块三部分组成。程序用于描述进程要完成的功能，是控制进程执行的指令集；数据集合是程序在执行时所需要的数据和工作区；程序控制块(Program Control Block，简称PCB)，包含进程的描述信息和控制信息，是进程存在的唯一标志。
进程具有的特征：
- 动态性：进程是程序的一次执行过程，是临时的，有生命期的，是动态产生，动态消亡的；
- 并发性：任何进程都可以同其他进程一起并发执行；
- 独立性：进程是系统进行资源分配和调度的一个独立单位；
- 结构性：进程由程序、数据和进程控制块三部分组成。
线程
线程是程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度和分派的基本单位。一个进程可以有一个或多个线程，各个线程之间共享程序的内存空间(也就是所在进程的内存空间)。一个标准的线程由线程ID、当前指令指针(PC)、寄存器和堆栈组成。而进程由内存空间(代码、数据、进程空间、打开的文件)和一个或多个线程组成。
区别
- 拥有资源
进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
- 调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
- 系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
- 通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。
状态的切换
- 就绪状态（ready）：等待被调度
- 运行状态（running）：正在运行
- 阻塞状态（waiting）：等待资源
应该注意以下内容：
- 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
- 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。
作业与进程的调度算法
先来先服务(FCFS)算法
短作业优先(SJF)调度算法
- 谁需要的服务时间最短就先服务谁
- 长作业可能会被饿死
优先级调度算法
- 选择优先级最高的进行服务
- 能否抢占低优先级
- 非剥夺式优先级调度算法
当一个进程在处理器运行时，即使有一个更高优先级的进程进入就绪队列，该高优先级的进程也必须等待低优先级进程退出处理器才能获取处理器
- 剥夺式优先级调度算法：
当一个进程在处理器运行时，当有一个更高优先级的进程进入就绪队列后，暂停正在运行的进程而将处理器分配给高优先级的进程
- 进程优先级能否改变
- 静态优先级：优先级在进程创建时确定，在进程整个运行期中保持不变
- 动态优先级：根据进程运行状况动态调整进程优先级
- 会产生饥饿状态
高响应比优先调度算法
- 是FCFS与SJF的综合平衡，同时考虑了每个进程的等待时间与估计运行时间，在每次作业调度时，先计算各作业响应比，选择响应比最高的作业调入内存
- 响应比 = (等待时间 + 要求服务时间) / 要求服务时间
- 克服了饥饿状态
时间片轮转调度算法
- 类似于FCFS算法，但每个进程仅能运行一个时间片，当进程时间片用完后，无论该进程是否完成，必须释放处理器给就绪队列中的下一个进程，而自身进入就绪队列末尾排队
- 时间片的大小对算法性能影响很大，过大的时间片使得每个进程在一个时间片中运行完成，也就使该算法退化为FCFS，过小的时间片，会使得花费在调度上的时间过多
- 时间片的选择通常由系统响应时间、就绪队列中进程数目、系统的处理能力共同决定
多级反馈队列调度算法
- 通过设置多个就绪队列，每个队列的优先级不同，高优先级队列中每个进程分配的时间片越小，每个进程最先进入优先级最高的就绪队列末尾，当该就绪队列中进程在属于该就绪队列的时间片中未运行完后，进入下一个优先级低一级的就绪队列中等待执行。系统总是爱高优先级队列为空时才执行下一优先级就绪队列中的进程
页面置换算法
在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
最佳(OPT)置换算法
- 选择以后不会被使用或最长时间内不再被访问的页面换出，以保证最低的缺页
- 由于是对未来的预测，该算法无法实现，但OPT常被用于评价其他算法
先进先出(FIFO)页面置换算法
- 选择最先进入内存的页面(在内存中滞留时间最长度的页面)换出
- FIFO实现简单，但该算法可能出现分配的页面数增多但缺页率反而提高的现象，称为Belady异常
- Belady异常
- stack algorithm
如果内存中页数更小的集合是内存页数更大的集合的子集，这个算法被称为stack algorithm。可以证明stack algorithm(如LRU)不会出现belady现象，FIFO会出现。
最近最久未使用(LRU)置换算法
- 选择最近最长时间未被访问的页面换出，该算法认为过去一段时间未被访问的页面在将来也不会被访问，采用过去预测将来
- LRU算法性能较好，但需要寄存器和栈的硬件支持，属于堆栈类算法，不会出现 Belady异常
- LRU性能接近OPT，但实现困难，且开销大
时钟(CLOCK)置换算法
- 简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法
- CLOCK算法性能比较接近LRU算法
- 为每个帧继续添加附加位，用于标识各个状态，形成各个改进的CLOCK算法
磁盘结构
- 盘面（Platter）：一个磁盘有多个盘面
- 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道
- 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小
- 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）
- 制动手臂（Actuator arm）：用于在磁道之间移动磁头
- 主轴（Spindle）：使整个盘面转动
磁盘调度算法
先来先服务(FCFS)
- 最简单的磁盘调度算法，根据进程访问磁盘的先后顺序进行调度
- FCFS具有公平性，在少量进程访问簇聚的文件扇区时有较好性能，但若大量进程竞争使用磁盘则性能接近随机调度
最短寻找时间优先(SSTF)
- 选择与当前磁头距离最近的磁道，以便每次寻找时间最短
- 可能产生饥饿现象
扫描算法(SCAN)
- SCAN算法在当前磁头移动方向上选择与当前磁头距离最近的请求作为下一次服务对象，当前方向的请求服务完后，就开始反向扫描。（就跟电梯的运行一样。先上到按的最上面的楼层，到了已按的最上面楼层后就不继续上，而是开始向下）
- 当磁头刚从里向外移动而超越了某一磁道时，恰好又有一进程请求访问此磁道，这时该进程必须等待。将磁头继续从里向外，然后再从外向里扫描完处于外面的所有要访问的磁道后，才处理该进程的请求，致使该请求的请求被大大的推迟。
循环扫描算法(C-SCAN)
- 在SCAN算法的基础上规定磁头单向移动提供服务，回返时直接快速移动到起始端(电梯到达最高楼后，直接瞬移到最下面)