概述

指令

指令是计算机运行的最小的功能单元，是指挥计算机硬件运行的命令

• 算术运算指令
• 逻辑运算指令
• 移位操作指令
• 数据传送指令
• 输入输出指令
• 转移指令等

操作码 + 操作数

在硬件和应用软件之间引入操作系统

• 管理系统的各个部件，使之能正常运转；
• 给上层的应用软件提供一个易于理解和编程的接口

操作系统发展历史

• 1946-1950
  • 机器语言，纸带或卡片
• 50年代末-60年代中
  • 批处理管理程序
  • 串行执行，单道批处理
  • 60年代初发展了通道与中断技术
• 60年代中-70年代中
  • 现代意义上的操作系统的出现
  • 多道批处理系统
• 70年代中-至今
  • 分时系统
    • CTSS
    • MULTICS
    • UNIX
• 个人计算机操作系统

操作系统类型

• 批处理操作系统（多道批处理）
• 分时操作系统
• 实时操作系统
• 嵌入式系统
• 个人计算机操作系统
• 分布式操作系统

操作系统需要的硬件特性

受保护的指令

• 对某些硬件资源直接访问的指令

• 对内存管理状态进行操作的指令

• 某些特殊的状态位的设置指令

• 停机指令

根据运行程序对资源和机器指令的使用权限，把处理器设置为不同状态

• 管态：操作系统的管理程序运行时的状态，较高的特权级别，又称为特权态、系统态、内核态，处于该状态时可以执行所有的指令（包括特权指令）、使用所有的资源，并具有改变处理器状态的能力
• 目态：用户程序运行时的状态，较低的特权级别，又称为普通态（普态）、用户态。在此状态下禁止使用特权指令，不能直接使用系统资源与改变CPU状态，并且只能访问用户程序所在的存储空间

有的系统分为核心状态，管理状态和用户程序状态（目标状态）三种

程序状态字PSW (Program Status Word )一个专门的寄存器，用来指示处理器的状态，包括

• CPU的工作状态码
• 条件码
• 中断屏蔽码

系统调用

用户程序通过特殊的访管指令，来请求操作系统为其提供某种功能的服务

• 当CPU执行访管指令时，即引起访管中断；
• 处理器保存中断点的程序执行上下文环境（PSW, PC和其他的一些寄存器），CPU切换到内核态。
• 中断处理程序开始工作，调用相应的系统服务；
• 中断处理结束后，恢复被中断程序的上下文环境，CPU恢复为用户态，回到中断点继续执行。

内存保护

• 防止一个用户程序去访问其他用户 程序的数据；
• 保护操作系统免受用户程序的破坏。

最简单的做法：基址寄存器和边界寄存器。在开始运行一个程序时，由操作系统负责给基址寄存器和边界寄存器设置相应的值

虚拟存储技术：把内存和外存结合起来使用，硬件提供虚、实地址映射的机制。

中断机制

• 同步中断：指当CPU正在执行指令的时候，由CPU的控制单元所发出的中断，也称为“异常”
  • CPU检测到的异常，包括：错误Fault、陷阱Trap和中止Abort，例如：算术溢出、被零除、用户态下使用了特权指令等；
  • 程序设定的异常，即程序员通过int、int3等指令来发出的中断请求，也称为软中断，主要用来实现系统调用服务。
• 异步中断：指由其他的硬件设备在任意的时刻所发出的中断，简称为“中断” ；
  • 可屏蔽中断，即I/O中断，它是当外部设备或通道操作正常结束或发生错误时所发生的中断。例如：打印机打印完成、缺纸，读磁盘时驱动器中没有磁盘等；
  • 不可屏蔽中断，例如：由掉电、存储器校验错等硬件故障引起的硬件中断；

每一个中断或异常都用一个0－255之间的整数来标识，称为中断向量，系统根据中断向量，来为每一个中断或异常指定相应的处理程序

I/O系统

完成计算机系统中信息的输入输出功能

时钟操作

时钟是操作系统运行时必不可少的硬件设施，在操作系统中需要时钟支持的工作有：

• 在分时系统中，间隔时钟实现进程间按时间片轮转；
• 在实时系统中，按要求的间隔输出正确的时间信号给实时的控制设备；
• 记录用户和系统所需的绝对时间（年、月、日、时、分、秒）。

进程管理

进程 process

前置知识

CPU

• 控制单元
  • 能够正确并且自动地连续执行指令
  • 能正确并分步完成每一条指令的功能读取指令、分析指令、控制执行
  • 响应并处理中断
• 执行单元
  • CPU的“计算器”
  • 分为不同的功能部件，包括算术逻辑单元（ALU，+-*/）、移位器、乘法器、除法器、分支单元等
  • 来自控制单元的信号选择不同的功能部件
• 寄存器组
  • General-purpose register
  • Segment register
  • EFLAGS register
  • EIP

虚拟/物理计算机

• 虚拟CPU
• 虚拟内存
  • 栈
  • 堆
  • 静态数据
  • 代码

进程基本

process = program in execution

一个进程应该包括：

• 程序的代码；
• 程序的数据；
• CPU寄存器的值，如PC，用来指示下一条将运行 的指令、通用寄存器等；
• 堆、栈；
• 一组系统资源（如地址空间、打开的文件）

总之，进程包含了正在运行的一个程序的所有状态信息。

栈Stack

• 只允许在一端插入和删除。允许插入和删除的一端称为栈顶 (top)，另一端称为栈底 (bottom)
• 特点：后进先出(LIFO)
• 栈的主要操作
  • 进栈 Push
  • 出栈 Pop
• 栈的用途
  • 用于暂存功能，在程序运行时保存运行上下文信息
  • 在函数调用发生时，保存被调用函数的局部变量和形参

堆Heap

• 内存中的一块空间，用于动态分配；
• 在C语言中，通过malloc来申请动态内存空间，通过free来释放；
• 使用不当可能导致内存泄漏。

进程的特性

• 动态性：程序的运行状态在变，PC、寄存器、堆和栈等；
• 独立性：是一个独立的实体，是计算机系统资源的使用单位。每个进程在一个“虚拟计算机”上运行，每个进程都有“自己”的PC和内部状态，运行时独立于其他的进程（虚拟PC和物理PC）；
• 并发性：从宏观上看各进程是同时独立运行的

进程的创建

引起进程创建的三个主要事件：

• 系统初始化时；
• 在一个正在运行的进程当中，执行了创建进程的系统调用；
• 用户请求创建一个新进程。

从技术上来说，只有一种创建进程的方法，即在一个已经存在的进程（用户进程或系统
进程）当中，通过系统调用来创建一个新的进程。

• Unix：fork函数；
• Windows：CreateProcess函数;

进程的状态

进程的三种基本状态：

• 运行状态（Running）：进程占有CPU，并在CPU上运行。处于此状态的进程数目小于等于CPU的数目。
• 就绪状态（Ready）：进程已经具备运行条件，但由于CPU忙暂时不能运行，只要分得CPU即可执行；
• 阻塞状态（Blocked）：指进程因等待某种事件的发生而暂时不能运行的状态（如I/O操作或进程同步）,此时，即使CPU空闲，该进程也不能运行。

进程转换

• 运行 –> 阻塞
  • 等待I/O的结果
  • 等待某一进程提供输入
• 运行 –> 就绪
  • 运行进程用完了时间片
  • 运行进程被中断，因为一高优先级进程处于就绪状态
• 就绪 –> 运行
  • 调度程序选择一个新的进程运行
• 阻塞 –> 就绪
  • 当所等待的事件发生时

描述进程的数据结构：进程控制块（Process Control Block，PCB）

系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息

虚拟CPU即为存放在PCB中的内存变量

系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志

状态对列

• 操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；
• 不同的状态分别用不同的队列来表示（运行队列、就绪队列、各种类型的阻塞队列）；
• 每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列。

使用链表实现

线程 thread

进程 ＝ 线程 ＋ 资源平台

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

TCP

线程与进程比较

• 进程是资源分配单位和操作系统保护单位，线程 是CPU调度单位；
• 进程拥有一个完整的资源平台，如代码、数据和 堆，而线程只独享必不可少的资源如寄存器和栈
• 线程同样具有就绪、阻塞和执行三种基本状态， 同样具有状态之间的转换关系；
• 线程能减少并发执行的时间和空间开销；
• 线程 ＝ 轻量级进程（lightweight process）

进程间通信

进程之间的信息交流与协调

并发进程之间的两种关系：

• 相互独立：进程之间没有任何关联关系，仅有CPU竞争关系；
• 相互关联：进程之间存在着某种关联关系（直接或间接），需要相互通信。

进程间通信方式

• 低级通信：只能传递状态和整数值（控制信息）
  • 信号量（semaphore）
  • 信号（signal）
• 高级通信：能够传送任意数量的数据
  • 共享内存（shared memory）
  • 消息传递（message passing）
  • 管道（pipe）

进程互斥的产生原因

• 进程宏观上并发执行，依靠时钟中断来实现微观上轮流执行；
• 访问共享资源。

竞争状态

两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。在同一时刻，只允许一个进程访问该共享数据

对共享内存或共享文件的访问，可能会导致竞争状态的出现，把完成这类事情的那段程 序称为“临界区”，把需要互斥访问的共享资 源称为“临界资源”。

实现互斥访问的四个条件

• 任何两个进程都不能同时进入临界区；
• 不能事先假定CPU的个数和运行速度；
• 当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；
• 任何一个进程进入临界区的要求应该在有限时间内得到满足。

实现

基于关闭中断的互斥实现

当一个进程进入临界区后，关闭所有的中断；当它退出临界区时，再打开中断。

• 进程的切换是由中断引发的，关闭中断后，CPU不会被分配给其他进程，其他进程无法执行；
• 操作系统内核经常使用这种方法来更新内部的数据结构（变量、链表等）

基于繁忙等待的互斥实现

• 加锁标志位法

lock的初始值为0，当一个进程想进入临界区时，先查看lock的值，若为1，说明已有进程在临界区内，只好循环等待。等它变成了0，才可进入。

缺点：可能出现针对lock的竞争状态问题。

• 强制轮流法

基本思想：每个进程严格地按照轮流的顺序来进入临界区。

优点：保证在任何时刻最多只有一个进程在临界区
缺点：违反了互斥访问四条件中的第三个条件

• Peterson方法

当一个进程想进入临界区时，先调用enter_region函数，判断是否能安全进入，不能的话等待；当它从临界区退出后，需调用leave_region函数，允许其它进程进入临界区。两个函数的参数均为进程号。

基于繁忙等待的互斥实现缺点

• 浪费CPU时间；

• 可能导致预料之外的结果（如：一个低优先级进程位于临界区中，这时有一个高优先级的进程也试图进入临界区）

信号量

semaphore

取值可正可负，正数表示当前空闲资源的数量，负数的绝对值表示正在等待进入临界区的进程个数。

由操作系统来维护，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。初始化可指定一个非负整数，即空闲资源总数。

原语不会被中断

• P、V原语包含有进程的阻塞和唤醒机制，因此在进程等待进入临界区时不会浪费CPU时间；

• P原语：申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；

• V原语：释放一个被占用的资源（把信号量加1），若发现有被阻塞的进程，则选择一个唤醒之

信号量与PV原语的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

typedef struct{
    int   count;			// 计数变量
    struct  PCB *queue;	    // 进程等待队列
} semaphore;

P( semaphore  S){
    --S.count;		    //表示申请一个资源;
    if (S.count < 0){	//表示没有空闲资源;
      该进程进入等待队列S.queue末尾;
      阻塞该进程;
      调用进程调度器；     // OSSched( )
    }
}

V( semaphore  S){
    ++S.count;		    //表示释放一个资源;
    if (S.count <= 0){  //表示有进程被阻塞;
      从等待队列S.queue中取出一个进程;
      把该进程改为就绪状态，插入就绪队列
    }
}

• Windows
  • CreateSemaphore（创建信号量）
  • WaitForSingleObject（P操作）
  • ReleaseSemaphore（V操作）
• COS-II
  • osSemCreate（创建信号量）
  • osSemPend （P操作）
  • osSemPost（V操作）
• Python
  • threading.Semaphore类
  • ```python
    Semaphore(value = 1)
    acquire(blocking = True, timeout=None)
    release(n=1)

    1 2 3 4 5 6 7 8 9 10

    - value：构造函数的参数，默认为1，即互斥 - acquire：相当于P原语，申请一个资源，若成功则退出，若失败则阻塞当前线程 - release：相当于V原语，释放一个资源，若当前有线程被阻塞，则唤醒 利用信号量来实现进程互斥 ``` c int count; semaphore mutex; //初始化为1

1
2
3
4
5
6

//各进程
非临界区
P(mutex);
临界区
V(mutex);
非临界区

进程间同步

指多个进程中发生的事件存在某种时序关系，因此在各个进程之间必须协同合作，相互配合，使各个进程按一定的速度执行，以共同完成某一项任务。

• 同步：合作

• 互斥：竞争

只考虑基于信号量的同步问题。

先A执行后B执行实现

进程调度

调度器

1
2
3
4
5
6

if ( readyProcesses(PCBs) ) {
	nextPCB = selectProcess(PCBs);
	run( nextPCB );
} else {
	run_idle_process();
}

CPU繁忙（CPU-bound）的进程：大部分时间 处于运行和就绪状态；
I/O繁忙（I/O-bound）的进程：大部分时间处 于阻塞状态。

两种调度方式

• 不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出CPU。以上的情形1－3均可发生调度；
• 可抢占调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形1－5均可发生调度

算法

时间片轮转法

• 在时间片轮转算法（Round-Robin，RR）中，将所有的就绪进程按照FCFS原则，排成一个队列；
• 每次调度时将处理器分派给队首进程，让其执行一小段CPU时间（时间片）；
• 在一个时间片结束时，如果进程还没有执行完的话，在时钟中断中，进程调度程序将暂停当前进程的执行，并将其送到就绪队列的末尾，然后执行当前的队首进程；
• 如果一个进程在它的时间片用完之前就已结束或被阻塞，那么立即让出CPU。

优点

• 公平性：各个就绪进程平均地分配CPU的使用时间。假设有n个就绪进程， 那么每个进程将得到1/n的CPU时间；
• 活动性：若时间片大小为q，每个进程最多等待(n-1)q时间就能够再次得到CPU去运行。

缺点：q的大小难以确定

• q太大：退化为FCFS算法，进程在一个时间片内执行完或被阻塞，响应时间长。如q=100ms；
• q太小：每个进程需要更多时间片才能处理完，进程切换次数增加(1ms)，增大系统开销；
• 一般在20－50ms

优先级算法

给每个进程设置一个优先级，然后在所有就绪进程中选择优先级最高的那个进程去运行；

可以把进程按照不同的优先级别分组，然后在不同级别之间使用优先级算法，而在同一级别的各个进程之间使用时间片轮转法。

饥饿（Starvation）：低优先级的进程始终得不到CPU去运行

解决办法：动态优先级。

优先级反转

• T1 优先级高、T2 优先级低
  • T2 获得了锁 L
  • T1 试图去获取L，失败，被阻塞。T3 进入系统，其优先级高于T2、低于T1。 T2 无法运行。

储存管理

储存管理概述

理想的存储器

更大、更快、更便宜的非易失性存储器

存储器系统的层次结构

• 寄存器
• 高速缓存
  • Cache
• 主存储器
  • DRAM
• 外部存储器
  • 硬盘、光盘、U盘

工作原理

• 一个内存中包含有许多存储单元，每个单元可以存放一个适当单位的信息
• 全部存储单元按一定顺序编号，这种编号称为存储器的地址。对各个存储单元的读写操作就是通过它们的地址来进行的

单道程序储存管理

内存分为两个区域：系统区，用户区。

每次把一个应用程序装入到用户区运行，由它和操作系统来共享内存。当它运行结束后，操作系统再装入一个新的程序把它覆盖

优点

• 简单、开销小，易于管理；
• 适合于单用户、单任务的OS

缺点

• 每次只能运行一个程序
• 内存资源的使用效率不高
  • 程序较小时，会浪费大量的内存空间
• OS的保护
  • 应用程序的bug会破坏OS
• 地址空间有限
  • 即为物理内存的大小

多道存储管理需考虑

• 内存管理
• 内存分配
• 内存回收
• 地址重定位
• 内存保护
• 内存共享

分区储存管理

内存分为两大区域：系统区，用户区。又把用户区划分为若干分区(partition)。一个进程占用一个分区

特点：适合多道程序系统和分时系统，支持多个程序并发执行

固定分区存储管理

各个用户分区的个数、位置和大小一旦确定以后，就固定不变

分区大小

• 多个小分区、适量的中等分区、少量大分区

输入队列

• 管理进程进入分区

数据结构

• 设置内存分配表

内存分配

• 先放入输入队列，然后采用最先匹配法、最佳匹配法等算法

内存回收

• 简单

缺点

• 内存利用率不高，内碎片造成很大浪费。所谓内碎片，即进程所占用分区之内的未被利用的空间。
• 分区的总数固定，限制了并发执行的程序个数，不够灵活。
• 地址空间的大小有限。

可变分区储存管理

可变分区（动态分区）

• 初始时，操作系统会占用内存的一部分，其余空间为一个完整的大空闲区
• 当一个程序要求装入内存运行时，系统从这个空闲区中划一块分配给它
• 当程序完成后释放所占用的存储区
• 随着一系列的内存分配和回收，原来的一整块大空闲区就形成了若干占用区和空闲区相间的布局

特点

• 分区的个数、位置和大小都是随进程的进出而动态变化的，非常灵活，避免了在固定分区中因分区大小不当所造成的内碎片，提高了内存利用率。
• 有外碎片，即各个占用分区之间难以利用的空闲分区。
• 使得内存的分配、回收和管理更为复杂

地址映射（重定位）

CPU访问内存的两种模式

• 实模式：直接访问内存，8086 CPU的工作方式，数据总线和寄存器各16位，地址总线20位，可访问内存空间1M。现代计算机在刚加电时运行在实模式，单道；
• 保护模式：需要进行地址映射，286以后CPU采用的工作方式

虚拟计算机

物理地址

• 也叫内存地址、绝对地址，实地址；
• 把内存分成很多个大小相等的存储单元，每个单元给一个编号，这个编号称为物理地址；
• 物理地址可以直接寻址；
• 物理地址的集合称为物理地址空间（内存地址空间），它是一个一维的线性空间。

逻辑地址

• 也叫相对地址，虚地址；
• 用户程序经汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都是相对首地址来编址；
• 内存保护：逻辑地址与物理地址分离。

地址映射

• 为保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，此过程称为地址映射

为了保证CPU执行指令时可正确访问存储单元，在装入程序时必须进行地址映射，将程序中的
逻辑地址转换为物理地址。这主要有两种方式：

• 静态地址映射（静态重定位）
  • 当用户程序被装入内存时，直接对指令代码进行修改，一次性实现逻辑地址到物理地址的转换。
  • 无需额外硬件，适用于嵌入式系统
• 动态地址映射（动态重定位）
  • 当用户程序被装入内存时，不对指令代码做任何修改。而是在程序运行过程中，当需要访问内存单元时再来进行地址转换（即在逐条执行指令时完成转换）。
  • 由硬件地址映射机制完成，如设置一个基地址寄存器，并装入进程所在分区起始地址；
  • 在程序运行时，硬件自动完成地址映射

储存保护

为了防止一个用户程序去访问其他用户程序的内存分区，保护操作系统免受用户程序的破坏，须进行存储保护

最简单的做法：在基地址寄存器的基础上再增加一个限长寄存器，记录分区长度。这两者在一起，就定义了进程所在的分区

CPU组件

CPU+MMU->发送指令到总线

MMU作用

• 内存保护
• 内存共享

页式和段式存储管理

页式存储管理

基本原理

• 把物理内存划分为许多个固定大小的内存块，称为物理页面，或页框（page frame）；

• 把逻辑地址空间划分为大小相同的块，称为逻辑页面，或简称页面（page）；

• 页面大小为2^n，一般在512字节到8K字节之间；

• 当一个用户程序装入内存时，以页面为单位进行分配。若要运行一个大小为n个页面的程序，

  需要有n个空闲的物理页面把它装入，这些页面不必是连续的

数据结构

页表：系统为每一个进程都建立了一个页表，页表给出了逻辑页面号和具体内存块号（物理页面号）之间的对应关系

物理页面表：在系统中设立一张物理页面表，用来描述内存空间当中，各个物理页面的分配使用状况。具体实现：位示图，空闲页面链表

内存的分配与回收

内存的分配与回收算法与物理页面表的具体实现方法有关。这里以位示图为例。

内存的分配

• 计算一个进程所需要的页面数N，并查看位示图，看是否还有N个空闲页面；
• 若有，则申请一个页表，其长度为N，并把页表的起始地址填入PCB；
• 分配N个空闲物理页面，将其编号填入页表；
• 修改位示图（0→1，空闲页面数－N）

内存的回收

• 当一个进程运行结束，释放它所占用的内存空间后，需要对这些物理页面进行回收。
• 对于每一个物理页面，根据它的编号计算出它在位示图当中的相应位置，并将相应位的值从1改成0；
• 修改位示图中的空闲页面数：加上N

地址映射

• 对于给定的逻辑地址，找到逻辑页面号和页内偏移地址；
• 查找页表，找到相应的物理页面号；
• 计算最终的物理地址

把逻辑地址划分为两部分：逻辑页面号和页内偏移地址。这种划分是由系统自动完成的，对用户是透明的。由于页面的大小一般为2的整数次幂，因此，地址的高位部分即为页号，低位部分即为页内偏移地址

逻辑地址为十进制的形式的计算方法：

• 页号 ＝ 虚地址 / 页大小
• 位移量 ＝ 虚地址 % 页大小

页表的具体实现

• 页表保存在内存当中（内核空间）;
• 设置一个页表基地址寄存器（Page-table base register，PTBR），用来指向页表的起始地址；
• 设置一个页表长度寄存器（Page-table length register，PTLR），指示页表大小

在现有的方案中，每一次访问内存（数据/指令）时，都要做两次访问内存的工作。为缩短页表的查找时间，可以采用一种特殊的快速查找硬件：TLB (Translation Lookaside Buffer) 或称associative memory,用来存放那些最常用的页表项

优缺点

优点

• 没有外碎片，内碎片的大小不超过页面的大小；
• 一个程序不必连续存放；
• 进程看到连续逻辑地址空间，OS辛苦

缺点

• 程序必须全部装入内存；
• OS为每个进程维护一张页表，切换开销

段式存储管理

页式存储管理（和分区存储管理）只有一个逻辑地址空间，即一维的线性连续空间

存储保护

• 代码段：一条条指令组成，只读，可执行，无需写回磁盘；
• 数据段：全局变量，可修改，可读写，需写回磁盘；
• 栈：形参、局部变量、CPU寄存器、返回地址，可读写；

存储共享

• 在多个进程之间，共享代码和数据

基本原理

对程序的每个逻辑单元（代码、数据和栈等），设立一个完全独立的地址空间，称为“段”。每个段的内部是一维线性连续地址，大小可不同

对于物理内存来说，采用可变分区（动态分区）的管理方法

当一个程序需要装入内存时，以段为单位进行分配，把每一个段装入到一个内存分区当中，这些内存分区不必是连续的

具体实现

在段式存储管理中，用户空间地址为二维地址：(段号，段内偏移)。

实现方式：

• 地址高端为段号、低端为偏移；
• 指令中显式地给出段号和段内偏移。

段表：系统为每一个进程都建立了一个段表，它给出了进程当中的每一个段与它所对应的内存分区之间的映射关系。

段表的具体实现

• 段表保存在内存当中；
• 设置一个段表基地址寄存器（Segment-table base register，STBR），用来指向内存当中段表的起始地址；
• 设置一个段表长度寄存器（Segment-table length register，STLR），用来指示段表的大小，即程序当中的段的个数；

放在MMU里，轮到运行，操作系统更新

优缺点

优点

• 程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享；
• 一个程序不必连续存放，没有内碎片。

缺点：

• 程序必须全部装入内存、外碎片等。

段页式存储管理

段式存储和页式存储各有特点：

• 段式存储管理为用户提供了一个二维的逻辑地址空间，可以满足程序和信息的逻辑分段要求，反映了程序的逻辑结构，有利于段的共享、保护和动态增长；
• 页式存储管理的特征是等分内存，它有效地克服了碎片问题，提高了内存的利用率。

为了保持页式在存储管理上的优点和段式在逻辑上的优点，人们又提出了段页式存储管理技术

基本思想

先把程序划分为段，然后在段内分页。

内存划分：按页式存储管理方案
内存分配：以页面为单位进行分配

具体实现

• 段表：记录了每个段的页表起始地址和页表长度，而不是该段所在内存分区的起始地址。
• 页表：记录了逻辑页面号与物理页面号之间的对应关系。（每一段有一个，一个程序可能有多个页表）
• 需要的硬件支持：段表基地址寄存器（STBR）和段表长度寄存器（STLR）

虚拟储存技术

程序的局部性原理

局部性原理(principle of locality)

程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。

局部性原理的具体表现：

• 程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令；
• 程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行；
• 程序中存在很多对一定数据结构的操作，如数组操作，往往局限在较小范围内。

程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的

虚拟页式存储管理

当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面（0个或多个），就可启动程序运行。在运行的过程中，如果发现要执行的指令或要访问数据不在内存，则发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能继续运行。

• 当内存空间不够用时，需要把页面保存在磁盘上（backing store，后备存储）；

• 内存物理页面称为page frame，磁盘上的页面称为后备页面（backing frame）；

• 目的：提供一种错觉，内存的容量好像和磁盘容量一样大，且速度和内存一样快（理想状态）。

页表表项

每个页表项包含以下信息：逻辑页号、物理页号、驻留位、保护位、修改位、访问位、

• 驻留位（有效位）：表示该页是否在内存。若该位为1，表示该页位于内存中，即该页表项有效，可以使用；若该位为0，表示该页当前还在外存中，此时若访问该页表项，将导致缺页中断；
• 保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等；
• 修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存；
• 访问位：如果该页面被访问过（包括读操作或写操作），则设置此位。用于页面置换算法。

哪些位是CPU写OS读？哪些位是OS写CPU读？

缺页中断

在地址映射过程中，如果所要访问的逻辑页面 p 不在内存，则产生缺页中断(page fault)。中断处理过程：

• 如果在内存中有空闲的物理页面，则分配一页，设为 f，然后转第4步；否则转第2步；
• 采用某种页面置换算法，选择一个将被替换的物理页面 f，它所对应的逻辑页面为p’。如果该页在内存期间被修改过，则需把它写回外存；
• 对p’所对应的页表项进行修改，把驻留位置为0；
• 将需要访问的页面 p 装入到物理页面 f 当中（进程被阻塞），并修改 p 所对应的页表项的内容，把驻留位置为1，把物理页面号设置为 f；
• 重新运行被中断的指令（PC不变）。

用户进程感觉不到缺页中断的发生（就像进程切换一样）

页面置换算法

最优页面置换算法OPT

当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在它的下一次访问之前，还需等待多长时间，从中选择等待时间最长的那个，作为被置换的页面。

最近最久未使用算法LRU

当一个缺页中断发生时，选择最近最久未使用的那个页面，并淘汰之。

完美的LRU算法并不实用：

• 在每次内存访问时，都需要去更新该页面访问时间（时间戳法）或调整各个页面的先后顺序（链表法和栈法），开销很大；
• 缺乏硬件支持。

可行的做法：

• 对LRU算法的近似；
• 在硬件的支持下，使用某种简单而快速的方法来寻找比较老（而非最老）的页面

最不常用算法LFU

当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之。

实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加 1。在发生缺页中断时，淘汰计数值最小的那个页面。

先进先出算法FIFO

选择在内存中驻留时间最长的页面并淘汰之

性能较差，调出的页面有可能是经常要访问的页面

工作集模型

工作集

一个进程当前正在使用的逻辑页面集合，可以用一个二元函数W(t, $\Delta$)来表示：

• t是当前的执行时刻；
• $\Delta$ 称为工作集窗口（working-set window ），即一个定长的页面访问窗口；
• W(t, $\Delta$)＝在当前时刻 t 之前的 $\Delta$ 窗口当中的所有页面所组成的集合（随着 t 的变化，该集合也在不断地变化）；
• | W(t, $\Delta$) | 指工作集的大小，即页面数目。

工作集大小的变化：进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

驻留集

驻留集是指在当前时刻，进程实际驻留在内存当中的页面集合。

工作集是进程在运行过程中固有的性质，而驻留集取决于系统分配给进程的物理页面数目，以及所采用的页面置换算法

虚拟页式的设计问题

页面的分配策略

固定分配策略：驻留集大小固定。例如：各进程平均分配，或根据程序大小按比例分配等。

• 采用局部页面置换的方式，当发生一个缺页中断时，被置换的页面局限在本进程内部。
• 缺点：分配的物理页面数难以确定。进程在运行过程中，工作集的大小可能会不断地变化，若分配的页面数太少，则发生抖动；若分配的页面数太多，则浪费内存资源。

可变分配策略：驻留集大小可变。例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整驻留集的大小。

• 可采用全局页面置换的方式，当发生一个缺页中断时，被置换的页面可以是在其它进程当中，各个并发进程竞争地使用物理页面。
• 优缺点：性能较好，但增加了系统开销。
• 具体实现：可以使用缺页率算法(PFF, page fault frequency)来动态调整驻留集的大小。

PFF

缺页率表示“缺页次数 / 内存访问次数”(比率)或“缺页的平均时间间隔的倒数”。影响缺页率的因素：

• 页面置换算法
• 分配给进程的物理页面数目
• 页面本身的大小
• 程序的编制方法

若进程的缺页率过高，则分配更多的物理页面；若进程的缺页率过低，则减少它的物理页面数，力图使每个进程的缺页率保持在一个合理的范围内。

页表结构

为解决页表占内存过多的问题，需提出新的页表结构：

• 多级页表 (Multilevel Page Tables)；
• 反置页表(Inverted Page Tables)。

多级页表

由于不是所有的虚拟地址都会用到，所以不必把所有的页表项都保存在内存当中。

反置页表

• 根据内存中的物理页面号来组织页表，用物理页面号来作为访问页表的索引。页表项的个数仅与物理内存的大小和页面大小有关，与逻辑空间大小和进程数无关。

• 每个页表项记录了在相应的物理页面中，保存的是哪个进程的哪一个逻辑页面。

• 反置页表节省了大量内存空间，但逻辑页面号到物理页面号的转换变得更复杂，一种方法是Hash表.

I/O设备管理

I/O硬件

按交互方向分类：

• 输入设备：键盘、鼠标、扫描仪；
• 输出设备：显示器、打印机；
• 输入/输出：磁盘、网卡。

按数据组织分类：

• 块设备：
  • 以数据块作为信息的存储和传输单位，每个数据块都有一个地址，数据块之间的读写操作是相互独立的，如硬盘
• 字符设备：
  • 以字符作为信息存储和传输单位，数据即字符流，无定位无寻址，如鼠标、键盘

一个I/O单元由两部分组成：机械部分和电子部分（设备控制器或适配器）。

每个设备控制器都有一些寄存器用来与CPU通信。通过往这些寄存器中写入不同的值，OS能命令该设备去执行发送数据、接收数据、打开、关闭等操作；OS也能通过读取这些寄存器的值来了解设备的当前状态。此外，许多控制器还有一个数据缓冲区供OS读写。

CPU与设备控制器进行通信的方法有三种

I/O独立编址

基本思路

• 给控制器中的每一个寄存器分配一个唯一的I/O端口（I/O port）编号，称为I/O端口地址，然后用专门的I/O指令对端口进行操作；

• 这些端口地址所构成的地址空间是完全独立的，与内存的地址空间没有关系。

内存映像编址

基本思路

• 把所有控制器中的每个寄存器都映射为一个物理内存地址，专门用于I/O操作（功能上），对这些单元的读写操作即为普通的内存访问操作。
• 端口地址空间与物理内存的地址空间统一编址，前者是后者的一部分，一般位于后者的顶端部分

如：显存（帧缓存，frame buffer）

混合编址

基本思路

• 对于设备控制器中的寄存器，采用独立编址的方法；
• 而对于设备的数据缓冲区，采用内存映像编址的方法。

I/O控制方式

程序循环检测方式(Programmed I/O)

基本思路

• 在程序（设备驱动程序）中通过不断地检测I/O设备的当前状态，来控制I/O操作的完成。具体来说，在进行I/O操作之前，要循环地检测设备是否就绪；在I/O操作进行之中，要循环地检测设备是否已完成。从硬件来说，控制I/O的所有工作均由CPU来完成。
• 也称为繁忙等待方式（busy waiting）或轮询方式（polling）。

I/O控制与I/O操作

1 2 3 4 5

//已知I/O地址采用内存映像编址的方式，现需要在打印机上打印一个字符串“ABCDEFGH” for (i = 0; i < count; i++){ while(*printer_status_reg != READY); *printer_data_register = p[i]; }

中断驱动方式(Interrupt-driven I/O)

当一个I/O设备完成任务时，它的控制器会通过总线向中断控制器发出一个信号，如果中断控制器接受了该信号，就把标明该设备的一个编号放在地址线上，并向CPU发出一个中断信号。 CPU发现后就中断当前工作，并以该编号为索引去访问中断向量表，取出中断处理程序的起始地址，并在该程序运行后向中断控制器发出确认信号。

1 2 3

//用户进程 strcpy(buffer, “ABCDEFGH”); print(buffer, strlen(buffer));

1 2 3 4 5 6

//系统调用函数print copy_from_user(buffer, p, count); // p:内核缓冲区 enable_interrupts( ); while(*printer_status_reg != READY); *printer_data_register = p[0]; scheduler( );

1 2 3 4 5 6 7 8 9

//中断处理程序 if(count == 0){ unblock_user( ); }else{ *printer_data_register = p[++i]; count --; } acknowledge_intereupt( ); return_from_interrupt( );

直接内存访问方式(DMA, Direct Memory Access)

在硬件上需要一个DMA控制器。

DMA控制器可以直接去访问系统总线，它能代替CPU去指挥I/O设备与内存之间的数据传送。

I/O软件

I/O 设备管理软件的基本思想是采用分层的结构，把各种设备管理软件组织成一系列的层次

低层与硬件特性相关，它把硬件和较高层的软件隔离开来

I/O软件系统的层次
用户空间的I/O软件
设备独立的系统软件
设备驱动程序
中断处理程序
硬件

设备驱动程序

• 与具体的设备类型相关的，用来控制设备运行的程序。一般由设备生产商提供
• 通常是平台相关（如Windows/linux），适合于特定的某个设备（如键盘）或某类设备（如SCSI）
• 每一个I/O设备都需要相应的设备驱动程序，而每一个设备驱动程序一般只能处理一种设备类型。

设备独立的系统软件

设备独立的I/O软件（I/O子系统）是系统内核的一部分，其任务是实现所有设备都需要的一些通用的I/O功能，并向用户级软件提供一个统一的接口。

需要内核的I/O软件的原因

• I/O设备的种类繁多、功能各异，需要标准化接口
• I/O设备不可靠，如存储介质失效或传输错误
• I/O设备不可预测，且运行速度快慢不一

内核I/O子系统实现的主要功能：

• 给上层应用的统一接口
• 与设备驱动程序的统一接口
• 提供与设备无关的数据块大小
• 缓冲技术

上层接口

应用程序开发人员 - 程序/OS的接口 - 操作系统

• 设备独立性：使得用户在编写程序、访问各种I/O设备时，无需事先指定特定的设备类型，各种类型的设备之间的差异由OS来处理，对用户是透明的。
• 统一命名：即用简单的字符串或整数的方式来命名一个文件或设备。例如在Unix当中，所有的文件和设备都采用相同的命名规则：路径名。
• 阻塞与非阻塞I/O：当进程启动一个系统调用后，是立即返回还是被阻塞起来，直到I/O操作完成。

Windows中的CreateFile()函数

• 创建或打开以下的某种对象：控制台、通信资源（如串口）、目录、磁盘设备（分区）、文件（软盘、硬盘、光盘）等；
• lpFileName, // file name
• dwDesiredAccess, // 访问模式，读/写/执行等
• dwShareMode, // 共享模式，
• lpSecurityAttributes, // 安全属性
• dwCreationDisposition, // how to create
• dwFlagsAndAttributes, // file attributes
• 设备独立性。统一命名：
  • “A:\1.txt”、“C:\2.txt”、“F:\3.txt”、“COM1”、“\.\A:”、“\.\C:”、“CON”。

阻塞与非阻塞I/O

• 阻塞：进程被阻塞起来，直到I/O操作完成
  • 易于使用和理解
  • 有些情形下不能满足要求
• 非阻塞：I/O调用很快返回
  • 异步性：当I/O操作进行时进程继续执行，当I/O操作完成时，I/O子系统给进程发信号
  • 调用者具有主动权
  • 不易使用，多线程

阻塞I/O示例

1 2 3 4 5 6 7 8 9

//串口访问 HANDLE hCom; hCom = CreateFile("COM1",GENERIC_READ,0,NULL, OPEN_EXISTING, 0, NULL); //EV_RXCHAR: A character was received and placed in the input buffer SetCommMask(hCom, EV_RXCHAR); WaitCommEvent(hCom, &dwEvtMask, NULL); if (dwEvtMask & EV_RXCHAR) { ReadFile(hCom, buf, NumBytesToRead,NumBytesRead, NULL); }

非阻塞I/O示例

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

HANDLE hCom; OVERLAPPED o; hCom = CreateFile(“COM1”,GENERIC_READ,0, NULL, OPEN_EXISTING, FILE_FLAG_OVERLAPPED, NULL);//重叠I/O //EV_RXCHAR: A character was received and placed in the input buffer SetCommMask(hCom, EV_RXCHAR); o.hEvent = CreateEvent(NULL,...); bR = WaitCommEvent(hCom, &dwEvtMask,&o); if(!bR)ASSERT(GetLastError()== ERROR_IO_PENDING); r = WaitForSingleObject(o.hEvent,INFINITE); if(r == WAIT_OBJECT_0){ //有数据到达 bR = ReadFile(hCom, buf, sizeof(buf),&nBytesRead, &o); if( !bR ){ if(GetLastError()==ERROR_IO_PENDING){ r = WaitForSingleObject(o.hEvent,2000); if(r == WAIT_OBJECT_0) GetOverlappedResult(hCom, &o,&nBytesRead, FALSE); else if(r == WAIT_TIMEOUT)... } }

Linux简化版本

1 2 3 4 5 6

//阻塞地读取串口一个字符 char buf; fd=open("/dev/ttyS1",O_RDWR); .... res=read(fd,&buf,1); //当串口有输入时才返回 if(res==1) printf("%c\n",buf);

1 2 3 4 5 6

//非阻塞地读取串口一个字符 char buf; fd=open("/dev/ttyS1",O_RDWR|O_NONBLOCK); .... while(read(fd,&buf,1)!=1);//串口无输入也返回 printf("%c\n",buf);

下层接口

操作系统 - OS/设备驱动的接口 - 设备

• 为实现设备独立性，OS把各种类型的设备划分为三类：块设备、字符设备和网络设备，并为每一类定义了一个标准接口，大多数设备驱动程序都支持其中之一。
• 这个接口供上层的OS软件使用，它由一些抽象的函数组成，该接口是设备独立的。
• 分层：其他OS软件/接口/设备驱动程序。

字符设备驱动程序的接口

• open(deviceNumber)：启动设备并初始化
• close(deviceNumber)：关闭设备
• read(deviceNumber, buffer, size)：从一个字节流设备中读入size个字节到buffer缓冲区中
• write(deviceNumber, buffer, size)：从缓冲区buffer中取出size个字节写入到一个字节流设备中

块设备驱动程序的接口

• open(deviceNumber)：启动设备并初始化
• close(deviceNumber)：关闭设备
• read(deviceNumber, deviceAddr, buffer)：从设备地址deviceAddr处读入一块数据到buffer缓冲区
• write(deviceNumber, deviceAddr, buffer)：把buffer中的数据块写入到设备地址deviceAddr
• seek(deviceNumber, deviceAddress)：把访问指针定位到正确的位置

接口映射

用户空间的I/O软件

在用户态下执行的I/O软件

• 库函数：如C语言里与I/O有关的库函数write、read等，它们实质上只是将它们的参数再传递给系统调用函数，并由后者来完成实际的I/O操作；
• Spooling技术：在多道系统中，一种处理独占设备的方法。

利用假脱机技术（SPOOLing, Simultaneous Peripheral Operation On Line, 也称虚拟设备技术）可把独占设备转变成具有共享特征的虚拟设备，从而提高设备利用率。

实例

一次I/O请求的生命周期

字符驱动示例（互斥访问）

1 2 3 4 5 6 7 8 9 10 11 12 13

size_t foo_read(struct file *filp, char *buf,size_t count, loff_t *ppos){ foo_dev_t *foo_dev = filp->private_data; if(down_interruptible(&foo_dev->sem)//互斥 return -ERESTARTSYS; foo_dev->intr = 0; //同步 outb(DEV_FOO_READ, DEV_FOO_CONTROL_PORT); wait_event_interruptible(foo_dev->wait,(foo_dev->intr == 1)); // 被阻塞 if (put_user(foo_dev->data, buf)) return -EFAULT; up(&foo_dev->sem); return 1; }

1 2 3 4 5

void foo_interrupt(int irq,void *dev_id,struct pt_regs *regs){ foo->data = inb(DEV_FOO_DATA_PORT); foo->intr = 1; wake_up_interruptible(&foo->wait); }

块设备的驱动程序方案

• 数据结构：请求队列（request queue）；
• 块设备驱动程序：上层函数，负责管理请求队列；底层函数，负责与硬件打交道，完成真正的I/O；
• I/O请求的提交与真正实现是分离的。各个用户进程（通过内核）调用上层函数，提交I/O请求(mak_request)，然后阻塞；底层函数则从队列中取出每个I/O请求，并完成之。
• 能对各I/O请求进行优化，如数据块重组。

Example: A scsi disk driver in UNIX

• sdstrategy: do error checking, if device is not busy, issue a start request for the specific unit (disk).
• sdustart: find the proper queue for this unit, put the request on the queue, issue start.
• sdstart: request the resources needed for the request (scsi bus or DMA resources).
• sdgo: write the commands to the controller, set the interrupt vector, issue the start request to the controller.
• sdintr: called from I/O interrupt, finish the request (schedule the waiting process), issue a new request if there is one.

存储设备

磁盘

• 磁道：当传动装置固定在某个位置时，若盘面旋转一圈，磁头所能访问的圆环区域；
• 柱面：在所有盘面上，半径相同的所有磁道即组成一个柱面；
• 扇区：每一个磁道被划分为若干个扇区；
• 磁盘的访问过程：以扇区作为最小的寻址和存取单位。首先移动传动装置，通过它来移动磁头，从而定位正确的柱面。然后选中相应的磁头，等我们想要的扇区正好路过这个磁头正下方的时候，就可以对它进行访问了。

读写字节

• 读入包含该字节的扇区；
• 修改该字节；
• 把整个扇区写回到磁盘

磁盘的访问是以扇区作为最小的寻址和存取单位，在访问一个磁盘扇区时，所需的时间主要有：

• 柱面定位时间：磁头在磁头臂牵引下，移动到指定柱面的机械运动时间；
• 旋转延迟时间：等待指定的扇区旋转到磁头的正下方所需的机械运动时间；它与磁盘转速有关，如：软盘转速可为600rpm(每分钟转速)，硬盘可为7,200rpm至10,000rpm；
• 数据传送时间：从指定扇区读写数据的时间。

提高磁盘访问速度

• 合理地组织磁盘数据的存储位置
• 磁盘调度
  • 减少平均的柱面定位时间将有效地改进系统的输入输出性能
  • 来自不同进程的磁盘访问请求构成一个随机分布的请求队列。磁盘调度的基本思路就是通过对这些I/O请求的执行顺序进行调整，来减少整个请求队列所对应的平均柱面定位时间
  • 磁盘调度算法：先来先服务、最短定位时间优先、电梯算法等。

磁盘格式化

• 低级格式化
  • 标出磁道和扇区，在相邻的扇区之间有狭窄的间隙隔开。一个扇区的格式是：相位编码（preamble）＋数据区＋纠错码（ECC）
    • 相位编码：以某个特定的位组合模式开始，向硬件表明这是一个新扇区的开始。还包括柱面号、扇区号、扇区大小等类似信息；
    • 数据区：由格式化程序确定其大小，一般512；
    • 纠错码：包含冗余信息，用来纠正读取错误
• 分区
  • 用分区软件把整个硬盘划分为若干个逻辑分区，每个分区可视为一个独立的磁盘。在多数计算机上，用第0个扇区来存放一些系统启动代码和一个分区表，记录了每个分区的起始扇区和大小
• 高级格式化
  • 对每一个逻辑分区，分别进行一种高级格式化（即通常的格式化操作），生成一个引导块、空闲存储管理结构、根目录和一个空白的文件系统。对不同的分区，可以使用不同的文件系统，如FAT16、FAT32、NTFS等

SSD硬盘

闪存

闪速存储器（Flash Memory）

• 可读/可写
• 基本单元电路（存储细胞）为双层浮空栅MOS管，带电表示存入0，不带电表示存入1
• 速度快，无机械装置，无需柱面定位和旋转延迟，可用电气的方法快速地擦写
• 非易失型，在断电后不丢失信息
• 经久耐用（压力、温度、水），在嵌入式设备中得到广泛应用

NOR Flash

• 设计目标：替代原来的ROM，可方便地进行重写。用于存储不经常更新的程序代码。
• 读操作：提供完全的地址和数据总线，可以随机地访问任何存储单元，类似于RAM。处理器可以直接执行上面的程序。
• 写操作：随机写，但只能从1到0。
• 擦除操作：必须以块为单位，通常的块大小为64、128或256KB。最大擦写次数可达100万次。

NAND flash

• 设计目标：缩小芯片面积，实现大容量的Flash Memory，以匹敌磁介质存储设备，如硬盘。
• 写操作能力增强，与NOR相比，有较快的擦除和写入速度。体积小，存储密度大，成本低。
• I/O接口不提供随机访问的外部地址总线，所有操作（读、擦除和写）都必须以块为单位。
• 不适合取代原来的ROM，因为微处理器不能直接执行存储在它上面的代码。
• 在访问方式和容量上类似于硬盘这样的块设备。

在一个嵌入式系统（如数码相机或摄像机）中，可能会用到哪些不同类型的存储器

• 存放BootLoader的存储器，必须随机访问，其内容主要是代码，一般不会修改。非易失型。
  • 可用ROM或NOR Flash实现。
• 内存。程序必须装入内存执行。要求可读写、随机访问，速度要快。
  • 可用DRAM实现。
• 系统的固件放哪？可读可写，不需要随机访问，容量要大。
  • 可用NAND Flash实现。
• 用户产生的数据文件放哪？
  • NAND Flash。

页（page）：一页有若干个KB，如4KB

块（block）：一块由若干个页组成

读取一页

• 读取某一页的全部内容
• 时间开销：10—20微秒
• 所需时间与页号和之前的访问请求无关
• 硬盘：柱面定位4-15毫秒、旋转延迟2-6毫秒、数据读取1.4微秒

写一页

• 写操作只能将数据位从1写成0，不能从0写成1（1111->1110)，故在重新写入前先要执行擦除操作，初始为1
• 擦除操作最小单位是块，且次数有限
• 时间开销：擦~1-2ms，写20-200μs

SSD硬盘

• SSD（Solid-State Drive）：固态硬盘，一种固态存储设备，使用集成电路部件来永久地存储数据，外部接口与传统硬盘相同
• SSD的存储介质主要是NAND flash，早期也有用DRAM的
• 优点：可靠、无噪声、读速快（总是快）
• 缺点：价格贵、写速慢、擦除次数有限

• SSD硬盘不需要碎片整理，SSD硬盘不需要机械寻址。
• 要尽量减少SSD硬盘的擦写次数
• SSD硬盘存放常用、速度慢及以读为主的内容，而不常用、速度快及频繁删除的内容尽量存放在机械硬盘上

文件系统

一个简单的文件系统

可以从两种不同的观点来看待文件系统：

• 用户观点：关心的是文件系统所提供的对外的用户接口，包括文件如何命名、如何保护、如何访问（创建、打开、关闭、读、写等）；
• 操作系统观点：关心的是如何来实现与文件有关的各个功能模块，包括如何来管理存储空间、文件系统的布局、文件的存储位置等。

文件

文件是一种抽象机制。可以视为一个单独的连续的逻辑地址空间，其大小即为文件的大小，与进程的地址空间无关。

命名

文件名.扩展名

结构

指文件的逻辑结构，即文件系统提供给用户的文件结构形式，它独立于在外存上的物理存储结构。

无结构：整个文件由一序列无结构的字节流组成；

文件的访问方式

随机存取：根据所需访问的字节或记录在文件中的位置，将文件的读写指针直接移至该位置，然后进行存取。每一次存取操作都要指定该操作的起始位置。现代OS都提供随机存取的方式。

分类

• 普通文件（regular file）：包含用户信息的文件；
  • ASCII文件：由一行行的文本组成；
  • 二进制文件：非ASCII文件，通常具有某种内部的逻辑结构，为相关的应用程序所了解。
• 目录文件（directory）：管理文件系统结构的系统文件。

属性

• 每个文件都有一个名字和它所保存的信息，此外，OS还给每个文件附加了一些其他的信息，这些信息称为文件的属性。
• 常见的一些文件属性：
  • 保护信息：谁可以对该文件进行何种操作；
  • 创建者：该文件是谁创建的；
  • 只读标志位：0表示可读/写，1表示只读；
  • 隐藏标志位：0表示普通文件，1表示隐藏文件；
  • 系统标志位：0表示普通文件，1表示系统文件；
  • 创建时间、最后访问时间、最后修改时间；
  • 文件长度。

控制

文件控制指围绕文件属性的控制所进行的文件操作。

• 创建create：创建一个空白的文件；
• 删除delete：删除一个文件，释放磁盘空间；
• 获取文件属性get attributes：读取文件的属性信息;
• 设置文件属性set attributes：设置文件的属性信息；
• 修改文件名rename：改变文件的文件名。

访问

文件访问指围绕文件内容的读写所进行的文件操作。

• 打开open：在访问一个文件前，必须先打开它；
• 关闭close：在使用完一个文件后，要关闭该文件；
• 读read：从文件中读取数据；
• 写write：把数据写入文件；
• 添加append：添加数据到文件的末尾；
• 定位seek：指定文件访问的当前位置。

目录

• 目录（directory）也称文件夹（folder），它是一张表格，记录了在该目录下的每一个文件的文件名和其他的一些管理信息。
• 一般情况下，每个文件占用该表格的某一行，即一个目录项；
• 这张表格本身是以文件的形式存放在磁盘上；
• 在目录的管理上，也有相关的系统调用，如：
  • 创建目录create；
  • 删除目录delete；
  • 修改目录名rename；

多级目录结构

文件系统的实现

• 文件的逻辑结构一般是字节流；
• 对于用户而言，可以在这种字节流的基础上，构造自己所需的各种类型的数据结构，如：记录结构、树状结构、线性结构等；
• 对于文件系统而言，必须将这种字节流（一个连续的逻辑地址空间）保存在磁盘的某些扇区中；
• 通常做法：把磁盘空间划分为一个个大小相同的块（block），称为物理块；把该逻辑地址空间也分成大小相同的逻辑块，在文件系统的内部，以块为单位来进行操作；
• 一个物理块由一个或多个连续的扇区组成。

文件系统的布局

• 一个磁盘在低级格式化以后，可以用分区软件划分为若干个分区。在分区以后，磁盘的扇区0称为主引导记录（Master Boot Record, MBR），用来启动计算机，MBR的结尾是一个分区表，记录了每个分区的起始扇区和大小，其中有一个分区为活动分区；
• 在不同的分区中，可以使用不同的文件系统，每一种文件系统在分区中的布局可能各不相同。

文件的实现

文件控制块

• 文件控制块（File Control Block，FCB）：是操作系统为了管理文件而设置的数据结构，存放了文件的所有管理信息。是文件存在的标志；

• 文件控制块的内容一般包括：

  • 文件的类型、长度；
  • 文件的所有者、文件的访问权限；
  • 文件的创建时间、最后访问时间、最后修改时间；
  • 文件所在的物理块信息；

• 在Linux中，称为I结点（inode，索引结点）。

文件的物理结构

文件在物理介质上的存放方式。

具体而言，以块为单位，研究如何把文件的一个个连续的逻辑块存放在不同的物理块当中，即研究逻辑块与物理块之间的映射关系（类似于页式存储管理方案）

连续结构

连续结构（顺序结构）：把文件的各个逻辑块按照顺序存放在若干个连续的物理块当中。

• 优点：
  • 简单，容易实现从逻辑块到物理块的映射关系，设起始的物理块号为S，则第n个逻辑块的地址为S+n
  • 对于机械硬盘，由于物理块是顺序存放的，所以在访问文件时，只需将磁头定位到第一个物理块，即可顺序地读取，因而速度很快。
• 缺点：
  • 随着磁盘文件的增加和删除，将形成已占用物理块与空闲物理块交错的情形，那些较小的、无法再利用的物理块，即成为外碎片。
  • 文件的大小不能动态的增长，对于在创建之时未知大小的文件，预留空间少了则不够用，预留多了则浪费。

在CD-ROM、DVD和其他一些一次性写入的光学存储介质中，有着广泛的应用。

链表结构

链表结构：把文件的各个逻辑块依次存放在若干个（可以）不连续的物理块当中，各块之间通过指针连接，前一个物理块指向下一个物理块。

• 缺点：
  • 只能进行顺序访问，不能进行随机访问。为了访问一个文件的第n个逻辑块，必须从文件的第一个物理块开始，按照指针所指向的地址，顺序地访问前n个块，即为了得到第n个逻辑块的物理块地址，必须先访问n-1次的硬盘，速度非常慢；
  • 每个物理块上的数据存储空间不再是2的整数次幂（指针占用了若干个字节），从而使文件的访问不太方便。

带有文件分配表的链表结构

基本思路：在链表结构的基础上，把每一个物理块当中的链表指针抽取出来，单独组成一个表格，即文件分配表（File Allocation Table, FAT），并把它放在内存当中。

• 特点：
  • 实现了链表指针与文件数据的分离，整个物理块都可以用来存放数据；
  • FAT表放在内存当中，因此，若要随机地访问文件的第n个逻辑块，可以先从FAT表中查到相应的物理块编号（地址），然后再去访问外存，这样只需访问一次外存，速度快。
• 缺点：
  • 需要把整个FAT表保存在内存中，会占用较大的内存空间。例如，假设硬盘20GB，块大小为1KB，表项长度4个字节，则整个FAT表大小为80MB
  • FAT文件系统仍然在使用中，如U盘、SD卡等

整个硬盘共用一张FAT表

索引结构

索引结构：类似于普通页表，把文件的每一个逻辑块所对应的物理块编号直接记录在FCB中，称为I结点（inode，index-node，索引结点）。

• 特点：
  • 每一个文件都有一个索引结点；
  • 直接实现逻辑块与物理块的映射；
  • 只需把那些正被使用的文件的索引结点装入内存即可，不必象FAT表那样须全部装入。

UFS-Unix File System

12 direct blocks

直接索引 48k

一级索引 4M

二级索引 4G

三级索引 4T

目录的实现

目录的主要功能：根据用户给出的ASCII形式的文件名（路径名），迅速地定位到相应的文件控制块。

不同的系统采用不同的实现方法，一般分为两类：

• 直接法：目录项＝文件名＋FCB（属性信息、在外存上的存放位置）
• 间接法：目录项＝文件名＋FCB地址（索引号）

不管是何种方法，给定一个文件名，即可返回相应的FCB。

文件属性的访问

访问目录项

• 创建文件
• 修改文件属性
• 删除文件
• 修改文件名
• 移动文件

文件内容的访问

打开文件

在读写一个文件之前，先要打开该文件

1	int open(char *filename, int flags) //返回fd

flags是一个位向量:

• Access modes (Rd, Wr, …)
• Open Flags (Create, …)
• Operating modes (Appends, …)

作用

• 利用目录结构进行文件名解析，将文件名（路径名）翻译为一个整数fd
• 在进程PCB中的“打开文件表”中增加一项，返回其下标fd
• 在硬盘找到该文件的FCB并读入内存，通过fd可访问该FCB，进而定位各物理块
• 其它工作，如检查文件访问的合法性

目录检索

解析路径名”/Ann/mail/B”的执行过程

• 读入根结点的FCB（位于硬盘固定区域）
• 读入根目录的第1个数据块
• 该数据块即为根目录的开始部分的内容，在其中搜索Ann子目录
• 读入”Ann”目录文件的FCB
• 读入”Ann”目录文件的第1个数据块，并在其中搜索”mail”子目录
• 读入”mail”目录文件的FCB
• 读入”mail”目录文件的第1个数据块，并在其中搜索”B”
• 读入”B”目录文件的FCB

读取文件

在打开一个文件后，即可对该文件进行读写，典型的读写操作是：读写该文件从某个位置开始的若干个字节。

1 2	lseek(fd, 100, SEEK_SET); read(fd，buffer，10);

其他

其他的一些系统调用：

• 创建文件create；
• 写文件write；
• 添加append；
• 文件定位seek；
  ……