操作系统相关 - 张天宇的博客

学啊，学无止境，太深了。

概述

基本特征

并发

并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。

并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。

操作系统通过引入进程和线程，使得程序能够并发运行。
共享

共享是指系统中的资源可以被多个并发进程共同使用。

有两种共享方式：互斥共享和同时共享。

互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。
虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。
异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

基本功能

进程管理

进程控制、进程同步、进程通信、死锁处理、处理机调度等。
内存管理

内存分配、地址映射、内存保护与共享、虚拟内存等。
文件管理

文件存储空间的管理、目录管理、文件读写管理和保护等。
设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。

主要包括缓冲管理、设备分配、设备处理、虛拟设备等。

大内核和微内核

大内核

大内核是将操作系统功能作为一个紧密结合的整体放到内核。

由于各模块共享信息，因此有很高的性能。
微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。

在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

中断分类

外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
异常

由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
陷入

在用户程序中使用系统调用。

进程管理

进程和线程

进程

进程是资源分配的基本单位。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。
线程

线程是独立调度的基本单位。

一个进程中可以有多个线程，它们共享进程资源。
区别
- 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。
- 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
- 由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
- 线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

为什么有了进程还要线程？

进程有很多优点，它提供了多道编程，让我们感觉我们每个人都拥有自己的CPU和其他资源，可以提高计算机的利用率。

进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。
进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。

线程的同步与阻塞关系

没有任何关系。

同步和异步关注的是消息通信机制。同步调用在没有得到返回值的时候不会返回；异步会立刻返回，由被调者通知它。

阻塞和非阻塞关注的是在等待返回结果时线程的状态。阻塞会挂起线程，也就是卡在这里不往下面执行了；但是，非阻塞调用不会卡住，虽然没有得到返回值，但是依然可以继续往下执行。

线程和进程切换的开销

进程切换开销：

切换虚拟地址空间
切换CPU上下文
切换内核栈

线程切换开销：

切换CPU上下文
切换内核栈

线程之间的共享资源和独占资源

共享资源

进程申请的堆内存
进程打开的文件描述符
进程的全局数据，可以用于线程之间的通信
进程 ID 和进程组 ID
进程目录
信号处理器

独占资源

线程 ID
寄存器组的值
线程堆栈
错误返回码
信号屏壁码
线程的优先级

僵尸进程和孤儿进程

孤儿进程

无危害，一个父进程退出，而它的一个或者多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被 init 进程 (进程号为 1) 所收养，并由 init 进程对它们完成状态收集工作（也就是清理进程号）。
僵尸进程

有危害，一个进程使用 fork 创建子进程，如果子进程退出，而父进程并没有调用 wait 或 waitpid 获取子进程的状态信息，那么子进程的进程描述符（如进程号、运行时间等）仍然保存在系统中。这种进程称之为僵尸进程（进程号就会一直被占用，导致无法产生新的进程）。
僵尸进程解决办法
- 信号机制：子进程退出时候，向父进程发送信号，父进程立马 wait 它
- 找到产生僵尸进程的父进程，kill 掉，init 进程会处理僵尸进程
- 重启

进程状态切换

就绪状态（ready）：等待被调度
运行状态（running）
阻塞状态（waiting）：等待资源
只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程调度算法

先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
最短剩余时间优先 shortest remaining time next（SRTN）

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。
时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
最高相应比优先

R=(w+s)/s （R为响应比，w为等待处理的时间，s为预计的服务时间）

当前进程完成或被阻塞时，选择R值最大的就绪进程，它说明了进程的年龄。当偏向短作业时，长进程由于得不到服务，等待时间不断增加，从而增加比值，最终在竞争中赢了短进程。
多级反馈队列

多级队列是为需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,…。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

进程同步

临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
同步和互斥
- 同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
- 互斥：多个进程在同一时刻只有一个进程能进入临界区。
信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。
- down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
- up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。
down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
管程

管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

进程通信

进程间资源是独立的，关注的是通讯问题。

线程间资源是共享的，关注的是安全问题。

进程同步：控制多个进程按一定顺序执行；
进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

管道

管道的通知机制有些类似于缓存，一个进程将数据存储于缓存当中，然后等待另外一个进程去拿。类似的，一个进程将数据放于管道中，然后等另一个进程从管道中获取，并且管道是单向传输的，也就是说，数据只能从A到B，或者从B到A，并不能做到A和B相互发送和接收。

从管道的机制以及它单向传输的特点，不难分析出来，管道十分简单，但是不适合频繁的进程通信，进程间如果通过管道进行通信的话，效率会很低。
FIFO

FIFO文件通常也称为命名管道（named pipe）。命名管道是一种特殊类型的文件，它在文件系统中以文件名的形式存在。
消息队列

我们可以通过将进程A所需要发送的信息存入对应的消息队列当中，进程B需要时再去对应的消息队列当中获取。这样便能够把进程的数据放在消息队列中，而不需要等待其他进程来取便可以继续进行后续的操作。
共享内存

系统在加载一个进程的时候，分配给进程的内存是虚拟内存空间，因此，可以让互相通信的两个进程各拿出一块虚拟地址空间，映射到相同的物理内存当中，从而完成内存共享机制。

当两个进程共享内存之后，不可避免地便会出现多进程竞争资源的问题，类似于线程安全问题。
信号量

信号量的本质就是一个计数器，用于实现进程间的互斥于同步，信号量只能进行操作等待V(sv)和发送信号P(sv)两种操作。
Socket

管道、消息队列、共享内存、信号量这四种方式，都是多个进程在同一台主机之间的通信，当涉及到不同主机的进程间通信时，则需要使用Socket，Socket会指定所需要通信的进程所对应的IP地址及其所监听/发送的端口号。

死锁

锁是多用户环境中对数据访问的控制。

指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。

系统资源不足
资源分配不当
进程推进顺序不当

客情占资源

可抢占资源：可以从拥有它的进程中抢占而不会产生任何副作用。
不可抢占资源：在不引起相关的计算失败的情况下，无法把它从占有它进程处抢占过来。

必要条件

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
占有和等待：已经得到了某个资源的进程可以再请求新的资源。
不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

处理方法

鸵鸟策略
死锁检测与死锁恢复
死锁预防
死锁避免

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁恢复

利用抢占恢复
利用回滚恢复
通过杀死进程恢复

死锁预防

在程序运行之前预防发生死锁。

破坏互斥条件

例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏占有和等待条件

一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
破坏不可抢占条件
破坏环路等待

给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

安全状态

如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
多个资源银行家算法

内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

虚拟内存、共享内存和常驻内存

虚拟内存 VIRT：进程“需要的”虚拟内存大小，包括进程使用的库、代码、数据，以及malloc、new分配的堆空间和分配的栈空间等。
常驻内存 RES：进程当前使用的内存大小，包括使用中的malloc、new分配的堆空间和分配的栈空间。
共享内存 SHR：除了自身进程的共享内存，也包括其他进程的共享内存。计算某个进程所占的物理内存大小公式：RES – SHR。

虚拟地址、逻辑地址和物理地址

虚拟地址到物理地址的转换

虚拟地址是由程序产生的由段选择符和段内偏移地址组成的地址。这两部分组成的地址并没有直接访问物理内存，而是要通过分段地址的变换处理后才会对应到相应的物理内存地址。
逻辑地址指由程序产生的段内偏移地址。有时把逻辑地址当成虚拟地址，两者并没有明确的界限。
线性地址是逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。
物理地址是指现在 CPU 外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果。

页面置换算法

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

OPT
LRU
FIFO
SCR, 第二次机会算法

第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

分页储存管理方式

在该方式中，将用户程序地址空间分为若干固定大小的区域，称为“页”或“页面”。典型的页面大小为1KB。相应的，也将内存空间分为若干个物理块或页框（frame），页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分配。

分段储存管理方式

这是为了满足用户要求而形成的一种储存管理方式。它把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。在储存器分配时，以段为单位，这些段在内存中可以不相邻接，所以也同样实现了离散分配。

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

这是分页和分段两种储存管理方式相结合的产物。程序的地址空间划分为多个拥有独立地址空间的段，每个段上的地址空间划分为大小相同的页。这样既拥有分段系统的共享保护，又拥有分页系统的虚拟内存功能。它兼具两者的优点，是目前应用较为广泛的一种储存管理方式。

对用户而言，分段是对内存的有效使用；而对于计算机而言，分页可以提高内存的使用效率。在段页式存储中，每个分段又被分成若干个固定大小的页。页面大小等于页框。地址结构：段号 + 页号 + 页内位移。

优点:

(1) 它提供了大量的虚拟存储空间。

(2) 能有效地利用主存，为组织多道程序运行提供了方便。

缺点：

(1) 增加了硬件成本、系统的复杂性和管理上的开消。

(2) 存在着系统发生抖动的危险。

(3) 存在着内碎片。

(4) 还有各种表格要占用主存空间。

分页和分段

对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
地址空间的维度：分页是一维地址空间，分段是二维的。
大小是否可以改变：页的大小不可变，段的大小可以动态改变。
出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

设备管理

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

先来先服务

FIFO，按照磁盘请求的顺序进行调度。

优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
最短寻道时间优先

SSTF，优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。
电梯算法

SCAN，电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。
循环扫描

场景

遍历二维数组，按行遍历和按列遍历效率是否不同

二维数组的内存地址是连续的，当前行的尾与下一行的头相邻

现代计算机，在CPU与内存之间还有一种存储机制，那就是CPU缓存（cache）。CPU缓存的容量比内存小的多但是交换速度却比内存要快得多。缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾，因为CPU运算速度要比内存读写速度快很多，这样会使CPU花费很长时间等待数据到来或把数据写入内存。

访问数组元素时，CPU不会每次只从内存中读取一个元素，而是读取一个区域的元素。假设二维数组的大小为（10 x 10），访问第一个元素时，CPU也会读取它的相邻元素，因为这个数组比较小，CPU一次就可以把所有元素缓存，因此无论是按行访问数组还是按列访问数组，CPU访问主存的数量都相同。随着数组元素越来越多，CPU缓存一次只能读取数组不到一行的数据，因此按列访问元素时每访问一个元素都要访问内存，因此速度就会慢很多。

32 位系统最大寻址空间

寻址空间一般指的是CPU对于内存寻址的能力。通俗地说，就是能最多用到多少内存的一个问题。数据在存储器(RAM)中存放是有规律的，CPU在运算的时候需要把数据提取出来就需要知道数据在那里，这时候就需要挨家挨户的找，这就叫做寻址，但如果地址太多超出了CPU的能力范围，CPU就无法找到数据了。 CPU最大能查找多大范围的地址叫做寻址能力，CPU的寻址能力以字节为单位，如32位寻址的CPU可以寻址2的32次方大小的地址也就是4G，这也是为什么32位的CPU最大能搭配4G内存的原因，再多的话CPU就找不到了。

内存泄漏

内存泄露是指：内存泄漏也称作"存储渗漏"，用动态存储分配函数动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。(其实说白了就是该内存空间使用完毕之后未回收)即所谓内存泄漏。

单例造成的内存泄露

由于单例的静态特性使得其生命周期和应用的生命周期一样长，如果一个对象已经不再需要使用了，而单例对象还持有该对象的引用，就会使得该对象不能被正常回收，从而导致了内存泄漏。
非静态内部类创建静态实例造成的内存泄漏
资源未关闭造成的内存泄漏
静态集合类引起内存泄漏，有存无放
当集合里面的对象属性被修改后，再调用 remove() 方法时不起作用
各种连接如数据库等没有关闭

用户态和内核态切换代价大

在用户态有一个用户态调用栈，当需要进行系统函数调用的时候，就会从用户态进入内核态，也就是需要切换到内核态栈，内核代码对用户不信任，需要进行额外的检查。系统调用的返回过程有很多额外工作，如：保存现场、恢复现场，切换栈等。所以导致了切换的开销大。

中断技术实现了切换。

ID 发号器

对 ID 的要求

全局唯一
按照时间粗略有序
尽可能短

实现策略

参考 Twitter 的雪花算法：64 位的比特，第 0 位空着，接下来的 41 位为 Unix 时间戳，然后接下来的 10 位为机器的id，最后 12 位为计数用的
使用 UUID 算法
多台 MySQL 主键自增实现 ID 唯一

概述