一, 操作系统概述
1. 计算机软硬件系统
冯诺伊曼结构
以运算单元为核心, 控制流由指令流产生
程序和数据存储在主存中
主存是按地址访问, 线性编址
指令由操作码和地址码组成
数据以二进制编码
其他: 参考《重学计算机 - 计算机组成原理》
2. 计算机操作系统的发展
概述: 任何一台机器都有其操作平台和操作系统
洗衣机: 开关表示, 按钮控制, 亮灯显示
演进过程
手工操作: 手动调动地址和数据按钮录入内存, 然后点运行
引进装入程序: 用卡片和纸带, 通过 ROM 上的装入程序载入内存
汇编语言: 对指令提供了助记符号
高级语言: 面向问题
简单批处理系统: 编写作业控制程序, 缩短手工操作的时间
多道批处理系统: 排队执行作业, 不能同时, 也不能和计算机交互
分时系统, 实时系统: 进程间切换, 引入中断机制
通用操作系统: 同时具备以上功能
3. 不同视角下的操作系统
资源管理的角度:
资源: 硬件资源(处理器, 内存, 外设), 软件资源(数据, 程序)
例子: 驱动程序
共享: 资源独占, 并发共享
分配: 静态, 动态, 抢占
程序控制的角度: 进程
操作方式的角度: 脱机, 联机
人机交互的角度: 行命令, 全屏幕控制, 窗口界面, 虚拟现实
程序接口的角度: 系统调用(陷入机制)
系统结构的角度:
OS 构件: 内核, 进程, 线程, 管程
设计概念: 模块化, 层次化, 虚拟化
二, 处理器管理
1. 指令与处理器模式
指令执行周期: 取指, 译码, 执行
指令分类(根据权限)
特权指令: 只能被操作系统内核使用(启动 IO, 置 PC 值)
非特权指令: 所有程序都能使用
处理器模式:
共有四种: 0 内核模式, 1 系统调用, 2 共享库程序, 3 用户模式
一般来说: 只有 0 内核模式 (能执行全部指令) 和 3 用户模式(只能执行非特权指令)
模式切换:
用户模式 --> 内核模式(系统调用, 异常, 响应中断)
内核模式 --> 用户模式(中断返回指令)
2. 中断
概念:
操作系统是中断驱动的. 即中断是激活操作系统的唯一方式
广义中断: 停止 CPU 正在执行的进程, 转而执行中断处理程序, 处理完后返回原进程或调度新进程
狭义中断: 源于处理器之外的中断事件, IO 中断, 时钟中断, 外部信号中断
中断源:
处理器硬件故障中断事件: 内存故障
程序性中断事件: 除 0 异常, 缺页异常
自愿性中断事件: 系统调用
IO 中断事件: IO 完成
外部中断事件: 鼠标点击
中断系统:
实现: 硬件完成中断响应, 软件完成中断处理
中断装置:
处理器外中断: 由中断控制器实现
处理器内中断(陷阱): 由指令控制逻辑实现
系统调用(系统陷阱): 执行陷入指令时直接触发, 即系统陷阱
中断处理流程
多中断处理: 中断屏蔽, 中断优先级, 中断嵌套
3. 进程
进程: 操作系统进行资源分配和调度的独立单位
进程解剖: OS 管理进程的数据结构 P + 内存代码 + 内存数据 + 通用寄存器 R + PSW
进程状态:
进程数据:
进程控制块 PCB: 是 OS 用于记录进程状态和环境信息的数据结构
标识信息: 进程标识(进程标识号, 进程组标识号)
现场信息: 用户可见寄存器内容, 控制 / 状态寄存器内容, 栈指针内容
控制信息: 进程调度信息, 进程组成信息, 队列指引元, 通信相关, 进程特权信息, 处理器使用信息, 资源清单信息
进程映像: 某一时刻进程的内容及执行状态集合
进程控制块, 进程程序块, 进程数据块, 核心栈
进程上下文: 进程执行的环境支持(CPU 现场, Cache 中的执行信息)
用户级, 寄存器级, 系统级
进程的管理
进程实现的队列模型
进程控制流程
进程创建: 进程表增加一项, 申请 PCB 并初始化, 生成标识, 建立映像, 分配资源, 移入就绪队列
进程撤销: 从队列中移除, 归还响应资源...
进程阻塞: 保存现场, 修改 PCB, 移入等待队列
进程唤醒: 从等待队列移出, 修改 PCB, 进入就绪队列
进程挂起: 修改进程状态并出入相关队列, 收回内存等资源送至对换区
进程激活: 分配内存, 修改状态并出入相关队列
原语
概念: 由若干指令构成的完成某种特定功能, 有原子性
应用: 修改 OS 核心数据结构(进程表, PCB 池)
进程切换与模式切换
流程: 俩进程上下文切换(保存被中断的上下文, 进程调度, 恢复待运行的上下文)
模式切换: 用户态到内核态这种. 进程切换必须在内核态完成, 所以必须经理模式切换
4. 线程
多线程技术: 一个进程内有多个线程
思路: 将进程的两个功能 "独立分配资源" 和 "调度执行" 功能分开
分类:
KLT: 内核级多线程
ULT: 用户级别多线程
多线程实现的混合策略
一个 ULT 绑定多个 KLT
5. 处理器调度
处理器调度的层次: 高级, 中级, 低级
处理器调度算法
原则: 资源利用率, 响应时间, 周转时间(进入系统到出系统时间), 吞吐量(单位时间处理进程数), 公平性
算法: 优先数算法, 时间片轮转, 分级调度算法, 彩票算法
三, 存储管理
1. 存储管理的基本概念
逻辑地址: 用户地址, 从零开始编号
一维逻辑地址:(地址)
二维逻辑地址:(段号: 段内地址)
主存储器的复用方式
按分区: 主存划分为多个固定 / 可变分区, 一个程序占一个分区
按页架: 主存划分为多个固定页架, 一个程序占多个页架
存储管理的模式
单连续: 一维逻辑地址程序, 占一个固定 / 可变分区
段 式: 二维逻辑地址程序, 占多个可变分区
页 式: 一维逻辑地址程序, 占多个页架
段页式: 二维逻辑地址程序, 占多个页架
地址转换: 逻辑地址 --> 物理地址
静态重定位: 程序装入内存时转换(早期 OS)
动态重定位: CPU 执行时转换, 效率考虑需要硬件帮助
虚拟存储器
由于程序的局部性顺序性等, 可以考虑只将部分程序调入主存, 其他的随用随调
达到了面对程序员主存扩容的目的
2. 单连续分区存储管理
单用户连续分区管理: 主存区划分为系统区和用户区, 采用静态重定位进行地址转换, 一般适用于单用户单任务操作系统(DOS)
固定分区管理: 一个程序占一个分区, 有主存分配表, 容易产生内零头
可变分区管理: 按进程内存需求动态分配内存空间, 容易产生外零头
3. 页式存储管理 **
概念:
主存分页架, 程序分页.
不同程序页可放在不同主存页架中, 不需要连续
页和页架关系由页表维护
用位示图表示主存分配与去配, 用进程页表维护进程逻辑完整性
地址:
逻辑地址: 页号 + 单元号
物理地址: 页架号 + 单元号
快表:
利用 Cache 存放部分页表
同 Cache 缓存内存数据一样, 也是相联存储器技术, 并且有淘汰策略, 具体见《重学计算机 -- 计算机组成原理》
页式虚拟存储
页表: 标识位 + 主存块号 + 辅存地址
实现:
查页表, 若页在内存, 则生成绝对地址
若不在内存, 发起缺页中断
OS 响应缺页中断, 若内存有空闲页架, 则从辅存中调入页. 更新页表快表
若无空闲页架, 先淘汰页, 再调入
页面调度算法:
同 Cache 和内存的调度策略, 具体参考《重学计算机 -- 计算机组成原理》
4. 其他
段式存储管理: 基本不用, 略
段页式存储管理: 基本不用, 略
内存管理单元 MMU:
作用: 管理虚拟存储器的硬件控制线路, 把虚拟地址映射为物理地址, 并提供内存保护, 必要时淘汰页面
实现: 用一种数据结构 反置页表 IPT
PS: 许多年以前, 当人们还在使用 DOS 或是更古老的操作系统的时候, 计算机的内存还非常小, 一般都是以 K 为单位进行计算, 相应的, 当时的程序规模也不大, 所以内存容量虽然小, 但还是可以容纳当时的程序. 但随着图形界面的兴起还有用户需求的不断增大, 应用程序的规模也随之膨胀起来, 终于一个难题在程序员的面前, 那就是应用程序太大以至于内存容纳不下该程序, 通常解决的办法是把程序分割成许多称为覆盖块 (overlay) 的片段. 覆盖块 0 首先运行, 结束时他将调用另一个覆盖块. 虽然覆盖块的交换是由 OS 完成的, 但是必须先由程序员把程序先进行分割, 这是一个费时费力的工作, 而且相当枯燥. 人们必须找到更好的办法从根本上解决这个问题. 不久人们找到了一个办法, 这就是虚拟存储器(virtual memory). 虚拟存储器的基本思想是程序, 数据, 堆栈 https://baike.baidu.com/item/堆栈 的总的大小可以超过物理存储器的大小, 操作系统把当前使用的部分保留在内存中, 而把其他未被使用的部分保存在磁盘上. 比如对一个 16MB 的程序和一个内存只有 4MB 的机器, 操作系统通过选择, 可以决定各个时刻将哪 4M 的内容保留在内存中, 并在需要时在内存和磁盘间交换程序片段, 这样就可以把这个 16M 的程序运行在一个只具有 4M 内存机器上了. 而这个 16M 的程序在运行前不必由程序员进行分割.
四, 设备管理
1. IO 的控制方式
演进过程: 轮询 --> 中断 --> DMA --> IO 通道
经典布局: 南北桥
PS: 详见《计算机组成原理》
2. IO 的实现
软件实现层次: 硬件 --> 中断处理程序 --> 设备驱动程序 --> 独立于设备的 IO 软件 --> 用户空间的 IO 软件
IO 缓冲:
解决问题:
设备与 CPU 速度不匹配
逻辑记录大小和物理记录大小不一致
减少 IO 操作对 CPU 的中断次数
实现: 缓冲区
内存中开辟一个专门临时存放 IO 数据的区域
分类: 单缓冲, 双缓冲, 多缓冲
3. 磁盘
调度策略
移臂调度: 以双向调度中的电梯调度算法为经典
旋转调度: 写数据时采用交叉因子写入方式, 可以提高旋转读数据的命中率
五, 文件系统
1. 文件系统
文件系统概述
文件的组织:
逻辑结构: 流式, 记录式
物理结构: 顺序, 连接, 直接, 索引
文件的存取: 顺序, 直接, 索引
文件的控制: 逻辑控制, 物理控制
文件的使用: 打开, 关闭, 读, 写, 控制
文件的存储
块: 存储介质上连续存储的区域, 是主存与辅存信息交换的单位
顺序存取设备: 光盘, 磁带
直接存取设备: 磁盘
2. 文件
文件的逻辑结构
流式文件: 只是由一段字节序列构成的
记录式文件: 有含义有结构的信息, 比如员工工资记录
文件的物理机构
顺序文件: 块块之间相连, 批处理文件和系统文件一般都这么存.---> 数组
连接文件: 有连接字指向下一个块地址.---> 链表
直接文件: 又叫散列文件. 对内容进行散列存储到相应物理位置. ---> 散列表
索引文件: 为文件建立一个索引表, 可多级. ---> 增加了散列表的链表
文件的目录
概念: 实现文件按名存取的关键数据结构
分类: 一级目录, 二级目录, 树型目录
六, 并发程序设计
1. 并发程序的基本概念
程序顺序性
内部顺序性: CPU 严格按照顺序执行指令
外部顺序性: 程序员设计程序时往往用顺序设计的思想
顺序程序特性
程序执行的顺序性
计算环境的封闭性: 程序执行时犹如独占资源
计算结果的确定性
计算过程的可再现性
并发进程
无关的并发进程: 一组并发进程, 在不同变量集上运行
交往的并发进程: 一组并发进程, 共享某些变量, 相互影响
并发进程制约关系
进程互斥: 争夺某一个资源
进程同步: 共同完成某一个任务, 协调先后顺序
发生问题:
与时间有关的错误: 结果错误, 永远等待
临界区:
临界资源: 一次只能被一个进程使用的资源(互斥共享变量)
临界区: 是个程序段, 是并发进程中与互斥共享变量相关的程序段
相关的临界区: 两个进程的临界区有相同的临界资源(必须互斥进入)
问题:
多个并发进程访问临界资源存在制约关系
如果两个进程同时处在相关的临界区, 会发生与时间有关的错误
临界区管理的要求:
一次至多允许一个进程停留在相关临界区
一个进程不能无限制停留在临界区内
一个进程不能无限制等待进入临界区内
临界区嵌套使用
2. 并发程序控制和问题
临界区管理实现:
思路: 判断锁和获取锁要作为原子操作, 不然会死锁或时间错误
实现:
原子指令: 测试并建立锁指令, 对换指令(忙式等待, 效率不高)
中断控制: 进出临界区时开关中断, 这样临界区执行时就不会被中断, 自然实现了原子性
这个时操作系统的原语, 是操作系统解决这个问题的办法
不建议用户程序使用, 因为无法保证程序员设计出短小精悍的原语
PV 操作: 用信号量,"申请 - 等待队列 - 中断恢复"
生产者消费者问题:
进程间通信
信号量: 低级通信方式
信件: 进程通信机制(直接通信, 间接通信)
基于流: 多个进程共同使用一个缓冲区
RPC: 远程过程调用
死锁
概念: 两个进程分别等待对方占有的资源
死锁的产生
互斥: 进程互斥地使用资源
占有和等待: 一个进程得不到资源, 就等待且不释放已有资源
不剥夺: 进程不能从另一个进程抢走资源
循环等待: 每个进程都等待它前一个进程所持有的资源
死锁的防止
破坏上述四个条件之一即可
eg. 层次分配: 资源分成多个层次, 一个进程获得某个资源后只能获得比他层次更高的资源
死锁的避免: 银行家算法
死锁的检测:
算法: warshall 闭包
来源: https://www.cnblogs.com/flashsun/p/10669879.html