研distance——操作系统部分

概论

操作系统：控制管理计算机的硬件，协调控制资源分配，并为应用程序和用户提供接口以供使用

基本特征

操作系统的基本特征包括并发，共享，虚拟和异步

1. 并发
   并发是指两个或多个事件在同一时间间隔内发生。操作系统的并发性是指计算机系统中同时存在多个运行的程序，因此它具有处理和调度多个程序同时执行的能力。这是通过类似时间片轮转的机制实现的。
   并行性是指系统具有同时进行运算或操作的特性，在同一时刻能完成两种或两种以上的动作，需要相关硬件的支持,如多流水线或多处理机硬件环境

2. 共享
   共享：系统内的某些资源可以供并发的不同进程使用，分为以下几种方式
   

   1. 互斥共享
      规定在一段时间内只允许一个进程访问该资源，系统分配该资源前，必须确保没有其他进程正在使用它，分配后，在进程访问并释放该资源后，其他进程对资源的申请才会被操作系统允许。
      这种一段时间内只能被一个进程占有的资源被称为临界资源
      大部分硬件，某些软件的栈，变量等都属于临界资源
      
   2. 同时访问
      某些系统资源可以在同一时间段内被多个进程同时访问，例如文件系统，这种同时访问可能是交替进行。
      互斥共享要求一种资源在一段时间内(哪怕是一段很小的时间)只能满足一个请求，同时访问通常要求一个请求可以分时间片间隔地完成，效果和连续完成相同

并发和共享是操作系统两个最基本的特征，两者之间互为存在的条件：

• 资源共享是以程序的并发为条件的：若系统不允许程序并发执行，则自然不存在资源共享问题
  
• 若系统不能对资源共享实施有效的管理，则必将影响到程序的并发执行，其至根本无法并发执行。

3. 虚拟
   虚拟是指把一个物理上的实体变为若干逻辑上的对应物。
   虚拟处理器技术是通过多道程序设计技术，采用让多道程序并发执行的方法，来分时使用一个处理器的。此时，虽然只有一个处理器，但它能同时为多个用户服务
   把一个物理cpu虚拟成多个虚拟cpu,称为虚拟处理器
   虚拟技术可以在时间或者空间上进行相应的现实虚拟转换

4. 异步
   虽然进程可以并发进行，但推进速度，时间等是不确定的，操作系统必须确保，相同环境下相同操作的进程得到相同的结果，不论时间多久

功能

1. 管理系统资源
   1. 处理机(进程)的管理，包括创建，调度，死锁检测和恢复等
      
   2. 存储器管理，即内存的分配和管理
      
   3. 文件管理，即操作系统的文件系统空间，目录，格式等
      
   4. 设备管理，处理用户的I/O请求
      
2. 提供用户接口操作硬件和程序
   
3. 命令接口
   1. 联机命令接口(交互式命令接口，适用于实时或分时系统)：用户通过终端实时输入命令与操作系统交换，输入一条，操作系统解释并执行一条，然后才可以输入下一条(shell)
      
   2. 脱机命令接口(批处理命令接口,适用于批处理系统)：用作业控制命令写成一本作业说明书，操作系统读取说明书，逐条解释执行(脚本)
      
4. 程序接口：有一系列系统调用组成，用户在程序中使用这些系统调用命令来让操作系统提供相应服务，例如GUI界面(严格的说gui界面只是使用了操作系统提供的图形相关的系统调用)
   
5. 实现了对计算机资源的扩充

历史

1. 手工操作阶段
   缺点：1，cpu利用不充分。2，计算机资源利用率低下
   
2. 批处理阶段
   1. 单道批处理系统：操作系统一次只执行一个程序，依次处理，特征：
      1. 自动性，磁带上的作业可以自动依次进行
         
      2. 顺序性，作业有明确顺序依次进入内存
         
      3. 单道性，内存中只有一个程序运行，任务完成或异常后才调入下一个
         问题：任务间隔等待下一个调入时，I/O效率低下
         
   2. 多道批处理程序，内存中可以有多个程序共享系统资源，交替运行，避免I/O期间的算力浪费，特点是：
      1. 多道，内存存放多道程序
         
      2. 宏观上并行，内存中的程序都处于运行状态
         
      3. 微观上串行，程序交替使用cpu
         问题：处理器资源，内存资源和I/O的分配，以及如何组织处理大量的程序和数据
         在批处理系统中采用多道程序设计技术就形成了多道批处理操作系统。该系统把用户提交的作业成批地送入计算机内存，然后由作业调度程序自动地选择作业运行。

• 优点：资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用：系统吞吐量大，CPU和其他资源保持“忙碌”状态。
  
• 缺点：用户响应的时间较长：不提供人机交互能力，用户既不能了解自已的程序的运行情况，又不能控制计算机。

3. 分时操作系统
   将处理器的运算分成很短的时间片，按时间片轮流把处理器分配给各联机作业使用。时间片内不能完成的作业等到下个周期继续进行，时间片很短，因此对用户来说几乎实时。
   分时操作系统是指多个用户通过终端同时共享一台主机，这些终端连接在主机上，用户可以同时与主机进行交互操作而互不干扰，同时有较快的交互速度
   特性：

   1. 同时性，允许多个用户同时使用一台计算机(多终端)
      
   2. 交互性
      
   3. 独立性，各个用户相对独立，不会互相影响
      
   4. 及时性，对用户请求用较快的速度回应

4. 实时操作系统
   一些特殊场合(比如飞行器系统)，对操作的时限有硬性要求(或者软性要求)，这样的操作系统叫做实时操作系统
   其中绝对无法违反时限的是硬实时系统，偶尔可以违反的是软实时系统
   特点：

• 及时性
  
• 可靠性

5. 其他
   网络操作系统把计算机网络中的各台计算机有机地结合起来，提供一种统一、经济而有效地使用各台计算机的方法，实现各台计算机之间数据的互相传送。网络操作系统最主要的特点是网络中各种资源的共享及各台计算机之间的通信。
   分布式计算机系统是由多台计算机组成并满足下列条件的系统：

   • 系统中任意两台计算机通过通信方式交换信息：
     
   • 系统中的每台计算机都具有同等的地位，即没有主机也没有从机：每台计算机上的资源为所有用户共享：
     
   • 系统中的任意台计算机都可以构成一个子系统，并且可以重构；
     
   • 任何工作都可以分布在几台计算机上，由它们并行工作、协同完成。
     用于管理分布式计算机系统的操作系统称为分布式计算机系统。该系统的主要特点是：分布性和并行性。分布式操作系统与网络操作系统的本质不同是，分布式操作系统中的若干计算机相互协同完成同一任务。

6. 个人计算机操作系统
   个人计算机操作系统是目前使用最广泛的操作系统，常见的有Windows、Linux和Macintosh等。

运行环境

cpu一般执行两种程序，一种是操作系统内核程序，另一种是用户程序，因此对cpu指令需要做区分

• 特权指令，是指不允许用户直接使用的指令，如I/O指令、置中断指令，存取用于内存保护的寄存器、送程序状态字到程序状态字寄存器等的指令。
  
• 非特权指令，是指允许用户直接使用的指令，它不能直接访问系统中的软硬件资源，仅限于访问用户的地址空间，这也是为了防止用户程序对系统造成破坏。
  在具体实现上，将CPU的运行模式划分为用户态(目态)和核心态 (又称管态，内核态)

内核机制

1. 时钟管理，提供计时功能，是时间片轮转，实时系统的截止时间等功能的基础
   
2. 中断机制，操作系统的大部分功能都依赖中断，可以说现代操作系统是中断驱动的，中断机制只有一小部分属于内核，负责保护和恢复现场等
   
3. 原语，操作系统的底层小程序，有以下特点
   1. 最底层，最接近硬件
      
   2. 操作有原子性，不可分割
      
   3. 运行时间短，调用频繁
      
4. 系统控制的数据结构和处理,常见操作有
   1. 进程管理
      
   2. 存储器管理
      
   3. 设备管理

中断和异常

由于用户态的某些操作需要核心态的一些功能，需要中断和异常机制，来让cpu从用户态进入核心态(这通过硬件实现，比如一个特殊寄存器)
中断(Interruption)也称外中断，是指来自CPU执行指令外部的事件，通常用于信息输入/输出，如设备发出的I/O结束中断，表示设备输入/输出处理已经完成。时钟中断，表示一个固定的时间片已到，让处理机处理计时、启动定时运行的任务等
异常(Exception)也称内中断，是指来自CPU执行指令内部的事件，如程序的非法操作码、地址越界、运算溢出、虚存系统的缺页及专门的陷入指令等引起的事件。异常不能被屏蔽，一出现，就应立即处理。

二者的分类如图，其中：
故障(Fault)通常是由指令执行引起的异常，如非法操作码，缺页故障、除数为0、运算溢出等。
自陷(Trap)是一种事先安排的“异常”事件，用于在用户态下调用操作系统内核程序。
终止(Abort)是指出现了使得CPU无法继续执行的硬件故障，如控制器出错、存储器校验错等。

故障异常和自陷异常属于软件中断(程序性异常)，终止异常和外部中断属于硬件中断。

中断处理流程：操作系统发现中断请求或者异常后，打断当前程序，调转到中断或者异常的处理程序，如果程序能解决问题，就再次回到现场继续执行，如果是致命错误，则终止程序

系统调用

一般涉及对系统资源的请求，都需要系统调用，系统调用可以视为一种特殊的公共子程序
常见类型：

• 设备管理。完成设备的请求或释放，以及设备启动等功能。
  
• 文件管理。完成文件的读、写、创建及删除等功能。
  
• 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
  
• 进程通信。完成进程之间的消息传递或信号传递等功能。
  
• 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及始址等功能

用户程序可以执行陷入指令(又称访管指令或trap指令)来发起系统调用，此时相当于cpu使用权被交给内核，来让cpu进入核心态执行特权指令，最后结果和cpu返还给程序
当需要管理程序服务时，系统则通过硬件中断机制进入核心态，运行管理程序：也可能是程序运行出现异常情况，被动地需要管理程序的服务，这时就通过异常处理来进入核心态。
管理程序运行结束时，用户程序需要继续运行，此时通过相应的保存的程序现场退出中断处理程序或异常处理程序，返回断点处继续执行

执行系统调用的过程如下：正在运行的进程先传递系统调用参数，然后由陷入(trap)指令负责将用户态转换为内核态，并将返回地址压入堆栈以备后用，接下来CPU执行相应的内核态服务程序，最后返回用户态。

• 由用户态进入核心态，不仅状态需要切换，而且所用的堆栈也可能需要由用户堆栈切换为系统堆栈，但这个系统堆栈也是属于该进程的,此外，这个转变是硬件完成的，核心态到用户态则是操作系统完成
  
• 访管指令在用户态使用，因此不是特权指令
  
• 输入输出这种涉及到中断机制的指令，必须在核心态执行
  
• 命令解释这种与用户交互的程序在用户态执行，而进程调度则需要核心态(单个用户不应能影响进程这样的全局状态，否则就可以只让自己的进程优先执行)
  
• 外部中断时，通用寄存器由操作系统保存，PC(程序计数器)则由中断指令自动保存
  
• 时钟中断后，服务程序应当更新内核中时钟变量的值,当前进程占用CPU的时间,当前进程在时间片内的剩余执行时间等全部时钟相关的数据
  
• 操作系统通过提供系统调用避免用户程序直接访问外设
  
• 当CPU检测到中断信号后，由硬件自动保存被中断程序的断点(即程序计数器PC)，之后，硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址(各中断向量保存PSW、保存中断屏蔽字、保存各通用寄存器的值，并提供与中断信号对应的中断服务，中断服务程序属于操作系统内核)
  
• 能在内核态下执行。常见的特权指令有：
  • 有关对IO设备操作的指令
    
  • 有关访问程序状态的指令
    
  • 存取特殊寄存器的指令
    
• 通道技术和中断技术结合起来就可实现CPU与I/O设备并行工作，即CPU启动通道传输数据后便进行其他程序的计算工作，而通道则进行输入输出操作；通道工作结束后，通过中断让cpu进行处理，处理完再各自进行对应的工作

结构

1. 分层法
   最底层为硬件，最高层为用户接口，每个高层只能调用它向下单层的功能和服务
   优点：

   1. 便于调试和验证，由于每层都相对独立，可以隔绝问题，在单层定位问题
      
   2. 易于扩充维护，只要确保层间接口不便，就可以随意修改单层内的模块

问题：1，难于定义各层。2，由于有时需要跨多层调用，额外开销较大，效率较低

2. 模块化
   将操作系统定义成各种有自己接口的模块，各模块通过接口进行组合和通信
   
   这样的结构需要保证模块之间的独立性，即：

   • 内聚性，模块内部各部分间联系的紧密程度。内聚性越高，模块独立性越好。
     
   • 耦合度，模块间相互联系和相互影响的程度。耦合度越低，模块独立性越好。
     模块化的优点：①提高了操作系统设计的正确性、可理解性和可维护性：②增强了操作系统的可适应性：③加速了操作系统的开发过程。
     模块化的缺点：①模块间的接口规定很难满足对接口的实际需求。②各模块设计者齐头并进，每个决定无法建立在上一个已验证的正确决定的基础上，因此无法找到一个可靠的决定顺序。

3. 宏内核
   宏内核，指将系统的主要功能模块作为整体运行在核心态，从而为用户程序提供高性能的系统服务。各管理模块之间共享信息，性能较高；但同时有更高耦合性，一个模块故障可能波及整个系统
   主流操作系统都使用了宏内核，但事实上也在逐渐引进微内核技术，成为一种混合结构

4. 微内核
   微内核构架，是指将内核中最基本的功能保留在内核，而将那些不需要在核心态执行的功能移到用户态执行，从而降低内核的设计复杂性。那些移出内核的操作系统代码根据分层的原则划分成若干服务程序，它们的执行相互独立，交互则都借助于微内核进行通信。
   一般可以分为两个部分：

• 微内核,实现操作系统最基本核心功能的小型内核
  • 与硬件紧密相关的功能
    
  • 基本功能
    
  • 客户和服务器的通信
    
• 多个服务器

为了实现高可靠性，只有微内核运行在内核态，其余模块都运行在用户态，一个模块的错误不会影响整个系统
微内核的功能：

• 进程(线程)管理：进程的通信，切换，调度，多处理器的同步等都应该放入微内核，但进程分类，优先级确定等不涉及机制的功能可以放入进程管理服务器
  
• 低级存储器管理：比如页表机制和地址变换机制，而虚拟存储器的管理，页面置换算法等则由存储器管理服务器管理
  
• 中断和陷入处理，捕获相关事件，进行中断响应处理，然后发送给相关服务器来处理

优点：

• 拓展性和灵活性
  
• 可靠性和安全性
  
• 可移植性(和硬件有关的都在微内核中，其他服务器和硬件无关)
  
• 分布式计算，通信采用消息传递机制，很好的支持分布式系统和网络系统

微内核结构的主要问题是性能问题，因为需要频繁地在核心态和用户态之间进行切换，操作系统的执行开销偏大。

5. 外核
   不同于虚拟机克隆真实机器，另一种策略是对机器进行分区，给每个用户整个资源的一个子集。在底层中，一种称为外核(exokernel)的程序在内核态中运行。它的任务是为虚拟机分配资源，并检查使用这些资源的企图，以确保没有机器会使用他人的资源。每个用户层的虚拟机有自己的操作系统，但资源是受限制的
   外核机制的优点是减少了映射层。在其他的设计中，每个虚拟机都认为它有自己的磁盘，这样虚拟机监控程序就必须维护一张表格以重映像磁盘地址，有外核就不需要维护这个表格了，并且实现了各个虚拟机之间的安全划分，没有冲突

引导

操作系统引导过程：

1. 激活CPU。激活的CPU读取ROM中的boot程序，将指令寄存器的内容置为BIOS(基本输入/输出系统)的第一条指令，即开始执行BIOS的指令。
   
2. 硬件自检。启动BIOS程序后，先进行硬件自检，检查硬件是否出现故障。如有故障，主板会发出不同含义的蜂鸣，启动中止：如果没有故障，屏幕会显示CPU、内存、硬盘等信息。
   
3. 加载带有操作系统的硬盘。硬件自检后，BIOS开始读取BootSequence(通过CMOS里保存的启动顺序，或者通过与用户交互的方式)，把控制权交给启动顺序排在第一位的存储设备，然后CPU将该存储设备引导扇区的内容加载到内存中。
   
4. 加载主引导记录MBR。硬盘以特定的标识符区分引导硬盘和非引导硬盘。如果发现一个存储设备不是可引导盘，就检查下一个存储设备。如无其他启动设备，就会死机。主引导记录MBR的作用是告诉CPU去硬盘的哪个主分区去找操作系统。
   
5. 扫描硬盘分区表，并加载硬盘活动分区。MBR包含硬盘分区表，硬盘分区表以特定的标识符区分活动分区和非活动分区。主引导记录扫描硬盘分区表，进而识别含有操作系统的硬盘分区(活动分区)。找到硬盘活动分区后，开始加载硬盘活动分区，将控制权交给活动分区。
   
6. 加载分区引导记录PBR。读取活动分区的第一个扇区，这个扇区称为分区引导记录(PBR)，其作用是寻找并激活分区根目录下用于引导操作系统的程序(启动管理器)
   
7. 加载启动管理器。分区引导记录搜索活动分区中的启动管理器，加载启动管理器
   
8. 加载操作系统

简单来说，是指计算机利用CPU运行boot程序(例如焊在主板上的rom中)，先进行自检，然后识别硬盘，找到有系统的硬盘(多系统则需要指定顺序)，由于硬盘分区且操作系统以区为单位存放，因此需要通过MBR中的分区信息寻找活动分区，最后通过分区内特定的引导程序启动操作系统

虚拟机

虚拟机是一台逻辑计算机，是指利用特殊的虚拟化技术，通过隐藏特定计算平台的实际物理特性，为用户提供抽象的、统一的、模拟的计算环境。有两类虚拟化方法。

1. 虚拟机管理程序作为唯一运行在最高特权的程序，在裸机上运行并且具备多道程序功能。管理程序向上层提供若干台虚拟机、这些虚拟机是裸机硬件的精确复制品。由于每台虚拟机都与裸机相同，所以在不同的虚拟机上可以运行任何不同的操作系统。

虚拟机作为用户态的一个进程运行，不允许执行敏感指令。然而，虚拟机上的操作系统认为自已运行在内核态(实际上不是)，称为虚拟内核态。虚拟机中的用户进程认为自已运行在用户态(实际上确实是)
当虚拟机操作系统执行了一条CPU处于内核态才允许执行的指令时，会陷入虚拟机管理程序。在支持虚拟化的CPU上，虚拟机管理程序检查这条指令是由虚拟机中的操作系统执行的还是由用户程序执行的。如果是前者，虚拟机管理程序将安排这条指令功能的正确执行。否则，虚拟机管理程序将模拟真实硬件面对用户态执行敏感指令时的行为。

2. 类似一个依赖宿主机的普通进程，操作系统安装到虚拟磁盘上(其实只是宿主操作系统中的一个文件)。客户操作系统安装完成后，就能启动并运行。 此时，虚拟机管理程序伪装成一台计算机(比如vmware)

有的教材将第一类虚拟化技术称为裸金属架构，将第二类虚拟化技术称为寄居架构

• 通常可以从四个方面来描述微内核OS：①内核足够小；②基于客户/服务器模式；③应用“机制与策略分离”原理；④采用面向对象技术。
  
• 常驻内存的只是操作系统内核，其他部分仅在需要时才调入。
  
• 操作系统的引导程序位于磁盘活动分区的引导扇区中。引导程序分为两种：一种是位于ROM中的自举程序(BIOS的组成部分)，用于启动具体的设备；另一种是位于装有操作系统硬盘的活动分区的引导扇区中的引导程序(称为启动管理器)，用于引导操作系统
  
• CPU激活后，会从最顶端的地址FFFF0H获得第一条指令来执行，这个地址仅仅只有16字节，放不下一段程序，所以是一条JMP指令，以跳到更低地址去执行BIOS程序。BIOS程序在内存最开始的空间构建中断向量表和相应服务程序,在后续POST过程中要用到中断调用等功能。然后进行通电自检POST (Power-on Self Test)以检测硬件是否有故障。完成POST后，BIOS需要在硬盘、光驱或软驱等存储设备搜寻操作系统内核的位置以启动操作系统
  
• BIOS将控制权交给排在首位的启动设备后，CPU将该设备主引导扇区的内容(主引导记录MBR)加载到内存中，然后由MBR检查分区表，查找活动分区，并将该分区的引导扇区的内容(分区引导记录PBR)加载到内存加以执行
  
• 机制是指实现某一功能的具体执行机构。策略则是在机制的基础上借助于某些参数和算法来实现该功能的优化，或达到不同的功能目标。在传统的OS中，将机制放在OS内核的较低层中，把策略放在内核的较高层中。而在微内核OS中，通常将机制放在OS的微内核中。正因如此，才可以将内核做得很小
  
• 处于用户态的用户程序使用访管指令时，系统根据访管指令的操作数执行访管中断处理程序，访管中断处理程序将按系统调用的操作数和参数转到相应的例行子程序。完成服务功能后，退出中断，返回到用户程序断点继续执行。

---

进程和线程

进程

为了更好的控制并发的多个程序，引入了进程(process)的概念
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位(但不是最小的)。进程是一个动态的、过程性的概念,而程序则是静态的二进制码
对每个进程必须为之配置一个专门的数据结构，称为进程控制块(Process Control Block, PCB),PCB是对进程的唯一标志

特征：

• 动态性
  
• 并发性，多个进程实体同时存在于内存，在一段时间内并发执行
  
• 独立性，进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位
  
• 异步性，进程推进的速度不可预知，因此需要相应的同步策略

状态(前三个是基本状态)：

1. 运行态，在处理机上运行
   
2. 就绪态，进程得到了处理机外的所有资源，就绪的进程一般用就绪队列管理
   
3. 阻塞态，进程正在等待某个事件或者资源，一般会用多个阻塞队列管理这样的进程
   
4. 创建态，进程正在创建，还没进入就绪态，比如没有足够分配的资源时创建进程
   
5. 终止态，结束进程时先设置成终止态，随后进行资源释放等工作

组成

1. PCB
   PCB是进程实体的一部分，是进程存在的唯一标志，也被用于存储进程状态，断点的恢复和保存
   

   当操作系统欲调度某进程运行时，要从该进程的PCB中查出其现行状态及优先级；在调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据；进程在运行过程中，当需要和与之合作的进程实现同步、通信或访问文件时，也需要访问PCB；当进程由于某种原因而暂停运行时，又需将其断点的处理机环境保存在PCB中。在进程的整个生命期中，系统通过PCB对进程进行控制

   
   
   PCB的组成如图，其中寄存器值一般用于切换进程时保护现场，以备之后从断点执行，这些信息也被称上下文。
   对进程的管理一般通过对PCB进行组织来进行，一般可以分为链表和索引两种组织方式，不同进程状态对应不同索引或队列(链式队列)

2. 程序段
   程序段就是能被进程调度程序调度到CPU执行的程序代码段。注意，程序可被多个进程共享，即多个进程可以运行同一个程序。
   进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。在操作系统中，一般把进程控制用的程序段称为原语

3. 数据段
   一个进程的数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行时产生的中间或最终结果。

控制

1. 创建
   子进程可以继承父进程所拥有的资源。当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。此外，在撤销父进程时，通常也会同时撤销其所有的子进程。
   操作系统创建一个新进程的过程如下(创建原语)：

   1. 为新进程分配一个唯一的进程标识号，并申请一个空白PCB (PCB是有限的)。若PCB申请失败，则创建失败。
      
   2. 为进程分配其运行所需的资源，如内存、文件、I/O设备和CPU时间等(在PCB中体现)。这些资源或从操作系统获得，或仅从其父进程获得。如果资源不足(如内存)，则并不是创建失败，而是处于创建态，等待内存资源。
      
   3. 初始化PCB,主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。
      
   4. 若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行

2. 终止
   引起进程终止的事件主要有：

   • 正常结束，进程的任务己完成并准备退出运行。
     
   • 异常结束，进程在运行时，发生了某种异常事件，如存储区越界、I/O故障等。
     
   • 外界干预，指进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止

3. 阻塞和唤醒
   正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败等，进程便通过调用阻塞原语(Block),使自己由运行态变为阻塞态。

阻塞原语的执行过程如下：

1. 找到将要被阻塞进程的标识号对应的PCB
   
2. 若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。
   
3. 把该PCB插入相应事件的等待队列，将处理机资源调度给其他就绪进程

当被阻塞进程所期待的事件出现时，如它所期待的I/O操作已完成或其所期待的数据已到达，由有关进程调用唤醒原语(Wakeup),将等待该事件的进程唤醒。

唤醒原语的执行过程如下：

1. 在该事件的等待队列中找到相应进程的PCB
   
2. 将其从等待队列中移出，并置其状态为就绪态。
   
3. 把该PCB插入就绪队列，等待调度程序调度。

就像c++的new和delete一样，阻塞和唤醒必须成对进行，否则就会出现"睡美人"

通信

进程通信是指进程之间的信息交换

1. 共享存储
   在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换,此时需要PV等机制来进行同步。
   共享存储又分为两种：

   • 低级方式的共享是基于数据结构的共享
     
   • 高级方式的共享则是基于存储区的共享
     

     进程运行期间一般不能访问其他进程的空间，想让两个进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的

2. 消息传递
   在消息传递系统中，进程间的数据交换以格式化的消息(Message)为单位。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。 这种方式公开透明，简化了程序的设计，因此应用比较广泛
   在微内核操作系统中，微内核与服务器之间的通信就采用了消息传递机制。由于该机制能很好地支持多处理机系统、分布式系统和计算机网络，因此也成为这些领域最主要的通信工具。
   分为：

   1. 直接通信方式。发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息
      
   2. 间接通信方式。发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱。该通信方式广泛应用于计算机网络中。

3. 管道通信
   
   管道通信允许两个进程按生产者-消费者方式进行通信,生产者向管道的一端写，消费者从管道的另一端读。
   数据在管道中是先进先出的。只要管道非空，进程就能从管道中读出数据，若数据被读空，则读进程阻塞，直到写进程往管道中写入新的数据，再将读进程唤醒。
   只要管道不满，写进程就能往管道中写入数据，若管道写满，则写进程阻塞，直到读进程读出数据，再将写进程唤醒。
   为了协调双方的通信，管道机制必须提供三方面的协调能力：互斥、同步和确定对方的存在。
   

   实例：
   在linux中，管道是一种文件，准确的说是一个固定大小(4KB)的缓冲区，写满时自动阻塞，直到部分数据被读取，被读空时，则对读操作阻塞，直到有新的内容写入

   
   管道只能由创建进程所访问，当父进程创建一个管道后，由于管道是一种特殊文件，子进程会继承父进程的打开文件，因此子进程也继承父进程的管道，并使用它来与父进程进行通信

线程和多线程模型

概念

线程最直接的理解就是“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。
线程是进程中的一个实体，是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。
一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于线程之间的相互制约，致使线程在运行中呈现出间断性。

线程也有就绪、阻塞和运行三种基本状态
进程是除CPU外的系统资源的分配单元，而线程则作为处理机的分配单元。

和进程的比较：

1. 调度，引入线程后，线程才是独立调度的基本单位，而线程切换的代价远低于进程,同一进程的线程可以随意切换，而避免较大的上下文切换开销
   
2. 并发，引入线程后，一个进程的线程，以及不同进程的线程都可以并发执行，提高了系统的资源利用率和吞吐量
   
3. 拥有资源，进程是拥有系统资源的最小单位，线程除了极少必要资源不占有资源，同一进程的线程有相同的地址空间，可以共享该进程资源
   
4. 独立性，进程之间相互独立，除了共享资源无法互相访问，线程则可以共享资源和地址空间
   
5. 系统开销，由于避免创建PCB，分配资源，切换上下文，通信等开销,线程开销更小
   
6. 支持多处理器系统，一个进程的不同线程可以用多个处理器同时运算

属性和状态

1. 每个线程都有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态。
   
2. 不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。
   
3. 同一进程中的各个线程共享该进程所拥有的资源。
   
4. 线程是处理机的独立调度单位,可以并发执行。在单CPU的计算机系统中，各线程交替地占用CPU；在多CPU的计算机系统中，各线程可同时占用不同的CPU,若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。
   
5. 一个线程被创建后，便开始了它的生命周期，直至终止。线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。

• 执行状态：线程己获得处理机而正在运行。
  
• 就绪状态：线程已具备各种执行条件，只需再获得CPU便可立即执行。
  
• 阻塞状态：线程在执行中因某事件受阻而处于暂停状态

线程的组织与控制

• 线程控制块通常包括：①线程标识符；②一组寄存器，包括程序计数器、状态寄存器和通用寄存器；③线程运行状态，用于描述线程正处于何种状态；④优先级；⑤线程专有存储区，线程切换时用于保存现场等；⑥堆栈指针，用于过程调用时保存局部变量及返回地址等。
  
• 各个线程都可以访问进程地址空间的每个单元，所以一个线程可以读、写或甚至清除另一个线程的堆栈。
  
• 用户程序启动时，通常仅有一个称为“初始化线程”的线程正在执行，其主要功能是用于创建新线程。在创建新线程时，需要利用一个线程创建函数，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小、线程优先级等。线程创建函数执行完后，将返回一个线程标识符
  
• 通常，线程被终止后并不立即释放它所占有的资源，只有当进程中的其他线程执行了分离函数后，被终止线程才与资源分离，此时的资源才能被其他线程利用。被终止但尚未释放资源的线程仍可被其他线程调用，以使被终止线程重新恢复运行

分类

1. 用户级线程(ULT)
   用户级线程的所有管理都在用户空间进行，和内核无关，通常应用从单线程开始，运行中可以随意创建删除线程
   优点：

   1. 不需要切换到内核空间，减少开销
      
   2. 调度算法可以各个进程专用，便于灵活选择
      
   3. 不会影响到操作系统层，所有线程只是应用程序，比较稳定

缺点：

1. 一个线程发起系统调用时，所有同进程的线程都要阻塞  
2. 不能发挥多处理机优势  

2. 内核级线程(KLT)

线程管理在内核空间进行，由内核分配线程管理块，加以管理

优点：

1. 发挥多处理机优势，多个线程可以并行    
2. 一个线程被阻塞，同进程的其他线程依然可以被调度    
3. 内核支持的线程会占用更小的空间，并有更小的开销    
4. 内核也可以使用多线程，更加灵活地调度线程    

缺点：

1. 对同一进程的线程切换，由于需要切换到内核态才能切换，会产生较大开销     

3. 组合方式

内核和用户空间各自可以创建线程，一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程实现的。同一进程中的多个线程可以同时在多处理机上并行执行，且在阻塞一个线程时不需要将整个进程阻塞

线程库(thread library)是为程序员提供创建和管理线程的API。实现线程库主要的方法有如下两种：

• 在用户空间中提供一个没有内核支持的库。这种库的所有代码和数据结构都位于用户空间中。这意味着，调用库内的一个函数只导致用户空间中的一个本地函数的调用。
  
• 实现由操作系统直接支持的内核级的一个库。对于这种情况，库内的代码和数据结构位于内核空间。调用库中的一个API函数通常会导致对内核的系统调用。

目前使用的三种主要线程库是：POSIX Pthreads、Windows APL Java., Pthreads作为POSIX标准的扩展，可以提供用户级或内核级的库。Windows API是用于Windows系统的内核级线程库。Java线程API允许线程在Java程序中直接创建和管理。由于JVM实例通常运行在宿主操作系统之上，Java线程API通常采用宿主系统的线程库来实现，因此在Windows系统中Java线程通常采用Windows API来实现，在类UNIX系统中采用Pthreads来实现。

多线程模型

1. 多对一模型，多个用户线程(一般属于同一进程)映射到一个内核线程,线程管理在用户空间进行，需要内核访问时，挂载到一个内核线程(每次只能一对一映射)
   优点：用户空间管理进程效率较高
   缺点：无法多处理机运行，挂载内核线程时线程堵塞则整个进程堵塞
   
2. 一对一模型,一个用户线程映射一个内核线程
   优点：当一个线程被阻塞后，允许调度另一个线程运行，所以并发能力较强。
   缺点：每创建一个用户线程，相应地就需要创建一个内核线程，开销较大。
   
3. 多对多模型。将n个用户线程映射到m个内核级线程上，要求n>=m。克服了多对一模型并发度不高的缺点，也克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。但实现较复杂。

• 程序这种静态概念难以描述程序的并发执行，因此需要进程这样的动态概念
  
• 引入线程后，进程仍然是资源分配的单位。内核级线程是处理器调度和分派的单位
  
• PCB内所含的数据结构内容，主要有四大类：进程标志信息、进程控制信息、进程资源信息、CPU现场信息
  
• 唯有进程中某线程的栈指针(包含在线程TCB中)是属于线程的，属于进程的资源可以共享，属于线程的栈指针是独享的，对其他线程透明
  
• 父进程可与子进程共享一部分资源，但不能共享虚拟地址空间，在创建子进程时，会为子进程分配资源，如虚拟地址空间等
  
• 执行一条命令或运行一个应用程序时，进程和程序之间形成一对一的关系。进程在执行过程中可以加载执行不同的应用程序，从而形成一对多的关系；以不同的参数或数据多次执行同一个应用程序时，形成多对一的关系；并发地执行不同的应用程序时，形成多对多的关系
  
• 父进程与子进程同时执行(并发)。主程序调用子程序后，主程序暂停在调用点，子程序开始执行
  
• 主要的进程通信方式：共享内存，共享文件，管道，消息传递
  
• 二进制代码和常量存放在正文段，动态分配的存储区在数据堆段，临时使用的变量在数据栈段

处理机调度

处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

调度的层级

1. 高级调度(作业调度)，从外存的后备队列中作业中选取一个调入内存，并分配资源，建立进程。多见于多道批处理系统
   
2. 中级调度(内存调度)，把暂时不能运行的进程调到外存等待，进程进入挂起态，等内存有所空余时调入进入就绪态的进程进入内存，修改成就绪态，入队就绪队列
   
3. 低级调度(进程调度)，从就绪队列选取一个进程交给处理机，最常见最频繁的调度

作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。
挂起指的是进程被调到外存，是内存调度的工作，可分为就绪挂起和阻塞挂起，与阻塞不同的是，阻塞只是暂时无法获得cpu，但进程还在内存中

调度的目标

1. CPU利用率(cpu有效工作时间/(有效工作时间+等待时间))
   
2. 系统吞吐量，单位时间内cpu完成作业的数量
   
3. 周转时间，作业完成时间-作业提交时间。
   1. 平均周转时间
      
   2. 带权周转时间(作业周转时间/作业实际运行时间)
      
   3. 平均带权周转时间，带权周转时间的平均值
      
4. 等待时间，进程等待时间之和
   
5. 响应时间，用户提交需求到系统首次响应需要的时间，对交互式系统是一个重要指标

以上指标不可能兼顾，必须有所取舍

实现

用于调度和分派CPU的组件称为调度程序，一般由三部分组成

1. 排队器，把系统内部的就绪进程排列成一个或者多个就绪队列
   
2. 分派器，根据调度程序选择的进程，把指定进程从队列中拉出，分配cpu
   
3. 上下文切换器，需要进行两个上下文操作
   1. 保存当前程序的上下文到其PCB,装入分派程序的上下文
      
   2. 移出分派程序的上下文，将其PCB内的cpu现场信息装入cpu的寄存器

通常采用两组寄存器，其中一组供内核使用，一组供用户使用。这样，上下文切换时，只需改变指针，让其指向当前寄存器组即可

不能立刻进行调度的特殊情况：

1. 处理中断时，理论上中断是系统级工作，不应被进程影响
   
2. 进程在系统内核临界区，由于此时一般进程被加锁，解锁前不应切换进程(普通临界区则可以)
   
3. 其他需要屏蔽中断的原子操作

需要进行调度的情况：

1. 发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。属于非剥夺调度。
   
2. 中断处理结束或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。属于剥夺方式的调度

现场切换时，操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存它们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的现场信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

有一种特殊的闲逛进程，在没有就绪进程时被处理机运行，一旦有就绪进程就被抢占

进程调度分为两种：

• 抢占调度(剥夺方式)，一个进程在处理机执行时，允许暂停该进程分配处理机给另一个进程
  
• 非抢占调度(非剥夺方式)，在进程运行完成或者进入阻塞态前，不允许其他进程获得它的处理机

线程调度：

• 用户级线程，调度和内核无关，交给进程调度
  
• 内核级线程，内核选择一个特定线程运行，通常不用考虑该线程属于哪个进程。对被选择的线程赋予一个时间片，如果超过了时间片，就会强制挂起该线程。

调度算法

1. FCFS先来先服务(非抢占)
   进程先进先出地进入队列，算法每次都选取最先进入就绪队列的进程运行，直到完成或阻塞才释放
   相对利好长作业和cpu密集作业

2. SJF短作业优先(非抢占)
   从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机
   所有进程都几乎同时到达时，SJF调度算法的平均等待时间、平均周转时间最少,但会产生饥饿问题，且没有考虑优先级，依赖的估计也未必准确
   抢占式的短作业/进程优先调度算法(最短剩余时间优先, SRNT算法)的平均等待时间、平均周转时间最少

3. 优先级调度

调度算法按照优先级从就绪队列调入进程给处理机，可分为抢占与非抢占
根据优先级是否改变，也可以分为静态和动态优先级
优先级设置的可能原则：

• 系统进程>用户进程
  
• 交互进程>非交互进程
  
• I/O密集大于cpu密集

4. 高响应比优先

响应比Rp=((等待时间+要求服务时间)/要求服务时间)
等待时间相同时类似SJF，要求服务时间相同时类似FCFS，但解决了饥饿问题

5. 时间片轮转调度

主要适用于分时系统，按时间片以此选取进程运行

6. 多级队列调度

设置多个就绪队列，每个队列有不同的调度策略

7. 多级反馈队列调度

• 设置多个就绪队列，优先级依次递减，优先级越高的队列，时间片越短
  
• 对一个新进程来说，首先进入第一个队列末尾，如果在第一个时间片内成功则撤离，否则进入第二个队列末尾，这样依次进行，最后一级队列按时间片轮转调度
  
• 只有前面的队列为空，才会轮到下一级的队列，如果有更高优先级的进程来到，可以抢占低优先级或者说低层的进程，被抢占的进程放到该队列末尾

上下文切换：切换进程时,保存上一个进程的状态，并恢复另一个进程的状态
上下文切换的过程

1. 挂起一个进程，保存CPU上下文，包括程序计数器和其他寄存器
   
2. 更新PCB信息
   
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列
   
4. 选择另一个进程执行，并更新其PCB
   
5. 跳转到新进程PCB中的程序计数器所指向的位置执行
   
6. 恢复处理机上下文

• 上下文切换对系统来说意味着消耗大量的CPU时间。有些处理器提供多个寄存器组，这样，上下文切换就只需要简单改变当前寄存器组的指针
  
• 用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性
  
• 一般来说，先有资源的调度，然后才有进程的切换

• 当进程处于临界区时，说明进程正在占用处理机，只要不破坏临界资源的使用规则，就不会影响处理机的调度
  
• 一般来说，因为I/O操作需要及时完成，I/O型作业的优先权高于计算型作业的优先权
  
• 0时刻的调度也计入调度次数
  
• 一般来说cpu密集型作业相对较长

同步与互斥

为了协调进程之间的相互制约关系，引入了进程同步的概念

1. 临界资源:一次仅允许一个进程使用的资源，对其的访问可分为
   1. 进入区，需要在此检查是否可以进入，在进入后设置标志，阻止其他进程进入
      
   2. 临界区，进程访问临界资源的代码
      
   3. 退出区，将对临界资源的访问标志清除
      
   4. 剩余区，代码剩余的部分
      
2. 同步,进程之间由于次序关系产生的等待，传递信息的制约关系
   
3. 互斥，也称间接制约关系，一个进程使用临界资源时，另一个进程必须等待

同步机制应该遵守以下准则：

1. 空闲让进，临界区空闲时允许进入
   
2. 忙则等待,有进程在临界区内，其他进程必须等待
   
3. 有限等待，对所有请求进程，应该保证有限时间内能进入临界区
   
4. 让权等待，进程不能进入时，应该释放处理器防止忙等待

实现互斥的方法

软件实现：

1. 单标志法

设置标志turn,若turn = 0,则允许P0进程进入临界区
两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区,违反了空闲让进原则

//p0进程  
while(turn!=0); //进入区  
critical section; //临界区  
turn=1; //退出区  
remainder section;   
  
//p1进程  
while(turn!=1); //进入区  
critical section; //临界区  
turn=0; //退出区  
remainder section; //剩余区  

2. 双标志法先检查

在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问，该进程需等待；否则，进程才进入自己的临界区。
设置数组flag,如第i个元素flag[i]为FALSE,表示Pi进程未进入临界区，如为TRUE,表示Pi进程进入临界区。

//Pi进程  
while(flag[j]);   
flag[i]=TRUE;  //进入区  
critical section; //临界区  
flag[i]=FALSE; //退出区  
remainder section; //剩余区  
  
//Pj进程  
while(flag[i]);   
flag[j]=TRUE;  //进入区  
critical section; //临界区  
flag[j]=FALSE; //退出区  
remainder section; //剩余区  

在检查对方的flag后和切换自己的flag前有一段时间，有可能都检查通过,例如双方近乎同时检查了，随后就会一起进入临界区
违反忙则等待原则

3. 双标志法后检查

先将自己的标志设置为TRUE,再检测对方的状态标志，若对方标志为TRUE,则进程等待；否则进入临界区。
当两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，结果导致都无法进入的饥饿问题,违背空闲让进与有限等待

//Pi进程  
flag[i]=TRUE;   
while(flag[j]);   
critical section;  
flag[i]=FALSE;   
remainder section;   
  
//Pj进程  
flag[j]=TRUE;  
while(flag[i]);  
critical section;  
flag[j]=FALSE;  
remainder section;  

4. Peterson's Algorithm

每个进程在先设置自己的标志后再设置turn标志。这时，再同时检测另一个进程状态标志和允许进入标志，以便保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。

//Pi进程  
flag [i] =TRUE; turn=j ;   
while(flag[j]&&turn==j);  
critical section;  
flag[i]=FALSE;  
remainder section;  
  
//Pj进程  
flag [j] =TRUE; turn=i ;   
while(flag[i]&&turn==i);  
critical section;  
flag[j]=FALSE;  
remainder section;  

flag表示进入意愿，turn表示优先级，如果对方想进入且更优先，则自己要忙等待，利用flag解决临界资源的互斥访问，而利用turn解决"饥饿”现象，因为需要忙等待，违背了让权等待原则

硬件实现

1. 中断屏蔽方法

一个进程进入临界区后直接禁止中断的产生，这种方法有损处理机运行效率，且有中断不被再次启用的风险，且只适用于系统内核的进程

关中断；  
临界区；  
开中断；  

2. 硬件指令方法

lock表示资源的两种状态：true表示正被占用，初值为false。进程在进入临界区之前，利用TestAndSet检查标志lock,若无进程在临界区，返回值为false,可以进入，关闭临界资源，把lock置为true,使任何进程都不能进入临界区；若有进程在临界区，则循环检查，直到进程退出。
这样的方法依旧让其他进程会忙等待
Swap类似TSL(Test and Set Lock),只是改用交换的方式检查标志

boolean TestAndSet(boolean *lock) {//原子指令,设置某个标志为真，并读出旧标志  
    boolean old;  
    old=*lock;  
    *lock=true;  
    return old;  
}  
  
Swap(boolean *a, boolean *b) {  
    boolean temp;  
    temp=*a;  
    *a=*b; .  
    *b=temp;  
}  
  
//testandset实现互斥  
while TestAndSet(&lock) ;  
//进程的临界区代码段；  
lock=false;  
//进程的其他代码；  
  
//用swap实现互斥  
bool key=true;  
while(key!=false) Swap(&lock, &key);  
//进程的临界区代码段；  
lock=false;  
//进程的其他代码；  

硬件实现的优点

• 适用于任意数目的进程，而不管是单处理机还是多处理机；
  
• 简单、容易验证其正确性。
  
• 可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量

硬件实现的缺点

• 进程等待进入临界区时要耗费处理机时间，不能实现让权等待。
  
• 从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致"饥饿”现象

互斥锁

解决临界问题的有效机制是互斥锁，进程进入临界区前得到锁，退出时释放锁

acquire(){//原子  
    while(!available); //忙等待  
    available=false; //获得锁  
    }  
release(){//原子  
    available=true; //释放锁  
}  

适用于多处理器系统，不适用于单处理器，这种需要忙等待的锁称为自旋锁，通常硬件实现，TSL也是此类
以上所有方法都无法实现让权等待，因此需要信号量机制

信号量

另一种有效机制是信号量,它只能被两个标准的原语wait(P)和signal(S)访问，也可记为“P操作”和"V操作”(首字母来源于荷兰语)
信号量例题

分类

1. 整型信号量

wait(S){  
    while(S<=0);  
    S=S-1;  
}  
  
signal(S){  
    S=S+1;  
}  

只要信号量S<=0,就会不断地忙等待。因此并未遵循“让权等待”的准则。

2. 记录型信号量

除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L,用于链接所有等待该资源的进程

typedef struct{  
int value;  
struct process *L;  
} semaphore;  
  
void wait (semaphore S) { //相当于申请资源  
    S.value--;  
    if(S.value<0) {  
    //add this process to S.L;  
    block(S.L);  
    }  
}  
void signal (semaphore S) { //相当于释放资源  
    S.value ++;  
    if (S. value<=0) {  
    //remove a process P from S.L;  
    wakeup(P);  
    }  
}  

这样一来信号量的value值，若是自然数表示剩余资源，若是负数，其绝对值就是阻塞的进程数量

基于信号量的同步

semaphore S=0; //初始化信号量  
P1() {  
    //其他  
    x;  
    V(S);//告诉进程P2,语句x巳经完成  
    //其他  
}  
  
P2() {  
    //其他操作  
    P(S);//检查语句x是否运行完成  
    y;//检查无误，运行y语句  
    //其他  
}  

y想要运行必须得到X释放的信号量，由此实现了同步

信号量实现互斥

semaphore S=1; //初始化信号量  
P1() {  
    //其他  
    P(S);//加锁  
    //临界区  
    V(S);//解锁  
    //其他  
}  
  
P2() {  
    //其他操作  
    P(S);//加锁  
    //临界区  
    V(S);//访问结束，解锁  
    //其他  
}  

当没有进程在临界区时，任意一个进程要进入临界区，就要执行P操作，把S的值减为0,然后进入临界区；当有进程存在于临界区时，S的值为0,再有进程要进入临界区，执行P操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。
互斥问题中，P, V操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

信号量实现前驱关系

semaphore a1=a2=b1=b2=c=d=e=0;  
Sl() { //初始化信号量  
    //其他  
    V(a1); V(a2); //S1已经运行完成  
}  
S2() {  
    P(a1); //检查S1是否运行完成  
    //其他  
    V(b1);V(b2); //S2已经运行完成  
}  
S3() {  
    P(a2); //检查S1是否己经运行完成  
    //其他  
    V(c); //S3己经运行完成  
}  
S4() {  
    P(b1); //检查S2是否已经运行完成  
    //其他  
    v(d); //S4已经运行完成  
}  
S5() {  
    P(b2); //检查S2是否已经运行完成  
    //其他  
    V(e); //S5已经运行完成  
}  
S6() {  
    P(c); //检查S3是否已经运行完成  
    P(d); //检查S4是否已经运行完成  
    P(e); //检查S5是否已经运行完成  
    //其他  
}  

也就是说，互斥操作是先P在V，同步时，前面的进程先V，后面的进程P操作才不会阻塞

管程

利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程(monitor)。

管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。
管程的组成:

1. 名称
   
2. 管程内部的共享数据结构说明
   
3. 对该数据结构操作的一组过程
   
4. 对管程内部共享数据设置初值的语句

monitor Demo{ //1.定义一个名称为“Demo”的管程  
    //2.定义共享数据结构，对应系统中的某种共享资源  
    //共享数据结构 S;  
    //4.对共享数据结构初始化的语句  
    init_code() {  
        S=5; //初始资源数等于5  
    }  
    //3.过程1:申请一个资源  
    take_away(){  
        对共享数据结构x的一系列处理；  
        S --; //可用资源数-1  
        //其他  
    }  
    //3.过程2；归还一个资源  
    give_back() {  
        //对共享数据结构x的一系列处理；  
        S++; //可用资源数+1  
        //其他  
    }  
}  

• 一个进程只有通过调用管程内的过程才能进入管程访问共享资源
  
• 每次只允许一个进程进入管程，如果多个进程想进入，只能依次进行

条件变量
将阻塞原因定义为条件变量condition，在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即wait和signaL
x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。此时其他进程可以使用该管程。
x.signal： x对应的条件发生了变化，则调用x.signal,唤醒一个因x条件而阻塞的进程

monitor Demo {  
    //共享数据结构S;  
    condition x; //定义一个条件变量x  
    init_code(){/*其他*/ }  
    take_away(){  
        if (S<=0) x.wait (); //资源不够，在条件变量x上阻塞等待  
        //资源足够，分配资源，做一系列相应处理：  
    }  
    give_back() {  
        //归还资源，做一系列相应处理；  
        if (/*有进程在等待*/) x.signal () ;//唤醒一个阻塞进程  
    }  
}  

与信号量不同的是，条件变量不需要记录剩余资源数，这个部分由管程的共享数据结构记录

同步问题实例

生产者-消费者

一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源；它只允许一个生产者放入消息，或一个消费者从中取出消息。

semaphore mutex=1; //临界区互斥信号量  
semaphore empty=n;//空闲缓冲区  
semaphore full=O;//缓冲区初始化为空  
/*信号量mutex作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量初值为1;信号量full用于记录当前缓冲池中的满缓冲区数，初值为0。信号量empty用于记录当前缓冲池中的空缓冲区数，初值为n*/  
producer() {//生产者进程  
    while (1) {  
        //produce an item in nextp;生产数据  
        P (empty);//获取空缓冲区单元  
        P (mutex);//进入临界区  
        //add nextp to buffer;//将数据放入缓冲区  
        V (mutex);//离开临界区，释放互斥信号量  
        V(full);//满缓冲区数加1  
    }  
}  
  
consumer() {//消费者进程  
    while(1){  
        P(full);//获取满缓冲区单元  
        P(mutex);//进入临界区  
        //remove an item from buffer;从缓冲区中取出数据  
        V(mutex);//离开临界区，释放互斥信号量  
        V(empty);//空缓冲区数加1  
        consume the item;//消费数据  
    }  
}  

必须确保先获取一个缓冲区单元再进入临界区，否则缓冲区满时，由于临界区已经锁住，只能无限等待对方释放空/满缓冲区，陷入死锁

更复杂的变种：

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出
两个生产者和两个消费者被连接到大小为1的缓冲区上。爸爸妈妈互斥，爸爸女儿，妈妈儿子是同步关系

semaphore plate=1, apple=0, orange=0;  
/*首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果,初值为1表示允许放入，且只允许放入一个。  
信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。  
信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange = 1表示可以取。*/  
dad () { //父亲进程  
    while (1) {  
        //prepare an apple;  
        P(plate); //互斥向盘中取、放水果  
        //put the apple on the plate; //向盘中放苹果  
        V(apple); //允许取苹果  
    }  
}  
mom() { //母亲进程  
    while (1) {  
        //prepare an orange;  
        P(plate); //互斥向盘中取、放水果  
        //put the orange on the plate; //向盘中放橘子  
        V(orange); //允许取橘子  
    }  
}  
son() { //儿子进程  
    while(1) {  
        P(orange); //互斥向盘中取橘子  
        //take an orange from the plate;  
        V(plate); //允许向盘中取、放水果  
        //eat the orange;  
    }  
}  
daughter() {//女儿进程  
    while(1) {  
        P(apple); //互斥向盘中取苹果  
        //take an apple from the plate;  
        V(plate); //允许向盘中取、放水果  
        //eat the orange;  
    }  
}  

读者-写者问题

有读者和写者两组并发进程，共享一个文件，读进程并行执行没有问题，写进程和其他进程同时访问共享数据时则可能导致数据不一致的错误。
要求：

• 允许多个读者可以同时对文件执行读操作
  
• 只允许一个写者往文件中写信息
  
• 任意一个写者在完成写操作之前不允许其他读者或写者工作
  
• 写者执行写操作前，应让己有的读者和写者全部退出

int count=0; //用于记录当前的读者数量  
semaphore mutex=1;//用于保护更新count变量时的互斥   
semaphore rw=1;//用于保证读者和写者互斥地访问文件  
  
void writer() {  
  while (1) {  
    P(rw); //互斥访问共享文件  
    writing;  
    V(rw);  
  }  
}  
  
void reader(){//读者进程   
  while (1) {  
    P(mutex);//互斥访问count变量  
    if(count==0)//互斥访问count变量  
      P(rw);//阻止写进程写    
    count++; //读者计数器加1  
    V(mutex); //释放互斥变量count  
    reading; //读取  
    P(mutex); //互斥访问count变量  
    count--; //读者计数器减1    
    if(count==0) V(rw); //当最后一个读进程读完共享文件后允许写进程写释放互斥变量count  
    V(mutex);//释放互斥变量count  
  }  
}  

以上是一种读进程优先的情形，只要读进程存在，就会一直阻塞写进程
若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到己在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。增加一个信号量并在上面程序的writer,和reader。函数中各增加一对PV操作，就可以得到写进程优先的解决程序

int count=0;//用于记录当前的读者数量  
semaphore mutex=1;  //用于保护更新count变量时的互斥  
semaphore rw=1;//用于保证读者和写者互斥地访问文件   
semaphore w=1;//用于实现“写优先”  
writer() {//写者进程  
  while (1){  
   P(w);//在无写进程请求时进入  
   P(rw); //互斥访问共享文件  
   writing;   
   V(rw); //释放共享文件  
   V(w); //恢复对共享文件的访问  
  }  
}  
  
void reader() {//读者进程  
  while (1) {  
    P(w); //在无写进程请求时进入  
    P(mutex); //互斥访问count变量  
    if (count==0)//当第一个读进程读共享文件时  
        P(rw); //阻止写进程写  
    count++;//读者计数器加1    
    V(mutex); //释放互斥变量count  
    V(w); //恢复对共享文件的访问  
    reading;//读取  
    P(mutex);//互斥访问count变量  
    count--;//读者计数器减1  
    if (count==0)//当最后一个读进程读完共享文件  
        V(rw);//允许写进程写  
    V(mutex);//释放互斥变量count  
  }  
}  

哲学家进餐问题

当哲学家饥饿时，尝试拿起左、右两根筷子(一根一根地拿起)。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，释放筷子。

semaphore chopstick[5] ={1,1,1,1,1}; //定义信号量数组 chopstick[5],并初始化  
/*定义互斥信号量数组chopstick[5]=(1, 1, 1, 1, 1),用于对5个筷子的互斥访问。哲学家按顺序编号为0〜4,哲学家i左边筷子的编号为i，哲学家右边筷子的编号为(i + 1)%5*/  
Pi() {//i号哲学家的进程  
    do{  
        P(chopstick[i]); //取左边筷子  
        P(chopstick[(i+1)%5]); //取右边筷子  
        eat(); //进餐  
        V (chopstick[i]); //放回左边筷子  
        V(chopstick[(i+1)%5]);//放回右边筷子  
        think();  
    } while(1);  
}  

该算法存在以下问题：当5名哲学家都想要进餐并分别拿起左边的筷子时(都恰好执行完wait(chopstick[i]);)筷子已被拿光，等到他们再想拿右边的筷子时(执行wait(chopstick[(i + 1)%5]);)就全被阻塞，因此出现了死锁。
为防止死锁发生，可对哲学家进程施加一些限制条件，

• 至多允许4名哲学家同时进餐；
  
• 仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子(令取两只筷子这个行为互斥，这样只有左右都有筷子时才能获取成功)；
  
• 对哲学家顺序编号，要求奇数号哲学家先拿左边的筷子，然后拿右边的筷子，而偶数号哲学家刚好相反。

semaphore chopstick[5] = {1,1,1,1,1};  
semaphore mutex=1;  
Pi() {//当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子  
    do{  
    P(mutex);//在取筷子前获得互斥量  
    P(chopstick[i]);  
    P(chopstick[(i+1)%5]);  
    V(mutex);//释放取筷子的信号量  
    eat;  
    V(chopstick[i]); //放回左边筷子  
    V(chopstick[ (i+1) %5] ) ; //放回右边筷子  
    think; //思考  
    } while (1);  
}  

吸烟问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉己完成，此时供应者就会将另外两种材料放到桌上，如此重复(让三个抽烟者轮流地抽烟)。

int num=0;  
semaphore offer1=0;   
semaphore offer2=0;  
semaphore offer3=0;  
semaphore finish=0;  
  
/*信号量offerl, offer2, offer3分别表示烟草和纸组合的资源、烟草和胶水组合的资源、纸和胶水组合的资源。信号量finish用于互斥进行抽烟动作。*/  
void P1(){  
  while(1){  
    num++;  
    num=num%3;  
    if(num==0)   
      V(offer1);  
    else if(num==1)    
      V(offer2);  
    else  
      V(offer3);  
    P(finish);  
  }  
}  
  
void P2(){  
  while(1){  
    P(offer3);    
    //拿纸和胶水,卷成烟,抽掉  
    V(finish);   
  }  
}  
  
void P3(){  
  while(1){  
    P(offer2);  
    //拿烟草和胶水,卷成烟,抽掉  
    V(finish);  
  }    
}  
  
void P4(){  
  while(1){  
    P(offer1);  
    //拿烟草和纸,卷成烟,抽掉  
  }  
}  

总结

为了协调进程之间的相互制约关系，引入了进程同步的概念。
同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。
互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

死锁

死锁的原因

1. 系统资源的竞争
   
2. 进程推进顺序非法
   
3. 信号量配置错误

必要条件

1. 互斥，一段时间内某资源只能被一个进程占用
   
2. 不抢占
   
3. 请求并占有
   
4. 循环等待，存在一个进程集合，其资源分配图存在循环

处理策略

1. 预防，破坏必要条件
   
2. 避免，防止资源分配导致的死锁
   
3. 检测和解除，允许死锁，发现后解除死锁

预防

1. 互斥，允许资源共享，但对某些特定资源很难做到
   
2. 不抢占，一个持有不可被抢占资源的进程申请资源时必须释放已有资源(有损运行效率)
   
3. 占有并等待，运行前进程必须申请到需要的所有资源(浪费资源)
   
4. 循环等待，给资源编号，必须按递增顺序申请，同类资源一次申请完，(在这种机制的实现上会有麻烦)

总的来说，预防死锁要么难以实现，要么极大损失性能

避免

1. 系统安全状态
   系统在进行资源分配之前，应先计算此次分配的安全性，如果不安全，则不分配资源
   安全状态，是指系统能按某种进程推进顺序(P1,P2,……,Pn)为每个进程Pi分配其所需的资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序完成。此时称P1,P2,…，Pn为安全序列。只要在前的进程结束后归还资源时，剩余资源满足后面的进程需要，那么就是安全的

2. 银行家算法

把操作系统视作银行家，进程运行前声明最大需求量，运行时分配的总资源不超过这个需求量，此外，如果申请时资源超过系统能分配的资源，就暂时推迟分配

数据结构

• 可利用资源向量Available：含有m个元素的数组，其中每个元素代表一类可用的资源数目。Available[j] = K表示系统中现有Rj类资源K个。
  
• 最大需求矩阵Max：n*m矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求。 简单来说，一行代表一个进程，一列代表一类资源。Max[i,j]=K表示进程i需要Rj类资源的最大数目为K
  
• 分配矩阵Allocation： n*m矩阵，定义系统中每类资源当前已分配给每个进程的资源数。Allocation[i,j]=K表示进程i当前已分得Rj类资源的数目为K
  
• 需求矩阵Need: n*m矩阵，表示每个进程接下来最多还需要多少资源。Need[i,j]= K表示进程i还需要Rj类资源的数目为 K
  
• 上述三个矩阵间存在下述关系： Need = Max- Allocation

运行步骤

1. 若Request_i[j]<=Need[i,j]则转到2. 否则进程要求资源超过Max
   
2. Request_i[j]<=Available[j],则转到3.，否则系统资源不足
   
3. 预分配资源，且修改数据结构
   

//Request_i表示i请求的各种资源  
Available = Available- Request_i;  
Allocation[i, j] = Allocation[i, j] + Request_i[j];  
Need[i,j] = Need[i, j] - Request_i[j]；  

4. 确认分配后系统安全，然后分配资源，否则放弃，让进程等待(安全性算法)

安全性算法

设置工作向量Work,有m个元素，表示系统中的剩余可用资源数目。在执行安全性算法开始时，Work = Available

1. 初始时安全序列为空。
   
2. 从Need矩阵中找出符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于或等于Work向量，找到后，把对应的进程加入安全序列；若找不到，则执行步骤4.。
   
3. 进程R进入安全序列后，可顺利执行，直至完成，并释放分配给它的资源，因此应执行Work = Work + Allocation[i],其中Allocation[i]表示进程 Pi代表的在 Allocation 矩阵中对应的行，返回步骤2.
   
4. 若此时安全序列中已有所有进程，则系统处于安全状态，否则系统处于不安全状态。

简单来说，类似放贷，先放出能借出的钱，这时总资产就可以把所有借款归还后的本金和利息算入，在这样的基础上继续放贷，如果最后这样计算下来能满足所有借贷需求，就视作资金安全

检测和解除

检测

资源分配图
用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程

检测方法

1. 找到不阻塞且不孤立的进程Pi(与其连接的资源边，申请数量少于系统空闲资源)，这样的进程必然可以完成，因此消去其的边
   
2. 消除第一步的进程的新图继续按1.中的方法消去边，如果最后所有进程孤立，则该图可完全简化

资源分配图不可完全简化是死锁的充要条件(死锁定理)

解除

1. 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源而处于资源匮乏的状态。
   
2. 撤销进程法。强制撤销部分甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
   
3. 进程回退法。让一(或多)个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而非被剥夺。要求系统保持进程的历史信息，设置还原点

• 死锁检测不需要知道系统总资源数
  
• 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
• 绝对不会死锁的情况：设k个进程需要的最大资源数为xk,对每个临界资源来说，其总数≥sum(x_1-1,x_2-1,……x_k-1)+1，即至少一个进程能得到需要的所有资源

---

内存管理

概念

内存管理包括

• 内存空间的分配与回收
  
• 逻辑地址和物理地址的转换
  
• 通过虚拟技术扩充内存空间
  
• 内存共享，允许多进程共享内存空间
  
• 存储保护，维护各个作业地址空间的独立

程序的链接和装入

• 编译，将源代码编译成若干模块
  
• 链接，链接编译出的各个模块
  • 静态链接，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，需要修改相对地址，并且变换外部调用符号为相对地址(编译后所有目标模块都是0开始的相对地址)
    
  • 装入时动态链接，装入内存时，边装入边链接，便于修改更新
    
  • 运行时动态链接，程序执行时才会链接目标模块，执行用不到的模块就暂时不会被链接(节省空间优化性能)
    
• 装入，把模块装入内存运行
  • 绝对装入，只适用于单道环境，装入到装入程序提供的绝对地址，且此时的逻辑地址和实际内存地址相同，且地址可以手动指定
    
  • 可重定位装入，装入时对目标程序中指令和数据地址进行修改(该过程叫做重定位),这样的变换一般在装入进程时一次完成，因此叫做静态重定位
    
  • 动态运行时装入，也称为动态重定位，装入模块装入内存后，在程序执行时才把相对地址转换成绝对地址(需要重定位寄存器支持)，这样对地址的使用灵活，且便于程序段共享

编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址(或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间(或虚拟地址空间).进程在运行时，看到和使用的地址都是逻辑地址
对于32位系统，逻辑地址空间的范围为0~2^32-1

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。
操作系统通过内存管理部件(MMU)将进程使用的逻辑地址转换为物理地址。进程使用虚拟内存空间中的地址，操作系统在相关硬件的协助下，将它"转换”成真正的物理地址。逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。

进程的内存映像

• 代码段：即程序的二进制代码，代码段是只读的，可以被多个进程共享。
  
• 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量。
  
• 进程控制块(PCB)：存放在系统区。操作系统通过PCB来控制和管理进程。
  
• 堆：用来存放动态分配的变量。通过调用malloc函数动态地向高地址分配空间。
  
• 栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长。

代码段和数据段在程序调入内存时就指定了大小，而堆和栈动态管理空间

内存保护
操作系统需要维护每个进程有独立的内存空间，与系统和其他进程隔绝，也就是内存保护

• cpu设置上下限寄存器，存放用户作业的地址上下限，用来判断访问是否越界
  
• 使用重定位寄存器(基地址寄存器)和界地址寄存器(限长寄存器)，前者有最小的物理地址，后者存放逻辑地址最大值

加载重定位寄存器和界地址寄存器时必须使用特权指令，只有操作系统内核才可以加载这两个存储器。

内存共享
可重入代码又称纯代码，是一种允许多个进程同时访问但不允许被任何进程修改的代码。但在实际执行时，也可以为每个进程配以局部数据区，把在执行中可能改变的部分复制到该数据区，这样，程序在执行时只需对该私有数据区中的内存进行修改，并不去改变共享的代码区。

内存的分配方式

连续分配管理

为一个用户程序分配一个连续的内存空间

1. 单一连续分配，分为系统区和用户区，分别供系统和单一用户程序使用。这种方法无外部碎片，但只用于单用户单任务系统
   
2. 固定分区分配，用户内存空间分成若干分区，每个分区只用于装载一个作业。如果分区大小不等，就需要建立使用表格来分配。容易产生内部碎片，或者划分空间太小
   
3. 动态分区分配，进程装入内存时根据其需要分配空间，容易产生外部碎片，并且需要确定内存块分配算法，比如
   1. 首次适应，容易在低地址处产生碎片,综合最好
      
   2. 邻近适应，首次适应的基础上从上次查找结束的位置继续查找，容易在尾地址产生碎片，且导致大碎片匮乏
      
   3. 最佳适应，找到满足要求的最小分区，产生最多外部碎片
      
   4. 最坏适应，找到满足要求的最大分区，导致空间匮乏

回收内存
系统根据回收分区的始址，从空闲分区链中找到相应的插入点

1. 回收区与插入点的前一空闲分区相邻，将这两个分区合并，并修改前一分区表项的大小为两者之和；
   
2. 回收区与插入点的后一空闲分区相邻，将这两个分区合并，并修改后一分区表项的始址和大小；
   
3. 回收区同时与插入点的前、后两个分区相邻，此时将这三个分区合并，修改前一分区表项的大小为三者之和，取消后二分区表项；
   
4. 回收区没有相邻的空闲分区，此时应为回收区新建一个表项，填写始址和大小，并插入空闲分区链。

基于索引搜索的分配算法,大、中型系统中往往采用索引,根据其大小对空闲分区建立索引，按需要的大小分配:

1. 快速适应算法，索引表中找到能容纳需要的最小空闲分区链表，从链表中取出第一块进行分配。内部碎片小，但需要频繁回收合并
2. 伙伴系统。规定所有分区的大小均为2的k次幕，对需求n，取其上界大小的分区，若不存在，则对半拆分若干次更大的分区(拆分后多余的大小填入分配索引表)
3. 哈希算法。构建一张以空闲分区大小为关键字的哈希表以及恰当的哈希函数，根据哈希函数计算结果分配

分页存储管理

把内存分为若干固定大小的块，进程根据需要申请一定数量的块，只有最后一块会产生内部碎片
进程中的块称为页或页面(Page),内存中的块称为页框或页帧(Page Frame)外存也以同样的单位进行划分，直接称为块或盘块(Block)。

页号	页内偏移量
P	W

地址结构包含两部分：前一部分为页号P,后一部分为页内偏移量W,地址长度为32位，其中0〜11位为页内地址，即每页大小为4KB； 12〜31位为页号，即最多允许2^20页
页表记录页面在内存中对应的物理块号，一般也放在内存(PCB)

地址变换

地址变换机构将逻辑地址转换成内存中的物理地址，借助页表实现
系统中通常设置一个页表寄存器(PTR),存放页表在内存的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度存放在本进程的PCB中，当进程被调度执行时，才将页表始址和页表长度装入页表寄存器中。

页面大小为Z,逻辑地址A到物理地址E的变换过程：

1. 计算页号P=A/L，页内偏移量W=A%L
   
2. 比较页号和页表长度M，如果P>=M，则产生越界中断
   
3. P对应页表地址=页表始址F+页号P*页表项长度，该项内容b就是物理块号。//页表项长度指页地址占多大的存储空间
   
4. E=b*L + W，得出物理地址并访问内存

页表项大小怎么确定
逻辑地址空间大小/页大小得到页数，页表项大小的位数就要确保能表示这个页数，其位数需要大于等于对页数取的对数
一般用字节作为地址单位，所以对这个位数除8并向上取整得到需要的字节数

问题：

• 需要确保地址转换足够快
  
• 页表不能太大，否则会浪费空间，降低内存利用率

快表

在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器一一快表，又称相联存储器(TLB),用来存放当前访问的若干页表项，以加速地址变换的过程，相对应的，主存中的页表称为慢表  

地址变换过程

1. 逻辑地址给出后，页号送入高速缓存寄存器，与快表中的所有页号比较
2. 如果快表中有存储，直接取出页框号，算出物理地址
3. 否则访问慢表，并将最后得出的页表项送入快表，如果已满则推出原有一项

两级页表

鉴于大量页表不仅占用极大的连续空间，并且很可能真正使用的内存并没有这么多页，需要引入二级页表  
顶级页表最多只有一个页面  
需要在系统中增设一个外层页表寄存器（也称页目录基址寄存器）.用于存放页目录始址。将逻辑地址中的页目录号作为页目录的索引，从中找到对应页表的始址：再用二级页号作为页表分页的索引，从中找到对应的页表项,由于最后需要一次取内存块操作，N级页表一次读写需要N+1次访存

分段存储管理

按照用户进程划分段，段内要求连续，段间不要求连续，段号和段内偏移量必须由用户显式提供，在高级程序设计语言中，这个工作由编译程序完成。  
每个进程都有一张逻辑空间与内存空间映射的段表，其中每个段表项对应进程的一段，段表项记录该段在内存中的始址和长度

段表寄存器，用于存放段表始址F和段表长度M  

地址变换过程  

1. 从逻辑地址A取出段号S和段内偏移量W
2. 确保S<M,否则越界中断
3. 段号S对应段表项地址=段表始址F+段号S*段表项长度，取出表项中的段长C，并确保段内偏移量<C
4. 取出段表项中的始址b，E=b+W,用E访问内存

共享与保护
段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的，这产生了一个读者写者问题，读者在读，写者就不能写
可重入代码(不能修改的代码)和不能修改的数据可以共享，可修改的代码和数据不能共享

段的保护分为存取控制保护和地址越界保护
越界保护确保段号小于段表长度且段内偏移量小于段长

段页式管理

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位  
作业的逻辑地址分为三部分：段号、页号和页内偏移量  
段表只有一个，而页表可能有多个。
进行地址变换时，首先通过段表查到页表始址，然后通过页表找到页帧号，最后形成物理地址，是一种二维地址
分段对用户是可见的，编程需要指定段号，段内地址，而页的所有部分对用户透明

• 整个系统中设置一个重定位寄存器(放程序在内存中的始址),运行不同程序时更换内容
  
• 段式存储管理方式，主要是为了满足用户的下列要求：方便编程、分段共享、分段保护、动态链接和动态增长
  
• 对主存的访问以字节或字为单位,分配则是区，页，段等划分
  
• 每个进程有自己的页表，进程未执行时，页表的始址和页表长度存放在本进程的PCB中，执行时调入内存的页表寄存器
  
• 一个页目录能放下的表项是页面大小/表项大小，表项数量总和必须等于虚拟地址的页面数
  
• 最佳适应算法最容易产生内存碎片
  
• 计算有效存取时间要考虑快表查询是同时还是在先

虚拟内存

其他内存扩充方法：

• 覆盖：程序或进程分为固定区与覆盖区，固定区常驻内存，覆盖区可以不断交换给其他进程，基本过时
  
• 交换：进程被调度程序调入调出内存(需要外存提供单独的交互区)

如果作业一次性全部装入内存，且在完成前无法换出,其实会造成内存空间的浪费，因此就需要虚拟内存技术
局部性原理：

1. 时间局部性。程序中的某条指令一旦执行，不久后该指令可能再次执行
   
2. 空间局部性,程序在一段时间内所访问的地址，可能集中在一定的范围之内，因为指令和数据通常是顺序存放、顺序执行的

基于局部性原理，内存中可以只存放部分程序需要的页面或者段，其他部分留在外存，需要时再调入，这种机制叫做虚拟存储器
虚拟存储器有以下三个主要特征：

1. 多次性。是指无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行，多次性是虚拟存储器最重要的特征。
   
2. 对换性。是指无须在作业运行时一直常驻内存，在进程运行期间，允许将那些暂不使用的程序和数据从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换进)
   
3. 虚拟性。是指从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量。这是虚拟存储器所表现出的最重要特征，也是实现虚拟存储器的最重要目标。

连续性内存分配不支持逻辑上的扩容，因此虚拟内存只有三种实现方式：

• 请求分页存储管理。
  
• 请求分段存储管理。
  
• 请求段页式存储管理

虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
同时需要内外存，页表机制，中断，地址变换等硬件支持

请求分页管理方式

基于分页系统的虚拟内存是最常见的

为了解决区分访问页面在不在内存中而增加的页表项字段：

• 状态位F。用于指示该页是否已调入内存，供程序访问时参考。
  
• 访问字段A,用于记录本页在一段时间内被访问的次数，或记录本页最近己有多长时间未被访问，供置换算法换出页面时参考。
  
• 修改位M,标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存。
  
• 外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

缺页中断
每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞(调页完成唤醒)，若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页(若被淘汰页在内存期间被修改过，则要将其写回外存)
缺页中断属于内中断(内部异常)的故障fault

地址变换

1. 检索快表，如果找到要访问的页，修改访问位，利用表项的物理块号和页内偏移量算出物理地址
   
2. 找不到页表项则到内存查找页表，对比状态位P，看页是否已经调入内存，若调入则该页的页表写入快表，快表已满则替换，若未调入，则产生缺页中断，从外存调入

页框分配

对进程分配物理页框也是需要操作系统需要考虑的问题，这会影响主存的多道程度，进程的缺页率等
一般来说有以下几种策略：

1. 固定分配局部置换,每个进程物理帧数量固定，缺页时在固定的框中选一个置换，缺点是难以确定合适数量的帧
   
2. 可变分配全局置换，分配一定数量的物理块，运行期间动态增减，缺点是可能会盲目增减
   
3. 可变分配局部置换，与1.类似，但如果频繁缺页则会分配更多物理块，直到缺页率正常，若缺页率低也会适当减少物理块

物理块调入算法：

1. 平均分配，所有物理块均分给进程
   
2. 按比例分配，按进程大小比例分配
   
3. 优先级分配，优先级高的进程有更多物理块

调入页面的时机：

1. 预调页，预测可能被访问的页，提前调入内存，也可以由程序员指定
   
2. 请求调页，需要的页不在内存时再调入，易于实现，但I/O开销较大

调入页面的区域
请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘I/O速度比文件区的更快

1. 对换区空间足够，则全部由对换区调入
   
2. 对换区空间不足，不需要修改的文件都从文件区调入，可能修改的则先调到对换区，需要时通过对换区调入
   
3. UNIX方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于是放在对换区，因此在下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入

• 快表有的页面必然在内存中，如果一个页调出内存，需要同时删除其快表项(如果有的话)
  
• 只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数
  
• 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中

当进程所访问的页面不在内存中时(存在位为0),便向CPU发出缺页中断，中断响应后便转入缺页中断处理程序。该程序通过查找页表得到该页的物理块，此时如果内存未满，则启动磁盘I/O,将所缺页调入内存，并修改页表。如果内存已满，则先按某种置换算法从内存中选出一页准备换出；如果该页未被修改过(修改位为0),则无须将该页写回磁盘；但是，如果该页己被修改(修改位为1),则必须将该页写回磁盘，然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为1。调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址

页面置换算法

1. 最佳置换(OPT),换出最长时间内不再被访问的页面，以便保证获得最低的缺页率，无法真正实现，只能用于其他算法的评价参考
   
2. FIFO,淘汰最先进入内存的页面，会产生所分配的物理块数增大而页故障数不减反增的异常现象，称为Belady异常，只有FIFO会有这种异常
   
3. 最近最久未使用(LRU)置换,该算法为每个页面设置一个访问字段，用来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。性能较好，但开销较大且需要硬件支持
   
4. 时钟(CLOCK)置换算法，为每帧设置一位访问位A，当某页首次被装入或被访问时，其访问位被置为1，所有帧视为循环队列，有一个从第一个帧开始的指针，替换时循环检查，访问位若是1置0且指针后移，若是0则替换，替换后指针后移一位,最多需要两轮
   
5. 改进后的clock算法,换出页面时，修改过的页额外需要写回磁盘，有更高的性能代价，除考虑页面使用情况外，还增加了置换代价一一修改位M。在选择页面换出时，优先考虑既未使用过又未修改过的页面。
   1. 寻找第一个A==M==0的页面，这次扫描不改变A
      
   2. 第二轮扫描，寻找第一个A==0 && M==1的页面，这次扫描到的页面A置0
      
   3. 指针复位，所有帧访问位置0，重复1.2.直到找到一个符合要求的页
      
   4. 最多四轮扫描就能找到一个置换页(所有页A==M==1时才需要四轮)

抖动和工作集合

刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸。
抖动的根本原因是，系统中进程的资源不足，频繁缺页

工作集是指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。
工作集W可由时间t和工作集窗口大小Δ来确定

一般来说分配给进程的物理块数(即驻留集大小)要大于工作集大小。落在工作集内的页面需要调入驻留集中，而落在工作集外的页面可从驻留集移除。若可用物理块小于进程的工作集合，就需要暂停一个进程

一些对性能问题的影响因素：

• 页面较大则缺页率较低，页面较小则缺页率较高。页面较小会减少碎片，但导致页表较长占用更多内存，页面较大时相反
  
• 物理块越多，缺页率越低，但达到一个阈值时改善就会变得不明显
  
• 换出已修改过的页面时，应当写回磁盘，如果每当一个页面被换出时就将它写回磁盘，那么每换出一个页面就需要启动一次磁盘，效率极低。为此在系统中建立一个已修改换出页面的链表，对每个要被换出的页面(已修改)，可以暂不将它们写回磁盘，而将它们挂在该链表上，仅当被换出页面数达到给定值时，才将它们一起写回磁盘，这样就可显著减少磁盘I/O的次数，即减少巳修改页面换出的开销。此外，如果有进程在这批数据还未写回磁盘时需要再次访问这些页面，就不需从外存调入，而直接从已修改换出页面链表上获取，这样也可以减少页面从磁盘读入内存的频率，减少页面换进的开销
  
• 编写程序的局部化程度越高，执行时的缺页率就越低。如果存储采用的是按行存储，访问时就要尽量采用相同的访问方式，避免按列访问造成缺页率过高的现象

内存映射

内存映射文件(Memory-MappedFiles)
将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，而不必执行文件I/O操作，也无须对文件内容进行缓存处理。可通过共享页表实现
系统内存中的所有页面都由虚拟存储器负责管理，虚拟存储器以统一的方式处理所有磁盘I/O.当进程退出或显式地解除文件映射时，所有被改动的页面会被写回磁盘文件。
多个进程允许并发地内存映射同一文件，以便允许数据共享。实际上，很多时候，共享内存是通过内存映射来实现的。进程可以通过共享内存来通信，而共享内存是通过映射相同文件到通信进程的虚拟地址空间实现的。内存映射文件充当通信进程之间的共享内存区域，如图3.28所示。一个进程在共享内存上完成了写操作，此刻当另一个进程在映射到这个文件的虚拟地址空间上执行读操作时，就能立刻看到上一个进程写操作的结果。

地址翻译

流程如下：

1. 根据TLB,Cache是否n路组相联，页面大小等，计算出逻辑物理地址的格式
   
2. 根据逻辑地址的标记查找TLB(注意是否分组)以及页表(注意是否有效)
   
3. 拼接出物理地址，根据该地址查找Cache和主存(如果Cache不命中)

• 虚存的最大容量<=计算机的地址位数能容纳的最大容量 && <=内外存之和
  
• 置换页时，把需要调入页的内容放到被换出的页的页框里，也就是页框号不变
  
• 页缓冲队列将被淘汰的页面缓存下来，暂时不写回磁盘，队列长度会影响页面置换的速度，但不会影响缺页率
  
• 处理缺页中断不包括访问调入的页内容，因此处理后从头开始访存
  
• 高级页表指的是最高几位表示的页表，也就是说一级页表是可以直接查到页框号的页表

---

文件管理

概念

文件(File)是以硬盘为载体的存储在计算机上的信息集合
文件的结构:

1. 数据项。是文件系统中最低级的数据组织形式，可分为以下两种类型：
   1. 基本数据项。用于描述一个对象的某种属性的一个值，是数据中的最小逻辑单位。
      
   2. 组合数据项。由多个基本数据项组成。
      
2. 记录。是一组相关的数据项的集合，用于描述一个对象在某方面的属性。
   
3. 文件。是指由创建者所定义的、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相似的记录组成，如一个班的学生记录；而无结构文件则被视为一个字符流，比如一个二进制文件或字符文件。

文件属性，一般用文件控制块(FCB)维护

1. 名称，一般唯一
   
2. 类型
   
3. 创建者
   
4. 所有者
   
5. 位置(指针)
   
6. 大小
   
7. 保护(访问控制信息)
   
8. 时间，包括创建，最后修改，最后存取等

FCB
文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构,FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。

FCB主要包含以下信息：

• 基本信息，如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
  
• 存取控制信息，包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
  
• 使用信息，如文件建立时间、上次修改时间等。

索引节点

有的系统为了便于检索，采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称i结点(inode)

• 磁盘索引结点，存放在磁盘上的索引节点，每个文件有一个唯一的磁盘索引结点
  • 文件主标识符，表示拥有文件的个人或者用户组
    
  • 文件类型，如linux的目录和普通文件
    
  • 文件存取权限
    
  • 物理地址
    
  • 长度
    
  • 链接计数
    
  • 存取时间
    
• 内存索引结点，存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点复制到内存的索引结点中，便于以后使用。在磁盘结点的基础上增加了：
  • 索引结点编号
    
  • 状态,是否上锁或被修改
    
  • 访问计数，记录正在访问此结点的进程数量
    
  • 逻辑设备号，所属文件系统的逻辑设备号
    
  • 链接指针，指向空闲链表和散列队列的指针

操作

对文件的基本操作

1. 创建文件：
   1. 分配外存空间
      
   2. 创建目录项
      
2. 写文件，需要执行系统调用，需要搜索目录找到相关目录项，每个文件维护一个写指针，写后更新,如需要互斥写，可通过系统调用加锁
3. 读文件，需要执行系统调用，类似写文件也需要一个读指针，读后更新，对只用到一个文件的进程这两个指针可以共用
   
4. 重新定位文件，也称文件定位，搜索目录找到适当条目，并将目前文件位置指针重定位到给定值，只涉及目录
   
5. 删除，找到目录项，释放空间，删除目录条目
   
6. 截断，文件所有属性不变，空间释放，长度置零

文件打开和关闭
操作系统维护一个包含所有打开文件信息的表(打开文件表)。打开操作时，通过系统调用open，搜索目录找到该文件，将其复制到内存打开文件表的一个表目，将该表目索引返回给用户。
这样对打开文件可以用打开文件表快速索引，关闭时通过系统调用close，删除打开文件表的条目

在多个不同进程可以同时打开文件的操作系统中，通常采用两级表：整个系统表和每个进程表。
整个系统的打开文件表包含FCB的副本及其他信息。每个进程的打开文件表根据它打开的所有文件，包含指向系统表中适当条目的指针。对通过open打开同一文件的其他进程，只需要增加文件打开表的一个条目与相应的指针。
一般每个文件在系统打开表中有一个打开计数器，通过open和close增减，归零时允许删除

对于访问打开文件表的索引，UNIX称之为文件描述符，而Windows称之为文件句柄。只要文件未被关闭，所有文件操作就通过打开文件表来进行

每个打开文件都具有如下关联信息：

• 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
  
• 文件打开计数。归零时才可以删除文件打开条目
  
• 文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中能提高效率
  
• 访问权限。每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)。操作系统根据该信息允许或拒绝后续的I/O请求

文件保护和权限

文件保护通过口令保护、加密保护和访问控制等方式实现，相关权限可分为以下几种：

• 读
  
• 写
  
• 执行
  
• 添加，相当于编程中的append操作
  
• 删除
  
• 列表清单，列出文件信息

最普遍的访问控制机制，为每个文件和目录增加一个访问控制列表(Access-Control List, ACL)放在FCB或者索引结点,以规定每个用户名及其所允许的访问类型。这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预计并且可能导致复杂的空间管理
精简的访问列表采用拥有者、组和其他三种用户类型。

1. 拥有者。创建文件的用户。
   
2. 组。一组需要共享文件且具有类似访问的用户。
   
3. 其他。系统内的所有其他用户。

其他的访问控制方法：

• 口令，用户在建立文件时提供一个口令，建立fcb时附上口令，其他用户访问时需要提供口令，缺点是口令存储在系统中不安全
  
• 密码，用密码对文件加密，访问需要密钥，有一定的加密解密成本

此外，目录由于涉及递归的子目录，需要不同的保护机制

逻辑结构

按逻辑结构，文件可划分为无结构文件和有结构文件两大类。

• 无结构文件(流式文件)，无结构文件将数据按顺序组织成记录并积累、保存
  
• 有结构文件(记录式文件)
  • 顺序文件，顺序或者链表存储，分为没有关键字排序的串结构和按关键字排序的顺序结构
    
  • 索引文件，建立一张索引表，为主文件的每个记录在索引表中分别设置一个表项，包含指向变长记录的指针(即逻辑起始地址)和记录长度，索引表按关键字排序，因此其本身也是一个定长记录的顺序文件。
    
  • 索引顺序文件,将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一条记录建立一个索引项，其中含有该记录的关键字值和指向该记录的指针。见附图
    
  • 直接或者散列文件，直接用哈希产生的键值对储存地址

物理结构

常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。

• 连续分配,每个文件在磁盘上占有一组连续的块,逻辑文件中的记录也顺序存储在相邻接的块中,目录项中的物理地址只需要包括第一块地址和区域长度
  • 难以动态增加
    
  • 删除和插入记录时性能消耗较大
    
  • 反复增删会产生外部碎片
    
  • 难以确定文件最后需要分配的空间大小
    
• 链接分配
  • 隐式链接，目录项中含有文件第一块的指针和最后一块的指针,一个盘块有链接下一个盘块的指针，只能顺序访问，缺点是容易丢失，可以通过将若干盘块组合成簇来改进(会增加内部碎片)
    
  • 显式链接，把用于链接文件各物理块的指针，从每个物理块的末尾中提取出来，显式地存放在内存的一张链接表中，称为文件分配表FAT,可以用一个特殊的数字-1表示文件的最后一块，可以用-2表示这个磁盘块是空闲的,FAT表在系统启动时就会被读入内存，因此查找记录的过程是在内存中进行的
    
• 索引分配，将每个文件所有的盘块号都集中放在一起构成索引，每个文件有索引块，其第i条目的指针指向文件第i块，这样没有外部碎片，但增加了存储开销
  • 链接索引块来减少开销
    
  • 多层索引来支持更大文件
    
  • 混合索引，见下文

• 对于小文件，为了提高对众多小文件的访问速度，将它们的每个盘块地址直接放入FCB,这样就可以直接从FCB中获得该文件的盘块地址，即为直接寻址。
  
• 对于中型文件，可以采用单级索引方式，需要先从FCB中找到该文件的索引表，从中获得该文件的盘块地址，即为一次间址。
  
• 对于大型或特大型文件，可以采用两级和三级索引分配方式。UNIX系统采用的就是这种分配方式

unix的inode

• 直接地址，在索引结点中可设置10个直接地址项，小于10个盘块的文件可以直接寻址
  
• —次间接地址，i.addr(l0)提供一次间接地址,存放的是索引表，所有一级寻址索引表可存放1024个盘块号，假设一个盘块4kB,允许文件长达4MB
  
• 多次间接地址。当文件长度大于4MB + 40KB (一次间接地址与10个直接地址项)时，系统还需采用二次间接地址分配方式。用地址项i.addr(ll)提供二次间接地址，允许文件最大长度可达4GB，以此类推

疑难梳理：
文件：信息的集合，在操作系统中文件由一系列的目录项FCB管理。
目录项可包括文件的大部分信息，但目录项最重要的功能是提供文件名以便查询，因此目录项可以只存放文件名与一个索引结点号或物理簇号，一般索引结点用于存放描述信息。同时，目录项可以集中存放在一些物理簇上便于查询
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件
操作系统中的文件夹，实际上是一种目录文件，目录文件只存放目录项FCB,可以通过目录文件的FCB调取到目录文件

物理存放上，可分为：

• 连续存放，此时FCB或者索引结点可以用(起始块号,块数)的形式描述文件物理地址
  
• 隐式链接，目录项需要记载起始结束块号或者指针，涉及到的每个磁盘块有指向下一块的指针(指针大小不计入文件大小)
  
• 显式链接，一个磁盘设置一张文件分配表FAT，常驻内存，由于表项等长，物理块号(表项的索引)可以等长,访问第i块可以查表，避免低速的IO(随机访问)
  
• 索引表，每个文件需要索引表，存放在特定物理簇，称为索引块，与数据块区分，FCB(或者索引结点)需要记录索引块号，索引块可以链接，可以分层，可以像linux一样混合在inode里

文件操作：

1. 创建(create系统调用)
   1. 找到足够的空闲硬盘块
      
   2. 根据路径找到创建目录的目录文件，为其增加一个目录项
      
2. 删除(delete)
   1. 找到目录项，根据物理块信息回收磁盘
      
   2. 删除目录项(在上级目录的目录文件里)
      
3. 打开(open)
   1. 找到目录项，检查用户是否有足够权限
      
   2. 将目录项调入内存的打开文件表，返回用户的是对应表项的编号，不需要调入文件内容(分为进程和系统，系统中的表项有打开计数，进程中链接到系统的表项，并且进程有自己的读写指针)
      
4. 关闭(close)
   1. 删除进程的打开文件表项
      
   2. 回收内存
      
   3. 系统打开文件表项，打开计数器减一，若为0删除
      
5. 读(read)
   1. 根据读写指针，读入长度，读后数据存放位置进行读命令
      
6. 写(write)
   1. 类似读命令

注意：(进程)打开文件表的索引号也叫文件描述符(句柄)，读写时用描述符即可指定文件，无需访问外存的文件名

文件共享：

• 硬链接：目录文件的目录项只提供文件名和索引结点指针(硬盘块号)，索引节点维护打开计数，链接到同一个索引节点的两个目录项共享一个索引节点表示的文件
  
• 软链接：一种类型为Link的文件，内容包括链接文件的路径，可以用这个路径检索到对应文件，但除此以外和链接文件无关，根据路径寻找发现无效后删除

目录

FCB的有序集合称为目录，FCB则是目录项
目录管理的基本要求：按名存取,访问控制，不同用户对不同文件采用相同的名字，性能较好等

目录结构

1. 单级目录，当访问一个文件时，先按文件名在该目录中查找到相应的FCB，建立新文件时需要先确保没有重名再新增一个目录项
   
2. 两级目录，分为主文件目录MDF和用户文件目录UFD,主文件目录项记录用户名及相应用户文件目录所在的存储位置。用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD，这样解决了重名问题
   
3. 树形目录(最普遍)，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成，分为绝对路径(根目录开始)和相对路径(当前目录开始)，一般操作系统提供一条专门的系统调用，供用户随时改变
   
4. 无环图目录结构,每个共享结点设置一个共享计数器,归零才可以删除，对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见

目录操作

• 搜索
  
• 创建文件，新增目录项
  
• 删除文件，删除目录项
  
• 创建目录
  
• 删除目录，分为可删除非空目录和不可删除，后者需要递归删除目录中文件和目录
  
• 移动目录
  
• 显示目录
  
• 修改目录属性
  目录一般有哈希表和线性表两种实现

文件共享

• 基于索引结点的共享方式(硬链接)：文件属性等信息，不再放在目录项中，而放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还应有一个链接计数count,用于表示链接到本索引结点(即文件)上的用户目录项的数目。
  
• 利用符号链实现文件共享(软链接)：为使用户B能共享用户A的一个文件F,可以由系统创建一个LINK类型的新文件，也取名为F,并将该文件写入用户B的目录中，系统看到要读的文件是LINK类型，则根据该文件中的路径名去找到文件F,然后对它进行读。只有文件主才拥有指向其索引结点的指针。而共享该文件的其他用户只有该文件的路径名，当文件主把一个共享文件删除后，若其他用户又试图通过符号链去访问它时，则会访问失败，于是将符号链接删除,缺点是增加I/O开销与一定的空间开销
  
• 两个进程同时对同一个文件进行操作，这样的共享称为动态共享

硬链接的查找速度要比软链接的快

• n条记录的平均查找次数是(1+n)/2
  
• 索引分配下文件最大等于(索引总数*文件块大小)
  
• 对文件修改后需要写回操作
  
• 提前读(将可能访问盘块读入内存)和延迟写(对文件的修改先写入缓冲区以便高速读取，缓冲不够才写入文件)，硬盘高速缓存和连续分配空间都可以提高文件访问速度
  
• 平均访问硬盘块数=每个访问项需要的访问次数之和/访问项总数
  
• 读和写各自算一次访问io,例如移动记录这种操作需要两次访问io
  
• 文件最大长度只计算数据部分，需要减去链接指针占用大小
  
• 符号链接无法感知链接文件的状态，引用计数保持不变
  
• 进程的读/写指针记录了该进程对文件的读/写操作进行到的位置，独属于进程
  
• 文件描述符是进程各自的用户打开文件表项的索引号
  
• FAT的每个表项中存放下一个簇号,且连续存放，访问特定地址时可以计算要访问的是第几个地址块，从而查表直接找到其物理块号
  
• 文件系统的文件索引结点数决定可存放的文件数，一个索引结点的地址项数量和性质以及簇可存放的地址项数量决定一个文件的最大长度
  
• 打开文件指的是将其目录项读入内存，且写入打开文件表，不包括将其内容调入内存

文件系统

图中：

• 基本文件系统：向相应设备驱动程序发生命令，读写磁盘的物理块；管理内存缓冲区，存文件系统需要的缓存
  
• 文件组织模块：组织文件及其逻辑和物理块，并进行逻辑物理块的转换；空闲空间管理器，跟踪未分配的块
  
• 逻辑文件系统，管理元数据，即文件系统的所有结构，但不包括实际数据，本质上通过FCB实现；文件保护

布局

1. 主引导记录(Master Boot Record, MBR),位于磁盘的0号扇区，用来引导计算机，MBR后面是分区表，该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区，当计算机启动时，BIOS读入并执行MBR。MBR做的第一件事是确定活动分区，读入它的第一块，即引导块。
   
2. 引导块(boot block), MBR执行引导块中的程序后，该程序负责启动该分区中的操作系统。为统一起见，每个分区都从一个引导块开始，即使它不含有一个可启动的操作系统,也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。除了从引导块开始，磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如图4.18所列的一些项目。
   
3. 超级块(super block),包含文件系统的所有关键信息，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
   
4. 文件系统中空闲块的信息，可以使用位示图或指针链接的形式给出。后面也许是一组i结点，每个文件对应一个结点，i结点包含文件属性。也可能是根目录，它存放文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件

在内存中的结构

内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载，在文件系统操作期间被更新，在卸载时被丢弃。可能包括：

1. 内存中的安装表(mounttable),包含每个已安装文件系统分区的有关信息。
   
2. 内存中的目录结构的缓存,包含最近访问目录的信息。对安装分区的目录，它可以包括一个指向分区表的指针。
   
3. 整个系统的打开文件表，包含每个打开文件的FCB副本及其他信息。
   
4. 每个进程的打开文件表，包含一个指向整个系统的打开文件表中的适当条目的指针，以及其他信息

创建文件的流程

1. 进程调用逻辑文件系统
   
2. 逻辑文件系统分配一个FCB
   
3. 系统将新目录读入内存，用文件名和FCB更新，并写回磁盘

打开文件的流程：

1. 调用Open，文件名传给逻辑文件系统
   
2. 搜索系统的打开文件表
   1. 如果有其他进程使用，则现在进程的打开文件表设置条目指向系统的打开文件表相应表项
      
   2. 如果这个文件尚未打开，则根据文件名搜索目录结构，找到后复制其FCB到系统打开文件表，进程的打开文件表项增设条目指向系统的表项，通过指针将整个系统打开文件表的条目与其他域相连
      
3. 返回一个指向单个进程的打开文件表中的适当条目的指针，文件操作将用该指针进行

关闭文件的流程：

1. 删除单个进程打开文件表中的相应条目，整个系统的打开文件表的文件打开数量也会递减
   
2. 当所有打开某个文件的用户都关闭该文件后，任何更新的元数据将复制到磁盘的目录结构中，并且整个系统的打开文件表的对应条目也会被删除

外存管理

磁盘可以划分成分区，这是单纯对硬件的划分，而文件系统却是软件层面的概念，因此一个有文件系统的分区才能实际使用，称为卷，卷对应硬件上的存储，不局限于具体设备  
卷中的文件数据和FCB是分离的(汝,似为分离而生),现代操作系统往往有很多文件管理模块，通过它们可以访问不同格式卷的文件  
卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放卷信息的超级块  
文件存储设备管理实质上是对空闲块的组织管理，过程中以块为单位交换信息

引导信息是一系列可以加载到内存中的连续块，加载到内存后从其第一条代码开始执行，引导程序便启动一个具体的操作系统。引导块之后是超级块，它存储文件系统的有关信息,随后是多个索引结点,索引结点中包含多个指针，指向属于该文件的各个数据块。最后是文件数据块
文件系统在进程使用前必须先安装，也称挂载

• Windows系统维护一个扩展的两级目录结构，用驱动器字母表示设备和卷，卷具有常规树结构的目录，与驱动器号相关联，每个卷有自己的文件系统
  
• UNIX使用系统的根文件系统，由内核在引导阶段直接安装,也可以后续用脚本或者用户命令安装在已有文件系统的目录下，作为一个目录树，每个文件系统都拥有自己的根目录。安装文件系统的这个目录称为安装点，安装就是将磁盘分区挂载到该安装点下，进入该目录就可以读取该分区的数据。己安装文件系统属于安装点目录的一个子文件系统。

1. 空闲表法，每个文件分配一块连续空间，系统为所有空闲区建立空闲表，和表项一一对应，空闲区的分配类似内存分配，可以用首次/最佳适应等，不适用大型系统
   
2. 空闲链表法，所有空闲盘区组成一个链表，不适用大型系统
   1.  空闲盘块链，分配文件从链首裁剪，回收空间插入到链尾，但这样的链会很长
      
   2. 空闲盘区链，盘区可以包括若干盘块，每个盘区包括自己盘块数的信息，一般用首次适应分配，和第一个相反，分配回收较复杂，效率较高
      
3.  位示图法，用二进制的一位表示一个盘块使用情况，比如0表示空，1表示已分配，分配过程是：
   1.  顺序扫描位示图，找出足够的0位
      
   2.  将找到的二进制位，转换成对应盘块号b，b = n(i-1) +j,ij是坐标，n是每行位数
      
   3.  修改位示图,map[i,j]=1
      
   4.  回收时,j = (b-1)DIVn+ 1  j = (b-1) MODn+ 1并修改map[i,j]=0
      
4.  成组链接法(UNIX使用)，把顺序的n个空闲盘块号保存在第一个成组链块中，其最后一个空闲盘块(作为成组链块)则用于保存另一组空闲盘块号，系统只需保存指向第一个成组链块的指针，分配与回收过程：
   1.  根据第一个成组链块的指针，将其对应的盘块分配给用户
      
   2.  指针后移，如果指向最后一个盘块，就把下一组读入内存，指针指向其开头
      
   3.  回收时，成组链块的指针上移一格，再记入回收盘块号。当成组链块的链接数达到n时，表示己满，便将现有已记录n个空闲盘块号的成组链块号作为新链块记入新回收的盘块
      
   4.  表示空闲空间的位向量表或第一个成组链块，以及卷中的目录区、文件区划分信息都要存放在磁盘中，一般放在卷头位置，在UNIX系统中称为超级块。在对卷中的文件进行操作前，超级块需要预先读入系统空闲的主存，并且经常保持主存超级块与磁盘卷中超级块的一致

虚拟文件系统VFS

VFS提供文件系统的统一接口，使用者不需要关注具体实现  
为了实现VFS, Linux主要抽象了四种对象类型。每个VFS对象都存放在一个适当的数据结构中，其中包括对象的属性和指向对象方法(函数)表的指针。

• 超级块对象：表示一个己安装(或称挂载)的特定文件系统。
  
• 索引结点对象；表示一个特定的文件。
  
• 目录项对象：表示一个特定的目录项。
  
• 文件对象：表示一个与进程相关的已打开文件

linux中有一切皆文件的说法，这也包括目录，特定地说：

• 超级块对象：对应文件系统的超级块，存储文件系统的元信息
  
• 索引节点对象：文件系统处理文件所需要的所有信息，都放在一个称为索引结点的数据结构中，索引结点对文件是唯一的。只有当文件被访问时，才在内存中创建索引结点对象，这个对象有个修改状态字，用于更新
  
• 目录项对象：目录项对象是一个路径的组成部分，它要么是目录名，要么是文件名;例如'/test'中'/'和'test'都是这种对象
  
• 文件对象：文件对象代表进程打开的一个文件，一个文件可以对应出多个文件对象，它对应一个唯一的索引节点和目录项，包含一些文件的必要信息

物理存储中，不同文件系统的目录项，索引结点等也不同，VFS用统一的vnode表示文件，只运行在内存中(与inode不同的是inode可以存在外存)
VFS还有另一个重要作用，即提高系统性能。最近最常使用的目录项对象被放在目录项高速缓存的磁盘缓存中，以加速从文件路径名到最后一个路径分量的索引结点的转换过程,VFS并不是一种实际的文件系统，它只存在于内存中

新分区(文件系统)的挂载：

1. VFS注册新的文件系统，放在内存的挂载表中
   
2. 文件系统提供一个函数地址列表
   
3. 将分区挂载在特定的一个目录下

---

I/O设备

概念

分类

1. 块设备，信息交换以数据块为单位，属于有结构设备，如磁盘，传输的数据有结构,可寻址(随机读写)
   
2. 字符设备，信息交换以字符为单位，属于无结构设备，如打印机，不可寻址

或者按传输速率分：

1. 低速设备，每秒数百字节或以下，如键鼠
   
2. 中速设备，数万字节或以下，如打印机
   
3. 高速设备，数百千字节或更高，如磁盘

I/O接口(设备控制器)：

根据cpu命令和设备状态协调两者工作

• 设备控制器与cpu接口，分为数据，地址，控制线，数据线一般和数据寄存器与控制/状态寄存器相连
  
• 设备控制器与设备接口，可能有多个设备的多个接口，每个都有数据，控制，状态类型的信号
  
• I/O逻辑，通过控制线与cpu交互，对cpu发来的命令译码，CPU启动设备时，将启动命令发送给控制器，同时通过地址线把地址发送给控制器，由控制器的I/O逻辑对地址进行译码，并相应地对所选设备进行控制。

主要作用：

• 接受识别cpu命令
  
• 数据交互，设备主存控制器三者交互
  
• 识别报告设备状态
  
• 地址识别
  
• 数据缓冲
  
• 差错控制

I/O端口
指设备控制器中可被cpu直接访问的寄存器，主要有以下三类：

• 数据寄存器，实现cpu和外设之间的数据缓冲
  
• 状态寄存器，获取执行结果和设备的状态信息
  
• 控制寄存器，cpu写入，对设备进行操作，如启动或更改模式

cpu和io端口的通信方式：

• 独立编址，每个端口分配一个端口号，只有操作系统可以用特殊io指令访问这些端口
  
• 统一编址(内存映射I/O)，每个端口分配唯一的内存地址，这部分内存被该端口独占，地址通常靠近地址空间顶端

控制方式

1. 程序直接控制，cpu对外设状态循环检查，直到确定从i/o设备读取的字已经在io控制器的数据寄存器中，缺点是cpu利用率低下
   
2. 中断驱动，允许I/O设备中断cpu，会消耗较多的CPU时间，流程如下
   1. cpu发送指令，如读，保存需要io的当前程序上下文，继续下一个作业
      
   2. i/o控制器接受指令后，读数据存入数据寄存器后通过控制线发送中断信号
      
   3. cpu收到中断信号，进行中断处理，对控制器发出取请求
      
   4. 控制器把数据放到数据总线，i/o控制器的操作完成
      
   5. cpu存入寄存器，随后存入主存，恢复发出I/O请求的程序继续运行
      
3. DMA方式，在I/O设备和内存之间设置数据交换通路，中断方式在每个数据需要传输时中断CPU,而DMA方式则是在所要求传送的一批数据全部传送结束时才中断CPU(缺点是对离散的数据块请求仍需要较多cpu占用)
   1. 特点
      1. 基本单位是数据块
         
      2. 数据直接在设备与内存之间传输
         
      3. 传输数据块的开始和结束时需要cpu干预，传输过程由dma控制器操纵
         
   2. 寄存器
      1. 命令/状态寄存器CR，接受i/o命令，控制状态信息
         
      2. 内存地址寄存器MAR,分别在输入输出时存放设备到内存和内存到设备的内存起始地址
         
      3. 数据寄存器DR，暂存交换的数据
         
      4. 数据计数器DC，存放传输数据的字数或者字节数
         
   3. 工作流程
      1. cpu接受io设备的dma请求，向dma控制器发送命令，设置MAR,DC初值，继续其他工作
         
      2. DMA与主存交换数据，每次一个字，结束后发送中断信号
         
      3. cpu进行中断处理
         
4. 通道控制，在内存设置通道，一个通道可以控制多个设备的内存交换，结束后中断cpu(通道只需要cpu简单地初始化，就可以控制一组数据块的传输，并行度最高，硬件成本也最高)通道没有自己的内存，程序存在主存

I/O软件层次

将系统中的设备管理模块分为若干个层次,每层都是利用其下层提供的服务，每层都只有接口与其他层面交互，屏蔽具体细节

1. 用户层，用户可以调用相关库函数，对设备进行操作，最终一般会用系统调用来获取系统服务
   
2. 设备独立性(无关性)软件，用于实现用户程序与设备驱动器的统一接口、设备命令、设备的保护及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间
   1. 应用程序独立于具体的物理设备，用逻辑设备名请求设备，系统执行时映射成物理设备，这样可以灵活分配设备，并易于实现I/O重定向(即物理设备可以随意更换)、
      
   2. 主要功能：
      1. 执行所有设备的公有操作，分配回收，逻辑映射，访问控制，缓冲差错控制等
         
      2. 对用户或文件层提供统一接口，r/w等
         
3. 设备驱动程序，负责具体实现系统对设备发出的操作指令，设备驱动程序向上层用户程序提供一组标准接口，向下发送命令给设备控制器，并接受其信号发送给软件
   
4. 中断处理，用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完毕再恢复被中断进程的现场后，返回到被中断进程。
   1. 主要任务：进程上下文切换，读取设备状态，修改进程状态等

设备独立性软件,设备驱动程序，中断处理程序是操作系统内核部分，称为IO系统或者IO核心子系统

一次标准I/O操作流程：

1. 通过用户层软件发送io相关的指令
   
2. 独立软件进行解析，一般转换成通用命令，发送给驱动程序
   
3. 驱动程序根据设备具体实现这个命令
   
4. 中断当前运行进程，由硬件开始执行命令

应用程序接口

I/O系统与更高层的接口

1. 字符设备接口，字符设备是指数据的存取和传输是以字符为单位的设备，一般不可寻址，中断驱动，需要互斥操作。通常为字符设备建立一个字符缓冲区，用户程序通过get操作从缓冲区获取字符，通过put操作将字符输出到缓冲区。并用一个通用的in-control指令处理
   
2. 块设备接口，块设备是指数据的存取和传输是以数据块为单位的设备，如磁盘，一般可寻址，常使用dma
   1. 块设备接口将磁盘的所有扇区从0到依次编号，这样，就将二维结构变为一种线性序列。
      
   2. 把上层的打开关闭读写等抽象命令转换成设备识别的底层命令
      
   3. 内存映射接口通过内存的字节数组来访问磁盘，而不提供读/写磁盘操作。映射文件到内存的系统调用返回包含文件副本的一个虚拟内存地址。只在需要访问内存映像时，才由虚拟存储器实际调页
      
3. 网络设备接口，一般使用网络套接字接口，套接字接口的系统调用使应用程序创建的本地套接字连接到远程应用程序创建的套接字，通过此连接发送和接收数据。
   
4. 阻塞/非阻塞I/O
   1. 阻塞I/O是指当用户进程调用I/O操作时，进程就被阻塞，需要等待I/O操作完成，进程才被唤醒继续执行，更加常见
      
   2. 非阻塞I/O是指用户进程调用I/O操作时，不阻塞该进程，该I/O调用返回一个错误返回值，通常，进程需要通过轮询的方式来查询I/O操作是否完成。

• I/O管理的主要功能：状态跟踪，设备存取，分配(多用户)，控制
  
• 共享设备必须是可寻址的和可随机访问的设备
  
• 虚拟设备是指采用虚拟技术将一台独占设备转换为若干逻辑设备
  
• 通道控制设备控制器、设备控制器控制设备工作
  
• 所有设备的启动工作都由系统统一来做
  
• 首先获得中断驱动的io设备(如键盘)输入信息的是中断程序
  
• dma每传送一个字都需要中断处理

设备独立性软件

与设备无关的软件是I/O系统的最高层软件，一般用于执行所有设备公有操作

高速缓存和缓冲区

磁盘高速缓存
利用内存中的存储空间来暂存从磁盘中读出的一系列盘块中的信息。因此，磁盘高速缓存逻辑上属于磁盘，物理上则是驻留在内存中的盘块。
在内存中分为两种形式：

• 在内存中开辟一个单独的空间作为磁盘高速缓存，大小固定；
  
• 是未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘I/O时共享。

缓冲区

引入缓冲区的目的主要如下：

1. 缓和CPU与I/O设备间速度不匹配的矛盾。
   
2. 减少对CPU的中断频率，放宽对CPU中断响应时间的限制。
   
3. 解决基本数据单元大小(即数据粒度)不匹配的问题。
   
4. 提高CPU和I/O设备之间的并行性。

硬件缓冲器出于成本较少用，内存设置缓冲区是更常见的情况
假定从磁盘把一块数据输入到缓冲区的时间为T,操作系统将该缓冲区中的数据传送到用户区的时间为M,而CPU对这一块数据处理的时间为C。

单缓冲
初始状态为：工作区是满的，缓冲区是空的。一般认为二者大小相等
单缓冲区处理每块数据的用时为max(C, T)+M

双缓冲
单缓冲中CPU在M时间空闲，所以引入双缓冲
先装填到缓冲区1,在缓冲区1填满后才开始装填缓冲区2,与此同时处理机可以从缓冲区1中取出数据送入用户进程，当缓冲区1中的数据处理完后，若缓冲区2己填满，则处理机又从缓冲区2中取出数据送入用户进程，而I/O设备又可以装填缓冲区1
初始状态：工作区是空的，其中一个缓冲区是满的，另外一个缓冲区是空的

• 假设T>C+M,满的区传送数据，空区充入数据，C+M后数据处理完，但新的数据还没冲入，需要等到T才能回到初始状态
  
• 假设T<C+M,T后空区被冲满，但原数据没有处理完，需要等到C+M
  
• 若M+C<T,则可使块设备连续输入；若C+M>T,则可使CPU不必等待设备输入

综上，处理一块数据周期需要时间是max(C + M, T)。

为了实现双向数据传输，必须在两台机器中都设置两个缓冲区，一个用作发送缓冲区，另一个用作接收缓冲区

循环缓冲
包含多个大小相等的缓冲区,每个有一个指向下个区的指针，构成一个循环链表
需要有两个指针in和out，in指向第一个空区，out指向第一个满区

缓冲池
由多个系统公用的缓冲区组成，缓冲区按其使用状况可以形成三个队列：空缓冲队列、装满输入数据的缓冲队列(输入队列)和装满输出数据的缓冲队列(输出队列)。
以及四种缓冲区：

• 用于收容输入数据的工作缓冲区
  
• 用于提取输入数据的工作缓冲区
  
• 用于收容输出数据的工作缓冲区
  
• 用于提取输出数据的工作缓冲区
  
  当输入进程需要输入数据时，便从空缓冲队列的队首摘下一个空缓冲区，把它作为收容输入工作缓冲区，然后把输入数据输入其中，装满后再将它挂到输入队列队尾。当计算进程需要输入数据时，便从输入队列取得一个缓冲区作为提取输入工作缓冲区，计算进程从中提取数据/数据用完后再将它挂到空缓冲队列尾。当计算进程需要输出数据时，便从空缓冲队列的队首取得一个空缓冲区，作为收容输出工作缓冲区，当其中装满输出数据后，再将它挂到输出队列队尾。当要输出时，由输出进程从输出队列中取得一个装满输出数据的缓冲区，作为提取输出工作缓冲区，当数据提取完后，再将它挂到空缓冲队列的队尾。
  类似一个循环流水线，一个装瓶，一个把瓶子里的原料用掉

两者比较

设备分配与回收

设备分配是指根据用户的I/O请求分配所需的设备。需要充分利用设备又不导致进程死锁

设备的分类

• 独占设备，分配给进程后独占，直到释放
  
• 共享设备，多个进程可共用的设备
  
• 虚拟设备，SPOOLing(假脱机)技术实现了虚拟设备功能，可以将设备同时分配给多个进程。这种技术实质上就是实现了对设备的I/O操作的批处理。

数据结构
设备分配依据的主要数据结构有设备控制表(DCT)、控制器控制表(COCT)、通道控制表(CHCT)和系统设备表(SDT)

• 一个设备控制表就表示一个设备，而这个控制表中的表项就是设备的各个属性,凡因请求本设备而未得到满足的进程，其PCB排成一个设备请求队列，设备队列的队首指针指向该请求队列队首PCB。
  
• COCT需要一个通道服务，因此存放一个CHCT的指针
  
• CHCT可以服务多个设备，因此存放一个设备控制器表的首地址
  
• SDT存储系统连接到的设备，是唯一的
  
  

设备分配的过程:

1. 分配设备:首先根据I/O请求中的物理设备名，查找SDT,从中找出该设备的DCT,再根据DCT中的设备状态字段，可知该设备的状态。若忙，则将进程PCB挂到设备等待队列中：若不忙，则根据一定的策略将设备分配给该进程
2. 分配控制器:设备分配后，根据DCT找到COCT,查询控制器的状态。若忙，则将进程PCB挂到控制器等待队列中；若不忙，则将控制器分配给该进程。
3. 分配通道:控制器分配后，根据COCT找到CHCT,查询通道的状态。若忙，则将进程PCB挂到通道等待队列中：若不忙，则将通道分配给该进程。只有设备、控制器和通道都分配成功时，这次的设备分配才算成功，之后便可启动设备进行数据传输
4. 可以直接分配物理设备，也可以用类别区分逻辑设备，分配某一类设备

分配策略
需要考虑设备固有属性，分配算法，安全性

• 静态分配：在用户作业执行前，一次性分配其需要的所有设备与控制器，进程独占这些设备与控制器直到终止或撤销，使用效率较低但没有死锁，常用于独占设备
  
• 动态分配：进程执行中根据需求分配，用完立刻释放，效率但可能死锁，常用于共享设备
  
• 常见的分配算法：先请求先分配，优先级等
  
• 每当进程发出I/O请求后便进入阻塞态，直到其I/O操作完成时才被唤醒，这样破坏了占有并等待条件，不会产生死锁，是一种安全的分配，但效率较低，不能并行
  
• 进程在发出I/O请求后仍继续运行，仅当进程所请求的设备已被另一进程占用时，才进入阻塞态，这样不安全，但并行度高

设备独立性
指应用程序独立于具体设备，在应用程序中使用逻辑设备名来请求使用某类设备，在系统中设置一张逻辑设备表LUT，用于将逻辑设备名映射为物理设备名，表项包括逻辑设备名、物理设备名和设备驱动程序入口地址；当进程用逻辑设备名来请求分配设备时，系统为它分配一台相应的物理设备，并在LUT中建立一个表目，当以后进程再利用该逻辑设备名请求I/O操作时，系统通过查找LUT来寻找对应的物理设备和驱动程序

逻辑设备表可以系统中唯一设定(不允许重名)也可以每个用户设置一个，用户登录时建立一个进程，并建立一个LUT放入其PCB

SPOOLing技术(假脱机)

为了缓和CPU的高速与I/O设备低速性之间的矛盾，引入了脱机输入/输出技术，利用专门的外围控制机，将低速I/O设备上的数据传送到高速磁盘上，或者相反

1. 输入井和输出井，分别模拟脱机输入和输出时的磁盘，接受IO设备输入的数据，收容用户程序的输出数据，每个进程的输入输出数据都以文件为单位保存，最后链接成一个输入或者输出队列
   
2. 输入缓冲区和输出缓冲区，用于暂存输入输出过程的数据
   
3. 输入进程和输出进程，模拟脱机输入/输出时的外围控制机，用户请求输入和输出的数据到达井后，可以从输入井读入内存，或者从输出井经过缓冲区到达输出设备

实例：共享打印机
用户进程请求打印，由假脱机进程进行以下工作：

1. 在磁盘缓冲区中为之申请一个空闲盘块，并将要打印的数据送入其中暂存。
   
2. 为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到假脱机文件队列
   软件层面上进程已经完成了输出工作，具体的硬件操作会在之后进行

特点

1. 提高了 I/O的速度，将对低速I/O设备执行的I/O操作演变为对磁盘缓冲区中数据的存取，如同脱机输入/输出一样，缓和了 CPU和低速I/O设备之间的速度不匹配的矛盾
   
2. 将独占设备改造为共享设备，在假脱机打印机系统中，实际上并没有为任何进程分配设备
   
3. 实现了虚拟设备功能，对每个进程而言，它们都认为自己独占了一个设备
   这三部分由预输入程序、井管理程序和缓输出程序管理
   对时间的优化主要体现在，cpu通过内存向磁盘的输入输出井交换数据要快于低速I/O设备，但相对的也会增加空间占用

设备驱动程序接口

每个设备驱动程序与操作系统之间应该有相同或相近的接口，这样便于设备的添加管理和开发
对于每种设备类型，例如磁盘，操作系统都要定义一组驱动程序必须支持的函数，驱动程序中通常包含一张表格，这张表格具有针对这些函数指向驱动程序自身的指针，装载驱动程序时，操作系统记录这个函数指针表的地址，所以当操作系统需要调用一个函数时，它可以通过这张表格发出间接调用。这个函数指针表定义了驱动程序与操作系统其余部分之间的接口。.给定类型的所有设备都必须服从这一要求。
与设备无关的软件还要负责将符号化的设备名映射到适当的驱动程序上。例如，在UNIX中,设备名/dev/disk0唯一确定了一个特殊文件的i结点，这个i结点包含了主设备号(用于定位相应的驱动程序)和次设备号(用来确定要读写的具体设备)
在UNIX和Windows中，设备是作为命名对象出现在文件系统中的，有自己的FCB文件，因此针对文件的常规保护规则也适用于I/O设备。系统管理员可以为每个设备设置适当的访问权限

磁盘和固态硬盘

磁盘

表面涂有磁性物质的物理盘片，盘片旋转，通过磁头读取数据，磁盘盘面上的数据存储在一组同心圆中，称为磁道。每个磁道与磁头一样宽，一个盘面有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小，一个扇区称为一个盘块。
多个盘片垂直堆叠，组成磁盘组，每个盘面对应一个磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动。所有盘片上相对位置相同的磁道组成柱面。扇区是磁盘可寻址的最小单位，磁盘上能存储的物理块数目由扇区数、磁道数及磁盘面数决定
磁盘地址用“柱面号•盘面号•扇区号”表示。

磁盘按不同的方式可分为若干类型：

• 磁头相对于盘片的径向方向固定的，称为固定头磁盘，每个磁道一个磁头；
  
• 磁头可移动的，称为活动头磁盘，磁头臂可来回伸缩定位磁道；
  
• 磁盘永久固定在磁盘驱动器内的，称为固定盘磁盘；
  
• 可移动和替换的，称为可换盘磁盘。

磁盘管理

为了让控制器能进行读写操作，需要把磁盘划分扇区，这被称为低级(物理)格式化，每个扇区的数据结构通常由头尾和中间的数据区完成
低级格式化时，磁盘控制器可以用备用块替换坏块，这种情况坏块对操作系统透明
操作系统需要把数据结构记录到磁盘上，这需要将磁盘分成若干柱面组成的分区(分区的起始扇区和大小记录在主引导记录的分区表)，并且对分区进行逻辑格式化，把文件系统存储到磁盘上
逻辑格式化时屏蔽的坏块可以被操作系统感知
若干相邻扇区会被组合成一簇(linux称为块)，一般簇是文件存储的最小单位,即小于一簇大小的文件也会占用一簇,所以一般对磁盘鼓励减少小文件

计算机启动时，自举程序找到磁盘上的操作系统内核，加载到内存，转到起始地址，一般rom中存放自举程序的装入程序，完整的引导程序放在磁盘启动块上，有启动分区的磁盘称为系统磁盘或者启动磁盘
例如在windows中，0号扇区存放引导代码，称为主引导记录MBR，rom中代码指示系统从MBR读取代码，并根据MBR存放的分区表和引导分区标志读取到引导分区的引导扇区(第一个扇区)

磁盘可能会出现坏块，可以手动处理或者控制器维护屏蔽一个坏块列表，用备用块替换掉

磁盘调度算法

一次磁盘读写操作的时间由寻找(寻道)时间、旋转延迟时间和传输时间决定。

• 寻找时间\(T_s\) ,活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。这个时间除跨越n条磁道的时间外，还包括启动磁臂的时间s,即\(T_s = m\times{n} + s\),式中，m是与磁盘驱动器速度有关的常数，约为0.2ms,磁臂的启动时间约为2ms。
  
• 旋转延迟时间\(T_r\) 磁头定位到某一磁道的扇区所需要的时间，设磁盘的旋转速度为r,\(T_r=\frac{1}{2r}\),典型速度是每分钟5400转
  
• 传输时间\(T_t\)从磁盘读出或向磁盘写入数据所经历的时间，这个时间取决于每次所读/写的字节数b和磁盘的旋转速度：\(T_t=\frac{b}{rN}\)

总平均存取时间可以表示为:\[T_a=T_s+\frac{1}{2r}+\frac{b}{rN}\]

常见的磁盘调度算法：

1. FCFS，较少用
   
2. 最短寻找时间优先SSTF,调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以便使每次的寻找时间最短,可能产生饥饿
   
3. 扫描SCAN (又称电梯调度)，规定磁头运动方向，来回往复地单向扫描，偏向于最里或者最外的磁道
   
4. 循环扫描C-SCAN，在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求
   
5. LOOK和C-LOOK，在扫描算法的基础上，磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点，一般默认是扫描算法的高级替代
   

减少延迟时间
对盘面扇区进行交替编号，对磁盘片组中的不同盘面错位命名。假设每个盘面有8个扇区，磁盘片组共8个盘面
磁盘是连续自转设备，磁头读/写一个物理块后，需要经过短暂的处理时间才能开始读/写下一块。假设逻辑记录数据连续存放在磁盘空间中，若在盘面上按扇区交替编号连续存放，则连续读/写多条记录时能减少磁头的延迟时间；同柱面不同盘面的扇区若能错位编号，连续读/写相邻两个盘面的逻辑记录时也能减少磁头延迟时间。

传输时间被硬件限制，无法优化

固态硬盘

基于闪存技术的存储器，由一个或多个闪存芯片和闪存翻译层组成，闪存翻译层将来自CPU的逻辑块读写请求翻译成对底层物理设备的读写控制信号,相当于扮演了磁盘控制器的角色

固态的主要缺点是闪存擦写寿命有限，需要磨损均衡技术：

1. 动态磨损均衡。写入数据时，自动选择较新的闪存块
   
2. 静态磨损均衡。就算没有数据写入，SSD也会监测并自动进行数据分配，让老的闪存块承担无须写数据的存储任务，同时让较新的闪存块腾出空间，平常的读写操作在较新的闪存块中进行。

• 文件以块为单位存放于磁盘中，文件的读写也以块为单位
  
• 分区在逻辑格式化之前，逻辑格式化是建立文件系统
  
• 默认的scan算法不会调度到最内外的磁道，而是最靠近内外侧的磁道
  
• 包括多个扇区的簇，其物理地址是起始扇区的地址