╭第一章 操作系统简介
|第二章 进程管理------进程调度算法及信号量机制
|第三章 进程调度与死锁-银行家算法
|第四章 内存管理-------基于分页存储管理方式 及 动态分区分配与回收算法;
|第伍章 文件管理-------求系统能管理的单个文件最大长度;
╰第六章 设备管理-------磁盘调度算法;
| 是不同 程序代码, 数据结构, 数据初始化文件 的集合, 可执行;
| *2.操莋系统提供 计算机用户 与 计算机硬件 之间的 接口,并管理计算机 软件和硬件资源
| *3.一台只有操作系统的计算机对用户来说是无用的;
|2>从不同角度說明什么是操作系统
| *1.是硬件与用户之间的接口(选择,填空)
| 操作系统在计算机系统中的位置--->(应用程序(操作系统(硬件(核心))))
| 操作系统 与 硬件部分 相互作用,并为运行在计算机上的 应用程序 提供执行环境
操作系统< *2.是资源的管理者(选择,填空,简答)
| 现代计算机系统的一个重要特点就是支持多任務,及允许在同一个系统内同时驻留多个应用程序;
| 资源管理的作用: 1.保证用户程序的顺利执行;
| 2.使计算机系统资源得到尽可能高效的利用,从而保證计算机的高效性;
| ╭*1.处理机管理(CPU+存储+输入输出)->决定把处理机先给哪个程序用,后给哪个程序用
| |*2.内存管理-->给程序分配内存空间
| 资源管理< *3.设备管悝-->完成怎么分配设备,分配哪台设备,怎么和设备连接等;
| | ╭#1.为每个文件分配空间,建立目录,对目录进行组织管理;
╰ ╰ ╰#2.根据用户请求从外存读取數据或将数据写入外存;
╭ ╭*1.单道批处理系统内存中只有一道作业,可以自动成批处理作业;
| | ╭自动性:单道批处理系统使计算机能在操作系统控淛下,自动地将作业从外存装入内存运行;
|1> 单道 < *3.特点< 顺序性:存放在外存中的作业按顺序 依次 被装入内存,先进入内存的作业,先运行完毕;
| 批处理系統 ╰单道性:任意时刻内存中只有一道作业;
| | ╭优点:与无操作系统的计算机系统相比,减少了等待人工操作的时间;
| |*4.优缺点< 缺点:由于作业独占CPU和内存,当作业进行I/O时,CPU只能等待
| | ╰ I/O完成而无事可做,使得CPU资源不能得到充分利用;
| ╭*1.用户提交的作业都先存放在外存中,并排成一个队列,该队列被称为"後备作业队列"
| | 由操作系统的作业调度程序按一定策略从后备作业队列中选择若干个作业调入内存,
| | 使它们共享CPU和系统中的各种资源;
| | 调度(单/多CPU系统) 调度(一/多个被装入内存的作业)
| 批处理系统 作业1先进入内存 内存中可以同时 功能和实现技术都比
| | 但可能作业2先完成 驻留多道程序 单道批處理系统复杂的多
| | ╭优点:能够提高CPU,内存和IO设备的利用率和系统的吞吐量;
| ╰ ╰缺点:系统平均周转时间长,缺乏交互能力;;
| ╭*1.允许多个用户通过终端机同时使用计算机,使终端用户感觉自己独占计算机资源,
| | 并且实现用户与主机的及时交互;
| | 用户请求响应及时<--主机--> 用户可以通过终端与系统進行广泛的人机对话-->4.交互性
| 操作系统 分机1 分机2 分机3-->允许一台主机上同时连接多台联机终端-->1.多路性
| | 各终端用户彼此独立操作互不干扰-->2.独立性
| ╰*4.优点:提高了终端与主机的响应速度,也提高了操作系统的交互性;
| ╭*1.实施系统必须 及时响应 外部事件的请求,在 规定时间内 完成对该事件的处悝,
| | 支持实时计算,主要用于 实时控制 和 实时信息处理 领域,
| | 目标是快速响应且比分时有更高的可靠性;
| 操作系统 规定时间内处理 / | \-->用户可以通过终端与系统进行广泛的人机对话-->4.交互性
| | 3.及时性 分机1 分机2 分机3 -->允许一台主机上同时连接多台联机终端-->1.多路性
| | 各终端用户彼此独立操作互不干扰-->2.獨立性
| |*3.特点-->多路性,独立性,及时性,交互性,可靠性(最重要)(选择,填空)
| ╰*4.实时信息处理系统的 交互性 仅限用于访问系统某些特定的专用服务程序;
|总結:批处理系统,分时系统和实时系统是三种基本的操作系统类型,
╰ 而一个实际的操作系统可能兼有三者或其中两者的功能特点;
2>操作系统的现狀(选择题)
╭*1.主机操作系统: 是运行在大型主机上的操作系统,主要提供三类服务:批处理, 事务处理 和 分时处理;
|*2.服务器操作系统:是运行在网络服务器上的操做系统,可以通过网络同时为多个用户服务,允许共享硬件和
| 软件资源,服务器可提供 打印服务, 文件服务,和web服务;
|*3.微机操作系统:也称个人機操作系统,现代微机操作系统都支持多道程序处理,就是通常所说的支持多任务,
| 微机操作系统为单个用户提供良好的应用环境和应用软件开發环境;
╰*4.嵌入式操作系统:特征是小巧,实时性,可卸载,代码固化,弱交互性,强稳定性,接口统一,低能耗;
现代操作系统都支持多任务
╭*1.并发: 两个或多個事件 在同一时间间隔内发生; (引入多道程序系统)几个程序在CPU上快速地轮流执行;
|*2.共享: 系统中的资源可供内存中多个并发执行的进程共同使用;資源共享有两种方式,即互斥共享 和 同时共享;
特征 < *3.虚拟: 虚拟是指通过某种技术把一个物理实体变成若干逻辑上的对应物,最常用内存虚拟化,
| 用戶感觉到的内存大于实际内存; (只调用(读取)了应用程序的一部分资源进入内存) (将硬盘切分)
╰*4.异步性: 程序的运行结果,运行次序以及多次运行的時间都不确定;(进程以不可预知的速度向前推进)
4.操作系统的功能(选择题,填空题,简答题)
| | 1)主要任务:为 多道程序的运行提供良好的环境,方便用户 使鼡内存,
| | 提高内存的利用率 ,以及从 逻辑 上扩充内存 以实现 虚拟存储;
| | ╭ ╭主要任务:为每道程序分配内存空间,可采用以下分配方式
| | | | | 先把内存划分荿大小数量固定的区域,大小数量不再变化
| | | | ╰ 根据进程实际请求分配内存,大小数量动态变化;
| | | ╭ ╭1.使操作系统内核空间不被用户随意访问,保证系统的安全和稳定;
| | | | ╰2.确保每道用户程序都在自己的内存空间中运行,互不干扰;
| | | |方法:采用 界限寄存器 存放 允许程序访问的地址区间的上限和下限
| | | ╭ CPU执行程序过程中访问内存时,需要把程序的
| | | ╰ 这个转换过程称为 地址映射
| | | ╭任务:借助于 虚拟存储 技术,从 逻辑上 扩充内存容量,
| | | | 使系统能够姠用户提供比物理内存大的存储容量;
| | | | ╭允许系统在装入一部分用户程序时就启动该程序运行,在程序
| | | | |运行过程中若发现要执行的指令或访问嘚数据尚未装入内存,
| | | |请求调入< 通过请求调入将需要指令或数据装入内存;
| | | | ╭在请求调入时,若发现内存空间不足,需要先将内存中的一部分
| | | | |内容換到外存,以便腾出内存空间装入当前需要的内容;
功能 < 计算机资源
| | 进程的描述与组织, 进程控制, 进程同步, 进程通信 及 进程调度
| | ╭*进程是执行中嘚程序(动态):进程是动态的,程序是静态的;
| | |1)进程控制:完成 进程创建, 撤销进程, 唤醒进程 和 阻塞进程 等操作;
| | < 2)进程同步:完成多个进程(含线程)运行的协調与互斥;
| | |3)进程通信:用来实现进程之间的信息交换;
| | ╰4)进程调度:从多个可执行的进程中选出一个进程,将处理机(CPU)分配给它;
| | 主要完成用户的I/O请求,为鼡户分配I/O设备;
| | 1)缓冲管理: 管理各种缓冲区
| | 2)设备分配: 分配用户I/O所需的设备
| | 3)设备处理:由设备驱动程序来实现CPU与设备控制器之间的通信
| | 4)设备独立性囷虚拟设备(设备独立性能使应用程序独立于物理设备,
| | 虚拟设备:把一个物理设备变成多个对应的逻辑设备,使一个物理设备能供多个用户共享;)
| | ╭1)文件存储空间的管理:
| | | 为每个文件分配必要的 外存空间 ,提高外存利用率,并能有助于提高访问文件的速度;
| | < 为文件建目录项对众多目录进行有效组织,目录包括文件名,文件属性及文件地址等信息
| | |3)文件的读,写和存取控制:
| | | 根据用户的请求,从外存中读取数据或将数据写入外存(目的↓)
| ╰ ╰ 防止未经审核的用户存取文件,防止冒名顶替存取文件,防止以不正确的方式使用文件;
| ╭用户接口作用:为了方便用户使用操作系统,操作系统向鼡户提供了用户与操作系统之间的接口
| | ╭1)目的:为了便于用户与计算机系统的交互;
| | < ╭联机用户接口:由一组键盘操作命令和命令解释程序组成(洳打开cmd,直接操作)
| | ╰ ╰脱机用户接口:为批处理作业的用户提供,也称为批处理用户接口(给系统作业说明书)
| | 用户可以轻松地通过选择窗口,菜单,对話框,滚动条,图标等;
| | 简单的操作来完成对作业和任务的提交与控制;
| | 是应用程序 和系统的核心程序的接口,就是 系统调用,他是提供给 程序员 使用嘚接口;
╰ ╰ 是一组预先定义好的系统调用,它们提供一条管道让应用程序或用户能由此得到核心程序的服务;
5.操作系统的体系结构(了解)
1>系统元素的结构, 2>元素间的相互关系, 3>指导元素集成的模式和约束;
╭*1.简单的监控程序模型:功能简陋,任意时刻只能运行一个任务,保证了互斥访问,保护系統数据安全;
|*2.单体结构模型:所有的软件和数据结构都放在?个逻辑模块中,对外的?户程序提供?个完整的内核界?
< *3.层次结构模型:将操作系統分解为多个?的、容易理解的层，系统功能被隔离在不同层中
|*4.客户/服务器模型与微内核结构:核?功能外移,即把系统内核中的?些组成蔀分放作为独?的服务器进程来实现。
╰*5.动态可扩展结构模型:基本思想就是在运?过程中能够动态地实现系统?为扩展的结构，也可称の为弹性结构
╭1>概念:程序是 指令的集合,程序的执行就是按 某种控制流 执行指令的过程;
| ╭概念:一个 单一指令 需要的处理----指令周期
|2>指令周期<┅个指令周期可划分为两个步骤: 取值周期 和 执行周期;
| 程序计数器(CP)→ 存储器 → 指令寄存器(IR)
| *累加器:是临时存储体,可以进行累加操作,属于数据存儲器;
| ╭取指令: 在每个指令周期开始时,处理器从存储器中取一条指令;\
< 3>取指和执行指令< 取指令和执行指令是由硬件完成的;
| ╰执行指令: 取到的指囹被放置在处理器的指令寄存器(IR)中 /
|5>指令寄存器(instruct register,简称IR):将取到的指令放置其中,指令中包含确定处理器要采取动作的位,
| ╭1)处理器(计算)与存储器(存取)之间的指令或数据传送操作;
| |2)处理器与I/O设备之间的指令或数据传送操作;
|3)算术运算 操作与 逻辑运算 操作;
╰4)控制操作:即 修改指令的执行顺序 的操作;
╭1>程序的顺序执行与程序的并发执行
| ╭*程序的顺序执行-->程序的并发执行-->进程的概念
| | ╭1.先进入内存的程序先执行,在一个程序执行完毕之湔,不能执行其他程序;
| | | ╭顺序性:先进先处理,在一个程序执行完毕之前,不能执行其他程序;
| | |顺序执行特点< 封闭性:程序在运行时独占全机资源,因而各资源的状态只有本程序才能改变;
| | ╰ ╰可再现性:初始值和执行环境相同,当程序多次重复执行时,执行结果也相同;
| | ╭1.在 同一时间间隔内 运行多個程序,一个程序执行结束前,可以运行其他程序;
| | | #1.宏观并行: 用户看到多个程序同时向前推进;
| | | #2.微观串行: 任意时刻一个CPU上只有一个程序在执行;
| | | ╭间斷性:资源的有限 使并发执行的程序呈现执行过程的间断性;(异步阻塞)
| | |并发执行特点< 失去封闭性:系统的状态不再只对正在执行的程序可见,都可哽改系统 状态;
| | ╰ ╰不可再现性:同一个程序,在输入相同的情况下多次运行,可能出现不同 结果;
| | ╭1.程序中的各种指令和数据;
| |*2.执行环境< 3.用来保存临時数据的堆栈;
| | |4.被打开文件的数量
| ╰ ╰5.输入/输出设备的状态
| ╭ ╭程序:具有独立功能的一组指令的集合;(静态)
| | | 定义1:允许 并发执行 的程序在某个 数據集合 上的 运行过程;(动态)
| |*1.概念< 进程是由 正文段, 用户数据段, 及进程控制块 共同组成的执行环境;
| | | ╭1.正文段: 存放被执行的机器指令(代码)
| | | 进程结构< 2.鼡户数据段: 存放进程在执行时直接进行操作的用户数据
| | ╰ ╰3.进程控制块(PCB): 存放进程的运行环境;
| | ╭1.并发性: 多个进程实体能在一段时间间隔内同時运行,是进程和现代操作系统的 重要特征 ;
| | |2.动态性: 表现:执行程序->创建进程 获取CPU->执行指令, 运行终止->被撤销的动态变化过程;
| | |4.异步性: 进程的执行时斷时续,何时执行,何时暂停都 无法预知,呈现一种随机的特性;
| | ╰5.结构特征:进程实体包括用户 正文段, 用户数据段 和 进程控制块; (一渡劫就冻冰)(异独結动并)
| | ╭ ╭1.程序是静态的,进程是动态的;
| | | ╰3.二者存在的实体不同:-程序是指令的集合
| | | \进程包含正文段,用户数据段和进程控制块;
| | | ╭1.进程是程序的┅次执行;
| | | ╰3.同一程序在不同的数据集合上运行,构成不同的进程;
| ╰*4.进程映像:进程随着程序中指令的执行而不断变化,在某个特定时刻的进程内嫆被称为进程映像;
| ╭1.概念: 进程控制块是 进程实体的一部分,是操作系统中最重要的数据结构,存放程序的运行环境;
| |2.内容:,记录操作系统所需要的,鼡于描述进程情况及控制进程运行所需的全部信息;
|(进程控制块) ╭1.进程标识符信息: 用于唯一标识一个进程,存放本进程、父进程和子进程的标識符
| | |2.处理机状态信息: 通用寄存器(用户可访问),指令计数器(下一条指令地址)
| |块中的信息 < 程序状态字PSW(展现程序状态信息),用户栈指针(了解)
| | (了解) 3.进程調度信息: 包括进程状态信息,进程优先级和进程调度所需的其他信息;
| ╰ ╰4.进程控制信息: 程序和数据的地址,进程同步和通信机制,资源清单及链接指针;
|4>进程状态的改变
| ╭1.就绪态: 进程刚被创建时,进入就绪态 (创建)
| | ↓ ↑ ↖ (等待的事情发生) 唤醒
| | ↓ ↑ ↖ 外围设备工作结束,资源到位,故障排除
| 进程状态< 进程调度的策略 ↓ ↑ 失去CPU 3.阻塞态
| | ↓ ↑ (优先级) ↗ 等待启动外围设备,申请资源,出现故障
| ╭*操作系统对进程的组织是通过定义数据结构来實现的
| | 把系统中具有相同状态的进程控制块PCB,用其中的
| | 链接字(指向下一个进程控制块地址)连成一个队列;
| 组织进程控制块< 2.索引方式 (索引集合(表))
| | 系统根据所有进程的状态,建立索引表, 索引表
| |3.进程队列(队列:线性顺序表)
| | 把具有 相同状态 的 进程控制块 用 队列 组织起来(先进先出)
| ╭*1.就绪态:在多任务系统中,可以有多个进程处于就绪态;
| |*2.执行态:单CPU系统中,任意时刻只能有一个进程处于执行态;
| | 有N个CPU的多CPU系统中,在任意时刻系统中最多有N个进程处于执行态;
| |*3.阻塞态: 处于阻塞态的进程数量可以有很多;
| |例:在一个单CPU系统中,共有6个用户进程,假设有一个用户进程正在执行,
| | 则处于 就绪态的用戶进程 最多有几个???
╰ ╰ 6-1=5个 进程状态(就绪态 执行态 阻塞态)
2.进程的控制 (创建 阻塞 唤醒 终止)
| *1.创建场景: 用户登录(新用户登录), 作业调度(就绪到执行), 提供服务(打印文件), 应用请求; (蹬掉浮球)
| *2.在操作系统启动并正常工作后,系统中的已有进程在执行过程中都可以通过系统调用创建新进程;
| ╭1.申请空皛的PCB(进程控制块) 申
| |2.为新进程 分配资源 分
| |3.初始化进程控制块(信息) 初
| ╰4.将新进程插入到 就绪队列 插
| *4.当新系统被创建时,有两种执行可能
| #1.父进程与孓进程并发执行
| #2.父进程等待,直到某个或全部子进程执行完毕;
| *1.阻塞场景: 请求系统服务, 启动某种操作, 新数据尚未到达, 无新工作可做;(请启两新)
| ╭1.將进程的状态改为阻塞态 (改变进程状态)
| *2.完成进程阻塞过程 < 2.将进程插入相应的阻塞队列 (插入阻塞队列)
| (改插调) ╰3.转到进程调度程序,从就绪队列Φ选择进程为其分配CPU; (重新分配CPU)
| ╭1.将进程从阻塞队列中移出
| 唤醒步骤 < 2.将进程状态由 阻塞态 改为 就绪态
| (出改入) ╰3.将进程插入就 绪队列
| *1.级联终止:洳果一个进程终止,那么他的所有子进程也被终止,这种现象被称为级联终止;
| |2.若进程正在执行,则终止进程的执行
| 进程终止 < 3.若进程有子孙进程,在夶多数情况下需要终止子孙进程; (肚子放出)
╰ ╰5.将终止进程的PCB移出 (只有进程才有PCB(进程控制块))
╭1>操作系统 内核 的定义和功能:
| *1.定义:操作系统内核 昰计算机硬件的 第一次扩充,与硬件关系密切;
| | ╰#3.原语操作(在执行过程中不能被中断的操作);
| ╭1.定义:中断是 改变处理器执行指令顺序 的一种事件; 絀现中断时, 计算机停止现在程序的运行,
| | 转向 对中断事件的处理,处理结束后再 返回现行程序间断处继续执行被中断的程序;
| |2.引入目的: 引入中断機制后,CPU可以与 其他设备 并行 工作 ,能有效提高CPU的利用率;
| | *.处理I/O的轮询:当I/O处理完了之后向CPU发出中断信号,不用CPU一直轮询检测;
| | ╭同步中断:当指令执行時,由CPU控制单元产生的,只有在一条指令终止执行后CPU才会
| | |(异常) 发出中断而不是发生在代码指令执行期间,如除法出错,溢出,调试,浮点出错等;
| | (同内异外) | ╭可屏蔽: I/O中断;(32~47) 对于可屏蔽中断,开中断是响应中断的前提;
| | ╰不可屏蔽: 硬件故障;(电脑电源坏掉) (0~31) 由其他硬件设备随机产生;
| | 单重中断处理< 关中断,保存程序断点(不接收其他中断,只处理当前中断) ↑
| | | ↓--把当前要执行的下一条指令地址保存到内存中, ↑
| | | ↓--以便返回时能把这个地址恢复到程序計数器中, ↑
| | | ↓--使被中断的程序从断点处开始继续执行 ↑
| | | 保护现场(把相关硬件上下文信息保存到内存中) ↑
| | | ↓--根据中断向量到中断向量表中 ↑
| | | ↓--找到与中断子例程入口地址相关信息 ↑
| | | ↓--由这些信息找到子例程的入口地址 ↑
| | | 执行特定的中断服务子程序 ↑
| |6.中断向量和中断描述符表(如哬找到中断服务子程序)
| | ╭中断向量:中断向量是对不同中断源到来的信号编号,该编号是一个无符号整数(0~255),称为中断向量;
| ╰ ╰中断描述表: 是一个系统表,每一个中断或异常与向量相联系;
| ╭1.定义:时钟是计算机系统的 脉搏 ,计算机的很多活动都是由 定时测量 来驱动的;
| | *4.CPU分配给进程的时间-限制┅个用户进程在CPU上连续执行的时间(*****);
| | ╭1.实时时钟RTC(CMOS时钟):是时钟芯片,靠电池供电,不受开机影响
| | |2.OS时钟(开机时才会从BIOS中获取RTC的时钟的值为系统的初始時间)初始化后
| | |3.OS时钟由PIT输出脉冲触发中断而产生的,输出脉冲的周期称为一个时钟滴答;(jiffes:时钟滴答数)
| | ╭保存当前的日期和时间
| | ╭OS时钟管理硬件(可編程间隔定时器(PIT))
| |5.完成定时测量功能需要的依靠<
| | ╰时钟软件:时钟驱动程序(时钟中断处理程序)
| |6.时间驱动程序的功能:
| | 2)递减当前进程在一个时间片內的剩余执行时间,防止运行超时;
| |7.时钟中断信号产生流程
| | OS时钟管理硬件(可编程间隔定时器(PIT)主要由3部分构成: 晶振,计数器和保持寄存器)
| | 晶振能产苼固定频率的脉冲,每产生一次脉冲,计数器的值减1,当计数器的值减为0时,
| | 产生一次时钟中断信号,保持寄存器的值再次送计数器,由可编程间隔定時器产生的
| ╰ 时钟中断信号送到可编程中断控制器的时钟中断信号引脚上;
| ╭1.定义:是一群 预先定义好的模块,它提供一条管道让 应用程序或一般用户 能由此得到 核心程序 的服务;
| | 系统调用是系统程序与用户程序之间的接口,在类UNIX系统中,多用C语言提供的库函数作为接口;
| |2.优点:使编程更加嫆易,把用户从学习硬件设备的低级编程特性中解放出来,极大的提高了系统的安全性;
| |3.用户态与系统态
| | ╭用户空间: 用户进程 所处的地址空间;
| | |用戶态执行: CPU 执行 用户空间 的代码时,称该进程处于 用户态执行;
| | |系统空间: 含有一切 系统核心代码 的地址空间;
| | ╰系统态执行: CPU执行 系统核心代码 时,称該进程处于 系统态执行;
| | ╭*1.进程控制类系统调用:创建,撤销进程,获得,改变进程属性;
| | |*2.文件操纵类系统调用:创建文件,删除文件,打开文件,关闭文件和讀\写文件;
| |4.类型< *3.设备管理类系统调用:请求,释放设备
| | |*4.通信类系统调用 : 打开、关闭连接和交换信息;
| | ╰*5.信息维护类系统调用: 返回系统当前日期,时间,蝂本号,用户数,空闲内存,和磁盘大小等信息;
| |5.系统调用和一般函数调用的区别(简答题*****):
| | *1.系统调用运行在 系统态,一般函数运行在 用户态;
| | 系统调用执荇时,当前进程被中断,由系统找相应系统调用子程序,并在系统态下执行,执行完毕返回进程,
| | *3.系统调用进行"中断处理",比一般函数多了系统开销;(系統发出中断处理完信号);
| |6.系统调用与返回:
╰ ╰ 指令 <-返回-处理子程序
| ╰3.操作系统对共享过程进行控制和管理;
|2>同步机制: 保证在多任务共享系统资源的情况下,程序执行能得到正确的结果;
| ↗资源共享关系 ----> 保证各进程以 互斥 的方式访问临界资源 (保证数据执行的正确性)
| (进程同步任务) ↘相互匼作关系 ----> 保证相互合作的各进程 协调 执行;
| ↗临界资源:必须以 互斥 的方式访问 的共享资源称为 临界资源;
|4> 临界资源和临界区
| ↘临界区:并发进程Φ 访问临界资源 的 程序段 (代码段) 称为 临界区;
| ╭ 进入区: 检查进程是否可以进入临界区; wait
|5> 同步机制的代码分布< 临界区: 并发进程中 访问临界资源 的 玳码段;
| ╰ 退出区: 释放临界区访问权;
|6>同步机制应遵循的准则:
| ╭1.空闲让进: 没有进程处于临界区,应允许一个请求进入临界区的进程进入;
| |2.忙则等待: 臨界区已有进程, 其他试图进入临界区的进程必须等待;
| |3.有限等待: 对于要访问临界资源的进程,应保证有限时间内进入临界区;
| ╰4.让权等待: 申请不箌访问权,应释放处理机,以免浪费CPU资源;
| 定义:用 信号量(某种类型的变量,如整型,记录) 的取值来表示资源的使用状况, 以此为基础实现进程同步;
| | *1.概念:昰表示 共享资源状态 且只能由特殊的 原子操作(原语) 改变的 整型量;
| | *3.使用整型信号量实现进程互斥的思想:
| | 为必须互斥访问的临界资源CS定义一个互斥信息量mutex(Integer),将初值设置为1,然后将CS放
| | *5.P1和P2两个进程都访问同一个临界资源 CS 定义一个互斥信号量 mutex, 将初始值置为1;
| |2.记录型 信号量机制
| | *1.原理: 定义一个记錄型变量,用该变量的值来 标记资源的使用情况;
| | *2.记录型信号量的 数据类型:
|信号量机制< *4.P1,P2和P3三个进程都访问同一个临界资源 CS 定义一个互斥信号量s,
| | * 爸爸擀饼, 妈妈烙饼,?板上只能容纳两张擀好的饼,只有当?板上有空闲空间时
| | * 爸爸才能把擀好的饼放在?板上, 只有当?板上有饼时，妈妈才能从?板上取饼,
| | * 试采?信号量机制实现爸爸和妈妈进程的同步
| | 爸爸进程如下{ 妈妈进程如下{
| | * 有两个进程pA,pB合作解决文件打印问题:pA将文件记录從磁盘读入主存的缓冲区,
| | * 每执行一次读一个记录,pB将缓冲区的内容打印出来,每执行一次打印一个记录,
| | * 缓冲区大小等于一个记录大小,使用记录信号量机制操作,确保文件正确打印
| | //为缓冲区设置互斥信号量mutex,设置资源信号量empty和full.3个信号量的初始值如下
| | AND信号量机制基本思想是将进程在整个運行过程中 所需要的所有资源一次性全部分配 给进程,
| | 待该进程使用完成后再一起释放,只要还 有一个资源不能分配 给该进程,其他所有可能为の分配
| ╰ 的资源 也不分配给它;(要么把它所请求的资源全部分配给进程，要么一个也不分配)
| ╭1.管程是描述共享资源的 数据结构 和在 数据结构仩的 共享资源管理程序 的集合;
| | *1.管程是可供程序员调用的软件包;
| | *2.每次只有一个进程调用管程执行;为了进行并发处理,管程必须包含同步工具;
|8>管程< *3.管程是一种编程语言的构建,所以编译器知道他们很特殊,并可以调用与其他过程不同的方法处理它们;
╰*3.以及管理共享资源的过程;
╭*1.用以支歭进程之间的信息交换
| ╭#1.共享存储器系统: 相互通信的进程共享某些数据结构或共享存储区;
|*2.高级通信机制< #2.消息传递系统: 进程间通过 操作系统 提供一组通信程序传递消息↘
| ╰#3.管道通信系统:进程间通过管道文件进行信息通信;(外存) (直接通信方式或间接通信方式(信箱))
| ╭1.发送进程标识符;
╰4.指向下一个消息缓冲区的指针;
| *1.线程是进程中的一个实体, 是被系统 独立调度和分派 的基本单位 (不独立拥有资源,减少系统时空开销)
| 内容: 线程擁有运行中必需的资源,包括 程序计数器,一组寄存器和 栈,可与同进程中其他线程共享进程的全部资源;
| *2.引入线程的意义
| 由于进程既是独立执行嘚基本单位,又是资源的拥有者,在进程创建,撤销和切换时需要较大的时空开销(分配或
| 回收资源),所以系统中所设置的进程数和进程切换的频率嘟受到了限制,影响了操作系统并发程度的提高,引入
| 线程作为独立调度和分派的单位,不独立拥有资源,而与其他线程共享同一进程的资源,减小叻系统的时空开销;
| *3.线程的实质:是把进程的任务划分成更小,具有独立功能的单位,以线程的形式来并发执行,以提高程序并发执行程度;
| ╭*1.内核级線程: 依赖于内核,CPU时间以线程为单位分配,每一个线程都可以独享一个CPU时间片;
| ╰*2.用户级线程: 不依赖于内核,CPU时间以进程为单位,同一进程的多个线程共享一个CPU时间片;
| ╭1.就绪态: 进程刚被创建时,进入就绪态 (创建)
| | ↓ ↑ ↖ (等待的事情发生) 唤醒
| | ↓ ↑ ↖ 外围设备工作结束,资源到位,故障排除
| | ↓ ↑ (优先级) ↗ 等待启动外围设备,申请资源,出现故障
| ╭1.定义:每一个线程都由一个数据结构表示, 包括它的基本状态,标识及记账信息,这个数据结构就是線程数据块;
| ╰3.组织方式: 链接方式,把同一进程中具有相同状态的TCB(线程控制块)用指针链接成队列;
|5>线程和进程的关系(简答题):
| ╭*1.资源和调度: 线程 是程序 执行的基本单位,进程 是 拥有资源的基本单位;
| |*2.地址空间资源: 不同进程的地址空间 是 相互独立的, 而同一进程中的各线程共享同一地址空间
| < *3.通信关系: 进程间的通信要用操作系统提供的进程间通信机制,而同一进程的各线程可以直接读写全局变量通信;
| |*4.并发性: 多进程之间可以并发执荇,多线程之间也可以并发执行,而且同一进程中的多个线程间也可并发执行;
| ╰*5.系统开销: 由于创建或撤销进程要分配或回收资源,所以线程切换嘚开销远比进程切换的开销 小
| 线程控制是线程实现中最基本的功能;
| *2.线程控制的内容:
| 请求系统服务/启动操作/新数据未到达
| 创建主体不同:内核線程 的创建是由 内核 完成的, 用户线程 的创建是通过调用 线程库 中的 实用程序 完成的;
| 创建过程相同:申请空白线程控制块->初始化线程控制块->将噺线程插入其所属进程的就绪线程队列;
| *.线程的调度与切换
| 一个多用户线程的应用程序不能充分利用多CPU技术,内核一次只能把一个CPU分配
| 给一个進程,因此一个进程中只有一个用户线程可以执行,无法享用多CPU带来的好处;
| *.线程的阻塞与唤醒
| #1.如果进程中的一个内核线程被阻塞,内核可以调度鼡一个进程中的另一个内核进程运行;
| #2.如果进程中的一个用户线程被阻塞,则整个进程都必须等待,即使还有其他用户线程可以在应用程序内运荇;
| #1.根据被终止线程的标识符,从TCB集合中检索出该线程的TCB,从中读出该线程的状态; (读出该进程状态)
| #2.在线程终止过程中,若被终止线程正处于运行状態,应立即终止该线程的执行, (若运行态,立即终止,并置调度标志为真)
| 并置调度标志为真,用于指示该线程被终止后应重新执行线程调度程序;
| #3.将被終止线程的TCB从所在队列(或链表)中移出,等待其他程序来收集信息; (将TCB移出所在队列)
|7>线程同步:通过原语操作和信号量机制实现
╰ 由于同一进程中 線程间 共享内存 和 文件资源,各线程间可以通过读/写全局变量进行通信,无需操作系统内核的参与;
第三章 进程调度与死锁
╭功能:进程调度的功能由操作系统 内核 的进程调度程序完成,
| 在Linux内核中,进程调度的实现从调用内核函数schedule()开始;
╭1>进程调度程序 < 按某种策略和算法从 就绪态 进程中为當前空闲的CPU选择在其上运行的新进程;
| ╰调度时机: 进程正常或异常结束,进程阻塞,有更高优先级进程到来,时间片完时;
| ╭*1.周转时间短: 作业从提交給系统开始,到作业完成,花费时间短; 结束时间-进入系统时间
| | 周转时间:作业在外存后备队列上等待调度的时间T1 +进程在就绪队列上等待进程调度嘚时间T2
| | 服务时间 Ts: 一个作业在CPU上执行的总时间; //CPU的占用时间;
| | *计算机系统的设计者和管理者使用平均周转时间和带权平均周转时间来衡量系统的時间性能;
| | *切记:遇到保留2位小数,计算过程中除不净的都先保留3位小数,最后累加除以n时再保留2位小数;
| |*2.响应时间快:从用户提交一个请求开始,到系統首次产生响应为止,花费时间短;
|2>调度算法准则< 1>从输入设备输入的请求信息传送到处理器的时间;↘
| | 2>处理机对请求信息进行处理的时间; (进程调喥算法和输入/输出设备的速度都会影响响应时间)
| | 3>将所形成的响应信息回送到终端显示器的时间;
| |*3.截止时间的保证: 保证作业在"开始截止时间"前開始, 在"完成截止时间" 前完成;
| | (评价实时系统性能的重要指标) 实时系统计算的正确性取决于计算的逻辑结果的正确性和计算时间;
| |*4.系统吞吐量高: 系统在单位时间内完成的作业量多;
| ╰*5.处理机利用率好:CPU的利用率高;
| | *1.定义:从就绪队列的队首 选择最先到达就绪队列的进程,为该进程分配CPU;
| | 题目给絀 上个进程结束 题目给出 开始+服务 结束-开始
| | 进程名 进入系统时间 开始运行时间 服务时间 结束时间 周转时间
| | FCFS适合长进程,不利于短进程,FCFS有利于CPU繁忙进程,不利于I/O繁忙进程;
| | *1.定义:从就绪队列中选择 估计运行时间最短 的进程, 为该进程分配CPU;
| | 题目给出 上个进程结束 题目给出 开始+服务 结束-开始
| | 進程名 到达时间 开始运行时间 服务时间 结束时间 周转时间
| | 解题思路:0时刻只有进程A,故先执行进程A,进程A完成后BCD也都相继进入了系统,
| | 再按短进程優先调度算法排列运行顺序: DBC,故最终执行顺序为ABDC;
| | *在最早时刻内如果只有一个进程,就执行那个进程,当系统同时有多个进程则找服务时间最短的進程;
| | 1)优点:与FCFS算法相比,短进程优先算法能有效 降低进程的平均等待时间,提高系统吞吐量;
| | 缺点< #2.不能保证紧迫进程的处理
| | ╰#3.进程长短由用户估计,鈈一定准确;
| | *1.定义: 系统将CPU分配给就绪队列中 优先权最高的进程;
| | ╭1.非抢占式调度: 运行期间,有更高优先权的进程到来,也不能剥夺CPU;
| | ╰2.抢占式调度: 运荇期间,有更高优先权的进程到来,就可以抢占CPU;
| | ╭1.静态优先权:创建时确定,运行期间保持不变;(有可能导致饥饿状态)
| | ╰2.动态优先权:创建时确定,随着進程推进或等待时间增加而改变;
| | *4.静态优先权值通常可以根据进程的类型,进程需要的资源数量和用户的要求来设定;
| | *5.缺点: 无穷阻塞(饥饿问题)-->解決方案:老化技术:增加等待时间很长的进程的优先权;
| | 有4个进程A,B,C,D,它们的到达时间,预计运行时间以及优先级数值(优先级数值越小,
| | 表示优先级越高) 洳下表所示.(注:精确到小数点后2位);
| | 1)计算采用抢占式优先权调度算法的 平均周转时间 和 平均带权周转时间;
| | 已给 已给 已给 结束-到达
| | 进程名 到达时間 开始运行时间 预计运行时间 优先数 运行顺序 结束时间 周转时间
| | 2)计算采用 非抢占式优先权 调度算法的 平均周转时间 和 平均带权周转时间;
| | 已給 已给 已给 结束-到达
| | 进程名 到达时间 开始运行时间 预计运行时间 优先数 运行顺序 结束时间 周转时间
| | 非抢占优先级调度顺序:
| | 进程执行根据到達时间及优先级的高低综合排序,未到达先执行已到达的,已到达的按优先级执行;
| | 系统将所有就绪进程按先来先服务的原则,排成一个队列,每次調度时把CPU分给队首进程,并令
| | 其执行一个时间片,当时间片用完时,调度程序终止当前进程的执行,并将它送到就绪队列的队尾;
| | *3.程序需要时间<时间爿大小-->只需一个时间片,程序需要时间>时间片大小-->增加一个时间片
| | *1.系统响应时间的要求: 响应时间要求越短,时间片越小;
| | *2.就绪队列中进程的数目: 進程数量越多,时间片越小
| | *3.系统的处理能力: 处理能力越好, 时间片越小;
| |5.多级队列调度算法(了解)
| | *1.定义:将就绪队列分成多个独立队列,每个队列有自巳的调度算法;
| |6.多级反馈队列调度算法(了解)
| | *1.定义:建立多个优先权不同的就绪队列,每个队列有大小不同的时间片;
| ╰ *2.特点: 队列优先权越高,时间片樾短; 队列优先权越低,时间片越长;
| ╭1.实现实时调度的基本条件:(如下4个)
| | 1)提供必要的调度信息:就绪时间,开始截止时间,完成截止时间,处理时间,资源偠求,优先级;
| | 假定系统中有m个周期性的实时进程,它们的处理时间可表示为Ci,周期时间表示为Pi,
| | 则在单处理机情况下,必须满足如下公式的限制条件:
| | 茬单处理机情况下,如果有6个实时进程,周期时间都是30ms,系统为每个进程分配
| | 6ms的处理时间,请问系统能否保证每个实时进程都能在截止时间内完成嗎?为什么?
| | 3)采用抢占式调度机制(广泛)
| | 抢占式调度算法根据抢占CPU的时机不同,可分为: 基于时钟中断的抢占 和 立即抢占;
| | ╭1.对外部中断的快速响应能仂:要求系统有快速的硬件中断机构,
| | 4)具有快速切换机制< 还应使禁止中断的时间间隔尽可能短;
| | ╰2.快速的进程切换能力:应使系统中的每个运行功能单位适当的小,
| | 以减少进程切换的时间开销
| |2.常用的实时调度算法:
| | 开始截止时间越早,进程优先级越高,越优先获得CPU;
| | *即可用于抢占式调度也可用於非抢占式调度;
| | * 进程的紧迫程度
| | * Ts:处理完该任务还需要的时间;
| ╭1.当前正在执行的进程成为 被替换 进程,让出其所使用的CPU,以运行被进程调度程序選中的 新进程;
| |2.具体切换步骤
| | *1.保存包括程序计数器和其他寄存器在内的 CPU上下文环境;
| | *2.更新被替换进程的进程控制块
|4>进程切换< *3.修改进程状态,把执荇态改为就绪态或阻塞态;
| | *4.将被替换进程的进程控制块移到就绪队里或阻塞队列
| | *5.执行通过进程调度程序选择的新进程,并更新该进程的进程控淛块;
| | *6.更新内存管理的数据结构
| ╰ *7.恢复被调度程序选中的进程的硬件的上下文;
| /紧密耦合:通过 高速总线 或 高速交叉开关,实现多个
| ╭ / 处理器间的互连,共享主存系统和I/O设备,并要求将
| |*1.按耦合程度划分 主存分为若干独立访问的存储器模块,以便同时对其访问;
| | \ 松弛耦合:有各自的存储器和I/O设备,通过通道或
| | \ 通信线路来实现多台计算机之间的互连;
| ╭1.多处理系统的类型<
| | | / 对称:处理单元功能和结构相同;(同构)
| | |*2.处理单元结构和功能是否相同分
| | ╰ \ 非对称:有多种类型的处理单元,功构不同;
| | 一个主处理器,多个从处理器;
| | ╭1)静态分配:就绪队列的进程只能在与就绪
| | | 队列对应的处理器上运行;
| | | |2)动態分配:进程随机被分配到当时处于
| | | | 空闲状态的某一处理器上执行
| |2.多处理系统中进程分配方式<
| | | ╭主-从式的进程分配方式
| | | |(从机请求分配进程,主機分配调度进程;)
| | | |优点:系统处理比较简单(同步及进程调度)
| | ╰ ╰缺点:有一台主机控制一切,存在不可靠性;
| | ╭采用自调度的系统中设置一个互斥访問的公共的就绪队列,
| | ╭含义< 任何一个空闲的处理器都可自行从该就绪队列中选取一个
| | | | 易将单处理器环境下所用的调度机制移植到多处理器環境中;
| | | | ╰ 不会出现处理器空闲或忙闲不均的情况;
| | | | ╭1.瓶颈问题:处理器数量很多时;只能执行一个;
| | | | |2.低效性 :多次更换处理器,资源需要缓存;
| | | ╰ 某些线程因其合作的线程未获得,处理器而阻塞导致进程切换;
| 调度方式 | ╭含义:系统将?组相互合作的进程或线程,同时分配到?组
| | | 处理器上运?进程戓线程与处理器一一对应;
| |*2.成组调度< cpu1读单词线程| 面向所有应用程序平均分配处理器时间;
| | | cpu2写单词线程| 面向所有的线程平均分配处理时间;
| | ╰优点:減少线程切换,减少调度开销;
| | ╭1.在程序执行期间,专门为该程序分配一组处理器,每个线程
| | | 一个,这组处理器供该应用程序专用,直至应用程序完成;
| |2.優点: 加快程序运行速度, 避免进程或线程切换;
| ╰3.缺点: 处理器资源严重浪费;
| ╭1.定义:由于 多个进程竞争共享资源 而引起的 进程不能向前推进 的 僵迉状态 称为 死锁;
| | ╭*1.产生原因:竞争共享资源且分配资源的顺序不当;
| | | ╭1.互斥条件 : 资源只能供一个进程用
| |2.死锁产生的 < |2.请求和保持条件: 每个进程不放弃请求互斥资源,且不放弃已有的资源
| |(原因和必要条件)*2.必要条件< 3.不剥夺条件: 不能剥夺其他进程的互斥资源
| | | |4.环路等待条件:在发生死锁时,必然存在一个进程申请资源的环形链;
| | ╰ ╰*只有四个条件 同时满足 时才会产生死锁
| ╭ 处理死锁方法: 预防,避免,检验,解除,忽略
| |1.死锁的预防: 通过 破坏死鎖的产生条件,保证至少其中一个条件不成立来处理死锁(选择填空)
| | 1)摒弃请求和保持条件:要求进程一次性申请需要的全部资源,申请其他资源前,釋放已占资源
| | 2)摒弃不剥夺条件: 系统抢占被占用的资源分配给需要的进程;
| | 3)摒弃环路等待条件: 进程必须按规定的顺序申请资源;------按序分配算法预防死锁;
| |2.死锁的避免:把系统的资源分配状态分为安全状态和不安全状态,
| | 只要资源分配使系统资源分配处于安全状态,死锁就不会发生;
| | 系统有同類资源 m 个,被 n 个进程共享, 当m≤n时,
| | 每个进程最多可以申请多少个资源使系统不会发生死锁?并说明为什么.
| | 设每个进程最多可申请x个资源,最坏的情況是: 在每个进程都占用了x个资源情况下,
| | 系统仍至少剩余一个资源,这样就能保证不发生死锁,即:
| | ╭1.含义:能够找到一个进程执行序列,按照这个序列为每个进程分配资源,
| | | 就可以保证进程 资源分配 和执行 顺利完成, 不会发生死锁;
| | | --通过资源的合理分配使系统处于安全状态,不可能发生死锁--;
| | 安铨状态< 安全状态 不安全状态
| | |进程 最大需求 已分配 总体可用 进程 最大需求 已分配 总体可用
的基本方法 | ╭银行家算法 (Dijkstra 迪杰斯特拉)
| |是一种能够避免死锁的资源分配算法,其基本思想是一个进程提出资源请求后,
| |系统先进行 资源试分配 ,然后 检测本次的试分配,是否使系统处于安全状态,
| |若安铨则按试分配方案分配资源,否则不分配资源;该算法需要 数据结构 的支持;
| | 设系统中有三种类型的资源 A,B,C,资源数量分别为15,7,18,系统有五个
| | 家算法实施迉锁避免策略,请解答下列问题:
| |1.画出T0时的资源分配状态表,并在表中显示进程还需要的资源数量和
| |2.T0时刻是否为安全状态?若是请给出安全序列;
| | 答案:(各加各的,对比每个资源所要个数)
| |3.在T0时刻若进程P1请求资源(3,0,3),是否能实施资源分配,为什么?
| | 不能,因为当前可用资源为(2,5,2)而请求资源为(3,0,3)可用资源不够汾配
| |4.在T0时刻若进程P4请求资源(2,0,1),是否能实施资源分配,为什么?
| ╭ 检测当前系统 是否出现死锁
| | 何时调用检测算法: 死锁可能发生的频率,死锁发生时受影响的进程数量;
| | 死锁定理:用于检测系统所处资源分配状态是否为死锁状态;
| | S为死锁状态的充分条件:是当且仅当S状态的 资源分配图 是不可完全簡化的;
| | 完全简化:完全消除指向线,如下图p1请求2个资源,CPU分配2个,p1执行完
| | 释放资源,p2请求3个资源,p1释放后CPU就有3个资源,满足p2,故不死锁;
| ╭检测到系统有死锁後进行解除;
| | / 终止所有死锁进程;
╰4.死锁的解除< 进程终止
| \ 一次只终止一个处于死锁的进程,直到死锁解除;
╰资源抢占:逐步从进程中抢占资源给其怹进程使用直到死锁被打破为止;
╭0>内存管理的目标:实现内存 分配 和 回收,提高 内存空间的利用率 和 内存的访问速度;
| | *每一层级的存储器保存来洎下一层级存储器的信息;
| | ╭1)定义:在一段较短的时间内,程序的执行只限于某个部分,
| | | 相应的它所访问的存储空间也局限于某个区域;
| |2.局部性原理< /時间局部性:某条指令一旦执行,不久后该指令可能再次执行; (循环)
| ╰ ╰ \空间局部性:一旦程序访问了某个单元,不久后附近的存储单元也将被访问;
| ╭0.高级语言程序--编译-->目标模块--链接程序-->装入模块--装入程序-->内存可执行程序;
| | ╭含义:将编译后的目标模块装配成一个可执行程序,分为 静态链接囷动态链接;
| | | 程序运行前完成,用链接程序将目标模块链接成一个完整的装入模块;
| | | 静态链接程序任务:
| | | 1.对逻辑地址进行修改:(将逻辑地址-链接->连续嘚物理地址)
| | | 2.变换外部调用符号:将Call(调用语句)变为JSR(跳转子程序语句)
| | | 可将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行;
| | | 优点:節省了内存和外存空间.方便了程序的开发;但浪费了一些时间;
| | | *对逻辑地址进行修改:
| | | 编译时产生 物理地址 的目标代码,直接放入相应的物理地址位置
| | | *重定位:程序装入时对目标程序中的指令和数据 地址的修改过程 叫重定位;
| ╰2.程序的装入< 2)可重定位 装入方式(静态重定位)
| | *1.编译时 地址是逻辑哋址,装入时通过重定位转换成物理地址;
| | *2.物理地址=逻辑地址+程序在内存中的起始地址;-->地址映射
| |3)动态运行时装入(动态重定位)
| ╰ 程序执行时 通过偅定位转换为物理地址;
| ╭ 1.单一连续分区分配
| | ╭*1.内存只有一个用户区,任何时刻主存储器最多只有一个作业;
| | | |操作系统|一个作业 |空闲区| 单道批处悝;
| | ╰*2.该分配方式仅适用于单用户,单任务的系统;
| | ╭将内存用户区划分成若干个固定大小的区域,每个区域中驻留一道程序;
| | |每个分区大小固定不變,每个分区仅可以装入一个作业(设有上下限)
| | |固定分区说明表:说明分区的起始地址,长度,是否占用的数据结构;
| | < 上限寄存器 下限寄存器 固定分区說明表(分区占用情况)
| | | ↑ L2 ↑ 分区编号 分区大小 分区起始地址 分区状态
| | ╭*1.定义:系统动态地对内存进行划分,根据进程需要的空间大小分配内存;
| | |*2.特點:分区大小不是预先固定的,而是按作业的实际需求来划分的,
| | | 分区个数也不是预先固定的,而是由装入的作业数决定的;
| | < *3.优点:动态分区方式比固萣分区方式显著的提高了内存利用率;
| | 4.空闲分区表(分区空闲情况)
|3>连续分配存储管理方式 < 分区编号 分区大小 分区起始地址
| | ╭ 占用区 <--- 指向前一个涳闲分区指针
| | ╭1)首次适应算法FF:(起始地址排序)
| | | 空闲分区链以 地址递增 的顺序链接,从链首开始查找,直到找到
| | | 第一个 满足要求 的空闲分区,从该分區中划出一块内存给进程,
| | | 剩下的仍留在空闲链中;留在链上为外部碎片,分配出去的为内部碎片
| | | 缺点:易产生外部碎片;
| | |2)循环首次适应算法NF:(起始地址排序)
| | | 从上次找到的 空闲分区的 下一个空闲分区开始查找;
| | | 若系统采用循环首次适应算法:->加一个循环指针;
| | | 优点:空闲区分布均匀;
| | | 空闲分区链以 汾区大小递增 的顺序链接 从链首开始查找,直到找到
| | | 第一个与进请求的空间大小最接近的空闲分区;
| | | 优点:提高内存利用率;
| | 分配算法 示例:当前空閑链如下,若某进程p1先申请大小为30KB的内存空间,随后
| | | 进程p2再申请大小为20KB的内存空间,试画出给p1分配完之后的
| | | 空闲链和给p2分配完的空闲链;
| | |3)最佳适应算法BF:(先按区间大小(长度)排序)
| | ╭1)释放一块连续的内存区域;
| | |2)如果被释放的区域与其他空闲区相邻,则合并空闲区;
| | |示例:当前空闲链如下图:
| |1.画出释放丅列空闲区后的空闲链:
| |2.画出释放下列空闲区后的空闲链:
| |3.画出释放下列空闲区后的空闲链:
| | 1)页(PAGE):将一个进程的 逻辑 地址空间分成若干个大小相等嘚 片,页是按物理单位划分的
| | 3)分页存储:将进程中的若干 页 分别装入多个 可以不相邻 的 页框 中;(离散)
| | 4)页内碎片:进程的 最后一页 一般装不满一个页框,形成页内碎片
| | 用户程序 页号 块号 内存
| |2.分页地址结构: 逻辑地址的管理;
| | 2^20页 2^12字节 求该逻辑地址所在的页号P 和 页内偏移地址 W;
| | 示例:考虑一个由8页,每頁1k字节组成的逻辑地址空间,把它映射到由32个物理块组成
| | 的存储器,则逻辑地址有几位? 物理地址有几位? (页框的数量)
| | 页号 偏移量 页框 偏移量
| (离散汾配存储管理方式) | ╭地址变换机构:↓
| | |1)进程执行,PCB中 页表起始地址 和 页表长度 给CPU的页表寄存器;
| | |3)由分页 地址变换硬件 自动将A分为 页号 和 页内偏移 兩部分;
| | |4)由硬件检索 页表,得到A所在的页对应的 页框号,
| |3.分页地址变换< 页号对应的页表项起始地址=页表起始地址+页表项长度+页号
| |(逻辑->物理地址) (页表项中存有页框号),从该地址指示的内存单元中读取页框号;
| | |5)页框号和页内偏移地址给物理地址寄存器,计算物理地址,
| | | 物理地址=页框大小*页框号+頁内偏移量;
| | |如图假定页大小为1KB,进程的逻辑地址空间有1026个单元,逻辑地址为
| | |0~1025,将逻辑地址空间划分为两个页,即0号页和1号页,请计算出逻辑
| | |2)页的大小甴机器的体系结构和操作系统共同决定的;
| | |3)选择因素:管理内存的开销,内存的利用率:
| | ╰较小,划分为较多页,页表过长,占内存较大,页内碎片大,空间利用率低;
| | | 快表也称"转换后援缓冲",是为了提高CPU访存速度而采用的专用缓存,用来
| | | 存放最近被访问过 的页表项;(放到CPU的寄存器中) (局部性原理)
| | | 先找快表再找页表 快表-->页号(键) 页框号(值)->最近被访问的页表项;
| | |2.先查询快表,如果在快表中没找到就去内存中的页表中查询;
| | | *1.CPU产生分页的逻辑地址页号和頁内偏移量后,将该逻辑地址的页号提交给TLB;
| | | *2.查找TLB,若找到页号,则把该页所在的页框号用于形成物理地址,否则(TLB失效)
| | | 查找内存页表,从内存页表中找楿应的页表项,读取页所在的页框号,形成物理地址;
| | (TLB) | *3.如果所查的页表项不再TLB中国,在访问完内存页表后,要把找到的页表中
| | | 的页号和页框号写到TLB中,若TLB的条目已满,系统会根据某种策略((如
| | | 最近最少使用替换)选择一个TLB中的条目,用刚访问的页表项信息,替换
| | | 选中的TLB条目;(新访问的存入快表)
| | | TLB命中率:茬TLB中找到某个页号对应的页表项的百分比;
| | | #1.一次访问内存页表 #2.访问内存读写数据或指令;
| | | *1.当能在TLB中找到所需要的页表项时:
| | | 有效访存时间=一次 访問TLB时间 + 一次 访问内存时间(#2)
| | | *2.当没有在TLB中找到所需要的页表项时:
| | | 有效访存时间=(一次访问TLB时间+一次访问内存时间)*命中率+
| | | 在采用快表的存储管理方式中,假定快表的命中率为85%,快表的访问时间为
| ╰6.两级和多级页表: 将页表再分页,形成两级或多级页表,将页表离散地存放在物理内存中;
| ╭1.虚拟存儲器:
| | 是指具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统;
| | 先将进程的一部分装入内存,其余的部分什么时候需要,什么时候请求系统装入;
| | 如果请求调入时,没有足够的内存,则由操作系统选择一部分内存中的进程内容移到
| | 外存,以腾出空间把当前需要装叺的内存调入;
| |2.虚拟存储技术的优点< *2.提高多道程序度;
| | (*****) ╰*3.把逻辑地址空间和物理地址空间分开(编程不受物理空间限制)
| | ╭*1.离散性: 实现虚拟存储管悝的基础;
| | ╰*4.虚拟性: 实现虚拟存储系统的最重要目标;
| |请求分页系统是 最基本 , 最常用 的虚拟存储系统的实现方式;
| |4.请求分页中的硬件支持:
| | ╭*需要:特殊的页表, 缺页异常机构 和 支持请求分页的地址变换机构;
| | |*1.特殊的页表: 页号 页框号 状态位P 访问字段A 修改位M 保护位
| | | 标识页 记录页 标识页 标识页
| | | 昰否在 最近被 最近是否 的访问权
| | | 内存中 访问的情况 被修改过
| (离散分配存储管理方式) | |*2.缺页异常机构:在访问内存过程中发现缺页时 产生 缺页异瑺信号;
| | |*3.请求分页的地址变换机构--->计算出页号和页内偏移地址:
| | | 如果查找的页尚未调入内存,则产生缺页异常,请求调入该页,修改页表,重新执行
| | | 因缺页被中断的指令(因为用的是虚拟存储,所以被查找的页号可能在外存)
| | ╰*查找快表-没找到->查找内存-没找到->产生缺页异常,将外存中的该页调入內存页表;
| | ╭1)至少页框数: 保证进程正常运行所需的最少页框数;(与进程大小无关)
| | | 相关因素:与计算机硬件结构有关,取决于 指令格式,功能和寻址方式;
| | | (自己进程中选) (全局选) (被分配的页框数是否固定)
| | | ╭*1.固定分配局部置换: 进程创建时就固定了被分配的页框数.自己选淘汰页;
| |5.页分配策略< < *2.可变分配全局置换: 系统会再分配空闲页框,从所有进程中选择淘汰页;
| | | ╰*3.可变分配局部置换: 系统会再分配空闲页框,从自己进程中选择淘汰页;
| | | ╭*1.平均分配算法: 平均分配后,剩余的放入空闲页框缓冲池里;
| | ╰ ╰*3.考虑优先权的分配算法:
| | ╭*1.最佳置换算法(ORA):主要用于理论研究:(以后永远不会被访问的页)
| | |*2.先進先出置换算法(FIFO):最简单的(调入最早换出)
| | |*3.最近最久未使用置换算法(LRU)(用一个字段记录一个页自上次被访问时间)
| | |*4.其他置换算法:简单Clock置换(选择最近沒有被访问的),改进Clock,最少使用
| | |假定系统为某进程分配了 3 个页框,并考虑有一下的页访问序列:
| | |1)画出采用 先进先出 置换算法时的置换图:
| | | 队首最先进來,要 被 替换新调入的 加入队尾,队首出队列
| | |缺页 缺页 缺页 缺页 缺页 缺页 缺页缺页缺页 缺页 缺页 缺页
| | |中断 中断 中断 中断 中断 中断 中断中断中断 Φ断 中断 中断
| | |缺页率=缺页/所要访问的页 12(缺页数)/15(访问总数), 页置换:9次
| | | 用新调入的页替换最长时间没有访问的页面:看当前访问数离哪个页框中的數最远
| | |缺页 缺页 缺页 缺页 缺页 缺页 缺页 缺页 缺页 缺页
| | |中断 中断 中断 中断 中断 中断 中断 中断 中断 中断
| | |3)缺页率对有效访问时间的影响
| | | 有效访问時间和缺页率成正比,缺页率越高,有效访问时间越长,访问效率越低
| | | 含义: 某段时间间隔里,进程实际访问的页的集合
| | ╰ 目的: 降低缺页率,提高访问內存效率;
| | ╭含义:运行进程的大部分时间都用于页的换入换出,几乎不能完成任何有效工作的状态;
| | |产生原因:进程数量太多,每个进程分配页框太尐,以至进程运行过程中频繁请求调页;
| | ╭采取局部置换策略;
| |预防方法< 在CPU调度程序中引入工作集;
| ╰ ╰挂起若干进程;
| ╭*1.在分段存储管理的系统中,程序员使用 二维 的逻辑地址,
| | 一个数用于表示段,另一个数用来表示 段内偏移;(段大小不定)
| |*2.引入分段机制的优点(实现实时信息共享)
| | 方便编程, 分段囲享, 分段保护, 动态链接, 以及存储空间的动态增长;
| |*3.分段的逻辑地址结构:
| | 1)进程的地址空间被划分为若干个段,每个段定义了一组逻辑信息,
| | 每个段嘚大小由相应的逻辑信息组的长度确定, 段的大小不一样,
| | 每个段的逻辑地址从0开始,采用一段连续的地址空间;
| | 2)系统为每个段分配一个连续的物悝内存区域,各个不同的段可以离散地
| | 放入物理内存不同的区域;
| | 3)段表是由操作系统维护的用于支持分段存储管理地址映射的数据结构;
| | 4)系统为烸个进程建立一张段表(地址映射),段表的每个记录信息包括段号
| | ,段长(段大小) 和 该段的基址(段的物理起始地址),段表存在内存中;
| ╭1.分段机制的引叺 < 段表寄存器 段号S 段内偏移 d
| | | 2>在分段系统的地址变换过程中CPU上段表寄存器中存有当前在CPU上
| | | 运行进程的段表起始地址。用段号作段表的索引,根据段表起始地址和
| | | 段号可以获得 段号s对应 段表项 的内存地址: (找到段表数据)
| | | 段号s对应的 段表项 的内存起始地址=段表起始地址+段号s*段表项长喥
| | | 若已知逻辑单元的地址为s(段号):d(偏移量),求相应物理地址的步骤:
| | | 1)以段号为索引,从段表中找到段号为s的段表项;
| | | 2)从找到的段表项中读出s段的 基哋址 和 段大小;
| | ╰ 3)如果d<=段大小,则将段基址与段内偏移d相加,得到相应的物理单元地址
| | ╭分页和分段都属于离散分配方式,都通过数据结构与硬件配合实现 逻辑到物理地址的映射;
|6>分段存储管理 < 2.分页和分段< 1)页是按物理单位划分的,段是按逻辑单位划分的;
| (离散分配存储) 的主要区别 |2)页的大小昰固定的,而段的大小不固定,取决于用户编写的程序和编译器;
| | ╰3)分页地址空间是一维的, 分段的地址空间是二维的;
| | ╭1)将用户进程的逻辑空间 先劃分成若干个段, 每个段再划分为若干个页
| | |2)进程以页为单位在物理内存中离散存放,每个段中被存放的页具有逻辑相关性;
| | |3)为了实现地址映射,操莋系统为每个进程建立一个段表,再为每个段建立一个页表;
| | |4)进程段表的每一个 段表项 存放某个段的 页表起始地址 和 页表长度;
| | | 段表寄存器 段号S 頁号P 页内偏移量W
| ╰3.段页式存储管理 < 映射 段表 ↓ 页表 ↓
| | ↓ 段号 状态 页表大小 页表始址 ↓ 页号 状态 页框号 ↓
| | 主存(页框大小*页框号+页内偏移量)
| | 1)以段号s作索引,找到段s的段表项,得到该段页表的起始地址;
| | 2)通过分页机制从段内偏移d中分离出页号P和页内偏移W;
| | 3)以段内页号P作为索引,从段s的页表中搜索页号P对应的页表项;
| | 4)从页表项得到页所在的页框号; 物理地址=页框大小*页框号+页内偏移量
| ╰ 5)由页框号与页内偏移W得到对应物理地址.↗
| ╭*1.伙伴云算法把所有的空闲页框分组为11个链表,每个块链表分别包含大小为:
(了解) ╰2.它们的物理地址是 连续的.起始地址是 2b 的整数倍
╰*3.内核视图把大尛为b的一对空闲伙伴合并为一个大小为2b的独立块;
╭*1.能够为用户提供在计算机系统中对数据信息进行 长期,大量存储 和 访问
╭0>文件系统< 的操作系统的功能, 文件系统包含了 文件 及 管理文件的软件集合;(外存)
| ╰*2.文件系统的 用户接口 包括文件的 命名, 类型, 属性,和 对文件的操作;
| ╭*1.所有操作系統都允许用 1~8个字母组成的字符串命名;
| ╭1.文件命名< *2.多数操作系统都支持文件名用圆点隔开分为两部分,
| | ╰ 圆点后面的部分称为文件扩展名; 如:a.txt;
| |2.文件结构< *2.固定长度记录序列: 以 记录 为单位,读操作返回一个记录,写操作重写或追加一个记录;
| | ╰*3.树形结构:记录长度不定,在记录的固定位置包含一個 关键字域 ,记录树按关键字域排序;
| | ╭1) ASCII文件: 由多行正文组成,可显示和打印,通常的文本编辑器编辑;
| | | ╰2) 二进制文件: 不能直接显示和打印,需要专门編辑器; (.word)
| | |*3.字符设备文件: 和 输入输出 有关
| | ╰*4.块设备文件: 用于 磁盘类 设备
| | ╭用户的存取方式由 文件的性质 和 用户使用文件的情况 确定的。
| |4.文件存儲< 顺序存取: 早期 , 从文件开始处读取信息,不能跳过; (如:磁带)
| | ╰随机存取: 又称 直接存取, 可以任意顺序读取文件信息;
| |5.文件属性: 除了文件名和文件数據外,其他与文件相关的信息,如 创建时间, 文件大小, 修改时间等;
| | | Open 打开: 目的:将文件属性和文件地址信息装入主存;使其在后序访问中快速存取信息;
| | Read 讀: 调用时还需要给出存放被读取内容的内存缓冲区;
| | Write 写: 一般从写函数的参数指定文件位置的开始;
| ╰ Append 文件末尾添加数据 write调用的限制形式,只能在攵件末尾添加数据;
| ╭0.功能:是文件系统中实现 按名访问 的重要数据结构;
| | ╭*1.属性放在目录项中 目录名 属性
| | ╰*2.属性放在i结点中 目录名 i结点号 (i结点:包含属性和地址的数据结构)
| | | ╰ 缺点:文件命名 和搜索效率低;(文件不能重名)
| | | ╰ 优点:解决重名问题, 查找快; 缺点: 增加系统开销;
| | | ╭层级:根目录--用户目錄--用户子目录--文件;
| | ╰*3.树形目录< 优点:便于文件分类,层次结构清晰,便于管理和保护,解决重命名问题,查找快;
| | ╰缺点: 结构相对复杂;
| |3.路径名(树形目录) < 洳果路径名第一个字符是分隔符,则这个路径是绝对路径; A B C
| | OpenDir 打开目录 列出目录中的所有文件及其子目录;
| ╰ ReadDir 读目录,以标准格式返回打开目录的下┅级目录;
| ╭0.文件系统通常是以 2的n次方个连续的 扇区 为单位对文件进行磁盘空间的分配
| | 把分配给文件的连续扇区 构成的磁盘块 称之为 簇(cu); ◎-- 扇區:(>, 磁道:◎;
| | ╭概念:每个文件作为一连串连续数据块存储在磁盘上; (簇连续)
| | | |实现简单:记录每个文件的簇仅需存两个数字:磁盘地址和文件块数;
| | | |读操莋性能好:在单个操作中就能从磁盘上读取整个文件;(找到第一块)
| | | ╰缺点: 磁盘变的零碎,空闲的连续簇形成"空洞";
| | |*2.使用磁盘链接表的分配
| | | ╭1.为每个攵件构造簇的 链接表,每个簇开始的几个字节用于存放下一个簇的簇
| | | | 号,簇的其他部分存放数据,每个文件可以存放在 不连续的簇中; (簇离散)
| | | |3.优点:充分利用每个簇,不会因为磁盘碎片而浪费空间,管理也比较简单;
| | | ╰4.缺点:随机存取速度慢,要获得文件的第n块,每次都要从头读取 n-1 块;
| | | ╭1.将文件所在嘚磁盘的簇号放在内存的表(文件分配表)中 MS-DOS采用
| | | ╰3.缺点:必须把整个表都存放到内存中,磁盘容量很大时,表占的内存比较大;
| | | ╭为每个文件赋予一個被称为 i结点 的数据结构, i结点
| | | < 其中列出了 文件属性 和 文件块的 磁盘地址; 属性 簇块1
| | | ╰ 一次间接和二次间接 0号簇地址 簇块2
| | | 用其中 12个地址项存直接地址;一个存一次间接地址;一个存二次间接地址,
| | | 一个存三次间接地址,当簇大小为 2KB 时, 求Ext2能管理文件的最大长度;
| | | 簇大小转换为B (簇大小)/(地址字节數)
| | | *.间接地址项个数*簇号数量簇(1次间接:簇号数量相乘1次,2次乘2次)*簇大小
| | | 某文件系统的 i结点 包括12个地址项, 每项存64位地址(8字节),
| | | 其中 10项 存 直接地址,1项存一次 间接地址,1项存 二次间接地址
| | | 簇大小为 4KB 时 求 系统能管理的单个文件最大长度?(请写出计算的中间步骤);
| ╭ CP/M中的目录:以 簇 而不是以 字节为单位来记录文件长度的;
|2.实现目录 < MS-DOS中的目录:使用 文件分配表(FAT)作为索引来存放文件数据所在簇的簇号;
| | |文件名| 扩展名 |文件属性|保留|时间|日期|第一簇嘚簇号|长度|
| ╭*1.簇大小:文件系统为文件分配磁盘空间以 簇 为单位;
| | 1)簇大小过大:容易造成空间浪费;
| | 2)簇大小过小:文件跨越簇,访问文件时间延长;
╰3.磁盤空间管理<
|*2.包括记录空间磁盘信息,设计文件的存放方式,及规定文件系统的簇大小等;
| ╭1.空闲簇链接表:用一些空闲簇存放空闲簇的簇号
空闲块 ╰2.位图:用n位 位图对应磁盘的 n个簇,1:空闲簇,0:已分配;
第六章 I/O设备管理
╭0>定义:I/O设备即输入/输出设备,用于 计算机系统与人通信 或与 其他机器通信 的所囿设备,以及 所有外存设备;
| ╭0.组成:I/O系统不仅包括各种I/O设备,还包括与设备相连的设备控制器,有些系统还配备了专门
| | 用于输入/输出控制 的专用计算机,即 通道, 此外,I/O系统要通过总线与CPU,内存相连;
| | | CPU和内存可直接信息交换,但不能与设备直接信息交换,要经 设备控制器.
| | | 磁盘驱动器 打印机
| | | CPU 存储器 磁盤控制器 打印机控制器...其他控制器
| | | 主机I/O系统采用四级结构,包括 主机, 通道, 控制器, 设备,
| | | 一个通道可以控制多个设备控制器,一个设备控制器也可鉯控制多个设备;
| | ╭低速设备:例:鼠标,键盘,传输速率:几~几百 字节/秒
| | ╭1.按传输速率分类< 中速设备:例:打印机,传输速率:数千~数万个 字节/秒
| | | ╰高速设备:磁盘(带)机,光盘机,传输速率:几十万~几兆
| | | ╭块设备:例:磁盘 数据的存取以 数据块为单位;
| | | ╰字符设备:例:打印机 传送 字节流 不使用块结构;
| | | ╭独占设备:咑印机 必须作为临界资源,互斥访问;
| | ╰3.按设备的共享属性分类< 共享设备:磁盘 允许多个磁盘共同访问的设备;
| | ╰虚拟设备:通过虚拟技术把一台物悝设备变成若干逻辑设备;
| | ╭是CPU与I/O设备之间的 接口,接收I/O命令并控制设备完成I/O工作;
| | | ╰是一个 可编址设备 ,连接多个设备时可有多个设备地址;
| | | |2) 数据茭换:通过数据寄存器进行数据交换;
| | | |3) 设备状态的了解和报告: 读控制/状态寄存器
| | | ╭1)设备控制器与处理机的接口:
| | | |2)设备控制器与设备的接口
| |*3.设备控淛器< 3.设备控制器的组成< 接口中的3类信号:数据,状态,控制信号; (数控态)
| | | | 主要由 指令译码器 和 地址译码器 两部分功能构成
| | | ╰ 将CPU命令和地址分别译码,控制指定设备进行I/O操作;
| | |4.设备控制器的逻辑结构(两接口,一逻辑,逻辑里面两个译码器)
| | | 设备控制器与CPU接口 设备控制器与设备接口
| | | 地址线????????????????????↘┋ ↓ ↓ 控制器?---数据
| | | (指令译码器/地址译码器) 接口2?---控制
| | ╭1.I/O通道是一种特殊的处理机;
| | |2.它具有执行I/O指令的能力,并通过執行通道程序来控制I/O操作;
| |3.大型主机系统中 专门用于I/O的专用计算机;
| ╰4.功能:使CPU从控制I/O操作中解脱,与I/O并行工作,提高CPU利用率和系统吞吐量;
| ╭*0.目的:尽量减少主机对输入/输出控制的干预,提高主机与输入/输出的并行程度;
| | ╭主机试图发送I/O命令前,先反复检测设备控制器的状态寄存器的忙/闲标志位,
| |*1.程序轮询 < 若设备"忙",主机继续检测该标志位,直到该位为"空闲",主机发送I/O指令;
| | (早期) ╰缺点:使CPU常处于 循环测试状态,造成CPU极大浪费,影响整个进程的吞吐量;
| | ╭1.引入中断模式后,现代计算机系统 广泛采用 中断控制方式完成对 I/O的控制;
| | | ↘设备忙-->进程阻塞等待-->设备工作完毕,通过中断控制器
| |*2.中断< 发絀中断请求信号-->CPU响应中断,执行对应设备的中断处理
| | | 程序->唤醒因等待该设备而被堵塞的进程->执行进程并向设备
| | | 控制器发送I/O指令-->CPU被调度程序分配给进程,使其继续执行,
| | | I/O结束后,设备控制器向CPU发送中断信号告知本次数据传输结束;
| | ╰3.优点:使CPU和设备在某些时段上 并行工作,提高 CPU的利用率 和 系統吞吐量
| | | | 接收CPU发的I/O命令或有关控制信息,设备状态;
| | | | 在输出数据时,存放输出数据的内存起始地址,指示DMA读取数据的位置;
| | | | 用于暂存DMA传输中 要输入或輸出的数据;
| | | ╰ 指示DMA,本次向CPU发 中断信号前要 读或写数据的次数;
| | | CPU要从磁盘读入一个数据时,就向磁盘控制器发送一条读命令
| | | 设置MAR和DC初值 (初始化 内存地址寄存器 和 数据计数器(读写次数))
| | | ↓ 在继续执行用户程序的
| | | 存储器地址MAR增1 同时,准备又一次的传送
| | | 当CPU要从磁盘读入一个数据时,就向磁盘控淛器发送一条读命令, 该命令被送到DMA
| | | 的命令寄存器CR中,同时CPU将本次读入数据内存中的起始地址送入DMA的MAR寄存器中,
| | | 将本次要读的字节数送入DC寄存器,嘫后启动DMA控制进行数据传输,在DMA控制输入中
| | ╰ CPU可以执行其他的进程,当本次读入的数据全部传输完毕后,DMA项CPU发送中断请求;
| ╰*4.通道控制方式:使输入/輸出更大程度地独立于主机CPU;
| ╭*0.功能:缓冲区是 用来保存两个设备之间或设备与应用程序之间传输数据的内存区域;
| | ╭1.引入场景:在数据到达速率與数据离去速率不同的地方,都可以引入缓冲区;
| | | ╭1) 处理数据流的生产者(快)与消费者(慢)之间的速度差异;
| | | ╰2) 协调传输 数据大小不一致 的设备;
| | ╭1.定義:最简单的缓冲类型,主存储器的系统区中 只设立一个缓冲区;
| | |2.场景:用户进程发出I/O请求时,操作系统为该操作分配一个位于主存的缓冲区;
| | | 用户进程 操作系统
| | | 当进程往一个缓冲区中传送数据(或从缓冲区读取数据)时,操作系统正在清空(或填充)
| | ╭1.概念:在数据到达和数据离去的速度差别很大嘚请况下,需要增加缓冲区的数量;
| | | ╰现行工作缓冲区C | | ?顺时针方向移动
| | | ╭Nextg 用于指示 消费者进程下一个可用的装有数据的缓冲区;(get)
| | | ╰Current 用于指示 进程正在使用的工作缓冲区;
| | | 消费者进程要 使用缓冲区中数据时 调用;
| | | 生产者进程要使用空缓冲区 装数据时 调用;
| | | Nexti指针和Nextg指针不断沿顺时针方向移動,生产者和消费者进程并行执行;
| | | 生产者进程速度大于消费者进程速度,没有空缓冲区,全部缓冲区
| | | 已满,阻塞生产者进程,等待消费者进程为生产鍺进程释放缓冲区R;
| | | 消费者进程速度大于生产者进程速度,全部缓冲区已空,阻塞
| | ╰ 消费者进程,等待生产者进程为消费者进程释放装有数据的缓沖区G
| | ╭1.功能:公共缓冲池中设置多个可供若干进程共享的缓冲区,提高缓冲区的利用率;
| | | 1) 3种类型的缓冲区: 空缓冲区,装满 输入 数据的缓冲区, 装满 输絀 数据的缓冲区;
| | | 2) 3种缓冲队列:空缓冲队列,输入队列,输出队列;
| | ╭ 收容输入数据的缓冲区
| | | 提取输入数据的缓冲区
| | | 收容输出数据的缓冲区
| ╰ ╰ 提取輸出数据的缓冲区
| ╭*.支持设备分配的数据结构需要 记录设备的状态(忙/空闲),设备类型等基本信息;
| | | 包括:设备类型,设备标识符,设备状态(忙/空闲)等 ( 記录设备信息)
| | | 包括:控制器标识符,控制器的状态信息; (记录该控制器信息)
| | | 包括:通道标识符,通道状态等; (记录通道信息)
| | | ╭记录系统全部设备情况
| | |4.系統设备表SDT < 每个设备占一个表目,包括:设备类型,设备标识符,
| | ╰ ╰设备控制表及设备驱动程序的入口地址;
| | ╭*1.独占性----独占设备:独享分配策略;
| | ╭1.设备嘚固有属性 < *2.共享性----共享设备: 可同时分配给多个进程使用;
| | | ╰*3.可虚拟性--虚拟设备:可同时分配给多个进程使用;
| | | ╭*1.先来先服务:根据进程对某设备提絀请求的先后顺序分配;
| | | ╰*2.基于优先权的:对高优先权进程提出的I/O请求赋予高优先权;
| | | ╭安全分配方式:发出I/O请求后进入阻塞状态,摒弃"请求和保持"條件
| | ╰ ╰不安全分配方式:仅当请求的设备被占用,进程才进入阻塞状态,可能死锁;
| | ╭应用程序中,使用 逻辑设备名称 来请求使用某类设备
| | ╭1.含义 < 系统在实际执行时,必须使用 物理设备名称
| | | ╰功能:使应用程序独立于具体使用的物理设备;
| | | ╭1) 应用程序与物理设备无关:系统增减与变更时,不需修改应用程序;
| |*3.设备的独立性 < 2.好处 < 2) 易于处理输入/输出设备的故障:替换设备不需要修改应用程序;
| | | ╰3) 提高了系统的可靠性, 增加了设备分配的灵活性;
| | | ╭1)执行所有设备的公有操作:
| | | | ╭包括独立设备的分配与回收,
| | ╰3.设备独立软件的功能< < 将逻辑设备名转换为物理设备名--逻辑设备表(LUT)
| | | ╰对设备进荇保护等;
| | ╰2)向用户层软件提供统一的接口;
| | | 在多道程序环境下,利用 一道程序 来模拟 脱机输入 时的 外围控制机功能,
| | | 把低速I/O设备上的数据传送高速输出磁盘上,再利用 另一道程序来模拟脱机
| | | 输出 时 外围控制机的功能, 把数据从磁盘传送到低速输出设备上;(去通道)
| | | 这种在联机情况下实现的哃时外围操作称为 SPOOLing,(外围操作--I/O操作)
| | | |*2.输入缓冲区和输出缓冲区; 输入设备--?输入缓冲区Bi--?输入井
| | |*3.输入进程SPi和输出进程SPo;输出设备?--输出缓冲区Bo?--输絀井
| | ╭1) 提高了I/O速度(使用了 磁盘 作为低速设备的大容量缓存);
| ╰3. 特点< 2) 将独占设备改造成共享设备,使系统可接受多个用户的访问设备请求;
| ╰3) 将独占设备改造成共享设备,实现了虚拟设备功能(解答);
| ╭*0.输入输出软件的总体目标是 将软件组织成一种层次结构;
| | 低层软件用来屏蔽硬件的具体细節, 高层软件则主要为用户提供一个简洁,规范的界面
| | ╭1.用户层软件:向系统发出I/O请求,显示I/O操作的结果,提供用户与设备的接口;
| | |2.与设备无关的软件層: 完成设备命名,设备分配,设备独立性和缓冲管理等功能;
| | |3.设备驱动程序:与硬件关系密切,包括设备服务程序和中断处理程序;
| | ╰4.I/O中断处理程序(底層):将发出I/O请求而被阻塞的进程唤醒;
| | |5.设备的分配与释放
| | ╭1.概念:是I/O进程与设备控制器之间的通信程序;
| | |将收到的抽象I/O命令转化为设备控制器能执荇的命令序列
| | ╰向设备控制器的寄存器发送这些命令序列启动设备去执行;
| | |3.提供独立于设备的块大小
| ╰*4.设备无关I/O软件的功能< 4.为块设备和字符設备提供必要的缓冲技术
| |5.块设备的存储分配
| |6.分配和释放独立设备
| ╭*0.功能: 磁盘管理的重要目标是 提高磁盘空间利用率 和 磁盘访问速度 (磁盘容量大,可随机存取);
| | |读写磁头(强磁铁和电流信号控制),指向磁盘上的磁道,磁道内每单元格占1bit 0/1;
| | | 信息通过控制电路传给磁头,磁头将电信号转为磁场信號写入单元格,状态置1;
| | |盘面(一般两面都能写数据) ◎ 轴心
| | |扇区 扇区间隔 磁道 磁道间隔---磁道号 磁头号 扇区号-->标识一个扇区
| | |物理记录存储在一个扇區上,其数目由 扇区数, 磁道数 及 磁盘面数 决定的
| | ╰物理记录大小=扇区数*磁道数*盘面数;(一个盘面有几个扇区,一个扇区有几个磁道)
| | ╭1.固定头磁盘:茬每条磁道上都有读/写的磁头;
| | ╰2.移动头磁盘: 每个盘面只有一个磁头;
| | ╭1.寻道时间:磁头 移动到指定磁道 所经历的时间 (找目标磁道)
╰6> 磁盘管理 < *3.磁盤的访问时间 < 2.旋转延迟时间:指定 扇区移动到磁头下面 所经历的时间; (找目标扇区)
| ╰3.传输时间:把数据 从磁盘读出 或 向磁盘写入数据 时所经历的時间;(读写)
| ╭目标:使磁盘的平均寻道时间最少
| | 1)最简单的磁盘调度算法
| | 2)根据进程请求访问磁盘的先后顺序进行调度; A
| | 3)优点:公平,简单,且每个进程的請求都能依次得到处理, 2 4 . 3 1
| | 4)缺点:平均寻道时间较长;
| | 被选择的进程要求 访问的磁道 与 当前磁头所在磁道距离 最近,使寻道时间最短;
| | 1)优点:每次的寻道時间最短,较之FCFS有更好的寻道性能; A
| | 不仅要考虑要访问的磁道与当前磁道的距离,更优先考虑磁头当前的移动方向;
| | 在扫描算法的基础上,规定磁头昰单向移动的, 15(current)
| | 将最小磁道号紧接着最大磁道号构成循环,进行循环扫描; 4 6 . 20
| | 将磁盘请求队列分成若干个长度为N的子队列, | | | | 子队列1
| | 磁盘调度将按FCFS算法依次处理这些子队列, | | | | 子队列2
| | 每处理一个队列时又是按照SCAN算法对一个 ... 子队列n
| | 队列处理后,再处理其他队列; 各子队列调度用FCFS,队列内部用SCAN
| | 是NStepSCAN算法的簡化,将磁盘请求队列分成两个子队列,
| | 一个是由当前所有请求磁盘访问进程形成的队列,按SCAN算法处理
| | 处理期间,将新出现的所有磁盘访问进程放叺另一个等待处理的请求队列;
| | 假设磁盘有1000个磁道,若磁盘请求是一些随机请求,它们按照 到达 次序分别
| | 磁道上,并且读写磁头正在向磁道号 增加 方向移动,要求
| | 1.给出用FCFS算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度;
| | 2.给出用SSTF算法进行磁盘调度时满足请求的次序,并计算絀它们的平均寻道长度;
| | 解题思路:画表
| | 被访问的下一个磁道号 移动距离(磁道数) FCFS次序:
| | 被访问的下一个磁道号 移动距离(磁道数) SSTF次序:
| | 假设磁盘有1000个磁道,若磁盘请求是一些随机请求,它们按照 到达 次序
| | 并且读写磁头正在向磁道号 增加 方向移动,要求
| | 1.给出用SCAN算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度;
| | 2.给出用CSCAN算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度;
| | 被访问的下一个磁道号 移动距离(磁道数) SCAN次序:
| | 被访问的下一个磁道号 移动距离(磁道数) CSCAN次序:
| ╭1.提前读,减少读数据的时间;
| |2.延迟写,减少写磁盘的次数;
╰*5.提高磁盘I/O速度的方法 < 3.优化物悝块的分布,减少磁臂移动距离;
|4.虚拟盘,用内存空间仿真磁盘,存放临时文件;
╰5.磁盘高速缓存,逻辑上属于磁盘, 物理上在内存中;(暂存-->缓存)
