怎么建设ftp网站,NET开发网站开发工程师招聘,兰州网站建设推荐q479185700上快,iis添加网站文章目录 [toc] 计算机系统概述操作系统的基本概念操作系统的概念和特征操作系统的目标和功能#xff08;**处理器管理、存储器管理、设备管理、文件管理、向用户提供接口、扩充机器**#xff09; 操作系统的发展与分类操作系统的运行环境操作系统的运行机制 操作系统的体系结… 文章目录 [toc] 计算机系统概述操作系统的基本概念操作系统的概念和特征操作系统的目标和功能**处理器管理、存储器管理、设备管理、文件管理、向用户提供接口、扩充机器** 操作系统的发展与分类操作系统的运行环境操作系统的运行机制 操作系统的体系结构大内核和微内核 总结 进程管理进程与线程进程的概念和特征进程的状态与转换进程控制进程的组织进程的通信**线程概念**和**多线程模型** 处理机调度调度的概念调度的时机、切换、过程进程调度方式调度的基本准则典型的调度算法 进程同步进程同步的基本概念实现**临界区**互斥的基本方法信号量管程经典同步问题 死锁死锁的概念死锁的处理策略死锁预防死锁避免死锁检测和解除 总结 内存管理内存管理概念内存管理的基本原理和要求连续分配管理方式非连续分配管理方式 虚拟内存管理虚拟内存的基本概念请求分页管理方式页面置换算法决定应该换入哪页、换出哪页页面分配策略抖动工作集地址翻译 总结 文件管理文件系统基础文件的逻辑结构目录结构文件共享文件保护 文件系统实现文件系统层次结构目录实现文件实现--文件分配方式文件实现--文件存储空间管理 磁盘组织与管理磁盘的结构磁盘调度算法磁盘的管理 输入/输出管理I/O管理概述I/O设备I/O控制方式I/O子系统的层次结构 I/O核心子系统I/O调度概念高速缓存与缓冲区设备分配与回收SPOOLing技术 (**假脱机技术**)
计算机系统概述 操作系统的基本概念
操作系统的概念和特征
操作系统 是指 控制和管理整个计算机系统的硬件与软件资源合理地组织、调度计算机的工作与资源的分配进而为用户和其他软件提供方便接口与环境的程序集合。操作系统是计算机系统中最基本的系统软件 计算机系统自下而上分为4部分硬件、操作系统、应用程序、用户 划分与计算机组成原理不同 操作系统的特征 并发、共享、虚拟、异步 并发Concurrence 操作系统的并发性是通过 分时 得以实现的 并发同一时间间隔 9:00到9:30 吃饭9:30到10:00 学习则在 9:00到10:00这段间隔里面吃饭与学习并发 并行同一时刻并行性需要有相关硬件的支持如多流水线、或 多处理机硬件环境 共享Sharing互斥共享方式 与 同时访问方式 指系统中的资源可供内存中多个 **并发执行 **的进程共同使用 互斥共享方式 仅当进程访问完并释放该资源后才允许另一个进程对该资源进行访问。 一段时间内只允许一个进程访问的资源称为 临界资源 或 独占资源。计算机系统中的大多数物理设备 及某些软件中所用的 栈、变量和表格都属于 临界资源。 同时访问方式 允许在一段时间内由多个进程**“同时”访问**“同时”是宏观概念微观上这些进程是 交替地对该资源进行访问即“分时共享”。典型资源是 磁盘设备。 互斥共享 要求一种资源在一段时间内哪怕是一段很小的时间只能满足一个请求否则就会出现严重问题。而 同时访问共享 通常要求一个请求分几个时间片段间隔地完成其效果与连续完成的效果相同。 并发 和 共享 是操作系统两个最基本的特征两者之间互为存在的条件 资源共享是以程序的并发为条件的若系统不允许程序并发执行则自然 不存在资源共享问题若系统不能对资源共享实施有效的管理则必将影响到程序的并发执行甚至根本无法并发执行 虚拟Virtual 把一个物理上的实体变为若干逻辑上的对应物。实现虚拟的技术称为 虚拟技术虚拟技术可归纳为 时分复用技术 处理器的分时共享 和 空分复用技术 虚拟存储器 虚拟处理器技术 通过多道程序设计技术让多道程序并发执行来分时使用一个处理器 虚拟存储器技术 将一台机器的物理存储器变为虚拟存储器以便从逻辑上扩充存储器的容量 虚拟设备技术 将一台物理I/O设备虚拟为多台逻辑上的I/O设备 异步Asynchronism 多道程序环境允许多个程序并发执行但由于资源有限进程的执行并不是一贯到底的而是走走停停它以不可预知的速度向前推进
操作系统的目标和功能处理器管理、存储器管理、设备管理、文件管理、向用户提供接口、扩充机器 操作系统作为计算机系统资源的管理者 处理器管理 多道程序环境下处理机的分配和运行都以进程或线程为基本单位因而对处理机的管理可归结为对进程的管理。并发是指在计算机内同时运行多个进程因而进程的创建、撤销、管理、避免冲突、合理共享就是 进程管理 的最主要任务。进程管理的主要功能包括 进程控制、进程同步、进程通信、死锁处理、处理机调度 等 存储器管理 包括 内存分配与回收、地址映射、内存保护与共享、内存扩充 等功能 文件管理 包括 文件存储空间的管理、目录管理、文件读写管理和保护 设备管理 主要任务是 完成用户的I/O请求方便用户使用各种设备提高设备的利用率 包括 缓冲管理、设备分配、设备处理、虚拟设备 等功能 操作系统作为用户与计算机硬件系统之间的接口命令接口、程序接口 命令接口 联机命令接口交互式命令接口 适用于 分时或实时系统 的接口脱机命令接口批处理命令接口 适用于 批处理系统脱机用户不能直接干预作业的运行。 程序接口 由一组**系统调用也称广义指令**组成
操作系统的发展与分类
操作系统的运行环境
操作系统的运行机制 CPU通常执行两种不同性质的程序 操作系统内核程序用户自编程序即系统外层的应用程序或简称应用程序 操作系统内核程序是用户自编程序的管理者因此内核程序要执行一些特权指令而用户自编程序出于安全考虑不能执行这些指令。 特权指令计算机中不允许用户直接使用的指令如I/O指令、置中断指令存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等的指令。具体实现上将CPU的状态划分为用户态目态和核心态管态、内核态。用户自编程序运行在用户态操作系统内核程序运行在核心态。 一些与硬件关联较紧密的模块如时钟管理、中断处理、设备驱动等处于最低层。其次是运行频率较高的程序如进程管理、存储器管理和设备管理等。这两部分内容构成了操作系统的内核。这部分内容的指令操作工作在核心态。 内核是计算机上配置的底层软件是计算机功能的延伸内核包含以下4方面内容 时钟管理 在计算机的各种部件中时钟是最关键的设备。时钟的第一功能是计时操作系统需要通过时钟管理向用户提供标准的系统时间。通过时钟中断的管理可以实现进程的切换。 在分时操作系统中采用时间片轮转调度在实时系统中按截止时间控制运行在批处理系统中通过时钟管理来衡量一个作业的运行程度 中断机制 引入中断技术的初衷是提高多道程序运行环境中CPU的利用率而且主要是针对外部设备。例如键盘或鼠标信息的输入、进程的管理和调度、系统功能的调用、设备驱动、文件访问等。现在操作系统是靠中断驱动的软件。中断机制中只有一小部分功能属于内核它们负责保护和恢复中断现场的信息转移控制权到相关的处理程序。这样可以减少中断的处理时间提高系统的并行处理能力。 原语 把具有以下特点的程序称为原语 处于操作系统的最低层是最接近硬件的部分这些程序的运行具有原子性其操作只能一气呵成主要从系统安全性和便于管理考虑这些程序的运行时间都较短而且调用频繁 定义原语的直接方法是关闭中断让其所有动作不可分割地完成后再打开中断。系统中的设备驱动、CPU切换、进程通信等功能中的部分操作都可定义为原语使它们成为内核的组成部分。 系统控制的数据结构及处理 系统中用来登记状态信息的数据结构很多如作业控制块、进程控制块PCB、设备控制块、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表 为了实现有效的管理系统需要一些基本的操作常见的如下3种 进程管理 进程状态管理、进程调度和分派、创建与撤销进程控制块等。 存储器管理 存储器的空间分配和回收、内存信息保护程序、代码对换程序等。 设备管理 缓冲区管理、设备分配和回收等 中断和异常的概念 系统不允许用户程序实现核心态的功能而它们又必须使用这些功能。因此需要在核心态建立一些“门”以便实现从用户态进入核心态。在实际操作系统中CPU运行上层程序时唯一能进入这些“门”的途径就是通过中断或异常。 发生中断或异常时运行用户态的CPU会立即进入核心态这是通过硬件实现的。 操作系统的发展过程大体上就是一个想方设法不断提高资源利用率的过程而提高资源利用率就需要在程序并未使用某种资源时把它对那种资源的占有权释放而这一行为就需要通过中断实现。 中断Interruption也称外中断指来自CPU执行指令以外的事件的发生 如设备发出的I/O结束中断表示设备输入/输出处理已经完成希望处理机能够向设备发下一个输入/输出请求同时让完成输入/输出后的程序继续运行。时钟中断表示一个固定的时间片已到让处理机处理计时、启动定时运行的任务等。这一类中断通常是与当前指令执行无关的事件即它们与当前处理机运行的程序无关。 异常Exception也称内中断、例外、或陷入trap指源自CPU执行指令内部的事件如程序的非法操作码、地址越界、算术溢出、虚存系统的缺页及专门的陷入指令等引起的事件。对异常的处理一般要依赖于当前程序的运行现场而且异常不能被屏蔽一旦出现应立即处理。 中断处理的过程 关中断 CPU响应中断后首先要保护程序的现场状态在保护现场的过程中CPU不应响应更高级中断源的中断请求。否则若现场保存不完整在中断服务程序结束后也就不能正确恢复并继续执行现行程序。 保存断点 为保证中断服务执行完毕后能正确地返回到原来的程序必须将原来的程序的**断点即程序计数器PC**保存起来。 中断服务程序寻址 实质是取出中断服务程序的入口地址送入程序计数器PC。 保存现场和屏蔽字 进入中断服务程序后首先要保存现场现场信息一般是指**程序状态字寄存器PSWRProgram Status Word Register**和某些通用寄存器的内容。 开中断 允许更高级中断请求得到响应 执行中断服务程序 这是中断请求的目的。 关中断 保证在恢复现场和屏蔽字时不被中断 恢复现场和屏蔽字 将现场和屏蔽字恢复到原来的状态 开中断、中断返回 中断服务程序的最后一条指令通常是一条中断返回指令使其返回到原程序的断点处以便继续执行原程序。 系统调用 指用户在程序中调用操作系统所提供的一些子功能系统调用可视为特殊的公共子程序。系统中的各种共享资源都由操作系统统一掌管因此在此用户程序中凡是与资源有关的操作存储分配、进行I/O传输及管理文件等都必须通过系统调用方式向操作系统提出服务请求并由操作系统代为完成。通常一个操作系统提供的系统调用命令由几十条乃至上百条之多。这些系统调用按功能可分为如下几类 设备管理 完成设备的请求或释放以及设备启动等功能 文件管理 完成文件的读、写、创建、删除等功能 进程控制 完成进程的创建、撤销、阻塞、唤醒等功能 进程通信 完成进程之间的消息传递或信号传递等功能 内存管理 完成内存的分配、回收、获取作用占用内存区大小、始址等功能 系统调用相关功能设计系统资源管理、进程管理之类的操作必须需要使用某些特权指令才能完成所以系统调用的处理需要由操作系统内核程序负责完成要运行在核心态。用户程序可以执行陷入指令又称防管指令或trap指令来发起系统调用请求操作系统提供服务。可以这么理解用户程序执行陷入指令相当于把CPU的使用权主动交给操作系统内核程序CPU状态会从用户态进入核心态之后操作系统内核程序再对系统调用请求作出相应处理。处理完成后操作系统内核程序又会把CPU的使用权还给用户程序即CPU状态会从核心态回到用户态。这么设计的目的是用户程序不能直接执行对系统影响非常大的操作必须通过系统调用方式请求操作系统代为执行以便保证系统的稳定性和安全性防止用户程序随意更改或访问重要的系统资源影响其他程序的运行 用户通过操作系统运行上层程序如系统提供的命令解释程序或用户自编程序而这个上层 程序的运行依赖于操作系统底层管理程序提供服务支持当需要管理程序服务时系统通过硬件中断机制进入核心态运行管理程序也可能是程序运行出现异常情况被动地需要管理程序的服务这时就通过异常处理来进入核心态。管理程序运行结束时用户程序需要继续运行此时通过相应的保存的程序现场退出中断处理程序或异常处理程序返回断点处继续执行。如下图 列举一些用户态转核心态的例子 用户程序要求操作系统的服务即系统调用发生一次中断用户程序中产生了一个错误状态用户程序中企图执行一条特权指令从核心态转用户态由一条指令实现这条指令也是特权指令一般是中断返回指令 由用户态进入核心态不仅状态需要切换而且所用的堆栈也可能需要用户堆栈切换为系统堆栈但这个系统堆栈也是属于该进程的。 用户态转核心态会用到访管指令访管指令是在用户态使用的所以它不可能是特权指令
操作系统的体系结构
大内核和微内核
大内核系统将操作系统的主要功能模块都作为一个紧密联系的整体运行在核心态从而为应用提供性能的系统服务。为解决操作系统的内核代码难以维护的问题提出了微内核的体系结构。它将内核中最基本的功能保留在内核将不需要在核心态执行的功能移到用户态执行从而降低了内核的设计复杂性。移出内核的操作系统代码根据分层的原则被划分成若干服务程序它们的执行相互独立交互则都借助于微内核进行通信。微内核结构有效地分离了内核与服务、服务与服务使得它们之间的接口更加清晰维护的代价大大降低各部分可以独立地优化和演进从而保证了操作系统的可靠性最大的问题是性能问题因为需要频繁地在核心态和用户态之间切换操作系统的执行开销偏大。因此有的操作系统把频繁使用的系统服务移回内核但体系结构不是引起性能下降的主要因素为减少切换开销也可以将系统服务作为运行库链接到用户程序这种体系结构称为库操作系统
总结
并行性和并发性的区别和联系 并行性 两个或多个事件在同一时刻发生 并发性 两个或多个事件在同一时间间隔发生 多道程序环境下并发性指一段时间内宏观上有多个程序同时运行但在单处理器系统中每个时刻仅能有一道程序执行因此微观上这些程序只能分时交替运行。但在多处理器系统中并发执行的程序被分配到多个处理器上实现并行执行 特权指令和非特权指令 特权指令必须在核心态执行CPU在核心态下可以执行指令系统的全集用户态下只能使用非特权指令使用特权指令时将产生中断以阻止用户使用从用户态转换为核心态的唯一途径是中断或异常 访管指令和访管中断 访管指令是一条可以在用户态下执行的指令在用户程序中因要求操作系统提供服务而有意识的使用访管指令从而产生一个中断事件自愿中断将操作系统转换为核心态称为访管中断。访管中断由访管指令产生程序员使用访管指令向操作系统请求服务访管指令本身不是特权指令基本功能是让程序拥有自愿进管的手段从而引起访管中断处于用户态的用户程序使用访管指令时系统根据访管指令的操作数执行访管中断处理程序访管中断管理程序将按系统调用的操作数和参数转到相应的例行子程序。完成服务功能后退出中断返回到用户程序断电继续执行。
进程管理 进程与线程
进程的概念和特征 进程的概念 多道程序环境下允许多个程序并发执行此时它们将失去封闭性并具有间断性和不可再现性的特征。为此引入了进程的概念用来描述、控制程序的并发执行实现操作系统的并发性、共享性。 为了使参与并发执行的程序含数据能独立地运行必须配置一个专门的数据结构称为进城控制块Process Control BlockPCB由程序段、相关数据段、PCB三部分组成了进程映像进程实体 创建进程实质上就是创建进程映像中的PCB。撤销进程实质上是撤销进程的PCB。进程映像是静态的进程是动态的 PCB是进程存在的唯一标志 进程进程实体的运行过程是系统进行资源分配、调度的一个独立单位 进程的特征 动态性 最基本的特性 进程是程序的一次执行有着创建、活动、暂停、终止等过程具有一定的生命周期是动态地产生、变化、消亡的 并发性 重要特征 多个进程实体同时存在于内存中能在一段时间内同时运行提高资源利用率 独立性 进程实体是一个能独立运行、独立获得资源、独立接受调度的基本单位凡未建立PCB的程序都不能作为一个独立的单位参与运行 异步性 由于进程的相互制约使得进程具有执行的间断性即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性为此在操作系统中必须配置相应的进程同步机制 结构性 每个进程都配置一个PCB对其进行描述。从结构上看进程实体是由程序段、数据段、进程控制块三部分组成的
进程的状态与转换 进程通常有以下5种状态前3种是基本状态 运行态 进程正在处理机上运行。在单处理机环境下每个时刻最多只有一个进程处于运行态 就绪态 进程获得了除处理机外的一切所需资源一旦得到处理机便可立即运行。将多个处理就绪状态的进程排成一个队列称为就绪队列 阻塞态 等待态 进程正在等待某一事件而暂停运行如等待某资源为可用不包括处理机或等待输入输出完成即使处理机空闲该进程也不能运行 创建态 进程正在被创建尚未转到就绪态。创建进程通常需要多个步骤 申请一个空白PCB向PCB填写一些控制、管理进程的信息由系统为该进程分配运行时所需资源把该进程转入就绪态 结束态 进程正在从系统中消失可能是进程正常结束或其他原因中断退出运行进程需要结束运行时系统首先将该进程置为结束态然后处理资源释放、回收 注意区分就绪态与等待态 之所以把处理机和其他资源划分开是因为在分时系统的时间片轮转机制中每个进程分到的时间片是若干毫秒。也就是说进程得到处理机的时间很短且频繁进程在运行过程中是频繁转到就绪态的。而其他资源如外设的使用、分配或某一事件的发生如I/O操作的完成对应的时间相对来说很长转到等待态的次数也相对较少 进程状态的转换 就绪态 - 运行态 获得处理机资源 运行态 - 就绪态 时间片用完后让出处理机可剥夺的操作系统中更高优先级的进程就绪时调度程序将正在执行的进程转换为就绪态让更高优先级的进程执行 运行态 - 阻塞态 进程请求某一资源如外设的使用、分配或等待某一事件的发生如IO操作的完成时进程以系统调用的形式请求操作系统提供服务这是一种特殊的、由运行用户态程序调用操作系统内核过程的形式 阻塞态 - 就绪态 进程等待的事件到来时如IO操作结束、中断结束 一个进程从运行态变成阻塞态是主动行为从阻塞态变成就绪态是被动行为需要其他进程的协助
进程控制 一般把进程控制用的程序段称为原语原语的特点是执行期间不允许中断是一个不可分割的基本单位 进程的创建 子进程可以继承父进程所拥有的资源子进程被撤销时应将其从父进程获得的资源归还给父进程操作系统创建一个新进程的过程如下创建原语 为新进程分配一个唯一的进程标识号申请一个空白的PCBPCB是有限的PCB申请失败则创建失败为进程分配资源为程序、数据、用户栈分配必要的内存空间在PCB体现 若资源不足如内存空间并不是创建失败而是处于阻塞态等待内存资源 初始化PCB主要包括初始化标志信息、处理机状态信息、处理机控制信息以及设置进程的优先级等若进程就绪队列能够接纳新进程则将新进程插入就绪队列等待被调度运行 进程的终止 引起进程终止的事件主要有 正常结束 表示进程的任务已完成并准备退出运行 异常结束 表示进程在运行时发生了某种异常事件使程序无法继续运行 如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、IO故障等 外界干预 进程应外界的请求而终止运行 如操作员/操作系统干预、父进程请求、父进程终止 操作系统终止进程的过程撤销原语 根据被终止进程的标识符检索PCB从中读出该进程的状态若被终止进程处于执行状态立即终止该进程的执行将处理机资源分配给其他进程若该进程还有子孙进程则将所有子孙进程终止将该进程拥有的所有资源或归还给父进程或归还给操作系统将PCB从所在队列链表中删除 进程的阻塞和唤醒 正在执行的进程由于期待的事件未发生请求系统资源失败、等待某种操作完成、新数据尚未到达、无新工作可做由系统自动执行阻塞原语Block使自己由运行态变为阻塞态 可见进程的阻塞是进程自身的一种主动行为也因此只有处于运行态的进程获得CPU才可能将其转为阻塞态。阻塞原语的执行过程如下 找到将要阻塞进程的标识号对应的PCB若该进程为运行态则保护其现场将其状态转为阻塞态停止运行把该PCB插入相应事件的等待队列将处理机资源调度给其他就绪进程 当被阻塞进程所期待的事件出现时启动的IO操作已完成、期待的数据已到达由有关进程释放该IO设备的进程、或提供数据的进程调用唤醒原语Wakeup将等待该事件的进程唤醒唤醒原语执行过程如下 在该事件的等待队列中找到相应进程的PCB将其从等待队列中移出并置其状态为就绪态把该PCB插入就绪队列等待调度程序调度 Block原语与Wakeup原语是一对作用相反的原语必须成对使用。Block原语是由被阻塞进程自我调用实现的Wakeup原语是由一个与被唤醒进程合作或被其他相关的进程调用实现的 进程切换 处理机从一个进程的运行转到另一个进程上运行在这个过程中进程的运行环境产生了实质性的变化。进程切换的过程如下 保存处理机上下文包括程序计数器、其他寄存器更新PCB信息把进程的PCB移入相应的队列 如就绪、在某事件阻塞等队列 选择另一个进程执行并更新其PCB更新内存管理的数据结构恢复处理机上下文 进程切换与处理机模式切换是不同的模式切换时处理机逻辑上可能还在同一进程中运行。若进程因中断、异常进入核心态运行执行完后又回到用户态刚被中断的程序运行则操作系统只需恢复进程进入内核时所保存的CPU现场而无需改变当前进程的环境信息。而切换进程则当前进程的环境信息需要改变。 调度和切换的区别调度是决定资源分配给哪个进程的行为是一种决策行为。切换是实际分配的行为是执行行为。一般来说先资源调度后进程切换
进程的组织 进程控制块 最核心 进程执行时系统通过其PCB了解进程的现行状态信息以便对其进行控制、管理管理结束时系统收回其PCB该进程随之消亡。 PCB主要包括进程描述信息、进程控制、管理信息、资源分配清单、处理机相关信息等详细如下 进程描述信息进程控制和管理信息资源分配清单处理及相关信息进程标识符PID)进程当前状态代码段指针通用寄存器值用户标识符UID进程优先级数据段指针地址寄存器值代码运行入口地址堆栈段指针控制寄存器值程序的外存地址文件描述符标志寄存器值进入内存时间键盘状态字处理机占用时间鼠标信号量使用 进程标识符标志各个进程每个进程都有唯一的标识号用户标识符进程归属的用户主要为共享、保护服务进程当前状态作为处理机分配调度的依据资源分配清单说明有关内存地址空间、虚拟地址空间的状况所打开文件的列表、使用的输入输出设备信息处理机相关信息处理机中各寄存器的值当进程被切换时处理机状态信息都必须保存在相应的PCB中以便在进程重新执行时能从断点继续执行 组织PCB的常用方式有链接方式和索引方式两种 链接方式 将同一状态的PCB链接成一个队列不同状态对应不同的队列也可把处于阻塞态的进程的PCB根据阻塞原因的不同排成多个阻塞队列 索引方式 将同一状态的进程组织在一个索引表中索引表的表项指向相应的PCB不同状态对应不同的索引表 如就绪索引表、阻塞索引表 程序段 能被进程调度程序调度到CPU执行的程序代码段。注意程序可被多个进程共享即多个进程可以运行同一程序 数据段 可以是进程对应的程序加工处理的原始数据也可以是程序执行时产生的中间、最终结果
进程的通信 PV操作是低级通信方式高级通信方式是以较高的效率传输大量数据的通信方式主要有3种 共享存储 通信的进程之间存在一块可直接访问的共享空间通过对这片共享空间进行读写操作实现进程之间的信息交换共享存储分两种 低级方式基于数据结构的共享高级方式基于存储区的共享 操作系统只负责为通信进程提供可共享使用的存储空间、同步互斥工具用户需自己安排读写指令完成数据交换用户程序空间一般都是独立的进程运行期间一般不能访问其他进程的空间而进程内的线程是自然共享进程空间的 消息传递 进程间的数据交换是以格式化的消息为单位的若通信的进程之间不存在可以直接访问的共享空间则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息、接收消息两个原语进行数据交换。 直接通信方式 发送进程直接把消息发送给接收进程并将它挂在接收进程的消息缓冲队列上接收进程从消息缓冲队列中取得消息 间接通信方式 信箱通信方式 发送进程把消息发送到某个中间实体或信箱接收进程从中间实体取得消息。该通信方式广泛应用于计算机网络中相应的通信系统称为电子邮件系统 管道通信 消息传递的一种特殊方式所谓管道是用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件又名pipe文件。 为了协调双方的通信管道机制必须提供三方面的能力互斥、同步、确定对方的存在 管道也是一种文件但是管道可以克服使用文件进行通信的两个问题 限制管道的大小 管道是一个固定大小的缓冲区在Linux中固定大小为4KB 读进程也可能工作的比写进程快 当这种情况发生时一个随后的read()调用将被阻塞等待某些数据被写入解决了**read()**调用返回文件结束的问题 从管道读数据是一次性操作数据一旦被读取它就从管道中被抛弃释放空间以便写更多的数据。管道只能采用半双工通信即某一时刻只能单向传输。要实现父子进程双方互动通信需要定义两个管道。 管道可以理解为共享存储的优化和发展因为在共享存储中若某进程要访问共享存储空间则必须没有其他进程在该共享存储空间进行写操作 PV操作是一种实现进程互斥、同步的有效方式与信号量的处理相关P表示通过的意思V表示释放的意思
线程概念和多线程模型 线程的基本概念 引入进程的目的是更好地使多道程序并发执行提高资源利用率、系统吞吐量。引入线程的目的是减小程序在并发执行时所付出的时空开销提高操作系统的并发性能线程是进程中的一个实体是被系统独立调度、分派的基本单位自己不拥有系统资源只拥有一点儿在运行时必不可少的资源引入线程后进程的内涵发生改变进程只作为除CPU外的系统资源的分配单元而线程作为处理机的分配单元。 线程与进程的比较 调度 同一进程中线程的切换不会引起进程切换。在不同进程中进行线程切换如从一个进程内的线程切换到另一个进程中的线程时会引起进程切换 拥有资源 进程拥有资源线程不拥有系统资源有一点儿必不可少的资源线程可以访问其隶属进程的系统资源 并发性 进程和线程都可以并发执行 系统开销 创建、撤销进程系统要为之分配、回收资源如内存空间、IO设备。因此开销比线程大切换进程涉及当前执行进程CPU环境的保存、新调度到进程CPU环境的设置。而切换线程只需保存、设置少量寄存器内容开销很小 地址空间和其他资源 进程的地址空间之间互相独立同一进程的各线程间共享进程的资源某进程内的线程对于其他进程不可见 通信方面 进程间通信IPC需要进程同步、互斥手段的辅助以保证数据的一致性而线程间可以直接读写进程数据段如全局变量来进行通信 线程的属性 是一个轻型实体不拥有系统资源但有一个唯一的标识符和一个线程控制块线程控制块记录了线程执行的寄存器、栈等现场状态不同的线程可以执行相同的程序即同一个服务程序被不同用户调用时操作系统把它们创建成不同的线程同一进程中的各个线程共享该进程所拥有的资源线程是处理机的独立调度单位多个线程是可以并发执行的。在单CPU的计算机系统中各线程可以交替地占用CPU若各个CPU同时为一个进程内的线程服务则可缩短进程的处理时间线程在生命周期内会经历阻塞态、就绪态、运行态等各种状态变化 线程的实现方式 用户级线程 User-Level Thread ULT 内核意识不到该种线程的创建、撤销、切换等通常应用程序从单线程开始在其运行的任何时刻可以通过调用线程库中的派生例程创建新线程 内核级线程 Kernel-Level Thread KLT、内核支持的线程 线程管理的所有工作由内核完成应用程序没有进行线程管理的代码只有一个到内核级线程的编程接口内核为进程机器内部的每个线程维护上下文信息调度也在内核 基于线程架构的基础上完成有些系统中使用组合方式的多线程实现。线程创建完全在用户空间中完成线程的调度、同步也在应用程序中进行。一个应用程序中的多个用户级线程被映射到一些小于等于用户级线程的数目内核级线程上 多线程模型 多对一模型 将多个用户级线程映射到一个内核级线程线程管理在用户空间完成。此模式中用户级线程对操作系统不可见即透明优点线程管理是在用户空间进行的效率比较高缺点一个线程在使用内核服务时被阻塞整个进程都会被阻塞多个线程不能并行地运行在多处理机上 一对一模型 将每个用户级线程映射到一个内核级线程优点一个线程被阻塞后允许另一个线程继续执行所以并发能力强缺点每创建一个用户级线程都需要创建一个内核级线程与其对应这样创建线程的开销比较大会影响到应用程序的性能 多对多模型 将n个用户级线程映射到m个内核级线程上要求** m ≤ n m \le n m≤n**特点克服了多对一模型的并发度不高的缺点克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点
处理机调度
调度的概念 调度的基本概念 对处理机进行分配即从就绪队列中按照一定的算法公平、高效地选择一个进程并将处理机分配给它运行以实现进程并发地执行 调度的层次 作业调度 高级调度 内存、辅存之间的调度对于每个作业只调入一次、调出一次多道批处理系统中大多配有作业调度其他系统通常不需要配置。作业调度的执行频率较低通常为几分钟一次 中级调度 内存调度 提高内存利用率、系统吞吐量将暂时不能运行的进程调至外存等待此时的进程状态称为挂起态。当具备运行条件、内存有空闲时由中级调度来决定把外存上的就绪进程重新调入内存修改器状态为就绪态挂在就绪队列上等待 进程调度 低级调度 按照某种方法、策略从就绪队列选取一个进程将处理机分配给它。进程调度是最基本的一种调度一般的操作系统都必须配置。进程调度频率很高一般几十毫秒一次。 三级调度的联系 作业调度从外存的后备队列中选择一批作业进入内存为它们建立进程这些进程被送入就绪队列进程调度从就绪队列中选出一个进程把其状态改为运行态把CPU分配给它。中级调度是为了提高内存的利用率系统将那些暂时不能运行的进程挂起来。当内存空间宽松时通过中级调度选择具备运行条件的进程将其唤醒。作业调度为进程活动做准备进程调度使进程正常活动起来中级调度将暂时不能运行的进程挂起中级调度处于作业调度、进程调度之间作业调度次数少中级调度次数略多进程调度频率最高进程调度是最基本的不可或缺
调度的时机、切换、过程 进程调度、切换程序是操作系统内核程序。 现代操作系统中不能进行进程的调度、切换的情况有以下几种 处理中断的过程中 中断处理过程复杂实现上很难做到进程切换而且中断处理是系统工作的一部分逻辑上不属于某一进程不应被剥夺处理机资源 进程在操作系统内核程序临界区中 进入临界区后需要独占式地访问共享数据理论上必须加锁以防止其他并行程序进入在解锁前不应切换到其他进程运行以加快该共享数据的释放 其他需要完全屏蔽中断的原子操作过程中 如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中连中断都要屏蔽更不应该进行进程调度、切换 若在上述过程中发生了引起调度的条件则不能马上进行调度、切换应置系统的请求调度标志直到上述过程结束后才进行相应的调度、切换 应该进行进程调度、切换的情况如下 发生引起调度条件、当前进程无法继续运行下去时可以马上调度切换。若操作系统只在这种情况下进行进程调度则是非剥夺调度 中断处理结束、自陷处理结束后返回被中断进程的用户态程序执行现场前若置上请求调度标志即可马上进行进程调度、切换。若操作系统支持这种情况下的运行调度程序则实现了剥夺方式调度 进程切换往往在调度完成后立刻发生它要求保存原进程当前切换点的现场信息恢复被调度进程的现场信息。现场切换时操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后开始运行新的进程
进程调度方式
非剥夺调度方式 非抢占方式 当一个进程正在处理机上执行时即使有某个更为重要的进程进入就绪队列仍然让正在执行的进程继续执行直到该进程完成或发生某种事件而进入阻塞态时才把处理机分配给更为重要或紧迫的进程一旦把CPU分配给一个进程该进程就会保持CPU直到终止或转换到等待态。优点是实现简单、系统开销小适用于大多数的批处理系统但不能用于分时系统、大多数的实时系统 剥夺调度方式 抢占方式 当一个进程正在处理机上执行时若有某个更为重要的进程需要使用处理机则立即停止正在执行的进程将处理机分配给这个更重要的进程提高系统吞吐率、响应效率但剥夺不是一种任意性行为必须遵循一定的原则主要有优先权、短进程优先、时间片原则等
调度的基本准则
CPU利用率 尽可能使CPU保持忙状态 系统吞吐量 单位时间内CPU完成作业的数量。 周转时间 从作业提交到作业完成所经历的时间是作业等待、就绪队列排队、处理机运行、进行输入输出操作所花费时间的总和周转时间 作业完成时间 - 作业提交时间带权周转时间是作业周转时间与作业实际运行时间的比值 带权周转时间 作业周转时间 / 作业实际运行时间 等待时间 进程处于等处理机状态的时间之和 处理机调度算法实际上不影响作业执行、输入输出操作时间只影响作业在就绪队列中等待所花的时间。因此衡量一个调度算法的优劣只需简单考查等待时间 响应时间 从用户提交请求到系统首次产生响应所用的时间。在交互式系统中一般采用响应时间而不是周转时间作为衡量调度算法的重要准则。从用户角度看调度策略应尽量降低响应时间
典型的调度算法 先来先服务FCFS调度算法 最简单的调度算法可用于作业调度、进程调度 作业调度中从后备作业队列中选最先进入该队列的一个或几个作业调入内存分配资源创建进程放入就绪队列进程调度中从就绪队列选择最先进入该队列的进程分配处理机 属于不可剥夺算法对所有作业都公平长作业先到达会使后面许多短作业等待长时间因此不能作为分时系统、实时系统的主要调度策略 被结合在其他调度策略中使用 在使用优先级作为调度策略的系统中对多个具有相同优先级的进程按FCFS原则处理 特点是算法简单、但效率低。对长作业有利不利于短作业相对于SJF、高响应比有利于CPU繁忙型作业不利于IO繁忙型作业。 短作业优先SJF调度算法 缺点 对长作业不利长作业周转时间会增加。可能导致长期不被调度饥饿现象区分死锁前者是调度策略问题后者是系统环形等待未考虑作业的紧迫程度作业的长短只是根据用户所提供的估计执行时间而定不一定能真正做到短作业优先调度 SJF调度算法的平均等待时间、平均周转时间最少 优先级调度算法 可用于作业调度、进程调度根据新的更高优先级进程能否抢占正在执行的进程该调度算法可分如下两种 非剥夺式优先级调度算法 让正在运行的进程继续执行直到由于自身的原因而主动让出处理机任务完成、或等待事件 剥夺式优先级调度算法 立即暂停正在执行的进程 根据进程创建后其优先级是否可以改变可分为两种 静态优先级 优先级在创建进程时确定在运行期间不变。确定优先级的主要依据有进程类型、进程对资源的要求、用户要求 动态优先级 进程运行时动态调整优先级调整优先级的依据有进程占有CPU时间的长短、就绪进程等待CPU时间长短 一般来说进程优先级的设置可以参照以下原则 系统进程 用户进程交互型进程 非交互型进程前台进程 后台进程IO型进程 计算型进程 IO设备的处理速度比CPU慢得多因此将IO型进程的优先级设置得更高更有可能让IO设备尽早开始工作进而提升系统的整体效率 高响应比优先调度算法 用于作业调度对FCFS、SJF的一种综合平衡。在每次进行作业调度时先计算后备作业队列中每个作业的响应比选出最高的作业运行 响应比 R p 等待时间 要求服务时间 要求服务时间 响应比R_p \frac{等待时间要求服务时间}{要求服务时间} 响应比Rp要求服务时间等待时间要求服务时间 作业的等待时间相同时要求服务时间越短响应比越高利于短作业要求服务时间相同时等待时间越长响应比越高因此实现的是先来先服务对于长作业也是因此克服了饥饿状态 时间片轮转调度算法 适用于分时系统时间片的大小对系统性能影响很大若时间片足够大以至于所有进程都能在一个时间片内执行完毕则算法退化成先来先服务调度算法。若时间片很小则处理机将频繁地在进程间切换使处理机开销增大时间片的长短通常由以下因素确定系统的响应时间、就绪队列中的进程数目、系统的处理能力 多级反馈队列调度算法 是时间片轮转调度算法和优先级调度算法的综合发展通过动态调整进程优先级、时间片大小该算法可以兼顾多方面的系统目标 实现思想 设置多个就绪队列赋予不同的优先级第1级队列优先级最高赋予各个队列中进程执行时间片的大小各不相同。优先级越高的队列每个进程的运行时间片越小一个新进程进入内存后放入第1级队列末尾按FCFS原则排队等待调度。当轮到该进程执行时如能在该时间片内完成便可准备撤离系统若未完成该进程进入第2级队列末尾再同样按照FCFS等待调度执行以此轮转仅当第1级队列为空调度程序才调度第2级队列中的进程以此类推。若处理机正在执行第i级队列中的某进程时有新进程进入优先级较高的队列则新进程将抢占正在运行进程的处理机即由调度程序把正在运行的进程放回第i级队列的末尾把处理机分配给新进程 优点 终端型作业用户 短作业优先 短批处理作业用户 周转时间较短 长批处理作业用户 经过前面几个队列得到部分执行不会长期得不到处理
进程同步
进程同步的基本概念 临界资源 一次仅允许一个进程使用的资源 许多物理设备都属于临界资源。许多变量、数据等都可以被若干进程共享也属于临界资源 对临界资源的访问必须互斥地进行在每个进程中访问临界资源的那段代码称为临界区为了保证临界资源的正确使用可把访问临界资源的过程分为4部分 进入区 先检查可否进入临界区能进则设置正在访问临界区的标志以阻止其他进程同时进入临界区 临界区 进程中访问临界资源的那段代码称临界段 退出区 将正在访问临界区的标志清除 剩余区 代码中的其余部分 do {entry section;critical section;exit section;remainder section;
} while (true)同步 制约关系 为完成某种任务而建立两个或多个进程因为需要协调这些进程的工作次序而等待、传递信息所产生的制约关系 互斥 间接制约关系 当一个进程进入临界区使用临界资源时另一个进程必须等待直到该进程退出临界区为禁止两个进程同时进入临界区同步机制应遵循以下准则 空闲让进 临界区空闲时可以允许一个请求进入临界区的进程立即进入临界区 忙则等待 已有进程进入临界区时其他试图进入临界区的进程必须等待 有限等待 对请求访问的进程应保证能在有限时间内进入临界区 让权等待 当进程不能进入临界区时应立即释放处理器防止进程忙等待
实现临界区互斥的基本方法 软件实现方法 单标志法 设置一个公用整型变量turn用于指示被允许进入临界区的进程编号若turn0允许 P 0 P_0 P0进程进入临界区。但两个进程必须交替进入临界区若某个进程不再进入临界区则另一个进程也将无法进入临界区。违背空闲让进 只有一个公用变量且某个进程出来时并不重置该公用变量需要依赖其他进程改变该公用变量以让该进程能重新进入 双标志法先检查 每个进程访问临界区资源之前先查看临界资源是否正被访问若正被访问该进程需等待否则进程才进入自己的临界区。为此设置一个数据flag[i]如第i个元素值为FALSE表示** P i P_i Pi进程未进入临界区值为TRUE**表示进入临界区。 优点是不用交替进入可连续使用。缺点是两个进程可能同时进入临界区。 双标志法后检查 算法二先检测对方的进程状态标志再置自己的标志由于在检测、放置中可插入另一个进程到达时的检测操作会造成两个进程在分别检测后同时进入临界区。为此该算法先将自己的标志设置为TRUE再检测对方的状态标志若对方标志为TRUE则进程等待否则进入临界区 两个进程几乎同时都想进入临界区时分别将自己的标志值flag设置TRUE并同时检测对方的状态执行while语句发现对方也要进入临界区时双方互相谦让导致都无法进入形成饥饿现象 Petersons Alogrithm 为了防止两个进程为进入临界区而无限期等待又设置了变量turn每个进程在先设置自己的标志后再设置turn标志。 利用flag解决临界资源的互斥访问利用turn解决饥饿现象 硬件实现方法 中断屏蔽方法 禁止一切中断发生或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完进而保证互斥的正确实现然后执行开中断即关中断 - 临界区 - 开中断这种方法限制了处理机交替执行程序的能力因此执行效率明显降低。对内核来说在它执行更新变量或列表的几条指令期间关中断是很方便的但将关中断的权利交给用户则很不明智若一个进程关中断后不再开中断则系统可能会因此终止 硬件指令方法 TestAndSet指令这条指令是原子操作即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。 可以为每个临界资源设置一个共享布尔变量lock表示资源的两种状态true表示正被占用初值为false。在进程访问临界资源之前利用TestAndSet检查和修改标志lock若有进程在临界区则重复检查直到进程退出。 Swap指令该指令的功能是交换两个字字节的内容 以上对TestAndSet和Swap指令的描述仅是功能实现而非软件实现的定义。事实上它们是由硬件逻辑直接实现的不会被中断 应为每个临界资源设置一个共享布尔变量lock初值为false在每个进程中再设置一个局部布尔变量key用于与lock交换信息。在进入临界区前先利用Swap指令交换lock与key的内容然后检查key的状态有进程在临界区时重复交换和检查过程直到进程退出。 优点是适用于任意数目的进程不管是单处理机、多处理机简单、容易验证其正确性支持进程内有多个临界区只需为每个临界区设置一个布尔变量 缺点是进程等待进入临界区时要耗费处理时间不能实现让权等待。从等待进程中随机选择一个进入临界区有的进程可能一直选不上从而导致饥饿现象
信号量 信号量机制是一种功能较强的机制可用来解决互斥与同步问题只能被两个标准原语waitS、signalS访问也可记为P操作和V操作 原语指完成某种功能且不被分割、不被中断执行的操作序列通常可由硬件实现。原语功能不被中断执行的特性在单处理机上可由软件通过屏蔽中断方法实现 整型信号量 一个用于表示资源数目的整型量S该机制并未遵循让权等待准则而是使进程处于忙等状态 记录型信号量 不存在忙等现象的进程同步机制。除需要一个用于代表资源数目的整型变量value外再增加一个进程链表L用于链接所有等待该资源的进程。当资源已分配完毕进程应调用block原语进行自我阻塞放弃处理机并插入资源的等待队列即该机制遵循了让权等待准则当进程释放一个资源是系统中可供分配的资源数增1但是资源数value依然value 0表示在队列中仍有等待该资源的进程被阻塞因此还应调用wakeup原语将队列中的第一个等待进程唤醒 利用信号量实现同步 利用信号量实现进程互斥 利用信号量实现前驱关系 为使各程序段能正确执行应设置若干初始值为0的信号量。例如为保证** S 1 → S 2 S 1 → S 3 S_1 \rightarrow S_2S_1 \rightarrow S_3 S1→S2S1→S3**的前驱关系应分别设置信号量a1a2。同样其他程序段类似 分析进程同步和互斥问题的方法步骤 关系分析 找出问题中的进程数分析它们之间的同步、互斥关系。 整理思路 找出解决问题的关键点并根据做过的题目找出求解的思路。根据进程的操作流程确定P操作、V操作的大致顺序 设置信号量 根据前面两步设置需要的信号量确定初值完善整理
管程
管程的定义 代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序这组操作能同步进程、改变管程中的数据管程由4部分组成 管程的名称局部于管程内部的共享结构数据说明对该数据结构进行操作的一组过程或函数对局部于管程内部的共享数据设置初始值的语句 类比面向对象开发管程很像一个类 管程把对共享资源的操作封装起来 管程内的共享数据结构只能被管程内的过程所访问一个进程只有通过调用管程内的过程才能进入管程访问共享资源 每次仅允许一个进程进入管程从而实现进程互斥 条件变量 当一个进程进入管程后被阻塞直到阻塞的原因解除时在此期间如果该进程不释放管程那么其他进程无法进入管程。为此将阻塞原因定义为条件变量condition。通常一个进程被阻塞的原因可以有多个因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列用于记录因该条件变量而阻塞的所有进程对条件变量只能进行两种操作即wait、signal x.wait 当x对应的条件不满足时正在调用管程的进程调用x.wait将自己插入x条件的等待队列并释放管程。此时其他进程可以使用该管程。 x.signal x对应的条件发生了变化则调用x.signal唤醒一个因x条件而阻塞的进程 条件变量 VS 信号量 相似点条件变量的wait/signal操作类似于信号量的P/V操作可以实现进程的阻塞/唤醒不同点条件变量是没有值的仅实现了排队等待功能而信号量是有值的反映了剩余资源数而在管程中剩余资源数用共享数据结构记录
经典同步问题
生产者-消费者问题哲学家进餐问题
死锁
死锁的概念 定义 多个进程因竞争资源而造成的一种僵局互相等待若无外力作用这些进程将无法向前推进 产生原因 系统资源的竞争 只有对不可剥夺资源的竞争才可能产生死锁对可剥夺资源的竞争不会引起死锁 进程推进顺序非法 进程运行过程中请求、释放资源的顺序不当同样会导致死锁。信号量使用不当也会造成死锁 死锁产生的必要条件 互斥条件 进程要求对所分配的资源进行排他性控制即一段时间内某资源仅为一个进程所占有 不剥夺条件 进程所获得的资源在未使用完之前不能被其他进程强行夺走只能主动释放 请求并保持条件 进程已经保持了至少一个资源但是又提出了新的资源请求而该资源已被其他进程占用此时请求进程被阻塞但对自己获得的资源保持不放 循环等待条件 存在一种进程资源的循环等待链链中每个进程已获得的资源同时被链中下一个进程所请求。 直观上看循环等待条件似乎和死锁的定义一样其实不然按死锁定义构成等待环所要求的条件更严它要求 P i P_i Pi等待的资源必须由 P i 1 P_{i1} Pi1来满足而循环等待条件无此限制。 如下所示资源分配图含圈而不一定造成死锁的原因是同类资源数大于1但若系统中每类资源都只有一个资源则含圈就变成了系统出现死锁的充要条件 注意区分不剥夺条件和请求并保持条件
死锁的处理策略 为使系统不发生死锁必须破环死锁的4个必要条件之一或允许死锁产生但当死锁发生时能检测出死锁并有能力实现恢复 死锁预防 设置限制条件破坏死锁产生的4个必要条件 避免死锁 在资源的动态分配过程中用某种方法防止系统进入不安全状态从而避免死锁 死锁的检测及解除 不采取任何限制性措施允许发生死锁。通过系统检测及时检测出死锁的发生然后采取措施解除 思索处理策略的比较 资源分配策略各种可能模式优点缺点死锁预防保守宁可资源闲置一次请求所有资源资源剥夺资源按序分配适用于突发式处理的进程不必进行剥夺效率低可进城初始化时间延长剥夺次数过多不便灵活申请新资源死锁避免是预防和检测的折中在运行时判断是否可能死锁寻找可能的安全允许顺序不必进行剥夺必须知道将来的资源需求进程不能被长时间阻塞死锁检测宽松只要允许就分配资源定期检查死锁是否已经发生不延长进程初始化时间允许对死锁进行现场处理通过剥夺解除死锁造成损失
死锁预防
破坏互斥条件 允许系统资源都能共享使用时系统不会进入死锁状态。但有些资源不能同时访问所以不太可行 破坏不剥夺条件 当一个已保持了某些不可剥夺资源的进程请求新的资源而得不到满足时它必须释放已经保持的所有资源待以后需要时再重新申请这种方法常用于状态易于保存、恢复的资源如CPU的寄存器、内存资源一般不能用于打印机之类的资源 破环请求并保持条件 采用预先静态分配方法即进程在运行前一次申请完它所需要的全部资源在它的资源未满足前不让其运行。一旦投入运行这些资源一直归它所有不再提出其他资源请求优点是实现简单缺点是系统资源被严重浪费有些资源可能仅在运行初期或运行快结束时才使用甚至根本不使用。而且还会导致饥饿现象由于个别资源长期被其他进程占用时将致使等待该资源的进程迟迟不能开始运行。 破坏循环等待条件 采用顺序资源分配法给系统中的资源编号规定每个进程必须按编号递增的顺序请求资源同类资源一次申请完。 只要进程提出申请分配资源 R i R_i Ri则该进程以后的资源申请中就只能申请编号大于 R i R_i Ri的资源 缺点 编号必须相对稳定这就限制了新类型设备的增加也经常会发生作业使用资源的顺序与系统规定顺序不同的情况造成资源的浪费按规定次序申请资源的方法也必然会给用户的编程带来麻烦
死锁避免 系统安全状态 允许进程动态地申请资源但系统在进行资源分配之前应先计算此次分配的安全性。若此次分配不会导致系统进入不安全状态则允许分配否则让进程等待安全状态是指系统能按某种进程推进顺序为每个进程分配其所需的资源直至满足某个进程对资源的最大需求使每个进程都可顺序完成。此时称该推进顺序为安全序列。若系统无法找到一个安全序列则称系统处于不安全状态。并非所有的不安全状态都是死锁状态但当系统进入不安全状态后便可能进入死锁状态反之只要系统处于安全状态系统便可便避免进入死锁状态 银行家算法 进程运行之前先声明对各种资源的最大需求量 当进程在执行中继续申请资源时先测试该进程已占用的资源数与本次申请的资源数之和是否超过该进程声明的最大需求量 若超过则拒绝分配资源若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量 若能满足则按当前的申请量分配资源否则推迟分配 数据结构描述 可利用资源向量 Available 含有m个元素数组其中每个元素代表一类可用的资源数目。Available[j] K表示系统中现有 R j R_j Rj类资源K个 最大需求矩阵 Max n × m n\times m n×m矩阵定义系统中n个进程中的每个进程对m类资源的最大需求。简单来说一行代表一个进程一列代表一类资源。Max[i, j]K表示进程i需要** R j R_j Rj类资源的最大数目为K**。 分配矩阵 Allocation n × m n \times m n×m矩阵定义系统中每类资源当前已分配给每个进程的资源数。Allocation[i, j] K表示进程i当前已分得** R j R_j Rj类资源的数目为K** 需求矩阵 Need n × m n \times m n×m矩阵表示每个进程接下来最多还需要多少资源。Need[i, j] K表示进程i还需要** R i R_i Ri类资源的数目为K** 三个矩阵间存在下述关系 N e e d M a x − A l l o c a t i o n Need Max - Allocation NeedMax−Allocation 一般情况下在银行家算法题目中Max矩阵和Allocation矩阵是已知条件而求出Need矩阵是解题第一步 安全性算法 设置工作向量Work有m个元素表示系统中的剩余可用资源数目。在执行安全性算法开始时WorkAvailable 初始时安全序列为空从Need矩阵中找出符合下面条件的行 该行对应的进程不在安全序列中而且该行小于等于Work向量 找到后把对应进程加入安全序列找不到则执行步骤4 进程 P i P_i Pi进入安全序列后可顺利执行直至完成并释放分配给它的资源因此应执行Work Work Allocation[i]其中Allocation[i]表示进程 P i P_i Pi代表的在Allocation矩阵中对应的行返回步骤2若此时安全序列中已有所有进程则系统处于安全状态否则系统处于不安全状态
死锁检测和解除 资源分配图 系统死锁可利用资源分配图来描述 圆圈代表一个进程框代表一类资源。由于一种类型的资源可能有多个因此用框中的一个圆代表一类资源中的一个。 进程到资源的有向边称为请求边 表示该进程申请一个单位的该类资源 资源到进程的边称为分配边 表示该类资源已有一个分配了该进程 死锁定理 在资源分配图中找出既不阻塞又不孤点的进程P 即找出一条有向边与它相连且该有向边对应的资源的申请数量小于等于系统中已有的空闲资源数量。若所有连接该进程的边均满足上述条件则这个进程能继续运行直至完成然后释放它所占有的所有资源 消去它所有的请求边和分配边使之称为孤立的结点 若能消去图中所有的边则称该图是可完全简化的 系统状态为死锁的条件是当且仅当系统状态的资源分配图是不可完全简化的该条件为死锁定理 死锁解除 资源剥夺法 挂起一部分死锁进程抢占它的资源把资源分配给其他的死锁进程 应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态 撤销进程法 强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行 进程回退法 让一个或多个进程回退到足以回避死锁的地步进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息设置还原点
总结 为什么要引入进程 为了深刻描述程序动态执行过程的性质以更好地支持和管理多道程序的并发执行 什么是进程由什么组成 进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。可以申请、拥有系统资源是一个动态的概念是一个活动实体。通过程序计数器的值、处理寄存器的内容来表示进程实体由程序段、数据段、PCB三部分构成 为什么要进行处理机调度 可在运行进程等待外部设备时把处理机调度给其他进程提高处理机利用率 为什么会产生死锁产生死锁有什么条件 两个或以上进程占有自身的资源并请求对方的资源时会导致每个进程都无法向前推进这就是死锁死锁的必要条件 互斥条件 进程要求分配的资源是排他性的最多只能同时供一个进程使用 不剥夺条件 进程在使用完资源之前资源不能被强制夺走 请求并保持条件 进程占有自身本来拥有的资源并要求其他资源 循环等待条件 存在一种进程资源的循环等待链 解决死锁的办法 预防死锁 设立限制条件破坏死锁的必要条件让死锁无法发生 避免死锁 在动态分配资源的过程中用一些算法防止系统进入不安全状态从而避免死锁 死锁的检测与解除 死锁产生前不采取任何措施只检测当前系统有没有发生死锁若有采取措施解除 银行家算法的工作原理 主要思想是避免系统进入不安全状态。在每次进行资源分配时它首先检查系统是否有足够的资源满足要求若有则先进行分配并对分配后的新状态进行安全性检查。若新状态安全则正式分配上述资源否则拒绝分配上述资源。
内存管理
内存管理概念
内存管理的基本原理和要求 内存空间的分配与回收 操作系统完成主存储器空间的分配、管理使程序员拜托存储分配的麻烦提高编程效率 地址转换 多道程序环境下程序中的逻辑地址与内存中的物理地址不可能一致因此存储管理必须提供地址变换功能把逻辑地址转换成相应的物理地址 内存空间的扩充 利用虚拟存储技术、自动覆盖技术从逻辑上扩充内存 存储保护 保证各道作业在各自的存储空间内运行互不干扰 进程运行的基本原理 程序装入和链接 创建进程首先要将程序、数据装入内存。将用户源程序变为可在内存中执行的程序通常需要以下几个步骤 编译 由编译程序将用户源代码编译成若干目标模块 链接 由链接程序将编译后的一组目标模块及所需的库函数链接在一起形成一个完整的装入模块 装入 由装入程序将装入模块装入内存运行 程序的链接有以下三种方式 静态链接 程序运行之前先将各目标模块及它们所需的库函数链接成一个完整的可执行程序以后不再拆开 装入时动态链接 将用户源程序编译后得到的一组目标模块在装入内存时采用边装入边链接的方式 运行时动态链接 对某些目标模块的链接是在程序执行中需要该目标模块时才进行的。优点是便于修改、更新便于实现对目标模块的共享 内存装入模块装入内存的三种方式 绝对装入 知道程序将驻留在内存的某个位置则产生绝对地址的目标代码由于程序中的逻辑地址与实际内存地址完全相同因此不需要对程序和数据的地址进行修改只适用于单道程序环境程序中使用的绝对地址可在编译、汇编时给出也可由程序员直接赋予 通常程序中采用符号地址编译或汇编时再转为绝对地址 可重定位装入 多道程序环境下多个目标模块的起始地址通常都从0开始程序中的其他地址都是相对于起始地址的装入时对目标程序中的指令和数据的修改过程称为重定位 地址变换通常是在装入时一次完成的所以又称静态重定位静态重定位的特点是一个作业装入内存时必须给它分配要求的全部内存空间若没有足够的内存则不能装入该作业。此外作业一旦进入内存整个运行期间就不能在内存中移动也不能再申请内存空间 动态运行时装入 动态重定位 程序在内存中若发生移动则需要采用动态装入方式。 装入程序把装入模块装入内存后不立即把装入模块的相对地址转换为绝对地址而是推迟到程序真正要执行的时候才进行。因此装入内存后所有的地址均为相对地址这种方式需要一个重定位寄存器的支持 特点是可以将程序分配到不连续的存储区中在程序运行之前可以只装入它的部分代码即可投入运行之后在程序运行期间根据需要动态申请分配内存便于程序段的共享可以向用户提供一个比存储空间大得多的地址空间 逻辑地址空间与物理地址空间 编译后每个目标模块都从0号单元开始编址这称为目标模块的相对地址或逻辑地址当链接程序将各个模块链接成一个完整的可执行目标程序时链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。不同进程可以有相同的逻辑地址因为相同的逻辑地址可以映射到主存的不同位置物理地址空间是指内存中物理单元的集合是地址转换的最终地址进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时必须通过地址转换将逻辑地址转换成物理地址这个过程称为地址重定位 内存保护 内存分配前需要保护操作系统不受用户进程的影响同时保护用户进程不受其他用户进程的影响。内存保护可采取两种方法 在CPU中设置一对上、下限寄存器存放用户作业在主存中的下限与上限地址每当CPU要访问一个地址时分别和两个寄存器的值相比判断有无越界 采用重定位寄存器或基址寄存器和界地址寄存器或限长寄存器来实现这种保护。重定位寄存器含物理地址的最小值界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须小于界地址寄存器内存管理机构动态地将逻辑地址与界地址寄存器进行比较若未发生地址越界则加上重定位寄存器的值后映射成物理地址再送交内存单元 实现内存保护需要重定位寄存器和界地址寄存器因此要注意两者区别。重定位寄存器用来加的逻辑地址加上重定位寄存器的值就能得到物理地址界地址寄存器是用来比的通过比较界地址寄存器的值与逻辑地址的值来判断是否越界
连续分配管理方式 单一连续分配 内存在此方式下分为系统区、用户区系统区仅供操作系统使用通常在低地址部分用户区为用户提供的、除系统区之外的内存空间这种方式不需要内存保护因为内存中永远只有一道程序肯定不会因越界影响其他程序优点是简单、无外部碎片可以采用覆盖技术不需要额外的技术支持缺点是只能用于单用户、单任务的操作系统中有内部碎片存储器的利用率极低 固定分区分配 最简单的一种多道程序存储管理方式将用户内存空间划分为若干固定大小的区域每个分区只能装入一道作业。当有空闲分区时便可再从外存的后备作业队列中选择适当大小的作业装入该分区如此循环 固定分区分配有两种划分分区的方法 分区大小相等 用于利用一台计算机去控制多个相同对象的场合缺乏灵活性 分区大小不等 划分为多个较小的分区、适量的中等分区、少量大分区 为了便于内存分配通常将分区按大小排队并建立分区说明表其中各表项包括每个分区的始址、大小、状态是否已分配 当有用户程序要装入时便检索该表以找到合适的分区给予分配并将其状态置为已分配 未找到合适分区时则拒绝为该用户程序分配内存 这种方式存在两个问题 程序可能太大而放不进任何一个分区中这时候用户不得不使用覆盖技术来使用内存空间主存利用率低当程序小于固定分区大小时也占用一个完整的内存分区空间这样分区内部就存在空间浪费这种现象称为内部碎片 固定分区是可用于多道程序设计的最简单的存储分配无外部碎片但不能实现多进程共享一个主存区所以存储空间利用率低。很少用于现代通用操作系统但可用于控制多个相同对象的控制系统 动态分区分配 可变分区分配 不预先划分内存而是在进程装入内存时根据进程的大小动态地建立分区并使分区的大小正好适合进程的需要 因此系统中分区的大小、数目是可变的 动态分区在开始分配时是很好的但之后会导致内存中出现许多小的内存块即外部碎片指在所有分区外的存储空间会变成越来越多的碎片与固定分区的内部碎片正好相对。 克服外部碎片可通过紧凑技术Compaction来解决即操作系统不时地对进程进行移动、整理。但这需要动态重定位寄存器的支持且相对费时 紧凑过程类似于Window系统中的磁盘整理程序只不过后者是对外存空间的紧凑 在进程装入或换入主存时若内存中有多个足够大的空闲块则操作系统必须确定分配哪个内存块给进程使用这就是动态分区的分配策略 首次适应First Fit算法 空闲分区以地址递增的次序链接。分配内存时顺序查找找到大小能满足要求的第一个空闲分区 最佳适应Best Fit算法 空闲分区按容量递增的方式形成分区链找到第一个能满足要求的空闲分区 最坏适应Worst Fit算法 **最大适应Largest Fit**算法 空闲分区以容量递减的次序链接找到第一个能满足要求的空闲分区即挑选出最大的分区。 邻近适应Next Fit算法 循环首次适应算法 由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找 以上几种方法的评价 首次适应算法是最简单、最好、最快的。不过首次适应算法会使得内存的低地址部分出现很多小的空闲分区而每次分配查找时都要经过这些分区因此增加了查找的开销邻近适应算法试图解决这个问题但实际上它常导致在内存的末尾分配空间分裂成小碎片。因为在一遍扫描中内存前面部分使用后再释放不会参与分配。它通常比首次适应算法更差。最佳适应算法虽然称为最佳但是性能通常很差因为每次最佳的分配会留下很小的难以利用的内存块会产生最多的外部碎片最坏适应算法与最佳适应算法相反它把最大的连续内存划分开会很快导致没有可用的大内存块因此性能也非常差。 三种内存分区管理方式的比较 作业道数内部碎片外部碎片硬件支持可用空间管理解决碎片方法解决空间不足提高作业道数单道连续分配1有无界地址寄存器、越界检查机构--覆盖交换多道固定连续分配 ≤ N \le N ≤N用户空间划为N块有无上下界寄存器、越界检查机构、基地址寄存器、长度寄存器、动态地址转换机构----多道可变连续分配-无有同上数组、链表紧凑--以上三种内存分区管理方法有一个共同特点即用户进程或作业在主存中都是连续存放的
非连续分配管理方式 根据分区大小是否固定分为分页存储管理方式和分段存储管理方式 分页存储管理方式 根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式 基本分页存储管理方式 固定分区产生内部碎片动态分区产生外部碎片这两种技术的内存利用率都比较低。这就引入了分页思想 把主存空间划分为大小相等且固定的块块相对较小作为主存的基本单位。每个进程也以块为单位进行划分进程在执行时以块为单位逐个申请主存中的块空间 分页的方法从形式上看像分区相等的固定分区技术分页管理不会产生外部碎片。本质的不同点是块的大小相对分区要小很多而且进程也按照块进行划分进程运行时按块申请主存可用空间并执行。这样进程只会在为最后一个不完整的块申请一个主存空间时才产生主存碎片所以尽管会产生内部碎片但这种碎片相对于进程来说也是很小的每个进程平均只产生半个块大小的内部碎片也称页内碎片 分页存储的几个概念 页面和页面大小 进程中的块称为页Page内存中的块称为页框Page Frame或页帧。外存也以同样的单位进行划分直接称为块Block。进程在执行时需要申请主存空间即要为每个页面分配主存中的可用页框为方便地址转换页面大小应该是2的整数幂。同时页面大小应该适中页面太小会使进程的页面数过多这样页表就会过长占用大量内存也会增加硬件地址转换的开销降低页面换入换出的效率页面过大又会使页内碎片增多降低内存的利用率 地址结构 逻辑地址结构如下 地址长度为32位011**位是页内地址**1231位是页号地址空间最多允许** 2 20 2^{20} 220**页 地址结构决定了虚拟内存的寻址空间有多大在实际问题中页号、页内偏移、逻辑地址大多都是用十进制数给出的。 题目用二进制地址的形式给出时读者要会转换 页表 为了便于在内存中找到进程的每个页面所对应的物理块系统为每个进程建立一张页表它记录页面在内存中对应的物理块号页表一般存放在内存中 配置页表后进程执行时通过查找该表即可找到每页在内存中的物理块号。 页表由页表项组成页表项与地址都由两部分构成第一部分都是页号但页表项第二部分是物理内存中的块号地址第二部分是页内偏移。页表项第二部分与地址第二部分共同组成物理地址。 基本地址变换机构 将逻辑地址转换为内存中的物理地址地址变换借助于页表实现 在系统中通常设置一个页表寄存器PTR存放页表在内存的起始地址F和页表长度M。进程未执行时页表的始址、长度存放在进程控制块中当进程执行时才将页表始址、长度存入页表寄存器。设页面大小为L逻辑地址A到物理地址E的变换过程如下逻辑地址、页号、每页的长度都是十进制数 计算页号PPA/L和页内偏移量WWA%L 比较页号P和页表长度M若P M则产生越界中断否则继续执行 页表中页号P对应的页表项地址 页表始址F 页号P * 页表项长度取出该页表项内容b即为物理块号。 注意区分页表长度和页表项长度。页表长度的值是指一共有多少页页表项长度是指页地址占多大的存储空间 计算E b * L W用得到的物理地址E去访问内存 以上地址变换由硬件自动完成页式管理只需给出一个整数就能确定对应的物理地址因为页面大小L是固定的。因此页式管理中地址空间是一维的 页表项的作用是找到该页在内存中的位置。以32位逻辑地址空间、字节编址单位、一页4KB为例地址空间一共有** 2 32 B / 4 K B 1 M 2^{32}B/4KB1M 232B/4KB1M页因此需要log1M20位才能保证表示范围能容纳所有页面又因为字节作为编址单位即页表项的大小 ⌈ 20 / 8 ⌉ 3 B \lceil 20/8 \rceil 3B ⌈20/8⌉3B**。所以在这个条件下为了保证页表项能够指向所有页面页表项的大小应该大于3B当然也可选择更大的页表项让一个页面能够正好容下整数个页表项进而方便存储如取成4B一页正好可以装下1K个页表项或增加一些其他信息 分页管理方式存在的两个主要问题 每次访存操作都需要进行逻辑地址到物理地址的转换 地址转换过程必须足够快否则访存速度会降低 每个进程引入页表用于存储映射机制 页表不能太大否则内存利用率会降低 具有快表的地址变换机构 若页表全部放在内存中则存取一个数据或一条指令至少要访问两次内存 访问页表确定所存取的数据或指令的物理地址 根据该地址存取数据、指令 这种方法比通常执行指令的速度慢了一半 为提高速度在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器–快表又称相联存储器TLB用来存放当前访问的若干页表项以加速地址变换的过程。 与此对应主存中的页表常称为慢表 具有快表的地址变换机构如下 具有快表的分页机制中地址的变换过程如下 CPU给出逻辑地址后由硬件进行地址转换将页号送入高速缓冲存储器并将此页号与快表中的所有页号进行比较若找到匹配的页号说明所要访问的页表项就在快表中则直接从中取出该页对应的页框号与页内偏移量拼接形成物理地址。这样存取数据仅一次访存便可实现若未找到匹配的页号则需要访问主存中的页表在读出页表项后应同时将其存入快表以便后面可能的再次访问。但若快表已满则必须按照一定算法对旧的页表项进行替换。 一般快表的命中率可达90%以上这样分页带来的速度损失就可降低至10%以下。快表的有效性基于局部性原理 两级页表 使用层次结构的页表将页表的10页空间也进行地址映射建立上一级页表用于存储页表的映射关系 二级页表实际上是在原有页表结构上再加上一层页表 建立多级页表的目的在于建立索引以便不用浪费主存空间去存储无用的页表项也不用盲目地顺序式查找页表项 基本分段存储管理方式 与分页的区别联系 分页管理方式从计算机角度出发目的是提高内存利用率提升计算机的性能。通过硬件机制实现对用户完全透明分段管理方式从用户、程序员角度出发满足方便编程、信息保护与共享、动态增长、动态链接等方面需求 分段 按照用户进程中的自然段划分逻辑空间 页式系统中逻辑地址的页号、页内偏移量对用户是透明的但段式系统中段号、段内偏移量必须由用户显式提供在高级程序设计语言中这个工作由编译程序完成 段表 每个进程都有一张逻辑空间与内存空间映射的段表其中每个段表项对应进程的一段段表项记录该段在内存中的始址和长度 配置段表后执行中的进程可通过查找段表找到每段所对应的内存区 即段表用于实现从逻辑段到物理内存区的映射 地址变换机构 分段系统的地址变换如下图。为了实现进程从逻辑地址到物理地址的变换功能在系统中设置了段表寄存器用于存放段表始址F和段表长度M。从逻辑地址A到物理地址E之间的地址变换如下 从逻辑地址A中取出前几位为段号S后几位为段内偏移量W 注意在段式存储管理的题目中逻辑地址一般以二进制数给出而在页式存储管理中逻辑地址一般以十进制数给出 比较段号S和段表长度M若S M则产生越界中断否则继续执行段表中段号S对应的段表项地址 段表始址F 段号S * 段表项长度取出该段表项的前几位得到段长C。若段内偏移量 C则产生越界中断否则继续执行。 段表项实际只有两部分前几位是段长后几位是始址 取出段表项中该段的始址b计算EbW用得到的物理地址E去访问内存 段的共享与保护 分段系统中段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时必须防止另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码不属于临界资源这样的代码和不能修改的数据可以共享而可修改的代码、数据不能共享 与分页管理类似分段管理的保护方法主要有两种 存取控制保护地址越界保护 将段表寄存器中的段表长度与逻辑地址中的段号比较若段号大于段表长度则产生越界中断再将段表项中的段长与逻辑地址的段内偏移进行比较若段内偏移大于段长也会产生越界中断 分页管理中的地址越界保护只需要判断页号是否越界页内偏移是不可能越界的 与页式管理不同段式管理不能通过给出一个整数便确定对应的物理地址因为每段的长度是不固定的无法通过整数除法得出段号无法通过求余得出段内偏移所以段号和段内偏移一定要显式给出因此分段管理的地址空间是二维的 段页式管理方式 页式存储管理能有效的提高内存利用率分段存储管理方式能反映程序的逻辑结构有利于段的共享。 段页式系统中作业的地址空间首先被分成若干逻辑段每段都有自己的段号然后将每段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样将其分成若干和页面大小相同的存储块对内存的分配以存储块为单位。 段页式系统中作业的逻辑地址分三部分段号、页号、页内偏移量如下 为了实现地址变换系统为每个进程建立一张段表每个分段有一张页表。段表表项中至少包括段号、页表长度、页表始址页表表项中至少包括页号、块号此外系统中还应有一个段表寄存器指出作业的段表始址、段表长度 段表寄存器和页表寄存器的作用都有两个一是在段表、页表中寻址二是判断是否越界 注意在一个进程中段表只有一个页表可能有多个 地址变换时通过段表查到页表始址通过页表找到页帧号最后形成物理地址。进行一次访问实际需要三次访问主存这里同样可以使用快表来加快查找速度关键字由段号、页号组成值是对应的页帧号、保护码 段页式管理的地址空间是二维的
虚拟内存管理
虚拟内存的基本概念
传统存储管理方式的特征 一次性 作业必须一次性全部装入内存后才能开始运行。这会导致两种情况 当作业很大而不能全部被装入内存时将使该作业无法运行当大量作业要求运行时由于内存不足以容纳所有作业只能使少数作业先运行导致多道程序度的下降 驻留性 作业被装入内存后就一直驻留在内存中其任何部分都不会被换出直至作业运行结束。运行中的进程会因等待IO而被阻塞可能处于长期等待状态 局部性原理 高速缓存是计算机科学中唯一重要的思想依赖的原理就是局部性原理表现在以下两个方面 时间局部性 某条指令、数据一旦执行或访问不久后可能再次执行或访问 产生时间局部性的典型原因是程序中存在大量的循环 空间局部性 一旦程序访问了某个存储单位不久后附近的存储单元也将被访问即程序在一段时间内访问的地址可能集中在一定的范围之内因为指令通常是顺序存放、顺序执行的数据也一般是以向量、数组、表等形式簇聚存储的 时间局部性通过将近来使用的指令、数据保存到高速缓冲存储器中。空间局部性通常使用较大的高速缓存并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上建立了内存-外存的两级存储机构利用局部性原理实现高速缓存。 虚拟存储器的定义和特征 基于局部性原理在程序装入时将程序的一部分装入内存而将其余部分留在外存就可启动程序执行。在程序执行过程中当所访问的信息不在内存时由操作系统将所需要的部分调入内存然后继续执行程序。另一方面操作系统将内存中暂时不使用的内容换出到外存上虚拟存储器有以下三个主要特征 多次性 无须在作业运行时一次性地全部装入内存而允许被分成多次调入 对换性 无须在作业运行时一直常驻内存而允许在作业的运行过程中进行换出、换入 虚拟性 从逻辑上扩充内存容量使用户所看到的内存容量远大于实际的内存容量 虚拟内存技术的实现 虚拟内存技术允许将一个作业分多次调入内存。采用连续分配时会使相当一部分内存空间都处于暂时或永久的空闲状态造成内存资源的严重浪费而且也无法从逻辑上扩大内存容量。因此虚拟内存的实现需要建立在离散分配的内存管理方式的基础上虚拟内存的实现有以下三种方式 请求分页存储管理请求分段存储管理请求段页式存储管理 一般需要的硬件支持如下 一定容量的内存、外存页表机制、段表机制作为主要的数据结构中断机构当用户程序要访问的部分尚未调入内存时则产生中断地址变换机构逻辑地址到物理地址的变换
请求分页管理方式 建立在基本分页系统基础之上为了支持虚拟存储器而增加了请求调页、页面置换功能。是目前最常用的一种实现虚拟存储器的方法 页表机制 不同于基本分页系统请求分页系统在一个作业运行之前不要求全部一次性调入内存因此在作业运行过程中必然会出现要访问的页面不在内存中的情况如何发现、处理这种情况为此在请求页表项中增加了4个字段如下 状态位P 指示该页是否已调入内存供程序访问时参考 访问字段A 用于记录本页在一段时间内被访问过的次数或记录本页最近已有多长时间未被访问供置换算法换出页面时参考 修改位M 标识该页在调入内存后是否被修改过 外存地址 用于指出该页在外存上的地址通常是物理块号供调入该页时参考
缺页中断机构 请求分页系统中每当要访问的页面不在内存时便产生一个缺页中断请求操作系统将所缺的页面调入内存。此时应将缺页的进程阻塞调页完成唤醒若内存中有空闲块则分配一个块将要调入的页装入该块并修改页表中的相应页表项若此时内存中没有空闲块则要淘汰某页若被淘汰页在内存期间被修改过则要将其写回外存缺页中断与普通中断的区别 在执行指令期间而非一条指令执行完后产生和处理中断信号属于内部中断一条指令在执行期间可能产生多次缺页中断 地址变换机构 是在分页系统地址变换机构的基础上为实现虚拟内存增加了某些功能形成的 进行地址变换时先检索快表 若找到要访问的页则修改页表项中的访问位写指令还需要重置修改位然后利用页表项中给出的物理块号和页内地址形成物理地址 若未找到该页的页表项则应到内存中去查找页表再对比页表项中的状态位P看该页是否已调入内存未调入则产生缺页中断请求从外存把该页调入内存
页面置换算法决定应该换入哪页、换出哪页 最佳OPT置换算法 选择的被淘汰页面是以后永不使用的页面或是在最长时间内不再被访问的页面以便保证获得最低的缺页率。 由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的因而该算法无法实现最长时间不被访问和以后被访问次数最小是不同的概念 可用来评价其他算法 先进先出FIFO页面置换算法 优先淘汰最早进入内存的页面即在内存中驻留时间最久的页面。该算法实现简单只需要把调入内存的页面根据先后次序链接成队列设置一个指针总指向最早的页面 该算法与进程实际运行时的规律不适应因为在进程中有的页面经常被访问 FIFO算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象由Belady发现故称Belady异常。只有FIFO算法才会出现这种异常 最近最久未使用LRU置换算法 选择最近最长时间未访问过的页面予以淘汰它认为过去一段时间内未访问过的页面在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段来记录页面自上次被访问以来所经历的时间淘汰页面时选择现有页面中值最大的予以淘汰。LRU算法的性能较好但需要寄存器、栈的硬件支持。LRU是堆栈类的算法理论上可以证明堆栈类算法不可能出现Belady异常FIFO算法基于队列实现不是堆栈类算法。 时钟CLOCK置换算法 LRU算法性能接近于OPT算法但实现起来比较困难且开销大FIFO算法实现简单但性能差。试图用比较小的开销接近LRU算法的性能这类算法都是CLOCK算法的变体因为算法要循环扫描缓冲区像时钟的指针一样转动所以称为CLOCK算法又称**最近未使用NRUNot Recently Used**算法 简单的CLOCK算法給每帧关联一个附加位称为使用位。当某页首次装入主存时将该帧的使用位设置为1当该页随后再被访问到时其使用位也被置为1。对于页替换算法用于替换的候选帧集合可视为一个循环缓冲区并有一个指针与之相关联。当某一页被替换时该指针被设置成指向缓冲区中的下一帧。当需要替换一页时操作系统扫描缓冲区以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时操作系统将该位重新置0若在这个过程开始时缓冲区中的所有帧的使用位均为0则选择遇到的第一个帧替换若所有帧的使用位均为1则指针在缓冲区中完整地循环一周把所有使用位都置为0并停留在最初的位置上替换该帧中的页。由于该算法循环检查各页面的情况因此称CLOCK算法 CLOCK算法的性能比较接近LRU算法而通过增加使用的位数目可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位则得到改进型CLOCK置换算法这样每帧都处于以下4种情况 最近未被访问也未被修改u0m0最近被访问但未被修改u1m0最近未被访问但被修改u0m1最近被访问被修改u1m1 算法执行如下操作步骤 从指针的当前位置开始扫描帧缓冲区。在这次扫描过程中对使用位不做任何修改。选择遇到的第一个帧u0m0用于替换若第一步失败则重新扫描查找u0m1的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中对每个跳过的帧把它的使用位设置成0若第二步失败则指针将回到它的最初位置且集合中所有帧的使用位均为0。重复第1步并且若有必要重复第2步以便可以找到供替换的帧 改进型CLOCK算法优于简单CLOCK算法的地方在于替换时首选没有变化的页由于修改过的页在被替换之前必须写回因而这样做会节省时间 改进型CLOCK算法与普通CLOCK算法区别 操作系统中任何经过优化的页面置换算法都有一个原则 尽可能保留曾经使用过的页面而淘汰未使用过的页面认为这样可以在总体上减少换页次数。 CLOCK算法只考虑到是否被访问过因此被访问过的当然尽可能留下未使用过的就淘汰而改进型CLOCK算法对使用过的页面又做了细分分为使用过但未修改和使用过且修改过因此若有未使用过的页面则当然首先把它换出若全部页面都使用过则当然有限把未修改过的页面换出。
页面分配策略
驻留集大小 对于分页式的虚拟内存在进程准备执行时不需要、不可能把一个进程的所有页都读入主存。因此操作系统决定读取多少页即决定给特定的进程分配几个页框。给一个进程分配的物理页框的集合就是这个进程的驻留集。需要考虑以下几点 分配给一个进程的存储量越小任何时候驻留在主存中的进程数就越多从而可以提高处理机的时间利用效率。若一个进程在竹村中的页数过少则尽管有局部性原理页错误率仍然会相对较高若页数过多则由于局部性原理给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响 现代操作系统通常采用三种策略 固定分配局部置换 为每个进程分配一定数目的物理块在整个运行期间都不改变。若进程在运行中发生缺页则只能从该进程在内存中的页面中选出一页换出然后调入需要的页面。这种策略难以确定应为每个进程分配的物理块数目 太少会频繁出现缺页中断太多会使CPU和其他资源利用率下降 可变分配全局置换 最容易实现的策略为系统中的每个进程分配一定数目的物理块操作系统自身也保持一个空闲物理块队列当某进程发生缺页时系统从空闲物理块队列中取出一个物理块分配给该进程并将欲调入的页装入其中。这种方法比固定分配局部置换更加灵活可以动态增加进程的物理块但也存在弊端 会盲目地给进程增加物理块从而导致系统多道程序的并发能力下降 可变分配局部置换 为每个进程分配一定数目的物理块当某个进程发生缺页时只允许从该进程在内存的页面中选出一页换出因此不会影响其他进程的运行。若进程在运行中频繁地缺页则系统再为该进程分配若干物理块直至该进程缺页率趋于适当程度反之若进程运行中的缺页率特别低则可适当减少分配给该进程的物理块 比起可变分配全局置换这种方法不仅可以动态地增加进程物理块地数量还能动态减少进程物理块地数量在保证进程不会过多地调页地同时也保持了系统的多道程序并发能力。 调入页面的时机 预调页策略 根据局部性原理一次调入若干相邻的页可能会比一次调入一页更高效。但若调入的一批页面中大多数都未被访问则又是低效的。因此需要采用预测为基础的预调页策略将预计在不久之后便会被访问的页面预先调入内存。 目前预调页的成功率在50%左右因此该策略主要用于进程的首次调入由程序员指定应先调入哪些页 请求调页策略 进程在运行中需要访问的页面不在内存而提出请求由系统将所需页面调入内存。由这种策略调入的页一定会被访问且这种策略比较易于实现因此在目前的虚拟存储器中多大采用此策略。 缺点时每次只调入一页调入调出页面数多时会花费过多的IO开销 预调入实际上就是运行前调入请求调页实际上就是运行期间调入。一般情况下两种策略都会用到 从何处调入页面 请求分页系统中的外存分两部分 用于存放文件的文件区 采用离散分配方式 用于存放对换页面的对换区 对换区通常采用连续分配方式因此对换区的磁盘IO速度比文件区的更快 从何处调入页面存在三种情况 系统拥有足够的对换空间 可以全部从对换区调入所需页面以提高调页速度 在进程运行前需将与该进程有关的文件从文件区复制到对换区 系统缺少足够的对换区空间 不会被修改的文件都直接从文件区调入。换出这些页面时由于它们未被修改而不必将它们换出。但对于可能被修改的部分在将它们换出时必须调到对换区以后需要时再从对换区调入 因为读的速度比写快 UNIX方式 与进程有关的文件都放在文件区因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面由于放在对换区因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存则无须再从对换区调入。
抖动
页面置换过程中刚刚换出的页面马上又要换入主存刚刚换入的页面马上又要换出主存这种频繁的页面调度行为称为抖动、颠簸 若一个进程在换页上用的时间多于执行时间则这个进程就在颠簸 频繁发生**缺页中断抖动**的主要原因 某个进程频繁访问的页面数目高于可用的物理页帧数目 虚拟内存技术可在内存中保留更多的进程以提高系统效率。在稳定状态几乎主存的所有空间都被进程块占据处理机和操作系统可以直接访问到尽可能多的进程。 如果管理不当那么处理机的大部分时间都将用于交换块即请求调入页面的操作而不是执行进程的指令因为会大大降低系统效率。
工作集
在某段时间间隔内进程要访问的页面集合。基于局部性原理可以用最近访问过的页面来确定工作集。 一般来说工作集W可由时间t和工作集窗口大小** Δ \Delta Δ**来确定 实际应用中工作集窗口会设置的很大即对于局部性好的程序工作集大小一般会比工作集窗口** Δ \Delta Δ**小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合因此若分配给进程的物理块小于工作集大小则该进程就很有可能频繁缺页所以为了防止这种抖动现象一般来说分配进程的物理块数即驻留集大小要大于工作集大小工作集模型的原理 让操作系统跟踪每个进程的工作集并为进程分配大于其工作集的物理块落在工作集内的页面需要调入驻留集中而落在工作集外的页面可以从驻留集中换出若还有空闲物理块则可以再调一个进程到内存以增加多道程序数若所有进程的工作集之和超过了可用物理块的总数则操作系统会暂停一个进程将其页面调出并将物理块分配给其他进程防止出现抖动现象
地址翻译
总结 分页管理VS分段管理 分页分段目的页是信息的物理单位分页是为实现离散分配方式以削减内存的外零头提高内存的利用率。或者说分页仅是由于系统管理的需要而不是用户的需要段是信息的逻辑单位含有一组意义相对完整的信息。分段的目的是能更好地满足用户的需求长度页的大小固定且由系统决定由系统把逻辑地址划分为页号和页内地址两部分是由机器硬件实现的因而在系统中只能有一种大小的页面段的长度不固定决定于用户所编写的程序通常由编译程序在对程序进行编译时根据信息的性质来划分地址空间作业地址空间是一维的即单一的线性地址空间程序员利用一个记忆符即可表示一个地址作业地址空间是二维的程序员在标识一个地址时需给出段名、段内地址碎片有内部碎片无外部碎片有外部碎片无内部碎片共享和动态链接不容易实现容易实现
文件管理 文件系统基础
文件的定义 以计算机硬盘为载体的存储在计算机上的信息集合。在系统运行时计算机以进程为基本单位进行资源的调度分配。而在用户进行的输入输出中则以文件为基本单位文件的结构 数据项 文件系统中最低级的数据组织形式分两种类型 基本数据项 描述一个对象的某种属性的一个值数据中可命名的最小逻辑数据单位即原子数据 组合数据项 多个基本数据项组成 记录 一组相关的数据项的集合用于描述一个对象在某方面的属性 文件 由创建者所定义的一组相关信息的集合逻辑上可分为有结构文件、无结构文件两种 有结构文件由一组相似记录组成又称纪录式文件无结构文件被视为一个字符流又称流式文件 文件的属性 名称 唯一以容易读取的形式保存 标识符 标识文件系统内文件的唯一标签通常为数字是对人不可读的一种内部名称 类型 被支持不同类型的文件系统所使用 位置 指向设备和设备上文件的指针 大小 当前大小用字节、字、块表示也可包含文件允许的最大值 保护 对文件进行保护的访问控制信息 时间、日期、用户标识文件创建、上次修改、上次访问的相关信息用于保护、跟踪文件的使用 文件的基本操作 创建文件 在文件系统中为文件找到空间在目录中为新文件创建条目该条目记录文件名称、在文件系统中的位置、其他可能的信息 写文件 执行一个系统调用指明文件名称和要写入文件的内容。对于给定文件名称系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作时便更新写指针 读文件 执行一个系统调用指明文件名称和要读入文件块的内存文职。同样需要搜索目录以找到相关目录项系统维护一个读位置的指针 一个进程通常只对一个文件读写因此当前操作位置可作为每个进程当前文件位置的指针。由于读和写都使用同一指针因此节省了空间也降低了系统复杂度 文件重定位文件寻址 按某条件搜索目录将当前文件位置设为给定值并且不会读写文件 删除文件 先从目录中找到要删除文件的目录项使之成为空项然后回收该文件所占用的存储空间 截断文件 允许所有文件的属性不变并删除文件内容即将其长度设为0并释放其空间 文件的打开与关闭 系统要求在首次使用文件时使用系统调用open将指明文件的属性包括该文件在外存上的物理位置从外存复制到内存打开文件表的一个表目中并将该表目的编号也称索引返回给用户。操作系统维护一个包含所有打开文件信息的表打开文件表open-file table。当用户需要一个文件操作时可通过该表的一个索引指定文件因此省略了搜索环节。当文件不再使用时进程可以关闭它操作系统从打开文件表删除这一条目open通常返回一个指向打开文件表中的一个条目的指针。通过使用该指针而非文件名进行所有IO操作以简化步骤并节省资源另一个进程执行open时只是在其进程打开表种增加一个条目并指向整个系统表的相应条目。系统打开文件表的每个文件时还用一个文件打开计数器Open Count以记录多少进程打开了该文件。每个关闭操作close使count递减当打开计数器为0时表示该文件不再被使用系统将回收分配给该文件的内存空间等资源。若文件被修改过则将文件写回外存并将系统打开文件表中的相应条目删除最后释放文件的文件控制块File Control BlockFCB每个打开文件都有如下关联信息 文件指针 系统跟踪上次的读写位置作为当前文件位置的指针这种指针对打开文件的某个进程来说是唯一的因此必须与磁盘文件属性分开保存 文件打开计数 文件关闭时操作系统必须重用其打开文件表条目否则表内空间会不够用。因为多个进程可能打开同一文件所以系统在删除打开文件条目之前必须等待最后一个进程关闭文件计数器跟踪打开和关闭的数量计数为0时系统关闭文件删除该条目 文件磁盘位置 绝大多数文件操作都要求系统修改文件数据。该信息保存在内存种以免为每个操作都从磁盘中读取 访问权限 每个进程打开文件都需要有一个访问模式创建、只读、读写、添加等。该信息保存在进程的打开文件表中以便操作系统能够允许或拒绝之后的IO请求
文件的逻辑结构 无结构文件 流式文件 最简单的文件组织形式将数据按顺序组织成记录并积累、保存有序相关信息项的集合以字节为单位由于无结构文件没有结构所以对记录的访问只能通过穷举搜索的方式因此这种文件形式对多数应用不适用字符流的无结构文件管理简单用户可以方便地对其进行操作对基本信息单位操作不多的文件较适于采用字符流的无结构方式 源程序、目标代码文件 有结构文件 纪录式文件 顺序文件 文件中的记录一个接一个地顺序排列记录通常是定长的可以顺序存储或以链表形式存储在访问时需要顺序搜索文件两种结构 串结构 记录之间地顺序与关键字无关通常的办法是由时间决定即按存入时间的先后排列 顺序结构 文件中的所有记录按关键字顺序排列 索引文件 对于定长记录文件要查找第i条记录可直接根据公式得到第i条记录相对于第1条记录的地址 A i i × L A_ii \times L Aii×L 对于可变长记录文件要查找第i条记录必须顺序地查找前i-1条记录从而获得相应记录的长度L再根据公式计算第i条记录的首址 A i ∑ i 0 i − 1 L i 1 A_i\sum^{i-1}_{i0} L_i1 Aii0∑i−1Li1 假定每条记录前用一个字节指明该记录的长度 变长记录文件只能顺序查找系统开销较大可以建立一张索引表加快检索索引表本身是定长记录地顺序文件 索引顺序文件 顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干组为顺序文件建立一张索引表在索引表中为每组中的第一条记录建立一个索引项其中含有该记录地关键字值和指向该记录的指针。索引文件和索引顺序文件都提高了存取地速度因为配置索引表而增加了储存空间 直接文件或散列文件 给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件、索引文件没有顺序的特性有很高的存取速度但是会引起冲突即不同关键字的散列函数值相同
目录结构
文件控制块和索引结点 文件控制块 用来存放控制文件需要的各种信息的数据结构以实现按名存取。FCB的有序集合称为文件目录一个FCB就是一个文件目录项。为了创建一个新文件系统将分配一个FCB并存放在文件目录中成为目录项 FCB包含以下信息 基本信息 文件名、物理位置、逻辑结构、物理结构等 存取控制信息 存取权限等 使用信息 建立时间、修改时间等 索引结点 在检索目录文件的过程中只用到了文件名仅当找到一个目录项查找文件名与目录项中文件名匹配时才需要从该目录项中读出该文件的物理地址。 检索目录时文件的其他描述信息不会用到也不需要调入内存因此有的系统UNIX采用了文件名和文件描述信息分开的方法文件描述信息单独形成一个称为索引结点的数据结构简称i结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成 一个FCB的大小是64B盘块的大小是1KB因此每个盘块可以存放16个FCB。FCB必须连续存放。而在UNIX系统一个目录项仅占16B其中14B是文件名2B是i结点指针。在1KB的盘块中可存放64个目录项。这样就可使查找文件时的平均启动磁盘次数减少到原来的1/4大大节省了开销。存放在磁盘上的索引结点称为磁盘索引结点UNIX中的每个文件都有一个唯一的磁盘索引结点包括以下几个方面 文件主标识符 个人或小组的标识符 文件类型 普通文件、目录文件、特别文件 文件存取权限 各类用户对该文件的存取权限 文件物理地址 每个索引结点中含有13个地址项即iaddr(0)~iaddr(12)它们以直接或间接方式给出数据文件所在盘块的编号 文件长度 以字节为单位 文件链接计数 本文件系统中所有指向该文件的文件名的指针计数 文件存取时间 本文件最近被进程存取的时间、最近被修改的时间、索引结点最近被修改的时间 文件被打开时磁盘索引结点复制到内存的索引结点中以便于使用。在内存索引结点又增加了以下内容 索引结点编号 标识内存索引结点 状态 指示i结点是否上锁或被修改 访问计数 每当有一进程要访问此i结点时计数加1访问结束减1 逻辑设备号 文件所属文件系统的逻辑设备号 链接指针 设置分别指向空闲链表和散列队列的指针 目录结构 目录层次上要执行的操作 搜索 当用户使用一个文件时需要搜索目录以找到该文件的对应目录项 创建文件 当创建一个新文件时需要在目录中增加一个目录项 删除文件 当删除一个文件时需要在目录中删除相应的目录项 显示目录 用户可以请求显示目录的内容 如目录中所有文件及属性 修改目录 某些文件属性保存在目录中因而这些属性的变化需要修改相应的目录项 操作时考虑以下几种目录结构 单极目录结构 整个文件系统中只建立一张目录表每个文件占一个目录项实现了按名存取但是查找速度慢、文件不允许重名、不便于文件共享而且对于多用户的操作系统显然是不适用的 两级目录结构 单极目录容易造成文件名称的混淆因此考虑两级方案将文件目录分成**主文件目录Master File Directory和用户文件目录User File Directory**两级主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时只需搜索该用户对应的UFD 既解决了不同用户文件的重名问题又在一定程序上保证了文件的安全 两级目录结构可以解决多用户之间的文件重名问题文件系统可以在目录上实现访问限制。但是两级目录结构缺乏灵活性不能对文件分类。 多级目录结构树形目录结构 将两级目录结构的层次关系加以推广就形成了多级目录结构即树形目录结构用户要访问某个文件时用文件的路径名标识文件文件路径名是个字符串由从根目录出发到所找文件通路上所有目录名于数据文件名用分隔符**/**链接而成。 无环图目录结构 树形目录结构能便于实现文件分类但不便于实现文件共享为此在树形目录结构的基础上增加了一些指向同一结点的有向边使整个目录成为一个有向无环图系统为每个共享节点设置一个共享计数器每当图中增加对该结点的共享链时计数器加1每当某用户提出删除该结点时计数器减1。仅当共享计数器为0时才真正删除该结点否则仅删除请求用户的共享链。无环图目录结构方便地实现了文件的共享但使得系统的管理变得更加复杂
文件共享
基于索引结点的共享方式硬链接 在树形结构的目录中当有两个或多个用户要共享一个子目录或文件时必须将共享文件或子目录链接到两个或多个用户的目录中才能方便地找到该文件在这种共享方式中诸如文件的物理地址及其他的文件属性等信息不再放在目录项中而放在索引结点中。在文件目录中只设置文件名和指向相应索引结点的指针。在索引结点中还应有一个链接计数count用于表示连接到本索引结点即文件上的用户目录项的数目。 利用符号链实现文件共享软链接 为使用户B能共享用户A的一个文件F可以由系统创建一个LINK类型的新文件也取名为F并将文件F写入用户B的目录中以实现用户B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接新文件中的路径名只被视为符号链当用户B要访问被链接的文件F且正要读LINK类新文件时操作系统根据新文件中的路径名去读该文件从而实现用户B对文件F的共享利用符号链方式实现文件共享时只有文件的拥有者才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名并不拥有指向其索引结点的指针。 这样可以避免在文件主删除一个共享文件后留下一个悬空指针的情况当文件的拥有者把一个共享文件删除后其他用户通过符号链去访问它会出现访问失败于是将符号链删除此时不会产生任何影响 当文件拥有者将其删除而在共享的其他用户使用其符号链接访问该文件之前又有人在同一路径下创建了另一个具有同样名称的文件则该符号链将仍然有效但访问的文件已经改变从而导致错误 符号链的共享方式中当其他用户读共享文件时需要根据文件路径名逐个地查找目录直至找到该文件的索引结点。因此每次访问时都可能要多次地读盘使得访问文件的开销变大并增加了启动磁盘的频率此外符号链的索引结点也要耗费一定的磁盘空间很大的优点即网络共享只需提供该文件所在机器的网络地址即该机器中的文件路径 上面两种链接方式都存在一个共同的问题即每个共享文件都有几个文件名。换言之每增加一条链接就增加一个文件名 实质上是每个用户都使用自己的路径名去访问共享文件。当我们试图去遍历整个文件系统时将会多次遍历到该共享文件 硬链接和软链接都是文件系统中的静态共享方法在文件系统中还存在着另外的共享需求即两个进程同时对同一个文件进行操作这样的共享称为动态共享硬链接就是多个指针指向同一个索引结点保证只要还有一个指针指向索引结点索引结点就不能删除软链接就是把到达共享文件的路径记录下来当要访问文件时根据路径寻找文件 硬链接查找速度要比软链接的快
文件保护
文件保护通过口令保护、加密保护、访问控制等方式实现访问类型 读写执行添加删除列表清单 访问控制 最常用的方法时根据用户身份进行控制。而实现基于身份访问的最为普通的方法是为每个文件和目录增加一个访问控制列表Access-Control ListACL以规定每个用户名及其所允许的访问类型优点是可以使用复杂的访问方法缺点是长度无法预计并且可能导致复杂的空间管理使用精简的访问列表可以解决这个问题精简的访问列表采用拥有者、组、其他三种用户类型 拥有者创建文件的用户组一组需要共享文件且具有类似访问的用户其他系统内的所有其他用户 口令和密码是另外两种访问控制方法 口令指用户在建立一个文件时提供一个口令系统为其建立FCB时附上相应口令同时告诉允许共享该文件的其他用户。用户请求访问时必须提供相应的口令 优点是时间和空间的开销不多缺点是口令直接存在系统内部不够安全 密码指用户对文件进行加密文件被访问时需要使用密钥 优点是保密性强节省了存储空间缺点是编码和译码要花费一定的时间
文件系统实现
文件系统层次结构 用户调用接口 由若干程序模块组成每个模块对应一条系统调用用户发出系统调用时控制即转入相应的模块 文件目录系统 主要功能是管理文件目录任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块 存取控制验证模块 实现文件保护主要由该级软件完成它把用户的访问要求与FCB中指示的访问控制权限进行比较以确认访问的合法性 逻辑文件系统与文件信息缓冲区 根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号 物理文件系统 把逻辑记录所在的相对块号转换成实际的物理地址 辅助分配模块 管理辅助空间负责分配辅存空闲空间和回收辅存空间 设备管理程序模块 分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。
目录实现
线性列表 最简单的实现方法是使用存储文件名、数据块指针的线性表。 创建新文件时必须首先搜索目录表以确定没有同名的文件存在然后在目录表后增加一个目录项删除文件则根据给定的文件名搜索目录表接着释放分配给它的空间 重用目录项有许多方法 可以将目录项标记为不再使用或将它加到空闲目录表上还可以将目录表中的最后一个目录项复制到空闲位置并降低目录表长度 采用链表结构可以减少删除文件的时间其优点在于实现简单不过由于线性表的特殊性比较费时 哈希表 优点是查找非常迅速插入和删除也比较简单不过需要一些预备措施来避免冲突。最大的困难是哈希表长度固定以及哈希函数对表长的依赖性目录查询是通过在磁盘上反复搜索完成的需要不断地进行I/O操作开销较大。所以如前所述为了减少I/O操作把当前使用的文件目录复制到内存以后要使用该文件时只需在内存中操作因此降低了磁盘操作次数提高了系统速度。
文件实现–文件分配方式 连续分配 要求每个文件在磁盘上占有一组连续的块如下图磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小 支持顺序访问、直接访问优点是实现简单、存取速度快 缺点是文件长度不宜动态增加因为一个文件末尾后地盘块可能已分配给其他文件一旦需要增加就需要大量移动盘块。此外反复增删文件后会产生外部碎片与内存管理分配方式中的碎片相似且很难确定一个文件需要的空间大小因而只适用于长度固定的文件。 链接分配 采取离散分配的方式消除了外部碎片因此显著提高了磁盘空间的利用率又因为根据文件的当前需求为其分配必须的盘块当文件动态增长时可以动态地再为它分配盘块 分为隐式链接、显式链接两种形式 隐式链接 每个文件对应一个磁盘块的链表 磁盘块分布在磁盘的任何地方除最后一个盘块外每个盘块都有指向下一个盘块的指针这些指针对用户是透明的 目录包括文件第一块的指针和最后一块指针 创建新文件时目录中增加一个新条目。每个目录项都有一个指向文件首块的指针。该指针初始化为NULL以表示空文件大小字段为0。写文件会通过空闲空间管理系统找到空闲块将该块链接到文件的尾部以便写入。读文件则通过块到块的指针顺序读块 缺点是无法直接访问盘块只能通过指针顺序访问文件且盘块指针会消耗一定的存储空间。隐式链接分配的稳定性也是一个问题系统在运行过程中由于软件、硬件错误导致链表中的指针丢失、损坏会导致文件数据的丢失 显式链接 把用于链接文件各物理块的指针从每个物理块的块末尾中提取出来显式地存放在内存的一张链接表中。该表在整个磁盘中进设置一张称为文件分配表File Allocation TableFAT。 每个表项中存放对应快的下一块链接指针即下一个盘块号。文件的第一个盘块号记录在目录中后续的盘块可通过查FAT找到 不难看出FAT的表项与全部磁盘块一一对应并且可以用特殊数字表示 -1表示文件的最后一块-2表示这个磁盘块是空闲的也可**-3、-4** FAT不仅记录了文件各块之间的先后链接关系同时还标记了空闲的磁盘块操作系统也可以通过FAT对文件存储空间进行管理。当某进程请求操作系统分配一个磁盘块时操作系统只需从FAT中找到**-2**的表项并将对应的磁盘块分配给进程即可 FAT表在系统启动时就会被读入内存因此查找FAT的过程是在内存中进行的因此不仅显著地提高了检索速度而且明显减少了访问磁盘的次数 索引分配 解决了连续分配的外部碎片和文件大小管理的问题。但是链接分配不能有效支持直接访问FAT除外。索引分配解决了这个问题它把每个文件的所有的盘块号都集中放在一起构成索引块表 每个文件都有其索引块这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第i个块。目录条目包括索引块的地址。要读第i块通过索引块的第i个条目的指针来查找、读入所需的块 创建文件时索引块的所有指针都设为空 首次写入第i块时先从空闲空间中取得一个块再将其地址写到索引块的第i个条目 索引分配支持直接访问且没有外部碎片问题 缺点是由于索引块的分配增加了系统存储空间的开销。索引块的大小是一个重要的问题每个文件必须有一个索引块因此索引块应尽可能小但索引块太小就无法支持大文件。可以采用如下机制解决 链接方案 一个索引块通常为一个磁盘块因此它本身能直接读写。为了处理大文件可以将多个索引块链接起来 多层索引 使第一层索引块指向第二层的索引块第二层索引块再指向文件块。 根据最大文件大小的要求可以继续到第三层、第四层 混合索引 将多种索引分配方式相结合的分配方式 例如系统既采用直接地址又采用单极索引分配方式、两级索引分配方式 三种分配方式比较 访问第n条记录优点缺点连续分配需访问磁盘1次顺序存取时速度快文件定长时可根据文件起始地址及记录长度进行随机访问文件存储要求连续的存储空间会产生碎片不利于文件的动态扩充链接分配需访问磁盘n次可解决外存的碎片问题提高外存空间的利用率动态增长较方便只能按照文件的指针链顺序访问查找效率低指针信息存放消耗外存空间索引分配m级需访问磁盘m1次可以随机访问文件易于增删索引表增加存储空间的开销索引表的查找策略对文件系统效率影响较大 访问文件需要两次访问外存首先要读取索引块的内容然后访问具体的磁盘块因而降低了文件的存取速度。为了解决这一问题通常将文件的索引块读取内存的缓冲区中以加快文件的访问速度。
文件实现–文件存储空间管理 文件存储器空间的划分与初始化 一般来说一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分也可以是整个物理盘 在一个文件卷中文件数据信息的空间文件区和存放文件控制信息FCB的空间目录区是分离的 文件存储器空间管理 文件存储设备分成许多大小相同的物理块并以块为单位交换信息因此文件存储设备的管理实质上是对空闲块的组织和管理它包括空闲块的组织、分配与回收等问题 空闲表法 连续分配方式与内存的动态分配方式类似为每个文件分配一块连续的存储空间。 系统为外存上的所有空闲区建立一张空闲盘块表每个空闲区对应于一个空闲表项其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列如下 空闲盘区的分配与内存的动态分配类似同样采用首次适应算法、循环首次适应算法等。 系统在对用户所释放的存储空间进行回收时也采取类似于内存回收的方法即要考虑回收区是否与空闲表中插入点的前区和后区相邻接对相邻接者应予以合并 空闲链表法 将所有空闲盘区拉成一条空闲链根据构成链所用的基本元素不同可把链表分成两种形式 空闲盘块链 将磁盘上所有空闲空间以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时系统从链首开始依次摘下适当数目的空闲盘块分配给用户当用户因删除文件而释放存储空间时系统将回收的盘块依次插入空闲盘块链的末尾优点是分配和回收一个盘块的过程非常简单但在为一个文件分配盘块时可能要重复多次操作 空闲盘区链 将磁盘上所有空闲盘区每个盘区可包含若干盘块拉成一条链在每个盘区上除含有用于指示下一个空闲盘区的指针外还应有能指明本盘区大小盘块数的信息分配盘区的方法与内存的动态分区分配类似通常采用首次适应算法回收盘区时同样也要将回收区与相邻接的空闲盘区合并 位示图法 利用二进制的一位来表示磁盘中的一个盘块的使用情况磁盘上所有的盘块都有一个二进制与之对应 值为0表示对应的盘块空闲值为1表示对应的盘块已分配 盘块的分配 顺序扫描位示图从中找出一个或一组其值为0的二进制位 将找到的一个或一组二进制位转换成与之对应的盘块号 若找到的其值为0的二进制位位于位示图的第i行、第j列则其相应的盘块号应按下式计算n代表每行的位数 b n ( i − 1 ) j bn(i-1)j bn(i−1)j 修改位示图令map[i,j] 1 盘块的回收 将回收盘块的盘块号转换成位示图中的行号和列号转换公式为 i ( b − 1 ) D I V n 1 j ( b − 1 ) M O D n 1 \rm i(b-1) \ DIV \ n1 \newline \rm j(b-1) \ MOD \ n1 i(b−1) DIV n1j(b−1) MOD n1 修改位示图令map[i,j] 0 成组链接法 空闲表法、空闲链表法不适用于大型文件系统因为这会使空闲表或空闲链表太大 UNIX系统采用的是成组链接法 结合了空闲表法、空闲链表法两种方法克服了表太大的缺点 大致思想是把顺序的n个空闲扇区地址保存在第一个空闲扇区内其后一个空闲扇区内则保存另一个顺序空闲扇区的地址如此继续直至所有空闲扇区均予以链接。系统只需要保存一个指向第一个空闲扇区的指针。假设磁盘最初全为空闲扇区其成组链接如下 表示文件存储器空闲空间的位向量表或第一个成组链块以及卷中的目录区、文件区划分信息都需要存放在辅存储器中一般放在卷头位置在UNIX系统中称为超级块。在对卷中的文件进行操作前超级块需要预先读入系统空闲的主存并且经常保持主存超级块与辅存卷中的超级块的一致性
磁盘组织与管理
磁盘的结构 磁盘是由表面涂有磁性物质的金属或塑料构成的圆形盘片通过一个称为磁头的导体线圈从磁盘存取数据。在读写操作期间磁头固定磁盘在下面高速旋转。如下 磁盘盘面上的数据存储在一组同心圆中称为磁道。每个磁道与磁头一样宽一个盘面有上千个磁道磁道又划分为几百个扇区每个扇区固定存储大小通常为512B一个扇区称为一个盘块。相邻磁道及相邻扇区间通过一定的间隙分隔开以避免精度错误。注意由于扇区按固定圆心角度划分所以密度从最外道向里道增加磁盘的存储能力受限于最内道的最大记录密度。 扇区是磁盘可寻址的最小存储单位磁盘地址用**柱面号·盘面号·扇区号或块号**表示 磁盘按不同的方式可分为若干类型 固定头磁盘 磁头相对于盘片的径向方向固定每个磁道一个磁头 活动头磁盘 磁头可移动的磁头臂可来回伸缩定位磁道 固定盘磁盘 磁盘永久固定在磁盘驱动器内 可换盘磁盘 可移动和替换的
磁盘调度算法 一次磁盘读写操作的时间由寻找时间寻道时间、旋转延迟时间、传输时间决定 寻找时间 T s T_s Ts 活动头磁盘在读写信息前将磁头移动到指定磁道所需要的时间。这个时间除跨越n条磁道的时间外还包括启动磁臂的时间s即 T s m × n s T_sm \times n s Tsm×ns m是与磁盘驱动器速度有关的常数约为0.2ms磁臂的启动时间s约为2ms 旋转延迟时间 T r T_r Tr 磁头定位到某一磁道的扇区所需要的时间设磁盘的旋转速度为r则 T r 1 2 r T_r\frac{1}{2r} Tr2r1 对于硬盘典型的旋转速度为5400转/分相当于一周11.1ms则** T r T_r Tr**为5.55ms对于软盘其旋转速度为300600转/分则**$T_r$**为50100ms 传输时间 T t T_t Tt 从磁盘读出或向磁盘写入数据所经历的时间这个时间取决于每次所读/写的字节数b和磁盘的旋转速度 T t b r N T_t \frac{b}{rN} TtrNb r为磁盘每秒的转数N为一个磁道上的字节数 总平均存取时间 T a T_a Ta T a T s 1 2 r b r N T_aT_s \frac{1}{2r} \frac{b}{rN} TaTs2r1rNb 目前常用的磁盘调度算法 先来先服务 First Come First Served FCFS 根据进程请求访问磁盘的先后顺序进行调度是最简单的算法 优点是具有公平性。若只有少量进程需要访问且大部分请求都是访问簇聚的文件扇区则有望达到较好的性能 若有大量进程竞争使用磁盘则这种算法在性能上往往接近于随机调度所以实际磁盘调度中会考虑一些更复杂的算法 最短寻找时间优先 Shortest Seek Time First SSTF 选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道以便使每次的寻找时间最短。当然总是选择最小寻找时间并不能保证平均寻找时间最小但能提供比FCFS算法更好的性能 这种算法会产生饥饿现象即远离磁头的磁道访问被无限期延迟 扫描 SCAN电梯调度算法 在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象实际上就是在最短寻找时间优先算法的基础上规定了磁头运动的方向 这种算法对最近扫描过的区域不公平因此它在访问局部性方面不如FCFS、SSTF算法好 循环扫描Circular SCANC-SCAN 在扫描算法的基础上规定磁头单向移动来提供服务回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求所以使用改进型的C-SCAN算法来避免这个问题 采用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端显然在实际使用时还可以改进即磁头移动只需要达到最远端的一个请求即可返回不需要到达磁盘端点。这种形式的SCAN算法和C-SCAN算法称为LOOK调度和C-LOOK调度因为它们在朝一个给定方向移动前会查看是否有请求 几种磁盘调度算法的对比 FCFS算法太过简单性能较差仅在请求队列长度接近于1时才较为理想SSTF算法较为通用和自然SCAN、C-SCAN算法在磁盘负载较大时比较占优势 优点缺点FCFS公平、简单平均寻道距离大仅应用在磁盘IO较少的场合SSTF性能比FCFS好不能保证平均寻道时间最短可能出现饥饿现象SCAN寻道性能较好可避免饥饿现象不利于远离磁头一端的访问请求C-SCAN消除了对两端磁道请求的不公平- 除减少寻找时间外, 减少延迟时间也是提高磁盘传输效率的重要因素.可以对盘面扇区进行交替编号, 对磁盘片组中的不同盘面错位命名 磁盘寻块时间分为三部分,即寻道时间, 延迟时间, 传输时间, 寻道时间, 延迟时间属于找的时间, 凡是找的时间都可以通过一定的方法削减, 但传输时间是磁盘本身性能所决定的, 不能通过一定的措施减少
磁盘的管理
磁盘初始化 一个新的磁盘只是一个含有磁性记录材料的空白盘. 在磁盘能存储数据之前, 它必须分成扇区以便磁盘控制器能进行读写操作, 这个过程称为低级格式化(物理分区). 低级格式化为磁盘的每个扇区采用特别的数据结构. 每个扇区的数据结构通常由头, 数据区域(通常为512B大小)和尾部组成. 头部和尾部包含了一些磁盘控制器所使用的信息为了使用磁盘存储文件, 操作系统还需要将自己的数据结构记录在磁盘上 将磁盘分为一个或多个柱面组成的分区对物理分区进行逻辑格式化(创建文件系统), 操作系统将初始的文件系统数据结构存储到磁盘上, 这些数据结构包括空闲和已分配的空间及一个初始为空的目录 引导块 计算机启动需要运行一个初始化程序(自举程序), 它初始化CPU, 寄存器, 设备控制器, 内存 等, 接着启动操作系统. 该自举程序应找到磁盘上的操作系统内核, 装入内存, 并转到起始地址, 从而开始操作系统的运行自举程序通常保存在ROM中, 为了避免改变自举代码而需要改变ROM硬件的问题, 因此只在ROM中保留很小的自举装入程序, 将完整功能的自举程序保存在磁盘的启动块上, 启动快位于磁盘的固定位, 拥有启动分区的磁盘称为启动磁盘, 系统磁盘 坏块 由于磁盘有移动部件, 且容错能力弱, 因此容易导致一个或多个扇区损坏. 部分磁盘甚至从出厂时就有坏扇区. 根据所使用的磁盘和控制器, 对这些块有多种处理方式 对于简单磁盘, 坏扇区可手工处理, 执行逻辑格式化时会扫描磁盘以检查坏扇区. 坏扇区会在FAT表上标明, 因此程序不会使用对于复杂磁盘, 其控制器维护一个磁盘坏块链表, 该链表在出厂前进行低级格式化时就已经初始化, 并在磁盘的整个使用过程中不断更新. 低级格式化将一些块保留作为备用, 对操作系统透明. 控制器可用备用块来逻辑地替代坏块, 这种方案称为扇区备用 对坏块的处理实质上就是用某种机制, 使系统不去使用坏块. 坏块属于硬件故障, 操作系统是不能修复坏块的
输入/输出管理
I/O管理概述
I/O设备
按使用特性可分为以下类型 人机交互类外部设备 用于与计算机用户之间交互的设备, 数据交换速度相对较慢, 通常是以字节为单位进行数据交换的 如打印机, 显示器, 鼠标, 键盘等 存储设备 存储程序和数据的设备, 用于数据交换, 速度较快, 通常以多字节组成的块为单位进行数据交换 如磁盘, 磁带, 光盘等 网络通信设备 用于与远程设备通信的设备, 速度介于前两类设备之间. 网络通信设备在使用和管理上与前两类设备也有很大不同 如各种网络接口, 调制解调器 按传输速率分类 低速设备 传输速率仅为每秒几字节到数百字节的一类设备, 如键盘, 鼠标 中速设备 传输速率为每秒数千字节至数万字节的一类设备 如行式打印机, 激光打印机 高速设备 传输速率在数百千字节至千兆字节的一类设备 如磁带机, 磁盘机, 光盘机等 按信息交换的单位分类 块设备 由于信息的存取总是以数据块为单位的, 所以存储信息的设备称为块设备, 它属于有结构设备 如磁盘 字符设备 用于数据输入/输出的设备为字符设备, 因为其传输的基本单位是字符, 属于无结构类型, 基本特征是传输速率低, 不可寻址, 并且在输入/输出时常采用中断驱动方式 如 交互式终端机, 打印机
I/O控制方式 程序直接控制方式 计算机从外部设备读取数据到存储器, 每次读一个字的数据. 对读入的每个字, CPU需要对外设状态进行循环检查, 知道确定该字已经在I/O控制器的数据寄存器中此方式中, 由于CPU的高速性和I/O设备的低速性, 致使CPU的绝大部分时间都处于等待I/O设备完成数据I/O的循环测试中, 造成了CPU资源的极大浪费. 在该方式中, CPU之所以要不断地测试I/O设备的状态, 就是因为在CPU中未采用中断机构, 使I/O设备无法向CPU报告它已经完成了一个字符的输入操作此方式优点是简单, 且易于实现. 缺点是CPU和I/O设备只能串行工作, 导致CPU的利用率相当低 中断驱动方式 思想是, 允许I/O设备主动打断CPU的运行并请求服务, 从而解放CPU, 使得其向I/O控制器发送读命令后, 可以继续做其他有用的工作. I/O控制器的角度 I/O控制器从CPU接受一个读命令, 然后从外围设备读数据, 一旦数据读入该I/O控制器的数据寄存器, 便通过控制线给CPU发出一个中断信号, 表示数据已准备好, 然后等待CPU请求该数据. I/O控制器收到CPU发出的取数据请求后, 将数据放到数据总线上, 传到CPU的寄存器中. 至此, 本次I/O操作完成, I/O控制器又可以开始下一次I/O操作 CPU的角度 CPU发出读命令, 然后保存当前运行程序的上下文(现场, 包括程序计数器, 处理机寄存器), 转去执行其他程序. 在每个指令周期的末尾, CPU检查中断. 当有来自I/O控制器的中断时, CPU保存当前正在运行程序的上下文, 转去执行中断处理程序以处理该中断, 这时, CPU从I/O控制器读一个字的数据传送到寄存器, 并存入主存. 接着, CPU恢复发出I/O命令的程序(或其他程序)的上下文, 然后继续运行. 该方式比程序直接控制方式有效, 但由于数据中的每个字在存储器与I/O控制器之间的传输都必须经过CPU, 这就导致了中断驱动方式仍然会消耗较多的CPU时间 DMA方式 中断驱动方式中, I/O设备与内存之间的数据交换必须要经过CPU中的寄存器, 所以速度还是受限, 而DMA(直接存储器存取)方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路, 彻底解放CPU 特点如下 基本单位是数据块所传送的数据, 是从设备直接送入内存的, 或者相反仅在传送一个或多个数据块的开始和结束时, 才需CPU干预, 整块数据的传送是在DMA控制器的控制下完成的 要在主机与控制器之间实现成块数据的直接交换, 须在DMA控制器中设置4类寄存器 命令/状态寄存器(CR) 用于接收从CPU发来的I/O命令或有关控制信息, 或设备的状态 内存地址寄存器(MAR) 输入时, 它存放把数据从设备传送到内存的起始目标地址输出时, 它存放由内存到设备的内存源地址 数据寄存器(DR) 用于暂存从设备到内存或从内存到设备的数据 数据计数器(DC) 存放本次要传送的字节数 DMA方式的工作过程是 CPU接收到I/O设备的DMA请求时, 它给I/O控制器发出一条命令, 启动DMA控制器, 然后继续其他工作.CPU就把控制操作委托给DMA控制器, 由该控制器负责处理. DMA控制器直接与存储器交互, 传送整个数据块, 每次传送一个字, 这个过程不需要CPU参与传送完成后, DMA控制器发送一个中断信号给处理器, 因此只有在传送开始和结束时才需要CPU的参与 DMA控制方式与中断驱动方式的主要区别是 中断驱动方式在每个数据需要传输时中断CPU, 而DMA控制方式则是在所要求传送的一批数据全部传送结束时, 才中断CPU中断驱动方式数据传送是在中断处理时由CPU控制完成的, 而DMA控制方式则是在DMA控制器的控制下完成的 通道控制方式 I/O通道时指专门负责输入/输出的处理机, I/O通道方式是DMA方式的发展, 它可以进一步减少CPU的干预, 即把对一个数据块的读(或写)为单位的干预, 减少为对一组数据块的读(或写)及有关控制和管理为单位的干预. 同时, 又可以实现CPU, 通道, I/O设备三者的并行操作, 从而更有效地提高整个系统地资源利用率I/O通道与一般处理机的区别是: 通道指令的类型单一, 没有自己的内存, 通道所执行的通道程序是放在主机的内存中的, 也就是说通道与CPU共享内存I/O通道与DMA方式的区别是: DMA方式需要CPU来控制传输的数据块大小, 传输的内存位置, 而通道方式中这些信息是由通道控制的. 另外, 每个DMA控制器对应一台设备与内存传递数据, 而一个通道可以控制多台设备与内存的数据交换
I/O子系统的层次结构 整个I/O系统可以视为具有4个层次的系统结构, 各层次及其功能如下 用户层I/O软件 实现与用户交互的接口, 用户可直接调用在用户层提供的, 与I/O操作有关的库函数, 对设备进行操作一般而言, 大部分的I/O软件都在操作系统内部, 但仍有一小部分在用户层, 包括与用户程序链接在一起的库函数, 以及完全运行于内核之外的一些程序. 用户层软件必须通过一组系统调用来获取操作系统服务 设备独立性软件 用于实现用户程序与设备驱动器的 统一接口, 设备命令, 设备保护, 设备分配与释放 等, 同时为设备管理和数据传送提供必要的存储空间设备独立性也称设备无关性, 是的应用程序独立于具体使用的物理设备, 为实现设备独立性而引入了逻辑设备, 物理设备两个概念, 在应用程序中, 使用逻辑设备名来请求使用某类设备, 而在系统实际执行时, 必须将逻辑设备名映射成物理设备名使用 使用逻辑设备名的好处 增加设备分配的灵活性易于实现I/O重定向 I/O重定向, 指用于I/O操作的设备可以更换, (即重定向), 而不必改变应用程序 为了实现设备独立性, 必须再在驱动程序之上设置一层设备独立性软件, 总体而言, 设备独立性软件的主要功能可分为两个方面 执行所有设备的公有操作 对设备的分配, 回收将逻辑设备名映射为物理设备名对设备进行保护, 禁止用户直接访问设备缓冲管理差错控制提供独立于设备的大小统一的逻辑块, 屏蔽设备之间信息交换单位大小和传输速率的差异 向用户层(或文件层)提供统一接口 无论何种设备, 它们向用户所提供的接口应是相同的. 设备驱动程序 与硬件直接相关, 负责具体实现系统对设备发出的操作指令, 驱动I/O设备工作的驱动程序通常, 每类设备配置一个设备驱动程序, 它是I/O进程与设备控制器之间的通信程序, 常以进程形式存在, 设备驱动程序向上层用户程序提供一组标准接口, 设备具体的差别被设备驱动程序所封装, 用于接收上层软件发来的抽象I/O要求, 转换为具体要求后, 发送给设备控制器, 控制I/O设备工作; 它也将由设备控制器发来的信号传送给上层软件, 从而为I/O内核子系统隐藏设备控制器之间的差异 中断处理程序 用于保存被中断进程的CPU环境, 转入相应的中断处理程序进行处理, 处理完并恢复被中断进程的现场后, 返回到被中断进程中断处理层的主要任务 进行进程上下文的切换, 对处理中断信号源进行测试, 读取设备状态和修改进程状态等由于中断处理与硬件紧密相关, 对用户而言, 应尽量加以屏蔽, 因此应放在操作系统的底层, 系统的其余部分尽可能少地与之发生联系 硬件设备 I/O设备通常包括一个机械部件和一个电子部件, 为了达到设计的模块性和通用性, 一般将其分开 电子部件称为设备控制器(或适配器), 在个人计算机中, 通常是一块插入主板扩充槽地印制电路板机械部件则是设备本身 设备控制器通过寄存器与CPU通信, 在某些计算机上, 这些寄存器占用内存地址的一部分, 称为内存映像I/O, 另一些计算机则采用I/O专用地址, 寄存器独立编址. 操作系统通过向控制器寄存器写命令字来执行I/O功能. 控制器收到一条命令后, CPU可以转向进行其他工作, 而让设备控制器自行完成具体的I/O操作, 当命令执行完毕后, 控制器发出一个中断信号, 操作系统重新获得CPU的控制权并检查执行结果, 此时, CPU仍旧从控制器寄存器中读取信息来获得执行结果和设备的状态信息 设备控制器的主要功能如下 接收和识别CPU或通道发来的命令 如磁盘控制器能接收读, 写, 查找等命令 实现数据交换, 包括设备和控制器之间的数据传输; 通过数据总线或通道, 控制器和主存之间的数据传输 发现和记录设备及自身的状态信息, 供CPU处理使用 设备地址识别 为了实现上述功能, 设备控制器必须包含以下组成部分 设备控制器与CPU的接口 三类信号线, 数据线, 地址线, 控制线, 数据线通常与两类寄存器相连 数据寄存器 存放从设备送来的输入数据或从CPU送来的输出数据 控制/状态寄存器 存放从CPU送来的控制信息或设备的状态信息 设备控制器与设备的接口 设备控制器连接设备需要相应数量的接口, 一个接口连接一台设备. 每个接口中都存在数据, 控制, 状态三种类型的信号 I/O控制逻辑 用于实现对设备的控制, 通过一组控制线与CPU交互, 对从CPU收到的I/O命令进行译码, CPU启动设备时, 将启动命令发送给控制器, 同时通过地址线把地址发送给控制器, 由控制器的I/O逻辑对地址进行译码, 并相应地对所选设备进行控制
I/O核心子系统
I/O调度概念
操作系统开发人员通过为每个设备维护一个请求队列来实现调度, 当一个应用程序执行阻塞I/O系统调用时, 该请求就加到相应设备的队列上, I/O调度会重新安排队列顺序, 以改善系统总体效率和应用程序的平均响应时间I/O子系统还可使用主存或磁盘上的存储空间的技术来改善计算机效率 如缓冲, 高速缓存, 假脱机
高速缓存与缓冲区 磁盘高速缓存 (Disk Cache) 正在运行的进程的指令, 既存储在磁盘上, 又存储在物理内存, CPU的二级和一级高速缓存中磁盘高速缓存技术不同于通常意义下的介于CPU与内存之间的小容量高速存储器, 而是指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息. 因此, 磁盘高速缓存逻辑上属于磁盘, 物理上则是驻留在内存中的盘块高速缓存在内存中分为两种形式 在内存中开辟一个单独的存储空间作为磁盘高速缓存, 大小固定把未利用的内存空间作为一个缓冲池, 供请求分页系统和磁盘I/O时共享 缓冲区 (Buffer) 目的 缓和CPU与I/O设备间速度不匹配的矛盾减少对CPU的中断频率, 放宽对CPU中断响应时间的限制解决基本数据单元大小(数据粒度)不匹配的问题提高CPU和I/O设备之间的并行性 实现方法如下 采用硬件缓冲器, 但由于成本太高, 除一些关键部位外, 一般不采用硬件缓冲器采用缓冲区, (位于内存区域) 缓冲区有一个特点 即当缓冲区的数据非空时, 不能往缓冲区冲入数据, 只能从缓冲区把数据传出当缓冲区为空时, 可以往缓冲区冲入数据, 但必须把缓冲区充满后, 才能从缓冲区把数据传出 根据系统设置缓冲器的个数, 缓冲技术可以分为如下几种 单缓冲 在设备和处理机之间设置一个缓冲区, 设备和处理机交换数据时, 先把被交换数据写入缓冲区, 然后需要数据的设备或处理机从缓冲区取走数据 记从磁盘把一块数据输入缓冲区的时间为T, 操作系统将该缓冲区中的数据传送到用户区的时间为M, 而CPU对这一块数据处理的时间为C, 则单缓冲区处理每块数据的用时为 m a x ( C , T ) M max(C,T)M max(C,T)M 双缓冲 根据单缓冲的特点, CPU在传送时间M内处于空闲状态, 由此引入双缓冲. I/O设备输入数据时先装填到缓冲区1, 在缓冲区1填满后才开始装填缓冲区2, 与此同时处理机可以从缓冲区1中取出数据放入用户进程处理, 当缓冲区1中的数据处理完后, 若缓冲区2已填满, 则处理机又从缓冲区2中取出数据放入用户进程处理, 而I/O设备又可以装填缓冲区1. 注意, 必须等缓冲区2充满才能让处理机从缓冲区2取出数据. 双缓冲机制提高了处理机和输入设备的并行操作的程序 双缓冲区处理一块数据的用时为 m a x ( C M , T ) max(CM, T) max(CM,T) 循环缓冲 包含多个大小相等的缓冲区, 每个缓冲区中有一个链接指针指向下一个缓冲区, 最后一个缓冲区指针指向第一个缓冲区, 多个缓冲区构成一个环形循环缓冲用于输入/输出时, 还需要有两个指针in, out, 对输入而言, 首先要从设备接收数据到缓冲区中, in指针指向可以输入数据的第一个空缓冲区. 当运行进程需要数据时, 从循环缓冲区中取一个装满数据的缓冲区, 并从此缓冲区中提取数据, out指针指向可以提取数据的第一个满缓冲区, 输出则正好相反 缓冲池 由多个系统公用的缓冲区组成, 缓冲区按其使用状况可以形成三个队列, 空缓冲队列, 装满输入数据的缓冲队列(输入队列), 装满输出数据的缓冲队列(输出队列). 还应具有4种缓冲区 用于收容输入数据的工作缓冲区用于提取输入数据的工作缓冲区用于收容输出数据的工作缓冲区用于提取输出数据的工作缓冲区 当输入进程需要输入数据时, 便从空缓冲队列的队首摘下一个空缓冲区, 把它作为收容输入工作缓冲区, 然后把输入数据输入其中, 装满后再将它挂到输入队列队尾. 当计算进程需要输入数据时, 便从输入队列取得一个缓冲区作为提取输入工作缓冲区, 计算进程从中提取数据, 数据用完后再将它挂到空缓冲队列尾. 当计算进程需要输出数据时, 便从空缓冲队列的队首取得一个空缓冲区, 作为收容输出工作缓冲区, 当其中装满输出数据后, 再将它挂到输出队列队尾. 当要输出时, 由输出进程从输出队列中取得一个装满输出数据的缓冲区, 作为提取输出工作缓冲区, 当数据提取完后, 再将它挂到空缓冲队列的队尾. 高速缓存与缓冲区的对比 高速缓存缓冲区相同点介于高速设备和低速设备之间同左存放数据区别存放的是低速设备上的某些数据的复制数据, 即高速缓存上有的, 低速设备上面必然有存放的是低速设备传递给高速设备的数据(或相反), 而这些数据在低速设备(或高速设备)上却不一定有备份, 这些数据再从缓冲区传送到高速设备(或低速设备)目的区别高速缓存存放的是高速设备经常要访问的数据, 若高速设备要访问的数据不在高速缓存中, 则高速设备就需要访问低速设备高速设备和低速设备的通信要经过缓冲区, 高速设备永远不会直接去访问低速设备
设备分配与回收 设备分配概述 指根据用户的I/O请求分配所需的设备, 分配的总原则是充分发挥设备的使用效率, 尽可能地让设备忙碌, 又要避免由于不合理的分配方法造成进程死锁. 从设备的特性来看, 采用下述三种使用方式的设备分别称为独占设备, 共享设备, 虚拟设备 独占式使用设备 指在申请设备时, 若设备空闲, 则将其独占, 不再允许其他进程申请使用, 一直等到该设备被释放才允许其他进程申请使用 如打印机 分时式共享使用设备 独占式使用设备时, 设备利用率很低, 当设备没有独占使用的要求时, 可以通过分时共享使用提高利用率 如对磁盘设备的I/O操作 以SPOOLing方式使用外部设备 (Simultaneous Peripheral Operation On-Line, 假脱机) 在批处理操作系统时代引入, 用于对设备的操作, 实质上就是对I/O操作进行批处理该技术实质上是一种以空间换时间的技术, 而请求分页系统中的页面调度算法就刚好相反, 是以时间换空间的技术 设备分配的数据结构 设备控制表 DCT 一个设备控制表就表征一个设备, 而这个控制表中的表项就是设备的各个属性 控制器控制表 COCT 和 通道控制表 CHCT 4种I/O控制方式中, 通道方式明显要比其他几种方式更加优越, 因此现代操作系统的I/O控制采用的都是通道控制. 设备控制器控制设备与内存交换数据, 而设备控制器又需要请求通道为它服务, 因此每个COCT必定有一个表项存放指向**相应通道控制表(CHCT)**的指针, 而一个通道可为多个设备控制器服务, 因此CHCT中必定有一个指针, 指向一个表, 这个表上的信息表达的是CHCT提供服务的那几个设备控制器, CHCT与COCT的关系是一对多的关系 系统设备表 SDT 整个系统只有一张SDT, 它记录已连接到系统中的所有物理设备的情况, 每个物理设备占一个表目 由于在多道程序系统中, 进程数多于资源数, 会引起资源的竞争, 因此要有一套合理的分配原则, 主要考虑的因素有 I/O设备的固有属性I/O设备的分配算法I/O设备分配的安全性I/O设备的独立性 设备分配的策略 设备分配原则 应根据设备特性, 用户要求, 系统配置情况, 分配的总原则是, 既要充分发挥设备的使用率, 又要避免造成进程死锁, 还要将用户程序和具体设备隔离开 设备分配方式 静态分配 主要用于对独占设备的分配, 它在用户作业开始执行前, 由系统一次性分配该作业所要求的全部设备, 控制器(如通道等). 一旦分配, 这些设备, 控制器(和通道)就一直为该作业所占用, 直到该作业被撤销静态分配方式不会出现死锁, 但设备的使用效率低 因此, 该方式并不符合分配的总原则 动态分配 在进程执行过程中根据执行需要进行. 当进程需要设备时, 通过系统调用命令向系统提出设备请求, 由系统按照事先规定的策略给进程分配所需要的设备, I/O控制器, 一旦用完, 便立即释放动态分配方式有利于提高设备的利用率, 但若分配算法使用不当, 有可能造成进程死锁 设备分配算法 常用的有先请求先分配, 优先级高者优先等对于独占设备, 及可以采用动态分配方式, 又可以静态分配方式, 但往往采用静态分配方式, 即在作业执行前, 将作业所要用的这一类设备分配给它共享设备可被多个进程所共享, 一般采用动态分配方式, 但在每个I/O传输的单位时间内只被一个进程所占有, 通常采用先请求先分配和优先级高者优先的分配算法 设备分配的安全性 安全性是指设备分配中应防止发生进程死锁安全分配方式 每当进程发出I/O请求后便进入阻塞态, 直到其I/O操作完成时才被唤醒. 这样, 一旦进程已经获得某种设备后便阻塞, 不能再请求任何资源, 而且在它阻塞时也不保持任何资源优点是设备分配安全, 缺点是CPU和I/O设备是串行工作的(对同一进程来说) 不安全分配方式 进程在发出I/O请求后继续运行, 需要时又发出第二个, 第三个I/O请求等, 仅当进程所请求的设备已被另一进程占用时, 才进入阻塞态优点是一个进程可同时操作多个设备, 从而迅速推进进程, 缺点是这种设备分配有可能产生死锁 逻辑设备名到物理设备名的映射 为了提高设备分配的灵活性和设备的利用率, 方便实现I/O重定向, 引入了设备独立性. 是指应用程序独立于具体使用的物理设备为了实现设备独立性, 在应用程序中使用逻辑设备名来请求使用某类设备, 在系统中设置一张逻辑设备表(Logical Unit Table, LUT), 用于将逻辑设备名映射为物理设备名. LUT表项包括逻辑设备名, 物理设备名, 设备驱动程序入口地址, 当进程用逻辑设备名来请求分配设备时, 系统为它分配相应的物理设备, 并在LUT中建立一个表项. 以后进程再利用逻辑设备名请求I/O操作时, 系统通过查找LUT来寻找相应的物理设备和驱动程序可采取两种方式建立逻辑设备表 在整个系统中只设置一张LUT, 这样, 所有进程的设备分配情况都记录在这张表中, 因此不允许有相同的逻辑设备名, 主要适用于单用户系统为每个用户设置一张LUT, 当用户登录时, 系统便为该用户建立一个进程, 同时也为之建立一张LUT, 并把该表放入进程的PCB
SPOOLing技术 (假脱机技术) 为了缓和CPU的高速性与I/O设备低速性之间的矛盾, 引入了脱机输入/输出技术, 该技术利用专门的外围控制机, 将低速I/O设备上的数据传送到高速磁盘上, 或者相反 SPOOLing的意思是外部设备同时联机操作, 又称假脱机输入/输出操作, 是操作系统中采用的一项将独占设备改造成共享设备的技术 输入井和输出井 输入井和输出井是指在磁盘上开辟出两个存储区域. 输入井模拟脱机输入时的键盘, 用于收容I/O设备输入的数据. 输出井模拟脱机输出时的键盘, 用于收容用户程序的输出数据 输入缓冲区和输出缓冲区 输入缓冲区和输出缓冲区是在内存中开辟的两个缓冲区. 输入缓冲区用于暂存由输入设备送来的数据, 以后再传送到输入井. 输出缓冲区用于暂存从输出井送来的数据, 以后再传送到输出设备 输入进程和输出进程 输入进程模拟脱机输入时的外围控制机, 将用户要求的数据从输入机通过输入缓冲区再送到输入井, 当CPU需要输入数据时, 直接将数据从输入井读入内存. 输出进程模拟脱机输出时的外围控制机, 把用户要求输出的数据先从内存送到输出井, 待输出设备空闲时, 再将输出井中的数据经过输出缓冲区送到输出设备共享打印机是SPOOLing技术的一个实例, 当用户进程请求打印输出时, SPOOLing系统同意为它打印输出, 但并不真正立即把打印机分配给该用户进程, 而只为它做两件事 由输出进程在输出井中为它申请一个空闲磁盘块区, 并将要打印的数据送入其中输出进程再为用户进程申请一张空白的用户请求打印表, 并将用户的打印要求填入其中, 再将该表挂到请求打印队列上 SPOOLing系统的主要特点 提高了I/O的速度将独占设备改造为共享设备实现了虚拟设备功能 SPOOLing如何节省时间 磁盘是一种高速设备, 在与内存交换数据的速度上优于打印机, 键盘, 鼠标等中低速设备, 试想一下, 若没有SPOOLing技术, CPU要向打印机输出要打印的数据, 打印机的打印速度比较慢, CPU就必须迁就打印机, 在打印机把数据打印完后才能继续做其他工作, 浪费了CPU不少时间在SPOOLing技术下, CPU要打印机打印的数据可以先输出到磁盘的输出井中, ( 这个过程由输出进程控制), 然后做其他事情. 若打印机此时被占用, 则SPOOLing系统就会把这个打印请求挂到等待队列上, 待打印机有空时再把数据打印出来, 向磁盘输出数据的速度比向打印机输出数据的速度快, 节省了时间
