博客原文：计算机操作系统重点 – 全栈之路 (jason-xy.cn)

知乎原文：计算机操作系统复习整理 - 知乎 (zhihu.com)

第一章 绪论（考概念）

什么是OS？

• 操作系统是一组控制和管理计算机软硬件资源、合理地对各类作业进行调度以及方便用户使用的程序集合。

• 操作系统是位于硬件层(HAL)之上，所有其它系统软件层之下的一个系统软件，使得管理系统中的各种软件和硬件资源得以充分利用，方便用户使用计算机系统。
• 

操作系统的目标

方便性：

• 计算机只能识别0、1
• 用户熟悉的是各种语言
• 命令和图形界面

有效性：

• 长期是最重要的目标
• 提高系统资源利用率
• 提高系统吞吐量

可扩充性：

• 便于修改和增加功能（如何设计？）

开放性：

• 系统能支持世界标准规范

批处理、分时、实时系统比较

批处理系统

单道批处理系统

• 名称由来：内存中始终仅存一道作业运行；
• 主要特征：自动性、顺序性、单道性；
• 主要优点：减少人工操作，解决了作业的自动接续；
• 主要缺点：平均周转时间长，没有交互能力。

多道批处理系统

• 定义：在内存中存放多道作业运行，运行结束或出错，自动调度内存中的另一道作业运行；
• 好处：
  • 提高CPU的利用率；
  • 提高内存和I/O设备利用率；
  • 增加系统吞吐率；
• 特征：多道性、无序性、调度性；
• 主要优点：提高了资源利用率和吞吐能力；
• 主要缺点：平均周转时间长，没有交互能力。

分时系统

• 产生：人机交互、共享主机、便于用户上机
• 关键问题：及时接收、及时处理
• 特点：多路性、独立性、及时性、交互性

实时系统

• 定义：是计算机及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致的运行。
• 举例：工业控制、军事控制、医疗控制、航班订票、联机情报检索
• 分类：周期性非周期性、软硬实时任务
• 特征：多路性、独立性、交互性、可靠性、及时性

OS 的作用

• 作为用户与计算机硬件系统之间的接口
• 作为计算机系统资源的管理者
• 用作扩充机器

OS 的四个基本特性⭐

• 并发性（最重要的特性）

  并行是指两或多个事件在同一时刻发生
  并发是两或多个事件在同一时间间隔内发生

• 共享性

  系统中资源可供内存中多个并发执行的进程共同使用
  **互斥共享：**一段时间只允许一个进程访问该资源
  **同时访问：**微观上仍是互斥的
  并发和共享是操作系统的两个最基本的特征，它们又是互为存在的条件

• 虚拟性

  **时分复用：**虚拟处理机技术， 虚拟设备技术
  **空分复用：**虚拟存储
  通过某种技术把一个物理实体变为若干个逻辑上的对应物。若n是某一物理设备所对应的虚拟的逻辑设备数，则虚拟设备的速度必然是物理设备速度的1/n。

• 异步性

  停停走走
  运行进度不可预知

OS 的五大功能⭐

• 处理机管理（CPU）
• 存储器管理
• 设备管理
• 文件管理
• 方便用户使用的用户接口。

OS 的基本类型（了解即可）

• 批处理系统
• 分时系统
• 实时系统

第二章 进程管理

进程和线程的概念、比较

进程

• 进程是程序的一次执行
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

线程

轻型进程

比较

• 调度的基本单位

  在引入线程的OS 中，已把线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位。当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程。

• 并发性

  在引入线程的OS 中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，甚至还允许在一个进程中的所有线程都能并发执行。同样，不同进程中的线程也能并发执行。

• 拥有资源

  线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源。

  属于同一进程的所有线程都具有相同的地址空间。

• 独立性

  在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。

• 系统开销

  在一些OS 中，线程的切换、同步和通信都无需操作系统内核的干预。

• 支持多处理机系统

  对于多线程进程，就可以将一个进程中的多个线程分配到多个处理机上，使它们并行执行，这无疑将加速进程的完成。

进程的基本状态及状态转换的原因

三种状态

就绪状态

当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。（万事俱备，只欠CPU）

执行状态

进程已获得CPU，其程序正在执行。（获得CPU）

阻塞状态

正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。（无法继续执行，放弃处理机处于暂停状态）

状态转换原因

PCB 的作用

• 是进程存在的唯一标志
• PCB (Process Control Block) 常驻内存

PCB 内的信息

• 进程标识符
• 处理机状态
• 进程调度信息
• 进程控制信息

进程控制的原语操作

Create()

1. 申请空白 PCB
2. 为新进程分配资源
3. 初始化进程控制块
   1. 初始化标识信息
   2. 初始化处理机状态信息
   3. 初始化处理机控制信息
4. 将新进程插入就绪队列

终止

1. 根据进程ID，检索进程PCB，读取进程信息
2. 若被终止进程处于执行状态，则立即终止进程，并置调度指示符为真，用于指示该进程被终止后重新进行调度
3. 终止子孙进程
4. 归还资源
5. 移出已终止进程

block()

1. 进程通过调用阻塞原语 block() 阻塞自己
2. 更改进程状态，并插入阻塞队列
3. 处理机重新调度，分配给另一就绪进程

wakeup()

1. 将进程移出阻塞队列，并更改PCB中现行状态
2. 将PCB插入就绪队列

suspend()

1. 首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪
2. 对于活动阻塞状态的进程，则将之改为静止阻塞状态

active()

1. 将进程从外存调入内存，检查该进程的现行状态
2. 若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞

进程切换

1. 保存进程上下文环境
2. 更新当前运行进程的控制块内容，将其状态改为就绪或阻塞状态
3. 将进程控制块移到相应队列
4. 改变需投入运行进程的控制块内容，将其状态变为运行状态
5. 恢复需投入运行进程的上下文环境

进程互斥、临界区、进程同步的基本概念、同步准则

概念

进程互斥

任何时刻，只允许一个进程进入临界区，以此实现进程对临界资源的互斥访问。

临界区

访问临界资源的那段代码称为临界区。

进程同步

使并发执行的主进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

同步准则

• 空闲让进
• 忙则等待
• 有限等待
• 让权等待

信号量机制

信号量（Semaphores）机制:是一种卓有成效的进程同步工具

• 整型信号量
• 记录型信号量
• ​ AND 型信号量
• 信号量集

信号量应用实现

• 利用信号量实现进程互斥
• 利用信号量实现前趋关系

经典进程同步问题⭐

生产者消费者问题

• 互斥信号量mutex：实现诸进程对缓冲池的互斥使用
• 资源信号量empty：表示缓冲池中空缓冲区的数量
• 资源信号量full：表示满缓冲区的数量
• 只要缓冲池未满，生产者便可将消息送入缓冲池
• 只要缓冲池未空，消费者便可从缓冲池中取走一个消息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int in=0,  out=0;
item buffer[n];
semapthore mutex=1, empty=n, full=0;
void proceducer() {
      do{
            producer an item nextp;
            …….
            wait(empty);
            wait(mutex);
            buffer[in]=nextp;
            in=(in+1) %n;
            signal(mutex);
            signal(full);
       } while(TRUE);
}

void consumer() {
      do{
            wait(full);
            wait(mutex);
            nextc=buffer[out];
            out=(out+1) %n;
            signal(mutex);
            signal(empty);
            consumer the item in nextc;
            ………
       } while(TRUE);
}

哲学家进餐问题

特殊情况：死锁 。
解决办法：
至多只允许四位哲学家同时去哪左边的筷子。
仅当哲学家的左、右两只筷子同时可以时才允许他拿起筷子。
规定奇数号哲学家先拿他左边的筷子，然后再拿右边的；而偶数号哲学家则相反。

• 记录型信号量

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

semaphore  chopstick［5］ =[1，1，1，1，1];

do{
    wait(chopstick[i]);
    wait(chopstick[(i+1) %5]);
    …
   //eat
    …
   signal(chopstick[i]);
   signal(chopstick[(i+1) % 5]);
    …
   //think;
    …
} while (TRUE)

• AND 型信号量

1
2
3
4
5
6
7
8
9

Var chopstick: array[0, …, 4] of semaphore:=(1,1,1,1,1);
processi
Repeat
   think;
   Sswait(chopstick[(i+1)mod 5],chopstick[i]);
   eat
   Ssignal(chopstick[(i+1)mod 5],chopstick[i]);
Until false

读者写者问题

• 信号量集

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

int RN;
semaphore L=RN, mx=1;
void Reader(){
    do{
           Swait(L, 1, 1);
           Swait(mx, 1, 0);
           …….
           perform read operation;
            ……
            Ssignal(L, 1)
     }while (TRUE);
}

void Writer(){
      do{
           Swait(mx, 1,1; L, RN, 0);

           perform write operation;

           Ssignal(mx, 1);
      } while(TRUE);
}

进程间通信的原理和实现方法

原理

进程之间的信息交换

• 共享存储器系统
• 消息传递系统
• 管道（Pipe）通信

实现方法

• 直接通信方式
  • Send(Receiver，message);
  • Receive(Sender，message);
• 间接通信方式
  • Send(mailbox, message);
  • Receive(mailbox, message);

第三章 处理机调度

调度的层次

调度算法的准则

不同的设计需求决定了不同的目标：

共同目标：

• 资源利用率
• 公平性
• 平衡性
• 策略强制执行

周转时间

• 作业在外存的等待时间
• 进程在就绪队列的等待时间
• 进程占用CPU的时间
• 进程阻塞时间

带权周转时间

响应时间

调度算法⭐

先来先服务

周转时间

• 作业在外存的等待时间
• 进程在就绪队列的等待时间
• 进程占用CPU的时间
• 进程阻塞时间

**缺陷：**对待短作业（进程）不公平，如果他们排在队列后面，则其等待时间远大于其执行时间。

时间片轮转

原理：

• FCFS策略+时钟中断+时间片原则

进程切换时机：

• 时间片内进程结束，进程结束事件激活进程调度，新进程可运行一个时间片。
• 时间片用完，时钟中断激活调度，旧进程到就绪队列尾，队头进程投入运行一个时间片。

时间片大小的确定：

• 太小：利于短作业，但增大调度和上下文切换频率，增大系统开销。

• 太长：退化为FCFS算法。

• 合适：略大于一次典型的交互所需的时间，使大多数交互式进程能在一个时间片内完成。

  

基于优先权

赋予作业动态优先级，优先级随作业等待时间延长而增加，从而使长作业的优先级在等待期间不断增加。

高响应比优先

等待时间+要求服务时间=响应时间
故优先级相当于响应比Rp。

• 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。
• 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
• 对于长作业，作业的优先级可以随等待时间的增加而提高， 从而也可获得处理机。
• 简言之，该算法既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。

多级反馈队列

长短不同作业的矛盾。

调度机制

• 设置多个就绪队列，并为各个队列赋予不同的优先级。
• 优先级愈高的队列的进程的执行时间片就愈小。
• 新进程首先进入最高优先级的队列。每个队列采用FCFS算法。队列中的进程运行一个时间片后未结束则降级排到下一个队列的末尾。最低优先权队列中的进程则按RR方式运行。
• 按队列优先级调度。只有比队列的优先级高的队列均空时，才运行该队列中的进程。

特点：长、短作业兼顾，有较好的响应时间

（1）短作业一次完成，响应时间性能好；

（2）中型作业周转时间不长；

（3）大型作业不会长期不处理。

实时调度（了解）

实时调度算法分类

死锁

概念及原因

死锁（Deadlock），是指多个进程在运行过程中因争夺资源而造成的一种僵局（Deadly- Embrace），当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

产生死锁的原因可归结为如下两点：

（1）竞争资源。

（2）进程间推进顺序非法。

必要条件

（1）**互斥条件：**指进程对所分配到的资源进行排它性使用 。

（2）**请求和保持条件：**指进程已经保持了至少一个资源，但又提出了新的资源请求 。

（3）**不剥夺条件：**指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

（4）**环路等待条件：**指在发生死锁时，必然存在一个进程——资源的环形链 。

预防

是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。至于必要条件1，因为它是由设备的固有属性所决定的，不仅不能改变，还应加以保证。

破坏“请求和保持”条件

系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。

从而进程在整个运行期间，便不会再提出资源要求，从而摒弃了请求和保持条件，由此可以避免发生死锁。

**优点：**简单、易于实现且很安全。
**缺点：**资源被严重浪费，使进程延迟运行。

摒弃“不剥夺”条件

当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源。待以后需要时再重新申请。从而摒弃了“不剥夺”条件。

**缺点：**实现起来比较复杂且要付出很大代价。

• 一个资源在使用一段时间后，它的被迫释放可能会造成前段工作的失效。
• 会使进程前后两次运行的信息不连续。
• 因反复地申请和释放资源，致使进程执行被无限推迟，延长进程周转时间、增加系统开销、降低吞吐量 。

摒弃“环路等待”条件

这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。 所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。

存在严重问题

第一，为系统中各类资源分配的序号必须相对稳定，这就限制了新设备类型的增加；

第二，会经常发生作业使用的顺序与系统规定顺序不同的情况，造成资源浪费；

第三，增加了程序设计难度。

避免

是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

检测

通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。

解除

当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程。

安全状态

安全状态

• 所谓安全状态，是指系统能按某种进程顺序，如<P1，P2，…，Pn>，依次为n个进程分配其所需资源，直至其最大需求，使每个进程都可顺利地完成，称系统处于安全状态。
• 称〈P1，P2，…，Pn〉序列为安全序列。否则，如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

银行家问题⭐

银行家算法中的数据结构

• **可利用资源向量Available。**这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。其数值随该类资源的分配和回收而动态地改变。 Available[j]=k,表示系统中现有Rj类资源k个。
• **最大需求矩阵Max。**这是一个n × m的矩阵，它定义了n个进程中每一个进程对m类资源的最大需求。Max[i,j]=K，表示进程i需要Rj类资源的最大数目为K。
• **分配矩阵Allocation。**这是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。Allocation［i,j]=K，表示进程i当前已分得Rj类资源的数目为K。
• **需求矩阵Need。**这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。Need[i,j]=K，表示进程Pi还需要Rj类资源K个，方能完成其任务。

第四章 存储器管理

存储器结构层次

• 寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。
• 磁盘和可移动存储介质属于设备管理和文件系统的管辖范畴，它们存储的信息将被长期保存。

程序的装入

**绝对装入方式(Absolute Loading Mode) ：**编译时，已知程序在内存的具体位置，则编译程序可产生实际存储地址（绝对地址）的目标代码。

可重定位装入方式(Relocation Loading Mode)

重定位（地址映射）：

• 经编译得到的目标模块中为相对地址（通常从0开始，也称逻辑地址），即地址都是相对于0开始的。
• 装入模块中的逻辑地址与实际装入内存的物理地址不同。
• 装入内存时，相对地址（数据和指令的地址）要作出相应的修改以得到正确的物理地址，这个修改的过程称为重定位。

静态重定位：

• 地址变换是在装入内存时一次完成的，且以后不能移动。
• 一般情况下,物理地址=相对地址+内存中的起始地址。
• 适用于多道程序环境，可以将装入模块装入到内存中任何允许的位置。
• 优点：不需硬件支持，可以装入有限多道程序。
• 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享。

动态运行时装入方式(Denamle Run-time Loading)

• 装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行。在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为动态重定位。
• 最简单的办法是利用一个重定位寄存器(RR)。该寄存器的值是由进程调度程序根据作业分配到的存储空间起始地址来设定的。
• 在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据CPU给出的有效地址去访问主存，而是将有效地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。

访问地址时才确定物理地址，因此采用动态重定位技术后，可在运行中动态分配或者释放存储空间。

主要优点：

• 主存的使用更加灵活有效。非连续分配和部分装入。
• 几个作业共享一程序段的单个副本比较容易。
• 有可能向用户提供一个比主存的存储空间大得多的地址空间。因而无需用户来考虑覆盖结构，而由系统来负责全部的存储管理。

主要缺点：

• 需要附加硬件支持。
• 实现存储器管理的软件比较复杂。

程序的链接

静态链接： (Static Linking)

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。

存在问题：

• 不便于对目标模块的修改和更新（若要更新其中一个模块，需要打开装入模块）。
• 无法实现对目标模块的共享。

装入时动态链接

用户源程序是主目标模块，装入内存时再链接需要的其他模块。即在装入目标模块时，若发现一个外部模块调用，则由装入程序找出相应的外部目标模块，并将其装入内存。

优点：

• 便于软件版本的修改和更新。只需修改各个目标模块，不必将装入模块拆开，非常方便。
• 便于实现目标模块共享。即可以将一个目标模块链接到几个应用模块中，从而实现多个应用程序对该模块的共享。

缺点：

• 进程（程序）在整个执行期间，装入模块是不改变的。
• 每次运行时的装入所有涉及的模块，但许多模块并不是每次运行都需要的，占用内存。

运行时动态链接

采用运行时动态链接可将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由操作系统去找到该模块，将它装入内存，并链接到调用模块上。

优点：

• 凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
• 运行时动态链接是目前最常使用的链接方式。

连续分配方式

连续分配方式，是指为一个用户程序分配一个连续的内存空间。

单一连续分配

• 系统区
• 用户区
• 存贮保护
  • 一般不设置保护也可，因单任务。

分区式分配

固定分区

特点：有n个分区，则可同时装入n个作业/任务。

一、分区大小：

​ 相等:

​ 不相等：不相等利用率更高。

二、内存分配：

数据结构

​ 将分区按大小排序，并将其地址、分配标识作记录

例：dos的MCB

三、特点：

简单，有碎片（内零头）

可变式分区（比固定式分区有改善）

一、数据结构

​ 1．空闲分区表

​ 2．空闲分区链

二、顺序分配算法

要求：空闲分区按照地址或者大小组织为链表。

1．首次适应算法FF。

方法：每次链首开始，直到找到满足大小的空闲分区，分割该分区。

特点：有外零头，低址内存使用频繁，查找慢。高地址区保留大分区。

2．循环首次适应算法。

方法：从上次找到的空闲分区的下一个开始查找，直到找到满足大小的空闲分区，分割该分区。

特点：空闲分区分布均匀，提高了查找速度；缺乏大的空闲分区。

3．最佳适应算法

要求：分区按大小递增排序；分区释放时需插入到适当位置。

方法：从小分区开始，找大小满足要求，但空余最小的分区。

特点：单次分配看似最优，但存在许多难以利用的碎片。总体未必最优。

4．最坏适应算法

方法：总是选择最大的分区来分割分配。

特点: 缺乏大的空闲分区。对中小作业有利。查找效率高。

三、分区分配

1．分配：

2．回收：

（1）上邻空闲区：合并，改大小。

（2）下邻空闲区：合并，改大小，首址。

（3）上、下邻空闲区：合并，改大小。

（4）不邻接，则建立一新表项。

可重定位分区分配

动态重定位的引入

• 内零头：分配给作业但作业并不需要的部分。
• 外零头：太小无法分配给任何作业的块。
• 连续式分配中，总量大于作业大小的多个小分区不能容纳作业。
• 紧凑
  • 通过作业移动将原来分散的小分区拼接成一个大分区。
  • 作业的移动需重定位。是动态（因作业已经装入）

动态重定位实现

动态分区分配算法

离散分配方式

离散分配方式的引入

• 连续分配方式会产生内/外零头
• 为解决零头问题又要进行紧凑等高开销活动

什么是离散分配

• 程序在内存中不一定连续存放

根据离散时的基本单位不同，可分为三种：

• 分页存储管理
• 分段存储管理
• 段页式存储管理

分页存储管理

页面和物理块

• 将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。
• 相应地，也把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框。
• 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
• 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。

注：

• 系统一旦启动，则页和页框大小固定不变，且两者相等。
• 从0开始编制页号，页内地址是相对于0编址。
• 在进程调度时，必须把它的所有页一次装入到主存的页框内；如果当时页框数不足，则该进程必须等待，系统再调度另外的进程。（纯分页方式）

实现分页存储管理的数据结构

1. **页表：**每个进程对应 1 个页表，描述该进程的各页面在内存中对应的物理块号。

• 页表中包括页号、物理块号（还可有存取控制字段，对存储块中的内容进行保护）。
• 注意：全部页表集中存放在主存的系统专用区中，只有系统有权访问页表，保证安全。

2. 作业表：整个系统1张，记录作业的页表情况，包含进程号、页表长度、页表始址等信息。

3. **空闲块表：**整个系统1张，记录主存当前空闲块。

地址变换机构

快表

• 分页系统：处理机每次存取指令或数据至少需要访问两次物理内存： 第一次访问页表，第二次存取指令或数据

• 为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、TLB(Translation Lookaside Buffer)，或联想存储器（Associative Memory）

内存的有效访问时间

有快表时：命中率，指使用快表并在其中成功找到所需页面的表项的概率。

EAT = a x λ + ( t + λ )(1-a) + t = 2t + λ – t x a

λ为查找快表所需的时间，a为命中率，t表示一次内存访问需要的时间。

两级或多级页表

对分页存储管理的评价

• 彻底消除了外零头,仅存在很少的内零头, 提高了内存利用率。
• 分页操作由系统自动进行,一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。
• 采用分页技术不易于实现存储共享，也不便于程序的动态链接。

分段存储管理方式

• 作业地址空间按逻辑信息的完整性被划分为若干个段。
• 每段有段名（或段号），每段从0开始编址。
• 段内的地址空间是连续的。
• 许多编译程序支持分段方式，自动根据源程序的情况产生若干个段。

段表

• 为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。
• 应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。
• 通常将段表放在内存中，执行中的进程可通过查找段表找到每个段所对应的内存区。
• 作用：实现从逻辑段到物理内存区的映射。

地址变换机构

信息共享

可重入代码（Reentrant Code, 纯代码）

是一种允许多个进程同时访问的代码（可共享），且是一种不允许任何进程对其进行修改的代码。

分页共享

分段共享

段页式存储管理方式

先将用户程序分段，每段内再划分成若干页，每段有段名（段号），每段内部的页有一连续的页号。

逻辑地址结构

地址变换机构

• 首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。
• 然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
• 再根据逻辑地址中指定的页号检索该页表，找到对应页所在的物理块号。
• 最后，用物理块号加上逻辑地址中指定的页内偏移量，形成物理地址。

在段页式存储管理方式中，每访问一次数据，需访问三次内存。

• 第一次访问内存中的段表
• 第二次访问内存中的页表
• 第三次访问相应数据。

解决方法：

可以设置快表，表项应包括段号、页号、物理块号。

虚拟存储管理

常规存储管理方式的特征

“一次性”: 要求将一个作业全部装入内存才能运行。

1）大作业无法运行。

2）限制作业并发执行的程度。

“驻留性”: 作业装入后一直驻留内存直到作业完成。

内存中存在一些已无用的、或暂时不用的程序或数据，浪费内存空间。

内存扩充方法

局部性原理

时间局限性

• 如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。
• 产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。

空间局限性

• 一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。
• 程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

实现虚拟存储的一般过程

虚拟存储器的特征

1．多次性

​ 多次性是指一个作业被分成多次调入内存运行。

2．对换性

​ 对换性是指作业的运行过程中进行换进、换出，换进和换出能有效地提高内存利用率。

3．虚拟性

虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟存储管理的实现方法

请求分页存储管理方式

这是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。

允许只装入部分页面的程序（及数据），便启动运行。

以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。

置换时以页面为单位。

硬件支持：

①请求分页的页表机制上增加若干项，作为请求分页的数据结构。

②缺页中断机构:当要访问的页面尚未调入内存时，便产生缺页中断，请求调页。

③地址变换机构：虚地址到物理地址转换。

软件支持：

①实现请求调页的软件

②实现页面置换的软件

请求分段系统

它允许只装入若干段的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能，将暂不运行的段调出，同时调入即将运行的段。

为了实现请求分段，系统同样需要必要的硬件支持。一般需要下列支持：

（1）请求分段的段表机制，这是在纯分段的段表机制基础上增加若干项而形成的。

（2）缺段中断机构

（3）地址变换机构。

实现请求调段和段的置换功能也须得到相应的软件支持。

段页式虚拟存储系统

许多虚拟存储管理系统是建立在段页式系统的基础上的，通过增加了请求调页、页面置换两大功能所形成的段页式虚拟存储系统。

请求分页存储管理方式

页表机制

**状态位：**也称存在位，标志该页是否驻留内存。

**访问位：**记录一段时间内该页被访问的情况，如一段时间内该页被访问的次数或者多长时间未被访问。

**修改位：**标记该页是否被修改过。注：为减少置换开销，通常选择未被修改过的页面置换。

**外存地址：**用于记录该页在外存上的存储地址。

缺页中断机构

• 在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。
• 地址转换时，检查页面的页表项中的存在位，如果为0，则产生一个缺页中断。

缺页中断处理过程

（1）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；

（2）操作系统通知处理机从外存读取指定的页面；

（3）处理机激活I/O设备；

（4） 检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；

（5） 利用页面置换算法，选择内存中的某个页面，换出内存；

（6） 将指定页面从外存装入内存；

（7） 更新该进程的页表；

（8） 更新快表；

（9）计算物理地址。

地址变换机构

内存分配策略和分配算法

物理块的分配策略

固定分配局部置换

• 为每个进程分配一定数目的物理块，在整个运行期间都不再改变。
• 实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。
  • 若太少，会频繁地出现缺页中断，降低了系统的吞吐量。
  • 若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。

可变分配全局置换 （常用方式）

在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一个物理块分配给该进程，并将欲调入的（缺）页装入其中。这样，凡产生缺页（中断）的进程，都将获得新的物理块；仅当空闲物理块队列中的物理块用完时， OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。

可变分配局部置换

吗为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。

在进程运行过程中统计进程的缺页率，如果缺页率高，则为其增加一定的内存页，否则适当减少其内存的页面数。

实现复杂：对进程的缺页情况的统计需要额外的开销。

物理块分配算法

平均分配算法

将系统中所有可供分配的物理块，平均分配给各个进程。

按比例分配算法

根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：

又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：

bi应该取整，它必须大于最小物理块数。

考虑优先权的分配算法

通常采取的方法是把内存中可供分配的所有物理块分成两部分：

• 一部分按比例地分配给各进程。
• 另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。

调页策略

预调页方式

可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。

处理过程：

当进程创建时，预先为进程装入多个页面。

缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。

若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率。目前预调页的成功率仅约50％。

请求调页

• 仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。
• 采用请求调页方式，一次装入请求的一个页面，磁盘I/O的启动频率较高，系统的开销较大。
• 当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。

从何处调入页面

在请求分页系统中的外存分为两部分：

• 用于存放文件的文件区
• 用于存放对换页面的对换区

（1）系统拥有足够的对换区空间

• 进程运行前需将全部有关文件从文件区拷贝到对换区。
• 这时可以全部从对换区调入所需页面，以提高调页的速度。

（2）系统缺少足够的对换区空间

• 这时凡是不会被修改的文件，都直接从文件区调入。
• 而当换出这些页面时，若未被修改则直接丢弃，以后再调入时，仍从文件区调入。
• 但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。

（3）UNIX方式

• 由于与进程有关的文件都放在文件区，应从文件区调入。
• 凡是未运行过的页面，都应从文件区调入。
• 而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。
• 允许页面共享

页面调入过程

页面置换算法

• 最佳(优)置换算法
• 先进先出（FIFO）页面置换算法
• 最近最久未使用（LRU）置换算法
• Clock置换算法
• 改进型Clock置换算法
• 其它置换算法

最佳(优)置换算法

所选择的被淘汰页面，将是以后永不使用的，或是在最长(未来)时间内不再被访问的页面。

假定系统为某进程分配了三个物理块， 并考虑有以下的页面访问序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

进程运行时， 先将7，0，1三个页面装入内存。

以后，当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。

先进先出（FIFO）页面置换算法

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰

最近最久未使用（LRU）置换算法

LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

Clock置换算法

• 当采用简单c1ock算法时，为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。
• 当某页被访问时，其访问位被置1。
• 置换程序从上次停止位置开始检查页面的访问位。
  • 如果是0，就选择该页换出。
  • 若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会。
• 由于该算法是循环地检查各页面的使用情况，故称为c1ock算法。
• 置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法NRU。

Clock算法的流程

实例

改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：

• ​ 1类（A=0，M=0：表示该页最近既未彼访问，又未被修改，是最佳淘汰页。
• ​ 2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
• ​ 3类（A=1，M=0）：最近已被访问，但未被修改：该页有可能再被访问。
• ​ 4类（A=1，M=1）：最近已被访问且被修改，该页可能再被访问。

第五章 设备管理

• 设备管理的对象：主要是I/O设备。
• 设备管理的基本任务：完成用户提出的I/O请求，提高I/O速率以及改善I/O设备的利用率。
• 设备管理的主要功能有：缓冲区管理、设备分配、设备处理、虚拟设备及实现设备独立性等。

I/O 系统的基本功能

1. 设备分配

2. 设备映射

3. 设备驱动

4. I/O缓冲区的管理

通用设备管理分层模型

设备控制器的组成

I/O 通道

I/O通道设备的引入 目的是使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。

采用通道有以下特点：

• ① DMA（直接存储器存取）方式显著地减少了CPU的干预。
• ②只需向I/O通道发送一条I/O指令，即可完成一组相关的读（或写）操作及有关控制。
• ③可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

中断简介

**中断源：**引起中断发生的事件

**中断请求：**中断源向CPU发出的请求中断处理信号

**中断响应：**CPU收到中断请求后转到相应的事件处理程序的过程

**关中断/开中断：**CPU内部的PSW的中断允许位被清除/被设置，不允许/允许CPU响应中断。用于保证某段程序执行的原子性

**中断屏蔽：**在中断请求产生后，系统有选择地封锁一部分中断而允许另一部分仍能得到响应。有些具有最高优先级的中断不允许被屏蔽

中断处理层的主要工作有：

• 进行进程上下文的切换
• 对处理中断信号源进行测试
• 读取设备状态和修改进程状态等

中断线程保护

中断处理流程

对I/O设备的控制方式

轮询的可编程I/O方式

中断的可编程I/O方式

直接存储器访问方式

DMA控制方式的特点：

①数据传输的基本单位是数据块，即在CPU与I/O设备之间，每次传送至少一个数据块；

②所传送的数据是从设备直接送入内存的，或者相反；

③仅在传送一个或多个数据块的开始和结束时，才需CPU干预，整块数据的传送是在控制器的控制下完成的。

DMA控制器的组成

DMA工作过程

I/O通道控制方式

I/O通道控制方式的引入

I/O通道方式是DMA方式的发展，它可进一步减少CPU的干预，即把对一个数据块的读（或写）为单位的干预，减少为对一组数据块的读（或写）及有关的控制和管理为单位的干预。

可实现CPU、通道和I/O设备三者的并行操作，从而更有效地提高整个系统的资源利用率。

I/O控制方式

磁盘存储管理

提高磁盘I/O速度的主要途径：

（1）选择性能好的磁盘

（2）采用好的磁盘调度算法

（3）设置磁盘高速缓存（Disk Cache）

（4）其它方法

（5）采用高度可靠、快速的容量磁盘系统–磁盘冗余阵列

数据的组织和格式

• 存储面(surface)
• 磁道(track)
• 柱面
• 扇区(sectors)

磁盘访问时间分成以下三部分：

寻道时间Ts ：

这是指把磁臂（磁头）移动到指定磁道上所经历的时间。

s：启动磁臂的时间

n：磁头移动n条磁道

m：移动每一条磁道所花费的时间

旋转延迟时间Tτ：

这是指定扇区移动到磁头下面所经历的时间。

例如：

软盘旋转速度为 300 r/min或600 r/min，这样，平均Tτ 为50～100 ms。

硬盘旋转速度为15 000 r/min，每转需时4 ms，平均旋转延迟时间Tτ为2 ms。

传输时间Tt：

这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。

Tt 的大小与每次所读/写的字节数b 和旋转速度有关:

r为磁盘每秒钟的转数；N为一条磁道上的字节数

磁盘调度算法

先来先服务FCFS

• 根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次地得到处理，不会出现某一进程的请求长期得不到满足的情况。

最短寻道时间优先SSTF

• 该算法选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，
• SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”现象。

扫描（SCAN）算法

• SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”(Starvation)现象。
• 该算法优先考虑的是磁头当前的移动方向。例如，磁头自里向外移动, 并同时自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向自外向里移动。（又常称之为电梯调度算法 ）

循环扫描（CSCAN）算法

CSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。

第六章 文件管理

文件的概念

文件是存储和管理数据的容器

若文件中的数据有格式，可能是如下的结构：

文件是指由创建者所定义的、 具有文件名的一组相关元素的集合。

在有结构的文件中，文件由若干个相关记录组成；

而无结构文件则被看成是一个字符流。

文件在文件系统中是一个基本的管理单元，这个管理单元必然有一组属性。

文件的属性

文件的属性可以包括：

(1) 文件类型

(2) 文件长度

(3) 文件的物理位置

(4) 文件的建立时间

文件系统概念

定义：操作系统中的各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。

有少数实时操作系统没有文件系统功能。

绝大多数操作系统都包含文件管理系统部分。

文件系统的功能

• 有效地管理文件的存储空间；
• 管理文件目录；
• 完成文件的读/写操作；
• 实现文件共享与保护；
• 为用户提供交互式命令接口和程序调用接口。

文件系统模型

文件操作概述

1.最基本的文件操作有：创建文件、删除文件。读文件、写文件、截断文件和设置文件的读／写位置。

2.文件的“打开”和“关闭”操作：所谓“打开”，是指系统将指名文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引）返回给用户。 利用“关闭”（close）系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上删除掉。

3．其它文件操作：对文件属性的操作，改变文件名、改变文件的拥有者，查询文件的状态等；

文件目录的管理要

如何来组织和访问大量的文件？

对目录管理的要求如下：

(1)实现“按名存取”。

(2) 提高对目录的检索速度。

(3) 文件共享。

(4) 允许文件重名。

文件控制块和索引节点

文件控制块（FCB）：用于描述和控制文件的数据结构。

文件目录：文件控制块的有序集合。

通常，一个文件目录也被看做是一个文件，称为目录文件。

文件控制块的内容

**基本信息：**文件名、文件类型等；

**地址信息：**卷（存储文件的设备）、起始地址（起始物理地址）、文件长度（以字节、字或块为单位）等。

**访问控制信息：**文件所有者、访问信息（用户名和口令等）、合法操作等；

**使用信息：**创建时间、创建者身份、当前状态、最近修改时间、最近访问时间等。　

FCB

目录结构

单级目录结构

所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项。

• 单级目录的优点是简单且能实现目录管理的基本功能——按名存取

• 存在下述一些缺点：

​ (1) 查找速度慢

​ (2) 不允许重名

​ (3) 不便于实现文件共享

两级目录结构

主文件目录MFD、用户文件目录UFD

• 一定程度解决了重名问题
• 提高了文件目录检索效率
• 简单的文件共享

**问题：**不便用户文件的逻辑分类；进一步解决重名、共享、检索效率等问题

树形结构目录

多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。

树叶是数据文件。

树的节点是目录，或称为子目录。

目录操作

**创建目录：**在用户要创建一个新文件时，只需查看在自己的UFD及其子目录中，有无与新建文件相同的文件名。若无，便可在UFD或其某个子目录中增加一个新目录项。

目录删除采用下述两种方法处理：

（1）不删除非空目录。

（2）可删除非空目录。

**改变目录：**改变工作目录

**移动目录：**将子目录或者文件移动到其他目录下。

**链接操作：**通过链接让同一个文件具有多个父目录。

**查找：**在目录中查找某个文件或者子目录。

目录查询技术

线性检索法

线性检索法又称为顺序检索法。

①在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。

②在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。

文件系统外存管理

磁盘管理的主要任务和目标是；

• 有效地利用外存空间
• 提高对文件的访问速度
• 提高磁盘系统的可靠性

目前，常见的文件磁盘块的组织方法有:

• 连续组织
• 链接组织
• 索引组织

连续组织

假设磁盘的容量是1MB，每个磁盘块的大小为512个字节

磁盘块数量：1MB/512B=2048块

编码磁盘块需要位数：2∧10 < 2048 <= 2 ∧11，因此需要11个二进制位

如果文件的长度不大于512K

长度需要10位来表示：512K/512 = 1024, 2∧10 = 1024

因此，每个文件需要在目录中额外占用21个二进制位。

空闲链表法

空闲盘区链

• 将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。

• 在每个盘区上含有用于指示下一个空闲盘区的指针和能指明本盘区大小(盘块数)的信息。

• 分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。

• 在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。

• 为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。

• 每个分区结点内容：起始盘块号、盘块数、指向下一个空闲盘区的指针。

问题

• 一段时间以后，可能会使空闲分区链表中包含太多小分区，使文件分配到的存储空间过分离散。
• 删除一个由许多离散小分区组成的文件时，将回收的小分区链接到空闲分区链表中需要很长时间。
• 若一个文件申请连续存储空间，则需要花费较长的时间查找相邻的空闲分区。
• 因此，这种空闲空间组织方法适合于非连续存储文件。

位示图

利用二进制位0、1表示存储空间中存储块的使用状态。空闲分区:0，已分配分区:1（或者相反）。

磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。

通常可用m × n 个位数来构成位示图，并使m × n等于磁盘的总块数。

位示图也可描述为一个二维数组map：

Var map: array of bit;

位示图优点

• 可以容易地找到一个或一组连续的空闲分区。
• 例如，我们需要找到4个相邻接的空闲盘块，这只需在位示图中找出4个其值连续为“0”的位即可。

位示图的其他问题

• 一个位示图需要占用的存储空间大小为：

磁盘容量（字节数）/ （8 * 数据块大小）

• 对于容量较小的磁盘，位示图占用的空间会很小。
• 但是，对于一个16GB的磁盘，若数据块大小为512字节，则位示图大小为4MB，大约需要占用8000个磁盘块的存储空间。

总结

重点：

• 文件和文件系统的概念；文件是具有符号名的信息（数据）项的集合；文件是具有符号名的记录的集合；文件是具有符号名的数据项的集合。
• 文件逻辑结构；顺序文件、索引顺序文件、索引文件、HASH文件；
• 磁盘存储分配方法；连续分配、链接分配、索引分配；
• 文件目录及文件控制块；文件存储器分区和空间管理。
• 磁盘存储管理；位示图、空闲链表、索引。

难点：

• 磁盘存储管理；

• 位示图、空闲链表、