操作系统
2020-09-15 10:02:27 1 举报AI智能生成
408计算机基础，操作系统，二战123分老学长一年整理出来的资料。
作者其他创作
大纲/内容
文件管理
文件组成
文件控制块（fcb）
文件名
文件结构
文件的位置（逻辑块号）
存取控制信息
管理信息
文件体
目录结构
单机目录（不能重名）
二级目录结构（不同用户下的可以重名）
树级（多级）目录（可以重名）
绝对路径
从根目录出发
相对路径
从当前路径出发，加快查找速度
无环图（实现文件的共享）
共享
当删除一个硬链接后计数器为0删除这个文件，指向这个文件的软连接指针悬空
软连接
软连接计数器为1
可以跨文件系统
存放的是文件的绝对路径
若指向的硬链接被删除，指针悬空
硬链接
硬链接计数器加1
不可以跨文件系统
保护
访问控制矩阵
是一个矩阵因此需要m*n个bit表示m个用户n种权限的排列组合
访问控制表
用户权限表
口令和密码
结构
逻辑结构
流式文件
比如txt文件
纪录式文件
顺序文件
记录定长
记录定长的顺序文件可以实现随机存取
记录不定长
不定的顺序文件不可以实现随机存取
索引文件
索引表
索引表是定长文件
每一个索引项记录该条记录逻辑文件的起始位置和长度
逻辑文件
不存放每条记录的长度
索引顺序文件
一级索引顺序文件
索引表
不同于索引文件的索引表，它的索引项是一组记录的索引
逻辑文件
多级索引顺序文件
索引表是多级
加快查找速度，但是多级索引表的存放需要额外的空间
利用关键字找到该记录组中第一个记录的表项，然后，顺序查找所要求的记录
索引顺序要求块内可以无序，但是块间必须有序（一块中的所有关键字必须比另外的一块中的所有关键字全部大或者小），然后再将每块的最大值或者最小值作为索引。所以先找索引再顺序查找记录。
采用多级索引的顺序文件可以减少找到一条记录的查找次数
索引文件和索引顺序文件的区别
两者之间最大的区别是索引文件为为每一项建立一个索引，而索引顺序文件是为一组数据建立一个索引
文件分配方式（物理结构）
连续分配（fcb存放起始位置和块数）
链式分配（fcb存放起始位置和结束位置）
隐式链式分配（在每一块的后面放一个下一块的地址）
显式链式分配FAT（文件分配表）
可用于空余块的管理
索引（fcb存放索引表的位置）
单级索引
多级索引
混合（有多级索引和直接地址）
空闲块管理方式
位示图
每一位的01代表这个位置是否是空闲
一般来说位置都是从0开始
成组链接法（超级块）
分配
1.判断超级块中N是否大于一，若大于一则执行2，等于1执行3
2.分配栈顶指针指向的块
3.将栈顶指针指向的块的信息拷贝到超级快里面，原栈顶指向的块分配出去
回收
1.判断超级快是否满，若不满则执行2，满则执行3
2.将改内存块挂到超级快的末尾
3.将超级块的信息拷贝到空闲块中，超级快指向这个块
空闲文件表
注意回收时的合并
空闲块链表
FAT文件分配表
目录文件（逻辑上是定长的顺序文件）
存放有序的文件目录项的文件
文件控制块就是文件目录项
索引节点（相当于为定长的记录文件建立的索引）
在检索文件目录时只能用到用户名因此将文件名和指向文件描述信息的指针
此处的文件描述信息就是原本文件控制块的信息
i/o操作
io设备分类
字符型（鼠标，键盘）
块设备（可寻址，u盘）
网络通信设备（锚）
io系统分类
用户层io软件
设备性独立软件
设备逻辑设备名和物理设备名之间的转换，实现设备无关性
设备驱动程序
与硬件直接相关（如计算磁盘的的实际地址）
中断处理程序
处理中断
硬件
机械设备
设备控制器
一个设备控制器可以连接多个设备因此一个设备控制器可以有多个地址
io控制方式（内存和外设之间，不一定是外存）
轮询（消耗大量的cpu资源）
中断（和轮询一次传送的大小相等）
DMA，直接内存访问，以块为单位，一个或者是多个连续的块（数据由内存到外设时经过DMA缓存，用于高速外设比如磁盘）
通道（微处理机硬件支持，传输的可以是多个不连续的块）
字节多路通道（连接多个中低速设备）（并行，传输慢）
数组选择通道（设备独占通道）（外设独占通道，传输快）
数组多路通道（数组方式连接中高速设备）（结合和两者特点既并行又传输快）
缓冲区
单缓冲
max（调入主存储区时间，cpu从用户区取数据时间）+主存储区到用户区时间
计算多个的时候需要增加一个cpu从用户区取数据时间
双缓冲
max（调入主存储区时间，cpu从用户区取数据时间+主存储区到用户区时间）
计算多个事需要增加一个cpu从用户区取数据时间和一个主存储区到用户区的时间
循环缓冲
缓冲池
很好的支持多个进程的输入输出
设备分配
设备分类
独占设备
如打印机
共享设备
如磁盘
虚拟设备
物理上独占设备的设备改造成逻辑上个共享的设备
设备分配算法
先来先服务
优先级高的优先
设备分配的安全性
静态分配
作业运行前一次性分配作业设备，直到作业结束
动态分配
安全分配
进程申请IO就进入阻塞态防止死锁
破坏请求并保持条件，不会死锁，但是推进慢
不安全分配
进程申请IO后还可以继续申请
推进快但是可能会出现死锁
spooling技术
假脱机技术（将物理的独占设备改为逻辑上的共享设备）
组成
输入输出进程
输入输出缓存区
输入输出井（高速设备一般是磁盘）
特点
提高IO速度
实现了虚拟设备的功能
spool除了是一个速度匹配技术还是一个虚拟设备技术
操作系统
操作系统的诞生
批处理（单道和多道），分时操作系统，实时操作系统
多道批处理引入中断，操作系统正式出现
分时操作系统，多用户交互
实时操作系统：加入优先级可以及时的响应用户的操作
操作系统的四大特性：并发，共享，虚拟，异步
最基础的是并发和共享
并发和共享互为条件
并行需要硬件的支持
提供服务
提供给用户
命令接口
用户界面
提供给程序员
系统调用
系统调用在用户态
系统调用的执行只能在核心态
系统调用是程序和操作系统的接口
必要性
系统调用的目的是让系统 资源有序，按照指定的规则被应用程序使用
性能
吞吐量
一秒执行的作业个数
指令
广义指令（核心态），可以认为是系统调用命令
访管指令（只能在用户态，进入核心态的指令，引起访管中断，自愿进管，系统调用时会执行陷入）也叫陷入指令
特权指令 只能在核心态运行的指令
调度
高级调度（作业调度），中级调度（内存调度（交换技术）调用调出的是进程，而不是进程的页），低级调度（cpu调度）
异常和中断
中断和异常的区别是中断是来自cpu外部异常产生于cpu内部
中断可以嵌套，异常一般为一层
中断处理程序不会产生异常，不会被阻塞，异常处理程序可能被阻塞
中断可以被屏蔽
核心态唯一会产生的异常时缺页异常
中断处理程序是只能是系统程序
异常是内中断
硬件中断
缺页中断
软件中断
除0
切换
五中状态：就绪态，运行态，阻塞态，新建，结束之间的转换关系
用户态和核心态以及两者之间的转换
用户态到核心态只能靠硬件中断
核心态到用户态转换只需要更改状态寄存字
内核体系结构
大内核
内核功能比较多
效率快（内核态和用户态的切换少）
微内核
内核功能比较少，内核保留少部分的功能
复杂度低易于维护
内核和服务之间，服务和服务之间接口接口更清晰
进程管理
进程的调度算法
先来先服务（作业调度和进程调度）
相对比较公平
不会产生饥饿
对长进程比较友好
现在很少使用一般与其他的调度算法结合，比如在优先级相同的时候是使用先来先服务
短进程优先（作业调度和进程调度）
对短进程比较友好
可能会产生饥饿
分为抢占式和非抢占式
优先级调度（作业调度和进程调度）
分为静态或者是动态优先级调度
分为抢占式和非抢占式
优先级相同时可以按照短进程优先或者是先来先服务选取
高响应比（作业调度）（不合适交互式系统）
（等待时间+要求服务时间）/要求服务时间
既考虑到短进程又考虑到等待的时间
时间片轮转（进程调度）
分配固定的时间轮流服务，时间片太大和太小都不好
多级响应队列（进程调度）
队列由上到下时间片逐渐增加
时间片小的队列运行完后放进时间片较大的队列
队列由上到下优先级逐渐降低
优点
1.新来的进程放入优先级高的队列，有先来先服务的优点
2.单个优先级队列时间片轮转，有时间片轮转的优点
3.优先级高的队列时间片短，短进程友好
进程的同步与互斥
互斥原则
1.空闲让进
没有进程进入临界区的情况下应该立即允许一个进程立即进入临界区
2.忙则等待
一个进程进去临界区其他的试图进入临界区的进程需要等待
3.有限等待
等待的时间应该是有限的
4.让权等待
不能进去临界区的进程应该释放自己的处理器资源
硬件实现（都不符合让权等待原则）
中断屏蔽
swap指令
testandset
软件实现（都不符合让权等待原则）
单标记法
违反空闲让进，只能两个进程进程交替访问
双标记先检查法
先检查时可能出现两个都是false的情况从而两个都进入，不符合忙则等待
双标记后检查法
后检查可能出现两个都是true的情况，两者无限等待下去，不符合有限等待
peterson算法（不会产生饥饿或者是死锁，但不满足让权等待的原则）
信号量法（通过pv操作）（满足四个互斥原则）
生产者消费者问题
读者写着问题
抽烟者问题
哲学家就餐问题
管程（管理进程）
组成部分
数据结构
数据结构上的操作
数据结构的初始化
一次仅允许一个进程进入管程
管程和信号量的区别
管程的引入是为了系统的管理程序中散乱的pv操作
管程的wait和p不同，wait直接阻塞
管程的sign和v不同，若没有该条件下阻塞的进程sign什么也不做，而v会将信号量加一
管程的sign必须在wait操作后执行
进程和程序
程序
顺序执行的程序
顺序性（一条执行后再执行另一个）
封闭性（独占系统的资源，这些资源只有本程序能使用）
可再现性（再次执行获得相同的结果）
并发执行的程序
间断性（执行-间断-执行）
失去封闭性（资源状态由几个进程共同决定）
不可再现性（两次执行的结果不一定相同）
进程
进程是一个动态的概念（进程映像或者叫进程实体是静态的概念）
进程的构成（pcb，数据，程序）
进程的控制由原语（不可中断）实现，比如说创建原语撤销原语
进程切换
进程的切换一定会中断，处理机状态由用户态切换到核心态，切换后由核心态进入用户态
处理机状态的切换不一定会引起进程的切换
进程的阻塞和唤醒
阻塞是一种主动行为是进程调用阻塞源于来自我阻塞，由运行态到阻塞态
唤醒是一种被动行为，是协作的进程唤醒阻塞进程，由阻塞态到就绪态
不能执行进程调度的时间
中断处理（在机组中中断单中断和多重中断都是有关中断和开中断）
在操作系统的内核临界区中（注意是内核的临界区，普通的临界区中是可以调度的）
其他屏蔽中断的原子操作
进程和线程的联系和区别
进程是资源分配的独立单位，进程中的线程共享进程的资源，线程没有独立的地址空间（共享进程的）
（内核级）线程是处理机调度的独立单位
线程的分类
内核级线程
为系统所感知
切换的时候需要内核的参与，因此开销比用户级线程大
单独一个线程阻塞不会影响进程的其他线程
用户级线程
不为系统所感知，调度的时候任然是以进程为单位
切换的时候不需要内核的参与，系统开销小
单个线程的阻塞会引起整个进程的阻塞
在不支持内核级线程的系统中也可以运行
内核级线程和用户级线程的对应关系（该系统必须同时支持用户级线程和内核级线程）
多对一关系
在同一个内各级线程下的用户级线程一个阻塞则这个内核级线程被阻塞
一对一关系
一个内核级线程对用一个用户级线程，系统开销大
多对多关系
一个用户级线程阻塞后不影响其他的线程
内核级线程是操作系统调度的独立单位，一个进程若有多个内核级线程，则这多个内核级线程可以实现并行
进程之间的通信
共享文件
消息传递
发送消息原语是接收消息原语
直接通信
间接通信（信箱）
管道（单向）
只有空的时候可以写（否则阻塞）
只有满的时候可以取（否则阻塞）
管道可以有多个写进程但只能有一个读进程
进程从管道中取完数据后会从管道中删除，若多个读进程可能会出现接收信息错乱的情况
多个进程给一个进程发送数据的时候，因为接收进程是一个因此不会出现上面说的情况
共享内存（共享存储区）
临界区临界资源
临界区是访问临界资源的那段代码
临界资源是操作系统的资源
死锁
死锁的预防 死锁的四个必要条件（预防死锁）
互斥条件（一般不可破坏）
请求并保持（一次申请完）
不可剥夺（释放自己的资源）
循环等待（给资源编号）
死锁的避免
银行家算法（避免死锁）
安全状态一定不会死锁
安全状态的定义就是不会发生死锁（在银行家算法下不会分配给可能死锁的资源，因此不会发生死锁）
不分配给可能发生死锁的的进程资源并非是限制资源的申请顺序
举例
a进程申请两种资源x1,x2必须先申请x1后再申请x2这叫限定资源的申请顺序
不安全状态不一定会死锁
不安全状态是这一刻的状态，而随着时间的推移系统资源的数量可能会变化所以只是可能会发生死锁
死锁的检查和解除
资源分配图（死锁定理）判断是当前状态是不是死锁状态
撤回进程，回退进程（回退在一段时间前的状态）
内存管理
程序执行
编译
编译程序实现
生成若干目标模块
链接
链接程序实现
形成逻辑地址
生成完整的装入模块
分类
静态链接
运行前将各个目标模块和库函数链接成一个可执行程序
动态链接
装入时动态链接
将若干目标模块装入内存时边装入边链接
运行时动态链接
在执行的过程中发现一个模块没有被装入内存，找到它并将它链接到模块上，并装入内存
装入
装入程序实现
将装入模块装入内存
分类
绝对装入
编程时就知道调入时的内存地址
不合适多道程序
可重定位装入
装入时一次完成
也叫静态重定位
无需地址变换机构（如页表）
要求连续的区域
动态运行装入（典型的例子页表）
允许程序在运行时移动位置
不一定需要连续的区域
需要地址变换机构
形成物理地址
扩充技术
覆盖（对用户不透明）
交换（pcb不会调出内存）
现在多使用，不同于虚拟存储技术（以页为单位）
是以单个程序为单位，中级调度
交换技术的换出对应的是七态模型里面的 挂起，阻塞不会交换出内存
虚拟存储（动态重定位）
程序的局部性原理（不均匀性）
时间局部性调用过的指令在一段时间内被再次调用
空间局部性，调用的的指令的上一条或者是下一条被调用
特性
离散型
多次性
交换性
虚拟性
方式
请求页式
可能会出现中断
地址越界（查询页表时或者是段表）
缺页（改页不在内存中）
访问权限错误
不会出现的中断
内存溢出
页面置换算法
最优页面置换算法
性能最好但不能实现
先进先出置换算法
唯一可能会产生贝拉异常，易实现，性能差
最近最久未使用
淘汰页面需要排序，有一定的开销
时钟算法
最近访问位
过程
第一步.检查是否命中，若命中则修改命中页面的访问位为1指针不移动否则执行第二步
第二步检查当前指针位置的访问位是否为0若为0则替换该页并将访问位置1指针下移，否则执行第三步
第三步将当前指针指向的页面修改位改为0，指针下移重复第二步
改进的时钟算法
最近访问位和最近修改位
页面何处调入
Unix方式
调入内存
首次调入内存从磁盘的文件区调入内存
非首次调入内存用磁盘的交换区调入内存
调出内存
调出内存由内存到磁盘的交换区
系统有足够多的的交换区
系统运行前将进程有关的文件全部调入对换区
系统没有足够多的的交换区
系统运行前只将会被修改的文件调入交换区
内存分配策略
固定分配局部置换（该开始就给定，不允许更改）
可变分配全局置换（缺页就给）
可变分配局部置换（根据缺页率动态分配内存块）
全局置换意味着缺页就给，固定要求不允许给，因此不存在固定分配全局置换的算法
内存分配算法
连续分配
单一连续分配（整个内存分为操作系统和程序）
固定分区分配（产生内部碎片）
分区大小相等
分区大小不等
动态分区分配（产生外部碎片）
产生的外部碎片可以靠紧凑技术但是需要消耗大量的时间
记录内存的使用情况
1.空闲分区表
2.空闲分区链
分区分配算法
首次适应
空闲分区按照按照地址递增
性能最佳
下次适应
空闲分区按照按照地址递增
更加均匀
最佳适应
空闲分区按照按照大小递增
最容易存生外部碎片
最坏适应
空闲分区按照按照大小递减
不容易保存区域大的连续内存
碎片概念
内部碎片
分配单位大小固定（如页，固定分区）占不满一个单位
外部碎片
由于不连续的空间太小不能分配
离散分配
页式管理
优点
不需要连续的地址空间
便于存储访问
不会有外部碎片
缺点
需要地址变换机构（页表）的支持
产生内部碎片
不利于存储保护
段式管理
优点
不需要连续的地址空间
方便编程
方便信息保护和信息共享
便于动态链接
缺点
需要硬件支持
外部碎片需要拼凑技术浪费时间
段页式管理
优点
无外部碎片
具有段式和页式的优点
缺点
需要硬件支持
地址变换的过程需要多次访问内存增加了时间
仍有内部碎片
本质
在逻辑上分段，段内分页
内存保护
界寄存器
1.上下界寄存器和形成的物理地址比较
2.相对地址和限长寄存器比较，若在范围内加上基址寄存器的值后形成物理地址
保护键
给每个单独的存储块分配键
作业赋予保护键判断它是否和存储块的键相等
pv操作大题
1.草稿纸上次写出行为轨迹，每个行为前后留出足够的空间放pv操作
2.分析哪个地方前会出现等待，那个地方会互斥访问临界资源
在需要等待的地方p一下
需要互斥访问的行为，先p后v，紧贴互斥行为
3.坚持一个原则，pv操作一定是成对出现的，在需要等待的地方p一下资源，在等待事件发生后的地方v一下这个资源
4.先确认pv操作的位置，再确定初值
0 条评论
下一页
