text: 操作系统中的磁盘调度算法
  操作系统是 管理和控制 计算机 硬件和软件资源 的计算机程序 ，是直接运行在 “裸机”上的最基本的系统软件，任何其他软件都必须在操作系统的支持下才能运行。
  操作系统的功能 包括管理 计算机系统的硬件、软件及数据资源， 控制程序运行，改善人机交互，为其他应用软件提供支持等， 使计算机系统所有资源最大限度的发挥作用。
  1、调度:线程是独立调度的基本单位 ， 进程是资源拥有的基本单位。
  在不同进程中进行线程切换，将会引起进程切换。
  2、拥有资源: 进程是拥有资源的基本单位，而线程一般不拥有资源 (除了少量资源，比如栈、程序计数器、寄存器)，不过线程可以 访问 其隶属进程的系统资源。
  3、并发性:在引入线程的操作系统中，不仅进程之间可以并发执行，而且 同一个进程内的多个线程之间也可以并发执行， 能提高系统的吞吐量， 系统的并发性也更好。
  4、系统开销:在 创建进程和撤销进程 时，系统都要为之分配或回收资源 ，所以操作系统为进程付出的系统开销远大于创建线程的开销。
  作业是用户需要计算机完成单位某项任务，是要求计算机所做工作的集合。
  在用户向计算机提交作业后，系统将它放入外存中的作业等待队列 中等待执行，而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。
  任意进程，只要被创建，总有相应的部分存在于内存中，
  2、 一个作业可以由多个进程组成，且必须至少由一个进程组成，反过来则不成立
  3、作业的概念主要用于 批处理系统中， 像 UNIX 这样的分时系统中就没有作业的概念。
  而进程的概念则用在几乎所有的多道程序系统中进程是操作系统进程资源分配的单位。
  在 Windows 下，进程又被细化为线程，也就是一个进程下有多个能单独运行的更小的单位。
  4、 作业调度:外存 --> 内存(频率低)开始工作
  进程调度:内存 -->CPU (并发性，频率高) 工作时
  宏内核，就是操作系统的所有功能都绑定到一起，作为一个进程被发起 ，可以理解为一个单一的进程，开机后它自己启动自己，然后从事管理工作。
  微内核相对于宏内核而言的，微内核，就是操作系统有很多程序 / 进程组成。
  系统在运行时， 不同的进程负责不同的事务。
  进程之间可以通过通讯，来进行协调。
  没有一个可以控制一切的进程存在。
  DMA( Direct memory access ): 是一种 无需 CPU 的参与 就可以让 外设与系统内存 之间进行 双向数据传输的硬件机制， 使用 DMA 可以 使系统 CPU 从实际的 I/O 数据传输过程中摆脱出来 ，从而大大提高系统的吞吐量。
  (直接存储器存取)
  所以中断和 DMA 的区别在于是否有 CPU 参与
  软中断:软中断发生的时间是由 程序控制的 ，中断源发中断请求或软中断信号后， CPU 或接受进程在适当的实际自动进行中断处理，或完成软中断信号对应的功能;
  硬中断:硬中断时硬件实现的中断， 是程序运行时设备对它的中断， 硬件中断 处理程序要 确保它能快速 地完成它的任务，这样程序执行时才不会等待较长时间。
  为了便于在内存中找到 进程的每个页面对应的物理块 ，系统为每个进程建立一张 页面映射表 。
  页表由页表项组成，页表项有页号和块号组成，根据页表项就可以找到每个页号对于物理内存中的物理块的块号。
  1、 最佳置换算法( OPT ):在预知一个进程的页面号引用串的情况下， 每次都淘汰以后不再使用的或以后最迟再被使用的页面。
  该算法 不能实现 ，只能作为一个标准来衡量其他置换算法的优劣。
  2、 先进先出算法( FIFO ):每次总是 淘汰最先进入内存的页面 ，也就是将在内存中驻留时间最长的页面 淘汰。
  (可能产生 Belady 异常，缺页次数随着分配的物理块的增加而增加)
  3、 最近最少使用算法( LRU ):选择 最近最少未被使用的页面进行淘汰 ，其思想是用以前的页面引用情况来预测将来会出现的页面的引用情况。
  磁盘调度算法的目的:使磁盘的平均寻道时间最少1、先来先服务算法:按照进程请求访问磁盘的先后顺序进行调度
  2、SCAN 算法:在当前磁头移动方向上，选择与当前磁头所在磁道最近的请求，作为下一个的服务对象。
  3、FSCAN 算法，把请求队列分成两个子队列将新出现的请求放在一个队列中
  信号量分类:
  1、 整型信号量 : 所谓的整型信号量就是一个用于表示资源个数的整型量
  2、 记录型信号量(资源信号量): 就是用一个结构体实现，里面包含了表示资源个数的整形量和一个等待队列
  信号量的应用:实现进程同步，实现进程互斥
  信号量的值除了初值外，仅能有这PV 原语加以改变。
  PV 操作以 原语形式( 不会被线程调度机制打断的操作，称原子操作 ) 实现，保证了对 信号量进行操作过程中不会被打断或阻塞 。
  P 操作相当于 申请资源 ， V 操作相当于 释放资源 。
  P 操作和 V 操作必定成对出现。
  但未必在同一进程中。
  链表:进程管理 -PCB 的连接;外存分配方式 - 链接分配
  队列: 进程通信 - 消息队列的实现;处理机调度 - 任务就绪队列的实现;存储器管理 - CLOCK 置换算法的实现(循环队列)
  栈:存储器管理 -LRU 置换算法
  树:进程管理 - 进程家族关系描述 - 进程树， 进程树是一个形象化的比喻，比如 一个进程启动了一个程序 ，而 启动的这个进程 就是原来那个进程的子进程 ，依次形成一个树形的结构，我们可以在进程管理器选择结束进程树，就可以结束其子进程和派生的子进程
  散列表 : 内存管理 - 连续分配方式 ( Hash 算法); 文件管理( Hash 文件)
  1、用户态 --> 系统态，此时 CPU 环境中有中断程序，需将 CPU 的通用寄存器内容压入堆栈 ，然后再将 用户定义的参数传送带指定的地址保存起来
  2、分析系统调用类型，转入相应的系统 调用处理子程序
  3 、 在系统调用处理子程序执行完后，应 恢复被中断的或 设置新进程的 CPU 现场 ，然后返回被中断进程或新进程，继续往下执行
  基于局部性原理 ，应用程序在运行之前， 仅将那些当前要运行的少数页面或段先装入内存便可运行 ，其余部分暂时留在盘上。
  从应用程序的角度，让应用程序认为它拥有连续的可用内存，即一个完整的地址空间
  从用户角度出发，该系统的内存容量比实际内存容量大很多 ，故成这样的存储器为虚拟存储器。
  存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及从逻辑上扩充存储器，故有以下功能:1、 内存的分配和回收 :实施 内存的分配，回收系统或用户释放的内存空间
  2、 地址变换 :提供地址变换功能，将 逻辑地址转换为物理地址
  4 、存储保护 :保证进入内存的各道作业都在自己的存储空间内运行，互不干扰 。
  界限寄存器:上下界寄存器方法、基址、限长寄存器方法
  存储保护键:给每个存储块分配一个单独的存储键，它相当于一把锁
  TLB 中存放了一些页表文件， 文件中记录了虚拟地址和物理地址的映射关系 。
  当应用程序访问一个虚拟地址的时候， 会从 TLB 中查询出对应的物理地址， 然后访问物理地址。
  Cache 通常由两部分组成 , 块表 和 快速存储器 .
  其工作原理是 : 处理机按主存地址访问存储器 ， 主存 -Cache 地址映射机构 借助 查块表判定该地址的存储单元是否在 Cache 中 , 如果在 ， 则 Cache 命中 ， 按 Cache 地址访问 Cache ; 否则 ,Cache 不命中 ， 则需要访问主存 ， 并从主存中调入相应数据块到 Cache 中 ， 若 Cache 中已写满 ， 则要按某种算法将 Cache 中的某一块替换出去 ， 并 修改有关的地址映射关系
  1、 直接映射 就是将主存地址映射到 Cache 中的一个指定地址 .
  3、 组相联映射 指的是将存储空间的页面分成若干组 , 各组之间的直接映射 , 而组内各块之间则是全相联映射 .
  补充:应用程序从用户编写的源文件到内存中执行的过程大致分为三个阶段:编译、链接、装入1、绝对装入:在 编译时就知道程序 将要驻留在内存的物理地址 ， 编译程序产生含有物理地址的目标代码 ，不适合多道程序的执行
  2、可重定向装入:根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称为静态重定向。
  当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定向时程序中指令或操作数的逻辑地址加上这个起始地址就可以得到物理地址
  3、动态运行装入:允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到响应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。
  动态重定向的实现要依靠硬件地址变换机构。
  1、静态链接:在程序运行之前，先把各个目标模块及所需库 链接为一个完整的可执行程序 ，以后不再拆开
  2、装入时动态链接:将应用程序编译后所得到的一组目标模块在装入内存时采用 边装入边链接 的链接方式
  3、运行时动态链接: 知道程序运行过程中需要一些模块时 ，才对这些模块进行链接
  覆盖技术:把一个大的程序划分为一系列覆盖 ，把程序执行时 并不要求同时装入内存的覆盖为一组，成为覆盖段， 为了解决内存容量大小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制
  交换技术:把暂时不用的某个程序及数据部分从内存移到外存中去， 以便腾出必要的内存空间
  1、与覆盖技术相比， 交换技术不要求程序员给出程序段之间的覆盖结构
  2、交换技术主要在 进程和作业 之间进行，覆盖技术主要在同一个进程 或 作业 中进行
  3、覆盖技术只能覆盖于覆盖程序段无关的程序段 ，交换进程由 换出和换入两个过程组成
  1、单一连续分配(静态分配)、2、固定分区分配(分区大小可以不等但必须事先确定，运行时不能改变)
  3、动态分区分配
  ① 首次适应算法 First Fit ② 循环首次适应算法 Next Fit ③ 最佳适应算法 Best Fit ④ 最差适应算法 Worst Fit
  非连续分配方式允许一个程序分散的装入不相邻的内存分区，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。
  内部碎片:分配给作业的存储空间中未被利用的部分
  外部碎片: 系统中无法利用的小存储块 ，比如通过动态内存分配技术从空闲内存区上分配内存后剩下的那部分内存块。
  什么是拼接技术
  在分区管理方式下， 系统运行 一段时间后， 内存中会出现相当一部分的碎片 ， 拼接技术是解决碎片问题的方法。
  通过移动把多个分散的小分区拼接成一个大分区的方法叫做拼接技术。
  ① 先来先服务调度FCFS ② 短作业优先调度 SJF ③ 优先级调度 Priority ④ 时间片轮转调度 RR
  ⑤ 高响应比优先调度⑥ 多级队列调度⑦ 多级反馈队列调度、
  死锁是指两个或两个以上的进程在执行过程中，争夺资源 而造成的一种 互相等待 的现象， 若无外力作用，他们都将无法推进下去。
  死锁原因: 1 、 系统资源不足、 2 、进程推进顺序不当
  ② 请求和保持条件:指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程
  占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
  ③ 不剥夺条件: 指进程已获得的资源，在未使用完之前，不能被剥夺 ，我的就是我的，我自己说得算
  ④ 环路等待条件:指在发生死锁时，进程之间 你等我，我等你
  处理死锁的基本方法:找到进程号， kill 进程
  等待时间给进程推进和响应带来明显影响的时差称为进程饥饿。
  饥饿并不代表系统一定死锁，但至少有一个程序的执行被无限期的推迟
  1、 进入饥饿的进程可能只有一个 ，但是 死锁必须大于等于两个
  2、处于 饥饿状态的进程可能是一个就绪进程 ，但是 死锁状态的进程必定是阻塞进程
  主要是思想是避免系统进入不安全状态 ，在每次进行资源分配时，它 首先检查系统是否有足够的资源满足要求 ，如果有，则先 试行分配 ，并对 分配后的新状态进行安全性检查 。
  如果新状态安全，则 正是分配上述资源，否则拒绝分配上述资源 。
  这样就保证系统时钟处于安全状态，从而避免死锁现象的发生。
  所谓“ 实时操作系统 ” ，实际上是指操作系统 时，其各种资源可以根据需要随时进行动态分配 。