本文是《现代操作系统》一书的阅读笔记，主要记录俺觉得重要的知识。
第5章：输入/输出
I/O硬件原理
CPU与设备通信的方式有三种：
- 单独的I/O和内存空间：每个控制寄存器被分配一个I/O端口号，所有 I/O端口形成I/O端口空间。
- 内存映射I/O：每个控制寄存器被分配惟一的一个内存地址，井且不会有内存被分配这一地址。
- 混合方案：内存映射I/O的数据缓冲区，而控制寄存器则具有单独的I/O端口。
I/O软件层次
缓冲有以下几种方案
- 无缓冲的输入
- 用户空间中的缓冲
- 内核空间中的缓冲接着复制到用户空间：避免缓冲被换页
- 内核空间中的双缓冲：避免字符在缓冲区复制的时候到达
假脱机(spooling)工作方式，以打印机为例
- 一个进程要打印一个文件时，首先生成要打印的整个文件，并且将其放在假脱机目录下。
- 由守护进程打印该目录下的文件，该进程是允许使用打印机特殊文件的惟一进程。
盘
磁盘臂调度算法有以下几种
- 先来先股务：每次接收一个请求并按照接收顺序完成请求。
- 最短寻道优先：下一次总是处理与磁头距离最近的请求。
- 电梯算法：保持按一个方向移动，到在那个方向上没有请求为止，然后改变方向。
第6章：死锁
死锁概述
发生死锁的四个必要条件：
- 互斥条件。每个资源要么已经分配给了一个进程，要么就是可用的。
- 占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。
- 不可抢占条件。已经分配给一个进程的资探不能强制性地被抢占，它只能被占有它的进程显式地释放。
- 环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
死锁检测和死锁恢复
每种类型一个资源的死锁检测可以使用资源分配图是否包含环来检测。资源分配图用圆形表示的进程，用方形表示的资源：
- 从资源节点到进程节点的有向边代表该资探已被清求、授权井被进程占用。
- 由进程节点到资源节点的有向边表明当前进程正在请求该资源。
每种类型多个资源的死锁检测需要一个基于矩阵的死锁检测算法，假设有n个进程和
种资源：
是现有资源向量，
第i种资源数量
是可用资源向量，
表示当前可供使用的资源i数量
代表当前分配矩阵，
代表进程i所持有的资源j的数量
代表请求矩阵，
代表
所需要的资源j的数量
每个进程起初都是没有标记过的。死锁枪梢算法如下：
- 寻找一个没有标记的进程
- 如果找到了这样一个进程，那么将C矩阵的第i行向量加到A中，标记该进程， 并转到第1步。
- 如果没有这样的进程，那么算法终止 。
算法结束时，所有没有标记过的进程都是死锁进程。
检测到死锁之后可以采取以下方法，但是都不太理想：
- 利用抢占恢复（不是什么资源都能抢占）
- 利用回滚恢复（不是什么进程都能回滚）
- 通过杀死进程恢复（……）
死锁避免
如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
银行家算法通过检测当前状态是否安全来避免死锁，有现有资潦、已分配资源
、可用资源
以及分配矩阵
和请求矩阵
。检查一个状态是否安全的算法如下：
- 查找
- 假若找到这样一行，那么可以假设它获得所需的资源并运行结束，将该进程标记为终止，并将其资源加到向量A上。
- 重复以上两步，或者直到所有的进程都标记为终止，其初始状态是安全的；或者所有进程的资源需求都得不到满足，此时就是发生了死锁。
死锁预防
根据死锁的四个条件，死锁预防方法有如下几种
| 条件 | 处理方式 |
|---|---|
| 互斥 | 一切都使用假脱机技术 |
| 占有和等待 | 在开始就请求全部资掠 |
| 不可抢占 | 虚拟化资源 |
| 环路等待 | 对资源按序编号 |
其他问题
- 两阶段加锁
- 第一阶段，进程试图对所有所需的记录进行加锁，一次锁一个记录。
- 第二阶段，完成更新然后释放锁。
- 通信死锁：在一系列进程中，每个进程因为等待另外一个进程引发的事件而产生阻塞。
- 活锁：没有进展也没有阻塞。
- 饥饿：一些进程永远得不到服务，虽然它们并不是死锁进程。
第10章：UNIX、Linux和Android
Linux中的进程
Linux中的进程描述符结构通常包含以下内容
- 谓度参数。进程优先级，最近消耗的CPU时间，最近睦联的时间。
- 内存映射。指向代码、数据、堆栈段或页表的指针。
- 信号。掩码显示了哪些信号被忽略、哪些信号需要捕捉、哪些信号被暂时阻塞及哪些信号在传递当中。
- 机器寄存器。当内核陷阱发生时，机器寄存器的内容会被保存。
- 系统调用状态。关干当前系统调用的信息，包括参数和返回值。
- 文件描述符表。当一个与文件描述符有关的系统调用披调用的时候，文件述符作为索引在文件描述符表中定位相关文件的 1节点数据结构。
- 统计。指向记录用户、进程占用系统CPU时间的表的指针。
- 内核堆栈。进程的内核部分可以使用的固定堆栈。
- 其他。当前进程状态。如果有的话，包括正在等待的事件、距离警报时钟超时的时间、PID、父进程的PID以及其他用户标识符、组标识符等。
Linux有过两种调度器
调度器：调度队列被组织成两个数组，一个是任务正在活动的数组,一个是任务到期的数组。每个数组都包含了140个链表头，每个链表具有不同的优先级。链表头指向给定优先级的双向进程链表。
- 调度器从正在活动数组中选择一个优先级最高的任务。如果这个任务的时间片过期了，就把它移动到过期失效数组中。
- 正在等待I/O事件，那么在它的时间片过期失效之前，会被放回到之前正在活动的数组中。
当正在活动数组中没有其他的任务了，调度器交换指针，使得 正在活动数组变为过期失效数组，过期失效数组变为正在活动数组。不同的优先级被赋予不同的时间片长度，高优先级的进程拥有较长的时间片。
- 完全公平调度器：CFS的主要思想是使用一棵红黑树作为调度队列的数据结构。根据任务在CPU上运行的时间长短而将其有序地排列在树中。
- 总是优先调度那些使用CPU时间最少的任务，通常是在树中最左边节点上的任务。
- CFS会周期性地根据任务已经运行的时间，递增它的虚拟运行时间值，并将这个值与树中当前最左节点的值进行比较，如果正在运行的任务仍具有较小虚拟运行时间值，那么它将继续运行，否则，它将被插入红黑树的适当位置，并且CPU将执行新的最左边节点上的任务。
考虑到任务有优先级的差异和，因而当一个任务在CPU上运行时，CFS会改变该任务 的虚拟运行时间流逝的有效速率。对于优先级较低的任务，时间流逝更快。
Linux中的内存管理
每个Linux进程都有一个地址空间
- 代码段包含了形成程序可执行代码的机器指令。
- 数据段包含了所有程序变量、字符串、数字和其他数据的存储。
- BSS段为未初始化数据。
- 堆栈段用于运行时数据存储。
Linux使用伙伴算法进行页分配：
- 当一个内存请求到达时，首先上舍入到2的幕。
- 内存块被分割成两半，如果片段太大，较低的片段被再次二分，然后再二分。直到得到合适大小的内存，把它分配给请求者。
- 如果刚刚释放的两个邻接的
页面块来自同一个
页面块，那么将他们合并。
Linux使用slab分配器分配小对象，它使用伙伴算法获得内存块，但是之 后从其中切出slab(更小的单元井且分别进行管理。因为内核频繁地创建和撤销一定类型的对象（如task_struct)，它使用了对象缓存。这些缓存由指向一个或多个slab的指针组成，而slab可以存储大文相同类型的对象。每个slab要么是满的，要么是部分满的，要么是空的。
