对不起我看吐了，考炸了
操作系统的目标
方便性，有效性，可扩充性和开放性
可扩充性：采用微内核结构 P30
发展主要动力
- 不断提高计算机资源利用率
- 方便用户
- 器件的更新换代
- 体系结构的发展
- 新的应用需求
多道程序设计的基本概念
利用I/O操作的空闲时间，调度B程序运行，B空闲调度C等 P8
优缺点
- 资源利用率高
- 吞吐量大
- 平均周转时间长
- 没有交互能力
==操作系统定义为:一组能有效组织和管理硬件和软件资源，合理进行调度，方便用户使用程序的集合==
分时系统（The Sharing System）
在一台主机上连接多个终端，允许多个用户同时通过终端以交互方式使用计算机，共享主机资源
特征
- 多路性
- 独立性
- 及时性
- 交互性
基本特性
有并发，共享，虚拟，异步四个基本特征
并行与并发
并行：多个程序同时执行
并发：分时交替执行（为主）
进程
指在系统中可以独立运行并且是资源分配的基本单元
共享
互斥共享方式和同时访问方式
虚拟
（没有那么多但感觉有那么多）
- 时分复用技术 （空闲时给其他用户服务
- 空分复用技术 （储存器空闲时存储和运行程序
异步
（同时开始，不同时结束）
进程以不可预知的速度进行
存储器管理功能
- 内存分配
- 内存保护
- 地址映射
- 内存扩充
OS结构设计
第一代无结构OS，第二代模块化OS，第三代分层式OS
进程
PCB进程控制块（Process Control Block）
定义：
- 进程的程序的一次执行
- 进程是一个程序及其数据 顺序执行的活动
- 进程是系统进行资源分配的独立单元
特性
- 动态性
- 并发性
- 独立性
- 异步性
进程状态转换
==P42-43==
操作系统内核
处理机两种执行状态：系统态和用户态
进程同步
临界资源-生产者消费者问题
设置临界区
- 进入区 判断资源是否被访问
- 临界区
- 退出区 将正被访问标志恢复为未被访问
- 剩余区
同步规则
- 空闲让进
- 忙则等待
- 有限等待 有限时间内能访问
- 让权等待 不能进入则释放处理机
利用信号量实现进程互斥
设mutex为互斥信号量，=1都未进入临界区，=0有一个进入运行，另一阻塞。= -1有一正在运行，另一等待。
线程
调度和分派的基本单位，能独立运行的基本单位
切换时仅保存和设置少量寄存器内容，切换代价远低于进程
处理机调度层次
高级调度
调度对象是作业，多用于多道批处理
低级调度
决定就绪队列哪个进程获得处理机
中级调度
提高内存利用率和系统吞吐量（把暂时不运行的进程调至外存，此时进程状态为就绪/挂起状态）
公式
CPU利用率
CPU利用率 = CPU有效工作时间/(CPU有效工作时间 + CPU空闲等待时间)
平均周转时间
T = 1/n(T1+T2 ······ +Tn)
平均带权周转时间
W = 1/n(作业周转时间Ti/提供服务Ts + ······ ) i=1,2,3,4…..
系统吞吐量大
与作业平均长度有关，单纯提高吞吐量可选择多的短作业运行
分时系统目标
- 响应时间快
- 均衡性（相应快慢和请求的复杂性相适应）
实时系统目标
- 截止时间的保证
- 可预测性
作业调度算法
FCFS（First Come First Server）先来先服务
SJF (Short Job First) 短作业优先
PSA (Priority-Scheduling Algorithm) 优先级调度算法
基于作业紧迫程度
HRRN (Highest Response Ratio Next) 高响应比优先调度算法
优先权 = (等待时间 + 要求服务时间) / 要求服务时间
RR ( Round Robin) 基于时间片的轮转调度算法
EDF (Earliest Deadline First) 最早截止时间优先算法
LLF (Least Laxity First) 最低松弛度算法
松弛度 = (必须完成时间 - 本身运行时间 - 当前时间)
死锁
定义
一组进程中每一个进程都在等待只有其他进程才能引发的时间
必要条件
- 互斥条件
- 请求和保持条件
- 不可抢占条件
- 循环等待条件
银行家算法 P121
判断 需求是否小于等于需要的
判断 需要是否小于等于可用的
模拟分配并检测是否有安全序列
磁盘缓存
在内存中暂存磁盘中读出的数据
固定分区分配
-
相等
-
不相等 建立表，记录分区信息
动态分区分配
常见数据结构:
- 空闲分区链
- 空闲分区表
空闲分区分配算法
FF (First Fit) 首次适应
从头找，找到空间再划分内存给作业
NF (Next fit) 循环首次适应
从上一次查找到的空闲区的下一个开始查找
BF (Best Fit) 最佳适应算法
把能满足要求、最小的空闲区分配，但碎片很多
WF (Worst Fit)最坏适应算法
总挑选最大的空闲区进行分配
优点 剩下的空闲区不至于太小 查找效率高
分页储存
分页储存
页面和物理块
用户程序的地址空间分为若干区域，成为页。
内存中同样划分，成为块
地址结构：
高20位 页号 低12位 位偏移量
页表
记录页在内存中对应的物理块号
分段管理
编程需要：
- 信息共享
- 信息保护
- 动态增长
- 动态链接
作业地址被分为多个段，所以呈现出二维特性
分段地址：
高16位 段号 低16位 段内地址
段表
各个段离散的放入内存不同分区中，需要为每个进程建立段映射表
实现从逻辑段到物理内存区的映射
虚拟存储器定义
具有请求调入和置换功能，从逻辑上对内存扩充的存储器系统
特征
- 多次性 分多次装入内存
- 对换性
- 虚拟性
页面置换算法
Optimal 最佳置换算法
预测最久不使用的页并进行替换。
FIFO 先进先出页面置换算法
总淘汰最先进入的（驻留最久的）
LRU (Least Recent Used) 最近最久未使用
选择最近最久未使用的页面
LRU和OPT，加物理块数不会增加缺页次数，FIFO不一定能减少缺页次数
抖动
原因
运行的进程太多，频繁出新缺页，进程大部分时间都用于页面的换进换出
预防
- 局部置换策略 只在分配给自己的内存中置换
请求分段储存管理
共享段表
分段保护
- 越界检查
- 存取控制检查
- 环保护机构 类似系统的内核等级
I/O基本功能
- 方便用户使用
- 提高CPU和IO设备利用率
- 共享设备时提供方便
中断处理程序
- 测定是否有未响应的中断信号
- 保护被中断进程的CPU环境
- 转入相应的设备处理程序
- 中断处理
- 恢复CPU现场并退出中断
图p206
DMA控制器
主机-控制器接口
- DR 数据寄存器
- MAR 内存地址寄存器
- DC 数据计数器
- CR 命令/状态寄存器
DC，MAR，CR获得从CPU传来的数据和命令，DR获取数据，并传入MAR
设置MAR和DC初值 -> 启动DMA -> 使用存储器周期传送数据 -> 存储器地址+1，DC-1 -> 循环
若DC = 0 请求中断
与设备无关IO
- 以物理设备名使用设备 不灵活，利用率也不高
- 逻辑设备名
设备控制表DCT
- 设备类型
- 设备标志符
- 设备状态
- 指向控制器表的指针
- 重复执行次数或时间
- 设备队列的队首指针
控制器控制表COCT
记录控制器情况
LUT (Logical Unit Table) 逻辑设备表
逻辑设备名 | 物理设备名 | 驱动程序入口地址
/dev/tty | 3 | 1024
逻辑设备表 | 系统设备表指针
/dev/tty. | 3
缓冲
CPU和IO设备速度不匹配
利用缓冲寄存器暂存数据
磁盘调度算法
FCFS
SSTF (Shortest Search Time First) 最短寻道时间优先
基于扫描的磁盘调度
SCAN 扫描算法 又称电梯调度算法
要访问的磁道与刺头当前距离较近
文件结构
文件逻辑结构
文件由一系列逻辑记录组成，是可以直接处理的数据及其结构，独立于文件的物理特性，又称文件组织
物理结构
对磁盘管理器的要求
- 有效地利用存储空间
- 提高磁盘IO速率
- 提高磁盘系统可靠性
外存组织方式
- 连续
- 链接
- 索引
链接组织方式
显式 表中放指针，链表、隐式 链表
FAT
分成卷
一个磁盘可多个卷，一个卷可由多个磁盘组成
文件第一个盘号放在FCB中，FAT每个表项最后放下一个盘块号
簇
是一组相邻的上去，作为虚拟扇区。盘块分配时以簇为基本单位
好处：能适应磁盘容量不断增大的情况，还可减少FAT表中项数
文件储存空间管理
空闲表法
给每个文件分配连续存储空间。
系统也会为外存空闲区建立空闲表
位视图法
二位数组模样，m*n=磁盘总块数
「真诚赞赏，手留余香」
Mr.Be1ieVe's Treasure
真诚赞赏，手留余香
使用微信扫描二维码完成支付
