跳转至

第一章 操作系统引论

1.1目标&作用

-----操作系统定义

是指==控制和管理==整个计算机系统的硬件和软件==资源==，并合理地组织==调度==计算机的工作和资源的分配，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

  • 是系统最基本最核心的软件，属于系统软件
  • 控制和管理整个计算机的硬件和软件资源
  • 合理的组织、调度计算机的工作与资源的分配
  • 为用户和其它软件提供方便的接口和环境

屏幕截图 2023-08-21 200923

----操作系统目标

  • 方便性
  • 有效性
  • 提高系统资源利用率

  • 提高系统的吞吐率

  • 可扩充性

  • 开放性

----操作系统作用

  • 作为用户与计算机硬件系统之间的接口

​ 用户和操作系统通信的三种方法：命令方式，系统调用方式，图标-窗口方式

  • 作为计算机系统资源的管理者

==计算机系统资源：处理机，内存，I/O设备，文件（数据和程序）== - 实现对计算机资源的抽象

​ 覆盖了软件，提供一个对硬件操作的抽象模型

----推动操作系统发展的主要动力

  • 不断提高计算机资源利用率

  • 方便用户

器件的不断更新换代

  • 计算机体系结构的不断发展

  • 不断提出新的应用需求

1.2操作系统的基本特征

采用多道程序设计技术的操作系统：==并发性，共享性，虚拟性，异步性==

并发性

屏幕截图 2023-08-27 091038

并行：指两个或多个事件在同一时刻同时发生。

并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

​ 1. 操作系统的并发性指计算机系统中在同一时间段内存在着多个运行着的程序，通过分时实现

​ 2. 针对内存中的程序分别建立一个==进程==，实现并发处理

进程：系统中资源分配的基本单位，能够独立运行；多个进程之间可以进行并发执行和交换信息

PS:线程——系统中独立运行的基本单位

共享性

资源复用/资源共享：系统中的资源可供内存中的多个并发执行的进程共同使用

主要复用方式

  • 互斥共享方式

一段时间内，只允许一个进程访问该资源（临界资源）

  • 同时访问方式

一段时间内，允许多个进程“同时访问”该资源

  • ==并发和共享的关系（互为存在条件）==

通过上述例子来看并发与共享的关系：

使用QQ发送文件A，同时使用微信发送文件B。

１、两个进程正在并发执行（并发性）

如果失去并发性，则系统中只有一个程序正在运行，则共享性失去存在的意义

２、需要共享地访问硬盘资源（共享性）

如果失去共享性，则QQ和微信不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发。

虚拟性

虚拟：指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。

  • 虚拟处理器（CPU）：通过多道程序设计技术，采用让多道程序并发执行的方法，分时来使用一个CPU，实际物理上只有一个CPU，但是用户感觉到有多个CPU

  • 虚拟存储器：从逻辑上扩充存储器容量，用户感觉到的但实际不存在的存储器

  • 虚拟设备：将一台物理设备虚拟为逻辑上的多台设备，使多个用户在同一时间段内访问同一台设备，即同时共享，用户宏观上感觉是同时的，但实际上是微观交替访问同一台设备的

虚拟技术

  • 时分复用技术：如处理器的分时共享
  • 空分复用技术：如虚拟存储器
  • 没有并发，就谈不上虚拟性

异步性

异步： 指在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

因此针对不同进程：先后；执行时间；速度；何时申请资源.......全都是不可预知的，即：不做前提假设

显然，如果失去了并发性，则系统只能串行地处理各个进程，每个进程地执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。

没有并发和共享，就谈不上虚拟和异步，因此==并发和共享是操作系统的两个最基本的特征。==

1.3操作系统的主要功能

OS的主要目的： 提高系统资源的利用率

OS的主要功能： 管理计算机系统中的资源

==处理机管理，存储器管理，设备管理，文件管理，方便的用户接口==

处理机管理：（以进程为单位）

==进程控制，进程同步，进程通信，进程调度==

进程控制
为作业创建进程，撤销（终止）已结束的进程，控制进程在运行状态中的转变
进程同步（PV）

以进货商-仓库-客户为例，要杜绝“放满”，“取空”

屏幕截图 2023-08-27 155131

方式：互斥方式（访问临界资源时），同步方式（合作完成任务的进程间）

进程通信

原因：一组相互合作的进程完成一个共同的任务时，需要交换信息

如：输入进程，计算进程，打印进程

进程调度

分类：作业调度，进程调度

  1. 作业调度：从外存调入内存

  2. 进程调度：从内存中的进程就绪队列中选一个，分配处理机（执行）

存储器管理

==内存分配，内存保护，地址映射，内存扩充==

  • 内存分配

​ 为（运行中）程序（再）分配内存空间，并提高存储器的利用率

​ 静态/动态分配方式（数组/链表）

  • 内存保护

​ 用户程序互不干扰，不允许用户程序访问操作系统的程序和数据

​ 避免空间和资源上“越界”：设立界限寄存器，存放正在执行程序的上下界

​ 屏幕截图 2023-08-27 160720

  • 地址映射

逻辑地址/相对地址——>内存中的物理地址（硬件支持下完成）

屏幕截图 2023-08-27 161303

  • 内存扩充

​ 虚拟存储技术[[]]

​ 请求调入功能（磁盘->内存），置换功能（内存->磁盘，腾出空间）

```延伸/联想 置换算法不好引发的后果：抖动<频繁地进出内存> 即将较为重要的部分“置换”出内存 虚拟存储器：外存借给内存空间——为了空间 如果内存空间借给外存——为了速度




### 设备管理

==缓冲管理，设备分配，设备处理，虚拟设备，设备独立性==

- ##### **缓冲管理**

​   **```解决CPU与I/O之间速度不匹配的问题——CPU利用率，系统吞吐量``·**

​   缓冲区机制（```由OS缓冲管理机制管理```）：单缓冲区，双缓冲区，循环缓冲区（circle）

- ##### **设备分配**

​   根据用户请求,分配I/O设备及相应的控制器和通道

- ##### **设备处理**

​   ```用于实现CPU与设备控制器之间的通信```

- ##### **设备独立性和虚拟设备**

​   1. **应用程序独立于物理设备**,使得用户编制的程序与实际使用的物理设备无关。

​       **即：**编写代码时，写明操作和需求，不写交给谁做（不涉及物理设备）

​   2.**虚拟设备：**物理设备——>能”同时“供多个进程**共享**的设备

### **文件管理**

==文件存储空间的管理，目录管理，文件的读/写管理和保护==

### 友好的用户接口

==用户接口(联机，脱机，图形)，程序接口==

### 现代操作系统的新功能

==系统安全，网络的功能和服务，支持多媒体==

---



## 1.4操作系统的发展过程

> 1.硬件不断发展
>
> 2.系统资源利用率，系统吞吐率需要提高
>
> 3.用户对人-机交互的需求

### 1. 未配置操作系统的计算机系统

- **手工操作阶段**

​       ```机器语言，输入输出——纸带```

​       缺点：用户独占全机，CPU等待人工操作，人机速度矛盾导致资源利用率极低

- **脱机输入/输出方式**

​       ```外围机控制I/O设备（而非主机直接控制）```

​       进步点：减少了CPU的空闲时间；提高了I/O速度

​       缺点：用户独占全机（人机交互性差），计算机处理能力（上升）与手工操作（低效）的矛盾

### 2. **批处理系统**

**```批处理技术：计算机系统对一批作业自动进行处理的一种技术```**

<img src="D:\My Files\笔记\笔记图片\屏幕截图 2023-08-27 090045.png" alt="屏幕截图 2023-08-27 090045" style="zoom:67%;" align="left"/>



- **批处理阶段 — 单道批处理系统**

  <img src="D:\My Files\笔记\笔记图片\屏幕截图 2023-08-21 205930.png" alt="屏幕截图 2023-08-21 205930" style="zoom:50%;" align="left"/>

​       









**==特征：自动性，顺序性，单道性==**

​     ```单道性:内存中最多只有一道程序在运行(计算时：CPU工作，外设空闲；I/O：外设工作，CPU空闲)```

​       主要优点： 缓解了一定程度的人机速度矛盾，资源利用率有所提升。

​       主要缺点： 内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU有大量的时间是在空闲等待I/O完成。资源利用率依然很低。CPU与外设串行

- **批处理阶段 — 多道批处理系统**

  每次往内存中输入多个作业，使它们共享CPU和系统中的各种资源。

  <img src="D:\My Files\笔记\笔记图片\屏幕截图 2023-08-21 210002.png" alt="屏幕截图 2023-08-21 210002" style="zoom:50%;" align="left"/>

​       












==**特征：多道性，无序性，调度性，宏观并发微观串行****==

```无
无序性：作业的完成顺序与作业进入内存的顺序无关系
调度性：1.作业调度,从后备队列进入内存     2.进程调度,分配处理机运行。

​ 主要优点： 多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源保持“忙碌”状态，系统吞吐量增大。

​ 主要缺点： 用户响应时间长，无交互功能（不利调试和修改），作业平均周转时间长(需排队处 理)

4. 分时操作系统

区别于多道批处理的多道程序并行，分时可理解为 多个用户 / 终端的并行 (针对交互性)

用户需求：人机交互，共享主机，便于用户上机

计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

多个用户共享主机中的资源

==特点：多路性，独立性，及时性，交互性、==

分时操作系统的及时性
用户的请求能在很短的时间内获得响应，很短的时间——根据人所能接受的等待时间而定

关键问题：及时接受；及时处理

​ 主要优点： 用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

​ 主要缺点： 不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务的紧急性。

5. 实时操作系统

实时：表示“及时” 实时系统能够及时的响应、处理外部事件，并控制所有的实时任务协调一致的运行

在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

==特点：多路性，独立性，及时性，可靠性==

实时操作系统的及时性
由控制对象所要求的截止时间来确定

实时任务的“截止时间”：

  • 开始截止时间：最晚开始时间
  • 完成截止时间：最晚完成时间

​ 主要优点： 能够优先响应一些紧急任务，某些紧急任务不需时间片排队。

  • 硬实时任务：必须在绝对严格的规定时间内完成处理（导弹系统）
  • 软实时任务：能接受偶尔违反时间规定（12306火车票）

6. 其他操作系统

  • 网络操作系统

工作方式：把计算机网络中的各台计算机有机的结合起来，提供统一、经济而有效的使用各台计算机的方法、实现各台计算机之间的数据互相传送

特点：有主从关系、网络中资源共亨、网络中的计算机通过协议通信

  • 分布式操作系统

工作方式︰系统中的各计算机相互协同并行完成同一任务

特征

系统中任意两台计算机通过通信方式交换信息

系统中的计算机都具有同等地位，无主从关系

每台计算机上的资源为所有用户共享

系统中的任意台计算机都可以构成一个子系统，并且还能重构

任何工作都可以分布在几台计算机上、由他们并行工作、协同完成

特点：分布性和并行性

  • 嵌入式操作系统

固话在硬件里面的系统、比如手机、路由器等

特点

完成某一项特定的功能、不具有通用性

广泛用于文字处理、电子表格、游戏中等个人计算机操作系统

常见的有Windows、Linux、Macintosh等

操作系统 优势/进步点 特点
人工操作（无操作系统） 人机矛盾，CPU和I/O设备速度不匹配
单道批处理系统 系统资源利用率，系统吞吐率提高 自动性，顺序性，单道性
多道批处理系统 系统资源利用率，系统吞吐率提高（无交互，周转慢） 无序性，多道性，调度性，宏观并行微观串行
分时操作系统 多个用户共享主机，人机交互 多路性，独立性，及时性，交互性
实时操作系统 可靠性 多路性，独立性，及时性，可靠性

第二章 进程和线程

2.1 前驱图和程序执行

描述程序顺序执行和并行——前驱图

前驱图是一个有向不循环图，记为DAG

前驱图的结点用于描述一段程序或进程，语句，有向边->则表示两个节点之间存在的前驱关系

没有前趋的结点——初始结点；没有后继的结点——终止结点

  • 顺序执行

==特点：顺序性，封闭性，可再现性==

封闭性：系统资源被“封闭”，即被运行中的程序独占
可再现性：只要顺序执行的初始条件与环境相同，程序所得结果也相同（可再现）

S1: a=x+y;
S2: b=a-5;
S3: c=b+1;

屏幕截图 2023-08-30 143902

  • 并发执行

==特点：间断性，失去封闭性，不可再现性==

牢记：并行 <=> 谁先开始不知道，谁中间停止不清楚

屏幕截图 2023-08-30 144417

注意：不能假设，不能假设，不能假设（如S1先S2后）

限制条件（√）：如S3不能先于S1,S2执行；S1和S2执行后，S3可以执行。

关于不可再现性：

任何程序在执行时都会被分为几步，几个程序并行时，如果访问了相同的资源，可能导致不同结果：

屏幕截图 2023-08-30 144748

如何解决这一问题？ ——可交叉变量仅有 读变量

屏幕截图 2023-08-30 144838

image-20231210155108044

2.2 进程的描述

进程是程序的一次执行

严格定义：进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位

QQ为一个程序，多次执行可产生多个进程：登录，个人信息，聊天

进程的组成

进程（进程实体）由程序段、数据段、PCB三部分组成。

  • 数据段：程序运行时使用、产生的运算数据。如全局变量
  • 程序段：程序代码即存放在此
  • PCB：==进程控制块 PCB是进程存在的唯一标志==，操作系统通过PCB来管理进程，因此PCB中应该包含操作系统对其进行管理所需的各种信息。

进程的特点

  • 动态性，并发性，独立性，异步性，结构性

进程的基本状态及操作

  • 就绪态，执行态，阻塞态
1)就绪(Ready)状态 
进程已获得 除处理机外的所需资源 ,等待分配处理机资源;只要分配CPU就可执行。
一个系统中多个处于就绪状态的进程排成就绪队列。
(2)执行(Running)状态
处于就绪状态的进程一旦获得了处理机,就可以运行,进程状态也就处于执行状态。
处于此状态的进程的数目小于等于CPU的数目。
(3)阻塞(Blocked)状态(“等待”或“睡眠”) 
由于进程等待某种事件(如I/O操作或进程同步),在事件发生之前无法继续执行。该事件发生前即使把处理机分配给该进程,也无法运行。如:请求I/O操作,申请缓冲空间等
通常阻塞进程也排成若干队列（比如按照等待的资源来分）

屏幕截图 2023-08-30 150144

==注： 阻塞态不能直接到执行态==

  • 火车道损坏： 执行态->阻塞态
  • 火车道修好，火车仍然要排队通过：阻塞态->就绪态
  • 创建状态，终止状态
1）新(创建)状态： 
当一个新进程刚刚建立,还未将其放入就绪队列时的状态,称为新（创建）状态。 
获得所需资源（除了处理机外），且PCB的初始化工作完成时，由创建状态——>就绪状态

2）终止状态：
当一个进程已经正常结束或异常结束,操作系统已将其从系统队列中移出,但尚未撤消,这时称为终止状态。

屏幕截图 2023-08-30 150859

  • 挂起操作，激活操作
引入挂起的原因 
(1)终端用户的请求（需要）
当终端用户在自己的程序运行期间发现有可疑问题时,希望暂时将自己的程序静止下来。
(2)父进程请求
父进程需要考查和修改子进程。
(3)操作系统的需要
如检查运行中的资源使用情况。
(4)对换的需要
缓和内存紧张,将阻塞进程换到外存上,有别于阻塞状态。
(5)负荷调节的需要
在 实时系统 中为了调整工作负荷可将不重要的进程挂起。

可见就绪态、阻塞态分为了 挂起、激活状态

屏幕截图 2023-08-30 151331

原语：挂起原语（Suspend）,激活原语（Active）

PS:注意“挂起”和“阻塞”的区别

两种就绪挂起 状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为阻塞挂起 多个队列。

  • 进程刚刚创建时，该进程处于创建状态
  • 创建态的进程获得资源后（除了处理机），进入就绪态，加入到就绪队列
  • 就绪态的进程获得处理机后，进入执行态

进程控制块

==PCB是进程存在的唯一标志==

组成：进程标识符，处理机状态，进程调度信息，进程控制信息

进程调度信息：（1）进程状态（2）进程优先级（3）进程调度所需的其他信息（4）事件（如阻塞原因）

组织方式：线性方式，链接方式，索引方式

2.3 进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能（是进程管理最基本的功能）。

如何实现进程控制？ ——用==原语==实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。

这种不可被中断的操作即原子操作。
原语采用“关中断指令”和“开中断指令”实现
显然，关/开中断指令的权限非常大，必然只允许在核心态下执行的特权指令。

阻塞原语：block
唤醒原语：wakeup //block和wakeup成对使用
挂起原语：suspend
激活原语：active

执行机状态

为了防止OS本身数据以及关键数据（PCB）收到应用程序的破坏，处理机状态分为系统态和用户态。

  • 系统态（管态,核心态） 一切指令和寄存器，存储区

​ 传统的OS在系统态运行

  • 用户态（目态）

​ 应用程序只能在用户态中运行

image-20231210163856680

进程的创建

在OS中，可以由一个进程创建另一个进程，创建进程的进程称为父进程，被创建的进程称为子进程.........从而构成进程的层次结构： 进程图是用于描述一个进程的家族关系的有向树,树中的结点表示进程，撤消父进程时必须同时撤消子进程 image-20231210164515607

什么时候创建进程（引起创建进程的事件）：只有先创建进程，才能使程序运行 （1）用户登录，合法用户在终端登录后，系统将为用户创建一个进程 （2）作业调度 （3）提供服务 （4）应用请求，由应用进程为自己创建进程,以便能并发执行,如输入、计算、输出程序。

进程创建的步骤：（1）申请空白PCB（2）为新进程分配资源（内存）（3）初始化进程控制块（填入信息）（4）将新进程插入就绪队列

一个进程被创建后，位于就绪态

进程的终止

引起进程终止的事件：（1）正常结束（2）异常结束（3）外界干预

引起正常结束的事件：通常在程序的最后安排一条Halt指令/logs off或终止的系统调用。当程序运行到Halt指令时,将产生一个中断,去通知OS本进程已经完成 引起异常结束的事件：越界错误，保护错，非法指令，特权指令错，运行超时，等待超时，算术运算错，I/O故障 外界干预的事件：操作员或操作系统干预，父进程请求，父进程终止

进程的终止过程

image-20231210165439038

进程的阻塞与唤醒

引起进程阻塞和唤醒的事件

image-20231216202209060

进程的挂起与激活

==2.4 进程同步（PV大题)==

引入：进程并行时->异步性，不可再现性，导致 不正确

如+1 -1操作（各三步）

基本概念

两种形式的制约关系

  • 间接相互制约关系(互斥)

同处于一个系统中的进程必然共享某种资源,如CPU、I/O设备等,间接相互制约即源于资源共享。如A、B共享打印机,若A申请打印时,打印机已分配给B,则A只能阻塞,等B释放后再改为就绪,又称为“互斥”。

  • 直接相互制约关系（同步）

这种制约源于进程之间的合作关系。如进程A向B提供数据,当输入缓冲空时,B不能得到数据而阻塞;反之当缓冲满时,A无法写入而阻塞,又称为“同步”。

举例说明：生产者-消费者问题（假定1-1-1）

互斥关系： 生产者和消费者不能同时访问仓库

同步关系： 生产者访问仓库空间资源放入资源后，要“告知”消费者； 消费者访问货物资源取走资源后，要“告知”生产者

临界资源

定义:在一段时间内只允许一个进程访问的资源。(又叫==独占资源==)

例如:打印机,磁带机,卡片输入机,变量,表格,数据,指针、数组等。

临界区

不论是硬件临界资源还是软件临界资源,多个进程必须互斥地对它进行访问

在每个进程中访问临界资源的那段代码称为临界区 在临界区之前执行的这段代码称为进入区(entry section)，目的是设置访问标志 在临界区后面也要加上一段代码,用于将临界区被访问的资源恢复为未被访问的标志,称为退出区(exit section)

屏幕截图 2023-08-30 163616

同步机制遵循的规则

  • 空闲让进，忙则等待，有限等待（防止死等），==让权等待==（防止忙等）

信号量机制

老师-教室/学生 访问： 1.观察教室是否上锁 2.若未上锁，进入教室给学生上课，给教室上锁 3.若上锁，则无法进入教室给学生上课 4.若到达下课时间，离开教室，将教室的锁打开 PS：观察教室是否上锁这一作业，也是由处理机执行（即若上锁时，某个老师一直观察，会消耗CPU资源->进入等待队列 ）

信号量，理解为一种数据结构即可

==总结要点==——利用信号量实现进程同步：
  • 信号量只有两种操作，赋初值和P,V操作
  • P（mutex）和V（mutex）成对出现（有时可能距离远）
  • 尽量先执行同步P，后执行异步P
  • 某些问题中，互斥问题存在，但不一定需要单独设置互斥信号量解决（有时会被同步信号量提前解决）
  • 如生产者-消费者（1-n-1）
  • 判断：考虑互斥的信号量有几种状态，分别指向可/不可执行

——整型信号量

定义整型信号量为一个用于表示资源数目的整数量S，S仅能通过以下两个原子操作（+1;-1）访问：

  • P操作: wait(S)
  • V操作: signal(S)

==问题：违反让权等待==

```P,V wait(S){ while(S<=0); //S非正数，啥也不做 S--; //S=1,门没锁，进入房间，锁上门（S=0） }//在进入区中

signal(S) { S++； //使用完毕，退出房间，把锁打开 }//在退出区中


```pascal
wait(S):while S <= 0 do
        no-op;
        S:=S-1;//先判断再减
signal(S):S:=S+1;

PS:怎么找临界区？ ——临界区代码访问了临界资源，访问=读/写

使用场景：一般不使用整形信号量，但当涉及到计数（加减）时，可以设置为整形信号量（读者-写者问题）

但是要注意，当访问这个信号量时，它同时相当于临界资源，因此要根据实际情况设置相应的互斥信号量（）

image-20231210195741900

V操作要紧挨着临界区，因此不能将两个V(S)用分支外的一个V(S)替换。（十几秒把票都打出来后才释放S，执行效率不高）

——记录信号量

增加一个进程链表指针list,用于链接所有的等待进程

typedef struct{
    int value;
    struct process_control_block *list;
    }semaphore;

```P,V wait(semaphore S){ (S).value--; if((S).value < 0) block((S).list); }

signal(semaphore S){ (S).value++; if((S).value <= 0) wakeup((S).list); }


- S >= 0时，有S个空闲的资源
- S <=  0时，有|S|个等待的进程

==**当S的初值为1时：互斥信号量**==

==当进程被block：**执行态->阻塞态**==



#### ——AND型信号量

针对死锁状态

**一个进程需要多个共享资源**才能执行任务，进程A和进程B都需要临界资源D,E,交替地执行wait操作

出现拿着资源，想要另一个资源的情况；

解决方案：==**”一次性交付“**==

SP:Swait(S1, S2, …, Sn) if S1≥1 and … and Sn≥1 then { 每个资源都可用} for i: =1 to n do Si:=Si-1; {分配所有资源} endfor else {否则,将进程放到等待资源Si的队列中} “阻塞”(去第1个Si<1的“等待Si”的阻塞队列中排队,并置它的程序计数器于SP操作的起始点)  endif

SV:Ssignal(S1, S2, …, Sn) for i: =1 to n do Si=Si+1; {释放所有资源} “唤醒”(所有“等待Si”的阻塞进程,置为“就绪”状态,移到就绪队列中) endfor; 




#### ——信号集信号量

一次一次访问太慢（N次wait(S)）——>==一次申请多个(Swait() )==

SP:Swait(S1, t1, d1, …, Sn, tn, dn) if S1≥t1 and … and Sn≥tn then for i:=1 to n do Si:=Si-di; {一次分配d个资源} endfor else “阻塞”(去第1个Si<ti的“等待Si”的阻塞队列中排队)  endif

SV:Ssignal(S1, d1, …, Sn, dn) for i:=1 to n do Si :=Si+di; {释放所有资源} “唤醒”(所有“等待Si”的阻塞进程,置为“就绪”状态,移到就绪队列中) endfor; 


<img src="D:\My Files\笔记\笔记图片\image-20230903181923523.png" alt="image-20230903181923523" style="zoom:50%;"  align="left"/>



### 信号量的应用

#### 实现互斥关系

目的：使多个进程互斥地访问某临界资源

具体实现：为该资源设置一个**互斥信号量Mutex，设其初值为1**

临界区前P，后V

<img src="D:\My Files\笔记\笔记图片\image-20230903182023750.png" alt="image-20230903182023750" style="zoom:67%;" />

```C
semaphore mutex = 1;
P1()                                     
{
    P(mutex);
    临界区；
    V(mutex);
}
P2()
{
    P(mutex);
    临界区；
    V(mutex);
}

//注：Pascal语言中的parbegin-parend意为P1和P2是并发执行的两个程序
//并发执行：谁先谁后不清楚，中间谁停谁完成不知道
//需要互斥地访问-》由信号量解决
//切记：先同步后互斥，但是取完立刻放，V()

实现前趋关系

image-20230903182647449

限制条件：

1.S2不能先于S1执行(block操作——P()) 2.S1执行后S2可以执行(S1执行完后要告知S2——V(),且是同样的信号量)

semophore a = 0;
P1()
{
    S1;  // S1无限制，随时可以开始
    V(a);//告知S2，S1已经完成(a++ -> a=1,wakeup)
}

P2()
{
    P(a)//S2不能先于S1执行(初始a=0,a-- -> a=-1,block;a=1,a-- -> a=0,执行)
    S2；
}

针对下图：==每条边对应一个信号量==

image-20230903183431516

2.5 经典进程的同步问题

——生产者-消费者问题

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据）

生产者、消费者共享一个初始为空、大小为n的缓冲区。

  • 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。（同步关系）
  • 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。（同步关系）
  • 缓冲区是临界资源，各进程必须互斥地访问。(互斥关系)

四条基本原则

关键：

  • 同步——防止放满和取空（执行操作前先P，同步信号量：仓库空间，货物）
  • 互斥（临界资源：仓库——互斥信号量）

互斥信号量：mutex——仓库

同步信号量： empty——仓库的空间；full——仓库的货物

1-1-1情况

一个生产者，一个消费者，一个缓冲区

==下面是错误的代码：(或者中间过程)==

//错误的代码，违反了第四条
semaphore mutex = 1;
semaphore empty = 1;
semaphore full = 0;//初始情况下，仓库没有货物

生产者：
    P(empty);
    P(mutex);
    放入消息到缓冲区
    V(mutex);
    V(full);

消费者：
    P(full);
    P(mutex);
    取出缓冲区的消息
    V(mutex);
    V(empty);

==正解：==

image-20230903192229132

互斥所要解决的：限制多个程序不能同时访问一个临界资源，即不能多个P执行
本题中的缓冲区大小为1，在任何时刻,最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区

1-n-1 情况


semaphore empty = n;
semaphore full = 0;

生产者：
    P(empty);

    放入；

    V(empty);

消费者：
    P(full);

    取出；

    V(empty);

==注意注意注意==：为什么不用设置互斥信号量？（思考重点）

首先要明确一点：这道题的临界资源是分区的（看成一个循环队列），里面的每个缓冲区都是相互独立的，只有当同一个缓冲区被多个进程同时访问时才存在互斥

要分析哪些过程/情况存在互斥，即同时访问同一个缓冲区
生产者-生产者：不存在，因为只有一个生产者
消费者-消费者：不存在，因为只有一个消费者
生产者-消费者：
    1.仓库不空不满：不存在互斥，因为此时尾指针和头指针不会重合
    2.仓库空或满：头尾指针指向同一单元，存在互斥，但是可以由同步信号量解决

    full  n   0
    empty 0   n
    可执行 放入 取空

image-20230903194415348

能否改变相邻的PV操作顺序？

——实现互斥的P操作一定要在实现同步的P操作之后。（要确定能进，才能锁门） V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

① -> ② -> ③
若此时缓冲区内已经放满产品，则empty=0，full=n。

则生产者进程执行①使mutex变为0，再执行②，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行③，由于mutex为0，即生产者还没释放对临界资源的“锁”，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现“死锁”。

③ -> ④ -> ①
同样的，若缓冲区中没有产品，即full=0，empty=n。按③④① 的顺序执行就会发生死锁。


注意：
互斥信号量加不加，加上肯定没错
实现互斥的P操作一定要在实现同步的P操作之后，否则可能导致死锁
分析问题应该以事件角度考虑，而不是以进程角度考虑

n-n-n情况

image-20230909153020276

分析：

同步：仓库为空时消费者不能取东西，仓库为满时消费者不能放东西 互斥：生产者-生产者，消费者-消费者，生产者-消费者(可以由同步信号量解决)

semaphore empty = n;
semaphore full = 0;
semaphore mutex = 1;    //互斥信号量（不完善）

//使用一个互斥信号量存在的问题：当仓库不空不满时，不能一边取，一边放
//改法：分别设一个互斥信号量mutex1，mutex2
//生产者
producer()
{
    while(ture)
    {
       P(empty);
       P(mutex1);
       放入;
       V(mutex1);
       V(full);
    }
}

//消费者
consumer()
{
    while(ture)
    {
        P(full);
        P(mutex2);
        取出；
        V(mutex2);
        V(empty);
    }
}

上述代码只设置了一个互斥信号量，解决了互斥，但是用力过猛了（不能一边放消息、一边取消息）。可以分别设置两个互斥信号量（实现互斥：生-生，消-消）

var empty,full,mutex1,mutex2:semaphore:=n,0,1,1;
buffer:array[0,..,n-1] of item
begin
    parbegin
        producer:
            begin
                repeat
                    ...
                    生成一条消息=>nextp;
                    ...
                    p(empty);
                    p(mutex1);
                    buffer(in):=nextp;
                    in:=(in+1)mod n;
                    v(full);
                    v(mutex1);
                until false
            end

        consumer:
            begin
                repeat
                    p(full);
                    p(mutex2);
                    nextc:=buffer(out);
                    out:=(out+1)mod n;
                    v(empty);
                    v(mutex);
                    消费nextc中的一条信息;
                until false
            end
    parend
end

——哲学家进餐问题

问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

image-20230909153132791

问题分析

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。

关系分析

系统中有5个哲学家进程，5位哲学家与左右邻居对其中间筷子的访问是互斥关系。

整理思路: 这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。 信号量设置: 定义互斥信号量数组 chopstick[5]={1,1,1,1,1} 用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家 i 左边的筷子编号为i，右边的筷子编号为 (i+1)%5。

合理方案

可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的

image-20231212170602761

要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

==写在后面==：关于死锁问题的一些思考
就目前学到的知识，当进程需要申请多种资源才能执行时，可能会发生死锁
最直接的解决方案就是：AND信号量，要么一次性获得所有资源，要么等待所有资源都空闲
背后的思想就是：每次至少让一个人能拿到所需的所有资源
针对这一要求来设计限制——哲学家进餐问题

——读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

——关系分析——

互斥关系：写-写，读-写

读-读之间不存在互斥关系，因此，只要有一个读进程在执行（没有和写互斥），那么读进程可以一直进行

同理，只要还有一个读进程在执行，就不能执行写进程，直到所有的读进程完成

——信号量设置

设置一个整形的信号量——readcount，专门用于计数：正在执行中的读进程的数量（同时也是一个临界资源） 配套一个互斥信号量——rmutex（读进程要访问，写进程也要访问readcount）

设置一个互斥信号量——wmutex() (互斥：读-写，写-写)

semaphore wmutex = 1;
int readcount = 0;
semaphore rmutex = 1;

reader()
{
    while(ture)
    {
        P(rmutex);
        if(readcount == 0)
            P(wmutex);  //
        readcount = readcount + 1;
        V(rmutex);

        执行读操作；

        P(rmutex);
        readcount = readcount - 1;
        if(readcount == 0)
            V(wmutex);  //
        V(rmutex);
    }
}

writer()
{
    while(ture)
    {
        P(wmutex);
        执行写操作；
        V(wmutex);
    }
}

==思考==：reader()中能否保留首尾的P（rmutex）和V（rmutex），而删去中间的？

——不可以，如此则多了一个限制：不能多个进程同时读

==写在后面==：关于互斥P,V的思考
互斥信号量的P(),V()紧贴着临界区
这意味着它们中间的部分，执行一定受到了限制，即里面执行的操作/访问的资源存在互斥情况
这样想就回答了上面的思考题：读操作也包含在其中，读-读存在互斥——与关系分析不符，引入了不存在的限制，不可以这样做

image-20230909155213659

桌子上有一只盘子,每次只能放入一只水果。爸爸专向盘中放苹果,妈妈专向盘中放桔子,儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。试用P、V操作完成上述四个进程？

image-20231212192306842

购物问题。某超级市场,可容纳100人同时购物,入口处备有篮子,每个购物者可持一个篮子入内购物,出口处结帐,并归还篮子(出、入口(一共2个口)仅容纳一人通过),请用P、V操作完成购物同步算法。 

某条河上只有一座独木桥(东西向),以便行人过河。现在河的两边都有人要过桥,按照下面的规则过桥,为了保证过桥安全,请用P、V操作分别实现正确的管理。
(1)每次只有一个人通过桥。
(2)同一方向的可连续过桥,某方向有人过桥时另一方向的人要等待

小路问题。在两地之间有一条弯曲小路,其中S到T的一段路每次只允许一辆自行车通过,但中间有一个小的“安全岛”M(同时允许两辆自行车停留),可供两辆自行车在从两端进入小路情况下错车使用,如图,试设计一个算法使来往的自行车均可顺利通过。(同方向不允许连续过自行车)

image-20231212193009030

拣棋子问题。生产围棋的工人不小心把相等数量的黑棋子和白棋子混装在一个箱子里,现要用自动分拣系统把黑棋子和白棋子分开,该系统由两个并发执行的进程组成,系统功能如下:
(1)进程A专门拣黑子,进程B专门拣白子;
(2)每个进程每次只拣一个,当一个进程在拣子时,不允许另一个进程去拣子;
(3)当一个进程拣了一个子(黑或白)以后,必让另一个进程拣一个子(白或黑); 
(4)进程A先执行。

某寺庙有小、老和尚若干,有一个水缸,由小和尚提水入水缸供老和尚饮用。水缸可以容纳10桶水,水取自同一井水。水井狭窄,每次只能容一个桶取水。水桶总数为3个,每次入、出水缸仅一桶,且不可同时进行。试P、V操作描述算法。(提示：老和尚从水缸取水需要用桶)

2.6 管程机制

image-20230909160408025

使用管程时，编写伪代码不用考虑互斥了（管程自动解决），但是还是要考虑同步的问题

2.7 进程通信（~看）

进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的程效率传输大量数据的通信方式。

进程是分配系统资源的单位（包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

但是进程之间的信息交换又是必须实现的。为了保证进程间的安全通信，操作系统提供了一些方法。

共享存储

两个进程对共享空间的访问必须是互斥的（互斥访问通过操作系统提供的工具实现）。

操作系统只负责提供共享空间和同步互斥工具（如P、v操作)

  • 基于数据结构共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
  • 基于存储区共享：基于在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

管道通信

“管道”是指用于连接读写进程的一个共享文件，又名pipe文件。其实就是在内存中开辟一个==大小固定的缓冲区==

  • 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
  • 各进程要互斥地访问管道。
  • 数据以字符流的形式写入管道，当管道写满时，写进程的write() 系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程的read() 系统调用将被阻塞。（缓冲区的特性）
  • 如果没写满，就不允许读。如果没读空，就不允许写。（缓冲区的特性）
  • 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

特点:

  • 以文件为传输介质。

  • 以字符流方式读写。

  • 以队列方式工作。

  • ==UNIX系统==

消息传递

进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息 / 接收消息”两个原语进行数据交换。

——消息组成：

  • 消息头：包括发送进程ID、接受进程ID、消息类型、消息长度等格式化的信息（计算机网络中发送的“报文”其实就是一种格式化的消息)
  • 消息体

——消息传递方式：

  • 直接消息传递：消息直接挂到接收进程的消息缓冲队列上
  • 间接消息传递：消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。Eg：计网中的电子邮件系统

客户机-服务器系统

主要是在网络环境的各种应用领域以成为当前主流的通信实现机制，实现方法分为三类： （1）套接字（Socket）：起源于20世纪70年代加州伯克利分校版本的UNIX（BSD Unix），是UNIX操作系统下的网络通信接口。 （2）远程过程调用： RPC（Remote Procedure Call）远程过程调用，通过网络从远程计算机上请求调用某种服务。它是一种通过网络从远程计算机程序上请求服务，而不需要了解底层网络技术的协议。 （3）远程方法调用：RMI（Remote Method Invocation）远程方法调用，能够让在客户端Java虚拟机上的对象像调用本地对象一样调用服务端java虚拟机中的对象上的方法。

直接通信原语：

对称寻址方式：
send(receiver,message);//发送一个消息给接收进程
receive(sender,message);//接收sender发来的消息

非对称寻址方式：
send(P,message);
receive(id,message);

信箱通信原语：

send(mailbox,message);//将一个信息发送到指定信箱
receive(mailbox,message);//从指定邮箱接受一个信息

2.8 线程的基本概念

进程：资源调配的基本单位，独立运行的单位
线程：独立运行的基本单位

进程过于大/繁琐，调来调去代价过大，引入线程

拓展知识：进程调度的切换和过程

“狭义的进程调度”与“进程切换”的区别：

  • 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）

  • 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

过程

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：

  • 对原来运行进程各种数据的保存
  • 对新的进程各种数据的恢复（如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

2.9 线程的实现（略）

image-20231212200200646

image-20231212200222441

第三章 处理机调度

原因/目的：计算机内部的资源有限，需要经过调度来实现系统资源利用率的最大化。

调度的本质：·==资源分配==

3.1 处理机调度的基本概念

3.1.1 三种层次的处理机调度

1.高级调度

==高级调度，又称长程调度、作业调度、接纳调度==

  • 将外存上处于后备作业队列上的作业调入内存,并创建进程、分配资源,安排在就绪队列上

  • 调度对象：作业

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

每次执行作业调度时，需要考虑以下两方面：

  • 接纳多少个作业
  • 接纳哪些作业（作业调度算法的选择）
  • 先来先服务
  • 短作业优先
  • 优先权高优先

image-20230917155240124

2.低级调度

==低级调度，又称短程调度、进程调度==

  • 决定就绪队列中的哪个进程应获得处理机。

  • 调度对象是进程

常见的低级调度有两种：非抢占式，抢占式

  • 非抢占式（非剥夺式）

一旦将处理机分配给某进程，便让该进程一直执行，直至该进程正常完成或阻塞时再分配给其他进程

引起进程调度的因素：

  • 正在执行的进程执行完毕,或因发生某事件而不能再继续执行
  • 执行中的进程因提出I/O请求而暂停执行
  • 在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)、Block原语等

优点：简单,系统开销小

缺点：不适合时间要求严格的实时系统

  • 抢占式

允许调度程序根据某种原则,暂停正在执行的进程,将处理机分配给其他进程

抢占式调度主要有以下原则:

  • 优先权原则:重要作业赋予高优先权,优先占用处理机
  • 短作业(进程)优先原则:执行时间短的进程优先执行
  • 时间片原则:时间片用完后停止执行,适用于分时系统

特点:它增加了进程调度的次数,增加了系统的开销,但保证了系统的实时性

3.中级调度

image-20230917160609026

4.三层调度对比

img

image-20230917160609026

注意“挂起”和“阻塞”的区别:
两种就绪挂起状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

image-20231212222900266

3.1.2 调度队列模型

1. 仅有进程调度的调度队列模型

在分时系统中,通常仅设有进程调度,用户键入命令和数据,都直接进入内存,系统可以把就绪进程组织成一个队列

  • 时间片

image-20230917161457894

每个进程在执行时,可能有以下三种情况

  • 进程在给定时间片内已完成,释放处理机后为完成状态
  • 进程在时间片内未完成,进入就绪队列末尾
  • 进程在执行期间因某事件而阻塞,进入阻塞队列

2.具有高级和低级调度的调度队列模型

在批处理系统中,不仅需要进程调度,而且还要有作业调度

该模型与上一模型主要区别在于:

就绪队列的形式

  • 在批处理系统中,常用优先权队列。进程进入就绪队列时,按优先权高低插入相应位置

设置多个阻塞队列

  • 根据事件的不同设置多个队列提高效率

image-20230917161915152

image-20230917162117005

3.同时具有三级调度的调度队列模型

在引入中级调度后,可把就绪分为内存就绪和外存就绪(就绪挂起);阻塞也可分为内存阻塞和外存阻塞(阻塞挂起)

image-20230917162341468

4. 图表总结

调度队列模型 适用操作系统类型
仅有进程调度 分时系统
作业调度+进程调度 批处理系统
三级调度（作业调度+进程调度+内存调度）

即批处理、分时、实时操作系统都有进程调度

3.1.3 选择调度方式和调度算法的若干准则

#### 1. 面向用户的准则\

  • 周转时间短
  • 响应时间快

公式：

​ 周转时间 = 结束执行的时间 - 进入磁盘的时间

​ 带权周转时间 = 周转时间 / 服务时间

image-20230917163940813

image-20230917163955298

2. 面向系统的准则

  • 系统吞吐量高
  • 处理机利用率高
  • 各类资源的平衡利用（性）
吞吐量指单位时间内系统所完成的作业数
作业调度的方式和算法对吞吐量的大小有较大影响

各类资源：内存、外存和I/O设备

3.2 调度算法

周转时间=结束执行时间-进入磁盘时间
带权周转时间=周转时间/服务时间
等待时间=开始执行时间-进入磁盘时间（并不总是：HRF抢占式，时间片轮转）实际（周转时间-执行时间）
高响应比=(等待时间+服务时间)/服务时间 或=等待时间/服务时间

调度算法评价指标

image-20231212225814658

CPU利用率：指CPU “忙碌”的时间占总时间的比例。

利用率 = 忙碌的时间 / 总时间

系统吞吐量：单位时间内完成作业的数量

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔

平均周转时间：各个作业周转时间之和 / 作业数

带权周转时间：

image-20231212225239385

带权周转时间始终大于1，带权周转时间和周转时间越小越好

等待时间：是指进程/作业处于等待处理机状态时间之和（等待被服务）

显然：等待时间+服务时间（执行时间）= 周转时间（不一定是这样）

响应时间：用户提交请求到首次产生相应所用的时间。

3.2.1 先来先服务和短作业优先算法

1. 先来先服务算法(FCFS)
  • 按照作业进入系统的先后次序进行调度,先进入系统者先调度;即启动等待时间最长的作业
  • 是一种最简单的调度算法,即可用于作业调度（谁先到后备队列）,也可用于进程调度（谁先到就绪队列）
  • FCFS算法比较有利于长作业(进程),而不利于短作业(进程)
  • 不会导致“饥饿”

下面这个例子默认内存无限大：即作业调度不受限；并且作业调度的时间极小

image-20231212230818365

image-20230917210504241

下面这个例子内存有限，并且采用不移动的可变分区方式

image-20230917210839117

进入磁盘时间、装入主存时间、开始执行时间

10:30此时内存不够，C不能进行作业调度装入主存，但是当时间到10:36时，D可以装入主存。直到A,B结束执行后，才有足够大的连续的内存空间，11:18时A,B结束，C，E装入内存，但根据进入磁盘时间的先后，实际上是C先E后

对于FCFS的进程调度而言，D先C后，C先E后

image-20230917211002840image-20230917211846040

2. 短作业优先算法（SJ(P)R）
  • 短作业(进程)优先调度算法SJ(P)F,以要求运行时间长短进行调度,即启动要求 目前队列中运行时间最短的作业
  • 可以分别用于作业调度和进程调度
  • 短作业优先(SJF)的调度算法,是从后备队列中选择一个或若干个估计运行时间最短的作业,将它们调入内存运行; 而短进程优先(SPF)调度算法,则是从就绪队列中选出一估计运行时间最短的进程,将处理机分配给它,使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时,再重新调度

image-20230917212256341

image-20230917212319225

image-20230917212347377

E,C都是在11:18装入主存的，但由于是短作业优先，所以E相对更早进入主存

SJ(P)F调度算法也存在不容忽视的缺点:
(1)该算法对长作业不利,可能产生饥饿现象，如作业C的周转时间由10增至16,其带权周转时间由2增至3.2。更严重的是,如果有一长作业(进程)进入系统的后备队列(就绪队列),由于调度程序总是优先调度那些(即使是后进来的)短作业(进程),将导致长作业(进程)长期不被调度。
(2)该算法完全未考虑作业的紧迫程度,因而不能保证紧迫性作业(进程)会被及时处理。
(3)必须预知作业的运行时间。由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的,而用户又可能会有意或无意地缩短其作业的估计运行时间,致使该算法不一定能真正做到短作业优先调度。
(4)在采用SJF算法时，人-机无法实现交互。

image-20231212232323791

3.2.2 高优先权优先调度算法

1. 优先权调度算法的类型
  • 非抢占式优先权算法
  • 抢占式优先权算法
2. 优先权的类型

  • 静态优先权 静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。 (1)进程类型系统进程优先级高于用户进程 (2)进程对资源的需求执行时间短,内存要求小的进程,有较高优先权。 (3)用户要求根据用户进程紧迫程度及用户所付费用的多少来确定静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。 三种依据： (1)进程类型 系统进程优先级高于用户进程 (2)进程对资源的需求 执行时间短,内存要求小的进程,有较高优先权。 (3)用户要求 根据用户进程紧迫程度及用户所付费用的多少来确定>

    注意：数值越大！=优先权越高，具体要看题目

  • 动态优先权

3. 高响应比优先调度算法（HRF）
  • 该算法是FCFS和SJF的结合,克服了两种算法的缺点
  • 响应比最高的作业优先启动
  • 等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比R~P~。
  • 采用的是动态优先权

优先权的两种公式（相差1）==用第二种==

image-20230917214031917

image-20230917214159195

执行完B后：

image-20231214205837187

==非抢占式==

image-20230918082559131

==抢占式==

image-20230918082659516

image-20231212233504920

3.2.3 基于时间片的轮转调度算法

1. 时间片轮转算法

image-20230918082750262

进程A并不是“一口气”执行完成的，等待时间：

image-20230918084211391

image-20230918084135200

图一是极其粗糙的，比如时间为1时，A执行完装入主存并且B装入主存，谁先谁后？

注意：进程执行完，立即将时间片分配给下一进程

image-20230918085105844

image-20231213162918110image-20231213162843289

2. 多级反馈队列调度算法

优先级从高到低，时间片从小到大

高优先级的队列执行完了，才轮到较低级的队列获得时间片

队列内采用FCFS，若时间片用完了进程还没执行完，则装入下一队列的队尾

image-20231213162935816

3.3 实时调度

3.3.1 实现实时调度的基本条件

（1）提供必要的信息（2）系统处理能力强（3）采用抢占式调度机制（4）具有快速切换机制 （小题）

  • 快速响应，快速任务分配

image-20231213163040110

image-20231213163050838

假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,必须满足下面的限制条件,系统才是可调度的。(若有N个处理机，则<=N)

image-20231213163201408

3.3.2 实时调度算法

1. 最早时间优先（EDF）

image-20231213163547972

2. 最低松弛度优先（LLF）

该算法根据任务的紧急（或松弛）程度，确定任务的优先级；任务越紧急，优先度越高，以使其优先执行。要求系统中有一个按松弛度排序的实时任务队列（低到高），调度程序选择队首（最低）的任务执行，即：选择松弛度小的任务执行 - 该算法主要用于可抢占调度方式中 - 松弛度是适时调整的，当某任务的松弛度降到0时，立即“终止”当前正在执行的任务（注意调整相关时间），执行该任务（抢占）

==松弛度 = 任务完成截止时间 - 当前时间 - 执行时间==

  • 松弛度 = 0 时，任务必须执行（抢占）
  • 松弛度 < 0 时，任务已经来不及执行了

假如在一个实时系统中,有两个周期性实时任务A和B,任务A要求每 20 ms执行一次,执行时间为 10 ms;任务B只要求每50 ms执行一次,执行时间为 25 ms:

image-20231209205446671

题目隐含条件：每 20 ms执行一次，即任务A1,A2,A3在0,20,40，...的时候才进入内存。

3.4 多处理机系统中的调度

3.4.1 多处理机系统的类型

1.按照多处理器之间耦合的紧密程度分为：

  • 紧密耦合MPS
  • 通过高速总线或高速交叉开关,来实现多个处理器之间的互连
  • 共享主存储器系统和I/O设备,并要求将主存储器划分为若干个能独立访问的存储器模块,以便多个处理机能同时对主存进行访问。系统中的所有资源和进程,都由操作系统实施统一的控制和管理
  • 松散耦合MPS
  • 通过通道或通信线路,来实现多台计算机之间的互连
  • 每台计算机都有自己的存储器和I/O设备,并配置了OS来管理本地资源和在本地运行的进程。因此,每一台计算机都能独立地工作,必要时可通过通信线路与其它计算机交换信息,以及协调它们之间的工作

2.根据系统中所用处理器的相同与否，将MPS分为：

  • 对称多处理器系统SMPS
  • 非对称多处理器系统
  • 只有一个主处理器,有多个从处理器

3.4.2 进程分配方式

1.对称多处理器系统中的进程分配方式

（1）静态分配方式

（2）动态分配方式

2.非对称MPS中的进程分配方式

image-20231215170600748

3.4.3 进程(线程)调度方式

1.自调度方式

image-20231215170714464

image-20231215170723645

image-20231215170732311

2.成组调度方式

image-20231215170754287

image-20231215170831950

3.专用处理器分配

image-20231215170840521

image-20231215170856929

3.5 产生死锁的原因和必要条件

死锁原因

  • 竞争资源（非剥夺资源（不可抢占式），临时性资源）

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

image-20231213103532990

死锁的必要条件：（1）互斥条件（2）请求和保持条件（3）不剥夺（不可抢占）条件（4）环路等待条件

image-20231213103707635

只要有一个必要条件不满足，就可以排除死锁

处理死锁的方法

  • 预防死锁：设置限制条件，破坏死锁产生的必要条件

  • 避免死锁：分配资源时，用某种方法防止系统进入不安全的状态（死锁条件存在，但是避免走向死锁）

  • 检测死锁：确定与死锁有关的进程和资源,采取措施,清除死锁。

  • 解除死锁：与检测死锁配套的一种措施。

image-20231213115441323

3.6 预防死锁的方法

原理：该方法是通过对资源分配的原则进行限制,从而使产生死锁的四个必要条件中的第2、3、4个条件之一不能成立,来预防产生死锁

环路等待，不可抢占，请求与保持

3.6.1 预防死锁

1.摒弃（破坏）“请求和保持”条件

方法：一次性请求所需要的所有资源

image-20231213105035240

第二种协议：允许一个一个申请资源，而且需要逐个释放已分配给自己的，且已用毕的全部资源，然后再请求新的所需资源。

2.摒弃（破坏）“不剥夺（不可抢占）”条件

方法： 当一个已经保持了某些资源的进程申请新资源而不能得到满足时,必须放弃所有已保持的资源

image-20231213105118446

3.摒弃（破坏）“环路等待”条件

image-20231213105136989

image-20231213110133839

3.6.2 系统安全状态（避免死锁）

​ 在死锁的避免中,所施加的限制较弱,将获得较好一些的系统性能。该方法把系统状态分为安全状态和不安全状态,只要能使系统始终处于安全状态,便可以避免发生死锁。

  • 避免死锁 是在资源动态分配的过程中，防止系统进入不安全状态，以避免发生死锁

安全状态：系统能按某种进程顺序(P1, P2, …,Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列,则称系统处于不安全状态。

避免死锁方法在进行资源分配前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,令进程等待。

image-20231213111117872

安全序列：P2(2),P1(5),P3(7) 如果不按照安全序列分配资源,则系统可能会由安全状态进入不安全状态

3.6.3 用银行家算法避免死锁

设计思想：当用户申请一组资源时,系统必须做出判断：如果把这些资源分出去,系统是否还处于安全状态。若是,就可以分出这些资源；否则,该申请暂不予满足。

  • 每一个新进程在进入系统后，必须声明在运行过程中，可能需要每种资源类型的最大单元数目，其数目不应超过系统所拥有的的资源总量。
  • 每次分配时，判断是否有足够的资源分配给该进程

使用到的数据结构：

可利用资源向量Available：Available[j]=K,则表示系统中现有 Rj 类资源K个

最大需求矩阵Max：如果Max[i,j]=K,则表示 进程i 需要 Rj类资源的最大数目为K

分配矩阵： Allocation[i,j]=K,则表示 进程i 当前已分得Rj类资源的数目为K

需求矩阵： 表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示 进程i 还需要 Rj类资源 K个,方能完成其任务。

Need[i,j]=Max[i,j]-Allocation[i,j]

银行家算法

选择足够分的请求，检查其安全性

image-20231213112522310

image-20231213114207096

image-20231213114222954

举例：

image-20231213114456945

image-20231213114506940

image-20231213114523000

image-20231213114535224

image-20231213114551323

image-20231213114603556

3.7 死锁的检测与解除

3.7.1 死锁的检测

1.资源分配图

  • 资源i ->进程j : 表示进程j 已经申请到了 资源i
  • 进程j -> 资源i ：表示进程j 还没有申请到 资源i（但是需要i）

image-20231213115747374

2.死锁定理

image-20231213115841131

S为死锁的充分条件是: 当且仅当S状态的资源分配图是==不可完全简化的==。该充分条件称为死锁定理

  • 找出一个既不阻塞又非孤立的进程结点Pi，消去Pi所有的请求边和分配边,使之成为孤立结点（即先得到所有资源，运行后释放所有资源） -> 使Pi+1获得资源而继续运行,直至Pi+1完成又释放出所占有资源
  • 在进行一系列化简后若能消去图中所有的边,使所有进程结点成为孤立结点,则称该图是可完全简化的;否则是不可完全简化的

image-20231213120218434

image-20231213120233007

3.7.2 死锁的解除

1.剥夺 / 抢占 资源

从其他进程剥夺足够的资源给死锁进程,以解除死锁状态

2.撤销（或终止）进程

简单方法:撤消（终止）所有死锁进程 温和方法:按照某种顺序逐个地撤消进程,直至有足够的资源可用,使死锁状态消除

第四章 存储器管理

![[45e4a5b931e47e59483ab13978db163.jpg]]

优化过程简介

固定 -- 装入/调用时可变/使用 -- 运行时 变/使用

连续 -- 离散 -- 虚拟

理想化预知 -- 就近判断 -- 根据刚刚的过去预知即将的未来

4.1 程序的装入与链接

多道程序环境下,程序要运行必须为之创建进程,而创建进程的第一件事就是分配内存

源程序要运行通常经过编译(compile)--链接(link)--装入(load)等几个步骤 ![[Pasted image 20230927220930.png]]

程序运行步骤简介：

(1)编译
由编译程序将用户源代码编译成若干个目标模块。

(2)链接
由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起,形成一个装入模块。

(3)装入。
由装入程序将装入模块装入主存的过程。

基本上三种思路：

  1. 固定的 / 静态的

  2. 可变的

    1. 装入时变换
    2. 运行时变换

4.1.1 程序的装入

==装入：由装入程序，将 装入模块 装入 主存 的过程。==

1.绝对装入方式

适合单道

为用户分配的存储空间的“逻辑地址/相对地址”是多少，装入主存时的“物理地址/绝对地址”就是多少

![[Pasted image 20230927221343.png]]

"该是多少，就是多少"

![[Pasted image 20230927221848.png]]

  • 装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址完全相同,故不需对程序和数据的地址进行修改

  • 绝对装入方式只能将目标模块装入到内存中事先指定的位置（预知->适合单道）

2.可重定位装入方式

  • 在多道程序环境下,不可能预知目标模块放在内存中的地址,因此绝对装入方式不适合在多道环境下使用(即不能做到预知，使逻辑地址=物理地址)

  • 程序中目标模块的地址通常从0开始,其他地址都是相对于0计算

把在装入时对目标程序中指令和数据的修改过程称为重定位 - 地址变换通常是在装入时一次完成的,以后不再改变,故称为静态重定位。 - 静态重定位特点: 简单、不能在内存中移动、要求连续。

<span style="background:rgba(140, 140, 140, 0.12)">程序装入到内存中，地址发生了变化（且只在装入时变换）：</span>

![[Pasted image 20230927222501.png]]

作业装入内存时的情况：

![[Pasted image 20230927222639.png]]

存在的问题：当采用可重定位装入方式时，作业装入内存后，不能进行移动（再次更改地址）

![[Pasted image 20230927223015.png]]

3.动态运行时装入方式

  • 可重定位方式不允许程序运行时在内存中移动位置，进行优化-》动态运行时装入方式

  • 装入程序,在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址，而是程序要执行时才进行地址装换

    • 在程序未执行前，装入内存后的所有地址都仍是相对地址（逻辑地址）,依靠硬件支持进行地址转换。

  • 动态重定位特点: 在内存中可移动

4.1.2 程序的链接

==链接：由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起,形成一个装入模块。==

1.静态链接方式

在程序运行前,先将各目标模块及所需的库函数链接成一个完整的装入模块,以后不再拆开

在将这几个目标模块装配成一个装入模块时,须解决以下两个问题 - 对相对地址进行修改 - 变换外部调用符号

![[Pasted image 20230927223751.png]]

2.装入时动态链接方式

将用户的源程序编译后所得的一组目标模块在装入内存时采用边装入边链接的方式 优点:

(1)便于目标模块的修改和更新 (2)便于实现对目标模块的共享

![[Pasted image 20230927224104.png]]

3.运行时动态链接方式

原因：应用程序在每次运行的模块可能不相同,出错模块不一定什么时候运行。

  • 运行时动态链接方式将对某些模块的链接推迟到执行时才去做

    • 即在执行过程中,当发现一个被调用模块尚未装入内存时,立即由OS去找到该模块并将之装入内存,把它链接到调用者模块上

  • 凡在执行过程中未被用到的目标模块,都不会被调入内存和被链接到装入模块上,这样不仅可加快程序的装入过程,而且可节省大量的内存空间

  • 理解：只在要用的时候，把它装入内存并“链接”，不需要用到的不会被调入内存和被链接；典型应用：dll

![[Pasted image 20230927225319.png]]

![[Pasted image 20230927225342.png]]

4.2 连续分配方式

==连续分配方式为一个用户程序分配一个连续的内存空间==

内部碎片和外部碎片

1.外部碎片：内存中的某些空闲区由于太小了而难以利用
2.内部碎片：分配给进程的内存区域中，有部分没有用上

4.2.1 单一连续分配

  • 单一连续分配是最简单的一种存储管理方式,但只能用于单用户、单任务的操作系统中

  • 内存中只能有一道用户程序，用户程序独占整个用户区空间。

  • 采用这种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给OS使用,通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间,提供给用户使用

  • 一般情况下无存储器保护机构(早期有)

  • 特点: (1)简单易行,系统开销小，使用覆盖技术 (2)资源利用率低(一次只能装入一个作业) (3)有内部碎片

![[Pasted image 20230929130529.png]]

4.2.2 固定分区分配

在产生了支持多道程序的系统后，为了能在内存中装入多道程序而互相之间不产生干扰，将整个用户区划分为若干个固定大小的分区(分区大小可以相等也可以不相等)，在每个分区中只能装入一道作业， 形成了最早的可运行多道程序的内存管理方式。

划分分区的方法：

  • 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
  • 分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分

实现方法：

为了便于内存分配，通常将分区按照其大小进行排队，并为之建立一张分区使用表，表中包含： 分区的起始地址、大小以及状态（是否已分配出去）

==注意：只分配用户区==

![[Pasted image 20230929131807.png]]

管理特点：

  • 固定分配分区方式支持多个程序并发执行

  • 一个作业只能装入一个分区（分区如果小了，便不能装入）,不能装入两个或多个相邻的分区。

  • 通过对“分区使用表”的改写，来实现主存的分配与回收。作业在执行时,不会改变存储区域，所以采用静态地址重定位方式。此方法易于实现,系统开销小。

  • 分区大小固定，会造成存储空间的浪费，产生内部碎片（无外部碎片)

4.2.3 动态分区分配

动态分区分配又称为可变分区分配， 这种分配方式不会预先划分内存分区。进程装入内存时根据进程大小动态地建立分区，并使得分区的大小正好适合进程的需要。

  • 系统中分区的大小和数目可变
  • 如何实现动态：从该分区中按请求的大小划分出一部分内存空间分配下去，剩余部分仍留在表中

分区分配中的操作

  • 分配内存
  • 回收内存

  • 1. 分配内存 ![[c0777c8c344623d078793423b41e4f7.jpg]] u.size：请求的分区大小 m.size：空闲分区的大小 size：规定的不再切割的空闲分区的大小（再小就用不了了，成碎片了） ![[a1b69811c6d3d6000d47866da7d147e.jpg]]

2. 回收内存(笔记不完整) ![[7ca7dce2bdcd861a141b4a4c56141e7.jpg]]

分区分配中的数据结构

  • 空闲分区表

    • 记录每个空闲分区的情况
    • ![[Pasted image 20231003074344.png]]

  • 空闲分区链

    • 实现对空闲分区的分配和链接
    • ![[Pasted image 20231003074416.png]]

分区分配算法

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

本质：依次搜索空闲分区链上的空闲分区，寻找一个大小能满足要求的空闲分区

基于顺序搜索的动态分区分配算法
1. 首次适应算法

  • 空闲分区链以地址递增顺序链接

  • 分配时从链首开始查找,找到一个大小可满足的空闲分区,划出一块给请求者（优先利用低地址部分的空闲分区）

  • 低地址部分被不断划分，会留下“碎片” ``碎片：难以被利用的，很小的分区

![[Pasted image 20231003074935.png]] ![[Pasted image 20231003074953.png]] ![[Pasted image 20231003075010.png]]

优点:

(1)分配算法简单 (2)优先利用低址部分,保留了高址的大空闲区,为大作业装入提供条件。

缺点:

每次从链首开始,增加了查找开销,并且留下许多难以利用的”碎片”(外碎片)

2. 循环首次适应算法

  • 空闲分区链以地址递增顺序链接,链表为循环链表

  • 每次分配时从上一次找到空闲分区的下一个空闲区开始

![[Pasted image 20231003075922.png]] ![[Pasted image 20231003075947.png]] ![[Pasted image 20231003080009.png]]

优点:

使空闲分区分布均匀,减少查找空闲分区开销

缺点:

会缺乏大的空闲分区

3. 最佳适应算法

  • 空闲分区链以分区大小递增的顺序链接(每分配一次，都要调整顺序)

  • 每次为作业分配内存时，将能满足条件，且是最小的空闲分区分配给作业（避免“大材小用”）

    • 从头开始,第一次找到满足要求的空闲分区,必然是最优的

  • 分区切割后的剩余部分（小）——产生不可利用的空闲区（“小碎片”）

  • ==收回主存时,要按分区大小递增顺序插入到空闲区表中==

``如何找到满足条件的最小？ ——排序+作差

![[Pasted image 20231003080553.png]] 排序： ![[Pasted image 20231003081049.png]] 分配满足条件的最小空闲分区： ![[Pasted image 20231003081114.png]] 排序： ![[Pasted image 20231003081155.png]]

4. 最差（坏）适应算法
  • 空闲分区链以分区大小递减的顺序链接(每分配一次，都要调整顺序)
  • 每次为作业分配内存时，将能满足条件，且是最大的空闲分区分配给作业（避免“大材小用”）
    • 从头开始,第一次找到满足要求的空闲分区,必然是最优的
  • 分区切割后的剩余部分（小）——产生不可利用的空闲区（“小碎片”）
  • ==收回主存时,要按分区大小递减顺序插入到空闲区表中==
基于顺序搜索的动态分区分配算法 链接顺序 分配特点 缺点
首次适应算法 地址递增 每次从链首开始，分配第一个大小满足的分区 低址部分会产生外碎片
循环首次适应算法 地址递增 每次从上一次的下一个分区开始，分配第一个大小满足的分区 会缺乏大的空闲分区
最佳适应算法 分区大小递增 分配大小满足且是最小的分区（排序+首次适应的分配方式） 性能差（几乎每个分区都会被“噶”）
最差适应算法 分区大小递减 分配大小满足且是最大的分区（排序+首次适应的分配方式 会缺乏大的空闲分区
##### 基于索引搜索的动态分区分配算法
为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法
###### 1.快速适应算法(分类搜索法)
  • 按照分区大小设置多个空闲分区链，增加一个索引表，可以快速对应到一个空闲分区链上。
  • 空闲分区链分类：常用的大小分类，如2KB,4KB,8KB
  • 特点:分配速度快,不进行分区分割;存在一定的主存浪费;典型的以空间换时间的作法。 ![[Pasted image 20231005163207.png]]
2.伙伴系统
  • Linux采用伙伴(buddy)算法对物理内存进行管理
  • 通过不断地平分较大的空闲内存块来获得较小的空闲内存块，直到获得所需的内存块；当内存释放时，尽可能的合并空闲内存块（若伙伴空闲，则与伙伴合并..........）。 其中内存块分配与合并都采用以2的幂次方为单位。
  • 所谓“伙伴”，就是指在空闲块被分裂时，由一个大块内存分裂出来的两个小块内存,互称“伙伴”
  • 算法采用位图和空闲链表作为辅助工具，其中位图用来跟踪内存块的使用情况，空闲链表用来维护内存中没有使用的内存块
    • 位图：0表示空闲，1表示已经分配，每一位表示一个最小的分配请求单元 当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i-1<n≤2i，在空闲分区大小为2i的空闲分区链表中查找，否则在2i+1找，等分后分配，依次类推。
  • 分配内存的大体步骤
    • 需要申请 n KB 的内存空间
    • 搜索空闲链表，对应的 n KB 的是否为空
    • 若为空——继续平分（要加入到空闲链表种）直至产生 n KB 的内存块，分配
    • 若不为空——分配对应的内存块
    • 更改位图
  • 释放内存的大体步骤
    1. 将当前释放的内存块的位图清零
    2. 检测当前释放的内存块的伙伴是否处于使用状态
    3. 若伙伴处于空闲状态，合并，转向步骤2
    4. 若伙伴处于使用状态，不能合并，将当前内存块加入到对应的空闲链表中

分配内存实例 ![[Pasted image 20231005164126.png]] 申请8KB的内存空间： 1. 整个内存分成A和A’(各个分区指向空闲链表对应的大小) 2. A分成B和B’ 3. B分成C和C’ 4. 分配C给用户，更新位图 ![[Pasted image 20231006091654.png]]

释放内存实例 初始状态：![[Pasted image 20231006092949.png]] 释放2KB的E块 1. E’正处于空闲状态，E和E’合并为D 2. D’正处于空闲状态，D和D’合并为C' 3. C正处于空闲状态，C和C’合并为B 4. B'正处于使用状态，不合并，将B加入到16KB的空闲链表中 ![[Pasted image 20231006093407.png]]

3.哈希算法
  • 引入原因：上述的分类搜索法和伙伴系统中，都是把空闲分区进行分类，再查找这些分类的分区上会使时间性能下降。
  • 原理：哈希算法就是利用哈希快速查找的优点，对索引表进行快速查找

小结

连续分配方式 辅助的数据结构 特点 备注
单一连续分配 无 一道进程独占用户区 有内部碎片
固定分区分配 分区使用表 内存划分为若干固定大小的区域，每个分区只装入一道作业 有内部碎片
动态分区分配 空闲分区表 根据进程的大小动态地分配内存空间 多种分配算法 产生许多“外碎片”

4.2.4 （动态）可重定位分区分配

如何解决装入后“不可移动”的问题？ 使用的技术：“拼接”或“紧凑”——将原来分散的多个空闲小分区拼接成一个大分区

优点: - 可以消除碎片,能够分配更多的分区,有助于多道程序设计,提高内存的利用率。

缺点: - 紧凑增加主机的开销，花费了大量CPU时间 - 每次紧凑后，都必须对移动的程序和数据进行重定位，修改空闲分区表 移动条件: 无内外存信息交换

![[Pasted image 20231006094957.png]]

动态可重定位分区分配的实现 - 正如动态运行时装入方式，作业装入内存后的所有地址仍是相对地址,将相对地址转换成物理地址的工作在指令执行时进行 - 地址变换过程是在程序执行期间,随着每条指令和数据的访问而自动进行的（动态运行时装入）。 - 真正访问地址=相对地址+重定位寄存器中地址 - 需要有硬件地址变换机构的支持 ![[Pasted image 20231006095443.png]]

动态可重定位分区分配算法 动态可重定位分配算法与动态分区分配算法基本相同，差别在于：增加了紧凑的功能

基于顺序搜索：首次适应算法，循环首次适应算法，最佳适应算法，最差适应算法
基于索引搜索：快速适应算法，伙伴系统，哈希算法（搜索）

![[Pasted image 20231006095745.png]]

4.2.5 对换(Swapping)

  • 把内存中暂时不能运行的进程或者暂时不用的程序和数据,调（换）出到外存上,以便腾出足够的内存空间,再把已具备运行条件的进程或进程所需要的程序和数据,调（换）入内存——提高内存利用率和系统吞吐量
    • 对换是以整个进程为单位,称为“整体对换”或“进程对换”
    • 对换是以“页”或“段”为单位进行的,则称为“页面对换”或“分段对换”,又统称为“部分对换”（目的是为了支持虚拟存储器） ![[Pasted image 20231006101220.png]] 为实现进程对换，系统要实现三方面的功能：对换空间的管理，进程的换入和换出

对换空间的管理

  • 在具有对换功能的OS中,通常把外存分为文件区和对换区
    • 文件区管理的主要目标是提高文件存储空间的利用率,采取离散分配方式。
    • 外存中对换区主要存放从内存中换出的进程,对换空间管理的主要目标是提高进程换入和换出的速度。
  • 为了能对对换区中的空闲盘块进行管理,在系统中应配置相应的数据结构,以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似,即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项, 即对换区的首址及其大小,它们的单位是盘块号和盘块数
  • 对换区的分配采用连续分配方式,分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法

进程的换出与换入

极其耗费时间 进程的换出 1. 选出被换出的进程 选择原则: - ⅰ先“阻塞”或“睡眠”的进程,后“就绪” - ⅱ优先级低的进程 - ⅲ在内存最长的进程的进程换出 - ⅳ最近最久未使用进程 2. 进程换出过程 - 系统首先选择处于“阻塞”状态且优先级最低的进程作为换出进程,然后启动盘块,将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误,便可回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改。 - 若换出进程，应确保该进程完全处于空闲状态 - 在换出进程时，只能换出非共享的程序与数据段；共享的程序与数据段只要还有进程需要它，就不能被换出 进程的换入 - 系统应定时地查看所有进程的状态，从中找出(PCB集合中)“就绪”状态且已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，申请内存，若成功将之换入，否则在换出某些进程,腾出足够内存，再换入。

对换和覆盖

在多道程序系统下用来扩充内存的两种方法 - 交换技术主要在不同进程（作业）进行，而覆盖用于同一个程序或者进程中

4.3 基本分页存储管理方式

如果允许一个进程直接分散地装入到许多不相邻接的分区中,称为离散分配方式，可以充分的利用内存空间（并无需进行“紧凑”） 离散分配方式有分页存储管理方式、分段存储管理方式和段页存储管理方式

大致实现方式：

  1. 在为作业分配主存时,以块为单位将作业中的若干页分别装入多个可以不相邻接的块中。作业执行时根据逻辑地址中的页号找到它所在的块号,再确定当前指令要访问的主存的物理地址。
  2. 程序地址空间分成大小相等的页面,同时把内存也分成与页面大小相等的块,当一个用户程序装入内存时,以页面为单位进行分配。页面的大小是为2n,通常为1KB,2KB,nKB等。

页面大小的确定： - 在分页系统中的页面其大小应适中，由硬件决定,即由机器的地址结构所决定。 - 页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外,还会降低页面换进换出的效率 - 如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为1KB~8KB

一些概念

将进程（逻辑地址空间）分为等大小的页 -> 页面，页号 逻辑地址 = 页号 * 页大小 + 页内偏移量（相对地址）

将主存按相同的页大小分块 -> 页框/块，块号 物理地址 = 块号 * 页大小 + 页内偏移量

分页系统中,将进程的每一页离散地存储在内存的任一物理块中,为每个进程建立一张页面映像表 -> 页表（每个进程一张表） - 作用：是实现从页号到物理块号的地址映射 - 组成：页号 - 块号（慢表通常不需要存页号，要连续分配）

![[Pasted image 20231006110532.png]]

![[Pasted image 20231006111207.png]]

访问程序需要访问2次内存（相较于直接访问，指令的执行时间变慢） 由于页表是存放在内存中,因此每次CPU存取一个数据要两次访问内存即,查页表时要作一次访问内存的工作,然后是访问程序要求访问的内存 每个进程对需要建一个对应的页表 页表、快表需要占内存；页表中的页号可以省略，快表不行

地址变换过程：

页表大多驻留在内存中,在系统中设置页表寄存器PTR(Page–Table Register),在其中存放页表在内存中的始址和页表的长度 进程未执行时,页表的始址和页表长度存放在本进程的PCB中,当调度程序调度到某进程时,才将这两个数据装入页表寄存器

无快表的情况

![[屏幕截图 2023-10-06 112513.png]]

拥有快表的地址变换机构

  • 为提高地址变换速度，在地址变换机构中增设一个具有并行查寻能力的高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)或“快表”，用以存放当前访问的那些页表项,价格贵。
  • 快表组成：页号+块号（页号不可以省略，因为不是连续的） ![[Pasted image 20231006113803.png]]

具体求解方法

PS：可能的越界：逻辑地址中的页号大于页表的长度 - 首先根据给出的地址，得到页号/块号，页内偏移量 - 然后查询页表，得到对应的块号/页号 - 拼接页/块的基址和页内偏移量（说成相加也行），得到相对应的内存中的地址/逻辑地址 需要访问两次内存

如何得到页号和页内偏移量？ 公式联想：123 = 1 * 102 + 23 <=> 123 / 102 = 1.....23

一般法： 逻辑地址（十进制形式）除以页大小 - 商——页号 - 余数——页内偏移量 启发法： 逻辑地址、页大小转换为2进制形式，假设页大小为2n B 则：逻辑地址 = 页号 * 2n + 页内偏移量（相对地址），相当于页号（B）左移了n位，低位补相对地址 - 低n位——页内偏移量 - 其余高位——页号（别管2n的位权了，直接数数）

![[Pasted image 20231006111301.png]]

两级和多级页表

  • 现代的大多数计算机系统,都支持非常大的逻辑地址空间(232~264)。在这样的环境下,页表就变得非常大,要占用相当大的内存空间，并且，页表需要占据连续的内存空间
  • 可以采用两个方法来解决这一问题
    1. 采用离散分配方式来解决难以找到一块连续的大内存空间的问题
    2. 只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上，需要时再调入 ![[Pasted image 20231213213943.png]] ![[Pasted image 20231213214033.png]]

4.4 基本分段存储管理方式

段大小不定，它以段为单位分配主存，每段分配一个连续的主存空间，但各段之间不要求连续。由于各段的长度不一样,所以分配的内存空间大小也不一样。 - 属于==满足用户需要==的存储管理方式，并不能实现提高内存利用率，存在外碎片问题 - 供用户使用的逻辑地址为段号(段名)+段内地址。 - 用一张段表记录每个分段在主存中的起始地址和长度 - 主存的分配与回收类似于动态分区分配,采用动态重定位

![[Pasted image 20231011200812.png]] ![[Pasted image 20231011200728.png]]

地址变换机构

![[Pasted image 20231011200904.png]]

  • 可能的越界：段号，段内偏移量
  • 段表元素：段号，段长，基址（主存内）
  • 需要访问两次内存
具体求解方法

以段号查段表，得到对应段装入内存的基址 内存地址＝基址＋段内地址

分页和分段的主要区别

![[Pasted image 20231011202046.png]]

分块方式 使用 碎片 长度 目的
分页存储管理 物理分块 对程序员是不可见，使用简单 每个进程只有一个内部碎片，大小不超过1页 固定 提高内存的利用率
分段存储管理 逻辑分块，大小与信息块有关，满足用户需要 对程序员可见，使方便，但系统实现难度大 会产生多个外部碎片 不固定 便于信息保护与共享，方便用户

信息共享

分段存储的一个优点是易于实现段的共享，即允许若干个进程共享一个或多个分段 `分页系统中虽然也能实现程序和数据的共享,但远不如分段系统方便

`分段系统中共享editor的示意图 ![[Pasted image 20231011202146.png]]

可重入代码(Reentrant Code)：又称为“纯代码”(Pure Code)是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码 1. 程序在执行时可能改变的部分,拷贝到该局部数据区。 2. 程序执行时,只对该数据区(属于该进程私有)中的内容进行修改,而不去改变共享的代码

段页式存储管理方式

分配方式：

根据程序情况把程序分成若干段，再根据页面大小把每一段分成若干页

主存仍然分成与页大小相等的块。分配主存时,把程序的每一段的页分配到主存块中。

地址结构：

段页式管理中,逻辑地址由段号、段内页号及页内地址三部分所组成 ![[Pasted image 20231011202659.png]]

地址变换过程：

![[Pasted image 20231011202805.png]]

基本特点：

  • 这种分配方式（见上）既照顾到了用户共享和使用方便的需求,又考虑到了主存的利用率,提高了系统的性能

- 这种分配方式比分页管理的空间浪费要多（如：多了一个表要存入内存）

4.5 虚拟存储器的基本概念

4.5.1 虚拟存储器的引入

传统存储管理的分类和特点

![[Pasted image 20231011215446.png]]

![[Pasted image 20231011215739.png]] ![[Pasted image 20231011215942.png]]

2.局部性原理（实现的原理）

![[Pasted image 20231011220030.png]]

![[Pasted image 20231011220458.png]]

3.虚拟存储器定义

![[Pasted image 20231011203944.png]]

4.5.2 虚拟存储器的实现方法

虚拟存储器的实现都是建立在离散分配的存储管理方式基础上的 ![[Pasted image 20231011203857.png]]

![[Pasted image 20231011203648.png]]

![[Pasted image 20231011203707.png]]

4.5.3 虚拟存储器的特征

==离散型，多次性，对换性，虚拟性==

![[Pasted image 20231011203608.png]]

![[Pasted image 20231011221424.png]]

4.6 请求分页存储管理方式

请求分页系统

在分页系统的基础上增加了请求调页功能和页面置换功能 - 请求调页功能：在发生缺页中断时，将缺失页面从外存调入到内存中 - 页面置换功能：当分配的内存已满时，将暂时用不到的页面换出内存

(1)硬件支持

1.请求分页的页表机制

它是在纯分页的页表机制上增加若干项而形成的,作为请求分页的数据结构; ![[Pasted image 20231009092219.png]] - 访问字段A：用于记录本页在一段时间内被访问的次数,或记录本页在最近多长时间未被访问 - 修改位M：表示该页在调入内存后是否被修改过 - 状态位P：用于指示该页是否已调入内存，供程序访问时参考 - 外存地址：该页在外存上的地址,通常是物理块号,供调入该页时参考。 ![[Pasted image 20231011152233.png]]

2.缺页中断机构

即每当用户程序要访问的页面尚未调入内存时便产生缺页中断（属于内中断），以请求OS将所缺的页调入内存（或者是页表中没有对应的块号时->缺页中断） 注意也要保存多次中断时的状态 ![[Pasted image 20231011152451.png]]

缺页中断与一般中断的区别 1. 在指令执行期间产生和处理中断信号（要用时发现不在内存->立即缺页中断） 2. 一条指令在执行期间可能产生多次缺页中断

    ![[屏幕截图 2023-10-11 102204.png]]
3.==地址映射机构==

它同样是在纯分页地址变换机构的基础上发展形成的 相较于基本分页，请求分页（发生缺页中断时）的新增步骤 1. 请求调页（页表项P = 0时） 2. 页面置换（需要调入页面到内存，但是没有空闲内存） 3. 执行完请求分页后，需要修改页表中新增的表项

  • 检测是否越界中断（页号）
  • 检索快表-访问内存
  • 检索快表-检索页表（快表中没有，访问完后写入快表中）-访问内存
  • 检索快表-检索页表-缺页中断，调页（页不在内存中，后修改页表，快表）-访问内存
    • 缺页中断后得到一切需要的，不需要再访问快表、页表
    • 缺页中断换入换出——联系：页面置换算法，内存分配策略 ![[Pasted image 20231011102530.png]] PS：

  • 只有“写指令”才需要更改修改位M；

  • 缺页中断处理仍然需要保留CPU现场

  • 需要用某种“页面置换算法”来决定一个换出页面

  • 页面调入到内存中时，需要修改慢表，同时更新快表

(2)实现请求分页的软件

用于实现请求调页的软件和实现页面置换的软件

页面是否在内存——状态位P，页面是否被修改——修改位M ~![[Pasted image 20231009092623.png]]

4.6.2 内存分配策略和分配算法

1.最小物理块数的确定

取决于指令格式，功能，寻址方式

![[Pasted image 20231011103453.png]]

2.物理块的分配策略

驻留集：指请求分页存储管理中给进程分配的物理块的集合 - 采用虚存技术的系统中，驻留集的大小一般小于进程的总大小 - 驻留集太小：导致缺页频繁 - 驻留集太大：导致多道程序并发性下降，资源利用率降低 另： 工作集

分配策略：固定分配局部置换，可变分配局部置换，可变分配全局置换

![[Pasted image 20231011103520.png]]

![[Pasted image 20231011194707.png]]

3.物理块分配算法

平均分配算法，按比例分配算法，考虑优先权的分配算法

![[Pasted image 20231011103601.png]]

![[Pasted image 20231011103620.png]]

![[Pasted image 20231011103632.png]]

4.6.3 页面调入策略

主要问题： 1. 何时调入 2. 何处调入 3. 如何调入 目标： 页面的换出、换入需要磁盘I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

1.何时调入页面

预调页策略，请求调页策略

![[Pasted image 20231011104711.png]]

2.何处调入页面

  • 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。==对换区的磁盘I/O速度比文件区的高==

  • 每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况

    (1)系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。在进程运行前,文件由文件区->对换区。 ![[Pasted image 20231011195607.png]] (2)系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入。凡是会被修改的文件,都直接从对换区调入。 ![[Pasted image 20231011195655.png]] (3)==UNIX方式。==开始时,由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都应从文件区调入。换出到对换区,以后再调入就从对换区调入。 ![[Pasted image 20231011195739.png]]

3.如何调入页面

三种判断：缺页中断（状态位P）-页面置换-写回磁盘（修改位M）

![[Pasted image 20231011104302.png]]

4.7 页面置换算法

使用到的页表项：访问位A（记录访问次数）

4.7.1 最佳置换算法和先进先出置换算法

最佳置换算法(预知未来)：

其所选择的被淘汰页面,将是以后永不使用的, 或许是在(未来)最长时间内不再被访问的页面 - 理论上的算法（不能百分百的预知未来），无法实现

需要调入页面2时：内存已满（0,1,7），未来最长时间不再被访问的是页面7，因此淘汰页面7，调入页面2 ![[Pasted image 20231011154825.png]] ![[Pasted image 20231011155206.png]]

先进先出(FIFO)页面置换算法

每次选择淘汰的页面是最早进入内存的页面，实质上是淘汰在内存驻留时间最长（或最久未使用/未访问） 的页。（==算法性能差==）

实现方法：使用队列 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块

页面3最早进入内存，淘汰页面3 ==方法：”内存块“这几行往前数（重复页面从何处开始），选最前面的== ![[Pasted image 20231011160654.png]] 缺页次数：9 ![[Pasted image 20231011161424.png]] Belady异常：使用FIFO时，分配的内存块增大时，缺页次数不减反增的异常现象

4.7.2 最近最久未使用(LRU)置换算法

当需要置换一页时,选择在最近一段时间最久未使用（借助访问字段A） 的页面予以淘汰。 性能最好，但实现困难，开销大（需要硬件支持）

==方法：逆向检查”访问页面号“，看此时在内存中的机构页面号（就近），选当前内存中最前面的== ![[Pasted image 20231011162203.png]]

4.7.3 CLOCK置换算法

1.简单的Clock置换算法

引入:LRU算法有较多的硬件支持,成本高

具体实现： - 当采用简单的Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列 - 当某页被访问时,其访问位被置 1 - 置换算法在选择一页淘汰时,只需检查页的访问位A - 如果是1，则将它置0，暂不换出，继续检查下一个页面 - 若第一轮扫描中所有页面都是1，则将这些页面地访问位依次置0后，再进行第二轮扫描（一定能找到） - 简单的clock算法选择一个淘汰页面最多会经过两轮扫描

![[Pasted image 20231011164605.png]]

![[Pasted image 20231011190601.png]] 经过一轮扫描后 ![[Pasted image 20231011190703.png]] ![[Pasted image 20231011190726.png]]

由于该算法是循环地检查各页面的访问情况,故称为Clock算法,又称为最近未用算法NRU(Not Recently Used)

![[Pasted image 20231011164338.png]]

2.改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面(即最多进行4轮查找)

  • 1类(A=0,M=0):表示该页最近既未被访问,又未被修改,是最佳淘汰页

  • 2类(A=0,M=1):表示该页最近未被访问,但已被修改,并不是很好的淘汰页

  • 3类(A=1,M=0):最近已被访问,但未被修改,该页有可能再被访问

  • 4类(A=1,M=1):最近已被访问且被修改,该页可能再被访问

    ![[Pasted image 20231011164525.png]]

![[Pasted image 20231011193345.png]]

4.7.4 其它置换算法

![[Pasted image 20231012220520.png]]

![[Pasted image 20231012220600.png]]

![[Pasted image 20231012220617.png]] ![[Pasted image 20231012220627.png]]

4.8 请求分段存储管理方式

第五章 设备管理

image-20231215113309164

5.1 I/O设备

5.1.1 I/O设备的类型

（1)按传输速率分类

低速设备 - 每秒几个字节至数百字节 - 键盘、鼠标、语音输入输出设备等

中速设备 - 每秒数千至数万字节 - 行式打印机、激光打印机等

高速设备 - 每秒数百K至数十M字节 - 磁盘机、磁带机、光盘机等

(2)按信息交换的单位分类

块设备(Block Device)

  • 信息的存取总是以数据块为单位
  • 基本特征是其传输速率较高,通常每秒钟为几兆位
  • 可寻址,即对它可随机地读/写任一块
  • 属于有结构设备
  • 磁盘的I/O常采用DMA方式,每个盘块的大小为512B~4KB

字符设备(Character Device)

  • 基本单位是字符
  • 基本特征是其传输速率较低,通常每秒钟为几个字节到数千字节
  • 不可寻址
  • 属于无结构设备
  • 通常采用中断驱动方式
  • 例:交互式终端、打印机

(3)按设备的共享属性分类

独占设备(临界资源 )

  • 如打印机

共享设备

  • 可供多个进程同时访问,如磁盘
  • 共享设备必须是可寻址的和可随机访问的设备。

虚拟设备

  • 通过虚拟技术将一台独占设备变换为若干个逻辑设备,供若干个进程同时使用

(4)按操作(使用)特性分类

存储设备:用来存放各种信息的设备称为存储设备 - 例软盘、磁盘、光盘和磁带等

I/O设备:用来向计算机输入和输出信息的设备 - 如键盘、鼠标、显示器、打印机

在现代计算机系统中有些设备既可以做存储设备,也可以做I/O设备,例如,软盘、硬盘等。

5.1.2 设备控制器

![[Pasted image 20231016083907.png]]

image-20231214212820866

组成：

  1. 设备控制器与处理机的接口 主要作用：用于实现设备控制器与CPU之间的通信 三类信号线：数据线，地址线，控制线

  2. 设备控制器与设备的接口 一个设备控制器可以连接多台设备（见下图右侧） 每个接口中有数据、控制和状态三中类型的信号

  3. I/O逻辑 控制器对设备的控制通过I/O逻辑实现的。包括对收到命令和地址进行译码。

![[Pasted image 20231016085114.png]]

基本功能：

  • 接受和识别命令
  • 数据交换
  • 标识和报告设备的状态
  • 地址识别
  • 数据缓冲
  • 差错控制

5.1.3 I/O通道

  • 是一种特殊处理机（处理的指令有限，仅限于I/O）
  • 引入目的（给CPU减负）、
    • 主要目的是为了建立独立的I/O操作，使有关对I/O操作的组织、管理及其结束处理也独立于CPU
    • CPU向I/O通道发送I/O命令,由通道执行程序
    • 实现内存与外设的交互

与一般处理机的区别： - 指令类型单一，局限于与I/O操作有关的命令（数据传送指令和设备控制指令） - 没有独立的内存，通道与CPU共享内存

通道类型： （1）字节多路通道，以时间片轮转方式共享主通道 （2）数组选择通道 （3）数组多路通道

瓶颈问题（类似“木桶短板”）：对于单通路I/O系统而言，通道的速率限制了I/O设备 image-20231214213131858

解决方案 多通路I/O系统：不增加通道数，增加I/O设备到通道的“通路数” image-20231214213144207

5.1.4 总线系统

image-20231214213259913

在计算机系统中的各部件,如CPU、存储器以及各种I/O设备之间都是通过总线来联系。 1.ISA和EISA总线 2.局部总线(Local Bus)

局部总线是指将多媒体卡、高速网卡、高性能图形板等从ISA总线上卸下来,再通过局部总线控制器直接接到CPU总线上

5.2 I/O控制方式

I/O控制方式意为：支持计算机与各种外部设备交换信息。它通过内存与外部设备间的数据传输实现。

内存与外设的控制方式主要有四种:程序I/O方式（使用轮询的可编程I/O方式）、中断驱动I/O方式（使用中断的可编程I/O方式）、直接存储访问DMA I/O控制方式和I/O通道控制方式。

5.2.1 程序I/O方式（PIO）

程序I/O控制方式也称为“忙—等待”方式,即在一个设备的操作没有完成时,控制程序一直检测设备的状态,直到该操作完成,才能进行下一个操作。==使用轮询的可编程I/O方式==

image-20231214214302957

程序I/0控制方式的步骤

用户输入数据时： （1）处理机向设备管理器发送一条I/O指令，启动设备进行输入 （2）设备输入数据期间，处理机通过 循环执行测试指令 不间断地检测设备状态寄存器的值（状态位为1表示设备还没有准备好） （3）当状态寄存器的值显示设备输入完成时，处理机将数据寄存器中的数据取出，送入内存指定的存储单元，然后启动设备去读取下一个数据

用户进程向设备输出数据时：发出启动命令启动设备输出，并等待输出操作完成

存在问题： 速度慢，忙等（一直询问）,CPU的利用率太低 CPU与I/O设备只能串行工作，不支持多道程序

5.2.2 中断驱动I/O方式

引入中断方式，中断驱动方式，即当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后CPU立即返回继续执行原来的任务；设备控制器接受并识别I/O命令后，设备控制器按命令要求去控制指定的I/O设备,完成后,通过中断向CPU发送一中断信号 在I/O设备输入数据的过程中，无须CPU干预，且每次传送一个字符 每完成一个字节的I/O,控制器便向CPU发一中断,请求CPU中断处理。

“控制信号交流”：1.CPU向设备控制器发出一条启动I/O命令；2.设备控制器向CPU发送一条中断命令。(以字节为单位)

  • 打印机，交互式终端

image-20231214215735543

数据的输入输出步骤：

  1. 要求输入数据的进程把一个启动命令和允许中断位“1”写入相应设备的控制状态寄存器中,从而启动了该设备;
  2. 该进程因等待输入的完成进入睡眠状态。
  3. 当输入完成后,输入设备向CPU发出完成中断请求信号;
  4. 处理机响应中断,处理该中断,并唤醒等待输入完成的进程;
  5. 在以后的某个时期,该程序被调度到后,继续运行。

中断控制方式的特点： (1)中断控制方式比程序直接控制方式提高了CPU的利用率。 (2)每输入输出一个数据都发生中断,传输一次数据需要多次中断,浪费了CPU的处理时间。 (3)I/O以字节为单位 (4)CPU与I/O设备并行操作。

5.2.3 直接存储器访问方式（DMA）

在DMA控制器的作用下,设备和主存之间可以成批地进行数据交换,而不用CPU的干涉。

image-20231214221636663

DMA控制器的组成

  • 主机与DMA控制器的接口
  • DMA控制器与块设备的接口
  • I/O控制逻辑

为了实现在主机与控制器之间成块数据的直接交换, 必须在DMA控制器中设置如下四类寄存器:

  • 命令/状态寄存器CR。用于接收从CPU发来的I/O命令或有关控制信息,或设备的状态。
  • 内存地址寄存器MAR。在输入时,它存放把数据从设备传送到内存的起始目标地址;在输出时,它存放由内存到设备的内存源地址。
  • 数据寄存器DR。用于暂存从设备到内存,或从内存到设备的数据。
  • 数据计数器DC。存放本次CPU要读或写的字(节)数。

DMA工作过程

image-20231214222014933image-20231214222113748

特点：

  • 数据传输的基本单位是数据块(连续)
  • 大大减少中断次数
  • 所传送的数据是从设备直接送入内存的,或者相反
  • 仅在传送一个或多个数据块的开始和结束时才需CPU干预,整块数据的传送是在DMA控制器控制下完成的。
  • I/O数据传输速度快,CPU负担少。
  • 在DMA方式下,数据的传送方向、存放数据的内存始址及传送数据的长度等都由CPU控制。每台设备需要配一个DMA控制器。

5.2.4 I/O通道方式

image-20231214223119223

通道控制方式特点: (1)I/O通道是一种特殊的处理器,它具有执行I/O操作指令的能力。 (2)I/O通道通过执行通道(I/O)程序来控制I/O操作,完成I/O任务。 (3)通道程序是放在内存中的,即通道与CPU共享内存。 (4)CPU、通道、I/O设备三者并行工作。 (5)能传送多个数据块。

通道程序 (1)操作码 规定指令所执行的操作,如读、写、控制等 (2)内存地址 标明字符送入内存或从内存取出的内存首址 (3)计数 本条指令所要读/写的字节数 (4)通道程序结束位P 表示通道程序是否结束,P=1表示结束（一个程序可以处理多条记录） (5)记录结束标志R R=0,表示本指令与下一指令处理同一个记录;R=1表示处理某记录的最后一条指令

image-20231214223238847

5.3 缓冲管理

5.3.1 缓冲的引入

缓冲的作用：

(1) 缓和CPU与I/O设备间速度不匹配的矛盾。 (2) 减少对CPU的中断频率,放宽对CPU中断响应时间的限制。 (3) 解决数据粒度不匹配的问题。 (4) 提高CPU和I/O设备之间的并行性。

对缓冲区的理解 ①缓冲是提高CPU与外设并行程度的一种技术。 ②凡是数据来到速度和离去速度不同的地方都可以使用缓冲区。如CPU与内存之间有高速缓存(Cache Memory),主存与显示器之间有显示缓存,主存与打印机之间有打印缓存等等。 ③缓冲的实现方式有两种:一是,采用硬件缓冲器实现(缓冲寄存器);二是,在==内存==划出一块区域,专门用来存放临时输入输出的数据,这个区域称为缓冲区。 ④根据系统设置缓冲区的个数,将缓冲技术分为:单缓冲、双缓冲、循环（环形）缓冲、缓冲池。 ==操作系统在主存中分配缓冲区==

5.3.2 单缓冲和双缓冲

单缓冲工作示意图 缓冲区的输入和传送是==串行==的 存在“取空”和”放满“的状态，此时不能传送/输入数据

image-20231214224528517

双缓冲工作示意图 两个缓冲区是==并行==的

image-20231214224619317

在双机通信时，为了实现双向数据传输，必须在两台机器中都设置两个缓冲区，一个用作发送缓冲区，另一个用作接收缓冲区。（都是单向的） image-20231214224826350

5.3.3 循环（环形）缓冲

当输入与输出速度基本匹配时,双缓冲能获得较好效果；当速度相差较大时,可引入多个缓冲,组织成循环（环形）缓冲的形式

1. 循环（环形）缓冲的组成

​ a. 多个缓冲区 ​ （1）用于装输入数据的空（白）缓冲区R ​ （2）已装满数据的满缓冲区G ​ （3）计算进程正在使用的现行工作缓冲区C

​ b. 多个指针 ​ （1）指示计算进程下一可用缓冲区Nextg ​ （2）指示输入进程下一可用空（白）缓冲区Nexti ​ （3）指示计算进程正在使用的缓冲区Current

计算进程：  
指针——Current,Nextg
占用的缓冲区——C，G（占用一个装满的缓冲区G作为 当前使用的缓冲区C）
输入进程：
指针：Nexti
占用的缓冲区——R,G（占用R输入，G是装满的）

image-20231214225542000

2.循环（环形）缓冲区的使用 (1)Getbuf过程 为计算进程和输入进程提供缓冲区,并移动指针 (2)Releasebuf过程 当计算进程或输入使用完缓冲区后,调用过程将缓冲区释放

3.进程同步 (1)Nexti指针追赶上Nextg指针 输入进程速度大于计算进程,全部空（白）缓冲区已满,无可用缓冲区,输入进程阻塞 (2)Nextg指针追赶上Nexti指针 计算进程速度大于输入进程,全部缓冲区空,无可用数据,计算进程阻塞

5.3.4 缓冲池（Buffer Pool）

1.缓冲池概念

使多个进程能有效地同时处理I/O,

专用缓冲的利用率不高,因此设置公用缓冲池,其中至少应含有以下三种类型的缓冲区: ①空(闲)缓冲区; ②装满输入数据的缓冲区; ③装满输出数据的缓冲区。

三个队列: (1)空（白）缓冲队列emq。由空（白）缓冲区所链成的队列; (2)输入队列inq。由装满输入数据的缓冲区所链成的队列; (3)输出队列outq。由装满输出数据的缓冲区所链成的队列。

2.缓冲池的工作方式

收容输入，提取输入，收容输出，提取输出

记忆：“收容”——腾出一个==空闲==空间来，“提取”——从“已有的”空间中取

设置四种工作缓冲区：

  • 用于收容输入的收容输入工作缓冲区（hin）
  • 用于提取输入的提取收入工作缓冲区（sin）
  • 用于收容输出的收容输出工作缓冲区（hout）
  • 用于提取输出的提取输出工作缓冲区（sout）

image-20231214230205752

5.4 设备分配

5.4.1 设备分配中的数据结构

==四张表==：设备控制表(DCT), 控制器控制表(COCT), 通道控制表(CHCT), 系统设备表(SDT)

设备-控制器-通道
记录内容：1.本身的特性（使用情况）2.和xxx的连接情况

三者关系：一个通道可以控制多个控制器，每个控制器可以控制多个设备 为了确保CPU设备之间能进行通信，还应该分配相应的控制器和通道

1.设备控制表（DCT）

系统为每个设备配置一张设备控制表，用于记录==该设备的特性==及==I/O控制器连接的情况（指向控制器表的指针）。==

设备队列的队首指针：凡是因为请求该设备而未得到满足的进程，应将其PCB按照一定的策略排成一个设备请求队列，其队首指针指向队首进程PCB

image-20231215095310637

2.控制器控制表（COCT）

每个控制器配置一张表,它反映==控制器的使用状态==以及和==通道的连接状况等（与控制器连接的通道表指针）==。

image-20231215095402921

3.通道控制表（CHCT）

为每个通道配置一张表,它反映==通道的使用状态。== 包含与通道连接的控制器表首址

image-20231215095503799

4.系统设备表（SDT）

它记录已被连接到系统中的所有物理设备的情况,==每个物理设备占一个表目==。整个系统配置一张。 一个表目记录一个设备的信息（包含设备控制表） 设备标识符——物理设备名

image-20231215100209118

设备分配步骤

  • 根据进程请求的物理设备名查找SDT。

  • 根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。

  • 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配 给进程。
  • 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进 程。

缺点：

  • 用户编程时必须使用 “ 物理设备名 ”，底层细节对用户不透明，不方便编程。
  • 若换了一个物理设备，则程序无法运行。
  • 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待。

设备分配步骤改进方法

  • 建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。
  • 某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的 设备类型（逻辑设备名)查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。
  • 如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户 进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。

逻辑设备表的设置问题：

  • 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
  • 每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统

5.4.2 设备分配时应考虑的因素

1. 设备的固有属性

(1)独占性 独占设备是不能同时共用的设备,即在一段时间内,该设备只允许一个进程独占。 (2)共享性 允许多个进程同时共享 (3)可虚拟性 虚拟设备是利用某种技术把独占设备改造成可由多个进程共用的设备。

2. 三种设备对应的分配策略

(1)独占设备 缺点: 设备不能充分利用,防止死锁 (2)共享设备 注意各进程的访问次序进行合理调度 (3)虚拟设备 采用SPOOLing技术将独占设备改造成虚拟的共享设备，并同时分配给多个进程使用

3. 设备分配算法

  • 先来先服务
  • 优先级高者优先

4. 设备分配中的安全性

(1)安全分配方式 每当进程发出I/O请求后,便进入阻塞状态,I/O操作完成后唤醒 摒弃了“请求和保持”条件,不会产生死锁 缺点:进程进展缓慢(可能产生死锁，可以对分配设备进行安全性计算，之后再决定是否分配设备)

(2)不安全分配方式 进程发出I/O请求后仍继续运行 可操作多个设备,推进迅速快

5.4.3 设备独立性（设备无关性）

基本含义是:应用程序==独立==于具体使用的物理设备,即是指用户在编程序时所使用的设备（逻辑设备）与实际设备（物理设备）无关。

在应用程序中,使用逻辑设备名称来请求使用某类设备;而系统在实际执行时,还必须使用物理设备名称 系统须具有将逻辑设备名称转换为某物理设备名称的功能,这非常类似于存储器管理中所介绍的逻辑地址和物理地址的概念

用户在编写程序时，==不会指明"具体由哪个设备来完成任务"==

image-20231215101518326

image-20231215101530608

设备独立性（设备无关性）的优点 (1)设备分配时的灵活性 系统可将该逻辑设备类中的任一台分配给进程使用 所有设备均占用时才阻塞 (2)易于实现I/O重定向 所谓I/O重定向,指用于I/O操作的设备可以更换,而不必变应用程序 如调试程序时输出到屏幕,而实际应用时改为输出到打印机(逻辑设备表中的显示终端改为打印机)

设备独立性（设备无关性）软件 为了实现设备独立性（设备无关性）,必须在设备驱动程序上设置一层软件,称为设备独立性（设备无关性）软件，具体有以下几项： (1)设备驱动程序的统一接口 (2)缓冲管理,即对字符设备和块设备的缓冲区进行有效的管理 (3)差错控制 (4)对独立设备的分配与回收 (5)独立于设备的逻辑数据块

逻辑设备名到物理设备名映射的实现——逻辑设备表(==LUT==) 用于实现将应用程序中的逻辑设备名映射为物理设备名 逻辑设备表的设置问题：

  • 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
  • 每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统

image-20231215102303667

给一个逻辑设备选择一个物理设备后，补充一项LUT表目，逻辑名-物理名-驱动程序入口地址，以及逻辑名-系统设备表指针（指向记录该物理设备的表项位置）

5.4.4 独占设备的分配程序

1.基本的设备分配程序 (1)分配设备 (2)分配控制器 (3)分配通道

单通路：

image-20231215102738829

不考虑设备独立性，不考虑多通路情况的设备分配流程图

image-20231215102814700

物理设备名 -> SDT中的相应表项 -> DCT -> 是否分配设备 -> COCT -> 是否分配控制器 -> CHCT -> 是否分配通道 基本分配程序的问题 (1)进程以物理设备名提出I/O请求,无设备独立性（设备无关性） (2)采用单通路I/O系统结构,容易产生瓶颈 改进方案 (1)增加设备独立性（设备无关性） (2)考虑多通路情况

提出逻辑设备名，由LUT转成物理设备名,随后进入流程

image-20231215103257204

5.4.5 SPOOLing技术

==本质：模拟假脱机操作== image-20231215103444078

SPOOLing系统的组成

image-20231215103840515

输入井和输出井

  • 在==磁盘==上的两个存储空间
  • 输入井模拟脱机输入,暂存输入数据
  • 输出井模拟脱机输出,暂存输出数据

输入缓冲区和输出缓冲区==(内存中)==

  • 用来缓和CPU与磁盘之间的速度的矛盾

输入进程SPi和输出进程SPo

  • 模拟脱机I/O时的==外围控制机==

井管理程序

  • 用于控制作业与磁盘井之间信息的交换。井管理程序控制从输入井读取信息或将信息输出至输出井。

image-20231215115726784

共享打印机

打印机为独占设备,利用SPOOLing技术,可将之改造为共享设备 用户请求打印时,SPOOLing系统处理如下 （1）由输出进程在输出井中为之申请一个空闲磁盘块区, 并将要打印的数据送入其中 （2）输出进程再为用户进程申请一张空白的用户请求打印表,并将用户的打印要求填入其中, 再将该表挂到请求打印队列上

SPOOLing系统的特点

(1)提高了I/O的速度。 原来是对输入和输出设备的操作,现在是对磁盘操作。 (2)将独占设备改造为共享设备。 由于SPOOLing技术把所有用户进程的输出都送入输出井,然后再由输出进程完成打印工作,而输出井在磁盘上,为共享设备。这样SPOOLing技术就把打印机等独占设备改造为共享设备。 (3)实现了虚拟设备功能。 由于SPOOLing技术实现了多个用户进程共同使用打印机这种独占设备的情况,从而实现了把一个设备当成多个设备来使用的情况,即虚拟设备的功能。

同时：付出不少代价 ①占用大量的内存作为外设之间传送信息用的缓冲区,它所用的表格也占用不少内存空间;（==空间换时间==） ②占用大量磁盘空间作为输入井和输出井; ③增加了系统的复杂性。

5.5 设备处理(了解)

5.5.1 设备驱动程序的功能和特点

1.设备驱动程序功能 (1)接收由由与设备无关的软件发来的命令和参数, 并将命令中的抽象要求转换为与设备相关的底层操作序列。 (2)检查用户I/O请求的合法性,了解I/O设备的状态,传递有关参数,设置设备的工作方式 (3)发出I/O命令并检查设备状态 (4)及时响应由控制器或通道发来的中断请求并处理

2.设备驱动程序的特点 (1)驱动程序主要是指在请求I/O的进程与设备控制器之间的一个通信和转换程序 (2)驱动程序与设备控制器和I/O设备的硬件特性紧密相关,因而对不同类型的设备应配置不同的驱动程序 (3)驱动程序与I/O设备所采用的I/O控制方式紧密相关 (4)由于驱动程序与硬件紧密相关,因而其中的一部分必须用汇编语言书写 (5)驱动程序应允许重入。一个正在运行的驱动程序常会再一次调用完成前被再次调用

3.设备处理方式 在不同的操作系统中所采用的设备处理方式并不完全相同。根据在设备处理时是否设置进程,以及设置什么样的进程而把设备处理方式分成以下三类: (1)为每一类设备设置一个进程,专门用于执行这类设备的I/O操作 (2)在整个系统中设置一个I/O进程,专门用于执行系统中所有各类设备的I/O操作 (3)不设置专门的设备处理进程,而只为各类设备设置相应的设备处理程序(模块),供用户进程或系统进程调用

5.5.2 设备驱动程序的处理过程

1.将抽象要求转换为具体要求 设置控制器中的寄存器 2.对服务请求进行校验 若请求的设备不支持本次的I/O请求,认为是非法操作 3.检查设备的状态 检查设备是否空闲或是否就绪 4.传送必要的参数 如数据量、起始地址等 5.启动I/O设备

image-20231215111226770

5.5.3 中断处理程序的处理过程

中断现场保护示意图

image-20231215111237454

中断处理流程

image-20231215111306279

5.6 磁盘存储器管理

5.6.1 磁盘性能简述

image-20231215111345116

image-20231215111400265

1.数据的组织和格式 盘片、盘面、磁道、扇区 扇区有标识符字段和数据字段

2.磁盘的类型 (1)固定头磁盘 这种磁盘在每条磁道上都有一读/写磁头,所有的磁头都被装在一刚性磁臂中。通过这些磁头可访问所有各磁道,并进行并行读/写,有效地提高了磁盘的I/O速度 (2)移动头磁盘 每一个盘面仅配有一个磁头,也被装入磁臂中。为能访问该盘面上的所有磁道,该磁头必须能移动以进行寻道

3.磁盘访问时间 (1)寻道时间Ts 这是指把磁臂(磁头)移动到指定磁道上所经历的时间。该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和,即 Ts=m×n+s

(2)旋转延迟时间Tr 这是指定扇区移动到磁头下面所经历的时间

(3)传输时间Tt 这是指把数据从磁盘读出或向磁盘写入数据所经历的时间。Tt的大小与每次所读/写的字节数b和旋转速度有关

image-20231215111528772

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

image-20231215111549046

磁盘调度算法

1.先来先服务FCFS

根据进程请求访问磁盘的先后次序进行调度

  • 简单、公平,每个进程得到满足
  • 适合请求磁盘进程数目少
例：初始情况下磁头在100号磁道，请求访问的先后顺序是55,58,39,18,90,160,150,38,184,求采用FCFS算法时的磁道访问顺序与磁头移动距离

image-20231214231444655

image-20231214232028133

2.最短寻道时间优先SSTF

每次选择与当前磁头所在磁道距离最近的请求磁道作为下一个被访问的磁道

  • 每次寻道时间最短，但是不能保证平均寻道时间最短（不一定最优）
  • ==有“饥饿”现象==
例：初始情况下磁头在100号磁道，请求访问的先后顺序是55,58,39,18,90,160,150,38,184,求采用SSTF算法时的磁道访问顺序与磁头移动距离

image-20231214232316492

image-20231214232338074

3.扫描算法SCAN(电梯调度算法)

SCAN算法不仅考虑欲访问的磁道与当前磁道的距离,更优先考虑的是磁头当前的移动方向

  • “走到底，再往回走”
  • 可防止进程出现“饥饿”现象
例：初始情况下磁头在100号磁道，向磁道号增加的方向访问。请求访问的先后顺序是55,58,39,18,90,160,150,38,184,求采用电梯调度算法时的磁道访问顺序与磁头移动距离

image-20231214232431738

image-20231214232455250

4.循环扫描算法CSCAN

在SCAN的基础上：规定磁头单向移动，减少刚移过的磁道的等待时间

例：初始情况下磁头在100号磁道，向磁道号增加的方向访问。请求访问的先后顺序是55,58,39,18,90,160,150,38,184,求采用循环扫描算法时的磁道访问顺序与磁头移动距离

image-20231214232824397

image-20231214232849006

5.N-Step-SCAN和FSCAN算法

(1)N-Step-SCAN算法

在以前讲的算法都对于先来和后来的请求同等处理(除FCFS),不好,应该考虑。 N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法,对一个队列处理完后,再处理其他队列

  • 当N=1时，等同于FCFS; 当N足够大时，等同于SCAN

image-20231214233033090

(2)FSCAN算法

FSCAN算法实质上是N步SCAN算法的简化,即FSCAN只将磁盘请求队列分成两个子队列。一个是由当前所有请求磁盘I/O的进程形成的队列,由磁盘调度按SCAN算法进行处理。在扫描期间,将新出现的所有请求磁盘I/O的进程,放入另一个等待处理的请求队列

image-20231214233219377

5.6.3 磁盘高速缓冲

利用内存中的存储空间,来暂存从磁盘中读出的一系列盘块中的信息 高速缓存是一组在逻辑上属于磁盘,而物理上是驻留在内存中的盘块

高速缓存在内存中可分成两种形式 （1）第一种是在内存中开辟一个单独的存储空间来作为磁盘高速缓存,其大小是固定的 （2）第二种是把所有未利用的内存空间变为一个缓冲池,供请求分页系统和磁盘I/O时(作为磁盘高速缓存)共享

2.数据交付方式 数据交付(Data Delivery)是指将磁盘高速缓存中的数据传送给请求者进程 当有进程请求访问某个盘块时,选查看磁盘高速缓存 系统可以采取两种方式,将数据交付给请求进程: (1)数据交付。这是直接将高速缓存中的数据,传送到请求者进程的内存工作区中。 (2)指针交付。只将指向高速缓存中某区域的指针,交付给请求者进程。 后一种方式由于所传送的数据量少,因而节省了数据从磁盘高速缓存存储空间到进程的内存工作区的时间

3.置换算法 将磁盘中的盘块写入高速缓存时,会出现因为高速缓存中已装满盘块而需要将高速缓存中的数据先换出的问题,常用算法有最近最久未使用LRU,最近未用NRU,最少使用LFU等 同时还需考虑以下几点 (1)访问频率 (2)可预见性 (3)数据的一致性 内存中已修改数据要写回磁盘

4.周期性写回磁盘 在LRU算法中,经常被访问的盘块数据可能一直保留在高速缓存中,长期不被写回磁盘(有可能丢数据) 在UNIX系统中专门增设了一个修改(update)程序, 使之在后台运行,该程序周期性地调用一个系统调用SYNC。该调用的主要功能是强制性地将所有在高速缓存中已修改的盘块数据写回磁盘 在MS-DOS中所采用的方法是:只要高速缓存中的某盘块数据被修改,便立即将它写回磁盘,并将这种高速缓存称为“写穿透、高速缓存”(write-through cache)

5.6.4 提高磁盘I/O速度的其它方法

1.提前读(Read-Ahead) 在读当前块的同时,将下一盘块读入缓冲区 2.延迟写 缓冲区中的数据不立即写回磁盘,而挂在队尾 3.优化物理块分布 使文件的物理块集中,减小磁头移动距离 4.虚拟盘 利用内存空间仿真磁盘,又称为RAM盘 虚拟盘与磁盘高速缓存的主要区别: (1)虚拟盘内容完全由用户控制(用户那他当磁盘用) (2)而高速磁盘缓存内容由操作系统OS控制(用户不知道其存在)

第六章 文件管理

image-20231209213737349

6.1 文件与文件系统

1.数据组的三个层次：==数据项，记录与文件==

  • 数据项
  • 最小的逻辑数据单元
  • 分为基本数据项（字段），组合数据项（组项）
  • “型”的组成：数据名+数据结构
  • 记录：一组相关数据项的集合（描述一个对象在某方面的属性）
  • 唯一标识一个记录：关键字（数据项的集合）
  • 文件
  • 最大的逻辑数据单元
  • 基本属性：文件类型，文件长度，文件的物理位置，文件的建立时间

2.文件名和扩展名

扩展名是在文件名后面的若干个附加字符（.后缀名），用于指示文件的类型

3.文件类型的划分

  1. 按用途分类

系统文件，用户文件，库文件

  1. 按文件中的数据的形式分类

源文件，目标文件(.obj)，可执行文件(.exe)

  1. 按存取控制属性分类（允许哪些操作）

只执行文件，只读文件，读写文件

  1. 按组织形式和处理方式分类（是由什么组成的）

普通文件，目录文件，特殊文件

文件系统的层次结构

对象及其属性

  • 文件、目录、磁盘存储空间

对对象进行操纵和管理的软件集合（文件系统的功能）

  • 管理文件存储空间
  • 管理文件目录
  • 文件读写管理
  • 文件的共享与保护
  • 文件逻辑地址与物理地址的转换基址

文件系统提供给用户的接口

  • 命令接口（用户-文件系统）
  • 程序接口（用户程序-文件系统）

文件操作

创建文件、删除文件、读文件、写文件、设置文件的读写位置

文件的“打开”和“关闭”操作：（P242）

6.2 文件的逻辑结构

从用户角度看到的 “文件“ 属于逻辑结构（文件组织），由一系列的逻辑记录组成（文件的物理结构——怎么存）

文件的逻辑结构的类型

  1. 按文件是否有结构：

有结构文件：即记录式文件，文件的长度以记录条数为单位

  • 按 记录的长度 分为 定长记录 和 不定长记录（类似char和varchar）

无结构文件：即流式文件，文件的长度以字节为单位

  • 如：系统中运行的大量源程序、可执行文件、可函数
  • 访问：利用读、写指针来指出下一个要访问的字符
  • 相当于记录式文件的特例：一个记录仅有一个字符
  1. 按文件的组织方式分类

将有结构文件分为下面三类：

顺序文件

索引文件

索引顺序文件

顺序文件

常见于磁带

索引文件

索引：实际上是定长记录的顺序文件，表项记录 指向记录的指针（或者记录的关键字）

索引顺序文件

类似数据结构分块查找

6.3 外存的组织方式（文件的物理结构）

==对于不同的外存组织方式，将形成不同的文件物理结构==

image-20231208195248764

如同内存分页，磁盘也会被分为若干块，通常磁盘块的大小与内存块、页面的大小相同。 存储在磁盘中的文件逻辑地址空间也会分为若干文件块，文件逻辑地址形式：（逻辑块号，块内地址） image-20231208195815838

1.连续组织方式

为每个文件分配一片连续的磁盘空间（相邻接的盘块） image-20231208195918963

在目录项中的“文件物理地址”字段中记录： 该文件第一条记录所在的盘块号 和 文件长度（以盘块为单位） image-20231208200020329

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB） 物理块号 = 起始块号＋ 逻辑块号（偏移量） 还需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度就不合法) 操作系统可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问( 随机访问 )

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
  • 连续组织方式的文件在顺序读/写时的速度最快
  • 顺序访问和随机访问容易

缺点：

  • 产生大量的外碎片，存储空间利用率低
  • 结合紧凑来消除碎片，会产生额外的系统花销
  • 文件不方便扩展

2.链接组织方式

为每个文件分配一片不连续的磁盘空间(盘块)，通过 每个盘块的链接指针 将同属一个文件的多个离散的盘块链接成一个链表

  • 隐式链接（默认情况）
  • 显式链接

隐式链接

在文件目录的每个==目录项==中，都需含有指向链接文件的 ==第一个盘块的指针== 和 ==最后第一盘块的指针==

(目录项)|file1   start    end|---->(add=start)|data1  next|--->|data2   next|--->...--->(add=end)|data_n     null|

image-20231208200853357

操作系统如何实现从文件的逻辑块号到物理块号的映射：

  • 用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB） …

  • 从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置…以此类推。

  • 因此：访问i号逻辑块(0开始)，总共需要i+1次磁盘I/O

采用链接分配（隐式链接方式）的文件，只适用于顺序访问，对于随机访问极其低效（查找不方便） 采用隐式链接方式的文件，方便文件扩展。另外不会有碎片问题，外存利用率高。

一种优化方法：提高检索速度和减少指针所占用的空间：将几个盘块组成一个簇（作为分配的单元），缺点——增大了内部碎片

显式链接

将用于 链接文件各个物理块的指针 显式地 存放在 ==内存== 的 一张链接表中——==文件分配表FAT==，且文件目录项中只需记录文件的起始块号

  • 表存放在==内存==中，而且整个磁盘只设置一张
  • DOS系统采用的是显式链接方式（外存的组织形式）

image-20231208202252437

如何找到 对应文件的链接指针 在表中的位置？ 类似一个进程的创建——PCB（程序控制块），每个文件都有对应的FCB（文件控制块），其中会存放文件在FAT表中链接的起始位置的指针

优点：

  • 支持顺序访问和随机访问
  • 文件的访问效率更高（块号转换过程中不需要访问磁盘）
  • 不会产生外部碎片，也方便文件扩展

问题： 占内存（空间换时间），FAT存放了几乎所有的盘块指针——盘块多，FAT占用内存空间较大 不能支持高效的直接存取，读取一个大文件时，往往要频繁地查找FAT（PS：FAT32支持一个文件最大4GB）

3.索引组织方式

做法：针对每个文件，分配一个索引块（磁盘内），把分配给该文件的所有物理块号（逻辑块号可省略）都记录在该块中，并将指向索引块的指针记录在目录项中

  • 对比 隐式链接：分开存 "下一个" 指针；显式链接：把所有文件的指针都存在内存中的一张表中

image-20231208204656060

image-20231208205028964

  • 支持顺序访问和随机访问
  • 方便文件扩展

4.多级索引组织方式

image-20231208205806770

计算所允许的最大文件长度： 最”大“级索引中存放的 “索引数” * 每个盘块的大小

image-20231208211850611

image-20231208213533382

6.4 文件目录

image-20231208191323795

文件控制块与索引节点

文件控制块是用于描述和控制文件的数据结构。 文件控制块内容包括基本信息类（文件名，文件物理位置，文件逻辑结构，文件物理结构），控制信息类（用户对文件的存取权限），使用信息类（文件建立、修改的时间与日期）。最主要内容是文件名和文件物理地址。 借助FCB中的信息，文件管理程序可以对文件进行各种操作：搜索，创建文件，删除文件，显示目录，修改目录。

文件目录示例：

image-20231208190651145

一个文件对应一个文件控制块（FCB），一个FCB就是一个文件目录项，多个FCB组成文件目录

上述示例的问题：文件目录通常放在磁盘上,当文件很多时,占用大量磁盘空间。 可以将文件信息分为两部分：文件名和文件描述信息。将文件描述信息单独形成一个数据结构，称为索引结点。而在文件目录中的每个目录项,仅包含文件名和指向索引结点的指针。

image-20231208190944611

采用索引节点后：目录项只存放文件名和索引节点指针，可以极大地==减小目录项的长度==。因此每个磁盘块可以存放更多的目录项，检索文件时磁盘I/O的次数少了很多

image-20231208204438282

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息， 包括文件在外存中的存放位置，根据“存放位置”即可找到文件。 存放在磁盘上的索引节点称为磁盘索引节点，调入内存的索引节点称为内存索引节点（信息更多：文件是否被修改，此时有几个进程正在访问）

目录结构的组织

  • 单级目录结构
  • 两级目录结构
  • 多级（树形）目录结构
  • 无环图目录结构
1. 单级目录结构

整个系统只建立一张目录表，每个文件占一个目录项

  • 优点：易于实现，管理简单，能够实现按名存取
  • 缺点：不允许重名，不支持多用户使用（即不支持文件共享）

image-20231208193605124

2.两级目录结构

两级目录分别是主文件目录（MFD）和用户文件目录（UFD） 该结构为每个用户建立一个单独的用户文件目录，由用户所有文件的FCB组成；每个用户目录文件在主文件目录中占一个目录项

  • 提高了检索目录的速度(n+m,n*m)
  • 在不同的用户目录中,可以使用相同的文件名。
  • 不同用户还可使用不同的文件名来访问系统中的同一个共享文件、可实现对文件的保护和保密作用。
  • 两级文件目录虽然解决了不同用户之间文件同名的问题,但同一用户的文件不能同名。

image-20231208194409056

3.多级目录结构（树形目录结构）

image-20231208194754014

为每个进程设置一个“当前目录”,又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行。 把从当前目录开始直到数据文件为止所构成的路径名,称为相对路径名；把从树根开始的路径名称为绝对路径名

6.5 文件存储空间的管理

本质：对磁盘中空闲块的（分配）管理方式

image-20231209194253937

空闲表法和空闲链表法

空闲表法：

1.结构

主要结构为空闲盘块表，每个表项记录连续的空闲磁盘块区域的“第一个空闲的盘块号”和“空闲盘块数”。

如果将盘块号为18,19的盘块分配出去，则表项中的（18,3）改为（19,1）

image-20231209182526114

2.如何分配磁盘块

与内存管理中的动态分区分配很类似，为一个文件分配==连续的存储空间==。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

3.如何回收磁盘块

四种情形：回收区的前后都没有相邻空闲区；回收区的前后都是空闲区；回收区前面是空闲区；回收区后面是空闲区。关键点是注意合并

空闲链表法

image-20231209184618281

空闲盘区：由连续的空闲盘块组成一个空闲盘区

空闲盘块链

1.操作系统保存着链头链尾的指针，适用于离散分配的物理结构

2.如何分配 从链首开始，依次取出盘块分配，并修改链首指针

3.如何回收 回收的盘块依次放入链尾，并修改链尾指针

空闲盘区链

1.适用于离散分配和连续分配

2.如何分配

若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的指针、盘区大小等数据。

3.如何回收

若回收区与某个空闲盘区相邻（地址上），则需要将回收区合并到空闲盘区中；若回收区没有和任何空闲区相邻，则将会收取作为一个单独的空闲盘区挂在链尾

位示图法

用二进制位来对应每个盘块，‘0’代表盘块空闲，‘1’代表盘块已分配。适用于·连续分配和离散分配

image-20231209191806044

image-20231209192112283

image-20231209192131479

成组链接法

==必考题==

约束条件：
（1）空闲盘块号栈永远记第一组信息，就一个栈。(画栈时不要忘了栈顶指针)
（2）每次分配和回收都对栈操作。

空闲盘块号栈:用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块数N，将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈 每一组的第一个盘块号存放下一组含有的盘块数和下一组所有的盘块号

例如：第一组（盘块号201~300）的盘块号记录在空闲盘块号栈中，第一组的盘块数量（100）记录在空闲盘块号栈的第一个盘块中。 第二组（盘块号301~400）的盘块号记录在第一组的第一个盘块中（300）

  • 有的盘块只有“盘块号指向”，有的盘块记录某组的盘块数量、盘块号信息和 存放 下一分组盘块号信息的盘块 的盘块号
  • 每一组的盘块总数N和盘块号记入 前一组的第一个盘块的S.free(0)~S.free(99)
  • 将第一组盘块总数和盘块号记入空闲盘块号栈，最末一组的S.free(0)为“0”,表示空闲盘块链结束

image-20231209192443288

难点：分配/释放空闲盘块后的图

==分配/释放后要改数量==

image-20231209195412440

image-20231209195439052

例题：

image-20231209200520182

是的，有一个释放出来的物理块用来存 “前第一组”的盘块数和盘块号了，但分配时也被“拉上凑数了”，

（1）释放5个块后：

image-20231209202049587

（2）再次分配6个块后

image-20231209202137500

6.6 文件共享与保护

文件共享

文件共享是指一个文件可以被多个授权的用户共同使用，在系统中只保留一份共享文件的备份 需要解决两个问题：一是如何实现共享，二是对各类共享文件的用户进行存取控制。 实现文件共享的方法：（1）绕弯路法 （2）连访法（3）利用基本文件实现文件共享（4）基于索引节点的共享方式（有向无循环图）（5）利用符号链实现文件共享

image-20231209203022071

绕弯路法： 用“”表示一个目录的父目录。 假定当前目录为F(12)*，那么可用*/E/J访问文件J(17)，*/*/C/A访问文件A(9)

F(12)的*：image-20231209205658865

连访法：在相应的目录项之间进行虚线链接 虚线b:用户B的作业F能访问作业E的文件J(17) 虚线a:用户B的作业D能访问用户C的文件A(9) (1)文件说明中加一项“连访”属性,指明物理地址部分是指向文件,还是共享文件的目录表目。 (2)撤销一个表目时,必须判别是否有共享用户还要使用,所以增加“用户计数”一项。

利用基本文件目录实现文件共享：如果一个用户想共享另一个用户的文件,只需在自己的目录文件中增加一个目录项（指向那个文件）,填上他为该文件所起的符号名及该共享文件的唯一标识符即可。

基本文件目录+符号文件目录

image-20231209210123559

基于==索引节点==的共享方式（有向无循环图）

image-20231209213123908

利用符号链实现文件共享：为使B能共享C的一个文件F,可以由系统创建一个LINK类型的新文件,也取名为F,以实现B的目录中与文件F的链接。在新文件中只包含被链接文件F的路径名。

image-20231209213249683

文件保护

1.用户对文件的权限

文件的安全管理，通常是通过设置存取控制表来控制用户对文件的访问

image-20231209213421904

image-20231209213449300

2.文件保护的方法

（1）口令

  • 简便。节省空间。
  • 可靠性差。口令易被窃取。

（2）加密

为防止文件内容泄密,用户在创建文件时对其编码加密,成为密码文件。

  • 合法授权用户得到该文件的密钥后,才可对文件解码解密。
  • 加密方法很多,但都要以牺牲系统效率为代价。

image-20231209215722248

image-20231209220041676

image-20231210121304775

image-20231210121433514

image-20231210121500363

image-20231210121526496

image-20231210121603698

image-20231210121808837

image-20231210121940904

EOS

控制台命令：

ds：测试磁盘调度算法

help：得到各个命令的作用

vm 1: 查看进程PID为1的虚拟地址描述符

pm: 查看物理存储器信息

pt：查看进程线程信息

快捷键

ctrl+(F1~F4）：切换控制台

F5：启动调试(并在断点处中断)

ctrl+F5：开始执行（不管断点了）

shift+F5：终止调试

F9：设置一个断点

F10：逐过程调试（跳过调用函数的定义部分）

F11：逐语句调试（进入调用函数的定义部分）