调度算法 进程调度 总论 当CPU空闲，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU 什么时候会发生 CPU 调度 当进程从运行状态转到等待状态 当进程从运行状态转到就绪状态 当进程从等待状态转到就绪状态 当进程从运行状态转到终止状态 其中发生在 1 和 4 两种情况下的调度称为「非抢占式调度」， 2 和 3 两种情况下发生的调度称为「抢占式调度」 非抢占式：当进程正在运行时，会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程 抢占式：进程正在运行的时，可以被打断，使其把 CPU 让给其他进程 先来先服务调度 先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行 对长作业有利，适用 CPU 繁忙型作业的系统，而不适用 I/O 繁忙型作业的系统 最短作业优先调度 会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量 显然对长作业不利，很容易造成一种极端现象 高响应比优先调度 每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行 时间片轮转调度 每个进程被分配一个时间段，称为时间片，即允许该进程在该时间段中运行 最高优先级调度 对多用户计算机系统就有不同的看法，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级调度 优先级可分为： 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化 动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，就随着时间的推移增加等待进程的优先级 多级反馈队列调度 「时间片轮转算法」和「最高优先级算法」的综合和发展 「多级」有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。 「反馈」如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列； 内存页面置换 缺页异常（缺页中断）
当 CPU 访问的页面不在物理内存，便产生一个缺页中断，请求操作系统将所缺页调入到物理内存。与一般中断区别在于： 缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号 缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行 页面置换算法：当出现缺页异常，需调入新页面但内存已满，选择被置换的物理页面，也就选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页 最佳页面置换
置换在「未来」最长时间不访问的页面，但无法实现 先进先出置换
选择在内存驻留时间很长的页面进行中置换，就是「先进先出置换」算法的思想 最近最久未使用置换
发生缺页时，选择最长时间没有被访问的页面进行置换，假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用 时钟页面置换
把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面
缺页中断时，首先检查表针指向的页面：
如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置； 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止 网络 I/O多路复用 服务用户数量...
总论 现代操作系统，内核一般会提供 4 个基本能力： 管理进程、线程，决定哪个进程、线程使用 CPU，也是进程调度的能力； 管理内存，决定内存的分配和回收，也是内存管理的能力； 管理硬件设备，为进程与硬件设备之间提供通信能力，也是硬件通信能力； 提供系统调用，如果应用程序要运行更高权限运行的服务，就需要有系统调用，是用户程序与操作系统之间的接口 内核具有很高的权限，可控制 cpu、内存、硬盘等硬件，而应用程序具有的权限很小。 因此大多数操作系统，把内存分成了两个区域 内核空间：这个内存空间只有内核程序可以访问 用户空间：这个内存空间专门给应用程序使用 用户空间的代码只能访问一个局部的内存空间，而内核空间的代码可以访问所有内存空间 当程序使用用户空间时，我们常说该程序在用户态执行 当程序使内核空间时，程序则在内核态执行 应用程序如果需要进入内核空间，就需要通过系统调用 内核程序执行在内核态，用户程序执行在用户态 应用程序使用系统调用时，会产生一个中断。发生中断后， CPU 会中断当前在执行的用户程序，转而跳转到中断处理程序（开始执行内核程序） 内核处理完后，主动触发中断，把 CPU 执行权限交回给用户程序，回到用户态继续工作 现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程 A 和 进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址，对于数据的增删查改互不影响 内存管理 虚拟内存 单片机的 CPU 是直接操作内存的「物理地址」 想在内存中同时运行两个程序是不可能的。如果第一个程序在 2000 的位置写入一个新的值，将会擦掉第二个程序存放在相同位置上的所有内容，所以同时运行两个程序是根本行不通的 解决方法？ 把进程所使用的地址「隔离」开来，即让操作系统为每个进程分配独立的一套「虚拟地址」，人人都有，大家自己玩自己的地址就行，互不干涉 有个前提每个进程都不能访问物理地址，至于虚拟地址最终怎么落到物理内存里，对进程来说是透明的 理解：之所以不能同时运行，就是因为两个程序引用相同物理地址，也就是不能让其使用相同的物理地址，加一层映射过去 操作系统会提供一种机制，将不同进程的虚拟地址和不同内存的物理地址映射起来 程序要访问虚拟地址的时候，由操作系统转换成不同的物理地址，这样不同的进程运行的时候，写入的是不同的物理地址，这样就不会冲突了 引出两种地址概念： 我们程序所使用的内存地址叫做虚拟内存地址 实际存在硬件里面的空间地址叫物理内存地址 操作系统引入了虚拟内存，进程持有的虚拟地址会通过 CPU 芯片中的内存管理单元（MMU）的映射关系，来转换变成物理地址，然后再通过物理地址访问内存 虚拟内存作用： 第一，虚拟内存使得进程对运行内存超过物理内存大小，因为程序运行符合局部性原理，CPU 访问内存会有很明显的重复访问的倾向性，对于那些没有被经常使用到的内存，我们可以把它换出到物理内存之外，比如硬盘上的 swap 区域 理解：加载一个很大的存储，原本只能一次性，现在可分按需批 第二，由于每个进程都有自己的页表，所以每个进程的虚拟内存空间就是相互独立的。进程也没有办法访问其他进程的页表，所以这些页表是私有的，这就解决了多进程之间地址冲突的问题 第三，页表里的页表项中除了物理地址之外，还有一些标记属性的比特，比如控制一个页的读写权限，标记该页是否存在等。在内存访问方面，操作系统提供了更好的安全性 内存分段 程序是由若干个逻辑分段组成的，如可由代码分段、数据分段、栈段、堆段组成。不同的段是有不同的属性的，所以就用分段（Segmentation）的形式把这些段分离出来 分段机制下，虚拟地址的物理地址的映射 分段机制下的虚拟地址由两部分：段选择因子和段内偏移量 段选择子就保存在段寄存器里面。段选择子里面最重要的是段号，用作段表的索引。段表里面保存的是这个段的基地址、段的界限和特权等级等。 虚拟地址中的段内偏移量应该位于 0 和段界限之间，如果段内偏移量是合法的，就将段基地址加上段内偏移量得到物理内存地址 虚拟地址是通过段表与物理地址进行映射的，分段机制会把程序的虚拟地址分成 4 个段，每个段在段表中有一个项，在这一项找到段的基地址，再加上偏移量，于是就能找到物理内存中的地址 问题： 第一个是内存碎片 内存分段管理可以做到段根据实际需求分配内存，有多少需求就分配多大的段，所以不会出现内部内存碎片，但是由于每个段的长度不固定，所以多个段未必能恰好使用所有的内存空间，会产生了多个不连续的小物理内存，导致新的程序无法被装载，所以会出现外部内存碎片 解决「外部内存碎片」的是内存交换 内存交换空间，在Linux中，是我们常看到的 Swap 空间，这块空间是从硬盘划分出来的，用于内存与硬盘的空间交换 第二个是内存交换的效率低 如果内存交换的时候，交换的是一个占内存空间很大的程序，这样整个机器都会显得卡顿 内存分页 分段的好处就是能产生连续的内存空间 但会出现「外部内存碎片和内存交换的空间太大」的问题 解决这些问题，那么就要想出能少出现一些内存碎片的办法 分页是把整个虚拟和物理内存空间切成一段段固定尺寸的大小，这样一个连续并且尺寸固定的内存空间，我们叫页（Page）。在 Linux 下，每一页的大小为 4KB 虚拟地址与物理地址之间通过页表来映射 页表存储在内存里，内存管理单元 （MMU）将虚拟内存地址转换成物理地址工作 当进程访问的虚拟地址在页表中查不到时，系统会产生一个缺页异常，进入系统内核空间分配物理内存、更新进程页表，最后再返回用户空间，恢复进程的运行 解决分段问题 内存分页由于内存空间都是预先划分好的，采用了分页，页与页之间是紧密排列的，所以不会有外部碎片 内存分页机制分配内存的最小单位是一页，即程序不足一页大小，我们最少只能分配一个页，所以页内会出现内存浪费，所以针对内存分页机制会有内部内存碎片 内存空间不够，操作系统会把其他正在运行的进程中的「最近没被使用」的内存页面给释放掉，也就是暂时写在硬盘上，称为换出（Swap Out）。一旦需要的时候，再加载进来，称为换入（Swap In）一次性写入磁盘的也只有少数的一个页或者几个页，不会花太多时间，内存交换的效率就相对比较高 分页的方式使得我们在加载程序的时候，不再需要一次性都把程序加载到物理内存中，只有在程序运行中，需要用到对应虚拟内存页里面的指令和数据时，再加载到物理内存里面去 分页机制，虚拟地址与物理地址的映射 分页机制下，虚拟地址分为两部分，页号和页内偏移。页号作为页表的索引，页表包含物理页每页所在物理内存的基地址，这个基地址与页内偏移的组合就形成了物理内存地址 总结一下，对于一个内存地址转换，就是这样三个步骤： 把虚拟内存地址，切分成页号和偏移量； 根据页号，从页表里面，查询对应的物理页号； 直接拿物理页号，加上前面的偏移量，就得到了物理内存地址 缺陷： 操作系统是可以同时运行非常多的进程的，那这不就意味着页表会非常的庞大 在 32 位的环境，虚拟地址空间共 4GB，假设一个页大小是 4KB（2^12），就需要大约 100 万 （2^20） 个页，每个「页表项」需要 4 个字节(4B)来存储，那整个 4GB 空间的映射就需要 4MB 的内存来存储页表 100 个进程的话，就需要 400MB 的内存来存储页表，这是非常大的内存 多级页表 解决分页的缺陷 把这 100 多万个「页表项」的单级页表再分页，将页表（一级页表）分为 1024 页表（二级页表），每个表（二级页表）中包含 1024 个「页表项」，形成二级分页 算机组成原理里面无处不在的局部性原理 每个进程都有 4GB 的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到 4GB，因为会存在部分对应的页表项都是空的，根本没有分配，对于已分配的页表项，如果存在最近一定时间未访问的页表，在物理内存紧张的情况下，操作系统会将页面换出到硬盘，也就是说不会占用物理内存 一级页表就可以覆盖整个 4GB 虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表 深入理解思想： 从页表的性质来看，保存在内存中的页表承担的职责是将虚拟地址翻译成物理地址 页表一定要覆盖全部虚拟地址空间，不分级的页表就需要有 100 多万个页表项来映射，而二级分页则只需要 1024 个页表项 此时一级页表覆盖到了全部虚拟地址空间，二级页表在需要时创建 TLB 多级页表虽然解决了空间上的问题，但是虚拟地址到物理地址的转换就多了几道转换的工序，这显然就降低了这俩地址转换的速度，带来了时间上的开销 程序是有局部性的，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域 最常访问的几个页表项存储到访问速度更快的硬件，于是计算机科学家们，就在 CPU 芯片中，加入了一个专门存放程序最常访问的页表项的 Cache，这个 Cache 就是 TLB 有TLB 后，那么 CPU 在寻址时，先查 TLB，如果没找到，才会继续查常规的页表 TLB 的命中率其实是很高的，因为程序最常访问的页就那么几个 段页式内存管理 内存分段和内存分页并不是对立的，它们是可以组合起来在同一个系统中使用的，那么组合起来后，通常称为段页式内存管理 段页式内存管理实现方式： 先将程序划分为多个有逻辑意义的段，也就是前面提到的分段机制 再把每个段划分为多个页，也就对分段划分出来的连续空间，再划分固定大小的页 这样，地址结构就由段号、段内页号和页内位移三部分组成 段页式地址变换中要得到物理地址须经过三次内存访问： 第一次访问段表，得到页表起始地址； 第二次访问页表，得到物理页号； 第三次将物理页号与页内位移组合，得到物理地址 Linux内存结构 Linux 系统中的每个段都是从 0 地址开始的整个 4GB 虚拟空间（32 位环境下），也就是所有的段的起始地址都是一样的。这意味着，Linux 系统中的代码，包括操作系统本身的代码和应用程序代码，所面对的地址空间都是线性地址空间（虚拟地址），这种做法相当于屏蔽了处理器中的逻辑地址概念，段只被用于访问控制和内存保护 Linux 内存主要采用的是页式内存管理，但同时也不可避免地涉及了段机制 每个进程都各自有独立的虚拟内存，但是每个虚拟内存中的内核地址，其实关联的都是相同的物理内存。这样，进程切换到内核态后，就可以很方便地访问内核空间内存 分配内存 应用程序通过 申请内存的时候，实际上申请的是虚拟内存，此时并不会分配物理内存...