整本书内存分配是重点。IO和CPU协同工作是难点。进程同步是难点。
进程
进程和线程的区别
- 进程是资源分配单位，线程是调用单位
- 线程共享进程资源，共享地址空间，独享栈空间
进程调度的方法
FCFS(先来先服务)，优先级，时间片轮转，多级反馈
进程状态转换
就绪、执行、阻塞
- 时间片用完，进程从执行到就绪(而不是阻塞)
- 执行到阻塞一定是缺失继续执行下去的资源
- 进程一定要从就绪状态才能转换成执行状态
进程同步
进程同步的目的即在当前访问临界资源的进程被系统调度切换到另一个进程时候，保证临界资源不被别的进程访问。
方法有：信号量、关中断、硬件指令
内存分配
首先看到内存分配四个字，就能条件反射知道这是讲什么内容。
内存用来干嘛的，作业要运行，必须装入到内存中。有两个问题：
- 作业是整个装进去，还是离散装进去，离散装进去，是全部都装进去，还是一开始只装需要那部分呢？
- 内存是固定分成大小，还是动态可以变化的(分区可以分割，可以合并)
基于这两个问题，有不同的内存分配算法。
固定分区分配
内存分为N块，每块大小可以不相同，但是是固定的，不能变化的。
动态分区分配
动态就体现在，内存分块大小是可以变化的。
一开始内存不分块。作业需要多大，就划分多大。
但是当作业回收的时候，这个地方就会留下一个空闲块。时间长了，整个内存就会有很多个空闲块。此时可以用一个空闲分区链表把这些空闲的分区都连起来。当有新的作业装入内存，此时就涉及到空闲分区分配算法的问题。
- 首次适应，按地址，从头开始找
- 下次适应，按地址，从上次分配的空闲分区地址开始找
- 最佳适应，按分区大小，选择最小且能装得下的。
- 最差适应，按分区大小，选择最大的
分页/分段分配
我们一直折腾这个内存的分块。
分页/分段是对作业而言的，将作业分成很多个的块。
页和段区别就是
页面大小是固定的，而且和内存的物理块大小是一致的（内存分成等分的物理块）是内存管理自动划分的，用户是看不到的。
段的大小是按照程序员意愿进行划分成大小不等的块。段是信息的逻辑单位。
还有一个问题：我把离散的作业块调入内存，我怎么知道作业的哪一块在内存的哪一块中呢。这就是页/段表的作用。
页表就是作业的逻辑地址和内存的物理地址的映射。
比如32位机器的逻辑地址位数是32位。物理地址位数由真实内存大小确定。
页表和段表的区别1
页表
段表
为什么说段表是二维结构？
因为段号对应两个元素(段长、基址)
而页面只对应一个元素(块号)
请求分页分配(虚拟内存技术)
既然作业都分为离散的块了，根据程序的局部性原理，我们没必要一次性把作业所有的块都调入内存。内存肚子很小的，就不能体谅一下嘛。所以一个作业我只给你分配一定数目的物理块。
就要考虑下面几个问题（这个5个问题对于理解整个过程非常重要）：
- 分配作业的物理块数目是固定的还是动态的？(页面分配算法)
- 作业的哪些页面应该调入到内存中呢？(页面调入算法)
- 如果分配给作业的物理块满了，而现在向又需要调入某个页面，要将谁给置换出去？(页面置换算法)
- 如果分配给作业的物理块有空闲，作业的某个页面调入内存，放在什么位置？(逻辑地址和物理地址的映射关系)
- 如果内存中页面内容修改了，如何处理？(数据一致性问题)
这四个问题，对cache的分配是同样要面对的。只不过把页面/物理块换成cache块(cache块大小和物理块大小并不一定相等)。所以下面我们从共性出发，对于不同的地方进行特别记忆即可。
TLB(块表)、 页表 、cache 、内存
- cache 是存储在高速缓存中，页表存储在内存中
- 页表是作业与内存的页号和块号的映射。TLB是内存与cache的分块映射。
cache分配和内存分配的区别：
- cache内容是内存的一个副本，需要保存数据一致。而内存内容是从磁盘(作业的位置)调入的，可以不一致，当置换出去的时候再写入磁盘即可，无需特别的保持数据一致性。
- 一般给作业分配的物理块比较少，所以内存分配一般没说明的话都是直接相连，而cache与内存的映射关系比较复杂。
页面分配算法
对于内存分配来说，可以是固定的，即一开始就给作业分配好固定数目的物理块。这样当内存中物理块满了，就需要将这些物理块其中一个的内容置换出去。即固定分配，局部置换。
也可以是动态的，又分为两种情况：
- 一开始就不给作业分配物理块，内存维护一个空闲物理块链表，作业页面需要进内存，就直接从这个链表中选择一个空的物理块装入即可。如果系统整个内存都满了，就调出其他进程的一页。即动态分配，全局置换
- 一开始分配一定数目的物理块，内存也维护一个空闲物理块链表。作业页面需要进内存，如果自己物理块满了，先置换自己的。如果这个作业频繁的发送缺页中断，频繁置换自己的物理块，那系统就看不下去了，就从空闲物理块链接给他分配一个。如果这个作业基本不发送中断，就可以适当减少他的物理块。即动态分配，局部置换
对于内存分配一般使用的是固定分配，局部置换算法。
对于cache来说，因为cache大小很小，所以所有作业共享同一个cache空间，即使用的是动态分配，全局置换。
这三种方式就和教育方式很像。
第一种，给孩子一个月零花钱固定的，你要用完了，还想买别的东西，那你就卖掉一些你自己的东西，我不会多给你。
第二种，明显的溺爱，你要买啥，我就给你钱。如果家里没钱了，爸爸少花点钱买烟。
第三种，一开始给你一个固定数额，你要用完了，还想买别的东西，那你也得卖掉一些你自己的东西。但是如果家长发下这个孩子频繁的买东西，就多加一点钱。如果发现这个孩子基本上不靠卖东西赚钱，就可以少给点钱。
页面调入算法
一开始cache/内存中都是空闲的。可以一开始就进行判断调入一些可能接下来会用到的页面/cache数据块，即预调页策略。
也可以一开始不调入，等缺页/cache未命中，再进行调入。即请求调入策略。
映射关系
这个我当时学起来真的很费劲。
它解决的问题就是数据块要调入cache的时候，不能有空闲的位置，就直接坐下来，必须遵循一个规则，比如这个数组块在内存是某个组的第三个成员，那它一定要坐在cache的第三组中。就算第一组有空位置，你都不能去。
这种映射规则也就决定了当cache满的时候，它只能置换掉指定组的一个成员，如果指定组有多个成员，就继续按照页面置换算法进行选择置换。
规则如下：
cache有M行，给所有行分组，一共有N组。
主存也要分组，每组成员数为N。
主存的某个数据块和cache的某个组对应。
如果cache只分了一组，就是直接相连。
cache分了M组(N = M)，就是全相连。
否则就是组相连。
为什么要搞这么复杂的映射关系？
我内存分配多简单是吧。给定的物理块集合有空闲的，直接进去完事了，你还得规定我只能进特定的组，你是不是有毛病？
原因就是因为页表存在内存中，内存空间大啊。而TLB存在高速缓存中，人家寸土寸金，你的TLB块表自然越小越好。
TLB表大小和映射关系到底什么关系？
TLB表结构和页表很像，就是把页号变成数据块内容。即每一行结构可以简单的如下：
数据块号 + 数据块内容
数据块号标记内存的哪一个数据块。(特别提醒：数据块大小和物理块大小不一定一致，所以这里块号准确的名词应该是标记位)
通过映射关系可以帮我们减少这个标记位的长度，因为映射关系本身能提供一些信息。
举个例子，cache一共16行，分为8组，每组2行。主存一共分成了32组，每组8个成员。
可以看到主存本来是有32×8 = 2^8，即数据块号需要8位。主存的第三块必须要进入第三组(3%8=3)
这样块号可以分割成两个部分：剩余部分（5位），组号(3位)
其中组号直接可以从数据块在cache的位置看出来，就没必要存在标记位里了（这个组号信息就是映射关系提供的）。所以标记位只需要存储剩余部分即可。标记位长度由8位减小成5位。
还可以看出，分组越多，标记位越小（全相连映射标记位数最少）。但带来的问题就是容易发生冲突。比如主存数据块号为3和11就会抢占同一组。
页面置换算法
不管是固定分配还是动态，当所有的物理块都被占用，新的页面又必须调入进来，就必须淘汰一些人。
我们学习这部分，课本上讲的都是页面置换，即内存分配中发生的情况，但实际上cache分配同样会使用这个算法(一个组有多个成员)。如果题目考察比较细致，综合性就比较强。
有最佳置换、FIFO、LRU(最近最少使用算法)、Clock算法。具体细节以后单独再展开。
数据一致性问题
这个其实并不是cache分配特有的问题。内存分配只是默认都是回写法
因为cache是内存一些块的副本。必须保证这两个地方的数据是一致的。
所以当cache中的数据被修改了（写操作），内存那边要怎么办？
未命中
- 先读到cache中，对cache中数据修改
- 先对内存中数据修改，再读到cache中
命中：
- cache和内存同时修改(全写法)
- 只对cache数据进行修改，当该数据块被置换出去时候，再对内存中数据回写(回写)
可以看出第二和第三种方法是时刻保持cache和内存的数据一致的。但第一和第四可以提升速度。
总结
内存分配是固定分配+局部置换+直接相连映射+页面置换+回写法数据一致性算法
cache分配是动态分配+全局置换+多种映射关系+对指定映射的组成员进行页面置换+多种数据一致性算法
如果能理解上面这个过程，应该对内存分配和cache分配理解差不多。
文件管理
硬链接和软链接
这两个概念真的是记了忘，忘了记。我很无奈。
- 软链接，比如Windows上面的新建一个快捷方式。当原来的程序卸载了，快捷方式还保留着，但是打开的时候提示"找不到应用程序"。这个软链接文件的目录项的内容只是目标文件的路径名，而且该目录项会被标识为"link"。
- 硬链接，硬链接文件的目录下内容和目标文件的是同一个索引节点(索引分配)，或者是同一个FCB（隐式链接分配）。删除的时候，删掉一个其中文件，该文件的引用计数会减1，只有文件
文件在磁盘上的物理分配
目录项、inode节点、FCB
操作系统名词贼多，一个个看起来很厉害的样子。
inode节点和FCB都是描述目录项一种方式。目录项则是描述文件的信息(包括名称和在磁盘上位置)。
inode节点就是FCB把文件名称信息去掉，其他信息组合在一起，创建一个新的名字。
连续分配
文件挨个划分为等大小的磁盘块，然后挨个顺序的存放在磁盘中。FCB记录其实块号和大小。
显式链接分配
磁盘块中除了文件内容，再划分一小块作为指针区域，指向下一个磁盘块。FCB只需要记录起始块号。
隐式链接分配
指针的信息都放在一个FAT表中。表是一维结构。表的行号表示物理块号，表的行的内容表示下一个链接的物理块号。
FCB只需要记录起始物理块号，然后去FAT表中查询即可。
索引分配
每个文件建立一个索引表，索引表存储在磁盘中。索引表的内容就是该文件在磁盘中的所有物理块。
FCB记录索引表的物理块号即可。
IO系统
程序中断
CPU读磁盘数据的时候，磁盘输出的速率慢，CPU的读的速度很快。磁盘有一个数据寄存器，只能存放一个字节。
磁盘输出的时候，CPU不要忙等，而是等数据寄存器满了之后，叫CPU(发起中断请求)。
DMA
在程序中断原理上，增加DMA控制器。CPU一开始把要读取的字节数告诉DMA。每次磁盘的数据寄存器满了，直接发起DMA请求，DMA把数据运到内存（这个过程需要和CPU争夺总线周期的）。直到指定的字节数读完了，DMA控制器发起中断请求，让CPU处理后事。
