操作系统概论
2024-06-26 11:33:45 0 举报AI智能生成
操作系统概论 完整总结 适合面试考试
作者其他创作
大纲/内容
操作系统（OS）是一种复杂的<font color="#000000" style=""><b>系统软件</b></font>，是不同程序代码、数据结构、数据初始化文件的集合，可执行
操作系统提供计算机用户与计算机硬件之间的接口，并<b>管理计算机软件和硬件资源</b>
操作系统为应用程序提供运行环境
与硬件部分相互作用，为包含在硬件平台上的所有底层可编程部件提供服务。
为运行在计算系统上的应用成本（即所谓用户程序）提供执行环境
用户与硬件之间的接口
处理机管理
内存管理
设备管理
文件管理
操作系统的主要功能
资源的管理者
什么是操作系统
操作系统的发展从时间顺序上经历了<b>从无操作系统到单道批处理系统、多道程序系统（多道批处理系统、分时系统）的发展过程</b>
第一代计算机（1945-1955年）使用<b>电子管</b>作为主要的电子器件，用插件板上的硬连线或穿孔卡片表示程序，没有用来存储程序的内存，<b>无操作系统</b>
1946年诞生于宾夕法尼亚大学的第一台实用电子计算机<b>“埃尼阿克”（ENIAC）</b>，<b>无法支持存储程序，不能连续自动工作</b>
无操作系统
第二代计算机（1955-1965年）使用的主要电子器件是<b>晶体管</b>，开始使用磁性存储设备，内外存容量增加，计算机运算速度提高，出现了早期的单道批处理系统。
<b>用户程序及程序处理的数据统称为作业</b>
<b>这一时期的操作系统是单道批处理系统，内存中只能驻留一道用户作业，CPU和内存资源被用户作业独占。<br>程序是指令的集合，程序的执行是CPU依次、逐条执行指令的过程</b><br>
<b>吞吐量是指单位时间内计算机系统处理的作业量</b>
单道批处理系统
随着电子技术的发展，计算机开始采用集成电路芯片作为主要的电子器件，<b>IBM 360</b>是第一个采用小规模集成电路芯片的主流机型，<b>OS/360</b>是IBM开发的一个多道程序系统
早期的多道程序系统<b>不具有交互功能</b>，被称为<b>多道批处理系统</b>。由于不具有交互功能，于是出现了<b>分时操作系统</b>
在分时操作系统的支持下，<b>多个用户可以同时通过不同的终端使用主机</b>，主机可以快速响应常用命令，如程序调试命令。使终端用户感觉自己独占计算机资源，并且<b>实现用户与主机的即时交互</b>。<br>在分时系统中，<b>多个作业交替执行，分时使用主机资源</b>
第一个通用分时系统CTSS是麻省理工学院于1962年在一台改装过的IBM 上开发成功的
多道程序系统
微软的MS-DOS，成为微机操作系统的主流。<br>1985年微软开始构建Windows操作系统
微机操作系统
如：锅炉温度和压力自动控制系统、重病检测系统都属于实时操作系统
实时操作系统
单道批处理系统内存中只有一道作业，可以自动成批处理作业，其特点如下
（1）自动性
（2）顺序性
（3）单道性
由于作业在独占CPU和内存，当作业进行I/O时，CPU只能等待I/O完成而无事可做，使得CPU资源不能得到充分利用
单道批处理系统的特点
在多道批处理系统中，用户所提交的作业都先存放在外存并排成一个队列，该队列被称为“<b>后备作业队列</b>”
（1）多道性<br>
（2）无序性
（3）调度性
（4）复杂性
多道批处理系统的<b>优点</b>是能够提交CPU、内存和I/O设备的利用率和系统的吞吐量<br>多道批处理系统的<b>缺点</b>平均周转时间长，缺乏交互能力
多道批处理系统的特点
分时操作系统允许多个用户通过终端同时使用计算机。
（1）多路性
（2）独立性
（3）及时性
（4）交互性
分时系统的<b>优点</b>是向用户提供了人机交互的方便性，使多个用户可以通过不同的终端共享主机
分时系统的特点
实时系统的<b>优点是</b>
实时系统主要用于<b>实施控制</b>和<b>实时信息处理</b>领域
（5）可靠性
实时系统的特点
批处理系统、分时系统、实时系统的特点
主机操作系统
服务器操作系统
<b>嵌入式操作系统的特征</b>是小巧、实时性、可装卸、代码固化、弱交互性、强稳定性、接口统一、低能耗
应用领域：掌上电脑、智能手机、数码相机、自动售货机、自动取款机、工业控制设备、军工装备、游戏机
嵌入式操作系统
操作系统产品现状
操作系统的发展
现代操作系统都支持多任务，具有<b>并发、共享、虚拟和异步性</b>特征
<b>并发是指两个或多个事件在同一时间间隔内发生</b>；<br>并行是指多个事件同时发生
并发型
<b>共享是指系统中的资源可供内存中多个并发执行的进程共同使用。</b><br>
<b>互斥共享是指任意时刻一种资源只能被一个进程访问</b>。例如打印进的访问
<b>同时共享是指从宏观上看，资源可以被多个进程同时访问，如对磁盘的访问。<br>从宏观上看，磁盘可以被多个用户同时访问</b>
共享性
<b>虚拟是指通过某种技术把一个物理实体变成若干个逻辑上的对应物。</b>
虚拟性
进程以不可预知的速度向前推进。<br><b>内存中的每个程序何时执行、何时暂停、以怎样的速度向前推进，以及每道程序总共需要多少时间才能完成，都是不可预知的</b><br>
异步性
操作系统的特征
<b>内存管理应具有内存分配、内存保护、地址映射和内存扩充功能</b>
采用静态分配方式是把内存划分呈固定大小和数量一定的区域，在系统运行过程中各种分区的大小和数量不再变化。<br>
静态分配内存
采用动态分配方式是在系统运行过程中，根据进程的请求分配内存，内存中分区的大小和数量都是动态变化的
动态分配内存
分配方式
内存分配
一是使操作系统内核的空间不会被用户随意访问，以保证系统的安全和稳定
二是确保每到用户程序都在自己的内存空间中运行，互不干扰
任务
实现内存保护的界限寄存器
内存保护
CPU执行程序过程中访问内存时，需要吧程序的逻辑地址转变为逻辑地址，这个转换的过程成为地址映射
逻辑地址与物理地址
将逻辑地址转换为物理地址
地址映射
内存扩充的任务是借助于虚拟存储技术，从逻辑上扩充内存容量，使系统能够向用户提供比物理内存大的存储空间
内存扩充
进程管理
设备管理主要完成用户的IO请求，为用户分配IO设备
缓冲管理
设备分配
设备处理
设备独立性和虚拟设备
功能
文件存储空间的管理
目录管理
文件读、写管理和存取控制
联机用户接口
脱机用户接口
命令接口
图形用户接口
向程序员提供应用程序与操作系统之间的接口即<b>系统调用</b><br>
程序借口<br>
提供用户接口
操作系统的功能
操作系统的体系结构
程序是指令的集合，程序的执行就是按照某种控制流程执行指令的过程
指令周期
取指令<br>
执行指令
取指令和执行指令
指令的执行
操作系统简介
顺序性
封闭性
可再现性
程序的顺序执行
程序并发执行是指在同一时间间隔内运行多个程序。<br>一个程序执行结束之前，可以运行其他程序。
（1）间断性
（2）失去封闭性
（3）不可再现性
程序并发执行有以下特点
程序的并发执行
<b>程序的并发执行</b>
<b>进程是允许并发执行的程序在某个程序集合上的运行过程</b>
<b>进程是由正文段、用户数据段及进程控制块共同组成的执行环境</b>
进程的定义
（1）并发性<br>
（2）动态性
（3）独立性
（4）异步性
（5）结构特征
进程的特征
<b>程序是静态的；进程是动态的</b>
<b>程序是永久的；进程是暂时的</b>
<b>程序是指令的集合，而进程是包括了正文段、用户数据段和进程控制块的实体</b>
<b>进程与程序的区别</b><br>
<b>进程是程序的一次执行，进程总是对应至少一个特定的程序执行程序的代码。一个程序可以对应多个进程</b>
<b>进程与程序的联系</b>
进程与程序的比较
<b>进程的概念</b><br>
<b>每个进程有唯一的进程控制块，进程控制块是操作系统感知进程存在的唯一标志</b>
什么是进程控制块（PCB）
<b>进程标识符用于唯一标识一个进程</b>
进程标识符信息
<b>处理机是被进程共享的资源</b>
通用寄存器
指令计数器
程序状态字PSW
用户栈指针
包括
处理机状态信息
进程调度信息
进程控制信息
进程控制块中的信息
<b>进程控制块</b>
就绪态是进程一旦获得CPU就可以投入运行的状态。在多任务系统中，可以有多个处于就绪态的进程
（1）就绪态
执行态是进程获得CPU正在运行的状态。系统中执行态进程数量受CPU数量的限制
（2）执行态
阻塞态是进程由于等待资源或某个事件的发生而暂停执行的状态，系统不会为阻塞态的进程分配CPU。阻塞态进程在获得其等待的资源或其等待的事件发生之后，转变为就绪态。处于阻塞态的进程的数量可能很多，系统可以根据不同的阻塞原因进程组织不同的阻塞队列。
（3）阻塞态
进程的三种状态
<b>进程开始在CPU上运行，进程的状态就由就绪态变为执行态。执行态进程可能变为就绪态，也可能变为阻塞态</b>
<b>进程状态不能由阻塞态直接变为执行态</b>，进程状态转换阻塞态变为就绪态的过程称为<b>唤醒过程</b>，由执行态变为阻塞态的过程称为<b>阻塞过程</b>
<br>
进程状态的转换
<b>进程的状态</b>
对进程的组织是靠数据结构来实现的
把系统中具有相同状态的进程控制块（PCB）用其中的链接字链接成一个队列
链接方式
系统根据所有进程的状态，建立几张索引表，索引表的每一个表项指向一个PCB的物理块
索引方式
当系统中有很多进程时，可以把进程控制块用队列组织起来，形成<b>进程队列</b>。<br>处于就绪态的进程构成的进程队列被称为<b>就绪队列</b> <br>处于阻塞态的进程构成的进程队列被称为<b>阻塞队列</b> <br>
进程队列
<b>进程的组织</b>
进程的描述
简介
用户登录
作业调度
提供服务
应用请求
通常下列情况需要创建新进程
父进程与子进程并发执行
父进程等待，直到某个或全部子进程执行完毕
当新进程被创建时，有两种可能
子进程共享父进程的地址空间
子进程拥有独立地址空间
新进程的地址空间也有两种可能
申请空白PCB<br>
为新进程分配资源
初始化进程控制块
将新进程插入就绪队列<br>
创建进程的一般步骤
进程的创建
请求系统服务
启动某种操作
新数据尚未到达
无新工作可做
操作系统在下列情况下可可能进行进程的阻塞和唤醒操作
将进程状态改为阻塞态
将进程插入相应的阻塞队列<br>
转换进程调度程序，从就绪进程中选择进程为其分配CPU<br>
完成进程阻塞的过程如下
进程的阻塞
将进程从阻塞队列中移出<br>
将进程由阻塞态改为就绪态
将进程插入就绪队列
将阻塞态进程变为就绪态进程的过程如下
进程的唤醒
当进程正常执行完毕，调用终止进程的系统调用，请求操作系统删除该进程<br>
一个进程调用适当的系统调用，终止另外一个进程。<br>
会被进程终止情况
子进程使用了超过他所分配到的一些资源
分配给子进程的任务已不再需要
父进程退出
父进程终止子进程的原因
从进程PCB中读取进程状态<br>
若进程正在执行，则终止进程的执行
若进程有子孙进程，在大多数情况下需要终止子孙进程
释放资源
将终止进程的PCB移出
操作系统通过系统调用完成进程终止的过程如下
进程的终止
进程的控制
<b>操作系统内核是计算机硬件的第一次扩充</b>
<b>支撑功能包括中断处理、时钟管理和原语操作。<br>原语操作也称原子操作，是一组在执行过程中不能被中断的操作</b><br>
支撑功能
<b>资源管理包括进程管理、存储器管理和设备管理</b>
资源管理功能
操作系统内核功能
中断是改变处理器执行指令顺序的一种事件
中断分为<b>同步中断（也称内部中断或异常）和异步中断（也称外部中断）</b>两种
同步中断是当指令执行时由CPU单元控制产生的<br>之所以称为同步，是因为只有在一条指令终止执行后才会发出中断，如<b>除法出错、调试、溢出和浮点出错</b>
同步中断
异步中断是由其他硬件设备随机产生的
<b>外部可屏蔽中断。外不可屏蔽中断是由I/O设备产生的中断</b>
<b>外部不可屏蔽中断。外部不可屏蔽中断是由紧急事件引起的中断，如硬件故障</b>
<b>外部中断又可以分为外部可屏蔽中断和外部不可屏蔽中断</b>
异步中断（外部中断）
中断类型
人为设置中断
程序性事故。如计算中出现除数为0
硬件故障
IO设备
外部事件
引起中断的原因
系统关闭中断，保护断点，把当前要执行的下一条指令保存到内存中
转中断处理程序
保护完现场后，根据中断向量到中断向量表中找到与中断处理子例程入口地址相关的信息
最后，恢复现场，开中断
单重中断的处理过程
中断向量是对于不同中断源到来的信号编号，该编号是一个无符号整数（0-255），成为中端向量
不可屏蔽中断的向量和异常的向量是固定的，而可屏蔽中断的向量可以通过对中断控制器的编程来改变
可编程中断控制器的IRQ线是从0开始顺序编号的
中断向量
中断描述符表
如何找到中断服务子程序
<b>中断</b>
<b>时钟管理</b>
系统调用是系统程序与用户应用程序之间的接口
用户空间是指用户进程所处的地址空间，一个用户进程不能访问其他进程的用户空间，只有系统
用户态执行
系统态执行
系统调用运行在核心态，而一般函数运行在用户态
系统调用与一般函数调用的执行过程不同
系统调用一般要经过中断处理，比一般函数调用多了一些系统开销
区别如下
系统调用与一般函数的区别
<b>系统调用</b>
<b>操作系统内核</b>
多任务操作系统支持多个进程并发执行，并发执行的进程共享系统的软件和硬件资源<br>
1）对具有共享资源关系的进程，保证以互斥的方式访问临界资源。临界资源是必须以互斥方式访问的共享资源。<br>
2）对具有相互合作关系的进程，要保证相互合作的诸进程协调执行。<br>
进程同步有两个任务<br>
1）空闲让进<br>
2）忙则等待<br>
3）有限等待<br>
4）让权等待<br>
同步机制应遵循的准则<br>
信号量机制（wait signal）对不同的共享资源设置称为信号量的变量，用信号量的取值标识资源的使用状况，或某种事件的发生 <br>
用整型变量值来标记资源的使用情况。<br><b>若整型量>0，说明有可用资源；若整型量<=0，说明资源忙，进程必须等待。</b><br>对于一次只允许一个进程访问的临界资源，可定义一个用户互斥的整型信号量，并将其初始化为1，<br><b>整型信号量的值只能通过两个特定的原子操作wait和signal来改变。 </b><br>
整型信号量的互斥：初始变量为1 整型信号量的协调：初始变量为0
1）整型信号量的值只能由wait和signal操作改变 <br>
wait和signal的操作都是原子操作，即在这两个操作中对信号量的访问是不能被中断的
原子操作可以通过关中断来实现 <br>
整型信号量机制的实例：linux中的自旋锁SpinLock <br>
不同的资源对应不同的信号量，并不是系统中所有资源都用同一个信号量标识
总结
一、 整型信号量机制：<br>
记录型信号量的优点是不存在「忙等」，采取了「让权等待」的策略
二、 记录型信号量机制：
基本思想是将进程在整个运行过程中所需要的所有资源一次性的全部分配给进程，待进程使用完之后再一起释放。只要还有一个资源不能分配给该进程，其他所有可能为之分配的资源也不分配给它。
三、 AND型信号量的机制<br>
信号量机制
是描述共享资源的数据结构和在数据结构上的共享资源的管理程序的集合
管程<br>
进程同步的概念
进程同步
进程之间的高级通信机制分为：共享存储器系统、消息传递系统、管道通信系统。<br>
进程通信
在操作系统中，进程是进行资源分配和独立执行的基本单位，为了进一步提高程序的并发性，减少系统开销，在操作系统中引入了线程的概念。
线程是进程中的一个实体，是被系统独立调度和分派的基本单位。
线程在运行中存在间断性，也有就绪、执行、阻塞三种形态。
用户级线程不依赖于内核，用户级线程的创建、撤销和切换都与内核无关
用户级线程的调度程序运行在用户态
切换慢
用户级线程
内核级线程的调度程序运行在系统态
切换块
内核级线程
线程的分类
正常结束
异常结束
外界干预
线程的终止
线程
进程调度算法（选择、填空、简答、综合）
实时系统中的调度概念及算法（选择、填空、简答、综合）
进程切换（选择、填空、简答）
多处理器调度（选择、填空、简答）
死锁产生的原因、必要条件（选择、填空、简答）
死锁的预防和避免（选择、填空、简答）
银行家算法（选择、填空、简答、综合）
死锁的检测和解除（选择、填空、简答）
近三年分值分步：21-26分
本章考试重点：
<b>进程调度功能由操作系统内核的进程调度程序完成</b>
进程调度的功能是<b>按照某种策略或算法从就绪态</b>进程中为<b>当前空闲的cpu</b>选择在其上运行的新进程。 <br>
进程调度的功能
当一个进程运行结束、进程阻塞、中断返回、在支持抢占式调度的系统中有比当前运行进程优先级更高的进程到来、当前运行进程的时间片用完。<br>系统都会通过<b>执行进程调度程序</b>重新进行进程调度<br>
进程调度的时机
进程调度的功能与时机
进程调度算法是指从就绪态进程中选择一个进程为其分配CPU，使其进入执行态的算法
周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔
<b>1、作业在外存后备队列上等待调度的时间</b>
<b>2.进程在就绪队列上等待的时间</b>
<b>3.进程在CPU上执行的时间</b>
<b>4、进程等待I/O操作完成的时间</b>
包括四部分时间：
如果系统中有n个作业，<b>系统的平均周转时间</b>等于n个作业的周转时间之和除以n
作业的周转时间T与系统为它提供的服务时间Ts之比为W，W称为<b>带权周转时间</b>
<b>服务时间</b>Ts是一个作业在CPU上执行的的总时间
1.周转时间短
响应时间是指从用户提交一个请求开始直至系统首次产生相应的时间为止的一段时间
响应时间快
截止时间是指某个任务必须开始的最迟时间，或必须完成的最迟时间
截止时间的保证
系统吞吐量
在选择和设计进程调度算法应考虑使得CPU的利用率尽可能高
处理机的利用率好
选择调度方式和算法的若干准则
在进程调度中，FCFS就是从就绪队列的队首选择最先到达就绪队列的进程，为该进程分配CPU
调度算法
FCFS适合长进程，有利于CPU繁忙的进程
性能分析
先来先服务算法（FCFS）<br>
短进程优先（SPF）的调度算法是从就绪队列中选择估计运行时间最短的进程
短进程优先调度算法能有效降低进程的平均等待时间，提高系统吞吐量
算法优点
对长进程不利，如果系统中不断有短进程到来，长进程可能长时间得不到调度
不能保证紧迫进程的及时处理，因本算法不考虑进程的紧迫程度
进程的长度由用户估计而定，可能有偏差
算法缺陷
短进程优先调度算法（SPF）
在使用优先权调度的系统中，每个进程都有一个与之关联的优先权
CPU会优先分配给优先权最高点进程
非抢占式优先权调度算法
抢占式优先权调度算法
优先权调度算法的类型
静态优先权
动态优先权
优先权的类型
问题：无穷阻塞或称饥饿问题。指就绪态进程因得不到CPU而等待的状态
解决方案：老化（Aging）技术。逐渐增加在系统中等待时间很长的进程的优先权
优先权调度算法存在的问题和解决方案
优先权调度算法
时间片是一个较小的时间单位，通常为10-100ms<br>
时间片轮转调度算法
时间片太长，可使多数进程在一个时间片内处理完，可降低进程的周转时间，但可能造成用户的响应时间过长。
时间片太短，一个进程需经过多次调度才能运行完，会增加进程切换和调度的开销，系统的平均周转时间也较长
系统对相应时间的要求。响应时间越短，时间片取值应越小
就绪队列中进程的数目。进程越多，响应时间越长
系统的处理能力
确定时间片大小时，通常考虑以下因素：
时间片大小的确定
时间片轮转调度算法的性能依赖于时间片的大小。
时间片很大，与先来先服务算法一样
时间片很小，会增加CPU用于进程切换和进程调度的开销
时间片轮转调度算法的性能评价
引入时间片轮转调度算法的目的是：多个终端都能得到系统的及时响应
将每个进程分配到不同的队列，每个队列都有自己的调度算法
多级队列调度
多级反馈队列可以解决多级队列调度中存在的无穷阻塞（饥饿）的问题
多级反馈队列调度
就绪时间
开始截止时间和完成截止时间
处理时间
资源请求
优先级
提供必要的调度信息
系统处理能力强
基于时钟中断的抢占式优先权调度算法
立即抢占的优先权调度算法
采用抢占式调度机制
<b>具有快速切换机制</b>
实现实时调度的基本条件
最早截止时间EDF算法
最低松弛度优先LLF算法
常用的集中实时调度算法
实时系统中的调度
进程调度算法
保存程序计数器和其他寄存器CPU上下文环境
更新被替换进程的进程控制块
修改进程状态，把执行态改为就绪态或阻塞态
将被替换的进程控制块移到就绪队列或阻塞队列
执行通过进程调度程序选择的新进程，并更新该进程的进程控制块
更新内存管理的数据结构
恢复被调度程序选中的进程的硬件上下文
进程切换步骤
进程的切换
根据处理器的耦合程度，分为<b>紧密耦合和松弛耦合</b>
根据处理器的结构，分为<b>对称和非对称</b>
多处理器系统的类型
操作系统为每个处理器建立一个专门的就绪队列
静态分配
每个进程经过多次调度，每次获得的不一定是同一个处理器
动态分配
对称多处理器系统中的进程分配方式
采用主——从式操作系统，操作系统的核心部分驻留在一台主机上，而从机上只运行用户应用程序，只有主机执行调度程序，而所有从机的进程都是由主机分配的
非对称多处理器系统中的进程分配方式
采用自调度的系统中设置有一个公共的就绪队列，任何一个空闲的处理器都可以自行从该就绪队列中选取一个进程或者一个线程运行
易移植
有利于提高CPU的利用率
自调度算法的优点
系统中只有一个必须互斥访问公共就绪队列，在系统有多个处理器的情况下，容易形成瓶颈
瓶颈问题
高速缓冲的命中率较低
低效性
线程切换频繁
自调度算法的缺点
自调度
系统将一组相互合作的进程或线程同时分配到一组处理器上运行，进程或线程与处理器一一对应
减少线程切换
减少调度开销
优点
成组调度
进程（线程）调度方式
多处理器系统中的进程分配方式
多处理器调度
进程调度
在多道系统中，多个进程可能竞争数量有限的资源
若一个进程所申请的资源被其他处于阻塞状态的进程所战友，该进程就不会因为不能获得所申请的资源而被阻塞
这种由于多个进程竞争共享资源而引起的进程不能行前推进的僵持状态称为死锁
<b>竞争共享资源且分配资源的顺序不当</b>
产生死锁的原因
指一个进程在访问资源的过程中，其他进程不能访问该资源<br>
互斥条件
进程已经保持了至少一个资源，又提出了新的资源要求，而新请求的资源已经被其他进程占有，此时进程阻塞，但又对已经获得的资源保持不放<br>
<b>请求和保持条件</b>
进程已经获得的资源不能被剥夺，只能由进程自己释放
<b>不剥夺条件</b>
进程死锁时，必然有个一进程申请资源的环形链
<b>环路等待</b>
注意：只有上述四个条件同时满足时才会发生死锁
产生死锁的必要条件
产生死锁的原因和必要条件
处理死锁的基本方法有<b>预防死锁、避免死锁、检测并解除死锁和忽略死锁问题（即假定死锁不可能在系统内发生而忽略死锁）</b>
通过保证至少有一个条件不成立来达到预防发生死锁的目的
有些资源被定义为临界资源，对于这些资源的访问必须是互斥的。因此互斥条件不能摒弃
系统要求所有进程执行前要一次性的申请在整个运行过程中所需要的全部资源。
<b>摒弃请求和保持条件</b>
一个已经保持了某些资源的进程，当它在提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源
摒弃不剥夺条件
<b>进程必须按规定的顺序申请资源</b>
摒弃环路等待
预防死锁可以摒弃<b>以下三个条件之一</b>
死锁的预防
<b>避免死锁的方法是把系统的资源分配状态分为安全状态和不安全状态</b>
在避免死锁的方法中，<b>允许进程动态的申请资源</b>
系统在分配资源之前，先计算资源分配的安全性，若本次资源分配不会导致系统进入不安全状态，便将资源分配给进程。否则拒绝进程的资源请求。
当系统能找到一个进程执行序列，使系统只要按此序列为每个进程分配资源，就可以保证进程的资源分配和执行顺利完成，不会发生死锁时，称系统处于安全状态。<br>若不存在这样的安全序列，则称系统处于不安全状态。
<b>不安全状态不一定是死锁状态，但当系统处于不安全状态之后，便可能进入死锁状态，反之，只要系统处于安全状态，系统可避免进入死锁状态</b>
因此，避免进程思索的实质在于<b>使系统处于安全状态</b>
<b>系统的安全状态</b>
<b>死锁的避免</b>
处理死锁的基本方法
其基本思想是一个进程提出资源请求后，系统先进行资源的试分配。<br>然后检测本次的试分配是否使系统处于安全状态，若安全状态则按分配方案分配资源，否则不分配资源
用m表示系统中的资源的种类数，n表示系统中的进程数。
available[ ]是一个一维数组。标识系统中某种资源的可用数量，也就是这种资源可分配的数量，available[j]=k表示j类资源的可用数量为k，系统可以为进程分配的j类资源为k个
需要的数据结构如下
数据结构
银行家算法
操作系统可以不采取事先预防和避免的方法来解决死锁问题，二是检测是否有死锁发生。如果检测到系统中有死锁进程，则解除死锁
取决于两个因素：<br>死锁可能发生的频率；<br>当死锁的发生时受影响的进程数量<br>
何时调用检测算法
死锁状态的充分条件是当且仅当资源分配状态是不可完全简化的
死锁定理
一是终止处于死锁状态的进程
<b>二是抢占死锁进程占有的资源</b>
<b>死锁的解除</b>
死锁的检测和解除
死锁
进程调度与死锁
存储器的层次结构（选择、填空、简答）
程序的链接和装入（选择、填空、简答）
连续分配存储管理、动态分区分配算法（选择、填空、简答、综合）
分页、快表、两级页表（选择、填空、简答、综合）
虚拟存储、缺页、页分配策略（选择、填空、简答）
页置换算法（选择、填空、简答、综合）
分段系统、段表、段页式存储管理（选择、填空、简答）
本章近三年分值：19-22分
本章考试重点
<b>当操作系统接收到运行某程序的命令后，要为该进程的运行分配内存资源，创建进程，并把进程的全部或部分调入内存</b>
实现内存分配、内存回收等基本内存管理功能
<b>提高内存空间的利用率和内存的访问速度</b>
内存管理的目标
存储器是一个不同容量、成本和访问时间的存储设备的层次结构
在这个层次系统中，从高层到底层（L0-L5），较低层的存储设备访问慢，容量更大、价格更便宜
在最高层（L0层），是少量的快速CPU寄存器，CPU可以在一个时钟周期内访问他们
L1、L2层是一个或多个小型或中型的基于SRAM的<b>高速缓存存储器</b>，可以再几个CPU时钟周期内访问他们
L3层是一个大的基于<b>DRAM的主存</b>，可以再几十或几百个时钟周期内访问他们
L4层是慢速但容量很大的<b>本地磁盘</b>
L5层表示有些系统可能还包括一层<b>附加的远程服务器上的磁盘</b>，需要通过网络来访问
CPU中<b>寄存器</b>保存最常用的少量数据
主存·暂时存放存储容量更大、速度更慢的磁盘上的数据。
而这些磁盘常常又作为存储在通过网络连接的其他机器或磁盘或磁带上的数据的缓冲区
如果程序需要的数据存放在CPU寄存器中，程序执行期间在零个周期内就可以访问到
如果在高速缓存中，需要1-10个周期
如果存放在主存中，访问他们需要50-100个周期。
如果存放在磁盘中，访问他们需要大约2000万个周期
程序的执行遵循局部性原理
程序在执行时呈现出局部性规律，即在一段较短的时间内，程序的执行仅限于某个部分，相应的，他所访问的存储空间也局限于某个区域
1.程序在执行时，除了少数部分转义和过程调用指令，<b>大多数情况下是顺序执行</b>
2.过程调用将会使程序的执行轨迹由一部分内存区域转移到另一部分内存区域
3.程序中存在很多循环结构，他们虽然由少数指令构成，但多次执行
4.程序中往往包括许多对数据结构的处理，如对数组的操作，他们往往都局限在很小的范围内。<br>总的来说，局部性原理表现为时间和空间的局部性
程序的执行
如果程序中的某条指令一旦执行，则不久后该指令可能再次执行
时间局部性
<b>一旦程序访问了某个单元，不久后，其附近的存储单元也将被访问</b>
空间局部性
局部性
存储器的层次结构
高级语言程序必须经过<b>编译、链接</b>才能成为可执行程序
链接程序要解决的问题是将编译后的目标模块装配成一个可执行的程序。<br>
<b>在程序运行前，用链接程序将目标程序链接成一个完整的装入模块</b>
静态链接
<b>将某些目标模块的链接推迟到这些模块中的函数被调用执行时才进行</b>
采用动态链接节省内、外存空间，方便了程序开发。
速度慢
<b>动态链接</b>
程序的链接
将一个用户源程序变为一个可在内存中执行的程序，必须经过编译、链接和装入3个阶段
可执行程序以二进制可执行文件的形式存在磁盘上，为执行程序，操作系统需要吧程序调入内存
程序装入内存的方式称为<b>绝对装入方式、可重定位装入方式（静态重定位）、和动态运行时装入方式</b>
编译程序事先已知程序在内存中的驻留位置，编译时产生的物理地址的目标代码
绝对装入方式
如果<b>编译时不知道</b>目标程序将驻留在内存的什么位置，则<b>编译时就必须生成可重定位的代码</b>，其中的地址都是<b>逻辑地址</b>，在程序被装入内存时，再把这些<b>逻辑地址映射为物理地址</b>
在程序装入时对目标程序中的指令和数据地址的修改过程称为<b>重定位</b>
可重定位装入方式（静态重定位）
进程再装入内存后，还可能从内存的一个区域移动到另一个区域，这种情况可能发生在支持虚拟存储系统中。
一个进程在被<b>换出之前所在的内存位置与后来被从外存重新调入时</b>的内存位置不同，这种装入方式称为<b>运行时装入</b>
在晋城运行访存的过程中才进行地址转换，需要<b>重定位寄存器</b>支持
动态运行时装入（静态重定位）
程序的装入
程序的链接和装入
连续分配是指操作系统分配内存是，为每个进程分配一块物理地址连续的内存空间，连续分配有3中类型
内存中只有一个用户区，任意时刻内存中智能装入一道程序，这种分配方式适用于单用户、单任务系统
在单用户、单任务操作系统中较常用的方法是设置<b>一个基址寄存器和一个界限寄存器</b>
基址寄存器中存放程序在物理内存中的最小地址，界限寄存器中存放装入用户区程序的地址范围
单一连续分配
将内存用户划分成若干个固定大小的区域，每个区域中驻留一道程序
把用户区划分成大小相等的若干个分区
缺点是内存利用率比较低
当程序太小时，改程序所占用的分区有很大一部分是空闲的<br>当程序太大时，可能找不到一个分区足以装下改程序
分区大小相等
为用户进程分配空间时，把大小最接近进程大小的空闲分区分配给申请内存空间的进程。<br>使小进程占小分区，大进程占大分区，减少内存浪费
分区大小不相等
划分分区的方法
记录用户分区大小和使用情况的数据结构
支持固定分区分配的数据结构
需要为进程分配内存时，操作系统执行内存分配程序，搜索内存分区使用表。当找到一个大小大于或等于进程需要的内存空间而且处于空闲状态的用户分区是，将该分区分配给进程，并且将该分区状态改为已占用
固定分区分配的过程
<b>当进程运行结束后，系统要回收进程占用的分区</b>
固定分区分配实现简单，但是由于每个分区的大小固定，必定<b>造成存储空间的浪费，是内存利用率低下</b>
<b>固定分区的回收</b>
固定分区分配
系统动态的对内存进行划分，根据进程需要的空间大小分配内存。内存中分区的大小和数量是变化的
动态分区固定分区方式显著的提高了<b>内存利用率</b>
<b>系统初始只有一个大空闲区</b>
系统维护一个记录当前空闲分区情况的数据结构，<b>当进程请求内存时，系统从所有空闲区中找到大小合适的空闲分区进行分配</b>
动态分区分配原理
系统在空闲分区表中<b>为每一个空闲分区建立一个表项</b>，每个表项中包含分区编号、大小和起始地址
使用空闲分区表的缺点是，若设置太多表项，会浪费内存空间；设置太少的表项，当空闲分区较多时，无法记录所有空闲分区的情况。在实现时，结构体的大小不容易确定
空闲分区表
可以动态的为每一个空闲分区建立一个结点。每一个结点包过分区大小、分区起始地址、指向前一个分区结点的指针，以及指向后一个结点的指针
空闲分区链中的每个节点占用的内存可以动态分配，动态回收。
空闲分区链
动态分区分配的数据结构
要求空闲分区链以地址递增的顺序连接<br>
在进行内存分配时，从链首开始顺序查找，直到找到一个能满足进程大小要求的空闲分区为止。然后在按照进程请求内存的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。
该算法先分配低地址部分的内存空间，容易使低地址部分留下小分区，而高地址部分大空闲分区较多。当进程请求大空间时，要找到合适的空闲分区时，时间开销大<br>
<b>而低地址部分的空闲分区反复被划分</b>，可能留下许多难以利用的很小的空闲分区，这种小空闲区被称为<b>外部碎片或外碎片</b><br>
分配给进程的的分区若大于进程请求的分区，分区内存在一部分人不被利用的空间，这部分被浪费的空间称为<b>内部碎片或内碎片</b>
首次适应算法FF（First Fit）
为进程分配内存空间时，不再每次从链首开始查找，而是<b>从上次找到的空闲分区的下一个空闲分区开始查找</b>，知道找到第一个能满足要求的空闲分区，并从中划出一块玉请求的大小相等的内存空间分配给进程。
为实现该算法，应该设置一个<b>起始查找指针</b>，以指示下一次起始查找的空闲分区，并采用<b>循环查找方式</b><br>
循环首次适应算法的优点是：空间分布均匀，查找开销较小。缺点是容易使系统缺乏大空闲区
循环首次适应算法NF（Next Fit）<br>
该算法每次作业分配内存，总是把<b>大小与进程所请求的内存空间大小最接近的空闲分区分配给进程</b>，避免了“大材小用”。为了加速寻找，该算法要求将所有的空闲<b>按分区大小递增顺序</b>形成一个空闲区链<br>
最佳适应算法BF（Best Fit）<br>
动态分区分配算法
<b>内存分配有内存分配程序完成。</b><br>内存不再被应用程序需要时<b>，由系统调用内存回收程序回收原来被占用的内存分区</b>
内存分配流程
动态分区分配的流程
动态分区分配
连续分配存储管理方式
把进程<b>离散的</b>存储在内存中<b>物理地址不连续的区域中</b>，这种内存管理方式称为<b>离散内存管理方式</b>
将一个进程的<b>逻辑地址空间</b>分成若干个大小相等的<b>片</b>，称为<b>页</b>
页（Page）
将<b>物理内存空间</b>分成与页大小相同的若干个存储块，称为<b>页框</b>或页帧
页框
在为进程分配内存时，以<b>页框为单位</b>将进程中的若干页分别<b>装入可以不相邻的页框中</b>
<b>分页存储</b>
<b>进程的最后一页一般装不满一个页框，是一种内部碎片</b>
<b>页内碎片</b>
<b>页表是系统为进程建立的数据结构，页表的作用是实现从页号到页框号的映射</b>
<b>页表</b>
基本概念
基本分页的逻辑地址结构包含两部分：页号P和页内偏移量W。
页号为（逻辑地址/页）<b>取整，</b>页内偏移量（逻辑地址%页）<b>取余</b>
地址结构
物理地址=页框大小*页框号+页内偏移量
分页地址转换
若页较小，页表较长，页表需要占的内存空间较大，而且换入、换出频繁；<br>若页较小，页内碎片会增大
页大小的选择
分页存储管理的基本原理
因为页表存放在内存里，CPU要访问内存读写数据或读取指令，必须访问两次内存。<br>
第一次访问内存，第二次访存是根据计算出的物理地址实现对内存单元的访问，读写数据或读取指令。
<b>为了减少CPU在有效访存上的时间开销，提高访存速度，在硬件上引入了快表机制</b>
快表也称转换后援缓冲（TLB），是为了<b>提高CPU访存速度</b>而采用的专用缓存，用来存放最近被访问过的页表项
什么是快表
懒得写
引入快表之后的地址变换过程
再快表中找到某一个页号对应的页表项的百分比称为快表命中率。
当能再快表中找到所需要的页表项时，有效访存时间等于一次访问快表的时间加上一次访问内存的时间
当没有再快表中找到所需要的页表项时，访存时间等于一次访问块表的时间加上两次访问内存（一次访问内存页表，依次访问内存读写数据或指令）的时间
引入快表的性能分析
快表
将页表再进行分页
两级和多级页表
为每个页框设一个表项，表项中存放进程号和页号
反置页表
使用位图管理空闲页框
使用空闲页框的链表
空闲页框的管理
基本分页存储管理方式
虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统
在虚拟存储器系统中，进程无需全部装入，只需要装入一部分即可运行
虚拟存储技术实现的思想是，只把进程的一部分装入内存。进程执行过程中，CPU访问内存时如果发现所访问的内容不再内存中，则通过异常处理将所需要的内容从外存调入内存。即先将进程的一部分装入内存，其余的部分需要的时候在请求系统装入，这就是请求调入。<br>
如果请求调入时，没有足够的内存，系统选择一部分内存中的内容换到外存，这就是置换
提高内存利用率
提高多道程序度
把逻辑地址空间和物理地址空间分开，是程序员不再关心物理内存的容量对编程的限制
虚拟存储技术的优点
离散性
多次性
对换性
虚拟存储系统的特征
<b>请求分页系统</b>是最基本、最常用的<b>虚拟存储系统</b>的实现方式
其基本原理是，把进程的逻辑地址空间分成大小相同的页，操作系统创建进程时只把进程的一部分页调入内存。<br>进程运行过程中访问内存，若发现所访问的页不在内存中，则产生一个<b>缺页异常信号</b>，系统响应缺页异常，<b>请求调入缺页</b>
需要特殊的页表、缺页异常机构和支持请求分页的地址变换结构
是支持请求分页系统中最重要的数据结构，其作用是记录描述页的各种数据，<br>包括在实现逻辑地址到物理地址映射时需要的页号与页框号的对应关系<br>
除了页号和页框号之外，页表中增加了请求换入和页置换时需要的数据
存放页所在的页框号
页框号
标识页是否在内存中
状态位
用于<b>记录页最近被访问的情况</b>。
访问字段A
标识页最近是否被修改过
修改位M
标识页的访问权限
保护位
页表
主要作用是在访问内存过程中发现缺页时产生缺页异常信息，使CPU中断当前控制流的执行，转去执行操作系统的缺页异常处理程序，完成请求调页
缺页异常机构
请求分页系统中的地址变换过程如下
由分页地址变换机构从逻辑地址中分离出页号和页内偏移地址。
以页号为索引查找快表，若块表中有该页的页表项，则读出页框号，计算物理地址
若快表中无该页信息，转到内存页表中查找
若该页尚未调入内存，则产生缺页异常
地址变换
请求分页中的硬件支持
指能保证进程正常运行所需要的最少页框数
最少页框数<br>
页分配策略
大多数系统都采用预先调入页的策略，将预计不久之后就会被访问的页预先调入内存
在实际系统中，通常是在调入缺页时，把与所缺页相邻的若干页也调入内存
何时调入页
当系统拥有足够的对换空间时，若发生缺页请求，则从兑换区调入页
对换区中的页是进程运行前从文件区复制到对换区的
从何处调入页
页调入策略
选择以后永远不会被访问的页或者在未来最长时间内不再被访问的页作为换出页。该算法主要用于理论研究
最佳置换算法
为每个页记录该页调入内存时间，当选择换出页时，选择进入内存时间最早的页
实现简单，但效率低，会导致较高的缺页率。页刚被换出可能又要立即访问
先进先出置换算法
选择最近最久未使用的页换出。
最近最久未使用算法LRU
附加引用位算法、简单Clock置换算法、改进型Clock算法、最少使用算法
其他置换算法
页置换算法
请求调入和置换技术都是以时间换空间的技术
缺页率对有效访问时间的影响
引入工作集机制是为了有效降低缺页率
工作集<br>
多道程序度太高，使运行进程的大部分时间都用于进行页的换入换出，而几乎不能完成任何有效工作的状态称为抖动
引起抖动的原因是系统中的进程数量太多，每个进程能分配到的页框太少，以至于进程运行过程中频繁请求调页
原因
采取局部置换侧率。仅在进程自己的内存空间范围内换页
在CPU调度程序中引入工作集算法
挂起若干进程，腾出进程占用的空间
抖动的预防
抖动产生的原因和预防方法
请求分页系统的性能分析
基于分页的虚拟存储系统
分段能为进程提供多个地址空间，把逻辑上关联的部分放在一个地址空间中，逻辑上没有关联也没有共同特征的部分放在不同地址空间中。
把分别存放逻辑上相关的信息、相互独立的逻辑地址空间称为一个段，每个段由一个从0到最大线性地址的逻辑地址空间构成
分段系统中，程序员使用二维的逻辑地址，一个数表示段，另一个数表示段内偏移，段是一个逻辑实体，程序员可以通过使用逻辑地址来访问不同的逻辑段。
一个段可能包括一个过程，或者一个数组，一个堆栈，一些数值变量，但是一般不会同时包含多种不同的内容
分段机制的引入
段的大小不一样，每个段的逻辑地址从0开始，采用一段连续的地址空间。系统为每个段分配一个连续的物理内存区域，各个不同的段可以离散的放入物理内存不同的区域
<b>系统为每个进程建立一张段表</b>，段表的每个表项记录的信息包括<b>段号、段长和该段的基址</b>，段表存放在内存中<br>
分段
分段机制的逻辑地址是二维的，由段号和段内偏移组成
分段的逻辑地址结构
段表是<b>由操作系统维护</b>的用于支持分段存储管理地址映射的数据结构。<br>
<b>通常每个进程有一个段表，段表由段表项构成。每个段表项包含段号、段基址（段的起始地址）和段长（段大小）三个部分</b>
段表
逻辑地址由段号s和段内偏移d构成
已知逻辑单元地址为s:d，求物理地址的步骤
（1）以s为索引，从段表中找到段号为s的段表项，
（2）从找到的段表项中读出s段的基地址和段大小
（3）如果d<=段大小（否则越界），则将段地址与段内偏移d相加，得到与逻辑地址单元s:d对应的物理单元地址。
分段系统的地址变换
<b>页是按物理单位划分的，分页的引入是为了提高内存的利用率和支持虚拟存储。<br>而段是按逻辑单位划分的，</b>一个段含有一组意义相对完整的信息<b>，引入分段的目的是为了方便程序员编程。</b><br>
页的大小时固定的，而段的大小不固定，取决于用户编写的程序和编译器
分页的地址空间是一维的 <br>分段的地址空间是二维的 <br>
分页和分段的主要区别
分段系统的基本原理
既有分段系统的优点，又有分页系统的优点
将用户进程的逻辑空间先划分成若干个段，每个段再划分成若干个页。
进程以页为单位在物理内存中离散存放，每个段中被离散存放的页具有<b>逻辑相关性</b>
<b>操作系统为每个进程建立一个段表，为进程的每个段建立一个页表</b>，进程段表的每一个段表项存放某个段的起始地址和页表长度
段页式存储管理的基本原理
物理地址=页框号*页框大小+页内偏移
地址变换过程
段页式存储管理
分段存储管理
文件结构、类型、存取、属性（选择、填空、简答）
目录结构、路径名（选择、填空、简答）
实现文件、实现目录（选择、填空、简答、综合）
本章近三年分值：14-19分
操作系统中处理文件的部分称为文件系统
<b>文件名</b>向用户提供了简单、直观的文件<b>访问方式</b>
<b>按名存取</b>。用户访问文件时，只需要给出访问的文件名
所有操作系统都支持1-8个字符组成的字符串作为文件名
许多系统支持长达255个字符的文件名
如hello.c，原点后面为<b>扩展名，用于表示文件的类型</b>
文件命名
也称流式文件，如程序
<b>无结构字节序列</b>
记录长度固定
<b>固定长度记录序列</b>
记录长度不固定
<b>树形结构</b>
文件结构
顺序存取
<b>随机存取</b>
文件存取
文件的创建日期、文件大小和修改时间等，这些附件信息称为<b>文件属性</b>
文件属性
CREATE：创建文件，并设置一些属性
DELETE：删除文件并释放磁盘空间
OPEN，使用文件之前必须打开文件
CLOSE，存取结束后，关闭文件以释放内存空间
READ。从文件中读取数据
WRITE，往文件中写数据
APPEND，在文件末尾添加数据
SEEK，对于随机存储文件，要指定从何处开始取数据
GETATTRIBUTES。用于获取文件的属性
SETATTRIBUTES。用于修改文件属性
RENAME。修改已有文件的文件名
文件操作
文件
目录是文件系统中实现按名访问文件的重要的数据结构<br>
也被称为根目录
单层目录
第一级称为主目录，第二级称为用户目录
两级目录解决了<b>文件重名</b>和<b>共享问题</b>
两级目录
也称多级目录，最高层为<b>根目录</b>，最底层为文件，用户可以创建任意数量的子目录
优点：便于文件的分类，层次结构清晰，便于管理和保护，<b>解决了重名问题</b>，查找速度快
树形结构
目录结构
用目录树组织文件系统是，需要两种方法指明文件名：绝对路径名和相对路径名
由从根目录到文件的路径组成。
绝对路径名总是从根目录开始，并且是唯一的
如C:\\program\\practice\\test
绝对路径名
<b>所有的不从根目录开始的路径名都是相对于工作目录的</b>
如practice\\test
“.”指当前目录，“..”指当前目录的父目录
相对路径名
路径名
目录
将分配给文件的<b>连续扇区构成的磁盘块称为簇</b>
把每个文件作为一连串数据块存储在磁盘块上
优点：实现简单，读操作性能好
缺点：随着时间的推移，磁盘会变得零碎。删除文件所释放的簇形成“空洞”，难以利用
连续分配
为每个文件构造簇的链接表，每个簇开始的几个字节用于存放下一个簇的簇号，簇的其他部分存放数据，每个文件可以放在不连续的簇中。
在目录项中只需存放第一块簇的地址
优点：可以充分利用每个簇，管理简单
缺点：随机存取相当缓慢
使用磁盘链接表分配
将文件所在的磁盘的簇号存放在内存的表中
访问文件时只需从内存文件分配表中顺着某种连接关系查找簇的簇号，根据簇号查找文件的所有块。
缺点：必须把整个表都存放在内存中
使用内存的链接表分配
该方法为每个文件赋予一个被称为i结点的数据结构，其中列出了文件属性和文件块的磁盘地址
给定一个文件的i结点，就有可能找到文件的所有块
系统打开文件时，将文件的i结点从磁盘读入内存
当访问文件时，系统先根据文件名搜索文件所在的目录文件，从该文件对应的目录项中找到文件的i结点号，根据i结点号从磁盘中将i结点信息读入内存，文件在磁盘中的地址信息都存放在i结点中。
<b>i-结点</b>
实现文件
系统在读文件之前，必须先打开文件
实现目录
文件系统为文件分配磁盘空间是以簇为单位的。
一般簇的大小时2的整数次幂个连续的扇区
簇大小
空闲簇链接表
位图
记录空闲块
磁盘空间的管理
文件系统的实现
文件系统
IO系统的结构、IO设备分类、设备控制器（选择、填空、简答）
轮询、中断、DMA控制方式（选择、填空、简答）
缓冲管理（选择、填空、简答）
设备分配、独立性、SPOOLing技术（选择、填空、简答）
IO软件管理（选择、填空、简答）
磁盘结构（选择、填空、简答）
磁盘调度（选择、填空、简答、综合）
本章近三年分值：12-20分
IO系统不仅包括IO设备，还包括与设备相连的设备控制器，有些系统还配备了专门用于输入输出控制的专用计算机，即<b>通道。</b>此外，IO系统要通过<b>总线</b>与CPU、内存相连
概述
CPU与内存之间可以直接进行信息交换，但不能与设备直接进行交换，必须经过设备控制器
微机IO系统
IO系统可能采用四级结构：主机、通道、控制器和设备
一个通道可以连接多个控制器，一个控制器也可以连接多个设备
主机IO系统
键盘鼠标
低速设备
打印机
中速设备
磁带机、磁盘机、光盘机
高速设备
按传输速率分类
数据的存取以数据块为单位
如磁盘
块设备
传送字节流
如打印机、鼠标
字符设备
按照信息交换单位分类
必须作为临界资源互斥访问的设备
如打印机
独占设备
允许多个进程共同访问的设备，如磁盘
但同一时刻，只能有一个进程对磁盘进行读写
共享设备
通过某种技术将一台物理设备虚拟成若干台逻辑设备
虚拟设备
按设备共享属性分类
IO设备的分类
设备控制器是CPU与IO设备之间的接口，接收IO的命令并控制设备完成IO工作
接收和识别命令
数据交换
设备状态的了解和报告
地址识别
数据缓冲
差错控制
设备控制器的功能
数据线、控制线和地址线
设备控制器与处理机的接口
设备与设备控制器的接口中的3类信号为数据、状态和控制信号
设备控制器与设备的接口
包括指令译码器和地址译码器，将CPU的命令和地址分别译码，控制指定设备进行IO操作
IO逻辑
设备控制器的组成
设备控制器
通道用于大型主机系统控制IO设备，与控制设备结合，用来代替微机、小型机中的设备控制器，实现大型主机系统的IO设备控制器功能，提供操作系统与IO设备之间的接口
IO通道是一种特殊的处理机
通道是大型主机中专门用于IO的专用计算机
引入通道能使CPU从控制IO的任务中解脱，使CPU与IO并行工作，提高了CPU的利用率
IO通道
IO系统的组成
在IO控制方式的发展中始终追求的目标是尽量减少主机对IO控制的干预，提高主机与IO的并行程度，以提高整个系统的性能
主机发出IO控制命令之前，先反复检测设备控制器的状态寄存器的忙/闲标志，若设备“忙”，主机继续检测该标志位，直到该位“空闲”，主机发送IO指令
这种控制方式造成CPU资源极大浪费
轮询
CPU执行过程中，发出IO请求，若此时IO设备忙，则进程阻塞等待。当处于“忙”状态的设备工作完毕，通过中断控制器发出中断请求信号，CPU响应中断，执行对应设备的中断处理程序，然后唤醒因等待该设备而被阻塞的进程
IO与CPU并行工作
中断
为了进一步提高IO速度和CPU与IO的并行程度，采用DMA方式
DMA控制器的逻辑组成包括：主机与DMA的接口、DMA与设备的接口、以及IO控制逻辑
用于接收从CPU发来的IO命令或有关控制信息、设备状态
命令/状态寄存器CR
存放内存地址
内存地址寄存器MAR
指示DMA，本次向CPU发中断信号要读或写数据的次数
数据计数器DC
用于暂存DMA传输中要输入或输出的数据
数据寄存器DR
DMA控制方式<br>
IO的控制方式
缓冲区是用来保存两个设备之间或设备与应用程序之间传输数据的内存区域
处理数据流的生产者与消费者之间的速度差异
降低对CPU中断频率的要求，放宽对响应时间的限制，提高CPU和IO设备之间的并行性
引入缓冲区的原因
当用户进程发出IO请求是，操作系统为该操作分配一个位于主存的缓冲区
输入设备不是把数据直接送给用户进程，而是把数据放入所设置的缓冲区，用户进程总是从缓冲区中取所需要的数据
单缓冲
在数据的输入和输出速度差别很大时，需要增加缓冲区的数量，可引入循环缓冲
生产者进程下一个可用的空缓冲区
空缓冲区区R
用于指示消费者进程下一个可用的装有产品的缓冲区
已装满数据的缓冲区G
消费者进程正在使用的工作缓冲区
现行工作缓冲区C
多个缓冲区
Nextg
Nexti
Current
多个指针
循环缓冲的多个缓冲区构成一个环，指针Nexti和指针Nextg不断地沿顺时针方向移动<br>
当Nexti指针追上Nextg指针，即生产者进程速度大于消费者进程速度，没有空缓冲区区，全部缓冲区已满。<br>此时，需要阻塞生产者进程，等待消费者进程为生产者进程释放空缓冲区R<br>
当Nextg指针追上Nexti指针，消费者进程速度大于生产者进程速度，全部缓冲区已空。<br>此时需要阻塞消费者进程，等待生产者进程释放装有数据的缓冲区G<br>
循环缓冲区的组成
循环缓冲
公共缓冲池既可用于输入，又可用于输出，其中至少包含三种类型的缓冲区、三种缓冲队列和四种工作缓冲区
空缓冲区、装满输入数据的缓冲区和装满输出数据的缓冲区
三种类型的缓冲区
空缓冲区队列、输入队列、输出队列
三种队列
收容输入数据的缓冲区。收容完输入数据后，缓冲区被插入到输入队列中
提取输入数据的缓冲区、存在于输入队列中，进程需要输入数据时，先从输入队列中获取这些缓冲区
收容输出队列的缓冲区。收容完输出数据后，缓冲区被插入到输出队列中
提取输出数据的缓冲区。存在于输出队列中，进程需要输出数据时，先从输出队列中获取这种缓冲区。
四种工作缓冲区
缓冲池的组成
缓冲池
在多道程序环境下，系统中的设备不允许用户自行使用，须有系统分配
支持设备分配的数据结构需要记录设备的状态（忙或空闲）、设备类型等基本信息
系统为每个设备建立一张设备控制表
设备控制表DCT
系统为每个控制器设置一张用于记录该设备控制器信息的控制器控制表
控制器控制表COCT
在一些主机系统中还有通道设备，系统会为每个通道设备设置一张通道控制表
通道控制表CHCT
记录了系统中全部设备的情况。每个设备占一个表目
<b>系统控制表SDT</b>
设备分配方案
设备分配中的数据结构
为使系统有条不紊的工作，系统在分配设备时应考虑以下因素
缺点是得不到充分利用且容易引起死锁
独占性
可同时分配给多个进程使用。
一台设备采用虚拟技术后变为多台逻辑上的设备
可虚拟性
设备的固有属性
设备独立性也成为设备无关性，提高了操作系统的可适应性和可扩展性。其含义是应用程序独立于具体使用的物理设备
应用程序与物理设备无关
易于处理输入\\输出设备的故障
提高了系统的可靠性
好处
执行所有设备的公有操作<br>
向用户层软件提供统一接口
设备独立软件
设备独立性
对于具有IO通道的系统，在进程提出IO请求后，系统的设备分配程序执行下列步骤
分配设备
分配控制器
分配通道
独占设备的分配程序<br>
在多到程序环境下，利用一道程序来模拟脱机输入时的外围控制机的功能，把低速IO设备上的数据传送到高速输出磁盘上，再利用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。这种在联机情况下实现的同时外围操作称为SPOOLing技术
王道《操作系统》
输入井和输出井是位于磁盘上的存储区域
过程：<br>输入时从输入缓冲区读入输入井，输入设备从输入井读<br>输出时从输出井输出到输出缓冲区，输入设备从输出缓冲区读
SOOPLing技术实现共享打印机
提高了IO速度
将独占设备改造为共享设备
实现了虚拟设备功能
特点
SPOOLing技术（假脱机技术）
IO软件的总体目标是将软件组织成一种层次结构，底层软件用来屏蔽硬件的具体细节，高层软件则主要是为用户提供一个简洁规范的界面
分支主题
用户层软件
与设备无关的软件层
设备驱动程序
中断处理程序（底层）
设备管理软件分4个层次
设备管理软件与硬件关系最密切的是设备驱动程序
实现IO设备的独立性
错误处理
异步传输
设备的分配和释放
实现IO控制方式<br>
设备管理软件的功能
IO中断处理程序的作用是将发出IO请求而被阻塞的进程唤醒
中断处理程序
设备驱动程序是IO进程与设备控制器之间的通信程序，其主要任务是接收上层软件发来的抽象IO请求，把他们转换为具体要求后，发送给设备控制器，启动设备去执行
设备驱动程序属于操作系统的内核程序，一般由生产设备厂商开发
IO软件管理
磁盘管理的重要目标是提高磁盘空间利用率和磁盘访问速度
磁盘设备可包括一个或多个物理盘片<br>每个盘片分为一个或两个存储面，<br>每个盘面被组织成若干个同心环，这种环被称为磁道<br>
在每条磁道上存储相同数目的二进制位。<br>磁盘密度是内层磁道的密度高于外层。每条磁道又被划分成若干扇区
数据的组织和格式
固定头磁盘
移动头磁盘
磁盘的类型
把磁臂（磁头）移动到指定磁道上所经历的时间
寻道时间
将指定扇区移动到磁头下面所经历的时间
旋转延迟时间
把数据从磁盘读出或向磁盘写入数据时所经历的时间
传输时间
磁盘的访问时间
磁盘结构
目标是使各个进程对磁盘的平均访问时间最短
最简单的磁盘调度算法。根据进程请求访问磁盘的先后顺序进行调度
先来先服务算法（FCFS）
选择进程时要求访问磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短
最短寻道时间优先（SSTF）
SSTF最短寻道时间优先算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”现象
SCAN算法不仅要考虑访问的磁道与当前磁道的距离，更优先考虑磁头当前的移动方向
扫描算法（SCAN）
SCAN算法存在的问题：当磁头从里向外移动而越过了某一磁道时，恰好又有一进程请求访问磁道。这时该进程需要等待很长时间
CSCAN算法规定磁头单向移动，即只向里或向外移动
循环扫描算法（CSCAN）
在前面几种算法中，可能会出现磁盘臂停留在某处不动的情况。
如果有一个或者多个进程对某一磁道有较高的访问频率，从而垄断了整个磁盘设备。把这一现象称为“磁臂粘着”，在高密度磁盘上容易出现这种情况
将磁盘请求队列分成若干个长度为N的子队列，按FCFS算法依次调度这些子队列，在队列按SCAN算法，对一个队列处理完以后，在处理其他队列
NStepSCAN算法
FSCAN算法是NStepSCAN算法的简化。只将磁盘请求队列分成两个子队列
FSCAN算法
NStepSCAN和FSCAN算法
磁盘调度
<b>提前读</b>
<b>延迟写</b>
适当的集中数据在磁盘上存放的位置，可以减少磁臂移动的距离，有利与提高传输速率
原则就是尽可能把一个文件存放在同一个磁道或者相邻的磁道上
<b>优化物理块的分步</b>
指利用内存空间去仿真磁盘
虚拟盘
<b>磁盘高速缓存</b>
提高磁盘IO速度的方法
磁盘管理
I/O设备管理
操作系统概论
0 条评论
回复 删除
下一页
