操作系统
2021-03-02 14:54:27 0 举报AI智能生成
参照《操作系统高分笔记》编写，主要为逻辑框架，建立整体观。
作者其他创作
大纲/内容
概论
特征
并发
共享
虚拟
异步
目标和功能
计算机系统资源的管理者
用户与计算机系统之间的接口
命令接口
程序接口
GUI
扩充机器
发展
批处理操作系统 -->分时操作系统 --> 实时操作系统 --> 网络和分布式操作系统
运行机制
中断和异常
系统调用
体系结构
大内核
微内核
进程管理
大纲
进程
概念
与程序的区别
特征
动态性、并发性、独立性、异步性、结构性
状态
运行、就绪、阻塞、创建、结束
控制
创建、终止、阻塞和唤醒、切换
组织
进程控制块PCB、程序段、数据段
通信
共享存储、消息传递、管道通信
线程
概念、与进程的比较、属性
线程额实现方式
处理机调度
概念、三级调度：作业调度、中级调度、进程调度
调度方式：剥夺式、非剥夺式
调度准则：CPU利用率、吞吐量、周转时间、等待时间、响应时间
算法：先来先服务、短作业优先、优先级、高响应比优先、时间片轮转、多级反馈队列
进程同步
概念：临界资源、同步、互斥
实现方法：软件实现的几种算法、硬件实现
信号量：整型、记录型
经典问题：生产者-消费者问题、读者与写者问题、哲学家进餐问题、吸烟者问题
死锁
定义
原因
系统资源竞争、进程推进顺序非法
条件
互斥、不剥夺、请求和保持、循环等待
策略
预防死锁、避免死锁、死锁的检测与解除
细节
进程
目的：更好地描述和控制程序的并发执行
定义：进程是进程实体的一次执行，是系统进行资源分配和调度的一个独立的单位
组成
PCB：保存进程运行期间的相关数据，是进程存在的唯一标志
程序段：能被进程调度程序调度到CPU运行的程序的代码段
数据段：存储程序运行期间的相关数据，可以是原始数据也可以是相关结果
进程的状态
状态的种类
运行状态：进程在处理机上运行
就绪状态：进程已获得了除处理机之外的一切所需资源
阻塞状态：进程正在等待某一事件而暂停运行
创建状态：进程正在被创建，尚未转到就绪状态
结束状态：进程正从系统中消失，分为正常结束和异常退出
转态的变化
就绪 --> 运行 ：经过处理机调度，就绪进程得到处理机资源
运行 --> 就绪 ：时间片用完或在可剥夺系统中有更高优先级进程进入
运行 --> 阻塞 ：进程需要的某一资源还没准备好
阻塞 --> 就绪 ：进程需要的资源已准备好
进程控制
创建：终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等
终止：正常结束、发生异常、外界干预
阻塞：等待资源
唤醒：资源到达
切换：时间片用完、主动放弃处理机、被更高优先级的进程剥夺处理机
进程的通信
共享存储
低级方式：基于数据结构的共享
高级方式：基于存储区的共享
消息传递
直接通信方式：直接把消息挂到接收进程的消息队列
间接通信方式：挂到某个中间实体，接收进程找实体接收消息 类似电子邮件
管道通信
利用一种特殊的pipe文件链接俩个进程
代价
时间代价：进行进程间的切换、同步及通信等所付出的时间开销
空间代价：进程控制块以及协调各运行机构所占用的内存空间开销
线程
引入目的：为了更好地使多道程序并发执行，以提高资源利用率和系统吞吐量，增加程序的并发性
特点：是程序执行的最小单元，基本不拥有任何资源
实现方式：用户级线程、系统级线程
调度
调度层次
作业调度（高级调度）：选择处于后备状态的作业分配资源，发生频率最低
内存调度（中级调度）：选择暂时不能运行的进程调出内存，发生频率中等
进程调度（低级调度）：选择就绪队列中合适的进程分配处理机，发生频率最高
进程调度的原因：合理的处理计算机软件硬件资源
进程调度方式
剥夺式：有更为重要的或紧迫的进程需要使用处理机，立即分配
非剥夺式：有更为重要的或紧迫的进程需要使用处理机，仍让当前进程继续执行
典型的调度算法
先来先服务：选择最先进入队列的
短作业优先：选择完成时间最短的
优先级调度：选择优先级最高的
高响应比优先：选择相应比最高的
时间片轮转：总是选择就绪队列中第一个进程，但仅能运行一个时间片
多级反馈队列：时间片轮转调度算法和优先级算法的综合和发展
进程同步
引入原因：协调进程之间的相互制约关系
制约关系
同步：需要在某些位置上协调进程之间的工作次序而等待、传递信息所产生的制约关系
互斥：当一个进程进入临界资源区使用临界资源时，其他要求“进入临界区”或“进区”必须等待
临界资源：一次仅允许一个进程使用的资源
临界区互斥
原则：空闲让进、忙则等待、有限等待、让权等待
基本方法
软件实现
单标志法：违背“空闲让进”的原则
双标志法先检查：违背“忙则等待”原则
双标志后检查：会导致“饥饿”现象
皮特森算法：单标志和双标志后检查的结合
硬件实现
中断屏蔽法：进区关中断、出区开中断
硬件指令法：设立原子操作指令
信号量：利用PV操作实现互斥
管程
定义：有一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块
组成
局部于管程的共享结构数据说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句
死锁
产生原因：非剥夺资源的竞争和进程的不恰当推进顺序
定义：多个进程因竞争资源而造成的一种僵局（相互等待），若无外力作用，这些进程无法向前推进
解决方案
预防死锁
破坏互斥条件：有些资源必须互斥使用，无法破坏互斥条件
破坏不可剥夺条件：增加系统开销，降低吞吐量
破坏请求和保持条件：严重浪费系统资源，还可能导致饥饿现象
破坏循环等待条件：浪费系统资源，并造成编程不便
避免死锁
安全状态：能找到一个分配资源的序列能让所有的进程都顺序完成
银行家算法：采用预分配策略检查分配完成时系统是否处在安全状态
检测死锁
利用死锁定理化简资源分配图以检测死锁的存在
解除死锁
资源剥夺法：挂起某些死锁进程并抢夺它的资源，以便其他进程继续推进
撤销进程法：强制撤销部分、甚至全部的死锁进程并剥夺这些进程的资源
进程回退法：让一个或者多个进程回退到足以回避死锁的地步
内存管理
知识框架
程序执行过程
编译、链接、装入
逻辑地址、物理地址
扩充内存
覆盖与交换
连续分配
单一连续分配
固定分配
会产生内部碎片
动态分区分配
产生外部碎片
分配算法：首次、最佳、最坏、邻近适应
非连续分配
页式存储管理
概念：页面、地址结构、页表
地址变化机构及变化过程
快表
段式存储管理
段表、地址变换机构、段的共享和保护
段页式存储管理
段表、页表
虚拟内存
概念
局部性原理
特征：多次性、对换性、虚拟性
请求分页
组成：页表结构、缺页中断结构、地址变换结构
页面置换算法
最佳置换法
先进先出
Belady异常（抖动）
最近最久未使用
时钟算法
页面分配策略
预调页策略、请求调页策略
抖动、工作集
细节
引入目的：更好地支持多道程序并发执行，提升系统性能
程序的转入
绝对转入：适合单道程序环境
静态重定位：适合装入之后不在移动的情况
动态重定位：适合装入时还会移动的情况
程序的链接
静态链接：在程序运行前链接
装入时动态链接：在装入内存时，采用边装入边链接的链接方式
运行时动态链接: 在程序执行中需要该目标模块，才对它进行的链接
地址空间
逻辑地址空间
一个源程序在编译或者链接装配后指令和数据所用的所有相对地址的空间
物理地址空间
内存中物理单元的集合
内存保护
上、下限寄存器：分别与上、下限寄存器比较
基址、限长寄存器：与限长寄存器比较，与基址寄存器相加
管理方式
连续分配
单一连续分配：分配到内存固定区域，只适合做单任务系统
固定连续分配：分配到内存中不同的固定区域，分区可以相等也可以不等
动态分区分配
基本概念：按照程序的需要进行动态划分
分配方法
首次适应：按地址从大到小为序，分配第一个符合条件的分区
最佳适应：按空间从小到大为序，分配第一个符合条件的分区
最坏适应：按空间从大到小为序，分配第一个符合条件的分区
领进适应：与首次适应相似，从上次查完的结束位置开始查找
非连续分配
基本分页：内存分为固定的块，按物理结构划分，会有内部碎片
基本分段：内存块的大小不固定，按逻辑结构划分，会有外部碎片
段页式：基本分段和基本分页的结合，会有内部碎片
内存扩充
覆盖：预选设定覆盖段，覆盖掉暂时不用的内容，通常在同一个程序中进行
交换：把处于等待的程序暂时移到外存，通常在不同的程序中进行
虚拟内存
引入原因：在逻辑上扩充内存
组成部分
页表机制：通过查表获取相关信息
中断结构：要访问的页不在内存时产生缺页中断
地址变换结构：把逻辑地址变换成物理地址
内存和外存：需要一定容量的内存和外存的支持
置换算法
最佳OPT：选择以后不用的页面
FIFO：选择最先装入的页面
LRU：选择最近最久未用的页面
CLOCK：选择最近未用的页面
改进型CLOCK：考虑页面修改问题
地址翻译
TLB --> 页表（TLB未命中）-->Cache -->主存（Cache未命中）-->外存（缺页）
文件管理
知识框架
概念：定义、属性、基本操作、打开和关闭
文件逻辑结构
无结构文件（流式文件）
有结构文件（记录式文件）
索引文件
顺序文件
索引顺序文件
目录结构
文件控制块（FCB）、索引结点
单级目录结构、两级目录结构、树形目录结构、图形目录结构
文件共享
基于索引结点（硬链接）
利用符号链实现（软件链接）
文件保护
访问类型、访问控制
实现
层次结构
目录实现
线性列表、哈希表
文件分配
连续分配
链接分配
索引分配
索引链接、多层索引、混合索引
文件存储空间管理
空闲表法
空闲链表
位示图法
成组链接法
磁盘
访问时间
寻道时间、延迟时间、传输时间
调度算法
先来先服务：公平
最短寻找时间优先（SSTF）：饥饿现象
扫描算法
循环扫描
磁盘的管理
初始化、引导块、坏块
细节
基础
逻辑结构
无结构文件：将数据按顺序组织成记录并积累保存
有结构文件
顺序文件
串结构：记录之间的顺序与关键字无关
顺序结构：记录之间的顺序与关键字有关
索引文件：为变长文件建立索引表，提高查找速度
索引顺序文件：顺序文件和索引文件的结合
直接文件：通过哈希函数直接决定记录地址
目录结构
单级：全部文件放在一个目录下
两级：在目录下分出用户目录
多级：将两级结构加以推广，采用树形结构
无环图：在树型结构上加入一些有向边，便于共享
文件共享
基于索引节点（硬链接）：共享文件指向同一个索引节点
基于符号链接（软连接）：保存共享文件的路径名
文件保护
口令保护：通过口令访问文件
加密保护：对文件进行加密处理
访问控制：根据访问者的身份进行限制
实现
目录实现
线性列表
有序：查找文件较快，新建文件较慢
无序：查找文件较慢，新建文件较快
哈希表
查找、新建速度都比较快，要处理冲突
文件实现
连续分配
在磁盘上连续存放文件
链接分配
隐式：采用类似链表的结构
显示：把隐式文件中的指针单独抽离出来
索引分配：每个文件所有的盘块号都集中存放，建立索引表
存储空间管理
空闲表：把所有的空闲块组织成链表
空闲链表法：把所有空闲块组织成链表
位示图：利用二进制的每位记录空闲表
成组链接：空闲表和空闲链表的结合，适合大的文件系统
磁盘管理
磁盘地址结构
柱面号、盘面号、扇区号
读写时间
寻道时间：将磁头移动到指定磁道所需的时间
延迟时间：磁头定位到某一磁道的扇区所需要的时间
传输时间：从磁盘读出或向磁盘写入数据所经历的时间
启动时间（一般忽略）：控制器的启动时间
调度算法
先来先服务：根据进程请求访问磁盘的先后顺序进行调度
最短寻找时间优先：选择当前磁头所在磁道距离最近的磁道
扫描算法：在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求
循环扫描：在扫描算法的基础上规定磁头单向移动来服务
磁盘管理
初始化:对磁盘进行低级格式化和逻辑格式化
引导块：存放自举程序
坏块：对于损坏扇区的处理
IO管理
知识框架
概述
I/O设备分类
I/O控制方式：程序直接控制、中断驱动方式、DMA方式、通道方式
I/O层次结构：用户层I/O、设备独立软件、设备驱动层、中断处理层、硬件层
缓冲区
单缓冲
双缓冲
循环缓冲
缓冲池
缓冲区与高速缓存的对比
设备分配
概述
独占设备：独占式使用
共享设备：分时式共享
虚拟设备：SPOOLing方式
数据结构
DCT、COCT、CHCT、SDT
策略
静态分配、动态分配
逻辑设备名到物理设备名的映射
SPOOLing系统（虚拟设备技术）
组成、实例
细节
IO管理
设备分类
安传输效率分类
低速：鼠标、键盘
中速：如行式打印机、激光打印机
高速：磁带机、磁盘机、光盘机
安信息交换单位分
块设备：如磁盘
字符设备：如交互式终端机、打印机
控制方式
程序直接控制：程序直接对设备循环测试
中断驱动：引入中断机制，当设备准备完成时发生中断
DMA：在I/O设备与内存间开辟直接数据通路
通道控制：引入专门的I/O处理机进行处理
I/O子系统层次
用户层I/O软件：实现与用户交互的接口
设备独立性软件：实现用户程序与设备驱动器的统一接口、设备命令、设备保护以及设备分配与释放
设备驱动程序：与硬件直接相关，负责具体实现系统对设备发出的操作指令
中断处理程序：用于处理中断相关事项
硬件设备：包括一个机械部件（设备本身）和一个电子邮件（控制器）
I/O核心子系统
I/O调度：确定一个好的顺序来执行这些I/O请求
磁盘高速缓存
1、在内存中开辟一个单独的存储空间作为磁盘高速缓存
2、把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O分时共享
缓冲区
单缓冲
双缓冲
循环缓冲
缓冲池
设备的分配与回收
分类
独占式使用设备：设备使用时不再允许其他的进程使用该设备
分时共享使用设备：设备没有独占使用的要求时，可以通过分时共享使用
SPOOLing技术：将独占设备改造成共享设备
分配原则
既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户的程序和具体设备隔离开
分配方式
静态分配：在用户作业开始执行之前，由系统一次性分配该作业所需求的全部设备
动态分配：在进程执行过程中根据执行需要进行分配
收藏
收藏
0 条评论
下一页
