首页  思维导图  详情

操作系统导图

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





AI智能生成

为你推荐

查看更多



操作系统-CPU

操作系统

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

作者其他创作

大纲/内容

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

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

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

高级调度

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

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

处于挂起状态

换出

换入

引入原因

中级调度

就绪队列中分配处理机

原则

抢占式

非抢占式

方式

进程调度

低级调度

提交状态

后备状态

执行状态

完成状态

作业状态

只有低级调度是必须的

处理机调度的层次

一级

二级

三级

调度队列模型

系统吞吐量

CPU利用率

各类资源的平衡利用

面向系统的准则

周转时间短

相应时间快

截止时间的保证

稳定性

面向用户的准则

易于实现

执行开销比

算法的性能准则

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

调度队列模型和调度准则

span style=\"font-size: inherit;\

特点，优缺点

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

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

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

特点

抢占式优先级调度算法

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

非抢占式优先级调度算法

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

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

确定静态优先级的依据

静态优先级

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

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

确定动态优先级的依据

动态优先级

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

高优先权优先调度算法

响应比

最高相应比优先调度算法

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

时间片过大

时间片过小

设置多个队列

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

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

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

多级反馈队列调度算法

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

调度算法

提供必要的信息

系统处理能力强

采用抢占式调度机制

具有快速切换机制

实现实时调度的基本条件

非抢占式轮状调度算法

非抢占式优先调度算法

非抢占式调度算法

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

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

抢占式调度算法

实时调度算法的分类

最早截止时间优先

松弛度

抢占式的

最低松弛度优先

常用的几种实时调度算法

实时调度

可剥夺资源与不可剥夺

永久性和临时性

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

竞争资源

进程推进顺序不当

产生死锁的原因

死锁

互斥条件

请求和保持条件

不可剥夺条件

环路等待条件

产生死锁的必要条件

是设备本身固有的属性

不可修改

互斥？

静态资源分配法

一次分配所用的全部资源

资源利用率低，进程延迟

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

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

摒弃“不可剥夺”

有序资源分配

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

限制了用户编程

限制了设备的增加

摒弃“环路等待”

预防死锁的方法

预防死锁

系统安全状态

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

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

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

利用银行家算法避免死锁

避免死锁

用圆圈代表进程

方框表示一类资源

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

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

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

资源分配图

不可完全简化即死锁

完全简化即形成孤立结点

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

检测

死锁的检测

资源剥夺法

撤销进程法

死锁的解除

检测死锁和解除

不考虑此问题

处理死锁的基本方法

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

处理机调度与死锁

原子数据

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

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

基本数据项

由若干基本数据项组成

组合数据项

数据项

一组相关数据项的集合

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

记录

对象

有结构文件

无结构文件

一个对象集

文件类型

文件长度

文件的物理位置

文件的建立时间

属性

文件

文件、记录和数据项

按用途分类

按文件中数据的形式分类

存取控制属性

类型

分支主题

磁盘存储空间

对象及其属性

对文件存储空间的管理

对文件目录的管理

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

对文件的读和写的管理

文件的共享与保护

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

命令接口

程序接口

文件系统的接口

文件系统模型

文件类型和文件系统模型

创建文件

删除文件

读文件

写文件

截断文件

设置文件的读／写位置

文件操作

文件和文件系统

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

记录是可以定长或变长的

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

串结构

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

顺序结构

结构

顺序文件

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

索引表

索引文件

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

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

索引顺序文件

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

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

直接文件或散列文件

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

只能以穷举搜索的方式

管理简单

文件逻辑结构的类型

文件的逻辑结构

顺序访问容易

顺序访问速度快

优点

连续的存储空间

事先知道文件的长度

缺点

连续分配

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

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

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

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

隐式链接

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

显式链接

链接分配

单级索引

多级索引

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

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

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

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

混合索引

索引分配

外存分配方式

文件控制块和索引结点

单级目录结构

两级目录结构

目录结构

路径名

当前目录

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

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

增加和删除目录

多级目录结构

线性检索法

Hash方法

目录查询技术

目录管理

存储空间的分配与回收

和动态分配类似

空闲表法

空闲盘块链

空闲盘区链

空闲链表法

位示图

令值变成1

盘块的分配

令值变成0

盘块的回收

位示图法

空闲盘块的组织

以栈的形式体现

执行空闲盘块数加1操作

执行空闲盘块数减1操作

空闲盘块的分配与回收

成组链接法

文件存储空间的管理

利用符号链实现文件共享

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

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

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

第一级容错技术SFT-Ⅰ

磁盘镜像

磁盘双工

第二级容错技术SFT-Ⅱ

磁盘容错技术

定义

恢复

事务

检查点

并发控制

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

数据一致性控制

文件共享与文件保护

文件管理

寄存器

高速缓存

主存储器

磁盘缓存

固定磁盘

可移动存储介质

存储器的层次结构

主存

辅存

CPU寄存器

目标模块采用绝对地址

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

适用于单道环境

绝对装入

在程序装入的时候装入

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

程序需要连续空间

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

可重定位装入

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

可以在内存之中移动

可以实现虚拟存储

动态运行时装入

装入

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

静态链接

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

便于修改和更新

便于实现目标模块的共享

装入时动态链接

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

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

运行时动态链接

链接

装入和链接

单一连续分配

分区使用表

内存利用与回收

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

限制了活跃进程的最大数

碎片过多

扩充和贡献困难

固定分区分配

首次适应算法

循环首次适应算法

最佳适应算法

最坏适应算法

算法

空闲分区表

空闲分区链

管理空闲分区

分区回收

分区分配

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

动态分区分配

重定位寄存器

地址变换机构

目标程序

动态重定位分配

伙伴算法

内存分配

内存回收

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

伙伴系统

以进程为单位

以页或段为单位

交换

连续分配方式

主存中为块

进程的逻辑结构中为页

存储空间

页表

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

页表存放

即在第几页

页号

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

总的大小为页面大小，如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系统

ISA和EISA总线

VESA

PCI

局部总线

总线系统

I/O设备

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

没有中断机构

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

程序I/O方式

加入中断

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

中断驱动I/O控制方式

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

有关控制信息

设备的状态

命令／状态寄存器CR

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

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

内存地址寄存器MAR

存储数据

从设备到内存

从内存到设备

数据寄存器DR

本次CPU要读或写的字节数

数据计数器DC

设置MAR和DC初值

启动DMA传送命令

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

存储器地址增一

字节数寄存器减一

工作过程

DMA

传输单位是数据块

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

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

DMA I/O控制方式

进一步减少CPU的干预

对一组数据块的相关操作

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

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

操作码

内存地址

计数

通道程序结束位P

记录结束标志R

通道程序

I/O通道控制方式

I/O控制方式

单缓冲

双缓冲

循环缓冲

缓冲

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

队列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设备

处理过程

设备驱动程序

进程上下文切换

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

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

主要工作

唤醒被阻塞的程序

保护被中断进程的CPU环境

转入相应的设备处理现场

中断处理

恢复被中断进程的现场

工作流程

中断处理程序

硬件

I/O系统的层次

设备分配

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

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

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

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

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

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

共享打印机

提高I/O速度

将独占设备改造共享设备

实现了虚拟设备功能

SPOOLing技术

数据的组织和格式

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

固定头磁盘

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

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

移动头磁盘

磁盘类型

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

Ts=m×n+s

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

寻道时间

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

旋转延迟时间

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

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

传输时间

总时间

磁盘访问时间

磁盘性能简介

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

先来先服务FCFS

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

可能产生“饥饿”现象

最短寻道时间优先SSTF

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

扫描(SCAN)算法

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

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

循环扫描(CSCAN)算法

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

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

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

N-Step-SCAN

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

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

FSCAN调度算法

磁盘调度

磁盘存储器管理

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

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

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

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

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

形式

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

数据交付

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

数据量小，节省了时间

指针交付

数据交付方式

磁盘高速缓存

置换算法

UNIX方法

MS-DOS方法

周期性地写回磁盘

提前读

延迟写

优化物理块的分布

虚拟盘

提高速度的方法

设备管理

程序的顺序执行及其特征

前趋图

程序的并发执行及其特征

结构性

动态性

并发性

独立性

异步性

就绪态

执行态

阻塞态

基本状态

静止就绪

静止阻塞

进程的挂起

创建状态

终止状态

考虑全局

转换

状态

进程的特征与状态

进程标识信息

处理机状态信息

进程调度和状态信息

进程控制信息

链接方式

索引方式

组织方式

进程控制块

进程的基本概念

进程图

原语

前置概念

引起事件

创建一个空闲PCB结构

为新进程分配资源

初始化新的PCB结构

将PCB结构插入相应的队列

创建原语

进程的创建

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

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

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

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

撤销PCB

终止原语

进程的终止

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

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

保存进程的现场到PCB结构

将该进程PCB插入等待队列

转进程调度程序

阻塞原语

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

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

转进程调度或返回

唤醒原语

进程的阻塞与唤醒

挂起引起事件

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

运行状态

就绪状态

等待状态

取PCB的状态

挂起原语

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

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

有需要转进程调度

激活原语

进程的挂起与激活

进程控制

相互协作关系

资源共享关系

进程制约关系

临界资源

互斥

临界区