导图社区 23考研操作系统思维导图
这是一篇关于23计算机操作系统的思维导图。该思维导图从计算机系统概述、进程管理、内存管理、文件管理、i/o设备等几个方面进行归纳总结,适用于考研。
编辑于2021-07-24 14:59:23参考吴恩达机器学习教程,参考pytorch官方文档和B站Pytorch入门教程,内部机器学习基本知识,pytorch函数,神经网络搭建方法等
这是一篇关于23计算机操作系统的思维导图。该思维导图从计算机系统概述、进程管理、内存管理、文件管理、i/o设备等几个方面进行归纳总结,适用于考研。
这是一篇关于23考研计算机网络原理的思维导图。计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备,通过通信路线连接起来,在网络操作系统、网络管理软件及网络通信协议的管理和协调下,实现资源共享和信息传递的计算机系统。
社区模板帮助中心,点此进入>>
参考吴恩达机器学习教程,参考pytorch官方文档和B站Pytorch入门教程,内部机器学习基本知识,pytorch函数,神经网络搭建方法等
这是一篇关于23计算机操作系统的思维导图。该思维导图从计算机系统概述、进程管理、内存管理、文件管理、i/o设备等几个方面进行归纳总结,适用于考研。
这是一篇关于23考研计算机网络原理的思维导图。计算机网络是指将地理位置不同的具有独立功能的多台计算机及其外部设备,通过通信路线连接起来,在网络操作系统、网络管理软件及网络通信协议的管理和协调下,实现资源共享和信息传递的计算机系统。
操作系统
1. 计算机系统概述
1. 操作系统概念
计算机自上至下,硬件,操作系统,应用程序,用户(计组是划分为软件系统和硬件系统)
操作系统是计算机系统最基本的软件,管理着各种资源,并组织,调度计算机工作
操作系统的特性
并发
区分并行
共享
互斥访问和(宏观)同时访问
最基本
虚拟
异步
并发引起进程的走走停停
目标和功能
负责管理:2-4章标题
提供接口:命令接口(分/实时交互式和批处理) 程序接口(系统调用,如GUI图形接口)
2. 操作系统发展与分类
手工操作阶段(无操作系统)
批处理阶段(单道)
多道批处理
采用多道程序设计形成多道批处理OS
分时操作系统
切时间片,实现人机交互
实时操作系统
及时性和可靠性,允许紧急情况
6.网络操作系统和分布式7.个人计算机操作系统
3. 操作系统运行环境
运行机制
概念:内核/应用程序,特权指令,管态/目态
内核实现:时钟管理,中断机制,原语,系统数据结构管理
中断和异常
中断,来自CPU外部,和CPU执行指令无关,如时钟中断
异常:源自CPU指令内部的事件
中断处理:详见计组
系统调用
用户可通过陷入(也叫访管/trap)来发起系统调用
4. 操作系统体系结构
大内核(大部分模块由OS管理),微内核(部分模块由OS管理)
2. 进程管理
1. 进程与线程
相关概念
进程映像进程实体
PCB
1.进程描述信息
2.进程控制和管理信息
3.资源分配清单
4.处理机相关信息
注意:进程被调入内存时,系统为之创建一个PCB
程序段
相关数据段
作业
用户给操作系统的任务,可能有一个或多个进程来完成
进程的特征
动态性
动态性是最基本的特征
并发性
独立性
独立接受资源,运行,接受调度的基本单位
异步性
以不可预知的速度向前推进(所以需要引入同步机制)
结构性
进程的状态
五状态
运行
就绪
阻塞
创建
结束
七状态
添加了就绪挂起和阻塞挂起
注意:一个进程从运行态到阻塞态是主动的行为
进程控制
进程创建
申请PCB、分配资源、初始化PCB、(插入就绪队列)
进程终止
正常结束,异常结束,外界干预
进程的阻塞和唤醒
阻塞需要保护现场,后插入相应等待队列唤醒插入就绪队列
进程切换
注意进程切换需要保存上下文
进程通信
共享存储
低级共享(基于数据结构的共享)
高级共享(基于存储区的共享)
操作系统只负责提供存储空间和同步互斥工具
消息传递
进程通过发送消息和接受消息两个原语进行数据交换,无共享空间
直接通信方式
进程之间z直接进行通信,将消息放到缓冲队列上
间接通信方式(信箱通信方式),《计网》中电子邮件系统
管道通信
半双工通信:某一时刻只能单向传输
没写满不能读,没读完不能写,数据只能读一次
线程
引入目的
为了更好的使多道程序并行开发,提高吞吐率和资源利用率
特点
是程序执行最小单元,,是一个轻型实体,线程不拥有系统资源
同一进程的多个线程并发执行,共享进程拥有的全部资源
线程也有就绪、阻塞、运行三种基本状态
实现方式
用户级线程
用户通过线程库设计多线程程序
内核级线程
工作通通由内核完成
多线程模型
多对一模型
效率高但是容易阻塞
一对一模型
并发强但是开销大
多对多模型
集两者长处
2. 处理机调度
调度的层次
作业调度(高级调度)
作业调入内存,建立pcb
内存调度(中级调度)
将暂时不能运行的进程调入外存等待(挂起态)
进程调度(低级调度)
从就绪里选进程分配处理机
调度的时机
不能调度的情况:处理中断/临界区/原子操作
调度的方式
广义 进程调度+进程切换
狭义 就绪队列选出要运行的进程
非剥夺调度方式(非抢占式),批处理使用
剥夺调度方式(抢占式)
调度的准则
cpu利用率
系统吞吐量
周转时间
作业完成时间-作业提交时间
带权周转时间
作业周转时间/作业实际运行时间
等待时间
进程等待时间
进程建立到完成的等待时间
作业等待时间
进程等待时间+在外存后备队列排队时间
注意:衡量一个算法通常只需要考察等待时间
响应时间
提出请求到相应的时间
调度算法
先来先服务FCFS
公平,不会饥饿,非抢占,对长友好,对短不友好
无交互性
短作业优先调度算法(SJF,short iob first)
饥饿,只对短友好,平均等待时间,平均周转时间最少
无交互性
优先级调度算法
1、系统进程优先级>用户 2、前台>后台 3、i/o进程更高
高响应比有限算法
响应比=(等待时间+要求服务时间)/要求服务时间
不会饥饿
无交互性
时间片轮转调度算法
抢占式,时间片到期,不会饥饿
人机交互
多级反馈队列调度算法(融合前几种优点)
抢占,会导致饥饿
抢占式
非抢占式
3. 进程同步
基本概念
临界资源
只允许一个进程使用的资源
进入区
临界区(指访问临界资源的代码)
退出区
剩余区
同步
直接制约关系
互斥
间接制约关系
互斥软件实现均不能让权等待
单标志法
不能空闲让进
双标志法
可能违背忙则等待原则
双标志法后检查
两个进程可能都进不去,不遵循有限等待
Peterson算法
相比较前三种最好,谁最后客气谁就后用,不遵循让权等待,会发生忙等
互斥硬件实现方法(元/低级方法)
中断屏蔽方法
硬件指令方法
TestAndSet指令(TS指令),原子操作
Swap指令
信号量解决同步互斥
Wait()(P操作)和signal(V操作)
整型信号量
不遵循让权等待
记录型信号量(semaphore)
常用,资源数+进程链表
同步(先V后P)
互斥(先P后V)
管程
封装共享资源,自动实现互斥
管程组成:1.名称,2.数据结构说明,3.操作的过程(函数),4.初试化语句
经典同步问题
生产者--消费者问题
特点:多对多,共享资源为n
读者--写者问题
特点:一对多,读写互斥
哲学家就餐问题
特点:多对多,互相干扰
吸烟者问题
特点:一对多,轮流生产
4. 死锁
死锁产生的原因
系统资源的竞争
进程推进顺序非法
必要条件:互斥,不剥夺,请求并保持,循环等待
死锁处理策略
死锁预防
破坏四个必要条件其中一个破坏请求并保持:预先静态资源分配破坏循环等待:顺序资源分配法
死锁避免
银行家算法(基于安全状态)
死锁检测和解除
死锁定理:当且仅当资源分配图不可完全简化时才可能死锁
死锁接触:资源剥夺,撤销进程,进程回退
3. 内存管理
1. 内存管理基本概念
程序变为程序步骤
编译
编译程序将用户源代码编译称若干目标模块
链接
将编译后的目标模块和库函数链接,形成装入模块
装入
将装入模块装入内存
程序链接方式
静态链接
装入时动态链接
运行时动态链接
装入的方式
绝对装入
编译时产生地址(逻辑地址=物理地址);只适用单道程序
可重定位装入
重定位:装入时对目标程序和数据的修改
运行时装入(动态重定位)
需要重定位寄存器支持,适用于虚拟地址
内存保护
cpu设置上下限寄存器
存放用户作业在内存的上下限地址
重定位寄存器(基址寄存器)+界地址寄存器(限长寄存器)
*覆盖与交换**大纲已移除*
覆盖
固定区+若干覆盖区
对用户不透明,增加变成负担,是个单道程序
交换
PCB常驻内存
中级调度技术就是交换技术
分为
文件去(内存)
对换区(外存)
对比
注意:交换技术只在不同进程或者作业之间进行,而覆盖技术用于同一个程序或进程中
2. 连续分配管理方式(分配连续内存)
单一连续分配(独占)
系统区(系统区仅供操作系统使用,通常在低地址部分)
用户区
注: 只能用于单用户,单任务,无外部碎片,有内部碎片,存储器利用率极低
固定分区分配
分区大小相等
缺乏灵活性,适用于控制各个相同对象
大小不等
配有分区说明表
注:有内部碎片,无外部碎片,支持多道程序,每个分区只能装一个作业
动态分区分配
注意:支持多道程序,在进程装入内存时,根据进程大小动态建立分区
无内部碎片,有外部碎片(可用紧凑技术解决)
内存分配的算法
首次适应算法
性能最好,算法开销最小
最佳适应算法
容量递增排序
最坏适应算法(最大适应算法)
容量递减排序
临近适应算法(循环首次适应算法)
3. 非连续分配管理方式
基本分页存储管理方式
术语:进程块称为页/页面,内存块称为页框,外存块称为块地址结构:后面是页内偏移,前面是页号页表:一个进程对应一张页表,每个进程对应一个页表项,页表项由页号和块号组 成,每个页表项长度相同,页号隐含
方式
基本地址变换机构
硬件完成,设置页表寄存器
具有快表的地址变换机构快表:相联存储器(TLB)
注意:做题要看快表是同时查找还是先后查找
多级页表
一级页表(查到地址后,查快表,未命中再查内存);两级页表
注意:n级页表需要n+1次访存,顶级页表不超过一个页面
基本分段存储管理方式
段长不同,多一次检查,段号依然可以隐含(段号+段内偏移)
方便用户编程、信息保护与共享,段内要求连续,段间不要求
段页式管理方式
地址格式:段号+页号+页内偏移量(段内地址经硬件自动拆分为页号+业内偏移量)
一个进程段表只有一个,页表可能有多个
区别
页:对用户不可见,地址空间一维,页面不是按逻辑块分块,难以实现共享,不方便 逻辑管理,有内部碎片(无外部)段:对用户可见,地址空间2维,(纯代码或可重入代码可共享,可修改代码不能共 享),容易实现信息共享,两次判断是否越界段页式: 地址2维注意:做题时无论采用哪种方式,都需要检查页面/段是否越界
4. 虚拟内存
传统存储管理方式特征
一次性
一次性装入后才开始运行
驻留性
一直驻留在内存,直到运行结束
局部性原理
时间局部性
空间局部性
虚拟存储器的特征
多次性
允许作业分多次调入内存
对换性
作业无需常驻内存
虚拟性
逻辑上扩充内存
虚拟内存实现的三种方式
请求分页存储管理
请求分段存储管理
请求段页式存储管理
请求分页管理方式
功能
请求换页功能
页面置换功能
机制
页表机制
页表项:页号+物理块号+状态位P+访问字段A+修改位M+外存地址 (是否已调入)(访问次数)(是否被修改)
页表项比基本页表新增加四个字段修改位写指令才修改,一般只修改快表数据,将快表项删除时才写回慢表
与基本表区别
缺页中断机制
找到页面后检查页面是否在内存,若没在内存,产生缺页中断
缺页中断处理后,需要将目标页面调入内存,有必要时还需换出页面
缺页中断属于内中断,属于内中断的故障,即可能被系统修复的异常
一条指令在执行过程中可能产生多次缺页中断
地址变换机制p184
找到页表项时需要检查页面是否在内存中
若页面不在内存中,需要请求调页
若内存空间不够,还需要换出页面
页面调入内存后,需要修改相应的页表项
注意:为了实现请求分页,系统必须提供一定的硬件支持
页面置换算法
最佳置换算法OPT
理想化算法(无法实现),缺页中断不一定会页面置换
最长时间内不再被访问页面的页面换出(向后找)
先进先出页面置换算法FIFO
算法性能差,会出现Belady异常,物理快增加,缺页故障不减反增
最近最近未使用算法LRU
向前找,性能最接近opt,硬件支持
时钟置换算法CLOCK详见p187
最多两轮循环
改进型时钟置换算法
优先淘汰未被修改的页面,最多四轮扫描
页面分配策略
驻留集
内存中给一个进程分配的物理块的数目
页面分配、置换策略
固定分配局部置换
驻留集大小不变
可变分配全局置换
只要缺页就分配
可变分配局部置换
根据缺页的频率动态增加或者减少进程物理块,如果频率低,就从自己的驻留集中换入换出
调入页面的时机
预调页策略
根据局部性原理,对下次调页进行预测,主要用于进程的首次调入,成功率为50%左右
进程运行时,发现缺页再调入
从何处调入
对换区:采用连续存储方式,速度更快文件区:采用离散存储方式,速度更慢
兑换区足够大:运行将数据从文件区复制到兑换区,只够所有的页面调入,调出都是在内存与兑换区之间进行
兑换区不够大:不会修改的数据每次从文件区调入;会修改的数据调出到兑换区,需要时再从对换区调入
unix方式:第一次使用的文件都从文件区调入;调出的文件都写回对换区,再次使用时从对换区调入
抖动(颠簸)现象
页面频换换入换出的现象,驻留集太小
工作集
再某段时间间隔里,进程实际访问页面的集合,驻留集大小一般不能小于工作集大小
4. 文件管理
1. 文件系统基础
文件系统由: 1有关软件 2被管文件 3数据结构组成
文件定义
硬盘为载体存储在计算机的信息集合,用户IO操作基本单位
文件属性
名称
标识符(供操作系统区分文件)
类型
位置
大小
保护
时间,日期和用户标识
文件基本操作
创建
写
读
重定位(寻址)
删除
截断(删除文件内容,属性不变)
由一系列系统调用构成(creat/delete/read……)
文件逻辑结构
无结构文件(流式文件)
有结构文件(记录式文件)
顺序文件
串结构
与关键字无关,按存入时间先后顺序排列
顺序结构
按关键字顺序排列
注意:可变长记录无法随机存储,定长记录可以 最大缺点:不方便增加/删除记录
索引文件
建立索引表(索引表是定长顺序文件),一个索引项就是一条定常记录,支持随机存取
若索引表按关键字顺序排序,则可支持快速检索
索引顺序文件
前两种结合,分组,每组顺序文件,每组对应一个索引项组内可无序,组间必须有序
直接文件或散列(hash)文件
没有顺序的特性
目录结构
文件控制块(FCB)
实现“按名存储”系统创建一个新文件,就会分配一个FCB并存放到文件目录中,成为目录项,open操作调入目录项FCB。PS:FCB必须连续存放
索引节点
定义:文件信息单独形成的一种数据结构目的:为了减少FCB的大小,进而在查目录时减少I/O次数特点:文件被打开时,磁盘索引结点复制进内存索引结点
文件目录:FCB(目录项)的有序集合
目录结构
单级目录结构
整个系统只建立一张目录表,文件不允许重名
两级目录结构
多用户,文件可重名,不能对文件分类
多级目录结构
便于实现文件分类
绝对路径:从根目录出发进行查询相对路径:的引入减少磁盘访问次数
不便于文件共享
无环图目录结构
实现文件共享
文件共享
静态共享
硬链接(基于索引节点)
索引节点设有计数count,记录链接伤的用户目录项数目
软连接(基于符号链接)
由系统创建一个ink类型的新文件,存放文件路径(快捷方式)
注意:硬链接查找速度比软连接快
动态共享
两个进程同时对同一个文件进行操作
文件保护
口令保护
开销小,口令存在系统不安全
加密保护
异或加密,需解密时间,比口令保护高
访问控制
特点:每个文件和目录增加一个访问控制列表ACL(可以使用复杂的访问方法)规定每个用户名和及所允许的访问类型
复杂访问列表
缺点:长度无法预计,且可能导致复杂的空间管理
精简访问者列表(分组)
拥有者
组
其他(其他用户)
注意:口令和密码都是防止文件被他人窃取,并没有控制用户对文件的访问类型
2. 文件系统实现(文件管理系统)
文件系统层次结构
用户调用接口
创建删除等操作
文件基本操作
文件目录系统
管理文件目录
目录系统
存取控制验证模块
把用户的访问要求与FCB权限信息进行比较
文件保护
逻辑文件系统与文件信息缓冲区
将用户要求的逻辑记录转换成文件逻辑结构块号
逻辑结构
物理文件系统
逻辑块号转化为物理地址
物理地址映射
辅助分配模块
管理辅存空间(外存)
文件实现
设备管理程序模块
与设备直接交互
目录实现
线性列表
哈希表
文件实现—研究文件物理结构
分配方式(管非空闲块)
连续分配(一次访存)
为文件分配连续的磁盘块
优点:速度快,支持随机访问缺点:不好拓展文件大小,会产生碎片(可紧凑,时间代价)
链接分配(n次访存)
隐式链接(默认)
从文件目录项FCB中找到起始块,起始块有指向下一个块的指针
缺点:不支持随机访问,查找效率低
显式链接
将所有指针提取出来制成一张FAT(文件分配表),支持随机存储,一张磁盘有一个FAT
索引分配(m+1次访存)
一个文件对应一个索引块表,通过文件目录项找到索引块表,支持随机存储
优点:可以随机访问,文件易于增删缺点:索引表占用一定的空间,访问数据块前需要先读入索引块
大文件解决方式
链接索引
1->1->1->1........
多层索引
1->n->n²
混合索引
既采用直接地址,又采用单级或者两级分配方式
存储空间管理(管空闲块)
存储空间的划分与初始化
存储空间的划分
文件卷,逻辑卷,逻辑盘
存储空间的初始化
目录区
FCB,空闲表,位示图,超级块等用于文件管理的数据
文件区
文件数据
1.空闲表法
空闲表记录每个连续空间的起始盘块号,盘块数
分配时采用首次适应算法,最佳适应算法等策略
2.空闲链表法
空闲盘块链
以块为单位组成空闲链,分配时从头取下,回收放回链尾
空闲盘区链
以盘区(若干个空闲盘块组成)为单位
3.位示图法
用二进制一位来表示磁盘一个块是否为空,1表示已分配,0表示空闲
计算:盘块号与字号,位号的转换
4.成组链接法 (UNIX)(适用于大型文件系统)
理解即可,空闲表法+空闲链表法,超级块充当链头,比较复杂,基本不考
3. 磁盘组织和管理
磁盘
由磁头,磁道,磁块(扇区)组成
分类
固定头磁盘
活动头磁盘
固定盘磁盘
可换盘磁盘
磁盘时间计算
寻找(道)时间
寻道
旋转延迟时间
旋转找到某一扇区所用的时间,默认取转半圈时间
传输时间
从磁盘读出或写入数据所经历时间,根据转速计算
磁盘调度算法
先来先服务算法
最短寻找时间有优先算法(Shorest Seek Time First)
会产生饥饿
扫描算法/电梯调度算法(SCAN)
不会产生饥饿
look算法解决必须到头才能回来的问题,边移动边看,不一定要移动到头注意:题目的scan算法默认为look算法
循环扫描算法(C-SCAN)
返回时不做任何操作,直接移动到头,c-look同样改进,不用移动到头注意:题目的c-scan算法默认为c-look算法
降低磁盘延迟
交替编号
磁盘相邻的扇区物理上不相邻,让扇区能连续读取
错位命名
让相邻盘面扇区编号错位,在切换盘面时也减少时间
磁盘地址结构的设计
物理地址顺序为: 柱面号+盘面号+扇区号
目的:减少磁头臂的移动,更多的是磁头移动,减少时间消耗
磁盘的管理
磁盘初始化
低级格式化/物理格式化:划分扇区
磁盘分区(c盘D盘E盘)
逻辑格式化:操作系统在磁盘上建立文件系统
引导块
存放自举程序,自举程序初始化CPU、寄存器等,然后启动操作系统
rom存放很小的自举装入程序,完整自举程序存放到启动块中拥有启动分区的磁盘称为启动磁盘或系统磁盘
坏块
简单磁盘:逻辑格式化时在FAT将坏块标记出来
复杂磁盘:磁盘控制器维护一个坏块链,并管理备用扇区
扇区备用:将一些快保留备用,对操作系统透明
5. i/o设备
1. i/o设备管理
i/o设备分类
按使用特性
人机交互类外部设备;存储设备;网络通信设备
按传输速率分
低速设备;中速设备;高速设备
按信息交换单位分类
块设备
可寻址,传输速率高,有结构
字符设备
不可寻址,传输速率低,中断驱动方式,无结构
i/o控制方式详见计组
程序直接控制方式
一次读入一个字,cpu和i/o只能串行工作,先从外存读入cpu,然后才能读入内存
中断驱动方式
中断信号驱动,需要保存CPU上下文,每个字的传输必须经过CPU
DMA方式
一次读入一个或多个块,多个块读入必须连续,不需读入cpu
通道控制方式
通道是小型cpu(只能识别通道指令),将通道程序存入内存(通道没有自己的内存),需要硬件支持,cpu通过i/o通道发送i/o指令,给出通道程序在内存位置,通道cpu自动执行程序,传送结束向cpu发送中断请求,每次可读入一组数据,需硬件支持
i/o子系统层次结构
用户层i/o软件
与i/o操作有关库函数,spooling技术(假脱机技术)
用户
设备独立性(设备无关性)软件
向用户层提供接口
将逻辑设备映射成物理设备以及其他共有操作
设备驱动程序
与硬件直接相关,用于驱动IO设备;以进程存在,向上层用户程序提供一组标准接口
中断处理程序
保存被中断的CPU环境,转入相应中断处理程序
I/O系统操作系统
硬件设备
电子部件:设备控制器(适配器)
机械部件:设备本身
设备控制器
设备控制器通过寄存器与CPU通信;寄存器编制可独立编制(需要寄存器)或者内存映像IO(与内存同编制)
功能
接收识别cpu发出的命令(控制寄存器)
数据交换(数据寄存器,暂存输入输出数据)
向cpu报告设备状态
设备地址识别:通过地址判断要使用的寄存器
组成
与CPU的接口
数据寄存器,状态/控制寄存器
与设备的接口
一个通道对应多个控制器,一个控制器对应多个设备
i/o控制逻辑
识别cpu发出的命令,并向设备发出命令
2. i/o核心子系统
高速磁盘缓冲和缓冲区区别
高速磁盘缓冲
逻辑上是磁盘,物理上是内存块(磁盘驻留),复制磁盘常用数据
缓冲区
单缓冲
双缓冲
循环缓冲
缓冲区呈环形,设置in和out指针
缓冲池
设置三个队列
设备分配与回收
设备分配方式
独占式使用设备
例:打印机,磁带机
分时式共享使用设备
例:磁盘
以spooling方式使用外部设备
以空间换时间,假脱机技术,虚拟设备(用户以为有好多设备)
设备分配数据结构
DCT设备控制表
每个设备有一张,记录设备属性
COCT控制器控制表
CHCT通道控制表
SDT系统设备表
整个系统只有一张,每个目录项包括设备类/标识符/DCT/驱动入口
设备分配步骤1,2,3,
设备分配策略
设备分配原则
考虑设备特性、用户要求和系统配置情况
设备分配安全性
安全分配方式
i/o操作完成前,进程阻塞,缺点cpu和i/o串行工作,优点不会死锁
不安全分配方式
可以连续发出i/o请求,直到请求设备被另一个进程占用才阻塞,会死锁
设备分配算法
静态
独占设备
动态
有可能造成进程死锁,多道程序
设备分配算法
静态:死锁预防(破坏请求和保持)动态:可采用死锁避免
设备独立性的实现
设置一张LUT(逻辑设备表)来实现逻辑名到物理名的映射
方式:①整个设备只有一张LUT,不可重复,适用单用户 ②每个用户有一张LUT,可重复,适用多用户
SPOOLing技术
用户将需要输入输出的数据(经内存的缓冲区)先放到磁盘(输出井),待设备空闲,将数据调入缓冲区然后输出