计算机操作系统复习

第零章 绪论

1. 操作系统是一种规模较大、复杂性高的系统软件。

2. 操作系统做什么？

   1. 为应用程序开发提供平台 2. 为应用程序运行提供支持：提供、资源管理、驱动硬接口件。

3. 操作系统原理/OS设计与实现原理？

   功能、与硬件的接口、算法、数据结构、策略。

4. 操作系统 是如何被装入内存并开始运行的？

   BOOT->LOADER->KERNEL

5. 当你点击word的“存盘”时，你的数据是如何由内存传入磁盘？为什么你给出路径和文件名就可以得到你需要的文件内容？

   打开一个word文档是指把该文档从磁盘调入到内存并显示，文件系统。

6. 你桌面上的时钟每隔一分钟会刷新一次，怎么实现的？

   时钟中断，具体为，PIT(可编程间隔定时器) ---时钟中断---> PIC (可编程中断控制器) ---电信号、时钟中断向量--> CPU ---> 时钟中断处理程序。

7. 对一个大规模矩阵，按行遍历快还是按列遍历更快？为什么？一个应用程序的时间性能可以通过哪些环节的改善得以提高？

   看操作系统，按行优先还是按列优先。

   降低时间复杂度，提高程序的局部性。

8. 网络数据包的发送和接收是如何实现的？

   参考链接：Linux 数据包的接收与发送过程

注：CPU上下文环境是指保证程序能正常运行而需要从内存恢复到CPU中寄存器的值。

磁盘块是指$2^n$个连续扇区，扇区大小一般为512字节。

第一章 操作系统概述

1 什么是操作系统

1、操作系统是用户与计算机硬件之间的接口

屏蔽控制硬件的细节，使应用程序的开发更简单、高效

1.2 接口形式：命令行接口、图形用户接口、系统调用

1.3 文件的存放

1.3.1 逻辑地址和物理地址

逻辑地址：簇号或扇区的逻辑编号。

物理地址：柱面号、磁头号（磁道号）、扇区号。

逻辑地址转为物理地址依赖于文件系统和设备驱动程序。

1.3.2 磁盘读文件的过程

1）用户给出文件名，提出访问文件的请求

2）文件系统通过按名访问机制获取文件的逻辑地址（磁盘块号或扇区编号）[OS完成]

3）磁盘驱动程序将逻辑地址转换为物理地址、发送磁盘操作指令 [OS完成]

2、操作系统是计算机资源的管理者

管理：处理机、内存、设备、文件、网络等。

2.1 操作系统的设计追求的主要目标

1）方便用户（最终用户和程序员）

2）提高系统性能：空间性能、时间性能、资源利用率

2 操作系统的发展

1、无操作系统

定义：第一代计算机（1945-1955）使用电子管作为主要的电子器件，用插件板上的硬连线或穿孔卡表示程序，没有存储程序的内存，无操作系统。

2、单道批处理系统

定义：单道批处理系统内存中只有一道作业，可以成批处理作业。克服CPU因等待人工操作造成的资源浪费问题

特点：①自动性 ②顺序性 ③单道性

优点：减少等待人工操作的时间

缺点： ①作业独占CPU ②CPU等待I/O使得CPU利用率低（相对于多道程序系统而言）

3、多道程序系统

3.1 多道批处理系统

特点：①多道性 ②无序性 ③调度性 ④复杂性

优点：①提高CPU利用率 ②提高内存和I/O利用率 ③增加系统吞吐量

缺点： ①平均周转时间 ②缺乏交互能力

3.2 分时系统

连续的时间片轮流交替使用。

定义：①人机交互 ②共享主机 ③便于用户上机

特点：①多路性 ②独立性 ③及时性 ④交互性

优点：①提供人机交互 ②多终端共享主机

分时系统实现中的关键问题：

①及时接收：及时接收用户的命令或数据

②及时处理：及时处理用户命令。应该使所有的用户作业都直接进入内存；在很短的时间内使每个作业都得到运行。

4、微机操作系统

5、实时操作系统

定义：实时系统是支持实时计算的系统。实时计算可以定义成这样一类计算，既系统的正确性不仅取决于计算的逻辑结果，而且还依赖于产生结果的时间。

特点：①多路性 ②独立性 ③及时性 ④交互性 ⑤可靠性

实时任务的类型 ①周期性实时任务 ②非周期性实时任务 ③硬实时任务 ④软实时任务。

注：一个实际的OS可以同时具有批处理、分时和实时的特点，如Windows NT。

吞吐量是指单位时间内系统处理的作业量/任务量。

事件的开始截止时间，完成截止时间。

作业：在计算机操作系统中，作业(Job)是计算机操作员(或称为作业调度程序的程序)提供给操作系统执行任务的工作单元，一系列程序+数据的集合。

3. 操作系统的特征

并发：两个或多个事件在同一时间间隔内发生。并发强调“同一时间间隔”，与并行是不同的两个概念，并行是指多个事件同时发生。

共享：系统中的资源可供内存中多个并发执行的进程共同使用。 资源共享有两种方式，即：互斥共享和同时共享。

虚拟：通过某种技术把一个物理实体变成若干逻辑上的对应物。

异步：进程以不可预知的顺序、进度运行，系统能处理随机发生的事件。

4 操作系统的功能

内存管理功能、进程管理功能、设备管理功能、文件管理功能、用户接口

1、内存管理功能

内存分配;

内存保护: 确保每道用户程序都在自己的内存空间中运行，互不干扰。

地址映射;

①逻辑地址和物理地址

一个应用程序经编译后，通常会形成若干个目标程序，这些目标程序再经过链接而形成可装入程序。这些程序的地址都是从某一起始地址开始的，程序中的其它地址都是相对于起始地址计算的；由这些地址所形成的地址范围称“地址空间”，其中的地址称为“逻辑地址”。

由内存中的一系列单元所限定的地址范围称为“内存空间”，其中的地址称为“物理地址”。

②地址映射

内存扩充；虚拟内存。

内存回收：程序执行完毕或文件被关闭，系统将程序、文件占用的内存空间标记为空闲状态。

2、进程管理功能

进程控制

进程同步

进程通信

进程调度

3、设备管理功能

缓冲管理：管理各种缓冲区。

设备分配：分配用户I/O 所需要的设备。

设备处理：由设备驱动程序来实现CPU与设备控制器之间的通信。

设备独立性：应用程序与具体的物理设备无关。

虚拟设备：多个用户、多个进程课共享同一个物理设备。

4、文件管理功能

文件的按名访问

文件的存储

5、提供用户接口

命令接口

图形接口：采用图形化的操作界面。

程序接口：由一组系统调用组成。

5 指令的执行

1、取指令与执行指令

1.1 取指令

在每个指令周期开始的时候，处理器从存储器中取一条指令，在典型的处理器中，程序计数器（PC）保存有下一次要取的指令的地址。除非接收到别的指示（如执行跳转指令），否则处理器在每次完成取指令后总是对PC递增，使它能够按顺序取得下一条指令。（即位于下一个高端存储器地址的指令）。

1.2 执行指令

取到的指令被放置在处理器中的指令寄存器（IR中。指令中包含确定处理器将要采取动作的位，处理器解释指令并执行要求的操作，这些操作可分为4类：

①处理器-存储器:数据在存储器和处理器之间传送；

②处理器-I/O：数据在I/O设备和处理器之间传送；

③数据处理：算术操作或逻辑操作；

④控制：修改指令的执行顺序。

2、内部CPU寄存器

程序计数器（PC）----存指令地址

指令寄存器（IR) ----存正在执行的指令

累加器（AC) ----临时存储体和累加操作

6 小结

1. 程序执行的过程是反复取指令和执行指令的过程；
2. PC始终存有下一条待取指令的地址；
3. 指令执行的结果就是使寄存器或内存单元的值发生变化。指令执行的过程也就是存储体内容不断变化的过程。
4. 取指令和执行指令是由硬件完成的。
5. 不同硬件的体系结构支持不同的指令集合，为某种硬件平台开发的操作系统不能直接在另一种体系结构的硬件上运行。
6. 任何高级语言程序被编译成指令集合，其中的每一条指令属于机器体系结构指令集。CPU执行的最小程序单位是指令而不是高级语言程序的语句。
7. 操作系统是一组控制和管理计算机硬件和软件资源、合理地对各类作业进行调度以及方便用户的程序集合。
8. 说明逻辑地址对于程序的自动执行而言有什么意义？逻辑地址的存在使得编译器能够忽略不同操作系统和硬件的差异并且只针对统一的编址空间执行优化。

9. 以printf的执行为例说明操作系统提供了应用程序开发的方便性、操作系统屏蔽了硬件细节的作用。

   封装调用系统调用，sys_print()系统调用并返回。

10. 请简要说明操作系统为应用程序的执行做了哪些工作？

    操作系统到外存查找可执行文件

    操作系统分配内存，将程序装入内存

    为执行hello程序创建执行环境（创建新进程）

    操作系统设置CPU上下文环境，并跳到程序开始处

    程序的第一条指令执行

    程序执行与printf对应的库函数、系统调用

    执行显示驱动程序

    将像素写入存储映像区(显存）

11. 操作系统具有哪些特征？什么是并发？什么是共享？它们有什么关系？

    并发性（Concurrence）

    并行性和并发性是既相似又有区别的两个概念。并行性是指两个或多个事件在同一时刻发生，而并发性是指两个或多个在同一时间间隔内发生。在多道程序环境下，并发性是指宏观上在一段时间内有多道程序在同时执行。但在单处理机系统中，每一个时刻CPU仅能执行一道程序，故微观上，这些程序是在CPU上交互执行。

    共享性（Sharing）

    共享是指系统中的所有资源不再为一个程序所独占，而是供同时存在于系统中的多道程序所共同使用。根据资源属性不同，可有互斥共享和同时共享两种不同的共享方式。
    并发和共享关系：

    并发和共享是操作系统的两个最基本的特性，它们又是互为存在条件。一方面资源共享是以程序（进程）的并发性执行为条件的，若系统不允许程序并发执行，自然不存在资源共享问题。另一方面若系统不能对资源共享实施有效管理，则也必将影响到程序并发执行。

第二章 进程的描述与控制

1 程序的并发运行

1 概念

在同一时间间隔内运行多个程序，一个程序还没有执行完，可以运行其它的程序，对用户而言，看到的是计算机同时运行多个程序。

程序并发执行的方式可以是多个程序分时使用多CPU或单CPU。

2 特点

①间断性 ②多个程序共享系统资源（失去封闭性）③不可再现性

2 进程的描述

进程概念的引入是为了跟踪并描述程序的并发执行。当允许程序并发执行时，并发执行的程序可能是同一个程序在不同数据集合上的执行，也可能是不同的程序在不同数据集合上的执行，它们共享系统资源，用程序已不能方便地描述程序的并发执行，所以引入了进程的概念 。

1 进程的定义

定义1：进程是允许并发执行的程序在某个数据集合上的执行过程。

定义2：进程是由用户数据、系统数据和程序构成的实体。

2 进程的特征

并发性：多个进程实体，同存于内存中，能在一 段时间内同时运行。

动态性：进程是进程实体的执行过程，对应了存储体的不断变化；有创建、执行、状态变化和运行终止被撤消的过程

独立性：独立运行和资源调度的基本单位。

异步性：以不同的、不可预知的速度向前推进。

结构特征：进程包括用户数据、程序、系统数据。

3 进程与程序的比较

区别 ：

①程序是静态的概念，进程是动态的概念

②程序是永久的，进程是暂时存在的

③程序与进程的存在实体不同

联系 ：

①进程是程序的一次执行，进程总是对应一个特定的程序，执行程序的代码，一个进程必然对应至少一段程序。

②一个程序可以对应多个进程。同一个程序段可以在不同的数据集合上运行，因而构成若干个不同的进程。

4 程序控制块

进程控制块是进程实体的一部分，与进程一一对应，是操作系统中最重要的记录型数据结构，PCB中记录了操作系统所需要的用于描述进程情况及控制进程运行所需的全部信息，只有内核程序可以直接访问。

4.1 进程控制块中的信息

1） 进程标识符信息

① 外部标识符 ② 内部标识符 ③ 父进程标识符 ④子进程标识符

2）处理机状态信息

①通用寄存器 ②指令计数器 ③程序状态字PSW ④用户栈指针

3）进程调度信息
①进程状态信息 ②进程优先级 ③进程调度所需要的其他信息 ④事件

4）进程控制信息
①程序和数据的地址 ②进程同步和通信机制 ③资源清单 ④链接指针

3 Linux的进程控制块

Linux PCB大小为8KB

4 进程控制

1、进程的基本状态

1.1 进程的三种基本状态

就绪状态：进程一但获得CPU就可以投入运行的状态。

执行状态：进程获得CPU正在运行的状态。

阻塞状态：进程由于等待资源或某个事件的发生而暂停执行的状态。

1.2 进程状态的转换

进程状态转换

1.3 进程的组织

​ 当系统中有很多进程时，可以用队列把进程控制块组织起来，形成进程队列。把具有相同状态的进程放在同一个队列中，具有不同状态的进程就可形成不同的进程队列。处于就绪状态的进程构成的进程队列称为就绪队列，处于阻塞状态的进程构成的进程队列称为阻塞队列。

1.4 链接方式

​ 把具有相同状态的PCB用其中的链接字，链接成一个队列。就绪队列、执行队列和阻塞队列。

​ 进程链表，循环队列

​ Pidhash表及链表 参考：Linux内核探秘——进程（二）

​ 进程树

​ 结构数组

2、进程的创建

2.1 引起创建进程的事件：① 用户登录 ② 作业调度③ 提供服务④ 应用请求

2.2 进程创建 调用创建新进程的原语来创建进程，一般步骤为： ① 申请空白PCB② 为新进程分配资源③ 初始化进程控制块 ④ 将新进程插入就绪队列

3、进程阻塞

3.1 引起进程阻塞和唤醒的事件①请求系统服务，如：打印服务。②启动某种操作，如：启动I/O或启动打印机。③ 新数据尚未到达，如：一个计算进程，如果新的输入 数据还没有到达，则计算进程需要阻塞等待。

3.2 进程阻塞的简化过程①暂停进程的执行，将进程的状态改为阻塞态。②将进程插入相应的阻塞队列。③转进程调度程序，重新进行进程调度。

4、进程唤醒

4.1 进程唤醒过程 ①将进程从阻塞队列中移出 ②将进程状态由阻塞改为就绪 ③将进程插入就绪队列

5、进程的终止

5.1 引起进程终止的事件①正常结束②异常结束③外界干预

5.2 进程终止过程 ①从进程PCB中读进程状态②若进程正在执行则终止进程的执行③若进程有子孙进程则终止子孙进程*(不一定）④释放资源 ⑤将终止进程的PCB“移”出

注：系统引导过程：

执行BIOS程序将BOOT程序加载入内存

执行BOOT程序，从外存找到Loader程序，将其加载入内存，并执行该程序

Loader程序将内核程序从外存加载入内存

内核开始执行

5 操作系统内核

1、中断

中断是改变处理器执行指令顺序的一种事件。这样的事件与CPU芯片内外部 硬件电路产生的电信号相对应 。

计算机在执行程序的过程中，当出现中断时，计算机停止现行程序的运行，转向对这些中断事件的处理，处理结束后再返回到现行程序的间断处。

引入中断机制能有效提高CPU的利用率，改善系统性能。

为什么引入中断？引入中断机制后，CPU可以与其它设备并行工作，能有效提高CPU的利用率，改善系统性能，支持系统的异步性。

1.1 中断类型

内部中断和外部中断

1.2 中断响应

响应外部中断的条件:开中断

响应外部中断的时机:CPU每执行完一条指令

内部中断：随时可能产生

1.3 单重中断的执行

单重中断的执行

注：现在的计算机系统大多允许中断嵌套，在这样的系统中，保护完现场后就可以打开中断，允许响应新的中断。

1.4 如何找到中断服务程序？

不同中断源对应不同的中断向量

根据中断向量查找中断向量表

从中断向量表中读取中断服务程序的入口地址相关信息

中断服务程序的入口地址相关信息在内存中的地址=idtr中的地址+中断向量表表项的长度×中断向量的值，idtr中的地址即为中断向量表的起始地址。

1.5 关于中断OS要做的事情

初始化中断向量表

初始化中断向量表寄存器（idtr寄存器）

执行中断处理程序

1.6 需要了解的硬件：

不同中断源对应的中断向量值

可编程中断控制器接口（PIC 可编程中断控制器）

与中断相关的寄存器名称及其用途

2、时钟管理

2.1 时钟的重要性

定时测量

编译程序

防止进程垄断CPU或其他资源(CPU时间片)

与时钟相关的软件需要时钟支持

2.2 计算机系统中的时钟

大部分PC机中有两个时钟源，分别叫做RTC和OS时钟。

RTC时钟也叫CMOS时钟，是一块时钟芯片，靠电池供电，为计算机提供计时标准，是最原始、最底层的数据。

OS时钟产生于PC主板上的定时/计数芯片，在开机时有效。

时钟运作机制

2.3 操作系统的时钟机制

2.3.1 操作系统内核需要完成的定时测量功能：

1.保存当前的日期和时间；2.维持定时器。

2.3.2 如何实现？

1.操作系统依靠时钟硬件（可编程间隔定时器）2.时钟软件（时钟驱动程序）

2.3.3 OS时钟硬件（可编程间隔定时器PIT，Programmable Interval Timer)）

功能：按指定的时间间隔产生时钟中断，测量逝去的时间,并触发与时间有关的操作。

组成：OS时钟由三个元件组成：晶振、计数器、保持寄存器。

PIT

image-20220608114949661

2.3.4 时钟软件（时钟驱动程序）

时钟驱动程序做的几件事：

①维护日期、时间 ②递减时间片并检查是否为零，防止进程运行超时 ③对 CPU的使用情况记帐 ④递减报警计数器

3、系统调用

系统调用是一群预先定义好的模块,它们提供一条管道让应用程序或一般用户能由此得到核心程序的服务。系统调用是核心程序与用户程序之间的接口，在类UNIX系统中，系统调用多使用C语言所提供的函数库接口。如：在程序中，使用C的函数printf( )。

3.1 系统调用与一般函数的区别

系统调用实现例程运行在系统态（核心态）而一般函数运行在用户态。

系统调用与一般函数调用的执行过程是不同的。当系统调用执行时，当前进程被中断，由系统找相应的系统调实现例程，并在系统态下执行，执行结果返回进程。

系统调用要进行“中断处理”比一般函数调用多了一些系统开销。

注：CPU内核态和用户态

（1）内核态执行

内核空间是指含有一切系统核心代码的地址空间，当CPU执行系统核心代码时，称进程处于内核态执行，CPU状态为内核态。

（2）用户态执行

用户空间是指用户进程所处的地址空间，当CPU执行用户空间的代码时，称该进程在用户态执行。CPU状态为用户态

0x 0000_0000 ~ 0x BFFF_FFFF 用户空间 3GB

0x C000_0000 ~ 0x FFFF_FFFF 内核空间 1GB

3.2 Linux系统调用的实现

system_call()

系统调用号:与系统调用一一对应的整数

系统调用表:存系统调用实现例程起始地址的数据结构 ，由系统在初始化时建立。在Linux2.4.18和Linux2.6.11中这个表是sys_call_table数组，有NR_syscalls个表项（通常是256个,在linux2.6.11中是289）：第n个表项包含系统调用号为n的服务例程的地址。

系统调用实现例程

TODO ：类似于外设的控制

int 0x80
sysenter 都可以完成从用户态到内核态的切换

image-20220608140516278

3.3 系统调用的类型

进程控制类系统调用:创建、撤消进程；获得、改变进程属性；

文件操纵系统调用：创建、删除、打开、关闭、读、写文件；

设备管理系统调用：请求、释放设备；

通信用系统调用：打开、关闭连接、交换信息；

信息维护：返回系统当前日期、时间、版本号、用户数、空闲内存、磁盘空间大小。

3.4 Linux中的系统调用举例

fork创建一个新进程 clone按指定条件创建子进程 execve运行可执行文件 exit中止进程

open打开文件 creat创建新文件 close关闭文件描述字 read读文件 write写文件

3.5 操作系统提供系统调用的优点

使编程更加容易，把用户从学习硬件设备的低级编程特性中解放出来；

提高了系统的安全性。

4、线程

线程是进程中的一个实体，是被系统独立调度和分派的基本单位。线程只拥有在运行中必需的资源，包括程序计数器、一组寄存器和栈，但它可以与同属一个进程的其他线程共享进程的全部资源，如：虚拟地址空间、文件。

注：进程作为拥有资源的基本单位。

4.1 进程与线程的关系

进程于线程的关系

4.2 线程的三种基本状态

就绪，运行，阻塞三种状态（同进程的三种基本状态）

4.3 线程控制块TCB

线程控制块

每个线程都由一个数据结构表示，包括它的基本状态、标识以及记账信息。

线程控制块中的信息

①线程标识符信息 ②处理机状态信息 ③线程调度信息 ④线程控制信息

4.4 线程控制块的组织方式

正在执行队列、就绪队列和阻塞队列。

4.5 线程与进程的关系

①资源和调度 ②地址空间资源 ③通信关系 ④并发性 ⑤系统开销

TODO ：查询进程和线程之间的关系。

4.6 线程的控制

(1) 线程的创建 (2) 线程的终止 (3) 线程的调度 (4) 线程的阻塞与唤醒 (5)线程的同步

4.7 线程实现的模型

多对一模型、一对一模型、多对多模型

参考：

系统线程（内核线程）和用户线程区别

用户态线程和内核态线程有什么区别？

内核线程与用户线程区别、同步互斥的实现原理——详解

用户线程、内核线程对应关系的三种模型

TODO：查询内核线程和用户线程之间的关系。

注：批处理系统可以分为单道批处理系统和多道批处理系统。批处理是指用户将一批作业提交给操作系统后就不再干预,由操作系统控制它们自动运行。

进程存在的标志是（进程控制块PCB）。

1、什么是操作系统内核﹖操作系统内核主要完成什么功能?

操作系统内核是计算机硬件的第一次扩充，内核执行OS与硬件关系密切，执行频率高的模块，常驻内存。

不同的OS内核包括的功能不同，多数OS内核包括下述功能:

支撑功能:

中断处理、时钟管理、原语操作

资源管理功能:

进程管理、存储器管理、设备管理

2、操作系统在什么时候创建进程﹖操作系统如何创建一个进程﹖举例说明操作系统创建进程的过程和进程执行的功能。(理解)

引起创建进程的事件

1、用户登录2、作业调度 3、提供服务4、应用请求。

调用创建新进程的原语来创建进程，一般步骤为:

1、申请空白PCB。2、为新进程分配资源。3、初始化进程控制块。4、将新进程插入就绪队列。

6 问题

1、什么是系统态和用户态？

用户态执行：用户空间是指用户进程所处的地址空间，当一个进程在用户空间执行时，称该进程在用户态执行。
系统态执行：系统核心空间是指含有一切系统核心代码的地址空间，当进程处于具有执行系统核心代码的权力之状态时，称为进程处于系统态执行。

2、什么是系统调用？系统调用与库函数有什么区别？简要说明系统调用的执行过程。

答：系统调用是一群预先定义好的模块,它们提供一条管道让应用程序或一般用户能由此得到操作系统核心程序的服务。

系统调用与库函数的区别：

系统调用运行在系统态（核心态）而一般函数运行在用户态。

系统调用与一般函数调用的执行过程不同。

系统调用要进行“中断处理”比一般函数调用多了系统开销

系统调用的执行过程如下：

1）保存系统调用号；

2）执行陷入指令；

3）执行与陷入指令相关的处理程序；

4）以系统调用号为索引，在系统调用表中找到系统调用实现例程的起始地址；

5）执行系统调用例程，返回用户态。

第三章 进程同步

1、为什么需要同步机制？

因为现代操作系统既要支持多进程（多线程）的并发执行，又要保证并发执行的程序结果是可再现的。

2、在多道程序环境下，进程之间可能存在两种关系：

1.资源共享 2.相互合作

进程同步的任务就是：

1.在资源共享的情况下：保证诸进程以互斥的方式访问临界资源—必须以互斥方 式访问的共享资源；

2.在相互合作的关系中：进程同步的主要任务是保证相互合作的诸进程在执行次序上协调，（有些教材把这种功能称做“同步”）。相互合作的进程可能同时存在资源共享的关系。

1 临界资源

1、临界资源的定义

临界资源：以互斥方式访问的共享资源叫做临界资源。

临界区：每个进程中访问临界资源的那段代码称为临界区。

进入区：检查是否可以进入临界区并对临界区“加锁”的代码。

退出区：释放临界区访问权的代码。、

P
｛… …
    进入区
    CS
    退出区
    … …
｝

2、同步机制应遵循的准则

控制临界资源访问权的控制算法在设计上应遵循的原则 :

1.空闲让进 2. 忙则等待 3. 有限等待 4. 让权等待

2 信号量机制

​ 在信号量机制中，用某种类型的变量-信号量的取值来表示资源的使用状况，或某种事件是否发生，以此为基础实现进程的同步。我们将介绍整型信号量机制、记录型信号量机制、AND型信号量机制。

1、整型信号量

​ 整型信号量是表示共享资源状态且只能由特殊操作改变的整型量。（其值好比信号灯的颜色）

​ 信号量是一种数据结构（可以是整型数、整型数组、链表、记录型变量（结构体））。信号量的值与相应资源的使用情况有关。信号量的值仅由P、V操作改变。

​ 思路：定义一个整型变量，用整型变量值标记资源使用情况：如整型量>0,说明有可用资源；整型量≤0说明资源忙，进程必须等待。对于一次只允许一个进程访问的CS，可定义一个用于互斥的整型信号量，并被初始化为1。

​ 整型信号量的wait和signal操作

​ wait(s)和signal(s)是原子操作（最基本、最小的、中间不允许插入任何中断的操作。要执行就要执行完），只要信号量s≤0就不断测试，不满足让权等待。

var s:integer;        //s为整型信号量
wait(s){            //用于申请资源
    while s≤0 do no-op;
    s=s-1;
}

signal(s){          //用于释放资源
    s=s+1;
}

整型信号量应用举例：

用整型信号量实现进程互斥

思路：为必须互斥访问的CS定义一个互斥信号量mutex，初始值为1。然后，将CS放在wait(mutex)和signal(mutex)之间，当CS可访问时，wait(mutex)才能正常结束使进程进入临界区。

伪代码：

P1:
{   …
     wait(mutex);
     counter=counter+1;
     signal(mutex);
     …
}
P2:
{   …
     wait(mutex);
     counter=counter+1;
     signal(mutex);
     …
}

用整型信号量实现进程协调

有p1和p2两个进程，要求p2必须在p1结束后执行，为此可设置一个信号量s，初始值置为0，同步代码如下：

parbegin
  begin p1; signal(s); end
  begin wait(s); p2; end
parend

对整型信号量机制的总结

①整型信号量的值只能由wait和signal操作改变

②==wait和signal 两个操作中对信号量的访问是不能被中断的。==（为什么？）

③原子操作可以通过关中断来实现。（为什么对临界资源的访问不简单地通过关中断来实现？）

④整型信号量机制的实例:Linux中的自旋锁SpinLock

⑤不同的资源对应不同的信号量，并不是系统中所有的资源用同一个信号量表示。

2、记录型信号量

（1）记录型信号量的数据类型

Type  semaphore=record
value:integer        //资源数量
L:list of process   //阻塞队列
end.

（2）记录型信号量的wait(s)和signal（s）操作

procedure wait(s)
    var s:semaphore
        begin
            s.value=s.value-1;
            if s.value<0 then  
                block(s.L)
        end.

procedure signal(s)
    var s:semaphore
        begin
            s.value=s.value+1;
            if s.value<=0 then  
                wakeup(s.L)
        end.

（3）利用记录型信号量实现互斥

var s:semaphore  
s.value=1
begin                
   repeat
       wait(s);
          critical section
       signal(s)
       remainder section
    until false;
end

(4)利用记录型信号量实现“协调”的应用举例

输入进程：从外存读取数据并将数据放入内存缓冲区。

计算进程：从内存缓冲区取数据并对数据进行处理。

输入进程和计算进程共用内存缓冲区，缓冲区最多能容纳2个数据。要求：缓冲区满时，输入进程阻塞；缓冲区空时计算进程阻塞。

试采用记录型信号量机制实现输入进程与计算进程的同步。

解：设置两个信号量 var empty、full:semaphore。
   初始：        empty.value=2, full.value=0
输入进程：
{
    从外存读数据；
    wait(empty).
    往缓冲区中放数据
    signal(full)
}
计算进程：
{
    wait(full)；
    从缓冲读取数据；
    signal(empty)
    处理数据；
}

3 经典同步问题

1、生产者-消费者问题

(1)问题描述

生产者进程生产产品，并将产品提供给消费者进程消费。为使生产者进程和消费者进程能并发执行，在它们之间设置了一个具有n个缓冲区的缓冲池，生产者进程可以将它所生产的产品放入一个缓冲区中，消费者进程可以从一个缓冲区中取得一个产品消费。任意两个进程必须以互斥的方式访问公共缓冲池。当缓冲池空时，消费者进程必须等待；当缓冲池装满产品时，生产者进程必须等待。

(2) 需要解决的问题

①==对缓冲池的互斥访问。==

②对生产者进程、消费者进程的“协调”，即：有产品时才能消费，无产品时，必须先生产后消费；有空间时才能生产，空间满时，必须先消费再生产。

(3)信号量的设置

①一个互斥信号量，==mutex用于实现对公共缓冲池的互斥访问，初值为1。==

②两个同步信号量，分别表示可用资源数。

​ empty：表示空缓冲区数,初值为n

​ full： 表示装有产品的缓冲区数，初值为0，(一个缓冲区中放一个产品）

(4)同步程序

 Producer:                               
 begin                                  
   repeat                                 
   …                                     
   produce an item in nextp;                    
   wait(empty);                             
   wait(mutex);                              
   buffer(in):=nextp;                        
   in:=(in+1)mod n
   signal(mutex);                            
   signal(full)；
 until false;  
 end       
 
 Consumer:
  begin
     repeat
     …
     wait(full);
     wait(mutex);
     nextc:=buffer(out);
     out:=(out+1)mod n;
     signal(mutex);
     signal(empty)；
     consume item in nextc;
     until false; 
     end

(5)说明

①wait 和signal操作成对出现

②wait操作的顺序不能颠倒

③对具有相互合作关系的进程，提供解决问题的模型

2、习题：

TODO

某系统有同属一个进程的两个线程P和Q，共享一个数据区B，假设B区空间足够大。线程P负责周期性检测工作场所的温度，将所测结果送入数据区B。线程Q则每次从数据区B取出一个最新的检测数据进行处理。如果B区中没有检测数据，则线程Q阻塞等待。请回答下列问题：

（1）数据区B应采用什么样的数据结构？栈

（2）用记录型信号量机制实现进程P与Q之间的同步关系。（说明信号量的作用及初值）

解：设置两个信号量 var empty,mutex:semaphore。
   初始：        empty.value=0,mutex.value=1
P进程：
{
    wait(mutex)
    从外存读数据；
    signal(empty)
    signal(mutex)
}
Q进程：
{
    wait(empty)
    wait(mutex)
    从缓冲读取数据；
    处理数据；
    signal(mutex)
}

3、 读者-写者问题

(1)问题描述

D是多个进程共享的数据区，允许多个进程同时读D区中的数据；允许一个进程往D区写数据，有一个进程在D区中执行写操作时，不能有其它任何进程在D区中执行读或写操作。

(2)信号量的设置

①全局量readcount 用于对进入共享区的读进程计数。

②rmutex用于对多个进程共享的变量readcount的互斥访问。

③wmutex用于实现读/写互斥、写/写互斥。

(3)同步程序

解：设置两个信号量 var rmutex,wmutex:semaphore。
   初始：        rmutex.value=1,wmutex.value=1
   变量：var readcount.
   初始：readcount=0
读进程：
{
    wait(rmutex)
    if(readcount==0)
        wait(wmutex);
    readcount++;
    signal(rmutex)
    读数据
    wait(rmutex)
    readcount--;
    if(readcount==0)
        signal(wmutex);
    signal(rmutex)
}
写进程：
{
    wait(wmutex);
    写数据
    signal(wmutex);
}

4 管程

信号量机制的缺陷：每个访问临界资源的进程都必须自备同步操作wait(s)和signal(s)。这就使大量的同步操作分散在各个进程中，这不仅给系统的管理带来麻烦，而且还会因同步操作的使用不当而导致系统出错,因此引入了“管程”的解决方案。

1、管程的定义

管程是描述共享资源的数据结构和在数据结构上的共享资源管理程序的集合。

2、对管程的说明

①管程是可供程序员调用的软件包，一个管程是一个由过程、变量等组成的一个集合，它们组成一个特殊的模块或软件包。进程可以在任何需要的时候调用管程中的过程，但它们不能在管程外的过程中直接访问管程内的变量。

②每次只有一个进程调用管程执行，任一时刻管程中只能有一个活跃进程。若多个进程同时调用一个管程中的过程，只有一个进程得以进入管程，继续运行，其它进程需要等待。

③管程是一种编程语言的构件，所以编译器知道它们很特殊，并可以采用与其他过程调用不同的方法来处理它们。典型的，当一个进程调用管程中的过程时，前几条指令将检查在管程中是否有其他的活跃进程，如果有，调用进程将挂起，直到另一个进程离开管程，如果没有，则调用进程进入管程。

如果P唤醒Q，可能有两种不同的处理方案：

P继续在管程中执行，Q等待；P等待，让Q先执行管程中的代码。

3、条件变量

为了进行并发处理，管程必须包含同步工具,例如：假设一个进程调用了管程，并且当它在管程中时必须被阻塞，直到满足某些条件。这就需要一种机制，使得该进程不仅被阻塞而且能释放这个进程，以便某些别的进程可以进入。以后当条件满足并且管程再次可用时，需要恢复该进程并允许它在阻塞点重新进入管程。管程通过使用条件变量提供同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问。

一个管程过程，可以用在某条件变量上执行wait操作，将调用的进程阻塞并插入该条件的阻塞队列 ，也可以用在条件变量上执行signal操作，唤醒在该条件上阻塞的进程。

4、管程的应用

（1）利用管程解决生产者-消费者问题

type PC=monitor
condition full, empty;
integer count;
procedure enter(item)
      begin
          if count=N then wait(full);
           enter–item;
           count=count+1;
           signal(empty) //唤醒因为队列空而阻塞的进程
       end

procedure remove(item)
      begin
          if count=0 then wait(empty);
           remove–item;
           count=count-1;
           signal(full) //唤醒因为队列满而阻塞的进程
       end
count=0;
end monitor;

Producer:
begin
     repeat
     produce an item in nextp;
     PC.enter(item);
 until false;
 end

 Consumer:
 begin
     repeat
     PC.remove(item);
     consume the item in nextc;
 until false;
 end

（2）利用管程解决哲学家进餐问题

问题描述

有五个哲学家围坐在一个圆桌旁，每两人之间放一只筷子，每个哲学家的行为是思考，感到饥饿，然后用餐。为了能够进餐，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。

代码

    type dining-philosophers=monitor
    var state:array[0..4] of (thinking,hungry,eating);
    var self:array [0..4]  of condition;
    
     procedure entry pickup(i:0..4);
        begin
            state[i]=hungry;
            test(i);
            if state[i]≠eating then self[i].wait;
      end;    

     procedure entry putdown(i:0..4);
     begin
         state[i]=thinking;
         test(i+4 mod 5);
         test(i+1 mod 5);
     end
     
     procedure test(k:0..4);
       begin
           if state[k+4 mod 5] ≠eating
               and state[k]=hungry
               and state[k+1 mod 5] ≠eating
           then begin
               state[k]=eating
               self[k].signal;
           end
        end
    
        begin
            for i:=0 to 4
               do state[i]=thinking;
        end
        
        void philosopher(int i)
       {
            while(true)
           {
                think();
                pickup(i);
                eat();
                putdown(i);
             }
        }

5 进程间通信

image-20220609162852242

6 小结

1、实现进程互斥的基本原理是什么?

记录性信号量机制:在记录性信号机制里面有S .value，记录的是资源的信号的量，通过去验证每次这个值是否大于0，来判断是否让进程来使用此资源，但是，一旦这个值 s.value=1就允许一个进程访问该资源。从而实现了进程的互斥。这种机制用于各个进程对一个资源的共享。

AND型信号的机制:将一个进程中运行过程中的所有需要的资源，都一次性全部分配给进程。待进程使用完成后，在一并的去释放。这是好几个进程对好几个共享资源的一个实现的方法。

管程机制:利用共享数据结构抽想的表示系统的共享资源。把对该共享数据的操作定义为一组过程。进程对共享资源的操作，就是这组过程对共享数据的一个操作。

进程互斥的目的是使进程以互斥的方式访问临界资源，只要能使进程以互斥的方式进入临界区就能够保证进程对临界资源的互斥访问。所以，可以通过在临界区前加进入区代码，在临界区后面加退出区代码来实现进程的互斥。

临界区是每个进程中访问临界资源的那段代码。进入区是检查是否可以进入临界区并对临界区“加锁”的代码。退出区是释放临界区访问权的代码。

2、进程同步机制的任务是什么？

进程同步的主要任务是对多个相关进程在执行次序上进行协调,以使并发执行的诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性。

3、为什么在生产者-消费者问题中wait操作的顺序不能颠倒？

如果生产者和消费者进程都先通过执行等待(互斥)申请公共缓冲池的互斥访问权，然后通过申请资源信号量申请空缓冲区或装满产品的缓冲区，当缓冲池满时，若生产者进程先申请到公共缓冲池的互斥访问权，然后申请空缓冲区，因缓冲池中没有空缓冲区，生产者进程阻塞。消费者进程因无法申请到公共缓冲池的互斥访问权，也会被阻塞.生产者进程等待消费者进程释放空缓冲区，消费者进程等待生产者进程释放公共缓冲池的互斥访问权，进程因互相等待对方释放资源而处于不能执行的僵持状态.

4、为什么对10个不同的临界资源(counter1-counter10)不能只用一个互斥信号量﹖(理解)

若用一个互斥信号量实现对多个临界资源的互斥访问，则会造成资源的浪费，一个进程申请一个资源时，会同时占用其不需要的资源，则其他进程不能访问被锁住却并没有被使用的资源。

故10个不同的临界资源不能只用一个互斥信号量。

5、三个进程P1、P2、P3互斥使用一个包含N（N > 0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。

采用记录型信号量来实现，伪代码如下。

解：设置两个信号量 var mutex,empty,odd,even:semaphore。
   初始：        mutex.value=1,empty=N,odd=0,even=0
P1进程：
{
    wait(empty)
    wait(mutex)
    num = produce()
    signal(mutex)
    if(num%2==0)
        signal(even)
    else
        signal(odd)
}
P2进程：
{
    wait(odd)
    wait(mutex)
    getodd()
    countodd()
    signal(mutex)
    signal(empty)
}
P3进程：
{
    wait(even)
    wait(mutex)
    geteven()
    counteven()
    signal(mutex)
    signal(empty)
}

7 参考

Linux内核自旋锁(spinlock)使用与源码分析

操作系统第三章：进程同步和互斥

8 问题

1、实现进程互斥的基本原理是什么？

进程互斥的目的是使进程以互斥的方式访问临界资源，只要能使进程以互斥的方式进入临界区就能够保证进程对 临界资源的互斥访问。所以，可以通过在临界区前加进入区代码，在临界区后加退出区代码来实现进程的互斥。
进入区检查是否可以进入临界区并对临界区“加锁 ” 。退出区释放临界区访问权。

2、写出记录型信号量wait操作和signal操作的算法描述（说明信号量的数据结构）

Type  semaphore=record
                 Value:integer          资源数量
                 L:list of process       阻塞队列
           end

procedure wait(s)
  var s:semaphore
   begin
      s.value:=s.value-1;
      if s.value<0 then  
            block(s.L)
end.

procedure signal(s)
  var s:semaphore
   begin
      s.value:=s.value+1;
      if s.value<=0 then  
            wakeup(s.L)
end.

第四章 进程调度

调度算法是指：根据系统的资源分配策略所规定的资源分配算法 。本章介绍作业调度算法和进程调度算法。

作业调度：从后备作业队列的多个作业中选择一个作业进入内存的算法

进程调度：从多个就绪进程中选择进程并为其分配CPU的算法

中级调度：内存中不能有太多的进程，把进程从内存移到外存，当内存有足够空间时，再将合适的进程换入内存，等待进程调度。中级调度实际上就是存储器管理中的对调功能。

1 调度类型和模型

根据系统的不同需求，可以采用不同的调度类型组合，从而形成以下几种调度队列模型。

(1)仅有进程调度的调度队列模型。

(2)具有作业调度和进程调度的调度队列模型。

(3)同时具有三级调度的调度队列模型。

2 调度算法

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

面向用户的准则

(1) 周转时间短 (2) 响应时间快 (3) 截止时间的保证

面向系统的准则

(1) 系统吞吐量高 (2) 处理机利用率高

2、调度算法

2.1 先来先服务调度算法

在作业调度中，FCFS就是从后备作业队列中，选择最先进入该队列的作业进行调度。

在进程调度中，FCFS 是选择最先进入就绪队列的进程，为该进程分配CPU。

性能分析

FCFS适合长作业(进程），不利于短作业（进程），作业（进程）等待时间太长。FCFS使短作业的周转时间过长。

FCFS有利于CPU繁忙型作业（进程），如科学计算。不利于I/O繁忙型作业 （进程），如多数的事务处理。

2.2 短作业(进程)优先调度算法

短作业优先(SJF) 的调度算法。

短进程优先(SPF)的调度算法。

算法优点

与FCFS算法相比 ，短作业(进程)算法能有效降低作业（进程）的平均等待时间、平均周转时间和带权平均周转时间、 提高系统的吞吐量。

注：周转时间定义：

周转时间(作业周转时间)指的是从作业被提交给系统开始, 到作业完成为止的这段时间

周转时间包括四部分:

1） 作业在外存后备队列上等待作业调度的时间

2）进程在就绪队列上等待进程调度的时间

3）进程在cpu上执行的时间

4）进程等待I/O操作完成的时间

周转时间=作业完成时间−作业提交时间

平均周转时间=(作业1的周转时间+…+作业n的周转时间)/n

带权周转时间=作业周转时间作业/实际运行时间

平均带权周转时间=(作业1的带权周转时间+…+作业n的带权周转时间)/n

参考：周转时间, 平均周转时间, 带权周转时间

算法的缺陷

对长作业不利，长作业可能长时间得不到调度。

不能保证紧迫作业的及时处理，因为该算法不考虑作业的紧迫程度。

作业长短根据用户的估计而定，故不一定能真正做到短作业优先

习题：

进程p1,p2,p3到达系统的时间分别为0ms，0ms，6ms时刻，它们需要的服务时间分别为16ms，8ms，4ms，若系统采用==短进程优先==的==非抢占式==进程调度算法，从0ms时刻开始进行进程调度，进程的调度顺序是（ ），系统的平均周转时间是（ ）。

进程调度顺序为 P2 --> p3 --> p1

平均周转时间为 (28ms + 8ms + 6ms) / 3 = 14ms

3、优先权调度算法

当使用优先权调度算法进行作业调度时，系统将从后备队列中选择优先权最高的作业调入内存。

当使用优先权调度算法进行进程调度时，系统将CPU分配给就绪队列中优先权最高的进程。

非抢占式(nonpreemptive)调度

进程一但得到处理机，则该进程便一直进行下去直到完成或由于某事件放弃处理机。

抢占式(preemptive)调度

高优先权的进程可以抢占处理机，使正在执行的低优先权进程中断执行。 在 UNIX中广泛采用抢占式。

抢占时机：基于时钟中断的抢占式优先权调度算法、立即抢占的优先权调度算法

3.1 优先权的类型

静态优先权

优先权在创建时确定，在进程的整个运行期间保持不变。决定静态优先权的依据：进程类型、进程对资源的需求、用户要求 。

静态优先权调度算法可能导致无穷阻塞(indefinite blocking)或饥饿(starvation)问题。

动态优先权

进程创建时获得的优先权，随进程的推进而改变。

4、时间片轮转调度算法

在早期的时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片，当时间片用完时，调度程序终止当前进程的执行，并将它送到就绪队列的队尾。

时间片大小的确定

系统对响应时间的要求、就绪队列中进程的数目、系统的处理能力

响应时间T=Nq

N:系统中的进程数；q: 时间片的大小。

1、（进程数一定）当系统要求的响应时间越短，时间片就越短；

2、（响应时间一定）系统允许的最大进程数越多，时间片也越短；

3、 基本命令应该在一个时间片内执行完。

性能评价

时间片轮转调度算法的性能在很大程度上依赖于时间片的大小。如果时间片很大，进程的响应时间无法保证；如果时间片很小，则进程需要经过多次上下文切换和进程调度，增加了CPU在进程切换和进程调度上的开销，影响系统的吞吐量和CPU利用率等方面的性能。

注：时间片的大小通常为 10~100ms。

6、多级队列调度算法

将就绪队列分成多个独立队列，根据进程的某些属性（如内存大小、进程优先权或进程类型），进程会被永久地分配到一个队列。每个队列都有自己的调度算法。不同的队列优先权不同，调度算法也可能不同。

应用举例minix的多级队列调度

image-20220610112558612

7、多级反馈队列调度算法

设多个优先权不同的就绪队列

允许进程在多个不同的就绪队列间移动

要考虑的问题：

就绪队列的数量

根据进程优先权确定进程应该进入哪个就绪队列的算法

用于确定进程何时转移到较高优先权队列的算法

用于确定进程何时转移到较低优先权队列的算法

3 实时系统中的调度

实时系统对处理机操作或者数据流动具有严格的时限制，其进程调度对保证时间要求具有重要作用。

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

(1) 提供必要的调度信息

1.就绪时间。2.开始截止时间和完成截止时间 3.处理时间 4.资源要求 5.优先级

(2)系统处理能力强

1. 单处理机情况下必须满足的限制条件

   $\sum^{m}_{i=1}{\frac{C_i}{P_i}} \le 1 (1\le i \le m)$

2. N个处理机情况下必须满足的限制条件

   $\sum^{m}_{i=1}{\frac{C_i}{P_i}} \le n (1\le i \le m)$

(3)采用抢占式调度机制

1. 基于时钟中断的抢占式优先权调度

   2. 立即抢占的优先权调度

(4)尽可能短的系统延迟

1. 对外部中断的快速响应能力
2. 快速的进程调度与切换’‘

3.2 常用的几种实时调度算法

​ (1)最早截止时间优先EDF(Earliest Deadline First)

​ (2)最低松弛度优先LLF(Least Laxity First)

注：松弛度计算

松弛度(L,Laxity)用来表示一个实时任务的紧迫程度。如果一个任务的完成截止时间为T,当前时刻为Tc ,处理完该任务还需要的时间为Ts ,则松弛度计算式表示为：$L=T- T_c - T_s$

假如一个实时系统中有两个周期性实时任务，A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。
图给出了A和 B截止的时间点。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

注：在t=30时刻，A松弛度降为0，立即抢占。

参考博客：操作系统处理机的调度问题

4 小结

1、引起进程调度的原因有哪些？

正在执行的进程执行完毕；进程阻塞；正在运行的进程时间片用完；在支持抢占式调度的系统中有优先权高的进程到来；中断返回。

(1)正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费 处理机资源。

(2)执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等状态。

(3)执行中进程调用了P 原语操作，从而因资源不足而被阻塞；或调用了v原语操作激活了等待资源的进程 队列。

(4)执行中进程提出I/O请求后被阻塞。

(5)在 分时系统中时间片已经用完。

(6)在执行完 系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行。

以上都是在 可剥夺方式下的引起进程调度的原因。在CPU执行方式是可剥夺时．还有

(7)就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。

2、支持多任务的操作系统为什么需要进程调度功能？

当多个进程并发执行时候，所有的进程会共享cpu。当某一cpu上运行的进程，因为阻塞或者运行结束时而使cpu可以分配给其他进程使时，如何从众多的就绪队列中选择一个进程，将cpu分配给该进程，使系统有效运行。这是多任务操作系统必须要解决的问题。 为了更好的调度程序，设计了一些调度算法，使各个进程够更加协调的工作。

3、进程p1,p2,p3到达系统的时间分别为0ms，9ms，9ms时刻，它们需要的服务时间分别为8ms，16ms，4ms，优先权分别为100，120，140，请说明并计算当系统分别采用短进程优先的进程调度算法和基于优先权的进程调度算法时，进程的调度顺序及系统的平均周转时间。(优先权值越大优先权越低）

短进程优先

P1-p3-p2

平均周转时间=(8ms+4ms+20ms)/3=32/3ms

基于优先级（非抢占式）

p1-p2-p3

平均周转时间=(8ms+16ms+20ms)/3=44/3ms

4、实现时间片轮转调度算法需要哪些特定硬件和软件的支持

答：需要的硬件：可编程间隔定时器、可编程中断控制器。

需要的软件：进程控制块、就绪队列、进程调度程序、时钟中断处理程序。

5、什么是基于优先权的进程调度算法？在基于优先权的进程调度算法中如何为进程给定优先权值？

答：基于优先权的进程调度算法是系统为每个进程都赋予一个优先权，系统将CPU分配给就绪队列中优先权最高的进程。

​ 优先权的类型分为静态优先权和动态优先权。

（1）静态优先权

​ 静态优先权在创建时确定，在进程的整个运行期间保持不变。静态优先权值通常可以根据进程的类型、进程需要的资源数量、用户的要求来设定。

（2）动态优先权

​ 进程创建时被赋予的优先权，随进程的推进或随其等待时间的增加而改变。动态优先权调度算法可以使系统获得更好的调度性能。

第五章 死锁

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

1、产生死锁的原因

(1)进程使用资源顺序

​ ①申请资源

​ ②访问资源

​ ③释放资源

(2)产生死锁原因

​ ①竞争共享资源;

​ ②进程推进顺序不当;

2、产生死锁的必要条件

​ ①互斥条件

​ ②请求和保持条件

​ ③不剥夺条件

​ ④环路等待

2 处理死锁的基本方法

(1)预防死锁

(2)避免死锁

(3)检测死锁

(4)解除死锁：剥夺资源或撤消进程

1、死锁的预防

死锁预防的基本原理是：破环死锁的四个必要条件之一，除互斥条件外。

(1)摒弃：请求和保持“条件”

​ ①实现方法：进程一次性申请整个运行过程中的全部资源，只有申请到全部资源后，方可投入运行，运行期间不再提出资源要求。

​ ②缺点：资源严重浪费，进程延迟运行。

(2)摒弃：“不剥夺”条件

​ ①方法：一个已保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源。

​ ②缺点：实现复杂而且代价高 。

(3)摒弃：“环路等待”

​ ①方法：“规定进程必须按资源排序的秩序依一定顺序申请资源。

②缺点：限制了新设备的增加。系统为资源分配的序号与进程实际使用资源的顺序不同而造成资源浪费。给用户编程带来了麻烦。

3、死锁的避免

(1)安全状态

​ 当系统找到一个进程执行序列，使系统只要按此序列推 进进程时，可以保证进程的资源分配和顺利完成，不会发生死锁，这种状态称安全状态 。

(2)不安全状态举例

​ 设在T0时刻，系统分配资源情况如下，则系统处于不安全状态，因为当系统处于下表所示的状态时，无论进程按什么秩序推进，都无法避免死锁。

(3)安全状态可以向不安全状态转换

​ 系统不按照安全序列分配资源时，则系统可能会由安全状态进入不安全状态。

3 利用银行家算法避免死锁

1、算法的基本思想

一个进程提出请求后先试分配，然后检测本次的分配是否使系统处于安全状态，安全则按试分配方案分配资源，否则不分配。

2、数据结构

①available [i] 当前可分配资源

②max[i,j] 进程需要的最大资源数。

③allocation[i,j] 某时刻已分配给进程的资源数。

④need[i,j] 进程还需要多少资源才能就绪。

3、银行家算法的说明

两个过程：

①进行资源的试分配(对每一次资源请求)。

②对刚给出的分配方案做安全性检测。

检测结果：

若当前的分配方案是安全的，则分配资源。若当前的分配方案是不安全的则令申请资源的进程等待，暂不为它分配资源。

①资源分配算法

image-20220610202325887

②安全性检测算法：

数据结构：work、finish[i]

算法思想：对T时刻的分配方案进行检测，确定是否 存在至少一个安全序列。

image-20220610202347222

4、银行家算法的实例

​ 假设一个系统，有5个进程p0,p1,p2,p3,p4，有3种类 型的资源A,B,C，其中A类资源有10个，B类资源有5个，C类资源有7个。假定在T0时刻，系统资源分配状态如下：

在T0时刻，可以找到一个安全序列<p1,p3,p4,p2,p0>，系统在T0时刻处于安全状态。

若此时进程p1提出资源请求request1=(1,0,2)，则通过银行家算法先进行资源试分配，然后检测试分配后系统在T1时刻的状态是否安全。

5、银行家算法应用情况的说明

​ 银行家算法缺乏实用价值，因为很少有进程能够在运行之前就知道其所需资源的最大值，而且进程数不是固定
的，往往在不断变化，原本可用的资源也可能突然间变成不可用(如磁带机可能会坏掉)

4 题目

1、资源的按需分配策略可以破坏循环等待条件

2、某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是10。

公式：$M=N*(W-1)+1$，M：最小资源数 N：进程数 W：每进程需要同类资源数 本题：3*（4-1）+1=10

3个进程要想不死锁 每个进程都需要4个同类资源，所以只要每个进程都有3个资源 另外一个在给一个额外的资源。 那么3个进程中有一个可以运行。运行完以后 释放资源然后其余的 进程在申请资源就可以了啊 。

第六章 内存管理

1 存储器的层次结构

image-20220610121643231

注：局部性原理

程序执行的局部性原理指出：程序在执行时呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。关于程序执行的局部性原理有以下几个论点：

程序在执行时，除了少部分的转移和过程调用指令以外，在大多数情况下是顺序执行的。

过程调用将会使程序的执行轨迹由一部分内存区域转到另一部分内存区域。但研究表明，在大多数情况下，过程调用的深度都不超过5，这就是说，程序将会在一段时间内，局限在这些过程的范围内运行。

3.程序中存在很多循环结构，它们虽然由少数指令构成，但多次执行。

4.程序中往往包括许多对数据结构的处理，如对数组进行操作，它们往往都局限在很小的范围内。

总的来说，局部性原理表现为时间和空间的局部性：

时间局部性：如果程序中的某条指令一旦执行，则不久后该指令可能再次执行，如果某个数据结构被访问，不久以后该数据结构可能再次被访问。

空间局部性：一旦程序访问了某个单元，在不久之后，其附近的存储单元也将被访问。

具有良好局部性的程序会经常访问相同的数据集合或地址相邻的数据集合。具有良好局部性的程序比局部性差的程序能更好地利用处于高层次的储存器，减少访存时间，因此运行速度更快。

2 程序的装入和链接

在多道程序环境下，程序要运行必须为之创建进程，进程执行过程中，CPU通过访问内存获取其要执行的指令。进程的执行需要操作系统将程序和数据装入内存。将一个用户的源程序变为一个可在内存中执行的程序，通常要经过编译、链接、装入 。

链接要解决的问题：将编译后的目标模块装配成一个可执行的程序。

链接的两种方式：1、静态链接 (static Linking) 2、运行时动态链接 (Run-time Dynamic Linking)

2.1 静态链接

在程序运行前，用链接程序将目标模块链接成一个完整的装入模块。

静态链接的任务：

1）对相对地址进行修改：

2）变换外部调用符号：将每个模块中所用的外部调用符号，都变换为相对地址

静态链接的特点：

1）存储开销大

2）程序开发不方便

3）程序运行快（相对于动态链接）

2.2 运行时动态链接

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

动态链接的特点：

1）节省内存和外存空间；

2）方便程序开发；

3）程序运行时的速度慢了。

3、程序的装入

3.1 绝对装入方式

编译程序事先已知程序在内存中的驻留位置，编译时产生绝对地址的目标代码，绝对装入程序按照装入模块的绝对地址将程序和数据装入内存。装入模块被装入内存后，不需对程序和数据的地址进行修改。

逻辑地址 == 物理地址

3.2 可重定位装入方式(静态重定位)

在程序装入时对目标程序中的指令和数据地址的修改过程称为重定位。

1）编译程序使目标模块的起始地址从0开始。

2）程序装入时，装入程序根据内存的使用情况将装入模块装入到内存的某个位置，并对模块进行重定位。

物理地址=有效逻辑地址+程序在内存中的起始地址。

3.3 动态运行时装入

进程执行时进行逻辑地址到物理地址的转换 。(因为进程在活动过程中，在物理内存中的位置会发生变化，比如在具有对换功能的系统中）。

CPU --逻辑地址346--> + 重定位寄存器(14000) --> 物理地址(14346)--->内存

3 连续分配存储管理方式

1、单一连续分配

这种方式适用于单用户，单任务的OS。把内存分为系统区和用户区。系统区仅供OS使用，用户区供用户使用。

用户程序 + OS内核

2、分区式分配

2.1 固定分区分配

image-20220610154121954

struct {
      int num;  //分区编号
      int length; //分区大小
      int addr;  //分区起始地址   
      int state ;//分区状态，
      } mem_block[4]；

固定分区的特点：

1、管理简单 2、内存利用率低

2.2 动态分区分配

使用固定分区不利于提高内存利用率，故使用动态分区，根据进程的具体情况分配内存。

本节主要内容：动态分区分配使用的数据结构、动态分区分配算法、动态分区的分配和回收操作

2.2.1 动态分区分配的基本原理

​ 系统初始只有一个大空闲区，当进程请求空间时，由系统根据进程需要的空间大小划分出一片空闲区分配给进程。系统运行一段时间后，内存的空闲区可能散布在不连续的区域。系统维护一个记录当前空闲分区情况的数据结构，当进程请求内存时，系统从所有空闲区中找大小合适的空闲分区进行分配。系统中分区的大小和数量都是变化的，空闲区的大小和数量也是变化的。

2.2.2 分区分配中的数据结构

空闲分区表

包含分区序号、分区始址及分区大小等表目。

空闲分区链

为每个空闲分区建立一个分区结点

每个结点包括:向前、向后指针、分区起始地址及大小。

image-20220610154625695

2.2.3 动态分区分配算法

我们介绍下面三种动态分区分配算法：

1）首次适应算法FF 2） 循环首次适应算法。3） 最佳适应算法

2.2.3.1 首次适应算法FF

在采用空闲分区链作为数据结构时，FF算法要求空闲分区链以地址递增的次序链接。在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后，再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。

首次适应算法FF的特点：

1）高地址部分大空闲区较多；

2）低地址部分容易留下小分区；

3）查找从低地址开始，查找开销较大。

2.2.3.2 循环首次适应算法

该算法是由首次适应算法演变而形成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，并从中划出一块与请求的大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，以指示下一次起始查找的空闲分区，并采用循环查找方式。

循环首次适应算法的特点:

1）空闲区分布均匀

2）查找开销较小

3）容易使系统缺乏大空闲区

2.2.3.3 最佳适应算法

该算法每次为作业分配内存，总是把既能满足要求、又是最小的空闲分区分配给作业，避免了“大材小用”。为了加速寻找，该算法要求将所有的空闲区，按其大小以递增的顺序形成一空闲区。这样，第一次找到的满足要求的空闲区，必然是最优的。

最佳适应算法的特点：

1）避免大材小用，提高内存利用率

2）容易留下难以利用的小空闲区

2.2.3.4 分区分配操作

内存分配流程

image-20220610155849400

内存回收流程

1）释放内存 2）合并空闲区

紧凑

一、紧凑

把多个分散的小分区拼接成大分区的方法，被称为“拼接”或“紧凑”

image-20220610155941627

二、动态重定位

物理地址=逻辑地址+重定位寄存器中的地址

4 不连续分配存储管理方式

4.1 基本分页存储管理方式

将一个进程的逻辑地址空间分成若干个大小相等的页,将内存空间分成与页相同大小的若干个物理块（页框）。每个进程页存在一个内存物理块中,页号连续的页可以离散存放在物理块号不连续的物理块中.利用页表实现逻辑地址到物理地址的映射。

一、基本概念

1.页：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页（page）。

2.物理块：将内存空间分成与页相同大小的若干个存储块，称为物理块或页框或帧。(page frame)

3.分页存储：在为进程分配内存时，以物理块为单位将进程中的若干页分别装入 多个可以不相邻接的物理块中。

4.页内碎片：进程的最后一页一般装不满一块，而形成不可利用的碎片，称为“页内碎片”。

二、基本分页存储管理方式中的地址结构

1、地址结构中包含两部分：页号P、页内偏移量W。若用m位表示逻辑地址，页大小为2的n次幂，则用低n位表示页内偏移量w；用高m-n位表示页号P

以32位地址为例:可用0~11位表示页内偏移量n=12(页内$2^{12}$个单元=物理块大小=4KB);12-31位(20位)表示页号，共可有$2^{20}$个页(1M个页)这种地址结构可以表示4GB的逻辑地址空间。

三、页表

页表是系统为进程建立的数据结构，页表的作用是实现从页号到物理块号的映射。在进程地址空间内的所有页(0-n)，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号（页框号）

image-20220610162914055

四、地址变换机构

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构，该机构的基本任务是实现逻辑地址到物理地址的转换。

image-20220610163320431

地址变换过程

1、进程执行，PCB块中页表起始地址送页表寄存器。

2、CPU访问逻辑单元a。

3、由分页地址变换机构自动将 a 分为页号和页内地址两部分

4、由硬件检索机构搜索页表，得到物理块号（页框号）。

搜索原理：页号对应的页表项地址=页表起始地址+页表项长度*页号。(页表项中存有物理块号)。

5、生成物理地址。物理地址=物理块号*块大小+块内偏移地址

页大小的选择

1、在分页系统中页的大小是由机器的体系结构所决定的,亦即由硬件决定。（如：分页单元把低12位逻辑地址解释为页内偏移地址，则页大小就是4KB).

2、影响页大小设计的因素

1）管理内存的开销：

（1）页太小，有利于提高内存的利用率。但会导致进程所需页多，页表过长，占用大量内存空间；同时，降低页换入换出效率。
（2）页太大，页内碎片大，空间利用率降低。

2）页的大小

(1)、页大小是2的幂。

(2)、页大小在512B~1GB

(3)、硬件可以支持多种不同的页大小。页大小4KB 16KB 2MB 4MB 8MB 16MB等等

五、块表

快表（转换后援缓冲TLB-Translation Lookaside Buffer）,是为了提高CPU访存速度而采用的专用缓存，用来存放最近被访问过的页表项。

TLB包括P1和P2页号以及页内偏移

1、快表的引入

CPU读写一个数据，需两次访问内存。第1次访存读物理块号、第2次取指令或数据。

为了提高访存速度引入快表，快表用于存放最近使用过的页表项。

2、引入TLB之后的地址变换过程

image-20220610164632006

3、引入TLB的性能分析

若cpu访问内存的时间为120ns,访问TLB的速度为20ns,试比较有TLB和无TLB系统的有效访问时间。

假定TLB的命中率为90%

1）有TLB系统的有效访问时间=（120+120+20）* 10%+（120+20）* 90%=152ns

2）无TLB系统的有效访问时间=120+120=240ns

六、两级和多级页表

对于很大的逻辑地址空间，使用分页存储，需要很大的连续空间来存放页表，为了实现页表的离散存放，我们引入了两级或多级页表，其好处是：

1）对页表所需的内存空间，采用离散分配方式,来解决难以找到一块连续的大内存空间以及页表的离散存放的问题。

2）只将当前需要的页表调入内存，其余的页表可以驻留在外存中。

1、两级页表的实现方法

​ 将页表再进行分页，使每个页表分页的大小与内存物理块的大小相同，并为它们编号。将这些页表分页分别放入不同的、不一定相邻的物理块中，为离散分配的页表分页再建立一张页表，称为外层页表（也叫页目录），在外层页表中的每个表项中记录了页表分页所在的物理块号。

image-20220610165221247

2、两级页表的寻址

1）对于给定的逻辑地址A,由p1，从外层页表中找到页表分页所在的物理块号。

2）由p2，从页表分页中找到进程页所在的物理块号。

3）由A所在的进程页的物理块号*块大小+页内偏移得到A对应的物理地址。

image-20220610165949152

使用两级页表的系统，当进程切换时，欲运行的进程的外层页表起始地址被写入CPU页表寄存器。地址映射的过程如下：

（1）对于给定的逻辑地址A，由硬件从中分离出外部页号p1、页表分页中的页号p2、页内偏移地址W。

（2）外层页表的p1号页表项的起始地址=外层页表的起始地址（页表寄存器的值）+p1 ×页表项长度

​ 从该地址处读取p1号页表分页所在的物理块号d1

（3）P1号页表分页的p2号页表项的起始地址=d1 ×物理块大小+p2 ×页表项长度

​ 从该地址处读取进程页所在的物理块号d2

（4）A对应的物理单元的地址=d2×物理块大小+页内偏移地址W。

七、多级页表结构

​ 对于64位的机器，使用二级页表，仍存在连续占用大量内存的问题，可以采用多级页表结构（64位系统的四级分页和ULtraSPARC的7级分页），将外层页表再分若干页。

image-20220610183627887

减少页表占用内存的方法

将当前所需要的页表和外层页表放在内存中，其余页表放在外存，当所需页表不在内存时，产生中断，将请求的页表调入内存。

八、反置页表

用反置页表，为每一个物理块设一个表项，表项中放进程号和页号，系统只维护一张反置页表。由于物理存储空间小于逻辑存储空间，所以使用反置页表减少了页表占用的内存空间。

逻辑地址：进程号、页号、页内偏移地址

寻址过程：根据进程号和页号找到物理块号

物理地址=物理块首址+页内偏移地址

九、页的共享

image-20220610184231826

4.2 分段系统的基本原理

分段：作业的地址空间被划分成若干个段，每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定，段的大小不一样,每段的逻辑地址从0开始。

分段的逻辑地址结构：段的逻辑地址=段号+段内偏移地址

一、段表

1）系统为每个段分配一个连续存储区，各个段可以离散地放入内存不同的区域。

2）系统为每个进程建立一张段表，段表的每一个表项记录信息：段号、段长、该段的基址。

三、段表

1、系统为每个段分配一个连续存储区，各个段可以离散地放入内存不同的区域。

2、系统为每个进程建立一张段表，段表的每一个表项记录信息：段号、段长、该段的基址。

image-20220610185422528

image-20220610185528581

四、分页和分段的主要区别

1）页是按物理单位划分的,段是按逻辑单位划分的。

2）页的大小是固定的，段的大小不固定。

3）分页的地址空间是一维的，分段的地址空间是二维的。

4.3 段页式存储管理方式

​ 将用户进程空间先划分成若干个段，每个段划分成若干个页，每个进程有一个段表，每个段都有一个页表。已知地址为段号和段内偏移。段页式存储管理的逻辑地址形式由段号、段内页号和页内地址三部分组成。每一段表项存放某个段的页表起始地址和页表长度。

image-20220610185900352

二、地址变换过程

1）利用段号，找到某段的段表项，得到该段页表的首地址。

2）利用段内页号和由1得到的页表起始地址得到页表项。

3）由页表项得到页所在的物理块号。

4）物理块号与页内地址得到某逻辑地址对应的物理地址。

image-20220610190146972

5 题目

1、若CPU访问内存的速度为120ns,访问TLB的速度为20ns,试比较有TLB和无TLB系统的有效访问时间。

假定TLB命中率为90%，则由TLB时$(120+120+20)*10%+(120+20)*90%$，无TLB时$(120+120)$

2、页太大或者太小对内存管理的 效率和内存利用率分别有什么影响？分页系统一般采用多大的页？

答：页太小，页内碎片小，但会导致进程所需页多，页表过长，占用大量连续内存空间；同时，导致较高的缺页率。页太大，进程页表占用的连续空间小，缺页率低。但页内碎片大，空间利用率降低。

一般页大小在512个字节~4KB。

3、说明分页存储管理的地址映射过程。

答：分页存储管理的地址映射过程说明如下：

进程执行，页表起始地址和页表长度送页表寄存器。

CPU访问逻辑单元a。

由分页地址变换机构自动将a分为页号和页内地址两部分

由硬件检索机构搜索页表，得到物理块号。

搜索原理：页号对应的页表项地址=页表起始地址+页表项长度*页号。(页表项中存有物理块号)。
物理地址=物理块号*物理块大小+页内偏移地址。

第七章 虚拟内存管理

1 虚拟存储器概述

一、什么是虚拟存储器

虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。在虚拟存储器系统中，进程无需全部装入，只要装入一部分就可运行。

二、为什么引入虚拟存储技术

1.提高内存利用率

2.提高多道程序度

注：多道程序度是指同时驻存在内存的进程数

3.使程序员不用担心物理内存的容量对编程的限制。

三、 虚拟存储器的特征

1）离散性 2）多次性 3）对换性 4）虚拟性

2 虚拟存储器的实现方式-请求分页系统

请求分页系统是在分页系统的基础上，增加了请求调页功能、页置换功能所形成的页式虚拟存储系统。其实现包括：

1）请求分页的页表 2）缺页中断处理机制 3）地址变换

3 请求分页存储管理方式

一、请求分页中的软/硬件支持

页表项包括以下内容：

1）物理块号 2）状态位P 3）访问字位A 4）修改位M 5）外存地址

若存在位为0，则产生却也异常中断，缺页异常处理程序主要完成的功能有：保护现场、将缺页调入内存、更新页表。

二、缺页中断处理机制

1.在指令执行期间产生中断

2.回到中断前的指令处重新执行被中断的指令

三、地址变换

image-20220610192529848

四、页面分配

4.1 最小物理块数

​ 保证进程正常运行所需要的最少物理块数，它与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。

4.2 页分配和置换策略

1）固定分配局部置换。 2）可变分配全局置换。 3） 可变分配局部置换

4.3 分配算法
1）平均分配算法 2）按比例分配算法 3）考虑优先权的分配算法

五、页面调入策略

何时调入页面

1）预调页策略：将预计不久之后会被访问的页，预先调入内存。

2）请求调页策略。

从何处调入页面（教材P188页）

1）对换区调入：对换空间足够大,进程运行前,将相关文件从文件区拷贝到对换区，发生缺页请求时，从对换区调入缺页。
2）从文件区调入：对不会修改的页，从文件区调入；可能被修改的部分，换出时写入对换区，再换入时，从对换区调入。
3）Unix方式:与进程有关的文件都放在文件区,凡是未运行过的页面都应该从文件区调入,曾经运行过又被换出的页面从对换区调入。

六、页面置换算法

6.1 最佳置换算法

策略：将未来最长时间内不再被访问的页换出。

缺点：不可实现。

优点：换页率最低。

image-20220610193220407

为什么选择最近既没有被访问也没有被修改的页面作为淘汰页？

因为最近没有被访问的页面在将来被访问的可能性小，选择这样的页面换出能降低缺页率。没有被修改的页面换出时不需要把页面内容写回磁盘，避免了访问磁盘造成的时间开销。

6.2 先进先出页面置换

策略：最先进入内存的页最先被淘汰。

实现：采用一个先进先出队列。

缺点：无法保证常用页面不被换出，导致较低的效率。

优点：实现简单。

image-20220610193252472

6.3 最近最久未使用（Least Recently Used）LRU置换算法

LRU置换算法是选择最近最久未使用的页面予以淘汰。 向左看（置换图）P191-192页

LRU算法的实现要求系统具有较多的硬件支持。要解决两个问题：

1）一个进程在内存中的各个页各有多久时间未被进程访问；

2）如何快速地知道哪一页是最近最久未使用的页。

LRU算法的实现

栈：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用的页面号。

时间计数器：为每个页表项增加一个时间字段，并为CPU增加一个逻辑时钟或计数器。每次访问内存某个页时，就将递增了的时钟寄存器的值赋给这个页对应的页表项的时间字段，每次置换时选择时间字段值最小的页作为换出页。

LRU的近似算法

附加引用位算法：为内存的页保留一个8位的字节，在规定时间间隔内，操作系统把每个页的引用位（也就是访问位A）转移到其8bit字节的高位，将其他位右移，并抛弃最低位。置换时选附加位值最小的页。

简单的Clock置换算法：利用Clock算法时，为每一页设置一位访问位，再将内存中的所有页都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查其访问位。如果是0，就选择该页换出；若为1，则重新将它复0，暂不换出而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页时 ，若其访问位仍为1，则返回到队首再去检查第一个页。

改进型Clock置换算法：在将一个页换出时，如果该页已被修改过，便须将它重新写到磁盘上，但如果该页未被修改过，则不必将它写回磁盘。换言之，对于修改过的页在换出时所付出的开销将比未修改过的页开销大。在改进型Clock算法中，除考虑页的使用情况外，还须再增加一个置换代价这一因素。这样，选择换出页时，既要是未使用过的页，又要是未被修改过的页。把同时满足两个条件的页作为首选的淘汰页。

在该算法中，由访问位A和修改位M可以组合成下面四种类型的页面：

1（A=0,M=0)该页最近既未被访问、又未被修改，是最佳淘汰页。

2（A=0,M=1)该页最近未被访问但已被修改，并不是很好的淘汰页。

3（A=1,M=0)最近已被访问，但未被修改，该页有可能再被访问。

4（A=1,M=1)最近已被访问且被修改，该页可能再被访问。

改进型Clock置换算法可分为以下三步：

1、从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页。将遇到的第一个页作为所选中的淘汰页。在第一次扫描期间不改变访问位A。

2、如果第一步失败，则开始第二论扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有经过的页面的访问位置0。

3、如果第二步也失败，即未找到第二类页面，则将指针返回到开始的位置。然后，重复第一步，如果仍失败再重复第二步，此时一定能找到被淘汰的页。

最坏需要四次扫描。

image-20220610194144761

6.4 最少使用置换算法

该置换算法选择在最近时期使用最少的页面作为淘汰页。

6.5 页缓冲算法

采用可变分配和局部置换方式，置换算法采用的是FIFO。算法规定如果被淘汰的页面未被修改，就将它直接放入空闲链表中，否则，便放入已修改页面的链表中。

4 请求分页系统的性能分析

1、缺页率对有效访问时间的影响
有效访问时间：成功访存所用的时间。

P：缺页率。Ma：内存访问时间

有效访问时间=(1-P)×ma+P×缺页时间。

缺页时间=缺页服务时间+缺页读入时间+进程重新执行时间

2、工作集

程序在运行时对页的访问是不均匀的；即往往在某段时间内的访问仅局限于较少的若干个页，而在另一段时间内，则又可能仅局限于对另一些较少的页进行访问，若能预知程序在某段时间间隔内要访问哪些页，并能将它们提前调入内存，将会大大降低缺页率，从而减少置换工作，提高CPU的利用率。

在某段时间间隔△里，进程实际要访问的页的集合。要使缺页少发生，必须使程序的工作集全部在内存中。

三、W(t, △) 工作集的窗口

△又叫工作集的“窗口尺寸”， △太大，影响存储器利用率。

△太小，缺页率高，降低程序执行的时间性能，降低系统吞吐量。

W(t，△)与t相关，不同的t对应不同的工作集。

即：程序运行的过程中，运行到不同的时刻，需要访问的页不同。

注：最小工作集，是进程正常运行需要调入内存的最小页数。

当内存有足够的空间时，可以为进程分配足够的空间以装入它的最大工作集。

3、抖动

多道程序度太高，使运行进程的大部分时间都用于进行页的换入/换出，而几乎不能完成任何有效的工作的状态称为“抖动”。

抖动的预防

1）采取局部置换策略。当进程发现缺页后，仅在自己的内存空间范围内置换页面，不允许从其他进程获得新的物理块。
2）在CPU调度程序中引入工作集算法。只有当每个进程在内存中都有足够大的驻留集时，方能再从外存上调入新的作业。
3）挂起若干进程。为了预防抖动，挂起若干进程，腾出进程占用的空间。

第八章 文件系统

1 文件

1、文件命名

文件命名向用户提供文件访问的抽象机制

2、文件的命名规则

不同系统的文件命名略有不同，但所有操作系统都允许用一到八个字母组成的字符串作为文件名。

有的文件系统可支持长文件名，255个字符的文件名。

文件名的大小写:有的系统区分文件名的大小写，如：UNIX；

有的系统不区分文件名的大小写，如DOS。

3、文件扩展名

文件扩展名的作用有两种：

一种扩展名不给计算机传送特别信息，只是用于表示这个文件的类型，给用户一个提示信息。

另一种扩展名，如C程序的扩展名，则为编译器、链接程序和系统提供信息,使它们能够区分哪些是C文件，哪些是汇编文件，哪些是其它文件。

4、文件结构

(1)无结构字节序列

(2)固定长度记录序列

这个模型中，文件是一个固定长度记录的序列，每条记录都有内部结构，把文件作为记录序列的中心思想是：读操作返回一条记录，而写操作重写或追加一条记录。

5、文件类型

OS设计要考虑：系统应该支持哪些类型的文件，并为每种类型的文件定义合法的操作。文件的类型有：

正规文件、目录文件、字符设备文件、块设备文件等

本节主要介绍正规文件，正规文件中包含用户信息，一般为ASCII或二进制文件。

5.1 ASCLL文件

由多行正文组成，每行用回车符或换行符，或回车换行符结束。

ASCII文件可以原样地显示和打印，也可以用通常的文本编辑器进行编辑。

5.2 二进制文件

具有一定的内部结构，不能直接用通常的编辑器显示 或打印。不同的OS可以识别不同的二进制文件，把某一种结构的二进制文件做为系统中的可执行文件。

6、文件存取

顺序存取：进程可以从文件开始处读取文件中的所有字节或者记录，但不能跳过某些内容

随机存取：可以以任意顺序读取文件中的字节或记录。

7、文件属性

文件属性是用来描述文件的信息，如文件长度、文件的创建日期，不同的系统为文件定义不同的属性。

下面是一些常用的系统调用，通过这些系统调用，可以实现对文件的操作。

(1)CREATE 创建文件，并设置文件属性。

(2)DELETE 删除文件释放磁盘空间。

(3)OPEN 使用文件之前，进程必须打开文件。OPEN 调用的目的是：将文件属性和磁盘地址表载入主存，便于以后的快速存取。

(4)CLOSE 当存取结束后，文件属性和磁盘地址就不再需要了，这时应该关闭文件，以释放内部表空间，许多系统限制进程打开的文件数，鼓励用户关闭不再使用的文件。

(5)READ 文件读取数据，应该指明读取的字节数及读入数据存放的缓冲区。

(6)WRITE 写文件尾，则文件长度增加；写中间，则文件原数据丢失。

(7)APPEND 只能在文件尾添加数据。

(8)SEEK 对于随机存取文件，SEEK用于将文件指针指向特定位置。

(9)GETATTRIBUTES

(10)SETATTRIBUTES

(11)RENAME

2 目录

目录通常包含有许多目录项，每个目录项对应一个文件。

1、目录结构

1）属性和地址信息放在目录项中

2）属性和地址信息不在目录项中

2、目录的结构

image-20220610212006675

3、目录类型

①单层目录

②两级目录(一个用户一个目录)

③树型目录

用户需要的是目录树，使每个用户可以拥有所需要的多个目录，以便自然地组织他们的文件。

4、路径名

(1)绝对路径名

它由从根目录到文件的路径组成，绝对路径名总是从根目录开始，并且是唯一的。

(2)相对路径名

所有的路径名，如果不是从根目录开始的，都是相对于当前目录(工作目录)的，同一文件的相对路径可能有多个，由当前工作目录而定。

5、目录操作

  相对于文件的系统调用而言，各个系统中用于管理目录的系统调用差别更大，我们以UNIX系统为例，说明对系统目录有哪些操作。

CREATE

DELETE

OPENDIR

CLOSEDIR

READDIR

RENAME

3 文件系统的按名访问

1、连续分配

连续分配是将文件作为连续数据块存储在磁盘上。

优点：简单易实现，记录每个文件用到的磁盘块仅需一个数字，即第一块的磁盘地址以及文件所占磁盘块数量。性能好，一次操作，可读出整个文件。

缺点：无法知道该为文件分多少空间，文件长度是会变的，造成磁盘碎片。

2、链式分配

为每个文件构造磁盘块的链接，每个块的第一个字用于指向下一块的指针，块的其它部分存放数据。在目录项中只需存放文件第一个数据块所在的磁盘地址，文件的其它块可以根据这个地址来查找。

优点：磁盘空间利用率高，管理简单。

缺点：随机存取的速度慢。

3、使用索引的链接表分配

使用方法二实现文件，取出每个磁盘块的地址信息（如：簇号），把它放在内存的表或索引中。随机查找时，顺着链查找磁盘块，但只需查找内存中的链表，不需访问磁盘。

同以前的方法一样，不管文件有多大，在目录项中只需记录一个整数，根据它可以找到文件的所有块。MS-DOS就使用这种方法进行磁盘分配。

4、文件按名访问的实现

目录系统的主要功能是把ASCⅡ文件名映射成查找文件数据所需的地址信息。

（1）CP/M中的目录

CP/M中只有一层目录，因此只有一个目录(文件)，查找文件名，就是在这个唯一的目录中找到文件对应的目录项，从目录项中获得文件存放的磁盘地址。

image-20220610212830732

（2）MS—DOS中的目录

​ 每个目录项包含文件名、文件属性、和第一个磁盘块号，根据第一个磁盘块的块号，可以找到所有的文件块。MS-DOS是树型目录(层次型目录)。

image-20220610212853449

目录结合FAT表

image-20220610213036088

（3）FAT12

FAT12采用12位文件分配表，磁盘块大小为2KB，则FAT12可以管理的磁盘容量是8M。2KB×4K（个）（2^12个磁盘块）=8MB

FAT12文件系统的文件名：只能是8.3格式的文件名。

说明：文件系统以簇（磁盘块）为单位为文件分配存储空间

(4)UNIX中的目录

UNIX中使用的目录结构非常简单，每个目录项只包含一个文件名及其i节点号。==文件类型、长度、时间、拥有者和地址等所有信息都放在i-节点中== 。当查找文件时先找到该文件的i节点存放的位置，再从i节点中找到该文件的磁盘块号。

image-20220610213836505

i节点

给每个文件赋予一张称为i节点的小型表其中列出了文件属性和各数据块在磁盘上的地址，对于大文件，由于包含的磁盘块数很多，可以在i节点中存放一次间接地址，或二次间接地址，或三次间接地址。UNIX中使用这种分配方案。

image-20220610214320911

4 磁盘空间的管理

1、磁盘空间管理

文件通常存放在磁盘上，所以空间的管理是系统设计者要考虑的一个重要问题。

文件的存放有两个策略：连续存放和不连续地分块存放。连续存放存在一个缺陷，当文件扩大时，可能需要移动文件，而在磁盘上移动文件是很慢的。所以几乎所有的文件系统都把文件分割成固定大小的块来存储。各块不必相邻。

2、块（簇）大小

给文件分配块太大，浪费磁盘空间。块太小，查找一个文件多次寻道,浪费时间。一般选择的块大小为2n个连续的扇区。若扇区大小为512个字节，磁盘块的大小选定为4KB，则文件系统读写8个连续的扇区，并把它们看成不可分割的单元。

现在的磁盘扇区大小有的是1KB、4KB不一定是512字节。

3、记录空闲块

空白磁盘块的链接表

用一些空白磁盘块存放空闲磁盘块块号。一个磁盘块存放尽可能多的空闲盘块号，并专门留出最后几个字节存放指向下一个存放空闲盘块号的磁盘块的指针 。

用n位位图表示磁盘块使用情况

磁盘被划分成n块，用n位位图表示磁盘块使用情况,每一位代表一个盘块，比如用：位的值为0表示磁盘空闲，位的值为1表示磁盘已分配。

4、虚拟文件系统(VFS)

虚拟文件系统（Virtual Filesystem）也可以称之为虚拟文件系统转换（Virtual Filesystem Switch）或VFS，是一个内核软件层，用来处理与Unix标准文件系统相关的所有系统调用,能为各种文件系统提供一个通用的接口。

5 题目

1、举例说明文件系统是如何实现文件的按名存取的。

答:在类Unix操作系统中目录文件中存有子目录文件和用户文件的文件名和i结点号，先以文件名为索引在目录文件中找到文件的i结点号，根据i结点号可以找到该文件的i结点，其中包含了文件的属性和地址信息。

2、举例说明文件系统所能管理的文件大小是由什么决定？

例如:FAT12采用12位文件分配表，簇块大小是连续的四个扇区，可以管理的磁盘容量是8M=4个扇区*512B*2^12。

3、“打开"操作。用户要使用存放在存储介质上的文件前，必需提出“打开"要求。系统在接到用户的“打开"要求后，找到该用户的文件，在文件目录中找到与用户的需求相符合的目录项,取出文件存放的物理地址。如果是索引文件，还要将这个文件的索引表也调入到主存中，这样，后继的读操作能够很快地进行。

4、文件系统的打开操作完成什么功能？说明FAT12文件系统完成按名访问需要哪些数据结构？是如何完成文件的按名访问的。

文件系统的打开操作完成的功能是将文件属性和文件的地址信息装入主存。

FAT12文件系统完成按名访问需要目录和FAT表的支持。

其完成按名访问的过程是：文件系统的目录项中存有文件名和文件的第一个数据块在磁盘中的簇号。在FAT表中存有后续数据块在磁盘中的簇号。 FAT12文件系统先以文件名为索引搜索目录，找到相应的目录项后获取文件第一个数据块在磁盘中的簇号。根据第一个数据块在磁盘中的簇号从FAT表中可以找到文件的其他所有数据块的簇号。

注：

什么是扇区？

盘面中一圈圈灰色同心圆为一条条磁道，从圆心向外画直线，可以将磁道划分为若干个弧段，每个磁道上一个弧段被称之为一个扇区。扇区是磁盘的最小组成单元，通常是512字节。（由于不断提高磁盘的大小，部分厂商设定每个扇区的大小是4096字节）

什么是磁盘块？

操作系统与磁盘之间交流的最小单位就是磁盘块，它是一个虚拟的概念。是对于操作系统（软件）来说有意义的概念。

由于扇区的数量比较小，数目众多在寻址时比较困难，所以操作系统就将相邻的扇区组合在一起，形成一个块，再对块进行整体的操作。

操作系统忽略对底层物理存储结构的设计。通过虚拟出来磁盘块的概念，在系统中认为块是最小的单位。

磁盘的读写基本单位是什么？

读写基本单位是扇区。磁盘的原理，物理实现，磁盘控制器是按照扇区这个单位读取等操作数据的。此题问磁盘的读写，和操作系统没有关系，千万不要联系到操作系统层面去了。

磁盘块与扇区的大小关系

既然磁盘块是一个虚拟概念。是操作系统自己＂杜撰＂的。软件的概念，不是真实的。所以大小由操作系统决定，操作系统可以配置一个块多大。一个块大小=一个扇区大小*2的n次方。N是可以修改的。

块与页的关系

操作系统经常与内存和硬盘这两种存储设备进行通信，类似于“块”的概念，都需要一种虚拟的基本单位。所以，与内存操作，是虚拟一个页的概念来作为最小单位。与硬盘打交道，就是以块为最小单位。

第九章 设备管理

1 I/O系统的组成

1、I/O系统的结构

（1）微机I/O系统 （总线型I/O系统结构）

image-20220611220641168

（2）主机I/O系统（具有通道的I/O系统结构）

image-20220611220710807

2、I/O设备的分类

(1)按传输的速率分类

①低速设备：键盘鼠标，几个字节-几百字节/秒

②中速设备：打印机，数千~数十千字节/秒

③高速设备：磁带机、磁盘机、光盘机 几十万~几兆/秒

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

①块设备：数据的存取以数据块为单位，如磁盘。块设备在块中保存信息，块的大小通常是固定的，并且一次只传送一块，通常可以通过块号访问数据。

②字符设备：传送字节流，没有使用块结构。终端、打印机、通信端口、鼠标等都是字符设备。

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

①独占设备 ②共享设备 ③虚拟设备

3、设备控制器

I/O逻辑

一个控制器可以对应多个外设、一个通道可以对应多个控制器

image-20220611220843782

I/O通道

I/O通道是一种特殊的处理机，它具有执行I/O指令的能力，并通过执行通道程序来控制I/O操作。简单说，通道是大型主机系统中专门用于I/O的专用计算机。

2 I/O控制方式

1、I/O控制的发展

程序I/O方式

 ↓

中断驱动方式

 ↓

DMA控制器（使传输以字节为单位变成以数据块为单位。）

 ↓

通道（使I/O的组织和数据的传送，都能独立进行，无需CPU干预。）

2、轮询控制方式

主机在试图发送I/O控制命令之前先反复检测设备控制器状态寄存器的忙/闲标志位，若设备忙，则主机继续检测该标志位，直到该标志位为“空闲”，然后发送I/O指令。

3、中断控制方式

与轮询控制方式相比，中断驱动I/O控制方式可以极大地提高CPU的利用率。

4、DMA控制方式

image-20220611221121035

(1)没有使用DMA时从磁盘读数的过程

①首先控制器从设备完整地读出一块数据放入数据寄存器中。

②计算该块数据的检验和以保证读取正确。

③控制器发中断信号，CPU开始从控制器的设备寄存器中将数据读入内存。

在这种方式下,每传送一个或多个字节,CPU就要处理一次中断,把数据从控制器的数据缓存送入内存。

(2)DMA控制方式

CPU发送I/O指令--命令写入CR寄存器--内存起始地址写入MAR--I/O字节数写入DC--将I/O设备地址送I/O控制逻辑--启动DMA

(3)DMA控制从磁盘读数的过程

DMA控制器控制I/O工作的原理

3 缓冲管理

1、缓冲的引入

在数据到达和数据离去的速度不一致的地方都可以引入缓冲。

2、单缓冲的工作

image-20220611221921139

2、双缓冲的工作

image-20220611221917437

3、循环缓冲

见课本252页

(1)引入循环缓冲的理由

(2)循环缓冲的组成

(3)缓冲区的使用

(4)进程同步

4、缓冲池

见课本252页

(1)缓冲池的组成

(2)Getbuf过程和Putbuf过程

(3)缓冲区的工作方式

4 设备分配

1、设备分配中的数据结构

在进行设备分配时所需的数据结构有：

(1)设备控制表

(2)控制器控制表

(3)通道控制表

(4)系统设备表

(1)设备控制表DCT

①设备类型

②设备标识符

③设备状态：等待/不等待，忙 、闲

④指向控制器表的指针

⑤重复执行的次数或时间

(2)控制器控制表COCT

①控制器标示符

②控制器状态

③与控制器相连接的通道表指针

④控制器队列的队首指针

(3)通道控制表CHCT

①通道标示符

②通道状态

③与通道连接的控制器表首址

④通道队列的队首指针

(4)系统设备表SDT

image-20220611225301360

(5)设备分配与数据结构

image-20220611230103523

2、设备分配时应考虑的若干因素

(1)设备的固有属性

①独占设备

②共享设备

③虚拟设备

(2)设备分配算法

①先来先服务

②优先级高者优先

(3)设备分配中的安全性

①安全分配方式

②不安全分配方式

3、设备独立性

(1)设备独立性的概念

设备独立性也称设备无关性，其基本含义是： 应用程序独立于具体使用的物理设备

(2)实现设备独立性带来的好处

①用户程序与物理的外围设备无关，系统增减或变更外围设备时不需要修改应用程序。

②易于处理输入输出设备的故障。

逻辑设备表：为了实现设备的独立性，系统必须能够将应用程序中所使用的逻辑设备名映射为物理设备名。可以使 用逻辑设备表实现该映射功能。

4、独占设备的分配程序

对于具有I/O通道的系统，在进程提出I/O请求后，系统的设备分配程序可按下述步骤依次进行设备分配：

(1)分配设备 (2)分配控制器 (3)分配通道

5、SPOOLing的概念

在多道程序环境下，利用一道程序来模拟脱机输入时的外围控制机的功能，把低速I/O设备上的数据传送到高速磁盘上；再利用另一道程序来模拟脱机输出时外围控制机的功能，把数据从磁盘传送到低速输出设备上。这种在联机情况下实现的同时外围操作称为Spooling(Simultaneous Periheral Operations On-Line)。

1）SPOOLing系统的组成

image-20220611231037198

2）利用SPOOLing技术实现共享打印机

当用户进程提出打印请求时，SPOOling系统先为用户做两件事：

第一步：由输出进程在输出井中为之申请一空闲盘块区，并将要打印的数据送入其中。

第二步：输出进程再为用户申请、并填写一张用户请求打印表，将该表挂到请求打印队列上。当打印机空闲时，出进程完成以下动作。

①从请求打印队列队首取一张请求打印表。

②将打印数据从输出井送打印机缓冲区(输出缓冲区)。

③打印。

④若打印完转第①步，取下一个打印请求表。

3）SPOOLing的特点

①提高I/O速度

②将独占设备改造为共享设备

③实现了虚拟设备功能

5 I/O软件原理

1、设备管理软件的层次结构

image-20220611231349337

设备无关层软件主要实现哪些功能？

主要实现缓冲管理、设备分配、设备的独立性和虚拟设备等功能。

2、中断处理程序

I/O中断处理程序的作用是将发出I/O请求而被阻塞的进程唤醒。用户进程在发出I/O请求后，由于等待I/O而被阻塞。CPU转去执行其它任务，当I/O任务完成，控制器向CPU发中断请求信号，CPU转去执行中断处理程序，由中断处理程序唤醒被阻塞的用户进程。

3、设备驱动程序

设备驱动程序是I/O进程与设备控制器之间的通信程序。其主要任务是接收上层软件发来的抽象要求，再把它转换成具体要求后发送给设备控制器，启动设备去执行。此外，它也将由设备控制器发来的信号传送给上层软件。设备驱动程序中包括了所有与设备相关的代码,是数据结构与函数的集合。每个设备驱动程序只处理一种设备，或者一类紧密相关的设备。只有驱动程序才知道某类设备控制器有多少个寄存器及它们的用途。

1）设备驱动程序的工作流程

驱动程序接收CPU的I/O命令--将接收到的抽象I/O命令转化为设备控制器能执行的命令序列--向控制器的寄存器发送这些命令序列

2）磁盘驱动程序

当有一个读第N块磁盘的请求时，磁盘驱动程序要完成以下的工作：

①计算出所请求块的物理地址。

②检查驱动器电机是否在运转。

③检查磁头臂是否定位在正确的柱面。

④确定需要哪些控制器命令及命令的执行次序。

⑤向设备控制器的设备控制寄存器中写入命令。

⑥阻塞进程，I/O完成后向上层软件传送数据并唤醒进程。

4、磁盘管理

1）磁盘调度

磁盘调度算法用来从磁盘请求队列中选择一个当前访问磁盘的任务。

(1) FCFS调度

先到先服务

(2) SSTF调度

最短路径

(3) SCAN

从外向里--从里向外--从外向里--从里向外

(4) C-SCAN

从外向里--从外向里

(5) NStepSCAN和FSCAN算法、

NStepSCAN算法是将磁盘请求队列分为N个磁盘请求队列，每个队列按照FSFC原则进行调度。

FSCAN是两个队列的NStepSCAN。

注：SCAN、SSTF和CSCAN三种扫描方法均有可能出现饥饿现象。

磁盘粘着现象

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

（1）提前读

（2）延迟写

（3）优化物理块的布局

（4）虚拟磁盘

（5）磁盘高速缓存

6 题目

1、设置当前工作目录的主要目的是( )。

A．节省外存空间B．节省内存空间C．加快文件的检索速度D．加快文件的读/写速度

C设置当前工作目录，可以减少访问文件时读取磁盘索引块的个数，从而加快文件的检索速度。

2、在系统内存中设置磁盘缓冲区的主要目的是什么

在系统内存中设置磁盘缓冲区的主要目的是减少磁盘I/O次数。磁盘缓冲区是硬盘与外部总线交换数据的场所，它对性能的影响大大超过磁盘缓存对性能的影响。

3、现有一个容量为10 GB的磁盘分区，磁盘空间以簇（Cluster）为单位进行分配，簇的大小为4 KB，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为

$10GB/4KB=10*1024*1024/4=2621440/8/1024=320KB=80簇$

4、假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35, 45, 12, 68, 110, 180, 170, 195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是？

110-170-180-195-68-45-35-12

5、在采用中断控制方式进行输入输出时，进程从提出I/O请求到本次I/O结束，操作系统要执行哪些程序？

答：执行系统调用程序、设备分配程序、设备驱动程序、中断处理程序、进程调度程序。

6、Ext2文件系统的一个i结点包括15个地址项，每个地址项存32位地址（4个字节），其中12个地址项存直接地址；一个地址项存一次间接地址；一个地址项存二次间接地址，一个地址项存三次间接地址。当一个逻辑块大小为4KB时，EXT2能管理的文件的最大长度是多少？

答：首先，12个地址项存放的是磁盘块号，所以基本的磁盘地址可表示的文件大小为12×4KB。其次，每个磁盘块大小为4KB，每个地址项占4个字节，所以，每个磁盘块中可以存放1024个地址项，这样，一次间接块可以表示的文件大小为1024×4KB。依次类推，二次间接块可以表示的文件大小为1024×1024×4KB，三次间接块可以表示的文件大小为1024×1024×1024×4KB。一个文件的最大长度为12×4KB+1024×1024×4KB+1024×1024×1024×4KB