操作系统
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 条评论
回复 删除
下一页
