简介

我们可以将计算机系统分为硬件和软件，软件又可以进一步分为系统软件和应用软件，而操作系统则属于系统软件。操作系统处于上层应用软件与底层硬件的中间层，为此它提供了三大抽象，进程是其对 CPU 的抽象，虚拟地址空间是其对内存的抽象，文件是其对 I/O 设备的抽象。

先修

本实验的先修课程如下所示：

  • 计算机组成原理
  • C 语言程序设计
  • 数据结构
  • 操作系统

除此之外，你还需要懂得基本的 Linux 命令行使用知识。

本节将对开发环境、C 语言、汇编和 80386 做简要介绍。

开发环境

本实验在 Ubuntu 18.04 上开发完成，关于 Ubuntu 的安装，这里不再赘述，值得注意的是，如果你使用的是 Windows 10， 其内置了 WSL（Windows Subsystem for Linux）功能，可以更加方便的在 Windows 中使用 Linux 子系统。

安装完 Ubuntu 之后，你需要安装如下必备的开发工具：

  • GCC：编译器
  • GDB：调试器
  • QEMU：模拟器

使用如下命令即可一键安装上述工具：

sudo apt-get install build-essential gdb qemu -y

安装完成后，依次输入如下命令：

gcc -v

gdb -v

qemu-system-i386 –-version

若无明显报错，且正常显示相应的版本信息，即代表安装成功。

GCC

GCC 是由 GNU 开源组织开发的编译器套装，其中包含了 C 语言编译器 gcc、C++ 编译器 g++、链接器 ld、 汇编器 ns、构建器 make 等众多工具。在 Ubuntu 中，这些工具被集合进了一个软件包，即 build-essential， 所以只需要安装它即可。

GDB

GDB 同样是由 GNU 开源组织开发的命令行调试器，其可以和 GCC 完美配合。

QEMU

QEMU 是我们在此实验中所用到的模拟器（或称虚拟机），它会模拟出一个 32 位的 80386 硬件环境， 其用来运行编译生成的 OS 镜像文件。为什么不选择常用的 VMware 或者 VirtualBox，而使用不常见的 QEMU，其原因如下：

  • 我们所使用的 Linux 开发环境是在虚拟机中运行的，要在虚拟机中的 Linux 上再安装一个虚拟机， VMware 或者 VirtualBox 是不支持的，而 QEMU 则支持。
  • QEMU 有很方便的调试功能，配合 GDB 可以实现计算机加电后的逐步调试功能，而 VMware 或者 VirtualBox 则不尽完美。
  • QEMU 完全采用命令行操作，更符合 Linux 的设计哲学。

除了上述必备工具之外，以下辅助工具你可能也会用到：

编辑器

系统自带的编辑器可能不够强大，因此你可能需要一个第三方的编辑器，命令行界面的编辑器推荐使用 Vim， 图形化界面的编辑器推荐使用 Sublime Text 3 。

文本差异比较工具

在很多时候，我们需要比较多个文件或文件夹之间的差异，比如比较 Lab1 和 Lab2 之间的差异， 可以帮助我们更好的理解 Lab2 中新增的功能。命令行界面的比较工具可以使用系统自带的 diff 命令， 图形化界面的比较工具推荐使用 Meld 。

C 语言

本节不会讲述 C 语言的基本语法，只会就某些特性做简要说明。

编译过程

一个 C 语言源代码变成二进制可执行文件，大致要经过 4 个步骤，以 test.c 为例说明：

  1. 预处理：test.c 经过编译预处理程序（cpp）生成 test.i，主要处理源代码文件中的编译预处理指令。
  2. 编译：test.i 经过编译器（gcc）生成 test.s，test.s 为汇编语言。
  3. 汇编：test.s 经过汇编器（ns）生成 test.o，test.o 为二进制代码。
  4. 链接：test.o 经过链接器（ld）生成 test，test 为可执行文件。

头文件

头文件是存放声明的地方，声明（declare）和定义（define）是两个不同的概念， 声明是不产生代码的东西，而定义是产生代码的东西，声明可以包括函数原型和变量声明等等，以下举例说明：

// 变量定义
int a;

// 变量声明
extern int a;


// 函数定义
int
plus(int a, int b){
    return a+b;
}

// 函数原型，即函数声明
int plus(int a, int b);

在大型项目中，往往需要把一个源代码文件中对外公开的函数或变量的声明放到其对应的头文件中， 当其他源代码文件想要使用其提供的函数或变量时，需要先使用编译预处理指令 #include 引入其头文件。

对于不愿对外公开的函数或变量，可以在其前加上 static 修饰符，使其只能在其源代码文件中被使用。

为了防止头文件中结构体的重复声明，需要使用标准头文件结构，运用条件编译和宏， 可以保证这个头文件在一个编译单元中只会被 #include 一次。示例如下：

#ifndef __TEST_H__
#define __TEST_H__

extern int a;
int plus(int a, int b);

#endif

面向对象

利用结构体和函数指针，可以实现 C 语言的面向对象特性， 下面以一个计算器对象为例说明，假设计算器对象包含类型、价格等属性和加法、乘法等方法：

#include <stdio.h>

// 定义一个计算器结构体，其对外提供统一的接口
struct calc{
    char *type;
    int price;
    int (*plus)(int a, int b);
    int (*multiply)(int a, int b);
};

// 定义具体的加法方法
int
int_plus(int a, int b){
    return a+b;
}

// 定义具体的乘法方法
int
int_multiply(int a, int b){
    return a*b;
}

// 定义具体的计算器
struct calc int_calc = {
    .type = "Integer Calculator",
    .price = 10,
    .plus = int_plus,
    .multiply = int_multiply,
};

// 进行相关调用
int
main(void){
    struct calc *calc;
    calc = &int_calc;
    printf("%s\n", calc->type);
    printf("￥%d\n", calc->price);
    printf("3+5=%d\n", calc->plus(3, 5));
    printf("3*5=%d\n", calc->multiply(3, 5));
    return 0;
}

通过使用这种方法，我们可以方便的更改具体的计算器实现。

代码风格

关于代码风格的讨论，向来都没有一个绝对正确的答案，但是统一的代码风格有助于每个人更好的阅读理解代码， 在此实验中，我们采用如下规定的代码风格：

换行

函数返回值类型和函数名之间换一行，这样可以更方便的使用 grep 命令找到函数实现， GNU 和 BSD 等开源代码多采用这种风格，以下是示例：

void
trap(struct trapframe *tf) {
    trap_dispatch(tf);
}
// 可以使用grep ^trap命令找到函数实现

类似的，起始大括号不换行，同样可以参考上面的示例。

汇编

关于 80386

Lab 1：启动和 bootloader

操作系统通过中断与底层硬件进行交互，通过系统调用和异常与上层应用程序进行交互。中断、异常和系统调用又被统称为中断（广义上的中断），其中中断又被称为硬中断，异常和系统调用又被称为软中断。

计算机加电，启动 BIOS，BIOS 加载 bootloader，bootloader 加载 OS 内核。

bootloader 主要完成的工作为：

  • 从实模式切换到保护模式
  • 建立分段机制
  • 加载 OS 内核

具体而言，通过设置 A20 门和 CR0 寄存器以切换到保护模式，要建立段表（GDT）。

OS 内核主要完成的工作为：

  • 建立中断机制
  • 打印函数调用栈关系。

具体而言，要初始化中断向量表（IDT）。

数据块与扇区：

  • 数据块（block）：逻辑存储单元，可能由多个扇区组成
  • 扇区（sector）：磁盘的物理存储单元

实验目的

Exercise 2

Lab 2：物理内存管理

真实的物理内存通常是多种多样的，它们可能是互不连续且速度差异巨大的，操作系统需要为上层应用抽象出一个连续的 逻辑地址空间，逻辑地址空间到物理地址空间的映射则由 MMU（Memory Management Unit，内存管理单元）来负责。

逻辑地址空间与物理地址空间：

  • 逻辑地址空间（logical address space）：又称虚拟地址空间（virtual），在 CPU 运行的进程看到的地址，即可执行文件中的地址
  • 物理地址空间（physical）：由硬件直接支持的地址空间
  • 线性地址空间（linear）：

操作系统对内存的管理主要体现为 内存分配，内存分配又分为 连续内存分配 和 非连续内存分配，连续内存分配可以通过 重定位 实现，非连续内存分配可以通过 段机制 或 页机制 实现。

连续内存分配

连续内存分配是一种最简单的内存分配算法，指给进程分配一块不小于指定大小的连续的物理内存区域。值得注意的是，连续内存分配可能会产生空闲内存不能被利用的 碎片，碎片又分为外碎片和内碎片，外碎片 是指分配单元之间的未被使用内存，内碎片 是指分配单元内部的未被使用内存，内碎片的产生取决于分配单元大小是否要取整。

一个优秀的连续内存分配算法致力于减少这种碎片的产生，以下介绍一些常用的连续内存分配算法：

  • 最先匹配（First Fit Allocation）：空闲分区列表按地址顺序排序，分配过程时，搜索第一个合适的分区，释放分区时，检查是否可与临近的空闲分区合并。
    • 优点：简单；在高地址空间有大块的空闲分区。
    • 缺点：会产生外碎片；分配大块时较慢。
  • 最佳匹配（Best Fit Allocation）：空闲分区列表按由小到大排序，分配时，查找一个合适的分区，释放时，查找并且合并临近的空闲分区（如果找到）
    • 优点：大部分分配的尺寸较小时，效果很好
      • 可避免大的空闲分区被拆分
      • 可减小外碎片的大小
      • 相对简单
    • 缺点：会产生外碎片；释放分区较慢；容易产生很多无用的小碎片。
  • 最差匹配（Worst Fit Allocation）：空闲分区列表按由大到小排序，分配时，选最大的分区，释放时，检查是否可与临近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序。
    • 优点：中等大小的分配较多时，效果最好；避免出现太多的小碎片
    • 缺点：会产生外碎片；释放分区较慢；容易破坏大的空闲分区，因此后续难以分配大的分区

在连续内存分配中，当一个新进程需要内存空间，但却没有足够可使用的内存空间时，我们就需要碎片整理，碎片整理 是指通过调整进程占用的分区位置来减少或避免分区碎片。碎片整理进一步又分为：

  • 紧凑（compaction）：通过移动分配给进程的内存分区，以合并外部碎片。紧凑的条件是所有应用程序可动态重定位。通常来说会对等待态的进程进行移动。
  • 分区对换（swapping in/out）：通过抢占并回收处于等待态的进程的分区，以增大可用内存空间。

一个较好的连续内存分配的实现是 伙伴系统（buddy system）。

非连续内存分配

连续内存分配存在诸多缺点，因此我们需要非连续内存分配以提高内存利用效率和管理灵活性。具体而言，非连续内存分配 允许一个程序使用非连续的物理地址空间，允许共享代码与数据，支持动态加载和动态链接。根据非连续内存分配中的内存块的大小，我们可以将非连续内存分配分为 段式存储管理（segmentation）和 页式存储管理（paging），两者的区别是段式存储管理的内存块比较大，页式存储管理的内存块比较小。

段式存储管理

在段式存储管理中，段 表示访问方式和存储数据等属性相同的一段地址空间，其对应一个连续的内存“块”，若干个段组成进程逻辑地址空间。将逻辑地址空间映射为物理地址空间遵循如下步骤：

  1. 根据 段号 在 段表 中查找相应的 段基址 和 段长度
  2. 比较 段内偏移 是否小于等于段长度，若否，则抛出内存异常，若是，则进行下一步
  3. 根据段基址和段内偏移得到真实的物理地址

页式存储管理

在页式存储管理中，我们把物理地址空间划分为大小相同的基本分配单位 —— 帧，把逻辑地址空间也划分为相同大小的基本分配单位 —— 页，具体如下：

  • 帧（frame）：又称页帧（page frame）或物理页面，物理地址空间的基本单元，大小是 \(2^{n}\)，在 32 位系统中一般为 4K（4096，\(2^{12}\)）字节
  • 页（page）：又称页面或逻辑页面，逻辑地址空间的基本单元，大小和帧相同

将逻辑地址空间映射为物理地址空间遵循如下步骤：

  1. 根据 页号 在 页表 中查找相应的 帧号
  2. 根据帧号和 帧内偏移（或 页内偏移）得到真实的物理地址：\(s\times2^{n}+o\)

注意：一般来说，帧内偏移 = 页内偏移，帧号 != 页号。

每个进程都有一个页表，页表由一个个的 页表项 组成，页表的基址存储在 页表基址寄存器（PTBR，Page Table Base Register）中，页表项由以下内容组成：

  • 帧号
  • 页表项标志位：
    • 存在位（resident bit）：是否有帧号与此页号对应，若有，则为 1
    • 修改位（dirty bit）：表示在内存中的该页是否被修改过，用于虚拟页式存储中，回收该物理页面时，据此判断是否要把它的内容写回外存。
    • 引用位/访问位（clock/reference bit）：表示该页面是否被访问过（读或写），用于页面置换算法
    • 保护位：表示该页的允许访问方式，只读、可读写、可执行等，用于虚拟页式存储中。
    • 驻留位：表示该页是否在内存，用于虚拟页式存储中，1 表示该页位于内存中，该页表项是有效的，可以使用；0 表示该页当前在外存中，访问该页表项将导致缺页异常。

页式存储管理存在以下性能问题：

  • 内存访问性能：访问一个内存单元需要 2 次内存访问，第一次访问页表项，第二次才访问数据。
  • 页表大小问题：页表可能非常大

通过缓存（Caching）可以解决内存访问性能问题，通过间接（Indirection）访问可以解决页表大小问题。具体来说，通过快表（Translation Look-aside Buffer，TLB）缓存近期访问的页表项到 CPU 中；多级页表通过间接引用将页号分成 k 级，如果所有页表项都存在的话，使用多级页表实际上存储并没有减少，但实际中运行的进程，多数并不会用到整个所有的页表，在这种情况下，我们可以通过各级页表中的存在位把那些不存在的给省掉，这样可以节省空间。

此外，通过页寄存器和反置页表也可以解决上述的页表大小的问题。

段页式存储管理

段式存储在内存保护方面有优势，页式存储在内存利用和优化转移到后备存储方面有优势，段页式存储管理则是将这两者结合起来。

具体来说，在段式存储管理基础上，给每个段加一级页表。

在段页式存储管理中可以很方便的实现内存共享，即通过指向相同的页表基址，实现进程间的段共享。

实验

首先，在实模式下通过 BIOS 15 号中断来探测物理内存大小。

其次，实现连续内存分配算法：首次适配算法（First Fit）。

最后，建立分页机制。

具体而言，要建立二级页表

Exercise 1

Exercise 2

Lab 3：虚拟内存管理

计算机系统时常出现内存空间不够用，为了解决此问题，可以使用以下办法：

  • 覆盖（overlay）：应用程序手动把需要的指令和数据保存在内存中
  • 交换（swapping）：操作系统自动把暂时不能执行的程序保存到外存中
  • 虚拟存储：在有限容量的内存中，以页为单位自动装入更多更大的程序

局部性原理（principle of locality）：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。具体来说，体现在以下方面：

  • 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内。
  • 空间局部性：当前指令和临近的几条指令，当前访问的数据和临近的几个数据都集中在一个较小区域内。
  • 分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置。

局部性原理的意义在于：从理论上来说，虚拟存储技术是能够实现的，而且可取得满意的效果。

虚拟存储的思路是将不常用的部分内存块暂存到外存。具体来说：

  • 装载程序时：只将当前指令执行需要的部分 页面 或 段 装入内存
  • 指令执行中需要的指令或数据不在内存（称为缺页或缺段）时：处理器通知操作系统将相应的 页面 或 段 调入内存。
  • 操作系统将内存中暂时不用的页面或段保存到外存：通过页面置换算法。

具体实现方式包括：

  • 虚拟页式存储：在页式存储管理的基础上，增加请求调页和页面置换
  • 虚拟段式存储

页面置换算法

当出现缺页异常时，需调入新页面而内存已满时，页面置换算法选择被置换的物理页面。页面置换算法大致分为两类：

  • 局部页面置换算法：置换页面的选择范围仅限于当前进程占用的物理页面内
    • 最优算法
    • 先进先出算法
    • 最近最久未使用算法
    • 时钟算法
    • 最不常用算法
  • 全局页面置换算法：置换页面的选择范围是所有可换出的物理页面
    • 工作集算法
    • 缺页率算法

最优页面置换算法（OPT，optimal）是指置换在未来最长时间不访问的页面。

先进先出算法（First-In First-Out，FIFO）是指选择在内存驻留时间最长的页面进行置换。

最近最久未使用算法（Least Recently Used，LRU）是指选择最长时间没有被引用的页面进行置换。如果某些页面长时间未被访问，则它们在将来还可能会长时间不会访问。

LRU 算法的可能实现方式：

  • 页面链表：系统维护一个按最近一次访问时间排序的页面链表，链表首节点是最近刚刚使用过的页面，链表尾节点是最久未使用的页面，访问内存时，找到相应页面，并把它移到链表之首，缺页时，置换链表尾节点的页面。
  • 活动页面栈：访问页面时，将此页号压入栈顶，并将栈内相同的页号抽出；缺页时，置换栈底的页面。

时钟置换算法（Clock）是 FIFO 和 LRU 的折中，其仅对页面的访问情况进行大致统计。具体来说，各页面组织成环形链表，指针指向最先调入的页面，访问页面时，在页表项记录页面访问情况，缺页时，从指针处开始顺序查找未被访问的页面进行置换。

实验

实现基于分页机制的虚拟内存管理，要建立缺页异常处理机制，实现先进先出页面置换算法（First-In First-Out）。

Exercise 1

Exercise 2

Lab 4：内核线程管理

进程

进程是指一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

进程控制块（PCB，Process Control Block）是操作系统管理控制进程运行所用的信息集合。

进程控制块主要包含以下 3 类信息：

  • 进程的标识信息：如执行的程序、进程 ID、父进程等
  • 进程的状态信息：如状态寄存器、内存地址空间、进程状态等
  • 进程所占用的资源信息：如堆栈、存储等

进程的基本状态：

  • 等待态：等待外设
  • 就绪态：等待CPU
  • 运行态：占有CPU

线程

线程是进程的一部分，描述指令流执行状态。它是进程中的指令执行流的最小单元，是 CPU 调度的基本单位。

线程的优点：

  • 一个进程中可以同时存在多个线程
  • 各个线程之间可以并发地执行
  • 各个线程之间可以共享地址空间和文件等资源

线程的缺点：

  • 一个线程崩溃，会导致其所属进程的所有线程崩溃

线程 = 进程 - 共享资源。线程与进程的比较：

  • 进程是资源分配单位，线程是 CPU 调度单位。
  • 进程拥有一个完整的资源平台，而线程只独享指令流执行的必要资源，如寄存器和栈
  • 线程同样具有就绪、等待和运行三种基本状态和状态间的转换关系
  • 线程能减少并发执行的时间和空间开销
    • 线程的创建时间比进程短
    • 线程的终止时间比进程短
    • 同一进程内的线程切换时间比进程短
    • 由于同一进程的各线程间共享内存和文件资源，可不通过内核进行直接通信。
  • 进程主要是隔离，线程主要是共享。

实现线程通常有三种方法：

  • 用户线程：在用户空间实现
  • 内核线程：在内核中实现
  • 轻量级进程：在内核中实现，支持用户线程

进程控制

Unix 进程创建系统调用：fork/exec：

  • fork() 把一个进程复制成二个进程，parent(old PID)，child(new PID)
  • exec() 用新程序来重写当前进程，PID 没有改变

用 fork 和 exec 创建进程的示例：

int pid = fork();  // 创建子进程
if(pid == 0){  // 子进程在这里继续
    // Do anything
    exec("program", argc, argv0, argv1, ...)
}

子进程的 fork() 返回 0，父进程的 fork() 返回子进程标识符，fork() 返回值可方便后续使用，子进程可使用 getpid() 获取 PID。

fork 的实现大致为：

  1. 父进程复制 PCB
  2. 修改 PCB 中的进程 ID
  3. 将复制修改好的 PCB 放入就绪队列

exec 的实现大致为：

  1. 读取磁盘中的程序
  2. 将其加载到相应地内存地址

实验

创建进程相关的数据结构和算法。

具体而言，创建进程控制块（PCB）数据结构，创建进程创建（do_fork）函数。

打印字符串

Lab 5：用户进程管理

实验

创建进程执行（do_execve）函数。

执行 ELF 格式的二进制程序。

Lab 6：处理器调度

进程（CPU）调度算法：

  • 先来先服务算法（FCFS）
  • 时间片轮转算法（Round-Robin）
  • 短进程优先算法
  • 最高响应比优先算法
  • 多级反馈队列算法
  • 公平共享调度算法

先来先服务算法

依据进程进入就绪状态的先后顺序排列，进程进入等待或结束状态时，就绪队列中的下一个进程占用 CPU。

优点：

  • 简单

缺点：

  • 平均等待时间波动较大
  • I/O 资源和 CPU 资源的利用率较低

短进程优先算法

选择就绪队列中执行时间最短进程占用 CPU 进入运行状态。就绪队列按 预期 的执行时间来排序

优点：

  • 具有最优平均周转时间

缺点：

  • 可能导致饥饿
  • 需要预知未来

最高响应比优先算法

选择就绪队列中响应比 R 值最高的进程，R = (w+s)/s，w：等待时间，s：执行时间。

时间片轮转算法

时间片是分配处理机资源的基本时间单位，时间片结束时，按 FCFS 算法切换到下一个就绪进程，每隔 (n-1) 个时间片进程执行一个时间片 q

实验

实现先来先服务调度算法（First-Come First-Served）、轮转调度算法（Round Robin）。

Lab 7：同步互斥

同步互斥

同步是指协调多线程对共享数据的访问，即任何时刻只能有一个线程执行临界区代码。

锁是一个抽象的数据结构，其包含：

  • 一个二进制变量（锁定/解锁）
  • Lock::Acquire()：锁被释放前一直等待，然后得到锁
  • Lock::Release()：释放锁，唤醒任何等待的进程

使用锁来控制临界区访问：

lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

信号量

信号量（semaphore）是操作系统提供的一种协调共享资源访问的方法。

信号是一种抽象数据类型，由一个整形（sem）变量和两个原子操作组成：

  • P()：Prolaag，荷兰语尝试减少，sem 减 1，如 sem<0，进入等待，否则继续
  • V()：Verhoog，荷兰语增加，sem 加 1，如 sem<=0，唤醒一个等待进程
class Semaphore {
    int sem;
    WaitQueue q;
}

Semaphore::P() {
    sem--;
    if (sem < 0) {
        Add this thread t to q;
        block(p);
    }
}

Semaphore::V() {
    sem++;
    if (sem <= 0) {
        Remove a thread t from q;
        wakeup(t);
    }
}

管程

死锁

死锁是由于竞争资源或者通信关系，两个或更多线程在执行中出现，永远相互等待只能由其他进程引发的事件。

比如线程 1 正在使用文件 A，同时想要使用文件 B，而文件 B 此时正被线程 2 所使用，线程 2 此时又想使用文件 A，这就造成了死锁。

出现死锁必须同时满足以下 4 个必要条件：

  • 互斥：任何时刻只能有一个进程使用一个资源实例。
  • 持有并等待：进程保持至少一个资源，并正在等待获取其他进程持有的资源。
  • 非抢占：资源只能在进程使用后自愿释放。
  • 循环等待：

死锁的处理方法有：

  • 死锁预防（Deadlock Prevention）：确保系统永远不会进入死锁状态。
  • 死锁避免（Deadlock Avoidance）：在使用前进行判断，只允许不会出现死锁的进程请求资源。
  • 死锁检测和恢复（Deadlock Detection & Recovery）：在检测到运行系统进入死锁状态后，进行恢复。

通常操作系统忽略死锁，由应用进程处理死锁。

银行家算法是死锁避免的一种方法。

进程通信

进程通信（IPC，Inter-Process Communication）是进程进行通信和同步的机制。

任何 IPC 都提供 2 个基本操作：

  • 发送操作：send(message)
  • 接收操作：receive(message)

进程通信流程：

  1. 在通信进程间建立通信链路
  2. 通过 send/receive 交换消息

进程通信方式有：

直接通信

直接通信是在两个进程之间建立一个通信信道（即共享信道），两个进程必须同时存在才能够进行通信。

要进行直接通信，进程必须正确的命名对方：

  • send(P, message)：发送信息到进程 P
  • receive(Q, message)：从进程 Q 接收消息

直接通信中的通信链路具有以下属性：

  • 自动建立链路
  • 一条链路恰好对应一对通信进程
  • 每对进程之间只有一个链路存在
  • 链路可以是单向的，但通常是双向的

间接通信

间接通信是通过操作系统维护的消息队列实现进程间的消息接收和发送。

在间接通信中，每个消息队列都有一个唯一的标识，只有共享了相同消息队列的进程，才能够通信。

间接通信中通信链路具有以下属性：

  • 只有共享了相同消息队列的进程，才建立链路
  • 链路可以是单向或双向
  • 消息队列可以与多个进程相关联
  • 每对进程可以共享多个消息队列

间接通信的通信流程如下：

  1. 创建一个新的消息队列
  2. 通过消息队列发送和接收消息
  3. 销毁消息队列

间接通信的基本通信操作：

  • send(A, message)：发送信息到队列 A
  • receive(A, message)：从队列 A 接收消息

进程通信可划分为阻塞（同步）或非阻塞（异步）：

  • 阻塞通信
    • 阻塞发送：发送者在发送消息后进入等待，直到接收者成功收到。
    • 阻塞接收：接收者在请求接收消息后进入等待，直到成功收到一个消息。
  • 非阻塞通信
    • 非阻塞发送：发送者在消息发送后，可立即进行其他操作。
    • 非阻塞接收：没有消息发送时，接收者在请求接收消息后，接收不到任何消息。

进程发送的消息在链路上可能有 3 种缓冲方式：

  • 0 容量：发送方必须等待接收方
  • 有限容量：通信链路缓冲队列满时，发送方必须等待
  • 无限容量：发送方不需要等待

进程间通信的 4 种方法：

信号

信号（Signal）是进程间的软件中断通知和处理机制。如：Ctrl + c 或 kill -9。

信号的接收处理：

  • 捕获（catch）：执行进程指定的信号处理函数被调用
  • 忽略（Ignore）：执行操作系统指定的缺省处理，例如进程终止、进程挂起等
  • 屏蔽（Mask）：禁止进程接收和处理信号，可能是暂时的（当处理同样类型的信号）

信号的不足在于传送的信息量小，只有一个信号类型，仅仅用来做一种快速的响应机制，它比别的通信要快。

管道

管道（Pipe）是进程间基于内存文件的通信机制。如：ls | more。

管道是 Linux 中一种比较常见的做法。

消息队列

消息队列（Message Queues）是由操作系统维护的以字节序列为基本单位的间接通信机制。

共享内存

共享内存是把同一个物理内存区域同时映射到多个进程的内存地址空间的通信机制。

共享内存的优点是快速、方便地共享数据，缺点是必须用额外的同步机制来协调数据访问。

实验

实现锁机制、信号量机制。

Lab 8：文件系统

文件系统

概念

文件系统是操作系统中管理持久性数据的子系统，提供数据存储和访问功能。

文件是具有符号名，由字节序列构成的数据项集合。文件是文件系统的基本数据单位。文件名是文件的标识符号。

文件描述符是指操作系统在打开文件表中维护的打开文件状态和信息。

文件以目录的方式组织起来。目录是一类特殊的文件，目录的内容是文件索引表，即 <文件名，指向文件的指针>。

文件别名即两个或多个文件名关联同一个文件。具体可分为：

  • 硬链接：多个文件项指向一个文件。
  • 软链接：以“快捷方式”指向其他文件。通过存储真实文件的逻辑名称来实现。

文件系统需要先挂载才能被访问。

文件系统具体可分为如下几类：

  • 磁盘文件系统
  • 数据库文件系统
  • 日志文件系统
  • 网络/分布式文件系统
  • 特殊/虚拟文件系统

虚拟文件系统

虚拟（逻辑）文件系统（VFS，Virtual File System）的目的是对所有不同文件系统的抽象。其提供如下功能：

  • 提供相同的文件和文件系统接口
  • 管理所有文件和文件系统关联的数据结构
  • 高效查询例程，遍历文件系统
  • 与特定文件系统模块的交互

具体来说，文件系统基本数据结构有：

  • 文件卷控制块（Unix：superblock）：每个文件系统一个。当文件系统挂载时进入内存。
  • 文件控制块（Unix：vnode/inode）：每个文件一个。当文件被访问时进入内存。
  • 目录项（Linux：dentry）：每个目录项一个。在遍历一个文件路径时进入内存。

冗余磁盘阵列

  • RAID-0：
  • RAID-1（磁盘镜像）：向两个磁盘写入，从任何一个读取
  • RAID-4：

I/O 子系统