操作系统
操作系统
1 特点
- 管理系统的软硬件和数据资源
- 控制程序运行
- 人机之间的接口
- 软件和硬件之间的接口
- 为应用程序的开发和运行提供一个高效率的平台
操作系统最接近硬件，应用软件最接近用户
2 进程和线程
2.1 概念
进程的组成
- 程序块
- 进程控制块（PCB） 进程存在的唯一标志，包含进程的大部分信息
- 数据块
进程内的内存地址空间、代码、数据、文件等可以给多个线程共享
线程的程序计数器、寄存器、栈不共享
2.2 进程状态
进程的状态会持续变化
- 运行：一个进程在CPU上运行
- 就绪：一个进程获得了除了CPU外的一切资源，一旦得到CPU就可以开始执行，有一个就绪队列
- 阻塞：也称等待或者睡眠状态，正在等待某一个时间的发生，此时即使获得CPU也无法运行，事件发生后进入就绪队列
3 进程管理
3.1 同步和互斥
互斥：多个人抢打印机用
同步：你跑的快 在目的地等你朋友
3.2 PV操作
信号量是一种特殊的 全局变量，可以理解为资源数，当信号量为负数的时候代表排队进程数
取值范围：[ 信号量-进程数 ,总信号量]
如：2个信号量，3个进程,其取值范围为 [ -1, 2 ] -1代表有一个进程在排队
P操作：申请/锁定资源，信号量-1，如果P操作结束信号量小于0则进入阻塞队列
V操作：释放/解锁资源，信号量+1，如果V操作结束后信号量<=0则唤醒阻塞队列的第一个进程，进入就绪队列
3.3 前趋图
- 节点表示进程，箭头表示前趋后继关系
- 1个箭头就代表一个前趋关系
- 没有前趋进程的节点是起始进程，没有后继进程的节点是终结进程
- A有箭头指向D，则记录为（A，D）
- 有几个箭头就代表要几个信号量
- 有前驱操作就有P，有后继操作就有V
题目可能不会给出具体信号量是哪个，需要根据选项推测
例题
P1执行后，需要有个后继箭头，所以是2个V操作，即V(S1)V(S2)
P2操作执行前，两个前趋箭头，需要两个P，即P(S1)P(S3)，一个后继箭头，V(S4)
4 死锁和银行家算法
4.1 死锁
死锁四大条件
- 互斥
- 保持和等待
- 环路等待
- 不剥夺
问：ABC三个进程都需要5个系统资源，
- 几个资源一定死锁：不足以支持任何一个进程即 4个
- 几个资源不可能发生死锁： 3 *（5-1）+1 = 13
4.2 银行家算法
分配资源的原则（概念不用记）
- 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程；
- 进程可以分期请求资源，但请求的总数不能超过最大需求量；
- 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。
例题
25 -6-4-7-6 =2 目前剩下2个资源
P1获得资源后也达不到需求资源数
P3获得资源后，达到需求资源数，P3执行完成后释放资源，所以系统是安全的
5 存储管理
虚拟存储体系 = 外存 + 内存
淘汰规则：
状态位 = 1 代表还在内存中
访问位 = 0 代表最近没有访问过，如果有多个可选，则优先淘汰修改位=0
5.1 页式存储
将程序和内存划分为大小相同的块，以页为单位将程序调入内存
优点：利用率高，碎片小，分配管理简单
缺点：增加了系统开销，有抖动现象
逻辑地址 = 页号 + 页内地址
物理地址 = 页帧号 + 页内地址
假设每个页的大小为4KB
4KB 等于2的12次方，所以需要12位2进制来表示页内地址，然后根据页表即可得出物理地址和逻辑地址（题目可能给10进制，也可能是16进制，要转为2进制）
假设 页表给出 页号2 对应块号6
则其
逻辑地址 = 10 + 页内地址12位二进制
物理地址 = 110 + 页内地址12位二进制
4k = 2的12次方，所以页内地址有12位，则前四位代表页面
0010转十进制为2，则页帧号 = 110
5.2 段式存储
按照用户作业中的自然段划分逻辑空间， 然后调入内存，段的长度可以不一样，通常大于页。
地址表示方法：（段号，段内偏移量）
优点：多道程序共享内存，各段程序修改互不影响
缺点：内存利用率低
5.3 段页式存储
段式和页式的结合，先分段再分页面。
一个程序有多个段，每个段里有多个页，页大小相同，但是段大小不相同
优点：空间浪费小，存储共享容易，存储保护容易，能动态链接
缺点：执行速度下降，复杂性和开销增加
逻辑地址 = 段号 + 页号 + 页内地址
6 磁盘管理
6.1 概念
- 盘面：硬盘由多个圆盘组成，每个盘面都有上下两个记录面
- 磁头：读写数据的组件，悬停在盘面上
- 磁道：磁头悬停的地方，由盘面旋转产生的同心圆
- 扇区：磁道被划分为若弧段(扇形)，每个弧段称为一个扇区
6.2 存取时间
磁头必须在某个扇区的起始处才能读取数据，且硬盘旋转无法停止。
寻道时间: 磁头移动到磁道需要的时间
等待时间（旋转延迟）：等待读写的扇区旋转到磁头下方需要的时间
数据存取时间 = 寻道时间 + 等待时间 + 数据传输时间
例题1：
某磁盘磁头从⼀个磁道移⾄另⼀个磁道需要10ms。⽂件在磁盘上⾮连续存放， 逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间 分别为100ms和2ms，则读取⼀个100块的⽂件需要多少时间
文件非连续存放，所以读完一个块之后需要重新寻道
寻道时间 = 10*10ms 等待时间=100ms 数据传输时间 = 2ms
所以 （10 * 10 + 100 + 2）*100
例题2:
假设某个磁盘每个磁道被划分为11个物理块,每块存放一个逻辑记录。逻辑记录R0，R1…R10存放在同一个磁道上，记录的存放顺序如下
| 物理块 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 逻辑记录 | R₀ | R₁ | R₂ | R₃ | R₄ | R₅ | R₆ | R₇ | R₈ | R₉ | R₁₀ |
磁盘的旋转周期 = 33ms，磁头当前在R0起始处。若系统使用单缓存区处理这些记录，每个记录的处理时间为3ms，则处理这11个记录的最长时间为多少？若进行优化分布后，处理11个记录的最少时间为多少？
已知磁盘旋转周期 = 33ms，共有11个块，则每个磁头在每个块上的停留时间（读取时间）=3ms ，由于在同一个磁道里，所以寻道时间=0
读取完数据R0后，磁头在R1起始处，此时需要对R0数据进行处理（3ms），处理完成后，磁头位于R2开始处，需要等待磁盘旋转到R1起始处进行处理。
R0 = 0ms（旋转延迟） + 3ms(读取时间) + 3ms(处理时间)
R1~R10 = 3ms*10（磁头从R2移动到R1，移动10个扇区）+ 3ms(读取时间) + 3ms(处理时间)
最长时间 = 3+3 + 10 （310 + 3 + 3） = 366ms
优化分布后，即R0读取完之后可以直接读取到R1，无需等待旋转
最短时间 = 11 *（3+3） = 66ms
6.3 移臂算法
- 先来先服务：按照请求序列寻道
- 最短寻道时间优先：离磁头最近（根据磁道号/柱面号判断）的优先，相同的情况下按扇区从小到大
- 扫描算法：电梯算法，不会改变磁头方向
- 循环扫描算法
离20最近的是21，离21最最近的是22，离22最近的是18，离18最近的是16。相同柱面号的情况下扇区小的优先
7 文件系统
7.1 索引文件结构
如果没有指出，默认一个索引文件里有13个节点0～12
其中
0～9: 直接索引，直接指向物理盘块
10: 1级间接索引，指向一个索引表，通过索引再指向物理盘块
11: 2级间接索引，指向一个索引表，该索引表每个索引指向一个1级索引表
12: 3级间接索引，指向2级索引
假设一个地址项大小为4字节，一个数据块大小为1KB，间接索引表里可以存放1024/4 = 256个地址。最大范围 = 起始地址 + 个数 - 1
- 直接索引的逻辑地址范围：[0，9]
- 一级索引地址范围:[10，265 ]
- 二级索引地址范围：[266，266+256平方-1]
计算题需要注意边界值的判断!
直接索引范围：[0,5]
一级索引范围：[6,261]
二级索引范围：[262, 65535+262-1 ]
7.2 位示图BitMap
本质上是一个存放二进制数的表格，1表示占用。按照字长（题目会给）分组，每个比特位代表一个磁盘块的占用情况
磁盘容量/块大小 = 块数量 块数量/字长 = 字数
300*1024/32 = 9600
1023号物理块 = 第1024块
1024/32 = 32 余数0，所以放在31号字的下表为31的比特位 ，置为1