史上最全的操作系统复习笔记（基于王道和自己整理）

来都来了给我点个赞吧🌹🌹🌹🌹🌹

什么是操作系统

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

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

OS 作为用户与计算机硬件系统之间接口的含义是：OS 处于用户与计算机硬件系统之 间，用户通过 OS 来使用计算机系统。或者说，用户在 OS 帮助下，能够方便、快捷、安全、 可靠地操纵计算机硬件和运行自己的程序。应注意，OS 是一个系统软件，因而这种接口是软件接口。图 1-1 是 OS 作为接口的示意图。由图 可看出，用户可通过以下三种方式使用计算机。

 (1) 命令方式。这是指由 OS 提供了一组联机 命令接口，以允许用户通过键盘输入有关命令来 取得操作系统的服务，并控制用户程序的运行。

 (2) 系统调用方式。OS 提供了一组系统调用， 用户可在自己的应用程序中通过相应的系统调 用，来实现与操作系统的通信，并取得它的服务。

 (3) 图形、窗口方式。这是当前使用最为方便、最为广泛的接口，它允许用户通过屏幕 上的窗口和图标来实现与操作系统的通信，并取得它的服务。

2.OS 作为计算机系统资源的管理者 

在一个计算机系统中，通常都含有各种各样的硬件和软件资源。归纳起来可将资源分 为四类：处理器、存储器、I/O 设备以及信息(数据和程序)。相应地，OS 的主要功能也正是 针对这四类资源进行有效的管理，即：处理机管理，用于分配和控制处理机；存储器管理， 主要负责内存的分配与回收； I/O 设备管理，负责 I/O 设备的分配与操纵；文件管理，负责 文件的存取、共享和保护。可见，OS 的确是计算机系统资源的管理者。事实上，当今世界 上广为流行的一个关于 OS 作用的观点，正是把 OS 作为计算机系统的资源管理者。 

值得进一步说明的是，当一个计算机系统同时供多个用户使用时，用户对系统中共享 资源的需求(包括数量和时间)可能发生冲突，为了管理好这些共享资源(包括硬件和信息)的 使用，操作系统必须记录下各种资源的使用情况，对使用资源的请求进行授权，协调诸用 户对共享资源的使用，避免发生冲突，并计算使用资源的费用等

3.OS 实现了对计算机资源的抽象 

对于一个完全无软件的计算机系统(即裸机)，它向用户提供的是实际硬件接口(物理接 口)，用户必须对物理接口的实现细节有充分的了解，并利用机器指令进行编程，因此该物 理机器必定是难以使用的。为了方便用户使用 I/O 设备，人们在裸机上覆盖上一层 I/O 设备 管理软件，如图 1-2 所示，由它来实现对 I/O 设备操作的细节，并向上提供一组 I/O 操作命令，如 Read 和 Write 命令，用户可利用它来进行数据输入或输出，而无需关心 I/O 是如何 实现的。此时用户所看到的机器将是一台比裸机功能更强、使用更方便的机器。这就是说， 在裸机上铺设的 I/O 软件隐藏了对 I/O 设备操作的具体细节，向上提供了一组抽象的 I/O 设备.

4.用户和计算机硬件之间的接口

（1）人工操作方式

从第一台计算机诞生(1945 年)到 20 世纪 50 年代中期的计算机，属于第一代计算机。此 时的计算机是利用成千上万个真空管做成的，它的运行速度仅为每秒数千次，但体积却十 分庞大，且功耗也非常高。这时还未出现 OS。计算机操作是由用户(即程序员)采用人工操 作方式直接使用计算机硬件系统，即由程序员将事先已穿孔(对应于程序和数据)的纸带(或 卡片)装入纸带输入机(或卡片输入机)，再启动它们将程序和数据输入计算机，然后启动计 算机运行。当程序运行完毕并取走计算结果之后，才让下一个用户上机。这种人工操作方 式有以下两方面的缺点:  

(1) 用户独占全机。此时，计算机及其全部资源只能由上机用户独占。 

(2) CPU 等待人工操作。当用户进行装带(卡)、卸带(卡)等人工操作时，CPU 及内存等 资源是空闲的。

可见，人工操作方式严重降低了计算机资源的利用率，此即所谓的人机矛盾。随着 CPU 速度的提高和系统规模的扩大，人机矛盾变得日趋严重。

下面的作业也就是一个程序：

（2）脱机输入/输出方式

脱机也就是运用了io的方式让电脑操作不是只通过主机来操作数据，认识引进了磁盘的类似概念

为了解决人机矛盾及 CPU 和 I/O 设备之间速度不匹配的矛盾，20 世纪 50 年代末出现 了脱机输入/输出(Off-Line I/O)技术。该技术是事先将装有用户程序和数据的纸带(或卡片) 装入纸带输入机(或卡片机)，在一台外围机的控制下，把纸带(卡片)上的数据(程序)输入到 磁带上。当 CPU 需要这些程序和数据时，再从磁带上将其高速地调入内存。 

脱机 I/O 方式的主要优点：

 1.减少了 CPU的空闲时间。装带(卡)、 卸带(卡)以及将数据从低速 I/O 设备送到高 速磁带(或盘)上，都是在脱机情况下进行 的，并不占用主机时间，从而有效地减少了 CPU 的空闲时间，缓和了人机矛盾。 

2.提高了 I/O 速度。当 CPU 在运行中需要数据时，是直接从高速的磁带或磁盘上将 数据调入内存的，不再是从低速 I/O 设备上输入，极大地提高了 I/O 速度，从而缓和了 CPU 和 I/O 设备速度不匹配的矛盾，进一步减少了 CPU 的空闲时间。

通常是把一批作业以脱机 方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下使这批作业能一个 接一个地连续处理。其自动处理过程是：首先，由监督程序将磁带上的第一个作业装入内 存，并把运行控制权交给该作业。当该作业处理完成时，又把控制权交还给监督程序，再 由监督程序把磁带(盘)上的第二个作业调入内存。计算机系统就这样自动地一个作业一个作 业地进行处理，直至磁带(盘)上的所有作业全部完成，这样便形成了早期的批处理系统。由 于系统对作业的处理都是成批地进行的，且在内存中始终只保持一道作业，故称此系统为 单道批处理系统(Simple Batch Processing System)。

单道批处理系统的特征:

(1) 自动性。在顺利情况下，在磁带上的一批作业能自动地逐个地依次运行，而无需人 工干预。

(2) 顺序性。磁带上的各道作业是顺序地进入内存，各道作业的完成顺序与它们进入内 存的顺序，在正常情况下应完全相同，亦即先调入内存的作业先完成。

 (3) 单道性。内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入 内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。

多道程序设计的基本概念:

在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备 队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享 CPU 和系统中的各种资源。

多道批处理系统的优缺点

(1) 资源利用率高。由于在内存中驻留了多道程序，它们共享资源，可保持资源处于忙 碌状态，从而使各种资源得以充分利用。

(2) 系统吞吐量大。系统吞吐量是指系统在单位时间内所完成的总工作量。能提高系统吞吐量的主要原因可归结为：第一，CPU 和其它资源保持“忙碌”状态； 第二，仅当作业 完成时或运行不下去时才进行切换，系统开销小。

(3) 平均周转时间长。作业的周转时间是指从作业进入系统开始，直至其完成并退出系 统为止所经历的时间。在批处理系统中，由于作业要排队，依次进行处理，因而作业的周转时间较长，通常需几个小时，甚至几天。

(4) 无交互能力。用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，这对修改和调试程序是极不方便的。

分时系统(Time Sharing System)与多道批处理系统之间有着截然不同的性能差别，它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。它被经常应用于查询系统中，满足许多查询用户的需要。简单来说就是把一个系统再多用户访问的时候给每个用户分一段时间在一段时间没有做完这个任务，也把时间给下一位用户直到循环回来继续执行。

分时系统的特征

 (1) 多路性。允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服 务。宏观上，是多个用户同时工作，共享系统资源；而微观上，则是每个用户作业轮流运 行一个时间片。多路性即同时性，它提高了资源利用率，降低了使用费用，从而促进了计 算机更广泛的应用。 

(2) 独立性。每个用户各占一个终端，彼此独立操作，互不干扰。因此，用户所感觉到 的，就像是他一人独占主机。

(3) 及时性。用户的请求能在很短的时间内获得响应。此时间间隔是以人们所能接受的 等待时间来确定的，通常仅为 1～3 秒钟。

(4) 交互性。用户可通过终端与系统进行广泛的人机对话。其广泛性表现在：用户可以 请求系统提供多方面的服务，如文件编辑、数据处理和资源共享等。

所谓“实时”，是表示“及时”，而实时系统(Real Time System)是指系统能及时(或即时) 响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一 致地运行。例如自动驾驶要在指定的时间内完成任务不然就会出问题

在实时系统中必然存在着若干个实时任务，这些任务通常与某个(些)外部设备相关，能 反应或控制相应的外部设备，因而带有某种程度的紧迫性。可从不同的角度对实时任务加 以分类。

1) 按任务执行时是否呈现周期性来划分

(1) 周期性实时任务。外部设备周期性地发出激励信号给计算机，要求它按指定周期循 环执行，以便周期性地控制某外部设备。 

(2) 非周期性实时任务。外部设备所发出的激励信号并无明显的周期性，但都必须联系 着一个截止时间(Deadline)。它又可分为开始截止时间(某任务在某时间以前必须开始执行) 和完成截止时间(某任务在某时间以前必须完成)两部分。

2) 根据对截止时间的要求来划分

(1) 硬实时任务(Hard real-time Task)。系统必须满足任务对截止时间的要求，否则可能 出现难以预测的结果。 

(2) 软实时任务(Soft real-time Task)。它也联系着一个截止时间，但并不严格，若偶尔 错过了任务的截止时间，对系统产生的影响也不会太大。

1．单用户单任务操作系统

2．单用户多任务操作系统（windos）

3．多用户多任务操作系统（linux）

并发是指两个或多个事件在同一时间间隔内发生。这些事件在宏观上是同时发生的，在微观上是交替发生的。（把并发想成串行就好理解了）

易混淆的概念——并行：两个或多个事件在同一时刻同时发生

共享即资源共享，是指系统中的资源内存中多个并发执行的进程共同使用。

所谓的“同时”往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的(即分时共享)

生活实例:

互斥共享方式:使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程。

同时共享方式:使用QQ发送文件A，同时使用微信发送文件B。宏观上看，两边都在同时读取并发送文件，说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

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

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

指令

由于内核划分功能的不同，内核分为大内核和微内核。

大内核和微内核的优缺点

类比:

操作系统的体系结构问题与企业的管理问题很相似。

内核就是企业的管理层，负责一些重要的工作。只有管理层才能执行特权指令，普通员工只能执行非特权指令。用户态、核心态之间的切换相当于普通员工和管理层之间的工作交接

大内核:企业初创时体量不大，管理层的人会负责大部分的事情。优点是效率高;缺点是组织结构混乱，难以维护。

微内核:随着企业体量越来越大，管理层只负责最核心的一些工作。优点是组织结构清晰，方便维护;缺点是效率低。

1.概念和作用

中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行。

当中断发生时，CPU立即进入核心态

当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理。

对于不同的中断信号，会进行不同的处理。

有了中断，才能实现多道程序并发执行。

“用户态→核心态”是通过中断实现的，并且中断是唯一途径。“核心态→用户态”的切换是通过执行一个特权指令，将程序状态字（ PSW）的标志位设置为 “用户态”。

2.分类

中断信号的来源来自CPU内部称为内中断，外部称为外中断。

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。

应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如存储分配、I/o操作、文件管理等），都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

编程语言（c,java）中里边有很多库函数，其实它们（不是所有的库函数）就是将系统调用封装起来，隐藏一些细节，使上层进行系统调用更加方便。

系统调用发生在用户态，对系统调用的处理发生在核心态。

执行陷入指令（自陷指令或访管指令）会处理内中断，使处理器（CPU）从用户态进入核心态。

通过任务管理器我们可以发现每个进程不仅仅只有cpu内存磁盘的占用率也是有唯一用来表示进程的PID（process id）

程序的运行过程：

进程特征：

总结：

进程是程序的一次执行。在这个执行中，进程的状态有各种变化。为了方便进程管理，把进程分为了，运行态，就绪态，阻塞态、创建态、终止态五种状态。

组织也就是调用的方式

链式

索引

进程控制的含义：进程控制就是要用来实现进程状态的转化的

进程控制的实现：进程控制由原语实现。所谓原语，一般是指由若干条指令组成的程序段，用来实现某个特定功能，在执行过程中不可被中断。原语采用 “关中断指令” 和 “开中断指令” 来实现。 注意： 原语运行在核心态。

那么原语是如何实现进程状态的转换呢？

程序的运行

含义：进程通信就是进程之间的信息交换。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。所以操作系统就提供了三种方法使得进程可以进行信息交换。

1.共享存储

2.消息传递

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

3.管道通信

1.管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

2.各进程要互斥地访问管道。

3.数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取后，管道变空，此时读进程的read()系统调用将被阻塞。

4.如果没写满，就不允许读。如果没读空，就不允许写。

5．数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况。

有的进程需要同时做很多事，例如用QQ来进行聊天，发送文件等，而传统的进程只能串行执行一系列程序。因此，引入“线程”，来增加并发度。

内核级线程的管理工作由操作系统内核完成。线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

可以这样理解，“内核级线程”就是“从操作系统内核视角看能看到的线程”。

操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

线程模型分为三种：一对一、多对一、多对多

一对一模型

多对一模型

多对一模型:多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。

优点:用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点:当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

多对多模型

首先我们需要认知的是作业和进程的区别是什么：

作业是用户需要计算机完成的某项任务。一个作业的完成要经过作业提交、作业收容、作业执行和作业完成四个阶段。而进程是对已提交完毕的程序所执行过程的描述。

1.作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业作业后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。

2.一个作业可由多个进程组成，且必须至少由一个进程组成，反过来不成立。

3.作业的概念主要用在批处理系统中，像UNIX这样的分时系统中就没有作业的概念。而进程的概念则用在几乎所有的多道程序系统中。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

调度分为三个层次，分别为高级调度，中级调度，初级调度。

临界资源： 一个时间段内只允许一个进程使用的资源。各进程需要互斥的访问临界资源。

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

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列。

优点：实现简单,系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

优点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统

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

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

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

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

可以看下面调度算法的例题来理解其中的含义是怎么算的

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

非抢占式的作业优先算法

抢占式的作业优先算法

例题：

时间片就是分配一段时间给进程运行时间到了就会主动的放弃处理机

非抢占式

抢占式

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步”所讨论的内容。

对临界资源的互斥访问，可以在逻辑上分为如下四个部分:

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

算法思想:每个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

代码实现

上面的代码如果用turn等于0开始，如果率先得到cpu的进程使p1进程，会使p1进程卡在代码5上，（while循环满足条件虽然没有要执行的语句但是会一直卡在里面），但是当p1的时间片到了，就会给p0进程执行代码，到了p0进入临界区了，又且回到p1进程但是还是继续卡住知道执行了代码3就可以执行进程p1了，但是我们可以发现一个很明显的问题就是，在p1想先访问的时候是不可以访问的，所以这是违法了空闲让进的原则。

算法思想:设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] =ture”意味着0号进程 P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[li]设为true，之后开始访问临界区。

若按照①⑤②⑥③⑦…的顺序执行，P0和P1将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则。

原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

算法思想:双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”,但是这两个操作又无法一气呵成,因此导致了两个进程同时进入临界区的问题。因此,人们又想到先“上锁”后“检查”的方法，来避免上述问题。

算法思想:双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gary L.Peterson想到了一种方法，如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”，主动让对方先使用临界区。

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

与普通整数变量的区别：对信号量的操作只有三种，初始化，P操作，V操作。

下面以打印机为例：

整型信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构表示的信号量。

先P后V

注意： 对不同的临界资源（如摄像头，打印机）需要设置不同的互斥信号量。

P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

进程同步：要让各并发进程按要求有序的进行。

那么如何实现呢？

下面通过一个例子来解释，要求：进程2的代码4必须在进程1的代码2之后执行。

进程P1中有句代码S1，P2中有句代码S2 …P… P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作)，因此，

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

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

问题：可不可以不使用问题信号量？

.结论:即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象

原因在于:本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻,最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区…

如果盘子（缓冲区）数量为2，可能会出现两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。

在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议:在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料:烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复(让三个抽烟者轮流地抽烟)。

也就是先i=0的时候取出组合1放在桌子上然后就给finish加锁，生产者就被锁在了P（finish）处，在这之前要是有smokern在进程中了也会被P（offern）阻塞住，知道生产者告诉吸烟者才会把烟卷起来抽掉，再释放finish，生产者又可以继续的生成了就是这样的过程实现让三个抽烟者循环抽烟

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

①允许多个读者可以同时对文件执行读操作;

②只允许一个写者往文件中写信息;

③任一写者在完成写操作之前不允许其他读者或写者工作;

④写者执行写操作前，应让已有的读者和写者全部退出。

潜在的问题：只要读进程还在读，写进程就要一直堵塞等待，可能会饿死。因此在这种算法中，读进程优先。下面来实现“ 先来先服务”算法，这样就不会导致写进程饿死。

读者-写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器count用来记录当前正在访问共享文件的读进程数。我们可以用count的值来判断当前进入的进程是否是第一个/最后一个读进程，从而做出不同的处理。

另外，对count变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现“一气呵成”，自然应该想到用互斥信号量。

最后，还要认真体会我们是如何解决“写进程饥饿”问题的。

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

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

2.整理思路。这个问题中只有互斥关系，但与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。如何避免临界资源分配不当造成的死锁现象，是哲学家问题的精髓。

3.信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}，用于实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

如果使用下图所示的方法，图中方法也就是哲学家都先拿自己左边的筷子，然后等着拿自己右边的筷子，要是每个哲学家同时拿自己左边的筷子就会导致死锁问题。

那么如何解决呢？

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

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

③仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

下面用代码实现第三种方式。

1.为什么引入管程？

信号量机制存在的问题 : 编写程序困难、易出错。 因此人们想设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松。1973年，Brinch Hansen首次在程序设计语言(Pascal)中引入了“管程”成分――一种高级同步机制。

管程相当于对临界区资源进行抽象而编写的一个类。

管程是一种特殊的软件模块，有这些部分组成:

管程的基本特征:

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁“。

产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。

注意 : 发生死锁时一定有循环等待 , 但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件)

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了。

1.什么是安全序列

2.银行家算法

数据结构:

长度为m的一维数组 Available表示还有多少可用资源

nm矩阵Max表示各进程对资源的最大需求数

nm矩阵Allocation表示已经给各进程分配了多少资源

Max - Allocation = Need矩阵表示各进程最多还需要多少资源

用长度为m的一位数组Request表示进程此次申请的各种资源数

银行家算法步骤:

①检查此次申请是否超过了之前声明的最大需求数

②检查此时系统剩余的可用资源是否还能满足这次请求

③试探着分配，更改各数据结构

④用安全性算法检查此次分配是否会导致系统进入不安全状态

安全性算法步骤:

检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。

不断重复上述过程，看最终是否能让所有进程都加入安全序列。

内存是用于存放数据的硬件。程序执行之前需要先放在内存中才可以被cpu执行。

相对地址和绝对地址

编译时产生的指令只关心“相对地址”，实际放入内存中时再想办法根据起始位置得到“绝对地址”。

Eg: 编译时只需确定变量x存放的相对地址是100（也就是说相对于进程在内存中的起始地址而言的地址）。CPU 想要找到x在内存中的实际存放位置，只需要用进程的起始地址+100即可。

相对地址又称逻辑地址，绝对地址又称物理地址。

⭐⭐⭐编址方式，位 (bit)、字节 (Byte)、字 (word) 的区别

1字节=8位 也就是 1byte=8bit

1kB=1024B=2^10B

1MB=1024kB=2^20B

1GB=1024MB=2^30B

1TB=1024GB=2^40B

例题

计算机字长（word）为32位，存储容量为16MB，按字节编址和字编制的时候，它的寻址范围分别为多少？

寻址范围：存储容量/编址大小（单位都是B）

1.按照字节编址： 16MB=2^24B=2^24*8bit=2^27bit

寻址范围:  (2^27b)/8b=2^24b

2.按字寻址:     (2^27bit)/32bit=2^22bit

操作系统对内存进行管理，那么要管理哪些内容呢？

内存保护可采取两种方法:

方法一:在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

方法二:采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖技术的思想 : 将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。

内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束)不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点:对用户不透明，增加了用户编程负担。覆盖技术只用于早期的操作系统中，现在已成为历史。

交换（对换）技术的设计思想: 内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）。之前讲的中级调度（内存调度）就是为这个服务的。

1.应该在外存（磁盘）的什么位置保存被换出的进程?

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。

2.什么时候应该交换?

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。

3.应该换出哪些进程?

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…

(注意:PCB会常驻内存，不会被换出外存)

连续分配：指为用户进程分配的必须是一个连续的内存空间。

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

使用这种方式的话，我们需要考虑以下三个问题。

​ 使用动态分区算法，这个将在下一小节进行详细介绍。

动态分区分配算法:在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

算法思想: 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。

如何实现:空闲分区按容量递增次序链接。每次分配以后都要把最小的分区调到最前面。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

又称最坏适应算法(Largest Fit)

算法思想:为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现:空闲分区以地址递增的顺序排列(可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

连续分配:为用户进程分配的必须是一个连续的内存空间。

非连续分配:为用户进程分配的可以是一些分散的内存空间。

基本分页存储管理的思想――把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分。

将内存空间分为一个个大小相等的分区（比如:每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。每个页面也有一个编号，即“页号”，页号也是从0开始。

(注:进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片)

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

思考： 将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换?

如何计算:

举例:

页号=80 / 50= 1

页内偏移量=80 % 50 = 30

1号页在内存中存放的起始位置450

思考: 如何知道该页号对应页面在内存中的起始地址?

操作系统为每一个进程创建一个页表

如何理解每个页表项的长度是相同的，页号是“隐含的”？

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器(PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

页表长度是指这个页表中总共有几个页表项，即总共有多少页。页面大小是指一个页面占多大的存储空间。页表项长度是指每个页表项占多大的存储空间。

通过下面这个例子来理解页表项长度。

Eg:假设某系统物理内存大小为4GB，页面大小为4KB，内存总共会被分为2^32/ 2^12=2^20个内存块，因此内存块号的范围应该是0~2^20 - 1。因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够(每个字节8个二进制位，3个字节共24个二进制位)。每个块号用三个字节来表示。

时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢?

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

两级页表的出现主要是为了解决单级页表的问题。那么单级页表有什么问题呢？

问题一:页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。

问题二:没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

1.解决问题一

我们可以回想以下当初是如何解决进程必须连续的问题 ？

我们可以把页表放在不同的页框中，再用一个表来记录各个各个子页表所在位置，我们把这个表叫做页目录表（外层页表，顶级页表）。

2.解决问题二

3. 其他细节

注意页表项是放在页面里面的一个结构，所以我们可以通过页面大小/页面项大小算出可以放多少个页表项

N级页表访问一个逻辑地址需要N+1次访问内存。

进程的地址空间:按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程)，每段从0开始编址。

内存分配规则 : 以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

段号的位数决定了每个进程最多可以分几个段。

段内地址位数决定了每个段的最大长度是多少。

既然两者都有优缺点，那么可不可以把他们结合起来呢？答案当然是可以的。如下图所示。

段号的位数决定了每个进程最多可以分几个段

页号位数决定了每个段最大有多少页

页内偏移量决定了页面大小、内存块大小是多少

易混知识点:

虚拟内存的最大容量是由计算机的地址结构（ CPU寻址范围）确定的

虚拟内存的实际容量= min(内存和外存容量之和，CPU寻址范围)

如: 某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB.

则虚拟内存的最大容量为2^32B= 4GB 。 虚拟内存的实际容量=min (2^32B,512MB+2GB)= 2GB+512MB

虚拟内存有一下三个主要特征:

虚拟内存的实现需要建立在离散分配的内存管理方式基础上。

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，

因此页表会增加四个字段来上面的信息。

假设此时要访问逻辑地址 = (页号，页内偏移量）= (0，1024)

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

一条指令在执行期间，可能产生多次缺页中断。(如: copy AtoB，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

①只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。

②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。

③需要用某种“页面置换算法”来决定一个换出页面（下节内容)

④换入/换出页面都需要启动慢速的I/o操作，可见，如果换入/换出太频繁，会有很大的开销。

⑤页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。

最佳置换算法（OPT，Optimal):每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的（在计算机的角度上）。

先进先出置换算法（FIFO):每次选择淘汰的页面是最早进入内存的页面

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

Belady异常―一当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

最近最久未使用置换算法（LRU，least recently used):每次淘汰的页面是最近最久未使用的页面。

实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差;最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，NotRecently Used)

简单的CLOCK 算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/o操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/o操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1)表示一个页面近期被访问过，且被修改过。

算法规则: 将所有可能被置换的页面排成一个循环队列

第一轮:从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位

第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0

第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0，0）的帧用于替换。本轮扫描不修改任何标志位

第四轮:若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。

由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描

驻留集:指请求分页存储管理中给进程分配的物理块的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际上用于进程推进的时间很少。

驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

下面来分别介绍这几种方式。

可变分配全局置换:只要缺页就给分配新物理块

可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块

1．预调页策略:根据局部性原理（主要是空间局部性），一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。它是运行前调入。

2．请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘l/o操作，因此I/o开销较大。它是运行时调入。

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够)。

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率

为了研究为应该为每个进程分配多少个物理块，Denning提出了进程“工作集”的概念。

驻留集:指请求分页存储管理中给进程分配的内存块的集合。

工作集:指在某段时间间隔里，进程实际访问页面的集合。

一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。

文件分为有结构文件和无结构文件。

操作系统向上（用户和应用程序）提供的功能

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如:Windows操作系统中的.txt文件。

有结构文件:由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如:数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID)

我们主要研究有结构文件。

顺序文件:文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储（相当于数组）或链式存储（相当于链表）。

顺序存储又可以分为串结构和顺序结构。

那么这几种存储方式可以快速找到第i个记录对应的地址呢？

结论:定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取;若能再保证记录的顺序结构，则可实现快速检索(即根据关键字快速找到对应记录)

简单的说也就是在顺序表的基础上加上一个指针可以直接指向不定长的顺序表。

思考：对于可变长记录文件，要找到第i个记录，必须先顺序第查找前i-1个记录,但是很多应用场景中又必须使用可变长记录。如何解决这个问题?

这时我们可以建立一张索引表来快速找到第i个记录。如图所示：

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。

每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不同的数据项建立多个索引表。如:学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。(Eg: SQL就支持根据某个数据项建立索引的功能)

思考索引文件的缺点:每个记录对应一个索引表项，因此索引表可能会很大。比如:文件的每个记录平均只占8字节，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

那么如何解决呢？

我们可以建立一个索引顺序文件。

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是:并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

在本例中，学生记录按照学生姓名的开头字母进行分组。每个分组就是一个顺序文件，分组内的记录不需要按关键字排序。

为了进一步提高检索效率，可以为顺序文件建立多级索引表。

例如，对于一个含10^6个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项(即10000个定长记录)，再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。

FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等)，使用信息（如文件的建立时间、修改时间等）。

最重要，最基本的还是文件名、文件存放的物理地址。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享同一目录下的所有内容）。

需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。

只有共享计数器减为0时，才删除结点。

注意:共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如:文件是否被修改、此时有几个进程正在访问该文件等。

在介绍这些分配方式之前，先介绍一下什么是文件块，磁盘块。

在内存管理中，进程的逻辑地址空间被分为一个一个页面。

同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。

用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。

连续分配方式要求每个文件在磁盘上占有一组连续的块。如图所示

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

物理块号=起始块号＋逻辑块号（类似内存的页面的计算就好了）

当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号≥长度就不合法)、

优点:支持顺序访问和直接访问（即随机访问)；连续分配的文件在顺序访问时速度最快

缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

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

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

因此，读入i号逻辑块，总共需要i+1次磁盘l/O。

结论:采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table)。如图所示

注意:一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

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

从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

结论:采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的 0~i-1号逻辑块)，由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

最大的区别就是一个是有一个单独的表，一个是用指针的方式

隐式链接――除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

显式链接――把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表――建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

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

从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知道i号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配一个空闲块，并增加一个索引表项即可)

但是索引表需要占用一定的存储空间

如果一个文件的索引表太大，一个磁盘块放不下，那么如何解决呢？

可以用以下三种方式解决。

①链接方案:如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

②多层索引:建立多层索引（原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

③混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引（指向两层索引表)。

总结

①链接方案 : 如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。

②多层索引:建立多层索引(原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。缺点:即使是小文件，访问一个数据块依然需要K+1次读磁盘。

③混合索引:多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点:对于小文件来说，访问一个数据块所需的读磁盘次数更少。

存储空间的划分:将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)。所谓的文件卷就相当于电脑上的C盘，D盘等。

为一个磁盘创建一个表，来存储空闲磁盘块的位置。

如何分配磁盘块 : 与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况―—①回收区的前后都没有相邻空闲区;②回收区的前后都是空闲区;③回收区前面是空闲区;④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。

空闲链表发分为空闲盘块链和空闲盘区链。

位示图:每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号）对应一个盘块号。当然有的题目中也描述为（行号，列号)

(字号,位号)=(i j) 的二进制位对应的盘块号 b= ni + j

b号盘块对应的字号i = b/n，位号j = b%n。

如何分配:若文件需要K个块，

①顺序扫描位示图，找到K个相邻或不相邻的“0”;

②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;

③将相应位设置为“1”。

如何回收:

①根据回收的盘块号计算出对应的字号、位号;

②将相应二进制位设为“0”。

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。

文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。如图所示。

如何分配?

Eg :需要100个空闲块

①检查第一个分组的块数是否足够。100=100，是足够的。

②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中。

Eg :需要1个空闲块

①检查第一个分组的块数是否足够。10，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。当count =0时系统负责删除文件。

软链接只是执行文件的地址

当User3访问“ccc”时，操作系统判断文件“ccc”属于Link类型文件，于是会根据其中记录的路径层层查找目录，最终找到User1的目录表中的“aaa”表项，于是就找到了文件1的索引结点。类似于快捷方式。

为文件设置一个“口令”(如: abc112233），用户请求访问该文件时必须提供“口令”。

口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件。

优点:保存口令的空间开销不多，验证口令的时间开销也很小。

缺点:正确的“口令”存放在系统内部，不够安全。

使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

Eg:一个最简单的加密算法――异或加密。

假设用于加密/解密的“密码”为“01001”。

在每个文件的FCB（或索引结点）中增加一个访问控制列表(Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。如图所示：

在windows中也就是：

精简的访问列表:以“组”为单位，标记各“组”用户可以对文件执行哪些操作。如:分为系统管理员、文件主、文件主的伙伴、其他用户几个分组。当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。

用一个例子来辅助记忆文件系统的层次结构:

假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。

①根据“柱面号”移动磁臂，让磁头指向指定柱面;

②激活指定盘面对应的磁头;

③磁盘旋转的过程中，指定的扇区会从磁头下面划过，这

①启动磁头臂是需要时间的。假设耗时为s;

②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。则:

寻道时间Ts = s + mn

1/r就是转一圈需要的时间。找到目标扇区平均需要转半圈，因此再乘以1/2

每个磁道要可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r。

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。但是操作系统的磁盘调度算法会直接影响寻道时间。

SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优)

SSTF算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

扫描算法（SCAN)中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。(边移动边观察，因此叫LOOK)。

SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

假设要连续读取橙色区域的2、3、4扇区:

磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停地旋转

因此，如果2、3号扇区相邻着排列，则读完2号扇区后无法连续不断地读入3号扇区

必须等盘片继续旋转，3号扇区再次划过磁头，才能完成扇区读入。

结论:磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。如图所示。

思考:为什么磁盘的物理地址是（柱面号，盘面号，扇区号)，而不是(盘面号，柱面号，扇区号)？

答:读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间

磁盘初始化:

Step 1:进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误)

Step 2:将磁盘分区，每个分区由若干柱面（磁道）组成（即分为我们熟悉的C盘、D盘、E盘)

step 3:进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表)

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序（自举程序）完成的。

初始化程序可以放在ROM(只读存储器）中。ROM中的数据在出厂时就写入了，并且以后不能再修改 。

初始化程序程序（自举程序）放在ROM中存在什么问题?万一需要更新自举程序，将会很不方便，因为ROM中的数据无法更改。如何解决呢?

ROM中只存放很小的“自举装入程序”。开机时计算机先运行“自举装入程序”，通过执行该程序就可找到引导块，并将完整的“自举程序”读入内存，完成初始化

完整的自举程序放在磁盘的启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置。

拥有启动分区的磁盘称为启动磁盘或系统磁盘（c:盘)

在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。

会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

i设备：鼠标、键盘、写字板、麦克风

o设备：显示器、耳机

输入输出设备：云盘

CPU无法直接控制l/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制。

这个电子部件就是I/O控制器，又称设备控制器。CPU可控制I/o控制器，又由I/O控制器来控制设备的机械部件。

流程图

虽然中断驱动方式解决了程序直接控制方式的问题，但是每一次只能读/写一个字，导致CPU频繁切换，耗费了很多时间。于是人们又发明了DMA方式。

通道控制方式是为了解决DMA方式连续存储的问题

设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现。

主要功能：

设备独立性软件需要通过“逻辑设备表（LUT，Logical UnitTable）”来确定逻辑设备对应的物理设备，并找到该设备对应的设备驱动程序。如图所示：

操作系统系统可以采用两种方式管理逻辑设备表(LUT) :

第一种方式，整个系统只设置一张LUT，这就意味着所有用户不能使用相同的逻辑设备名，因此这种方式只适用于单用户操作系统。

第二种方式，为每个用户设置一张LUT，各个用户使用的逻辑设备名可以重复，适用于多用户操作系统。系统会在用户登录时为其建立一个用户管理进程，而LUT就存放在用户管理进程的PCB中。

思考:为何不同的设备需要不同的设备驱动程序?

不同设备的内部硬件特性也不同，这些特性只有厂家才知道，因此厂家须提供与设备相对应的驱动程序，CPU执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作。

当I/o任务完成时，I/o控制器会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。中断处理程序的处理流程如下:

I/O调度:用某种算法确定一个好的顺序来处理各个I/o请求。

如:磁盘调度（先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。

当多个磁盘I/o请求到来时，用某种调度算法确定满足I/o请求的顺序。

同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定IV/o调度顺序。

操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限（如:只读、读和写等）。

在UNIx系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。(参考“文件保护”小节)

Tips:为什么称为“脱机”？一脱离主机的控制进行的输入/输出操作。

“假脱机技术”，又称“SPOOLing 技术”，用软件的方式模拟脱机技术。SPOQLing系统的组成如下:

要实现SPOOLing 技术，必须要有多道程序技术的支持。系统会建立“输入进程”和“输出进程”。

设备的固有属性可分为三种:独占设备、共享设备、虚拟设备。

先来先服务，优先级高者优先，短任务优先…

从进程运行的安全性上考虑，设备分配有两种方式:

安全分配方式:为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。(eg:考虑进程请求打印机打印输出的例子)

不安全分配方式:进程发出I/o请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/o请求。只有某个l/o请求得不到满足时才将进程阻塞。

静态分配:进程运行前为其分配全部所需资源，运行结束后归还资源。破坏了“请求和保持”条件，不会发生死锁

动态分配:进程运行过程中动态申请设备资源

“设备、控制器、通道”之间的关系:

①根据进程请求的物理设备名查找SDT（注:物理设备名是进程请求分配设备时提供的参数)

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

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

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

注∶只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可后动/O设备进行数据传送。

缺点:

①用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程

②若换了一个物理设备，则程序无法运行

③若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

改进方法:建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名

①根据进程请求的逻辑设备名查找SDT(注:用户编程时提供的逻辑设备名其实就是“设备类型”)

②查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT)中新增一个表项。

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

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

逻辑设备表

含义

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本)

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区

作用

假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。如图所示

注意:当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出;当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块)。