基础原理篇
操作系统构成
- CPU管理——进程
- 内存管理——虚拟内存
- 外存管理——文件系统
- 设备管理——I/O
- 批处理管理
操作系统发展阶段
- 状态机操作系统(1940年以前)
- 单一操作员操作系统(20世纪40年代)
- 批处理操作系统(20世纪50年代)
- 多道批处理系统(20世纪60年代)
- 分时操作系统和实时操作系统(20世纪70年代)
- 现代操作系统(1980年以后)
内核态与用户态
- 内核态就是拥有资源多的状态，或者说访问资源多的状态，我们也称之为特权态。相对来说，用户态就是非特权态，在此状态下访问的资源将受到限制。
- 运行在内核态的程序可以访问的资源多，但可靠性、安全性要求高，维护管理都复杂；用户态运行的程序则编写和维护简单。
系统调用
系统调用分为三个阶段，分别是：
- 参数准备阶段
- 系统调用识别阶段
- 系统调用执行阶段
以用户程序调用read为例，在参数准备阶段，需要使用系统服务的程序将系统调用所需的参数压入栈中(最高效的是直接放到寄存器中)，然后调用库函数read，而库函数read将调用系统调用read的代码放入一个约定好的寄存器中，通过陷入(trap，一种中断方式)将控制交给操作系统。由此进入第二阶段。操作系统获取控制后，将系统调用代码从寄存器取出，与操作系统维护的一张系统调用表进行比较，获得系统调用read的程序体所在的内存地址。之后跳到改地址，进入第三阶段，执行系统调用函数，执行完毕后返回到用户程序。
CPU管理——进程
进程
进程表示进展中的程序，操作系统通过进程表来管理，在任何时候，进程占有的所有资源，包括分配给进程的内存、内核数据结构和软资源形成一个进程核(Core),核快照(Core Image)代表进程的某一特定时刻的状态。
进程创建
- 分配进程控制块
- 初始化机器寄存器
- 初始化页表
- 将程序代码从磁盘读取进内存
- 将处理器状态设置成用户态
- 跳转到程序的起始位置(设置程序计数器)
进程的创立在不同的操作系统所需方法不一样，例如unix中，分为两个步骤：
- fork，创建一个与自己完全一样的新进程。
- exec，将新进程的地址空间用另一个程序的内容覆盖，然后跳转到新程序的起始地址，完成新程序的启动。
线程
线程是进程的一个执行序列，同一进程下的线程共享进程的地址空间、文件、信号、全局变量等，而线程间的独享资源有：程序计数器、寄存器、栈、状态字。
线程管理
线程既然是进程的构成部分，则通过进程自己管理还是操作系统管理可以分为用户态线程实现(进程自己管理)和内核态线程实现(操作系统管理)。
- 内核态线程实现优点：用户编程简单，线程的复杂调度由操作系统承担，用户编程时无需管理线程调度，并且如果一个线程阻塞，则操作系统可以调度另一个线程。
- 内核态线程实现缺点：效率较低，由于线程在内核态实现，每次线程切换都需要先陷入内核。此外，内核态实现占用内存资源，操作系统由于需要维护线程表导致线程数量过多会耗尽内核空间。第三，为了管理线程，需要修改操作系统。
- 用户态线程实现优点：首先，灵活性强，操作系统不知道线程的存在，所以任何操作系统上都能应用，其次，线程切换快，因为切换发生在用户态，无需陷入内核，第三，不需要修改操作系统，实现容易。
- 用户态线程实现缺点：编程困难，由于线程需要相互合作才能运转，因此需要考虑什么时候让出cpu资源给其他线程使用。
线程何时从用户态进入内核态
- 如果程序运行过程中发生中断或异常，系统将自动切换到内核态来运行中断或异常处理机制。
- 程序进行系统调用也会造成用户态进入内核态的转换。
进程通信
- 无名管道
- 有名管道
- 信号
- 共享内存
- 消息队列
- 信号量
- 套接字
进程同步
- 锁
- 信号量
- 管程
- 消息传递
- 栅栏
线程同步
- 临界区
- 事件
- 互斥量
- 信号量
锁
操作系统之所以能够构建锁之类的同步源语，原因就是硬件已经为我们提供了一些原子操作：中断禁止和启动、内存加载和存入、测试与设置指令。有了这些硬件原子操作，我们便能够构建软件原子操作：锁、睡眠与叫醒、信号量等。
上述三种实现方式中测试和设置相对来说更为简单实现锁机制，此外该方法可以适用于多CPU环境而中断启用和禁止则不能。
死锁
死锁的4个必要条件：
- 互斥
- 请求和保持
- 非剥夺
- 环路等待
死锁应对
允许发生死锁
假装没看见，不予理睬
死锁检测与修复
- 死锁检测，类似与银行家算法(实现动态避免死锁)
- 死锁恢复，抢占或杀死进程
这种策略弊端较多，首先检测和恢复是难题，其次检测进程死锁，则发生致命问题。
不允许死锁发生
资源分配动态检测是否会发生死锁，避免死锁发生
消除死锁的必要条件，杜绝死锁发生
哲学家就餐问题
#define N 5 /*哲学家人数*/
#define LEFT(i) ((i+N-1)%N) /*哲学家i左边的哲学家*/
#define RIGHT(i)((i+N-1)%N) /*哲学家i右边的哲学家*/
#define THINGKING 0 /*思考状态*/
#define HUNGRY 1 /*饥饿状态*/
#define EATING 2 /*吃饭状态*/
typedef int semaphore;
int state[N]; /*记录每个哲学家当前状态的数组*/
semaphore mutex = 1; /*互斥信号量*/
semaphore s[N]; /*每个哲学家等待一个单独信号量*/
void philosopher(int i){
while(TRUE){
think();
take_forks(i); /*同时获得两根筷子，否则阻塞等待*/
eat();
put_forks(i); /*同时放下两根筷子*/
}
}
void take_forks(i){
down(&mutex);
state[i] = HUNGRY;
test(i); /*试图拿起两根筷子*/
up(&mutex);
down(&s[i]); /*如果没有拿起筷子，则阻塞等待*/
}
void put_forks(i){
down(&mutex);
state[i] = THINKING;
test(LEFT(i)); /*测试左面的哲学家是否可以吃饭*/
test(RIGHT(i)); /*测试右面的哲学家是否可以吃*/
up(&mutex);
}
void test(i){
if(state[i]==HUNGRY&&state[LEFT(i)]!=EATING&&state[RIGHT(i)]!=EATING){
state[i] = EATING;
up(&s[i]);
}
}
内存管理——虚拟内存
内存管理目标
- 地址保护：一个程序不能访问另一个程序地址空间。
- 地址独立：程序出发的地址应与物理主存地址无关。
虚拟地址
物理地址 = 虚拟地址 + 程序所在区域的起始地址
由此我们只需要记录两个端值：基址和极限，即可达到地址翻译和地址保护的目的，这两个端值可以由寄存器来存放，分别称为基址寄存器和极限寄存器。
if(虚拟地址 > 极限){
陷入内核
停止进程(core dump)
}else{
物理地址 = 虚拟地址 + 基址
}
交换
交换就是将一个进程从内存倒出到磁盘上，再将其从磁盘上加载到内存中来的过程。这种交换的主要目的是为程序找一片更大的空间，从而防止一个程序空间不够而崩溃。交换的另一个目的是实现进程切换，就是将一个程序暂停一会，让另一个程序运行。不过这样使用交换成本高，一般不这么做。
闲置空间管理
- 位图法
- 链表法
内存管理
- 固定加载地址的内存管理(只是用与单道编程)
- 固定分区的内存管理
- 动态分区的内存管理
- 交换内存管理
- 分页内存管理
- 分段内存管理
- 段页式内存管理
分页内存管理
分页系统的核心是将虚拟内存空间和物理内存空间皆划分为大小相同的页面，并以页面作为空间分配的最小单位，一个程序的一个页面可以存放在任意一个物理页面里。这样将不会产生外部碎片。同时，由于一个虚拟页面可以存放任何一个物理页面里，空间增长也容易解决，只需要分配额外的虚拟页面，并找到一个闲置的物理页面存放即可。
地址翻译
- 虚拟地址有两部分组成：页面号和页内偏移量
- 分页系统对于任意一个虚拟页面，首先检测是否合法，之后系统可以判断该页面是否在物理内存中，如果在，其对应的物理内存是哪一个。如果不在的话，则产生一个系统中断(缺页中断)，并将该虚拟业从磁盘加载到内存，然后分配物理页面号。
- 系统通过查页表可得知是否在物理内存以及对于的物理页框号，此外页表项中还存有该页面的其他信息例如是否在缓冲，是否受保护等。
- 单级页表每次内存访问都需要至少2次内存访问，一次查页表，一次读取访问内容，若有缺页中断，则还需要一次磁盘读取。而多级页表则访问次数更多。
- 为了加快访问次数，系统添加了快表(TLB)，实现快速定位。
缺页中断过程
- 硬件陷入到内核
- 保护通用寄存器
- 操作系统判断所需的虚拟页面号
- 操作系统检测地址的合法性
- 操作系统选择一个物理页面用来存放将要调入的页面
- 如果选择的物理页面保护有未写入的内容，则首先进行写盘操作
- 操作系统将新的虚拟页面调入内存
- 更新页表
- 发生缺页中断的程序进入就绪状态
- 恢复寄存器
- 程序继续
页面置换算法
- 随机更换算法
- 先进先出算法
- 第二次机会算法
- 时钟算法
- 最优更换算法
- NRU算法
- LRU算法
- 工作集算法
- 工作集合时钟算法
段式内存管理
分段即将程序分为多个段，每个段使用一个虚拟地址空间，这样克服了分页的缺点——只能使用一个虚拟地址空间。事实上，基本内存管理的一段式管理称为纯粹分段，而一个程序分为多个段的分段管理称为逻辑分段。分段使用的段表，记录了每个段的基址。段页式管理则段表中记录了次级页表的地址，通过段表得到页表，再来定位段内的页地址。
外存管理——文件系统
文件系统目标
- 地址独立：一个文件在产生的时候无需担心其存放的磁盘地址，即文件数据的产生与文件将来存放的磁盘地址互相独立。
- 地址保护：对文件的访问进行一定的限制，即不是任何人都能够访问任何文件。
文件类型
大部分操作系统支持多种文件，根据文件的内容是用户数据还是文件系统本身数据，文件可分为三种：目录、一般文件、块文件。
- 目录：记录文件的文件，它的内容关乎别的文件。
- 一般文件：文本文件和二进制文件
- 块文件：既不是关于别的文件也不是用户数据文件，而是关于输入输出设备的。具体来说，块文件模拟输入输出，提供给输入输出一个抽象。
为什么要分区
- 分区可以方便我们对磁盘的使用，不同分区可以建立不同的文件系统。
- 分区有安全优势，一个分区毁坏，另一个分区仍然可以使用。
- 分区还有可靠性的优势，因为一个分区的故障不影响另一个分区的运行。
- 磁盘空间的使用，操作系统能访问的磁盘地址是有限的，如果磁盘大小超过访问空间，则剩下的磁盘就不能够被访问了，因此必须分区。
文件系统布局
- MBR(主引导记录)，该记录的内容是一个小程序，用来启动计算机。
- 磁盘分区表，给出磁盘的所有分区以及其开始地址和终结地址，其中一个分区为主分区，操作系统就装载在这个分区，主分区里面最前面的是引导记录(BOOT RECORD)。
- 计算机启动时，处于主板ROM的BIOS程序首先运行。
- BIOS在进行一些基本的系统检测和配置扫描后对磁盘的扇面0进行读操作，将MBR里的程序读到内存运行。
- MBR程序接下来找系统主分区，并将主分区里面的BOOT RECORD加载运行。
- BOOT RECORD里面内容是一个小程序，改程序负责找到操作系统映像，并加载到内存，从而启动操作系统。
- BOOT RECORD记录块后面的内容根据文件系统的不同而不同，但通常情况下，紧接着后面的是一个超级数据块(SUPER BLOCK)，该块里面存放关于文件系统的各种参数。SUPER BLOCK后则是磁盘自由空间，其后是I-NODE区，再后面是文件系统根目录区。分区最后存放用户文件和文件夹区(文件夹的目的是实现文件名到文件地址的映射)
文件的实现
文件的实现，归根结底，就是要把文件的内容存放到合适的地方，并能够在需要的时候很容易读出这些数据。这样，文件的实现要解决的就是如下的三个问题：
- 给文件分配磁盘空间：按照用户要求或文件大小分配恰当容量的磁盘空间
- 记录这些磁盘空间的位置
- 将文件内容存放在这些空间：通过磁盘本身的驱动实现
上述三点均需要了解数据在磁盘上存放方式：
- 连续空间存放
- 非连续空间存放
- 链表方式：链表、FAT
- 索引方式：I-NODE
设备管理——I/O
输入输出目的
- 设备独立：输入输出不以设备不同而不同，即屏蔽输入输出设备上的差异，实现同一接口
- 设备保护：一个输入输出设备不影响另一个输入输出设备
物理I/O模式
根据CPU与设备控制器的沟通以及与内存的不同关系，可以分为：
- 专有通道I/O : 与内存完全脱离，输入输出不影响内存，但对其访问需要专门的指令
- 内存映射I/O : 将I/O映射到内存，实现同一访问方式，但存在总线竞争和控制器缓存更新问题
- 混合I/O
根据CPU在输入输出过程中的涉入程度来分：
- 繁忙等待访问
- 直接内存访问
逻辑I/O模式(软件I/O模式)
- 可编程I/O原理
- 中断驱动I/O原理
- 直接内存访问I/O原理
I/O软件的目的
- 设备独立：程序对I/O设备的访问不依赖与设备的物理特征
- 统一命名：设备或文件的命名不依赖于具体的计算机
- 错误处理：对输入输出过程中产生的数据错误进行侦测与纠正
- 数据传输：实际操作数据在主机与外设之间传递
- 缓冲：为数据传输提供一个临时存放地，方便将数据拷贝到目的地
- 共享与独享：将设备尽量变为共享，以增大资源利用率和降低死锁发生的概率
I/O软件的分层
- 中断服务程序
- 设备驱动程序
- 设备独立的OS软件
- 统一界面(统一功能清单)
- 缓冲
- 错误报告
- 用户层I/O软件