武汉大学 操作系统期末考试复习笔记

Chapter1:导论

计算机系统可以大致分为4个部分：硬件，操作系统，系统程序与应用程序，用

户

操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次扩充，它位于硬

件与其他软件之间，是所有其他软件运行的基础。

对操作系统的公认的定义：操作系统是一直在计算机上运行的程序（通常称为内

核）

操作系统是计算机系统中的一个系统软件，它管理和控制计算机系统中的

硬件和软件资源。

裸机：没有配置软件的计算机，即计算机硬件

虚拟机：覆盖了软件的机器

最基本的操作系统类型有三种：批处理操作系统，分时操作系统，实时操作系

统

批处理系统：单道批处理系统，多道批处理系统

在单处理机系统中，多道程序运行的特点是多造、宏观上并行和微观上

串行。

分时系统：时间片轮转，设置多路卡，（用户能在很短时间内获得响应）人机交

互，共享主机，方便用户上机

实时系统：系统能及时响应外部事件的请求，在规定的时间范围内完成对该事件

的处理，并控制实时任务协调一致地运行。（响应时间由控制对象决定，可靠性

高）

在主机控制下进行的输入/输出操作称为_联用镰人献C操作。（联机批处理，脱

机批处理，联机UO,脱机I/O）

作业是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作集合，

包括用户程序、所需的数据及命令等

操作系统的4个基本特征：并发，共享，虚拟，不确定（并发和共享互为存在

条件）

计算机系统的两种运行状态:核心态（kernelmode）,0,用户态（usermode）,1

Chapter2：操作系统结构

用户接口：命令行接口(联机命令接口，脱机命令接口)、批处理接口以及图形

用户接口(GUI)

系统调用(systemcalls):系统调用在运行程序和操作系统之间提供接口

运行程序和操作系统之间的参数传递有3种常用方法：寄存器中的参数传递，参

数存在内存的一张表中表地址作为寄存器的参数传递，程序把参数压入栈由操作

系统弹出

系统调用的类型：大致可分为5类：进程控制，文件管理，设备管理，信息维护，

通信

系统调用与过程调用的区别：系统调用在核心态下运行,子程序在用户态下运行;

系统调用通过中断机构进入以实现运行状态的改变，子程序直接调用不涉及运行

状态改变

系统结构：

MS-DOS：以最小的空间提供最多的功能。不划分模块，其接口和功能层次没有

划分清楚

早起的UNIX：受硬件功能限制，由两个独立的部分组成，系统程序和内核

内核包括了在物理硬件之上，系统调用之下的一切。内核通过系统调用提供文件

系统、CPU调度、存储管理和其他操作系统功能

操作系统分层：0层为硬件层，N层(最高层)为用户接口，每层都利用较低层

的功能和服务，为较高层隐藏一定的数据结构、操作和硬件的存在

层次结构：给模块赋予了层次顺序使调用关系变得有序，在上下两层不变的基础

上可以换掉某层便于移植和扩充，但牺牲一定的灵活性为代价

微内核：微内核通常包括最小的进程和内存管理以及通信功能

微内核特点：降低了开发难度，具有较好的扩展性及可移植性，特别适合大规模

开放式的分布系统。但是效率较低

模块结构，将操作系统内核按照功能划分为一个个独立的模块，模块之间相对独

立，只能通过事先规定好的接口方式来调用。每个模块实现一个完整独立的功能,

所有模块之间相互调用，共同构成一个完整的系统内核。

模块结构特点：效率高，但全局函数使用多造成访问控制困难，结构不清晰可理

解性可维护性可移植性差

宏内核：在运行过程中，它是一个独立的进程。模块结构、层次结构的系统内核

基本都是宏内核

微内核：大部分内核模块都作为独立的进程，它们之间通过信息通信使模块之间

互相提供服务。

Chapter3进程

进程的顺序执行:程序通常由若干个程序段所组成，它们必须按照某种先后次序

来执行，仅当前一个操作执行完后才能执行后继操作

顺序执行的特征：顺序性，封闭性(一旦开始运行结果不受外界影响)，可再现

性(执行情况相同重复执行获得相同结果)

程序的并发执行:若干程序或程序段同时在系统中运行

并发执行的特性：间断性，失去封闭性(进程共享资源)，不可再现性

Bernstein条件:能保证两个程序段并发执行而不会产生与时间有关的错误(全局

变量的改变什么的)

R(Si)nw(Sj)={}这两条保证

R(Sj)nw(Si)={}两次读之间数据不变

w(Si)nw(Sj)={}本条保证写操作结果不丢

考虑下面是条语句：

SI：a=x+yS2：b=z+l

S3：c=a-bS4：d=c+l

R(Sl)={x,y}R(S2)={z}R(S3)={a,b}

W(Sl)={a}W(S2)={b}W(S3)={c}

因R(Sl)nW(S2)UR(S2)nW(Sl)UW(Sl)nW(S2)={},故SI和S2可以并发

执行。

因R(S2)nW(S3)UR(S3)nW(S2)UW(S3)nW(S2)={b},故S2和S3不能并发

执行。

并发语句描述：cobegin.….coend

进程：进程是执行中的程序。一个进程包括，代码段，程序计时器和处理机寄存

器内容，栈，数据部分

进程的特征：动态性(进程是动态存在和消失的而程序是静态实体)，并发性(多

个进程实体同时在内存并能在一段时间内同时发生)，独立性(进程是独立运行

的基本单位)，异步性(进程各自以独立的不可预知的速度向前推进)，结构性(由

很多段组成(程序段，数据段，控制块))

进程状态：新建，运行，等待，就绪，终止

通常一个进程至少应有以下三种基本状态：就绪状态，执行状态(运行)，阻塞

状态(等待状态通常是I/O请求)

进程由PCB,程序段，数据段三部分组成

进程控制块(PCB,process-control-block)：每个进程在操作系统内用进程控制块

表示。PCB是描述和管理进程的数据结构。它是进程实体的一部分，操作系统

通过PCB感知进程的存在，PCB是进程存在的唯一•标志。

进程的挂起状态：(由于系统故障，检查，资源内存不足等原因)人为将进程挂

起使之处于静止状态。

/*进程调度*/

作业队列：系统中所有进程的集合

就绪队列：内存中就绪并等待执行的所有进程的集合（常用链表实现）

设备队列：等待某DO设备的进程队列

长程调度（作业调度）：选择可以进入就绪队列的进程

短程调度（CPU调度）：选择下一个执行并分配CPU

长程调度（作业调度）的频率相对低，长程调度控制了多道

进程可以分为：DO型进程，和CPU型进程

上下文切换：将CPU切换到另一个进程需要保存当前进程的状态并恢复另一个

进程的状态，这个任务称为上下文切换

原语：原语是由若干条机器指令构成的，用以完成特定功能的一段程序，实现对

进程的管理和控制。这段程序在执行期间不可分割（原语不允许被中断。不同层

次之间的对话的语言称为原语）

种类：创建原语，撤销原语，阻塞原语，唤醒原语，挂起原语，激活原语…

进程创建：通过创建进程系统调用可以创建多个新进程，创建进程称为父进程，

被创建进程称为子进程。每个新进程可以再创建新进程，从而形成了进程树。进

程树乂称为进程图或进程家族树

有的系统中，若父进程终止不允许子进程继续，这种现象称为：级联终止

进程的组织：线性方式，链接方式（链表方式），索引方式

进程通信：进程之间的信息交换

低级进程通信方式：进程互斥与同步交换的信息量较少且效率较低。P、V操作

是一种低级进程通信原语

高级进程通信方式：进程之间以较高的效率传送大量数据

高级进程通信方式分为三大类：共享存储器系统，消息传递系统，管道通信系统

或共享文件系统

共享存储器系统：相互通信的进程共享某些数据结构或共享存储区

消息传递系统：进程间的数据交换以消息为单位，程序员直接利用系统提供的一

组通信命令（原语）来实现通信。

消息传递系统因其实现方式不同可分为：直接通信方式（讲消息直接发在接受进

程的消息队列上），间接通信方式（将消息发送到信箱）

管道（共享文件）通信：通过连接读进程和写进程的共享文件来实现读写进程之

间通信

缓冲（Buffering）：通信进程交换的信息都驻留在临时队列中，队列实现有三种形

式，零容量（发送者必须等待接受者），有限容量（线路满则发送者必须等待），

无限容量（发送者无需等待）

管道：使用管道通信时，基本上采用文件系统的原有机制实现。包括创建、打开、

关闭、读写等。

管道机制应提供以下三方面的协调能力：互斥（互斥读写管道），同步（管道空

满情况处理），存在（确定对方是否存在）

在单处理机计算机系统中，如果有N个进程（只考虑等待，就绪，运行）

那么

运行状态最多1个，最少0个；

等待状态最多N个，最少。个；

就绪状态最多N-1个，最少0个。

Chapter4线程

在操作系统中引入进程的目的是：使用多道程序能并发执行，以改善资源利用率

及提高系统吞吐量

在操作系统中引入线程的目的是：减少程序并发执行的时空开销，使操作系统有

更好的并发性

线程是CPU使用的一个基本单元，包括线程标识（threadID）,程序计数器（PC）,

寄存器集（registerset）,栈（stack）

线程自己基本上不拥有资源，只拥有一点在运行时必不可少的资源（如程序计数

器、寄存器集和栈）。但它可以与同属一个进程的其他线程共享进程拥有的全部

资源

线程与属于同一进程的线程共享：代码段，数据段，其他操作系统资源

线程的状态，同步与通信与进程类似

进程的挂起及终止将影响到其中所有进程

线程的优点：响应能力强（即使进程的一块被阻塞了，其他部分也能运行），资

源共享，经济性，多处理器体系结构的利用，创建撤销切换时间短，共享内存和

资源线程间通信方便

多线程模型

操作系统中有多种方式实现对进程的支持：内核线程（kernelThreads）,用户线

程（UserThreads）的组合实现

内核线程：也称内核级线程，是指依赖于内核，由操作系统内核完成创建和撤销

工作的线程。

一个内核线程的阻塞不会影响其他线程的运行。

处理机分配的对象是线程，所以有多个线程的进程将获得更多的处理机时间

用户线程：也称用户级线程，是指不依赖于操作系统核心，由应用进程利用线程

库提供创建、同步、调度和管理线程的函数来控制的线程

用户线程的维护由应用进程完成，可以用于不支持线程的操作系统

当一个线程阻塞时，整个进程都必须等待。

处理机时间是分配给进程的，进程内有多个线程时，每个线程的执行时间相对少

一占八、、

用户线程与内核线程的关系

多对一模型：将多个用户线程映射到一个内核线程。线程管理由线程库在用户空

间进行。用于不支持内核线程的系统中（只有一个内核线程，相当于没有）

一对一模型：将每个用户线程映射到一个内核线程。这种模型的绝大多数实现限

制了系统支持的线程数量

多对多模型：多个用户线程到同样数量或更少的内核线程上

多线程问题：

线程取消可以再i下两种情况下发生：异步取消（一个线程立即终止目标进程），

延迟取消（目标线程不断检查它是否应该终止）

线程与进程的比较：从调度的基本单位，拥有资源的基本单位，并发性，和系统

开销四个方面说。

ChaptersCPU调度

处理机的三级调度：作业调度，进程调度，交换调度

作业调度：又称长程调度，宏观调度和高级调度，从外存上处于后备状态的作业

中选择一个或多个作业，给他们分配内存、I/O设备等必要资源，并建立相应的

进程，使该作业具有获得竞争处理机的权利

作业调度的运行频率低，通常儿分钟一次

进程调度：又称短程调度，微观调度和低级调度，从就绪队列中选取一个进程，

将处理机分配给它。

进程调度的运行频率很高，一般十几毫秒就要运行一次

交换调度：又称中程调度，中级调度，将内存总暂时不用的信息移到外存，以腾

出空间给内存中的其他进程使用，或将需要的信息从外存读入内存。

交换调度的目的是，提高内存利用率和系统吞吐量

交换调度的运行频率介于上面两者之间

作业：是用户在一次解题或一个事务处理过程中要求计算机系统所做的工作的集

合，包括用户程序、所需的数据及命令等

作业从提交到完成要经历四种状态：提交状态，后备状态（将作业插入后备作业

队列中等待调度运行），运行状态（作业在内存中执行），完成状态

作业控制块（JCB,jobcontrolblock）：系统通过JCB感知作业的存在，JCB是

作业存在的唯一标志

一个作业可以分成若干顺序处理的加工步骤，每个步骤称为一个作业步

多道程序的设计目标在于任何时候都有某些进程运行，使CPU利用率最大化。

CPU调度可能发生如下4种情况

从运行状态转到等待状态

从运行状态转到就绪状态

从等待状态转到就绪状态

进程终止

1.4两种情况的调度称为非抢占调度，2,3两种情况的调度称为抢占式调度

进程调度的两种方式：抢占方式，非抢占方式

抢占方式：又称波多方式。抢占原则有，优先权，时间片

分派程序：用来将对CPU的控制交给由短程调度程序选择的进程

分派延迟：分派程序终止一个进程的运行并启动另一个进程运行所花的时间，也

成为调度时间

调度准则：

CPU利用率

吞吐量（单位时间内运行完的程序数）

周转时间（进程从提交到运行结束的全部时间

等待时间（进程在就绪队列中等待调度的时间总和）

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

带全周转时间（作业周转时间与作业实际运行时间的比）

调度算法：（画图用到gantt图）

FCFS先来先服务调度，适用于作业调度，进程调度

算法简单易于实现，不适用与短作业和I/O繁忙的作业

SJB最短作业优先（抢占/非抢占）

适合短作业，对长作业不利，运行时间为估计

抢占SJB调度有时称为最短剩余时间优先调度，若到达新进程的CPU区间短于当

前运行进程的剩余时间，则它将抢占CPU。

可能有饥饿

优先级调度（抢占/非抢占）

优先级的类型：静态优先级，动态优先级（确定原则：占用CPU时间，等待时间）

存在的问题：饥饿，低优先级的进程可能永远得不到运行

解决方法：老化，视进程等待时间的延长提高其优先级数

时间片轮转调度（RR）

每个进程得到小单位的CPU时间，称为时间片，通常为10700毫秒。时间片用

完后，该进程将被抢占并插入就绪队列末尾。

时间片大小：太大：退化为FCFS太小：调度频繁系统开销大。现代操作系统的

时间片一般为10-100ms,上下文切换时间一般少于10uSo

确定时间片大小应考虑的因素：

系统对响应时间的要求：响应时间=时间片*进程数

就绪队列中的进程数目：时间片应与就绪进程数成反比

系统的处理能力：考虑响应时间在可承受范围内，系统速度快则时间片可以增长

时间片轮转算法的特点及改进：

虚拟时间片轮转法（针对偏重I/O的进程）：

新进程基于FCFS进入就绪队列，进程用完时间片后也进入就绪队列，进程因I/O

阻塞进入I/O队列，I/O完成时进程进入附加队列，附加队列的优先级高于就绪

队列，当进程从附加队列被调度时，其运行时间不超过上次发生中断时剩余的时

间。

高响应比优先调度算法

响应比=1+作业等待时间/估计运行时间

I

A、B、C、D、E的到达时间依次为0、1、2、3、

4,要求运行时间依次为3、6、4、5、2

0：A运行，BCD依次到达；

3：rB=1+2/6,rc=1+1/4,rD=l：B先运行。

9：rc=1+7/4,rD=1+6/5,rE=1+5/2；E先运行。

11：rc=1+9/4,rD=1+8/5；C先运行。

•由此可知作业的运行顺序为A、B、E、C、D。

多级队列调度

将就绪队列分为多个独立队列，每个队列有自己的调度算法，根据进程属性，一

个进程被永久分配到一个队列

例如分为前台（交互式）RR算法，和后台（批处理）FCFSo前台的优先级高

多级反馈队列调度

进程能在不同的队列间移动。如果进程使用过多的CPU时间，那么它会被移动到

更低优先级队列。此外，在较低优先级队列中等待时间过长的进程会被移到更高

优先级队列

每个队列有不同优先级，第一队列最高，其余递减，每个队列的时间片大小也各

不相同，优先级高的队列时间片短。

当一个新进程进入系统时，首先将它放入第1个队列的末尾，按先来先服务的原

则排队等待调度。当轮到该进程执行时，如能在此时间片内完成，便可准备撤离

系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2队

列的末尾，再同样地按先来先服务原则等待调度执行。如此下去，最后一个队列

中使用时间片轮转调度算法。仅当第1个队列为空时，调度程序才调度第2队列

中的进程运行；仅当第1个至第（i-D个队列均为空时，才会调度第i个队列

中的进程运行。当处理机正在为第i个队列中的某进程服务时，若又有新进程进

入优先级较高的队列中，则此时新进程将抢占正在运行进程的处理机，即由调度

程序把正在执行进程放回第i个队列末尾，重新将处理机分配给新进程。

多级反馈队列调度算法能较好满足各类用户的需求

公平分享调度算法：基于进程组来分配CPU时间，其实现思想是对系统中的每个

用户赋予某种权值，根据用户权值大小，按比例分配处理机时间。

进程切换：在操作系统中凡是要进行中断处理和进程调度时，都将涉及到进程上

下文的保存的恢复。

中断时：系统保存和恢复的是同一个进程的上下文

进程调度时恢复的是调度程序所选中进程的上下文

既考虑作业等待时间，又考虑作业执行时间的调度算法是响应比高优先调度

Chapter6进程同步

进程同步：系统中各进程之间逻辑上的相互制约关系叫做进程同步

在多道程序系统中，进程之间存在着的不同制约关系可以划分为两类：同步和互斥

同步指进程间具有的一定逻辑关系；互斥是指进程间在使用共享资源方面的约束关系。

临界区问题：每个进程有一个访问共享数据的代码段，称为临界区（critical

section）。需保证一个进程在其临界区执行时，不允许其他进程在其临界区执行。

临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如打印机，共

享变量

同类临界区：所有与同一临界资源相关联的临界区

临界区问题的解决应满足：互斥，前进（如果没有进程在其临界区内执行，且有

进程需要进入临界区，那么只有不在剩余区执行的进程可以参加选择，以确定下

一个进入临界区的进程，且选择不能无限期延长），有限等待（在一个进程提出

进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须

是有限的）

访问临界资源应遵循的原则：空闲让进，忙则等待，有限等待，让权等待（当

进程不能进入自己的临界区时，应释放处理机）

Peterson算法

enumbooIean{faIse,true)；

booIeanfIag[2]={faIse,faIse)；intturn；

PO：{

do{

fIag[0]=true；turn=1；

while(flag[1]&&turn==1)；〃实现互斥，前进

进程PO的临界区代码CSO；

fIag[0]—faIse；

进程PO的其他代码；}

while(true)}

P1：（

do{

flag[1]=true；turn=0；

while（flag[0]&&turn==0）；

进程P1的临界区代码CS1；

fIag[1]=faIse；

进程P1的其他代码；}

while（true）}

硬件同步：用硬件方法实现互斥的主要思想是保证检查操作与修改操作不被打断

禁止中断方法：当进程执行临界区代码时，禁止中断（很多缺点）

硬件指令方法

用TS实现互斥：

booIeanTS(boolean*1ock)

(

booIeanold；

oId=*lock；

*lock=true；

returnold；

1

।

।■

whileTS(&lock)；

〃lock=1的话，陷入while；lock=0的话，将lock置1,进入临界区

临界区代码CriticalSection；

Iock=faIse；

其他代码remaindersection；

।

用swap指令实现进程互斥：

//swap(a,b)交换两值

I

I

I

key=true；

while(key!=faIse)Swap(&Iock,&key)；

//如果lock=true,不停的swap,直到lock=false,进入临界区

临界区代码CriticalSection；

lock=faIse；

其他代码remaindersection；

।

।

用锁机制实现互斥(自旋锁)

Iock(w)

(

while(w==1)；

w=1；

)

unIock(w)

(

w=0；

)

进程P1进程P2

II

II

II

Iock(w)；Iock(w)；

临界区；临界区；

unIock(w)；unIock(w)；

।।

这一'页的方法都不能实现让权等待，即存在忙等待

信号量：信号量S是个整型变量，除了初始化外，它只能通过两个标准原子操作

wait()和signaI()来访问。

wait(S)signaI(S):

{whileS0dono-op;{S++;

S—;}

Wait是原来的P操作

Signal是原来的V操作

当进程需要使用资源时则对信号量执行wait,当释放资源时执行signal

互斥信号量的实现

信号量由两个成员(s,q)组成，其中s是一个具有非负初值的整型变量，q是

一个初始状态为空的队列。又称信号灯。

除信号量的初值外，信号量的值仅能由P操作(又称为wait操作)和V操作(又

称为signal操作)改变。

wait(semaphore*s)

{s_>vaIue—;

if(s->vaIue<0)

{addthisprocesstos->list;

//如果所有资源都被占用，加入等待队列，if里的value是被减过的。如果等

于0,那么value被减过之前是1,有资源，就不用等待了

bIock();

1}

signaI(semaphre*s)

{s->vaIue++;

if(s->vaIue<=0)

//如果有进程在等待，就把第一个进程移除。注意if里的value是被加过的，

如果value=0,那么就没有进程在等待

{removeaprocessPfroms->list;

wakeup(P);

1

)

信号量中的整型变量S表示系统中某类资源的数目。

当其值大于0时，表示系统中当前可用资源的数目；

当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

P,V操作类似

P,V操作是原语

利用信号量实现互斥

设S为两个进程P1、P2实现互斥的信号量，S的初值应为1(即可用资源数目为

Do只需把临界区置于P(S)和V(S)之间，即可实现两进程的互斥。

卜解法工

除理信号量实现前趋关系

■例如：Pl、P2、设七个同步信号

P3、P4、P5、P6、b、c、d、e、

为一组合作进f、g分别表示进程

程，其前驱图如之间的前驱关

下所示，试用P、系，如图所示，

V操作完成这六个其初值均为0。这

进程的同步。六个进程的同步

描述如下：

P2()

解法2

P(a)；

执行P2的代码;-设五个同步信号量fl、f2、f3、f4、f5分

v(c);G别表示进程Pl、P2、P3、P4、P5是否执

v(d);

P5行完成，其初值均为0。这六个进程的同

步描述如下：

3

■0表示未完成，1表示完成了

P2()

{

犬仕)；

执行P2的代码;

v(f2);

V(⑵；

死锁：两个或多个进程无限等待一个事件的发生，而该事件正是由其中一个的等

待进程引起的。

饥饿：无限期的阻塞。进程可能永远都无法从它等待的信号量队列中移去

经典同步问题：

有限缓冲问题生产者一消费者问题

它描述了一组生产者进程向一组消费者进程提供产品，它们共享一个有界缓冲

池。缓冲池中的每个缓冲区可以存放一个产品，生产者进程不断生产产品并将产

品放入缓冲池中，消费者进程不断从缓冲池内取出产品并消费。

设置两个同步信号量empty、full,其初值分别为n、0。

//empty代表缓冲区空的区域个数，fuII代表缓冲区被填充的区域个数

mutex是确保对缓冲区的访问互斥的信号量，初值为1

<4生产者消费者

—生产一个产品；p(full)；

p(empty)；p(mutex)；

p(mutex)；从缓冲区中取一个产品;

将一个产品送入缓冲区;v(mutex)；

v(mutex)；v(empty)；

v(full)；消费一个产品；

无论在生产者进程还是在消费者进程中，P操作的次序都不能颠倒，否则将可能

造成死锁。

读者-写者问题

第一读者-写者问题：要求没有读者需要保持等待除非有一个写者已经获得允许

使用共享数据

第二读者-写者问题：一旦写者就绪，不会有新读者开始读操作

用信号量解决读者-写者问题：

目标：允许多个读进程同时读此数据对象，

但是一个写进程不能与其他进程(不管是写进程还是读进程)同时访问此数据对

象

互斥信号量mutex,初值1,共享变量readcount记录当前读进程数，初值0,写

互斥信号量writer,用于实现写进程与写进程和读进程的互斥，初值为1

读者：

p(mutex)；

if(readcount-0)p(writer)；

〃如果没有读者访问，则等待写者的完成。如果有读者，则直接访问临界区

readcount=readcount+1；

v(mutex)；

读数据集；

p(mutex)；

readcount=readcount-1；

if(readcount==0)v(writer)；//所有人读完才能写

v(mutex)；

Mutex用于保护readcount的互斥访问

哲学家进餐问题：

第i个哲学家活动算法描述：

p(stick[i])；

p(stick[(i+1)%5])；

进餐；

v(stick[i])；

v(stick[(i+1)%5])；

思考；

可能会死锁

解决方法：至多允许四个哲学家同时进餐。

仅当左、右两支筷子均可用时，才允许拿起筷子进餐。

奇数号哲学家先拿左筷子再拿右筷子，偶数号哲学家相反。

睡眠的理发师问题

理发店里有一位理发师，一把理发椅和N把供等候理发顾客坐的椅子。

如果没有顾客，理发师睡眠，当一个顾客到来时叫醒理发师；

若理发师正在理发时又有顾客来，那么有空椅子就坐下，否则离开理发店。

为解决睡眠的理发师问题，应使用三个信号量：

customers记录等候理发的顾客数(不包括正在理发的顾客)；初值为0

barbers记录正在等候顾客的理发师数；初值为0

mutex用于互斥。初值为1

变量count记录等候的顾客数，它是customers的一份拷贝。之所以使用count

是因为无法读取信号量的当前值。

理发师：

p(customers)；/*是否有等候的顾客*/

p(mutex)；

count=count—1；/*顾客数减1*/

v(barbers)；/*理发师开始理发*/

v(mutex)；

理发；

顾客：

p(mutex)；

if(count<N)

{count=count+1

v(customers)；

v(mutex)；

p(barbers)；

理发；}

elsev(mutex)；/*无空椅子则离开*/

Chapter7死锁

死锁：是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作

用，这些进程都将永远不能向前推进

可剥夺资源：某进程获得这类资源后，该资源可以被其他进程或系统剥夺，如

CPU,存储器

非剥夺资源：系统将这类资源分配给进程后，再不能强行收回，只能在进程使用

完后主动释放。如打印机、读卡器

注：竞争可剥夺资源不会产生死锁。

永久性资源：可顺序重复使用的资源，如打印机

消耗性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又

称为临时性资源。如消息

注:竞争永久性资源和临时性资源都可能产生死锁

死锁产生的原因：竞争资源，进程推进顺序不当

死锁发生的条件：互斥，占有并等待，非抢占，循环等待（等待资源的进程间存

在环）

通过资源分配图来观察进程是否发生死锁

如果资源分配图没有环，系统就没有进程死锁。如果分配图有环，那可能产生死

锁

有死锁的资源分配图：有环但没有死锁的资源分配图

图中P1占有R2的一个实例可知P4释放资源后就不会死锁

P1申请并等待R1的一个实例

处理死锁的基本办法：忽略思索，预防死锁，避免死锁，检测死锁及解除

避免死锁：

1.打破占有并等待，要求进程在执行前一次申请全部的资源，或只有没有占有资

源时才可以分配资源。导致资源利用率低，可能出现饥饿

2.破坏非抢占条件，如果一个进程占有资源并申请另一个不能立即分配的资源，

那么其现已分配的资源都可被抢占。缺点：实现复杂，释放已获得资源可能造成

前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。该

协议通常应用于状态可以保存和恢复的资源，如CPU寄存器、内存

3.破坏循环等待：有序资源分配法;将所有资源按类型排队，并赋予不同序号，

要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。能保证没

有死锁

安全状态：系统能按某种顺序如＜P1、P2…、Pn＞来为每个进程分配其所需的资

源，直至最大需求，使每个进程都可以顺利完成

＜P1＞P2、…、Pn＞为安全序列

银行家算法：（举例）

。时刻的安全性检查

《银行家算法例T

NeedO:7,4,3Needl:1,2,2Need2:6,0,0Need3:0,1,1Need4：4,3,1

■假定系统中有5个进程PO、Pl、P2、P3、P4和三种类型的资AllocO：1,1,0Allod：20」Alloc2：3,0,3Alloc3：2,1,1Alloc4:1,0,2

源A、B、C,数量分别为12、5、9,在TO0寸刻的资源分配情Avail33213420

况如下所示。

w遵情况WorkNeedAllocWDrk+Alloc

进屋'Finish

情况MaxAllocationNeedAvailableABCABCABCABC

进程、

ABCABcABCABCPl332122201533true

P0853110743332

P3533011211744true

P1323201122

P4744431102846true

P2903303600

P28466003031149true

P3222211011

P011497431101259true

P4533043

121—~A

TO时刻存在着一个安全序列＜PkP3、P4、P2、P0＞,故系统是安全的。

资源分配图简化判断是否死锁：找出一个既不阻塞又非孤立的进程结点pi,进

程pi获得了它所需要的全部资源，能运行完成然后释放所有资源。如果能消去

所有边，则不死锁

资源抢占来处理死锁：逐步从进程中抢占资源给其他进程使用，直到死锁环被打

破为止。

选择一个牺牲：最小代价

回退：返回到安全状态，然后重新启动进程

饥饿：同一进程可能总是被选中

处理死锁的综合方法：将系统中的资源按层次分为若干类，对每一类资源使用最

适合它的办法解决死锁问题。即使发生死锁，一个死锁环也只包含某一层次的资

源，因此整个系统不会受控于死锁。

把资源分为：内部资源（有序资源分配法），主存资源（资源剥夺法），作业资源

（可分配的设备和文件采用避免方法），交换空间（静态分配法）

对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家

算法是属于避免，破坏环路等待条件是属于预防，而剥夺资源是

解除的基本方法

Chapter8内存管理

内存：即存储器、主存，分为两大部分：系统区，用户区

内存由很大一组字或字节组成，每个字或字节都有它们自己的地址

存储器管理的功能

存储空间的分配和回收

地址变换：将逻辑地址变换成物理地址

存储保护：防止因用户程序错误破坏系统或其他用户，防止程序之间的相互干扰

存储扩充：在逻辑上为用户提供一个比实际内存更大的存储空间

CPU能直接访问的存储器有：主存，高速缓存和寄存器

将程序装入内存有三种方式:绝对装入方式（编译时产生绝对地址的代码无需地

址变换），可重定位装入方式（编译时产生相对地址的目标代码），动态运行时装

入方式（执行时进行地址变换）

逻辑地址：由CPU产生的地址。用户编程时所用的地址，又称相对地址、虚地址

物理地址：内存单元所看到的地址。又称绝对地址，实地址

逻辑地址空间：逻辑地址的集合

物理地址空间：物理地址的集合

为了确保每个进程都有独立的内存空间。

基地址寄存器，界限地址寄存器

300040120900

那么程序可以访问300040-420900的所有地址

内存管理单元（MMU,memory-management-unit）:运行时把虚拟地址映射到物

理地址的设备。在MMU中，用户进程所产生的地址在送交内存前都将加上重定位

寄存器的值

地址变换：将逻辑地址转换为物理地址。又称地址映射、重定位

地址变换分两类：静态地址变换（程序装入时一次完成不改变，需要连续存储空

间，难共享），动态地址变换（在程序执行过程中，每次访问内存之前将要访问

的地址转为内存地址，不需连续空间，可以实现虚拟存储）

动态加载：子程序只有调用时才被加载。优点：不用的子程序不会被加载

动态链接：链接被推迟到执行时期

存根：小段代码用来定位合适的内存驻留库程序

程序的链接：链接程序的功能是将经过编译或汇编后得到的目标模块以及所需的

库函数装配成一个完整的装入模块

实现链接的三种方式：静态链接，装入时动态链接，运行时动态链接

静态链接：在程序运行之前，将各目标模块及其所需的库函数装配成一个完整的

装入模块

装入时动态链接：源程序编译后所得到的目标模块在装入内存时边装入边链接。

运行时动态链接：将某些目标模块的链接推迟到执行时才进行。即在执行过程中，

若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存并

链接到调用者模块上。

覆盖技术：把一个大程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单

位。把程序执行时不要求同时装入内存的覆盖组成一组叫覆盖段。将一个覆盖段

分配到同一个存储区中，这个存储区称为覆盖区。覆盖区的大小由覆盖段中最大

的覆盖确定。

覆盖技术主要在早期系统使用，要求专业的程序员给出覆盖结构。

交换:进程可以暂时从内存中交换到备份存储上，当需要再次执行时再换回内存。

（例如低优先级内存被换出，这样高优先级进程可以装入执行。这种交换又被称

为滚出，滚入）

交换空间管理：交换空间设置在外存交换区，交换空间管理的主要目标是提高交

换速度

交换空间采用连续分配方式，使用与动态分区分配类似的数据结构和分配算法

交换技术由操作系统自己完成

连续内存分配

内存通常分为两个区域：一个驻留操作系统，通常位于内存低端；一个驻留用户

进程，通常位于内存高端

内存保护：防止一个进程有意无意的破坏系统或其他进程（内存访问不能越界）

常用的存储保护方法：界限寄存器法，存储保护键，环保护机制，访问权限

界限寄存器法：通过对每个进程设置一对界限寄存器（上下界寄存器或基址限长

寄存器）来防止越界访问（如果越界则产生越界中断），达到存储保护的目的。

存储保护键：为每个存储块分配一个保护键，相当于一把锁；进入系统的每个作

业赋予一个保护键，相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，

若二者匹配，则允许访问。否则发出保护性中断信号

环保护机制：处理器状态分为多个环，分别具有不同的存储访问特权级，通常环

的编号越小，特权级越高。

存取权限：除上述保护方案外，还有四种存取权限：禁止做任何操作，只能执行,

只能读，读/写

内存分配：

分区储存管理分为：固定分区，动态分区

分区分配算法：首次适应算法，循环首次适应算法（从上次找到的空闲分区的下

一个开始，使存储空间利用均衡），最佳适应算法（分区按容量递增的次序排列）,

最坏适应算法（分区按容量大小递减）

模拟实验显示，首次适应和最佳适应难分伯仲，但是首次适应快

内部碎片：分配给作业的存储空间中未被使用的部分

外部碎片：系统中无法利用的小存储块（因为它们太小了）

解决碎片的方法：拼接/紧缩，要浪费很多的处理机时间

分页：将物理内存分为固定大小的块，称为帧。将逻辑内存也分为同样大小的块,

称为页。在为进程分配存储空间时，总是以块为单位来分配，可以将进程中的某

一页存放到主存的某一空闲块中。

分页没有外部碎片，有内部碎片

页的逻辑地址由页号和页内位移（pageoffset）组成

页的大小一般为512B-8KB

页表：记录页面在内存中对应物理块的数据结构

分页机制中，每一次的数据/指令存取需要两次内存访问（一次页表一次数据）

TLB（translationlook-asidebuffer）转换后备缓冲区，即快表，存放当前

访问的那些页表项

TLB失效：页号不在TLB内，则访问页表

如果TLB中的条目已满，则需要替换，替换策略有LRU（最近最少使用），随即

替换等。有的TLB允许有些条目固定下来

TLB命中率：一般80%-90%

有效内存访问时间：如果内存一次存取时间是m,TLB访问一次时间是n,命中

率为P。那么有效内存访问时间=p*（n+m）+（1-p）（2m+n）

存储保护

有效-无效位（valid-invalidbit）:附在页表的每个表项中。当该位有效时，表

示相关的页在进程的逻辑地址空间内，是合法的。反之不合法

共享页：如果代码是可重入代码（reentrantcode纯代码）则可以共享（每个

进程可以有自己的数据页，但可用同一段代码，访问内存的同一块）

可重入代码是不能自我修改的代码，它在执行期间不会改变

分段（segmentation）：（考虑程序的逻辑完整性）一个程序是一些段的集合，一

个段是一个逻辑单位。如一个程序可分段为：代码，全局变量，堆，每个线程的

栈等

每个分段有自己的名字，由0开始编址并采用一段连续的地址空间。每段分配一

个连续的内存区，但各段之间不要求连续

段表，类比页表

分段不会产生内部碎片

三种不连续内存管理方式是：分页存储管理、分段存储管理和段页式

存储管理（访问两次内存）。

Chapter9虚拟内存

虚拟内存技术：允许执行进程不必完全在内存中。是一种以时间换空间的技术

虚拟存储器的特征：离散型（不连续内存分配），多次性（一个作业多次装入内

存），对换性（允许运行中换进换出），虚拟性（逻辑上扩充内存）

按需调页：只有在需要的时候才调入一个页（懒惰交换）

页错误：当访问无效页时，会产生页错误陷阱.分页硬件在通过页表转换地址时，

将发现已设置了无效位，会陷入操作系统。

缺页中断:缺页中断处理程序根据该页在外存的地址把它调入内存。若内存有空

闲空间，则缺页中断处理程序只需把缺页装入并修改页表中的相应项；若内存中

无空闲物理块，则需要先淘汰内存中的某些页，若淘汰页曾被修改过，则还要将

其写回外存。

有效访问时间：

内存的读写周期为t，缺页中断服务时间为tl（包含读入缺页、页表更新、快表

更新时间），快表的命中率为a,缺页中断率为f,快表访问时间为e,则有效

存取时间可表示为：

EAT=a*（e+t）+（1-a）*［（1-f）*2（e+t）+f*（tl+2（e+t））］（里

面包括了查快表时间）

页面置换（页面淘汰）：

为进程分配的帧越多，页错误越少

内存的引用序列称为引用串（referencestring）

采用如下引用串讨论页置换算法：70120304230321201701

（分配3个可用帧）

先进先出置换算法（FIFO）

（会有15次页面错误）（注：计算页面错误时，注意前三个必产生3个页面错误）

Belady异常：页错误率可能随分配的帧数的增加而增加

最优置换（OPT算法/MIN算法）（不会有belady异常）产生的页错误率最低

置换最长时间不会用到的页（看未来）

难实现

LRU页置换最近最少使用算法。可以画栈看会有多少页面错误

近似LRU算法：附加引用位算法（被使用过就标记1并添置高位（前八位）舍弃

最后一位），二次机会算法，增强型二次机会算法

基于计数的页面置换：最不经常使用算法（LFU）,最常使用页置换算法（MFU）

页面缓冲算法：页面缓冲算法是FIFO算法的发展。它在系统中保存一个空闲帧

缓冲池。

页面缓冲置换算法采用FIFO选择被置换页面，选择出的页面不是立即换出，而

是放入空闲帧池。

帧分配

帧的最小数量：分配的帧要大于最少数量（不然产生太多的页面错误）

分配算法：平均分配，比例分配（根据进程大小，将可用的帧分给每个进程），

按优先级分配

全局分配与局部分配

固定分配和可变分配

将分配策略和置换范围组合可得如下三种策略：

固定分配局部置换

可变分配全局置换

可变分配局部置换

颠簸/抖动：频繁的页调度行为而几乎不能完成任何有效的工作。如果一个进程

在换页上用的时间多于执行的时间，那么这个进程就在颠簸。

Chapter10文件系统接口

文件系统：操作系统中与管理文件有关的软件和数据的集合。

文件系统负责管理外存上的文件，并为用户提供对文件进行存取、共享及保护的

手段。

文件是具有文件名的一组相关信息的集合，文件存放在外存上的。

文件由若干记录组成。

记录是一些相关数据项的集合。

数据项是数据组织中可以命名的最小逻辑单位。

文件属性包含：名称，标识符，类型，位置，大小，保护，时间日期和用户标识

所有的文件的属性信息都保存在目录结构中

通常目录项包含文件名及标识号，而标识号定位文件其他属性信息。

文件操作：建立，删除，读，写，打开，关闭（文件的操作除了正常的访问之外,

还要包括对目录项的操作）

在文件内重定位：搜索相应的目录表项，设置当前文件指针给定值

文件类型：实现文件类型的常用技术是在文件名称内包含类型：如名称.扩展名

文件分类方法

按用途分类：系统文件（系统软件构成的文件），库文件（系统提供给用户使用

的各种标准过程、函数和应用程序），用户文件（用户委托文件系统保存的文件）

按保护级别分类：只读文件，读写文件，执行文件（允许核准用户调用执行，但

不允许读写），不保护文件（不加任何访问限制）

按信息流向分类：输入文件（来自输入设备的文件），输出文件，输入输出文件

（如磁盘上的文件，可以读也可以写）

按数据形式分类：源文件（由源程序和数据构成的文件），目标文件（源程序经

过编译但未链接成可执行代码的目标代码文件），可执行文件（链接过的可运行

文件）

文件结构：

逻辑结构：又称文件组织，是从用户观点出发所看到的文件组织形式。

物理结构：又称文件的存储结构，是文件在外存上的存储组织形式。

文件的逻辑结构：记录式文件（有结构文件），流式文件（无结构文件，由字符

序列构成）

记录式文件的组织方式：顺序文件（顺序排列，记录通常是定长的），索引文件

（有索引表），索引顺序文件（分组顺序排列，索引）

文件的物理结构：顺序结构（连续），链接结构（指针），索引结构（索引表）

文件存取方法：顺序存取法（按照文件中记录的顺序依次访问），直接存取法（任

意顺序快速读写），按键存取法

目录：用来组织文件。目录可看作符号表，它能将文件名称转换成目录项。

存储结构：每个磁盘分区可以创建一个文件系统。这些分区可以组合成更大的结

构-卷。卷可以看成虚拟磁盘。

文件由文件说明和文件体两部分组成。

文件控制块：即文件说明是保存文件属性信息的数据结构。包含，文件名，文件

类型，文件结构，文件物理位置，存取控制信息，管理信息

文件目录与目录文件：

目录：文件控制块的集合。即文件控制块是一个目录项。

目录文件：文件的内容为目录信息。

目录的功能：

实现“按名存取”：用户只需提供文件名就可以对文件进行操作。这是目录管理

的最基本功能。

提高检索速度

允许文件同名：不同目录下的文件可以使用相同名字。

允许文件共享

目录结构：

单级目录结构（所有文件被包含在一张目录表，每个文件占一个表目）

二级目录结构（将文件目录分为，主文件目录（记录用户名以及用户文件目录的

位置），用户文件目录）

多级目录结构（又称树形目录结构，在多级目录结构中，第一级目录称为根目录

（树根），目录树中的非叶节点均为目录文件（又称子目录），叶结点为文件。）

图形目录结构（无环图目录，允许目录含有共享子目录和文件。通用图目录）

路径名：是一个字符串，该字符串由从根目录出发到所找文件的通路上所有各级

子目录名和该文件名用分隔符连接起来构成

从根目录出发的路径称为绝对路径（absolutepathname）0

相对路径（relativepathname）：由从当前目录出发到所找文件的通路上的所

有目录名与数据文件名用分隔符连接起来而形成。

有两个特殊目录：

“表示给定目录的父目录

”.表示当前目录

文件共享：是指不同用户可以共同使用某文件。

共享语义：是文件系统对共享文件或目录冲突访问的处理方法。不同共享语义定

义了对缓存一致性问题的不同解决方案。

一致性语义：描述多用户同时访问共享文件时的语义。这些语义规定了一个用

户所修改的数据何时对另一个用户可见

UNIX语义：一个用户对已经打开的文件进行写操作，可以被同时打开同一文件

的其他用户所见

会话语义（AFS语义）：一个用户对打开文件的写不能立即被同时打开同一文件

的其他用户所见。

不可修改共享文件语义：一旦一个文件被其创建者声明为共享，它就不能被修改。

（文件名和内容都不能被修改）

文件系统的早期实现：绕道法（绕到共享文件上方的目录），链接法（将一个目

录中的链指针直接指向被共享文件所在的目录），基本文件目录表

Chapter11文件系统的实现

分层文件系统

文件系统按层组织：I/O控制层，基本文件系统层，文件组织模块层，逻辑文件

系统层

I/O控制层：由驱动程序和中断处理程序组成，实现内存与磁盘之间的信息传输。

基本文件系统层：向合适的设备驱动程序发送一般命令就可对磁盘上的物理块进

行读写

文件组织模块层：将逻辑块转换为物理块，空闲空间管理器

逻辑文件系统层：管理元数据信息，管理目录结构，通过文件控制块来维护文件

结构。

用于文件系统管理的内存信息：

内存安装表：