第一部分概述
一、导论
1.操作系统做什么
① 冯诺依曼体系结构 ② OS角色：对上：控制程序正确执行，使用方便；对下：资源分配器 ③ 核心功能：进程管理，内存管理，文件管理，输入输出，保护和安全 2.计算机系统组织
① 中断 ② 存储结构：寄存器→高速缓存→主存→电子磁盘→光盘→磁带 ③ I/O结构：I/O的同步、异步；慢速设备（中断）快速设备（DMA） 3.操作系统结构：多道（使CPU总有一个任务执行）、分时（高频率切换任务） 4.进程管理
① 进程有其生命周期，进程是执行中的程序 ② 管理活动：创建或删除用户或系统进程；挂起或重启进程；防死锁；提供进程同步、通信机制 ③ 目的：使进程可以运行，相互协调不死锁 5.内存管理
① 目标：内核健壮 ② 保护方法：独立操作模式:用户模式，内核模式；计数器定时中断防止死循环 6.存储管理
① 解决问题：速度匹配→缓存（缓存的命中率） ② 等级问题：一致性；多处理器下各缓存的一致性
二、操作系统结构
1.操作系统服务：用户界面，程序执行，I/O操作，文件系统操作，通信，错误检测，资源分配，统计，保护和安全。
2.操作系统的用户界面：命令解释程序，图形用户界面
3.系统调用类型：进程控制，文件管理，设备管理，信息维护，通信
4.系统程序分类：文件管理，状态信息，文件修改，程序设计语言支持，程序装入和执行，通信，系统工具，应用程序。 5.操作系统结构：
① 简单结构(MS-DOS)：小空间多功能，应用程序直接操作硬件，不安全，无模块，接口和功能层次没有区分 ② 分层法：难划分，效率低，但是构造和调试简单化 ③ 微内核：包括最小的进程和内存管理以及通信，便于扩充操作系统。 ④ 模块化：动态加载模块，允许内核提供核心服务，也能动态的实现特定的功能 ⑤ 组合结构
第二部分进程管理
一、进程
1.进程的概念
① 进程通常包括：程序计数器，栈，数据段 ② 进程状态：新建，运行，等待，就绪，终止 ③ 进程控制块PCB：进程状态，程序计数器，CPU寄存器，CPU调度信息，内存管理信息，记账信息，I/O状态信息 ④ 2.进程调度
① 调度队列：作业队列，就绪队列，设备队列
P80 ② 调度程序：长期调度程序（作业调度程序）：从作业池中选择进程，并装入内存准备执行。短期调度程序（CPU调度程序）：从准备执行的进程中选择进程，并为之分配CPU时间。中期调度程序：能将进程从内存中移出。
长短期的区别是执行频率；长期调度控制多道程序设计的程度，中期调度可以降低多道。 ③ I/O绑定进程，CPU绑定进程 ④ 上下文切换：将CPU切换到另一个进程需要保存当前进程的状态和恢复另一进程的状态。
3.进程操作
① 进程创程：创建新进程的执行方式（父子进程并发执行；父进程等待直到某个或全部子进程执行完毕）
新进程地址空间（子进程是父进程的副本；子进程装入另一个新程序） 资源共享（所有/子集/不共享） ② 进程终止
父进程终止子进程的原因（子进程使用了超过它分配的资源；分配给子程序的任务不需要了；父进程结束）
4.进程间通信
① 通信基本模型：共享内存，消息传递 ② 共享内存：消费者可能等待生产者；无限缓冲区，有限缓冲区的区别 ③ 消息传递：
命名：直接通信（对称寻址：接受者命名发送者；非对称寻址：接受者不需要命名发送者）间接通信（邮箱、端口的参与） 同步：阻塞与非阻塞（发送，接收），同步与异步 缓冲：零容量（无缓冲）；有限容量、无限容量（自动缓冲）
5.客户机-服务器通信：套接字SOCKET，RPC远程调用，RMI远程方法调用
二、线程
1.概述：多线程优点：响应度高，资源共享，经济，多处理器体系结构的利用
2.多线程模型：用户层的用户线程或内核层的内核线程，用户线程受内核支持，而无需内核管理，而内核线程由操作系统直接支持和管理，这两种方法支持多线程。 ① 多对一模型（效率比较高，阻塞系统调用的后果） ② 一对一模型（更好的并发功能，缺点是创建一个用户线程就需要一个内核进程） ③ 多对多模型（用户可以创建任意多的线程；二级模型=多对多+一对一） 3.多线程问题
① 系统调用fork().exex() ② 线程取消异步取消（立即终止），延迟取消（检查是否应该终止） ③ 信号处理：信号必须有一个处理程序 ④ 线程池：优点（处理请求速度快，线程数量可控制）
三、CPU调度
1.基本概念
① CPU区间和I/O区间的概念 ② 抢占与非抢占调度的概念（发生在：一个进程从运行切换到等待、运行切换到就绪、等待切换到就绪、以及终止，1,4非抢占，2,3抢占） 2.调度准则：CPU利用率（使CPU尽量忙），吞吐量（测量工作的方法），周转时间（从进程提交到完成的时间），等待时间，响应时间 3.调度算法
① 先到先服务调度FCFS（非抢占的） ② 最短作业优先调度SJF（抢占，最优算法，难知道下一CPU区间长度，用于长期调度） ③ 最短剩余时间优先调度SRTF（强占式的SJF，适合长期调度） ④ 优先级调度（问题：无穷阻塞或饥饿，老化来解决；非抢占方式不用占用CPU切换） ⑤ 轮转调度RR（专为分时系统设计，是可抢占的，时间片过大变为FCFS，时间片过小等待时间段，但是切换频繁） ⑥ 多级队列调度（前台与后台的调度算法不同，RR与FCFS）？ ⑦ 多级反馈队列调度 ⑧ 实时调度：硬实时（在特定硬件上保证时间），软实时：尽力而为，优先级不变，没有饥饿现象
4.算法评估
① 确定性模型甘特图 ② 排队模型 N=入*W（N平均队列长度，W为队列的平均等待时间，入为新进程到达队列的平均到达率） ③ 模拟 ④ 实现
四、进程同步
1． 背景：竞争条件：共享内存，共享变量 2． 临界区问题
① 临界区解决方案：进入去，临界区，退出区，剩余区 ② 效果：互斥，有空让进，有限等待 ③ 证明：1.互斥，临界区一个时间只能有一个进程2.前进，临界区内无进程执行，那么只有那些不在剩余区内执行的进程可参加选择，这种选择不能无限延迟3.有限等待，从一个进程做出进入临界区的请求，知道该请求允许为止，其他进程允许进入其临界区的次数有上限。 ④ PETERSON算法
3． 信号量：计数信号量，二进制信号量
① 技术信号量用于控制访问：当每个线程需要使用资源时，需要对该信号量执行acquire()操作，当线程释放资源时，需要对该信号执行release()操作。 ② 用信号量解决同步问题
4． 管程：管程结构确保一次只有一个进程能在管程内活动 5． 经典同步问题
① 生产者消费者问题 ② 读者写者问题 ③ 哲学家吃饭问题
五、死锁
1.死锁特征
① 必要条件：互斥，占有并等待，非抢占，循环等待 ② 资源分配图：分配图没有环则没有死锁，有环则有死锁；有环则可能有死锁。 2.死锁预防
① 互斥：通常不能通过否定互斥条件来预防死锁：有的资源本身就是非共享的。 ② 占有并等待：协议一：每个进程在执行前申请并获得所有资源；协议二，允许进程在没有资源时才可以申请资源。协议缺点：资源利用率低，可能发生饥饿。 ③ 非抢占：协议：如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现在已分配的资源都可被抢占。 ④ 循环等待：对所有资源类型进行完全排序，且要求每个进程按递增顺序来申请资源。
3.死锁避免
① 安全状态:如果系统能按某个顺序为每个进程分配资源并能避免死锁，那么系统状态就是安全的。 ② 单实例：资源分配图：申请边，分配边，需求边 ③ 多实例：银行家算法Available(向量),Max（矩阵）,Allocation（矩阵），Need(矩阵), 4.死锁检测
① 单实例：等待图：当且仅当等待图中有一个环时，系统存在死锁 ② 多实例：类似银行家算法 5.死锁恢复
① 进程终止：终止所有死锁进程；一次只终止一个进程，直到取消死锁循环为止 ② 资源抢占：问题：选择一个牺牲品；回滚；饥饿
第三部分内存管理
一、内存管理
1.背景
① 地址绑定：编译时（编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码），加载时（生成可重定位的代码），运行时（如果进程在执行时可以从一个内存段移到另一个内存段，那么绑定必须延迟到执行时才进行） ② 逻辑地址（CPU所生成的地址）物理地址（内存单元所看到的地址） ③ 动态加载（子程序只在调用时加载，优点不用的子程序绝不会被加载） ④ 动态链接与共享库（将连接延迟到运行时） 2.交换（没看）
3.连续内存分配：单分区，多分区
4.非连续内存分配：分页（分页技术不会产生外部碎片） 5.动态存储分配问题：首次适应，最佳适应，最差适应 6.页表结构：层次页表，哈希页表，反向页表
二、虚拟内存
1.背景
① 多道尽可能多的程序，这也是内存管理的目标 ② 虚拟内存好处：可以运行比物理内存大的程序；更快的启动和响应（载入更快）；更多的多道；更容易的共享文件盒地址空间；更少的输入输出。
2.按需调页：在需要时才调入页
① 有效位-无效位来来确定页是否在内存 ② 有帧就加入，无帧就换页，页错误处理流程：检查内部表确定引用是否合法→非法则终止，合法则调入→找到空闲帧，装入内存→修改内部表→重启指令 ③ 按需调页的有效访问时间：effective acce time=(1-p)*ma+p*处理页错误的时间 3.页面置换（引用串）
① FIFO 先入先出 ② 最优算法：向后看，换页的时候看内存中哪个页最晚用；是所有算法中产生页错误最低的算法；问题：需要引用串的未来知识 ③ LRU最近最少使用算法：往前看，内存中哪页在列表序列中离的最远，无Belady异常 ④ 算法实现：计数器（最近最少使用：换计数器值最小的）代价大：系统级，可能溢出，一定会写全表
页码堆栈：每当引用一个页，该页就从栈中删除并放在栈顶。严格实现，但是代价高。
二次机会：引用位，引用时改为1,；换页时，是1则置零，是0则换 计数算法：LFU最不经常使用， MFU最经常使用（可采用老化）
4.帧分配
① 分配策略限制：所分配的帧不能超过可用帧的数量，大于最小需求 ② 每个进程帧的最少数量是由体系结构决定的，而最大数量帧是由可用物理内存决定的。 ③ 当指令完成之前出现页错误，该指令必须重新执行 ④ 帧分配方法：
固定分配：平均分配、按比例分配 优先级分配：全局置换（帧数可变），局部置换（固定）；全局置换算法的一个问题是进程不能控制其页错误率，但是全局置换通常会有更好的系统吞吐量，且更为常用。
5.系统颠簸
① 颠簸产生的原因：抢帧→I/O上升→CPU使用率降低→多道继续增加→忙于换页 ② 工作集合策略防止了颠簸，并尽可能的提高了多道程序的程度，可以通过页错误频率PFF来直接测量和控制页错误以防止颠簸。上限之上分配更多，下限之下，减少帧数
6.其他问题
① 预调页关键问题：采用预调页的成本是否小于处理响应页错误的成本。 ② 页大小问题：最佳页大小的选择，大页，小页 ③ 优化程序结构
第四部分存储管理
一、文件系统接口
1.文件概念
① 文件是逻辑外存的最小分配单元，即数据除非在文件中，否则不能写到内存中。 ② 文件操作：写，读，重定位，删除，截短 ③ 文件加锁：共享锁，专用锁；强制，建议文件加锁机制 2.访问方法：顺序访问，直接访问，其他方法（索引） 3.目录结构
① 目录操作：创建文件，删除文件，遍历目录，重命名文件，跟踪文件系统 ② 评价目录结构：命名（不同文件同名），分组（同一文件不同命名） ③ 单层结构目录（命名，分组均无），双层结构目录（可命名不可分组），树状结构（绝对，相对路径；可命名分组），无环图目录（硬链接，软链接），通用图目录
二、文件系统实现
1.文件系统结构：应用程序→逻辑文件系统→文件组织模块→基本文件系统→I/O控制→设备
2.目录实现：线性列表（编程简单，运行费时，查找文件需要线性搜索）
哈希表（采取策略避免冲突）
3.分配方法
① 连续分配：每个文件在磁盘上占有一组连续的块；困难时为新文件找到空间，外部碎片问题也可能很大，确定文件分配多大空间， ② 链接分配：解决了连续分配的所有问题；必须顺序访问文件，指针需要空间，由于指针分配在整个磁盘，可靠性就成了一个问题。
FAT文件分配表：改善了随机访问时间，但是需要大量磁头寻道时间 ③ 索引分配：把所有指针都放在一起，构成索引块；支持直接访问，且没有外部碎片问题，但是会浪费空间；索引块分多大是个问题 链接方案（一个索引块可以指向另一索引块构成链接）
多层索引（第一个索引块指向第二个索引块，第二个指向文件数据块） 组合方案P404 N级间接块（计算）
4.空闲空间管理：为向量（1空0满）块号码计算：（值为0的数字）*（一个字的位数）+第一个值为1的位的偏移；链表（所有空闲的块用链表链接起来）；组（将N个空闲块的地址存储在第一个空闲块中）；计数（）
