【专题】操作系统期末复习资料

一、绪论

（★ ★）操作系统基本概念：操作系统的功能，特征，层次结构。

操作系统的地位。

操作系统作为裸机和应用的中间层；

提供资源管理功能和方便用户的各种服务功能；

将裸机改造成功能更强、使用更为方便的的机器；

各种应用程序运行在操作系统之上，向用户提供其需求所需的各种服务。

操作系统的层次结构。（分层结构）【FOCUS】

目的：

改善模块间毫无规则的相互调用、相互依赖的关系

将系统所有功能模块按调用次序排成若干层

将操作系统分为多层 (levels)。

每层建立在低层之上；

最底层(layer 0), 是硬件；

最高层(layer N) 是用户界面。

每一层仅使用更低一层的功能（操作）和服务。

特点：

模块间组织依赖关系清晰

系统的可读性、适用性和稳定性都得到增强

如果修改只影响上下两层，便于修改和扩充

操作系统的特征。【FOCUS】

并发性。

并行性：两个以上事件同一时刻发生

并发性：两个以上事件同一时间间隔内发生

单处理系统中微观上程序交替执行

并发性能提高资源利用率

使系统复杂化

共享性。

系统资源不再为某个程序独占。

并发与共享互为存在条件

互斥共享（打印机，程序数据）

同时共享（动态链接库（只读））

并发性和共享性是操作系统最基本的两个特征。

虚拟性。

把一个物理上的实体变为若干个逻辑上的对应物，让用户感觉独自占用某资源

时分复用与空分复用

例如：CPU的分配

异步性。

多道程序中，资源受限

程序运行“走走停停”推进速度不可预知

OS需保证程序运行结果一致

操作系统的功能。【FOCUS】

处理机管理。

多道程序环境下处理器的分配和运行以进程为单位。

进程控制：进程的创建，撤销及状态转换

进程同步：对并发的进程进行协调

进程通信：负责完成进程间的信息交换

进程调度：按一定算法进行处理器分配

存储器管理。

内存分配：按一定策略为每道程序分配内存

内存保护：保证程序在自己的内存区域内运行而不相互干扰

内存扩充：虚拟存储技术，扩大内存效果

设备管理。

通道、控制器和输入输出设备的分配和管理（缓冲技术、虚拟技术）

保证设备独立性（设备的启动、中断、结束）

文件管理（信息管理）。

存储空间管理：空间的分配与回收

目录管理：存储、检索

文件操作管理：文件创建、读写、授权、关闭等

文件保护：防止文件遭到破坏

用户接口。

命令接口：提供一组命令供用户直接或间接控制自己的作业

程序接口：即系统调用，系统提供一组调用命令，供用户程序和其他系统程序调用

图形接口：联机命令接口的图形化

（★）操作系统发展过程、分类及每种操作系统的特征。【FOCUS】

单用户。（计算资源有限）

无操作系统

用户独占全机

CPU等待人工操作（纸带或卡片）

问题：昂贵组件的低利用率。

顺序执行与批处理。（提高CUP利用率）

单道批处理特点：

自动性：磁带上的一批作业可以按照顺序依此自动进行，无需人工干预

顺序性：先调入内存的作业先完成

单道性：内存内只有一道运行程序，只有异常或运行结束才换入后续程序

多道程序系统。（多用户共享计算资源）

保持多个工作在内存中并且在各工作间复用CPU。

特点：

多道：多个程序在内存中

宏观并行

微观串行：CPU轮转

分时系统。（提高用户体验，短作业提前结束）

分时操作系统的特点：

多路性：一台计算机与若干台终端连接，终端上的用户可以同时，或基本同时使用计算机

交互性：分时操作系统中的用户的操作方式是联机操作方式，即用户通过终端采用人机对话的方式直接控制程序执行

独占性：采用时间片轮转的方法使得一台计算机同时为多个终端使用（通常能再2~3秒内响应用户请求），客观效果是这些用户彼此之间都感觉不到别人也在使用计算机

及时性：系统能够在较短时间内响应用户需求。

实时系统。

主要特点：提供即时响应和高可靠性

实时信息处理系统：订票、监控系统等

实时控制系统：炼油、化工生产控制系统等

需要考虑的因素：

实时时钟管理（定时处理和延时处理）

连续人机对话

过载保护

冗余措施：保障可靠性和安全性。

通用操作系统。（每个用户一个系统（图形界面，易用性））

个人电脑系统的特点：

单用户；

利用率已不再是关注点；

重点是用户界面和多媒体功能；

很多老的服务和功能不存在。

分布式操作系统。（每个用户多个系统（安全、协同））

（★ ★ ★）操作系统的软硬件运行环境：内核态与用户态的区别，中断和异常的区别，系统调用的概念。

内核态与用户态的区别。【FOCUS】

核心态。（内核态）

又称管态、系统态，是操作系统管理程序执行时机器所处的状态。

具有较高的特权，能执行包括特权指令和一切指令，能访问所有寄存器和存储区。

内核程序运行在核心态

用户态。

又称目态，是用户程序执行时机器所处的状态。

具有较低特权的执行状态，只能执行规定的指令，能访问指定寄存器和存储区。

用户态程序不能直接调用核心态程序，需执行访问核心态的命令，引起中断，由中断系统转入操作系统内的相应程序。

自编程序运行在用户态

内核态和用户态的区别。

权限级别：

内核态：是操作系统的一种特权模式，也称为内核模式或内核空间。在这种状态下，CPU可以执行任何指令，包括直接与硬件交互的指令。内核态允许操作系统核心访问所有的内存和设备，执行关键系统任务。

用户态：是对普通应用程序的限制模式，也称为用户模式或用户空间。在用户态下，程序不能直接访问硬件或执行某些受限指令。这种模式下的程序只能通过操作系统提供的接口（如API）间接访问硬件和资源。

功能职责：

内核态：主要负责管理硬件资源，包括内存管理、进程调度、文件系统操作、设备驱动等。这些功能都是操作系统核心的部分，需要高权限来执行。

用户态：主要运行应用程序，如文本编辑器、游戏等。这些程序无法直接执行硬件操作，必须通过操作系统提供的服务来完成。

资源访问：

内核态：可以访问系统的所有资源，包括所有内存和硬件设备。这种无限制的访问权限使得内核态能够高效地管理系统资源。

用户态：程序只能访问它们被授权的资源，无法直接访问关键系统资源。这种限制是为了保护系统免受恶意程序的攻击。

运行速度与效率：

内核态：由于内核态程序直接与硬件交互，并且没有权限限制，因此它们通常运行得更快。

用户态：用户态程序需要通过系统调用与硬件交互，这增加了额外的开销，因此运行效率相对较低。

中断和异常的区别。

系统内核工作在核心态，而用户程序工作在用户态，系统不允许用户态程序实现核心态的功能，而它们又必须使用这些功能。中断和异常就是用户态进入核心态的途径。是通过硬件实现的。

中断：

也称外中断，指来自CPU执行指令以外的事件的发生，导致CPU跳转。

IO结束中断，表示IO操作已结束，CPU可执行IO之后的后续操作

时钟中断，表示固定时间片已到，让处理机处理计时，启动定时运行的任务

异常：

也称内中断，源自CPU执行指令的内部事件。如非法操作、地址越界、文件损坏等。

异常不能被屏蔽，一旦出现应立即处理

异常通常会引起中断，但是中断不一定是由异常引起的。

中断和异常的区别：

产生原因

中断：中断是由外部设备或某些内部事件（但与当前执行的指令无关）触发的。例如，当外部设备（如键盘、打印机）需要CPU服务时，会向CPU发送中断信号。此外，某些内部事件（如时钟中断）也会定期触发中断，以通知CPU执行特定的任务。

异常：异常是由当前正在执行的指令直接引起的。例如，当程序尝试访问非法的内存地址或执行无效的操作码时，会触发异常。异常通常表示程序中的错误或异常情况。

处理方式

中断：当中断发生时，CPU会暂停当前正在执行的程序，并跳转到中断处理程序（也称为中断服务程序）执行。中断处理程序负责处理中断事件，并在处理完毕后返回被中断的程序继续执行。中断处理过程通常由硬件和操作系统共同完成。

异常：当异常发生时，CPU也会暂停当前正在执行的程序，但会跳转到异常处理程序执行。异常处理程序负责处理异常事件，并根据异常类型进行相应的处理。例如，对于非法内存访问异常，异常处理程序可能会终止程序执行并输出错误信息；对于除零异常，异常处理程序可能会进行错误修正或输出警告信息。

优先级和嵌套性

中断：中断的优先级通常是由硬件决定的，不同的中断源可能有不同的优先级。在中断处理过程中，允许嵌套发生其他中断（即中断中断），但具体的嵌套规则取决于硬件和操作系统的设计。

异常：异常的优先级通常由操作系统或程序本身决定。在异常处理过程中，通常不允许嵌套发生其他异常（即异常异常），因为异常处理本身就是为了处理程序中的错误或异常情况。

对程序的影响

中断：中断是异步的，即它可能在任何时候发生，与当前执行的指令无关。因此，中断的发生可能会打断程序的正常执行流程，但中断处理程序在处理完毕后通常会恢复被中断的程序继续执行。

异常：异常是同步的，即它发生在当前执行的指令执行期间。异常的发生通常会导致程序执行流程的中断，并可能需要程序进行错误处理或终止执行。

应用场景

中断：中断在操作系统、设备驱动程序、实时控制系统等领域有广泛应用。例如，在操作系统中，中断用于实现进程调度、内存管理、设备I/O等操作；在实时控制系统中，中断用于实现实时响应和处理。

异常：异常在程序调试、错误处理、程序安全性等领域有重要应用。例如，在程序调试过程中，异常可以帮助开发者发现程序中的错误和漏洞；在错误处理过程中，异常可以帮助程序进行错误修正或输出错误信息；在程序安全性方面，异常可以用于防止程序执行非法操作或访问非法资源。

系统调用的概念。

系统调用就是用户在程序中调用操作系统提供的一些子功能，系统调用可以被看作是特殊的公共子程序。

在用户程序中凡是与资源有关的操作都必须通过调用的方式向操作系统提出服务请求并由操作系统代为完成。

系统调用运行在系统的核心态。

系统调用按功能大致分为如下几类：

设备管理：完成设备的请求和释放，以及设备启动等功能

文件管理：完成文件读、写、创建和删除等功能

进程控制：完成进程创建、撤销、阻塞、唤醒等功能

进程通信：完成进程间的消息传递或信号传递等功能

内存管理：完成内存的分配、回收以及获取作业占用内存区大小及初始地址等功能

（★）操作系统体系结构的基本概念

操作系统（Operating System，OS）的基本概念。

是配置在计算机硬件上的第一层软件;

是对硬件系统的首次扩充;

其主要作用是管理好这些设备，提高他们的利用率和系统的吞吐量，并为用户和应用程序提供一个简单的接口，便于公户使用。

操作系统是一个控制程序，一个系统软件。

控制程序执行过程，防止错误和计算机的不当使用；

执行用户程序，给用户程序提供各种服务；

方便用户使用计算机系统。

操作系统是一个资源管理器。

应用程序与硬件之间的中间层；

管理各种计算机软硬件资源；

提供访问计算机软硬件资源的高效手段；

解决资源访问冲突，确保资源公平使用。

二、进程管理

2.1 进程与线程

（★ ★ ★ ）进程的概念、进程与程序的异同、进程的组织结构（PCB的构造与功能）

程序的概念。

程序(Program)

描述计算机所要完成的具有独立功能的，并在时间上按严格次序前后相继的计算机操作序列的集合。

程序的顺序执行

顺序性：一条接着一条执行，上一条结束是下一条开始的必要条件件封闭性；最终结果由初始条件决定，不受外界因素影响可

再现性：最终结果与执行速度和执行的时间无关，重复执行应得到一样的结果。

进程的概念。【FOCUS】

进程实体由程序段、数据段和PCB来表示，其中PCB是进程存在的唯一标识，程序段是进程运行程序的代码，数据段则存储程序运行过程中相关的一些数据。

进程是程序在处理器上的一次执行过程。

进程是可以和别的进程并行执行的计算。

进程是程序在一个数据集上的运行过程，是系统进行资源分配和调度的一个独立单位。

进程是一个程序关于某个数据集合在处理器上顺序执行所发生的活动。

程序和进程的异同。【FOCUS】

进程是一个动态概念，程序是一个静态概念

进程具有并发性，而程序没有。程序不反映执行过程

进程是竞争计算机资源的基本单位

同一个程序可以开启多个进程

联系：

进程，是操作系统处于执行状态的程序的抽象

程序 = 文件（静态的可执行文件）

进程 = 执行中的程序

同一个程序多次执行过程对应为不同进程

如，一台电脑登录多个QQ号

进程的执行需要资源

内存：保存代码和数据

CPU：执行指令

区别：

进程动态的，程序是静态的

程序是有序代码的集合

进程是程序的执行，进程有核心态和用户态

进程是暂时的，程序是永久的

进程是一个状态变化的过程

程序是可以长期保存的

进程与程序的组成不同

进程的组成包括：程序，数据和进程控制块

进程的组织结构。

进程控制块。

进程创建时，操作系统新建一个PCB结构，之后它常驻内存，任意时刻可存取

进程执行时，操作系统通过PCB了解进程的运行状态

进程结束时，系统回收PCB

PCB是进程实体的一部分，是进程存在的唯一标识。

进程的组织。

链表：

同一状态的进程其PCB成一链表，多个状态对应多个不同的链表

各状态的进程形成不同的链表：就绪链表、阻塞链表

索引表：

同一状态的进程归入一个索引表（由索引指向PCB），多个状态对应多个不同的索引表

各状态的进行形成不同的索引表：就绪索引表、阻塞索引表

PCB的构造和功能。【FOCUS】

进程控制块的构造

进程标识符：每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。例如，UNIX系统中就是一个整型数，在进程创建时由系统赋予。

进程当前状态：说明进程当前所处的状态，例如，可以是new（新建）、ready（就绪）、running（运行）、waiting（等待）或blocked（阻塞）等。为了管理的方便，系统设计时会将相同状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等。

进程程序和数据地址：以便把PCB与其程序和数据联系起来。

进程资源清单：列出所拥有的除CPU外的资源记录，如拥有的I/O设备，打开的文件列表等。

进程优先级：进程的优先级反映进程的紧迫程度，通常由用户指定和系统设置。例如，UNIX系统采用用户设置和系统计算相结合的方式确定进程的优先级。

CPU现场保护区，进程同步与通信机制，队列链接信息。

进程控制块的功能

记录进程信息：PCB记录了进程的有关信息，以便操作系统的进程调度程序对进程进行调度。这些信息包括标志信息、说明信息、现场信息和管理信息等。

标志进程存在：PCB是进程存在的唯一标志。操作系统通过PCB来感知和管理进程，确保进程能够正确地被创建、执行和销毁。

支持进程调度：PCB中包含了与进程调度相关的信息，如进程状态、优先级等。这些信息使得操作系统能够根据一定的调度算法，选择合适的进程进行执行，从而实现资源的有效利用和系统的并发性。

支持进程切换：在进程切换时，操作系统需要保存当前进程的状态信息，并恢复下一个进程的状态信息。PCB中保存了进程的现场信息，使得操作系统能够在不同进程之间快速切换，从而实现多任务处理。

支持进程同步与通信：PCB中包含了进程同步与通信所需的机制，如信号量等。这些机制使得进程之间能够进行协调的工作，避免资源的冲突和竞争。

（★ ★ ★ ）线程的概念及其与进程的异同

线程的概念。

线程是轻量级的进程，是基本的CPU执行单元，是程序执行流的最小的单位

由线程ID、程序计数器、寄存器集合和堆栈组成

是被系统独立调度和分派的基本单位

可以创建、撤销另一个线程

线程自己不拥有系统资源，但他与其他属于同一个进程的线程共享进程的全部资源

线程也有就绪、阻塞和运行三种基本状态

线程的优缺点。

线程的优点：

一个进程中可以同时存在多个线程

各个线程之间可以并发地执行

各个线程之间可以共亨地址空间和文件等资源

线程的缺点:

一个线程崩溃，会导致其所属进程的所有线程崩溃

线程的特点。

轻型实体

只拥有必不可少的资源，如：线程状态，寄存器上下文和栈

独立调度和分派的基本单位

具有就绪、阻塞和执行三种基本状态

创建、终止时间比进程短

线程切换系统开销小

可并发

不同进程内的线程并发执行

不同进程间的线程并发执行

共享进程资源

共享进程的资源和文件

进程切换可不通过内核直接通信

线程与进程的异同。

线程 = 进程 - 共享资源

进程是资源分配单位，线程是CPU调度单位

进程拥有一个完整的资源平台，而线程只独享指令流执行的必要资源，如寄存器和栈

线程具有就绪、等待和运行三种基本状态和状态间的转换关系

线程能减少并发执行的时间和空间开销口

线程的创建时间比进程短

线程的终止时间比进程短

同一进程内的线程切换时间比进程短

由于同一进程的各线程间共享内存和文件资源可不通过内核进行直接通信

进程、线程和程序之间的区别联系。【FOCUS】

区别：

程序：

是一组指令的集合，是静态的实体，本身不具有运行的含义。

它是应用程序的一个执行过程的描述，存储在计算机系统的硬盘等存储空间中。

进程：

是程序在某个数据集上的执行，是一个动态的实体，具有自己的生命周期。

进程是系统进行资源分配和调度的基本单位，每个进程都有自己的代码空间和数据空间。

一个进程可以包含多个线程，并且至少有一个主线程。进程在执行过程中拥有独立的内存单元。

线程：

是进程中的一个执行单元，是进程内调度实体，比进程更小的能独立运行的基本单位。

线程共享进程所拥有的资源，但每个线程都有自己的执行堆栈和程序执行上下文。

线程不能独立执行，必须依存于应用程序中，由应用程序提供多个线程执行控制。

联系：

程序与进程：

程序是进程的基础，进程是程序的一次执行活动。程序需要加载到内存中，由操作系统分配资源后才能执行，这时就产生了进程。

一个程序可以对应多个进程，例如在不同的数据集上运行时会生成不同的进程。

进程与线程：

进程是线程的容器，一个进程可以包含多个线程。

线程共享进程所拥有的资源，这使得多线程程序能够更高效地利用系统资源。

进程和线程都是操作系统进行资源分配和调度的基本单位，但线程的调度粒度更细，并发性更高。

程序与线程：

程序通过线程在处理器上执行，线程是程序内部具有并发性的顺序代码流。

线程的存在使得程序能够同时执行多个任务，提高了程序的运行效率。

（★ ★ ★ ）进程的三状态及其转换，引起进程转换的经典事件

进程的五状态及其转换。【FOCUS】

进程的七状态及其转换。【FOCUS】

引起进程转换的经典事件。

挂起。

进程从内存到外存

就绪挂起：从活动就绪到静止就绪。

高优先级阻塞程序 > 低优先级就绪程序，挂起低优先级进程

阻塞挂起：从活动阻塞到静止阻塞。

无程序处于就绪状态，或者就绪进程要求更多内存资源时，挂起阻塞进程，以提交新进程或者运行就绪进程。

从运行到就绪挂起：

对于抢占式系统，当有高优先级阻塞进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态。

执行的进程暂停

就绪的进程不再调度

阻塞的进程即使事件出现也不调度

激活。

进程从外存到内存

就绪激活：从静止就绪到活动就绪。

没有就绪进程或静止就绪进程的优先级高于就绪进程

阻塞激活：从静止阻塞到活动阻塞。

当一个进程释放足够内存时，系统会把高优先级的静止阻塞激活

事件出现。

进程等待的事件出现，如操作完成，申请成功等

阻塞到就绪：针对内存进程的事件出现

静止阻塞到静止就绪：针对外存进程的事件出现

2.2 处理机调度

（★ ★ ★ ）处理机三级调度及之间的比较

处理机调度概念。

处理机调度是对处理机（CPU）进行分配，就是从就绪队列中，按照一定的算法（公平，高效）选择一个进程并将处理机分配给他运行，以实现进程并发地执行。

处理机调度的层次。【FOCUS】

作业调度（宏观调度、高级调度、长程调度）

调度对象是作业

按一定原则从外存上处于后备状态的作业中挑选一个（或多个）作业，给他们分配内存，输入输出设备等必要资源，并建立相应进程，以使他们获得竞争处理机的权利。

是内存与辅助存储之间的调度。

每个作业只调入一次，调出一次。

多道批处理系统中大多配有作业调度，执行效率较低，一般几分钟一次

交换调度（内存调度、中级调度）

目的是为了提高内存利用率和系统吞吐量

将暂时不能运行的进程调至外存，即，挂起状态

内存空闲或运行条件具备的时候，再将其调度内存

进程调度（微观调度、低级调度、短程调度）

调度对象是进程（或内核级线程）

按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它

是操作系统最基本的一种调度

频率很高，一般几十毫秒一次

线程调度

目的是为了更高效的利用处理机与资源，增加并行性

作业和进程调度

多道系统中，存在作业调度和进程调度。分时和实时系统中，一般不存在作业调度

作业总是由一个以上的进程组成

作业是一次计算或控制过程，进程是资源分配和调度的基本单位

各级调度之间的比较

作业调度，从外存的后备队列中选择一批作业进入内存，为他们建立进程，这些进程被送入就绪队列

进程调度，从就绪队列中选出一个合适进程，把其状态改为运行状态，把CPU分配给它

交换调度，是为了提高内存利用率，系统将那些暂时不能运行的进程挂起来，当内存资源宽松时，通过交换调度原则将具备运行条件的进程唤醒

作业调度为进程活动作准备，进程调度使进程正常活动起来，交换调度将暂时不能运行的进程挂起，交换调度处于作业调度和进程调度之间

作业调度次数少，交换调度次数略多，进程调度频率最高

进程调度是最基本的，不可或缺。

（★ ★ ★ ）典型的调度算法（FCFS、SPN、HRN、RR、MFQ）

（★ ★ ★ ）进程在不同调度算法下的执行顺序的确定、周转时间、等待时间等的计算

调度算法的衡量标准【FOCUS】

CPU利用率

CPU是计算机系统中最重要和昂贵的资源之一

应尽可能使CPU保持“忙”的状态。使CPU的利用率最高

系统吞吐量

表示单位时间内CPU完成作业的数量。

长作业处理时间长，会降低系统的吞吐量

短作业处理时间短，能提高系统的吞吐量

调度方式不同，会影响系统的吞吐量

周转时间【FOCUS】

从作业提交到作业完成所经历的时间，包括作业等待、就绪等待，执行时间及输入输出时间

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

平均周转时间，是多个作业周转时间的平均值

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

带权周转时间：作业周转时间与作业实际运行时间的比值

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

平均带权周转时间：多个作业带权周转时间的平均值

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

等待时间【FOCUS】

进程处于处于等处理机状态时间之和，等待时间越长，用户满意度越低

处理机调度只影响作业在就绪队列等待所花时间

衡量一个算法的优劣，通常只考虑等待时间

响应时间

从用户提交请求到系统首次产生响应所用的时间

交互式系统中，通常使用响应时间作为衡量调度算法的重要准则之一。

典型调度算法【FOCUS】【FOCUS】【FOCUS】

（例题必须全部手动模拟一遍）

先来先服务(FCFS)

依据进程进入就绪状态的先后顺序排列

进程进入等待或结束状态时，就绪队列中的下一个进程占用CPU

优点：

简单

对长作业有利

对CPU繁忙型作业有利

缺点：

对短作业不利

对IO繁忙型作业不利

平均等待时间波动大

例题：

短作业优先(SJF) 或 短进程优先(SPF)

选择就绪队列中执行时间最短进程占用CPU进入运行状态

优点：

短进程优先算法具有最优平均周转时间

缺点：

导致饥饿。

连续的短进程流会使长进程无法获得CPU资源

对长作业不利

没有考虑进程的紧迫程度。

需要预知未来。

例题：

优先级调度算法(PSA)

使用优先级描述作业或进程运行的紧迫程度

算法的核心是确定进程或作业的优先级

例题：

动态优先级调度算法：

进程在运行的过程中，根据运行情况，动态的调整进程的优先级

根据近进程占用CPU的时间长短确定优先级

占用时间越长，再次获得调度的可能性就越小

占用时间越短，优先级越高，再次被调度的可能性就越大

根据就绪进程等待CPU时间的长短来决定优先级

在就绪队列中等待时间越长，优先级越高

在就绪队列中等待时间越短，优先级越低

高响应比优先(HRRN)

平衡FCFS和SPN两种算法的特点

FCFS只考虑等待时间未考虑执行时间

SPN只考虑执行时间未考虑等待时间

响应比

R = (W+T)/ T = 1+ W/ T

T为估计的执行时间，W为作业或者进程的等待时间

特点：

相同的等待时间，要求服务时间越短，优先级越高，有利于短作业

要求服务时间相同，等待时间越长，优先级越高，即先来先服务

对于长作业，等待时间的增加会提高其优先级，最终得到CPU使用权，杜绝饥饿状态。

每次调用都会重新计算优先级，影响系统效率

例题：

时间片轮转算法(RR)

时间片

分配处理机资源的基本时间单元

算法思路

时间片结束时，按FCFS算法切换到下一个就绪进程

每隔(n – 1)个时间片进程执行一个时间片q

例题：

多级反馈队列(MLFQ、MFQ)

多级反馈队列调度算法时时间片轮转调度算法和优先级调度算法的综合发展

通过动态调整进程优先级和时间片大小，兼顾多方面的系统目标

为提高系统吞吐量和缩短平均周转时间而照顾短进程

为了较好的IO设备利用率和缩短响应时间而照顾IO进程

可以不必预先估计进程的执行时间

特点：

短作业优先

终端用户：响应迅速

长作业：优先级下降快

进程切换次数少

传统调度算法的总结

先来先服务（FCFS）

对短作业不公平，平均等待时间差

短进程优先（SPN）

对长作业不公平，平均周转时间最小，需要估算运行时间，可能导致饥饿

高响应比优先（HRRN）

非抢占式调度，基于SPN发展而来，能够照顾SPN中的长作业

时间片轮转（RR）

公平，平均等待时间较长

多级反馈队列（MLFQ）

多种算法集成，不用预估时间

2.3 同步与互斥、死锁

（★ ★ ★ ）临界区与临界资源，抢占式与非常抢占式调度、进程同步与互斥的区别

临界区与临界资源【FOCUS】

临界资源

虽然多个进程可以共享系统中的各个资源，但其中许多资源一次只能为一个进程所使用，这种一次仅允许一个进程使用的资源称为临界资源。

对临界资源的访问必须互斥的进行

许多物理设备都属于临界资源，如打印机

许多变量，数据等都可以被若干进程共享，也属于临界资源

临界区

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

为了保证临界资源的正确使用，将临界资源访问过程分成四个部分

访问临界区

进入区：为了进入临界区使用临界资源，在进入区要检查是否可以进入临界区，如果可以则进入临界区，并设置正在访问临界区的标志

临界区：进程中访问临界资源的那段代码，又称临界段

退出区：将正在访问临界资源的标志清除

剩余区：代码中的其余部分

临界区和临界资源的区别

临界资源是一种系统资源，需要不同进程互斥访问

临界区是一段代码，属于某个进程，用来访问临界资源

每个进程的临界区代码可以不同

每个进程对临界区资源如何利用，具体操作如何，跟临界区资源以及互斥和同步的管理无关。

抢占式与非抢占式调度

非剥夺式优先级调度算法，系统一旦将处理器分配给就绪队列中优先级最高的进程，该进程便会一致运行下去，直至当前进程主动让出CPU，才把CPU分给另一个当前最紧迫的进程。

剥夺式优先级调度算法，系统将CPU分配给优先级最高的进程，并使之运行。在进程运行的过程中，一旦出现了另一个优先级更高的进程，进程调度程序，暂停当前进程，将CPU分给新出现的高优先级进程。

进程同步与互斥【FOCUS】

互斥

间接制约

一个进程进入临界区使用邻接资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，其他进程才能通过临界区访问共享资源。

两种互斥现象：

饥饿：

一个就绪的进程所申请的资源总是被优先于自己的其他进程所占有

始终处于不能被调度执行的状态

死锁：

某些进程间都在等待对方的资源，且都无法运行

即在进程集合中的这些进程处于永远的阻塞状态

互斥的准则：

空闲让进。当没有进程处于临界区，可以允许一个请求进入临界区的进程立即进入自己的临界区。

忙则等待。已有进程进入临界区时，其他试图进入临界区的进程必须等待。

有限等待。对要求访问临界资源的进程，应保证能在有限时间内进入自己的临界区。

让权等待。当一个进程因为某些原因不能进入自己的临界区时，应释放处理器给其他进程，防止“忙等”。

同步

直接制约

当一个进程A的运行需要另一个进程B所产生的信息时，这时A必须等待B执行完毕。

互斥与同步的区别

相似之处：

进程的互斥，实际上是进程同步的一种特殊的情况

即逐次使用互斥资源

是对进程使用资源次序的一种协调

可将进程同步和进程互斥统称为进程同步

区别：

互斥是进程之间共享互斥资源的使用权，这种竞争没有确定的必然联系

同步，涉及共享互斥资源的并发进程之间有一种必然的联系

当前运行进程执行过程中需要进程同步时

即使没有其他进程使用互斥资源

在没有得到协调工作的其他协作进程发来同步消息前

当前进程也不能去使用该互斥资源

（★ ★ ★ ★ ★ ）实现进程互斥的软件方法、通过信号量保证进程间的同步与互斥

实现进程互斥的硬件方法

禁止硬件中断

禁止了中断，没有上下文的切换，因此没有并发；通过硬件将中断处理延迟到中断被启用之后

缺点：

禁用中断后，进程无法被停止

整个系统都会为此停下来

可能导致其他进程处于“饥饿”状态

必须小心处理

中断，是接近系统底层的操作，影响系统稳定性

目前的windows系统已经把所有用户能控制的中断操作都屏蔽了

原子操作质量锁的特征

优点：

适用于单处理器或者共享主存的多处理器中任意数量的进程同步

简单并且容易证明

支持多临界区

缺点：

忙等待消耗处理器时间

可能导致饥饿，进程离开临界区时有多个等待进程的情况

死锁

拥有临界区的低优先级进程

请求访问临界区的高优先级进程获得处理器并等待临界区

实现进程互斥的软件方法

单标志法（钥匙传递）

设置一个公用整形变量turn，用于标识被允许进入临界区的进程编号

Turn = 0，则允许P0进入临界区。Turn = 1，则允许P1进入临界区

可以确保每次只有一个进程进入临界区

缺点：

两个进程交替进入临界区，如果某一进程不再进入临界区了，另一个进程也无法进入临界区

违背了“空间让进”的规则。造成资源利用不充分。

双标志先查法（挂牌进入）

一个进程进入临界区之前，先查看临界资源是否正在被访问

如果正在被访问，则等待；否则，进程进入自己的临界区

缺点：

按如下步骤进行，Pi和Pj能够同时进入临界区

违背“忙则等待”规则

双标志后查法（挂牌进入）

一个进程进入临界区之前，先查看临界资源是否正在被访问

如果正在被访问，则等待；否则，进程进入自己的临界区

缺点：

可能造成都不进入临界区

导致“死锁”现象，违背“有限等待”规则

peterson法（绅士法）

设置标签同时，设置turn标志

使用之前先谦让。

注意判断条件，如果 i 已经标记，并且turn == i 则 i 开始执行，否则任意条件不满足则 i 等待。

该算法是单标志法和双标志后查法的综合

利用flag解决临界资源互斥访问的问题，利用 turn 解决“饥饿”现象

以上算法只限于两个进程间得互斥

软件方法的总结

实现复杂，需要两个进程间的共享数据项

主要问题发生在标志的检查和修改不能作为一个整体执行，而导致无法保证互斥访问的问题。

忙等待

不能满足“让权等待”的规则

用无限循环，监测等待事件的完成，以便能够继续执行，等待的进程或线程不放弃CPU

通过信号量保证进程间的同步与互斥【FOCUS】

1956年Dijkstra提出了一个同步机制，称为信号量。其基本思想是在多个相互合作的进程时间使用简单的信号来同步

信号量

信号量是操作系统提供的一种协调共享资源访问的方法

OS是管理者，地位高于进程

用信号量表示系统资源的数量

信号是一种抽象的数据类型，

由一个整形变量（sem）和两个原子操作组成

P（）Prolaag （荷兰语尝试、减少）

V（）Verhoog（荷兰语增加）

整形信号量

信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作P()和V()来操作

P()和V()都是原子操作，执行不能被打断

缺点：信号量 S ≤ 0 时“忙等”，未遵循“让权等待”

为了实现“让权等待”，除了需要一个记录资源数量的sem外还要增加一个“进程链表”，用于链接需要等待的进程。
P(S): while S <= 0 do no-op;S = S - 1;  
V(S):S = S + 1;
P/V操作【FOCUS】

P/wait/test操作：

sem 减 1

如果sem减1之后，仍然大于或等于 0，P操作返回，该进程继续执行

如果sem减1之后小于0，则该进程被阻塞后，放入该信号对应的阻塞队列中，然后转进程调度

V/signal/increment操作：

sem 加 1

若sem加1后大于0，V操作返回，该进程继续执行

若sem加1后，仍然小于或等于0，则从该信号阻塞队列中唤醒一个等待的进程，然后V操作返回继续执行，或，执行进程调度。

信号量的实现

信号量的特点

信号量是被保护的整形变量

初始化完成后，只能通过P()和V()操作来修改

由操作系统保证，PV操作是原子操作

P()可能阻塞，V()不会阻塞

通常假定信号量是“公平的”

进程不会被无限期阻塞在P()操作

假定信号量等待按先进先出排队

利用信号量实现进程互斥【FOCUS】

设置互斥信号量mutex，初值为1（即可用资源数为1）

将临界区放在P()、V()原语之间即可实现两个进程的互斥进入
semaphore mutes = 1;
Process 1:while(true){P(mutex);critical section;v(mutex);remainder section;}
Process 2:while(true){P(mutex);critical section;v(mutex);remainder section;}
// 如果没有进程在临界区，则mutex一直为 1 
// 有进程准备进入临界区，P()原语将mutex减1，mutex变为0，执行临界区代码
// 再有进程准备进入临界区， P()原语将mutex减1，mutex变为-1。进入等待队列

// 临界区代码执行完毕， V()原语将mutex加1
// 若mutex加1之前小于0，即mutex加1之后小于或等于0，则唤醒一个阻塞进程
互斥的实现是不同进程对同一信号量进行P()V()操作

注意：

同一个进程中P(mutex)和V(mutex)必须成对出现

P()操作保证互斥访问临界资源

如果缺少P（mutex）将会导致系统混乱，不能实现对临界资源的互斥访问

V()操作在使用后释放临界资源

如果缺少V（mutex）将会导致临界资源永远得不到释放，从而使因等待该资源而进入阻塞状态的进程永远不会被唤醒

P(mutex)和V(mutex)先后次序不能混淆

利用信号量实现进程同步【FOCUS】

为P0与P1临界资源设置信号量mutex，初值为0（即可用资源数为0）

P0执行相关操作之后，释放信号量（V操作）

P1一直等待（P操作），等到P0释放的信号后才能继续执行下面的指令
semaphore mutes = 0;
Process 0:while(true){// ...produce x;v(mutex);remainder section;}
Process 1:while(true){P(mutex);use x;// ...remainder section;}
// 信号量mutex，初值为0，代表P0还未完成
// 如果P1执行P操作，mutex减1，mutex = -1，P1被放入等待队列
// P0执行完相应操作（produce x）后，执行V操作， mutex加1，mutex = 0，从等待队列中唤醒P1操作，P1执行后续操作（use x）。
注意

P(mutex)和V(mutex)也必须成对出现，但是出现在不同进程中

P()操作，后续进程不会在前驱进程完成前执行

V()操作，释放信号量，让后续的进程可以执行

P(mutex)和V(mutex)先后次序不能混淆

mutex的初值问题

（★ ★ ★ ★ ★ ）常见的进程同步问题

生产者-消费者问题【FOCUS】

有一群生产者进程生产产品，并将这些产品交给消费者进程进行消费

为了使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池

生产者进程每生产一个产品，就将其放入缓冲区中

消费者进程负责从缓冲区中取走产品进行消费

一个生产者、一个消费者、一个缓冲区（只放一个产品）

生产者生产-放入缓冲区

消费者消费-从缓冲区中取出

生产者生产 -> 消费者消费 -> 生产者生产 -> ……（交替执行）

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

交替执行也能解决问题，但是浪费缓冲区

将缓冲区中每一个格子看成一个资源

生产者看空着的格子是否存在，如果存在则可以存放

消费者看满着的格子是否存在，如果存在则可以提取
// 两个信号量full和empty代表两种资源满的格子和空的格子
// 生产者消耗空的资源，产生满的资源，即P（empty）、V（full）
// 消费者消耗满的资源，产生空的资源，即P（full）、V（empty）
semphore empty = N, full = 0;
Process Producter:
while(true){生产产品;P(empty);存放仓库;V(full);
}
Process Consumer:
while(true){P(full);提取产品;V(empty);消费产品;
}
多个生产者，多个消费者，1个缓冲区

使用empty和full信号量也能解决问题，empty=1，full=0

生产者根据empty的值进行排队

消费者根据full的值进行排队

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

关系分析：

生产者和消费者对缓冲区的访问是互斥关系

生产者和消费者是协作关系，即同步关系

思路整理：

有几个进程：生产者、消费者。互斥和同步发生在生产者和消费者之间

需要解决P、V操作的位置

信号量设置：

一个互斥信号量，mutex用于互斥缓冲区，初始值为1

一个满资源的信号量，full控制生产者，初始值为0

一个空资源的信号量，empty控制消费者，初始值与缓冲区大小相同（N）

流程图绘制：

得出代码：
semphore empty = N, full = 0, mutex = 1;
Process Producter:
while(true){生产产品;P(empty);P(mutex);存放仓库;V(mutex);V(full);
}
Process Consumer:
while(true){P(full);P(mutex);提取产品;V(mutex)V(empty);消费产品;
}
注意事项：

在每个进程中用于实现互斥的P(mutex)和V(mutex)必须成对的出现

对于资源型信号量empty和full的P和V操作，同样需要成对的出现，但他们分别处于不同的进程中

如，P(empty)再生产者进程中，而V(empty)则在消费者进程中，生产者若因执行P(empty)而阻塞，则以后将由消费者进程将其唤醒。

每个进程中的多个P操作顺序不能颠倒，应先执行对资源型信号量的P操作，然后再执行对互斥信号量的P操作，否则可能引起死锁

记住，只要存在多个同类进程，就一定会用到互斥变量

哲学家就餐问题【FOCUS】

设有5个哲学家，共享一张放有5把椅子的桌子，每人坐在一把椅子上。桌上总共有5根筷子，在每个人的两边各放一只。
哲学家平时都在思考，只有饿了的时候才会试图拿起两边的筷子准备吃饭。
每个哲学家只有拿起两根筷子才可以吃饭
如果筷子在他人手上，哲学家只有等待。

关系分析：
- 5个哲学家，相邻科学家中间的那跟筷子是互斥访问的资源
- 哲学家之间不存在同步关系
整理思路：
- 存在5个哲学家，即5个进程。问题的关键在于，如何让一个哲学家同时获得左右两边的筷子，而不造成饥饿或死锁
- 方法有两个，一个是让他们同时去拿两个筷子，二是控制哲学家的动作避免饥饿或死锁
信号量设置：
- 争夺的资源是筷子，所以筷子是临界资源
- 为每一跟筷子设置一个信号量chopstick[5] = { 1，1，1，1，1 }
流程图绘制：

相邻位置不能同时就餐

最多可以两个人同时就餐

存在多个临界资源

代码实现：

Semaphore chopstick[5] = {1,1,1,1,1};
philosopher(int i){while(true){thinks;P(chopstick[i]);P(chopstick[(i+1)%5]);eat;V(chopstick[i]);V(chopstick[(i+1)%5]);}
}
// 如果5个哲学家同时想吃饭了，都拿起了左手的筷子，都在等待右手的筷子，则会引起死锁

// 将“吃饭” 作为一个互斥资源。mutexEat = 1
Semaphore chopstick[5] = {1,1,1,1,1};
Semaphore mutexEat = 1;
philosopher(int i){while(true){thinks;P(mutexEat);P(chopstick[i]);P(chopstick[(i+1)%5]);eat;V(chopstick[i]);V(chopstick[(i+1)%51);V(mutexEat);}
}
// 有人想吃，其他人就别动，让想吃的这个人拿筷子吃饭
// 同时、最多、只能有一个人吃饭
// 互斥临界区中的“抢筷子”没有实际意义

// 把取筷子的事件作为互斥信号。mutexGet = 1
Semaphore chopstick[5] = {1,1,1,1,1};
Semaphore mutexEat = 1;
philosopher(int i){while(true){thinks;P(mutexGet);P(chopstick[i]);P(chopstick[(i+1)%5]);V(mutexGet);eat;V(chopstick[i]);V(chopstick[(i+1)%51);}
}
// 当一个哲学家开始取筷子的时候，其他人都不能动----等待取筷子事件
// 同一时刻只能有一个人取筷子
// 跟吃饭的人隔一个的人，可以获得全部筷子，开始就餐
// 保证最大用餐人数

// 解决死锁问题，同时最多可有两个哲学家一起吃饭
// 至多只允许四位哲学家同时去拿左边的筷子 
// 能保证至少有一位哲学家能够就餐
// 就餐完毕后，能释放出两根筷子从而使更多的哲学家能够就餐// 将“想吃饭” 作为一个资源型信号量。semEat = 4
Semaphore chopstick[5] = {1,1,1,1,1};
Semaphore semEat = 4;
philosopher(int i){while(true){thinks;P(semEat);P(chopstick[i]);P(chopstick[(i+1)%5]);eat;V(chopstick[i]);V(chopstick[(i+1)%5]);V(semEat);}
}
// 第5个想吃饭的哲学家会进入等待----先饿着
// 至少保证一个哲学家能就餐
// 就餐完毕，释放“想吃”信号，释放两根筷子。保证其他人能就餐

// 按照哲学家编号的奇偶性，规定取筷子的顺序
// 奇数号的哲学家先拿左边的筷子，然后再去拿右边的筷子
// 偶数号的哲学家先拿右边的筷子，然后再去拿左边的筷子
// 1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子
// 即，5位哲学家都去竞争奇数号的筷子
// 获取后，再去竞争偶数号的筷子
// 最后总会有一个哲学家能获得两只筷子而就餐
// “左右互斥”
Semaphore chopstick[5] = {1,1,1,1,1};
philosopher(int i){while(true){think;if(0 == i%2){				// 偶数哲学家，先右后左P(chopstick[i]);P(chopstick[(i+1)%5]);eat;V(chopstick[(i+1)%5]);V(chopstick[i]);}else{						//奇数哲学家，先左后右P(chopstick[i]);P(chopstick[(i+1)%5]);eat;V(chopstick[(i+1)%5]);V(chopstick[i]);}}
}

读者-写者问题【FOCUS】

由一个由许多进程共享的数据区域，这个区域可以是一个文件或内存的一块空间

共享数据的进程分为两类

写进程，只负责往共享区写数据

读进程，只能够从共享区读数据

还满足以下条件：

任意多个读进程可以同时读取共享区数据

一次只能有一个写进程往共享区写数据

如果有进程在读文件，禁止写进程写共享区

如果有写进程在写文件，禁止其他进程操作共享区

关系分析：

读者和写者是互斥关系；

写者和写者是互斥关系；

读者和读者是独立的关系；

思路整理：

两个进程，经典的多进程并发纯互斥问题。

读者进程与任何进程都互斥，临界资源为共享的文件，使用对共享文件的P()、V()可以实现读进程互斥

读者和写者间的互斥，仅用一对互斥信号量无法实现，因为还需要让读者并发共享资源。如果一直有读者访问共享区，则读进程不会放弃资源，写进程无法进入临界区。因此需要记录读进程的数量，直至读进程数量为0才能释放资源。

信号量设置：

一个变量countR，用来记录访问共享区的读进程的数量

初始为0，表示没有读进程访问临界区；

一个互斥信号量mutexBuf，用来控制共享区的访问

初始值为1，标志共享区可访问；

由于多个读进程都要修改countR，因此countR也成为了临界资源

一个互斥信号量mutexCouter，用来控制countR的访问

初始值为1，表示当前无进程修改countR；

流程图绘制：

代码实现：
Semaphore mutexBuf = 1, mutexCnt = 1;
int countR = 0;
Writer(){while(true){P(mutexBuf);write(Buffer);V(mutexBuf);}
}
Reader(){while(true){P(mutexCnt);if(countR == 0)P(mutexBuf);countR = countR + 1;V(mutexCnt);read(Buffer);P(mutexCnt);countR = countR - 1;if(countR == 0)V(mutexBuf);V(mutexCnt);}
}

（★ ★ ★ ★ ）死锁的概念，发生死锁的4个必要条件，处理死锁的方法，银行家算法

死锁的概念

死锁，是指多个进程因竞争资源而造成的一种僵局（相互等待），若无外力作用，这些进程将无法向前推进。

死锁产生的原因【FOCUS】

死锁产生的原因是竞争资源

若系统中只有一个进程运行，所有资源被进程独享，则不会产生死锁

当系统中有多个进程并发执行时

若系统中的资源不足以满足所有进程的需要，则会引起进程对资源的竞争从而可能导致死锁

竞争可能导致死锁，但是竞争并不是一定会死锁

只有进程运行过程中请求和释放资源的顺序不当的时候才会导致死锁

死锁产生的原因是系统资源不足和进程推进顺序不当

系统资源不足是产生死锁的根本原因

设计操作系统的目的就是使并发进程共享系统资源

进程推进顺序不当是产生死锁的重要原因

当系统资源刚好够进程使用时，进程的顺序推进不当就很容易导致进程彼此占有对方的资源，从而导致死锁

死锁产生必要条件【FOCUS】

互斥条件：进程要求对所分配的资源进行排他控制，即在一段时间内，某种资源仅为一个进程所占有。

不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得资源的进程自己释放

请求与保持条件（部分分配条件）：每次进程申请他所需要的一部分资源，等待分配新资源的同时，进程继续占有已分配的资源。

环路等待条件：存在一种进程资源的循环等待链，而链中的每一个进程已经获得的资源同时被链中的下一个进程请求。

资源分配图

描述资源和进程间的分配和占用关系的有向图

两类结点（顶点）

系统中所有的进程：P = { P1, P2, …, Pn }

系统中所有的资源：R = { R1, R2, …, Rm }

两类有向边

资源请求边：进程 Pi 请求资源Rj ： Pi→Rj

资源分配边：资源 Rj 已经分配给进程 Pi ： Rj → Pi

处理死锁的方法

鸵鸟算法，视而不见

预防死锁（资源未分配时进行），通过设置某些限制条件，去破坏死锁的4个必要条件中的一个或几个，确保系统永远不会进入死锁状态。

避免死锁（资源分配后进行），在资源的动态分配过程中，用某种方法防止系统进入不安全状态，只允许不会出现死锁的请求执行，从而避免死锁的产生。

检测及解除（死锁发生了进行），通过系统的检测结构及时检测死锁的发生，然后采取某种措施解除死锁

银行家算法【FOCUS】

Dijkstra给出的最具有代表性的避免死锁的算法

操作系统被看成银行家

操作系统的资源被看成银行家管理的资金

进程向操作系统申请资源相当于用户向银行家贷款

银行家必须考查用户的资金需求与贷款的情况，以保证正常的资金流转，让所有用户都能满足贷款需求，防止资金断流，即避免出现死锁

算法思路：

操作系统按照银行家制定的规则为进程分配资源

当进程首次申请资源的时候，要测试进程对资源的最大需求量

如果系统的现存资源可以满足它的最大需求量，则按当前申请量分配资源

否则推迟分配

当进程在执行过程中继续申请资源时，先测试进程已占用资源和申请资源的和是否超过进程对资源的最大需求，超过则拒绝分配

否则测试系统现存资源能否满足该进程尚需的最大资源量

若能满足按当前申请量分配，否则推迟分配

可利用资源Available：

含有m个元素的数组，其中每一个元素代表一类可用资源，Available[i]=k，表示系统中Ri类资源还有K个

最大需求矩阵Max：

n×m矩阵，一行代表一个进程，一列代表一个资源。Max[ i , j ] = k，表示系统中进程 i 共需要 k 个 j 类资源才能完成。

分配矩阵Allocation：

n×m矩阵，Allocation[ i , j ] = k，表示系统已经给第 i 个进程分配了 k 个 j 类资源。

当前需求矩阵Need：

n×m矩阵，Need[ i , j ] = k，表示当前进程 i 还需分配k 个 j 类资源才能完成

Need = Max - Allocation

Max和Allocation一般是已知条件，Need需要求解

请求矢量Request：

单次向系统请求的资源数，Requesti[j] = k，表示进程 i 此次向系统请求 k 个资源 j

银行家算法流程：

示例1：

示例2：

示例3：

示例4：

三、内存管理

（★ ★）程序执行的完整过程（包括编译、连接、装入执行），静态装入与动态装入，物理地址与逻辑地址，交换与覆盖

程序执行的完整过程

进程要运行，首先要将程序和数据装入内存

编译：编译程序将用户源代码编译成若干目标模块

连接：连接程序将编译后形成的一组目标模块，以及所用的函数库连接在一起，形成一个完整的装入模块

装入：装入程序将装入模块装入内存运行

编译 -> 汇编 -> 链接 -> 加载

程序连接

静态连接

程序运行前，现将各个目标模块及他们所需的库函数连接成一个完整的可执行程序，以后不再拆开

装入时需解决如下两个问题

1）对相对地址进行修改

2）变换外部调用符号

装入时动态连接

经过编译后得到一组目标模块，在装入程序时，采用边装入边连接的方式

优点：

1）便于修改和更新

2）便于实现对目标的共享

运行时动态连接

对于某些目标模块的连接，是在程序执行中需要该模块时，才对他进行连接。

不仅能加快程序的装入过程，而且可以节约大量的内存空间

静态装入与动态装入

绝对装入

编译程序产生绝对地址的目标代码

装入程序按照装入模块中的地址，将程序和数据装入内存

逻辑地址与实际地址相同

只适用于单道环境

可重定位装入

多个目标模块的起始地址都是从0开始

程序中的其他地址都是相对于起始地址的

根据内存情况将模块装入内存时，对目标程序中指令和数据地址进行修改

地址变换通常是在装入时一次完成

又称为静态重定位

必须一次载入内存

动态运行时装入

程序在内存中会发生移动

程序真正要执行时开始地址转换，之前保持相对地址

需要重定位寄存器支持

可将程序分配到不连续存储区

程序可异步运行，可动态申请内存

便于程序段共享

逻辑空间可以大于物理空间

物理地址与逻辑地址

物理地址空间

硬件支持的地址空间

起始地址为0

地址总线的根数决定空间的大小

逻辑地址空间

在CPU上运行的程序看到的地址

起始地址为0

其大小由用户程序决定

逻辑地址对应到相应的物理才能完成相关操作

地址生成过程

CPU

ALU：需要逻辑地址的内存内容

MMU：进行物理地址和逻辑地址的转换

CPU控制逻辑：给总线发送物理地址请求

内存

发送物理地址的内容给cpu

或接收CPU数据到物理地址

操作系统

建立逻辑地址和物理地址的映射

交换和覆盖【FOCUS】

计算机系统时常出现内存空间不够用

覆盖（overlay）

应用程序手动把需要的指令和数据保存在内存中

交换（swapping）

操作系统自动把暂时不能执行的程序保存到外存中

覆盖技术【FOCUS】

目标

在较小的可用内存中运行较大的程序

方法

依据程序逻辑结构，将程序划分为若干功能相对独立的模块，与不会同时执行的模块共享同一块内存区域

必要部分(常用功能)的代码和数据常驻内存

可选部分(不常用功能)放在其他程序模块中,只在需要到时装入内存

不存在调用关系的模块可相互覆盖，共用同一块内存区域

交换技术【FOCUS】

目标

增加正在运行或需要运行的程序的内存

实现方法

可将暂时不能运行的程序放到外存

换入换出的基本单位

整个进程的地址空间

换出(swap out)

把一个进程的整个地址空间保存到外存

换入(swap in)口

将外存中某进程的地址空间读入到内存

覆盖&交换的区别【FOCUS】

覆盖

只能发生在没有调用关系的模块间

程序员须给出模块间的逻辑覆盖结构

发生在运行程序的内部模块间

交换

以进程为单位

不需要模块间的逻辑覆盖结构

发生在内存进程间

（★ ★ ★ ）连续内存分配方式与3种非连续内存分配方式（分页、分段、段页式），内部碎片与外部碎片

连续内存分配

给进程分配一个不小于指定大小的连续的物理内存区域

每个进程的地址空间中包含各自的代码段，数据段和相应的堆栈数据

进程结束后释放其占用的内存空间

单一连续分配：

内存分为系统区和用户区

系统区仅提供给操作系统使用，通常在低地址部分

用户区为用户提供，是除了系统区之外的内存空间

无需内存保护，因为内存中永远只有一道程序，不会干扰其他程序

特点：

简单，无外碎片，

缺点：

只能用于单用户，单任务系统，有内部碎片，内存利用率低

固定分区分配：

将用户空间划分为若干固定大小的区域，每个分区只装一道作业

有空闲分区时，从后备作业队列中选择适当大小的作业装入分区

分区大小相等：缺乏灵活性

分区大小不等：多个小区域 + 适量中等区域 + 少量大分区

将分区按大小排队，并位置建立一张分区表（起始地址、大小、状态）

用户通过分区表检索合适的分区，分配，状态标记为“已分配”

问题：

程序太大无法放入分区

主存利用率太低，程度大部分情况小于分区，产生内部碎片

特点：

支持多道程序，实现比较简单

无外部碎片

动态分区分配：

不预先在内存内划分区域，根据进程大小动态创建分区，当程序被加载时，分配一个进程指定大小的分区（块、内存块）

分区的地址是连续的

操作系统需要维护的数据结构（分区表、分区链）

所有进程的已经分配区域

空闲分区

不同分区策略会影响分配的效果

内存分配算法

最先匹配策略（First Fit Allocation）

思路

分配n个字节，使用第一个可用空间比n大的空闲块

原理

空闲分区列表按地址顺序排序

分配过程，从头开始搜索一个比n大的分区

释放分区时，检测是否可以与临近的空闲分区合并

优点

简单

在高地址空间有大块的空闲分区

缺点

存在外部碎片，分配大块空间时较慢

循环首次适应策略（Next Fit Allocation）

原理

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

优点

查找空闲分区的开销小

空闲分区分布更均匀

缺点

缺乏大的空闲区

最佳匹配策略（Best Fit Allocation）

思路

分配n个字节的分区时，查找并使用不小于n的最小空闲分区

原理

空闲分区列表按由小到大排序

分配过程，从头开始搜索一个比n大的分区

释放分区时，查找并合并临近的空闲分区（重新排序）

优点

大部分分配尺寸较小时，效果很好

可以减小外部碎片的大小，相对简单

缺点

产生很多无用细小碎片，释放分区较慢

最坏匹配策略（Worst Fit Allocation）

思路

分配n个字节的分区时，查找并使用不小于n的最大空闲分区

原理

空闲分区列表按由大到小排序

分配过程，从头开始搜索一个比n大的分区

释放分区时，查找并合并临近的空闲分区（重新排序）

优点

中等大小的分配较多时，效果最好

避免出现太多的小碎片

缺点

释放分区较慢；破坏较大分区，后续难以分配大分区

快速适应算法（quick fit）

将空闲分区根据其容量的大小进行分类（2K、4K、8K…）

设立一张管理索引表，每个索引表项对应一种空闲分区类型

分配：根据进程大小从索引表中找到能容纳它的最小的分区链表，从表中取下第一块分配即可

特点：

分配效率高，不用分割空间

分区归还的算法比较复杂，增加了系统开销

存在内碎片

伙伴系统（Buddy System）

整个可分配的分区大小2的u次幂，2U

当进程申请分区的大小S满足 2U-1 < S ≤ 2U 时，把整个块分配给该进程

如S ≤2i－1，将大小为2i 的当前空闲分区划分成两个大小为2i－1 的空闲分区

重复划分过程，直到2i-1 < S ≤ 2i，并把一个空闲分区分配给该进程

释放过程

把释放的块放入空闲块数组

合并满足条件的空闲块

合并条件

大小相同2i；地址相邻；低地址空闲块起始地址为2k

动态可重定位分区分配

碎片整理

通过调整进程占用的分区位置来减少或避免分区碎片

紧凑（Compaction）技术

称为碎片整理

通过移动分配给进程的内存分区，以合并外部碎片

需要重定位寄存器的支持

内部碎片与外部碎片

内存中暂时不能被利用的区域，称为内存碎片

外部碎片

分配单元之间未被使用的内存

内部碎片

分配单元内部未被使用的内存

取决于分配单元大小是否需要取整

页式存储

页帧（帧、物理页面, Frame, Page Frame）

物理内存被划分为大小相等的帧

内存物理地址的表示：二元组（f，o）

f-帧号（F位，共有2F 个帧)

o-帧偏移 (S 位, 每帧有2S 字节)

物理地址= f * 2S + o

把物理地址空间划分为大小相同的基本分配单位

2的n次方，如512, 4096, 8192

页面（页，逻辑页面，Page）

进程逻辑地址空间被划分为大小相等的页

页内偏移 = 帧内偏移

页号 ≠ 帧号

进程逻辑地址的表示：二元组（p，o）

p-页号（P位，共有2P 个页)

o-页偏移 (S 位, 每帧有2S 字节)

虚拟地址= p * 2S + o

把逻辑地址空间也划分为相同大小的基本分配单位

帧和页的大小必须是相同的

页面到帧

逻辑地址到物理地址的转换

MMU、TLB

段式存储

进程的地址空间由多个段组成：主代码段、子模块代码段、公用库代码段、堆栈段（stack）、堆数据（heap）、初始化数据段、符号表等

段式存储管理的目的

更细粒度和灵活的分离与共享

逻辑空间中是顺序的程序段

在物理空间中是离散化存储

段的概念

段，表示访问方式和存储数据等属性相同的一段地址空间

对应一个连续的内存块

若干个段组成进程逻辑地址空间

段的访问（其逻辑地址由二元组<s,addr>构成）

s - 表示段号

addr - 段内偏移

逻辑地址

段表：逻辑地址和到理地址的映射

记录：段号，起止位置，段长度

地址映射

段共享

方式，两个作业的段表的项指向同一个物理副本（基址相同）

一个作业读取时，必须保证另一个作业不许修改

纯代码、可重入代码（不属于临界资源）可共享

段保护、

存取控制保护

地址越界保护（段长度寄存器，段表长度）

段页式存储

页式存储能有效地地提高内存利用率

分段存储能反映程序的逻辑结构并有利于段共享

结合两种存储管理方式

逻辑空间首先被分成若干逻辑段，每段有自己的段号

再将每段分成若干大小固定的页

物理空间管理和分页存储一样

将其分成若干和页面大小相同的存储块

并以块作为内存分配的单位

段页式存储的转换

（★ ★ ★ ★ ）分页管理方式中的逻辑地址结构、页表、快表与多级页表

地址映射

页到帧的映射

逻辑地址中的页号是连续的

物理地址中的帧号不连续

不是所有的页都有对应的帧

映射机构

页表结构

每一个进程都有一个页表

每一个页面对应一个页表项

页表内容随进程运行状态而动态变化

页表基址寄存器(PTBR: Page Table Base Register)

转换实例

性能问题

页式管理中的地址空间是一维的

得到相应的物理地址，段式管理需给出基址和段长

页式管理只需给出一个整数就能确定对应的物理地址

内存访问性能问题

访问一个内存单元需要2次访存

第一次访问：获取页表项

第二次方位：访问数据

降低访问速度和吞吐量

快表（Translate Look-aside Buffer，TLB）

使用关联存储实现缓存近期访问的页表项

如果TLB命中，物理帧号可以很快被获取

如果TLB未命中，将对应的页表项更新到TLB中

TLB，联想寄存器

主存中的页表又称为慢表

快表、慢表同时查找，如果快表命中，终止慢表查找

一般快表命中率能达到90%以上

快表的有效性基于局部性原理

多级页表

由于引入分页，进程在执行时不需要将所有页面都调入内存帧中

只需将保存有映射关系的页表调入内存中即可

32位逻辑地址空间、页面大小4K，页表项4B，页表就占1024页

通过间接引用将页号分成k级

建立页表树

减少每一级页表的长度

为了查询方便，顶级页表最多只能有一个页面

二级页表

多级页表

（★ ★ ★ ）虚拟内存与三种虚拟内存管理方式（请求分页、请求分段、请求段页式），每种方式的特点及其之间的区别

虚拟内存

在有限容量的内存中，以页为单位自动装入更多更大的程序

只把部分程序放到内存中，从而运行比物理内存大的程序

由操作系统自动完成，无需程序员的干涉

实现进程在内存与外存之间的交换，从而获得更多的空闲内存空间

在内存和外存之间只交换进程的部分内容

思路：

将不常用的部分内存块暂存到外存

原理：

装载程序时

只将当前指令执行需要的部分页面或段装入内存

指令执行中需要的指令或数据不在内存(称为缺页或缺段)时

处理器通知操作系统将相应的页面或段调入内存

操作系统将内存中暂时不用的页面或段保存到外存

虚拟存储的基本特征：

之所以称其为虚拟存储器，是因为这种存储器并不存在，是因为操作系统提供了部分装入、请求调入和置换功能后，给用户的感觉好像是存在一个比实际物理内存大得多的存储器。

虚拟存储器存在如下性质

多次性：进程是被允许分成多次调入内存的

对换性：进程无需常驻内存，允许进程块被换入和换出

虚拟性：从逻辑上扩充内存，用户看到的内存容量远大于实际物理内存

不连续性：物理内存分配不连续

虚拟内存管理方式

请求分页存储管理

特点：

虚拟存储：请求分页存储管理是实现虚拟存储器的一种常用方式。它允许进程在运行时只装入部分页面，其余页面根据进程的运行需要动态地装入。

页面置换：当内存空间已满，而又需要装入新的页面时，系统会根据置换功能适当调出某个页面，以便腾出空间装入新的页面。

硬件支持：请求分页存储管理需要一定的硬件支持，包括页表机制、缺页中断机构和地址变换机构。

地址空间一维：分页的地址空间是一维的，程序员只需利用一个记忆符，即可表示一个地址。

请求分段存储管理

特点：

逻辑分段：分段由用户设计划分，每段对应一个相应的程序模块，具有完整的逻辑意义。

二维地址空间：分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

动态链接：进程开始运行时，只装入主模块，运行中需要哪段再装入、链接。

段长不等：段的长度不固定，决定于用户所编写的程序，可以动态增长。

易于共享：分段存储管理便于段的共享，因为每段都有独立的段名，可以通过段名来访问和共享相应的段。

请求段页式存储管理

请求段页式存储管理结合了分段和分页的特点，将内存空间划分为大小相等的页面，同时将程序划分为多个段，每个段再划分为多个页面。这种方式既保留了分段管理的优点，如易于共享和保护，又克服了分段管理内存碎片较多的缺点。不过，请求段页式存储管理的实现较为复杂，需要同时维护段表和页表，且地址变换过程也相对复杂。

其间的区别

单位与目的：

分页：页是信息的物理单位，分页的目的是实现离散分配，减少内存的外零头，提高内存利用率。

分段：段是信息的逻辑单位，分段的目的是为了能更好地满足用户的需要，使程序具有更好的可读性和可维护性。

地址空间：

分页：一维地址空间，程序员只需利用一个记忆符即可表示一个地址。

分段：二维地址空间，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

长度与增长：

分页：页的大小固定且由系统决定。

分段：段的长度不固定，决定于用户所编写的程序，且可以动态增长。

共享与保护：

分页：页面一般不能共享，但可以通过其他机制实现共享。

分段：分段存储管理便于段的共享，因为每段都有独立的段名，且可以针对不同类型的段采取不同的保护措施。

（★ ★ ★ ★ ）请求分页管理方式中的访存过程，访存有效时间以及几种页面置换算法

虚拟页式存储管理

在页式存储管理的基础上，增加请求调页和页面置换

思路

当用户程序要装载到内存运行时，只装入部分页面，就启动程序运行

进程在运行中发现有需要的代码或数据不在内存时，则向系统发出缺页异常请求

操作系统在处理缺页异常时，将外存中相应的页面调入内存，使得进程能继续运行

页表项结构

驻留位：表示该页是否在内存

1表示该页位于内存中，该页表项是有效的，可以使用

0表示该页当前在外存中，访问该页表项将导致缺页异常

修改位：表示在内存中的该页是否被修改过

回收该物理页面时，据此判断是否要把它的内容写回外存

访问位：表示该页面是否被访问过（读或写）

用于页面置换算法

保护位：表示该页的允许访问方式

只读、可读写、可执行等

访存过程

有效存储访问时间（effective memory access time EAT）

被访问页在内存中，且其对应的页表项在快表中（快表命中）【FOCUS】

EAT = λ + t

λ：查找快表的时间

t：访问内存的时间

被访问页在内存中，且其对应的页表项不在快表中（快表没命中）【FOCUS】

EAT = λ + t + λ + t = 2 × ( λ + t )

被访问页不在内存中（缺页）【FOCUS】

EAT = λ + t + e + λ + t = e + 2( λ + t )

e：缺页中断处理时间

换出页被修改【FOCUS】

EAT = λ + t + e + e + λ + t = 2( λ + t + e )

若考虑：命中率a，缺页率p，修改率q

EAT = λ + at + (1-a)[t + (1-f)(λ + t) + f(1+q)*(e + λ + t)]

页面置换算法【FOCUS】

最优页面置换算法(OPT, optimal)

基本思路

置换在未来最长时间不访问的页面

算法实现

缺页时，计算内存中每个逻辑页面的下一次访问时间

选择未来最长时间不访问的页面

算法特征

缺页最少，是理想情况

实际系统中无法实现

无法预知每个页面在下次访问前的等待时间

作为置换算法的性能评价依据

模拟器上运行某个程序，并记录每一次的页面访问情况

第二遍运行时使用最优算法

示例

先进先出算法（First-In First-Out, FIFO）

基本思路

选择在内存驻留时间最长的页面进行置换

算法实现

维护一个记录所有位于内存中的逻辑页面链表

链表元素按驻留内存的时间排序，链首最长，链尾最短

出现缺页时，选择链首页面进行置换，新页面加到链尾

算法特征

实现简单

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

进程分配物理页面数增加时，缺页并不一定减少(Belady现象)

很少单独使用

示例

最近最久未使用算法 (Least Recently Used, LRU)

算法思路

选择最长时间没有被引用的页面进行置换

如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问

算法实现

缺页时，计算内存中每个逻辑页面的上一次访问时间

选择上一次使用到当前时间最长的页面

算法特征

最优置换算法的一种近似

示例

LRU算法的堆栈实现

时钟置换算法（Clock）

算法思路

仅对页面的访问情况进行大致统计

数据结构

在页表项中增加访问位，描述页面在过去一段时间的内访问情况

各页面组织成环形链表

指针指向最先调入的页面

算法实现

访问页面时，在页表项记录页面访问情况

缺页时，从指针处开始顺序查找未被访问的页面进行置换

页面装入内存时，访问位初始化为0

访问页面（读/写)时，访问位置1

缺页时，从指针当前位置顺序检查环形链表

访问位为0，则置换该页

访问位为1，则访问位置0，并指针移动到下一个页面，直到找到可置换的页面

算法特征

时钟算法是LRU和FIFO的折中

示例

改进的Clock算法

算法思路

减少修改页的缺页处理开销

算法实现

在页面中增加修改位，并在访问时进行相应修改

缺页时，修改页面标志位，以跳过有修改的页面

使用位、修改位变化规则

示例

最不常用算法（Least Frequently Used, LFU）

算法思路

缺页时，置换访问次数最少的页面

算法实现

每个页面设置一个访问计数

访问页面时，访问计数加1

缺页时，置换计数最小的页面

算法特征

算法开销大

开始时频繁使用，但以后不使用的页面很难置换

解决方法：计数定期右移

LRU和LFU的区别

LRU关注多久未访问，时间越短越好

LFU关注访问次数，次数越多越好

示例

LRU、FIFO和Clock的比较

LRU算法和FIFO本质上都是先进先出的思路

LRU依据页面的最近访问时间排序

LRU需要动态地调整顺序

FIFO依据页面进入内存的时间排序

FIFO的页面进入时间是固定不变的

LRU可退化成FIFO

如页面进入内存后没有被访问，最近访问时间与进入内存的时间相同

例如:给进程分配3个物理页面，逻辑页面的访问顺序为1、2、3、4、5、6、1、2、3...

LRU算法性能较好，但系统开销较大

FIFO算法系统开销较小，会发生Belady现象

Clock算法是它们的折衷

页面访问时，不动态调整页面在链表中的顺序，仅做标记

缺页时，再把它移动到链表末尾

对于未被访问的页面，Clock和LRU算法的表现一样好

对于被访问过的页面，Clock算法不能记录准确访问顺序，而LRU算法可以

Belady现象【FOCUS】

现象：

分配的物理页面数增加，缺页次数反而上升的异常现象。

采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象

原因：

FIFO算法的置换特征与进程访问内存的动态特征矛盾

被它置换出去的页面并不一定是进程近期不会访问的

FIFO算法有Belady现象

LRU算法没有Belady 现象

工作集置换算法

算法思路

换出不在工作集中的页面

窗口大小τ

当前时刻前τ个内存访问的页引用是工作集，τ被称为窗口大小

算法实现

访存链表：维护窗口内的访存页面链表

访存时，换出不在工作集的页面；更新访存链表

缺页时，换入页面；更新访存链表

示例

缺页率置换算法（PFF, Page-Fault-Frequency）

通过调节常驻集大小，使每个进程的缺页率保持在一个合理的范围内

若进程缺页率过高，则增加常驻集以分配更多的物理页面

若进程缺页率过低，则减少常驻集以减少它的物理页面数

算法实现

访存时，设置引用位标志

缺页时，计算从上次缺页时间tlast 到现在tcurrent 的时间间隔

如果tcurrent– tlast ≤ T, 则增加缺失页到工作集中

示例

抖动问题(thrashing)【FOCUS】

抖动

进程物理页面太少，不能包含工作集

造成大量缺页，频繁置换

进程运行速度变慢

产生抖动的原因

随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升

操作系统需在并发水平和缺页率之间达到一个平衡

选择一个适当的进程数目和进程需要的物理页面数

四、文件管理

文件的基本操作【FOCUS】

创建：①找到物理空间；②在目录中创建条目，记录文件的名称、位置及信息（创建的是文件目录项）

写文件：参数（文件名称，要写入的内容），系统为该文件维护一个写位置的指针，一旦发生写操作，更新写指针

读文件：参数（文件名称，要读入的内存位置），系统维护一个读位置指针，一旦发生读操作，更新度指针

通常，一个进程只对一个文件进行读或写，因此系统为每个进程维护一个当前位置指针，读写使用同一指针，节省系统空间，降低系统复杂度

文件重定位（寻址）：按某条件搜索目录，将当前文件位置设定为给定值。不会读或写文件

删除文件：从目录中找到要删除文件的目录项，置为空项，并回收该文件所占的存储空间

截断文件：允许文件所有属性保持不变，并删除文件内容，即将其长度设为0，并释放其空间

以上6项基本操作可以组合执行其他文件操作

如复制，创建新文件→从旧文件读出→写入新文件

目录

文件“外部”的逻辑结构问题，多个文件间在逻辑上是如何组织的

从用户角度看，目录在用户需要的文件名和文件之间提供一种映射，目录管理要实现“按名存取”

共享系统中，目录还需要提供用于控制文件访问的信息

需要提高对目录的检索速度

允许文件重名

通过树形结构来解决和实现上述问题

目录操作

搜索：当用户使用一个文件时，需要搜索目录，易找到该文件的对应目录项

创建文件：当创建一个新文件时，需要在目录中增加一个目录项

删除文件：当删除一个文件时，需要在目录中删除相应的目录项

显示目录：用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性

修改目录：某些文件属性保存在目录中，因此这些属性的变化需要改变相应的目录项

单极目录结构

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

实现了按名存储

查找速度慢，文件不允许重名、不便于文件共享

二极目录结构

将文件目录分成主文件目录和用户文件目录两级

解决了多用户之间重名问题，可以在目录上实现访问限制

缺乏灵活性，不能对文件进行分类

多极目录结构（树形结构）

将两级目录的层次关系进行推广，形成多级目录结构

绝对路径，从根目录出发的路径

相对路径，从当前目录出发的路径

方便分类、层次清晰、增加磁盘访问次数

五、设备管理

I/O子系统的层次结构【FOCUS】

用户层I/O软件

实现与用户交互的接口

用户可直接调用在用户层提供的与I/O有关的库函数，对设备进程操作

一般而言大部分I/O软件都在操作系统内核

用户层软件必须通过系统调用来获取操作系统服务

内核I/O子系统

实现用户程序与设备驱动的统一接口、设备命令、设备保护、以及设备分配和释放等

同时为设备管理和数据传送提供必要的存储空间

使得应用程序独立于具体使用的物理设备

为了实现设备独立，须在驱动程序之上实现一层设备独立软件

设备驱动程序

与硬件直接相关

实现系统对设备发出操作指令，驱动I/O设备工作

每类设备配置一个设备驱动程序

为上层进程提供一组标准接口，设备具体差别被驱动程序封装

接受上层的I/O请求后转换成具体命令后，发送给设备控制器，控制I/O设备工作

中断处理程序

保护被中断进程的CPU现场

转入相应的中断处理程序进行处理

处理完毕后恢复被中断进程的现场，返回被中断的进程

硬件

通常包括一个机械部件和一个电子部件

电子部件称为设备控制器（适配器）

接受和识别CPU或通道发来的命令

实现数据交换：

设备和控制器之间

控制器和主存之间

发现和记录设备状态，供CPU处理和使用

设备地址识别

机械部件是设备本身

I/O请求生命周期【FOCUS】

假脱机技术（SPOOLing）【FOCUS】

为了缓和CPU的高速性与IO设备的低速性

利用专门的外围控制机，将低速IO设备上的数据传送到高速磁盘上

外部设备同时联机操作

操作系统将独占设备改造成共享设备的技术

输入井，模拟脱机出入磁盘，用于收容IO设备输入的数据

输出井，模拟脱机输出磁盘，用户收容用户程序的输出数据

输入缓冲区，用于暂存由输入设备送来的数据，之后传到输入井

输出缓冲区，用于暂存从输出井送来的数据，再传送给输出设备

输入进程，模拟脱机输入时的外围控制机，将用户要求的数据从输入机通过输入缓冲区再送到输入井，CPU需要数据时，直接从输入井读取

输出进程，模拟脱机输出时的外围控制机，把用户要输出的数据先从内存送入输出井，带输出设备空闲的时候，再将输出的数据通过缓冲区送到输出设备

特点：【FOCUS】【FOCUS】【FOCUS】

提高了IO（作业执行）的速度

将独占设备改成了共享设备（提高独占设备的利用率）

实现了虚拟设备的功能

是一种空间换时间的技术