操作系统
大约 4 分钟
操作系统
前置知识
基本概念
计算能源：第三次科技革命的能源是计算能源，是数字能量，本质上是计算
数字能量产生过程：
- 电能给芯片供电
- 芯片中的一种电子元件晶振（也就是石英晶体）通电后产生振荡
- 振荡会产生频率稳定的、高频的脉冲信号（每秒百万次）
- 通过谐振效应放大信号，形成方波
- 再通过电子元件调整脉冲的频率，把脉冲信号转换为我们需要的频率，就形成的驱动芯片工作的时钟信号
- 时钟信号驱动着芯片工作，就像脉搏，买一次脉冲的到来，都让芯片的状态发生一次变化
- 最终存储器中的指令被一行行执行
- 指令被执行就是数据被计算，就是计算能量
摩尔定律：当价格不变时，集成电路中可容纳的晶体管数目约每隔 18～24 个月就会增加一倍，性能也将提升一倍
这一定律揭示了信息技术发展的速度，但到今天，摩尔定律失效了。因为随着芯片越来越小，在尺寸和散热等方面已经挑战了人类的极限，芯片中无法再放入更多的电子元件了。
但是计算能力又开始以另一种方式发展，比如一个普普通通的 NVIDA 显卡中就拥有了几百个核心，这样就可以进行大量的并发计算；另外，一个分布式的大数据集群，里面就可能有上千个核心。
展望未来，计算能力还有更多的增长点，不仅有可以无限提高计算能力的量子计算机，还有利用光学元件替代晶体元件的光电集成电路。
可计算理论：图灵发现如果一个问题是可计算的，那么它的解决方案就必须可以被具化成一条条的指令，也就是可以使用图灵机处理。因此，不能使用图灵机处理的问题，都是不可计算的问题
- 公理化体系：这个世界可以建立一套完善的公理体系，由少数几个公理出发，推导出所有的定理和推论。这样就可以逐渐通过这种方法将世界上的万事万物都统一到一个体系中
- 不完备性定理：即便在完善的公理体系中仍然可以找到不能被证明也不能被证伪的命题。
- 计算机能力也是有边界的。哥德尔的不完备性定理，让大家看到了世界上还有大量不可计算的问题
- 素数是不是有无穷多个？不可计算
- 停机问题：不可计算 --- 无法实现用一个通用程序去判断另一个程序是否会停止
- 问题的分类：
- 可计算：根据复杂度分为--简单问题、复杂问题
- 不可计算
- P问题、NP问题
- 按照摩尔定律所说，人类的计算能力每 18～24 个月翻一倍，我们的计算能力在呈指数形式上升。因此，在所有可以计算的问题中，像 O(N1000)的问题，虽然现在的计算能力不够，但是相信在遥远的未来，我们会拥有能力解决。这种我们有能力解决的问题，统称为多项式时间（ Polynomial time）问题。我们今天能解决的问题，都是多项式时间的问题，记为 P 类型的问题
- 另外，还有一类问题复杂度本身也是指数形式的问题，比如 O(2N)的问题。这类型的问题随着规模 N 上升，时间开销的增长速度和人类计算能力增长速度持平甚至更快。因此虽然这类问题可以计算，但是当 N 较大时，因为计算能力不足，最终结果依然无法被解决。由此可见，不是所有可以计算的问题都可以被解决，问题如果不能在多项式时间内找到答案，我们记为 NP 问题
- 有一部分 NP 问题可以被转化为 P 问题，比如斐波那契数列求第 N 项，可以用缓存、动态规划等方式转化为 O(N) 的问题。但还有更多的 NP 问题，比如一个集合，找出和为零的子集，就没能找到一个合适的转换方法