# 操作系统原理 <!-- > 于鸣 QQ：280961400 M：13796684861 10%平时+10%实验+30%阶段+50%期末 考试不考简答 《操作系统之哲学原理》 --> ## 1 操作系统引论 **计算机操作系统是方便用户，管理和控制计算机软硬件的系统软件** ### 1.1 操作系统的目标和作用 #### 1.1.1 计算机系统资源 * 软件：系统软件（操作系统，数据库系统，编译环境），应用软件 * 硬件：处理机（CPU），内存，外部I/O设备，总线（BUS） * 操作系统的基本目标： 1. 方便性 能够方便的进行学习，使用与开发 2. 有效性 第一层含义是提高系统资源的利用率 另一层含义是提高系统的吞吐量 3. 可扩充性 能够方便的增添或修改功能或模块 4. 开放性 系统能遵循世界标准规范，便于彼此兼容 #### 1.1.2 什么是操作系统 * 关于现代操作系统的基本观点： * 从外部看操作系统 * 用户环境观点（计算机用户的观点） 操作系统是计算机用户与计算机硬件系统之间的**接口** * 用户接口（user interface）（eg：gui，cli） * 程序接口（application interface） * 虚拟环境观点（普通应用程序员的观点） 操作系统是建立在计算机硬件平台上的**虚拟机器（操作系统实现了对计算机资源的抽象）** 操作系统在虚拟机中充当管理员和协调员的角色，管理计算机的软硬件资源，并协调多任务、多进程的运行 * 从内部看操作系统 * 资源管理观点 操作系统是计算机系统中各类资源的管理者，它负责分配、回收以及控制系统中的各种软硬件资源 * 处理机管理 * 存储器管理 * I/O设备管理 * 文件管理 * 简单总结为以下三点： 1. OS作为用户与计算机硬件系统之间的接口 2. OS作为计算机系统资源的管理者 3. OS实现了对计算机资源的抽象 * *我们可以得到这样一个相对准确的操作系统的定义*：操作系统是计算机系统中的一个、**系统软件**，**管理和控制**计算机系统中的**硬件和软件资源**，合理地组织计算机的**工作流程**,以便有效利用这些资源为用户提供一个功能强、使用方便的**工作环境**，从而在计算机与用户之间起到**接口**的作用。 #### 1.1.3 推动操作系统发展的主要动力 1. 不断提高计算机资源的利用率 2. 方便用户 3. 器件的不断更新换代 4. 计算机体系结构的不断发展 5. 不断提出新的应用需求 ### 1.2 操作系统发展过程 #### 1.2.1 未配置操作系统的计算机系统 * 人工操作方式 * 特点： 1. 用户独占全机 2. CPU等待人工操作（I/O速度<<CPU速度） 3. 独占性 4. 串行性 * 缺点： 1. 计算机的有效机时受限制 2. 效率低 * 脱机输入/输出（Off-Line I/O）方式 事先在外围机的控制下将程序读入磁盘或磁带中，这样主机就可以和高速的磁盘或磁带完成I/O操作，有效减少CPU的空闲时间  * 优点 1. 减少了CPU的空闲时间 2. 提高了I/O速度 #### 1.2.2 单通道批处理系统 通过批处理程序管理应用程序一个接一个地运行，目的是减少作业间转换时的人工操作，从而减少CPU的等待时间 * 特点： 1. 自动性 2. 顺序性 3. 单道性  * 缺点： 1. 资源利用率低：内存中仅有一道程序，I/O过程中CPU处于等待状态，而I/O设备的低速性进一步降低了资源利用率（还是I/O速度<<CPU速度的矛盾）  #### 1.2.3 多道批处理系统 在执行I/O操作时为避免CPU空闲而运行其他程序，以此减少因I/O而带来的等待时间，使多道程序能够交替地运行，可以有效提高CPU的利用率 * 特点 1. 多道性 2. 无序性 3. 调度性 * 优点 1. 资源利用率高：多个程序交替运行，提高了利用率 2. 系统吞吐量大：系统资源处于忙绿状态，状态切换次数少 3. 平均周转时间长：作业需要排队等待 4. 无交互能力：运行过程中无法进行程序交互，修改和调试 * 多道批处理系统需要解决的问题 1. 处理机争用问题 2. 内存分配与保护问题 3. I/O设备分配问题 4. 文件的组织和管理问题 5. 作业管理问题 6. 用户与系统的接口问题 #### 1.2.4 分时系统 多道批处理系统虽然提高了资源利用率和吞吐量但是没有人机交互能力，存在一定的不便 * 分时系统实现中的关键问题： * 及时接收：指及时接收多个用户键入的命令或数据 * 及时处理：目的是使用户能对自己的作业及其运行及时地实施控制或进行更改 * 分时系统的设计思想： * 作业直接进入内存 * 采用时间片轮转的方式，同时为许多终端用户服务，对每个用户能保证足够快的响应时间，并提供交互会话的功能 * 时间片：将CPU的时间划分成若干个很短的片段（例如30ms），称为时间片，系统规定每个作业每次只能运行一个时间片，即便没有结束也会暂停该作业的运行，并立即调度下一个作业运行 * 特点： 1. 多路性 2. 交互性 分时系统最重要的特性，解决了批处理系统中的问题 3. "独占"性 （宏观上是多个人同时使用一个CPU，但实际上是多个人在不同时刻轮流使用CPU） 4. 及时性 #### 1.2.5 实时系统 实时系统是指系统能**及时**响应外部时间的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行 * 实时系统的类型 1. 工业（武器）控制系统 2. 信息查询系统 3. 多媒体系统 4. 嵌入式系统 * 实时系统与分时系统特征的比较： | 特征 | 实时系统 | 分时系统 | | ------ | ----------------------------------------------------------------------------------------------------------------------------------------------- | -------------------------------------- | | 多路性 | 在实时控制系统中体现为：系统周期性的对多路现场信息进行采集 | 按分时原则为多个终端用户提供服务 | | 独立性 | 在实时控制系统中体现为：对信息的采集和对对象的控制也都是彼此互不干扰的 不同终端用户在操作时彼此互不干扰 | | | 及时性 | 在预期的事件限度内完成相应的任务 | 指用户的请求能够在很短时间内获得相响应 | | 交互性 | 交互权限仅限于访问系统中的特定服务程序或接口 | 用户可通过终端与系统进行广泛的人机对话 | | 可靠性 | 要求系统**高度**可靠 | 要求系统可靠 | #### 1.2.6 微机操作系统的发展 1. 单用户单任务操作系统 1. CP/M 2. MS-DOS 2. 单用户多任务操作系统 1. Windows NT 4. 多用户多任务操作系统 1. UNIX OS ### 1.3 操作系统的基本特性 * 并发性 * 并行与并发 * 并行性是指两个或多个事件在**同一时间**发生 * 并发性是两个或多个事件在**同一时间间隔**内发生 * 需要注意并发与并行之间的区别，并发性+硬件多核=并行运行 * 线程 * 未引入线程时，同一个应用程序的计算程序和I/O程序只能顺序执行，效率较低 * 引入线程后，计算程序和I/O程序可以分别创建一个进程，两个进程可以**并发**执行，极大的提高了系统资源的利用率 * 共享性 * 指操作系统与多个用户的程序共同使用计算机系统中的资源 * **资源共享是以程序的并发为条件的**，若系统不允许程序并发运行，那也就不存在资源共享问题。同样的，如果系统不能处理好资源共享，那程序并发也必然会受到影响 * 虚拟性 * 虚拟，是指把一个物理上的实体，变为若干个逻辑上的对应物eg：VRAM，intel VT * 时分复用，空分复用 * 异步性 * 在多道程序环境下，允许多个进程并发执行，但由于竞争资源等因素的限制，进程的执行实质上是走走停停的，不连续的 * 因此每个程序在何时执行，多个程序间的执行顺序以及完成每道程序所需的时间都是不确定的和不可预知的，进程是以人们不可预知的顺序和速度向前推进的，这也就是异步性的解释 ### 1.4 操作系统的主要功能 1. 处理机管理功能 1. 进程控制 2. 进程同步 3. 进程通信 4. 调度 1. 作业调度 2. 进程调度 2. 存储器管理功能 1. 内存分配 2. 内存保护 3. 地址映射 4. 内存扩充 3. 设备管理功能 1. 缓冲管理 2. 设备分配 3. 设备处理 4. 文件管理功能 1. 文件存储空间的管理 2. 目录管理 3. 文件的读/写管理和保护 1. 文件的读/写管理 2. 文件保护 5. 操作系统和用户之间的接口管理功能 1. 用户接口 1. 联机用户接口 2. 脱机用户接口 3. 图形用户接口 2. 程序接口 ### 1.5 OS结构设计 * 传统的操作系统结构 * 无结构操作系统 * 模块化结构操作系统 * 分层式结构操作系统 * 客户/服务器模式 将OS划分为两部分，一部分是用于提供各种服务的一组服务器(进程)，另一部分是内核，用来处理客户和服务器之间的通信 1. 提高了系统的灵活性和可扩充性。 2. 提高了OS的可靠性。 3. 可运行于分布式系统中。 * 面向对象的程序设计 * 微内核操作系统结构 * 微内核与多个提供应用与服务的模块化服务器 * 提高了系统的可扩展性 * 增强了系统的可靠性 * 可移植性强 * 由于存在用户态与内核态的切换，故运行效率有所降低 ## 2 进程的描述与控制 ### 2.2 进程的描述 为了使程序并发执行，并且可以对并发执行程序加以描述和控制，我们引入进程的概念（进程=程序+执行） PCB：进程控制块（Process Control Block） #### 2.2.1 进程的定义与特征 * 进程是可并发执行的程序在一个数据集合上的**运行过程**，是系统进行进行**资源分配和调度**的**基本单位** * 进程和程序之间存在一对多的关系 * 一个程序可以对应一个或多个进程 * 一个进程只可以对应一个或一段程序 * 进程与程序是截然不同的概念，进程除了拥有程序所没有的PCB结构外还具有： 1. 动态性 进程动态产生动态消亡，可以在多个基本状态之间切换 2. 并发性 任何进程都可以同其他进程一起向前推进 3. 独立性 进程是一个能独立运行的基本单位，同时也是系统分配资源和调度的独立单位 4. 异步性 进程之间相互制约，随时中断，各个进程按各自独立，不可预知我的速度向前推进 #### 2.2.2 进程的基本状态及转换 1. 进程的三种基本状态 1. 就绪状态：进程已经准备好执行，只缺少处理机资源即可运行 2. 执行状态：正在占用处理机资源运行 3. 阻塞状态：进程还需要等待某一件或多件事件发生才能就绪  2. 进程的五种基本状态 1. 创建状态：进程已经创建，但未被操作系统纳入可执行进程管理 2. 终止状态：进程因多种原因而自我终止或被操作系统杀死  **进程因创建而产生 ，因调度而运行，因等待资源或事件而等待，因完成而消亡** #### 2.2.3 引入挂起操作后的进程状态与转换 为了减缓多个进程竞争内存资源的情况，因此引入虚拟存储，将一部分进程交换到外存以腾出内存空间 进程被交换到外存以后即进入挂起状态 被挂起的进程不能立即执行，也只有挂起它的进程才能使其取消挂起状态。挂起状态的条件独立于其他任何条件 1. 进程的七种基本状态 1. 静止就绪和活动就绪 2. 静止阻塞和活动阻塞  #### 2.2.4 进程管理中的数据结构 1. 操作系统中用于管理控制进程的数据结构 2. 进程控制块（PCB）的作用 1. 作为独立运行其基本单位的标志 2. 能实现间断性的运行方式 3. 提供进程管理所需要的信息 4. 提供进程调度所需要的信息 5. 实现与其他进程的同步与通信 3. PCB中的信息 1. 进程标识符 用于唯一的标识一个进程 1. 外部标识符 2. 内部标识符 2. 处理机状态 也称处理机的上下文，主要是由各种寄存器中的内容组成的（例如PC寄存器），该内容对应于响应中断的**保护现场** 3. 进程调度信息 为了操作系统能够调度进程而必须的一些信息 1. 进程状态 2. 进程优先级 优先级越高，越优先获得处理机时间 3. 进程调度所需的其他信息 与调度算法有关，例如已经等待的时间，已经运行的时间等 4. 事件（阻塞原因） 4. 进程控制信息 用于进程控制所必须的信息 1. 程序和数据的地址 程序和数据的内外存地址，以便再次调度到该进程执行时能够从PCB中找到其程序和数据 2. 进程同步和通信机制 实现进程同步和通信所必须的全部资源，例如消息队列指针，信号量 3. 资源清单 记录进程在运行期间所需要的和已分配的全部资源清单（除CPU以外） 4. 连接指针 队列中下一个进程的**PCB**的首地址 进程控制信息+程序+数据=进程 4. 进程控制块的组织方式 1. 线性表方式 2. 连接表方式 设置了多种状态队列（就绪队列、阻塞队列、运行队列等）指针，按链接方式组织PCB  3. 索引表方式 设置了多种状态索引表（就绪索引表、阻塞索引表等）指针，按索引方式组织PCB 5. 用户进程与系统进程 | 不同点 | 系统进程 | 用户进程 | | ---------------- | ---------------------------------------------------- | -------------------------------------------------------------------- | | 进程地位不同 | 系统进程是操作系统用来管理系统资源并行活动的并发软件 | 是操作系统提供服务的对象，是系统资源的实际使用者 | | 控制主体不同 | 由操作系统负责 | 主要由用户负责，但操作系统提供了一套基建变得服务调用命令作为协调手段 | | 资源控制属性不同 | 直接管理软硬件活动 | 必须向系统申请，由系统调度和分配 | | 调度优先级不同 | 较高 | 较低 | ### 2.3 进程控制 进程控制是进程管理中的最基本的功能，主要负责进程的创建及状态的切换。进程控制一般是由操作系统内核中的**原语**实现的 #### 2.3.1 操作系统内核 1. 支撑功能 1. 中断处理 2. 时钟管理 3. 原语操作 * 原语一般是指由若干条指令所组成的，用来实现某个特定功能，在执行过程中不可被中断的程序段 * 原语是操作系统核心的一个组成部分，并且**常驻内存** * 原语一旦开始执行，就要**连续执行完**，中间**不允许中断** 2. 资源管理功能 1. 进程管理 2. 存储器管理 3. 设备管理 #### 2.3.2 进程的创建 1. 进程的层次结构 通常允许一个进程创建和控制另一个进程，前者称为父进程，后者称为子进程，子进程又可创建其子进程，从而形成了一个树形结构的进程家族 2. 进程图 描述进程家族关系之间的一颗**有向树**  3. 引起创建进程的事件 1. 用户登录 2. 作业调度 3. 提供服务 4. 应用请求 4. **进程的创建** 在系统中出现创建新进程的请求后，便有Creat进程创建原语介入 1. 申请空白PCB 申请唯一标识符，索取一个空白PCB 2. 为新进程分配其运行所需的资源 3. 初始化进程控制块 回写相关信息 4. 把PCB插入就绪队列 #### 2.3.3 进程的终止 1. 引起进程终止的事件 1. 正常结束 2. 异常结束（Runtime Error） 3. 外界干预 2. 进程的终止 在系统中出现终止进程的请求后，便有进程终止原语介入 1. 根据标识符，检索出进程PCB，读取该进程的状态 2. 若被终止进程正处于执行状态，则立即终止该进程 3. 若该进程还有子孙进程，则一并终止，以防止其成为不可控制的进程 4. 将被终止进程的所有资源归还给父进程或系统 5. 将该进程的PCB从队列中移除 #### 2.3.4 进程的阻塞与唤醒 1. 引起进程的阻塞与唤醒的事件 1. 向系统请求共享资源失败后进入阻塞，等待资源释放后被唤醒 2. 等待某种操作的完成而进入阻塞，完成后被唤醒 3. 新数据尚未到达时而进程进入阻塞，到达而就绪后被唤醒 4. 等待新任务的到达而进入阻塞，到达后被唤醒 2. 进程的阻塞 1. 中断CPU，停止进程运行 2. 将CPU的现行状态存放到PCB的CPU状态保护区中 3. 将该进程置阻塞状态，并把它插入到等待队列中 4. 系统执行调度程序，将CPU分配给另一个就绪的进程 3. 进程的唤醒 1. 找到被唤醒进程的内部标识，让该进程脱离阻塞队列 2. 将现行状态改变为就绪状态 3. 插入就绪队列等待调度运行 ### 2.4 进程的互斥与同步 我们把异步环境下并发执行的进程，因直接制约而需要相互等待，相互合作，以达到各进程按相互协调的速度执行的过程称为**进程间的异步**，把因间接制约而导致交替执行的过程称为**进程间的互斥** * 基本概念： * 进程互斥：在多道程序环境下，每次只允许**一个进程**对**临界资源**进行访问 * 进程同步：指多个相关资源在执行次序上的协调 * 临界资源：一次仅供一个进程使用的资源（独占性） * 在进程中涉及到临界资源的程序段称为临界区，多个进程的临界区称为相关临界区 * **使用互斥临界区的原则** * **空闲让进**：当无进程在临界区时，任何有权使用临界区的进程可进入 * **忙则等待**：不允许两个及以上的进程同时进入临界区 * **有限等待**：任何进入临界区的要求应在有限的时间内得到满足（换句话说一个进程不能无限制地使用临界资源） * **让权等待**：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权 #### 2.4.1 互斥与同步问题的解决 * 软件方法 指由进程自己，通过执行相应的程序指令，实现与别的进程的同步与互斥 ```cpp= flag[i]=true,turn=j; flag[j]=true,turn=i; while(flag[j]&&turn==j); while(flag[i]&&trun==i); //do ops here //do ops here flag[i]=false; flag[i]=false; ``` * 硬件方法 指通过屏蔽中断或采用专门的机器指令控制同步与互斥 * 信号量方法 指在操作系统的管理下，通过标记信号量来完成进程间的信息交互，进而解决互斥问题 一般来说互斥资源需要一个信号量记录，而同步需要通过2个信号量，进行交叉唤醒。 1. 整型信号量 整型信号量只能通过两个标准的**原子操作**来访问，分别是``wait(S)``，``signal(S)`` ```cpp wait(S){ //occupy or lock while(S<=0);//just wait S--; } solve(){ //do ops here } signal(S){ //free or unlock S++; } ``` ``wait(s)``会导致处理机始终处于**忙等**状态，因此该机制并未遵守"让权等待"要求 2. 记录型信号量 ```cpp typedef struct{ int value; struct process_control_block *list; }semaphoere wait(semaphoere* S){ S->value--; if(S->value<0){ block(S->list);//即阻塞当前的进程 } } solve(process_control_block* tr){ //do ops here! //当其运行结束时需要将自己移出list head，以允许后续进程得到运行 } signal(semaphoere* S){ S->value++; if(S->value<=0){ wakeup(S->list);//即已知此时有进程处于被阻塞状态，需要将当前归还的进程给予list头的阻塞进程，并将其唤醒，使得其能够继续运行 } } ``` 事实上记录型信号量的机制是利用了阻塞与唤醒原语，而为了利用上这两种原语，需要对阻塞的进程有所记录（``-(S->value)``事实上表示此时被阻塞的进程数，并且始终阻塞的是头进程），进一步通过list结构去保证优先关系 以捡黑白球题为例： ```cpp semaphore s1,s2; s1.value=1,s2.value=0; cobegin process P1(){ while(true){ wait(s1){ s1--; //check and block }; //do ops signal(s2){ s2++; //check and wakeup }; } } //-------------------// process P2(){ while(true){ wait(s2){ s2--; //check and block }; //do ops signal(s1){ s1++; //check and wakeup }; } } coend ``` 苹果橘子问题 桌上有一个盘子，每个盘子只能放入一只水果，爸爸放苹果，妈妈放橘子，女儿吃苹果，儿子吃橘子 考虑关键资源是盘子，量为1，其中四个人都是互斥使用盘子，爸爸和女儿构成同步关系，妈妈和儿子构成同步关系 ```cpp semaphore sa,sb,sc,sd,p;//一对同步需要两个，一对互斥需要一个。此处有AB互斥，AC同步，BD同步，共需5个信号量 p.value=1; sa.value=1; sb.value=1; sc.value=0; sd.value=0; cobegin process sa{ while(true){ wait(sa)&wait(p);//check whether dad can put or plate is empty //put apple signal(sc);//notice daughter to eat } } process sb{ while(true){ wait(sb)&wait(p); //put tangerine signal(sd); } } process sc{ while(true){ wait(sc);//check whether she can eat //eat apple signal(sa)&signal(p);//notice dad can put and release the plate to be empty } } process sd{ while(true){ wait(sd); //eat tangerine signal(sb)&signal(p); } } coend ``` 事实上此处的sa与sb的功能被资源p的使用情况给完全覆盖，因此sa与sb可以优化去除，如下代码 其中p的资源限制用来控制放置水果的过程，sc与sd的限制用来区分此处的资源归属 ```cpp semaphore sc,sd,p;// p.value=1; sc.value=0; sd.value=0; cobegin process sa{ while(true){ wait(p);//check whether dad can put or plate is empty //put apple signal(sc);//notice daughter to eat } } process sb{ while(true){ wait(p); //put tangerine signal(sd); } } process sc{ while(true){ wait(sc);//check whether she can eat //eat apple signal(p);//notice dad can put and release the plate to be empty } } process sd{ while(true){ wait(sd); //eat tangerine signal(p); } } coend ``` 3. AND型信号量 将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配 这种做法可以有效地避免死锁的产生 ``Swait(S1,S2,S3,...,Sn)`` ``Ssignal(S1,S2,S3,...,Sn)`` 4. 信号量集合 通过``triplet<semaphore,int,int>tp;//<Si,ti,di>-><resource semaphore,minimun resource count,required resource count>``来控制资源的申请，即设定了一个资源最小量 一般信号量集有几种特殊情况 1. ``Swait(S,d,d)``，此时在信号量S，但允许他每次申请d个资源，如果当现有资源数小于d，不予分配 2. ``Swait(S,1,1)``，此时的信号量集已退化为一般的记录型信号量或者是互斥信号量 3. ``Swait(S,1,0)``，这是一种很特殊的信号量操作，当S>=1时，允许多个进程进入某特定去，当S变为0后，将阻止任何进程进入特定区。亦即是一个可控开关 * 管程方法 信号量方法要求程序编写者具有完善的进程分析能力，难度较高，实现过程不便。因此引入管程机制来优化这个过程 代表**共享资源**的**数据结构**，以及由对该共享数据结构**实施操作**的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块 我们称之为管程。 * 管程由以下三部分组成 1. 局部于管程的共享变量说明 2. 对该数据结构进行操作的一组过程 3. 对局部于管程的数据设置初始值的语句 * 此外，还须为管程赋予一个名字。  * 条件变量 * 当一个进程进入管程后被阻塞，知道阻塞的原因被接触时，在此期间如果该进程不释放管程，那么其他进程也不能够进入管程。为此，把**阻塞原因**定义为条件变量，每一个条件变量会维护一个等待队列，记录因该条件变量而阻塞的所有进程，对条件变量只有两种操作，wait与signal * ``x.wait``，不满足条件x，把进程插入x的等待队列，并释放该管程 * ``x.signal``，x条件得到满足，从队列中唤醒一个进程 * 与信号量不同，条件变量时没有值的，剩余资源数由共享数据结构记录 * 利用管程实现互斥 * 任何时刻管程内只允许有一个活跃进程 * 当一个进程调用管程中的过程时，首先检查该管程中是否有其他活跃进程，如果有则阻塞调用进程，直到管程中的进程离开管程 * 管程的互斥操作由编译程序支持，自动存在一个mutex互斥信号量 * 利用管程实现同步 * 在管程中设置一对同步操作原语 * 利用管程解决生产者-消费者问题 首先便是为它们建立一个管程，该管程包含两个过程 1. put过程，即生产者放入缓冲池的过程 2. get过程，即消费从缓冲池取的过程 * 消息传递方式 见[进程通信](#25-进程通信) #### 2.4.2 经典信号同步问题 * 生产者与消费者问题 一个经典的吃水果问题为例 桌子上有个能装下五个水果的空盘子，爸爸不断的向里面放苹果与橘子，儿子吃橘子，女儿吃苹果 ```cpp semaphore mutex;//盘子的访问互斥信号量 semaphore empty; semaphore p1,p2; mutex.value=1; empty.value=5; p1.value=p2.value=0; cobegin process Dad(){ while(true){ wait(empty);//(1) wait(mutex);//(2) //put in tangerine or apple randomly signal(mutex);//(3) if(put_in_tangerine){ signal(p1); } if(put_in_apple){ signal(p2); } } } process Son(){ while(true){ wait(p1);//(4) wait(mutex);//(5) //eat tangerine signal(mutex); signal(empty); } } process Daughter(){ while(true){ wait(p2); wait(mutex); //eat apple signal(mutex); signal(empty); } } coend ``` 几点需要注意 1. (1)(2)处不可以交换，必须先试图获取到盘子中的空位资源，再申请盘子的操作互斥锁，反之就可能出现申请到操作互斥锁后而因为没有空位出现死锁的情形 2. (3)处可以置为``while()``循环末尾，但考虑到mutex是互斥访问锁，会阻断其他所有进程的运行，因此需要尽可能降低其互锁的范围，置于此是最优的选择 3. (4)(5)处不可交换，同(1)(2) * 读者/写者问题 需要满足的几个要求： * 可以同时读 * 不可以同时写 * 不可以在读取的时候写入 在读者优先的情况下，读请求会覆盖写请求，只有当所有的读全部结束以后才允许写 ```cpp swmaphore wsem,X; wsem.value=1;//写允许信号量 X.value=0;//rcount的X锁 int rcount=0;//正在读取的进程数 process read(){ wait(X); rcount++; if(rcount==1){ wait(wsem); } signal(X); //do ops here //reading wait(X); rcount--; if(rcount==0){ signal(wsem); } signal(X); } process write(){ wait(wsem); //do ops here //writing signal(wsem); } ``` 在写者优先 ```cpp semaphore rsem,wsem,X,Y; rsem.value=wsem.value=X.value=Y.value=1; int rcount,wcount; process read(){ wait(rsem); wait(X); rcount++; if(rcount==1){ wait(wsem); } signal(X); signal(rsem);//允许其他人加入读队列 //do ops here //reading wait(X); rcount--; if(rcount==0){ signal(wsem); } signal(X); } process write(){ wait(Y); wcount++; if(wcount==1){ wait(rsem); } signal(Y); wait(wsem);//注意区分此处的wait是在加入写队列之后。也就是说只要有写请求就会的关闭rsem，阻塞读进程，而写进程不会阻塞读的优先级，并且只允许一个 //do ops here //writing signal(wsem); wait(Y); wcount--; if(wcout==0){ signal(rsem); } signal(Y); } ``` 用的最为广泛的是时间优先，只需要一个整体信号量作为入口就可以 一定程度上存在性能损失，因为没有利用读的并行操作 ```cpp semaphore X; X.value=1; process read(){ wait(X); //do ops here //reading signal(X); } process read(){ wait(X); //do ops here //writing signal(X); } ``` 例题1： 独木桥问题：东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待另一方的汽车全部过完后，另一方的汽车才允许过桥 ```cpp semaphore wait;//独木桥的互斥信号量 semaphore mutex1;//count1的读写锁 semaphore mutex2;//count2的读写锁 mutex1.value=mutex2.value=1=wait.value=1; int count1;//东到西的桥上车辆数量 int count2;//西到东的桥上车辆数量 count1=count2=0; cobegin process eastToWest(){ while(true){ wait(mutex1); count1++; if(count1==1){ wait(wait); } signal(mutex1); //cross Bridge wait(mutex1); count1--; if(count1==0){ signal(wait); } signal(mutex1); } } process westToEast(){ while(true){ wait(mutex2); count2++; if(count2==1){ wait(wait); } signal(mutex2); //cross Bridge wait(mutex2); count2--; if(count2==0){ signal(wait); } signal(mutex2); } } coend ``` 例题2： 橘子果汁问题，阶段真题 ```cpp semaphore pour,drink,bottle; int vol=0; pour.value=bottle.value=1;//pour 和 drink 都只用来限制是否能放，和是否能喝，具体瓶子中的果汁量通过vol变量去记录，而vol又通过bottle信号量实现互斥访问 cobegin process dad(){ while(true){ wait(pour); wait(bottle); vol++; if(vol==1){ signal(drink); } if(vol!=5){ signal(pour); } signal(bottle); } } process son(){ while(true){ wait(drink); wait(bottle); vol=0; signal(pour); signal(bottle); } } coend ``` * 哲学家进餐问题 * 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边和右边去取筷子 * 如果简单的获取资源并执行很容易出现死锁，不是一个正确的调度策略 * 给出一些有趣的解法 1. 最多只允许4个哲学家同事坐在桌子周围，仅当一个哲学家左右两边的筷子都可用时才允许他拿筷子 此时不会出现死锁 ```cpp semaphore chop[5]; for(int i=0;i<5;i++){ chop[i].value=1; } semaphore seat; seat.value=4;//设置为4，就不会出现1等待2，2等待3，...，5等待1的情况，等待链会有断开，也就不会出现死锁 void philosopher(int i){ while(1){ think(); wait(room); wait(chop[i]); wait(chop[(i+1)%5]); eat(); signal(chop[(i+1)%5]); signal(chop[i]); signal(room); } } int main(){ for(int i=0;i<5;i++){ parbegin(philosopher(i)); } } ``` 2. 规定奇数号的哲学家必须先拿左边的筷子，偶数号的哲学家必须先拿右边的筷子 此时不会出现死锁 ```cpp semaphore chop[5]; for(int i=0;i<5;i++){ chop[i].value=1; } void philosopher(int i){ while(1){ think(); if(i%2==0){ wait(chop[(i+1)%5]); wait(chop[i]); eat(); signal(chop[i]); signal(chop[(i+1)%5]); } else{ wait(chop[i]); wait(chop[(i+1)%5]); eat(); signal(chop[(i+1)%5]); signal(chop[i]); } } } ``` ### 2.5 进程通信 * 进程之间的同步和互斥是一种低级通信（即交换控制信息的过程），只是用来控制进程执行的速度 * 进程通信的类型 1. 共享存储器系统 2. 消息传递系统，通过通信原语进行操作 3. 管道系统，通过共享的管道文件，一端发送数据，一端接受数据 4. 客户/服务器系统 1. 套接字（Socket.io） 2. 远程过程服务器调用（RPC） * 消息传递通信的实现方法 1. 直接通信方式 ``send(Receiver,msg)``发送一个消息给接收进程 ``receive(Sender,msg)``接收sender发来的消息 2. 间接通信方式 ``send(mailbox,msg)`` ``receive(mailbox,msg)`` * 信箱的类型 1. 私用信箱 由用户进程自己创建，拥有者可读写，其他用户只写。 2. 公用信箱 由操作系统创建，提供给所有进程使用 3. 共享信箱 由某进程创建，拥有者和共享者可以读写 * 四种对应关系 * 一对一 sender和receiver建立专用通信链路 * 多对一 允许提供服务的进程于多个用户进程交互 * 一对多 一个发送进程与多个接收进程交互，广播形式 * 多对多 公用信箱，多用户可读写 * 消息传递通信中遇到的若干问题 * 通信链路的建立 通过建立连接的系统原语实现 * 消息的格式 定长与不定长的消息格式，通过协议规约 * 进程的同步方式 发送方与接收方的阻塞/不阻塞关系 ### 2.6 线程的基本概念 > 随着进程愈发庞大，其在系统中进行状态切换所需要的性能开销越来越大 #### 2.6.1 线程的引入 * 因此引入线程的概念，由进程负责资源的调度，而**线程则成了独立的调度分派的基本单位**。线程轻量，便于在不同状态之间切换，而**进程依然作为系统资源调度的基本单位**而存在。 * 需要注意的是，并不意味的线程不拥有任何资源，事实上线程会拥有一部分私有资源便于程序执行等，绝大多数的资源依然归于进程管理 #### 2.6.2 进程与线程的比较 | Column 1 | Column 2 | Column 3 | | ---------------- | ---------------------- | -------------------------- | | 调度的基本单位 | 资源分配 | 调度分派，独立运行 | | 并发性 | 只能够进程并发 | 不同进程，不同线程均可并发 | | 拥有资源 | 大多数 | 少量 | | 独立性 | 进程为粒度，独立性较高 | 线程为粒度，独立性更低 | | 系统开销 | 大 | 小 | | 支持多处理机系统 | 多进程 | 单进程也可以多线程 | #### 2.6.3 线程的状态和线程控制块 * 线程运行的三个状态 * 执行态 * 就绪态 * 阻塞态 * 线程控制块TCB 内容近同PCB，不再赘述 * 多线程OS中的进程属性 * 进程是一个可拥有资源的基本单位 * 多个线程可并发执行 * 进程已不是可独立运行的基本个体 ### 2.7 线程的实现 #### 2.7.1 线程的实现方式 1. 用户级线程（User Level Threads） 用户级线程是在用户空间内创建的，对线程的创建，撤销，同步，通信等功能都不需要内核的支持 优点： * 线程切换与内核空间无关，节约了模式切换的开销 * 调度算法可以针对进程专门编写 * 用户级线程的实现与OS无关，便于改造 缺点： * 系统调用引起的阻塞，当一个线程执行系统调用时，不仅该线程被阻塞，进程内的所有线程都会被阻塞 * 多线程应用不能利用多处理机进行多重处理的优点 * 存在执行优先级分配不公平的现象（进程公平而不是线程公平） 2. 内核支持线程（Kernel Supported Threads） 线程的创建，撤销，同步，通信等功能都是在内核空间实现的 优点： * 内核能够同时调度同一进程中的多个线程并行执行 * 如果一个线程被阻塞了，其所属的进程内的其他线程可以正常执行，不受影响 缺点： * 线程运行在用户态，但对线程的调度管理是在内核态实现的，线程切换需要进行内核/用户的模式切换，系统开销较大 3. 混合模式（ULT/KST mixed） 将一个或多个用户级线程映射到一个或多个内核级线程上，这样的内核级线程通常称为轻型进程（Light Weight Process） 这样可以有效的利用KST的并行性，又可以避免因内核空间太多的线程导致的系统负担 #### 2.7.2 线程的实现 1. ULT的实现 通过运行时系统（Runtime System），对线程进行管理和控制 通过轻型进程（Light Weight Process），对线程进行管理和控制（对应ULT/KST mixed模式） 2. KST的实现 系统创建新进程的时候，就会分配一个任务数据区（Per Task Data Area），其中有若干个TCB空间 ## 3 处理级调度与死锁 > 3.2与3.6是本章核心 ### 3.1 处理机调度的基本概念 调度是指，在一个队列中，按照某种方法，选择一个合适个体的过程（选择的问题） #### 3.1.1 高级，中级和低级调度 1. 高级调度 调度对象是作业 从外存中选择一个作业调入内存中，为他们创建进程，分配资源，并把它们放入就绪队列 2. 中级调度 调度对象是进程，调度位置是内存 调度目标是提高内存利用率和系统吞吐量 把那些暂时不能运行的线程调至外存等待（挂起状态） 3. 低级调度 调度对象是进程 决定就绪队列中哪个进程可以获得处理机 * 非抢占方式 1. 执行完毕或不能再执行 2. 提出I/O请求而中断执行 3. 执行了某种原语操作 * 抢占方式 允许通过优先级原则；短进程优先原则；时间片原则等去中断进程的运行，以提高运行效率 #### 3.1.2 调度目标及调度队列模型 调度目标： 1. 资源利用率 2. 公平性 3. 平衡性 4. 策略强制执行 队列模型： 1. 仅有进程调度的调度队列模型  2. 具有高级和低级调度的队列模型  3. 同时具有三级调度的队列模型  #### 3.1.3 选择调度方式和调度算法的若干准则 1. 面向用户的准则 1. 周转时间短 平均周转时间为：$\begin{align}T=\frac{1}{n}[\sum_{i=1}^{n}T_i]\end{align}$ 带权周转时间：$\begin{align}W=\frac{1}{n}[\sum_{i=1}^{n}\frac{T_i}{T_{S_i}}]\end{align}$ 例如：一个任务在$T=8$的时候到来，$T=10$的时候得到运行，$T=12$时运行完成，则其周转时间为$T=12-8=4$，带权周转时间为$W=(12-8)/(12-10)=2$，平均周转时间$\downarrow$，带权周转时间$\rightarrow 1$，调度越好 系统吞吐量高 处理机利用率高 2. 响应时间快（分时操作系统） 3. 截止时间的保证，可预测性（实时操作系统） 4. 优先权准则 2. 面向系统的准则 1. 系统吞吐量高 2. 处理机利用率好 3. 各类资源的平衡利用 4. 策略强制执行 ### 3.2 调度算法 #### 3.2.1 先来先服务（First-come First-served）和短作业（Short Job First）优先调度算法 1. FCFS调度 仅需要一个队列即可实现 对短作业不公平（白等） 2. SJF调度 从后备队列中选择若干个估计运行时间最短的作业，优先执行 缺点： 1. 该算法对长作业不利，长作业可能一直得不到执行 2. 不考虑作业的紧迫程度 3. 估计运行时间可能会出现偏差，致使不能真正实现优化调度 #### 3.2.2 高优先权优先调度算法 1. 优先权调度算法的类型 1. 非抢占式 系统每次都把处理机分配给就绪队列中优先权最高的进程后，而一旦开始运行该进程便一直执行下去，直至完成 2. 抢占式 系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权（严格）更高$(P_new>P_{current})$的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程 2. 优先权的类型 1. 静态优先权 静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变 确定依据包括： 1. 进程类型 2. 进程对资源的需求 3. 用户要求 2. 动态优先权 在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能（即综合考虑先来先服务） 3. 高响应比优先调度算法 优先权=（等待时间+服务时间）/（要求服务时间）=（响应时间）/（要求服务时间） 该算法综合考虑了短作业和先来先服务的算法，对于长作业来说，长期等待以后也会获得更高的优先级得到运行 #### 3.2.3 基于时间片的轮转调度算法 1. 时间片轮转法 在早期的时间片轮转法中，系统将所有的就绪进程按**先来先服务**的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片 2. 多级反馈队列调度算法 为了解决优先级的问题，应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小（一般成2的次幂） 性能评价： 1. 终端型作业用户 对实时性要求最高，所需时间也小，通常在第一队列中即可完成 2. 短批处理作业用户 前几个队列即可快速完成，周转时间仍然较短 3. 长批处理作业用户 可以依次轮转，不必担心得不到运行 ### 3.3 实时调度（考试不涉及） #### 3.3.1 实现实时调度的基本条件 1. 提供必要的信息 2. 系统处理能力强 3. 采用抢占式调度 ### 3.4 死锁概述 #### 3.4.1 资源问题 1. 可重用资源和消耗性资源 1. 可重用资源指可供用户重复分配多次的资源 2. 可消耗性资源是指在进程运行期间由进程动态地创建和消耗的资源 2. 可抢占性资源于不可抢占性资源 1. 可抢占性资源在某进程获得后仍然可以再被其他进程或系统抢占，可抢占性资源不会引起死锁 2. 不可抢占性资源指某进程获得后不可以再被分配给其他的进程，只能由该进程自行释放 #### 3.4.2 计算机系统中的死锁 1. 可能引起死锁的原因 1. 竞争不可抢占性资源引起死锁 因争夺资源陷入僵局 2. 竞争可消耗资源引起死锁 消息通信机制进行通信可能因为receive与send的顺序不当而引起死锁 3. 进程推进顺序不当引起死锁 错误的进程推进顺序可能会导致多个进程因为资源的抢占而阻塞引起死锁 2. 产生死锁的必要条件 1. 互斥条件 2. 请求和保持条件 3. 不可抢占条件 4. 循环等待条件 3. 处理死锁的方法 1. 预防死锁 2. 避免死锁 3. 检测死锁 4. 解除死锁 ### 3.5 预防死锁 通过破坏产生死锁的必要条件而从底层预防死锁 1. 破坏请求和保持 1. 必须一次请求并获得进程所需的所有资源，否则等待且不占用任何资源 2. 允许只获得运行初期所需的资源，再逐步释放，逐步请求，是一种折中的方法 2. 破坏不可抢占 1. 当一个已经保持了某些不可抢占的资源的进程提出申请但无法被满足时，其需要释放所有已占有的资源 3. 破坏循环等待 1. 对资源进行线性排序，进程需要按序号递增来进行资源申请，也就不会出现1等2，2等1的情况 ### 3.6 避免死锁 避免死锁同样是一种预防性措施，但不采取限制措施，而是通过某种运行中策略，避免系统进入死锁 #### 3.6.2 银行家算法 需要准备的数据结构 1. 可利用资源向量Available 2. 最大需求矩阵Max 3. 分配矩阵Allocation 4. 需求矩阵Need Need=Max-Allocation 设Request~i~是进程P~i~的请求向量，如果Request~i~[j]=K，表示进程P~i~需要K个R~j~类型的资源。当P~i~发出资源请求后，系统按下述步骤进行检查： 1. 如果Request~i~[j]≤Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值 2. 如果Request~i~[j]≤Available[j]，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待 3. 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]-= Request~i~[j]; Allocation[i,j]+= Request~i[j]; Need[i,j]-= Request~i~[j]; 4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程P~i~，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程P~i~等待 ### 3.8 死锁的检测与解除 如果在系统中，因为各种原因发生了死锁，需要进行检测与解除 #### 3.8.1 死锁的检测 系统中必须保存有关资源的请求与分配信息，以及提供一个能够检测死锁的算法 1. 资源分配图算法 圈表示进程；矩形块表示资源，其中体现个数；有向边表示请求与分配  #### 3.8.2 死锁的解除 1. 终止所有死锁进程 2. 逐个终止死锁进程 ## 4 存储器管理 ### 4.1 存储器的层次结构 * 访问速度与存储容量的不同需求催生了计算机的存储器产生多样的层次结构 #### 4.1.1 多层结构的存储器系统 * 越靠近CPU的存储器越强调速度，反之则越强调容量与性价比 * 两种存储介质之间通常存在**缓存**，用来解决两种介质读写速度不匹配的问题  ### 4.2 程序的装入和连接 用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下步骤: 1. 编译，由编译程序(Compiler)对用户源程序进行编译，形成若干个目标模块(Object Module) 2. 链接，由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(Load Module) 3. 装入，由装入程序(Loader)将装入模块装入内存  #### 4.2.1 程序的装入 1. 绝对装入方式 计算机内存较小，系统精简，仅能运行单道程序的时候。**单道批处理系统**中可以**直接确定程序装入内存的何处**，程序以**绝对地址（物理地址）**进行编程 2. 可重定位装入方式 在**多道批处理系统中不能够直接确定物理地址**，因此引入相对地址的概念，编写程序时，依据0为起始相对地址进行编程，装入内存后再根据实际装入的位置进行移动（$0+t$） 一旦程序装入内存后，其各处地址将不再能够更改，**不适合进程在内存空间的移动**，也就不适合包括挂起，唤醒，中断等一系列操作 3. 动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种**地址转换推迟到程序真正要执行时**才进行，可以很好地解决程序在内存中的**移动**问题 #### 4.2.2 程序的连接 * 一个程序可能由多个函数（模块）组合而成，模块与模块之间存在相互依赖和调用的关系，必须将他们连接在一起成为了一个完整的装配模块，一并装入内存，程序才能运行 需要解决两个问题 1. 对相对地址进行修改 2. 变换外部调用符号 1. 静态连接方式 直接将程序所用到的所有模块连接在一起，一并装入内存 静态链接方式可能会存在模块冗余的问题，降低了内存利用率，没有实现模块之间的共享 （如下图，两个程序都用到了B，C模块，但如果采用静态链接，则两个程序的B，C模块不能复用，内存中必须存在两份）  2. 装入时动态链接 在**装入内存**时，采用边装入边连接的连接方式，如果发生一个外部模块调用事件则首先去寻找内存中是否已经装入，如果有则不再二次装入重复的模块，而是连接起来，并去更改相关模块中的相对地址 * 上述两种方式，都需要一次性将程序运行所需要的模块全部装入内存，依然可能存在内存浪费的情况（比如某些分阶段运行的程序，不同的阶段使用不同的模块，一次性全部装入势必会产生浪费） 3. 运行时动态链接 在**程序运行**时，采用边运行，边装入连接的方式，如果在运行时发生某一模块缺失的情况，才去内存中寻找或是装入。虽然损失了一部分性能，但换取了更高的内存利用率 ### 4.3 连续分配存储管理方式 #### 4.3.1 单一连续分配 在**单道程序环境**下，当时的存储器管理方式是把内存分为系统区和用户区两部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而**在用户区内存中，仅装有一道用户程序**，即**整个内存的用户空间由该程序独占**。这样的存储器分配方式被称为单一连续分配方式（计算机组成原理上所学习的机器模型） #### 4.3.2 固定分区分配 1. 划分分区 将内存的用户空间，划分成若干个大小固定的内存分区 * 划分成相同大小 * 划分成不同大小 2. 内存分配 为了管理内存空间，需要一个**固定分区使用表**，用来记录每个分区的分区号，首地址，分区大小以及分配状态，用来满足进程对内存的请求与分配 3. 可能存在的问题 分区的大小难以掌握，可能会出现分区浪费（每个分区只能同时被一个进程占用），或是分区大小不足以满足进程需求的情况 #### 4.3.3 动态分区分配 1. 动态分区分配中的数据结构 1. 空闲分区表 空闲分区表用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号、分区大小和分区始址等数据项  2. 空闲分区链 空闲分区链实现对空闲分区的分配和链接，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链  2. 基于顺序搜索的动态分区分配算法 1. 首自适应算法（First Fit） 排序策略：按地址递增的次序连接 分配策略：从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。找到以后，划分该空闲分区，维持链接状态不变。如果到链尾依然没有找到，则分配失败 策略特性：FF算法可以保证较高地址具有较大的连续空闲分区，能够比较好的利用低地址区域，但时间复杂度较大，每次分配可能都会遍历整个空闲分区链，且低地址区域可能出现比较多的空闲分区碎片，会产生很多不必要的时间开销 2. 循环首自适应算法（Next Fit） 排序策略：按地址递增的次序连接 分配策略：区别于FF，每次都从链首开始顺序查找，NF算法每次从上一次找到的空闲分区下一个空闲分区开始查找，其数据结构是一个**循环链表**，如果遍历一圈仍然没有找到，则分配失败 策略特性：NF算法虽然会导致较大的连续空闲分区减少，但可以保证低地址空闲避免出现过多的空闲分区碎片，一定程度上可以减少分配的时间开销 3. 最佳适应算法（Best Fit） 排序策略：按容量大小递增的次序连接 分配策略：从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。找到以后，划分该空闲分区，维持链接状态不变。如果到链尾依然没有找到，则分配失败 策略特性：可能会出现大量的空闲分区碎片，但空间利用率高 4. 最差适应算法（Worst Fit） 排序策略：按容量大小递增的次序连接 分配策略：总是选择最大的空闲区使用 策略特性：内存碎片较小，但会导致存储器内缺少较大的空闲分区 3. 基于索引搜索的动态分区分配算法 1. 快速适应算法（Quick Fit） 排序策略：将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区单独设立一个空闲分区链表，这样系统中存在多个空闲分区链表。同时，在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针 2. 伙伴系统（Buddy System） 排序策略：该算法规定，无论已分配分区或空闲分区,其大小均为$2^k$，$k\leq m$。通常$2^m$是整个可分配内存的大小 4. 动态分区分配流程 * 内存分配 通过设置一个分区最小值size，避免出现过多的内存分区碎片，影响分配算法的执行效率  * 内存回收  回收后会自动拼接到上下的空闲分区内 5. 动态重定位分区分配算法 * 这样的分配流程可能会导致因为内存碎片的存在而出现，总剩余内存足够，但却没有一块连续分区足够，而导致程序无法装入内存，得到运行的窘境，因此引入了紧凑的概念 紧凑是将内存中的正在使用的分区，通过移动，将空闲区域汇总到一起，形成一个较大的连续空闲区，进而可以将其他需要的程序得到运行 *  * 动态重定位 要实现这个过程，还需要让内存中的程序得以移动，即引入了动态重定位的概念 即通过一个重定位寄存器，让CPU侧看来，程序依然没有移动而内存侧已经实际发生了移动（本来相对地址是+0，现在重定位以后变成+t）  ### 4.4 对换 #### 4.4.1 多道程序环境下的对换技术 * 对换的引入 某些进程可能因为阻塞而处于未运行状态，但却在内存中占用了大量的资源，因此需要将这类进程进行有效的管理 * 对换区 在外存中设置一块单独的区域——对换区，一旦出现进程因为阻塞而占用大量内存的情况，则将这部分转移至对换区，这个操作被称为挂起（对进程挂起）与对换（内存空间上进行对换） * 对换的类型 根据每次对换的数量 * 整体对换 一次性对换整个进程 对应连续内存空间分配的情况 * 页面（分段）对换 一次只对换一个页面 对应离散内存空间分配的情况（分页或分段式存储） #### 4.4.2 对换空间的管理 * 对换空间管理的主要目标 * 对文件区管理的主要目标 考虑容量问题，采用离散存储方式 * 对对换空间管理的主要目标 考虑读写速度问题，采用连续编址方式 * 对换区空闲盘块管理中的数据结构与分配策略 由于对换区采用和内存相同的连续编址方式，其数据结构与分配策略均与内存中的相雷同见[连续动态分区分配](#43-连续分配存储管理方式) #### 4.4.3 进程的唤出与换入 * 进程的换出 * 选择被换出的进程后进行数据转移 * 进程的换入 * 对换进程将定期执行换入操作，每次从中选取就绪状态但被换出的进程，优先选择等待时间最久的进程换入 ### 4.5 分页存储管理方式 分页存储管理是与前面所述的连续存储管理所不同的一种存储管理方式，其目的是将多个离散的内存块分配给同一个程序 对于程序来说，其看到的内存空间仍然是连续的，但因为引入了地址变换映射机构，可以将其离散到实际的内存空间上去。既提高了内存利用率，也避免了程序编写过于复杂 #### 4.5.1 页面与页表 * 页面 * 页面与物理块 将一个进程的逻辑地址空间分成若干个大小相等的片，称为**页面或页**，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为**物理块或页框**， 也同样为它们加以编号，如0＃块、1＃块等等。**页和块是一一对应的概念** 如果最后一页装不满一块而形成了不可利用的碎片，称之为**页内碎片** * 页面大小的设置 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大 通常来说，页面大小我们选择2的整数次幂，通常介于512B-8KB之间 * 页表 需要保存下来页与块的对应关系，因此引入页表的概念，即将页号与块号构建出一一对应的关系，存入表内。页表是对于进程而言的，每个进程都拥有其页表 | 页号 | 块号 | | ----- | ------ | | Page1 | Block2 | | Page2 | Block1 | | Page3 | Block5 | | ... | ... | 需要注意的是，实际情况下页号通过数组下标进行索引，不会真实存在 #### 4.5.2 地址变换机构 1. 基本地址变换机构 由于页表长度与物理块长度相同，那么从逻辑地址到物理地址的转换就只涉及到从页号到块号的变换  2. 具有快表的地址变换机构 在基本地址变换机构内，每次完成从逻辑地址到物理地址的转换都需要一次额外的访存（查页表），存在优化的空间 考虑可能一段程序当中会频繁地对同一页进行访存，那么之前的地址变换就可以以某种形式缓存下来，避免频繁重复查找。于是引入快表的概念，即通过一个快表寄存器，缓存下来**最近的页表内容**，减少重复查找的访存。快表命中率越高，则效率越高  #### 4.5.3 两级页表与多级页表 * 分级页表 随着内存空间的不断增大，逻辑地址的长度也随之增加，在不改变页面大小的前提下（页面大小不宜过大，不然会导致巨大的索引时间开销），其页表大小会随之而增加。而页表有需要在内存当中连续存储，过大的页表将不利于内存空间的管理。 因此引入分段的概念，即设立多级页表，限制每一级页表的大小，通过多次访存，得到实际的物理地址 这里以二级页表为例，其页表组织形式如下所示：  由于涉及到多级页表，相应的地址变换机构也就存在多级  多级页表机制的引入，可以便于在内存空间内管理页表，但同时也会带来过多的访存频次（**每一级页表都需要一次访存转换**） * 倒置页表 由于引入了多级页表，同时因为每个进程都对应一个页表，那么相应的，就会导致内存中散落有大量的页表，具有浪费的现象 于是构造倒置页表，通过物理块号去标识进程号与页号，可以有效降低碎片化现象 | 块号 | 进程号 | 页号 | etc | | ------ | ------ | ----- | --- | | Block1 | Proc1 | Page1 | etc | ### 4.6 分段存储管理方式 机械的分页方式有可能把逻辑上在同一块区域的数据分散在多个页面当中，增大了不必要的访存开销。 | 段号 | 段长 | 基址 | | -------- | ---- | ------- | | Section1 | Len1 | StAddr1 | ## 5 虚拟存储器 ### 5.1 虚拟存储器概述 两种棘手的情况： * 作业所要求的内存空间非常大，超过了内存总容量，导致作业无法运行 * 有大量的作业要求运行，但内存有限，导致只能有少量的作业得到运行，大量的作业在外存上等待 #### 5.1.1 常规存储管理方式的特征和局部性原理 * 常规存储管理方式（连续，离散）的特征 * 一次性 都是**一次性**把进程整体装入内存（程序并不是开始运行时都需要所有的数据） * 驻留性 只要进程被分配了内存，除非他运行完毕，否则不会离开内存（程序执行完毕的部分依然留在内存中占用） * 局部性原理 * 程序在执行时将呈现出局部性规律 * **在一个较短的时间内**，程序的执行仅局限于某个部分（时间局部性），其所访问的存储空间也局限于某个区域（空间局部性） 综合上述，我们可以通过**部分装入**来解决内存空间不足的问题 #### 5.1.2 虚拟存储器的定义和特征 * 虚拟存储器的特征 * 多次性 * 对换性 * 虚拟性 #### 5.1.3 虚拟存储器的实现方法 1. 分页请求系统 * 硬件支持 * 请求分页的页表机制 * 缺页中断机构 * 地址变换机构 * 软件支持 * 实现请求分页的软件 2. 分段请求系统 * 分段请求 ### 5.2 请求分页存储管理方式 #### 5.2.1 请求分页中的硬件支持 * 足够容量的内存与外存 * 请求分页的页表机制 主要的数据结构是请求页表，用以将用户地址空间中的逻辑地址映射成内存空间中的物理地址 同时为了满足页面的换进换出的需要，在[分页系统页表机制](#451-页面与页表)的基础上添加了四个字段 | 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 | | ---- | -------- | ------------ | --------- | --------- | -------- | | Page | Block | Is_in_memory | Accessed? | Modified? | 0xffffff | * 缺页中断机构 * 在指令执行期间产生和处理中断信号 * **一条指令**在执行期间**可能产生多次**缺页中断 * 地址变换机构 在[分页系统地址变换机构](#452-地址变换机构)的基础上，添加了某些功能实现的  #### 5.2.2 请求分页中的内存分配 1. 最小物理块数的确定 为每个进程分配的物理块数越少，缺页率越高；物理块数越多，资源层面不允许。因此需要合理分配确定最小物理块数 2. 内存分配策略 | 固定分配 | 可变分配 | | -------------------------------- | -------------------------------- | | 进程运行过程中所分配的物理块不变 | 进程运行过程中所分配的物理块可变 | | 全局置换 | 局部置换| | -------- | -------- | | 可以对整个内存空间进行置换 | 只能对该进程分配的块进行置换 | 1. 固定分配 局部置换 2. 可变分配 全局置换 3. 可变分配 局部置换 3. 物理块分配算法 1. 平均分配算法 把系统中所有可供分配的物理块平均分配给各个进程 2. 按比例分配算法 根据进程的页面数来进行加权分配 假设系统中总可用的物理块数为$m$，每个进程的页面数为$S_i$，则每个进程能分到的物理块$b_i$为$\begin{align}b_i=\lceil\frac{S_i}{\sum_{i=1}^{n}S_i}\cdot m\rceil\end{align}$，注意$b_i$需要向上取整，并且必须大于操作系统规定的最小物理块数 3. 考虑优先权的分配算法 综合考虑平均分配以及优先权分配，将总可用物理块划分成两部分，一部分平均分配给所有进程，用以保证进程的基本需求，另一部分按照进程的优先级大小，加权分配，= #### 5.2.3 页面调入策略 1. 系统应何时调入所需页面 1. 预调页策略 操作系统能够预估未来需要用到哪些页面，预先提前调入，不产生中断，或很少产生中断 实际上非常难以实现 2. 请求调页策略 2. 系统从何处调入所需页面 1. 系统拥有足够的对换区 在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区，遇到缺页时直接从对换区调入，速度快 2. 系统没有足够的对换区 需要从文件区调入，涉及到索引访问，速度略低 换出未更改页面时直接丢弃，换入时从文件区调入；换出更改页面时则将其放到对换区，换入时从对换区调入 3. UNIX方式 首次加载时从文件区调入，否则从对换区调入。**UNIX允许页面共享** 3. 系统如何调入页面 见[地址变换机构图例](#521-请求分页中的硬件支持) #### 5.2.4 请求分页存储管理相关习题 某虚拟存储器系统的主存空间共16KB，分为16个页框（物理块），系统为每个用户进程分配3个实页框（物理块）并采用LRU页面置换策略。设T时刻用户进程P的页表如下所示，P过去一段时间内的页面走向为 0 1 4 2 0 5 1 3 6 3 0 6，若T时刻进程P访问逻辑地址0A55，请给出该逻辑地址的对应物理地址。 ### 5.3 页面置换算法（imp） * 根据[局部性原理](#511-常规存储管理方式的特征和局部性原理)，我们可以知道**部分装入**有助于解决内存空间不足的问题，但在内存空间不足的时候，系统选择哪一页的程序或数据送到磁盘的对换区中所使用的页面置换算法非常重要，将直接影响到系统的性能 1. 最佳（Optimal）置换算法 * 每次选择的淘汰页面都是以后永不使用或是未来的很长的一段时间内不使用的页面 * 可以保证最低的缺页率，但由于人们无法预知那一个页面时未来不被访问的，因此该算法实际上无法实现，是一个理论上的算法 * 由于其计算出了理论最低缺页率，其通常被用来评价其他的页面置换算法的效果 * 缺页率=$\begin{align} \frac{Page_{Miss}}{Page_{Req}}\end{align}$ 2. 先进先出（First-In-First-Out FIFO）页面置换算法 * 总是淘汰最先进入内存的页面 * 实现简单，只需要借助一个FIFO队列即可实现，但其实与进程实际运行的规律不相适应 3. 最近最久未使用（Latest-Recent-Unused LRU）算法 * 总是淘汰最近最久未被使用的页面 * 性能较好，但实现较为复杂，需要借助栈和寄存器，也会产生额外的时间开销（但通常值得，因为其缺页率远低于FIFO） * LRU的硬件支持 * 寄存器法 为每一个页面都提供一个寄存器，每过一个时间周期都自动向左移位，而每被访问一次都置寄存器的最高位为1，因此寄存器内值最小（非0）的页面，就是最近最久未使用的页面 * 栈法 每当进程访问一个页面时，都将该页面从栈内弹出，并压入栈顶，因此栈顶始终是最新被访问的页面，而栈底则是最久未被访问的页面 4. 时钟（CLOCK）置换算法 * 虽然LRU的性能较高，但其时空开销较大，不便于实现，因此人们尝试去用相对简化的方法去接近LRU的性能 1. 简单的CLOCK置换算法 * 在内存中为每一个页面都配置一个使用位（Used Bit） * 当页面装入内存或被引用时，其UB被置为1 * 系统将置换范围内的所有页面组成过一个循环队列，并设置一个扫描指针 * 未进行页面置换时，扫描指针总是指向上一次进行页面置换时被置换页面的所在位置的下一个位置 * 当需要进行页面置换时，系统移动扫描指针，搜索各页面 * 如果扫描到页面的UB为1，则将该UB设为0，继续搜索 * 如果扫描到页面的UB为0，则置换该页面，停止搜索 2. 改进的CLOCK置换算法 * 系统把一个页面移出内存时，如果该页面在驻留内存期间未被改动过，那么就不必将其实际上写入辅存，而可以直接复用辅存中已有的部分 * 每个页面在使用位（Used Bit）的基础上还添加了一个修改位（Modified Bit） 可以得到以下四种组合 * 1类（U=0,M=0），表示该页最近未被访问，未被修改，最佳淘汰页 * 2类（U=0,M=1），表示该页最近未被访问，但已被修改，不是最佳淘汰页 * 3类（U=1,M=0），表示该页最近已被访问，但未被修改，有可能被再次访问到 * 4类（U=1,M=1），最近已被访问且被修改，该页可能再被访问 * 每次循环依次优先淘汰1类，2类，3类页面 ### 5.4 抖动和工作集 #### 5.4.1 多道程序度与抖动 * 多道程序度与处理机的利用率 * 人们希望系统中能够运行更多的进程，即增加多道程序度以提高处理机的利用率 * 初期增加进程数时，可以有效提高CPU的利用率，但随着进程数过度地增加，每个进程所能得到的物理块越来越少，操作系统将会耗费大量的资源在缺页中断的处理上，会降低CPU地利用率，就叫“抖动”现象  * 产生抖动的原因 * 发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求。 #### 5.4.2 工作集 * 工作集的基本概念 * 进程发生缺页率的时间间隔与进程所获得的物理块数有关  * 工作集的定义 * 利用一个时间窗口，记录在一个过去的时间间隔内，进程实际访问的页面的集合。以便用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似 #### 5.4.3 抖动的预防方法 1. 采用局部置换策略 2. 把工作集算法融入处理机调度内 3. 使用L=S准则调借缺页率 L是缺页之间的平均时间 S是平均缺页服务时间 若L远大于S，则说明缺页很少，可以适当引入作业，反之则说明缺页大幅发生，需要控制作业。而当L与S接近时，说明进程调度良好 4. 选择暂停的进程 ### 5.5 请求分段存储管理方式 * 待补 ## 6 输入输出系统 ### 6.1 I/O系统 * 设备管理的主要功能 * 设备分配 * * 设备映射 * 逻辑设备到物理设备的映射 * 设备驱动 * 在操作系统更底层，辅助操作系统与设备交互 * I/O缓冲区的管理 * I/O系统的组成 * I/O设备$\rightarrow$控制器$\rightarrow$I/O通道c$\rightarrow$系统总线$\rightarrow$处理机与内存 * 附图 #### 6.1.1 I/O设备 * I/O设备的类型 * 按传输速率分类 * 低速：几-数百字节每秒。键盘鼠标 * 中速：数千-数万字节每秒，打印机。扫描仪 * 高速：数百千-数兆每秒以及更高。磁盘 * 按信息交换的单位分类 * 块设备：以数据块为单位访问。磁盘 * 传输速率高 * 可寻址，DMA * 字符设备：以字符为单位。键盘鼠标 * 传输速率低 * 按设备的共享属性分类 * 独占设备 * 共享设备 * 虚拟设备 * 设备与控制器之间的接口 *  * 如设备与麦克风之间的数据交互，控制器就需要辅助实现包括串并转换，模数转换在内的多种处理 #### 6.1.2 设备控制器 * 设备控制器是实现主机与设备交互的关键部分 * 设备控制器的主要功能 * 接收和识别命令 * 数据交换 * 表示和报告设备的状态 * 地址识别 * 数据缓冲 * 差错控制 * 设备控制器的组成 * 附图 * I/O系统的层次结构  #### 6.1.3 I/O通道 * I/O通道是一种特殊的处理机，它拥有执行I/O指令的能力，用来辅助处理机，完成I/O的工作 * 通道类型 * 字节多路通道 轮转 * 数组选择通道 独占 * 数组多路通道 * 通道的瓶颈问题 * 由于I/O通道，控制器都是一带多的情形，那么设备损坏会导致子设备均不能使用 * 引入多通路I/O系统，利用通道环路，多备选路径，完成损坏设备的冗余 #### 6.1.4 总线系统 ### 6.2 I/O控制方式 #### 6.2.1 程序I/O方式 即有一个程序不断检测I/O设备的状态，在程序I/O方式中，由于CPU的高速性和IO设备的低速性，致使CPU的绝大部分时间都处于等待IO设备完成数据IO的循环测试中，造成对CPU的极大浪费  #### 6.2.2 中断I/O方式 由设备控制器去完成等待查询就绪的事宜，并通过中断方式通知CPU处理，可以极大减少对CPU时间的浪费 #### 6.2.3 DMA I/O方式 传输数据块（必须以块形式，如果是字符型则使用中断I/O，如键盘）**直接进入内存或相反**，CPU只需要在每个数据块读取开始时和即将结束时才干预，进一步地减少了CPU对I/O的干预情况，提高了CPU与I/O设备的并行操作程度 #### 6.2.4 I/O通道控制方式 在DMA的形式上，进一步发展，他可以进一步减少对CPU的干预，即把对每**一个**数据块的读写为单位的干预，减少为对**一组**数据块的读写时才干预 需要借助通道程序 | 操作 | P（通道程序结束位） | R（记录结束位） | 计数 | 内存地址 | | ----- | ------------------- | --------------- | ---- | -------- | | WRITE | 0 | 0 | 80 | 813 | | WRITE | 0 | 0 | 140 | 1034 | | WRITE | 0 | 1 | 60 | 5830 | | WRITE | 0 | 1 | 300 | 2000 | | WRITE | 0 | 0 | 250 | 1850 | | WRITE | 1 | 1 | 250 | 720 | ### 6.3 缓冲管理 #### 6.3.1 缓冲的引入 * 缓和CPU与I/O设备间速度不匹配的矛盾 * 减少对CPU的中断频率，放宽对CPU中断响应时间的限制 * 提高CPU和I/O设备之间的并行性 #### 6.3.2 单缓冲与双缓冲 $T$为输入缓冲区的时间，$M$为CPU读取缓冲区数据的时间，$C$为CPU处理数据的时间 * 单缓冲区结构内，系统对每一块数据的平均处理时间为$max(C,T)+M$  * 双缓冲区结构内，I/O读写与CPU读写可以并行进行，可以粗略的认为，系统对每一块数据的平均处理时间为$max(C,T)$，  #### 6.3.3 循环缓冲 * 分别设立$Next_{in}$与$Next_{get}$指针，$Next_{in}$指针永远指向空的缓冲区（首写地址），$Next_{get}$指针永远指向有数据的缓冲区（首读地址） * 另有以$Currnet$工作指针，完成放入和提取的操作  * 凡是一对生产消费者都需要维护这样的一个缓冲循环队列，内存开销很大，并且也会造成一定程度的浪费 #### 6.3.4 缓冲池 * 与循环缓冲由用户进程维护相反，缓冲池高度封装缓冲功能，由操作系统统一管理，并提供给用户进程使用 * 缓冲池的组成 * 空闲缓冲区emq * 装满输入数据的缓冲区inq * 装满输出数据的缓冲区otq * 收容输入/输出寄存器 hin/hout (house) * 提取输入/输出寄存器 sin/sout (seek) ### 6.4 设备分配 #### 6.4.1 设备分配中的数据结构 1. 设备控制表DCT（Device Control Table）  2. 控制器表COCT（Controler Control Table）  3. 通道表CHCT（Channel Control Table）  至此，就已经完成了设备$\rightarrow$控制器$\rightarrow$通道的整体关联 4. 系统设备表SDT（System Device Table）  操作系统通过查SDT，就可以完整得到和一个设备有关的所有信息 5. 逻辑单元表LUT（Logical Unit Tabble）  用以实现逻辑设备名到物理设备名之间的映射 #### 6.4.2 假脱机系统（SPOOLing） * 系统引入 * 为了缓和CPU的高速性与I/O设备低速性间的矛盾而引入了脱机输入、 脱机输出技术 * 事实上， 当系统中引入了多道程序技术后，完全可以利用其中的一道程序，来模拟脱机输入时的外围控制机功能，把低速I/O设备上的数据传送到高速磁盘上；再用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上 * 系统组成与原理： * 输入井与输出井 * 输出缓冲区与输出缓冲区 * 输入进程和输出进程 * 井管理程序 *  * 特点： * 提高了I/O的速度 * 将独占设备改造为共享设备 * 实现了虚拟设备功能 * 一个经典的SPOOLing应用——打印机系统 * 磁盘缓冲区 * 打印缓冲区 * 假脱机管理进程与假脱机打印进程 * 过程 1. 由输出进程在输出井中为之申请一个空闲磁盘块区， 并将要打印的数据送入其中 2. 输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中， 再将该表挂到请求打印队列上 ### 6.5 设备处理 * 设备驱动程序 * 设备驱动程序的功能 * 接收由I/O进程发来的命令和参数， 并将命令中的抽象要求转换为具体要求 * 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式 * 发出I/O命令 * 及时响应由控制器或通道发来的中断请求 * 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序 * 设备驱动程序的特点 * 驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序 * 驱动程序与设备控制器和I/O设备的硬件特性紧密相关， 因而对不同类型的设备应配置不同的驱动程序 * 驱动程序与I/O设备所采用的I/O控制方式紧密相关 * 由于驱动程序与硬件紧密相关， 因而其中的一部分必须用汇编语言书写 * 设备驱动程序的过程 1. 将抽象要求转换为具体要求 2. 检查I/O请求的合法性 3. 读出和检查设备的状态 4. 传送必要的参数 5. 工作方式的设置 6. 启动I/O设备 ### 6.6 磁盘存储器管理（imp） #### 6.7.1 磁盘简述 * 基本概念 1. 磁道 以盘片中心为圆心，用不同的半径，划分出不同的很窄的圆环形区域，称为磁道。 2. 柱面 上下一串盘片中，相同半径的磁道所组成的一个圆柱型的环壁，就称为柱面。 3. 扇区 磁盘上的每个磁道被等分为若干个弧段，这些弧段便是磁盘的扇区.扇区是磁盘最小的物理存储单元 4. 磁盘簇（windows） windows将相邻的扇区组合在一起，形成一个簇，然后再对簇进行管理 5. 寻道时间 磁头从开始移动到移动到数据所在磁道所需要的时间 6. 旋转延迟  * 磁盘的类型 * 固定头磁盘 每条磁道上均有一个读/写头，读写数据时不需要移动磁头，并且可以实现并行读/写 * 移动头磁盘 每个盘面只有一个磁头，读写数据时磁头需要不断移动，只能串行读/写 * 磁盘的访问时间 * 寻道时间$T_{S(seek)}$ 把磁头移动到指定磁道上的时间 设启动磁臂的时间为$s$，磁头移动1条磁道所需的时间为$m$ 则移动$n$条磁道所需的$T_s=m\cdot n+s$ $m$通常小于0.2ms，$s$约为2ms，硬盘的寻道时间大致为5-30ms数量级 * 旋转延迟时间$T_{\tau}$ 指定扇区旋转到磁头下所经历的时间 对于5400r/min的磁盘，每转需时11.1ms，平均$T_{\tau}$为5.55ms #### 6.7.2 磁盘调度 1. 先来先服务FCFS 根据访问请求的到达顺序，按序完成访问 2. 最短寻道时间优先SSTF 因为移动距离（磁道数）与寻道时间息息相关，因此按需移动距离进行排序 与进程调度的SJF类似，容易出现饥饿现象 3. 扫描算法SCAN SSTF算法虽然能获得较好的寻道性能， 但却可能导致某个进程发生"饥饿"现象 在SSTF的基础上，可以指定始终按访问的磁道数递增或递减的次序进行访问（到达临界后可以选择循环归0或原路返回） ## 7 文件管理 ### 7.1 文件和文件系统 #### 7.1.1 文件、记录和数据项 1. 数据项 * 基本数据项，用于描述一个对象的某种属性的字符集，是数据组织中可以被命名的最小数据单位 * 组合数据项，由若干个基本数据项组成 2. 记录 * 记录是一组相关数据项的集合，用于描述一个对象在某方面的属性 3. 文件 * 文件是指，由创建者所定义的，具有文件名的一组相关记录的集合 * 可分为有结构文件（Readable/Visible）和无结构文件（Binary/Stream）两种 * 文件的属性通常可以包括 * 文件类型 * 文件长度 * 文件的物理位置 * 文件的创建时间 * etc... #### 7.1.2 文件类型和文件系统模型 * 文件类型 * 按用途分类 1. 系统文件 2. 用户文件 3. 库文件 * 按文件中数据的形式分类 1. 源文件(.c) 2. 目标文件(.o) 3. 可执行文件(.exe) * 按存取控制属性分类 1. 只执行文件 2. 只读文件 3. 读写文件 * 文件系统模型 用户$\rightarrow$文件系统接口$\rightarrow$对对象操纵和管理的软件的集合$\rightarrow$对象及其属性 * 对象及其属性 文件管理系统管理的对象有 1. 文件 2. 目录 3. 磁盘存储空间 * 对对象操纵和管理的软件的集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的 1. 对文件存储空间的管理 2. 对文件目录的管理 3. 用于将文件的逻辑地址转换为物理地址的机制 4. 对文件读和写的管理 5. 对文件的共享与保护 6. etc... * 文件系统的接口 为了方便用户使用文件系统，文件系统通常向用户提供简便易行的一些接口 #### 7.1.3 文件操作 1. 创建文件 2. 删除文件 3. 读文件 4. 写文件 5. 截断文件 6. 设置文件的读/写位置 ### 7.2 文件的逻辑结构 * 文件的逻辑结构，是指用户角度出发，看到的文件存储组织形式 * 文件的物理结构，又称为文件的存储结构，是指文件在外存上的存储组织形式 #### 7.2.1 文件逻辑结构的类型 1. 有结构文件 1. 定长记录 2. 变长记录 3. 顺序文件 4. 索引文件 5. 索引顺序文件 2. 无结构文件 1. 流式文件 #### 7.2.2 顺序文件 #### 7.2.3 索引文件 ### 7.3 外存的分配方式 * 连续分配 * 优点： * 顺序访问容易 * 顺序访问速度快 * 缺点 * 要求有连续的存储空间 * 必须事先知道文件的长度 * 链接分配 * 隐式链接 * 内含指针 * 显式链接 * 外置文件控制块（File Control Block，FCB） * 优点 * 比较灵活 * 缺点 * 存在空间浪费 * 访问慢，需要频繁的磁盘寻道 * 混合式索引 ### 7.4 目录管理 ### 7.5 文件存储空间的管理 ### 7.6 文件共享和文件保护 ### 7.7 数据一致性控制