导图社区 操作系统
操作系统是管理计算机硬件与软件资源的计算机程序。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。
数据结构与算法 数据结构是计算机中存储、组织数据的方式。 数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。
计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备，通过通信线路连接起来，在网络操作系统，网络管理软件及网络通信协议的管理和协调下，实现资源共享和信息传递的计算机系统。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
操作系统
文件系统
概念
簇与块
Windows下叫簇,Linux下叫块
文件系统管理的最小单位
逻辑结构
顺序文件
索引文件
需要一张索引表
定长记录文件的索引表无长度项
顺序索引文件
当索引数=索引块内条目数时查找次数最少,为sqrt(N)
直接文件或Hash文件
目录
文件目录即文件的FCB
目录文件指表示目录的文件,这种文件的数据是其子文件与子目录的目录项
FCB包含文件权限信息
在UNIX中FCB分离为文件目录与索引节点
文件目录仅包含文件名与索引节点指针
FCB中包含着物理地址,具体取决于实现方式
连续分配
首地址
链接分配
索引分配
索引块地址
内存索引节点
逻辑设备号
链接指针
访问计数
状态
是否被访问/修改
编号
标识内存结点
硬链接与软链接
每个目录下都有两个硬链接文件,一个指向自身,另一个指向父目录
因此每个目录的硬链接数=2+子目录数
软链接
事实上是一个包含指向文件路径的文件
访问时就相当于按照这个路径访问文件
因此比硬链接慢
在linux中，当拥有某文件的权限而不拥有父目录的权限，此时硬链接能访问该文件而软链接不行
目录结构
单级
不允许文件的文件名相同
两级
允许不同用户持有文件名相同的文件
树型
路径名唯一确定文件
无环图
支持用户间文件共享
访问控制
访问控制列表ACL
又称存取控制矩阵
口令
要求访问文件时必须提供口令
口令存储在OS内部,不安全
密码
加密文件,需要使用密码解密
文件访问
用户调用接口
系统依次查找目录以获取文件FCB或索引节点
按照索引信息检查用户访问权限
将用户提供的逻辑地址转换为物理地址
文件实现
目录实现
线性表
只支持顺序查找
在表尾添加新目录项
哈希表
文件分配方式
显式链接分配（FAT）
在内存中
并可用于管理空闲块
在FAT中0，1号簇有特殊用途
-9表示坏块，-10~-15保留，-8~-1用于文件结束标志
但是计算最大支持文件仅需考虑表项长度（例如FAT16，2^16*sector size即可
最大地址也只需考虑FAT表长度
隐式链接分配
目录包含头尾指针
稳定性差
多层索引
混合索引分配
Linux方式
逻辑卷与物理卷
逻辑卷包括目录区和文件区
空闲空间管理
空闲表
头地址-空闲块长度
跟内存回收一致，可以合并
空闲链表
空闲盘块链
将空闲盘块串起来
每个项长度为1
空闲盘区链
将连续的空闲盘区串起来
每个项长度不定
位图法
成组链接法
每个索引块含有(n-1)个数据块与1个索引块的指针
系统拥有一个指向第一个索引块的指针
磁盘管理
格式化
低级格式化
创建物理扇区
确定物理扇区使用的数据结构
例如校验码的位数
逻辑格式化
创建文件系统
访问时间
寻找时间（寻道时间）
延迟时间（旋转延迟）
平均半圈
传输时间
一般而言，传输时间等于转过该扇区需要的时间
磁盘调度
FCFS
SSTF
SCAN
双方向处理
CSCAN
单方向处理
默认LOOK=SCAN,CLOOK=CSCAN
概论
性能指标
MIPS
每秒百万指令
由于快慢是相对程序而言的，MIPS大的计算机不一定比MIPS小的快
操作系统特征
并发
一段时间内多个任务
并行
同时多个任务
注意并行一定是并发的
共享
资源共享
分类
独占/互斥共享
同时访问
虚拟
虚拟存储器
虚拟设备
异步
进程推进顺序不可预知,与调度有关
接口
命令接口
交互式命令接口(SHELL)
批处理命令接口(BAT)
程序接口
用户程序通过使用系统调用获取服务
系统调用
又称广义指令
可以在用户态调用
在内核态执行
操作系统演进
总体上,批处理->分时->实时
单道批处理系统
多道操作系统(多道批处理系统)
也称多任务操作系统
宏观上并行，微观上并发/串行
主要缺点是不提供人机交互能力
分时操作系统
支持交互
实时操作系统
软实时
硬实时
有硬指标
每个进程/线程有两个栈,用户栈与内核栈
当陷入中断进入内核态后,会将当前栈指针压入内核栈,之后在内核态下运行
返回时使用中断返回指令(iret)而非无条件跳转指令
在系统调用中可以被阻塞
大内核与微内核
微内核增加稳定性,降低性能
进程管理
进程的组成,状态
进程控制
创建
分配PID
分配必要资源
如果资源不足,进入阻塞态
初始化PCB
插入就绪队列
终止
按PID查找PCB
若正执行,立刻终止执行
关闭所有子进程
释放资源
删除PCB
阻塞
将状态改为阻塞,插入等待队列
唤醒
切换
一定处于核心态
IPC
高级通信
消息传递机制
直接通信
操作系统提供一组原语,通信不经过操作系统
间接通信
双方通过共享中间实体(邮箱)交换信息
存储器共享
管道
低级通信
信号量
线程
共享地址空间及其他资源
共享堆但不共享栈
不共享栈,但允许runtime利用指针等方式访问其他线程的栈空间
假装不考与父子进程的联系与区别
内核级与用户级
内核级线程是native的,由os调度
用户级线程由library支持,由lib调度
因此多对一模型一个线程阻塞将导致整个进程阻塞
调度
高级/作业调度
只进行一次,使作业开始运行
中级/内存调度
即交换技术,将暂时不运行的进程移出内存
低级/调度
不适合IO型进程
因为进入阻塞态的概率会比IO型大得多
事实上对短进程不利
RR
一定是抢占式
SJF
必定导致饥饿
高响应比
没有饥饿
多级反馈
(静态)优先级
系统进程>用户进程
交互型>非交互型
IO型>计算型
不能调度的情况
中断中,此时逻辑上不属于某一进程
在操作系统内核临界区时
注意在普通临界区可以调度
内核临界区指访问OS互斥资源的临界区,例如访问PCB的代码
在原语中
注: 目前(Linux2.6以后),当不属于上述情况时,处于内核态的程序总可以被抢占
另外,当使用抢占式时,当从内核态回到用户态时,总会发生调度
进程同步
整型信号量
忙等
记录型信号量
先修改再对队列进行操作
所以注意临界条件
进程之间的关系
同步
又称直接制约
互斥
又称间接制约
没有逻辑上的先后
死锁判断
代码中有计数器时认为有多个进程,例如读写者问题
并发进程推进的相对速度与调度策略有关
单缓冲区的生产者消费者问题不需要mutex
管程
语言机制,保证同一时刻至多一个进程使用管程
条件变量
为了使管程支持同步,加入类似信号量的机制
条件变量拥有wait和signal方法
与记录型信号量的不同的时它不记录值,仅将进程移入移出等待队列
死锁
鸵鸟策略
Windows
Linux
OpenBSD
死锁的原因
共享资源不会死锁
不剥夺
不允许OS强制拿走进程目前独占的资源
请求并保持
进程保持资源后又会提出新请求
循环等待
死锁预防
破坏互斥
不现实
破坏不剥夺
一般用于易于保存和恢复的资源
破坏请求并保持
静态分配,即一次分配所有资源
破坏循环等待
顺序资源分配
死锁避免
使用银行家算法防止进入不安全状态
限制资源的分配顺序而非申请顺序
死锁检测
资源分配图
进程是大圆
资源是方框,其中的小圆代表资源实例
资源向进程的边为分配边
进程向资源的边为请求边
死锁定理
S死锁当且仅当资源分配图不可完全化简
死锁解除
资源剥夺
挂起某些死锁进程并剥夺资源
可能导致这些被剥夺进程的饥饿
撤销进程
撤销部分或全部死锁进程
回退
需要设置还原点
执行对象不一定死锁
内存管理
交换,覆盖
交换指硬盘中的进程A覆盖内存中的进程B
覆盖指进程在硬盘中的段A覆盖内存中的段B
交换要求换出的进程必须空闲
覆盖段必须由开发者手动设计
装入与链接
链接
静态链接
编译为一个完整的程序
装入时动态链接
编译为多个模块,装入时一起读入
执行时动态链接
编译为多个模块,需要时再读入
装入
绝对装入
程序将被放置到固定位置
只适合单道程序
可重定位装入
又称静态重定位
在装入时将代码段的相对地址修改为绝对地址
一旦装入后,内存位置与大小就不再变化
动态运行时装入
需要重定位寄存器的支持
允许地址空间比存储空间大
内存分配方式
单一连续分配
只适合单道环境
固定分区
等长分区
不等长分区
动态分区
无内部碎片有外部碎片
非连续分配
分页
每个进程有半页的页内碎片
页表基本上常驻内存
需要增加页表寄存器
快表TLB
页号可能有越界中断,但页内偏移没有
分段
段表寄存器
分段系统中地址二维,由用户提供
段号和段内偏移都可能出现越界中断
段页式
高层段机制,底层页机制
虚存
核心是局部性原理
只能在非连续分配上实现
页面置换算法
页面置换只考FIFO OPT LRU CLOCK
Belady
有FIFO选FIFO
会出现Belady的算法
NRU/CLOCK及其改进
FIFO
不会出现Belady的算法
OPT
LRU
CLOCK算法
替换后额外移动一次指针
改进型CLOCK一般会提供指针位置
页面分配策略
没有固定分配全局置换
驻留集指进程的物理页框集合
调入页面的时机
预调页
请求调页
从何处调入
swap够
文件预先复制到swap
从swap调入
swap不够
不被修改的部分从文件区调入,不换出
可能被修改的文件换出后再从交换区调入
UNIX
所有文件初次均从文件区调入
由其他进程调入的共享页面不重复调入
工作集
最近访问窗口中的不同页面
