四、操作系统

发表于 分类于

1 操作系统概述

1.1 操作系统的基本概念

1.1.1 操作系统定义及作用

  • 定义：操作系统是计算机系统的核心系统软件，用于管理软硬件资源，组织计算机工作流程，控制程序执行，并为用户提供准确良好的工作环境和友好的接口。
  • 作用：
    • 提高计算机系统的效率。
    • 改善人机界面，提高用户工作效率。

1.1.2 操作系统的特征与功能

  • 特征：并发性、共享性、虚拟性和不确定性。
  • 功能：
    • 进程管理：管理 CPU 的执行时间，采用多道程序等技术合理分配 CPU 时间。
    • 文件管理：管理文件存储空间、目录管理、文件的读写管理和存取控制。
    • 存储管理：管理主存储器空间，包括分配与回收、存储保护、地址映射和主存扩充。
    • 设备管理：管理硬件设备，包括分配、启动、完成和回收。
    • 作业管理：管理任务、界面、人机交互等。

1.2 操作系统分类及特点

1.2.1 批处理操作系统

  • 单道批处理：早期系统，一次只有一个作业在内存中，依次执行多个作业。
  • 多道批处理：允许多个作业同时在内存中执行，提高资源利用率。

1.2.2 分时操作系统

  • 特点：多路性、独立性、交互性和及时性。
  • 功能：将 CPU 时间划分为时间片，轮流为多个终端用户服务。

1.2.3 实时操作系统

  • 特点：快速响应外部事件，可靠性高。
  • 应用：生产过程控制、实时信息处理。

1.2.4 网络操作系统

  • 功能：支持网络资源共享和通信，提供高效、可靠的网络服务。
  • 特点：硬件独立性、多用户支持、网络安全管理。

1.2.5 分布式操作系统

  • 特点：由多个计算机组成，无主次之分，支持分布处理和资源共享。
  • 优势：透明性、高性能、可靠性。

1.2.6 微型计算机操作系统

  • 常用系统：Windows、Mac OS、Linux。
  • 特点：图形用户界面、多任务、多线程。

1.2.7 嵌入式操作系统

  • 特点：微型化、可定制、实时性、可靠性、易移植性。
  • 应用：过程控制、数据采集、多媒体信息处理。

1.3 操作系统的发展

  • 驱动力：硬件升级、新服务需求、系统错误修补。
  • 目标：提高性能、资源利用率，解决现有问题。

2 进程管理

2.1 基本概念

2.1.1 程序与进程

1) 程序顺序执行的特征
  • 前趋图：有向无循环图，结点表示操作，有向边表示前趋关系。
  • 程序顺序执行特征：顺序性、封闭性、可再现性。
2) 程序并发执行的特征
  • 失去了程序的封闭性。
  • 程序和机器执行活动不再一一对应。
  • 并发程序相互制约。

为了解决这一问题，需要研究进程间的同步与互斥问题。

2.1.2 进程的组成

  • 定义：进程是程序的一次动态执行过程，是系统进行资源分配和调度的基本单位。
  • 特点
    • 动态性：进程具有生命周期，有创建、运行和消亡的过程。
    • 并发性：多个进程可以在同一时间段内并发执行。
    • 独立性：进程是独立运行的单位，具有独立的资源和状态。
    • 异步性：进程的执行速度不可预知，按随机速度向前推进。
  • 组成
    • PCB（进程控制块，Process Control Block）：进程存在的唯一标志，包含进程标识符、状态、位置信息、控制信息、队列指针、优先级、现场保护区等。
    • 程序：描述进程功能的部分，应为可再入代码，它是程序执行时不可修改的部分。
    • 数据：进程专用的可修改部分。

2.1.3 进程的状态及其状态间的转换

1) 三态模型
  • 就绪态：进程已获得除处理机外的所需资源，等待调度。
  • 运行态：进程在处理机上运行。
  • 阻塞态：进程因等待某种事件（如I/O操作完成）而暂停运行。

状态转换：

  • 运行态 → 就绪态：时间片到。
  • 运行态 → 阻塞态：等待某事件。
  • 就绪态 → 运行态：被调度。
  • 阻塞态 → 就绪态：等待事件发生。
2) 五态模型

在三态模型基础上增加了“新建态”和“终止态”。

  • 新建态：进程刚被创建，等待系统完成创建信息。
  • 就绪态。
  • 运行态。
  • 阻塞态。
  • 终止态：进程运行结束或因异常被终止，等待操作系统善后处理和释放内存。
3) 具有挂起状态的进程状态及其转换
  • 活跃就绪：进程在主存且可被调度。
  • 静止就绪：就绪进程被换到辅存，不能被直接调度。
  • 活跃阻塞：进程在主存，等待事件产生后进入活跃就绪。
  • 静止阻塞：阻塞进程被换到辅存，等待事件产生后进入静止就绪。

2.2 进程的控制

进程控制是对系统中的所有进程从创建到消亡的全过程实施有效的控制。操作系统设置了一套控制机构，其主要功能包括：

  • 创建新进程：启动一个新进程。
  • 撤销已运行完的进程：结束一个已完成的进程。
  • 改变进程状态：根据系统调度，更改进程的状态，如从就绪态转为运行态等。
  • 实现进程间通信：支持进程间的信息交换和同步。

进程控制的实现：由操作系统内核中的原语实现。

2.3 进程间的通信

2.3.1 同步与互斥

1）进程间的同步

进程合作的直接制约问题。需要在确定点协调合作进程的工作。

2）进程间的互斥

进程因争用临界资源而产生的间接制约问题。

3）临界区管理原则

  1. 有空即进：无进程在临界区时，允许进程进入。
  2. 无空则等：有进程在临界区时，其他进程等待。
  3. 有限等待：保证进程在有限时间内进入临界区。
  4. 让权等待：无法进入临界区时，等待时释放 CPU。

2.3.2 信号量机制

1）整型信号量与 PV 操作

信号量（Semaphore）：一种用于同步和互斥访问共享资源的机制，是一个计数器，可以被多个进程共享。通过信号量可以控制进程的同步和互斥。

  • P 操作：申请资源，信号量减 1。若信号量 <0<0 则进程将被阻塞，直到资源可用。
  • V 操作：释放资源，信号量加 1。若信号量 ≤0\leq 0，唤醒其中一个被阻塞的进程。

2）PV 操作实现互斥

使用信号量 mutex（初值为 1）实现进程间互斥，控制临界区访问。
互斥信号量 S 的定义：S的初值设为1，表示当前没有进程在临界区，可以进入临界区。

  • S = 1：表示没有进程在进入临界区，即可以有一个进程进入。
  • S = 0：表示已有一个进程进入临界区，其他进程必须等待。
  • S < 0：表示已有一个进程进入临界区，且有 |S| 个进程在等待进入临界区。

PV 操作表示进程对临界区的申请和释放：

  • 进入临界区之前：进程要进入临界区时，首先执行P(S)操作，即“申请”信号量S。
  • 退出临界区之后：当进程完成临界区操作后，执行V(S)操作，即“释放”信号量S。

3）PV 操作实现同步

同步机制：用于确保多个并发进程能够正确、有序地协作，避免数据冲突和确保数据一致性。

通过信号量协调进程间合作，如生产者-消费者问题。

PV操作实现进程的同步：

  • P 操作：测试消息是否到达。如果信号量S的值大于0，进程继续执行并进入临界区；如果信号量 S的 值小于等于0，进程进入等待状态，直到信号量 S 的值大于0。
  • V 操作：发送消息。增加信号量 S 的值，唤醒因等待信号量而阻塞的进程。

2.3.3 高级通信原语

为了提高信号通信的效率，传递大量数据，降低程序编制的复杂度，系统引入了高级通信
方式。

  • 共享存储模式：进程共享数据结构实现通信。
  • 消息传递模式：以消息为单位交换数据，使用系统通信命令。
  • 管道通信：通过管道（共享文件）连接读写进程，以字节流形式传输数据。

2.4 管程

2.4.1 管程的引入

  • 为解决信号量和 P、V 操作带来的死锁问题，1974 和 1975 年汉森和霍尔提出管程。
  • 管程通过集中管理共享资源的代码段，借助数据结构和操作过程管理资源申请和释放。
  • 提供安全共享抽象数据类型的机制，条件变量支持同步互斥。

2.4.2 管程的结构

管程由共享数据、一组进程可执行的共享数据操作集合、初始代码和存取权组成。

2.4.3 利用管程解决生产者—消费者问题

  • 管程描述：包含 put(item) 和 get(item) 操作，管理缓冲池消息存取。
  • 条件变量：notfull 和 notempty 控制缓冲区状态。
  • 操作逻辑：
    • put(item)：缓冲区满时等待，放入消息后唤醒等待的消费者。
    • get(item)：缓冲区空时等待，取出消息后唤醒等待的生产者。

管程提供了一种结构化的方法来管理共享资源，确保进程间的同步和互斥，有效解决了生产者-消费者等经典同步问题。

2.5 进程调度

调度方式

进程调度方式分为两种：

  • 可剥夺式：高优先级进程到来时，立即分配 CPU。
  • 不可剥夺式：需等待运行进程释放 CPU 后再分配。

2.5.1 三级调度

  1. 高级调度：决定输入池中的后备作业调入主系统成为就绪进程。
  2. 中级调度：决定交换区中的就绪进程调入内存参与 CPU 竞争。
  3. 低级调度：决定内存中的就绪进程占用 CPU。

2.5.2 调度算法

  1. 先来先服务 (FCFS)：

    • 按作业提交或进程就绪的先后顺序分配 CPU。
    • 优点：简单，利于长作业和 CPU 繁忙作业。
    • 缺点：不利于短作业和 I/O 繁忙作业。

  2. 时间片轮转：

    • 为每个进程分配相等时间片，提高资源利用率。
    • 时间片长度可固定或可变。

  3. 优先级调度：

    • 根据进程优先级分配 CPU，优先级分为静态和动态两种。
    • 静态优先级：创建时确定，不改变。
    • 动态优先级：运行过程中可调整。

  4. 多级反馈队列调度：

    • 结合时间片轮转和优先级算法。
    • 优点：照顾短进程、提高 I/O 设备利用率、无需估计执行时间。

2.5.3 进程优先级确定

  1. I/O 型进程：高优先级，快速响应 I/O 请求。
  2. 计算型进程：每次执行完时间片后降低优先级。
  3. 混合型进程：I/O 完成后，返回适当优先级队列。
  4. 动态调整：I/O 完成时提高优先级，时间片用完时降低优先级。

通过三级调度和多种调度算法，操作系统能够高效管理进程的 CPU 使用，提高系统整体性能。

2.6 死锁

  • 定义：多个进程因互相等待资源而无法继续运行的状态。
  • 产生原因 资源分配不当，进程推进顺序不合理。

-产生条件**
互斥条件：资源不能同时共享。
请求保持条件：进程已占用资源，又请求新资源。
不可剥夺条件：已分配的资源不能被强制剥夺。
环路条件：存在资源分配环路。

-处理方法**
预防：破坏死锁产生的条件之一。
避免：银行家算法，动态检测死锁。
检测：定期检测系统是否死锁。
解除：剥夺资源或撤销进程。

2.6.1 死锁举例

  • 资源竞争导致死锁：多个进程请求对方已占用资源，导致互相等待。
  • 资源分配不当导致死锁：资源不足且分配策略不当。
  • PV 操作不当导致死锁：信号量使用不当导致进程无法继续。

2.6.2 死锁产生的原因及 4 个必要条件

  • 原因：竞争资源及进程推进顺序非法。
  • 4 个必要条件：
    1. 互斥条件：资源只能被一个进程使用。
    2. 请求保持条件：进程已占有资源，再请求新资源。
    3. 不可剥夺条件：资源只能由占用进程释放。
    4. 环路条件：进程资源请求形成环路。

2.6.3 死锁的处理

2.6.3.1 死锁预防
  • 预先静态分配法：破坏了不可剥夺条件，预先分配所有资源。
  • 资源有序分配法：破坏了环路条件，资源有序分配，避免环路。
2.6.3.2 死锁避免
  • 银行家算法：分配资源前检查系统是否处于安全状态。
  • 安全状态：存在资源分配顺序，使所有进程都能完成。
  • 示例分析：通过资源分配和需求矩阵判断系统安全性。

银行家分配思路：可以分别列出“进程”、列表，可用、需求、已分、可用+已分、“能否完成标志”列。

2.6.3.3 死锁检测

定期运行检测算法判断是否存在死锁。

2.6.3.4 死锁解除
  1. 资源剥夺法：从其他进程剥夺资源分配给死锁进程。
  2. 撤销进程法：撤销死锁进程直到解除死锁。

死锁处理策略选择需权衡资源利用率和系统开销，预防和避免策略能有效减少死锁发生，检测与解除则用于处理已发生的死锁。

2.7 线程

线程的引入

  • 传统的进程有两个基本属性：资源分配的独立单位和调度分配的基本单位。
  • 引入线程的原因：进程在创建、撤销和切换中开销较大，限制了并发程度。线程将传统进程的两个属性分开，作为调度和分配的基本单位，而进程作为资源分配的单位。

线程的特点

  • 线程是进程中的一个实体，是系统独立分配和调度的基本单位。
  • 线程基本上不拥有资源，只拥有运行中必不可少的资源（如程序计数器、一组寄存器和栈），可与同属一个进程的其他线程共享进程资源。
  • 线程具有就绪、运行和阻塞三种基本状态。
  • 线程也称为轻型进程（Light-Weight Process），与传统的重型进程（Heavy-Weight Process）相比，具有较小的时空开销。

线程的分类

  • 用户级线程（User-Level Threads）：不依赖于内核，创建、撤销和切换不利用系统调用。
  • 内核支持线程（Kernel-Supported Threads）：依赖于内核，创建、撤销和切换都利用系统调用。

线程与进程的关系

  • 线程和进程在本质上不同，但表面上相似。
  • 进程切换依赖于内核中的进程调度，而线程切换不一定依赖内核。

3 存储管理

3.1 基本概念

存储管理主要涉及主存的分配和回收、提高主存利用率、扩充主存、保护对主存信息的有效保护。

3.1.1 存储器的结构

存储器的结构包括：

  • 寄存器 - 告诉缓存 - 主存 - 外存结构：存储组织的功能是在存储技术和 CPU 寻址技术许可的范围内组织合理的存储结构，使得各层次的存储器都处于均衡的繁忙状态。
  • 虚拟地址：对于程序员来说，数据的存放地址是由符号名决定的，称为符号名地址，它不是主存中的真实地址。
  • 地址空间：源程序经过编译或汇编再经过链接编辑形成程序的装入模块，转换为相对地址编址的模块，称为相对地址空间。
  • 存储空间：逻辑地址空间是逻辑地址的集合，物理地址空间是物理地址的集合。

3.1.2 地址重定位

地址重定位是将逻辑地址转换成主存物理地址的过程：

  • 静态重定位：在程序装入主存时完成逻辑地址到物理地址的变换，执行期间不再变化。优点是无需硬件地址变换机构支持，缺点是作业运行期间不能扩充存储空间。
  • 动态重定位：在程序运行期间完成逻辑地址到物理地址的变换，依赖硬件地址变换机构。优点是程序执行期间可以换入换出主存，可以在主存中移动，充分利用空间，实现共享。

3.2 存储管理方案

3.2 1 分区存储管理

分区存储管理概述

分区存储管理是早期的存储管理方案，将主存的用户区划分为若干区域，每个区域分配给一个用户作业使用，并限定作业只能在自己的区域内运行。分区存储管理方式可分为固定分区、可变分区和可重定位分区。

固定分区

  • 特点：在系统生成时已将主存划分为若干个分区，每个分区大小可不等。
  • 管理方式：通过主存分配情况表管理主存。
  • 问题：已分配区内存在未用空间（零头/内碎片）。

可变分区

  • 特点：存储空间的划分在作业装入时进行，分区大小刚好等于作业的大小。
  • 优点：主存的分配更灵活，也提高了主存的利用率
  • 管理表格：需要已分配表和未分配表。
  • 分配算法：
    1. 最佳适应算法：找到最接近用户需求的分区，能保留较大的空白区，但可能产生外碎片。
    2. 最差适应算法：将用户作业装入最大的空白区，减少外碎片。
    3. 首次适应算法：从主存低地址开始选择能满足作业的空白区，便于相邻空白区合并。
    4. 循环首次适应算法：从刚分配的空白区开始寻找。

问题：系统在不断地分配和回收中，必定会出现一些不连续的小的空闲区，产生外碎片，解决方法是拼接（紧凑）。

可重定位分区

  • 特点：解决碎片问题，移动已分配的分区形成连续区域。
  • 时机：用户请求空间得不到满足或作业执行完毕时进行。
  • 问题：导致地址发生变化，需进行地址重定位。

分区保护

  • 目的：防止未经授权的用户访问分区。
  • 方式：
    1. 上界/下界寄存器保护：物理地址必须满足上界寄存器 ≤ 物理地址 ≤ 下界寄存器。
    2. 基址/限长寄存器保护：物理地址必须满足基址寄存器 ≤ 物理地址 < 基址寄存器 + 限长寄存器。

3.3 分页存储管理

3.3.1 纯分页存储管理

3.3.1.1 分页原理
  • 将进程的地址空间划分为若干大小相等的区域，称为页。
  • 将主存空间划分为与页相同大小的若干物理块，称为物理块或页框。
  • 进程的各页可离散地分配到多个不相邻的物理块中。
3.3.1.2 地址结构
  • 逻辑地址分为页号和页内地址（偏移量）。
  • 例如，32 位地址中，0~11 位为页内地址（每页大小为4kb，即 4kb/页），12~31位为页号，允许地址空间最多为 1Mb 页。

1.3 页表

  • 系统为每个进程建立一张页面映射表，简称页表，记录每页对应的物理块号。
  • 地址变换机构利用页表将逻辑地址转换为物理地址。
  • 页表始址和长度存放在进程的PCB中，执行时加载到页表寄存器。

3.3.2 快表

  • 为提高访问速度，引入快表（联想存储器）保存当前访问频率高的页号及物理块号。
  • 访问数据时，先查快表；若未命中，再查主存页表。
  • 快表命中率高时，可显著减少主存访问次数。

3.3.3 两级页表机制

为减少页表占用的连续主存空间，引入两级页表：

  • 外层页表（页目录表）：记录各页表的物理地址。

  • 内层页表（页表）：记录各页的物理块号。

  • 逻辑地址分为外层页号、内层页号和页内地址。

  • 地址变换时，先通过外层页号查页目录，再通过内层页号查页表，最后得到物理地址。

总结：分页存储管理通过将进程地址空间和主存空间划分为固定大小的页和块，实现了离散分配，解决了分区存储管理中连续空间分配的问题。快表和两级页表机制进一步提高了地址变换的速度和效率。

3.4 分段存储管理

在分段存储管理中，作业的地址空间被划分为若干个段，每个段是一组完整的逻辑地址空间，如主程序段、子程序段、数据段和堆栈段等。各段有自己的名字，从 0 开始编号，但长度不等。

逻辑地址由段号和段内地址（段内偏移量）组成。例如，允许一个作业最多有 64 kb 个段，每个段的最大长度为 64 kb。

系统为每个进程建立一张段映射表（段表），每个段在表中占一项，记录该段在主存中的起始地址（基址）和段的长度。进程执行时通过查段表找到每个段对应的主存区。

系统设置段表寄存器存放段表地址和段表长度。地址变换时，系统将逻辑地址中的段号与段表长度比较，若越界则中断；否则计算段表项位置，读取基址并检查段内地址是否越界，若未越界则将基址与段内地址相加得到物理地址。

假设某作业的段表如下：

段号 基址 段长
0 219 600
1 2300 200
2 90 100
3 1327 580
4 1952 96

（1）逻辑地址（0，168）、（1，58）、（2，98）、（3，300）和（4，100）能否转换为物理地址？

  • （0，168）、（1，58）、（2，98）和（3，300）可以转换。
  • （4，100）不能转换，因段长为 96，地址越界。

（2）转换后的物理地址：

  • （0，168）→ 219 + 168 = 387。
  • （1，58）→ 2300 + 58 = 2358。
  • （2，98）→ 90 + 98 = 188。
  • （3，300）→ 1327 + 300 = 1627。

4.3.5 段页式存储管理

段页式系统结合了分页和分段的优点：

  • 分页提高主存利用率。

  • 分段满足用户逻辑需求，便于共享和保护。

  • 定义：段页式存储管理是将段式存储和页式存储相结合的一种内存管理方式。先将程序按逻辑结构划分为多个段，再将每个段细分为固定大小的页面。

  • 逻辑地址结构：逻辑地址由段号、段内页号和页内地址三部分组成。

  • 段表和页表：系统为每个进程建立一张段表，用于管理段的分配和访问。每个段再建立一张页表，用于管理段内页面的分配和访问。

  • 地址转换：逻辑地址由段号、段内页号和页内地址三部分组成。首先通过段表找到对应的段，再通过页表找到对应的物理页面，最后将物理页面号与页内地址组合成物理地址。

段页式存储管理的地址由段号、段内页号和页内地址组成。系统需配置段表和页表，段表内容为页表起始地址和页表长度。

地址变换过程

  1. 根据段号查段表，得页表起始地址。
  2. 根据页号查页表，得物理块号。
  3. 将物理块号与页内地址拼接成物理地址。

段页式存储管理通过段表和页表的配合，实现了从逻辑地址到物理地址的高效转换，既提高了主存利用率，又方便了用户对信息的逻辑访问。

3.6 虚拟存储管理

通过虚拟存储技术有效扩展主存容量并提高系统性能。虚拟存储器通过将作业的一部分装入主存即可启动运行，其余部分暂时留在磁盘上，需要时再调入主存。这样可以有效利用主存空间，从用户角度看，系统容量比实际主存大得多。

程序局部性原理

程序在执行时呈现局部性规律：

  • 时间局部性：近期访问的指令和数据可能再次被访问。
  • 空间局部性：访问了某个存储单元后，其附近单元也可能被访问。

虚拟存储器的实现

虚拟存储器的实现主要有三种方式：

  1. 请求分页系统：基于分页系统，增加了请求调页和页面置换功能。
  2. 请求分段系统：基于分段系统，增加了请求调段和段置换功能。
  3. 请求段页式系统：结合分段和分页，增加了请求调页和页面置换功能。

请求分页管理的实现：请求分页系统是在纯分页系统的基础上增加了请求调页和页面置换功能。其核心是通过页表管理实现虚拟存储。

缺页中断

当访问的页面不在主存时产生缺页中断，操作系统将所需页面调入主存。缺页中断与普通中断的区别：

  1. 缺页中断在指令执行期间产生，而普通中断在指令执行完后产生。
  2. 缺页中断返回到被中断指令重新执行，普通中断返回到下一条指令。
  3. 一条指令可能引起多次缺页中断。

页面置换算法

页面置换算法用于确定哪个页面应被换出主存，常用的算法有：

  1. 最佳置换算法（Optimal）：
    • 理想化的算法，淘汰未来最长时间不再访问的页面。
    • 性能最优，但难以实现。
  2. 先进先出置换算法（FIFO）：
    • 淘汰最早进入主存的页面。
    • 实现简单，但可能存在 Belady 异常。
  3. 最近最少使用置换算法（LRU）：
    • 淘汰最近最久未使用的页面。
    • 需要记录页面的使用情况。
  4. 最近未用置换算法 （NUR，Not Used Recently）

工作集

工作集理论由 Denning 于 1968 年提出。工作集是指在某段时间间隔（Δ）内进程实际要访问的页面的集合。工作集的大小对缺页率有重要影响，合理的分配物理块可以将缺页率控制在合理水平，避免“颠簸”现象。

工作集的定义

  • 工作集窗口：Δ，表示时间间隔。
  • 工作集记号：w(t, Δ)，表示进程在时间 t 的工作集。

工作集的应用

  • 降低缺页率：预知程序在某段时间内要访问的页面，并提前调入主存，可降低缺页率，提高 CPU 利用率。
  • 动态调整工作集大小：当工作集达到最小值时，虚存管理程序根据缺页数量和主存中空闲页面数量，动态调整工作集大小。

4 设备管理

4.1 设备管理概述

设备管理是操作系统中与硬件紧密相关的复杂部分，负责管理实际 I/O 操作的设备及支持设备。其目标是提高设备利用率，为用户提供更方便的接口。

4.1.1 设备的分类

  1. 按数据组织分类
    • 块设备（Block Device）：如磁盘。
    • 字符设备（Character Device）：如键盘、打印机。
  2. 按功能分类
    • 输入设备：键盘、鼠标。
    • 输出设备：显示器、打印机。
    • 存储设备：磁盘、光盘。
    • 网络设备：网卡。
    • 供电设备：电源、UPS。
  3. 从资源分配角度分类
    • 独占设备：如打印机。
    • 共享设备：如磁盘。
    • 虚拟设备：通过虚拟技术实现共享。
  4. 按数据传输率分类
    • 低速设备：键盘、鼠标。
    • 中速设备：行式打印机。
    • 高速设备：磁盘、光盘。

4.1.2 设备管理的目标与任务

  • 提高设备利用率。
  • 提供方便统一的用户界面。
  • 主要功能：
    • 掌握设备状态。
    • 设备分配与释放。
    • 缓冲区管理。
    • 实现物理 I/O 操作。
    • 提供用户接口和设备控制。

4.2 I/O 软件

I/O 软件采用分层设计，分为四层：

  1. 中断处理程序：处理硬件中断。
  2. 设备驱动程序：控制设备操作。
  3. 设备无关系统软件：提供通用功能。
  4. 用户级软件：提供用户接口。

I/O 软件的主要目标是设备独立性和统一命名，便于设备管理软件的设计和设备更新。

4.3 设备管理采用的相关技术

4.3.1 通道技术

  • 目的：使数据传输独立于 CPU，减轻 CPU 的 I/O 负担。
  • 工作方式：CPU向通道发送 I/O 命令，通道自主执行I/O任务，完成后向CPU发送中断信号。
  • 分类：字节多路通道、数组选择通道、数组多路通道。
  • 瓶颈问题：通道数量有限，可能成为 I/O 的瓶颈。解决方法是增加设备到主机之间的通路。

4.3.2 DMA技术（直接内存访问）

  • 原理：数据在主存与I/O设备间直接成块传送，无需CPU干预。
  • 优点：减少 CPU 中断频率，提高数据传输效率。
  • 示例：非 DMA 打印 2048 字节需 2048 次输出指令，DMA方式只需一次输出指令。

4.3.3 缓冲技术

  • 目的：缓和 CPU 与 I/O 设备间速度不匹配的矛盾，减少 CPU 中断频率，提高并行性。
  • 类型：单缓冲、双缓冲、多缓冲、环形缓冲。
  • 应用场景：所有 I/O 设备与处理机之间都使用缓冲区交换数据，操作系统需组织和管理缓冲区。

4.3.4 Spooling 技术

  • 原理：用一类物理设备模拟另一类物理设备，使独占设备变成多台虚拟设备共享。
  • 组成：预输入程序、缓输出程序、井管理程序、输入井、输出井。
  • 工作过程：操作系统激活预输入程序，捕获输入请求，存入输入井；作业调度程序调度作业执行；缓输出程序处理输出结果，存入输出井；井管理程序管理输入井和输出井。

4.4 磁盘调度

磁盘的结构：一个磁盘有多个磁盘，每个磁盘可能是单个或正反两个盘面，每个盘面有多个同心圆（磁道），每个磁道又被划分为多个扇区。数据存放在扇区中。读取数据时，会产生寻道时间和等待时间。

磁盘调度应优先进行移臂调度，再进行旋转调度。

4.4.1 磁盘驱动调度

磁盘调度的目标是通过优化磁盘访问顺序，使磁盘的平均寻道时间最少。常见的调度算法如下：

  1. 先来先服务（FCFS）
  • 原理：根据进程请求访问磁盘的先后顺序进行调度。
  • 优点：公平、简单，每个请求依次处理。
  • 缺点：未对寻道进行优化，平均寻道时间可能较长。
  1. 最短寻道时间优先（SSTF）
  • 原理：选择与当前磁头距离最近的请求进行调度。
  • 优点：减少每次的寻道时间。
  • 缺点：不能保证平均寻道时间最短，可能出现饥饿现象。
  1. 扫描算法（SCAN）又称“电梯算法”
  • 原理：磁头单方向移动，依次处理沿途请求，到端点后反向扫描。
  • 优点：避免饥饿现象，适合多个请求分散在磁盘的情况。
  • 缺点：可能存在较长的等待时间。
  1. 单向扫描调度算法（CSCAN）
  • 原理：磁头只进行单向移动，类似于 SCAN 算法但不反向。
  • 优点：减少因反向造成的延迟。

4.4.2 旋转调度算法

当磁头到达指定柱面后，决定多个进程访问该柱面的顺序。旋转调度的目标是最小化旋转延迟时间。

2.1 调度原则

  1. 同一磁道不同扇区：按到达顺序依次访问。
  2. 不同磁道不同扇区：按到达顺序依次访问。
  3. 不同磁道相同扇区：任选一个读/写磁头位置下的扇区进行访问。

磁盘访问时间主要由三部分组成：寻道时间、旋转延迟时间和数据传输时间

寻道时间是指磁头从当前位置移动到目标磁道所需的时间。它取决于磁头的移动速度和目标磁道与当前磁道的距离。寻道时间的计算公式为：寻道时间=(目标磁道号−当前磁道号)×寻道速度。其中，寻道速度是磁头每跨越一个磁道所需的时间。

旋转延迟时间是指等待所需数据扇区旋转到磁头下方的时间

数据传输时间是指数据从磁盘传输到内存的时间，它取决于数据量和传输速率。数据传输时间的计算公式为：数据传输时间= 传输速率 /数据量

5 文件管理

5.1 文件与文件系统

5.1.1 文件

  • 定义：文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。例如，源程序、目标程序、文档等。
  • 组成：文件包括文件体（真实内容）和文件说明（管理信息，如文件名、类型、存储地址等）。
  • 命名：文件名在创建时确定，操作系统通过文件名进行控制和管理。不同系统对文件名的格式和长度有不同规定。

5.1.2 文件系统

  • 定义：文件系统是操作系统中负责文件统一管理的软件和相关数据的集合。
  • 功能：
    • 按名存取：用户通过文件名访问文件，无需关心存储位置。
    • 统一用户接口：在不同设备上提供一致的访问接口。
    • 并发访问控制：支持多用户系统中的文件并发访问。
    • 安全控制：限制不同用户对文件的访问权限。
    • 性能优化：提高存储、检索和读写效率。
    • 差错恢复：验证文件正确性并恢复错误。

5.1.3 文件的类型

  • 按性质和用途：系统文件、库文件、用户文件。
  • 按信息保存期限：临时文件、档案文件、永久文件。
  • 按保护方式：只读文件、读/写文件、可执行文件、不保护文件。
  • UNIX 系统分类：普通文件、目录文件、设备文件（特殊文件）。

常用文件系统类型**：FAT、VFat、NTFS、Ext、HPFS 等。

5.2 件的结构和组织

5.2.1 文件的逻辑结构

文件的逻辑结构是用户看到的文件组织形式，分为两大类：

  1. 记录式文件
  • 定长记录：所有记录长度相同，处理方便，开销小，适用于数据处理。
  • 变长记录：记录长度不同，根据数据项数目和长度变化。
  1. 流式文件
  • 无结构的字节流，不划分记录，通常采用顺序访问方式，长度以字节为单位。在 UNIX 系统中，所有文件都被视为流式文件。

5.2.2 文件的物理结构

文件的物理结构是文件在存储设备上的存放方法，影响文件的存取效率。

  1. 连续结构
  • 文件信息存放在连续编号的物理块上。
  • 优点：批量存取效率高。
  • 缺点：不便于记录的增删，随机访问性能差。
  1. 链接结构
  • 文件信息存放在不连续的物理块上，每个物理块有指针指向下一个块。
  • 优点：便于增删记录。
  • 缺点：访问速度较慢。
  1. 索引结构
  • 系统为文件建立索引表，记录逻辑块号与物理块号的对应关系。
  • 优点：访问速度快。
  • 缺点：增加了存储开销。
  1. 多级索引结构（UNIX系统）
  • 包括直接寻址、一级、二级和三级间接寻址。
  • 平衡了访问速度和存储开销。

在 UNIX 文件系统中采用的是三级索引结构。
UNIX 文件索引表项分 4 种寻址方式：直接寻址、一级间接寻址、二级间接寻址和三级间接寻址。

5.3 文件目录

5.3.1 文件控制块（FCB）

文件控制块是用于描述和控制文件的数据结构，包含以下三类信息：

  • 基本信息类：文件名、物理地址、文件长度、文件块数。
  • 存取控制信息类：文件的存取权限，如UNIX系统的RWX权限。
  • 使用信息类：文件建立日期、修改日期、访问日期、使用信息。

5.3.2 目录结构

目录结构的组织方式影响文件存取速度、共享性和安全性。常见目录结构有：

一级目录结构

  • 特点：单张目录表，所有文件目录项集中。
  • 优点：简单。
  • 缺点：查找慢、不允许重名、不利于共享。

二级目录结构

  • 组成：主文件目录（MFD）和用户文件目录（UFD）。
  • 优点：提高检索速度，解决重名问题。
  • 缺点：用户间隔离不利于共享。

多级目录结构（树型目录结构）

  • 特点：目录结构类似倒置树，根目录下有多个子目录。

  • 优点：便于共享和组织文件，支持相对路径和绝对路径。

  • 应用：MS-DOS 和 UNIX 等操作系统均采用。

  • 绝对路径：采用全文件名，例如 D:\Program\Java-prog\fl.java，包含盘符及从根目录开始的完整路径。

  • 相对路径：从当前目录到目标文件的路径。

5.4 文件存取方法和存储空间的管理

5.4.1 文件的存取方法

文件的存取方法主要有两种：

  1. 顺序存取：按文件中信息的顺序依次读写。
  2. 随机存取：可按任意顺序读写文件中的信息。

5.4.2 文件存储空间的管理

文件存储空间管理需了解外存的使用情况，常用方法如下：

  • 空闲区表
    • 记录所有空闲区的信息，包括起始块号和块数。
    • 适用于连续文件结构。
  • 位示图
    • 用位图记录每个物理块的使用情况（0 表空闲，1 表占用）。
    • 每位对应一个物理块，适合各种物理结构。
  • 空闲块链
    • 空闲块通过指针链成链表，申请时依次获取。
  • 组链接法
    • 将空闲块分组，每组的第一个块记录下一组的起始号和块数。

5.5 文件的使用

文件系统负责将逻辑文件转换为物理文件存储，并提供文件操作服务。操作系统提供目录管理和文件操作命令，支持文件的安全访问和权限控制。

5.6 文件的共享和保护

5.6.1 文件的共享

文件共享允许多个用户进程访问同一文件，节省存储空间并减少访问次数。常见的文件链接方式有：

  1. 硬链接：多个文件名指向同一文件实体。在 UNIX 系统中，ln 命令用于创建硬链接。硬链接不能跨文件系统。
  2. 符号链接：创建新文件或目录，指向原文件路径。在 UNIX 系统中，ln -s 命令用于创建符号链接。符号链接可以跨文件系统，甚至通过网络访问。

5.6.2 文件的保护

文件保护通过存取控制实现，防止未授权访问。常见的存取控制方法有：

  1. 存取控制矩阵：理论上，存取控制可用二维矩阵表示，行代表用户，列代表文件，元素表示权限（如 R、W、X）。但实现困难，存储和验证成本高。
  2. 存取控制表：按用户类别简化权限管理。UNIX 系统将用户分为文件主、同组用户和其他用户，每类有独立权限。权限用 R、W、X 表示，无权限用 -。
  3. 用户权限表：以用户或用户组为单位，列出可访问文件及其权限，相当于存取控制矩阵的行简化。
  4. 密码保护：文件创建时设置密码，读取时需解密，仅授权用户可访问。

5.7 系统的安全与可靠性

5.7.1 系统的安全

系统的安全管理分为四个级别：系统级、用户级、目录级和文件级。

  1. 系统级安全管理
  • 任务：阻止未经授权的用户进入系统。
  • 措施：注册与登录。
  1. 用户级安全管理
  • 任务：对用户分类并分配访问权限。
  • 实现：UNIX 系统中的用户分类（文件主、同组用户、其他用户），设置不同权限。
  1. 目录级安全管理
  • 任务：保护系统目录。
  • 措施：仅系统核心有写目录权限。
  1. 文件级安全管理
  • 任务：通过文件属性控制访问。
  • 实现：设置文件属性（只执行、隐含、只读、读/写、共享、系统），用户访问权限由用户权限、目录权限和文件属性共同决定。

5.7.2 文件系统的可靠性

文件系统的可靠性是指系统抵抗和预防物理及人为破坏的能力。

  1. 转储与恢复
  • 目的：通过转储形成文件或文件系统的多个副本，以便故障恢复。
  • 方法：静态转储、动态转储、海量转储、增量转储。
  1. 日志文件
  • 功能：记录用户对文件的操作，用于故障恢复。
  1. 文件系统的一致性
  • 问题：系统崩溃可能导致文件系统不一致。
  • 解决方案：一致性检查，包括块的一致性检查和文件的一致性检查。

6. 作业管理

6.1 作业与作业控制

6.1.1 作业控制

作业控制分为脱机控制和联机控制：

  • 脱机控制：用户通过作业控制语言（JCL）编写作业说明书，连同作业一起提交给计算机系统。
  • 联机控制：用户通过终端输入命令控制作业的运行过程。

作业由程序、数据和作业说明书三部分组成：

  • 作业基本情况：用户名、作业名、编程语言、处理时间等。
  • 作业控制描述：控制方式、作业步顺序、错误处理等。
  • 作业资源要求：处理时间、优先级、内存空间、外设要求等。

6.1.2 作业状态及转换

作业状态分为四种：

  1. 提交：作业提交给计算机系统。
  2. 后备：作业通过 Spooling 系统存入后备存储器。
  3. 执行：作业被调度程序选中并执行。
  4. 完成：作业正常结束或异常终止。

6.1.3 作业控制块和作业后备队列

  • 作业控制块（JCB）：记录作业相关信息，是作业存在的唯一标志。
  • 作业后备队列：由多个 JCB 组成，用于作业调度程序调度。

6.2 作业调度

6.2.1 作业调度算法

选择调度算法需考虑系统设计目标、资源均衡使用和用户需求。常见的调度算法包括：

  1. 先来先服务：按作业到达顺序调度。
  2. 短作业优先：优先运行时间短的作业。
  3. 响应比高者优先：
    • 响应比公式：Rp=1+作业等待时间作业执行时间R_p = 1 + \frac{\text{作业等待时间}}{\text{作业执行时间}}，一般而言等待时间长、运行时间短的先执行
  4. 优先级调度：根据用户指定或系统设定的优先级调度。
  5. 均衡调度：根据系统运行情况和作业特性均衡使用资源。

6.2.2 作业调度算法性能的衡量指标

  • 平均周转时间：T=1n∑i=1nTiT = \frac{1}{n} \sum_{i=1}^n T_i
  • 平均带权周转时间：W=1n∑i=1nWiW = \frac{1}{n} \sum_{i=1}^n W_i，其中 Wi=TitnW_i = \frac{T_i}{t_n}

性能指标的目标是使系统的平均周转时间和平均带权周转时间最小。

6.3 用户界面

用户界面是计算机中实现用户与计算机通信的软硬件部分的总称，可分为多个发展阶段：

  1. 控制面板式用户界面
  • 特点：用户通过控制台开关、板键或穿孔纸带输入命令或数据，计算机通过指 示灯及打印机输出信息。
  • 评价：操作笨拙，用户需适应计算机的工作方式。
  1. 字符用户界面（CUI）
  • 特点：用户通过键盘输入字符命令，计算机以字符形式输出结果。
  • 优点：功能强大、灵活性好、屏幕开销少。
  • 缺点：操作步骤繁琐，学习成本高。
  1. 图形用户界面（GUI）
  • 特点：用户通过图形、图像、声音等多媒体元素与计算机交互。
  • 关键技术：超文本技术，支持文本、图像、音频、视频等多种媒体。
  • 优势：操作直观、方便，用户体验更好。
  1. 新一代用户界面
  • 特点：利用虚拟现实技术，用户以自然方式与虚拟环境交互。
  • 特征：以用户为中心、自然、高效、支持多媒体和多通道交互。
  • 技术支持：语音识别、自然语言处理、手势识别、视线追踪等。
  • 优势：提供沉浸式体验，支持多种感知通道的交互。

用户界面的发展从早期的控制面板，到字符界面，再到图形界面，直至新一代的虚拟现实界面，体现了计算机交互方式从以机器为中心到以用户为中心的转变。

7 加餐和总结

常见文件系统

  • FAT：文件分配表文件系统，适用于小型存储设备。
  • NTFS：Windows 操作系统中的高级文件系统，支持大容量存储设备和高级功能。
  • ext：Linux 操作系统中的文件系统，如ext2、ext3、ext4。
  • HFS+：Mac OS 操作系统中的文件系统。