操作系统

1、绪论

考纲内容

• 操作系统基本概念
• 操作系统的发展历程
• 程序运行环境
  • CPU运行模式：内核模式与用户模式
  • 中断和异常的处理：系统调用
  • 程序的链接与装入：程序运行时内存映像与地址空间
• 操作系统结构
  • 分层、模块化、宏内核、微内核、外核
• 操作系统引导
• 虚拟机

操作系统基本概念

• 操作系统的概念
  • 操作系统：
    • 是指控制和管理整个计算机系统的硬件与软件资源，操作系统是计算机系统中最基本的系统软件，
    • 组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口环境的程序集合；
  • 计算机系统大致可分为4部分：硬件、操作系统、应用程序和用户。
  • 操作系统充当计算机硬件与用户之间的中介；
• 操作系统的特征
  • pre：操作系统与其它系统软件和应用程序软件有很大的不同，它有如下四种基本特征：
    • 并发
      • 多个事件在同一时间间隔内发生，引入进程的目的就是使程序能并发执行，
      • 单处理机同一时刻只能有一道程序执行，因此宏观上多个程序仍然是分时交替执行的，操作系统的并发性是通过分时实现的；
      • 时间间隔(并发)，同一时刻(并行)；
      • 并发和共享是操作系统两个最基本的特征，两者之间互为存在条件，资源共享是以程序的并发为条件的；
    • 共享
      • pre：共享是指系统中的资源可供内存中多个并发执行的进程共同使用，共享可分为以下两种：
      • 互斥共享方式：
        • 一段时间内只允许一个进程访问该资源，进程访问前先提出请求，若资源此时空闲，则分配给进程使用，若非空闲则其它提出请求的进程就等待；
        • 把这种一段时间内只允许一个进程访问的资源被称为临界资源，这些资源都被互斥地共享，例如打印机；
      • 同时访问方式：
        • 系统中还有一类资源，这类资源允许在一段时间内由多个进程同时访问，
        • 同时指的宏观上，微观上这些进程是在同一时刻交替地对资源进行访问，既分时共享，例如磁盘，一些用可重入码编写的文件也可被同时共享；
    • 虚拟
      • 是指把一个物理上的实体(实际存在的)变为若干个逻辑上(虚的)的对应物，这种技术称为虚拟技术；
      • 操作系统用多种虚拟技术来实现：虚拟处理器、虚拟内存和虚拟外部设备；
        • 虚拟处理器技术：是利用多道程序设计技术，来分时使用一个处理器，把一个物理上的CPU虚拟为多个逻辑CPU，使每个终端用户都感觉有一个CPU在专门为它服务；
        • 虚拟存储器技术：把一台机器的物理存储器变成虚拟存储，以便扩充存储器的容量；这是用户能感觉到内存容量是虚的；
        • 虚拟外部设备技术：将一台物理I/O设备虚拟为多台逻辑上的I/O设备，使原来的临界资源变成一段时间内允许多个进程同时访问的共享设备，例如打印机队列；
      • 操作系统的虚拟技术可归纳为：
        • 时分复用技术，例如处理器的分时共享；
        • 空分复用技术，例如虚拟存储器；
    • 异步
      • 多道程序并发执行，进程的执行并不是一贯到底的，而是走走停停，它以不可预知的速度向前推进，这就是进程的异步性。
      • 正常IO操作指的是进程碰到IO等待就让出CPU，让进程从运行态变成阻塞态，异步IO指由程序自己控制，碰到IO操作不会让出CPU，可以避免上下文切换的损耗；
• 操作系统的目标和功能
  • 作为计算机系统资源的管理者
    • 处理机管理：
      • 处理机的分配和运行都以进行(或线程)为基本单位；
      • 进程管理的主要任务：进程何时创建、何时销毁、如何管理、如何避免冲突、合理共享；
    • 存储管理：
      • 提高内存的利用率，主要包括内存分配与回收、地址映射、内存保护与共享、内存扩充等功能；
    • 文件管理：
      • 计算机的中的信息都是以文件的形式存在的，操作系统中的文件系统负责文件的管理，
      • 文件管理包括，文件存储空间的管理、目录管理及文件读写管理和保护等；
    • 设备管理：
      • 主要任务是完成用户的I/O请求，方便用户使用各种设备，并提高设备的利用率，
      • 主要包括，缓冲管理、设备分配、设备处理和虚拟设备等功能；
  • 作为用户与计算机硬件系统之间的接口
    • 命令接口
      • 用户利用这些操作命令来组织和控制作业的执行；
      • 用命令接口按作业控制方式的不同主要方式有两种，联机控制方式和脱机控制方式
        • 联机命令接口(交互式命令接口)：适用于分时或实时系统的接口，用户通过终端输入操作命令，向系统提出各种服务请求，强调交互性；
        • 脱机命令接口(批处理命令接口)：适用于批处理任务，由一组作业控制命令组成，批处理shell脚本啊；
    • 程序接口
      • 由一组系统调用组成，用户通过在程序中使用这些系统调用来请求操作系统为其提供服务，如使用外部设备、申请分配和回收内存等；
      • GUI是图形接口，GUI最终是通过调用程序接口实现的，图形接口所调用的命令是操作系统的一部分；
      • 编程人员可以使用它们来请求操作系统服务
  • 操作系统实现了对计算机资源的扩充
    • 没有任何软件支持的计算机称为裸机，是构成计算机的物质基础，用户面前使用的计算机系统是经过若干层改造的计算机，
    • 操作系统就是将裸机改造成功能更强、使用更方便的机器；
    • 通常把覆盖了软件的机器称为虚拟机，有两种虚拟机，1是直接在裸机上安装虚拟机系统，2是在操作系统之上的虚拟机软件，通过操作系统进行系统调用；

操作系统发展历程

• 手工操作阶段：独占计算机资源，资源利用率底；
• 批处理阶段(os开始出现)：高效率利用CPU的资源，宏观上的并行、微观上串行；
• 分时操作系统
  • 所谓分时技术，
    • 是指把处理器的运行时间分成很短的时间片，按时间片轮流把处理器分配给不同进程使用，计算速度很快，作业运行轮转得也很快；
    • 分配给某个作业的时间片用完还没有完成作业，则该作业停止运行，把处理器让给其它作业处理，等待下一轮再继续运行；
  • 多用户同时共享一台主机，通过终端连接在主机上，用户同时与主机进行交互操作而互不干扰
  • 分时系统的主要特征如下：
    • 同时性：多用户通过终端同时操作，也称多路性；
    • 交互性：多用户通过终端采用人机对话的方式进行交互；
    • 独立性：系统中多个用户互相独立，互不干扰，单个用户感觉不到别人在使用这台计算机；
    • 及时性：用户请求能在短时间内获得响应，采用时间片轮转方式使一台计算机同时为多个终端服务；
  • 不同于多道批处理系统，多道批处理系统作业自动控制无人工干预的系统，而分时系统实现了人机交互的系统；
• 实时操作系统
  • 为了能在某个时间限制内完成某些紧急任务，而不需要以时间片排队，诞生了实时操作系统，时间限制可分为两种：
    • 硬实时操作系统：某个动作必须绝对地在规定的时间内完成(规定的时间范围发生)，用户飞行器的飞行控制系统；
    • 软实时操作系统：能够接受偶尔违反时间规定且不会引起任何永久性的损害；
  • 在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并严格在规定时间内处理完，主要特点是及时性和可靠性；
• 网络操作系统和分布式计算机系统
  • 网络操作系统：
    • 把计算机网络中的各台计算机有机结合起来，提供一种统一、经济而有效的使用各台计算机的方法。
    • 最主要特点是网络中各种资源的共享及各台计算机之间的通信；
    • 服务于计算机网络，集中控制方式，集群的管理n台计算机；
  • 分布式计算机系统：
    • 由多台计算机组成并满足以下条件的系统
    • 系统中任意两台计算机通过通信方式交换信息，每天计算机具有同等地位，没有主机和从机的区分，每台计算机上的资源所用用户共享；
    • 任何工作都可以分布在几台计算机上，由它们并行工作，协同完成，特点是分布式、并行性；
    • 建立在网络操作系统上，控制功能均为分布式，与网络操作系统的本质不同是，分布式计算机系统中的若干计算机协同完成同一任务；
• 个人计算机操作系统
  • 主要用于文字处理、电子表格、游戏，常见的有Windows、Linux、MacOs
• 嵌入式操作系统、服务器操作系统、智能手机操作系统；

操作系统的运行环境

• 处理器运行模式
  • CPU执行两种不能类型的程序
    • 操作系统内核程序，是管理程序，可以执行一些特权指令，运行在内核态；
    • 用户程序：应用程序，不能执行特权程序，运行在用户态；
    • 用户程序向操作系统请求服务是通过使用访管指令，从而产生一个中断事件将由操作系统转换为内核态
  • 特权指令：不允许用户直接执行，如I/O指令、中断指令，存取内存保护的寄存器，程序状态寄存器；
  • 非特权指令：允许用户直接使用的指令，它不能直接访问系统中的软硬件资源，仅限于访问用户的地址空间，防止对系统造成破坏
  • 时钟管理：在计算机的各种部件中，时钟是最关键的设备，首要功能是计时，向用户提供系统时间。另外通过时钟中断的管理，可以实现进程的切换；
  • 中断机制：
    • 中断技术是提高多道程序运行中CPU的利用率，而且主要是针对外部设备的；
    • 有多种中断类型，是操作系统各项操作的基础，例如键盘或鼠标信息的输入、进程的管理和调度、设备驱动、文件访问等；
    • 现代计算机是靠中断驱动的软件，中断机制中只有一小部分属于内核，它们负责保护和恢复中断现场，转移控制权相关的处理程序，提供系统的并行处理能力；
  • 原语：
    • 按层次结构设计的操作系统中，底层都是一些可被调用的公用小程序，它们各自完成一些规定的操作，这些程序的运行具有原子性，其操作只能一气呵成；
    • 这些程序运行时间都较短，而且调用频繁，处于操作系统的最底层，是最接近硬件的部分；
    • 定义原语的直接方法是关闭中断，动作完成后再打开。系统中的CPU切换、进程通信、设备驱动等功能中的部分操作都可定义为原语，是内核的一部分；
  • 系统控制的数据结构及处理：
    • 系统中的数据结构：用来登记状态信息，例如：PCB、设备控制块、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表等等；
    • 系统中的一些基本操作，常见操作有以下3中：
      • 进程管理：进程状态管理、进程调度和分派、创建和销毁PCB等；
      • 存储器管理：存储器的空间分配与回收、内存信息保护程序、代码对换程序等；
      • 设备管理：缓冲区管理、设备分配和回收等；
  • 从上述内容可以了解，内核态指令包括系统调用类指令、时钟操作、中断和原语的操作指令；
• 中断和异常的概念
  • 内核态和用户态这两种工作状态如何切换，
    • 在内核态建立一些“门”，以便从用户态进入内核态，唯一能进入这些“门”的操作是通过中断或异常；
    • 发生中断或异常时，CPU会立即进入内核态，这是通过硬件实现的一种标识1(用户态)或0(内核态)，程序对资源的占有权释放这种行为就是通过中断实现；
  • 中断和异常的定义
    • 中断也称外中断，是指来自CPU执行指令外部的事件，例如设备发出的I/O结束中断，标识I/O处理已经完成。时钟中断，表示固定的时间片已到，让CPU处理计时任务；
    • 异常也称内中断(软中断)，是指来自CPU执行指令内部的事件，例如非法操作码、地址越界、运算溢出、虚拟内存的缺页中断。异常不能屏蔽，出现就要立即处理；
    • 外中断和内中断的区别：外部中断可屏蔽中断INTR，NMI不可屏蔽，内中断一般是硬件发出或系统故障；
  • 中断和异常的分类
    • 外中断可分为，可屏蔽中断由INTR线发出，和不可屏蔽中断NMI先发出的中断请求，通常是紧急的硬件故障，如电源调电；
    • 异常可分为，故障(缺页中断)、自陷(事先安排好的异常事件)和终止(出现了使CPU无法继续执行的硬件故障，如控制器出错)，异常不能被屏蔽；
  • 中断和异常的处理过程
    • 当CPU在执行第i条指令时检测到一个中断，则CPU打断当前的用户程序，然后转到相应的中断或异常处理程序去执行；
    • 若中断或异常处理程序发现是不可恢复的致命错误，则终止用户程序。可恢复中断程序处理会后回到被打断的用户程序的第i条指令继续执行；
• 系统调用
  • 所谓系统调用，是指用户在程序中调用操作系统提供的一些子功能，系统调用可视为特殊的公共子程序；
  • 在用户程序中，凡是与资源有关的操作，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。
  • 通常系统调用命令有几十乃至上百条之多，大致按功能可分为以下几类：
    • 设备管理相关、文件管理相关、进程控制相关、进程通信、内存管理相关；
  • 系统调用对整个系统的影响非常大，所以必须由操作系统内核程序负责完成，要运行在内核态；

操作系统结构

• 分层法
  • 将操作系统分为若干层，每层只能调用相邻它的底层的功能和服务；
  • 现代操作系统几乎都是分层式的机构，操作系统的各项功能分别被设置在不同的层次上，
  • 内核是计算上配置的底层软件，它管理着系统的各种资源，是连接应用程序和硬件的一座桥梁；
• 模块化
  • 按功能划分为若干具有一定独立性的模块，并规定好各模块间的通信接口，模块-接口法；
  • 模块独立性越高，各模块间的交互就越少，系统的结构也就越清晰，模块的独立性主要右两个标准：
    • 内聚性：模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越好；
    • 耦合性：模块间相互联系和相互影响的程度。耦合度越低，模块独立性越好；
• 从操作系统的架构来划分，可分为宏内核和微内核
  • 宏内核
    • 也称单内核或大内核，系统主要功能模块作为一个紧密联系的整体运行在内核态，从而为用户程序提供高性能的系统服务，性能高；
    • Windows/IOS/Android/Linux/MacOS都是基于宏内核的架构；
    • 不过目前主要操作系统不是当年纯粹的宏内核架构了，而是广泛吸收了微内核架构的优点后糅合而成的混合内核；
  • 微内核
    • 微内核基本概念：
      • 微内核将操作系统划分为两大部分：微内核和多个服务器，微内核是指能实现操作系统最基本核心功能的小型内核，包括与硬件处理的紧密相关的部分；
      • 是指将内核中最基本的功能保留在内核，将那些不需要在内核态执行的功能放在用户态执行，划分成若干服务程序，从而降低内核设计的复杂性；
      • 操作系统绝大部分功能都放在微内核外的一组服务器(进程)中实现，他们的执行相互独立，之间的交互借助于微内核进行通信，如进程、存储、IO设备管理；
      • 只有微内核运行在内核态，其余模块都运行在用户态，这种设计的好处是方便扩展系统，目前谷歌和华为Fuchsia的鸿蒙OS都是基于微内核；
    • 微内核的基本功能
      • 微内核通常利用“机制与策略分离”的原来来构造OS，将与硬件紧密相关的部分放入微内核，微内核通常具有如下功能：
        • 进程(线程)管理：进程的切换和调度；
        • 低级存储器管理
        • 中断与陷入处理
        • 进程管理、存储管理以及IO管理的功能一分为二，属于机制很小的一部分放入微内核，而绝大部分放入微内核以外的各种进程中实现，属于C/S模式；
    • 微内核的特点
      • 扩展性和灵活性
      • 可靠性和安全性
      • 可移植性
      • 分布式计算：客户与服务器之间通信采用消息传递机制，这就使得微内核可以很好的支持分布式系统和网络系统；
    • 微内核的主要问题：需要频繁的在内核态与用户态之间进行切换，系统执行开销偏大，性能问题很大；
  • 宏内核与微内核的比较：宏内核适用桌面操作系统，微内核在实时、工业、航空及军事领域适用，这些领域都是关键任务，需要高度的可靠性；
• 外核
  • 在底层中，一种称为外核的程序在内核态中运行，它的任务是为虚拟机分配资源，并检查使用这些资源的企图，确保不会用到分配给他人的资源；
  • 外核机制的优点是减少了映射层，在其它虚拟机设计中，每个虚拟机都认为自己有磁盘的磁盘块号从0到最大编号，这样虚拟机监控程序就需要维护一张磁盘映射地址表；
  • 有了外核，这种重映射处理就不需要了。外核只需要记录已经分配给各个虚拟机的有关资源即可，外核只需要保持多个虚拟机之间不发生冲突就行；

操作系统引导

• 操作系统是一种程序，以数据的形式存放在硬盘中，操作系统引导是指通过程序识别硬盘分区上的操作系统，通过程序启动操作系统的过程；
• 常见操作系统的引导过程如下：
  • 激活CPU：激活CPU读取ROM中的boot程序，将指令寄存器置为BIOS(基本输入输出系统)的第一条指令，开始执行BIOS指令；
  • 硬件自检：启动BIOS程序后，先进行硬件自检，硬件有问题主板会发出不同含义的蜂鸣，自检后没有问题屏幕显示CPU、内存、硬盘等信息；
  • 加载带有操作系统的硬盘：硬件自检后BIOS开始读取Boot Sequence，把控制权交给启动顺序排在第一位的存储设备，然后CPU将存储设备引导扇区的内容加载到内存；
  • 加载主引导记录MBR：主引导记录MBR先识别硬盘分区，然后告诉CPU去硬盘的哪个分区去找操作系统，没找到启动设备就会死机；
  • 扫描硬盘分区表：主引导记录扫描硬盘分区表，进而识别含有操作系统的硬盘分区(活动分区)，开始加载硬盘活动分区，将控制权交个存储设备引导扇区的内容；
  • 加载分区引导记录PBR：读取活动分区的第一个扇区，寻找并激活分区根目录下用于引导操作系统的程序(启动管理器)；
  • 加载启动管理器：分区引导记录在磁盘中找到启动管理器后，加载启动管理器；
  • 加载操作系统
• 操作系统启动主要经过，两个程序和两块指令：
  • BIOS->CPU加载存储设备引导扇区的内容到内存->识别并加载(含有操作系统的)硬盘活动分区->启动管理器->操作系统启动；
  • 硬盘分活动分区和非活动分区，用特定的标识符区分，非活动分区是存普通文件的？

虚拟机

• 虚拟机的基本概念
  • 虚拟机是一台逻辑计算机，是利用虚拟化技术，为用户提供抽象的、统一的、模拟的计算环境，有两类虚拟化方法：
    • 第一类虚拟管理程序
      • 就像一个精简的操作系统，因为这个虚拟管理程序是唯一一个运行最高特权的程序，它在裸机上运行并且具备多道程序功能；
      • 虚拟机程序向上提供若干台虚拟机，这些虚拟机是裸机硬件的精确复制品，在不同的虚拟机上运行不同的操作系统；
      • 这类虚拟机也以用户态进程运行，由虚拟机管理程序执行内核态的命令；
    • 第二类虚拟管理程序
      • 是一个依赖操作系统分配和调度的程序，很像一个普通的进程，把自己伪装成具有CPU和各种设备的完整计算机；
    • 区别：感觉这两个虚拟机差不多，唯一的区别是裸机上是虚拟管理程序还是操作系统；

2、进程和线程

考纲内容-2

• 进程与线程

  • 进程与线程的基本概念：进程/线程的状态与转换
  • 线程的实现：内核支持的线程，线程库支持的线程
  • 进程与线程的组织与控制
  • 进程间通信：共享内存，消息传递，管道

• CPU调度与上下文切换

  • 调度的基本概念：调度的目标
  • 调度的实现
    • 调度器/调度程序(scheduler)
    • 调度的时机与调度方式(抢占式、非抢占式)
    • 闲逛进程
    • 内核级线程与用户级线程调度
  • 典型调度算法
    • 先来先服务调度算法：短作业（短进程、短线程）优先调度算法
    • 时间片轮转调度算法
    • 优先级调度算法
    • 高响应比优先调度算法
    • 多级队列调度算法
    • 多级反馈队列调度算法
  • 上下文及其切换机制

• 同步与互斥

  • 同步与互斥的基本概念
  • 基本的实现方法：软件方法、硬件方法
  • 锁：信号量、条件变量
  • 经典同步问题
    • 生产者-消费者问题
    • 读者-写着问题
    • 哲学家进餐问题

• 死锁

  • 死锁的基本概念
  • 死锁预防
  • 死锁避免
  • 死锁检测和解除

进程与线程

• 进程的概念
  • 在多道程序并发执行的过程中，它们失去了封闭性，并具有不可再现的特征。
  • 为此引入了“进程”的概念，以便更好的描述和控制程序的并发执行，实现OS的并发性和共享性(OS最基本的两个特征)；
  • 为每个程序配置了一个数据结构，称为进程控制块(PCB)，系统用PCB来描述进程的基本情况和运行状态，用PCB控制和管理进程；
  • 进程实体的由三块构成：程序段、相关数据段和PCB。所谓创建进程实际是创建实体中的PCB，而撤销进程实质是清除PCB；
  • 进程的特征：
    • 进程和程序是两个不同的概念；
    • 动态性：进程是程序的一次执行，有着创建、暂停、终止等过程，具有一定的生命周期，动态性是进程最基本的特征；
    • 并发性：多个进程同时存在于内存中，能在一段时间内同时运行，并发性是进程的重要特征，也是操作系统的重要特征；
    • 独立性：进程是系统进行资源分配和调度的基本单位，既“时间片”分配的基本单位；
    • 异步性：由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进，异步性会导致执行结果不可重现，为此必须在OS中配置相应的进程同步机制；
• 进程的状态与转换
  • pre：进程在其生命周期内，由于系统中各进程之间的相互制约及系统的运行环境的变化，使得进程的状态也在不断地发生变化，前3种是进程的基本状态。
  • 运行态：进程正在处理机上运行。在单处理机中，每个时刻只有一个进程处于运行态；
  • 就绪态：进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
  • 阻塞态：又称等待态，进程正在等待某一事件而暂停运行，即使处理机空闲，该进程也不能运行。系统通常将处于阻塞态的进程根据阻寨原因的不同，设置多个阻塞队列。
  • 创建态：进程正在被创建，尚未转到就绪态，创建进程需要多个步骤
    • 首先申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息;
    • 然后为该进程分配运行时所必须的资源;
    • 最后把该进程转入就绪态并插入就绪队列。
    • 但是，如果进程所需的资源尚不能得到满足，如内存不足，则创建工作尚未完成，进程此时所处的状态称为创建态。
  • 终止态：进程正从系统中消失，可能是进程正常结束或其他原因退出运行。进程需要结束运行时，系统首先将该进程置为终止态，然后进一步处理资源释放和回收等工作。
  • 5种进程状态的切换
    • 就绪态->运行态：处于就绪态的进程被调度后，获得处理机资源(分派处理机时间片)，于是进程由就绪态转换为运行态；
    • 运行态->就绪态：
      • 处于运行态的进程在时间片用完后，不得不让出处理机，从而进程由运行态转换为就绪态。
      • 此外，在可剥夺的操作系统中，当有更高优先级的进程就绪时，调度程序将正在执行的进程转换为就绪态，让更高优先级的进程执行；
    • 运行态->阻塞态：
      • 进程请求某一资源(如外设)的使用和分配或等待某一事件的发生(如 I/O 操作的完成)时，它就从运行态转换为阻塞态。
      • 进程从运行态变成阻塞态是主动的行为，而从阻塞态变成就绪态是被动的行为，需要其他相关进程的协助；
    • 阻塞态->就绪态：进程等待的事件到来时，如I/O操作结束或中断结束时，中断处理程序必须把相应进程的状态由阻塞态转换为就绪态。
• 进程的组成
  • pre：进程是一个独立的运行单位，也是操作系统进行资源分配和调度的基本单位。它由以下三分组成，其中最核心的是(PCB)
  • 进程控制块
    • 系统通过PCB对进程进行控制的过程如下；
      • 进程执行时：系统通过其PCB了解进程的现行状态信息，以便操作系统对其进行控制和管理；
      • 当操作系统欲调度某进程运行时：要从该进程的PCB中查出其现行状态及优先级；
      • 在调度到某进程后：要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据；
      • 进程在运行过程中：当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问PCB；
      • 当进程由于某种原因而暂停运行时：又需将其断点的处理机环境保存在PCB中；
      • PCB是进程实体的一部分，是进程存在的唯一标志，该结构创建之后常驻内存，任意时刻都可以存取，在进程结束时删除；
    • PCB中主要包括的信息：
      • 进程描述信息：
        • 进程标识PID：标志各个进程，每个进程都有一个唯一的标识号。
        • 用户标识符UID：进程归属的用户，用户标识符主要为共享和保护服务。
      • 进程控制和管理信息：
        • 进程当前状态：描述进程的状态信息，作为处理机分配调度的依据。
        • 进程优先级：描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机。
        • 代码运行入口地址，程序的外存地址，进入内存的时间，CPU占用时间，信号量使用；
      • 资源分配清单：用于说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入/输出设备信息，文件描述符，鼠标、键盘；
      • 处理机相关信息：
        • 也称CPU的上下文，主要指处理机中各寄存器的值。
        • 当进程处于执行态时，处理机的许多信息都在寄存器中，通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字。
        • 当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时，能从断点继续执行。
    • 各进程的PCB组织方式，为了方便进程的调度和管理，目前，常用的组织方式有两种：
      • 链接方式：将同一状态的PCB链接成一个队列,不同状态对应不同的队列，也可把处于阻塞态的进程的PCB，根据其阻塞原因的不同，排成多阻塞队列。
      • 索引方式：将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，同状态对应不同的索引表，如就绪索引表和阻塞索引表等。
  • 程序段：能被进程调度程序调度到CPU执行的程序代码段。 注意，程序可被多个进程共享，即多个进程可以运行同一个程序；
  • 数据段：一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。
• 进程控制
  • pre：在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位；
  • 进程的创建
    • 允许一个进程创建另一个进程，此时创建者称为父进程，被创建的进程称为子进程，子进程可以继承父进程所拥有的资源。
    • 当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，通常也会同时撤销其所有的子进程。
    • 在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。
    • 操作系统创建一个新进程的过程如下(创建原语):
      • 1 为新进程分配一个唯一的进程标识号，并申请一个空白PCB(PCB是有限的)。若PCB申请失败，则创建失败。
      • 2 为进程分配其运行所需的资源，如内存、文件、IO设备和CPU时间等(在PCB中体现)。这些资源或从操作系统获得，或仅从其父进程获得。
      • 3 初始化PCB，主要包括初始化标志信息、初始化CPU状态信息和初始化CPU控制信息，以及设置进程的优先级等。
      • 4 若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。
  • 进程的终止
    • 引起进程终止的事件主要有:
      • ①正常结束，表示进程的任务已完成并准备退出运行。
      • ②异常结束，表示进程在运行时，发生了某种异常事件使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O故障等。
      • ③外界干预，指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。
    • 操作系统终止进程的过程如下(终止原语):
      • 1 根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态。
      • 2 若被终止进程处于运行状态，立即终止该进程的执行，将处理机资源分配给其他进程。
      • 3 若该进程还有子孙进程，则应将其所有子孙进程终止。
      • 4 将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。
      • 5 将该PCB从所在队列(链表)中删除。
  • 进程的阻塞和唤醒
    • 正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等,
    • 进程便通过调用阻塞原语(Block)，使自己由运行态变为阻塞态，可见，阻塞态是一种进程自身主动行为
    • 阳塞原语的执行过程如下：
      • 1 找到将要被阴塞进程的标识号对应的PCB；
      • 2 若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行；
      • 3 把该PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程；
    • 唤醒原语的执行过程如下：
      • 当被阻塞进程所期待的事件出现时，如它所期待的I/O操作已完成或其所期待的数据已到达，由有关进程调用唤醒原语(Wakeup)，将等待该事件的进程唤醒；
      • 1 在该事件的等待队列中找到相应进程的PCB。
      • 2 将其从等待队列中移出，并置其状态为就绪态。
      • 3 把该PCB插入就绪队列，等待调度程序调度。
      • Block原语和Wakeup原语是一对作用刚好相反的原语，必须成对使用。避免阻塞进程因不能被唤醒而永久地处于阻塞状态。
• 进程的通信
  • pre：进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式，高级通信方法主要有以下三类
  • 共享存储：
    • 在通信的进程之间存在一块可直接访问的共享空间,通过对这片共享空间进行写/读操作实现进程之间的信息交换；
    • 在对共享空间进行写/读操作时，需要使用同步互斥工具(如 P操作、V操作)，对共享空间的写/读进行控制。
    • 共享存储又分为两种：
      • 低级方式的共享是基于数据结构的共享；
      • 高级方式的共享则是基于存储区的共享；
      • 操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。
  • 消息传递
    • 在消息传递系统中，若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。
    • 进程通过系统提供的发送消息和接收消息两个原语进行数据交换，是当前应用最广泛的进程间通信机制。
    • 在微内核操作系中，微内核与服务器之间的通信就采用了消息传递机制。
    • 由于该机制能很好地支持多处理机系统、分布式系统和计算机网络,因此也成为这些领域最主要的通信工具。
    • 两种通信方式：
      • 1 直接通信方式。发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息；
      • 2 间接通信方式、发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息，这种中间实体一般称为信箱，该通信方式广泛应用于计算机网络中；
  • 管道通信
    • 管道道信允许两个进程按生产者-消费者方式进行通信，生产者向管道的一端写，消费者从管道另一端读；
    • 为了协调双方的通信，管道机制必须提供三方面的协调能力：互斥、同步和确定对方的存在。
    • 在Linux中，管道是一种使用非常频繁的通信机制。
    • 从本质上说，管道也是一种文件，但它又和一般的文件有所不同，管道可以克服使用文件进行通信的两个问题，具体表现如下：
      • 1 限制管道的大小，管道文件是一个固定大小的缓冲区，这使得它的大小不像普通文件那样不加检验地增长，在Linux中该缓冲区的大小为4KB。管道变满后将会被阻塞；
      • 2 解决了read()调用返回文件结束的问题，读进程也可能工作得比写进程快。当所有管道内的数据已被读取时，管道变空。一个随后的read()调用将默认地被阻塞；
    • 管道只能由创建进程所访问，当父进程创建一个管道后，子进程也继承父进程的管道，并使用它来与父进程进行通信。
    • 注意：从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据。普通管道只允许单向通信，若要实现父子进程双向通信，则需要定义两个管道。
• 线程和多线程模型
  • 线程的基本概念
    • 引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；
    • 而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
    • 线程最直接的理解就是“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。
    • 一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。
    • 线程也有就绪、阻塞和运行三种基本状态。
    • 引入线程后，进程的内涵发生了改变，进程只作为（除CPU外的）系统资源的分配单元，而线程则作为处理机的分配单元。
    • 由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。
  • 线程与进程的比较
    • 调度：线程切换的代价远低于进程。在同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换；
    • 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且一个进程中的多个线程之间亦可并发执行、甚至不同进程中的线程也能并发执行；
    • 拥有资源：进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源）；
    • 独立性：某进程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及址进行相互之间的合作而创建的，它们共享进程的地址空间和资源。
    • 系统开销：
      • 线程创建或撤销比进程的开销要小很多，比如：分配或回收进程控制块PCB及内存空间、IO设备等；
      • 类似地，在进程切换时涉及进程上下文的切换，而线程切换时只需保存和设置少量寄存器内容，开销很小。
      • 此外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。
    • 支持多处理机系统：对于传统单线程进程，不管有多少处理机，进程只能运行在一个处理机上。对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行。
  • 线程的属性
    • 多线程操作系统中的进程已不再是一个基本的执行实体，但它仍具有与执行相关的状态；
    • 所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。线程的主要属性如下：
      • 1 线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态。
      • 2 不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。
      • 3 同一进程中的各个线程共享该进程所拥有的资源；
      • 4 线程是处理机的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU，在多CPU的计算机系统中，各线程可同时占用不同的CPU，若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。
      • 5 一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。
  • 线程的状态与切换
    • 与进程一样，各线程在运行时也具有执行状态、就绪状态、阻塞状态，这个三个状态之间的转换和进程基本状态之间的转换是一样的；
  • 线程的组织与控制
    • 线程控制块
      • 与进程类似，系统也为每个线程配置一个线程控制块TCB，用于记录控制和管理线程的信息。线程控制块通常包括:
        • ①线程标识符；
        • ②一组寄存器，包括程序计数器、状态寄存器、通用寄存器；
        • ③线程运行状态，用于描述线程正处于何种状态；
        • ④优先级；
        • ⑤线程专有存储区，线程切换时用于保存现场等；
        • ⑥堆栈指针，用于过程调用时保存局部变量及返回地址等；
        • 同一进程中的所有线程都完全共享进程的地址空间和全局变量。一个线程可以读、写或甚至清除另一个线程的堆栈；
    • 线程的创建
      • 线程也是具有生命期的，它由创建而产生，由调度而执行，由终止而消亡。每个线程创建后将返回一个线程标识符。
    • 线程的终止
      • 当一个线程完成自己的任务后，或线程在运行中出现异常而要被强制终止时，由终止线程调用相应的函数执行终止操作。
      • 但是有些线程(主要是系统线程)一旦被建立，便一直运行而不会被终止。线程被终止后并不立即释放它所占有的资源；
  • 线程的实现方式
    • 用户级线程
      • 在用户级线程中，有关线程管理(创建、撤销和切换等)的所有工作都由应用程序在用户空间中完成，内核意识不到线程的存在；
      • 通常，应用程序从单线程开始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程；
      • 对于设置了用户级线程的系统，其调度仍是以进程为单位进行的，各个进程轮流执行一个时间片。
      • 假设进程A包含1个用户级线程，进程B包含100个用户级线程，这样进程A的运行时间将是进程B中各线程运行时间的100倍，因此对线程来说实质上是不公平的。
      • 这种实现方式的优点如下:
        • ①线程切换不需要转换到内核空间，节省了模式切换的开销。
        • ②调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法。
        • ③用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分。
      • 这种实现方式的缺点如下:
        • ①系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞。
        • ②不能发挥多处理机的优势，内核每次分配给进程的仅有一个CPU，因此进程中仅有一个线程能执行；
    • 内核级线程
      • 内核空间也为每个内核级线程设置一个线程控制块TCB，内核根据该控制块感知某线程的存在，并对其加以控制;
      • 这种实现方式的优点如下:
        • ①能发挥多处理机的优势，内核能同时调度同一进程中的多个线程并行执行。
        • ②如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程。
        • ③内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小。
        • ④内核本身也可采用多线程技术，可以提高系统的执行速度和效率。
      • 这种实现方式的缺点如下:
        • 同一进程中的线程切换，需要从用户态转到核心态进行，系统开销较大。这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的。
    • 组合方式
      • 同一进程中的多个线程可以同时在多处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞，所以组合方式能结合KLT和ULT的优点，并且克服各自的不足。
      • 有些系统使用组合方式的多线程实现。在组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。
      • 一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程实现的。
      • 有两种线程库(thread library )：
        • ①在用户空间中提供一个没有内核支持的库，这种库的所有代码和数据结构都位于用户空间中。这意味着，这个库内函数只作用于用户空间中的一个本地函数的调用。
        • ②实现由操作系统直接支持的内核级的一个库，对于这种情况，库内的代码和数据结构位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。
    • 目前使用有三种主要线程库
      • Pthreads作为POSIX标准的扩展，可以提供用户级或内核级的库。
      • Windows API是用于Windows系统的内核级线程库。
      • Java线程API是由JVM在宿主操作系统之上，采用宿主系统的线程库来实现，在Windows上采用Windows API来实现，在类UNIX系统中采用Pthreads来实现。
  • 多线程模型
    • 有些系统同时支持用户线程和内核线程，由于用户级线程和内核级线程连接方式的不同，从而形成了下面三种不同的多线程模型。
      • 多对一模型：将多个用户级线程映射到一个内核级线程，这些用户线程一般属于一个进程，线程的调度和管理在用户空间完成。
        • 优点:线程管理是在用户空间进行的，因而效率比较高。
        • 缺点:如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞;在任何时刻，只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行。
      • 一对一模型：将每个用户级线程映射到一个内核级线程
        • 优点:当一个线程被阻塞后，允许调度另一个线程运行，所以并发能力较强。
        • 缺点:每创建一个用户线程，相应地就需要创建一个内核线程，开销较大。
      • 多对多模型：将n个用户线程映射到m个内核级线程上，要求n≥m；
        • 特点:既克服了多对一模型并发度不高的缺点，又克服了1对1模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有上述两种模型各自的优点。

处理机调度

• 调度的概念

  • 调度的基本概念

    • 从就绪队列中按照一定算法（公平、高效的原则）选择一定进程并将处理机分配给它运行，一实现多进程并发的执行；
    • 进程的数量往往多于处理机的个数，处理机调度是对处理机进行分配，处理机调度是操作系统的基础，也是操作系统设计的核心问题；

  • 调度的层次，一个作业从提交开始直到完成，往往要经历以下三级调度：

    • 高级调度（作业调度）
      • 按照一定的原则从外存上处于后备队列的作业中挑选一个(或多个)，给它(们)分配内存、IO设备等必要的资源，并建立相应的进程，以使它(们)获得竞争处理机的权利。
      • 简言之，作业调度就是内存与辅存之间的调度。每个作业只调入一次、调出一次。
    • 中级调度（内存调度）
      • 引入中级调度的目的是提高内存利用率和系统吞吐量。将那些暂时不能运行的进程调至外存等待，此时进程的状态称为挂起态。
      • 当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。
      • 中级调度实际上是存储器管理中的对换功能。
    • 低级调度（进程调度）
      • 按照某种算法从就绪队列中选取一个进程，将处理机分配给它。进程调度是最基本的一种调度。进程调度的频率很高，一般几十毫秒一次。

  • 三级调度的联系

    • 作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程并送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它；
    • 中级调度是为了提高内存的利用率，将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间；
    • 作业调度次数少，中级调度次数略多，进程调度频率最高。进程调度是最基本的，不可或缺。

  • 调度的目标

    • pre：不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法的特性。为了比较处理机调度算法的性能，有以下评价标准
    • CPU利用率
      • CPU是计算机系统中最重要和昂贵的资源之一，所以应尽可能使CPU“忙”状态，使这一资源利用率最高；
      • CPU利用率的计算方法：CPU有效工作时间 / （CPU有效工作时间 + CPU空闲等待时间）；
    • 系统吞吐量
      • 表示单位时间内CPU完成作业的数量，长作业需要消耗较长的处理机时间因此会降低系统的吞吐量。
      • 而对于短作业，需要消耗的处理机时间较短，因此能提高系统的吞吐量、调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。
    • 周转时间
      • 指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及输入/输出操作所花费时间的总和；
      • 周转时间的计算方法：周转时间 = 作业完成时间 - 作业提交时间；
      • 多个作业周转时间的平均值(平均周转时间)：平均周转时间=(作业1的周转时间+.+作业n的周转时间)/n
      • 带权周转时间：作业周转时间 / 作业实际运行时间，指的多个作业带权周转时间的平均值；
    • 等待时间
      • 指进程处于等处理机的时间之和，等待时间越长，用户满意度越低。衡量一个调度算法的优劣，常常只需简单地考察等待时间。
      • 处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。
    • 响应时间
      • 指从用户提交请求到系统首次产生响应所用的时间。在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一。
    • 设计调度程序的策略
      • 从用户角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能接受的范围之内。
      • 一方面要满足特定系统用户的要求(如某些实时和交互进程的快速响应要求)，
      • 另一方面要考虑系统整体效率(如减少整个系统的进程平均周转时间)，同时还要考虑调度算法的开销。要想得到一个满足所有用户和系统要求的算法几乎是不可能的。

  • 调度的实现

    • 调度程序（调度器）
      • pre：用于调度和分派CPU的组件称为调度程序，它通常由三部分组成：
      • 1 排队器：将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便于调度程序选择。每当有一个进程转变为就绪态时，排队器便将它插入到相应的就绪队列中；
      • 2 分派器：依据调度程序所选的进程，将其从就绪队列中取出，将CPU分配给新进程；
      • 3 上下文切换器：在对处理机进行切换时，会发生两对上下文的切换操作：
        • 第一对，将当前进程的上下文保存到其PCB中，再装入分程序的上下文，以便分派程序运行，
        • 第二对，移出分派程字的上下文，将新选进程的CPU现场信息装入处理机的各个相应寄存器。
        • 在上下文切换时，需要执行大量load和store指令，以保存寄存器的内容。因此会花费较多时间；现在己有硬件实现的方法来减少上下文切换时间，
        • 通常采用两组寄存器，其中一组供内核，一组供用户使用，这样上下文切换时，只需改变指针，让其指向当前寄存器组即可；
    • 调度的时机、切换与过程
      • 调度程序是操作系统内核程序，请求调度的事件发生后，才可能运行调度程序。调度了新的就绪进程后，才会进行进程切换。
      • 理论上这三件事情应该顺序执行，但在实际的操作系统内核程序运行中，若某时刻发生了引起进程调度的因素，则不一定能马上进行调度与切换。
      • 不能进行进程的调度与切换的情况有以下几种:
        • 1 在处理中断的过程中。中断处理过程复杂，在实现上很难做到进程切换，而且中断处理是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。
        • 2 进程在操作系统内核临界区中。进入临界区后需要独占式地访问，理论上必须加锁，以防止其他并行进程进入，在解锁前不应切换到其他进程，以加快临界区的释放。
        • 3 其他需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。
        • 发生了引起调度的条件，但不能马上进行调度和切换的，应置系统的请求调度标志，直到上述过程结束后才进行相应的调度与切换。
      • 应该进行进程调度与切换的情况如下:
        • 1 发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
        • 2 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。剥夺方式的调度。
    • 进程调度方式
      • pre：所谓进程调度方式，是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程要处理，即有优先权更高的进程进入就绪队列，此时应如何分配处理机；
      • 非抢占式调度（非剥夺方式）
        • 是指当一个进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，仍然让正在执行的进程继续执行，
        • 直到该进程运行完成或发生某种事件而进入阻塞态时，才把处理机分配给其他进程。
        • 非抢占调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统，但它不能用于分时系统和大多数的实时系统。
      • 抢占式调度（剥夺方式）
        • 是指当一个进程正在处理机上执行时，若有某个更为要或紧追的进程需要使用处理机，则将处理机分配给这个更为重要或紧迫的进程。
        • 抢占调度方式对提高系统吞吐率和响应效率都有明显的好处。但必须遵循一定的原则，主要有优先权、短进程优先、时间片原则等。
    • 闲逛进程
      • 闲逛进程(idle)的优先级最低，没有就绪进程时才会运行闲逛进程，只要有进程就绪，就会立即让出处理机。闲逛进程不需要 CPU之外的资源，它不会被阻塞。
    • 两种线程的调度
      • 1 用户级线程调度：由于内核并不知道线程的存在，所以内核还是和以前一样，选择一个进程，并给予时间控制。由进程中的调度程序决定哪个线程运行。
      • 2 内核级线程调度：内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程。
      • 内核级线程的线程切换需要完整的上下文切换、修改内存映像、使高速缓存失效，这会导致了若干数量级的延迟。用户级线程的线程切换仅需少量的机器指令；

  • 典型的调度算法

    • pre：操作系统中存在多种调度算法，有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。
    • 先来先服务（FCFS）
      • FCFS调度算法是一种最简单的调度算法，它既可用于作业调度，又可用于进程调度。
      • 每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。
      • 在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它；
      • FCFS调度算法的性能计算：
        • 平均等待时间、平均周转时间、平均带权周转时间(64页)；
      • FCFS调度算法属于不可剥夺算法
        • 从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统、就会使后面的许多如作业等待报长时间；
        • 因此它不能作为分时系统和实时系统的主要调度策略，但它常被结合在其他调度策略中使用。
        • 例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。
      • FCFS调度算法的特点是算法简单，但效率低，有利于CPU繁忙型作业，而不利于1/O繁忙型作业。
    • 短作业优先（SJF）
      • 短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。短作业优先(SJP)调度算法从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行；
      • 短作业优先调度算法的性能计算：
        • 平均等待时间、平均周转时间、平均带权周转时间；
        • 短作业优先调度算法的平均等待时间、平均周转时间最少。
      • 缺点：
        • 对长作业不利
        • 完全未考虑作业的紧迫程度
        • 作业时间的长短是根据用户所提供的估计时间而定的；
    • 优先级调度算法
      • pre：优先级调度算法既可用于作业调度，又可用于进程调度。该算法中的优先级用于描述作业的紧迫程度。
      • 根据新的更高优先级进程能否抢占正在执行的进程，可将该调度算法分为如下两种:
        • 非抢占式优先级调度算法
          • 当一个进程正在处理机上运行时，即使有某个优先级更高的进程进入就绪队列，仍让正在运行的进程继续运行，
          • 直到由于其自身的原因而让出处理机时，才把处理机分配给就绪队列中优先级最高的进程。
        • 抢占式优先级调度算法
          • 当一个进程正在处理机上运行时，若有某个先级更高的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给优先级更高的进程。
          • 根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：
            • 静态优先级
              • 优先级是在创建进程时确定的，且在进程的整个运行期间保持不变，确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求；
            • 动态优先级
              • 在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优失级的主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短。
              • 一般来说，进程优先级的设置可以参照以下原则:
                • 1 系统进程>用户进程。系统进程作为系统的管理者，理应拥有更高的优先级。
                • 2 交互型进程(前台)>非交互型进程(后台)，例如：在使用手机时，在前台运行的正在和你交互的进程应该更快速地响应你，因此自然需要被优先处理。
                • 3 IO型进程>计算型进程。I/O设备(如打印机)的处理速度要比CPU慢得多，因此若将I/O型进程的优先级设置得更高,就更有可能让I/O设备尽早开始工作，进而提升系统的整体效率。
    • 高响应比优先调度算法
      • 主要用于作业调度，是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间，
      • 在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
      • 响应比的变化规律可描述为：响应比Rp=(等待时间+要求服务时间)/要求服务时间，根据公式可知:
        • ①作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业，因而类似于 SIF；
        • ②要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而类似于FCFS。
        • ③对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，也可获得处理机，克服了“饥饿”现象。
    • 时间片轮转调度算法
      • 主要适用于分时系统，在这种算法中，系统将所有就绪进程按FCFS策略排成一个就绪队列，调度程序总是选择就绪队列中的第一个进程执行，但仅能运行一个时间片；
      • 在使用完一个时间片后，即使进程并未运行完成，它也必须释放出(被剥夺)处理机给下一个就绪进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。
      • 时间片的大小应选择适当，时间片的长短通常由以下因素确定:
        • 系统的响应时间
        • 就绪队列中的进程数量
        • 系统的处理能
    • 多级队列调度算法
      • 前述的各种调度算法，由于系统中仅设置一个进程的就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。
      • 该算法在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列。每个队列可实施不同的调度算法；
      • 系统针对不同用户进程的需求，很容易提供多种调度策略，同一队列中的进程可以设置不同的优先级；
      • 在多CPU系统中，可以很方便为每个CPU设置一个单独的就绪队列，每个CPU可实施各自不同的调度策略、这样就能根据用户需求将多个线程分配到一个或多个CPU上运行。
    • 多级反馈队列调度算法（融合了前几种算法的优点）
      • 是时间片轮转调度算法和优先级调度算法的综合与发展，通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。
      • 例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程,为获得较好的1/O设备利用率和缩短响应时间而照顺IO型进程的同时，也不必事先估计进程的执行时间。
      • 多级反馈队列调度算法的实现思想如下:
        • 1 设置多个就绪队列：并为每个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列的优先级次之，其余队列的优先级逐个降低。
        • 2 赋予各个队列的进程运行时间片的大小各不相同：在优先级越高的队列中，每个进程的时间片就越小。例如，第i+1级队列的时间片要比第i级队列的时间片长1倍
        • 3 每个队列都采用FCFS算法：
          • 当新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS 原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。
          • 若它在一个时间片结束时尚未完成，调度程序将其转入第2级队列的末尾等待调度；
          • 若它在第2级队列中运行一个时间片后仍未完成，再将它放入第3级队列……，以此类推。
          • 当进程最后被降到第n级队列后，在第n级队列中便采用时间片轮转方式运行。
        • 4 按队列优先级调度
          • 仅当第1级队列为空时，才调度第2级队列中的进程运行，仅当第1~1-1级队列均为空时，才会调度第i级队列中的进程运行。
          • 若处理机正在执行第1级队列中的某进程时，又有新进程进入任何一个优先级较高的队列，
          • 此时须立即把正在运行的进程放回到第1级队列的末尾，而把处理机分配给新到的高优先级进程；
      • 多级反馈队列的优势有以下几点
        • 终端型作业用户：短作业优先
        • 短批处理作业用户：周转时间较短
        • 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理；
    • 要记住常见的几种调度算法特点(优缺点、适用于)：先来先服务、短作业优先、高响应比优先、时间片轮转、多级反馈队列；

进程切换

• 对于通常的进程而言，其创建、撤销及要求由系统设备完成的I/O操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。
• 进程切换同样是在内核的支持下实现的，任何进程都是在操作系统内核的支持下运行的；
• 上下文切换
  • 切换CPU到另一个进程时，需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。上
  • 下文是指某一时刻CPU寄存器和程序计数器的内容。
  • 进行上下文切换时，内核会将旧进程状态保存在其PCB中，然后加载经调度而要执行的新进程的上下文。在这个过程中，进程的运行环境产生了实质性的变化；
  • 上下文切换的流程如下：
    • 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器；
    • 更新PCB信息
    • 把进程的PCB移入相应的队列，如就绪、在等待某事件阻塞等队列
    • 选择一个进程执行，并更新其PCB；
    • 跳转到新进程PCB中的程序计算器所指向的位置执行
    • 恢复处理机上下文
• 上下文切换的消耗
  • 上下文切换通常是计算密集型的，即它需要相当可观的CPU时间，在每秒几十上百次的切换中，每次切换都需要纳秒量级的时间，
  • 所以上下文切换对系统来说意味着消耗大量的CPU时间，现代计算机中有些处理器提供多个寄存器组，这样，上下文切换就只需要简单改变当前寄存器组的指针。
• 上下文切换与模式切换(用户态和内核态)
  • 用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。
  • 用户进程最开始都运行在用户态，若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的进程运行。
  • 模式切换与上下文切换是不同的，模式切换时，CPU逻辑上可能还在执行同一进程。
• 调度和切换的区别：
  • 调度是指决定资源分配给哪个进程的行为，是一种决策行为;
  • 切换是指实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。

同步与互斥

• 同步与互斥的基本概念

  • 概念：多进程是并发执行的，为了协调进程之间的相互制约关系，引入了进程同步的概念，实际是制定一定的机制去约束进程；
  • 临界资源
    • 将一次仅允许一个进程使用的资源称为临界资源，为了保证临界资源的正确使用，可把临界资源的访问过程分成4个部分:
      • 进入区：在进入区要检查可否进入临界区，若能进入界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区；
      • 临界区：进程中访问临界资源的那段代码，又称临界段；
      • 退出区：将正在访问临界区的标志清除；
      • 剩余区：代码中的其余部分；
  • 同步
    • 同步也称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
    • 进程间的直接制约关系源于它们之间的相互合作。
  • 互斥
    • 互斥也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。
  • 为禁止两个进程同时进入临界区，同步机制应遵循以下准则
    • 1 空闲让进，临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
    • 2 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
    • 3 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。
    • 4 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

• 实现临界区互斥的基本方法

  • 软件实现方法
    • pre：在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。
    • 算法一：单标志法，该算法设置一个公用整型变量turn=0，用于指示被允许进入临界区的进程编号，即0允许、1禁止。
    • 算法二：双标志法先检查
      • 该算法的基本思想是在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问该进程需等待，设置一个布尔型数组flag。
    • 算法三：双标志法后检查
      • 算法二先检测对方的进程状态标志，再置自己的标志，会造成两个进程在分别检测后同时进入临界区。
      • 为此，算法三先将自己的标志设置为TRUE,再检测对方的状态标志，若对方标志为TRUE，则进程等待，否则进入临界区。缺点，会导致“饥饿”现象；
    • 算法四：Peterson`s Algorithm
      • 为了防止两个进程为进入临界区而无限期等待，又设置变量turn，每个进程在先设置自己的标志后再设置turn标志。
      • 再同时检测另一个进程状态标志和允许进入标志，以便保证两个进程同时要求进入临界区时，只允许一进程进入临界区。
      • 本算法的基本思想是算法一和算法三的结合。利用flag解决临界资源的互斥访问，而利用turn解决“饥饿”现象。
  • 硬件实现方法
    • pre：学习这个对学习后面的信号量很有帮助。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。
    • 中断屏蔽法
      • 当一个进程正在执行它的临界区代码时，最简方法是关中断，因为CPU只在发生中断时引起进程切换，进程临界区代码利地执行完，然后执行开中断。
      • 这种方法限制了CPU交替执行程序的能力，执行的效率会明显降低。对内核行更新变量或列表的几条指令期间，关中断是很方便的，但不能将关中断的权力交给用户；
    • 硬件指令方法
      • TestAndSet 指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。
        • 可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态:true 表示正被占用，初值为false。
        • 进程在进入临界区之前，利用TestAndSet检查标志lock，其值为false可以进入，进入后把lock置为true。当有进程在临界区，则循环检查，直到进程退出；
      • Swap指令：该指令的功能是交换两个字(字节)的内容。其功能描述如下:
        • 用Swap指令可以简单有效地实现互斥，为每个临界资源设置一个共享布尔变量lock，初值为fnlse。在每个进程中再设置一个局部布尔变量key，用于与lock交换信息，
        • 在进入临界区前，先利用Swap指令交换lock与key的内容，然后检查key的状态。有进程在临界区时，重复交换和检查过程，直到进程退出；
      • 注意：TestAndSet和Swap指令的描述仅是功能实现，而并非软件实现的定义，事实上，它们是由硬件逻辑直接实现的、不会被中断。
    • 硬件方法的优、缺点：
      • 优点：适用于任意数目的进程，而不管是单处理机还是多处理机，简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。
      • 缺点:进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。
      • 无论是软件实现方法还是硬件实现方法，都需理解它的执行过程,特别是软件实现方法。以上是为了表述进程实现同步和互斥的过程，并非计算机内部实现同步互斥的代码。

• 互斥锁(采用硬件机制来实现)

  • 解决临界区最简单的工具就是互斥锁(mutex lock)。一个进程在进入临界区时应获得锁，在退出临界区时释放锁。
  • 函数acquire()获得锁，而函数release()释放锁，每个互斥锁有一个布尔变量available,表示锁是否可用；
  • 如果锁是可用的，调用acquire()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。
  • acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。
  • 互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一个CPU时，就浪费了CPU周期。
  • 因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。可以用互斥锁解决经典同步问题。

• 信号量

  • pre：是一种用来解决互斥与同步问题功能较强的机制，只能被两个标准原语wait(S)和signal(S)访问，被记为P操作和V操作
  • 整型信号量：表示资源数量的整型量S，这个机制并未遵循“让权等待”的标准，而是处于忙等待的状态；
  • 记录型信号量：不存在“忙等”现象的同步机制，增加了进程链表L，用于链接所有等待该资源的进程，这个机制遵循“让权等待”原则；
  • 利用信号量实现同步：信号量机制能用于解决各种同步问题，设置一个公共信号量(全局变量)；
  • 利用信号量实现进程互斥：信号量机制能方便解决互斥问题，设置一个公共信号量，初始值为1，进入临界区之后置为0，互斥是不同进程对同一信号量进行P、V操作实现的；
  • 利用信号量实现前驱关系：信号量也可以用来描述程序语句之间的前驱关系，后继需要用到前驱的资源，则可以用信号量保证语句之间的前驱关系；
  • 分析进程同步和互斥问题的方法步骤
    • 1 关系分析：找出问题中的进程数，并分析他们之间的同步与互斥关系；
    • 2 整理思路：找出解决问题的关键点，根据进程的操作流程确定P操作、V操作的大致顺序。P在用到资源的行为前面，释放资源之后V操作一下；
    • 3 设置信号量：根据上面的两步，设置需要的信号量，确定初值，完善整理；

• 管程

  • 管程的定义
    • 是一种进程同步工具，无序让各个进程自备PV操作，管程的特性保证了进程互斥，降低了死锁发生的可能性，管程同时还提供了条件变量
    • 把系统中的各种硬件和软件资源用数据结构抽象地描述其资源特性，而把对该数据结构实施的操作定义为一组过程，包括申请和释放等操作；
    • 这组过程可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样可以统一管理对共享资源的所有访问，这组过程就叫管程；
    • 管程定义了一组数据结构和能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据；
    • 管程由4部分组成：
      • 管程的名称
      • 局部于管程内部的共享数据结构说明；
      • 对该数据结构进行操作的一组过程（或函数）；
      • 对局部于管程内部的共享数据设置初始值的语句；
    • 可以把管程理解成面向对象的一个类
      • 管程把对共享资源的操作封装起来，管程内的数据只允许管程内的过程访问，外部资源只能通过调用管程的方法和申请和归还资源；
      • 每次仅允许一个进程进入管程，从而实现进程互斥；take_away()申请资源、give_back()归还资源；
  • 条件变量
    • 将阻塞原因定义为条件变量condition，通常一个进程被阻塞的原因有多个，因此在管程中设置多个条件变量，每个条件变量保存一个等待队列，记录因为该条件变量而阻塞的所用进程；
    • 对条件变量只能进行两个操作，wait和signal
      • x.wait，当x对应的条件不满足时，当前进程会调用管程的x.wait将自己插入x条件的等待队列，并释放管程，此时其它进程可以使用管程；
      • x.siganl，当x对应的条件发生变化，则调用x.siganl唤醒一个因x条件而阻塞的进程；

• 条件变量和信号量的比较

  • 相似点：条件变量的wait和signal操作类似于信号量的P/V操作，可以实现进程的阻塞和唤醒；
  • 不同点：条件变量是没有值的，仅实现了排队等待功能，而信号量是有值的，信号量的值反映了剩余资源数；
  • 管程的缺点：当一个进程进入管程后被阻塞，直到阻塞原因被解除，在此期间如果进程不释放管程那么其它进程也无法进程管程；条件变量就可以解决这个问题；

• 经典同步问题

  • 生产者-消费者问题
    • 简单问题
      • 问题描述：一个大小为n的缓冲区为生产者和消费者共享，缓冲区是临界资源，缓冲区空则消费者取消息阻塞，缓冲区满则生产者发消息阻塞；
      • 问题分析
        • 关系分析：生产者和消费者对缓冲区的访问互斥关系、生产者和消费者是相互协作关系、只有生产者生产之后消费者才能消费，他们这是同步关系；
        • 整理思路：这两个进程有互斥和同步关系，只需要解决互斥和同步PV操作的位置；
        • 信号量设置：信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，用两个信号量，full的0,1标记缓冲区是否满，empty记录空缓冲区数，初始值为n；
    • 复杂一些问题
      • 问题描述：两队进程，一对有两个进程负责写操作(各自写自己部分的数据)，另一对也是两个进程负责读操作(读各自写进程对应的数据)，有数据时才可读；
      • 问题分析
        • 关系分析：两个写进程是互斥关系，同时只能一个进程执行写操作，读和写是同步关系，两个读进程是选择条件执行，不可能并发；
        • 整理思路：这里有4个进程，实际上可抽象成两个生产者和两个消费者被连接到大小为1的缓冲区上；
        • 信号量设置：
          • plate是互斥信号量，标记是否允许写数据1可写0不可写，只能同时1个进程执行写操作；
          • apple信号量表示缓冲区是否有苹果的数据1有0无，orange表示缓存取总是否有橘子的数据1有0无，
  • 读者-写者问题
    • 问题描述：
      • 有读者和写者两组并发进程，共享一个文件，当某个写进程和其他读写进程同时访问数据时会出现数据不一致的问题；
      • 四个要求：
        • 1 允许多个读者可以同时对文件执行读操作；
        • 2 只允许一个写者往文件中写信息；
        • 3 任意一个写进程在写操作是不允许其它进程读或写工作；
        • 4 写执行前让读和写的进程都退出；
    • 问题分析
      • 关系分析：读者和写者是互斥的，写者和写者也是互斥的，而读者和读者不存在互斥问题；
      • 整理思路：
        • 两个进程读者和写者，写者和任何进程都互斥，用互斥信号量P、V操作即可解决；
        • 读者必须在实现与写者互斥的同时，实现与其它读者共享，用一个count计数器判断是否有读者读文件；
      • 信号量设置：count、mutex、rw
        • 首先设置信号量count为计数器，用于记录当前读者的数量，初始值为0。
        • 设置mutex为互斥信号量，用于保护更新count变量时的互斥；
        • 设置互斥信号量rw，用于保证读者和写者的互斥访问；
  • 哲学家进餐问题
    • 问题描述：
      • 一个圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，当哲学家饥饿时会试图拿起左右两根筷子(一根一根地拿起)；
      • 若筷子已经在他人之手，则需要等待，只有拿到两只筷子才能开始进餐，进餐完毕后放下筷子；
    • 问题分析：
      • 关系分析：5名哲学家和左右邻居对其中的筷子的访问是互斥关系；
      • 整理思路：
        • 五个进程，关键是如何让一名哲学家拿到左右两根筷子，而不造成死锁或饥饿现象；
        • 解决方法有两个，1是让他们同时拿两根筷子，2是对每名哲学家的动作指定规则，避免死锁或饥饿现象发生；
      • 信号量设置
        • 定义互斥信号量数组 chopstick[5]={1,1,1,1,1}，用于对5个筷子的互斥访问；
        • 哲学家编号为0-4，哲学家i左边筷子的编号为i，右边的筷子编号为(i+1)%5;
      • 为防止死锁发生，可以对哲学家进餐施加一些限制，例如：
        • 比如至多允许4名哲学家同时进餐，仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子；
        • 对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反；
      • 和贪心算法的比较
        • 哲学家进餐问题的思想与贪心算法的思想截然相反，贪心算法强调正确眼前认为最好的，而不考虑后续会有什么后果；
        • 不仅要考虑眼前的一步，而且考虑下一步，既不因为有筷子能拿起来就拿起来，而不考虑能不能一次拿起来根筷子才做决定，就可以避免死锁问题；
        • 这是哲学家进餐问题的思维精髓；
  • 吸烟者问题
    • 问题描述：让三个抽烟者轮流抽烟，假设系统中有三个抽烟者进程和一个供应者进程，抽烟者抽掉一只烟需要三种材料：烟草、纸和胶水，这些材料凑齐才是抽掉一只烟；
    • 问题分析
      • 关系分析：三个抽烟者进程和一个供应者是同步关系，供应者无法同时满足两个及以上的抽烟者，三个抽烟者对抽烟的动作是互斥的(轮流抽烟)；
      • 整理思路：供应者作为生产者向三个抽烟者提高材料；
      • 信号量设置：信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用户互斥进行抽烟动作；
  • 提示：大部分考试中的问题用读者-写者、生产者-消费者模型就能解决，哲学家进餐问题和吸烟者问题要求熟悉就行；

死锁

• 死锁的基本概念

  • 死锁的定义：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进；
  • 死锁产生的原因
    • 系统资源的竞争：只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源是不会产生死锁的；
    • 进程推进顺序非法
      • 请求和释放资源的顺序不当，造成互相等待对方资源释放；
      • 信号量使用不当也会造成死锁，进程间互相等待对方发来消息造成互相等待；
  • 死锁产生的必要条件
    • pre：必须同时满足以下4个条件，只要其中任意一项不成立，死锁就不会产生；
    • 互斥条件：进程要求对所分配资源进行排他性使用，其它进程请求该资源只能等待；
    • 不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能由获得该资源的进程主动释放；
    • 请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求被阻塞，但对自己获得资源保持不放；
    • 循环等待条件：
      • 存在一种进程资源的循环等待链，链中的每个进程已获得资源同时被链中下一个进程请求资源；
      • 循环等待不同于死锁，死锁的要求更严格，只等待某一个具体资源释放。循环等待可能等待的资源被pn或pk持有，pk释放资源之后就可打破循环等待；
  • 死锁的处理策略
    • pre：为使系统不发生死锁，必须设法破坏死锁产生的4个必要条件之一，或有死锁检测功能并能实时解除死锁；
    • 死锁预防：设置某些限制条件，破坏死锁产生的4个必要条件之一或几个。
    • 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态；
    • 死锁的检测及消除：无需采取限制措施，允许死锁发送，通过系统检测功能检测死锁，然后采取某种措施解除死锁；
    • 死锁的处理策略的比较：
      • 死锁预防，这种方式实现简单，但会导致系统的效率低，资源利用率低；
      • 死锁避免是“预防”和“检测”的折中，在运行时判断是否可能死锁，不过必须知道将来的资源需求；
      • 死锁的检测及消除，通过剥夺解除死锁会造成损失；

• 死锁预防

  • 破坏互斥条件：允许系统资源都能共享，则系统不会进程死锁状态。但有些邻接资源只能互斥使用，这个时候破坏互斥条件预防死锁的方法就不太行了；
  • 破坏不剥夺条件：当进程保持请求资源没有得到满足时，先暂时释放自己拥有的资源，待需要时再申请。这种方法适用于易于保存和恢复的资源，如CPU的寄存器；
  • 破坏请求并保持条件：采用预先静态分配方法，在进程运行前一次申请它所需要的全部资源，运行之后不再提出资源申请请求，这种方法实现简单但资源利用率低；
  • 破坏循环等待条件：采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源；

• 死锁避免

  • 系统安全状态
    • 在系统在进行资源分配之前，先计算此次分配的安全性，若此次分配不会导致系统进入不安全状态，则允许分配，否则让进程等待。
    • 所谓安全状态，是指系统能按某种进程推进顺序(P,P2,Pn)，为每个进程P,分配其所需的资源直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。
    • 若系统无法找到一个安全序列，则称系统处于不安全状态。假设系统中有三个进程P、P,和P3,共有12台磁带机，当这三个进程申请的磁带机数量没分配好时就会造成死锁；
  • 银行家算法
    • 银行家算法是最著名的死锁避免算法，其思想是：
      • 把操作系统视为银行家，资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款，操作系统按照银行家制定的规则为进程分配资源；
      • 进程运行之前先声明对各种资源的最大需求量，当进程在执行中维续申请资源时、先测试该进程已占用的资源数与本次申请的资源数之和是否超过诶进程声明的最大需求量。
      • 若超过则拒绝分配资源，若未超过则再测试系统现存的资源能否满足该进程尚需的最大资源量、若能满足则按当前的申请量分配资源，否则也要推迟分配；
    • 数据结构描述
      • 可利用资源向量Available：含有m个元素的数组，其中每个元素代表一类可用的资源数目；
      • 最大需求矩阵Max：n*m矩阵；
      • 分配矩阵Allocation：n*m矩阵；
      • 需求矩阵Need：n*m矩阵，上述三个矩阵的关系，Need = Max - Allocation；
    • 银行家算法描述
      • 当P1发出资源请求后，系统按下述步骤进行检查：
        • 1 检测请求资源是否大于进程声明的最大资源，则转向步骤2；
        • 2 可用资源小于请求资源，则转向步骤3，否则表示尚无足够资源，则P1进程须等待；
        • 3 系统试着把资源分配给进程P1，并修改数据结构中的数组；
        • 4 系统执行安全性检测算法，检测此次资源分配后，系统是否处于安全状态，若安全才正式将资源分配给进程，否则本次试探分配作废，让P1进程等待；
    • 安全性算法
      • 设置工作向量Work，有m个元素，表示系统中的剩余可用资源数目。在执行安全性算法开始时，Work = Available.
        • 1 初始时安全序列为空。
        • 2 从Need矩阵中找出符合下面条件的行:该行对应的进程不在安全序列中，而且该行小于或等于Work向量，找到后把对应的进程加入安全序列;若找不到，则执行步骤④。
        • 3 进程P1进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源；
        • 4 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。
  • 安全性算法举例
    • 资源分配数量、在T0时刻的资源分配情况表；
  • 银行家算法举例
    • 安全性算法是银行家算法的核心，在银行家算法的题目中，一般会有某个进程的一个资源请求向量，
    • 只要执行上面所介绍的银行家算法的前三步，马上就会得到更新的Allocation矩(139页)。

• 死锁检测和解除

  • 资源分配图(有向图)
    • 系统死锁可利用资源分配图来描述，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。
    • 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源，从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程
  • 死锁定理
    • 简化资源分配图可检测系统状态S是否为死锁状态。简化方法如下:
    • 1 在资源分配图中，找出既不阻塞又不孤点的进程Pi，即找出一条有向边与它相连，且该有向边对应资源的申请数量小于或等于系统中已有的空闲资源数量，
      • 若所有连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源。消去它所有的请求边和分配边，使之成为孤立的结点。
      • 要注意一个问题，判断某种资源是否有空闲，应该用它的资源数量减去它在资源分配图中的出度；
    • 2 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
    • 根据1中的方法进行一系列简化后，若能消去图中所有的边，则称该图是可完全简化的，S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。
  • 死锁解除
    • 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
    • 撤销进程法：强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
    • 进程回退法：让一(或多)个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点。

3、内存管理

考纲内容-3

• 内存管理基础

  • 内存管理概念
    • 逻辑地址与物理地址空间
    • 地址转换
    • 内存共享
    • 内存保护
    • 内存分配与回收
  • 连续分配管理方式
    • 页式管理
    • 段式管理
    • 段页式管理

• 虚拟内存管理

  • 虚拟内存基本概念
    • 请求页式管理
    • 叶框分配
    • 页置换算法
    • 内存映射文件（Memory-Mapped Files）
      • 虚拟存储器性能的影响因素及改进方式

• 内存管理基础

  • 内存管理概念
    • 因为内存大小的原因，不能将所有用户进程和系统所需要的全部程序与数据放入主存，因此OS对内存空间的划分和动态分配就是内存管理的概念；
    • 内存管理的基本原理和要求：
      • 内存空间的分配与回收：有OS完成主存储器空间的分配和管理，是程序员摆脱存储分配的麻烦；
      • 地址转换：在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址；
      • 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
      • 内存共享：指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同块数据，因此必须支持对内存共享区域进行受控访问。
      • 存储保护：保证各道作业在各自的存储空间内运行，互不干扰。
    • 进程运行的基本原理和要求：
      • 程序的链接与装入
        • 创建进程先将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：编译、链接(库函数)、装入(装入程序将装入模块装入内存运行)
      • 程序的链接有以下三种方式
        • 1 静态链接：
          • 在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。
          • 将几个目标模块装配成一个装入模块时，需要解决两个问题:
            • ①修改相对地址，编译后的所有目标模块都是从0开始的相对地址，当链接成一个装入模块时要修改相对地址。
            • ②变换外部调用符号，将每个模块中所用的外部调用符号也都变换为相对地址。
        • 2 装入时动态链接：
          • 将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享。
        • 3 运行时动态链接：
          • 对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。
          • 其优点是能加快程序的装入过程，还可节省大量的内存空间。
      • 内存的装入模块在装入内存时，同样有以下三种方式
        • 1 绝对装入：
          • 绝对装入方式只适用于单道程序环境。在编译时，由编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。
          • 由于程序中的逻辑地址与实际内存地址完全相同，因此不需对程序和数据的地址进行修改。
          • 另外，程序中所用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。而通常情况下在程序中采用的是符号地址，编译或汇编时再转换为绝对地址。
        • 2 可重定位装入(静态重定位)：
          • 在多道程序环境下，多个目标模块的起始地址通常都从0开始，程序中的其他地址都是相对于起始地址的，此时应采用可重定位装入方式。
          • 根据内存的当前情况，将装入模块装入内存的适当位置。在装入时对目标程序中指令和数据地址的修改过程称为重定位，地址变换通常是在进程装入时一次完成的，故称为静态重定位
          • 当一个作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则无法装入。此外，程序在整个运行期间就不能在内存中移动，也不能再申请内存空间。
        • 3 动态运行时装入(动态重定位)：
          • 程序在内存中若发生移动，则需要采用动态的装入方式，装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，
          • 而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持；
          • 优点，可以将程序分配到不连续的存储区，在程序运行之前可以只装入部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存，便于程序段的共享。
      • 逻辑地址与物理地址空间
        • 编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址(或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，
        • 链接程序顺序依次按各个模块的相对地址，构成统一的从0号单元开始编址的逻辑地址空间(或虚拟地址空间)，对于32位系统，逻辑地址空间的范围为0~2”-1。
        • 进程在运行时，看到和使用的地址都是逻辑地址。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的。
        • 不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。
        • 物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都通过物理地址从主存中存取。
        • 当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位，
        • 操作系统通过内存管理部件(MMU)将进程使用的逻辑地址转换为物理地址，进程使用虚拟内存空间中的地址、操作系统在相关硬件的协助下，将它“转换”成真正的物理地址。
        • 逻辑意址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。
      • 进程的内存映射
        • 不同于存放在硬盘上的可执行程序文件，当一个程序调入内存运行时，就构成了进程的内存映像，一个进程的内存映像一般有几个要素:
        • 代码段：即程序的二进制代码，代码段是只读的，可以被多个进程共享。
        • 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。
        • 进程控制块(PCB)：存放在系统区。操作系统通过PCB来控制和管理进程。
        • 堆：用来存放动态分配的变量。通过调用malloc函数动态地向高地址分配空间。
        • 栈：用来实现函数调用，从用户空间的最大地址往低地址方向增长。
      • 内存中的一个进程：
        • 操作系统内核区：用户代码不可见区域；
        • 用户栈：在程序运行期间也可以动态地扩展和收缩，每次调用一个函数，就会增长;从一个函数返回时，栈就会收缩。
        • 共享库的存储区：共享库用来存放进程用到的共享函数库代码，如 printf()函数等；
        • 动态生成的堆：运行时由malloc创建和free收缩，在运行时动态地扩展和收缩；
        • 读写数据段(.data .bss)：.data是已初始化的全局变量和静态变量，.bss是未初始化及所有初始化为0的全局变量和静态变量；
        • 只读代码段(.init .text .rodata)：init是程序初始化时调用的_init函数:.text 是用户程序的机器代码:rodata是只读数据。
      • 内存保护
        • 确保每个进程都有一个单独的内存空间，内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。
        • 内存保护可采取两种方法:
          • 1 在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当 CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界；
          • 2 采用重定位寄存器(又称基地址寄存器)和界地址寄存器(又称限长寄存器)来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值。
          • 内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元；
          • 重定位寄存器和界地址寄存器的硬件支持：CPU->逻辑地址->重定位寄存器->界地址寄存器->物理地址->内存；
        • 实现内存保护需要重定位寄存器和界地址寄存器，两者的区别
          • 重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址;
          • 界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。
        • 加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器。这种方案允许操作系统内核修改这两个寄存器的值。
      • 内存共享
        • 并不是所有的进程内存空间都适合共享，只有那些只读的区域才可以共享。可重入代码又称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。
        • 但在实际执行时，也可以为每个进程配以局部数据区，把在执行中可能改变的部分复制到该数据区，这样程序在执行时只需对该私有数据区中的内存进行修改；
        • 为实现代码共享，应在每个进程的页表中都建立40个页表项，它们都指向共享代码区的物理页号。每个进程还要为自己的数据区建立10个页表项，指向私有数据区的物理页号。
        • 对于分段系统，由于是以段为分配单位的，不管该段有多大，都只需为该段设置一个段表项(指向共享代码段始址，以及段长160KB)。
        • 由此可见，段的共享非常简单易行。此外，有基于共享内存的进程通信，由操作系统提供同步互斥工具。还有一种内存共享的实现一一内存映射文件。
      • 内存分配与回收
        • 存储管理方式的发展：由单一连续分配->固定分区分配->动态分区分配->连续分配方式发展到离散分配方式--页式存储管理;
        • 引入分段存储管理的目的，主要是为了满足用户在编程和使用方面的要求，其中某些要求是其他几种存储管理方式难以满足的。
    • 覆盖交换(重要)
      • 覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。
      • (1)覆盖：覆盖的基本思想，由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序)，因此可把用户空间分成一个固定区和若干覆盖区。
      • 将经常活跃的部分放在固定区，其余部分按调用关系分段，首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。
      • 覆盖技术的特点是，打破了必须将一个进程的全部信息装入主存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行，此外，内存中能够更新的地方只有覆盖区的段，不在覆盖区中的段会常驻内存。覆盖技术对用户和程序员不透明；
      • (2)交换：交换(对换)的基本思想是，把处于等待状态(或在CPU调度原则下被剥夺运行权利)的程序从内存移到辅存，把内存空间腾出来，这一过程又称换出；
      • 把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称换入。中级调度采用的就是交换技术。在理想情况下，内存管理器的交换过程速度足够快，总有进程在内存中可以执行。
      • 有关交换，需要注意以下几个问题：
        • 交换需要备份存储，通常是磁盘。它必须足够大，并提供对这些内存映像的直接访问。
        • 为了有效使用CPU，需要使每个进程的执行时间比交换时间长。
        • 若换出进程，则必须确保该进程完全处于空闲状态。
        • 交换空间通常作为磁盘的一整块，且独立于文件系统，因此使用起来可能很快。
        • 交换通常在有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停。
        • 普通的交换使用不多，但交换策略的某些变体在许多系统(如UNIX)中仍发挥作用。
      • 覆盖与交换的区别：
        • 交换技术主要在不同进程之间进行，而覆盖则用于同一个程序或进程中。覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。
        • 对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的；
    • 连续分配管理方式

      • 连续分配方式是指为一个用户程序分配一个连续的内存空间，譬如某用户需要100MB的内存空间，连续分配方式就在内存空间中为用户分配一块连续的100MB空间。

      • 连续分配方式主要包括

        • 1 单一连续分配
          • 内存在此方式下分为系统区和用户区，系统区仅供操作系统使用，通常在低地址部分:在用户区内存中，仅有一道用户程序，即整个内存的用户空间由该程序独占。
          • 这种方式的优点是简单、无外部碎片，无须进行内存保护，因为内存中永远只有一道程序。缺点是只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低。
        • 2 固定分区分配
          • 固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业，当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。
          • 在划分分区时有两种不同的方法。
            • 分区大小相等。程序太小会造成浪费，程序太大又无法装入，缺乏灵活性。
            • 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区。
          • 为了便于分配，建立一张分区使用表，通常按分区大小排队，各表项包括每个分区的起始地址、大小及状态(是否已分配)，分配内存时，便检索该表；
          • 这种方式存在两个问题:
            • 一是程序可能太大而放不进任何一个分区，这时就需要采用覆盖技术来使用内存空间:
            • 二是当程序小于固定分区大小时，也要占用一个完整的内存分区，这样分区内部就存在空间浪费，这种现象称为内部碎片。
            • 固定分区是可用于多道程序设计的最简单的存储分配，无外部碎片，但不能实现多进程共享一个主存区，所以存储空间利用率低。
        • 3 动态分区分配
          • 又称可变分区分配，它是在进程装入内存时，根据进程的实际需要，动态地为之分配内存，并使分区的大小正好适合进程的需要。因此，系统中分区的大小和数目是可变的。
          • 动态分区在开始时是很好的，但随着时间的推移，内存中会产生越来越多小的内存块，内存的利用率也随之下降。这些小的内存块称为外部碎片，
          • 它存在于所有分区的外部，这与固定分区中的内部碎片正好相对。克服外部碎片可以通过紧凑技术来解决，即操作系统不时地对进程进行移动和整理。
          • 但这需要动态重定位寄存器的支持，且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘碎片整理程序；
          • 在进程装入或换入主存时，若内存中有多个足够大的空闲块，则操作系统必须确定分配哪个内存块给进程使用，这就是动态分区的分配策略。
          • 考虑以下几种算法:
            • 1 首次适应(First Fit)算法：空闲分区以地址递增的次序链接。分配内存时，从链首开始顺序查找，找到大小能满足要求的第一个空闲分区分配给进程。
            • 2 邻近适应(Next Fit)算法：又称循环首次适应算法，由首次适应算法演变而成。不同之处是，分配内存从上次找结束的位置开始继续查找。
            • 3 最佳适应(Best Fit)算法：空闲分区容量增的次序形成空闲分区链，找到第一个能满足要求且最小的空闲分区分配给作业，避免“大材小用”。
            • 4 最坏适应(Worst Fit)算法：空闲分区以容量减的次序链接，找到第一个能满足要求的，即最大的分区，从中分割一部分存储空间给作业。
          • 首次适应算法最简单，通常也是最好和最快的。不过，首次适应算法会使得内存的低地址部分出现很多小的空闲分区，而每次分配查找时都要经过这些分区，因此增加了开销。
          • 邻近适应算法试图解决这个问题。但它常常导致在内存空间的尾部(因为一遍扫描中，内存前面部分使用后再释放时，不会参与分配)分裂成小碎片。通常比首次适应算法要差。
          • 最佳适应算法虽然称为“最佳”，但是性能通常很差，因为每次最佳的分配会留下很小的难以利用的内存块，会产生最多的外部碎片。
          • 最坏适应算法与最佳适应算法相反，它选择最大的可用块，这看起来最不容易产生碎片，但是却把最大的连续内存划分开，会很快导致没有可用的大内存块，因此性能也非常差。
          • 在动态分区分配中，与固定分区分配类似，设置一张空闲分区链(表)，并按始址排序。
          • 分配内存时，检索空闲分区链，找到所需的分区，若其大小大于请求大小，便从该分区中按请求大小分割一块空间分配给装入进程(若剩余部分小到不足以划分，则无须分割)，余下部分仍留在空闲分区链中。
          • 回收内存时，系统根据回收分区的始址，从空闲分区链中找到相应的插入点，此时可能出现四种情况:
            • ①回收区与插入点的前一空闲分区相邻，将这两个分区合并，并修改前一分区表项的大小为两者之和;
            • ②回收区与插入点的后一空闲分区相邻，将这两个分区合并，并修改后一分区表项的始址和大小:
            • ③回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，取消后一分区表项:
            • 4 回收区没有相邻的空闲分区，此时应为回收区新建一个表项，填写始址和大小，并插入空闲分区链。
        • 以上三种内存分区管理方法有一个共同特点，即用户程序在主存中都是连续存放的。在连续分配方式中，即使内存有超过1GB的空闲空间，但若没有连续的1GB空间，
        • 进程仍然无法运行。但若采用非连续分配方式，则进程要求的1GB内存空间可以分散地分配在内存的各个区域，当然这需要额外的空间去存储他们(分散区域)的索引；
        • 非连续分配方式的存储密度低于连续分配方式，非连续分配方式根据分区大小是否固定，分为
          • 分页存储管理：
            • 在分页存储管理中，又根据运行进程时是否要把进程的所有页面都装入内存才能运行，分为：
            • 基本分页存储管理，
            • 请求分页存储管理。
          • 分段存储管理；

      • 基本分页存储管理

        • 固定分区会产生内部碎片、动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生，这就引入了分页的思想:
        • 把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。
        • 分页的方法从形式上看，像分区相等的固定分区技术，分页管理不会产生外部碎片。但它又有本质的不同点:块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。
        • 这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片(也称页内碎片)；
        • 1 分页存储的几个基本概念
          • 1 页面和页面大小：
            • 进程中的块称为页或页面(Page)，内存中的块称为页框或页帧(Page Frame)。外存也以同样的单位进行划分，直接称为块或盘块(Block)，
            • 进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。为方便地址转换，页面大小应是2的整数幂。
            • 同时页面大小应该适中，页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；
            • 页面过大又会使页内碎片增多，降低内存的利用率。
          • 2 地址结构
            • 分页存储管理的逻辑地址结构，页号p、页内逻辑偏移量w
            • 地址结构包含两部分:前一部分为页号P，后一部分为页内偏移量W。地址长度为32位，其中0~11 位为页内地址，即每页大小为4KB:12~31位为页号，即最多允许220页。
            • 地址结构决定了虚拟内存的寻址空间有多大。在实际问题中，页号、页内偏移、逻辑地址可能是用十进制数给出的，若题目用二进制地址的形式给出时，需要会转换。
          • 3 页表
            • 为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中。
            • 在配置页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射(168页图)。
            • 页表是由页表项组成的，页表项与地址结构容易混淆，页表项与地址都由两部分构成，而且第一部分都是页号，
            • 但页表项的第二部分是物理内存中的块号，而地址的第二部分是页内偏移，页表项的第二部分与地址的第二部分共同组成物理地址；
        • 2 基本地址变换机构
          • 地址变换机构的任务是将逻辑地址转换成内存中的物理地址。地址变换是借助于页表实现的；
          • 分页存储管理系统中的地址变换机构：
            • 页表寄存器(页表起始地址F、页表长度M)->越界中断->逻辑地址(页号P、页内偏移量W)->页表(页号、块号)->物理地址E(b、W)
          • 在系统中通常设置一个页表寄存器(PTR)，存放页表在内存的起始地址F和页表长度M。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中，
          • 当进程被调度执行时，才将页表始址和页表长度装入页表寄存器中。设页面大小为L，逻辑地址A到物理地址E变换过程如下(假设逻辑地址、页号、每页的长度都是十进制数):
          • 例如：
            • 1 计算页号P(P=A/L)和页内偏移量W(W=A%L)。
            • 2 比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。
            • 3 页表中页号P对应的页表项地址=页表始址F+页号Px页表项长度，取出该页表项内容b，即为物理块号。注意区分页表长度和页表项长度。页表长度是指一共有多少页，页表项长度是指页地址占多大的存储空间。
            • 4 计算E=bxL+W,用得到的物理地址E去访问内存。
            • 以上整个地址变换过程均是由硬件自动完成的。
          • 计算条件用十进制数和用二进制数给出，过程会稍有不同。页式管理只需给出一个整数就能确定对应的物理地址，因为页面大小L是固定的。因此，页式管理中地址空间是一维的。
          • 页表项的大小不是随意规定的，而是有所约束的。如何确定页表项的大小?
          • 页表项的作用是找到该页在内存中的位置。当然，也可选择更大的页表项让一个页面能够正好容下整数个页表项，进而方便存储，或增加一些其他信息。
          • 下面讨论分页管理方式存在的两个主要问题:
            • ①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低;
            • ②每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。
        • 3 具有快表的地址变换机构
          • 若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存:
            • 第一次是访问页表，确定所存取的数据或指令的物理地址;
            • 第二次是根据该地址存取数据或指令。显然，这种方法比通常执行指令的速度慢了一半。
          • 为此，在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器快表,又称相联存储器(TLB),用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表常称为慢表；
          • 在具有快表的分页机制中，地址的变换过程如下:
            • (1) CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
            • (2) 若找到匹配的页号，说明所要访问的页表项在快表中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。这样，存取数据仅一次访存便可实现。
            • (3) 若未找到匹配的页号，则需要访问主存中的页表，读出页表项后，应同时将其存入快表，以便后面可能的再次访问。若快表已满，则须按特定的算法淘汰一个旧页表项。
            • 注意:有些处理机设计为快表和慢表同时查找，若在快表中查找成功则终止慢表的查找.
            • 一般快表的命中率可达90%以上，这样分页带来的速度损失就可降低至10%以下，快表有效性基于著名的局部性原理；
          • 两级页表
            • 由于引入了分页管理，进程在执行时不需要将所有页调入内存页框，而只需将保存有映射关系的页表调入内存；
            • 页表项并不需要同时保存在内存中，因为在大多数情况下，映射所需要的页表项都在页表的同一个页面中；
            • 为了压缩页表，进一步延伸页表映射的思想，就可得到二级分页，即使用层次结构的页表，将页表的10页空间也进行地址映射，建立上一级页表，用于存储页表的映射关系。
            • 若不把这些页表放在连续的空间里，则需要一张索引表来告诉我们第几张页表该上哪里去找，这能解决页表的查询问题,且不用把所有的页表都调入内存，
            • 只在需要它时才调入(虚拟存储器思想)，因此能解决占用内存空间过大的问题。
            • 这个方案就和当初引进页表机制的方式一模一样，实际上就是构造一个页表的页表,也就是二级页表，为查询方便，顶级页最多只能有1个页面(一定要记住这个规定)，
            • 正好使得二级页表的大小在一页之内，这样就得到了逻辑地址空间的格式；
            • 逻辑地址空间的格式：一级页号、二级页号页内偏移；
            • 二级页表实际上是在原有页表结构上再加上一层页表，建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项。
            • 二级页表示意图：171页；
        • 基本分段存储管理
          • 分页管理方式是从计算机的角度考虑设计的，目的是提高内存的利用率，提升计算机的性能。分页通过硬件机制实现，对用户完全透明。
          • 分段管理方式的提出则考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
          • 1 分段
            • 在页式系统中，逻辑地址的页号和页内偏移量对用户是透明的，
            • 但在段式系统中，段号和段内偏移量必须由用户显式提供，在高级程序设计语言中这个工作由编译程序完成。
            • 段式管理方式按照用户进程中的自然段划分逻辑空间。例如，用户进程由主程序段、两个子程序段、栈段和数据段组成，于是可以把这个用户进程划分为5段，
            • 每段从0开始编址，并分配一段连续的地址空间(段内要求连续，段间不要求连续，因此整个作业的地址空间是二维的)，其逻辑地址由段号S与段内偏移量W两部分组成。
          • 2 段表
            • 每个进程都有一张逻辑空间与内存空间映射的段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。段表的内容(段号、段长、本段在主存的起始地址)
            • 配置段表后，执行中的进程可通过查找段表，找到每段所对应的内存区，可见段表用于实现从逻辑段到内存区的映射；
            • 利用段表实现物理内存区映射：进程空间->段表(段号、段长、本段在主存的起始地址)->内存空间
          • 3 地址变换机构
            • 为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址F和段表长度M。从逻辑地址A到物理地址E之间的地址变换过程如下；
            • 分段系统的地址变换过程如下：
              • 逻辑地址A->比较段号S和段表长度M or 段表中段号S对应的段表项地址->计算从段表项中取出的起始址，用得到的物理地址E去访问内存；
              • ①从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。注意，在地址变换的题目中，要注意逻辑地址是用二进制数还是用十进制数给出的。
              • ②比较段号S和段表长度M，若S≥M，则产生越界中断，否则继续执行。
              • ③段表中段号S对应的段表项地址=段表始址F+段号Sx段表项长度，取出该段表项的前几位得到段长C。若段内偏移量≥C，则产生越界中断，否则继续执行。
              • 段表项实际上只有两部分，前几位是段长，后几位是始址。
              • ④取出段表项中该段的始址b，计算E=b+W，用得到的物理地址E去访问内存。
          • 4 段的共享与保护
            • 在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
            • 当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据。
            • 不能修改的代码称为纯代码或可重入代码(它不属于临界资源)，这样的代码和不能修改的数据可以共享，而可修改的代码和数据不能共享。
            • 与分页管理类似，分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。
            • 地址越界保护将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断;
            • 再将段表项中的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断。分页管理只需要判断页号是否越界，页内偏移是不可能越界的。
            • 与页式管理不同，段式管理不能通过给出一个整数便确定对应的物理地址，因为每段的长度是不固定的，无法通过整数除法得出段号，无法通过求余得出段内偏移，
            • 所以段号和段内偏移一定要显式给出(段号，段内偏移)，因此分段管理的地址空间是二维的。
        • 段页式管理
          • 分页存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享和保护。将这两种存储管理方法结合起来，便形成了段页式存储管理方式。
          • 在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页。
          • 对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位，段表(页表长度，页表起始地址)->页表->主存；
          • 在段页式系统中，作业的逻辑地址分为三部分：段号、页号和页内偏移量；
          • 为了实现地址变换，系统为每个进程建立一张段表，每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址，页表表项中至少包括页号和块号。
          • 此外，系统中还应该有一个段表寄存器，指出进程的段表起始地址和段表长度。段表寄存器和页表寄存器的作用都有两个，一是在段表或页表中寻址，二是判断是否越界；
          • 在一个进程中，段表只有一个，也页表可能有多个；
          • 在进行地址变换时，进行一次访问实际需要三次访问主存，首先通过段表查到页表起始地址，然后通过页表找到页帧号，最后形成物理地址。这里也可以通过快表来加速查找；
          • 段页式管理的地址空间是二维的；

• 虚拟内存管理

  • 虚拟内存基本概念
    • 1 传统存储管理方式的特征
      • 各种内存管理策略都是为了同时将多个进程保存在内存中，他们都具有以下两个特征
        • 1. 一次性：进程必须一次性全部装入内存，才能开始运行，这会导致两种情况
          • 1 当进程很大时不能全部被装入内存，将使该进程无法运行
          • 2 当大量进程要求运行时，由于内存不足以容纳这些进程，只能使少数进程先运行，导致多道程序度的下降；
        • 2. 驻留性：作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。运行中会因为I/O阻塞而被阻塞，可能处理长期等待；
      • 由以上可知，许多程序在运行中不用或暂时不用的程序(数据)占据了大量的内存空间，而一些需要允许的程序又无法装入运行，显然浪费了宝贵的内存资源。
    • 2 局部性原理
      • 要真正理解虚拟内存技术的思想，首先须了解著名的局部性原理。从广义上讲，快表、页高速缓存及虚拟内存技术都属于高速缓存技术，这个技术所依赖的原理就是局部性原理。
      • 局部性原理既适用于程序结构，又适用于数据结构(goto语句有害是出于对程序局部性原理的深刻认识和理解)。
      • 局部性原理表现在以下两个方面：
        • 1. 时间局部性：程序中的某条指令一旦执行，不久后该指令可能再次执行。某数据被访问过，不久后该数据可能再次被访问，产生的原因是程序中存在着大量的循环操作。
        • 2. 空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，
        • 因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。
      • 时间局部性通过将近来使用的指令和数据保存到高速缓存中，并使用高速缓存的层次结构实现。
      • 空间局部性通常使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。
      • 虚拟内存技术实际上建立了“内存一外存”的两级存储器结构，利用局部性原理实现高速缓存。
    • 3 虚拟存储器的定义和特征
      • 基于局部性原理，在程序装入时，仅须将程序当前要运行的少数页面或段先装入内存，而将其余部分暂留在外存，便可启动程序执行。
      • 在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。
      • 另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
      • 之所以将其称为虚拟存储器，是因为这种存储器实际上并不存在，只是由于系统提供了部分装入和置换功能后，给用户的感觉是好像存在一个比实际物理内大得多的存储器，但容量大只是一种错觉，是虚的；
      • 虚拟存储器有以下三个主要特征
        • 1. 多次性：是指无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内i存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。
        • 以后每当要运行到尚未调入的那部分程序时，再将它调入，多次性是虚拟存储器最重要的特征。
        • 2. 对换性：是指无须在作业运行时一直常驻内存，在进程运行期间，允许将那些暂不使用(换进)的程序和数据从内存调至外存的对换区(换出)。
        • 待以后需要时再将它们从外存调至内存量、正是由于对换性，才使得虚拟存储器得以正常运行。
        • 3. 虚拟性：是指从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容。这是虚拟存储器所表现出的最重要特征，也是实现虚拟存储器的最重要目标。
    • 4 虚拟内存技术的实现
      • 虚拟内存技术允许将一个作业分多次调入内存。采用连续分配方式时，会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，
      • 而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。
      • 虚拟内存的实现有以下三种方式：
        • 请求分页存储管理
        • 请求分段存储管理
        • 请求段页式存储管理
      • 不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面
        • 一定容量的内存和外存。
        • 页表机制(或段表机制)，作为主要的数据结构。
        • 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。
        • 地址变换机构，逻辑地址到物理地址的变换。
  • 请求分页管理方式
    • 请求分页系统建立在基本分页系统基础之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
    • 在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。
    • 在作业执行过程中，当所要访问的页面不在内存中时，再通过调页功能将其调入，同时还可通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。
    • 为了实现请求分页，系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统，还需要有页表机制、缺页中断机构和地址变换机构。
    • 1 页表机制
      • 请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业的运行过程中，必然会出现要访问的页面不在内存中的情况，
      • 请求分页系统中的页表项：页号、物理块号、状态位P、访问字段A、修改位M、外存地址，增加的4个字段说明如下：
      • 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
      • 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考；
      • 修改位M：标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存；
      • 外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
    • 2 缺页中断机构
      • 在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞(调页完成唤醒)，
      • 若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页(若被淘汰页在内存期间被修改过，则要将其写回外存)。
      • 缺页中断作为中断，同样要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比，它有以下两个明显的区别:
      • 1. 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部异常。
      • 2. 一条指令在执行期间，可能产生多次缺页中断。
    • 3 地址变换机构
      • 请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存，又增加了某些功能而形成的，如产生和处理缺页中断，及从内存中换出一页的功能等等。在进行地址变换时，先检索快表:
      • 请求分页中的地址变换过程：见195页；
      • 若找到要访问的页，则修改页表项中的访问位(写指令还需要重置修改位)，然后利用页表项中给出的物理块号和页内地址形成物理地址。
      • 若未找到该页的页表项，则应到内存中去查找页表，再对比页表项中的状态位P，看该页是否已调入内存，若页面已调入，则将该页的页表写入快表，若快表已满，则需采用某种算法替换。
      • 若页面未调入，则产生缺页中断，请求从外存把该页调入内存。
  • 叶匡分配
    • 1 驻留集大小
      • 对于分页式的虚拟内存，在进程准备执行时，不需要也不可能把一个进程的所有页都读入主存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。
      • 给一个进程分配的物理页框的集合就是这个进程的驻留集。需要考虑以下几点:
      • 1. 分配给一个进程的页框越少，驻留在主存中的进程就越多，从而可提高CPU的利用率。
      • 2. 若一个进程在主存中的页面过少，则尽管有局部性原理，缺页率仍相对较高。
      • 3. 若分配的页框过多，则由于局部性原理，对该进程的缺页率没有太明显的影响。
    • 2 内存分配策略
      • 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出下面三种适用的策略。
      • (1)固定分配局部置换
        • 为每个进程分配一定数目的物理块，在进程运行期间都不改变。
        • 所谓局部置换，是指如果进程在运行中发生缺页，则只能从分配给该进程在内存的页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。
        • 实现这种策略时，难以确定应为每个进程分配的物理块数目，太少会频繁出现缺页中断，太多又会降低CPU和其他资源的利用率。
      • (2)可变分配全局置换
        • 先为每个进程分配一定数目的物理块，在进程运行期间可根据情况适当地增加或减少。
        • 所谓全局置换，是指如果进程在运行中发生缺页，系统从空闲物理块队列中取出一块分配给该进程，并将所缺页调入。
        • 这种方法比固定分配局部置换更加灵活，可以动态增加进程的物理块，但也存在弊端，如它会盲目地给进程增加物理块，从而导致系统多程序的并发能力下降。
      • (3)可变分配局部置换
        • 为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，因此不会影响其他进程的运行。
        • 若进程在运行中频繁地发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页率趋于适当程度；
        • 反之，若进程在运行中的缺页事特别低，则可适当减少分配给该进程的物理块，但不能引起其缺页率的明显增加。这种方法在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力。
        • 当然它需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的；
    • 3 物理块调入算法
      • 采用固定分配策略时，将系统中的空闲物理块分配给各个进程，可采用下述几种算法。
      • 1. 平均分配算法，将系统中所有可供分配的物理块平均分配给各个进程。
      • 2. 按比例分配算法，根据进程的大小按比例分配物理块；
      • 3. 优先分配算法，为重要和紧迫的进程分配较多的物理块。通常采用的方法是把所有可分配的物理块分成两部分：一部分按比例分配给各个进程，一部分则根据优先权分配；
    • 4 调入页面的时机
      • 为确定系统将进程运行时所缺的页面调入内存的时机，可采取以下两种调页策略:
      • 1. 预调页策略：根据局部性原理，一次调入若干相邻的页会比一次调入一页更高效。但若调入的一批页面中的大多数都未被访问，则又是低效的。
      • 因此，需要采用以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约50%。因此这种策略主要用于进程的首次调入，由程序员指出应先调入哪些页。
      • 2. 请求调页策略：进程在运行中需要访问的页面不在内存，便提出请求，由系统将其所需页面调入内存。
      • 由这种策略调入的页一定会被访问，且这种策略比较易于实现，因此目前的虚拟存储器大多采用此策略。其缺点是每次仅调入一页，增加了磁盘I/O开销。
      • 预调入实际上就是运行前的调入，请求调页实际上就是运行期间调入。
    • 5 从何处调入页面
      • 请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘I/O速度比文件区的更快。
      • 这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况:
      • 1. 系统拥有足够的对换区空间：可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
      • 2. 系统缺少足够的对换区空间：凡是不会被修改的文件都直接从文件区调入;而当换出这些页面时，由于它们未被修改而不必再将它们换出。
      • 但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入(因为读比写的速度快)。
      • 3. UNIX方式：与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于是放在对换区，因此在下次调入时应从对换区调入。
      • 进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入。
    • 6 如何调人页面
      • 当进程所访问的页面不在内存中时(存在位为0)，便向CPU发出缺页中断，中断响应后便转入缺页中断处理程序。
      • 该程序通过查找页表得到该页的物理块，此时如果内存未满，则启动磁盘I/O，将所缺页调入内存，并修改表。
      • 如果内存已满，则先按某种置换算法从内存中选出一页准备换出;如果该页未被修改过(修改位为0)，则无须将该页写回磁盘，但是，如果该页已被修改(修改位为1)，则必须将该页写回磁盘，
      • 然后将所缺页调入内存，并修改页表中的相应表项。置其存在位为1。调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。
  • 页面置换算法
    • 进程运行时，若其访何的页面不在内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。
    • 选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或以后较长时间内不会再访问的页面先调出。
    • 常见的置换算法有以下4种：
    • 1、最佳(OPT)置换算法
      • 最佳置换算法选择的被淘汰页而是以后永远不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率，
      • 然而，由于目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。但可利用该算法去评价其他算法。
      • 从(198页)图中可以看出采用最佳置换算法时的情况。
    • 2、先进先出(FIFO)页面置换算法
      • 优先淘汰最早进入内存的页面，即淘汰在内存中驻留时间最久的页面。该算法实现简单，只需把已调入内存的页面根据先后次序链接成队列，设置一个指针总是指向最老的页面。
      • 但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。利用 FIFO 算法，比最佳置换算法正好多一倍。
      • FIFO算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象，称为Belady异常。只有FIFO算法可能出现Belady异常，LRU和OPT算法永远不会出现Belady异常。
    • 3 最近最久未使用（LRU）置换算法
      • 选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。
      • 该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。
      • LRU算法根据各页以前的使用情况来判断，是“向前看”的，而最佳置换算法则根据各页以后的使用情况来判断，是“向后看”的。而页面过去和未来的走向之间并无必然联系。
      • LRU算法的性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。
    • 4 时钟（CLOCK）置换算法
      • LRU算法的性能接近OPT算法，但实现起来的开销大。因此，操作系统的设计者尝试了很多算，试图用比较小的开销接近LRU算法的性能，这类算法都是CLOCK算法的变体。
      • (1)简单的CLOCK 置换算法
        • 为每帧设置一位访问位，当某页首次被装入或被访问时，其访问位被置为1。对于替换算法，将内存中的所有页面视为一个循环队列，并有一个替换指针与之相关联，
        • 当某一页被替换时，该指针被设置指向被替换页面的下一页。在选择一页淘汰时，只需检查页的访问位。若为0，就选择该页换出;若为1，则将它置为0，暂不换出，
        • 给予该页第二次驻留内存的机会，再依次顺序检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。
        • 由于该算法是循环地检查各个页面的使用情况，故称CLOCK算法。但是，因为该算法只有一位访问位，而置换时将未使用过的页面换出，故又称最近未用(NRU)算法。
      • (2) 改进型CLOCK置换算法
        • 将一个页面换出时，若该页已被修改过，则要将该页写回磁盘，若该页未被修改过，则不必将它写回磁盘。可见，对于修改过的页面，替换代价更大。
        • 在改进型CLOCK算法中，除考虑页面使用情况外，还增加了置换代价（修改位）。在选择页面换出时，优先考虑既未使用过又未修改过的页面。
        • 由访问位A和修改位M可以组合成下面四种类型的页面:
          • 1类A=0,M=0:最近未被访问且未被修改，是最佳淘汰页。
          • 2类A-0,M=1:最近未被访问，但已被修改，不是很好的淘汰页。
          • 3类A=1,M=0:最近已被访问，但未被修改，可能再被访问。
          • 4类A=1,M=1:最近已被访问且已被修改，可能再被访问。
        • 内存中的每页必定都是这四类页面之一。在进行页面置换时，可采用与简单CLOCK算法类似的算法，差别在于该算法要同时检查访问位和修改位。
        • 算法执行过程如下:
          • 1. 从指针的当前位置开始，扫描循环队列，寻找A=0且M=0的1类页面，将遇到的第一个1类页面作为选中的淘汰页。在第一次扫描期间不改变访问位A。
          • 2. 若第1步失败，则进行第二轮扫描，寻找A=0且M=1的2类页面。将遇到的第一个2类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
          • 3. 若第2步也失败，则将指针返回到开始的位置，并将所有帧的访问位复0。重复第1步，并且若有必要，重复第2步，此时一定能找到被淘汰的页。
        • 改进型CLOCK算法优于简单CLOCK算法的地方在于，可减少磁盘的I/O操作次数，但为找了到一个可置换的页，可能要经过几轮扫描，即实现算法本身的开销将有所增加。
        • 操作系统中的页面置换算法都有一个原则，即尽可能保留访问过的页面，而淘汰未访问的页。简单的CLOCK算法只考虑页面是否被访问过；
        • 改进型CLOCK算法对这两类页面做了细分，分为修改过的页面和未修改的页面。因此，若有未使用过的页面，则当然优先将其中未修改过的页面换出。若全部页面都用过，还是优先将其中未修改过的页面换出。
  • 抖动和工作集
    • 1 抖动
      • 在页面置换过程中，一种最糟糕的情形是，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。
      • 系统发生抖动的根本原因是，系统中同时运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页，必须请求系统将所缺页面调入内存。
      • 这会使得在系统中排队等待页面调入/调出的进程数目增加。
      • 显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换入/换出，而几乎不能再去做任何有效的工作，进而导致发生处理机的利用率急剧下降并趋于零的情况。
      • 抖动是进程运行时出现的严重问题，必须采取相应的措施解决它。由于抖动的发生与系统为进程分配物理块的多少有关，于是又提出了关于进程工作集的概念。
    • 2 工作集
      • 工作集是指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。一般来说，工作集W可由时间t和工作集窗口大小来确定。
      • 实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，
      • 因此，若分配给进程的物理块小于工作集大小，则该进程就很有可能频繁缺页，所以为了防止这种抖动现象，一般来说分配给进程的物理块数(即驻留集大小)要大于工作集大小。
      • 工作集模型的原理是，让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。
      • 落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集中换出。若还有空闲物理块，则可再调一个进程到内存。
      • 若所有进程的工作集之和超过了可用物理块总数，则操作系统会暂停一个进程，将其页面调出并将物理块分配给其他进程，防止出现抖动现象。
  • 内存映射文件
    • 内存映射文件(Memory-MappedFiles)与虚拟内存有些相似，将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，
    • 而不必执行文件IO操作，也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。
    • 使用内存映射文件所进行的任何实际交互都是在内存中进行的，并且是以标准的内存地址形式来访问的、磁盘的周期性分页是由操作系统在后台隐蔽实现的，对应用程序而言是完全透明的，
    • 系统内存中的所有页面都由虚拟存储器负责管理，虚拟存储器以统一的方式处理所有磁盘1/O.当进程退出或显式地解除文件映射时，所有被改动的页面会被写回磁盘文件。
    • 多个进程允许并发地内存映射同一文件，以便允许数据共享。实际上，很多时候，共享内存是通过内存映射来实现的。
    • 进程可以通过共享内存来通信，而共享内存是通过映射相同文件到道信进程的虚拟地址空间实现的。内存映射文件充当通信进程之间的共享内存区域。
    • 一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。
  • 虚拟存储器性能影响因素
    • 缺页率(缺页率高即为抖动)是影响虚拟存储器性能的主要因素，且缺页率又受到页面大小、分配给进程的物理块数(取决于工作集)、页面置换算法以及程序的编制方法的影响。
    • 根据局部性原理，页面较大则缺页率较低，页面较小则缺页率较高。
    • 页面较小时，一方面减少了内存碎片，有利于提高内存利用率;另一方面，也会使每个进程要求较多的页面，导致页表过长，占用大量内存。
    • 页面较大时，虽然可以减少页表长度，但会使页内碎片增大。
    • 分配给进程的物理块数越多，缺页率就越低，但是当物理块超过某个数目时，再为进程增加一个物理块对缺页率的改善是不明显的。
    • 可见，此时已没有必要再为它分配更多的物理块，否则也只能是浪费内存空间。只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。
    • 好的页面置换算法可使进程在运行过程中具有较低的缺页率。选择LRU、CLOCK等置换算法，将未来有可能访问的页面尽量保留在内存中，从而提高页面的访问速度。
    • 写回磁盘的频率。换出已修改过的页面时，应当写回磁盘，如果每当一个页面被换出时就将它写回磁盘，那么每换出一个页面就需要启动一次磁盘，效率极低，
    • 为此在系统中建立一个已修改换出页面的链表，对每个要被换出的页面(已修改)，可以暂不将它们写回磁盘，而将它们挂在该链表上，
    • 仅当被换出页面数达到给定值时，才将它们一起写回磁盘，这样就可显著减少磁盘I/O的次数,即减少已修改页面换出的开销。
    • 此外，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面，就不需从外存调入，而直接从已修改换出页面链表上获取，这样也可以减少页面从磁盘读入内存的频率，减少页面换进的开销。
    • 编写的程序局部化程度越高，执行时的缺页率就越低。如果存储采用的是按行存储，访问时就要尽量采用相同的方式，避免按列访问造成缺页率过高的现象；
  • 问题
    • 1 为什么要引入虚拟内存？
    • 2 虚拟内存空间的大小由什么因素决定？
    • 3 虚拟内存是怎么解决问题的？会带来什么问题？

4、文件管理

考纲内容-4

• 文件
  • 文件的基本概念：文件元数据和索引结点（inode）
  • 文件的操作：建立、删除、打开、关闭、读、写
  • 文件的保护：文件的逻辑结构，文件的物理结构
• 目录
  • 目录的基本概念
    • 树形目录
    • 目录的操作
    • 硬链接与软连接
• 文件系统
  • 文件系统的全局结构
    • 文件系统在外存中的结构
    • 文件系统的内存中的结构
  • 外存空闲空间管理办法
    • 虚拟文件系统
    • 文件系统挂载(mounting)

文件系统基础

• 文件的基本概念

  • 文件是信息集合，是以硬盘为载体存储在计算机上的；
  • 在用户进行输入和输出中，是以文件为基本单位；
  • 文件管理系统，是操作系统中的文件系统，实现对文件的维护管理，例如将文件用于程序的输入和输出、访问、修改和保存文件；
  • 文件的组成：
    • 一块存储空间，更准确地说，是存储空间中的数据(书本中的内容)
    • 对文件进行分类和索引，所以文件必须包含分类和索引信息。用于对成千上万的数据进行划分和管理；
    • 文件访问权限的信息，便于设置不同用户对不同数据的访问权限；
  • 从用户角度看文件系统需要提供的功能
    • 如何命名、分类、查找文件
    • 如何保证文件数据的安全性及对文件可以进程的操作有哪些；
    • 对文件如何存储在辅存上，如何管理文件辅存区域等方面不关心；
  • 文件的结构
    • 数据项：是文件系统中最低级的数据组织形式，可分为以下两种类型
      • 基本数据项：用于描述一个对象的某种属性的一个值，是数据中的最小逻辑单位。
      • 组合数据项：由多个基本数据项组成。
    • 记录：是一组相关的数据项的集合，用于描述一个对象在某方面的属性。
    • 文件：具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。
      • 在有结构的文件中，文件由若干个相似的记录组成，如一个班的学生记录；
      • 而无结构文件则被视为一个字符流，比如一个二进制文件或字符文件。
  • 文件可以是数字、字符或二进代码，基本访问单元可以是字节或记录。文件可以长期存储在硬盘中，允许可控制的进程间共享访问，能够被组织成复杂的结构。

• 文件控制块和索引结点

  • 文件的属性
    • 名称
    • 类型
    • 创建者
    • 位置：指向设备和设备上文件的指针；
    • 大小
    • 保护：对文件进行保护的访问控制信息；
    • 创建时间：最后一次修改、最后一次存取时间，这些信息用户跟踪文件的使用；
    • 这些附加信息称为文件属性或文件元数据，操作系统通过文件控制块（FCB）来维护文件元数据；
  • 文件控制块
    • 用来存放控制文件需要的各种信息和数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项；
    • 创建一个文件，操作系统就会分配一个FCB，并存放在文件目录中，一个文目录也被视为一个文件，称为目录文件；
    • PCB包含以下信息
      • 基本信息：文件名、文件的物理位置、文件的逻辑结构、文件的物理机构等；
      • 存取控制信息：各种用户的的存取权限；
      • 使用信息：文件创建时间、上次修改时间、上次修改时间等；
  • 索引结点
    • 文件目录通常存放在磁盘上，在查找目录时需要从磁盘的第一个盘块中的目录调入内存，然后用给定的文件名逐一比较，检索一般只需要用到文件名；
    • 为了方便文件目录的检索，采用了文件名和文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点(inode);
    • 在文件目录中，每个目录项仅由文件名和指向该文件所对应的i结点的指针构成；
    • 假设一个FCB为64B，盘块大小为1KB，则每个盘块可以存放16个FCB(FCB必须连续存放)，若一个文件目录共有640个FCB，则查找文件平均需要启动磁盘20次；
    • 在unix系统中，一个目录项占16B，其中14B是文件名，2B是i结点指针；这样存储目录可以减少查找文件的平均启动磁盘次数1/4，大大节省了系统开销；
    • 1 磁盘索引结点，每个文件有一个唯一的磁盘索引结点，主要包括以下内容：
      • 文件主标识符：拥有该文件的个人或小组的标识符
      • 文件类型：包括普通文件、目录文件或IO文件
      • 文件存取权限
      • 文件物理地址：每个索引结点中含有13个地址项，即iaddr(O)~iaddr(12)。它们以直接或间接方式给出数据文件所在盘块的编号。
      • 文件长度：指以字节为单位的文件长度。
      • 文件链接计数：软硬链接数量，在本文件系统中所有指向该文件的文件名的指针计数。
      • 文件存取时间、本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。
    • 2 内存索引结点，是指存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点复制到内存的索引结点中，便于以后使用。增加了以下内容
      • 索引结点编号：用于标识内存索引结点。
      • 状态：指示i结点是否上锁或被修改。
      • 访问计数：每当有一进程要访问此i结点时，计数加1，访问结束减1。
      • 逻辑设备号：文件所属文件系统的逻辑设备号。
      • 链接指针：设置分别指向空闲链表和散列队列的指针。

• 文件的操作

  • 文件的基本操作
    • pre：文件属于抽象数据类型。为了正确地定义文件，操作系统提供系统调用对文件进行创建、写、读、重定位、删除和截断等操作。
    • 创建文件：创建文件有两个必要步骤：1是为新文件分配必要的外存空间，2是在目录中为之创建一个目录项；
    • 写文件：为了写文件，执行一个系统调用。对于给定文件名，搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每次写操作时便更新写指针。
    • 读文件：为了读文件，执行一个系统调用。同样需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。
    • 重新定位文件：也称文件定位。搜索目录以找到适当的条目，并将当前文件位置指针重新定位到给定值。重新定位文件不涉及读、写文件。
    • 删除文件：为了删除文件，先从目录中检索指定文件名的目录项，然后释放该文件所占的存储空间，以便可被其他文件重复使用，并删除目录条目。
    • 截断文件：允许文件所有属性不变，并删除文件内容，将其长度置为0并释放其空间。
  • 文件的打开与关闭
    • 打开文件信息的表
      • 操作系统维护一个包含所有打开文件信息的表（打开文件表），可以节省再次搜索目录的开销，系统调用close时，打开文件表中删除这一条目；
      • 当用户对一个文件实施操作时，每次都要从检索目录开始。为了避免多次重复地检索目录，在文件使用之前通过系统调用open根据文件名搜索目录，
      • 从外存复制到内存打开文件表的一个表目中。当用户再次向系统发出文件操作请求时，可通过索引在打开文件表中找；
    • 多个进程同时打开文件的操作系统中，通常采用两级表：
      • 整个系统表：整个系统的打开文件表包含FCB的副本及其他信息。
      • 每个进程表：每个进程的打开文件表根据它打开的所有文件，包含指向系统表中适当条目的指针。
      • 一旦有进程打开了一个文件，系统表就包含该支分的条目。当另一个进程执行调用open时，只不过是在其文件打开表中增加一个条目，
      • 并指向系统表的相应条目、通常、系统打开文件表为每个文件关联一个打开计数器(OpenCount)，以记录多少进程打开了该文件。
      • 当打开计数器为0时，可从系统打开文件表中删除相应条目。
  • 文件名不必是打开文件表的一部分，因为一旦完成对FCB在磁盘上的定位，系统就不再使用文件名。
  • 对于访问打开文件表的索引，UNIX称之为文件描述符，而Windows称之为文件句柄。因此，只要文件未被关闭，所有文件操作就通过打开文件表来进行。
  • 每个打开文件都具有如下关联信息：
    • 文件指针：系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
    • 文件打开计数：计数器跟踪当前文件打开和关闭的数量，因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。
    • 文件磁盘位置：大多数文件操作要求系统修改文件数据，查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息。
    • 访问权限：每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)。该信息保存在进程的打开文件表中，以便系统能够允许或拒绝后续的I/O请求。

• 文件的保护

  • 概念：为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。
  • 文件系统中建立相应的文件保护机制，有以下方式：
    • 口令保护、加密保护：口令和加密为了防止用户文件被他人存取或窃取；
    • 访问控制：访问控制则用于控制用户对文件的访问方式；
  • 访问类型
    • 对文件的保护可从限制对文件的访问类型中出发，可加以控制的访问类型主要有以下几种：
      • 读、写、执行、添加(将信息添加到文件结尾部分)、删除、列表清单(列出文件名和文件属性)、重命名、复制、编辑；
    • 访问控制
      • 拥有者：文件的创建者；
      • 组：一组需要共享文件且具有类似访问的用户；
      • 其它：系统内的所有其他用户；
      • 这样只需要三个域即可列出访问表中的三类用户的访问权限，这些权限在改文件的FCB中；

• 文件的逻辑结构

  • pre：文件的逻辑结构与存储介质无关，它是指文件在内部，数据逻辑上是如何组织起来的，从用户观点出发看到的文件的组织形式；
  • 1 无结构文件（流式文件）
    • 无结构文件是最简单的文件组织形式，将数据按顺序组织保存，以字节(Byte)为单位；适合于字符流的方式有源程序文件、目标代码文件；
  • 2 有结构文件（记录式文件）
    • 顺序文件
      • 文件的中记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储也可以链式存储；
      • 顺序文件有以下两种结构：
        • 串结构：记录之间的顺序与关键字无关，按存入时间的先后进行排列，检索时必须从头开始顺序依次查找，比较费时；
        • 顺序结构：
          • 按文件中所有记录的关键字顺序排列，可采用折半查找，提高了检索效率。
          • 顺序结构也适合对记录进行批量操作，每次读写一大批记录，是所有逻辑结构中效率最高的；
          • 对于顺序存储设备（磁带），也只有顺序存储才能被存储并有效的工作；
          • 在经常需要查找、修改、增加或删除单个记录的场合，顺序文件的性能也比较差；
    • 索引文件
      • 索引表按关键字排序，为主文件中的每个记录在索引表中分别设置一个表项，包含指向变长记录的指针（即逻辑地址地址）和记录长度；
      • 索引文件本身也是一个定长记录的顺序文件，是把对变长记录顺序文件的检索转变为对定长记录索引文件的随机检索，从而加快了记录的索引速度；
    • 索引顺序文件
      • 索引顺序文件是顺序文件和索引文件的结构，最简单的索引文件只使用了一级索引。索引顺序文件将顺序文件中的所有记录分为若干组，
      • 为顺序文件建立一张索引表，在索引表中为组中的第一条记录建立一个索引项，组与组之间的关键字有序排列，其中包含该记录的关键字值和指向该记录的指针；
      • 查找一条数时，首先通过索引表找到其所在的组，然后在该组中使用顺序查找，就能很快地找到记录；
      • 索引文件和索引顺序文件都提高了存取的速度，但因为配置索引表而增加了存储空间；
    • 直接文件或散列文件（Hash File）
      • 给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。
      • 散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。
    • 有结构文件逻辑上的组织，是为在文件中查找数据服务的(顺序查找、索引查找、索引顺序查找、哈希查找)。
    • 文件实际上是一种抽象数据类型，我们要研究它的逻辑结构、物理结构，以及关于它的一系列操作。

• 文件的物理结构

  • 文件的物理结构就是研究文件数据在物理存储设备上是如何分布和组织的，对这个问题有两个方面的回答:
    • 一是文件的分配方式，讲的是对磁盘非空闲块的管理；
    • 二是文件存储空间管理，讲的是对磁盘空闲块的管理(详见4.3节)。
  • pre：文件分配对应于文件的物理结构，是指如何为文件分配磁盘块，常用的磁盘空间分配方法有如下三种：
  • 连续分配：
    • 连续分配方法要求每个文件在磁盘上占有一组连续的的块，磁盘地址定义了磁盘上的一个线性排序；
    • 连续分配时，逻辑文件中的记录也是顺序的存储在相邻接的块中。连续分配支持顺序访问和直接访问；
    • 连续分配的优缺点：
      • 优点：是实现简单、存取速度快。
      • 缺点：
        • 1是文件长度不宜动态增加，
        • 2为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动，
        • 3删除会产生外部碎片；
        • 4很难确定一个文件需要的空间大小，因而只适用于长度固定的文件；
  • 链接分配
    • 链接分配是一种采用离散分配的方式。它消除了磁盘的外部碎片，提高了磁盘的利用率。可以动态地为文件分配盘块，因此无须事先知道文件的大小。
    • 此外，对文件的插入、删除和修改也非常方便。链接分配又可分为隐式链接和显式链接两种形式：
      • 隐式链接：
        • 目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表;
        • 磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都含有指向文件下一个盘块的指针，这些指针对用户是透明的。
        • 隐式链接的缺点
          • 是只适合顺序访问，若要访问文件的第i个盘块，则只能从第1个盘块开始通过盘块指针顺序查找到第i块，随机访问效率很低。
          • 隐式链接的稳定性也是一个问题，系统在运行过程中由于软件或硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。
        • 通常的解决方案是，
          • 将几个盘块组成簇(cluster),按簇而不按块来分配，可以成倍地减少查找时间。比如一簇为4块，这样指针所占的磁盘空间比例也要小得多；
          • 这种方法的代价是增加了内部碎片，簇可以改善许多算法的磁盘访问时间，因此应用于大多数操作系统；
      • 显示链接
        • 放在内存的一张链接表中。该表在整个磁盘中仅设置一张，称为文件分配表(File Allocation Table, FAT)。每个表项中存放链接指针，即下一个盘块号。
        • 文件的第一个盘块号记录在目录项“物理地址”字段中，后续的盘块号可以通过查FAT找到；FAT的表项与全部磁盘块一一对应，用-1表示文件的最后一块，-2表空闲；
        • FAT不仅记录了文件各块之间的先后链接关系，同时还标记了空闲的磁盘块，操作系统也通过FAT对文件存储空间进行管理；进程请求磁盘块时，OS在FAT中找-2的表项；
        • FAT在操作系统启动时就会被读入内存，明显的减少了访问磁盘的次数；
        • 例如，某磁盘共有100个磁盘块、存放了两个文件:文件“aaa”占三个盘块，依次是2-8→5:文件“bbb”占两个盘块，依次是7一1。其余盘块都是空闲盘块；
  • 索引分配
    • 链接分配解决了连续分配的外部碎片和文件大小管理的问题。但依然存在问题:
      • ①链接分配不能有效支持直接访问(FAT除外);
      • ②FAT需要占用较大的内存空间。事实上，在打开某个文件时，只需将该文件对应盘块的编号调入内存即可，没必要将整个FAT调入内存；
      • 为此，索引分配将每个文件所有的盘块号都集中放在一起构成索引表(见，238页索引分配图)；
      • 每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第i个条目指向文件的第个块。第1块，通过索引块的第i个条目的指针来查找和读入所需的块。
      • 优缺点：
        • 索引分配的优点是支持直接访问，且没有外部碎片问题。
        • 缺点是由于索引块的分配，增加了系统存储空间的开销。索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但太小就无法支持大文件。
        • 可以采用以下机制来处理这个问题。
        • 链接方案：一个索引块通常为一个磁盘块，因此它本身能直接读写。为了支持大文件，可以将多个索引块链接起来。
        • 多层索引：通过第一级索引块指向一组第二级的索引块，第二级索引块再指向文件块。查找时，通过第一级索引查找第二级索引，再采用这个第二级索引查找所需数据块。
        • 混合索引：将多种索引分配方式相结合的分配方式。例如，系统既采用直接地址，又采用单级索引分配方式或两级索引分配方式。
      • 访问文件需两次访问外存，先读取索引块的内容，然后访问具体的磁盘块，因而降低了文件的存取速度。为了解决这一问题，通常将文件的索引块读入内存，以提高访问速度。
  • 混合索引分配
    • 为了能够较全面地照顾到小型、中型、大型和特大型文件，可采用混合索引分配方式。
    • 对于小文件，为了提高对众多小文件的访问速度，最好能将它们的每个盘块地址直接放入FCB,这样就可以直接从FCB中获得该文件的盘块地址，即为直接寻址。
    • 对于中型文件，可以采用单级索引方式，需要先从FCB中找到该文件的索引表，从中获得该文件的盘块地址，即为一次间址。inode结构图（239页）
    • 对于大型或特大型文件，可以采用两级和三级索引分配方式。UNIX系统采用的就是这种分配方式，在其索引结点中，共设有13个地址项，即i.addr(0)~i.addr(12)
      • 直接地址
        • 为了提高对文件的检索速度，在索引结点中可设置10个直接地址项，即用 i.addr(0)~i.addr(9)来存放直接地址，即文件数据盘块的盘块号。
      • 一次间接地址
        • 对于中、大型文件，只采用直接地址并不现实的。为此，可再利用索引结点中的地址项i.addr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。
        • 一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1024个盘块号，因而允许文件长达4MB。
      • 多次间接地址
      • 当文件长度大于4MB+40KB(一次间接地址与10个直接地址项)时，系统还需采用二次间接地址分配方式。这时，用地址项i.addr(11)提供二次间接地址。
      • 该方式的实质是两级索引分配方式。系统此时在二次间址块中记入所有一次间址块的盘号。
      • 地址项i.addr(11)作为二次间址块，允许文件最大长度可达4GB。同理，地址项iaddr(12)作为三次间址块，其允许的文件最大长度可达4TB

目录

• 目录的基本概念

  • FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。与文件管理系统和文件集合相关联的是文件目录，它包含有关文件的属性、位置和所有权等；

• 目录结构

  • 单级目录结构：在整个文件系统中只建立一张目录表，每个文件占一个目录项；
  • 两级目录结构：为了克服单级目录所存在的缺点，可以采用两级方案，将文件目录分成主文件目录(Master File Directory,MFD)和用户文件目录(UFD)两级；
  • 树形目录结构：
    • 将两级目录结构加以推广，就形成了树形目录结构，它可以明显地提高对目录的检索速度和文件系统的性能。从根目录出发到所找文件用分隔符“/”链接而成。
    • 在树形目录中查找一个文件，需要按路径名逐级访问中间结点，增加了磁盘访问次数。目前，大多数操作系统如UNIX、Linux和Windows系统都采用了树形文件目录。
  • 无环图目录结构：
    • 树形目录结构能便于实现文件分类，但不便于实现文件共享，为此在树形目录结构的基础上root为一个有向无环图增加了一些指向同一结点的有向边，
    • 使整个目录成为一个有向无环图。共享文件(或目录)不同于文件拷贝(副本)，对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见。
    • 无环图目录结构方便地实现了文件的共享，但使得系统的管理变得更加复杂。

• 目录的操作

  • 搜索。当用户使用一个文件时，需要搜索目录，以找到该文件的对应目录项。
  • 创建文件：当创建一个新文件时，需要在目录中增加一个目录项；
  • 删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
  • 创建目录：在树形目录结构中，用户可创建自己的用户文件目录，并可再创建子目录。
  • 删除目录：有两种方式:①不删除非空目录，删除时要先删除目录中的所有文件，并递归地删除子目录。②可删除非空目录，目录中的文件和子目录同时被删除。
  • 移动目录：将文件或子目录在不同的父目录之间移动，文件的路径名也会随之改变。
  • 显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性；
  • 修改目录：某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项。

• 目录的实现

  • 概述
    • 在访问一个文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。
    • 目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。
  • 线性列表
    • 最简单的目录实现方法是，采用文件名和数据块指针的线性列表。
    • 当要重用目录项时有许多种方法:可以将目录项标记为不再使用，或将它加到空闲目录项的列表上，还可以将目录的最后一个目录项复制到空闲位置,并减少目录的长度。
    • 采用链表结构可以减少删除文件的时间。线性列表的优点在于实现简单，不过由于线性表的特殊性，查找比较费时。
  • 哈希表
    • 采用哈希数据结构，哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。
    • 这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些措施来避免冲突(两个文件名称哈希到同一位置)。
  • 目录查询是通过在磁盘上反复搜索完成的，需要不断地进行I/O操作，开销较大。
    • 所以为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。

• 文件共享

  • pre：文件共享使多个用户共享同一个文件，系统中只需保留该文件的一个副本。现代常用的两种文件共享方法如下：
  • 基于索引结点的共享方式（硬链接）
    • 在这种共享方式中，诸如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。
    • 在索引结点中还有一个链接计数count，用于表示链接到本索引结点(即文件)上的用户目录项的数目。
    • 用户A创建一个新文件时，他便是该文件的所有者，此时将count置为1。用户B要共享此文件时，在B的目录中增加一个目录项，并设置一个指针指向该文件的索引结点。
    • 删除操作是删除该文件的索引结点，拥有者删除只是将该文件的count减1，然后删除自己目录中的相应目录项。用户B仍可以使用该文件。当count-0时，才会删除该文件。
  • 利用符号链实现文件共享（软连接）
    • 利用符号链方式实现文件共享时，只有文件主才拥有指向其索引结点的指针，而共享该文件的其他用户只有该文件的路径名，并不拥有指向其索引结点的指针。
    • 操作系统查看到要读的文件是LINK类型，则根据该文件中的路径名去找到文件F，然后对它进行读，从而实现用户B对文件F的共享。这样的链接方法被称为符号链接。
    • 当文件主把一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是将符号链删除，此时不会产生任何影响。
    • 当其他用户读软连接共享文件时，系统根据文件路径名逐个查找目录，直至找到该文件的索引结点。每次访问共享文件时，都可能要多次地读盘。
    • 使得访问文件的开销甚大，且增加了启动磁盘的频率。此外，符号链的索引结点也要耗费一定的磁盘空间。
  • 硬链接和软连接的区别：
    • 硬链接就是多个指针指向一个索引结点，保证只要还有一个指针指向索引结点，索引结点就不能删除;
    • 软链接就是把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。硬链接的查找速度要比软链接的快；
  • 硬链接和软链接都是文件系统中的静态共享方法，在文件系统中还存在着另外的共享需求，即两个进程同时对同一个文件进行操作，这样的共享称为动态共享。
  • 利用符号链实现网络文件共享时，只需提供该文件所在机器的网络地址及文件路径名。

文件系统

• 文件系统结构

  • 概述：
    • 文件系统提供高效和便捷的磁盘访问，以便允许存储、定位、提取数据。组织文件的目录结构；
    • 利用合理的算法和数据结构，以便映射逻辑文件系统到物理外存设备。操作系统有多种文件系统类型，因此文件系统的层次结构也不尽相同；
    • 合理的文件系统层次结构：应用程序->逻辑文件系统->文件组织模块->基本文件系统->I/O控制->设备
  • I/O控制：包括设备驱动程序和中断处理程序，在内存和磁盘系统之间传输信息，设备驱动程序告诉I/O控制器对设备的什么位置采取什么动作；
  • 基本文件系统：向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块。也管理内存缓冲区，并保存各种文件系统、目录和数据块的缓存；
  • 文件组织模块：组织文件及其逻辑块和物理块。文件组织模块可以将逻辑块地址转换成物理块地址，逻辑块与数据的物理块不匹配，需要通过转换来定位；
  • 逻辑文件系统：
    • 用于管理元数据信息，元数据信息包括文件系统的所有结构，而不包括实际数据(或文件内容)，逻辑文件系统管理目录结构；
    • 以便根据给定文件名称为文件组织模块提供所需要的信息。它通过文件控制块来维护文件结构，逻辑文件系统还负责文件保护；

• 文件系统布局

  • 文件系统在磁盘中的结构
    • 文件系统存放在磁盘上、多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统。
    • 文件系统可能包括如下信息，启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等(文件系统布局图266页);
    • 主引导记录(Master Boot Record)：
      • 位于磁盘的0号扇区，用来引导计算机，MBR后面是分区表，该表给出每个分区的起始和结束地址。
      • 表中的一个分区被标记为活动分区，当计算机启动时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一块，即引导块。
    • 引导块：
      • MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统，
      • 也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的。
    • 超级快(super block)：
      • 包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。
      • 超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
    • 文件系统中空闲块的信息：
      • 可以使用位示图或指针链接的形式给出。后面也许跟的是一组i结点,每个文件对应一个结点，i结点说明了文件的方方面面。
      • 接着可能是根目录，它存放文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。
  • 文件系统在内存中的结构
    • pre：内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新。这些结构的类型可能包括
    • 内存中的安装表：内存中的安装表(mount table)，包含每个已安装文件系统分区的有关信息。
    • 内存中的目录结构的缓存包含最近访问目录的信息：对安装分区的目录，它可以包括一个指向分区表的指针；
    • 整个系统的打开文件表：包含每个打开文件的FCB副本及其他信息；
    • 每个进程的打开文件表：包含一个指向整个系统的打开文件表中的适当条目的指针，以及其它信息；
  • 打开和关闭一个文件的流程：
    • pre：
      • 为了创建新的文件，应用程序调用逻辑文件系统，逻辑文件系统知道目录结构的格式，它将为文件分配一个新的FCB。
      • 然后，系统将应的目录读入内存，使用新的文件名和FCB进行更新，并将它写回磁盘。
      • 一旦文件被创建，它就能用于I/O。不过，首先要打开文件。系统调用open()将文件名传递给逻辑文件系统。
    • 打开
      • 调用open()首先搜索整个系统的打开文件表，以确定这个文件是否已被其他进程使用。如果已被使用，则在单个进程的打开文件表中创建一个条目，让其指向现有整个系统的打开文件表的相应条目。
      • 该算法在文件已打开时，能节省大量开销。如果这个文件尚未打开，则根据给定文件名来搜索目录结构，部分目录结构通常缓存在内存中，以加快目录操作。
      • 找到文件后，它的FCB会复制到整个系统的打开文件表中。该表不但存储FCB，而且跟踪打开该文件的进程的数量。
      • 然后，在单个进程的打开文件表中创建一个条目，并且通过指针将整个系统打开文件表的条目与其他域(如文件当前位置的指针和文件访问模式等)相连。
      • 调用open()返回的是一个指向单个进程的打开文件表中的适当条目的指针。以后，所有文件操作都通过该指针执行。
      • 一旦文件被打开，内核就不再使用文件名来访问文件，而使用文件描述符(Windows称之为文件句柄)。
    • 关闭
      • 当所有打开某个文件的用户都关闭该文件后，任何更新的元数据将复制到磁盘的目录结构中，并且整个系统的打开文件表的对应条目也会被删除。

• 外存空闲空间管理

  • 概述
    • 一个存储设备可以按整体用于文件系统，也可以细分。例如，一个磁盘可以划分为4个分区，每个分区都可以有单独的文件系统。
    • 包含文件系统的分区通常称为卷(volume)。卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成RAID集；
    • 在一个卷中，存放文件数据的空间(文件区)和FCB的空间(目录区)是分离的。
    • 由于存在很多种类的文件表示和存放格式，在OS中一般都有很多不同的文件管理模块，利用它们来访问不同格式的卷中的文件。
    • 卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块。
    • 文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲的织、分配与回收等问题。
  • 空闲表法
    • 系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列；
    • 空闲盘区的分配与内存的动态分配类似，为每个文件分配一块连续的存储空间，同样采用首次适应算法和最佳适应算法，例如，在系统为某新创建的的文件分配空闲盘块时，
    • 先顺序地检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户，同时修改空闲盘块表。
    • 系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲盘块表中插入点的前区和后区相邻接，对相邻接者应予以合并。
  • 空闲链表法
    • pre：将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，分为两种形式:
    • 空闲盘块链
      • 将磁盘上的所有空闲空间以盘块为单位拉成一条链。当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。
      • 当用户因删除文件而释放存储空间时，系统将回收的盘块依次插入空闲盘块链的末尾。这种方法的优点是分配和回收一个盘块的过程非常简单，
      • 但在为一个文件分配盘块时可能要重复操作多次，效率较低。又因它是以盘块为单位的，空闲盘块链会很长。
    • 空闲盘区链
      • 将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。每个盘区除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。
      • 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区合并。
      • 这种方法的优缺点刚好与第一种方法的相反，即分配与回收的过程比较复杂，但效率通常较高，且空闲盘区链较短。
  • 位示图法
    • 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。值为“0”时表示盘块空闲;为“1”时表示已分配。
    • 这样，一个 mn位组成的位示图就可用来表示mn个盘块的使用情况，无特殊说明，位示图法中行和列都从1开始编号；
    • 盘块的分配
      • 顺序扫描位示图：顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位。
      • 将找到的一个或一组二进制位转换成与之对应的盘块号，转换成与之对应的盘块号，将找位于位示图的第1行、第j列，转换按下式计算(n为每行位数)：b=n(i-1)+1；
      • 修改位示图：令 map[i,j]=1；
    • 盘块的回收
      • 将回收盘块的盘块号转换成位示图中的行号和列号：转换公式为：i=(b- 1)DIV n+1；j= (b-1)MOD n+1
      • 修改位示图：令 map[i,j]=0；
  • 成组链接法
    • 在UNIX中采用的是成组链接法(存放一组空闲盘块号的盘块)，这种方法结合了空闲表和空闲链表两种方法，有上述两种方法的优点，克服了两种方法均有的表太长的缺点。
    • 成组链接法的大致思想是：
      • 把顺序的n个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块(作为成组链块)则用于保存另一组空闲盘块号，
      • 如此继续，直至所有空闲盘块均予以链接，系统只需保存指向第一个成组链块的指针。见图(269)；
    • 盘块的分配
      • 根据第一个成组链块的指针，将其对应的盘块分配给用户，然后将指针下移一格。
      • 若该指针指向的是最后一个盘块(即成组链块)，由于该盘块记录的是下一组空闲盘块号，因此要将该盘块读入内存，并将指针指向新的成组链块的第一条记录，然后分配；
    • 盘块的回收
      • 成组链块的指针上移一格，再记入回收盘块号。当成组链块的链接数达到n时，表示已满，便将现有已记录n个空闲盘块号的成组链块号记入新回收的盘(作为新的成组链块)。
      • 表示空闲空间的位向量表或第一个成组链块，以及卷中的目录区、文件区划分信息都要存放在磁盘中，一般放在卷头位置，在UNIX系统中称为超级块
      • 在对卷中的文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与磁盘卷中超级块的一致性。

• 虚拟文件系统

  • 概念：
    • 虚拟文件系统j(VFS)为用户程序提供了文件系统操作的统一接口，屏蔽了不同文件系统的差异和操作细节。
    • 用户程序通过VFS提供的统一调用函数(如open)来操作不同的文件系统，而无须考虑具体的文件系统和实际的存储介质；
    • 虚拟文件系统采用了面向对象的思想，新的文件系统只需要支持并实现这些接口即可安装使用，例如write是调用VFS中的sys_write()处理，
    • sys_write()找到具体文件系统，将控制权交给该文件系统，最后由具体文件系统与物理储存介质交互并写入数据；
  • 为了实现VFS，OS抽象了四种对象类型：
    • pre：每个VFS对象都存放在一个适当的数据结构中，其中包括对象的属性和指向对象方法表的指针；
    • 超级块对象：表示一个已安装（或称挂载）的特定文件系统；
    • 索引结点对象：表示一个特定的文件；
    • 目录项对象：表示一个特定的目录项；
    • 文件对象：表示一个与进程相关的已打开文件；
  • Liunx将目录当作文件对象处理，文件系统是由层次目录组成的，目录项作为单独抽象的对象，是因为目录可以层层嵌套，以便形成文件路径，
  • 而路径中的每一部分其实就是目录项
    • 超级块对象：
      • 超级块对象对应于磁盘上特定扇区的文件系统超级块，用于存储已安装文件系统的元信息，
      • 元信息中包含文件系统的基本属性：
        • 文件系统类型、
        • 文件系统基本块的大小、
        • 文件系统所挂载的设备、
        • 操作方法（函数）指针等。其中操作方法（函数）指针指向该超级块的操作方法表；
        • 包含一些列可在超级块对象上调用的操作函数：主要有分配inode、销毁inode、读写inode、文件同步等；
    • 索引结点对象
      • 文件系统处理文件所需要的所有信息，都放在一个称为索引结点的数据结构中，索引结点对文件是唯一的。只有当文件被访问时，才在内存中创建索引结点对象；
      • 每个索引结点对象都会复制磁盘索引结点包含的一些数据，该对象中有一个状态字段表示是否被修改，其值为“脏”时，说明对应的磁盘索引结点必须被更新；
      • 索引结点对象还提供许多操作接口，如创建新索引结点、创建硬链接、创建新目录等；
    • 目录项对象
      • 由于VFS经常执行切换到某个目录这种操作，为了提高效率，便引入了目录项的概念、目录项对象是一个路径的组成部分，它要么是目录名，要么是文件名。
      • 例如，在查找路径名/test时，内核为根目录“/”创建一个目录项对象，为根目录下的test创建一个第二级目录项对象，目录项对象包含指向关联索引结点的指针，和指向父目录和指向子目录的指针。
      • 不同于前面两个对象，目录项对象在磁盘上没有对应的数据结构，而是VFS在遍历路径的过程中，将它们逐个解析成目录项对象的。
    • 文件对象
      • 文件对象代表进程打开的一个文件。可以通过open()调用打开一个文件，通过 close()调用关闭一个文件。文件对象和物理文件的关系类似于进程和程序的关系。
      • 由于多个进程可以打开和操作同一文件，所以同一文件在内存中可能存在多个对应的文件对象，但对应的索引结点和目录项是唯一的。
      • 文件对象仅在进程观点上代表已经打开的文件，它反过来指向其索引结点。
      • 文件对象包含：与该文件相关联的目录项对象、该文件的文件系统、文件指针等、还包含在该文件对象上调用的一系列操作函数(见271页图)。
    • 进程与VFS对象之间的交互：进程->文件对象->目录项对象->索引结点对象->超级块对象->磁盘文件；
    • VFS还有另一个重要作用
      • 即提高系统性能，最近最常使用的目录项对象被放在目录项高速缓存的磁盘缓存中，以加速从文件路径名到最后一个路径分量的索引结点的转换过程。
      • 严格来说，VFS并不是一种实际的文件系统，它只存在于内存中，不存在于任何外存空间中。VFS在系统启动时建立，在系统关闭时消亡。

• 分区和安装

  • 分区：
    • 一个磁盘可以划分为多个分区，每个分区都可以用于创建单独的文件系统，每个分区还可以包含不同的操作系统。分区可以是原始的，没有文件系统，
    • 当没有合适的文件系统时，可以使用原始磁盘，unix交换空间可以使用原始磁盘格式，而不使用文件系统；
    • 一个典型的linux分区，从前往后包含这4部分：
      • 引导块
        • 分区的第一部分是引导块，里面存储着引导信息，它有自身的格式，因为在引导时系统并未加载文件系统代码，因此不能解释文件系统的格式。
        • 引导信息是一系列可以加载到内存中的连续块，加载到内存后从其第一条代码开始执行，引导程序便启动一个具体的操作系统。
      • 超级块
        • 引导块之后是超级块，它存储文件系统的有关信息，包括文件系统的类型、i结点的数目、数据块的数目，
      • i结点
        • 随后是多个索引结点，它们是实现文件存储的关键，每个文件对应一个索引结点，索引结点中包含多个指针，指向属于该文件的各个数据块。
      • 文件数据块：
        • 最后是文件数据块。
  • 安装：
    • 如文件在使用前必须打开一样，文件系统在进程使用前必须先安装，也称挂载。
    • Windows系统维护一个扩展的两级目录结构，
      • 用驱动器字母表示设备和卷。卷具有常规树结构的目录,与驱动器号相关联，还含有指向已安装文件系统的指针。
      • 特定文件的路径形式为driver- letter:'path'to file,操作系统找到相应文件系统的指针，并且遍历该设备的目录结构，以查找指定的文件。
      • 新版本的Windows允许文件系统安装在目录树下的任意位置，就像UNIX一样。在启动时，Windows操作系统自动发现所有设备，并且安装所有找到的文件系统。
    • UNIX使用系统的根文件系统
      • 由内核在引导阶段直接安装，其他文件系统要么由初始化脚本安装，要么由用户安装在已安装文件系统的目录下。作为一个目录树，每个文件系统都拥有自己的根目录。
      • 安装文件系统的这个目录称为安装点，安装就是将磁盘分区挂载到该安装点下，进入该目录就可以读取该分区的数据。
      • 已安装文件系统属于安装点目录的一个子文件系统。安装的实现是在目录inode的内存副本上加上一个标志，表示该目录是安装点。
      • 还有一个域指向安装表的条目，表示哪个设备安装在哪里，这个条目还包括该设备的文件系统超级块的一个指针。
      • 假定将存放在/dev/fd0 软盘上的ext2 文件系统通过mount命令安装到/flp：mount -t ext2 /dev/fd0 /flp，如需卸载该文件系统，可以使用umount命令。
    • 我们可以这么理解:
      • UNIX本身是一个固定的目录树，只要安装就有，但是如果不给它分配存储空间，就不能对它进行操作，所以首先要给根目录分配空间，这样才能操作这个目录树。
      • 贯穿本章内容有两条主线:
      • 第一条主线是介绍一种新的抽象数据类型--文件，从逻辑结构和物理结构两个方面进行;
      • 第二条主线是操作系统是如何管理“文件”的，介绍了多文件的逻辑结构的组织，即目录，还介绍了如何处理用户对文件的服务请求，即磁盘管理。

5、I/O设备管理

考纲内容-5

• I/O管理基础
  • 设备：设备的基本概念，设备的分类，I/O接口，I/O端口
  • I/O控制方式：轮询方式、中断方式、DMA方式
  • I/O软件层次结构
    • 中断处理程序
    • 驱动程序
    • 设备独立性软件
    • 用户层I/O软件
    • 阻塞/非阻塞I/O
• 设备独立软件
  • 缓冲区管理
  • 设备分配与回收
  • 假脱机技术（SPOOLing）
  • 设备驱动程序接口
• 外存管理(文件系统)
  • 磁盘：磁盘结构、格式化、分区、磁盘调度方法
  • 固态硬盘：读写性能特效，磨损均衡

I/O管理概述

• I/O设备

  • pre：I/O设备包含了很多领域的不同设备及与设备相关的应用程序，因此这一块是操作系统设计中最具有挑战性的部分；
  • 设备的分类
    • 按信号交换的单位分类：
      • 块设备：以数据库为信息交换单位，属于有结构设备，如磁盘，可随机读、写任意一块，磁盘设备的基本特征是传输速度较高，可寻址；
      • 字符设备：信息交换以字符为单位，属于无结构类型，如交互式终端、打印机，它们基本特征是传输速度低，不可寻址，通常采用中断I/O方式；
    • 按传输速率分类：
      • 低速设备：传输速率仅为每秒几字节到数百字节的一类设备,如键盘、鼠标等；
      • 中速设备：传输速率为每秒数千字节至数万字节的一类设备,如激光打印机等；
      • 高速设备：传输速率在数百千字节至千兆字节的一类设备，如磁盘机、光盘机等；
  • I/O接口(设备控制器)
    • 位于CPU与设备之间，它既要与CPU通信，又要与设备通信，还要具有按CPU发来的命令去控制器设备工作的功能，主要由三部分组成：
      • 1 设备控制器与CPU的接口：该接口有三类信号线，数据线、地址线和控制线。数据线通常与两类寄存器相连:
        • 数据寄存器(存放从设备送来的输入数据或从CPU送来的输出数据)；
        • 和控制/状态寄存器(存放从CPU送来的控制信息或设备的状态信息)。
      • 2 设备控制器与设备的接口：一个设备控制器可以连接一个或多个设备，因此控制器中有一个或多个设备接口。每个接口中都存在数据、控制和状态三种类型的信号。
      • 3 I/O逻辑：用于实现对设备的控制。它通过一组控制线与CPU交互，对从CPU收到的I/O命令进行译码。对地址进行译码，并相应地对所选设备进行控制。
    • 设备控制器的主要功能有6种:
      • ①接收和识别 CPU 发来的命令，如磁盘控制器能接收读、写、查找等命令；
      • ②数据交换，包括设备和控制器之间的数据传输，以及控制器和主存之间的数据传输；
      • ③标识和报告设备的状态，以供CPU处理；
      • ④地址识别;⑤数据缓冲;⑥差错控制。
  • I/O端口
    • I/O端口是指设备控制器中可被CPU直接访问的寄存器，主要有以下三类寄存器。
      • 数据寄存器:实现CPU和外设之间的数据缓冲；
      • 状态寄存器:获取执行结果和设备的状态信息，让CPU知道是否准备好；
      • 控制寄存器:由CPU写入，以便启动命令或更改设备模式；
    • CPU与I/O端口进行通信的两种方式
      • 1 独立编址。为每个端口分配一个I/O端口号，所有I/O端口形成I/O端口空间，普通用户程序不能对其进行访问，只有操作系统特殊的IO指令才能访问端口；
      • 2 统一编址，又称内存映射I/O，每个端口被分配唯一的内存地址。且不会有内存被分配这一地址，通常分配给端口的地址靠近地址空间的顶端；

• I/O控制方式

  • 设备管理的主要任务之一是控制设备和内存或CPU之间的数据传送。外围设备和内存之间的输入、输出控制方式有4种
    • 程序直接控制方式：
      • 在程序直接控制方式中，由于CPU和I/O设备的速度之差，CPU需要对外设状态进行循环检查，以确定输入信息已经在I/O控制器的数据寄存器中，造成CPU资源极大浪费；
      • 在该方式中，CPU之所以要不断地测试I/O设备的状态，就是因为在CPU中未采用中断机构，使I/O设备无法向CPU报告它已完成了一个字符的输入操作；
    • 中断驱动方式
      • 允许I/O设备主动打断CPU的运行并请求服务，从而“解放"CPU，从而使得其向I/O控制器发送读命令后可以继续做其他有用的工作。
      • I/O控制器收到CPU发出的取数据请求后，将数据放到数据总线上，传到CPU的寄存器中。至此，I/O控制器又可开始下一次I/O操作。
      • 中断驱动方式比程序直接控制方式有效，但由于数据中的每个字在存储器与1/O控制器之间的传输都必须经过CPU，中断驱动方式有较多的CPU时间消耗。
    • DMA方式
      • DMA(直接存储器存取)方式的基本思想是在I/O设备和内存之间开辟直接的数据交换通路，彻底“解放”CPU。DMA方式的特点如下：
        • 1 基本单位是数据块；
        • 2 所传送的数据，是从设备直接送入内存的，或者相反；
        • 3 仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在DMA控制器的控制下完成的；
      • 要在主机与控制器之间实现成块数据的直接交换，须在DMA控制器中设置如下4类寄存器：
        • 1 命令/状态寄存器(CR)。接收从CPU发来的IO命令、有关控制信息，或设备的状态。
        • 2 内存地址寄存器(MAR)。在输入时，它存放把数据从设备传送到内存的起始目标地址。在输出时，它存放由内存到设备的内存源地址。
        • 3 数据寄存器(DR)。暂存从设备到内存或从内存到设备的数据。
        • 4 数据计数器(DC)。存放本次要传送的字(节)数。
    • DMA方式与中断方式的主要区别
      • 中断方式在每个数据需要传输时中断CPU，而DMA方式则是在所要求传送的一批数据全部传送结束时才中断CPU;
      • 此外，中断方式的数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下完成的。
    • 通道控制方式
      • I/O通道是指专门负责输入/输出的处理机。I/O通道方式是DMA方式的发展，它可以进一步减少CPU的干预，
      • 即把对一个数据块的读(或写)为单位的干预，减少为对一组数据块的读（或写）及有关控制和管理为单位的干预，
      • 同时，又可以实现CPU、通道、I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。
      • 例如，当CPU要完成一组相关的读或写操作及有关控制时，只需向I/O通道发送一条I/O指令，给出要访问的I/O设备，通道程序便可完成CPU指定的I/O任务，数据传送结束时向CPU发中断请求。
    • I/O通道与一般处理机的别：通道指令的类型单一，没有自己的内存，通道所执行的通道程序是放在主机内存中的，和CPU共享内存；
    • I/O通道与DMA方式的区别：
      • DMA方式需要CPU来控制传输的数据块大小、传输的内存位置，而通道方式中这些信息由通道控制；
      • 另外，每个DMA控制器对应一台设备与内存传递数据，而一个通道可以控制多台设备与内存的数据交换；

• I/O软件层次结构

  • I/O软件涉及的面宽，往与硬件有着密关系，往上又与虚拟存储器系统、文件系统和用户直接交互，它们都需要10软件来实现10操作。
  • 将系统中的设备管理模块分为若干个层次，每层都是利用其下层提供的服务，完成输入/输出功能中的某些子功能，向高层提供服务；
  • 比较合理的层次划分如下：
    • 用户层I/O软件
    • 设备独立性软件
    • 设备驱动程序
    • 中断处理程序
    • 硬件
  • 整个I/O软件可以视为具有4个层次的系统结构，各层次及其功能如下：
    • 用户层I/O软件：
      • 实现与用户交互的接口，用户直接调用与I/O操作有关的库函数，对设备进行操作；
    • 设备独立性软件：
      • 用于实现用户程序与设备驱动器的统一接口、设备命令、设备的保护及设备的分配与释放等；
      • 为实现设备独立性而引入了逻辑设备和物理设备这两个概念，在应用程序中，使用逻辑设备名来请求使用某类设备；
      • 而在系统实际执行时，必须将逻辑设备名映射成物理设备名使用。使用逻辑设备名的好处是:
        • ①增加设备分配的灵活性，
        • ②易于实现1/O重定向，所谓1/O重定向，是指用于I/O操作的设备可以更换(即重定向)，而不必改变应用程序。
      • 为了实现设备独立性，必须再在驱动程序之上设置一层设备独立性软件，总体而言，设备独立性软件的主要功能可分为以下两个方面:
        • ①执行所有设备的公有操作，包括对设备的分配与回收，将逻辑设备名映射为物理设备名，对设备进行保护；
        • ②向用户层(或文件层)提供统一接口。无论何种设备，它们向用户所提供的接口应是相同的。例如对各种设备的读/写操作，都统一使用read/write命令等
    • 设备驱动程序
      • 与硬件直接相关，负责具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。
      • 通常，每类设备配置一个设备驱动程序，它是I/O进程与设备控制器之间的通信程序，通常以进程的形式存在。
      • 设备驱动程序向上层用户程序提供一组标准接口，设备具体的差别被设备驱动程序所封装，用于接收上层软件发来的抽象I/O要求，如read和 write命令，
    • 中断处理程序
      • 用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程。
      • 中断处理层的主要任务有：进行进程上下文的切换、对处理中断信号源进行测试、读取设备状态和修改进程状态等；
      • I/O子系统的层次结构，类似于文件系统的层次结构，例如以用户对设备的一次命令来总结各层次的功能：
        • ①当用户要读取某设备的内容时，通过操作系统提供的read命令接口，这就经过了用户层。
        • ②操作系统提供给用户使用的接口，如read命令，用户发出的read命令，首先经过设备独立层进行解析，然后交往下层。
        • ③接下来，不同类型的设备对read命令的行为会有所不同，如磁盘接收read命令后的行为与打印机接收read命令后的行为是不同的。因此，需要针对不同的设备,把read 命令解析成不同的指令，这就经过了设备驱动层。
        • ④命令解析完毕后，需要中断正在运行的进程，转而执行read命令，这就需要中断处理程序。
        • ⑤最后，命令真正抵达硬件设备，硬件设备的控制器按照上层传达的命令操控硬件设备，完成相应的功能。

• 应用程序I/O接口

  • pre：在I/O系统与高层之间的接口中，根据设备类型的不同，又进一步分为若干接口；
  • 字符设备接口
    • 字符设备是指数据的存取和传输是以字符为单位的设备,如键盘印机等。基本特征是传输速率较低、不可寻址，并且在输入/输出时通常采用中断驱动方式；
    • get和put操作，由于字符设备不可寻址，只能采取顺序存取方式，通常为字符设备建立一个字符缓冲区，get操作获取字符，put操作将字符输出到缓冲区；
    • in-control指令。字符设备类型繁多，差异甚大，因此在接口中提供一种通用的in-control 指令来处理它们；
    • 字符设备都属于独占设备，为此接口中还需要提供打开和关闭操作，以实现互斥共享；
  • 块设备接口
    • 块设备是指数据的存取和传输是以数据块为单位的设备，典型的块设备是磁盘。基本特征是传输速率较高、可寻址。磁盘设备的I/O常采用DMA方式。
    • 隐藏了磁盘的二维结构，块设备接口将磁盘的所有扇区从0到n-1依次编号，这样就将二维结构变为一种线性序列。在二维结构中，每个扇区的地址需要用磁道号和扇区号来表示；
    • 将抽象命令映射为低层操作，块设备接口支持上层发来的对文件或设备的打开、读、写和关闭等抽象命令，该接口将上述命令映射为设备能识别的较低层的具体操作。
    • 内存映射接口通过内存的字节数组来访问磁盘，而不提供读/写磁盘操作。映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址。只在需要访问内存映像时，才由虚拟存储器实际调页。内存映射文件的访问如同内存读写一样简单，极大地方便了程序员。
  • 网络设备接口
    • 操作系统提供的网络I/O接口为网络套接字接口，套接字接口的系统调用使应用程序创建的本地套接字，连接到远程应用程序创建的套接字，通过此连接发送和接收数据。
  • 阻塞/非阻塞I/O
    • 操作系统的I/O接口还涉及两种模式，阻塞和非阻塞，大多数操作系统提供的I/O接口都是采用阻塞I/O；
    • 阻塞 I/O 是指当用户进程调用I/O操作时，进程就被阻塞，需要等待I/O操作完成，进程才被唤醒继续执行；
    • 非阻塞I/O是指用户进程调用I/O操作时，不阻塞该进程，该I/O调用返回一个错误返回值，通常，进程需要通过轮询的方式来查询I/O操作是否完成；

设备独立软件

• 与设备无关的软件

  • 设备独立软件包括执行所有设备公有操作的软件，一些本应由设备独立性软件实现的功能，也可能放在设备驱动程序中实现；

• 高速缓存与缓冲区

  • 磁盘高速缓存
    • 指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息，磁盘高速缓存逻辑上属于磁盘，物理上则是驻留在内存中的盘块；
    • 正在运行进程的数据既存储在磁盘上，又存储在物理内存上，也被复制到CPU的二级和一级高速缓存中；
  • 缓冲区
    • 在设备管理子系统中，引入缓冲区的目的主要如下:
      • 1 缓和CPU与I/O设备间速度不匹配的矛盾。
      • 2 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
      • 3 解决基本数据单元大小(即数据粒度)不匹配的问题。
      • 4 提高 CPU和I/O 设备之间的并行性。
      • 实现方式如下：
        • 1 采用硬件缓冲器，但由于成本太高，除一些关键部位外，一般不采用硬件缓冲器。
        • 2 采用缓冲区(位于内存区域)。根据系统设置缓冲器的个数，缓冲技术可以分为如下几种:
        • 单缓冲区：
          • 在主存中设置一个缓冲区。当设备和处理机交换数据时，先将数据写入缓冲区，然后需要数据的设备或处理机从缓冲区取走数据，在缓冲区写入或取出的过程中，另一方需等待。
          • 在计算每块数据的处理时间时，需要考虑这三个的总时间：读磁盘->传送到用户区->CPU对数据的处理
            • 从磁盘把一块数据输入到缓冲区的时间(T)
            • 操作系统将该缓冲区中的数据传送到用户区的时间(M)；
            • CPU对这一块数据处理处理的时间(C)
          • 计算每块数据处理时间的技巧：
            • 假设T > C时，当工作区满了之后，缓冲区的数据同时也空了，用时为M，达到下一个初始状态，整个过程用时M+T，
            • 假设T < C时，整个过程用时M+C，
            • 故单缓冲区处理每块数据的用时为max(C,T)+M，数据输入到缓冲区的时间和CPU处理数据的时间哪个大就取哪个 + 传送到用户区的时间；
        • 双缓冲区
          • 根据单缓冲的特点，CPU在传送时间M内处于空闲状态，由此引入双缓冲。
          • I/O设备输入数据时先装填到缓冲区1，在缓冲区1填满后才开始装填缓冲区2，与此同时处理机可以从缓冲区1中取出数据送入用户进程，
          • 当缓冲区1中的数据处理完后，若缓冲区2已填满，则处理机又从缓冲区2中取出数据送入用户进程，而IO设备又可以装填缓冲区1。
          • 注意，必须等缓冲区2充满才能让处理机从缓冲区2取出数据。双缓冲机制提高了处理机和输入设备的并行程度。
          • 计算双缓冲处理一块数据的用时，
            • 假设T < C+M，缓冲区2开始向工作区传送数据，缓冲区1开始冲入数据，当工作区充满数据后，规冲区为空，时间为M；
            • 假设T > C+M。缓冲区2开始向工作区传送数据，缓冲区1开始冲入数据，区1的数据充满到达下一个初始状态，当工作区充满数据并处理完后，用时C+M,
            • 总结：双缓冲区处理一块数据的用时为max(C+M,T)，示意图在(290页)。
        • 循环缓冲
          • 包含多个大小相等的缓冲区，每个缓冲区中有一个链接指向下一个缓冲区，最后一个缓冲区指向第一个缓冲区，构成一个环形；
          • 循环缓冲用于输入输出时，还需要有两个指针in和out。对输入而言，首先要从设备接收数据到缓冲区中，in指针指向可以输入数据的一个缓冲区；
          • 当运行进程需要数据时，从循环缓冲区中取第一个装满数据的缓冲区提取数据，out指针指向可以提取数据的第一个满缓冲区；
        • 缓冲池
          • 由多个系统公用的缓冲区组成，三个队列、四种缓冲区
            • 缓冲区按其使用状况可以形成三个队列:
              • 空缓冲队列、
              • 装满输入数据的缓冲队列(输入队列)、
              • 装满输出数据的级冲队列(输出队列)。
            • 还应具有4种缓冲区:
              • 用于收容输入数据的工作级冲区、
              • 用于提取输入数据的工作缓冲区、
              • 用于收容输出数据的工作缓冲区、
              • 用于提取输出数据的工作缓冲区
          • 输入、输出数据的过程：
          • 当输入进程需要输入数据时，
            • 便从空缓冲队列的队首摘下一个空缓冲区，把它作为收容输入工作缓冲区，然后把输入数据输入其中，装满后再将它挂到输入队列队尾。
            • 当计算进程需要输入数据时，便从输入队列取得一个缓冲区作为提取输入工作缓冲区，计算进程从中提取数据，数据用完后再将它挂到空缓冲队列尾。
          • 当计算进程需要输出数据时
            • 便从空缓冲队列的队首取得一个空缓冲区，作为收容输出工作缓冲区，当其中装满输出数据后，再将它挂到输出队列队尾。
            • 当要输出时，由输出进程从输出队列中取得一个装满输出数据的缓冲区，作为提取输出工作缓冲区，当数据提取完后，再将它挂到空缓冲队列的队尾。
    • 循环缓冲、缓冲池、单缓冲、双缓冲：
      • 对于循环缓冲和缓冲池，了解机理就行，而不去定量研究它们平均处理一块数据所需要的时间。
      • 而对于单缓冲和双缓冲，只要按照上面的模板分析，就可以解决任何计算单缓冲和双缓冲情况下数据块处理时间的问题，

• 高速缓存与缓冲区的对比

  • 高速缓存是可以保存数据拷贝的高速存储器，访问高速缓存比访问原始数据更高效，速度更快。高速缓存和缓冲区的对比如下：
    • 相同点：都是介于高速设备与低速设备之间；
    • 区别
      • 存放数据：高速缓存存放的是低速设备上的某些数据的复制数据，缓冲区存放的是低速设备传递给高速设备的数据(或相反)，这些数据不一定有备份；
      • 目的：高速缓存存放的是高速设备经常要访问的数据，高速设备与低速设备的通信都要经过缓冲区，高速设备永远不会直接去访问低速设备；

• 设备分配与回收

  • 设备分配概述
    • 设备分配是指根据用户的I/O请求分配所需的设备，分配的总原则是充分发挥设备的使用效率，尽可能地让设备忙绿，又要避免不合理的分配。
    • 从设备特性来看，采用下述三种使用方式的设备分别称为
      • 独占设备：独占式使用设备，进程分配到独占设备后，便由其独占，直至该进程释放该设备；
      • 共享设备：分时式共享使用设备，对于共享设备，可同时分配给多个进程，通过分时共享使用；
      • 虚拟设备：以SPOOLing的方式使用外部设备，SPOOLing技术实现了虚拟设备功能，可以将设备同时分配给多个进程，逻辑隐射而已；
  • 设备分配的数据结构
    • 设备控制表（DCT）：
      • 一个设备控制表就表征一个设备，这个控制表中的表项就是设备的各个属性，将请求本设备未得到满足进程的PCB按某种策略排成一个设备请求队列；
    • 控制器控制表（COCT）
      • 设备控制器控制设备与内存交换数据，而设备控制器又需要请求通道为它服务，因此每个COCT有一个表项存放指向相应通道控制表(CHCT)的指针；
    • 通道控制表（CHCT）
      • 而一个通道可以为多个设备控制器服务，因此CHCT中也有一个指针指向一个表，这个表上的信息表达的是CHCT提供服务的那几个设备控制器
      • CHCT与COCT是一对多的关系；
    • 系统设备表（SDT）
      • 整个系统只有一张SDT，它记录已连接到系统中的所有物理设备的情况，每个物理设备占一个表目；
  • 设备分配的策略
    • pre：在多道程序系统中，进程数多于资源数，因此需要一套合理的分配原则，主要考虑的因素有：
      • 1 设备分配原则：
        • 设备分配应根据设备特性、用户要求和系统配置情况。既要充分发挥设备的使用效率，又要避免造成进程死锁，还要用户进程与具体设备隔离；
      • 2 设备分配方式：
        • ①静态分配：主要用于对独占设备的分配，它在用户作业开始执行前，由系统一次性分配该作业所要求的全部设备、控制器，
          • 一旦分配，这些设备、控制器就一直为该作业所占用，直到该作业被撤销。静态分配方式不会出现死锁，但设备的使用效率低。
        • ②动态分配：在进程执行过程中根据进程执行需要进行分配，通过系统调用命令向系统提出设备请求，由系统按某种策略给进程分配所需要的设备、控制器，
          • 一旦用完，便立即释放。这种方式有利于提高设备利用率，但若分配算法使用不当，则有可能造成进程死锁。
      • 3 设备分配算法：
        • 动态设备分配算法有先请求先分配、优先级高者优先等。
        • 共享设备，一般采用动态分配方式，但在每个I/O传输的单位时间内只被一个进程所占有，通常采用先请求先分配和优先级高者优先的分配算法；
        • 对于独占设备，既可以采用动态分配方式，又可以采用静态分配方式，但往往采用静态分配方式；
  • 设备分配的安全性
    • pre：设备分配的安全性是指设备分配中应防止发生进程死锁。
    • 1 安全分配方式。每当进程发出IO请求后便进入阻塞态，直到其I/O操作完成时才被唤醒，这样，一旦进程已经获得某种设备后便阻塞，不能再请求任何资源，
      • 而在它阻塞时也不保持任何资源。其优点是设备分配安全，缺点是CPU和I/O设备是串行工作的。同步IO；
    • 2 不安全分配方式。进程在发出IO请求后仍继续运行，需要时又发出第二个、第三个I/O请求等。仅当进程所请求的设备已被另一进程占用时，才进入阻塞态。
      • 优点是一个进程可同时操作多个设备，使进程推进迅速，缺点是有可能造成死锁。异步IO；
  • 逻辑设备名到物理设备名的映射
    • 在应用程序中使用逻辑设备名来请求使用某类设备，在系统中设置一张逻辑设备表(Logical Unit Table,LUT)，用于将逻辑设备名映射为物理设备名。
    • LUT表项包括逻辑设备名、物理设备名和设备驱动程序入口地址;当进程用逻辑设备名来请求分配设备时，系统为它分配一台相应的物理设备，
    • 并在LUT中建立一个表目，当以后进程再利用该逻辑设备名请求I/O操作时，系统通过查找LUT来寻找对应的物理设备和驱动程序。
    • 在系统中可采取两种方式设置逻辑设备表：
      • 1 在整个系统中只设置一张LUT。这样所有进程的设备分配情况都记录在同一张LUT中，因此不允许LUT中具有相同的逻辑设备名，主要适用于单用户系统。
      • 2 为每个用户设置一张LUT。每当用户登录时，系统便为该用户建立一个进程，同时也为之建立一张 LUT，并将该表放入进程的 PCB 中。

• 假脱机技术（SPOOLing）

  • 概述：
    • 它是操系统中采用的一项将独占设备改造成共享设备的技术。为了缓和CPU的高速性与I/O设备低速性之间的矛盾，引入了脱机输入/输出技术。
    • 该技术利用专门的外围控制机，将低速设备上的数据传送到高速磁盘上，或者相反；
    • SPOOLing系统的组成如下：
      • 1 输入井与输出井：
        • 在磁盘上开辟出的两个存储区域。输入井模拟脱机输入时的磁盘，用于收容I/O设备输入的数据。
        • 输出井模拟脱机输出时的磁盘，用于收容输入用户程序的输出数据。
        • 一个进程的输入(或输出)数据保存为一个文件，所有进程的数据输入(或输出)文件链接成一个输入(或输出)队列。
      • 2 输入缓冲区与输出缓冲区
        • 在内存中开辟的两个缓冲区。输出缓冲区用于暂存从输出井送来的数据，以后再传送到输入井。
        • 输出缓冲区用于暂存从输出井送来的数据，以后再传送到输出设备。
      • 3 输入进程和输出进程
        • 输入/输出进程用于模拟脱机输入/输出时的外围控制机。用户要求的数据从输入设备经过输入缓冲区送到输入井，当CPU需要输入数据时，直接从输入井读入内存。
        • 用户要求输出的数据先从内存送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备；
        • 共享打印机是使用SPOOLing技术的实例。当用户进程请求打印输出时，SPOOLing系统同意打印，但是并不真正立即把打印机分配给该进程，而由假脱机管理进程完成两项任务:
          • 1 在磁盘缓冲区中为之申请一个空闲盘块，并将要打印的数据送入其中暂存。
          • 2 为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到假脱机文件队列上。
    • SPOOLing系统的特点如下:
      • ①提高了1/O的速度，将对低速1O设备执行的I/O操作演变为对磁盘缓冲区中数据的存取，如同脱机I/O一样，缓和了CPU和低速I/O设备之间速度不匹配的矛盾；
      • ②将独占设备改造为共享设备，在假脱机打印机系统中，实际上并没有为任何进程分配设备:
      • ③实现了虚拟设备功能，对每个进程而言，它们都认为自己独占了一个设备。
      • SPOOLing技术是一种以空间换时间的技术；

• 设备驱动程序接口

  • 操作系统定义一组驱动程序必须支持的函数，对磁盘而言，这些函数包括读、写、格式化等；
  • 驱动程序提供一张表格，这张表格提供指向驱动程序函数自身的指针。当操作系统要调用读、写操作函数时，就可以通过这个表格发出间接调用；
  • 与设备无关的软件，还要负责将符号化的设备名映射到适当驱动程序上，
    • 例如unix中，设备名/dev/disk唯一确定了一个特殊文件的i结点，i结点包括主设备号(用于定位相应的驱动程序)和次设备号(定位要读写的具体设备)；
    • 在unix和Windows中，设备是作为命名对象出现在文件系统中的，因此针对文件的常规保护操作也适用于I/O设备；

外存管理

• 磁盘的组成

  • 组成：
    • 磁盘：由表面涂有磁性物质的物理盘片，通过一个称为磁头的导体线圈从磁盘存取数据。一个磁盘盘面有上千个磁道；
    • 磁头：从磁盘存取数据，在读写操作期间，磁头固定，磁盘在下面高速旋转；
    • 磁盘驱动器：磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴和用于数据I/O的电子设备组成;
    • 磁盘盘片包括：
      • 磁道：划分为几百个扇区，磁盘盘面上的数据存储在一组同心圆中，称为磁道；
      • 扇区：是磁盘可寻址的最小单位；
      • 盘块：一个扇区称为一个盘块；
      • 磁道间隙、扇区间隙
    • 磁盘上能存储的物理块数目：由扇区数、磁道数及磁盘面数决定，磁盘地址用“柱面号·盘面号·扇区号”表示。
  • 磁盘按不同的方式可分为若干类型:
    • 固定头磁盘，
    • 磁道、磁头，磁头可移动的，称为活动头磁盘，
    • 磁头臂(定位磁道):
    • 固定盘磁盘：磁盘永久固定在磁盘驱动器内;
    • 可换盘磁盘。
  • 磁盘调度算法要解决的问题：
    • 用户访问文件，文件实际上存储在磁盘中，操作系统接收用户的命令后，经过一系列的检验访问权限和寻址过程后，最终都会到达磁盘，控制磁盘把相应的数据信息读出或修改。
    • 操作系统中几乎每介绍一类资源及其管理时，都要涉及一类调度算法。当有多个请求同时到达时，操作系统要决定先为哪个请求服务，这就是磁盘调度算法要解决的问题。

• 磁盘管理

  • 磁盘初始化
    • 一个新的磁盘只是一个磁性记录材料的空白盘。在磁盘可以存储数据之前，必须将它分成扇区,以便磁盘控制器能够进行读写操作，这个过程称为低级格式化(或称物理格式化)。
    • 低级格式化为每个扇区使用特殊的数据结构填充磁盘、每个扇区的数据结构通常由头部、数据区域(通常为512B大小)和尾部组成。头部和尾部包含了一些磁盘控制器的使用信息。
    • 大多数磁盘在工厂时作为制造过程的一部分就已低级格式化，这种格式化能够让制造商测试磁盘，并且初始化逻辑块号到无损磁盘扇区的映射。
    • 对于许多磁盘，当磁盘控制器低级格式化时，还能指定在头部和尾部之间留下多长的数据区，通常选择256或512 字节等。
  • 分区
    • 在可以使用磁盘存储文件之前，操作系统还要将自己的数据结构记录到磁盘上，分为两步:
    • 第一步是，将磁盘分为由一个或多个柱面组成的分区(即我们熟悉的C盘、D盘等形式的分区),每个分区的起始扇区和大小都记录在磁盘主引导记录的分区表中:
    • 第二步是，对每个物理分区进行逻辑格式化(创建文件系统)，OS将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲空间和已分配的空间以及一个初始为空的目录。
    • 因扇区的单位太小，为了提高效率，操作系统将多个相邻的扇区组合在一起，形成一簇(在 Linux中称为块)。为了更高效地管理磁盘，一簇只能存放一个文件的内容，
    • 文件所占用的空间只能是簇的整数倍。如果文件大小小于一簇(甚至是0字节)，也要占用一簇的空间。
  • 引导块
    • 计算机启动时需要运行一个初始化程序(自举程序)，它初始化CPU、寄存器、设备控制器和内存等,接着启动操作系统。
    • 自举程序：
      • 自举程序找到磁盘上的操作系统内核，将它加载到内存，并转到起始地址，从而开始操作系统的运行。
      • 通常存放在ROM中，为了避免改变自举代码而需要改变ROM硬件的问题，通常只在ROM中保留很小的自举装入程序，
    • 而将完整功能的引导程序保存在磁盘的启动块上，启动块位于磁盘的固定位置。具有启动分区的磁盘称为启动磁盘或系统磁盘。
    • 引导ROM中的代码指示磁盘控制器将引导块读入内存，然后开始执行，它可以从非固定的磁盘位置加载整个操作系统，并且开始运行操作系统。
    • 引导程序->从MBR中读取引导代码(MBR包含引导代码和磁盘分区和标志从哪个分区引导系统)->读取引导分区的第一扇区(引导扇区)->加载各种系统服务；
  • 坏块
    • 对坏块的处理实质上就是用某种机制使系统不去使用坏块。由于磁盘有移动部件且容错能力弱，因此容易导致一个或多个扇区损坏。部分磁盘甚至在出厂时就有坏块。
    • 坏块在FAT表上会标明，因此程序不会使用它们。对于复杂的磁盘,控制器维护磁盘内的坏块列表。这个列表在出厂低级格式化时就已初始化，并在磁盘的使用过程中不断更新。
    • 低级格式化将一些块保留作为备用，操作系统看不到这些块。控制器可以采用备用块来逻辑地替代坏块，这种方案称为扇区备用。

• 磁盘的调度算法

  • 一次磁盘读写操作的时间由寻找(寻道)时间、旋转延迟时间和传输时间决定。
    • 1 寻找时间Ts：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。这个时间除跨越n条磁道的时间外，还包括启动磁臂的时间s，即Ts = m*n+s(306页)；
    • 2 旋转延迟时间Tt：磁头定位到某一磁道的扇区所需要的时间；
    • 3 传输时间Tr：从磁盘读出或向磁盘写入数据所经历的时间，这个时间取决于每次所读写的字节数b和磁盘的旋转速度:
  • 读写磁盘的计算的平均值是没有太大实际意义的，因为在实际的磁盘I/O操作中，存取时间与磁盘调度算法密切相关。目前常用的磁盘调度算法有以下几种：
  • 先来先服务调度算法
    • (First Come First Served,FCFS)算法根据进程请求访问磁盘的先后顺序进行调度，这是一种最简单的调度算法，该算法的优点是具有公平性。
    • 若只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则有望达到较好的性能;
    • 若有大量进程竞争使用磁盘，则这种算法在性能上往往接近于随机调度。所以，实际磁盘调度中会考虑一些更为复杂的调度算法。
  • 最短寻找时间优先
    • (Shortest Scek Time First,SSTF)算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以便使每次的寻找时间最短。
    • 当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。
  • 扫描（SCAN）算法(又称电梯调度算法)
    • SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，实际上就是在最短寻找时间优先算法的基础上规定了磁头运动的方向，
    • 由于磁头移动规律与电梯运行相似，因此又称电梯调度算法，SCAN算法对最近扫描过的区域不公平，因此它在访问局部性方面不如FCFS算法和SSTF算法好。
  • 循环扫描（C-SCAN）算法
    • (CircularSCAN,C-SCAN)算法在扫描算法的基础上规定磁头单向移动来提供服务。
    • 回返时直接快速移动至起始端而不服务任何请求。由于SCAN算法偏向于处理那些接近最里或最外的磁道的访问请求，所以使用改进型C-SCAN算法来避免这个问题；
    • 磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点，这种形式的SCAN算法和C-SCAN算法称为LOOK调度；
    • 若无特别说明，也可以默认SCAN算法和C-SCAN算法为LOOK和CLOOK调度
  • 对比以上几种磁盘调度算法，
    • FCFS算法太过简单，性能较差，仅在请求队列长度接近于1时才较为理想，适合I/O较少的场合；
    • SSTF算法较为通用和自然，不能保证平均时间最短，会产生“饥饿”现象；
    • SCAN算法和C-SCAN算法在磁盘负载较大时比较占优势。C-SCAN消除了对两端磁道请求的不公平；
  • 除减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。
    • 定位磁道中的一个扇区平均需要转过4个扇。这时延迟时间是传输时间的4倍，这是一种非常低效的方式，
    • 理想的情况是不需要定位而直接连续读取扇区，没有延迟时间；这样磁盘数据存取效率可以成倍提高。但由于读取扇区的顺序是不可预测的，所以延迟不可避免；
    • 磁盘寻块时间分为三个部分：寻道时间、延迟时间、传输时间，寻道时间和延迟时间属于“找”的时间，可以通过一定方法削减，但传输时间是磁盘本身性质决定的，减少不了；
  • 需要计算每种算法的平均寻找长度：例如给定请求序列，磁头的初始位置+具体算法的磁头的运动过程；

• 固态硬盘

  • 固态硬盘的特性
    • 固态硬盘(SSD)是一种基于闪存技术的存储器。它与U盘并无本质差别，只是容量更大，存取性能更好。
    • 一个SSD由一个或多个闪存芯片和闪存翻译层组成，闪存芯片替代传统旋转磁盘中的机械驱动器，闪存翻译层相当于扮演了磁盘控制器的角色。
    • 固态硬盘(SSD)：I/O总线->闪存翻译层->闪存(存储块(0-N)->页)。页大小是512B~4KB，每块由32~128页组成，块的大小为16KB~512KB；
    • 数据是以页为单位读写的，只有在一页所属的块整个被擦除后，才能写这一页，不过，一旦擦除一块，块中的每页就都可以直接再写一次；
    • 随机写很慢，有两个原因。
      • 首先，擦除块比较慢，通常比访问页高一个数量级。
      • 其次，如果写操作试图修改包含已有数据的页P，那么这个块中所有含有用数据的页都必须被复制到一个新(擦除过的)块中，然后才能进行对页Pi的写操作。
    • 比起传统磁盘，SSD有很多优点，它由半导体存储器构成，没有移动的部件，因而随机访问速度比机械磁盘要快很多，SSD会有望逐步取代传统机械硬盘。
  • 磨损均衡 (Wear Leveling)
    • 固态硬盘也有缺点，闪存的擦写寿命是有限的，一般是几百次到几千次。
    • 为了弥补 SSD 的寿命缺陷，引入了磨损均衡。SSD磨损均衡技术大致分为两种:
    • 1 动态磨损均衡：写入数据时，自动选择较新的闪存块，老的闪存块先歇一歇。
    • 2 静态磨损均衡：让各闪存块的损耗平均，当没有数据写入SSD会监测并自动进行数据分配，让老的闪存块承担无须写数据的存储任务，平常的读写操作在较新的闪存块中进行。
  • 有了磨损均衡这种算法加持，SSD的寿命就比较可观了。例如对于一个256GB的SSD，如果闪存的擦写寿命是500次，就算每天写入10GB数据，也要三十多年才能将闪存磨损坏；

问题

• 在磁盘上进行有一次读写操作需要哪几部分时间？其中哪部分时间最长？
• 一次磁盘操作需要的时间，以及对于给定访盘的磁道序列，按照特定算法求出磁道通过的总磁道数及平均寻道数；