操作系统-1-计算机系统概述
2021-09-17 15:57:56 2 举报
AI智能生成
408考研操作系统思维导图
作者其他创作
大纲/内容
操作系统-1-计算机系统概述
基本概念
概念
计算机系统自下而上可分为:硬件→操作系统→应用程序→用户
操作系统管理计算机资源(软件+硬件),成为硬件与用户之间的媒介
操作系统管理软硬件资源、组织和调度资源分配、为用户和软件提供方案接口
操作系统的特性
并发(宏观):同一时间间隔内同时存在多个运行的程序(引入进程是为了能够使程序并发执行) 【注意区分并发和并行。 记住并行是指同时进行(微观上也是同时进行的)。】
共享:资源供多个并发的程序共同使用
互斥性共享:一段时间内只允许一个进程访问资源(称为临界资源或独占资源)
同时访问方式:一段时间允许多个进程“同时访问”(宏观上)
虚拟:把一个物理上的实体变为若干个逻辑上的对应物(虚拟处理器、虚拟内存)【时分复用:处理器; 空分复用:虚拟存储器】
异步:因程序并发执行,而资源有限导致程序走走停停。以不可预知的速度运行。称为进程的异步性
操作系统的目标:处理机管理、存储器管理、文件管理、设备管理
用户接口
命令接口(操作和控制作业)
联机控制(交互式):适应于分时和实时的系统,类似于解释型语言,一条一条的输入和执行
脱机控制(批处理):一次给一组命令,类似于编译型语言
程序接口(面向用户):由一组系统调用命令(广义指令)组成,例如常用的图形用户界面GUI
操作系统的发展
手工阶段(此阶段无OS):全程人工干预,用户独占全机,CPU需要手工操作
批处理阶段(有OS,但不能人机交互)
单道批处理:内存中只有一道作业
多道批处理:多个程序同时进入内存,CPU交替进行。(宏观并行,微观串行)
分时操作系统(人机交互):处理器时间分片轮转,实现人机交互系统,能接收并响应
实时操作系统:抢占。某个动作必须在规定的时刻发生。及时和可靠。
操作系统的运行
运行机制
1、为了系统的安全性把系统分为 用户态(目态) 和 核心态(管态、内核态)
2、特权指令是核心态才能使用的指令,也是分态的原因。不让用户随意使用
内核:时钟管理、中断、原语(不可分割)、系统控制(调用)
中断和异常(硬件)
特点:要保存PC和PSW
系统只能通过中断或异常进入核心态
中断(外中断):外设请求,人为干预
异常(内中断)也叫陷入(trap):CPU内部事件,不能被屏蔽,一旦发生要立即执行。 此处要和组成原理的(外)中断区分
系统调用
在用户程序中凡是与资源有关的操作,必须通过系统调用方式向OS发出请求,并由OS代为完成
系统调用要用到特权指令,需要进入内核态。由用户程序执行陷入指令(访管指令、trap指令)
其他
核心态可以执行所有指令、用户态只能执行非特权指令
用户态→核心态(硬件中断); 核心态→用户态(操作系统程序)
用户态不能执行中断指令
通道是一种控制一台或多台外部设备的硬件机构
不是所有的异常处理后都能回到原来指令继续执行
操作系统-2-进程管理
进程与线程
进程
组成与特征
组成:PCB、程序段、相关数据。PCB是进程存在的唯一标识
特征:
1、进程是资源分配的最小单位、是调度的独立单位(非最小)
2、进程是由多程序的并发执行引出的
3、进程有 动态性(最基本)、并发性、独立性、异步性、结构性
状态与转换
运行态→就绪态:时间片用完,被抢占
运行→阻塞是主动、阻塞→就绪是被动
就绪态是只缺少处理机,其他什么都不缺
进程控制(使用原语)
创建:用户登录系统、作业调度、系统提供服务、用户程序应用的请求
创建时,创建PCB失败则创建进程失败、 获取资源不足则进入阻塞态
PCB
包含:进程描述信息(ID和归属)、控制管理信息(状态,优先级,地址,时间)、 资源分配清单(各种指针)、 处理机信息(各种寄存器的值)
常驻内存,在进程结束时删除。是进程存在的唯一标识
进程通信
共享存储:通信进程之间有一个可直接访问的共享空间
消息传递:以message为单位,通过发和收两个原语实现【直接:直接发收信件、 间接:使用信箱中间实体】
管道通信:管道是通信过程中的一个共享文件(pipe),半双工,一次性,信息不在管道逗留,缓冲区,字符流传输
线程
目的:减少程序并发执行时的时空开销,提高系统并发性
特点:基本的CPU执行单元,程序执行的最小单元
由线程ID、PC、寄存器集合和堆栈组成
是进程中的一个实体,是系统独立调度和分配的基本单位
不能拥有资源(除了自己的一点信息),可用所属进程的资源。有唯一的标识符和一个线程控制块
用户级线程管理工作由应用程序完成(对内核透明)、 内核级线程管理工作由内核完成
处理机调度
作业调度(高级调度):从外存→内存→外存。 每个作业只进出一次
内存调度(中级调度):不能运行的调入内存挂起
进程调度(低级调度):从就绪队列→处理机。 是操作系统中最基本的一种调度
调度方式:剥夺式和非剥夺式
调度的相关计算
系统吞吐量:单位时间CPU完成的作业量
周转时间:完成时间—提交时间
带权周转时间:周转时间/实际运行时间 大于1
调度算法
先来先服务(FCFS): 作业、进程调度, 不可剥夺, 长作业有利、短作业不利
短作业优先(SJF): 对长作业不利, 有饥饿现象, 平均等待和周转时间最少
优先级调度:静态:优先级在创建进程时确定,全程不变、 动态:根据情况动态调整
高响应比: (等待时间+要求服务时间)/要求服务时间 响应比越大越先执行
时间片轮转: 分时系统 一定可抢占 目的:使多个交互的用户能得到及时的响应
多级反馈,相对而言比较好的算法,各方面都很好
进程同步
1、临界资源:一次只允许一个进程使用的资源
2、临界区:访问临界资源的那段代码
3、同步:直接制约关系、 互斥:间接制约关系
4、同步机制遵循准则: 空闲让进、忙则等待、有限等待、让权等待
互斥方法
Peterson Algorithm 没有饥饿,不能让权等待
硬件方法(TestAndSet) 不能实现让权等待,有饥饿
管程
组成
局部于管程的共享结构数据说明
对该数据结构进行操作的一组过程
对局部于管程的共享数据设置初始值的语句
特性
局部于管程的数据结构只能被局部于管程内的过程访问
一个进程只有通过调用管程内的过程才能进入管程访问共享数据
每次只允许一个进程在管程内执行某个内部过程
死锁
产生原因
对系统中不可剥夺的资源的竞争
进程推进顺序非法,请求和释放资源的顺序不当
死锁产生必要条条件: 互斥条件、不可剥夺条件、请求并保持条件、循环等待条件【死锁产生必须同时满足,缺一不可】
处理策略(学会区分)
死锁预防
破坏互斥条件:资源共享(不现实)
破坏不可剥夺条件:不能满足全部就释放已有
破坏请求并保持条件:预先静态分配方法,不能一次性分配就不分配。 浪费资源、有饥饿现象
破坏循环等待条件:顺序资源分配法,给资源编号,按编号顺序请求资源。
死锁避免:避免系统进入不安全状态, 安全状态一定不会发生死锁。 使用银行家算法
死锁检测: 利用资源分配图,死锁定理
死锁解除
资源剥夺:挂起某些死锁进程,抢占其资源
撤销进程:强制撤销部分或者全部死锁进程的资源
进程回退:让一个或者多个进程回退到自已回避死锁的地步
操作系统-3-内存管理
内存管理概念
内存管理原理
概念:操作系统对内存的划分和动态分配
内存管理的功能:存储空间的管理和分配、地址转换、内存空间的扩充、存储保护
程序装入和链接
步骤:编译 → 链接 → 装入 (编译:把用户源代码编译成目标模块,链接:把目标模块和库函数链接在一起形成装入模块,装入:把装入模块装入内存)
链接
静态链接:在程序运行之前,就把目标模块和库函数链接成一个执行程序,以后不再拆分。
装入时动态链接:得到目标模块后,在装入内存时,边装入边链接。
运行时动态链接:在程序执行中需要该目标模块才链接。便于修改和更新,实现共享
装入
绝对装入:编译时,若知道驻留地址,就会产生绝对地址。 只适用于单道程序环境。
可重定位装入(静态):从0开始产生相对地址,地址变换在装入时一次完成。装入时分配全部空间
动态重定位:地址转换在程序真正需要运行的时候,需要重定位寄存器的支持。程序可以被分配到不连续的存储区
内存保护
上下限寄存器判断越界。
重定位寄存器(用来+),界地址寄存器(用来比)
连续分配管理方式
单一连续分配:没有内存保护,只能用于单用户单任务的系统。内部碎片,利用率低
固定分区分配:(多道程序最简单的存储分配)每个分区只装一个作业。内部碎片
动态分区分配
首次适应:按照地址递增排序,通常来说是最简单,且最好和最快的
最佳适应:按照容量递增排序,会产生最多的外部碎片
最坏适应:按照容量递减排序
邻近适应:循环首次适应
非连续分配管理方式
基本分页存储管理方式
1、把主存和进程都按照同样大小的块划分,进程的块叫页,主存的块叫页框
2、页面太小会导致页面数过多,页表过长,占用大量内存; 页面过大,内部碎片增多,降低利用率
3、页表存储在主存中,由页表项组成
4、地址变换过程由硬件完成,页式管理的地址空间是一维的
5、多级页表的时候,顶级页表只能由一个页面
基本分段存储管理方式
1、按照进程的自然段划分
2、段地址空间的二维的,由段号和段内偏移组成
3、当一个作业正从共享段中读取数据的时候,必须防止另一个作业修改此共享段的数据。不能修改的代码称为纯代码或者(可重入代码)
段页式管理方式
1、把进程先分段,再分页
2、一个进程中,段表只能有一个,页表可以有多个。
3、分段来管理和分配用户地址空间,分页来管理物理存储空间
虚拟内存管理
传统存储管理方式的特点:一次性、驻留性
虚拟存储器管理的特点:多次性、对换性、虚拟性
虚拟内存技术的实现。需要建立在离散分配的内存管理方式的基础上,不管哪种方式都需要一定硬件的支持。
请求分页管理方式
1、需要一定的硬件:页表机制、缺页中断机构、地址变换机构
2、缺页中断:在指令执行期间而不是指令完成后。属于内部中断
页面置换算法
最佳置换:以后永不使用,无法实现的算法
先进先出(FIFO):有Belady异常。
最近最久未使用(LRU):每个页面需要一个访问字段,需要寄存器和栈的硬件支持
时钟CLOCK(最近未用NRU):优先换出未使用过的页面
只有FIFO有Belady,但是每个算法都有可能抖动
页面分配策略
驻留集分配(考察过名称)
固定分配全局置换:为每个进程分配一定数目的物理块,全程不变
可变分配全局置换:若进程缺页系统会分配新的物理块
可变分配局部置换:若频繁的缺页2,则再分一些物理块。若缺页率较低也会回收。
调入时间:预调页策略;一般在首次调入的时候使用; 请求调页策略:有请求就调页。
操作系统-4-文件管理
基础
定义
文件是以计算机硬盘为载体的存储在计算机上的信息集合
用户的输入和输出以文件为基本单位
组成:数据项 → 记录 → 文件
所有文件信息都保存在目录结构中,目录结构保存在外存上
操作
打开
首次使用文件时,使用系统调用OPEN将指定文件的属性从外存复制到内存打开文件表的一个表目,并把该表目的编号(索引)返回给用户
操作系统维护一个包含所有打开文件信息的表(打开文件表)
OPEN通常返回一个指向打开文件表中一个条目的指针。通过该指针(非文件名)进行I/O操作
关闭:打开文件表中每个文件都有一个文件打开计数器,只有当计数器为0时才能删除打开文件表中的条目,释放FCB
结构
文件的逻辑结构【用户观点】
特点:用户观点出发看到的组织形式,与存储介质无关
无结构文件(流式文件)
以B为单位,数据按顺序组织成记录。穷举法搜索。
有结构文件(记录式文件)
顺序文件:顺序排列,一般是定长 平均需要N/2次查找
串结构:按时间先后顺序排列
顺序结构:按关键字顺序排列
索引文件:建立一张索引表(表自身是顺序文件),
索引顺序文件:(为每组的第一个记录创建索引项,包含关键字值和一个指向该记录的指针)组间有序,组内无序。 先根据索引表找到组号,再在组内顺序查找记录 平均需要N开方次查找
直接文件或散列文件:通过散列函数查找,没有顺序。
文件的物理结构【磁盘存储观点】
分配方式
连续分配:
每个文件在磁盘上占一组连续的块,目录条目【实地址 | 长度】
支持顺序和直接访问,不能动态增长,会有外部碎片。访盘一次
连接分配
可以动态增长,但只能按照链接顺序查找,不能直接访问。指针信息占内存。 访盘n次
隐式链接:每个盘块都包含有指向下一个盘块的指针(对用户透明) 目录【始指针 | 尾指针】
显示连接:内存中有一张链接表(文件分配表,FAT),整个磁盘只有一张,表项是该盘块对应下一个盘块的指针。
索引分配:
每个文件的所有盘块号集中放在一起构成索引块(表),每个文件都有其索引块
链接方案:一个索引块为一个磁盘块。大文件把多个索引块链接起来
多层索引:第一层指向第二层,以此类推。
混合索引:索引节点内包含多个不同级的地址索引(有直接、一级、二级。。。)
索引块占用内存,M级索引需要M+1次访盘
管理方式
空闲表法:外存上所有空闲区有一张空闲盘块表,按盘块号递增次序排序。属于连续分配方式/
空闲链表法
空闲盘块连:以盘块为单位,链首分配,回首到链尾。
空闲盘区法:(一个盘区包含多个盘块),盘曲有指向下一盘区的指针,以及本盘区的大小信息。
位视图法:用二进制矩阵表示盘块的使用情况。0表示空闲。
成组链接法:UNIX中使用的方法
文件的目录结构
文件控制块和索引节点
文件控制块(FCB)
1、存放用来控制文件的各种信息数据
2、FCB的有序集合称为文件目录,一个FCB就是一个文件目录项
3、FCB包含 文件名、物理位置、逻辑结构、物理结构、存取权限等信息
4、FCB必须连续存放
索引结点
有些系统(UNIX)文件名和文件描述信息分开,文件描述信息单独形成一个称为索引结点的数据结构
目录结构
单级目录结构:整个文件系统中只有一张目录表,每个文件占一个目录项
两级目录结构:主文件目录和用户文件目录(一级目录按照用户划分)
多级目录结构:从根目录出发形成的目录是”绝对路径“; 从当前目录形成的目录是“相对路径”
无环图目录结构:每个文件都有一个共享计数器,当其值为0时才能删除。
文件的共享
基于索引结点(硬链接)
1、文件的物理地址和其他信息存放在索引结点 (索引结点里有一个链接计数count)
2、文件目录中只有文件名和指向相应索引结点的指针
3、只有当count = 0 的时候才能删除该文件。
基于符号链(软连接)
1、被共享者(非拥有者)创建一个同名文件F并写入自己的目录,但是F里面只包含一个连接到真实F的路径名
2、只有共享者(拥有者)才拥有指向该索引结点的指针,其他用户只有路径名。
硬链接速度比软连接快很多
文件的保护
1、通过口令保护、加密保护和访问控制来实现
2、口令保护和加密保护是防止文件被他人存取和窃取,访问控制是控制用户对文件的访问方式。
3、口令是用户在建立文件时提供的,存在系统内部,不够安全。
4、访问控制机制的安全性比加密保护的安全性差; 访问控制由系统实现。
5、文件的访问由 用户访问权限和文件属性共同限制。
磁盘
一次读写操作时间:寻道时间+延迟时间+传输时间 其中延迟时间为转一圈 时间的一半 选到时间一般影响最大
磁盘调度算法
先来先服务:最简单,最公平。
最短寻找时间优先(SSTF):会有饥饿现象。
扫描算法(SCAN)电梯调度算法:会计算一次边界顶点
循环扫描(C-SCAN):只按一个方向移动,会计算两次边界顶点
LOOK和C-LOOK算法是SCAN和C-SCAN的改进,不需要到达边界顶点。
磁盘初始化
低级格式化(物理分区):在磁盘存储数据之前,必须分成扇区以便控制器能进行读和写操作。里面包含磁盘控制器所使用的信息,包括检验码
逻辑格式化:操作系统将初始的文件系统数据结构存储到磁盘上。包含空闲和已分配的空间以及一个初始为空的目录。
计算机启动时的初始化程序(自举程序)通常保存在ROM里面。因为ROM掉电非易失,如果掉电易失,关机后没法再开机。
操作系统-5-输入输出管理
I/O子程序的层次结构
层次(由高到低): 用户层I/O软件 → 设备独立性软件 → 设备驱动程序 → 中断处理程序 → 硬件
底层为高层提供服务,只有最底层才涉及硬件的具体特性
层次结构
用户层I/O软件:实现与用户交互的接口,用户层软件只能通过系统调用来获取系统服务
设备独立性软件:实现用户程序与设备驱动器的统一接口,命令设备,设备保护,设备分配与始放等。 使用逻辑设备名请求,执行时才转换成物理设备名。I/O重定向。
设备驱动程序:每类设备配置一个设备驱动程序,以进程形式存在。
中断处理程序:保护被中断进程的CPU环境。主要任务:进程上下文切换;处理中断信号源进行测速;读取设备状态和修改进程状态。
硬件设备:机械部件+电子部件。电子部件称为设备控制器。
设备控制器(也称I/O逻辑):接收和识别CPU或通道发来的命令; 数据交换; 发现和记录设备以及自身的状态,供CPU处理; 设备地址识别
高速缓存与缓冲区
磁盘高速缓存
1、提高磁盘的I/O速度
2、逻辑上属于磁盘,物理上是驻留在内存的盘块
缓冲区(Buffer)
特点:缓冲区不为空不能冲入数据,只有为空时才能冲入,必须充满后才能取出
双缓冲:一块数据用时MAX(C+M,T) T是右边
缓冲池:由多个系统公用的缓冲区组成,还有四种特殊缓冲区
高速缓存和缓冲区的对比:都是介于高低速设备之间; 高速缓存是备份副本。缓冲区不是; 高速缓存缺失时高速设备会直接访问低速设备
设备分配与回收
分配的数据结构
1、系统设备表(SDT):整个系统只有一张,每个表目表一个设备并含有一个DCT
2、设备控制表(DCT):一个设备由、有一张设备控制表,表项是设备的属性,其中有一个表目是一个设备控制器COCT的指针
3、设备控制器表(COCT):设备控制器要请求通道来进行服务,则其中有一个表项表通道控制器(CHCT)
4、通道控制表(CHCT):一个通道可以为多个设备控制器服务,则CHCT里面有一个指针指向一个表,该表每个表目指向一个被服务的设备控制器COCT
每个控制器控制表COCT只能指向一个通道控制表CHCT; 一个通道控制表CHCT可以指向多个控制器控制表COCT
分配策略
原则:根据设备特性,用户要求,系统配置情况。
静态分配:主要用于独占设备,执行前一次性分配全部需求。不会出现死锁
动态分配:有需就给,用完即收。有可能死锁
分配算法:先请求先分配和优先级高者优先
分配安全性
安全分配:发出I/O请求便阻塞,完成I/O请求才被唤醒
不安全分配:可 连续多个请求,只有当某个被请求的设备被其他进程占用才阻塞
设备独立性
设备独立性是指应用程序独立于具体使用的物理设备
逻辑设备表(LUT):表项 【 逻辑设备名 | 物理设备名 | 设备驱动程序的入口地址】
整个系统只有一张LUT: 适用于单用户系统,不允许有相同的逻辑设备名。
每个用户一张LUT:用户登录时创建一个程序,也创建一张LUT,放入PCB
SPOOLing(假脱机技术)
输入井和输出井:是在磁盘中开辟的两个存储区域。用于模拟脱机的磁盘,收容I/O和用户的输入输出数据
输入缓冲区和输出缓冲区:在内存中开辟出来的两个缓冲区用于暂存和输入输出井配合使用
0 条评论
回复 删除
下一页