操作系统2复习

4 5 6 7章节

存储器管理

内存基础知识

程序执行前需要先放到内存中才能被CPU处理（缓解CPU和硬盘之间的速度矛盾）
在多道程序环境下，有多个程序的数据需要同时放入内存中，通过对内存的存储单元编址来区分不同程序的数据在内存中的位置。

内存：地址从0开始，每个地址对应一个存储单元
存储单元大小：按字节编址，存储单元大小为1个字节，即1B；按字编制，存储单元大小为计算机字长
2^10=1K 2^20=1M 2^30=1G

程序的装入和链接

用户程序要在系统中运行，必须先将它装入内存，再将其变为一个可执行程序，通常需要以下步骤

1. 编译：由编译程序（Compiler）对用户源程序进行编译，形成若干目标模块。形成虚拟地址
2. 链接：由链接程序（Linker）对编译后形成的目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块（装入模块就是可执行文件）【形成完成整的逻辑地址】
3. 装入：由装入程序（Loader）将装入模块装入内存【逻辑地址转换为物理地址】

在编译阶段形成虚拟地址，因为链接需要库函数，需要逻辑地址
程序经过编译、链接之后生成的指令中指明的是逻辑地址，即相对于进程起始地址而言的地址

程序的装入

1. 绝对装入：在编译时提前知道程序放在了内存的哪个位置，编译程序将产生绝对地址的目标代码。（绝对地址即物理地址）
   • 只适用于单道程序环境
   • 灵活性差
2. 可重定位装入(静态重定位)：装入时对地址进行“重定位”，将逻辑地址变为物理地址（在装入时一次完成，即装入后的地址不会再改变）。
   • 早期多道批处理
   • 如果已知装入的起始物理地址，就把指令中的地址均加上该地址
   • 特点：在作业装入内存的时候，必须分配其要求的全部内存空间，如果没有足够的内存就不能装入该作业；且作业一旦进入内存，在运行期间就不能再移动，也不能再申请新的内存空间
   • 重定位：指装入时对目标程序中的指令和数据地址的修改过程
   • 静态：进程装入时一次完成，以后不再改变，故称为静态重定位
3. 动态运行时装入（动态重定位）：运行时将逻辑地址转换为物理地址
   • 装入的时候不会立即把逻辑地址转换为物理地址，把地址转换推迟到程序执行的时候进行，需要一个重定位寄存器
   • 允许程序在内存中发生移动

   lff:可重入的程序才能进行动态运行装入；程序的三种装入方式 区别在地址确定的时机。

程序的链接

lff:链接需要库函数，需要逻辑地址；
静态链接：不便于程序共享，相对地址根据模块已经修改好了；一般是动态链接，对应的装入方式，好处：便于共享

1. 静态链接:程序运行之前就把各个目标模块以及它们所需要的库函数链接成一个完整的装配模块，以后不再拆开。
   • 装入模块的时候要对相对地址进行修改
   • 装入模块时要变换外部调用符号的相对地址

   lff:不便于程序共享，相对地址根据模块已经修改好了；

2. 装入时动态链接：边装入边链接，装入一个模块的时候如果出现一个外部模块的调用事件，则装入程序会寻找相应模块并将其装入内存，同时修改相对地址。
   • 便于修改和更新
   • 便于实现对目标模块的共享
3. 运行时动态链接：对某些模块的链接推迟到程序执行时才进行（执行时如果发现被调用模块没有装入内存，则由OS寻找模块并将其装入内存，链接到被调用模块中）
   • 节省大量内存空间（没被用到的模块就不会被调入内存和被链接到装入模块）

连续分配管理方式

连续分配：为用户分配的空间必须是连续空间；只要是采用分区分配，一定都是连续分配的,注意和段式和页式的不同

lff:这几种方法的差别就在于分区的大小是相等还是不等的

单一连续分配

单道程序环境下，内存被分为系统区和用户区，用户区会存放用户进程相关数据，内存中只能有一道用户程序，用户程序独占整个用户空间。

• 实现简单，无外部碎片
• 只能用户单用户单任务OS，有内部碎片（很大一片）

固定分区分配

lff:分区分配的由来：由于多道程序运行的时候有存储保护问题，为了防止各道程序相互干扰，需要将用户空间划分为若干个固定大小的区域，每个分区只装入一道作业，这就是最早的、最简单的一种可运行多道程序的分区式存储管理方式。
支持多道程序系统，将内存划分为固定大小分区，不同分区装入不同作业，每个分区只装入一道作业

• 划分分区方法：
  1. 分区大小相等
     • 缺乏灵活性
     • 方便实用
  2. 分区大小不等
     • 增加灵活性，满足不同大小的作业
• 分区说明表：表中：分区起始地址、大小、状态（是否已分配），实现分区的分配和回收
• 实现简单，无外部碎片
• 缺点：1. 用户程序太大的时候，所有分区都不满足需求，不得不使用覆盖技术解决，导致性能降低；2. 产生内部碎片，内存利用率低

动态分区分配

进程装入内存的时候，根据进程大小动态地建立分区

1. 数据结构
   • 空闲分区表：每个空闲分区占一个表目
   • 空闲分区链：分区起始和末尾部分分别设置前向指针和后向指针
   
2. 动态分区分配算法（下一节）
3. 分区分配操作
   • 分配内存：u请求的分区大小，m每个空闲分区的大小；跟表中的每个空闲分区的大小比较，如果m.size()-u.size()<=size(剩余的部分很小，可不再切割，可以分配)，如果>size，则从该分区划分一块内存空间分配出去，余下的部分留在空闲分区表/链表中。
   • 回收内存：(四种情况)
     • 回收区与插入点前一个空闲分区(F1)邻接=回收区与插入点前一分区合并（向下合并）
     • 回收分区与插入点后一空闲分区(F2)相邻接=回收区与插入点后一分区合并（向上合并）
     • 回收区同时与插入点前后两个分区邻接=取消F2表项，使用F1表项，F1首地址和F2尾地址
     • 回收区不与F1、F2相邻，则回收区自成一个新表项
     

动态分区算法

内部碎片：分配给某进程的内存区域中，有没有用上的部分
外部碎片：内存中某些空闲分区由于太小而无法利用

1. 首次适应算法
   • 空闲分区链以地址递增次序链接，从链首开始查找，直到能找到一个大小可以满足要求的空闲分区为止，按照作业大小划分分配空间；如果都不能满足，则内存分配失败，返回
   • 开销小，回收分区后不会对分区进行重新排列；低地址会留下很多外部碎片；碎片都在前面，增加查找时间
2. 循环首次适应算法
   • 空闲分区链以地址递增次序链接，每次都是从上次找到的空闲分区的下一空闲分区开始查找，直到找到一个满足要求的分区
   • 优点：内存空闲分区分布均匀；算法开销小，不用每次都重新查找
   • 缺点：缺乏大的空闲分区
3. 最佳适应算法【一定要掌握】
   • 空闲分区链以容量递增次序链接，优先使用更小的分区，保留更大的分区
   • 优点：有更多大分区被保留，满足大进程需求
   • 缺点：会产生许多太小、难以利用的碎片；开销大，回收内存后可能要对空闲队列重新排序
4. 最坏适应算法
   • 空闲分区链以容量递减次序链接，优先使用更大的分区，以免产生太小的不可用碎片
   • 优点：减少难以利用的小碎片，对中小作业有利；效率高，只要看第一个分区就可以
   • 缺点：大分区容易被用完；算法开销大（回收后要重新排序）

基于索引搜索的动态分区分配算法

动态可重定位分区分配

1. 紧凑
   连续分配需要连续的空间，大作业占内存太大内存中没有足够的内存可以装入，可以采用紧凑技术。
   紧凑通过移动内存中作业的位置，把原来多个分散的小分区拼成一个大分区。
   紧凑需要对程序的数据或者地址进行重定位，影响系统的运行效率。
2. 动态重定位

lff:动态重定位和运行时动态链接是相关的；把逻辑地址转换成物理地址的过程，由操作系统进行地址重定位完成，需要硬件支持
使用重定位寄存器，地址变换在程序运行期间，随着指令或数据的访问自动进行；如果系统堆内存进行了紧凑，使得若干程序从某处移动到另一处，不需要对程序做出修改

3. 动态重定位分区分配算法

对换

对换技术也称交换技术，要实现对换技术，系统中必须要有一台I/O速度较高的外存，容量要足够大。

多道程序环境下的对换技术、

对换是指把内存中暂时不能运行的进程或暂时不用的程序或数据调到外存上，一边腾出足够的内存空间，再把具备运行条件的进程或进程所需要的程序和数据调入内存。

• 对换的类型
  1. 整体对换
  2. 页面对换

对换空间管理

在具有对换功能OS中，通常把磁盘空间（外存）分配文件区和对换区两部分

• 文件区
  • 占大部分，用于存放各类文件，目标是提高文件存储空间的利用率，然后再是提高对文件的访问速度
  • 离散分配方式
• 对换区
  • 占小部分，用于存放从内存中换出的进程，这些进程在对换区中驻留的时间短暂，对换频率高
  • 目标：提高进程换入和换出的频率，然后是提高文件存储空间的利用率
  • 连续分配方式
• 对换区空闲盘块管理的数据结构
  • 空闲分区表/空闲分区链
• 对换空间的分配与回收
  • 连续分配方式，和动态分区方式相同

进程的换出与换入

发生时机：内核发现内存不足的时候会调用对换进程，实现进程换入换出。（进程运行的时候出现缺页且显现出内存紧张的情况）
换出是将内存中某些进程调出至对换区，但是PCB常驻内存

• 选择被换出的进程：首先选处于阻塞状态或睡眠状态的进程
• 进程换出过程
  • 先申请对换空间，申请成功，启动磁盘，将程序和数据传送到磁盘对换区上。若传送过程没有出错，则把该进程占用的内存空间回收，并对该进程的TCB、内存分配表等数据结构进行修改。如果内存中还有可换出的进程，则继续执行换出，直到内存中没有阻塞进程为止。
• 进程换入过程
  • 找出就绪态但已换出的进程，如果有多个，则选择已换出到磁盘上空间最久的进程，为它申请内存。如果申请成功，则直接调入内存。如果失败，则先将内存中的进程调出，腾出足够空间再调入。
  • 直到内存中没有就绪且换出状态的进程或者没有足够内存换入进程，终止调换。

分页存储管理方式

分页存储管理的基本方法

进程页面离散存放，页面内连续存放

1. 页面和物理块
   • 页面：进程的逻辑地址空间，可以分为若干页，为其加以编号
   • 物理块：内存的物理地址分割为若干块，为其加以编号
   • 进程中的若干页可以分别装入到多个不相邻接的物理块中
   • 最后一页经常装不满一块，形成不可利用的碎片，称为页内碎片
   • 页面大小
     • 过小：减少内存碎片，利于提高内存利用率但是会造成每个进程占用过多的页面，导致进程页表过长，占用大量内存，降低页面换进换出的效率
     • 过大：减少页表长度提高页面换进换出的速度，但是会使页内碎片过大
     • 适中最好，一般为1KB-8KB
     • 大小计算
       • 内存块大小=页面大小；块数=内存大小/页面大小 块数=》表示块号所用的字节数
       • 存储的时候，页号是隐含的，页表的大小=页数*表示块号所需要字节数
2. 地址结构
   • 如何访问一个逻辑地址？
     1. 确定页号
     2. 找到页的起始地址
     3. 确定页内偏移量
   
   • 页号=逻辑地址/页面长度（除法整数部分）======高位是页号
   • 页内偏移量=逻辑地址%页面长度（取余）========低位是页内偏移量
   • 实际物理地址=页面在内存中的起始地址+页内偏移量
   • 同样，物理块号也可以这样算
   • K位页内偏移量=页面大小位$2^K$；M位页号=$2^M$位
3. 页表：实现页号到物理块号的地址映射，存放在PCB中
   • 一个进程对应一张页表
   • 进程的每个页面对应一个页表项
   • 每个页表项由页号和块号组成
   • 页表记录进程页面和实际存放的内存块之间的映射关系
   
   • 对于页表项大小的讨论：
     每个页表项长度是相同的，页号是隐含的，一般页表项按顺序连续存放在内存中；为方便页表查询，常常会使表项占据更多字节，使得每个页面恰好可以装下整数个页表项s

地址变换机构

用于实现逻辑地址到物理地址转换的硬件机构

1. 基本地址变换机构
   页表寄存器(PTR)：存放当前运行的进行的页表在内存的地址始址以及页表长度（进程未执行，页表始址和页表长度放在PCB中）
   • 变换过程：（逻辑地址A到物理地址E）
     1. 计算页号P和页内偏移量W
     2. 比较页号P和页表长度M，如果P>=M（页号从0开始，页表长度至少为1）,产生越界中断
     3. 【访问内存】根据页表起始地址、页号找到对应页表项；页表中页号P对应的页表项地址=页表起始地址F+页号P*页表项长度（一个页面的大小） ；取出该页表项内容b
     4. 根据页表项中记录的内存块号、页内偏移量，得到最终物理地址；计算B=b*L+W
     5. 【访问内存】访问物理内存对应的内存单元
     
   • 页式管理中地址是一维的（只查一次就能查到）
2. 具有快表的地址变换机构
   快表（TLB、联想寄存器）是一种访问速度比内存块很多的高速缓存（不是内存），用来存放最近访问的页表项的副本，可以加快地址变换的速度，内存中的页表被称为慢表。

   lff:使用快表的目的：缩短进程访问内存的有效时间，加快访问内存的速度

   
   • 查询步骤：
     1. 通过逻辑地址计算出页号、页内偏移量，将页号与快表中的所有页号进行比较
     2. 找到匹配的页号，说明要访问的页表项在快表中有副本，直接从中取出该页对应的内存块号，拼接成物理地址，最后访问对应内存单元。【快表命中，访问逻辑地址只需要一次访存】
     3. 没有找到匹配页号，访问内存中的页表，得出物理地址之后访问内存单元。【两次访存】找到页表项后，需要将其加入快表。
        由于局部性原理，快表命中率高达90%以上。
   • 需要注意，快表和慢表是否同时查找（并行/不并行）
   • TLB不是Cache，TLB存放页表项副本，Cache存放其它各种数据的副本

访问内存的有效时间EAT

(lff说不重要)
设访问一次内存的时间是t，查找快表需要时间r，快表命中率a

• 基本分页式：EAT=t+t=2t（页表一次，访存一次）
• 引入快表：EAT=a*r+(t+r)(1-a)=2t+r-t*a

两级和多级页表

lff: 1.**两级多级页表的目的：避免页表的连续存放,避免把页表连续放在内存中(但是找不到内存)**2.多级页表不会减少访问内存的时间，不会避免缺页的中断问题，最主要的优点就是避免页表在内存中的连续存放

• 单级页表问题：页表很大，可能会占用很大的内存空间而且页表要求存储它的内存空间是连续的，为了解决该问题，因此采用如下两个方法解决问题：
  1. 页表可以采用离散分配，页表可能难以分到大块连续内存空间（多级页表）
  2. 不需要将整个页表常驻内存，只需要在特定时间访问特定页面即可（虚拟存储）
• 两级页表
  建立外层页表，该页表项中记录了页表页面的物理块号。
  1. 地址结构：
  
  2. 地址变换过程：
     1. 按照地址结构将逻辑地址拆分为三部分
     2. 从PCB中读出外层页表的起始地址，根据外层页号查目录表，找到下一级页表在内存中存放的位置
     3. 根据二级页号查表，找到最终想访问的内存块号
     4. 结合页内偏移量得到物理地址
     
• 多级页表：各级页表大小不超过一个页面
• 两级页表（在没有快表的情况下）会有三次访存（多了一次访存外层页表）；N级需要N+1次访存

反置页表

• 由于页表的大小是根据页表项的多少来决定的，如果进程逻辑地址空间很大，那么其页表项也会增多，页表大小也会增加，占用大量空间。
• 解决方法：引入反置页表：为每个（内存）物理块设置一个页表项，按照物理块号排序，其中的内容是页号以及其隶属进程的标识符。由于内存容量不会变化，所有反置页表也不会变化。

分段存储管理方式

分段存储管理方式引入

分段的特点

1. 方便编程，提高程序可读性
2. 信息共享
3. 信息保护
4. 动态增长
5. 动态链接

分段系统基本原理

1. 分段
   • 分段：按照程序自身的逻辑关系划分为若干个段，每个段有段名，每段从0开始编址；内存以段为单位分配，每段在内存中占据连续空间，但是各个段之间可以不相邻，各个段的长度不相等
   • 地址结构：段号（每个进程最多可以分几个段）+段内地址（每个段的最大长度）
2. 段表：段号、段长、基址
   • 每个段对应一个段表项，段表项中记录了段在内存中的起始位置和段的长度
   • 各个段表项的长度是相同的，因此段号可以隐藏，由段表项长度和段表起始地址计算出
   
3. 地址变换机构
   • 变换过程：段表寄存器，段表始址F，段表长度M；段表中记录段长C，基址b
     1. 根据逻辑地址得到段号S、段内地址W
     2. 检查段号是否产生越界中断，若S>=M，则产生越界中断，否则继续执行
     3. 查询段表，找到对应段表项，F+S*段表项长度
     4. 检查段内地址是否超过段长，若W>=C产生越界中断，否则继续执行
     5. 计算得到物理地址b+W，并访问内存单元

• 分页和分段的主要区别
  1. 页是信息的物理单位，主要是为了实现离散分配，提高内存利用率，分页是满足系统管理上的需要，对用户是不可见的。段是信息的逻辑单位，分段是为了更好地满足用户需求，一个段通常包含一组属于一个逻辑模块的信息，分段是对用户可见的，编程时需要给出段名
  2. 页大小固定且由系统决定，且直接由硬件实现。段长度不固定，取决于用户编写的程序，主要根据信息性质进行划分。
  3. 分页用户进程地址空间是一维的，用户程序属于单一的线性地址空间，秩序利用一个记忆符就可以表示一个地址。分段是用户的行为，分段系统中用户程序的地址空间是二维的，在标识一个地址的时候既要给出段名(段号)，又要给出段内地址。
  • 访存：单级分页需要两次访存，分段也需要两次访存

  lff:分段是用户行为，分段的地址空间是两维的

信息共享

分段系统的突出优点：容易实现段的共享，允许若干个进程共享一个或多个分段以及实现段的保护

1. 分页系统对程序和数据的共享
   页面不是按照逻辑划分，难以实现共享和保护
2. 分段系统对程序和数据的共享
   容易实现共享，只需要在段表中添加响应项即可
   例：可重入代码/纯代码 允许多个进程同时访问，不允许任何进程对其进行修改（看书，图）

   可重入代码：又称为纯代码，允许多个进程同时访问的代码，不允许任何进程对其进行修改。

段页式存储管理方式（ff说不考）

• 分段、分页优缺点
  • 分页
    • 优点：内存空间利用率高，不产生外部碎片，有少量内部碎片
    • 缺点：不方便按照逻辑模块实现信息共享和保护
  • 分段
    • 优点：便于信息的共享和保护
    • 缺点：段长过大，分配连续空间不方便，且容易产生外部碎片
• 段页式管理思想：先分段再将各段分页
  1. 地址结构：段号S+页号P+页内偏移量W；页号决定每个段最大有多少页（需要提供段号+页号，因此是二维的）
     段页式管理的地址结构是二维的（需要显式给出段号、段内地址）
  2. 段表、页表
     段表：(段号、)页表长度、页表存放块号
     页表：(页号、)内存块号
     一个进程对应一个段表，一个段一个页表，一个进程对应多个页表
  3. 地址变换机构
     段表始址F，段表长度M
     1. 根据逻辑地址得到段号S、页号P、页内偏移地址W
     2. 判断段号是否越界，若S>=M，则产生越界中断，否则继续执行
     3. 【访存】查询段表，找到对应表项，段表项地址：F+S*段表项长度
     4. 检查页号是否越界，如果页号>=页表长度，则发生越界中断，否则继续执行
     5. 【访存】根据页表存放块号、页号查询页表，找到页表项
     6. 根据内存块号、页内偏移量得到最终物理地址，【访存】最后访问内存
        访存次数：三次，可以引入快表，同时使用段号和页号检索快表
     

虚拟存储器

虚拟存储器概述

虚拟存储器主要解决的问题：1.作业很大，不能全部装入内存 2.大作业要求运行但是内存不够，大作业只能在外存等待

常规存储管理方式的特征、局部性原理

1. 常规存储器管理方式的特征

   1. 一次性：作业需要一次性全部装入内存->大作业无法在小内存中运行，浪费内存；多道并发性下降
   2. 驻留性：作业被装入内存后就一直驻留在内存中，直到作业运行结束。->占用资源

2. 局部性原理

   • 时间局限性：之前执行过的指令很可能再次执行；之前访问的内存不久后可能还会被访问（循环操作—）
   • 空间局限性：之前访问过的内存单元的附近单元也会被访问（程序顺序执行）

3. 虚拟存储器的基本工作情况
   只需将当前要运行的少数页面段先装入内存，其余部分留在盘上

   程序运行时：如果段/页已经在内存，便执行下去；如果程序要访问的页/段未调入内存（缺页/段）则发出缺页（段）中断请求，OS会使用请求调页（段）功能将其调入内存；如果内存已满，则OS会使用页（段）置换功能，将内存中暂时不用的页（段）调至盘上，腾出足够的内存空间后再将要访问的页（段）调入内存，使程序继续执行下去。

虚拟存储器的定义和特征

• 定义：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
• 特征：
  1. 多次性<->(一次性)：作业中的程序和数据无需一次性全部装入内存，允许多次调入内存运行
  2. 对换性<->(驻留性)：无需再作业运行时一直常驻内存，允许在作业允许过程中进行换进、换出
     3.虚拟性：能从逻辑上扩充内存容量，使用户看到的内存容量远大于实际内存容量（提高并发性和内存吞吐量）

虚拟存储器的实现方法

离散分配存储管理方式；与传统离散分配存储管理的区别；1.访问信息不在内存时，OS需要将所需信息从外存调入内存；2.内存不够，需要将暂时用不到的信息换出到外存

1. 请求分页存储管理（见下节）
   在传统分页系统上增加了请求调页功能和页面置换功能
   • 硬件支持：
     1. 请求分页的页表机制
     2. 缺页中断机构
     3. 地址变换机构
   • 软件支持
2. 请求分段存储管理
   在传统分段系统上增加了请求调段功能和分段置换功能
   • 硬件支持：
     1. 请求分段的段表机制
     2. 缺页中断机制
     3. 地址变换机构
   • 软件支持
     3，请求段页式存储管理

请求分页存储管理方式

1. 硬件支持

   1. 请求页表机制：页表包含以下诸项：（基本分页机构只有前两项）

      页号	物理块号	状态位P	访问字段A	修改位M	外存地址

      1. 状态位P：指示该页是否已调入内存，程序访问时参考
      2. 访问字段A：记录本页在一段时间内被访问的次数
      3. 修改位M：标识页面在调入内存后是否被修改，未被修改可以不用写回外存
      4. 外存地址：指出该页在外存上的地址，通常是物理块号，供调入该页时参考

      lff:状态，访问字段，修改位是必须有的，外存地址不一定会有

   2. 缺页中断机构
      每当访问的页面不在内存时，便产生缺页中断（内中断）；缺页中断与一般中断的区别如下：

      1. 在指令执行期间产生和处理中断信号，（一般是CPU执行完一条指令再检查有没有中断请求到达）
      2. 一条指令在执行期间可能产生多次缺页中断（下图例子：6次缺页中断，指令跨两个页面，指令需要的A、B又跨两个页面）
      • 补充：缺页中断处理完成后，返回该指令，一定会重新执行一次发生缺页中断的指令，原因：产生缺页中断的时候指令没有执行完，所以需要重新执行一次；普通中断一般是指令执行完毕之后产生的，因此解决后，直接执行下一条指令
      • 缺页中断一般由什么部件产生？一般都是由MMU产生 MMU:内存管理单元
      • 缺页中断后OS进行的处理：===？

   3. 地址变换机构
      在分页系统地址变换机构上增加了某些功能

      1. 先检索快表，如果找到访问页：**修改页表项:**修改页表项中的访问位；如果是写指令，则将修改位置为1；**访问：**通过物理块号和页内地址形成物理地址
      2. 快表未命中：在内存中找页表，看页表中的状态位P（是否已经调入内存）=>在内存：页表项写入快表=>如果快表满，则通过某种算法调出某页表项（出快表），再写入该页页表项=>地址变换、访问
      3. 该页不在内存：产生缺页中断=>保存CPU现场=>内存中未满：从外存读取缺页
      4. 内存已满：选择一页换出【页面置换算法】；如果换出页被修改，需要将该页写回外存
      5. OS命令CPU从外存读取缺页，启动I/O硬件，将一页从外存换入内存，修改页表、复制到快表
      

页面调入策略

（在"抖动"与工作集节有详细记录）

页面置换算法

缺页率：f=F/A 外存调入页面的次数F 访问页面成功的次数S 总的访问页面次数A=F+S

最佳置换算法

lff:理论上的置换算法，最佳置换不会被使用
选择的被淘汰页面是以后永不使用的或是再最长时间内不再被访问的页面；该算法性能是最优的，但是实际是无法实现的
缺页中断不一定发生页面置换，因为内存不一定是满的
算法过程：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

先进先出页面置换算法

FIFO 算法总是太太最先进入内存的页面，选择在内存中驻留时间最久的页面予以淘汰，将调入的页面拍成一个队列，设置替换指针
FIFO会产生Belady异常：为进程分配的物理块增大后，缺页次数不减反增

最近最久未使用置换算法

LRU 根据页面调入内存后的使用情况做出决策；从当前往回看，最后一个被使用的页面会被换出（页面自上次访问以来经历的时间t）

• 硬件支持较多：寄存器和栈
  • 寄存器：让问后置1，每过一段时间，就把寄存器右移一位，寄存器数值最小的就是最久没被使用的页面
  • 栈：每次访问就把页号从栈中移出并压入栈顶，每次栈顶的是最新被访问的，栈底是最近最久未使用的页面的页面号

最少使用置换算法

选择在最近时期使用最少的页面作为淘汰页。

方法：设置移位寄存器，被访问一次，寄存器最高位置为1，每次被访问，向右移一次，则，寄存器中值最小的就是

Clock置换算法

1. 简单的Clock置换算法（NRU 最近未使用算法）
   每页一个访问位，内存中所有页面通过一个链接指针链接成一个循环队列。某页被访问，访问位置为1。
   淘汰方法：检查页面访问位，如果是0，换出；如果是1，重新置0，暂不换出，再按照FIFO检查下一个页面；如果最后一个页面访问位还是1，则继续从队首查找第一个页面。
2. 改进型Clock置换算法
   考虑到：被修改的页面换出开销比未修改过的大
   综合考虑访问位A和修改位M
   • 四种类型：
     1. A=0 B=0 最近未访问，未修改 最佳淘汰页
     2. A=0 B=1 最近未访问但是，但是已修改，
     3. A=1 B=0 最近已访问但是未被修改，可能还会再被访问
     4. A=1 B=1 最近已访问且已修改，可能还会再被访问
   • 算法过程：
     1. 第一轮：指针从指示位置开始，找A=0,M=0的页面，如果找到，就将其淘汰；不改变访问位A
     2. 第二轮：找A=0 M=1的页面，且把扫描过的页面访问位都置0，如果找到第一个页面就是淘汰页
     3. 第三轮：指针返回开始位置，(此时所有访问位都是0)，重复第一步，找A=0,B=0页面，如果失败，就重复第二步，找A=0,M=1页面，此时一定能找到被淘汰页

页面缓冲算法（lff没提到）

PBA 王道没讲

• 影响页面换进换出效率的若干因素：
  1. 页面置换算法：缺页率
  2. 写回磁盘的频率：已修改页面，写回增加I/O操作次数
  3. 读入内存的频率
• 页面缓冲算法：
  • 特点：1.显著降低页面换进换出频率 2.采用策略简单，开销小，不需要特殊硬件
  • 思路：略

访问内存的有效时间

1. 被访问页在内存、对应页表项在快表 访问时间：$EAT=\lambda +t$
2. 被访问页面在内存，对应页表不在快表中 访问时间： $EAT=\lambda +t+\lambda +t=2*(\lambda +t)$ 两次访内存（读取页表+读取数据）
3. 被访问也不在内存中：缺页中断处理，有效访问时间：查找快表时间+查找页表时间+处理缺页中断时间+更新快表时间+访问实际物理地址时间
   设缺页中断处理时间为e $EAT=EAT=\lambda +t+e+\lambda +t=e+2*(\lambda +t)$
   考虑快表命中率a、缺页命中率f：$EAT=EAT=\lambda +a*t+(1-a)*[t+f*(e+\lambda+t)+(1-f)(\lambda+t)]$
   只考虑缺页率，不考虑快表命中率，缺页中断处理时间为 $\phi$ ：$EAT=EAT=t+f*(\phi +t)+(1-f)*t$

"抖动"与工作集

（前半部分对应书5.2.2）

• 驻留集：请求分页存储管理中给进程分配的物理块集合
  【驻留集太大：多道程序并发度下降；驻留集太小：频繁缺页】
  • 驻留集大小分为可变分配（大小改变）和固定分配（大小不变）
  • 置换分为局部置换（只对进程自己的物理块置换）和全局置换（可以拿走别的进程的空物理块或者调出别的进程的页至外存->进程拥有的物理块数一定改变）
• 页面分配、置换策略
  1. 固定分配局部置换：缺点：很难确定合理的分配给进程的物理块数
  2. 可变分配全局置换：刚开始分配一定数量物理块，只要进程发生缺页，都将获得新的物理块，而被选择调出的页从属的进程拥有的物理块会减少，缺页率会增加【只要缺页就有物理块】
  3. 可变分配局部置换：缺页，只能选自己的物理块，如果频繁缺页，系统适当增加分配给该进程的物理块；缺页不频繁，减少物理块【依照缺页率增减物理块】
• 页面调入策略：
  • 何时调入页面
    1. 预调页策略：根据局部性原理，一次性调入多个页面（预测），主要使用在进程首次调入，一般由程序员指出【运行前】
    2. 请求调页策略：进程在运行期间发现缺页，才将所缺页面调入内存；I/O开销大；调入页面一定会被访问到【运行时】
  • 何处调入页面
    外存分为两部分：文件区（存放文件）；对换区（存放对换页面）；文件区离散分配，读写慢；对换区连续分配，读写快
    1. 系统中又足够的对换区空间：页面调入、调出都是在内存和对换区之间进行，调入调出速度快
    2. 系统确实足够的对换空间：不会被修改的文件：文件区调入，不需要换出；可能被修改的部分:调到对换区换出，从对换区换入
    3. UNIX方式：运行之前数据都在文件区，如果需要换出，写回对换区，下次需要，从对换区调入
• 抖动(颠簸)现象
  抖动：刚刚换出的页面马上又要换入内存，新换入的页面马上要换出外存
  产生原因【非常重要】：进程频繁访问的页面数目高于可用物理块数（分配给进程的物理块不够）；
  - 书原文：同时在系统中运行的进程太多，由此分配给每个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将其所缺的页调入内存。使得在系统中排队等待页面调进/调出的进程数目增加，导致对磁盘的有效访问时间随之增加，造成每个进程大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致处理及的应用几句下降并趋于0。
• 工作集：
  • 定义：某段时间间隔$\Delta$里，进程实际访问的页面集合
    系统会根据工作集的大小计算驻留集的大小，驻留集大小不能小于工作集大小，否则进程会频繁缺页
  • 工作集用于预调页策略的实现:如果能够预知程序在某段时间间隔内要访问哪些页面，并将它们调入内存，将会大大降低缺页率，从而显著提高处理机利用率。
  • Denning提出工作集的理论并推广
• 抖动的预防策略
  1. 采用局部置换策略，如果采用可变分配，可以采取局部置换，即使抖动不影响其他进程。
  2. 工作集算法融入到处理机调度中：调度之前先检查每个进程在内存的驻留页面是否足够多；足够多就调入，此时不会因为页面调入增加缺页率；如果进程的内存页面不足，则为缺页率高的作业增加物理块
  3. L=S缺页准则：缺页之间的平均时间、平均缺页服务时间接近，即L=S的时候，磁盘和处理机利用率最高【Denning提出】
  4. 选择暂停进程：暂停优先级最低的进程，直接把进程调出内存

请求分段存储管理方式

1. 请求页表机制：页表包含以下诸项：（基本分页机构只有前两项）

    |段名|段长|段基址| 存储方式 | 访问字段A | 修改位M|存在位P|增补位|外存地址|
    |---|----|------|---------|----------|-------|-------|-------|-------|
   

   前三项，基本项

   1. 存取方式：段是信息的逻辑单位，根据存取方式对段进行保护，分为只执行、只读、允许读/写
   2. 访问字段A：
   3. 修改位M
   4. 存在位：是否在内存
   5. 增补位：特有字段，标识本段在允许过程中是否做过动态增长
   6. 外存始址：标识本段在外存的起始地址

2. 缺段中断机构
   如果要访问的段没有调入内存，缺段中断机构会产生一缺段中断信号；一条指令执行期间可能有多次缺段中断；由于段不是定长的，缺段中断处理比缺页更为复杂，要考虑内存中有无合适空闲区，如果没有，还要空区拼接

   

3. 地址变换机构
   如果段不在内存，先把所缺的段调入内存，修改段表，之后利用段表地址变换

4. 分段的共享与保护
   • 共享段表新加字段：
     1. 共享进程计数 count=0才回收到内存区
     2. 存取控制字段：不同进程有不同的存取权限
     3. 段号：每个进程对应不同段号，每个进程用自己的段号找到共享段
   • 分配与回收：
     1. 分配：
     2. 回收：
        — 分段保护：
     3. 越界检查（地址变换机构）
     4. 存取控制检查（存取控制字段）
     5. 环保护检查

输入输出系统

I/O系统的功能、模型和接口

I/O系统的基本功能

1. 隐藏物理设备的细节
2. 与设备的无关性
3. 提高处理机和I/O设备的利用率
4. 对I/O设备进行控制
5. 确保对设备的正确共享
6. 错误处理

I/O系统的层次结构

OS内核部分（打星号的）一个I/O请求的处理顺序（上至下）/I/O应答顺序（下至上）；倒数2、3直接接触硬件

• 用户层软件：实现与用户的交互接口，如I/O相关的库函数，系统调用
• 设备独立性软件【设备无关性软件】✳：用于实现用户程序与设备驱动器的统一接口、设备命名、设备保护以及设备的分配与释放等，同时为设备管理和数据传送提供必要的存储空间。
  • 与设备硬件特性无关的功能几乎都在该层实现
    • 向上层提供系统调用接口
    • 提供设备的保护
    • 差错处理
    • 设备的分配与回收
    • 数据缓冲区管理
    • 建立逻辑设备名到物理设备名的映射，根据设备类型选择相应的驱动程序（不同设备有不同的设备驱动程序）
      • 实现方法：LUT逻辑设备表，包含三项：逻辑设备名，物理设备名和驱动程序入口地址
      • 设置方式：
        1. 整个系统设置一（个LUT只能是单用户）：不同用户文件名不能相同
        2. 每个用户一个LUT：各个用户使用的逻辑设备可以重复，适用于多用户操作的系统
• 设备驱动程序✳：与硬件直接相关，用于具体实现系统对设备发出的操作指令，驱动I/O设备工作的驱动程序。设置设备寄存器、检查设备状态

  lff:访问磁盘：柱面、磁道和扇区在哪一层被确定出来？？=========设备驱动程序与硬件直接相关，这些参数是由设备驱动程序算出来的

• 中断处理程序✳：保存被中断的进程的CPU环境，转入对应中断处理程序进行处理，处理完毕后再恢复到被中断进程的现场，返回被中断的进程。
• 硬件：执行I/O操作

I/O系统的接口

• 块设备接口
• 流设备接口
• 网络通信接口

I/O设备和控制器

I/O设备

I/O设备由执行I/O操作的机械部分和执行控制I/O的电子部件（I/O控制器）组成
I/O设备分类：

1. 按照信息交换的单位：块设备（移动硬盘/磁盘：可寻址，速率高）、字符设备（鼠标/键盘）

   lff:字符设备和块设备:块设备一般是磁盘，Linux的文件系统是在块设备上实现的

2. 按照使用特性：存储设备和I/O设备（输入、输出、交互设备）
3. 按照传输速率分类：低俗、中速、高速设备

设备控制器

• 设备控制器的基本功能：
  1. 接收和识别指令：控制寄存器，对处理机指令译码；存放CPU送来的控制信息
  2. 数据交换：数据寄存器，CPU与控制器、控制器与设备之间数据交换
  3. 标识和报告设备状态：状态寄存器，记下设备状态供CPU了解
  4. 地址识别：地址译码器，设备控制器需要识别设备地址以及每个寄存器中的地址
  5. 数据缓冲区：解决CPU和I/O设备速率不匹配的情况
  6. 差错控制：检查输入数据的正确性
     (以上寄存器也可能有多个)
• 设备控制器的组成
  1. 设备控制器与处理机的接口:数据线、地址线、控制线
  2. 设备控制器与设备的接口（可以对应多个设备）
  3. I/O逻辑：实现设备控制，I/O逻辑对收到地址、指令进行译码，对所选设备进行控制
  

内存映像I/O

1. 寄存器独立编址
   寄存器独立编址，早期使用，缺点：需要设置专门指令来实现对控制器的操作（指明地址+控制器编号），访问内存和访问设备需要两种不同指令
2. 内存映像I/O
   控制器中的寄存器与内存地址统一编址，简化了指令和I/O编程

I/O通道

中断机构和中断处理程序

（书p189【202】）

设备驱动程序（设备处理程序）

设备驱动程序概述

• 设备驱动程序功能：
  1. 接收命令和参数并转换为与设备相关的低层操作序列
  2. 检查用户I/O请求合法性
  3. 发出I/O命令
  4. 及时响应由设备控制器发来的中断请求
• 设备驱动程序特点
  • 设备驱动程序是低级的系统例程
• 设备处理方式

lff强调的点：

1. 设备驱动程序本身和硬件相关；在设备驱动程序之间不能再使用OS的系统调用。
2. 既可以运行在核内，也可以运行在核外

设备驱动程序的处理过程

对I/O设备的控制方式

1. 轮询的可编程I/O方式
   CPU发送一条指令后，busy=1 程序不断循环测试busy直到busy=0 分析：
   - CPU干预频率：大，等待I/O完成过程中需要不断论查
   - 数据传送单位：一个字
   - 数据的流向：读：I/O->CPU->内存 写：内存->CPU->I/O设备
   - 优点：简单
   - 缺点：CPU/IO设备只能串行，CPU长期忙等
2. 使用中断的可编程I/O方式
   CPU把等待I/O的进程阻塞，切换到别的进程执行，一旦I/O完成，控制器向CPU发送中断信号，保存进程的允许环境信息，专执行中断处理程序处理该中断；处理完成后，CPU恢复等待I/O的进程的运行环境，继续执行 分析：
   - CPU在每个指令周期的末尾检查中断
   - 中断处理过程有开销，频率太高降低性能
   - CPU干预：I/O开始之前,CPU要介入，等待I/O，CPU可以切换到别的进程
   - 数据传送的单位：每次读写一个字
   - 数据流向：读：I/O->CPU->内存 写：内存->CPU->I/O设备
   - 优点：CPU/IO并行工作
   - 缺点：每个字的传输都要经过CPU 频繁中断处理消耗较多的CPU时间
3. DMA方式（直接存储器存取）
   • 特点：
     • 数据传送单位是块，不是字
     • 数据流向：设备放入内存/内存直接到设备，不经过CPU
     • 仅在传送一个或多个数据块的开始和结束需要CPU干预
   
   • DMA控制器的组成
     1. 主机与DMA控制器接口
        • 命令/状态寄存器CR：存放CPU发来的I/O命令或设备的状态信息
        • 内存地址寄存器MAR：输入：数据从设备传送到内存的起始目标地址；输出：内存到设备的内存源地址
        • 数据寄存器DR：暂存从设备到内存/内存到设备的数据
        • 数据寄存器DC：存放CPU要读写的字节数
     2. DMA控制器与块设备的接口
     3. I/O控制逻辑
   • DMA工作过程（见书）
     分析：
     • 传送多个块的开始和结束才需要CPU干预
     • 数据传送单位：每次读/写一个或多个块（连续的）【DMA与内存之间的传输单位是一个字】2
     • 数据流向：不再经过CPU：读：I/O->内存 写：内存->I/O设备
     • 优点：进一步提升效率，cpu接入频率降低，CPU，I/O并行性能提示
     • 缺点：只能读写一个或多个连续数据块
4. 通道控制方式（略）
   由来：CPU只能一次性读取一个连续的数据块，不适用于一次性多个数据块的读取
   通道：一种硬件，有类似CPU的功能，通道可以识别并执行一系列通道指令
   过程：
   - CPU向通道发出I/O指令，指明通道程序在内存中的位置，指明要操作的是哪个I/O设备，之后CPU切换到其它进程执行；
   - 由通道执行内存中的通道程序
   - 通道执行完规定的任务后，向CPU发出中断信号，之后对CPU进行中断处理
   分析：
   - CPU干预频率：只有完成一组数据块的读写才需要发出CPU中断信号，请求CPU干预
   - 数据传送单位：一组数据块
   - 数据流向：在通道的控制下进行：读：I/O->内存 写：内存->I/O设备
   - 优点：CPU、通道、I/O设备并行工作，资源利用率高
   - 缺点：实现复杂，需要专门的通道硬件支持
   通道程序（略）：一系列通道指令构成
   包含：1.操作码 2.内存地址 3.计数 4.通道程序结束位 5.记录结束标志

与设备无关的I/O软件

与设备无关软件的基本概念

与设备无关的软件

设备分配

一般使用逻辑设备名访问物理设备

• 设备分配时应该考虑的因素：
  • 设备固有属性：
    • 独占设备（一个时间段职能分配给一个进程）
    • 共享设备（一个时间段多个进程）
    • 虚拟设备（spooling技术将独占设备改造成为虚拟共享设备）
  • 设备分配算法：
    • FCFS
    • 优先级高有点
  • 设备分配中的安全性
    • 安全分配方式：一个时间段，一个进程只能请求一个设备，破坏请求和保护条件，不会死锁，但是效率低，CPU和I/O对于一个进程来说只能串行工作
    • 不安全分配方式：发出I/O请求后，继续执行，之后还可以发出更多I/O请求，效率高，但是它可能导致死锁（有请求和保持条件）
• 静态分配、动态分配
  • 静态分配是一次性全分配好，避免了死锁
  • 动态分配：进程运行过程中动态申请，可能死锁
• 设备分配管理中的数据结构
  • 设备控制表：DCT，系统为每个设备配置一张DCT，记录设备情况
    • 设备队列队首指针（PCB组成）：请求本设备到那时未得到满足的进程，需要将PCB排成一个请求队列
    • 设备状态：忙/闲 标识当前设备状态
    • 与设备相连的控制器表指针：指向该设备所连接的控制器的控制表
    • 重复执行次数或时间：外部设备容易发生错误，如果在重复执行后可以回复正常，则认为传输成功，仅当重复执行次数达到规定值后仍不成功时才认为传送失败
  • 控制器控制表、通道控制表和系统控制表
    • 一个通道控制多个控制器、一个控制器控制多个设备
    • 控制器控制表COCT：OS根据COCT中的信息对控制器进行操作和管理；=>对应控制器
    • 通道控制表CHCT：OS根据CHCT的信息对通道进行操作和管理 =>对应通道
    • 系统设备表SDT：记录系统中全部设备的情况 =>对应设备
    
• 独占设备分配程序

  • 基本设备分配步骤

    1. 分配设备：根据进程请求的物理设备名查找SDT，找到该设备的DCT；根据DCT判断该设备是否忙碌，如果设备忙，则将进程PCB挂到等待队列中，不忙则直接分配设备给进程
    2. 分配控制器：如果上一步分配，系统会从DCT中找到与该设备连接的控制器的COCT，查看COCT中控制器是否忙碌，如果忙则把PCB挂到该控制器的等待队列中，不忙碌则把该控制器分配给该进程
    3. 分配通道：如果上一步分配，系统会在COCT中招待与该控制器连接的通道的CHCT，再根据CHCT判断是否忙碌，如果忙碌，则把PCB挂到该通道的等待队列中，如果不忙碌，则把通道分配给该进程

    设备、控制器、通道三个都分配成功才算分配成功

    • 缺点：
      • 编程不便，需要提供设备名，但是物理设备名可能改变
      • 进程请求的设备忙碌，不会把同类型的空闲设备分配给该进程

  • 改进设备分配程序

    
    1. 使用逻辑设备名查找SDT
    2. 查找SDT 找到用户指定类型且空闲的设备，将其分配给该进程，同时OS在逻辑设备表（LUT）中增加一个表项
    3. 此后按照基本方式分配控制器和通道
    • LUT建立了逻辑设备名和物理设备名之间的映射关系
    • LUT的设置：
      1. 整个系统只有一张LUT
      2. 每个用户一张LUT(上图表2)

缓冲区管理（略）

缓冲区：一般用在对速度要求高的场合，一般缓存区由内存组成

缓冲区的引入

• 缓和CPU和I/O设备速度不匹配的矛盾
• 减少对CPU中断的频率，放宽对CPU中断响应时间的限制
• 解决数据粒度不匹配的问题（生产者和消费者之间交换数据的粒度粒度：数据单元大小）
• 提高CPU和I/O设备之间的并行性

单缓冲区和双缓冲区

缓冲区数据非空时，不能向缓冲区冲入数据，只能传出；当缓冲区为空，可以冲入但是不能传出

• 单缓冲区：每当用户进程发出一I/O请求时，OS便在主存中为止分配一个缓冲区
  • 计算：处理每块数据的时间
    • 假设：工作区满，缓冲区空；再次回到该状态视为一次处理
    • 设把数据输入到缓冲区时间为T 数据从缓冲区送到用户区（工作区）时间为M CPU对数据处理时间为C
    • T>C的情况;T<C的情况：
    • 平均耗时：max(C,T)+M
• 双缓冲区：OS会给进程分配两个缓冲区
  • 计算，假设初始状态：工作区空，一个缓冲区满，另一个缓冲区空
    • T>C+M ：时间：T
    • T<C+M(很难找到一个准确的时间，只能平均下来估算)平均：C+M
    = MAX(T,M+C)
• 通信时的单缓冲与多缓冲区：
  • 单缓冲区：只能单向传播数据
  • 双缓冲区：同一时刻可以实现双向数据传播

环形缓冲区

多个大小相等的缓冲区连接成一个循环队列

缓冲池

缓冲区：一组内存块的链表
缓冲池：包含一个管理的数据结构以及一组操作函数的管理机制，用于管理多个缓冲区

• 组成：三个队列，四个缓冲区
  • 队列
    • 空缓冲队列
    • 输入队列
    • 输出队列
  • 缓冲区
    • 收容输入数据的工作缓冲区
    • 提取输入数据的工作缓冲区
    • 收容输出数据的工作缓冲区
    • 提取输出数据的工作缓冲区

磁盘存储器的性能和调度

盘片、（磁盘有两个）盘面、磁道、扇区
柱面：所有磁盘中相对位置相同的磁道组成一个柱面
每个扇区存储的数据量相同，但是最内侧磁道上的扇区面积最小，数据密度最大

• 寻找数据的方法；块号=>柱面号、盘面号、扇区号
  1. 根据柱面号移动磁臂，让磁头指向固定柱面
  2. 激活指定盘面对应磁头
  3. 磁盘旋转过程中，指定扇区会从磁头下划过，完成对扇区的读/写
• 磁盘分类：
  • 固定头磁盘：每个磁道都有一个磁头（大容量磁盘）
  • 活动头磁盘：只有一个磁头（磁头有寻道功能，只能串行读写）
• 磁盘调度算法

  lff：先来先服务 最短寻道时间优先、电梯算法，等三个算法 平均寻道长度，开始磁道号，要访问的磁道号，不同方式算出来的平均寻道长度不一样，会计算最短寻道时间

  • 磁盘访问时间组成
    • 寻道时间：Ts：把磁臂移动到指定磁道上所经历的时间：s+m*n(设启动磁臂时间为s，磁头跨过一个磁道耗时m)
    • 延迟时间：Tr：通过旋转使磁头定位到目标扇区所需要的时间，Tr=1/2*（1/r）=1/2r(磁盘转速为r 转/秒 转/分)（平均所需延迟时间）
    • 传输时间：Tt：从磁盘读出或向磁盘写入数据所经历的时间：1/r*(b/N)=b/(rN)【转一圈的时间*字节占总字节的比率】
    • 总平均存取时间：Ta=Ts+1/2r+b/(rN)
    • 延迟时间和传输时间不可优化，只能优化寻道时间
  • 先来先服务算法 FCFS（图看书吧懒得写了）
    • 优点：公平、简单
    • 缺点：有大量进程竞争使用磁盘，请求访问磁道分散，性能较差
  • 最短寻找时间优先算法 SSTF
    • 选择要求访问的磁道与当前磁头所在磁道最近的
    • 优点：性能好，平均寻道时间短
    • 缺点：可能产生饥饿现象，因为每次都服务离当前磁道最近的，离得远的磁道不会被访问
    
  • 扫描算法 SCAN(电梯调度算法)
    在SSTF的基础上：考虑磁头移动的方向，如果访问的磁道既在当前磁道之外，又是距离最近的，如果没有更外的磁道需要访问，才会将磁臂换向为自外向里
    • 优点：性能好，不会产生饥饿，平均寻道时间短
    • 缺点：SCAN算法对各个位置的磁道响应频率不平均；如果磁头从里到外已经越过某一个磁道，恰好有一个进程请求访问此磁道，必须等待很长时间（从里到外扫到顶在从底向上扫到该处）
  • 循环扫描算法 CSCAN：
    • 解决SCAN的缺点2
      只有磁头朝某个特定方向移动时才处理磁道访问请求，返回时直接快速移动到最里的欲访问磁道，而不处理任何请求。将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。
    • SCAN的延迟：2T CSCAN的延迟：T+Smax（磁头从最外面被访问的磁道直接移动到最里面欲访问的磁道的时间
    

  SSTF SCAN CSCAN都有可能出现磁臂停留在某处不动的情况，即，如果一个或者几个进程对某一磁道有较高的访问频率，这些进程反复请求对某一磁道的I/O操作，垄断了整个磁盘设备。这一现象称为磁臂粘着。FCFS不会出现磁臂粘着。

I/O软件层次结构(王道)

OS内核部分（打星号的）一个I/O请求的处理顺序（上至下）/I/O应答顺序（下至上）；倒数2、3直接接触硬件

• 用户层软件：实现与用户的交互接口，如I/O相关的库函数，系统调用
• 设备独立性软件【设备无关性软件】✳：与设备硬件特性无关的功能几乎都在该层实现
  • 向上层提供系统调用接口
  • 提供设备的保护
  • 差错处理
  • 设备的分配与回收
  • 数据缓冲区管理
  • 建立逻辑设备名到物理设备名的映射，根据设备类型选择相应的驱动程序（不同设备有不同的设备驱动程序）
    • 实现方法：LUT逻辑设备表，包含三项：逻辑设备名，物理设备名和驱动程序入口地址
    • 设置方式：
      1. 整个系统设置一（个LUT只能是单用户）：不同用户文件名不能相同
      2. 每个用户一个LUT：各个用户使用的逻辑设备可以重复，适用于多用户操作的系统
• 设备驱动程序✳：设置设备寄存器、检查设备状态
• 中断处理程序✳：中断处理
• 硬件：执行I/O操作

输入输出应用程序接口和驱动程序接口（王道）

• 输入输出应用程序接口：
  • 字符设备接口：get/put系统调用，以字符为单位
  • 块设备接口：read/write 向读写指针位置读/写多个字符；seek修改读写指针位置
  • 网络设备接口；socket接口 socket系统调用，创建一个网络套接字
• 阻塞/非阻塞I/O
  • 阻塞I/O：发出I/O系统调用后，进程需要转换为阻塞态等待
  • 非阻塞I/O：应用程序发出I/O系统调用后，系统调用可以迅速返回，进程无需阻塞等待
• 统一标准的驱动程序

I/O核心子系统

• 用户层软件
  • 假脱机技术（用软件实现脱机技术）
    • 脱机技术：脱离主机控制进行输入/输出操作（使用外围控制机）
    • 输入进程模拟脱机输入时的外围控制机，输出进程模拟脱机输出时的外围控制机
    • 输入缓冲区和输出缓冲区对数据进行暂存；输入从输入缓冲区拿到输入井；输出，把输出井内容输出到输出缓冲区中
    • 把一台物理上的设备虚拟成逻辑上的多台设备，把独占式设备改造成共享设备
• 设备独立性软件
  • I/O调度：用某种算法确定一个顺序来处理各个I/O请求
  • 设备保护：不同用户只能操作不同文件，设备被看作是一种特殊的文件
  • 设备分配与回收
  • 缓冲区管理

文件管理

内存映射文件

内存映射我呢见的访问方式：

1. open系统调用打开文件
2. mmap系统调用：将文件映射到进程的虚拟地址空间

• 特性：
  • 可以以访问内存的方式访问文件数据
  • 文件数据的读入、读出由OS自动完成而不需要read系统调用
  • 进程关闭文件时，OS自动将文件被修改的数据写回磁盘，不需要调用write系统调用
  • 多个进程可以映射同一个文件，实现共享
• 优点：编程简单，按照访问内存的方式读写，文件读入写出完全由OS负责，I/O效率由系统优化

文件和文件系统

（王道）入门

• OS向上提供什么功能？
  • 创建文件 creat系统调用
  • 读文件 read系统调用
  • 写文件 write系统调用
  • 删除文件 delete系统调用
  • 打开文件 open系统调用
  • 关闭文件 close系统调用
  • eg 复制文件：先创建一个新的空文件，把文件读入内存，将内存中的数据写到新文件中
• OS如何将文件放在外存？（文件的物理结构）
  • OS以块为单位为文件分配存储空间。
  • 文件共享
  • 文件保护

数据项、记录和文件

1. 数据项：最低级的数据组织形式，分为基本数据项(字段)和组合数据项(若干个基本数据项的组合)
2. 记录：一组相关数据项的集合 描述对象在某方面的属性
3. 文件：描述一个对象集
   • 文件分类：
     • 有结构文件：文件由若干记录组成（如数据库表）
     • 无结构文件：字符流或二进制流组成
   • 文件的属性
     • 文件名：同一个目录下不允许有重名文件
     • (标识符)：OS内部用于区分文件的内部名称，对用户来说无可读性
     • 文件类型：指明文件类型
     • 文件的物理位置：文件所在的设备以及所在设备中地址的指针
     • 创建时间：最后一次修改的时间’
     • 文件长度：
     • (护信息保):对文件进行访问控制

文件名和类型

• 文件名和扩展名
  • 文件名和扩展名之间使用圆点分开a.txt
• 文件类型
  • 按照

文件的逻辑结构

• 文件逻辑结构与物理结构：
  • 逻辑结构（文件组织）：从用户观点出发观察到的文件的组织形式，文件是由一系列的逻辑记录组成的
  • 物理机构（存储结构）：系统将文件存储在外存上所形成的存储组织形式，是用户不可见的。
• 文件逻辑结构的类型
  对文件逻辑结构的要求：1.利于提高检索记录速度和效率 2. 方便对文件修改 3. 降低文件再外存上的存储费用（所占空间尽可能小，不要求大片连续空间）
  • 按是否有结构分类：
    1. 有结构文件：由一组相似的记录组成，即记录式文件，每条记录由若干数据项组成
       • 定长记录：文件中每个记录的长度都相同，各个数据项都处于记录中相同的位置；便于修改和处理
       • 变长记录：文件中各记录长度不同。检索速度慢，不便于处理和修改，但有特殊应用场景
    2. 无结构文件：即流式文件，长度以字节为单位。访问方式：利用读写指针访问。

    lff:一般早期的OS会用到有结构的文件，现在的大多是OS的文件是无结构的，是无结构的文件；
    lff:无结构文件的好处：对文件的解释是依赖于具体的应用程序而不是OS来的
    辨析：这里的无结构指的是逻辑结构无结构，但是组织方式是可以看到的，通常是树形的组织方式

  • 按文件组织方式分类
    • 顺序文件(一般指顺序存储方式)：文件中的记录在逻辑上顺序排列（在物理上顺序或链式存储），记录可以是定长或变长的
      • 按照排列方式分类：
        • 如果按照关键字有序排列：顺序结构
        • 如果记录之间的顺序和关键字无关：串结构（如按照存入的时间顺序）
      • 存储方式：
        • 链式存储：无法实现随机存取，每次只能从第一个记录向后查找
        • 顺序存储：
          • 可变长记录：无法实现随机存取；
          • 定长记录：就可以实现随机存取；
            • 串结构无法快速找到关键字对应的记录，
            • 顺序结构可以快速找到关键字对应记录（如使用折半查找）
      • 顺序文件缺点：增加、删除记录比较困难，但串结构增删相对简单（解决方法：配置事务文件，产生按照关键字排序的新文件）；
      • 顺序文件优点：存取效率高。
    • 索引文件：为可变长记录建立的索引表
    • 索引顺序文件：顺序文件和索引文件的结合

顺序文件（合并到上一节）

记录寻址

1. 隐式寻址方式：通过上下文或规定的规则隐含地确定
   • 定长顺序文件：每次指针加定长的偏移量；读取第i个记录只要指针加上i*L即可
   • 变长记录的顺序文件：每次得到正在读写的记录的长度，偏移到下一个记录只需要将指针偏移刚刚读写的记录的长度；如果要随机访问一个记录i，那么就需要把所有的0-i-1个记录全部进行扫描或读取，才能得到第i个记录的位置
2. 显式寻址方式：程序员或用户直接指定数据或操作的目标地址
   • 通过文件记录中的位置
   • 利用关键字

索引文件

1. 按照关键字建立索引：
   对变长记录文件建立索引表，为文件中的每个记录建立一个表项，记录指向记录的指针。（书图7-4）将对变长记录顺序文件的顺序检索转换为对定长记录索引文件的随机检索，加快对记录检索的速度

   索引表本身是一个定长记录的顺序文件，按照关键字排序可以按照关键字折半查找。

   主要用于对信息处理的及时性要求较高的场合，解决了顺序文件不方便增删记录的问题，实现了不定长记录的文件实现了随机存取。

2. 具有多个索引的索引文件
   用不同数据项建立多个索引表

索引顺序文件

目的：减少索引表的空间占用

• 特征
  • 索引文件和顺序文件思想的结合
  • 保留顺序文件中，记录按照关键字顺序组织的特点
  • 文件索引表：通过文件索引表实现对索引顺序文件的随机访问
  • 溢出文件：记录新增加、删除、和修改的记录
• 一级索引顺序文件（图 7-5）
  只使用了一级索引
  • 首先：将变长记录的顺序文件分组
  • 然后：为顺序文件建立索引表，表中记录的是每组中第一个记录的关键字和指向该记录的指针。
  • 效率分析：有10000个记录的顺序文件
    • 根据关键字检索：从头开始顺序查找：平均查找5000个记录
    • 根据索引顺序文件结构：分为100组，每组100个记录。要找一个记录，首先找分组，平均查找长度 50 再从分组里找到顺序查找记录，平均查找长度50.总长度：100
• 两级索引顺序文件
  • 效率分析：1000000个记录的文件，先按照每100个为一组，分成10000组（一级索引表），然后把10000个定长记录分组，每100个为一组（二级索引表），这样二级索引表中就有100个记录，平均查找长度：50+50+50=150

直接文件和哈希文件

文件目录

对文件目录的要求：按名存取、提高检索速度、文件共享、允许重名

文件控制块和索引结点

1. 文件控制块FCB
   FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。一个文件目录也可以被看作是一个文件，即目录文件（定长顺序文件）。
   • 包含信息

     lff：要知道FCB有什么内容，要记录三类信息包括什么
     -基本信息类：
     1. 文件名：标识一个文件的符号名
     2. 文件物理位置（外存的存储位置，包括设备名、盘块号、占用盘块数、字节数）
     3. 文件逻辑结构：指示文件是流式还是记录式（记录数），文件是定长/变长记录）
     4. 文件物理结构(顺序/连接式/索引)

     • 存取控制信息：包括文件主的存取权限、核准用户的存取权限、一般用户的存取权限
     • 使用信息类：文件的建立日期和时间、文件上一次修改的日期和时间，当前使用的信息。（当前已打开的文件的进程数，是否被其他进程锁住，文件咋爱内存中是否已修改但是为拷贝到盘上）
     • MS-DOS的文件控制块
   • FCB实现了文件名和文件之间的映射
2. 索引结点
   • 引入：解决检索目录过程中，FCB占用内存过大的问题，只使用文件名来检索目录。把文件名和文件描述信息分开，文件描述信息单独作为索引结点（i结点）文件目录中每个目录项仅由文件名和指向该文件对应的i结点的指针。
   • 好处：索引结点机制大大减小文件名检索目录的大小，提升文件检索速度
     • 一个FCB 64B 盘块大小1KB 每个盘块放16个FCB 共有640个目录项，则需要40个盘块存放，平均需要查找320个目录项，平均需要启动磁盘20次(i/o)只读取一块
     • 索引结点：文件名占14B，索引结点指针2B 每个盘块可以放64个目录项，按照文件名检索平均只需要320/64=5个盘块
   • 找到文件名对应的目录项之后才需要把索引结点调入内存。
   • 磁盘索引结点：存放在外存的索引结点（书）
   • 内存索引结点：存放在内存的索引结点
     • 存放在内存的索引结点需要增加一些信息：状态（是否被修改/上锁）、访问计数、文件所属文件系统的逻辑设备号、链接指针

简单的文件目录

文件目录一般会有顶级目录

1. 单级文件目录
   • 整个文件系统只建立一个目录表，每个文件占一个目录项。
   • 实现了按名存取但是不允许文件重名，创建文件之前必须保证新文件名在目录中是唯一的
   • 优点：简单
   • 缺点：查找慢、不允许重名、不便于文件共享（不适用于多用户OS，原因见书）
2. 两级文件目录（书图7-10，两级文件目录） 分为主文件目录(MFD)和用户文件目录(UFD)
   • 主目录：每个用户目录文件占一个目录项,包括用户名、指向用户目录文件的指针
   • 用户目录：由该用户的文件FCB组成
   • 满足文件目录的要求：
     • 提高检索速度：原因同多级索引顺序文件
     • 不同用户目录可以使用相同的文件名；但是在自己UFD中文件名是唯一的
     • 不同用户可以使用不同文件名访问系统中的同一个共享文件
   • 问题
     • 用户之间存在隔离，无法共享文件
3. 树形结构目录（多级目录结构）
   主目录称为根目录，每个目录只能有一个父目录，允许目录文件中的目录项既可以是目录的FCB也可以是文件的FCB
   • 路径名和当前目录
     • 路径名：使用/连接
     • 当前目录：避免每次查找都从根目录开始，把当前目录开始知道数据文件为止所构成的路径名称为相对路径名

     lff:路径名和当前目录；当前目录的作用：加快文件的检索速度

   • 优点：查询快，结构清晰，赋权容易
   • 缺点：逐级访问，增加磁盘访问速度，不便实现文件共享（但是可以用链接使得文件有多个父目录）
   • UNIX LINUX WINDOWS都采用树形文件目录
4. 无环图目录结构（解决共享问题）
   树形目录结构的基础上增加一些指向统一节点的有向边，使目录成为有向无环图
   • 可以使用不同文件名指向同一个文件/目录
   • 为每个结点设置共享计数器，某个用户删除结点的时候只删除该用户FCB，共享计数器-1，并不会真正删除结点；只有当共享计算器=0才会删除结点
   • 只要一个用户修改了文件数据，所有用户都可以看到文件数据的变化

磁盘存储器的管理

文件的物理结构（王道）

OS对磁盘进行的管理：对非空闲磁盘块（=>文件物理结构的问题）；对空闲磁盘块（=>文件存储空间管理）

• 文件的物理结构（文件分配方式——
  • 探讨：文件数据如何存放在外存中？
  • 连续
• 文件块与磁盘块
  • 磁盘块大小与内存块、页面的大小相同（便于内存和外存以块为单位交换）
  • 内存管理中，进程的逻辑地址空间被分为一个个页面，在外存管理中，文件的逻辑地址也被划分为一个个文件块。文件的逻辑地址可以表示为（逻辑块好，块内地址）的形式

外存的组织方式

连续组织方式

连续组织方式：每个文件在磁盘上占有一组连续的块

上图展示了物理块号与逻辑块号的映射关系，显示了文件目录中存放的内容
物理块号计算方法：
- 物理块号=起始块号+逻辑块号
- 连续分配支持顺序访问和直接访问（随机访问）

• 优点：
  • 由于读取磁盘块需要移动磁头，访问两个磁盘块相隔越远，移动磁头需要的时间越长，因此连续分配的文件在顺序读写时速度最快，磁头移动距离最少。
  • 顺序访问容易，支持对定长文件的随机存取
• 缺点：
  • 产生很多外部碎片，存储空间利用率低，都需要定期执行紧凑消除碎片，但是紧凑需要耗费大量时间
  • 不方便文件拓展，插入和删除记录的时候很难为其分配空间
  • 必须要事先知道文件长度才能对空间有最大的利用率（不然要么少了要么分配多了）
  • 对于动态增长的文件，很难为其分配空间；如果使用预分配，会早场一块存储空间长期空闲

链接组织方式

• 隐式链接
  • 磁盘空间：除了文件的最后一个磁盘块之外，每个磁盘块都保存一个指向下一个盘块的指针，这些指针对用户是透明的
  • 文件目录：目录中记录文件存放的起始块号的结束块号（或者存放文件的起始块号和文件长度）
  • 缺点：
    • 只适合顺序访问，随机访问很低效,查找效率低，；（例子：要找第i块，必须先找到起始块号strat，顺序从第一块读到第i-1块才知道第i块的地址；共需要i+1次磁盘I/O【王道说是起始块号不算第一块】，书上说i=100需要100次访问）
    • 指针也要耗费少量的存储空间
  • 优点：便于文件拓展，没有碎片问题，外存利用率高
• 显式链接
  • 把用于链接文件各物理块的指针显式存放在一张表中，即文件分配表FAT（File Allocation Table）；表的序号是物理盘块号（可以隐藏），表项存放链接指针，即下一个盘块号
  • 目录中只需要记录文件起始块号
  • 磁盘中不需要存放指针
  • 每个磁盘仅设置一张FAT，开机时FAT读入内存，并常驻内存；FAT在物理上连续存储，每个表项长度相同（可以隐藏序号）
  • 逻辑块号到物理块号的转变：不需要读磁盘操作，只需要在内存中查询即可
  • 优点：
    • 支持顺序访问和随机访问，块号转换不需要访问磁盘，访问速度比隐式链接快
    • 不会产生外部碎片，可以方便地对文件进行拓展
  • 缺点：文件分配表需要占用一定存储空间

索引组织方式(主要组织方式)

1. 单级索引组织方式
   • 索引分配允许文件离散分配在各个磁盘块中，并且系统会为每个文件建立一张索引表，索引表中记录了文件各个逻辑块对应的物理块。
     • 磁盘中存放：索引块和数据块；索引表存放的磁盘块叫做索引块 文件数据存放的磁盘块成为数据块
     • 目录中记录的内容：指向该文件的索引块的指针
     • 与FAT的不同之处：FAT每个磁盘对应一张，索引表每个文件对应一张表
     • 索引表是固定长度顺序存储，因此索引表中的逻辑块号可以省略的
   • 逻辑地址转换为物理地址：把索引表从外存读入，查找索引表中第i号逻辑块
   • 优点：
     • 支持随机访问，文件拓展容易（只要在索引表中添加表项即可），没有外部碎片
     • 索引表占用一定存储空间；对小文件来说索引块利用率很低
2. 多级索引组织方式
   文件太大，文件的索引不够装在一个索引块，对于多个索引块的组织方式，有以下几种：
   • 链接方案：索引之间采用隐式链接；但是这样做只能依靠顺序查找来找逻辑块
     • 缺点：磁盘I/O次数过多
   • 多级索引：建立多层索引，第一层索引块指向第二层索引块，还可以再建立更多层索引块；多层索引中的各个索引表大小不能超过一个磁盘块

     • 文件目录中存放每个文件的一级索引块

     • 逻辑地址转换为物理地址：先从文件目录获得一级索引表调入内存，找到对应二级索引表，然后再把二级索引表调入内存，查找表项中的文件块号；需要3次磁盘I/O；K级索引需要K+1次磁盘I/O

     • 例子：
       如果盘块大小1KB 索引表项占4B 一个磁盘块存放256个表项

       如果文件采用两层索引，文件最大长度可以达到2562561KB=64MB

       如果要访问1026号逻辑块，1026/256=4 存放在一级索引表中序号为4的表项对应的索引表，1026%256=2 表示在索引表的第4个表项

     • 优点：大大加快对大型文件的查找速度

     • 缺点：访问一个盘块，需要启动磁盘的速度随着索引级数的增加而增多，对小文件不利，即使是小文件也要K+1次读磁盘操作

   • 混合索引（增量式索引组织方式）

     lff:会根据逻辑地址偏移量计算使用了一次、两次间址；每种方式可以存多少盘块；每块能装多大的文件；根据文件长度确定使用直接/一次/两次间址；假设使用6个或者7个地址项目，前3-4直接地址，剩下的4/5使用间址，计算文件长度，如果给定地址，给定文件偏移量，计算使用的索引组织方式

     • 思路：多种索引分配方式结合，一个文件的顶级索引表中既包含直接地址索引（直接指向数据块），还包含一级间接索引（指向单层索引表），还包含两级间接索引（指向两层索引表）;从文件角度来看，这些索引的地址都是放在FCB或者索引结点中的
     • 🌟根据顶级索引表计算出支持的最大文件长度（直接+一级索引表个数*索引表项数*文件块大小+二级个数*索引表项数^2*文件块大小，各级索引表最大不超过一个块）
     • 🌟根据顶级索引表结构计算出访存次数【如果索引表没有读入内存】
       • 直接索引两次读磁盘（读入混合索引表+访问）；
       • 一次间接地址：读入混合索引表+读入索引表+访问文件 3次读磁盘
       • 二级间接地址：读入混合索引表，读入一级表，读入二级表，访问文件 4次读盘
     • 优点：兼顾了小文件和大文件
   

文件的逻辑结构和物理结构概念对比（王道）

• 逻辑结构（从用户视角看）整个文件占用一片连续的空间
  • 逻辑结构决定文件内部信息的组织方式
  • 顺序文件的链式存储：用户视角，每个文件都被分配了一块连续的空间
  • 索引文件：索引用于索引变长文件中的记录的，在用户看来，文件依然是占用整片连续空间的；索引文件中的索引表完成关键字到记录存放的逻辑地址的映射
• 物理结构（从OS视角看）:把文件拆成若干个块，使用不同的方式（结构）存储在磁盘中，分散存储
  • 物理结构决定文件使用什么物理结构存储
  • 链式存储的顺序文件以及连接分配：链式存储是用户设计的（OS不关心），连接分配是由OS决定的（用户不关心）
  • 索引分配：索引分配是OS建立的，完成从逻辑块号到物理块号的映射

文件存储空间的管理

存储空间的划分与初始化

存储空间初始化：将物理磁盘划分为一个个文件卷，文件卷也可以由多个物理磁盘组成

将各个文件卷划分为目录区（FCB、索引结点、磁盘管理信息等）、文件区（存放文件数据）

关注问题：用什么方式记录、组织空闲块？如何分配空闲块？如何回收空闲块？

空闲表法

与内存动态分配方式雷同，为每个文件分配一块连续的存储空间。适用于连续分配的情况，空闲表中的每个表项对应一个空闲区，包括第一空闲盘块号以及空闲盘块数

• 空闲块分配：类似内存的分配算法，比如：首次适应算法、最佳适应算法、最坏适应算法等
• 回收空闲块：考虑回收区与空闲表中前后的连接与否来决定是否进行表项合并；分为：没有相邻空闲；前后都有空闲；前面有空闲和后面有空闲四种情况
• 优点：分配速度快、减少I/O请求次数

空闲链表法

• 空闲盘块链：以盘块为单位组成空闲链
  • 空闲块记录：OS保存链头、链尾指针
  • 分配：申请K个盘块，则从链头开始依次摘下K个盘块分配并且修改空闲链头指针
  • 回收：回收的盘块依次挂到链尾，并且更改链尾指针
• 空闲盘区链：以盘区为单位组成空闲链（第一个盘块会记录盘区长度
  • 空闲块记录：OS保存链头、链尾指针
  • 申请K个盘块：采用首次适应、最佳适应等算法从链头开始检索，按照算法规则找到大小符合要求的空闲盘区。如果每找到合适的连续空闲块，则用不同盘区的盘块同时分配给一个文件，分配后要修改对应的链指针、盘区大小等数据
  • 如何回收：回收区和空闲区相邻，则要合并到空闲盘区，如果不和任意一个盘区相邻，则把这个空闲盘区挂到链尾
  • 优点：离散、连续分配都适用，而且分配大片区域操作次数少

位示图法（连续分配、离散分配都适用）

lff:给定行列计算磁盘块块号,注意编址的开始

• 空闲块记录：位示图：每个二进制位对应一个盘块，0表示空闲，1表示已分配（或相反）；每一行表示一个字号，每一列表示位号，可以通过（字号，位号）确定一个盘块号，或使用（行号，列号）确定一个盘块号
  • 注意盘块号、字号、位号的起始位置
  • （字号，位号）=（i，j） 对应的盘块号b=ni+j；b号盘块对应字号i=b/n 位号j=b%n
• 分配：（0为空闲）
  1. 顺序扫描位示图，找到一个或一组为0的二进制位
  2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件
  3. 将相应的位设置为1
• 回收：根据回收的盘块号计算出位号和字号，将相应的二进制位设置为0

成组链接法

lff:数据结构的特点、(数据结构的解释)空闲盘块的分配和回收过程；空闲链表法是一种管理空闲磁盘块的方法
空闲链表法、空闲表法不适用于大文件系统，UNIX采用成组链接法对磁盘空闲块进行管理，空间盘块号栈一般放在内存中的超级块中

• 组织方式：
  • 空闲盘块号栈：存放当前可用的一组空闲盘块的盘块号（最多100个），以及栈中尚有的空闲盘块数N（同时还是栈顶指针）；一个分组中的块号不需要连续
  • 将每个空闲盘块分成若干组，每100个为一组
  • 将每组含有的盘块总数N和该组所有的盘块号计入前一组的第一个盘块的的S.free(0)~S.free(99)中
  • 最末一组只有99个盘块，其盘块号分别记入前一组S.free(1)和S.free(99)中，在S.free(0)中存放0（或者-1）表示空闲盘块结束，因为指向最末一组的盘块栈的第一条表项用来存放结束标志了;(在最后一个盘比其他盘块少一块真实可用的盘块，但还是会算成与其他组的盘块数量一样，因为最后一个盘块的最后一个盘块存放0或者-1表示盘块结束)
• 分配方法：
  1. 检查第一个分组的块数是否足够
  2. 如果足够，查看空闲盘块号栈是否上锁，如果未上锁，则从栈顶取出一空闲块号，将与之对应的盘块分给用户，栈顶指针向下移一格
  3. 如果待分配的盘块号是栈底，代表这hi当前栈中最后一个可分配的盘块号，由于该盘块号中记录有下一组可用的盘块号因此必须调用磁盘存储过程将栈底盘块号对应的盘块内容读入到栈中，作为新盘块号栈的内容，吧原栈底分配出去
• 回收方法：调用盘块回收过程进行回收，将回收的盘块号计入空闲盘块号栈的顶部，执行空闲盘块数+1，如果空闲盘块号数已经到100.栈已满，则把现有的100个盘块号计入新回收的盘块中，再将其盘块号作为新栈底
• 简答题：
  • 成组链接法是UNIX系统中的采用的空闲盘块的管理方式，它将一个文件卷的所有空闲盘块按固定大小分成若干组，并将每一组的盘块数和该组所有的盘块号记入前一组的最后一个盘块中，第一组的盘块数和该组所有的盘块号则记入超级快的空闲盘块号栈中。

实验

open什么意思，link什么意思 dup什么意思 mmap什么意思 lseek什么意思
open、close、read、write、dup（复制一个文件描述符）、link、unlink、mount、umount、mmap、lseek

open

int open(const char *pathname,flags,int perms)

参数详解：

pathname：被打开的文件名，可包含路径

flag ：文件打开的方式，参数可以通过“|” 组合构成，但前3 个参数不能互相重合。

O_REONLY ：只读方式打开文件
O_WRONLY ：可写方式打开文件
O_RDWR ：读写方式打开文件
O_CREAT ：如果文件不存在时就创建一个新文件，并用第三个参数为其设置权限。
O_EXCL ：如果使用O_CREAT 时文件存在，则可返回错误信息。这一参数可测试文件是否存在。
O_NOCTTY ：使用本参数时，如文件为终端，那么终端不可以作为调用open （）系统调用的那个进程的控制终端。
O_TRUNC ：如文件已经存在，并且以只读或只写成功打开，那么会先全部删除文件中原因数据。
O+APPEND ：以添加方式打开文件，在打开文件的同时，文件指针指向文件末尾。
perms：权限，可以用数字表示

返回值，成功返回文件描述符，失败返回-1

close

int close （int fd ）
函数输入值：fd ：文件描述符

函数返回值：成功：0 出错：-1

read

ssize_t read(int fd,void *buf,size_t count)
fd: 文件描述符

Buf ：指定存储器读出数据的缓冲区

Count ：指定读出的字节数

函数返回值：成功：读出的字节数 0 ：已到达文件尾 -1 ：出错

write

ssize_t write(int fd,void *buf,size_t count)
函数传入值：

fd: 文件描述符

Buf ：指定存储器写入数据的缓冲区

Count ：指定读出的字节数

函数返回值：成功：已写的字节数 出错 ：-1

lseek

用于在文件中移动文件指针位置的系统调用,，当打开一个文件时，除非指定O_APPEND选项，否则该偏移量被设置为0。
off_t lseek(int fd,off_t offset,int whence)

函数传入值：

fd: 文件描述符
Offset ：偏移量，每一读写操作所需要移动的距离，单位是字节的数量，可正可负（向前移，向后移）
Whence ：当前位置的基点：
    SEEK_SET ：当前位置为文件开头，新位置为偏移量的大小
    SEEK_CUR ：当前位置为文件指针位置，新位置为当前位置加上偏移量
    SEEK_END ：当前位置为文件的结尾，新位置为文件的大小加上偏移量大小

link unlink

用于创建文件的硬链接,系统调用或者命令

• 系统调用
  int link(const char *oldpath, const char *newpath);
  • oldpath 是现有文件的路径。
  • newpath 是新创建硬链接的路径。
  • 调用会在文件系统中创建一个新的硬链接，将新路径 newpath 映射到与旧路径 oldpath 相同的 inode 上。这意味着对硬链接的修改会影响到所有其他硬链接，因为它们实际上指向相同的数据块。
  • 删除int unlink(const char *pathname);
• 命令 link SOURCE TARGET或者 ln [参数][源文件或目录][目标文件或目录]
• 硬链接与软连接
  硬链接的意思是一个档案可以有多个名称，而软链接的方式则是产生一个特殊的档案，该档案的内容是指向另一个档案的位置。硬链接是存在同一个文件系统中，而软链接却可以跨越不同的文件系统。
  • 软链接：ln -s log2013.log link2013
    1. 软链接，以路径的形式存在。类似于Windows操作系统中的快捷方式
    2. 软链接可以 跨文件系统 ，硬链接不可以
    3. 软链接可以对一个不存在的文件名进行链接
    4. 软链接可以对目录进行链接
  • 硬链接:ln log2013.log ln2013
    • 硬链接只能链接到同一文件系统中的文件。
    • 删除一个硬链接并不会影响其他硬链接，直到最后一个链接被删除才会释放文件的 inode 和相关磁盘空间。
    • 硬链接不能链接目录。
  • 删除：unlink FILE

dup

• 用于复制文件描述符。这个系统调用创建一个新的文件描述符，指向与原始文件描述符相同的文件。这有助于在同一进程中多次引用相同的文件，或者在不同进程之间共享文件描述符。
• int dup(int oldfd);函数执行成功返回新的文件描述符，失败则返回-1。
• dup使用例子

mmap

• void *mmap(void *start, size_t length, int prot, int flags,int fd, off_t offset)

  start：用户进程中要映射的用户空间的起始地址，通常为NULL（由内核来指定）
  length：要映射的内存区域的大小
  prot：期望的内存保护标志
      PROT_READ：允许读取映射区域的内容。
      PROT_WRITE：允许写入映射区域的内容。
      PROT_EXEC：允许执行映射区域的内容。
      PROT_NONE：映射区域不可访问。
  flags：指定映射对象的类型
      MAP_SHARED：映射区域与文件关联，并且对映射区域的写入会反映到文件中。需要指定 fd 和 offset。
      MAP_PRIVATE：映射区域私有，对映射区域的写入不会反映到文件中。需要指定 fd 和 offset。
      MAP_ANONYMOUS：映射区域不与任何文件关联，而是用零填充。
      MAP_FIXED：如果指定地址 addr 不为 NULL，并且映射区域可以被放置到指定地址。
      MAP_DENYWRITE：阻止写入映射区域，对应于 PROT_WRITE。
      MAP_EXECUTABLE：与 PROT_EXEC 一起使用，表明映射区域可执行。
  fd：文件描述符（由open函数返回）
  offset：设置在内核空间中已经分配好的的内存区域中的偏移，例如文件的偏移量，大小为PAGE_SIZE的整数倍
  返回值：mmap()返回被映射区的指针，该指针就是需要映射的内核空间在用户空间的虚拟地址

• 典型代码段：

  fd=open(name, flag, mode);   
  if(fd<0)   
  ...   
  ptr=mmap(NULL, len , PROT_READ|PROT_WRITE, MAP_SHARED , fd , 0);  

• 参考
• 系统调用mmap()就是用来实现上面说的内存映射。最常见见的操作就是文件（在Linux下设备也被看做文件）的操作，可以将某文件映射至内存(进程空间)，如此可以把对文件的操作转为对内存的操作，以此避免更多的lseek()与read()、write()操作，这点对于大文件或者频繁访问的文件而言尤其受益。
• mmap将一个文件或者其它对象映射进内存。文件被映射到多个页上，如果文件的大小不是所有页的大小之和，最后一个页不被使用的空间将会清零。munmap执行相反的操作，删除特定地址区域的对象映射。
• 当使用mmap映射文件到进程后，就可以直接操作这段虚拟地址进行文件的读写等操作，不必再调用read，write等系统调用。但需注意，直接对该段内存写时不会写入超过当前文件大小的内容。
• 父子进程之间使用mmap
  • 使用特殊文件提供匿名内存映射：适用于具有亲缘关系的进程之间；由于父子进程特殊的亲缘关系，在父进程中先调用mmap()，然后调用fork()。那么在调用fork()之后，子进程继承父进程匿名映射后的地址空间，同样也继承mmap()返回的地址，这样，父子进程就可以通过映射区域进行通信了。注意，这里不是一般的继承关系。一般来说，子进程单独维护从父进程继承下来的一些变量。而mmap()返回的地址，却由父子进程共同维护。 对于具有亲缘关系的进程实现共享内存最好的方式应该是采用匿名内存映射的方式。此时，不必指定具体的文件，只要设置相应的标志即可.

题目

1. 对
2. 错
3. 书p135 MSDOS不采取存取保护措施，单用户
4. 对
5. D
6. B 动态重定位
7. A
8. 错 从创建进程的时候不保安含执行地址变换，运行时才执行变换

12/4题目
6.页表不会在cpu 快表mmu
7.逻辑地址转为物理地址
8.A对换
9.B虚拟内存
10.A硬件
11.

选择 填空 判断 简答 计算

LFF

提高磁盘I/O速度的途径就是增加设备缓冲区

第四章节

• 4.2 编译、连接、装入、执行====和虚拟存储系统有关系
  -分页也可以用动态链接，连续也可以用运行时地址的确定方式，没有必然联系-(删，只是别人的提问)
  虚拟地址在哪个阶段形成的？ 编译、连接、装入、执行 A：在编译阶段形成的；链接需要库函数，需要逻辑地址；
  程序的装入方式三种；主要的区别是地址确定的时机；
  - 静态链接：不便于程序共享，相对地址根据模块已经修改好了；
  - 一般是动态链接，对应的装入方式，好处：便于共享
  - 装入时动态链接，很难修改；可重入的程序才能进行动态运行装入
• 4.3 连续分配的存储管理方式
  只要是采用分区分配，一定都是连续分配的，区别在于分区的大小可能是相等或不等；和段式和页式的不同！
  单一连续分配给单个程序，多道程序分给多道程序，需要存储保护，为了保护个程序之间的；多道程序运行时有存储保护问题,目的是为了防止各道程序相互干扰
  空闲分区表和空闲分区链，记录整块内存；空闲分区链的结构
  分区分配算法
  • 一定要掌握最佳适应算法：
  • 分区回收方法有四种情况【项数变化情况】：上邻、下邻（只需要修改大小即可，空闲分区项数不增加）书p129；插入点前后都相邻，三个合并，删除一项，空闲分区表/链都少一项；没有上下邻，多一项
  • 紧凑了解一下，动态重定位和运行时动态链接是相关的；把逻辑地址转换成物理地址的过程，由操作系统进行地址重定位完成，需要硬件支持
• 对换 了解一下就好了
• 4.5 分页存储管理
  地址结构，多少个页面，页有多大，最多有多少个虚页（书）
  页表：
  - 为每个进程建立的页面映像表==?
  - 地址变换机构 地址重定位系统==?
  快表TLB：页表增加
  - 使用快表的目的：缩短进程访问内存的有效时间，加快访问内存的速度
  两级多级页表的目的：避免页表的连续存放,避免把页表连续放在内存中(但是找不到内存)
  - 多级页表不会减少访问内存的时间，不会避免缺页的中断问题，最主要的优点就是避免页表在内存中的连续存放
  - 多级页表地址，或者也可以叫（页目录号，页表项，页内地址）页目录项，页表项
  反置页表【知道概念】：按照内存空间建立的页表而不是按照虚拟地址建立的页表；按照内存的空间分页==？
• 分段存储方式
  分段，很了解；分段的特点（书上）：1.分段是用户行为，分段的地址空间是两维的

虚拟存储器

• 5.1
  请求分页页表机制，抖动，工作集（一点点，没听清）
• 5.2 请求分页页表机制
  根据程序需求，通过缺页中断，调页进入内存，根据局部性原理
  与请求分页相对的是预调页机制，主要是和工作集相关，工作集不属于请求调页系统，属于预调页系统
  • 请求页表机制：页表怎该的字段【状态，访问字段，修改位是必须有的，外存地址不一定会有】;各个字段的含义
  • 缺页中断：指令执行期间产生和处理的中断信号，和其它中断不同;缺页中断处理完成后，返回该指令，一定会重新执行一次发生缺页中断的指令
    • 一个例子：产生缺页中断的时候指令没有执行完，所以需要重新执行一次；普通中断一般是指令执行完毕之后产生的，因此解决后，直接执行吓一条指令
  • 还有一个问题：缺页中断一般由什么部件产生？一般都是由MMU产生 MMU内存管理单元
  • 缺页中断时OS做的事情：
    • 磁盘I/O（外存读取页面）；读取后，内存中的页表更新；执行缺页中断处理程序===？
      请求调页：页面置换算法 最佳置换是理论上的置换算法，FIFO LRU LFU CLOLCK都会实际被使用；实际上最佳置换不会被使用
• 抖动与工作集
  • 抖动产生的原因,重要，记下来：同时在进程中运行的（书p170）
  • 工作集用于预调页策略的实现：和预调页有关，定义（书p171）
  • 两种方式？？没听清===？
  • 抖动：经常看到danny的名字，书p184 MIT的（准则调节制约）知道它关于抖动的论述
  • 分段存储管理：分段地址程序中，用户地址是两维的，物理地址空间按照线性编址，物理地址空间不会进行两维划分；

输入输出系统

• **I/O软件的层次结构：**四个层次：(书p180)【没太听清楚】
  • 访问磁盘：柱面、磁道和扇区在哪一层被确定出来？？=========设备驱动程序与硬件直接相关，这些参数是由设备驱动程序算出来的
  • 设备驱动程序：本身和硬件相关；在设备驱动程序之间不能再使用OS的系统调用。既可以运行在核内，也可以运行在核外【没听清楚】20:37和硬件直接相关，实现系统对设备发出的操作指令；如果设备驱动程序中还有OS的系统调用，按理来说驱动程序的指令是用硬件执行的，不能再使用系统调用了；设备驱动程序中，不会出现系统调用
• I/O设备分为字符设备和块设备
  • 块设备一般是磁盘，Linux的文件系统是在块设备上实现的
• 与设备无关的设备：一般使用逻辑设备名访问物理设备，
• 磁盘的性能需要知道，6.8节磁盘访问时间书p232
• 先来先服务 最短寻道时间优先、电梯算法，等三个算法 平均寻道长度，例子，开始磁道号，要访问的磁道号，不同方式算出来的平均寻道长度不一样，最短寻道时间
• 调度算法的特性：最短优先，扫描，循环扫描dou会出现现象p235 出现磁臂黏着，FCFS不会出现

第七章 文件管理

• 关于文件的特性？
• 文件的逻辑结构：主要是早期的文件，现在常用的OS，文件是无结构的，是无结构的文件;好处：对文件的解释是依赖于具体的程序而不是OS来的，linux，中，大部分文件都是无结构的；【这里的无结构指的是逻辑结构无结构，但是组织方式是可以看到的，通常是树形的组织方式】
• 7，3 文件目录 文件控制块：要记录三类信息：基本（包括四类）、存取控制（包括什么）、使用信息（包括什么）
• 文件目录 通常是由几级目录；路径名和当前目录；当前目录的作用：加快文件的检索速度

磁盘存储器的管理

• 索引组织方式:单、多、增量（混合索引）；混合索引需要根据图来计算【会计算书上的内容】；给了逻辑地址偏移量，要知道用了一次间址还是两次间址；给定一个地址，这个地址不能叫文件偏移量（给定一个磁盘块号，确定使用几级索引）
• 文件的物理结构：共有三种，书p268；文件的物理结构取决于；
• 存储空间的管理方法：几个方法；位示图法：给定行列计算磁盘块块号；成组链接法，数据结构的特点，空闲盘块的分配和回收过程要会解释他的数据结构，【感觉要简答题】，这是一种管理空闲磁盘块的方法

没讲的不考，讲的就考

实验相关内容：

实验课主要针对文件进行，讲了文件相关的系统调用：open什么意思，link什么意思 dup什么意思 mmap什么意思 lseek什么意思

LFY小透

题型

1. 判断题–20分
2. 单选题–20分
3. 填空题–20分，一共20个空
4. 简答题–20分，一共5题，每题4分
5. 综合题–20分，一共3题，分别6、9、5分

出题分：lff

判断题

• 18、20为Linux题
  • 文件里保存的是一个个字节
  • 文件系统不归OS管
• 1个DOS题
  • DOS里面没有任何存储保护的措施（记就完事了）
• I/O指令一定是特权指令，必须运行在核内（这句话是错的）
  • 总之I/O指令不是特权指令（佛的标准）
• 缺页中断是由存储管理部件MMU引起的，不是由外部设备引起的
• 驱动程序不能使用系统功能调用（佛的标准）
• 页表项中的present（P位）会引起缺页中断

单选题

• 前7题为存储管理相关题目
• 8、9、11、12、15为设备管理
• 后4题为Linux/Unix相关
• 其他为文件系统
• 5题：逻辑地址是被开发者设定的，balabalabalabala（反正这道题佛说这题我们班选编辑，但是标准答案是编译）
• 8题：和文件系统层次有关
• 9题：关于驱动程序在OS中的位置：Unknown，可能在核内可能在核外，因为不同的系统有不同的实现方式
• 16题：空闲存储块的存储，位示图相关，需要计算
  • 推测是要根据盘号计算位示图位置
• 17题为Linux相关（关于设备的文件类型一个概念：块设备和字符设备）
• 19题：与引导块、超级块、索引结点区、数据区有关
  • 块设备由如上四个部分组成
  • 引导区存放开机相关信息
  • 超级块存放整个文件系统的信息
  • 每个文件系统的信息放在索引结点中，索引结点集中存放在索引结点区
  • 数据区存放文件中的数据
  • 目录文件放在数据区
• 20题送分题
• 有一题是文件名与文件目录的关系
• 有一题是磁臂粘着（？）相关，问你哪个算法（最短寻道SSFT）有磁臂粘着的问题
• 在Unix中不用文件名访问设备（总之选一个和文件名最相似的选项）
• 有一题与缺页中断有关，给四个关于缺页中断的论述，选一个错误的
  • 当前指令引发了缺页中断，在处理完之后，中断服务子程序会返回到该指令的起点，重新执行该指令

填空题

• 有一题是实验相关的Unix命令
• 其他题目（四道题）的知识点参考简答题复习大纲

简答题

• 存储管理两道题

  • 如何做地址映射
  • 多级页表的结构（两级页表）：
    • 知道结构、要会算页页框等的大小、会计算寻址范围之类的
  • 反置页表的概念
  • 缺页中断
    • 硬件无法解决的问题交由软件处理
    • 发生在指令的边界
  • 请求页表机制
  • 抖动与工作集：
    • 工作集：由Denning提出

• 文件系统两道题

  • 文件的逻辑结构和物理结构

  • 文件目录：

    • 文件控制快中包含哪些文件信息（7.3.1）

    • 文件路径如何转换成矮结点

      

  • 混合索引结构和成组链接法

• 设备管理一道题

  • I/O软件层次结构：（书6.1.2的那段话背出来）（来自佛的瑞萍：背下来抄上去分就拿到手了）

    

  • Spooling（这一部分讲得比较模糊）

  • 磁盘：

    • 有哪些磁盘
    • 磁盘的访问时间（寻道时间、旋转时间、读些时间）

• 第五章有道题与调度算法有关

综合题

• 第五大题第一小题（要么设备管理要么存储管理）：

  • 如果是设备管理：
    • 磁盘调度算法（电梯算法）
  • 如果是存储管理：
    • 存储管理算法

• 第五大题第二小题为9分的大题，磁盘存储器的管理：

  第一问考混合索引方式的计算——“某文件系统的内部索引有7个索引项，4直接地址1个一级间址2个二级间址（没有3级）”，两项计算内容，一个已知文件地址算设备地址（比如已知地址为xxx，问文件长度是多少，或者计算IO次数）

  第二问没说

  找到一道可能的原题：

  【2010 考研 408 统考真题】设文件索引结点中有 7 个地址项，其中 4 个地址项是直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4B，若磁盘索引块和磁盘数据块大小均为 256B，则可表示的单个文件的最大长度？

  答案：根据题目描述，一共 7 个地址项，前 4 个为直接地址项，也就是说，如果这些盘块用来装文件，就直接装，因为盘块大小都为 256 B，所以前四个盘块我们可以装 4*256 B 大小的文件。

  接下来再来看，一共有 2 个一级间址（间接地址），也就是说，5，6 号盘块现在不用来装实际的文件数据了，而是用来装一组间接的地址，因为一个地址项有 4B 大小，所以一个盘块可以装 256/4 B 的地址，也就是 5，6 号盘块一共可以装 2*（256/4）B = 128B 这么多的地址，而这些地址（指针）将会（一对一）指向其他的空的盘块，正如我们知道的一个盘块 256B ，所以一级间址一共可以装 2*（256/4）256 B 的文件。就是说 128B 大小的地址中，每个地址指向的一个盘块有 256B，一共就是 2（256/4）*256 B 多的文件。

  二级间址，乃至三级间址都是一样的计算方式，你可以先自己尝试一下，然后再看下面的解答。

  ok，题目告诉一共有一个二级间址，就是说我现在 7 号盘块分成 128B 装地址，这些地址指向的盘块又被用来装地址（一级间址的时候只有一次磁盘块用来存储地址），也就是 （256/4）（256/4）这么多个地址，每个地址都指向一个盘块（256B），所以结果是 （256/4）（256/4）*256

  而题目问的最大的单个文件，就是指直接地址，一级间址，二级间址一共可以用的空间大小，就是把上面计算的值加起来：4256 B + 2（256/4）256 B + （256/4）（256/4）*256 = 1082368 B = 1057KB

  操作系统中的多级间址计算题_操作系统文件间接地址题-CSDN博客

• 大题或者简答题必考一道成组链接法

• 第五大题第三小题：

  考察linux系统功能调用

  佛的小例子：open、close、read、write、dup（复制一个文件描述符）、link、unlink、mount、umount、mmap、lseek

  严重怀疑是最后两个（因为佛看了眼手机再写到黑板上去的），link和unlink也强调了一下