操作系统
2020-07-28 10:12:14 0 举报AI智能生成
操作系统核心知识大纲
作者其他创作
大纲/内容
操作系统
进程
定义
PCB
特征
动态性
并发性
独立性
异步性
基本状态与相互转换
三个基本状态
就绪
执行
阻塞
相互转换
创建状态和终止状态
进程表PCB
作用
包含信息
组织方式
进程控制
执行状态划分
用户态
内核态
功能
支撑功能
中断处理
时钟处理
原语操作
资源管理功能
进程管理
存储器管理
设备管理
进程创建过程
进程终止
终止事件
终止过程
进程阻塞与唤醒
进程的挂起与激活
进程同步
概念
临界资源
临界区
对临界资源进行访问的那段代码称为临界区。
同步机制遵守的规则
空闲让进 忙则等待 优先等待 让权等待
硬件同步机制
信号量
整型信号量
记录型信号量
信号零应用
经典生产者消费者
管程
管程把控制的代码独立出来
经典进程同步问题
生产者消费者问题
哲学家进餐问题
读者写者问题
进程通信
管道
命名管道FIFO
消息队列
共享存储
套接字
线程
处理机调度与死锁
处理机调度的层次
高级调度
调度对象：作业
低级调度
即进程调度
调度对象：进程
中级调度
内存调度
处理机调度算法目标
共同目标
资源利用率
公平性
平衡性
策略强制执行
批处理系统目标
平均周转时间短
系统吞吐量高
处理机利用率大
分时系统目标（交互式系统）
响应时间快
均衡性
实时系统目标
截止时间的保证
可预测性
作业与作业调度
进程调度
进程调度的任务、机制和方式
任务
机制
方式
批处理系统中的调度算法
先来先服务FCFS
最短作业优先
最短剩余时间优先
交互式系统（分时系统）的调度算法
轮询调度
优先级调度
多级队列
最短进程优先
保证调度
彩票调度
公平分享调度
实时系统的调度算法
线程调度
内存
多层结构的存储器系统
无存储器抽象
有存储器抽象
地址空间
创建一种抽象内存来供程序使用
是一个进程可以用来来寻址内存的地址集。
基址寄存器
存储数据内存的起始位置
变址寄存器
存储应用程序的长度
交换技术
空闲内存管理
位图
使用链表来进行管理
首次适应算法FF
循环首次适应算法NF
最佳适配算法BF
最差适配算法WF
虚拟内存
分页
MMU 内存管理单元
存在映射的页如何映射
未映射的也如何映射
发生缺页中断/缺页错误
页表
虚拟地址=虚拟页号（高位）与偏移量（低位）
页表项的结构
加速分页过程
问题：虚拟地址到物理地址的映射速度必须快！！
转换检测缓冲区
软件TLB管理
针对大内存的页表
多级页表
倒排页表
页面置换算法
和页面置换相似的问题
缓存
最优页面置换算法
特点：寻找最晚要执行的页面对其进行替换
但是此算法无法实现！
最近未使用页面置换算法NRU
思想：随机地从编号最小的非空类中删除一个
先进先出页面置换算法FIFO
队列
不大常用
第二次机会页面置换算法
找一个早添加的页面判断是否用过（R位），没用过淘汰，用过就放在队列最后R为重置
因为第二次R位重置，所以这个算法可以结束
时钟页面置换算法
环形队列，类似一个表
最近最少使用页面置换算法LRU
很优秀 难实现
最不经常使用算法NFU
老化算法
工作集算法
什么是工作集？
一个进程当前正在使用的页面的集合
颠簸
预先调页
工作集时钟算法
分段
段：机器上提供多个互相独立的地址空间
长度：不同，可变
地址：段号 段内地址
分段与分页的比较
纯分段的实现
分段与分页的结合：MULTICS
死锁
资源
可抢占资源
不可抢占资源
竞争不可抢占资源易引起死锁
死锁简介
一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的时间，那么该进程集合就是死锁的
资源死锁
发生死锁的四个必要条件
互斥条件
每个资源要么已经分配给了一个进程，要么就是可用的，就是说某资源只能被一个线程占用
占有和等待条件
已经得到了某个资源的进程可以再请求新的资源
不可抢占条件
已经分配给一个进程的资源不能强制性的被抢占，它只能被占有他的进程显示地释放
环路等待条件
死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，环路的每个进程都在等待下一个进程占用的资源
四个条件缺一不可！！
处理死锁
鸵鸟策略
把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
死锁检测与死锁恢复
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
每种类型一个资源的死锁检测
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
每种类型多个资源的死锁检测
死锁恢复
利用抢占恢复利用回滚恢复通过杀死进程恢复
死锁避免
安全状态和不安全状态
定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
银行家算法
单个资源的银行家算法
多个资源的银行家算法
事实上 银行家算法并不使用 因为很难再运行前就知道所需要资源的最大值
死锁预防
破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏占有和等待条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
破坏不可抢占条件
抢占资源
破坏环路等待
给资源统一编号，进程只能按编号顺序来请求资源。
0 条评论
下一页
