操作系统
更新: 2021-01-10 00:30:31
按点总结
1.系统调用
用户与操作系统进行交互，从而请求系统执行一些只有操作系统才能做到的指令，每个这样的请求都是由用户调用来执行特权指令的，这种请求成为系统调用。操作系统内核提供一系列预订功能，通过一组成为系统调用的接口呈现给编程人员，系统调用把应用程序的请求传给内核，系统调用相应的内核函数完成所需的处理，将处理结果返回给应用程序。
每个系统调用都跟一个数相关，通过索引找内核函数，类似于中断向量表，系统调用本质上也是一种软中断。
API掩盖细节，提供方便的功能，可移植性强，系统调用太复杂了。
向操作系统传递参数：堆栈；寄存器；内存。
特权指令：能引起及其损害的。
2.进程
进程上下文用进程的PCB表示，它包括寄存器的值、进程状态和内存管理信息等。通常通过执行一个状态保存来保存CPU的当前状态（不管他是内核模式还是用户模式），之后执行一个状态恢复重新开始运行。
PCB是进程存在的唯一标志。
PCB的组织：链接方式是每个队列对应一个表，索引是每个队列对应一个索引表，差不多。
并发：在某一个时间段内任务交替执行；并行：多个任务同时执行。
进程状态转换：
标准答案：
进程调度
高级调度 作业调度 长期调度
中级调度 内存调度 中期调度
低级调度 进程调度 短期调度
进程的挂起与7状态模型
子进程
fork 子进程做父进程的上下文拷贝，包括PCB和新的地址空间。
pid = fork() 父进程返回子进程号，子进程返回0，错误-1。
3.格式化
磁盘的格式化分为 物理格式化和逻辑格式化 。 物理格式化又称低级格式化，是对磁盘的物理表面进行处理， 在磁盘上建立标准的磁盘记录格式，划分磁道（track） 和扇区（sector）。逻辑格式化又称高级格式化， 是在磁盘上建立一个系统存储区域，包括引导记录区、 文件目录区FCT、文件分配表FAT。
逻辑格式化创建了文件系统。
4.VFS
物理文件系统与文件系统服务之间的一个接口层，对物理文件系统的所有细节进行抽象，并为这些不同的文件系统提供一个统一的系统调用接口。严格来说不是一个文件系统，只存在于内存中，不存在于任何的外存空间，在系统启动时建立，系统关闭时消亡。
5.线程
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。进程是除CPU之外的系统资源的分配单元。
内核级线程才是处理机分配的单位。
**用户级线程、内核级线程。**多线程模型（用户级线程与内核级线程的映射关系）：多对一、一对一、 多对多。
处理器只能看到内核级线程，对于多核只能调度这个。
不共享栈和寄存器。
6.CPU调度
衡量准则
CPU利用率：忙碌的时间占比
系统吞吐量：单位时间内完成作业的数量
周转时间：作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 周转时间 / 作业实际运行时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间：对于进程，进程建立后等待被服务的时间之和；对于作业，除了建立进程后的等待时间，还要加上作业在外存后备队列中的等待时间。等待时间 = 周转时间 - 运行时间 - I/O操作时间（如果有的话）
响应时间：用户提交请求到首次产生响应所用的时间。
周转时间 = 等待时间 + 执行时间 = 结束时间 - 进入就绪队列时间。
调度算法
**先来先服务 FCFS、最短作业优先 SJF、最短剩余时间 SRTF、轮转法 RR、优先级算法、**多级反馈队列调度算法
导致饥饿：优先级调度和SJF
7.进程同步与互斥
Peterson 使用令牌，i ，j 会有问题和bug
硬件：
while的那种会有自旋锁，忙等待。
非忙等待：block，把自己送入该信号量的等待队列中。
管程：一种数据结构，结构内的多个子程序形成的多个工作线程互斥的访问共享资源，可以理解为一个类的定义，但是不同的是，管程有条件变量可以用于控制进程之间的同步。
互斥
太简单了。用PV挨个加
同步
生产者消费者问题
关系：① 缓冲区大小，生产者每生产一个之前都要申请一个空间。 ② 商品，消费者需要拿一个商品 ③ mutex
如果只有2个的话，可以没有mutex其实。
吸烟者问题
三种材料两两一组看做三种，生产者轮流提供，三个吸烟者轮流获取，获取完都要V(finish)一下。
读者写者问题
key：如何实现读写 写写的互斥而读读不互斥，方法是加count在第一个读和最后一个读进行pv操作。
这个会导致饥饿，于是解决方法是，再加一对PV，实现写优先：在阻塞写者之前，加一个P，如果同时有写和读，那么这个时候虽然写者在P真正的操作，但是上面的P已经不允许新的读者了。（如果有已经在阻塞中的写者，则阻塞住新的读者，操作是在写着阻塞那句话之前p一个变量，写者需要p这个变量才能整新的。）
哲学家进餐问题
解决死锁的方法：① 最多允许4个人同时进餐 ② 奇数先拿左边，偶数先拿右边 ③ 第五个哲学家先右边，其他人先左边 ④ 只有当左右都可以拿的时候才拿 ⑤ 管程。
④ 不太好，这样所有人拿筷子变成了互斥。
睡眠理发师问题 (¦3[▓▓]
用PV保护变量的修改 那些 count
8.死锁
一组处于等待（阻塞）状态的进程，每一个进程持有其他进程所需要的资源，而又等待使用其他进程所拥有的的资源，导致这组进程互相等待，均无法向前推进。
**四个条件：**互斥、占有并等待、非抢占、循环等待
预防，破坏四个条件：互斥：SPOOLing；占有并等待：拥有不等待、等待不拥有；非抢占：抢占；循环等待：对资源排序，按照顺序申请。
死锁避免：银行家算法
① request <= need && request <= available
② 假分配 寻找安全序列
死锁检测：思路跟银行家算法一样，不过可以从表中，也可以从图中。
死锁恢复：进程终止、资源将抢占。
9.内存
连续分配之动态分区分配
首次适应、最佳适应、最差适应、临近适应（Next-fit）
分页
页：逻辑内存，帧：物理内存。页框和页帧是对于内存的，页和页面时对于进程的。
**页表：**一个进程对应一张页表
起始地址 = M号内存地址*页框大小
一些理解：页内偏移量是为了物理地址。
然后算多少个页表项，所以需要页面大小/每一块的大小。
分段存储
注意这里的段表加了一个段长。
10.虚拟内存
仅把作业的一部分装入内存，具有请求调入和置换功能，能在逻辑上对内存空间加以扩充。
给页表加了几个字段：状态位、访问字段、修改字段、外存地址。
缺页中断属于内中断中的“故障”。
置换算法
最佳置换算法（OPT）
淘汰在之后的访问中最长时间不再访问的面。
。。。只是理想化的算法，在实际应用中是无法实现的。
先进先出置换算法（FIFO）
Belady异常——当为进程分配的物理块增大时，缺页次数不减反增的异常现象。
实现简单，但是算法性能差。
最近最久未使用置换算法（LRU）
性能好，但是实现困难，需要硬件支持，开销大
时钟置换算法（CLOCK）
循环队列，找第一个访问位为0的，扫描过的1->0
改进版：优先淘汰没有被修改过的页面，增加修改位。
00 01 10 11
系统抖动
进程没有足够的帧，频繁的进行页调度。
解决方法：① 采用局部替换和局部置换算法（？ ② 工作集，定义一个窗口尺寸，看看在这个尺寸里有多少不同的帧
11.对于有数据的部分的文件系统管理
分块。
连续分配，外碎片。
链接分配，可以扩展，指针占用空间，可靠性差。
加入FAT的链接分配，可以随机访问了。
索引分配：随机访问、可拓展、没有外碎片。
12.空闲地址管理
位向量
链表
成组链接法：超级块 链头
13.磁盘调度
先来先服务FCFS
最短寻找时间 SSTF，选择离当前刺头最近的，可能会饥饿
扫描算法SCAN： 不会饥饿，到了头才回头，不平均
LOOK：改进SCAN，不用到头
循环扫描算法C-SCAN：单向运动，快速回去。
C-LOOK：不到头。
14.I/O
阻塞I/O：当应用程序发出一个阻塞系统调用时，应用程序挂起，应用程序从运行队列转入等待队列。等系统调用完成之后再回到就绪队列，在合适的时候继续运行。
非阻塞式I/O：一个非阻塞调用在程序执行过长时间并不会终止应用程序，他会很快返回，其返回值表示已经传输了多少个字节。适合多个程序协作完成I/O
零碎知识点，王道顺序
基本知识
并发：微观上多个任务交替执行，宏观上多个任务一起完成。
并行：同时进行。
程序状态寄存器PSW记录了当前是核心态还是用户态。
操作系统的结构：
大内核和微内核的区别：大内核要上面的橙色、黄色；微内核只要上面的黄色一层。各有优缺点。
中断
用户态->核心态是通过中断实现的，并且中断是唯一的途径。核心态->用户态是执行一个特权指令，将程序状态字PSW的标志位设置为用户态。
内中断：当前指令，CPU内部；外中断：狭义的中断，CPU外部，与当前指令无关。
系统调用
与资源有关的操作（如存储分配、I/O操作、文件管理）
进程
进程实体：进程控制块 PCB + 程序段 + 数据段
PCB是进程存在的唯一标志。
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。如果有线程，那不是调度的基本单位。
组织PCB（进程）的方式：
链接方式：
索引方式：
这两种差不多。
**进程的特征：**动态性、并发性、独立性、异步性、结构性。动态性是进程最基本的特征，进程是资源分配、接受调度的基本单位。
进程状态及其转换：
进程通信
两个进程对共享空间的访问必须是互斥的
pipe
消息传递，通过“发送消息/接受消息”两个原语
线程
线程是一个基本的CPU执行单元，也是程序执行流的最小单位。进程是除CPU之外的系统资源的分配单元。
用户级线程、内核级线程。
内核级线程才是处理机分配的单位。
多线程模型（用户级线程与内核级线程的映射关系）：多对一、一对一、 多对多。
处理机调度
高级调度/作业调度：从后备队列等待，选择进入内存，运行结束退出内存
中级调度/内存调度：PCB继续留在内存中，进程退出进入外存，等待被调度重新进入内存。
低级调度/进程调度：从就绪队列中（在内存里）选择，将处理机分配给它
进程的挂起与7状态模型
进程在操作系统内核程序临界区中是不能进行进程调度与切换的，但是在普通临界区中是可以的。
调度算法
CPU利用率：忙碌的时间占比
系统吞吐量：单位时间内完成作业的数量
周转时间：作业完成时间 - 作业提交时间
平均周转时间 = 各作业周转时间之和 / 作业数
带权周转时间 = 周转时间 / 作业实际运行时间
平均带权周转时间 = 各作业带权周转时间之和 / 作业数
等待时间：对于进程，进程建立后等待被服务的时间之和；对于作业，除了建立进程后的等待时间，还要加上作业在外存后备队列中的等待时间。等待时间 = 周转时间 - 运行时间 - I/O操作时间（如果有的话）
响应时间：用户提交请求到首次产生响应所用的时间。
先来先服务 FCFS
哪个队列先到后备队列，哪个进程先到就绪队列
短作业优先 SJF
服务时间最短的优先/进程先得到服务
分为非抢占式和抢占式SRTN
可能会导致饥饿现象
非抢占式：
抢占式：
高响应比优先 HRRN
在每次调度时，先计算响应比，选择响应比高的进程或者作业。是非抢占式。
响应比 = （等待时间+要求服务时间）/ 要求服务时间
时间片轮转 RR
是用于进程调度的，因为分配时间片是对于进程来说的。
算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms），如果进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
属于抢占式算法
常用于分时操作系统，更注重“响应时间”，因此这里不计算周转时间
优先排新来的，再排刚结束的。如果没用完则主动放弃处理机。
当时间片足够大，那么就退化成了FCFS算法。
个人理解像是设置一个止损的最大时长，但缺点是进程数量过多的时候效率会有设计上的损耗。
标准答案缺点：进程切换开销大、无法区分紧急任务。
让切换进程的开销不超过1%
优先级调度算法
可以作业调度也可以进程调度，甚至可以I/O调度
非抢占式：
抢占式：需要在就绪队列改变的时候也检查优先级。
对于优先级的选择：
可能会导致饥饿。
多级反馈队列调度算法
被抢占之后还是在原来这个级别的队列中。如果到了最低级的队列，那么运行完一个时间片后如果任务还没结，那么还是放到当前层级的队列中。
没啥缺点好像。
进程互斥
单标志法：违反空闲让进
双标志法：标记各进程想进入临界区的意愿
双标志后检查法：。。。。。。。
Peterson 算法
双方都让了一次之后，后说的那个能能够谦让成功。
硬件方法：中断屏蔽（内核进程才可以）
TestAndSetLock（用硬件实现不允许被中断的lock，检查和上锁写在了一起，不满足让权等待）
Swap指令
信号量
整型信号量存在的问题：不满足让权等待会发生忙等待。
记录型信号量：
block的时候进程从运行态->阻塞态
wakeup：阻塞态->就绪态
实现互斥：semaphore mutex = 1
实现同步：semaphore S = 0; 在先完成的操作后V，后需要的代码前P
实现前驱：
生产者-消费者
找进程 - 找关系 - 几对信号量
多生产者-多消费者
吸烟者问题
读者写者问题
key在于如何实现读写的互斥而保持可以同时多个读者，加count只对第一个读者和最后一个读者进行操作。
实现写优先
思想：如果有已经在阻塞中的写者，则阻塞住新的读者，操作是在写着阻塞那句话之前p一个变量，写者需要p这个变量才能整新的。
哲学家进餐
重点是解决资源问题导致的死锁
这样不太好其实，这样是拿筷子的操作是互斥。
睡眠理发师问题
实验题目
管程
用来实现同步和互斥的
死锁
四个必要条件：
互斥、占有并等待、非抢占、循环等待。
预防死锁
避免死锁
寻找安全序列
在资源分配之前预先判断这次分配是否会导致系统进入不安全状态
银行家算法
定义向量，找安全序列。
死锁的检测和解除
检测：找一个不阻塞也不鼓励的进程，然后假设分给他资源，如果可以的话那么全部释放，继续找下一个，直到简化整个图。
解除死锁：
- 资源剥夺法：挂起死锁进程，抢占资源，把资源分配给其他。但这样可能会导致饥饿。
- 撤销进程法：强制撤销进程。
- 进程回退，回退到足以避免死锁的地步，要求记录历史信息和还原点。
内存的基础知识
按字节编址： 每个存储单元为1字节，即1B，8个二进制位
按字编址：看这个计算机的字长是多少，字长为16位的计算机那么每个存储单元=每个字=16个二进制位
绝对装入，静态重定位，**动态重定位：**在使用的时候重定位寄存器+地址
链接也有三种方式
内存管理
内存保护：上下限寄存器、重定位寄存器和届地址寄存器进行越界检查、
覆盖技术：
交换技术：中级调度
动态分区分配
首次适应：从低地址开始查找空闲分区。
最佳适应算法：按照容量递增，找大小能满足要求的第一个空闲分区，能满足但最小的。会产生很多小碎片。
最坏适应算法：容量递减，跟上一个相反。对于大进程不友好。
邻近适应算法： 从上次查找结束的位置开始查找空闲分区。
基本分页存储管理
把内存分为小分区，然后按照小分区大小拆分真正的大进程。
页框和页帧是对于内存的，页和页面时对于进程的。
地址转换：
如果用二进制表示的话，就更简单了。
**页表：**一个进程对应一张页表
起始地址 = M号内存地址*页框大小
页表︰将页和帧完成映射（逻辑地址到物理地址的映射)。由于页号是从0开始按顺序排列的，所以页表中忽略页号，只留帧号。
地址变换机构
例题：
快了个表：
两级页表
分段存储
段号、段内地址
分段、分页的对比
段页式
虚拟内存
把基本换成请求
特征：
缺页中断属于内中断的故障。
页面置换算法
最佳置换算法（OPT）
淘汰在之后的访问中最长时间不再访问的面。
。。。只是理想化的算法，在实际应用中是无法实现的。
先进先出置换算法（FIFO）
Belady异常——当为进程分配的物理块增大时，缺页次数不减反增的异常现象。
实现简单，但是算法性能差。
最近最久未使用置换算法（LRU）
性能好，但是实现困难，需要硬件支持，开销大
时钟置换算法（CLOCK）
循环队列，找第一个访问位为0的，扫描过的1->0
改进版：优先淘汰没有被修改过的页面，增加修改位。
00 01 10 11
** **
页面分配、置换策略
驻留集：指请求分页存储管理中给进程分配的物理块的集合。
固定分配局部置换，灵活性低
可变分配全局置换，缺页会获得新的物理块
可变分配局部置换：根据缺页率动态增删。
调入页面：预调页、请求调页
工作集：在某段时间间隔里，进程实际访问页面的集合。
文件系统
数据项是文件系统中最基本的数据单位
文件通过目录组织起来
向上提供的基本功能：
有结构文件的逻辑结构
顺序文件、索引文件、索引顺序文件
顺序文件：串结构、顺序结构
索引文件、索引顺序文件
后一种，先分组再建立索引
多级索引顺序文件……
文件目录
单极目录
两层目录结构
树形目录结构，引入相对路径和绝对路径，不好解决多用户共享
无环图目录结构
文件分配方式 物理结构
连续分配：支持顺序访问和直接访问；顺序访问速度快；不适合拓展；磁盘碎片
链接分配（隐式链接）：链表，只顺序，不随机，适合拓展
链接分配（显式链接）：指针放到一个文件分配表中（FAT）
文件分配方式 索引分配
每个文件一个索引表
随机访问√文件拓展√
文件太大：
链接方案：多个索引块
多层索引：K层索引 K+1次读磁盘操作
混合索引：
存储空间管理 空闲
空闲表法
空闲链表法：分为两种
位示图法
成组链接法：
超级块 链头
文件系统层次结构
磁盘调度
先来先服务FCFS
最短寻找时间 SSTF，选择离当前刺头最近的，可能会饥饿
扫描算法SCAN： 不会饥饿，到了头才回头，不平均
LOOK：改进SCAN，不用到头
循环扫描算法S-SCAN：单向运动，快速回去。
C-LOOK：不到头。
I/O
I/O缓冲
单缓冲 MAX（T,C）+ M
更新: 2021-01-10 00:30:31
原文: https://www.yuque.com/qer233/sdu_note/os