导图社区 计算机——操作系统
- 201
- 10
- 2
- 举报
计算机——操作系统
计算机操作系统框架及部分细节，考研408适用。主要内容有进程管理、内存管理、设备管理、文件管理、操作系统、基本概念。
编辑于2021-11-08 13:51:59
- 相似推荐
- 大纲
操作系统
进程管理
进程基本概念
进程与程序的区别
1. 程序是代码的集合，静态的。 2. 进程是程序的一次执行，动态的。
进程的特性
1. 动态性（最基本特征）。 2. 并发性。 3. 独立性。 4. 结构性。 5. 异步性。
进程结构
1. PCB。 2. 代码段。 3. 数据段。
进程的五状态
一. 五种状态 1. 创建态：创建PCB，初始化PCB，分配资源，插入就绪队列队尾。 2. 就绪态：获得了除CPU以外的所有资源。 3. 运行态：进程在CPU上运行。 4. 阻塞态：因缺少某一进程而处于等待状态。 5. 终止态：撤销PCB，回收资源。 二. 状态转换 1. 就绪态->运行态：调度 2. 运行态->就绪态：被高优先级进程抢占或时间片完。 3. 运行态->阻塞态：等待某一事件的发生。 4. 阻塞态->就绪态：等待的某一事件发生。 p
进程通信
低级通信：PV操作 高级通信：共享存储，消息传递，管道通信。 共享存储：基于数据结构，基于存储区。 消息传递：直接传递，间接传递（信箱模式）。 管道通信：半双工，互斥访问。
线程基本概念
什么是线程？
轻量级进程。
线程的特性与优点
1.引入线程后，进程依旧是资源分配的基本单位，而线程是调度的基本单位。 2.线程间的切换，代价小，提高了并发度。 进程间的切换，代价高，降低了并发度。
线程的实现
用户级线程
1. 线程间管理由应用程序完成，因此线程间的切换代价低，速度快。 2. 然而操作系统无法意识到这种情况下线程的存在，因此当一个线程阻塞的时候，整个进程内的线程都阻塞。降低并发度。
内核级线程
1. 线程间管理由操作系统完成，因此线程间的切换代较高，速度较慢。 2. 操作系统意识到这种情况下线程的存在，因此当一个线程阻塞的时候，并不影响其他整个进程内的线程。提高了并发度。
处理机调度
三级调度
高级调度（作业调度）
频率最低，从磁盘后备队列选择一个作业，创建进程，放入就绪队列队尾。
中级调度（内存调度）
频率在三者之间。将处于就绪态或阻塞态的进程从内存中移出到外存，但 PCB 常驻内存。
进程七状态图
p
低级调度（进程调度）
频率最高，就绪态->运行态，CPU的分配。
性能评价指标
调度算法
FCFS（先来先服务）
SJF（短作业优先）
高响应比优先调度
时间片轮转
优先级调度
多级反馈队列调度
进程同步与互斥
同步与互斥概念
同步
又称直接制约关系：为完成某种任务而建立两个或多个进程，需要在某些位置上协调工作次序而产生制约关系。
互斥
又称间接制约关系：进程互斥指当一个进程访问某临界资源 时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后， 另一个进程才能去访问临界资源。
临界资源的互斥访问
进入区
检查是否可以进入临界区，若可以进入，则应该设置正在访问临界资源的标志。
临界区
访问临界资源的代码。
退出区
解除正在访问临界资源的标志。
剩余区
做后处理。
进程互斥四大原则
空闲让进
忙则等待
有限等待
让权等待
互斥实现方法
软件实现
操作不具备原子性。
单标志法
进程间交替进入临界区，当一个进程不想进入临界区，则另一个进程也进步了临界区。
双标志先检查法
存在两个进程同时进入临界区，违背忙则等待。
双标志后检查法
存在两个进程都进不入临界区，违背空闲让进。
Peterson
硬件实现
中断屏蔽方法
利用关中断与开中断命令。这限制了处理机交替执行程序能力。
TestAndSet指令
Swap指令
信号量机制
为什么引入信号量？
软件/硬件实现方法均无法解决让权等待原则。
记录型信号量
理解记录型信号量不同区间取值的意义： 1. 信号量>0 2. 信号量<=0
P,V操作
1. P 操作，先 S.value--，之后执行 block 原语。 2. V 操作，先 S.value++，之后执行 wakeup 原语。
经典例题
生产者-消费者问题
多生产者-消费者问题
吸烟者问题
读者-写者问题
哲学家进餐问题
死锁
基本概念
什么是死锁？
多个进程因争夺资源，导致进程都无法向前推进。
产生原因
系统资源的争夺，进程推进顺序非法。
产生的必要条件
互斥条件
不剥夺条件
保持并请求
循环等待
死锁解决办法
死锁预防
破坏互斥条件（不现实）
破坏不剥夺条件
些不可剥夺资源的进程请求新的进程得不到满足的时候，不许释放已经保持的所有资源，待以后重新申请。
破坏保持并请求
运行前一次申请完所需的全部资源。
破坏循环等待
资源编号，按编号递增顺序请求资源。
死锁避免
安全状态与死锁
安全状态一定不会发生死锁，不安全状态可能发生死锁。（可能期间存在有进程返还系统资源）
银行家算法
死锁检测
数据结构：资源分配图
死锁检测：死锁定理
死锁解除
资源剥夺法
挂起某些死锁进程，并抢夺资源。
进程撤销法
撤销多个或全部死锁进程。
进程回退法
让一个或多个进程回退到足以回避死锁的阶段。
内存管理
实现功能
内存的分配与回收
地址转换
内存保护
内存空间扩充
程序编译基本概念
编译
将源代码文件编译成若干目标模块。
链接
通过链接程序将目标模块与其所需的库函数链接，形成完整的装入模块。
静态链接
装入时链接
运行时链接
装入
由装入程序将装入模块装入内存。本质是将逻辑地址转换为物理地址。
绝对装入
编译，链接时需要给出绝对地址。
静态重定位
一次性将装入的所有模块重定位。
动态重定位
在重定位寄存器的支持下，按运行时的进行重定位。
内存保护
可以通过设置重定位寄存器（基址寄存器），和界地址寄存器实现。
内存扩充方法
覆盖技术
前者将用户空间划分为一个固定区和若干覆盖区，需要写程序时提前声明。
交换技术
程序在内存和辅存间对换。
虚拟内存技术
连续分配方式
单一连续分配
内存分为用户区和系统区。无外部碎片，有内部碎片。
固定分区分配
无外部碎片，有内部碎片。
分区大小相等
分区大小不等
动态分区分配
有外部碎片，无内部碎片。
数据结构
空闲分区表
空闲分区链
分配算法
首次适应
空闲分区按地址递增顺序，找到第一个满足的空闲分区。性能最优。
最佳适应
空闲分区按容量递增顺序，找到第一个满足的空闲分区。
最坏适应
空闲分区按容量递减顺序，找到第一个满足的空闲分区。
邻近适应
首次适应加上每次从上次结束位置处开始。
回收算法
非连续分配
基本分页式
基本概念
内存空间划分为大小相等的分区 页（页面）：进程中的块。 页框：内存中的块。 页与页框一一对应。 页表寄存器：存放页表地址信息（页表始址，页表长度）。 页表：记录了由页号->内存块号的映射。
地址结构
地址结构 = （页号，页内偏移量）
页表结构
页号（不实际存储），物理块号。
地址变换
1. 计算页号，页内偏移（十进制通过除取整，求余，二进制根据位数判断）。 2. 页号与页表寄存器内的页表长度比较， 超过则越界中断。 3. 页表项长度 = 页表始址 + 页号 * 页表项长度。 4. 找到页表项，得到物理块号。 5. 物理地址 = 页面大小 * 物理块号 + 页内偏移 p
基本分段式
基本概念
以程序的逻辑关系分为若干段，段间非连续存放。段内连续存放。
地址结构
地址结构 = （段号，段内偏移）
段表结构
段号，段始址，段长度。
地址变换
1. 计算段号，段内偏移。 2. 段号与段表寄存器的段表长度比较，超过则发生越界中断。 3. 段表项地址 = 段表始址 + 段号 * 段表项大小。 4. 根据段表得到段始址和段长度。 5. 段内偏移与段长度比较，超过则发生越界中断。 6. 物理地址 = 段表始址 + 段内偏移。 p
基本段页式
基本概念
结合二者的优点。
地址结构
地址结构 = （段号，页号，页内偏移）
段/页表结构
段表：段号，页表长度，页表始址。 页表：物理块号。
地址变换
1. 计算段号，页号，页内偏移。 2. 段号与段表寄存器的段表长度比较，超过则越界中断。 3. 段表项地址 = 段表始址 + 段号 * 段表项长度。 4. 访问段表得到页表长度，页表始址。 5. 页号与页表长度比较，超过则越界中断。 6. 页表项地址 = 页表始址 + 页号 * 页面大小。 7. 查询页表得到物理块号。 8. 物理地址 = 物理块号 * 页面大小 + 页内偏移。 p
分页式与分段式的比较
信息的单位
分页的基本单位是页，是物理单位。 分段的基本单位是段，是逻辑单位。
大小
页表的大小是固定的，段是不固定的。
可见性
段是由编程时决定，可见。 页时由操作系统决定，不可见。
地址空间
段的地址空间是二维，页的地址空间是一维。
信息共享与保护
段有利于信息共享与保护。页不方便。
快表机制
什么是快表？
在存储器层次结构中，属于高速缓存，访问最近访问的页表项副本。
局部性原理
时间局部性
空间局部性
地址变换
1. 计算页号，页内偏移（十进制通过除取整，求余，二进制根据位数判断）。 2. 页号与页表寄存器内的页表长度比较， 超过则越界中断。 查快表，若命中则直接指导了物理块号。若未命中，则无事发生。 3. 页表项长度 = 页表始址 + 页号 * 页表项长度。 4. 找到页表项，得到物理块号。 5. 物理地址 = 页面大小 * 物理块号 + 页内偏移。 p
平均访问时间
快表和慢表同时访问（内存中的页表）
先访问快表，未命中再访问慢表
两/多级页表机制
为什么引入两/多级页表？
如果页表过大（即页表项过多，且页表项连续存放），会占据较大的连续存储空间。因此引入层次概念。
地址结构
以两级页表为例：地址结构 = （一级页号，二级页号，页内偏移量） p
注意事项
1. 页表内加入了一个“是否在内存中”的状态位。 2. 顶级目录只有一个。 3. n 级页表的访问内存次数为 n+1 次。
虚拟存储
虚拟内存特性
多次性
作业允许分成多次调入内存。
对换性
作业无需常驻内存，可以换入换处。
虚拟性
逻辑上扩充内存容量。
请求分页系统
在基本分页管理的基础上，加入了请求调页功能，页面置换。
页表
页表 = （页号，物理块号，状态位，访问字段，修改位，外存地址） 状态位：是否处于内存中。 修改位：是否被修改。（决定是否在调出时，写回内存否？）。 访问字段：算法位。
缺页中断
缺页中断属于内部中断，且一条指令的执行期间可能存在多次缺页中断。
地址变换
1. 比较页号与页表长度，超过则越界中断。 2. 检查快表中是否有该项，没有则访问页表。 3. 如果页表在内存中，则修改访问位和修改位，形成物理地址。 4. 如果页面不再内存，则进行缺页中断。 缺页中断 1. 保护 CPU 现场。 2. 从外存中找到缺页。 3. 若内存中有空闲块则直接放入，若没有则通过页面置换算法选择一个页面调出。 4. 被调出的页面检查修改位，若被修改需要写回到外存。 5. 换入内存后修改页表，回到程序中断处。
请求分段系统
页面置换算法
最佳置换算法（OPT）
先进先出
存在 Belady 异常：增加物理块，命中率降低。
LRU
淘汰最近最长时间未使用的页面。
CLOCK 算法
页面分配策略
驻留集
请求分页存储管理中给进程分配的物理块集合。
固定分配局部置换
系统为每个进程分配一定数量的物理块，整个运行期间不变。
可变分配全局置换
先为系统中每个进程分配一定数目物理块，操作系统本身维持一个空闲物理块队列。哪个进程发生缺页，就分配一块。无空闲块时，选择未锁定页面换出。
可变分配局部置换
先为系统中每个进程分配一定数目物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存，若频繁缺页，系统会为该进程多分配物理块。反之会减少分配物理块。
工作集
某段时间间隔内，进程实际访问页面的集合。 注意：驻留集大小不能小于工作集大小。
调入策略
预调页策略（运行前调入）
请求调页策略（运行时调入）
抖动
刚换入的页面马上又被换出，刚换出的页面马上又被换入。
设备管理
I/O控制方式
程序查询方式
CPU 循环测试I/O 状态。
中断驱动方式
I/O 每完成一个字的数据放到指定寄存器后，I/O 设备通过中断方式请求服务。
DMA 方式
基本单位数据块，DMA 与 内存直接交换数据，仅在预处理与后处理需要 CPU 干预。
通道方式
通道是专用 I/O 处理机，一组数据块，通道比 DMA 可以独立决定数据始址和长度。
I/O 子系统
用户I/O软件
设备独立性软件
设备驱动程序
中断处理程序
硬件
I/O核心子系统
I/O调度
高速缓存缓冲区
单缓冲区
max(T1, T3) + T2
双缓冲区
max(T1 + T2, T3)
循环缓冲
循环队列。
缓冲池
三个队列：空缓冲队列，输入队列和输出队列。 四个缓冲区：收容输入数据缓冲区，收容输出数据缓冲区，提取输入数据缓冲区，提取输出数据缓冲区。
设备分配与回收
数据结构
设备控制表（DCT） 系统设备表（SDT） I/O 控制器设备表（COCT） I/O 通道控制表（CHCT）
设备分配流程
SDT -> DCT -> COCT -> CHCT。
设备分配方式
静态分配
运行前一次分配所有。
动态分配
运行时按需分配。
逻辑设备表（LUT）
逻辑设备与物理设备间的映射关系。
SPOOLing 技术
基本组成
输入井，输出井，输入缓冲区，输出缓冲区，输入进程，输出进程。
共享打印机工作流程
输出进程在输出井申请空白磁盘区，将打印数据放进去。 输出进程申请一张空白 PCB，初始化信息后放在打印队列队尾。 打印机从输出井中提取数据。
文件管理
文件基本概念
文件的结构
自底向上 记录项：不可分割，最低级的数据组织方式。 记录：一组相关数据项的集合。 文件：一组相关信息的集合。
文件基本操作
创建文件
打开文件
写文件
读文件
文件重定位（文件寻址）
删除文件
关闭文件
文件属性
文件的逻辑结构
无结构文件（流式文件）
有结构文件（记录文件）
顺序文件
链式存储
无法实现随机存取。
顺序存储
可变长记录
无法实现随机存取。
定长记录
可实现随机存取。
串结构（不按关键字顺序存储）
顺序结构（按关键字顺序存储）
索引结构
由于索引表本身就是顺序表，所以即使逻辑文件是可变长的，仍然可以实现随机存取。 p
索引顺序结构
为了能有效降低索引表的大小，引入索引顺序结构。索引结构是一个索引项对应一个记录，而索引顺序结构一个索引项对应一组记录。 p
多级索引顺序结构
进一步地提高了提高了检索的效率。 p
目录结构
FCB
文件控制块（FCB）包含了文件基本信息，多个FCB 构成目录。
索引结点
将整个 FCB 放入目录会降低检索效率，因此将 FCB 中除文件名之外的文件描述信息放入索引结点中。目录中只包括文件名，一个指向索引结点的指针。 p
单级目录结构
p
两级目录结构
p
主文件目录
用户文件目录
多级目录结构（树型目录结构）
p
绝对路径
相对路径
无环图目录结构
方便共享，每个共享结点设置一个共享计数器。 p
文件分配方式
连续分配
1. 支持随机访问。 2. 存取速度最快。 3. 扩展较难。 p 可以通过紧凑技术来解决碎片问题。
链式分配
隐式链接
除了文件最后一个盘块，每个盘块中都存有指向下一个盘块的指针。
显式链接
链接各物理块的指针显式存放在 FAT 表中。 p
索引分配
单独弄出一些盘块存放索引表信息。 p 存放数据的盘块称：数据块。 存放索引表的盘块称：索引块。
链接方案
p
多层索引
p
混合索引
p
文件存储空间管理
空闲表法
空闲盘块表 = （序号，第一个空闲盘块号，空闲盘块数）
空闲链表法
空闲盘块链
所有空闲盘块以盘块为单位组成一条链。
空闲盘区链
所有空闲盘块以盘区为单位组成一条链。
位示图法
成组链接法
文件共享
硬链接
软链接
文件保护
口令保护
加密保护
访问控制
磁盘管理
磁盘结构
磁盘
磁道
扇区
磁盘地址结构
（柱面号，盘面号，扇区号） 磁头指到指定的柱面。 选择特定的盘面激活磁头。 磁盘旋转划过指定扇区。 这么设计：因为盘面号不同不需要移动磁头臂。
磁盘调度
磁盘访问时间
寻道时间
寻道时间 = 启动磁臂时间 + 移动一个磁道的单位时间 * 移动磁道数
旋转时延
磁头定位到指定扇区的平均时间（转半圈） = 1 / (2 * 磁盘转速)
数据传输时延
划过指定扇区。
磁盘调度算法
改善寻道时间。
先来先服务（FCFS）
最短寻找时间（SSTF）
优先处理与当前磁头最近的磁道。
扫描算法（SCAN）
移动到最外侧磁道时才能往内移动，移动到最内侧磁道时才能往外移动。
LOOK 算法
在 SCAN 基础上，若磁头移动方向上无别的请求，可以立即改变磁头移动方向。
C-SCAN 算法
只有沿特定方向移动才处理磁道访问请求，返回时直接快速移动至起始端不处理任何请求。
C-LOOK 算法
相比于 C-SCAN，若移动方向上无请求，则直接快速返回起始端。
其他减少时延方法
交替编号
针对单个盘面。
错位命名
针对多个盘面。
磁盘初始化
物理格式化
将磁道划分为扇区，初始化管理扇区的控制信息。
磁盘分区
逻辑格式化
创建文件系统。
磁盘引导区
坏块管理
解决方法：提供备用扇区
FAT 标明
维护坏块链表
操作系统基本概念
功能
控制和管理计算机系统硬件与软件资源，为用户和其他软件提供方便接口与环境的程序集合，计算机系统中最基本的系统软件。
特征
并发
并发：两个或多个事件在同一时间段内发生。 并行：两个或多个事件在同一时刻发生。
共享
虚拟
异步
接口
命令接口
交互式命令接口
批处理命令接口
程序接口
系统调用（广义指令）
图形接口（GUI）
发展
多道批处理系统：提高系统利用率，但缺乏人机交互。 分时操作系统：提供人机交互，但时间片切换存在系统开销。 实时操作系统：追求及时性与可靠性。
批处理
单道批处理
多道批处理
分时系统
实时系统
网络操作系统
分布式计算机系统
运转机制
用户态 & 内核态
特权指令 & 非特权指令
用户态与内核态间的切换
用户态->内核态
中断。 一方面是主动的中断：系统调用。 一方面是被动的中断：系统强行转为内核态。
内核态->用户态
操作系统主动的过程。
中断
内中断（异常）
陷入
程序自愿的行为。
故障
终止
外中断（中断）
体系架构
大内核
时钟管理，中断管理，原语。
微内核
微内核 + 进程管理，内存管理，设备管理。
大内核与微内核差异比较
大内核：一次申请系统服务所需要的状态转换次数较少，性能较优。 微内核：一次申请系统服务所需要的转台转换次数较多，性能较差。 但微内核管理较大内核要好点。
浮动主题