首页  思维导图  详情

操作系统导图

2023-04-18 12:51:35   2  举报





AI智能生成

操作系统给思维导图：可展开

操作系统复习

操作系统归纳

操作系统概论

操作系统

作者其他创作

大纲/内容

处理机调度与死锁

处理机调度的层次

高级调度

决定后备队列中调入主存的作业

多少作业：取决于多道程序度

接纳哪些作业：取决于调度算法

中级调度

闪存中把暂时不运行的换出外存

决定那些进程被允许参与竞争CPU

处于挂起状态

引入原因

换出

换入

低级调度

就绪队列中分配处理机

进程调度

方式

抢占式

原则

非抢占式

作业状态

提交状态

后备状态

执行状态

完成状态

只有低级调度是必须的

调度队列模型和调度准则

调度队列模型

一级

二级

三级

选择调度方式和调度算法的若干准则

面向系统的准则

系统吞吐量

CPU利用率

各类资源的平衡利用

面向用户的准则

周转时间短

相应时间快

截止时间的保证

稳定性

算法的性能准则

易于实现

执行开销比

调度算法

先来先服务和短作业（进程）优先调度算法FCFS

特点，优缺点

算法简单，但效率；对长作业比较有利，但对短作业不利(相对SJF和高响应比)；有利于CPU繁忙型作业,而不利于I/O繁忙型作业

最短剩余时间优先调度算法SJF

特点，优缺点

缺点是：该算法对长作业不利,SJF调度算法中长作业的周转时间会增加。更严重的是，若有一长作业进入此系统的后备队列，由于调度程序总是有限调度那些短作业,将导致长作业长期不被调度(产生饥饿现象)

高优先权优先调度算法

抢占式优先级调度算法

特点

当一个进程正在处理机上运行时，若有某个优先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给优先级更高的进程

非抢占式优先级调度算法

特点

当一个进程正在处理机上运行时，即使有某个优先级更高的进程进入队列，仍让正在运行的进程继续运行，直到任务完成或者有等待事件，才把处理机分配给就绪队列中优先级最高的进程

优先级 |||根据进程创建后其优先级是否可以改变

静态优先级

特点

优先级在创建时确定，且在进程的整个运行期间保持不变

确定静态优先级的依据

进程类型、进程对资源的要求、用户要求

动态优先级

特点

在进程运行过程中，根据进程情况的变化动态调整优先级

确定动态优先级的依据

进程占有CPU时间的长短、就绪进程等待CPU时间长短

最高相应比优先调度算法

响应比

基于时间片的轮转调度算法

最开始的在队首，执行完时间片到队尾

时间片过大

时间片过小

多级反馈队列调度算法

设置多个队列

优先级越高，执行时间越短

在第一个队列执行完以后再执行第二个队列

执行过的进程放到最后一个队列的末尾

实时调度

实现实时调度的基本条件

提供必要的信息

系统处理能力强

采用抢占式调度机制

具有快速切换机制

实时调度算法的分类

非抢占式调度算法

非抢占式轮状调度算法

非抢占式优先调度算法

抢占式调度算法

基于时钟中断的抢占式优先权调度算法

立即抢占的优先权调度算法

常用的几种实时调度算法

最早截止时间优先

最低松弛度优先

松弛度

抢占式的

产生死锁的原因和必要条件

产生死锁的原因

竞争资源

可剥夺资源与不可剥夺

永久性和临时性

不可剥夺、永久性和临时性资源可造成死锁

进程推进顺序不当

死锁

产生死锁的必要条件

互斥条件

请求和保持条件

不可剥夺条件

环路等待条件

处理死锁的基本方法

预防死锁

预防死锁的方法

互斥？

是设备本身固有的属性

不可修改

请求和保持条件

静态资源分配法

一次分配所用的全部资源

资源利用率低，进程延迟

摒弃“不可剥夺”

已有该资源的进程要求释放资源

只可用于状态可以保存和恢复的资源

摒弃“环路等待”

有序资源分配

资源利用率提高（还是存在浪费）

限制了用户编程

限制了设备的增加

避免死锁

系统安全状态

利用银行家算法避免死锁

1. 通过对资源分配进行分析

2. 如果有任何一个进程的资源需求满足现有资源储备量，则可分配，并释放占用的资源重复1

如果所有进程可全部被释放，则处于安全状态

检测死锁和解除

死锁的检测

资源分配图

用圆圈代表进程

方框表示一类资源

方框中一个点代表一类资源的一个实例

从进程到资源表示进程请求一个该类资源

从资源指向进程表示有一个资源分配给该进程

检测

不可完全简化即死锁

完全简化即形成孤立结点

可以获取到想要的资源则移除请求边和分配边

死锁的解除

资源剥夺法

撤销进程法

不考虑此问题

文件管理

文件和文件系统

文件、记录和数据项

数据项

基本数据项

原子数据

数据组织中可以命名的最小逻辑数据单位

描述对象某种属性的字符集

组合数据项

由若干基本数据项组成

记录

一组相关数据项的集合

描述一个对象在某方面的属性

对象

文件

有结构文件

无结构文件

一个对象集

属性

文件类型

文件长度

文件的物理位置

文件的建立时间

文件类型和文件系统模型

类型

按用途分类

按文件中数据的形式分类

存取控制属性

文件系统模型

分支主题

对象及其属性

文件

磁盘存储空间

对对象操纵和管理的软件集合

对文件存储空间的管理

对文件目录的管理

用于将文件的逻辑地址转换为物理地址的机制

对文件的读和写的管理

文件的共享与保护

文件系统的接口

命令接口

程序接口

文件操作

创建文件

删除文件

读文件

写文件

截断文件

设置文件的读／写位置

文件的逻辑结构

文件逻辑结构的类型

有结构文件

顺序文件

文件中的记录一个接一个地顺序排列

记录是可以定长或变长的

结构

串结构

记录之间的顺序与关键字无关

顺序结构

文件中的所有记录按关键字顺序排列

索引文件

变长记录文件只能顺序查找

索引表

索引顺序文件

索引顺序文件将顺序文件中的所有记录分为若干个组

在索引表中为每组中的第一个记录建立一个索引项

直接文件或散列文件

给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址

这种映射结构不同于顺序文件或索引文件，没有顺序的特性

无结构文件

无结构文件将数据按顺序组织成记录并积累保存，它是有序相关信息项的集合，以字节(Byte)为单位

只能以穷举搜索的方式

管理简单

外存分配方式

连续分配

优点

顺序访问容易

顺序访问速度快

缺点

连续的存储空间

事先知道文件的长度

链接分配

隐式链接

一个串联文件结构是按顺序由串联的块组成

文件的信息存储在若干个块之中

最后一个块为链接字，指出后续地址

链首指针存放在文件目录之中

显式链接

是指把用于链接文件各物理块的指针，显示地存放在内存的一张连接表中。该表在整个磁盘就一张。此表就是文件分配表

索引分配

单级索引

多级索引

混合索引

索引结点中可设置10个直接地址项

文件较小的时候可以直接从索引结点中读出该文件的全部盘块号

对于较大的文件，将直接地址项变为间接地址

多次间接地址（开始增加地址项来提供间接地址）

目录管理

文件控制块和索引结点

目录结构

单级目录结构

两级目录结构

多级目录结构

目录结构

路径名

当前目录

增加和删除目录

目录文件不为空时，不可删除

或删除目录文件中所有其他文件

目录查询技术

线性检索法

Hash方法

文件存储空间的管理

空闲表法

存储空间的分配与回收

和动态分配类似

空闲链表法

空闲盘块链

空闲盘区链

位示图法

位示图

盘块的分配

令值变成1

盘块的回收

令值变成0

成组链接法

空闲盘块的组织

以栈的形式体现

空闲盘块的分配与回收

执行空闲盘块数加1操作

执行空闲盘块数减1操作

文件共享与文件保护

利用符号链实现文件共享

磁盘容错技术

第一级容错技术SFT-Ⅰ

双份目录和双份文件分配表

备份一份文件目录和文件分配表

热修复重定向和写后读校验

第二级容错技术SFT-Ⅱ

磁盘镜像

磁盘双工

数据一致性控制

事务

定义

记录

恢复

检查点

并发控制

重复数据的数据一致性问题

内存管理

存储器的层次结构

寄存器

高速缓存

主存储器

磁盘缓存

固定磁盘

可移动存储介质

装入和链接

装入

绝对装入

目标模块采用绝对地址

逻辑地址和实际地址完全相同

适用于单道环境

可重定位装入

在程序装入的时候装入

存在地址变换，但是是直接找的当前合适的内存位置

程序需要连续空间

不存在在程序执行的过程中在内存移动

动态运行时装入

地址转换在程序需要真正执行时才进行

可以在内存之中移动

可以实现虚拟存储

链接

静态链接

在程序运行之前，将各目标模块以及它们需要的库函数链接成一个完整的转入模块

装入时动态链接

在装入的时候边装入边链接

便于修改和更新

便于实现目标模块的共享

运行时动态链接

当程序需要的时候采取链接

节约内存空间、加快装入过程

连续分配方式

单一连续分配

固定分区分配

分区使用表

内存利用与回收

缺点

规定了分区大小，大程序无法装入

限制了活跃进程的最大数

碎片过多

扩充和贡献困难

动态分区分配

算法

首次适应算法

循环首次适应算法

最佳适应算法

最坏适应算法

管理空闲分区

空闲分区表

空闲分区链

分区回收

分区分配

没有程序数目和大小的限制但是会产生过多的碎片

动态重定位分配

重定位寄存器

地址变换机构

目标程序

伙伴系统

伙伴算法

内存分配

内存回收

在进程释放存储空间时，寻找伙伴合并，可以做到类似递归进行，知道找不到可以合并的伙伴为止

交换

以进程为单位

以页或段为单位

基本分页存储管理方式

存储空间

主存中为块

进程的逻辑结构中为页

页面与页表

页表存放

页表

分支主题

为记录页面在内存中对应的物理块

页表

逻辑地址构成

页号

即在第几页

页内位移

即距离页面里面第一个地址的距离

总的大小为页面大小，如1KB的页面，会有2的10次方的地址

逻辑地址从0开始

为解决连续分配方式存在的碎片

地址变换机构

分页逻辑地址

映射

快表

两级和多级页表

每多一次页表会多一次对主存的访问

信息共享

可重入代码

基本分段存储管理方式

逻辑地址结构

段表

与分页的区别

信息共享

大小

逻辑地址结构

段号

通过段号可以知道最多允许有多少分段

段内地址

可以知道每段的最大长度

不定

段页式存储管理方式

逻辑地址结构

先分段再分段

所以会先访问段表再访问页表

最后访问信息

段表和页表

虚拟存储器

原理

请求调入

置换

局部性原理

程序中少量分支和过程调用大都是顺序执行

过程调用深度有限，

存在着许多循环

数组等数据结构

体现

时间局部性

空间局部性

物质基础

相当数量的外存

一定容量的内存

地址变换机构

实现方法

请求分页存储管理方式

内存分配和分配算法

进程需要的最小物理块数

执行一条指令所涉及的页面数确定

单地址指令

直接寻址

间接寻址

功能较强时

进程的物理块数是固定还是可变

固定分配局部置换

可变分配全局置换

可变分配局部置换

按什么原则为进程分配物理块数

平均分配算法

按比例分配算法

按优先级分配算法

实现方案

局部范围内

页面置换算法

最佳置换算法

将来最长时间不会使用

仅具有理论意义

分支主题

先进先出算法

选择调入主存时间最长的页面予以淘汰

最近最久未使用置换算法

选择最近一段时间内最长时间没有被访问过的页面予以淘汰

实现

基于寄存器的方法

配置一个n位寄存器，在进程访问页面的时候最左置1

每过一段时间则计数器右移1位

最小数值的寄存器即最近最久未使用的页面

基于栈的方法

栈顶存放最近使用过的页面

时钟置换算法

将页面设置成循环队列

首次调入内存，置访问位置1

被访问置访问位置1

缺页中断的时候

访问为0则淘汰

不为0则置为0

接上次判定界面位置

改进：访问位和修改位分开考虑

有四种情况

先寻找访问位和修改位都为0的页面淘汰

没有则再寻找访问页为0，修改位为1的淘汰，并将访问位设置为0

没有重复一操作

其他置换算法

性能分析

有效访问时间

访问存储器所需时间的平均值

在快表中，则需要访问一次主存

分支主题

不在内存，则要缺页中断时间

缺页中断时间

界面传送时间

进程重新执行时间

仅考虑页面传送时间

影响缺页率的因素

分配给进程的物理块数

页面本身大小

程序编制方法

页面置换算法

抖动现象

全局抖动

局部抖动

产生原因

进程分配物理块太少

置换算法选择不当

全局置换使抖动传播

预防与解除

采用局部置换策略

增加分配给相应进程的物理块

挂起进程

页面大小的选择

有个最佳界面大小可以选择

每个页表项需e个字节

内存大小为m

进程的平均长度为s

计算开销碎片项和页表项的总和（pm/2s + me/p）求最小值

p=2es的算术平方根

调页策略

何时

预调页策略

请求调页策略

何处

文件区

存放文件

离散分配

对换区

存放对换页面

连续分配

磁盘I/O较高

情况

对换区空间足够

对换区空间不够

将进程中可能被修改的调入对换区

UNIX方式

全部存放在文件区

运行过调出的放于对换区

存在页面共享

支持机构

页表

扩充的页表

缺页中断机构

缺页中断

中断过程

地址变换机构

类似于分页存储管理

进行缺页中断处理

请求分段存储管理方式

请求调段

分段置换

支持结构

段表

缺段中断机构

类似缺页中断

内存管理

段的置换

有空间则直接调入

没有就检查空闲区之后是否满足

再不符合则淘汰若干段

地址变换机构

动态地址变换

分段共享

实现

为了实现分段共享，可在系统中设置一张共享段表，所有共享分段都在其中占有一表项

增加共享进程计数

存取控制字段

共享段在不同进程中有不同的段号

分支主题

分配

对于第一个请求使用该段的进程，系统为该共享段分配一个内存区，在将共享段调入

同时将该区的始地址填入请求进程的段表

在共享段表中增加一项，填写有关数据将count置1

填入相关的数据结构

回收

释放该进程段，将count减一

如果变为0则需要系统回收共享段的物理内存及有关表项

分段保护

越界保护

用段表长度与逻辑地址中的段号比较

段长与逻辑地址中的段内位移比较

存取方式检查

本段的访问方式

环保护结构

低编号环具有高优先权

原则

一个程序可以访问在相同的环或者较低环中的数据

一个程序可以调用驻留在相同环或较高环中的服务

特征

多次性

对换性

虚拟性

设备管理

I/O设备

I/O设备的类型

传输速率

信息交换单位

共享属性

拓展

设备与控制器之间的接口

数据信号线

状态信号线

控制信号线

设备控制器

功能

组成

I／O设备通道

类型

字节多路

以字节交换方式工作

含有若干个非分配型子通道

每个子通道连接一台I/O设备

按时间片轮转方式共享主通道

用于中低速设备

数组选择

以数组方式进行数据传送

只有一个分配型子通道

不允许其他设备使用该通道

数组多路

字节多路和数组选择的综合

功能

特殊的处理机，具有执行I/O指令的能力

通过执行通道程序来控制I/O操作

指令单一

通道没有自己的内存

多通路I/O系统

存储器到设备之间有多通道

提高运输速率

分支主题

总线系统

ISA和EISA总线

局部总线

VESA

PCI

I/O控制方式

程序I/O方式

CPU要不断地测试I/O设备的状态

没有中断机构

让I/O设备无法向CPU报告已完成一个字符的输入操作（是CPU没有办法终止）

中断驱动I/O控制方式

加入中断

在输完一个数据时，需要CPU花费极短时间去做中断处理

DMA I/O控制方式

DMA

分支主题

组成

命令／状态寄存器CR

接收从CPU发来的I/O命令

有关控制信息

设备的状态

内存地址寄存器MAR

输入时，存放把数据从设备传送到内存的起始目标地址

输出时，存放由内存到设备的内存源地址

数据寄存器DR

存储数据

从设备到内存

从内存到设备

数据计数器DC

本次CPU要读或写的字节数

工作过程

设置MAR和DC初值

启动DMA传送命令

挪用存储器周期传送数据字

存储器地址增一

字节数寄存器减一

特征

传输单位是数据块

从设备和内存之间直接交互

尽在数据块的传送开始和结束时，才需要CPU干预，在控制器的控制下完成传送

I/O通道控制方式

进一步减少CPU的干预

对一组数据块的相关操作

通道程序

向I/O通道发送一条I/O指令，以给出其所要执行的通道程序首地址和要访问的设备

通道执行通道程序即可完成CPU的I/O任务

组成

操作码

内存地址

计数

通道程序结束位P

记录结束标志R

缓冲管理

缓冲

单缓冲

双缓冲

循环缓冲

缓冲池

既可以用于输入又可用于输出

空缓冲区

队列emq

装满输入数据的缓冲区

队列inq

装满输出数据的缓冲区

队列outq

设备分配

设备独立性

逻辑设备

物理设备

设备独立性软件

执行所有设备的公有操作

对独立设备的分配与回收

映射

对设备进行保护，禁止用户直接访问设备

缓冲管理

差错控制

向用户层(或文件层)软件提供统一接口

映射

好处

数据结构

设备控制表

控制器控制表

通道控制表

系统设备表

考虑因素

设备的固有属性

设备分配算法

设备分配中的安全性

分配程序

基本的设备分配程序

设备分配程序的改进

设备分配

I/O软件的目标

与具体设备无关

统一命名

对错误的处理

缓冲技术

设备的分配和释放

I/O控制方式

I/O系统的层次

用户空间的软件

与设备无关的软件

设备驱动程序

功能

接受由I/O进程发过来的命令和参数，并将命令中的抽象要求转化为具体要求

如磁盘号转换为磁盘的盘面、磁道号及扇区号

检查用户I/O请求的合法性

了解I/O设备的状态

传递有关参数

设置设备的工作方式

发出I/O命令

如果设备空闲，便立即启动I/O设备去完成指定的操作

如果设备忙碌，则请求块挂在设备队列上等待

及时响应由控制器或通道发来的中断请求并进行处理

对于设置有通道的计算机系统，还可以根据用户的I/O请求，构成通道程序

设备处理方式

为每一类设备设置一个进程，专门用于执行这类设备的I/O操作

在系统中设置的一个I/O进程，专门用于执行系统中所有各类设备的I/O操作

不设置专门的设备处理进程，而只为各类设备设置相应的设备处理程序

特点

在I/O的进程与设备控制器之间的一个通信和转换程序

与I/O特性相关，不同类型的设备应该配置不同的驱动程序

与硬件相关，因此需要汇编语言

驱动程序与I/O设备所采用的控制方式紧密相关

处理过程

将抽象要求转换为具体要求

检查I/O请求的合法性

读出和检查设备的状态

传送必要的参数

工作方式的设置

启动I/O设备

中断处理程序

主要工作

进程上下文切换

对处理中断信号源进行测试

读取设备状态和修改进程状态

工作流程

唤醒被阻塞的程序

保护被中断进程的CPU环境

转入相应的设备处理现场

中断处理

恢复被中断进程的现场

硬件

SPOOLing技术

为了缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、脱机输出技术

把低速I/O设备上的数据传送到高速磁盘上

分支主题

实现

利用其中的一道程序，来模拟脱机输入时的外围控制机功

再用另一道程序来模拟脱机输出时外围控制机的功能

共享打印机

将输出进程在输出井中申请一个空闲磁盘块区，并将打印的数据送入其中

输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入，再将该表挂到请求打印队列

特点

提高I/O速度

将独占设备改造共享设备

实现了虚拟设备功能

磁盘存储器管理

磁盘性能简介

数据的组织和格式

磁盘类型

固定头磁盘

在每条磁道上都有一读/写磁头

移动头磁盘

每一个盘面仅配有一个磁头

移动磁头仅能以串行方式读/写

磁盘访问时间

寻道时间

启动磁臂的时间s与磁头移动n条磁道所花费的时间之和

Ts=m×n+s

m是一常数，与磁盘驱动器的速度有关

旋转延迟时间

指定扇区移动到磁头下面所经历的时间

传输时间

Tt的大小与每次所读/写的字节数b和旋转速度有关

分支主题

r为磁盘每秒钟的转数；N为一条磁道上的字节数

总时间

分支主题

磁盘调度

先来先服务FCFS

按进程请求访问磁盘的先后次序进行调度

最短寻道时间优先SSTF

选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象

可能产生“饥饿”现象

扫描(SCAN)算法

当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象

循环扫描(CSCAN)算法

磁头移到最外磁道时立即又返回到最里磁道

消除了对两端磁道请求的不公平

N-Step-SCAN

N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列

每处理一个队列时又是按SCAN算法

当正在处理某子队列时，如果又出现新的磁盘I/O请求，便将新请求进程放入其他队列

FSCAN调度算法

一个是由当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理

将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理

磁盘高速缓存

逻辑上属于磁盘，而物理上是驻留在内存中的盘块

形式

在内存中开辟一个单独的存储空间来作为磁盘高速缓存

把所有未利用的内存空间变成一个缓冲池，供请求分页系统和磁盘I/O时共享

当磁盘I/O的频繁程度较高时，该缓冲池可能包含更多的内存空间

而在应用程序运行得较多时，该缓冲池可能只剩下较少的内存空间

数据交付方式

数据交付

直接将高速缓存中的数据，传送到请求者进程的内存工作区

指针交付

只将指向高速缓存中某区域的指针，交付给请求者进程

数据量小，节省了时间

置换算法

周期性地写回磁盘

UNIX方法

MS-DOS方法

提高速度的方法

提前读

延迟写

优化物理块的分布

虚拟盘

进程管理

进程的基本概念

程序的顺序执行及其特征

前趋图

程序的并发执行及其特征

进程的特征与状态

特征

结构性

动态性

并发性

独立性

异步性

状态

基本状态

就绪态

执行态

阻塞态

进程的挂起

静止就绪

静止阻塞

考虑全局

创建状态

终止状态

转换

进程控制块

进程标识信息

处理机状态信息

进程调度和状态信息

进程控制信息

组织方式

链接方式

索引方式

进程控制

前置概念

进程图

原语

进程的创建

引起事件

创建原语

创建一个空闲PCB结构

为新进程分配资源

初始化新的PCB结构

将PCB结构插入相应的队列

进程的终止

引起事件

终止原语

根据进程标识符，找到相应的PCB，读取状态

如果正处于进行状态，则停止进程的执行

如果有子进程，终止子进程

归还资源到父进程或者系统

撤销PCB

进程的阻塞与唤醒

引起事件

阻塞原语

根据当前执行进程的标识符找到PCB

停止执行进程，改状态为阻塞

保存进程的现场到PCB结构

将该进程PCB插入等待队列

转进程调度程序

唤醒原语

从等待队列中取出相应进程

改程序状态为就绪，将进程插入就绪队列

转进程调度或返回

进程的挂起与激活

挂起引起事件

挂起原语

根据被挂起进程的标识符，找到PCB

取PCB的状态

运行状态

就绪状态

等待状态

激活原语

系统将外存上被挂起的进程换入内存

将进程状态由挂起改为激活后的状态

有需要转进程调度

进程同步

进程同步的基本概念

进程制约关系

相互协作关系

资源共享关系

临界资源与互斥

临界资源

互斥

临界区