计算机操作系统学习笔记-摩杜云开发者社区

第1章计算机系统概述
- 1.1 操作系统的基本概念
  - 1.1.1 操作系统的概念
    操作系统是计算机系统中最基本的系统软件。
    - 操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件与软件资源，合理地组织、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。
  - 1.1.2 操心系统的特征
    操作系统的基本特征包括：并发、共享、虚拟和异步。并发和共享是操作系统两个最基本的特征，两者之间互为存在的条件。
    - 1. 并发（Concurrence）：并发是指两个或多个事件在同一时间间隔内发生。
      操作系统的并发性指计算机系统中同时存在多个运行的程序。操作系统的并发性是通过分时实现的。
      - 并发性与并行性的区别
    - 2. 共享（Sharing）：指系统中的资源可供内存中多个并发执行的进程共同使用。
      - （1）互斥共享方式：在一段时间内只允许一个进程访问该资源（这种资源就叫临界资源）。如打印机、磁带机等大多数物理设备及某些软件中所用的栈、变量和表格这些临界资源。
      - （2）同时访问方式：允许在一段时间内由多个进程“同时”访问。如磁盘设备、用重入码编写的文件。
        “同时”指宏观上的，而在微观上还是交替对该资源进行访问的。
    - 3. 虚拟（Virtual）：把一个物理上的实体变为若干逻辑上的对应物。
      操作系统的虚拟技术应用在虚拟处理器、虚拟内存和虚拟外部设备等。操作系统的虚拟技术可归纳为：时分复用技术，如处理器的分时共享；空分复用技术，如虚拟存储器。
    - 4. 异步（Asynchronism）：操作系统运行在一种随机的环境下，以不可预知的速度向前推进，可能导致进程产生与时间有关的错误。
      只要运行环境相同，操作系统就必须保证多次运行进程后都能获得相同的结果。
  - 1.1.3 操作系统的目标和功能
    操作系统应具有以下功能：处理机管理、存储器管理、设备管理和文件管理，向用户提供接口及用来扩充机器。
    - 1. 操作系统作为计算机系统资源的管理者
      - （1）处理机管理：包括进程控制、进程同步、进程通信、死锁处理、处理机调度等。
        在多道程序环境下，处理机的分配和运行都以进程（或线程）为基本单位，故对处理机的管理就是对进程的管理。
      - （2）存储器管理：包括内存分配与回收、地址映射、内存保护与共享和内存扩充等。
      - （3）文件管理：包括文件存储空间的管理、目录管理及文件读写管理和保护等。
      - （4）设备管理：包括缓冲管理、设备分配、设备处理和虚拟设备等。
        主要任务是完成用户的I/O请求，方便用户使用各种设备，提高设备的利用率。
    - 2. 操作系统作为用户与计算机硬件系统之间的接口
      - （1）命令接口：用户利用这些操作命令来组织和控制作业的执行。
        
        命令接口根据作业控制方式的不同，分为联机命令接口（交互式命令接口）和脱机命令接口（批处理命令接口）。
      - （2）程序接口：编程人员可以使用它们来请求操作系统服务。
        
        程序接口由一组系统调用（也称广义指令）组成。图形用户界面（GUI）就是调用程序接口实现的。
    - 3. 操作系统用作扩充机器
      - 没有任何软件支持的计算机叫裸机，操作系统提供的资源管理功能和方便用户的各种服务功能，将裸机改造成更强、使用更方便的机器。
- 1.2 操作系统的发展与分类
  - 1.2.0 发展历程
  - 1.2.1 手工操作系统阶段（此阶段无操作系统）
    - 用户在计算机上计算题目需要人工干预。
    - 两个突出缺点：
      - ①用户独占全机，不好出现资源被其他用户占用而等待的现象，但资源利用率低。
      - ②CPU等待手工操作，CPU利用不充分。
  - 1.2.2 批处理阶段（操作系统开始出现）
    - 引入目的：为了解决人机矛盾及CPU和I/O设备之间速度不匹配的问题，出现了批处理系统。
    - 按发展历程分单道批处理系统和多道批量处理系统：
      - 1. 单道批处理系统：系统对作业的处理是成批进行的，单内存中始终只保持一道作业。
        特点：自动性、顺序性、单道性。
      - 2. 多道批处理系统：允许多个程序同时进入内存并允许它们在CPU中交替运行，共享系统中的各种软/硬件资源。
        引入目的：为了进一步提高资源的利用率和系统的吞吐量。因为单道系统在运行期间发出I/O请求后，高速的CPU会处于等待低速的I/O完成状态。特点：多道、宏观上并行、微观上串行。
    - 优缺点
      - 优点：资源利用率高；系统吞吐量大，CPU和其他资源保持“忙碌”状态。
      - 缺点：用户响应的时间较长；不提供人机交互能力。
  - 1.2.3 分时操作系统
    - 引入目的：为了解决批处理系统不能进行人机交互的问题。
    - 概念：分时系统是指多个用户通过终端同时共享一台主机，用户可以同时与主机进行交互操作而互不干扰。分时系统是实现人机交互的系统。
    - 特点：
      - （1）同时性。指允许多个终端用户同时使用一台计算机。
      - （2）交互性。指用户能够与系统进行人机对话交互。
      - （3）独立性。系统中多个用户可以彼此独立进行操作，互不干扰，单个用户感觉不到别人也在使用这台计算机，好像只有自己独自使用。
      - （4）及时性。用户请求能在短时间内得到响应。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务。
  - 1.2.4 实时操作系统
    - 引入目的：为了能在某个时间限制内完成某些紧急任务而不需要时间片排队。
    - 根据时间限制分为两种情况：硬实时系统和软实时系统。
      - 硬实时系统：某个动作必须绝对地在规定时间范围发生。如飞行器的自动控制系统。
      - 软实时系统：能够接受偶尔违反时间规定且不好引起任何永久性的损害。如飞机订票系统、银行管理系统。
    - 特点：及时性、可靠性。
  - 1.2.5 网络操作系统和分布式计算机系统
    二者本质不同是：分布式操作系统中的若干计算机相互协同完成同一任务。
    - 网络操作系统
      - 概念：把计算机网络中的各台计算机结合起来，集中控制，实现各台计算机之间的数据相互传送。
      - 特点：网络中各种资源的共享、各台计算机之间的通信。
    - 分布式计算机系统
      - 概念：任意两台计算机通过通信方式交互信息；地位同等（没有主机也没有从机）；每天计算机的资源为所有用户共享；任意台计算机能构成子系统并还能重构；任何工作可以分布在几台计算机上，并行工作协同完成。
      - 特点：分布式和并行性。
  - 1.2.6 个人计算机操作系统
    - 目前使用最广泛的操作系统，广泛应用于文字处理、电子表格、游戏中，常见的由Windows、Linux和Macintosh等。
- 1.3 操作系统的运行环境
  - 1.3.1 操作系统的运行机制
    - CPU执行两种不同性质的程序：一种是操作系统内核程序；另一种是用户自编程序（应用程序）。前者是后者的管理者。
    - 特权指令（内核程序要执行的指令）：指计算机中不允许用户直接使用的指令。如I/O指令、置中断指令，存取用于内存保护的寄存器、送程序状态字道程序状态字寄存器等指令。
    - 在具体实现上将CPU的状态分为：
      - 用户态：用户自编程序运行在用户态
      - 核心态（管态、内核态）：操作系统内核程序运行在核心态。
        
        内核的内存构成（这部分内容的指令操作工作在核心态）：
        
        一些与硬件关联紧密的模块，如时钟管理、中断处理、设备驱动等处于最底层。
        
        其次是运行频率较高的程序，如进程管理、存储器管理和设备管理等。
    - 大多数操作系统内核包含以下的内容：
      内核是计算机上配置的底层软件。核心态指令实际上包括系统调用指令和一些针对时钟、中断和原语的操作指令。
      - 1. 时钟管理
        
        时钟的功能：计时（第一功能）；实现进程的切换（如分时系统中采用时间片轮转调度；实时系统中按截止时间运行；批处理系统中衡量作业的运行程度）。
      - 2. 中断机制
        
        引入目的：提高多道程序运行环境中CPU的利用率，主要针对外部设备。
        
        功能：负责保护和恢复中断现场的信息、转移控制权道相关的处理程序。
        只有一小部分属于内核，为的是减少中断的处理时间，提高系统的并行处理能力。
      - 3. 原语
        
        原语的特点（也是定义）：
        原语是操作系统底层可被调用的公用小程序，它们各自完成一个规定的操作。
        
        （1）处于操作系统的最底层，是最接近硬件的部分。
        
        （2）这些程序的运行具有原子性（要么成功要么失败无其他可能），主要处于系统安全性和便于管理考虑。
        
        （3）这些程序的运行时间都较短，而且调用频繁。
        
        定义原语的方法：直接方法是关闭中断，让其所有动作不可分割地完成后再打开中断。
        系统中的设备驱动、CPU切换、进程通信等功能中的部分操作可以定义为原语，称为内核的组成部分。
      - 4. 系统控制的数据结构及处理
        
        为了实现数据结构的管理，通过有以下一些基本操作：
        
        （1）进程管理。进程状态管理、进程调度和分派、创建与撤销进程控制块。
        
        （2）存储器管理。存储器的空间分配和回收、内存信息保护程序、代码对换程序。
        
        （3）设备管理。缓冲区管理、设备分配和回收。
  - 1.3.2 中断和异常的概念
    - 0. 中断的应用
      - （1）发生中断或异常时，运行用户态的CPU就会立即进入核心态，这是通过硬件实现的。
      - （2）对资源占有权的释放，也需要通过中断实现。
    - 1. 中断和异常的定义
      - 中断（也称外中断）：指来自CPU执行指令以外的事件的发生，与当前指令执行无关的事件发生（即它们与当前处理机运行的程序无关）。如I/O结束中断、时钟中断等。
      - 异常（也称内中断、例外或陷入(trap)）：指来自CPU执行指令内部的事件，对异常的处理一般要依赖于当前程序的运行现场，而且异常不能被屏蔽，一旦出现应立即处理。如程序性的非法操作码、地址越界、算术溢出、虚存系统的缺页及专门的陷入指令等。
      - 内中断与外中断的联系与区别
    - 2. 中断处理的过程
      - 外中断处理流程如下：
        
        其中第（1）~（3）步是在CPU进入中断周期后，由硬件（中断隐指令）自动完成的；（4）~（9）步由中断服务程序完成。
        
        （1）关中断。CPU响应中断后，首先要保护程序的现场状态，在保护现场的过程中，CPU不应响应更高级中断源的中断请求。否则，若现场保存不完整，也就不能正确地恢复并继续执行现行程序。
        
        （2）保存断点。为保证中断服务程序执行完毕后能正确地返回到原来的程序，必须将原来的程序的断点（即程序计数器PC）保存起来。
        
        （3）引出中断服务程序。其实质是取出中断服务程序的入口地址送入程序计数器PC。
        
        （4）保存现场和屏蔽字。进入中断服务程序后，首先要保存现场，现场信息一般是指程序状态字寄存器PSWR和某些通用寄存器的内容。
        
        （5）开中断。允许更高级中断请求得到响应。
        
        （6）执行中断服务程序。这是中断请求的目的。
        中断服务程序是专门为中断设计的，在中断事件发生时执行的专用子程序，一般分为：保护现场、执行操作、恢复现场这些部分。
        
        （7）关中断。保证在恢复现场和屏蔽字时不被中断。
        
        （8）恢复现场和屏蔽字。将现场和屏蔽字恢复到原来的状态。
        
        （9）开中断、中断返回。中断服务程序的最后一条指令通常是一条中断返回指令，使其返回到原程序的断点处，以便继续执行原程序。
  - 1.3.3 系统调用
    - 定义：系统调用是指用户在程序中调用操作系统所提高的一些子功能，系统调用可视为特殊的公共子程序。
    - 按功能分类：
      - 设备管理。完成设备的请求或释放，以及设备启动等功能。
      - 文件管理。完成文件的读、写、创建及删除等功能。
      - 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
      - 进程通信。完成进程之间消息传递或信号传递等功能。
      - 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及始址等功能。
    - 系统调用执行过程：系统调用的处理需要由操作系统内核程序负责完成，要运行在核心态。
      
      用户程序可以执行陷入指令（又称访管指令或trap指令）来发起系统调用（执行陷入指令CPU状态从用户态进入核心态；处理完成后CPU状态从核心态回到用户态），请求操作系统提供服务。
    - 核心态与用户态间的切换
      若程序的运行由用户态转到核心态，则会用到访管指令，访管指令是在用户态使用的，所以它不可能为特权指令。
      - 用户态转向核心态的例子：
        注意：由用户态进入核心态，不仅需要状态切换，而且所用的堆栈也可能需要由用户堆栈切换为系统堆栈，单这个系统堆栈也是属于该进程的。
        
        （1）用户程序要求操作系统的服务，即系统调用。
        
        （2）发生一次中断。
        
        （3）用户程序产生了一个错误状态。
        
        （4）用户程序中企图执行一条特权指令。
        
        （5）从核心态转向用户态由一条特权指令实现，这条指令也是特权指令，一般是中断返回指令。
- 1.4 操作系统的体系结构
  - 1.4.1 大内核和微内核
    - 操作系统的核心态
      为应用程序提供什么样的公共服务、如何提高公共服务形成了两种体系结构：大内核和微内核。
      - 大内核：提供了高性能的系统服务，但使得系统层次间界限模糊，接口不清晰，维护代价高，稳定性低。
      - 微内核：将最基本的功能（如进程管理）保留在内核，将一些服务（如文件系统）移到用户态执行。降低了内核设计的复杂性，移出内核的服务程序执行相互独立，交互则需借助微内核通信。使接口更加清晰，维护代价降低，保障了操作系统的可靠性（稳定性），但是系统性能下降。
        为解决操作系统内核代码难以维护的问题，即大内核的接口不够清晰、层次模糊的问题，提出了微内核的体系结构。
第2章进程管理
- 2.1 进程与线程
  - 2.1.1 进程的概念
    - 1. 进程的概念
      - 为什么要引入进程：为了更好地描述和控制程序的并发执行。
      - 什么是进程：进程是进程实体的一次运行，是系统进行资源分配和调度的一个独立单位。
      - 什么是进程实体：进程实体由程序段、相关数据段和PCB三部分构成，也称为进程映像。
        注意：进程映像是静态的，进程则是动态的。
        
        进程控制块（PCB）：保存进程运行期间相关的数据，是进程存在的唯一标志。
        
        程序段：能被进程调度程序调度到CPU运行的程序的代码段。
        
        数据段：存储程序运行期间的相关数据，可以是原始数据，也可以是程序执行时产生的中间或最终结果。
      - 什么是处理机：处理机是处理计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件。
        
        程序是描述处理机完成某项任务的指令序列。
        
        指令则是处理机能直接解释、执行的信息单位。
    - 2. 进程的特征
      - 进程与程序的区别
      - 进程的基本特征
        
        （1）动态性。进程是程序的一次执行，具有创建、活动、终止等过程，是动态地产生、变化和消亡。动态性是进程最基本的特征，是区别于程序的根本特征。
        
        （2）并发性。指多个进程实体能够同时存在于内存中，能在一段时间内同时运行。
        
        （3）独立性。指进程实体是一个能够独立运行、独立获得资源和独立接受调度的基本单位。
        
        （4）异步性。指进程以不可预知的速度向前推进，内存中的每个进程何时执行，何时暂停，以怎样的速度向前推进，每道程序总共需要多少时间才能完成等都是不可预知的。异步性导致执行结果具有不可再现性，需要配置相应的同步机制才会多次运行得出相同结果。
        异步是指进程之间有制约关系，进程A需要用打印机，如果进程B占用了打印机，就要等一等，进程A就会表现出走走停停、以不可预知的速度前进。
        
        （5）结构性。指进程实体由程序段、数据段和PCB三部分组成。
  - 2.1.2 进程的状态与转换
    - 进程的状态种类
      - 创建状态：进程正在被创建，尚未转到就绪状态。
      - 就绪状态：进程已经获得除处理机之外的一切所需资源。
      - 运行状态：进程正在处理机上运行。
        在单处理机环境下，每个时刻最多只有一个进程处于运行态。比如说单处理系统中，若同时存在10个进程，那么不可能出现10个进程都处于就绪或运行状态，可能是9个处于就绪状态、1个处于运行状态或者可能10个进程都处于阻塞状态。
      - 阻塞状态（等待状态）：进程正在等待某一事件而暂停运行。
        某一事件可能是等待某资源（不包括处理机）或等待输入输出的完成。注意，即使处理机空闲，进程也不能运行。
      - 结束状态：进程正从系统中消失，分为正常结束和异常退出。
        注意，必须先将进程置为结束态，才能释放回收资源。
    - 进程的状态变化
      - 三中基本状态之间的切换
        
        注意：一个进程从运行态变成阻塞态是主动的行为；而从阻塞态变成就绪态是被动的行为，需要其他相关进程的协助。
  - 2.1.3 进程的控制
    - 创建：终端用户登陆系统、作业调度、系统提供服务、用户程序的应用请求等。
    - 终止：正常结束、发生异常、外界干预。
      - 正常结束：进程的任务完成。
      - 异常结束：如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O故障等。
      - 外界干预：操作员或操作系统干预、父进程请求和父进程终止。
    - 阻塞：等待资源。
    - 唤醒：资源到达。
    - 切换：时间片用完、主动放弃处理机、被更高优先级的进程剥夺处理机。
      进程的切换指处理机从一个进程的运行转到另一个进程上运行。
  - 2.1.4 进程的组织
    - 1. 进程控制块（PCB）
      进程是一个独立的运行单位，是操作系统进行资源分配和调度的基本单位。由以下三部分组成，其中最核心的是进程控制块PCB。
      - PCB是进程实体的一部分，是进程存在的唯一标志。操作系统通过PCB表来管理和控制进程。PCB主要包括进程描述信息、进程控制和管理信息、资源分配清单和处理相关信息。
    - 2. 程序段
      - 程序可被多个进程共享，即多个进程可以运行通过一个程序。
    - 3. 数据段
      - 一个进程的数据段，可以是原始数据，也可以是程序执行时产生的中间或最终结果。
  - 2.1.5 进程的通信
    - 概念：进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式，包括以下三类：共享存储、消息传递和管道通信。
    - 高级通信方法
      - （1）共享存储
        
        共享存储的分类
        
        低级方式的共享是基于数据结构的共享
        
        高级方式的共享是基于存储区的共享
        
        理解
        
        甲和乙中间有一个大布袋，甲和乙交换东西都是通过布袋进行的，甲把东西放在布袋里，乙拿走。但乙不能直接到甲手中拿东西，甲也不能直接到乙的手中拿东西。
      - （2）消息传递
        
        消息传递分类
        
        直接通信方式：直接把消息挂到接收进程的消息队列中。
        
        间接通信方式：挂到某个中间实体，接收进程找实体接收消息，类似于电子邮件。
        
        理解
        
        甲要告诉乙某些事情，就要写信，然后通过邮差送给乙。直接通信就是邮差直接把信交到乙的手上；间接通信就是乙家门口有个邮箱，邮差把信放到邮箱里。
      - （3）管道通信
        
        利用一种特殊的pipe文件连接两个进程。是一种半双工通信。
  - 2.1.6 线程概念和多线程模型
    - 1. 线程的基本概念
      - 引入目的：为了更好的使多道程序并发执行，以提高资源利用率和系统吞吐量，增加程序的并发性。
      - 特点
        
        线程由线程ID、程序计数器、寄存器集合和堆栈组成。
        
        线程自己不拥有系统资源，只拥有一点儿运行中必不可少的资源。
        
        与同进程中的其他线程共享进程所拥有的全部资源。
        
        一个线程可以创建和撤销另一个线程，同一进程中多个线程可以并发执行。
        
        线程也有就绪、阻塞和运行三种基本状态。
        
        引入线程后，进程只作为除CPU外的系统资源的分配单元，而线程作为处理机的分配单元。
        
        一个进程中有多个线程，若线程的切换发生在同一个进程中，只需要很少的时空开销。
      - 为什么线程的提出有利于提高系统并发性：由于有了线程，线程切换时，有可能会发生进程切换，也有可能不发生进程切换，平均而言每次切换所需的开销就变小了，因此让更多的线程参与并发，而不会影响到响应时间等问题。
    - 2. 线程与进程的比较
      我们使用打开一个微信软件，这个时候就开启了一个进程，当我们在微信里面进行各种操作（查看朋友圈，扫一扫...），这么多的操作就是线程。
      - 比较总结
    - 3. 线程的属性
      - （1）线程不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块，线程控制块积累了线程执行的寄存器和栈等现场状态。
      - （2）不同的线程可以执行相同的程序。
      - （3）同一进程中的各个线程共享该进程所拥有的资源。
      - （4）线程是处理机的独立调度单位，多个线程是可以并发执行的。
      - （5）一个线程被创建后，便开始了它的生命周期，包括阻塞状态、就绪状态和运行状态直到终止等各种状态变化。
    - 4. 线程的实现方式
      - 用户级线程：有关线程管理（如线程的创建、撤销和切换等）的所有工作都是在应用程序完成，内核意识不到线程的存在。
      - 内核级线程：线程管理的所有工作由内核完成。
    - 5. 多线程模型
- 2.2 处理机调度
  - 2.2.1 调度的概念
    - 1. 调度的基本概念
      - 进程调度的原因：若没有调度，则需要等当前进程完成后，才能执行下一个进程，在实际情况中，进程时常需要等待一些外部设备的输入，而外部设备的输入与处理机相比是很慢的，若让处理机总等外部设备，则是对处理机资源的极大浪费。引进处理机调度后，在运行进程等待外部设备时，可以把处理机调度给其他进程，从而提高处理机的利用率。简单的来说，就是合理地处理计算机的软/硬件资源。
        通俗易懂的来说，就是由于你正在下载一个电子书，要下载完成后才能阅读，但在这期间你不可能一直等在电脑前直到电子书下载完成，这将是对你时间的极大浪费，这时候你可以把你的时间分配到其他地方去（如听音乐、打电话等）。
      - 进程调度的概念：是对处理机进行分配，即从就绪队列中按一定算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发运行。
    - 2. 调度的层次
      - 作业调度（高级调度）：选择处于后备状态的作业分配资源，发生频率最低。
      - 内存调度（中级调度）：选择暂时不能运行的进程调出内存，发生频率中等。
        作用是提高内存利用率和系统吞吐量。哪些暂时不能运行调至外存等待的进程状态就做挂起态。
      - 进程调度（低级调度）：选择就绪队列中合适的进程分配处理机，发生频率最高。
    - 3. 三级调度的联系
      - （1）作业调度为进程活动作准备，进程调度使进程正常活动起来，中级调度将暂时不能运行的进程挂起，中级调度处于作业调度和进程调度之间。
      - （2）作业调度次数最少，中级调度次数略多，进程调度频率最高。
      - （3）进程调度是最基本的，不可或缺。
  - 2.2.2 调度的时机、切换与过程
    进程调度和切换程序是操作系统内核程序。
    - 不能进行进程的调度与切换的情况：
      发生了下述情况，不能马上进行调度和切换，而是应置系统的请求调度标志，直到下述过程结束才进行相应的调度与切换。
      - （1）在处理中断的过程中。
      - （2）进程在操作系统内核程序临界区中。
      - （3）其他需要完全屏蔽中断的原子操作过程中。如加锁、解锁、中断现场保护、恢复等原子操作。
        在原子过程中，连中断都要屏蔽，更不应该进行进程调度与切换。
    - 应该进行进程的调度与切换的情况：
      - （1）发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。若操作系统只在这种情况下进行进程调度，则是非剥夺调度。
      - （2）中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。若操作系统支持这种情况下的运行调度程序，则实现了剥夺方式的调度。
  - 2.2.3 进程调度方式
    - 进程调度方式的概念：是指当某个进程正在处理机上执行时，若有某个更为重要或紧迫的进程需要处理，即优先级更高的进程进入就绪队列，此时改如何分配处理机。
    - 两种进程调度方式
      - （1）非剥夺调度方式（非抢占式）：有更为重要或紧迫的进程需要使用处理机，仍让当前进程继续执行。
        
        优点：实现简单、系统开销小，适用于大多数的批处理系统。
        
        缺点：不能用于分时系统和大多数的实时系统。
      - （2）剥夺调度方式（抢占式）：有更为重要或紧迫的进程需要使用处理机，立即分配。
        
        优点：提高系统吞吐率和响应效率，适用于分时系统和实时系统。
  - 2.2.4 进程调度的基本准则
    - （1）CPU利用率。要尽可能使CPU处于忙的状态，使CPU利用率最高。
    - （2）系统吞吐量。表示单位时间内CPU完成作业的数量。长作业消耗处理机较长时间，降低了系统的吞吐量，短作业消耗处理机较短时间，提高了系统的吞吐量。调度算法和方式的不同会对系统的吞吐量产生较大影响。
    - （3）周转时间。是指从作业提交到作业完成所经历的时间。
      - 作业周转时间公式：周转时间 = 作业完成时间 — 作业提交时间。
      - 平均周转时间是指多个作业周转时间的平均值：平均周转时间 = （作业1的周转时间 + ... + 作业n的周转时间）/ n。
      - 带权周转时间是指作业周转时间与作业实际运行时间的比值：带权周转时间=作业周转时间/作业实际运行时间。
      - 平均带权周转时间是多个作业带权周转时间的平均值：平均带权周转时间 = （作业1的带权周转时间 + ... + 作业n的带权周转时间）/ n。
    - （4）等待时间。指进程处于等处理机状态的时间之和。处理机调度算法实际上并不影响作业执行或输入/输出的时间，只影响作业在就绪队列中等待所花的时间。
    - （5）响应时间。指用户提交请求到系统首次产生响应所用的时间。
  - 2.2.5 典型的调度算法
    - 0. 各种调度算法总结
      - 几种常见进程调度算法的特点
    - 1. 先来先服务（FCFS）调度算法
      - 算法描述：选择最先进入就绪队列中的作业（进程）。
      - FCFS调度算法的特点：
        
        FCFS算法属于不可剥夺算法。
        
        不能作为分时系统和实时系统的主要调度策略。
        
        算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比）；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。
      - FCFS调度算法的性能：顺序是作业①——②——③——④。
    - 2. 短作业优先（SJF）调度算法
      - 算法描述：选择运行时间最短的作业（进程）。
      - SJF算法的特点：
        
        该算法对长作业不利。
        
        不能保证紧迫性作业会被及时处理。
        
        由于作业的长短由用户所提供的估计执行时间而定，致使算法不一定真正做到短作业优先调度。
        
        算法的平均等待时间、平均周转时间最少。
      - SJF算法的性能：顺序是作业①——④——③——②。
    - 3. 优先级调度算法
      - 算法描述：选择优先级最高的作业（进程）。
        优先级指用于描述作业运行的紧迫程度。
      - 进程优先级分类
        根据进程创建后其优先级是否可以改变，分为如下两种：
        
        （1）静态优先级。优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。
        
        （2）动态优先级。在进程运行过程中，根据进程情况的变化动态调整优先级。动态调整优先级的主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短。
      - 进程优先级设置原则：
        
        （1）系统进程 > 用户进程。
        系统进程作为系统的管理者，理应有更高的优先级。
        
        （2）交互型进程 > 非交互型进程（前台进程 > 后台进程）。
        交互的进程应该更快被优先处理。
        
        （3）I/O型进程 > 计算型进程。
        频繁使用I/O设备的进程应该有更高的优先级，会让I/O设备尽快地投入工作。
    - 4. 高响应比优先调度算法
      - 算法描述：选择响应比最高的，主要用于作业调度，是FCFS算法和SJF算法的综合平衡。
      - 响应比计算公式：响应比=（等待时间+执行时间）/ 执行时间。
      - 算法特点：
        
        （1）作业等待时间相同时，要求服务时间越短，相应比越高，有利于短作业。
        
        （2）要求服务时间相同时，作业的响应比由等待时间决定，等待时间越长，响应比越高，实现的是先来先服务。
        
        （3）克服了饥饿状态，兼顾了长作业。
    - 5. 时间片轮转调度算法
      - 算法描述：总是选择就绪队列中的第一个进程，但仅能运行一个时间片。主要适用于分时系统。
      - 时间片的长短的决定因素：系统的响应时间、就绪队列中的进程数目和系统的处理能力。
    - 6. 多级反馈队列调度算法
      - 算法描述：时间片轮转调度算法和优先级调度算法的综合和发展。
      - 算法优势
        
        （1）终端型作业用户：短作业优先。
        
        （2）短批处理作业用户：周转时间较短。
        
        （3）长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。
  - 2.2.0 题目补充
    - （1）时间片轮转的主要目的是，使得多个交互的用户能够得到及时响应，使用户以为“独占”计算机的使用，因此它没有偏好，也不会对特殊进程进行特殊服务。时间片轮转增加了系统开销，所以不会使得系统高效运转，吞吐量和周转时间均不如批处理。但其较快速的响应时间使得用户能够与计算机进行交互，改善了人机环境，满足了用户需求。
    - （2）在单处理的多进程系统中，进程什么时候占用处理器及决定占用时间的长短由进程特点和进程调度策略决定的。
    - （3）若每个作业只能建立一个进程，为了照顾短作业用户，应采用短作业优先调度算法；为了照顾紧急作业用户，应采用剥夺式优先级调度算法；为了能够实现人机交互，应采用时间片轮转调度算法；而能使短作业、长作业和交互作业用户都满意，应采用多级反馈队列调度算法。
    - （4）处于运行态的进程用完一个时间片后，其状态会变为就绪态，等待下一次处理器调度。进程执行完最后的语句并使用系统调用exit请求操作系统删除它或出现一些异常情况时，进程才会终止。
    - （5）作业的优先权与长作业、短作业或系统资源要求的多少没有必然关系。在动态优先权中，随着进程执行时间的增加其优先权随之降低，随着作业等待时间的增加其优先权相应上升。
    - （6）时间片轮转算法是按固定时间配额来运行的，时间一到，不管是否完成，当前进程必须撤下，调用新的进程，因此它是由时间配额决定的，是绝对可抢占的。而优先级算法和短进程优先算法都可分为抢占式和不可抢占式。（即先来先服务、优先级、短进程优先算法都不是绝对可抢占式的。）
    - （7）作业与进程最主要的区别是，作业是用户提交的，进程是系统自动生成的。作业是以用户任务为单位，进程是操作系统控制的单位。
    - （8）采用时间片调度算法，当时间片过大时，就会使时间片轮转算法转化为先来先服务算法。
    - （9）采用静态优先级调度且系统总是出现优先级高的任务时，优先级低的任务总是得不到处理机而产生饥饿现象；而短任务优先调度不管是抢占式还是非抢占的，当系统总是出现新来的短任务时，长任务总是得不到处理机，也会产生饥饿现象。而时间片调度算法不可能产生饥饿现象。
    - （10）分时系统中，响应时间与时间片和用户数成正比，因此当分时系统的时间片固定时，用户数越多，响应时间越长。UNIX是一个强大的多用户、多任务操作系统，支持多宗处理器架构，按照操作系统分类，属于分时操作系统。中断向量本身是用于存放中断服务例行程序的入口地址，因此中断向量地址就应是该入口地址的地址。中断由硬件保护并完成，主要是为了保证系统运行可靠、正确，提高处理速度也是一个好处，但不是主要目的。
- 2.3 进程同步
  - 2.3.1 进程同步的基本概念
    - 0. 进程同步
      - 引入目的：为了协调进程之间的相互制约关系。
        例如1+2x3要求是先乘法再加法。但由于计算机操作系统的异步性，可能发生先加法后乘法的情况，而同步就是使计算机系统按照先乘法再加法的顺序进行。
    - 1. 临界资源
      - 临界资源：即一次仅允许一个进程使用的资源称为临界资源。
        如打印机等物理设备及许多可以被若干进程共享的变量、数据等。
      - 把临界资源的访问过程分为四个部分：
        
        对临界资源的访问必须互斥（就是你正在访问那么我就不能访问了，我正在访问你就不能访问了）的进行。
        
        （1）进入区。在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
        
        （2）临界区（又称临界段）。进程中访问临界资源的那段代码。
        
        （3）退出区。将正在访问临界区的标志清除。
        
        （4）剩余区。代码中的其他部分。
    - 2. 同步
      - 同步：即直接制约的关系，是指为完成某种任务而建立的量或多个进程，在位置上协调它们的工作次序。
    - 3. 互斥
      - 互斥：也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许访问此临界资源。
        比如说打印问题。
      - 为了禁止两个进程同时进入临界区，同步机制应遵循以下原则：
        
        （1）空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
        
        （2）忙则等待。当临界区已有进程时，其他试图进入临界区的进程必须等待。
        
        （3）有限等待。必须保证请求的进程在有限时间内能够进入临界区。
        
        （4）让权等待。当进程不能进入临界区时，应立即释放处理机资源，防止进程忙等待。
  - 2.3.2 实现临界区互斥的基本方法
    - 1. 软件实现方法
      - （1）算法一：单标志法
        
        两个进程无法交替进入临界区（违背“空闲让进”）：指的是当P0进入临界区又回来后，会将turn置为1，此时临界区是空闲的，允许P1进入临界区，但是问题来了，P1暂时不想进入临界区，而P0现在又想进入临界区了，可是turn现在为1只允许P1进入，导致P0不能进入，所以违背了“空闲让进”原则。
      - （2）算法二：双标志法先检查
        
        可能两个进程同时进入临界区（违背“忙则等待”）：即检查对方的flag是否为TRUE和切换自己的flag为TRUE前有一段时间，可能发生结果都检查通过，问题是检查和修改操作要分两次完成而不能一次完成。P0现在想要进入临界区了，在进入之前，先检查P1是否在临界区，发现P1不在临界区它的flag为FALSE，表示此刻P0可以进入临界区，然后P0就准备将自己的flag置为TRUE表示正在临界区，但是问题来了，在P0修改成功之前，P1现在也想要进入临界区，检查P0的flag为FLASE（因为还没有修改成功），然后P0就认为自己被允许进入临界区，所以也修改自己的flag，最后就会导致两个进程P0和P1同时将自己的flag修改为TRUE，发生同时进入临界区的问题，违背“忙则等待”原则。
      - （3）算法三：双标志法后检查
        
        两个进程谁也不能进入临界区（“饥饿”现象）：进程P0现在想要进入临界区，所以将自己的flag标志置为TRUE，然后检测P1进程的标志，这个时候（即未检测到P1状态之前），P1也想进入临界区，所以也将自己的flag标志置为TRUE，然后也检测P0的标志，问题来了，P0发现P1标志为TRUE，P1也发现P0标志为TRUE，都互相谦让，然后都不能进入，就会产生“饥饿”现象。
      - （4）算法四：Peterson's Algorithm
        
        利用flag解决临界资源的互斥访问并且利用turn解决“饥饿”现象（是算法一和算法三的结合）：P0将自己的flag标志设置为TRUE表示自己想要进入临界区，然后再设置turn=1表示允许P1进程进入临界区，检测只有当P1的flag标志为TRUE并且turn=1时表示P1已经在临界区，P0进程只能等待，若P1不想进入临界区，即它的flag标志为FALSE，则P0可以进入临界区。
    - 2. 硬件实现方法
      - （1）中断屏蔽方法
      - （2）硬件指令方法
        
        TestAndSet指令：读出指定标志然后将该标志设置为真。这条指令属于原子操作，不允许被中断。
        
        TestAndSet指令功能描述是：
        
        利用该指令实现进程互斥的算法描述如下：
        
        为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false表示未被占用。在进程访问临界资源之前，利用TestAndSet指令检查和修改标志lock；若有进程正在占用临界区，则反复检查，直到进程退出。
        
        Swap指令：功能是交换两个字（字节）的内容。
        
        Swap指令功能描述如下：
        
        利用该指令实现进程互斥的算法描述如下：
        
        为每个临界资源设置一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区前，先利用Swap指令交换lock与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。
  - 2.3.3 信号量
    - 0. 概念
      - 信号量：用来解决互斥与同步问题的，它只能被两个标准的原语wait(S)和signal(S)访问，也可记为“P操作”和“V操作”。
      - 原语：是指完成某种功能且不被分割、不被中断执行的操作序列，通常由硬件实现。
    - 1. 整型信号量
    - 2. 记录型信号量
    - 3. 利用信号量实现同步
      信号量机制能用于解决各种同步问题。
      - 例如，设S为实现进程P1、P2同步的公共信号量，初值为0。进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成后语句y才能执行（即要先执行P1进程再执行P2进程，但由于操作系统的异步性，可能先执行P2进程再执行P1进程，所以需要进程同步来解决这个问题）。实现同步的算法如下：
        
        若P2先执行，在运行y语句之前就会执行P(S)检查，那么由于P1进程并没有执行，则S为0，执行P操作就会把进程P2阻塞，放入阻塞队列；当P1进程中的x语句执行完成后，执行到V(S)操作，把P2从阻塞队列中放回到就绪队列，当P2得到处理机时，得以继续执行。
    - 4. 利用信号量实现进程互斥
      信号量机制也能解决进程互斥问题。
      - 例如，设S为实现进程P1，P2互斥的信号量，由于每次只允许一个进程进入临界区，所以S的初值应为1（即可用资源数为1）。只需把临界区置于P(S)和V(S)之间，即可实现两个进程对临界资源的访问。实现互斥的算法如下：
        
        当没有进程进入临界区时，任意一个进程进入临界区，就要只需P操作，把S的值减为0，然后进入临界区；当有进程存在于临界区时，S的值为0，再有进程要进入临界区，执行P操作时将会被阻塞，直至临界区的进程退出，这便实现了临界区的互斥。
      - PV操作在同步互斥中的应用总结：
        
        在同步问题中，若某个行为需要用到某种资源，则在这个行为前P这种资源（即检查是否有这种资源）；若某个行为会提供某种资源，则在这个行为后面V这种资源一下（即提供这种资源以便P操作检查）。
        
        在互斥问题种，P、V操作要紧夹使用互斥资源的哪个行为，中间不能有其他冗余代码。
    - 5. 利用信号量实现前驱关系
      信号量机制也可以用来描述程序之间或语句之间的前驱关系。
      - 例如，如下图的前驱图，其中S1，S2，...，S6都是最简单的程序段，为使各程序段正常运行，应该设置若干初始值为“0”的信号量。
        
        第一步：分析关系
        
        第二步：实现算法如下
    - 6. 分析进程同步和互斥问题的方法步骤
      - （1）关系分析。找出问题的进程数，并分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中经典范式改写。
      - （2）整理思路。找出解决问题的关键点，并根据做过的题目找出求解的思路。根据进程的操作流程确定P操作、V操作的大致顺序。
      - （3）设置信号量。根据上面的两步，设置需要的信号量，确定初值，完善整理。
  - 2.3.4 管程
    - 0. 前言
      - 管程的引入：在信号量机制中，每个要访问临界资源的进程都必须自备同步的PV操作，大量分散的同步操作不便管理，而且容易因同步操作不当导致死锁，所以产生了新的进程同步工具——管程。
      - 管程的优点：保证了进程互斥，无须程序员自己实现互斥，降低了死锁发生的可能性。同时提供了条件变量，使程序员可以灵活地实现进程同步。
    - 1. 管程的定义
      - 管程的定义：由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件。
      - 管程的组成：
        
        ①管程的名称
        
        ②局部于管程内部的共享结构数据说明。
        
        ③对该数据结构进行操作的一组过程（或函数）
        
        ④对局部于管程内部的共享数据设置初始值的语句
      - 管程的举例：
        
        举例：类似于Java语言中的类（class）结构
      - 管程的特点：
        
        （1）管程把对共享资源的操作封装起来，一个进程只能通过调用管程内的过程才能进入管程访问共享资源。
        
        （2）每次仅允许一个进程进入管程，从而实现进程互斥。
    - 2. 条件变量
      - 条件变量：即一个进程进入管程后被阻塞的原因定义为条件变量condition。
        通常，一个进程有多个阻塞原因，故可以有多个条件变量。
      - 条件变量只能进行两种操作：wait和signal。
        
        x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。
        
        x.signal：当x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程。
      - 条件变量和信号量的比较
  - 2.3.5 经典同步问题
    - 1. 生产者-消费者问题
      经典的同步互斥综合问题。
      - 问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区属于临界资源，它只允许一个生产者放入消息，或一个消费者取出消息。
      - 问题分析：
        
        （1）关系分析。由于缓冲区属于临界资源故生产者和消费者对缓冲区的访问属于互斥访问，是互斥关系；由于必须先有生产者生成消息消费者才能取出消费，有先后顺序，所以又是同步关系。
        
        （2）整理思路。进程：生产者进程和消费者进程；关系：同步和互斥关系。
        
        （3）信号量设置。互斥访问缓冲区需要一个信号量mutex，初始值为1；信号量full记录当前缓冲池“满”缓冲区的个数，初始为0，这是题目设置的；信号量empty记录当前缓冲池“空”缓冲区的个数，初值为n，也是题目设置的。
      - 代码描述：
        
        第一步：初始化信号量
        
        第二步：写进程，有几个写几个
        
        第三步：在进程内写具体的PV操作
    - 1. 复杂的生产者-消费者问题
      - 问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸转向盘子中放苹果，妈妈转向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时爸爸或妈妈才能向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。
      - 问题分析：
        
        （1）关系分析：由每次只可向其中放入一只水果可知爸爸和妈妈是互斥关系，对象盘子放水果是互斥的。爸爸和女儿、妈妈和儿子是同步关系，即要爸爸或妈妈要先放水果，女儿或儿子才能取水果吃，是先后顺序。儿子和女儿没有互斥和同步的关系，是选择条件执行，有需要的水果才吃。爸爸放苹果和女儿吃苹果、妈妈放橘子和儿子吃橘子必须连续执行。
        
        （2）整理思路。这里有四个进程：爸爸进程、妈妈进程、儿子进程和女儿进程。可以抽象成两个生产者（爸爸和妈妈）和两个消费者（女儿和儿子）被连接到大小为1（只有一个盘子）的缓冲区上。
        
        （3）信号量设置。信号量plate表示释放允许盘子放入水果，是互斥信号量。信号量apple表示盘子中是否有苹果，初值为0表示没有苹果可取；信号量orange表示盘子中是否有橘子，初值为0表示没有橘子可取。
      - 代码描述：
        
        第一步：初始化信号量
        
        第二步：写进程，有几个写几个
        
        第三步：在进程内写具体的PV操作
        
        dad()和daughter()、mom()和son()必须连续执行，也只能在女儿拿走苹果或儿子拿走橘子后才能释放盘子，即V(plate)操作。
        
        自己理解
    - 2. 读者-写者问题
      读者-写者问题最关键的是有一个互斥访问的计数器count，如果遇到不好解决的同步互斥问题，可以考虑使用count能否解决。
      - 问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不好产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者向文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。
      - 问题分析：
        读者写者问题最核心的问题是如何处理多个读者可以同时对文件的读操作。
        
        （1）关系分析。读者和写者是互斥的；写者和写者也是互斥的；读者和读者不存在互斥关系。
        
        （2）整理思路。两个进程，即读者进程和写者进程。写者和任何进程都互斥，用互斥信号量的PV操作解决。读者问题较为复杂，必须在实现与写者互斥的同时，实现与其他读者的同步，这里会用到一个计数器，用来判断是否有读者读文件。当有读者时，写者无法写文件，此时读者一直占用文件；当没有读者时，写者才可以写文件。不同读者对计数器的访问是互斥的。
        
        （3）信号量设置。信号量count为计数器，用来记录当前读者的数量，初值为0，表示没有一个读者；信号量mutex为互斥信号量，用来保护更新count变量时的互斥，初值为1；信号量rw也为互斥信号量，用来保证读者和写者的互斥访问，初值为1。
      - 代码描述（读进程优先）：
        在下面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件，可能导致写进程长时间等待，且存在写进程“饿死”的情况。
        
        第一步：初始化信号量
        
        第二步：写进程，有几个写几个
        
        第三步：在进程内写具体的PV操作
      - 代码描述（写进程优先）：
        如果希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问时，这时应禁止后续读进程的请求，等到已在共享文件的读进程完毕，立刻让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。解决方法就是增加一个信号量w并在上面的读进程优先的程序中的writer()和reader()函数中各增加一对PV操作。
        
        具体代码
        
        这里的写进程优先是相对而言的，也成为读写公平法，即读写进程具有一样的优先级。
    - 3. 哲学家进餐问题
      - 问题描述：一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭，如图2.10所示。哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
      - 问题分析：
        
        （1）关系分析。五名哲学家与左右邻居对其中间筷子的访问是互斥关系。
        
        （2）整理思路。五个哲学家进程。本题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁或饥饿现象。解决方法是：一是让他们同时拿两根筷子；二是对每名哲学家的动作制定规则，避免饥饿或死锁现象的发生。
        
        （3）信号量设置。定义互斥信号量数组chopstick={1,1,1,1,1}，用于对5个筷子的互斥访问。哲学家按顺序编号0~4，哲学家i左边筷子的编号为i，哲学家右边筷子的编号为(i+1)%5。
      - 代码描述（思考，可以这样吗？）：
      - 代码描述（存在死锁问题）：
        
        该算法存在以下问题：当五名哲学家都想要进餐并分别拿起左边的筷子时（都恰好执行完成wait(chopstick[i]);）筷子已被拿光，等到他们想要再拿起右边的筷子时（执行wait(chopstick[(i+1)%5]);）就全被阻塞，因此出现了死锁。
      - 代码描述（解决死锁方法）：
        
        为了防止死锁发生，可以对哲学家进程添加一些限制条件，比如至多允许4名哲学家同时进餐；仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子；对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。下面的算法是第二种方法：当一名哲学家左右两边的筷子都可用时才允许抓起筷子。
    - 4. 吸烟者问题
      - 问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复(让三个抽烟者轮流地抽烟)。
      - 问题分析:
        
        （1）关系分析。供应者与三个抽烟者分别是同步关系。由于供应者无法同时满足两个或以上的抽烟者，三个抽烟者对抽烟这个动作互斥(或由三个抽烟者轮流抽烟得知)。
        
        （2）整理思路。显然这里有4个进程。供应者作为生产者向三个抽烟者提供材料。
        
        （3）信号量设置。信号量offer1、offer2、offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。
      - 代码描述
        
        第一步：初始化信号量
        
        第二步：写进程，有几个写几个
        
        第三步：在进程内写具体的PV操作
- 2.4 死锁
  - 2.4.1 死锁的概念
    - 1. 死锁的定义
      - 是指多个进程因竞争资源而造成的一种僵局（互相等待）。
        例如，进程P1和P2分别正在使用资源A和资源B，但是进程P1又提出请求正被P2使用的B资源，进程2又提出请求正被P1使用的A资源，这样两个进程相互无休止的等待下去，均无法继续执行，此时两个进程陷入死锁状态。
    - 2. 死锁产生的原因
      - （1）系统资源的竞争
        
        系统中拥有的不可剥夺资源的数量不足以满足多个进程运行的需要，因争夺资源而陷入僵局。
        注意：只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源的竞争不会产生死锁。
        
        系统中资源分为两类：
        
        可剥夺资源：指进程在获得这类资源后，该资源可以被其他进程或系统剥夺。例如CPU和主存都是可剥夺性资源。
        
        不可剥夺资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。
      - （2）进程推进顺序非法
        
        进程运行过程中，请求和释放资源的顺序不当，也会导致死锁。
        例如：并发进程P1，P2分别占有了资源A和B，而进程P1又申请资源B、进程P2又申请资源A，两者都会因为所需资源被占用而阻塞。
        
        信号量使用不当也会造成死锁。
        例如：进程A等待进程B的消息，进程B又在等待进程A发的消息，可以看出不是因为竞争同一资源，而是在等待对方的资源而导致死锁。
      - （3）死锁产生的必要条件
        产生死锁必须同时满足以下四个条件，只要其中任意一个不成立，都不会产生死锁。
        
        互斥条件：即在一段时间内，某资源仅为一个进程所占有，在此期间若有其他进程请求该资源，只能排队等待。
        
        不剥夺条件：即进程所获得的资源在未用完之前不能被其他进程强行夺走，只能自己主动释放。
        
        请求并保持条件：即进程已经占有了至少一个资源，但又提出了新的资源请求，而所请求的资源被其他进程占有，故请求进程阻塞，而自己占有的资源又不释放。
        
        循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。即存在一个等待态的进程集合{P1,P2,...,PN}，其中P[i]等待的资源被P[i+1]（i=0,1,...,n-1）占有，P[n]等待的资源被P[0]占有。
  - 2.4.2 死锁的处理策略
    预防死锁和避免死锁都属于事先预防的策略。
    - 1. 死锁预防：设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。
    - 2. 避免死锁：在资源的动态分配中，用某种方法防止系统进入不安全状态，从而避免死锁。
    - 3. 死锁的检测及解除：允许进程发生死锁，通过系统的检测及时地检测出死锁的发生，然后采取某种措施解除死锁。
    - 死锁的几种处理策略的比较
      - 比较
  - 2.4.3 死锁预防
    死锁预防的发生只需要破坏死锁产生的四个必要条件之一即可。
    - 1. 破坏互斥条件
    - 2. 破坏不剥夺条件
    - 3. 破坏请求并保持条件
    - 4. 破坏循环等待条件
    - 死锁预防的几种方法的比较
  - 2.4.4 死锁避免
    - 1. 系统安全状态
      - 所谓安全状态，就是找到一个安全序列能够满足每个进程对自由的最大需求，使每个进程可顺利完成。如果无法找到安全序列，则称系统处于不安全状态。
      - 实例
        
        （1）在T0时刻系统是安全的。因为存在安全序列P2,P1,P3。 ①当前可用磁带机为3台，把这3台分配给P2以满足最大需求，P2结束并归还资源后，系统有5台磁带机可用； ②接下来将5台磁带机分配给P1使用以满足最大需求，P1结束并归还资源后，系统有10台磁带机可用； ③最后分配7台给P3使用，P3也能顺利完成。（2）若在T0时刻后系统分配1台磁带机给P3，系统剩余资源为2，此时系统进入不安全状态，因为找不到安全序列。 ①把剩下的2台磁带机分配给P2，这样P2完成后只能释放4台磁带机，既不能满足P1又不能满足P3，彼此都在等待对方资源，陷入死锁。
      - 并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。
    - 2. 银行家家算法
      银行家算法是最著名的死锁避免算法。银行家算法：次啊用预分配策略检查分配完成时系统是否处于安全状态。
      - （1）数据结构描述
        
        可利用资源向量Available：代表可用资源，即待分配的资源。
        
        最大需求矩阵Max：代表每个进程对某类资源的最大需求。
        
        分配矩阵Allocation：定义系统中已经分配的资源数。
        
        需求矩阵Need：代表每个进程接下来还需要多少资源。Need=Max-Allocation。
      - （2）银行家算法描述
        
        看看就行，具体看题
      - （3）安全性算法
        
        看看就行，具体看题
    - 3. 安全性算法举例
      详见课本。
    - 4. 银行家算法举例
      详见课本。
  - 2.4.5 死锁检测和解除
    检测死锁：利用死锁定理化简资源分配图以检测死锁的存在。
    - 1. 资源分配图
      - 系统死锁可用资源分配图来描述。
      - 圆圈代表一个进程；
      - 框代表一类资源；
      - 框中的一个圆代表一类资源中的一个资源；
      - 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；
      - 从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程。
      - 如图所示
    - 2. 死锁定理
      - 系统状态S为死锁的条件是当前仅当S状态的资源分配图是不可完全简化的，该条件为死锁定理。
    - 3. 死锁解除
      - （1）资源剥夺法：挂起某些死锁进程并抢夺它的资源，以便让其他进程继续推进。
      - （2）撤销进程法：强制撤销部分，甚至全部死锁进程并剥夺这些进程的资源。
      - （3）进程回退法：让一个或多个进程回退到足以回避死锁的地步。
  - 2.4.0 题目补充
    - （1）出现了循环等待的现象，意味着可能会导致死锁。进程释放资源不会导致死锁，进程自己进入死循环只能产生“饥饿”，不涉及其他进程。共享型设备允许多个进程申请使用，因此不会造成死锁。死锁一定要两个或两个以上的进程才会导致，而饥饿可能由一个进程导致。
    - （2）系统产生死锁的可能原因是独占资源分配不当。
    - （3）多道程序技术要求进程间能实现并发，需要实现进程调度以保证CPU的工作效率，而并发性的实现需要中断功能的支持。
    - （4）三个进程共享四个同类资源，这些资源的分配与释放只能一次一个，已知每个进程最多需要两个该类资源，则该系统进程请求该类资源必然能得到，不会发生死锁。因为每个进程都分得一个资源时，还有一个资源可用让任意一个进程满足，这样这个进程可用顺利运行完成而释放它的资源。
    - （5）资源分配图是一个有向图，用于表示某时刻系统资源与进程之间的关系。
    - （6）死锁的四个必要条件中，无法破坏的是互斥使用资源。
    - （7）死锁与不安全状态的关系：不是所有的不安全状态都是死锁状态，当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态；死锁状态必定是不安全状态。
      - 关系图表
    - （8）死锁检测一般采用两种方法：资源有向图法和资源矩阵法。前驱图只是说明进程之间的同步关系，搜索树用于数据结构的分析，安全图并不存在。注意死锁避免和死锁检测的区别：死锁避免是指避免死锁发生，即死锁没有发生；死锁检测是指死锁已出现，要把它检测出来。
    - （9）某个进程主动释放资源不会导致死锁，因为破坏了请求并保持条件；回退是指从此时此刻的状态退回到一分钟之前的状态，假如一分钟之前拥有资源X，它有可能释放了资源X，那就不称回到一分钟之前的状态，也就不是回退；由于进程过于“慷概”，不断把自己已得到的资源送给必然，导致自己长期无法完成，所以是饥饿。
    - （10）出现了环路，只是满足了循环等待的必要条件，而满足必要条件不一定导致死锁，也就是说出现了环路不能判断是否处于死锁状态；没有环路，破坏了循环等待条件，一定不会发生死锁；每种资源只有一个，又出现了环路，这是死锁的充分必要条件，可用确定是否有死锁；即使每个进程至少有一条请求边，若资源足够，则不会发生死锁，但若资源不足，则有可能发生死锁。
第3章内存管理
- 3.1 内存管理概念
  - 3.1.1 内存管理的基本原理和要求
    - 内存管理概念
      - 内存管理：操作系统对内存的划分和动态分配。
      - 为什么要进行内存管理：
        
        方便用户使用存储器
        
        提高内存利用率
        
        通过虚拟技术从逻辑上扩充存储器
      - 内存管理的功能：
        
        内存空间的分配和回收。由操作系统完成对主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率。
        
        地址转换。把逻辑地址转换成相应的物理地址。
        
        内存空间的扩充。利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。
        
        存储保护。保证各道作业在各自的存储空间内运行，互不干扰。
    - 进程运行的基本原理和要求
      在进行具体的内存管理之前，需要了解进程运行的基本原理和要求。
      - 1. 程序装入和链接
        
        将用户程序变为可在内存中执行的程序的步骤：
        
        编译。由编译程序将用户源代码编译成若干目标模块。
        
        链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起，形成一个完整的装入模块。
        
        装入。由装入程序将装入模块装入内存运行。
        
        程序的链接有以下三种方式：
        
        静态链接。
        
        装入时动态链接。
        
        运行时动态链接。
        
        内存的装入模块在装入内存时也有三种方式：
        
        （1）绝对装入。
        
        （2）可重定位装入（静态重定位）。
        
        （3）动态运行时装入（动态重定位）。
      - 2. 逻辑地址空间和物理地址空间
        
        相对地址（逻辑地址）：编译后，每个目标模块都是从0号单元开始编址，这称为目标模块的相对地址。
        
        逻辑地址空间：当链接程序把各个目标模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块相对地址构成统一的从0号单元开始编址的逻辑地址空间。
        用户程序和程序员只需知道逻辑地址，只有系统编程人员才涉及内存管理的具体机制。不同进程可以由相同的逻辑地址，因为会映射到主存的不同位置。
        
        物理地址空间：是指内存中物理单元的集合，它是地址转换的最终地址。
        
        地址重定位：当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程就叫地址重定位。
      - 3. 内存保护
        
        内存保护是什么：在内存分配前，需要保护操作系统不受用户进程的影响，同事保护用户进程不受其他用户进程的影响。
        
        内存保护可采用的两种方法：
        
        （1）在CPU中设置一对上、下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。
        
        （2）采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长寄存器）来实习这种保护。内存管理结构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交给内存单元。
        
        重定位寄存器含最小的物理地址值。界地址寄存器含逻辑地址的最大值。每个逻辑地址值必须小于地址寄存器。
        
        注意重定位寄存器和界地址寄存器的区别：
        
        重定位寄存器是用来“加”的，逻辑地址加上重定位寄存器中的值就能得到物理地址；
        
        界地址寄存器是用来“比”的，通过比较界地址寄存器中的值与逻辑地址的值判断是否越界。
  - 3.1.2 覆盖与交换
    
    覆盖和交换技术是在多道程序环境下用来扩充内存的两种方法。
    - 1. 覆盖
    - 2. 交换
  - 3.1.3 连续分配管理方式
    
    连续分配方式指为一个用户程序分配一个连续的内存空间。连续分配方式主要包括单一连续分配、固定区分配和动态区分配。
    - 1. 单一连续分配
    - 2. 固定区分配
      - 固定分区分配在划分分区时有两种不同的方法：
        
        分区大小相等。用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性。
        
        分区大小不等。划分多个较小的分区、适量的中等分区和少量大分区。
      - 分区说明表：
        
        引入目的：为了便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表。
        
        表项：包括每个分区的始址、大小及状态（是否已分配）。
        
        应用：当有用户程序要装入时，便检索该表，以找到合适的分区给予分配并将其状态置为“已分配”；未找到合适分区时，则拒绝为该程序分配内存。
      - 这种分区方式存在的两个问题：
        
        一是程序可能太大不能放入任何一个分区，用户不得不采用覆盖技术来使用内存空间；
        
        二是主存利用率低，当程序小于固定分区大小时，用不完一个完整的内存分区空间，这样造成的分区内部空间浪费，也就是内部碎片。
    - 3. 动态分区分配
      - 动态分区的分配策略算法：
        
        各算法比较：
        
        在内存空间利用上：首次适应算法 > 最佳适应算法 > 最大适应算法。
        
        算法实现上：最佳适应算法和最大适应算法都需要对可用块进行排序或遍历查找，而首次适应算法和邻近适应算法只需要简单查找。
        
        在回收上：当回收的块与原来的空闲块相邻时需要进行合并。
  - 3.1.4 非连续分配管理方式
    非连续分配方式是指允许一个程序分散地装入不相邻的内存分区中。
    - 0. 分类
      
      非连续分配方式根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。在分页存储管理方式中，根据允许作业时是否要把作业的所有页面都调入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。
    - 1. 基本分页存储管理方式
      - （0）前言
        
        引入分页的目的：为了尽量避免碎片的产生。（固定分区会产生内部碎片、动态分区会产生外部碎片）
        采用分页管理后不会产生外部碎片，每个进程平均只产生半个块大小的内部碎片（也称业内碎片）。
        
        分页的思想：把内存空间划分为大小相等且固定的块，块相对较小，作为内存的基本单位。每个进程也以块为单位进行划分，进程在执行时，也以块为单位申请内存中的块空间。
      - （1）分页存储的几个基本概念
        
        ①页面和页面大小
        
        页（Page）：进程中的块称为页。
        
        页框（Page Frame）：内存中的块称为页框。
        进程执行时申请内存空间，即页面分配可用页框，页和页框一一对应。
        
        块（Block）：外存也以同样的单位划分，直接称为块。
        
        页面大小：为了方便地址转换，页面大小应是2的整数幂。页面大小要适中。
        
        页面太小：造成进程的页面数过多，这样页表就会过长，占用大量内存；而且会增加硬件地址转换的开销，降低页面换入/换出的效率。
        
        页面过大：使业内碎片增多，降低内存的利用率。
        
        ②地址结构
        注意：地址结构决定了虚拟内存的寻址空间有多大。
        
        分页存储管理的逻辑地址结构
        
        ③页表
        
        页表的组成：页表项。页表项的组成如下：
        
        页表项的作用：找到该页在内存中的位置。
        
        页表项与地址结构的区别：
        
        都由两部分组成；
        
        第一部分都是页号；
        
        页表项的第二部分是物理内存中的块号，地址结构中的第二部分是业内偏移；
        
        页表项的第二部分与地址的第二部分共同组成物理地址。
        
        页表的作用：实现从页号到物理块号的地址映射，页表一般存放在内存中。
        
        配置页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。
      - （2）基本地址变换机构
        
        地址变换机构的作用：将逻辑地址转换为内存中的物理地址。地址变换借助于页表实现。
        
        设页面大小为L，逻辑地址A到物理地址E的变换过程如下（逻辑地址、叶红、每页的长度都是十进制数）：
        
        系统中设置的页表寄存器（PTR），存放页表在内存的起始地址F和页表长度M。进程未执行时页表的始址和长度存放在进程控制块（PCB）中；进程执行时，才放入页表寄存器（PTR）中。整个地址变换过程由硬件自动完成。页式管理中地址空间是一维的。
        
        ①计算页号P（P=A/L，如5/2=2）和页内偏移量W（W=A%L，如5%2=1）。
        
        ②比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行。
        
        ③页表中页号P对应的页表项地址 = 页表始址F + 页号P x 页表项长度，取出该页表项内容b，即为物理块号。
        区分页表长度和页表项长度：页表长度指一共有多少页；页表项长度指页地址占多大的存储空间。
        
        ④计算逻辑地址E = b x L + W，用得到的物理地址E去访问内存。
        
        ⑤例题：若页面大小L为1KB，页号2对应的物理块为b=8，计算逻辑地址A=2500的物理地址E的过程如下：
        页号P=A/L=2500/1KB=2500/1024=2；页内偏移量W=A%L=2500%1KB=2500%1024=452；逻辑地址E=b x L + W=8*1KB+452=8*1024+452=8644。
        
        分页管理方式存在的两个主要问题：
        
        ①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低。
        
        ②每个进程引入页表，用于存储映射机制，页表不能太大，否则内存的利用率会降低。
      - （3）具有快表的地址变换机构
        
        单纯的地址变换机构存在的问题：若页表全部放在内存中，则存取一个数据或一条指令需要至少两次访问内存，第一次是访问页表确定所取数据或指令的物理地址，第二次是根据该地址存取数据或指令。这种方法比通常执行指令速度慢了一半。解决方法是引入快表。
        
        快表（又称相联存储器(TLB)）：一个具有并行查找能力的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，主存中的页表称为慢表。
        快表的有效性基于著名的局部性原理。
        
        具有快表的地址变换结构，地址的变换过程如下：先去快表找，若找到则取出对应页号同业内偏移量拼接形成物理地址，这样存取数据近一次访存就能实现；若未找到则访问主存中的页表，在读出页表后，同时将其存入快表以便以后可能的再次访问。若快表已满，按一定算法对旧的页表项进行替换。
      - （4）两级页表
        
        两次页表逻辑地址空间的格式
        
        二级页表结构示意图
        
        建立多级页表的目的：在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不能盲目地顺序式查找页表项。
    - 2. 基本分段存储管理方式
      - （0）前言
        
        分页管理方式的目的：提供内存的利用率，提升计算机的性能，分页通过硬件机制实现，对用户完全透明。
        
        分段管理方式的目的：考虑了用户和程序员，以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。
      - （1）分段
        
        分段：按照用户进程中的自然段划分逻辑空间。
        例如，用户进程由主程序、两个子程序、栈和一段数据组成，则可用划分为5段，每段从0开始编址，并分配一段连续的地址空间。（要求段内连续，段间不要求连续，整个作业空间是二维的）
        
        分段系统中的逻辑地址结构
        
        页式系统中，逻辑地址的页号和页内偏移量对用户是透明的。段式系统中，逻辑地址的段号和段内偏移量必须由用户显式提供，在高级程序设计语言中，这个工作由编译程序完成。
      - （2）段表
        
        段表的组成：段表项。段表的内容如下：
        
        每个进程都有一张段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度。
        
        段表的作用：用于实现从逻辑段到物理内存区的映射。
      - （3）地址变换机构
        
        地址变换机构的作用：实现进程从逻辑地址到物理地址的变换功能。
        系统中设置的段表寄存器，用于存放段表始址F和段表长度M。
        
        从逻辑地址A到物理地址E之间的地址变换过程如下：
        
        ①从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。
        注意，段式存储管理的题目中，逻辑地址以二进制给出；页式存储管理的题目中，逻辑地址以十进制给出。但具体问题具体分析。
        
        ②比较段号S和段表长度M，若S>=M，则产生越界中断，否则继续执行。
        
        ③段表中段号S对应的段表项地址=段表始址F + 段号S x 段表项长度。取出该段表项的前几位得到段长C。若段内偏移量>=C，则产生越界中断，否则继续执行。
        段表项实际只有两部分，前几位是段长，后几位是始址。
        
        ④取出段表项中该段的始址b，计算物理地址E=b+W，用得到的物理地址E去访问内存。
      - （4）段的共享与保护
        
        段的共享：在段式系统中，通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
        注意：当一个作业正在从共享段读取数据时，必须防止另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码（它不属于临界资源），这样的代码和不能修改的数据可以共享，可修改的代码和数据不能共享。
        
        段的保护：
        注意：页式管理可以根据给出的一个整数确定对应的物理地址，但段式管理不能，因为段的长度不固定，页面大小是固定的，所以必须给出段号和段内偏移，因此段式管理的地址空间是二维的。
        
        一种是存取控制保护；
        
        另一种是地址越界保护。
        地址越界保护将段表寄存器中的段表长度与逻辑地址中的段号进行比较，若段号大于段表长度，则产生越界中断；再将段表项的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，页号产生越界中断。注意：分页管理中的地址越界保护只需要判断页号是否越界，页内偏移是不可能越界的。
    - 3. 段页式管理方式
      - 引入：页式存储管理提供了内存利用率，段式存储管理反映程序的逻辑结构有利于段的共享，将这两种存储管理方法结合起来就是段页式存储管理方式。
      - 段页式管理：在段页式系统中，作业的地址空间被分成若干逻辑段，然后将每个段分成若干固定大小的页。对内存空间的管理仍然和页式管理一样。
        
        段页式管理的地址空间是二维的。
      - 段页式系统的逻辑地址结构：
      - 段表与页表：为了实现地址变换，系统为每个进程建立一张段表，每个分段建立一张页表。（注意：在一个进程中，段表只有一个，而页表可能有多个）
        段表寄存器和页表寄存器的作用都有两个：一个是在段表或页表寻址；而是判断是否越界。
      - 地址变换机构：进行地址变换时，首先通过段表查到页表始址，然后通过页表找到块号，最后形成物理地址。
        
        进行一次访问需要三次访问主存，可以使用快表技术加快查找速度，其关键字由段号、页号组成，值是对应的块号和保护码。
- 3.2 虚拟内存管理
  - 3.2.1 虚拟内存的基本概念
    - 1. 传统存储管理方式的特征：一次性和驻留性。
      由于作业一次性全部装入并且一直驻留在内存中不被换出，浪费了内存资源。
    - 2. 局部性原理
      - 应用：如快表、页高速缓存及虚拟内存技术（都属于高速缓存技术，这个技术依赖于局部性原理）。
      - 局部性原理表现的两个方面：
        
        （1）时间局部性。某条指令或数据执行访问过，不久又会被再次执行访问。
        时间局部性产生的原因是存在着大量循环操作。
        
        （2）空间局部性。程序访问了某存储单元，那么不久后，其周围附件的也将被访问。
    - 3. 虚拟存储器的定义和特征
      - 虚拟存储器原理：在程序装入时，只将一部分装入内存，其他部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时用不到的内容换出到外存上，从而腾出空间放将要调入内存的信息。
        简而言之：程序不一次性全调入内存，在需要的时候再调入内存，并且将暂时用不到的内容换出到外存。
      - 虚拟存储器的特点
        
        （1）多次性。指作业无须一次性全部装入内存，而是在需要时多次调入。
        
        （2）对换性。指作业无须一直驻留在内存，允许在作业的运行过程中换进和换出。
        
        （3）虚拟性。实际上并没有增加内存容量，只是从逻辑上扩充内存容量。
    - 4. 虚拟内存技术的实现
      虚拟内存的实现如果采用连续分配的方式，会造成内存资源的浪费，也无法从逻辑上扩大内存容量。虚拟内存的实现需要采用离散分配的内存管理方式。
      - 虚拟内存实现的三种方式：
        
        请求分页存储管理
        
        请求分段存储管理
        
        请求段页式存储管理
      - 无论哪种方式，都需要一定硬件支持，一般需要以下支持：
        
        一定容量的内存和外存。
        
        页表机制（或段表机制），作为主要的数据结构。
        
        中断机构，当缺页（即程序要访问的部分不在内存时），则产生中断。
        
        地址变换机构，逻辑地址变换为物理地址。
  - 3.2.2 请求分页管理方式
    - 0. 请求分析管理方式：在请求分页系统中，只要求将当前需要的一部分页面装入内存，便快要启动作业。在作业执行过程中，当所要访问的页面不在内存中时，通过调页功能调入，同时考可以通过置换功能将暂时不用的页面换出到外存上。
      为了实现请求分页，需要硬件支持：一定容量的内存及外存的计算机系统、页表机制、缺页中断机构和地址变换机构。
    - 1. 页表机制
      - 请求分页系统中的页表项及参数说明：
        
        页号：页表项的号。
        
        物理块号：物理内存中的块号。
        
        状态位P：用于指示该页是否已调入内存，供程序访问时参考。
        
        访问字段A：用于记录本页在一段时间内被访问的次数或记录本页有多长时间未被访问，供置换算法换出页面时参考。
        
        修改位M：标识该页在调入内存后是否被修改过。
        
        外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入参考。
    - 2. 缺页中断机构
      - 每当所要访问的页面不在内存中时，便产生一个缺页中断。
      - 缺页中断与一般中断的相比，有两个明显区别：
        
        （1）在指令执行期间产生和处理中断信号，属于内部中断。
        
        （2）一条指令执行期间，可能产生多次缺页中断。
    - 3. 地址变换机构
      - 在进行地址变换时，先检索快表：
        
        若找到要访问的页，则修改页表项中的访问位（写指令还需要重置修改位，表示该页被修改过），然后利用页表项中给出的物理块号和业内地址形成物理地址。
        
        若未找到该页的页表项，则应到内存中去查找页表项，再对比页表项中的状态位P，看是否已经调入内存，未调入则产生缺页中断，请求从外存把该页调入内存。
  - 3.2.3 页面置换算法（决定应该换入哪页、换出哪页）
    - 0. 前言
      - 为什么需要页面置换算法：进程运行时，若其访问的页面不在内存中需要将其调入，但内存无空闲空间，那么需要考虑从内存中调出一页数据或程序，然后腾出空间来调入需要的页。
      - 页面置换算法的定义：选择调出页面的算法就叫页面置换算法。
      - 页面置换算法的目标：将以后不会再访问或以后较长时间内不会再访问的页面先调出。
    - 1. 最佳（OPT）置换算法
      - 图表演示及注释说明
        
        ①内存中不存在页号为7的页面，因此缺页，直接调入。
        
        ②内存中不存在页号为0的页面，因此缺页，直接调入。
        
        ③内存中不存在页号为1的页面，因此缺页，直接调入。此时三个物理块填满，接下来就可能进行页面置换了。
        
        ④内存中不存在页号为2的页面，因此缺页，不能直接调入，因为三个物理块已满，需要进行置换，OPT置换算法是置换最长时间内不再被访问的页面，从此处往后数，发现页号为7最长时间内不会被访问，因此将物理块1中的7换出，然后调入2。
        
        ⑤内存中存在页号为0的页面，不缺页，不需要调入也不需要置换。
        
        ⑥内存中不存在页号为3的页面，因此缺页，不能直接调入，因为三个物理块已满，需要进行置换，OPT置换算法是置换最长时间内不再被访问的页面，从此处往后数，发现页号为1最长时间内不会被访问，因此将物理块3中的1换出，然后调入3。
        
        ⑦内存中存在页号为0的页面，不缺页，不需要调入也不需要置换。
    - 2. 先进先出（FIFO）页面置换算法
      - 图表演示及注释说明
        
        ①中有四个数分别为7、0、1、2，其中前三个为物理块中填满的，而红色的2是进行置换的，那么根据FIFO算法置换最先进入的，观察四个数，最先进入的是7，那么把物理块1中的7换成2。后面也是这样来的，通过上面的队列方便观察该置换哪个数出去。
        
        ②中有四个数分别为0、1、2、3，其中有个空格是表示物理块中已有此页，而红色的3是进行置换的，那么根据FIFO算法，观察四个数，最先进入的是0，因为7已经被置换掉了，所以是0，将0换成3。注意所有的都是4个数，这是由物理块的个数加一个待置换的页决定的。
    - 3. 最近最久未使用（LRU）置换算法
      - 图表演示及注释说明
    - 4. 时钟（CLOCK）置换算法
      暂无处理
      - CLOCK算法和改进型CLOCK算法
        
        在使用位（访问位）上再添加一个修改位，得到改进型CLOCK置换算法，使每页都处于以下四种情况：
        
        （1）最近未被访问，也未被修改（u=0,m=0）。
        
        （2）最近被访问，但未被修改（u=1,m=0）。
        
        （3）最近未被访问，但被修改（u=0,m=1）。
        
        （4）最近被访问，被修改（u=1,m=1）。
        
        改进型CLOCK算法优于简单CLOCK算法的地方在于替换时首选没有变化的页。
        
        CLOCK算法只考虑到是否被访问过，因此被访问过的当然尽可能留下，未使用过的就淘汰；而改进型CLOCK算法对使用过的页面又做了细分，分为使用过但未修改过和使用过且修改过，对于有未使用过的页面，则当然首先把它换出，若全面页面都使用过，则当然优先把未修改过的页面换出。
    - 5. 几种页面置换算法的比较
      - 图表比较
  - 3.2.4 页面分配策略
    - 1. 驻留集大小
      - 驻留集：给一个进程分配的物理页框的集合就是这个进程的驻留集。
        操作系统必须绝对读多少页（不可能把一个进程的所有页都读入注册），即决定给特定的进程分配几个页框。
      - 采用三种策略：
        
        （1）固定分配局部置换。
        
        （2）可变分配全局置换。
        
        （3）可变分配局部置换。
      - 三种策略的总结比较
    - 2. 调入页面的时机
      - 为确定系统将进程运行时所缺的页面调入内存的时机，有以下两种调页策略：
        
        （1）预调页策略。
        
        （2）请求调页策略。
      - 两种调页策略的比较
    - 3. 从何处调入页面
      - 请求分页系统中的外存分为两部分：
        
        用于存放文件的文件区，采用离散分配方式。
        
        用于存放对换页面的对换区，采用连续分配方式，磁盘I/O速度比文件区快。
      - 从何处调入页面存在三种情况：
        
        1)系统拥有足够的对换区空间。可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
        
        2)系统缺少足够的对换区空间。凡不会被修改的文件都直接从文件区调入:而当换出这些页面时，由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分，在将它们换出时须调到对换区，以后需要时再从对换区调入(因为读的速度比写的速度快)。
        
        3) UNIX方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于放在对换区，因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入。
  - 3.2.5 抖动
    - 抖动（颠簸）：即在页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的调度行为称为抖动。
    - 频繁发生抖动的原因：某个进程频繁访问的页面数目高于可用的物理页帧数。
  - 3.2.6 工作集
    - 工作集：指某段时间间隔内，进程要访问的页面集合。
    - 计算工作集
      
      注意：去掉重复项。
    - 工作集的特点
      - 基于局部性原理，可用用最近访问过的页面来确定工作集。
      - 工作集可由时间t和工作集窗口大小来确定。
      - 工作集反映了进程在接下来一段时间内可能会频繁访问的页面集合。
      - 若分配的物理块小于工作集大小，进程就可能频繁缺页。
      - 为了防止抖动现象，一般来说分配给进程的物理块数（即驻留集大小）要大于工作集大小。
  - 3.2.7 地址翻译
    暂无处理
    - TLB——页表（TLB不命中）——cache——主存（cache不命中）——外存（缺页）。
第4章文件管理
- 4.1 文件系统基础
  - 4.1.1 文件的概念
    - 1. 文件的定义
      - 文件（File）：是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。
        注：（1）在系统运行时，计算机以进程为基本单位进行资源的调度和分配。（2）在用户进行的输入、输出中，则以文件为基本单位。
      - 文件系统：用于实现用户输入、输出、访问、修改和保存文件等操作管理的。
        从用户角度讲，文件系统是操作系统的重要部分之一，用户关心如何命名、分类和查找文件，如何保证文件数据的安全性及对文件可以进行哪些操作。而对其中的细节如文件如何存储、如何管理文件辅存区域等不是很关心。
      - 文件的结构
        通过自底向上的方式来定义。
        
        （1）数据项。数据项是文件系统中最低级的数据组织形式，可分为以下两种类型：
        
        基本数据项。用于描述一个对象的某种属性的一个值，是数据中可命名的最小逻辑数据单位，即原子数据。
        如姓名、日期或证件号等。
        
        组合数据项。由多个基本数据项组成。
        
        （2）记录。是一组相关的数据项的集合，用于描述一个对象在某方面的属性。
        如一个考生的报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列。
        
        （3）文件。是指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种。
        
        有结构文件（又称记录式文件）：由一组相似的记录组成。
        如报考某学校的所有考生的报考信息记录。
        
        无结构文件（又称流式文件）：被视为一个字符流。
        如一个二进制文件或字符文件。
      - 文件的特点
        
        在操作系统中，通常讲程序和数据组织成文件。
        
        文件可以是数字、字母或二进制代码，基本访问单元可以是字节、行或记录。
        
        文件可以长期存储于硬盘或其他二级存储器中，允许可控制的进程间共享访问，能够被组织成复杂的结构。
    - 2. 文件的属性
      文件具有一定的属性，系统不同，文件的属性也会有所不同。
      - 通常文件有如下属性：
        
        （1）名称。文件名称唯一，以容易读取的形式保存。
        
        （2）标识符。标识文件系统内文件的唯一标签，通常为数字，是对人不可读的一种内部名称。
        
        （3）类型。被支持不同类型的文件系统所使用。
        
        （4）位置。指向设备和设备上文件的指针。
        
        （5）大小。文件的当前大小（用字节、字或块表示），也可以包含文件允许的最大值。
        
        （6）保护。对文件进行保护的访问控制信息。
        
        （7）时间、日期和用户标识。文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。
      - 文件的属性的特点
        
        所有文件的信息都保存在目录结构，而目录结构保存在外存上。
        
        文件信息在需要时才调入内存。
        
        通常目录条目包括文件名称及唯一的标识符，而标识符定位其他属性的信息。
    - 3. 文件的基本操作
      文件属于抽象数据类型。
      - （1）创建文件。
      - （2）写文件。
      - （3）读文件。
      - （4）文件重定位（文件寻址）。
      - （5）删除文件。先从目录中找到要删除文件的目录项，使之称为空项，然后回收该文件所占用的存储空间。
      - （6）截断文件。允许文件所有属性不变，并删除文件内容，即讲其长度设为0并释放其空间。
    - 4. 文件的打卡与关闭
      - 每个打开文件都有如下关联信息：
        
        文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对于打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
        
        文件打开计数。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目时，必须等待最后一个进程关闭文件。计数器跟踪打开和关闭的数量，计数为0时，系统关闭文件，删除该条目。
        
        文件磁盘位置。绝大多数文件操作都要求系统修改文件数据。该信息保存在内存中，以免为每个操作都从磁盘中读取。
        
        访问权限。每个进程打开文件都需要一个访问模式（创建、只读、读写、添加等）。该信息保留在进程的打开文件表中，以便操作系统能够允许或拒绝之后的I/O请求。
  - 4.1.2 文件的逻辑结构
    文件的逻辑结构实际上是指文件的内部，数据逻辑上是如何组织起来的。按逻辑结构，文件可划分为有结构文件和无结构文件。
    - 0. 文件的逻辑结构与物理结构的区别
      - 区别
    - 0. 有结构文件和无结构文件的区别
      - 区别
    - 1. 无结构文件（流式文件）
    - 2. 有结构文件（记录式文件）
      - （1）顺序文件。
      - （2）索引文件。
        索引表本身是定长记录的顺序文件。
        
        图示
        
        对于定长记录文件，要查找第 i 条记录，可直接根据式子计算得到第 i 条记录相对于第1条记录的地址：
        
        对于可变长记录文件，要查找第 i 条记录，必须顺序地查找前 i - 1 条记录，从而获得相应记录的长度L，进而按下式计算出第i条记录的首址：
      - （3）索引顺序文件。
        
        图示
        
        对于含有N条记录的顺序文件，查找某关键字值的记录时，平均需要查找N/2次。
        
        对于含有N条记录的索引顺序文件，假设N条记录分为√N组，索引表中有√N个表项，每组有√N条记录，查找某关键字值的记录时，先顺序查找索引表，需要查找√N/2次，然后在主文件对应的组中顺序查找，也需要查找√N/2次，因此共需要查找√N/2+√N/2=√N次。
      - （4）直接文件或散列文件。
  - 4.1.3 目录结构
    - 0. 前言：目录管理的基本要求
      - “按名存取”；
      - 提高对目录的检索速度；
      - 在共享系统中提供用于控制访问文件的信息；
      - 允许文件重名，通过树形结构解决和实现。
    - 1. 文件控制块和索引结点
      - （1）文件控制块
        
        定义：文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。
        
        FCB主要包含以下信息：
        
        基本信息。如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
        
        存取控制信息。如文件存取权限等。
        
        使用信息。如文件建立时间、修改时间等。
      - （2）索引结点
        
        引入目的：在检索目录文件的过程中，只用到了文件名，只有当查找文件名与目录项中文件名匹配成功时，才需要从该目录项中读取该文件的物理地址。故不需要把文件的所有信息都调入内存，可以节省系统开销。
        
        索引结点：有的系统（如UNIX）采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
        存在在磁盘上的所有结点称为磁盘所有结点，UNIX中的每个文件都有一个唯一的磁盘索引结点。文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。
    - 2. 目录结构
      - 在目录上可能需要执行的操作有：搜索、创建文件、删除文件、显示目录、修改目录等。
      - 考虑以下几种目录结构：
        
        （1）单级目录结构。
        
        访问：当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。
        
        新建：当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中。
        
        删除：当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。
        
        图示
        
        （2）两级目录结构。
        
        访问：当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD。
        
        图示
        
        （3）多级目录结构（树形目录结构）。
        
        访问：用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
        
        绝对路径：从根目录出发的路径称为绝对路径。
        
        相对路径：相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
        为什么引入当前目录：当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录。进程对各文件的访问都是相对于当前目录进行的。
        
        图示
        
        （4）无环图目录结构。
        
        删除：当某用户删除一个共享结点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。为此，可为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加1；每当某用户提出删除该结点时，计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。
        
        共享文件（或目录）与文件拷贝（副本）的区别：
        
        若两个文件拷贝，则每个程序员看到的是拷贝而不是原件，然而当一个文件被修改后，则另一个程序员的拷贝不会改变。
        
        对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见。
        
        图示
  - 4.1.4 文件共享
    - 1. 基于索引结点的共享方式（硬链接）
      - 硬链接是指共享文件指向同一个索引结点。
      - 在这种共享方式中，如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还有一个链接计数count，用于表示链接到本索引结点（即文件）上的用户目录项的数目。
        如count=2，表示有两个用户目录链接到本文件，或者说有两个用户共享此文件。
      - 文件的创建者删除原文件，那么索引结点也被删除了，但会留下一个悬空指针，使其他共享的用户不能访问到该文件了。
      - 如果想要删除，只需要将文件的count减1，然后删除字节目录中的相应目录项即可，其他用户仍可访问。当count=0时表示没有用户使用该文件，系统负责删除该文件。
    - 2. 利用符号链接实现文件共享（软链接）
      - 软连接是指保存共享文件的路径名，类似于Windows系统的快捷方式。
      - 文件的创建者删除原文件，其他用户通过符号链去访问它时，会出现访问失败，于是将符号链删除，不会产生任何影响。
      - 每次访问时，需要多次读盘，使得访问文件的开销变大并增加了启动磁盘的频率，此外，符号链的索引节点也需要耗费一定的磁盘空间。
      - 符号链的优点是即网络共享只需要提供该文件所在机器的网络地址及该机器中的文件路径。
    - 3. 硬链接和软链接的联系区别
      - 两种链接方式都存在一个共同问题，即每个共享文件都有几个文件名。遍历整个文件系统时，会多次遍历到该共享文件。
      - 硬链接和软链接都是文件系统中的静态共享方法。动态共享是指两个进程同时对同一个文件进行操作。
      - 硬链接就是多个指针指向一个索引结点，只要还有一个指针指向索引结点，索引节点就不能删除；软链接就算把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。
      - 硬链接的查找速度要比软链接的快。
  - 4.1.5 文件保护
    - 0. 前言
      - 为什么要引入文件保护：为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取。
      - 实现方式：口令保护、加密保护和访问控制等。
    - 1. 访问控制
      - 注意
        
        口令和密码保护都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型。
        
        目录操作与文件操作不同，因此需要不同的保护机制。
- 4.2 文件系统实现
  - 4.2.1 文件系统层次结构
    
    用一个例子来辅助记忆文件系统的层次结构：假设某用户请求删除文件“D:/工作目录/学生信息.xIsx"的最后100条记录。1. 用户需要通过操作系统提供的接口发出.上述请求-- -用户接口2. 由于用户提供的是文件的存放路径，因此需要操作系统- -层一层地查找目录，找到对应的目录项--文件目录系统3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限一一存取控制模块(存取控制验证层)4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址---逻辑文件系统与文件信息缓冲区5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址---物理文件系统6. 要删除这条记录，必定要对磁盘设备发出请求--设备管理程序模块7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收----辅助分配模块
    - 1. 用户调用接口：文件系统为用户提供与文件及目录有关的调用。
      如新建、打开、读写、关闭、删除文件，建立、删除目录等。
    - 2. 文件目录系统：主要功能是管理文件目录。
      如管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块。
    - 3. 存取控制验证模块：实现文件保护，把用户的访问请求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。
    - 4. 逻辑文件系统与文件信息缓冲区：根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。
    - 5. 物理文件系统：把逻辑记录所在的相对块号转换成实际的物理地址。
    - 6. 辅助分配模块：管理辅存空间，即负责分配辅存空闲空间和回收辅存空间。
    - 7. 设备管理程序模块：主要功能是分配设备、分配设备读写缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。
  - 4.2.2 目录实现
    
    目录实现的基本方法有线性表和哈希表。目录的实现就是为了查找。目录查询是通过在磁盘上反复搜索完成的，需要不断进行I/O操作，开销较大，所以为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，降低了磁盘操作次数，提高了系统速度。
    - 1. 线性列表
    - 2. 哈希表
  - 4.2.3 文件实现
    文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两方面的回答：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。
    - 1. 文件分配方式
      
      文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。
      - （1）连续分配
        文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。连续分配支持顺序访问和直接访问。
        
        图示
      - （2）链接分配
        
        ①隐式链接。
        每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任意地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，指针对用户是透明的；目录包括文件第一块的指针和最后一块的指针；
        
        创建新文件：目录中增加一个新条目。每个目录项都有一个指向文件首块的指针（也有一个指向文件最后一块的指针），该指针初始化为NULL表示空文件，大小字段为0。
        
        写文件：通过空闲空间管理系统找到空闲块，讲该块链接到文件尾部，以便写入。
        
        读文件：通过块到块的指针顺序读块。
        
        图示
        
        ②显示连接。
        文件分配表FAT整个磁盘中仅有一张。每个表项存放对应块的下一块链接指针，即下一个盘块号。文件的第一个盘块号记录在目录中，后续的盘块可通过查FAT查到。
        
        当某进程请求操作系统分配一个磁盘块时，操作系统只需要从FAT中找到为-2的表项，并将对应的磁盘块分配给进程即可。
        
        FAT表在启动时就会被读入内存，因此查找FAT的过程是在内存中进行，提高了检索速度。
        
        FAT表与全部盘块一一对应，用特殊数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的（也可以用-3，-4等）。
        
        图示
      - （3）索引分配
        链接分配解决了连续分配的外部碎片和文件大小管理的问题，但链接分配不能有效之间访问（FAT除外），索引分配解决了这个问题。
        
        图示
        
        每个文件都有其索引块，这是一个数组，数组里面是磁盘块地址。
        
        索引块的第 i 个条目指向文件的第 i 块。
        
        目录条目包括索引块的地址。
        
        要读第 i 块，通过索引块的第 i 个条目的指针来查找和读入所需的块。
        
        创建文件时，索引块的所有指针都设为空，首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目。
        
        访问文件需要两次访问外存——首先要读取索引块的内容，然后访问具体的磁盘块，降低了文件的存取速度。为了解决这问题，通常将文件的索引块读入内存的缓冲区，以加快文件的访问速度。
        
        索引块的大小要合适，每个文件必须有一个索引块，因此索引块尽可能小，但太小又无法支持大文件。可采用如下方法来解决：
        
        链接方案。将多个索引块链接起来。
        
        多层索引。多层索引使第一层索引块指向第二层的索引块，第二层的索引块再指向文件块。甚至可以第三层、第四层。
        
        混合索引。将多种索引分配方式相结合的分配方式。
    - 2. 文件存储空间管理
      - （1）文件存储器空间的划分与初始化。
        
        逻辑卷与物理盘的关系：文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成。
      - （2）文件存储器空间管理。
        文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配与回收等问题。
        
        ①空闲表法：将所有空闲区记录在一个表中。适合连续分配。
        
        如何分配磁块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
        
        如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况―—①回收区的前后都没有相邻空闲区;②回收区的前后都是空闲区;③回收区前面是空闲区;④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
        
        ②空闲链表法：将所有空闲块链成一个链表。适合离散分配。
        
        空闲盘块链：以盘块为单位组成一条空闲链。
        
        操作系统保存着链头、链尾指针。适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作
        
        如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
        
        如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
        
        空闲盘区链：以盘区为单位组成一条空闲链。
        
        操作系统保存着链头、链尾指针。离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。
        
        如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给-一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
        
        如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的-一个空闲盘区挂到链尾。
        
        ③位示图法：用一串二进制位反映磁盘空间中分配使用情况，每个物理块对应一位, 分配物理块为1，否则为0申请物理块时，可以在位示图中查找为0的位，返回对应物理块号；归还时，将对应位转置0。描述能力强，适合各种物理结构（对连续文件稍差），本身占空间少，可常驻内存，而字位号到块号的转换也不难。Linux使用。
        
        位示图：每个二进制对应一个盘块，本例中“0”表示盘块空闲，“1”表示盘块已分配。
        注意：所使用的位示图中行和列都是从1开始编号，若考试题目中从0开始编号，则需要调整。
        
        盘块号、行号、列号都从1开始
        
        盘块号、行号、列号都从0开始
        
        如何分配：若文件需要k个块，①顺序扫描位示图，找到k个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
        
        如何回收：①根据回收的盘块号计算出对应的行号、列号；②将相应二进制位设为“0”。
        
        ④成组链接法：链上每个节点记录1组空闲块。适合大型文件系统，分配、释放快，链本身短,占空间少。UNIX用。
        
        图示
- 4.3 磁盘组织与管理
  - 4.3.1 磁盘的结构
    - 磁盘示意图
      - 磁盘：是由表面涂有磁性物质的金属或塑料构成的圆形盘片。
        磁盘安装在一个磁盘驱动器中，由磁头臂、用于旋转磁盘的主轴和用于数据输入/输出的电子设备组成。磁盘按不同的方式可分为若干类型：
        
        固定头磁盘：磁头相对于盘片的径向方向固定的，每个磁道一个磁头。
        
        活动头磁盘：磁头可移动的，磁头臂可来回伸缩定位磁道。
        
        固定盘磁盘：磁盘永久固定在磁盘驱动器内的。
        
        可换盘磁盘：可移动和替换磁盘的。
      - 柱面：所有盘片上相对位置相同的磁道组成柱面。
        磁盘的柱面数与一个盘面上的磁道数是相等的。由于每个盘面都有自己的磁头，因此，盘面数等于总的磁头数。
      - 磁头：导体线圈组成，从磁盘存取数据。
        读/写期间，磁头固定，磁盘在下面高速旋转。
      - 磁道：磁盘盘面上的数据存储在一组同心圆中，称为磁道。
      - 扇区（盘块）：从圆心向外画直线，可以将磁道划分为若干个弧段，每个磁道上一个弧段被称之为一个扇区。
        扇区固定存储大小，通常为512B。扇区是磁盘可寻址的最小存储单位。磁盘地址用“柱面号 · 盘面号 · 扇区号（或块号）”表示。
      - 磁道间隙：相邻磁道通过一定间隙分隔开，以避免精度错误。扇区间隙亦是如此。
        扇区的密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度。
  - 4.3.2 磁盘调度算法
    - 1. 读写时间
      
      一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定。除了减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。可以对盘面扇区进行交替编号，对磁盘片组的不同盘面错位命名。寻道时间和延迟时间都可以通过一定的方法进行削减，但传输时间是磁盘本身性质所决定的，不能通过一定的措施减少。
      - （1）寻找时间Ts。
        在磁盘的存取时间计算中，寻道（寻找）时间与磁盘的调度算法有关。调度算法直接决定寻找时间，从而决定总的存取时间。
      - （2）延迟时间Tr。
        延迟时间和传输时间都与磁盘旋转速度相关，且线性相关。
      - （3）传输时间Tt。
      - （4）启动时间。
        一般忽略，控制器的启动时间。
    - 2. 调度算法
      - （1）先来先服务（First Come First Served，FCFS）算法。
        
        示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，采用FCFS算法时磁头运行轨迹如下：
        
        磁头共移动了100-55 + 58-55 + 58-39 + 39-18 + 90-18 + 160-90 + 160-150 + 150-38 + 184-38=45+3+19+21+72+70+10+112+146=498个磁道，平均寻找长度=498/9=55.3。（注：由于磁头的初始位置是磁道100，而FCFS算法是先来先服务，所以要将磁头从100移到第一个请求55的地方，需要移动磁道数为100-55=45个；而根据FCFS第二个请求按顺序是58，磁头从55到58要移动磁道数为58-55=3个，....，后面依次按照FCFS算法来计算即可。磁道顺序是100——55——58——39——18——90——160——150——38——184）。
      - （2）最短寻找时间优先（Shortest Seek Time First，SSTF）算法。
        
        示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，采用SSTF算法时磁头运行轨迹如下：
        
        磁头共移动了100-90+90-58+58-55+55-39+39-38+38-18+150-18+160-150+184-160=10+32+3+16+1+20+132+10+24=248个磁道，平均寻找长度=248/9=27.5。（注：由于磁头的初始位置是磁道100，而SSTF算法是最短寻找时间优先，比较请求队列中的几个顺序，发现90离100最近，即100-90=10是最短寻找时间，现在磁头到90位置了，继续比较，发现58到90的距离是最短的，即90-58=32是最短寻找时间，...，后面依次按照SSTF算法来计算即可。磁道顺序是100——90——58——55——39——38——18——150——160——184）。
      - （3）扫描（SCAN）算法（又称电梯调度算法）。
        采用SCAN算法不但要知道磁头的当前位置，还要知道磁头的移动方向。
        
        示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，假设磁头沿着磁道号增大的顺序移动，采用SCAN算法时磁头运行轨迹如下：
        
        磁头共移动了150-100+160-150+184-160+200-184+200-90+90-58+58-55+55-39+39-38+38-18=50+10+24+16+110+32+3+16+1+20=282个磁道，平均寻找长度=282/9=31.33。（注：由于磁头的初始位置是磁道100，而SCAN算法规定了磁头移动方向是沿着磁道号增大的顺序移动，故150离100最近而不是90，并且要移动到最大值200（即磁盘端点），才开始往回移动也就是从200移到90。磁道顺序是100——150——160——184——200——90——58——55——39——38——18）。
      - （4）循环扫描（Circular SCAN，C-SCAN）算法。
        
        示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，假设磁头沿着磁道号增大的顺序移动，采用C-SCAN算法时磁头运行轨迹如下：
        
        磁头共移动了150-100+160-150+184-160+200-184+200-0+18-0+38-18+39-38+55-39+58-55+90-58=50+10+24+16+200+18+20+1+16+3+32=390个磁道，平均寻找长度=390/9=43.33。（注：与SCAN算法不同的是，到达磁盘端点200时，下一个访问的磁道号是0（即起始磁盘端点）而不是距离最近的90号。磁道顺序是100——150——160——184——200——0——18——38——39——55——58——90）。
        
        改进：实际中不必到大磁盘端点（即200号和0号），只需要到达最远端的一个请求即可返回。
        
        LOOK调度（即这种形式的SCAN算法）
        
        C-LOOK调度（即这种形式的C-SCAN算法）
  - 4.3.3 磁盘的管理
    - 1. 磁盘初始化：对磁盘进行低级格式化和逻辑格式化。
      - 低级格式化（物理分区）：在磁盘能够存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作。
      - 逻辑格式化：对物理分区创建文件系统，操作系统将初始的文件系统数据结构存储道磁盘上。
    - 2. 引导块：存放自举程序。
      计算机启动时需要运行一个初始化程序（自举程序）。
      - 自举程序的作用：初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。
      - 自举程序通常保存在ROM中。
        只在ROM中保留很小的自举程序，将完整功能的自举程序保留在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘或系统磁盘（通常就是我们说的C盘）。
    - 3. 坏块：对于损坏扇区的处理。
      对于坏块的处理就算使系统不去使用它。坏块属于硬件故障，操作系统是不能修复的。
      - 对于简单磁盘，如电子集成驱动器（IDE），坏扇区可手工处理。
      - 对于复杂磁盘，如小型计算机系统接口（SCSI），其控制器维护一个磁盘坏块链表，在出厂前进行低级格式化时就已经初始化，并在使用过程中不断更新。
第5章输入/输出（I/O）管理
- 5.1 I/O管理概述
  - 5.1.1 I/O设备
    - I/O设备的分类（按使用特性分类）
    - I/O设备的分类（按传输速率分类）
    - I/O设备的分类（按信息交换的单位分类）
  - 5.1.2 I/O控制方式
    - 有4种：
      - 1. 程序直接控制方式
      - 2. 中断驱动方式
      - 3. DMA方式
        
        DMA方式的特点
        
        （1）基本单位是数据块。
        
        （2）所传送的数据，是从I/O设备直接送入内存，或者相反。
        
        （3）仅在传送一个或多个数据块的开始和结束时，才需要CPU的干预，整块数据的传送是在DMA控制器下完成的。
        
        DMA控制器的组成
        
        （1）命令/状态寄存器（CR）。
        
        （2）内存地址寄存器（MAR）。
        
        （3）数据寄存器（DR）。
        
        （4）数据计数器（DC）。
        
        DMA方式与中断驱动方式的主要区别
      - 4. 通道控制方式
        
        I/O通道与DMA方式的主要区别
        
        I/O通道与一般处理机的区别：通道指令的类型单一；没有自己的内存，通道所执行的通道程序放在主机的内存中（即通道与CPU共享内存）。
    - 总结比较
  - 5.1.3 I/O子系统的层次结构
    - I/O子系统的层次结构
      - （1）用户层I/O软件。实现与用户交互接口。
      - （2）设备独立性软件。用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护，以及设备分配与释放等，同时也为设备管理和数据传送提供必要的存储空间。
        
        设备独立性软件的主要功能可分为以下两个方面：
        
        ①执行所有设备的公有操作。包括：对设备的分配与回收；逻辑设备名映射为物理设备名；对设备进行保护，禁止用户直接访问设备；缓冲管理；差错控制；提供独立于设备的大小统一的逻辑块，屏蔽设备之间信息交换单位大小和传输速率的差异。
        
        ②向用户层(或文件层)提供统接口。无论何种设备，它们向用户所提供的接口应是相同的。例如，对各种设备的读/写操作，在应用程序中都统使用read/write命令等。
      - （3）设备驱动程序。与硬件直接相关，负责具体实现系统对设备发出的操作指令。
      - （4）中断处理程序。用于处理中断相关事项。
      - （5）硬件设备。包括一个机械部件（设备本身）和一个电子部件（设备控制器或适配器）。
        
        设备控制器的主要功能如下：
        
        （1）接收和识别CPU或通道发来的命令，如磁盘控制器能接收读、写、查找等命令。
        
        （2）实现数据交换，包括设备和控制器之间的数据传输；通过数据总线或通道，控制器和主存之间的数据传输。
        
        （3）发现和记录设备及自身的状态信息，供CPU处理使用。
        
        （4）设备地址识别。
        
        设备控制器送来的必须包含以下组成部分：
        
        ①设备控制器与CPU的接口。该接口有三类信号线：数据线、地址线和控制线。数据线通常与两类寄存器相连：数据寄存器（存放从设备送来的输入数据或从CPU送来的输出数据）和控制/状态寄存器（存放从CPU送来的控制信息或设备的状态信息）。
        
        ②设备控制器与设备的接口。设备控制器连接设备需要相应数量的接口，一个接口连接一台设备。每个接口中都存在数据、控制和状态三种类型的信号。
        
        ③I/O控制逻辑。用于实现对设备的控制。它通过一组控制线与CPU交互，对从CPU收到的I/O命令进行译码。CPU启动设备时，将启动命令发送给控制器，同时通过地址线把地址发送给控制器，由控制器的I/O逻辑对地址进行译码，并相应地对所选设备进行控制。
- 5.2 I/O核心子系统
  - 5.2.1 I/O子系统概述
    - I/O核心子系统提供的服务主要有：I/O调度、缓冲与高速缓存、设备分配与回收、假脱机、设备保护和差错控制。
  - 5.2.2 I/O调度概念
    - I/O调度就是确定一个好的顺序来执行这些I/O请求，减少I/O完成所需要的平均等待时间，提高计算机效率。
  - 5.2.3 高速缓存与缓冲区
    - 1. 磁盘高速缓存（Disk Cache）
      - 引入目的：提高磁盘的I/O速度，对高速缓存复制的访问要比原始数据访问更加高效。
      - 定义：磁盘高速缓存技术指利用内存中的存储空间来暂存从磁盘中读出的一系列盘块种的信息。
        因此，磁盘高速缓存逻辑上属于磁盘，物理上则是驻留在内存种的盘块。
      - 高速缓存在内存中分为两种形式：
        
        一种是在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定。
        
        另一种是把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O时共享。
    - 2. 缓冲区（Buffer）
      - 引入目的：
        
        （1）缓和CPU与I/O设备间速度不匹配的矛盾。
        
        （2）减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
        
        （3）解决基本数据单元大小不匹配的问题。
        
        （4）提高CPU和I/O设备的并行性。
      - 实现方法：
        
        （1）采用硬件缓冲器，成本太高，只在一些关键部位采用。
        
        （2）采用缓冲区（位于内存区域）
      - 缓冲区特点：
        
        缓冲区数据非空时，不能放入数据，只能传出数据；
        
        缓冲区为空时，可以放入数据，但必须把缓冲区充满后，才能传出数据。
      - 根据系统设备缓冲器的个数，缓冲技术分为以下几类：
        
        （1）单缓冲。
        
        思想：在设备和处理机之间设置一个缓冲区。设备和处理机交换数据时，先把被交换数据写入缓冲区，然后需要数据的设备或处理机从缓冲区取走数据。
        
        计算：单缓冲区处理每块数据的用时为MAX(C,T) + M。
        
        T指的是将从磁盘将一块数据写入缓冲区的时间。
        
        M是指将缓冲区的数据传送到用户区的时间。
        
        C指的是CPU对这一块数据的处理时间。
        
        图示
        
        （2）双缓冲。
        
        引入目的：根据单缓冲的特点，CPU在传送时间M内处于空闲状态，由此引入双缓冲。
        
        思想：I/O设备写入数据时先装填到缓冲区1，在缓冲区1满后才开始装填缓冲区2，与此同时处理机可以从缓冲区1中取出数据放入用户进程处理，当缓冲区1的数据处理完成时，缓冲区2已经填满，则处理机又从缓冲区2取出数据放入用户进程处理，而I/O设备又可以装填缓冲区1。双缓冲机制提高了处理机和输入设备的并行操作的程度。
        
        计算：双缓冲区处理一块数据的用时为MAX(C + M , T)。
        
        T指的是将从磁盘将一块数据写入缓冲区的时间。
        
        M是指将缓冲区的数据传送到用户区的时间。
        
        C指的是CPU对这一块数据的处理时间。
        
        图示
        
        （3）循环缓冲。
        
        思想：包含多个大小相等的缓冲区，每个缓冲区中有一个链接指针指向下一个缓冲区，最后一个缓冲区指向第一个缓冲区，多个缓冲区构成一个环形。
        
        （4）缓冲池。
        
        组成：由多个系统公用的缓冲区组成，缓冲区按使用情况可以形成三个队列：空缓冲队列、装满输入数据的缓冲队列（输入队列）和装满输出数据的缓冲队列（输出队列）。还应有4种缓冲区：用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区、用于收容输出数据的工作缓冲区和用于提取输出数据的工作缓冲区。
        
        思想：当输入进程需要输入数据时，便从空缓冲队列的队首摘下一个空缓冲区，把它作为收客输入工作缓冲区，然后把输入数据输入其中，装满后再将它挂到输入队列队尼。当计算进程需要输入数据时，便从输入队列取得. 个缓冲区作为提取输入工作缓冲区，计算进程从中提取数据，数据用完后再将它挂到空缓冲队列尾。当计算进程需要输出数据时，便从空缓冲队列的队首取得一个空缓冲区，作为收容输出工作缓冲区，当其中装满输出数据后，再将它挂到输出队列队尾。当要输出时，由输出进程从输出队列中取得一个装满输出数据的缓冲区，作为提取输出工作缓冲区，当数据提取完后，再将它挂到空缓冲队列的队尾。
    - 3. 高速缓存与缓冲区的对比
      - 图表
  - 5.2.4 设备分配与回收
    - 1. 设备分配概述
      - 设备分配：是指根据用户的I/O请求分配所需的设备。
      - 分类（从设备的特性来分）：
        
        （1）独占式设备（独占设备）：指申请设备时，若设备空闲则将其独占，不再允许其他进程申请使用，一直等到该设备被释放才允许其他进程申请使用。如打印机。
        
        （2）分时式共享使用设备（共享设备）：当设备没有独占使用的要求时，可以通过分时共享使用提高利用率。如对磁盘的I/O操作。
        
        （3）以SPOOLing方式使用外部设备（虚拟设备）：SPOOLing技术即假脱机技术，实质上就是对I/O操作进行批处理。
        是一种以空间换时间的技术，而请求分页系统种的页面调度算法是一种以时间换空间的技术。
    - 2. 设备分配的数据结构
      - 设备分配依据的主要数据结构：设备控制表（DCT）、控制器控制表（COCT）、通道控制表（CHCT）和系统设备表（SDT）。
        
        设备控制表（DCT）：一个设备控制表就表示一个设备，控制表的表项就是该设备的各个属性。每个设备由机械部件和电子部件（控制器）组成，故每个DCT都需要一个表项来表示控制器（电子部件），即需要一个指向控制器控制表（COCT）的指针，因此DCT与COCT具有一一对应的关系。
        
        控制器控制表（COCT）：设备控制器控制设备与内存交换数据，而设备控制器又需要请求通道为它服务，故每个COCT必定有一个表项存放指向相应通道控制表（CHCT）的指针。
        
        通道控制表（CHCT）：一个通道可以为多个设备控制器服务，因此CHCT种必定又一个指针指向一个表，这个表上的信息就是CHCT提供服务的那几个设备控制器，因此CHCT与COCT是一对多的关系。
        
        系统设备表（SDT）：整个系统只有一张SDT，它记录已连接到系统中的所有物理设备的情况，每个物理设备占一个表目。
    - 3. 设备分配的策略
      设备分配主要考虑的因素有：I/O设备的固有属性、I/O设备的分配算法、I/O设备分配的安全性以及I/O设备的独立性。对于独占设备，既可以采用动态分配方式又可以采用静态分配方式，往往采用静态分配方式。对于共享设备，一般采用动态分配方式，通常采用先请求先分配和优先级高者优先的分配算法。
      - （1）设备分配原则。
        
        分配的总原则：既要充分发挥设备的使用效率，又要避免造成进程死锁，还要将用户程序与具体设备隔离开。
      - （2）设备分配方式
        
        设备分配方式有静态分配和动态分配两种。
      - （3）设备分配算法
        
        常用的动态分配算法有：先请求先分配、优先级高者优先等。
    - 4. 设备分配的安全性
      - 设备分配的安全性：是指分配中应防止发生进程死锁。
    - 5. 逻辑设备名到物理设备名的映射
      - 设备独立性：是指应用程序独立于具体使用的物理设备。
        即用户在编程时使用的设备与实际设备无关，在用户程序中只需指明I/O使用的设备类型即可。
      - 设备独立性的优点
        
        （1）方便用户编程。
        
        （2）使程序运行不受具体机器环境的限制。
        
        （3）便于程序的移植。
      - 如何实现设备独立性：在应用程序中使用逻辑设备名来请求使用某类设备，在系统中设置一张逻辑设备表（LUT），用于将逻辑设备名映射为物理设备名。
      - LUT表项：包括逻辑设备名、物理设备名和设备驱动程序入口地址。
      - 具体使用：当进程用逻辑设备名来请求分配设备时，系统为它分配相应的物理设备，并在LUT中建立一个表项，以后进程再利用逻辑设备名请求I/O操作时，系统通过查找LUT来寻找相应的物理设备和驱动程序。
      - 系统中采用两种方式建立逻辑设备表（LUT）
        
        （1）整个系统只设置一张LUT。所有进程的设备分配情况都记录在这张表中，因此不允许有相同的逻辑设备名，主要适用于单用户系统。
        
        （2）为每个用户设置一张LUT。
  - 5.2.5 SPOOLing技术（假脱机技术）
    - 引入目的：为了缓和CPU的高速性与I/O设备低速性直接的矛盾。
    - SPOOLing技术：该技术利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上（或者相反），是操作系统中采用的一项将独占设备改造成共享设备的技术。
    - SPOOLing系统的组成
      - 1. 输入井和输出井
        
        输入井：指在磁盘上开辟出的一个存储区域，模拟脱机输入时的磁盘，用于收容I/O设备输入的数据。
        
        输出井：指在磁盘上开辟出的一个存储区域，模拟脱机输出时的磁盘，用于收容用户程序输出的数据。
      - 2. 输入缓冲区和输出缓冲区
        
        输入缓冲区：是在内存中开辟的一个缓冲区，用于暂存由输入设备送来的数据，以后再传送到输入井。
        
        输出缓冲区：是在内存中开辟的一个缓冲区，用于暂存由输出井送来的数据，以后再传送到输出设备。
      - 3. 输入进程和输出进程
        
        输入进程：模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井。当CPU需要输入数据时，直接将数据从输入井读入内存。
        
        输出进程：模拟脱机输出时的外围控制机，将用户要求输出的数据从内存传送到输出井，待输出设备空闲时，再将输出井中的数据经过输出缓冲区传到输出设备。
    - SPOOLing系统的主要特点：
      - 提高了I/O的速度；
      - 将独占设备改造为共享设备；
      - 实现了虚拟设备功能。
    - SPOOLing技术是如何以时间换空间的？
      - 牺牲空间：在内存划出一片作为输入/输出缓冲区，在磁盘划出一块作为输入/输出井。
      - 节省时间：磁盘是一种高速设备，与内存交换数据的速度优于打印机等中低速I/O设备，如果不采用SPOOLing技术，那么CPU要向打印机大于数据，打印机的速度比较慢，故CPU必须迁就打印机，等打印机把数据打印完才能做其他工作，浪费了CPU时间。但在SPOOLing技术下，CPU把打印机要输出的数据先输出到磁盘的输出井中（这个过程由输出进程控制），然后做其他事情，若打印机被占用，SPOOLing系统会把这个打印请求挂到等待队列上，待打印机空闲时把数据打印出来，向磁盘输出数据的速度比向打印机输出数据的速度快，故节省了时间。