操作系统概论

微内核与聚内核

• 微内核：内核只负责相当核心的工作，包括进程管理、内存管理等，而诸如文件系统等模块以守护进程的方式运行在用户空间，运行起来特别稳定，缺点是效率低；比如Windows操作系统就是微内核。
• 聚内核：聚内核（单内核、宏内核）不仅包括进程管理、内存管理等核心的模块外，还包括文件系统、网络等模块内容，特点是稳定性差，牵一发而动全身，优点是高效，所有模块都运行在内核，相互之间沟通直接函数调用即可。

系统运行模式

• 内核模式：操作系统内核，具备执行特权指令的权限；
• 用户模式：非操作系统内核程序运行；

用户模式的进程通过系统调用（system call）来进入内核模式；

操作系统引导（Boot）

BIOS 操作系统引导

比如BIOS用来引导操作系统（x86），首先将MBR（Master Boot Record）加载到0x7C00的内存位置，然后程序跳转到0x7C00的位置执行指令，之后开始进行从磁盘加载操作系统的工作，最后开始执行操作系统；

MBR：磁盘的第一块扇区，存储着分区表等信息，MBR大小非常小（512byte）；

进程

一个程序运行起来就称为一个进程，一个进程在操作系统里面使用一个PCB（Process Controller Block）来表示：

Process

更为具体的，一个进程的结构布局如下：

进程布局

总结：

• PC：程序计数器等寄存器，寄存器是非常重要的存储设备，是cpu存取指令的介质；
• Text：代码段，用于存储程序代码；
• Data：数据段
• heap：堆
• stack：栈

考虑到局部性原理，即：当命中某个位置的数据的同时，命中数据位置的两边局部的数据被访问的概率会非常大，使用数组的效率非常高，而链表这种数据结构其实非常不符合局部性原理，无法预测下一个节点的内存位置，所以访问效率较低，会频繁的刷新缓存。

进程状态

进程状态

• new： 新建
• ready：准备好可以开始执行
• running：获取到cpu资源，进程正在运行
• waiting：进程正在等待某种资源，比如I/O资源，或者等待某种事件；
• terminated：进程结束运行；

状态变更：

• ready -> running: 进程被调度执行，获取到cpu；
• running -> waiting: 进程请求I/O资源，等待事件，进行系统调用等；
• running -> ready: 进程被调度，cpu时间片用完了；
• waiting -> ready: 进程所等待的资源得到满足，可以继续运行；

操作系统如何实现进程调度

操作系统通过时钟中断来进行进程调度，时钟中断发生的时候，正在运行的进程将陷入内核，操作系统内核获取到CPU，进程控制权被进程获取，内核就可以开始运行调度算法进行进程调度。

进程调度

比如，进程1正的cpu时间片用完了，时钟中断发生，操作系统内核获取到cpu，此时内核首先将保存进程1的上下文并进行状态变更等操作，接着开始运行调度算法挑选下一个可以运行的进程，比如进程2被挑选出来，则将进程2的pcb加载进来，然后开始将控制权转移到进程2，接着进程2开始运行，周而复始；

软硬件协同设计

用软件无法很好的完成的工作，硬件可能会完成得非常好，比如进程切换的时候上下文切换的工作，软件完成的话虽然简单，但是没有优化空间，在上下文切换特别频繁的时候就会成为瓶颈，而如果将此功能实现为一个硬件指令，则可以很好的解决效率问题。

创建新进程

fork：这是一个系统调用，可以完整的copy出一个当前进程，然后父进程和子进程非开调度运行，子进程将执行fork之后的代码。

线程

线程

在linux里面，线程通过clone 系统调用来实现，clone通过设定一些标志来设定是否需要继承父进程的某些内容；

线程的实现

线程的实现模式分为用户级线程和内核级线程：

用户级线程

• 用户级线程：效率高，在用户空间进行调度，可定制型强，但是当一个线程block之后，所以共享一个内核线程的线程组都将被阻塞，而且多个线程只能在一个CPU上执行，无法充分利用系统资源；
• 内核级线程：所谓的轻量级进程；

user-thread-缺点-1
user-thread-缺点-2

多进程和多线程架构

• 性能问题：差不多
• 资源占用：多进程资源占用较多；
• 安全性：多进程资源隔离，具备一定的安全性，多线程共享进程资源，安全性较低；
• 稳定性：多进程架构多个进程之间相互独立，不会相互影响，而多线程之间相互影响，一个线程奔溃整个进程就会崩溃。

例子：Chrome使用多进程架构，而IE使用多线程架构。

CPU调度

首先需要了解的内容是进程的分类，进程生命周期内大量占用CPU资源的进程成为CPU绑定的进程，而在生命周末内大量进行I/O操作的进程成为I/O绑定进程，操作系统调度算法的实现依赖进程的类型；

CPU调度的算法分为抢占式和非抢占式，进程主动让出CPU资源则为非抢占式，否则就是抢占式，抢占式意味着进程的调入调出都交给操作系统来进行。

衡量CPU调度算法的好坏需要根据一些指标来进行，下面是一些常用的衡量指标及其表示的含义：

• CPU利用率：CPU利用率越高，说明进程调度算法越好；
• 吞吐量： 单位时间内调度算法可以完成的调度，越大说明调度算法的效率越好；
• 周转时间：进程从开始执行到结束运行花费的时间，周转时间越小代表调度算法越好；
• 等待时间：进程在ready状态下等待CPU资源所花费的时间，越小表示调度算法越好；

一般使用平均周转时间来衡量CPU调度算法的效率。

调度算法类别

调度算法类别较多，下面是几种典型的CPU调度算法：

• 先来先服务：有一个FIFO队列，等待CPU资源的进程被依次放入这个队列里面，而CPU调度的时候也会依次从这个队列取出进程来执行；

先来先服务

• 最短任务优先：当CPU进行调度的时候，将所有等待CPU资源分配的进程中所需要CPU时间最少的进程拿出来执行，这样可以保证平均周转时间是最少的；

最短任务优先

• 时间片轮转：CPU的资源被划分成很小的时间片，每个进程被调度到CPU之后执行指定的时间片后需要陷入操作系统再进行调度；

先来先服务调度算法是实现起来最简单的，也是最容易理解的调度算法，但是它的缺点非常明显，就是周转时间不是最优的，可能有一些进程会因为需要执行大量的时间而让其他一些需要很少CPU时间的进程等待非常长的时间；
最短任务优先算法是一种相当优化的算法，但是实现起来非常困难，甚至无法实现，因为我们无法准确的知道一个进程需要运行的时间到底是多少。
在实现上，使用一种称为优先级队列的方法来实现，需要说明的是，优先级队列是一种操作系统实现CPU调度算法的策略，并不是一种具体的算法，优先级队列的思想比较简单，它维护一个队列，队列里面的进程都具备不同的优先级，也就是说，每个进程都有不同的优先级，优先级高的进程能被更快的调度，这个算法的致命缺点就是低优先级的进程会出现“饥饿”，因为如果队列里面不停的进来一些高优先级的进程，那么在队列里面的那些低优先级的进程将久久不能被调度。
基于优先级队列的缺点，出现了多级优先级队列，不同的队列使用时间片算法来保证不会被饿死：

多级队列

多级队列每个队列内部还可以使用不同的调度算法来进行，比如高优先级的队列内部使用时间片轮转算法，低优先级队列内部使用先来先服务的调度算法；
多级队列是一个很好的思路，但目前操作系统实现进程调度使用的是一种称为多级反馈队列的策略来实现，这种反馈就是基于进程的历史行为来确定未来：

多级反馈队列

进程一开始被放到最高优先级的队列里面等待执行，如果发现进程可以将分配给他的时间片用完，那么认为它是CPU绑定的，那么他的优先级减小，将它放到下一个低优先级的队列中去，直到最低优先级队列；当然，进程的优先级还可能不断升高，当进程运行一段时间之后，变成I/O绑定的了，那么就会不断提高优先级来快速实现快速响应；

多核调度算法

多个CPU核心的调度算法要复杂得多，它需要解决的问题包括：

• 负载均衡：不至于有些CPU非常繁忙，而有些CPU则很空闲；
• cache 刷新：cache是非常重要的，CPU是一种比内存快速的组件，所以CPU和内存中间会存在多级缓存，如果缓存不断刷新的话，也是一个不小的开销；

cache刷新