一. 操作系统引论
二. 进程的描述和控制
三. 处理机调度和死锁
四. 存储器管理
五. 虚拟存储器
六. 输入输出系统
七. 文件管理
八. 磁盘存储器的管理
九. 操作系统接口
十. 多处理器操作系统

1. 操作系统引论

1.1 操作系统的目标和作用

  • 操作系统的目标：方便性，有效性，可扩充性，开放性

  • 操作系统的作用：OS作为用户与计算机硬件系统之间的接口, 计算机资源的管理者, 实现了计算机资源的抽象

1.2 操作系统的发展过程

  • 未配置操作系统的计算机系统
  • 单道批处理系统
  • 多道批处理系统：资源利用率高，系统吞吐量大，平均周转时间长，没有交互能力
  • 分时系统：多路性，独立性，及时性，交互性
  • 实时系统

1.3 操作系统的基本特征

  • 并行和并发
并行 两个或多个事件在同一时刻发生
并发 两个或多个事件在同一时间间隔发生

  • 引入进程

  • 共享：互斥共享方式，同时访问方式

  • 虚拟：时分复用与空分复用

  • 异步

1.4 操作系统的基本功能

  • 进程控制：为使作业并发执行，为其创建一个或多个进程，并为其分配必要的资源
  • 进程同步：使多个进程相互协调，常用互斥与同步
  • 进程通信：进程之间的信息交互，IPC
  • 调度：作业调度与进程调度

  • 内存分配：为程序分配内存空间，提高存储器利用率，尽量减少内存碎片，允许正在运行的程序申请追加的内存空间

    OS在实现内存分配时，可以采用静态和动态两种方式

  • 内存保护：确保每道用户程序都仅在自己的内存空间运行，彼此互不干扰，不允许用户程序访问操作系统的程序和数据

    需要采用内存保护机制，如设置两个界限寄存器

  • 地址映射：在硬件的支持下，将线性地址空间中的逻辑地址转换为内存空间中与之相对应的物理地址

  • 内存扩充：采用虚拟存储技术，从逻辑上扩展内存

  • 缓冲管理：在IO设备和CPU之间引入缓冲，可以有效地缓和CPU和IO设备速度不匹配的矛盾，提高CPU的利用率，进而提高系统的吞吐量
  • 设备分配：根据用户进程的IO请求，系统现有的资源情况以及分配策略，为之分配所需的设备
  • 设备处理：设备驱动系统，实现CPU和设备控制器
  • 文件储存空间的管理：为文件分配外存空间，提高外存利用率
  • 目录管理：为每个文件建立一个目录项，从外存中读取数据
  • 文件的读写管理和保护：利用读写指针对文件进行读写操作，同时实现存取控制

1.5 OS的结构设计

  1. 传统操作系统的结构：

    • 无结构操作系统

    • 模块化操作系统

      将操作系统的功能分为若干个具有一定独立性的模块

      内聚性:模块内部各部分之间的紧密程度,内聚性越高,模块独立性越强

      耦合度:模块间相互联系和相互影响的程度,耦合度越低,模块独立性越好

    • 分层式结构OS

  2. 客户/服务器模式

  3. 面向对象的程序设计

  4. 微内核OS结构

    • 足够小的内核
    • 基于客户/服务器模式
    • 应用机制与策略分离原理
    • 采用面向对象技术

2. 进程的描述与控制

2.1 进程的控制

在多道程序环境下，程序的执行属于并发执行，此时它们将失去封闭性，并具有间断性，因此通常的程序不能参与并发执行，因此引入进程概念

为了使参与执行的每个程序都能独立运行，在操作系统中必须配置一个专门的数据结构，即PCB

创建进程就是创建进程实体的PCB，PCB，程序段和相关的数据段组成了进程的实体

  • 进程的特征：动态性，并发性，独立性，异步性
  • 进程的三种基本状态：
    1. 就绪状态（Ready）：进程已经被分配到除了CPU以外的所有必要资源，只要获得CPU就可以立即执行
    2. 执行状态（Running）：程序正在执行
    3. 阻塞状态（Block）：正在执行的进程由于发生某事件（如I/O请求）暂时无法继续执行的情况
  • 创建状态和终止状态：
    • 创建状态：创建一个空的PCB，并向PCB中填写用于控制和管理进程的信息，并为其分配运行必须的资源
    • 终止状态：等待操作系统进行善后处理，最后将PCB清零返还系统

  • 挂起操作和进程状态的转换

    在许多系统中除了就绪执行和阻塞三种基本的状态之外，还引入了进程的挂起操作

    当该操作作用于某个进程时，意味着此进程进入静止状态，暂停执行并且暂时不接受调度

2.2 进程管理中的数据结构

  1. 操作系统中用于管理控制的数据结构：内存表，文件表，设备表，进程表

  2. PCB的信息

    • 进程标识符：外部标识符，内部标识符
    • 处理机状态：寄存器，指令计数器，用户栈指针
    • 进程调度信息
    • 进程控制信息

  3. 进程控制块的组织方式：线性方式，链接方式，索引方式

2.3 进程控制

进程控制指进程管理中最基本的功能，主要包括创建新进程，终止已完成的进程，将发生异常情况而无法继续运行的进程置于阻塞状态，进程控制一般是由OS的内核中的原语来实现的。

操作系统内核主要包含了以下两大方面的内容：支撑功能，资源管理功能

  • 进程的创建：创建进程的进程称为父进程，被创建的进程是子进程，子进程可以继续创建进程，组成了一个进程家族，引起创建进程的事件有：用户登录，作业调度，提供服务，应用请求
  • 进程的终止：引起进程终止的时间：正常结束，异常结束，外界干预（操作系统，父进程），终止过程：根据进程标识符找到PCB，如果进程正在执行，终止执行状态，置调度标志为1，若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程，将被终止进程的所有资源归还给父进程，将被终止进程PCB从所在队列中移除
  • 引起进程阻塞或者唤醒的事件：向系统请求共享资源失败，等待某种操作的完成，新数据尚未到达，等待新任务的到达

2.4 进程同步

进程同步机制的主要任务是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间按照一定的规则共享系统的资源。两种相互制约关系：简介相互制约关系，直接相互制约关系

  • 临界资源：硬件资源等需要采用互斥方式实现共享

  • 临界区：每个进程中访问临界资源的代码成为临界区

  • 硬件同步机制

    1. 关中断：在临界区执行时不会响应中断，从而不会发生进程调度
    2. Test-and-Set指令实现互斥
    3. 使用Swap指令实现进程互斥

  • 信号量机制（整型信号量，记录型信号量，AND型信号量）

  • 经典进程同步问题：生产者-消费者问题，哲学家进餐问题，读者-写者问题

2.5 进程通信IPC

  • 进程通信的类型

    1. 共享存储器系统
    2. 管道通信系统：进程通过向管道文件发送字节流，共享数据
    3. 消息传递系统：直接通信和间接通信
    4. 客户机-服务器系统：套接字，远程过程调用和远程方法调用

  • 消息传递机制通信的实现方式

    1. 直接消息传递系统：直接通信原语
    2. 信箱通信：属于间接通信方式，进程间的通信需要通过某种中间实体来完成该实体建立在随机存储器的公用缓冲区上，暂存发送进程发送给目标进程的消息，系统为信箱的创建和接收信息提供了原语

2.6 线程的基本概念

线程是比进程更小的基本单位，引入的目的是进一步提高程序的并发执行的程度

  • 进程的两个基本属性：京城是一个可以拥有资源的独立单位，进程同时又是一个可独立调度和分派的基本单位
  • 进程和线程的比较：
    1. 调度的基本单位：在传统OS中，进程是能够运行的基本单位，每次被调度时都需要切换上下文，开销较大，引入线程后，将线程作为独立运行的基本单位，当线程切换时，仅需保存和设置少量的寄存器，切换代价小于进程，同时在同一进程中线程的切换不涉及进程的切换
    2. 并发性：在引入线程之后，不仅进程之间可以并发进行，并且在一个进程中的多个线程亦可以并发执行
    3. 拥有资源：进程可以拥有资源并作为拥有资源的一个基本单位，但线程本身没有系统资源，而是仅有一点必不可少的，能保证独立运行的资源，如TCB，进程除了拥有自己的少量资源外，还允许多个线程共享该线程所拥有的资源，属于同一个进程的所有线程都有相同的地址空间
    4. 独立性：在同一进程中的不同线程的独立性比不同进程之间的独立性低得多，每一个进程都有一个独立的地址空间和其他资源，而同一进程中的不同线程为了提高并发性，每个线程可以访问他们所属进程的地址空间的所有地址
    5. 系统开销：在创建和撤销进程时，系统都要位置分配和回收进程控制块和其他资源，OS的开销远大于线程创建和撤销时付出的开销
    6. 支持多处理机系统：对于多处理机系统，可以将多线程进程的多个线程分配到不同的处理机上，使其并行执行，即多线程
  • 线程运行的三个状态：执行状态，就绪状态，阻塞状态

2.7 线程的实现

  1. 内核支持线程KST
  2. 用户级线程ULT
  3. 组合方式

3. 处理机调度与死锁

3.1 处理机调度的层次和调度算法的目标

  • 处理机调度的层次：高级调度，低级调度，中级调度
    1. 高级调度：又称长程调度，调度对象是作业，将外存中位于后被队列中的作业调入内存，为其创建进程，主要用于多批道处理系统
    2. 低级调度：调度对象是进程，主要功能是根据某种算法，决定就绪队列中的哪个进程应该获得处理机
    3. 中级调度：又称为内存调动，把暂时不需要的进程移动到外存等待，提高内存利用率
  • 处理机调度算法的共同目标是提高资源利用率，公平性，平衡性和策略强制执行

3.2 作业与作业调度

  • 作业：比程序更加广泛的概念，不仅包含了通常的程序和数据，还包含一份作业说明书，在多批道处理系统中，以作业为基本单位从外存调入内存
  • 作业步：每个作业都需要若干个互相独立的顺序加工才能得到结果，每一步成为一个作业步
  • 作业控制块：包含作业标识，用户名称，用户账号，和作业类型等的数据结构
  • 作业运行的三个状态：收容状态，运行状态，完成状态
  • 作业调度：
    1. 先来先服务（FCFS）调度算法
    2. 短作业优先（SJF）调度算法：必须预知作业运行的时间，对长作业非常不利，不能保证紧迫性作业及时得到处理
    3. 优先级（PSA）调度算法
    4. 高响应比优先调度算法：优先级=（等待时间+要求服务时间）/要求服务时间
  • 进程调度任务：保护处理机的现场信息，按照某种算法选取进程，把处理器分配给进程
  • 进程调度方式：非抢占方式，抢占方式
  • 调度算法
    1. 轮转调度算法：时间片轮转（RR）调度算法，系统的所有就绪进程按照FCFS策略排成一个就绪队列，在当前进程运行完成或者时间片用完时激活进程调度程序，若此时当前程序没有运行完将其送往调度程序的队末
    2. 优先级调度算法：分为抢占式和非抢占式，优先级为静态优先级或者动态优先级
    3. 多队列调度算法：将不同类型的进程固定分配在不同队列，实施不同的调度算法
    4. 多级反馈队列：设置多个就绪队列，并为每个就绪队列赋予不同的优先级，越前的队伍优先级越高，队伍优先级越高，时间片就越小，每个队伍都采用FCFS算法，当进程进入内存后先将其放入第一个队列的末尾，如果该进程能在规定的时间片内完成，便可撤离，否则进入第二队队尾等待，当进程最后被降级到最后一个队列时，采取RR方式运行。同时队列间按照优先级调度，当优先级高的队列空时，才会调度低优先级的队列。
    5. 基于公平原则的调度算法

3.3 实时调度

  • 实现实时调度的基本条件：提供实施调度的基本信息，系统处理能力抢，采用抢占式调度机制，具有快速切割机制

  • 最早截止时间优先（EDF）算法：任务完成的截止时间越早，优先级越高

  • 最低松弛度优先（LLF）算法：该算法在确定任务的优先级时，根据人物的紧急程度，任务的紧急程度越高，使其先执行

  • 优先级倒置：

    1. 优先级倒置的形成：高优先级进程和低优先级进程共享临界资源而被低优先级资源阻塞
    2. 优先级倒置的解决方案：动态优先级继承，即在高优先级进程进入临界区之后，如果有低优先级进程正在使用临界资源，则阻塞高优先级进程，使低优先级进程继承其优先级

3.4 死锁

竞争不可抢占性资源引起死锁

竞争可消耗性资源引起死锁

进程推进顺序不当引起死锁

  • 死锁的定义：如果一组进程中的每一个进程都在等待该组进程中的其他进程才能引发的事件，那么该组进程是死锁的
  • 产生死锁的必要条件：
    1. 互斥条件
    2. 请求和保持条件
    3. 不可抢占条件
    4. 循环等待条件
  • 处理死锁的方法：
    1. 预防死锁：设置限制，破坏四种条件的产生
    2. 避免死锁：在资源的动态分配中加入某种方法防止系统进入不安全条件
    3. 检测死锁
    4. 解除死锁：撤销一些进程回收资源

3.5 预防死锁

针对条件 措施
“请求与保持” 所有协议在开始之前必须请求所有运行时需要的资源，进程在运行中逐步释放已经用完的资源
“不可抢占” 已经保持了不可抢占资源的进程在提出新的资源请求无法被满足时，必须释放已经保持的所有资源
“循环等待” 对资源进行线性排序，只能单向地请求资源

3.6 避免死锁（最大需求+已分配）

在死锁避免方法中，将系统的状态分为安全状态和不安全状态，在安全状态中可以避免发生死锁，因此应避免系统进入不安全状态

常利用银行家算法避免死锁，每一个新进程进入系统时，都要申明在运行过程中需要的每种资源的最大单元数目，系统在分配资源时需确定是否有足够的资源分配给该进程

3.7 死锁的检测和排除

  • 死锁的检测：某状态的资源分配图不能完全简化则发生死锁
  • 死锁的排除：终止所有进程，或逐个终止进程直到拥有足够的资源

4. 存储器管理

4.1 存储器的层次结构

寄存器和主存储器又称为可执行存储器，与外存的访存机制不同

寄存器的访问速度最快，高速缓存介于寄存器和主存之间，磁盘缓存用户缓和磁盘IO和主存访问速度的不匹配

4.2 程序的装入和链接：

用户程序要在系统中运行，需要先装入内存，然后将其转变为一个可以执行的程序，需要以下步骤

  1. 编译：由编译程序将用户程序编译成若干个目标模块
  2. 链接：由链接程序将编译后的一组目标模块以及他们需要的库函数链接在一起，形成一个完整的装入模块
  3. 装入：由装入程序将装入模块装入内存

4.3 连续分配存储管理方式

为了将用户程序装入内存，必须为其分配一个一定大小的内存空间

连续分配存储中代码和数据的逻辑地址相邻，体现在内存分配时物理地址的相邻

常用的连续分配方式分为四类：单一连续分配，固定分区分配，动态分区分配和动态可重定位分区分配

  1. 单一连续分配：在用户区内存中仅有一道用户程序（单任务操作系统）

  2. 固定分区分配：内存的用户空间划分成若干固定大小的分区，分区大小可以固定也可以不等

  3. 动态分区分配：根据进程的实际需要，动态地为之分配内存空间，涉及到分区分配中使用的数据结构，分区分配算法和分区的分配与回收操作三方面的问题

    • 数据结构：空闲分区表，空闲分区链

    • 基于顺序搜索的动态分区分配算法

      1. 首次适应（FF）算法
      2. 循环首次适应（NF）算法：从上次找到的空闲分区开始查找
      3. 最佳适应（BF）算法：空闲分区链按容量从小到大排列
      4. 最坏适应（WF）算法：:与BF相反，不易产生碎片

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

      1. 快速适应算法
      2. 伙伴系统
      3. 哈希算法

  4. 动态可重定位分区分配

4.4 交换技术（swapping）

将内存中暂时不用的程序或者数据换出到外存上，以便腾出足够的内存空间，再把已经具备运行条件的进程或者程序和数据换入内存

  • 交换的类型：整体交换，页面交换

4.5 分页存储管理方式

将进程分散地装入到许多不相邻接的分区中，可以充分地利用内存空间，即离散式分配方式

分页存储管理方式，分段存储管理方式，段页式存储管理方式

  1. 分页存储管理的基本方法：

    • 页面和物理块：分页存储管理将进程的逻辑空间分成若干个页，并为各页编号，相应的也为内存空间分割编号，在进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻的物理块中，易形成页内碎片
    • 分页地址：分页地址包含页号和位移量两个部分，位移量即页内地址
    • 页表：在分页系统中，系统为每个进程建立了一张页面映像表，简称页表，记录页号对应的内存块号，实现了页号到物理块号的地址映射
  1. 地址变换机构：实现从逻辑地址到物理地址的转换，借助页表完成

​ 页表大部分滞留在内存中，系统保留一个页表寄存器，进程未执行时，页表的始址和页表长度保存在本进程的PCB中，当调度到该进程时，再将其装入页表寄存器，因此系统仅需一个页表寄存器，当进程要访问某个逻辑地址中的数据时，转换机构将有效地址分为页号和页内地址两个部分，以页号为索引去检索页表，若页表大于或等于页表长度，则发生越界中断，否则将页表始址和页表长度的乘积相加，得到该表项在页表中的位置，于是得到该页的物理块号，将其装入物理地址寄存器。为了提高地址变换效率，在高速缓存中增设快表。

  1. 访问内存的有效时间：从进程发出指定逻辑地址的访问要求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所花费的总时间

  2. 两级和多级快表

    • 两级页表：为离散分布的页表建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号
{% qnimg image-20200828135043309.png %}
  • 多级页表：多用于64位计算机
  1. 反置页表

4.6 分段存储管理方法

通常程序要分为若干个段，为了实现使用段号+段内偏移量的方式寻址，需要引入分段存储，为了方便起见，每个段用一个段号来代替 ，每个段都使用0开始编址，分段地址中的地址包括段号和段内地址。系统为每个分段分配一个连续的分区，进程中的各个段可以离散地装入到内存的不同分区中。段表中记录了某个段的段长和基址，进程可以通过段表找到对应的内存区

  1. 分段存储地址变换：

  1. 分段和分页的主要区别：

    • 页是信息的物理单位，采用分页存储方式是为了实现离散分配，实现系统管理的需要，对于用户是不可见的，而段则是信息的逻辑单位，含有相对完整的信息，用于更好地满足用户需求
    • 页的大小固定且由系统决定，直接使用硬件实现，而段的长度不固定，由编译程序根据信息的性质进行划分
    • 分页的用户地址空间是一维的，分页完全是系统的行为，因此在分页中用户程序的地址是属于单一的线性地址空间，而分段是用户的行为，在分段中用户的地址空间是二维的

  2. 信息共享

    分段系统易于进行段的共享，即允许若干个进程共享一个或多个分段

4.7 段页式存储管理方式

  1. 基本原理：段号，段内页号，以及页内地址
  1. 地址变换过程

5. 虚拟存储器

5.1 概述

具有请求调入功能和置换功能，能从逻辑上对内存的容量加以扩充的一种存储器系统

  • 虚拟存储器的特征：多次性，对换性，虚拟性
  • 虚拟存储器的实现：分页请求系统，请求分段系统

5.2 请求分页存储管理方式

  • 请求页表机制：除了页对应的物理块号，页表还应包含状态位（是否调入内存），访问字段，修改位，外村地址

  • 缺页中断机制：在请求分页系统中，当所要访问的页面不在内存中时，便会产生缺页中断请求OS将页调入内存

  • 地址变换机构

  • 请求分页中的内存分配：最小物理块数的决定，内存分配策略，物理块分配算法

  • 页面调入策略

    1. 影响缺页率：页面大小，进程分到的内存块数，页面置换算法，程序固有特性
    2. 何时调入：预调页，请求调页
    3. 何处调入：兑换区（连续），文件区（离散）

5.3 页面置换算法

  1. 最佳（optimal）置换算法：选择淘汰的是最长未来时间不会使用的
  2. 先进先出（FIFO）页面置换算法
  3. 最近最久未使用（LRU）置换算法
  4. 最少使用（LFU）置换算法：页面访问图和LRU完全相同
  5. Clock置换算法
  6. 页面缓冲算法（PBA）

6. 输入输出系统

I/O系统的主要对象是I/O设备和相应的设备控制器，其最主要的任务是，完成用户提出的I/O请求，提高I/O速率，以及提高设备的利用率，并能为更高层的进程方便地使用这些设备提供手段

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

  1. 基本功能：隐藏物理设备的细节，与设备的无关性，提高处理机和I/O设备的利用率，对I/O设备进行控制，确保设备的正确共享，错误处理

  2. I/O系统的层次结构和模型

    • I/O软件组织分为四个层次：用户层I/O软件，设备独立性软件，设备驱动性软件，中断处理程序
    • I/O系统中各模块之间的层次：I/O系统的上（OS）下（硬件）接口

  3. I/O设备接口：块设备接口，流设备接口，网络设备接口

6.2 I/O设备和设备控制器

  1. I/O设备的分类：按照使用特性分类，按照传输速率分类

  2. 设备和控制器之间的接口：数据信号线，控制信号线，状态信号线

  3. 设备控制器：

    • 设备控制器的基本功能：接受和识别命令，数据交换，标识和报告设备的状态，地址识别，数据缓冲区，差错控制
    • 设备控制器的组成：设备控制器和处理机的接口，设备控制器和设备的接口，I/O逻辑

  4. 内存映像I/O

    驱动程序将抽象的I/O命令转换出一系列具体的命令，由控制器执行这些命令

    • 利用特定的I/O指令
    • 内存映像I/O

  5. I/O通道

    虽然有设备控制器，当主机的外设很多时，CPU的负担很重，为此在CPU和设备控制器之间又增设了I/O通道，其主要目的是为了建立独立的I/O操作，使得一些原来有CPU执行的I/O任务由I/O通道来处理

    • 通道类型：字节多路通道，数组选择通道，数组多路通道

6.3 中断机制和中断处理程序

  1. 中断和陷入：外中断，内中断（陷入），主要区别是信号的来源来自CPU的内部和外部

  2. 中断向量表和中断优先级

  3. 多中断源的处理：屏蔽中断，嵌套中断

  4. 中断处理程序：但一个进程请求I/O操作时，该进程被挂起，知道I/O设备完成操作时，向CPU发送一个中断请求，CPU响应后转向中断处理程序，处理完成后解除相应进程的阻塞状态

    • 测定是否有未响应的中断信号
    • 保护被中断进程的CPU环境
    • 转入相应的设备处理程序
    • 中断处理
    • 恢复CPU的现场并退出中断（当采用嵌套中断，可以处理优先级更高的中断）

6.4 设备驱动程序

  1. 设备驱动程序的功能：

    • 接受由与设备无关的软件发来的命令和参数，并将命令中的抽象要求转换为与设备相关的底层操作序列
    • 检查用户I/O请求的合法性，了解I/O设备的工作状态
    • 发出I/O命令
    • 及时响应由设备控制器发来的中断请求

  2. 对I/O设备的控制方式：

  • 使用轮询的可编程I/O方式
  • 使用中断的可编程I/O方式
  • 直接存储器访问方式：数据的传输单位是数据块，从设备直接送入主存，仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的，进一步提高了CPU和I/O设备的并行操作程度

6.5 与设备无关的I/O软件

为了使实现设备独立性，在现代OS中增加了与设备无关的I/O软件，应用程序中使用的设备，不局限于某个具体的物理设备，为每个设备所需的设备驱动程序是与硬件紧密相关的软件，为了实现设备独立性，必须在设备驱动程序上设置一层软件，称为与设别无关的I/O软件

  • 从物理设备名到逻辑设备名，实现了逻辑设备名到物理设备名的转换
  • 设备驱动程序的统一接口，缓冲管理，差错控制，对独立设备的分配和回收，独立于设备的逻辑数据块

6.6 用户层的I/O软件

  1. 系统调用和库函数

    用户态的应用无法直接调用系统态中的OS过程，可以通过系统调用间接调用OS中的I/O过程，对I/O设备进行操作

6.7 缓冲区管理

  1. 缓冲的引入

    • 缓和CPU和I/O设备间速度不匹配的矛盾
    • 减少对CPU的中断频率，放宽CPU中断时间的限制
    • 解决数据粒度不匹配
    • 提高CPU和I/O设备的并行性

  2. 单缓冲区，双缓冲区，环形缓冲区

6.8 磁盘存储器的性能和调度

  1. 数据的组织和形式：磁盘设备可包含多个物理盘片，每个磁盘片可包含两个盘面，每个盘面有若干个磁道，磁被分为多个扇区

  2. 磁盘的类型：固定头磁盘，移动头磁盘

  3. 磁盘访问时间：寻道时间+旋转延迟时间+传输时间

  4. 早期的磁盘调度算法：

    • 先来先服务（FCFS）
    • 最短寻道时间优先（SSTF）

  5. 基于扫描的磁盘调度算法

    • 扫描（SCAN）算法
    • 循环扫描算法（CSCAN）：规定单向扫描
    • NStepSCAN和FSCAN算法

7. 文件管理

7.1 文件和文件系统

  1. 文件系统的层次结构
  2. 文件操作

7.2 文件的逻辑结构

文件有两种文件结构：逻辑结构，物理结构

按照文件的组织形式可以分为顺序文件，索引文件和索引顺序文件

  • 顺序文件：串结构，顺序结构
  • 索引文件：按照关键字建立索引，可以具有多个索引表
  • 索引顺序文件：以及索引顺序文件，两级索引顺序文件

7.3 文件目录

  1. 文件控制块（FCB）

    • 基本信息：文件名，文件物理位置，文件逻辑结构，文件物理结构
    • 存取控制信息
    • 使用信息类

  2. 索引节点：每个文件都有一个唯一的磁盘索引节点

  3. 简单的文件目录：单级文件目录，两级文件目录

  4. 树形结构目录

7.4 文件共享

  • 基于有向无循环图
  • 利用符号链

7.5 文件保护

为了确保文件系统的安全，主要采取三方面的措施：

  1. 通过存取控制，防止人为造成的文件不安全
  2. 通过系统容错技术，防止系统部分的故障造成的文件不安全
  3. 建立后备系统，防止由于自然原因的不安全
  • 保护域，访问矩阵

8. 磁盘存储器的管理

8.1 外存的组织方式

  • 连续组织方式，链接组织方式，索引组织方式

  1. 连续组织方式

    连续组织模式又称为连续分配模式，要求为每一个文件分配一组相邻接的盘块，通常位于同意磁道上，读取时不必移动磁头，顺序访存快且速度快，单易产生外部碎片，必须事先知道文件的长度且不能灵活地删除或者插入记录，对于动态增长的文件很难预先知道文件的最终大小

  1. 链接组织方式

    为文件分配不连续的盘块，再通过每个盘块上的指针，将属于同一文件的离散的盘块链接成一个链表，消除了外部碎片，且插入删除都很容易

  1. 隐式链接：在文件目录的每个目录项中含有指向链接文件第一个盘块和最后一个盘块的指针，每个盘块包含下一个盘块的指针

  2. 显示链接：通过FAT表显式记录各物理块的链接，显著提高了检索效率，减少了访问磁盘的次数

    FAT技术：FAT12,FAT16,FAT32

  1. 索引组织方式：

    • 单极索引组织方式
  • 多级索引组织方式
  • 增量式索引组织方式

8.2 文件存储空间的管理

  • 空闲表法和空闲链表法

    使用方式和内存的动态分配相似，动态链表包括空闲盘块链和空闲盘区链

  • 位示图法

    利用二进制的一位表示磁盘的一个盘块的使用情况，形成一个二维数组表示每个盘块是否已经被分配，称为位示图

    盘块的分配：在位示图中找到足够的未被分配的盘块，根据位示图中的行号和列号得到盘号，并更改其标志位

    盘块的回收：根据盘号得到其在位示图中的位置，修改位示图

  • 成组链接法

8.3 提高磁盘I/O速度的途径

改进对文件的访问速度，可以从三方面入手：

  1. 改进文件的目录结构以及检索目录的方法减少对文件的查找时间
  2. 选取好的文件存储结构，以提高对文件的访问速度
  3. 提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中

  1. 磁盘高速缓存：在内存中为磁盘盘块设置一个缓存区，访问磁盘的请求会先访问缓存区

    • 数据交付方式：数据交付，指针交付
    • 置换算法：访问频率，可预见性，数据的一致性
    • 周期性写回磁盘

  2. 提前读

  3. 延迟写

  4. 优化物理块的分布

  5. 虚拟盘

  6. 廉价磁盘冗余阵列

8.4 提高磁盘可靠性的技术

  • 第一级容错技术：双份目录和双份文件分配表
  • 第二级容错技术：磁盘镜像，磁盘双工
  • 基于集群技术的容错功能
  • 后备系统

9. 操作系统接口

  • 用户接口：命令行接口，图形界面接口

  • shell命令语言

  • 系统调用的概念和类型

    通常情况下OS的内核运行在系统态，而应用程序运行在用户态

    • 系统态和用户态：特权指令运行在系统态，非特权指令运行在用户态，在实际运行过程中，处理机会在系统态和用户态之间切换
    • 系统调用：使应用程序间接调用OS中的相关过程，通过中断机制实现
    • 系统调用的类型：进程控制类系统调用，文件操纵类系统调用，进程通信类系统调用

10. 多处理机操作系统