02 操作系统

概述

操作系统的角色：

• 管理系统的硬件、软件、数据资源
• 控制程序运行
• 人机之间的接口
• 应用软件与硬件之间的接口

管理分类：

• 进程管理
• 存储管理
• 文件管理
• 作业管理
• 设备管理

特征：

• 并发性
• 共享性
• 虚拟性
• 不确定性

进程状态

基本概念：进程是程序的一次执行。通常由程序、数据、进程控制块组成。是资源分配和独立运行的基本单位。

进程两个基本属性：

• 可拥有资源的独立单位
• 可独立调度和分配的基本单位

三态模型

• 运行：万事具备
• 就绪：只等CPU资源
• 等待（阻塞）：除了CPU资源，还在等其他资源

五态模型

• 运行
• 静止就绪（运行过程中主动挂起）
• 活跃就绪
• 静止阻塞
• 活跃阻塞=等待

前趋图

同步与互斥

概念：同步指的是一些需要相互合作的进程，之间的相互联系；互斥指的是争用临界资源而互斥执行

• 互斥：一个资源同时只能被一个进程所用
• 同步：速度有差异，一定情况下要等待

【注意】：两者不为相反的概念，互斥<->共享，同步<->异步

在生产者消费者问题，理解互斥和同步：如一个商场只能存放一件物品，若目前已有一件时，生产者无法将新的一件放入（互斥）；生产者是否可以放入也取决于消费者是否消费了这个物品，只有等消费者消费了，生产者才能新生产（同步）

PV操作（信号量机制）

概念

临界资源：进程间需要互斥访问的资源（如打印机，磁带机）

临界区：每个进程中访问临界资源的那段代码

信号量：一种特殊的变量，如P(s)中的s

• 公用信号量：实现互斥，初值为1或资源的数目
• 私用信号量：实现同步，初值为0或某个正整数

P分配（减），V释放（加）

• P操作后，>=0继续执行；<0设为阻塞
• V操作后，>0继续执行；<=0从阻塞唤醒一个进程到就绪队列，然后V操作的进程继续

例子（单缓冲区）：

习题：

答案：A和C

PV操作和前趋图

【重要！经常考！】

例题（答案：CAA）：

解题思路：信号量的赋值可根据从上到下、从左到右的原则赋值，出箭头设为V(s)，入箭头设为P(s)。如P1出箭头那里是V(S1)，P2出箭头那里是V(S2)，P3入箭头那里是P(S1)和P(S2)。

进程调度

• 高级调度（作业调度）
• 中级调度（交换区的哪个就绪进程可以调入内存）
• 低级调度（进程调度，决定内存中的哪个就绪进程可以占用CPU，最重要）

进程调度：

• 先来先服务
• 时间片轮转
• 优先级调度
• 多级反馈调度：时间片和优先级算法的综合发展

线程

概念：线程作为调度和分配的基本单位，进程作为独立分配资源的单位。线程基本不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈）。

线程可以创建另一个线程，同一个进程中的多个线程可以并发执行

分为：

• 用户级线程：不依赖内核，创建、撤销、切换不利用系统调用
• 内核支持线程：依赖内核，利用系统调用

死锁

最小需要多少个资源不发生死锁

公式：k*(n-1)+1；k：进程数，n，每个进程需要的资源数

死锁四大条件

• 互斥
• 保持和等待
• 不剥夺
• 环路等待

解决死锁

• 预防：打破四大条件
• 避免：有序资源分配法，银行家算法
• 检测
• 解除：资源剥夺法、撤销进程法

银行家算法

例题：

存储管理

概念：地址重定位，将外存中的程序装载到内存，需要将程序中指令和数据的逻辑地址转换为对应的物理地址

分区存储

• 首次适应法
• 最佳适应法（空闲区块按大小顺序链式排列，找最小能满足分配空间的内存块）
  • 内存碎片多
• 最差适应法（类似最佳，找最大能满足的内存块）
• 循环首次适应法（把可分配区块循环链接起来，下次就先看下一块能否分配，而不是从头开始匹配）
  • 分配均匀些

页式存储

把用户程序等分为固定大小的页，这样不需要一次性将全部程序导入内存才能运行

• 优点：利用率高，碎片小，分配及管理简单
• 缺点：增加系统开销；可能产生抖动现象

常考：逻辑和物理地址的转换

页表中记录了【页号】和对应的【块号】

【可参考上面的例题】逻辑转为物理地址的思路：逻辑地址由页号和块内地址组成：

1、找到页号和块内地址分别是几位表示：根据页面大小为4K，说明块内地址是用12位表示，也就是A29H，那么页号就是5；

2、根据页号5，找到对应的页帧号（也就是块号）为6，所以选D

找到淘汰页号的思路：

1、从状态位为1的（在内存中）中找

2、从访问位为0的（最近没访问）中找

所以选页号为1的页面

段式存储

组成：段号+段内地址

段的长度也不同，依据代码结构

优点：多道程序共享内存，各段程序修改互不影响

缺点：内存利用率低，内存碎片浪费大

段页式存储

结合段式和页式，先分段再分页

涉及：

• 段表
• 页表
• 逻辑地址：段号、段内页号、页内地址
• 物理地址：块号、页内地址

请求分页（页面置换）

当访问的页面不存在主存时，产生缺页中断

页面置换算法：

• 最佳置换算法：最长时间不被访问
• 先进先出
• 最近最少未使用：为每个页面设置一个访问字段，代表访问时间T
• 最近未用置换算法：为每个页面设置一个访问字段，1或0

快表

小容量的相联存储器，放在cache，速度快。从硬件保证按内存并行查找。

页面置换算法

页面淘汰算法分类

• 最优 OPT(optimal)：只存在理论上的，从整体序列来分析
• 随机算法
• 先进先出FIFO：有可能产生抖动
• 最近最少使用LRU：不会抖动

例题:

答案：B和C

没有使用快表：意味着访问一页，需要访问两次内存（第一次为查询页表）

考试有个潜在规则：读取指令时是算作一次，也就是说虽然横跨0和1页，但是缺页中断次数为1；但是读取操作数时，比如读取A，横跨2和3页，所以缺页中断次数为2

文件管理

索引文件结构

目的：扩充容量

例题：

答案：C和D

文件和树型目录结构

绝对路径/相对路径

空闲存储空间管理

方法分类

• 空闲区表法（空闲文件目录），适用于连续文件结构
• 空闲链表法：每个空闲物理块设置一个指针指向下一个空闲物理块
• 位示图法（每一位对应一个物理块，0，1分别代表空闲和占用）
• 成组链接法：将空闲块分成若干组，每组第一块记录下一组空闲块的块号和空闲块总数

位示图法

例题：

(4195+1)/32=131.125

注意：位置是从0开始算

答案：D和B

数据传输控制方式

方式

• 程序控制方式（需要很多CPU参数，CPU持续发出查询指令）
• 程序中断方式（外设准备好后，主动向CPU发中断请求）
• DMA方式（直接内存存取控制方式，专门的DMA控制器硬件。由主存和外设之间交互，CPU只要在开头介入即可）
• 通道
• 输入输出机

虚设备与SPOOLING技术

微内核操作系统

作业管理

作业调度算法：

• 先来先服务
• 短作业优先
• 相应比高优先，相应比=响应时间/执行时间=（等待+执行时间）/执行时间
• 优先级调度
• 均衡调度

设备管理

相关技术

• 通道技术
• DMA技术
• 缓冲技术
• Spooling技术：使用脱机输入输出操作缓和CPU高速和IO低速的矛盾

磁盘调度算法

分为移臂调度和旋转调度，使得平均寻道时间最少

读取磁盘数据的时间=存道时间+旋转延迟+数据传输时间

移臂调度

• 先来先服务：按照进程请求顺序
• 最短寻道时间优先：磁头最近的磁道优先
• 扫描算法：不仅考虑距离最近，还考虑磁头当前的移动方向
• 单向扫描算法：规则只做单向移动

旋转调度

• 请求的是不同编号的扇区，让首先到达磁头位置下的扇区先
• 请求的是相同编号的扇区，任选一个扇区进行读写