学习文档站

第一章计算机系统概述

1 操作系统的基本概念

1.1 操作系统的概念

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

1.2 操作系统的特征

操作系统的四大特征：

并发
- 并发:指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。
- 常考易混概念――并行:指两个或多个事件在同一时刻同时发生。
共享
- 共享即资源共享，指系统资源可以供内存中多个并发的程序使用，分为互斥共享和同时共享两种模式
  - 互斥共享：一段时间内只允许一个进程访问该资源
  - 同时共享：一段时间内允许多个进程“同时”访问该资源
虚拟
- 虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者)是用户感受到的。
异步
- 异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

其中，并发与共享是最基本的特征，二者互为存在条件

1.3 操作系统的功能和目标

系统资源的管理者

用户与硬件之间的接口

硬件机器的扩展

操作系统对硬件机器的拓展:通过优秀工匠，这些简单的原料可以组织成房子、帆船、匹诺曹。。。

普通用户可直接使用工匠提供的房子、帆船、匹诺曹，而无需关心这些东西在底层是怎么组织起来工作的

2 操作系统的发展与分类

2.1 手工操作阶段

用户在计算机上算题的所有工作都要人工干预，如程序的装入、运行、结果的输出等。随着计算机硬件的发展，

人机矛盾(速度和资源利用）越来越大，必须寻求新的解决办法。

手工操作阶段有两个突出的缺点:

① 用户独占全机，不会出现因资源已被其他用户占用而等待的现象，但资源利用率低。

② CPU等待手工操作，CPU的利用不充分。

唯一的解决办法就是用高速的机器代替相对较慢的手工操作来对作业进行控制。

2.2 批处理阶段

为了解决人机矛盾及CPU和IO设备之间速度不匹配的矛盾，出现了批处理系统。

它按发展历程又分为单道批处理系统、多道批处理系统

2.2.1 单道批处理系统

系统对作业的处理是成批进行的，但内存中始终保持一道作业。单道批处理系统是在解决人机矛盾及CPU和IO设备速率不匹配的矛盾中形成的。单道批处理系统的主要特征如下:

自动性
- 在顺利的情况下，磁带上的一批作业能自动地逐个运行，而无须人工干预。
顺序性
- 磁带上的各道作业顺序地进入内存，各道作业的完成顺序与它们进入内存的顺序在正常情况下应完全相同，亦即先调入内存的作业先完成。
单道性
- 内存中仅有一道程序运行，即监督程序每次从磁带上只调入一道程序进入内存运行，当该程序完成或发生异常情况时，才换入其后继程序进入内存运行。

此时面临的问题是:每次主机内存中仅存放一道作业，每当它在运行期间（注意这里是“运行时”而不是“完成后”)发出输入/输出请求后，高速的CPU便处于等待低速的IO完成状态。

为了进一步提高资源的利用率和系统的吞吐量，引入了多道程序技术。

2.2.2 多道批处理系统

多道程序设计技术允许多个程序同时进入内存并允许这些它们在CPU 中交替地运行，这些程序共享系统中的各种硬/软件资源。当一道程序因I/O请求而暂停运行时，CPU便立即转去运行另一道程序。

它不采用某些机制来提高某一技术方面的瓶颈问题，而让系统的各个组成部分都尽量去“忙”，因此切换任务所花费的时间很少，可实现系统各部件之间的并行工作，使其整体在单位时间内的效率翻倍。

当然，多道批处理系统的设计和实现要比单道系统复杂很多，因为要充分利用各种资源，就要涉及各种资源的调度问题。

多道程序设计的特点是多道、宏观上并行、微观上串行。

多道
- 计算机内存中同时存放多道相互独立的程序。
宏观上并行
- 同时进入系统的多道程序都处于运行过程中，即它们先后开始各自的运行，但都未运行完毕。
微观上串行
- 内存中的多道程序轮流占有CPU，交替执行。

多道程序设计技术的实现需要解决下列问题:

如何分配处理器。
多道程序的内存分配问题。
IO设备如何分配。
如何组织和存放大量的程序和数据，以方便用户使用并保证其安全性与一致性。

在批处理系统中采用多道程序设计技术就形成了多道批处理操作系统。该系统把用户提交的作业成批地送入计算机内存，然后由作业调度程序自动地选择作业运行。

优点:资源利用率高，多道程序共享计算机资源，从而使各种资源得到充分利用:系统吞吐量大，CPU和其他资源保持“忙碌”状态。

缺点:用户响应的时间较长;不提供人机交互能力，用户既不能了解自己的程序的运行情况，又不能控制计算机。

2.3 分时操作系统

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

主要特征：

同时性
- 同时性也称多路性，指允许多个终端用户同时使用一台计算机，即一台计算机与若干台终端相连接，终端上的这些用户可以同时或基本同时使用计算机。.
交互性
- 用户能够方便地与系统进行人机对话，即用户通过终端采用人机对话的方式直接控制程序运行，与同程序进行交互。
独立性
- 系统中多个用户可以彼此独立地进行操作，互不干扰，单个用户感觉不到别人也在使用这台计算机，好像只有自己单独使用这台计算机一样。
及时性
- 用户请求能在很短时间内获得响应。分时系统采用时间片轮转方式使一台计算机同时为多个终端服务，使用户能够对系统的及时响应感到满意。

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

2.4 实时操作系统

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

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

2.5 网络操作系统和分布式计算机系统

网络操作系统：
- 是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享和各台计算机之间的通信。
分布式操作系统：
- 主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。

2.6 个人计算机操作系统

个人计算机操作系统:如Windows XP、MacOs，方便个人使用。

3 操作系统的运行环境

3.1 操作系统的运行机制

指令：处理器能识别、执行的最基本命令。

两种指令：

特权指令：不允许用户使用
非特权指令：用户可以使用

CPU如何判断当前是否可以执行特权指令?

两种处理器状态：

用户态：只能执行非特权指令
核心态：特权指令、非特权指令都可以执行

两种程序：

内核程序：操作系统的内核程序是系统的管理者，既可以执行特权指令，也可以执行非特权指令，运行在核心态。
应用程序：为了保证系统能安全运行，普通应用程序只能执行非特权指令，运行在用户态。

3.2 中断和异常的概念

3.2.1 中断机制的诞生

早期的计算机，各程序只能串行执行，系统资源利用率低。

为了解决上述问题，人们发明了操作系统（作为计算机的管理者)，引入中断机制，实现了多道程序并发执行本质:

发生中断就意味着需要操作系统介入，开展管理工作。

3.2.2 中断的概念和作用

当中断发生时，CPU立即进入核心态
当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理
对于不同的中断信号，会进行不同的处理

由于操作系统的管理工作需要使用特权指令，因此CPU要从用户态转为核心态。

中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。

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

3.2.3 用户态、核心态之间如何切换？

用户态->核心态的唯一方式：中断

核心态->用户态：通过执行一个特权指令，将程序状态字( PSW）的标志位设置为“用户态”

4.2.4 中断的分类

第一种分类：

第二种分类

4.2.5 外中断的处理过程

执行完每个指令之后，CPU都要检查当前是否有外部中断信号
如果检测到外部中断信号，则需要保护被中断进程的CPU环境（如程序状态字PSw、程序计数器PCc、各种通用寄存器)
根据中断信号类型转入相应的中断处理程序
恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

3.3 系统调用

3.3.1 系统调用的概念和功能

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

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

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

系统调用相关处理涉及到对系统资源的管理、对进程的控制,这些功能需要执行一些特权指令才能完成，因此系统调用的相关处理需要在核心态下进行

3.3.2 系统调用按功能分类

设备管理
- 完成设备的请求/释放/启动等功能
文件管理
- 完成文件的读/写/创建/删除等功能
进程控制
- 完成进程的创建/撤销/阻塞/唤醒等功能
进程通信
- 完成进程之间的消息传递/信号传递等功能
内存管理
- 完成内存的分配/回收等功能

3.3.3 系统调用和库函数的区别

3.3.4 系统调用背后的过程

传递系统调用参数
执行陷入指令
执行系统调用相应服务程序
返回用户程序

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

执行陷入指令会产生内中断，使处理器从用户态进入核心态。

4 操作系统的体系结构

内核是计算机上配置的底层软件，是操作系统最基本、最核心的部分。

实现操作系统内核功能的那些程序就是内核程序。

与硬件关联

时钟管理

实现计时功能

中断处理

负责实现中断机制

原语

是一种特殊的程序
处于操作系统最底层，是最接近硬件的部分
这种程序的运行具有原子性——其运行只能一气呵成，不可中断
运行时间较短、调用频繁

对系统资源进行管理的功能

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

4.1 大内核和微内核

大内核
- 将操作系统的主要功能模块都作为系统内核，运行在核心态
- 优点：高性能
- 缺点：内核代码庞大，结构混乱，难以维护
微内核
- 只把最基本的功能保留在内核
- 优点:内核功能少，结构清晰，方便维护
- 缺点:需要频繁地在核心态和用户态之间切换，性能低

第二章进程管理

1 进程与线程

1.1 进程的概念和特征

程序：就是一个指令序列

早期的计算机(只支持单道程序)，在内存中，程序的代码放在程序段内，数据放在数据段内。

引入多道程序技术以后，为了方便操作系统管理，完成各程序并发执行，引入了进程、进程实体的概念。

1.1.1 进程的定义

PCB：系统为每个运行的程序配置一个数据结构，称为进程控制块（PCB)，用来描述进程的各种信息（如程序代码存放位置)

进程：PCB、程序段、数据段三部分构成了进程实体（进程映像)，一般情况下简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB;而撤销进程，实质上是撤销进程实体中的PCB。

注意:PCB是进程存在的唯一标志！

从不同的角度，进程可以有不同的定义，比较传统典型的定义有:

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

引入进程实体的概念后，可把进程定义为:

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

注:严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的。不过，除非题目专门考察二者区别，否则可以认为进程实体就是进程。因此我们也可以说“进程由程序段、数据段、PCB三部分组成”

1.1.2 进程的组成

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

PCB的组成部分

1.1.3 进程的特征

进程和程序是两个截然不同的概念，相比于程序，进程拥有以下特征:

动态性
- 进程是程序的一次执行过程，是动态地产生、变化和消亡的
并发性
- 内存中有多个进程实体，各进程可并发执行
独立性
- 进程是能独立运行、独立获得资源、独立接受调度的基本单位
异步性
- 各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题
结构性
- 每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成

其中，需要注意的是：

动态性是进程最基本的特征

进程是资源分配、接受调度的基本单位

异步性会导致并发程序执行结果的不确定性。具体会在“进程同步”相关小节进行学习

1.2 进程的状态与转换

进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时又需要等待CPU服务，可见，进程的状态是会有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态。

1.2.1 三种基本状态

运行态(Running)
- 占有CPU，并在CPU上运行
就绪态(Ready)
- 已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
阻塞态(Waiting/Blocked，又称:等待态)
- 因等待某一事件而暂时不能运行

1.2.2 进程的另外两种状态

创建态(New，又称:新建态)
- 进程正在被创建，操作系统为进程分配资源、初始化PCB
终止态(Terminated，又称:结束态)
- 进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

1.2.3 进程状态的转换

1.3 进程控制

1.3.1 什么是进程控制

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

简化理解:反正进程控制就是要实现进程状态转换

1.3.2 如何实现进程控制

用原语实现进程控制。原语的特点是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。

原语采用“关中断指令”和“开中断指令”实现。

显然，关/开中断指令的权限非常大，必然是只允许在核心态下执行的特权指令。

1.3.3 进程控制相关的原语

学习技巧:进程控制会导致进程状态的转换。无论哪个原语，要做的无非三类事情

更新PCB中的信息（如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
- a. 所有的进程控制原语一定都会修改进程状态标志
- b. 剥夺当前运行进程的CPU使用权必然需要保存其运行环境c.某进程开始运行前必然要恢复期运行环境
将PCB插入合适的队列
分配/回收资源

进程的创建

进程的终止

进程的阻塞和唤醒

进程的切换

1.4 进程的组织

在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应该用适当的方式把这些PCB组织起来。

注:进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式问题

进程的组织方式

链接方式
- 按照进程状态将PCB分为多个队列
- 操作系统持有指向各个队列的指针
索引方式
- 根据进程状态的不同，建立几张索引表
- 操作系统持有指向各个索引表的指针

链接方式如图

索引方式如图

1.5 进程的通信

1.5.1 什么是进程通信

顾名思义，进程通信就是指进程之间的信息交换。

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

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

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

共享存储
管道通信
消息传递

1) 共享存储

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

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

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

2) 管道通信

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

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

3) 消息传递

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

消息的结构

消息头
- 发送进程ID
- 接收进程ID
- 消息类型
- 消息长度
消息体

消息传递的方式

直接通信方式
- 消息直接挂到接收进程的消息缓冲队列上

间接通信方式
- 消息要先发送到中间实体（信箱）中，因此也称“信箱通信方式”。Eg:计网中的电子邮件系统

1.6 线程概念和多线程模型

1.6.1 什么是线程

可以把线程理解为“轻量级进程”。

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件)。

引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。线程则作为处理机的分配单元。

1.6.2 引入线程后的变化

资源分配、调度
- 传统进程机制中，进程是资源分配、调度的基本单位
- 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
并发性
- 传统进程机制中，只能进程间并发
- 引入线程后，各线程间也能并发，提升了并发度
系统开销
- 传统的进程间并发，需要切换进程的运行环境，系统开销很大
- 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境
- 引入线程后，并发所带来的系统开销减小

1.6.3 线程的属性

1.6.4 线程的实现

1) 用户级线程

用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责（包括线程切换) 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。

在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。（用户级线程对用户不透明，对操作系统透明)

可以这样理解，“用户级线程”就是“从用户视角看能看到的线程”

2) 内核级线程

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

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

组合方式

在同时支持用户级线程和内核级线程的系统中，可采用二者组合的方式:将n个用户级线程映射到m个内核级线程上 ( n >= m)

重点:

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

多线程模型

在同时支持用户级线程和内核级线程的系统中，由几个用户级线程映射到几个内核级线程的问题引出了“多线程模型”问题。

多对一模型

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

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

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

一对一模型

一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

优点:当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

缺点:一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多对多模型

n用户及线程映射到m个内核级线程(n >= m)。每个用户进程对应m个内核级线程。

克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

2 处理机调度

2.1 调度的概念

2.1.1 调度的基本概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。

2.1.2 调度的三个层次

高级调度
中级调度
低级调度

1) 高级调度（作业调度）

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

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

2) 中级调度(内存调度)

引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。

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

暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

3) 低级调度（进程调度)

低级调度（进程调度)，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

补充知识:进程的挂起态与七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend)

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态，五状态模型→七状态模型

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

两种状态都是暂时不能获得CPU的服务，

但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

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

三层调度的联系与对比

2.2 调度的时机、切换与过程

2.2.1 进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

需要进行进程调度与切换的情况

当前运行的进程主动放弃处理机
- 进程正常终止
- 当前运行的进运行过程中发生异常而终止
- 进程主动请求阻塞（如等待I/O)
当前运行的进程被动放弃处理机
- 分给进程的时间片用完
- 有更紧急的事需要处理（如I/O中断)
- 有更高优先级的进程进入就绪队列

不能进行进程调度与切换的情况

在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
进程在操作系统内核程序临界区中。
在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)

2.2.2 进程的切换与过程

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

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

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

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

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

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

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

2.3 进程调度方式

非剥夺调度方式（非抢占方式）。
- 即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
- 实现简单,系统开销小但是无法及时处理紧急任务,适合于早期的批处理系统
剥夺调度方式（抢占方式）。
- 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
- 可以优先处理更紧急的进程,也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。适合于分时操作系统、实时操作系统

2.4 调度的基本准则

CPU利用率
系统吞吐量
周转时间
- 周转时间、平均周转时间
- 带权周转时间、平均带权周转时间
等待时间
响应时间

2.4.1 CPU利用率

由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作CPU利用率:指CPU“忙碌”的时间占总时间的比例。

有的题目还会要求计算某种设备的利用率，通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算

Eg:某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少?

2.4.2 系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业

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

Eg:某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为? 10/100 = 0.1道/秒

2.4.3 周转时间

对寸计算机的用尸来说，他很关心目己的作业从提父到完成化了多少时间。周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

它包括四个部分：

作业在外存后备队列上等待作业调度（高级调度）的时间、

进程在就绪队列上等待进程调度（低级调度）的时间、

进程在CPU上执行的时间、

进程等待I/o操作完成的时间。

后三项在一个作业的整个处理过程中，可能发生多次。

2.4.4 等待时间

计算机的用户希望自己的作业尽可能少的等待处理机

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

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

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

一个作业总共需要被CPU服务多久，被I/o设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

2.4.5 响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。

响应时间，指从用户提交请求到首次产生响应所用的时间。

2.5 典型的调度算法

2.5.1 先来先服务(FCFS)

算法思想
- 主要从“公平”的角度考虑(类似于排队买东西)
算法规则
- 按照作业/进程到达的先后顺序进行服务
用于作业/进程调度
- 用于作业调度时，考虑的是哪个作业先到达后备队列
- 用于进程调度时，考虑的是哪个进程先到达就绪队列
是否可抢占?
- 非抢占式的算法
优缺点
- 优点:公平、算法实现简单
- 缺点:排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很天，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利(Eg:排队买奶茶..)
是否会导致饥饿
- 不会

2.5.2 短作业优先(SJF)

算法思想
- 追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
算法规则
- 最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短）
用于作业/进程调度
- 既可用于作业调度，也可用于进程调度
- 用于进程调度时称为“短进程优先(SPF）算法”
是否可抢占?
- SJF和SPF是非抢占式的算法。
- 但是也有抢占式的版本――最短剩余时间优先算法(SRTN）
优缺点
- 优点:“最短的”平均等待时间、平均周转时间
- 缺点:不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
是否会导致饥饿
- 会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

2.5.3 高响应比优先(HRRN)

算法思想
- 要综合考虑作业/进程的等待时间和要求服务的时间
算法规则
- 在每次调度时先计算各个作业/进程的响应比，选择响应响应比最高的作业/进程为其服务
- 响应比=(等待时间+要求服务时间)/要求服务时间
用于作业/进程调度
- 即可用于作业调度，也可用于进程调度
是否可抢占?
- 非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
优缺点
- 综合考虑了等待时间和运行时间（要求服务时间)
- 等待时间相同时，要求服务时间短的优先(SJF 的优点)
- 要求服务时间相同时，等待时间长的优先(FCFS的优点)
- 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
是否会导致饥饿
- 不会

2.5.4 时间片轮转（RR)

算法思想
- 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
- 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
用于作业/进程调度
- 用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
是否可抢占?
- 若进程未能在时间片内运行完，将被强行剥夺处理机使用权
- 因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片己到
优缺点
- 优点:公平;响应快，适用于分时操作系统;
- 缺点:由于高频率的进程切换，因此有一定开销：不区分任务的紧急程度。
是否会导致饥饿
- 不会
补充
- 时间片太大或太小分别有什么影响?

2.5.5 优先级调度算法

算法思想
- 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
- 调度时选择优先级最高的作业/进程
用于作业/进程调度
- 既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
是否可抢占?
- 抢占式、非抢占式都有
- 非抢占式只需在进程主动放弃处理机时进行调度即可
- 而抢占式还需在就绪队列变化时，检查是否会发生抢占
优缺点
- 优点:用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
- 缺点:若源源不断地有高优先级进程到来，则可能导致饥饿
是否会导致饥饿
- 会

2.5.6 多级反馈队列调度算法

算法思想
- 对其他调度算法的折中权衡
算法规则
- 1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 1. 新进程到达时先进入第1级队列，按FCFs原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
- 1. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
用于作业/进程调度
- 用于进程调度
是否可抢占?
- 抢占式的算法。在k 级队列的进程运行过程中，若更上级的队列( 1~k1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
优缺点
- 对各类型进程相对公平（FCFS的优点）﹔
- 每个新到达的进程都可以很快就得到响应（RR的优点)﹔
- 短进程只用较少的时间就可完成(SPF的优点）﹔
- 不必实现估计进程的运行时间（避免用户作假)﹔
- 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、l/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)
是否会导致饥饿
- 会

3 进程同步

3.1进程同步的基本概念

3.1.1 临界资源

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

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

对临界资源的访问，分成4个部分：

进入区：
- 负责检查是否可进入临界区,若可进入,则应设置正在访问临界资源的标志(可理解为“上锁”)以阻止其他进程同时进入临界区
临界区：
- 访问临界资源的代码
退出区：
- 负责解除正在访问临界资源的标志(可以理解为"解锁")
剩余区：
- 做其他处理

do{
    entry section //进入区
    critical section //临界区
    exit section //退出区
    remainder section //剩余区
}
while(true)

3.1.2 同步

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

3.1.3 互斥

互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

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

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区;
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

3.2 实现临界区互斥的基本方法

3.2.1 软件实现方法

1) 单标志法

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

turn 的初值为0，即刚开始只允许0号进程进入临界区。

若P1先上处理机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度，切换 P0上处理机运行。

代码①不会卡住 P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在⑤。

只有P0在退出区将turn改为1后，P1才能进入临界区。

因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”

turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn的值。也就是说，对于临界区的访问，一定是按P0→P1→P0→P1→..…..这样轮流访问。

这种必须“轮流访问”带来的问题是，如果此时允许进入临界区的进程是 P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。

因此，单标志法存在的主要问题是:违背“空闲让进”原则。

2) 双标志先检查法

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

若按照①⑤②⑥③⑦....的顺序执行，PO和P1将会同时访问临界区。因此，双标志先检查法的主要问题是:违反“忙则等待”原则。原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

3) 双标志后检查法

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

若按照1⑤②6....的顺序执行，PO和P1将都无法进入临界区因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

4）peterson算法

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

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。 Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

3.2.2 硬件实现方法

1) 中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

优点:
- 简单、高效
缺点:
- 不适用于多处理机:只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

2) TestAndSet指令

简称TS指令，也有地方称为TestAndSetLock 指令，或TSL指令

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

若刚开始lock 是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPu并循环执行TSL指令，从而导致“忙等”。

3) Swap指令

有的地方也叫Exchange指令，或简称XCHG指令。 Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用c语言描述的逻辑

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在 old变量上），再将上锁标记lock设置为 true，最后检查old，如果 old为 false 则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。优点:实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境缺点:不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

3.3 信号量

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语: wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量s其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、v操作（来自荷兰语 proberen和 verhogen)。因此，做题的时候常把wait(S)、 signal(S)两个操作分别写为P(S)、v(S)

3.3.1 整型信号量

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

与普通整数变量的区别:对信号量的操作只有三种,即初始化、P操作、V操作

“检查”和“上锁”一气呵成,避免了并发、异步导致的问题

存在的问题:不满足“让权等待”原则，会发生“忙等”

Eg :某计算机系统中有一台打印机...

int S = 1  //初始化整型信号量s，表示当前系统中可用的打印机资源数

void wait(int S){  // wait原语，相当于“进入区”
	while(S <= 0){  //如果资源数不够，就一直循环等待
        S = S - 1;  //如果资源数够，则占用一个资源
    }
}

void signal(int S){  // signal原语，相当于“退出区”
    S = S + 1;  // 使用完资源后，在退出区释放资源
}

3.3.2 记录型信号量

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

/*记录型信号量的定义*/
typedef struct{
    int value; //资源数量
    struct process *L; //等待队列
} semaphore;

/*某进程需要使用资源时，通过wait原语申请*/
void wait (semaphore S){
    S.value --;
	/*如果剩余资源数不够，使用block原语使进程从运行态进入阻塞态，
    并把挂到信号量S的等待队列（即阻塞队列）中*/
    if(S.value < 0){ 
        block(S.L)
    }
}

/*进程使用完资源后，通过signal原语释放*/
void signal (semaphore S) {
	S.value ++;
 	/*释放资源后，若还有别的进程在等待这种资源，
 	则使用wakeup 原语唤醒等待队列中的一个进程，该进程从阻塞态变为就绪态*/
	if (s.value <= 0) {
        wakeup(S.L);
    }
}

在考研题目中wait(S)、signal(S)也可以记为P(S)、v(S),这对原语可用于实现系统资源的“申请”和“释放”。 S.value 的初值表示系统中某种资源的数目。

对信号量s的一次Р操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减1，当S.value <0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞（当前运行的进程从运行态→>阻塞态），主动放弃处理机，并插入该类资源的等待队列s.L中。可见，该机制遵循了“让权等待”原则，不会出现“忙等”现象。

对信号量s的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加1，若加1后仍是S.value <=0，表示依然有进程在等待该类资源，因此应调用wakeup 原语唤醒等待队列中的第一个进程（被唤醒进程从阻塞态→就绪态）。

3.3.3 利用信号量实现互斥

分析并发进程的关键活动，划定临界区（如:对临界资源打印机的访问就应放在临界区)
设置互斥信号量mutex，初值为1
在临界区之前执行P(mutex)
在临界区之后执行v(mutex)

/*信号量实现互斥*/
semaphore S = 1;//初始化信号量

P1(){ // 进程1
    ……
	P(S);//准备开始访问临界资源，加锁
	进程P1的临界区
	V(S);//访问结束，解锁 
    ……
)
        
P2(){ // 进程2
    ……     
	P(S);//准备开始访问临界资源，加锁	 
    进程P2的临界区
	V(S); // 访问结束，解锁
    ……
 }

3.3.4 利用信号量实现同步

用信号量实现进程同步:

分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码)
设置同步信号量S,初始为0
在“前操作”之后执行v(S)
在“后操作”之前执行P(S)

/*信号量实现同步*/
semaphore S = 0;//初始化信号量

P1(){
    代码1;
    代码2;
    P(S);
    代码3;
}

P2(){
	代码4;
	V(S);
	代码5;
	代码6;
}

3.3.5 利用信号量实现前驱关系

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

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

要为每一对前驱关系各设置一个同步变量
在“前操作”之后对相应的同步变量执行v操作
在“后操作”之前对相应的同步变量执行Р操作

如图所示：

3.4 管程

3.4.1 为什么要引入管程

信号量机制存在的问题:编写程序困难、易出错

能不能设计一种机制，让程序员写程序时不需要再关注复杂的PV操作，让写代码更轻松呢?

1973年，Brinch Hansen首次在程序设计语言(Pascal) 中引入了“管程”成分――一种高级同步机制

3.4.2 管程的定义和基本特征

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

局部于管程的共享数据结构说明;
对该数据结构进行操作的一组过程;
对局部于管程的共享数据设置初始值的语句;
管程有一个名字。

跨考Tips:“过程”其实就是“函数”

管程的基本特征:

局部于管程的数据只能被局部于管程的过程所访问;
一个进程只有通过调用管程内的过程才能进入管程访问共享数据;
每次仅允许一个进程在管程内执行某个内部过程。

3.5 经典同步问题

3.5.1 生产者-消费者问题

问题描述

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

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

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

缓冲区是临界资源，各进程必须互斥地访问。

问题分析

如何实现

semaphore mutex = 1;//临界区互斥信号量
semaphore empty = n;//空闲缓冲区
semaphore full = 0;//缓冲区初始化为空

producer(){ //生产者进程
	while(1){
		produce an item in nextp; //生产数据
		P(empty);(要用什么，P一下) //获取空级冲区单元			
		P(mutex); （互斥夹紧) //进入临界区
		add nextp to buffer;（行为) //将数据放入缓冲区
		V(mutex);(互斥夹紧） //离开临界区,释放互斥信号量
        V(full);(提供什么，V一下) //满缓冲区数加1
	}
}
                  
consumer (){ //消费者进程
	while(1){
		P(ful1); //获取满缓冲区单元
		P(mutex); //进入临界区
		从缓冲区中取出数据; 
		V(mutex); //离开临界区,释放互斥信号量
		V(empty); //空缓冲区数加1
		消费数据;
    }
}

3.5.2 多生产者-消费者问题

问题描述

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

问题分析

如何实现

semaphore plate = 1,apple = 0,orange = 0;

dad(){//父亲进程
while(1){
    准备苹果; 
    P(Plate);//互斥向盘中取、放水果
    向盘中放苹果;
    V(apple);//允许取苹果
}

mom(){//母亲进程
	while(1){
    	准备橘子;
    	P(plate);//互斥向盘中取、放水果
    	向盘中放橘子
    	V(orange);//允许取橘子
	}
}

son() {//儿子进程
	while(1){
		P(orange);//互斥向盘中取橘子
		从盘子拿走橘子;
		V(plate);//允许向盘中取、放水果
		吃橘子;
    }
}

daughter(){//女儿进程
    while(1){
        P(apple);//互斥向盘中取苹果
		从盘子拿走苹果;
		V(plate);//运行向盘中取、故水果
		吃苹果;
    }
}

3.5.3 吸烟者问题

问题描述

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

问题分析

如何实现

int random;//存储随机数
semaphore offer1 = 0;//定义信号量对应烟草和纸组合的资源
semaphore offer2 = 0;//定义信号量对应烟草和胶水组合的资源
semaphore offer3 = 0;//定义信号量对应纸和胶水组合的资源
semaphore finish = 0;//定义信号量表示抽烟是否完成

process provider(){//供应者
	while(1){
		random = 任意一个整数随机数;
        random = random % 3;
		if(random == O){
            V(offer1);//提供烟草和纸
        }else if(random == 1){
            v(offer2);//提供烟草和胶水
        }else{
            v(offer3);//提供纸和胶水
        }
        任意两种材料放在桌子上;
		P(finish);
    }
}
		
process smoke(){//拥有烟草者
    while(1){
        P(offer3);
        拿纸和胶水，卷成烟，抽掉;
        V(offer3);
    }
}

process paper(){//拥有纸者
    while(1){
        P(offer2);
        拿烟草和胶水，卷成烟，抽掉;
        V(offer2);
    }
}

process glue(){//拥有胶水者
    while(1){
        P(offer1);
        拿烟草和胶水，卷成烟，抽掉;
        V(offer1);
    }
}

3.5.4 读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求:①允许多个读者可以同时对文件执行读操作;②只允许一个写者往文件中写信息;③任一写者在完成写操作之前不允许其他读者或写者工作;④写者执行写操作前，应让己有的读者和写者全部退出。

问题分析

如何实现

/*读进程优先*/
int count=0;//用于记录当前的读者数量
semaphore mutex=l;//用于保护更新count变量时的互斥
semaphore rw=1;//用于保证读者和写者互斥地访问文件

writer(){//写者进程
	while(1){
		P(rw) ;//互斥访问共享文件
		写入;
		v(rw);//释放共享文件  
    }
}

 reader({//读者进程
 	while(1){
        P(mutex);//互斥访问count变量
        if (count == 0){//当第一个读进程读共享文件时
            P(rw);//阻止写进程写
        }
        count ++;//读者计数器加1
        v(mutex);//释放互斥变量count
		读取;
		P(mutex);//互斥访问count变量
		count --;//读者计数器减1
		if(count==0){//当最后一个读进程读完共享文件
    		V(rw);//允许写进程写
		}
 		V(mutex);//释放互斥变量count
    }
 }

/*写进程优先*/
semaphore rw = 1;//用于实现对文件的互斥访问
int count = 0;//记录当前有几个读进程在访问文件
semaphore mutex = 1;//用于保证对count变量的互斥访问
semaphore w = 1;//用于实现“写优先”

writer(){//写者进程
	while (1){
	P(w);//互斥访问“写优先”
    P(rw);//互斥访问共享文件
    写文件;
    V(rw);//释放共享文件  
    V(w);//释放“写优先”
	}
}

reader(){//读者进程
	while(1){
		P(w);//在无写进程请求时进入
		P(mutex);//互斥访问count变量
 		if(count == O){
            P(rw);//阻止写进程写
        }
		count ++;//读者计数器加1
		V(mutex);//释放互斥变量count
        V(w);//恢复对共享文件的访问
		读文件;
    	P(mutex);//互斥访问count变量
        count --;//读者计数器减1
		if(count == 0){//当最后一个读进程读完共享文华
            v(rw);//允许写进程写
        }
		v(mutex);//释放互斥变量count
    }
}

3.5.5 哲学家进餐问题

问题描述

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

问题分析

如何实现

semaphore chopstick [5] = {1,1,1,1,1};//初始化信号量semaphore mutex=1;
semaphore mutex = 2//设置取筷子的信号量

Pi(){//i号哲学家的进程
	do{
		P(mutex);//在取筷子前获得互斥量
		P(chopstick[i]);//取左边筷子
		P(chopstick[(i+1)%5]);//取右边筷子
		V(mutex);//释放取筷子的信号量
        进餐;
		V(chopstick[i]);//放回左边筷子
		V(chopstick[(i+1)85]);//放回右边筷子
        思考;
	} while(1);
}

4 死锁

4.1 死锁的概念

4.1.1 死锁的定义

在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死切。发生死锁后若无外力干涉,这些进程都将无法向前推进。

4.1.2 死锁产生的原因

对系统资源的竞争。
- 各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的。
进程推进顺序非法。
- 请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
- 信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。(可以把互斥信号量、同步信号量也看做是一种抽象的系统资源)

4.1.3 死锁产生的必要条件

互斥条件
- 对必须互斥使用的资源的争抢才会导致死锁
不剥夺条件
- 进程保持的资源只能主动释放，不可强行剥夺
请求和保持条件
- 保持着某些资源不放的同时，请求别的资源存在一种进程资源的循环等待链
循环等待条件
- 循环等待未必死锁，死锁一定有循环等待

4.1.4 死锁、饥饿、死循环的区别

死锁:各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿:由于长期得不到想要的资源，某进程无法向前推进的现象。

死循环:某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是程序员故意设计的。

4.2 死锁的处理策略

预防死锁。破坏死锁产生的四个必要条件中的一个或几个。
避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法)
死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。

4.3 死锁预防

4.3.1 破坏互斥条件

互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁。

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

该策略的缺点:并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。

4.3.2 破坏不剥夺条件

不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。

方案一:当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。

方案二:当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如:剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)

该策略的缺点:

实现起来比较复杂。
释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
反复地申请和释放资源会增加系统开销，降低系统吞吐量。
若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。

4.3.3 破坏请求和保持条件

请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。

可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。

该策略实现起来简单，但也有明显的缺点: 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

4.3.4 破坏循环等待条件

循环等待条件:存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源〔即编号相同的资源）一次申请完。

原理分析:一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象。

该策略的缺点:

不方便增加新的设备，因为可能需要重新分配所有的编号
进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
必须按规定次序申请资源,用户编程麻烦。

4.4 死锁避免

4.4.1 安全状态

什么是安全序列

所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

4.4.2 银行家算法

银行家算法是荷兰学者Dijkstra为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁。核心思想:在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。

数据结构: 长度为m的一维数组Available表示还有多少可用资源nm矩阵Max表示各进程对资源的最大需求数 nm矩阵Allocation表示已经给各进程分配了多少资源 Max - Allocation = Need矩阵表示各进程最多还需要多少资源用长度为m的一位数组Request表示进程此次申请的各种资源数

银行家算法步骤: ①检查此次申请是否超过了之前声明的最大需求数

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

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

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

安全性算法步骤: 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。

4.5 死锁检测和解除

4.5.1 死锁的检测

为了能对系统是否已发生了死锁进行检测，必须：

①用某种数据结构来保存资源的请求和分配信息；——资源分配图

②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行卞去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。

相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程..

如果按上述过程分析，最终能消除所有边，就称这个图是可完全筒化的。此时一定没有发生死锁(相当于能找到一个安全序列)

如果最终不能消除所有边，那么此时就是发生了死锁

检测死锁的算法:

1)在资源分配图中，找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源)。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。

2）进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2就满足这样的条件。根据1)中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。

死锁定理:如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

4.5.2 死锁的解除

一旦检测出死锁的发生，就应该立即解除死锁。

补充:并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要方法有:

资源剥夺法。挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
撤销进程法（或称终止进程法）。强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息。设置还原点

第三章内存管理

1 内存管理概念

1.1 内存管理的基本原理和要求

操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么呢?

内存空间的分配与回收

操作系统要怎么记录哪些内存区域已经被分配出去了,哪些又还空闲?

当进程运行结束之后，如何将进程占用的内存空间回收?

内存空间扩充

游戏GTA的大小超过60GB，按理来说这个游戏程序运行之前需要把60GB数据全部放入内存。然而，实际我的电脑内存才4GB，但为什么这个游戏可以顺利运行呢?

地址转换功能

为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（这个过程称为地址重定位）应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。

内存保护功能

保证各道作业在各自的存储空间内运行，互不干扰。

1.1.1 程序装入和链接

内存的概念及作用

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

内存中也有一个一个的“小房间”，每个小房间就是一个“存储单元”

如果计算机“按字节编址”,则每个存储单元大小为1字节,即1B，即8个二进制位

如果字长为16位的计算机“按字编址”，则每个存储单元大小为1个字:每个字的大小为16个二进制位

思考
- 在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么，如何区分各个程序的数据是放在什么地方的呢?
方案
- 给内存的存储单元编地址,内存地址从0开始,每个地址对应一个存储单元

进程运行的原理-指令

我们写的代码要翻译成CPU能识别的指令。这些指令会告诉CPU应该去内存的哪个地址存/取数据，这个数据应该

做什么样的处理。在这个例子中，指令中直接给出了变量x的实际存放地址（物理地址）。但实际在生成机器指令

的时候并不知道该进程的数据会被放到什么位置。所以编译生成的指令中一般是使用逻辑地址(相对地址)

从写程序到程序运行

编译:由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言)

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

装入（装载）:由装入程序将装入模块装入内存运行

链接的三种方式

静态链接 : 在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块)，之后不再拆开。
装入时动态链接 : 将各目标模块装入内存时，边装入边链接的链接方式。
运行时动态链接 : 在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

装入的三种方式

绝对装入

在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。
特点:
- 绝对装入只适用于单道程序环境。
- 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。

静态重定位

又称可重定位装入。编译、链接后的装入模块的地址都是从o开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的)
特点:
- 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。

动态重定位

又称动态运行时装入。编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。
特点
- 可将程序分配到不连续的存储区中:在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存:便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间。

1.1.2 逻辑地址空间与物理地址空间

编译后,每个目标模块都从0号单元开始编址,这称为该目标模块的相对地址(或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的，它们只有系统编程人员才会涉及。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。

1.1.3 内存保护

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

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

1.2 覆盖与交换

1.2.1 覆盖

早期的计算机内存很小，比如IBM推出的第一台PC机最大只支持1MB大小的内存。因此经常会出现内存大小不够的情况。

后来人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题.

覆盖技术的思想:将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存。内存中分为一个“固定区”和若干个“覆盖区”。

需要常驻内存的段放在“固定区”中，调入后就不再调出(除非运行结束)

不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

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

1.2.1 交换

交换（对换）技术的设计思想:内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度)

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。

暂时换出外存等待的进程状态为挂起状态（挂起态，suspend)

挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

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

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间....

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

1.3 连续分配管理方式

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

1.3.1 单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据:用户区用于存放用户进程相关数据。

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

优点:
- 实现简单;
- 无外部碎片;
- 可以采用覆盖技术扩充内存;
- 不一定需要采取内存保护(eg:早期的PC操作系统MS-DOS） .
缺点:
- 只能用于单用户、单任务的操作系统中;
- 有内部碎片;
- 存储器利用率极低。

1.3.2 固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

分区大小相等:缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合（比如:钢铁厂有n个相同的炼钢炉，就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序)

分区大小不等:增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如:划分多个小分区、适量中等分区、少量大分区)

操作系统需要建立一个数据结构―一分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“己分配”。

优点:
- 实现简单，无外部碎片。
缺点:
- 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能;
- 会产生内部碎片，内存利用率低。

1.3.3 动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。(eg:假设某计算机内存大小为64MB，系统区8MB，用户区共56 MB...）

系统要用什么样的数据结构记录内存的使用情况?

当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配？

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

下个小节会介绍四种动态分区分配算法....

如何进行分区的分配与回收操作？

如何分配？

进程5需要在20M、10M、4M中选择

如果选择20M，则分区1大小=20-4=16，起始地址=8+4=12

如果选择4，则分区3耗尽，仅剩分区1、分区2

如何回收？

情况1：要回收进程4，后面有相邻的空闲分区，则合并两个分区，分区1大小=10+14=24，起始地址=32-4=28

情况2：要回收进程3，前面有相邻的空闲分区，则合并两个分区，分区2大小=18+10=28，起始地址=32

情况3：要回收进程4，前、后都有相邻的空闲分区，则合并三个分区，分区1大小=20+10+4=34，起始地址=8，原来的分区3变为分区2

情况2：要回收进程2，没有相邻的空闲分区，则进程2 变为单独的空闲区，分区大小=14，起始地址=20+8=28

动态分区分配没有内部碎片，但是有外部碎片。

内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。

外部碎片，是指内存中的某些空闲分区由于太小而难以利用。

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。

可以通过紧凑（拼凑，Compaction）技术来解决外部碎片。

1.3.4 动态分区分配算法

首次适应算法(First Fit)

算法思想
- 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现
- 空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到天小能满足要求的第一个空闲分区。

最佳适应算法(Best Fit)

算法思想
- 由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
如何实现
- 空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。
缺点
- 每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法(Worst Fit)

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

算法思想
- 为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现
- 空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
缺点
- 每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法(Next Fit)

算法思想
- 首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现
- 空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

首次适应算法何次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有因能用列低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)

邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点>综合来看，四种算法中，首次适应算法的效果反而更好

1.4 非连续分配管理方式

1.4.1 基本分页存储管理

思考:连续分配方式的缺点

考虑支持多道程序的两种连续分配方式:

固定分区分配:缺乏灵活性，会产生大量的内部碎片，内存的利用率很低。
动态分区分配:会产生很多外部碎片，虽然可以用“紧凑”技术来处理，但是“紧凑”的时间代价很高

如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”

基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

1) 分页存储管理的基本概念

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

a. 页面和页面大小

进程中的块称为页（Page)，内存中的块称为页框（Page Frame，或页帧)。外存也以同样的单位进行划分，直接称为块（Block)。进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

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

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

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

b. 如何进行地址转换

要算出逻辑地址对应的页号
要知道该页号对应页面在内存中的起始地址
要算出逻辑地址在页面内的“偏移量”
物理地址=页面始址＋页内偏移量

c. 逻辑地址结构

分页存储管理的逻辑地址结构如下所示:

地址结构包含两个部分:前一部分为页号，后一部分为页内偏移量w。在上图所示的例子中，地址长度为32位，其中0-11位为“页内偏移量”，或称“页内地址”;12~31 位为“页号”。

如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是2个内存单元

如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有 2M个页面

d. 页表 为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。

2) 基本地址变换机构

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

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

注意:页面大小是2的整数幂

设页面大小为L，逻辑地址A到物理地址E的变换过程如下:

①计算页号P(P=AIL）和页内偏移量w(W= A%L)。 ②比较页号P和页表长度M,若P≥M，则产生越界中断，否则继续执行。 ③页表中页号Р对应的页表项地址=页表始址F+页号Px页表项长度，取出该页表项内容b，即为物理块号。要注意区分页表长度和页表项长度。页表长度的值是指一共有多少页，页表项长度是指页地址占多大的存储空间。 ④计算E=bXL＋W，用得到的物理地址E去访问内存。

3) 具有快表的地址变换机构

a. 局部性原理

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

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

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

**b. 什么是快表（TLB) **

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

引入快表后,地址的变换过程

①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意:在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。

4) 两级页表

单级页表存在的问题

所有的页表项都连续存放，页面过大需要很大的连续空间
进程在一段时间内只需要访问某几个页面就可以正常运行了。没有必要让整个页表都常驻内存。

两级页表的原理、地址结构

如何实现地址变换

①按照地址结构将逻辑地址拆分成三部分

②从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置

③根据二级页号查表，找到最终想访问的内存块号

④结合页内偏移量得到物理地址

需要注意的几个细节

多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级
多级页表的访存次数（假设没有快表机构)——N级页表访问一个逻辑地址需要N+1次访存

1.4.2 基本分段存储管理方式

1) 分段

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

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

分段系统的逻辑地址结构由段号(段名）和段内地址（段内偏移量）所组成。如:

段号的位数决定了每个进程最多可以分几个段段内地址位数决定了每个段的最大长度是多少

2) 段表

问题:程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”。

3) 地址变换

4) 分页、分段的对比

分页对用户不可见，分段对用户可见

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

分段更容易实现信息的共享和保护(纯代码/可重入代码可以共享)

分页(单级页表)、分段访问一个逻辑地址都需要两次访存，分段存储中也可以引入快表机构

1.4.3 段页式管理方式

1) 分段、分页的优缺点

2) 分段+分页=段页式管理

3) 逻辑地址结构

每个段对应一个段表项。各段表项长度相同，由段号（隐含)、页表长度、页表存放地址组成

每个页对应一个页表项。各页表项长度相同，由页号（隐含)、页面存放的内存块号组成

4) 访问逻辑地址所需访存次数

第一次——查段表、第二次——查页表、第三次——访问目标单元

可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存

2 虚拟内存管理

2.1 虚拟内存的基本概念

2.1.1 传统存储管理方式的特征、缺点

一次性

作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：
- 作业很大时，不能全部装入内存，导致大作业无法运行;
- 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

驻留性

一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

2.1.2 局部性原理

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。

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

高速缓冲技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。

2.1.3 虚拟内存的定义和特征

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充。

虚拟内存有三个主要特征：

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

2.1.4 虚拟内存技术的实现

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存(请求调页功能)

内存空间不够时，将内存中暂时用不到的信息换出到外存(页面置换功能)

虚拟内存的实现有以下三种方式

请求分页存储管理
请求分段存储管理
请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持。一般需要硬件的支持，有以下几个方面

定容量的内存和外存
页表机制（或段表机制），作为主要的数据结构。
中断机构，当用户程序要访问的部分尚未调入内存，则产生中断。
地址变换机构，逻辑地址到物理地址的变换。

2.2 请求分页管理方式

2.2.1 页表机制

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存:如果还没调入，那么也需要知道该页面在外存中存放的位置。

当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面;有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

2.2.2 缺页中断机制

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

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

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

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

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断一条指令在执行期间，可能产生多次缺页中断。(如: copy AtoB，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

2.2.3 地址变换机构

请求分页存储管理与基本分页存储管理的主要区别:

找页表项是否在内存中
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
页面调入内存后，需要修改相应页的表项

2.3 页面置换算法

2.3.1 最佳置换算法（OPT)

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

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

2.3.2 先进先出置换算法(FIFO)

每次选择淘汰的页面是最早进入内存的页面

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

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

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

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

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

2.3.4 时钟置换算法（CLOCK)

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

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

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

2.3.5 改进型的时钟置换算法

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

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

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

算法规则:将所有可能被置换的页面排成一个循环队列第一轮:从当前位置开始扫描到第一个(0，0）的帧用于替换。本轮扫描不修改任何标志位

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

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

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

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

2.4 页面分配策略

1.4.1 驻留集大小

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

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

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

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

固定分配:操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

可变分配:先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

局部置换:发生缺页时只能选进程自己的物理块进行置换。

全局置换:可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

三种策略

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)

可变分配全局置换：刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

可变分配局部置换：刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度;反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

1.4.2 何时调入页面

预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。
请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/o操作，因此I/o开销较大。

1.4.3 从何处调入页面

系统拥有足够的对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
系统缺少足够的对换区空间：凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

2.5 抖动

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

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

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

2.6 工作集

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

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

操作系统会根据“窗口尺寸”来算出工作集。

例:某进程的页面访问序列如下，窗口尺寸为4，各时刻的工作集为?

工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如:窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。

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

第四章文件管理

1 文件系统基础

1.1 文件的概念

1.1.1 文件的定义

文件（File）是操作系统中的一个重要概念。文件是以计算机硬盘为载体存储在计算机上的信息集合，文件可以是文本文档、图片、程序，等等。

数据项：数据项是文件系统中最低级的数据组织形式，可分为以下两种类型：
- 基本数据项：用于描述一个对象的某种属性的一个值，如姓名、日期或证件号等，是数据中可命名的最小逻辑数据单位，即原子数据
- 组合数据项：由多个基本数据项组成
记录：记录是一组相关的数据项的集合，用于描述一个对象在某方面的属性，如一个考生报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列域
文件：文件是指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种。在有结构文件中，文件由一组相似记录组成，如报考某学校的所有考生的报考信息记录，又称记录式文件而无结构文件则被看成是一个字符流，比如一个二进制文件或字符文件，又称流式文件

1.1.2 文件的属性

文件有一定的属性，这根据系统的不同而有所不同，但是通常都包括如下属性：

名称：文件名称唯一，以容易读取的形式保存
标识符：标识文件系统内文件的唯一标签，通常为数字，它是对人不可读的一种内部名称。
类型：被支持不同类型的文件系统所使用
位置：指向设备和设备上文件的指针。
大小：文件当前大小（用字节、字或块表示），也可包含文件允许的最大值。
保护：对文件进行保护的访问控制信息
时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护、安全跟踪文件的使用。

所有文件的信息都保存在目录结构中，而目录结构也保存在外存上。文件信息当需要时再调入内存。通常，目录条目包括文件名称及其唯一标识符，而标识符定位其他属性的信息。

1.1.3 文件的基本操作

文件属于抽象数据类型。为了恰当地定义文件，就需要考虑有关文件的操作。操作系统提供系统调用，它对文件进行创建、写、读、定位和截断。

创建文件：创建文件有两个必要步骤，一是在文件系统中为文件找到空间：二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能信息
写文件：为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作，便更新写指针
读文件：为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，所以当前操作位置可作为每个进程当前文件位置指针。由于读和写操作都使用同一指针，节省了空间也降低了系统复杂度。
文件重定位（文件寻址）：按某条件搜索目录，将当前文件位置设为给定值，并且不会读写文件
删除文件：先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间
截断文件：允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间

这6个基本操作可以组合执行其他文件操作。例如，一个文件的复制，可以创建新文件、从旧文件读出并写入到新文件

1.1.4 文件的打开与关闭

将目录项中的信息复制到内存中的打开文件表中，并将==打开文件表的索引号返回给用户==

打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作

每个进程有自己的打开文件表，系统中也有一张总的打开文件表

进程打开文件表中特有的属性：读写指针、访问权限（只读?读写?）

系统打开文件表中特有的属性：打开计数器（有多少个进程打开了该文件）

open请求

首次使用文件，会调用open请求指明文件的属性（包括其物理位置）从外存复制到内存打开文件表的一个表目中，并将该表目的编号（索引）返回给用户；
操作open会根据文件名==搜索目录==，并将目录条目复制到打开文件
调用open请求（创建、只读、读写、添加等）得到允许，进程就可以打开文件，open会返回一个指向打开文件表中的一个==条目的指针==
通过使用该指针进行I/O操作，简化步骤并节省资源

文件关联信息

文件指针：系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对于打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存

文件打开计数：文件关闭时，必须重用其打开文件表条目，否则表内空间会不够用，计数器为0关闭文件，删除该条目

文件磁盘位置：该信息存储在内存放，以免每个操作都要从磁盘中读取

访问权限：每个进程打开文件都需要一个访问模式（创建、只读、读写、添加等）。该信息保存在进程打开的文件表中，以便操作系统能够允许或拒绝之后的I/O请求

1.2 文件的逻辑结构

按逻辑结构，文件有无结构文件和有结构文件两种类型

1.2.1 无结构文件（流式文件）

无结构文件是最简单的文件组织形式。无结构文件将数据按顺序组织成记录并积累、保存，它是有序相关信息项的集合，以字节(Byte）为单位。由于无结构文件没有结构，因而对记录的访问只能通过穷举搜索的方式，故这种文件形式对大多数应用不适用。但字符流的无结构文件管理简单，用户可以方便地对其进行操作。所以，那些对基本信息单位操作不多的文件较适于采用字符流的无结构方式，如源程序文件、目标代码文件等。

1.2.2 有结构文件（记录式文件）

有结构文件（记录式文件）：由一组相似的记录组成，一般来说，每条记录有一个数据项可作为关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

可变长记录的顺序文件无法实现随机存取，定长记录可以

定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录)

1) 顺序文件

文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索文件。顺序文件有以下两种结构：

第一种是串结构，记录之间的顺序与关键字无关。通常的办法是由时间决定，即按存入时间的先后排列，最先存入的记录作为第1条记录，其次存入的为第2条记录，以此类推。

第二种是顺序结构,指文件中的所有记录按关键字顺序排列

2) 索引文件

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

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

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

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

3) 索引顺序文件

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

4) 直接文件或散列文件

给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。

1.3 目录结构

1.3.1 文件控制块

FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息(是否可读/可写、禁止访问的用户名单等），使用信息(如文件的建立时间、修改时间等)。

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

需要对目录进行哪些操作?

搜索:当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项创建文件:创建一个新文件时，需要在其所属的目录中增加一个目录项

删除文件:当删除一个文件时，需要在目录中删除相应的目录项

显示目录:用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性

修改目录:某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名)

1.3.2 文件目录

1) 单级目录结构

单级目录实现了“按名存取”，但是不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适用于多用户操作系统。

2) 两级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录(MFD，Master File Directory〉和用户文件目录(UFD，User Flie Directory) 。

3) 多级目录结构

用户(或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“”隔开。从根目录出发的路径称为绝对路径。

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”

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

4) 无环图目录结构

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享同一目录下的所有内容）。需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。

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

1.3.3 索引节点

其实在查找各级目录的过程中只需要用到“文件名”这个信息,只有文件名匹配时,才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。

除了文件名外的文件描述信息都放到索引节点里来

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

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

1.4 文件的物理结构

1.4.1 文件分配方式-连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。优点:支持顺序访问和直接访问（即随机访问)﹔连续分配的文件在顺序访问时速度最快缺点:不方便文件拓展;存储空间利用率低，会产生磁盘碎片

每个文件在磁盘上占有一组连续的块，磁盘地址定义了磁盘上的一个线性排序。访存1次

优点：实现简单，存取速度快，使得访问磁盘需要的寻道数和寻道时间最小

缺点：文件长度不宜动态的增加，会产生外部碎片

1.4.2 文件分配方式-链接分配

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

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

优点:很方便文件拓展，不会有碎片问题，外存利用率高。

缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

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

优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。

缺点:文件分配表的需要占用一定的存储空间。

1.4.3 文件分配方式-索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表――建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。若文件太大，索引表项太多，可以采取以下三种方法解决:

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

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

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

超级超级超级重要考点:

①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key:各级索引表最大不能超过一个块)﹔

②要能自己分析访问某个数据块所需要的读磁盘次数(Key: FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件――顶级索引块是否已调入内存)

1.5 文件共享

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件

注意：

多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

1.5.1 基于索引结点的共享方式（硬链接)

各个用户的目录项指向同一个索引节点

索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。

若count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。

若count > 0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。

当count = 0时系统负责删除文件。

1.5.2 基于符号链的共享方式(软链接)

在一个Link 型的文件中记录共享文件的存放路径(Windows 快捷方式)

操作系统根据路径一层层查找目录，最终找到共享文件

即使软链接指向的共享文件已被删除，Link 型文件依然存在，只是通过Link 型文件中的路径去查找共享文件会失败(找不到对应目录项)

由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O,因此用软链接访问共享文件的速度要比硬链接更慢

1.6 文件保护

为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此，必须在文件系统中建立相应的文件保护机制。文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

1.6.1 口令保护

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

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

优点
- 保存口令的空间开销不多，验证口令的时间开销也很小。
缺点
- 正确的“口令”存放在系统内部，不够安全。

1.6.2 加密保护

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

优点
- 保密性强，不需要在系统中存储“密码”
缺点
- 编码/译码，或者说加密/解密要花费一定时间。

1.6.3 访问控制

在每个文件的FCB（或索引结点）中增加一个访问控制列表，该表中记录了各个用户可以对该文件执行哪些操作。

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

2 文件系统实现

2.1 文件系统层次结构

2.2 目录实现

在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有线性列表和哈希表两种，要注意目录的实现就是为了查找，因此线性列表实现对应线性查找，哈希表的实现对应散列查找。

2.2.1 线性列表

最简单的目录实现方法是使用存储文件名和数据块指针的线性表。创建新文件时，必须首先搜索目录表以确定没有同名的文件存在，然后在目录表后增加一个目录项。删除文件则根据给定的文件名搜索目录表，接着释放分配给它的空间。重用目录项有许多方法:可以将目录项标记为不再使用，或将它加到空闲目录项表上，还可以将目录表中的最后一个目录项复制到空闲位置，并降低目录表长度。采用链表结构可以减少删除文件的时间，其优点在于实现简单，不过由于线性表的特殊性，比较费时。

2.2.2 哈希表

哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突。最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。目录查询是通过在磁盘上反复搜索完成的，需要不断地进行IO操作，开销较大。所以如前所述，为了减少IO操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，因此降低了磁盘操作次数，提高了系统速度。

2.3 文件实现

2.3.1 文件分配形式

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。

连续分配。连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序。这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。
链接分配。链接分配采取离散分配的方式，消除了外部碎片，因此显著提高了磁盘空间的利用率;又因为根据文件的当前需求为其分配必需的盘块，当文件动态增长时，可以动态地再为它分配盘块，因此无须事先知道文件的大小。此外，对文件的增、删、改也非常方便。链接分配又可以分为隐式链接和显式链接两种形式。
索引分配。链接分配解决了连续分配的外部碎片和文件大小管理的问题。但是，链接分配不能有效支持直接访问（FAT除外)。索引分配解决了这个问题，它把每个文件的所有的盘块号都集中放在一起构成索引块（表)

2.3.2 文件存储空间管理

文件存储器空间的划分与初始化。一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成，如图4.13所示。
文件存储器空间管理。文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织、分配与回收等问题。
1. 空闲表:把所有空闲块组织成表
2. 空闲链表法:把所有空闲块组织成链表位示图:利用二进制的每位记录空闲块
3. 成组链接:空闲表和空闲链表的结合，适合大的文件系统

3 磁盘组织与管理

3.1 磁盘的结构

3.1.1 磁盘、磁道、扇区的概念

==磁盘==的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据

磁盘表面上的数据存储在一组同心圆中，称为==磁道==

一个磁道又被划分成一个个==扇区==，每个扇区就是一个“磁盘块”。各个扇区存放的==数据量相同==（如1KB）

最内侧磁道上的扇区面积最小，因此数据密度最大

3.1.2 如何在磁盘中读/写数据

需要把“磁头”移动到想要读/写的扇区所在的磁道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作

3.1.3 盘面、柱面的概念

3.1.4 磁盘的物理地址

可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。

3.1.5 磁盘的分类

磁头是否可移动

固定头磁盘∶磁头相对于盘片的径向方向固定
活动头磁盘：每个磁道一个磁头，磁头可以移动

盘片是否可更换

固定盘磁盘∶磁头臂可以来回伸缩定位磁道，磁盘永久固定在磁盘驱动器内
可换盘磁盘∶可以移动和替换

3.2 磁盘调度算法

3.2.1 一次磁盘读/写操作需要的时间

寻找时间（寻道时间)Ts:在读/写数据前，将磁头移动到指定磁道所花的时间。 ①启动磁头臂是需要时间的。假设耗时为s: ②移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。

则:寻道时间Ts=s+m*n

延迟时间TR:通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/秒，或转/分），

则平均所需的延迟时间TR=(1/2)*(1/r)=1/2r

传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则: 传输时间Tt= (1/r)*(b/N)= b/(rN)

3.2.2 先来先服务算法(FCFS )

FCFS 算法根据进程请求访问磁盘的先后顺序进行调度

3.2.3 最短寻找时间优先算法(SSTF）

SSTF 算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以便使每次的寻找间最短。当然，总是选择最小寻找时间并不能保证平均寻找时间最小，但能提供比 FCFS算法更好的性能。这种算法会产生“饥饿”现象。

3.2.4 扫描算法(SCAN)

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

3.2.5 LOOK调度算法

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

3.2.6 循环扫描算法(C-SCAN)

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

3.2.7 C-LOOK调度算法

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

3.3 磁盘的管理

3.3.1 磁盘初始化

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

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

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

3.3.2 引导块

计算机启动时运行自举程序，初始化CPU寄存器、设备控制器和内存等，然后启动操作系统

组局程序通常保存在ROM中，在ROM中保留很小的自举块，完整的自举程序保存在启动块上拥有启动分区的磁盘称为启动磁盘或系统磁盘

3.3.3 坏块的管理

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它

简单磁盘：手动处理，对坏块进行标记，程序不会使用

复杂磁盘：控制器维护一个磁盘坏块链表，同时将一些块作为备用，用于替代坏块（扇区备用）

第五章输入输出管理

1 输入输出管理（I/O）

1.1 IO设备的基本概念和分类

“I/O”就是“输入/输出”（Input/Output）I/O设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的==硬件部件==。

1.1.1 按使用特性分类

人机交互的外部设备：用于与计算机用户之间交互设备（打印机，鼠标，键盘）

交换速度相对较==慢==，以==字节==为单位进行数据交换

存储设备：用于存储程序和数据的设备（磁盘、磁带、光盘）

交换速度较==快==，以多字节组成的==块==为基本单位交换

网络通信设备：用于远程设备通信的设备（网络接口、调制解调器）

速度介于前两类==之间==

1.1.2 传输速率分类

低速设备：每秒进位==几个字节==到数百字节（鼠标、键盘）

中速设备∶传输速率为每秒==数千字节至数万字节==（行式打印机、激光打印机）

高速设备：传输速率在数==百兆字节至千兆字节==的一类设备（磁带机、磁盘机、光盘机）

1.1.3 信息交换单位分类

块设备：信息存取总是以==数据块==为基本单位，存储信息的设备称为块设备==传输速率高==，可寻址，可以==任意读写==某块

字符设备：用于数据输入输出的设备为字符设备，传输的基本单位是字符（交互式终端机，打印机）”传输==速率低==，不可寻址，输入输出时常采用==中断驱动方式==

1.2 I/O控制器

I/O设备由机械部件和电子部件组成

1.2.1 I/O设备的机械部件

I/O设备的机械部件主要用来执行具I/O操作。如我们看得见摸得着的鼠标/键盘的按钮;显示器的LED屏;移动硬盘的磁臂、磁盘盘面。

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

1.2.2 I/设备的电子部件（I/O控制器)

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

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

1.2.3 I/O 控制器的功能

接受和识别CPU发出的命令
- 如CPU发来的read/write命令，1/o控制器中会有相应的控制寄存器来存放命令和参数
向CPU报告设备的状态
- I/O设备的机械部件控制器中会有相应的状态寄存器,向CPU报告设备的状态用于记录I/O设备的机械部件设备的当前状态。如:1表示空闲，0表示忙碌
数据交换
- I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPu发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。
地址识别
- 类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPu提供的“地址”来判断CPU要读/写的是哪个寄存器

1.2.4 1/O控制器的组成

值得注意的小细节:

①一个I/O控制器可能会对应多个设备; ②数据寄存器、控制寄存器、状态寄存器可能有多个(如:每个控制/状态寄存器对应一个具体的设备〉，且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O;另一些计算机则采用I/O专用地址，即寄存器独立编址。

1.2.5 内存映像I/O v.s.寄存器独立编址

1.3 IO控制方式

1.3.1 程序直接控制方式

计算机从外部设备读取数据到存储器，每次读一个字的数据，对读入的每个字，CPU都要对外没状态进行==循环检查==，知道确定该字已经在I设备控制器的数据寄存器中。

读写单位：==字==

优点：容易实现，操作简单

缺陷∶CPU高速性和I/O设备的低速性的矛盾（降低了CPU的利用率），CPU和I/O设备只能串行工作

1.3.2 中断驱动方式

允许I/O设备主动打断CPU的运行并请求服务，进而==解放CPU==，使其向I/O控制器发送读命令后可以继续做其他有用的工作

读写单位∶==字==

优点∶比程序直接控制方式有效

缺点：数据的传输必须要经过CPU，仍然后消耗CPU的时间

1.3.3 DMA方式

在I/O设备和内存之间开辟直接的数据交换通路，==彻底解放CPU==

读写单位：==数据块==

设备==直接送入内存==

只有当一个或多个数据块开始和结束的时候，CPU才会进行干预

命令/状态寄存器（CR）：用于接收CPU发送的IO命令和有关控制信息或者设备状态

内存地址寄存器（MAR）：数据直接在设备与内存之间交互

数据寄存器（DR）：用于暂存从设备到内存或者从内存到设备的数据

数据计数器（DC）：存放本次要传送的字（节）数

1.3.4 通道控制方式

设置一个专门负责输入/输出的处理机（DMA方式的发展），实现对一组数块的读写以及相关控制和管理为单位干预

读写单位：==一组块==

优点：有效的提高了系统资源利用率

缺点：实现较为复杂

1.3.5 DMA与通道的区别

DMA需要==CPU来控制==传输的数据块大小、传输的内存位置、而通道方式中这些信息是由==通道控制==的

DMA控制器对应一台设备与内存传递数据，通道可以控制多态设备与内存的数据交换

1.4 I/O软件层次结构

1.4.1 用户层I/O软件

==实现与用户交互的接口==，用户可以直接调用在用户层提供的，与IO操作有关的==库函数==，对设备进行操作

1.4.2 设备独立性软件

用于实现用户程序与设备驱动器的==统一接口、设备命令、设备保护、差错控制及设备分配与释放==，同时为设备管理与数据传送提供必要的存储空间

设备独立性也称为设备==无关性==，使得应用程序独立于具体使用的物理设备（使用逻辑设备名）

使用逻辑设备名的好处：增加设备分配的灵活性；易于实现IO重定向

主要功能

执行所有设备的公有操作（设备的分配与回收，==逻辑设备名映射为物理设备名==，对设备进行保护，进制用户直接访问设备），屏蔽设备之间数据交换的速度差异等

向用户层（文件层）提供统一接口∶无论哪种设备，他们向用户提供的==接口都是相同的==

1.4.3 设备驱动程序

与硬件直接相关，负责实现系统==对设备发出的操作命令==，驱动IO设备工作的驱动程序

1.4.4 中断处理程序

用于保存被中断进程的CPU环境，转入相应的中断处理程序进行处理，处理完并恢复被中断进程的现场后，返回被中断进程

1.4.5 硬件设备

IO设备通常包括一个机械部件和一个电子部件

1.5 IO核心子系统

1.5.1 I/O子系统概述

主要提供==I/O调度==，缓冲与高速缓存，设备分配与回收，假脱机，设备保护和差错处理

1.5.2 I/O调度概念

通过I/O调度改善系统整体性能，使得进程之间==公平共享设备==访问，减少I/O完成所需要的平均等待时间

使用主存或者磁盘上的存储空间的技术，如缓冲、高速缓存、假脱机等来改善计算机效率

1.6 假脱机技术

1.6.1 目的

缓解CPU 与I/O的==速度差异矛盾==

要实现SPOOLing 技术，必须要有多道程序技术的支持

1.6.2 输入井和输出井

输入井用来收容IO设备的数据

输出井用来==模拟输出时的磁盘==

1.6.3 输入缓冲区和输出缓冲区

输入缓冲区：暂存由输入设备送来的数据

输出缓冲区：暂存从输出井送来的设备

1.6.4 输入进程和输出进程

输入进程∶模拟脱机输入时的外围控制机，将用户要求的数据从输入机==通过输入缓冲区送到输入并中==，当CPU需要数据，直接将==输出井中的数据送入内存==

输出进程：模拟脱机输出时的外围控制机，把用户要求输出的数据先从内存送到输出井中，待输出设备空闲时，再将输出井中的数据经过输出缓冲区送到输出设备

1.6.5 特点

提高了IO速度

独占设备变成了共享设备

实现了虚拟设备功能

通俗一点就是，如果设备被占用，我们就先把数据暂存一下，等到设备空闲了就把这些数据输送到设备中

1.7 设备的分配与回收

1.7.1 概述

―根据用户IO请求分配设备，原则：充分发挥设备的使用效率，避免进程死锁

1.7.2 设备类型分类

独占式使用设备设备只能互斥使用（打印机）

分时共享使用设备通过分时共享来提高设备的利用率

SPoOLing方式使用设备使用空间换时间，对IO设备进行批处理

1.7.3 设备分配的数据结构

设备控制表（DCT）

一个设备控制表表征一个设备，控制表中是设备的各项属性

控制器控制表（COCT）

COCT与DCT——对应关系，DCT需要一个表项来表示控制器，即一个指向控制器控制表的指针

通道控制表（CHCT）

CHCT提供服务的那几个设备控制器

系统设备表（SDT）

记录已经连接到系统中的所有物理设备的情况

1.7.4 设备分配的策珞

分配原则：充分发挥设备效率，避免进程死锁

分配方式

静态：系统—次性的把设备分配给相应作业，直到作业结束
优点∶没有死锁问题
缺点：降低了设备使用率
动态：进程执行过程中根据执行需要进行分配
优点：提高了设备利用率
缺点∶分配算法不当可能导致死锁

设备分配算法

先请求先分配类似于先来先服务

优先级高者优先

独占设备一般使用静态分配，共享设备一般使用动态分配

1.8 缓冲区管理

1.8.1 磁盘高速缓存

使用磁盘高速缓存技术可以提高磁盘的IO速度，对高速缓存复制的访问要比原始数据访问更高效

磁盘高速缓存，逻辑上属于磁盘，物理上属于驻留在内存中的盘块

在内存中的两种形式

在内存中开辟一个单独的存储空间作为磁盘高速缓存，大小固定

把未利用的内存空间作为一个缓冲池，供请求分页系统和磁盘IO时共享

1.8.2 缓冲区

引入缓冲区的目的

缓和CPU与IO之间的速度差异矛盾

减少对CPU的中断频率，放宽对CPU中断响应时间的限制

解决基本数据单元大小不匹配的问题

提高CPU和IO设备之间的并行性

实现方法

采用硬件缓冲器〔成本过高），除了关键位置，一般不使用硬件缓冲器

采用缓冲区（位于内存区域）

注意

管道通信中的“管道”其实就是缓冲区。要实现数据的双向传输，必须设置两个管道

1.8.3高速缓存与缓冲区对比

相同点

都介于高速设备和低速设备之间

不同

存放数据
高速缓存：存放的是低速设备上的某些数据的==复制数据==
缓冲区：存放的是低速设备==传递==给高速设备的数据，这些数据在低速设备上==不一定有备份==，这些数据再从缓冲区传送到高速设备
目的
高速缓存∶高速缓存存放的是高速设备==经常要访问==的数据，如高速缓存中数据不在，高速设备就要访问低速设备
高速设备和低速设备的通信都要经过==缓冲区==，==高速设备永远不会去直接访问低速设备==

# 第一章 计算机系统概述

# 1 操作系统的基本概念

# 1.1 操作系统的概念

# 1.2 操作系统的特征

# 1.3 操作系统的功能和目标

# 2 操作系统的发展与分类

# 2.1 手工操作阶段

# 2.2 批处理阶段

# 2.2.1 单道批处理系统

# 2.2.2 多道批处理系统

# 2.3 分时操作系统

# 2.4 实时操作系统

# 2.5 网络操作系统和分布式计算机系统

# 2.6 个人计算机操作系统

# 3 操作系统的运行环境

# 3.1 操作系统的运行机制

# 3.2 中断和异常的概念

# 3.2.1 中断机制的诞生

# 3.2.2 中断的概念和作用

# 3.2.3 用户态、核心态之间如何切换？

# 4.2.4 中断的分类

# 4.2.5 外中断的处理过程

# 3.3 系统调用

# 3.3.1 系统调用的概念和功能

# 3.3.2 系统调用按功能分类

# 3.3.3 系统调用和库函数的区别

# 3.3.4 系统调用背后的过程

# 4 操作系统的体系结构

# 4.1 大内核和微内核

# 第二章 进程管理

# 1 进程与线程

# 1.1 进程的概念和特征

# 1.1.1 进程的定义

# 1.1.2 进程的组成

# 1.1.3 进程的特征

# 1.2 进程的状态与转换

# 1.2.1 三种基本状态

# 1.2.2 进程的另外两种状态

# 1.2.3 进程状态的转换

# 1.3 进程控制

# 1.3.1 什么是进程控制

# 1.3.2 如何实现进程控制

# 1.3.3 进程控制相关的原语

# 1.4 进程的组织

# 1.5 进程的通信

# 1.5.1 什么是进程通信

# 1) 共享存储

# 2) 管道通信

# 3) 消息传递

# 1.6 线程概念和多线程模型

# 1.6.1 什么是线程

# 1.6.2 引入线程后的变化

# 1.6.3 线程的属性

# 1.6.4 线程的实现

# 1) 用户级线程

# 2) 内核级线程

# 2 处理机调度

# 2.1 调度的概念

# 2.1.1 调度的基本概念

# 2.1.2 调度的三个层次

# 1) 高级调度（作业调度）

# 2) 中级调度(内存调度)

# 3) 低级调度（进程调度)

# 2.2 调度的时机、切换与过程

# 2.2.1 进程调度的时机

# 2.2.2 进程的切换与过程

# 2.3 进程调度方式

# 2.4 调度的基本准则

# 2.4.1 CPU利用率

# 2.4.2 系统吞吐量

# 2.4.3 周转时间

# 2.4.4 等待时间

# 2.4.5 响应时间

# 2.5 典型的调度算法

# 2.5.1 先来先服务(FCFS)

# 2.5.2 短作业优先(SJF)

# 2.5.3 高响应比优先(HRRN)

# 2.5.4 时间片轮转（RR)

# 2.5.5 优先级调度算法

# 2.5.6 多级反馈队列调度算法

第一章计算机系统概述

1 操作系统的基本概念

1.1 操作系统的概念

1.2 操作系统的特征

1.3 操作系统的功能和目标

2 操作系统的发展与分类

2.1 手工操作阶段

2.2 批处理阶段

2.2.1 单道批处理系统

2.2.2 多道批处理系统

2.3 分时操作系统

2.4 实时操作系统

2.5 网络操作系统和分布式计算机系统

2.6 个人计算机操作系统

3 操作系统的运行环境

3.1 操作系统的运行机制

3.2 中断和异常的概念

3.2.1 中断机制的诞生

3.2.2 中断的概念和作用

3.2.3 用户态、核心态之间如何切换？

4.2.4 中断的分类

4.2.5 外中断的处理过程

3.3 系统调用

3.3.1 系统调用的概念和功能

3.3.2 系统调用按功能分类

3.3.3 系统调用和库函数的区别

3.3.4 系统调用背后的过程

4 操作系统的体系结构

4.1 大内核和微内核

第二章进程管理

1 进程与线程

1.1 进程的概念和特征

1.1.1 进程的定义

1.1.2 进程的组成

1.1.3 进程的特征

1.2 进程的状态与转换

1.2.1 三种基本状态

1.2.2 进程的另外两种状态

1.2.3 进程状态的转换

1.3 进程控制

1.3.1 什么是进程控制

1.3.2 如何实现进程控制

1.3.3 进程控制相关的原语

1.4 进程的组织

1.5 进程的通信

1.5.1 什么是进程通信

1) 共享存储

2) 管道通信

3) 消息传递

1.6 线程概念和多线程模型

1.6.1 什么是线程

1.6.2 引入线程后的变化

1.6.3 线程的属性

1.6.4 线程的实现

1) 用户级线程

2) 内核级线程

2 处理机调度

2.1 调度的概念

2.1.1 调度的基本概念

2.1.2 调度的三个层次

1) 高级调度（作业调度）

2) 中级调度(内存调度)

3) 低级调度（进程调度)

2.2 调度的时机、切换与过程

2.2.1 进程调度的时机

2.2.2 进程的切换与过程

2.3 进程调度方式

2.4 调度的基本准则

2.4.1 CPU利用率

2.4.2 系统吞吐量

2.4.3 周转时间

2.4.4 等待时间

2.4.5 响应时间

2.5 典型的调度算法

2.5.1 先来先服务(FCFS)

2.5.2 短作业优先(SJF)

2.5.3 高响应比优先(HRRN)

2.5.4 时间片轮转（RR)

2.5.5 优先级调度算法

2.5.6 多级反馈队列调度算法